Polynomial-Time Algorithms for Multirate Anypath Routing in Wireless Multihop Networks

Autor: Henri Dubois-Ferriere, Leonard Kleinrock, Rafael Laufer
Rok vydání: 2012
Předmět:
FOS: Computer and information sciences
Routing protocol
Dynamic Source Routing
Computer Networks and Communications
Equal-cost multi-path routing
Computer science
Routing table
Distributed computing
Enhanced Interior Gateway Routing Protocol
Wireless Routing Protocol
Geographic routing
02 engineering and technology
Computer Science - Networking and Internet Architecture
Routing Information Protocol
0203 mechanical engineering
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Data Structures and Algorithms (cs.DS)
Destination-Sequenced Distance Vector routing
Electrical and Electronic Engineering
Hierarchical routing
Triangular routing
Networking and Internet Architecture (cs.NI)
Zone Routing Protocol
Static routing
business.industry
Wireless network
Network packet
ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS
Testbed
Policy-based routing
Path vector protocol
DSRFLOW
020302 automobile design & engineering
020206 networking & telecommunications
Computer Science Applications
Routing domain
Link-state routing protocol
Multipath routing
business
Algorithm
Software
Computer network
Zdroj: IEEE/ACM Transactions on Networking. 20:742-755
ISSN: 1558-2566
1063-6692
DOI: 10.1109/tnet.2011.2165852
Popis: In this paper we present a new routing paradigm that generalizes opportunistic routing for wireless multihop networks. In multirate anypath routing, each node uses both a set of next hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set and one of them forwards the packet on to the destination. To date, there has been no theory capable of jointly optimizing both the set of next hops and the transmission rate used by each node. We solve this by introducing two polynomial-time routing algorithms and provide the proof of their optimality. The proposed algorithms run in roughly the same running time as regular shortest-path algorithms, and are therefore suitable for deployment in routing protocols. We conducted measurements in an 802.11b testbed network, and our trace-driven analysis shows that multirate anypath routing performs on average 80% and up to 6.4 times better than anypath routing with a fixed rate of 11 Mbps. If the rate is fixed at 1 Mbps instead, performance improves by up to one order of magnitude.
14 pages, 11 figures
Databáze: OpenAIRE
Externí odkaz: