MANETs-Dynamic Source Routing Protocol

Dynamic Source Routing : 

Re-Active Routing Protocols In Detailed-I Dynamic Source Routing

Introduction : 

Introduction DSR Protocol allows nodes to dynamically determines a source route across multiple network hops to any destination in the ad hoc network. Using DSR, the network is completely self-organizing and self-configuring, doesn’t require existing network infrastructure or administration. Dynamically determines a route based on Cached Information. Result of Route Discovery.

Overview : 

Overview DSR is composed of two Mechanism. Route Discovery Route Maintenance Route Discovery & Route Maintenance each operate entirely On-Demand. Advantages : Supports unidirectional links , Asymmetric routes ,Load balancing and Internetworking between different type of Wireless Networks. No Periodic Activity, thus less overhead in Packet Delivery. No Link Sensing & No Neighbor Detection. All state maintained by DSR is “Soft State”.

Why is safe state ? : 

Why is safe state ? Loss of any state will not interfere with actual operation of protocol. States are Discovered and Re-Discovered when failure occurs, when ever needed. If a node fails and/or reboots , it can easily re-join the network and can resume the activities it doing(like forwarding routes). Makes protocol to be robust to problems like Dropping or Delaying routing packets. Node failures.

Assumptions Taken : 

Assumptions Taken All nodes are willing to communicate with each other and willing to forward packets for other nodes. Nodes can detect errors and discards packets. Nodes are moving with a constant moderate speed. Diameter of the network is the minimum number of hops necessary for a packet to reach from any node.

Route Discovery : 

Route Discovery Invoked only when routing path from Source to Destination is not found in Route Cache. Terminate when route found (or) No route found after checking all route permutation. Node may learn and Cache Multiple Routes to any Destination, to avoid Overhead in Route Determination. Uses two type of messages. Route Request Packet(RREQ) Route Reply Packet(RREP)

Basic Operation-Route Discovery : 

Basic Operation-Route Discovery Sender : Broadcasts a Route Request Packet(RREQ). RREQ packet contains a unique Request ID. RREQ contains a Record listing of Intermediate nodes. Receiver : If this host is Target (or) having route to Target, then send Route Reply Packet(RREP). If this host is source, then Discard the Packet. Otherwise, if the host address is already listed in Route Record in RREQ then discard else Append its address to Route Record in RREQ and broadcast.

Basic Operation-Route Discovery : 

A B C E D G H F RREQ Packet RREP Packet Basic Operation-Route Discovery

Slide 9: 

A B C D E ID=2 ID=2 ID=2 ID=2 A A,B A,B,C A,B,C,D Broadcasting Route Request Packets(Propagating) Source Destination Broadcasting Route Request Packets(Non-Propagating)-Expanding Ring S D Hop Count=1 Hop Count=2

Slide 10: 

A B C D E Returning Route Reply to Source Source Destination C: E,D,C; A: E,F,G,A G F RREP(A,B,C,D,E) Case I : If a route is Found in route Cache , then send the RREP in that path. Case II : If no route is Found in route Cache ,then It will invoke Route Discovery to find a route to A. Drawback: Infinite Recursion of series of Route Discovery. To Avoid Infinite Recursion It must Piggyback RREP with RREQ packet for Source Route to A. Otherwise it can simply reverse the sequence of Hops in Route Record. RREP(A,B,C,D,E) RREP(A,B,C,D,E) RREP(A,B,C,D,E) RREP(A,B,C,D,E) RREP(A,B,C,D,E) RREP(A,B,C,D,E) P RREP(A,B,C,D,E) PIGGYBACKED RREP(A,B,C,D,E) PIGGYBACKED RREP(A,B,C,D,E) PIGGYBACKED

Route Maintenance : 

Route Maintenance Each node transmitting the packet is responsible for confirm the Delivery of packet to next node along source route. Confirmation of packet in many cases provided by DSR either as Link-Level ACK Frame or “Passive ACK”. Otherwise A Specific DSR software is requested to send Acknowledgement by the next-hop. Uses two type of messages. Route Error Packet(RERR) Acknowledgement(Either Link-Level/Passive/Explicit)

Basic Operation-Route Maintenance : 

