Connections with multiple congested gateways in packet-switched networks part 1: one-way traffic

ABSTRACT

In this paper we explore the bias in TCP/IP networks against connections with multiple congested gateways. We consider the interaction between the bias against connections with multiple congested gateways, the bias of the TCP window modification algorithm against connections with longer roundtrip times, and the bias of Drop Tail and Random Drop gateways against bursty traffic. Using simulations and a heuristic analysis, we show that in a network with the window modification algorithm in 4.3 tahoe BSD TCP and with Random Drop or Drop Tail gateways, a longer connection with multiple congested gateways can receive unacceptably low throughput. We show that in a network with no bias against connections with longer roundtrip times and with no bias against bursty traffic, a connection with multiple congested gateways can receive an acceptable level of throughput.We discuss the application of several current measures of fairness to networks with multiple congested gateways, and show that different measures of fairness have quite different implications. One view is that each connection should receive the same throughput in bytes/second, regardless of roundtrip times or numbers of congested gateways. Another view is that each connection should receive the same share of the network's scarce congested resources. In general, we believe that the fairness criteria for connections with multiple congested gateways requires further consideration.

REFERENCES

• 1: [BDSY88] Bacon, D., Dupuy, A., Schwartz, J., and Yemimi, Y., "Nest: a Network Simulation and Prototyping Tool", Proceedings of Winter 1988 Usenix Conference, 1988, pp. 17- 78.
• 2: [BJ81] Bharath-Kumar, K., and Jeffrey, J., A New Approach to Performance-Oriented Flow Control, IEEE Transactions on Communications, Vol. COM-29 N.4, April 1981.
• 3: Ramón Cáceres , Peter B. Danzig , Sugih Jamin , Danny J. Mitzel, Characteristics of wide-area TCP/IP conversations, Proceedings of the conference on Communications architecture & protocols, p.101-112, September 03-06, 1991, Zurich, Switzerland
• 4: D.-M. Chiu , R. Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• 5: [DKS90] Demers, A., Keshav, S., and Shenker, S., "Analysis and Simulation of a Fair Queueing Algorithm", Internetworking: Research and Experience, Vol. 1, 1990, p. 3-26.
• 6: Sally Floyd , Van Jacobson, Traffic phase effects in packet-switched gateways, ACM SIGCOMM Computer Communication Review, v.21 n.2, p.26-42, April 1991 [doi>10.1145/122419.122421]
• 7: [FJ91b] Floyd, S., and Jacobson, V., On Traffic Phase Effects in Packer-Switched Gateways , in preparation. (This is a longer version of the paper above.)
• 8: [FJ91c] Floyd, S., and Jacobson, V., Random Early Detection gateways for congestion avoidance , in preparation.
• 9: [H89] Hashem, E., "Analysis of random drop for gateway congestion control", Report LCS TR-465, Laboratory for Computer Science, MIT, Cambridge, MA, 1989.
• 10: [HG86] Hahne, E., and Gallager, R., Round Robin Scheduling for Fair Flow Control in Data Communications Networks, IEEE International Conference on Communications, June, 1986.
• 11: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 12: V. Jacobson , R. T. Braden, TCP extensions for long-delay paths, RFC Editor, 1988
• 13: [J90] Jacobson, V., Berkeley TCP Evolution from 4.3-tahoe to 4.3-reno, "Proceedings of the Eighteenth Internet Engineering Task Force", Vancouver, British Columbia, August, 1990.
• 14: [JCH84] Jain, R., Chiu, D.M., and Hawe, W., "A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems." DEC FR-301, Littleton, MA: Digital Equipment Corporation.
• 15: Srinivasan Keshav, REAL: A Network Simulator, University of California at Berkeley, Berkeley, CA, 1988
• 16: [M90a] Mankin, A., "A Measurement Study of Random Drop and Gateway Interaction", 1990.
• 17: A. Mankin, Random drop congestion control, Proceedings of the ACM symposium on Communications architectures & protocols, p.1-7, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 18: [MS90] Mitra, D. and Seery, J., Dynamic Adaptive Windows for High Speed Data Networks: Theory and Simulations, AT&T Bell Laboratories report, April 1990.
• 19: [RCJ87] Ramakrishnan, K.K., Chiu, D., and Jain, R., "Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part IV: A Selective Binary Feed-back Scheme for General Topologies", DEC-TR-510, November, 1987.
• 20: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.158-181, May 1990 [doi>10.1145/78952.78955]
• 21: [R83] Ross, S., Stochastic Processes, John Wiley & Sons, 1983.
• 22: Rick Wilder , K. K. Ramakrishnan , Allison Mankin, Dynamics of congestion control and avoidance of two-way traffic in an OSI testbed, ACM SIGCOMM Computer Communication Review, v.21 n.2, p.43-58, April 1991 [doi>10.1145/122419.122422]
• 23: Lixia Zhang , Scott Shenker , Daivd D. Clark, Observations on the dynamics of a congestion control algorithm: the effects of two-way traffic, Proceedings of the conference on Communications architecture & protocols, p.133-147, September 03-06, 1991, Zurich, Switzerland
• 24: [Z89] Zhang, L., "A New Architecture for Packet Switching Network Protocols", MIT LCS TR-455, Laboratory for Computer Science, Massachusetts Institute of Technology, Au - gust 1989.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification