ECE544: Communication Networks-II, Spring 2007Today’s LectureIP AddressHow to Make Routing ScaleSlide 5Sub-nettingSubnet ExampleSlide 8Super-netting (CIDR)Slide 10Slide 11Slide 12Slide 13Slide 14Route Aggregation ExamplesHierarchical addressing: route aggregationHierarchical addressing: more specific routesSlide 18Address Matching in CIDRCIDR (Summary)IP addressing (Summary)Slide 22Introduction: Routing ProblemTwo main approachesRouting in the InternetInternet AS HierarchyIntra-AS RoutingSlide 28RIP ( Routing Information Protocol)RIP: ExampleSlide 31RIP: Link Failure and RecoveryRIP Table processingRIP Table example (continued)OSPF (Open Shortest Path First)OSPF “advanced” features (not in RIP)Hierarchical OSPFSlide 38Inter-AS routing in the Internet: BGPInternet inter-AS routing: BGPSlide 41BGP: controlling who routes to youSlide 43BGP operationBGP Operations (Simplified)Four Types of BGP MessagesBGP AttributesMost Important BGP attributesAttributes are Used to Select Best RoutesASPATH AttributeAS Graphs Do Not Show Topology!AS Graphs Depend on Point of ViewShorter Doesn’t Always Mean ShorterRoute Selection SummaryImplementing Customer/Provider and Peer/Peer relationshipsImport RoutesExport RoutesWhy different Intra- and Inter-AS routing ?Slide 59Multicast: one sender to many receiversSlide 61Slide 62Internet Multicast Service ModelMulticast groupsJoining a mcast group: two-step processSlide 66IGMP: Internet Group Management ProtocolHow IGMP WorksHow IGMP Works (cont.)IGMPSlide 71Multicast Routing: Problem StatementApproaches for building mcast treesShortest Path TreeReverse Path ForwardingBuilding the Reverse PathBuilding a Reverse Path TreeReverse Path Forwarding: exampleReverse Path Forwarding: pruningShared-Tree: Steiner TreeCenter-based treesCenter-based trees: an exampleSlide 83The First Intra-Domain Routing Protocol: DVMRPDistance-Vector Multicast Routing Protocol (DVMRP)Example TopologyPhase 1: Truncated BroadcastPhase 2: PruningSteady StateGrafting on New ReceiversSteady State after GraftingCurrent IP Multicast Routing ProtocolsCurrent IP Multicast Routing Protocols (cont.)Multicast Routing: MOSPFMulticast OSPF (MOSPF)Slide 101Slide 102Slide 103Slide 104Multicast Routing: PIMProtocol Independent Multicast (PIM)PIM Protocol OverviewPhase 1: Build Shared TreePhase 2: Sources Send to RPPhase 3: Stop EncapsulationPhase 4: Switch to Shortest Path TreePhase 5: Prune (S2 off) Shared TreeRP MechanismRP Mechanisms — OverviewBootstrap RouterBootstrap Router ElectionAll routers use hash function to map Group Address to RPSlide 118What Exactly is Needed?Inter-Domain Route ExchangeSlide 121Slide 122The Internet SolutionThe Internet Solution (cont)Slide 125MSDP -- Basic IdeaMSDP - Elements of OperationMSDP - Elements of Operation (cont)Slide 129How MSDP works with PIM-SMSlide 131Source Specific Multicast (SSM)How SSM WorksSource Specific MulticastSlide 135Slide 136Slide 137Slide 138Slide 139Slide 140Slide 141Slide 142Slide 143Slide 144Slide 145Slide 146Slide 147Slide 148Slide 149Slide 150Slide 151Slide 152Slide 153Slide 154Slide 155Slide 156Slide 157Slide 158Slide 159Slide 160Slide 161Slide 162Slide 163Slide 164Slide 165Slide 166Slide 167Slide 168Slide 169Slide 170Slide 171Slide 172Slide 173Slide 174Slide 175Slide 176Slide 177Slide 178Slide 179Slide 180How to Dig DeeperMulticast TextbooksECE544: Communication Networks-II, Spring 2007Sanjoy PaulLecture 8Includes teaching materials from L. Peterson, J. Kurose, K. AlmerothToday’s Lecture•Recap–Addressing•IP Address•Sub-netting•Super-netting (CIDR)•Route Aggregation Examples–Routing Protocols•Introduction•Intra-domain (RIP, OSPF)•Inter-domain (BGP)•Multicast–Introduction –Internet Group Management Protocol (IGMP)–Routing Protocols•Intra-domain (DVMRP, MOSPF, PIM)•Inter-domain (MSDP, SSM)–Reliable MulticastIP Address0networkhost10networkhost110network host1110multicast addressABCDclass1.0.0.0 to127.255.255.255128.0.0.0 to191.255.255.255192.0.0.0 to223.255.255.255224.0.0.0 to239.255.255.25532 bits“class-full” addressing:How 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 scaleToday’s Lecture•Recap–Addressing•IP Address•Sub-netting•Super-netting (CIDR)•Route Aggregation Examples–Routing Protocols•Introduction•Intra-domain (RIP, OSPF)•Inter-domain (BGP)•Multicast–Introduction–Internet Group Management Protocol (IGMP)–Routing Protocols•Intra-domain (DVMRP, MOSPF, PIM)•Inter-domain (MSDP, SSM)–Reliable MulticastSub-netting•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.0H3Today’s Lecture•Recap–Addressing•IP Address•Sub-netting•Super-netting (CIDR)•Route Aggregation Examples–Routing Protocols•Introduction•Intra-domain (RIP, OSPF)•Inter-domain (BGP)•Multicast–Introduction–Internet Group Management Protocol (IGMP)–Routing Protocols•Intra-domain (DVMRP, MOSPF, PIM)•Inter-domain (MSDP, SSM)–Reliable MulticastSuper-netting (CIDR)•Class addressing doesn’t match real needs:–Class C is 255 addresses, too small–Clsss B is 64K addresses, too big•Need method of allocating addresses in multiple sizes•Assign block of contiguous network numbers to nearby networks•Called CIDR: Classless Inter-Domain RoutingClassless Inter Domain Routing (CIDR)Class B:Class C:Net ID Host IDHost IDNet ID Problem: Class B addresses are running out  Solution: Allocate multiple Class C addresses Problem: Random allocation of Class C addresses need multiple routing table entries