Grid Schedulerの調査

[1/24]
Compact Routing
with Minimum Stretch
Kei Takahashi
1
[2/24]
Introduction
In distributed networks, message relaying is
inevitable
All-to-all connections are physically impossible
Nodes can dynamically appear, move, and disappear
Some routing tactics are possible
Broadcast
Random relaying
Routing table
V1
V0
Message
To V3
V3
V2
2
[3/24]
Routing tables
 A routing table knows the next hop to each node
 The information need not be optimal
 Stray messages can be rerouted at relay nodes
 There are trade-off of the table size and efficiency
 A complete routing table occupies large memory
 Efficient routing is not always possible with partial routing tables
V1
V1 : Port 0
V2 : Port 1
V3 : Port 1
V0
Port 1
Message
To V3
Port 0
V3
V2
V0 : Port 0
V1 : Port 1
V3 : Port 3
2
[4/24]
Naïve (complete) routing
 Each node holds the next hop to all nodes
 Always assures optimal routing
 Table size is O(n log(n)) at each node
 n : number of nodes
 size(table) = size(column) * (n-1)
 size(column) = size(nodename) + size(portname)
≤ O(log(n))
log(n)
n-1
V1 : Port 0
V2 : Port 1
V3 : Port 1
V4 : Port 0
V5 : Port 1
V6 : Port 1
…
V0
Port 1
4
[5/24]
The proposed method
Table size ≤ O(n2/3 log4/3 (n))
Better than O(n log(n)) in the naïve method
In most cases, table is smaller than this bound
Maximum stretch ≤ 3
Transfer cost is 3 times more than optimal case
In most cases, the cost is smaller
V1
5
V0
Stretch = 2
6
4
V2
5
[6/24]
Agenda
 Introduction
 Problem definition
 Basic Idea
 Landmarks
 Re-labeling
 Routing
 Details
 Selecting landmarks
 Constructing Routing tables
 Proofs
 Table size
 Max stretch < 3
 Conclusion
6
[7/24]
Problem definition
 Nodes are connected with undirected edges having weight
 Node names can be relabeled as long as length ≤ O(log(n))
 Hostname, IP, processor number
 It is freely changed in programs
 Edges are identified with “port name”
 Port names differ in each node, and cannot be relabeled
 “Port” is something like a UNIX socket
NG
OK
A303
V0
A302
V1
A300
Port 1
V2
Port V2 Port 0
A301
V3
7
[8/24]
Basic idea (1) : landmarks
 Select global “Landmarks”
 They are near to many neighbor nodes
 Each node sets its own landmark as nearest one
 Routing tables have columns for…
 On landmarks : other landmarks (no entry for neighbors)
 On the other nodes : landmarks and neighbors whose shortest path
to their landmark goes through that node
In case of v0, v1 applies to this criteria
label
Landmarks
Near nodes
port
v0
v1
v2
v3
v4
Landmark v5
v6
V3
:
V10
:
-------------V1
:
v7
v9
v8
Landmark
v10 v11
v12 v13
8
[9/24]
Basic idea (2) : re-labeling
Re-label node names
v → (v, lv, elv(v))
lv : Ladmark of v
elv(v) : Next-hop from lv to v
In a natural way, elv(v) is written in the routing table
of lv, but then routing table of lv gets larger
label
Landmarks
Near nodes
port
(V3,
V3, -):
V3
:
(V10,V10,-):
V10
:
-------------(V1,V3,)
:
V1
vv0
0,v3
vv1
1,v3
vv2
2,v3
vv3
3,v3
vv4
4,v3
vv5
5,v3
vv6
6,v3



-

vv7
7,v10



vv9
9,v10


vv10
11,v10
10,v10 vv11

-
vv12
12,v10 vv13
13,v10

vv8
8,v10

9
[10/24]
Basic idea (3) : routing algorism
 The node u routes a message to (v, lv, elv(v)) as follows:
 if u == lv : send to elv(v)
 if v is in u’s table: send according to the table
 otherwise: send to its landmark (lv)’ s next hop
 Let’s see the node (v0, v3, ↑) in the following figure
 (v1,v3,↓) : check the table and send to →
 (v12, v10, ↓) : try to send to (v10,v10,-)
(v3, v3, -):
(v10,v10,-):
-------------(v1,v3,) :
v0,v3
v1,v3
v2,v3

v3,v3
-
v6,v3
v5,v3
v6,v3





v7,v10
v8,v10
v10,v10
-
v11,v10

v9,v10

v12,v10 v13,v10




10
[11/24]
An example of routing
 A message from (v0, v3, ↑) to (v12, v10, ↓)
 (v0, v3, ↑) Checks the entry of landmark (v10,v10,-) : ↓
 (v3, v3, -)
