CS 452/652 Fall 2019 - Lecture 23

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(N³) complexity
  • ok for dense graphs
• Dijkstra's Algorithm
  • less computational overhead for sparse graphs
  • notation:
    

    N	set 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(N³), with heap O(N² 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