技術要約：大規模な決定論的ネットワークのための、非ワークコンザービング（非仕事保存型）ステートレス・コア・フェア・キューイング・スケジューラ

問題提起

決定論的ネットワーク（Detnet）は、大規模なネットワークにおいて、参加するフローに対してエンドツーエンド（E2E）の遅延およびジッタの厳格な境界を保証することを目指している。小規模なネットワークで伝搬遅延が低い場合には決定論的なパフォーマンスを実現できるが、これらのソリューションを大規模なネットワークへとスケールアップさせるには、大きな課題が存在する。既存のアプローチには以下の具体的な制限がある：

• ステートフル・フェア・キューイング（例：PGPS、WFQ）： これらは最適なフロー隔離と遅延境界を提供するが、すべてのノードにおいて、フローごとの状態情報（具体的には前パケットの終了時刻）を保持する必要がある。数百万のフローを処理するコアノードにおいて、この状態管理の複雑さ（$O(N)$）は、ラインレートでの処理を困難にする。
• ワークコンザービングなステートレス・スケジューリング（例：C-SCORE）： スケーラビリティに対処するため、IETF DetNetワーキンググループおよびITU-TはC-SCOREを標準化している。この手法は、フローの状態をメタデータ（終了時刻：FT）としてパケットヘッダー内に転送することで、コアノードにフロー状態を保持させる必要性を排除する。しかし、C-SCOREはワークコンザービング（リンクがアイドル時にパケットを即座に送信する）であるため、決定論的なジッタ保証を提供できない。ジッタはE2E遅延の境界と同じ幅まで変動し得る。
• 代替メカニズム（TSN、CJVC）： IEEE 802.1 TSNにおけるタイムアウェア・シェーピング（TAS）や、サイクリック・キューイング・アンド・フォワーディング（CQF）はジッタ制御を実現するが、スケジューリングのNP困難性、厳格な同期要件、またはサイクルタイムの制限によるスケーラビリティの問題に直面する。コア・ステートレス・バーチャル・クロック（CJVC）はジッタを低減しようとするが、過剰なメタデータと、送信前のサービス完了時間の予測といった複雑な計算を必要とし、リアルタイム処理において負担が大きい。

手法

著者らは、スケーラビリティを犠牲にすることなく決定論的なジッタを提供するために設計された、C-SCOREフレームワークの進化形であるN-SCORE（Non-work conserving Stateless Core fair queuing）を提案している。

コア・アルゴリズム

N-SCOREは、フローの状態をパケットメタデータとして運ぶというC-SCOREのステートレスな性質を維持しつつ、**Eligible Time（ET：適格時刻）パラメータを用いた非ワークコンザービング（Non-Work Conserving）**メカニズムを導入している。

1. メタデータの伝搬：
   • Finish Time (FT)： エントランスノードで計算され、コアノードで更新される。これは理想的なサービス完了時刻を表す。
   • Eligible Time (ET)： エントランスノードで計算され、コアノードで更新される新しいパラメータである。これはパケットがサービスを開始することを許可される最も早い時刻を定義する。
2. スケジューリング・ロジック：
   • パケットはFTに基づいて（昇順で）キュー内でソートされる。
   • 非ワークコンザービング制約： パケットは、現在の時刻がそのET以上である場合にのみサービスを受けることができる。たとえリンクがアイドル状態であっても、ETより前に到着したパケットは待機しなければならない。
   • この強制的な待機期間により、ワークコンザービングなシステムにおいてジッタを引き起こす原因となるリンク利用率の「バースト性」を防止する。
3. 数学的定式化：
   • ノード $h$ におけるFTは、$F_h(p) = F_{h-1}(p) + d_{h-1}(p)$ として更新される。これはC-SCOREと同一である。
   • ETは、$E_h(p) = E_{h-1}(p) + d_{h-1}(p)$ として更新される。ここで $d$ はノード遅延因子および伝搬/クロック差を含む。
   • サービス間隔は $(E_h(p), F_h(p)]$ と定義される。著者らは、同一フローの連続するパケット間のこれらの間隔が重複しないことを証明している。

理論的導出

本論文は、以下の境界に関する厳密な数学的証明を提供している：

