EECS 122 Introduction to Computer Networks Switch and Router Architectures Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Today s Lecture Application Transport Today Network IP Link Physical Katz Stoica F04 2 IP Routers Router consists of Set of input interfaces where packets arrive Set of output interfaces from which packets depart Some form of interconnect connecting inputs to outputs Router Router implements 1 Forward packet to corresponding output interface 2 Manage bandwidth and buffer space resources 5 4 7 8 6 11 10 2 13 1 3 12 Katz Stoica F04 3 Generic Architecture Input and output interfaces are connected through an interconnect Interconnect can be implemented by Shared memory Low capacity routers e g PC based routers Shared bus Medium capacity routers Point to point switched bus High capacity routers input interface output interface Interconnect Katz Stoica F04 4 Shared Memory 1st Generation 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 5Gbps aggregate capacity Limited by rate of shared memory Slide by Nick McKeown Katz Stoica F04 5 Shared Bus 2nd Generation CPU Typically 5Gb s aggregate capacity Limited by shared bus 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 Slide by Nick McKeown Katz Stoica F04 6 Point to Point Switch 3rd Generation 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 50Gbps aggregate capacity Slide by Nick McKeown Katz Stoica F04 7 What a Router Looks Like Cisco GSR 12416 Juniper M160 19 19 Capacity 160Gb s Power 4 2kW Capacity 80Gb s Power 2 6kW 3ft 6ft 2ft 2 5ft Slide by Nick McKeown Katz Stoica F04 8 Interconnect Point to point switch allows simultaneous transfer of packet between any two disjoint pairs of inputoutput interfaces Goal come up with a schedule that Provides Quality of Service Maximizes 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 Katz Stoica F04 9 Output Queued Routers Only output interfaces store packets Advantages Easy to design algorithms only one congestion point input interface output interface Backplane Disadvantages Requires an output speedup of N where N is the number of interfaces not feasible RO C Katz Stoica F04 10 Input Queued Routers Only input interfaces store packets Advantages Easy to build Store packets at inputs if contention at outputs Relatively easy to design algorithms Only one congestion point but not output Need to implement backpressure input interface 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 RO C Katz Stoica F04 11 Head of line Blocking Cell at 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 Output 3 Katz Stoica F04 12 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 Load 60 80 2 2 58 Katz Stoica F04 100 13 Solution to Avoid Head of line Blocking Maintain at each input N virtual queues i e one per output port Input 1 Input 2 Output 1 Output 2 Output 3 Input 3 Katz Stoica F04 14 Combined Input Output Queued CIOQ Routers Both input and output interfaces store packets Advantages Easy to built Utilization 1 can be achieved with limited input output speedup 2 input interface output interface Backplane Disadvantages Harder to design algorithms Two congestion points Need to design flow control RO C Katz Stoica F04 15 Input Interface 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 input interface output interface Interconnect Katz Stoica F04 16 Lookup Identify the output interface to forward an incoming packet based on packet s destination address Routing tables summarize information by maintaining a mapping between IP address prefixes and output interfaces How are routing tables computed Route lookup find the longest prefix in the table that matches the packet destination address Katz Stoica F04 17 IP Routing Packet with destination address 12 82 100 101 is sent to interface 2 as 12 82 100 xxx is the longest prefix matching packet s destination address 128 16 120 xxx 1 12 82 xxx xxx 3 12 82 100 xxx 2 12 82 100 101 1 128 16 120 111 2 Katz Stoica F04 18 Patricia Tries Use binary tree paths to encode prefixes 1 0 001xx 2 0100x 3 10xxx 1 01100 5 1 0 0 0 1 2 1 0 3 1 0 0 5 Advantage simple to implement Disadvantage one lookup may take O m where m is number of bits 32 in the case of IPv4 Katz Stoica F04 19 Another Forwarding Technique Source Routing Each packet specifies the sequence of routers or alternatively the sequence of output ports from source to destination source 4 3 4 1 2 3 4 1 2 3 4 1 2 3 4 4 3 4 1 2 3 4 1 2 3 4 1 2 3 4 4 3 4 Katz Stoica F04 20 Source Routing cont d Gives the source control of the path Not scalable Packet overhead proportional to the number of routers Typically require variable header length which is harder to implement Hard for source to have complete information Loose source routing sender specifies only a subset of routers along the path Katz Stoica F04 21 Output Functions Buffer management decide when and which packet to drop Scheduler decide when and which packet to transmit Buffer Scheduler 1 2 Katz Stoica F04 22 Example FIFO router Most of today s routers Drop tail buffer management when buffer is full drop the incoming packet First In First Out FIFO Scheduling schedule packets in the same order they arrive Katz Stoica F04 23 Output Functions cont d Packet classification map each packet to a predefined flow connection for datagram forwarding Use
View Full Document
Unlocking...