Network border patrol: preventing congestion collapse and promoting fairness in the Internet

The Internet's excellent scalability and robustness result in part from the end-to-end nature of Internet congestion control. End-to-end congestion control algorithms alone, however, are unable to prevent the congestion collapse and unfairness created by applications that are unresponsive to network congestion. To address these maladies, we propose and investigate a novel congestion-avoidance mechanism called network border patrol (NBP). NBP entails the exchange of feedback between routers at the borders of a network in order to detect and restrict unresponsive traffic flows before they enter the network, thereby preventing congestion within the network. Moreover, NBP is complemented with the proposed enhanced core-stateless fair queueing (ECSFQ) mechanism, which provides fair bandwidth allocations to competing flows. Both NBP and ECSFQ are compliant with the Internet philosophy of pushing complexity toward the edges of the network whenever possible. Simulation results show that NBP effectively eliminates congestion collapse and that, when combined with ECSFQ, approximately max-min fair bandwidth allocations can be achieved for competing flows.     

A survey on TCP-friendly congestion control

New trends in communication, in particular the deployment of multicast and real-time audio/video streaming applications, are likely to increase the percentage of non-TCP traffic in the Internet. These applications rarely perform congestion control in a TCP-friendly manner; they do not share the available bandwidth fairly with applications built on TCP, such as Web browsers, FTP, or e-mail clients. The Internet community strongly fears that the current evolution could lead to congestion collapse and starvation of TCP traffic. For this reason, TCP-friendly protocols are being developed that behave fairly with respect to coexistent TCP flows. We present a survey of current approaches to TCP friendliness and discuss their characteristics. Both unicast and multicast congestion control protocols are examined, and an evaluation of the different approaches is presented     

Promoting the use of end-to-end congestion control in the Internet

This paper considers the potentially negative impacts of an increasing deployment of non-congestion-controlled best-effort traffic on the Internet. These negative impacts range from extreme unfairness against competing TCP traffic to the potential for congestion collapse. To promote the inclusion of end-to-end congestion control in the design of future protocols using best-effort traffic, we argue that router mechanisms are needed to identify and restrict the bandwidth of selected high-bandwidth best-effort flows in times of congestion. The paper discusses several general approaches for identifying those flows suitable for bandwidth regulation. These approaches are to identify a high-bandwidth flow in times of congestion as unresponsive, “not TCP-friendly”, or simply using disproportionate bandwidth. A flow that is not “TCP-friendly” is one whose long-term arrival rate exceeds that of any conformant TCP in the same circumstances. An unresponsive flow is one failing to reduce its offered load at a router in response to an increased packet drop rate, and a disproportionate-bandwidth flow is one that uses considerably more bandwidth than other flows in a time of congestion     

Game of protocols: Is QUIC ready for prime time streaming?

Quick User Datagram Protocol (UDP) Internet Connections (QUIC) is an experimental and low‐latency transport protocol proposed by Google, which is still being improved and specified in the Internet Engineering Task Force (IETF). The viewer's quality of experience (QoE) in HTTP adaptive streaming (HAS) applications may be improved with the help of QUIC's low‐latency, improved congestion control, and multiplexing features. We measured the streaming performance of QUIC on wireless and cellular networks in order to understand whether the problems that occur when running HTTP over TCP can be reduced by using HTTP over QUIC. The performance of QUIC was tested in the presence of network interface changes caused by the mobility of the viewer. We observed that QUIC resulted in quicker start of media streams, better streaming, and seeking experience, especially during the higher levels of congestion in the network and had a better performance than TCP when the viewer was mobile and switched between the wireless networks. Furthermore, we measured QUIC's performance in an emulated network that had a various amount of losses and delays to evaluate how QUIC's multiplexing feature would be beneficial for HAS applications. We compared the performance of HAS applications using multiplexing video streams with HTTP/1.1 over multiple TCP connections to HTTP/2 over one TCP connection and to QUIC over one UDP connection. To that effect, we observed that QUIC provided better performance than TCP on a network that had large delays. However, QUIC did not provide a significant improvement when the loss rate was large. Finally, we analyzed the performance of the congestion control mechanisms implemented by QUIC and TCP, and tested their ability to provide fairness among streaming clients. We found that QUIC always provided fairness among QUIC flows, but was not always fair to TCP.     

