Lec13router1Lec13router1Workstation-BasedAggregate bandwidth 1/2 of the I/O bus bandwidth capacity shared among all hosts connected to switchexample: 1Gbps bus can support 5 x 100Mbps ports (in theory)Packets-per-second must be able to switch small packets300,000 packets-per-second is achievablee.g., 64-byte packets implies 155MbpsSpring 20002CS 461Switching Hardware Design Goalsthroughput (depends on traffic model)scalability (a function of n)Portscircuit management (e.g., map VCIs, route datagrams)buffering (input and/or output)Fabricas simple as possiblesometimes do buffering (internal) SwitchfabricControlprocessorOutputportInputportSpring 20003CS 461BufferingWherever contention is possibleinput port (contend for fabric)internal (contend for output port)output port (contend for link)Head-of-Line Blockinginput buffering Spring 20004CS 461Crossbar SwitchesSpring 20005CS 461Knockout SwitchExample crossbarConcentratorselect l of n packetsComplexity: n2 1234OutputsInputsSpring 20006CS 461Knockout Switch (cont)Output Buffer(c)ShifterBuffers(b)ShifterBuffers(a)ShifterBuffersSpring 20007CS 461Self-Routing FabricsBanyan Networkconstructed from simple 2 x 2 switching elementsself-routing header attached to each packetelements arranged to route based on this headerno collisions if input packets sorted into ascending ordercomplexity: n log2 n Spring 20008CS 461Self-Routing Fabrics (cont)Batcher Networkswitching elements sort two numberssome elements sort into ascending (clear)some elements sort into descending (shaded)elements arranged to implement merge sortcomplexity: n log22 n Common Design: Batcher-Banyan SwitchSpring 20009CS 461High-Speed IP RouterSwitch (possibly ATM)Line Cardslink interface (input, output)router lookup (input)common IP path (input)packet queue (output)Control Processorrouting protocol(s)exceptional casesLine card(forwarding buffering)Line card(forwarding buffering)Line card(forwarding buffering)Line card(forwarding buffering)RoutingCPUBuffermemoryRouting softwarew/ router OSSpring 200010CS 461IP Forwarding is SlowProblem: classless IP addresses (CIDR)Route by variable-length Forwarding Equivalence Classes (FEC)FEC = IP address plus prefix of 1-32 bits; e.g., 172.200.0.0/16IP Routerforwarding tbl: match IP address to FEC w/ longest prefixSpring 200011CS 461Primary goal: fast, cheap forwarding 1Gb/s IP router: $187,0005Gb/s ATM switch: $41,000Create Virtual Circuit at Flow Setup Cell Forwardingindex, swap, switch ATM ForwardingSpring 200012CS 461Cisco: Tag SwitchingAdd a VCI-like tag to packets TSR uses ATM switch hardware IP routing protocols (OSPF, RIP, BGP)build forwarding table from routing tableGoal: IP router functionality at ATM switch speeds/costsSpring 200013CS 461ForwardingShim before IP headerTag Forwarding Information Base (TFIB) Just like ATMindex, swap, switchTTL (8 bits)CoS STag (20 bits)Spring 200014CS 461Tag BindingNew FEC from IP routing protocolsSelect local tag (index in TFIB) Need for next hopOther routers need my Solution: distribute tags like other routing infoSpring 200015CS 461Tag Distribution ProtocolSend TDP messages to peersUpon receiving TDP message, check if sender is next hop for FECyes, save tag in TFIBno, can discard or save for future useControl-driven label assignmentSpring 200016CS 461The First TagTwo kinds of routers: edge vs. interiorEdge: add shim based on IP lookup, strip at exitInterior: forward by tag onlyEIIESpring 200017CS 461Robustness IssuesWhat if tag fault?try to forward (default route)discard packetForwarding Loopstopology changes cause temporary loopsTTL field in tag, same as IPSpring 200018CS 461Ipsilon: IP SwitchingRun on ATM switch over ATM networkATM hardware + IP switching softwareIdea: Exploit temporal locality of traffic to cache routing decisionsAssociate labels (VCI) with flowsforward packets as usualmain difference is in how labels are created, distributed to other routersSpring 200019CS 461IP SwitchAssume default ATM virtual circuits between routersRouter runs IP routing protocol, can forward IP packets on default VCsIdentify flows, assign flow-specific VCflow = port pair or host pairData-driven label assignmentSpring 200020CS 461Flow Setup on IP Switch Get IFMP, ATM SwitchControllerPort iPort jvci = xvci = yPort cvci = xIFMP messageIFMP messageSpring 200021CS 461ComparisonSwitch by flowData drivenSoft-state timeoutBetween end-hostsEvery router can do IP lookupScalable?Switch by FECControl drivenRoute changesBetween edge TSRsInterior TSRs only do tag switchingIP SwitchingTag SwitchingSpring 200022CS 461