Email this article A Routing Algorithm To Reduce The Queueing Complexity In Communication Networks
Abstract
A new adaptive routing algorithm built ahead the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. The routing algorithm is considered to decrease the average number of hops used by packets in the network. This idea along with the scheduling/routing decoupling leads to setback decrease compared with the traditional back-pressure algorithm. The algorithm can be applied to wire line and wireless networks. Wide simulations show spectacular improvement in delay performance compared to the back-pressure algorithm. When network coding is employed per-previous-hop queues may also be essential but this is a requirement compulsory by network coding not by our algorithm.
Keywords
References
L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Autom. Control, vol. 37, no.
, pp. 1936–1948, Dec. 1992.
M. J. Neely, E. Modiano, and C. E. Rohrs, “Dynamic power allocationand routing for time varying wireless networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89–103, Jan. 2005.
L. Bui, R. Srikant, and A. L. Stolyar, “Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing,” in Proc. IEEE INFOCOM Mini-Conf., Apr. 2009, pp. 2936–2940.
L. Bui, R. Srikant, and A. L. Stolyar, “A novel architecture for delay reduction in the back-pressure scheduling algorithm,” IEEE/ACM Trans. Netw., vol. 19, no. 6, pp. 1597–1609, Dec. 2011.
L. Bui, R. Srikant, and A. L. Stolyar, “Optimal resource allocation for multicast flows in multihop wireless networks,” Phil. Trans. Roy. Soc., Ser. A, vol. 366, pp. 2059–2074, 2008.
L. Ying, S. Shakkottai, and A. Reddy, “On combining shortest-path and back-pressure routing over multihop wireless networks,” in Proc. IEEE INFOCOM, Apr. 2009, pp. 1674–1682.
S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “XORs in the air: Practical wireless network coding,” Comput. Commun. Rev., vol. 36, pp. 243–254, 2006.
M. Effros, T. Ho, and S. Kim, “A tiling approach to network code design for wireless networks,” in Proc. Inf. Theory Workshop, 2006, pp. 62–66.
H. Seferoglu, A. Markopoulou, and U. Kozat, “Network coding-aware rate control and scheduling in wireless networks,” in Proc. ICME Special Session Netw. Coding Multimedia Streaming, Cancun, Mexico, Jun. 2009, pp. 1496–1499.
S. B. S. Sengupta and S. Rayanchu, “An analysis of wireless network coding for unicast sessions: The case for coding-aware routing,” in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 1028–1036.
T. Ho and H. Viswanathan, “Dynamic algorithms for multicast with intra-session network coding,” IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 797–815, Feb. 2009.
A. Eryilmaz, D. S. Lun, and B. T. Swapna, “Control of multi-hop communication networks for inter-session network coding,” IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 1092–1110, Feb. 2011.
L. Chen, T. Ho, S. H. Low, M. Chiang, and J. C. Doyle, “Optimization based rate control for multicast with network coding,” in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 1163–1171.
B. Awerbuch and T. Leighton, “A simple local-control approximation algorithmformulticommodity flow,” in Proc. 34th Annu. Symp. Found. Comput. Sci., 1993, pp. 459–468.
A. Dimakis and J. Walrand, “Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits,” Adv. Appl. Probab., vol. 38, no. 2, Jun. 2006.
Refbacks
- There are currently no refbacks.
Copyright © 2013, All rights reserved.| ijseat.com
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at http://creativecommons.org/licenses/by/3.0/deed.en_GB.