EE122: Switching and Forwarding

EE122: Switching and Forwarding

Network layer (addendum) Slides adapted from material by Nick McKeown and Kevin Lai Routers .. . .. . A router consists - A set of input interfaces at which packets arrive - A set of output interfaces from which packets depart - Some form of interconnect connecting inputs to outputs Router implements two main functions - Forward packet to corresponding output interface - Manage bandwidth and buffer space resources CS640, UW-Madison 2 What a Router Looks Like Cisco GSR 12416

Juniper M160 19 19 Capacity: 160Gb/s Power: 4.2kW 3ft 6ft 2ft Slide by Nick McKeown Capacity: 80Gb/s Power: 2.6kW 2.5ft CS640, UW-Madison 3 Why Understand Router Design Many companies make switches and routers - e.g., Cisco, Juniper, Nortel

Many other devices have a similar structure - e.g., PCs internal interconnect, multi-processor interconnect Switch design dictates what can be done at higher layers - e.g., per flow state is expensive,the need to minimize per packet processing time CS640, UW-Madison 4 Why Do We Need Faster Routers? 1. 2. To prevent routers becoming the bottleneck in the Internet. To increase POP capacity, and to reduce cost, size and power. CS640, UW-Madison 5

Requirements Power - generates heat, costs money - < 5kW Size - space costs money - < 2m3 Bandwidth Ports - number of external links Price Some customers want - Multicast - Quality of Service CS640, UW-Madison

6 Generic Router Architecture Input and output interfaces are connected through an interconnect A interconnect can be implemented by input interface output interface Interconnect - Shared memory low capacity routers (e.g., PC-based routers) - Shared bus Medium capacity routers - Point-to-point (switched) bus High capacity routers CS640, UW-Madison 7

First Generation Routers Shared Backplane CP I Line U nte rfa ce M em or y CPU Route Table Buffer Memory Line Interface Line Interface Line Interface MAC

MAC MAC Typically <0.5Gb/s aggregate capacity Slide by Nick McKeown CS640, UW-Madison 8 Second Generation Routers CPU Route Table Buffer Memory Line Card Line Card Line Card

Buffer Memory Buffer Memory Buffer Memory Fwding Cache Fwding Cache Fwding Cache MAC MAC MAC Typically <5Gb/s aggregate capacity Slide by Nick McKeown CS640, UW-Madison 9

Third Generation Routers Switched Backplane Li I CPnt ne Uerf ac e M em or y Line Card CPU Card Line Card Local Buffer Memory Routing Table

Local Buffer Memory Fwding Table Fwding Table MAC MAC Typically <50Gb/s aggregate capacity Slide by Nick McKeown CS640, UW-Madison 10 Speedup C input/output link capacity RI maximum rate at which an input interface can send data into interconnect

RO maximum rate at which an output can read data from interconnect B maximum aggregate interconnect transfer rate Interconnect speedup: B/C Input speedup: RI/C Output speedup: RO/C input interface output interface Interconnect C CS640, UW-Madison

RI B RO C 11 Typical Functions Performed by Input Interface on Data Path Packet forwarding: decide to which output interface to forward each packet based on the information in packet header - examine packet header - lookup in forwarding table - update packet header CS640, UW-Madison 12 Typical Functions Performed by Output Interface

Buffer management: decide when and which packet to drop Scheduler: decide when and which packet to transmit Buffer Scheduler 1 2 CS640, UW-Madison 13 Typical Functions Performed by Output Interface (contd) Packet classification: map each packet to a predefined flow/connection (for datagram forwarding) - use to implement more sophisticated services (e.g., QoS) flow 1 1 2 Classifier flow 2

Scheduler flow n Buffer management Flow: a subset of packets between any two endpoints in CS640, UW-Madison 14 the network Interconnect Point-to-point switch allows to simultaneously transfer a packet between any two disjoint pairs of input-output interfaces Goal: come-up with a schedule that - Provide Quality of Service - Maximize router throughput Challenges: - Address head-of-line blocking at inputs

- Resolve input/output speedups contention - Avoid packet dropping at output if possible Note: packets are fragmented in fix sized cells at inputs and reassembled at outputs CS640, UW-Madison 15 Output Queued (OQ) Routers Only output interfaces store packets Advantages input interface - Easy to design algorithms: only one congestion point output interface Backplane Disadvantages

