Document

5. Deadlock-free Packet
Switching
hayami
2015/10/1
1
Deadlockはなぜ発生するのか
各nodeのバッファの容量は有限である
転送先のバッファがFullだと転送できない
→ Store-and-forward deadlock
s
1
t
×
u
v
B
2015/10/1
Full
2
目的
Deadlock-freeなcontrollerの考案
2015/10/1
3
発表の手順
準備
Structured Solutions
Unstructured Solutions
Misc.
2015/10/1
4
準備
 諸概念の定義
2015/10/1
5
前提
ネットワークはグラフ G
G=(V,E)
 V , E  で表現
各ノードは B 個のバッファを持つ
転送経路はルーティングアルゴリズムが決定
2015/10/1
6
パケットの操作
「生成」 → 「転送」 → 「消費」
例 source : s
destination : v
path P  s, t , u, v
s
t
u
v
1
B
2015/10/1
7
Controllerとは?
 パケット操作のタイミングを決定するアル
ゴリズムで、以下の制約を満たすもの
1. パケットの消費は常に許可
2. sourceノードの全バッファが空の場合、パ
ケットの生成は常に許可
3. パケットの転送はLocalな情報をもとに許可
2015/10/1
8
Controllerとは? (formal)
controller: con  Genu , Foru 
(cu , p)  Genuの時のみuでのパケット
pの生成を許可
(cu , p)  Foruの時のみuへのパケット
pの転送を許可
Genu , Foru  Zu 
cu : stateof u
Zu : set of cu
2015/10/1
9
Deadlock
 Packet p がDeadlock

p の消費につながる操作が存在しない
 Controller conがDeadlock-free
 conのもとでinitial configurationからdeadlock
configurationに到達不能
2015/10/1
10
Structured Solutions
Buffer Graph
Buffer Graph Controller
2015/10/1
11
観察
Deadlockの原因はcyclic wait
→acyclicにしてやればよい!
2015/10/1
12
Buffer Graphの定義
buffer graph: BG 


, BE
1. BGはacyclic
u,vのバッファとする
2. b, cはそれぞれノード
もしbc  BEならu  vまたはuv  E
が
3. GのどのパスP  についても、イメージ
Pであるような
BGのパスが存在する
: set of B, BE : 
2015/10/1
13
Buffer graph controller
bgcBG
bgcBG  Genu , Foru 
s.t.
Genu  (cu , p) fb( p)  e m ptyin cu 
Foru  (cu , p ) nb( p, b)  e m ptyin cu 
※ fb( p) : パケット
pが生成されて最初に入るバッファ
nb( p, b) : パケット
pがbの次に転送されるバッ
ファ
2015/10/1
14
bgc はdeadlock-free
 証明はbuffer classに関する帰納法
→ 別紙参照
2015/10/1
15
Buffer Graphの構築
G
BG
Gから構築される
BG は一意ではない
BG をつくるとBB を小さくできる
よい BG
BGd destination scheme (B=N
B  N)
BGｄ:
B  D)
BGh:
BGh hops-so-far scheme (B=D
( B  D)
Bga
BGa: acyclic orientation cover scheme B<D
bgc を適用すればOK.
構築した BG
BG に bgc
2015/10/1
16
Destination scheme
各destination別にバッファを確保
BN
fb( p )  bu [v]
nb( p, b)  bw [v]
2015/10/1
17
Hops-so-far scheme
sourceからのホップ数別にバッファを用意
最大ホップ数+1個のバッファが必要
Minimum-hop routingなら
B  D 1
fb( p)  bu [0]
nb( p, bu [i])  bw [i  1]
2015/10/1
18
BGd とBGh の例
BGd
u
G
v
w
N 3
D 1
2015/10/1
BGh
19
Acyclic Orientation Cover

G  (V , E ) のacyclic orientaion G’=(V’,E’)
G=(V,E)
  (V , E)
G

GはDAG, V   V , ( Eの無向化)  E
G のacyclic orientation cover G1…GB
G1 ,, GB
G
B
P   Pi
for P 
i 1
where Pi  Giのpat h
2015/10/1
20
AOC scheme
GのAOCのサイズだけバッファを用意
Hops-so-farよりも有利 ( B  D)
fb( p )  bu [1]
 bw [i ]
if uw  Ei
nb( p, bu [i ])  
bw [i  1] if wu  Ei
2015/10/1
21
BG
の例
Bgaの例
a
G
v
AOC  G1 , G2
u
u
w
v
w
v
u
w
BGa
2015/10/1
22
必要なバッファ数B の比較
BG に依存
必要なバッファ数 B は BG
BGa  BGh  BGd
2015/10/1
23
Unstructured Solutions
Forward-count Controller
Forward-state Controller
2015/10/1
24
Unstructured controllerの特徴
Buffer graphを作らない
ホップ数や空きバッファ数を利用
2015/10/1
25
Forward-count controller
 残りホップ数より空きバッファが多ければ転送
FC  Foru 
s.t.
Foru  (cu , p) s p  f u in cu


s p : pのdestinationまでの残りホップ数(0  s p  k )
f u : uの空きバッファ数 (0  f u  B)
2015/10/1
26
FCはdeadlock-free
証明は背理法
→ 別紙参照
2015/10/1
27
FCは改良の余地あり
state vector の利用
state vectorの定義
uのstate vector: j0 ,  , jk
where js  ノード
u内でs p  sを満たすパケット
pの数
例
u
B5
k  4 Sp=1
uのstate vector  0,2,0,1,0
3
1
2015/10/1
28
Forward-state controller
 state vector を利用
fu よりも多い
 state vector の情報量は fu
FS  Foru 
s.t.
k



Foru  (cu , p) i,0  i  s p : i  B   js in cu 
s i


2015/10/1
29
FSはdeadlock-free
証明は背理法(c.f. FCの証明)
2015/10/1
30
Controllerの比較
 FC
FC よりも FS
FS の方が自由度が高い
補題 : FC で許される操作は
FS でも許される
証明 pをuに転送するのをFCが許可したとする。こ
のとき、
k


s p  f u   B   js 
s 0


が成り立つ。すると、
i  s p なるiについて、
k
k
s 0
s i
i  s p  B   js  B   js
が成り立つ。これは
FS においても同じ操作が
許される
ことをあらわしている
。
2015/10/1
31
Misc.
Topological Changes
その他のDeadlocks
Livelock
2015/10/1
32
Topological Changes
destはつかえる
ホップ数を利用するhsf,FC,FSは無理
上位のプロトコルと協力
2015/10/1
33
その他のDeadlocks
Progeny
Copy-release
Pacing
Reassembly
2015/10/1
34
Livelock
 コントローラ con
con のもとでパケット p が消費され
ないような無限に適用可能な操作列が存在
→
p
はLivelocked
 適切なfairnessを仮定するとbgc
bgc はLivelock-free
 FS
FS をLivelock-freeに改善することは可能
2015/10/1
35
2015/10/1
36

Download Report