Randomized Algorithms (Spring 2010)/More on Chernoff bounds

Permutation Routing

The problem raises from parallel computing. Consider that we have [math]\displaystyle{ N }[/math] processors, connected by a communication network. The processors communicate with each other by sending and receiving packets through the network. We consider the following packet routing problem:

• Every processor is sending a packet to a unique destination. Therefore for [math]\displaystyle{ [N] }[/math] the set of processors, the destinations are given by a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [N] }[/math], such that for every processor [math]\displaystyle{ i\in[N] }[/math], the processor [math]\displaystyle{ i }[/math] is sending a packet to processor [math]\displaystyle{ \pi(i) }[/math].
• The communication is synchronized, such that for each round, every link (an edge of the graph) can forward at most one packet.

With a complete graph as the network. For any permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [N] }[/math], all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is sparse, such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices.

The hypercube is one of the graphs with these desirable properties.

Routing in a hypercube

A hypercube, sometimes called a Boolean cube, a Hamming cube, or just cube, is defined over [math]\displaystyle{ N }[/math] nodes, for [math]\displaystyle{ N }[/math] a power of 2. We assume that [math]\displaystyle{ N=2^d }[/math]. A hypercube of [math]\displaystyle{ d }[/math] dimensions, or a [math]\displaystyle{ d }[/math]-cube, is an undirected graph with the vertex set [math]\displaystyle{ \{0,1\}^d }[/math], such that for any [math]\displaystyle{ u,v\in\{0,1\}^d }[/math], [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] are adjacent if and only if [math]\displaystyle{ h(u,v)=1 }[/math], where [math]\displaystyle{ h(u,v) }[/math] is the Hamming distance between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math].

A [math]\displaystyle{ d }[/math]-cube is a [math]\displaystyle{ d }[/math]-degree regular graph over [math]\displaystyle{ N=2^d }[/math] vertices. For any pair [math]\displaystyle{ (u,v) }[/math] of vertices, the distance between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] is at most [math]\displaystyle{ d }[/math]. (How do we know this? Since it takes at most [math]\displaystyle{ d }[/math] steps to fix any binary string of length [math]\displaystyle{ d }[/math] bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

Bit-Fixing Routing Algorithm:

For each packet: Let [math]\displaystyle{ u, v\in\{0,1\}^d }[/math] be the origin and destination of the packet respectively. For [math]\displaystyle{ i=1 }[/math] to [math]\displaystyle{ d }[/math], do: if [math]\displaystyle{ u_i\neq v_i }[/math] then traverse the edge [math]\displaystyle{ (v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d) }[/math].

This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property oblivious routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called switches).

When routing all [math]\displaystyle{ N }[/math] packet in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge. With some "queuing policy", which specifies the schedule of delivering the packets in the queue.