ネットワークフローとその代表的な問題

Size: px

Start display at page:

Download "ネットワークフローとその代表的な問題"

しなつはにうだ
5 years ago
Views:

1 ネットワークフローとその代表的な問題金子紘也 ( 日本電気株式会社情報ナレッジ研 ) Internet Week 2013 S8 SDN 時代を生き抜く為のグラフ理論とネットワークのアルゴリズム入門

2 ネットワークフローとは? フロー最適化最大フロー線形計画法による解法多品種フロー問題 Max-min fairness まとめ

3 ネットワークフローとは? フロー最適化最大フロー線形計画法による解法多品種フロー問題 Max-min fairness まとめ

4 ネットワークフローとは? グラフ上の流れを扱う分野グラフ構造にエッジ容量の概念を導入フローは容量を消費する定義 :flowはedgeを実数に写像する関数 B- >C : 3 A 3/7 3/7 B 7/7 C 7/7 D 7/7 4

5 ネットワークフローの例 1 通信ネットワーク交通システム A B C D 5

6 ネットワークフローの例 2 電気回路 6

7 ネットワークフローとは? フロー最適化最大フロー線形計画法による解法多品種フロー問題 Max-min fairness まとめ

8 そもそも最適化とは? B から C に行きたい黄色は最適な経路? -> 確かに最短ではあるけど... 0/14 A 0/10 B 0/4 C D 0/15 0/18 8

9 そもそも最適化とは? BからCに行きたい黄色は最適な経路? -> 確かに最短ではあるけど... 何が最適なのかは目的次第ここからは流量最大化にフォーカス! B 0/14 A 0/4 0/10 C D 0/15 0/18 9

10 最大フロー問題最大どれだけ流せるのか? を知りたい問 :B から C までの流量を最大化せよ 0/14 A 0/10 B 0/4 C D 0/15 0/18 10

11 最大フロー問題最大どれだけ流せるのか? を知りたい問 :BからCまでの流量を最大化せよ解 :28 B->A->C :10 B->A->D->C:4 B->D->C :14 B 0/14 A 0/4 0/10 C D 0/15 0/18 11

12 Ford-Fulkerson 法最大フローを求めるアルゴリズムフロー増加法と呼ばれる基本的な流れ 1. 残余 NWから増加路を探索 2. 増加路にフローを流し, 残余 NW 作成増加路が発見できなくなったら終了増加路は幅優先探索などで発見 12

13 Ford-Fulkerson 法残余 NWとは? - > 現時点で利用可能な容量を示したNW 利用済みの後進辺も記述初期状態 14 A 10 B C D 18 13

14 Ford-Fulkerson 法 1.B- >A- >C のパスに流量を 10 追加 14- >4 A 10- >0 B C D

15 Ford-Fulkerson 法 2.B- >D- >C のパスに流量を 15 追加 4 A 0 B C 0 D 3 15

16 Ford-Fulkerson 法 3.B- >A- >D- >C のパスに流量を 3 追加 1 A 0 B C 0 D 0 16

17 Ford-Fulkerson 法 4.B- >Cの間に増加路なし, 終了解 :28 B- >A- >C :10 B- >A- >D- >C:4 B- >D- >C :14 B 1 A C D 0 17

18 Ford-Fulkerson 法後進辺を利用しない場合のコーナーケース一回目の増加路に B- >A- >D- >C を選んだ場合 1 A 1 B 1 C D

19 Ford-Fulkerson 法後進辺を利用しない場合のコーナーケース一回目の増加路にB- >A- >D- >Cを選んだ場合 => 増加道なし ( に見える ) 最大流 1? 0 A 1 B 0 C D

20 Ford-Fulkerson 法正しい最大流フロー B- >A- >C B- >D- >C の計 2 0 A 0 B 1 C D

21 Ford-Fulkerson 法正しい最大流フロー B- >A- >C B- >D- >C の計 2 0 A 0 B 1 C 増加路を選ぶ順番によっては D 最適解に辿りつけない??

22 Ford-Fulkerson 法後進辺の役割 1. 最初に B- >A- >D- >C を選択してしまった場合 0 A 1 B C 1 D 0 22

23 Ford-Fulkerson 法後進辺の役割 2. 後進辺を含めると増加路が存在する! 0 A 1 B C 1 D 0 23

24 Ford-Fulkerson 法後進辺の役割 3. 後進路を辿ってフローを増加 - > 最大フロー 0 A 0 B C 0 D 0 24

25 Ford-Fulkerson 法後進辺の役割 3. 後進路を辿ってフローを増加 - > 最大フロー 0 A 0 B C 1 1 局所最適に陥る要因となったフロー 0 D 0 を押し戻すような動作 25

26 ネットワークフローとは? フロー最適化最大フロー線形計画法による解法多品種フロー問題 Max-min fairness まとめ

