To Learn More About BGPRouting vs. ForwardingTwo Classes of Routing ProtocolsIP Addressing and ForwardingIP Address ClassesIP Address ClassesImproving the HierarchyClassless Interdomain RoutingAggregation with CIDRRouting Table Entry ExamplesSplitting with CIDRSize of Complete Routing TableIPv6 AddressingName, Address, RouteName, Address, RouteInternet StructureRouting between ISPsAutonomous Systems (AS)ImplicationsIntradomain And InterdomainAS Numbers (ASNs)Nontransit vs. Transit ASesSelective TransitCustomers and ProvidersCustomers Don’t Always Need BGPCustomer-Provider HierarchyThe Peering RelationshipPeering Provides ShortcutsPeering WarsBorder Gateway ProtocolPurpose of BGPMultiple Routing Processes on a Single RouterExample of Advertising RouteJoin EGP with IGP For ConnectivityI-BGP and E-BGPiBGP Peers Must be Fully MeshedPath Vector ProtocolBGP Operations (Simplified)115-441 Computer NetworksInter-Domain RoutingProfessor Hui [email protected] ZhangTo Learn More About BGP http://www.cambridge.intel-research.net/~tgriffin/talk_tutoriasl/3Hui ZhangRouting vs. ForwardingRRRABCDR1R2R3R4R5ENet Nxt HopR4R3R3R4DirectR4Net Nxt HopABCDEdefaultR2R2DirectR5R5R2Net Nxt HopABCDEdefaultR1DirectR3R1R3R1Default toupstreamrouterABCDEdefaultForwarding always worksRouting can be badly brokenForwarding: determine next hopRouting: establish end-to-end paths4Hui ZhangTwo Classes of Routing Protocols Distance vector (RIP) Distribute path computation Keep only local link data Bellman-Ford algotrithm Link state (OSPF, IS-IS) Local path computation Distribute all link data Dijkstra’s algorithm5Hui ZhangLink State vs. Distance VectorLink State Vectoring Topology information is floodedwithin the routing domain Best end-to-end paths are computed locally at each router. Best end-to-end paths determine next-hops. Based on minimizing some notion of distance Works only if policy is sharedand uniform Examples: OSPF, IS-IS Each router knows little about network topology Only best next-hops are chosen by each router for each destination network. Best end-to-end paths result from composition of all next-hop choices Does not require any notion of distance Does not require uniform policies at all routers Examples: RIP, BGP6Hui ZhangIP Addressing and Forwarding Routing Table Requirement For every possible destination IP address, give next hop Nearly 232(4.3 x 109) possibilities! Hierarchical Addressing Scheme Address split into network ID and host ID E.g., CMU has one network ID shared by all hosts within CMU All packets to given network follow same route, until they reach destination network Fields–pfx Prefix to specify split between network & host IDs– network 2xpossibilities– host 2ypossibilitiespfx network hostxy7Hui ZhangIP Address Classes Class A mit.edu: 18.7.22.69 Class B cmu.edu: 128.2.11.43 Class C Classes D, E, F Not commonly used0 network host72410 network host1416110 network host218First digit: 1–126First digit: 128–191First digit: 192–2238Hui ZhangIP Address ClassesClass Count HostsA 27-2 = 126 224-2 = 16,777,214B 214= 16,398 216-2 = 65,534C 221= 2,097,512 28-2 = 254Total 2,114,036 Partitioning too Coarse Not enough big (class A) addresses No organization needs 16.7 million hosts– Large organization likely to be geographically distributed Many organizations must make do with multiple class C’s Too many different Network IDs Routing tables must still have 2.1 million entries9Hui ZhangImproving the Hierarchy Basic Idea of Hierarchy is Good Organizations of different sizes can be assigned different numbers of IP addresses Shortcomings of Class-Based Addressing Class A too coarse; Class C too fine; not enough Class B’s When fully deployed would have too many entries in routing table (2.1 million) Solution Hierarchy with finer gradation of network/host ID split10Hui ZhangClassless Interdomain Routing CIDR, pronounced “cider” Arbitrary Split Between Network & Host IDs Specify either by mask or prefix length E.g., CMU can be specified as– 128.2.0.0 with netmask 255.255.0.0– 128.2.0.0/16network host1111111111111111000000000000000011Hui ZhangAggregation with CIDR– Original Use: Aggregate Class C Addresses One organization assigned contiguous range of class C’s– e.g., Microsoft given all addresses 207.46.192.X --207.46.255.X– Specify as CIDR address 207.46.192.0/18207 46 192 0cf 2e c0 000 8 16 24 311100 1111 0010 1110 11xx xxxx xxxx xxxxDecimalHexadecimalBinaryUpper 18 bits frozen Lower 14 bits arbitrary12Hui ZhangRouting Table Entry Examples Snapshot From MAE-West Routing Table Probably out of date Note hole in table: Nothing covers bytes 96 – 127Address Prefix Length Third Byte Byte Range207.46.0.0 19 000xxxxx20 – 31207.46.32.0 19 001xxxxx232 – 63207.46.64.0 19 010xxxxx264 – 95207.46.128.0 18 10xxxxxx2128 – 191207.46.192.0 18 11xxxxxx2192 – 255microsoft.com: 207.46.245.214 & 207.46.245.22213Hui ZhangSplitting with CIDR Expose subnetting structure to external routers Example Class A address 12.X.X.X has 413 entries in MAE-WEST table Prefix lengths 8--24 attbi.com– Backbone services of AT&T Geographically distributed– Don’t want all packets to concentrate to single region14Hui ZhangSize of Complete Routing Table Source: www.cidr-report.org Shows that CIDR has kept # table entries in check– Currently require 124,894 entries for a complete table– Only required by backbone routers15Hui ZhangIPv6 Addressing Main motivation for switch from IPv4 Getting hard to manage 32-bit address allocation 128-Bit Addresses Standard unicast addresses 125 bits long (3-bit prefix) 4.2 x 1037nodes Earth radius is 6371 km Metric: 4.2 x 1037/ [4 π (6.371 x 108)2] = 8 X 1018nodes / cm216Hui ZhangName, Address, Route First order approximation Name tells who you are– www.cnn.com Address tells where you are– 64.236.16.20 Route tells how to get there– <prefix, nextHop>17Hui ZhangName, Address, Route How many names each address can have? How many addresses each name can have? How many addresses each “node” can have? How many names each “node” can have? How many routes to each prefix?18Hui ZhangInternet StructureLarge ISPLarge ISPDial-UpISPAccessNetworkSmall ISPStub StubStubThe Internet contains a large
View Full Document
Unlocking...