draft-ietf-manet-zone-zrp-02.txt   draft-ietf-manet-zone-zrp-03.txt 
INTERNET-DRAFT Zygmunt J. Haas, Cornell INTERNET-DRAFT Zygmunt J. Haas, Cornell University
University Marc R. Pearlman, Cornell University
Marc R. Pearlman, Cornell
University Expires in six months on September 2000 March 2000
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-02.txt> <draft-ietf-manet-zone-zrp-03.txt>
Status of this Memo Status of this Memo
This document is an Internet-Draft and is NOT offered in accordance This document is an Internet-Draft and is NOT offered in accordance
with Section 10 of RFC2026, and the author does not provide the IETF with Section 10 of RFC2026, and the author does not provide the IETF
with any rights other than to publish as an Internet-Draft. with any rights other than to publish as an Internet-Draft.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-Drafts. other groups may also distribute working documents as Internet-Drafts.
skipping to change at line 48 skipping to change at page 1, line 47
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.
The ZRP framework is designed to provide a balance between the
contrasting proactive and reactive routing approaches. To underscore
this general philosophy, both the proactive and reactive components of
this ZRP implementation have been expanded. This draft provides
specifications for both a (split-horizon) Distance Vector AND a Link
State
version of the proactive IntrAzone Routing Protocol (IARP). The reactive
IntErzone Routing Protocol (IERP) provides a route caching option. When
route caching is globally enabled, the IERP acts as a reactive Distance
Vector protocol, distributing routing information among intermediate
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
Applicability Statement . . . . . . . . . . . . . . . . . . . . v Applicability Statement . . . . . . . . . . . . . . . . . . . iii
A. Networking Context . . . . . . . . . . . . . . . . . . v A. Networking Context . . . . . . . . . . . . . . . . . iii
B. Protocol Characteristics and Mechanisms . . . . . . . . v B. Protocol Characteristics and Mechanisms . . . . . . . iii
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 1
2. Overview of the Zone Routing Protocol . . . . . . . . . . . 3 2. Overview of the Zone Routing Protocol . . . . . . . . . . . 2
2.1 The Notion of a Routing Zone and the 2.1 Routing Zones, Extended Routing Zones,
Intrazone Routing Protocol (IARP) . . . . . . . . . . 3 and the Intrazone Routing Protocol (IARP) . . . . . . 2
2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 4 2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 3
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 . . . . . . . . . . . . . . . 6
3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 8 3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 7
4. Implementation Details . . . . . . . . . . . . . . . . . . 9 4. Implementation Details . . . . . . . . . . . . . . . . . . 8
4.1 Intrazone Routing Protocol (IARP) . . . . . . . . . . 9 4.1 Intrazone Routing Protocol (IARP) -- Link State . . . 8
4.1.1 Distance Vector Implementation . . . . . . . . 9 A. Packet Format . . . . . . . . . . . . . . . . . . 9
A. Packet Format . . . . . . . . . . . . . . . . 10 B. Data Structures . . . . . . . . . . . . . . . . . 10
B. Data Structures . . . . . . . . . . . . . . . 11 C. Interfaces . . . . . . . . . . . . . . . . . . . . 12
C. Interfaces . . . . . . . . . . . . . . . . . . 11 D. State Machine . . . . . . . . . . . . . . . . . . 13
D. State Machine . . . . . . . . . . . . . . . . 12 E. Pseudocode Implementation . . . . . . . . . . . . 14
E. Pseudocode Implementation . . . . . . . . . . 14
4.1.2 Link State Implementation . . . . . . . . . . . 16
A. Packet Format . . . . . . . . . . . . . . . . 16
B. Data Structures . . . . . . . . . . . . . . . 18
C. Interfaces . . . . . . . . . . . . . . . . . . 20
D. State Machine . . . . . . . . . . . . . . . . 20
E. Pseudocode Implementation . . . . . . . . . . 21
4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 24 4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 18
A. Packet Format . . . . . . . . . . . . . . . . . . 26 A. Packet Format . . . . . . . . . . . . . . . . . . 19
B. Data Structures . . . . . . . . . . . . . . . . . 22
C. Interfaces . . . . . . . . . . . . . . . . . . . . 23
D. State Machine . . . . . . . . . . . . . . . . . . 23
E. Pseudocode Implementation . . . . . . . . . . . . 25
4.3 Bordercast Resolution Protocol (BRP) . . . . . . . . . 30
A. Packet Format . . . . . . . . . . . . . . . . . . 30
B. Data Structures . . . . . . . . . . . . . . . . . 31 B. Data Structures . . . . . . . . . . . . . . . . . 31
C. Interfaces . . . . . . . . . . . . . . . . . . . . 31 C. Interfaces . . . . . . . . . . . . . . . . . . . . 32
D. State Machine . . . . . . . . . . . . . . . . . . 32 D. State Machine . . . . . . . . . . . . . . . . . . 32
E. Pseudocode Implementation . . . . . . . . . . . . 33 E. Pseudocode Implementations . . . . . . . . . . . . 34
4.3 Bordercasting Resolution Protocol (BRP) . . . . . . . 37
A. Packet Format . . . . . . . . . . . . . . . . . . 38
B. Data Structures . . . . . . . . . . . . . . . . . 38
C. Interfaces . . . . . . . . . . . . . . . . . . . . 38
D. State Machine . . . . . . . . . . . . . . . . . . 39
E. Pseudocode Implementations . . . . . . . . . . . . 43
Haas, Pearlman Expires December 1999 [Page
iii]
INTERNET DRAFT The Zone Routing Protocol June
1999
5. Other Considerations . . . . . . . . . . . . . . . . . . . 53 5. Other Considerations . . . . . . . . . . . . . . . . . . . 37
5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 53 5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 37
5.2 Hierarchical Routing and the ZRP . . . . . . . . . . . 53 5.2 Hierarchical Routing and the ZRP . . . . . . . . . . . 37
6. References . . . . . . . . . . . . . . . . . . . . . . . . 55 6. References . . . . . . . . . . . . . . . . . . . . . . . . 39
Haas, Pearlman Expires December 1999 [Page 7. Draft Modifications . . . . . . . . . . . . . . . . . . . . 40
iv]
INTERNET DRAFT The Zone Routing Protocol June Authors' Information . . . . . . . . . . . . . . . . . . . . . 41
1999 MANET Contact Information . . . . . . . . . . . . . . . . . . . 41
Applicability Statement Applicability Statement
A. Networking Context A. Networking Context
The hybrid Zone Routing Protocol (ZRP) can adapt to a wide variety of The hybrid Zone Routing Protocol (ZRP) can adapt to a wide variety of
network scenarios by adjusting the range of the nodes' proactively network scenarios by adjusting the range of the nodes' proactively
maintained routing zones. Large routing zones are preferred when demand maintained routing zones. Large routing zones are preferred when
for routes is high and/or the network consists of many slowly moving demand for routes is high and/or the network consists of many slowly
nodes. In the extreme case of a network with fixed topology, the ideal moving nodes. In the extreme case of a network with fixed topology,
routing zone radius would be infinitely large. (Consider the purely the ideal routing zone radius would be infinitely large. (Consider
proactive routing protocols used on the fixed Internet). On the other the purely proactive routing protocols used on the fixed Internet).
hand, On the other hand, smaller routing zones are appropriate in
smaller routing zones are appropriate in situations where route demand situations where route demand is low and/or the network consists of a
is small number of nodes that move fast relative to one another. In the
low and/or the network consists of a small number of nodes that move "worst case", a routing zone radius of one hop is best, and the ZRP
fast defaults to a traditional reactive flooding protocol.
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, When the ZRP is properly configured for a particular network scenario,
it it can perform at least as well as (and often better than) its purely
can perform at least as well as (and often better than) its purely proactive and reactive constituent protocols. In situations where
proactive the network behavior varies across different regions, the ZRP
and reactive constituent protocols. In situations where the network performance can be fine-tuned by individual adjustment of each node's
behavior varies across different regions, the ZRP performance can be routing zone.
fine
tuned by individual adjustment of each node's routing zone.
The global reactive component of the ZRP uses the unicast/multicast The global reactive component of the ZRP uses the multicast based
based
"bordercast" mechanism to propagate route queries throughout the "bordercast" mechanism to propagate route queries throughout the
network, network, rather than relying on neighbor-broadcast flooding found in
rather than neighbor-broadcast based flooding found in tradtional tradtional reactive protocols. Consequently, the ZRP provides the
reactive most benefit in networks where reliable neighbor broadcasting is
protocols. Consequently, the ZRP provides the most benefit in networks either inefficient or altogether impossible. In particular, the ZRP
where reliable neighbor broadcasting is either inefficient or is well suited for multi-channel, multi-technology routing fabrics
all-together and networks operating under high load.
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 B. Protocol Characteristics and Mechanisms
* Does the protocol provide support for unidirectional links? (if so, * Does the protocol provide support for unidirectional links?
how?) (if so, how?)
Yes. The ZRP provides "local" support for unidirectional links. Yes. The ZRP provides "local" support for unidirectional links.
A unidirectional link can be used as long as the link source and A unidirectional link can be used as long as the link source and
link destination lie within each other's routing zone. link destination lie within each other's routing zone.
* Does the protocol require the use of tunneling? (if so, how?) * Does the protocol require the use of tunneling? (if so, how?)
No. No.
* Does the protocol require using some form of source routing? (if * Does the protocol require using some form of source routing?
so, how?) (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 No. The ZRP's framework supports global route discovery based
1999 on source routing, distributed distance vectors, or various
combinations of both.
* Does the protocol require the use of periodic messaging? (if so, * Does the protocol require the use of periodic messaging?
how?) (if so, how?)
Yes. The ZRP proactively maintains local routing information Yes. The ZRP proactively maintains local routing information
(routing zones) based on periodic exchanges of neighbor (routing zones) based on periodic exchanges of neighbor
discovery messages. discovery messages.
* Does the protocol require the use of reliable or sequenced packet * Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?) delivery? (if so, how?)
The ZRP only assumes that link-layer (neighbor) unicasts are The ZRP only assumes that link-layer (neighbor) unicasts are
delivered reliably and in-sequence. Reliable and sequenced delivered reliably and in-sequence. Reliable and sequenced
skipping to change at line 247 skipping to change at page 1, line 178
* Does the protocol provide support for routing through a multi- * Does the protocol provide support for routing through a multi-
technology routing fabric? (if so, how?) technology routing fabric? (if so, how?)
Yes. It is assumed that each node's network interface is Yes. It is assumed that each node's network interface is
assigned a unique IP address. assigned a unique IP address.
* Does the protocol provide support for multiple hosts per router? * Does the protocol provide support for multiple hosts per router?
(if so, how?) (if so, how?)
Yes. Multiple hosts may be associated with a router. These hosts Yes. Multiple hosts may be associated with a router. These
can be identified by the neighbor discovery/maintenance process. hosts can be identified by the neighbor discovery/maintenance
process.
By default, it is assumed that a host's association with a router By default, it is assumed that a host's association with a router
is not permanent. As a result, the ZRP exchanges routing is not permanent. As a result, the ZRP exchanges routing
information information for individual hosts in the same manner as routing
for individual hosts in the same manner as routing information for information for routers.
routers.
In cases where a router is permanently associated with a network In cases where a router is permanently associated with a network
(subnetwork), the ZRP supports the exchange of network (subnetwork) (subnetwork), the ZRP supports the exchange of network
prefixes in place of all aggregated host IP addresses. (subnetwork) prefixes in place of all aggregated host IP
addresses.
* Does the protocol support the IP addressing architecture? (if so, * Does the protocol support the IP addressing architecture?
how?) (if so, how?)
Yes. Each node is assumed to have a unique IP address (or Yes. Each node is assumed to have a unique IP address (or
set of unique IP addresses in the case of multiple interfaces). set of unique IP addresses in the case of multiple interfaces).
The ZRP references all nodes/interfaces by their IP address. The ZRP references all nodes/interfaces by their IP address.
This version of the ZRP also supports IP network addressing This version of the ZRP also supports IP network addressing
(network prefixes) for routers that provide access to a (network prefixes) for routers that provide access to a
network of non-router hosts. network of non-router hosts.
Haas, Pearlman Expires December 1999 [Page * Does the protocol require link or neighbor status sensing
vi] (if so, how?)
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 Yes. The ZRP proactively maintains local routing information
(routing zones) based on detected changes in neighbor status. (routing zones) based on detected changes in neighbor status.
* Does the protocol have dependence on a central entity? (if so, * Does the protocol have dependence on a central entity?
how?) (if so, how?)
No. The ZRP is a fully distributed protocol. No. The ZRP is a fully distributed protocol.
* Does the protocol function reactively? (if so, how?) * Does the protocol function reactively? (if so, how?)
Yes. The ZRP's GLOBAL route discovery mechanism is reactive. Yes. The ZRP's GLOBAL route discovery mechanism is reactive.
A route query is initiated, on demand, when a node requires routing A route query is initiated, on demand, when a node requires
information that is not immediately available in its routing table. routing information that is not immediately available in its
routing table.
The route query propagates through the network, using a ZRP-specific The route query propagates through the network, using a special
packet delivery service called "bordercasting". Bordercasting packet delivery service called "bordercasting". Bordercasting
leverages knowledge of local network topology to direct route leverages knowledge of local network topology to direct route
queries away from the source, thereby reducing redundancy. queries away from the source, thereby reducing redundancy.
* Does the protocol function proactively? (if so, how?) * Does the protocol function proactively? (if so, how?)
Yes. The ZRP proactively maintains local routing information Yes. The ZRP proactively maintains LOCAL routing information
(routing zones) for each node. The routing zone information is (routing zones) for each node. The routing zone information is
leveraged, through the bordercasting mechanism, to support leveraged, through the bordercasting mechanism, to support
efficient global propagation of route queries. efficient global propagation of route queries.
* Does the protocol provide loop-free routing? (if so, how?) * Does the protocol provide loop-free routing? (if so, how?)
Yes. Loop-freedom in the reactive route discovery process Yes. In this draft, loop-freedom in the reactive route discovery
is ensured by labeling each route query and route reply process is ensured by inspection of accumulated source routes.
with the IP address of its originating node AND a unique For distributed distance vector approaches, loop-freedom can be
sequence number. Nodes that relay the route queries ensured by labeling queries (replies) with the source
/route replies temporarily cache these identifiers in order (destination) address and locally unique sequence number. Nodes
to identify and terminate loops. that relay these messages can 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 The ZRP's Link State proactive protocol is inherently loop-free,
1999 although temporary loops may form while new link state updates
propagate through the routing zone.
* Does the protocol provide for sleep period operation? (if so, how?) * Does the protocol provide for sleep period operation? (if so, how?)
No. No.
* Does the protocol provide some form of security? (if so, how?) * Does the protocol provide some form of security? (if so, how?)
No. It is assumed that security issues are adequately addressed No. It is assumed that security issues are adequately addressed
by the underlying protocols (IPsec, for example) by the underlying protocols (IPsec, for example).
* Does the protocol provide support for utilizing multi-channel, * Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?) link-layer technologies? (if so, how?)
Yes. It is assumed that each node's network interface is Yes. It is assumed that each node's network interface is
assigned a unique IP address. assigned a unique IP address.
Haas, Pearlman 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
data (e.g., routes, routes updates, or routing tables) among the data (e.g., routes, routes updates, or routing tables) among the
network nodes. Thus, the amount of update traffic can be quite high. network nodes. Thus, the amount of update traffic can be quite high.
This is in contradiction with the fact that all updates in a This is in contradiction with the fact that all updates in a
wirelessly interconnected ad hoc network travel over the air and, wirelessly interconnected ad hoc network travel over the air and,
thus, are costly in resources. thus, are costly in resources.
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. Examples of proactive routing
hand, invoke a route determination procedure on demand only. Thus, protocols include the Wireless Routing Protocol (WRP) [7] and
when a route is needed, some sort of global search procedure is Destination-Sequenced Distance-Vector (DSDV) routing [11]. Reactive
employed. The family of classical flooding algorithms belong to the protocols, on the other hand, invoke a route determination procedure
reactive group. Some examples of reactive (also called on-demand) on demand only. Thus, when a route is needed, some sort of global
ad hoc network routing protocols are Dynamic Source Routing (DSR)[6], search procedure is employed. The family of classical flooding
Ad-hoc On demand Distance Vector Routing (AODV) [11] and the algorithms belong to the reactive group. Some other examples of
Temporally Ordered Routing Algorithm (TORA) [9]. reactive (also called on-demand) ad hoc network routing protocols are
Dynamic Source Routing (DSR)[5], Ad-hoc On demand Distance Vector
Routing (AODV) [12] and the Temporally Ordered Routing Algorithm
(TORA) [8].
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)" ([1], [2]), is an example of a such a hybrid (ZRP)" ([1], [2],[9]), is an example of a such a hybrid proactive/
proactive/reactive scheme. 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. Globally proactive protocols tend to distribute such
changes widely in the network, incurring large costs. The ZRP limits topological changes widely in the network, incurring large costs. The
propagation of such information to the neighborhood of the change ZRP limits propagation of such information to the neighborhood of the
only, thus limiting the cost of topological updates. change 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 Routing Zones, Extended Routing Zones, and the
(IARP) Intrazone Routing Protocol (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 no greater than some
number, which is referred to as the Zone Radius. An example of a parameter 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.
+-----------------------------------------+ +-----------------------------------------+
| +---+ | | +---+ |
| +---+ ---| F |-------| | | +---+ ---| F |-------| |
+---+ | +---+ --| C |--/ +---+ +---+ | +---+ | +---+ --| C |--/ +---+ +---+ |
| G |-----| D |--/ +---+ | E | | Zone of node A | G |-----| D |--/ +---+ | E | | Routing Zone of
+---+ | +---+ | +---+ +---+ | of radius=2 +---+ | +---+ | +---+ +---+ | node A
| +---+ ---| B |-------| | | +---+ ---| B |-------| | (radius = 2 hops)
| | 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
be reached by two paths from A, one with length 2 hops and one with reached by two paths from A, one with length 2 hops and one with
length 3 hops. 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
This service, which we refer to as bordercasting, allows for more 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 IP multicast
unicasts or an IP multicast (Distance Vector Multicast Routing (Distance Vector Multicast Routing Protocol (DVMRP) [14]) to the
Protocol [13]) to the peripheral nodes. (In cases where peripheral nodes. However, as will be explained later, efficient ZRP
multicasting is supported, the multicasting approach is preferred operation requires that the bordercast service be handled, on a
to reduce the amount of traffic over the air.) However, as will be hop-by-hop basis, by the ZRP.
explained later, efficient ZRP operation requires that these unicast
or multicast services be provided by the ZRP, with IP providing best-
effort delivery to the specified ZRP next hops.
The ZRP supports the proactive maintenance of routing zones
through its proactive Intrazone Routing Protocol (IARP). Through
the IARP, each node learns the identity of and the (minimal)
distance to all the nodes in its routing zone. The IARP may be
derived from a wide range of proactive protocols, such as
Distance Vector (e.g., [8], [10]) or Shortest Path First
(e.g., OSPF [7]). Whatever the choice of IARP is, the base
protocol needs to be modified to ensure that the scope of this
operation is restricted to the radius of a node's routing zone.
Haas, Pearlman Expires December 1999 [Page
3]
INTERNET DRAFT The Zone Routing Protocol June In its basic form, the ZRP's Intrazone Routing Protocol (IARP) is
1999 responsible for providing each node with current view of its routing
zone topology. With this information, a node can identify ITS
peripheral nodes AND construct a bordercast (multicast) tree to them.
However, in order for the bordercast to be carried out, member of the
bordercast tree needs to know the tree's downstream structure. This
can be achieved if each node tracks the routing zone topology of each
of ITS interior routing zone members. This "extended" routing zone
consists of all nodes that are at a minimum distance (in hops) LESS
THAN twice the "basic" routing zone radius.
Because each node needs to proactively acquire route information The IARP may be derived from a variety of existing globally proactive
only for the nodes within its zone, the total amount of IARP traffic protocols that provide a complete view of network connectivity (for
does not depend on the size of the network, which may be quite large example, the Shortest Path First OSPF [6]). The base protocol needs
to be modified to ensure that the scope of the route updates is
restricted to the radius of a node's extended routing zone. Because
each node needs to proactively acquire route information only for the
nodes within its zone, the total amount of IARP traffic does not
depend on the size of the network, which may be quite large.
2.2 The Interzone Routing Protocol (IERP) 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
topology. A node is able to respond positively to any queries for topology. A node is able to respond positively to any queries for its
its routing zone nodes. For large networks, relatively few routing zone nodes. For large networks, relatively few destinations
destinations lie within any particular node's routing zone. In this lie within any particular node's routing zone. In this more likely
more likely case, the node can efficiently continue the propagation case, the node can efficiently continue the propagation of the query,
of the query, through the routing zone-based bordercast delivery through the routing zone-based bordercast delivery mechanism.
mechanism.
2.2.1 Routing Zone Based Route Discovery
The IERP operates as follows: The source node first checks whether
the destination is within its routing zone. (Again, this is possible
as every node knows the content of its zone). If so, the path to the
destination is known and no further route discovery processing is
required. If, on the other hand, the destination is not within the
source's routing zone, the source bordercasts a route query to all of
its peripheral nodes. Now, in turn, all the peripheral nodes execute
the same algorithm: check whether the destination is within their
zone. If so, a route reply is sent back to the source indicating the
route to the destination. If not, the peripheral node forwards the
query to its peripheral nodes, which, in turn, executes the same
procedure. An example of this Route Discovery procedure is
demonstrated in the figure below.
* Some functions of the IERP, including bordercasting, route * The IERP relies on a special sub-protocol, called the Bordercast
accumulation, and query control (see later), are performed by a Resolution Protocol (BRP) to provide the bordercast message delivery
special component of the IERP called the Bordercast Resolution service for route queries. Sections 3.0 and 4.0 describe in detail
Protocol (BRP). Sections 3.0 and 4.0 describe, in detail, the the relationship between the BRP and the IERP.
relationship between the BRP and the IERP proper.
Haas, Pearlman Expires December 1999 [Page 2.2.1 Routing Zone Based Route Discovery
4]
INTERNET DRAFT The Zone Routing Protocol June We illustrate the basic operation of routing zone based route
1999 discovery through a simple (and as we will see, inefficient) IERP
implementation. The source node, in need of a route to a destination
node, first checks whether the destination lies within its routing
zone. (This is possible since every node knows the content of its
routing zone). If a path to the destination is known, no further
route discovery processing is required. On the other hand, if the
destination is not within the source's routing zone, the source
bordercasts a route query to all of its peripheral nodes. Upon
receipt of the route query, each peripheral nodes executes the same
algorithm. If the destination lies within its routing zone, a route
reply is sent back to the source, indicating the route to the
destination. If not, this node forwards the query to ITS peripheral
nodes. This process continues until the query has spread throughout
the network.
+---+ +---+
+---+ | F | +---+ | F |
+---+---| C |----+---+-----+---+ +---+ +---+---| C |----+---+-----+---+ +---+
| D | +---+ | E |----| H | | D | +---+ | E |----| H |
+---+ | +---+-----+---+ +---+ +---+ | +---+-----+---+ +---+
+---+----| B | | +---+----| B | |
| A | +---+-----+---+ +---+ | A | +---+-----+---+ +---+
+---+ | G | | I | +---+ | G | | I |
+---+ +---+ +---+ +---+
| |
+---+ +---+
+---+ | J | +---+ | J |
| C |----+---+----+---+ +---+ | C |----+---+----+---+ +---+
+---+ | K |----| L | +---+ | K |----| L |
+---+ +---+ +---+ +---+
The node A has a datagram to send to node L. Assume a uniform In the example illustrated above, node A has a datagram to send to
routing zone radius of 2 hops. Since L is not in A's routing zone node L. Assuming each node's zone radius is 2 hops, node L does not
(which includes B,C,D,E,F,G), A bordercasts a routing query to its lie within A's routing zone (which does include B,C,D,E,F,G).
peripheral nodes: D,F,E, and G. Each one of these peripheral nodes Therefore, A bordercasts a routing query to its peripheral nodes:
check whether L exists in their routing zones. Since L is not found D,F,E and G. Each one of these peripheral nodes check whether L
in any routing zones of these nodes, the nodes bordercast the request exists in their routing zones. Since L is not found in any routing
to their peripheral nodes. In particular, G bordercasts to K, which zones of these nodes, the nodes bordercast the request to their
realizes that L is in its routing zone and returns the requested peripheral nodes. In particular, G bordercasts to K, which realizes
route (L-K-G-A) to the query source, namely A. that L is in its routing zone and returns the requested route (L-K-G-A)
to the query source, namely A.
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,
source, S, providing S with the desired route. To perform the route S, providing S with the desired route. To perform the route reply,
reply, sufficient information needs to be accumulated during the sufficient information needs to be accumulated during the query phase
query phase so that Y is provided with a route back to S. Providing so that Y is provided with a route back to S. Providing routes from
routes from discovering node Y to query source S, and from the query discovering node Y to query source S, and from the query source S back
source S back to the query destination D (through Y), is the role of to the query destination D (through Y), is the role of the Route
the Route Accumulation procedure. 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
route from the query's source to the current node. By reversing this 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, the route reply can be returned via strict source routing.
Haas, Pearlman Expires December 1999 [Page In order to reduce the length of query packets and query response time,
5] the query packet's accumulated route can be cached among the path's
nodes (in the form of the previous hop toward the query source),
rather than explicitly recorded in the packet itself. During the
reply phase, the cached previous hops can direct the reply back to the
source. Along the way, information can be accumulated in the reply
packet, forming a source route. Alternatively, the discovered route
may be distributed among its nodes' routing tables, providing a next
hop routing solution.
INTERNET DRAFT The Zone Routing Protocol June Sending replies along the (reversed) paths explicitly traveled by the
1999 successful query packets can result in a set of discovered routes that
exhibit limited diversity among. This anomalous behavior can be
explained as follows. Variations in packet forwarding delay often
result in one query packet reaching the destination region ahead of
others. The descendents of this query packet trigger the majority of
route replies. The route diversity problem is aggravated when all
possible paths between the source and destination pass through a
common node, called a topological bottleneck. Since only one query
packet passes through the bottleneck, all discovered routes will be
identical prior to the topological bottleneck.
Given sufficient storage space, a queried node may cache routing This problem could be addressed by allowing a node to relay a route
information accumulated in the query packet, allowing the information query more than once. Alternatively, we can apply "diversity
to be remove from the packet. This has the benefit of reducing the injection" [10] to increase diversity without generating additional
length of the query packet, thereby decreasing the query traffic and route replies. During the route query stage, nodes temporarily cache
query response time. The IP addresses that remain in the packet can the previous hop information for ALL received query packets (including
be used to form a loose source route back to the query's source (If the packets that are discarded). Later, during the reply phase,
ALL nodes have cached the accumulated route information, then this replies are relayed through the shortest of the least selected cached
effectively becomes next hop routing. If no nodes have cached paths that does not produce a routing loop.
accumulated route information, then this defaults to the basic case
previously discussed). The same caching strategy can be applied to
the reply packet on its way back to the source. In this case, a
loose source route to the destination is formed.
2.2.3 Query Control Mechanisms 2.2.3 Query Control Mechanisms
Bordercasting has the potential to support global querying schemes Bordercasting has the potential to support global querying schemes
that are more efficient than flooding. To achieve this efficiency, that are more efficient than flooding. To achieve this efficiency,
the protocol should be able to detect and terminate a query thread the protocol should be able to terminate a bordercasted packet before
when it appears in a previously queried region of the network (i.e. it arrives at a recipient peripheral node lying in a previously
arrives at a node belonging to the routing zone of a previously queried region of the network. The ZRP's ability to provide this
queried node). This detection / termination capability is level of query control capability is significantly limited when
significantly limited when bordercasting is implemented directly bordercast messages are forwarded to peripheral nodes by IP.
through IP unicast or IP multicast.
By implementing bordercasting within the ZRP, the nodes that relay
the query to the peripheral node are able to detect the passing
query. If the underlying IP delivery is (neighbor) broadcast or
if IP is operating in promiscuous mode, then nodes that overhear
a query transmission are also able to detect the query, further
strengthening the Query Detection (QD) mechanism. Upon detecting
a query, the identifying query parameters (i.e. query source,
query ID) are recorded in a Detected Queries Table, to provide a
basis for termination of future threads of that query.
A node can consider a query to be redundant if it has already
detected that query, bordercasted by a different node. If
bordercasting is implemented directly through IP unicast/ multicast,
then a query thread could only be terminated after being received by
the peripheral node (bordercast destination). This could result in
wasted transmissions as a query penetrates into a previously queried
region. Implementing bordercasting in the ZRP allows the protocol to
provide an Early Termination (ET), as the redundant query enters the
previously queried region.
Haas, Pearlman Expires December 1999 [Page To prevent redundant querying, nodes should be able to detect when
6] routing zones that they belong to have been queried. Clearly, a node
that bordercasts a route query is aware that its own zone has been
queried. If bordercast messages are relayed by IP, then the query
will not be detected again until it reappears at the target peripheral
nodes. On the other hand, if bordercast forwarding is performed
within the routing protocol, then all nodes in the bordercast tree
will detect the query. Additional query detection is possible in
shared channel networks if the underlying IP delivery is neighbor
broadcast or if promiscuous mode operation is enabled. In this case,
nodes may "overhear" a query even if they do not belong to the
bordercast tree.
INTERNET DRAFT The Zone Routing Protocol June Standard flood search protocols terminate query packets that are
1999 targeted for (or arrive at) previously queried nodes. We can extend
this idea to the ZRP by discarding route queries before they arrive at
bordercast recipients that belong to a previously queried routing
zone. More precisely, a node will not relay a packet down a branch of
the bordercast tree if each of the branch's downstream "leaves"
(bordercast recipients) either lies inside the routing zone of a
previous bordercasted nodes, or if this node has already relayed the
query to that leaf. This scheme, which we refer to as Early
Termination (ET), relies on the aforementioned Query Detection to
identify which routing zone nodes have already bordercast a query.
The "extended" routing zone maintained by the IARP is then used to
determine the members of these previously bordercasted nodes' routing
zones.
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 Routing Table).
Upon detection of a route failure, a node may choose to notify
the route's source of the failure and / or attempt to repair the
route. A route failure notification consists of a transmission
back to the query source, indicating that the source route has
failed, and possibly the hop at which it failed. This type of
service is provided by protocols like ICMP. The node that detects
the route failure may also try to repair the failed connection by
discovering a route to bypass the failed connection. The repair
discovery process is nearly identical to an initial route discovery.
Route repairs should not be substantially longer than the original
failed connection. Thus, the depth of a repair query can be limited,
through the use of hop counter. This has the advantage of producing
much less query traffic than an unrestricted initial route query.
After a successful repair, the route's source MAY be notified so that
routes are properly selected for use. Alternatively, the repair
could go unreported without compromising the connectivity between
source and destination.
Haas, Pearlman Expires December 1999 [Page
7]
INTERNET DRAFT The Zone Routing Protocol June Upon local detection of a route failure, a node may choose to attempt
1999 a route repair by discovering a path to bypass the failed link. The
repair discovery process is nearly identical to an initial route
discovery. Route repairs should not be substantially longer than the
original failed connection. Therefore, the depth of a repair query
can be limited, through the use of a "time to live" field. This has
the advantage of producing much less query traffic than an
unrestricted initial route query. After a successful repair, the
route's source MAY be notified so that routes are properly selected
for use. Alternatively, the repair could go unreported without
compromising the connectivity between source and destination.
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
Existing Protocols Existing Protocols
------------------ ------------------
IP Internet Protocol IP Internet Protocol
ICMP Internet Control Message Protocol ICMP Internet Control Message Protocol
ZRP Entities ZRP Entities
------------ ------------
IARP IntrAzone Routing Protocol IARP IntrAzone Routing Protocol
IERP IntErzone Routing Protocol IERP IntErzone Routing Protocol
BRP Bordercast Resolution Protocol BRP Bordercast Resolution Protocol
(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) -- Link State Implementation
The Intrazone Routing Protocol (IARP) is responsible for proactively The Intrazone Routing Protocol (IARP) is responsible for proactively
maintaining routes within each node's routing zone. This can be achieved maintaining routes within each node's routing zone. Many traditional
through a variety of different implementations. In fact, many proactive protocols can be modified to serve as an IARP by limiting
traditional proactive protocols can be modified to serve as an IARP by the range of route updates to the boundary of (extended) routing
limiting the range of route updates to the boundary of routing zones. zones.
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.
This particular looping condition result in the "counting to
infinity" problem. By deleting these routes, this problem can be
avoided, allowing the IARP to converge faster.
A node may receive new route information either from a received IARP
packet or from an interrupt generated by its Neighbor Discovery /
Maintenance (NDM) process*. In the special case when a host has
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
their routing zones (i.e. each host with a hop count less than it's
routing zone radius). The node then records the new route information
in its Intrazone Routing Table. If the shortest path to the host has
changed, the terminal broadcasts an IARP packet reflecting the
change.
* IARP relies on the services of a separate protocol (referred to
here as the Neighbor Discovery/Maintenance Protocol) to provide
current information about a host's neighbors. At the least, this
information must include the IP addresses of all the neighbors.
The IARP can be readily configured to support supplemental
link quality metrics.
Haas, Pearlman Expires December 1999 [Page
9]
INTERNET DRAFT The Zone Routing Protocol June
1999
A. Packet Format
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Subnet Mask (Optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop #1 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop #2 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | Route
\| |/ Metrics
\ /
(optional)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Hop Count |
+-+-+-+-+-+-+-+-+
Field Description:
* Destination Address (32 bits)
IP address of the destination host
* Destination Subnet Mask (32 bits)
IP subnet mask associated with the destination
* Next Hop # 1 Address (32 bits)
IP address of the "next hop" host to the destination host
* Next Hop # 2 Address (32 bits)
IP address of the Next Hop #1 's "next hop" host to
the destination host
* 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
in hops
Haas, Pearlman Expires December 1999 [Page
10]
INTERNET DRAFT The Zone Routing Protocol June
1999
B. Data Structures
B.1 Intrazone Routing Table
+---------+--------|-----------------------------------------+
| Dest | Subnet | Routes |
| Addr | Mask |-----------+-----------+-----+-----------+
| | | 0 | 1 | ==> | M-1 |
+---------+--------|-----------+-----------+-----+-----------+
| | | | | ==> | |
|---------+--------|-----------|-----------|-----|-----------|
| | | | | ==> | |
|---------+--------|-----------|-----------|-----|-----------|
| | | | | | | ==> | |
+---------+--------|----| |----+-----------+-----+-----------+
| |
| +---\ +----------|--+--+ +--+
+-----/ | | | |...| |
+----------|--+--+ +--+
Next Hop route
node ID metrics
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.
Haas, Pearlman Expires December 1999 [Page
11]
INTERNET DRAFT The Zone Routing Protocol June
1999
D. State Machine
The IARP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The IARP immediately
acts upon an event and then returns back to the IDLE state.
Notes: 1) X is used as a label for the host running this state
machine.
2) INF is a reserved field value corresponding to
"infinity".
D.1
Event: An IARP packet is received containing route
information to a destination D. The hop count
associated with the received route is LESS THAN
OR EQUAL TO the routing zone radius. The
second next-hop is EQUAL to X.
Action: NONE
D.2
Event: An IARP packet is received containing route
information to a destination D. The hop count
associated with the received route is LESS THAN
the routing zone radius. The second next-hop
is NOT EQUAL to X.
Action: The received route is recorded in the Intrazone
Routing Table. If the received route is shorter
than the previous shortest route to D, then a new
IARP packet containing route information to D
through X is broadcasted.
D.3
Event: An IARP packet is received containing route
information to a destination D. The hop count is
EQUAL TO the routing zone radius. The second
next-hop is NOT EQUAL to X.
Action: The received route is recorded in the Intrazone
Routing Table.
Haas, Pearlman Expires December 1999 [Page
12]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.4
Event: An IARP packet is received containing route
information to a destination D. The hop count is
equal to INF.
Action: The route to D is removed from the Intrazone
Routing Table.
1) If the Intrazone Routing Table still
contains a route to D and the length of the
shortest route has increased due to the route
removal, then the an IARP packet containing the
shortest route to D through X is broadcasted.
2) If the Intrazone Routing Table contains no
more routes to D, then an IARP packet containing
a route to D through X with hop count of INF is
broadcast. A "Host Lost" interrupt is
generated to alert the IERP that D has moved
beyond the routing zone.
D.5
Event: A "Neighbor Found" interrupt is received,
indicating the discovery of a neighbor host N.
Action: For each destination in X's Intrazone Routing
Table, an IARP packet is sent to N containing the
best route to that destination. An IARP packet is
then broadcasted containing the 1 hop route to N
through X.
D.6
Event: A "Neighbor Lost" interrupt is received, indicating
that host N is no longer a neighbor of X
Action: The one hop route to N is removed from the
Intrazone Routing Table.
1) If the Intrazone Routing Table still
contains a route to N and the length of the
shortest route has increased due to the route
removal, then the an IARP packet containing the
shortest route to N through X is broadcasted.
2) If the Intrazone Routing Table contains no
more routes to N, then an IARP packet containing
a route to D through X with hop count of INF is
broadcast. A "Host Lost" interrupt is generated
to alert the IERP that D has moved beyond the
routing zone.
Haas, Pearlman Expires December 1999 [Page
13]
INTERNET DRAFT The Zone Routing Protocol June
1999
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
if (packet arrived)
extract(packet)
else
{
{dest,mask,metric} <-- intrpt
next_hop_1=dest
if (type(intrpt) == "Neighbor Found")
{
for d = each node in Intrazone_Routing_Table
{
best_route = get_shortest_route(Intrazone_Routing_Table,d)
mask = get_mask(Intrazone_Routing_Table, d)
if (best_route->hop_count < ROUTING_ZONE_RADIUS)
{
packet<--{d,mask,MY_ID,best_route->next_hop,
best_route->metric,best_route->hop_count+1}
send(packet,dest)
}
}
hop_count=1
}
else
hop_count=INF
}
former_best_route = get_shortest_route(Intrazone_Routing_Table,dest)
Haas, Pearlman Expires December 1999 [Page
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
remove(Intrazone_Routing_Table, {dest, next_hop_1})
best_route = get_shortest_route(Intrazone_Routing_Table,dest)
if (best_route != NULL)
{
if (best_route->hop_count != former_best_route->hop_count
(AND) best_route->hop_count < ROUTING_ZONE_RADIUS)
{
packet <-- {dest,mask,MY_ID,best_route->next_hop,
best_route->metric,best_route->hop_count+1}
send(packet,BROADCAST)
}
}
else
{
force_intrpt("IERP","Zone Node Lost",{dest})
packet <-- {dest, mask, MY_ID, MY_ID, NULL, INF}
send(packet,BROADCAST)
}
Haas, Pearlman Expires December 1999 [Page
15]
INTERNET DRAFT The Zone Routing Protocol June In this draft, we detail implementations for a Link-State IARP.
1999 Nodes compute intrazone routes based on the link state (neighbor
connectivity) of each extended 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 extended 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.
4.1.2 Link State IARP In addition to computing routes to all nodes in the extended routing
In this version of the IARP, nodes compute intrazone routes based on the zone, the IARP also uses the extended zone topology to construct
link state (neighbor connectivity) of each routing zone node. A node may the bordercast tree of each routing zone member. A node's bordercast
receive link state updates either from an IARP link state packet or from tree can be constructed by first determining the minimum spanning
an interrupt generated by its Neighbor Discovery / Maintenance (NDM) tree for its routing zone, and then pruning interior node leaves.
process*. Link states are maintained in a Link State Table. When all For each bordercast tree, the node should record if it's a member,
pending link state updates have been received (full link state updates and if so, its downstream neighbors and peripheral nodes.
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 * the 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 node'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 link
link quality metrics. quality metrics.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Source Address | | Link Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Destination Address | | Link Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at line 1129 skipping to change at page 9, line 31
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| RESERVED | Metric Type | Metric Value | | | RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | Link | | Link
\| |/ Metrics \| |/ Metrics
\ / | \ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| RESERVED | Metric Type | Metric Value | | | RESERVED | Metric Type | Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
Haas, Pearlman Expires December 1999 [Page
16]
INTERNET DRAFT The Zone Routing Protocol June
1999
Field Description: Field Description:
* Link Source Address (32 bits) * Link Source Address (node_id) (32 bits)
IP address of the reported link's source node. IP address of the reported link's source node.
* Link Destination Address (32 bits) * Link Destination Address (node_id) (32 bits)
IP address of the reported link's destination node. IP address of the reported link's destination node.
* Packet Source Address (32 bits) * Packet Source Address (node_id) (32 bits)
IP address of the node that sent this packet. IP address of the node that sent this packet.
(Used to account for any outstanding link state information) (Used to account for any outstanding link state information)
* Link State ID (16 bits) * Link State ID (unsigned int) (16 bits)
Sequence number used to track the link state history of Sequence number used to track the link state history of
the Link Source node. the Link Source node.
* Zone Radius (8 bits) * Zone Radius (unsigned int) (8 bits)
Routing zone radius of the link's source node. Determines the Routing zone radius of the link's source node. Determines
extent that link state information propagates. the extent that link state information propagates.
* Flags (8 bits) * Flags (boolean) (8 bits)
Flags(0) Full Link Information Flags(0) Full Link Information
Indicates whether this link state information was sent as: Indicates whether this link state information was sent
as:
(0) a PARTIAL link state update (0) a PARTIAL link state update
OR OR
(1) part of a FULL update of all the (1) part of a FULL update of all the
link source's current links link source's current links
Flags(1) Current Link State Update Flags(1) Current Link State Update
Indicates whether more link state information is pending Indicates whether more link state information is pending
for THIS link state update {link_source,state_id} for THIS link state update {link_source,state_id}
(0) INCOMPLETE (0) INCOMPLETE
(1) COMPLETE (1) COMPLETE
Flags(2) All Link State Updates Flags(2) All Link State Updates
Indicates whether more link state updates are pending Indicates whether more link state updates are pending
(0) INCOMPLETE (0) INCOMPLETE
(1) COMPLETE (1) COMPLETE
skipping to change at line 1184 skipping to change at page 10, line 25
Flags(3) Link Destination Subnet Mask Flags(3) Link Destination Subnet Mask
(0) INCLUDED (0) INCLUDED
(1) NOT INCLUDED (1) NOT INCLUDED
Flags(4) Link Status Flags(4) Link Status
(0) DOWN (0) DOWN
(1) UP (1) UP
Flags(5..7) RESERVED for future use. Flags(5..7) RESERVED for future use.
Haas, Pearlman Expires December 1999 [Page * Node/Link Metrics (metric) (X * 32 bits)
17] This section of the packet is used to report the quality
of this link (or link source node).
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) * Metric Type (char) (8 bits)
Type of metric being reported Type of metric being reported
(based on pre-defined metric types) (based on pre-defined metric types)
* Metric Value (16 bits) * Metric Value (unsigned int) (16 bits)
Value of node / link metric specified by Metric Type Value of node / link metric specified by Metric Type
B. Data Structures B. Data Structures
B.1 Intrazone Routing Table B.1 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
+-----------------------|--------------------------------+-----------+
| Dest | Subnet | Routes | Route | Intrazone |
| Addr | Mask | | Metrics | |
| (node_id) | (node_id) | (node_id list) | (metric list) | (boolean) |
|-----------+-----------|----------------+---------------+-----------+
| | | | | |
|-----------+-----------|----------------+---------------+-----------+
| | | | | |
|-----------+-----------|----------------+---------------+-----------+
| | | | | |
+-----------------------|--------------------------------------------+
B.2 Link State Table B.2 Link State Table
+--------+--------+------------+ +-----------|--------+-------+------------------+
| Link | Zone | Link State | Link State Information | Link | Zone | Link | Link State |
| Source | Radius | ID | | Source | Radius | State | Information # |
+--------+--------+------------+ +---|---|-----|-+ | Addr | | ID | |
+---|---|-----|-+ | (node_id) | (int) | (int) | (ls_info list)## |
| | | |---> | | | | | | |...| | | | | +-----------|--------+-------+------------------|
| | ** | | | | |
| | +------------+ +---|---|-----|-+ | | |-------+------------------|
+---|---|-----|-+ | | | | |
| | | |-+ | | |-------+------------------|
| | +------------+ | +---|---|-----|-+ | | | | |
: : : || : +-> | | | | | | | |-----------|--------+-------+------------------|
: : : \||/ : +---|---|-----|-+ | | | | |
: : : \/ : |-----------|--------+-------+------------------|
| | +------------+ +---+---|-----|-+ | | | | |
| | | |---> | | | | | | | | | |-------+------------------|
+--------+--------+------------+ +---+---|-----|-+ | | | | |
| || | || | || | (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 # The first link state entry for each link source
contains the complete link state information contains the complete link state information
corresponding to the Link State ID. corresponding to the Link State ID.
Subsequent entries contain only changes of a single Subsequent entries contain only changes of a single
link state. link state.
A FULL link state entry of link state #k and A FULL link state entry of link state #k and
a PARTIAL entry of link state #(k+1) can be a PARTIAL entry of link state #(k+1) can be
merged into a FULL link state entry of merged into a FULL link state entry of
link state #(k+1) link state #(k+1)
B.3 Pending Link State List ## detail of (ls_info) data type
+---+---|---|---+
| | ||||| |
+---+---|---|---+
(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)
B.3 Bordercast Tree Table
+-----------|-----------+----------------+----------------+
| | | Downstream | Downstream |
| Node | Member | Neighbors | Peripheral |
| | | | Nodes |
| (node_id) | (boolean) | (node_id list) | (node_id list) |
+-----------|-----------+----------------+----------------|
| | | | |
+-----------|-----------+----------------+----------------|
| | | | |
+-----------|-----------+----------------+----------------|
| | | | |
+-----------|---------------------------------------------+
B.4 Pending Link State List
(list of neighbors in the process of sending link state updates) (list of neighbors in the process of sending link state updates)
+----------+ +----------+ +----------+ +----------+ +----------+ +----------+
| | ---> | | . . . | | (node addresses) | | ---> | | . . . | | (node_id list)
+----------+ +----------+ +----------+ +----------+ +----------+ +----------+
B.4 New Neighbors List B.5 New Neighbors List
(list of new neighbors to receive a copy Link State Table, (list of new neighbors to receive a copy Link State Table,
upon completion of updates) upon completion of updates)
+----------+ +----------+ +----------+ +----------+ +----------+ +----------+
| | ---> | | . . . | | (node addresses) | | ---> | | . . . | | (node_id list)
+----------+ +----------+ +----------+ +----------+ +----------+ +----------+
Haas, Pearlman Expires December 1999 [Page B.6 Former Routing Zone Nodes
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) (list of routing zone nodes, prior to routing table updates)
+----------+ +----------+ +----------+ +----------+ +----------+ +----------+
| | ---> | | . . . | | (node addresses) | | ---> | | . . . | | (node_id list)
+----------+ +----------+ +----------+ +----------+ +----------+ +----------+
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,mask,metric) C.3.1 Neighbor_Lost(node,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" (with subnet mask "mask"). has been lost with "node" (with subnet mask "mask").
Any node/link quality measurements are reported in Any node/link quality measurements are reported in
the "metric" list. the "metric" list.
C.3.2 Neighbor_Found(host,mask,metric) C.3.2 Neighbor_Found(node,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" (with subnet mask "mask"). has been confirmed with "node" (with subnet mask "mask").
Any node/link quality measurements are reported in Any node/link quality measurements are reported in
the "metric" list. the "metric" list.
C.4 IERP C.4 IERP
C.4.1 Zone_Node_Lost(host) C.4.1 Zone_Node_Lost(node)
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.
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 node running this state
machine. machine.
2) INF is a reserved field value corresponding to
"infinity".
D.1 D.1
Event: An IARP link state packet is received. Event: An IARP link state packet is received.
Action: The link state update is recorded in the Link State Action: The link state update is recorded in the Link State
Table. Table. If more link state updates are pending,
If more link state updates are pending, then the IARP then the IARP returns to an idle state. Otherwise,
returns to an idle state. Otherwise, X rebuilds its X rebuilds its routing table and the bordercast trees
routing table. Links that lie outside of the routing of its routing zone nodes. Links that lie outside of
zone the routing zone are removed from the Link State
are removed from the Link State Table. X sends its Table. X sends its neighbors all previously
neighbors all previously unforwarded link state updates unforwarded link state updates from its NON-
from its NON-peripheral nodes. Finally, all neighbors peripheral nodes. Finally, all neighbors in the New
in the New Neighbor List are sent the link states of Neighbor List are sent the link states of X's NON-
X's peripheral nodes, and the New Neighbor List is
NON-peripheral nodes, and the New Neighbor List is
cleared. cleared.
Haas, Pearlman Expires December 1999 [Page
20]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.2 D.2
Event: A "Neighbor Found" interrupt is received, indicating Event: A "Neighbor Found" interrupt is received, indicating
the discovery of a neighbor N. the discovery of a neighbor N.
Action: X's new link to N is recorded in the Link State Table Action: X's new link to N is recorded in the Link State Table
and and N is added to the New Neighbors List. If more
N is added to the New Neighbors List. If more link link state updates are pending, then the IARP returns
state to an idle state. Otherwise, X rebuilds its routing
updates are pending, then the IARP returns to an idle table and the bordercast trees of its routing zone
state. Otherwise, X rebuilds its routing table. Links nodes. Links that lie outside of the routing zone
that lie outside of the routing zone are removed from are removed from the Link State Table. X sends its
the neighbors all previously unforwarded link state
Link State Table. X sends its neighbors all previously updates from its NON-peripheral nodes. Finally, all
unforwarded link state updates from its NON-peripheral neighbors in the New Neighbor List are sent the link
nodes. Finally, all neighbors in the New Neighbor List states of X's NON-peripheral nodes, and the New
are sent the link states of X's NON-peripheral nodes, Neighbor List is cleared.
and
the New Neighbor List is cleared.
D.3 D.3
Event: A "Neighbor Lost" interrupt is received, indicating Event: A "Neighbor Lost" interrupt is received, indicating
that node N is no longer a neighbor of X. that node N is no longer a neighbor of X.
Action: The lost link to neighbor N is removed from the Link Action: The lost link to neighbor N is removed from the Link
State Table and N is removed from the New Neighbor State Table and N is removed from the New Neighbor
List. List. If more link state updates are pending, then
If more link state updates are pending, then the IARP the IARP returns to an idle state. Otherwise, X
returns to an idle state. Otherwise, X rebuilds its rebuilds its routing table and the bordercast trees
routing table. Links that lie outside of the routing of its routing zone nodes. Links that lie outside of
zone are removed from the Link State Table. X sends the routing zone are removed from the Link State
its Table. X sends its neighbors all previously
neighbors all previously unforwarded link state updates unforwarded link state updates from its NON-
from its NON-peripheral nodes. Finally, all neighbors peripheral nodes. Finally, all neighbors in the New
in the New Neighbor List are sent the link states of Neighbor List are sent the link states of X's NON-
X's peripheral nodes, and the New Neighbor List is
NON-peripheral nodes, and the New Neighbor List is
cleared. cleared.
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 IARP packet to the following extracts the fields of the IARP packet to the following
variables: {link_source, link_dest, pk_source, state_id, variables: {link_source, link_dest, pk_source, state_id,
skipping to change at line 1412 skipping to change at page 15, line 5
* full_link_state -> flag(0) * full_link_state -> flag(0)
* current_update -> flag(1) * current_update -> flag(1)
* all_updates -> flag(2) * all_updates -> flag(2)
* mask -> flag(3) * mask -> flag(3)
* link_status -> flag(4) * link_status -> flag(4)
load (packet) load (packet)
loads the values of the aforementioned variables into loads the values of the aforementioned variables into
the fields of the IARP packet. 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 E.1 Update Intrazone Routing Table
args: (packet, link_dest, mask, link_metric)
if (packet arrived) // IARP may be triggered by either a link state packet update
// or an interrupt from the NDP
if (packet)
{ {
extract(packet) extract(packet);
my_link_changed = FALSE my_link_changed = FALSE;
} }
else else
{ {
{link_dest,mask,link_metric} <-- intrpt link_source = MY_ID;
link_source = MY_ID pk_source = MY_ID;
pk_source = MY_ID state_id = MY_LINK_STATE_ID;
state_id = MY_LINK_STATE_ID radius = MY_ROUTING_ZONE_RADIUS;
radius = MY_ROUTING_ZONE_RADIUS
full_link_state = 0 full_link_state = 0;
current_update = COMPLETE current_update = COMPLETE;
all_updates = COMPLETE all_updates = COMPLETE;
if (type(intrpt) == "Neighbor Found") if (type(intrpt) == "Neighbor Found")
link_status = UP link_status = UP;
else else
link_status = DOWN link_status = DOWN;
my_link_changed = TRUE my_link_changed = TRUE;
} }
add(Pending_Link_State_List, link_from_id) // Record link state information in Link State Table
status = add(Link_State_Table,link_source, link_dest, mask, radius, add(Pending_Link_State_List, pk_source_id);
link_metric, state_id, flags) status = add(Link_State_Table, link_source, link_dest, mask,
radius, link_metric, state_id, flags);
// Determine if received link state information is new
if (status == NEW_LINK_INFO) if (status == NEW_LINK_INFO)
{ {
cum_status = UPDATE_IN_PROGRESS cum_status = UPDATE_IN_PROGRESS;
if(my_link_changed) if(my_link_changed)
{ {
if (link_status == UP) if (link_status == UP)
add(New_Neighbor_List, link_dest) add(New_Neighbor_List, link_dest);
else else
remove(New_Neighbor_List, link_dest) remove(New_Neighbor_List, link_dest);
MY_LINK_STATE_ID++ MY_LINK_STATE_ID++;
} }
} }
// Release hold on pk_source when all link state information
// from pk_source is received
if(all_updates == COMPLETE) if(all_updates == COMPLETE)
remove(Pending_Link_State_List, link_from_id) remove(Pending_Link_State_List, pk_source);
// Once all pending link state information has been received,
Haas, Pearlman Expires December 1999 [Page // recompute Routing Table
22]
INTERNET DRAFT The Zone Routing Protocol June
1999
if(empty(Pending_Link_State_List) (AND) if(empty(Pending_Link_State_List) (AND)
cum_status == UPDATE_IN_PROGRESS) cum_status == UPDATE_IN_PROGRESS)
{ {
for(each node (BELONGING TO) Intrazone_Routing_Table) // Record former routing zone nodes in order to determine
add(Former_Routing_Zone_Nodes, node) // (later) which nodes have left the routing zone
for((EACH) node (BELONGING TO) Routing_Table)
{
if(Routing_Table[node].Intrazone)
add(Former_Routing_Zone_Nodes, node);
}
// The Link State Table should not contain links that lie
// beyond the (extended) routing zone.
// The Routing Table is recomputed until all outlying links
// have been removed from the Routing Table
rebuild = TRUE; rebuild = TRUE;
while (rebuild) while (rebuild)
{ {
Intrazone_Routing_Table for((EACH) node (BELONGING TO) Routing_Table)
= {
construct_spanning_tree(Link_State_Table); if(Routing_Table[node].Intrazone)
delete(Routing_Table[node]);
}
for((EACH) node (BELONGING TO) Link_State_Table)
{
Routing_Table[node].route =
compute_route_from_links(Link_State_Table,node);
Routing_Table[node].Intrazone = TRUE;
}
rebuild = update(Link_State_Table); rebuild = update(Link_State_Table);
} }
// After recomputing the Routing Table, the bordercast trees
// of the interior routing zone nodes are recomputed
for ((EACH) node (BELONGING TO) Routing_Table)
{
if(Routing_Table[node].Intrazone)
{
Bordercast_Tree[node] =
construct_bordercast_tree(Link_State_Table,node);
}
}
// Broadcast all new link state information that lies
// inside the extended routing zone
broadcast_link_state_updates(Link_State_Table); broadcast_link_state_updates(Link_State_Table);
for (each node (BELONGING TO) New_Neighbor_List)) // Send all link state information that lies inside the
// extended routing zone to each new neighbor
for ((EACH) node (BELONGING TO) New_Neighbor_List))
send_link_state_table(Link_State_Table, node); send_link_state_table(Link_State_Table, node);
clear(New_Neighbor_List);
clear(New_Neighbor_List)
cum_status = UPDATE_COMPLETE; cum_status = UPDATE_COMPLETE;
for (each node (BELONGING TO) Former_Routing_Zone_Nodes) // Alert IERP about any lost routing zone nodes
for ((EACH) node (BELONGING TO) Former_Routing_Zone_Nodes)
{ {
if(node !(BELONGS TO) Intrazone_Routing_Table) if(node !(BELONGS TO) Routing_Table)
force_intrpt("IERP","Zone Node Lost",{node}) Routing_Zone_Node_Lost(IERP, node);
} }
clear(Former_Routing_Zone_Nodes) 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 nodes which are beyond a node's routing
zone. The IERP acquires routing information reactively, exploiting zone. These routes are acquired, on demand, by efficiently probing the
the knowledge of the routing zone topology through the bordercasting network with bordercasted route queries.*
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. A node issues a ROUTE_QUERY when a route is
terminated before reaching the query destination. This provides needed for a destination outside of its routing zone. A ROUTE_QUERY
a faster response to the route query than if the destination, D, for a new route may probe the entire network. In contrast, a route
were to respond directly. However, because D never receives the repair will only trigger a limited depths search. A ROUTE_QUERY is
query, it does not acquire a route back to the source, S. If the guided from a node outward to its peripheral nodes, using the BRP's
D needs to send data back to S (which is often the case, given the bordercast service (described in greater detail in Section 4.3).
bi-directional nature of many applications), a separate route query Because future IERP implementations may not be "routing zone aware",
from D to S would have to be initiated. This substantial overhead the BRP delivers the query up to the IERP at every hop. When the
is avoided by having the query forwarded to D, by the node Y that ROUTE_QUERY is received at the IERP, the previous hop node address is
discovers D in its routing zone. We refer to this as a recorded in the Routing Table and Temporary Query Cache. The previous
QUERY_EXTENSION. hop node address is then overwritten in the packet by the current
node's address. If the ROUTE_QUERY destination lies within this node's
Both the source and destination can acquire routes to each other routing zone, then a ROUTE_REPLY is sent to the query source and a
through the BRP route accumulation mechanisms (to be discussed QUERY_EXTENSION is forwarded to the query destination. Otherwise, the
later). Distributing route information in the caches of the ROUTE_QUERY is sent back down to the BRP.
route's nodes can significantly reduce the size of the IERP packets
and provide for a faster query response. On the other hand, QOS
requirements for a particular application may favor a source
specified route. (rather than a distributed next-hop approach).
Source routing requires that the discovered route information be
accumulated in the IERP packets, rather than cached. This IERP
implementation satisfies the demands for rapid query response
and source routing support by two stages of route reporting. In the
first two stages, route information is cached by the route's nodes
(when possible). Next-hop route are quickly returned to the source
in ROUTE_REPLY packets and forwarded to the destination in QUERY_
EXTENSION packets. At this point, bi-directional connectivity is
established. In the third stage, the source and destination can
provide each other with complete source routes, by sending each
other ROUTE_ACCUMULATION packets. As these packets traverse the
route, the cached route information is accumulated in the packets,
thereby constructing the desired source route.
Variations on this IERP implementation can be realized by combining The QUERY_EXTENSION performs route accumulation in distributed manner,
or eliminating some of these stages. For example, if source routing similar to the ROUTE_QUERY. When the QUERY_EXTENSION arrives at the
is not desired, the ROUTE_ACCUMULATION stage can be eliminated. destination, a next hop route is formed back to the query source.
Also, if all of the route's nodes elect not to cache the routing
information (perhaps due to storage limitations), then the ROUTE_
REPLY and QUERY_EXTENSION packets essentially serve the role of
ROUTE_ACCUMULATION packets, obviating the need for a separate
ROUTE_ACCUMULATION stage.
Haas, Pearlman Expires December 1999 [Page As the ROUTE_REPLY proceeds back the query source, each node selects a
24] previous hop from its Temporary Query Cache (i.e. based on diversity
injection criteria) and appends the address to the packet. When the
ROUTE_REPLY arrives at the query source, it contains a source route
to the destination.
INTERNET DRAFT The Zone Routing Protocol June This IERP version offers some additional features. Multiple
1999 destination route discoveries (for any OR all destinations) can be
aggregated into a single ROUTE_QUERY. In addition, QOS routing is
supported through the collection of various route quality metrics.
Because each node proactively maintains the local topology of its * The bordercast service is provided by the Bordercast Resolution
routing zone, it is not necessary for a source route to specify Protocol (BRP)
every hop along the route (i.e. strict source routing). A properly
chosen subset of the complete source route can be used to specify
the route to the destination, and where desirable, the reverse route
back to the source. The IERP supports such an optimization through
a final ROUTE_OPTIMIZATION stage. The details of the route
optimization are described in the BRP specification. Upon
completion of the ROUTE_OPTIMIZATION stage, sufficient routing zone
membership is acquired for each node in the route so that the source
route may be reduced (by translating this route reduction into
an appropriate set covering problem, and employing a suitable
heuristic).
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
| S | . . . . | Y | . . . | D | | S | . . . . | Y | . . . | D |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
(1) search for ROUTE_QUERY (1) search for ROUTE_QUERY
route |--------------------------> route |-------------------------->
(2) establish ROUTE_REPLY EXTENSION (2) establish ROUTE_REPLY EXTENSION
connectivity <--------------------------| connectivity <--------------------------|
|=============> |=============>
(3) provide ROUTE_ACCUMULATION
(OPTIONAL)
source route |---------------------------------------->
<========================================|
(4) optimize ROUTE_OPTIMIZATION
(OPTIONAL)
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 | TTL | Hop Count | Flags | | Type | TTL | Hop Count | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Current | ROF Ptr | Num Dests = D | Num Nodes = N | | Current Hop Ptr | Num Dests = D | Num Nodes = N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query ID | Reply ID | | Query ID | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query/Route Source Address | | Query/Route Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Replying Node Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bad Link Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Query/Route Destination (1) Address | | | Query/Route Destination (1) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Query/Route Destination (2) Address | | | Query/Route Destination (2) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | | | | |
| | Dests | | Dests
\| |/ | \| |/ |
\ / | \ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Query/Route Destination (D) Address | | | Query/Route Destination (D) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Next IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Next BRP Address | BRP
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fields
| Prev IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Intermediate Node (1) Address | | | Intermediate Node (1) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Intermediate Node (2) Address | | | Intermediate Node (2) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| |
route(1:N)
| | | | | |
| | route(1:N)
\| |/ | \| |/ |
\ / | \ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| |
| Intermediate Node (N) Address | | | Intermediate Node (N) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Node | Metric Type |D| Metric Value | | | Node | Metric Type |D| Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Node | Metric Type |D| Metric Value | | | Node | Metric Type |D| Metric Value | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | Node/ | | Node/
| | | | Segment
Segment \| |/ Metrics
\| |/
Metric(s)
\ / | \ / |
Haas, Pearlman Expires December 1999 [Page
26]
INTERNET DRAFT The Zone Routing Protocol June
1999
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Node | Metric Type |D| Metric Value | | | 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) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
Field Description: Field Description:
* Type (8 bits) * Type (char) (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 three packet types:
ROUTE_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.
ROUTE_REPLY: ROUTE_REPLY:
response to a ROUTE_QUERY packet, sent from the node response to a ROUTE_QUERY packet, sent from the
that discovers the Destination back to the Source. node that discovers the Destination back to the
At a minimum, the ROUTE_REPLY contains Source. 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
the first node which has cached routing first node which has cached routing information
information. If no nodes have cached routing If no nodes have cached routing information, then
information, then the complete source route is the complete source route is returned.)
returned.)
ROUTE_ACCUMULATION (optional):
sent by the Source to the Destination, in
response to a ROUTE_REPLY, and sent by the
Destination to the Source, in response to a
QUERY_EXTENSION. Routing information cached
at the route's nodes is accumulated in this
packet, providing a complete source route at
the destination of this packet.
Haas, Pearlman Expires December 1999 [Page
27]
INTERNET DRAFT The Zone Routing Protocol June
1999
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) * TTL (Time to Live) (unsigned int) (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
configure the depth of a route search, in order to the depth of a route search, in order to control the
control the amount of IERP traffic generated. amount of IERP traffic generated.
* Hop Count (8 bits) * Hop Count (unsigned int) (8 bits)
Hop count from source to current node (ROUTE_QUERY, Hop count from source to current node (ROUTE_QUERY,
QUERY_EXTENSION) or hop count from source to route QUERY_EXTENSION) or hop count from source to route
destination destination (ROUTE_REPLY, ROUTE_ACCUMULATION,
(ROUTE_REPLY, ROUTE_ACCUMULATION, ROUTE_OPTIMIZATION). ROUTE_OPTIMIZATION).
* Flags (8 bits) * Flags (boolean) (8 bits)
Flags(0) ANY destination (0) / ALL destination (1) Flags(0) ANY destination (0) / ALL destination (1)
In the case of multiple destinations, specifies In the case of multiple destinations, specifies
whether whether the ROUTE_QUERY should return routes for
the ROUTE_QUERY should return routes for ANY ANY specified destination, or ALL specified
specified destinations.
destination, or ALL specified destinations.
In the case of a single MULTICAST IP address, In the case of a single MULTICAST IP address,
specifies specifies whether the ROUTE_QUERY should return
whether the ROUTE_QUERY should return routes to ANY routes to ANY member of the multicast group, or
member of the multicast group, or ALL members of the ALL members of the multicast group.
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) Flags(1..7) RESERVED for future use
* Current Hop Pointer (unsigned int) (16 bits)
INDEX of the route (see below) corresponding to the route INDEX of the route (see below) corresponding to the route
node node that has most recently received this packet. (the
that has most recently received this packet. (the first first node in the route has an index of 1).
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 = D (unsigned int) (8 bits)
Number of destinations included in the route query/reply Number of destinations included in the route query/reply
packet. packet. This allows multiple route discoveries to be
This allows multiple route discoveries to be consolidated consolidated into a common route query process. The
into a common route query process. The multiple query multiple query destinations feature is particularly useful
destinations feature is particularly useful for routing to for routing to a multicast group with known members, or
a for locating downstream nodes during the route repair
multicast group with known members, or for locating phase.
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 = N (unsigned int) (8 bits)
Number of nodes IP addresses appearing in the route Number of nodes IP addresses appearing in the route
specification. specification.
* Query ID (16 bits) * Query ID (unsigned int) (16 bits)
Sequence number which, along with the Query Source Address Sequence number which, along with the Query Source Address
(see below) uniquely identifies any ROUTE_QUERY in the (see below) uniquely identifies any ROUTE_QUERY in the
network. network.
* Reply ID (16 bits) * Query/Route Source Address (node_id) (32 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. IP address of the node that initiates the ROUTE_QUERY.
In subsequent stages, this corresponds to the IP address of In subsequent stages, this corresponds to the IP address
the of the discovered route's source node.
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
corresponding to the source of routes failed link.
* Query/Route Destination Addresses (D * 32 bits) * Query/Route Destination Addresses (node_id) (D * 32 bits)
List of IP addresses to be located during the ROUTE_QUERY List of IP addresses to be located during the ROUTE_QUERY
phase. phase. (Either ANY or ALL addresses, depending on the
(Either ANY or ALL addresses, depending on the setting of setting of Flags(0)) In subsequent stages, this field
Flags(0)) contains the IP address of the discovered route's (single)
In subsequent stages, this field contains the IP address of destination node.
the
discovered route's (single) destination node.
* Next IERP Address (32 bits)
IP address of the next IERP recipient
* Next BRP Address (32 bits)
IP address of the next BRP recipient.
(i.e. next hop to the next IERP recipient)
* Prev IERP Address (32 bits)
IP address of the previous IERP recipient
* Route (N * 32 bits) * Route (node_id) (N * 32 bits)
Variable length field that contains the recorded IP Variable length field that contains the recorded IP
addresses addresses of nodes along the path traveled by this
of nodes along the path traveled by this ROUTE_QUERY packet ROUTE_QUERY packet from the Query Source. In subsequent
from the Query Source. stages (after a route to a Query Destination has been
In subsequent stages (after a route to a Query Destination discovered), this set of IP addresses provides a partial
has
been discovered), this set of IP addresses provides a
partial
specification of the route between the Route Source and specification of the route between the Route Source and
Route Route Destination.
Destination.
Haas, Pearlman Expires December 1999 [Page
29]
INTERNET DRAFT The Zone Routing Protocol June
1999
* Node/Segment Metrics (X * 32 bits) * Node/Segment Metrics (metric) (X * 32 bits)
This optional section of the packet can be used to This optional section of the packet can be used to
record a variety of node and segment quality measurements. record a variety of node and segment quality measurements.
(In this context, a segment refers to the communication path (In this context, a segment refers to the communication
between consecutive nodes in the packet's accumulated route. path between consecutive nodes in the packet's accumulated
In the case of neighboring nodes, a segment is equivalent to route. In the case of neighboring nodes, a segment is
a (one-hop) link). equivalent to a (one-hop) link).
* Node (8 bits) * Node (char) (8 bits)
Index of the route corresponding to a particular node. Index of the route corresponding to a particular
node.
* Metric Type (7 bits) * Metric Type (char) (7 bits)
Type of metric being recorded Type of metric being recorded
(based on pre-defined metric types) (based on pre-defined metric types)
* Direction Flag (1 bit) * Direction Flag (boolean) (1 bit)
For segment metrics, specifies either the upstream For segment metrics, specifies either the:
segment (toward Query/Route Source) or the downstream upstream segment (toward Query Source) (0)
segment (toward Query/Route Dest). downstream segment (toward Query Dest) (1)
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
during the optional ROUTE_OPTIMIZATION stage, may be
used to determine the shortest possible specification
for the accumulated source route.
Haas, Pearlman Expires December 1999 [Page
30]
INTERNET DRAFT The Zone Routing Protocol June * Metric Value (unsigned int) (16 bits)
1999 Value of node / segment metric specified by
Metric Type
B. Data Structures B. Data Structures
B.1 Intrazone Routing Table (See IARP Description) B.1 Routing Table (See IARP Description)
B.2 Interzone Routing Table
+---------+-----------------------------------------+ B.2 Temporary Query Cache
| | Routes |
| Dest +-----------+-----------+-----+-----------+
| | 0 | 1 | ==> | M-1 |
+---------+-----------+-----------+-----+-----------+
| | | | ==> | |
|---------|-----------|-----------|-----|-----------|
| | | | ==> | |
|---------|-----------|-----------|-----|-----------|
| | | | | | ==> | |
+---------+----| |----+-----------+-----+-----------+
| |
| +---\ +------|---|--+--+ +--+
+-----/ | | | | |...| | --+ (node 1)
+------|---|--+--+ +--+ |
+------------------------------+
| +------|---|--+--+ +--+
+->| | | | |...| | --+ (node 2)
+------|---|--+--+ +--+ |
| | :
\| |/ :
: \ /
:
| +------|---|--+--+ +--+
+->| | | | |...| | (node N)
+------|---|--+--+ +--+
(a) (b) (c)
(a) Node ID +------------------------------------------------------+ ...
(b) Required Node Flag | Query | Query_ID | Prev_hop | Hop Count |
(for Route Optimization) | Source | | | |
(c) Node/Link Metric |(node_id)|(unsigned int)|(node_id list)|(unsigned int)|
|---------+--------------|--------------+--------------+ ...
| | | | |
|---------+--------------|--------------+--------------+ ...
| | | | |
|---------+--------------|--------------|--------------+ ...
| | | | |
+------------------------------------------------------+ ...
... +--------------+
| Injection |
| Counter |
|(unsigned int)|
... +--------------|
| |
... +--------------|
| |
... +--------------|
| |
... +--------------+
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(packet,source,query_ID,BRP_cache_ID)
Used by the IERP to request transmission of an Used by the IERP to request packet transmission
IERP packet. through the BRP.
C.2.2 Deliver() (same interface as IP deliver()) C.2.2 Deliver(packet,BRP_cache_ID)
Used by the BRP to alert the IERP of the arrival of a Used by the BRP to deliver data packet to the IERP.
data packet. C.3 Lower Layer (IP)
C.3 IARP C.3.1 Send() (specified in IP standard)
C.3.1 Zone_Node_Lost(host) C.3.2 Deliver() (specified in IP standard)
C.4 IARP
C.4.1 Zone_Node_Lost(node)
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.5 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 node running this state
machine. machine.
D.1 D.1
Event: A "Zone_Node_Lost" interrupt is received, Event: A routing zone node is reported lost by the IARP,
indicating that the node H has moved beyond the indicating that a node H has moved beyond the
routing zone. routing zone.
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 AND Proactive Route Repair is enabled, then a
discovery) to H is initiated. route "Repair" (limited depth route discovery) to H
is initiated.
D.2 D.2
Event: A "Host_Unreachable" interrupt is received from the Event: ICMP issues a "Host_Unreachable" message, triggering
ICMP, indicating an unknown destination host D. a route discovery for unreachable host H.
Action: A full depth route discovery to D is initiated. Action: A FULL depth route discovery to H is initiated.
X's query_id is incremented and assigned to a new X's query_id is incremented and assigned to a new
ROUTE_QUERY packet. The route is initialized with the ROUTE_QUERY packet. The route is initialized with
IP addresses of the route's source and destination the IP addresses of the route's source and destination
IP addresses (X and D). Finally, the ROUTE_QUERY IP addresses (X and H). Finally, the ROUTE_QUERY
packet packet is sent to the BRP to be bordercasted.
is bordercasted.
D.3 D.3
Event: A "Source_Route_Failed" or "Proactive_Repair" Event: The IERP or ICMP (via source_route_failed()) triggers
interrupt is received, indicating that the next a "Repair" message, indicating that the next hop
hop, H, specified in a source route does not H specified in a source route cannot be found locally.
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 X's query_id is incremented and assigned to a new
ROUTE_QUERY packet. The route is initialized with the ROUTE_QUERY packet. The route is initialized with
valid portion of the failed route, and the bad link the IP addresses of the route's source and destination
address field is set with X's IP address, to indicate IP addresses (X and H). Finally, the ROUTE_QUERY
the location of the route failure. packet is sent to the BRP to be bordercasted.
Finally, the ROUTE_QUERY packet is bordercasted.
D.4 D.4
Event: A ROUTE_QUERY packet is received with a destination Event: A ROUTE_QUERY packet is received with a destination
that that appears within X's routing zone.
appears within X's routing zone.
Action: X copies the ROUTE_QUERY packet's contents to a Action: The packet's accumulated route information (for the
ROUTE_REPLY, labelling it with its IP address and source)is recorded in X's Routing Table and Temporary
incremented reply_id. Query Cache. The accumulated route is replaced by
A QUERY_EXTENSION is sent to the query destination. X's address and any accumulated route metrics are
updated and compressed.
X copies the ROUTE_QUERY packet's contents to a
ROUTE_REPLY. A loop-free return path is selected
from the Temporary Query Cache (i.e. based on
"Diversity Injection"). X also forwards a
QUERY_EXTENSION to discovered query destination. If
the ROUTE_QUERY packet has not traveled too deep into
the network (i.e. TTL > 0) AND there are still more
destinations to be discovered, then the ROUTE_QUERY
is sent down to the BRP to be relayed outward.
D.5 D.5
Event: A ROUTE_QUERY packet is received with a destination Event: A ROUTE_QUERY packet is received with a destination
that that DOES NOT appear within X's routing zone.
DOES NOT appear within X's routing zone.
Action: The ROUTE_QUERY packet is bordercasted.
Haas, Pearlman Expires December 1999 [Page
32]
INTERNET DRAFT The Zone Routing Protocol June Action: The packet's accumulated route information (for the
1999 source) is recorded in X's Routing Table and
Temporary Query Cache. The accumulated route is
replaced by X's address and any accumulated route
metrics are updated and compressed. The ROUTE_QUERY
packet is sent down to the BRP to be relayed outward.
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_ACCUMULATION Action: The packet's accumulated route information (for the
packet. The ROUTE_ACCUMULATION packet is sent to the source) is recorded in X's Routing Table. The
query source. accumulated route is replaced by X's address and any
accumulated route metrics are updated and compressed.
If X is not the query destination, then X forwards the
message toward the destination (directly through IP)
D.7 D.7
Event: A ROUTE_REPLY packet is received. Event: A ROUTE_REPLY packet is received.
Action: The packet contents are moved to a ROUTE_ACCUMULATION Action: The packet's accumulated route information (for the
packet. The ROUTE_ACCUMULATION packet is sent to the destination) is recorded in X's Routing Table. X
query destination. adds its address to the accumulated route and adds
metrics for the downstream (toward the destination)
D.8 link to the accumulated metrics. If X is not the
Event: A ROUTE_ACCUMULATION packet is received. X is not query source, then X forwards the message toward the
the final destination of this packet source (directly through IP), along a path selected
(i.e. X != IERP_next). This only occurs when the from the Temporary Query Cache (i.e. based on
accumulated route contains a repair Diversity Injection).
Action: The bad link is replaced by the path repair in the
Interzone Routing Table.
D.9
Event: A ROUTE_ACCUMULATION packet is received. X is
either the route source or (route destination).
Action: The (reversed) accumulated route is added to the
Interzone Routing Table or replaces a failed route
if the packet specifies a bad link. In addition,
if X is the ROUTE_ACCUMULATION destination, the
packet contents may be moved to a ROUTE_OPTIMIZATION
packet, which is then sent to the query destination
(query source).
D.10
Event: A ROUTE_OPTIMIZATION packet is received.
Action: The routing zone membership information that is
collected in the ROUTE_OPTIMIZATION packet is
processed. The resulting optimized route(s) are
added to the Interzone Routing Table.
E. Pseudocode Implementation 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, TTL, hop_count, flags, current_hop_ptr, variables: {type, TTL, hop_count, flags, current_hop_ptr,
query_id, reply_id, source, reply_node, query_id, reply_id, source, reply_node,
bad_link_source, dests, next_IERP, next_BRP, dests, route, metric}
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: load(packet) automatically computes the values of:
num_dests = |dests| num_dests = |dests|
num_nodes = |routes| num_nodes = |routes|
E.1 Routing Zone Node Lost E.1 Routing Zone Node Lost
args: (lost_node)
{lost_host} <-- intrpt // Determine if lost_node belongs to any stored routes.
repair_link = FALSE // If so, the route should be removed from the
for host = each host in Interzone Routing Table // Routing Table and a route repair triggered
// (if proactive route repairs are enabled)
repair_link = FALSE;
for((EACH) node (BELONGING TO) Routing Table)
{ {
for (route = each Interzone route to host) for ((EACH) route (BELONGING TO) Routing_Table[node])
{ {
if (lost_host (EXISTS IN) route) if (lost_node (BELONGS TO) route)
{ {
if (PROACTIVE_REPAIRS_ENABLED) if (PROACTIVE_REPAIRS_ENABLED)
{ {
removal_timer = ROUTE_QUERY_TIMEOUT removal_timer = ROUTE_QUERY_TIMEOUT;
repair_link = TRUE repair_link = TRUE;
} }
else else
removal_timer = 0 {
schedule( removal_timer = 0;
remove(Interzone_Routing_Table[host]->route(m)), }
removal_timer) schedule(remove(Routing_Table[node,route],removal_timer)
} }
} }
} }
if(repair_link) if(repair_link)
{ {
dests = lost_host dests = lost_node;
force_intrpt("IERP","Proactive_Repair",{MY_ID,dests,ALL}) Initiate_Route_Discovery(IERP, {dests, ALL, REPAIR});
} }
E.2 Initiate Route Discovery E.2 Initiate Route Discovery
args: (dests, flags, type)
{source,dests,flag} <-- intrpt // Route query is initialized and sent down to the BRP
// to be bordercasted
if (type(intrpt) == "Proactive_Repair" (OR) if (type == REPAIR)
type(intrpt) == "Source_Route_Failed") TTL = MAX_REPAIR_HOPS;
{
TTL = MAX_REPAIR_HOPS
bad_link_source = MY_ID
}
else else
{ TTL = MAX_FULL_QUERY_HOPS;
TTL = MAX_FULL_QUERY_HOPS
bad_link_source = NULL
}
query_id = MY_QUERY_ID++
load (packet)
send (packet, BORDERCAST)
Haas, Pearlman Expires December 1999 [Page
34]
INTERNET DRAFT The Zone Routing Protocol June source = MY_ID
1999 query_id = MY_QUERY_ID++;
type = ROUTE_QUERY;
hop_count = 0;
route = NULL;
current_hop_ptr = 0;
load (packet);
send ((packet, source, query_id, NULL), BRP);
E.3 Receive IERP Packet E.3 Receive IERP Packet
args: (packet, BRP_cache_ID)
extract(packet) extract(packet);
switch(type) switch(type)
{ {
case: ROUTE_QUERY case: ROUTE_QUERY
if (dest (EXISTS IN) Intrazone_Routing_Table) // Update Time-to-Live and hop count
{ TTL--;
type = ROUTE_REPLY hop_count++;
reply_id = MY_REPLY_ID++
if(bad_link_source)
IERP_next = bad_link_source
else
IERP_next = source
load(packet)
send(packet,IERP_next)
type = QUERY_EXTENSION // Extract route (and metrics) from packet and record
IERP_next = dest // them in the Routing Table and Temporary Query Cache
load(packet) prev_hops = route(1 : current_hop_ptr);
send(packet,IERP_next) metrics = compress(metrics,
} get_metrics(prev_hops|prev_hop|,MY_ID));
else add(Routing_Table[source],(reverse(prev_hops),
send(packet,BORDERCAST) reverse(metrics),FALSE);
break add(Temp_Query_Cache[source,query_id],
case: QUERY_EXTENSION (reverse(prev_hops),hop_count));
type = ROUTE_ACCUMULATION
IERP_next=source // Determine if routes are known for each destination
load(packet) find_all = flags(0);
send(packet, IERP_next) find_any = !flags(0);
break found_any = FALSE;
case: ROUTE_REPLY found_all = TRUE;
type = ROUTE_ACCUMULATION
IERP_next = dest // Save current values for dests and metrics, since
load(packet) // we may need them later
send(packet, IERP_next) DESTS = dests;
break METRICS = metrics;
case: ROUTE_ACCUMULATION for((EACH) dest (BELONGING TO) DESTS)
if (bad_link_source)
{ {
if(bad_link_source != source) if (Routing_Table[dest].Intrazone)
repair_src_ptr = get_index(route, bad_link_source) {
else // A route to this destination is known
repair_src_ptr = 0 found_any = TRUE;
dests = dest;
remove(dest, DESTS);
bad_link = {bad_link_source,dest} // Forward query directly to destination, so
path_repair = {bad_link_source, // that the destination will have some routing
route(repair_src_ptr+1:|route|), // information back to the source
dest} type = QUERY_EXTENSION;
replace_link(Interzone_Routing_Table,IERP,bad_link, prev_hops = NULL;
path_repair) next_hops = Routing_Table[dest].route;
route = {prev_hops,MY_ID,next_hops};
current_hop_ptr = |prev_hops|+1;
load(packet);
send((packet,next_hops(1)),IP);
// Send reply back to the source
type = ROUTE_REPLY;
reply_node = MY_ID;
reply_id = MY_REPLY_ID++;
next_hops = Routing_Table[dest].route;
prev_hops = inject_loopfree_path(next_hops,
Temp_Query_Cache[source,query_id]);
metrics = NULL;
route = {prev_hops,MY_ID,next_hops};
current_hop_ptr = |prev_hops|+1;
load(packet);
send((packet,prev_hops(|prev_hops|)),IP);
}
found_all = found_all && found_any;
} }
Haas, Pearlman Expires December 1999 [Page // If more destinations need to be discovered then
35] // forward QUERY via BRP bordercasting
if(((find_all && !found_all)||(find_any && !found_any))
INTERNET DRAFT The Zone Routing Protocol June && TTL>0)
1999 {
dests = DESTS;
metrics = METRICS;
prev_hops = NULL;
next_hops = NULL;
route = {prev_hops, MY_ID, next_hops};
current_hop_ptr = |prev_hops|+1;
load(packet);
send((packet,BRP_cache_ID), BRP);
}
break;
case: QUERY_EXTENSION
// Extract route (and metrics) from packet and record
// them in the Routing Table
prev_hops = route(1 : current_hop_ptr);
next_hops = route(current_hop_ptr+1 : |route|);
metrics = compress(metrics,
get_metrics(prev_hops|prev_hop|,MY_ID));
add(Routing_Table[source],(reverse(prev_hops),
reverse(metrics),FALSE);
// Forward query extension until it reaches destination
if(MY_ID !(BELONGS TO) dests)
{
prev_hops = NULL;
if(|next_hops|==1)
{
next_hops = Routing_Table[dest].route;
route = {prev_hops, MY_ID, next_hops};
current_hop_ptr = |prev_hops|+1;
}
else else
{ {
if (IERP_next == source) current_hop_ptr++;
add(Interzone_Routing_Table, IERP, dest, }
next_hops,metric) load(packet);
if (IERP_next == dest) send((packet,next_hops(1)),IP);
add(Interzone_Routing_Table, IERP,
source, reverse(prev_hops),metric)
} }
break;
if (MY_ID == IERP_next) case: ROUTE_REPLY
// Extract route (and metrics) from packet and record
// them in the Routing Table
prev_hops = route(1 : current_hop_ptr-1);
next_hops = route(current_hop_ptr : |route|);
metrics = {metrics,get_metrics(MY_ID,next_hops(1))};
add(Routing_Table[dest],(next_hops,compress(metrics),FALSE);
// Forward reply until it reaches source
if(MY_ID != source)
{ {
if (MY_ID == source) // Choose a loopfree return path from the Temporary
IERP_next = dest // Query Cache (eg. shortest path, shortest least
if (MY_ID == dest) // "injected" path, etc.)
IERP_next = source
type = ROUTE_OPTIMIZATION prev_hops = inject_loopfree_path(next_hops,
load (packet) Temp_Query_Cache[source,query_id]);
send (packet, IERP_next) route = {prev_hops, MY_ID, next_hops};
current_hop_ptr = |prev_hops|+1;
load(packet);
send((packet,next_hop),IP);
} }
break break;
case: ROUTE_OPTIMIZATION
if (MY_ID == source)
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
} }
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 provides the "bordercasting" message delivery service, here
bordercasting, query control, route accumulation and routing zone used to forward IERP route queries. Messages are relayed from a
labelling, which form the basis for the route discovery procedure. bordercasting node outward to its peripheral nodes, along a
bordercast (multicast) tree. Although the intended recipients of
In this BRP implementation, bordercasting is implemented as a series the bordercast are the peripheral nodes, the BRP may deliver the
of unicasted messages to the peripheral nodes. The BRP is able to bordercast message up to the higher layer application (in this case,
identify the peripheral nodes based on the information contained in the IERP) at EVERY hop. This may be necessary for applications that
the Intrazone Routing Table. Rather than unicasting to the peripheral use bordercasting, but are generally not "routing zone aware".
node directly through IP, the bordercasted packets are relayed to
the peripheral nodes by the BRP layer. IP is used only to send
these messages one hop toward the peripheral nodes. This allows the
BRP to detect all ROUTE_QUERY packets that are received by that node.
To efficiently terminate the query, the BRP needs to record When a node receives a bordercasted message, it first needs to determine
sufficient information from each detected query. The query's source whether the message should be forwarded. Clearly, the node should
and ID, which serve to uniquely identify a query, are added to the only forward the message if it belongs to the bordercast tree.
Detected Queries Table. In addition, the IP address of the last Furthermore, if the node is the (peripheral node) bordercast recipient,
node to bordercast the query is also recorded in the Detected it would re-bordercast the message, but only if it has not been a bordercast
Queries table. Any threads of this query that are later received recipient before AND it does not lie inside the routing zone of a
from a different bordercasting node are discarded. Each query also detected "previously bordercasted" node.
contains a hop counter that is decremented at each node. When the
counter expires, the packet is discarded.
IERP packets (excluding ROUTE_OPTIMIZATION packets) that are not If the node decides not to discard the message, it next determines which
terminated next undergo a route accumulation procedure. As of the current bordercast tree's downstream branches will be dropped.
described earlier, route accumulation is used to construct routes, A downstream branch will be dropped if each of the branch's downstream
by recording the IP addresses of a route's nodes in the IERP packet peripheral nodes either has had a bordercast message relayed to it by
or local cache. The Detected Queries Table, extended by two this node OR lies inside the routing zone of a detected previously
columns, serves as a convenient route accumulation cache. bordercasted node.
The node begins the route accumulation procedure by adding its IP The BRP delivers the message up to the higher layer application (IERP).
address to the IERP route. This is followed by the IP addresses of After some processing, the application may return an updated message
any cached nodes leading to the packet's destination (the "next back to the BRP. The BRP will then relay the message on the selected
hops"). This is sufficient processing for ROUTE_ACCUMULATION outgoing links.
packets, where complete source routes are constructed. On the other
hand, ROUTE_QUERY, QUERY_EXTENSION and ROUTE_REPLY packets should carry
as
little of the route as possible. Therefore, if cache space is
available, the route accumulation process records the IP addresses
of the "previous hops" from the packet's source, and removes them
from the IERP packet.
The final role of the BRP is to contribute to the ROUTE_OPTIMIZATION A. Packet Format
process by indicating the mutual routing zone membership of the
nodes in the source route. This is done by appending a special
flag field to the ROUTE_OPTIMIZATION packet. The status of the
k-th bit in the flag field indicates whether the k-th hop in the
source route is a member of the node's routing zone. This
membership information is eventually processed at the source to
determine the smallest set of routing zones that cover the route
(and therefore the smallest set of nodes needed to specify this
route through loose source routing).
Haas, Pearlman Expires December 1999 [Page +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
37] | Message Source Addresss |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prev Bordercast Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| E N C A P S U L A T E D P A C K E T |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
* Message Source Address (node_id) (32 bits)
IP address of the node that initiates the message.
INTERNET DRAFT The Zone Routing Protocol June * Message ID (unsigned int) (16 bits)
1999 Sequence number which, along with the Message Source
Address uniquely identifies any BRP message in the
network.
A. Packet Format * Prev Bordercast Address (node_id) (32 bits)
IP address of the most recent bordercasting node
See IERP packet format in Section 4.2 * Encapsulated Packet (packet)
B. Data Structures *** note: Within the context of the ZRP, the Message Source
Address and Message ID can assume the same values
as the corresponding "Query" fields in the
encapsulated IERP packet.
As such, they can be eliminated AS LONG AS:
(a) The BRP has read access to the contents of
the encapsulated IERP packet.
(b) The BRP knows the format of the IERP packet.
B.1 Intrazone Routing Table (see IARP description) For this version of the ZRP, both (a) and (b) are true.
However, we provide the BRP with its own Message ID and
Message Source fields for future support of generic
higher layer applications.
B.2 Interzone Routing Table (see IERP description) B. Data Structures
B.3 Detected Queries Table B.1 Routing Table (see IARP description)
+--------------------+--------+ B.2 Bordercast Tree Table (see IARP description)
| Query | Query | Prev | B.3 Detected Messages Cache
| Source | ID | IERP |
|----------+---------|--------|
| | | |
|----------+---------|--------|
| | | |
|----------+---------|--------|
| | | |
+--------------------+--------+
B.4 Detected Replies Table +------------------------|--------------------------+ ...
| Message | Message ID | BRP_cache_ID | Prev |
| Source | | |Bordercast |
|(node_id)|(unsigned int)|(unsigned int)| (node_id) |
|---------+--------------|--------------+-----------+ ...
| | | | |
| | |--------------+-----------+ ...
| | | | |
|---------+--------------|--------------+-----------+ ...
| | | | |
| | |--------------+-----------+ ...
| | | | |
+------------------------|--------------+-----------+ ...
+--------------------+ ... +---------------+
| Reply | Reply | | Out_neighbor |
| Node | ID | | |
|----------+---------| |(node_id list) |
| | | ... +---------------|
|----------+---------| | |
| | | ... +---------------|
|----------+---------| | |
| | | ... +---------------|
+--------------------+ | |
... +---------------|
| |
... +---------------+
C. Interfaces C. Interfaces
C.1 Higher Layer (i.e. IERP) C.1 Higher Layer (IERP)
C.2.1 Send() (same interface as IP Send() primitive) C.2.1 Send(packet, BRP_cache_ID)
Used by higher layer protocol to request transmission of Used by the IERP to request packet transmission.
a data packet C.2.2 Deliver(packet, BRP_cache_ID)
C.2.2 Deliver() (same interface as IP Deliver() primitive) Used by the BRP to deliver a data packet up to IERP.
Used by the BRP to alert the higher layer protocol of
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 node running this state
machine. machine.
2) NULL is a reserved field value, corresponding to an
invalid IP address.
D.1 D.1
Event: A ROUTE_QUERY packet is received from the IERP. Event: A message is received from the higher layer (IERP).
BRP_cache_ID == NULL.
Action: If X is the query's source, then the identifying Action: The bordercast was initiated by X. X marks itself as
querying the previous bordercast node and relays the message to
information is recorded in the Detected Queries Table. all the downstream neighbors in its bordercast tree.
X adds its IP address to the packet's route. A copy of
the
packet is sent to the IERP layer of each peripheral
node,
by way of a BRP transmission to the next hop to that
peripheral node.
D.2 D.2
Event: A ROUTE_QUERY packet is received from the IP. The hop Event: A message is received from the higher layer (IERP).
counter has expired or the query was already BRP_cache_ID != NULL.
detected from another bordercasting node.
Action: The packet is discarded. Action: The bordercast was not initiated by X. X looks up
this message's forwarding information recorded in
it's Detected Messages Cache (and referenced by
BRP_cache_ID). X then relays the message to the
designated downstream neighbors.
D.3 D.3
Event: A ROUTE_QUERY packet is received from IP. The hop Event: A message is received from the IP.
count
has not expired and the query has not been previously
detected (or was detected from the same bordercasting
node).
X is not the intended BRP recipient.
Action: Identifying query information is recorded in the
Detected
Queries Table. The packet is then discarded.
D.4
Event: A ROUTE_QUERY packet is received from the IP. The hop
count has not expired and the query has not been
previously detected (or was previously detected
from the same bordercasting node). X is the
intended BRP recipient, but is not the intended
IERP recipient and the query destination does
not lie within X's routing zone.
Action: The hop counter is decremented. Identifying query
information is recorded in the Detected Queries Table
and accumulated route information is recorded
in the Interzone Routing Table. The recorded route
information is removed from the packet and X adds
its IP address to the route.
The packet is then sent to the BRP of the next hop
to the intended IERP recipient.
Haas, Pearlman Expires December 1999 [Page
39]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.5
Event: A ROUTE_QUERY packet is received from the IP. The hop
count has not expired and the query has not been
previously detected (or was previously detected
from the same bordercasting node). X is the
intended BRP recipient, and either X is the
intended IERP recipient, OR the query destination
lies in X's routing zone.
Action: The hop counter is decremented. Identifying query
information is recorded in the Detected Queries Table
and accumulated route information is recorded in the
Detected Queries Table. The recorded route information
is removed from the packet and X adds its IP address
to the route.
The packet is then delivered up to the IERP.
D.6
Event: A QUERY_EXTENSION is received from the IERP.
Action: The packet is sent to the BRP layer of the
next hop to the specified IERP recipient
(in this case, the query destination).
D.7
Event: A QUERY_EXTENSION is received from the IP.
X is not the intended BRP recipient.
Action: Identifying query information is recorded in the
Detected Queries Table and accumulated route
information is recorded in the Interzone Routing
Table.
The packet is then discarded.
D.8
Event: A QUERY_EXTENSION packet is received from the IP.
X is the intended BRP recipient, but is not the
intended IERP recipient.
Action: Identifying query information is recorded in the
Detected Queries Table and accumulated route
information is recorded in the Interzone Routing
The recorded route information is removed from the
packet and X adds its IP address to the route.
The packet is then sent to the BRP of the next hop
to the intended IERP recipient.
Haas, Pearlman Expires December 1999 [Page
40]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.9
Event: A QUERY_EXTENSION packet is received from the IP.
X is the intended BRP recipient and the intended
IERP recipient.
Action: Identifying query information is recorded in the
Detected Queries Table and accumulated route
information is recorded in the Interzone Routing
Table. The recorded route information is removed
from the packet and X adds its IP address to the
route. The packet is then delivered up to the IERP.
D.10
Event: A ROUTE_REPLY packet is received from the IERP.
Action: The IP addresses of X and the previous hops back
to the query source (cached in the Detected Queries
Table) are added to the route. The packet is sent
back to the IERP layer of the query source, by way
of a BRP layer transmission to the first hop back
to the query source.
D.11
Event: A ROUTE_REPLY packet is received from the IP.
X is not the intended BRP recipient or the
ROUTE_REPLY was previously detected.
Action: The packet is discarded.
D.12
Event: A ROUTE_REPLY packet is received from the IP.
X is the intended BRP recipient, but not the
intended IERP recipient.
The ROUTE_REPLY was not previously detected.
Action: Identifying query information is recorded in the
Detected Replies Table and accumulated route
information is recorded in the Interzone Routing
Table. The IP addresses of X and the previous hops
back to the query source (previously recorded in the
Interzone Routing Table) are added to the route.
The packet is then sent to the BRP layer of the
previous hop back to the query source.
D.13
Event: A ROUTE_REPLY packet is received from the IP.
X is the intended BRP recipient and the intended
IERP recipient.
The ROUTE_REPLY was not previously detected.
Action: Identifying query information is recorded in the
Detected Replies Table and accumulated route
information is recorded in the Interzone Routing
Table. The recorded route information is removed
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
Event: A ROUTE_ACCUMULATION packet is received from the IERP.
Action: The packet is sent to the IERP layer of the specified
IERP recipient by way of a BRP transmission to the next
hop toward the IERP recipient.
D.15
Event: A ROUTE_ACCUMULATION packet is received from the IP.
X is not the intended BRP recipient.
Action: The packet is discarded.
D.16
Event: A ROUTE_ACCUMULATION packet is received from the IP.
X is the intended BRP recipient, but not the intended
IERP recipient.
Action: The IP addresses of X and the next hops to the intended
IERP recipient (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.
D.17
Event: A ROUTE_ACCUMULATION packet is received from the IP.
X is the intended BRP recipient and the intended
IERP recipient.
Action: The packet is delivered up to the IERP.
D.18
Event: A ROUTE_OPTIMIZATION packet is received from the IERP.
Action: X indicates (in its ROF field) those route nodes that
belong to its routing zone. The packet is then sent to
the IERP layer of the specified IERP recipient, by way
of a BRP transmission to the next hop toward the
IERP recipient.
D.19
Event: A ROUTE_OPTIMIZATION packet is received from the IP.
X is not the intended BRP recipient.
Action: The packet is discarded.
Haas, Pearlman Expires December 1999 [Page
42]
INTERNET DRAFT The Zone Routing Protocol June
1999
D.20 Action: The message is terminated under the following
Event: A ROUTE_OPTIMIZATION packet is received from the IP. conditions:
X is the intended BRP recipient, but not the intended (1) X does not belong to the bordercast tree of
IERP recipient. prev_bcast.
(2) If X is the bordercast recipient and
(a) X has already been a bordercast recipient.
OR
(b) X is an interior (i.e. non-peripheral)
member of a detected previously
bordercasted node's routing zone.
Action: X indicates (in its ROF field) those route nodes that If X is a bordercast recipient and does not terminate
belong to its routing zone. the message then it re-bordercasts the message.
The packet is then sent to the IERP layer of the
specified next hop toward the IERP recipient.
D.21 Next, X decides which of the current bordercast
Event: A ROUTE_OPTIMIZATION packet is received from the IP. tree's downstream branches (neighbor) will be dropped.
X is the intended BRP recipient and the intended A downstream branch will be dropped if, for each of
IERP recipient. the branch's downstream peripheral node D:
(a) X has already relayed a message to D.
OR
(b) D is an interior (i.e. non-peripheral)
member of a detected previously
bordercasted node's routing zone
Action: X indicates (in its ROF field) those route nodes that Finally, X delivers the message to the higher layer
belong to its routing zone. The packet is then (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 BRP packet to the following
variables: {type, TTL, hop_count, flags, current_hop_ptr, variables: {source,message_id,prev_bordercst,
query_id, reply_id, source, reply_node, message_packet)
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 BRP 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
extract(packet)
switch(type)
{
case: ROUTE_QUERY
IERP_prev = MY_ID
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)
{
if (IERP_next is a peripheral node)
{
BRP_next=get_shortest_route(Intrazone_Routing_Table,
IERP_next)->next_hop
metric =get_metric(Intrazone_Routing_Table,BRP_next)
load(packet)
send(packet,BRP_next)
}
}
break
case: QUERY_EXTENSION
BRP_next=get_shortest_route(Intrazone_Routing_Table,
IERP_next)->next_hop
load(packet)
send(packet,BRP_next)
break
Haas, Pearlman Expires December 1999 [Page
44]
INTERNET DRAFT The Zone Routing Protocol June
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)) E.1 Receive Packet from higher layer (IERP)
{ args: (message_packet, BRP_cache_ID)
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) // If BRP_cache_ID == NULL then this is a new bordercast
current_hop_ptr = |prev_hops|+1 // issued by this node. This new bordercast can be relayed
route = {prev_hops, MY_ID, next_hops} // to ALL downstream neighbors in the bordercast tree.
load(packet) // Otherwise, this is an existing bordercast that should be
send(packet,BRP_next) // forwarded to the pre-assigned downstream neighbors.
break
case: ROUTE_ACCUMULATION if(BRP_cache_ID)
if(IERP_next == source)
{
BRP_next = route(|route|)
current_hop_ptr = |route|+1
}
if(IERP_next == dest)
{ {
BRP_next = route(1) prev_bcast = Detected_Messages[source,message_id
current_hop_ptr = 0 ,BRP_cache_ID].prev_bcast;
out_neighbors = Detected_Message
[source,message_id,BRP_cache_ID].out_neighbors;
} }
load(packet)
send(packet,BRP_next)
break
Haas, Pearlman Expires December 1999 [Page
45]
INTERNET DRAFT The Zone Routing Protocol June
1999
case: ROUTE_OPTIMIZATION
ROF = NULL
for (node = {source,route,dest})
{
if ((EXISTS) Intrazone_Routing_Table[node])
ROF = {ROF,1}
else else
ROF = {ROF,0}
}
if(IERP_next == dest)
{ {
BRP_next = route(1) prev_bcast = MY_ID;
current_hop_ptr = 0 out_neighbors = Bordercast_Tree[MY_ID].downstream_neighbors;
}
if(IERP_next == source)
{
BRP_next = route(|route|)
current_hop_ptr = |route|+1
} }
load(packet) source = MY_ID;
send(packet,BRP_next) message_id = MY_BORDERCAST_ID++;
break load(packet);
send(packet,out_neighbors),IP);
E.2 Receive Packet from IP E.2 Receive Packet from IP
args: (packet)
extract(packet) extract(packet);
switch(type)
{
case ROUTE_QUERY:
if (TTL > 0 (AND)
(!EXISTS(Detected_Queries[source,query_id] (OR)
Detected_Queries[source,query_id]->from == IERP_prev))
{
TTL--
hop_count++
prev_hops = route(1 : current_hop_ptr)
next_hops = route(current_hop_ptr+1 : |route|)
if(bad_link_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)
}
Haas, Pearlman Expires December 1999 [Page
46]
INTERNET DRAFT The Zone Routing Protocol June
1999
if (status == RECORDED_ROUTE)
{
prev_hops = NULL
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)
}
else
{
d = dests (BELONGING TO) Intrazone_Routing_Table
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)
send(packet, BRP_next)
}
}
}
else
discard(packet)
}
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)
}
break
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])
{
hop_count++
prev_hops = route(1: current_hop_ptr)
next_hops = route(current_hop_ptr+1 : |route|)
if(bad_link_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)
}
if (status == RECORDED_ROUTE)
{
prev_hops = NULL
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)
}
else
{
BRP_next=get_shortest_route(Intrazone_Routing_Table,
IERP_next)->next_hop
metric =
{metric,get_metric(Intrazone_Routing_Table,
BRP_next)}
load(packet)
send(packet, BRP_next)
}
}
else
discard(packet)
}
else
discard(packet)
break
Haas, Pearlman Expires December 1999 [Page
48]
INTERNET DRAFT The Zone Routing Protocol June
1999
case ROUTE_REPLY:
if(MY_ID == BRP_next (AND)
!EXISTS(Detected_Queries[source,query_id]))
{
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)
{
next_hops = NULL
metric = compress_metric(metric)
}
if (prev_hops(1) == MY_ID)
{
prev_hops=reverse(Interzone_Routing_Table[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)
}
else
{
metric = {metric,get_metric(Intrazone_Routing_Table,
BRP_next)}
route = {prev_hops, MY_ID, next_hops}
current_hop_ptr = |prev_hops|+1
load(packet)
send(packet,BRP_next)
}
}
else
discard(packet)
break
Haas, Pearlman Expires December 1999 [Page
49]
INTERNET DRAFT The Zone Routing Protocol June
1999
case ROUTE_ACCUMULATION:
if(MY_ID == BRP_next)
{
if(IERP_next == source)
{
prev_hops = route(1: current_hop_ptr-1)
next_hops = route(current_hop_ptr : |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(MY_ID == bad_link_source)
flags(1) = 1
}
if(IERP_next == dest) // Discard bordercast message if this node is not a member of
{ // prev_bcast's bordercast tree
prev_hops = route(1: current_hop_ptr) discard = !Bordercast_Tree[prev_bcast].member;
next_hops = route(current_hop_ptr+1 : |route|) // If this node is the downstream peripheral node of
// prev_bcast then terminate if this node:
// (a) has already been a bordercast recipient
// OR
// (b) is inside the routing zone of a node that has
// already bordercasted the message
if (next_hops(|next_hops|) == MY_ID) if(is_peripheral_node(prev_bcast,MY_ID))
{ {
next_hops=Interzone_Routing_Table[IERP_next]) for((EACH) queried_node (BELONGING TO)
Detected_Messages[source,message_id]
if(next_hops(|next_hops|) == IERP_next (OR) .prev_bcast)
next_hops == NULL)
{ {
next_hops = NULL a = MY_ID (BELONGS TO)
BRP_next = IERP_next Bordercast_Tree[queried_node]
} .downstream_peripheral_nodes;
else b = is_interior_node(queried_node,MY_ID);
BRP_next = next_hops(1) discard = discard || (a || b);
}
else
BRP_next = next_hops(1)
} }
// Since this node is the downstream peripheral recipient,
Haas, Pearlman Expires December 1999 [Page // it will re-bordercast the message (if it isn't
50] // terminated)
prev_bcast = MY_ID;
INTERNET DRAFT The Zone Routing Protocol June
1999
if(MY_ID == IERP_next)
{
load(packet)
deliver(packet, IERP)
} }
else out_neighbors = {};
{ if(!discard)
if(flags(1) == 1)
{ {
load(packet) // Don't relay message to a given downstream neighbor if
deliver(packet, IERP) // each covered downstream peripheral node (of prev_bcast):
} // (a) has already been a bordercast recipient
metric = {metric,get_metric(Intrazone_Routing_Table, // OR
BRP_next)} // (b) is inside the routing zone of a node that has
route = {prev_hops, MY_ID, next_hops} // already bordercast the message
current_hop_ptr = |prev_hops|+1
load(packet)
send (packet,BRP_next)
}
}
else
discard(packet)
break
case ROUTE_OPTIMIZATION: for((EACH) neighbor (BELONGING TO)
if(MY_ID == BRP_next) Bordercast_Tree[prev_bcast]
{ .downstream_neighbors)
f = NULL
for (node = {source,route,dest})
{ {
if ((EXISTS) Intrazone_Routing_Table[node]) drop_neighbor = TRUE;
f = {f,1} leaves = Bordercast_Tree[prev_bcast,neighbor
else ].downstream_peripheral_nodes;
f = {f,0} for((EACH) leaf_node (BELONGING TO) leaves)
}
if (IERP_next == source)
{ {
current_hop_ptr-- failed_leaf = TRUE;
prev_hops = route(1: current_hop_ptr-1) for((EACH) queried_node (BELONGING TO)
next_hops = route(current_hop_ptr+1 : |route|) Detected_Messages[source,message_id]
BRP_next = prev_hops(|prev_hops|) .prev_bcast)
ROF = {f,ROF}
}
if (IERP_next == dest)
{ {
current_hop_ptr++ a = leaf_node (BELONGS TO)
prev_hops = route(1: current_hop_ptr-1) Bordercast_Tree[queried_node]
next_hops = route(current_hop_ptr+1 : |route|) .downstream_peripheral_nodes;
BRP_next = next_hops(1) b = is_interior_node(queried_node,leaf_node);
ROF = {ROF,f} failed_leaf = failed_leaf || (a || b);
} }
drop_neighbor = drop_neighbor && failed_leaf;
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)
} }
else if(!drop_neighbor)
{ out_neighbors = {out_neighbors, neighbor};
load(packet)
send (packet,BRP_next)
} }
} }
else
discard(packet)
break
Haas, Pearlman Expires December 1999 [Page // Record BRP "state" in Detected Messages Cache, so that
52] // the message can be properly forwarded when returned by
// the higher layer app (IERP)
BRP_cache_ID++;
add(Detected_Messages[source,message_id],(BRP_cache_ID,
prev_bcast,out_neighbors));
schedule(remove(Detected_Messages[BRP_cache_ID],
MAX_QUERY_LIFETIME);
INTERNET DRAFT The Zone Routing Protocol June deliver(message_packet,BRP_cache_ID);
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
adapt to changes in network behavior, through dynamic configuration adapt to changes in network behavior, through dynamic configuration
of the zone radius [3]. In [4], it was shown that a node can accurately of the zone radius [3]. In [9], it was shown that a node can
estimate its optimal zone radius, on-line, based on local measurements of accurately estimate its optimal zone radius, on-line, based on local
ZRP traffic. The re-sizing of the routing zone can be carried out by a measurements of ZRP traffic. The re-sizing of the routing zone can be
protocol that conveys the change in zone radius to the members of the carried out by a protocol that conveys the change in zone radius to the
routing zone. The details of such an update protocol will be provided in members of the routing zone. The details of such an update protocol
a future version of this draft. will be provided in a future version of this draft.
5.2 Hierarchical Routing and the ZRP 5.2 Hierarchical Routing and the ZRP
In a hierarchical network architecture, network nodes are organized into In a hierarchical network architecture, network nodes are organized
a into a smaller number of (often disjoint) clusters. This routing
smaller number of (often disjoint) clusters. This routing hierarchy is hierarchy is maintained by two component routing protocols. An intra-
maintained by two component routing protocols. An intra-cluster protocol cluster protocol provides routes between nodes of the same cluster,
provides routes between nodes of the same cluster, while an inter-cluster while an inter-cluster protocol operates globally to provide routes
protocol operates globally to provide routes between clusters. between clusters.
The ZRP, with its routing zones and intrazone / interzone routing The ZRP, with its routing zones and intrazone / interzone routing
protocol protocol (IARP/IERP) architecture may give the appearance of being a
(IARP/IERP) architecture may give the appearance of being a hierarchical hierarchical routing protocol. In actuality, the ZRP is a flat routing
routing protocol. In actuality, the ZRP is a flat routing protocol. protocol. Each node maintains its own routing zone, which heavily
Each overlaps with the routing zones of neighboring nodes. Because there is
node maintains its own routing zone, which heavily overlaps with the a one-to-one correspondence between nodes and routing zones, the routing
routing zones, unlike hierarchical clusters, do not serve to hide the details of
zones of neighboring nodes. Because there is a one-to-one correspondence local network topology. As a result, the network-wide interzone routing
between nodes and routing zones, the routing zones, unlike hierarchical protocol (IERP) actually determines routes between individual nodes,
clusters, do not serve to hide the details of local network topology. rather than just between higher level network entities.
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, 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 For small to moderately sized networks, flat routing protocols, like the
ZRP, are preferable to hierarchical routing protocols. In order for ZRP, are preferable to hierarchical routing protocols. In order for
a node to be located, its address needs to reflect the node's location 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 within the network hierarchy (i.e. {cluster id,node id}). Because of
node mobility, a node's cluster membership (and thus address) is subject node mobility, a node's cluster membership (and thus address) is subject
to change. This complicates mobility management, for the benefit of more to change. This complicates mobility management, for the benefit of
efficient routing. In many hierarchical routing protocols, each cluster more efficient routing. In many hierarchical routing protocols, each
designates a single clusterhead node to relay inter-cluster traffic. cluster designates a single clusterhead node to relay inter-cluster
These traffic. These clusterhead nodes become traffic "hot-spots",
clusterhead nodes become traffic "hot-spots", potentially resulting in potentially resulting in network congestion and single point of failure.
network congestion and single point of failure. Furthermore, restricting Furthermore, restricting cluster access through clusterhead nodes can
cluster access through clusterhead nodes can lead to sub-optimal routes, lead to sub-optimal routes, as potential neighbors in different clusters
as potential neighbors in different clusters are prohibited from are prohibited from communicating directly. Some hierarchical routing
communicating directly. Some hieararchical routing protocols, such protocols, such as the Zone-Based Hierarchical Link-State (ZHLS) [4],
as the Zone-Based Hiearchical Link-State (ZHLS) [5], avoid these problems avoid these problems by distributing routing information to all cluster
by distributing routing information to all cluster nodes, rather than nodes, rather than maintaining a single clusterhead.
maintaining a single clusterhead.
In spite of these disadvantages, hierarchical routing protocols are often In spite of these disadvantages, hierarchical routing protocols are
better suited for very large networks than flat routing protocols. often better suited for very large networks than flat routing protocols.
Because hierarchical routing protocols provide global routes to network Because hierarchical routing protocols provide global routes to network
clusters, rather than individual nodes, routing table storage is more clusters, rather than individual nodes, routing table storage is more
scalable. Similarly, the amount of route update messages is also more scalable. Similarly, the amount of route update messages is also more
scalable. To some extent, the reduction in routing traffic is offset scalable. To some extent, the reduction in routing traffic is offset
by extra mobility management overhead (i.e. identifying which cluster by extra mobility management overhead (i.e. identifying which cluster
a node belongs to). However, it is quite common that the environment or a node belongs to). However, it is quite common that the environment or
existing organizational structure causes nodes to naturally cluster existing organizational structure causes nodes to naturally cluster
together. In these cases, there may be high degree of intra-cluster together. In these cases, there may be a high degree of intra-cluster
mobility, inter-cluster mobility is less common. mobility, with inter-cluster mobility is less common.
A hierarchical routing protocol can be viewed as a set of flat routing A hierarchical routing protocol can be viewed as a set of flat routing
protocols, each operating at different levels of granularity. In a two- protocols, each operating at different levels of granularity. In a two-
tier routing protocol, the inter-cluster components is essentially a tier routing protocol, the inter-cluster components is essentially a
flat routing protocol that computes routes between clusters. Likewise, flat routing protocol that computes routes between clusters. Likewise,
the intra-cluster component is a flat routing protocol, that computes the intra-cluster component is a flat routing protocol, that computes
routes routes between nodes in each cluster. For example, the Near Term
between nodes in each cluster. For example, the Near Term Digital Radio Digital Radio (NTDR) System [13] and ZHLS both employ proactive link
(NTDR) System [12] and ZHLS both employ proactive link state protocols to state protocols to determine inter and intracluster connectivity.
determine inter and intracluster connectivity.
In place of traditional proactive or reactive protocols, we recommend In place of traditional proactive or reactive protocols, we recommend
that the intra-cluster and inter-cluster routing protocol components that the intra-cluster and inter-cluster routing protocol components
be implemented based on the hybrid proactive/reactive ZRP. As described be implemented based on the hybrid proactive/reactive ZRP. As described
throughout this draft, the ZRP is designed to provide an optimal balance throughout this draft, the ZRP is designed to provide an optimal balance
between purely proactive and reactive routing. This applies equally well between purely proactive and reactive routing. This applies equally well
to routing between nodes at the intra-cluster level and between clusters to routing between nodes at the intra-cluster level and between clusters
at at the inter-cluster level. Additionally, the hybrid ZRP methodology can
the inter-cluster level. Additionally, the hybrid ZRP methodology can
be applied to the related mobility management protocols, which determine be applied to the related mobility management protocols, which determine
complete node addresses based on a node's location in the network complete node addresses based on a node's location in the network
hierarchy. hierarchy.
Haas, Pearlman Expires December 1999 [Page
54]
INTERNET DRAFT The Zone Routing Protocol June
1999
6.0 References 6.0 References
[1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable [1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable
Wireless Networks," ICUPC'97, San Diego, CA, Oct. 12,1997. Wireless Networks," ICUPC'97, San Diego, CA, Oct. 12,1997.
[2] Haas, Z.J. and Pearlman, M.R., "The Performance of Query [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.
[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.
[4] Haas, Z.J. and Pearlman, M.R., "Determining the Optimal [4] Joa-Ng, M. and Lu, I.T., "A Peer-to-Peer Zone-based Two-Level
Configuration for the Zone Routing Protocol," to appear
in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.
[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 Link State Routing for Mobile Ad-Hoc Networks," to appear
in IEEE JSAC issue on Ad-Hoc Networks, June, 1999. in IEEE JSAC issue on Ad-Hoc Networks, June, 1999.
[6] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing [5] 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.
[7] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, [6] Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD,
RFC 2178, July 1997. RFC 2178, July 1997.
[8] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient [7] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient
Routing Protocol for Wireless Networks," MONET, vol. 1, Routing Protocol for Wireless Networks," MONET, vol. 1,
no. 2, pp. 183-197, October 1996. no. 2, pp. 183-197, October 1996.
[9] Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed [8] Park, V.D., and Corson, M.S., "A Highly Adaptive Distributed
Routing Algorithm for Mobile Wireless Networks," Routing Algorithm for Mobile Wireless Networks,"
IEEE INFOCOM'97, Kobe, Japan, 1997. IEEE INFOCOM'97, Kobe, Japan, 1997.
[10] Perkins, C.E., and Bhagwat, P., "Highly Dynamic [9] Pearlman, M.R. and Haas, Z.J., "Determining the Optimal
Configuration for the Zone Routing Protocol," IEEE JSAC,
August, 1999.
[10] Pearlman, M.R. and Haas, Z.J., "Improving the Performance of
of Query-Based Routing Protocols Through 'Diversity
Injection'", IEEE WCNC'99, New Orleans, LA, Sept. 1999.
[11] 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.
[11] Perkins, C.E. and Royer, E.M., "Ad-Hoc On-Demand Distance [12] Perkins, C.E. and Royer, E.M., "Ad-Hoc On-Demand Distance
Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999 Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999
[12] Ruppe, R., Griswald, S., Walsh, P. and Martin, R., "Near Term [13] Ruppe, R., Griswald, S., Walsh, P. and Martin, R., "Near Term
Digital Radio (NTDR) System," IEEE MILCOM'97, Monterey, CA, Digital Radio (NTDR) System," IEEE MILCOM'97, Monterey, CA,
Nov. 1997. Nov. 1997.
[13] Waitzman, D., Partridge, C., Deering, S.E., "Distance [14] 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.
Haas, Pearlman Expires December 1999 [Page 7.0 Draft Updates
55]
INTERNET DRAFT The Zone Routing Protocol June - The sole function of the Bordercast Resolution Protocol (BRP) is
1999 to perform application independent bordercasting (all excess
routing protocol functionality has been moved up to the IERP).
This means that the BRP can be used outside of the ZRP, for any
application that requires an efficient network-wide query/probing
mechanism. Likewise, a wide variety of globally reactive routing
protocols may be adopted as alternate IERPs, by substituting the
query "broadcast()" with "bordercast()".
In further support of application independent bordercasting, the BRP
can deliver messages up to the higher layer application at every hop
(as opposed to only delivering for peripheral nodes). This is
important for applications that wish to use the bordercast service,
but are otherwise "routing zone unaware".
- The bordercast message delivery service is now implemented via
multicasting, rather than a series of separate unicasts to individual
peripheral nodes. The bordercast control mechanisms have been revised
to support this transition.
- The IARP is now required to proactively track the COMPLETE topology of
an EXTENDED routing zone, consisting of all nodes that are at a
minimum distance (in hops) LESS THAN twice the "basic" routing zone
radius. Nodes use this extended information to construct the
downstream portion of each routing zone node's bordercast (multicast)
tree. Consequently, the Distance Vector IARP implementation has been
dropped.
- For convenience, the IARP and IERP now share a single routing table.
IARP entries are indicated by a special flag.
- The IERP's optional Route Accumulation and Route Optimization stages
have been dropped.
- The route maintenance policy has been simplified. Local route
repairs are only reported to the source of the broken link, not to
the route's source.
- Support for "diversity injection" [10] has been added to the IERP.
The diversity injection mechanism allows the global route discovery
to extract more information about current network connectivity,
without any additional traffic.
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
skipping to change at line 3346 skipping to change at line 2141
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/