(57)【特許請求の範囲】
【請求項１】
ネットワーク内を所定の送信レートにて送信される複数のパケットからなる２以上のフローのキューに対し、パケットの転送開始時刻によって転送順を決定するパケットスケジューリング方法において、転送開始時刻が同時刻であるパケットが３以上で、そのうち送信レートの最も高いパケットより送信レートの低いパケット（以下、低レートパケットという。）が２以上である場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定することを特徴とするパケットスケジューリング方法。
【請求項２】
中央順位ほど送信レートが高くなるようにフローの転送順位を決定することを特徴とする請求項１に記載のパケットスケジューリング方法。
【請求項３】
新たなフローが追加され、かつ転送開始時刻が同時刻であるパケットが３以上で、そのうち低レートパケットが２以上であり、そのうち１のパケットが前記新たなフローに属する場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定することを特徴とする請求項１に記載のパケットスケジューリング方法。
【請求項４】
複数のフローに対応するＦＩＦＯキューと送信バッファとに接続され、前記ＦＩＦＯキューに格納されるパケットの転送開始時刻などを計算しこの計算結果に基づきパケットの転送順位を決定し、前記パケットを前記送信バッファに転送する機能を有するスケジューラを装備するパケットスケジューリング装置において、転送開始時刻が同時刻であるパケットが３以上で、そのうち送信レートの最も高いパケットより送信レートの低いパケット（以下、低レートパケットという。）が２以上である場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定する機能を有するスケジューラを装備することを特徴とするパケットスケジューリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットを格納する複数のキューからパケットと取り出し、転送するためのパケットスケジューリング方法に関し、特に開始時間公平キューイング（Ｓｔａｒｔ−ｔｉｍｅ  Ｆａｉｒ  Ｑｕｅｕｅｉｎｇ）（以下、ＳＦＱという。）を用いたパケットスケジューリング方法及びパケットスケジューリング装置に関する。
【０００２】
【従来の技術】
一般に、送信元から送信先へ連続して送信され、かつ同じルートを通る複数のパケット（以下、フローという。）がネットワーク内を転送される場合、パケットを転送するための転送制御には、各フローに対応する複数のキューに対し公平なキューイング機能が要求される。
従来、公平キューイング（Ｆａｉｒ  Ｑｕｅｕｅｉｎｇ）に関連し、重み付け公平キューイング（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｅｉｎｇ）（以下、ＷＦＱという。）や、ＷＦＱに比べ、計算コストの削減と低い遅延時間を保証するなどの特徴がある開始時間公平キューイング（Ｓｔａｒｔ−ｔｉｍｅ  Ｆａｉｒ  Ｑｕｅｕｅｉｎｇ）（以下、ＳＦＱという。）を用いたスケジューリング考案がなされている。
以下に、ＳＦＱを用いた従来のパケットスケジューリングについて図１を参照して説明する。
【０００３】
図１は、従来のパケットスケジューリング装置の構成図である。図１に示すように、スケジューラ１０は、キュー１〜Ｎ及び送信バッファ１１に接続されている。
【０００４】
図１において、フロー毎、すなわち送信元アドレス，宛先アドレス，プロトコル，セッションＩＤの組み合せ毎にパケットがキューイングされたキュー１〜Ｎは、それぞれ従来のＦＩＦＯキューで構成され、キュー１〜Ｎには個々のフローに対応するパケットが到着順に格納される。
【０００５】
パケットが到着すると、個々のキューの先頭パケットに対しスケジューラ１０でスケジューリングが行われる。スケジューラ１０はＳＦＱを実施するソフトウエアであり、まずキュー１〜Ｎにパケットが到着すると、到着したパケットの転送開始時刻などを計算し、この情報を各パケットの付加情報として記憶する。
キュー１〜Ｎの先頭パケットのうち、次に送信すべきパケットをスケジューリングするのは、前記付加情報をもとにスケジューラ１０が決定し、選択したパケットデータを該当するキューから送信バッファ１１へ転送し、転送元のキューから当該パケットを削除する。
【０００６】
そして、送信バッファ１１に格納されたパケットは、格納順に送出される。送信バッファ１１は、格納順にパケットが無くなるまで送出し続ける。
【０００７】
一般にＳＦＱでは、キューｉ（ｉ＝１，．．．，Ｎ）のｊ番目（ｊ＝０，．．．）のパケットをＰｉｊと表す。そして、このＰｉｊの直前のパケット（以下、直前パケットという。）の転送終了予定時刻をＦｉ（ｊ−１）とすると、Ｐｉｊの転送開始時刻Ｓｉｊが、
Ｓｉｊ＝ｍａｘ｛ｖ（Ａ（Ｐｉｊ）），  Ｆｉ（ｊ−１）  ｝    （式１）
（ｉ＝１，．．．，Ｎ；ｊ＝０，．．．）
となる。ここで、ｖ（Ａ（Ｐｉｊ））はＰｉｊがキューｉに到着した（格納された）仮想時刻を表し、ｍａｘ｛    ，  ｝は｛  ｝内の「，」で区切られた２つの値のうちの最大値を表す。また、直前パケットのパケット長及び転送開始時刻をそれぞれｌｉ（ｊ−１）及びＳｉ（ｊ−１）とし、キューｉに対応する送信レートをｒｉ（ｉ＝１，．．．，Ｎ）とした場合、Ｆｉ（ｊ−１）  は次式で表される。
Ｆｉ（ｊ−１）＝Ｓｉ（ｊ−１）  ＋  ｌｉ（ｊ−１）／ｒｉ          （式２）
（ｉ＝１，．．．，Ｎ；ｊ＝０，．．．）
【０００８】
ここで、ＳＦＱの具体的な実施例について図２を参照して説明する。
図２は、Ｎ＝５すなわち５フローの場合の転送開始時刻及び転送終了予定時刻の例を示しており、装置全体の送信レートＲ及び各送信レートｒｉ（ｉ＝１，２，３，４，５），パケット長ｌｉｊを
Ｒ＝ｒ１＋ｒ２＋ｒ３＋ｒ４＋ｒ５  ＝１
ｒ１＝１／２，ｒ２＝１／４，ｒ３＝ｒ４＝ｒ５＝１／１２
ｌｉｊ＝１  （ｉ＝１，２，３，４，５  ｊ＝０，１，２，．．．）
として以後の説明を行う。また図２に示す横軸ｔは転送開始時刻及び転送終了予定時刻を表し、各フローの最初のパケットの転送開始時刻が一致しているとしてこの時刻をｔ＝０とする。
【０００９】
式１及び式２を用いて各フローの最初のパケットの転送開始時刻と転送終了予定時刻とを計算すると、
キュー１に対して送信レートｒ１＝１／２なので、Ｓ１０＝０，Ｆ１０＝２となる。すなわちＳ１０，Ｆ１０間に１／２のレートで転送することになる。
キュー２に対しては送信レートｒ２＝１／４なので、Ｓ２０＝０，Ｆ２０＝４となる。すなわちＳ２０，Ｆ２０間に１／４のレートで転送することになる。
キュー３〜５に対しては送信レートｒ３＝ｒ４＝ｒ５＝１／１２なので、Ｓ３０＝Ｓ４０＝Ｓ５０＝０，Ｆ３０＝Ｆ４０＝Ｆ５０＝１２となる。すなわちＳ３０，Ｆ３０間、Ｓ４０，Ｆ４０間、Ｓ５０，Ｆ５０間に１／１２のレートで転送することになる。
同じように、後に続くパケットについても転送開始時刻と転送終了予定時刻とを得ることになる。以上のような結果により図２を得ると、次はこの計算結果に従いスケジューラ１０がパケットの転送順を決定（スケジューリング）する。
【０００１０】
ＳＦＱによるスケジューリングでは、Ｓｉｊが最小のパケットから転送するが、Ｓｉｊが同一のパケットが複数存在する場合の転送順の定義はない。このためパケット転送開始時刻の同じキューが複数存在する場合の、優先順位を決定するひつようがある。ここでは、キュー１，キュー２，キュー３，キュー４，キュー５の順（以下、同時刻の優先順位という。）にスケジューリングするものとする。
【００１１】
スケジューリング後のパケットの転送順を、図３を用いて説明する。ここで図３の横軸Ｔは実際の転送時刻を表す。
まず図２に示すようにｔ＝０でＳｉ０はいずれも０であるため、同時刻の優先順位に従ってＴ＝０でキュー１の先頭パケットＰ１０を最初に送信バッファ１１へ転送し、つづいてＴ＝１でキュー２の先頭パケットＰ２０，Ｔ＝２でキュー３の先頭パケットＰ３０，Ｔ＝３でキュー４の先頭パケットＰ４０，Ｔ＝４でキュー５の先頭パケットＰ５０の順に転送する。次に、ｔ＝２（図２）ではＰ１１のみであるのでＴ＝５でＰ１１を転送する。そして、ｔ＝４ではＳ１２＝Ｓ２１＝４で同時刻となるが、これも同時刻の優先順位により先にＴ＝６でＰ１２を転送し、後にＴ＝７でＰ２１を転送する。以下同様に、Ｔ＝８でＰ１３，Ｔ＝９でＰ１４，Ｔ＝１０でＰ２２，Ｔ＝１１でＰ１５を転送する。ｔ＝１２では、またＳ１６＝Ｓ２３＝Ｓ３１＝Ｓ４１＝Ｓ５１＝１２で同時刻となるが同様に同時刻の優先順位によりＴ＝１２でＰ１６を転送し、つづいてＴ＝１３でＰ２３，Ｔ＝１４でＰ３１，Ｔ＝１５でＰ４１，Ｔ＝１６でＰ５１を転送する。
【００１２】
以上のように、ＳＦＱを用いた従来のパケットスケジューリングは、パケットの転送開始時刻を計算しその情報と所定の同時刻の優先順位とをもとしてにスケジューラ１０が転送順位を決定していた。
【００１３】
しかし、ＳＦＱを用いた従来のパケットスケジューリングにおいて、パケット転送開始時刻の同じキューが複数存在する場合に、同時刻の優先順位にて決定された順位しだいでは、送信レートの比較的高いフローに属するパケットの転送が長時間にわたり集中してしまう場合がある。このため送信レートの比較的高いフローの平均遅延時間と送信レートの比較的低いフローの平均遅延時間との差が大きくなる。つまり、転送の遅延時間に偏りが生じる点で問題である。
ここで遅延時間とは、Ｐｉｊが実際に転送される時刻（図３の横軸Ｔで示した時刻）をＵ（Ｐｉｊ）とすると、
Ｕ（Ｐｉｊ）−Ｓｉｊ
で定義される。
【００１４】
【発明が解決しようとする課題】
本発明は以上の従来技術における問題に鑑みてなされたものであって、送信レートの異なる複数のキューに対してＳＦＱを用いてスケジューリングする場合に、送信レートの比較的高いフローのパケットの転送が時間的に集中するのを軽減することにより、送信レートの比較的高いフローのパケット転送の遅延時間と送信レートの比較的低いフローのパケット転送の遅延時間との差を軽減させるパケットスケジューリング方法を提供することを目的とする。
【００１５】
【課題を解決するための手段】
前記課題を解決する本出願第１の発明は、
ネットワーク内を所定の送信レートにて送信される複数のパケットからなる２以上のフローのキューに対し、パケットの転送開始時刻によって転送順を決定するパケットスケジューリング方法において、転送開始時刻が同時刻であるパケットが３以上で、そのうち送信レートの最も高いパケットより送信レートの低いパケット（以下、低レートパケットという。）が２以上である場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定することを特徴とするパケットスケジューリング方法である。
【００１６】
したがって本出願第１の発明のパケットスケジューリング方法によれば、転送開始時刻が同時刻であるパケットが３以上で、そのうち送信レートの最も高いパケットより送信レートの低いパケット（以下、低レートパケットという。）が２以上である場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定するので、送信レートの最も高いパケットが属するフローの転送順位を最初又は最後に決定する場合に生じる送信レートの最も高いパケットの転送の時間的集中が軽減され、送信レートの比較的高いフローのパケット転送の遅延時間と送信レートの比較的低いフローのパケット転送の遅延時間との差を軽減させるという利点がある。
ここで、フローとは、送信元から送信先へ連続して送信され、かつ同じルートを通る複数のパケットである。
【００１７】
また本出願第２の発明は、本出願第１の発明のパケットスケジューリング方法において、中央順位ほど送信レートが高くなるようにフローの転送順位を決定することを特徴とする。
【００１８】
したがって本出願第２の発明のパケットスケジューリング方法によれば、本出願第１の発明の利点があるとともに、転送開始時刻が同時刻であるパケットが３以上で、そのうち低レートパケットが２以上である場合は、中央順位ほど送信レートが高くなるようにフローの転送順位を決定するので送信レートの最も高いパケットの転送の時間的集中がより軽減され、送信レートの比較的高いフローのパケット転送の遅延時間と送信レートの比較的低いフローのパケット転送の遅延時間との差を軽減させるという利点がある。
ここで中央順位とは、全フロー数が２×ｍ（ｍは自然数）の場合はｍ番目又は（ｍ＋１）番目となり、全フロー数が２×ｍ＋１の場合は（ｍ＋１）番目となる。
【００１９】
また本出願第３の発明は、本出願第１の発明のパケットスケジューリング方法において、新たなフローが追加され、かつ転送開始時刻が同時刻であるパケットが３以上で、そのうち低レートパケットが２以上であり、そのうち１のパケットが前記新たなフローに属する場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定することを特徴とする。
【００２０】
したがって本出願第３の発明のパケットスケジューリング方法によれば、本出願第１の発明の利点があるとともに、新たなフローが追加され、かつ転送開始時刻が同時刻であるパケットが３以上で、そのうち低レートパケットが２以上であり、そのうち１のパケットが前記新たなフローに属する場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定するので、新たなパケット群が追加された場合でも送信レートの比較的高いフローのパケット転送の時間的集中が軽減され、送信レートの比較的高いフローのパケット転送の遅延時間と送信レートの比較的低いフローのパケット転送の遅延時間との差を軽減させるという利点がある。
【００２１】
前記課題を解決する本出願第４の発明は、複数のフローに対応するＦＩＦＯキューと送信バッファとに接続され、前記ＦＩＦＯキューに格納されるパケットの転送開始時刻などを計算しこの計算結果に基づきパケットの転送順位を決定し、前記パケットを前記送信バッファに転送する機能を有するスケジューラを装備するパケットスケジューリング装置において、転送開始時刻が同時刻であるパケットが３以上で、そのうち送信レートの最も高いパケットより送信レートの低いパケット（以下、低レートパケットという。）が２以上である場合は、前記低レートパケットが属するフローの転送順位を最初と最後に決定する機能を有するスケジューラを装備することを特徴とするパケットスケジューリング装置である。
【００２２】
【発明の実施の形態】
以下に本発明の一実施の形態のパケットスケジューリング方法につき図面を参照して説明する。以下は本発明の一実施形態であって本発明を限定するものではない。
【００２３】
実施の形態１
まず、本発明の実施の形態１のパケットスケジューリング方法につき、図４，図５，図６を参照して説明する。図４は本発明の実施の形態１のパケットスケジューリング装置を示す構成図である。
【００２４】
図４に示すように、スケジューラ２０には、キュー１〜Ｎが接続され、かつ送信バッファ１１にも接続されている。
【００２５】
図４においてまず、フロー毎、すなわち送信元アドレス，宛先アドレス，プロトコル，セッションＩＤの組み合せ毎にパケットがキューイングされたキュー１〜Ｎは、それぞれ従来のＦＩＦＯキューで構成され、キュー１〜Ｎには個々のフローに対応するパケットが到着順に格納される。
【００２６】
次に、個々のキューの先頭パケットに対しスケジューラ２０でスケジューリングが行われる。スケジューラ２０はＳＦＱを実施する前に、図４に示すキュー１〜Ｎに対応する各フローの送信レートをｒｉ（ｉ＝１，．．．，Ｎ）バイト／秒とすると、この送信レートに対してソート処理を行い１から中央順位までは昇順、中央順位からＮまでは降順になるよう並べ換える。この順番は、新たなフローが追加又は削除されるたびに各フローの送信レートｒｉ（ｉ＝１，．．．，Ｎ）に関してスケジューラ２０がソート処理を行い、同様の方法により並べ換えられる。
この後にＳＦＱを実施し、キュー１からキューＮへパケットが到着すると、到着したパケットの転送開始時刻などの情報を各パケットの付加情報として記憶する。キュー１からキューＮの先頭パケットのうち、次に転送すべきパケットのスケジューリングは、前記付加情報と並べ換えた順番とをもとにスケジューラ２０が決定（各パケットの転送開始時刻の順にスケジューリングする。）し、選択したパケットデータを該当するキューから送信バッファ１１へ移送し、転送元のキューから当該パケットを削除する。キュー１からキューＮに一度にパケットが到着した場合、各キューの転送開始時刻が等しくなるが、この場合には前記の並べ換えた順番に従い転送する。
【００２７】
そして、送信バッファ１１に格納されたパケットは、格納順に送出される。送信バッファ１１は、格納順にパケットが無くなるまで送出し続ける。
【００２８】
ここで、本発明の実施の形態１のパケットスケジューリング方法の具体的な実施例について図５を参照して説明する。
【００２９】
例としてＮ＝５すなわち５フローの場合を考えると、スケジューラ２０は、まず送信レートに関するソート処理を行う。そして１〜２までは昇順、３〜５までは降順に並べ替えることで図５の縦軸に示す優先順位を決定する。ここで、装置全体の送信レートＲ及び各送信レートｒｉ（ｉ＝１，２，３，４，５），パケット長ｌｉｊを
Ｒ＝ｒ１＋ｒ２＋ｒ３＋ｒ４＋ｒ５  ＝１
ｒ１＝１／２，ｒ２＝１／４，ｒ３＝ｒ４＝ｒ５＝１／１２
ｌｉｊ＝１  （ｉ＝１，２，３，４，５  ｊ＝０，１，２，．．．）
として以後の説明を行う。また横軸ｔは転送開始時刻及び転送終了予定時刻を表し、各フローの最初のパケットの転送開始時刻が一致しているとしてこの時刻をｔ＝０とする。
【００３０】
ＳＦＱの計算式を用いて各フローの最初のパケットの転送開始時刻と転送終了予定時刻とを計算すると、
キュー１に対して送信レートｒ１＝１／２なので、Ｓ１０＝０，Ｆ１０＝２となる。すなわちＳ１０，Ｆ１０間に１／２のレートで転送することになる。
キュー２に対しては送信レートｒ２＝１／４なので、Ｓ２０＝０，Ｆ２０＝４となる。すなわちＳ２０，Ｆ２０間に１／４のレートで転送することになる。
キュー３〜５に対しては送信レートｒ３＝ｒ４＝ｒ５＝１／１２なので、Ｓ３０＝Ｓ４０＝Ｓ５０＝０，Ｆ３０＝Ｆ４０＝Ｆ５０＝１２となる。すなわちＳ３０，Ｆ３０間、Ｓ４０，Ｆ４０間、Ｓ５０，Ｆ５０間に１／１２のレートで転送することになる。
同じように、つづくパケットについても転送開始時刻と転送終了予定時刻とを得ることになる。次に、この計算結果に従いスケジューラ２０がパケットの転送順を決定（スケジューリング）する。
【００３１】
スケジューリング後のパケット順を、図６を用いて説明する。ここで、図６におけるの横軸Ｔは実際の転送単位時刻を表す。ｔ＝０で、図５に示すようにＳｉ０はいずれも０であるため、並べ換えた順に転送する。つまり、Ｔ＝０でＰ３０，Ｔ＝１でＰ４０，Ｔ＝２でＰ１０，Ｔ＝３でＰ２０，Ｔ＝４でＰ５０の順に転送する。そして、Ｔ＝５でＰ１１を転送し、ｔ＝４でＳ１２＝Ｓ２１＝４で同時刻となるので、これも同様に並べ換えた順に従いＴ＝６でＰ１２を転送しＴ＝７でＰ２１を転送する。以下同様に、Ｔ＝８でＰ１３，Ｔ＝９でＰ１４，Ｔ＝１０でＰ２２，Ｔ＝１１でＰ１５を転送する。次に、ｔ＝１２においてもＳ３１＝Ｓ４１＝Ｓ１６＝Ｓ２３＝Ｓ５１＝１２で同時刻となるので、同様に並べ換えた順に従いＴ＝１２でＰ３１を転送しＴ＝１３でＰ４１，Ｔ＝１４でＰ１６，Ｔ＝１５でＰ２３，Ｔ＝１６でＰ５１を転送する。
【００３２】
以上のようにして、パケットの並べ換えた順と計算した転送開始時刻とをもとにスケジューラ２０が転送順位を決定し、決定した順にパケットデータを該当するキューから送信バッファ１１へ移送、その後転送元のキューから当該パケットを削除する。
【００３３】
そして、送信バッファ１１に格納されたパケットは、格納順に送出される。送信バッファ１１は、格納順にパケットが無くなるまで送出し続ける。
【００３４】
なお、スケジューラ１０の動作は、新たなフローが追加、又は削除されるたびに同様のソート処理と並べ替えとを行う。
【００３５】
実施の形態２
次ぎに本発明の実施の形態２のパケットスケジューリング方法につき図４，図７，図８を参照して説明する。なお、本発明の実施の形態２のパケットスケジューリング装置を示す構成は図４が示す構成と同様であるが、スケジューラ２０によるスケジューリングが実施の形態１の場合とは異なる。
【００３６】
図４においてまず、フロー毎、すなわち送信元アドレス，宛先アドレス，プロトコル，セッションＩＤの組み合せ毎にパケットがキューイングされたキュー１〜Ｎは、それぞれ従来のＦＩＦＯキューで構成され、キュー１〜Ｎには個々のフローに対応するパケットが到着順に格納される
【００３７】
次に、個々のキューの先頭パケットに対しスケジューラ２０でスケジューリングが行われる。スケジューラ２０はＳＦＱを実施する。この実施による個々のパケットの転送開始時刻と転送終了予定時刻との計算結果より、最小の転送開始時刻が同じ時刻で、かつそのようなパケットが所定数未満の場合、キュー１からキューＮへパケットが到着すると、到着したパケットの転送開始時刻などの情報を各パケットの付加情報として記憶する。
そして、最小の転送開始時刻が同じ時刻で、かつそのようなパケットが所定数以上の場合は、当該パケットの属するフローに対してのみ送信レートについてのソート処理を行う。つまりキュー１〜Ｎの送信レートをｒｉ（ｉ＝１，．．．，ｎ）バイト／秒とすると、当該フローの送信レートのみに対しソート処理を行い１から中央順位までは昇順、中央順位からＮまでは降順になるよう並べ換える。その後に再度ＳＦＱを実施し、キュー１からキューＮへパケットが到着すると、到着したパケットの転送開始時刻などの情報を各パケットの付加情報として記憶
する。
【００３８】
また、新たなフローが追加された場合、パケットの転送開始時刻と転送終了予定時刻との計算結果より、最小の転送開始時刻が同じ時刻で、かつそのようなパケットが所定数以上になると当該パケットの属するフローに対してのみ同様に送信レートについてのソート処理を行い、並べ換える。その後にＳＦＱを実施し、キュー１からキューＮへパケットが到着すると、到着したパケットの転送開始時刻などの情報を各パケットの付加情報として記憶する。
キュー１からキューＮの先頭パケットのうち、次に転送すべきパケットのスケジューリングは、前記付加情報と並べ換えた順番とをもとにスケジューラ２０が決定（各パケットの転送開始時刻の順にスケジューリングする。）し、選択したパケットデータを該当するキューから送信バッファ１１へ移送し、転送元のキューから当該パケットを削除する。
【００３９】
そして、送信バッファ１１に格納されたパケットは、格納順に送出される。送信バッファ１１は、格納順にパケットが無くなるまで送出し続ける。
【００４０】
ここで、本発明の実施の形態２のパケットスケジューリング方法の具体的な実施例についてを参照して説明する。
【００４１】
例として前記所定数＝３、Ｎ＝４すなわち４フローのパケット転送に、新たに１フローが追加されＮ＝５の５フローになった場合を考える。ここで、装置全体の送信レートＲ及び各送信レートｒｉ（ｉ＝１，２，３，４，５），パケット長ｌｉｊを
Ｒ＝ｒ１＋ｒ２＋ｒ３＋ｒ４＋ｒ５  ＝１
ｌｉｊ＝１  （ｉ＝１，２，３，４，５  ｊ＝０，１，２，．．．）
として以後の説明を行う。
図７に示すように、キューが１〜４の場合は、最小の転送開始時刻が同じ時刻のパケットがキュー２とキュー３とに属するパケットの２個だけなので送信レートについてのソート処理は行わない。しかし、図７に示すようなキュー５が追加されると、最小の転送開始時刻が同じ時刻のパケットが３個となるので、当該パケットの属するフローに対してのみ送信レートについてのソート処理を行う。つまり順番の初めからから中央順位までは昇順、中央順位から最後までは降順になるように各キューを近接して並べ換える。並べ替えによる各キューは、図８のように表される。
【００４２】
以上のようにして、パケットの並べ換えた順と計算した転送開始時刻とをもとにスケジューラ２０が転送順位を決定し、決定した順にパケットデータを該当するキューから送信バッファ１１へ移送、その後転送元のキューから当該パケットを削除する。
【００４３】
そして、送信バッファ１１に格納されたパケットは、格納順に送出される。送信バッファ１１は、格納順にパケットが無くなるまで送出し続ける。
【００４４】
以上のように、最小の転送開始時刻が同じ時刻で、かつそのようなパケットが所定数以上の場合に、当該パケットの属するフローに対してのみ送信レートについてのソート処理を行う。これにより、より計算量を少なくして、本発明の実施の形態１と同等な機能を提供できる利点がある。
【図面の簡単な説明】
【図１】従来のパケットスケジューリング装置の構成図
【図２】従来例の転送開始時刻及び転送終了予定時刻
【図３】従来例の転送時刻
【図４】本発明のパケットスケジューリング装置の構成図
【図５】実施の形態１の転送開始時刻及び転送終了予定時刻
【図６】実施の形態１の転送時刻
【図７】実施の形態２のソート追加前の転送開始時刻及び転送終了予定時刻
【図８】実施の形態２のソート追後前の転送開始時刻及び転送終了予定時刻
【符号の説明】
１〜Ｎ．キュー
１０．スケジューラ
１１．送信バッファ
Ｓｉｊ。＿＿転送開始時刻
Ｆｉ（ｊ−１）。＿＿転送終了予定時刻
【図１】
0003601592.tif 000002
【図２】
0003601592.tif 000003
【図３】
0003601592.tif 000004
【図４】
0003601592.tif 000005
【図５】
0003601592.tif 000006
【図６】
0003601592.tif 000007
【図７】
0003601592.tif 000008
【図８】
0003601592.tif 000009