ＩＰ層、ＴＣＰ層

分散システム

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/dsys-1997/1998-01-27
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■復習

■TCP/IP

◆ストリーム

TCP/IPは、信頼性のある（reliable）双方向のストリーム転送サービス （stream transport service）を提供する通信プロトコルである（図１）。ス トリームとは、通信する２つのプロセス間に結合(connection，通信路)が形成 され、複数回に分けて送り出したデータでも順番が入れ替わらないがデータの 区切りがわからなくなるような転送サービスである。UNIXのパイプは、双方向 ではなく単方向であるが、同じストリームに分類される転送サービスを提供す るものである。

図１　TCP/IPによりより提供されるストリーム
図１　TCP/IPによりより提供されるストリーム

なお、Ｃ言語のライブラリ関数である fopen(), fgets(), fputs() なども、 ストリームと呼ばれることがある。これは、もともとランダム・アクセス可能 で、メモリ中の配列と同じようにアクセスするすることもできるファイルを、 まるでプロセス間通信のストリームと同じように扱うことができることに由来 する。ストリームの元の意味は、プロセス間通信である。

◆層（プロトコル・スタック）

TCP/IPによる通信では、図２に示すように、４つのプロトコル（規約、約束事） の層が使われる。TCP/IP自身は、TCP層と IP層という２つのプロトコルに分解 される。このようにさまざまなプロトコルが決められ、全体として層をなして いる。この様子を、プロトコル・スタックと呼ぶ。

図２　TCP/IPにおけるプロトコル・スタック

図２　TCP/IPにおけるプロトコル・スタック

TCP は、IP という通信プロトコルを利用して実現されている。IPは、（信頼 性がない）データグラム（datagram）転送サービスを提供する通信プロトコル である。データグラムでは、データの送り手と受けての間に結合（通信路）が 形成されず、送出したデータの順番が途中で変ることや送出したデータが失わ れることがある。データグラムは、書留めではない郵便に似ている。IPのデー タグラムが配達されるときに使われる番号が、IPアドレスである。IPアドレス としては、現在32ビットの整数が使われている。

TCP層の上には、応用層が定義されている。この層では、ftp, rlogin, WWW, mnews,sendmail などの、TCP/IP を利用するプログラムの間の会話の方法が定 義される。TCP/IPを使った通信は、まるでプロセス同士が電話で会話するよう に進められる。普通の電話では、日本語を話す人と英語を話す人は、電話で情 報交換を行うことができない。同様に、同じTCP/IPを使っていても、会話の方 法が違うと、まったく情報交換を行うことができない。ゆえに、TCP/IPの上に さらに、情報交換のためにさまざまなプロトコルが取り決められている。

TCP/IPの上に構築されているプロトコルの例を、表１に示す。ポート番号につ いては、後述する。

表１　TCP/IPの上に構築されているプロトコルの例

--------------------------------------------------------------------
ポート番号	プロトコルの名前	目的
--------------------------------------------------------------------
21	FTP(File Transfer Protocol)		ファイル転送
23	Telnet					遠隔ログイン(telnet)
25	SMTP(Simple Mail Transfer Protocol)	電子メールの転送
79	finger					fingerコマンド
80	HTTP(HyperText Transfer Protocol)	WWWのデータ転送
119	NNTP(Network News Transfer Protocol)	ネットワーク・ニュース
						の記事の転送
513	login	遠隔ログイン(rlogin)
--------------------------------------------------------------------

IPのデータグラムを転送するためには、さまざまな物理的な媒体が使われる。 現在LANでは、イーサネットやFDDIがよく使われいる。イーサネットは、同軸 ケーブルやより対線(Twisted Pair Cable)を使ってデータを転送する。FDDIは、 光ケーブルを使っている。モデムなどを使ったシリアル回線では、PPP(Point to Point Protocol)というプロトコルの上に、IPデータグラムが流される。

データグラムは、ネットワーク通信では、最も基本的な転送サービスである。 IP上に構築された UDP（User Datagram Protocol）も、IPとほとんど同じ機能 を提供する。また、イーサネットやFDDIが提供する転送サービスも、データグ ラムである。

◆ホストとルータ

ネットワークに接続されている計算機の中で、ネットワークに１ヵ所の出入り 口（インタフェース）を持っているものは、ホストと呼ばれる。２ヵ所以上の 出入り口を持っている計算機は、ルータと呼ばれる。ルータは、ネットワーク とネットワークを接続するための計算機である。ルータは、入ってきたIPのパ ケットのIPアドレスを見て、どのネットワークに送ればよいかを判断する。

