0
\$\begingroup\$

I am into developing a protocol using Token Passing topology. For Physical Layer RS485 will be used. All the nodes will be connected in a daisy chain. No node is initially known the address of the predecessor or successor nodes's address except it's own. Same software will run in each node. At power up one node must initialise and generate first token to circulate avoiding any collision. Which node will do this? There can be couple of strategies to start the process:

  1. On time domain, when predefined time intervals will be over and lowest address node will generate the token. But there might be more than one node may generate the token this will lead to collision.
  2. Node can detect it's own address from EEPROM or hard coded in software and if it's the lowest in all, it may generate the Token. But if this node is down due to any reason, system will halt.

Therefore what should be the most optimal strategy that only lowest ordered node will initiate and generate the Token without creating the collision.

EDIT: There is a cap on maximum nodes from 0 to 127.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ your second option doesn't seem to make any sense. You say no node knows the ID of its predecessor. So, how does a node with ID "14" know whether 14 is the lowest ID in the chain? It can't. \$\endgroup\$ Nov 4, 2023 at 21:37
  • \$\begingroup\$ @MarcusMüller Yes you are right. I edited the question. For range of nodes addresses. now node 0 will be the lowest , But what if node 0 fails? \$\endgroup\$
    – Israr
    Nov 4, 2023 at 21:57
  • \$\begingroup\$ Your edit doesn't help. Your node still can't know whether there's a lower ID in the system, unless it has address 0. But if it has address 1, how would it know that there is no node with address 0? \$\endgroup\$ Nov 4, 2023 at 22:18
  • 2
    \$\begingroup\$ You might want to explain what you really mean by daisy chain, as there seems to be two interpretations of it depending on your description about the protocol. Are all 127 nodes on the same global RS-485 bus, or are there just separate local RS-485 links between each two nodes? \$\endgroup\$
    – Justme
    Nov 4, 2023 at 22:41
  • 1
    \$\begingroup\$ @Israr I think what you want is something more like the CAN bus, which is multi-master and supports intrinsic arbitration in the protocols. I've performed something similar with open-drain shared lines from multiple asynchronous MCUs (wrote a white-paper on it discussing how robust methods accounting for sampling-variation will impact overall bus speeds and showing that it is important to reduce that uncertainty to a minimum.) I've no clue if some creative 'unbalancing' of the balanced RS-485 might work, or not. Being ignorant, I'm open to such an idea. \$\endgroup\$ Nov 5, 2023 at 3:08

2 Answers 2

1
\$\begingroup\$

The wording "Daisy-Chain" adds some confusion.

I'll assume you mean, that the physical wiring between devices is a "Daisy-Chain", but each node is connected to the same physical bus medium in a "multi-drop" configuration.

So, the bus can be depicted as: Image removed

(1) Fixed Token-Master

Your bus requires a single Node with a "Magic-Adress". If a node is configured to have this hard-coded and well documented adress on boot, it generates the token.

Examples are: Profibus and others used in automation. The Magic-Adress is "0". Usually, the main process PLC is then configured to have this adress.

(2) Token-contesting on boot

In your firmware, after the controller is stable, add a delay. This delay consists of a fixed period (e.g. 10ms) + Adress * Period.

After this delay is passed, boot the comm-stack.

The comm-stack starts listening and if a characters are received, it does not attempt to contest the token.

If however, no characters are received, the comm-stack starts blocking the bus by sending "some garbage" for a duration of (Max-Address + 2 )*Period. After this, a message saying "Hey, i'm the token master now" is broadcasted.

Note: Can add a big delay in boot-time (e.g 256IDs * 10ms = 2,56s). I used this approach often in hobby-projects and while "playing-around" with 128IDs and 1ms delay usually.

(3) Random token

Find some source of randomness in your Node (If embedded uC e.g Controller-ID, quarz config, ... ) and just "roll it out".

If a node happens to "roll" a hardcoded magic-value, it assumes the token and starts broadcasting "I'm master now - make frame hardcoded". If a collision is detected during the transmission (every node listens), everybody "rolls" again. If no collision is detected, the node grabs the token.

EDIT:

As Israr requested it in the comments, i'll detail the solution (2).

Each node has a way to configure the node-address. This can be via e.g. a physical DIP-Switch or via an EEPROM-Value. This adress (per question) ranges from 0-127DEC.

When the Node-Controller (assuming Microcontroller with custom firmware under your control) powers up, the usual initialization is done. After this is finished, a timer is used to generate a delay.

First, a fixed delay is done to ensure, that nodes powering up "slower/later" can also initialize their firmware to listen to the token-arbitration messages. However, before the delay is done, the firmware starts listening on the UART-Port for a generic "jamming" signal. This can be as simple as "Receive a character" or a "dedicated frame".

Secondly, a delay based on the address of the node is added. Node[0] does no extra delay, where as Node[127] does 127*Period of delay. This means, that the lower the address, to sooner the delay is over.

Now, as soon as the delay is expired, the firmware boots the comm-stack. The stack first checks, if a "jamming signal" was received during the previous delay. If not so, the node starts jamming the bus by sending a dedciated frame or just some garbage. If so, a node with a lower address is present on the network as it started jamming.

In both cases, another delay is done, to allow all "higher-address-nodes" to participate.

Now, the "jamming-node" stops jamming, broadcasts "I'm master now" and alle nodes initialize the comm-stack fully. After this, normal device operation can start.