27 線形計画法とはここまで例はグラフの構造を利用していた派生問題も全てアルゴリズムを考える? disjoint path,minimum cost,etc... Linear Programming(LP) 制約条件群 ( 一次式 ) を満たす目的関数 ( 一次式 ) を最大 / 最小化する変数を探す手法! 27

28 線形計画法例生産計画利益を最大化したい! 定式化すると制約 1. x + 2y <= x <= x >= 0, y >= 0 目的関数 maximize 2x+y 製品 X 製品 Y 使える量原料 A 原料 B 利益 2 1 AとBを何個ずつ作ろう? 28

29 線形計画法例生産計画利益を最大化したい! 定式化すると制約 1. x + 2y <= x <= x >= 0, y >= 0 目的関数 maximize 2x+y 製品 X 製品 Y 使える量原料 A 原料 B 利益 2 1 A と B を何個ずつ作ろう? この形に落とし込めば solver で解ける! 29

30 線形計画法例制約 1. x + 2y <= x <= x >= 0, y >= 0 目的関数 maximize 2x+y 制約 3 制約 1 実行可能領域最適解! 制約 2 制約 3 30 h9p://

31 線形計画法例制約 1. x + 2y <= x <= x >= 0, y >= 0 目的関数 maximize 2x+y 制約 3 制約 1 実行可能領域最適解! 制約 2 制約 3 ネットワークフロー問題における目的関数 / 制約関数とは?? 31 h9p://

32 ネットワークフロー問題の定式化 B から C までの最大流問題 - 最大化したいもの :B->C のフロー流量 - 制約 : ネットワークフローであること 0/14 A 0/10 B 0/4 C D 0/15 0/18 32

33 ネットワークフロー問題の定式化目的関数 SourceNodeにおける出力フロー最大制約条件 1. エッジ上のフローはエッジの容量以下 2. 入出力フロー量の一致 33

34 ネットワークフロー問題の定式化目的関数 SourceNodeにおける出力フロー最大制約条件 1. エッジ上のフローはエッジの容量以下 2. 入出力フロー量の一致 34

35 ネットワークフロー問題の定式化目的関数 :SourceNode において出次エッジのフロー量最大 X+Y を大きくしたい! A B- >C : X 0/7 0/7 S B 0/7 B- >D : Y C 35

36 ネットワークフロー問題の定式化目的関数 x e x e e δ + ( v) e δ ( v) Source に入るフロー計 x e δ + (v) edge e 上のフロー量 v から出るエッジ e の集合この差が Source からの直接的な流出量 S X+Y を大きくしたい! B Source から出るフロー計 A B- >C : X 0/7 0/7 0/7 B- >D : Y D C 36

37 ネットワークフロー問題の定式化目的関数 SourceNodeにおける出力フロー最大制約条件 1. エッジ上のフローはエッジの容量以下 2. 入出力フロー量の一致 37

38 ネットワークフロー問題の定式化制約 1. 全てのエッジ上についてその上を流れるフローの合計ははエッジの容量を超えない容量制約則と呼ぶ A B- >C : X 0/7 0/7 S B X+Y < 7 0/7 B- >D : Y C 38 D

39 ネットワークフロー問題の定式化容量制約 x e c e edge e 上のフロー量 edge e の capacity 0 x e c e エッジを流れるフローが容量を超えないと言っているだけ A B- >C : X 0/7 0/7 S B X+Y < 7 0/7 B- >D : Y C 39 D

40 ネットワークフロー問題の定式化目的関数 SourceNodeにおける出力フロー最大制約条件 1. エッジ上のフローはエッジの容量以下 2. 入出力フロー量の一致 40

41 ネットワークフロー問題の定式化制約 2.S-Dでは無いノードについて入出力フロー量が一致するフロー保存則と呼ぶ入出力フロー量が一致 A Xin+Yin- Xout- Yout = 0 B- >C : X S 入出力フロー量が一致 D B B- >D : Y C 41

42 ネットワークフロー問題の定式化フロー保存則 e δ + ( v) x e x e e δ ( v) = 0 x e δ + (v) δ (v) 中継ノードについて入力 / 出力の差分が 0 edge e 上のフロー量 v から出るエッジ e の集合 v に入るエッジ e の集合 B- >C : X 入出力フロー量が一致 A Xin+Yin- Xout- Yout = 0 S 入出力フロー量が一致 D B B- >D : Y C 42

43 ネットワークフロー問題の定式化まとめ目的関数制約条件 1. 0 x e c e 2. x e x = 0 e δ + ( v) x e x e e δ + ( v) e δ ( v) e e δ ( v) Source に入るフロー計 Source から出るフロー計エッジを流れるフローが容量を超えないと言っているだけ目的関数と形同じ S/D ノード以外はフローを中継するのみこの差が Source からの直接的な流出量 43

44 Glpk で動かしてみよう GNU Linear Programming Kit 線形計画法をとくためのSolver Kit 目的関数 Maximize : xba + xbd 0/14 A 0/10 B 0/4 C 0/15 D 0/18 44

45 Glpk で動かしてみよう容量制約 0 x e c e xba <= 10, xbd <= 10, xad <= 10, xac<=10, xdc <= 10 0/14 A 0/10 xba >= 0, xbd >= 0, B 0/4 C xad >= 0, xac >= 0, xdc >= 0 0/15 D 0/18 45

46 Glpk で動かしてみようフロー保存則 e δ + ( v) x e x e e δ ( v) = 0 xdc xbd xad = 0 xad + xac xba = 0 0/14 A 0/10 B 0/4 C 0/15 D 0/18 46

47 ObjecFve: TRAFFIC = 28 (MAXimum) 実行例 No. Column name St AcFvity Lower bound Upper bound Marginal k1 B 28 2 uba B ubd NU < eps 4 uad B uac NU udc NU xba B xbd B A 9 xad B xac B xdc B B 10 C 15 D 18 47

48 ネットワークフローとは? フロー最適化最大フロー線形計画法による解法多品種フロー問題 Max-min fairness まとめ

49 多品種フロー品種 (commodity) とは発着地のペアの事さきほど解いた多品種問題は 1 品種品種 (B->C) 品種 1 49

50 多品種フロー品種とは発地, 着地のペアの事さきほど解いた多品種問題は1 品種品種 (B->C) 複数の品種に拡張 (multi commodity) 例えば (B->C) と (A->C) の 2 品種品種 1 品種 2 50

51 多品種フローの定式化今回目指す最適性複数品種のフローの合計を最大化目的関数 1 品種 :Sourceにおける出力フロー最大多品種 :Source 群における出力フロー合計最大品種 1 品種 2 51

52 多品種フロー問題の定式化目的関数 Source 群における出力フロー合計最大制約条件 ( 全ての品種の合計について ) 1. エッジ上のフローはエッジの容量以下 2. 入出力フロー量の一致品種 1 品種 2 52

53 多品種フロー問題の定式化目的関数 (1 品種 ) 目的関数 (k 品種 ) i=1 x a x a e δ + ( v) e δ ( v) k ( x a x a ) e δ+(v) e δ (v) 1 品種の時と同じ品種 1 K 品種分の合計を最大に品種 2 53

54 多品種フロー問題の定式化容量制約 (1 品種 ) 容量制約 (k 品種 ) k i x e c e i=1 0 x e c e x e i c e K 品種分の計がエッジの容量以下品種 1 品種 2 54

55 多品種フロー問題の定式化フロー保存制約 (1 品種 ) e δ + ( v) フロー保存制約 (k 品種 ) e δ + ( v) x e x e e δ ( v) i x e x i e e δ ( v) = 0 = 0 i x e edge e 上の品種 k のフロー量品種 1 各品種ごと各中継ノードごとにフロー保存則が成り立つ品種 2 55

56 多品種フロー, 結果得られた解目的関数 :28 各品種の流量品種 1:15 品種 2:13 品種 1 品種 2 56

57 多品種フロー, 結果得られた解目的関数 :28 各品種の流量品種 1:15 品種 2:13 これは最適な流し方? 品種 1 品種 2 57

58 ネットワークフローとは? フロー最適化最大フロー線形計画法による解法多品種フロー問題 Max-min fairness まとめ

59 最適な割り当ての問題最適にネットワークを使いきれる条件 1 品種の場合品種 1:28 2 品種の場合品種 1:15, 品種 2:13 要求 Aさん品種 1のパスに20 流したい Bさん品種 2のパスに13 流したいどうする?? 59

13 100% グラフ全体最大流割り当て割り当て / 要求利用率 28 28 100% 品種 1

60 回答 1 最適な割り当ての問題 A さん品種 1 そんなに流せないので 15 でネットワーク全体の利用率を再優先した考え方要求割り当て A さん % B さん % グラフ全体最大流割り当て割り当て / 要求利用率 % 品種 % 品種 % 品種 1 単独 % A さん流 B さん流 60

100% B さん 13 8 61% 最大流割り当て利用率グラフ全体 28 28 100%

61 最適な割り当ての問題回答 2 Aさんの方が偉いからAさん優先にしよう要求に完全に優先度を付け順に割当てる作戦要求割り当て割り当て / 要求 A さん % B さん % 最大流割り当て利用率グラフ全体 % 品種 % 品種 % 品種 1 単独 % A さん流 B さん流 61