図１で、左端と右端にあり、４層全てそろっている部分がホストである。 TCP/IPの通信は、ホストとホストの間で行われる。中央の、２層しかない部分 は、ルータである。ルータの仕事は、IP層において行われる。

◆仮想回線

TCP/IP では、プロセスとプロセスが、電話で会話をするように通信が行われ る。普通の電話で人間同士が話をするには、まず電話番号を指定して、話相手 に電話をとってもらわなければならない。TCP/IP においても同様である。 TCP/IPでは、電話を掛ける方をクライアント・プロセス、電話を待つ方をサー バ・プロセスと言いう。

TCP/IPにおいて、プロセス間に形成されたストリーム通信路のことを、計算機 間に張られた物理的な回線に似ていることから、仮想的回線(virtual circuit)とも言う。TCP/IP では、回線を接続する段階では、クライアント・ プロセスとサーバ・プロセスは非対称である。一度仮想回線が接続された後は、 両方のプロセスは、TCP/IPのレベルでは、まったく対称的になる。

TCP/IPにおいてプロセス間に仮想回線を開設するには、IPアドレスとポート番 号が必要である。ポート番号は、同じIPアドレスを持つホスト上で動いている プロセスを区別するために使われる。

以下に、通信路が開設される手順を示す。

  1. サーバ・プロセスがポート番号を指定して、接続要求受付用ポートを作る。 サーバ・プロセスは、クライアント・プロセスからの接続要求を待つ（図３ （ａ））。（注意：要求受付用ポートでは、データの送受信はできない。）
  2. クライアント・プロセスが通信用ポートを作る。このポートを、サーバ・ プロセスが動いているホストのＩＰアドレスと、サーバ・プロセスが作った接 続要求受付用ポートのポート番号を使って、接続要求を行う（図３（ｂ））。
  3. 接続要求が受け付けられると、サーバ・プロセスには、新たに通信用ポー トが作られる（図３（ｃ））。これは、特定のクライアントとの通信のために 使われる。

こうして一度通信路が開設されると、クライアントとサーバは、どちらからで もデータを送り始めることができる。

図３（ａ）　TCP/IP通信路の開設（１）

図３（ａ）　TCP/IP通信路の開設（１）

図３（ｂ）　TCP/IP通信路の開設（２）

図３（ｂ）　TCP/IP通信路の開設（２）

図３（ｃ）　TCP/IP通信路の開設（３）

図３（ｃ）　TCP/IP通信路の開設（３）

TCP/IPにおける通信路開設において、クライアントは、サーバ側の接続要求受 付用ポートのポート番号を、事前に知っている必要がある。表１に、いくつか の応用層のプロトコルについて、公に利用目的が決められているポート番号を 示す。1024以上のポート番号は、特に利用目的が決められていない。よって、 利用されていなければ、利用者が自由に使ってもよい。

クライアント側の通信用ポートのポート番号は、通常は、オペレーティング・ システムにより自動的に割り当てられる。サーバ側の通信用ポートのポート番 号も、同様である。

◆プロセス間通信におけるクライアント・サーバ・モデル

プロセス間通信は、本来自由に行うことができる。どのプロセスも自由にメッ セージを送信する権利がある。プロセス間通信におけるクライアント・サーバ・ モデルは、本来対称的なプロセスを最初にメッセージを送る方（クライアント・ プロセス）と受ける方（サーバ・プロセス）に分類することで、プロセス間通 信を構造化し、わかりやすくするものである。TCP/IPの通信路開設時における クライアントとサーバの役割は、このプロセス間通信におけるクライアント・ サーバ・モデルの１つの例になっている。

プロセス間通信におけるクライアント・サーバ・モデルにおける意味の他に、 クライアントとサーバという言葉は、サービスを受けるプロセスとサービスを 提供するプロセスの意味で使われることがある。インターネットにおけるプロ セス間通信では、多くの場合、サービスの授受の関係におけるクライアントと サーバと、プロセス間通信におけるクライアントとサーバが一致している（稀 に一致していないこともあるので、注意しなさい）。

◆ソケット

UNIX オペレーティング・システム上で動作するプログラムがTCP/IPの機能を 使う場合、UNIXオペレーティング・システムが提供するソケットというインタ フェースを通じて利用することになる。ソケットは、TCP/IP をはじめとして、 XNS, OSI などさまざまな通信プロトコルを UNIX オペレーティング・システ ム上で使うために設計されたものである。TCP/IP だけを考えると、ソケット のインタフェースは、繁雑であり、使いにくくなっている。

UNIXでは、ソケットをドメイン（Address Family）と型で区別する。 下の表は、socket() システム・コールに与えるドメインと型である。 

