日付：2000/7/1
この文章について | ネットワークの動作概要 | Physical Layer：物理層 | Media Access Control SubLayer | Logical Link Sublayer | Network Layer | Transport Layer
Network Layer-Part3N-2 Congestion Control
Congestionの意味を英和辞典で調べてみると「（交通）渋滞」という訳がでてくる。してみればつまるところCongestion controlとは「渋滞のコントロール」である。
さて、まずNetworkにおいてCongestion-渋滞はなぜ起こるかから。
・Link Congestion：複数のリンクから同じリンクへ送信されるべきパケットが、あまりに多く届いた場合に発生する。つまり届けられるパケットは山ほど複数のリンクからはいってくるのに、出ていく道が一つの場合だ。
・Speed Mismatch：高速なリンクから届いたパケットが低速なリンクにでていく場合。ちなみに思考の速度は速いのだろうが、口のスピードがおいついていないのではないかと思える人では頭の中でこの種のCongestionが起こっているに違いない、と思えることがある。
・processror Saturation：今迄の説明ではまあ何らかのロジックにしたがって入ってきたパケットを「どこかのリンク」に送り出す、としてきた。
しかしながら、こうした処理にはなんらかの「判断」が必要であり、その「判断」はノードのしかるべきProcessorが行なっているのである。そしてパケットの送り先を判断するのに必要な情報処理量がそのProcessorの処理量を超えれば渋滞が生じる。
・Link or Node failures：ネットワーク内のリンクまたはノードの故障（もしくはAny kind of 停止）道路がいきなり普通になったりあるいは高速道路の料金徴収所が閉鎖になったような状況だから渋滞が起こるのは当たり前だ。前述したAdaptive Routingはこうした場合に別のルートを探すことで、渋滞の緩和を図るのに役立つのだが。
さて、こうしたもろもろの理由でCongestionが起こってしまうとリンクやProcessorの処理能力は最適の状態で使用されている、とは言えなくなる。（ある個所で渋滞が起こってしまえば、そこから先のリンクはデータを送りたくても送れない状況になっているかもしれない）またこうした渋滞の結果あるノードから別のノードに送ったパケットがいつまでも届かないとしよう。すると送った側は
「いつになったらAcknowledgeが届くんだ。。しょうがねえな。タイムアウトになっちゃった。もう一度送り直そう」
と再び同じパケットを送信する。すると当然のことながら更に渋滞の状況は悪くなり、、といったように渋滞が渋滞を呼ぶことになりかねない。
最悪の場合は、Dead Lockと呼ばれる状況も発生する。例えば二つのノードがお互いにパケットを送ろうとしているものとする。そららのノードでは受信のバッファと送信バッファが共用されている。
Dead Lockとは以下のような場合である。すなわち両方のノードとも送信側に全てのバッファを使用しており、受信側のバッファが無いような状況だ。お互い
「おれは相手にデータを送ろうと思っている。送るためのデータはしこたま送信バッファにためてある。ところが相手の受信バッファは一つも空いていない。だからデータが送れない」
と考えていて、そこから一歩も進むことができない。
さて、こうしたCongestionを防ぐためにはどのような方法があるだろうか。
・Flow Control
Flow Controlで使われるテクニックとCongestion Controlで使われるテクニックは似てはいるが、その目的とするところは異なる。Flow Controlとは所詮２点間の流れを制御するものであり、他のリンクやノードがどうなっているかは待ったく気にしていないのである。しかしながら既に述べたFlow Controlの方法（例えばWindow Mechanism)はCongestion解消のためにも用いられる。
・Admission Control
基本的にあるホストを想定し、そこからネットワークへのパケットの注入可否をコントロールする方式である。基本的にはあるアルゴリズムにしたがって、ホストがクレジットを発行する。このクレジットはクレジットカードのクレジットのような意味でとればよかろうか。そしてそのクレジットを持っている人間がネットワークにパケットを送信できる。クレジットが切れればそれまでである。
この方法に属するものとして本講義では以下の二つの方法が説明された。
・isarithmic Control：この"Isarithmic"という言葉の意味は正直よくわからない。しかし行なうことはある意味明解であり、ネットワーク内のクレジットの数を一定に保とうとする。
(1)パケットがネットワークから出て行く場合には、新たにクレジットが発行される。
(2)パケットがネットワークに入る場合にはクレジットが捨てられる。
(3)クレジットはネットワークの中を巡回していて、各ノードはパケットを発信する前にクレジットを捕まえなければならない。
この方式にはいくつかの困難がある。まず第一にクレジットをネットワーク内に巡回させるのは一行でかけるほど簡単ではない。また何かの理由によりクレジットが失われる（パケットが失われることがあるのだから、クレジットも消える）場合に、それを検知するのは簡単ではない。
・Leaky Bucket：「漏れのあるバケツ」とでも訳すのだろうか。行なうことは以下の通りである。
(1)全てのノードはある一定のペースでクレジットをもらう。ただし、クレジットの数は上限を超えては増えない。
(2)クレジットを持っている限りノードはネットワークにパケットを送信できる。そしてクレジットを減らす。クレジットを使い切ればそれ以上パケットを送信できない。
・Choke Packets
先ほどの方法と異なり、ある単一のホストからではなく、全てのノードにおいて、Congestionの制御を行なう方式である。また始終Congestion制御のために何かしているのではなく、Congestionが予想された場合だけに制御を行なう。具体的には次のようなことを行なう
・Congestionを検知した場合、Choke Packet（ここでChokeとは「詰まる」とかそういう意味であろう。喉に物がつまるのは"Choke"だったはずだが）を詰まったリンクに送り出されるパケットを送ってきた元のノードに送信する。
Choke Packetを受け取った側はその目的地に送るパケットを減らす。一定期間の後二度ノードはChoke packetをチェックし、まだ送られてくるようであればさらにパケットの量を減らす。逆にもうChoke Packetが送られてこなければパケットの量を増やすことができる。（もちろん送るデータがないのに無理矢理パケットを送る必要はない）
つまり「詰まっているからもう送るな」というのを送り元に知らせる、というきわめて素直な方式に思えるのだが、いくつか問題がある。まずChoke Packetが作られてからその元となるノードにたどり着くまでにはいくばくかの時間遅れがある。その間元のノードは詰まっているとは思わずに今迄と同じペースでパケットを送りつづけるわけだ。またChoke packet自体がCongestionの原因にもなりかねない。某Web Siteには
「この方法は不正確で荒っぽい」
と書いてある。
・Buffer Reservation
Vritual Circuitにおいて（これが何者かは前述した）は、パケットがバッファ不足でなくならないようにバッファを十分に割り当てることが可能である。つまり出て行くべきリンクが混雑していてもパケットをバッファに貯えておけば、少なくともパケットが消えてしまうことはないわけだ。
しかしながらこの方法ではＶＣごとにバッファを割り当てる必要があり、かついつおこるかわからないCongestionに備えてバッファを確保しておく必要があるため、大変効率が悪い。
・Packet Discaring
またの名をBuffer Sharingである。先ほどのBuffer ReservationはＶＣごとにBufferを確保しておくから効率が悪かったのであって、バッファを全てのＶＣで必要に応じて共有すればバッファの無駄遣いはなくなる。ただし逆にディメリットとして、使えるバッファがない場合（誰か他のＶＣがみんな使ってしまった場合だ）にはパケットを捨てざるを得ない場合がありえる。そしてパケットを捨てざるを得ない、ということはNetwork layerもしくは上位のTransport Layerにおいて、そのリカバリをしなくてはならない、ということだ。
もしTransport Layerに対して、Connection-orientedのサービスを提供していれば、エラーのリカバリはNetworklayerの責任になる。この場合パケットが失われる場合に備えて、データを送ろうとするノードは、そのデータに対するAcknowledgeが返ってくるまでデータをバッファに貯えておく必要がある。
さて、かくのごとく「パケットをなくすんもんか」と思いバッファを使い切ってしまったとしよう。そこにパケットが届く。「もうバッファがないからこれ以上パケットは受け付けられないよ」と思ってもいきなりパケットを捨ててしまってはいけない。そのパケットは待ちに待った"Acknowledge"かもしれないのだ。（Acknowledgeであれば、バッファの中にためておいたデータを捨て、他のパケット用に使用することができる）
回線を効果的に使用するためには、各パケットを送り出す側のリンクに割り当てるバッファの数に制限を設けたうえで共用することもできる。バッファの数に上限を設けることで一つのリンクがバッファを独占してしまうことを防ぎ、下限を設けることで、バッファがないことによるパケットの損失を防ぐわけだ。この方法はChannel Queue Limitと呼ばれる。
・Deadlock Avoidance；
Deadlockが発生すると、まったくパケットの送受が行われない状況となってしまう。
これを避けるためにはいくつかの方法がある。例えばhttp://floppsie.comp.glam.ac.jp/Glamorgan/gaius/cnn/11routing.htmlには"bruteforce"として「送信待ちバッファに一定時間以上存在しているパケットは強制的に捨ててしまう」という方法が紹介されている。
本講義ではもう少し複雑な方法が紹介された。概要を以下に示す。Structured Buffer Pool：バッファを０からＭまでＭ＋１レベルにレベル分けする。ここでＭとはネットワーク内に属するノード間の最大Hop数である。
さて、新しく作られたパケットはレベル０のバッファを使用できる。一般的にはあるノードにおいてレベルiのバッファを使用していたパケットは次のノードではレベルi+1のバッファを使用する。レベルＭのバッファを使用していたパケットは次のノードに行ったときにはもうバッファは使用できない。
さてこのようにすると、Deadlockを避けることができる。問題としてはバッファの使用効率が低くなる可能性があげられているが、本講義では短に「そうした欠点を解消するこ改善型もある」とだけ書かれている。
さて、これまた恒例になりつつあるが、実際のネットワークではどのような方式が使われているかをずらずらと書いてみよう。
・ARPANET：Channel Queue Limitであまったパケットは捨てる。２点間のフローコントロールはTransport Layerで実施。
・TYMNET：ＶＣ上にあるすべての隣接したノード間でWindowを使った（DLCのところで述べた）制御を実施。
・SNA：Window Mechanismを使い、Windowのサイズを動的に変化させる。
・DECNET：Channel Queue Limit
N-3 Internetworking
さて、そもそもなぜ異なるネットワークをつなぐ必要があるのだろうか、ということが本講義では長々と書かれている。しかしながら本講義から１０年近くたった今日となってはこの意義をとくことはあまり必要ではないかもしれない。
例えばたいていの大学や企業ではインターネットを利用している。そしてそれとは別に自分のパソコンからなんだしらないが「LANのケーブル」なるものがでていることも知っている。そしてよほど楽観的な人間でない限り自分のパソコンから出ているケーブルがそのままの形で世界中にはりめぐらされているとは思わないだろう。（正直言えばこれは一時私が悩んだ問題なのだが）ということはどこかで別の形態のネットワークと接合されているけだ。
さて、こうしたネットワークの相互接続に望ましい性質は（例によって例のごとく）
・透明性。つまりつながれているということを意識せずにすむということ。
・堅牢性。信頼性。
・柔軟性
・セキュリティ
さて、こうした性質を実現しようとする際に問題になるのは、「異なるネットワーク」を相互接続する、ということから必然的に生じる問題だ。つまりプロトコルが異なるのである。プロトコルが異なればタイムアウトの時間がことなり、パケットのサイズがことなり、アドレスの方式が異なり、エラー回復の方法が異なり、説明したばかりのルーティングやCongestion Controlの方法が異なり、ユーザーの認証方法までも違うかもしれない。しかし「透明性」とうたっているからにはとにかくそうしたことは全てこの「Internetworking」という言葉でくくられる範疇で面倒を見なくてはならない。
さて、ここまでに「異なるネットワーク」を相互接続する、と書いているが、OSI７階層のどのレベルで動作するものか、とに関してはいくつかの種類がある。
一番単純なのは、物理層で動作するRepeater-リピーターである。物理層だから、基本的に何がはいっているかはまったく考えず、単に「ビット列」として信号を処理する。このリピーターなるものを一番意識したのは、LANの接続距離の延長（これは電気的信号の増幅器で対処できる範囲ということだが）だったが、なんでもかんでも10base-Tになり、ハブが実はリピーターの役割もしているのではないか、と思う今日このごろではあまり普通には目にしないのかもしれない。
さて、かくのごとくRepeaterは物理層の情報しかみていないので、例えば
「リピーターの同じ側にあるノード同士の通信パケットを、リピーターの反対側に通さない」
なんていう高級な制御はできない。もっとも10Base-Tでは最近「スイッチングハブ」なるこうした選択式にパケットを通すものもあるが、、あれは一体Repeaterなのか次に述べるBridgeなのか。。。たぶん後者だと思うのだが。（物理層だけ見ていては届け先のアドレスはわからない）
次にData Link Layerで動作するのがBridgeである。Mac layerが異なる二つのネットワークをつなぐのに使われる。例えばIEEE802.Xシリーズである。Toekn ringとEthernetのネットワークを結合したい時、あるいは私が実際に触ったネットワークで言えば、Localtalk（mac専用のLAN）とEthernet-Ethertalkをつないで一つのネットワークとして扱いたいときにBridgeを使ったことがある。
その一つ上、Network layerで動作するのがRounterである。最近普通の人が耳にする言葉で一番多いのはこのRouterであろう。以下BridgeとRouterについて説明する。
Bridges
基本的にはLAN-LANの接続に用いられる。そして上位のプロトコルに対しては透過的であることが期待される。透過的たぁなんだというと、ノード間で通信を行なうときにそれが複数のLANを結合したものであっても、一つのLANに属しているかのように扱える、という意味においてである。
ではこれはどのくらい難しいものだろうか？たとえばDLC Layerでの違いとは、同じIEEE802.Xシリーズと呼ばれるものの間でもこんな感じだ。
最大フレームサイズ：
802.3：1518bytes,802.4：8191 bytes, 802.5:制限なし。
伝送速度：
802.5は４又は１６Mbps,これに対して802.3は１０Ｍｂｐｓ．などなど。
では実際にはどのようなBridgeが使われるのだろうか。
・Spanning Tree Bridge
こちらは多分本講義では「Transparent Bridge」と称されたものと同一ではないかと思う。その目標とするところはTransparencyであり、具体的に言えばユーザーが購入して、二つのネットワークに接続し、電源を入れれば動作する、というものである。余計なハード、ソフト、もしくは設定など必要なしでだ。ではどうすればそれが達成できるか。
１．フレームから送り元と目的地のアドレスを取り出し、それぞれのアドレスに対応したテーブル（表）の値を見る。この表にはアドレスとそれに対応するリンクの情報がかかれている。
２．もし送り元へのリンクと目的地へのリンクが同一であれば、パケットは捨てる。（なぜかといえばパケットの送り元と目的地が同じネットワークに属していると考えられるからだ。
３．そうでなければ、目的地のアドレスに対応したリンクにパケットを送信する。
４．もし目的地が表にのっていなければ、Floodingを使い、もともとパケットを受け取ったリンク以外すべてのリンクにパケットを送信する。（とりあえずどこにあるかわからない相手だから可能性のあるリンクすべてに送信してみるわけだ）
５．表を作るためには、Backward learningを行なう。つまり目的地Ｘに対してどのリンクにパケットを送るかは、Ｘからきたパケットがどのリンクから届いたかを記録しておくことで判断する。
６。Bridgeが他のLANに移される場合も考えて、表はしばらく参照されないと自動的にクリアされる。
さて、このように動くBridgeであるが、LANの中にLoopがあると問題が生じる。パケットはループを永遠に回りつづけることになってしまいかねない空だ。（例えばEthernetのパケットに「寿命」などというものは定義されていない）
これを防ぐための仕組みも用意されている。まずBridgeは互いにBridgeのIDを交換し、低い番号のものがroot Bridgeになる。次に各Bridgeからroot BridgeにいたるMinimum Spanning Treeを構成する。そしてこのMinimum Spanning Treeに属さないリンク、またはBridgeは使わない。そしてリンクやBridgeがダウンした場合に備えて、このMinimum Spanning treeは定期的にアップデートされる。
さて、かくのとおりこの方式は前述した「透明性」をもっている。インストレーションは簡単だし、トポロジーが変わった場合にも勝手に適応してくれる。そしてノード側には何も複雑な機構は必要ない。
反対にDis-advantageだが、定義によってMultiple pathを使ってのRoutingは行われない。またSpanning Treeが必ずしも全てのノード間にとって最適経路という保証も無い。
このような問題もあるが、CSMA/CD方式においてこのSpanning Tree Bridgeは大変広く使用されている。
・Source Routing Bridge
Source Routing BridgeはSpanning Tree Bridgeとはまったく反対のアプローチをとっている。
１．全てのLANには16bitの番号が、また全てのBridgeには4bitの番号が振られている。これらの番号は事前にネットワーク管理者（それが誰であろうと）によって重複がないように決められなくてはならない。
２．パケットの送り元は、送り先への経路を指定する。経路は、[LAN番号,Bridge番号]の対によって指定される。
３.送り先への経路を探すためには、まず"Discovery Packet"をBroadCastで送りだす。でもって送り先にそのパケットが到着すると経路が発見できたことになるわけだ。送り元は複数のパケットから送られてきた経路情報のなかから「最短」のものを選択する。
この方式のメリットはいくつかある。まず最適経路を使用できる。また同一送り先に対して複数経路を使用する（Multiple path)も可能だ。さらにはMinimal SpanningTreeに経路が限定されないので、ネットワーク資源をより有効に使える可能性もある。
しかしながら（多分前の説明を読む間に気がつくと思うのだが）ディメリットはもっとたくさんある。一番おおきんあものは経路発見のためのDiscovery packtはノードの数が多くなるにつれて、指数的に増大してしまうことだ。また前述した通りネットワーク管理者はLAN番号、Bridge番号を管理する必要があるからTransparentではないし、リンクやBridgeがダウンした場合に発見するのもおそくなる。
先の参考文献によれば"not Surprisingly "IBMがこのSource Routing Bridgeをサポートしているという。彼らの愛するToken ringで使うためらしい。TransparentBridgeがCSMA/CDであるところのEhernetで使われていることを考えれば普通に目にするのはおそらくTransparent Bridgeのほうであろう。
・Routers
前述のWeb Siteによると、RoutrとGatewayという言葉は相互に同じ意味で使われると書いてある。本講義でだったかどうだったか覚えていないが、別物、という定義を聞いたこともあったのだが。
さて、Bridgeは主にLAN同士の接続に使われる、と書いたが、Routerはそれよりも広い範囲で使用される。Network layerで動作するためアドレスの変換、パケットの分割・結合など機能的にはより柔軟であるが、裏をかえせばよりCPUパワーを必要とし、動作は遅くなる傾向がある。さて、Routerには、それが使われるNetwork層のサービスに応じ、Connection-orientedとConnectionlessのものがある。
・Connection - oriented
Connection-OrietendのサービスをInternetworking環境下で実現するには以下のようなことを行なう。
・データを送ろうとするホストはVirtual Circuitを設定する。（しかしながらこのVirtucal Circuitはルーターを経由していくのであった）
・隣接した二つのRouterは同じサブネットに接続されている必要がある。
・End-to-EndのVirtual Circuitはネットワークパス上のVirtual Circuitを接続したものになる。
・Connectionless
DataGramの形態で用いられる。実際にIPで使われているのはこの形態だが、
「Routingはインターネットでは一般的に大変複雑である」
と一言かいてある。やることは概念的には単純で、ノードはRouterにパケットを送り、Routerは次のRouterにパケットを送り、、の繰り返しである。
送信元から送信先までの間には異なるDLC layerが用いられているかもしれない。そのたびに、パケットは異なるパケットにEncapsulateされることになる。またDLCごとにパケットの最大サイズがことなれば、パケットの分割、再結合が必要となる。
この「パケットの分割、再結合」はConnection-oritendの場合には避けることができる。なぜかといえば、Virtucal Cirrcuitのセットアップ時に「経路にあるすべてのDLCにおいての最小パケットサイズ」を設定して、そのサイズで送信する、ということが可能だからだ。ところがConnectionlessの場合にはパケットごとにまったく違うネットワークを経由していくこともありえるわけだから、こうした「パケットの分割」はパケットごとに行われなければならない。
Network Layerの例
さて、長々と説明してきたネットワーク層だが、ここでよく名前を聞くものについて、概略をば。
X.25：Virtucal Circuitベース。Internetworkingで、ネットワークの間の結合は、Half-Routerなるものが用いられる。このhalf-router間はX.75で結合される。
DARPA Internet：DataGramオペレーション。バックボーンのネットワークでは最短経路をDistributionで計算する。またChannnel Queue LimitによるCOngestion Controlを行なう。
MAP/TOPのNetwork layer：OSI Connectionless Internetworkプロトコル。IPに類似。