Introduction

The essential philosophy behind the Internet is expressed by the scalability argument: no protocol, algorithm or service should be introduced into the Internet if it does not scale well. A key corollary to the scalability argument is the end-to-end argument: to maintain scalability, algorithmic complexity should be pushed to the edges of the network whenever possible. Perhaps the best example of the Internet philosophy is TCP congestion control, which is achieved primarily through algorithms implemented at end systems. Unfortunately, TCP congestion control also illustrates some of the shortcomings of the end-to-end argument.

As a result of its strict adherence to end-to-end congestion control, the current Internet suffers from two maladies: congestion collapse from undelivered packets, and unfair allocations of bandwidth between competing traffic flows. The first malady--congestion collapse from undelivered packets--arises when bandwidth is continuously consumed by packets that are dropped before reaching their ultimate destinations [1]. Unresponsive flows, which are becoming increasingly prevalent in the Internet as network applications using audio and video become more popular, are the primary cause of this type of congestion collapse, and the Internet currently has no way of effectively regulating them.

The second malady--unfair bandwidth allocation--arises in the Internet for a variety of reasons, one of which is the presence of unresponsive flows. Adaptive flows (e.g., TCP flows) that respond to congestion by rapidly reducing their transmission rates are likely to receive unfairly small bandwidth allocations when competing with unresponsive or malicious flows. The Internet protocols themselves also introduce unfairness. The TCP algorithm, for instance, inherently causes each TCP flow to receive a bandwidth that is inversely proportional to its round trip time [2]. Hence, TCP connections with short round trip times may receive unfairly large allocations of network bandwidth when compared to connections with longer round trip times.

These maladies--congestion collapse from undelivered packets and unfair bandwidth allocations--have not gone unrecognized. Some have argued that they may be mitigated through the use of improved packet scheduling [3] or queue management [4] mechanisms in network routers. For instance, per-flow packet scheduling mechanisms like Weighted Fair Queueing (WFQ) [5,6] attempt to offer fair allocations of bandwidth to flows contending for the same link. So does Core-Stateless Fair Queueing (CSFQ) [7], an approximation of WFQ that requires only edge routers to maintain per-flow state. Active queue management mechanisms like Fair Random Early Detection (FRED) [8] achieve an effect similar to fair queueing by discarding packets from flows that are using more than their fair share of a link's bandwidth. All of these mechanisms are more complex and expensive to implement than simple FIFO queueing, but they reduce the causes of unfairness and congestion collapse in the Internet. Nevertheless, they do not eradicate them. For illustration of this fact, consider the example shown in Figure 1. In this example, two unresponsive flows compete for bandwidth in a network containing two bottleneck links arbitrated by a fair queueing mechanism. At the first bottleneck link (R₁-R₂), fair queueing ensures that each flow receives half of the link's available bandwidth (750 kbps). On the second bottleneck link (R₂-S₄), much of the traffic from flow B is discarded due to the link's limited capacity (128 kbps). Hence, flow A achieves a throughput of 750 kbps and flow B achieves a throughput of 128 kbps. Clearly, congestion collapse has occurred, because flow B packets, which are ultimately discarded on the second bottleneck link, unnecessarily limit the throughput of flow A across the first bottleneck link. Furthermore, while both flows receive equal bandwidth allocations on the first bottleneck link, their allocations are not globally max-min fair. A globally max-min fair allocation of bandwidth would have been 1.372 Mbps for flow A and 128 kbps for flow B.

Figure 1: Example of a network which experiences congestion collapse

This example, which is a variant of an example presented in [1], illustrates the inability of local scheduling mechanisms, such as WFQ, to eliminate congestion collapse and achieve global max-min fairness without the assistance of additional network mechanisms.

Jain et al. have proposed several rate control algorithms that are able to prevent congestion collapse and provide global max-min fairness to competing flows [10]. These algorithms (e.g., ERICA, ERICA+) are designed for the ATM Available Bit Rate (ABR) service and require all network switches to compute fair allocations of bandwidth among competing connections. However, these algorithms are not easily tailorable to the current Internet, because they violate the Internet design philosophy of keeping router implementations simple and pushing complexity to the edges of the network.

Floyd and Fall have approached the problem of congestion collapse by proposing low-complexity router mechanisms that promote the use of adaptive or ``TCP-friendly'' end-to-end congestion control [1]. Their suggested approach requires selected gateway routers to monitor high-bandwidth flows in order to determine whether they are responsive to congestion. Flows that are determined to be unresponsive are penalized by a higher packet discarding rate at the gateway router. A limitation of this approach is that the procedures currently available to identify unresponsive flows are somewhat arbitrary and not always successful [7].

In this paper, we introduce and investigate a new Internet traffic control mechanism called Network Border Patrol (NBP). The basic principle of NBP is to compare, at the borders of the network, the rates at which each flow's packets are entering and leaving the network. If packets are entering the network faster than they are leaving it, then the network is very likely to be buffering or, worse yet, discarding the flow's packets. In other words, the network is receiving more packets than it can handle. NBP prevents this scenario by ``patrolling'' the network's borders, ensuring that packets do not enter the network at a rate greater than they are able to leave it. This has the beneficial effect of preventing congestion collapse from undelivered packets, because an unresponsive flow's otherwise undeliverable packets never enter the network in the first place.

NBP's prevention of congestion collapse comes at the expense of some additional network complexity, since routers at the borders of the network (i.e., edge routers) are expected to monitor and control the rates of individual flows. NBP also introduces an added communication overhead, since in order for an edge router to know the rate at which its packets are leaving the network, it must exchange feedback with other edge routers. However, unlike other existing approaches to the problem of congestion collapse, NBP's added complexity is isolated to edge routers; routers within the core of the network remain unchanged. Moreover, end systems operate in total ignorance of the fact that NBP is implemented in the network, so no changes to transport protocols are necessary.

Note that the primary goal of NBP is to prevent congestion collapse from undelivered packets. On its own, NBP cannot provide global max-min fairness to competing network flows. Nevertheless, when combined with fair queueing at core routers, NBP can achieve approximate global max-min fairness, as we will show later in this paper.

The remainder of this paper is organized as follows. In section II, we describe the architectural components of the Network Border Patrol mechanism in further detail and present the feedback and rate control algorithms used by NBP edge routers to prevent congestion collapse. In section III, we present the results of several simulations, which illustrate the ability of NBP to avoid congestion collapse and, when combined with a fair queueing algorithm in core routers, to provide global max-min fairness to competing network flows. In section IV, we discuss several implementation and scalability issues that must be addressed in order to make deployment of NBP feasible in the Internet. Finally, in section V we provide some concluding remarks.