62 Fairness フェアな割り当てとはなにか? 1. 最低でもXの帯域を全員が確保できる 2. 均一な割り当て / 要求レートを目指す 3. ネットワークの利用率をとにかく上げる公平性の一つの考え方として Max-min Fairnessを紹介 62

63 Fairness Policy A-B-C と直列に繋がれたトポロジ e1 は 2, e2 は 4 の容量を持つ Flow 群 :A->B,B->C,A->C 最大フローを目的とする場合の解 flow1:0,flow2:2,flow3:4 の割り当てが最適ネットワーク全体で 6 の流量を確保 -> 最大フロー A e1(2) B e2(4) C flow2 flow3 flow1 flow 割り当て Sum 6 63

64 Fairness Policy A-B-C と直列に繋がれたトポロジ e1 は 2, e2 は 4 の容量を持つ Flow 群 :A->B,B->C,A->C 最大フローを目的とする場合の解 flow1:0,flow2:2,flow3:4 の割り当てが最適ネットワーク全体で 6 の流量を確保 -> 最大フロー flow1 は 0 で良いのか? A e1(2) B e2(4) C flow2 flow3 flow1 flow 割り当て Sum 6 64

65 Max-min Fairness Policy Maximize the minimum (to allocate) 割り当て可能な帯域が最も小さいものを優先するアルゴリズム 1. 全ての flow を同一ペースで増加させた場合に最初に飽和するリンク ( ボトルネックリンクと呼ぶ ) を特定する 2. 全ての flow に対してボトルネックリンクが発生する流量分割り当てを行い NW からボトルネックリンクを削除 3. 増加することのできる flow が存在する場合は 1 に戻る 65

66 Max-min Fairness Policy 1. 全てのflowを同一ペースで増加させた場合に最初に飽和するリンク ( ボトルネックリンクと呼ぶ ) を特定する下のトポロジの場合 flow1=flow2=flow3= 1 の時に e1 が飽和 e1がボトルネックリンクボトルネックリンクが最初に発生する流量は1 A e1(2) B e2(4) C flow2 e1= 1+1 e2= 1+1 flow3 flow1 flow 割り当て Sum 0 66

67 Max-min Fairness Policy 2. 全てのflowに対してボトルネックリンクが発生する流量分割り当てを行い NWからボトルネックリンクを削除下のトポロジの場合 flow1=flow2=flow3= に 1 を割り当てボトルネックリンク e1 を削除まだ flow3 は増やせるので 1 に戻る A e1(2) B e2(4) C flow2 e1= 1+1 e2= 1+1 flow3 flow1 flow 割り当て Sum 3 67

68 Max-min Fairness Policy 1. 全てのflowを同一ペースで増加させた場合に最初に飽和するリンク ( ボトルネックリンクと呼ぶ ) を特定する下のトポロジの場合 flow3=2 の時に e2 が飽和 e2 がボトルネックリンクボトルネックリンクが最初に発生する流量は 2 A e1(2) B e2(4) C flow2 e1= 1+1 e2= 2+2 flow3 flow1 flow 割り当て Sum 3 68

69 Max-min Fairness Policy 2. 全てのflowに対してボトルネックリンクが発生する流量分割り当てを行い NWからボトルネックリンクを削除下のトポロジの場合 flow3= に 2 を割り当てボトルネックリンク e2 を削除増加可能な flow が存在しないので終了 A e1(2) B e2(4) C flow2 e1= 1+1 e2= 1+1 flow3 flow1 flow 割り当て Sum 5 69

70 Fairness Policy Max- min fairness 合計帯域は減少したが割り当ては公平に Fairness Policy はユースケース次第 flow 割り当て 1 0 最大流 flow 割り当て 1 1 Max- min flow Sum Sum 5 A e1(2) B e2(4) C flow2 flow3 70

71 ネットワークフローとは? フロー最適化最大フロー線形計画法による解法多品種フロー問題 Max-min fairness まとめ

72 まとめネットワークフロー問題容量付きエッジ, 流れを扱う組み合わせ最適化線形計画法に落としこむことができる最大フロー問題 Ford-Fulkerson 法線形計画法 Fairness 複数のフロー間でどう容量を分け合うか? Max-min fairness SDN 時代の今こそ動かせる! 72

Microsoft PowerPoint - mp13-07.pptx

Microsoft PowerPoint - mp13-07.pptx 数理計画法 ( 数理最適化 ) 第 7 回ネットワーク最適化最大流問題と増加路アルゴリズム担当 : 塩浦昭義 ( 情報科学研究科准教授 ) hiour@di.i.ohoku.c.jp ネットワーク最適化問題 ( 無向, 有向 ) グラフ頂点 (verex, 接点, 点 ) が枝 (edge, 辺, 線 ) で結ばれたものネットワーク頂点や枝に数値データ ( 距離, コストなど ) が付加されたもの