esオペレーティングシステムのTCP/IPスタックの設計
(執筆中)

最終更新日 2007-11-06


ここではesオペレーティングシステムのTCP/IPプロトコルスタックの設計について説明します。

はじめに

esオペレーティングシステムのTCP/IPスタックは基本的に[Hüni 95]で述べられているコンジット+フレームワークに基づいて設計を行っています。[Hüni 95]の著者のひとりはデザインパターンのGoFのひとりR. E. Johnson教授です。

プロトコルスタックの実装は1980年代には非常に困難なものでした。OSI参照7層モデルにしたがってスタックを実装することについてMITのDavid D. Clark教授は[Comer 87]に寄せられた序文の中で"The layering suggested by the specification must be violated to insure efficient execution. (中略) The implementor must go it alone, trying to blend together network abstraction and operating system abstraction which don't seem to fit well"と述べられています。しかしストリーム入出力システム[Ritchie 84], マルチプレクサ[Pike 84]などオペレーティングシステムレベルでプロトコルスタックを構造的に設計、実装するための道具はその当時から提案されていたことがわかります。 そしてそれらにデザインパターンを適用したものがHüniらのコンジット+フレームワークです。ストリームを構成するスタック状に積み重ねたモジュールやマルチプレクサはコンジット+フレームワークではそれぞれ『コンジット』と呼ばれています。コンジットにはその用途によってプロトコル、アダプタ、マックス、コンジットファクトリの4種類に分類されています。そしてこれらのコンジットにストラテジーパターン、ステートパターン、シングルトンパターン、コマンドパターン、ビジターパターン、プロトタイプパターンを適用して ネットワークスタックの構造をより学びやすく使いやすくしようというのが コンジット+フレームワークの狙いです。

しかしコンジット+フレームワークを使ってTCP/IPスタック全体を構築したと言う例は筆者の知る限りではまだありません。NikanderらはJavaを用いてコンジット+フレームワークの実装を行い、それらを用いてUDP/IPを実装したりすることができていたようですが、TCP/IPまで完全に実装することは学生のプロジェクトとしては 時間的に困難であったようです[Nikander 98] 。

Wrightらの優れた著書[Wright 95]によって4.4BSD-LiteのC言語で記述されたTCP/IPスタックのコードを読むだけならば極めて困難と言うわけではな くなったようにも思われますが、それでもそれを改変したり実験したりすることは依然として非常に難しいことではないでしょうか? esオペレーティングシステムでは、RFC 1122にしたがったRFC準拠のTCP/IPスタックをコンジット+フレームワークに基づいて実装しオープンに提供することを目指しています。

TCP/IPスタックのコンジットグラフ

コンジット+フレームワークに基づいて設計したesのIPv4スタックのコンジットグラフの全体像を以下に示します([Hüni 95]の中ではアダプタは楕円と長方形を組み合わせたような図形で表現されていますが、以下の図ではただの楕円で示しています)。

論文中に出てくるコンジットグラフは簡単なものが多いのですが、完全なTCP/IPスタックのコンジットグラフはそれなりの規模のものになることがわかります。ネットワークやアプリケーション プログラムからアダプタが受信したパケットやデータはコマンドを運ぶメッセンジャーの中に格納されてコンジットグラフの中をビジターによって伝達されていきます。ビジターは訪れたアダプタやプロトコルなどそれぞれのコンジットに対してコマンドを発行していきます。ビジターによって指令されたコマンドはそれぞれのコンジットに対応付けられているレシーバによって処理されます。レシーバクラスの中ではさらにステートパターンを用いてTCP, ARP, IGMPといったプロトコルのステートに応じた処理が行われていきます。IPv6ではARPやIGMPに相当するものがICMPv6に統合されたおかげでコンジットグラフはIPv4のものよりも実は単純になると言うことについてはここでは簡単に触れるだけにしておきます(esのIPv6の実装も進めています)。

イーサネット ドライバ

