集中講義 インターネットテクノロジー 第2回

集中講義

インターネットテクノロジー

第2回

一井信吾

東京大学大学院数理科学研究科

ichii@ms.u-tokyo.ac.jp

昨日の補足：回線交換とパケット交換

音声のディジタル化

8000に区切る（8KHzサンプリング） 1秒 音 圧 レ ベ ル 時間 区切られた各時刻での音圧レベルを 256段階に数値化（8ビット量子化） 83 102 結果：1秒当たり8000×8 = 64000 ビット(64Kbps)

ディジタル信号の伝送

z

メディア上はアナログ（物理学の世界）

z

ディジタル信号は2値(on-off)

z

例

z

電流が流れている／流れていない

z

電圧が高い／低い

z

光が点灯している／点灯していない

z

2値を区別する閾（しきい）値(threshold)が

必要

ディジタル多重化

６４Kbps _{1.5Mbps 45Mbps 1.5Mbps}

６４Kbps _{1.5Mbps 45Mbps 1.5Mbps} ６４Kbps

６４Kbps

時分割多重

(TDM: Time Division Multiplex)

z

1.5Mbps = 24 × 64Kbps

・・・ ・・・ ・・・ 1秒 _{64Kbps × n} 1.5Mbps 1秒を24のslotに分割し、どの通話がどのスロットを使うか ダイヤルしたときに予約する

周波数多重

(FDM: Frequency Division Multiplex)

z

アナログでも多重化はする

z

同軸回線、マイクロ波回線

z

通話に独立の周波数を割り当てる

z

テレビやラジオと同じ

z

光ファイバ時代のFDM → WDM

z

Wavelength Division Multiplex

パケット(packet)交換

z

ディジタル化されたデータをある大きさに区切り

（パケット化）、

z

パケット毎に伝送する

z

制御情報：発信元、送信先、パケットの順序など

１MBのファイル １KBのパケット10個 制御情報を付加

統計多重

６４Kbps _{1.5Mbps 45Mbps 1.5Mbps} ６４Kbps データはいつも流れている わけではないので、 回線交換より多くの通話が 可能

パケットの伝送方式

z

同期式 vs. 非同期式

z

同期式(synchronous)

z

TDM

z

非同期式

z

フレーミング：特定の信号のパターンを検出してパケッ

トの始まりを知る（ハードウェアで行う）

packet パケットの始まりを表す信号 パケットの終わりを示す信号

本日の内容

z

プロトコルとは何か

z

階層構造とプロトコルスタック

z

ルーティング

z

IP

z

ICMP

z

ルーティングプロトコル

プロトコルとは何か

protocol, n.

1.

the customs and regulations dealing with diplomatic

formality, precedence, and etiquette.

2.

an original draft, minute, or record from which a

document, esp. a treaty, is prepared.

3.

a supplementary international agreement.

4.

an agreement between states.

5.

an annex to a treaty giving data relating to it.

6.

Med. the plan for carrying out a scientific study or a

patient’s treatment regimen.

7.

Computers. a set of rules governing the format of

messages that are exchanged between computers.

[orig., a leaf or tag attached to a rolled papyrus manuscript and containing notes as to contents.]

protocolとはなにか

人間protocols:

z

「今何時ですか？」

z

「質問があります」

… 特定のメッセージが送

られる

… メッセージが受け取ら

れると、特定の行為が

行われる

（何も起こらない、もあり）

network protocols:

z

人間ではなくて、機械（コ

ンピュータ）が行う

z

Internet上の通信はすべ

て何らかのprotocolにし

たがって行われる

protocolは、

z

メッセージの形式（format）

z

送受信されるメッセージの順序

z

受信されたメッセージに対応して取

られる action

を定める

プロトコルの階層構造（layer）

ネットワークは複雑なもの z たくさんの「もの」からなる z ホスト z ルータ z リンク z アプリケーション z プロトコル z ハード、ソフト z それぞれ種類も多い z 製造業者 z ソフトのバージョン z 機関（企業、ISP、お客）

問題：

ネットワークの構造を

組織的に

理解するには どうすればよいか？

「複雑さ」こそ

