INTERNET-DRAFT October 1998
draft-ietf-manet-cedar-spec-00.txt
Expires in six months
Core Extraction Distributed Ad hoc Routing (CEDAR) Specification
Raghupathy Sivakumar Prasun Sinha Vaduvur Bharghavan
University of Illinois, Urbana-Champaign
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress."
To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern
Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific
Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).
Abstract
This draft presents CEDAR, a Core-Extraction Distributed Ad
hoc Routing algorithm for QoS routing in ad hoc network environments.
CEDAR has three key components: (a) the establishment and
maintenance of a self-organizing routing infrastructure, called
the "core", for performing route computations, (b) the
propagation of the link-state of stable high-bandwidth links in the
core through "increase/decrease" waves, and (c) a QoS route
computation algorithm that is executed at the core nodes using only
locally available state.
Sivakumar, Sinha, Bharghavan [Page 1]
INTERNET-DRAFT CEDAR Specification October 1998
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Network Model . . . . . . . . . . . . . . . . . . . . . . . 5
3. CEDAR Architecture and the Core . . . . . . . . . . . . . . 7
3a. Rationale for a Core-based Architecture in CEDAR . . . . . 8
3b. Generation and Maintenance of the Core in CEDAR . . . . . 10
3c. Core Broadcast and its Application to CEDAR . . . . . . . 12
4. QoS State Propagation in CEDAR . . . . . . . . . . . . . . 14
4a. Increase and Decrease Waves . . . . . . . . . . . . . . . 15
4b. Issues in link state propagation . . . . . . . . . . . . 19
5. QoS Routing in CEDAR . . . . . . . . . . . . . . . . . . . 20
5a. Establishment of the Core Path . . . . . . . . . . . . . 20
5b. QoS Route Computation . . . . . . . . . . . . . . . . . . 22
5c. Dynamic QoS Route Recomputation for Ongoing Connections . 24
6. Performance Results . . . . . . . . . . . . . . . . . . . 25
7. Conclusions . . . . . . . . . . . . . . . . . . . . . . . 26
8. References . . . . . . . . . . . . . . . . . . . . . . . . 27
9 . Authors' Addresses . . . . . . . . . . . . . . . . . . . . 28
Sivakumar, Sinha, Bharghavan [Page 2]
INTERNET-DRAFT CEDAR Specification October 1998
1. Introduction
An ad hoc network is a dynamic multi-hop wireless network that is
established by a group of mobile hosts on a shared wireless
channel by virtue of their proximity t[o each other. These
channels, typically being scarce and dynamic, make it difficult to
perform efficient resource utilization or to execute critical
applications. Hence, QoS routing, as opposed to non-QoS routing, is
desirable in such environments. This draft focuses on a restricted
QoS Routing problem: the satisfaction of minimum bandwidth
requirements. Of course, since the network is highly dynamic, and
transmissions are susceptible to fades, interference, and collisions
from hidden/exposed stations, CEDAR cannot provide bandwidth
guarantees for the computed routes. Rather, its goal is to provide
routes that are highly likely to satisfy the bandwidth requirement of
a route, so long as such routes exist [1].
Given the nature of the network and the requirements of the
applications, the following are the key goals of CEDAR.
(a) Route computation must be distributed because centralized
routing in a dynamic network is impossible even for fairly small
networks. (b) Route computation should not involve the maintenance of
global state, or even significant amounts of volatile non-local
state. In particular, link state routing is not feasible for highly
dynamic networks because of the significant state propagation
overhead when the network topology changes. (c) As few nodes as
possible must be involved in state propagation and route computation
(without becoming single points of failure), since this involves
monitoring and updating at least some state in the network. On the
other hand, every host must have quick access to routes on-demand.
(d) Each node must only care about the routes corresponding to its
destination, and must not be involved in frequent topology updates
for parts of the network to which it has no traffic. (e) Stale routes
must be either avoided, or detected and eliminated quickly. (f)
Broadcasts must be avoided as far as possible because broadcasts are
highly unreliable in ad hoc networks. (g) If the topology stabilizes,
then routes must converge to the optimal routes, and (h) It is
desirable to have a backup route when the primary route has become
stale and is being recomputed.
QoS routing for ad hoc networks is relatively unchartered territory.
In addition to the above, we have the following goals for QoS routing
in ad hoc networks. (a) Applications provide a minimum bandwidth
requirement for a connection, and the routing algorithm must
efficiently compute a route that can satisfy the bandwidth
requirement with high probability. (b) The amount of state
propagation and topology update information must be kept to a
Sivakumar, Sinha, Bharghavan [Page 3]
INTERNET-DRAFT CEDAR Specification October 1998
minimum. In particular, every change in available bandwidth should
not result in updated state propagation. (c) Dynamic links (either
unstable or low bandwidth links) must not cause state propagation
throughout the network. Only stable high bandwidth link information
must be propagated throughout the network, and (d) The QoS route
computation algorithm should be simple and robust. Robustness, rather
than optimality, is the key requirement.
In order to achieve the above goals, this draft proposes the Core-
Extraction Distributed Ad hoc Routing (CEDAR) algorithm for QoS
routing in ad hoc networks. Briefly, CEDAR dynamically establishes a
"core" of the network, and then incrementally propagates link state
of stable high bandwidth links to the nodes of the core. Route
computation is on-demand, and is performed by core hosts using local
state only. CEDAR is proposed as a QoS routing algorithm for small
to medium size ad hoc networks consisting of tens to hundreds of
nodes. CEDAR does not compute optimal routes because of the
minimalist approach to state management, but the trade-off of
robustness and adaptation for optimality is believed to be well
justified in ad hoc networks. The following is a brief description of
the three key components of CEDAR.
1. Establishment and Maintenance of a core using Local Core
Extraction
CEDAR does core extraction in order to extract a subset of nodes
in the network that would be the only ones that perform state
management and route computation. The core extraction is done
dynamically by approximating a minimum dominating set of the ad
hoc network using only local computation and local state. Each
host in the core then establishes a virtual link (via a tunnel) to
nearby core hosts (within the 3rd neighborhood in the ad hoc
network). Each core host maintains the local topology of the hosts
in its domain, and also performs route computation on behalf of
these hosts. The core computation and core management upon change
in the network topology are purely local computations to enable
the core to adapt efficiently to the dynamics of the network.
2. Link State Propagation using Increase/Decrease waves
While it is possible to execute ad hoc routing algorithms using
only local topology information at the core nodes, QoS routing in
CEDAR is achieved by propagating, in the core, the bandwidth
availability information of stable links. The basic idea is that
the information about stable high-bandwidth links can be made
known to core nodes far away in the network, while information
about dynamic links or low bandwidth links should remain local. By
means of this link state propagation mechanism, CEDAR approximates
Sivakumar, Sinha, Bharghavan [Page 4]
INTERNET-DRAFT CEDAR Specification October 1998
a minimalist local state algorithm in highly dynamic networks
while it approaches the maximalist link state algorithm in highly
stable networks. The propagation of link-state is achieved through
slow-moving 'increase' waves (which denote increase of bandwidth)
and fast-moving 'decrease' waves (which denote decrease of
bandwidth), which traverse the core. The key questions to answer
in link state propagation are: when should an increase/decrease
wave be initiated, how far should a wave propagate, and how fast
should a wave propagate.
3. Route Computation
Route computation first establishes a core path from the domain of
the source to the domain of the destination. This initial phase
involves probing on the core, and the resultant core path is
cached for future use. The core path provides the directionality
of the route from the source to the destination. Using this
directional information, CEDAR iteratively tries to find a partial
route from the source to the domain of the furthest possible node
in the core path (which then becomes the source for the next
iteration) which can satisfy the requested bandwidth, using only
local information. Effectively, the computed route is a
concatenation of the shortest-widest-furthest (the least hop path
among the maximum bandwidth paths) paths found locally using the
core path as the guideline.
Several algorithms have been proposed for routing in ad hoc networks.
The ad hoc routing algorithms proposed in [2,3,4] provide a single
route in response to a route query from a source. Previous work on
tactical packet radio networks had led to many of the fundamental
results in ad hoc networks. [3] has proposed an architecture similar
to the "core" called the linked clusterhead architecture but it uses
gateways for communication between clusterheads and does not attempt
to minimize the size of the core infrastructure. The multipath
routing algorithms proposed in [6,7,8] are more robust than the
single route on demand algorithms, at the cost of higher memory and
message requirements.
2. Network Model
This section describes the network model and the terminology used in
this draft.
Network Model
CEDAR assumes that all the hosts communicate on the same shared
Sivakumar, Sinha, Bharghavan [Page 5]
INTERNET-DRAFT CEDAR Specification October 1998
logical wireless channel. CEDAR assumes that each transmitter has
a fixed transmission range, and that neighborhood is a commutative
property (i.e. if A can hear B, then B can hear A). Because of the
local nature of transmissions, hidden and exposed stations abound
in an ad hoc network. CEDAR assumes the use of a CSMA/CA like
algorithm for reliable unicast communication, and for solving the
problem of hidden/exposed stations. Essentially, data transmission
is preceded by a control packet handoff, and the sequence of
packets exchanged in a communication is the following: RTS (from
sender to receiver) - CTS (from receiver to sender) - Data (from
sender to receiver) - ACK (from receiver to sender). The RTS and
CTS packets avoid collisions from the exposed stations and the
hidden stations respectively. Local broadcasts are not guaranteed
to be reliable (because it is unreasonable to expect a CTS from
every receiver before commencing data transmission), and are
typically quite unreliable due to the presence of hidden and
exposed stations.
CEDAR assumes small to medium networks ranging upto to hundreds of
hosts. For larger networks, we believe that a clustering algorithm
[6] can be used to reduce the cluster size and apply CEDAR
hierarchically within each cluster, for a cluster of clusters,
etc. CEDAR also assumes that mobility and extended fades are the
main causes of link failures and topology changes. We assume that
the change in network topology is frequent, but not frequent
enough to render any sort of route computation useless. Note that
CEDAR only cares about the relative mobility of the hosts, not the
absolute mobility of the hosts. In particular, even if all the
hosts are moving, the ad hoc network would be considered to be
stable so long as the neighborhood of each host does not change.
As in most QoS routing algorithms, CEDAR assumes that the MAC/link
layer can estimate the available link bandwidth. Because all the
hosts in a region share the same channel, each host must share the
link bandwidth with the hosts in its second neighborhood [7]. In
related work on providing QoS in wireless channels, a mechanism is
provided for each host to fairly access a shared channel, and
claim at least B/N bandwidth, where B is the effective channel
bandwidth and N is the number of hosts locally contending for the
bandwidth [8]. This work is currently being extended to ad hoc
networks. While details of bandwidth sharing and estimation are
beyond the scope of this draft, it is assumed that each host can
estimate the available bandwidth of its links using some link-
level mechanisms.
CEDAR assumes a close coordination between the MAC layer and the
routing layer. In particular, it uses the reception of RTS and CTS
control messages at the MAC layer in order to improve the behavior
Sivakumar, Sinha, Bharghavan [Page 6]
INTERNET-DRAFT CEDAR Specification October 1998
of the routing layer, as explained in Section 3.
Finally, bandwidth is the QoS parameter of interest in this draft.
When an application requests a connection, it specifies the
required bandwidth for the connection. The goal of CEDAR is then
to find a short stable route that can satisfy the bandwidth
requirement of the connection.
Graph Terminology
The ad hoc network is represented by means of an undirected graph
G=(V,E), where V is the set of nodes in the graph (hosts in the
network), and E is the set of edges in the graph (links in the
network). The i-th open neighborhood, Ni(x) of node x is the set
of nodes whose distance from x is not greater than i, except node
x itself. The i-th closed neighborhood Ni[x] of node x is N(i) U
{x}.
A dominating set S (a subset of V) is a set such that every node
in V is either in S or is a neighbor of a node in S. A dominating
set with minimum cardinality is called a minimum dominating set
(MDS). A virtual link [u,v] between two nodes in the dominating
set S is a path in G from u to v. The draft uses the term tunnel
interchangeably with virtual link.
Given an MDS Vc of graph G, define a core of the graph C=(Vc, Ec),
where Ec = { [u,v] u in Vc, v in Vc, u in N3(v) } . Thus, the core
graph consists of the MDS nodes Vc, and a set of virtual links
between every two nodes in Vc that are within a distance 3 of each
other in G. Two nodes u and v which have a virtual link [u,v] in
the core are said to be "nearby" nodes.
For a connected graph G, consider any dominating set S. If the
diameter of G is greater than 2, then for each node v in S, there
must be at least one other node of S in N3(v) (otherwise there is
at least one node in G which is neither in S nor has a neighbor in
S). From the definition of the core, if G is connected, then a
core C of G must also be connected (via virtual links).
3. CEDAR Architecture and the Core
This section focuses on the establishment and maintenance of the
core. Briefly, CEDAR extracts the core of the ad hoc network by
approximating the minimum dominating set (MDS) of the ad hoc network.
The nodes in the MDS comprise the core nodes of the network. Each
core node establishes a unicast virtual link (via a tunnel) with
nearby core nodes that are a distance of 3 or less away from it in
the ad hoc network. This guarantees that the core is connected so
Sivakumar, Sinha, Bharghavan [Page 7]
INTERNET-DRAFT CEDAR Specification October 1998
long as the network is connected. The core nodes then collect local
topology information and information about stable high-bandwidth
links far away and perform routing for the nodes in their domain (or
immediate neighborhood). Each node that is not in the core chooses a
core neighbor as its dominator, i.e. the node which performs route
computations on its behalf. The core is merely an infrastructure for
facilitating route computation, and is itself independent of the
routing algorithm. In particular, it is possible to use any of the
well known ad hoc routing algorithms such as DSR [2], LMR [4], TORA
[5], DSDV [9], etc. in the core graph.
In the following subsections, the motivation for choosing a core-
based routing architecture is first described, then a low overhead
mechanism to generate and maintain the core of the network is
presented, and finally an efficient mechanism to accomplish a 'core
broadcast' using local unicast transmissions is described. The core
broadcast is used both for propagation of increase/decrease waves,
and for the establishment of the core path in the route computation
phase.
3a. Rationale for a Core-based Architecture in CEDAR
Many contemporary proposals for ad hoc networking require every
node in the ad hoc network to perform route computations and
topology management [2,6,19,20]. However, CEDAR uses a core-based
infrastructure for QoS routing due to two compelling reasons.
1. QoS route computation involves maintaining local and some
non-local link-state, and monitoring and reacting to some
topology changes. Clearly, it is beneficial to have as few
nodes in the network performing state management and route
computation as possible.
2. Local broadcasts are highly unreliable in ad hoc networks
due to the abundance of hidden and exposed stations. The
problem of local broadcasts in ad hoc networks has also been a
recent subject of discussion in the MANET working group.
Topology information propagation [19,20] and route probes [2,6]
are inevitable in order to establish routes and will, of
necessity, need to be broadcast if every node performs route
computation. On the other hand, if only a core subset of nodes
in the ad hoc network perform route computations, it is
possible to set up reliable unicast channels between nearby
core nodes and accomplish both the topology updates and route
probes much more effectively.
The issues with having only a core subset of nodes performing
Sivakumar, Sinha, Bharghavan [Page 8]
INTERNET-DRAFT CEDAR Specification October 1998
route computations are threefold. First, nodes in the ad hoc
network that do not perform route computation must have easy
access to a nearby core node so that they can quickly request
routes to be setup. Second, the establishment of the core must be
a purely local computation. In particular, no core node must need
to know the topology of the entire core graph. Third, a change in
the network topology may cause a recomputation of the core graph.
Recomputation of the core graph must only occur in the locality of
the topology change, and must not involve a global recomputation
of the core graph. On the other hand, the locally recomputed core
graph must still only comprise of a small number of core nodes -
otherwise the benefit of restricting route computation to a small
core graph is lost.
Sivakumar, Sinha, Bharghavan [Page 9]
INTERNET-DRAFT CEDAR Specification October 1998
o o
| |
| |
o *
/ \ / \
/ \ / \
o----o-----o----o o----*-----*----o
| | | |
o o o o
| | | |
| o | o
| | | |
o----o-----o----o o----*-----*----o
| | | |
| | | |
o-----o o-----o
(a) (b)
o nodes -- link
* core nodes
Figure 1 : (a) The example network (b) The example network with
core nodes chosen
3b. Generation and Maintenance of the Core in CEDAR
Ideally, the core comprises of the nodes in a minimum dominating
set Vc of the ad hoc network G=(V,E). While a greedy algorithm
can be used to generate the best known approximation for the MDS,
CEDAR uses a robust and simple, constant time algorithm which
requires only local computations and generates good approximations
for the MDS in the average case.
Consider a node u, with first open neighborhood N1(u), degree d(u)
= |N1(u)|, dominator dom(u), and effective degree d*(u), where
d*(u) is the number of nodes in the closed neighborhood N1[u], who
have chosen u as their dominator. The core computation algorithm,
which is performed periodically, works as follows at node u.
1. u broadcasts a beacon which contains the following
information pertaining to the core computation:
---------------------------
| u | d*(u) | d(u) | dom(u) |
---------------------------
2. u sets dom(u) <- v, where v is the node in N1[u] with the
Sivakumar, Sinha, Bharghavan [Page 10]
INTERNET-DRAFT CEDAR Specification October 1998
largest value for <d*(v), d(v)>, in lexicographic order. Note
that u may choose itself as the dominator.
3. u then sends v a unicast message including the following
information:
----------------------------------------
| u | {(w, dom(w)) : for all w in N1(u)} |
----------------------------------------
Upon reception of the message, v increments d*(v) if u is not
already in v's dominated list.
4. If d*(u) > 0, then u joins the core.
Essentially, each node that needs to find a dominator selects the
highest degree node with the maximum effective degree in its first
closed neighborhood. Ties are broken by node id.
When a node u joins the core, it issues a 'piggybacked broadcast'
in N3(u). A piggybacked broadcast is accomplished as follows. In
its beacon, u transmits a message:
-----------------------------------
| u | DOM | 3 | path_traversed=null |
-----------------------------------
When node w hears a beacon that contains a message
<u, DOM, i, path_traversed>, it piggybacks the message
----------------------------------
| u | DOM | i-1 | path_traversed+w |
----------------------------------
in its own beacon if (i-1 > 0). Thus, the piggybacked broadcast of
a core node advertises its presence in its third neighborhood. As
mentioned in Section 2, this guarantees that each core node
identifies its nearby core nodes, and can set up virtual links to
these nodes using the path_traversed field in the broadcast
messages. The state that is contained in a core node u is the
following:
1. its nearby core nodes (i.e. the core nodes in N3(u))
2. N*(u), the nodes that it dominates
3. for each node v in N*(u), <forall w in N1(v), <w, dom(w)>>
Thus each core node has enough local topology information to reach
the domain of its nearby nodes and set up virtual links. However,
no core node has knowledge of the core graph. In particular, no
Sivakumar, Sinha, Bharghavan [Page 11]
INTERNET-DRAFT CEDAR Specification October 1998
non-local state needs to be maintained by core nodes for the
construction or maintenance of the core. Note from steps 2 and 4
that over a period of time, the core graph prunes itself because
nodes have a propensity to choose their core neighbor with the
highest effective degree as their dominator. Figure 1 shows an
example network and the corresponding core for the network.
Maintaining the core in the presence of network dynamics is very
simple as the periodic computation of the original core
computation algorithm ensures nomination of an appropriate
dominator for each node that loses connectivity with its dominator
during mobility.
3c. Core Broadcast and its Application to CEDAR
As mentioned earlier, broadcasts do not work well in an ad hoc
network (because of hidden and exposed stations). Hence, CEDAR
uses a unicast based mechanism for achieving a 'core broadcast'.
Note that it is reasonable to assume a unicast based mechanism to
achieve broadcast in the core, because each core node is expected
to have few nearby core nodes. Besides, the core broadcast
mechanism ensures that each core node does not transmit a
broadcast packet to every nearby core node, as described before.
CEDAR uses a close coordination between the medium access layer
and the routing layer in order to achieve efficient core
broadcast.
Recall that a virtual link is a unicast path of length 1, 2, or 3.
Recall also, that CSMA/CA protocols use an RTS-CTS-Data-ACK
handshake sequence to achieve reliable unicast packet
transmission. Our goal is to use the MAC state in order to
achieve efficient core broadcast using O(|V|) messages, where |V|
is the number of nodes in the network.
In order to achieve efficient core broadcast, it is assumed that
each node temporarily caches every RTS and CTS packet that it
hears on the channel for core broadcast packets only. Each core
broadcast message M that is transmitted to a core node i has the
unique tag <M, i>. This tag is put in the RTS and CTS packets of
the core broadcast packet, and is cached for a short period of
time by any node that receives (or overhears) these packets on the
channel. Consider that a core node u has heard a CTS(<M, v>) on
the channel. Then, it estimates that its nearby node v has
received M, and does not forward M to node v. Now suppose that u
and v are a distance 2 apart, and the virtual channel [u,v] passes
through a node w. Since w is a neighbor of v, w hears CTS(<M, v>).
Thus, when u sends a RTS(<M, v>) to w, w sends back a NACK to u.
If u and v are a distance 3 apart, using the same argument there
Sivakumar, Sinha, Bharghavan [Page 12]
INTERNET-DRAFT CEDAR Specification October 1998
will be atmost one extra message. Essentially, the idea is to
monitor the RTS and CTS packets in the channel in order to
discover when the intended receiver of a core broadcast packet has
already received the packet from another node, and suppress the
duplicate transmission of this packet.
o
|
|
*
# \
# \
S o----*#####*----o
# |
# |
# |
# |
# |
o----*#####*----o D
| |
| |
o-----o
S:source; D:destination; #:tunnels used in the core broadcast
Figure 2 : A core broadcast initiated by dom(S) for finding a
route to D
Note that the core broadcast has the following properties:
1. The core nodes do not explicitly maintain a source-based
tree. However, the core broadcast dynamically (and implicitly)
establishes a source-based tree (using the MAC-based broadcast
suppression), which is typically a breadth-first search tree
for the source of the core broadcast.
2. The number of messages is O(|V|) in the worst case, and
O(|Vc|) in the average case. In particular, the only case
extra messages are transmitted is when two nearby core nodes
are a distance 3 apart.
3. Since the trees are not explicitly maintained, different
messages may establish different trees. Likewise, changes in
the network topology do not require any explicit recomputation
of the implicitly generated source tree. However, the
coordination of the MAC layer and the routing layer ensures
Sivakumar, Sinha, Bharghavan [Page 13]
INTERNET-DRAFT CEDAR Specification October 1998
that the core broadcast establishes a tree, and that a core
node typically does not receive duplicates for a core
broadcast.
While the core broadcast in CEDAR has low overhead and adapts
easily to topology changes, the RTS and CTS packets corresponding
to a core broadcast need to be cached for some time after their
reception. Figure 2 illustrates a core broadcast in an example
network. Notice that all tunnels need not be used for core
broadcast, as the core broadcast dynamically establishes a
source-based tree, as mentioned above.
Core broadcast finds applicability in two key aspects of CEDAR:
discovery of the core path, and propagation of increase/decrease
waves. The discovery of the core path is broadcast because the
sender may not know the location of the receiver. It initiates a
core broadcast to find the location of the receiver, and
simultaneously, discover the core path.
4. QoS State Propagation in CEDAR
Section 3 described the core routing infrastructure of CEDAR. Since
each core node uses only the locally cached state to compute the
shortest-widest furthest path along the core path in the route
computation phase, the focus is now turned to the nature of state
that is stored in each core node. At one extreme is the minimalist
approach of only storing local topology information at each core
node. This approach results in a poor routing algorithm (i.e. the
routing algorithm may fail to compute an admissible route even if
such routes exist in the ad hoc network) but has a very low overhead
for dynamic networks. At the other extreme is the maximalist approach
of storing the entire link state of the ad hoc network at each core
node. This approach may compute optimal routes but incurs a high
state management overhead for dynamic networks, and potentially
computes stale routes based on out-of-date cached state when the
network dynamics is high.
The problem with having only local state is that core nodes are
unable to compute good routes in the absence of link-state
information about stable high-bandwidth remote links, while the
problem of having global state is that it is useless to maintain the
link state corresponding to low-bandwidth and highly dynamic links
that are far away because the cached state is likely to be stale
anyway. Fundamentally, each core node needs to have the up-to-date
state about its local topology, and also the link-state corresponding
to relatively stable high-bandwidth links further away. Providing for
such a link-state propagation mechanism ensures that CEDAR approaches
Sivakumar, Sinha, Bharghavan [Page 14]
INTERNET-DRAFT CEDAR Specification October 1998
the minimalist local state algorithm in highly dynamic networks, and
approaches the maximalist link-state algorithm in highly stable
networks. CEDAR achieves the goal of having stability and bandwidth
based link-state propagation using increase and decrease waves, as
described in this section.
In the rest of this section, the draft first describes the mechanics
of the increase and decrease waves, and then answers the three key
questions pertaining to these waves: when should a wave be generated,
how fast should a wave propagate, and how far should a wave
propagate.
4a. Increase and Decrease Waves
For every link l=(a,b), the node b is responsible for monitoring
the available bandwidth on l and informing a of the same if l is
bi-directional. b and a in turn notify their respective
dominators for initiating the increase or decrease waves, when the
bandwidth changes by some threshold value. These waves are then
propagated by the dominators (core nodes) to a subset of core
nodes via core broadcasts. Each core node has two queues: the
"ito-queue" that contains the pending core broadcast messages for
increase waves, and the "dto-queue" that contains the pending core
broadcast messages for decrease waves. For each link l about which
a core node caches link-state, the core node contains the cached
available bandwidth bav(l).
Sivakumar, Sinha, Bharghavan [Page 15]
INTERNET-DRAFT CEDAR Specification October 1998
The following is the sequence of actions for an increase wave:
1. When a new link l=(a,b) comes up, or when the available
bandwidth b(a, b) increases beyond a threshold value, then the
two end-points of l inform their dominators for initiating a
core broadcast for an increase wave:
ito(<a, b, dom(a), dom(b), b(a,b), ttl(b)>)
where ito (increase to) denotes the type of the wave, (a,b)
identifies the link, dom(a) denotes the dominator of a, dom(b)
denotes the dominator of b, b(a, b) denotes the available
bandwidth on the link, and ttl(b) is a 'time-to-live' field
that denotes the maximum distance to which this wave can be
propagated as an increase wave. The ids of the dominators of
the link end-points are required by the routing algorithm.
ttl(b) is an increasing function of the available bandwidth, as
described in Section 4c.
2. When a core node u receives an ito wave
ito(<a, b, dom(a), dom(b), b(a, b), ttl>),
1 if u has no state cached for (a,b),
2 bav(a,b) <- b(a,b)
3 if (ttl > 0), then add the following message
to the ito-queue:
4 ito(<a, b, dom(a), dom(b), b(a,b), ttl - 1>)
5 else if u has cached state for (a,b) and (ttl > 0),
6 if (bav(a,b) < b(a,b))
7 bav(a,b) <- b(a,b)
8 delete any pending ito/dto message for (a,b) from the
9 ito-queue and dto-queue.
10 add the following message to the ito-queue:
11 ito(<a, b, dom(a), dom(b), b(a,b), ttl - 1>)
12 else if (bav(a,b) > b(a,b)),
13 bav(a,b) <- b(a,b)
14 delete any pending ito/dto message for (a,b) from the
15 ito-queue and dto-queue.
16 add the following message to the dto-queue:
17 dto(<a, b, dom(a), dom(b), b(a,b), ttl - 1>)
18 else if u has cached state for (a,b) and (ttl = 0),
19 bav(a,b) <- b(a,b)
20 delete any pending ito/dto message for (a,b) from the
ito-queue and dto-queue.
21 add the following message to the dto-queue:
22 dto(<a, b, dom(a), dom(b), 0, infinity>)
Sivakumar, Sinha, Bharghavan [Page 16]
INTERNET-DRAFT CEDAR Specification October 1998
The ito-queue and the dto-queues are flushed periodically,
depending on the speed of propagation of the increase/decrease
waves.
The following is the sequence of actions for a decrease wave:
1. When a link l=(a,b) goes down, or when the available
bandwidth b(a, b) decreases beyond a threshold value, then the
two end-points of l inform their dominators for initiating a
core broadcast for a decrease wave:
dto(<a, b, dom(a), dom(b), b(a,b), ttl(b)>),
where dto (decrease to) denotes the type of the wave, and the
other parameters are as defined before.
2. When a core node u receives a dto wave
dto(<a, b, dom(a), dom(b), b(a,b), ttl>),
1 if u has no state cached for (a,b) and (b(a,b) = 0),
2 the wave is killed.
3 else if u has no state cached for (a,b) and (b(a,b) > 0),
4 bav(a,b) <- b(a,b)
5 if (ttl > 0), then add the following message
to the ito-queue:
6 ito(<a, b, dom(a), dom(b), b(a,b), ttl - 1>)
7 else if u has cached state for (a,b) and (ttl > 0),
8 if (bav(a,b) < b(a,b)),
9 bav(a,b) <- b(a,b)
10 delete any pending ito/dto message for (a,b) from the
11 ito-queue and dto-queue.
12 add ito(<a, b, dom(a), dom(b), b(a,b), ttl - 1>) to
13 the ito-queue.
14 else if (bav(a,b) > b(a,b)),
15 bav(a,b) <- b(a,b)
16 delete any pending ito/dto message for (a,b) from the
17 ito-queue and dto-queue.
18 add the following message to the dto-queue.
19 dto(<a, b, dom(a), dom(b), b(a,b), ttl - 1>)
20 else if u has cached state for (a,b) and (ttl = 0),
21 bav(a,b) <- b(a,b)
22 delete any pending ito/dto message for (a,b) from the
23 ito-queue and dto-queue.
24 add the following message to the dto-queue.
25 dto(<a, b, dom(a), dom(b), 0, infinity>)
There are several key points in the above algorithm. First, the
Sivakumar, Sinha, Bharghavan [Page 17]
INTERNET-DRAFT CEDAR Specification October 1998
way that the ito-queue and the dto-queue are flushed ensures that
the decrease waves propagate much faster than the increase waves
and suppress state propagation for unstable links. Second, waves
are converted between ito and dto on-the-fly, depending on whether
the cached value for the available bandwidth is lesser than the
new update (ito wave generated) or not (dto wave generated).
Third, after a distance of ttl (which depends on the current
available bandwidth of the link), the dto(<a, b, dom(a), dom(b),
0, infinity>) message ensures that all other core nodes which had
state cached for this link now destroy that state. However, the
dto(<a, b, dom(a), dom(b), 0, infinity>) wave does not propagate
throughout the network - it is suppressed as soon as it hits the
core nodes which do not have link state for (a,b) cached (line 2
in decrease wave propagation). The increase/decrease waves use the
efficient core broadcast mechanism for propagation. Figure 3
illustrates a decrease wave cancelling a previously generated
increase wave for a link l.
^
|
|
| increase wave
^ | nullified
| | + -
| | + -
| + -
# of hops | + -
from | + -
l | + -
| + -
| + -
| + -
| + -
| + -
| + -
-|----X-----------------X---------------->
| increase wave decrease wave
| for l generated for l generated
time ->
Figure 3 : A decrease wave cancelling an increase wave for l
Essentially, the above algorithm ensures that the link-state
information for stable high-bandwidth links gets propagated
throughout the core, while the link-state information for unstable
and low-bandwidth links remains local - which is the goal of the
CEDAR state propagation algorithm.
Sivakumar, Sinha, Bharghavan [Page 18]
INTERNET-DRAFT CEDAR Specification October 1998
4b. Issues in link state propagation
In this subsection, the three key questions pertaining to the
propagation of increase/decrease waves are discussed: when should
a wave be generated, how fast should a wave propagate, and how far
should a wave propagate.
When is a wave generated ?
To avoid a large overhead, CEDAR generates waves only when the
bandwidth has changed by some threshold value. We suggest the
use of a constant threshold when the bandwidth request sizes
are comparable to the available bandwidth and a logarithmic
scale [10] for the threshold when the typical request sizes are
an order of a magnitude less than the available bandwidths. The
advantage of the logarithmic update is that it does not
wastefully generate increase/decrease waves when the change in
link capacity is unlikely to alter the probability of computing
admissible routes. Further work is needed to substantiate the
above heuristics.
How Far does a Increase/Decrease Wave Propagate?
The goal is to propagate link bandwidth information to a number
of nodes that is proportional to the amount of bandwidth being
propagated. The motivation for this approach is the fact that
every node that has knowledge about a particular link would
potentially contend for the link, and a higher percentage of
requests can be satisfied if the contention on a link is
proportional to its bandwidth. Hence we suggest that the
maximum distance that the link state travels (time to live -
ttl) be an increasing function of the available bandwidth of
the link. Although the current CEDAR simulation uses a linear
function of the available bandwidth for computing the ttl, a
fluid model analysis of an ad hoc network suggests that in
general, the ttl should be a function of b^(1/k), where k is a
small number between 1 and 3.
How Fast does a Increase/Decrease Wave Propagate?
An increase wave waits for a fixed timeout period (which is a
system parameter that should be approximately twice the
expected inter-arrival time between the generation of two
successive waves for any link in the network) at each node
before being forwarded to its neighbors (using the core
broadcast). Thus, increase waves propagate slowly. A decrease
wave is immediately forwarded to its neighbors (using the core
broadcast). Thus decrease waves move much faster and can kill
Sivakumar, Sinha, Bharghavan [Page 19]
INTERNET-DRAFT CEDAR Specification October 1998
increase waves for unstable links.
5. QoS Routing in CEDAR
The previous two sections have described the core infrastructure
(i.e. which nodes in the ad hoc network perform route computation and
how they communicate among themselves) and the state propagation
algorithm (i.e. what state does each core node contain). This
section completes the description of CEDAR by specifying how the core
nodes use the state information to compute QoS routes.
The QoS route computation in CEDAR consists of three key components:
(a) discovery of the location of the destination and establishment of
the core path to the destination, (b) establishment of a short stable
admissible QoS route from the source to the destination using the
core path as a directional guideline, and (c) dynamic re-
establishment of routes for ongoing connections upon link failures
and topology changes in the ad hoc network.
5a. Establishment of the Core Path
The establishment of a core path takes place when s requests
dom(s) to set up a route to d, and dom(s) does not know the
identity of dom(d) or does not have a core path to dom(d).
Establishment of a core path consists of the following steps.
1. dom(s) initiates a core broadcast to set up a core path with
the following message: <core_path_req, dom(s), d, b, P = null>.
2. When a core node u receives the core path request message
<core_path_req, dom(s), d, b, P>, it appends u to P, and
forwards the message to each of its nearby core nodes
(according to the core broadcast algorithm) to whose domain
there exists atleast one path (from u's domain) satisfying
bandwidth b.
3. When dom(t) receives the core path request message
<core_path_req, dom(s), d, b, P>, it sends back a source rooted
unicast core_path_ack message to dom(s) along the inverse path
recorded in P. The response message also contains P, the core
path from dom(s) to dom(d).
Upon reception of the core_path_ack message from dom(d), dom(s)
completes the core path establishment phase and enters the QoS
route computation phase.
Note that by virtue of the core broadcast algorithm, the core path
Sivakumar, Sinha, Bharghavan [Page 20]
INTERNET-DRAFT CEDAR Specification October 1998
request traverses an implicitly (and dynamically) established
source routed tree from dom(s) which is typically a breadth-first
search tree. Thus, the core path is approximately the shortest
admissible path in the core graph from dom(s) to dom(d), and hence
provides a good directional guideline for the QoS route
computation phase. Figure 4 shows an example for a core path. The
example assumes that the link marked with 0.5 has an available
bandwidth of 0.5 units, whereas all other links have 1 unit of
bandwidth available. The route request has a QoS requirement of 1
unit.
Sivakumar, Sinha, Bharghavan [Page 21]
INTERNET-DRAFT CEDAR Specification October 1998
o
|
|1
*
1 / \ 1
1 / \ 1
S o----*-----*----o
+ |
+ |
1 + | 1
+ |
1 + 0.5 | 1
o----*+++++*----o D
| |
1 | | 1
o-----o 1
+ core path S source D destination
Figure 4 : Core path from dom(S) to dom(D)
5b. QoS Route Computation
After the core path establishment, dom(s) knows dom(d) and the
core path from dom(s) to dom(d). Recall from Section 3 that dom(s)
has the local topology - which includes all the nodes in its
domain, and for each dominated node u, the bandwidth of each link
incident on u, the adjacency list of u and the dominator of each
of the neighbors of u. Recall from Section 4 that dom(s) has the
information gathered about remote links through increase/decrease
waves, and for each such link (u, v), the bandwidth of (u,v),
dom(u), and dom(v). dom(s) thus has a partial knowledge of the ad
hoc network topology, which consists of the up-to-date local
topology, and some possibly out-of-date information about remote
stable high-bandwidth links in the network. The following is the
sequence of events in QoS route computation.
1. Using the local topology, dom(s) tries to find a path from s
to the domain of the furthest possible core node in the core
path (say dom(t)) that can provide at least a bandwidth of b
(bandwidth of the connection request). The bandwidth that can
be provided on a path is the minimum of the individual
available link bandwidths that comprise the path.
2. Among all the admissible paths (known using local state) to
the domain of the furthest possible core node in the core path,
dom(s) picks the shortest-widest path using a two phase
Dijkstra's algorithm [11]. The first phase is used to find the
Sivakumar, Sinha, Bharghavan [Page 22]
INTERNET-DRAFT CEDAR Specification October 1998
available bandwidth B of the widest path. In the subsequent
phase, links with available bandwidth less than B are
eliminated before computing the shortest path in the resulting
graph.
3. Let t be the end point of the chosen path and p(s, t) denote
the path. dom(s) sends dom(t) the following message: < s, d,
b, P, p(s, t), dom(s), t>, where s, d, and t are the source,
destination, and intermediate node in the partially computed
path, b is the required bandwidth, P is the core path, and p(s,
t) is the partial path.
4. dom(t) then performs the QoS route computation using its
local state identical to the computation described above.
5. Eventually, either there is an admissible path to d or the
local route computation will fail to produce a path at some
core node. The concatenation of the partial paths computed by
the core nodes provides an end-to-end path that can satisfy the
bandwidth requirement of the connection with high probability.
Figure 5 shows how the core path found in Figure 4 is used to
find a QoS route satisfying the 1 unit bandwidth request. As
mentioned earlier, all links except the one indicated with 0.5,
have an available bandwidth of 1 unit. This example also
illustrates that the QoS route found in CEDAR can be non-
optimal as it uses a core path as the guiding direction (the
path along the core has 7 hops whereas there is another
feasible path - not along the chosen core path - with 6 hops).
The core path is computed in one round trip, and the QoS route
computation algorithm also takes one round trip. Thus, the route
discovery and computation algorithms together take two round trips
if the core path is not cached and one round trip otherwise.
Note that while the QoS route is being computed, packets may be
sent from s to d using the core path. The core path thus provides
a simple backup route while the primary route is being computed.
Sivakumar, Sinha, Bharghavan [Page 23]
INTERNET-DRAFT CEDAR Specification October 1998
o
|
|
*
/ \
/ \
S o....*-----*----o
: |
o o
: |
: o
: 0.5 |
o----*-----*....o D
: :
: :
o.....o
Figure 5 : QoS route from S to D satisfying a bandwidth
requirement of 1 unit.
5c. Dynamic QoS Route Recomputation for Ongoing Connections
Route recomputations may be required for ongoing connections under
two circumstances: the end host moves, and there is some
intermediate link failure (possibly caused by the mobility of an
intermediate router or by a reduction in available bandwidth on
that link such that the connection can no longer be served). End
host mobility can be thought of as a special case of link failure,
wherein the last link fails.
CEDAR has two mechanisms to deal with link failures and reduce the
impact of failures on ongoing flows: dynamic recomputation of an
admissible route from the point of failure, and notification back
to the source for source-initiated route recomputation. These two
mechanisms work in concert and enable us to provide seamless
mobility.
1. QoS Route Recomputation at the Failure Point: Consider that
a link (u, v) fails on the path of an ongoing connection from s
to t. The node nearest to the sender, u, then initiates a local
route recomputation similar to the algorithm in Section 5b.
Once the route is recomputed, u updates the source route in all
packets from s to t accordingly. If the link failure happens
near the destination, then dynamic route recomputation at the
intermediate node works very well because the route
recomputation time to the destination is expected to be small,
and packets in-flight are re-routed seamlessly.
Sivakumar, Sinha, Bharghavan [Page 24]
INTERNET-DRAFT CEDAR Specification October 1998
2. QoS Route Recomputation at the Source: Consider that a link
(u, v) fails on the path of an ongoing connection from s to t.
The node nearest to the sender, u, then notifies s that the
link (u, v) has failed. Upon receiving the notification, u
stops its packet transmission, initiates a QoS route
computation as in Section 5b, and resumes transmission upon
the successful re-establishment of an admissible route. If the
link failure happens near the source, then source-initiated
recomputation is effective, because the source can quickly
receive the link-failure notification and temporarily stop
transmission.
The combination of these two mechanisms is effective in supporting
seamless communication inspite of mobility and dynamic topology
changes. Basically, CEDAR uses source-initiated recomputation as
the long-term solution to handling link failure, while the short-
term solution to handle packets in-flight is through the dynamic
recomputation of routes from the intermediate nodes. Recomputation
at the failure point is not really effective if the failure
happens close to the source, but in this case, the number of
packets in flight from s to u is small.
6. Performance Results
We have evaluated the performance of CEDAR via both implementation
and simulation. Our implementation consists of a small ad hoc network
consisting of six mobile nodes that use Photonics (Data Technology) 1
Mbps infrared network. We have customized the Linux 2.0.31 kernel to
build our ad hoc network environment (written partly in user mode and
partly in kernel mode). While the testbed shows proof of concept and
has exposed some difficulties in implementing CEDAR, our detailed
performance evaluation [12] has been using a simulator that
faithfully implements the CEDAR algorithms.
While the entire gamut of results obtained from the tests are not
presented due to space constraints, the rest of this section briefly
summarizes the performance of CEDAR as observed from these tests. For
tests in a best-effort environment we assume the optimal performance
to be the performance of a global algorithm that does shortest path
computation, while in a QoS environment we assume this to be the
performance of a global algorithm doing a shortest widest path
computation. The metrics used for comparison in these results are:
(i) stretch - the ratio of the number of hops in a route computed by
CEDAR to the number of hops in a route computed by the global
algorithm, (ii) bandwidth - the ratio of bandwidth available on the
routes computed by CEDAR to that of the global algorithm, (iii)
message complexity, (iv) time complexity and (v) crankbacks - the
ratio of the number of rejects to the number of connection requests.
Sivakumar, Sinha, Bharghavan [Page 25]
INTERNET-DRAFT CEDAR Specification October 1998
In a best-effort environment, CEDAR performs reasonably well before
the introduction of ito/dto waves, and progressively converges to a
near optimal performance once these waves are introduced. In
particular, for dynamic networks we observed a stretch of around 1.2
before the waves were introduced. The stretch came down to 1.1 once
the waves were introduced. For stable networks, the stretch observed
was 1. Additionally, the message and time complexities of CEDAR were
also comparable to the optimal performance [12].
In a QoS environment, CEDAR was compared to the optimal algorithm in
terms of the number of hops and the bandwidth available on the
computed path. In terms of bandwidth, CEDAR's performance was worse
than the optimal performance by an average of 3%. For the number of
hops on the computed path, CEDAR in fact performed better in some
cases (the global algorithm could pick a longer path with a higher
bandwidth). When the number of crank-backs was observed in these
tests, CEDAR had 30% more crank-backs than the optimal algorithm
before the introduction of waves, while after the introduction of
ito/dto waves, the number of crank-backs were the same in both CEDAR
and the optimal algorithm.
For detailed performance results, please refer to [12].
7. Conclusions
This draft presents CEDAR, a core-Extraction Distributed Ad hoc
Routing algorithm for providing QoS in ad hoc network environments.
CEDAR has three key components: (a) the establishment and
maintenance of a self-organizing routing infrastructure, called
the "core", for performing route computations, (b) the
propagation of the link-state of stable high-bandwidth links in the
core through "increase/decrease" waves, and (c) a QoS route
computation algorithm that is executed at the core nodes using only
locally available state. While the core provides an efficient and
low-overhead infrastructure to perform routing and broadcasts in an
ad hoc network, the increase/decrease wave based state propagation
mechanism ensures that the core nodes have the important link-state
they need for route computation without incurring the high overhead
of state maintenance for dynamic links. The QoS routing algorithm is
robust and uses only local state for route computation at each core
node.
CEDAR is a robust and adaptive algorithm that reacts quickly and
efficiently to the dynamics of the network while still approximating
link-state performance for stable networks. Our simulations show that
CEDAR produces good stable admissible routes with a high probability
if such routes exist. Furthermore, CEDAR does not require high
maintenance overhead even for highly dynamic networks. Ongoing work
Sivakumar, Sinha, Bharghavan [Page 26]
INTERNET-DRAFT CEDAR Specification October 1998
on CEDAR is focusing on three areas. (a) While it is shown that CEDAR
is effective for small to medium size networks, work is being done on
a hierarchically clustered version of CEDAR that can provide QoS
routing in large ad hoc networks. (b) While this draft has only
considered bandwidth as the QoS parameter in this work, current work
is extending CEDAR to include delay as a QoS parameter and (c) The
heuristics mentioned in Section 4 need more study and are in the
process of being refined.
8. References
[1] R. Nair, B. Rajagopalan, H. Sandick, and E. Crawley. "A
framework for QoS-based routing in the Internet." Internet
Draft draft-ietf-qosr-framework-05.txt, May 1998.
[2] D. B. Johnson and D. A. Maltz. "Dynamic source routing in ad
hoc wireless networks". In Mobile Computing, (ed. T. Imielinski
and H. Korth), Kluwer Academic Publishers, 1996.
[3] A. Ephremides, J. E. Wieselthier, and D. J. Baker. "A design
concept for reliable mobile radio networks with frequency
hopping signaling". In Proceedings of the IEEE, pages 56--73,
January 1987.
[4] M. S. Corson and A. Ephremides. "A highly adaptive distributed
routing algorithm for mobile wireless networks". ACM/Baltzer
Wireless Networks Journal, 1(1):61--81, February 1995.
[5] V. D. Park and M. S. Corson. "A highly adaptive distributed
routing algorithm for mobile wireless networks". In Proceedings
of 1997 IEEE Conference on Computer Communications, April 1997.
[6] R. Sivakumar, B. Das, and V. Bharghavan. "Spine routing in ad
hoc networks". ACM/Baltzer Cluster Computing Journal (special
issue on Mobile Computing). To appear, 1998.
[7] V. Bharghavan, S. Shenker A. Demers, and L. Zhang. "MACAW: A
medium access protocol for wireless LANs". In Proceedings of
ACM SIGCOMM}, London, England, August 1994.
Sivakumar, Sinha, Bharghavan [Page 27]
INTERNET-DRAFT CEDAR Specification October 1998
[8] S. Lu, V. Bharghavan, and R. Srikant. "Fair queuing in wireless
packet networks". In Proceedings of ACM SIGCOMM '97, Cannes,
France, September 1997.
[9] C. E. Perkins and P. Bhagwat. "Highly dynamic destination-
sequenced distance-vector routing (DSDV) for mobile computers".
In Proceedings of ACM SIGCOMM, pages 234--244, London, England,
August 1994.
[10] B. Awerbuch, Yi Du, B. Khan, and Y. Shavitt. "Routing through
networks with topology aggregation". In IEEE Symposium on
Computers and Communications, Athens, Greece, June 1998.
[11] Q. Ma and P. Steenkiste. "On path selection for traffic with
bandwidth guarantees". In Proceedings of Fifth IEEE
International Conference on Network Protocols, Atlanta, October
1997.
[12] R. Sivakumar, P. Sinha and V. Bharghavan. "CEDAR: a Core-
Extraction Distributed Ad hoc Routing algorithm". TIMELY Group
Technical Report,http://www.timely.crhc.uiuc.edu/Papers/cedar.ps
9. Author's Addresses
Raghupathy Sivakumar
458 C&SRL, Coordinated Science Lab
University of Illinois, Urbana-Champaign
1308 W. Main St., Urbana, IL 61801
USA
Email: sivakumr@timely.crhc.uiuc.edu
Prasun Sinha
458 C&SRL, Coordinated Science Lab
University of Illinois, Urbana-Champaign
1308 W. Main St., Urbana, IL 61801
USA
Email: prasun@timely.crhc.uiuc.edu
Vaduvur Bharghavan
457 C&SRL, Coordinated Science Lab
University of Illinois, Urbana-Champaign
1308 W. Main St., Urbana, IL 61801
USA
Email: bharghav@timely.crhc.uiuc.edu
Sivakumar, Sinha, Bharghavan [Page 28]
INTERNET-DRAFT CEDAR Specification October 1998
Sivakumar, Sinha, Bharghavan [Page 29]