esオペレーティングシステムでは、今のところ、NE2000互換のREALTEK社製RTL8029ASというイーサネットコントローラチップを搭載したLANカードをサポートしています。RTL8029ASはqemuでもエミュレートされている非常にポピュラーだったコントローラーです。実際の商品ではBUFFALOのLGY-PCI-TLといったLANカードがRTL8029ASを搭載していました。

最新のイーサネットコントローラでは従来はCPUで行っていた処理をコントローラ側で行えるものが多いのですが、イーサネットドライバが提供する処理は基本的には以下のものです。

esオペレーティングシステムではこれらの処理はINetworkInterfaceインターフェイスとして定義されています。INetworkInterfaceインターフェイスを実装しさえすれば、esでRTL8029AS以外のイーサネットコントローラチップを利用することもできることになります。

参照: dp8390d.cpp

DIXコンジット

DixTypeMuxは受信したイーサネットパケット(フレーム)ヘッダーのパケットタイプに応じてdixInProtocol (IPv4), dixArpProtocol (ARP)にパケットを流します。dixInProtocolとdixArpProtocolは、送信するパケットにそれぞれ適切なイーサネットパケットヘッダーを付加します。

ARPコンジット

イーサネットのレベルではパケットの送受信はイーサネットのMACアドレスを指定して行われます。TCP/IPプロトコルで使用するIPアドレスとイーサネットのMACアドレスとの対応付けを解決するのがARPプロトコルの基本的な役割です。APRの基本的な仕組みは、通信を行いたい相手のIPアドレスがアサインされているノードがあるかどうかをブロードキャストで問い合わせて、問い合わせを受け取ったノードは自分自身のIPアドレスについての問い合わせであれば送り先に自身のMACアドレスを返信するというものです。IPパケットを送信するたびにARPでMACアドレスを問い合わせていたのではネットワークの利用効率が悪いので、ARPコンジットでは一度問い合わせたMACアドレスとIPアドレスをノード内に一定期間キャッシュしておくという処理を行います。

ARPのもうひとつの機能はリンクローカルIPアドレスの取得です。リンクローカルIPアドレスは、DHCPサーバーがないようなLAN内で機器に動的に割り当てられるIPアドレスで、 ルーターに接続していない家庭内LAN内の情報家電間などで特別な設定なしにTCP/IPによる通信を行えるようにするものです。リンクローカルIPアドレスを取得するときには、ブロードキャストでLAN内 の機器がこれから使用したいリンクローカルIPアドレスがすでに使われていないかどうかを(応答がこないということによって)確認し、応答が来なければ機器にそのリンクローカルIPアドレスを割り当てます。

オンリンクのInet4Addressオブジェクトの状態

ArpProtocolは受信したARPパケットのソースプロトコルアドレスを調べて、そのアドレスに対応するInet4Addressオブジェクトをすでにキャッシュしていれば状態をReachableに変更します。ArpMuxは受信したパケットのターゲットプロトコルアドレスに応じてARPパケットをArpAdapterに流します。ArpAdapterのレシーバーはInet4Addressオブジェクトで、その状態に応じた処理を行います。

状態 説明 RFC
Init IPアドレスに対応するMACアドレスがまだ分からない状態 826
Incomplete IPアドレスに対応するMACアドレスを問い合わせ中 826
Reachable IPアドレスに対応するMACアドレスが分かっている状態 826
Probe IPアドレスに対応するMACアドレスの再確認中 826
Tentative ローカルアドレスが使用可能かどうか確認中 3927
Preferred ローカルアドレスが使用可能な状態 3927
Deprecated 廃止予定のローカルアドレス 3927

注: Inet4Addressオブジェクトには、その他にマルチキャストアドレス、デスティネーションアドレスに関する状態がありますがそれについては後述します。

参照: arp.cpp, RFC 826, RFC 3927

IPコンジット

