ネットワーク レイヤ- IP (Internet Protocol) (0) 概要(1) IP (Internet Protocol)(2) Addressing(3) ARP(4) Routing(5) Address Discovery (e.g., DHCP)(6) ICMP
1OSIの7層モデル
レイヤ
7

アプリケーション

6

プレゼンテーション

5

セッション

4

トランスポート

3

ネットワーク2

データリンク

1

物理

Application protocol

アプリケーション

Presentation protocol

プレゼンテーション

Session protocol

セッション

Transport protocol①③⑤

ネットワークデータリンク物理②④⑥

トランスポート

ネットワーク①③

データリンク物理⑤

ネットワークデータリンク物理① : Network Layer Host-Router Protocol (e.g., ES-IS)②, ④,⑥ : サブネットプロトコル (e.g., IS-IS,NNI,)③ : Data link Layer Host-Router Protocol (e.g, UNI)
⑤ : Physical Layer Host-Router Protocol (e.g., UNI)

ネットワーク層 だけは、すべてのコンピュータで共通でないといけない！

TCP/IPの5層モデル
Application protocol

アプリケーション

TCP, UDP

トランスポート

ネットワークアプリケーションIP

ネットワーク

トランスポート
IP

ネットワークIP

ネットワークデータリンクデータリンクデータリンクデータリンク

物理

物理

物理

物理

3

バケツリレーのモデル• 隣接するエンティティだけが手渡せる
1. 少しずつ目的地に向かって進む ＝＝ 全体は知る必要がない
2. 手渡すまでの責任を持てば良い＝＝ 手渡したら忘れることができる

届ける方向
A

B

C

D

E

パケットの転送方法- 輸送システムに例えると L4： アプリケーションデータ ＝＝ 輸送したいものL3： IPパケット ＝＝ 人
L2： データリンクフレーム ＝＝車、電車、飛行機
L1： 物理層 ＝＝ 道路、線路、空/滑走路必要になるもの ；(1) レイヤ間でのインターフェース
e.g., 電車への乗り方、道路の走り方(2) 乗換場所、交差点(3) レイヤの統一規格
5

ping telnet ftp

X

traceroute

tftp bootp smtp

NFS/RPC

OS_Kernel

TCP

UDP
IP

ICMP
Driver

IGMP

Interface
Ethernet

FDDI

SDH

FR

ATM

図1-20. インターネットシステムにおけるソフトウェア構造の例
6

パケット• pack・et n.

（出典：EXCEED英和辞典）– 小包； （小さい）束；– 【コンピユータ】 パケット (データの転送の単位)；

これ7IPパケットの転送- 東大からコロンビア大へ 運びたいもの： 映画
媒体(CD, MD, DVD)、符号化(AVI, MPEG,DV)

経路はいっぱいあるねぇ。。
1. 本郷 ➔ 成田空港
2. 成田空港 ➔LGA/JFK/EWR
3. LGA/JFK/EWR ➔ マンハッタン(*) おっと、船もあったし、AMTRAK(電車) も飛行機が嫌いな人もいた。。。。
なるべく速く行きたい人もいた。。。。
8

IPパケットの転送- 東大からコロンビア大へ 利用する交通機関(データリンク)も いっぱいあるねぇ。。
1. 足(徒歩ともいう)
2. 自転車
3. 自動車4. 電車
5. 船
6. 飛行機(*) たまには予約も必要。。。。混んでると乗れないこともあるなぁ。。。
9

IPパケットの転送- 東大からコロンビア大へ 物理層もいろいろあるねぇ。。。。
1. 道路： 砂利道、ぬかるみ、舗装路
交通事故
2. 空 ： 高度と経路で値段違うのよねぇ。。。
墜落
3. 電車： 乗り心地、、、
列車事故(遅延、行けなくなる)4. 海 ： 天候次第でえらい違い
台風に巻き込まれると遭難、、、
10

IPパケットの転送- 東大からコロンビア大へ << 電話、放送、インターネットの違い >>電話 ： 先に偵察隊(シグナリング)が飛び、糸(=資源)があるか確認し、確保し、報告。
その後に、実際にものを送る。
放送 ： 面倒なので、とりあえず、送り続ける。
受信者側が、受け取るかどうか決める。
(SPAMに似ている)
インターネット ： つながっているかどうかの情報は報告されている(経路制御)。
つながっていれば、転送しちゃう。
届かないかもしれない。。。。。
11

