21-06-2013, 02:37 PM
Network Border Patrol: Preventing Congestion Collapse and Promoting
Fairness in the Internet
Network Border Patrol.pdf (Size: 155.27 KB / Downloads: 70)
Abstract
The end-to-end nature of Internet congestion control is an important factor in its scalability and robustness. However, end-to-end
congestion control algorithms alone are incapable of preventing the congestion collapse and unfair bandwidth allocations created by
applications that are unresponsive to network congestion. To address this flaw, we propose and investigate a novel congestion avoidance
mechanism called Network Border Patrol (NBP). NBP relies on 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. An enhanced core-stateless fair queueing mechanism
is proposed in order to provide fair bandwidth allocations among competing flows. NBP is 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 that, when combined with fair queueing, NBP achieves approximately max-min fair bandwidth allocations for
competing network flows
RELATED WORK
The maladies of congestion collapse from undelivered packets and of unfair bandwidth allocations have not
gone unrecognized. Some have argued that there are social incentives for multimedia applications to be friendly
to the network, since an application would not want to be held responsible for throughput degradation in the
Internet. However, malicious denial-of-service attacks using unresponsive UDP flows are becoming disturbingly
frequent in the Internet and they are an example that the Internet cannot rely solely on social incentives to control
congestion or to operate fairly.
Some have argued that these maladies may be mitigated through the use of improved packet scheduling [12] or
queue management [13] mechanisms in network routers. For instance, per-flow packet scheduling mechanisms
likeWeighted Fair Queueing (WFQ) [7], [8] attempt to offer fair allocations of bandwidth to flows contending for
the same link. So do Core-Stateless Fair Queueing (CSFQ) [9], Rainbow Fair Queueing [10] and CHOKe [11],
which are approximations of WFQ that do not require core routers to maintain per-flow state. Active queue
management mechanisms like Fair Random Early Detection (FRED) [14] also attempt to limit malicious or
unresponsive flows by preferentially 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. Two unresponsive flows
compete for bandwidth in a network containing two bottleneck links arbitrated by a fair queueing mechanism.
At the first bottleneck link (R1-R2), fair queueing ensures that each flow receives half of the link’s available
bandwidth (750 kbps).
NETWORK BORDER PATROL
Network Border Patrol is a network layer congestion avoidance protocol that is aligned with the core-stateless
approach. The core-stateless approach, which has recently received a great deal of research attention [18], [9],
allows routers on the borders (or edges) of a network to perform flow classification and maintain per-flow state
but does not allow routers at the core of the network to do so. Figure 2 illustrates this architecture. As in other
work on core-stateless approaches, we draw a further distinction between two types of edge routers. Depending
on which flow it is operating on, an edge router may be viewed as an ingress or an egress router. An edge router
operating on a flow passing into a network is called an ingress router, whereas an edge router operating on a flow
passing out of a network is called an egress router. Note that a flow may pass through more than one egress (or
ingress) router if the end-to-end path crosses multiple networks.
The Feedback Control Algorithm
The feedback control algorithm determines how and when feedback packets are exchanged between edge
routers. Feedback packets take the form of ICMP packets and are necessary in NBP for three reasons. First,
they allow egress routers to discover which ingress routers are acting as sources for each of the flows they are
monitoring. Second, they allow egress routers to communicate per-flow bit rates to ingress routers. Third, they
allow ingress routers to detect incipient network congestion by monitoring edge-to-edge round trip times.
CONCLUSION
In this paper, we have presented a novel congestion avoidance mechanism for the Internet called Network Border
Patrol and an enhanced core-stateless fair queuing mechanism. Unlike existing Internet congestion control
approaches, which rely solely on end-to-end control, NBP is able to prevent congestion collapse from undelivered
packets. It does this by ensuring at the border of the network that each flow’s packets do not enter the
network faster than they are able to leave it. NBP requires no modifications to core routers nor to end systems.
Only edge routers are enhanced so that they can perform the requisite per-flow monitoring, per-flow rate control
and feedback exchange operations.