----------------------------------------------------------------------
ドメイン　型		option	プロトコル
----------------------------------------------------------------------
AF_INET	SOCK_STREAM	0	TCP
AF_INET	SOCK_DGRAM	0	UDP
AF_INET	SOCK_RAW	?	IP
AF_INET	SOCK_RAW	?	ICMP
AF_UNIX	SOCK_STREAM	0	(UNIXドメインのストリーム)
AF_UNIX	SOCK_DGRAM	0	(UNIXドメインのデータグラム)
AF_NS	SOCK_SEQPACKET	?	XEROX NS protocol の順序付きパケット
AF_NS	SOCK_RDM	?	XEROX NS protocol の信頼性のあるデータグラム
----------------------------------------------------------------------
これ以外の組み合わせ、使えない。たとえば、AF_INETとSOCK_SEQPACKET を socket システム・コールで指定しても、うまくいかない。

◆DNS(Domain Name Service)

TCP/IPによる通信は、通信相手のIPアドレス（32ビットの整数）とポート番号 （16ビットの整数）さえわかれば、可能である。IPアドレスやポート番号は、 計算機にとって扱いやすいものであるが、人間にとって扱いやすいものではな い。人間にとってわかりやすい記号の名前から、IPアドレスに変換するサービ スがあれば便利である。このサービスを、名前サービス、それを行うプログラ ムを名前サーバという。

インターネットにおける名前サービスは、名前空間をドメイン（領域）に分割 して、階層的に管理することで実現されている。これを、ドメイン・ネーム・ サービス（Domain Name Service, DNS）という。DNSという言葉は、名前サー ビスを提供するプログラム（名前サーバ, Domain Name Server）を意味するこ ともある。

DNSでは、主に名前をIPアドレスへ変換するサービスが使われている。その他 に、名前から電子メールの配送先、名前から名前サーバが動いているホストの 名前、名前から名前サーバ自身の管理情報、逆にIPアドレスから名前を引くた めにも使われる。

■物理層とデータリンク層(IP層の下)

イーサネット(Ethernet)

LANでは、イーサネットがよく使われている。イーサネットは、IPと同じ くデータグラム・サービスを提供する。電気信号を伝える媒体としては、同軸 ケーブル、より対線(Twisted Pair)が使われる。

ARP(Address Resolution Protocol)

ARPは、イーサネットによるLANで、あるIPアドレスを持っているホス トのイーサネット・アドレスを探すためのプロトコルである。イーサネット上 に、探しているIPアドレスを含むパケットを放送する。IPアドレスを知っ ているホスト(普通は、自分自身)は、それに応答する。詳しくは、教科書 218ページを参照しなさい。

FDDI

PPP

■ＩＰ層(Internet Protocol)

IPは、転送サービスとして、(信頼性がない)データグラム転送サービスを提供 する。IP層は、OSI参照モデルのネットワーク層に相当する。

IPデータグラムの形式


Example 2:

  In this example, we show first a moderate size internet datagram (452
  data octets), then two internet fragments that might result from the
  fragmentation of this datagram if the maximum sized transmission
  allowed were 280 octets.


    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 
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Ver= 4 |IHL= 5 |Type of Service|       Total Length = 472      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Identification = 111      |Flg=0|     Fragment Offset = 0 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Time = 123  | Protocol = 6  |        header checksum        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         source address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      destination address                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             data                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             data                              |
   \                                                               \
   \                                                               \
   |                             data                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             data              |                                
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                                

                       Example Internet Datagram

                               Figure 6.
Ver
バージョン。IPv4。次は、IPv6。
IHL
ヘッダ長
TTL (time to live)
データグラムがネットワーク上に存在することができる時間。
Protocol
6 が TCP、17が UDP。
参照:rfc791.txt

ルーティング(routing, 経路選択)

パケット交換システムにおいて、経路制御（routing）とは、パケットを送る ために経路を選択する過程のことである。経路制御を行う計算機を、ルータ （router, ラオタと書く人もいる）という。TCP/IPでは、IP層で経路制御を行 う。IP層では、主に送り先のIPアドレスを見て、経路制御を行う。

テーブル駆動式経路制御

IPの経路制御アルゴリズムとしてよく使われているものは、経路制御表 （routing table）を使うものである。経路制御表は、到達可能な終点につい ての情報とその終点に到達する方法を蓄えている。

直接配送と間接配送

経路制御の形式は、おおきく直接配送と間接配送に分類される。直接配送では、 イーサネットやＦＤＤＩなどの物理転送システムを使ってパケットを送り届け る方法である。直接配送では、２つのホストの間には、ルータは介在しない。 間接配送とは、終点が同じネットワークに接続していない時にルータを経由し て配送されることである。

