Multiple-path layer-2 based routing and load balancing approach for wireless infrastructure mesh networks

ABSTRACT

This work presents a general layer-2 approach for routing and load balancing in Wireless Infrastructure Mesh Network The key idea is dynamic select routes among a set of slowly changing alternative network paths. Our approach decouples the routing and load balancing problem into two distinct sub-problems: path creation and path selection. Paths are created through the reuse of classical 802.1Q multiple spanning tree mechanisms. This guarantees that, for each formed tree, a path is deployed from each mesh node to the Mesh Gateway. Moreover, each tree (path) is assigned a Virtual LAN identifier. Path selection is driven by a local algorithm running at each mesh node, fed by measurements (taken along each path connecting the mesh node to the gateway) which allow to dynamically determine which are the best paths. In order to route a packet it is sufficient to mark the packet with the VLAN tag corresponding to the chosen path. The described approach provides a very general and flexible framework: performance/stability trade-offs can be tuned through the choice of i) the mechanism used to measure the path quality; ii) the algorithm employed to select the path, and iii) the system parameter used (link costs and link weights) for the multiple spanning tree formation.

REFERENCES

• 1: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 2: T. Clausen, P. Jacquet, A. Laouiti, P. Minet, P. Muhlethaler, A. Qayyum, and L. Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan, 2001.
• 3: C. E. Perkins et al. Ad hoc networking. Addison-Wesley Boston, 2001. Chapter: Ad hoc On-Demand Distance Vector Routing.
• 4: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 5: Richard Draves , Jitendra Padhye , Brian Zill, Comparison of routing metrics for static multi-hop wireless networks, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 6: B. Awerbuch, D. Holmer, and H. Rubens. High throughput route selection in multi-rate ad hoc wireless networks. First Working Conference on Wireless On-demand Network Systems (WONS), 2004.
• 7: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]