負荷分散スイッチ

負荷分散スイッチは、クロスバーを介して各パケットを 2 回送信するコストをかけて、中央調停をまったく行わずに 100% のスループットを保証するスイッチ アーキテクチャです。負荷分散スイッチは、実用的な中央調停の限界を超えた大規模なルーターの研究対象です。^[曖昧]

インターネットルーターは通常、スイッチに接続されたライン カードを使用して構築されます。中程度の総帯域幅をサポートするルーターはスイッチとしてバスを使用することがありますが、高帯域幅のルーターは通常、何らかのクロスバー相互接続を使用します。クロスバーでは、各出力が 1 つの入力に接続されるため、情報はすべての出力に同時に流れます。パケット スイッチングに使用されるクロスバーは、通常、1 秒間に数千万回再構成されます。これらの構成のスケジュールは、ライン カードからの相互情報送信要求に応じて、 Wavefront アービターなどの中央アービターによって決定されます。

完全なアービトレーションでは、スループットは各クロスバー入力または出力の最大スループットによってのみ制限されます。たとえば、ライン カード A と B に着信するすべてのトラフィックがライン カード C 宛ての場合、カード A と B が一緒に処理できる最大トラフィックは C によって制限されます。完全なアービトレーションには膨大な量の計算が必要であり、クロスバーのポート数よりもはるかに速くスケールアップすることがわかっています。実際のシステムでは、妥当な時間で計算できる不完全なアービトレーション ヒューリスティック (iSLIP など) が使用されます。

負荷分散スイッチは、負荷分散スイッチとは関係ありません。負荷分散スイッチは、Web サーバー ファームのフロントエンドとして使用され、単一の Web サイトへの要求を多数のサーバーに分散する一種のルーターを指します。

右の図に示すように、負荷分散スイッチには、それぞれがレート R の N 個の入力ライン カードがあり、それぞれがレート R/N のリンクによって N 個のバッファに接続されています。これらのバッファは、それぞれがレート R/N のリンクによって N 個の出力ライン カードに接続されています。中央のバッファは、N 個の仮想出力キューに分割されています。

各入力ライン カードはパケットを N 個のバッファに均等に分散しますが、これは明らかに競合なしで実行できます。各バッファはこれらのパケットを 1 つのバッファ ローカル メモリに合計速度 R で書き込みます。同時に、各バッファは各仮想出力キューの先頭にあるパケットを各出力ライン カードに送信します。この場合も各カードに速度 R/N で送信されます。出力ライン カードは明らかにこれらのパケットを競合なしでラインに転送できます。

負荷分散スイッチ内の各バッファは共有メモリ スイッチとして機能し、負荷分散スイッチは基本的に共有メモリ スイッチを拡張する方法ですが、パケットを R/N の 2 倍のレートで転送することに関連する追加の遅延が発生します。

負荷分散スイッチを調査しているスタンフォード グループは、バッファの数がライン カードの数と等しい実装に集中しています。各ライン カードに 1 つのバッファが配置され、2 つの相互接続メッシュは実際には同じメッシュであり、ライン カードの各ペア間に 2R/N のレートを提供します。ただし、基本的な負荷分散スイッチ アーキテクチャでは、バッファをライン カードに配置する必要はなく、バッファとライン カードの数が同じである必要もありません。

負荷分散スイッチの興味深い特性の 1 つは、ライン カードをバッファに接続するメッシュはすべてのライン カードをすべてのバッファに接続する必要があるものの、メッシュが非ブロッキング クロスバーとして機能する必要はなく、接続があらゆるトラフィック パターンに応答する必要もないことです。このような接続は、中央で調停されるクロスバーよりもはるかに単純です。

同じ出力宛ての 2 つのパケットが 1 つのライン カードに連続して到着すると、それらのパケットは 2 つの異なるバッファに分散され、それぞれのバッファの占有状況も異なるため、出力に配信されるまでにパケットの順序が入れ替わる可能性があります。順序の入れ替えは合法ですが、順序が入れ替わったパケットではTCP のパフォーマンスが悪くなるため、通常は望ましくありません。

さらなる遅延とバッファリングを追加することで、負荷分散スイッチはローカル情報のみを使用してフロー内のパケット順序を維持できます。このようなアルゴリズムの 1 つが FOFF (Fully Ordered Frames First) です。FOFF には、異常なトラフィック パターンに対する脆弱性を排除し、優先順位を実装するためのメカニズムを提供するという追加の利点があります。

スタンフォード大学の Tiny Teraプロジェクト ( Abrizioを参照) では、スイッチング ファブリック自体に少なくとも 2 つのチップ設計 (クロスバー スライスとアービター) を必要とするスイッチ アーキテクチャが導入されました。アービターをアップグレードして負荷分散機能を含め、これらのデバイスを組み合わせると、信頼性、コスト、スループットの面で利点が得られます。

負荷分散スイッチのライン カードは物理的に互いに近接している必要がないため、大陸全体または地球規模のバックボーン ネットワークを相互接続メッシュとして使用し、コア ルーターを「ライン カード」として使用するという実装方法があります。このような実装では、すべての遅延が最悪の場合の伝送遅延の 2 倍に増加するという問題があります。しかし、次のような興味深い利点がいくつかあります。

• 大規模なバックボーン パケット ネットワークは、通常、不完全な容量計画、輻輳、その他の問題に対処するために、膨大な過剰容量 (10 倍以上) を備えています。負荷分散スイッチ バックボーンは、システム全体で測定した場合、わずか 2 倍の過剰容量で 100% のスループットを実現できます。
• 大規模なバックボーン ネットワークの基盤は通常、迅速に切り替えられない光チャネルです。これらは、負荷分散スイッチのメッシュの一定速度の 2R/N チャネルに適切にマッピングされます。
• グローバル輻輳は発生していないため、グローバル輻輳情報に基づいてルート テーブルを変更する必要はありません。
• ノード障害が発生した場合の再ルーティングでは、光チャネルの構成を変更する必要があります。ただし、再ルーティングは事前に計算できます (障害が発生する可能性のあるノードの数は限られています)。また、再ルーティングによって輻輳が発生することはなく、その後にルート テーブルの変更が必要になります。

• 最適負荷分散 I. Keslassy、C. Chang、N. McKeown、D. Lee
• 光学技術を使用したインターネット ルーターのスケーリング I. Keslassy、S. Chuang、K. Yu、D. Miller、M. Horowitz、O. Solgaard、および N. McKeown