A betterthan-best-effort service for continuous media udp flows

Media UDP Flows*

Mark Parris Kevin Jeffay F. Donelson Smith Jan Borgersen

University of North Carolina at Chapel Hill

Department of Computer ScienceChapel Hill, NC 27599-3175 USA{parris,jeffay,smithfd,borg}@cs.unc.edu

http://www.cs.unc.edu/Research/dirt

Abstract

The Internet community is very interested in addressingcongestion with active queue management mechanismslike Random Early Detection (RED). Recent proposalsextend these mechanisms to actively penalize “misbehav-ing” flows. These methods favor TCP and TCP-like flowsstrongly over other flows like UDP. In this paper we pro-pose extensions to active queue management disciplineswhich continue to address congestion and reward TCP-friendly flows while minimizing impact on continuousmedia flows using other protocols. Our mechanism, DropPreference Management (DPM), recognizes tagged flowsand manages their latency while constraining the band-width they consume. We present empirical results of ex-periments comparing our mechanism to plain RED.

gestion in the current internet and makes two recommenda-tions [2]. First, they recommend deploying active queuemanagement schemes, specifically Random Early Detec-tion (RED) to more effectively notify responsive flows ofcongestion [5]. Active queue management refers to extend-ing the queueing discipline in the router beyond simpleenqueue and dequeue with drop-tail when full. For exam-ple, RED does not wait until the queue is full to droppackets. Instead, it probabilistically drops incoming pack-ets when the queue’s average size exceeds a particular thres-hold and automatically drops a random packet when theaverage exceeds a higher threshold. This provides earlierfeedback, before the queue overflows, and causes higherbandwidth flows to see a greater number of drops. Second,they recommend continued development of mechanisms todeal with flows that do not respond to congestion in TCP-friendly manner. To date “dealing with” these other flowshas centered on how to constrain or penalize those flows[6, 9]. We recognize the need to protect well-behaved flowsbut also recognize that many applications choose unre-sponsive protocols, such as UDP, because they are con-cerned with throughput and (especially) latency rather thanreliable delivery. Since reliable delivery in TCP dependson timeouts, feedback, and retransmissions, it can be in-compatible with performance goals. Multimedia applica-tions are a prime example of applications that avoid TCPfor performance reasons.

Simply penalizing these non-TCP flows leaves applica-tion developers with some unattractive options. With thedeployment of RED in many routers, application develop-ers must realize UDP flows will be subject to more ag-gressive drop policies than in the past. The developer coulduse TCP and incur overhead for features she may not want.Or, she could use another protocol and be subject to ag-gressive drop policies. Another alternative would be to usea protocol that implements TCP-like congestion manage-ment without the other undesired features such as reliable

1. Overview

As the Internet continues to evolve, increasing atten-tion is being given to recognizing and addressing conges-tion within the network. Particularly, there is increasingfocus on recognizing “well-behaved” flows, those that re-spond to congestion by reducing the load they place on thenetwork. Both Braden et al., and Floyd et al., recognizeTCP flows with correct congestion avoidance implementa-tions as well behaved [2, 6, 7, 1]. They argue that theseflows, as “good network citizens,” should be protected andisolated from the effects of “misbehaving” flows. Misbe-having flows include incorrect implementations of TCP,unresponsive but lightweight UDP connections, and highbandwidth flows that aggressively retransmit when dropsoccur. A recent internet draft considers the problem of con- ∗ Supported by grants from the National Science Foundation

(grants IRIS-9508514 & CCR-9510156), the Advanced Re-search Projects Agency (grant number 96-06580), the IBMCorporation, and a graduate fellowship from the Intel Corpo-ration.

In: Proceedings of the Eighth International Workshop on Network and OperatingSystem Support for Digital Audio and Video, Cambridge, UK, July 1998, pages 193-197.

delivery [3]. The correct long-term solution is to developadaptive applications that respond to congestion notifica-tion (as well as application level feedback). Our approachrecognizes all of these solutions. Our solution is orthogo-nal, providing better support for continuous media flowsin the router.

To mitigate the impact of active queue management onUDP flows, we are working on queue management poli-cies for routers that attempt to balance the concerns ofcongestion avoidance and the requirements for continuousmedia applications using UDP. Specifically, we are ex-perimenting with extensions to the Random Early Detec-tion (RED) packet discard mechanism for providing betterperformance for UDP flows without sacrificing perform-ance for TCP flows. The following briefly outlines thedesign of our RED extension, called RED with Drop Pref-erence Management (RED-DPM), and presents some earlyempirical results that suggest the mechanism performseffectively.

2. Active Queue Management

