draft-ietf-manet-zone-ierp-01.txt   draft-ietf-manet-zone-ierp-02.txt 
INTERNET-DRAFT Zygmunt J. Haas, Cornell University INTERNET-DRAFT Zygmunt J. Haas, Cornell University
Marc R. Pearlman, Cornell University Marc R. Pearlman, Cornell University
Prince Samar, Cornell University Prince Samar, Cornell University
Expires in six months on December 2001 June 2001 Expires in six months on January 2003 July 2002
The Interzone Routing Protocol (IERP) for Ad Hoc Networks The Interzone Routing Protocol (IERP) for Ad Hoc Networks
<draft-ietf-manet-zone-ierp-01.txt> <draft-ietf-manet-zone-ierp-02.txt>
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026, except the right to all provisions of Section 10 of RFC 2026, except the right to
produce derivative works is not granted. produce derivative works is not granted.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-Drafts. other groups may also distribute working documents as Internet-Drafts.
skipping to change at line 39 skipping to change at line 39
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
Abstract Abstract
This document describes the Interzone Routing Protocol (IERP), the This document describes the Interzone Routing Protocol (IERP), the
reactive routing component of the Zone Routing Protocol (ZRP). reactive routing component of the Zone Routing Protocol (ZRP).
IERP adapts existing reactive routing protocol implementations to IERP adapts existing reactive routing protocol implementations to
take advantage of the known topology of each node's surrounding take advantage of the known topology of each node's surrounding
r-hop neighborhood (routing zone), provided by the Intrazone R-hop neighborhood (routing zone), provided by the Intrazone
Routing Protocol (IARP). The availability of routing zone routes Routing Protocol (IARP). The availability of routing zone routes
allows IERP to suppress route queries for local destinations. allows IERP to suppress route queries for local destinations.
When a global route discovery is required, the routing zone based When a global route discovery is required, the routing zone based
bordercast service can be used to efficiently guide route queries bordercast service can be used to efficiently guide route queries
outward, rather than blindly relaying queries from neighbor to outward, rather than blindly relaying queries from neighbor to
neighbor. Once a route has been discovered, IERP can use routing neighbor. Once a route has been discovered, IERP can use routing
zones to automatically redirect data around failed links. zones to automatically redirect data around failed links.
Similarly, suboptimal route segments can be identified and traffic Similarly, suboptimal route segments can be identified and traffic
re-routed along shorter paths. re-routed along shorter paths.
Haas, Pearlman, Samar Expires December 2001 [Page i] Haas, Pearlman, Samar Expires January 2003 [Page i]
Contents Contents
Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Applicability Statement . . . . . . . . . . . . . . . . . . . iii Applicability Statement . . . . . . . . . . . . . . . . . . . iii
A. Networking Context . . . . . . . . . . . . . . . . . iii A. Networking Context . . . . . . . . . . . . . . . . . iii
B. Protocol Characteristics and Mechanisms . . . . . . . iii B. Protocol Characteristics and Mechanisms . . . . . . . iii
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1
skipping to change at line 81 skipping to change at line 81
B. Data Structures . . . . . . . . . . . . . . . . . . . . 7 B. Data Structures . . . . . . . . . . . . . . . . . . . . 7
C. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 8 C. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 8
D. State Machine . . . . . . . . . . . . . . . . . . . . . 8 D. State Machine . . . . . . . . . . . . . . . . . . . . . 8
E. Pseudocode Implementation . . . . . . . . . . . . . . . 9 E. Pseudocode Implementation . . . . . . . . . . . . . . . 9
6. References . . . . . . . . . . . . . . . . . . . . . . . . 12 6. References . . . . . . . . . . . . . . . . . . . . . . . . 12
Authors' Information . . . . . . . . . . . . . . . . . . . . . 14 Authors' Information . . . . . . . . . . . . . . . . . . . . . 14
MANET Contact Information . . . . . . . . . . . . . . . . . . . 14 MANET Contact Information . . . . . . . . . . . . . . . . . . . 14
Haas, Pearlman, Samar Expires December 2001 [Page ii] Haas, Pearlman, Samar Expires January 2003 [Page ii]
Applicability Statement Applicability Statement
A. Networking Context A. Networking Context
The Interzone Routing Protocol (IERP) is the global reactive The Interzone Routing Protocol (IERP) is the global reactive
routing component of the Zone Routing Protocol (ZRP). IERP routing component of the Zone Routing Protocol (ZRP). IERP
adapts existing reactive routing protocol implementations to adapts existing reactive routing protocol implementations to
take advantage of the known topology of each node's surrounding take advantage of the known topology of each node's surrounding
r-hop neighborhood (routing zone), provided by the Intrazone R-hop neighborhood (routing zone), provided by the Intrazone
Routing Protocol (IARP). The availability of routing zone routes Routing Protocol (IARP). The availability of routing zone routes
allows IERP to suppress route queries for local destinations. allows IERP to suppress route queries for local destinations.
When a global route discovery is required, the routing zone based When a global route discovery is required, the routing zone based
bordercast service [2] can be used to efficiently guide route bordercast service [2] can be used to efficiently guide route
queries outward, rather than blindly relaying queries from neighbor queries outward, rather than blindly relaying queries from neighbor
to neighbor. Once a route has been discovered, IERP can use to neighbor. Once a route has been discovered, IERP can use
routing zones to automatically redirect data around failed links. routing zones to automatically redirect data around failed links.
Similarly, suboptimal route segments can be identified and traffic Similarly, suboptimal route segments can be identified and traffic
re-routed along shorter paths. re-routed along shorter paths.
skipping to change at line 176 skipping to change at line 176
Yes. Each node is assumed to have a unique IP address (or set of Yes. Each node is assumed to have a unique IP address (or set of
unique IP addresses in the case of multiple interfaces). IERP unique IP addresses in the case of multiple interfaces). IERP
references all nodes/interfaces by their IP address. references all nodes/interfaces by their IP address.
* Does the protocol require link or neighbor status sensing * Does the protocol require link or neighbor status sensing
(if so, how?) (if so, how?)
No. No.
Haas, Pearlman, Samar Expires December 2001 [Page iv] Haas, Pearlman, Samar Expires January 2003 [Page iv]
* Does the protocol have dependence on a central entity? * Does the protocol have dependence on a central entity?
(if so, how?) (if so, how?)
No. IERP is a fully distributed protocol. No. IERP is a fully distributed protocol.
* Does the protocol function reactively? (if so, how?) * Does the protocol function reactively? (if so, how?)
Yes. A route query is initiated, on demand, when a node requires Yes. A route query is initiated, on demand, when a node requires
routing information that is not immediately available in its routing information that is not immediately available in its
routing table. The route query propagates through the network, routing table. The route query propagates through the network,
skipping to change at line 222 skipping to change at line 222
No. It is assumed that security issues are adequately addressed No. It is assumed that security issues are adequately addressed
by the underlying protocols (IPsec, for example). by the underlying protocols (IPsec, for example).
* Does the protocol provide support for utilizing multi-channel, * Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?) link-layer technologies? (if so, how?)
Yes. It is assumed that each node's network interface is Yes. It is assumed that each node's network interface is
assigned a unique IP address. assigned a unique IP address.
Haas, Pearlman, Samar Expires December 2001 [Page v] Haas, Pearlman, Samar Expires January 2003 [Page v]
1. Introduction 1. Introduction
The design of ad hoc network routing protocols is influenced by link The design of ad hoc network routing protocols is influenced by link
instability (due to node mobility) and limitations in available instability (due to node mobility) and limitations in available
bandwidth and transmission power. Traditional wired networks use bandwidth and transmission power. Traditional wired networks use
proactive routing protocols, like OSPF [7] and RIP [16] to maintain proactive routing protocols, like OSPF [7] and RIP [16] to maintain
up-to-date routes to all network nodes. More efficient proactive up-to-date routes to all network nodes. More efficient proactive
routing protocols have been developed for ad hoc networks [1][5][8] routing protocols have been developed for ad hoc networks [1][5][8]
[9][15]. However, continuously tracking the frequent topology changes [9][15]. However, continuously tracking the frequent topology changes
skipping to change at line 267 skipping to change at line 267
guide route queries outwards through bordercasting [2], rather than guide route queries outwards through bordercasting [2], rather than
blindly relaying queries from neighbor to neighbor. The proactive blindly relaying queries from neighbor to neighbor. The proactive
maintenance of routing zones also helps improve the quality and maintenance of routing zones also helps improve the quality and
survivability of discovered routes, by making them more robust to survivability of discovered routes, by making them more robust to
changes in network topology. Once routes have been discovered, changes in network topology. Once routes have been discovered,
routing zone offers enhanced, real-time, route maintenance. Link routing zone offers enhanced, real-time, route maintenance. Link
failures can be bypassed by multiple hop paths within the routing failures can be bypassed by multiple hop paths within the routing
zone. Similarly, suboptimal route segments can be identified and zone. Similarly, suboptimal route segments can be identified and
traffic re-routed along shorter paths. traffic re-routed along shorter paths.
Haas, Pearlman, Samar Expires December 2001 [Page 1] Haas, Pearlman, Samar Expires January 2003 [Page 1]
Within the context of the ZRP, we refer to the globally reactive Within the context of the ZRP, we refer to the globally reactive
routing component as the Interzone Routing Protocol (IERP). The IERP routing component as the Interzone Routing Protocol (IERP). The IERP
is not a specific routing protocol. Rather, it is a family of is not a specific routing protocol. Rather, it is a family of
reactive routing protocols that offer enhanced route discovery and reactive routing protocols that offer enhanced route discovery and
route maintenance services based on local connectivity monitored by route maintenance services based on local connectivity monitored by
the proactive Intrazone Routing Protocol (IARP) [3]. In this document, the proactive Intrazone Routing Protocol (IARP) [3]. In this document,
we provide an example IERP implementation. In addition, we provide a we provide an example IERP implementation. In addition, we provide a
set of basic guidelines which can be used to convert an existing set of basic guidelines which can be used to convert an existing
proactive routing protocol to an IARP. reactive routing protocol to an IERP.
2. On Demand Route Discovery and the IntErzone Routing Protocol (IERP) 2. On Demand Route Discovery and the IntErzone Routing Protocol (IERP)
The reactive route discovery process consists of two phases: the route The reactive route discovery process consists of two phases: the route
request phase and the route reply phase. The route request phase is 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 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 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. 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 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, it may respond with a reply. Otherwise, it forwards the
skipping to change at line 314 skipping to change at line 314
node can record the next-hop address to the destination in its routing node can record the next-hop address to the destination in its routing
table. table.
A route request broadcast traverses all network links, allowing any A route request broadcast traverses all network links, allowing any
reachable destination to be discovered. However, the undirected reachable destination to be discovered. However, the undirected
nature of broadcasting results in redundant coverage. Nodes are sent nature of broadcasting results in redundant coverage. Nodes are sent
copies of the same route request by each neighbor. An optimal probing copies of the same route request by each neighbor. An optimal probing
mechanism would direct the query outward, away from the query source mechanism would direct the query outward, away from the query source
and away from regions that have already been covered by the query. and away from regions that have already been covered by the query.
Haas, Pearlman, Samar Expires December 2001 [Page 2] Haas, Pearlman, Samar Expires January 2003 [Page 2]
A hybrid routing protocol can provide directed query propagation by A hybrid routing protocol can provide directed query propagation by
exploiting knowledge of routing zone topology. When a node processes exploiting knowledge of routing zone topology. When a node processes
a route request through its route cache, it is effectively responding a route request through its route cache, it is effectively responding
on behalf of its routing zone. As the routing is effectively covered, on behalf of its routing zone. As the routing zone is effectively
the routing zone nodes no longer need to be explicitly interrogated. covered, the routing zone nodes no longer need to be explicitly
Instead, the route request is "bordercast" to the routing zone's interrogated. Instead, the route request is "bordercast" to the
peripheral nodes*, along multicast trees constructed from the known routing zone's peripheral nodes*, along multicast trees constructed
routing zone topology. Redundant query coverage is minimized by from the known routing zone topology. Redundant query coverage is
pruning tree branches ending in the routing zones of previously minimized by pruning tree branches ending in the routing zones of
queried nodes. Bordercasting and zone-based query control are previously queried nodes. Bordercasting and zone-based query control
described in the Bordercast Resolution Protocol (BRP) specification are described in the Bordercast Resolution Protocol (BRP)
[2]. specification [2].
For a routing zone radius of one hop, bordercasting degenerates For a routing zone radius of one hop, bordercasting degenerates
into flood searching. Increasing the routing zone radius improves into flood searching. Increasing the routing zone radius improves
route discovery efficiency. However, this requires additional route discovery efficiency. However, this requires additional
proactive traffic to maintain a current view of the larger routing proactive traffic to maintain a current view of the larger routing
zone. The tradeoff between routing zone maintenance and route zone. The tradeoff between routing zone maintenance and route
discovery efficiency lies at the heart of the hybrid ZRP framework discovery efficiency lies at the heart of the hybrid ZRP framework
[4]. [4].
* Peripheral nodes are those routing zone members that mark the edge * Peripheral nodes are those routing zone members that mark the edge
skipping to change at line 363 skipping to change at line 363
replacement route or route segment is discovered, incoming data replacement route or route segment is discovered, incoming data
packets are either delayed or dropped, degrading application packets are either delayed or dropped, degrading application
performance. performance.
Because the routing zone provides a node with a view beyond its own Because the routing zone provides a node with a view beyond its own
neighborhood, many link failures can be instantly bypassed. As long neighborhood, many link failures can be instantly bypassed. As long
as the former neighbor remains within the routing zone, incoming data as the former neighbor remains within the routing zone, incoming data
packets can be redirected around a broken link, through an active packets can be redirected around a broken link, through an active
multi-hop path to the former neighbor. multi-hop path to the former neighbor.
Haas, Pearlman, Samar Expires December 2001 [Page 3] Haas, Pearlman, Samar Expires January 2003 [Page 3]
Just as a route's nodes may move apart, they may also move closer Just as a route's nodes may move apart, they may also move closer
together. This provides an opportunity for routes to be shortened. together. This provides an opportunity for routes to be shortened.
When the identity of a route's downstream nodes is known, as in the 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 case of source routes, a node can check if any "shortcuts" exist
through its routing zone. Some degree of proactive route shortening through its routing zone. Some degree of proactive route shortening
can be achieved simply by tracking neighbor connectivity (routing can be achieved simply by tracking neighbor connectivity (routing
zone of radius 1 hop). By examining the packet's source route, a 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 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 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 be replaced by a single hop. Route shortening can be extended to
skipping to change at line 407 skipping to change at line 407
- Redundant query termination (i.e. flood control) mechanisms must - Redundant query termination (i.e. flood control) mechanisms must
be disabled. Redundant query control is handled by BRP. be disabled. Redundant query control is handled by BRP.
However, IERP may discard ROUTE REQUESTS based on other criteria, However, IERP may discard ROUTE REQUESTS based on other criteria,
such as successful route discovery, exceeded QoS metrics, such as successful route discovery, exceeded QoS metrics,
expired TTL (limited depth search), etc. expired TTL (limited depth search), etc.
- ROUTE REQUEST broadcast jitter must be disabled. This service - ROUTE REQUEST broadcast jitter must be disabled. This service
is provided by BRP. is provided by BRP.
Haas, Pearlman, Samar Expires December 2001 [Page 4] Haas, Pearlman, Samar Expires January 2003 [Page 4]
5. Implementation Example - Reactive Source Routing 5. Implementation Example - Reactive Source Routing
This example IERP demonstrates the integration of bordercast route This example IERP demonstrates the integration of bordercast route
discovery and routing zone based route maintenance in a source route discovery and routing zone based route maintenance in a source route
reactive routing protocol. To highlight the role of the routing zone reactive routing protocol. To highlight the role of the routing zone
services, the implementation of the underlying reactive routing has services, the implementation of the underlying reactive routing has
been kept simple. More advanced features, such as diversity been kept simple. More advanced features, such as diversity
injection [13], expanding ring search, route metric collection, etc. injection [13], expanding ring search, route metric collection, etc.
are compatible with the routing zone services and may be added as are compatible with the routing zone services and may be added as
skipping to change at line 441 skipping to change at line 441
to a ROUTE_REPLY packet. The ROUTE_REPLY is forwarded back to to a ROUTE_REPLY packet. The ROUTE_REPLY is forwarded back to
the query source, by IERP, along the reversed accumulated route. the query source, by IERP, along the reversed accumulated route.
IERP also leverages the known routing zone topology to support IERP also leverages the known routing zone topology to support
local proactive route maintenance. When a node's IARP detects a local proactive route maintenance. When a node's IARP detects a
change in its routing zone connectivity, the IERP is notified and change in its routing zone connectivity, the IERP is notified and
proceeds to review the status of its routes. For each IERP route, proceeds to review the status of its routes. For each IERP route,
the node identifies an alternate path through its routing zone the node identifies an alternate path through its routing zone
that minimizes the distance to the destination. This serves to that minimizes the distance to the destination. This serves to
bypass failed links and sub-optimal route segments. The updated bypass failed links and sub-optimal route segments. The updated
routes are then saved in the IERP routing table, routes are then saved in the IERP routing table.
Haas, Pearlman, Samar Expires December 2001 [Page 5] Haas, Pearlman, Samar Expires January 2003 [Page 5]
A. Packet Format A. Packet Format
1 2 3 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 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 | | Type | Length | Node Ptr | RESERVED |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query ID | R E S E R V E D | | Query ID | R E S E R V E D |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query/Route Source Address | | Query/Route Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -+-
skipping to change at line 492 skipping to change at line 492
Destination, and sent back to the Query Source. Destination, and sent back to the Query Source.
* Length (char) (8 bits) * Length (char) (8 bits)
Length of the packet, in multiples of 32 bit words. Length of the packet, in multiples of 32 bit words.
* Node Pointer (char) (8 bits) * Node Pointer (char) (8 bits)
Index into the route (see below) corresponding to the Index into the route (see below) corresponding to the
node that has just received, or is next to receive, node that has just received, or is next to receive,
this packet. this packet.
Haas, Pearlman, Samar Expires December 2001 [Page 6] Haas, Pearlman, Samar Expires January 2003 [Page 6]
* Query ID (unsigned int) (16 bits) * Query ID (unsigned int) (16 bits)
Sequence number which, along with the Query Source Address Sequence number which, along with the Query Source Address
(see below) uniquely identifies any ROUTE_REQUEST in the (see below) uniquely identifies any ROUTE_REQUEST in the
network. network.
* Query/Route Source Address (node_id) (32 bits) * Query/Route Source Address (node_id) (32 bits)
IP address of the node that initiates the ROUTE_REQUEST. IP address of the node that initiates the ROUTE_REQUEST.
In subsequent stages, this corresponds to the IP address In subsequent stages, this corresponds to the IP address
of the discovered route's source node. of the discovered route's source node.
skipping to change at line 518 skipping to change at line 518
* Route (node_id) (N * 32 bits) * Route (node_id) (N * 32 bits)
Variable length field that contains the recorded IP Variable length field that contains the recorded IP
addresses of nodes along the path traveled by this addresses of nodes along the path traveled by this
ROUTE_REQUEST packet from the Query Source. After a ROUTE_REQUEST packet from the Query Source. After a
route to the Query Destination has been discovered, route to the Query Destination has been discovered,
this set of IP addresses provides a specification of this set of IP addresses provides a specification of
the route between the Route Source and Route Destination. the route between the Route Source and Route Destination.
B. Data Structures B. Data Structures
B.1 IARP Routing Table (See IARP Description) B.1 IARP Routing Table (See IARP Description [3])
B.2 IERP Routing Table B.2 IERP Routing Table
+-----------------------|--------------------------------+ +-----------------------|--------------------------------+
| Dest | Subnet | Route | Route | | Dest | Subnet | Route | Route |
| Addr | Mask | | Metrics | | Addr | Mask | | Metrics |
| (node_id) | (node_id) | (node_id list) | (metric list) | | (node_id) | (node_id) | (node_id list) | (metric list) |
|-----------+-----------|----------------+---------------| |-----------+-----------|----------------+---------------|
| | | | | | | | | |
|-----------+-----------|----------------+---------------| |-----------+-----------|----------------+---------------|
| | | | | | | | | |
|-----------+-----------|----------------+---------------| |-----------+-----------|----------------+---------------|
| | | | | | | | | |
+-----------------------|--------------------------------+ +-----------------------|--------------------------------+
Haas, Pearlman, Samar Expires December 2001 [Page 7] Haas, Pearlman, Samar Expires January 2003 [Page 7]
C. Interfaces C. Interfaces
C.1 Higher Layer (N/A) C.1 Higher Layer (N/A)
C.2 Lower Layer (BRP) C.2 Lower Layer (BRP)
C.2.1 Deliver(packet,BRP_cache_ID) C.2.1 Deliver(packet,BRP_cache_ID)
Used by BRP to deliver packet to IERP. Used by BRP to deliver packet to IERP.
C.3 Lower Layer (IP) C.3 Lower Layer (IP)
C.3.1 Deliver(packet) C.3.1 Deliver(packet)
Used by IP to deliver packet to IARP. Used by IP to deliver packet to IERP.
C.4 IARP C.4 IARP
C.4.1 IARP_updated() C.4.1 IARP_updated()
Notifies IERP that the routing zone connectivity Notifies IERP that the routing zone connectivity
has changed. has changed.
C.5 ICMP C.5 ICMP
C.5.1 Initiate_Route_Discovery(dest) C.5.1 Initiate_Route_Discovery(dest)
Initiates route discovery for "dest" when no route Initiates route discovery for "dest" when no route
to "dest" is available in the routing table. to "dest" is available in the routing table.
skipping to change at line 576 skipping to change at line 576
D.1 D.1
Event: IARP reports an update to routing zone connectivity. Event: IARP reports an update to routing zone connectivity.
Action: For each route in X's IERP routing table, compute a Action: For each route in X's IERP routing table, compute a
path to each downstream node (based on the IARP path to each downstream node (based on the IARP
routing table.) Identify the computed path that routing table.) Identify the computed path that
minimizes the route length, and update the IERP route minimizes the route length, and update the IERP route
with this path. with this path.
Haas, Pearlman, Samar Expires December 2001 [Page 8] Haas, Pearlman, Samar Expires January 2003 [Page 8]
D.2 D.2
Event: A ROUTE_REQUEST packet is received with a destination Event: A ROUTE_REQUEST packet is received with a destination
that appears within X's routing zone. that appears within X's routing zone.
Action: The packet's accumulated route information (for the Action: The packet's accumulated route information (for the
source) is recorded in X's Routing Table and Temporary source) is recorded in X's Routing Table and Temporary
Query Cache. The accumulated route is replaced by Query Cache. The accumulated route is replaced by
X's address and any accumulated route metrics are X's address and any accumulated route metrics are
updated and compressed. updated and compressed.
skipping to change at line 627 skipping to change at line 627
extract(packet) extract(packet)
extracts the fields of the IERP packet to the following extracts the fields of the IERP packet to the following
variables: {type, length, node_ptr, query_id, variables: {type, length, node_ptr, query_id,
source, route, dest} source, route, dest}
load(packet) load(packet)
loads the values of the aforementioned variables into loads the values of the aforementioned variables into
the fields of the IERP packet. the fields of the IERP packet.
load(packet) automatically computes the packet length load(packet) automatically computes the packet length
Haas, Pearlman, Samar Expires December 2001 [Page 9] Haas, Pearlman, Samar Expires January 2003 [Page 9]
E.1 IARP_updated() E.1 IARP_updated()
// Perform route maintenance on each IERP route // Perform route maintenance on each IERP route
for each dest (BELONGING TO) IERP_Routing Table for each dest (BELONGING TO) IERP_Routing Table
{ {
for each route (BELONGING TO) IERP_Routing_Table[dest] for each route (BELONGING TO) IERP_Routing_Table[dest]
{ {
L = length(route); L = length(route);
min_dist = INF; min_dist = INF;
new_route = NULL; new_route = NULL;
skipping to change at line 677 skipping to change at line 677
query_id = MY_QUERY_ID++; query_id = MY_QUERY_ID++;
type = ROUTE_REQUEST; type = ROUTE_REQUEST;
route = NULL; route = NULL;
node_ptr = 0; node_ptr = 0;
load (packet); load (packet);
// Replaces traditional "broadcast()" // Replaces traditional "broadcast()"
bordercast(packet, NULL); bordercast(packet, NULL);
Haas, Pearlman, Samar Expires December 2001 [Page 10] Haas, Pearlman, Samar Expires January 2003 [Page 10]
E.3 Deliver(packet, BRP_cache_ID) E.3 Deliver(packet, BRP_cache_ID)
extract(packet); extract(packet);
switch(type) switch(type)
{ {
case: ROUTE_REQUEST case: ROUTE_REQUEST
if ((EXISTS) IERP_Routing_Table[dest].route) if ((EXISTS) IERP_Routing_Table[dest].route)
{ {
// Append discovered route to accumulated route // Append discovered route to accumulated route
// and send reply back to the source. // and send reply back to the source.
skipping to change at line 728 skipping to change at line 728
{ {
node_ptr--; node_ptr--;
next_hop = route(node_ptr); next_hop = route(node_ptr);
load(packet); load(packet);
send((packet,next_hop),IP); send((packet,next_hop),IP);
} }
break; break;
} }
Haas, Pearlman, Samar Expires December 2001 [Page 11] Haas, Pearlman, Samar Expires January 2003 [Page 11]
5. References 5. References
[1] Garcia-Luna-Aceves, J.J. and Spohn, M., "Efficient Routing in [1] Garcia-Luna-Aceves, J.J. and Spohn, M., "Efficient Routing in
Packet-Radio Networks Using Link-State Information," Packet-Radio Networks Using Link-State Information,"
WCNC '99, September 1999. WCNC '99, September 1999.
[2] Haas, Z.J., Pearlman, M.R. and Samar, P., "Bordercast Resolution [2] Haas, Z.J., Pearlman, M.R. and Samar, P., "Bordercast Resolution
Protocol (BRP)," IETF Internet Draft, Protocol (BRP)," IETF Internet Draft,
draft-ietf-manet-brp-01.txt, June 2001. draft-ietf-manet-brp-02.txt, July 2002.
[3] Haas, Z.J., Pearlman, M.R. and Samar, P., "Intrazone Routing [3] Haas, Z.J., Pearlman, M.R. and Samar, P., "Intrazone Routing
Protocol (IARP)," IETF Internet Draft, Protocol (IARP)," IETF Internet Draft,
draft-ietf-manet-iarp-01.txt, June 2001. draft-ietf-manet-iarp-02.txt, July 2002.
[4] Haas, Z.J., Pearlman, M.R. and Samar, P., "Zone Routing Protocol [4] Haas, Z.J., Pearlman, M.R. and Samar, P., "Zone Routing Protocol
(ZRP)," IETF Internet Draft, draft-ietf-manet-zrp-04.txt, (ZRP)," IETF Internet Draft, draft-ietf-manet-zrp-04.txt,
January 2001. July 2002.
[5] Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L., [5] Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L.,
and Clausen T., "Optimized Link State Routing Protocol," and Clausen T., "Optimized Link State Routing Protocol,"
IETF Internet Draft, draft-ietf-manet-olsr-03.txt, IETF Internet Draft, draft-ietf-manet-olsr-03.txt,
November 2000. November 2000.
[6] Johnson, D.B. and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc [6] Johnson, D.B. and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc
Wireless Networks," in Mobile Computing, edited by T. Wireless Networks," in Mobile Computing, edited by T.
Imielinski and H. Korth, chapter 5, pp. 153-181, Imielinski and H. Korth, chapter 5, pp. 153-181,
Kluwer, 1996. Kluwer, 1996.
skipping to change at line 780 skipping to change at line 780
IEEE INFOCOM'97, Kobe, Japan, 1997. IEEE INFOCOM'97, Kobe, Japan, 1997.
[11] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal [11] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal
Configuration for the Zone Routing Protocol," IEEE JSAC, Configuration for the Zone Routing Protocol," IEEE JSAC,
August, 1999. August, 1999.
[12] Pearlman, M.R., Haas, Z.J. and S.I. Mir, "Using Routing Zones to [12] Pearlman, M.R., Haas, Z.J. and S.I. Mir, "Using Routing Zones to
Support Route Maintenance in Ad Hoc Networks," Support Route Maintenance in Ad Hoc Networks,"
IEEE WCNC 2000, Chicago, IL, Sept. 2000. IEEE WCNC 2000, Chicago, IL, Sept. 2000.
Haas, Pearlman, Samar Expires December 2001 [Page 12] Haas, Pearlman, Samar Expires January 2003 [Page 12]
[13] Pearlman, M.R., Haas, Z.J., "Improving the Performance of Query- [13] Pearlman, M.R., Haas, Z.J., "Improving the Performance of Query-
Based Routing Protocols Through Diversity Injection," Based Routing Protocols Through Diversity Injection,"
IEEE WCNC 1999, New Orleans, LA, Sept. 1999. IEEE WCNC 1999, New Orleans, LA, Sept. 1999.
[14] Perkins, C.E. and Royer, E.M., "Ad Hoc On-Demand Distance [14] Perkins, C.E. and Royer, E.M., "Ad Hoc On-Demand Distance
Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999
[15] Perkins, C.E. and Bhagwat, P., "Highly Dynamic [15] Perkins, C.E. and Bhagwat, P., "Highly Dynamic
Destination-Sequenced Distance-Vector Routing (DSDV) for Destination-Sequenced Distance-Vector Routing (DSDV) for
Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994. Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994.
[16] Postel, J., "Internet Protocol," RFC 791, Sept. 1981. [16] Postel, J., "Internet Protocol," RFC 791, Sept. 1981.
Haas, Pearlman, Samar Expires December 2001 [Page 13] Haas, Pearlman, Samar Expires January 2003 [Page 13]
Authors' Information Authors' Information
Zygmunt J. Haas Zygmunt J. Haas
Wireless Networks Laboratory Wireless Networks Laboratory
323 Frank Rhodes Hall 323 Frank Rhodes Hall
School of Electrical Engineering School of Electrical & Computer Engineering
Cornell University Cornell University
Ithaca, NY 14853 Ithaca, NY 14853
United States of America tel: (607) 255-3454, fax: (607) 255-9072 United States of America tel: (607) 255-3454, fax: (607) 255-9072
Email: haas@ee.cornell.edu Email: haas@ece.cornell.edu
Marc R. Pearlman Marc R. Pearlman
389 Frank Rhodes Hall 389 Frank Rhodes Hall
School of Electrical Engineering School of Electrical & Computer Engineering
Cornell University Cornell University
Ithaca, NY 14853 Ithaca, NY 14853
United States of America United States of America
tel: (607) 255-0236, fax: (607) 255-9072 tel: (607) 255-0236, fax: (607) 255-9072
Email: pearlman@ee.cornell.edu Email: pearlman@ece.cornell.edu
Prince Samar Prince Samar
372 Frank Rhodes Hall 374 Frank Rhodes Hall
School of Electrical Engineering School of Electrical & Computer Engineering
Cornell University Cornell University
Ithaca, NY 14853 Ithaca, NY 14853
United States of America United States of America
tel: (607) 255-9068, fax: (607) 255-9072 tel: (607) 255-9068, fax: (607) 255-9072
Email: samar@ee.cornell.edu Email: samar@ece.cornell.edu
The MANET Working Group contacted through its chairs: The MANET Working Group contacted through its chairs:
M. Scott Corson M. Scott Corson
Institute for Systems Research Institute for Systems Research
University of Maryland College Park, MD 20742 University of Maryland College Park, MD 20742
(301) 405-6630 (301) 405-6630
corson@isr.umd.edu corson@isr.umd.edu
Joseph Macker Joseph Macker
Information Technology Division Information Technology Division
Naval Research Laboratory Naval Research Laboratory
Washington, DC 20375 Washington, DC 20375
(202) 767-2001 (202) 767-2001
macker@itd.nrl.navy.mil macker@itd.nrl.navy.mil
Haas, Pearlman, Samar Expires December 2001 [Page 14] Haas, Pearlman, Samar Expires January 2003 [Page 14]
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/