\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt
$$\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
• 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
• 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.