dsr_draft1.txt

来自「dsr路协议规范」· 文本 代码 · 共 1,527 行 · 第 1/5 页

   each Route Request initiated, if no Route Reply is received for it,
   the node could double the hop limit used on the previous attempt,
   to progressively explore for the target node without allowing the
   Route Request to propagate over the entire network.  However, this
   expanding ring search approach could have the effect of increasing
   the average latency of Route Discovery, since multiple Discovery
   attempts and timeouts may be needed before discovering a route to the
   target node.





Johnson, et al            Expires 2 September 2001             [Page 12]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


3.4. Additional Route Maintenance Features

3.4.1. Packet Salvaging

   After sending a Route Error message as part of Route Maintenance
   as described in Section 3.2, a node MAY attempt to "salvage" the
   data packet that caused the Route Error rather than discarding the
   packet.  To attempt to salvage a packet, the node sending a Route
   Error searches its own Route Cache for a route from itself to the
   destination of the packet causing the Error.  If such a route is
   found, the node MAY salvage the packet after returning the Route
   Error by replacing the original source route on the packet with the
   route from its Route Cache.  The node then forwards the packet to the
   next node indicated along this source route.  For example, in the
   situation shown in the example of Section 3.2, if node C has another
   route cached to node E, it can salvage the packet by replacing the
   original route in the packet with this new route from its own Route
   Cache, rather than discarding the packet.

   When salvaging a packet in this way, a count is maintained in the
   packet of the number of times that it has been salvaged, to prevent a
   single packet from being salvaged endlessly.  Otherwise, it could be
   possible for the packet to enter a routing loop, as different nodes
   repeatedly salvage the packet and replace the source route on the
   packet with routes to each other.


3.4.2. Automatic Route Shortening

   Source routes in use MAY be automatically shortened if one or more
   intermediate hops in the route become no longer necessary.  This
   mechanism of automatically shortening routes in use is somewhat
   similar to the use of passive acknowledgements [15].  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 unused portion of that source route.  If this
   node is not the intended next hop for the packet but is named in
   the later unused 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













Johnson, et al            Expires 2 September 2001             [Page 13]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


   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) returns 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.


3.4.3. 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,
   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.












Johnson, et al            Expires 2 September 2001             [Page 14]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


4. Conceptual Data Structures

   This document describes the operation of the DSR protocol in terms
   of a number of conceptual data structures.  This section describes
   each of these data structures and provides an overview of its use
   in the protocol.  In an implementation of the protocol, these data
   structures MAY be implemented in any manner consistent with the
   external behavior described in this document.


4.1. Route Cache

   All routing information needed by a node participating in an ad hoc
   network using DSR is stored in that node's Route Cache.  Each node in
   the network maintains its own Route Cache.  A node adds information
   to its Route Cache as it learns of new links between nodes in the
   ad hoc network; for example, a node may learn of new links when it
   receives a packet carrying either a Route Reply or a DSR Routing
   header.  Likewise, a node removes information from its Route Cache as
   it learns that existing links in the ad hoc network have broken; for
   example, a node may learn of a broken link when it receives a packet
   carrying a Route Error or through the link-layer retransmission
   mechanism reporting a failure in forwarding a packet to its next-hop
   destination.

   It is possible to interface a DSR network with other networks,
   external to this DSR network.  Such external networks may, for
   example, be the Internet, or may be other ad hoc networks routed
   with a routing protocol other than DSR.  Such external networks may
   also be other DSR networks that are treated as external networks
   in order to improve scalability.  The complete handling of such
   external networks is beyond the scope of this document.  However,
   this document specifies a minimal set of requirements and features
   necessary to allow nodes only implementing this specification to
   interoperate correctly with nodes implementing interfaces to such
   external networks.  This minimal set of requirements and features
   involve the First Hop External (F) and Last Hop External (L)
   bits in a Source Route option (Section 5.7) and a Route Reply
   option (Section 5.3) in a packet's DSR header (Section 5).  These
   requirements also include the addition of an External flag bit
   tagging each node in the Route Cache, copied from the First Hop
   External (F) and Last Hop External (L) bits in the Source Route
   option or Route Reply option from which the link to this node was
   learned.

   The Route Cache SHOULD support storing more than one route to each
   destination.  In searching the Route Cache for a route to some
   destination node, the Route Cache is indexed by destination node
   address.  The following properties describe this searching function
   on a Route Cache:



Johnson, et al            Expires 2 September 2001             [Page 15]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


    -  Each implementation of DSR at any node MAY choose any appropriate
       strategy and algorithm for searching its Route Cache and
       selecting a "best" route to the destination from among those
       found.  For example, a node MAY choose to select the shortest
       route to the destination (the shortest sequence of hops), or it
       MAY use an alternate metric to select the route from the Cache.

    -  However, if there are multiple cached routes to a destination,
       the selection of routes when searching the Route Cache SHOULD
       prefer routes that do not have the External flag set on any node.
       This preference will select routes that lead directly to the
       target node over routes that attempt to reach the target via any
       external networks connected to the DSR ad hoc network.

    -  In addition, any route selected when searching the Route Cache
       MUST NOT have the External bit set for any nodes other than
       possibly the first node, the last node, or both; the External bit
       MUST NOT be set for any intermediate hops in the route selected.

   An implementation of a Route Cache MAY provide a fixed capacity
   for the cache, or the cache size MAY be variable.  The following
   properties describe the management of available space within a node's
   Route Cache:

    -  Each implementation of DSR at each node MAY choose any
       appropriate policy for managing the entries in its Route Cache,
       such as when limited cache capacity requires a choice of which
       entries to retain in the Cache.  For example, a node MAY chose a
       "least recently used" (LRU) cache replacement policy, in which
       the entry last used longest ago is discarded from the cache if a
       decision needs to be made to allow space in the cache for some
       new entry being added.

    -  However, the Route Cache replacement policy SHOULD allow routes
       to be categorized based upon "preference", where routes with a
       higher preferences are less likely to be removed from the cache.
       For example, a node could prefer routes for which it initiated
       a Route Discovery over routes that it learned as the result of
       promiscuous snooping on other packets.  In particular, a node
       SHOULD prefer routes that it is presently using over those that
       it is not.

   Any suitable data structure organization, consistent with this
   specification, MAY be used to implement the Route Cache in any node.
   For example, the following two types of organization are possible:

    -  In DSR, the route returned in each Route Reply that is received
       by the initiator of a Route Discovery (or that is learned from
       the header of overhead packets, as described in Section 6.1.4)
       represents a complete path (a sequence of links) leading to the



Johnson, et al            Expires 2 September 2001             [Page 16]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


       destination node.  By caching each of these paths separately,
       a "path cache" organization for the Route Cache can be formed.
       A path cache is very simple to implement and easily guarantees
       that all routes are loop-free, since each individual route from
       a Route Reply or Route Request or used in a packet is loop-free.
       To search for a route in a path cache data structure, the sending
       node can simply search its Route Cache for any path (or prefix of
       a path) that leads to the intended destination node.

       This type of organization for the Route Cache in DSR has
       been extensively studied through simulation [5, 11, 18] and
       through implementation of DSR in a mobile outdoor testbed under
       significant workload [19, 20, 20].

    -  Alternatively, a "link cache" organization could be used for the
       Route Cache, in which each individual link (hop) in the routes
       returned in Route Reply packets (or otherwise learned from the
       header of overhead packets) is added to a unified graph data
       structure of this node's current view of the network topology.
       To search for a route in link cache, the sending node must use
       a more complex graph search algorithm, such as the well-known
       Dijkstra's shortest-path algorithm, to find the current best path
       through the graph to the destination node.  Such an algorithm is
       more difficult to implement and may require significantly more
       CPU time to execute.

       However, a link cache organization is more powerful than a
       path cache organization, in its ability to effectively utilize
       all of the potential information that a node might learn about
       the state of the network:  links learned from different Route
       Discoveries or from the header of any overheard packets can be
       merged together to form new routes in the network, but this
       is not possible in a path cache due to the separation of each
       individual path in the cache.

       This type of organization for the Route Cache in DSR, including
       the effect of a range of implementation choices, has been studied
       through detailed simulation [9].

   The choice of data structure organization to use for the Route Cache
   in any DSR implementation is a local matter for each node and affects
   only performance; any reasonable choice of organization for the Route
   Cache does not affect either correctness or interoperability.


4.2. Route Request Table

   The Route Request Table records information about Route Requests that
   have been recently originated or forwarded by this node.  The table
   is indexed by IP address.



Johnson, et al            Expires 2 September 2001             [Page 17]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001