Towards end-host-based identification of competing protocols against TCP in a bottleneck link

Classical Transmission Control Protocol (TCP) designs have never considered the identity of the competing transport protocol as useful information to TCP sources in congestion control mechanisms. When competing against a TCP flow on a bottleneck link, a User Datagram Protocol (UDP) flow can unfairly occupy the entire link bandwidth and suffocate all TCP flows on the link. If it were possible for a TCP source to know the type of transport protocol that deprives it of link access, perhaps it would be better for the TCP source to react in a way which prevents total starvation. In this paper, we use coefficient of variation and power spectral density of throughput traces to identify the presence of UDP transport protocols that compete against TCP flows on bottleneck links. Our results show clear traits that differentiate the presence of competing UDP flows from TCP flows independent of round-trip times variations. Signatures that we identified include an increase in coefficient of variation whenever a competing UDP flow joins the bottleneck link for the first time, noisy spectral density representation of a TCP flow when competing against a UDP flow in the bottleneck link, and a dominant frequency with outstanding power in the presence of TCP competition only. In addition, the results show that signatures for congestion caused by competing UDP flows are different from signatures due to congestion caused by competing TCP flows regardless of their round-trip times. The results in this paper present the first steps towards development of more ’intelligent’ congestion control algorithms with added capability of knowing the identity of aggressor protocols against TCP, and subsequently using this additional information for rate control.     

End-to-end rate-based congestion control: convergence properties and scalability analysis

We study several properties of binary-feedback congestion control in rate-based applications. We first derive necessary conditions for generic binary-feedback congestion control to converge to fairness monotonically (which guarantees asymptotic stability of the fairness point) and show that AIMD is the only TCP-friendly binomial control with monotonic convergence to fairness. We then study the steady-state behavior of binomial controls with n competing flows on a single bottleneck. Our main result here shows that combined probing for new bandwidth by all flows results in significant overshoot of the available bandwidth and rapid (often super-linear as a function of n) increase in packet loss. We also show that AIMD has the best scalability and lowest packet-loss increase among all TCP-friendly binomial schemes. We conclude the paper by deriving the conditions necessary to achieve constant packet loss regardless of the number of competing flows, n, and, in both simulation and streaming experiments, examine one new scheme, called ideally scalable congestion control, with such constant packet loss.     

Fair internet traffic integration: network flow models and analysis

We use flow-level models to study the integration of two types of Internet traffic, elastic file transfers and streaming traffic. Previous studies have concentrated on just one type of traffic, such as the flow level models of Internet congestion control, where network capacity is dynamically shared between elastic file transfers, with a randomly varying number of such flows. We consider the addition of streaming traffic in two cases, under a fairness assumption that includestcp-friendliness as a special case, and under certain admission control schemes. We establish sufficient conditions for stability, using a fluid model of the system. We also assess the impact of each traffic type on the other: file transfers are seen by streaming traffic as reducing the available capacity, whereas for file transfers the presence of streaming traffic amounts to replacing sharp capacity constraints by relaxed constraints. Simulation results suggest that the integration of streaming traffic and file transfers has a stabilizing effect on the variability of the number of flows present in the system.     

Adaptive available bandwidth estimation for internet video streaming

In this study, an adaptive available bandwidth estimation approach that is suitable for Internet video streaming is developed. The algorithm exploits repetitive measurements and uses this redundancy to improve its video adaptation decision. The importance of available bandwidth estimation in Internet applications has recently increased particularly because of the heterogeneity of the network links. Many of the Internet paths may contain wired and wireless links in which loss may happen due to congestion as well as link errors. Hence, loss rate by itself is not a sufficient statistics for monitoring purposes. If the loss is due to congestion, video quality can then be decreased whereas if the loss is due to link error, no such action is necessary. Moreover, in video streaming, such an estimate can be used to determine the new video rate if the quality is to be increased. In our approach, active probing packets are used to estimate bandwidth in very short time duration. The novelty of our estimator is its adaptivity in the sense that the overhead caused by the estimator is automatically reduced when congestion builds up. The trade off is reduced accuracy. Such accuracy is not needed under congestion anyway and when things get back to normal, our estimator turns back to normal operation mode. We have integrated our algorithm into our video streamer and carried out experiments on both simulated and actual streaming applications on the Internet. The results indicate that our estimator algorithm increases streaming performance substantially.     