Basic Operation-Route Maintenance Intermediate Node: After Maximum number of Packet Re-transmissions and if no Receipt is confirmed, node sends a RERR(Route Error Message) to original sender identifying the broken link and discards the packet. Otherwise receives an Acknowledgement(Either Link-Level/Passive/Explicit). Source Node : After receiving RERR packet source removes the Routes in Route Cache which uses broken link. To Retransmit the Discarded packet ,it checks for new routes to the same destination in cache or Invokes a Route Discovery process.

Slide 13: 

A B C E D G H F G Route Cache (A)G: A, B, D, G G: A,C,E,D,G G: A, C, E, H, GF: B, C, F Basic Operation-Route Maintenance

Additional Features : 

Additional Features Additional Route Discovery Features: Caching Over-heard Routing Information. Replying to Route Request using Cached Routes. Route Request Hop Limits. Additional Route Maintenance Features: Packet Salvaging. Queued Packet Destination Over Broken-Link. Automatic Route Shortening. Increased Spreading of Route Error Messages.

Caching Over-heard Routing Information : 

Caching Over-heard Routing Information A B C D E Source DATA(A,B,C,D,E) Destination DATA(A,B,C,D,E) DATA(A,B,C,D,E) DATA(A,B,C,D,E) DATA(A,B,C,D,E) Unidirectional A B C D E Source DATA(A,B,C,D,E) Destination DATA(A,B,C,D,E) DATA(A,B,C,D,E) DATA(A,B,C,D,E) DATA(A,B,C,D,E) A B C D E Source DATA(A,B,C,D,E) Destination DATA(A,B,C,D,E) DATA(A,B,C,D,E) DATA(A,B,C,D,E) DATA(A,B,C,D,E) Unidirectional(Not Persistent) Bi-directional Route Cache: (D):C,D; (E):C,D,E; X Route Cache: (C):X,C; (A):C,B,A; (B):C,B; (D):C,D; (E):C,D,E; Route Cache: (A):C,B,A; (B):C,B; (D):C,D; (E):C,D,E;

Route Replies using Route Cache : 

Route Replies using Route Cache A B D E C F Route Cache: (E):F-C-D-E; RREQ:(A-B-C) A-B-C-F-C-D-E A-B-C-D-E No “F” in RREP from F Continues Broadcasting.

Packet Salvaging & Queued Packets Destining : 

Packet Salvaging & Queued Packets Destining A B D E C F DATA(A-B-C-D-E) DATA(A-B-C-F-E) DATA(A-B-C-D-E) DATA(A-B-C-D-E) DATA(A-B-C-F-E) Route Cache: (D):C,D; (E):C,D,E; (E):C,F,E; DATA(A-B-C-F-E) RERR(C-D) Packet Salvaging is expensive mechanism, so it is bound to number of Time the packet can be salvaged , independent of hop count(TTL). Remove Packets in N/W interface Q & Maintenance Buffer that uses Broken Link(C-D)

Automatic Route Shortening : 

Automatic Route Shortening A B C D E Source DATA(A,B,C,D,E) Destination DATA(A,B,C,D,E) DATA(A,B,C,D,E) DATA(A,B,D,E) DATA(A,B,D,E) Route Cache: (B):D,B; (B):D,C,D; (C):D,C; (A):D,B,A; (E):D,E; Route Cache: (A):B,A; (D):B,D; (D):B,C,D; (E):B,C,D,E; Gratuitous Reply(A-B-D-E)

Increased Spreading of Route Error Messages : 

Increased Spreading of Route Error Messages When a source Receives an Route Error for a data packet. the source node propagates copy of Error message its neighbors by Piggybacking in its next Route Request. Advantage : Avoids to generate Stale information in Caches of surrounding nodes containing same invalid link for which the source node received the Error.

Optional Flow State Extension : 

Optional Flow State Extension

Flow State : 

Flow State Provides "implicit source routing" by preserving DSR basic functioning but removing "Explicit source route". Allows the routing most packets without an explicit source route header , instead of this header uses a flow state for that route in n/w. State at each hop in flow is "safe state“. Flow state is dynamically initialized by the first packet using a source route and then able to route subsequent packets along the same flow. Advantages: Reduces the overhead in protocol. Same flow with out the use of source route header.

Flow Establishment : 

Flow Establishment Flow is a route from source to destination represented by hop-by-hop forwarding state within the nodes along the route. Flow is uniquely identified by a source address and destination address and FlowID(16-bit), Greater than old FlowID s. Any no. of flows may exists , but one flow is considered as default flow. If low bit of FlowID is odd then New flow is set as Default flow, otherwise not. records the FlowID along with hop count, for the future use for that route.

