Network Border Patrol: Preventing Congestion Collapse and ...

Network Border Patrol: Preventing Congestion Collapse and ...

Network Border Patrol: Preventing Congestion Collapse and Promoting Fairness in the Internet Celio Albuquerque, Brett J. Vickers, Tatsuya Suda 1 Outline The Problem Existing Solutions

Network Border Patrol Feedback Control Algorithm Rate Control Algorithm Simulations and Testing Conclusions 2 Worcester Polytechnic Institute The Problem

Congestion Collapse Poor retransmission strategies Rise of streaming video in the early 2000s Unfair bandwidth allocations Differing TCP congestion algorithms TCP bias towards short RTT 3 Worcester Polytechnic Institute

Existing Solutions Logic in the Routers Weighted Fair Queueing Core-stateless Fair Queuing CHOKe These are more complicated than FIFO They often do not work if your goal is global maxmin fairness If at router A, flows X and Y are allocated equally, and then only X encounters a later bottleneck, X will be overallocated at A.

4 Worcester Polytechnic Institute Network Border Patrol Schematically similar to core-stateless, pushing flow classification and handling to the edge routers Categorize routers as ingress and egress routers Note that a single router will act as both depending on which flows are being looked at

Ingress routers separate packets into logical flows Egress routers measure the outbound capacity for each logical flow Ingress routers meter logical flows based on egress capacity 5 Worcester Polytechnic Institute Network Border Patrol 6

Worcester Polytechnic Institute Feedback Control Algorithm Controls how the ingress and egress routers exchange packets A feedback packet is an ICMP packet (ping packet) In addition to exchanging flow data, they can be metered to sample internal congestion (through RTT) 7

Worcester Polytechnic Institute Feedback Control Algorithm At ingress, a router categorizes a packet into a flow. The router increases the counter on that flow by n, where n is the size of the packet When the counter for a flow reaches Tx , create a forward packet A forward packet contains a timestamp and a list of unique identifiers for each of the N flows that

the ingress router has seen for a given egress router 8 Worcester Polytechnic Institute Feedback Control Algorithm At egress, a router generates a backward packet every time it receives a forward packet. A backward packet contains an associative array containing each flow and its outbound capacity.

This packet is sent back to the ingress router and is used for traffic flow management (throttling, etc) 9 Worcester Polytechnic Institute Network Border Patrol 10

Worcester Polytechnic Institute Rate Control Algorithm Ingress routers use a Rate Control Algorithm to regulate the rate at which flows enter the network TCP-like implementation with two phases: slow start and congestion avoidance Track the RTT of the feedback packets and use the current RTT and best observed RTT in the algorithm 11

Worcester Polytechnic Institute Rate Control Algorithm 12 Worcester Polytechnic Institute Fairness? NBP by itself is not fair, it only meters a flow based on the share it can claim of its smallest

bottleneck. Thus if flows are competing for a bottleneck, they may still be treated unfairly. Introduce a fair queueing mechanism to NBP, such as CSFQ or rainbow fair queueing. 13 Worcester Polytechnic Institute Enhanced CSFQ CSFQ cannot be easily plugged into NBP because

CSFQ does not preserve the delay characteristics of true fair queueing, because it does not separate flow buffers. This can cause problems with congestion schemes that rely on RTT to throttle without packet drops. Instead of a single buffer, E-CSFQ uses a second, high priority buffer. This buffer is serviced first, and is used by flows using less than their fair share. 14

Worcester Polytechnic Institute Enhanced CSFQ The addition of a second buffer may cause packet reordering issues, but the writers assert this should be rare, because it requires a flow to be recategorized from low to high. The writers say these situations should be unlikely, because it requires a flow to drastically change its flow rate, or for bandwidth to appear. This will inherently mitigate reordering because it allows the low-priority queue to be serviced more

quickly. 15 Worcester Polytechnic Institute Simulations Implemented in ns-2 Experiment one deals with the ability of NBP to prevent congestion collapse Experement two deals with the ability of ECSFQ to provide fair allocations

