Lecture 7 & 8: Routing in Hypercube
September 21, 2004 Scribe:
Hypercube
A hypercube of dimension d is constructed a follows:
· Take two hypercubes of dimension d-1
· Connect identically labeled nodes
· Add a prefix of 0 to all nodes of hypercube 1 of dimension d-1
· Add a prefix of 1 to all nodes of hypercube 2 of dimension d-1
· Base case
o Hypercube of dimension 1
Properties
· An N-node hypercube is a graph where each node has degree log N
Proof: A hypercube of dimension (and degree) has N = 2d nodes
Base case: degree 1
Inductive hypothesis: Assume a hypercube of dimension d-1 has 2d-1 nodes.
Inductive step: To construct a d dimensional hypercube, we join together two d-1 dimensional hypercubes.
The degree of each node becomes d.
The number of nodes is now 2*2d-1 = 2d
· A dimension d hypercube has (d*N)/2 edges = (NlogN)/2 = 2*2d-1
Proof: N nodes each of degree d
Example: d = 3
Edges = 2*2d-1
= 3*22
= 12
· Adjacent nodes differ by 1 bit only
Routing: Oblivious routing, routing at each node.
Oblivious: Algorithm (through path ) is determined at the source.
Example: 010011 à 110101
-Use exclusive OR and route in the direction desired.
010011
110011
110111
110101
· Algorithm:
o Go from left to right on the source address.
o If the current bit is not equal to the corresponding bit int the destination, change it.
· Property:
o The length of a path from s (source) to t (destination) = # of bits that are different in s, t ( = # of 1’s in s XOR t)
The diameter of the hypercube is d = log N of N nodes.
Proof: The addresses have d bits. If they’re all different in s, t
Hamilton Cycle Problem
· Go over each vertex without covering an edge or vertex twice.
· Comes back to the starting point.
· NP-hard: no one knows how to solve in 0(Nk) for any fixed k.
Gray Code: Each time you increment, you flip one bit.
Inductive Construction:
2 bit gray code: / 3 bit gray code00 / 010 / 100 / 2 bit gray codes – reverse 1
First one gets prefix 0
Second one gets prefix 1
01 / 011 / 101
11 / 001 / 111
10 / 000 / 110
Reversed
By induction, must prove that 000 ßà 100 and 010ßà110
Theorem: If you follow the nodes corresponding to the gray code on the hypercube, you get a Hamiltonian cycle.
Degree 3 Hypercube Degree 4 Hypercube
Proof sketch: By induction, do identical Hamiltonian cycles on:
- the 2 dimensional d-1 hypercubes
- leave out the same edge
- then the endpoints differ only in their leading bits.
- By induction you can do this for any degree hypercube
Star Topology
Tree Topology
All node pairs have a unique path between them.
Solution to the bandwidth problem: Fat Tree.
Bandwidth increases exponentially higher up the tree.
Routing:
Permutation routing:
1 2 3 4 5 6 7 8
5 4 3 8 7 6 2 1
Issue: Max delivery time can be long if there is contention from a link.
Theorem: On the hypercube there exists a permutation that delivery time is ≥
└ N/d ┘ for any deterministic algorithm.
Randomized Routing:
For any s-t pair:
Pick an intermediate node v uniformly at random (can be done with d independent coin tosses, 1 for each bit of v).
Phase 1: Route from s to v
Phase 2: Route form v to t.
Theorem: With high probability (1 – ε for small ε) the routing will take O(log N) steps for any randomized algorithm.