RED was designed as a mechanism to notify responsiveflows of congestion, either explicitly, by marking packets,or implicitly, by dropping packets of a flow. The likeli-hood of a flow being notified is directly related to its (aver-age) bandwidth utilization. In this way RED avoids globalsynchronization as many flows back off at the same time,and avoids unfairly penalizing bursty traffic. Instead, thoseflows consuming the most bandwidth see the most drops.If responsive, the flow will reduce the load it generates andthe number of drops on that flow will decrease, allowing itto reach an equilibrium state. If the flow is unresponsive,the flow will continue to see a high number of drops, cor-responding to its utilization of a large part of the queue.However, RED assumes that traffic is responsive and thusis vulnerable to misbehaving unresponsive flows. A non-responsive flow could consume a large share of the band-width while other flows decrease their utilization in re-sponse to congestion notification. While RED does droppackets in ratio to the flow’s arrival rate, it still drops anequal percentage of arriving packets from all flows. Soeven well behaved flows continue to see drops if one mis-behaving flow keeps the queue full. As a result of thesedrops, well-behaved flows can back down to extremely low(or no) throughput. Both RED with Penalty Boxes andFRED address this deficiency in RED [6, 9]. Floyd andFall propose mechanisms for identifying several classes offlows: TCP-friendly, unresponsive, and very-high band-width flows [6]. They suggest simply that those flowswhich are not TCP-friendly should be “regulated” (without

2

clearly defining a mechanism for regulation) to preventthem from dominating network resources while TCP-friendly (i.e., responsive) flows continue to be notified ofcongestion via a RED-like mechanism.

FRED is an extension to RED that uses per-active-connection accounting to ensure fairness and isolation be-tween all active flows [9]. While RED drops an equal per-centage of packets across all flows, FRED increases thelikelihood of drops for high bandwidth flows. It does thisby concentrating drop actions on those flows that are ex-ceeding a threshold based on the average per flow logicalqueue length. Further, flows whose logical queue utiliza-tion is below average will not be subject to these drops. Italso concentrates drop actions on those flows that havefailed to respond to notification in the past. Both FREDand RED with penalty boxes take a harsh stance on unre-sponsive flows, constraining them tightly by droppingpotentially all arriving packets once a queue in a router isabove threshold.

3.ment

RED with Drop Preference Manage-We propose a mechanism to constrain misbehavingflows while attempting to provide them with the best per-formance possible under those constraints. A key observa-tion is that latency may be as important a consideration forthese flows as overall bandwidth. Thus we trade-off band-width for (lower) latency. We seek to minimize the latencyof those packets that do arrive at the end system and avoiddelivery of stale packets, packets that are queued in thenetwork and are not likely to arrive in time to be useful.In our scheme we identify multimedia flows with a tag1and maintain per flow statistics for those flows only.Non-tagged flows are subject to the standard RED queuemanagement policy. Packets in tagged flows are subject todrops based on queue length thresholds similar to FREDbut also are subject to drops if packets for that queue ex-ceed a “staleness” threshold. The staleness threshold isbased on the age and depth of the oldest packet for thisflow currently enqueued on the router. Further, anytime adecision to drop a packet is made, an alternative dropmechanism, delete and advance, is used. This mechanismdrops the oldest packet (at the head of the flow’s logicalqueue) so newer, fresher packets are given priority. It alsoreduces the time the new packets spend in the queue by 1 Any of several proposed tagging mechanisms in the IP

header could be used, e.g., the Clark or Nichols schemes [4,10].

3

100 Mbpsftp,UDP blast,& ProSharegeneratorsFreeBSDRouter10 Mbps100 Mbpsftp,UDP blast,& ProSharegeneratorsFreeBSDRouterFigure 1: Experimental network configuration.promoting them into their logical predecessor’s location inthe main queue. The depth of the queue elements for allother flows is unchanged.

With drop preference management we expect to reducethe impact of misbehaving tagged flows on responsiveflows by performing more aggressive dropping of non-TCP-conformant flows. These flows are subjected to aRED test on their (potentially much shorter) logical queueas well as a staleness test. However, UDP flows, and inparticular responsive UDP flows, benefit overall as theirpackets tend to stay closer to the head of the router queueand thus are delivered with lower latency. DPM shouldbenefit both responsive and non-responsive continuousmedia flows. Non-responsive flows will see a large num-ber of drops, just as they would in the face of most con-gestion, but the packets that are delivered will have lowerlatency (because of the delete and advance drop policy).Responsive flows will see this benefit but they will alsobe notified sooner of congestion because the oldest, not thenewest, enqueued packet will be the one dropped. Andmost importantly, a responsive flow will see no dropsonce it has adjusted its load so that it consumes a fair shareof the queue. Low bandwidth non-responsive flows willsee this benefit as well.

serve as a point of congestion. A series of machines at theedges of the network establish a number of connections tomachines on the opposite side of the network. Connec-tions include a mix of TCP connections and UDP connec-tions. In particular, several of the UDP connections arevideoconferencing flows generated by a version of the IntelProShare system (6 flows at approximately 200Kbpseach). We also generate a “UDP blast” of unresponsiveUDP traffic sent from one machine at the maximum rateavailable.