Flow Establishment : 

Flow Establishment In a flow every node establishes a state along that route, which is soft state. If a node possesses "forgotten state, then it reduces the performance. Hence define a flow's state to be "established end-to-end". But detection such a flow state is difficult. Source wishes to send packets along flow, if the flow state has been established end-to-end.

Receiving and Forwarding : 

Receiving and Forwarding If FlowID=0 then handle the packets through source route. if (FlowID !=0 && flow in Table) then increase hop count. If (FlowID !=0 && flow not in Table) then send Route Error(UNKNOWN FLOW). If(no Flow State Header) try to send packet in default flow with matching entry. otherwise sent "DEFAULT FLOW UNKNOWN“. Mark the respective Error flows with "No End-to-End Flow State."

Route Shortening : 

Route Shortening Since no source route, shortening must be carried out by flow state extension. Otherwise we can use promiscuous mode ,to know (Source IP Address, Destination IP Address, FlowID). To check with the corresponding Destination IP in flow table with less hop count. Maintains a Automatic Route shortening Table, to check entries an sends Gratuitous Route Reply to the source.

Acknowledgement Destination : 

Acknowledgement Destination To know previous hop can optionally store in the ACK REQ. SHOULD NOT be used when a Source Route option is present. MAY be used when flow state routing is used without a Source Route option, and SHOULD be used before Route Maintenance determines that the next-hop destination is unreachable

Rate Limiting : 

Rate Limiting Flow IDs are assigned with a counter, with "Current Flow ID" is kept. Algorithm is needed for avoiding duplicate, unexpired flow IDs is to rate limit new FlowID s to can average of n segment/sec, when n=2^15/Max. Timeout.

Conceptual Data Structures : 

Route Cache Send Buffer Route Request Table Gratuitous Route Reply Table Network Interface Queue & Maintenance Buffer Blacklist Conceptual Data Structures --Must be implemented in DSR Protocol

Route Cache : 

Route Cache Each node should maintain a Route Cache ,which contains Routing Information. Node adds Routing Information to its Route Cache , as it learns of new links between nodes , from Route Request, Route Reply or DSR Source Route. Node removes Information about a Route when it is reported as broken link by Route Error Packet. Node should check route to destination exists or not in route cache, for the packet in send buffer. if so send, otherwise remove packet from send buffer.

Searching for Route in Route Cache : 

Searching for Route in Route Cache Can use any strategy and Algorithm using any metrics that are liable. In case if multiple routes, prefers routes with no external flag/link(which allows route from external networks). External Network : DSR Network can be used in internetworking with other Network or Another DSR Network , and Assume it as An External Network ,even if it is DSR Network.

Management of Space & Organization of Route Cache : 

Management of Space & Organization of Route Cache MAY be Fixed Size or Variable. Implement an appropriate policy for managing the entries in its Route Cache, Like "least recently used" (LRU) cache replacement policy Some times policy SHOULD allow routes to be categorized based upon "preference“ Organization Cache: Path Cache: Learn from RREP by source and organized(routes are loop free).View of Source to Destination. Search for a node is simple. And gives complete sequence of links. Link Cache: Individual link organization. i.e. a node's view on Network topology(Individual links learnt). Search for a route is more Complex to find current best. Learns from RREP and Over Head packet so new routes can be establish to the best.

Entries in Route Cache : 

Entries in Route Cache Each entry in route cache should have a timeout associate with it, to delete if not used for some time. Time out setting can be like Link-MaxLife. Link-MaxLife: It is an adaptive link cache in which each link in cache has timeout that is determined dynamically by caching node according to its past behavior over the link.

Send Buffer : 

Send Buffer queue of packets that cannot be sent by that node, since source route is not yet found. and has a “Send Buffer Timeout” ,after which packet is discarded in FIFO(if required). Route Discovery mechanism allowed invoke for the destination address of the packets residing in send buffer only.

Route Request Table : 

Route Request Table Contains info about RREQ's that performed by this node, indexed by IP address. To calculate remaining time a node must implement a back-off algorithm in determining this time out. Uses LRU policy to manage these entries

How Safe State Achieved : 

How Safe State Achieved In addition, A FIFO cache of size , RequestTableIDs entries containing the ID value and the Target Address from the most recent RREQ from the initiator node is Added to Cache. After rebooting, Route Discovery initiates with the use of ID values which makes RREQ is appear to be duplicate to other nodes in n/w to avoid delay in re-Discovery Mechanism. otherwise base its initial ID value on a random number. The no. of ID value to retain such RREQ Table entry , RequestTableIDs must be limited.

Gratuitous Route Reply Table : 

Gratuitous Route Reply Table Used to limit the rate at which it originates gratuitous Route Replies(GRREP) for the same original sender for the same node which it overheard a packet to trigger the gratuitous Route. If Reply already exists then node should not send GRREP, Otherwise make an entry and discard that overheard packet.

Network Interface Queue & Maintenance buffer : 

Network Interface Queue & Maintenance buffer Outgoing packets are queued at OS/Link Layer , before transmission.(N/W interface Q) N/W interface should also provide a re-transmission mechanism for packets. DSR , as a part of Route Maintenance , requires limited buffering of next-hop destination has not yet been determined.(Maintenance Buffer) For each packet in Buffer, node counts the no. of retransmissions and the time of last retransmission. Maintenance Buffer is limited, when its full new packets are discarded. After MaxMaintRexmt attempts the packets with next hop destination are discarded and Route Error is sent for this packets original sender. & Salvage these packets (May be another route exists in the route cache).

Blacklist : 

Blacklist Blacklist is a table that contains the info about links which are not bidirectional, indexed by neighbor node address. E.g.: if a node forwarding a RREP discovers that next hop is unreachable, it places that next hop in its blacklist. If node discovers that it can communicate bidirectional with a node in blacklist ,then that entry is deleted from blacklist. States assigned to the links are "questionable" or "probable". If the unreachability is positively determined, then state is “Probable” otherwise “Questionable”.

Additional Conceptual Data Structures : 

Flow Table Automatic Route Shortening Table Default Flow ID Table Additional Conceptual Data Structures --Must be implemented in DSR Protocol for Flow State Extension

Flow Table : 

Records flow from which packets are recently have been sent or forwarded by this node. Indexed by (Source IP Address, Destination IP Address, FlowID). Contains following Entries in Table. MAC address of next-hop; MAC address of previous-hop; N/W interface to be used(Out going), N/W interface that is used(Received), Timeout-After which entry to be deleted, Expected Hop Count, Default Flow Flag-Can be used as Default Flow or not, Complete Source Route(to perform in Automatic Route Shortening.); Last Used Time. Flow Table

Automatic Route Shortening : 

Automatic Route Shortening Contains info about received packets for which Automatic Route Shortening may be possible. Indexed by (Source IP Address, Destination IP Address, FlowID). Each entry in Table contains a list of (packet identifier, Hop Count) pairs for that flow. Packet identifier in the list may be any unique identifier for the received packet. The Hop Count in the list in the entry is copied from the Hop Count field in the DSR Flow State header of the received packet for which this table entry was created. Note: Space is dynamically managed by any local algorithm at the node

Default Flow ID Table : 

Default Flow ID Table Contains info about Default Flows. Indexed by (Source IP Address, Destination IP Address).

DSR Options Header Format : 

DSR Options Header Format

DSR Options Header : 

DSR Options Header DSR uses a special header , carrying control information. Can be included in any Existing IP Packet. DSR Options Header is inserted following the packet’s IP, before any following header such as Transport Layer header.

Fixed Portion of DSR Options Header : 

Fixed Portion of DSR Options Header Options Payload Length 16-bits Next Header 8-bits Reserved 7-bits F 32 bits DSR Options MAY be padded for alignment , but due to limited wireless bandwidth , Receiving Nodes must not expect options with DSR Option Header is aligned.

DSR Options : 

DSR Options Each DSR Option is assigned a unique Option Type Code. The most 3 significant bits allow node to implement processing. Most Significant Bit: Represents whether or not respond to Option Type with a Route Error Message.(Except for RREQ Packet). Two Following Bits: Indicates how packet is treated, if it Doesn’t support. 00 – Ignore Option. 01 – Remove Option. 10 – Mark Option. 11 – Drop Option.

Various Types of DSR Options : 

Various Types of DSR Options Route Request Option Route Reply Option Route Error Option Acknowledgement Request Option Acknowledgement Option DSR Source Route Option Pad1 Option PadN Option

Route Request Option-1/2 : 

Route Request Option-1/2 Source Address Broad Cast Address(255.255.255.255) Hop Count (1-255)

Route Request Option-2/2 : 

