Communication Networks (Resource Allocation, Games, Queueing)

Pricing and resource allocation games

Overview paper:
R. Johari and J. N. Tsitsiklis, "A Game Theoretic View of Efficiency Loss in Resource Allocation,", in Advances in Control, Communication Networks, and Transportation Systems: In Honor of Pravin Varaiya, E. H. Abed (Ed.), Systems and Control: Foundations and Applications Series, Birkhauser, Boston, 2005, pp. 203-223.

R. Johari and J. N. Tsitsiklis, "Parameterized Supply Function Bidding: Equilibrium and Efficiency,'' Operations Research, Vol. 59, No. 5, September-October 2011, pp. 1079-1089.

R. Johari and J. N. Tsitsiklis, "Efficiency of Scalar-Parameterized Mechanisms", Operations Research, Vol. 57, No. 4, July-August 2009, pp. 823-839; electronic companion.

R. Johari and J. N. Tsitsiklis, "A Scalable Network Resource Allocation Mechanism with Bounded Efficiency Loss", IEEE JSAC Special issue: Price-Based Access Control and Economics for Communication Networks, Vol. 24, No. 5, May 2006, pp. 992-999; Expanded version: "Efficiency Loss in Cournot Games," technical report LIDS-P-2639, Laboratory for Information and Decision Systems, MIT, January 2005.

R. Johari, S. Mannor, and J. N. Tsitsiklis, "Efficiency Loss in a Network Resource Allocation Game: The Case of Elastic Supply," IEEE Transactions on Automatic Control, Vol. 50, No. 11, November 2005, pp. 1712-1724; expanded version, technical report LIDS-P-2605, June 2004.

R. Johari, S. Mannor, and J. N. Tsitsiklis, "A Contract-Based Model for Directed Network Formation," Games and Economic Behavior, Vol. 56, 2006, pp. 201-224.

R. Johari and J. N. Tsitsiklis, "Efficiency Loss in a Network Resource Allocation Game,", Mathematics of Operations Research, Vol. 29, No. 3, August 2004, pp. 407-435.

R. Johari and J. N. Tsitsiklis, "Routing and Peering in a Competitive Internet", technical report LIDS-P-2570, January 2003; condensed version in Proceedings of the 2004 IEEE Conference on Decision and Control, Bahamas, December 2004.

I. Ch. Paschalidis and J. N. Tsitsiklis, "Congestion-Dependent Pricing of Network Services", IEEE/ACM Transactions on Networking, Vol. 8, No. 2, April 2000, pp. 171-184.

Resource allocation problems (routing, admission control, scheduling, etc.)

M. G. Markakis, E. Modiano, and J. N. Tsitsiklis, "Delay Stability Regions of the Max-Weight Policy under Heavy-Tailed Traffic,'' working paper, July 2012.

M. G. Markakis, E. Modiano, and J. N. Tsitsiklis, "Max-Weight Scheduling in Queueing Networks with Heavy-Tailed Traffic,'', February 2012, revised December 2012; to appear in the IEEE/ACM Transactions on Networking.

J. N. Tsitsiklis and K. Xu, "On the power of (even a little) resource pooling", Stochastic Systems, Vol. 2, 2012, pp. 1-66.

K. Jagannathan, M. Markakis, E. Modiano, and J. N. Tsitsiklis, "Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic", IEEE/ACM Transactions on Networking, Vol. 20, No. 4, August 2012, pp. 1096 -1111.

K. P. Jagannathan, M. Markakis, E. Modiano, and J. N. Tsitsiklis, Throughput Optimal Scheduling in the Presence of Heavy-Tailed Traffic, Proceedings of the Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, September 2010.

D. Shah, J. N. Tsitsiklis, and Y. Zhong, "Qualitative properties of alpha-fair policies in bandwidth-sharing networks'', Annals of Applied Probability, Vol. 24, No. 1, February 2014, pp. 76-113.

D. Shah, J. N. Tsitsiklis, Y. Zhong, "Optimal scaling of average queue sizes in an input-queued switch: an open problem", Queueing Systems: Theory and Applications, Vol. 68, No. 3-4, August 2011, pp. 375-384.

M. G. Markakis, E. M. Modiano, and J. N. Tsitsiklis, ""Scheduling policies for single-hop networks with heavy-tailed traffic," Proceedings of the Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, September 2009.

D. Shah, D. N. C. Tse, and J. N. Tsitsiklis, "Hardness of Low Delay Network Scheduling", IEEE Transactions on Information Theory, Vol. 57, No. 12, December 2011, pp. 7810-7818.

A. Ganti, E. Modiano, and J. N. Tsitsiklis, "Optimal Transmission Scheduling in Symmetric Communication Models with Intermittent Connectivity," IEEE Transactions on Information Theory, Vol. 5, No. 3, March 2007, pp. 998-1008.

A. Fu, E. Modiano, and J. N. Tsitsiklis, "Optimal Transmission Scheduling over a Fading Channel with Energy and Deadline Constraints," IEEE Transactions on Wireless Communications, Vol. 5, No. 3, March 2006, pp. 630-641.

Preliminary versions of the previous paper:

A. Fu, E. Modiano, and J. N. Tsitsiklis, "Transmision Scheduling Over a Fading Channel with Energy and Deadline Constraints," in Proceedings of the 2002 Conference on Information Sciences and Systems, Princeton, New Jersey, March 2002.

A. Fu, E. Modiano, and J. N. Tsitsiklis, "Optimal Energy Allocation for Delay-Constrained Data Transmission over a Time-Varying Channel", to appear in the Proceedings of the 2003 INFOCOM, June 2003.

