Improving Internet Congestion Control and Queue Management
Algorithms
This work demonstrates that with simple modifications to
the network
and end-hosts, bandwidth guarantees can be provided over the
Internet using TCP and simple priority marking. Specifically,
the mechanism employed in the networks is an Enhanced RED queue. This
queue
management assumes that connections with reservations police their
connections
using a token bucket and that they mark packets [5] which are
compliant. The queue management mechanism gives preferential
treatment to marked packets in that their drop probabilities are
significantly smaller than those of unmarked packets. Given this
network support, we show that with minor
changes in the end-hosts, we can effectively support bandwidth
requirements
in the network. The work focuses on changes in the TCP sender,
however,
similar modifications can be easily applied to a UDP/RTP sender.
The simulations were run using a
modified version of ns-1.1. Experiment files which
were used to run the simulations are included underneath the graphs
which
display the results. If you have any problems with the code, you
can e-mail me.
The TCP mods and ERED are currently being implemented
at IBM.
Finally, the slides I meant to show at NOSSDAV (before the
laptop projector died on me) [1] are below.
[1] W. Feng, D. Kandlur, D. Saha, K. Shin, "Understanding TCP
Dynamics in an Integrated Services Internet"
NOSSDAV '97, May 1997. (Paper ps
| Slides html | Slides ppt)
[2] W. Feng, D. Kandlur, D. Saha, K. Shin, "Understanding and
Improving TCP Performance over Networks with Minimum Rate Guarantees"
IEEE/ACM Transactions on Networking, Vol. 7, No. 2, pp. 173-187, April
1999.
(Extended version of [1]) ps
[3] W. Feng, D. Kandlur, D. Saha, K. Shin, "TCP
Enhancements for an Integrated Services Internet," IBM Research
Report RC 20618, version 1, November 1996. ps
Note: This report contains
additional experiments related to burst losses and the delayed send
work. These simulations were removed from subsequent papers due to
space
limitations.
[4] D. Clark, "Adding
Service Discrimination to the Internet" September 1995.
The work presents several
adaptive packet marking mechanisms for providing soft bandwidth
guarantees to individual flows or flow groups. The schemes
use modest support from the network in the form of priority handling
for
appropriately marked packets and rely on intellligent transmission
control
mechanisms at the edges of the network to achieve the desired
throughput
levels. In our model, the user specifies a desired minimum
service rate for a connection or a connection group. At any point of
time,
the sender, in cooperation with the packet marking engine, tries to
achieve
and potentially exceed the requested minimum service rate without using
the high priority service. If however, it fails to achieve the minimum
target rate, the packet marking engine starts prioritizing packets
until
the observed service rate reaches the desired target rate. Once the
target
is reached, it strives to reduce the number of priority packets without
falling below the target. When the number of priority packets comes
down
to zero, the source tries to increase its share of the best-effort
bandwidth.
We consider marking mechanisms of two distinct
flavors: (1) where packet
marking is completely independent of and transparent
to the traffic source, and (2) where the marking module is integrated
with the transmission control mechanisms at the source. To address
the robustness of the algorithms, we evaluate their performance in
situations
where the network is over-subscribed and
when the network contains non-responsive
flows. We also consider scenarios where only some parts of the network
support service differentiation and propose mechanisms for detecting
and reacting to such situations at the source. Finally, we discuss
issues in interoperating ToS-based mechanisms with alternative
mechanisms
for supporting service differentiation in the Internet. The simulations
were run using a modified version of ns. All experiment files and
source
code will be made available soon.
[1] W. Feng, D. Kandlur, D. Saha, K. Shin, "Adaptive
Packet Marking for Providing Differentiated Services in the Internet"
U. Michigan CSE-TR-347-97 and IBM RC 21013, October 1997.
[2] W. Feng, D. Kandlur, D. Saha, K. Shin, "Adaptive
Packet Marking for Providing
Differentiated Services in the Internet" Proc. of 1998
International Conference on Network Protocols (ICNP '98), October
1998. (Also
IBM RC 21013 Version 2, January 1998.) (Paper ps |
Slides ps ppt)
[3] W. Feng, ns Modifications tgz.
[4] W. Feng, D. Kandlur, D. Saha, K. Shin, "Adaptive Packet Marking
for Maintaining End-to-End Throughput in a Differentiated Services
Internet", IEEE/ACM Transactions on Networking, v.7, n.5, Oct. 1999. ps
This work describes the use of Adaptive
RED and SubTCP for effectively eliminating packet loss in congested
TCP/IP
networks. The results show that one can reduce packet loss
considerably
by making active queue management techniques more cognizant of the
offered
load and by designing end-host congestion control mechanisms more
intelligently.
When both techniques are combined, they form a synergistic combination
which
can achieve extremely high efficiency even in the most difficult
scenarios.
[1] W. Feng, D. Kandlur, D. Saha, K. Shin,
"Techniques for Eliminating Packet Loss in Congested TCP/IP Networks"
U. Michigan CSE-TR-349-97, November 1997. ps
[2] W. Feng, D. Kandlur, D. Saha, K. Shin,
"A Self-Configuring RED Gateway", INFOCOM '99, March 1999. (This is a
subset of the work in [1].) (Paper ps | Slides ppt)
This work describes Blue, a fundamentally different
queue management algorithm which
can effectively eliminate packet loss in congested TCP/IP
networks. The results show that one can reduce packet loss
considerably
by decoupling congestion management algorithms from either the
instantaneous or average queue length. ns-1.1 simulation modifications
can be downloaded from [2]. The FreeBSD/ALTQ implementation can
be downloaded from [3]. The algorithm has been implemented and
validated by others [8,9,10] and was later acknowledged in an
article on router bufferbloat by the pioneer of AQM [11].
[1] W. Feng, D. Kandlur, D. Saha, K. Shin, "Blue: A
New Class of Active Queue Management Algorithms"
U. Michigan CSE-TR-387-99, April 1999.
ps
|
pdf
[2] W. Feng
"ns-1.1 modifications for implementing Blue and Stochastic Fair Blue"
tgz
[3] W. Feng
"ALTQ modifications for implementing Blue"
(Program mods tgz
|
Kernel mods tgz)
[4] W. Feng, D. Kandlur, D. Saha, K. Shin,
"Stochastic Fair Blue: A Queue Management Algorithm for Enforcing
Fairness",
in Proc. of INFOCOM 2001, April 2001.
(Paper pdf |
Slides ppt)
[5] W. Feng, D. Kandlur, D. Saha, K. Shin,
"Blue: An Alternative Approach To Active Queue Management", in
Proc. of NOSSDAV 2001, June 2001. (Paper ps |
Slides ppt)
[6] W. Feng, D. Kandlur, D. Saha, K. Shin,
"The Blue Queue Management Algorithms", IEEE/ACM Transactions on
Networking, Vol. 10, No. 4, August 2002. pdf
Winner of the IEEE Communications Society 2003 William R. Bennett
Prize for Best Paper in IEEE/ACM Transactions on Networking.
Also Winner of the Best IBM Research Paper Award in Computer
Science, Electrical Engineering, and Math 2002.
[7] W. Feng, "Parameters for Blue", Unpublished. txt
[8] I. Bartok, "Implementation and Evaluation of The Blue Active Queue Management Algorithm", Diploma Thesis, Budapest University of Technology and Economics, May 2001. pdf
[9] S. Burri, "Blue: Active Queue Management", CS756 Project Report, George Mason University, May 2004. pdf
[10] E. Dumazet, "Patchwork [net-next-2.6,v3] net_sched: SFB flow scheduler", February 2011. Summary | Development notes
[11] K. Nichols, V. Jacobson, "A Modern AQM is Just One Piece of the Solution to Bufferbloat", ACM Queue, Vol. 10, No. 5, May 2012. paper
Follow-on work
1. RED and Multimedia Congestion Control
This work describes the bandwidth jitter that accompanies the use of
randomized active queue management and its effect on the buffering
requirements of streaming multimedia applications.
[1] W. Feng, W. Feng, "The Impact of Active Queue Management on
Multimedia Congestion Control," IC3N 1998, October 1998. (Paper ps |
Slides ppt)