Option Type Target Address Address[1] Address[2] …. Address[n] Identification Option Data Length Route Request Option-2/2 1-Nodes not understanding this option will IGNORE this Option. 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. (4*n+6) A Unique Value generated by Source of RREQ Packet. To Determine whether it has recently seen a copy of this RREQ. If this value already existing in Route Request Table then this packet is Discarded. Otherwise this field must be copied to Route Request Table. Each node propagating the Route Request adds its own address to the Address[1-n] list. Address[1-n] should not contains Initiator Address. i.e. Address[1] is the address hop next to Source Generated RREQ Packet.

Route Reply Option : 

L Route Reply Option Option Type Address[1] Address[2] …. Address[n] Reserved Option Data Length 2-Nodes not understanding this option will IGNORE this Option. 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. (4*n+1) Last Hop External(L): Set to Indicate that the last hop(Address[n-1] – Address[n]) given by RREP Packet , is an arbitrary path in network External to This DSR Network. Nodes that caching this hop in their Route Cache MUST flag this hop with the External Flag. Selection of Routes from Cache should prefer Routes with out External Flag set.

Route Error Option : 

Route Error Option Option Type Error Source Address Error Destination Address Type Specific Information Salvage Option Data Length Error Type Reserved 3-Nodes not understanding this option will IGNORE this Option. 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. Minimum Value : 10 Salvage: Total Salvage Count is ,for each route error option , one plus the value in salvage field of that Route Error Option. Type of Error Encountered. 1=NODE_UNREACHABLE 2=FLOW_STATE_NOT_SUPPORTED 3=OPTION_NOT_SUPPORTED

Acknowledgement Request Option : 

Acknowledgement Request Option Option Type Identification Option Data Length 160-Nodes not understanding this option will IGNORE this Option. 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. The identification value is a unique value and is copied into the Identification Field of the ACKNOWLEDGEMENT Option when returned by node receiving the packet over this hop. Acknowledgement Request Option MUST NOT appear more than once with in a DSR Options Header.

Acknowledgement Option : 

Acknowledgement Option Option Type Identification Option Data Length 32-Nodes not understanding this option will REMOVE this Option. 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. ACK Source Address ACK Destination Address Copied from the Identification field of Acknowledgement Request Option of the packet being acknowledged. Acknowledgement Option MAY appear more than once with in a DSR Options Header.

DSR Source Route Option : 

DSR Source Route Option Salvage Reserved Segments Left Option Data Length F L Option Type Address[1] Address[2] …. Address[n] 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. (4*n+2) 96-Nodes not understanding this option will DROP this Option. Number of Route Segments Still left. i.e. Number of Explicitly listed nodes Still to be visited before reaching the final Destination. First Hop External(L): Set to Indicate that the First hop indicated by DSR Source Route Option, is an arbitrary path in network External to This DSR Network. Nodes that caching this hop in their Route Cache MUST flag this hop with the External Flag. Selection of Routes from Cache should prefer Routes with out External Flag set. Such opts MUST NOT be returned in RREP Packet generated by Source.

Pad1 Option : 

Pad1 Option Option Type 224-Nodes not understanding this option will DROP this Option and Return a Route Error. A Pad1 Option MAY be included in the Options field of DSR Options Header in order to Align Subsequent Options and is not Necessary. A Node MUST NOT expect DSR Options To be aligned in Options Header. Needed to align Only if any Headers follow the DSR Options Header ,since to make total length to be Multiple of 4 Octets.

PadN Option : 

PadN Option Option Type Option Data Option Data Length 0-Nodes not understanding this option will IGNORE this Option. 8-bit Unsigned Integer. The Size of Option Data Field. A number of 0-Valued Octets equal to Option Data Length. PadN is used instead of Inserting Multiple Pad1 Options for padding , specifying the length(In Octets) of padding to be inserted in DSR Option Header in Option Data Length.

Additonal Header Formats & Options : 

For Flow State Extension Additonal Header Formats & Options

New Headers, Options & Extensions : 

The Optional DSR Flow State Extension Requires a new header type , the DSR Flow State Header. It also adds the following Options for DSR Options Header. Time-Out Option. Destination and Flow ID Option. Two new Error Types were introduced. UNKNOWN_FLOW. DEFAULT_FLOW_UNKNOWN. New Extension was introduced to Acknowledgement Request Option. Previous Hop Address. New Headers, Options & Extensions

DSR Flow State Header : 