情報学類周辺のネットワーク接続状況

図 情報学類周辺の接続状況

図 情報学類周辺の接続状況

ルーティング・テーブル: 

adonis2




----------------------------------------------------------------------
% netstat -rn [←]
Routing tables
Destination      Gateway            Flags     Refs     Use  Interface
127.0.0.1        127.0.0.1          UH          0  4377339  lo0
default          130.158.87.1       UG         58  3328602  lan0
130.158.87       130.158.87.2       U           3 46169245  lan0
% ifconfig lan0 [←]
lan0: flags=63
        inet 130.158.87.2 netmask ffffffe0 broadcast 130.158.87.31
% []
----------------------------------------------------------------------







adonis1:




----------------------------------------------------------------------
% netstat -rn [←]
Routing tables
Destination      Gateway            Flags     Refs     Use  Interface
127.0.0.1        127.0.0.1          UH          0   242076  lo0
130.158.87.192   130.158.86.232     UG          0   130362  lan1
130.158.87.160   130.158.86.246     UG          0  4836059  lan1
130.158.87.128   130.158.86.245     UG          0  5094919  lan1
130.158.87.96    130.158.86.244     UG          0  1809467  lan1
130.158.87.64    130.158.86.243     UG          0  2323776  lan1
130.158.87.32    130.158.86.242     UG          0  2814236  lan1
default          130.158.86.254     UG          7 14490946  lan1
130.158.86.224   130.158.86.241     U           1 17427572  lan1
130.158.87       130.158.87.1       U           1 54176388  lan0
% ifconfig lan0 [←]
lan0: flags=63
        inet 130.158.87.1 netmask ffffffe0 broadcast 130.158.87.31
adonis1[~] 105% ifconfig lan1
lan1: flags=63
        inet 130.158.86.241 netmask ffffffe0 broadcast 130.158.86.255
%
----------------------------------------------------------------------
ルーティング・テーブルには、ホスト用とネットワーク用の２種類 があります。上の Flags の部分で、H と表示されているものが ホスト用、そうでないものがネットワーク用です。

Destination は、ホスト用の場合、パケットの最終目的地（ホスト） のＩＰアドレスそのもの、ネットワーク用の場合、最終目的地の ＩＰアドレスのネットワーク部を表しています。Gateway は、実際 にパケットを送るルータ（ゲートウエー）のＩＰアドレス、Refcnt (Reference count) は、これを利用して確立されているＴＣＰ／Ｉ Ｐの結合（コネクション）の数です。Useは、このエントリの利用 回数、Interface は、インタフェース名を表しています。

netstat -rn flags

H
Host
G
Gateway
U
UP
D
Dynamic (icmp redirect)
G
Gateway

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

表を検索して見つかったエントリを使う
  1. ホスト用テーブルを調べる
  2. ネットワーク用テーブルを調べる
  3. default を使う

経路制御表は、全てのホストのアドレスについての情報を含んでいるのではな く、ある物理ネットワークに含まれているホストに共通のプレフィクス（アド レスの共通部分）だけを含んでいる。この共通部分のことを、ＩＰアドレスの ネットワーク・アドレスという。これにより、情報隠蔽が実現され、経路制御 表の大きさを小さく保ち、経路制御の判断が効率的になる。

デフォルト経路（default route）

情報隠蔽を行い経路制御表を小さくするためにの技術の１つとして、複数のエ ントリを１つのデフォルトケース（default case）に統合する方法がある。 この方法では、経路制御ルーチンは、表に経路が登録されていなかった場合に デフォルトのルータへ送る。

IPアドレスのクラス

IPアドレスからネットワーク・アドレスを取り出すために使うビットパタンを ネットマスク（netmask）という。情報学類のＬＡＮでは、ネットマスクと しては、0xffffff00 と 0xffffffe0 が用いられている。

従来、ネットマスクは、IPアドレスのクラスにより固定されていた。IPアドレ スには、次の５つのクラスが定義されていた。 

----------------------------------------------------------------------
クラス	上位ビット	ネットマスク
----------------------------------------------------------------------
A	0		0xff000000
B	10		0xffff0000
C	110		0xffffff00
D	1110		-		マルチキャスト用
E	11110		-		予約
----------------------------------------------------------------------

筑波大学へは、クラスＢのアドレス(130.158)が割り当てられている。クラスＢ では、16ビットのネットワーク部と16ビットのホスト部を持つことになる。よっ て、大学内に65536台までホストを設置することができる。

サブネットとスーパーネット