用語の定義• ノード (e.g., 自宅、駅、空港)– インターネットに接続できる機器• ルータ・中継ノード (e.g., 駅、交差点)– 受け取ったパケットを転送できる(バケツリレー）
ノード• ホスト・エンドノード (e.g., 自宅)– ルータ・中継ノード以外のノード• 通常、家庭や会社にあるPCはホスト・エンドノード

12ルータ と ノード• いろいろな リンク(乗り物)を収容する。
• 人を適切なリンク(乗り物)に乗せる➔ 乗り物がたくさんあると悩んでしまう。。。。

• 車の交差点は特殊なケース• 交差点(i.e., ルータ)人が乗り物を乗り換える• どこで降りようか/乗り換えようか ?
➔ 経路制御(Routing Protocol)の役目• どの乗り物(席、時間)を使おうか？
➔ リンクアクセス制御(MAC (Media Access Control) Protocol)• 混んでいる乗り換え点では、事故が絶えない➔ 渋滞、衝突、乗り遅れ
13

IP - インターネット・プロトコル• IPパケット(= 人)
始点アドレス 終点アドレス• IPとTCP

データ

net-C

APP
TCP
IP

APP
TCP
IP

IP

net-A

net-B

14

経路制御
• ルータは受信したパケットの送り先のネット
ワーク番号から，次のルータを決定する
太平洋線
車
電車
自転車
徒歩

成田

東京駅

ルータ

R1

Net1
欧州線

Net2
羽田

Net1
Net2
Net3
Net4

R1
R1
R2
R3

経路表

R2

国内線

Net3

新横浜駅

R3

新幹線

Net4
15

IP(Internet Protocol) ～機能と特徴～
• 機能

• 特徴

– ホスト(インターフェース) – 信頼性のない通信を提供• データグラム型の識別• 32bits(or 128bits)の識別子• IPアドレス– データの中継• 乗換駅の例： 乗換え• ルータ・ゲートウェイ– データの分割• 一度に送れないデータを分割、再構成• 「失敗したらごめんね」• 最大限努力する– 大規模な環境• 処理が単純– 仕様が公開• RFC791

16IPの仕事• 指定されたコンピュータのインターフェースへ
データを届ける– 相手の指定(Addressing)– データの中継(Routing)• データの大きさの制限– 大きなデータは分割(Fragment)– 受け取ったら元に戻す(Reassemble)

17

IPアドレス• 32ビット(IPv4) と 128ビット(IPv6)の2進数– 例：10011101 01010010 11110110 01111000• IPv4– 8ビットずつ区切って10進数で表したものをドット(ピリオド)でつないで表記– 例：157.82.246.120• IPv6– 16ビットずつ区切って Hex で表したものを、コロン(：) でつないで表記– 例 2001:0db8:beef:cafe:0000:0000:0000:123
18

ネットマスクとプレフィックス• ネットワーク部は可変•

プレフィックス長によるネットワーク番号表記
プレフィックス長

アドレス

マスク

net-id1111..............11111

host-id0000......0000

例）133.201.2/24
プレフィックス長
ネットワーク番号19

IPアドレスのクラス｛という概念があった。。。歴史｝
32ビット

クラス

アドレス範囲1.0.0.0～
127.255.255.255

A

0 ネットワーク

ホスト

B

1 0

C

1 1 0

D

1 1 1 0

マルチキャスト・アドレス

224.0.0.0～
239.255.255.255

E

1 1 1 1 0

将来の使用に備え予約

240.0.0.0～
247.255.255.255

ネットワーク

128.0.0.0～
191.255.255.255

ホスト

ネットワーク

ホスト

192.0.0.0～
223.255.255.255

20

サブネット(階層化を自由に定義可能)
32ビット

1 0

ネットワークサブネット

ホスト(サブ)ネット1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
マスク

cf. 市外局番─市内局番─加入者番号• 組織の外からはサブネットは見えない• ドット表記または「IPアドレス/(サブ)ネットマスク長」で表記– 例： 10.0.1.0/24
21アドレスの種類• ユニキャスト(Unicast)• マルチキャスト (Multicast)• エニキャスト (Anycast)• Reserved• プライベート (Private)– 10.0.0.0/8（クラスA×1）– 172.16.0.0/12（クラスB×16）– 192.168.0.0/16（クラスC×256）
22

IP経路(ルーティング)制御- 金太郎飴的(recursive)ネットワーク AS=2014
AS=1998

AS=1210

AS=1391

IX

AS=1018

AS=2913

OSPF Backbone Network(Area0)POP

Area1

Webサーバ202.249.10.122

AreaN

Area2

POP
Campus Net.

Backbone Network

Campus Net.

: Boarder RouterDial-up access
メールサーバ133.196.16.10

23

Aggregating routing prefixes• Contiguous routing prefixes can be aggregated.
24
C

Network prefix

00

Host ID

C

Network prefix

01

Host ID

C

Network prefix

10

Host ID

C

Network prefix

11

Host ID- Address Aggregation- 4x(/24 address) → 1x(/22 adress)

22
４C

Network prefix

Host ID24

Aggregating Routing Prefixes
192.24.0.0 - 192.24.7.0= 192.24.0.0/21

192.32.0.0 - 192.32.15.0= 192.32.0.0/20

192.24.16.0 - 192.24.31.0= 192.24.16.0/20
192.24.8.0 - 192.24.11.0= 192.24.8.0/22
192.24.34.0 - 192.24.35.0= 192.24.34.0/23

RA

192.24.12.0 - 192.24.15.0= 192.24.12.0/22

RB

192.24.32.0 - 192.24.33.0= 192.24.32.0/23

192.24.32.0/22
192.24.0.0/19
192.32.0.0/20

192.24.32.0/22
192.24.0.0/19
192.32.0.0/20

25

0
1
2
3
12345678 90123456 78901234 56789012[1] 192.32. 0.0/20 : 11000000.00100000.0000---- -------[2] 192.24.34.0/23 : 11000000.00011000.0010001- -------[3] 192.24.32.0/23 : 11000000.00011000.0010000- -------[4] 192.24.16.0/20 : 11000000.00011000.0001---- -------[5] 192.24. 0.0/21 : 11000000.00011000.00000--- -------[6] 192.24. 8.0/22 : 11000000.00011000.000010-- -------[7] 192.24.12.0/22 : 11000000.00011000.000011-- -------Aggregate; [2] + [3] = [8] (.34/23 + .32/23)[6] + [7] = [9] (.8/22 + .12/22)

01
2312345678 90123456 78901234 56789012[1] 192.32. 0.0/20 : 11000000.00100000.0000---- -------[8] 192.24.32.0/22 : 11000000.00011000.001000-- -------[4] 192.24.16.0/20 : 11000000.00011000.0001---- -------[5] 192.24. 0.0/21 : 11000000.00011000.00000--- -------[9] 192.24. 8.0/21 : 11000000.00011000.00001--- -------Aggregate; [5] + [9] = [10] (.0/21 + .8/21)
26

0
1
2
3
12345678 90123456 78901234 56789012[1] 192.32. 0.0/20 : 11000000.00100000.0000---- -------[8] 192.24.32.0/22 : 11000000.00011000.001000-- -------[4] 192.24.16.0/20 : 11000000.00011000.0001---- -------[5] 192.24. 0.0/21 : 11000000.00011000.00000--- -------[9] 192.24. 8.0/21 : 11000000.00011000.00001--- -------Aggregate; [5] + [9] = [10] (.0/21 + .8/21)

01
2
312345678 90123456 78901234 56789012[1] 192.32. 0.0/20 : 11000000.00100000.0000---- -------[8] 192.24.32.0/22 : 11000000.00011000.000110-- -------[4] 192.24.16.0/20 : 11000000.00011000.0001---- -------[10] 192.24. 0.0/20 : 11000000.00011000.0000---- -------Aggregate; [4] + [10] = [11] (.16/20 + .0/20)

012312345678 90123456 78901234 56789012[1] 192.32. 0.0/20 : 11000000.00100000.0000---- -------[8] 192.24.32.0/22 : 11000000.00011000.000110-- -------[11] 192.24. 0.0/19 : 11000000.00011000.000----- -------27

ネットワーク レイヤ- IP (Internet Protocol) → (1) IP (Internet Protocol)(2) Addressing(3) ARP(4) Routing(5) Address Discovery (e.g., DHCP)(6) ICMP/IGMP28

IP version 4 (IPv4) Header Format
78

0 version
12

headerlength15 16
TOS

datagram-id
TTL

23 24
Total length (Bytes)
Fragment offset (13bits)

flag(3)

protocol-id

header checksum3source IP address

4

destination IP address

31

20 Bytes0

options (if any)
TCP/UDP data29

$40.00 / IPv4 addressFragment・ リンクMTU以上のパケットはFragment。
(要は、大き過ぎるパケットは、切り刻む)
・ すべてのパケットが同一のsrc_IP, dst_IPを持つ。
・ Flag=フラグメントの継続を示す(最後=“0”、他=“1”)・ Offset ; Byte単位の表現(先頭=“0”)
0

F1

F2

H0
H1

H2

H3

-FG=1
-OF=0

-FG=1
-OF=F1-FG=0-OF=F231

パケット分割ルータ

最大パケット長
最大パケット長
最大パケット長
ルータ
ルータ
ルータ
1500バイト
1000バイト1500バイト
len=1500,Id=xyz
MF=0, offset=0

len=996, Id=xyz
MF=1, offset=0

len=996, Id=xyz
MF=1, offset=0

len=524, Id=xyz
MF=0,offset=122

len=524, Id=xyz
MF=0,offset=12232

パケット分割ルータ

最大パケット長
最大パケット長
最大パケット長
ルータ
ルータ
ルータ
800バイト
1000バイト1500バイト
len=1500,Id=xyz
MF=0, offset=0

len=996, Id=xyz
MF=1, offset=0

len=524, Id=xyz
MF=0,offset=122

len=796, Id=xyz
MF=1, offset=0

len=220, Id=xyz
MF=1, offset=97

len=524, Id=xyz
MF=0,offset=12233

IP version 6 (IPv6) 基本Header Format
78

0 version

Priority1

Payload Length

2
3
4
5
6
7
8
9

15 16
Flow Label

23 24

Next Header Typesource IP address (128 bits)

destination IP address (128 bits)

options (if any)

TCP/UDP data

31
Hop-Limit

40 Bytes0IPｖ6 状況
1．GAFA+M, BAT は すべて対応済
2．速くしたい人は、IPoE 化！
(*) PPPoE は、厳しい状況
3. IPv4 as-a-Service
with IPv6 Single Stack へIPv6 in public carriers in Japan
73.8%

Wired IPv6 in NGN users

Mobile IPv6
in Japanese major 3 MNOs

36

外国の状況
• インド： モバイルで 一気に 普及• 中国 ： 政府が推進を{再}決定(2018年)

Googleの測定では見えません….!!!

WIDE Projecthttps://www.internetsociety.org/resources/2018/state-of-ipv6-deployment-2018/

Rank

ISP

Country

IPv6 Users (estimated)

1 Reliance Jio
2 Comcast
3 AT&T
4 Vodafone India
5 Verizon Wireless
6 Idea Cellular
7 Deutsche Telekom AG

237,600,764
36,114,435
22,305,974
18,368,165
15,422,684
14,681,694
14,261,836

8 T-Mobile USA
9 KDDI Corporation

14,057,105
11,871,952

10 Sky Broadband
11 Claro
12 Softbank
13 Orange
14 AT&T Wireless
15 Cox Communications

11,829,610
10,235,805
8,613,145
7,924,119
7,694,881
6,316,462

16 Kabel Deutschland

5,835,590

17 SK Telecom
18 NTT Communications

5,764,073
5,596,206

Rank of IPv6 users in 2018
[Source]
Internet Society web siteCloud Platform Upgrade

AlibabaTencent

Baidu

Kingsoft
Finished

JD
Unfinish

China Telecom China Mobile

China Unicom

Finish Percent

www.CFIEC.net

IPv6 address notation◆IPv4 address notation
Binary digit notation (32bits)
11000000 10101000 00000000 00000001

For every 8bits, display in decimal number and separate with “.”
192.168.0.1◆IPv6 address notation
Binary digit notation (128bit)
0010000000000001 0000110110111000 1011111011101111 1100101011111110
0000000000000000 0000000000000000 0000000000000000 0001001000110100

For every 16bits, display in Hex number and separate with “:”
2001:0db8:beef:cafe:0000:0000:0000:1234

Leading zero in 16bits field can be abbreviated2001:db8:beef:cafe:0:0:0:1234

Compress the zeros with “::” Can be done only once for each address
2001:db8:beef:cafe::1234

IPv6 Header Format

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

VersionTraffic Class
Payload Length

Flow Label
Next Header

Hop Limit

Source Address(128bit)

Destination Address(128bit)
Extension header

IPv4 Header Format

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

Total Length
IHL Type of Service
Identification
Fragment Offset
Flags
Time to Live
ProtocolHeader CheckSum
Source Address(32bit)
Destination Address(32bit)
Option Data (Variable)
Padding

Version

Newly defined in IPv6
Field name is changed
in IPv6
Deleted fieldIPv6 Unicast Address
Global Unicast Address
001

Global Routing Prefix

Subnet ID

Interface ID(3bit)

48bit

16bit

64bit

• Globally unique address e.g. 2001:db8::1

Link-Local Unicast Address
1111111010

Interface ID

0

10bit

54bit

64bit

• Unique address within one link (segment) (fe80::/10)Used for the communication within the link such as plug & play

Unique Local Unicast Address (ULA)1111110 L

8bit

Global ID

Subnet ID

16bit
L bit 0: future use 1: locallyassigned pseudorandom Global ID• Local address that could be used freely （fd00::/8）• Substitute for deprecate-site local address[RFC4193]
Interface ID
64bit

43

IPv6 Multicast Address (1)• One to many communication– Sent to specific groups such as live streaming of a video– Mainly used by NDP (Neighbor Discovery Protocol) in IPv6

Multicast Address
11111111

Flag
0RPT

Scope

Group ID

8bit

4bit

4bit

112bitFlag

Function

T flag0：Permanently-assigned (“well-known”) address assigned by IANA
1：non-permanently-assigned multicast address

P flag

1：Unicast-Prefix-based multicast address (RFC3306）* when P=1, then T must be 1

R flag1：For Rendezvous Point (RP)mapping in PIM-SM（RFC3956）* if R=1then (P=1&T=1)

Scope： Limit the scope of the multicast group0000（0）Reserved

0101（5）site-local scope0001（1）interface-local scope

1000（8）organizational-local scope0010（2）link-local scope1110（E）

global scope

0100（4）admin-local scope1111（F）

Reserved

44

IPv6 Anycast Address
Anycast address• Assigned to multiple nodes. Packets are sent to the nearest node in routing distance.
• Anycast addresses are syntactically indistinguishable from unicast addresses.
• Example usage: Root DNS

Subnet Router Anycast Address
Interface ID
All 0 （0..0）

Site prefixn bit

128 - n bit•Packets sent to this address will be delivered to one router on the subnet.
Communication comparison
Unicastone to one

Multicast

one to many

Anycastone to one of any

45

ネットワーク レイヤ- IP (Internet Protocol) (1) IP (Internet Protocol)→ (2) Addressing(3) ARP(4) Routing(5) Address Discovery (e.g., BOOTP)(6) ICMP/IGMP

46

アドレス
• 2つの目的– 目的のノード(のインターフェース) を識別するための識別子– 目的のノード(のインターフェース)へパケットを届ける(Routing)ためのヒント• アドレスの構造– 階層化(Hierarchy)と集約化(Aggregation)• 効率的な Routingのためのアドレス構造– 究極的には、個別の識別子でやりたい– 現実的には、集約化したアドレス空間を定義• アドレス空間の大きさ(＝桁数)47アドレス構造• 効率的な Routingのためのアドレス構造– 可変長 vs 固定長• 情報理論的には、可変長で、情報の多いもの(多くのノードを収容する空間)には、短いシンボル(アドレス長)を割り当てるべき。
➔ 転送すべき総情報量を極小化できる。

• ということで。
– 電話 ： CC(可変長)、TLA(可変長)、NLA(可変長)、SLA(固定長)– インターネット ： 昔は固定長、今はすべて可変長– 放送(ラジオ/テレビ) ： 特に関係なし

48

ネットマスクとプレフィックス• ネットワーク部は可変•

プレフィックス長によるネットワーク番号表記
プレフィックス長

アドレス

マスク

net-id1111..............11111

host-id0000......0000

例）133.201.2/24
プレフィックス長
ネットワーク番号49

アドレス構造• 効率的な Routingのためのアドレス構造– 可変長 vs 固定長• 情報理論的には、可変長で、情報の多いもの(多くのノードを収容する空間)には、短いシンボル(アドレス長)を割り当てるべき。
➔ 転送すべき総情報量を極小化できる。

• ということで。
– 電話 ： CC(可変長)、TLA(可変長)、NLA(可変長)、SLA(固定長)– インターネット ： 昔は固定長、今はすべて可変長– 放送(ラジオ/テレビ) ： 特に関係なし

50

オーダー。。。
• 階層化と集約化が、運命の分かれ道– 構造を 持たない アドレス
• MACアドレスとか• オーダー n ； o(n) と書く。

– 構造を持つアドレス• 階層化– 下手な階層化 ➔ 実は 依然として o(n) になる。
– 上手な階層化 (集約化との組み合わせ) ➔ o(log n) になる。
(例) 100を単位に階層化＆集約化
2階層で1万、3階層で100万、4階層で10億 と指数関数で増加➔ でも、、、、管理する情報量は、常に 100のオーダー。

(*) 必要になるもの； 2つのアドレスのマッピング/解決ネットワーク レイヤ- IP (Internet Protocol) (1) IP (Internet Protocol)(2) Addressing→ (3) ARP ➔ データリンク層で。
(4) Routing(5) Address Discovery (e.g., DHCP)(6) ICMP/IGMP

52

ネットワーク レイヤ- IP (Internet Protocol) (1) IP (Internet Protocol)(2) Addressing(3) ARP→ (4) Routing(5) Address Discovery (e.g., DHCP)(6) ICMP/IGMP53

Routing[Routingの種類](a) 静的ルーティング(static_routing, default_routing)(b) 動的ルーティング(dynamic_routing)[Routing Process(Dynamic Routing)が行う仕事](i) 経路情報の広告(to 隣接ノード)(ii) 経路の計算(iii) パケットの送信・転送・受信[パケットの受信時の手続き](1) host_address の検索(2) network_address の検索(3) defaultエントリー の検索
54

経路制御
• ルータは受信したパケットの送り先のネット
ワーク番号から，次のルータを決定する
太平洋線
車
電車
自転車
徒歩

成田

東京駅

ルータ

R1

Net1
欧州線

Net2
羽田

Net1
Net2
Net3
Net4

R1
R1
R2
R3

経路表

R2

国内線

Net3

新横浜駅

R3

新幹線

Net4
55

経路制御のお仕事。
• 数学的な表現– あるノード(目的地)をルート(根) とする ツリーを形成する。 ツリーは、多数存在可能であるが、あるコスト関数を用いて 唯一のツリーを選択させる。
– これを、すべてのノードに対して生成する。
– 全世界規模の完全なツリーを管理することは困難なので、上手に 再帰的(Recursive)な構造を持ち込む。

• ツリー ;
– 閉じた部分を持たないトポロジー
56

IP経路(ルーティング)制御- What a dynamic routing protocol does Import & Export
available networks
202.249.xxx.yyy→ R8

202.249.xxx.yyy → R6

202.249.xxx.yyy → R4

R5
R2

R8

R4
R1
R3

133.196.16.19
From 133.196.16.19 to 202.249.10.122

R6
R7

R9

Webサーバ202.249.10.122

A. 経路の計算(back-ground)
1.Routing Domain内の全接続情報
2. 接続されている全アドレス情報(輸出入)(Routing Domain 内・外)
B. L3パケット転送制御(on-demand)→ 宛先＝202.249.10.122 (ベストマッチ検索)→ Next Hop＝“R2” for 202.249.xxx.yyy
57

Dynamic Routing Protocols[Unicast Routing](1) IGP (Interior Gateway Protocol)(a) RIP (Routing Information Protocol)(b) OSPF (Open Shortest Path First)(2) EGP (Exterior Gateway Protocol)(c) BGP4 (Border Gateway Protocol version 4)[Multicast Routing](i) DVMRP (Distance Vector Multicast Routing Protocol)(ii) MOSPF (Multicast OSPF)(iii) PIM (Protocol Independent Multicast protocol)(iv) MBGP (Multicast BGP)
58

デフォルトルート• インターネット中の全てのネットワークをルー
ティングテーブルに書くことは困難• 「その他のネットワーク」を一括してアドレス
0.0.0.0、ネットマスク0.0.0.0で表現• 「デフォルトゲートウェイ」のみ設定することも多い

59

netstatコマンド

61

netstatコマンド

62

Dynamic Routing Protocols[経路計算アルゴリズム](1) 距離ベクトル(Distance Vector) 方式 ; DV型(2) リンク状態 (Link State) 方式； LS型(3) パス ベクトル (Path Vector) 方式； PV型(4) ソースルーティング (Source Routing) 方式
Routing Type

RIP
OSPF
BGP4
DVMRP
MOSPF
PIM
MBGP

DV型 LS型
Yes
Yes

PV型

Yes
Yes
Yes
n/a

n/a

－
n/a
Yes

ObjectIPv6
routedRIPng
gated
OSPFv6
gated
BGP4＋
mrouted －
－
－
－
－
－
63

ルーティングテーブル
10.0.0.1
ルータA
172.16.0.1

172.17.0.1
ルータB

172.17.0.2

172.17.0.3

ルータC

172.16.0.2

ルータD

192.168.1.1

192.168.2.1

ルータAのルーティングテーブル

宛先（サブ）ネットワーク （サブ）ネットマスク 転送先
10.0.0.0

255.0.0.0

10.0.0.1

172.16.0.0

255.255.0.0

172.16.0.1

172.17.0.0

255.255.0.0

172.16.0.2

192.168.1.0

255.255.255.0

172.16.0.2

192.168.2.0

255.255.255.0

172.16.0.2
64ルーティングテーブル
10.0.0.1
ルータA
172.16.0.1

172.17.0.1
ルータB

172.17.0.2

172.17.0.3

ルータC

172.16.0.2

ルータD

192.168.1.1

192.168.2.1

ルータBのルーティングテーブル

宛先（サブ）ネットワーク （サブ）ネットマスク 転送先
10.0.0.0

255.0.0.0

172.16.0.1

172.16.0.0

255.255.0.0

172.16.0.2

172.17.0.0

255.255.0.0

172.17.0.1

192.168.1.0

255.255.255.0

172.17.0.2

192.168.2.0

255.255.255.0

172.17.0.3
65

ルーティングテーブル
10.0.0.1
ルータA
172.16.0.1

172.17.0.1
ルータB

172.17.0.2

172.17.0.3

ルータC

172.16.0.2

ルータD

192.168.1.1

192.168.2.1

ルータCのルーティングテーブル

宛先（サブ）ネットワーク （サブ）ネットマスク 転送先
10.0.0.0

255.0.0.0

172.17.0.1

172.16.0.0

255.255.0.0

172.17.0.1

172.17.0.0

255.255.0.0

172.17.0.2

192.168.1.0

255.255.255.0

192.168.1.1

192.168.2.0

255.255.255.0

172.17.0.3
66

ルーティングテーブル
10.0.0.1
ルータA
172.16.0.1

172.17.0.1
ルータB

172.17.0.2

172.17.0.3

ルータC

172.16.0.2

ルータD

192.168.1.1

192.168.2.1

ルータDのルーティングテーブル

宛先（サブ）ネットワーク （サブ）ネットマスク 転送先
10.0.0.0

255.0.0.0

172.17.0.1

172.16.0.0

255.255.0.0

172.17.0.1

172.17.0.0

255.255.0.0

172.17.0.3

192.168.1.0

255.255.255.0

172.17.0.2

192.168.2.0

255.255.255.0

192.168.2.1
67

Distance Vector Routing Protocol
・ Bellman-Ford アルゴリズム (or Bellman-Fullkerson)- 1969年頃のARPANETにおいて使用- Developed by Xerox-PARC as XNS-RIP- Nodeから到達可能な宛先アドレスへの距離(Distance)
情報。すなわち、到達可能な宛先アドレスへの最適経路のベクトル情報を管理し、最も距離(Distance)が小さな経路を、宛先ネットワークへの最適経路と判断する。
- ルーティングドメインの接続情報は持たない。
① Distance Ventor ：宛先ネットワークに対する最短の距離情報ベクトル② 次ホップノード情報{dst_net, distance, next_hop_node}68Routing Information Protocol (RIP)・ RIP for IPv4 ; RFC 1058/1721/1722/1723/1724
RIP for IPv6 ; RFC 2080
・ routed (ルートデーモン) in BSD, SunOS- 最大ホップ数 ; 15 ホップ- Cold-Start 方式; 経路の計算に最大450秒(=15x30秒)必要- 30秒ごとにDistance Vectorデータベース情報の交換→ ノード/リンクの状態変化もホップホップに伝播- UDP(port=520)を用いたデータベース(Distance Vector)の交換。
- 180秒返事がないと故障と判断する(keep-alive方式)- 最適経路の計算式；- D(i,j) ; distance vector- d(i,j) ; node_i と node_j 間の距離

D(i,j) = min [d(i,k) + D(k,j)](for all k)

69

Routing Information Protocol (RIP)
A

(1)

(3)

B

(2)

C

(4)
(5)

D

E

(6)

(1) 0 sec
From A to Link Cost
A
local
0

(2) 30 sec

B→A

From B to Link Cost
B
local
0

D→A

From D to Link Cost
D
local
0

From A to Link Cost
A
local
0
B
(1)
1
D
(3)
1
70

Routing Information Protocol (RIP)(2) 30 sec
From A to Link Cost
A
local
0
B
(1)
1
D
(3)
1

(3) 60 sec
From A to Link
A
local
B
(1)
C
(1)
D
(3)
E
(1)

A

(1)

(3)

D

B
(4)

(6)

B→A

From B to Link Cost
A
(1)
1
B
local
0
C
(2)
1
E
(4)
1

D→A

From D to Link Cost
A
(3)
1
D
local 0
E
(6)
1

Cost
0
1
2
1
2

E

Select one from even two path
→ {(1),2} vs {(3), 2}

(2)

C

(5)

71

Routing Information Protocol (RIP)(3) 60 sec
From A to Link Cost
A
local
0
B
(1)
1
C
(1)
2
D
(3)
1
E
(1)
2
B→A

D→A

(4) 90 sec
From A to Link Cost
A
local
0
B
(1)
1
C
(1)
2
D
(3)
1
E
(1)
2

A

(1)

(3)

D

B
(4)

(6)

E

(2)

C

(5)

From B to Link Cost
A
(1)
1
B
local
0
C
(2)
1
D
(1)
2
E
(4)
1
From D to Link Cost
A
(3)
1
B
(3)
2
C
(6)
2
D
local 0
E
(6)
1

72

Link State Routing Protocol
・ SFP (Shortest Path First) 方式- 1970年頃のARPANETにおいて使用→ 大規模化への対応(Distance Vectorの課題の克服)- ルーティングドメイン内の各ノード間の接続トポロジー情報 と、ノード間の接続リンクのコスト値(Attribute value)のデータベースを持つ。
- リンク状態データベースは、ルーティングドメイン内のすべてのノードで同一。
- 同一のデータベース情報、同一の経路計算アルゴリズムを適用して各ノードで独立に最適経路(自ノードから宛先ネットワークへ最小コストで到達するために取るべき次ホップノードの選択)の計算を行う。
- リンクコストの積算値が極小となる経路を「最小コストの経路」とする。
→ 宛先ネットワークごとに、最小コストを提供する
Spanning_Tree の形成
73

Open Shortest Path First (OSPF)[ Link State Data-Base ]

A

(1)

(3)

B

(2)

C

(4)
(5)

D

(6)

E

At Node “A”
To Next-Hop Link-id
B
B
1
C
B
1
D
D
3
E
B
1

Exchange
LS information
between neighbor
node

From
A
A
B
B
B
C
C
D
D
E
E
E

To Link-id Distance
B
1
1
D
3
1
A
1
1
C
2
1
E
4
1
B
2
1
E
5
1
A
3
1
E
6
1
B
4
1
C
5
1
D
6
1

Calculate spanning tree

A
Build routing
table

(1)

B

(3)

D

(2)

C

(4)

E
74

Path Vector Routing Protocol- 1982年頃のRFC827 (EGP; Exterior Gateway Protocol)→ NSFNETバックボーンと地域バックボーンの相互接続を目的として開発された(RFC1093)。
→ 各ネットワークの運用・制御ポリシーを反映させる
ことのできるルーティングプロトコル。
- AS (Autonomous System)間での経路制御；
16 bits (現在は 32bitsに拡張)で表現される 自律ネットワーク(AS番号)間で、各宛先ASのネットワークへ到達するための経路を、AS番号 の順序列(Path-Vector)、あるいはAS番号の集合を用いて表現する。 各ASの境界ルータ(Boarder Router)は、隣接ルータ(Peering Router)と、自ASから、すべての到達可能な宛先ASへの到達経路(path)を広告する。 Path(AS番号の順序列)の集合情報を利用するので、Path-Vector方式と呼ばれている。
75

Path Vector Routing(AS=1)(AS=2)

A

B

A1,A2

E
D1

(AS=4)[ Path Vector Data-Base in node A]
From To
A
B1
A
B2
A
C1
A
C2
A
D1
A
E1
A
E2

Path
A,B
A,B
A,B,C
A,B,C
A,D
A,D,E
A,B,E

C C1,C2

B1,B2

D(AS=5)(AS=3)

Next-Router
B
B
B
B
D
D
B

E1,E2

[ Path Vector Data-Base in node C]
From
C
C
C
C
C
C
C

To
B1
B2
A1
A2
D1
E1
E2

Path
C,B
C,B
C,B,A
C,E,D,A
A,E,D
A,E
A,B,E

Next-Router
B
B
B
B
E
E
B
77

Path Vector Routing(AS=1)(AS=2)

A

B

To
B1
B2
D1

Path
A,B
A,B
A,D

Next-Router
B
BD(2) Step 2
From
A
A
A
A
A
A
A

B1,B2

D

(1) Step 1
From
A
A
A

A1,A2

To
B1
B2
C1
C2
D1
E1
E2

Path
A,B
A,B
A,B,C
A,B,C
A,D
A,D,E
A,B,E

Next-Router
B
B
B
B
D
D
B

(AS=5)E
D1［ From B］
From
To
B
E1
B
E2
B
C1
B
C2
［ From D］
From
To
D
A1
D
A2
D
E1
D
E2

(AS=4)(AS=3)C C1,C2

E1,E2

Path
B,E
B,E
B,C
B,C

Next-Router
E
E
C
C

Path
D,A
D,A
D,E
D,E

Next-Router
A
A
E
E

78

Path Vector Routing ; IBGP
(AS=2)(AS=1)

Network；
A1,A2,D1

B(AS=3)

A

B1,B2

D

E
(AS=4)C C1,C2F; Inter-AS （EBGP); Intra-AS （IBGP）

Network;
E1,E2,F1（*） IBGP； （A,D） & （E,F）
From B1 to E2 ； ｛AS=2,AS=1,AS=4｝
経路； B → （A → D） → E
From C2 to B2 ； ｛AS=3, AS=4, AS=1, AS=2｝
経路; C → （F → E） → （D → A） → B
79

Supernetting
192.24.0.0/23
R2

R3

Destination
next-hop(1) 192.24.1.122 : R2
(2) 192.24.8.36 : R1

R1
192.24.0.0/20<< Routing table in R3 >>0
1
2
3
Next-hop12345678 90123456 78901234 56789012
192.24.0.0/20 : 11000000.00011000.0000---- -------R1
192.24.0.0/23 : 11000000.00011000.0000000- -------R2
:
:
:
:
:
:
:
:
80

Q. 具体的なネットワークの数と計算処理速度の関係がとくわからなかったので教えていただきたいです。

Q. 具体的なネットワークの数と計算処理速度の関係がとくわからなかったので教えていただきたいです。
➔簡単な計算。 平均パケット長＝20バイト、経路数＝100万(106)、回線速度＝100Gbps(最新は 400Gbpsくらい)だと、、、➔PPS(Packet Per Second) は、100x109/160 = 0.625 x 109➔1.6 nsec の間に、106 エントリーの表を検索!!!!

ちなみに、CPUクロック数を 5GHz=5x109 Hz とすると、0.2 nsec/clockになるので、8 clocks で 106 エントリ
ーの表を検索ということに !!!

Anycast Routing• 同じ ルーティングエントリー(ネットワーク情報)を、インターネット上の別の場所から広告する。
➔ “自動的”に、配送木が分割される。
➔ (1) “自動的”負荷分散、(2) “自動的”障害対策

配送木

Anycast Routing

配送木

Anycast Routing

配送木Anycast Routing を用いて、Load Distribution と Resiliency を実現している

経路制御アーキテクチャのまとめ
1. 状態管理に関する点（戦略）– 「パスの状態」のみを管理するという 戦略• GW(=プロトコル変換)での状態管理 ( O(np) )• セッションごと(=On Demand型)の状態管理 ( O(n2) )※ 「パス」 ≪ 「セッション」 ≪ 「パケット」

2. 大規模化に関する点
i. 階層構造ii. (情報の)集約化

3. システムの持続性（Sustainability）に関する点
i. 分散的な経路計算(Single point of failureの回避)
ii. AS単位での 運用の自律性
iii. データリンク技術からの独立性

ネットワーク レイヤ- IP (Internet Protocol) (1) IP (Internet Protocol)(2) Addressing(3) ARP(4) Routing→ (5) Address Discovery (e.g., DHCP)(6) ICMP/IGMP

87

DHCP
(1) IP Address(i) Automatic allocation(ii) Dynamic allocation ; 貸し出し期間が存在する(iii) Static allocation ； Manual configuration(2) Subnet mask(3) MTU(4) Broadcast Address Flavor(5) Default Gateway(6) Static Routes Lists(*) DNSエントリーへの登録は行われない !
→ Internetからの直接アクセスが必要なHostには Static
allocation を適用すべき。

88

DHCPの課題
1. セキュリティー機能- BOOTPの延長上のプロトコルであり、Security機能を盛りこめない….

2. DNSシステムへの名前の反映- サーバ系ノードにはDHCPが適用できず。
- InternetへのNameの登録が困難…
- 逆引き(IP_Address → host_name)は不可能
ではないが、、、、
正引き(host_name→IP_address)は難しい。
89ネットワーク レイヤ- IP (Internet Protocol) (1) IP (Internet Protocol)(2) Addressing(3) ARP(4) Routing(5) Address Discovery (e.g., BOOTP)→ (6) ICMP/IGMP90

ICMP/IGMP
・ ICMP; Internet Control and Management Protocol- IPの管理・制御- ICMPを利用した重要なアプリケーション(i) ping(ii) traceroute(iii) Router_Discovery
・ IGMP; Internet Group Management Protocol- マルチキャストメンバーの管理

91

ICMP
・Domain Name
Request/Reply(RFRC1788)
・ ICMP redirection

Router discovery(RFC1256)

ホスト
(送信)

ルータ
(中継)
・Traceroute (RFC1393)
・Destination unreachable (RFC191)
・ICMP Source Quench (RFC1016/1018)

ICMP Source Quench (RDC1016/1018)

ホスト
(受信)

92

Dst4
(Alternative Path)

X

Dst2

Dst3
(unreacahble)“Destintion
unreachable..….”(too far)X“TTL expired..….”“echo request/reply”“Redirect”
to better path

Src1

“Source Quench !!!”
Dst1
asking reduce data-speed

93Ping Program
・ Ping 実行時のディスプレイ表示
bsdi% ping svr4
PING svr4 (140.252.13.34): 56 data bytes
64 bytes from 140.252.13.34: icmp_ser=0 ttl=255 time=0 ms
64 bytes from 140.252.13.34: icmp_ser=1 ttl=255 time=0 ms
64 bytes from 140.252.13.34: icmp_ser=2 ttl=255 time=0 ms:::

・ tcpdump 出力
1 0.0
2 0.003733 (0.0037)

bsdi > svr4: icmp : echo request
svr4 > bsdi: icmp : echo reply

3 0.998045 (0.9953)
4 1.001747 (0.0037)

bsdi > svr4: icmp : echo request
svr4 > bsdi: icmp : echo reply

5 1.997818 (0.9961)
6 2.001542 (0.0037)

bsdi > svr4: icmp : echo request
svr4 > bsdi: icmp : echo reply

7 2.997610 (0.9961)
8 3.001311 (0.0037):

bsdi > svr4: icmp : echo request
svr4 > bsdi: icmp : echo reply::

94Ping Program- with IP RR(Record Route) Option・ Ping 実行時のディスプレイ表示
bsdi% ping -R slip
PING slip (140.252.13.65): 56 data bytes
64 bytes from 140.252.13.65: icmp_ser=0 ttl=254 time=280 ms
RR：
bsdi (140.252.13.66)
slip (140.252.13.65)
bsdi (140.252.13.35)
svr4 (140.252.13.34)
64 bytes from 140.252.13.65: icmp_ser=0 ttl=254 time=280 ms (same route)
64 bytes from 140.252.13.65: icmp_ser=0 ttl=254 time=270 ms (same route)：：:・ tcpdump 出力
1 0.0

2 267746 (0.2677)

svr4 > slip: icmp : echo request (ttl 32,
id 35835, optlen=24 RR(39)= RR{#0.0.0.0/
0.0.0.0/0.0.0.0/0.0.0.0/0.0.0.0} EOL)
slip > svr4: icmp : echo reply (ttl 254,
id 1976, optlen=24 RR(39)= RR{#140.252.13.65/
140.252.13.35/#00.0.0/0.0.0.0/0.0.0.0} EOL)
95

Traceroute Program・ traceroute 実行時のディスプレイ表示
bsdi% traceroute nic.ddn.mil
traceroute to nic.ddn.mil (192.112.36.5), 30 hops max, 40 bytes packets
1 netb.tuc.noao.edu (140.252.1.183) 218 ms 227 ms 233 ms
2 gateway.tuc.noao.edu (140.252.1.4) 233 ms 229 ms 204 ms
3 butch.telecom.arizona.edu (140.252.104.2) 204 ms 228 ms 234 ms
4 Gabby.Telecom.Arizona.EDU (128.196.128.1) 234 ms 228 ms 204 ms
5 NSIgate.Telecom.Arizona.EDU (192.80.43.3) 233 ms 228 ms 204 ms
6 JPL1.NSN.NASA.GOV (128.161.88.2) 234 ms 590 ms 252 ms
7 JPL3.NSN.NASA.GOV (192.100.15.3) 238 ms 223 ms 234 ms
8 GSFC3.NSN.NASA.GOV (128.161.3.33) 293 ms 318 ms 324 ms
9 GSFC8.NSN.NASA.GOV (192.100.13.8) 294 ms 318 ms 294 ms
10 SURA2.NSN.NASA.GOV (128.161.166.2) 323 ms 319 ms 294 ms
11 nsn-FIX-pe.sura.net (192.80.214.253) 294 ms 318 ms 324 ms
12 GSI.NSN.NASA.GOV (128.161.252.2) 293 ms 318 ms 324 ms
13 NIC.DDN.MIL (192.112.36.5) 324 ms 321 ms 324 ms(*) -g オプションにより、loose/strict なsource routingを行いながらtracerouteが可能
bsdi% traceroute -g

sh.wide.ad.jp

nic.ddn.mil
96Traceroute Program
・ Ping 実行時のディスプレイ表示
bsdi% traceroute slip
traceroute to slip (140.252.13.65), 30 hops max, 40 bytes packets
1 bsdi (140.252.13.35) 20 ms 10 ms 10 ms
2 slip (140.252.13.65) 120 ms 120 ms 120 ms･ tracerouteの動作原理；→ ICMP time exceed message (type=11,code=0)を利用する。

1. TTL=1 ； On_the-LinkのNext_Hop_Node より先には到達できない。
→ Unreach destination_host due to Time_Exceeded
2. 2度(合計3度) 同一のTTLでICMPパケットの送信
3. TTL ← TTL+1
4. TTL=TTL+1 ; 1_hop先のNodeまでは到達可能になる。
If reachable → Stop
If unreachable{
2度(合計3度)同一のTTLでICMPパケットの送信;
goto step3.;}

97

ネットワーク レイヤ- IP (Internet Protocol) (0) 概要(1) IP (Internet Protocol)(2) Addressing(3) ARP(4) Routing(5) Address Discovery (e.g., DHCP)(6) ICMP
98