DSR Flow State Header Identifies the Type of Header immediately following the DSR Flow State Header. Flow State Header : Flag bit, must be set to 1. Set in DSR Flow State Header and cleared in DSR Options Header. Number of hops through which packet has been forwarded. Flow ID of this Flow.

Time-Out Option – New Option : 

Time-Out Option – New Option Option Type Time Out Option Data Length 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. In the presence of Extension >2. Number of Second for which this flow remains Valid. Time-Out Option MUST NOT appear more than once with in a DSR Options Header. 128-Nodes not understanding this option will IGNORE this Option and Return a Route Error.

Destination Flow ID Option – New Option : 

Destination Flow ID Option – New Option Option Type New Flow Identifier Option Data Length 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. In the presence of Extension >6. 129-Nodes not understanding this option will IGNORE this Option and Return a Route Error. New IP Destination Address Indicate the next Identifier to store in the Flow ID field of the DSR Options Header. Indicate the next address to store in the Destination Address field of the DSR Options Header.

Unknown Flow – Error Type : 

Unknown Flow – Error Type Error Type Value : 129 (UNKNOWN_FLOW) , is used in Route Error Option.

Default Flow Unknown– Error Type : 

Default Flow Unknown– Error Type Error Type Value : 130 (DEFAULT_FLOW_UNKNOWN) , is used in Route Error Option.

Previous Hop Address - Extension : 

ACK Source Address Previous Hop Address - Extension Option Type Packet Identifier Option Data Length 8-bit Unsigned Integer. Length of Options excluding Option Type and Option Data Length ,in Octets. Since it is the extension, it is >6. 160-Nodes not understanding this option will IGNORE this Option and Return a Route Error. The Address of node Requesting the DSR Acknowledgement. This field is set to a unique number and is copied into the Identification field of the DSR Acknowledgement Option when returned by the node receiving the packet over this hop.

Detailed Operation : 

General Packet Processing Route Discovery Processing Route Maintenance Processing Multiple Network Interface Support IP Fragmentation & Reassembly Flow State Processing Detailed Operation

General Packet Processing : 

General Packet Processing Originating a Packet Adding a DSR Options Header to a Packet Adding a DSR Source Route Option to a Packet Processing a Received Packet Processing a Received DSR Source Route Option Handling an Unknown DSR Option.

Originating Packet : 

Originating Packet A Node must follow these operation before Originating any Packet. Search the Route Cache for the route to IP Destination Address. If no route Found , then invoke Route Discovery to Destination. Can be done in 2 ways. Append RREQ to Current packet and broadcast it. Save current packet in “Send Buffer” and Broad cast a new packet with RREQ. If packet doesn’t contain a RREQ then Route must have found in Cache, then . IP Header DSR Header DSR Source Route Option DATA DATA

Adding DSR Option Header to Packet : 

Adding DSR Option Header to Packet IP Packet Must Contain only one DSR Header. Insert a DSR Options header after the IP header but before any other header that may be present. Set the Next Header field of the DSR Options header to the Protocol number field of the packet's IP header. Set the Protocol field of the packet's IP header to the protocol number assigned for DSR (48). MAC Header IP Header DSR Header DATA DATA

Adding DSR Source Route Option to Packet : 

Adding DSR Source Route Option to Packet The addresses within the source route for the packet are copied into sequential Address[i] fields in the DSR Source Route option, for i = 1, 2, ..., n. The Salvage field in the DSR Source Route option is initialized to 0. Salvage Reserved Segments Left Option Data Length F L Option Type Address[1] Address[2] …. Address[n]

Processing Packet Received-Immediate : 

Processing Packet Received-Immediate Process the packet, based on Option Type Received. If(Route Request Option) then, update route cache & process further. If(Route Reply Option) then, update route cache & process further. If (Acknowledgement Option) then, add the single link from the node identified to Route Cache & process further. If (Pad1 or PadN) then, IGNORE the packet.

Processing Received DSR Source Route Option : 

Processing Received DSR Source Route Option If there an opportunity for automatic route shortening, then node searches its Gratuitous Route Reply Table, an entry is found in the node's Gratuitous Route Reply Table, the node SHOULD NOT perform automatic route shortening. Otherwise, the node creates an entry for this overheard packet in its Gratuitous Route Reply Table.(sets timeout=GratReplyHoldoff) Discard the overheard packet. If the packet is not discarded as part of Automatic Route Shortening , then If segments left=0,remove DSR source route option from header. If >n , discard the packet , else decrement by 1. If address[i] is multicast, discard the packet. If MTU<size of packet either discard or fragment.

