draft-ietf-manet-dsr-10.txt

DSR-UU is a DSR implementation that runs in Linux and in the ns-2 network simulator. DSR-UU imple

   Source routes in use MAY be automatically shortened if one or more
   intermediate nodes in the route become no longer necessary.  This
   mechanism of automatically shortening routes in use is somewhat
   similar to the use of passive acknowledgements [18].  In particular,
   if a node is able to overhear a packet carrying a source route (e.g.,
   by operating its network interface in promiscuous receive mode), then
   this node examines the unexpended portion of that source route.  If
   this node is not the intended next-hop destination for the packet
   but is named in the later unexpended portion of the packet's source
   route, then it can infer that the intermediate nodes before itself in
   the source route are no longer needed in the route.  For example, the
   figure below illustrates an example in which node D has overheard a
   data packet being transmitted from B to C, for later forwarding to D
   and to E:

         +-----+     +-----+     +-----+     +-----+     +-----+
         |  A  |---->|  B  |---->|  C  |     |  D  |     |  E  |
         +-----+     +-----+     +-----+     +-----+     +-----+
                        \                       ^
                         \                     /
                          ---------------------

   In this case, this node (node D) SHOULD return a "gratuitous" Route
   Reply to the original sender of the packet (node A).  The Route
   Reply gives the shorter route as the concatenation of the portion of
   the original source route up through the node that transmitted the
   overheard packet (node B), plus the suffix of the original source
   route beginning with the node returning the gratuitous Route Reply
   (node D). In this example, the route returned in the gratuitous Route
   Reply message sent from D to A gives the new route as the sequence of
   hops from A to B to D to E.

   When deciding whether to return a gratuitous Route Reply in this way,
   a node MAY factor in additional information beyond the fact that it
   was able to overhear the packet.  For example, the node MAY decide to
   return the gratuitous Route Reply only when the overheard packet is
   received with a signal strength or signal-to-noise ratio above some
   specific threshold.  In addition, each node maintains a Gratuitous
   Route Reply Table, as described in Section 4.4, to limit the rate at
   which it originates gratuitous Route Replies for the same returned
   route.


3.4.4. Increased Spreading of Route Error Messages

   When a source node receives a Route Error for a data packet that
   it originated, this source node propagates this Route Error to its
   neighbors by piggybacking it on its next Route Request.  In this way,



