自律分散協調システム論

自律分散協調システム論
第9回「経路制御と輻輳制御」
中村修
[email protected]
経路制御
経路制御って？
• 鉄道モデルでいうと、路線図の管理
– 「○○駅に行くには、この線にのせればいいのね」
– 「××駅は載ってないから行き方が分かんない」
• インターネットでは、各コンピュータの持つ
経路表の管理
– 鉄道だと(目的駅、次の乗換駅、次に使う路線)
• 藤沢駅にて、(新宿、品川、東海道線)
復習
経路表
復習
• ルータ、ホストが保持する経路の一覧表
• 経路表(FIB: Forwarding Information Base)
– 経路表の要素
• プレフィクス
• next hop (次に転送するルータ)
• 出力インタフェース
• プレフィックス
– ネットワークアドレス
– サブネットマスク
– 例: 203.178.143.0/24
– 複数のサブネットを集約して一つのプレフィックスとして表現する
場合もある
経路表とIP Forwarding
prefix
10.0.0.0/24
172.16.0.0/24
ルータA
Next-hop
ルータA
ルータC
ルータC
ルータB
10.0.0.0/24
10.0.0.0/24
復習
172.16.0.0/24
192.168.0.0/24
172.16.0.0/24
静的経路制御 vs. 動的経路制御
• 静的経路制御
• メリット
– ポリシとオペレーションのエンジ
ニアリングとの一致が保証
– 経路情報に伴うトラフィックは発
生しない
– 経路が安定する
– 全てのルータで利用可能
• デメリット
– 管理者が経路表を全て
設定する必要がある
– 障害発生時に代替経路に
自動的に切り替えられない
• 管理者が設定を変更するまでそ
のまま
• 動的経路制御
• メリット
– 複雑なトポロジでも、最適な経路
表を短時間で設定
– 障害発生時に代替経路を選択
• デメリット
– 経路制御メッセージが、ネット
ワーク上に流れる
– 意図した通りに動作しない場合
がある
– 経路が安定しない時がある
• 設定ミス
• 遠隔のネットワーク内のトラブル
が伝播し、ネットワーク全体の
ルータの経路表が頻繁に書き変
わる
静的経路制御の課題と動的経路制御の必要性
• 静的経路制御の課題
• 耐障害性
– 障害発生時に、手動で障害箇所を迂回するよう経路設
定を変更した場合、復旧に時間もかかる
• 設定コスト
– 大規模なネットワークでは、膨大な経路を手動で設定
するのは大変

