Hierarchical RoutingEECS 228Abhay [email protected] 16, 2002Abhay K. Parekh: Topics in Routing2Hierarchical RoutingT Is a natural way for routing to scaleY SizeY Network AdministrationY GovernanceT Exploits address aggregation and allocationT Allows multiple metrics at different levels of the hierarchy6432132436137851121011Inter DomainRoutingOSPFRIPIGRPOctober 16, 2002Abhay K. Parekh: Topics in Routing3Why is hierarchical routing important?T The internet is an interconnection of unequal networksT Interconnection arrangements drive Y the competitive landscapeY the robustness of the networkY end-to-end performanceT Interconnection is central to all large networksY VoiceY DataY WirelessY CableOctober 16, 2002Abhay K. Parekh: Topics in Routing4Why are there so many players?T www.thelist.comY How many ISP’s in the 415 area code?T That start with A-C: about 200…T Just DSL that start with A-C: about 80T In the telephone networkY How many independent telephone companies in 1894-1902 in the US?T 3039 commercial companies, 979 co-operativesY By controlling interconnection Bell got rid of themY Interconnection is now regulated (CLECs)October 16, 2002Abhay K. Parekh: Topics in Routing5What is an InterconnectionT Access to sites reachable via routing and transport facilitiesT But could also include:Y WireT SLA + LeaseY SpaceT SizeT SpaceY Access to OSSY Dispute Resolution ProcessY TermOctober 16, 2002Abhay K. Parekh: Topics in Routing6Interconnections occur at many levels643213ABC2436137851121011Inter DomainRoutingOSPFRIPIGRPOctober 16, 2002Abhay K. Parekh: Topics in Routing7Interconnections occur at many levels643213ABC2436137851121011OSPFRIPIGRPA.1D.1D.2D.3October 16, 2002Abhay K. Parekh: Topics in Routing8Interconnections occur at many levels643213ABC2436137851121011OSPFRIPIGRPA.1D.1D.2D.3E.1E.2E.3October 16, 2002Abhay K. Parekh: Topics in Routing9Interconnections occur at many levels643213ABC2436137851121011OSPFRIPIGRPA.1D.1D.2D.3E.1E.2E.3October 16, 2002Abhay K. Parekh: Topics in Routing10Interconnections occur at many levels13137511211A.1D.1E.2D.2D.3E.1E.3DEOctober 16, 2002Abhay K. Parekh: Topics in Routing11Examples of overlaid interconnecting networksT IP over ATMT Multicast over IPT DSL over POTST IP over CATVT Etc., T Each involves routingOctober 16, 2002Abhay K. Parekh: Topics in Routing12Two ways to interconnect IP Networks…T PeeringY The business relationship whereby ISPs reciprocally provide to each other connectivity to each others’ transit customersT TransitY The business relationship whereby one ISP provides (usually sells) access to all destinations in it’s routing tableWilliam B. Norton, “Internet Service Providers and Peering”October 16, 2002Abhay K. Parekh: Topics in Routing13Peering and Transit Figures fromWilliam B. Norton, “Internet Service Providers and Peering”October 16, 2002Abhay K. Parekh: Topics in Routing14Benefits of Transit v/s PeeringWilliam B. Norton, “Internet Service Providers and Peering”October 16, 2002Abhay K. Parekh: Topics in Routing15Moving from Transit to PeeringWilliam B. Norton, “Internet Service Providers and Peering”October 16, 2002Abhay K. Parekh: Topics in Routing16Peering AttributesT Bandwidth Pricing: Everything you can think ofY Traffic may be asymmetric (web servers)Y Clout may varyY Some existing and suggested methodsT Zero Charge (Bill and Keep)T Average CostT Fully distributed cost pricingT Ramsey PricingT Wholesale Pricing T Marginal Cost PricingT Bandwidth is undifferentiated (can’t peer for video quality bw)T Connection MethodY Direct ConnectionY Internet ExchangeOctober 16, 2002Abhay K. Parekh: Topics in Routing17Internet Infrastructure providesundifferentiated serviceT More capacity is thrown at the undifferentiated network, and emphasis continues on “speeding up the internet”, but this just speeds up existing applicationsT No future for internet media or other bandwidth intensive applicationsT No future for significant high speed access penetrationT These are huge lost opportunities!!Undifferentiated Network here to stay?Undifferentiated Network here to stay?No BusinessModel Cop-outNo way to charge, peer or deliver high speed/quality sensitive applicationsOctober 16, 2002Abhay K. Parekh: Topics in Routing18Name of the Game: ReachabiltyT BGP is the way by which ISPs co-operate on reachabilityT Routing efficiency and performance is important, but not essentialY E.g. Path Vector uses many messagesT Power of BGP is that it can express many different ISP routing policies without exposing internal network statistics such as load and topologyT Tremendous growth in the last 10 years…October 16, 2002Abhay K. Parekh: Topics in Routing19October 16, 2002Abhay K. Parekh: Topics in Routing20Skitter LegendT Plot the AS based on polar co-ordinates (r,θ):Y r = 1- log (As degree +1 / Max Degree+1)T Higher the degree lower the radiusY Θ = longitude of AS headquartersOctober 16, 2002Abhay K. Parekh: Topics in Routing214/1-4/16 2002•1,224,733 IP addresses, •2,093,194 IP links, •932,000 destinations, •70% of globally routable network prefixes; •10,999 ASes (84% of ASes),•34,209 peering sessionsOctober 16, 2002Abhay K. Parekh: Topics in Routing22October 16, 2002Abhay K. Parekh: Topics in Routing23BGPT Runs over TCP port 179T One Border Routers can be involved in multiple sessionsT Border Routers Y from the same AS speak IBGPY from different AS’s speak EBGPT EBGP and IBGP are essentially the same protocolY IBGP can only propagate routes it has learned directly from its EBGP neighborsY All routers in the same AS form an IBGP meshY Important to keep IBGP and EBGP in syncOctober 16, 2002Abhay K. Parekh: Topics in Routing24Four message typesT Open: Session establishment id exchangeT Notification: exception driven informationT Keep Alive: soft state T Update: path vector informationOctober 16, 2002Abhay K. Parekh: Topics in Routing25Update MessageT Withdrawn Routes: No longer validT Attributes: Path Vector, weights and other information about each of the destinationsT <length,prefix>: CIDR notation for the destinationInfeasible Route LengthWithdrawn Routes (variable)Total Path Attribute LenPath Attributes (variable)Length|Prefix<length,prefix>..October 16, 2002Abhay K. Parekh: Topics in Routing26Classless Inter-domain Routing AddressesT 32 bits in the address divided into 4 8-bit parts, A.B.C.D Y Each part takes value 0,1,2,…,255T E.g. 128.23.9.0T Specify a range of addresses by a
View Full Document
Unlocking...