Please see pseudo-code:

/* Flag to check if chars have been received */
volatile char CommStack_HasReceivedChars = 0U;

CommStack_StartListening(void){
    /* Configure to listen and enable RX ISR */
}

CommStack_StartJammingBus(void){
    /* Just send some garbage via DMA/ISR */
}

CommStack_StopJammingBus(void){
    /* Disable DMA/ISR */
}

CommStack_AssumeToken(void){
    /* Assume token and broadcast to all 
    * other nodes, that "i have the token now"
}

CommStack_RxISR(void){
    /* Set Flag */
    CommStack_HasReceivedChars = 1U;
}

CommStack_Boot(void){
    /* Setup, configure, do what not .... */
    /* Now check if jamming was detected
    * If so, a lower address is present in the bus
    * If not, start jamming to signal 
    * token is contested */
    if(  CommStack_HasReceivedChars == 0U ){
        CommStack_StartJammingBus();
        
        /* Now do a delay, until all untis have been booted
        * do this via timer delay again and then
        * stop jamming bus */
        for( char i = 0; i < ( 127 + 1 ) - Config_GetNodeAddress(); i++ ){
            Timer_DoDelay();
        }
        CommStack_StopJammingBus();
        Timer_DoDelay();
        CommStack_AssumeToken();
    } else {
        /* Block until boot process is done.
        * use ( 127 + 1 ), so that the node
        * is ready to receive the broadcasted "I'm master now"
        * after the ( 127 + 1 .... + 1 ) delay */
        for( char i = 0; i < ( 127 + 1 ) - Config_GetNodeAddress(); i++ ){
            Timer_DoDelay();
        }
    }
}

CommStack_RunNormalOp(void){
    /* All the bits and pieces .... */
}

void main(void){
    /* Configure all Peripherals
    * start listening before fixed delay,
    * so that nodes not yet fully booted
    * have a chance to participate
    * in the token arbitration */
    InitializeAllPeripherals();
    CommStack_StartListening();
    Timer_DoDelay();
    
    /* Do a delay based on the address for this node 
    * can break loop if "jamming" is detected */
    for( char i = 0; i < Config_GetNodeAddress(); i++ ){
        Timer_DoDelay();
    }
    
    /* Run Boot Stack - returns after jamming 
    * was detected or token was grabbed */
    CommStack_Boot();
    
    /* Normal Op from here on */
    CommStack_RunNormalOp();
    
    /* ...... */
}

Disclaimer

This solution seems "easy to implement" at first glance, however when using ISR/DMA based approaches the jamming procedure can lead to some weird edge cases due to nodes "beeing out of sync" on the delays. You'll have to do some testing and monitoring, to get the firmware reliable!

Also, i strongly suggest architect your comm-stack as "two-parts". The first-part handles only the initial token arbitration, where as the second part handles normal op. This makes maintenance and so on easier.

Furthermore, i also suggest to not send "garbage" during jamming, but sending a dedicated frame with know format and some CRC and so on. This makes debugging the field with a traffic analyzer way easier.

Also, i suggest drawing a time/action-plot to better understand the timing. There is potential for optimization in regard to the boot-time.

\$\endgroup\$
7
  • \$\begingroup\$ What is "comm-stack" ? \$\endgroup\$
    – Israr
    Nov 4, 2023 at 23:30
  • \$\begingroup\$ "I'll assume you mean, that the physical wiring between devices is a "Daisy-Chain", but each node is connected to the same physical bus medium in a "multi-drop" configuration." Yes that's the connection i am talking about. \$\endgroup\$
    – Israr
    Nov 4, 2023 at 23:41
  • 1
    \$\begingroup\$ I think random IDs are the only way to do this without any configuration at all. I suppose that slaves also need different IDs, so all nodes will have to generate IDs and then detect collisions and re-roll the dice. For example one node can grab master as you described and then query all IDs 0-127, and if a collision is detected tell both nodes with that ID to re-roll. Downside is that startup time is not fully predictable. \$\endgroup\$ Nov 5, 2023 at 0:16
  • 1
    \$\begingroup\$ @Israr I added details for Sol(2) \$\endgroup\$ Nov 5, 2023 at 9:09
  • 1
    \$\begingroup\$ Thank you for an Amazing Answer +100. I will try to code in OSI Model and use atleast 3 layers. Physical Layer(1), Data Link Layer(2), Application Layer(7). For Framing and Data Packeteing I will refer "Data Communications and Networking By Behrouz A.Forouzan". For Data Analysis I will try for WireShark . Hardware : (1) STM32f1 MCU. (2) TTL to RS485 Board. (3) CAT4 Cable. Generally i don't do hurry for accepting the answer. But this is more than enough . \$\endgroup\$
    – Israr
    Nov 5, 2023 at 14:12
1
\$\begingroup\$

If the nodes are already assigned unique addresses then it’s pretty straightforward. On startup, a node sends a “discovery” token marked with its ID. If a node receives a discovery token with a lower ID than its own ID, it passes it along to the next node. If the token has a higher ID, the node drops it. When a node receives its own discovery token, it knows it’s the lowest-numbered node.

\$\endgroup\$
1
  • \$\begingroup\$ It seems all the devices are on same bus, so a node can't pass on anything to any next node because the nodes don't know their position on a bus. \$\endgroup\$
    – Justme
    Nov 4, 2023 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.