CEDAR
This draft presents CEDAR,a Core-Extraction Distributed Ad hoc Routingalgorithm for QoS routing in ad hoc network environments. CEDAR hasthree key components: (a) the establishment and maintenance of aself-organizing routing infrastructure, called the "core", forperforming route computations, (b) the propagation of the link-stateof stable high-bandwidth links in the core through "increase/decrease"waves, and (c) a QoS route computation algorithm that is executed atthe core nodes using only locally available state.
1. Establishment and Maintenance of a core using Local Core Extraction
CEDAR does core extraction in order to extract a subset of nodes inthe network that would be the only ones that perform state managementand route computation. The core extraction is done dynamically byapproximating a minimum dominating set of the ad hoc network usingonly local computation and local state.The core computation and coremanagement upon change in the network topology are purely localcomputations to enable the core to adapt efficiently to the dynamicsof the network.
2. Link State Propagation using Increase/Decrease waves
While it is possible to execute ad hoc routing algorithms using onlylocal topology information at the core nodes, QoS routing in CEDAR isachieved by propagating, in the core, the bandwidth availabilityinformation of stable links. The basic idea is that the informationabout stable high-bandwidth links can be made known to core nodes faraway in the network, while information about dynamic links or lowbandwidth links should remain local. The key questions to answer in link state propagation are: when should an increase/decrease wave beinitiated, how far should a wave propagate, and how fast should a wavepropagate.
3. Route Computation
Route computation first establishes a core path from the domain of thesource to the domain of the destination. This initial phase involvesprobing on the core, and the resultant core path is cached for futureuse. The core path provides the directionality of the route from thesource to the destination. Using this directional information, CEDARiteratively tries to find a partial route from the source to thedomain of the furthest possible node in the core path.
Artikeln skriven 2009-01-18 av Learning4sharing
Inga kategorier för denna artikel än...Intresserad av fler artiklar?
CESTStepp
Cert
CET
Centralförbundet för befälsutbildning
CFO
CFD
CGA
Cap Gemini Ernst & Young