IETF MANET Working Group Mario Gerla, UCLA
INTERNET-DRAFT Xiaoyan Hong, UCLA
Expiration: December 17, 2002 Guangyu Pei
Rockwell Scientific Company
June 17, 2002
Fisheye State Routing Protocol (FSR) for Ad Hoc Networks
<draft-ietf-manet-fsr-03.txt>
Status of This Memo
This document is an Internet-Draft and is subject to all provisions
of Section 10 of RFC2026.
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/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
the Link State update of a destination to its neighbors with a
frequency that depends on the hop distance to that destination
Gerla, Hong and Pei [Page 1]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
(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. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 4
3.2. Specification Language . . . . . . . . . . . . . . . . . 4
4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 5
4.1. Networking Context . . . . . . . . . . . . . . . . . . . 5
4.2. Protocol Characteristics and Mechanisms . . . . . . . . 5
5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 7
6. Fisheye Technique . . . . . . . . . . . . . . . . . . . . . . . 7
6.1. Fisheye Scope . . . . . . . . . . . . . . . . . . . . . . 8
6.2. Fisheye State Routing Exchange Scheme . . . . . . . . . . 8
7. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 9
7.1 Contents of Tables . . . . . . . . . . . . . . . . . . . . 9
7.1.1 Neighbor List . . . . . . . . . . . . . . . . . . 9
7.1.2 Topology Table . . . . . . . . . . . . . . . . . . 10
7.1.3 Routing Table . . . . . . . . . . . . . . . . . . 10
7.2. Link State Message . . . . . . . . . . . . . . . . . . . 10
7.2.1. Description of the fields . . . . . . . . . . . . 11
7.3. Link State Message Processing . . . . . . . . . . . . . . 12
7.3.1 Originating Link State Message . . . . . . . . . . 12
7.3.2 Receiving Link State Message . . . . . . . . . . 12
7.4. Link Breakage . . . . . . . . . . . . . . . . . . . . . . 13
7.5. Routing Table Calculation . . . . . . . . . . . . . . . . 13
Gerla, Hong and Pei [Page 2]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
8. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 14
9. Considerations about Routing Inaccuracy . . . . . . . . . . . 14
10. Configuration Parameters . . . . . . . . . . . . . . . . . . . 15
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 15
References . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 16
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.
* Simplicity
* Usage of up-to-date shortest routes
* Robustness to host mobility
* Exchange Partial Routing Update with neighbors
Gerla, Hong and Pei [Page 3]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
* Reduced Routing Update Traffic
2. Changes
Major changes from version 02 to version 03:
- Added descriptions of operations on the lastHeardTime variable
in the topology table.
- Editorial changes.
Major changes from version 01 to version 02:
- Added operations to exclude those entries whose propagation
will not cause topology update at its neighbors.
- Editorial changes.
Major changes from version 00 to version 01:
- Update of "Status of This Memo".
3. Terminology
3.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.
3.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].
Gerla, Hong and Pei [Page 4]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
4. Protocol Applicability
4.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
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.
4.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?)
Gerla, Hong and Pei [Page 5]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
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?)
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?)
Gerla, Hong and Pei [Page 6]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
Yes, in fact the multi-channel can be used to separate routing
messages from user data packets.
5. 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 does not 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.
6. Fisheye Technique
FSR uses the "fisheye" technique proposed by Kleinrock and
Stevens [3], where the technique was used to reduce the size of
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
Gerla, Hong and Pei [Page 7]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
neighborhood of a node, with progressively less detail as the
distance increases.
6.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.
6.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.
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.
Gerla, Hong and Pei [Page 8]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
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. The
periodic updates act also as neighbor discovering. Each node,
after hearing its neighbor's broadcast message, adds/updates
its neighbor list and topology table. 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.
The entries to be included in the periodic broadcast message
are selected according to the rule that their propagation should
cause an update in topology tables of its neighbors. The
benefit of this operation is large in a dense network where
a node may find that all its neighbors have the same freshness
of the information about another node. By excluding such
entries, only the effective entries are included in the
link state update message which leads to reduction in the
size of the message.
7. 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.
7.1 Contents of Tables
Each node running FSR is required to maintain following tables.
The required tables and suggested fields are listed below.
7.1.1 Neighbor List
When a node receives a link state message, it records/updates the
sender's link state information in its neighbor list. If the node
Gerla, Hong and Pei [Page 9]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
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 list. The following
information is maintained in the list for each neighbor node:
- Neighbor ID
- Latest time receiving from the neighbor
7.1.2 Topology Table
Topology table records the topology information obtained from the
link state message. Each destination has an entry in the table.
The entry contains three parts: the destination information, its
link state information and variables for selecting effective
entries. Based on this table, the routing table is calculated.
The distance information is maitained in the routing table
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
- Last heard time
- A list of its neighbors
- Previous sequence number
- A flag for "NeedToSend"
7.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.
7.2. Link State Message
Periodically, nodes broadcast the effective portion of the
topology tables to their neighbors. By listening to these
broadcastings, each node builds up its neighbor 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. At very beginning, this broadcast contains only
itself with empty topology table.
The proposed format of a Link State Message (assume the link cost
is measured in hop distance and is 1 for each neighbor, therefore
Gerla, Hong and Pei [Page 10]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
the link cost is not included) is as follows.
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)
7.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 for the first destination
in the past by the source of the message.
N_neighbors 1
The number of neighbors of the first destination.
Gerla, Hong and Pei [Page 11]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
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.
7.3. Link State Message Processing
7.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 broadcasting a node's topology table (for any
broadcast frequencies), the node first times out its topology
table. The lastHeardTime variable in the entries corresponding
to the frequency is checked, stale entries are timed out. The
time-out interval is set to be three times of the update interval.
For inner scope broadcasting, timing-out is performed after the
node refreshes its own entry. Then at the time for updating
fisheye scope-i's topology information, the node scans the
topology table to pick up corresponding nodes. The nodes
whose distance to the current node is within the range of
scope-i will be included in the update message if it is an
effective entry. 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.
To select the effective portion of the scope-i link state
message, an entry corresponding to scope-i is chosen if its
flag of "NeedToSend" is true. After the message is sent,
all the flags of entries of scope-i are reset to false,
and the previous sequence numbers are copied with the current
sequence number.
7.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 of the sender in the neighbor list.
The node then processes the link state information contained
Gerla, Hong and Pei [Page 12]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
in the update message. For each link state entry in the packet,
the following situations are considered.
(1) If it is a new destination to the current node, a new
topology table entry will be created and filled with
corresponding information. The "NeedToSend" flag sets
to true.
(2) Otherwise, only the most up to date destination 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 topology table, the local entry will be
replaced by the incoming one. The "NeedToSend" flag sets
to true.
(3) For a incoming destination not fitting into the previous
two cases, if the information is older than the one
stored in current node, i.e., its destination sequence
number is less than the previous sequence number of the
stored entry, the entry in the current node's topology
table needs to be sent in next link state update. The
"NeedToSend" flag of the entry sets to true.
In all the cases, when a topology entry is inserted or updated,
the time is stamped in the lastHeardTime variable. After all
incoming entries are examined, if there are any changes in the
topology table, routing table is recomputed.
7.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
considers a link to be broken if it does not receive link state
messages from the neighbor after a NEIGHBOR_TIMEOUT interval.
The node then deletes the neighbor from neighbor list and remove
it from its link state entry in topology table.
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.
The operation is the same as above. This faster discovery can
result in a better performance.
7.5. Routing Table Calculation
Whenever there are changes in the topology table, the routing table
will be recomputed. The topology table is checked to remove stale
entries prior to the calculation. Based on the latest topology
table, the Dijkstra's algorithm [6] is performed to find the
shortest paths from current node to all the destinations known
to it, i.e., in the topology table. Old routing table is replaced
Gerla, Hong and Pei [Page 13]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
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.
8. Data Packet Forwarding
As the routing table is calculated in 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.
9. 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
Gerla, Hong and Pei [Page 14]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
using larger radii will increase the routing update packets which
causes more control overhead.
10. 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
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.
Gerla, Hong and Pei [Page 15]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
[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
Flarion Technologies, Inc.
Bedminster One
135 Route 202/206 South
Bedminster, NJ 07921
USA
Phone: +1 908 947-7033
Email: corson@flarion.com
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:
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
Xiaoyan Hong
Gerla, Hong and Pei [Page 16]
INTERNET-DRAFT Fisheye State Routing Protocol June 17, 2002
3803F 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
Guangyu Pei
Rockwell Scientific Company
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@rwsc.com
Gerla, Hong and Pei [Page 17]
