Supervisor: Kaisa Sere
The Dynamic Source Routing (DSR) protocol
Download 298.62 Kb.
|
- Navigate this page:
- 3.5.1Route discovery process
- 3.5.2Route Maintenance
- 3.5.3Reflecting Shorter Routes
- 3.6 Optimized Link State Routing
3.5 The Dynamic Source Routing (DSR) protocolDSR [Johnson+96] uses its Route Discovery and Route Maintenance mechanisms to discover and configure source routes. DSR is a reactive protocol which discovers routes when needed. When a node forwards a discovery packet it adds itself to the route that has accumulated in the packet header. An interesting feature of DSR is that it supports unidirectional links if the underlying data link protocol supports this. DSR is also integrated with mobile IP (See mobile IP in 4.1). In contrast to AODV, DSR uses multiple routes, that is, the node that answers all the discovery messages it receives. 3.5.1Route discovery processThe route discovery process works as follows: If the sender has a route entry for the destination in its routing table it will copy that route to the header of the packet it is about to send. It will then transmit it to the first intermediate node in the route entry, which will know where to forward this package in order for it to reach its destination. If the sender on the other hand does not have an entry for the destination it will initiate a Route Discovery. The source node issues a Route Discovery by broadcasting such a message that contains the sender, destination, request ID and an empty intermediate node list. The intermediate node list is filled when the neighbors, in hope that the nexthop is the destination, rebroadcast the Route Request. Naturally, when the Route Request reaches the destination, it will send a Route Reply back to the source. If an intermediate node has an entry of a route to the destination it can stop the discovery process and concatenate the remaining hops to the accumulated route in the header so far and send this to the source of the Route Request. This is only allowed if the node that concatenates is itself part of the route. This limitation is required so that valid routes can be ensured. The Route Reply can be sent in a number of ways back to the originator of the Route Request. The logical approach would be to reverse the route found in the Route Request but this is possible only if every nexthop link on the route is bidirectional as required by IEEE 802.11. So, if a route to the source of the Route Request is not found in the routing table of the destination node and at least one node’s link in newly discovered route is unidirectional, then the destination must initiate a Route Request of its own. The second Route Request run the risk of starting a loop since the source of the first Route Request still does not have a route for the destination, making a Route Reply to the source of the second Route Request impossible. Therefore, a precaution must be taken in the form of a piggybacked message. The second Route Request from the destination node must piggyback the Route Reply onto its own Route Request message. Data messages for which addresses are not found in the routing table are kept in a send buffer until a Route Reply is received. A node cannot send an arbitrary amount of Route Requests, but is confined to an exponential backoff waiting period if a destination is not found. 3.5.2Route MaintenanceRoute Maintenance is a mechanism to ensure that the source route is intact and is defined in the following way: Every intermediate node that forwards a data packet is responsible for making sure that the packet was received by the nexthop neighbor. This can be done in a number of ways. If lower level protocol support is provided then this can be done by noting when the nexthop neighbor forwards it by listening for the next node to forward the message - this is known as "Passive hop-by-hop acknowledgement". An active acknowledgement can also be used at the link layer but if none of these are available, a network level DSR message must be used. When an acknowledgement is not received after a certain number of retries a Route Error is passed back to the source of a packet, which removes the route to the destination from its routing table and tries another route if it has one. If no other route is found, a new Route Discovery message has to be sent. Route Errors can also piggybacked on Route Discovery messages in order for this information to spread quickly throughout the network. When a node initiates a Route Requests there is a possibility that many nodes will have a route to the requested node, causing them all to answer the request. This will waste bandwidth, so a counter measure is taken. Whenever a node is about to send a Route Reply from its own cache, it will first backoff for a period corresponding to the length of the route to the source of the Route Request. During this time the answering node has its network interface in promiscuous14 mode, listening for a sign that the source has started using another shorter route. If not no such packet is registered by the answering node, it will send a Route Reply. 3.5.3Reflecting Shorter RoutesRoute shortening can be done by a node z operating in promiscuous mode when overhearing a transmission of a packet. This feature is useful when two nodes have moved closer to each other since they first started communicating. Suppose the scenario depicted in figure 3-3. 
Fig. 3 11: A partial route where x forwards a packet to Y also heard by node Z. Here, x and z have moved within radio range and z can therefore overhear the packet intended for y. From the header of the packet z can infer that it is the nexthop after y. In this situation z can send a gratuitous Route Reply to the original source of the packet containing a new route. This Route Reply contains the same route except that y has been expunged.
The Optimized Link State Routing Protocol (OLSR) is a table driven, proactive protocol, which exchanges topology information regularly with other nodes in the network. As the name implies, the protocol is an optimized version of the classical link state routing algorithm, modified for the requirements of ad hoc networks. An obvious advantage of proactive protocols is the shortened latency when routes are needed. On the other hand, a drawback of this is increased control traffic with unnecessary message passing, as all routes might not be needed. The authors of OLSR have taken this into account and reduced the amount of LSPs (see 3.1) by sending these only to a subset of its neighbors. The LSPs are called Topology Control (TC) messages in OLSR. Neighbors included in the TC are so-called Multipoint Relay Selectors (MPR), which are designated forwarding nodes for TCs. The other neighbors of the node only read the TC but do not forward it. In OLSR the age of a TC message is determined correctly on basis of sequence numbers. As a node is on the move, it develops links to new neighbors and in order for movements to be detected, control messages have to be sent with a high enough frequency. A necessary condition that the MPRs of a node n have to fulfill, is that they combined have bi-directional links to every node that is located two hops from n (some MPRs have links to some 2-hop neighbors, but every 2-hop neighbor hears some MPR of n). This condition is necessary for ensuring a complete broadcast (Fig.3-4 displays this configuration). When routes are calculated, only MPRs are taken into account as intermediate routers for a destination. Every node that receives information about another node’s MPRs will update its tables so that routes to destinations are calculated along these MPRs. 
Fig. 3 12: A part of a converging OLSR network. The fat circles are MPRs.15 OLSR also uses hello messages in order to establish link functionality between neighbors. The hello message contains the neighbors of the source of the hello message. A node concludes that its neighbor is accessed over a bi-directional link when it receives a hello message where the node finds itself listed. The sequence number of the TC is used for comparing incoming TCs and discarding old ones. The list of MPRs in the TC does not have to be complete in a single message, but as messages are sent during a specified period, all the MPRs have to appear in some of the messages in order to build a routing table. If a change in the MPR set of a node occurs then a TC is sent before the next TC was originally scheduled. Recorded TCs are discarded after a specified time period. The information extracted from TCs (MPR, Destination, Cost between the two) are recorded in a database and then calculated in the same way as in the basic Link State algorithm. Download 298.62 Kb. Share with your friends:
|