CS 536 ParkRoutingProblem: Given more than one path from source to des-tination, which one to take?Features:• Architecture• Algorithms• Implementation• PerformanceCS 536 ParkArchitectureHierarchical routing:−→ Internet: intra-domain vs. inter-domain routing−→ separate decision makingStubTier 2Tier 1Tier 3Tier 2Domain FDomain EDomain DDomain BDomain CDomain AStubCS 536 ParkGranularity of routing network:• Router• Domain: autonomous system (AS)→ 16 bit identifier: ASN (e.g., Purdue 17)→ assigned by IANA along with IP prefix block (CIDR)Network topology (i.e., map/connectivity):• Router graph→ node: router→ edge: physical link between two routers• AS graph→ node: AS→ edge: physical link between 2 or more border routers→ sometimes at exchange point or networkCS 536 ParkRouter type:• border router→ includes access router (to stub customer)• backbone routerAS type:• stub AS→ no forwarding→ may be multi-homed (more than one provider)• transit AS→ tier-1: global reachability & no provider above→ tier-2 or tier-3: providers aboveCS 536 ParkAS graph:PeeringTransit ASTransit ASTransit ASTransit ASStub ASStub ASProviderCustomerInter-AS relationship: bilateral• customer-provider: customer subscribes BW from provider→ most common→ customer can reach provider’s reachable IP space• peering:→ only the peer’s IP address and below→ the peer’s provider’s address space: invisibleCS 536 ParkCommon peering:• among tier-1 providers→ ensures global reachability• among tier-2 providers→ economic factors• among stubs→ economic factors→ e.g., content provider & access (“eyeball”) providerCS 536 ParkRoute or path: criteria of goodness• Hop count• Delay→ composed of three parts• Bandwidth→ available bandwidth• Loss rateComposition of goodness metric:−→ quality of end-to-end path• Additive: hop count, delay• Min: bandwidth• Multiplicative: loss rateCS 536 ParkGoodness of routing:−→ assume N users or sessions−→ suppose path metric is delay• System optimal routing→ choose paths to minimizePNi=1Di• User optimal routing→ each user i chooses path to minimize Di→ selfish actionsCS 536 ParkPros/cons:• System optimal routing:– Good: minimizes delay for the system as a whole– Bad: complex and difficult to scale• User optimal routing:– Good: simple– Bad: may not make efficient use of resources→ utilizationSome pitfalls of user optimal routing:−→ stemming from selfishness• Fluttering or ping pong effect• Braess paradoxCS 536 ParkBraess paradox example:• 6 users sending 1 Mbps traffic• Delay on shared link increases with traffic volume x• Users make routing decisions one after the otherUser 1User 2User 3User 4User 5User 65x + 15x + 1x + 25x + 25ABCD• 3 users will take A → B → D• 3 users will take A → C → D• total delay per user: (5 · 3+1)+(3+25)=44CS 536 ParkResource provisioning:−→ high bandwidth link is added between B and CUser 1User 2User 3User 4User 5User 65x + 15x + 1x + 25x + 25ABCD1• User 1: A → B → C → D (13)• User 2: A → B → C → D (23)• User 3: A → B → C → D (33)• User 4: A → B → C → D (43)• User 5: A → B → D (52)• User 6: A → C → D (52)CS 536 ParkAdding extra link should improve things, but has theopposite effect−→ high-speed link induces load imbalance−→ paradox possible due to selfishness−→ D. Braess (1969)−→ cannot arise in system optimal routing−→ i.e., cooperative routingModus operandi of the Internet: user optimal routing−→ simplicity wins the dayCS 536 ParkAlgorithmsFind short, in particular, shortest paths from source todestination.Key observation on shortest paths:• Assume p is a shortest path from S to D→ Spà D• Pick any intermediate node X on the path• Consider the two segments p1and p2→ Sp1à Xp2à D• The path p1from S to X is a shortest path, and sois the path p2from X to DCS 536 ParkIllustration:p1SDshortest pathshortest path shortest pathSDXpp2−→ reverse implication need not hold−→ suggests algorithm for finding shortest pathCS 536 ParkProcedure: Grow a routing tree T rooted at source S−→ initially T only contains S1. Find a node X with shortest path from S→ there may be more than one such node→ add X (and path Spà X) to routing tree T2. Find node Y/∈T with shortest path from S→ update existing paths if going through Y is shorter→ i.e., min{d(S, Z),d(S, Y )+`(Y,Z)}→ need only check for Z/∈T3. Repeat step two until no more nodes left to addObservations:−→ once node is added, it’s final (no backtracking)−→ builds minimum spanning tree routed at S−→ Dijkstra’s algorithmCS 536 ParkRemarks:• Running time: O(n2) time complexity→ n: number of nodes• If heap is used: O(|E|log |V |)→ good for sparse graphs: |E|¿n2→ e.g., if linear: O(n log n)• Can also be run “backwards”→ start from destination D and go to all sources→ a variant used in inter-domain routing→ forward version: used in intra-domain routing• Source S requires global link distance knowledge→ centralized algorithm (center: source S)→ every router runs Dijkstra with itself as sourceCS 536 Park• Internet protocol implementation→ OSPF (Open Shortest Path First)→ link state algorithm→ broadcast protocol• Minimum spanning tree routed at S:→ multicasting: multicast tree→ standardized but not implemented on InternetCS 536 ParkDistributed/decentralized shortest path algorithm:−→ Bellman-Ford algorithm−→ based on shortest path decomposition propertyKey procedure:• Each node X maintains current shortest distance toall other nodes→ a distance vector• Each node advertises to neighbors its current best dis-tance estimates→ i.e., neighbors exchange distance vectors• Node X, upon receiving an update from neighbor Y ,performs update: for all Zd(X, Z) ← min{d(X, Z),d(Y,Z)+`(X, Y ) }... same criterion as Dijkstra’s algorithmCS 536 ParkRemarks:• Running time: O(n3)• Each source or router only talks to neighbors→ local interaction→ no need to send update if no change→ if change, entire distance vector must be sent• Knows shortest distance, but not path→ just the next hop is known• Elegant but additional issues compared to Dijkstra’salgorithm→ e.g., stability• Internet protocol implementation→ RIP (Routing Information Protocol)CS 536 ParkQoS routing:Given two or more