A fluid-flow model for backlog-based CSMA policies

ABSTRACT

We present a fluid flow model to analyze backlog-based CSMA policies. The model is obtained using a CSMA fixed point approximation that has been recently proposed and analyzed. We provide numerical case studies to illustrate the accuracy of the fluid-flow model.

REFERENCES

• 1: D. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, MA, 1999.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: A. Eryilmaz, A. Ozdaglar, and E. Modiano. Polynomial complexity algorithms for full utilization of multi-hop wireless networks, 2006. LIDS Technical Report.
• 4: P. Gupta, Y. Sankarasubramaniam, and A. Stolyar. Random-access scheduling with service differentiation in wireless networks. In Proceedings of IEEE INFOCOM, 2005.
• 5: L. Jiang and J. Walrand. A csma distributed algorithm for throughput and utility maximization in wireless networks. In Proceedings of Allerton Conference, Monticello, IL, 2008.
• 6: K. Kar, S. Sarkar, and L. Tassiulas. Achieving proportionally fair rates using local information in aloha networks. In Proceedings of Allerton Conference, Monticello, IL, October 2003.
• 7: X. Lin and S. Rasool. Constant-time distributed scheduling policies for ad hoc wireless networks. In Proceedings of CDC, 2006.
• 8: X. Lin and N. Shroff. The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks. In Proceedings of IEEE Infocom, Miami, FL, March 2005.
• 9: P. Marbach. Rate control in random access networks: The finite node case. In Proceedings of IEEE Conference on Decision and Control, Paradise Island, Bahamas, December 2004.
• 10: P. Marbach and A. Eryilmaz. A backlog-based csma mechanism to achieve fairness and throughput-optimality in wireless networks. In Proceedings of Allerton Conference, Monticello, IL, 2008.
• 11: P. Marbach, A. Eryilmaz, and A. Ozdaglar. On the throughput-optimality of csma in wireless multihop networks. Computer Networks Research Lab, University of Toronto, Technical Report CNRL-08-002, August 2008.
• 12: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 13: Charles Bordenave , David McDonald , Alexandre Proutiere, Performance of random medium access control, an asymptotic approach, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 14: D. Shah and R. Sreevastsa. Reversible networks, distributed optimization, and network scheduling: what do they have in common? In Proceedings of CISS, Princeton, NJ, 2008.
• 15: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 16: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 36:1936--1948, December 1992.
• 17: X. Wu and R. Srikant. Regulated maximal matching: A distributed scheduling algorithm for multi-hop wireless networks with node-exclusive spectrum sharing. In Proceedings of IEEE Conference on Decision and Control., 2005.
• 18: Clement Yuen , Peter Marbach, Price-based rate control in random access networks, IEEE/ACM Transactions on Networking (TON), v.13 n.5, p.1027-1040, October 2005 [doi>10.1109/TNET.2005.858448]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Design, Performance

Keywords:
backlog-based scheduling, carrier sense multiple access, distributed algorithms, fixed point analysis, throughput-optimality, wireless networks