現在では、クラスに固定されてる以外のネットマスクが使われる局面が多くなっ ている。たとえばクラスＢのアドレスを割り当てられた組織は、そのまま使う のではネットワークが大きすぎて問題がある。そこであるクラスのＩＰアドレ スの空間ををいくつかに分割して使う方法が考え出された。これがサブネット （subnet）の考え方である。

サブネットでは１つのおおきなアドレス空間を分割して利用していた。これと は逆に、複数の空間を融合して使うことも考えられる。これは、スーパーネッ トと呼ばれている。現在、クラスＢのアドレスが不足してきている。会社の組 織の大きさによっては、クラスＢでは大きすぎる、クラスＣでは小さすぎると いうことが多い。この問題を解決するたに、クラスＣのアドレスを複数連結し て割り当てることが行われている。

traceroute


adonis2:
----------------------------------------------------------------------
% traceroute www.tsukuba.ac.jp [←]
traceroute to hagi.cc.tsukuba.ac.jp (130.158.70.50) from 0.0.0.0, 30
hops max, 2
0 byte packets
 1  adonis1 (130.158.87.1)  9 ms  2 ms  2 ms
 2  route-86 (130.158.86.254)  5 ms  5 ms  5 ms
 3  RD01.cc.tsukuba.ac.jp (130.158.1.80)  5 ms  6 ms  6 ms
 4  hagi.cc.tsukuba.ac.jp (130.158.70.50)  6 ms *  5 ms
%
----------------------------------------------------------------------

◆ルーティング・テーブルを書き換えよう

ルーティング・テーブルは、route コマンド、routed 、 ICMP Redirectメッセージによって書き換えられます。

(1) route コマンド

次のような形式で使います。 



----------------------------------------------------------------------
% /usr/etc/route add host 最終目的地 送り先 ホップ数 [←]
% /usr/etc/route add net  最終目的地 送り先 ホップ数 [←]
----------------------------------------------------------------------
add は、エントリを追加することを意味します。delete とすると、 そのエントリを削除します。次に、最終目的地のホスト名、または、 ネットワーク名を指定します。ＩＰアドレスを直接書いてもかまい ません。ホップ数とは、最終目的地に到達するまで、何個のホスト （ゲートウエー）を通過するかを表している数です。数字が小さい ほど優先順位が高いことを意味します。直接繋がっている場合は、 0 になります。

(2) routed (route daemon)

routed は、外のホスト上で動いている routed と通信して、自動 的にルーティング・テーブルを設定するデーモンです。routed は、 RIP (Routing Information Protocol) というプロトコルを使って、 ホップ数を放送します。ゲートウエー上の routed は、定期的に自 分自身のルーティング・テーブルを放送します。外のホスト上の routed は、その放送された情報をもとに、外のネットワークやホ ストへのホップ数を計算します。そして、現在の自分自身のホスト のルーティング・テーブルに記録されているものよりも、小さいホッ プ数のルート（route,経路）を発見した場合、ルーティング・テー ブルを書き換えます。

routed (RIP) を使ったルーティングでは、回線の速度に関係なく、 ホップ数が小さい経路が使われます。たとえば、ホップ数が大きく 速い回線があったとしても、ホップ数が小さく遅い回線のルートが 使われます。この問題を回避するために、遅い回線のホップ数を、 人為的に大きくすることがあります。

routed は、カリフォルニア大学バークレー校で開発され、4.3BSD に付属していたので、広く利用されています。その外に、Cornel 大学で開発された gated (gate daemon)というプログラムも使われ ています。gated では、RIP の外に HELLO というプロトコルを使っ て、ルーティングのための情報を交換します。HELLO では、RIP で 使われていたホップ数の代わりに、遅延（時間）を使います。 gated では、ルーティングのための情報を交換するホストを制限す る機能があります。

(3) ICMP Redirect

route コマンドも、routed も、カーネルの外からの指令でルーティ ング・テーブルを書き換えるものでした。これに対して、カーネル が、ネットワークから ICMP Redirect というメッセージを受け取 る事で、ルーティング・テーブルを書き換えることもあります。

ICMP Redirect メッセージは、 ルータが、受け取ったパケットを、再び同じインタフェー スから送りだす時に、このメッセージをパケットの送り手に送りま す。これは、同じネットワークにもっと相応しいルータ（または、 最終目的地のホストそのもの）がつながっているにもかかわらず、 そのルータを経由してパケットを送ろうとしたことを意味していま す。ルータから ICMP Redirect を受け取ったホストは、メッセー ジに従ってルーティング・テーブルを書き換えます。

この機能は、ルータが万能であり、その外のホストは、ルータの教 えに従うという戦略を使う時に適しています。たとえば、ルータで はないホストは、自分が知らないネットワークが現れた時には、 default を使ってルータに送ります。ルータは、そのパケットを中 継すると同時に、必要ならば、ICMP Redirect メッセージを送り返 します。最初にパケットをルータに送ったホストは、ルーティング・ テーブルを書き換えて（学習）、これ以降、その無駄なパケットの 中継が行われなくなります。

分散システムとしてのＩＰ層

分散システムの設計目標 （集中）アルゴリズム:（集中）システムで問題を解くための指令の集まり。 分散アルゴリズム: 要素間のメッセージの伝達の方法の集まり IP層

■経路制御情報の交換

経路制御表の要素が少ないうちは、人手で入れることも可能である。この方法 は、静的経路制御と呼ばれている。しかし人手でやる方法は、ネットワークの 急激な拡張や急速な変化に付いていくことができない。

そこで、自動的に経路制御表を作る方法が必要になる。このためには、ルータ はどのようなホストやネットワークが自分のネットワーク、あるいは隣のネッ トワークに接続されているかを互いに交換する必要がある。このようなネット ワークの接続状況を表わす情報を経路情報という。経路情報を交換して、刻々 と変化するネットワークの状況に合わせて経路制御を行うことを動的経路制御 という。

自律システム

経路情報の交換方法には、自律システム内部と自律システム間の２つの方法が ある。インターネットにおける自律システム（autonomous system）とは、経 路制御のために、単一の管理権限により制御されるネットワークとルータの集 合である。自律システムは、経路領域（routing domain）と呼ばれることもあ る。

ＥＧＰ（外部経路制御プロトコル）

１つの自律システムの内部では、内部の経路制御の方法を自由に選ぶことがで きる（実際には、静的経路制御や後述するＲＩＰ、ＯＳＰＦなどが使われる）。 異なる自律システムに属するルータは、ＥＧＰ（exterior gateway protocol） と呼ばれるプロトコルを用いて、経路情報を交換する。

ＥＧＰでは、主に次の４種類のメッセージが使われる。

  1. 近傍獲得（neighbor acquisition）。異なる自律システムに属するルータ 間で互いに経路情報を交換することに合意するために送る。
  2. 到達可能性。定期的に相手のルータが動作しているかどうかを確認する。
  3. 呼出し要求と応答。経路情報（ネットワークの到達可能性情報）を交換する。
  4. 経路制御更新。自分が持っている経路情報が変更されたことを相手に知ら せる。
ＥＧＰの問題点としては、交換すべき経路情報が大きいこと、全体のトポロジ が木構造になってしまうことがあげられる。

rfc904.txt

ＩＧＰ（内部経路制御プロトコル）

自律システム内で経路情報を交換するためのプロトコルをＩＧＰ（interior gateway protocol）と呼ばれる。自律ノード間で使われるＥＧＰが具体的なプ ロトコルであったのに対して、ＩＧＰは、あらゆるアルゴリズムについて言及 する総称的な言葉である。ＩＧＰの例としては、ＲＩＰ、ＨＥＬＬＯ、 ＯＳＰＦがある。

RIP

RIP (Routing Information Protocol)は、バークレー版UNIXに付属している routed というプログラムが利用しているＩＧＰの１つである。RIPでは、ベク トル距離経路制御（vector-distance routing）を実現している。RIP では、 ベクトル距離として、ホップ数を使っている。ホップ数とは、いくつルータを 経由するかを表わす数である。RIP では、各ルータは自分が属している自律シ ステム内のネットワークへの経路を（結果として）知っていなければならない。

ベクトル距離経路制御アルゴリズム

  1. 各ルータは、起動時に最初に自分が直接接続しているネットワークに関す る経路情報を保持する。直接接続しているネットワークへの距離は、０である。
  2. 各ルータは、定期的に経路制御表のコピーを直接到達できる他のルータす べてに報告する。
  3. ある報告がルータＪが、ルータＫに到着したとする。このときＫは、報告 された終点の集合とそれに対する距離を調べ、次のような場合自分の経路制御 表を更新する。 ここでルータＪがあるネットワークへの距離をＮとしてルータＫに報告すると、 ルータＫは、そのネットワークへの距離をＮ＋１として経路制御表に登録する。
ベクトル距離経路制御の利点 ベクトル距離経路制御の問題点 切れた瞬間に、距離を無限（１６）にする。 回りに広告する前に、別のルータからの情報が着てしまう。

地平線分割式更新(split horizon update)。 どこから情報を受け取ったかを覚えておき、 逆流させない。

poison reverse。一度接続がなくなると、無限大の情報をしばらくの間保持す る。悪い知らせを受け取ったら、すぐに伝える。 


