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]