TY - JOUR
T1 - A novel architecture for reduction of delay and queueing structure complexity in the back-pressure algorithm
AU - Bui, Loc X.
AU - Srikant, R.
AU - Stolyar, Alexander
N1 - Funding Information:
Manuscript received December 06, 2009; revised July 02, 2010 and February 14, 2011; accepted February 28, 2011. Date of publication March 28, 2011; date of current version December 16, 2011. The work of L. X. Bui and R. Srikant was supported in part by the DTRA under Grant HDTRA1-08-1-0016, the NSF under Grant CNS 07-21286, two Army MURIs, an AFOSR MURI, and the AFOSR under Grant FA-9550-08-1-0432. An earlier version of this paper was presented at the IEEE Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, April 19–25, 2009.
PY - 2011/12
Y1 - 2011/12
N2 - The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its implementation requires that each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. This fact may lead to a poor delay performance even when the traffic load is not close to network capacity. Also, since the number of commodities in the network is usually very large, the queueing data structure that has to be maintained at each node is respectively complex. In this paper, we present a solution to address both of these issues in the case of a fixed-routing network scenario where the route of each flow is chosen upon arrival. Our proposed architecture allows each node to maintain only per-neighbor queues and, moreover, improves the delay performance of the back-pressure algorithm.
AB - The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its implementation requires that each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. This fact may lead to a poor delay performance even when the traffic load is not close to network capacity. Also, since the number of commodities in the network is usually very large, the queueing data structure that has to be maintained at each node is respectively complex. In this paper, we present a solution to address both of these issues in the case of a fixed-routing network scenario where the route of each flow is chosen upon arrival. Our proposed architecture allows each node to maintain only per-neighbor queues and, moreover, improves the delay performance of the back-pressure algorithm.
KW - Communication networks
KW - queueing analysis
KW - scheduling algorithm
UR - http://www.scopus.com/inward/record.url?scp=84655169975&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84655169975&partnerID=8YFLogxK
U2 - 10.1109/TNET.2011.2126593
DO - 10.1109/TNET.2011.2126593
M3 - Article
AN - SCOPUS:84655169975
SN - 1063-6692
VL - 19
SP - 1597
EP - 1609
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 6
M1 - 5739564
ER -