コンピュータサイエンスの宿敵

A physicist, an engineer, and a computer scientist were

discussing the nature of God. ``Surely a Physicist,'' said

the physicist, ``because early in the Creation, God made

Light; and you know, Maxwell's equations, the dual

nature of electromagnetic waves, the relativistic

consequences...'' ``An Engineer!,'' said the engineer,

``because before making Light, God split the Chaos into

Land and Water; it takes a hell of an engineer to handle

that big amount of mud, and orderly separation of solids

from liquids...'' The computer scientist shouted: ``And the

Chaos, where do you think it was coming from, hmm?''

Why layering?

複雑なシステムを取り扱う方法として:

z

構造を明示することによって、システムの構成要素を明

確にし、それらの関係を明らかにすることができる

z

階層的(layered)

参照モデル（reference model)

の

役割

z

構成要素に分割する(modularization)ことによって、シス

テムの保守(maintenance)や改良が容易になる

z

各階層(layer)内部の実現・実装方法をどう変えても

他のlayerには影響しない

z

layering considered harmful?

インターネットのプロトコルスタック

z

アプリケーション：

ネットワークを役立てる

ためのサービスを提供

z

FTP, HTTP (Web), SMTP（メール）

z

トランスポート：

ホスト間のデータ通信サー

ビス

z

TCP, UDP

z

ネットワーク：

データグラム（パケット）を

送信側(src)から受信側(dest)に送り届け

る

z

IP, ICMP, routing protocols

z

リンク：

隣接ノード間のデータ授受

z

PPP, Ethernet

z

物理：

ビットごとの情報を物理的な信号

によって伝送

application

transport

network

link

physical

Layering: 論理的

application transport network link physical application transport network link physical _application transport network link physical application transport network link physical network link physical

各レイヤは

z

分散している

z

各ノード上で各

layerの機能を

実現している

entityがある

z

各entityはしか

るべきactionを

行ったり、同じ立

場にある他の

entity (= peer)と

メッセージを交

換したりする

Layering: 論理的

application transport network link physical application transport network link physical _application transport network link physical application transport network link physical network link physical data data

例：トランスポート

層

z

アプリケーションか

らデータを受け取る

z

アドレス、チェックサ

ムなどを付加し、

datagramを作る

z

作ったdatagramを

peerに送る

z

peerが受信したとい

う返事

(acknowledgement)

を返してくるのを待

つ

z

アナロジー：郵便局

data transport transport ack

Layering: 物理的

application transport network link physical application transport network link physical application transport network link physical application transport network link physical network link physical data data

プロトコルの階層と

データのやりとり

z 送信側(source)

z 各layerは上のlayerからデータを受け取る

z header informationを付加して新しいdata unitを作る z 作ったdata unitを下のlayerに渡す z 受信側(destination) z 逆の動作（下から上へ）

application

transport

network

link

physical

application

transport

network

link

physical

source

_destination

M M M M Ht Ht Hn Ht Hn Hl M M M M Ht Ht Hn Ht Hn Hl message segment datagram frame

Physical & Link layers

z Physical layer

z 有線系

z twisted pairs z coaxial cable z fiber optic cable

z 無線系 z LAN z wide-area z satellite z Link layer z Ethernet z Token Ring z HDLC z PPP

ネットワーク層の役割

z パケットを送信側ホストから受信 側ホストへ送り届ける z ネットワーク層はルータを含むす べての機器に存在 重要な機能３つ： z 経路の決定：srcからdestへのパ ケットの経路を決定する。ルーティ ングアルゴリズムが関係 z スイッチング：パケットをルータの 入り口からしかるべき出口に送り 出す z 「呼」の確立：データの送受信の 前に呼の確立が必要なネットワー クアーキテクチャもある（特に telco系） network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical application transport network data link physical

インターネットの場合：

データグラム方式

z

ネットワーク層で呼の確立は不要

z

ルータはend-to-endの通信に関する情報を持たない

z

ネットワーク層に「ネットワーク接続」の概念なし

z

パケットはdestアドレスによって個別にスイッチされる

z

同一のsrc-destペアをもつ二つのパケットが別の経路を通