Checks the entry of landmark (v10,v10,-) : →
 (v6, v3, →) Checks the entry of landmark (v10,v10,-) : →
 (v9, v10, ←) Checks the entry of landmark (v10,v10,-) : →
 (v10, v10, -) Checks the label of the destination :↓
 (v13, v10, ↓) Checks the entry of (v12, v10, ↓) : ←
 (v12, v10, ↓) Finally receives the message
 Longer than optimal,
but stretch < 3
Optimal route
v0,v3
v1,v3
v2,v3

v3,v3
-
v6,v3
v5,v3
v6,v3





v7,v10
v8,v10
v10,v10
-
v11,v10

v9,v10

v12,v10 v13,v10




Obtained route
11
[12/24]
高速道路のアナロジー
 Naïve routing : 全ての目的地が全ての案内板に書かれている
 現実的に不可能
 インターチェンジをランドマークにする
 あらゆるインターチェンジまでの経路は全ての案内板に書く
 インターチェンジの案内板には何も書かれていない
 柏キャンパスを「柏インターを北」と覚える
 (柏キャンパス, 柏インター, 北)とre-labeling
 遠くからのルーティング
 「柏インター」を目指して、案内板に沿って進む
 柏インターを北に進むと、柏キャンパスが載った案内板が出現する
 柏の近くからは、柏インターを経由せず到達できる
12
[13/24]
Agenda
 Introduction
 Problem definition
 Basic Idea
 Landmarks
 Re-labeling
 Routing
 Details
 Selecting landmarks
 Constructing Routing tables
 Proofs
 Table size
 Max stretch < 3
 Conclusion
13
[14/24]
Dijkstra algorithm
Gives shortest ways from one node to every node
in an undirected graph
For each reachable node, calculate min-cost
Take one node having min-cost
The adding can be stopped, then the n-nearest
subset is obtained → truncated-Dijkstra method
V0
4
1
V1
1
V2
3
V3
From v2
Costs : {v1 => 1, v3 => 3}
Take v1
Costs : {v0 => 2, v3 => 3}
Take v0
Costs : {v3 => 3}
Take v3
14
[15/24]
Neighbors set
Neighbors set (Bv) : reachable from v
Sort the nodes according to the cost from v
(if some costs are the same, sort by their name label)
Take nα nodes from the nearest one → Bv (v’s ball)
Reversed-neighbors set (Rv) : reachable to v
A set of nodes which have v as their neighbor
Rv ← {y | y ∈ Bv}
V0
1
V1
nα
2
1
V2
Bv
Rv
=3
v0
v0, v1 ,v2
v0, v1,v2
v1
v0, v1, v2
v0, v1, v2, v3
3
v2
v0, v1, v2
v0, v1, v2, v3
v3
v1, v2, v3
v3
V3
15
[16/24]
Requirements for landmarks
A) Only a limited number of nodes can be landmarks
 They should be close to many other nodes
 Adding landmarks makes every routing table bigger
B) If v is on the way from many nodes to their
landmark, v should be their landmark instead
 Otherwise the table on v is too big
Not suitable for a landmark
V3
V10
:
-------------V0
:
V1
:
V2
:
V4
:
V5
:
V6
:
v0
v1
v2
v3
v4
v5
v6
v7
v9
v8
v10 v11
v12 v13
16
[17/24]
A) Landmarks should be famous
Choose “famous” nodes from set of Bvs → D
Easily reached from any v
∃D ⊂ V such that
|D| = O(n1-α log n)
∀v ∈V , D ∩ Bv ≠ φ
An algorithm is known to obtain D
(called Extending dominating set”)
V0
1
V1
2
1
V2
3
V3
nα = 3
V = {v0, v1, v2, v3}
D = {v2}
|D| = 1
Bv0 ∩ D = v2
Bv1 ∩ D = v2
Bv2 ∩ D = v2
Bv3 ∩ D = v2
Bv
Rv
v0
v0, v1 ,v2
v0, v1,v2
v1
v0, v1, v2
v0, v1, v2, v3
v2
v0, v1, v2
v0, v1, v2, v3
v3
v1, v2, v3
v3
17
[18/24]
B) Famous nodes should be landmarks
∃C ⊂ V such that
∀c ∈ C , |Rc| ≥ n(1+α)/2
C is easy to be computed when Rv is given
C always satisfies
n =3
(1+α)/2
|C| ≤ O(n
)
V = {v0, v1, v2, v3}
α
Σ(∀v ∈ V) Rv =
V0
1
V1
2
1
V2
n*nα ≥
3
Σ(∀c ∈ C) Rc
V3
C = {v1, v2}
Rv1 = 4 > 3.6 = n(1+α)/2
Rv2 = 4 > 3.6 = n(1+α)/2
Bv
Rv
v0
v0, v1 ,v2
v0, v1,v2
v1
v0, v1, v2
v0, v1, v2, v3
v2
v0, v1, v2
v0, v1, v2, v3
v3
v1, v2, v3
v3
18
[19/24]
Selecting landmarks
 Two sets are obtained
 ∃D ⊂ V such that
