Traffic phase effects in packet-switched gateways

ABSTRACT

Much of the traffic in existing packet networks is highly periodic, either because of periodic sources (e.g., real time speech or video, rate control) or because window flow control protocols have a periodic cycle equal to the connection roundtrip time (e.g., a network-bandwidth limited TCP bulk data transfer). Control theory suggests that this periodicity can resonate (i.e., have a strong, non-linear interaction) with deterministic estimation or control algorithms in network gateways.¹ In this paper we define the notion of traffic phase in a packet-switched network and describe how phase differences between competing traffic streams can be the dominant factor in relative throughput. Drop Tail gateways in a TCP/IP network with strongly periodic traffic can result in systematic discrimination against some connections. We demonstrate this behavior with both simulations and theoretical analysis. This discrimination can be eliminated with the addition of appropriate randomization to the network. In particular, analysis suggests that simply coding a gateway to drop a random packet from its queue (rather than the tail) on overflow is often sufficient.We do not claim that Random Drop gateways solve all of the problems of Drop Tail gateways. Biases against bursty traffic and long roundtrip time connections are shared by both Drop Tail and Random Drop gateways. Correcting the bursty traffic bias has led us to investigate a different kind of randomized gateway algorithm that operates on the traffic stream, rather than on the queue. Preliminary results show that the Random Early Detection gateway, a newly developed gateway congestion avoidance algorithm, corrects this bias against bursty traffic. The roundtrip time bias (at least in TCP/IP networks) results from the TCP window increase algorithm, not from the gateway dropping policy, and we briefly discuss changes to the window increase algorithm that could eliminate this bias.

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: 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]
• 3: [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.
• 4: [FJ91] Floyd, S., and Jacobson, V., On Traffic Phase Effects in Packet-Switched Gateways , in preparation.
• 5: [H89] Hashem, E., "Analysis of random drop for gateway congestion control", Report LCS TR-465, Laboratory for Computer Science, MIT, Cambridge, MA, 1989.
• 6: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 7: Srinivasan Keshav, REAL: A Network Simulator, University of California at Berkeley, Berkeley, CA, 1988
• 8: [L89] LaTouche, Guy, "A Study of Deterministic Cycles in Packet Queues Subject to Periodic Traffic", Bellcore Technical Memorandum, 1989.
• 9: [L90] LaTouche, Guy, "Sample Path Analysis of Packet Queues Subject to Periodic Traffic", Computer Networks and ISDN Systems, V. 20, pp. 409-413, 1990.
• 10: 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
• 11: A. Mankin , K. Ramakrishnan, Gateway Congestion Control Survey, RFC Editor, 1991
• 12: 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]
• 13: [RW90] Ramaswami, W., and Willinger, W., "Efficient Traffic Performance Strategies for Packet Multiplexors", Computer Networks and ISDN Systems, V. 20, pp. 401-412, 1990.
• 14: Scott Schenker , Lixia Zhang , David D. Clark, Some observations on the dynamics of a congestion control algorithm, ACM SIGCOMM Computer Communication Review, v.20 n.5, p.30-39, Oct 1 1990 [doi>10.1145/381906.381931]
• 15: [Z89] Zhang, L., "A New Architecture for Packet Switching Network Protocols", MIT LCS TR-455, Laboratory for Computer Science, Massachusetts Institute of Technology, August 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

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