• ルータ間で経路情報を交換し、自動的に経路表を生成
– 動的経路制御を用いたネットワークで、全てのルータの経路表
が安定することを収束(コンバージェンス)という
経路制御プロトコル
距離ベクトル型
リンクステート型
IGPとEGP
• 経路制御プロトコルにはIGPとEGPがある
• IGP(Interior Gateway Protocol)
– AS内で利用する経路制御プロトコル
• いわば、組織のネットワーク内で利用する経路制御プロトコル
• ASの管理者が任意の経路制御プロトコルを選択
– RIP, OSPF, IS-IS, BGP4(iBGP) …
• EGP(Exterior Gateway Protocol)
– AS間を接続するための経路制御プロトコル
• いわば、the Internetを実現する経路制御プロトコル
• AS間で共通のルーティングプロトコル
– AS間の接続ポリシを経路制御に反映
– BGP4*1 (eBGP)
経路制御プロトコル (Routing Protocol)
• 経路表の更新
– ネットワークが変更されたらどうするか？
– 例：新しいネットワークが追加されたら？
• 全てのノードの経路表を更新する必要がある
– ルータ間で経路情報を交換し、経路表を作成
prefix
Next-hop
prefix
Next-hop
prefix
Next-hop
192.168.0.0/24
ルータB
10.0.0.0/24
ルータA
10.0.0.0/24
ルータB
172.16.0.0/24
ルータB
172.16.0.0/24
ルータC
192.168.0.0/24
ルータB
172.16.1.0/24
ルータB
ルータA
10.0.0.0/24
172.16.1.0/24
ルータC
ルータB
192.168.0.0/24
ルータC
172.16.0.0/24
172.16.1.0/24
距離ベクトル型アルゴリズムの特徴
• 代表的なプロトコル: RIPv1, RIPv2
• プロトコルの動作が簡単
– プログラムも簡単
– 小型ルータ/エントリクラスのL3スイッチでも搭載
• 経路の収束にかかる時間が長い
– ただし、小規模なネットワークなら高速
– 収束
• 全てのルータが正しい経路表が作成し、それ以上更新しなくなるまでの時間
• ループが発生する可能性
– 確率は低いが、完全にループフリーではない
• スケーラビリティ
– 大規模なネットワークほど、交換する経路情報が増す
– 国際線が9.6Kbpsだった時代、RIPでフルルートを…
距離ベクトル型のアルゴリズム
• 各ルータは、経路情報を隣接ルータに広告
– 自分が到達可能なプレフィックス
– そこへの距離(例えばホップ数)
• 経路情報を受け取った場合の処理
– 自分が知らない経路なら、採用
– 自分が知っているプレフィックスより、短いプレフィックス
の経路なら採用
• Longest match
• 新しい経路情報を隣接ルータに広告
距離ベクトル型経路制御プロトコルの動作(1/4)
• 自分が持つ経路情報を隣接ルータに広告
Net A
133.27.4.0/24
ルータＣ
ルータA
133.27.4.0/24まで
1 hop
ルータＢ
Net B
133.27.5.0/24
ルータD
距離ベクトル型経路制御プロトコルの動作(2/4)
• 受け取った経路情報を、更に隣接ルータに伝達
Net A
133.27.4.0/24
ルータA
133.27.4.0/24まで
ルータＣ
2 hop
133.27.4.0/24まで
1 hop
Net B
133.27.5.0/24
ルータＢ
ルータD
133.27.4.0/24まで
2 hop
距離ベクトル型経路制御プロトコルの動作(3/4)
• 受け取った経路情報が、自分が持つ経路情報より
ホップ数が多い場合は破棄
Net A
133.27.4.0/24
ルータA
133.27.4.0/24まで
ルータＣ
2 hop
133.27.4.0/24まで
3 hop
133.27.4.0/24まで
1 hop
Net B
133.27.5.0/24
ルータＢ
ルータD
133.27.4.0/24まで
2 hop
距離ベクトル型経路制御プロトコルの動作(4/4)
• 最短の経路でトラフィックを転送
Net A
133.27.4.0/24
ルータＣ
ルータA
133.27.4.0/24まで
1 hop
Net B
133.27.5.0/24
ルータＢ
ルータD
133.27.4.0/24まで
2 hop
リンク状態型アルゴリズムの特徴
• 代表的リンク状態型経路制御プロトコル
– OSPF (Open Shortest Path First)
– IS-IS (Integrated System to Integrated System)
• 大規模なネットワークに適している
– Loop Free
– いったん経路が収束した後は、経路制御メッセージに
よるトラフィック量が少ない
– ネットワークの規模が大きくなっても、恒常的に流れる経路制御
メッセージの増加量は少ない
• 距離ベクトル型に比べ、処理が複雑
– 安価なルータ,L3スイッチには搭載されていない
• 大規模なネットワークでも経路の収束が早い
リンク状態型のアルゴリズム
• 各ルータのリンク(インターフェース)情報をネットワーク全
体で共有
– 例: R1はR2と繋がっている
– 例: R1には133.27.4.0/24が繋がっている
• ネットワーク全体にflooding
– ネットワーク内のすべてのルータにリンク情報が伝わる
– 全ルータは同一のリンク情報データベースを持つ
– 状態に変化があったリンクの情報だけを伝える
• 各ルータが、リンク情報からトポロジを再構成
– リンク情報を基に、自分がルート(根)となるツリーを作成
– ツリーにすれば、ある宛先までの最短経路がわかる
– 全ルータが同一の計算方法
リンク状態型経路制御プロトコルの動作
• 各リンクにコストを設定
– 例：ルータA からルータB までのリンクコストは30
• 各ルータは、自分が持つリンクのUP/DOWNを監視
Net A
133.27.4.0/24
ルータＣ
ルータA
30
30
30
30
ルータＢ
30
30
Net B
133.27.5.0/24
100
ルータD
100
リンク状態のデータベース
• ルータは、自分が持つリンク情報をflooding
• 各ルータが、全ルータのリンク状態を保持
ルータA
To: B,
Cost: 30
ルータＢ
To: A ,
Cost: 30
To: B ,
To: D,
Cost: 30 Cost: 100
ルータC
To: B,
Cost: 30
To: D,
Cost: 30
ルータD
To: B ,
Cost: 500
To: C ,
Cost: 30
ツリーの作成
• コストが小さい順に組み合わせ、ツリーを作成
• 最短の経路が判明
ルータB
Cost 30
Cost 30
ルータA
Cost 100
(使わない)
ルータC
Cost 60
Net A
133.27.4.0/24
ルータD
Net B
133.27.4.0/24
IGPの比較
特徴
スケーラビリティ
計算量
収束時間
アルゴリズム
Neighbor生存確認
メトリック
RIP
OSPF
IS-IS
EIGRP
•ほとんどのL3機
器でサポート
•実装が容易でシ
ンプル
•小規模ネット
ワークで利用
•やや高価な機器
でサポート
•IPに最適化、IAB
推奨
•中・大規模ネット
ワークで利用
•もともとはOSI
CLNP用に設計
•一部ルータでのみ
サポート
•国内ではあまり利
用されない
•Cisco独自規格
•ループフリー、高
速な収束
△
○
○
○
少ない
多い
(特にDR/BDR)
多い
やや多い
低速
高速
高速
高速
距離ベクトル型
リンク状態型
リンク状態型
ハイブリッド
30秒
10秒
(Helloパケット)
10秒
(IS-IS Hello)
5秒
(1.5Mbps以下の
回線は60秒)
ホップ数
コスト(帯域幅)
コスト
帯域幅,遅延,信頼
性,負荷, MTUを
元に合成
Administrative Distance (1/2)
• ルータには経路制御プロトコルの持っている経路表(RIB)
とルータがパケットを転送する際の経路表(FIB)がある
• 同一機器上で複数の経路制御プロトコルを同時に利用し
た際、異なる経路情報を受け取る場合がある
– 経路制御プロトコルごとに経路選択の基準は異なる
• 例:
経路制御
プロトコル
RIPv2
Prefix
Next-hop
10.0.0.0/8
10.0.0.2
OSPF
172.18.2.41
EIGRP
192.168.3.1
Administrative Distance (2/2)
• Administrative Distance
– 経路制御プロトコルなど、経路の情報源に対する信頼度
• ベンダによってはPreferenceとも呼ぶ
• 同じ経路に対して複数の経路情報がある場合には、 Administrative
Distanceの値が少ない方が優先される
• デフォルト値から値を変更することも可能
– デフォルト値の例:
経路の情報源
Cisco, Foundry,
Juniper
Hitachi
(gated)
Connected (直接接続)
0
0
Static
1
20
EBGP
20
170
OSPF
110
10
RIP
120
100
AS(Autonomous System)
• 経路制御ポリシを共有するネットワークの集合
– 外部からは1つのネットワークとして見える
• 全国展開しているISPも外部から見ると1つの巨大なネットワーク
– インターネットは各ASが相互に接続されたもの
• AS番号
– 各ASは固有の番号を持つ
– 日本ではJPNICがAS番号を割り当て
• http://www.nic.ad.jp/ja/ip/asnumber.html
So-Net
2527
OCN
4713
KDDI
2516
IIJ
2497
インターネット
WIDE
2500
経路制御の分割
• 「AS内の経路制御」と「AS間の経路制御」
• 各ASは異なるポリシ・管理体系
• 規模性の問題
– 全世界を一つのRIPやOSPFドメインで接続することはできない
• 障害範囲の限定
– AS内の障害が世界中に伝播しない
• 経路数の軽減
– 経路をAS外に広告する場合、経路を集約できる
AS内の経路制御
(RIP, OSPF)
AS間の経路制御
(BGP)
AS内の経路制御
(RIP, OSPF)
AS
AS
AS
経路制御の階層化
• 経路制御は、大きく２階層に分かれる
– BGPでは、集約された経路情報だけ交換
EGP – (BGPによる)AS間の経路制御
the Internet全体の経路をフルルート(full route)と呼ぶ
約20万経路(2006年11月現在)
AS B
AS E
AS A
AS C
IGP – 各AS内の
経路制御
AS D
経路の集約
AS A
203.178.143.3へ送信
ルータX
BGP
BGPで得た経路情報から、
ASBへ転送
AS内経路制御により、
ルータBへ転送
ルータB
203.178.143.0/24はこっち
ルータA
RIP, OSPF
203.178.143.0/2
5はこっち
203.178.143.128/
25はこっち
ルータC
AS B
203.178.143.0/25
203.178.143.128/25
BGP (Border Gateway Protocol)
• パスベクトル型経路制御プロトコル
– ループフリー
• インターネット全体でループができたら大変
– BGP4自体はIGPとして利用することもできる - iBGP
• 経路制御のポリシを設定に反映しやすい
– ISP間の接続の契約に従った経路制御
複数の対外接続をどう使いわけるかなど
• ピア
– BGPによるルータ間 (AS間) の接続
AS 2516
ピア
ピア
AS 7660
AS 4767
AS 2500
ピア
ピア
AS 4717
パスベクトル型の経路制御方式
• 自分自身から目的地へ到達するまでに辿るパス
を経路として広告
– 目的地へのホップ数や距離ではない
• より短いパスを選択して広告(ベストパス選択)
1
A
A
2 Aは
B
B→A
C
3
1
Aは
C→B→A
A
D
2
E
Aは
D→A
4
Aは
D→A
ベストパス
C→B→A
×
ループ
• 一貫しない経路情報により、各ルータの経路表に
不整合があるとループが発生する場合がある
– パケットが適切な宛先に転送されない
– パケットはTTLが切れるまで転送され続ける
Next-hop is
10.0.0.3
10.0.0.2
Next-hop is
10.0.0.2
traceroute to 10.1.2.3, 30 hops max, 38 byte packets
1 10.0.0.3 8.875 ms 8.753 ms 9.691 ms
2 10.0.0.1 9.564 ms 11.345 ms 14.346 ms
3 10.0.0.2 8.693 ms 8.758 ms 8.631 ms
10.0.0.3
Next-hop is
10.0.0.1
10.0.0.1
4 10.0.0.3 8.622 ms 8.802 ms 8.728 ms
5 10.0.0.1 10.011 ms 12.782 ms 10.113 ms
6 10.0.0.2 10.007 ms 10.627 ms 10.049 ms
ループフリーになる仕組み(1/4)
• 受け取った経路情報のパスに自分自身が含まれ
ているかによってループを検出
– Bは、B自身がパスに含まれたAへの経路を破棄
B
A
C
A
D
ループフリーになる仕組み(2/4)
• 受け取った経路情報のパスに自分自身が含まれ
ているかによってループを検出
– Bは、B自身がパスに含まれたAへの経路を破棄
B
Aは
B→A
C
A
Aは
B→A
D
ループフリーになる仕組み(3/4)
• 受け取った経路情報のパスに自分自身が含まれ
ているかによってループを検出
– Bは、B自身がパスに含まれたAへの経路を破棄
B
C
A
Aは
C→B→A
D
ループフリーになる仕組み(4/4)
• 受け取った経路情報のパスに自分自身が含まれ
ているかによってループを検出
– Bは、B自身がパスに含まれたAへの経路を破棄
B
C
A
!!LOOP!!
Aは
D→C→B→A
Aは
C→B→A
D
BGPの経路表の例
#show ip bgp route
Total number of BGP Routes: 91216
Status A:AGGREGATE B:BEST b:NOT-INSTALLED-BEST C:CONFED_EBGP
D:DAMPED
E:EBGP H:HISTORY I:IBGP L:LOCAL M:MULTIPATH S:SUPPRESSED
Prefix
Next Hop
Metric LocPrf Weight Status
1
4.78.32.0/21
203.178.136.15 9041
100
0
BI
AS_PATH: 6461 14361 29748
2
4.78.32.0/21
203.178.136.15 9041
100
0
I
AS_PATH: 6461 14361 29748
3
4.78.32.0/21
203.178.136.15 9041
100
0
I
AS_PATH: 6461 14361 29748
4
4.78.32.0/21
203.178.136.15 9041
100
0
I
AS_PATH: 6461 14361 29748
5
6.1.0.0/16
203.178.136.15 100
100
0
BI
AS_PATH: 7660 11537 668 1455
BGPによる経路制御ポリシの実現
• 経路のフィルタリング
• BGPのアトリビュート
– AS_PATH
– MED(Multi Exit Discriminator)
• あるＡＳと複数の回線で接続されている場合に利用
• 隣接AS対し、複数ある接続回線のうち、利用すべき回線を指
定
– Local Preference
• 自AS内部において、他ASに行くときに、どの対外ルータを経
由すべきか指定
• Community属性の活用
TCPにおけるフロー制御
フローコントロール
②
もちょっとゆっくり
送って。
受信者
送信者
もちょっとゆっくり
③ 送るか。
①
キュー(バッファ)
早すぎてバッファがあふれる
フローコントロール
②
もっとはやく
送って。
受信者
送信者
③
じゃはやくおくるか
①
キュー(バッファ)
遅いから余裕があるな
ウィンドウ制御
• ウィンドウ広告＝受信バッファ残量
• ウィンドウ更新
– ACKセグメントによる
• ACKを待たずに、複数セグメントを転送
– 転送効率の向上
スライディングウィンドウ
8
1
7
6
直ちに
転送可能
2
広告
ウィンドウ
3
5
4
スライディングウィンドウ
8
転送されたが
1 確認応答されていない
7
2
6
広告
ウィンドウ
3
5
4
直ちに
転送可能
スライディングウィンドウ
8
7
1
転送されて
確認応答済み
2
転送されたが
確認応答されていない
6
3
5
4
直ちに
転送可能
スライディングウィンドウ
8
7
1
転送されて
確認応答済み
2
転送されたが
確認応答されていない
6
3
5
新たに広告された
ウィンドウ
4
直ちに
転送可能
TCPにおける輻輳制御
TCPの輻輳制御機能
②
もちょっとゆっくり
送ろう。
送信者
受信者
輻輳
①
受信者からしばらく応答がない
輻輳が発生してパケットが届いて
なさそうだ
輻輳制御の重要性
• 輻輳は悪化していく傾向がある
輻輳発生
二次災害
なんらかの対処をしなければ
悪化する一方（輻輳崩壊）
玉突き事故
TCPの輻輳制御アルゴリズム
• 非常に多くのアルゴリズムが存在
• 代表的な例
– TCP Tahoe
• スロースタートアルゴリズム，輻輳回避アルゴリズム，高速再転送アルゴ
リズム
– TCP Reno (TCP NewReno)
• 高速再転送アルゴリズム
– TCP Vegas
• RTTをベースとしたウィンドウサイズの調整
• OSによって実装されているアルゴリズムがことなることも
Linux Kernel の持つアルゴリズム
(Kernel 2.6.18の例, /usr/src/linux/net/ipv4/tcp_*.c)
•
Binary Increase Congestion control for TCP (BICTCP)
–
•
TCP Reno / TCP NewReno
–
•
Lawrence S. Brakmo and Larry L. Peterson.
TCP Veno
–
•
Tom Kelly
TCP Vegas
–
•
C.Caini, R.Firrincieli.
TCP Low Priority (TCP-LP)
Scalable TCP
–
•
R.N.Shorten, D.J.Leith.
TCP HYBLA
–
•
•
Sally Floyd.
H-TCP
–
•
Injong Rhee, Lisong Xu.
High Speed TCP
–
•
BSD系OSのデフォルト
Binary Increase Congestion control for TCP v2.0 (TCP CUBIC)
–
•
Lison-Xu, Kahaled Harfoush, and Injong Rhee.
Linuxにおけるデフォルトアルゴリズム
（変更可能）
C. P. Fu, S. C. Liew.
TCP Westwood+: end-to-end bandwidth estimation for TCP
–
Angelo Dell'Aera.
スロー・スタート
• スロー・スタート
– エンドノード間の回線状態はわからない
– 回線の許容量以下に送信量を制御する必要がある
– ネットワークへの突発的なトラフィック流入を防止可能
• 輻輳ウインドウ（cwnd）
– 送信者が送信可能なセグメント数を決定
– 送信者が管理するウィンドウ
– （注）受信者の管理するウィンドウとは別
スロー・スタートの仕組み
• スロー・スタートのアルゴリズム
– 通信開始時
• 輻輳ウィンドウサイズを1で初期化
– Ack受信時
• 輻輳ウィンドウをAck受信毎に増加
• 輻輳ウィンドウは幾何級数的に増加
スロー・スタートの概要
初期windowサイズは1で送信
１に対してAckを返す
送信者
受信者
windowサイズを2で送信
2に対してAckを2つ返す
windowサイズを4で送信
1,2,4,8,,,,と幾何級数的にウィンドウサイズを大きくする
輻輳回避状態
1. スロースタートを開始し、輻輳ウィンドウが増加
2. 送信者は、パケットロスを検知しスロースタートを停止
–
–
•
輻輳が発生したときの輻輳ウィンドウを記憶
輻輳ウィンドウを１に戻しスロースタートを再初期化
輻輳回避状態へ移行
–
–
記憶した輻輳ウィンドウまでは通常のスロースタート
記憶した輻輳ウィンドウに達すると
•
•
Ack受信ごとに輻輳ウィンドウを上げていかない
輻輳ウィンドウ分のAckを受信して輻輳ウィンドウを開く
高速再転送アルゴリズム
• 受信者のTCPが順番の違うセグメントを受信
– 確認応答（重複ACK）を生成する必要
• 単に順番が入れ替わった … (a)
– 受信者はセグメントを並び替えて上位層に渡す
• パケットロスが発生した … (b)
– 送信者は該当するセグメントを再送する必要
• 高速再転送アルゴリズム
– (a)、(b)をいち早く調べる方法
• 以下の場合、パケット損失の可能性高と判断
– 重複ACKを３つ受信した場合
• 再送タイマを待たずに直ちに再送する
高速再転送アルゴリズム
• 再送タイムアウトを待たずに再送
• 迅速な再送による転送効率の向上
５
４
3
2
1
発信元
2番のパケットが
届いていない！
５
４
2番パケットを転送 Packet loss
3
1
インターネット
3が届いた時点で1番へのACK
1番へのACKが
3が届いた時、4が届いた時、5が通ったとき
の合計3回届く
宛て先
TCP Tahoe におけるウィンドウサイズの変化
スロースタート
輻輳回避
ネットワーク
の限界
最適な
ウィンドウサイズ
スロースタート
閾値
t
TCP Reno におけるウィンドウサイズの変化
スロースタート
輻輳回避
ネットワーク
の限界
最適な
ウィンドウサイズ
スロースタート
閾値
t

Download Report