- Requires an output speedup of N, where N is the number of interfaces not feasible CS640, UW-Madison RO C 16 Input Queueing (IQ) Routers Only input interfaces store packets Advantages input interface - Easy to built Store packets at inputs if contention at outputs - Relatively easy to design algorithms Only one congestion point, but not output need to implement backpressure

output interface Backplane Disadvantages - Hard to achieve utilization 1 (due to output contention, head-of-line blocking) However, theoretical and simulation results show that for realistic traffic an input/output speedup of 2 is enough to achieve utilizations close to 1 CS640, UW-Madison RO C 17 Head-of-line Blocking The cell at the head of an input queue cannot be transferred, thus blocking the following cells Cannot be transferred because is blocked by red cell Input 1

Output 1 Input 2 Output 2 Input 3 Cannot be transferred because output buffer overflow CS640, UW-Madison Output 3 18 A Router with Input Queues Head of Line Blocking Delay The best that any queueing system can achieve.

0% 20% Slide by Nick McKeown 40% 60% 80% CS640, UW-Madison Load 2 2 58% 100% 19 Solution to Avoid Head-of-line Blocking Maintain at each input N virtual queues, i.e., one per output Input 1 Output 1 Output 2 Input 2

Output 3 Input 3 CS640, UW-Madison 20 Combined Input-Output Queueing (CIOQ) Routers Both input and output interfaces store packets Advantages input interface - Easy to built Utilization 1 can be achieved with limited input/output speedup (<= 2) output interface Backplane Disadvantages - Harder to design algorithms

Two congestion points Need to design flow control CS640, UW-Madison RO C 21

Recently Viewed Presentations

  • 5. Scottish Battles of WWI

    5. Scottish Battles of WWI

    The 'Piper of Loos' After the initial 4 day bombardment troops went 'ower the bags' A piper called Laidlaw began playing Scottish tunes on the bagpipes. He continued even though injured by shrapnel. He got one of the five Victoria...
  • Our Guide - Eastside church of Christ

    Our Guide - Eastside church of Christ

    —Psalm 48:14 The steps of a good man are ordered by the Lord, and He delights in his way. —Psalm 37:23 Since you are my rock and my fortress, for the sake of your name lead and guide me. —Psalm...
  • St. Barts Academy Trust Evolving Management and Governance

    St. Barts Academy Trust Evolving Management and Governance

    [Post-NPQH candidate] We were very impressed by so many things that we saw. [Headteacher Clarice Cliff Primary] You have had a significant impact on us all, staff and governors alike. [School Governor] I now have a good network with teachers...
  • Bonding Hybrid Orbitals - Copley

    Bonding Hybrid Orbitals - Copley

    For a double bond the other pair of electrons is found in the space above and below the sigma bond. This bond is called a pi bond ( bond) Sigma and pi bonding. C 2 H. 4. Sigma and pi...
  • Digital Media Literacy: Beyond Access

    Digital Media Literacy: Beyond Access

    Rupert Murdoch, 2006 Overview Confusing technology and media Digital idiocy and Media Studies 2.0 Critical concepts and social media The case of 'fake news' The limits of media literacy Technology or media?
  • These training materials are provided by the New Mexico ...

    These training materials are provided by the New Mexico ...

    A USB-B plug may be seen on some printers. Symbol for a USB port or plug. ... This "digital subscriber line" transmits signals over a specially augmented phone line, using different frequencies than those of the phone conversation. DSL -...
  • Mr. Reich&#x27;s Step by Step Guide to the TOK Essay

    Mr. Reich's Step by Step Guide to the TOK Essay

    Print a Copy of Mr. Reich's Guide to the TOK Essay Rubric (click here for the file) Main TOK Essay Rubric requirements for 9-10 score. Sustained Focus on Knowledge Questions. Connect KQ's to the PT. Investigate Different Perspectives. Link AOK's...
  • Правният език и правните ситуации като стилистично средство в ...

    Правният език и правните ситуации като стилистично средство в ...

    Съчетания via sacra vita humāna terra incognita causa pùblica persōna non grata àger pùblicus dolus malus dolus directus matrimonium iustum ànimus dòmini locus sacer pactum nudum exempli gratia stagnum magnum Forum Romanum (via sacra) Азбука и произношение Азбука и произношение...