Balancing traffic load using one-turn rectilinear routing. (English) Zbl 1139.68327
Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 467-478 (2008).
Summary: We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region and origin and destination nodes correspond to pairs of points in that region. The objective is to define a routing policy that assigns a continuous path to each origin-destination pair while minimizing the traffic, or load, passing through any single point. While the average load is minimized by straight-line routing, such a routing policy distributes the load non-uniformly, resulting in higher load near the center of the region. We consider one-turn rectilinear routing policies that divert traffic away from regions of heavier load, resulting in up to a 33% reduction in the maximum load while simultaneously increasing the path lengths by an average of less than 28%. Our policies are simple to implement, being both local and oblivious. We provide a lower bound that shows that no one-turn rectilinear routing policy can reduce the maximum load by more than 39% and we give a polynomial-time procedure for approximating the optimal randomized policy.
For the entire collection see [Zbl 1136.68001].
For the entire collection see [Zbl 1136.68001].
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Software:
CVXOPTReferences:
| [1] | Bose, P.; Morin, P.; Stojmenovic, I.; Urrutia, J., Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, 7, 609-616 (2001) · Zbl 0996.68012 · doi:10.1023/A:1012319418150 |
| [2] | Broch, J., Johnson, D., Maltz, D.: The dynamic source routing protocol for mobile ad hoc networks (1998): Internet-draft, draft-ietf-manet-dsr-00.txt |
| [3] | Busch, C., Magdon-Ismail, M., Xi, J.: Oblivious routing on geometric networks. In: Proc. ACM SPAA, vol. 17 (2005) · Zbl 1218.68194 |
| [4] | Chung, F. R.K.; Coffman, E. G. Jr.; Reiman, M. I.; Simon, B., The forwarding index of communication networks, IEEE Trans. Inf. Th., 33, 2, 224-232 (1987) · Zbl 0626.94019 · doi:10.1109/TIT.1987.1057290 |
| [5] | Dahl, J.: Cvxopt: A python package for convex optimization. In: Proc. Eur. Conf. Op. Res. (2006) |
| [6] | Gao, J., Zhang, L.: Load balanced short path routing in wireless networks. In: Proc. IEEE INFOCOM, vol. 23, pp. 1099-1108 (2004) |
| [7] | Gao, J., Zhang, L.: Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs. In: Proc. ACM PODC, pp. 189-196 (2004) · Zbl 1321.68384 |
| [8] | Gupta, P.; Kumar, P. R., The capacity of wireless networks, IEEE Trans. Inf. Th., 46, 388-404 (2000) · Zbl 0991.90511 · doi:10.1109/18.825799 |
| [9] | Heydemann, M. C.; Meyer, J. C.; Sotteau, D., On forwarding indices of networks, Disc. App. Math., 23, 103-123 (1989) · Zbl 0681.90077 · doi:10.1016/0166-218X(89)90022-X |
| [10] | Hyytiä, E.; Lassila, P.; Virtamo, J., Spatial node distribution of the random waypoint mobility model with applications, IEEE Trans. Mob. Comp., 6, 680-694 (2006) · doi:10.1109/TMC.2006.86 |
| [11] | Jinyang, L., Blake, C., Couto, D.D., Lee, H., Morris, R.: Capacity of ad hoc wireless networks. In: Proc. ACM MOBICOM (2001) |
| [12] | Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. CCCG, pp. 51-54 (1999) |
| [13] | Meyer auf der Heide, F., Schindelhauer, C., Volbert, K., Grunwald, M.: Energy, congestion, and dilation in radio networks. In: Proc. ACM SPAA, pp. 230-237 (2002) |
| [14] | Park, V., Corson, S.: A highly adaptive distributed routing algorithm for mobile wireless networks. In: Proc. IEEE INFOCOM, pp. 1405-1413 (1997) |
| [15] | Pham, P.P., Perreau, S.: Performance analysis of reactive shortest path and multi-path routing mechanism with load balance. In: Proc. IEEE INFOCOM, pp. 251-259 (2003) |
| [16] | Popa, L., Rostami, A., Karp, R.M., Papadimitriou, C., Stoica, I.: Balancing traffic load in wireless networks with curveball routing. In: Proc. ACM MOBIHOC (2007) |
| [17] | Santaló, L. A., Integral Geometry and Geometric Probability (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1116.53050 |
| [18] | Stojmenovic, I., Position based routing in ad hoc networks, IEEE Comm. Mag., 40, 128-134 (2002) · doi:10.1109/MCOM.2002.1018018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
