draft-ietf-manet-zone-zrp-01.txt   draft-ietf-manet-zone-zrp-02.txt 
INTERNET-DRAFT Zygmunt J. Haas, Cornell
INTERNET-DRAFT Zygmunt J. Haas, Cornell University University
Marc R. Pearlman, Cornell University Marc R. Pearlman, Cornell
Expires in six months August 1998 University
Expires in six months on December 1999 June
1999
The Zone Routing Protocol (ZRP) for Ad Hoc Networks The Zone Routing Protocol (ZRP) for Ad Hoc Networks
<draft-ietf-manet-zone-zrp-01.txt> <draft-ietf-manet-zone-zrp-02.txt>
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft and is NOT offered in accordance
documents of the Internet Engineering Task Force (IETF), its areas, with Section 10 of RFC2026, and the author does not provide the IETF
and its working groups. Note that other groups may also distribute with any rights other than to publish as an Internet-Draft.
working documents as Internet-Drafts.
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 Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference material
material or to cite them other than as ``work in progress.'' or to cite them other than as "work in progress."
To view the entire list of current Internet-Drafts, please check the The list of current Internet-Drafts can be accessed at
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow http://www.ietf.org/ietf/1id-abstracts.txt
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or The list of Internet-Draft Shadow Directories can be accessed at
ftp.isi.edu (US West Coast). http://www.ietf.org/shadow.html.
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
Abstract Abstract
This document describes the Zone Routing Protocol (ZRP), a hybrid This document describes the Zone Routing Protocol (ZRP), a hybrid
routing protocol suitable for a wide variety of mobile ad-hoc routing protocol suitable for a wide variety of mobile ad-hoc
networks, especially those with large network spans and diverse networks, especially those with large network spans and diverse
mobility patterns. Each node proactively maintains routes within a mobility patterns. Each node proactively maintains routes within a
local region (referred to as the routing zone). Knowledge of the local region (referred to as the routing zone). Knowledge of the
routing zone topology is leveraged by the ZRP to improve the routing zone topology is leveraged by the ZRP to improve the
efficiency of a reactive route query/reply mechanism. The proactive efficiency of a reactive route query/reply mechanism. The proactive
maintenance of routing zones also helps improve the quality of maintenance of routing zones also helps improve the quality of
discovered routes, by making them more robust to changes in network discovered routes, by making them more robust to changes in network
topology. The ZRP can be configured for a particular network by topology. The ZRP can be configured for a particular network by
proper selection of a single parameter, the routing zone radius. proper selection of a single parameter, the routing zone radius.
This version of the ZRP internet draft describes a number of The ZRP framework is designed to provide a balance between the
features which have been added to the protocol. The distance-vector contrasting proactive and reactive routing approaches. To underscore
based IARP algorithm has been enchanced to prevent the 'counting this general philosophy, both the proactive and reactive components of
to infinity problem'. Route caching is now supported by the IERP this ZRP implementation have been expanded. This draft provides
route discovery process. By allowing discovered route information specifications for both a (split-horizon) Distance Vector AND a Link
to be distributed in caches, route accumulation in the IERP query/ State
reply packets can be avoided, thereby reducing the amount of version of the proactive IntrAzone Routing Protocol (IARP). The reactive
route discovery traffic, and improving the query response time. IntErzone Routing Protocol (IERP) provides a route caching option. When
Two additional (optional) stages have also been added to the route route caching is globally enabled, the IERP acts as a reactive Distance
discovery process, to support the acquisition and optimization of Vector protocol, distributing routing information among intermediate
source routes. nodes.
On the other hand, when route caching is disabled, the routes are
accumulated
in the query packets and the protocol operates through source routing.
Haas, Pearlman Expires December 1999 [Page
i]
INTERNET DRAFT The Zone Routing Protocol June
1999
This ZRP specification also offers some additional enhancements. The
reactive route query procedure now supports route querying for multiple
destinations and multicast groups. Queries can be targeted for either
ANY destination or ALL destinations (depending on the nature of the
query).
By aggregating route queries, the amount of overhead traffic can be
greatly
reduced. In addition, the ZRP now supports QOS routing through the
collection of various route quality metrics (in both the proactive and
reactive routing components).
Haas, Pearlman Expires December 1999 [Page
ii]
INTERNET DRAFT The Zone Routing Protocol June
1999
Contents Contents
Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2 Applicability Statement . . . . . . . . . . . . . . . . . . . . v
A. Networking Context . . . . . . . . . . . . . . . . . . v
B. Protocol Characteristics and Mechanisms . . . . . . . . v
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1
2. Overview of the Zone Routing Protocol . . . . . . . . . . . 3 2. Overview of the Zone Routing Protocol . . . . . . . . . . . 3
2.1 The Notion of a Routing Zone and 2.1 The Notion of a Routing Zone and the
the Intrazone Routing Protocol (IARP) . . . . . . . 3 Intrazone Routing Protocol (IARP) . . . . . . . . . . 3
2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 4 2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 4
2.2.1 Routing Zone Based Route Discovery . . . . . . 4 2.2.1 Routing Zone Based Route Discovery . . . . . . 4
2.2.2 Route Accumulation Procedure . . . . . . . . . 5 2.2.2 Route Accumulation Procedure . . . . . . . . . 5
2.2.3 Query Control Mechanisms . . . . . . . . . . . 6 2.2.3 Query Control Mechanisms . . . . . . . . . . . 6
2.2.4 Route Maintenance . . . . . . . . . . . . . . . 7 2.2.4 Route Maintenance . . . . . . . . . . . . . . . 7
3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 8 3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 8
4. Implementation Details . . . . . . . . . . . . . . . . . . 9 4. Implementation Details . . . . . . . . . . . . . . . . . . 9
4.1 Intrazone Routing Protocol (IARP) . . . . . . . . . . 9 4.1 Intrazone Routing Protocol (IARP) . . . . . . . . . . 9
A. Packet Format . . . . . . . . . . . . . . . . . . 9 4.1.1 Distance Vector Implementation . . . . . . . . 9
B. Structures . . . . . . . . . . . . . . . . . . . . 10 A. Packet Format . . . . . . . . . . . . . . . . 10
C. Interfaces . . . . . . . . . . . . . . . . . . . . 10 B. Data Structures . . . . . . . . . . . . . . . 11
D. State Machine . . . . . . . . . . . . . . . . . . 11 C. Interfaces . . . . . . . . . . . . . . . . . . 11
E. Pseudocode Implementation . . . . . . . . . . . . 13 D. State Machine . . . . . . . . . . . . . . . . 12
E. Pseudocode Implementation . . . . . . . . . . 14
4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 14 4.1.2 Link State Implementation . . . . . . . . . . . 16
A. Packet Format . . . . . . . . . . . . . . . . . . 16 A. Packet Format . . . . . . . . . . . . . . . . 16
B. Structures . . . . . . . . . . . . . . . . . . . . 18 B. Data Structures . . . . . . . . . . . . . . . 18
C. Interfaces . . . . . . . . . . . . . . . . . . . . 19 C. Interfaces . . . . . . . . . . . . . . . . . . 20
D. State Machine . . . . . . . . . . . . . . . . . . 19 D. State Machine . . . . . . . . . . . . . . . . 20
E. Pseudocode Implementation . . . . . . . . . . . . 22 E. Pseudocode Implementation . . . . . . . . . . 21
4.3 Bordercasting Resolution Protocol (BRP) . . . . . . . 25 4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 24
A. Packet Format . . . . . . . . . . . . . . . . . . 26 A. Packet Format . . . . . . . . . . . . . . . . . . 26
B. Structures . . . . . . . . . . . . . . . . . . . . 26 B. Data Structures . . . . . . . . . . . . . . . . . 31
C. Interfaces . . . . . . . . . . . . . . . . . . . . 26 C. Interfaces . . . . . . . . . . . . . . . . . . . . 31
D. State Machine . . . . . . . . . . . . . . . . . . 26 D. State Machine . . . . . . . . . . . . . . . . . . 32
E. Pseudocode Implementations . . . . . . . . . . . . 31 E. Pseudocode Implementation . . . . . . . . . . . . 33
5. Other Considerations . . . . . . . . . . . . . . . . . . . 37 4.3 Bordercasting Resolution Protocol (BRP) . . . . . . . 37
5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 37 A. Packet Format . . . . . . . . . . . . . . . . . . 38
B. Data Structures . . . . . . . . . . . . . . . . . 38
C. Interfaces . . . . . . . . . . . . . . . . . . . . 38
D. State Machine . . . . . . . . . . . . . . . . . . 39
E. Pseudocode Implementations . . . . . . . . . . . . 43
6. References . . . . . . . . . . . . . . . . . . . . . . . . 38 Haas, Pearlman Expires December 1999 [Page
iii]
INTERNET DRAFT The Zone Routing Protocol June
1999
5. Other Considerations . . . . . . . . . . . . . . . . . . . 53
5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 53
5.2 Hierarchical Routing and the ZRP . . . . . . . . . . . 53
6. References . . . . . . . . . . . . . . . . . . . . . . . . 55
Haas, Pearlman Expires December 1999 [Page
iv]
INTERNET DRAFT The Zone Routing Protocol June
1999
Applicability Statement
A. Networking Context
The hybrid Zone Routing Protocol (ZRP) can adapt to a wide variety of
network scenarios by adjusting the range of the nodes' proactively
maintained routing zones. Large routing zones are preferred when demand
for routes is high and/or the network consists of many slowly moving
nodes. In the extreme case of a network with fixed topology, the ideal
routing zone radius would be infinitely large. (Consider the purely
proactive routing protocols used on the fixed Internet). On the other
hand,
smaller routing zones are appropriate in situations where route demand
is
low and/or the network consists of a small number of nodes that move
fast
relative to one another. In the "worst case", a routing zone radius of
one
hop is best, and the ZRP defaults to a tradtional reactive flooding
protocol.
When the ZRP is properly configured for a particular network scenario,
it
can perform at least as well as (and often better than) its purely
proactive
and reactive constituent protocols. In situations where the network
behavior varies across different regions, the ZRP performance can be
fine
tuned by individual adjustment of each node's routing zone.
The global reactive component of the ZRP uses the unicast/multicast
based
"bordercast" mechanism to propagate route queries throughout the
network,
rather than neighbor-broadcast based flooding found in tradtional
reactive
protocols. Consequently, the ZRP provides the most benefit in networks
where reliable neighbor broadcasting is either inefficient or
all-together
impossible. In particular, the ZRP is well suited for multi-channel,
multi-
technology routing fabrics and networks operating under high load.
B. Protocol Characteristics and Mechanisms
* Does the protocol provide support for unidirectional links? (if so,
how?)
Yes. The ZRP provides "local" support for unidirectional links.
A unidirectional link can be used as long as the link source and
link destination lie within each other's routing zone.
* Does the protocol require the use of tunneling? (if so, how?)
No.
* Does the protocol require using some form of source routing? (if
so, how?)
No. The ZRP's global reactive route discovery mechanism may
use either source routing or distributed distance vector based
route accumulation.
Haas, Pearlman Expires December 1999 [Page
v]
INTERNET DRAFT The Zone Routing Protocol June
1999
* Does the protocol require the use of periodic messaging? (if so,
how?)
Yes. The ZRP proactively maintains local routing information
(routing zones) based on periodic exchanges of neighbor
discovery messages.
* Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?)
The ZRP only assumes that link-layer (neighbor) unicasts are
delivered reliably and in-sequence. Reliable and sequenced
delivery of neighbor broadcasts and IP unicasts is not
required.
* Does the protocol provide support for routing through a multi-
technology routing fabric? (if so, how?)
Yes. It is assumed that each node's network interface is
assigned a unique IP address.
* Does the protocol provide support for multiple hosts per router?
(if so, how?)
Yes. Multiple hosts may be associated with a router. These hosts
can be identified by the neighbor discovery/maintenance process.
By default, it is assumed that a host's association with a router
is not permanent. As a result, the ZRP exchanges routing
information
for individual hosts in the same manner as routing information for
routers.
In cases where a router is permanently associated with a network
(subnetwork), the ZRP supports the exchange of network (subnetwork)
prefixes in place of all aggregated host IP addresses.
* Does the protocol support the IP addressing architecture? (if so,
how?)
Yes. Each node is assumed to have a unique IP address (or
set of unique IP addresses in the case of multiple interfaces).
The ZRP references all nodes/interfaces by their IP address.
This version of the ZRP also supports IP network addressing
(network prefixes) for routers that provide access to a
network of non-router hosts.
Haas, Pearlman Expires December 1999 [Page
vi]
INTERNET DRAFT The Zone Routing Protocol June
1999
* Does the protocol require link or neighbor status sensing (if so,
how?)
Yes. The ZRP proactively maintains local routing information
(routing zones) based on detected changes in neighbor status.
* Does the protocol have dependence on a central entity? (if so,
how?)
No. The ZRP is a fully distributed protocol.
* Does the protocol function reactively? (if so, how?)
Yes. The ZRP's GLOBAL route discovery mechanism is reactive.
A route query is initiated, on demand, when a node requires routing
information that is not immediately available in its routing table.
The route query propagates through the network, using a ZRP-specific
packet delivery service called "bordercasting". Bordercasting
leverages knowledge of local network topology to direct route
queries away from the source, thereby reducing redundancy.
* Does the protocol function proactively? (if so, how?)
Yes. The ZRP proactively maintains local routing information
(routing zones) for each node. The routing zone information is
leveraged, through the bordercasting mechanism, to support
efficient global propagation of route queries.
* Does the protocol provide loop-free routing? (if so, how?)
Yes. Loop-freedom in the reactive route discovery process
is ensured by labeling each route query and route reply
with the IP address of its originating node AND a unique
sequence number. Nodes that relay the route queries
/route replies temporarily cache these identifiers in order
to identify and terminate loops.
The routing protocols used for proactive routing zone maintenance
are based on traditional Distance Vector or Link State routing
protocols. The scope of these proactive route updates is limited
to the extent of a node's routing zone.
The ZRP's Link State proactive protocol is inherently loop-free.
The Distance Vector protocol may form temporary loops prior to
converging. However, convergence occurs quickly due to the limited
radius of the routing zones
Haas, Pearlman Expires December 1999 [Page
vii]
INTERNET DRAFT The Zone Routing Protocol June
1999
* Does the protocol provide for sleep period operation? (if so, how?)
No.
* Does the protocol provide some form of security? (if so, how?)
No. It is assumed that security issues are adequately addressed
by the underlying protocols (IPsec, for example)
* Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?)
Yes. It is assumed that each node's network interface is
assigned a unique IP address.
Haas, Pearlman Expires December 1999 [Page
viii]
INTERNET DRAFT The Zone Routing Protocol June
1999
1. Introduction 1. Introduction
One of the major challenges in designing a routing protocol for the 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 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 a packet route, a node needs to known at least the reachability
information to its neighbors. On the other hand, in an ad hoc information to its neighbors. On the other hand, in an ad hoc
network, the network topology can change quite often. Furthermore, network, the network topology can change quite often. Furthermore,
as the number of network nodes can be large, the potential number of as the number of network nodes can be large, the potential number of
destinations is also large, requiring large and frequent exchange of destinations is also large, requiring large and frequent exchange of
skipping to change at page 2, line 30 skipping to change at line 376
In general, the existing routing protocols can be classified either In general, the existing routing protocols can be classified either
as proactive or as reactive. Proactive protocols attempt to as proactive or as reactive. Proactive protocols attempt to
continuously evaluate the routes within the network, so that when continuously evaluate the routes within the network, so that when
a packet needs to be forwarded, the route is already known and can a packet needs to be forwarded, the route is already known and can
be immediately used. The family of Distance-Vector protocols is an be immediately used. The family of Distance-Vector protocols is an
example of a proactive scheme. Reactive protocols, on the other example of a proactive scheme. Reactive protocols, on the other
hand, invoke a route determination procedure on demand only. Thus, hand, invoke a route determination procedure on demand only. Thus,
when a route is needed, some sort of global search procedure is when a route is needed, some sort of global search procedure is
employed. The family of classical flooding algorithms belong to the employed. The family of classical flooding algorithms belong to the
reactive group. Some examples of reactive (also called on-demand) reactive group. Some examples of reactive (also called on-demand)
ad hoc network routing protocols are [Johnson], [AODV], [TORA] ad hoc network routing protocols are Dynamic Source Routing (DSR)[6],
(see also [Park]). Ad-hoc On demand Distance Vector Routing (AODV) [11] and the
Temporally Ordered Routing Algorithm (TORA) [9].
The advantage of the proactive schemes is that, once a route is The advantage of the proactive schemes is that, once a route is
needed, there is little delay until the route is determined. In needed, there is little delay until the route is determined. In
reactive protocols, because route information may not be available reactive protocols, because route information may not be available
at the time a datagram is received, the delay to determine a route at the time a datagram is received, the delay to determine a route
can be quite significant. Furthermore, the global flood-search can be quite significant. Furthermore, the global flood-search
procedure of the reactive protocols requires significant control procedure of the reactive protocols requires significant control
traffic. Because of this long delay and excessive control traffic, traffic. Because of this long delay and excessive control traffic,
pure reactive routing protocols may not be applicable to real-time pure reactive routing protocols may not be applicable to real-time
communication. However, pure proactive schemes are likewise not communication. However, pure proactive schemes are likewise not
appropriate for the ad hoc networking environment, as they appropriate for the ad hoc networking environment, as they
continuously use a large portion of the network capacity to keep the continuously use a large portion of the network capacity to keep the
routing information current. Since nodes in an ad hoc networks move routing information current. Since nodes in an ad hoc networks move
quite fast, and as the changes may be more frequent than the route quite fast, and as the changes may be more frequent than the route
requests, most of this routing information is never even used! This requests, most of this routing information is never even used! This
results in a further waste of the wireless network capacity. What is results in a further waste of the wireless network capacity. What is
needed is a protocol that, on one hand, initiates the route- needed is a protocol that, on one hand, initiates the route-
determination procedure on-demand, but at limited search cost. The determination procedure on-demand, but at limited search cost. The
protocol described in this draft, termed the "Zone Routing Protocol protocol described in this draft, termed the "Zone Routing Protocol
(ZRP)" ([Haas-1], [Haas-2]), is an example of a such a hybrid (ZRP)" ([1], [2]), is an example of a such a hybrid
proactive/reactive scheme. proactive/reactive scheme.
The ZRP, on one hand, limits the scope of the proactive procedure 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 only to the node's local neighborhood. On the other hand, the search
throughout the network, although global in nature, is done by throughout the network, although global in nature, is done by
efficiently querying selected nodes in the network, as opposed to efficiently querying selected nodes in the network, as opposed to
querying all the network nodes. querying all the network nodes.
Haas, Pearlman Expires December 1999 [Page
1]
INTERNET DRAFT The Zone Routing Protocol June
1999
A related issue is that of updates in the network topology. For a A related issue is that of updates in the network topology. For a
routing protocol to be efficient, changes in the network topology routing protocol to be efficient, changes in the network topology
should have only a local effect. In other words, creation of a new 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 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 probably, not a significant piece of information at the other end of
the network. Proactive protocols tend to distribute such topological the network. Proactive protocols tend to distribute such topological
changes widely in the network, incurring large costs. The ZRP limits changes widely in the network, incurring large costs. The ZRP limits
propagation of such information to the neighborhood of the change propagation of such information to the neighborhood of the change
only, thus limiting the cost of topological updates. only, thus limiting the cost of topological updates.
Haas, Pearlman Expires December 1999 [Page
2]
INTERNET DRAFT The Zone Routing Protocol June
1999
2. Overview of the Zone Routing Protocol 2. Overview of the Zone Routing Protocol
2.1 The Notion of a Routing Zone and the Intrazone Routing Protocol 2.1 The Notion of a Routing Zone and the Intrazone Routing Protocol
(IARP) (IARP)
A routing zone is defined for each node X, and includes the nodes 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 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 number, which is referred to as the Zone Radius. An example of a
routing zone (for node A) of radius 2 is shown below. routing zone (for node A) of radius 2 is shown below.
skipping to change at page 3, line 45 skipping to change at line 453
| G |-----| D |--/ +---+ | E | | Zone of node A | G |-----| D |--/ +---+ | E | | Zone of node A
+---+ | +---+ | +---+ +---+ | of radius=2 +---+ | +---+ | +---+ +---+ | of radius=2
| +---+ ---| B |-------| | | +---+ ---| B |-------| |
| | A |--/ +---+ | | | A |--/ +---+ |
| +---+ | | +---+ |
+-----------------------------------------+ +-----------------------------------------+
Note that in this example nodes B through E are within the routing 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 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 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 length 3 hops. Since the minimum is less or equal than 2, E is within
A's routing zone. A's routing zone.
Peripheral nodes are nodes whose minimum distance to the node in Peripheral nodes are nodes whose minimum distance to the node in
question is equal exactly to the zone radius. Thus, in the above question is equal exactly to the zone radius. Thus, in the above
figure, nodes D, F, and E are A's peripheral nodes. figure, nodes D, F, and E are A's peripheral nodes.
An important consequence of the routing zone construction is the An important consequence of the routing zone construction is the
ability of a node to deliver a packet to its peripheral nodes. ability of a node to deliver a packet to its peripheral nodes.
This service, which we refer to as bordercasting, allows for more This service, which we refer to as bordercasting, allows for more
efficient network-wide searching than simple neighbor broadcasting. efficient network-wide searching than simple neighbor broadcasting.
Bordercasting could be implemented either through a series of IP Bordercasting could be implemented either through a series of IP
unicasts or an IP multicast (Distance Vector Multicast Routing unicasts or an IP multicast (Distance Vector Multicast Routing
Protocol [RFC-1075])) to the peripheral nodes. (In cases where Protocol [13]) to the peripheral nodes. (In cases where
multicasting is supported, the multicasting approach is preferred multicasting is supported, the multicasting approach is preferred
to reduce the amount of traffic over the air.) However, as will be to reduce the amount of traffic over the air.) However, as will be
explained later, efficient ZRP operation requires that these unicast explained later, efficient ZRP operation requires that these unicast
or multicast services be provided by the ZRP, with IP providing best- or multicast services be provided by the ZRP, with IP providing best-
effort delivery to the specified ZRP next hops. effort delivery to the specified ZRP next hops.
The ZRP supports the proactive maintenance of routing zones The ZRP supports the proactive maintenance of routing zones
through its proactive Intrazone Routing Protocol (IARP). Through through its proactive Intrazone Routing Protocol (IARP). Through
the IARP, each node learns the identity of and the (minimal) the IARP, each node learns the identity of and the (minimal)
distance to all the nodes in its routing zone. The IARP may be distance to all the nodes in its routing zone. The IARP may be
derived from a wide range of proactive protocols, such as derived from a wide range of proactive protocols, such as
Distance Vector (e.g., [Murthy], [DSDV]) or Shortest Path First Distance Vector (e.g., [8], [10]) or Shortest Path First
(e.g., OSPF [RFC-2178]). Whatever the choice of IARP is, the base (e.g., OSPF [7]). Whatever the choice of IARP is, the base
protocol needs to be modified to ensure that the scope of this protocol needs to be modified to ensure that the scope of this
operation is restricted to the radius of a node's routing zone. operation is restricted to the radius of a node's routing zone.
Haas, Pearlman Expires December 1999 [Page
3]
INTERNET DRAFT The Zone Routing Protocol June
1999
Because each node needs to proactively acquire route information Because each node needs to proactively acquire route information
only for the nodes within its zone, the total amount of IARP traffic 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 does not depend on the size of the network, which may be quite large
2.2 The Interzone Routing Protocol (IERP) 2.2 The Interzone Routing Protocol (IERP)
While the IARP maintains routes within a zone, the IERP* is While the IARP maintains routes within a zone, the IERP* is
responsible for finding routes between nodes located at distances responsible for finding routes between nodes located at distances
larger than the zone radius. The IERP is distinguished from standard larger than the zone radius. The IERP is distinguished from standard
flood-search query/response protocols by exploiting the routing zone flood-search query/response protocols by exploiting the routing zone
skipping to change at page 5, line 5 skipping to change at line 522
required. If, on the other hand, the destination is not within the 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 source's routing zone, the source bordercasts a route query to all of
its peripheral nodes. Now, in turn, all the peripheral nodes execute its peripheral nodes. Now, in turn, all the peripheral nodes execute
the same algorithm: check whether the destination is within their the same algorithm: check whether the destination is within their
zone. If so, a route reply is sent back to the source indicating the 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 route to the destination. If not, the peripheral node forwards the
query to its peripheral nodes, which, in turn, executes the same query to its peripheral nodes, which, in turn, executes the same
procedure. An example of this Route Discovery procedure is procedure. An example of this Route Discovery procedure is
demonstrated in the figure below. demonstrated in the figure below.
* 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.
Haas, Pearlman Expires December 1999 [Page
4]
INTERNET DRAFT The Zone Routing Protocol June
1999
+---+ +---+
+---+ | F | +---+ | F |
+---+---| C |----+---+-----+---+ +---+ +---+---| C |----+---+-----+---+ +---+
| D | +---+ | E |----| H | | D | +---+ | E |----| H |
+---+ | +---+-----+---+ +---+ +---+ | +---+-----+---+ +---+
+---+----| B | | +---+----| B | |
| A | +---+-----+---+ +---+ | A | +---+-----+---+ +---+
+---+ | G | | I | +---+ | G | | I |
+---+ +---+ +---+ +---+
| |
skipping to change at page 5, line 31 skipping to change at line 560
The node A has a datagram to send to node L. Assume a uniform 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 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 (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 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 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 in any routing zones of these nodes, the nodes bordercast the request
to their peripheral nodes. In particular, G bordercasts to K, which to their peripheral nodes. In particular, G bordercasts to K, which
realizes that L is in its routing zone and returns the requested realizes that L is in its routing zone and returns the requested
route (L-K-G-A) to the query source, namely A. 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 2.2.2 Route Accumulation Procedure
The query propagation mechanism allows a route query to indirectly The query propagation mechanism allows a route query to indirectly
reach the desired destination (through some node Y, which discovers reach the desired destination (through some node Y, which discovers
the destination in its routing zone.) To complete the route the destination in its routing zone.) To complete the route
discovery process, Y needs to send a reply back to the query's 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 source, S, providing S with the desired route. To perform the route
reply, sufficient information needs to be accumulated during the reply, sufficient information needs to be accumulated during the
query phase so that Y is provided with a route back to S. Providing 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 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 source S back to the query destination D (through Y), is the role of
the Route Accumulation procedure. the Route Accumulation procedure.
In the basic Route Accumulation, a node appends its IP address to a In the basic Route Accumulation, a node appends its IP address to a
received query packet. The sequence of IP addresses specifies a received query packet. The sequence of IP addresses specifies a
route from the query's source to the current node. By reversing this 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 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. way, Y may send a reply back to S, through strict source routing.
Haas, Pearlman Expires December 1999 [Page
5]
INTERNET DRAFT The Zone Routing Protocol June
1999
Given sufficient storage space, a queried node may cache routing Given sufficient storage space, a queried node may cache routing
information accumulated in the query packet, allowing the information information accumulated in the query packet, allowing the information
to be remove from the packet. This has the benefit of reducing the to be remove from the packet. This has the benefit of reducing the
length of the query packet, thereby decreasing the query traffic and length of the query packet, thereby decreasing the query traffic and
query response time. The IP addresses that remain in the packet can 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 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 ALL nodes have cached the accumulated route information, then this
effectively becomes next hop routing. If no nodes have cached effectively becomes next hop routing. If no nodes have cached
accumulated route information, then this defaults to the basic case accumulated route information, then this defaults to the basic case
previously discussed). The same caching strategy can be applied to previously discussed). The same caching strategy can be applied to
skipping to change at page 7, line 5 skipping to change at line 629
A node can consider a query to be redundant if it has already A node can consider a query to be redundant if it has already
detected that query, bordercasted by a different node. If detected that query, bordercasted by a different node. If
bordercasting is implemented directly through IP unicast/ multicast, bordercasting is implemented directly through IP unicast/ multicast,
then a query thread could only be terminated after being received by then a query thread could only be terminated after being received by
the peripheral node (bordercast destination). This could result in the peripheral node (bordercast destination). This could result in
wasted transmissions as a query penetrates into a previously queried wasted transmissions as a query penetrates into a previously queried
region. Implementing bordercasting in the ZRP allows the protocol to region. Implementing bordercasting in the ZRP allows the protocol to
provide an Early Termination (ET), as the redundant query enters the provide an Early Termination (ET), as the redundant query enters the
previously queried region. previously queried region.
Haas, Pearlman Expires December 1999 [Page
6]
INTERNET DRAFT The Zone Routing Protocol June
1999
2.2.4 Route Maintenance 2.2.4 Route Maintenance
In addition to initially discovering routes, the IERP may also assume In addition to initially discovering routes, the IERP may also assume
responsibility for monitoring the integrity of these routes and responsibility for monitoring the integrity of these routes and
repairing failed routes as appropriate. repairing failed routes as appropriate.
Route failures can be detected either proactively or reactively. Route failures can be detected either proactively or reactively.
Proactive route failure detection is triggered by the IARP, in Proactive route failure detection is triggered by the IARP, in
response to a node leaving the routing zone. Any IERP routes response to a node leaving the routing zone. Any IERP routes
containing this node as the first hop can be considered invalid. containing this node as the first hop can be considered invalid.
Route failures may also be detected reactively, by IP, when the next Route failures may also be detected reactively, by IP, when the next
hop in a datagram's source route is determined to be unreachable hop in a datagram's source route is determined to be unreachable
(i.e. does not appear in the (Intrazone) Routing Table). (i.e. does not appear in the (Intrazone) Routing Table).
Upon detection of a route failure, a node may choose to notify 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 the route's source of the failure and / or attempt to repair the
route. A route failure notification consists of a transmission route. A route failure notification consists of a transmission
back to the query source, indicating that the source route has back to the query source, indicating that the source route has
failed, and possibly the hop at which it failed. This type of failed, and possibly the hop at which it failed. This type of
skipping to change at page 8, line 5 skipping to change at line 667
discovery process is nearly identical to an initial route discovery. discovery process is nearly identical to an initial route discovery.
Route repairs should not be substantially longer than the original Route repairs should not be substantially longer than the original
failed connection. Thus, the depth of a repair query can be limited, failed connection. Thus, the depth of a repair query can be limited,
through the use of hop counter. This has the advantage of producing through the use of hop counter. This has the advantage of producing
much less query traffic than an unrestricted initial route query. much less query traffic than an unrestricted initial route query.
After a successful repair, the route's source MAY be notified so that After a successful repair, the route's source MAY be notified so that
routes are properly selected for use. Alternatively, the repair routes are properly selected for use. Alternatively, the repair
could go unreported without compromising the connectivity between could go unreported without compromising the connectivity between
source and destination. source and destination.
Haas, Pearlman Expires December 1999 [Page
7]
INTERNET DRAFT The Zone Routing Protocol June
1999
3.0 The ZRP Architecture 3.0 The ZRP Architecture
......................................... .........................................
: ZRP : : ZRP :
: : : :
+---------+ : +---------+ +---------+ : +---------+ +---------+ : +---------+ +---------+ : +---------+
| NDM |========>| IARP |========>| IERP |<========| ICMP | | NDM |========>| IARP |========>| IERP |<========| ICMP |
+---------+ : +---------+ |.........| : +---------+ +---------+ : +---------+ |.........| : +---------+
/|\ : /|\ | BRP | : /|\ /|\ : /|\ | BRP | : /|\
| : | +---------+ : | | : | +---------+ : |
| : | /|\ : | | : | /|\ : |
| :.........|...................|.........: | | :...........|...................|.......: |
| | | | | | | |
\|/ \|/ \|/ \|/ \|/ \|/ \|/ \|/
+---------+---------+---------+---------+---------+---------+---------+ +---------+---------+---------+---------+---------+---------+---------+
| IP | | IP |
+---------+---------+---------+---------+---------+---------+---------+ +---------+---------+---------+---------+---------+---------+---------+
Legend: Legend:
A <---> B exchange of packets between protocols A & B A <---> B exchange of packets between protocols A & B
A ===> B information passed from protocol A to protocol B A ===> B information passed from protocol A to protocol B
skipping to change at page 9, line 5 skipping to change at line 716
(component of IERP) (component of IERP)
Additional Protocols Additional Protocols
-------------------- --------------------
NDM Neighbor Discovery/Maintenance Protocol NDM Neighbor Discovery/Maintenance Protocol
Note, it is assumed that basic neighbor discovery operation is Note, it is assumed that basic neighbor discovery operation is
implemented by the MAC/link-layer protocols. Thus the NDM protocol implemented by the MAC/link-layer protocols. Thus the NDM protocol
remains unspecified here. remains unspecified here.
Haas, Pearlman Expires December 1999 [Page
8]
INTERNET DRAFT The Zone Routing Protocol June
1999
4. Implementation Details 4. Implementation Details
4.1 The IntrAzone Routing Protocol (IARP) 4.1 The IntrAzone Routing Protocol (IARP)
The IARP can be implemented through various proactive protocols. We The Intrazone Routing Protocol (IARP) is responsible for proactively
present here an implementation based on a modified version of the maintaining routes within each node's routing zone. This can be achieved
Distance Vector algorithm. Routing information to a node is limited through a variety of different implementations. In fact, many
to the the routing zone of that node. In this version, routing traditional proactive protocols can be modified to serve as an IARP by
information consists of the route cost and the IP addresses of the limiting the range of route updates to the boundary of routing zones.
route destination and next two hops to the destination. The second hop
In this draft, we detail implementations for both a Distance-Vector
and a Link-State IARP. The convergence problems typically associated
with
the Distance-Vector approach are less of a liability in the IARP
implementation because of the finite hop count imposed by the routing
zone
radius. Additionally, techniques such as "hold-downs", "split horizons"
and "poison reverse" can be used to prevent instabilities. A stable
Distance Vector IARP implementation converges a rate comparable to
Link-State IARP, and generally with less control traffic and reduced
computational overhead. However, the Link-State IARP provides a complete
view of the routing zone topology, making it a favorable option for some
applications (including "on-line" routing zone re-sizing).
4.1.1 Distance Vector (with split horizon) IARP
In this version of the IARP, exchanged routing messages consist of the
route cost (including hop count) and the IP addresses of the route's
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. is included to identify routes where a node is it's own second hop.
This particular looping condition can result in the "counting to This particular looping condition result in the "counting to
infinity" problem. By deleting these routes, this problem can be infinity" problem. By deleting these routes, this problem can be
avoided, allowing the IARP to converge faster. avoided, allowing the IARP to converge faster.
A node may receive new route information either from a received IARP A node may receive new route information either from a received IARP
packet or from an interrupt generated by its Neighbor Discovery / packet or from an interrupt generated by its Neighbor Discovery /
Maintenance (NDM) proces*. In the special case when a host has Maintenance (NDM) process*. In the special case when a host has
discovered a neighor, the IARP is responsible for sending to the new discovered a neighbor, the IARP is responsible for sending to the new
neighbor the shortest route to each host which is common to both of 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 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 routing zone radius). The node then records the new route information
in its Intrazone Routing Table. If the shortest path to the host has in its Intrazone Routing Table. If the shortest path to the host has
changed, the terminal broadcasts an IARP packet reflecting the changed, the terminal broadcasts an IARP packet reflecting the
change. change.
* IARP relies on the services of a separate protocol (referred to * IARP relies on the services of a separate protocol (referred to
here as the Neighbor Discovery/Maintenance Protocol) to provide here as the Neighbor Discovery/Maintenance Protocol) to provide
current information about a host's neighbors. At the least, this current information about a host's neighbors. At the least, this
information must include the IP addresses of all the neighbors. information must include the IP addresses of all the neighbors.
The IARP can be readily configured to support supplemental The IARP can be readily configured to support supplemental
neighbor information, such as link cost. link quality metrics.
Haas, Pearlman Expires December 1999 [Page
9]
INTERNET DRAFT The Zone Routing Protocol June
1999
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address | | Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Subnet Mask (Optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop #1 Address | | Next Hop #1 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop #2 Address | | Next Hop #2 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
|Hop Cnt| | RESERVED | Metric Type | Metric Value | |
+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | Route
\| |/ Metrics
\ /
(optional)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Hop Count |
+-+-+-+-+-+-+-+-+
Field Description: Field Description:
* Destination Address (32 bits) * Destination Address (32 bits)
IP address of the destination host IP address of the destination host
* Destination Subnet Mask (32 bits)
IP subnet mask associated with the destination
* Next Hop # 1 Address (32 bits) * Next Hop # 1 Address (32 bits)
IP address of the "next hop" host to the destination host IP address of the "next hop" host to the destination host
* Next Hop # 2 Address (32 bits) * Next Hop # 2 Address (32 bits)
IP address of the Next Hop #1 's "next hop" host to IP address of the Next Hop #1 's "next hop" host to
the destination host the destination host
* Hop Count (4 bits)
* Node/Link Metrics (X * 32 bits)
This section of the packet is used to report the quality of
this link (or link source node).
* Metric Type (8 bits)
Type of metric being reported
(based on pre-defined metric types)
* Metric Value (16 bits)
Value of node / link metric specified by Metric Type
* Hop Count (8 bits)
Length of the route to the destination host, measured Length of the route to the destination host, measured
in hops in hops
B. Structures Haas, Pearlman Expires December 1999 [Page
10]
INTERNET DRAFT The Zone Routing Protocol June
1999
B. Data Structures
B.1 Intrazone Routing Table B.1 Intrazone Routing Table
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +---------+--------|-----------------------------------------+
| | Routes | | Dest | Subnet | Routes |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Addr | Mask |-----------+-----------+-----+-----------+
| Host | 0 | 1 | ==> | M-1 | | | | 0 | 1 | ==> | M-1 |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +---------+--------|-----------+-----------+-----+-----------+
| | Next : Hop | Next : Hop | ==> | Next : Hop | | | | | | ==> | |
| | Hop : Count | Hop : Count | | Hop : Count | |---------+--------|-----------|-----------|-----|-----------|
+-+-+-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-:-+-+-+-+-+-+-+-+-+-+-:-+-+-+-+ | | | | | ==> | |
| | : | : | | : | |---------+--------|-----------|-----------|-----|-----------|
|-----------|-------:-------|-------:-------|-----|-------:-------| | | | | | | | ==> | |
| | : | : | | : | +---------+--------|----| |----+-----------+-----+-----------+
|-----------|-------:-------|-------:-------|-----|-------:-------| | |
| | : | : | | : | | +---\ +----------|--+--+ +--+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-----/ | | | |...| |
+----------|--+--+ +--+
Next Hop route
node ID metrics
C. Interfaces C. Interfaces
C.1 Higher Layer (N/A) C.1 Higher Layer (N/A)
C.2 Lower Layer (IP) C.2 Lower Layer (IP)
C.1.1 Send() (specified in IP standard) C.1.1 Send() (specified in IP standard)
C.1.2 Deliver() (specified in IP standard) C.1.2 Deliver() (specified in IP standard)
C.3 NDM C.3 NDM
C.3.1 Neighbor_Lost(host) C.3.1 Neighbor_Lost(host,mask,metric)
Used by the NDM to notify the IARP that direct contact Used by the NDM to notify the IARP that direct contact
has been lost with "host". has been lost with "host" (with subnet mask "mask").
C.3.2 Neighbor_Found(host) Any node/link quality measurements are reported in
the "metric" list.
C.3.2 Neighbor_Found(host,mask,metric)
Used by the NDM to notify the IARP that direct contact Used by the NDM to notify the IARP that direct contact
has been confirmed with "host". has been confirmed with "host" (with subnet mask "mask").
Any node/link quality measurements are reported in
the "metric" list.
C.4 IERP C.4 IERP
C.4.1 Zone_Node_Lost(host) C.4.1 Zone_Node_Lost(host)
Used by IARP to notify the IERP that a node no longer Used by IARP to notify the IERP that a node no longer
exists within the routing zone. exists within the routing zone.
Haas, Pearlman Expires December 1999 [Page
11]
INTERNET DRAFT The Zone Routing Protocol June
1999
D. State Machine D. State Machine
The IARP protocol consists of only one state (IDLE). Therefore, The IARP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The IARP immediately no state transitions need to be specified. The IARP immediately
acts upon an event and then returns back to the IDLE state. 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 Notes: 1) X is used as a label for the host running this state
machine. machine.
2) INF is a reserved field value corresponding to 2) INF is a reserved field value corresponding to
"infinity". "infinity".
skipping to change at page 12, line 5 skipping to change at line 932
D.3 D.3
Event: An IARP packet is received containing route Event: An IARP packet is received containing route
information to a destination D. The hop count is information to a destination D. The hop count is
EQUAL TO the routing zone radius. The second EQUAL TO the routing zone radius. The second
next-hop is NOT EQUAL to X. next-hop is NOT EQUAL to X.
Action: The received route is recorded in the Intrazone Action: The received route is recorded in the Intrazone
Routing Table. Routing Table.
Haas, Pearlman Expires December 1999 [Page
12]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.4 D.4
Event: An IARP packet is received containing route Event: An IARP packet is received containing route
information to a destination D. The hop count is information to a destination D. The hop count is
equal to INF. equal to INF.
Action: The route to D is removed from the Intrazone Action: The route to D is removed from the Intrazone
Routing Table. Routing Table.
1) If the Intrazone Routing Table still 1) If the Intrazone Routing Table still
contains a route to D and the length of the contains a route to D and the length of the
shortest route has increased due to the route shortest route has increased due to the route
skipping to change at page 13, line 5 skipping to change at line 985
shortest route has increased due to the route shortest route has increased due to the route
removal, then the an IARP packet containing the removal, then the an IARP packet containing the
shortest route to N through X is broadcasted. shortest route to N through X is broadcasted.
2) If the Intrazone Routing Table contains no 2) If the Intrazone Routing Table contains no
more routes to N, then an IARP packet containing more routes to N, then an IARP packet containing
a route to D through X with hop count of INF is a route to D through X with hop count of INF is
broadcast. A "Host Lost" interrupt is generated broadcast. A "Host Lost" interrupt is generated
to alert the IERP that D has moved beyond the to alert the IERP that D has moved beyond the
routing zone. routing zone.
Haas, Pearlman Expires December 1999 [Page
13]
INTERNET DRAFT The Zone Routing Protocol June
1999
E. Pseudocode Implementation E. Pseudocode Implementation
We define two complimentary operations on packets:
extract(packet) and load(packet)
extract (packet)
extracts the fields of the IARP packet to the following
variables: {dest, mask, next_hop_1, next_hop_2,
route_metric,
hop_count}
load (packet)
loads the values of the aforementioned variables into
the fields of the IARP packet.
E.1 Update Intrazone Routing Table E.1 Update Intrazone Routing Table
if (packet arrived) if (packet arrived)
{host, route->next_hop, next_next_hop, route->hop_count} extract(packet)
<-- packet
else else
{ {
{host} <-- intrpt {dest,mask,metric} <-- intrpt
route->next_hop=host next_hop_1=dest
if (type(intrpt) == "Neighbor Found") if (type(intrpt) == "Neighbor Found")
{ {
for dest = each host in Intrazone_Routing_Table for d = each node in Intrazone_Routing_Table
{ {
best_route = Intrazone_Routing_Table[dest,0] best_route = get_shortest_route(Intrazone_Routing_Table,d)
mask = get_mask(Intrazone_Routing_Table, d)
if (best_route->hop_count < ROUTING_ZONE_RADIUS) if (best_route->hop_count < ROUTING_ZONE_RADIUS)
{ {
packet <--{dest,my_id,best_route->next_hop, packet<--{d,mask,MY_ID,best_route->next_hop,
best_route->hop_count+1} best_route->metric,best_route->hop_count+1}
send(packet,host) send(packet,dest)
} }
} }
route->hop_count=1 hop_count=1
} }
else else
route->hop_count=INF hop_count=INF
} }
former_best_route = Intrazone_Routing_Table[host,0] former_best_route = get_shortest_route(Intrazone_Routing_Table,dest)
if (route->hop_count < INF)
if(route->next_next_hop != my_id Haas, Pearlman Expires December 1999 [Page
add(Intrazone_Routing_Table[host], route) 14]
INTERNET DRAFT The Zone Routing Protocol June
1999
if (hop_count < INF)
{
if(next_hop_2 != MY_ID)
{
link_metric = get_metric(Intrazone_Routing_Table, next_hop_1)
route_metric = add_metric(route_metric, link_metric)
add(Intrazone_Routing_Table, {dest,mask,next_hop_1,
route_metric,hop_count})
}
}
else else
remove(Intrazone_Routing_Table[host], route) remove(Intrazone_Routing_Table, {dest, next_hop_1})
best_route = Intrazone_Routing_Table[host,0] best_route = get_shortest_route(Intrazone_Routing_Table,dest)
if (best_route != NULL) if (best_route != NULL)
{ {
if (best_route->hop_count != former_best_route->hop_count if (best_route->hop_count != former_best_route->hop_count
&& best_route->hop_count < ROUTING_ZONE_RADIUS) (AND) best_route->hop_count < ROUTING_ZONE_RADIUS)
{ {
packet <-- {host, my_id, best_route->next_hop, packet <-- {dest,mask,MY_ID,best_route->next_hop,
best_route->hop_count+1} best_route->metric,best_route->hop_count+1}
broadcast(packet) send(packet,BROADCAST)
} }
} }
else else
{ {
force_intrpt("IERP","Zone Node Lost",{host}) force_intrpt("IERP","Zone Node Lost",{dest})
packet <-- {host, my_id, my_id, INF} packet <-- {dest, mask, MY_ID, MY_ID, NULL, INF}
broadcast(packet) send(packet,BROADCAST)
} }
Haas, Pearlman Expires December 1999 [Page
15]
INTERNET DRAFT The Zone Routing Protocol June
1999
4.1.2 Link State IARP
In this version of the IARP, nodes compute intrazone routes based on the
link state (neighbor connectivity) of each routing zone node. A node may
receive link state updates either from an IARP link state packet or from
an interrupt generated by its Neighbor Discovery / Maintenance (NDM)
process*. Link states are maintained in a Link State Table. When all
pending link state updates have been received (full link state updates
may
contain multiple links and span multiple packets), the routing table is
recomputed, using a minimum spanning tree algorithm. The Link State
Table
is then updated to remove links that lie outside of the routing zone.
All
new link state updates for non-peripheral routing zone nodes are
forwarded
to all neighbors. In addition, if a new neighbor is discovered, the new
neighbor is sent the FULL link states of all non-peripheral routing zone
nodes.
* 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
link quality metrics.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link State ID | Zone Radius | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Destination Subnet Mask (Optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | Link
\| |/ Metrics
\ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
Haas, Pearlman Expires December 1999 [Page
16]
INTERNET DRAFT The Zone Routing Protocol June
1999
Field Description:
* Link Source Address (32 bits)
IP address of the reported link's source node.
* Link Destination Address (32 bits)
IP address of the reported link's destination node.
* Packet Source Address (32 bits)
IP address of the node that sent this packet.
(Used to account for any outstanding link state information)
* Link State ID (16 bits)
Sequence number used to track the link state history of
the Link Source node.
* Zone Radius (8 bits)
Routing zone radius of the link's source node. Determines the
extent that link state information propagates.
* Flags (8 bits)
Flags(0) Full Link Information
Indicates whether this link state information was sent as:
(0) a PARTIAL link state update
OR
(1) part of a FULL update of all the
link source's current links
Flags(1) Current Link State Update
Indicates whether more link state information is pending
for THIS link state update {link_source,state_id}
(0) INCOMPLETE
(1) COMPLETE
Flags(2) All Link State Updates
Indicates whether more link state updates are pending
(0) INCOMPLETE
(1) COMPLETE
Flags(3) Link Destination Subnet Mask
(0) INCLUDED
(1) NOT INCLUDED
Flags(4) Link Status
(0) DOWN
(1) UP
Flags(5..7) RESERVED for future use.
Haas, Pearlman Expires December 1999 [Page
17]
INTERNET DRAFT The Zone Routing Protocol June
1999
* Node/Link Metrics (X * 32 bits)
This section of the packet is used to report the quality of
this link (or link source node).
* Metric Type (8 bits)
Type of metric being reported
(based on pre-defined metric types)
* Metric Value (16 bits)
Value of node / link metric specified by Metric Type
B. Data Structures
B.1 Intrazone Routing Table
+---------+--------|-----------------------------------------+
| Dest | Subnet | Routes |
| Addr | Mask |-----------+-----------+-----+-----------+
| | | 0 | 1 | ==> | M-1 |
+---------+--------|-----------+-----------+-----+-----------+
| | | | | ==> | |
|---------+--------|-----------|-----------|-----|-----------|
| | | | | ==> | |
|---------+--------|-----------|-----------|-----|-----------|
| | | | | | | ==> | |
+---------+--------|----| |----+-----------+-----+-----------+
| |
| +---\ +----------|--+--+ +--+
+-----/ | | | |...| |
+----------|--+--+ +--+
Next Hop route
node ID metrics
Haas, Pearlman Expires December 1999 [Page
18]
INTERNET DRAFT The Zone Routing Protocol June
1999
B.2 Link State Table
+--------+--------+------------+
| Link | Zone | Link State | Link State Information
| Source | Radius | ID |
+--------+--------+------------+ +---|---|-----|-+
+---|---|-----|-+
| | | |---> | | | | | | |...| | | | |
| | **
| | +------------+ +---|---|-----|-+
+---|---|-----|-+
| | | |-+
| | +------------+ | +---|---|-----|-+
: : : || : +-> | | | | | | |
: : : \||/ : +---|---|-----|-+
: : : \/ :
| | +------------+ +---+---|-----|-+
| | | |---> | | | | | | |
+--------+--------+------------+ +---+---|-----|-+
| || | || | || | (a) (b) (c) (d)
: || : || : || :
: \||/ : \||/ : \||/ :
| \/ | \/ | \/ |
+--------+--------+------------+
(a) Link Destination Address
(b) Link Destination Subnet Mask
(c) Link Metrics
(d) Forward Flag (indicates if link state information has
been forwarded)
** The first link state entry for each link source
contains the complete link state information
corresponding to the Link State ID.
Subsequent entries contain only changes of a single
link state.
A FULL link state entry of link state #k and
a PARTIAL entry of link state #(k+1) can be
merged into a FULL link state entry of
link state #(k+1)
B.3 Pending Link State List
(list of neighbors in the process of sending link state updates)
+----------+ +----------+ +----------+
| | ---> | | . . . | | (node addresses)
+----------+ +----------+ +----------+
B.4 New Neighbors List
(list of new neighbors to receive a copy Link State Table,
upon completion of updates)
+----------+ +----------+ +----------+
| | ---> | | . . . | | (node addresses)
+----------+ +----------+ +----------+
Haas, Pearlman Expires December 1999 [Page
19]
INTERNET DRAFT The Zone Routing Protocol June
1999
B.5 Former Routing Zone Nodes
(list of routing zone nodes, prior to routing table updates)
+----------+ +----------+ +----------+
| | ---> | | . . . | | (node addresses)
+----------+ +----------+ +----------+
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,mask,metric)
Used by the NDM to notify the IARP that direct contact
has been lost with "host" (with subnet mask "mask").
Any node/link quality measurements are reported in
the "metric" list.
C.3.2 Neighbor_Found(host,mask,metric)
Used by the NDM to notify the IARP that direct contact
has been confirmed with "host" (with subnet mask "mask").
Any node/link quality measurements are reported in
the "metric" list.
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.
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 link state packet is received.
Action: The link state update is recorded in the Link State
Table.
If more link state updates are pending, then the IARP
returns to an idle state. Otherwise, X rebuilds its
routing table. Links that lie outside of the routing
zone
are removed from the Link State Table. X sends its
neighbors all previously unforwarded link state updates
from its NON-peripheral nodes. Finally, all neighbors
in the New Neighbor List are sent the link states of
X's
NON-peripheral nodes, and the New Neighbor List is
cleared.
Haas, Pearlman Expires December 1999 [Page
20]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.2
Event: A "Neighbor Found" interrupt is received, indicating
the discovery of a neighbor N.
Action: X's new link to N is recorded in the Link State Table
and
N is added to the New Neighbors List. If more link
state
updates are pending, then the IARP returns to an idle
state. Otherwise, X rebuilds its routing table. Links
that lie outside of the routing zone are removed from
the
Link State Table. X sends its neighbors all previously
unforwarded link state updates from its NON-peripheral
nodes. Finally, all neighbors in the New Neighbor List
are sent the link states of X's NON-peripheral nodes,
and
the New Neighbor List is cleared.
D.3
Event: A "Neighbor Lost" interrupt is received, indicating
that node N is no longer a neighbor of X.
Action: The lost link to neighbor N is removed from the Link
State Table and N is removed from the New Neighbor
List.
If more link state updates are pending, then the IARP
returns to an idle state. Otherwise, X rebuilds its
routing table. Links that lie outside of the routing
zone are removed from the Link State Table. X sends
its
neighbors all previously unforwarded link state updates
from its NON-peripheral nodes. Finally, all neighbors
in the New Neighbor List are sent the link states of
X's
NON-peripheral nodes, and the New Neighbor List is
cleared.
E. Pseudocode Implementation
We define two complimentary operations on packets:
extract(packet) and load(packet)
extract (packet)
extracts the fields of the IARP packet to the following
variables: {link_source, link_dest, pk_source, state_id,
radius, flags, mask, link_metric}
* full_link_state -> flag(0)
* current_update -> flag(1)
* all_updates -> flag(2)
* mask -> flag(3)
* link_status -> flag(4)
load (packet)
loads the values of the aforementioned variables into
the fields of the IARP packet.
Haas, Pearlman Expires December 1999 [Page
21]
INTERNET DRAFT The Zone Routing Protocol June
1999
E.1 Update Intrazone Routing Table
if (packet arrived)
{
extract(packet)
my_link_changed = FALSE
}
else
{
{link_dest,mask,link_metric} <-- intrpt
link_source = MY_ID
pk_source = MY_ID
state_id = MY_LINK_STATE_ID
radius = MY_ROUTING_ZONE_RADIUS
full_link_state = 0
current_update = COMPLETE
all_updates = COMPLETE
if (type(intrpt) == "Neighbor Found")
link_status = UP
else
link_status = DOWN
my_link_changed = TRUE
}
add(Pending_Link_State_List, link_from_id)
status = add(Link_State_Table,link_source, link_dest, mask, radius,
link_metric, state_id, flags)
if (status == NEW_LINK_INFO)
{
cum_status = UPDATE_IN_PROGRESS
if(my_link_changed)
{
if (link_status == UP)
add(New_Neighbor_List, link_dest)
else
remove(New_Neighbor_List, link_dest)
MY_LINK_STATE_ID++
}
}
if(all_updates == COMPLETE)
remove(Pending_Link_State_List, link_from_id)
Haas, Pearlman Expires December 1999 [Page
22]
INTERNET DRAFT The Zone Routing Protocol June
1999
if(empty(Pending_Link_State_List) (AND)
cum_status == UPDATE_IN_PROGRESS)
{
for(each node (BELONGING TO) Intrazone_Routing_Table)
add(Former_Routing_Zone_Nodes, node)
rebuild = TRUE;
while (rebuild)
{
Intrazone_Routing_Table
=
construct_spanning_tree(Link_State_Table);
rebuild = update(Link_State_Table);
}
broadcast_link_state_updates(Link_State_Table);
for (each node (BELONGING TO) New_Neighbor_List))
send_link_state_table(Link_State_Table, node);
clear(New_Neighbor_List)
cum_status = UPDATE_COMPLETE;
for (each node (BELONGING TO) Former_Routing_Zone_Nodes)
{
if(node !(BELONGS TO) Intrazone_Routing_Table)
force_intrpt("IERP","Zone Node Lost",{node})
}
clear(Former_Routing_Zone_Nodes)
}
Haas, Pearlman Expires December 1999 [Page
23]
INTERNET DRAFT The Zone Routing Protocol June
1999
4.2 IntErzone Routing Protocol (IERP) 4.2 IntErzone Routing Protocol (IERP)
The Interzone Routing Protocol (IERP) is responsible for discovering The Interzone Routing Protocol (IERP) is responsible for discovering
and maintaining routes to hosts which are beyond a node's routing and maintaining routes to hosts which are beyond a node's routing
zone. The IERP acquires routing information reactively, exploiting zone. The IERP acquires routing information reactively, exploiting
the knowledge of the routing zone topology through the bordercasting the knowledge of the routing zone topology through the bordercasting
delivery service. delivery service.
This version of the IERP extends the basic query / reply mechanism This version of the IERP extends the basic query / reply mechanism
described in Section 3. In the basic protocol, queries are described in Section 3. In the basic protocol, queries are
terminated before reaching the query destination. This provides terminated before reaching the query destination. This provides
a faster response to the route query than if the destination, D, a faster response to the route query than if the destination, D,
were to respond directly. However, because D never receives the were to respond directly. However, because D never receives the
query, it does not acquire a route back to the source, S. If 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 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 bi-directional nature of many applications), a separate route query
from D to S would have to be initiated. This substantial overhead 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 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 discovers D in its routing zone. We refer to this as a
EXTENSION. QUERY_EXTENSION.
Both the source and destination can acquire routes to each other Both the source and destination can acquire routes to each other
through the BRP route accumulation mechanisms (to be discussed through the BRP route accumulation mechanisms (to be discussed
later). Distributing route information in the caches of the later). Distributing route information in the caches of the
route's nodes can significantly reduce the size of the IERP packets route's nodes can significantly reduce the size of the IERP packets
and provide for a faster query response. On the other hand, QOS and provide for a faster query response. On the other hand, QOS
requirements for a particular application may favor a source requirements for a particular application may favor a source
specified route. (rather than a distributed next-hop approach). specified route. (rather than a distributed next-hop approach).
Source routing requires that the discovered route information be Source routing requires that the discovered route information be
accumulated in the IERP packets, rather than cached. This IERP accumulated in the IERP packets, rather than cached. This IERP
implementation satisfies the demands for rapid query response implementation satisfies the demands for rapid query response
and source routing support by two stages of route reporting. In the and source routing support by two stages of route reporting. In the
first two stages, route information is cached by the route's nodes first two stages, route information is cached by the route's nodes
(when possible). Next-hop route are quickly returned to the source (when possible). Next-hop route are quickly returned to the source
in QUERY-REPLY packets and forwarded to the destination in QUERY- in ROUTE_REPLY packets and forwarded to the destination in QUERY_
EXTENSION packets. At this point, bi-directional connectivity is EXTENSION packets. At this point, bi-directional connectivity is
established. In the third stage, the source and destination can established. In the third stage, the source and destination can
provide each other with complete source routes, by sending each provide each other with complete source routes, by sending each
other ROUTE-ACCUMULATION packets. As these packets traverse the other ROUTE_ACCUMULATION packets. As these packets traverse the
route, the cached route information is accumulated in the packets, route, the cached route information is accumulated in the packets,
thereby constructing the desired source route. thereby constructing the desired source route.
Variations on this IERP implementation can be realized by combining Variations on this IERP implementation can be realized by combining
or eliminating some of these stages. For example, if source routing or eliminating some of these stages. For example, if source routing
is not desired, the ROUTE-ACCUMULATION stage can be eliminated. is not desired, the ROUTE_ACCUMULATION stage can be eliminated.
Also, if all of the route's nodes elect not to cache the routing Also, if all of the route's nodes elect not to cache the routing
information (perhaps due to storage limitations), then the QUERY information (perhaps due to storage limitations), then the ROUTE_
REPLY and QUERY-EXTENSION packets essentially serve the role of REPLY and QUERY_EXTENSION packets essentially serve the role of
ROUTE-ACCUMULATION packets, obviating the need for a separate ROUTE_ACCUMULATION packets, obviating the need for a separate
ROUTE-ACCUMULATION stage. ROUTE_ACCUMULATION stage.
Haas, Pearlman Expires December 1999 [Page
24]
INTERNET DRAFT The Zone Routing Protocol June
1999
Because each node proactively maintains the local topology of its Because each node proactively maintains the local topology of its
routing zone, it is not necessary for a source route to specify routing zone, it is not necessary for a source route to specify
every hop along the route (i.e. strict source routing). A properly every hop along the route (i.e. strict source routing). A properly
chosen subset of the complete source route can be used to specify chosen subset of the complete source route can be used to specify
the route to the destination, and where desirable, the reverse route the route to the destination, and where desirable, the reverse route
back to the source. The IERP supports such an optimization through back to the source. The IERP supports such an optimization through
a final ROUTE-OPTIMIZATION stage. The details of the route a final ROUTE_OPTIMIZATION stage. The details of the route
optimization are described in the BRP specification. Upon optimization are described in the BRP specification. Upon
completion of the ROUTE-OPTIMIZATION stage, sufficient routing zone completion of the ROUTE_OPTIMIZATION stage, sufficient routing zone
membership is acquired for each node in the route so that the source membership is acquired for each node in the route so that the source
route may be reduced (by translating this route reduction into route may be reduced (by translating this route reduction into
an appropriate set covering problem, and employing a suitable an appropriate set covering problem, and employing a suitable
heuristic). heuristic).
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
| S | . . . . | Y | . . . | D | | S | . . . . | Y | . . . | D |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
(1) search for QUERY (1) search for ROUTE_QUERY
route |--------------------------> route |-------------------------->
QUERY QUERY (2) establish ROUTE_REPLY EXTENSION
(2) establish REPLY EXTENSION
connectivity <--------------------------| connectivity <--------------------------|
|=============> |=============>
(3) provide ROUTE-ACCUMULATION (3) provide ROUTE_ACCUMULATION
(OPTIONAL)
source route |----------------------------------------> source route |---------------------------------------->
<========================================| <========================================|
(4) optimize ROUTE-OPTIMIZATION (4) optimize ROUTE_OPTIMIZATION
(OPTIONAL)
source route <----------------------------------------| source route <----------------------------------------|
|========================================> |========================================>
Sequence of the IERP Route Discovery Stages Sequence of the IERP Route Discovery Stages
Haas, Pearlman Expires December 1999 [Page
25]
INTERNET DRAFT The Zone Routing Protocol June
1999
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 | Rsvd | Hops Left | Query ID | | Type | TTL | Hop Count | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bad Link Source Address (repair only) | | Current | ROF Ptr | Num Dests = D | Num Nodes = N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query ID | Reply ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query/Route Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Replying Node Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bad Link Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Query/Route Destination (1) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Query/Route Destination (2) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| | Dests
\| |/ |
\ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Query/Route Destination (D) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Next IERP Address | | | Next IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ BRP
| Next BRP Address | fields
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Next BRP Address | BRP
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fields
| Prev IERP Address | | | Prev IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Hop 0 Address (Source) | | | Intermediate Node (1) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Hop 1 Address | | | Intermediate Node (2) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| |
route(1:N)
| | | | | |
| | | \| |/ |
\| |/ route
\ / | \ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| |
| Hop (N-2) Address | | | Intermediate Node (N) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Node | Metric Type |D| Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Hop (N-1) Address (Destination) | | | Node | Metric Type |D| Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | Node/
| |
Segment
\| |/
Metric(s)
\ / |
Haas, Pearlman Expires December 1999 [Page
26]
INTERNET DRAFT The Zone Routing Protocol June
1999
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Node | Metric Type |D| Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Route Optimization Flags (Node 0 == Source) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Route Optimization Flags (Node 1) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| | R
\| |/ O
\ / F
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Route Optimization Flags (Node N) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Route Optimization Flags (Node N+1 == Dest) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Flags (optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field Description: Field Description:
* Type (4 bits) * Type (8 bits)
Identifies the type of IERP packet. The current version Identifies the type of IERP packet. The current version
of IERP contains five packet types: of IERP contains five packet types:
QUERY: ROUTE_QUERY:
request for an Interzone source route to the request for an Interzone source route to the
destination specified by the Destination destination specified by the Destination
IP Address IP Address
QUERY-EXTENSION: QUERY_EXTENSION:
extension of a QUERY packet sent from the extension of a QUERY packet sent from the
node that discovers the Destination to the node that discovers the Destination to the
Destination itself. Destination itself.
QUERY-REPLY: ROUTE_REPLY:
response to a QUERY packet, sent from the node response to a ROUTE_QUERY packet, sent from the node
that discovers the Destination back to the that discovers the Destination back to the Source.
Source. At a minimum, the QUERY-REPLY contains At a minimum, the ROUTE_REPLY contains
next-hop route information to the Destination. next-hop route information to the Destination.
(In general, returns the source route up to (In general, returns the source route up to
the first node which has cached routing the first node which has cached routing
information. If no nodes have cached routing information. If no nodes have cached routing
information, then the complete source route is information, then the complete source route is
returned.) returned.)
ROUTE-ACCUMULATION (optional): ROUTE_ACCUMULATION (optional):
sent by the Source to the Destination, in sent by the Source to the Destination, in
response to a QUERY-REPLY, and sent by the response to a ROUTE_REPLY, and sent by the
Destination to the Source, in response to a Destination to the Source, in response to a
QUERY-EXTENSION. Routing information cached QUERY_EXTENSION. Routing information cached
at the route's nodes is accumulated in this at the route's nodes is accumulated in this
packet, providing a complete source route at packet, providing a complete source route at
the destination of this packet. the destination of this packet.
ROUTE-OPTIMIZATION (optional): Haas, Pearlman Expires December 1999 [Page
sent by the Source to the Destination, and 27]
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) INTERNET DRAFT The Zone Routing Protocol June
Sequence number which, along with the Source Address 1999
(see below) uniquely identifies any route query in the
network.
* Hops Left (8 bits) ROUTE_OPTIMIZATION (optional):
sent by the Source to the Destination, and by the
Destination to the Source, in response to a
ROUTE_ACCUMULATION packet. Route Optimization
Flags (ROF) are appended to this packet,
reflecting the mutual routing zone membership
of each node in the source route.
* TTL (Time to Live) (8 bits)
Number of hops that a route query may continue to Number of hops that a route query may continue to
propagate. This field allows a querying node to propagate. This field allows a querying node to
configure the depth of a route search, to configure the depth of a route search, in order to
control the amount of IERP traffic generated. control the amount of IERP traffic generated.
* Bad Link Address (32 bits) * Hop Count (8 bits)
Hop count from source to current node (ROUTE_QUERY,
QUERY_EXTENSION) or hop count from source to route
destination
(ROUTE_REPLY, ROUTE_ACCUMULATION, ROUTE_OPTIMIZATION).
* Flags (8 bits)
Flags(0) ANY destination (0) / ALL destination (1)
In the case of multiple destinations, specifies
whether
the ROUTE_QUERY should return routes for ANY
specified
destination, or ALL specified destinations.
In the case of a single MULTICAST IP address,
specifies
whether the ROUTE_QUERY should return routes to ANY
member of the multicast group, or ALL members of the
multicast group.
Flags(1) Passed Bad Link Source
In the case of a "route repair", indicates whether
the
ROUTE_REPLY has passed the Bad Link Source node.
Flags(2..7) RESERVED for future use
* Current (8 bits)
INDEX of the route (see below) corresponding to the route
node
that has most recently received this packet. (the first
node
in the route has an index of 1).
* ROF Pointer (8 bits)
Pointer to the starting location of the Route Optimization
Flags (ROUTE_OPTIMIZATION phase). The ROF Pointer is
measured
in units of 32 bit words from the front of the packet.
* Number of Destinations = D (8 bits)
Number of destinations included in the route query/reply
packet.
This allows multiple route discoveries to be consolidated
into a common route query process. The multiple query
destinations feature is particularly useful for routing to
a
multicast group with known members, or for locating
downstream
nodes during the route repair phase.
Haas, Pearlman Expires December 1999 [Page
28]
INTERNET DRAFT The Zone Routing Protocol June
1999
* Number of Nodes = N (8 bits)
Number of nodes IP addresses appearing in the route
specification.
* Query ID (16 bits)
Sequence number which, along with the Query Source Address
(see below) uniquely identifies any ROUTE_QUERY in the
network.
* Reply ID (16 bits)
Sequence number which, along with the Replying Node Address
(see below) uniquely identifies any ROUTE_REPLY in the
network
* Query/Route Source Address (32 bits)
IP address of the node that initiates the ROUTE_QUERY.
In subsequent stages, this corresponds to the IP address of
the
discovered route's source node.
* Replying Node Address (32 bits)
IP address of the node that initiates the ROUTE_REPLY. Note
that this is usually NOT the destination node.
* Bad Link Source Address (32 bits)
Used during route repairs. Contains the IP Address Used during route repairs. Contains the IP Address
corresponding to the source of routes failed link. corresponding to the source of routes failed link.
* Query/Route Destination Addresses (D * 32 bits)
List of IP addresses to be located during the ROUTE_QUERY
phase.
(Either ANY or ALL addresses, depending on the setting of
Flags(0))
In subsequent stages, this field contains the IP address of
the
discovered route's (single) destination node.
* Next IERP Address (32 bits) * Next IERP Address (32 bits)
IP address of the next IERP recipient IP address of the next IERP recipient
* Next BRP Address (32 bits) * Next BRP Address (32 bits)
IP address of the next BRP recipient. IP address of the next BRP recipient.
(i.e. next hop to the next IERP recipient) (i.e. next hop to the next IERP recipient)
* Prev IERP Address (32 bits) * Prev IERP Address (32 bits)
IP address of the previous IERP recipient IP address of the previous IERP recipient
* 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) * Route (N * 32 bits)
The k-th bit of the n-th flag subfield indicates whether Variable length field that contains the recorded IP
route(k) is located within route(n)'s routing zone. addresses
of nodes along the path traveled by this ROUTE_QUERY packet
from the Query Source.
In subsequent stages (after a route to a Query Destination
has
been discovered), this set of IP addresses provides a
partial
specification of the route between the Route Source and
Route
Destination.
Haas, Pearlman Expires December 1999 [Page
29]
INTERNET DRAFT The Zone Routing Protocol June
1999
* Node/Segment Metrics (X * 32 bits)
This optional section of the packet can be used to
record a variety of node and segment quality measurements.
(In this context, a segment refers to the communication path
between consecutive nodes in the packet's accumulated route.
In the case of neighboring nodes, a segment is equivalent to
a (one-hop) link).
* Node (8 bits)
Index of the route corresponding to a particular node.
* Metric Type (7 bits)
Type of metric being recorded
(based on pre-defined metric types)
* Direction Flag (1 bit)
For segment metrics, specifies either the upstream
segment (toward Query/Route Source) or the downstream
segment (toward Query/Route Dest).
upstream = 0
downstream = 1
* Metric Value (16 bits)
Value of node / segment metric specified by Metric
Type
* ROF (Route Optimization Flags) ((N+2) * 32*ceil((N+2)/32)
bits)
The k-th bit of the n-th ROF subfield indicates whether
Node k is located within Node n's routing zone.
This routing zone membership information, collected This routing zone membership information, collected
during the optional ROUTE-OPTIMIZATION stage, may be during the optional ROUTE_OPTIMIZATION stage, may be
used to determine the shortest possible specification used to determine the shortest possible specification
for the accumulated source route. for the accumulated source route.
B. Structures Haas, Pearlman Expires December 1999 [Page
30]
INTERNET DRAFT The Zone Routing Protocol June
1999
B. Data Structures
B.1 Intrazone Routing Table (See IARP Description) B.1 Intrazone Routing Table (See IARP Description)
B.2 Interzone Routing Table B.2 Interzone Routing Table
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +---------+-----------------------------------------+
| | Routes | | | Routes |
+ Dest +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Dest +-----------+-----------+-----+-----------+
| | 0 | 1 | ==> | M-1 | | | 0 | 1 | ==> | M-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +---------+-----------+-----------+-----+-----------+
| | | | ==> | | | | | | ==> | |
|---------|-----------|-----------|-----|-----------| |---------|-----------|-----------|-----|-----------|
| | | | ==> | | | | | | ==> | |
|---------|-----------|-----------|-----|-----------| |---------|-----------|-----------|-----|-----------|
| | | | | | ==> | | | | | | | | ==> | |
+-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +---------+----| |----+-----------+-----+-----------+
| | | |
\ / | +---\ +------|---|--+--+ +--+
\ / +-----/ | | | | |...| | --+ (node 1)
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +------|---|--+--+ +--+ |
| 0 |==>| 1 |==> ...==>| N-1 | source +------------------------------+
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ route | +------|---|--+--+ +--+
source first (N-1) +->| | | | |...| | --+ (node 2)
host hop hop +------|---|--+--+ +--+ |
| | :
\| |/ :
: \ /
:
| +------|---|--+--+ +--+
+->| | | | |...| | (node N)
+------|---|--+--+ +--+
(a) (b) (c)
(a) Node ID
(b) Required Node Flag
(for Route Optimization)
(c) Node/Link Metric
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 Send() (same interface as IP send()) C.2.1 Send() (same interface as IP send())
Used by the IERP to request transmission of an Used by the IERP to request transmission of an
IERP packet. IERP packet.
C.2.2 Deliver() (same interface as IP deliver()) C.2.2 Deliver() (same interface as IP deliver())
Used by the BRP to alert the IERP of the arrival of a Used by the BRP to alert the IERP of the arrival of a
data packet. data packet.
C.3 IARP C.3 IARP
C.3.1 Zone_Node_Lost(host) C.3.1 Zone_Node_Lost(host)
Used by the IARP to notify the IERP that a node has left Used by the IARP to notify the IERP that a node has left
the routing zone the routing zone
C.4 ICMP C.4 ICMP
C.4.1 Host_Unreachable() (specified in ICMP standard) C.4.1 Host_Unreachable() (specified in ICMP standard)
C.4.2 Source_Route_Failed() (specified in ICMP standard) C.4.2 Source_Route_Failed() (specified in ICMP standard)
Haas, Pearlman Expires December 1999 [Page
31]
INTERNET DRAFT The Zone Routing Protocol June
1999
D. State Machine D. State Machine
The IERP protocol consists of only one state (IDLE). Therefore, The IERP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The IERP immediately no state transitions need to be specified. The IERP immediately
acts upon an event and then returns back to the IDLE state. 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 Note: 1) X is used as a label for the host running this state
machine. machine.
D.1 D.1
skipping to change at page 19, line ? skipping to change at line 1992
Action: Remove every route from the Interzone Routing Table Action: Remove every route from the Interzone Routing Table
which contains H. If any routes containing H are which contains H. If any routes containing H are
found, then a route repair (limited depth route found, then a route repair (limited depth route
discovery) to H is initiated. discovery) to H is initiated.
D.2 D.2
Event: A "Host_Unreachable" interrupt is received from the Event: A "Host_Unreachable" interrupt is received from the
ICMP, indicating an unknown destination host D. ICMP, indicating an unknown destination host D.
Action: A full depth route discovery to D is initiated. Action: A full depth route discovery to D is initiated.
The query_id is incremented and assigned to a new X's query_id is incremented and assigned to a new
QUERY packet. The route is initialized with the ROUTE_QUERY packet. The route is initialized with the
IP addresses of the route's source and destination IP addresses of the route's source and destination
IP addresses (X and D). Finally, the QUERY packet IP addresses (X and D). Finally, the ROUTE_QUERY
packet
is bordercasted. is bordercasted.
D.3 D.3
Event: A "Source_Route_Failed" or "Proactive_Repair" Event: A "Source_Route_Failed" or "Proactive_Repair"
interrupt is received, indicating that the next interrupt is received, indicating that the next
hop, H, specified in a source route does not hop, H, specified in a source route does not
appear within the routing zone. appear within the routing zone.
Action: A limited depth route discovery to H is initiated. Action: A limited depth route discovery to H is initiated.
The query_id is incremented and assigned to a new The query_id is incremented and assigned to a new
QUERY packet. The route is initialized with the ROUTE_QUERY packet. The route is initialized with the
valid portion of the failed route, and the valid portion of the failed route, and the bad link
bad link address field is set with X's IP address, address field is set with X's IP address, to indicate
to indicate the location of the route failure. the location of the route failure.
Finally, the QUERY packet is bordercasted. Finally, the ROUTE_QUERY packet is bordercasted.
D.4 D.4
Event: A QUERY packet is received with a destination that Event: A ROUTE_QUERY packet is received with a destination
that
appears within X's routing zone. appears within X's routing zone.
Action: A QUERY-REPLY is sent back to the query source, and Action: X copies the ROUTE_QUERY packet's contents to a
a QUERY-EXTENSION is sent to the query destination. ROUTE_REPLY, labelling it with its IP address and
incremented reply_id.
A QUERY_EXTENSION is sent to the query destination.
D.5 D.5
Event: A QUERY packet is received with a destination that Event: A ROUTE_QUERY packet is received with a destination
that
DOES NOT appear within X's routing zone. DOES NOT appear within X's routing zone.
Action: The QUERY packet is bordercasted. Action: The ROUTE_QUERY packet is bordercasted.
Haas, Pearlman Expires December 1999 [Page
32]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.6 D.6
Event: A QUERY-EXTENSION packet is received. Event: A QUERY_EXTENSION packet is received.
Action: The packet contents are moved to a ROUTE- Action: The packet contents are moved to a ROUTE_ACCUMULATION
ACCUMULATION packet. The ROUTE-ACCUMULATION packet. The ROUTE_ACCUMULATION packet is sent to the
packet is sent to the query source. query source.
D.7 D.7
Event: A QUERY-REPLY packet is received. Event: A ROUTE_REPLY packet is received.
Action: The packet contents are moved to a ROUTE- Action: The packet contents are moved to a ROUTE_ACCUMULATION
ACCUMULATION packet. The ROUTE-ACCUMULATION packet. The ROUTE_ACCUMULATION packet is sent to the
packet is sent to the query destination. query destination.
D.8 D.8
Event: A ROUTE-ACCUMULATION packet is received. X is not Event: A ROUTE_ACCUMULATION packet is received. X is not
the final destination of this packet the final destination of this packet
(i.e. X != IERP_next). This only occurs when the (i.e. X != IERP_next). This only occurs when the
accumulated route contains a repair accumulated route contains a repair
Action: The bad link is replaced by the path repair in the Action: The bad link is replaced by the path repair in the
Interzone Routing Table. Interzone Routing Table.
D.9 D.9
Event: A ROUTE-ACCUMULATION packet is received. X is Event: A ROUTE_ACCUMULATION packet is received. X is
either the route source or (route destination). either the route source or (route destination).
Action: The (reversed) accumulated route is added to the Action: The (reversed) accumulated route is added to the
Interzone Routing Table or replaces a failed route Interzone Routing Table or replaces a failed route
if the packet specifies a bad link. In addition, if the packet specifies a bad link. In addition,
if X is the ROUTE-ACCUMULATION destination, the if X is the ROUTE_ACCUMULATION destination, the
packet contents may be moved to a ROUTE- packet contents may be moved to a ROUTE_OPTIMIZATION
OPTIMIZATION packet, which is then sent to packet, which is then sent to the query destination
the query destination (query source). (query source).
D.10 D.10
Event: A ROUTE-OPTIMIZATION packet is received. Event: A ROUTE_OPTIMIZATION packet is received.
Action: The routing zone membership information that is Action: The routing zone membership information that is
collected in the ROUTE-OPTIMIZATION packet is collected in the ROUTE_OPTIMIZATION packet is
processed. The resulting optimized route(s) are processed. The resulting optimized route(s) are
added to the Interzone Routing Table. added to the Interzone Routing Table.
E. Pseudocode Implementation E. Pseudocode Implementation
We define two complimentary operations on packets: We define two complimentary operations on packets:
extract(packet) and load(packet) extract(packet) and load(packet)
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, hops_left, query_id, bad_link_source, variables: {type, TTL, hop_count, flags, current_hop_ptr,
next_IERP, next_BRP, prev_IERP, route, flag} query_id, reply_id, source, reply_node,
bad_link_source, dests, next_IERP, next_BRP,
prev_IERP, route, metric, ROF}
Haas, Pearlman Expires December 1999 [Page
33]
INTERNET DRAFT The Zone Routing Protocol June
1999
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 values of:
num_dests = |dests|
num_nodes = |routes|
E.1 Routing Zone Node Lost E.1 Routing Zone Node Lost
{lost_host} <-- intrpt {lost_host} <-- intrpt
repair_link = FALSE repair_link = FALSE
for host = each host in Interzone Routing Table for host = each host in Interzone Routing Table
{ {
for (route = each Interzone route to host) for (route = each Interzone route to host)
{ {
if (lost_host (EXISTS IN) route) if (lost_host (EXISTS IN) route)
skipping to change at page 22, line 30 skipping to change at line 2127
else else
removal_timer = 0 removal_timer = 0
schedule( schedule(
remove(Interzone_Routing_Table[host]->route(m)), remove(Interzone_Routing_Table[host]->route(m)),
removal_timer) removal_timer)
} }
} }
} }
if(repair_link) if(repair_link)
{ {
bad_link = my_id + lost_host dests = lost_host
force_intrpt("IERP","Proactive_Repair", bad_link) force_intrpt("IERP","Proactive_Repair",{MY_ID,dests,ALL})
} }
E.2 Initiate Route Discovery E.2 Initiate Route Discovery
{route} <-- intrpt {source,dests,flag} <-- 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" (OR)
if (type(intrpt) == "Proactive_Repair" ||
type(intrpt) == "Source_Route_Failed") type(intrpt) == "Source_Route_Failed")
{ {
hops_left = MAX_REPAIR_HOPS TTL = MAX_REPAIR_HOPS
bad_link_source = my_id bad_link_source = MY_ID
} }
else else
{ {
hops_left = MAX_FULL_QUERY_HOPS TTL = MAX_FULL_QUERY_HOPS
bad_link_source = NULL bad_link_source = NULL
} }
query_id ++ query_id = MY_QUERY_ID++
load (packet) load (packet)
send (packet, BORDERCAST) send (packet, BORDERCAST)
Haas, Pearlman Expires December 1999 [Page
34]
INTERNET DRAFT The Zone Routing Protocol June
1999
E.3 Receive IERP Packet E.3 Receive IERP Packet
extract(packet) extract(packet)
source=route(0) switch(type)
dest = route(length(route)-1)
switch(pk_type)
{ {
case: QUERY case: ROUTE_QUERY
if (dest (EXISTS IN) Intrazone_Routing_Table) if (dest (EXISTS IN) Intrazone_Routing_Table)
{ {
type = QUERY-REPLY type = ROUTE_REPLY
reply_id = MY_REPLY_ID++
if(bad_link_source) if(bad_link_source)
IERP_next = bad_link_source IERP_next = bad_link_source
else else
IERP_next = source IERP_next = source
load(packet) load(packet)
send(packet) send(packet,IERP_next)
type = QUERY-EXTENSION type = QUERY_EXTENSION
IERP_next = dest IERP_next = dest
load(packet) load(packet)
send(packet) send(packet,IERP_next)
} }
else else
bordercast(packet) send(packet,BORDERCAST)
break break
case: QUERY-EXTENSION case: QUERY_EXTENSION
type = ROUTE-ACCUMULATION type = ROUTE_ACCUMULATION
IERP_next=source IERP_next=source
send(packet) load(packet)
send(packet, IERP_next)
break break
case: QUERY-REPLY case: ROUTE_REPLY
type = ROUTE-ACCUMULATION type = ROUTE_ACCUMULATION
IERP_next = dest IERP_next = dest
load (packet) load (packet)
send (packet) send(packet, IERP_next)
break break
case: ROUTE-ACCUMULATION case: ROUTE_ACCUMULATION
if (bad_link_source) if (bad_link_source)
{ {
path_source_ptr = get_index(route, bad_link_source) if(bad_link_source != source)
path_dest_ptr = get_index(route, dest) repair_src_ptr = get_index(route, bad_link_source)
if (IERP_next == source) else
{ repair_src_ptr = 0
bad_link = bad_link_source + dest
path_repair = route(path_source_ptr:path_dest_ptr) bad_link = {bad_link_source,dest}
} path_repair = {bad_link_source,
if (IERP_next == dest) route(repair_src_ptr+1:|route|),
{ dest}
bad_link = dest + bad_link_source replace_link(Interzone_Routing_Table,IERP,bad_link,
path_repair = reverse(route(path_source_ptr : path_repair)
path_dest_ptr))
}
replace(Interzone_Routing_Table, bad_link,path_repair)
} }
Haas, Pearlman Expires December 1999 [Page
35]
INTERNET DRAFT The Zone Routing Protocol June
1999
else else
{ {
if (my_id == source) if (IERP_next == source)
add(Interzone_Routing_Table, route) add(Interzone_Routing_Table, IERP, dest,
if (my_id == dest) next_hops,metric)
add(Interzone_Routing_Table, reverse(route)) if (IERP_next == dest)
add(Interzone_Routing_Table, IERP,
source, reverse(prev_hops),metric)
} }
if (my_id == IERP_next) if (MY_ID == IERP_next)
{ {
if (my_id == source) if (MY_ID == source)
IERP_next = dest IERP_next = dest
if (my_id == dest) if (MY_ID == dest)
IERP_next = source IERP_next = source
type = ROUTE-OPTIMIZATION type = ROUTE_OPTIMIZATION
load (packet) load (packet)
send (packet) send (packet, IERP_next)
} }
break break
case: ROUTE-OPTIMIZATION
if (my_id == source) case: ROUTE_OPTIMIZATION
add(Interzone_Routing_Table, route, flags) if (MY_ID == source)
if (my_id == dest)
add(Interzone_Routing_Table, reverse(route), flags) add(Interzone_Routing_Table,IERP,dest,route,NO_METRIC,ROF)
if (MY_ID == dest)
add(Interzone_Routing_Table, IERP, source,
reverse(route), NO_METRIC, ROF)
break break
} }
Haas, Pearlman Expires December 1999 [Page
36]
INTERNET DRAFT The Zone Routing Protocol June
1999
4.3 Bordercast Resolution Protocol (BRP) 4.3 Bordercast Resolution Protocol (BRP)
The BRP is a sublayer of the IERP that performs the operations of The BRP is a sublayer of the IERP that performs the operations of
bordercasting, query control, route accumulation and routing zone bordercasting, query control, route accumulation and routing zone
labelling, which form the basis for the route discovery procedure. labelling, which form the basis for the route discovery procedure.
In this BRP implementation, bordercasting is implemented as a series In this BRP implementation, bordercasting is implemented as a series
of unicasted messages to the peripheral nodes. The BRP is able to of unicasted messages to the peripheral nodes. The BRP is able to
identify the peripheral based on the information contained in the identify the peripheral nodes based on the information contained in
Intrazone Routing Table. Rather than unicasting to the peripheral the Intrazone Routing Table. Rather than unicasting to the peripheral
node directly through IP, the bordercasted packets are relayed to node directly through IP, the bordercasted packets are relayed to
the peripheral nodes by the BRP layer. IP is used only to send the peripheral nodes by the BRP layer. IP is used only to send
these messages one hop toward the peripheral nodes. This allows the these messages one hop toward the peripheral nodes. This allows the
BRP to detect all QUERY packets that are received by that node. BRP to detect all ROUTE_QUERY packets that are received by that node.
To efficiently terminate the query, the BRP needs to record To efficiently terminate the query, the BRP needs to record
sufficient information from each detected query. The query's source sufficient information from each detected query. The query's source
and ID, which serve to uniquely identify a query, are added to the and ID, which serve to uniquely identify a query, are added to the
Detected Queries Table. In addition, the IP address of the last Detected Queries Table. In addition, the IP address of the last
node to bordercast the query is also recorded in the Detected node to bordercast the query is also recorded in the Detected
Queries table. Any threads of this query that are later received Queries table. Any threads of this query that are later received
from a different bordercasting node are discarded. Each query also from a different bordercasting node are discarded. Each query also
contains a hop counter that is decremented at each node. When the contains a hop counter that is decremented at each node. When the
counter expires, the packet is discarded. counter expires, the packet is discarded.
IERP packets (excluding ROUTE-OPTIMIZATION packets) that are not IERP packets (excluding ROUTE_OPTIMIZATION packets) that are not
terminated next undergo a route accumulation procedure. As terminated next undergo a route accumulation procedure. As
described earlier, route accumulation is used to construct routes, described earlier, route accumulation is used to construct routes,
by recording the IP addresses of a route's nodes in the IERP packet by recording the IP addresses of a route's nodes in the IERP packet
or local cache. The Detected Queries Table, extended by two or local cache. The Detected Queries Table, extended by two
columns, serves as a convenient route accumulation cache. columns, serves as a convenient route accumulation cache.
The node begins the route accumulation procedure by adding its IP The node begins the route accumulation procedure by adding its IP
address to the IERP route. This is followed by the IP addresses of address to the IERP route. This is followed by the IP addresses of
any cached nodes leading to the packet's destination (the "next any cached nodes leading to the packet's destination (the "next
hops"). This is sufficient processing for ROUTE-ACCUMULATION hops"). This is sufficient processing for ROUTE_ACCUMULATION
packets, where complete source routes are constructed. On the other packets, where complete source routes are constructed. On the other
hand, QUERY, QUERY-EXTENSION and QUERY-REPLY packets should carry as hand, ROUTE_QUERY, QUERY_EXTENSION and ROUTE_REPLY packets should carry
as
little of the route as possible. Therefore, if cache space is little of the route as possible. Therefore, if cache space is
available, the route accumulation process records the IP addresses available, the route accumulation process records the IP addresses
of the "previous hops" from the packet's source, and removes them of the "previous hops" from the packet's source, and removes them
from the IERP packet. from the IERP packet.
The final role of the BRP is contribute to the ROUTE-OPTIMIZATION The final role of the BRP is to contribute to the ROUTE_OPTIMIZATION
process by indicating the mutual routing zone membership of the process by indicating the mutual routing zone membership of the
nodes in the source route. This is done by appending a special nodes in the source route. This is done by appending a special
flag field to the ROUTE-OPTIMIZATION packet. The status of the 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 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 source route is a member of the node's routing zone. This
membership information is eventually processed at the source to membership information is eventually processed at the source to
determine the smallest set of routing zones that cover the route determine the smallest set of routing zones that cover the route
(and therefore the smallest set of nodes needed to specify this (and therefore the smallest set of nodes needed to specify this
route through loose source routing.) route through loose source routing).
Haas, Pearlman Expires December 1999 [Page
37]
INTERNET DRAFT The Zone Routing Protocol June
1999
A. Packet Format A. Packet Format
See IERP packet format in Section 4.2 See IERP packet format in Section 4.2
B. Structures B. Data Structures
B.1 Intrazone Routing Table (see IARP description) B.1 Intrazone Routing Table (see IARP description)
B.2 Detected Queries Table B.2 Interzone Routing Table (see IERP description)
B.3 Detected Queries Table
+--------------------+--------+
| Query | Query | Prev |
| Source | ID | IERP |
|----------+---------|--------|
| | | |
|----------+---------|--------|
| | | |
|----------+---------|--------|
| | | |
+--------------------+--------+
B.4 Detected Replies Table
+--------------------+
| Reply | Reply |
| Node | ID |
|----------+---------|
| | |
|----------+---------|
| | |
|----------+---------|
| | |
+--------------------+
|--------------------|--------|-----------------------|
| Query | Query | Prev | Prev | Next |
| Source | Id | IERP | Hop(s) | Hop(s) |
|----------+---------|--------+-----------+-----------|
| | | | | | | | | |
|----------+---------|--------+---+---+---|---+---+---|
| | | | | | | | | |
|----------+---------|--------+---+---+---|---+---+---|
| | | | | | | | | |
|--------------------|--------|-----------------------|
|
\|/
+---+ +---+ +---+
| A |-->| B |-->... | C |
+---+ +---+ +---+
cached "source" route
C. Interfaces C. Interfaces
C.1 Higher Layer (i.e. IERP) C.1 Higher Layer (i.e. IERP)
C.2.1 Send() (same interface as IP Send() primitive) C.2.1 Send() (same interface as IP Send() primitive)
Used by higher layer protocol to request transmission of Used by higher layer protocol to request transmission of
a data packet a data packet
C.2.2 Deliver() (same interface as IP Deliver() primitive) C.2.2 Deliver() (same interface as IP Deliver() primitive)
Used by the BRP to alert the higher layer protocol of Used by the BRP to alert the higher layer protocol of
the arrival of a data packet the arrival of a data packet
C.2 Lower Layer (IP) C.2 Lower Layer (IP)
C.2.1 Send() (specified in IP standard) C.2.1 Send() (specified in IP standard)
C.2.2 Deliver() (specified in IP standard) C.2.2 Deliver() (specified in IP standard)
Haas, Pearlman Expires December 1999 [Page
38]
INTERNET DRAFT The Zone Routing Protocol June
1999
D. State Machine D. State Machine
The BRP protocol consists of only one state (IDLE). Therefore, The BRP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The BRP immediately no state transitions need to be specified. The BRP immediately
acts upon an event and then returns back to the IDLE state. 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 Notes: 1) X is used as a label for the host running this state
machine. machine.
2) NULL is a reserved field value, corresponding to an 2) NULL is a reserved field value, corresponding to an
invalid IP address. invalid IP address.
D.1 D.1
Event: A QUERY packet is received from the IERP Event: A ROUTE_QUERY packet is received from the IERP.
Action: If X is the query's source, then the identifying Action: If X is the query's source, then the identifying
querying information is recorded in the Detected querying
Queries Table. X adds its IP address to the information is recorded in the Detected Queries Table.
packet's route. A copy of the packet is sent to X adds its IP address to the packet's route. A copy of
the IERP layer of each peripheral node, by way of the
a BRP transmission to the next hop to that 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. peripheral node.
D.2 D.2
Event: A QUERY packet is received from the IP. The hop Event: A ROUTE_QUERY packet is received from the IP. The hop
counter has expired or the query was already counter has expired or the query was already
detected from another bordercasting node. detected from another bordercasting node.
Action: The packet is discarded. Action: The packet is discarded.
D.3 D.3
Event: A QUERY packet is received from IP. The hop count Event: A ROUTE_QUERY packet is received from IP. The hop
has not expired and the query has not been count
previously detected (or was detected from the has not expired and the query has not been previously
same bordercasting node). X is not the detected (or was detected from the same bordercasting
intended BRP recipient. node).
X is not the intended BRP recipient.
Action: If cache space is available, identifying query Action: Identifying query information is recorded in the
information SHOULD be recorded in the Detected Detected
Queries Table. The packet is then discarded. Queries Table. The packet is then discarded.
D.4 D.4
Event: A QUERY packet is received from the IP. The hop Event: A ROUTE_QUERY packet is received from the IP. The hop
count has not expired and the query has not been count has not expired and the query has not been
previously detected (or was previously detected previously detected (or was previously detected
from the same bordercasting node). X is the from the same bordercasting node). X is the
intended BRP recipient, but is not the intended intended BRP recipient, but is not the intended
IERP recipient and the query destination does IERP recipient and the query destination does
not lie within X's routing zone. not lie within X's routing zone.
Action: The hop counter is decremented. If cache space Action: The hop counter is decremented. Identifying query
is available, identifying query information and information is recorded in the Detected Queries Table
accumulated route information should be recorded and accumulated route information is recorded
in the Detected Queries Table. The recorded route in the Interzone Routing Table. The recorded route
information is removed from the packet and X adds information is removed from the packet and X adds
its IP address to the route. its IP address to the route.
The packet is then sent to the BRP of the next hop The packet is then sent to the BRP of the next hop
to the intended IERP recipient. to the intended IERP recipient.
Haas, Pearlman Expires December 1999 [Page
39]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.5 D.5
Event: A QUERY packet is received from the IP. The hop Event: A ROUTE_QUERY packet is received from the IP. The hop
count has not expired and the query has not been count has not expired and the query has not been
previously detected (or was previously detected previously detected (or was previously detected
from the same bordercasting node). X is the from the same bordercasting node). X is the
intended BRP recipient, and either X is the intended BRP recipient, and either X is the
intended IERP recipient, OR the query destination intended IERP recipient, OR the query destination
lies in X's routing zone. lies in X's routing zone.
Action: The hop counter is decremented. If cache space Action: The hop counter is decremented. Identifying query
is available, identifying query information and information is recorded in the Detected Queries Table
accumulated route information should be recorded and accumulated route information is recorded in the
in the Detected Queries Table. The recorded route Detected Queries Table. The recorded route information
information is removed from the packet and X adds is removed from the packet and X adds its IP address
its IP address to the route. to the route.
The packet is then delivered up to the IERP. The packet is then delivered up to the IERP.
D.6 D.6
Event: A QUERY-EXTENSION is received from the IERP. Event: A QUERY_EXTENSION is received from the IERP.
Action: The packet is sent to the BRP layer of the Action: The packet is sent to the BRP layer of the
next hop to the specified IERP recipient next hop to the specified IERP recipient
(in this case, the query destination). (in this case, the query destination).
D.7 D.7
Event: A QUERY-EXTENSION is received from the IP. Event: A QUERY_EXTENSION is received from the IP.
X is not the intended BRP recipient. X is not the intended BRP recipient.
Action: If cache space is available, identifying query Action: Identifying query information is recorded in the
information SHOULD be recorded in the Detected Detected Queries Table and accumulated route
Queries Table. The packet is then discarded. information is recorded in the Interzone Routing
Table.
The packet is then discarded.
D.8 D.8
Event: A QUERY-EXTENSION packet is received from the IP. Event: A QUERY_EXTENSION packet is received from the IP.
X is the intended BRP recipient, but is not the X is the intended BRP recipient, but is not the
intended IERP recipient. intended IERP recipient.
Action: If cache space is available, identifying query Action: Identifying query information is recorded in the
information and accumulated route information Detected Queries Table and accumulated route
should be recorded in the Detected Queries Table. information is recorded in the Interzone Routing
The recorded route information is removed from the The recorded route information is removed from the
packet and X adds its IP address to the route. packet and X adds its IP address to the route.
The packet is then sent to the BRP of the next hop The packet is then sent to the BRP of the next hop
to the intended IERP recipient. to the intended IERP recipient.
Haas, Pearlman Expires December 1999 [Page
40]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.9 D.9
Event: A QUERY-EXTENSION packet is received from the IP. Event: A QUERY_EXTENSION packet is received from the IP.
X is the intended BRP recipient and the intended X is the intended BRP recipient and the intended
IERP recipient. IERP recipient.
Action: If cache space is available, identifying query Action: Identifying query information is recorded in the
information and accumulated route information Detected Queries Table and accumulated route
should be recorded in the Detected Queries Table. information is recorded in the Interzone Routing
The recorded route information is removed from the Table. The recorded route information is removed
packet and X adds its IP address to the route. from the packet and X adds its IP address to the
The packet is then delivered up to the IERP. route. The packet is then delivered up to the IERP.
D.10 D.10
Event: A QUERY-REPLY packet is received from the IERP. Event: A ROUTE_REPLY packet is received from the IERP.
Action: The IP addresses of X and the previous hops back Action: The IP addresses of X and the previous hops back
to the query source (cached in the Detected Queries to the query source (cached in the Detected Queries
Table) are added to the route. The packet is sent Table) are added to the route. The packet is sent
back to the IERP layer of the query source, by way back to the IERP layer of the query source, by way
of a BRP layer transmission to the first hop back of a BRP layer transmission to the first hop back
to the query source. to the query source.
D.11 D.11
Event: A QUERY-REPLY packet is received from the IP. Event: A ROUTE_REPLY packet is received from the IP.
X is not the intended BRP recipient. X is not the intended BRP recipient or the
ROUTE_REPLY was previously detected.
Action: The packet is discarded. Action: The packet is discarded.
D.12 D.12
Event: A QUERY-REPLY packet is received from the IP. Event: A ROUTE_REPLY packet is received from the IP.
X is the intended BRP recipient, but not the X is the intended BRP recipient, but not the
intended IERP recipient. intended IERP recipient.
The ROUTE_REPLY was not previously detected.
Action: If cache space is available, accumulated route Action: Identifying query information is recorded in the
information to the destination should be recorded Detected Replies Table and accumulated route
in the Detected Queries Table, and the recorded information is recorded in the Interzone Routing
route information removed from the packet. The IP Table. The IP addresses of X and the previous hops
addresses of X and the previous hops back to the back to the query source (previously recorded in the
query source (cached in the Detected Queries Table) Interzone Routing Table) are added to the route.
are added to the route.
The packet is then sent to the BRP layer of the The packet is then sent to the BRP layer of the
previous hop back to the query source. previous hop back to the query source.
D.13 D.13
Event: A QUERY-REPLY packet is received from the IP. Event: A ROUTE_REPLY packet is received from the IP.
X is the intended BRP recipient and the intended X is the intended BRP recipient and the intended
IERP recipient. IERP recipient.
The ROUTE_REPLY was not previously detected.
Action: If cache space is available, accumulated route Action: Identifying query information is recorded in the
information to the destination should be recorded Detected Replies Table and accumulated route
in the Detected Queries Table, and the recorded information is recorded in the Interzone Routing
route information removed from the packet. Table. The recorded route information is removed
The packet is then delivered up to the IERP. from the packet. The packet is then delivered up
to the IERP.
Haas, Pearlman Expires December 1999 [Page
41]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.14 D.14
Event: A ROUTE-ACCUMULATION packet is received from the Event: A ROUTE_ACCUMULATION packet is received from the IERP.
IERP.
Action: The packet is sent to the IERP layer of the Action: The packet is sent to the IERP layer of the specified
specified IERP recipient by way of a BRP IERP recipient by way of a BRP transmission to the next
transmission to the next hop toward the IERP hop toward the IERP recipient.
recipient.
D.15 D.15
Event: A ROUTE-ACCUMULATION packet is received from the Event: A ROUTE_ACCUMULATION packet is received from the IP.
IP. X is not the intended BRP recipient. X is not the intended BRP recipient.
Action: The packet is discarded. Action: The packet is discarded.
D.16 D.16
Event: A ROUTE-ACCUMULATION packet is received from the Event: A ROUTE_ACCUMULATION packet is received from the IP.
IP. X is the intended BRP recipient, but not the X is the intended BRP recipient, but not the intended
intended IERP recipient. IERP recipient.
Action: The IP addresses of X and the next hops to the intended
IERP recipient (previously recorded in the Detected
Replies 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.
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 D.17
Event: A ROUTE-ACCUMULATION packet is received from the Event: A ROUTE_ACCUMULATION packet is received from the IP.
IP. X is the intended BRP recipient and the X is the intended BRP recipient and the intended
intended IERP recipient. IERP recipient.
Action: The packet is delivered up to the IERP. Action: The packet is delivered up to the IERP.
D.18 D.18
Event: A ROUTE-OPTIMIZATION packet is received from the Event: A ROUTE_OPTIMIZATION packet is received from the IERP.
IERP.
Action: X indicates (in its flag field) those route nodes Action: X indicates (in its ROF field) those route nodes that
that belong to its routing zone. The packet is belong to its routing zone. The packet is then sent to
then sent to the IERP layer of the specified IERP the IERP layer of the specified IERP recipient, by way
recipient, by way of a BRP transmission to the of a BRP transmission to the next hop toward the
next hop toward the IERP recipient. IERP recipient.
D.19 D.19
Event: A ROUTE-OPTIMIZATION packet is received from the Event: A ROUTE_OPTIMIZATION packet is received from the IP.
IP. X is not the intended BRP recipient. X is not the intended BRP recipient.
Action: The packet is discarded. Action: The packet is discarded.
Haas, Pearlman Expires December 1999 [Page
42]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.20 D.20
Event: A ROUTE-OPTIMIZATION packet is received from the Event: A ROUTE_OPTIMIZATION packet is received from the IP.
IP. X is the intended BRP recipient, but not X is the intended BRP recipient, but not the intended
the intended IERP recipient. IERP recipient.
Action: X indicates (in its flag field) those route nodes Action: X indicates (in its ROF field) those route nodes that
that belong to its routing zone. The packet is belong to its routing zone.
then sent to the IERP layer of the specified IERP The packet is then sent to the IERP layer of the
recipient, by way of a BRP transmission to the specified next hop toward the IERP recipient.
next hop toward the IERP recipient.
D.21 D.21
Event: A ROUTE-OPTIMIZATION packet is received from the Event: A ROUTE_OPTIMIZATION packet is received from the IP.
IP. X is the intended BRP recipient and the X is the intended BRP recipient and the intended
intended IERP recipient. IERP recipient.
Action: X indicates (in its flag field) those route nodes Action: X indicates (in its ROF field) those route nodes that
that belong to its routing zone. The packet belong to its routing zone. The packet is then
is then delivered up to the IERP delivered up to the IERP.
E. Pseudocode Implementation E. Pseudocode Implementation
We define two complimentary operations on packets: We define two complimentary operations on packets:
extract(packet) and load(packet) extract(packet) and load(packet)
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, hops_left, query_id, bad_link_source, variables: {type, TTL, hop_count, flags, current_hop_ptr,
next_IERP, next_BRP, prev_IERP, route, flag} query_id, reply_id, source, reply_node,
bad_link_source, dests, next_IERP, next_BRP,
prev_IERP, route, metric, ROF}
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 values of:
num_dests = |dests|
num_nodes = |routes|
Haas, Pearlman Expires December 1999 [Page
43]
INTERNET DRAFT The Zone Routing Protocol June
1999
E.1 Receive Packet from IERP E.1 Receive Packet from IERP
extract (packet) 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
switch(type) switch(type)
{ {
case: QUERY case: ROUTE_QUERY
if ((bad_link_source == my_id || source == my_id) IERP_prev = MY_ID
add(Detected_Queries,packet) if ((bad_link_source == MY_ID (OR) source == MY_ID)
{
if(source != MY_ID)
{
route = reverse(Interzone_Routing_Table(source))
route = {route, MY_ID}
}
else
route = NULL
current_hop_ptr = |route|
if(bad_link_source)
add(Detected_Queries,{bad_link_source,query_id,
IERP_prev})
else
add(Detected_Queries,{source,query_id,IERP_prev})
}
for (IERP_next = each host in Intrazone_Routing_Table) for (IERP_next = each host in Intrazone_Routing_Table)
{ {
if (IERP next is a peripheral node) if (IERP_next is a peripheral node)
{ {
BRP_next=Intrazone_Routing_Table[host,0]->next_hop BRP_next=get_shortest_route(Intrazone_Routing_Table,
load(pk_copy) IERP_next)->next_hop
send(pk_copy,BRP_next) metric =get_metric(Intrazone_Routing_Table,BRP_next)
load(packet)
send(packet,BRP_next)
} }
} }
break break
case: QUERY-EXTENSION
BRP_next=Intrazone_Routing_Table[IERP_next,0]->next_hop case: QUERY_EXTENSION
BRP_next=get_shortest_route(Intrazone_Routing_Table,
IERP_next)->next_hop
load(packet) load(packet)
send(packet,BRP_next) send(packet,BRP_next)
break break
case: QUERY-REPLY
if (prev_hops(0) == source) Haas, Pearlman Expires December 1999 [Page
prev_hops = Detected_Queries[source,query_id] 44]
->prev_hops
route = prev_hops + my_id + next_hops INTERNET DRAFT The Zone Routing Protocol June
BRP_next = prev_hops(0) 1999
case: ROUTE_REPLY
prev_hops = route(1: current_hop_ptr-1)
next_hops = route(current_hop_ptr+1 : |route|)
if (prev_hops(1) == MY_ID)
{
prev_hops=reverse(Interzone_Routing_Table[IERP_next])
if(prev_hops(1) == IERP_next (OR) prev_hops == NULL)
{
prev_hops = NULL
BRP_next = IERP_next
}
else
BRP_next = prev_hops(|prev_hops|)
}
else
BRP_next = prev_hops(|prev_hops|)
if (!is_neighbor(Intrazone_Routing_Table, BRP_next))
{
prev_hops={prev_hops,get_route(Intrazone_Routing_Table,
BRP_next)}
BRP_next = prev_hops(|prev_hops|)
}
metric =get_metric(Intrazone_Routing_Table,BRP_next)
current_hop_ptr = |prev_hops|+1
route = {prev_hops, MY_ID, next_hops}
load(packet) load(packet)
send(packet,BRP_next) send(packet,BRP_next)
break break
case: ROUTE-ACCUMULATION
if(my_id == source) case: ROUTE_ACCUMULATION
BRP_next = next_hops(0) if(IERP_next == source)
if(my_id == dest) {
BRP_next = prev_hops(0) BRP_next = route(|route|)
current_hop_ptr = |route|+1
}
if(IERP_next == dest)
{
BRP_next = route(1)
current_hop_ptr = 0
}
load(packet) load(packet)
send(packet,BRP_next) send(packet,BRP_next)
break break
case: ROUTE-OPTIMIZATION
flag = NULL Haas, Pearlman Expires December 1999 [Page
for (i = 0 to length(route)-1) 45]
INTERNET DRAFT The Zone Routing Protocol June
1999
case: ROUTE_OPTIMIZATION
ROF = NULL
for (node = {source,route,dest})
{ {
if ((EXISTS) Intrazone_Routing_Table[route(i)]) if ((EXISTS) Intrazone_Routing_Table[node])
flag = flag,1 ROF = {ROF,1}
else else
flag = flag,0 ROF = {ROF,0}
}
if(IERP_next == dest)
{
BRP_next = route(1)
current_hop_ptr = 0
}
if(IERP_next == source)
{
BRP_next = route(|route|)
current_hop_ptr = |route|+1
} }
if(my_id == source)
BRP_next = next_hops(0)
if(my_id == dest)
BRP_next = prev_hops(0)
load(packet) load(packet)
send(packet,BRP_next) send(packet,BRP_next)
break break
E.2 Receive Packet from IP E.2 Receive Packet from IP
extract(packet) 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) switch(type)
{ {
case QUERY: case ROUTE_QUERY:
if (hops_left > 0 && if (TTL > 0 (AND)
(!EXISTS(Detected_Queries[source,query_id] || (!EXISTS(Detected_Queries[source,query_id] (OR)
Detected_Queries[source,query_id]->from Detected_Queries[source,query_id]->from == IERP_prev))
== IERP_prev))
{ {
hops_left -- TTL--
if (!FULL (Detected_Queries)) hop_count++
prev_hops = route(1 : current_hop_ptr)
next_hops = route(current_hop_ptr+1 : |route|)
if(bad_link_source)
{ {
add(Detected_Queries, packet)
prev_hops = source add(Detected_Queries,{bad_link_source,query_id,IERP_prev})
status =
add(Interzone_Routing_Table,BRP,bad_link_source,
prev_hops,metric)
} }
else else
route = prev_hops + my_id + next_hops {
add(Detected_Queries,{source,query_id,IERP_prev})
status = add(Interzone_Routing_Table,BRP,source,
prev_hops,metric)
}
if(BRP_next == my_id) Haas, Pearlman Expires December 1999 [Page
46]
INTERNET DRAFT The Zone Routing Protocol June
1999
if (status == RECORDED_ROUTE)
{ {
if(IERP_next == my_id || prev_hops = NULL
dest (EXISTS IN) Intrazone_Routing_Table) metric = compress_metric(metric)
}
route = {prev_hops, MY_ID, next_hops}
current_hop_ptr = |prev_hops|+1
if(BRP_next == MY_ID)
{
if(IERP_next == MY_ID)
{
load(packet)
deliver(packet,IERP) deliver(packet,IERP)
}
else else
{ {
BRP_next=Intrazone_Routing_Table[IERP_next] d = dests (BELONGING TO) Intrazone_Routing_Table
->route(0)->next_hop if(|d| > 0)
{
load(packet)
deliver(packet,IERP)
}
if((|d| == 0) (OR)
(|d| < |dests| (AND) flag(0) == ALL))
{
BRP_next=get_shortest_route(
Intrazone_Routing_Table,
IERP_next)->next_hop
metric = {metric,get_metric(
Intrazone_Routing_Table,
BRP_next)}
load(packet) load(packet)
send(packet, BRP_next) send(packet, BRP_next)
} }
} }
}
else else
discard(packet) discard(packet)
} }
else else
{
if(bad_link_source)
add(Detected_Queries,{bad_link_source,query_id,IERP_prev})
else
add(Detected_Queries,{source,query_id,IERP_prev})
discard(packet) discard(packet)
}
break break
case QUERY-EXTENSION:
Haas, Pearlman Expires December 1999 [Page
47]
INTERNET DRAFT The Zone Routing Protocol June
1999
case QUERY_EXTENSION:
if (!EXISTS(Detected_Replies[reply_node,reply_id])
{ {
if (!FULL (Detected_Queries)) hop_count++
prev_hops = route(1: current_hop_ptr)
next_hops = route(current_hop_ptr+1 : |route|)
if(bad_link_source)
{ {
add(Detected_Queries,packet)
prev_hops = source add(Detected_Queries,{bad_link_source,query_id,IERP_prev})
status =
add(Interzone_Routing_Table,BRP,bad_link_source,
prev_hops,metric)
}
else
{
add(Detected_Queries,{source,query_id,IERP_prev})
status = add(Interzone_Routing_Table,BRP,source,
prev_hops,metric)
} }
route = prev_hops + my_id + next_hops
if(BRP_next == my_id) if (status == RECORDED_ROUTE)
{ {
if(IERP_next == my_id || prev_hops = NULL
dest (EXISTS IN) Intrazone_Routing_Table) metric = compress_metric(metric)
}
route = {prev_hops, MY_ID, next_hops}
current_hop_ptr = |prev_hops|+1
if(BRP_next == MY_ID)
{
if(IERP_next == MY_ID)
{
load(packet)
deliver(packet,IERP) deliver(packet,IERP)
}
else else
{ {
BRP_next=Intrazone_Routing_Table[IERP_next]
->route(0)->next_hop BRP_next=get_shortest_route(Intrazone_Routing_Table,
IERP_next)->next_hop
metric =
{metric,get_metric(Intrazone_Routing_Table,
BRP_next)}
load(packet) load(packet)
send(packet, BRP_next) send(packet, BRP_next)
} }
} }
else else
discard(packet) discard(packet)
} }
else else
discard(packet) discard(packet)
break break
case QUERY-REPLY: Haas, Pearlman Expires December 1999 [Page
if(my_id == BRP_next) 48]
INTERNET DRAFT The Zone Routing Protocol June
1999
case ROUTE_REPLY:
if(MY_ID == BRP_next (AND)
!EXISTS(Detected_Queries[source,query_id]))
{ {
if (!FULL (Detected_Queries)) prev_hops = route(1: current_hop_ptr-1)
next_hops = route(current_hop_ptr : |route|)
add(Detected_Replies, {reply_node,reply_id})
status=add(Interzone_Routing_Table,BRP,dest,
next_hops,metric)
if (status == RECORDED_ROUTE)
{ {
add(Detected_Queries, packet) next_hops = NULL
next_hops = dest metric = compress_metric(metric)
} }
if (prev_hops(0) == source)
prev_hops = Detected_Queries[source,query_id] if (prev_hops(1) == MY_ID)
->prev_hops {
route = prev_hops + my_id + next_hops prev_hops=reverse(Interzone_Routing_Table[IERP_next])
if(my_id == IERP_next)
if(prev_hops(|prev_hops|) == IERP_next (OR)
prev_hops == NULL)
{
prev_hops = NULL
BRP_next = IERP_next
}
else
BRP_next = prev_hops(|prev_hops|)
}
else
BRP_next = prev_hops(|prev_hops|)
if (!is_neighbor(Intrazone_Routing_Table, BRP_next))
{
prev_hops={prev_hops,get_route(Intrazone_Routing_Table,
BRP_next)}
BRP_next = prev_hops(|prev_hops|)
}
if(MY_ID == IERP_next)
{
current_hop_ptr = 0
load(packet)
deliver(packet,IERP) deliver(packet,IERP)
}
else else
{ {
BRP_next = prev_hops(0) metric = {metric,get_metric(Intrazone_Routing_Table,
BRP_next)}
route = {prev_hops, MY_ID, next_hops}
current_hop_ptr = |prev_hops|+1
load(packet) load(packet)
send(packet,BRP_next) send(packet,BRP_next)
} }
} }
else else
discard(packet) discard(packet)
break break
case ROUTE-ACCUMULATION:
if(my_id == BRP_next) Haas, Pearlman Expires December 1999 [Page
49]
INTERNET DRAFT The Zone Routing Protocol June
1999
case ROUTE_ACCUMULATION:
if(MY_ID == BRP_next)
{ {
if(my_id == IERP_next) if(IERP_next == source)
deliver(packet, IERP)
else
{ {
if (bad_link_source && IERP_next == source) prev_hops = route(1: current_hop_ptr-1)
next_hops = route(current_hop_ptr : |route|)
if (prev_hops(1) == MY_ID)
{ {
bad_link_ptr=get_index(route,bad_link_source)
if (current_hop_ptr <= bad_link_ptr) prev_hops=reverse(Interzone_Routing_Table[IERP_next])
deliver(packet, IERP)
if(prev_hops(1) == IERP_next (OR) prev_hops == NULL)
{
prev_hops = NULL
BRP_next = IERP_next
} }
else
BRP_next = prev_hops(|prev_hops|)
}
else
BRP_next = prev_hops(|prev_hops|)
if(MY_ID == bad_link_source)
flags(1) = 1
}
if (IERP_next == dest) if (IERP_next == dest)
{ {
if(next_hops(0) == dest) prev_hops = route(1: current_hop_ptr)
next_hops=Detected_Queries[source,query_id] next_hops = route(current_hop_ptr+1 : |route|)
->next_hops
BRP_next = next_hops(0) if (next_hops(|next_hops|) == MY_ID)
{
next_hops=Interzone_Routing_Table[IERP_next])
if(next_hops(|next_hops|) == IERP_next (OR)
next_hops == NULL)
{
next_hops = NULL
BRP_next = IERP_next
} }
if (IERP_next == source) else
BRP_next = next_hops(1)
}
else
BRP_next = next_hops(1)
}
Haas, Pearlman Expires December 1999 [Page
50]
INTERNET DRAFT The Zone Routing Protocol June
1999
if(MY_ID == IERP_next)
{ {
if(prev_hops(0) == source) load(packet)
prev_hops=Detected_Queries[source,query_id] deliver(packet, IERP)
->prev_hops
BRP_next = prev_hops(0)
} }
route = prev_hops + my_id + next_hops else
{
if(flags(1) == 1)
{
load(packet)
deliver(packet, IERP)
}
metric = {metric,get_metric(Intrazone_Routing_Table,
BRP_next)}
route = {prev_hops, MY_ID, next_hops}
current_hop_ptr = |prev_hops|+1
load(packet) load(packet)
send (packet,BRP_next) send (packet,BRP_next)
} }
} }
else else
discard(packet) discard(packet)
break break
case ROUTE-OPTIMIZATION:
if(my_id == BRP_next) case ROUTE_OPTIMIZATION:
if(MY_ID == BRP_next)
{ {
f = NULL f = NULL
for (i = 0: length(route)-1) for (node = {source,route,dest})
{ {
if ((EXISTS) Intrazone_Routing_Table[route(i)]) if ((EXISTS) Intrazone_Routing_Table[node])
f = f,1 f = {f,1}
else else
f = f,0 f = {f,0}
} }
if (IERP_next == source) if (IERP_next == source)
flag = f , flag {
else current_hop_ptr--
flag = flag , f prev_hops = route(1: current_hop_ptr-1)
next_hops = route(current_hop_ptr+1 : |route|)
BRP_next = prev_hops(|prev_hops|)
ROF = {f,ROF}
}
if (IERP_next == dest)
{
current_hop_ptr++
prev_hops = route(1: current_hop_ptr-1)
next_hops = route(current_hop_ptr+1 : |route|)
BRP_next = next_hops(1)
ROF = {ROF,f}
}
if(my_id == IERP_next) Haas, Pearlman Expires December 1999 [Page
51]
INTERNET DRAFT The Zone Routing Protocol June
1999
if(MY_ID == IERP_next)
{
load(packet)
deliver(packet, IERP) deliver(packet, IERP)
}
else else
{ {
if(IERP_next == source)
BRP_next = prev_hops(0)
else
BRP_next = next_hops(0)
load(packet) load(packet)
send (packet,BRP_next) send (packet,BRP_next)
} }
} }
else else
discard(packet) discard(packet)
break break
Haas, Pearlman Expires December 1999 [Page
52]
INTERNET DRAFT The Zone Routing Protocol June
1999
5. Other Considerations 5. Other Considerations
5.1 Sizing the Zone Radius 5.1 Sizing the Zone Radius
The performance of the Zone Routing Protocol is determined by the The performance of the Zone Routing Protocol is determined by the
routing zone radius. In general, dense networks consisting of a few routing zone radius. In general, dense networks consisting of a few
fast moving nodes favor smaller routing zones. On the other hand, a fast moving nodes favor smaller routing zones. On the other hand, a
sparse network of many slowly moving nodes operates more efficiently sparse network of many slowly moving nodes operates more efficiently
with a larger zone radius. with a larger zone radius.
The simplest approach to configuring the routing zone radius is to The simplest approach to configuring the routing zone radius is to
make the assignment once, prior to deploying the network. This can make the assignment once, prior to deploying the network. This can
be performed by the network administration, if one exists, or by be performed by the network administration, if one exists, or by
the manufacturer, as a default value. This may provide acceptable the manufacturer, as a default value. This may provide acceptable
performance, especially in situations where network characteristics performance, especially in situations where network characteristics
do not vary greatly over space and time. Alternatively, the ZRP can do not vary greatly over space and time. Alternatively, the ZRP can
adpat to changes in network behavior, through dynamnic configuration adapt to changes in network behavior, through dynamic configuration
of the zone radius [Haas-3]. In [Haas-4], it was shown that of the zone radius [3]. In [4], it was shown that a node can accurately
a node can accurately estimate its optimal zone radius, on-line, estimate its optimal zone radius, on-line, based on local measurements of
based on local measurements of ZRP traffic. The re-sizing of the ZRP traffic. The re-sizing of the routing zone can be carried out by a
routing zone can be carried out by a protocol that conveys the protocol that conveys the change in zone radius to the members of the
change in zone radius to the members of the routing zone. The routing zone. The details of such an update protocol will be provided in
details of such an update protocol will be provided in a future a future version of this draft.
version of this draft.
6.0 References 5.2 Hierarchical Routing and the ZRP
[AODV] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing", In a hierarchical network architecture, network nodes are organized into
MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, a
November 3, 1997 smaller number of (often disjoint) clusters. This routing hierarchy is
maintained by two component routing protocols. An intra-cluster protocol
provides routes between nodes of the same cluster, while an inter-cluster
protocol operates globally to provide routes between clusters.
[Haas-1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable The ZRP, with its routing zones and intrazone / interzone routing
Wireless Networks", ICUPC'97, San Diego, CA, Oct. 12,1997. protocol
(IARP/IERP) architecture may give the appearance of being a hierarchical
routing protocol. In actuality, the ZRP is a flat routing protocol.
Each
node maintains its own routing zone, which heavily overlaps with the
routing
zones of neighboring nodes. Because there is a one-to-one correspondence
between nodes and routing zones, the routing zones, unlike hierarchical
clusters, do not serve to hide the details of local network topology.
As a result, the network-wide interzone routing protocol (IERP) actually
determines routes between individual nodes, rather than just between
higher
level network entities.
[Haas-2] Haas, Z.J. and Pearlman, M.R., "The Performance of Query Haas, Pearlman Expires December 1999 [Page
53]
INTERNET DRAFT The Zone Routing Protocol June
1999
For small to moderately sized networks, flat routing protocols, like the
ZRP, are preferable to hierarchical routing protocols. In order for
a node to be located, its address needs to reflect the node's location
within the network hierarchy (ie. {cluster id,node id}). Because of
node mobility, a node's cluster membership (and thus address) is subject
to change. This complicates mobility management, for the benefit of more
efficient routing. In many hierarchical routing protocols, each cluster
designates a single clusterhead node to relay inter-cluster traffic.
These
clusterhead nodes become traffic "hot-spots", potentially resulting in
network congestion and single point of failure. Furthermore, restricting
cluster access through clusterhead nodes can lead to sub-optimal routes,
as potential neighbors in different clusters are prohibited from
communicating directly. Some hieararchical routing protocols, such
as the Zone-Based Hiearchical Link-State (ZHLS) [5], avoid these problems
by distributing routing information to all cluster nodes, rather than
maintaining a single clusterhead.
In spite of these disadvantages, hierarchical routing protocols are often
better suited for very large networks than flat routing protocols.
Because hierarchical routing protocols provide global routes to network
clusters, rather than individual nodes, routing table storage is more
scalable. Similarly, the amount of route update messages is also more
scalable. To some extent, the reduction in routing traffic is offset
by extra mobility management overhead (i.e. identifying which cluster
a node belongs to). However, it is quite common that the environment or
existing organizational structure causes nodes to naturally cluster
together. In these cases, there may be high degree of intra-cluster
mobility, inter-cluster mobility is less common.
A hierarchical routing protocol can be viewed as a set of flat routing
protocols, each operating at different levels of granularity. In a two-
tier routing protocol, the inter-cluster components is essentially a
flat routing protocol that computes routes between clusters. Likewise,
the intra-cluster component is a flat routing protocol, that computes
routes
between nodes in each cluster. For example, the Near Term Digital Radio
(NTDR) System [12] and ZHLS both employ proactive link state protocols to
determine inter and intracluster connectivity.
In place of traditional proactive or reactive protocols, we recommend
that the intra-cluster and inter-cluster routing protocol components
be implemented based on the hybrid proactive/reactive ZRP. As described
throughout this draft, the ZRP is designed to provide an optimal balance
between purely proactive and reactive routing. This applies equally well
to routing between nodes at the intra-cluster level and between clusters
at
the inter-cluster level. Additionally, the hybrid ZRP methodology can
be applied to the related mobility management protocols, which determine
complete node addresses based on a node's location in the network
hierarchy.
Haas, Pearlman Expires December 1999 [Page
54]
INTERNET DRAFT The Zone Routing Protocol June
1999
6.0 References
[1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable
Wireless Networks," ICUPC'97, San Diego, CA, Oct. 12,1997.
[2] Haas, Z.J. and Pearlman, M.R., "The Performance of Query
Control Schemes for the Zone Routing Protocol," Control Schemes for the Zone Routing Protocol,"
SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998. SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998.
[Haas-3] Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design [3] Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design
Choices in Ad-Hoc Communications", MILCOM'98, Boston, MA, Choices in Ad-Hoc Communications," MILCOM'98, Boston, MA,
October 18-21, 1998. October 18-21, 1998.
[Haas-4] Haas, Z.J. and Pearlman, M.R., "Determining the Optimal [4] Haas, Z.J. and Pearlman, M.R., "Determining the Optimal
Configuration for the Zone Routing Protocol", submitted Configuration for the Zone Routing Protocol," to appear
for journal publication. in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.
[Johnson] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing [5] Joa-Ng, M. and Lu, I.T., "A Peer-to-Peer Zone-based Two-Level
Link State Routing for Mobile Ad-Hoc Networks," to appear
in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.
[6] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing
in Ad-Hoc Wireless Networks," in Mobile Computing, in Ad-Hoc Wireless Networks," in Mobile Computing,
edited by T. Imielinski and H. Korth, chapter 5, edited by T. Imielinski and H. Korth, chapter 5,
pp. 153-181, Kluwer, 1996. pp. 153-181, Kluwer, 1996.
[Murthy] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient [7] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD,
Routing Protocol for Wireless Networks", MONET, vol. 1, RFC 2178, July 1997.
[8] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient
Routing Protocol for Wireless Networks," MONET, vol. 1,
no. 2, pp. 183-197, October 1996. no. 2, pp. 183-197, October 1996.
[Park] Park, V.D., and Corson, M.S., "A Highly Adaptive [9] Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed
Distributed Routing Algorithm for Mobile Wireless Routing Algorithm for Mobile Wireless Networks,"
Networks," IEEE INFOCOM'97, Kobe, Japan, 1997. IEEE INFOCOM'97, Kobe, Japan, 1997.
[Perkins] Perkins, C.E., and Bhagwat, P., "Highly Dynamic [10] 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.
[TORA] Macker, J., "Mobile Ad Hoc Internetworking", MILCOM'97 [11] Perkins, C.E. and Royer, E.M., "Ad-Hoc On-Demand Distance
panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997. Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999
[RFC-0791] Postel, J., Editor, "Internet Protocol", STD 5, RFC 791, [12] Ruppe, R., Griswald, S., Walsh, P. and Martin, R., "Near Term
September 1981. Digital Radio (NTDR) System," IEEE MILCOM'97, Monterey, CA,
Nov. 1997.
[RFC-1075] Waitzman, D., Partridge, C., Deering, S.E., "Distance [13] Waitzman, D., Partridge, C., Deering, S.E., "Distance
Vector Multicast Routing Protocol",RFC 1075, Nov. 1, 1988. Vector Multicast Routing Protocol," RFC 1075, Nov. 1, 1988.
[RFC-2178] Moy, J., "OSPF Version 2", INTERNET DRAFT STANDARD, Haas, Pearlman Expires December 1999 [Page
RFC 2178, July 1997. 55]
INTERNET DRAFT The Zone Routing Protocol June
1999
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 Engineering
Cornell University Cornell University
Ithaca, NY 14853 Ithaca, NY 14853
United States of America United States of America
tel: (607) 255-3454, fax: (607) 255-9072 tel: (607) 255-3454, fax: (607) 255-9072
Email: haas@acm.org or haas@ee.cornell.edu Email: haas@ee.cornell.edu
Marc R. Pearlman Marc R. Pearlman
319 Frank Rhodes Hall 389 Frank Rhodes Hall
School of Electrical Engineering School of Electrical 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
Email: pearlman@ee.cornell.edu Email: pearlman@ee.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 University of Maryland
College Park, MD 20742 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 Expires December 1999 [Page
56]
 End of changes. 

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