InProtocolは受信したIPパケットのプロトコル番号を調べて、InMuxにパケットを流します。また受信したIPパケットがフラグメントパケットだった場合には、上位のフラグメント再構成コンジットに処理が進むように擬似プロトコル番号としてIPPROTO_FRAGMENTを設定します(IPPROTO_FRAGMENTは本来はIPv6用のプロトコル番号です)。また、InProtocolはこれから送信するIPパケットの宛先がループバックアドレスやオンリンクのIPアドレスでない場合にはルーターにメッセージを送るようにメッセンジャーを設定します。さらに、パケット長を調べてそれがパスMTUよりも大きければフラグメントに分割して下位のInScopeMuxに流します。

InMuxは受信したIPパケットのプロトコル番号を調べて、UDPやTCPなどより上位のコンジットにパケットを流します。

InScopeMuxは送信パケットのスコープIDを調べて、さらに下位のループバックインターフェイスやイーサネットインターフェイスにパケットを振り分けます。

参照: inet4.cpp, RFC 791

ICMPコンジット

ICMPコンジットではICMPエラーメッセージやICMPエコーメッセージの処理を行います。

IcmpMuxは受信したICMPメッセージのTYPEフィールドを見て、それぞれのTYPEに応じたコンジットにメッセージを流します。

EchoRequestMuxは、受信したICMP ECHO要求(8)を処理します。EchoRequestMuxから分岐するEchoRequestAdapterは、Inet4Addressオブジェクトの状態がPreferredになったときに各ローカルアドレスごとにインストールされます。EchoRequestAdapterではICMP ECHO応答を送り返します。

EchoReplyMuxは、受信したICMP ECHO応答(0)を処理します。EchoReplyMuxから分岐するEchoReplyAdapterは、Inet4Addressオブジェクトに対してisReachableメソッドが呼び出されたときにインストールされます。EchoReplyAdapterはICMP ECHO応答を受信できたら、isReachableメソッドを完了します。

UnreachProtocol, TimeExceededProtocolなどはICMPエラーメッセージを処理します。ICMPエラーメッセージを受信した場合には必要があれば受信したエラーメッセージに格納されている問題を起こしたIPパケットのヘッダーのコピーをもとにメッセージをエラーメッセージとしてInProtocolに流しなおします。エラーメッセージは今度はICMPコンジットではなく、そのパケットを送信したコンジット(TCPなど)に届けられます。

参照: icmp4.cpp, RFC 792

フラグメント再構成コンジット

フラグメントパケットはすべてInMuxからフラグメント再構成コンジットに流れてきます。ReassAdapterは新しいIPパケット番号のフラグメントがノードに到着したときにインストールされます。ReassAdapterでフラグメントの再構成が完了すると、再構成したパケットをInProtocolから上位のコンジットに向けて流します。ReassAdapterはフラグメントの再構成に完了したときや、タイムアウトによって再構成に失敗したときにアンインストールされます。

補足: フラグメントの再構成はIPv4のRFC上ではIPレイヤーの処理とされていますが、実装上はIPv6のようにそれ自体を独立したひとつのプロトコル処理とみなしてIPより上位のレイヤーで処理してしまった方が簡単でした。この点はClark教授の指摘通りとも言えますし、IPv6でプロトコルの設計自体も洗練されてきたという風にも思います。

参照: inet4reass.cpp, RFC 815

UDPコンジット

UDPデータグラムの処理を行うのがUDPコンジットです。下位のUdpProtocolではIPv4固有のUDP関連の処理を行います。一方、上位のDatagramProtocolでは、IPv4, IPv6で共通のUDP関連の処理を行います。

参照: datagram.cpp, udp.cpp, RFC 793

TCPコンジット

TCPの処理を行うのがTCPコンジットです。下位のTcpProtocolではIPv4固有のTCP関連の処理を行います。一方、上位のStreamProtocolでは、IPv4, IPv6で共通のTCP関連の処理を行います。ステートパターンを用いてTCPの処理を行うのは、StreamProtocolの方になります。

参照: stream.cpp, tcp.cpp, RFC 768

IGMPコンジット

マルチキャストアドレスのInet4Addressオブジェクトの状態