ることもある

application transport network data link physical application transport network data link physical

ルーティング

目的：srcからdestへの「良い」経 路（ルータの列）を決定する 経路情報＋アルゴリズム ルーティングプロトコル A E D C B F 2 2 1 3 1 1 2 5 3 5

グラフ理論的取り扱い

z

ノード ⇔ ルータ

z

エッジ ⇔ リンク

z

リンクには｢コスト」が

ある

z

コストの例：遅延、帯

z

「良い」経路とは：

z

コストが最小な経路

z

他の定義も可

ルーティングアルゴリズムの分類

大域的情報を持つかどうか

大域的（global):

z

すべてのルータがネットワーク

全体のリンク情報を持つ

z

“link state”型アルゴリズム

分散的(decentralized):

z

ルータは直結された「隣の」ルー

タとのあいだのリンク情報の

みを持つ

z

「計算＋隣との情報交換」のプ

ロセスを繰り返す

z

“distance vector”型アルゴリ

ズム

静的／動的

静的(static):

z

ネットワーク設計／管理

者が決定

z

経路の変更が少ない場

合に有効

動的(dynamic):

z

経路が頻繁に変動する場

合に有効

z

定期的にupdate

z

link costの変動に対

Link-State型

ルーティングアルゴリズム

ダイクストラのアルゴリズム

z 全ノードがネットワークのトポロ ジとリンクコストの情報を持つ z

“link state”情報のブロー

ドキャストで実現

z

全ノードが同一の情報

を持つ

z あるノード(src)から他の全ノー ド(dest)への最良経路を出力 z

ノードの「ルーティング

テーブル」を与える

z 繰り返し：k回の繰り返しの後、k 個のdestへの最良経路がわか る

記号：

z

c(i,j):

ノードiからノードjへのリ ンクコスト（隣接していない場合 は∞） z

D(v):

srcからdest Vへの経路 のコストの現在の値 z

p(v):

srcからノードvへ向かう 経路の、vに到達するひとつ手 前のノード z

N:

最小コスト経路が見出され たノードの集合

Dijsktra

’s Algorithm

1 Initialization: 2 N = {A}

3 for all nodes v

4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infty 7

8 Loop

9 find w not in N such that D(w) is a minimum 10 add w to N

11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) )

13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N

Dijkstra

’s algorithm: example

Step 0 1 2 3 4 5 start N A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) infinity 2,D D(F),p(F) infinity infinity 4,E 4,E 4,E A E D C B F 2 2 1 3 1 2 5 3 5

“Distance Vector”型

ルーティングアルゴリズム

繰り返し：

z

収束する（ノード間で

情報交換が行われな

くなる）まで

z

「停止信号」はない

非同期的：

z

ノード間の情報交換

は一斉に行われる必

要はない

分散的：

z

各ノードは直接つな

がった隣ノードとのみ

通信

“Distance Table”の構造

z

各ノードにひとつずつ

z

destを行に

z

ノードに直結された隣ノードを

列に

z

例：ノードX上、dest Yに行くに

は隣接ノードZを通る

D (Y,Z)

X distance from X to Y, via Z as next hop c(X,Z) + min {D (Y,w)}Z

w

= =

Distance Table: example

A E _D C B 7 8 1 2 1 2

D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

E cost to destination via

d e s ti n ati o n

D (C,D)

E c(E,D) + min {D (C,w)}D w = = 2+2 = 4

D (A,D)

E c(E,D) + min {D (A,w)}D

w

=

= 2+3 = 5

D (A,B)

E c(E,B) + min {D (A,w)}B

w

=

Distance table gives routing table

D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

E cost to destination via

d es ti n a ti o n

A

B

C

D

A,1

D,5

D,4

D,4

Outgoing link to use, cost d e s tin a ti o n

Routing table

Distance table

Distance Vector Algorithm:

At all nodes, X:

1 Initialization:

2 for all adjacent nodes v:

3 D (*,v) = infty /* the * operator means "for all rows" */ 4 D (v,v) = c(X,v)

5 for all destinations, y

6 send min D (y,w) to each neighbor /* w over all X's neighbors */

