INTERNET-DRAFT Zygmunt J. Haas, Cornell University
Marc R. Pearlman, Cornell University
Expires in six months August 1998
The Zone Routing Protocol (ZRP) for Ad Hoc Networks
<draft-ietf-manet-zone-zrp-01.txt>
Status of this Memo
This document is 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.''
To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Distribution of this memo is unlimited.
Abstract
This document describes the Zone Routing Protocol (ZRP), a hybrid
routing protocol suitable for a wide variety of mobile ad-hoc
networks, especially those with large network spans and diverse
mobility patterns. Each node proactively maintains routes within a
local region (referred to as the routing zone). Knowledge of the
routing zone topology is leveraged by the ZRP to improve the
efficiency of a reactive route query/reply mechanism. The proactive
maintenance of routing zones also helps improve the quality of
discovered routes, by making them more robust to changes in network
topology. The ZRP can be configured for a particular network by
proper selection of a single parameter, the routing zone radius.
This version of the ZRP internet draft describes a number of
features which have been added to the protocol. The distance-vector
based IARP algorithm has been enchanced to prevent the 'counting
to infinity problem'. Route caching is now supported by the IERP
route discovery process. By allowing discovered route information
to be distributed in caches, route accumulation in the IERP query/
reply packets can be avoided, thereby reducing the amount of
route discovery traffic, and improving the query response time.
Two additional (optional) stages have also been added to the route
discovery process, to support the acquisition and optimization of
source routes.
Haas, Pearlman Expires February 1999 [Page i]
INTERNET DRAFT The Zone Routing Protocol August 1998
Contents
Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2
2. Overview of the Zone Routing Protocol . . . . . . . . . . . 3
2.1 The Notion of a Routing Zone and
the Intrazone Routing Protocol (IARP) . . . . . . . 3
2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 4
2.2.1 Routing Zone Based Route Discovery . . . . . . 4
2.2.2 Route Accumulation Procedure . . . . . . . . . 5
2.2.3 Query Control Mechanisms . . . . . . . . . . . 6
2.2.4 Route Maintenance . . . . . . . . . . . . . . . 7
3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 8
4. Implementation Details . . . . . . . . . . . . . . . . . . 9
4.1 Intrazone Routing Protocol (IARP) . . . . . . . . . . 9
A. Packet Format . . . . . . . . . . . . . . . . . . 9
B. Structures . . . . . . . . . . . . . . . . . . . . 10
C. Interfaces . . . . . . . . . . . . . . . . . . . . 10
D. State Machine . . . . . . . . . . . . . . . . . . 11
E. Pseudocode Implementation . . . . . . . . . . . . 13
4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 14
A. Packet Format . . . . . . . . . . . . . . . . . . 16
B. Structures . . . . . . . . . . . . . . . . . . . . 18
C. Interfaces . . . . . . . . . . . . . . . . . . . . 19
D. State Machine . . . . . . . . . . . . . . . . . . 19
E. Pseudocode Implementation . . . . . . . . . . . . 22
4.3 Bordercasting Resolution Protocol (BRP) . . . . . . . 25
A. Packet Format . . . . . . . . . . . . . . . . . . 26
B. Structures . . . . . . . . . . . . . . . . . . . . 26
C. Interfaces . . . . . . . . . . . . . . . . . . . . 26
D. State Machine . . . . . . . . . . . . . . . . . . 26
E. Pseudocode Implementations . . . . . . . . . . . . 31
5. Other Considerations . . . . . . . . . . . . . . . . . . . 37
5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 37
6. References . . . . . . . . . . . . . . . . . . . . . . . . 38
Haas, Pearlman Expires February 1999 [Page 1]
INTERNET DRAFT The Zone Routing Protocol August 1998
1. Introduction
One of the major challenges in designing a routing protocol for the
ad hoc networks stems from the fact that, on one hand, to determine
a packet route, a node needs to known at least the reachability
information to its neighbors. On the other hand, in an ad hoc
network, the network topology can change quite often. Furthermore,
as the number of network nodes can be large, the potential number of
destinations is also large, requiring large and frequent exchange of
data (e.g., routes, routes updates, or routing tables) among the
network nodes. Thus, the amount of update traffic can be quite high.
This is in contradiction with the fact that all updates in a
wirelessly interconnected ad hoc network travel over the air and,
thus, are costly in resources.
In general, the existing routing protocols can be classified either
as proactive or as reactive. Proactive protocols attempt to
continuously evaluate the routes within the network, so that when
a packet needs to be forwarded, the route is already known and can
be immediately used. The family of Distance-Vector protocols is an
example of a proactive scheme. Reactive protocols, on the other
hand, invoke a route determination procedure on demand only. Thus,
when a route is needed, some sort of global search procedure is
employed. The family of classical flooding algorithms belong to the
reactive group. Some examples of reactive (also called on-demand)
ad hoc network routing protocols are [Johnson], [AODV], [TORA]
(see also [Park]).
The advantage of the proactive schemes is that, once a route is
needed, there is little delay until the route is determined. In
reactive protocols, because route information may not be available
at the time a datagram is received, the delay to determine a route
can be quite significant. Furthermore, the global flood-search
procedure of the reactive protocols requires significant control
traffic. Because of this long delay and excessive control traffic,
pure reactive routing protocols may not be applicable to real-time
communication. However, pure proactive schemes are likewise not
appropriate for the ad hoc networking environment, as they
continuously use a large portion of the network capacity to keep the
routing information current. Since nodes in an ad hoc networks move
quite fast, and as the changes may be more frequent than the route
requests, most of this routing information is never even used! This
results in a further waste of the wireless network capacity. What is
needed is a protocol that, on one hand, initiates the route-
determination procedure on-demand, but at limited search cost. The
protocol described in this draft, termed the "Zone Routing Protocol
(ZRP)" ([Haas-1], [Haas-2]), is an example of a such a hybrid
proactive/reactive scheme.
Haas, Pearlman Expires February 1999 [Page 2]
INTERNET DRAFT The Zone Routing Protocol August 1998
The ZRP, on one hand, limits the scope of the proactive procedure
only to the node's local neighborhood. On the other hand, the search
throughout the network, although global in nature, is done by
efficiently querying selected nodes in the network, as opposed to
querying all the network nodes.
A related issue is that of updates in the network topology. For a
routing protocol to be efficient, changes in the network topology
should have only a local effect. In other words, creation of a new
link at one end of the network is an important local event but, most
probably, not a significant piece of information at the other end of
the network. Proactive protocols tend to distribute such topological
changes widely in the network, incurring large costs. The ZRP limits
propagation of such information to the neighborhood of the change
only, thus limiting the cost of topological updates.
2. Overview of the Zone Routing Protocol
2.1 The Notion of a Routing Zone and the Intrazone Routing Protocol
(IARP)
A routing zone is defined for each node X, and includes the nodes
whose minimum distance in *hops* from X is at most some predefined
number, which is referred to as the Zone Radius. An example of a
routing zone (for node A) of radius 2 is shown below.
+-----------------------------------------+
| +---+ |
| +---+ ---| F |-------| |
+---+ | +---+ --| C |--/ +---+ +---+ |
| G |-----| D |--/ +---+ | E | | Zone of node A
+---+ | +---+ | +---+ +---+ | of radius=2
| +---+ ---| B |-------| |
| | A |--/ +---+ |
| +---+ |
+-----------------------------------------+
Note that in this example nodes B through E are within the routing
zone of A. Node G is outside A's routing zone. Also note that E can
be reached by two paths from A, one with length 2 hops and one with
length 3 hope. Since the minimum is less or equal than 2, E is within
A's routing zone.
Peripheral nodes are nodes whose minimum distance to the node in
question is equal exactly to the zone radius. Thus, in the above
figure, nodes D, F, and E are A's peripheral nodes.
An important consequence of the routing zone construction is the
ability of a node to deliver a packet to its peripheral nodes.
This service, which we refer to as bordercasting, allows for more
efficient network-wide searching than simple neighbor broadcasting.
Bordercasting could be implemented either through a series of IP
unicasts or an IP multicast (Distance Vector Multicast Routing
Haas, Pearlman Expires February 1999 [Page 3]
INTERNET DRAFT The Zone Routing Protocol August 1998
Protocol [RFC-1075])) to the peripheral nodes. (In cases where
multicasting is supported, the multicasting approach is preferred
to reduce the amount of traffic over the air.) However, as will be
explained later, efficient ZRP operation requires that these unicast
or multicast services be provided by the ZRP, with IP providing best-
effort delivery to the specified ZRP next hops.
The ZRP supports the proactive maintenance of routing zones
through its proactive Intrazone Routing Protocol (IARP). Through
the IARP, each node learns the identity of and the (minimal)
distance to all the nodes in its routing zone. The IARP may be
derived from a wide range of proactive protocols, such as
Distance Vector (e.g., [Murthy], [DSDV]) or Shortest Path First
(e.g., OSPF [RFC-2178]). Whatever the choice of IARP is, the base
protocol needs to be modified to ensure that the scope of this
operation is restricted to the radius of a node's routing zone.
Because each node needs to proactively acquire route information
only for the nodes within its zone, the total amount of IARP traffic
does not depend on the size of the network, which may be quite large
2.2 The Interzone Routing Protocol (IERP)
While the IARP maintains routes within a zone, the IERP* is
responsible for finding routes between nodes located at distances
larger than the zone radius. The IERP is distinguished from standard
flood-search query/response protocols by exploiting the routing zone
topology. A node is able to respond positively to any queries for
its routing zone nodes. For large networks, relatively few
destinations lie within any particular node's routing zone. In this
more likely case, the node can efficiently continue the propagation
of the query, through the routing zone-based bordercast delivery
mechanism.
2.2.1 Routing Zone Based Route Discovery
The IERP operates as follows: The source node first checks whether
the destination is within its routing zone. (Again, this is possible
as every node knows the content of its zone). If so, the path to the
destination is known and no further route discovery processing is
required. If, on the other hand, the destination is not within the
source's routing zone, the source bordercasts a route query to all of
its peripheral nodes. Now, in turn, all the peripheral nodes execute
the same algorithm: check whether the destination is within their
zone. If so, a route reply is sent back to the source indicating the
route to the destination. If not, the peripheral node forwards the
query to its peripheral nodes, which, in turn, executes the same
procedure. An example of this Route Discovery procedure is
demonstrated in the figure below.
Haas, Pearlman Expires February 1999 [Page 4]
INTERNET DRAFT The Zone Routing Protocol August 1998
+---+
+---+ | F |
+---+---| C |----+---+-----+---+ +---+
| D | +---+ | E |----| H |
+---+ | +---+-----+---+ +---+
+---+----| B | |
| A | +---+-----+---+ +---+
+---+ | G | | I |
+---+ +---+
|
+---+
+---+ | J |
| C |----+---+----+---+ +---+
+---+ | K |----| L |
+---+ +---+
The node A has a datagram to send to node L. Assume a uniform
routing zone radius of 2 hops. Since L is not in A's routing zone
(which includes B,C,D,E,F,G), A bordercasts a routing query to its
peripheral nodes: D,F,E, and G. Each one of these peripheral nodes
check whether L exists in their routing zones. Since L is not found
in any routing zones of these nodes, the nodes bordercast the request
to their peripheral nodes. In particular, G bordercasts to K, which
realizes that L is in its routing zone and returns the requested
route (L-K-G-A) to the query source, namely A.
* Some functions of the IERP, including bordercasting, route
accumulation, and query control (see later), are performed by a
special component of the IERP called the Bordercast Resolution
Protocol (BRP). Sections 3.0 and 4.0 describe, in detail, the
relationship between the BRP and the IERP proper.
2.2.2 Route Accumulation Procedure
The query propagation mechanism allows a route query to indirectly
reach the desired destination (through some node Y, which discovers
the destination in its routing zone.) To complete the route
discovery process, Y needs to send a reply back to the query's
source, S, providing S with the desired route. To perform the route
reply, sufficient information needs to be accumulated during the
query phase so that Y is provided with a route back to S. Providing
routes from discovering node Y to query source S, and from the query
source S back to the query destination D (through Y), is the role of
the Route Accumulation procedure.
In the basic Route Accumulation, a node appends its IP address to a
received query packet. The sequence of IP addresses specifies a
route from the query's source to the current node. By reversing this
sequence, a route may also be obtained back to the source. In this
way, Y may send a reply back to S, through strict source routing.
Haas, Pearlman Expires February 1999 [Page 5]
INTERNET DRAFT The Zone Routing Protocol August 1998
Given sufficient storage space, a queried node may cache routing
information accumulated in the query packet, allowing the information
to be remove from the packet. This has the benefit of reducing the
length of the query packet, thereby decreasing the query traffic and
query response time. The IP addresses that remain in the packet can
be used to form a loose source route back to the query's source (If
ALL nodes have cached the accumulated route information, then this
effectively becomes next hop routing. If no nodes have cached
accumulated route information, then this defaults to the basic case
previously discussed). The same caching strategy can be applied to
the reply packet on its way back to the source. In this case, a
loose source route to the destination is formed.
2.2.3 Query Control Mechanisms
Bordercasting has the potential to support global querying schemes
that are more efficient than flooding. To achieve this efficiency,
the protocol should be able to detect and terminate a query thread
when it appears in a previously queried region of the network (i.e.
arrives at a node belonging to the routing zone of a previously
queried node). This detection / termination capability is
significantly limited when bordercasting is implemented directly
through IP unicast or IP multicast.
By implementing bordercasting within the ZRP, the nodes that relay
the query to the peripheral node are able to detect the passing
query. If the underlying IP delivery is (neighbor) broadcast or
if IP is operating in promiscuous mode, then nodes that overhear
a query transmission are also able to detect the query, further
strengthening the Query Detection (QD) mechanism. Upon detecting
a query, the identifying query parameters (i.e. query source,
query ID) are recorded in a Detected Queries Table, to provide a
basis for termination of future threads of that query.
A node can consider a query to be redundant if it has already
detected that query, bordercasted by a different node. If
bordercasting is implemented directly through IP unicast/ multicast,
then a query thread could only be terminated after being received by
the peripheral node (bordercast destination). This could result in
wasted transmissions as a query penetrates into a previously queried
region. Implementing bordercasting in the ZRP allows the protocol to
provide an Early Termination (ET), as the redundant query enters the
previously queried region.
Haas, Pearlman Expires February 1999 [Page 6]
INTERNET DRAFT The Zone Routing Protocol August 1998
2.2.4 Route Maintenance
In addition to initially discovering routes, the IERP may also assume
responsibility for monitoring the integrity of these routes and
repairing failed routes as appropriate.
Route failures can be detected either proactively or reactively.
Proactive route failure detection is triggered by the IARP, in
response to a node leaving the routing zone. Any IERP routes
containing this node as the first hop can be considered invalid.
Route failures may also be detected reactively, by IP, when the next
hop in a datagram's source route is determined to be unreachable
(i.e. does not appear in the (Intrazone) Routing Table).
Upon detection of a route failure, a node may choose to notify
the route's source of the failure and / or attempt to repair the
route. A route failure notification consists of a transmission
back to the query source, indicating that the source route has
failed, and possibly the hop at which it failed. This type of
service is provided by protocols like ICMP. The node that detects
the route failure may also try to repair the failed connection by
discovering a route to bypass the failed connection. The repair
discovery process is nearly identical to an initial route discovery.
Route repairs should not be substantially longer than the original
failed connection. Thus, the depth of a repair query can be limited,
through the use of hop counter. This has the advantage of producing
much less query traffic than an unrestricted initial route query.
After a successful repair, the route's source MAY be notified so that
routes are properly selected for use. Alternatively, the repair
could go unreported without compromising the connectivity between
source and destination.
Haas, Pearlman Expires February 1999 [Page 7]
INTERNET DRAFT The Zone Routing Protocol August 1998
3.0 The ZRP Architecture
.........................................
: ZRP :
: :
+---------+ : +---------+ +---------+ : +---------+
| NDM |========>| IARP |========>| IERP |<========| ICMP |
+---------+ : +---------+ |.........| : +---------+
/|\ : /|\ | BRP | : /|\
| : | +---------+ : |
| : | /|\ : |
| :.........|...................|.........: |
| | | |
\|/ \|/ \|/ \|/
+---------+---------+---------+---------+---------+---------+---------+
| IP |
+---------+---------+---------+---------+---------+---------+---------+
Legend:
A <---> B exchange of packets between protocols A & B
A ===> B information passed from protocol A to protocol B
Existing Protocols
------------------
IP Internet Protocol
ICMP Internet Control Message Protocol
ZRP Entities
------------
IARP IntrAzone Routing Protocol
IERP IntErzone Routing Protocol
BRP Bordercast Resolution Protocol
(component of IERP)
Additional Protocols
--------------------
NDM Neighbor Discovery/Maintenance Protocol
Note, it is assumed that basic neighbor discovery operation is
implemented by the MAC/link-layer protocols. Thus the NDM protocol
remains unspecified here.
Haas, Pearlman Expires February 1999 [Page 8]
INTERNET DRAFT The Zone Routing Protocol August 1998
4. Implementation Details
4.1 The IntrAzone Routing Protocol (IARP)
The IARP can be implemented through various proactive protocols. We
present here an implementation based on a modified version of the
Distance Vector algorithm. Routing information to a node is limited
to the the routing zone of that node. In this version, routing
information consists of the route cost and the IP addresses of the
route destination and next two hops to the destination. The second hop
is included to identify routes where a node is it's own second hop.
This particular looping condition can result in the "counting to
infinity" problem. By deleting these routes, this problem can be
avoided, allowing the IARP to converge faster.
A node may receive new route information either from a received IARP
packet or from an interrupt generated by its Neighbor Discovery /
Maintenance (NDM) proces*. In the special case when a host has
discovered a neighor, the IARP is responsible for sending to the new
neighbor the shortest route to each host which is common to both of
their routing zones (i.e. each host with a hop count less than it's
routing zone radius). The node then records the new route information
in its Intrazone Routing Table. If the shortest path to the host has
changed, the terminal broadcasts an IARP packet reflecting the
change.
* IARP relies on the services of a separate protocol (referred to
here as the Neighbor Discovery/Maintenance Protocol) to provide
current information about a host's neighbors. At the least, this
information must include the IP addresses of all the neighbors.
The IARP can be readily configured to support supplemental
neighbor information, such as link cost.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop #1 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop #2 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Hop Cnt|
+-+-+-+-+
Haas, Pearlman Expires February 1999 [Page 9]
INTERNET DRAFT The Zone Routing Protocol August 1998
Field Description:
* Destination Address (32 bits)
IP address of the destination host
* Next Hop # 1 Address (32 bits)
IP address of the "next hop" host to the destination host
* Next Hop # 2 Address (32 bits)
IP address of the Next Hop #1 's "next hop" host to
the destination host
* Hop Count (4 bits)
Length of the route to the destination host, measured
in hops
B. Structures
B.1 Intrazone Routing Table
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Routes |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Host | 0 | 1 | ==> | M-1 |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Next : Hop | Next : Hop | ==> | Next : Hop |
| | Hop : Count | Hop : Count | | Hop : Count |
+-+-+-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-+-+-+-:-+-+-+-+
| | : | : | | : |
|-----------|-------:-------|-------:-------|-----|-------:-------|
| | : | : | | : |
|-----------|-------:-------|-------:-------|-----|-------:-------|
| | : | : | | : |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
C. Interfaces
C.1 Higher Layer (N/A)
C.2 Lower Layer (IP)
C.1.1 Send() (specified in IP standard)
C.1.2 Deliver() (specified in IP standard)
C.3 NDM
C.3.1 Neighbor_Lost(host)
Used by the NDM to notify the IARP that direct contact
has been lost with "host".
C.3.2 Neighbor_Found(host)
Used by the NDM to notify the IARP that direct contact
has been confirmed with "host".
C.4 IERP
C.4.1 Zone_Node_Lost(host)
Used by IARP to notify the IERP that a node no longer
exists within the routing zone.
Haas, Pearlman Expires February 1999 [Page 10]
INTERNET DRAFT The Zone Routing Protocol August 1998
D. State Machine
The IARP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The IARP immediately
acts upon an event and then returns back to the IDLE state.
Notes: 1) X is used as a label for the host running this state
machine.
2) INF is a reserved field value corresponding to
"infinity".
D.1
Event: An IARP packet is received containing route
information to a destination D. The hop count
associated with the received route is LESS THAN
OR EQUAL TO the routing zone radius. The
second next-hop is EQUAL to X.
Action: NONE
D.2
Event: An IARP packet is received containing route
information to a destination D. The hop count
associated with the received route is LESS THAN
the routing zone radius. The second next-hop
is NOT EQUAL to X.
Action: The received route is recorded in the Intrazone
Routing Table. If the received route is shorter
than the previous shortest route to D, then a new
IARP packet containing route information to D
through X is broadcasted.
D.3
Event: An IARP packet is received containing route
information to a destination D. The hop count is
EQUAL TO the routing zone radius. The second
next-hop is NOT EQUAL to X.
Action: The received route is recorded in the Intrazone
Routing Table.
Haas, Pearlman Expires February 1999 [Page 11]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.4
Event: An IARP packet is received containing route
information to a destination D. The hop count is
equal to INF.
Action: The route to D is removed from the Intrazone
Routing Table.
1) If the Intrazone Routing Table still
contains a route to D and the length of the
shortest route has increased due to the route
removal, then the an IARP packet containing the
shortest route to D through X is broadcasted.
2) If the Intrazone Routing Table contains no
more routes to D, then an IARP packet containing
a route to D through X with hop count of INF is
broadcast. A "Host Lost" interrupt is
generated to alert the IERP that D has moved
beyond the routing zone.
D.5
Event: A "Neighbor Found" interrupt is received,
indicating the discovery of a neighbor host N.
Action: For each destination in X's Intrazone Routing
Table, an IARP packet is sent to N containing the
best route to that destination. An IARP packet is
then broadcasted containing the 1 hop route to N
through X.
D.6
Event: A "Neighbor Lost" interrupt is received, indicating
that host N is no longer a neighbor of X
Action: The one hop route to N is removed from the
Intrazone Routing Table.
1) If the Intrazone Routing Table still
contains a route to N and the length of the
shortest route has increased due to the route
removal, then the an IARP packet containing the
shortest route to N through X is broadcasted.
2) If the Intrazone Routing Table contains no
more routes to N, then an IARP packet containing
a route to D through X with hop count of INF is
broadcast. A "Host Lost" interrupt is generated
to alert the IERP that D has moved beyond the
routing zone.
Haas, Pearlman Expires February 1999 [Page 12]
INTERNET DRAFT The Zone Routing Protocol August 1998
E. Pseudocode Implementation
E.1 Update Intrazone Routing Table
if (packet arrived)
{host, route->next_hop, next_next_hop, route->hop_count}
<-- packet
else
{
{host} <-- intrpt
route->next_hop=host
if (type(intrpt) == "Neighbor Found")
{
for dest = each host in Intrazone_Routing_Table
{
best_route = Intrazone_Routing_Table[dest,0]
if (best_route->hop_count < ROUTING_ZONE_RADIUS)
{
packet <--{dest,my_id,best_route->next_hop,
best_route->hop_count+1}
send(packet,host)
}
}
route->hop_count=1
}
else
route->hop_count=INF
}
former_best_route = Intrazone_Routing_Table[host,0]
if (route->hop_count < INF)
if(route->next_next_hop != my_id
add(Intrazone_Routing_Table[host], route)
else
remove(Intrazone_Routing_Table[host], route)
best_route = Intrazone_Routing_Table[host,0]
if (best_route != NULL)
{
if (best_route->hop_count != former_best_route->hop_count
&& best_route->hop_count < ROUTING_ZONE_RADIUS)
{
packet <-- {host, my_id, best_route->next_hop,
best_route->hop_count+1}
broadcast(packet)
}
}
else
{
force_intrpt("IERP","Zone Node Lost",{host})
packet <-- {host, my_id, my_id, INF}
broadcast(packet)
}
Haas, Pearlman Expires February 1999 [Page 13]
INTERNET DRAFT The Zone Routing Protocol August 1998
4.2 IntErzone Routing Protocol (IERP)
The Interzone Routing Protocol (IERP) is responsible for discovering
and maintaining routes to hosts which are beyond a node's routing
zone. The IERP acquires routing information reactively, exploiting
the knowledge of the routing zone topology through the bordercasting
delivery service.
This version of the IERP extends the basic query / reply mechanism
described in Section 3. In the basic protocol, queries are
terminated before reaching the query destination. This provides
a faster response to the route query than if the destination, D,
were to respond directly. However, because D never receives the
query, it does not acquire a route back to the source, S. If the
D needs to send data back to S (which is often the case, given the
bi-directional nature of many applications), a separate route query
from D to S would have to be initiated. This substantial overhead
is avoided by having the query forwarded to D, by the node Y that
discovers D in its routing zone. We refer to this as a QUERY
EXTENSION.
Both the source and destination can acquire routes to each other
through the BRP route accumulation mechanisms (to be discussed
later). Distributing route information in the caches of the
route's nodes can significantly reduce the size of the IERP packets
and provide for a faster query response. On the other hand, QOS
requirements for a particular application may favor a source
specified route. (rather than a distributed next-hop approach).
Source routing requires that the discovered route information be
accumulated in the IERP packets, rather than cached. This IERP
implementation satisfies the demands for rapid query response
and source routing support by two stages of route reporting. In the
first two stages, route information is cached by the route's nodes
(when possible). Next-hop route are quickly returned to the source
in QUERY-REPLY packets and forwarded to the destination in QUERY-
EXTENSION packets. At this point, bi-directional connectivity is
established. In the third stage, the source and destination can
provide each other with complete source routes, by sending each
other ROUTE-ACCUMULATION packets. As these packets traverse the
route, the cached route information is accumulated in the packets,
thereby constructing the desired source route.
Variations on this IERP implementation can be realized by combining
or eliminating some of these stages. For example, if source routing
is not desired, the ROUTE-ACCUMULATION stage can be eliminated.
Also, if all of the route's nodes elect not to cache the routing
information (perhaps due to storage limitations), then the QUERY
REPLY and QUERY-EXTENSION packets essentially serve the role of
ROUTE-ACCUMULATION packets, obviating the need for a separate
ROUTE-ACCUMULATION stage.
Haas, Pearlman Expires February 1999 [Page 14]
INTERNET DRAFT The Zone Routing Protocol August 1998
Because each node proactively maintains the local topology of its
routing zone, it is not necessary for a source route to specify
every hop along the route (i.e. strict source routing). A properly
chosen subset of the complete source route can be used to specify
the route to the destination, and where desirable, the reverse route
back to the source. The IERP supports such an optimization through
a final ROUTE-OPTIMIZATION stage. The details of the route
optimization are described in the BRP specification. Upon
completion of the ROUTE-OPTIMIZATION stage, sufficient routing zone
membership is acquired for each node in the route so that the source
route may be reduced (by translating this route reduction into
an appropriate set covering problem, and employing a suitable
heuristic).
+-----+ +-----+ +-----+
| S | . . . . | Y | . . . | D |
+-----+ +-----+ +-----+
(1) search for QUERY
route |-------------------------->
QUERY QUERY
(2) establish REPLY EXTENSION
connectivity <--------------------------|
|=============>
(3) provide ROUTE-ACCUMULATION
source route |---------------------------------------->
<========================================|
(4) optimize ROUTE-OPTIMIZATION
source route <----------------------------------------|
|========================================>
Sequence of the IERP Route Discovery Stages
Haas, Pearlman Expires February 1999 [Page 15]
INTERNET DRAFT The Zone Routing Protocol August 1998
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 | Rsvd | Hops Left | Query ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bad Link Source Address (repair only) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Next IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ BRP
| Next BRP Address | fields
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Prev IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Hop 0 Address (Source) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Hop 1 Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| | |
\| |/ route
\ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| |
| Hop (N-2) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Hop (N-1) Address (Destination) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Flags (optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field Description:
* Type (4 bits)
Identifies the type of IERP packet. The current version
of IERP contains five packet types:
QUERY:
request for an Interzone source route to the
destination specified by the Destination
IP Address
QUERY-EXTENSION:
extension of a QUERY packet sent from the
node that discovers the Destination to the
Destination itself.
Haas, Pearlman Expires February 1999 [Page 16]
INTERNET DRAFT The Zone Routing Protocol August 1998
QUERY-REPLY:
response to a QUERY packet, sent from the node
that discovers the Destination back to the
Source. At a minimum, the QUERY-REPLY contains
next-hop route information to the Destination.
(In general, returns the source route up to
the first node which has cached routing
information. If no nodes have cached routing
information, then the complete source route is
returned.)
ROUTE-ACCUMULATION (optional):
sent by the Source to the Destination, in
response to a QUERY-REPLY, and sent by the
Destination to the Source, in response to a
QUERY-EXTENSION. Routing information cached
at the route's nodes is accumulated in this
packet, providing a complete source route at
the destination of this packet.
ROUTE-OPTIMIZATION (optional):
sent by the Source to the Destination, and
by the Destination to the Source, in response
to a ROUTE-ACCUMULATION. Flags are appended
to this packet reflecting the mutual routing
zone membership of each node in the source
route.
* Query ID (16 bits)
Sequence number which, along with the Source Address
(see below) uniquely identifies any route query in the
network.
* Hops Left (8 bits)
Number of hops that a route query may continue to
propagate. This field allows a querying node to
configure the depth of a route search, to
control the amount of IERP traffic generated.
* Bad Link Address (32 bits)
Used during route repairs. Contains the IP Address
corresponding to the source of routes failed link.
* Next IERP Address (32 bits)
IP address of the next IERP recipient
* Next BRP Address (32 bits)
IP address of the next BRP recipient.
(i.e. next hop to the next IERP recipient)
* Prev IERP Address (32 bits)
IP address of the previous IERP recipient
Haas, Pearlman Expires February 1999 [Page 17]
INTERNET DRAFT The Zone Routing Protocol August 1998
* Source Route (N * 32 bits)
Variable length field that contains the IP addresses of
the source route's nodes.
- route(0) contains the IP address of the
route's source.
- route(N-1) contains the IP address of the
route's destination
- in general, route(n) contains the IP address
of the n-th hop of the source route
* Flags (N * 32*ceil(N/32) bits)
The k-th bit of the n-th flag subfield indicates whether
route(k) is located within route(n)'s routing zone.
This routing zone membership information, collected
during the optional ROUTE-OPTIMIZATION stage, may be
used to determine the shortest possible specification
for the accumulated source route.
B. Structures
B.1 Intrazone Routing Table (See IARP Description)
B.2 Interzone Routing Table
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Routes |
+ Dest +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | 0 | 1 | ==> | M-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | ==> | |
|---------|-----------|-----------|-----|-----------|
| | | | ==> | |
|---------|-----------|-----------|-----|-----------|
| | | | | | ==> | |
+-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
\ /
\ /
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+
| 0 |==>| 1 |==> ...==>| N-1 | source
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ route
source first (N-1)
host hop hop
Haas, Pearlman Expires February 1999 [Page i8]
INTERNET DRAFT The Zone Routing Protocol August 1998
C. Interfaces
C.1 Higher Layer (N/A)
C.2 Lower Layer (BRP)
C.2.1 Send() (same interface as IP send())
Used by the IERP to request transmission of an
IERP packet.
C.2.2 Deliver() (same interface as IP deliver())
Used by the BRP to alert the IERP of the arrival of a
data packet.
C.3 IARP
C.3.1 Zone_Node_Lost(host)
Used by the IARP to notify the IERP that a node has left
the routing zone
C.4 ICMP
C.4.1 Host_Unreachable() (specified in ICMP standard)
C.4.2 Source_Route_Failed() (specified in ICMP standard)
D. State Machine
The IERP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The IERP immediately
acts upon an event and then returns back to the IDLE state.
Note: 1) X is used as a label for the host running this state
machine.
D.1
Event: A "Zone_Node_Lost" interrupt is received,
indicating that the node H has moved beyond the
routing zone.
Action: Remove every route from the Interzone Routing Table
which contains H. If any routes containing H are
found, then a route repair (limited depth route
discovery) to H is initiated.
D.2
Event: A "Host_Unreachable" interrupt is received from the
ICMP, indicating an unknown destination host D.
Action: A full depth route discovery to D is initiated.
The query_id is incremented and assigned to a new
QUERY packet. The route is initialized with the
IP addresses of the route's source and destination
IP addresses (X and D). Finally, the QUERY packet
is bordercasted.
Haas, Pearlman Expires February 1999 [Page 19]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.3
Event: A "Source_Route_Failed" or "Proactive_Repair"
interrupt is received, indicating that the next
hop, H, specified in a source route does not
appear within the routing zone.
Action: A limited depth route discovery to H is initiated.
The query_id is incremented and assigned to a new
QUERY packet. The route is initialized with the
valid portion of the failed route, and the
bad link address field is set with X's IP address,
to indicate the location of the route failure.
Finally, the QUERY packet is bordercasted.
D.4
Event: A QUERY packet is received with a destination that
appears within X's routing zone.
Action: A QUERY-REPLY is sent back to the query source, and
a QUERY-EXTENSION is sent to the query destination.
D.5
Event: A QUERY packet is received with a destination that
DOES NOT appear within X's routing zone.
Action: The QUERY packet is bordercasted.
D.6
Event: A QUERY-EXTENSION packet is received.
Action: The packet contents are moved to a ROUTE-
ACCUMULATION packet. The ROUTE-ACCUMULATION
packet is sent to the query source.
D.7
Event: A QUERY-REPLY packet is received.
Action: The packet contents are moved to a ROUTE-
ACCUMULATION packet. The ROUTE-ACCUMULATION
packet is sent to the query destination.
D.8
Event: A ROUTE-ACCUMULATION packet is received. X is not
the final destination of this packet
(i.e. X != IERP_next). This only occurs when the
accumulated route contains a repair
Action: The bad link is replaced by the path repair in the
Interzone Routing Table.
Haas, Pearlman Expires February 1999 [Page 20]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.9
Event: A ROUTE-ACCUMULATION packet is received. X is
either the route source or (route destination).
Action: The (reversed) accumulated route is added to the
Interzone Routing Table or replaces a failed route
if the packet specifies a bad link. In addition,
if X is the ROUTE-ACCUMULATION destination, the
packet contents may be moved to a ROUTE-
OPTIMIZATION packet, which is then sent to
the query destination (query source).
D.10
Event: A ROUTE-OPTIMIZATION packet is received.
Action: The routing zone membership information that is
collected in the ROUTE-OPTIMIZATION packet is
processed. The resulting optimized route(s) are
added to the Interzone Routing Table.
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, hops_left, query_id, bad_link_source,
next_IERP, next_BRP, prev_IERP, route, flag}
load (packet)
loads the values of the aforementioned variables into
the fields of the IERP packet.
Haas, Pearlman Expires February 1999 [Page 21]
INTERNET DRAFT The Zone Routing Protocol August 1998
E.1 Routing Zone Node Lost
{lost_host} <-- intrpt
repair_link = FALSE
for host = each host in Interzone Routing Table
{
for (route = each Interzone route to host)
{
if (lost_host (EXISTS IN) route)
{
if (PROACTIVE_REPAIRS_ENABLED)
{
removal_timer = ROUTE_QUERY_TIMEOUT
repair_link = TRUE
}
else
removal_timer = 0
schedule(
remove(Interzone_Routing_Table[host]->route(m)),
removal_timer)
}
}
}
if(repair_link)
{
bad_link = my_id + lost_host
force_intrpt("IERP","Proactive_Repair", bad_link)
}
E.2 Initiate Route Discovery
{route} <-- intrpt
dest = route(length(route)-1)
current_hop_ptr = get_index(route, my_id)
prev_hops = route(0: current_hop_ptr-1)
route = prev_hops + my_id + dest
if (type(intrpt) == "Proactive_Repair" ||
type(intrpt) == "Source_Route_Failed")
{
hops_left = MAX_REPAIR_HOPS
bad_link_source = my_id
}
else
{
hops_left = MAX_FULL_QUERY_HOPS
bad_link_source = NULL
}
query_id ++
load (packet)
send (packet, BORDERCAST)
Haas, Pearlman Expires February 1999 [Page 22]
INTERNET DRAFT The Zone Routing Protocol August 1998
E.3 Receive IERP Packet
extract(packet)
source=route(0)
dest = route(length(route)-1)
switch(pk_type)
{
case: QUERY
if (dest (EXISTS IN) Intrazone_Routing_Table)
{
type = QUERY-REPLY
if(bad_link_source)
IERP_next = bad_link_source
else
IERP_next = source
load(packet)
send(packet)
type = QUERY-EXTENSION
IERP_next = dest
load(packet)
send(packet)
}
else
bordercast(packet)
break
case: QUERY-EXTENSION
type = ROUTE-ACCUMULATION
IERP_next=source
send(packet)
break
case: QUERY-REPLY
type = ROUTE-ACCUMULATION
IERP_next = dest
load (packet)
send (packet)
break
Haas, Pearlman Expires February 1999 [Page 23]
INTERNET DRAFT The Zone Routing Protocol August 1998
case: ROUTE-ACCUMULATION
if (bad_link_source)
{
path_source_ptr = get_index(route, bad_link_source)
path_dest_ptr = get_index(route, dest)
if (IERP_next == source)
{
bad_link = bad_link_source + dest
path_repair = route(path_source_ptr:path_dest_ptr)
}
if (IERP_next == dest)
{
bad_link = dest + bad_link_source
path_repair = reverse(route(path_source_ptr :
path_dest_ptr))
}
replace(Interzone_Routing_Table, bad_link,path_repair)
}
else
{
if (my_id == source)
add(Interzone_Routing_Table, route)
if (my_id == dest)
add(Interzone_Routing_Table, reverse(route))
}
if (my_id == IERP_next)
{
if (my_id == source)
IERP_next = dest
if (my_id == dest)
IERP_next = source
type = ROUTE-OPTIMIZATION
load (packet)
send (packet)
}
break
case: ROUTE-OPTIMIZATION
if (my_id == source)
add(Interzone_Routing_Table, route, flags)
if (my_id == dest)
add(Interzone_Routing_Table, reverse(route), flags)
break
}
Haas, Pearlman Expires February 1999 [Page 24]
INTERNET DRAFT The Zone Routing Protocol August 1998
4.3 Bordercast Resolution Protocol (BRP)
The BRP is a sublayer of the IERP that performs the operations of
bordercasting, query control, route accumulation and routing zone
labelling, which form the basis for the route discovery procedure.
In this BRP implementation, bordercasting is implemented as a series
of unicasted messages to the peripheral nodes. The BRP is able to
identify the peripheral based on the information contained in the
Intrazone Routing Table. Rather than unicasting to the peripheral
node directly through IP, the bordercasted packets are relayed to
the peripheral nodes by the BRP layer. IP is used only to send
these messages one hop toward the peripheral nodes. This allows the
BRP to detect all QUERY packets that are received by that node.
To efficiently terminate the query, the BRP needs to record
sufficient information from each detected query. The query's source
and ID, which serve to uniquely identify a query, are added to the
Detected Queries Table. In addition, the IP address of the last
node to bordercast the query is also recorded in the Detected
Queries table. Any threads of this query that are later received
from a different bordercasting node are discarded. Each query also
contains a hop counter that is decremented at each node. When the
counter expires, the packet is discarded.
IERP packets (excluding ROUTE-OPTIMIZATION packets) that are not
terminated next undergo a route accumulation procedure. As
described earlier, route accumulation is used to construct routes,
by recording the IP addresses of a route's nodes in the IERP packet
or local cache. The Detected Queries Table, extended by two
columns, serves as a convenient route accumulation cache.
The node begins the route accumulation procedure by adding its IP
address to the IERP route. This is followed by the IP addresses of
any cached nodes leading to the packet's destination (the "next
hops"). This is sufficient processing for ROUTE-ACCUMULATION
packets, where complete source routes are constructed. On the other
hand, QUERY, QUERY-EXTENSION and QUERY-REPLY packets should carry as
little of the route as possible. Therefore, if cache space is
available, the route accumulation process records the IP addresses
of the "previous hops" from the packet's source, and removes them
from the IERP packet.
The final role of the BRP is contribute to the ROUTE-OPTIMIZATION
process by indicating the mutual routing zone membership of the
nodes in the source route. This is done by appending a special
flag field to the ROUTE-OPTIMIZATION packet. The status of the
k-th bit in the flag field indicates whether the k-th hop in the
source route is a member of the node's routing zone. This
membership information is eventually processed at the source to
determine the smallest set of routing zones that cover the route
(and therefore the smallest set of nodes needed to specify this
route through loose source routing.)
Haas, Pearlman Expires February 1999 [Page 25]
INTERNET DRAFT The Zone Routing Protocol August 1998
A. Packet Format
See IERP packet format in Section 4.2
B. Structures
B.1 Intrazone Routing Table (see IARP description)
B.2 Detected Queries Table
|--------------------|--------|-----------------------|
| Query | Query | Prev | Prev | Next |
| Source | Id | IERP | Hop(s) | Hop(s) |
|----------+---------|--------+-----------+-----------|
| | | | | | | | | |
|----------+---------|--------+---+---+---|---+---+---|
| | | | | | | | | |
|----------+---------|--------+---+---+---|---+---+---|
| | | | | | | | | |
|--------------------|--------|-----------------------|
|
\|/
+---+ +---+ +---+
| A |-->| B |-->... | C |
+---+ +---+ +---+
cached "source" route
C. Interfaces
C.1 Higher Layer (i.e. IERP)
C.2.1 Send() (same interface as IP Send() primitive)
Used by higher layer protocol to request transmission of
a data packet
C.2.2 Deliver() (same interface as IP Deliver() primitive)
Used by the BRP to alert the higher layer protocol of
the arrival of a data packet
C.2 Lower Layer (IP)
C.2.1 Send() (specified in IP standard)
C.2.2 Deliver() (specified in IP standard)
D. State Machine
The BRP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The BRP immediately
acts upon an event and then returns back to the IDLE state.
Notes: 1) X is used as a label for the host running this state
machine.
2) NULL is a reserved field value, corresponding to an
invalid IP address.
Haas, Pearlman Expires February 1999 [Page 26]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.1
Event: A QUERY packet is received from the IERP
Action: If X is the query's source, then the identifying
querying information is recorded in the Detected
Queries Table. X adds its IP address to the
packet's route. A copy of the packet is sent to
the IERP layer of each peripheral node, by way of
a BRP transmission to the next hop to that
peripheral node.
D.2
Event: A QUERY packet is received from the IP. The hop
counter has expired or the query was already
detected from another bordercasting node.
Action: The packet is discarded.
D.3
Event: A QUERY packet is received from IP. The hop count
has not expired and the query has not been
previously detected (or was detected from the
same bordercasting node). X is not the
intended BRP recipient.
Action: If cache space is available, identifying query
information SHOULD be recorded in the Detected
Queries Table. The packet is then discarded.
D.4
Event: A QUERY packet is received from the IP. The hop
count has not expired and the query has not been
previously detected (or was previously detected
from the same bordercasting node). X is the
intended BRP recipient, but is not the intended
IERP recipient and the query destination does
not lie within X's routing zone.
Action: The hop counter is decremented. If cache space
is available, identifying query information and
accumulated route information should be recorded
in the Detected Queries Table. The recorded route
information is removed from the packet and X adds
its IP address to the route.
The packet is then sent to the BRP of the next hop
to the intended IERP recipient.
Haas, Pearlman Expires February 1999 [Page 27]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.5
Event: A QUERY packet is received from the IP. The hop
count has not expired and the query has not been
previously detected (or was previously detected
from the same bordercasting node). X is the
intended BRP recipient, and either X is the
intended IERP recipient, OR the query destination
lies in X's routing zone.
Action: The hop counter is decremented. If cache space
is available, identifying query information and
accumulated route information should be recorded
in the Detected Queries Table. The recorded route
information is removed from the packet and X adds
its IP address to the route.
The packet is then delivered up to the IERP.
D.6
Event: A QUERY-EXTENSION is received from the IERP.
Action: The packet is sent to the BRP layer of the
next hop to the specified IERP recipient
(in this case, the query destination).
D.7
Event: A QUERY-EXTENSION is received from the IP.
X is not the intended BRP recipient.
Action: If cache space is available, identifying query
information SHOULD be recorded in the Detected
Queries Table. The packet is then discarded.
D.8
Event: A QUERY-EXTENSION packet is received from the IP.
X is the intended BRP recipient, but is not the
intended IERP recipient.
Action: If cache space is available, identifying query
information and accumulated route information
should be recorded in the Detected Queries Table.
The recorded route information is removed from the
packet and X adds its IP address to the route.
The packet is then sent to the BRP of the next hop
to the intended IERP recipient.
Haas, Pearlman Expires February 1999 [Page 28]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.9
Event: A QUERY-EXTENSION packet is received from the IP.
X is the intended BRP recipient and the intended
IERP recipient.
Action: If cache space is available, identifying query
information and accumulated route information
should be recorded in the Detected Queries Table.
The recorded route information is removed from the
packet and X adds its IP address to the route.
The packet is then delivered up to the IERP.
D.10
Event: A QUERY-REPLY packet is received from the IERP.
Action: The IP addresses of X and the previous hops back
to the query source (cached in the Detected Queries
Table) are added to the route. The packet is sent
back to the IERP layer of the query source, by way
of a BRP layer transmission to the first hop back
to the query source.
D.11
Event: A QUERY-REPLY packet is received from the IP.
X is not the intended BRP recipient.
Action: The packet is discarded.
D.12
Event: A QUERY-REPLY packet is received from the IP.
X is the intended BRP recipient, but not the
intended IERP recipient.
Action: If cache space is available, accumulated route
information to the destination should be recorded
in the Detected Queries Table, and the recorded
route information removed from the packet. The IP
addresses of X and the previous hops back to the
query source (cached in the Detected Queries Table)
are added to the route.
The packet is then sent to the BRP layer of the
previous hop back to the query source.
D.13
Event: A QUERY-REPLY packet is received from the IP.
X is the intended BRP recipient and the intended
IERP recipient.
Action: If cache space is available, accumulated route
information to the destination should be recorded
in the Detected Queries Table, and the recorded
route information removed from the packet.
The packet is then delivered up to the IERP.
Haas, Pearlman Expires February 1999 [Page 29]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.14
Event: A ROUTE-ACCUMULATION packet is received from the
IERP.
Action: The packet is sent to the IERP layer of the
specified IERP recipient by way of a BRP
transmission to the next hop toward the IERP
recipient.
D.15
Event: A ROUTE-ACCUMULATION packet is received from the
IP. X is not the intended BRP recipient.
Action: The packet is discarded.
D.16
Event: A ROUTE-ACCUMULATION packet is received from the
IP. X is the intended BRP recipient, but not the
intended IERP recipient.
Action: The IP addresses of X and the next hops to the
intended IERP recipient (which are cached in the
Detected Queries Table) are added to the route.
If this packet contains a route repair and the
repair has already been accumulated, then a copy
of the packet is delivered to the IERP. The
packet is then sent to the BRP layer of the next
hop toward the IERP recipient.
D.17
Event: A ROUTE-ACCUMULATION packet is received from the
IP. X is the intended BRP recipient and the
intended IERP recipient.
Action: The packet is delivered up to the IERP.
D.18
Event: A ROUTE-OPTIMIZATION packet is received from the
IERP.
Action: X indicates (in its flag field) those route nodes
that belong to its routing zone. The packet is
then sent to the IERP layer of the specified IERP
recipient, by way of a BRP transmission to the
next hop toward the IERP recipient.
D.19
Event: A ROUTE-OPTIMIZATION packet is received from the
IP. X is not the intended BRP recipient.
Action: The packet is discarded.
Haas, Pearlman Expires February 1999 [Page 30]
INTERNET DRAFT The Zone Routing Protocol August 1998
D.20
Event: A ROUTE-OPTIMIZATION packet is received from the
IP. X is the intended BRP recipient, but not
the intended IERP recipient.
Action: X indicates (in its flag field) those route nodes
that belong to its routing zone. The packet is
then sent to the IERP layer of the specified IERP
recipient, by way of a BRP transmission to the
next hop toward the IERP recipient.
D.21
Event: A ROUTE-OPTIMIZATION packet is received from the
IP. X is the intended BRP recipient and the
intended IERP recipient.
Action: X indicates (in its flag field) those route nodes
that belong to its routing zone. The packet
is then delivered up to the IERP
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, hops_left, query_id, bad_link_source,
next_IERP, next_BRP, prev_IERP, route, flag}
load (packet)
loads the values of the aforementioned variables into
the fields of the IERP packet.
E.1 Receive Packet from IERP
extract (packet)
source = route(0)
dest = route(length(route)-1)
current_hop_ptr = get_index(route, my_id)
prev_hops = reverse(route(0: current_hop_ptr-1))
next_hops = route(current_hop_ptr+1 : length(route)-1)
IERP_prev = my_id
Haas, Pearlman Expires February 1999 [Page 31]
INTERNET DRAFT The Zone Routing Protocol August 1998
switch(type)
{
case: QUERY
if ((bad_link_source == my_id || source == my_id)
add(Detected_Queries,packet)
for (IERP_next = each host in Intrazone_Routing_Table)
{
if (IERP next is a peripheral node)
{
BRP_next=Intrazone_Routing_Table[host,0]->next_hop
load(pk_copy)
send(pk_copy,BRP_next)
}
}
break
case: QUERY-EXTENSION
BRP_next=Intrazone_Routing_Table[IERP_next,0]->next_hop
load(packet)
send(packet,BRP_next)
break
case: QUERY-REPLY
if (prev_hops(0) == source)
prev_hops = Detected_Queries[source,query_id]
->prev_hops
route = prev_hops + my_id + next_hops
BRP_next = prev_hops(0)
load(packet)
send(packet,BRP_next)
break
case: ROUTE-ACCUMULATION
if(my_id == source)
BRP_next = next_hops(0)
if(my_id == dest)
BRP_next = prev_hops(0)
load(packet)
send(packet,BRP_next)
break
case: ROUTE-OPTIMIZATION
flag = NULL
for (i = 0 to length(route)-1)
{
if ((EXISTS) Intrazone_Routing_Table[route(i)])
flag = flag,1
else
flag = flag,0
}
if(my_id == source)
BRP_next = next_hops(0)
if(my_id == dest)
BRP_next = prev_hops(0)
load(packet)
send(packet,BRP_next)
break
Haas, Pearlman Expires February 1999 [Page 32]
INTERNET DRAFT The Zone Routing Protocol August 1998
E.2 Receive Packet from IP
extract(packet)
source = route(0)
dest = route(length(route)-1)
current_hop_ptr = get_index(route, my_id)
prev_hops = reverse(route(0: current_hop_ptr-1))
next_hops = route(current_hop_ptr+1 : length(route)-1)
switch(type)
{
case QUERY:
if (hops_left > 0 &&
(!EXISTS(Detected_Queries[source,query_id] ||
Detected_Queries[source,query_id]->from
== IERP_prev))
{
hops_left --
if (!FULL (Detected_Queries))
{
add(Detected_Queries, packet)
prev_hops = source
}
else
route = prev_hops + my_id + next_hops
if(BRP_next == my_id)
{
if(IERP_next == my_id ||
dest (EXISTS IN) Intrazone_Routing_Table)
deliver(packet,IERP)
else
{
BRP_next=Intrazone_Routing_Table[IERP_next]
->route(0)->next_hop
load(packet)
send(packet, BRP_next)
}
}
else
discard(packet)
}
else
discard(packet)
break
Haas, Pearlman Expires February 1999 [Page 33]
INTERNET DRAFT The Zone Routing Protocol August 1998
case QUERY-EXTENSION:
{
if (!FULL (Detected_Queries))
{
add(Detected_Queries,packet)
prev_hops = source
}
route = prev_hops + my_id + next_hops
if(BRP_next == my_id)
{
if(IERP_next == my_id ||
dest (EXISTS IN) Intrazone_Routing_Table)
deliver(packet,IERP)
else
{
BRP_next=Intrazone_Routing_Table[IERP_next]
->route(0)->next_hop
load(packet)
send(packet, BRP_next)
}
}
else
discard(packet)
}
else
discard(packet)
break
case QUERY-REPLY:
if(my_id == BRP_next)
{
if (!FULL (Detected_Queries))
{
add(Detected_Queries, packet)
next_hops = dest
}
if (prev_hops(0) == source)
prev_hops = Detected_Queries[source,query_id]
->prev_hops
route = prev_hops + my_id + next_hops
if(my_id == IERP_next)
deliver(packet,IERP)
else
{
BRP_next = prev_hops(0)
load(packet)
send(packet,BRP_next)
}
}
else
discard(packet)
break
Haas, Pearlman Expires February 1999 [Page 34]
INTERNET DRAFT The Zone Routing Protocol August 1998
case ROUTE-ACCUMULATION:
if(my_id == BRP_next)
{
if(my_id == IERP_next)
deliver(packet, IERP)
else
{
if (bad_link_source && IERP_next == source)
{
bad_link_ptr=get_index(route,bad_link_source)
if (current_hop_ptr <= bad_link_ptr)
deliver(packet, IERP)
}
if (IERP_next == dest)
{
if(next_hops(0) == dest)
next_hops=Detected_Queries[source,query_id]
->next_hops
BRP_next = next_hops(0)
}
if (IERP_next == source)
{
if(prev_hops(0) == source)
prev_hops=Detected_Queries[source,query_id]
->prev_hops
BRP_next = prev_hops(0)
}
route = prev_hops + my_id + next_hops
load(packet)
send (packet,BRP_next)
}
}
else
discard(packet)
break
Haas, Pearlman Expires February 1999 [Page 35]
INTERNET DRAFT The Zone Routing Protocol August 1998
case ROUTE-OPTIMIZATION:
if(my_id == BRP_next)
{
f = NULL
for (i = 0: length(route)-1)
{
if ((EXISTS) Intrazone_Routing_Table[route(i)])
f = f,1
else
f = f,0
}
if (IERP_next == source)
flag = f , flag
else
flag = flag , f
if(my_id == IERP_next)
deliver(packet, IERP)
else
{
if(IERP_next == source)
BRP_next = prev_hops(0)
else
BRP_next = next_hops(0)
load(packet)
send (packet,BRP_next)
}
}
else
discard(packet)
break
Haas, Pearlman Expires February 1999 [Page 36]
INTERNET DRAFT The Zone Routing Protocol August 1998
5. Other Considerations
5.1 Sizing the Zone Radius
The performance of the Zone Routing Protocol is determined by the
routing zone radius. In general, dense networks consisting of a few
fast moving nodes favor smaller routing zones. On the other hand, a
sparse network of many slowly moving nodes operates more efficiently
with a larger zone radius.
The simplest approach to configuring the routing zone radius is to
make the assignment once, prior to deploying the network. This can
be performed by the network administration, if one exists, or by
the manufacturer, as a default value. This may provide acceptable
performance, especially in situations where network characteristics
do not vary greatly over space and time. Alternatively, the ZRP can
adpat to changes in network behavior, through dynamnic configuration
of the zone radius [Haas-3]. In [Haas-4], it was shown that
a node can accurately estimate its optimal zone radius, on-line,
based on local measurements of ZRP traffic. The re-sizing of the
routing zone can be carried out by a protocol that conveys the
change in zone radius to the members of the routing zone. The
details of such an update protocol will be provided in a future
version of this draft.
Haas, Pearlman Expires February 1999 [Page 37]
INTERNET DRAFT The Zone Routing Protocol August 1998
6.0 References
[AODV] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing",
MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA,
November 3, 1997
[Haas-1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable
Wireless Networks", ICUPC'97, San Diego, CA, Oct. 12,1997.
[Haas-2] Haas, Z.J. and Pearlman, M.R., "The Performance of Query
Control Schemes for the Zone Routing Protocol,"
SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998.
[Haas-3] Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design
Choices in Ad-Hoc Communications", MILCOM'98, Boston, MA,
October 18-21, 1998.
[Haas-4] Haas, Z.J. and Pearlman, M.R., "Determining the Optimal
Configuration for the Zone Routing Protocol", submitted
for journal publication.
[Johnson] 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.
[Murthy] 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.
[Park] Park, V.D., and Corson, M.S., "A Highly Adaptive
Distributed Routing Algorithm for Mobile Wireless
Networks," IEEE INFOCOM'97, Kobe, Japan, 1997.
[Perkins] 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.
[TORA] Macker, J., "Mobile Ad Hoc Internetworking", MILCOM'97
panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997.
[RFC-0791] Postel, J., Editor, "Internet Protocol", STD 5, RFC 791,
September 1981.
[RFC-1075] Waitzman, D., Partridge, C., Deering, S.E., "Distance
Vector Multicast Routing Protocol",RFC 1075, Nov. 1, 1988.
[RFC-2178] Moy, J., "OSPF Version 2", INTERNET DRAFT STANDARD,
RFC 2178, July 1997.
Haas, Pearlman Expires February 1999 [Page 38]
INTERNET DRAFT The Zone Routing Protocol August 1998
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@acm.org or haas@ee.cornell.edu
Marc R. Pearlman
319 Frank Rhodes Hall
School of Electrical Engineering
Cornell University
Ithaca, NY 14853
United States of America
Email: pearlman@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 Expires February 1999 [Page 39]
INTERNET DRAFT The Zone Routing Protocol August 1998