IResolverインターフェイスを使ってマルチキャストアドレスを指定してアドレスオブジェクトを生成すると、NonMember状態のInet4Addressオブジェクトが作られます。マルチキャストグループに参加するには、マルチキャストアドレスのInet4Addressオブジェクトを引数にとってIMulticastSocketインターフェイスのjoinGroupメソッドを呼び出します。そうすると、IGMPコンジットに新しいigmpAdapterがインストールされ、Inet4AddressオブジェクトはIGMP REPORTメッセージを送信してから、DelayingMember状態に遷移します。通常はDelayingMember状態に入ったInet4Addressオブジェクトはタイムアウトして、もう一度IGMP REPORTメッセージを送信してIdleMember状態に遷移します。マルチキャストグループから離脱するには、IMulticastSocketインターフェイスのleaveGroupメソッドを呼び出します。そうすると、Inet4AddressオブジェクトはIGMP LEAVEメッセージを送信してIdleMember状態に遷移し、さらに対応するigmpAdapterがIGMPコンジットからアンインストールされます。

マルチキャストルーターはLAN内にマルチキャストグループに参加しているノードがないかどうか確認するためにIGMP QUERYメッセージを送信する場合があります。QUERYを受信すると、Inet4AddressオブジェクトはDelayingMember状態に遷移します。基本的にはQUERYにはREPORTで応答する必要があるのですが、ルーターにとってはLAN内にひとつでもグループに参加しているノードがあるかどうかさえ分かればよいので、すべてのノードがQUERYに返答してきてもトラフィックの無駄になります。そのためRFC 2236では、グループに参加してるノードはQEURYを受信してもすぐにREPORTするのではなく、一定期間待機して別のノードがREPORTを送信していたら、自身は何も送信せずにIdleMember状態に戻るように指示しています。また、一定期間待機してもREPORTの送信を確認できなければ、ノード自身でREPORTを送信してからIdleMember状態に戻ります。待機期間はノードごとにランダムに決定するので、ほとんどの場合QUERYに対してはどれかひとつのノードだけがREPORTを送信するだけですみます。

状態 説明
NonMember グループに参加していない状態
DelayingMember グループに参加してるかどうか問い合わされている状態
IdleMember グループに参加している状態

注意: IGMPプロトコルには数バージョンかあって、ノードがデフォルトで使用しているバージョンよりも古いバージョンのQUERYをルーターから受信した場合には、ノード自身の使用するIGMPバージョンを動的に下げる必要がありますが、現状のesはIGMPv2の処理だけを実装しています。

参照: igmp.cpp, RFC 2236

Inet4Addressオブジェクト

Inet4AddressオブジェクトはIPアドレスに付随する情報を保持したオブジェクトです。新しいInet4Addressオブジェクトは、IResolverインターフェイスのgetHostByAddressおよびgetHostByNameメソッドを呼び出すことによって生成できます。

続く

...

参考文献

[Comer 87] D. Comer, "Operating System Design - Volume II: Internetworking with Xinu," Prentice-Hall, 1986.
[Hüni 95] H. Hüni, R. E. Johnson, R. Engel, "A Framework for Network Protocol Software," In Proc. OOPSLA '95, SIGPLAN Notices, pp. 358-369, Oct. 1995.
[Nikander 98] P. Nikander, et al., "Java Conduits Beans (Jacob) project," http://www.tml.tkk.fi/Research/TeSSA/Old_pages/Jacob/jacob3.html.
[Pike 84] R. Pike, "The Blit: A Multiplexed Graphics Terminal," AT&T Bell Laboratories Technical Journal, Vol 63, No. 8, Part 2, pp. 1607-1632, Oct. 1984.
[Ritchie 84] D. M. Ritchie, "A Stream Input Output System," AT&T Bell Laboratories Technical Journal,  Vol 63, No. 8, Part 2, pp. 1897-1910, Oct. 1984.
[Wright 95] G. R. Wright, W. R. Stevens, "TCP/IP Illustrated, Volume 2:The Implementation", Addison-Wesley, 1995.

[esオペレーティングシステムのホームページに戻る]


Copyright © 2007
Nintendo Co,. Ltd.

Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appears in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Nintendo makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.

SourceForge.jp