X X

X w

Distance Vector Algorithm (cont.):

8 loop

9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11

12 if (c(X,V) changes by d)

13 /* change cost to all dest's via neighbor v by d */ 14 /* note: d could be positive or negative */

15 for all destinations y: D (y,V) = D (y,V) + d 16

17 else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its min DV(Y,w) */ 20 /* call this received new value is "newval" */

21 for the single destination y: D (Y,V) = c(X,V) + newval 22

23 if we have a new min D (Y,w)for any destination Y 24 send new value of min D (Y,w) to all neighbors

w X X X X X w

Distance Vector Algorithm: example

X Z 1 2 7 Y

Distance Vector Algorithm: example

X Z 1 2 7 Y

D (Y,Z)X c(X,Z) + min {D (Y,w)}

w

=

= 7+1 = 8

Z

D (Z,Y)X c(X,Y) + min {D (Z,w)}

w

=

= 2+1 = 3

Distance Vector: link cost changes

Link cost changes:

z node detects local link cost change

z updates distance table (line 15)

z if cost change in least cost path, notify neighbors (lines 23,24) X Z 1 4 50 Y 1 algorithm terminates

“good

news

travels

fast”

Distance Vector: link cost changes

Link cost changes:

z

good news travels fast

z

bad news travels slow

-“count to infinity”

problem!

X Z 1 4 50 Y 60 algorithm continues on!

Distance Vector: poisoned reverse

If Z routes through Y to get to X :

z

Z tells Y its (Z

’s) distance to X is

infinite (so Y won

’t route to X via Z)

z

will this completely solve count to

infinity problem?

X Z 1 4 50 Y 60 algorithm terminates

階層的ルーティング

ここまでの議論での仮定：

z 全ルータは同一 z ネットワークは「フラット」

⇒ 現実のインターネットでは成り立たない！

スケール：

z インターネットのホスト(=dest) 数 > 5,000万 z 各destをすべてルーティングテー ブルに入れきれない z ルーティング情報の交換で帯域 が全部消費されてしまう

管理運営の問題：

z インターネットはネットワークの ネットワーク z 各ネットワークの運営者は自律 的にルーティングを行いたい

階層的ルーティング

z AS内の特別なルータ z AS内の他のルータとの間 でintra-ASルーティングプ ロトコルを動作 z 同時に、AS外へのルーティ ングを行う z

“

inter-AS

“ルーティ

ングプロトコルを他

のボーダルータと

の間で動作させる

ボーダルータ

z

ルータを

“autonomous

systems

” (AS)

と呼ばれ

る集まりにまとめる

z

同一AS内のルータは単

一のルーティングプロトコ

ルを動作させる

z

“

_intra-AS

” ルーティン

グプロトコル

z

ASが異なればルーティ

ングプロトコルも異なっ

てよい

Intra-AS/Inter-ASルーティング

ボーダルータ：

•ボーダルータ間で inter-AS routing •AS内の他のルータ とintra-AS routing inter-AS, intra-AS routing in gateway A.c network layer link layer physical layer a b b a a C A B d A.a A.c C.b B.a c b c

Intra-AS/Inter-ASルーティング

Host h2 a b b a a C A B d _c A.a A.c C.b B.a c b Host h1 Intra-AS routing within AS A Inter-AS routing between A and B Intra-AS routing within AS B

z

インターネットで使われているintra/inter-ASルー

ティングプロトコルについては後述

インターネットのネットワークレイヤ

ルーティング テーブル ルーティングプロトコル •経路選択 •RIP, OSPF, BGP IPプロトコル •アドレスのつけ方 •データグラムのフォーマット •パケットの取り扱い ICMPプロトコル •エラー報告 •ルータに対する「シ グナリング」 トランスポート層: TCP, UDP リンク層 物理層 ネットワーク 層

IP アドレス：基礎

z

IPアドレス：

ホストやルー

タのインターフェイスに

つけられる32-bitの識

別子

z

インターフェイスとは：

ホスト、ルータの物理リ

ンクへの接続点

z

ルータは複数のイン

ターフェイスを持つ

