パケット・スケジューリング

パケット・スケジューリング (Packet Scheduling) または単にスケジューリングとは、コンピュータネットワーク上のネットワーク機器において、パケットをそれが属するグループに応じたレートで送出することである。

 概要 
パケット・スケジューリングに使用されるアルゴリズムは、オペレーティング・システムなどにおけるスケジューリングと大きな違いはない。

スケジューリングの機構は、パケットをキューイングする機構とバッファ管理を行う機構とに論理的に分けることができる。スケジューリングは適切に制御することによってQoSを保証するのに役立つが、不適切なスケジューリング（キューイング）はQoSを劣化させる。ネットワーク機器の出口、特にLAN（ローカルエリア・ネットワーク）からWAN（広域ネットワーク）への接続点や、複数の入口から特定の出口に向かう点では、キューにパケットがたまりやすい。パケットがキューの中ですごす時間を制御できれば有効なQoS制御ができることになる。

 スケジューリングの方法 
代表的なスケジューリングの方法として優先キューイング、重み付き公平キューイング、クラスベース・キューイングがある。

 優先キューイング (Priority Queuing, PQ)
 最も基本的な方法であり、優先度が異なるクラスごとにキューを持ち、優先度の高いものから出力していく方法である。単純な機構であり、優先度の高いクラスのリアルタイム性が保証されるが、輻輳すると優先度の低いクラスが出力されなくなる可能性がある。クラシファイアによってクラス分けされたパケットは、優先度別にキューに入れられる。スケジューラは優先度が高いキューから順にパケットを取り出して出力していく。
 重み付き公平キューイング (Weighted Fair Queuing, WFQ)
 フロー（たとえば特定のユーザから他の特定のユーザへのTCPセッション）ごとにキューを割り当てて、フローごとに公平なキューイングを行う方法である。他のフローの影響を一定以下におさえることができるが、フローの数だけキューが必要になる。クラシファイアはフローごとのキューにパケットをいれる。スケジューラはラウンドロビン方式であり、各キューから公平にパケットを出力する。これによって、それぞれのフローは少なくとも1周に1回は処理される機会を得る。
 クラスベース・キューイング (Class-Based Queuing, CBQ)
 フローを階層的に制御するために、クラス毎に規定した使用量に応じたトラフィック制御を行うための方法である。スケジューラの出力はクラスごとに測定され、クラスに設定された上限値を超えた場合にはキューにペナルティが与えられる。スケジューラはそのペナルティを考慮したラウンドロビン方法によって出力する。これにより、クラスごとに「出力のn%まで」というような定量的な割合が定義できるようになる。

 関連項目 
 スケジューリング

Category:コンピュータネットワーク

en:Scheduling algorithm