# CS 452/652 Fall 2019 - Lecture 23

November 1, 2019 prev next

### Priorities (cont'd)

• priority inversion
• lower-priority tasks indirectly keeps higher-priority task from running
• performance (latency) problem
• correctness problem (starvation), if system fully loaded
• examples: lower number = higher priority
• example scenario A
• t10 sends to t1, then t5 wants to run
• t1 runs on behalf of t10, so t5 should be able to preempt
• ⇒ adjust server priority to current client's priority
• example scenario B
• t10 runs on behalf of t8, t7 preempts, then t5 wants to send to t10
• t7 keeps t10 from completing its computation, t5 blocked
• ⇒ boost server priority to waiting client's priority
• also: priority-based Send queues?

### Routing

• abstracted as path-finding to nodes in a graph
• shortest-path routing finds consistent paths without loops
• but is not necessarily efficient, because parallel links might go unused
• Floyd-Warshall Algorithm
• brute-force iteration of links with O(N3) complexity
• ok for dense graphs
• Dijkstra's Algorithm
• less computational overhead for sparse graphs
• notation:
Nset of nodes
N'set of 'visited' nodes
c(u,v)link cost u→v, possibly ∞
D(u,v)path cost u→v
P(u,v)2nd-last hop on path from u→v

• algorithm at Node u
```N' = { u }
D(u,v) = c(u,v) for all neighbours v of u
loop:
find w not in N' with minimum D(u,w)
add w to N'
for all v not in N' and adjacent to w:
if (D(u,w) + c(w,v) < D(u,v)):
D(u,v) = D(u,w) + c(w,v)
P(u,v) = w
until N' == N
```
• invariant at step k: N' contains nearest k destinations
→ i.e., the shortest paths to k destinations are known
• result: trace previous hops D(u,v) backwards to obtain full path and next hop information
• complexity
• O(N) for 'find w', but heap-sort could reduce to O(log N)
• O(E) for 'for all v'
• O(N) for running the algorithm for all nodes
• worst-case O(N3), with heap O(N2 log N)
• sparse graph: E << N (cf. Floyd-Warshall)
• Notes
• 'shortest' is common optimization objective to compute consistent paths without loops
• ... especially important in distributed computation (networking)
• compute routing information only for turnouts?
• build overlay data structure?
• add reversing by adding fake second edge to turnouts used as 'merge' (along with fake cost)
• can compute alternative paths, if marginal cost does not exceed distance of minimum loop
• example taken from Slide 4-83 of Kurose/Ross textbook slides