1Stan KurkovskyComputer NetworksComputer NetworksPrinciples of Principles of Routing and SwitchingRouting and SwitchingBased on Computer Networking, 4thEdition by Kurose and RossStan KurkovskyRouter Architecture OverviewRouter Architecture OverviewTwo key router functions:Two key router functions:•• run routing algorithms/protocol (RIP, OSPF, BGP)run routing algorithms/protocol (RIP, OSPF, BGP)••forwarding forwarding datagrams from incoming to outgoing linkdatagrams from incoming to outgoing link2Stan KurkovskyInput Port FunctionsInput Port FunctionsDecentralized switchingDecentralized switching::•• given datagram dest., lookup output port using given datagram dest., lookup output port using forwarding table in input port memoryforwarding table in input port memory•• goal: complete input port processing at ‘line goal: complete input port processing at ‘line speed’speed’•• queuing: if datagrams arrive faster than queuing: if datagrams arrive faster than forwarding rate into switch fabricforwarding rate into switch fabricPhysical layer:bit-level receptionData link layer:e.g., EthernetStan KurkovskyThree types of switching fabricsThree types of switching fabrics3Stan KurkovskySwitching Via MemorySwitching Via MemoryFirst generation routers:First generation routers:•• traditional computers with switching under direct control of CPUtraditional computers with switching under direct control of CPU•• packet copied to system’s memorypacket copied to system’s memory•• speed limited by memory bandwidth (2 bus crossings per datagram)speed limited by memory bandwidth (2 bus crossings per datagram)InputPortOutputPortMemorySystem BusStan KurkovskySwitching Via a BusSwitching Via a Bus•• datagram from input port memory to output port memory via a shared datagram from input port memory to output port memory via a shared busbus••bus contention:bus contention: switching speed limited by bus bandwidthswitching speed limited by bus bandwidth•• 1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers 1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone)(not regional or backbone)4Stan KurkovskySwitching via an Interconnection NetworkSwitching via an Interconnection Network•• overcome bus bandwidth limitationsovercome bus bandwidth limitations•• Banyan networks, other interconnection nets initially developed to Banyan networks, other interconnection nets initially developed to connect processors in multiprocessorconnect processors in multiprocessor•• Advanced design: fragmenting datagram into fixed length cells, switch Advanced design: fragmenting datagram into fixed length cells, switch cells through the fabric. cells through the fabric. •• Cisco 12000: switches Cisco 12000: switches 60 60 GbpsGbps through the interconnection networkthrough the interconnection networkStan KurkovskyOutput PortsOutput Ports••BufferingBufferingrequired when datagrams arrive from fabric faster than the required when datagrams arrive from fabric faster than the transmission ratetransmission rate••Scheduling disciplineScheduling disciplinechooses among queued datagrams for transmissionchooses among queued datagrams for transmission5Stan KurkovskyOutput port queueingOutput port queueing•• buffering when arrival rate via switch exceeds output line speedbuffering when arrival rate via switch exceeds output line speed••queueing (delay) and loss due to output port buffer overflow!queueing (delay) and loss due to output port buffer overflow!Stan KurkovskyInput Port QueuingInput Port Queuing•• Fabric slower than input ports combined Fabric slower than input ports combined --> queueing may occur at input > queueing may occur at input queues queues ••HeadHead--ofof--thethe--Line (HOL) blocking:Line (HOL) blocking: queued datagram at front of queue queued datagram at front of queue prevents others in queue from moving forwardprevents others in queue from moving forward••queueing delay and loss due to input buffer overflow!queueing delay and loss due to input buffer