Route Discovery Processing : 

Route Discovery Processing Originating a Route Request Processing a Received Route Request Option Generating a Route Reply Using the Route Cache Originating a Route Reply Preventing Route Reply Storms

Originating Route Request : 

Originating Route Request Packets containing a Route Request option SHOULD NOT include an Acknowledgement Request option, SHOULD NOT expect link-layer acknowledgement or passive acknowledgement, and SHOULD NOT be retransmitted.

Processing Route Request Option-1 : 

Processing Route Request Option-1 If Target ,then RETURN ROUTE REPLY. With sequence of hop addresses as (initiator, Address[1], Address[2], ..., Address[n], target). Discard the packet if node already appears in the Route Records List. If the last hop is listed in Blacklist, then If State is “Probable” , then Discard. Else check whether the last hop is Bidirectional or not.(If not Discard the Packet.) If a Matching Record found in Route Request Option for (Source Address, Target Address, Identification), then DISCARD.

Processing Route Request Option-2 : 

Processing Route Request Option-2 Add an entry in Route Request Table. Conceptually create a copy of this entire packet and perform the following steps on the copy of the packet. Append this node's own IP address to the list of Address[i]. If a route is found in its Route Cache, then this node SHOULD return a "cached Route Reply“. Otherwise Broadcast this Packet.

Route Reply Using the Route Cache : 

Route Reply Using the Route Cache If the node is target of RREQ, then L=0. Set identifier field with ID of RREQ. Sequence of hop addresses of RREQ must be copied into address array of RREP. Destination field of IP header must be set to address of initiator of route discovery. Delay the route reply for a JITTER period.(Bet. 0 to broadcast Jitter=10ms). If the MAC protocol is not capable of transmitting unicast packets over unidirectional links then route is reverse of that in RREQ. This restricts it only for bidirectional. If RREP performs route discovery, it must be piggybacked in RREQ.

Preventing Route Reply Storms : 

Preventing Route Reply Storms A B F E D C G RREQ RREQ RREQ RREQ RREQ CACHE C,B,G CACHE F,B,E CACHE G CACHE B,G CACHE B,G RREP RREP RREP RREP RREP

Route Maintenance Processing : 

Route Maintenance Processing Using Link-Layer Acknowledgements Using Passive Acknowledgements Using Network-Layer Acknowledgements Originating a Route Error Processing a Received Route Error Option Salvaging a Packet

Route Maintenance : 

Route Maintenance when forwarding a packet, a node MUST attempt to confirm the reachability of the next-hop node. If no confirmation is received after the retransmission of MaxMaintRexmt attempts, then the link for this next-hop node of the source route is "broken". can be implemented using link layer acknowledgement passive acknowledgement network-layer acknowledgement. The particular strategy for retransmission timing depends on the type of acknowledgement mechanism used.

Using Link-Layer Acknowledgement : 

Using Link-Layer Acknowledgement MAC protocol in use provides feedback as to the successful delivery of a data packet(IMPLICIT ACK). Preferred over other two. The retransmission timing controlled by link layer. When a node receives a link-layer acknowledgement for any packet in its Maintenance Buffer, that node SHOULD remove from its Maintenance Buffer that packet, as well as any other packets in its Maintenance Buffer with the same next-hop destination.

Using Passive Acknowledgement : 

Using Passive Acknowledgement Preferred over network layer acknowledgement. Requires nodes in "promiscuous“ receive mode & links to be bidirectional. B confirms receipt at C by overhearing C transmit the packet when forwarding it on to D. The following two strategies can be used:1st strategy Initially, the node sends the original transmission of that packet without requesting a network-layer acknowledgement for it. If no passive acknowledgement is received within PassiveAckTimeout after this transmission, the node retransmits the packet, again without requesting a network-layer acknowledgement for it. TryPassiveAcks retransmissions of the packet done if no passive ack. Received. If no acknowledgement has been received, network-layer acknowledgements are requested for all remaining attempts for that packet.

Using Passive Acknowledgements : 

Using Passive Acknowledgements A B PACKET WAIT FOR PASSIVE ACK UNTILL PassiveAck Tmeout IF PASSIVE ACK NOT RECEIVED PACKET 2 PERFORM FOR TryPassiveAckretransmissions IF NO ACK RECEIVED, GO FOR NETWORK LAYER ACK

