ネットワークスケジューラは、パケットスケジューラ、キューイング規律（qdisc）、またはキューイングアルゴリズムとも呼ばれ、パケット交換通信ネットワークにおけるノード上のアービタです。プロトコルスタックとネットワークインターフェースコントローラの送信キューと受信キューにおけるネットワークパケットの順序を管理します。様々なオペレーティングシステムに対応した複数のネットワークスケジューラが存在し、既存のネットワークスケジューリングアルゴリズムの多くを実装しています。
ネットワークスケジューラロジックは、次にどのネットワークパケットを転送するかを決定します。ネットワークスケジューラはキューイングシステムと連携し、ネットワークパケットを転送されるまで一時的に保存します。システムは1つまたは複数のキューを持つ場合があり、それぞれのキューは1つのフロー、分類、または優先度のパケットを保持します。
場合によっては、システムの制約内ですべての送信をスケジュールすることができないことがあります。このような場合、ネットワークスケジューラはどのトラフィックを転送し、どのトラフィックをドロップするかを決定する責任を負います。
用語と責任
ネットワーク スケジューラは、特定のネットワーク トラフィック制御イニシアチブの実装を担当する場合があります。ネットワーク トラフィック制御は、ネットワークの輻輳、遅延、およびパケット損失を削減するためのすべての対策を包括する用語です。具体的には、アクティブ キュー管理(AQM) は、キューに入れられたネットワーク パケットを選択的にドロップすることで、過度のネットワーク輻輳を防ぐという大きな目標を達成します。スケジューラはドロップするパケットを選択する必要があります。トラフィック シェーピングは、キューに入れられたパケットがバーストした場合に送信パケットを遅らせることで、トラフィック フローの帯域幅要件を平滑化します。スケジューラは、送信パケットのタイミングを決定します。サービス品質(QoS) は、サービス クラス (差別化サービス) または予約接続 (統合サービス)に基づいてトラフィックを優先順位付けすることです。
アルゴリズム
長い歴史の中で、多くのネットワークキューイング規律が開発されてきました。これらの規律はそれぞれ、様々な送信バッファまたは受信バッファ内でネットワークパケットの順序変更やドロップを行うものです。[ 1 ]キューイング規律は、特定のネットワークパケットクラスの遅延の 削減など、様々なネットワーク環境を補正するための手段として一般的に利用されており、一般的にはQoS（Quality of Service）対策の一部として利用されています。[ 2 ] [ 3 ] [ 4 ]
クラスフルキューイング規則では、木の枝のように機能するクラスを作成できます。各クラスにパケットをフィルタリングするためのルールを設定できます。各クラスには、他のクラスフルキューイング規則またはクラスレスキューイング規則を割り当てることができます。クラスレスキューイング規則では、他のキューイング規則を追加することはできません。[ 5 ]
ネットワーク トラフィックの管理に適したアルゴリズムの例は次のとおりです。
| アルゴリズム | 頭字語 | タイプ | ハードウェアサポート |
|---|---|---|---|
| 汎用セルレートアルゴリズム | GCRA | ||
| 応答しないフローに対して選択して強制終了する | チョーク | 階級のない | |
| 制御された遅延 | コードル | 階級のない | |
| 共通アプリケーションの強化を維持[ 6 ] | ケーキ | ||
| 最も早いTxTimeを優先 | ETF | 階級のない | はい |
| 先入先出 | 先入れ先出し法 | 階級のない | |
| 公平な待ち行列 | よくある質問 | 階級のない | |
| 公平なキューイング制御された遅延 | FQ-CoDel | 階級のない | |
| 比例積分コントローラによるフローキューイングの強化 | FQ-PIE | 階級のない | |
| 一般化ランダム早期検出 | グレッド | 階級のない | |
| ヘビーヒッターフィルター[ 7 ] | HHF | 階級のない | |
| マルチキュー優先度 | MQ-PRIO | 階級のない | はい |
| マルチキュー | マルチQ | 階級のない | はい |
| ネットワークエミュレータ[ 8 ] | ネテム | 階級のない | |
| 比例積分制御器強化版[ 9 ] | パイ | 階級のない | |
| ランダム早期検出 | 赤 | 階級のない | |
| ストキャスティックフェアブルー | SFB | 階級のない | |
| 確率的公平性キューイング | SFQ | 階級のない | |
| トークンバケットフィルター | TBF | 階級のない | |
| クラスベースのキューイング | CBQ | 上品な | |
| クレジットベースのシェイパー | CBS | 上品な | はい |
| 赤字ラウンドロビン[ 10 ] | 防災 | 上品な | |
| 強化されたトランスミッション選択 | ETS | 上品な | |
| 階層的公正サービス曲線 | HFSC | 上品な | |
| 階層型トークンバケット[ 11 ] | HTB | 上品な | |
| 優先度 | プリオ | 上品な | |
| クイックフェアキューイング[ 12 ] | クワッド | 上品な | |
| 時間を考慮した優先度設定 | タプリオ | 上品な | はい |
上記のいくつかはLinuxカーネルモジュール[ 13 ] [ 14 ]として実装されており、無料で入手できます。
バッファブロート
バッファブロートとは、パケット交換ネットワークにおいて、パケットの過剰なバッファリングによって遅延の増加やパケット遅延の変動が生じる現象です。バッファブロートは、ネットワークスケジューラによって戦略的にパケットを破棄することで、不必要に高いバッファリングバックログを回避することで対処できます。例としては、CoDel、FQ-CoDel、ランダム早期検出などが挙げられます。
実装
![[アイコン]](/wiki/File:Wiki_letter_w_cropped.svg) | このセクションは拡張が必要です。不足している情報を追加していただければ幸いです。 （2018年10月） |
Linuxカーネル
Linux カーネル パケット スケジューラは、Linux カーネルのネットワーク スタックの不可欠な部分であり、すべての NIC の 送信および受信リング バッファを管理します。
パケットスケジューラは、（トラフィック制御tcの略）と呼ばれるユーティリティを使用して設定されます。デフォルトのキューイング規則として、パケットスケジューラはpfifo_fastと呼ばれるFIFO実装を使用しますが[ 15 ] 、 systemdのバージョン217以降ではデフォルトのキューイング規則がに変更されています。[ 16 ]fq_codel
およびユーティリティを使用するifconfigとip、システム管理者は各デバイスのバッファサイズtxqueuelenとを、rxqueuelenイーサネットフレームのサイズに関係なく、個別に設定できます。Linuxカーネルのネットワークスタックには、ネットワークスケジューラによって管理されない他のバッファがいくつか含まれています。[ a ]
Berkeley Packet Filterフィルタは、パケットスケジューラの分類器に接続できます。2015年にLinuxカーネルバージョン4.1で導入されたeBPF機能は、従来のBPFプログラマブル分類器をeBPFに拡張しました。 [ 17 ]これらはLLVM eBPFバックエンド を使用してコンパイルし、ユーティリティを使用して実行中のカーネルにロードできますtc。[ 18 ]
BSDとOpenBSD
ALTQはBSD用のネットワークスケジューラの実装です。OpenBSDバージョン5.5以降、ALTQはHFSCスケジューラに置き換えられました。
セルフリーネットワークスケジューリング
通信ネットワークにおけるスケジューラは、パケットの優先順位付け、タイミング、リソース配分などのリソース割り当てを管理します。高度な実装では、現代のネットワーク構成の複雑さに対処するために、人工知能（AI）を活用するケースが増えています。例えば、セルフリーネットワークでは、複数の無線ユニット（RU）とユーザー機器（UE）間の相互作用を効率的に処理するために、教師ありニューラルネットワーク（NN）ベースのスケジューラが導入されています。このアプローチは、計算の複雑さを軽減しながら、遅延、スループット、リソース割り当てを最適化するため、5G以降のネットワークにとって有望なソリューションとなっています。[ 19 ]
参照
注記
- ^すべてのバッファの全体的なサイズは、 Bufferbloatプロジェクトによる批判の焦点となってきました。同プロジェクトは、主にOpenWrtでテストされた CoDel による部分的な解決策を提供しました。
参考文献
- ^ 「Traffic Control HOWTO: Classless Queuing Disciplines (qdiscs)」tldp.org . 2014年2月22日時点のオリジナルよりアーカイブ。2013年11月24日閲覧。
- ^ 「Traffic Control HOWTO: Linux Traffic Controlのコンポーネント」 . tldp.org . 2014年2月18日時点のオリジナルよりアーカイブ。2013年11月24日閲覧。
- ^ 「交通管制HOWTO：交通管制の伝統的な要素」tldp.org . 2013年5月27日時点のオリジナルよりアーカイブ。2013年11月24日閲覧。
- ^ 「Queuing Disciplines: Order of Packet Transmission and Dropping」(PDF) . tau.ac.il . 2006年10月25日. 2016年3月4日時点のオリジナルよりアーカイブ(PDF) . 2014年3月18日閲覧。
- ^ “Advanced traffic control - ArchWiki” . wiki.archlinux.org . 2023年9月22日時点のオリジナルよりアーカイブ。 2023年9月11日閲覧。
- ^ 「Let them run CAKE」 . LWN.net . 2024年11月12日時点のオリジナルよりアーカイブ。2019年9月3日閲覧。
- ^ 「Heavy-Hitter Filter qdisc」 . kernel.org . 2017年2月22日時点のオリジナルよりアーカイブ。 2016年7月25日閲覧。
- ^ 「ネットワークエミュレーター Linuxカーネルネットワークスケジューラモジュール」 . kernel.org . 2017年2月22日時点のオリジナルよりアーカイブ。2013年9月7日閲覧。
- ^ 「Proportional Integral controller Enhanced (PIE)」 . kernel.org . 2017年2月22日時点のオリジナルよりアーカイブ。 2016年7月25日閲覧。
- ^ 「DRR Linuxカーネルネットワークスケジューラモジュール」 . kernel.org . 2017年2月23日時点のオリジナルよりアーカイブ。2013年9月7日閲覧。
- ^ 「HTB Linuxカーネルネットワークスケジューラモジュール」 . kernel.org . 2013年9月7日閲覧。
- ^ 「QFQ Linuxカーネルネットワークスケジューラモジュール」 . kernel.org . 2017年2月23日時点のオリジナルよりアーカイブ。2013年9月7日閲覧。
- ^ 「Linuxカーネルネットワークスケジューラ」 . kernel.org . 2012年12月26日. 2013年9月7日閲覧。
- ^ "tc(8) - Linuxマニュアルページ" . man7.org . 2023年9月7日時点のオリジナルよりアーカイブ。2023年9月11日閲覧。
- ^ 「Linux Advanced Routing and Traffic Control HOWTO、セクション9.2.1. pfifo_fast」 . lartc.org . 2012年5月19日. 2014年9月21日時点のオリジナルよりアーカイブ。 2014年9月19日閲覧。
- ^ "systemd システムおよびサービスマネージャ: NEWS ファイル" . freedesktop.org . 2015年5月22日. 2014年12月22日時点のオリジナルよりアーカイブ。 2015年6月9日閲覧。
- ^ 「Linuxカーネル4.1、セクション11. ネットワーク」 . kernelnewbies.org . 2015年6月21日. 2015年10月16日時点のオリジナルよりアーカイブ。 2016年4月19日閲覧。
- ^ 「BPFおよびXDPリファレンスガイド」。Ciliumドキュメントウェブサイト。2018年4月24日時点のオリジナルからアーカイブ。 2018年8月21日閲覧。
- ^ Huleihel, Yara; Maman, Gil; Hadad, Zion; Shasha, Eli; Permuter, Haim H. (2025). 「データ駆動型セルフリースケジューラ」.アドホックネットワーク. 169 103738. Elsevier. doi : 10.1016/j.adhoc.2025.103738 .
