UCB Routing Jean Walrand U C Berkeley www eecs berkeley edu wlr Outline UCB Shortest Path Objective Bellman Ford Dijkstra Adaptive Routing QoS Routing UCB Shortest Path Objective Find shortest path between two nodes e g S and D in a graph Example Note Myopic shortest path is not optimal 1 S 2 3 4 4 3 3 4 1 D UCB Shortest Path Continued Dynamic Programming or Bellman Ford 7 1 4 3 S 7 3 2 5 5 min 3 3 4 1 7 min 1 7 2 5 4 4 3 3 4 1 1 D UCB Shortest Path continued Dijkstra 3 1 1 S 2 2 4 3 4 5 4 3 5 4 1 6 7 8 D UCB Dynamic Routing Base route on congestion Example 0 4ms 0 2ms 0 5ms 0 25ms 0 3ms 0 1ms 0 1ms UCB Dynamic Routing continued Difficulty Oscillations 0 8ms 0 1ms 0 1ms 0 8ms UCB Quality of Service Routing Shortest Path Single Additive Cost length path sum of length link a Shortest length min a A b B Shortest length A b Shortest length B UCB Quality of Service Routing cd Maximum Bandwidth bandwidth path minimum of bandwidth link a Max bw A b Max bw B Max bw max min a A min b B UCB Quality of Service Routing cd Multi objective e g delay bw min d 3 max bw 10 min d 3 max bw 10 or min d 6 max bw 15 min d 6 max bw 15 Quality of Service Routing cd UCB Example Better bw A Min d Max bw 12 20 8 30 7 10 A 16 18 B 11 10 C 10 10 4 18 D 13 14 d bw 4 20 4 12 3 10 5 15 2 14 D B C 8 10 4 20 11 20 Better d 7 30 D
View Full Document
Unlocking...