Consider the following graph representation of an ad-hoc network, where vertices represent devices and edges indicate...

Transcribed Image Text:

Consider the following graph representation of an ad-hoc network, where vertices represent devices and edges indicate pairs of vertices that can directly communicate with each other. 6 A 4 2 3 5 SBA algorithm: Answer the following questions given that the network uses the Scalable Broadcast Algo- rithm (SBA). Pb 1. [2 pts] Suppose node 1 has a message to broadcast to all nodes. Use notation to identify the data structures (set C, (m)) maintained by the neighbours i of node 1. Pb 2. [2 pts] Use principle to determine which node is next to decide about re-transmitting m or not (the node with the smallest index is next). Specify if this node re-transmits m. If applicable, iden- tify all the nodes i who receive this possible second transmission and provide the contents of set C; (m) for all the affected nodes i. Pb 3. [4 pts] Answer question Pb 2. for each of the remaining nodes that decide on re-transmitting m, until the broadcast procedure is complete. Pb 4. [2 pts] In order for the broadcast algorithm to work, certain pieces of information need to be attached to message m as part of a header. Identify all pieces of information (eg: source address, sequence numbers, etc) and justify why you think they are important. Define a header structure that contains your list. Recall that the maximum packet size id 32 bytes, and we must allocate at least 4 bytes (an integer) for the payload m. NOTE: design your header structure so that it is compatible with the Hello message structure from PA3 (use the "type" and "source address" fields identified there, and feel free to add any fields following the "source address" or use the unused field x from Hello). KBB algorithm: Repeat questions Pb 1.-Pb 4. using the KBB algorithm for the same network and scenario of node 1 broadcasting message m. Consider the following graph representation of an ad-hoc network, where vertices represent devices and edges indicate pairs of vertices that can directly communicate with each other. 6 A 4 2 3 5 SBA algorithm: Answer the following questions given that the network uses the Scalable Broadcast Algo- rithm (SBA). Pb 1. [2 pts] Suppose node 1 has a message to broadcast to all nodes. Use notation to identify the data structures (set C, (m)) maintained by the neighbours i of node 1. Pb 2. [2 pts] Use principle to determine which node is next to decide about re-transmitting m or not (the node with the smallest index is next). Specify if this node re-transmits m. If applicable, iden- tify all the nodes i who receive this possible second transmission and provide the contents of set C; (m) for all the affected nodes i. Pb 3. [4 pts] Answer question Pb 2. for each of the remaining nodes that decide on re-transmitting m, until the broadcast procedure is complete. Pb 4. [2 pts] In order for the broadcast algorithm to work, certain pieces of information need to be attached to message m as part of a header. Identify all pieces of information (eg: source address, sequence numbers, etc) and justify why you think they are important. Define a header structure that contains your list. Recall that the maximum packet size id 32 bytes, and we must allocate at least 4 bytes (an integer) for the payload m. NOTE: design your header structure so that it is compatible with the Hello message structure from PA3 (use the "type" and "source address" fields identified there, and feel free to add any fields following the "source address" or use the unused field x from Hello). KBB algorithm: Repeat questions Pb 1.-Pb 4. using the KBB algorithm for the same network and scenario of node 1 broadcasting message m.

Answer rating: 100% (QA)

For the Scalable Broadcast Algorithm SBA Pb 1 The set Cm maintained by the neighbors i of node 1 wou... View the full answer