draft-ietf-manet-zone-zrp-00.txt   draft-ietf-manet-zone-zrp-01.txt 
INTERNET-DRAFT Zygmunt J. Haas, Cornell University INTERNET-DRAFT Zygmunt J. Haas, Cornell University
Marc R. Pearlman, Cornell University Marc R. Pearlman, Cornell University
Expires in six months November 1997 Expires in six months August 1998
The Zone Routing Protocol (ZRP) for Ad Hoc Networks The Zone Routing Protocol (ZRP) for Ad Hoc Networks
<draft-zone-routing-protocol-00.txt> <draft-ietf-manet-zone-zrp-01.txt>
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its documents of the Internet Engineering Task Force (IETF), its areas,
areas, and its working groups. Note that other groups may also and its working groups. Note that other groups may also distribute
distribute working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six months
months and may be updated, replaced, or obsoleted by other and may be updated, replaced, or obsoleted by other documents at any
documents at any time. It is inappropriate to use Internet- time. It is inappropriate to use Internet-Drafts as reference
Drafts as reference material or to cite them other than as material or to cite them other than as ``work in progress.''
``work in progress.''
To view the entire list of current Internet-Drafts, please check To view the entire list of current Internet-Drafts, please check the
the "1id-abstracts.txt" listing contained in the Internet-Drafts "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
(Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
Coast), or ftp.isi.edu (US West Coast). ftp.isi.edu (US West Coast).
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
Abstract Abstract
This document describes a routing protocol for ad hoc networks. This document describes the Zone Routing Protocol (ZRP), a hybrid
In particular, it is suitable for highly versatile networks, routing protocol suitable for a wide variety of mobile ad-hoc
characterized by large range of nodal mobilities and large network networks, especially those with large network spans and diverse
diameters. The protocol is a hybrid of a proactive and a reactive mobility patterns. Each node proactively maintains routes within a
schemes, allowing adjustment of its operation to the current local region (referred to as the routing zone). Knowledge of the
network operational conditions. routing zone topology is leveraged by the ZRP to improve the
efficiency of a reactive route query/reply mechanism. The proactive
maintenance of routing zones also helps improve the quality of
discovered routes, by making them more robust to changes in network
topology. The ZRP can be configured for a particular network by
proper selection of a single parameter, the routing zone radius.
This version of the ZRP internet draft describes a number of
features which have been added to the protocol. The distance-vector
based IARP algorithm has been enchanced to prevent the 'counting
to infinity problem'. Route caching is now supported by the IERP
route discovery process. By allowing discovered route information
to be distributed in caches, route accumulation in the IERP query/
reply packets can be avoided, thereby reducing the amount of
route discovery traffic, and improving the query response time.
Two additional (optional) stages have also been added to the route
discovery process, to support the acquisition and optimization of
source routes.
Contents
Status of this Memo . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . i
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2
2. Overview of the Zone Routing Protocol . . . . . . . . . . . 3
2.1 The Notion of a Routing Zone and
the Intrazone Routing Protocol (IARP) . . . . . . . 3
2.2 The Interzone Routing Protocol (IERP) . . . . . . . . 4
2.2.1 Routing Zone Based Route Discovery . . . . . . 4
2.2.2 Route Accumulation Procedure . . . . . . . . . 5
2.2.3 Query Control Mechanisms . . . . . . . . . . . 6
2.2.4 Route Maintenance . . . . . . . . . . . . . . . 7
3. The ZRP Architecture . . . . . . . . . . . . . . . . . . . 8
4. Implementation Details . . . . . . . . . . . . . . . . . . 9
4.1 Intrazone Routing Protocol (IARP) . . . . . . . . . . 9
A. Packet Format . . . . . . . . . . . . . . . . . . 9
B. Structures . . . . . . . . . . . . . . . . . . . . 10
C. Interfaces . . . . . . . . . . . . . . . . . . . . 10
D. State Machine . . . . . . . . . . . . . . . . . . 11
E. Pseudocode Implementation . . . . . . . . . . . . 13
4.2 Interzone Routing Protocol (IERP) . . . . . . . . . . 14
A. Packet Format . . . . . . . . . . . . . . . . . . 16
B. Structures . . . . . . . . . . . . . . . . . . . . 18
C. Interfaces . . . . . . . . . . . . . . . . . . . . 19
D. State Machine . . . . . . . . . . . . . . . . . . 19
E. Pseudocode Implementation . . . . . . . . . . . . 22
4.3 Bordercasting Resolution Protocol (BRP) . . . . . . . 25
A. Packet Format . . . . . . . . . . . . . . . . . . 26
B. Structures . . . . . . . . . . . . . . . . . . . . 26
C. Interfaces . . . . . . . . . . . . . . . . . . . . 26
D. State Machine . . . . . . . . . . . . . . . . . . 26
E. Pseudocode Implementations . . . . . . . . . . . . 31
5. Other Considerations . . . . . . . . . . . . . . . . . . . 37
5.1 Sizing the Routing Zone . . . . . . . . . . . . . . . 37
6. References . . . . . . . . . . . . . . . . . . . . . . . . 38
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, at least the reachability information of the source a packet route, a node needs to known at least the reachability
neighbors needs to be known to the source node. On the other hand, information to its neighbors. On the other hand, in an ad hoc
in an ad hoc network, the network topology can change quite often. network, the network topology can change quite often. Furthermore,
Furthermore, as the number of network nodes can be large, the as the number of network nodes can be large, the potential number of
potential number of destinations is also large, requiring large and destinations is also large, requiring large and frequent exchange of
frequent exchange of data (e.g., routes, routes updates, or routing data (e.g., routes, routes updates, or routing tables) among the
tables) among the network nodes. Thus, the amount of update traffic network nodes. Thus, the amount of update traffic can be quite high.
can be quite high. This is in contradiction with the fact that all This is in contradiction with the fact that all updates in a
updates in a wirelessly interconnected ad hoc network travel over wirelessly interconnected ad hoc network travel over the air and,
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. Reactive protocols, on the other
hand, invoke a route determination procedure on demand only. Thus, hand, invoke a route determination procedure on demand only. Thus,
when a route is needed, some sort of global search procedure is when a route is needed, some sort of global search procedure is
employed. The family of classical flooding algorithms belong to the employed. The family of classical flooding algorithms belong to the
reactive group. Some examples of reactive (also called on-demand) reactive group. Some examples of reactive (also called on-demand)
ad hoc network routing protocols are [Johnson] and [TORA]. ad hoc network routing protocols are [Johnson], [AODV], [TORA]
(see also [Park]).
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 search procedure can be quite significant. Furthermore, the global flood-search
of the reactive protocols requires significant control traffic. procedure of the reactive protocols requires significant control
Because of this long delay and excessive control traffic, pure traffic. Because of this long delay and excessive control traffic,
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 again in an excessive waste of the wireless network results in a further waste of the wireless network capacity. What is
capacity. What is needed is a protocol that, on one hand, initiates needed is a protocol that, on one hand, initiates the route-
the route-determination procedure on-demand, but at limited search determination procedure on-demand, but at limited search cost. The
cost. The presented-here protocol, termed the "Zone Routing Protocol protocol described in this draft, termed the "Zone Routing Protocol
(ZRP)," is an example of a hybrid reactive/proactive routing (ZRP)" ([Haas-1], [Haas-2]), is an example of a such a hybrid
protocol. proactive/reactive scheme.
The ZRP, on one hand, limits the scope of the proactive procedure The ZRP, on one hand, limits the scope of the proactive procedure
only to the node's local neighborhood. On the other hand, the search only to the node's local neighborhood. On the other hand, the search
throughout the network, although global in nature, is done by throughout the network, although global in nature, is done by
efficiently querying selected nodes in the network, as opposed to efficiently querying selected nodes in the network, as opposed to
querying all the network nodes. querying all the network nodes.
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
have to have local effect only. In other words, creation of a new should have only a local effect. In other words, creation of a new
link at one end of the network is an important local event but, most link at one end of the network is an important local event but, most
probably, not a significant piece of information at the other end of probably, not a significant piece of information at the other end of
the network. Proactive protocols tend to distribute such topological the network. Proactive protocols tend to distribute such topological
changes widely in the network, incurring large costs. The ZRP limits changes widely in the network, incurring large costs. The ZRP limits
propagation of such information to the neighborhood of the change propagation of such information to the neighborhood of the change
only, thus limiting the cost of topological updates. only, thus limiting the cost of topological updates.
2.0 The Notion of Routing Zone, Zone Radius, and Bordercasting 2. Overview of the Zone Routing Protocol
A routing zone is defined for each node and includes the nodes whose 2.1 The Notion of a Routing Zone and the Intrazone Routing Protocol
minimum distance in *hops* from the node in question is at most some (IARP)
predefined number, which is referred to as the Zone Radius. An
example of a routing zone (for node A) of radius 2 is shown below. A routing zone is defined for each node X, and includes the nodes
whose minimum distance in *hops* from X is at most some predefined
number, which is referred to as the Zone Radius. An example of a
routing zone (for node A) of radius 2 is shown below.
+-----------------------------------------+ +-----------------------------------------+
| +---+ | | +---+ |
| +---+ | F | | | +---+ ---| F |-------| |
+---+ | +---+ ----| C |------+---+-----+---+ | +---+ | +---+ --| C |--/ +---+ +---+ |
| G |-----| D | +---+ | E | | Zone of node A | G |-----| D |--/ +---+ | E | | Zone of node A
+---+ | +---+ | +---+-----+---+ | of radius=2 +---+ | +---+ | +---+ +---+ | of radius=2
| +---+------| B | | | +---+ ---| B |-------| |
| | A | +---+ | | | A |--/ +---+ |
| +---+ | | +---+ |
+-----------------------------------------+ +-----------------------------------------+
Note that in this example nodes B through E are within the routing Note that in this example nodes B through E are within the routing
zone of A. Node G is outside A's routing zone. Also note that E can zone of A. Node G is outside A's routing zone. Also note that E can
be reached by two path from A, one with length 2 hops and one with be reached by two paths from A, one with length 2 hops and one with
length 3 hope. Since the minimum is less or equal than 2, E is within length 3 hope. 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.
Bordercasting is a process of sending an IP datagram ([RFC-0791]) by An important consequence of the routing zone construction is the
a node to all its peripheral nodes. Bordercasting can be implemented ability of a node to deliver a packet to its peripheral nodes.
either through regular IP unicast or through IP multicast (Distance This service, which we refer to as bordercasting, allows for more
Vector Multicast Routing Protocol [RFC-1075]). Of course, the efficient network-wide searching than simple neighbor broadcasting.
multicasting approach is preferred to reduce the amount of traffic Bordercasting could be implemented either through a series of IP
over the air. unicasts or an IP multicast (Distance Vector Multicast Routing
Protocol [RFC-1075])) to the peripheral nodes. (In cases where
2.1 The Zone Routing Protocol (ZRP) ([Haas-1],[Haas-2]) multicasting is supported, the multicasting approach is preferred
to reduce the amount of traffic over the air.) However, as will be
explained later, efficient ZRP operation requires that these unicast
or multicast services be provided by the ZRP, with IP providing best-
effort delivery to the specified ZRP next hops.
The ZRP is based on two procedures: the IntrAzone Routing Protocol The ZRP supports the proactive maintenance of routing zones
(IARP) and the IntErzone Routing Protocol (IERP). Through the use through its proactive Intrazone Routing Protocol (IARP). Through
of the IARP, each node learns the identity of and the (minimal) the IARP, each node learns the identity of and the (minimal)
distance to all the nodes in its routing zone. The actual IARP is distance to all the nodes in its routing zone. The IARP may be
not specified and can include any number of protocols, such as the derived from a wide range of proactive protocols, such as
derivatives of Distance Vector Protocol (e.g., Ad Hoc On-Demand Distance Vector (e.g., [Murthy], [DSDV]) or Shortest Path First
Distance Vector [AODV], Shortest Path First (e.g., OSPF (e.g., OSPF [RFC-2178]). Whatever the choice of IARP is, the base
[RFC-2178]), [Murthy]). In fact, different portions of an ad hoc protocol needs to be modified to ensure that the scope of this
network may choose to operate based on different choice of the IARP operation is restricted to the radius of a node's routing zone.
protocol. Whatever the choice of IARP is, the protocol needs to be
modify to ensure that the scope of this operation is restricted to
the zone of the node in question.
Note that as each node needs to learn the distances to the nodes Because each node needs to proactively acquire route information
within its zone only, the nodes are updated about topological only for the nodes within its zone, the total amount of IARP traffic
changes only within their routing zone. Consequently, in spite of does not depend on the size of the network, which may be quite large
the fact that a network can be quite large, the updates are only
locally propagated.
2.2 The Interzone Routing Protocol (IERP) 2.2 The Interzone Routing Protocol (IERP)
While IARP finds routes within a zone, IERP is responsible for While the IARP maintains routes within a zone, the IERP* is
finding routes between nodes located at distances larger than the responsible for finding routes between nodes located at distances
zone radius. IERP relies on bordercasting. Bordercasting is possible larger than the zone radius. The IERP is distinguished from standard
as any node knows the identity and the distance to all the nodes in flood-search query/response protocols by exploiting the routing zone
its routing zone by the virtue of the IARP protocol. topology. A node is able to respond positively to any queries for
its routing zone nodes. For large networks, relatively few
destinations lie within any particular node's routing zone. In this
more likely case, the node can efficiently continue the propagation
of the query, through the routing zone-based bordercast delivery
mechanism.
2.2.1 Routing Zone Based Route Discovery
The IERP operates as follows: The source node first checks whether The IERP operates as follows: The source node first checks whether
the destination is within its routing zone. (Again, this is possible 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 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 destination is known and no further route discovery processing is
required. If, on the other hand, the destination is not within the required. If, on the other hand, the destination is not within the
source's routing zone, the source bordercasts a route request source's routing zone, the source bordercasts a route query to all of
(referred to here as a "request") to all its peripheral nodes. Now, its peripheral nodes. Now, in turn, all the peripheral nodes execute
in turn, all the peripheral nodes execute the same algorithm: check the same algorithm: check whether the destination is within their
whether the destination is within their zone. If so, a route reply zone. If so, a route reply is sent back to the source indicating the
(referred to here as a "reply") is sent back to the source route to the destination. If not, the peripheral node forwards the
indicating the route to the destination. If not, the peripheral node query to its peripheral nodes, which, in turn, executes the same
forwards the query to its peripheral nodes, which, in turn, execute procedure. An example of this Route Discovery procedure is
the same procedure. An example of this Route Discovery procedure is demonstrated in the figure below.
demonstrated in the figure below. As we be shown, Thus, a route
within a network is specified as a sequence of nodes, separated by
approximately the zone radius.
+---+ +---+
+---+ | 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 node L. Assume routing zone radius of The node A has a datagram to send to node L. Assume a uniform
2. Since L is not in A's routing zone (which includes B,C,D,E,F,G), routing zone radius of 2 hops. Since L is not in A's routing zone
A bordercast a routing request to its peripheral nodes: D,F,E, and (which includes B,C,D,E,F,G), A bordercasts a routing query to its
G. Each one of these peripheral nodes check whether L exists in their peripheral nodes: D,F,E, and G. Each one of these peripheral nodes
routing zones. Since L is not found in any routing zones of these check whether L exists in their routing zones. Since L is not found
nodes, the nodes bordercast the request to their peripheral nodes. in any routing zones of these nodes, the nodes bordercast the request
In particular, G bordercasts to K, which realizes that L is in its to their peripheral nodes. In particular, G bordercasts to K, which
routing zone and returns the requested route (L-K-G-A) to the query realizes that L is in its routing zone and returns the requested
source, namely A. route (L-K-G-A) to the query source, namely A.
2.3 Route Accumulation procedure * Some functions of the IERP, including bordercasting, route
accumulation, and query control (see later), are performed by a
special component of the IERP called the Bordercast Resolution
Protocol (BRP). Sections 3.0 and 4.0 describe, in detail, the
relationship between the BRP and the IERP proper.
The process by which the node receiving a query knows the path back 2.2.2 Route Accumulation Procedure
to the source of the query is the Route Accumulation procedure. In
particular, the Route Accumulation procedure is used to return the
route to the source of the query by the "last peripheral node" in
which routing zone the destination resides. The Route Accumulation
procedure is based on each node that forwards a query writing into
the query packet its identification. The sequence of these
identifications represents a path from the source node to the
current node, and, by reversing the order, a path from the current
node to the source node.
2.4 Terminating the IERP flood The query propagation mechanism allows a route query to indirectly
reach the desired destination (through some node Y, which discovers
the destination in its routing zone.) To complete the route
discovery process, Y needs to send a reply back to the query's
source, S, providing S with the desired route. To perform the route
reply, sufficient information needs to be accumulated during the
query phase so that Y is provided with a route back to S. Providing
routes from discovering node Y to query source S, and from the query
source S back to the query destination D (through Y), is the role of
the Route Accumulation procedure.
It is desirable for route requests to propagate away from the source In the basic Route Accumulation, a node appends its IP address to a
and not to loop-back into a previously queried routing zone. To received query packet. The sequence of IP addresses specifies a
encourage this directed spread of route requests, IERP employs two route from the query's source to the current node. By reversing this
loop-back prevention mechanisms. The first mechansim terminates sequence, a route may also be obtained back to the source. In this
threads which loop-back on themselves. Such threads are terminated way, Y may send a reply back to S, through strict source routing.
when the accumulated route (excluding the previous hop) contains a
host which lies within its routing zone. A separate mechanism, based
on packet eavesdropping, is employed to reduce the overlapping of
parallel threads. When a host receives a route request, the IERP
records the request ID in its Processed Request List.* If a node
"officially" receives a request that has been previously recorded,
the new copy is discarded. Without these measures, the bordercast
transmission can actually generate more overhead than flooding.
* ICMP provides a service similar to IERP's route failure Given sufficient storage space, a queried node may cache routing
notification. However, the IERP service provides additional information accumulated in the query packet, allowing the information
diagnostic information, allowing the source to respond to the to be remove from the packet. This has the benefit of reducing the
route failure more effectively. length of the query packet, thereby decreasing the query traffic and
query response time. The IP addresses that remain in the packet can
be used to form a loose source route back to the query's source (If
ALL nodes have cached the accumulated route information, then this
effectively becomes next hop routing. If no nodes have cached
accumulated route information, then this defaults to the basic case
previously discussed). The same caching strategy can be applied to
the reply packet on its way back to the source. In this case, a
loose source route to the destination is formed.
2.5 Route failures notifications 2.2.3 Query Control Mechanisms
The IERP also provides a mechanism to reactively respond to route Bordercasting has the potential to support global querying schemes
failures. A route failure is detected by the IP when the next hop in that are more efficient than flooding. To achieve this efficiency,
a source route is determined to be unreachable (i.e., does not the protocol should be able to detect and terminate a query thread
appear in the Intrazone Routing Table). Upon detection of a route when it appears in a previously queried region of the network (i.e.
failure, the IERP is alerted, and a route failure packet is arrives at a node belonging to the routing zone of a previously
generated.** The route failure packet propagates back to the route's queried node). This detection / termination capability is
source in the same manner as a route reply. When the route's source significantly limited when bordercasting is implemented directly
receives notification of the route failure, the expired route is through IP unicast or IP multicast.
removed from its Interzone Routing Table. The IERP may also be
configured to locally repair the damaged Interzone route by
initiating a route discovery to the unreachable next hop.
** Eavesdropping nodes are only permitted to listen to route requests By implementing bordercasting within the ZRP, the nodes that relay
(and record them in their Processed Request List); they are the query to the peripheral node are able to detect the passing
prohibited from processing the request any further. 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.
2.6 Bordercast Resolution Protocol (BRP) 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.
The Bordercast Resolution Protocol (BRP) is included with the IERP in 2.2.4 Route Maintenance
order to provide bordercasting services which do not exist in IP. In
the current version of the BRP, the content of a bordercast message
is considered to be accessible to any host which receives the
message.*** Future versions of the BRP may allow for semi-private
bordercasting, where bordercast messages are only delivered to the
higher layers of the bordercast destinations (peripheral nodes).
*** When the BRP delivers the message to the next higher layer, a In addition to initially discovering routes, the IERP may also assume
flag is set to indicate whether the packet was overheard or responsibility for monitoring the integrity of these routes and
received at its intended destination. Note that this does not repairing failed routes as appropriate.
restrict access to the message; it only serves to provide the
access control status of the message. Route failures can be detected either proactively or reactively.
Proactive route failure detection is triggered by the IARP, in
response to a node leaving the routing zone. Any IERP routes
containing this node as the first hop can be considered invalid.
Route failures may also be detected reactively, by IP, when the next
hop in a datagram's source route is determined to be unreachable
(i.e. does not appear in the (Intrazone) Routing Table).
Upon detection of a route failure, a node may choose to notify
the route's source of the failure and / or attempt to repair the
route. A route failure notification consists of a transmission
back to the query source, indicating that the source route has
failed, and possibly the hop at which it failed. This type of
service is provided by protocols like ICMP. The node that detects
the route failure may also try to repair the failed connection by
discovering a route to bypass the failed connection. The repair
discovery process is nearly identical to an initial route discovery.
Route repairs should not be substantially longer than the original
failed connection. Thus, the depth of a repair query can be limited,
through the use of hop counter. This has the advantage of producing
much less query traffic than an unrestricted initial route query.
After a successful repair, the route's source MAY be notified so that
routes are properly selected for use. Alternatively, the repair
could go unreported without compromising the connectivity between
source and destination.
3.0 The ZRP Architecture 3.0 The ZRP Architecture
......................................... .........................................
: ZRP : : ZRP :
: : : :
+---------+ : +---------+ +---------+ : +---------+ +---------+ : +---------+ +---------+ : +---------+
| NDM |~~~~:~~~>| IARP |~~~~~~~~>| IERP |<~~~:~~~~| ICMP | | NDM |========>| IARP |========>| IERP |<========| ICMP |
+---------+ : +---------+ +---------+ : +---------+ +---------+ : +---------+ |.........| : +---------+
/|\ : /|\ | BRP | : /|\ /|\ : /|\ | BRP | : /|\
---------+ : +---------+ <span class="insert">|.........|</span> : +---------+
| : | +---------+ : | | : | +---------+ : |
| : | /|\ : | | : | /|\ : |
| :.......................................: | | :.........|...................|.........: |
| | | | | | | |
\|/ \|/ \|/ \|/ \|/ \|/ \|/ \|/
+---------+---------+---------+---------+---------+---------+---------+ +---------+---------+---------+---------+---------+---------+---------+
| 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 the neighbor discovery operation can be 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.
4.0 Implementation Details 4. Implementation Details
4.1 The IntrAzone Routing Protocol (IARP) 4.1 The IntrAzone Routing Protocol (IARP)
Although the IARP can be implemented through various proactive The IARP can be implemented through various proactive protocols. We
protocols, we present here an example of an implementation based present here an implementation based on a modified version of the
on a modified version of the Distance Vector algorithm that restricts Distance Vector algorithm. Routing information to a node is limited
the of the algorithm's operation to the range of the routing zone to the the routing zone of that node. In this version, routing
radius. information consists of the route cost and the IP addresses of the
route destination and next two hops to the destination. The second hop
is included to identify routes where a node is it's own second hop.
This particular looping condition can result in the "counting to
infinity" problem. By deleting these routes, this problem can be
avoided, allowing the IARP to converge faster.
A terminal may receive new route information either from a received A node may receive new route information either from a received IARP
IARP packet or from an interrupt generated by its Neighbor Discovery packet or from an interrupt generated by its Neighbor Discovery /
/ Maintenance (NDM) process$. In the special case when a host has Maintenance (NDM) proces*. In the special case when a host has
discovered a neighoor, the IARP is responsible for sending the new discovered a neighor, the IARP is responsible for sending to the new
neighbor the shortest route to each host which is common to both of neighbor the shortest route to each host which is common to both of
their routing zones. The terminal then records the new route their routing zones (i.e. each host with a hop count less than it's
information in its Intrazone Routing Table. If the shortest path to routing zone radius). The node then records the new route information
the host has changed, the terminal broadcasts an IARP packet in its Intrazone Routing Table. If the shortest path to the host has
reflecting the change. changed, the terminal broadcasts an IARP packet reflecting the
change.
$ IARP relies on the services of a separate protocol (referred to * IARP relies on the services of a separate protocol (referred to
here as the Neighbor Discovery/Maintenance Protocol) to provide here as the Neighbor Discovery/Maintenance Protocol) to provide
current information about a host's neighbors. At the least, this current information about a host's neighbors. At the least, this
information must include the IP addresses of all the neighbors. information must include the IP addresses of all the neighbors.
The IARP can be readily configured to support supplemental The IARP can be readily configured to support supplemental
neighbor information, such as link cost. neighbor information, such as link cost.
A. Packet Format A. Packet Format
1 2 3 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address | | Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop Address | | Next Hop #1 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop #2 Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Hop Cnt| |Hop Cnt|
+-+-+-+-+ +-+-+-+-+
Field Description: Field Description:
* Destination Address (32 bits) * Destination Address (32 bits)
IP address of the destination host IP address of the destination host
* Next Hop Address (32 bits) * Next Hop # 1 Address (32 bits)
IP address of the "next hop" host to the destination host IP address of the "next hop" host to the destination host
* Next Hop # 2 Address (32 bits)
IP address of the Next Hop #1 's "next hop" host to
the destination host
* Hop Count (4 bits) * Hop Count (4 bits)
Length of the route to the destination host, measured in hops Length of the route to the destination host, measured
in hops
B. Structures B. Structures
B.1 Intrazone Routing Table B.1 Intrazone Routing Table
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Routes | | | Routes |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Host | 0 | 1 | ==> | M-1 | | Host | 0 | 1 | ==> | M-1 |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 8, line 45 skipping to change at page 10, line 50
C.1.1 Send() (specified in IP standard) C.1.1 Send() (specified in IP standard)
C.1.2 Deliver() (specified in IP standard) C.1.2 Deliver() (specified in IP standard)
C.3 NDM C.3 NDM
C.3.1 Neighbor_Lost(host) C.3.1 Neighbor_Lost(host)
Used by the NDM to notify the IARP that direct contact Used by the NDM to notify the IARP that direct contact
has been lost with "host". has been lost with "host".
C.3.2 Neighbor_Found(host) C.3.2 Neighbor_Found(host)
Used by the NDM to notify the IARP that direct contact Used by the NDM to notify the IARP that direct contact
has been confirmed with "host". has been confirmed with "host".
C.4 IERP C.4 IERP
C.4.1 Host_Lost(host) C.4.1 Zone_Node_Lost(host)
Used by IARP to notify the IERP that a host 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 host running this state
machine. machine.
2) INF is a reserved field value corresponding to 2) INF is a reserved field value corresponding to
"infinity". "infinity".
D.1 D.1
Event: An IARP packet is received containing route Event: An IARP packet is received containing route
information to a destination D. The hop count information to a destination D. The hop count
associated with the received route is LESS THAN associated with the received route is LESS THAN
the routing zone radius. 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 Action: The received route is recorded in the Intrazone
Routing Table. If the received route is shorter Routing Table. If the received route is shorter
than the previous shortest route to D, then a new than the previous shortest route to D, then a new
IARP packet containing route information to D IARP packet containing route information to D
through X is broadcasted. through X is broadcasted.
D.2 D.3
Event: An IARP packet is received containing route Event: An IARP packet is received containing route
information to a destination D. The hop count is information to a destination D. The hop count is
EQUAL TO the routing zone radius. EQUAL TO the routing zone radius. The second
next-hop is NOT EQUAL to X.
Action: The received route is recorded in the Intrazone Action: The received route is recorded in the Intrazone
Routing Table. Routing Table.
D.3 D.4
Event: An IARP packet is received containing route Event: An IARP packet is received containing route
information to a destination D. The hop count is information to a destination D. The hop count is
equal to INF. equal to INF.
Action: The route to D is removed from the Intrazone Action: The route to D is removed from the Intrazone
Routing Table. Routing Table.
1) If the Intrazone Routing Table still 1) If the Intrazone Routing Table still
contains a route to D and the length of the contains a route to D and the length of the
shortest route has increased due to the route shortest route has increased due to the route
removal, then the an IARP packet containing the removal, then the an IARP packet containing the
shortest route to D through X is broadcasted. shortest route to D through X is broadcasted.
2) If the Intrazone Routing Table contains no 2) If the Intrazone Routing Table contains no
more routes to D, then an IARP packet containing more routes to D, then an IARP packet containing
a route to D through X with hop count of INF is a route to D through X with hop count of INF is
broadcast. A "Host Lost" interrupt is broadcast. A "Host Lost" interrupt is
generated to alert the IERP that D has moved generated to alert the IERP that D has moved
beyond the routing zone. beyond the routing zone.
D.4 D.5
Event: A "Neighbor Found" interrupt is received, Event: A "Neighbor Found" interrupt is received,
indicating the discovery of a neighbor host N. indicating the discovery of a neighbor host N.
Action: For each destination in X's Intrazone Routing Action: For each destination in X's Intrazone Routing
Table, an IARP packet is sent to N containing the Table, an IARP packet is sent to N containing the
best route to that destination. An IARP packet is best route to that destination. An IARP packet is
then broadcasted containing the 1 hop route to N then broadcasted containing the 1 hop route to N
through X. through X.
D.5 D.6
Event: A "Neighbor Lost" interrupt is received, indicating Event: A "Neighbor Lost" interrupt is received, indicating
that host N is no longer a neighbor of X that host N is no longer a neighbor of X
Action: The one hop route to N is removed from the Action: The one hop route to N is removed from the
Intrazone Routing Table. Intrazone Routing Table.
1) If the Intrazone Routing Table still 1) If the Intrazone Routing Table still
contains a route to N and the length of the contains a route to N and the length of the
shortest route has increased due to the route shortest route has increased due to the route
removal, then the an IARP packet containing the removal, then the an IARP packet containing the
shortest route to N through X is broadcasted. shortest route to N through X is broadcasted.
skipping to change at page 10, line 28 skipping to change at page 13, line 10
a route to D through X with hop count of INF is a route to D through X with hop count of INF is
broadcast. A "Host Lost" interrupt is generated broadcast. A "Host Lost" interrupt is generated
to alert the IERP that D has moved beyond the to alert the IERP that D has moved beyond the
routing zone. routing zone.
E. Pseudocode Implementation E. Pseudocode Implementation
E.1 Update Intrazone Routing Table E.1 Update Intrazone Routing Table
if (packet arrived) if (packet arrived)
{host, route->next_hop,route->hop_count} <-- packet {host, route->next_hop, next_next_hop, route->hop_count}
<-- packet
else else
{ {
{host} <-- intrpt {host} <-- intrpt
route->next_hop=host route->next_hop=host
if (type(intrpt) == "Neighbor Found") if (type(intrpt) == "Neighbor Found")
{ {
for recorded_host = each host in Intrazone_Routing_Table for dest = each host in Intrazone_Routing_Table
{ {
best_route = Intrazone_Routing_Table[recorded_host,0] best_route = Intrazone_Routing_Table[dest,0]
if (best_route->hop_count < ROUTING_ZONE_RADIUS) if (best_route->hop_count < ROUTING_ZONE_RADIUS)
{ {
packet <-- {recorded_host,my_id,hop_count+1} packet <--{dest,my_id,best_route->next_hop,
best_route->hop_count+1}
send(packet,host) send(packet,host)
} }
} }
route->hop_count=1 route->hop_count=1
} }
else else
route->hop_count=INF route->hop_count=INF
} }
former_best_route = Intrazone_Routing_Table[host,0] former_best_route = Intrazone_Routing_Table[host,0]
if (route->hop_count < INF) if (route->hop_count < INF)
if(route->next_next_hop != my_id
add(Intrazone_Routing_Table[host], route) add(Intrazone_Routing_Table[host], route)
else else
remove(Intrazone_Routing_Table[host],route) remove(Intrazone_Routing_Table[host],route)
best_route = Intrazone_Routing_Table[host,0] best_route = Intrazone_Routing_Table[host,0]
if (best_route != NULL) if (best_route != NULL)
{ {
if (best_route->hop_count != former_best_route->hop_count if (best_route->hop_count != former_best_route->hop_count
&& best_route->hop_count < ROUTING_ZONE_RADIUS) && best_route->hop_count < ROUTING_ZONE_RADIUS)
{ {
packet <-- {host, my_id, best_route->hop_count+1} packet <-- {host, my_id, best_route->next_hop,
best_route->hop_count+1}
broadcast(packet) broadcast(packet)
} }
} }
else else
{ {
force_intrpt("IERP","Host Lost",{host}) force_intrpt("IERP","Zone Node Lost",{host})
packet <-- {host, my_id, INF} packet <-- {host, my_id, my_id, INF}
broadcast(packet) broadcast(packet)
} }
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
routes to hosts which are beyond a terminal's routing zone. The IERP and maintaining routes to hosts which are beyond a node's routing
collects routing information reactively, through bordercasted queries zone. The IERP acquires routing information reactively, exploiting
which contain the accumulated routes from the source. the knowledge of the routing zone topology through the bordercasting
delivery service.
When IP receives a data packet intended for an unknown destination This version of the IERP extends the basic query / reply mechanism
(i.e., destination is not recorded in either the Intrazone or described in Section 3. In the basic protocol, queries are
Interzone Routing Tables), the IERP is interrupted. The IERP responds terminated before reaching the query destination. This provides
by initiating a route discovery and bordercasting a route query. Each a faster response to the route query than if the destination, D,
query in the network is uniquely identified by the IP address of the were to respond directly. However, because D never receives the
source and a request ID (local to the source). query, it does not acquire a route back to the source, S. If the
D needs to send data back to S (which is often the case, given the
bi-directional nature of many applications), a separate route query
from D to S would have to be initiated. This substantial overhead
is avoided by having the query forwarded to D, by the node Y that
discovers D in its routing zone. We refer to this as a QUERY
EXTENSION.
Upon receipt of a route request packet, a host searches its Intrazone Both the source and destination can acquire routes to each other
Routing Table to determine if the requested destination is within its through the BRP route accumulation mechanisms (to be discussed
routing zone. If so, the terminal responds with a route reply which later). Distributing route information in the caches of the
is returned to the source along the (reversed) accumulated route. If route's nodes can significantly reduce the size of the IERP packets
the destination is not within the terminal's routing zone, the and provide for a faster query response. On the other hand, QOS
terminal adds its terminal ID to the accumulated route and requirements for a particular application may favor a source
bordercasts the route request. specified route. (rather than a distributed next-hop approach).
Source routing requires that the discovered route information be
accumulated in the IERP packets, rather than cached. This IERP
implementation satisfies the demands for rapid query response
and source routing support by two stages of route reporting. In the
first two stages, route information is cached by the route's nodes
(when possible). Next-hop route are quickly returned to the source
in QUERY-REPLY packets and forwarded to the destination in QUERY-
EXTENSION packets. At this point, bi-directional connectivity is
established. In the third stage, the source and destination can
provide each other with complete source routes, by sending each
other ROUTE-ACCUMULATION packets. As these packets traverse the
route, the cached route information is accumulated in the packets,
thereby constructing the desired source route.
Variations on this IERP implementation can be realized by combining
or eliminating some of these stages. For example, if source routing
is not desired, the ROUTE-ACCUMULATION stage can be eliminated.
Also, if all of the route's nodes elect not to cache the routing
information (perhaps due to storage limitations), then the QUERY
REPLY and QUERY-EXTENSION packets essentially serve the role of
ROUTE-ACCUMULATION packets, obviating the need for a separate
ROUTE-ACCUMULATION stage.
Because each node proactively maintains the local topology of its
routing zone, it is not necessary for a source route to specify
every hop along the route (i.e. strict source routing). A properly
chosen subset of the complete source route can be used to specify
the route to the destination, and where desirable, the reverse route
back to the source. The IERP supports such an optimization through
a final ROUTE-OPTIMIZATION stage. The details of the route
optimization are described in the BRP specification. Upon
completion of the ROUTE-OPTIMIZATION stage, sufficient routing zone
membership is acquired for each node in the route so that the source
route may be reduced (by translating this route reduction into
an appropriate set covering problem, and employing a suitable
heuristic).
+-----+ +-----+ +-----+
| S | . . . . | Y | . . . | D |
+-----+ +-----+ +-----+
(1) search for QUERY
route |-------------------------->
QUERY QUERY
(2) establish REPLY EXTENSION
connectivity <--------------------------|
|=============>
(3) provide ROUTE-ACCUMULATION
source route |---------------------------------------->
<========================================|
(4) optimize ROUTE-OPTIMIZATION
source route <----------------------------------------|
|========================================>
Sequence of the IERP Route Discovery Stages
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 | Request ID | Last Hop | Hop Mrker | Max Hops | | Type | Rsvd | Hops Left | Query ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address | | Bad Link Source Address (repair only) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Next IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ BRP
| Next BRP Address | fields
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Prev IERP Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Hop 0 Address (Source) | | | Hop 0 Address (Source) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Hop 1 Address | | | Hop 1 Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | | | | |
| | source | | |
\ / route \| |/ route
\ / | \ / |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| |
| Hop (N-1) Address | | | Hop (N-2) Address | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Hop (N-1) Address (Destination) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+-- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --+--
| Flags (optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field Description: Field Description:
* Type (4 bits) * Type (4 bits)
Identifies the type of IERP packet. The current version Identifies the type of IERP packet. The current version
of IERP contains three packet types: of IERP contains five packet types:
REQUEST: request an Interzone source route to
the destination host specified in
Destination Address
REPLY: response to a request packet; includes the source route to the
destination host specified in
Destination Address
FAILURE: control message sent a host indicating
that the received data packet contains
an invalid source route.
* Request ID (10 bits) QUERY:
request for an Interzone source route to the
destination specified by the Destination
IP Address
QUERY-EXTENSION:
extension of a QUERY packet sent from the
node that discovers the Destination to the
Destination itself.
QUERY-REPLY:
response to a QUERY packet, sent from the node
that discovers the Destination back to the
Source. At a minimum, the QUERY-REPLY contains
next-hop route information to the Destination.
(In general, returns the source route up to
the first node which has cached routing
information. If no nodes have cached routing
information, then the complete source route is
returned.)
ROUTE-ACCUMULATION (optional):
sent by the Source to the Destination, in
response to a QUERY-REPLY, and sent by the
Destination to the Source, in response to a
QUERY-EXTENSION. Routing information cached
at the route's nodes is accumulated in this
packet, providing a complete source route at
the destination of this packet.
ROUTE-OPTIMIZATION (optional):
sent by the Source to the Destination, and
by the Destination to the Source, in response
to a ROUTE-ACCUMULATION. Flags are appended
to this packet reflecting the mutual routing
zone membership of each node in the source
route.
* Query ID (16 bits)
Sequence number which, along with the Source Address Sequence number which, along with the Source Address
(see below) uniquely identifies any route query in the (see below) uniquely identifies any route query in the
network. (used only for REQUEST packets) network.
* Last Hop (6 bits) * Hops Left (8 bits)
Indicates the previous recipient of the IERP packet Number of hops that a route query may continue to
(referenced as an index into the Source Route (see propagate. This field allows a querying node to
below)) configure the depth of a route search, to
control the amount of IERP traffic generated.
* Hop Marker (6 bits) * Bad Link Address (32 bits)
Currently used to indicate the hop where a route failure Used during route repairs. Contains the IP Address
was detected (referenced as an index into the Source corresponding to the source of routes failed link.
Route (see below)) (used only for FAILURE packets)
* Max Hops (6 bits)
Maximum number of Interzone hops which a route query may
propagate. This field allows nodes to adaptively
configure the depth of a route search in order to
control the amount of IERP traffic generated. (used only
for REQUEST packets)
* Destination Address (32 bits) * Next IERP Address (32 bits)
IP address of the destination host 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
* Source Route (N*32 bits) * Source Route (N*32 bits)
Variable length field which contains the IP addresses of Variable length field that contains the IP addresses of
an N hop source route. The first subfield of the Source the source route's nodes.
Route contains the IP address of the route's source. - route(0) contains the IP address of the
In general, the n-th subfield contains the IP address of route's source.
the n-th hop in the route. - route(N-1) contains the IP address of the
For REQUEST packets, the Source Route represents the route's destination
incomplete accumulated route to the destination host - in general, route(n) contains the IP address
(as indicated by the Destination Address) of the n-th hop of the source route
For REPLY and FAILURE packets, the Source Route contains
the complete route from the source host to the * Flags (N * 32*ceil(N/32) bits)
destination host. The k-th bit of the n-th flag subfield indicates whether
route(k) is located within route(n)'s routing zone.
This routing zone membership information, collected
during the optional ROUTE-OPTIMIZATION stage, may be
used to determine the shortest possible specification
for the accumulated source route.
B. Structures B. Structures
B.1 Intrazone Routing Table (See IARP Description) B.1 Intrazone Routing Table (See IARP Description)
B.2 Interzone Routing Table B.2 Interzone Routing Table
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Routes | | | Routes |
+ Dest +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + Dest +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | 0 | 1 | ==> | M-| | | | 0 | 1 | ==> | M-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | ==> | | | | | | ==> | |
|---------|-----------|-----------|-----|-----------| |---------|-----------|-----------|-----|-----------|
| | | | ==> | | | | | | ==> | |
|---------|-----------|-----------|-----|-----------| |---------|-----------|-----------|-----|-----------|
| | | | | | ==> | | | | | | | | ==> | |
+-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
\ / \ /
\ / \ /
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+
| 0 |==>| 1 |==> ...==>| N-1 | source | 0 |==>| 1 |==> ...==>| N-1 | source
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ route +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ route
source first (N-1) source first (N-1)
host hop hop host hop hop
B.3 Processed Request List
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source | Request ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |
|-----------|---------------|
| | |
|-----------|---------------|
| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
C. Interfaces C. Interfaces
C.1 Higher Layer (N/A) C.1 Higher Layer (N/A)
C.2 Lower Layer (BRP) C.2 Lower Layer (BRP)
C.2.1 Send() (same interface as IP send()) C.2.1 Send() (same interface as IP send())
Used by the IERP to request transmission of a data Used by the IERP to request transmission of an
packet. IERP packet.
C.2.2 Deliver() (same interface as IP deliver()) C.2.2 Deliver() (same interface as IP deliver())
Used by the BRP to alert the IERP of the arrival of a Used by the BRP to alert the IERP of the arrival of a
data packet. data packet.
C.3 IARP C.3 IARP
C.3.1 Neighbor_Lost(host) C.3.1 Zone_Node_Lost(host)
Used by the NDM to notify the IARP that direct contact Used by the IARP to notify the IERP that a node has left
has been lost with "host". the routing zone
C.3.2 Neighbor_Found(host)
Used by the NDM to notify the IARP that direct contact
has been confirmed with "host".
C.4 ICMP C.4 ICMP
C.4.1 Host_Unreachable() (specified in ICMP standard) C.4.1 Host_Unreachable() (specified in ICMP standard)
C.4.2 Source_Route_Failed() (specified in ICMP standard) C.4.2 Source_Route_Failed() (specified in ICMP standard)
D. State Machine D. State Machine
The IERP protocol consists of only one state (IDLE). Therefore, The IERP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The IERP immediately no state transitions need to be specified. The IERP immediately
acts upon an event and then returns back to the IDLE state. acts upon an event and then returns back to the IDLE state.
Note: 1) X is used as a label for the host running this state Note: 1) X is used as a label for the host running this state
machine. machine.
D.1 D.1
Event: A "Host Lost" interrupt is received, indicating Event: A "Zone_Node_Lost" interrupt is received,
that the host H has moved beyond the routing zone. indicating that the node H has moved beyond the
routing zone.
Action: Remove every route from the Interzone Routing Table Action: Remove every route from the Interzone Routing Table
which contains H. A limited depth route discovery which contains H. If any routes containing H are
to H is initiated. An IERP request packet is found, then a route repair (limited depth route
created with the destination addresss set to H and discovery) to H is initiated.
the source route initialized with the IP address
of X. The request packet is then bordercasted.
D.2 D.2
Event: A "Host Unreachable" interrupt is received from the Event: A "Host_Unreachable" interrupt is received from the
ICMP, indicating an unknown destination host D. ICMP, indicating an unknown destination host D.
Action: A full depth route discovery to the lost host is Action: A full depth route discovery to D is initiated.
initiated. An IERP request packet is created with The query_id is incremented and assigned to a new
the destination addresss set to H and the source QUERY packet. The route is initialized with the
route initialized with the IP address of X. The IP addresses of the route's source and destination
request packet is then bordercasted. IP addresses (X and D). Finally, the QUERY packet
is bordercasted.
D.3 D.3
Event: An "Source Route Failed" interrupt is received from Event: A "Source_Route_Failed" or "Proactive_Repair"
the ICMP, indicating that the next hop specified in interrupt is received, indicating that the next
an IP source route does not appear within the hop, H, specified in a source route does not
routing zone. appear within the routing zone.
Action: A route failure packet containing the invalid route
is sent to the route's source with the hop marker
indicating X as the host where a route failure was
detected.
Action: A limited depth route discovery to H is initiated.
The query_id is incremented and assigned to a new
QUERY packet. The route is initialized with the
valid portion of the failed route, and the
bad link address field is set with X's IP address,
to indicate the location of the route failure.
Finally, the QUERY packet is bordercasted.
D.4 D.4
Event: An IERP request packet is received with a Event: A QUERY packet is received with a destination that
destination that appears within X's routing zone. appears within X's routing zone.
Action: The request is recorded in the Processed Request Action: A QUERY-REPLY is sent back to the query source, and
List. In order to be processed further, four a QUERY-EXTENSION is sent to the query destination.
conditions must be satisfied. First, the received
packet must not be flagged as overheard. Second,
the number of hops in the route must not exceed the
maximum hop count. Third, the request must not
have been previously recorded. Finally, no hops in
the route (except the last_hop) may lie within X's
routing zone. X appends its IP address to the route
and sends an IERP reply packet to the preceding hop
in the route.
D.5 D.5
Event: An IERP request packet is received with a Event: A QUERY packet is received with a destination that
destination that DOES NOT appear within X's routing DOES NOT appear within X's routing zone.
zone.
Action: The request is recorded in the Processed Request Action: The QUERY packet is bordercasted.
List. In order to be processed further, four
conditions must be satisfied. First, the received
packet must not be flagged as overheard. Second,
the number of hops in the route must not exceed the
maximum hop count. Third, the request must not have
been previously recorded. Finally, no hops in the
route (except the last_hop) may lie within X's
routing zone. X appends its IP address to the route
and is bordercasts an IERP request packet
containing the updated route.
D.6 D.6
Event: An IERP reply packet is received containing X as Event: A QUERY-EXTENSION packet is received.
the source host.
Action: The received source route is recorded in Interzone
Routing Table.
Action: The packet contents are moved to a ROUTE-
ACCUMULATION packet. The ROUTE-ACCUMULATION
packet is sent to the query source.
D.7 D.7
Event: An IERP reply packet is received containing a node Event: A QUERY-REPLY packet is received.
other than X as the source host.
Action: The route reply packet is fowarded to the preceding Action: The packet contents are moved to a ROUTE-
hop in the route ACCUMULATION packet. The ROUTE-ACCUMULATION
packet is sent to the query destination.
D.8 D.8
Event: An IERP failure packet is received containing X as Event: A ROUTE-ACCUMULATION packet is received. X is not
the source host. the final destination of this packet
(i.e. X != IERP_next). This only occurs when the
accumulated route contains a repair
Action: X removes all routes from its Interzone Routing Action: The bad link is replaced by the path repair in the
table which contain the broken link specified by Interzone Routing Table.
the bad hop field.
D.9 D.9
Event: An IERP failure packet is received containing a Event: A ROUTE-ACCUMULATION packet is received. X is
node other than X as the source host. either the route source or (route destination).
Action: X fowards the route reply packet to the preceding Action: The (reversed) accumulated route is added to the
hop in the route 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
E.1 Intrazone Node Lost We define two complimentary operations on packets:
extract(packet) and load(packet)
extract (packet)
extracts the fields of the IERP packet to the following
variables: {type, hops_left, query_id, bad_link_source,
next_IERP, next_BRP, prev_IERP, route, flag}
load (packet)
loads the values of the aforementioned variables into
the fields of the IERP packet.
E.1 Routing Zone Node Lost
{lost_host} <-- intrpt {lost_host} <-- intrpt
repair_link = FALSE
for host = each host in Interzone Routing Table for host = each host in Interzone Routing Table
{ {
m=0 for (route = each Interzone route to host)
while (Interzone_Routing_Table[host,m] != NULL)
{ {
route=Interzone_Routing_Table[host,m]
if (lost_host (EXISTS IN) route) if (lost_host (EXISTS IN) route)
remove(Interzone_Routing_Table[host,m]) {
if (PROACTIVE_REPAIRS_ENABLED)
{
removal_timer = ROUTE_QUERY_TIMEOUT
repair_link = TRUE
}
else else
m++ removal_timer = 0
schedule(
remove(Interzone_Routing_Table[host]->route(m)),
removal_timer)
} }
} }
force_intrpt("IERP","repair",{lost_host}) }
E.2 Initiate Route Discovery if(repair_link)
{
{dest} <-- intrpt bad_link = my_id + lost_host
req_id++ force_intrpt("IERP","Proactive_Repair", bad_link)
route(0)=my_id }
last_hop=0
if (type(intrpt) == "repair")
max_hops=MAX_REPAIR_HOPS
else
max_hops=MAX_REQUEST_HOPS
packet <-- {REQUEST, req_id, last_hop, NULL, max_hops, dest,
route}
bordercast(packet)
add (Processed_Request_List, {my_id, req_id})
E.3 Report Route Failure E.2 Initiate Route Discovery
{route,dest} <-- intrpt {route} <-- intrpt
last_hop=0
while (route(last_hop) != my_id)
last_hop++
packet <-- {FAILURE, NULL, last_hop, last_hop, NULL, dest,
route}
send(packet, route(last_hop-1))
E.4 Receive IERP Packet dest = route(length(route)-1)
current_hop_ptr = get_index(route, my_id)
prev_hops = route(0: current_hop_ptr-1)
{pk_type, req_id, last_hop, bad_hop, max_hops, route} <-- route = prev_hops + my_id + dest
packet if (type(intrpt) == "Proactive_Repair" ||
{overheard} <-- intrpt type(intrpt) == "Source_Route_Failed")
switch(pk_type)
{ {
case: REQUEST hops_left = MAX_REPAIR_HOPS
add({Processed_Request_List, source, req_id) bad_link_source = my_id
LSP1_terminate = FALSE }
n=0 else
while (!LSP1_terminate && n < last_hop)
{ {
if (Intrazone_Routing_Table[route(n)]!=NULL) hops_left = MAX_FULL_QUERY_HOPS
LSP1_terminate = TRUE bad_link_source = NULL
n++
} }
LSP2_terminate = (Processed_Request_List[source,req_id] query_id ++
!= NULL) load (packet)
if (!overheard && !LSP1_terminate && !LSP2_terminate && send (packet, BORDERCAST)
last_hop < max_hops) E.3 Receive IERP Packet
extract(packet)
source=route(0)
dest = route(length(route)-1)
switch(pk_type)
{ {
last_hop++ case: QUERY
route(last_hop)=my_id
if (dest (EXISTS IN) Intrazone_Routing_Table) if (dest (EXISTS IN) Intrazone_Routing_Table)
{ {
packet<--{REPLY,req_id,last_hop,bad_hop,max_hops, type = QUERY-REPLY
dest,route} if(bad_link_source)
send(packet, route(last_hop-1)) IERP_next = bad_link_source
else
IERP_next = source
load(packet)
send(packet)
type = QUERY-EXTENSION
IERP_next = dest
load(packet)
send(packet)
} }
else else
{
packet<--{REQUEST,req_id,last_hop,bad_hop,max_hops,
dest,route}
bordercast(packet) bordercast(packet)
}
}
break break
case: REPLY case: QUERY-EXTENSION
case: FAILURE type = ROUTE-ACCUMULATION
if (route(0) == my_id) IERP_next=source
send(packet)
break
case: QUERY-REPLY
type = ROUTE-ACCUMULATION
IERP_next = dest
load (packet)
send (packet)
break
case: ROUTE-ACCUMULATION
if (bad_link_source)
{ {
if (pk_type == ROUTE_REPLY) path_source_ptr = get_index(route, bad_link_source)
add(Interzone_Routing_Table, route) path_dest_ptr = get_index(route, dest)
else if (IERP_next == source)
{ {
link(0)=route(bad_hop) bad_link = bad_link_source + dest
link(1)=route(bad_hop+1) path_repair = route(path_source_ptr:path_dest_ptr)
remove(Interzone_Routing_Table,link) }
if (IERP_next == dest)
{
bad_link = dest + bad_link_source
path_repair = reverse(route(path_source_ptr :
path_dest_ptr))
} }
replace(Interzone_Routing_Table, bad_link,path_repair)
} }
else else
{ {
last_hop -- if (my_id == source)
packet <-- {pk_type,req_id,last_hop,bad_hop,max_hops, add(Interzone_Routing_Table, route)
dest,route} if (my_id == dest)
send(packet, route(last_hop-1)) add(Interzone_Routing_Table, reverse(route))
}
} }
4.3 Bordercast Resolution Protocol (BRP) if (my_id == IERP_next)
{
if (my_id == source)
IERP_next = dest
if (my_id == dest)
IERP_next = source
The higher layer interface of the BRP is designed to be compatible type = ROUTE-OPTIMIZATION
with any IP based application. However, it is assumed that the load (packet)
routing zone hierarchy is visible only to the ZRP entities, making send (packet)
bordercasting services only of use to the IERP. }
break
case: ROUTE-OPTIMIZATION
if (my_id == source)
add(Interzone_Routing_Table, route, flags)
if (my_id == dest)
add(Interzone_Routing_Table, reverse(route), flags)
break
}
Upon receipt of a (IERP) packet to be bordercasted, the BRP resolves 4.3 Bordercast Resolution Protocol (BRP)
the bordercast address into the individual IP addresses of the
peripheral nodes. The received packet is then encapsulated into a BRP
packet and sent to each peripheral node (via IP broadcast
transmission).
When a BRP packet is delivered from IP, the (IERP) data is The BRP is a sublayer of the IERP that performs the operations of
decapsulated and passed on to the higher layer. If the BRP packet bordercasting, query control, route accumulation and routing zone
has not reached its destination, the BRP is responsible for labelling, which form the basis for the route discovery procedure.
forwarding the packet to the next hop toward its destination.
A. Packet Format In this BRP implementation, bordercasting is implemented as a series
of unicasted messages to the peripheral nodes. The BRP is able to
identify the peripheral based on the information contained in the
Intrazone Routing Table. Rather than unicasting to the peripheral
node directly through IP, the bordercasted packets are relayed to
the peripheral nodes by the BRP layer. IP is used only to send
these messages one hop toward the peripheral nodes. This allows the
BRP to detect all QUERY packets that are received by that node.
1 2 3 To efficiently terminate the query, the BRP needs to record
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 sufficient information from each detected query. The query's source
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ and ID, which serve to uniquely identify a query, are added to the
| Destination Address | Detected Queries Table. In addition, the IP address of the last
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ node to bordercast the query is also recorded in the Detected
| Next Hop Address | Queries table. Any threads of this query that are later received
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ from a different bordercasting node are discarded. Each query also
| Data | contains a hop counter that is decremented at each node. When the
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ counter expires, the packet is discarded.
Field Description: IERP packets (excluding ROUTE-OPTIMIZATION packets) that are not
terminated next undergo a route accumulation procedure. As
described earlier, route accumulation is used to construct routes,
by recording the IP addresses of a route's nodes in the IERP packet
or local cache. The Detected Queries Table, extended by two
columns, serves as a convenient route accumulation cache.
* Destination Address (32 bits) The node begins the route accumulation procedure by adding its IP
IP address of the destination host address to the IERP route. This is followed by the IP addresses of
any cached nodes leading to the packet's destination (the "next
hops"). This is sufficient processing for ROUTE-ACCUMULATION
packets, where complete source routes are constructed. On the other
hand, QUERY, QUERY-EXTENSION and QUERY-REPLY packets should carry as
little of the route as possible. Therefore, if cache space is
available, the route accumulation process records the IP addresses
of the "previous hops" from the packet's source, and removes them
from the IERP packet.
* Next Hop Address (32 bits) The final role of the BRP is contribute to the ROUTE-OPTIMIZATION
IP address of the "next hop" host to the destination process by indicating the mutual routing zone membership of the
host 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.)
A. Packet Format
* Data (variable length) See IERP packet format in Section 4.2
Encapsulated data
B. Structures B. Structures
B.1 Intrazone Routing Table (see IARP description) B.1 Intrazone Routing Table (see IARP description)
B.2 Detected Queries Table
|--------------------|--------|-----------------------|
| Query | Query | Prev | Prev | Next |
| Source | Id | IERP | Hop(s) | Hop(s) |
|----------+---------|--------+-----------+-----------|
| | | | | | | | | |
|----------+---------|--------+---+---+---|---+---+---|
| | | | | | | | | |
|----------+---------|--------+---+---+---|---+---+---|
| | | | | | | | | |
|--------------------|--------|-----------------------|
|
\|/
+---+ +---+ +---+
| A |-->| B |-->... | C |
+---+ +---+ +---+
cached "source" route
C. Interfaces C. Interfaces
C.1 Higher Layer (ie. IERP) C.1 Higher Layer (i.e. IERP)
C.2.1 Send() (same interface as IP Send() primitive) C.2.1 Send() (same interface as IP Send() primitive)
Used by higher layer protocol to request transmission of Used by higher layer protocol to request transmission of
a data packet a data packet
C.2.2 Deliver() (same interface as IP Deliver() primitive) C.2.2 Deliver() (same interface as IP Deliver() primitive)
Used by the BRP to alert the higher layer protocol of Used by the BRP to alert the higher layer protocol of
the arrival of a data packet the arrival of a data packet
C.2 Lower Layer (IP) C.2 Lower Layer (IP)
C.2.1 Send() (specified in IP standard) C.2.1 Send() (specified in IP standard)
C.2.2 Deliver() (specified in IP standard) C.2.2 Deliver() (specified in IP standard)
skipping to change at page 20, line 6 skipping to change at page 27, line 6
The BRP protocol consists of only one state (IDLE). Therefore, The BRP protocol consists of only one state (IDLE). Therefore,
no state transitions need to be specified. The BRP immediately no state transitions need to be specified. The BRP immediately
acts upon an event and then returns back to the IDLE state. acts upon an event and then returns back to the IDLE state.
Notes: 1) X is used as a label for the host running this state Notes: 1) X is used as a label for the host running this state
machine. machine.
2) NULL is a reserved field value, corresponding to an 2) NULL is a reserved field value, corresponding to an
invalid IP address. invalid IP address.
D.1 D.1
Event: A packet is received from the IERP, destined for Event: A QUERY packet is received from the IERP
the BORDERCAST address.
Action: The IERP packet is encapsulated in a BRP packet. A
copy of the BRP packet is made for each peripheral
host, P. (i.e., each host in X's Intrazone Routing
Table whose shortest route is ROUTING_ZONE_RADIUS
hops away from X). The packet's destination address
is set to the IP address of P and the next hop
address is set to the IP address of the next hop
to P (from X). Each packet is then broadcasted.
Action: If X is the query's source, then the identifying
querying information is recorded in the Detected
Queries Table. X adds its IP address to the
packet's route. A copy of the packet is sent to
the IERP layer of each peripheral node, by way of
a BRP transmission to the next hop to that
peripheral node.
D.2 D.2
Event: A packet is received from the IERP, destined for a Event: A QUERY packet is received from the IP. The hop
non-BORDERCAST address. counter has expired or the query was already
detected from another bordercasting node.
Action: The IERP packet is encapsulated in a BRP packet. Action: The packet is discarded.
The BRP packet`s destination address and next hop
address fields are cleared and the BRP packet is
sent to the specified destination.
D.3 D.3
Event: A BRP packet is received from the IP layer. The BRP Event: A QUERY packet is received from IP. The hop count
packet contains a next hop address EQUAL TO NULL. 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: The data is decapuslated from the BRP packet and Action: If cache space is available, identifying query
delivered to the IERP, with the overhead flag set information SHOULD be recorded in the Detected
to FALSE. Queries Table. The packet is then discarded.
D.4 D.4
Event: A BRP packet is received from the IP layer. The BRP Event: A QUERY packet is received from the IP. The hop
packet contains a valid next hop address and a count has not expired and the query has not been
destination address EQUAL TO X. 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 data is decapuslated from the BRP packet and Action: The hop counter is decremented. If cache space
delivered to the IERP, with the overhead flag set is available, identifying query information and
to FALSE. accumulated route information should be recorded
in the Detected Queries Table. The recorded route
information is removed from the packet and X adds
its IP address to the route.
The packet is then sent to the BRP of the next hop
to the intended IERP recipient.
D.5 D.5
Event: A BRP packet is received from the IP layer. The BRP Event: A QUERY packet is received from the IP. The hop
packet contains a valid next hop address EQUAL TO count has not expired and the query has not been
X and a destination address NOT EQUAL TO X. 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 data is decapuslated from the BRP packet and Action: The hop counter is decremented. If cache space
delivered to the IERP, with the overhead flag set is available, identifying query information and
to TRUE. The received BRP packet is copied, the accumulated route information should be recorded
next hop address field is updated by querying the in the Detected Queries Table. The recorded route
Intrazone Routing Table, and the new packet is information is removed from the packet and X adds
broadcasted. its IP address to the route.
The packet is then delivered up to the IERP.
D.6 D.6
Event: A BRP packet is received from the IP layer. The BRP Event: A QUERY-EXTENSION is received from the IERP.
packet contains a valid next hop address NOT EQUAL
TO X and a destination address NOT EQUAL TO X.
Action: The data is decapuslated from the BRP packet and Action: The packet is sent to the BRP layer of the
delivered to the IERP, with the overhead flag set next hop to the specified IERP recipient
to TRUE. (in this case, the query destination).
D.7
Event: A QUERY-EXTENSION is received from the IP.
X is not the intended BRP recipient.
Action: If cache space is available, identifying query
information SHOULD be recorded in the Detected
Queries Table. The packet is then discarded.
D.8
Event: A QUERY-EXTENSION packet is received from the IP.
X is the intended BRP recipient, but is not the
intended IERP recipient.
Action: If cache space is available, identifying query
information and accumulated route information
should be recorded in the Detected Queries Table.
The recorded route information is removed from the
packet and X adds its IP address to the route.
The packet is then sent to the BRP of the next hop
to the intended IERP recipient.
D.9
Event: A QUERY-EXTENSION packet is received from the IP.
X is the intended BRP recipient and the intended
IERP recipient.
Action: If cache space is available, identifying query
information and accumulated route information
should be recorded in the Detected Queries Table.
The recorded route information is removed from the
packet and X adds its IP address to the route.
The packet is then delivered up to the IERP.
D.10
Event: A QUERY-REPLY packet is received from the IERP.
Action: The IP addresses of X and the previous hops back
to the query source (cached in the Detected Queries
Table) are added to the route. The packet is sent
back to the IERP layer of the query source, by way
of a BRP layer transmission to the first hop back
to the query source.
D.11
Event: A QUERY-REPLY packet is received from the IP.
X is not the intended BRP recipient.
Action: The packet is discarded.
D.12
Event: A QUERY-REPLY packet is received from the IP.
X is the intended BRP recipient, but not the
intended IERP recipient.
Action: If cache space is available, accumulated route
information to the destination should be recorded
in the Detected Queries Table, and the recorded
route information removed from the packet. The IP
addresses of X and the previous hops back to the
query source (cached in the Detected Queries Table)
are added to the route.
The packet is then sent to the BRP layer of the
previous hop back to the query source.
D.13
Event: A QUERY-REPLY packet is received from the IP.
X is the intended BRP recipient and the intended
IERP recipient.
Action: If cache space is available, accumulated route
information to the destination should be recorded
in the Detected Queries Table, and the recorded
route information removed from the packet.
The packet is then delivered up to the IERP.
D.14
Event: A ROUTE-ACCUMULATION packet is received from the
IERP.
Action: The packet is sent to the IERP layer of the
specified IERP recipient by way of a BRP
transmission to the next hop toward the IERP
recipient.
D.15
Event: A ROUTE-ACCUMULATION packet is received from the
IP. X is not the intended BRP recipient.
Action: The packet is discarded.
D.16
Event: A ROUTE-ACCUMULATION packet is received from the
IP. X is the intended BRP recipient, but not the
intended IERP recipient.
Action: The IP addresses of X and the next hops to the
intended IERP recipient (which are cached in the
Detected Queries Table) are added to the route.
If this packet contains a route repair and the
repair has already been accumulated, then a copy
of the packet is delivered to the IERP. The
packet is then sent to the BRP layer of the next
hop toward the IERP recipient.
D.17
Event: A ROUTE-ACCUMULATION packet is received from the
IP. X is the intended BRP recipient and the
intended IERP recipient.
Action: The packet is delivered up to the IERP.
D.18
Event: A ROUTE-OPTIMIZATION packet is received from the
IERP.
Action: X indicates (in its flag field) those route nodes
that belong to its routing zone. The packet is
then sent to the IERP layer of the specified IERP
recipient, by way of a BRP transmission to the
next hop toward the IERP recipient.
D.19
Event: A ROUTE-OPTIMIZATION packet is received from the
IP. X is not the intended BRP recipient.
Action: The packet is discarded.
D.20
Event: A ROUTE-OPTIMIZATION packet is received from the
IP. X is the intended BRP recipient, but not
the intended IERP recipient.
Action: X indicates (in its flag field) those route nodes
that belong to its routing zone. The packet is
then sent to the IERP layer of the specified IERP
recipient, by way of a BRP transmission to the
next hop toward the IERP recipient.
D.21
Event: A ROUTE-OPTIMIZATION packet is received from the
IP. X is the intended BRP recipient and the
intended IERP recipient.
Action: X indicates (in its flag field) those route nodes
that belong to its routing zone. The packet
is then delivered up to the IERP
E. Pseudocode Implementation E. Pseudocode Implementation
E.1 Receive Data Packet from IERP We define two complimentary operations on packets:
extract(packet) and load(packet)
{dest} <-- intrpt extract (packet)
if (dest == BORDERCAST) extracts the fields of the IERP packet to the following
variables: {type, hops_left, query_id, bad_link_source,
next_IERP, next_BRP, prev_IERP, route, flag}
load (packet)
loads the values of the aforementioned variables into
the fields of the IERP packet.
E.1 Receive Packet from IERP
extract (packet)
source = route(0)
dest = route(length(route)-1)
current_hop_ptr = get_index(route, my_id)
prev_hops = reverse(route(0: current_hop_ptr-1))
next_hops = route(current_hop_ptr+1 : length(route)-1)
IERP_prev = my_id
switch(type)
{ {
for (host = each host in Intrazone_Routing_Table) case: QUERY
if ((bad_link_source == my_id || source == my_id)
add(Detected_Queries,packet)
for (IERP_next = each host in Intrazone_Routing_Table)
{ {
if (Intrazone_Routing_Table[host,0]->hop_count if (IERP next is a peripheral node)
==ROUTING_ZONE_RADIUS)
{ {
next_hop=Intrazone_Routing_Table[host,0]->next_hop BRP_next=Intrazone_Routing_Table[host,0]->next_hop
packet<--{host,next_hop,data_packet} load(pk_copy)
broadcast(packet) send(pk_copy,BRP_next)
} }
} }
break
case: QUERY-EXTENSION
BRP_next=Intrazone_Routing_Table[IERP_next,0]->next_hop
load(packet)
send(packet,BRP_next)
break
case: QUERY-REPLY
if (prev_hops(0) == source)
prev_hops = Detected_Queries[source,query_id]
->prev_hops
route = prev_hops + my_id + next_hops
BRP_next = prev_hops(0)
load(packet)
send(packet,BRP_next)
break
case: ROUTE-ACCUMULATION
if(my_id == source)
BRP_next = next_hops(0)
if(my_id == dest)
BRP_next = prev_hops(0)
load(packet)
send(packet,BRP_next)
break
case: ROUTE-OPTIMIZATION
flag = NULL
for (i = 0 to length(route)-1)
{
if ((EXISTS) Intrazone_Routing_Table[route(i)])
flag = flag,1
else
flag = flag,0
}
if(my_id == source)
BRP_next = next_hops(0)
if(my_id == dest)
BRP_next = prev_hops(0)
load(packet)
send(packet,BRP_next)
break
E.2 Receive Packet from IP
extract(packet)
source = route(0)
dest = route(length(route)-1)
current_hop_ptr = get_index(route, my_id)
prev_hops = reverse(route(0: current_hop_ptr-1))
next_hops = route(current_hop_ptr+1 : length(route)-1)
switch(type)
{
case QUERY:
if (hops_left > 0 &&
(!EXISTS(Detected_Queries[source,query_id] ||
Detected_Queries[source,query_id]->from
== IERP_prev))
{
hops_left --
if (!FULL (Detected_Queries))
{
add(Detected_Queries, packet)
prev_hops = source
} }
else else
route = prev_hops + my_id + next_hops
if(BRP_next == my_id)
{ {
packet<--{dest,NULL,data_packet} if(IERP_next == my_id ||
send(packet,dest) dest (EXISTS IN) Intrazone_Routing_Table)
deliver(packet,IERP)
else
{
BRP_next=Intrazone_Routing_Table[IERP_next]
->route(0)->next_hop
load(packet)
send(packet, BRP_next)
}
}
else
discard(packet)
}
else
discard(packet)
break
case QUERY-EXTENSION:
{
if (!FULL (Detected_Queries))
{
add(Detected_Queries,packet)
prev_hops = source
} }
route = prev_hops + my_id + next_hops
E.2 Receive Packet from IP if(BRP_next == my_id)
{
if(IERP_next == my_id ||
dest (EXISTS IN) Intrazone_Routing_Table)
deliver(packet,IERP)
else
{
BRP_next=Intrazone_Routing_Table[IERP_next]
->route(0)->next_hop
load(packet)
send(packet, BRP_next)
}
}
else
discard(packet)
}
else
discard(packet)
break
{dest,next_hop,data}<--packet case QUERY-REPLY:
overheard=FALSE if(my_id == BRP_next)
if (next_hop != NULL)
{ {
if (next_hop == my_id) if (!FULL (Detected_Queries))
{ {
if(dest != my_id) add(Detected_Queries, packet)
next_hops = dest
}
if (prev_hops(0) == source)
prev_hops = Detected_Queries[source,query_id]
->prev_hops
route = prev_hops + my_id + next_hops
if(my_id == IERP_next)
deliver(packet,IERP)
else
{ {
overheard=TRUE BRP_next = prev_hops(0)
next_hop = Intrazone_Routing_Table[dest,0]->next_hop load(packet)
packet<--{dest,next_hop,data} send(packet,BRP_next)
broadcast(packet)
} }
} }
else else
overheard=TRUE discard(packet)
break
case ROUTE-ACCUMULATION:
if(my_id == BRP_next)
{
if(my_id == IERP_next)
deliver(packet, IERP)
else
{
if (bad_link_source && IERP_next == source)
{
bad_link_ptr=get_index(route,bad_link_source)
if (current_hop_ptr <= bad_link_ptr)
deliver(packet, IERP)
} }
deliver(IERP,data,{overheard}) if (IERP_next == dest)
{
if(next_hops(0) == dest)
next_hops=Detected_Queries[source,query_id]
->next_hops
BRP_next = next_hops(0)
}
if (IERP_next == source)
{
if(prev_hops(0) == source)
prev_hops=Detected_Queries[source,query_id]
->prev_hops
BRP_next = prev_hops(0)
}
route = prev_hops + my_id + next_hops
load(packet)
send (packet,BRP_next)
}
}
else
discard(packet)
break
case ROUTE-OPTIMIZATION:
if(my_id == BRP_next)
{
f = NULL
for (i = 0: length(route)-1)
{
if ((EXISTS) Intrazone_Routing_Table[route(i)])
f = f,1
else
f = f,0
}
if (IERP_next == source)
flag = f , flag
else
flag = flag , f
5.0 Other Considerations if(my_id == IERP_next)
deliver(packet, IERP)
else
{
if(IERP_next == source)
BRP_next = prev_hops(0)
else
BRP_next = next_hops(0)
load(packet)
send (packet,BRP_next)
}
}
else
discard(packet)
break
5. Other Considerations
5.1 Sizing the Zone Radius 5.1 Sizing the Zone Radius
The value of the zone radius determines the performance of the ZRP The performance of the Zone Routing Protocol is determined by the
protocol. In general, highly mobile networks should set the zone routing zone radius. In general, dense networks consisting of a few
radius to a smaller values, while in more stationary networks the fast moving nodes favor smaller routing zones. On the other hand, a
zone radius should be larger. Similarly, in very active networks sparse network of many slowly moving nodes operates more efficiently
(frequent query requests), the zone radius should be larger, and in with a larger zone radius.
low-activity networks, the zone radius should be smaller.
We believe that setting the size of the zone radius should be The simplest approach to configuring the routing zone radius is to
performed by the administration of the network, if one exists, or make the assignment once, prior to deploying the network. This can
by the manufacturer, as a default value. Although some guidance can be performed by the network administration, if one exists, or by
be given as to "optimal" value of the zone radius [Haas-3], the manufacturer, as a default value. This may provide acceptable
additional constrains and operational conditions may affect this performance, especially in situations where network characteristics
choice. do not vary greatly over space and time. Alternatively, the ZRP can
adpat to changes in network behavior, through dynamnic configuration
of the zone radius [Haas-3]. In [Haas-4], it was shown that
a node can accurately estimate its optimal zone radius, on-line,
based on local measurements of ZRP traffic. The re-sizing of the
routing zone can be carried out by a protocol that conveys the
change in zone radius to the members of the routing zone. The
details of such an update protocol will be provided in a future
version of this draft.
6.0 References 6.0 References
[AODV] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing", [AODV] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing",
MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA,
November 3, 1997 November 3, 1997
[Corson] Corson, M.S., and Ephremides, A., "A Distributed Routing
Algorithm for Mobile Wireless Networks", ACM/Baltzer
journal on Wireless Networks, January 1995
[Haas-1] Haas, Z.J., "A New Routing Protocol for the Reconfigurable [Haas-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.
[Haas-2] Haas, Z.J., and Pearlman, M.R., "Providing Ad-Hoc [Haas-2] Haas, Z.J. and Pearlman, M.R., "The Performance of Query
Connectivity with the Reconfigurable Wireless Networks", Control Schemes for the Zone Routing Protocol,"
submitted for journal publication. SIGCOMM'98, Vancouver, BC, Sept. 2-4, 1998.
[Haas-3] Haas, Z.J., "Design Choices in Ad-Hoc Networking", [Haas-3] Haas, Z.J. and Tabrizi, S., "On Some Challenges and Design
in preparation. Choices in Ad-Hoc Communications", MILCOM'98, Boston, MA,
October 18-21, 1998.
[Haas-4] Haas, Z.J. and Pearlman, M.R., "Determining the Optimal
Configuration for the Zone Routing Protocol", submitted
for journal publication.
[Johnson] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing [Johnson] 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,
T. Imielinski and H. Korth, editors, Kluwer, 1996 edited by T. Imielinski and H. Korth, chapter 5,
pp. 153-181, Kluwer, 1996.
[Murthy] Murthy, S., and Garcia-Luna-Aceves, J.J., "A Routing [Murthy] Murthy, S., and Garcia-Luna-Aceves, J.J., "An Efficient
Protocol for Packet Radio Networks", MOBICOM'95, Routing Protocol for Wireless Networks", MONET, vol. 1,
November 14-15, 1995 no. 2, pp. 183-197, October 1996.
[Park] Park, V.D., and Corson, M.S., "A Highly Adaptive
Distributed Routing Algorithm for Mobile Wireless
Networks," IEEE INFOCOM'97, Kobe, Japan, 1997.
[Perkins] Perkins, C.E., and Bhagwat, P., "Highly Dynamic [Perkins] Perkins, C.E., and Bhagwat, P., "Highly Dynamic
Destination-Sequenced Distance-Vector Routing (DSDV) for Destination-Sequenced Distance-Vector Routing (DSDV) for
Mobile Computers, ACM SIGCOMM, vol.24, no.4, October 1994 Mobile Computers",ACM SIGCOMM, vol.24, no.4, October 1994.
[TORA] Macker, J., "Mobile Ad Hoc Internetworking", MILCOM'97 [TORA] Macker, J., "Mobile Ad Hoc Internetworking", MILCOM'97
panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997 panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997.
[RFC-0791] Postel, J., Editor, "Internet Protocol", STD 5, RFC 791, [RFC-0791] Postel, J., Editor, "Internet Protocol", STD 5, RFC 791,
September 1981 September 1981.
[RFC-1075] Waitzman, D., Partridge, C., Deering, S.E., "Distance [RFC-1075] Waitzman, D., Partridge, C., Deering, S.E., "Distance
Vector Multicast Routing Protocol", RFC 1075, Nov. 1, 1988 Vector Multicast Routing Protocol",RFC 1075, Nov. 1, 1988.
[RFC-2178] Moy, J., "OSPF Version 2", INTERNET DRAFT STANDARD, [RFC-2178] Moy, J., "OSPF Version 2", INTERNET DRAFT STANDARD,
RFC 2178, July 1997 RFC 2178, July 1997.
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 Electrial Engineering School of Electrical Engineering
Cornell University Cornell University
Ithaca, NY 14853 Ithaca, NY 14853
United States of America United States of America
tel: (607) 255-3454, fax: (607) 255-9072 tel: (607) 255-3454, fax: (607) 255-9072
Email: haas@acm.org or haas@ee.cornell.edu Email: haas@acm.org or haas@ee.cornell.edu
Marc R. Pearlman Marc R. Pearlman
319 Frank Rhodes Hall 319 Frank Rhodes Hall
School of Electrial Engineering School of Electrical Engineering
Cornell University Cornell University
Ithaca, NY 14853 Ithaca, NY 14853
United States of America United States of America
Email: pearlman@ee.cornell.edu Email: pearlman@ee.cornell.edu
The MANET Working Group contacted through its chairs: The MANET Working Group contacted through its chairs:
M. Scott Corson M. Scott Corson
Institute for Systems Research Institute for Systems Research
University of Maryland University of Maryland
 End of changes. 

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