Transcript slides

Near-Optimal Hot-Potato Routing
on Trees
Costas Busch
Malik Magdon Ismail
Marios Mavronicolas
Roger wattenhofer
Rensselaer Polytechnic Inst.
Rensselaer Polytechnic Inst.
University of Cyprus
ETH Zurich
1
Trees
Trees are important in many networks
(i.e. spanning trees)
2
Routing on Trees
•Every node generates at most one packet
•Packets follow shortest paths
3
Network Model
•Synchronous network
•Bi-directional links
•One packet per time step
4
Hot-Potato Routing
Time 0
Buffer-less nodes
5
conflict
Time 1
6
Time 2
deflected
7
Time 3
8
Time 4
9
Hot-potato routing is interesting:
•Optical networks
•Simple hardware implementations
•Works well in practice:
Bartzis et al.: EUROPAR 2000
Maxemchuck: INFOCOM 1989
10
Objective: Find hot-potato algorithm
which minimizes routing time
The time until the last packet
is delivered to its destination
11
Congestion: Maximum numbers of
packets that share an edge
C 3
12
Dilation:
Maximum path length
D 6
13
A lower bound on Routing Time:
Congestion+Dilation
(C  D)
We want to find an algorithm
close to this lower bound
14
Our contributions:
•Deterministic Algorithm: O ((C  D )logn )
node degree
network size
2
O
((
C

D
)
log
n)
•Randomized Algorithm:
degree independent
15
Related Work for Trees
•Matching Routing
•Direct Routing
•Hot-Potato routing
[ACG94] [PRS97] [Z97]
[AHLT98][BMMS04]
[RSW00]
Most results have routing time O(n)
(worst case bound for O(C+D))
16
Presentation Outiline
•Deterministic Algorithm
•Randomized Algorithm
17
Deterministic Algorithm
1. Divide time into phases according to
short nodes
2. At each phase send packets to
their destinations greedily
18
Short Node:
n

2
n

2
……
every subtree has at most
n

2
n
2
nodes
19
Example
short node
6
6
n 14

7
2 2
20
Phase 1:
Route packets that cross the short node
……
21
Phase 2:
In each subtree get the short nodes
……
22
Phase 2:
In each subtree get the short nodes
……
23
Phase 2:
Route packets that cross the short nodes
…………
24
There are at most
logn
n
phases
n
2
n
4
1
25
Phase k:
Route packets that cross the short node
C

……
Bound on number of packets: C
26
Phase k:
A packet follows its path greedily
27
However, packets can conflict
and get deflected
conflict
deflected
28
Deflection Sequence
[Borodin, Rabani, Schieber 1997]
p
p1
p2
p j 2 pj 1 p j
If a packet p is deflected
then some other packet p j
reaches its destination
29
Since there are at most C packets,
there are at most C deflections
Worst Routing Time for a packet:
2C  D
deflections
Initial distance
30
Total Routing Time
(2C  D )  logn
Packet time
In a phase
Number
of Phases
31
Presentation Outiline
•Deterministic Algorithm
•Randomized Algorithm
32
Randomized Algorithm
Same with deterministic algorithm,
with only difference:
Packet conflicts are resolved
according to random packet priorities
33
Packet Priorities:
Low:
each packet starts with
a low priority
High:
when a packet is deflected
it increases its priority
with probability
1
4(C  D )
34
A high priority packet can
conflict with at most 2C packets
C
C
……
From those packets, O (1)
are expected to be in high priority
35
A high priority packet
successfully reaches its destination
1
with probability
2
Thus O (logn ) attempts to become
high priority are enough.
36
Total Routing Time
 (C  D ) logn  logn
Packet time
In a phase
Number
of Phases
37
Discussion
We presented two near-optimal
hot-potato algorithms for trees
(within logarithmic factors from optimal)
Open problem:
Remove the logarithmic factors
38