z

ホストも複数のインター

フェイスを持ってよい

z

IPアドレスはインター

フェイス毎につく

_{223.1.1.1 =} 223.1.1.2 223.1.1.3 223.1.1.4 223.1.2.9 223.1.2.2 223.1.2.1 223.1.3.27 223.1.1.1 223.1.3.2 223.1.3.1 11011111 00000001 00000001 00000001

IPアドレス

223.1.1.1 223.1.1.2 223.1.1.3 223.1.1.4 223.1.2.9 223.1.2.2 223.1.2.1 223.1.3.2 223.1.3.1 223.1.3.27 LAN z

IP アドレスの構造：

z

ネットワーク部（上位

ビット）

z

ホスト部（下位ビット）

z

ここでいう｢ネットワーク」

とは？

z

ルータなしで互いに

通信できる（＝同一

のリンクにつながって

いる）インターフェイス

の集まり

z

同一のネットワーク部

を持つ

上の絵には3つのIPネットワークがある

IPアドレス

伝統的な「クラス」

(classfull addressing)

class 1.0.0.0 to 127.255.255.255 A 0network host 128.0.0.0 to 191.255.255.255 B ₁₀ network _host 192.0.0.0 to 223.255.255.255 C 110 network host 224.0.0.0 to 239.255.255.255 1110 multicast address D 32 bits

CIDR

z

“classful addressing”の問題:

z

アドレス空間の無駄遣い

z

例：ホスト2000台のネットワークにはclass Cでは小さす

ぎ、class Bでは大きすぎる（64Kホスト）

z

CIDR: C

lassless

I

nter

D

omain

R

outing

z

ネットワーク部を可変長にする

z

アドレスの書き方：

a.b.c.d/x

, x はネットワーク部の長さ

(in bits)

11001000 00010111 0001000

0 00000000

network part host part

200.23.16.0/23

IPアドレスの割り当て

z 各ホストのネットワーク部は契約毎にISPが持っている”address block”

から割り当ててもらう z ISPはレジストリ（日本ではJPNIC）からaddress blockの割り当てを受 ける ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. …. Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23

階層的アドレスと経路集約

階層的アドレス付けによって、効率的な経路情報の広告(advertisement)が行える “Send me anything with addresses beginning 200.23.16.0/20” 200.23.16.0/23 200.23.18.0/23 200.23.30.0/23 Fly-By-Night-ISP Organization 0 Organization 7 Organization 1

ISPs-R-Us “Send me anything_{with addresses} beginning 199.31.0.0/16” 200.23.20.0/23 Organization 2 .. . .. . _Internet

階層的アドレス：パンチングホール

Organization 1向けの短いマスクの経路情報が別にあると、そちらが優先される “Send me anything with addresses beginning 200.23.16.0/20” 200.23.16.0/23 200.23.18.0/23 200.23.30.0/23 Fly-By-Night-ISP Organization 0 Organization 7 Internet Organization 1

ISPs-R-Us “Send me anything_{with addresses} beginning 199.31.0.0/16 or 200.23.18.0/23” 200.23.20.0/23 Organization 2 .. . .. .

Private Addresses

z

The Internetと(IP layer的に)独立なlocal

networkでのみ使用可

z

RFC1918で規定

z

10.0.0.0 ~ 10.255.255.255 (10/8)

z

172.16.0.0 ~ 172.31.255.255 (172.16/12)

z

192.168.0.0 ~ 192.168.255.255 (192.168/16)

z

NAT (Network Address Translator)や

application gateway (proxy)を介してglobal

Internetとapplication layerでの通信はできる（場

合がある）

IPデータグラムの旅

IPデータグラム

223.1.1.1 223.1.1.2 223.1.1.3 223.1.1.4 223.1.2.9 223.1.2.2 223.1.2.1 223.1.3.2 223.1.3.1 223.1.3.27 A B E misc

fields IP addrsource IP addrdest data

Dest. Net. next router Nhops 223.1.1 1 223.1.2 223.1.1.4 2 223.1.3 223.1.1.4 2

Aのルーティング

テーブル

z

データグラムのフォーマッ