TCP-LP: low-priority service via end-point congestion control

Service prioritization among different traffic classes is an important goal for the Internet. Conventional approaches to solving this problem consider the existing best-effort class as the low-priority class, and attempt to develop mechanisms that provide "better-than-best-effort" service. In this paper, we explore the opposite approach, and devise a new distributed algorithm to realize a low-priority service (as compared to the existing best effort) from the network endpoints. To this end, we develop TCP Low Priority (TCP-LP), a distributed algorithm whose goal is to utilize only the excess network bandwidth as compared to the "fair share" of bandwidth as targeted by TCP. The key mechanisms unique to TCP-LP congestion control are the use of one-way packet delays for early congestion indications and a TCP-transparent congestion avoidance policy. The results of our simulation and Internet experiments show that: 1) TCP-LP is largely non-intrusive to TCP traffic; 2) both single and aggregate TCP-LP flows are able to successfully utilize excess network bandwidth; moreover, multiple TCP-LP flows share excess bandwidth fairly; 3) substantial amounts of excess bandwidth are available to the low-priority class, even in the presence of "greedy" TCP flows; 4) the response times of web connections in the best-effort class decrease by up to 90% when long-lived bulk data transfers use TCP-LP rather than TCP; 5) despite their low-priority nature, TCP-LP flows are able to utilize significant amounts of available bandwidth in a wide-area network environment.     

A stateless fairness-driven active queue management scheme for efficient and fair bandwidth allocation in congested Internet routers

Fair bandwidth sharing is important for the Internet architecture to be more accommodative of the heterogeneity. The Internet relies primarily on the end-systems to cooperatively deploy congestion control mechanisms for achieving high network utilization and some degree of fairness among flows. However, the cooperative behavior may be abandoned by some end-systems that act selfishly to be more competitive through bandwidth abuse. The result can be severe unfairness and even congestion collapse. Fairness-driven active queue management, thus, becomes essential for allocating the shared bottleneck bandwidth fairly among competing flows. This paper proposes a novel stateless active queue management algorithm, termed CHOKeH, to enforce fairness in bottleneck routers. CHOKeH splits the queue into dynamic regions at each packet arrival and treats each region differently for performing matched-drops using a dynamically updated drawing factor, which is based on the level of queue occupancy and the buffer size. In this way, CHOKeH can effectively identify and restrict unfair flows from dominating the bandwidth by discarding more packets from these flows. The performance of CHOKeH is studied through extensive simulations. The results demonstrate that CHOKeH is well suited for fair bandwidth allocation even in the presence of multiple unresponsive flows and across a wider range of buffer sizes. The results also show the ability of CHOKeH to provide inter-protocol and intra-protocols fairness and protection for short-lived flows. With a low per-packet-processing complexity, CHOKeH is amenable to implementation in core routers to offer an effective incentive structure for end-systems to self-impose some form of congestion control.     

Design and evaluation of an efficient traffic control scheme for integrated voice,video, and data over asynchronous transfer mode networks: Explicit allowed rate algorithm

Asychronous transfer mode (ATM) networks are high‐speed networks with guaranteed quality of service. The main cause of congestion in ATM networks is over utilization of physical bandwidth. Unlike constant bit‐rate (CBR) traffic, the bandwidth reserved by variable bit‐rate (VBR) traffic is not fully utilized at all instances. Hence, this unused bandwidth is allocated to available bit‐rate (ABR) traffic. As the bandwidth used by VBR traffic changes, available bandwidth for ABR traffic varies; i.e., available bandwidth for ABR traffic is inversely proportional to the bandwidth used by the VBR traffic. Based on this fact, a rate‐based congestion control algorithm, Explicit Allowed Rate Algorithm (EARA), is presented in this paper. EARA is compared with Proportional Rate Control Algorithm (PRCA) and Explicit Rate Indication Congestion Avoidance Algorithm (ERICA), in both LAN and WAN environments. Simulations of all three algorithms are conducted under both congestion and fairness configurations with simultaneous generation of CBR, rt‐VBR, nrt‐VBR and ABR traffic. The results show that, with very small over‐head on the switch, EARA significantly decreases the required buffer space and improves the network throughput. Copyright © 1999 John Wiley & Sons, Ltd.     