RIP のメッセージ。

       0                   1                   2                   3 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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | command (1)   | version (1)   |      must be zero (2)         |
      +---------------+---------------+-------------------------------+
      | address family identifier (2) |      must be zero (2)         |
      +-------------------------------+-------------------------------+
      |                         IP address (4)                        |
      +---------------------------------------------------------------+
      |                        must be zero (4)                       |
      +---------------------------------------------------------------+
      |                        must be zero (4)                       |
      +---------------------------------------------------------------+
      |                          metric (4)                           |
      +---------------------------------------------------------------+

Command は、1が要求、2が応答。
IP 以外でも使える。
0.0.0.0がデフォルト。
ホップ数は、1から16()。16は、無限。
UDP ポート 520 番が使われる。

1058.txt

HELLOプロトコル

RIPは、ホップ数を用いたベクトル距離アルゴリズムであった。HELLO では、 ホップ数の代わり、リンクの通信遅延時間を用いる。

gated

gated は、RIP, HELLO, EGP を解釈することができるプログラムである。 gated は、RIP や HELLOで受け付けた自律システム内部の経路情報を、EGP を 使って自律システム外部に広告することができる。

OSPF

OSPF (Open SPF)プロトコルは、ベクトル距離型あるアルゴリズムではなく、 SPF (Shortest Path First)と呼ばれるアルゴリズムを用いる。SPF では、各 ルータは、自律システム内の完全なトポロジを把握している。すなわち、ルー タを節(node)、ルータ間のリンクを辺(edge)としたグラフを考えると、SPF で は、各ルータは、全体のグラフを保持している。SPFは、リンク状態（リンク が使えるか使えないか）を使うことに着目して、リンク状態経路制御アルゴリ ズム（link state routing algorithm）とも呼ばれる。

SPFアルゴリズム

各ルータは、隣接したルータへのリンク状態のリストを交換する。このリスト は、他のルータへも中継され、結果として全てのルータに届けられる。各ルー タは、こうして得られたリンク状態を元に、ダイクストラの最短経路アルゴリ ズム（Dijkstra shortest path algorithm）を用いて、ネットワークの地図を 作る。

SPFの最大の利点は、各ルータが同じデータ（リンクの状態）を使って独立に 経路を計算することである。リンクの状態を運ぶメッセージは、単にコピーさ れるだけなので、デバッグが容易である。そして、リンクの状態を運ぶメッセー ジは１つのルータから直接つながっていることについての情報だけを運ぶので、 ネットワークの大きさに無関係である。

OSPF は、SPF アルゴリズムを実現したものの１つである。OSPF は、誰でもラ イセンス料無しに利用することができる（open）。さらに、終点のＩＰアドレ スだけではなく、サービスの型を用いた経路を行うことができる。複数のリン クが存在した場合、負荷分散を行うこともできる。

k-out-of-n 規則。 近隣が生きているかどうかを調べる時に、返事がなくても、 すぐに死んでいると判断しないで、ＵＰのままにしておく。 逆に、返事が届くようになっても、ある程度まではＤｏｗｎのままに しておく。

RFC1131 (PostScript)

歴史

  1. ネットワーク全体の情報がないと、ルーティングができない。
  2. デフォルト経路。部分情報だ持てばいい。
  3. バックボーンとコア・システム。無矛盾でも非効率になる。
  4. 対等なバックボーン。いくつかのデフォルトを使う ゲートウェーの集合に分割する。 宛先不明のパケットがループする。
  5. 自動化したい。
  6. ベクトル距離制御。ＧＧＰ。
  7. ＥＧＰ。

■ARP(Address Resolution Protocol)

ARP は、ＩＰアドレスをイーサネット・アドレスに変換するための プロトコルです。 １本のイーサネットにつながっているホストへ直接、ＩＰ のパケットを送る場合、まず、送り手は、

「ＩＰアドレスのイーサネット・アドレスを教えてください」

というＡＲＰパケットをイーサネットの放送を使って問い合せます。 各ホストは、自分のＩＰアドレスが問い合せられた時は、それに答 えます。送り手は、このイーサネット・アドレスを使って、ＩＰの パケットを送りだします。同時に、このイーサネット・アドレスを キャッシュとして、しばらくの間（２０分）保持し、次に同じホス トに送る時に使います。

◆ ARP のテーブルを見よう

現在の ARP のテーブルを見るには、次のように arp コマンドを使います。 