トの詳細は以下で

z

ここではsrc/dest IP

addrフィールドだけに着

目

IPデータグラムの旅

223.1.1.1 223.1.1.2 223.1.1.3 223.1.1.4 223.1.2.9 223.1.2.2 223.1.2.1 223.1.3.2 223.1.3.1 223.1.3.27 A B E

Dest. Net. next router Nhops 223.1.1 1 223.1.2 223.1.1.4 2 223.1.3 223.1.1.4 2 misc fields 223.1.1.1 223.1.1.3 data

AからBあてのIPデータグラ

ムの配送

z

Bのネットワークアドレスを見

る

z

BはAと同一ネットワークにあ

る

z

AはBへリンクレイヤの機能を

使って直接データグラムを送

信

IPデータグラムの旅

misc fields 223.1.1.1 223.1.2.3 data 223.1.1.1 223.1.1.2 223.1.1.3 223.1.1.4 223.1.2.9 223.1.2.2 223.1.2.1 223.1.3.2 223.1.3.1 223.1.3.27 A B E

Dest. Net. next router Nhops 223.1.1 1 223.1.2 223.1.1.4 2 223.1.3 223.1.1.4 2

AからEへ

z Eのネットワークアドレスを見る z EはAと違うネットワークにあるこ とがわかる z ルーティングテーブルを引く：E向 けnext hopは223.1.1.4 z Aはルータ223.1.1.4に送る z データグラムが223.1.1.4に到着 z 続く...

IPデータグラムの旅

223.1.1.1 223.1.1.2 223.1.1.3 223.1.1.4 223.1.2.9 223.1.2.2 223.1.2.1 223.1.3.2 223.1.3.1 223.1.3.27 A B E

network router Nhops interface 223.1.1 - 1 223.1.1.4 223.1.2 - 1 223.1.2.9 223.1.3 - 1 223.1.3.27 Dest. next misc fields 223.1.1.1 223.1.2.3 data

223.1.4に223.1.2.2向け

データグラムが到着

z Eのネットワークアドレスを見る z Eはルータのインターフェイス 223.1.2.9と同一ネットワーク上に ある z 223.1.2.9から223.1.2.2へリンク レイヤで送る z 223.1.2.2に到着（めでたしめでた し）

IPデータグラムのフォーマット

ver _length data (variable length, typically a TCP or UDP segment) 16-bit identifier Internet checksum time to live

32 bit source IP address 残りホップ数 （ルータを超える毎に1減る 0になると廃棄） fragmentation/ reassembly用 データグラムの長さ (bytes) 上位レイヤプロトコル head.

len type ofservice

データのタイプ _{flgs fragment} offset upper

layer

32 bit destination IP address Options (if any)

32 bits バージョン番号(4) ヘッダ長(bytes) timestamp, record route taken, source routing等

RFC791

RFC: 791

INTERNET PROTOCOL DARPA INTERNET PROGRAM PROTOCOL SPECIFICATION

September 1981 prepared for

Defense Advanced Research Projects Agency Information Processing Techniques Office

1400 Wilson Boulevard Arlington, Virginia 22209

by

Information Sciences Institute University of Southern California

4676 Admiralty Way

RFC791でのIPヘッダの表現

3.1. Internet Header Format

A summary of the contents of the internet header follows:

0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| IHL |Type of Service| Total Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identification |Flags| Fragment Offset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time to Live | Protocol | Header Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Options | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

IP Fragmentation & Reassembly

z リンクには最大フレーム長

MTU (max.transfer size)が定 義されている z

リンクの種類毎にMTU

も異なる

z MTUより大きなIPデータグラム は分割(“fragment”)される z

再構成(

“reassemble”)

はdestに到着したときの

みおこなわれる

z

IPヘッダ中にfragmentさ

れたデータグラムを識別

するフィールド、順序を

fragmentation:

in: one large datagram

out: 3 smaller datagrams

IP Fragmentation and Reassembly

ID =x fragflag₌₀ offset₌₀ length =4000 ID =x fragflag₌₁ offset₌₀ length =1500 ID =x fragflag=1 offset=1480 length =1500 ID =x fragflag=0 offset=2960 length =1040 大きなIPデータグラムがいくつかの小さな データグラムにfragmentされる

