29-08-2014, 11:26 AM
Network Border Patrol:
Preventing Congestion Collapse and Promoting
Fairness in the Internet
Network Border Patrol.pdf (Size: 155.27 KB / Downloads: 44)
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.
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.
Architectural Components
The only components of the network that require modification by NBP are edge routers; the input ports of
egress routers must be modified to perform per-flow monitoring of bit rates, and the output ports of ingress
routers must be modified to perform per-flow rate control. In addition, both the ingress and the egress routers
must be modified to exchange and handle feedback.
Figure 3 illustrates the architecture of an egress router’s input port. Data packets sent by ingress routers
arrive at the input port of the egress router and are first classified by flow. In the case of IPv6, this is done
by examining the packet header’s flow label, whereas in the case of IPv4, it is done by examining the packet’s
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.
Scalability
Scalability is perhaps the most important performance measure of any traffic control mechanism. As we saw in
the previous section, Network Border Patrol is a core-stateless traffic control mechanism that effectively prevents
congestion collapse and provides approximate max-min fairness. However, NBP’s scalability is highly dependent
upon per-flow management performed by edge routers. In a large scale network, the overheads of maintaining
per-flow state, communicating per-flow feedback, and performing per-flow rate control and rate monitoring may
become inordinately expensive. The number of border routers, the number of flows, and the load of the traffic