EE 122 Router Design Kevin Lai September 25 2002 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 laik cs berkeley edu 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 laik cs berkeley edu 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 PC s 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 laik cs berkeley edu 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 laik cs berkeley edu 5 Why we Need Faster Routers 1 To prevent routers from being the bottleneck Packet processing Power Link Speed 10000 2x 18 months 1000 2x 7 months 100 100 10 10 1 1 1985 1990 1995 2000 1985 1990 1995 2000 0 1 0 1 TDM Source SPEC95Int David Miller Stanford Slide by Nick McKeown laik cs berkeley edu DWDM 6 Fiber Capacity Gbit s Spec95Int CPU results 1000 10000 Why we Need Faster Routers 2 To reduce cost power complexity of POPs POP with large routers POP with smaller routers Ports Price 100k Power 400W It is common for 50 60 of ports to be for interconnection laik cs berkeley edu Slide by Nick McKeown 7 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 laik cs berkeley edu 8 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 laik cs berkeley edu 9 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 laik cs berkeley edu 10 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 laik cs berkeley edu 11 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 laik cs berkeley edu 12 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 laik cs berkeley edu RI B RO C 13 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 laik cs berkeley edu 14 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 laik cs berkeley edu 15 Typical Functions Performed by Output Interface cont d 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 Classifier 2 flow 2 Scheduler flow n Buffer management Flow a subset of packets between any two endpoints in the network laik cs berkeley edu 16 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 laik cs berkeley edu 17 Output Queued OQ Routers input interface Only output interfaces store packets Advantages 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 laik cs berkeley edu RO C 18 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 laik cs berkeley edu RO C 19 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 laik cs berkeley edu Output 3 20 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 laik cs berkeley edu Load 2 2 58 100 21 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 laik cs berkeley edu 22 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
View Full Document
Unlocking...