|D| = O(n1-α log n)
∀v ∈V , D ∩ Bv ≠ φ
 ∃C ⊂ V such that
∀c ∈ C , |Rc| ≥ n(1+α)/2
C always satisfies |C| ≤ O(n(1+α)/2)
 Landmark set is derived by simply joining them
L = C ∪ D
 L = O(n1-α log n) + O(n(1+α)/2)
V0
1
V1
2
1
V2
3
V3
Bv
Rv
v0
v0, v1 ,v2
v0, v1,v2
v1
v0, v1, v2
v0, v1, v2, v3
v2
v0, v1, v2
v3
v1, v2, v3
v0, v1, v2, v3
v3 Landmarks
19
[20/24]
Constructing routing tables
// Calculate paths to nα-shortest nodes from v
For each v ∈ V, perform truncated-Dijkstra(nα)
// Here, less than nα nodes are nearer than u from v
For each u reached from v:
// If ↓ is true, the best route is given by using that landmark
If no landmark is on the path from v to u:
store(v, eu(v)) at u
// Calculate shortest paths from landmarks to every node
For each l ∈ L, perform full-Dijkstra(nα)
// v appeared
For each v ∈ V
Store (l, eu(l)) at u
20
[21/24]
Proof : table size = O(n2/3 log4/3 (n))
 A set of landmarks (L) is O(n1-α log n + n(1+α)/2)
 Table size = size(label of node) * size(columns)
 Size(label of node) = O(log(n))
 Size(columns) ≤ |L| + nα = O(n1-α log n + n(1+α)/2 + nα)
∴ Table size = O((n1-α log n + n(1+α)/2 + nα) log n)
 Search α which minimizes table size, and get
α = 1/3 + (2 log log n) / (3 log n)
Table size = O(n2/3 log4/3 (n))
n
nα
# landmarks Table size
Naïve method (α=1)
1000
36
190
1315
6907
10000
94
972
8961
92103
100000
236
4864
56007
1151292
1000000
575
23995
331504
13815510
21
[22/24]
Proof : max stretch ≤ 3
 Theorem : route(u, v) ≤ 3 * d(u, v)
 route(u,v) : the cost of the route from u to v given by this algorism
 d(u,v) : the smallest cost from u to v
 L : set of landmarks
 X : points on the shortest path among u and v
 If d(u,v) < d(lv, v):
 d(x, v) < d(u, v) < d(lv, v)
 lv ∈ Bv, so (u ∈ Bv) and (v ∈ Ru) and (∀x ∈ X, x ∈ Bv, x ∈ Ru)
 X∩L=φ
 Otherwise v should take that node as lv (⊥)
 Then, u should have (v, eu(v)) on its routing table, so as ∀x
 The message will not pass lv (⊥)
(As a result, route(u, v) is always optimal in this case)
u
lv
x
v
22
[23/24]
Proof : max stretch ≤ 3 (Cont.)
 Otherwise : d(lv,v) ≤ d(u,v)
 Column (v, eu(v)) is not on u’s table
Otherwise (v ∈ Ru) so any x’s table has a column(v, ex(v))
The message will not pass lv (⊥)
 Y : nodes on the shortest path among u and lv
 If any y does not have a column (v, ey(v)) on its table :
route (u, v) = d(u, lv) + d(lv, v)
 Every y refers the column for lv, which gives the shortest path to lv
d(u,lv) ≤ d(u, v) + d(lv, v) (triangle equation)
d(u,lv) ≤ 2 * d(u, v), so route(u,v) ≤ 2 * d(u,v) + d(u,v) ≤ 3 * d(u,v)
 Otherwise : (skip)
(It can be proved that route(u,v) ≤ d(u, lv) + d(lv, v) )
u
y
x
lv
v
23
[24/24]
Conclusion
 A routing strategy was given which assures
 Small table size : O(n2/3 log4/3 (n))
 Max stretch is less than 3
 It consists of 4 parts:
 Selecting landmarks
 Re-labeling nodes
 Create routing tables
 Routing algorism
 For practical situations, alternative methods are proposed.
They offer smaller table size and better routing on average
24

Download Report