ICMP: Internet Control Message Protocol

z ネットワーク層の情報を伝える

ために用いられる

z

エラー：unreachable

host, network, port,

protocol

z

調査：echo

request/reply (ping)

z

IPデータグラムで送られ

る

z タイプ＋コードで区別

Type Code description

0 0 echo reply (ping)

3 0 dest. network unreachable 3 1 dest host unreachable

3 2 dest protocol unreachable 3 3 dest port unreachable 3 6 dest network unknown 3 7 dest host unknown

4 0 source quench (congestion control - not used)

8 0 echo request (ping) 9 0 route advertisement 10 0 router discovery 11 0 TTL expired 12 0 bad IP header

Intra-ASルーティング

z

Interior Gateway Protocols (IGP)

とも

z

よくつかわれているIGPs:

z

RIP: Routing Information Protocol

z

OSPF: Open Shortest Path First

z

IS-IS: Intermediate System

– Intermediate

System (from OSI)

z

IGRP: Interior Gateway Routing Protocol

RIP ( Routing Information Protocol)

z

Distance vector型

z

BSD-UNIX (routed)

z

メトリック： ホップ数(max = 15 hops)

z

Distance vectors: 30秒ごとにResponse

Messageにより交換(advertisement)

z

各advertisementには25dest netsまでの情

OSPF (Open Shortest Path First)

z

Link State型

z

Advertisementsは AS 全体に送信される(via

flooding)

z

複数の同一コストの経路が可能（負荷分散）

z

階層的構成が可能

inter-ASルーティングプロトコル：BGP

z

BGP (Border Gateway Protocol):

the de facto

standard

z

Path Vector

型:

z

Distance Vector型に似ている

z

各Border Gatewayは隣のpeers にAS pathを

送る

z

例：Gateway Xから dest ZへのAS path

Path (X,Z) = X,Y1,Y2,Y3,

…,Z

参考文献

z

RFC

z RFC791, “INTERNET PROTOCOL”, 1981.

z RFC792, “INTERNET CONTROL MESSAGE PROTOCOL”,

1981.

z RFC1058, “Routing Information Protocol”, 1988.

z RFC1723, “RIP Version 2 --- Carrying Additional Information”,

1994.

z RFC2328, “OSPF Version 2”, 1998.

z RFC1771, “A Border Gateway Protocol 4 (BGP-4)”, 1995.

z _{RFC1772, “Application of the Border Gateway Protocol in the}

Internet”, 1995.

参考文献

z

ネットワーク技術全般

z A. Tanenbaum, Computer Networks, 3rd ed. (Prentice-Hall,

1996)

z James F. Kurose & Keith W. Ross, Computer Networking --- A

Top-Down Approach Featuring the Internet (Addison-Wesley,

2001) z スライドをこの本のWebページから借用しています z

TCP/IP入門

z 竹下隆史／村山公保／荒井 透／苅田幸雄、

マスタリング

TCP/IP

入門編

第3版（オーム社、2002） z 若林 宏、

図解標準 最新

TCP/IP

ハンドブック 

（秀和システム、 2002） z

講座

z 岩波講座インターネット（全5巻）

参考文献

z

TCP/IPの定本

z D. Comer, Internetworking with TCP/IP, Vol. 1

：

Principles,

protocols, and architecture, 4th _{ed. (Prentice-Hall, 2000)} z W. R. Stevens, TCP/IP Illustrated, Vol. 1: The Protocols

(Addison-Wesley, 1994)

z

ルーティング

z _{R. Perlman, Interconnections: Bridges, Routers, Switches,}

and Internetworking Protocols, 2nd _{ed. (Addison-Wesley, 1999)} z _{J. Moy, OSPF: Anatomy of An Internet Routing Protocol}

(Addison-Wesley, 1998)

z _{J. Stewart, BGP4: Interdomain Routing in the Internet}

課題

z

Link state, distance vectorのルーティング

アルゴリズムがちゃんと動くことを確かめて

おくこと（証明しなくてもよい）