| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Reliable Packet Transmissions in Multipath Routed Wireless Networks
May 2006 (vol. 5 no. 5)
pp. 548-559
We study the problem of using path diversification to provide low probability of packet loss (PPL) in wireless networks. Path diversification uses erasure codes and multiple paths in the network to transmit packets. The source uses Forward Error Correction (FEC) to encode each packet into multiple fragments and transmits the fragments to the destination using multiple disjoint paths. The source uses a load balancing algorithm to determine how many fragments should be transmitted on each path. The destination can reconstruct the packet if it receives a number of fragments equal to or higher than the number of fragments in the original packet. We study the load balancing algorithm in two general cases. In the first case, we assume that no knowledge of the performance along the paths is available at the source. In such a case, the source decomposes traffic uniformly among the paths; we call this case blind load balancing. We show that for low PPL, blind load balancing outperforms single-path transmission. In the second case, we assume that a feedback mechanism periodically provides the source with information about the performance along each path. With that information, the source can optimally distribute the fragments. We show how to distribute the fragments for minimized PPL, and maximized efficiency given a bound on PPL. We evaluate the performance of the scheme through numerical simulations.
[1] 548 M.O. Rabin, “Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance,” J. ACM, vol. 36, no. 2, pp. 335-348, Apr. 1989.[2] P. Rodriguez, R. Chakravorty, J. Chesterfield, I. Pratt, and S. Banerjee, “MAR: A Commuter Router Infrastructure for the Mobile Internet,” Proc. MobiSys Conf., pp. 217-230, 2004.[3] Nortel Networks “Wireless Mesh Network— Extending the Reach of Wireless Lan, Securely and Cost-Effectively,” http://www. nortelnetworks.com/solutions wlan/, Nov. 2003.[4] Mesh Networks, “Putting Hot Spots in Motion Mesh-Enabled Solutions Mobile 802.11,” http://www.meshnetworks.com/pages/applications mobile_wifi.htm, Sept. 2004.[5] P. Djukic and S. Valaee, “Minimum Energy Fault Tolerant Sensor Networks,” Proc. Globecom Conf., 2004.[6] Mesh Networks, “White Paper: Mesh-Enabled Solutions for Intelligent Transportation Systems,” technical report, 2004.[7] T. Goff and D.S. Phatak, “Unified Transport Layer Support for Data Striping and Host Mobility,” IEEE J. Selected Areas of Comm., vol. 22, no. 4, pp. 737-746, May 2004.[8] H.-Y. Hsieh and R. Sivakumar, “A Transport Layer Approach for Achieving Aggregate Bandwidths on Multi-Homed Mobile Hosts,” Proc. MOBIHOC 2002 Conf., Sept. 2002.[9] T. Fowler, “Mesh Networks for Broadband Access,” IEE Rev., vol. 47, no. 1, pp. 17-22, Jan. 2001.[10] B. Schrick and M.J. Riezenman, “Wireless Broadband in a Box,” IEEE Spectrum, vol. 39, no. 6, pp. 39-43, June 2001.[11] S. Xu and T. Saadawi, “Does the IEEE 802. 11 MAC Protocol Work Well in Multihop Wireless Ad Hoc Networks,” IEEE Comm. Magazine, vol. 39, no. 6, pp. 130-137, June 2001.[12] R. Hsieh, A. Seneviratne, H. Soliman, and K. El-Malki, “Performance Analysis on Hierarchical Mobile Ipv6 with Fast-Handoff over End-to-End TCP,” Proc. GLOBECOM Conf., pp. 2488-2492, 2002.[13] S. Valaee, “Information Raining for Mobile Hotspots in 4G Wireless Networks,” Proc. 22nd Biennial Symp. Comm., May-June 2004.[14] D. Ho and S. Valaee, “Mobile Hotspot in Railway System,” Proc. 22nd Biennial Symp. Comm., May-June 2004.[15] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, “Modeling TCP Throughput: A Simple Model and Its Empirical Validation,” Proc. SIGCOMM '98 Conf., pp. 303-314, 1998.[16] M. Stoer, Design of Survivable Networks, Heidelberg: Springer Verlag, 1992.[17] M.K. Marina and S.R. Das, “On-Demand Multipath Distance Vector Routing in Ad Hoc Networks,” Proc. Int'l Conf. Network Procotols (ICNP), Nov. 2001.[18] A. Nasipuri, R. Castaneda, and S.R. Das, “Performance of Multipath Routing for On-Demand Protocols in Ad Hoc Networks,” ACM/Kluwer Mobile Networks and Applications (MONET) J., vol. 6, no. 4, pp. 339-349, 2001.[19] P. Papadimitratos, Z.J. Haas, and E.G. Sirer, “Path Selection in Mobile Ad Hoc Networks,” Proc. Mobihoc 2002 Conf., 2002.[20] S.-J. Lee and M. Gerla, “Split Multipath Routing with Maximally Disjoint Paths in Ad Hoc Networks,” Proc. Int'l Conf. Comm., vol. 10, pp. 3201-3205, 2001.[21] H. Lim, K. Xu, and M. Gerla, “TCP Performance over Multipath Routing in Mobile Ad Hoc Networks,” Prof. Int'l Conf. Comm., vol. 2, pp. 1064-1068, 2003.[22] S. Vutukury, “Multipath Routing Mechanisms for Traffic Engineering and Quality of Service in the Internet,” PhD dissertation, Univ. of California, Santa Cruz, May 2001.[23] A. Tsirigos and Z.J. Haas, “Multipath Routing in the Presence of Frequent Topological Changes,” IEEE Comm. Magazine, vol. 39, no. 11, pp. 132-138, Nov. 2001.[24] A. Tsirigos and Z.J. Haas, “Analysis of Multipath Routing-Part I: The Effect on the Packet Delivery Ratio,” IEEE Trans. Wireless Comm., vol. 3, no. 1, pp. 138-146, Jan. 2004.[25] A. Tsirigos and Z.J. Haas, “Analysis of Multipath Routing, Part 2: Mitigation of the Effects of Frequently Changing Network Topologies,” IEEE Trans. Wireless Comm., vol. 3, no. 2, pp. 500-511, Mar. 2004.[26] G.-S. Ahn, A.T. Campbell, A. Veres, and L.-H. Sun, “SWAN: Service Differentiation in Stateless Wireless Ad Hoc Networks,” Proc. INFOCOM Conf., 2002.[27] S.-B. Lee, G.-S. Ahn, and A.T. Campbell, “Improving UDP and TCP Performance in Mobile Ad Hoc Netoworks with INSIGNIA,” IEEE Comm. Magazine, vol. 39, no. 6, pp. 156-165, June 2001.[28] N.F. Maxemchuk, “Dispersity Routing,” Proc. IEEE Int'l Comm. Conf. (ICC '75), pp. 41.10-41.13, June 1975[29] J. Blomer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, and D. Zuckerman, “An XOR-Based Erasure-Resilient Coding Scheme,” Technical Report TR-95-048, Int'l Computer Science Inst., Berkeley, Calif., 1995.[30] A. Woo, T. Tong, and D. Culler, “Taming the Underlying Challenges for Reliable Multihop Routing in Sensor Networks,” Proc. ACM Conf. Embedded Networked Sensor Systems, 2003.[31] S. Valaee and B. Li, “Distributed Call Admission Control for Ad Hoc Networks,” Proc. Vehicular Technology Conf. (VTC), Sept. 2002.[32] C. Cetinkaya and E.W. Knightly, “Egress Admission Control,” Proc. IEEE 19th Ann. Joint Conf. IEEE Computer and Comm. Soc., pp. 1471-1481, Mar. 2000.[33] C. Tang and P.K. McKinley, “Modeling Multicast Packet Losses in Wireless LANS,” Technical Report MSU-CSE-02-12, Computer Science and Eng. Dept., Michigan State Univ., 2002.[34] M. Mushkin and I. Bar-David, “Capacity and Coding for the Gilbert-Elliott Channels,” IEEE Trans. Information Theory, vol. 35, no. 6, pp. 1277-1290, Nov. 1989.[35] H.S. Wang and N. Moayeri, “Finite-State Markov Channel— A Useful Model for Radio Communication Channels,” IEEE Trans. Vehicular Technology, vol. 44, no. 1, pp. 163-171, Feb. 1995.[36] D.R. Shier, Network Reliability and Algebraic Structures. Oxford: Claredon Press, 1991.[37] R.E. Barlow and K.D. Heidtmann, “Computing k-out-of-n System Reliability,” IEEE Trans. Reliability, vol. 33, no. 4, pp. 322-323, Oct. 1984.[38] R.J. Serfling, “Some Elementary Results on Poisson Approximation in a Sequence of Bernoulli Trials,” SIAM Rev., vol. 20, no. 3, pp. 567-579, July 1978.[39] P. Djukic, “Optimum Resource Allocation in Multipath Ad Hoc Networks,” MASc Thesis, Univ. of Toronto, 2003.[40] Limit Theorems of Probability Theory, Y.V. Prokhorov and V. Satulevicius, eds. Springer-Verlag, 2000.[41] J.F. Muth, “Optimal Properties of Exponentially Weighted Forecasts,” J. Am. Statistical Assoc., vol. 55, no. 290, pp. 299-306, June 1960.
Index Terms:
Wireless communication, fault tolerance, network monitoring, algorithm/protocol design and analysis, linear programming.
Citation:
Petar Djukic, Shahrokh Valaee, "Reliable Packet Transmissions in Multipath Routed Wireless Networks," IEEE Transactions on Mobile Computing, vol. 5, no. 5, pp. 548-559, May 2006, doi:10.1109/TMC.2006.72