QoS routing in ad hoc wireless networks

The emergence of nomadic applications have generated much interest in wireless network infrastructures that support real-time communications. We propose a bandwidth routing protocol for quality-of-service (QoS) support in a multihop mobile network. The QoS routing feature is important for a mobile network to interconnect wired networks with QoS support (e.g., ATM, Internet, etc.). The QoS routing protocol can also work in a stand-alone multihop mobile network for real-time applications. This QoS routing protocol contains end-to-end bandwidth calculation and bandwidth allocation. Under such a routing protocol, the source (or the ATM gateway) is informed of the bandwidth and QoS available to any destination in the mobile network. This knowledge enables the establishment of QoS connections within the mobile network and the efficient support of real-time applications. In addition, it enables more efficient call admission control. In the case of ATM interconnection, the bandwidth information can be used to carry out intelligent handoff between ATM gateways and/or to extend the ATM virtual circuit (VC) service to the mobile network with possible renegotiation of QoS parameters at the gateway. We examine the system performance in various QoS traffic flows and mobility environments via simulation. Simulation results suggest distinct performance advantages of our protocol that calculates the bandwidth information. It is particularly useful in call admission control. Furthermore, “standby” routing enhances the performance in the mobile environment. Simulation experiments show this improvement     

Accelerating peer-to-peer networks for video streaming using multipoint-to-point communication

Existing transport layer protocols such as TCP and UDP are designed specifically for point-to-point communication. The increased popularity of peer-to-peer networking has brought changes in the Internet that provided users with potentially multiple replicated sources for content retrieval. However, applications that leverage such parallelism have thus far been limited to non-real-time file downloads. In this article we consider the problem of multipoint-to-point video streaming over peer-to-peer networks. We present a transport layer protocol called R/sup 2/CP that effectively enables real-time multipoint-to-point video streaming. R/sup 2/CP is a receiver-driven multistate transport protocol. It requires no coordination between multiple sources, accommodates flexible application layer reliability semantics, uses TCP-friendly congestion control, and delivers to the video stream the aggregate of the bandwidths available on the individual paths. Simulation results show great performance benefits using R/sup 2/CP in peer-to-peer networks.     

Using Quick‐Start to enhance TCP‐friendly rate control performance in bidirectional satellite networks

In the not so distant future, we envisage an Internet where the biggest share of capacity is used by streaming applications. To avoid congestion collapse from unresponsive flows calls for a robust and ubiquitous end‐to‐end multimedia congestion control mechanism, such as TCP‐friendly rate control (TFRC), which provides fair sharing with the other Internet traffic. This paper therefore analyses the implications of using rate‐adaptive congestion control over satellite links that utilize demand allocation multiple access (DAMA) to maximize satellite transponder utilization. The interaction between TFRC and DAMA is explored using simulations supported by fluidic flow models. The analysis shows that DAMA reduces the start‐up phase of TFRC, causing non‐negligible delays. To mitigate this problem, we propose a new cross‐layer method based on the Quick‐Start mechanism. This can accelerate the start‐up of multimedia flows by a judicious allocation of additional capacity derived from cross‐layer signalling. Copyright © 2009 John Wiley & Sons, Ltd.     

Adaptive systems for improved media streaming experience

Supporting streaming media applications over current packet network infrastructures represents a challenging task in many regards. For one, the lack of quality of service (QoS) guarantees in existing networks such as the Internet means that time-constrained media packets will face dynamic variations in bandwidth, loss rate, and delay as they traverse the network from the sender to the receiver. The variable rate of media traffic represents yet another difficulty when transmission constraints need to be met. Finally, the heterogeneity of client devices and access bandwidth coupled with custom user preferences exacerbate the problem of smooth and quality-optimized media playback even further. In this article we provide an overview of the various techniques for media and streaming strategy adaptation, which can be employed to deal with the difficulties imposed by such dynamic environments. These techniques depend on the characteristics of the media application, in particular on the network streaming infrastructure and the timing constraints imposed on the media packets' delivery. We survey adaptation techniques that act on the encoding of the multimedia information, on the scheduling of the media packets, or that try to combat transmission errors. We also briefly overview some media-friendly networking solutions, which contribute to increased QoS by incorporating some level of intelligence in intermediate network nodes. Finally, we describe a few open challenges in media streaming, emphasizing strategies based on promising cross-layer approaches where adaptation strategies are applied in a coordinated manner, across different layers of the network protocol stack     

