ILプロトコル

Plan 9ファイルシステムプロトコル9PのRPCメッセージを転送するため、 ILと呼ぶ新しいネットワークプロトコルを実装しました。これはコネクション型のプロトコルで、 IPによってカプセル化されたデータグラムを運ぶ軽量なプロトコルです。 ILは消失したパケットの再送と順序通りの配達を提供しますが、フロー制御と暗黙的な再送はしません。

暗黙的な再送はおそらく、tcpでの再送依頼を受けたらそれ以降を再送するところかな。 ILはstateで受けたackの次にあるデータしか再送しないです。

導入

Plan 9は、RPCリクエストとレスポンスメッセージに、メッセージ区切りがあり、順序保証を要求するプロトコル(9P)を使います。標準IPプロトコルのどれも、9Pメッセージの転送に適切ではありません。 TCPは高いオーバーヘッドがあり、メッセージの区切りがありません。 UDPは、単純でメッセージ区切りを持つとはいえ、順序保証がありません。我々は自分たちのシステムにIP, TCP, UDPを実装していたとき、 9Pに適したプロトコルを選別しようとしました。要求する性質は:

信頼性のあるデータグラムサービス
順番通りの配達
IPネットワーク
シンプルで高パフォーマンス
柔軟なタイムアウト

標準プロトコルには上記を満たすものが無かったので、 IL(Internet Link)と呼ばれる新しいプロトコルを設計しました。

ILは軽量な、IPの上位プロトコルです。これはコネクション指向で、メッセージの到着順を保証します。クライアントサーバ間でRPCメッセージを転送するために設計されたので、フロー制御はなく、構造は固有のフロー制約を含みます。

未解決メッセージ用の小さい窓は、多すぎる受信を防ぐ, バッファされつつあるところからの;

ウインドウからあふれたメッセージは捨てられ、再送されなければなりません。コネクションの確立時に接続の両端でシーケンス番号の初期値を生成するため、 2wayハンドシェイクを使います; 続くデータメッセージは、受信側でバラバラになったメッセージを再並べ替えできるようにするため、シーケンス番号をインクリメントします。他のプロトコルとは対照的に、ILは暗黙的な再送が無効です。これは混雑したネットワークにおいて、暗黙的な再送によってより混雑させるのを防ぎます。 TCPに似て、ILは往復時間によってタイムアウトを決定しますので、インターネットとローカルイーサネットのどちらでも上手に動きます。ネットワーク速度に適した肯定応答と再送の時間を見積もるために、往復時間(RTT; round-trip timer)を使います。

コネクション

ILコネクションは接続している端から端へデータストリームを運びます。コネクションが維持されている間、片側に入ったデータは入れた順に逆側へ送られます。図1は、状態(円)とその変遷(弧)でコネクションの機能を描いたステートマシンです。それぞれの変遷は、水平線の上が変化の原因となったイベントで、下には、このときに受信または送信するメッセージを表しています。この論文の残りは、このステートマシンについて議論します。

<図1>, 原文をみてください。

snd(packet)は相手側へpacketを送信する。 rcv(packet)は受信。

packetはtype(seq, ack)かな？typeはsyncとかdataとか。

ackok: any sequence number between id0 and next inclusive
!x: xを除くなんらかの値
-: なんらかの値

ILステートマシンには、Closed, Syncer, Syncee, Established, Closingという5つの状態があります。コネクションは両端のIPアドレスとポート番号によって識別されます。アドレスはIPプロトコルヘッダにあり、ポート番号は18バイトのILヘッダにあります。コネクションごとに固有の変数は:

state: Closed, Syncer, Syncee, Established, Closingのどれか
laddr: 32bitローカルIPアドレス
lport: 16bitローカルILポート番号
raddr: 32bitリモートIPアドレス
rport: 16bitリモートILポート番号
id0: 32bitシーケンス番号(ローカル側)
rid0: 32bitシーケンス番号(リモート側)
next: ローカル側から送られる次のシーケンス番号
rcvd: 正常に受信した最後のリモート側番号
unacked: まだACKを受け取っていない最初のシーケンス番号(ローカル側)

接続は最初、未割当アドレスでClosedになっています。まだ接続されていないコネクションへメッセージが届くか、またはユーザが明確に接続すると、コネクションをオープンします。最初の場合、メッセージの送信元アドレスとポートがリモート側のそれになり、送信先はローカル側として処理します。このとき、コネクションの状態はSynceeです。2つ目の場合は、ユーザがローカルとリモート両方のアドレスとポートを明示します。コネクションの状態はSyncerになり、 syncメッセージがリモート側に送られます。ローカルアドレスの正当な値はIPの実装によります。

シーケンス番号

ILはデータメッセージを運びます。各メッセージはOSからのwrite命令1回分に対応し、それは32bitシーケンス番号により識別されます。コネクション両側の初期シーケンス番号はランダムで、最初のsyncメッセージで伝えます。番号は、続くデータメッセージごとにインクリメントされます。再送されたメッセージのシーケンス番号は、最初に送った番号です。

送信/再送

acknowledgement: 受信確認
acknowledge: 承認

各メッセージは識別子(ID)と受信確認(ACK)という 2つのシーケンス番号を持ちます。ACKは、リモート側で順序正しく受信を確認したシーケンス番号の最大値です。 dataとdataqueryメッセージの場合、IDはそのシーケンス番号です。 sync, ack, query, state, closeといったコントロールメッセージでは、 IDは送ったデータメッセージの最大シーケンス番号より1大きい。

