# フロースケジューリング ## 定義 フロースケジューリング(flow scheduling)とは、データセンターネットワークのマルチパストポロジにおいて、ネットワーク全体の状態を把握した上でフローに対して非衝突の転送パスを動的に割り当てる技術である。集約ネットワーク利用率(二分帯域幅 bisection bandwidth)を最大化することを主目的とする。 フローは一般に規模によって 2 種類に分類される: - **エレファントフロー(elephant flows)**: 少数・大容量・長寿命のフロー(例: MapReduce シャッフル、バックアップ転送)。ハッシュ衝突の影響を直接受け、スケジューリングの主対象となる - **マウスフロー(mouse flows)**: 多数・小容量・短寿命のフロー(例: RPC、検索クエリ応答)。流量の平均化でハッシュ衝突の影響が小さく、静的ハッシング(ECMP)でも比較的効率よく処理できる 集中型フロースケジューラは以下の制御ループで動作する([[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]]): 1. **検知**: エッジスイッチでフロー統計を収集し、閾値を超えた大フローを検知する 2. **需要推定**: TCP フローの現在の送信レートでなく、理想的なネットワーク下での達成可能帯域幅(自然需要 natural demand)を推定する 3. **配置計算**: フロー需要を入力として、非衝突パスを計算する(Global First Fit / Simulated Annealing 等) 4. **経路書き込み**: OpenFlow 等のプロトコルで対象スイッチの転送テーブルを更新する ## ECMP との関係 フロースケジューリングは[[ECMP]]を置き換えるものではなく補完するものである。マウスフロー(閾値以下)はデフォルト ECMP に委ねることで、スケジューラのオーバーヘッドを最小化しつつ両パターンで高い性能を達成する。 ECMP のハッシュ衝突がエレファントフロー支配的なワークロードで二分帯域幅を最大 60.8% 損失させることを Hedera(NSDI 2010)は定量的に示しており、フロースケジューリングの導入によってこの損失をほぼ解消できる。 ## スケジューリングアルゴリズム ### Global First Fit (GFF) フロー検知後、全等コストパスを線形検索して最初の収容可能なパスに貪欲割り当てを行う。時間計算量は O((k/2)²) でフロー数に非依存。反応が速い一方、高負荷時の最適性は保証されない。 ### Simulated Annealing (SA) 確率的探索アルゴリズムで、エネルギー関数(全リンクの容量超過量の総和)を最小化する。Hedera の核心的最適化は「フロー単位でなく宛先ホスト単位にコアスイッチを割り当てる」制約により探索空間を 1/10^12000 に削減すること。SA はほぼ全ての通信パターンで GFF を上回り、最適に漸近する。 ## TCP 自然需要推定 フロースケジューリングの精度はフロー需要の推定精度に直結する。TCP フローの現在送信レートはネットワーク輻輳で制限されており、理想的スケジューリング下での達成可能レートを反映しない。 Hedera の需要推定アルゴリズムは max-min 公平配分を反復計算で近似し、O(|F|) 時間で収束する。27,648 ホスト・250,000 フロー規模でも 200 ms 以内に完了する。 ## 横断的知見 - **「トポロジ設計」と「フロースケジューリング」は独立した問題として研究されたが、実際には不可分である**: Fat-Tree(SIGCOMM 2008)はコモディティスイッチで完全二分帯域幅を達成できるトポロジを提案した。しかし ECMP という転送プロトコルの制約により、この帯域幅はエレファントフロー時に活用できなかった。Hedera(NSDI 2010)はこのギャップを埋めるために登場し、トポロジの理論的上限に迫る実際の性能を実現した。2 論文を並べることで「設計と運用の乖離」が明確になる。(Source: [[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]]) ## 未解決の問い - 現代の 400 GbE / 800 GbE データセンターでは、スケジューリング間隔をサブ 100 ms にするための技術的障壁は何か。Hedera はテストベッド制約で 5 秒間隔だったが、理論的にはサブ秒が可能と主張している - RDMA / RoCEv2 環境では TCP と異なるフロー特性(バースト・マルチキャスト・集団通信)を持つ。エレファント/マウス分類の境界線はどこに置くべきか - 集中型スケジューラの単一障害点問題を解決しつつ、グローバル最適解に近い性能を維持できる分散型フロースケジューリングのアーキテクチャは確立されているか - 大規模 AI 学習クラスタ(All-to-All 通信支配的)での Hedera 型フロースケジューリングの適用可能性。GPU 集団通信は同期バリアを持つため、フロー寿命のパターンが MapReduce と根本的に異なる ## 関連 - 上位概念: [[負荷分散]] / [[データセンターネットワークトポロジ]] - 関連概念: [[ECMP]] / [[データセンター輻輳制御]] - 関連エンティティ: [[Mohammad Al-Fares]] / [[Amin Vahdat]] / [[Barath Raghavan]] / [[Sivasankar Radhakrishnan]] - 関連ソース: [[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]] ## 出典 - [[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]](集中型フロースケジューリングの最初の実用実装。Global First Fit と Simulated Annealing の 2 アルゴリズムを実装・評価。8,192 ホスト規模のシミュレーションで最適比 96% を達成)