Supervisor: Kaisa Sere
Download 298.62 Kb.
|
- Navigate this page:
- 5.4.1Forwarding of RQMs
- 5.4.2Preventing Loops
- 5.4.3Forwarding of Data Messages
5.4 ForwardingIn this section, the forwarding of TRP will be discussed. This touches both forwarding of RQMs (control messages) and data messages (non-overhead). Actually, the forwarding of the RQMs is part of the routing stage because that is what we try to establish, a routing table entry for one or more destinations. Nevertheless, these messages are being forwarded and it seems natural to have them in the same section, which makes it easier to compare the two. 5.4.1Forwarding of RQMsWhen a node wants to send a data message to a destination node, it first checks whether it has a route entry (next-hop) for the destination. The next-hop can be found by checking if the destination is among the node’s neighbors, children (in updates) or if there is a routing table entry. The entry can be recorded when the node previously issued a query and received an answer, or when it forwarded someone else’s RQM. When forwarding such a message, an intermediate node can extract a next-hop for the source. If the node does not have an entry for the destination it wants to send data to, it will send a RQM to all appropriate neighbors. The appropriate neighbors are the preferred neighbor, neighbors connected by extralinks and to branches (the path to the extralink) that contain extralinks. An extralink in a branch is detected in the following way: The subroot will check the update messages gotten from its children to see if any of the nodes in its subtree has a link to a node that is not included in the subroot’s subtree. In practice, every node adding itself to an update message will mark itself as a member of the tree and put its neighbors in another section of the message. The nodes of the neighbor section can then be compared one-by-one to the member nodes and whenever a match is not found, an extralink is detected. The subroot will in effect calculate the next-hop to the node with the extralink which will also be done by the next-hop node and so on until the node with the extralink is reached (the whole branch is discovered). If the node that is being forwarded a RQM neither has an entry for the destination, it will also forward the message to its appropriate neighbors. On the other hand, if it does possess the requested route, it can acknowledge the RQM and send it back to the source. This activates the route that was discovered up until the RQM was acknowledged, concatenated with the acknowledging node’s route. The neighbor of the destination is bound to be able to answer the query at the latest. To maximize dissemination of routing information, nodes that are forwarding unacknowledged RQMs record a next-hop for the originator and when forwarding acknowledged RQMs a next-hop for the destination can be recorded. 
Fig. 5 21: RQM format. The RQM message format is shown in figure 5-7. The first field identifies message types. The originator and destination fields are self-explanatory and used for the purposes explained above. The hops_traversed field is used to discriminate between copies of the same message that have taken different routes and will help reduce the message complexity further. Every node that forwards a RQM adds one to this field (an acknowledged RQM will contain the number of round trip hops when received by the initiator). If it has not seen this message or if it has seen it, but the hops_traversed is less than in the previous copy, it will still forward it. This applies to acknowledged and unacknowledged RQMs. In figure 5-8 a simple scenario is given, which explains how a node is found. 
Direction of the unacknowledged RQM Direction of the acknowledged RQM Fig. 5 22: RQM broadcast.
The RQMs possess another important property because of the field hops_traversed. This field will guard against message loops in the following way. Every node records a message the first time it gets it. If it is received again, then the message will have traveled a loop and it will have a greater hops_traversed value and therefore discarded. So, the message will actually be allowed to travel once through a loop and then stopped. The same argument for loop-free routes can be argued for the acknowledged RQMs since the hops_traversed value continues to accumulate after it is acknowledged. Because RQMs are not allowed to travel loops from this follows that routes cannot be set up that contain loops, therefore, data messages cannot loop either. Since the header field containing the RQM ID is finite it will roll-over at some point and start over. This has to be taken into account when specifying how long a forwarded RQM is to be stored in order to detect loops and obsolete messages. If they are stored too long, a situation where unseen messages are dropped can occur. On the other hand if the message is stored for a too short a period, it might happen that seen messages are forwarded again. As a starting point it might seem to make sense that both the storage time (st_time) and the time for the number to roll-over (ro_time) are of the same length. According to figure 5-9 the RQM will be deleted at the same time as a new RQM with the same ID arrives. It might be possible that the next time the source sends a new message, it will have acquired a shorter, faster route, making the message travel with lesser delay. This means that we cannot store the message over a time that would correlate to the number of hops that the message has traveled. There is a factor from which we can begin to reason, namely the propagation delay of a packet. The nodes will have to store entries containing the source address, message ID and destination address in order to detect seen messages. 
Fig. 5 23: Message propagation. From figure 5-9 it can be seen that if the maximum time to store an entry is equal to the time it takes for the message ID to roll-over the entry will be deleted at the same time a new message with the same id arrives. But this is to assume that both messages will propagate through the network with the same speed. It is possible that the first message A is traversing a route that is congested and will be heavily delayed while the second message B with the same ID travels much faster. This problem is equivalent with the problem that arises when the source finds a faster route. In this case the time for (T+delayA+st_time) > (T+ro_time+delayB ) meaning that the message A will still be stored as B arrives with the same message ID. This causes an unseen message to be dropped. It is obvious that an assessment of the largest network thinkable has to be made and the network delay (net_delay, the delay that could be experienced in the longest route in a maximum sized network) of that. One should not make the mistake of thinking that message A could be deleted at time (T+delayA ) because node 2 has no way of knowing when that is - it does not know when the message was sent. This is why the destination must wait a maximum network delay time (net_delay) before deleting the message. The source has to be even more cautious and never assume that the message will reach the destination with the same speed every time (as the example above indicates). To deal with this the ro_time has to be made twice as large as the net_delay. Figure 5-10 and 5-11 will further demonstrate this. In this example we assume that worst case buffering delay at every node is 2 time units and traversal of a link “costs” 1 time unit. Since the longest loop-free path is 5 the net_delay is assessed to be 15 time units (assuming that the message is not buffered at the source). 
Fig. 5 24: Incorrect storage time. 
Fig. 5 25: Correct storage time. The ro_time has to be this long in order to take the possibility that the first message is delayed the maximum amount of time on the network, and stored for 15 time units at the destination. From figure 5-11 it can be seen that even if message A experiences the worst-case delay, it will be deleted when message B arrives with the same ID. This means that it is deleted at time 30 and that the other message cannot be received before that. The following pseudo code outlines the procedure for forwarding RQMs: receive RQM r. IF a r’s ID and originator matches some entry, add next-hop and distance for originator in r, to routing table. IF I have entry for destination d, add the distance to d to the RQM hops traversed. send acknowledged RQM r to originator. ELSE add one to hops_traversed. forward the RQM to appropriate neighbors. ELSE discard r. The algorithm for forwarding an acknowledged RQM is almost the same except now a next-hop for the destination is added to the routing table. At this time the forwarding node will have a next-hop for the originator unless breakage has just happened and operation will have to stop. A transport protocol will be needed to make this operation reliable. The acknowledged RQM thus follows the shortest route back provided that all the unacknowledged RQMs have reached the destination, traversing every possible path. This might not always happen right away, but since nodes continue to forward seen messages with shorter hops traversed, it is bound to happen sometimes. So it does not actually matter if the first acknowledge RQM takes a longer path. The hops_traversed is, naturally, copied from the unacknowledged RQM to the acknowledged RQM, and will continue to accumulate as it is forwarded back to the originator. This means that also acknowledged RQMs can be dropped if multiple copies arrive at a node that has seen one with shorter hops_traversed. And as stated before the intermediate node that acknowledges the RQM also has to add the distance from it to the destination to the hops_traversed header field. 5.4.3Forwarding of Data MessagesA data message is a message used to carry the users information. For these messages routes are set-up by RQMs, therefore the data messages follow paths between the originator of the RQM and the destination as long as the route is not broken. The path is broken when one node in the path moves out of radio range of the previous node. A node in the route detects breakage by checking that the next-hop is still in the set of neighbors provided by the MAC-layer before forwarding the data message. It is assumed that the message gets transmitted and received, and left to the higher layers to achieve reliable end-to-end transmission. More reliability can be achieved by trying to overhear that the node that was forwarded a packet also forwards it itself if the MAC-layer has this ability. Hop-by-hop acknowledgements are also possible although not used at the moment. TRP does provide a way for other nodes on the route to be notified of the breakage. The node that discovers the breakage sends a “destination unreachable” message that propagates back to the originator of the data message and will at the same time delete every next-hop entry at every node for that particular route. Thereafter the source sends a new route query, and can try this for several times before giving up. Naturally, a data message can be sent to a neighbor or a (grand) child in a tree without querying at all, because of the updates. Because the neighbor of the destination node can at the latest, acknowledge the RQM, the discovery process provides no information about the network to the destination. Letting the destination record a next-hop for the source of the data message can help this. Download 298.62 Kb. Share with your friends:
|