An Efficient Path Selection Algorithm for On-Demand Link-State Hop-by-Hop Routing

An Efficient Path Selection Algorithm for On-Demand Link-State Hop-by-Hop Routing

5 Pages · 2006 · 91 KB · English

mation on-demand and on hop-by-hop packet forwarding. REFERENCES. [1] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad-Hoc. Wireless Networks,” Mobile Computing, 1994. [2] C. E. Perkins and E. M. Royer, “Ad Hoc On-Demand Distance Vector. Routing,” in Proc. of IEEE WMCSA'99 

An Efficient Path Selection Algorithm for On-Demand Link-State Hop-by-Hop Routing free download


An Efcient Path Selection Algorithm for OnDemand LinkState HopbyHop Routing Soumya Roy and JJGarciaLunaAceves Computer Engineering Department University of California Santa Cruz, CA 95064 soumya, [email protected] Abstract— Traditional routing protocols based on linkstate information form a network topology through the exchange of linkstate infor mation by ooding or by reporting partial topology information and compute shortest routes to each reachable destination using a pathselection algorithm like Dijkstra's algorithm or the Bellman Ford algorithm However, in an ondemand linkstate routing pro tocol, no one node needs to know the paths to every other node in the network Accordingly, when a node chooses a next hop for a given destination, it must be true that the next hop has reported a path to the same destination; otherwise, packets sent through that node would be dropped In this paper, we present a new pathselection algorithm that unlike traditional shortest path algo rithms, computes shortest paths with the above ondemand rout ing constraint I I NTRODUCTION To minimize control overhead in mobile adhoc networks, ondemand routing protocols (eg, dynamic source routing (DSR) [1], adhoc ondemand distance vector (AODV) [2] rout ing, temporally ordered routing algorithm (TORA) [3], source tree ondemand adaptive routing(SOAR) [4])) maintain paths to only those destinations to which data must be sent and the paths to such destinations need not be optimum In linkstate routing protocols meant for mobile adhoc net works, partial linkstate information can be used for computa tion of paths to destinations, because all nodes need not have to compute paths to every other destination Hence, each node may not know how to reach every other node in the network, even when all nodes remain connected For correct hopbyhop routing, every node that receives a data packet for forwarding should have a correct route for the destination Therefore, while computing routes, a node should be allowed to choose a neigh bor as the next hop for certain destinations only if that neighbor has advertised routes for those destinations; otherwise, packet forwarding would be incorrect Unfortunately, the Bellman Ford algorithm or Dijkstra's algorithm do not place any con straint for the computation of routes, and new path selection algorithms are needed to account for the ondemand routing constraint In this paper, we present such a new path selection This work was supported in part by the Defense Research Projects Agency (DARPA) under grant F306029720338 and by the US Air Force/OSR under grant F496200010330 algorithm that computes shortest paths with ondemand routing constraint Section II describes how the path selection algorithm should be specied for ondemand linkstate routing protocols Sec tion III describes the details of the path selection algorithm Section IV proves that the given path selection algorithm is correct, ie it correctly computes the best path to reach any destination under the ondemand routing constraint Section V concludes the paper II P AT H SELECTION FOR OND EMAND LINK STAT E ROUTING acef bdgh (c) (c) (c) (c) (c) (b) (b) (c) (b) Fig 1 Example explaining the requirements of a new path selection algorithm for routing protocols using linkstate information ondemand Considerable effort has been devoted for using distance vector information or pathvector ondemand (eg, AODV [2], DST [5], DSR [1]), but not much work has been done exploring the use of linksate information ondemand in routing Most of the linkstate routing protocols that have been devised for mo bile adhoc networks are proactive, like OLSR [6], STAR [7], FSR [8], TBRPF [9] while the source tree ondemand adaptive routing (SOAR) [4] is the only protocol reported to date that uses linkstate information ondemand The key idea in SOAR is for wireless routers to exchange minimal source trees, consisting of the state of the links that are in the paths used by the routers to reach onlyimportant destinations Important destinations are active receivers of data packets, relays, or possible relays Minimal source trees can be reported incrementally or atomically, and updates to individual links in source trees are validated using sequence numbers A wireless router uses its outgoing links and the minimal source trees received from its neighbors to get a partial view of the Report Documentation Page Form Approved OMB No 07040188 Public reporting

------------- Read More -------------

Download an-efficient-path-selection-algorithm-for-on-demand-link-state-hop-by-hop-routing.pdf

An Efficient Path Selection Algorithm for On-Demand Link-State Hop-by-Hop Routing related documents

DEPARTMENT of HEALTH and HUMAN - Centers for Disease Control and

507 Pages · 2008 · 6.61 MB · English

influenza, natural disasters, and terrorism, while remaining focused on the threats to health and local, tribal and territorial health network.

Solving Equations by Steepest Descent

4 Pages · 2008 · 62 KB ·

At the minimum, which we call y0, the gradient has to vanish which means that Ay0 = b and hence y0 is the solution. Example. Lets take A be the 2 × 2 

Morgan State University

49 Pages · 2013 · 503 KB ·

state and the special needs of Baltimore City Executive Assistant to the President, and Associate and Assistant Vice Presidents. Persons appointed to academic administrative positions serve at the pleasure of the The immediate supervisor shall record occurrences of sick leave used because of.

Interpreting sloppy stick figures by graph rectification and

14 Pages · 2001 · 822 KB · English

1 Interpreting sloppy stick figures by graph rectification and constraint-based matching. James V. Mahoney and Markus P. J. Fromherz Xerox Palo Alto Research Center

International Student Guide for Employment in the US

19 Pages · 2012 · 741 KB · English

Problem- If you do not speak English as a native language, you are at a distinct disadvantage communicating with recruiters. Solution- Consciously make an effort to talk with Americans: • Make presentations, take English courses, and work tirelessly at improving your English skills. • Ask a fel

Binders for radioactive waste forms made from pretreated calcined sodium bearing waste

8 Pages · 2006 · 187 KB ·

Although calcination of the pretreated SBW produces a instance metakaolin mixed with NaOH proved to be a superior binder for solidification.

The European Car Parking Sector Sees M&A Flurry, But Will It Be An Easy Ride For Investors?

11 Pages · 2017 · 813 KB · English

The European Car Parking Sector Sees M&A Flurry, But Will It Be An Easy Ride For Investors? spglobal.com/ratingsdirect. Dec. 6, 2017. 2. Despite lots of M&A activity in the. European car parking sector, the future is somewhat uncertain. Acquisitions are the major growth catalyst for operators, but

An integrated approach to product design and process selection

48 Pages · 2011 · 2.15 MB ·

Narayan Raman .. M? < Bs% .. a geometric series given by TEMP(y) = r * TEMP(

2) Install Mac OS X 10.6 Snow Leopard on the new partition

1 Pages · 2011 · 9 KB · English

1) Create a partition for Mac OS X Lion Download Mac OS X 10.6 (Snow Leopard) off of iTunes or insert the Snow Leopard DVD Launch Disk Utility

MSc Project Specification Applying Machine Learning Algorithms for

3 Pages · 2003 · 153 KB · English

• Weka ML toolkit and Java programming is a more recent problem solving paradigm where the incorporating multiple indices that use boosted DTs.