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
- 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.