ECE544: Communication Networks-II, Spring 2007Today’s LectureRouting MetricsMetric choicesOriginal ARPANET metricNew metricPerformance of new metricSpecific problemsConsequencesRevised link metricRouting metric v.s. link utilizationObservationsRouting dynamicsSlide 14Scalable IP RoutingHow to Make Routing ScaleInternet StructureSlide 18SubnettingSubnet ExampleSupernetting (CIDR)Slide 22Slide 23IP Version 6IPv6 Technology ScopeIPv4 & IPv6 Header ComparisonIPv6 AddressingIPv6 Address RepresentationIPv6 AddressingAggregatable Global Unicast AddressesAddress AllocationHierarchical Addressing & AggregationLink-Local & Site-Local Unicast AddressesMulticast Addresses (RFC 2375)more on IPv6 AddressingIPv6 Addressing ExamplesBGP OverviewBGP-4: Border Gateway ProtocolExamplePath SuboptimalityChoicesSolution: Path VectorsProblemsRouting table sizeSlide 45Slide 46Slide 47Slide 48Slide 49BGP ExampleInterior BGP peersSlide 52Interconnecting BGP peersHop-by-hop modelPolicy with BGPExamples of BGP policiesSlide 57BGP-4Routing information bases (RIB)BGP common headerBGP OPEN messageBGP UPDATE messageNLRIBGP NOTIFICATION messageBGP KEEPALIVE messagePolicy routingOptionsSourcesToday’s HomeworkECE544: Communication Networks-II, Spring 2007D. RaychaudhuriLecture 5Includes teaching materials from L. PetersonToday’s Lecture•Routing metrics•Scalable IP routing•IPv6•Inter-domain routing (BGP)Routing MetricsMetric choices•Static metrics (e.g., hop count)–good only if links are homogeneous–not the case in the Internet•Static metrics do not take into account:–link delay–link capacity–link load (hard to measure)Original ARPANET metric•Cost proportional to queue size–instantaneous queue length as delay estimator•Problems:–did not take into account link speed–poor indicator of expected delay due to rapid fluctuations–delay may be longer even if queue size is small due to contention for other resourcesNew metric•Delay = (depart time - arrival time) + transmission time + link propagation delay–(depart time - arrival time) captures queuing–transmission time captures link capacity–link propagation delay captures the physical length of the link•Measurements averaged over 10 seconds–Update sent if difference > threshold, or every 50 secondsPerformance of new metric•Works well for light to moderate load–static values dominate•Oscillates under heavy load–queuing dominates•Reason: there is no correlation between original and new values of delay after re-routing!Specific problems•Range is too wide–9.6 Kbps highly loaded link can appear 127 times costlier than 56 Kbps lightly loaded link–can make a 127-hop path look better than 1-hop•No limit in reported delay variation•All nodes calculate routes simultaneously–triggered by link updateConsequences•Low network utilization (50% in example)•Congestion can spread elsewhere•Routes could oscillate between short and long paths•Large swings lead to frequent route updates–more messages–frequent SPT re-calculationRevised link metric•Better metric: packet delay = f(queueing, transmission, propagation). •When lightly loaded, transmission and propagation are good predictors•When heavily loaded queueing delay is dominant and so transmission and propagation are bad predictorsRouting metric v.s. link utilization030601407550% 100%25% 75%225New metric(routing units)Utilization9.6 satellite9.6 terrestrial56 terrestrial56 satellite90Observations•Cost of highly loaded link never more than 3*cost when idle•Most expensive link is 7 * least expensive link•High-speed satellite link is more attractive than low-speed terrestrial linkRouting dynamics01.04.00.50.750.252.0 3.01.0 1.5 2.5 3.50.5Link reported costUtilizationBoundedoscillationMetric mapNetwork responseRouting dynamics01.04.00.50.750.252.0 3.01.0 1.5 2.5 3.50.5Reported costUtilizationMetric mapNetwork responseEasing ina new linkScalable IP RoutingHow to Make Routing Scale•Flat versus Hierarchical Addresses•Inefficient use of Hierarchical Address Space–class C with 2 hosts (2/255 = 0.78% efficient)–class B with 256 hosts (256/65535 = 0.39% efficient)•Still Too Many Networks–routing tables do not scale–route propagation protocols do not scaleInternet StructureRecent PastNSFNET backboneStanfordBARRNETregionalBerkeleyPARCNCARUAUNMWestnetregionalUNLKUISUMidNetregional…Internet StructureTodayBackbone service providerPeeringpointPeeringpointLarge corporationLarge corporationSmallcorporation“Consumer” ISP“Consumer” ISP“Consumer” ISPSubnetting•Add another level to address/routing hierarchy: subnet•Subnet masks define variable partition of host part•Subnets visible only within siteNetwork number Host numberClass B addressSubnet mask (255.255.255.0)Subnetted address111111111111111111111111 00000000Network number Host IDSubnet IDSubnet ExampleForwarding table at router R1Subnet Number Subnet Mask Next Hop128.96.34.0 255.255.255.128 interface 0128.96.34.128 255.255.255.128 interface 1128.96.33.0 255.255.255.0 R2Subnet mask: 255.255.255.128Subnet number: 128.96.34.0128.96.34.15128.96.34.1H1R1128.96.34.130Subnet mask: 255.255.255.128Subnet number: 128.96.34.128128.96.34.129128.96.34.139R2H2128.96.33.1128.96.33.14Subnet mask: 255.255.255.0Subnet number: 128.96.33.0H3Supernetting (CIDR)•Assign block of contiguous network numbers to nearby networks•Called CIDR: Classless Inter-Domain Routing•Protocol uses a (length, value) pair length = # of bits in network prefix•Use CIDR bit mask to identify block size•All routers must understand CIDR addressing•Routers can aggregate routes with a single advertisement -> use longest prefix matchSupernetting (CIDR)•Routers can aggregate routes with a single advertisement -> use longest prefix match•Hex/length notation for CIDR address:–C4.50.0.0/12 denotes a netmask with 12 leading 1 bits, i.e. FF.F0.0.0•Routing table uses “longest prefix match”–171.69 (16 bit prefix) = port #1–171.69.10 (24 bit prefix) = port #2–then DA=171.69.10.5 matches port #1–and DA = 171.69.20.3 matches port#2Chapter 4, Figure 26Border gateway(advertises path to11000000000001)Regional networkCorporation X(11000000000001000001)Corporation Y(11000000000001000000)Route Aggregation with CIDRIP Version 6•Features–128-bit addresses (classless)–multicast–real-time service–authentication and security –autoconfiguration –end-to-end