115-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 address2L-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 1sthop 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 7263L-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 tables4L-2; 9-24-04© Srinivasan Seshan, 2004 13Global Address ExampleReceiverPacketRSender234123412341R2R3R1RRR Æ 3R Æ 4R Æ 3RL-2; 9-24-04© Srinivasan Seshan, 2004 14Router 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 allocationL-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-route5L-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 network | 24 bit host (16M each)• B: 10 | 14 bit network | 16 bit host (64K)• C: 110 | 21 bit network | 8 bit host (255)• Address would specify prefix for forwarding table• Simple lookupL-2; 9-24-04© Srinivasan Seshan, 2004 19Original IP Route Lookup – Example• www.cmu.edu address 128.2.11.43• Class B address – class + network is 128.2• Lookup 128.2 in forwarding table• Prefix – part of address that really matters for routing• Forwarding table contains• List of class+network entries• A few fixed prefix lengths (8/16/24)• Large tables• 2 Million class C networks• 32 bits does not give enough space encode network location information inside address – i.e., create a structured hierarchyL-2; 9-24-04© Srinivasan Seshan, 2004 20CIDR Revisited• Supernets• Assign adjacent net addresses to same org• Classless routing (CIDR)• How does this help routing table?• Combine routing table entries whenever all nodes with same prefix share same hop6L-2; 9-24-04© Srinivasan Seshan, 2004 21CIDR Example• Network is allocated 8 class C chunks, 201.10.0.0 to 201.10.7.255• Allocation uses 3 bits of class C space• Remaining 21 bits are network number, written as 201.10.0.0/21• Replaces 8 class C routing entries with 1
View Full Document