ARC: the analytical rate control scheme for real-time traffic in wireless networks

Next-generation wireless Internet (NGWI) is expected to provide a wide range of services including real-time multimedia to mobile users. However, the real-time multimedia traffic transport requires rate control deployment to protect shared Internet from unfairness and further congestion collapse. The transmission rate control method must also achieve high throughput and satisfy multimedia requirements such as delay or jitter bound. However, the existing solutions are mostly for the wired Internet, and hence, they do not address the challenges in the wireless environments which are characterized by high bit error rates. In this paper, a new analytical rate control (ARC) protocol for real-time multimedia traffic over wireless networks is presented. It is intended to achieve high throughput and multimedia support for real-time traffic flows while preserving fairness to the TCP sources sharing the same wired link resources. Based on the end-to-end path model, the desired behavior of a TCP source over lossy links is captured via renewal theory. The resulting asymptotic throughput equation is designated as the driving equation for the proposed rate control method. Performance evaluation via simulation experiments reveals that ARC achieves high throughput and meets multimedia traffic expectations without violating good citizenship rules for the shared Internet.     

ISMA interoperability and conformance

Ubiquitous streaming of rich media has long been one of the most difficult challenges, and at the same time it has invoked the most rewarding killer applications. With the increasing bandwidth available to users, expanding pervasiveness of multimedia-ready devices, and growth in rich media content, the dream of streaming rich media is coming closer to reality. However, interoperability is still one of the important remaining challenges. The Internet Streaming Media Alliance (ISMA) is working toward the goal of interoperability of streaming rich media (video, audio, and data) over Internet protocol (IP) networks by developing open streaming standards. Some of ISMA's interoperability testing work takes the form of plugfests that provide intense interactions and exchange of media streams among tools and systems. This article describes how ISMA addresses interoperability testing and conformance, working toward the vision of seamless interworking streaming media devices.     

A low-state packet marking framework for approximate fair bandwidth allocation

Misbehaving, non-congestion-reactive traffic is on the rise in the Internet. One way to control misbehaving traffic is to enforce local fairness among flows. Locally fair policies, such as fair-queueing and other fair AQM schemes, are inadequate to simultaneously control misbehaving traffic and provide high network utilization. We thus need to enforce globally fair bandwidth allocations. However, such schemes have typically been stateful and complex to implement and deploy. In this letter, we present a low state, lightweight scheme based on stateless fair packet marking at network edges followed by RIO queueing at core nodes, to control misbehaving flows with more efficient utilization of network bandwidth. Additionally, with low-state feedback from bottleneck routers, we show that, in practice, we can approximate global max-min fairness within an island of routers. We show, using simulations, that we can indeed control misbehaving flows and provide more globally fair bandwidth allocation.     

Wireless video streaming with TCP and simultaneous MAC packet transmission (SMPT)

Video streaming is expected to account for a large portion of the traffic in future networks, including wireless networks. It is widely accepted that the user datagram protocol (UDP) is the preferred transport protocol for video streaming and that the transmission control protocol (TCP) is unsuitable for streaming. The widespread use of UDP, however, has a number of drawbacks, such as unfairness and possible congestion collapse, which are avoided by TCP. In this paper we investigate the use of TCP as the transport layer protocol for streaming video in a multi‐code CDMA cellular wireless system. Our approach is to stabilize the TCP throughput over the wireless links by employing a recently developed simultaneous MAC packet transmission (SMPT) approach at the link layer. We study the capacity, i.e. the number of customers per cell, and the quality of service for streaming video in the uplink direction. Our extensive simulations indicate that streaming over TCP in conjunction with SMPT gives good performance for video encoded in a closed loop, i.e. with rate control. We have also found that TCP is unsuitable (even in conjunction with SMPT) for streaming the more variable open‐loop encoded video. Copyright © 2004 John Wiley & Sons, Ltd.