Figure 2 reports some of our early results. It comparesthe performance of TCP (3 machines sending bulk data atthe maximum rate available) and UDP connections (Pro-share) when the routers use RED queue management andRED-DPM management. Figures 2a and 2b, show thethroughput of the TCP connections, first with just TCPand Proshare, then during a period when an unresponsiveUDP blast occurs, and finally back to just the TCP andProshare. Figure 2a shows the performance under REDqueue management. Figure 2b shows the performance un-der RED-DPM queue management. As mentioned above,RED does not effectively protect responsive flows fromnon-responsive ones. During the UDP blast period, theTCP flows see so many drops that they back off entirely,getting no throughput. Figure 2a confirms this shortcom-ing. RED-DPM does provide protection by limiting thenumber of buffers that the unresponsive stream can oc-cupy, thereby ensuring a minimal amount of space existsfor TCP flows. The result, as illustrated in Figure 2b isimproved throughput for TCP.

Figure 2c illustrates the impact of RED-DPM on theProShare (UDP) flows. This shows the latency of the Pro-share streams during the time the UDP blast is running.The top set of points is the latency with RED, while thelower, darker points are the latency with RED-DPM. Inthe case of RED-DPM, although the streams exhibit lossthe delete-and-advance mechanism results in lower end-to-end latency than when plain RED is used.

4. Empirical Results

We have implemented RED-DPM within the ALTQversion of the FreeBSD [8]. The RED-DPM implementa-tion maintains a logical queue for each tagged flow andperforms a threshold and staleness test on each taggedflow’s logical queue immediately prior to the normal REDtest.

To test the implementation we have constructed a sim-ple network consisting of a two switched 100 MbpsEthernet LANs that are interconnected by a 10 MbpsEthernet. FreeBSD routers route traffic between the 100Mbps Ethernets across the 10 Mbps Ethernet as shown inFigure 1. This 10Mbs network creates a bottleneck to

UDP blast400,000

300,000

200,000

100,000

21:32:40 21:33:00 21:33:20

2a) TCP performance under RED.(throughput (bps) v. time)

500,000

UDP blast400,000

300,000

200,000

100,000

21:37:40 21:38:00 21:38:20

2b) TCP performance under RED-DPM.

(throughput (bps) v. time)

UDP blast0.025

RED

0.020

0.015

0.010

0.005

RED-DPM

25s 30s 35s

2c) ProShare performance.(end-to-end latency (secs) v. time)Figure 2: Experimental results. Performance ofTCP and UDP flows during a UDP “blast.”

4

5. Conclusions and Future Work

We have shown preliminary results which indicate thatcurrent active queue management mechanisms, such asRED, can be extended to provide better support for con-tinuous media flows while maintaining or exceeding thecurrent performance offered to “well-behaved” flows. Weintend to conduct further comparisons between DPM andFRED, conduct more experiments with different networkconfigurations and traffic patterns, as well as exploring thedesign space available for thresholds and staleness values.

6. References

[1]R. Braden, Ed., Requirements for Internet Hosts-Communication Layers, RFC-1122, October 1989[2]B. Braden, et al., Recommendations on Queue Man-agement and Congestion Avoidance in the Internet, In-ternet draft draft-irtf-e2e-queue-mgt-01, Feb. 17, 1998.[3]S. Cen, C. Pu, J. Walpole, Flow and Congestion

Control for Internet Streaming Applications, Proc.SPIE/ACM Multimedia Computing and Networking'98, San Jose, CA, January 1998, pages 250-264.[4]D. Clark, J. Wroclawski, An Approach to Service

Allocation in the Internet, Internet Draft draft-clark-diff-svc-alloc-00, July 1997[5]S. Floyd, & V. Jacobson, Random Early Detection

gateways for Congestion Avoidance, IEEE/ACMTrans. on Networking, V.1 N.4, August 1993, p.397-413.[6]S. Floyd, S., & K. Fall, Promoting the Use of End-to-End Congestion Control in the Internet, February1998. (Under submission to IEEE/ACM Trans. onNetworking.)[7]V. Jacobson, Congestion Avoidance and Control,

ACM SIGCOMM '88, August 1988.[8]C. Kenjiro, A Framework for Alternate Queueing:

Towards Traffic Management by PC-UNIX BasedRouters, Accepted to USENIX ‘98, Annual TechnicalConference, New Orleans, LA, June 1998.

[9]D. Lin & R. Morris, Dynamics of Random Early

Detection, Proc. SIGCOMM ‘97.[10]K. Nichols, V. Jacobson , & L. Zhang, A Two-bit

Differentiated Services Architecture for the Internet,Internet-Draft, draft-nichols-diff-svc-arch-00.txt, Nov,1997.