よく分かっていないけど、 data(201, -)で送った後にsync, ackと続く場合、どちらもIDは202になるということなのかな。で、その後に送られるdataもIDは202ですが、おそらくここでインクリメント。次からIDは203になる。

ソースを読むと、ilackq関数でunackedに追加するのですが、これはilkick関数(データの送信)からしか呼び出していないのでたぶんあってる。nextを増やしているのもilkickだけだし、コントロールメッセージは受信したらすぐ応答しているし。

送信者はデータメッセージをdata型として送ります。 ACKが返送メッセージに含まれています。データを受信してから200msec以内に返送していない場合、 ackメッセージが送られるでしょう。

IPでは、順序が入れ違ったり、混雑により消失したり、失敗したりするかもしれません。これを克服し、かつネットワークを混雑させないために、ILは改良したgo back nプロトコルを使います。平均RTT(round trip time)は、メッセージの送信とそのACKを受け取った遅延を計測することによって保たれます。いちども承認を受信していなければ、平均RTTを100msecだと仮定します。受信確認がまだされていないメッセージでいちばん古いものについて、 RTTを4回過ぎても受信確認がない場合(図1ではrexmit timeout)は、 ILはメッセージか受信確認のどちらかが消失したと判断します。このとき、送信者は最初の未承認メッセージだけをdataquery型で再送します。受信者はdataqueryを受信すると、順番に受信したデータメッセージの最大ACKをstateメッセージで応答します。これはたぶん、再送されたメッセージのシーケンス番号、または (受信者が今までにため込んでいるメッセージの順序が狂ったなら) より大きい正常に受信したシーケンス番号でしょう。受信者が、順序が狂ったメッセージを保存するかどうかは実装によります。我々の実装では前方向に10パケットため込みます。送信者はstateメッセージを受信したとき、すぐに次の未承認なメッセージをdataquery型で再送します。これは全てのメッセージが承認されるまで続けられます。

sync: 最初の2wayハンドシェイク
data: ふつうのデータパケット
dataquery: ひとつのシーケンス番号だけ再送要求; stateを返す
ack: ack
query: データを持たないdataquery
state: 正常受信した最大シーケンス番号パケット; 未承認パケットがあればdataqueryを返す
close: close

もし、dataqueryの後にACKが届かないなら、タイムアウトの後、送信者はdataqueryメッセージの再送を続けます。再送の間隔は指数関数的に増大します。最後に受信してから300秒経過した後(図1のdeath timeout)、送信者はあきらめて接続が切れたと判断します。

再送は、Syncer, Syncee, Close状態でも起こります。その再送間隔はデータメッセージと同等です。

Keep Alive

切れた接続は発見され、リソースを消費しないように取り壊さなければなりません。生きているシステムだとしても、これ以上データも受信確認も送らないなら、今までに述べたプロトコルは、これらの接続を発見しません。

このあたり翻訳があやしい。

したがって、Established状態において、最後に送信してから6秒間、他にメッセージが無いなら、queryを送ります。受信者はいつでも、stateメッセージでqueryに応答します。もし最後に受信してから30秒間メッセージが届かなければ、接続は閉じられます。これは図1に描かれていません。

バイトオーダー

すべての32bitと16bit数はネットワークバイトオーダーです。

フォーマット

以下は、IPオプションを無いものとして、 C言語で記述したIP+ILヘッダです。

typedef unsigned char byte;
struct IPIL
{
	byte vihl;	/* バージョンとヘッダ長 */
	byte tos;	/* type of service */
	byte length[2];	/* パケット長 */
	byte id[2];	/* Identification */
	byte frag[2];	/* フラグメント情報 */
	byte ttl;	/* Time to live */
	byte proto;	/* プロトコル */
	byte cksum[2];	/* ヘッダのチェックサム */
	byte src[4];	/* IP送信元 */
	byte dst[4];	/* IP送信先 */
	byte ilsum[2];	/* ヘッダを含めたチェックサム */
	byte illen[2];	/* パケット長 */
	byte iltype;	/* パケットタイプ */
	byte ilspec;	/* special */
	byte ilsrc[2];	/* 送信元ポート番号 */
	byte ildst[2];	/* 送信先ポート番号 */
	byte ilid[4];	/* シーケンス番号 */
	byte ilack[4];	/* ACK */
};

データはヘッダのすぐ下です。 ilspecは将来のために予約されているフィールドです。

チェックサムはilsumとilspecを0にしたうえで計算されます。これは標準IPチェックサムで、 that is, the 16-bit one's complement of the one's complement sum of all 16 bit words in the header and text. もしメッセージのヘッダとテキストのバイト数が奇数なら、上位バイトを0で詰めた16bit数として扱います。

チェックサムはcksumからデータの終わりまでをカバーします。

有効なiltype値は:

enum {
	sync=		0,
	data=		1,
	dataquery=	2,
	ack=		3,
	query=		4,
	state=		5,
	close=		6,
};

illenフィールドはILヘッダとデータのバイト数です。

Numbers

IL用のIPプロトコル番号は40。割り当てられたILポート番号:

7: echo all input to output
9: discard input
19: send a standard pattern to output
565: send IP addresses of caller and callee to output
566: Plan 9認証プロトコル
17005: Plan 9 CPUサービス, データ
17006: Plan 9 CPUサービス, notes(シグナルのようなもの)
17007: Plan 9 exported file systems
17008: Plan 9ファイルサービス
17009: Plan 9 remote execution
17030: Alef Name Server

参照

The Use of Name Spaces in Plan 9
RFC791, Internet Protocol
RFC793, Transmission Control Protocol
RFC768, RFC768, User Datagram Protocol