Routers Forwarding EECS 122 Lecture 13 Department of Electrical Engineering and Computer Sciences University of California Berkeley Router Architecture Overview Two key router functions run routing algorithms protocol RIP OSPF BGP forwarding datagrams from incoming to outgoing link Interconnection fabric February 23 2006 EECS122 Lecture 12 AKP 2 1 Today Focus on Forwarding Datagrams Input Ports Output Ports Interconnection Fabric Forwarding Process Datagrams Lookups Virtual Circuit next lecture Examples of Routers February 23 2006 EECS122 Lecture 12 AKP 3 Input Port Functions Physical layer bit level reception Data link layer e g Ethernet Decentralized switching February 23 2006 given datagram dest lookup output port using forwarding table in input port memory goal complete input port processing at line speed queuing if datagrams arrive faster than forwarding rate into switch fabric EECS122 Lecture 12 AKP 4 2 Output Ports February 23 2006 5 EECS122 Lecture 12 AKP Queuing Functions Buffer management decide when and which packet to drop Scheduler decide when and which packet to transmit Buffer Scheduler February 23 2006 11 1 22 2 EECS122 Lecture 12 AKP 6 3 Output Queued Router Only output interfaces store packets Advantage Easy to design algorithms only one congestion point input interface output interface Fabric February 23 2006 EECS122 Lecture 12 AKP 7 Output Queued Routers February 23 2006 EECS122 Lecture 12 AKP 8 4 Output Queued Router Only output interfaces store packets Advantage Easy to design algorithms only one congestion point input interface Disadvantage Requires a speedup of a factor of N where N is the number of interfaces not feasible for large N February 23 2006 output interface Fabric 9 EECS122 Lecture 12 AKP Input Queues Only input interfaces store packets Advantages input interface Easy to build Simple algorithms February 23 2006 output interface Fabric EECS122 Lecture 12 AKP 10 5 Input Queues Head of line Blocking The packet at the head of an input queue cannot be transferred thus blocking the following packets Cannot be transferred because of HOL blocking Input 1 Output 1 Input 2 Output 2 Input 3 Output 3 Cannot be transferred because of output contention Wastes router capacity February 23 2006 11 EECS122 Lecture 12 AKP Input Queues Only input interfaces store packets Advantages Easy to build Simple algorithms output interface Fabric Disadvantages input interface HOL Blocking Need a speedup that eliminates HOL but does not create output queues About 2 suffices February 23 2006 EECS122 Lecture 12 AKP 12 6 Advanced Queuing Functions Packet classification map each packet to a predefined class use to implement more sophisticated services e g QoS Flow a subset of packets between any two endpoints in the network class 1 1 Classifier 2 class 2 Scheduler class n Buffer management February 23 2006 EECS122 Lecture 12 AKP 13 Three types of switching fabrics February 23 2006 EECS122 Lecture 12 AKP 14 7 Shared Bus Fabrics CPU Typically 5Gb s aggregate capacity Limited by shared bus 1 Gbps bus Cisco 1900 sufficient speed for access and enterprise routers not regional or backbone Buffer Memory Route Table 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 February 23 2006 15 EECS122 Lecture 12 AKP Shared Memory Based Fabrics Shared Backplane CP I Line U n te r fa 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 February 23 2006 EECS122 Lecture 12 AKP 16 8 Switched Fabrics Switched Backplane Li CPInt 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 February 23 2006 EECS122 Lecture 12 AKP Slide by Nick McKeown 17 Switched Fabrics Overcome bus bandwidth limitations Banyan networks other interconnection nets initially developed to connect processors in multiprocessor Advanced design fragmenting datagram into fixed length cells switch cells through the fabric Cisco 12000 switches Gbps through the interconnection network February 23 2006 EECS122 Lecture 12 AKP 18 9 Example Crossbar Switches Basic Idea N2 switching points not scalable Engineering Idea It is very unlikely that more than L packets will want to go to the same output port simultaneously How many switching points can we save for fixed L February 23 2006 EECS122 Lecture 12 AKP 19 The Knockout Concentrator Goal If there are greater than L packets that want to go to the same destination pick L in a fair manner Organize the switching elements as if they are implementing a multi round tournament A game consists of two players and the winner is selected at random at a switching element The winner moves on to the next round while the loser plays a consolation rank The top L players are selected February 23 2006 EECS122 Lecture 12 AKP 20 10 Knockout Switch Concentrator Inputs D delay elements to insure all packets exit at same time D D D D What is the complexity D How many 2X2 elements for fixed L D D D D D D 1 D D D 2 3 4 Outputs February 23 2006 EECS122 Lecture 12 AKP 21 Why have multiple rounds Example N 8 L 4 After one round there are four winners and four losers Why not just pick the winners and drop the losers February 23 2006 EECS122 Lecture 12 AKP 22 11 Example D delay elements to insure all packets exit at same time Inputs Stopping after the first round D D D would mean that two packets are dropped evenD though all four Should be delivered D D D D D D D D 1 February 23 2006 2 D D 3 4 Outputs EECS122 Lecture 12 AKP 23 The Forwarding Decision Process Datagram Routing Each packet is independently forwarded at each router Must look up IP address ranges Virtual Circuit Routing call setup teardown for each call before data can flow each packet carries VC identifier not destination host address every router on source dest path maintains state for each passing connection link router resources bandwidth buffers may be allocated to VC dedicated resources predictable service February 23 2006 EECS122 Lecture 12 AKP 24 12 Datagram Route Lookup Longest Prefix Match Not easy to do at line speeds It is useful to think of the search process as a traversal of a special kind of labeled tree called a Trie February 23 2006 25 EECS122 Lecture 12 AKP Trees and Tries Binary Search Tree
View Full Document
Unlocking...