インターネットルーティングチュートリアル

自律分散協調システム論
北陸先端科学技術大学院大学
情報科学センター助教
小原泰弘 (yasu)
[email protected]
2008/06/23
自己紹介
• 慶應義塾
– 高校（1995卒）、環境情報学部（1999卒）、政策・
メディア研究科修士（2001卒）、博士（2008取
得）
• ２００８年４月〜北陸先端科学技術大学院
大学情報科学センター助教
• 専門：インターネット経路制御
– IPv6 OSPF を実装、WIDE 6Bone で運用
– 新しい経路制御アルゴリズム、アーキテクチャを
開発
経路制御とは
• 通信経路を決めるシステム
– どのネットワークがどこにつながっているのか？
– 手動で設定する：静的(static)経路制御
– 自動的に計算：動的(dynamic)経路制御
•
•
•
•
•
規模性
耐故障性（単一障害点の回避）
独立性、協調性、自律ポリシの実現
自律分散システム
ピアツーピアの概念
イメージしてみましょう
•実際のネットワーク
•この規模で動作するシステム
これだと？
これだと？
• インプレスISPマップ
これだと？
インターネットの規模と構造
• インターネットの爆発的な成長
• 経路制御機構の重要性，要求される能力
489,774,269 hosts at Jul 2007
(http://www.isc.org/)
1,319,872,109 users
at Dec 31, 2007
grow 100+ million/year
www.internetworldstats.com
8
自律分散と動的経路制御
• 目的：
– 規模性：巨大なネットワークを自動で計算する
– 耐故障性：回線の故障等を回避する
• 自律性、分散性、協調性
– 各ルータが故障の有無を独立に調べる(自律性)
– 分散したルータ(分散性)が回線で接続されている
– 各ルータが情報をやり取りして(協調性)経路を計
算する
自律分散システムで重要なこと
• 単純さ
– 役割の少なさ、構造の少なさ、単純な処理
• 独立性（≒自律性）
– どの部分それ単体でも動作すること
– 最小のインタラクション、局所性、依存関係の少なさ
• 単純な処理を分散させる
– 単一障害点の回避
• 管理の容易さ
– 集中管理のほうが管理しやすい
• それらのバランスが大事
今日の授業の目的
• 経路制御はインターネット規模でどのように
動いているかを学ぶ
– 原理
– どのような工夫がされているか
– 挑戦と失敗、現状
流れ
• IP の復習：IP アドレス、IP 転送と経路（表）
– 経路集約という規模性に対する工夫など
• 原理：
– ディスタンスベクタ
– リンクステート
– パスベクタ
• 挑戦と失敗、現状など
汎用ネットワークの実現
（階層構造）
layering model
• D. E. Comer. Internetworking with TCP/IP, vol-1. Prentice Hall
（TCP/IPによるネットワーク構築〈Vol.1〉）
OSI 7-layer model
Application
TCP/IP internet layering model
Presentation
Session
Application
Transport
Transport
Network
Internet
Datalink
Network Interface
Physical
Hardware
データの作成と解析
TCPセッションの制御
IPパケットの送受信
イーサネットフレーム送受信
物理媒体への送受信
アプリケーション
ソフトウェア
ホスト
終点は
終点は
どっちだ？どっちだ？
ルータ
ルータ
終点は
どっちだ？
ルータ
アプリケーション
ソフトウェア
ホスト
経路表
• シンプルな構造
– 宛先が共有(同一)ネットワーク → 直接転送
– 宛先が別のネットワーク → 経路表に基づき転送
• ルーティングテーブル
終点
終点
終点
終点
次ホップ
次ホップ
次ホップ
次ホップ
方向（interface）
方向（interface）
方向（interface）
方向（interface）
Ver IHL
TOS
Identification
TTL
IPパケット
ペイロード
終点は
どっちだ
（経路検索）
終点は
どっちだ
（経路検索）
パケット長
FlagFlagment Offset
Protocol Header Checksum
始点IPアドレス
終点IPアドレス
IPヘッダ
IP アドレス
– 同一ネットワーク上のIPアドレスは、同じネット
ワークアドレスを持つ（ネットワーク部が同じ）
–IPアドレスはネットワークインター
フェースに付く
N1内のアドレス
R
10.1.0.2
N1内のアドレス
10.0.0.1
N1
10.0.0.0/8
N2のアドレス
192.168.0.1
R
N2
192.168.0.0/16
IPｖ４アドレス表記方法
• IPｖ４アドレスは３２bit
２０３．１７８．１４２．１３０
• 例：
• １０進数で１バイトずつ表記（０～２５５）
• ピリオドで区切る
• 実際には
.
.
203
178
142
.
130
11001011 10110010 10001110 10000010
16
32
64
128
842 1
128 + 8 + 4 + 2
=142
most ← (significant bit) → least
MSB
LSB
ＩＰアドレスの構造の理由
– Aまで行ければBにもCにも行ける（ARPで）
– BとCを区別する必要があるのはAのみ
– 「現地に行けば分かる」
A
D
E
N1
B
C
複数のネットワークをまとめて一
つのネットワークとして扱う
（アドレス集約，プレフィックス）
複数のホストをまとめて一つのネット
ワークとして扱う
（ネットワークアドレス）
プレフィックスとは
• ＩＰアドレスの「範囲」
• 範囲はどこでも切れるわけではない
0
0x00000000
0.0.0.0
192.168.255.255
4294967296
0xffffffff
255.255.255.255
192.168.0.0/16
192.0.0.0/8
/32→ホスト経路
0.0.0.0/0
(= 255.255.255.255/0)
アドレス全体
→デフォルト経路
ネットワークアドレスとネットマスク
•
•
•
•
IPアドレスの範囲を指定
203.178.142.128～159の３１個のアドレス範囲
例：203.178.142.128 netmask 0xffffffe0
例：203.178.142.128/27（プレフィックス）
.
.
.
203
178
142
130
11001011 10110010 10001110 10000010
11111111 11111111 11111111 11100000
0x
255
ff
.
255
ff
.
255
ff
.
224
e0
203
.
178
.
142
.
128
/ 27
11001011 10110010 10001110 100*****
IPv6アドレス
• IPアドレスは１６バイト（１２８bit）
• IPv4と同様の表記は長すぎ
– IPv4アドレスと同様の表記をすると、
– 123.123.123.123.123.123.123.123.123.123.123.123.123.123.12
3.123
•
•
•
•
16ビットずつ16進数で表現
ピリオド「.」ではなく、コロン「：」で区切る
16ビットの始まりの0は省略できる
コロン間が全て0の連続の場合、１回だけ省略できる
2001:0000:0000:0000:220:e0ff:fe89:dc8
= 2001::220:e0ff:fe80:dc8
IPｖ６アドレス表記方法
• IPｖ６アドレスは１２８bit
•
•
•
•
2001::200:e0ff:fe80:dc8
例：
１６進数で２バイトずつ表記（0x00～0xff）
コロンで区切る
実際には
00100000 00000001 00000000 00000000
00000000 00000000 00000000 00000000
00000010 00000000 11100000 11111111
11111110 10000000 00001101 11001000
IP Forwarding
実際には Dst が IP prefix になっている
Routing Table Lookup
Dst NH I/F
A B B N1
C
B N1
D
B N1
N1
AからDへの通信
C
N2
B
D
Routing Table Lookup
Dst NH I/F
A
A N1
C
C N2
D
D N3
N3
経路 match・longest match
203.178.142.130 は 203.178.128.0/17 に match
203.178.142.130 は 203.178.128.0/20 にも match
203.178.142.130 は 203.178.128.0/21 には？
203
.
178
.
142
.
130
110 0 1 011 101 1 0 010 100 0 1 111 010 1 1 001
203
.
178
.
128
.
0/17
110 0 1 011 101 1 0 010 100 0 0 000 000 0 0 000
203
.
178
.
128
.
0/20
110 0 1 011 101 1 0 010 100 0 0 000 000 0 0 000
203
.
178
.
128
.
0/21
110 0 1 011 101 1 0 010 100 0 0 000 000 0 0 000
挑戦、工夫、失敗（１）
• 不連続ネットマスク
– 人類はうまい利用法を考え付かなかった
– 現在は連続ネットマスクのみ→先頭からのビット数を示せば良い（/18
など）→ということは接頭辞（プレフィックス）のみでよい
• Class A/B/C/D/E
– 先頭のビットで判断：0, 10, 110, 1110, 1111
– default mask：A: /8, B: /16, C: /24,
– アドレス利用効率
• VLSM/CIDR
– Variable Length Subnet Mask
– Classless Inter Domain Routing
– RIPv1/IGRPは Classfull なので × になった
• IPv6
IP 転送の特徴
• IP アドレスの構造
– 単純、柔軟
– 失敗もあった
– それでも作り直す必要が出る(IPv6)
• IP 転送の特徴
– 単純：役割はルータとホストのみ
– 状態への依存性も最小
経路表の正確さ
• 経路が無い場合
– 通信が全く行えない
• 到達できない終点への経路がある場合
– 通信が全く行えない（どちらにせよ）
– 無駄なトラフィック
• 経路がループ（矛盾）している場合
– 通信が全く行えない
– リンクの輻輳
• 経路表は正確でなくてはならない／経路表が正確
であれば通信できる
• 経路制御システムの目的：経路表を正しく作成する
経路制御
• 静的経路制御(static routing)
– 人間が手で経路を設定する
– ネットワークが複雑だと、大変面倒臭い
• 動的経路制御(dynamic routing)
– コンピュータが自動的に経路を計算
– 迂回経路があれば、自動的に通信可能性が回
復
インターネットルーティングプロト
コル
まあまあ良書
• Christian Huitema, Routing in the Internet,
Prentice Hall
• インターネットルーティング, 翔泳社
• 是非英語で！
RIP
• 伝言式
• 隣接ルータと経路表を交換
– 経路表をまる投げ(ブロードキャスト)
• コストはホップ数で表す
– ディスタンスベクター型アルゴリズム
– 通知されたコストに１を追加
– 16ホップを無限大(infinity)
経路表の更新
• 必要に応じて経路表を更新
– 経路表にない経路が通知された場合
– 終点までコストが低い経路が通知された場合
– 経路表のネクストホップから通知された場合
• 各ルータは30秒毎に経路表を通知
– トポロジの変化への対応
– 180秒通知がない経路は切断とみなす
経路表の交換
A
B
A=0
L1
C
A=1
A=0
A=1
B=0
L3
L4
D
L2
C=0
E
A=1
D=0
L5
L6
From E to Link Cost
E
B
C
D
A
local
L4
L5
L6
L6
0
1
1
1
2
A
L4
same cost
No Update!
2
経路表の交換
A
B
C
L1
L3
L2
L4
D
A=2
E
L5
L6
From E to Link Cost
E
B
C
D
A
local
L4
L5
L6
L6
0
1
1
1
2
A
L5
bigger cost
No Update!
3
経路表の交換
A
B
A=0
F L7
A=0
L1
L3
L2
A=1
L3
A=1
C
L4
D
E
A=2
L5
L6
From E to Link Cost
E
B
C
D
A
local
L4
L5
L6
L6
0
1
1
1
2
A
L6
3
経路表のNext Hopから！
Update!
経路表の交換
A
B
A=0
F L7
L1
L2
A=1
L3
L3
C
L4
D
E
L5
L6
From E to Link Cost
E
B
C
D
A
local
L4
L5
L6
L6
0
1
1
1
3
→2。 Fも追加される
Counting to Infinity again…
• 必ずしもCounting to Infinityは防げない
D
From D to Link Cost
A
L3
C
L2
2
A
L3
Error!
B
A
A=16
L1
X
L4
From B to Link Cost
A
L1
From C to Link Cost
16
1
L4
16
2
Counting to Infinity again…
• 必ずしもCounting to Infinityは防げない
D
From D to Link Cost
A
L3
2
5
C
A=2
L2
From C to Link Cost
A
L4
L2
4
16
32
L3
A=4
B
A
A=3
L1
X
L4
From B to Link Cost
A
L1
L4
1
16
41
CよりもDが先に
通知してしまった場合
再び無限ループが発生
Counting to Infinity
RIPまとめ
• Why RIP is so simple ?
– 強さとシンプルさのトレードオフ
• とてもシンプル
– ディスタンスベクター型
– 簡単なプロトコルアルゴリズム
• 小規模ネットワーク用
– 16ホップを Infinity と認識（到達不可能）
• Counting to Infinity という問題
• 解決案
– まったく別のアルゴリズム（リンクステート型）
– 途中経路（パスリスト）を記録する（パスベクタ）
– シーケンス番号
OSPF
• Open Shortest Path First (RFC2328)
• リンクステート型ルーティングプロトコル
– 分散型データベース
– Dijkstra’s SPF algorithm
What is OSPF
• Open Shortest Path First protocol
• the open routing protocol that employs SPF
calculation (developed before 1991)
– specification is OPEN
– SPF calculation = Dijkstra algorithm
• Link state routing protocol
• Loop free
– as long as LSDB is synchronized
– as long as all routers employs the same calculation
• LSA (Link State Advertisement)
• LSDB (Link State DataBase)
用語説明
•
•
•
•
Node：ルータかマルチアクセスネットワーク
Neighbor：近接するルータ
Adjacency：OSPFの経路制御用セッション
LSA (Link State Advertisement)：
– OSPF経路制御情報の単位
• LSDB (Link State Database)：
– LSA のデータベース
OSPF
Open Shortest Path First
• 地図で計算型
• リンクステート型アルゴリズム
– Loop Free
– DV型に比べ、ルータ当たりの計算量が多い
• 信頼性がある(受信確認:LSAck)
• IP 用に作られた
– IP以外は not supported
• IAB が推奨している
OSPF
Open Shortest Path First
• Hello Sub-protocol
– リンク、ネットワークの接続性を監視
• LSA Flooding
– LSA（Link State Advertisement): ルータの接続情報
– 経路制御情報の伝播
• SPF 計算
– トポロジ、経路の計算
• Area functionality
– 経路制御ドメインの分割
LSA
• TLV：Type-Length-Value
– 任意の情報を格納できる
– 経路計算に使う情報が格納される
• LS Type, Link State ID, Advertising Router の組
で識別
• ネットワークの全ルータが同じLSAセット（LSDB)を
持つ
– Router-LSA, Network-LSA, AS-External-LSA, Type-3
Summary-LSA, Type-4 Summary-LSA
OSPFイメージ
LSA
LSDB
AS (Autonomous System)
Neighbor
Adjacency
各ルータは、neighbor と LSA を交換（全ルータで
LSDBを同期）。その後、それぞれのルータが
LSDBから経路を独自に計算する。
リンクコスト
• 管理者の意向を経路に反映するために、ネッ
トワークには「コスト」を設定できる
• コストは、出力側にかかる（有向）
B
D-A: 5
４
１
A ５
１
８
１
２
C
３
A-D: 4
D
マルチアクセスネットワーク
←データベース内の「接続」
←プロトコルセッション(Adjacency)
仮想ノード：O(n)
フルメッシュ：O(n^2) 無駄！
Router-LSA
A
Router-LSA
B
Router-LSA
C
Router-LSA
A
Router-LSA
B
Router-LSA
C
Network-LSA
D
E
Router-LSA
F
D
Router-LSA
Router-LSA
Router-LSA
Designated Router
Router-LSA
Network-LSA
D
Router-LSA
A
Router-LSA
B
E
Router-LSA
Router-LSA
C
F
Router-LSA
E
F
Router-LSA
Router-LSA
DR/Backup（実際）
DR
A
D
B
E
Backup
C
F
DR
• マルチアクセスネットワーク毎に選ばれる
• インターフェイスの状態(State)
– DR/Backup/DROther (/Down/PointToPoint/…)
A
B
C
N1
D
Backup
E
DR
F
Backup
DR
N2
H
I
J
G
Without Designated Router
and Network-LSA
A
1
B
2
7
D
A
1
C
8
3
E
B
2
7
D
C
8
3
E
Router A
B-1
C-1
D-1
E-1
Router B
A-2
C-2
D-2
E-2
Router D
A-7
B-7
C-7
E-7
Router C
A-8
B-8
D-8
E-8
Router E
A-3
B-3
C-3
D-3
With Designated Router
and Network-LSA
A
1
B
2
7
D
A
1
C
8
3
E
B
2
7
D
C
8
3
E
Router B
N1 - 2
Router A
N1 - 1
Network1
A-0
B-0
C-0
D-0
E-0
Router D
N1 - 7
Router C
N1 - 8
Router E
N1 - 3
SPF 計算
D
SPF Tree
B
3
D’s LSDB
LSA D
LSA B
LSA C
LSA A
C
1 計算
A
2
経路表
C|1|2
B|1|3
:
D
C
2
3
A
1
A’s LSDB
LSA A
LSA D
LSA B
LSA C
C’s LSDB
LSA C
LSA D
LSA B
LSA A
全トポロジ情報を持って
いるので、ループを含めた
B
トポロジが計算できる
4
B’s LSDB
LSA B
LSA D
LSA C
LSA A
トポロジ情報から、
それぞれが
独自に経路を計算
topology representation
Router A
B-3
D-1
A
3
1
2
B
3
D
4
1
2
4
C
Router B
A-2
C-4
Router D
A-3
C-1
E-8
8
6
E
Router C
B-2
D-4
Router E
D-6
Dijkstra algorithm
(N)Sc = Shortest path found as cost c at Nth step
(N)Cc = found as Candidate as cost c at Nth step
(0)S0
1. Install shortest path to self
Router A
2. follow the link of the node
B-3
(1)C3
(1)C1
whose shortest path have
D-1
(3)S3
(1)S1
just found in prev-step,
Router B
A-2
C-4
(2)C2
(2)S2
Router C
B-2
D-4
Router D
make those candidate
A - 3 3. Install shortest path of
C-1
candidate that has least
E-8
cost among candidates
Router E (2)C9
(4)C9
D-6
Dijkstra algorithm
• the paths to the candidate vertex that is closest
to the root are guaranteed to be shortest
• OSPF cost is defined to be a positive integer
1. Let C(B-E) be the cost from B
A
to E
G
2. Suppose C(I) is the least cost
C
B
among candidates
D
K
3. Can any I’ that satisfies C(I) >
F
E
C(I’) exist ?
H
?
•C(I) > C(?) + C(?-I’) from 3
I
J
•C(I) < C(?) from 2
I’
C(?-I’) satisfies above will be
negative, so contradiction
Dijkstra algorithm
• Is the path A-B-E-I Loop free ?
• Yes, As long as LSDBs are synchronized
1. C(A-C-F-?-I’) > C(A-B-E-I) so
C(B-A-C-F-?-I’) > C(B-E-I),
no chance for B to get back to
A (unless there’s another path
that we don’t know)
2. the same goes for E and B,
and for I and E
A
G
C
B
D
H
I
K
F
E
?
J
I’
OSPF Hierarchy
• Area を区切って階層化
• AS内には一つ Backbone Area が必要
• 各 Area は Backbone に接続されていなくて
はならない (Virtual Linkの利用)
Backbone
Area
Area
AS
Backbone = Area 0.0.0.0
Area内の計算：SPF algorithm
Area間の計算：Distance Vector algorithm
Area 境界はルータ内部にある
Interface が属する Area は一つ
Area
Area
DV
SPF
OSPF Area Hierarchy
ABR (Area Border Router)
Area 0.0.0.1
Backbone Area
(Area 0.0.0.0)
Area 128.0.0.0
Area 255.0.0.1
Area 0.0.0.128
Area 10.0.0.0
•Normal Area
•Transit Area
•Stub Area
•NSSA Area
Virtual Link
Backbone area must be adjacent to all other areas
設定項目
• OSPF Router-ID：ルータ識別子
• Interface
– Area ID：インターフェースが属する Area ID
– Hello Interval：Hello 送信間隔
– Router Dead Interval：ルータ消滅検知の間隔
– Priority：DRになる優先度
2WAY or FULL
cisco1.fujisawa#
show ip ospf neighbor
Neighbor ID
Pri
lo-0.cisco1.not
1
foundry2.otemac
0
lo-1.foundry1.f
1
lo-1.cisco1.nez
0
lo-1.foundry4.o
1
fe-0-7.hitachi2
0
ge-0-1-0-v4.jun
1
eth2.pc1.hongo.
0
ge-0-0-0-v4.cis
0
203.178.138.234
1
ve-4.foundry2.n
0
ve-4.foundry1.y
0
nec1.yagami.wid
0
ve-4.foundry3.n
1
fe-fxp1.pc3.yag
0
fe-fxp0.pc3.fuj
0
lo-0.cisco11.fu
1
lo-1.foundry1.f
1
fe-fxp0.pc1.fuj
0
fe-0-7.hitachi2
0
ve-100.foundry2
1
State
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
FULL/BDR
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
FULL/DR
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
FULL/BDR
2WAY/DROTHER
2WAY/DROTHER
2WAY/DROTHER
Dead Time
00:00:31
00:00:30
00:00:29
00:00:31
00:00:31
00:00:35
00:00:31
00:00:34
00:00:32
00:00:30
00:00:37
00:00:33
00:00:32
00:00:35
00:00:31
00:00:29
00:00:25
00:00:19
00:00:20
00:00:27
00:00:20
Address
203.178.138.225
203.178.138.227
203.178.138.253
203.178.138.231
203.178.138.241
203.178.138.251
203.178.138.228
203.178.138.230
203.178.138.233
203.178.138.234
203.178.138.237
203.178.138.240
203.178.138.242
203.178.138.244
203.178.138.245
203.178.138.254
203.178.137.78
203.178.137.91
203.178.137.69
203.178.137.70
203.178.137.74
Interface
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet2/0.4
GigabitEthernet1/0.100
GigabitEthernet1/0.100
GigabitEthernet1/0.100
GigabitEthernet1/0.100
GigabitEthernet1/0.100
Open Issues
• LSA 更新間隔
– 定期的、間隔は変えられない(30 min.)
– 140,000 LSA だと一リンク上に流れるのは 77 LSA/sec
– IS-IS にはこの問題が無い
• 最適なコスト設定は数学的に困難な問題
• エリアへの分割の仕方が確立されていない
• 一エリア内の規模性は未知
– Hello メッセージのサイズ制限問題
– ルータ 200 台以内に抑えるのが良いと言う（経験則）
– ルータ 500 台以上でも動いたという噂もある
OSPFまとめ
（利点、工夫、欠点、失敗）
•
•
•
•
•
設定が簡単
ループフリー
受信確認
DR, Network-LSA
LSDB同期処理が規模性の限界
– LSA 再広告間隔
• 最短経路制御のみサポート
– 最適コスト設定問題
その他のルーティングプロトコル
IS-IS
Intermediate System-Intermediate System
• Link state algorithm
– ほぼOSPFと同じ、長い間競争中
• マルチプロトコル対応
– Defined for OSI CLNP by ISO
– TLV
• 制限
– Metric 6bit (4-Types of Metrics)
– 1ルータにつき最大256の状態広告
– エリア機能が貧弱
IGRP
• Interior Gateway Routing Protocol
– Cisco’s proprietary protocol (特許)
• ディスタンスベクタ型アルゴリズム
• Composite metrics （合成メトリック）
– (delay, bandwidth, reliability, load)
• Loop Detection
– Path hold down (隔離期間）
– Route poisoning (ホップ数監視）
EIGRP
• Enhanced IGRP
• VLSMサポート
• Loop Detection
– DUAL (Diffusing Update Algorithm)
Inter Domain Routing / BGP
経路制御の階層化
• 規模性の向上には、階層化が不可欠
– ⇔フラットルーティング
• AS（Autonomous System:自律システム）
– 階層化のための、経路制御ドメインの単位
– 「単一のルーティングポリシを持つ組織」
– 現実の組織と緩く一致
• EGP: Exterior Gateway Protocol、AS間
• IGP: Interior Gateway Protocol、AS内
AS
Autonomous System
• 自律システム
– 元の定義：「単一のポリシで運用される経路制御
ドメイン」
– 今の一般的な定義：「経路制御のためのドメイン」
• インターネットをAS単位に分割
• AS番号の割り当て
– http://www.nic.ad.jp/jpnic/ipaddress/as-numbers.txt
AS Hierarchy
Internet Exchange (IX)
The Internet
3
4
Interior Gateway
Protocol (IGP)
k
8
10
b
f
2
5
6
7
a
j
1
d
c
l
s
m
u
11
e
i
h
g
p
o
n
q
t
v
r
AS (Autonomous System)
x
9
w
Exterior Gateway
Protocol (EGP)
AS Hierarchy
The Internet
EGP
(Exterior Gateway Protocol)
IGP
(Interior Gateway Protocol)
Private Peering
IX (Internet eXchange)
AS (Autonomous System)
IGP
Interior Gateway Protocol
• AS内で用いる経路制御プロトコル
• RIP, OSPF, IS-IS, IGRP, …
IGP
AS
EGP
Exterior Gateway Protocol
• AS間で用いる経路制御プロトコル
• BGP
EGP
AS
Inter Domain Topology
IX: Internet eXchange
AS
F
AS
F
AS
E
AS
AS
A
B
AS
C
AS
D
BGP
Border Gateway Protocol
• 現在のAS間経路制御プロトコル（EGP）
• パスベクタ型アルゴリズム
– Loop Free
• ASレベルでのルーティングポリシーを実現
Path Vector Algorithm
には自分 A が既に
現れているので、ループを検知
D A C
A C
AS
A
C
AS
1
A C 2
B
Loop?
D A C
C
AS
3
4 B A C
AS
D
B A C と
A C
短いパス A C を採用
Internal BGP peer
Internal BGP Peer
eBGP
eBGP
External BGP Peer
R
iBGP
R
IGP
AS
BGPの経路制御情報を
伝播できない
Route reflector
Reflector and cluster
ルーティングポリシ
• ポリシーに基づく経路選択
– 他のISP(AS)とどのようにトラフィックをやりとりしたいか
• 単に近さやコストをもとにした選択ではない
• 他のISPとの間でどのように経路情報をやり取りする
か
• 個々の目的地ごとに経路を選択する
• BGPのパス属性を用いる
– 経路情報のやり取りの制御だけでは実現できないポリ
シーもある
• ネットワークトポロジの再考などが必要
ルーティングポリシの実現
• Multi Exit Discriminator
• Local Preference
• AS Path Prepend
As-path prepend
As-path prepend
MED
Local Pref
BGPまとめ
• ダイナミックな経路情報の更新
– 初期情報の流通（準備）
– 変化の検知とその伝播
• スケーラビリティ
– 規模
– 正確さ
• 自律分散性
– 切断・故障のあとの生き残り部分の経路制御
経路制御の現状
• OSPF/BGP を利用するのが一般的
– IS-IS/BGP や、BGP のみという選択肢もある
• AS内は最短経路制御
– 遠回りさせたいという要求： Traffic Engineering,
QoS Routing
– そのために MPLS が良く利用される
• 帯域保証の NGN (経路制御に変更は無さそ
う)
自律分散システムで重要なこと
• 単純さ
– 役割の少なさ、構造の少なさ、単純な処理
• 独立性（≒自律性）
– どの部分それ単体でも動作すること
– 最小のインタラクション、局所性、依存関係の少なさ
• 単純な処理を分散させる
– 単一障害点の回避
• 管理の容易さ
– 集中管理のほうが管理しやすい
• それらのバランスが大事
まとめ
• 自律分散システムの例として、経路制御シス
テムを説明した
– 人工物で最大規模の自律分散システム
– インターネット自身
• 通信性能、耐故障性、等々
• 様々なものが関わる
– 数学的理論
– 組織や管理などの工学
– 経験則
– 政治経済
終わり
計算量
わかっておくべきこと
• 平均，分散・標準偏差
– 正規分布であれば平均の±２標準偏差の範囲内
に全体の９５％が含まれる
• 線形，対数関数，二（x）次関数，指数関数
– y = cn, log(n), n^x, x^n
計算量とは
• 成長率！
– 入力変数に対する成長率のみ
– 実際にどれだけの時間や空間が必要であるのか
はまったくわからない
• 二つの別のアルゴリズムで，O(n) が O(n^2) より短時
間であってもおかしくない
• 計算時間（ステップ数），計算空間（メモリ量）
• 平均と最悪がある
計算量の出し方
• 係数は重要ではない
– n が巨大になったとき，係数の違いは単なる定数倍にな
る
• 支配項
– 最も重要（巨大）になる項を重要視する
– 他の項は消す場合も： O(n^2 + n) → O(n^2)
• アルゴリズムの解析
– for ループの回数
– 各ステップでの内部計算
• データ構造や検索手法など
良書
• アルゴリズムC・新版―基礎・データ構造・整
列・探索 (単行本)
R. セジウィック (著), Robert Sedgewick (原
著), 野下浩平 (翻訳), 佐藤創 (翻訳), 星守
(翻訳), 田口東 (翻訳)近代科学社; 新版版
(2004/06)
グラフ理論
グラフ理論
• 数学記号に慣れる
– G = (V, E)
• 専門用語を勉強する
– 道，路，（出・入）次数，非循環，閉路
– 有向・無向などなど
• あとはパズル的
• ネットワーク全体を俯瞰するという感覚が重
要
用語
•
•
•
•
•
•
•
•
歩道(walk) – グラフに添った道順
小道(trail) – 辺が重複しない walk
路(path) – 頂点が重複しない trail
閉路(cycle) – 始点＝終点な trail
次数(degree) – ノードの接続辺の数
有向グラフ(directed graph)
容量付きグラフ(capacitated graph)
多重グラフ(multigraph)
良書
• 滝根哲哉，伊藤大雄，西尾章治郎，岩
波講座インターネット 5 ネットワーク設計
理論 ISBN4-00-011055-1
– すごくいい本
– 待ち行列の章は飛ばしても理解できる
最後に
研究とは
• よく調べること．
• 新しいものを発明しなくても良い
– サーベイ論文
– 制度・政策の研究
– ピンクフロイドの歌詞研究！
• 論理的，合理的であることが重要
いろいろなきっかけ
• 甲殻機動隊２
– 全身サイボーグ
– 体中に通信ネットワーク張り巡らされてる
– きっとＩＰだろう（じゃなくてもいいけど）
– 右腕乗っ取られたので，体と右腕との間で制御の
奪い合い，ウィルス攻撃合戦
–そのときのルーティングシステムって
何？
– （ＲＩＰもＯＳＰＦも有り得ない・・・）
研究者の心得・勉強の仕方
• 図書館行く
– 書籍を片っ端から開いてみる
– わかんなかったら無視
– 雑多なものも適当に読み，その上で珠玉の一冊を探す
• 論文を探す
– デジタルライブラリでキーワード検索
– 良い論文を見つける（有名な論文，良く参照される論文，
分かりやすい論文，まとまっている論文，・・・）
– 芋づる方式
• 論文の参考文献から手繰る・辿る（書籍も見つかる）
研究者の心得・勉強の仕方
• 論文読む(efficient reading, skimming)
1. タイトルを読む
2. アブストを読む → 2.を繰り返す or 次の論文に行く
3. イントロを読む → 2. に戻る or 3. を繰り返す or 次の論
文に行く
4. 結論を読む → 2. に戻る or 次の論文に行く
5. 図だけ適当に見る → 2. に戻る or 次の論文に行く
6. 真面目に読む or どうしても知りたいところをしっかり読む
7. 次の論文に行く
• 論文，英語の書き方を知る
– 論文を読み，模倣する（コピペしないように！）
– 論文や英語の書き方の書籍を見る
科学者として
• 目標は高く持て
• ズルすんな
– データ改ざんしない
– 文章の盗作しない
– 研究ネタを使いまわさない
• 誠実であれ
– 見栄張らない，嘘をつく，隠す（出来てないところは言わない等）をし
ない
• 自分が少しでも強引だと思うことはしない
– 自分の研究の欠点を述べる
• ちゃんと評価する
• 無駄を省け
– とことんまで無駄を省き，できるだけ短く
科学者として
• 論理的に，明確に説明せよ
–
–
–
–
–
–
–
–
何を目的としたか
前提は何か
どうしたらどうなると予想したか
なぜそのようになると予想したか（予想の根拠）
何をしたか
どういう結果が出たか
欠点は何か
新規性は何か
• 人の意見を聞く
– 論文を見せる
– 言われたことはちゃんと直す，反論を用意する

Download Report