$\newcommand{\indx}{{\it index}}$

Routing

Application of Chernoff: analysis of load balancing.

• Already saw balls in bins example

• synchronous message passing
• bidirectional links, one message per step
• queues on links
• goal: minimizie congestion
• sometimes impossible (e.g. all same destination)
• permutation routing
• oblivious algorithms each packet ignores others; route based on own source/destination only
• Theorem Any deterministic oblivious permutation routing requires $\Omega(\sqrt{N/d})$ steps on an $N$ node degree $d$ network.
  • reason: some edge has lots of paths through it.
  • homework: special case
• Hypercube.
  • $N$ nodes, $d=\log_2 N$ dimensions
  • $Nd$ directed edges
  • bit representation
  • natural routing: bit fixing (left to right)
  • paths of length $d$---lower bound on routing time
  • $Nd$ edges for $N$ length $d$ paths suggest no congestion bound
  • but deterministic bound $\Omega(\sqrt{N/d})$
• Randomized routing algorithm:
  • $O(d)=O(\log N)$ randomized
  • how? load balance paths.
• First idea: random destination (not permutation!), bit correction
  • Average case, but a good start.
  • $T(e_i)=$ number of paths using $e_i$
  • by symmetry, all $E[T(e_i)]$ equal
  • expected path length $d/2$
  • LOE: expected total path length $Nd/2$
  • $dN$ edges in hypercube
  • Deduce $E[T(e_i)] = 1/2$
  • but note $T(e_i)$ is a sum of independent indicator variables
  • Chernoff: every edge gets $\le 3d$ (prob $1-1/N$)
• Naive usage:
  • $d$ phases, one per bit
  • $3d$ time per phase
  • $O(d^2)$ total
• What if don't wait for next phase?
  • FIFO queuing
  • total time is length plus delay
  • Expected delay $\le E[\sum T(e_l)] = d/2$.
  • Chernoff bound? no. dependence of $T(e_i)$.
  • because same packet could delay several of my hops
• High prob. bound:
  • consider paths sharing $i$'s fixed route $(e_0,\ldots,e_k)$
  • Suppose $S$ packets intersect route (use at least one of $e_r$)
  • claim delay $\le |S|$
  • Suppose true, and let $H_{ij}=1$ if $j$ hits $i$'s (fixed) route. $$ \begin{eqnarray*} E[\mbox{delay}] &\le &E[\sum H_{ij}]\\ &\le &E[\sum T(e_l)]\\ &\le &d/2 \end{eqnarray*} $$ (second sum overcounts first if routes share $>1$ edge)
  • Now Chernoff does apply ($H_{ij}$ independent conditioned on fixed $i$-route).
  • $|S|=O(d)$ w.p. $1-2^{-5d}$, so $O(d)$ delay for all $2^d$ paths.
• Lag argument
  • Exercise: once packets separate, don't rejoin
  • Route for $i$ is $\rho_i=(e_1,\ldots,e_k)$
  • charge each delay to a departure of a packet from $\rho_i$.
  • Packet waiting to follow $e_j$ at time $t$ has: Lag $t-j$
  • Delay of $i$ is lag crossing $e_k$
  • When $i$ delay rises to $l+1$, some packet from $S$ has lag $l$ (since crosses $e_j$ instead of $i$).
  • Consider last time $t'$ where a lag-$l$ packet exists on path
    • some lag-$l$ packet $w$ crosses $e_{j'}$ at $t'$ (others increase to lag-$(l+1)$)
    • $w$ leaves (next edge is off path) at this point (if not, $w$ has lag $l$ at $e_{j'+1}$ next time)
    • charge one delay to $w$.
• Worst case destinations
  • Idea [Valiant-Brebner] From intermediate random destination, route back!
  • routes any permutation in $O(d^2)$ expected time.
  • what's going in with $\sqrt{N/d}$ lower bound?
  • Adversary doesn't know our routing so cannot plan worst permutation
  • We are hedging: double typical delivery time, but eliminate worst case

Similar analysis for routing on butterfly.