Johnson, et al             Expires 19 January 2005             [Page 16]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   stale information in the caches of nodes around this source node will
   not generate Route Replies that contain the same invalid link for
   which this source node received the Route Error.

   For example, in the situation shown in the example of Section 3.2,
   node A learns from the Route Error message from C, that the link
   from C to D is currently broken.  It thus removes this link from
   its own Route Cache and initiates a new Route Discovery (if it has
   no other route to E in its Route Cache).  On the Route Request
   packet initiating this Route Discovery, node A piggybacks a copy
   of this Route Error, ensuring that the Route Error spreads well to
   other nodes, and guaranteeing that any Route Reply that it receives
   (including those from other node's Route Caches) in response to this
   Route Request does not contain a route that assumes the existence of
   this broken link.


3.5. Optional DSR Flow State Extension

   This section describes an optional, compatible extension to the DSR
   protocol, known as "flow state", that allows the routing of most
   packets without an explicit source route header in the packet.  The
   DSR flow state extension further reduces the overhead of the protocol
   yet still preserves the fundamental properties of DSR's operation.
   Once a sending node has discovered a source route such as through
   DSR's Route Discovery mechanism, the flow state mechanism allows the
   sending node to establish hop-by-hop forwarding state within the
   network, based on this source route, to enable each node along the
   route to forward the packet to the next hop based on the node's own
   local knowledge of the flow along which this packet is being routed.
   Flow state is dynamically initialized by the first packet using a
   source route and is then able to route subsequent packets along
   the same flow without use of a source route header in the packet.
   The state established at each hop along a flow is "soft state" and
   thus automatically expires when no longer needed and can be quickly
   recreated as necessary.  Extending DSR's basic operation based on an
   explicit source route in the header of each packet routed, the flow
   state extension operates as a form of "implicit source routing" by
   preserving DSR's basic operation but removing the explicit source
   route from packets.


3.5.1. Flow Establishment

   A source node sending packets to some destination node MAY use the
   DSR flow state extension described here to establish a route to
   that destination as a flow.  A "flow" is a route from the source to
   the destination represented by hop-by-hop forwarding state within
   the nodes along the route.  Each flow is uniquely identified by a




Johnson, et al             Expires 19 January 2005             [Page 17]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   combination of the source node address, the destination node address,
   and a flow identifier (flow ID) chosen by the source node.

   Each flow ID is a 16-bit unsigned integer.  Comparison between
   different flow IDs MUST be performed modulo 2**16.  For example,
   using an implementation in the C programming language, a
   flow ID value (a) is greater than another flow ID value (b) if
   ((short)((a) - (b)) > 0), if a C language "short" data type is
   implemented as a 16-bit signed integer.

   A DSR Flow State header in a packet identifies the flow ID to
   be followed in forwarding that packet.  From a given source to
   some destination, any number of different flows MAY exist and
   be in use, for example following different sequences of hops to
   reach the destination.  One of these flows may be considered to be
   the "default" flow from that source to that destination.  A node
   receiving a packet with neither a DSR Options header specifying the
   route to be taken (with a Source Route option in the DSR Options
   header) nor a DSR Flow State header specifying the flow ID to be
   followed, is forwarded along the default flow for the source and
   destination addresses specified in the packet's IP header.

   In establishing a new flow, the source node generates a nonzero
   16-bit flow ID greater than any unexpired flow IDs for this
   (source, destination) pair.  If the source wishes for this flow to
   become the default flow, the low bit of the flow ID MUST be set (the
   flow ID is an odd number); otherwise, the low bit MUST NOT be set
   (the flow ID is an even number).

   The source node establishing the new flow then transmits a packet
   containing a DSR Options header with a Source Route option; to
   establish the flow, the source node also MUST include in the packet
   a DSR Flow State header, with the Flow ID field set to the chosen
   flow ID for the new flow, and MUST include a Timeout option in the
   DSR Options header, giving the lifetime after which state information
   about this flow is to expire.  This packet will generally be a normal
   data packet being sent from this sender to the receiver (for example,
   the first packet sent after discovering the new route) but is also
   treated as a "flow establishment" packet.

   The source node records this flow in its Flow Table for future use,
   setting the TTL in this Flow Table entry to be the value used in the
   TTL field in the packet's IP header and setting the Lifetime in this
   entry to be the lifetime specified in the Timeout option in the DSR
   Options header.  The TTL field is used for Default Flow Forwarding,
   as described in Sections 3.5.3 and 3.5.4.

   Any further packets sent with this flow ID before the timeout that
   also contain a DSR Options header with a Source Route option MUST use
   this same source route in the Source Route option.



Johnson, et al             Expires 19 January 2005             [Page 18]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


3.5.2. Receiving and Forwarding Establishment Packets

   Packets intended to establish a flow, as described in Section 3.5.1,
   contain a DSR Options header with a Source Route option, and are
   forwarded along the indicated route.  A node implementing the DSR
   flow state extension, when receiving and forwarding such a DSR
   packet, also keeps some state in its own Flow Table to enable it
   to forward future packets that are sent along this flow with only
   the flow ID specified.  Specifically, if the packet also contains
   a DSR Flow State header, this packet SHOULD cause an entry to be
   established for this flow in the Flow Table of each node along the
   packet's route.

   The Hop Count field of the DSR Flow State header is also stored in
   the Flow Table, as is Lifetime option specified in the DSR Options
   header.

   If the Flow ID is odd and there is no flow in the Flow Table with
   Flow ID greater than the received Flow ID, set the default Flow ID
   for this (IP Source Address, IP Destination Address) pair to the
   received Flow ID, and the TTL of the packet is recorded.

   The Flow ID option is removed before final delivery of the packet.


3.5.3. Sending Packets Along Established Flows

   When a flow is established as described in Section 3.5.1, a packet
   is sent which establishes state in each node along the route.
   This state is soft; that is, the protocol contains mechanisms for
   recovering from the loss of this state.  However, the use of these
   mechanisms may result in reduced performance for packets sent
   along flows with forgotten state.  As a result, it is desirable
   to differentiate behavior based on whether or not the sender is
   reasonably certain that the flow state exists on each node along
   the route.  We define a flow's state to be "established end-to-end"
   if the Flow Tables of all nodes on the route contains forwarding
   information for that flow.  While it is impossible to detect whether
   or not a flow's state has been established end-to-end without sending
   packets, implementations may make reasonable assumptions about the
   retention of flow state and the probability that an establishment
   packet has been seen by all nodes on the route.

   A source wishing to send a packet along an established flow
   determines if the flow state has been established end-to-end.  If
   it has not, a DSR Options header with Source Route option with this
   flow's route is added to the packet.  The source SHOULD set the
   Flow ID field of the DSR Flow State header either to the flow ID
   previously associated with this flow's route or to zero.  If it sets
   the Flow ID field to any other value, it MUST follow the processing



Johnson, et al             Expires 19 January 2005             [Page 19]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   steps in Section 3.5.1 for establishing a new flow ID. If it sets the
   Flow ID field to a nonzero value, it MUST include a Timeout option
   with a value not greater than the timeout remaining in the node's
   Flow Table, and if its TTL is not equal to that specified in the Flow
   Table, the flow MUST NOT be used as a default flow in the future.

   Once flow state has been established end-to-end for non-default
   flows, a source adds a DSR Flow State header to each packet it wishes
   to send along that flow, setting the Flow ID field to the flow ID of
   that flow.  A Source Route option SHOULD NOT be added to the packet,
   though if one is, then the steps for processing flows that have not
   been established end to end MUST be followed.

   Once flow state has been established end-to-end for default flows,
   sources sending packets with IP TTL equal to the TTL value in the
   local Flow Table entry for this flow then transmit the packet to the
   next hop.  In this case, a DSR Flow State header SHOULD NOT be added
   to the packet and a DSR Options header likewise SHOULD NOT be added
   to the packet; though if one is, the steps for sending packets along
   non-default flows MUST be followed.  If the IP TTL is not equal to
   the TTL value in the local Flow Table, then the steps for processing
   a non-default flow MUST be followed.


3.5.4. Receiving and Forwarding Packets Sent Along Established Flows

   The handling of packets containing a DSR Options header with
   both a nonzero Flow ID and a Source Route option is described in
   Section 3.5.2.  The Flow ID is ignored when it is equal to zero.
   This section only describes handling of packets without a Source
   Route option.

   If a node receives a packet with a Flow ID in the DSR Options
   header that indicates an unexpired flow in the node's Flow Table, it
   increments the Hop Count in the DSR Options header and forwards the
   packet to the next hop indicated in the Flow Table.

   If a node receives a packet with a Flow ID that indicates a flow not
   currently in the node's Flow Table, it returns a Route Error of type
   UNKNOWN_FLOW with Error Destination and IP Destination addresses
   copied from the IP Source of the packet triggering the error.  This
   error packet SHOULD be MAC-destined to the node from which it was
   received; if it cannot confirm reachability of the previous node
   using Route Maintenance, it MUST send the error as described in
   Section 8.1.1.  The node sending the error SHOULD attempt to salvage
   the packet triggering the Route Error.  If it does salvage the
   packet, it MUST zero the Flow ID.

   If a node receives a packet with no DSR Options header and no DSR
   Flow State header, it checks the Default Flow Table.  If there is



Johnson, et al             Expires 19 January 2005             [Page 20]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   an entry, it forwards to the next hop indicated in the Flow Table
   f