INTERNET-DRAFT Zygmunt J. Haas, Cornell University
Marc R. Pearlman, Cornell University
Prince Samar, Cornell University
Expires in six months on July 2001 January 2001
The Interzone Routing Protocol (IERP) for Ad Hoc Networks
<draft-ietf-manet-zone-ierp-00.txt>
Status of this Memo
This document is an Internet-Draft and is NOT offered in accordance
with Section 10 of RFC2026, and the author does not provide the IETF
with any rights other than to publish as an Internet-Draft.
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.
Distribution of this memo is unlimited.
Abstract
This document describes the Interzone Routing Protocol (IERP), the
reactive routing component of the Zone Routing Protocol (ZRP).
IERP adapts existing reactive routing protocol implementations to
take advantage of the known topology of each node's surrounding
r-hop neighborhood (routing zone), provided by the Intrazone
Routing Protocol (IARP). The availability of routing zone routes
allows IERP to suppress route queries for local destinations.
When a global route discovery is required, the routing zone based
bordercast service can be used to efficiently guide route queries
outward, rather than blindly relaying queries from neighbor to
neighbor. Once a route has been discovered, IERP can use routing
zones to automatically redirect data around failed links.
Similarly, suboptimal route segments can be identified and traffic
re-routed along shorter paths.
Haas, Pearlman, Samar Expires July 2001 [Page i]
INTERNET DRAFT Interzone Routing Protocol January 2001
Contents
Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Applicability Statement . . . . . . . . . . . . . . . . . . . iii
A. Networking Context . . . . . . . . . . . . . . . . . iii
B. Protocol Characteristics and Mechanisms . . . . . . . iii
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1
2. On Demand Route Discovery and
the Interzone Routing Protocol (IERP) . . . . . . . . . . . 2
3. Routing Zone Based Route Maintenance . . . . . . . . . . . 3
4. IERP Conversion Guidelines . . . . . . . . . . . . . . . . 4
5. Implementation Example - Reactive Source Routing . . . . . 5
A. Packet Format . . . . . . . . . . . . . . . . . . . . . 6
B. Data Structures . . . . . . . . . . . . . . . . . . . . 7
C. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 8
D. State Machine . . . . . . . . . . . . . . . . . . . . . 8
E. Pseudocode Implementation . . . . . . . . . . . . . . . 9
6. References . . . . . . . . . . . . . . . . . . . . . . . . 12
Authors' Information . . . . . . . . . . . . . . . . . . . . . 14
MANET Contact Information . . . . . . . . . . . . . . . . . . . 14
Haas, Pearlman, Samar Expires July 2001 [Page ii]
INTERNET DRAFT Interzone Routing Protocol January 2001
Applicability Statement
A. Networking Context
The Interzone Routing Protocol (IERP) is the global reactive
routing component of the Zone Routing Protocol (ZRP). IERP
adapts existing reactive routing protocol implementations to
take advantage of the known topology of each node's surrounding
r-hop neighborhood (routing zone), provided by the Intrazone
Routing Protocol (IARP). The availability of routing zone routes
allows IERP to suppress route queries for local destinations.
When a global route discovery is required, the routing zone based
bordercast service [2] can be used to efficiently guide route
queries outward, rather than blindly relaying queries from neighbor
to neighbor. Once a route has been discovered, IERP can use
routing zones to automatically redirect data around failed links.
Similarly, suboptimal route segments can be identified and traffic
re-routed along shorter paths.
The effectiveness of bordercasting and zone based route maintenance
improves with increased routing zone radius. However, an increased
routing radius requires additional proactive traffic to maintain a
current view of the larger routing zone. Based on this tradeoff, it
follows that networks characterized by a highly dynamic topology and/
or low route demand favor smaller routing zones. In extreme cases,
the routing zone reduces to zero hops (or one hop, for multiple
channel networks) and route discovery degenerates into traditional
flood searching. As the demand for new routes increases and/or the
network topology stabilizes, larger routing zones become more
appropriate.
B. Protocol Characteristics and Mechanisms
* Does the protocol provide support for unidirectional links?
(if so, how?)
Yes. The IERP can provide "local" support for unidirectional
links, based on routing information provided by the IARP.
A unidirectional link can be used as long as the link
source and link destination lie within each other's routing zone.
* 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.
Haas, Pearlman, Samar Expires July 2001 [Page iii]
INTERNET DRAFT Interzone Routing Protocol January 2001
* Does the protocol require the use of periodic messaging?
(if so, how?)
No.
* Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?)
No.
* 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. Multiple hosts may be associated with a router. These
hosts can be identified by the neighbor discovery/maintenance
process.
By default, it is assumed that a host's association with a router
is not permanent. As a result, IERP exchanges routing
information for individual hosts in the same manner as routing
information for routers.
In cases where a router is permanently associated with a network
(subnetwork), IERP may support the exchange of network
(subnetwork) prefixes in place of all aggregated host IP
addresses.
* 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). IERP
references all nodes/interfaces by their IP address.
* Does the protocol require link or neighbor status sensing
(if so, how?)
No.
Haas, Pearlman, Samar Expires July 2001 [Page iv]
INTERNET DRAFT Interzone Routing Protocol January 2001
* Does the protocol have dependence on a central entity?
(if so, how?)
No. IERP is a fully distributed protocol.
* Does the protocol function reactively? (if so, how?)
Yes. A route query is initiated, on demand, when a node requires
routing information that is not immediately available in its
routing table. The route query propagates through the network,
using a special packet delivery service called "bordercasting".
Bordercasting leverages knowledge of local network topology to
direct route queries away from the source, thereby reducing
redundancy.
* Does the protocol function proactively? (if so, how?)
No.
* Does the protocol provide loop-free routing? (if so, how?)
Yes. In this draft, loop-freedom in the reactive route discovery
process is ensured by inspection of accumulated source routes.
For distributed distance vector approaches, loop-freedom can be
ensured by labeling queries (replies) with the source
(destination) address and locally unique sequence number.
Nodes that relay these messages can temporarily cache these
identifiers in order to identify and terminate loops.
* Does the protocol provide for sleep period operation? (if so, how?)
No. Sleep period operation is not addressed in this draft.
However, sleep period support can be included as needed.
* Does the protocol provide some form of security? (if so, how?)
No. It is assumed that security issues are adequately addressed
by the underlying protocols (IPsec, for example).
* Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?)
Yes. It is assumed that each node's network interface is
assigned a unique IP address.
Haas, Pearlman, Samar Expires July 2001 [Page v]
INTERNET DRAFT Interzone Routing Protocol January 2001
1. Introduction
The design of ad hoc network routing protocols is influenced by link
instability (due to node mobility) and limitations in available
bandwidth and transmission power. Traditional wired networks use
proactive routing protocols, like OSPF [7] and RIP [16] to maintain
up-to-date routes to all network nodes. More efficient proactive
routing protocols have been developed for ad hoc networks [1][5][8]
[9][15]. However, continuously tracking the frequent topology changes
in a practical ad hoc network can still produce an overwhelming amount
of control traffic. Even worse, most of the acquired route
information expires before it is ever used, making the proactive
control traffic a poor investment of bandwidth. In contrast, reactive
routing protocols [6][10][14] only initiate a global, query-based,
route discovery as routes are needed. While some delay is incurred in
route acquisition, the amount of overhead traffic is generally much
less than proactive routing protocols, because routing information is
not wasted. For this reason, reactive protocols are generally viewed
as being more suitable than proactive routing protocols for the power/
bandwidth limited mobile ad hoc network.
Although a global proactive routing protocol may overwhelm an ad hoc
network's resources, a LIMITED SCOPE proactive routing protocol can be
used to the advantage of a global reactive routing protocol. This
hybrid routing approach forms the basis for the Zone Routing Protocol
(ZRP) framework [4].
The cost for each node to proactively track the topology of its
surrounding R-hop neighborhood (routing zone) can be justified by
improved route discovery efficiency and more effective route
maintenance [11][12]. Routes to local destinations are immediately
available, avoiding route discoveries. When the global route
discovery is needed, the routing zones can be used to efficiently
guide route queries outwards through bordercasting [2], rather than
blindly relaying queries from neighbor to neighbor. The proactive
maintenance of routing zones also helps improve the quality and
survivability of discovered routes, by making them more robust to
changes in network topology. Once routes have been discovered,
routing zone offers enhanced, real-time, route maintenance. Link
failures can be bypassed by multiple hop paths within the routing
zone. Similarly, suboptimal route segments can be identified and
traffic re-routed along shorter paths.
Haas, Pearlman, Samar Expires July 2001 [Page 1]
INTERNET DRAFT Interzone Routing Protocol January 2001
Within the context of the ZRP, we refer to the globally reactive
routing component as the Interzone Routing Protocol (IERP). The IERP
is not a specific routing protocol. Rather, it is a family of
reactive routing protocols that offer enhanced route discovery and
route maintenance services based on local connectivity monitored by
the proactive Intrazone Routing Protocol (IARP) [3]. In this document,
we provide an example IERP implementation. In addition, we provide a
set of basic guidelines which can be used to convert an existing
proactive routing protocol to an IARP.
2. On Demand Route Discovery and the IntErzone Routing Protocol (IERP)
The reactive route discovery process consists of two phases: the route
request phase and the route reply phase. The route request phase is
initiated when a node requires a route to a destination, but does not
have the route stored in its route table. This query source issues a
route request packet and sends this packet to each of its neighbors.
When a node with an active route to the query destination receives the
request, it may respond with a reply. Otherwise, it forwards the
request packet to its neighbors. Subsequent copies of the route
request are considered to be redundant and are discarded.
When a queried node can provide a route to the destination, a reply
containing information about the discovered route is sent back to the
query source. In order to relay the reply, the request needs to
accumulate route information as it progresses through the network.
Before forwarding a query packet, a node appends its address and
relevant node/link metrics to the packet. When a query packet reaches
the destination, the sequence of recorded nodes represents a route
from the source to the destination. This route may be reversed and
used to send the reply back to the query source. Transmission
resources can be saved during the route request phase by distributing
previous hop information among the intermediate nodes, instead of
appending node addresses to increasingly longer packets. A similar
approach can be used during the reply phase. The query source may
receive an entire source route to the query destination, or each route
node can record the next-hop address to the destination in its routing
table.
A route request broadcast traverses all network links, allowing any
reachable destination to be discovered. However, the undirected
nature of broadcasting results in redundant coverage. Nodes are sent
copies of the same route request by each neighbor. An optimal probing
mechanism would direct the query outward, away from the query source
and away from regions that have already been covered by the query.
Haas, Pearlman, Samar Expires July 2001 [Page 2]
INTERNET DRAFT Interzone Routing Protocol January 2001
A hybrid routing protocol can provide directed query propagation by
exploiting knowledge of routing zone topology. When a node processes
a route request through its route cache, it is effectively responding
on behalf of its routing zone. As the routing is effectively covered,
the routing zone nodes no longer need to be explicitly interrogated.
Instead, the route request is "bordercast" to the routing zone's
peripheral nodes*, along multicast trees constructed from the known
routing zone topology. Redundant query coverage is minimized by
pruning tree branches ending in the routing zones of previously
queried nodes. Bordercasting and zone-based query control are
described in the Bordercast Resolution Protocol (BRP) specification
[2].
For a routing zone radius of one hop, bordercasting degenerates
into flood searching. Increasing the routing zone radius improves
route discovery efficiency. However, this requires additional
proactive traffic to maintain a current view of the larger routing
zone. The tradeoff between routing zone maintenance and route
discovery efficiency lies at the heart of the hybrid ZRP framework
[4].
* Peripheral nodes are those routing zone members that mark the edge
of the routing zone. In the case of uniform zone radii, the
peripheral nodes of an r-hop routing zone are those nodes which lie
at a minimum distance of r hops.
3. Routing Zone Based Route Maintenance
After a route is acquired, knowledge of the local topology can be used
to bypass link failures and sub-optimal route segments. The resulting
increase in route lifetime and reduction in route length translates to
a more stable, lower latency, higher throughput network application.
When neighboring nodes in a route move out of direct radio contact,
the resulting link failure interrupts data flow across the route. For
a purely reactive routing protocol, any routes that include the broken
link immediately fail. To maintain end-to-end connectivity, a new
route discovery / repair would have to be initiated. Until a
replacement route or route segment is discovered, incoming data
packets are either delayed or dropped, degrading application
performance.
Because the routing zone provides a node with a view beyond its own
neighborhood, many link failures can be instantly bypassed. As long
as the former neighbor remains within the routing zone, incoming data
packets can be redirected around a broken link, through an active
multi-hop path to the former neighbor.
Haas, Pearlman, Samar Expires July 2001 [Page 3]
INTERNET DRAFT Interzone Routing Protocol January 2001
Just as a route's nodes may move apart, they may also move closer
together. This provides an opportunity for routes to be shortened.
When the identity of a route's downstream nodes is known, as in the
case of source routes, a node can check if any "shortcuts" exist
through its routing zone. Some degree of proactive route shortening
can be achieved simply by tracking neighbor connectivity (routing
zone of radius 1 hop). By examining the packet's source route, a
relay can determine the closest node to the destination that is also
a neighbor. In some cases, a multiple hop segment of the route can
be replaced by a single hop. Route shortening can be extended to
larger routing zones, providing earlier opportunities to redirect
traffic along a wider array of shorter alternate segments. Relaying
nodes make locally optimal decisions, selecting the path that reaches
the destination in the fewest hops.
4. IERP Conversion Guidelines
The following guidelines can be used to convert an existing
reactive routing protocol to an IERP, without compromising the
defining features of the base routing protocol.
- Any local proactive route updates and neighbor advertisements
should be disabled, since this functionality is provided by IARP.
- IERP must support the importation of IARP routes into its own
routing table and support route lookups into the IARP routing
table.
- Advanced route maintenance techniques such as on-line route
repair and route shortening may be employed.
- The broadcast() of ROUTE REQUEST packets should be replaced with
with a call to the bordercast() service, as provided by the BRP.
- Redundant query termination (i.e. flood control) mechanisms must
be disabled. Redundant query control is handled by BRP.
However, IERP may discard ROUTE REQUESTS based on other criteria,
such as successful route discovery, exceeded QoS metrics,
expired TTL (limited depth search), etc.
- ROUTE REQUEST broadcast jitter must be disabled. This service
is provided by BRP.
Haas, Pearlman, Samar Expires July 2001 [Page 4]
INTERNET DRAFT Interzone Routing Protocol January 2001
5. Implementation Example - Reactive Source Routing
This example IERP demonstrates the integration of bordercast route
discovery and routing zone based route maintenance in a source route
reactive routing protocol. To highlight the role of the routing zone
services, the implementation of the underlying reactive routing has
been kept simple. More advanced features, such as diversity
injection [13], expanding ring search, route metric collection, etc.
are compatible with the routing zone services and may be added as
desired.
When a node has no valid route to forward a data packet, it
launches a route discovery, probing the network via bordercast
ROUTE_REQUST packets. When a node receives a ROUTE_REQUEST packet,
it appends its IP address along with metrics for the link on which
the packet was received. It then checks its Routing Tables for
a valid route to the query destination. If no valid route is
found, the node relays the ROUTE_REQUEST to the "downstream"
neighbors identified by the bordercast service (provided by the
Bordercast Resolution Protocol (BRP)). If a valid route to the
query destination is known, then the route is appended to the
ROUTE_REQUEST's accumulated route. The complete route is copied
to a ROUTE_REPLY packet. The ROUTE_REPLY is forwarded back to
the query source, by IERP, along the reversed accumulated route.
IERP also leverages the known routing zone topology to support
local proactive route maintenance. When a node's IARP detects a
change in its routing zone connectivity, the IERP is notified and
proceeds to review the status of its routes. For each IERP route,
the node identifies an alternate path through its routing zone
that minimizes the distance to the destination. This serves to
bypass failed links and sub-optimal route segments. The updated
routes are then saved in the IERP routing table,
Haas, Pearlman, Samar Expires July 2001 [Page 5]
INTERNET DRAFT Interzone Routing Protocol January 2001
A. Packet Format
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Node Ptr | RESERVED |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query ID | R E S E R V E D |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query/Route Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -+-
| Intermediate Node (1) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Intermediate Node (2) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| | route
\| |/ |
\ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| |
| Intermediate Node (N) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Query/Route Destination Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -+-
Field Description:
* Type (char) (8 bits)
Identifies the type of IERP packet. The current version
of IERP contains two packet types:
ROUTE_REQUEST:
Request for a route to the Query Destination.
The ROUTE_REQUEST records the path that it
has traveled from the Query Source.
ROUTE_REPLY:
Response to a ROUTE_REQUEST packet, issued by
the node that discovers a route to the Query
Destination, and sent back to the Query Source.
* Length (char) (8 bits)
Length of the packet, in multiples of 32 bit words.
* Node Pointer (char) (8 bits)
Index into the route (see below) corresponding to the
node that has just received, or is next to receive,
this packet.
Haas, Pearlman, Samar Expires July 2001 [Page 6]
INTERNET DRAFT Interzone Routing Protocol January 2001
* Query ID (unsigned int) (16 bits)
Sequence number which, along with the Query Source Address
(see below) uniquely identifies any ROUTE_REQUEST in the
network.
* Query/Route Source Address (node_id) (32 bits)
IP address of the node that initiates the ROUTE_REQUEST.
In subsequent stages, this corresponds to the IP address
of the discovered route's source node.
* Query/Route Destination Address (node_id) (32 bits)
IP address to be located during the ROUTE_REQUEST
phase. In subsequent stages, this field contains the IP
address of the discovered route's destination node.
* Route (node_id) (N * 32 bits)
Variable length field that contains the recorded IP
addresses of nodes along the path traveled by this
ROUTE_REQUEST packet from the Query Source. After a
route to the Query Destination has been discovered,
this set of IP addresses provides a specification of
the route between the Route Source and Route Destination.
B. Data Structures
B.1 IARP Routing Table (See IARP Description)
B.2 IERP Routing Table
+-----------------------|--------------------------------+
| Dest | Subnet | Route | Route |
| Addr | Mask | | Metrics |
| (node_id) | (node_id) | (node_id list) | (metric list) |
|-----------+-----------|----------------+---------------|
| | | | |
|-----------+-----------|----------------+---------------|
| | | | |
|-----------+-----------|----------------+---------------|
| | | | |
+-----------------------|--------------------------------+
Haas, Pearlman, Samar Expires July 2001 [Page 7]
INTERNET DRAFT Interzone Routing Protocol January 2001
C. Interfaces
C.1 Higher Layer (N/A)
C.2 Lower Layer (BRP)
C.2.1 Deliver(packet,BRP_cache_ID)
Used by BRP to deliver packet to IERP.
C.3 Lower Layer (IP)
C.3.1 Deliver(packet)
Used by IP to deliver packet to IARP.
C.4 IARP
C.4.1 IARP_updated()
Notifies IERP that the routing zone connectivity
has changed.
C.5 ICMP
C.5.1 Initiate_Route_Discovery(dest)
Initiates route discovery for "dest" when no route
to "dest" is available in the routing table.
D. State Machine
This implementation of IERP consists of only one state (IDLE).
Therefore, no state transitions need to be specified. IERP
immediately acts upon an event and then returns back to the
IDLE state.
Note: 1) X is used as a label for the node running this state
machine.
D.1
Event: IARP reports an update to routing zone connectivity.
Action: For each route in X's IERP routing table, compute a
path to each downstream node (based on the IARP
routing table.) Identify the computed path that
minimizes the route length, and update the IERP route
with this path.
Haas, Pearlman, Samar Expires July 2001 [Page 8]
INTERNET DRAFT Interzone Routing Protocol January 2001
D.2
Event: A ROUTE_REQUEST packet is received with a destination
that appears within X's routing zone.
Action: The packet's accumulated route information (for the
source) is recorded in X's Routing Table and Temporary
Query Cache. The accumulated route is replaced by
X's address and any accumulated route metrics are
updated and compressed.
X copies the ROUTE_REQUEST packet's contents to a
ROUTE_REPLY packet. The ROUTE_REPLY packet is
returned to the query source, along the reversed
accumulated route.
D.3
Event: A ROUTE_REQUEST packet is received with a destination
that DOES NOT appear within X's routing zone.
Action: X adds its address to the accumulated route and the
ROUTE_REQUEST packet is bordercast().
D.4
Event: A ROUTE_REPLY packet is received.
Action: The packet's accumulated route information (for the
destination) is recorded in X's Routing Table. X
adds its address to the accumulated route and adds
metrics for the downstream (toward the destination)
link to the accumulated metrics. If X is not the
query source, then X forwards the message toward the
source (directly through IP), along a path selected
from the Temporary Query Cache (i.e. based on
Diversity Injection).
E. Pseudocode Implementation
We define two complimentary operations on packets:
extract(packet) and load(packet)
extract(packet)
extracts the fields of the IERP packet to the following
variables: {type, length, node_ptr, query_id,
source, route, dest}
load(packet)
loads the values of the aforementioned variables into
the fields of the IERP packet.
load(packet) automatically computes the packet length
Haas, Pearlman, Samar Expires July 2001 [Page 9]
INTERNET DRAFT Interzone Routing Protocol January 2001
E.1 IARP_updated()
// Perform route maintenance on each IERP route
for each dest (BELONGING TO) IERP_Routing Table
{
for each route (BELONGING TO) IERP_Routing_Table[dest]
{
L = length(route);
min_dist = INF;
new_route = NULL;
// Lookup the IARP path to each node in route.
// Update the IERP route using the IARP path
// that minimizes the distance to the
// IERP route's destination.
for j = 1:L
{
node = route(j);
route_tail = route(j+1:L);
IARP_path = IARP_Routing_Table(node).route;
new_route = IARP_path + route_tail;
if(hop_count(IARP_path + route_tail) < min_dist)
{
new_route = IARP_path + route_tail;
min_dist = hop_count(new_route);
}
}
}
}
// Import IARP routes to IERP, so that all known routes are
// centrally available
import(IERP_Routing_Table, IARP_Routing_Table);
E.2 Initiate_Route_Discovery(dest)
// ROUTE_REQUEST is initialized and sent down to BRP
// to launch bordercast
source = MY_ID
query_id = MY_QUERY_ID++;
type = ROUTE_REQUEST;
route = NULL;
node_ptr = 0;
load (packet);
// Replaces traditional "broadcast()"
bordercast(packet, NULL);
Haas, Pearlman, Samar Expires July 2001 [Page 10]
INTERNET DRAFT Interzone Routing Protocol January 2001
E.3 Deliver(packet, BRP_cache_ID)
extract(packet);
switch(type)
{
case: ROUTE_REQUEST
if ((EXISTS) IERP_Routing_Table[dest].route)
{
// Append discovered route to accumulated route
// and send reply back to the source.
route += IERP_Routing_Table[dest].route
type = ROUTE_REPLY;
load(packet);
send(packet,next_hop,IP);
}
else
{
// If route to destination is not available, then
// append MY_ID to accumulated route and continue
// to forward ROUTE_REQUEST packet.
route += MY_ID;
node_ptr++;
load(packet);
// Replaces traditional "broadcast()"
bordercast(packet, BRP_cache_ID);
}
break;
case: ROUTE_REPLY
// Extract route from packet and record it in the
// IERP Routing Table
route_tail = route(current_hop_ptr : length(route)):
add(IERP_Routing_Table[dest], route_tail);
// Forward ROUTE_REPLY until it reaches source
if(MY_ID != source)
{
node_ptr--;
next_hop = route(node_ptr);
load(packet);
send((packet,next_hop),IP);
}
break;
}
Haas, Pearlman, Samar Expires July 2001 [Page 11]
INTERNET DRAFT Interzone Routing Protocol January 2001
5. References
[1] Garcia-Luna-Aceves, J.J. and Spohn, M., "Efficient Routing in
Packet-Radio Networks Using Link-State Information,"
WCNC '99, September 1999.
[2] Haas, Z.J., Pearlman, M.R. and Samar, P., "Bordercast Resolution
Protocol (BRP)," IETF Internet Draft,
draft-ietf-manet-brp-00.txt, January 2001.
[3] Haas, Z.J., Pearlman, M.R. and Samar, P., "Intrazone Routing
Protocol (IARP)," IETF Internet Draft,
draft-ietf-manet-iarp-00.txt, January 2001.
[4] Haas, Z.J., Pearlman, M.R. and Samar, P., "Zone Routing Protocol
(ZRP)," IETF Internet Draft, draft-ietf-manet-zrp-04.txt,
January 2001.
[5] Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L.,
and Clausen T., "Optimized Link State Routing Protocol,"
IETF Internet Draft, draft-ietf-manet-olsr-03.txt,
November 2000.
[6] Johnson, D.B. and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc
Wireless Networks," in Mobile Computing, edited by T.
Imielinski and H. Korth, chapter 5, pp. 153-181,
Kluwer, 1996.
[7] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, RFC 2178,
July 1997.
[8] Murthy, S. and Garcia-Luna-Aceves, J.J., "An Efficient Routing
Protocol for Wireless Networks," MONET, vol. 1, no. 2,
pp. 183-197, October 1996.
[9] Ogier, R. "Efficient Routing Protocols for Packet-Radio Networks
Based on Tree Sharing," MoMUC '99, November 1999.
[10] Park, V.D. and Corson, M.S., "A Highly Adaptive Distributed
Routing Algorithm for Mobile Wireless Networks,"
IEEE INFOCOM'97, Kobe, Japan, 1997.
[11] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal
Configuration for the Zone Routing Protocol," IEEE JSAC,
August, 1999.
[12] Pearlman, M.R., Haas, Z.J. and S.I. Mir, "Using Routing Zones to
Support Route Maintenance in Ad Hoc Networks,"
IEEE WCNC 2000, Chicago, IL, Sept. 2000.
Haas, Pearlman, Samar Expires July 2001 [Page 12]
INTERNET DRAFT Interzone Routing Protocol January 2001
[13] Pearlman, M.R., Haas, Z.J., "Improving the Performance of Query-
Based Routing Protocols Through Diversity Injection,"
IEEE WCNC 1999, New Orleans, LA, Sept. 1999.
[14] Perkins, C.E. and Royer, E.M., "Ad Hoc On-Demand Distance
Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999
[15] Perkins, C.E. and Bhagwat, P., "Highly Dynamic
Destination-Sequenced Distance-Vector Routing (DSDV) for
Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994.
[16] Postel, J., "Internet Protocol," RFC 791, Sept. 1981.
Haas, Pearlman, Samar Expires July 2001 [Page 13]
INTERNET DRAFT Interzone Routing Protocol January 2001
Authors' Information
Zygmunt J. Haas
Wireless Networks Laboratory
323 Frank Rhodes Hall
School of Electrical Engineering
Cornell University
Ithaca, NY 14853
United States of America tel: (607) 255-3454, fax: (607) 255-9072
Email: haas@ee.cornell.edu
Marc R. Pearlman
389 Frank Rhodes Hall
School of Electrical Engineering
Cornell University
Ithaca, NY 14853
United States of America
tel: (607) 255-0236, fax: (607) 255-9072
Email: pearlman@ee.cornell.edu
Prince Samar
372 Frank Rhodes Hall
School of Electrical Engineering
Cornell University
Ithaca, NY 14853
United States of America
tel: (607) 255-9068, fax: (607) 255-9072
Email: samar@ee.cornell.edu
The MANET Working Group contacted through its chairs:
M. Scott Corson
Institute for Systems Research
University of Maryland College Park, MD 20742
(301) 405-6630
corson@isr.umd.edu
Joseph Macker
Information Technology Division
Naval Research Laboratory
Washington, DC 20375
(202) 767-2001
macker@itd.nrl.navy.mil
Haas, Pearlman, Samar Expires July 2001 [Page 14]