Experiment three deals with scalability of NBP Experiments were run for 100s 16 Worcester Polytechnic Institute Congestion Collapse Single Link 17 Charts from Albuquerque et al

Worcester Polytechnic Institute Congestion Collapse Multi Links 18 Charts from Albuquerque et al Worcester Polytechnic Institute Fairness Single Link

19 Charts from Albuquerque et al Worcester Polytechnic Institute Fairness Multi Link 20 Charts from Albuquerque et al

Worcester Polytechnic Institute Scalability Multiple Flows 21 Charts from Albuquerque et al Worcester Polytechnic Institute Scalability Crossing Flows

22 Charts from Albuquerque et al Worcester Polytechnic Institute Raised Issues, Future Work Flow classification overhead may become a concern, perhaps a coarser flow classification to reduce the number of macro-flows could be used. Scalability problems may be further reduced by

incorporating trust. Trust other subnets and accept their edge information, too. NBP must be deployed over an entire edge at once. Multicast greatly complicates the situation by breaking the one flow->one egress assumption. 24 Worcester Polytechnic Institute Conclusion

This paper presented a possible solution to the problem of congestion collapse, the fact that fair queuing algorithms can only look-backward NBP uses the idea of a circular communication in router coordination, rather than the one-way from ingress to core of CSFQ. They included a large amount of experimental data to demonstrate their point. Has scalability been fully addressed? 25

Worcester Polytechnic Institute

Recently Viewed Presentations

  • International Business by Daniels and Radebaugh Chapter 3

    International Business by Daniels and Radebaugh Chapter 3

    International Business by Daniels and Radebaugh Chapter 3 Political and Legal Environments Facing Business Objectives To discuss the different functions that political systems perform To compare democratic and totalitarian political regimes and discuss how they can influence managerial decisions To...
  • peelsenglish.weebly.com

    peelsenglish.weebly.com

    (applies to riddles, Beowulf, The Seafarer, etc.) Facts. Originally oral, not written. Employs alliteration (repetition of initial consonant sounds) ... Grand/large in its scope: geography, time. Lofty/formal language. Employs the supernatural.
  • PHASE Point of View WHAT IS A POINT

    PHASE Point of View WHAT IS A POINT

    PHASE Point of View * * this is a format w like to use b/c it forces us to use very vivid, empathetic language, * WHAT IS A POINT OF VIEW? Opportunities Exploration Development Implementation of Needs of Concepts of...
  • Recent Developments on the Test for Summary Judgment in Canada

    Recent Developments on the Test for Summary Judgment in Canada

    A "culture shift" called for by Supreme Court of Canada: Hryniak v. Mauldin, 2014 SCC 7 "When a summary judgment motion allows the judge to find the necessary facts and resolve the dispute, proceeding to trial would generally not be...
  • Winter Literature Focus Unit April Larson Fall 2007

    Winter Literature Focus Unit April Larson Fall 2007

    Winter Literature Focus Unit April Larson Fall 2007
  • Pluripotency of Embryonic Stem Cells

    Pluripotency of Embryonic Stem Cells

    Stem Cells Stem cells are master cells with two important characteristics Unspecialized cells capable of their own renewal Ability to differentiate into different cell types The stem cells may have various differentiation potentials Totipotent Pluripotent Multipotent Unipotent Pluripotent Stem Cells...
  • Project Roslyn - joehummel

    Project Roslyn - joehummel

    What is Project Roslyn? The ".NET Compiler Platform" Replacement of existing .NET compilers with new ones. csc for C#. vbc for VB.NET. SDC Meetup Sept 2014
  • Horowitz - Traumatys | Trauma Services

    Horowitz - Traumatys | Trauma Services

    Introduction "Avant tout, ne causer aucun tort." L'ÉSPT est une merveilleuse opportunité pour comprendre la psyché humaine. Dans le DSM-III, l'ÉSPT est l'une des rares catégories diagnostiques élaborées à partir de perspectives théoriques (surtout le modèle d'Horowitz et celui du...