A. Fu, E. Modiano, and J. N. Tsitsiklis, "Optimal Energy Allocation and Admission Control for Communications Satellites", IEEE/ACM Transactions on Networking, Vol. 11, No. 3, June 2003, pp. 488-500. preliminary version in Proceedings of the 2002 INFOCOM, June 2002.

P. Marbach, O. Mihatsch, and J. N. Tsitsiklis, "Call Admission Control and Routing in Integrated Service Networks Using Neuro-Dynamic Programming," IEEE Journal on Selected Areas in Communications, Vol. 18, No. 2, February 2000, pp. 197-208.

Preliminary versions of the previous paper:

P. Marbach, O. Mihatsch, and J. N. Tsitsiklis, "Call Admission Control and Routing in Integrated Service Networks Using Reinforcement Learning," in Proceedings of the 1998 IEEE CDC, Tampa, Florida.

P. Marbach, and J.N. Tsitsiklis, "A Neuro-Dynamic Programming Approach to Call Admission Control in Integrated Service Networks: The Single Link Case," Technical Report LIDS-P-2402, Laboratory for Information and Decision Systems, M.I.T., November 1997. Short version in Proceedings of the 2003 IEEE Conference on Decision and Control, Maui, Hawaii, December 2003.

P. Marbach, O. Mihatsch, M. Schulte, and J. N. Tsitsiklis, "Reinforcement Learning for Call Admission Control and Routing in Integrated Service Networks," presented at the Neural Information Processing Systems, Denver, Colorado, November 1997.

J.N. Tsitsiklis and D.P. Bertsekas, "Distributed Asynchronous Optimal Routing in Data Networks", IEEE Transactions on Automatic Control, Vol. 31, No. 4, 1986, pp. 325-332.

Queueing systems and networks

D. Shah and J. N. Tsitsiklis, "Bin Packing with Queues," Journal of Applied Probability, Vol. 45, No. 4, December 2008, pp. 922-939.

D. Bertsimas, D. Gamarnik, and J. N. Tsitsiklis, "Performance of Multiclass Markovian Queueing Networks via Piecewise Linear Lyapunov Functions", Annals of Applied Probability, Vol. 11, No. 4, pp. 1384-1428, 2001.

D. Bertsimas, D. Gamarnik, and J. N. Tsitsiklis, "Geometric Bounds for Stationary Distributions of Infinite Markov Chains Via Lyapunov Functions," technical report LIDS-P-2426, September 1998.

D. Bertsimas, D. Gamarnik, J. N. Tsitsiklis, "Stability Conditions for Multiclass Fluid Queueing Networks", IEEE Transactions on Automatic Control, Vol. 41, No. 11, November 1996, pp. 1618-1631.

D. Bertsimas, I. C. Paschalidis, and J. N. Tsitsiklis, "Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance", Annals of Applied Probability, Vol. 4, No. 1, 1994, pp. 43-75.

C. H. Papadimitriou and J. N. Tsitsiklis, "The Complexity of Optimal Queueing Network Control", Mathematics of Operations Research, Vol. 24, No. 2, May 1999, pp. 293-305.

G.D. Stamoulis and J.N. Tsitsiklis, "On the Settling Time of the Congested GI/G/1 Queue", Advances in Applied Probability, Vol. 22, 1990, pp. 929-956.

J.N. Tsitsiklis, C.H. Papadimitriou and P. Humblet, "The Performance of a Precedence-Based Queueing Discipline", Journal of the ACM, Vol. 33, No. 3, 1986, pp. 593-602.

Large deviations methods in queueing systems and networks

D. Bertsimas, I. C. Paschalidis, and J. N. Tsitsiklis, "Large Deviations Analysis of the Generalized Processor Sharing Policy", Queueing Systems, Vol. 32, 1999, pp. 319-349.

D. Bertsimas, I. C. Paschalidis, and J. N. Tsitsiklis, "On the Large Deviations Behavior of Acyclic Networks of G/G/1 Queues", Annals of Applied Probability , Vol. 8, No. 4, November 1998, pp. 1027-1069.

D. Bertsimas, I. C. Paschalidis, and J. N. Tsitsiklis, Asymptotic Buffer Overflow Probabilities in Multiclass Multiplexers: An Optimal Control Approach", IEEE Transactions on Automatic Control. Vol. 43, No. 3, March 1988, pp. 315-335.

D. N. C. Tse, R. G. Gallager, and J. N. Tsitsiklis, "Statistical Multiplexing of Multiple Time-Scale Markov Streams", IEEE Journal on Selected Areas in Communications, Vol. 13, No. 6, August 1995, pp. 1028-1038.

Multiaccess

J.N. Tsitsiklis, "Analysis of a Multiaccess Control Scheme", IEEE Transactions on Automatic Control, Vol. 32, No. 11, 1987, pp. 1017-1020.

Communication algorithms in parallel and distributed computing systems

G.D. Stamoulis and J.N. Tsitsiklis, "The Efficiency of Greedy Routing in Hypercubes and Butterflies", IEEE Transactions on Communications, Vol. 42, No. 11, November 1994, pp. 3051-3061.

G.D. Stamoulis and J.N. Tsitsiklis, "Efficient Routing Schemes for Multiple Broadcasts in Hypercubes", IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 7, July 1993, pp. 725-739.

G.D. Stamoulis and J.N. Tsitsiklis, "An Efficient Algorithm for Multiple Simultaneous Broadcasts in the Hypercube", Information Processing Letters, Vol. 46, 1993, pp. 219-224.

D.P. Bertsekas, C. Ozveren, G.D. Stamoulis, P. Tseng, and J.N. Tsitsiklis, "Optimal Communication Algorithms for Hypercubes" Journal of Parallel and Distributed Computing, Vol. 11, 1991, pp. 263-275.