15-744: Computer NetworkingForwarding and RoutersOutlineTechniques for Forwarding PacketsSource RoutingSlide 6Virtual Circuits/Tag SwitchingVirtual Circuits ExamplesVirtual CircuitsIP Datagrams on Virtual CircuitsSlide 11Global Addresses (IP)Global Address ExampleGlobal AddressesSummarySlide 17Original IP Route LookupOriginal IP Route Lookup – ExampleCIDR RevisitedCIDR ExampleIP Addresses: How to Get One?CIDR IllustrationCIDR ShortcomingsSlide 25Trie Using Sample DatabaseSpeeding up Prefix Match (P+98)Prefix TreeSlide 31Slide 32Slide 33Speeding up Prefix Match - AlternativesBinary Search on RangesSlide 36Slide 37Packet ClassificationComplexityBit VectorsSlide 41Observations [GM99]Aggregating Rules [BV01]Summary: Addressing/ClassificationSlide 46What Does a Router Look Like?Line CardsNetwork ProcessorSwitch Design IssuesSwitch BufferingLine Card InterconnectISLIPISLIP (cont.)What Limits Router Capacity?Multi-rack Routers Reduce Power DensityLimits to ScalingSlide 59QuestionIf Traffic is Uniform…Real Traffic is Not UniformTwo-stage Load-Balancing SwitchSlide 64Slide 65Static WDM SwitchingLinecard DataflowSummary - IP Router DesignSlide 69Factors Affecting RoutingTwo Main ApproachesDistance Vector ProtocolsExample - Initial DistancesE Receives D’s Routes; Updates CostCount to InfinityC Sends Routes to BB Updates Distance to AB Sends Routes to CSlide 79How are These Loops Caused?Some “Solutions”Example Where Split Horizon FailsAvoiding the Bouncing EffectDistance Vector in PracticeLink State – Basic StepsLink State Packets (LSPs)Reliable FloodingSPT ExampleExampleLink State CharacteristicsSummary: LS vs. DVSlide 93Slide 94Slide 95Open QuestionsNext Lecture: Inter-Domain Routing15-744: Computer NetworkingL-2 Addressing/ForwardingL-2; 9-24-04© Srinivasan Seshan, 2004 2Forwarding and Routers•Forwarding•IP lookup•High-speed router architecture•Intro to routing protocols•Readings•[D+97] Small Forwarding Tables for Fast Routing Lookups•[BV01] Scalable Packet Classification•[McK97] A Fast Switched Backplane for a Gigabit Switched Router•[KCY03] Scaling Internet Routers Using Optics•Know RIP/OSPFL-2; 9-24-04© Srinivasan Seshan, 2004 3Outline•Alternative methods for packet forwarding•IP route lookup•Variable prefix match algorithms•Packet classification•IP router design•Routing protocols•Distance vector•Link stateL-2; 9-24-04© Srinivasan Seshan, 2004 4Techniques for Forwarding Packets•Source routing•Packet carries path•Table of virtual circuits•Connection routed through network to setup state•Packets forwarded using connection state •Table of global addresses (IP)•Routers keep next hop for destination•Packets carry destination addressL-2; 9-24-04© Srinivasan Seshan, 2004 5Source Routing•List entire path in packet•Driving directions (north 3 hops, east, etc..)•Router processing•Examine first step in directions•Strip first step from packet•Forward to step just stripped offReceiverPacketR2, R3, RSender234123412341R2R3R1R3, RRL-2; 9-24-04© Srinivasan Seshan, 2004 6Source Routing•Advantages•Switches can be very simple and fast•Disadvantages•Variable (unbounded) header size•Sources must know or discover topology (e.g., failures)•Typical use•Ad-hoc networks (DSR)•Machine room networks (Myrinet)L-2; 9-24-04© Srinivasan Seshan, 2004 7Virtual Circuits/Tag Switching•Connection setup phase•Use other means to route setup request •Each router allocates flow ID on local link•Creates mapping of inbound flow ID/port to outbound flow ID/port•Each packet carries connection ID•Sent from source with 1st hop connection ID•Router processing•Lookup flow ID – simple table lookup•Replace flow ID with outgoing flow ID•Forward to output portL-2; 9-24-04© Srinivasan Seshan, 2004 8Virtual Circuits ExamplesReceiverPacket1,5 3,7Sender23411,7 4,2234123412,2 3,6R2R3R15 726L-2; 9-24-04© Srinivasan Seshan, 2004 9Virtual Circuits•Advantages•More efficient lookup (simple table lookup)•More flexible (different path for each flow)•Can reserve bandwidth at connection setup•Easier for hardware implementations•Disadvantages•Still need to route connection setup request•More complex failure recovery – must recreate connection state•Typical uses•ATM – combined with fix sized cells•MPLS – tag switching for IP networksL-2; 9-24-04© Srinivasan Seshan, 2004 10IP Datagrams on Virtual Circuits•Challenge – when to setup connections•At bootup time – permanent virtual circuits (PVC)•Large number of circuits•For every packet transmission•Connection setup is expensive•For every connection•What is a connection?•How to route connectionless traffic?L-2; 9-24-04© Srinivasan Seshan, 2004 11IP Datagrams on Virtual Circuits•Traffic pattern•Few long lived flows•Flow – set of data packets from source to destination•Large percentage of packet traffic•Improving forwarding performance by using virtual circuits for these flows•Other traffic uses normal IP forwardingL-2; 9-24-04© Srinivasan Seshan, 2004 12Global Addresses (IP)•Each packet has destination address•Each switch has forwarding table of destination next hop•At v and x: destination east•At w and y: destination south•At z: destination north•Distributed routing algorithm for calculating forwarding tablesL-2; 9-24-04© Srinivasan Seshan, 2004 13Global Address ExampleReceiverPacketRSender234123412341R2R3R1RRR 3R 4R 3RL-2; 9-24-04© Srinivasan Seshan, 2004 15Global Addresses•Advantages•Stateless – simple error recovery•Disadvantages•Every switch knows about every destination•Potentially large tables•All packets to destination take same routeL-2; 9-24-04© Srinivasan Seshan, 2004 16SummarySource Routing Global AddressesHeader Size Worst OK – Large addressRouter Table Size NoneNumber of hosts (prefixes)Forward Overhead Best Prefix matchingVirtual CircuitsBestNumber of circuitsPretty GoodSetup Overhead None NoneError Recovery Tell all hosts Tell all routersConnection SetupTell all routers and Tear down circuit and re-routeL-2; 9-24-04© Srinivasan Seshan, 2004 17Outline•Alternative methods for packet forwarding•IP route lookup•Variable prefix match algorithms•Packet classification•IP router design•Routing protocols•Distance vector•Link stateL-2; 9-24-04© Srinivasan Seshan, 2004 18Original IP Route Lookup•Address classes•A: 0 | 7 bit
View Full Document
Unlocking...