OMSCS 2024 Fall (秋学期) に履修している Computer Networks に関して、中間テストに向けてここまでの授業の内容をまとめた。
Overall
ネットワークの基礎に関して、実装の課題を交えながら深く学べることを期待して 2024 Fall (秋学期) にこの授業を受講した。 中間テストと期末テストがあり、中間テストでは Week1-6 までの内容が対象のためここまでを大まかに整理した。第三者に手短に説明するためには本質を理解する必要があるため、内容を定着させるための良い機会になると考えた。
Week1
ネットワークの研究の歴史から始まり、OSI 7 レイヤーのモデルの各層に関して概要を学んだ。7 層に分けることで、柔軟性がありコスト効率的であるが、レイヤー毎に機能が重複する可能性などがデメリットとして挙げられている。ネットワークの実装の原則として、End-to-End (E2E) principle があり、ネットワーク内部には必要最低限の機能のみを持たせ、エンドシステムで新しいアプリケーション、プロトコルを実装するという設計思想である。ネットワークの中間デバイスに関わらず、パケットをドロップするなどの理由から Firewall や NAT はこの原則に則さないとされる。
また、Data Link layer の話にも入っていき、Bridge, Switch における Spanning Tree Algorithm についても触れられていた。Spanning Tree Algorithm に関しては、ネットワークトポロジーにおいて loop が存在すると、broadcast storm が生じるため、こちらを防ぐために各 Bridge, Switch 同士が情報連携する分散アルゴリズムである。
Week2
Transport Layer と Application Layer が中心の週であった。ホストで同時に複数のアプリを利用したい場合に、これを実現する方法が Transport layer で、port を追加の識別子とする Multiplexing (多重化) である。主な Transport Layer のプロトコルは TCP と UDP があり、パケットの品質に対して異なる考えだが、TCP においては Automatic Repeat Request (ARQ) などによってパケットの品質を保っている。
Transmission control (伝送制御) の一種として、TCP では受信側のバッファーがオーバーフローすることから保護するために Flow control とも呼ばれるレート制御メカニズムがある。受信側のバッファーにどの程度処理が残っているかを送信側に共有して、送信側が送るのを制御する仕組みである。その他には、ネットワーク輻輳によってパケットドロップなどから保護するために伝送速度を制御するCongestion control があり、ネットワークのキャパシティを超えないように制御するものである。End-to-End congestion control は Transport 層で動作し、送信側が送信したデータと ACK が返ってきたデータの差分から未確認データを算出し、ネットワークか受信側のキャパシティを超えないようにするものである。
ネットワークのキャパシティに関しては、徐々に送る packet を増やしていき、遅延などを観測した場合には、キャパシティのサイズを半分にする Additive Increase/Multiplicative Decrease (AIMD) が利用される。リンクを共有する接続が全て同じ RTT (Round-Trip Time) である場合、AIMD を採用していれば最終的にはそれぞれが平等にキャパシティを共有することとなり、公平性が保たれるとされる。一方、RTT が異なる場合は、RTT が短い方が AIMD によって早く増加するため、公平性は保たれない。
Week3
この週は Network Layer が中心であり、特に同一管理者内のルーティングである Interior Gateway Protocols (IGP) を対象としていた。フォワーディングとは 単一のルーター内で着信リンクから発信リンクにパケットを転送することで、ルーティングとは、ルーターがルーティングプロトコルを使用して連携して、パケットが送信元ノードから宛先ノードへの適切なパスを見つけることである。
ルーティングのアルゴリズムとして、Link-State algorithm と Distance Vector Routing algorithm に関して取り扱った。Link-State algorithm は、Dijkstra’s algorithm に基づいており、ネットワーク全体のトポロジ情報を各ルーターが保持する。Distance Vector Routing algorithm では Bellman Ford Algorithm がベースになっている。Distance Vector Routing algorithm では、隣接するルーターから経路情報を得るため、リンクが切断された際に状態を適切に反映した情報が送られず、ループが生じコストが無限に可算される Count-to-Infinity problem が発生することがある。この対策としては、コストが無限であることを返す Poison reverse がある。Routing Information Protocol(RIP) は Distance Vector Routing algorithm を利用し、RIP の次に導入された Open Shortest Path First (OSPF) では Link-State algorithm が利用されている。
最終的な宛先がネットワークの外部に存在する場合、ソースから最も近い Egress point を選択し、ネットワークを出ていくルーティングを Hot Potato Routing という。
Week4
Week 3 の Intradomain の話題に続き、Week 4 では Interdomain の内容に関して取り扱った。ネットワークのサービスを提供する ISP は、Global scale の Tier 1, Regional scale の Tier 2, Local の Tier 3 に分類される。Tier 3 は Tier 2 に接続し、Tier 2 は Tier 1 に接続するような階層構成になっていた。しかし、相互接続を行うような IXP やコンテンツを提供する CDN が登場したことで、階層構造がフラットになりつつある。Autonomous Systems (AS) は同じ管理権限で動作するルータのグループであり、AS 間のルーティング情報の連携は Border Gateway Protocol (BGP) であり、AS 内のやり取りは Interior Gateway Protocol (IGP) である。
AS 間の繋がりは、Transit と呼ばれるプロバイダーと顧客の関係と、Peering と呼ばれるトラフィックの交換を行うような関係がある。異なる AS 間の BGP セッションは eBGP と呼ばれ、同じ AS 間の BGP セッションは iBGP である。iBGP と IGP の違いは、iBGP は外部ルートを配布することが目的であるが、IGP は AS 内部のルータのパスを決定するものである。
IXP は AS 同士を Peering することができるが、多数の AS を Peering するため、IXP は Route Server を提供し各 AS のルート情報を管理することで、Multi-lateral BGP を実現している。
Week5
ルーターの詳細に関して学んだ。ルーターは Forwarding plane function と Control plane function を提供する。Forwarding plane function とは、入力リンク インターフェイスから適切な出力リンク インターフェイスにパケットを転送するアクションであり、非常に短いタイムスケールで完了することが求められる。主にハードウェアで実装されることが多い。Control plane function は、ルーティングプロトコルの実装、ルーティングテーブルの保守、フォワーディングテーブルの計算を行い、ソフトウェアで実装される。
インターネットの黎明期には、クラス (固定長プレフィックス) に基づく IP アドレスモデルが使用されていたが、IP アドレスの急速な枯渇によって、Classless Internet Domain Routing (CIDR) が台頭した。CIDR は基本的に、任意の長さのプレフィックスを使用して IP アドレスを割り当てる。CIDR はルーター テーブルのサイズを小さくするのに貢献したが、同時に、longest-matching-prefix lookup という新しい問題が生じるようになった。
スイッチング ファブリックは、入力ポートから出力ポート ポートにパケットをフォワーディングを行う。ルーターはパケットをフォワーディングするために、prefix-match lookup によってパケットの宛先アドレスを検索する。主に lookup で時間を要しているのは、メモリへのアクセスであったことから、Multibit tries によってメモリアクセスの回数を減らす工夫がされた。
Week6
近年、ネットワークの複雑さが増す中で、packet forwarding において、TCP フラッグや送信元 IP アドレスによって、パケットを制御する必要が生まれ、packet classification が注目されている。 宛先と送信元の IP アドレスのマッチングを効率的に行う方法として、Set-pruning tries や Backtracking approach が存在する。Set-pruning tries は高速であるがメモリを多く利用する。一方、Backtracking approach は低速であるがメモリの消費を抑えることができる。Grid of tries approach では、この二つの方法を融合させたような方法である。
入力ラインと出力ラインをつなげるスケジューリングにおいては、希望する出力ラインに一斉にリクエストを出す Take the Ticket があるが、出力ラインが重複した際に残りが待機する Head-of-line 問題が生じる。この問題を解決するため、各入力キューを出力リンク毎に仮想キューを使用した Parallel iterative matching によって、並列で処理が行われることが可能になった。
ルーターでは、スケジューリングが必要となるが、出力リンク バッファにおける先入れ先出しの FIFO with tail drop が最もシンプルな実装である。出力リンク バッファのキューがフルの状態で追加されたパケットはドロップされる。ドロップによる品質悪化を回避する方法として、最小の終了ラウンド番号を持つパケットを送信する Bit-by-Bit Round Robin scheduling が登場した。しかし、最小の終了ラウンド番号の算出に、priority queue の実装が必要となり、time complexity が高い。そのため、quantum size と deficit counter によって送信するパケットのサイズを決定する Deficit Round Robin (DRR) であれば、定数時間でスケジューリングが可能となる。
リンクの出力レートを制限する Traffic scheduling として、Policing と Shaping がある。Policing は、最大レートを超えると超過した部分はドロップされる。一方、Shaping では超過したパケットはバッファーなどに保存され、後ほど送信される。穴の開いたバケツのように、一定の速度で出力するアルゴリズムは Leaky Bucket と呼ばれ、Traffic policing と Traffic shaping で利用される。