• E2E遅延の上限（Upper Bound）： ステートフル・フェア・キューイング（PGPS）およびC-SCOREと同一であることが証明されている。この境界は、フロー固有のパラメータ（バーストサイズ、パケット長、サービスレート）およびノード遅延因子の関数であり、ネットワーク利用率には依存しない。
• E2E遅延の下限（Lower Bound）： ET制約に基づいて導出されており、パケットが経験しなければならない最小限の遅延を確立している。
• ジッタ境界： 上限と下限の差として定義される。分析によれば、N-SCOREは非ワークコンザービングな挙動によって下限が引き上げられるため、ワークコンザービングなスキームと比較してジッタを大幅に低減する。
• バッファ占有量： ノードあたりのバッファ要件は、近似的に $3NL$（$N$ はフロー数、$L$ は最大パケットサイズ）によって制限される。この控えめな要件は、重複しないサービス間隔から導出されている。

主な貢献

1. N-SCOREの提案： 大規模ネットワークにおいて、コアノードにフローごとの状態を保持させることなく、決定論的なジッタ保証を実現する新しいスケジューラ。
2. 最適性の理論的証明： N-SCOREがステートフル・フェア・キューイングの最適なE2E遅延上限を維持しつつ、優れたジッタ抑制を実現するという厳密な証明。
3. バッファ複雑性の分析： ノードのバッファ要件の特性評価を行い、$\approx 3NL$ という上限を確立することで、他の文脈におけるPIFO（Push-In First-Out）キューイングと比較して実装の複雑さを軽減した。
4. 標準化の文脈： 本研究は、IETF DetNet WGのワーキンググループ・ドラフトとして採用されたことが記されている。

結果

著者らは、SimPyフレームワークを用い、部分メッシュネットワーク・トポロジー（7ホップ、1 Gbpsリンク）における広範なシミュレーションを通じてN-SCOREを検証した。研究では、車載ネットワークに典型的な3種類のフロータイプ（Audio、Video、Command & Control）の下で、N-SCOREをCQF、Enhanced CQF (ECQF)、ATS with ECQF、CJVC、およびC-SCOREと比較した。

• 遅延性能：
  • N-SCOREは、C-SCOREおよびCJVCと同一のE2E遅延上限を達成した。
  • CQFを除くすべてのスケジューラは、高利用率（93.6%）下でVideoフローの10 msのデッドライン要件を満たした。
  • C-SCOREは（ワークコンザービングであるため）最も低い絶対遅延を達成したが、N-SCOREは同じ理論的上限を維持した。
• ジッタ性能：
  • AudioおよびCommand & Controlフローにおいて、N-SCOREとCJVCは、CQFベースのスケジューラを大幅に上回る最低レベルのジッタを示した。
  • Videoフローについては、N-SCORE、CJVC、CQF、およびECQFを含むすべてのスケジューラが、約8 msの同様のジッタレベルを示した。これは、デッドライン要件を満たすためにVideoフローに適用されたシェーピング遅延に起因しており、この特定のフロータイプにおけるジッタ特性を支配していた。
  • C-SCOREは、ワークコンザービングな性質により、AudioおよびCommand & ControlフローにおいてN-SCOREやCJVCよりも高いジッタを示し、リンク効率とジッタ制御のトレードオフを裏付けた。
• バッファ占有量：
  • 93.6%の利用率におけるシミュレーションにより、すべてのノードで観測された最大バッファ占有量が、論文で導出された理論的上限を一貫して下回っていることが確認された。

意義

本論文は、N-SCOREを、大規模な決定論的ネットワークのための重要な進歩として位置づけている。その主な意義は、スケーラビリティと決定論的なジッタの間の長年のトレードオフを解決したことにある。

• コアノードにフロー状態を保持させる必要性を排除することで、N-SCOREは、ステートフルなアプローチが計算量的に不可能な大規模ネットワークへのフェア・キューイング原理の導入を可能にする。
• ETを用いた非ワークコンザービング・メカニズムを導入することで、N-SCOREは（C-SCOREの欠点である）ジッタ保証の欠如を、CJVCのような高いメタデータや計算オーバーヘッドを負うことなく克服している。
• 著者らは、N-SCOREが「両方の良いとこ取り」を実現する実用的な経路を提供すると結論付けている。すなわち、ステートフル・フェア・キューイングの最適な遅延上限と、非ワークコンザービング・システムのジッタ抑制の両立である。同時に、ハードウェア実装に適したバッファ・フットプリントも維持している。

なお、N-SCOREはジッタを大幅に改善するものの、単一のフローからの大きなバーストは、バースト内の最初のパケットと最後のパケットの間のE2E遅延の差により、依然としてジッタを引き起こす可能性があると論文は指摘している。著者らは、この影響をさらに軽減するために、バーストを単一のエンティティ（「フローレット」に類似）として扱う今後の研究の可能性を示唆している。