----------------------------------------------------------------------
% arp -a [←]
adonis1 (130.158.87.1) at 8:0:9:41:d4:1f ether
adonis3 (130.158.87.3) at 8:0:9:42:fb:99 ether
adonis4 (130.158.87.4) at 8:0:9:78:12:c3 ether
adonis5 (130.158.87.5) at 8:0:9:41:3c:cb ether
adonis6 (130.158.87.6) at 8:0:9:78:fd:22 ether
adonis7 (130.158.87.7) at 8:0:9:42:fb:46 ether
adonis8 (130.158.87.8) at 8:0:9:78:c5:37 ether
adonis9 (130.158.87.9) at 8:0:9:70:8c:3d ether
adonis10 (130.158.87.10) at 8:0:9:78:c5:c3 ether
adonis11 (130.158.87.11) at 8:0:9:70:7c:88 ether
adonis12 (130.158.87.12) at 8:0:9:41:64:ef ether
adonis13 (130.158.87.13) at 8:0:9:41:a4:f8 ether
adonis14 (130.158.87.14) at 8:0:9:41:d4:48 ether
adonis15 (130.158.87.15) at 8:0:9:41:98:63 ether
adonis16 (130.158.87.16) at 8:0:9:41:98:ed ether
adonis17 (130.158.87.17) at 8:0:9:42:a3:5b ether
adonis18 (130.158.87.18) at 8:0:9:78:c5:91 ether
adonis19 (130.158.87.19) at 8:0:9:41:98:fe ether
adonis20 (130.158.87.20) at 8:0:9:42:fb:49 ether
%
----------------------------------------------------------------------
-a (all) で、全てのエントリを表示します。

◆ ARP テーブルにエントリを追加しよう

ARP のテーブルのエントリは、普通自動的に登録されます。しかし、 ごく稀に、自分で ARP を解釈できないホストがあります。そのよ うなホストと通信を行う時には、 

% arp -s ホスト名 イーサネット・アドレス [←]
のように、手動で登録します。

◆ ARP テーブルからエントリを削除しよう

不用になったエントリや、間違ったエントリは、次のように 

	# arp -d ホスト名
で、削除することができます。

◆ Proxy ARP

ネットマスクが違う時に繋ぐ技術。

■ TCP(Transmission Control Protocol)

TCP/IPは、信頼性のある(reliable)双方向のストリーム転送サービス (stream transport service)を提供する通信プロトコルである。

TCP/IP では、プロセスとプロセスが、電話で会話をするように通信が行われ る。普通の電話で人間同士が話をするには、まず電話番号を指定して、話相手 に電話をとってもらわなければならない。TCP/IP においても同様である。 TCP/IPでは、電話を掛ける方をクライアント・プロセス、電話を待つ方をサー バ・プロセスと言いう。

TCP/IPにおいて、プロセス間に形成されたストリーム通信路のことを、計算機 間に張られた物理的な回線に似ていることから、仮想的回線(virtual circuit)とも言う。TCP/IP では、回線を接続する段階では、クライアント・ プロセスとサーバ・プロセスは非対称である。一度仮想回線が接続された後は、 両方のプロセスは、TCP/IPのレベルでは、まったく対称的になる。

TCP層の技術1:再転送付き肯定確認応答

IP層は、転送サービスとして信頼性のないデータグラムを提供する。TCP 層の仕事は、それを使って、双方向のストリーム転送サービス提供することで ある。そのために、「再転送付き肯定確認応答(positive acknowledgement with retransmission)」という、一般的によく用いられている技術が使われ ている。この技術では、データの受け手は、データを受け取る度に、送り手に 確認応答(acknowledgement, しばしば ack と省略される)を返す。データの 送り手は、確認応答を受け付けると、次のデータを送る。ある時間がたっても 確認応答が来なかった場合、データの送り手は、再転送(retransmit)する。

TCP層の技術2:スライディング・ウィンドウ

ストリームを実現する技術として、TCPは、スライディング・ウィンドウ (sliding window)と呼ばれる技術を用いている。この技術では、ウィンドウと 呼ばれる範囲を設定して、確認応答が来る前に、次々とウィンドウ内のパケッ トを送出す。確認応答を受け取ると、ウィンドウを「スライド」させ、次のパ ケットを送り出す。

フロー制御

受け手のバッファ（メモリ）は、有限である。送り手は、受け手消費する速度 に合わせてパケットを送出さなければならない。このような制御をフロー制御 という。TCPでは、スライディング・ウィンドウを用いてフロー制御を行って いる。

■UDP (User Datagram Protocol)

UDPは、IPと同じく、データグラム・サービスを提供する。IPとの違いは、ポー ト番号により、１つのホスト上で送り手受け手のプロセスを識別することがで きることにある。

■RFC(Request For Comment)

↑[もどる] ・[1月27日] →[2月3日]
Last updated: 1998/01/27 01:08:55
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>