RoutingOutlineShortest PathShortest Path - ContinuedShortest Path - continuedDynamic RoutingDynamic Routing - continuedQuality of Service RoutingQuality of Service Routing (cd)Slide 10Slide 11UCBRoutingJean WalrandU.C. Berkeleywww.eecs.berkeley.edu/~wlrUCBOutlineShortest PathObjectiveBellman-FordDijkstraAdaptive RoutingQoS RoutingUCBShortest PathObjective: Find shortest path between two nodes (e.g., S and D) in a graphExample:Note: Myopic shortest path is not optimal!123434341SDUCBShortest Path - Continued“Dynamic Programming” or Bellman-Ford:123434341SD123434341SD7413755 = min{3 + 3, 4 + 1}7 = min{1 + 7, 2 + 5}UCBShortest Path - continuedDijkstra:123434341SD12455687UCBDynamic RoutingBase route on “congestion” Example:0.3ms0.1ms0.1ms0.2ms0.25ms0.4ms0.5msUCBDynamic Routing - continuedDifficulty: Oscillations0.1ms0.8ms0.8ms0.1msUCBQuality of Service RoutingShortest Path: Single Additive “Cost” length(path) = sum of length(link)Shortest length = AShortest length = BabShortest length = min{a + A, b + B}UCBQuality of Service Routing (cd)Maximum Bandwidth bandwidth(path) = minimum of bandwidth(link)Max. bw = AMax. bw = BabMax bw = max{min{a, A}, min{b, B}}UCBQuality of Service Routing (cd)Multi-objective: e.g., (delay, bw)(min. d = 3, max. bw = 10)(min. d = 6, max. bw = 15)(min. d = 3, max. bw = 10)or(min. d = 6, max. bw = 15)UCBQuality of Service Routing (cd)Example(4, 18)(2, 14)(8, 30)(4, 12)(5, 15)(4, 20)(3, 10)(4, 20)(7, 30)D[Min d, Max bw](d, bw)[12, 20][7, 10][8, 10][11, 20]A [16, 18]B [11, 10]C [10, 10]D [13, 14]Better dBetter bwADB
View Full Document