CEDAR
The Core Extraction Distributed Ad Hoc routing Protocol (CEDAR) presented in [
Sinha1999] is a hierarchical routing approach. A set of nodes called the core tries to maintain stable high-bandwidth links. The selection of routes is done with the consideration of the quality of service a link could provide.
It is assumed that the link-level protol of the communication between the nodes is reliable and that the nodes can estimate the available bandwidth of links. The core nodes which are dominators of normal nodes do the route compution for the lins with other core nodes on behalf of the nodes they dominate. A core computation algorithm is triggered periodically to elect the core nodes.
Core computation
-
a node u broadcasts a beacon which contains the following info:
-
u, the nopdes id
-
d*(u) the effective degree, this is the number of neighbours which u is a dominator for
-
d(u) the degree of u (number of its direct neighbours
-
dom(u) the dominator node of u (maybe itself)
-
u sets dom(u) to be v to be the highest value of <d*(v),d(v)> in lexicographical order. A node u may also choose itself as a dominator.
-
u then sends v (its dominator) an unicast message containing its id and the ids and the dominators of its immediate neighbours. v then increments d*(v)
-
if d*(u) finally is >0 u joins the core of the network.
When a node joins the core it advertises itself to the other nodes in the third neighborhood. This is done by a hop counter in the message which is initially set to three and decremented at the nodes which propagate the message. To identify the route between core nodes and to prevent multiple propagation of the advertisement message an array of the ideas of the nodes whcih have propagated the message is contained in the message. So the core nodes know the routes of the other core nodes which are thus at most 3 hops away.
Core broadcast
The communication between core nodes is unicast over at most 3 hops and those links are called virtual links. Because unicast is a feature of the medium acces mechanism, the (physically) broadcast between core nodes has to be obtimized in order to limit the waste of messages. This is done by tagging the broadcast RTS/CTS-messages with a message id and a node id. Nodes hearing these link-layer messages cache the tags of the messages for a short period of time in order to avoid duplicate transmission of a message when a message already has reached the destination through another node.
QOS routing
Only the core nodes do route computation by maintaining link state information. It would be impractical for the core nodes to store information about the whole network topology. Instead only link state about reliable high-bandwidth far-away links are maintained and of course also the whole local link state in the domain of a dominator.
This is achieved by so called "increase- and decrease-waves". To make sure that the link state of more remote places in the network which can not guarantee a high bandwidth does not propagate too far away, the messages describing an increase of bandwidth are "travelling" slower than the messages about a decrease of bandwidth. This way only information about stable high-bandwidth links are propagated further in the network.
Every core node maintains to queues for core broadcasting increase and decrease waves. Every node which has a link to another node monitors the available bandwidth for that link. If a link comes up, or the bandwidth across that link increases over a given threshold, the node informs its dominator to generate an increase wave to broadcast.
The core sends an "increase to" ito message containing the nodes ids of the endpoints of the links, their dominating nodes, the available bandwidth of the link and a time-to-live value which indicates how far this wave is allowed to be propagated. The ttl value is a function of the available bandwidth.
When a core node receives an increase message it either:
-
discards the message if the node has no link state cached for the endpoints and the bandwith of the endpoints is 0
-
if it has no state cached for the link and the bandwith is greater than 0 and the ttl is not null, it decreases the ttl and appends the message to its ito-queue
-
if the core node has cached state for the link in its tables and ttl > 0 it immediately deletes all his pending messages in both the ito and dto (decrease-to) queues. Then: If the bandwidth of the message it received is bigger than the bandwidth of the cached state it sends an increase message to the ito-queue with ttl decreased by one. Else if it is smaller it sends a decrease message to the dto-queue with ttl-1.
-
if the core node has cahed state for the link of the received message and the messages time-to-live has reached 0. The node deletes any pending messages for the link in both queues and appends a dto-message to the dto queue with ttl set to infinity and bandwith of the link set to 0.The ito-queue is flushed periodically, the time being dependant on the rate of increase-messages.
The decrease-to messages are processed analogously to the ito-messages with the important difference that the dto-queue is flushed as there are packets in the queue.
The above described method ensures that link state is erased when the bandwidth becomes zero through the infinite ttl of the decrease message with bandwidth 0. It also ensures that link state information doesn't travel too far down the network through the introduciton of the ttl parameter. It finally ensures that messages about decreasing bandwith are privileged versus messages about increasing bandwidth which allows secure erasure of invalid links through the unequal intervals with which the queues are flushed.
Route computation
A core node has only partial knowledge about the network topology. Local topology knowledge is complete and knowledge about more far away high-bandwidth links may be outdated. A core node which needs a route tries to reach the furthest away core node on the shortest-widest path (computed by a two phsae
Dijkstra algorithm). The furthest away core node also does a similar route computation. The path along the route is recorded in an array and the path from core node to core node are concatenated to form the final path (see source routing)
References
[
Sivakumar1998] Original internet-draft
[
Sinha1999] Original paper
[
Sivakumar1999] Original journal
