ELECINF344/381

Partie interactive du site pédagogique ELECINF344/ELECINF381 de Télécom ParisTech (occurrence 2011).

Catégories

MB Led : Algorithm

 

As Samuel noticed that there is not formal description of the algorithm, I will do this now.

First of all, all the messages use the packet structure giving by Cédric here. So, they all have an ID and we know who is the sender. I will start by showing all the messages and then I’ll explain the algorithm.

List of the differents messages

There are a large number of messages and they all have specifics arguments.

  • PING
  • PONG (idPacket)
  • ACK (idPacket)
  • START_ELECTION
  • CANDIDATE (leaderID, membersInNetwork)
  • REJECTED (leaderID, membersInNetwork)
  • ELECTED (leaderID, membersInNetwork)
  • YOUR_POSITION (leaderID, myOrientation, yourI, yourJ, myInterface)
  • NETWORK (blockID, hisI, hisJ, hisLeaderID)
  • RESET_NETWORK
  • TURN (blockID, rotation)
  • TIME(time, synchroID)
  • CMD_DATA

1. Generalities

For the algorithm, I use « interfaces » which are aliases of UARTs. The UARTs are used by the IrDA while the interfaces are used for the algorithm. For example, interface 0 represents the north (and is in reality UART 2), interface 1 is the east (but in reality it’s UART 5), etc.

All the blocks know :

  • their own ID (given by the STM32_ID),
  • their leader ID,
  • their orientation (which « interface » represents the north)
  • the number of member in their network
  • their « nearest » neighbors (who is in front of my UART2,3,4 and 5) : the Interface table.

They have a network table (for each ID, they know the position (i,j) and who was the leader when they had the information) and an election table (for each ID, they know his state in the election) . We will try to replace theses tables by a list in the future.

Every message except PING and PONG is answered by an ACK message. The PONG message contains the PING ID so it is itself a ACK. If there is no ACK, the message is resend.

When starting all of this, the block starts the timer 5 of the STM32 for the synchronization. (see section 4)

 

2.The identification

Each block sends PING messages in the 4 directions and start a timer for each direction.
When receiving a PING message, a block sends back a PONG message as fast as he can.
When it receives a PONG message, the block knows who is his neighbor and changes his Interface table. Furthermore, the block stops the timer.
If the block is aware that there was a neighbor but there is no answer at the end of the timer, it sends a RESET_NETWORK message (see section 5).

If this interface wasn’t ready before, the block has to check if he knew the neighbor (in order to notice a turn of the other block) or not (in order to start an election.)

Explanation of this check :

When receiving a PONG message from a « new neighbor », the block checks if the « new neighbor » was a neighbor before or not. This is checked by comparing the current interface table and the saved interface table.
If the interfaces tables don’t match, there is an election.
Else, the block  sends to the block TURN (myID, rotation). The rotation is the difference of index between the current interfaces and the saved interfaces.

To compare the interfaces, the block waits a little bit for PONG message from all the interfaces.

 

 

3. The election

When it’s the first PONG from a new neighbor, an election takes place.
When starting an election, the block starts a timer. If his candidature isn’t refused at the end of the timer, he is elected and he broadcasts the information.

In the election, the blocks send messages for their « network » (all the blocks with the same leader). Here, the « network » can be a network of one block (so the leader ID is his ID).
The block sends a START message to his neighbors not in his « network » (and this is broadcast). All blocks sends a CANDIDATE message with his leaderID and the numbers of members in his network.

The winner of the election is the network with the larger number of blocks in his network. If this isn’t enough to decide , the lower leader ID is declared winner.

When receiving a CANDIDATE message, the block checks if the candidate can win or not. If he can’t, the block broadcasts a REJECTED message. If he cans, the block broadcasts the CANDIDATE message.

When receiving a REJECTED message with his leader ID, the block stops the timer  : he can no longer win the election.

At the end of the timer, one network is the winner. It sends the ELECTED message and everyone broadcasts it.

 

4. After the election

After the election,the leader is in (0,0). If he was part of a network, he sends his information to the others by sending NETWORK messages.
For every NETWORK message received, the block analyzes it : if the leaderID of the NETWORK message isn’t his leaderID, it drops the message. Else, if the message contains a good information, the block changes his network table and transmits it.

Then he sends the POSITION message : [YOUR_POSITION leaderID, myOrientation, yourI, yourJ, myInterface]. The block which receive this calculate his new orientation (with « myOrientation », « myInterface ») and change his position in his network table. Then it calculate the position of his neighbors and sends the message.

 

The leader sends TIME messages (which are broadcasted if they are « young » enough.. That explains the synchroID) from times to times. In his TIME message, there is his current time (according to the STM32). The block that receive this message update his new « current time » (with a function which take into account the emission time) and then sends his current time to others, etc.

5. If someone leaves

If some block leaves the network, there is no PONG message to the PING message of his former neighbor. The former neighbor notices that and broadcasts a RESET_NETWORK message.
This message is broadcast to all the network and means that every data (leaderID, network table, …) must be restarted; the interface table is saved (for the TURN mechanism). A new election starts soon after. (plus the orientation, network information, synchro…).

 

The turn mechanism isn’t implemented yet and the ACK mechanism has to be implemented very soon.

Then, there will be messages for the applications (games, firmware upgrade, …).

Sur le même sujet :

  1. MB Led: Working IrDA and colored LEDs.
  2. MB Led et IrDA: paquets, procédure de test…
  3. MB Led: Journée de présentation
  4. MB Led: Des séparations difficiles…
  5. MB Led: Algorithmie

3 comments to MB Led : Algorithm

  • Micka

    I don’t understand some points:
    – When the election is finished, the leader sends a NETWORK message with « hisI » and his « hisJ ». How is his position determined? I mean if the map doesn’t exist yet, are (i,j) set to (0,0)? If yes why do you send them? If no how are they determined?
    – What is the ELECTED message? And what is the « membersInNetwork »? What is this network? The new one or the old one? If it is the new one how do you know the number of members? If it is the old one why do you need it?
    – What’s the link between the RESET_NETWORK message and the START_ELECTION message? Which one starts the timer?
    Thank you :)

  • Guillaume

    Hey Micka!
    -When the election is finished, the leader is in (0,0). He sends to his neighbor on his right « you’re in (0,1) », etc. When receiving this message, a block changes his position in the network table and then sends a POSITION message to his neighbors.

    -The ELECTED message says who is the leader. membersInNetwork is the number of blocks who were in his network during the election; it isn’t really useful but I used this because the others messages for the election (CANDIDATE, REFUSED) have the same pattern (leaderID, membersInNetwork).

    I will give you an example : there are 2 networks : network1 (3 blocks,leaderID = 4) and network2 -2 blocks, leaderID=1 ). The blocks from network2 send CANDIDATE (1,2), thoses from network1 CANDIDATE (4,3). The blocks from network1 will send REJECTED(1,2) and then ELECTED(4,3).

    -When receiving a RESET_NETWORK message, the block waits a little bit and then sends a START_ELECTION message so that an election could take place. It is the START_ELECTION message which starts the timer. (It’s always like that).

  • Ce n’est probablement pas une bonne idée d’avoir réinventé un protocole plutôt que de partir sur des choses comme un link-state routing protocol un peu modifié.