15-441 Computer NetworkingOutlineTechniques for Forwarding PacketsSource RoutingSource Routing ExampleSlide 6Global Addresses (IP)Global Address ExampleRouter Table SizeGlobal AddressesHow do we set up Routing Tables?Virtual Circuits/Tag SwitchingVirtual Circuits ExamplesVirtual CircuitsIP Datagrams on Virtual CircuitsSlide 16ComparisonForwarding vs. RoutingSlide 19How is IP Design Standardized?Addressing in IPAddressing ConsiderationsSlide 23IP AddressesIP Address Classes (Some are Obsolete)Some Special IP AddressesInteraction with Link LayerOriginal IP Route LookupOriginal IP Route Lookup – ExampleSubnet Addressing RFC917 (1984)SubnettingSubnetting ExampleForwarding ExampleSlide 34IP Address Problem (1991)IP Address Utilization (‘98)IP Addressing ProblemsClassless Inter-Domain RoutingCIDRIP Addresses: How to Get One?IP addresses: How to Get One?Slide 42Hierarchical Addressing: Route AggregationHierarchical Addressing: More Specific RoutesCIDR ExampleCIDR IllustrationCIDR Addressing ShortcomingsSlide 48Routing to the NetworkRouting Within the SubnetSlide 51Slide 5215-441 Computer NetworkingLecture 7 – IP Addressing and ForwardingLecture 7: 9-18-01 2Outline•Methods for packet forwarding•Traditional IP addressing•CIDR IP addressing•Forwarding exampleLecture 7: 9-18-01 3Techniques 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 addressLecture 7: 9-18-01 4Source 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 offLecture 7: 9-18-01 5Source Routing ExampleReceiverPacket3,4,3Sender234123412341R2R3R14,33Lecture 7: 9-18-01 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)Lecture 7: 9-18-01 7Global 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 tablesLecture 7: 9-18-01 8Global Address ExampleReceiverPacketRSender234123412341R2R3R1RRR 3R 4R 3RLecture 7: 9-18-01 9Router Table Size•One entry for every host on the Internet•100M entries,doubling every year•One entry for every LAN•Every host on LAN shares prefix•Still too many, doubling every year•One entry for every organization•Every host in organization shares prefix•Requires careful address allocationLecture 7: 9-18-01 10Global Addresses•Advantages•Stateless – simple error recovery•Disadvantages•Every switch knows about every destination•Potentially large tables•All packets to destination take same routeLecture 7: 9-18-01 11How do we set up Routing Tables?•Graph theory to compute “shortest path”•Switches = nodes•Links = edges•Delay, hops = cost•Need to adapt to changes in topologyLecture 7: 9-18-01 12Virtual 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 portLecture 7: 9-18-01 13Virtual Circuits ExamplesReceiverPacket1,5 3,7Sender23411,7 4,2234123412,2 3,6R2R3R15 726Lecture 7: 9-18-01 14Virtual 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 networksLecture 7: 9-18-01 15IP 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?Lecture 7: 9-18-01 16IP 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 forwardingLecture 7: 9-18-01 17ComparisonSource 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-routeLecture 7: 9-18-01 18Forwarding vs. Routing•Forwarding: the process of moving packets from input to output•The forwarding table•Information in the packet•Routing: process by which the forwarding table is built and maintained•One or more routing protocols•Procedures (algorithms) to convert routing info to forwarding table.Lecture 7: 9-18-01 19Outline•Methods for packet forwarding•Traditional IP addressing•CIDR IP addressing•Forwarding exampleLecture 7: 9-18-01 20How is IP Design Standardized?•IETF•Voluntary organization•Meeting every 4 months•Working groups and email discussions•“We reject kings, presidents, and voting; we believe in rough consensus and running code” (Dave Clark 1992)•Need 2 independent, interoperable implementations for standard•IRTF•End2End •Reliable Multicast, etc..Lecture 7: 9-18-01 21Addressing in IP•IP addresses are names of interfaces•Domain Name System (DNS) names are names of hosts•DNS binds host names to interfaces•Routing binds interface names to pathsLecture 7: 9-18-01 22Addressing Considerations•Fixed length or variable
View Full Document
Unlocking...