Transcript Document
Compact Routing Schemes
Mikkel Thorup
Uri Zwick
AT&T Labs – Research
Tel Aviv University
Routing
3
u
v
2
1
Packet:
label(v)
information
Handshaking
u
v
header(u,v)
Packet: header(u,v)
information
The same header is used for all messages
sent from u to v
Routing in Trees
Each vertex is assigned a
(1+o(1))log2n – bit label.
Given label(u) and label(v),
it is possible to find, in
constant time, the right
edge to take from u.
u
v
Similar result by Fraigniaud
and Gavoille [ICALP’01]
Routing in General Graphs
Stretch
Table Size
Handshaking?
3
n1/2
no
5
n1/3
yes
7
n1/3
no
2k-1
1/k
n
yes
4k-5
n1/k
no
Previous Results
Stretch
Table Size
Authors
3
n2/3
Cowen ‘99
5
n1/2
O(k2)
n1/k
Eilam, Gavoille
Peleg ‘98
Awerbuch
Peleg ‘92
Our Results Are
Essentially Optimal!
Labels must be at least log2n – bit long.
In graphs, for stretch<3, the total size of
the routing tables must be (n2). For
stretch<5, the total size must be (n3/2).
Conjecture: For stretch<2k+1, the total size
of the tables must be (n1+1/k). (Equivalent
to a well known girth conjecture of Erdös.)
Tree Routing – A Practical Scheme
O(log2n)-bit labels.
Arbitrary port numbers.
DFS numbering:
For every vertex u, let fu
be the largest descendant
4
of u. Then v is a descendant
of u iff v [u, f ]
10 1
7
2
3
5
11
6
7
u
A trivial solution with
O(deg(v)) memory.
10
8
9
12
13
14
Tree Routing – A Practical Scheme (Cont.)
Let s(v) be the number
of descendants of v.
Let pv be the
parent of v. Then,
vertex v is heavy if
s(v)s(pv)/2, and
light otherwise.
14
8
2
7
1
1
1
4
3
1
1
3
1
1
Tree Routing – A Practical Scheme (End)
0
r
e1
2
2
3
1
e2
e3
3
e4
4 v
The light-level lv of a vertex v is the
number of light vertices on the path
to it from the root.
Claim: lv<log2n
label(v)=(v,port(e1),port(e2),…)
At v we store:
v, fv, hv, lv, port(v,pv) and port(v,hv).
Routing in Graphs
Choose a Set of Centers
centA(v) = a center closest to v
Construct Clusters
cluster
clusterA(v) = vertices that are
closer to v than to all centers.
Keep Routing Info
from v to AclusterA(v)
If vclusterA(u),
Route Directly
u
w
v
For any w on the shortest
path we have vclusterA(w).
If vclusterA(u),
Route through centA(v)
centA(v)
Label(v)=
u
v
(v,centA(v),port(centA(v),v))
(cent A (v ), v ) ( u, v )
( u, cent A (v )) 2 ( u, v )
( u, cent A (v )) (cent A (v ), v ) 3 ( u, v )
How do we choose centers?
We want A such that
|A|=O(n1/2)
clusterA(v)=O(n1/2), for every v
[Cowen does this with O(n2/3)]
Algorithm center(G)
A; WV;
While W
{
AA choose(W,n1/2);
W{wV | clusterA(w)>4n1/2 };
}
Return A;
The expected size of A is O(n1/2log n).
Smaller Tables,
Larger stretch
Use a hierarchy of centers.
Construct a tree cover
of the graph.
Identify an appropriate tree
from the cover and route on it.
Tree Cover
Each vertex contained in at most n1/k trees.
For every u,v, there is a tree with a path of
stretch at most 2k-1 between them.
Is there a
routing scheme with:
• Table size = O(n1/k)
• Label size = O(log n)
• No handshaking
???