[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03

IETF MANET Working Group                              Mario Gerla, UCLA
INTERNET-DRAFT                                              Guangyu Pei
Expiration: May 17, 2001                        Rockwell Science Center
                                                     Xiaoyan Hong, UCLA
                                                           Tsu-Wei Chen
                                                    Lucent Technologies
                                                      November 17, 2000

       Fisheye State Routing Protocol (FSR) for Ad Hoc Networks

                  <draft-ietf-manet-fsr-01.txt>


Status of This Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC 2026 except that the right to
   produce derivative works is not granted.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note
   that other groups may also distribute working documents as
   Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at
   any time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress".

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft is a submission to the IETF Mobile Ad Hoc
   Networks (MANET) Working Group.  Comments on this draft may be sent
   to the Working Group at manet@itd.nrl.navy.mil, or may be sent
   directly to the authors.


Abstract

   The Fisheye State Routing (FSR) algorithm for ad hoc networks
   introduces the notion of multi-level "scope" to reduce routing
   update overhead in large networks.  A node stores the Link State
   for every destination in the network.  It periodically broadcasts


Pei, Gerla, Hong, and Chen                                     [Page 1]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


   the Link State update of a destination to its neighbors with a
   frequency that depends on the hop distance to that destination
   (i.e., the "scope" relative to that destination).  State updates
   corresponding to far away destinations are propagated with lower
   frequency than those for close by destinations.  From state updates,
   nodes construct the topology map of the entire network and compute
   efficient routes.  The route on which the packet travels becomes
   progressively more accurate as the packet approaches its
   destination.  FSR resembles Link State routing in that it propagates
   Link State updates.  However, the updates are propagated as
   aggregates, periodically (with period dependent on distance) instead
   of being flooded individually from each source.  FSR leads to major
   reduction in link O/H caused by routing table updates.  It enhances
   scalability of large, mobile ad hoc networks.


                                Contents


Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . . 1

Abstract  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

 1. Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 3

 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 4
     2.1. General Terms   . . . . . . . . . . . . . . . . . . . . . 4
     2.2. Specification Language  . . . . . . . . . . . . . . . . . 4

 3. Protocol Applicability  . . . . . . . . . . . . . . . . . . . . 4

     3.1. Networking Context  . . . . . . . . . . . . . . . . . . . 4
     3.2. Protocol Characteristics and Mechanisms   . . . . . . . . 5

 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 7

 5. Fisheye Technique . . . . . . . . . . . . . . . . . . . . . . . 7
     5.1. Fisheye Scope . . . . . . . . . . . . . . . . . . . . . . 8
     5.2. Fisheye State Routing Exchange Scheme . . . . . . . . . . 8

 6.  Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 9
     6.1 Contents of Tables . . . . . . . . . . . . . . . . . . . . 9
           6.1.1 Topology Table . . . . . . . . . . . . . . . . . . 9
           6.1.2 Neighbor Link State List . . . . . . . . . . . . . 10
           6.1.3 Routing Table  . . . . . . . . . . . . . . . . . . 10
     6.2. Link State Message  . . . . . . . . . . . . . . . . . . . 10
           6.2.1. Description of the fields . . . . . . . . . . . . 11
     6.3. Link State Message Processing . . . . . . . . . . . . . . 12



Pei, Gerla, Hong, and Chen                                     [Page 2]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


           6.3.1 Originating Link State Message . . . . . . . . . . 12
           6.3.2 Receiving Link State Message   . . . . . . . . . . 12
     6.4. Link Breakage . . . . . . . . . . . . . . . . . . . . . . 13
     6.5. Routing Table Calculation . . . . . . . . . . . . . . . . 13

 7.  Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 14

 8.  Considerations about Routing Inaccuracy . . . . . . . . . . .  14

 9.  Configuration Parameters . . . . . . . . . . . . . . . . . . . 14


 Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . . . 15

 References   . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

 Chair's Address  . . . . . . . . . . . . . . . . . . . . . . . . . 15

 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16


1. Introduction

   This document describes the Fisheye State Routing Protocol (FSR)
   [1,2] developed by the Wireless Adaptive Mobility (WAM)
   Laboratory [7] at University of California, Los Angeles.  Fisheye
   State Routing is a table-driven routing protocol which is adapted
   to the wireless ad hoc environment. It provides an implicit
   hierarchical routing structure.  Through updating link state
   information with different frequencies depending on the fisheye
   scope distance, FSR scales well to large network size and keeps
   overhead low without compromising route computation accuracy when
   the destination is near.  The routing accuracy of FSR is comparable
   with an ideal Link State scheme.  By retaining a routing entry for
   each destination, FSR avoids the extra work of "finding" the
   destination (as in on-demand routing) and thus maintains low single
   packet transmission latency.  As mobility increases, routes to
   remote destinations become less accurate.  However, when a packet
   approaches its destination, it finds increasingly accurate routing
   instructions as it enters sectors with a higher refresh rate.  As a
   results, FSR is more desirable for large mobile networks where
   mobility is high and the bandwidth is low.  By choosing proper
   number of scope levels and radius size, FSR proves to be a flexible
   solution to the challenge of maintaining accurate routes in ad hoc
   networks.

   The following properties of FSR highlight its advantages.



Pei, Gerla, Hong, and Chen                                     [Page 3]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


   *   Simplicity

   *   Usage of up-to-date shortest routes

   *   Robustness to host mobility

   *   Exchange Partial Routing Update with neighbors

   *   Reduced Routing Update Traffic


2. Terminology

2.1. General Terms

   This section defines terminology used in FSR.

   node

      A MANET router that implements this Fisheye State Routing
      protocol.

   neighbor

      Nodes that are within the radio transmission range.

   fisheye scope

      A zone that is bounded by hop distances.

2.2. Specification Language

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [8].


3. Protocol Applicability

3.1. Networking Context

   FSR is best suited for large scale mobile ad hoc wireless networks,
   as the scope update scheme has larger advantages in reducing routing
   update packet size and achieve high date packet to routing packet
   ratio. Moreover, the fact that the route error is weighted by
   distance obviously reduces the sensitivity to network size.

   FSR is also suited for high mobility ad hoc wireless networks.  This



Pei, Gerla, Hong, and Chen                                     [Page 4]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


   is because in a mobility environment, a change on a link far away
   from the source does not necessarily cause a change in the routing
   table at the source.

3.2. Protocol Characteristics and Mechanisms

   * Does the protocol provide support for unidirectional links?
     (if so, how?)
        Yes, since FSR is link state based routing protocol and
        directional link states can be included in the FSR update
        messages.

   * Does the protocol require the use of tunneling? (if so, how?)
        No.

   * Does the protocol require using some form of source routing? (if
     so, how?)

        No.

   * Does the protocol require the use of periodic messaging? (if so,
     how?)

        Yes.  The FSR periodically exchanges partial link state
        information with its neighbors

   * Does the protocol require the use of reliable or sequenced packet
     delivery? (if so, how?)

        No.  As the packets are sent periodically, they need not be
        sent reliably.

   * Does the protocol provide support for routing through a multi-
     technology routing fabric? (if so, how?)

        Yes.  It is assumed that each node's network interface is
        assigned a unique IP address.


   * Does the protocol provide support for multiple hosts per router?
     (if so, how?)

        Yes.  The router that has multiple hosts can use network ID of
        these hosts as the address to participate FSR.


   * Does the protocol support the IP addressing architecture? (if so,
   how?)



Pei, Gerla, Hong, and Chen                                     [Page 5]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


        Yes.  Each node is assumed to have a unique IP address (or
        set of unique IP addresses in the case of multiple interfaces).
        The FSR references all nodes/interfaces by their IP address.

        This version of the FSR also supports IP network addressing
        (network prefixes) for routers that provide access to a
        network of non-router hosts.


   * Does the protocol require link or neighbor status sensing (if so,
   how?)

        No.

   * Does the protocol have dependence on a central entity? (if so,
   how?)

        No.


   * Does the protocol function reactively? (if so, how?)

        No.

   * Does the protocol function proactively? (if so, how?)

        Yes.  The FSR proactively maintains routing information at each
        node.

   * Does the protocol provide loop-free routing? (if so, how?)

        Yes.  As the protocol uses link state algorithm, so the
        routing is loop-free in a stable state.  In mobile
        environment, each link state entry is destination sequenced
        which can prevent loop in routing.

   * Does the protocol provide for sleep period operation?(if so, how?)

        Yes. However, this requires TDMA MAC layer support. The router
        can be scheduled to sleep during the idle period.

   * Does the protocol provide some form of security? (if so, how?)

        No.

   * Does the protocol provide support for utilizing multi-channel,
     link-layer technologies? (if so, how?)




Pei, Gerla, Hong, and Chen                                     [Page 6]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



        Yes, in fact the multi-channel can be used to separate routing
        messages from user data packets.


4. Protocol Overview

   Fisheye State Routing is a table-driven or proactive routing
   protocol.  It bases on link state protocol and has the ability of
   immediately providing route information when needed. The fisheye
   scope technique allows exchanging link state messages at different
   intervals for nodes within different fisheye scope distance, which
   reduces the link state message size.  Further optimization allows
   FSR only broadcast topology message to neighbors [4] in order to
   reduce the flood overhead.  With these optimizations, FSR
   significantly reduces the topology exchange overhead and scales
   well to large network size.

   FSR routes each data packet according to locally computed routing
   table.  The routing table uses most recent topology information.
   The fisheye scope message updating scheme will not lose routing
   accuracy for inner scope nodes.  For outer scope nodes,
   information in routing entries may blur due to longer exchange
   interval, but the extra work of "finding" the destination (as in
   on-demand routing) is not necessary.  Thus low single packet
   transmission latency can be maintained.  At a mobile environment,
   this inaccuracy for remote nodes will increase.  However, when a
   packet approaches its destination, it finds increasingly accurate
   routing instructions as it enters sectors with a higher refresh rate.

   FSR doesn't trigger any control messages when a link failure is
   reported.  Thus it is suitable for high topology change environment.
   The broken link will not be included in the next fisheye scope link
   state message exchange.  Sequence number and table refreshment
   enables the FSR to maintain the latest link state information and
   loop-free in a unreliable propagation media and highly mobile
   network.

   The protocol works independently with the IP format of packets and
   is a distributed protocol.  It can be implemented either in network
   layer or in application layer. It only deals with routing table
   management of the network system.


5. Fisheye Technique

   FSR uses the "fisheye" technique proposed by Kleinrock and
   Stevens [3], where the technique was used to reduce the size of



Pei, Gerla, Hong, and Chen                                     [Page 7]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


   information required to represent graphical data.  The eye of a fish
   captures with high detail the pixels near the focal point.
   The detail decreases as the distance from the focal point increases.
   In routing, the fisheye approach translates to maintaining accurate
   distance and path quality information about the immediate
   neighborhood of a node, with progressively less detail as the
   distance increases.

5.1. Fisheye Scope

   The fisheye scope is defined as the set of nodes that can be
   reached within a given number of hops.  An example of a fisheye
   scope (at node A) of hop 2 is shown below.

             +-----------------------------------------+
             |                       +---+             | +---+
             |            +---+   ---| F |-------|-------| H |
      +---+  |  +---+   --| C |--/   +---+     +---+   | +---+
      | G |-----| D |--/  +---+                | E |   |
      +---+  |  +---+       |        +---+     +---+   |
             |            +---+   ---| B |-------|     |
             |            | A |--/   +---+             |
             |            +---+                        |
             +-----------------------------------------+
               Fisheye Scope at Node A of Hop 2

   Note that in this example node E can be reached through B from A
   with 2 hops and through F with 3 hops. Since the minimum path
   length is 2, E are within the fisheye scope of node A.  By setting
   multiple hop radius, multiple level of scopes will cover the
   entire network.

5.2. Fisheye State Routing Exchange Scheme

   FSR is functionally similar to Link State Routing (LS) in that
   it maintains a topology map at each node.  The key difference is
   the way in which routing information is disseminated.  In LS, the
   update message could consume considerable amount of bandwidth,
   which depends on the update period.  In order to reduce the
   size of update messages without seriously affecting routing
   accuracy, FSR uses the Fisheye technique. Entries in routing
   table corresponding to nodes within the smallest scope are
   propagated to the neighbors with the highest frequency.  The
   rest of the entries are sent out with lower frequencies.  As a
   result, a considerable fraction of link state entries is
   suppressed in a typical update, thus reducing the message size.
   Thus by using different exchange periods for different entries
   in routing table, routing update overhead is reduced.



Pei, Gerla, Hong, and Chen                                     [Page 8]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



   This strategy produces timely updates from near stations, but
   creates large latencies from stations afar.  However the imprecise
   knowledge of the best path to a distant destination is
   compensated by the fact that the route becomes progressively more
   accurate as the packet gets closer to destination.  As the
   network size grows large, a "graded" frequency update plan must
   be used across multiple scopes to keep the overhead low.

   Link state packets are generated and flooded into the network
   periodically or whenever a node detects a topology change.
   In FSR, link state packets are not flooded.  Instead, they are
   exchanged periodically with their local neighbors only.  A node
   maintains a link state table based on the up-to-date information
   received from neighboring nodes.  Sequence numbers are used for
   entry replacements. The sequenced periodic table update resembles
   the vector exchange in Destination-Sequenced Distance-Vector
   Routing (DSDV [5]) where the distances are updated according to
   the time stamp or sequence number assigned by the node
   originating the update.  However, in FSR link states rather than
   distance vectors are propagated.  Moreover, like in LS, a full
   topology map is kept at each node and shortest paths are computed
   using this map.

   In a wireless environment, a radio link between mobile nodes may
   experience frequent disconnects and reconnects.  The LS protocol
   releases a link state update for each such change, which floods
   the network and causes excessive overhead.  FSR avoids this
   problem by using periodic, instead of event driven, exchange of
   the topology map, greatly reducing the control message overhead.


6. Protocol Operation

   This section discusses the operation of FSR routing protocol.
   The sending and receiving of routing packets are in the proactive
   nature.  And the routing packets are processed separately from
   ordinary data packets.

6.1 Contents of Tables

   Each node running FSR is required to maintain following tables.
   The required tables and suggested fields are listed below.

6.1.1 Topology Table

   Topology table records the topology information obtained from the
   link state message.  Each destination  has an entry in the table.



Pei, Gerla, Hong, and Chen                                     [Page 9]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


   The entry contains two parts: the link state information,
   a destination sequenced sequence number.  Based on this table,
   the routing table is calculated.  The distance information is
   obtained from routing table calculation and is used to classified
   the node to a fisheye scope.  The topology table has following
   fields for every link state entry:
   -  Destination Address
   -  Destination sequence number
   -  Link State List

6.1.2 Neighbor Link State List

   When a node receives a link state message, it records/updates the
   sender's link state information in its neighbor table.  If the node
   does not receive link state updates from a neighbor for a
   NEIGHBOR_TIMEOUT interval, the entry for that neighbor will be
   deleted from the neighbor Link State List.  The following
   information is maintained in the list for each neighbor node:
   -  Neighbor Node Link State List
   -  Latest timestamp of the received link state from the neighbor

6.1.3 Routing Table

   The routing table of FSR provides the next hop information to
   forward the packets for the other destinations in the network.
   The entries are updated when topology table is changed.  The
   routing table has the following fields:
   -  Destination Address
   -  Next hop address
   -  Distance

   Initially when a FSR router is powered up, it knows nothing about
   the network except routing information about all interfaces and
   hosts that are directly attached to the router.

6.2. Link State Message

   Periodically, nodes broadcast the topology tables to their
   neighbors.  By listening to these broadcastings, each node builds
   up its neighbor link list.  As the source address (the address
   originating this message) and destination address(broadcast address
   of the network) are already included in the IP header, the link
   state message given here only contains packet size and topology
   table entries.

   The proposed format of a Link State Message (assume the link cost
   is measured in hop distance and is 1 for each neighbor, therefore
   the link cost is not included) is as follows.



Pei, Gerla, Hong, and Chen                                    [Page 10]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Packet Length         |           Reserved            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address 1                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Destination Sequence Number 1                 | N_neighbors 1 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address 1                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                             . . .                             :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 Neighbor Address N_neighbors 1                |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address 2                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Destination Sequence Number 2                 | N_neighbors 2 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address 1                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                             . . .                             :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 Neighbor Address N_neighbors 2                |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                             . . .                             :
   :                                                               :
                                 (etc)


6.2.1. Description of the fields

   Packet Length

      The length (in bytes) of the packet.

   Reserved

      The bits are set to '0' and are ignored on reception.

   Destination Address 1
      The first destination address in the topology table.

   Destination Sequence Number 1
      The last sequence number received in the past by the source
      of the first destination.



Pei, Gerla, Hong, and Chen                                    [Page 11]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



   N_neighbors 1
      The number of neighbors of the first destination.

   Neighbor Address 1, ..., Neighbor Address N_neighbors 1
      The list of neighbors of the first destination.  The number is
      indicated in the field N_neighbors 1.

   Destination Address 2
      The second destination address in the topology table.

   These fields are repeated for each entry in the topology table.
   The length of link state message is limited to the maximum IP
   packet size.  In that case, multiple packets may required to
   broadcast all the topology entries.

6.3. Link State Message Processing

6.3.1 Originating Link State Message

   Each node broadcasts the latest link state information to its
   neighbors.  FSR uses different update intervals for different
   entries in the table according to their distance from the node.
   To be precise, entries corresponding to nodes that are nearby
   (within a predefined scope) are propagated to the neighbors more
   frequently than entries of nodes that are far away.  When it is
   the time for updating fisheye scope-i's topology information,
   by scanning through the topology table, the nodes whose distance
   to the current node is within the range of scope-i will be included
   in the update message.  The update interval of fisheye scope level i
   is UpdateInterval_i.  If the current node will be included in the
   link state message, its sequence number is increased by one.

6.3.2 Receiving Link State Message

   When a node receives a link state message, it first checks its
   neighbor link state list for the sender.  If the sender is a new
   neighbor, it will insert the sender into the list.  Otherwise,
   it will update the timestamp and link state information about
   the sender in the list.  The node then processes the link state
   information contained in the update message.  For each link state
   entry in the packet, only the most up to date entry is copied to
   the local topology table.  That is, if any entry in the incoming
   message has a larger sequence number regarding to destination j
   comparing with the ones stored in the node's local storage, the
   local entry will be replaced by the incoming one.  After all
   incoming entries are examined, if there are any changes in the
   topology table, routing table is updated.



Pei, Gerla, Hong, and Chen                                    [Page 12]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



6.4 Link Breakage

   In a mobile ad hoc network, link breakage is a frequent incident.
   Each node uses soft state to detect link breakage, i.e., each node
   will delete a neighbor from its link state list if it does not
   receive link state messages from the neighbor after a
   NEIGHBOR_TIMEOUT interval.

   FSR does not rely on feedback from MAC.  If MAC can provide
   Feedback in case of link failure, FSR will use the report to update
   the neighbor table and provide more up-to-date routing information.
   This faster discovery can result in a better performance.

6.5. Routing Table Calculation

   Whenever there are changes in the topology table, the routing table
   will be updated.  Based on the latest topology table, the Dijkstra's
   algorithm [6] is performed to find the shortest paths from current
   node for all the destinations known to it, i.e., in the topology
   table.  Old routing table is replaced completely by the newly
   computed next hop information.

   FindSP(i) is the algorithm used to create a shortest path tree
   rooted at i.  In this documentation, the procedure is based on the
   Dijkstra's algorithm with modifications so that the next hop
   (denoted as table NEXTi()) and the distance (denoted as table Di())
   are computed in parallel with the tree reconstruction.

   At node i, FindSP(i) initiates with P = {i}, then it iterates until
   P = V, where V is the set of all nodes.  In each iteration,
   it searches for a node j such that node j minimizes the value of
   (Di(k) + weight(k,j)), for all j and k, where j belongs to {V - P},
   k belongs to nodes in topology table and weight(k,j) does not equal
   to infinite.  Once node j is found, P is augmented with j, D(j) is
   assigned to D(k) + weight(k,j) and NEXTi(j) is assigned to NEXTi(k).
   That is, as the shortest path from i to j has to go through k,
   the successor for i to j is the same successor for i to k.

   A weight function, weight(), is used to compute the distance of
   a link.  Since minimum hop shortest path is considered in this
   stage, this weight function simply returns 1 if two nodes have
   direct connection, otherwise, it returns 0.  This weight function
   may also be replaced with other functions for routing with different
   metrics.  For instance, a bandwidth function can be used to realize
   a QoS routing.





Pei, Gerla, Hong, and Chen                                    [Page 13]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



7. Data Packet Forwarding

   As the routing table is calculated background, hop by hop data
   packet forwarding is very straight forward.  The source node or
   any intermediate nodes retrieve the destination from the data
   packet, and look at their routing tables.  If the route is known,
   i.e., there is an entry for the destination, the data packet is
   sent to the next hop node.  This procedure repeats until the
   packet finally reaches the destination.


8. Considerations about Routing Inaccuracy

   FSR only has inaccurate routing information about remote nodes.
   This inaccuracy is affected by the route update interval.
   The longer the update interval, the less accurate the routing
   information.  However, several features of FSR reduces the routing
   inaccuracy.  For large network size, as the route error is weighted
   by distance, the sensitivity to network size is largely reduced.
   Thus, receiving updates about far away nodes at low frequency will
   not significantly affect the routing accuracy.  The same mechanism
   applies to mobility, i.e., the progressive accurating of the routing
   path reduces the impact from mobility.

   Also, increasing the scope radius will improve the accuracy.  But
   using larger radii will increase the routing update packets which
   causes more control overhead.


9.  Configuration Parameters

   This section gives default values for some important parameters
   associated with the FSR protocol operations.  Readers should take
   these values as an example for the design of their own network
   scenario.  Different values of these parameters may affect the
   performance of the protocol.  The following values define a network
   with two level fisheye scopes.  The inner scope is bounded by hop
   distance 2.  Two different update frequencies are used for the
   scopes, they are called IntraScope_Interval and InterScope_Interval
   for inner and outer scope respectively.

      Parameter Name                   Value
      -----------------------------    ----------------
      Number of Scope                  2
      IntraScope_Interval              5 second
      IntreScope_Interval              15 seconds
      NEIGHBOR_TIMEOUT                 15 seconds



Pei, Gerla, Hong, and Chen                                    [Page 14]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



Acknowledgments

   This work was supported in part by NSF under contract ANI-9814675,
   in part by DARPA under contract DAAB07-97-C-D321.


References

   [1] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing:
   A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of
   ICC 2000, New Orleans, LA, Jun. 2000.

   [2] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in
   Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless
   Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000.

   [3] L. Kleinrock and K. Stevens, "Fisheye: A Lenslike Computer
   Display Transformation," Technical report, UCLA, Computer Science
   Department, 1971.

   [4] T.-W. Chen and M. Gerla, "Global State Routing: A New Routing
   Scheme for Ad-hoc Wireless Networks," In Proceedings of IEEE ICC'98,
   Atlanta, GA, Jun. 1998, pp. 171-175.

   [5] C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination-
   Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,"
   In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994,
   pp. 234-244.

   [6] R. Sedgewick,Weighted Graphs, chapter 31, Addision-Wesley, 1983.

   [7] UCLA Wireless Adaptive Mobility (WAM) Laboratory.
       http://www.cs.ucla.edu/NRL/wireless

   [8] S. Bradner.  Key words for use in RFCs to Indicate
       Requirement Levels.  RFC 2119, March 1997.


Chair's Address

   The MANET Working Group can be contacted via its current chairs:

        M. Scott Corson
        Institute for Systems Research
        University of Maryland
        College Park, MD  20742
        USA



Pei, Gerla, Hong, and Chen                                    [Page 15]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000



        Phone:  +1 301 405-6630
        Email:  corson@isr.umd.edu


        Joseph Macker
        Information Technology Division
        Naval Research Laboratory
        Washington, DC  20375
        USA

        Phone:  +1 202 767-2001
        Email:  macker@itd.nrl.navy.mil


Authors' Addresses

   Questions about this document can also be directed to the authors:

        Guangyu Pei
        Rockwell Science Center
        1049 Camino Dos Rios
        P.O. Box 1085
        Thousand Oaks, CA 91358-0085
        USA

        Phone:  +1 805 373-4639
        Fax:    +1 805 373-4383
        Email:  gpei@rsc.rockwell.com


        Mario Gerla
        3732F Boelter Hall
        Computer Science Department
        University of California
        Los Angeles, CA  90095-1596
        USA

        Phone:  +1 310 825-4367
        Fax:    +1 310 825-7578
        Email:  gerla@cs.ucla.edu


        Tsu-Wei Chen
        Bell Laboratories
        Lucent Technologies
        600 Mountain Avenue
        Murray Hill, NJ 07974



Pei, Gerla, Hong, and Chen                                    [Page 16]


INTERNET-DRAFT     Fisheye State Routing Protocol     November 17, 2000


        USA

        Email:  tsuwei@research.bell-labs.com


        Xiaoyan Hong
        3820 Boelter Hall
        Computer Science Department
        University of California
        Los Angeles, CA  90095-1596
        USA

        Phone:  +1 310 825-4623
        Fax:    +1 310 825-7578
        Email:  hxy@cs.ucla.edu




Pei, Gerla, Hong, and Chen                                    [Page 17]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/