Using Passive Acknowledgement : 

Using Passive Acknowledgement 2nd strategy: Each node maintains a table of next-hop destination nodes, noting whether or not passive acknowledgements can typically be expected from transmission to that node & its expected latency. The node checks its table of next-hop destination nodes to determine whether to use a passive acknowledgement or a network-layer acknowledgement for that transmission to that node. When a node heres passive acknowledgement, it must remove the packet from the Maintenance buffer.

Using Passive Acknowledgements : 

Using Passive Acknowledgements A C B TABLE OF A NODE PASSIVE ACK B ----------------YES C----------------NO IF YES, WAITS FOR PASSIVE ACK IF NO, GO FOR NETWORK LAYER ACK

Using Network Layer Acknowledgement : 

Using Network Layer Acknowledgement A node requests acknowledgement for receipt of the packet by the next hop. When a node receives a packet containing an Acknowledgement Request option, that node performs the following tests on the packet: The indicated next-hop node address is the next Address[i] field in the DSR Source Route option in the DSR Options header in the packet, or the IP Destination Address in the packet if the packet does not contain a DSR Source Route option or the Segments Left there is zero. If the packet contains an Acknowledgement option, then this node MUST NOT process the Acknowledgement Request option. If above two are Success the send “Acknowledgement.”

Sending Acknowledgement : 

Sending Acknowledgement Create a packet. Set the IP Protocol field to the protocol number assigned for DSR (48). Set IP source address field & IP destination address field. Add a DSR Options header to the packet. Set the Next Header field in the DSR Options header to the value 59, "No Next Header“. Add an Acknowledgement option to the DSR Options header & option type to 32. Copy the Identification field from the received Acknowledgement Request option into the Identification field in the Acknowledgement option. Set the ACK source address field & destination field. Remove the packet from maintenance buffer of the node.

Originating Route Error : 

Originating Route Error When a node is unable to verify reachability of a next-hop, it SHOULD send a Route Error to the IP Source Address of the packet must follow the below. Create an IP packet set the IP Protocol field to the protocol number assigned for DSR (48). Set the Source Address field in this packet's IP header to the address of this node. If Salvage=0 in original packet, then destination=original source, else destination=address[1]. Insert a DSR Options header into the new packet & fill the error type: 1 = NODE_UNREACHABLE, 2 = FLOW_STATE_NOT_SUPPORTED 3 = OPTION_NOT_SUPPORTED Salvage from original packet & error source & destination address.

Slide 88: 

A C B PACKET WAIT FOR ACK IF ACK NOT RECEIVED Create a IP packet & fill required fields IF salvage=0,destination=original source Else,address[1]

Processing Route Error : 

Processing Route Error Process the Route Error option according to the following sequence of steps: Remove the routes using the link identified from its Route Cache. If the option following the Route Error is an Acknowledgement or Route Error option sent by this node, copy the DSR options following the current Route Error into a new packet with IP Source Address equal to this node's own IP address and IP Destination Address equal to the Acknowledgement or Error Destination Address. Such packets may perform route discovery to the source due to the errors.

Slide 90: 

A C B D A,B,C,D,E B,C,D,E B,C,D E RERR RERR RERR

Salvaging the Packet : 

Salvaging the Packet When a node detects that route for a packet is broken, and if it has another route to the packet's IP Destination in its Route Cache, then node SHOULD "salvage“ the packet rather than discard it. If the links are unidirectional , then If(Route Reply Option Found), then remove & discard RREP Option. If(no DSR Options/Only Source Route Found) , then Remove DSR Header and Options.(Keeps only IP Header.) Modify the existing DSR Source Route option in the packet, Address[1], here, it is the address of the salvaging node itself. N=number of hop addresses in this source route excluding destination. Segments Left field=n The Last Hop External (L) bit in the DSR Source Route option is copied from the External bit flagging the last hop in the source route for the packet, as indicated in the Route Cache. Salvage=1+salvage

Multiple Network Interface Support : 

Multiple Network Interface Support

Interfacing Support : 

Interfacing Support DSR MAY have multiple network interfaces that support DSR ad hoc network routing. node MAY choose to forward all Route Requests over all network interfaces. Append the node's IP address for the incoming network interface. Append the node's IP address for the outgoing network interface. route specifying a change to a network interface, that is no longer available, it MAY send a Route Error to the source of the packet