JP2000101591A

JP2000101591A - セルスケジューラ

Info

Publication number: JP2000101591A
Application number: JP26691398A
Authority: JP
Inventors: Masayoshi Nabeshima; 正義鍋島; Naoaki Yamanaka; 直明山中
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 1998-09-21
Filing date: 1998-09-21
Publication date: 2000-04-07

Abstract

(57)【要約】【課題】パケットを意識したセルスケジューリングを
行いながら同一の帯域を共用している通信中のコネクシ
ョン間の公平性を満足しつつ、かつパケット転送時間を
短くする。【解決手段】複数のセルバッファが循環的にセルの送
出を行うと仮定した場合の各セルバッファのキュー長を
推定することにより、パケットを意識しないセル単位の
セルスケジューリングによるキュー長を推定する。推定
したキュー長と実際のキュー長とを比較することにより
セル単位のセルスケジューリングとパケットを意識した
セルスケジューリングとの較差を求め、これにしたがっ
て優先制御を実行する。さらに、パケット長にしたがっ
て優先順位を設定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はＡＴＭ(Asynchronou
s Transfer Mode)に利用する。本発明は上位レイヤのパ
ケットを複数のセルに分割して転送するＡＴＭ通信に利
用するに適する。本発明はＡＴＭ網を公平に利用する技
術に関する。

【０００２】

【従来の技術】ＡＴＭ網は、セルネットワークである
が、最近、上位レイヤであるパケットを意識した制御が
数多く提案されている。その中に、上位レイヤのパケッ
トを意識したセルスケジューリングがある。パケットを
意識したセルスケジューリングの目的は、パケットの転
送時間をできるだけ短くすることである。

【０００３】ここでセル転送時間を短くしただけでは、
パケット転送時間が短縮できない例を図９に示す。図９
では、スイッチに、パケットサイズ４のパケットを構成
するセルが、それぞれｔ＝１、２、３、４に到着したと
している。

【０００４】出力Ａでは、セルはそれぞれｔ＝２、ｔ＝
３、t ＝４、t ＝８に出力されているため、各セルのセ
ル転送時間は、（２−１）＝１、（３−２）＝１、（４
−３）＝１、（８−４）＝４となり、平均セル転送時間
は、（１＋１＋１＋４）／４＝１．７５となる。また、
パケット転送時間は、パケット転送時間を“パケットを
構成する最初のセルが到着してからパケットを構成する
最後のセルが出力されるまでの時間”と定義すると、
（８−１）＝７となる。

【０００５】出力Ｂでは、セルはそれぞれｔ＝３、ｔ＝
４、ｔ＝５、ｔ＝６に出力されているため、各セルのセ
ル転送時間は、（３−１）＝２、（４−２）＝２、（５
−３）＝２、（６−４）＝２となり、平均セル転送時間
は、（２＋２＋２＋２）／４＝２となる。また、パケッ
ト転送時間は、（６−１）＝５となる。

【０００６】すなわち、平均セル転送時間は、出力Ａの
方が出力Ｂより短いにも関わらず、パケット転送時間
は、出力Ｂの方が出力Ａより短くなる。よって、パケッ
ト転送時間を短くするには、従来のセルのみを意識した
セルスケジューリングに代わって、パケットを意識した
セルスケジューリングが必要となる。そのようなセルス
ケジューリングとして、パケットを構成する最後のセル
（ＥＯＰセル：ＥｎｄｏｆＰａｃｋｅｔセル）が到着
したコネクションのセルを優先的に出力する方法が提案
されている（曽田他、“パケットを基準としたＡＴＭセ
ルスケジューリング方式の検討，”1996年電子情報通信
学会通信ソサイエティ大会Ｂ−５４８）。以下にその手
順を示す。（１）全コネクションキューにおいて、パケットの切れ
目であるＥＯＰセルを含むキューがあるとき、その一つ
をラウンドロビンで選択する。（２）（１）で選択したキュー内のセルを先頭から最初
のＥＯＰセルまで連続して送信する。（３）ＥＯＰセルを含むキューが無くなるまで、
（１）、（２）を続ける。（４）ＥＯＰセルを含むキューが無くなったとき、セル
を含むキューの一つをラウンドロビンで選択する。（５）（４）で選択したキュー内のセルを最後まで送信
する。但し、途中で他のキューにＥＯＰセルがキューイ
ングされたとき、そのキューにおいて（２）を実行す
る。（６）セルを含むキューが無くなるまで、（４）、
（５）を続ける。

【０００７】

【発明が解決しようとする課題】このように、従来より
提案されている方式を用いることにより、パケット転送
時間を短くすることができる。しかし、利用可能な帯域
を、現在通信を行っているアクティブなコネクション間
で公平に分配することはできない。すなわち公平性を満
足することができない。それは、従来より提案されてい
る方式では、多くのトラヒックを出力しているコネクシ
ョン程、多くの帯域を得ることができるからである。

【０００８】つまり、従来より提案されているパケット
を意識したセルスケジューリングでは、公平性を満足し
つつ、かつパケット転送時間を短くすることはできない
という問題がある。

【０００９】そこで、本願出願人は、特願平１０−２５
５４５１号（本願出願時に未公開）により、パケットを
意識したセルスケジューリングを行いながら同一の帯域
を共有している通信中のコネクション間の公平性を満足
しつつ、かつパケット転送時間を短くすることができる
セルスケジューラを提案した。

【００１０】しかし、先願ではパケット長を意識した制
御を行っていないため、長さの短いパケットを送出して
いるコネクションのパケット転送時間がラウンドロビン
でセルを送出する場合に比べ、長くなるという問題があ
った。

【００１１】すなわち、コネクションが優先的にセルを
送出できるコネクションになる場合に、そのコネクショ
ンがこれから送出するセル数がある値以下ならば、優先
的にセルを送出できるコネクションの中でもさらに優先
的にセルを送出できるようにするといった階層的なセル
スケジューリング制御が望まれる。

【００１２】本発明は、このような背景に行われたもの
であって、パケットを意識したセルスケジューリングを
行いながら同一の帯域を共用している通信中のコネクシ
ョン間の公平性を満足しつつ、かつパケット転送時間を
短くすることができるとともに、パケット長にも配慮し
たセルスケジューラを提供することを目的とする。

【００１３】

【課題を解決するための手段】本発明はセルスケジュー
ラであって、到着したセルが一つのパケットを複数のセ
ルに分解して送信した複数のセルの最後尾のセルである
か否かを識別する識別手段と、到着したセルを各コネク
ション毎に格納する複数のセルバッファと、この複数の
セルバッファのうちセル読出しの優先権を付与するセル
バッファを判定する判定手段とを備え、この判定手段
は、前記最後尾のセルを含むセルバッファを前記優先権
を付与する候補とする選択手段を含むセルスケジューラ
である。

【００１４】ここで、本発明の特徴とするところは、前
記複数のセルバッファが循環的にセルの送出を行うと仮
定した場合の各セルバッファのキュー長を推定する手段
を設け、前記選択手段は、この推定する手段により推定
されたキュー長が実際のキュー長を下回るセルバッファ
に前記最後尾のセルが含まれるときこのセルバッファに
前記優先権を付与する手段を含み、前記優先権を付与す
る手段は、前記パケットの長さにしたがって優先順位を
設定する手段を含むところにある。

【００１５】前記優先順位を設定する手段は、所定のパ
ケット長よりもパケット長が短いパケットに対し前記所
定のパケット長よりもパケット長が長いパケットに比較
して上位の優先順位を設定する手段を含むことが望まし
い。

【００１６】このように、本発明は、パケットを意識し
たセルスケジューリングを行いながら同一の帯域を共用
している通信中のコネクション間の公平性を満足しつ
つ、かつパケット転送時間を短くすることができるとと
もに、パケット長に配慮することを特徴とする。

【００１７】すなわち、前記複数のセルバッファが循環
的にセルの送出を行うと仮定した場合の各セルバッファ
のキュー長を推定することにより、パケットを意識しな
いセル単位のセルスケジューリングによるキュー長を推
定することができる。このようにして推定したキュー長
をバーチャルキュー長と呼ぶことにすると、実際のキュ
ー長とこのバーチャルキュー長とを比較することによ
り、セル単位のセルスケジューリングとパケットを意識
したセルスケジューリングとの較差を求めることができ
る。

【００１８】つまり、バーチャルキュー長とは、通信中
のコネクション間で公平に帯域が分配されたときのキュ
ー長である。よって、実際のキュー長がバーチャルキュ
ー長より長いコネクションとは、公平な帯域より少ない
帯域を得ているコネクションであり、一方、実際のキュ
ー長がバーチャルキュー長より短いコネクションとは、
公平な帯域より多い帯域を得ているコネクションとな
る。

【００１９】したがって、実際のキュー長がバーチャル
キュー長より長いコネクションであり、かつ、ＥＯＰセ
ルがセルバッファに蓄積されているコネクションを優先
的にセルを送出できるコネクションとすることにより、
公平性を満足しつつ、パケット転送時間を短くすること
ができる。

【００２０】このとき、本発明では、パケット長に配慮
し、長さの短いパケットを送出しているコネクションの
パケット転送時間がラウンドロビンでセルを送出する場
合に比べ、長くなるという問題を解決する。すなわち、
ＥＯＰセルを含むセルバッファが複数存在するときに
は、その中で、パケット長の短いパケットを含むセルバ
ッファに高い優先順位を与えることによりこの問題を解
決する。

【００２１】前記優先順位を設定する手段により前記優
先順位が設定されたセルバッファに対し前記最後尾のセ
ルが送出されるまでセルの送出を許可する送出権を付与
する手段を備えることが望ましい。

【００２２】また、前記送出権を付与する手段は、前記
送出権が付与されたセルバッファが前記最後尾のセルを
送出したときには、その送出権を他のセルバッファに移
行する手段を備えることが望ましい。

【００２３】すなわち、一つのパケットを構成する一連
のセルを送出し終えたときには、他のセルバッファに送
出権を移行することにより、同じく送出権を得る条件を
有する複数のセルバッファ間でのセル送出機会の均等を
確保することができる。

【００２４】

【発明の実施の形態】発明の実施の形態を図１を参照し
て説明する。図１は本発明実施例のセルスケジューラの
要部ブロック構成図である。

【００２５】本発明はセルスケジューラであって、図１
に示すように、到着したセルが一つのパケットを複数の
セルに分解して送信した複数のセルのＥＯＰセルである
か否かを識別するＶＣＩ識別部１と、到着したセルを各
コネクション毎に格納する複数のセルバッファ６₁〜６
_nと、このセルバッファ６₁〜６_nのうちセル読出しの
優先権を付与するセルバッファ６_i（ｉ＝１〜ｎのいず
れか）を判定する判定部３とを備え、この判定部３は、
前記ＥＯＰセルを含むセルバッファを前記優先権を付与
する候補とするセルスケジューラである。

【００２６】ここで、本発明の特徴とするところは、セ
ルバッファ６₁〜６_nが循環的にセルの送出を行うと仮
定した場合の各セルバッファのキュー長を推定する手段
としての情報管理部２を設け、判定部３は、情報管理部
２により推定されたキュー長が実際のキュー長を下回る
セルバッファに前記ＥＯＰセルが含まれるときこのセル
バッファに前記優先権を付与し、さらに、判定部３は、
前記パケットの長さにしたがって優先順位を設定すると
ころにある。

【００２７】また、判定部３は、所定のパケット長より
もパケット長が短いパケットに対し前記所定のパケット
長よりもパケット長が長いパケットに比較して上位の優
先順位を設定し、前記優先順位が設定されたセルバッフ
ァ６_iに対しＥＯＰセルが送出されるまでセルの送出を
許可する送出権を付与する。この設定結果は、優先コネ
クション用リスト部７に格納される。さらに、判定部３
は、前記送出権が付与されたセルバッファ６_iが前記最
後尾のセルを送出したときには、その送出権を他のセル
バッファに移行する。

【００２８】

【実施例】（第一実施例）本発明第一実施例を図１から
図７を参照して説明する。図２は情報管理部２の記録内
容を示す図である。図３は本発明第一実施例の送出セル
決定手順を示すフローチャートである。図４は優先的に
セルが出力できるコネクションへの移行手順を示すフロ
ーチャートである。図５は具体的な動作例を説明するた
めの図である。図６は情報管理部の記録内容を示す図で
ある。図７は優先コネクション用リスト部７の記録内容
を示す図である。

【００２９】図１に示すように、ＶＣＩ識別部１は、到
着したセルのＶＣＩとそのセルがＥＯＰセルであるかど
うかを識別する。キュー長読取部４は、各コネクション
毎に設けられるセルバッファ６₁〜６_nのキュー長を読
取る。

【００３０】情報管理部２は、各コネクション毎に、そ
のコネクションが優先的にセルを出力できるコネクショ
ンかどうか、セルバッファ６₁〜６_nにあるＥＯＰセル
の個数、先頭のＥＯＰセルの位置、常にラウンドロビン
でセルがセルバッファ６₁〜６_nから送出されたときの
各コネクションのキュー長であるバーチャルキュー長を
管理している。

【００３１】優先コネクション用リスト部７は、優先的
にセルを出力できるコネクションを二つのリストで管理
しており、コネクションがどちらのリストに登録される
かの判断を行う。判定部３は、あるコネクションの実際
のキュー長がバーチャルキュー長以上であれば、そのコ
ネクションを優先的に出力できるコネクションと判定す
る。制御部５は、次に送出するセルを制御する。

【００３２】以降、図５ないし図７を参照して本発明第
一実施例の動作を説明する。今、時刻はｔ＝１で、通信
中のコネクション数は３で、それぞれのセルバッファ６
₁〜６_nには、セルが２つずつあり、それぞれのバーチ
ャルキュー長は、１、１、４であり、それぞれのＥＯＰ
セルの個数は、１、０、０であり、優先的にセルを出力
できるコネクションは、コネクション＃１のみで、コネ
クション＃１はリストに登録されている。コネクショ
ンがリストに登録されるかリストに登録されるかど
うかは、先頭のＥＯＰセルの位置、すなわち送信するセ
ル数が３以下ならば、リストに登録され、そうでなけ
ればリストに登録されるとする。コネクション＃２、
＃３は、ＥＯＰセルがｔ＝２にスイッチに到着するとす
る。（ｔ＝２）（セル出力）制御部５は、優先コネクション用リスト部
７において、リストには登録が無く、リストの先頭
にコネクション＃１が登録されていることが分かるの
で、コネクション＃１のセルを出力する。その結果、そ
れぞれのコネクションのキュー長は、１、２、２とな
り、バーチャルキュー長は、０、１、４となる。コネク
ション＃１の先頭のＥＯＰセルの位置は１になる。

【００３３】コネクション＃１のバーチャルキューが減
算されたが、コネクション＃１は既に優先的にセルを出
力できるコネクションなので判定部３は判定を行わな
い。また出力したセルは、ＥＯＰセルではないので、コ
ネクション＃１は優先的にセルを出力できるコネクショ
ンから外されない。（セル入力）コネクション＃２、＃３のＥＯＰセルが到
着すると、ＶＣＩ識別部１が到着したセルのＶＣＩ番号
と到着したセルをＥＯＰセルであると識別し、その結果
を情報管理部２に通知する。

【００３４】情報管理部２は、ＶＣＩ識別部１からＶＣ
Ｉ番号とＥＯＰセルが到着したという情報を受信したな
らば、管理しているそのコネクションのバーチャルキュ
ー長とＥＯＰセルの個数情報を１つ増加させる。その結
果、それぞれのバーチャルキュー長は、０、２、５、そ
れぞれのＥＯＰセルの個数は１、１、１となる。また、
コネクション＃２、＃３の先頭のＥＯＰセルの位置はそ
れぞれ３、３になる。コネクション＃２、＃３のＥＯＰ
セルが到着し、かつコネクション＃２、＃３は優先的に
セルを送出できるコネクションではないので、情報管理
部２は、コネクション番号とそのコネクションのバーチ
ャルキュー長を判定部３に送る。

【００３５】判定部３は、情報を受信したならば、受信
したコネクション番号の実際のキュー長を送るようにキ
ュー長読取部４に要求する。キュー長読取部４は、要求
されたコネクションのキュー長をセルバッファ６₁〜６
_nから読取り、それを判定部３に送る。判定部３では、
受信したキュー長とバーチャルキュー長からそのコネク
ションが優先的にセルを送出するコネクションになるか
どうかを判定する。本発明第一実施例では、コネクショ
ン＃２は、実際のキュー長が３、バーチャルキュー長が
２なので、優先的にセルを送出するコネクションにな
り、先頭のＥＯＰセルの位置は３なので、リスト１に登
録される。一方、コネクション＃３は、実際のキュー長
が３、バーチャルキュー長が５なので、優先的にセルを
送出するコネクションにならない。

【００３６】ここで、実際のキュー長とバーチャルキュ
ー長とを比較する意味を説明する。バーチャルキュー長
は、上述したように常にラウンドロビンでセルがセルバ
ッファから送出されたときの各コネクションのキュー長
である。つまり、バーチャルキュー長とは、通信中のコ
ネクション間で公平に帯域が分配されたときのキュー長
である。よって、実際のキュー長がバーチャルキュー長
より長いコネクションとは、公平な帯域より少ない帯域
を得ているコネクションである。一方、実際のキュー長
がバーチャルキュー長より短いコネクションとは、公平
な帯域より多い帯域を得ているコネクションとなる。し
たがって、実際のキュー長がバーチャルキュー長より長
いコネクションを優先的にセルを送出できるコネクショ
ンとすることにより、公平性を満足しつつパケット転送
時間を短くすることができる。（ｔ＝３）（セル出力）制御部５は、優先コネクション用リスト部
７において、リストの先頭にコネクション＃２が登録
されていることが分かるので、コネクション＃２のセル
を出力する。その結果、それぞれのコネクションのキュ
ー長は、１、２、３となり、バーチャルキュー長は、ｔ
＝２で、コネクション＃１のものを選択したので、ラウ
ンドロビンにより、コネクション＃２を選択し、０、
１、５となる。コネクション＃２の先頭のＥＯＰセルの
位置は２になる。コネクション＃２のバーチャルキュー
が減算されたが、コネクション＃２は既に優先的にセル
を出力できるコネクションなので、判定部３は判定を行
わない。また出力したセルは、ＥＯＰセルではないの
で、コネクション＃２は優先的にセルを出力できるコネ
クションから外されない。（セル入力）セルは入力されない。（ｔ＝４）（セル出力）制御部５は、優先コネクション用リスト部
７において、リストの先頭にコネクション＃２が登録
されていることが分かるので、コネクション＃２のセル
を出力する。その結果、それぞれのコネクションのキュ
ー長は、１、１、３となり、バーチャルキュー長は、ｔ
＝３で、コネクション＃２のものを選択したので、０、
１、４となる。コネクション＃２の先頭のＥＯＰセルの
位置は１になる。コネクション＃３のバーチャルキュー
が減算されたので、判定部３はコネクション＃３が優先
的にセルを送出できるコネクションであるかどうかの判
定を行うが、実際のキュー長が３でバーチャルキューが
４なので、優先的にセルを送出できるコネクションとは
しない。また出力したセルは、ＥＯＰセルではないの
で、コネクション＃２は優先的にセルを出力できるコネ
クションから外されない。（セル入力）セルは入力されない。（ｔ＝５）（セル出力）制御部５は、優先コネクション用リスト部
７において、リストの先頭にコネクション＃２が登録
されていることが分かるので、コネクション＃２のセル
を出力する。その結果、それぞれのコネクションのキュ
ー長は、１、０、３となり、バーチャルキュー長は、ｔ
＝４で、コネクション＃３のものを選択したので、ラウ
ンドロビンにより、０、０、４となる。（コネクション
＃１のバーチャルキューはすでに０なので選択されな
い。）コネクション＃２の先頭のＥＯＰセルの位置は０にな
る。コネクション＃２のバーチャルキューが減算された
が、コネクション＃２はＥＯＰセルがないので、判定部
３は判定を行わない。また出力したセルは、ＥＯＰセル
なので、コネクション＃２は優先的にセルを出力できる
コネクションから外れる。（セル入力）セルは入力されない。

【００３７】以下、図３、図４の手順に従い、セルを送
出する。図３に示すように、優先的にセルを出力できる
コネクションは存在するか否かを判定し（Ｓ１）、存在
しないときには、セルバッファにセルを有するコネクシ
ョンの中からラウンドロビンによって送出するセルを決
定する（Ｓ２）。また、存在するときには、そのような
コネクションの中からリストに登録されているコネク
ションはあるか否かを判定する（Ｓ３）。リストに登
録されているコネクションがあれば、リストの先頭に
登録されているコネクションに送出権を与える（Ｓ
４）。リストに登録れさているコネクションがなけれ
ば、リストの先頭に登録されているコネクションに送
出権を与える（Ｓ５）。送出権を有するコネクションの
セルを送出する（Ｓ６）。送出したセルがＥＯＰセルで
あれば（Ｓ７）、送出したセルを有するコネクションを
優先的にセルを出力するコネクションから外す（Ｓ
８）。

【００３８】図４に示すように、コネクション＃ｉのＥ
ＯＰセルがセルバッファ６_iに到着したとき、あるい
は、コネクション＃ｉのバーチャルキュー長が減少され
たとき（Ｓ９）、コネクション＃ｉは、セルバッファ６
_iにＥＯＰセルがあり、かつ、優先的にセルを出力でき
るコネクションであるか否かを判定する（Ｓ１０）。こ
のとき、優先的にセルを出力できるコネクションであれ
ば、さらに、コネクション＃ｉの実際のキュー長とバー
チャルキュー長とを比較し、実際のキュー長がバーチャ
ルキュー長を上回れば（Ｓ１１）、コネクション＃ｉを
優先的にセルを出力できるコネクションにする（Ｓ１
２）。コネクション＃ｉの次に現れるＥＯＰセルまでの
セル数があらかじめ設定した値以下である場合には（Ｓ
１３）、優先コネクション用リスト部７のリストにコ
ネクション＃ｉを登録する（Ｓ１４）。コネクション＃
ｉの次に現れるＥＯＰセルまでのセル数があらかじめ設
定した値を上回る場合には（Ｓ１３）、優先コネクショ
ン用リスト部７のリストにコネクション＃ｉを登録す
る（Ｓ１５）。（第二実施例）本発明第二実施例を図１、図２、図４か
ら図８を参照して説明する。システム構成、優先的にセ
ルが出力できるコネクションへの移行手順、具体例を示
す図は本発明第一実施例と同様であり、図８は本発明第
二実施例の送出セル決定手順を示すフローチャートであ
る。

【００３９】以降、図５〜図７を参照して本発明第二実
施例の動作を説明する。今、時刻はｔ＝１で、通信中の
コネクション数は３で、それぞれのセルバッファには、
セルが２つずつあり、それぞれバーチャルキュー長は
１、１、４であり、それぞれのＥＯＰセルの個数は、
１、０、０であり、優先的にセルを出力できるコネクシ
ョンは、コネクション＃１のみで、コネクション＃１は
リストに登録され、送出権を持っているとする。コネ
クションがリストに登録されるかリストに登録され
るかどうかは、先頭のＥＯＰセルの位置、すなわち送信
するセル数が３以下ならば、リストに登録され、そう
でなければリストに登録されるとする。コネクション
＃２、＃３は、ＥＯＰセルがｔ＝２にスイッチに到着す
るとする。（ｔ＝２）（セル出力）制御部５は、優先コネクション用リスト部
７において、リストの先頭のコネクション＃１が送出
権を持っていることが分かるので、コネクション＃１の
セルを出力する。その結果、それぞれのコネクションの
キュー長は、１、２、２となり、バーチャルキュー長
は、０、１、４となる。コネクション＃１の先頭のＥＯ
Ｐセルの位置は１になる。コネクション＃１のバーチャ
ルキューが減算されたが、コネクション＃１は既に優先
的にセルを出力できるコネクションなので、判定部３は
判定を行わない。また出力したセルは、ＥＯＰセルでは
ないので、コネクション＃１は優先的にセルを出力でき
るコネクションから外されない。（セル入力）コネクション＃２、＃３のＥＯＰセルが到
着すると、ＶＣＩ識別部１が到着したセルのＶＣＩ番号
と到着したセルをＥＯＰセルであると識別し、その結果
を情報管理部２に通知する。情報管理部２は、ＶＣＩ識
別部１からＶＣＩ番号とＥＯＰセルが到着したという情
報を受信したならば、管理しているそのコネクションの
バーチャルキュー長とＥＯＰセルの個数情報を１つ増加
させる。その結果、それぞれのバーチャルキュー長は、
０、２、５、それぞれのＥＯＰセルの個数は、１、１、
１となる。また、コネクション＃２、＃３の先頭のＥＯ
Ｐセルの位置はそれぞれ３、３になる。コネクション＃
２、＃３のＥＯＰセルが到着し、かつコネクション＃
２、＃３は優先的にセルを送出できるコネクションでは
ないので、情報管理部２は、コネクション番号とそのコ
ネクションのバーチャルキュー長を判定部３に送る。

【００４０】判定部３は、情報を受信したならば、受信
したコネクション番号の実際のキュー長を送るようにキ
ュー長読取部４に要求する。キュー長読取部４は、要求
されたコネクションのキュー長をセルバッファ６₁〜６
_nから読取り、それを判定部３に送る。判定部３では、
受信したキュー長とバーチャルキュー長からそのコネク
ションが優先的にセルを送出するコネクションになるか
どうかを判定する。本発明第二実施例では、コネクショ
ン＃２は、実際のキュー長が３、バーチャルキュー長が
２なので、優先的にセルを送出するコネクションにな
り、先頭のＥＯＰセルの位置は３なので、リストに登
録される。一方コネクション＃３は、実際のキュー長が
３、バーチャルキュー長が５なので、優先的にセルを送
出するコネクションにならない。（ｔ＝３）（セル出力）制御部５は、優先コネクション用リスト部
７において、リストの先頭のコネクション＃１が送出
権を持っていることが分かるので、コネクション＃１の
セルを出力する。その結果、それぞれのコネクションの
キュー長は、０、２、３となり、バーチャルキュー長
は、ｔ＝２で、コネクション＃１のものを選択したの
で、ラウンドロビンにより、コネクション＃２を選択
し、０、１、５となる。コネクション＃１の先頭のＥＯ
Ｐセルの位置は０になる。コネクション＃２のバーチャ
ルキュー長が減算されたが、コネクション＃２は既に優
先的にセルを出力できるコネクションなので、判定部３
は判定を行わない。また出力したセルは、ＥＯＰセルな
ので、コネクション＃１は優先的にセルを出力できるコ
ネクションから外れ送出権を失う。（セル入力）セルは入力されない。（ｔ＝４）（セル出力）制御部５は、優先コネクション用リスト部
７において、送出権を持つコネクションがないので、リ
ストの先頭のコネクション＃２に送出権を与え、コネ
クション＃２のセルを出力する。その結果、それぞれの
コネクションのキュー長は、０、２、３となり、バーチ
ャルキュー長は、ｔ＝３で、コネクション＃２のものを
選択したので、０、１、４となる。コネクション＃２の
先頭のＥＯＰセルの位置は２になる。コネクション＃３
のバーチャルキューが減算されたので、判定部３はコネ
クション＃３が優先的にセルを送出できるコネクション
であるかどうかの判定を行うが、実際のキュー長が３で
バーチャルキューが４なので、優先的にセルを送出でき
るコネクションとはしない。また出力したセルは、ＥＯ
Ｐセルではないので、コネクション＃２は優先的にセル
を出力できるコネクションから外されない。（セル入力）セルは入力されない。（ｔ＝５）（セル出力）制御部５は、優先コネクション用リスト部
７において、リストの先頭にコネクション＃２を持っ
ていることが分かるので、コネクション＃２のセルを出
力する。その結果、それぞれのコネクションのキュー長
は、０、１、３となり、バーチャルキュー長は、ｔ＝４
で、コネクション＃３のものを選択したので、ラウンド
ロビンにより、０、０、４となる。コネクション＃１の
バーチャルキューはすでに０なので選択されない。コネ
クション＃２の先頭のＥＯＰセルの位置は１になる。コ
ネクション＃２は既に優先的にセルを出力できるコネク
ションなので判定部３は判定を行わない。（セル入力）セルは入力されない。

【００４１】以下、図４および図８の手順に従い、セル
を送出する。図４は前述のとおりである。図８に示すよ
うに、優先的にセルを出力できるコネクションは存在す
るか否かを判定し（Ｓ１６）、存在しないときには、セ
ルバッファにセルを有するコネクションの中からラウン
ドロビンによって送出するセルを決定する（Ｓ１７）。
また、存在するときには、そのようなコネクションの中
から送出権を有するコネクションはあるか否かを判定す
る（Ｓ１８）。送出権を有するコネクションがあれば、
送出権を有するコネクションのセルを送出する（Ｓ２
２）。送出したセルがＥＯＰセルであれば（Ｓ２３）、
送出したセルを有するコネクションを優先的にセルを出
力するコネクションから外す（Ｓ２４）。

【００４２】また、送出権を有するコネクションが無い
ときには（Ｓ１８）、リストに登録されているコネク
ションはあるか否かを判定する（Ｓ１９）。リストに
登録されているコネクションがあれば、リストの先頭
に登録されているコネクションに送出権を与える（Ｓ２
１）。リストに登録れさているコネクションがなけれ
ば、リストの先頭に登録されているコネクションに送
出権を与える（Ｓ２０）。送出権を有するコネクション
のセルを送出する（Ｓ２２）。送出したセルがＥＯＰセ
ルであれば（Ｓ２３）、送出したセルを有するコネクシ
ョンを優先的にセルを出力するコネクションから外す
（Ｓ２４）。

【００４３】

【発明の効果】以上説明したように、本発明によれば、
パケットを意識したセルスケジューリングを行いながら
同一の帯域を共用している通信中のコネクション間の公
平性を満足しつつ、かつパケット転送時間を短くするこ
とができるとともに、パケット長にも配慮したセルスケ
ジューラを実現することができる。

【図面の簡単な説明】

【図１】本発明実施例のセルスケジューラの要部ブロッ
ク構成図。

【図２】情報管理部の記録内容を示す図。

【図３】本発明第一実施例の送出セル決定手順を示すフ
ローチャート。

【図４】優先的にセルが出力できるコネクションへの移
行手順を示すフローチャート。

【図５】具体的な動作例を説明するための図。

【図６】情報管理部の記録内容を示す図。

【図７】優先コネクション用リスト部の記録内容を示す
図。

【図８】本発明第二実施例の送出セル決定手順を示すフ
ローチャート。

【図９】セル転送時間を短くしただけではパケット転送
時間が短縮できない例を示す図。

【符号の説明】

１ＶＣＩ識別部２情報管理部３判定部４キュー長読取部５制御部６₁〜６_n セルバッファ７優先コネクション用リスト部

Claims

【特許請求の範囲】

【請求項１】到着したセルが一つのパケットを複数の
セルに分解して送信した複数のセルの最後尾のセルであ
るか否かを識別する識別手段と、到着したセルを各コネ
クション毎に格納する複数のセルバッファと、この複数
のセルバッファのうちセル読出しの優先権を付与するセ
ルバッファを判定する判定手段とを備え、この判定手段は、前記最後尾のセルを含むセルバッファ
を前記優先権を付与する候補とする選択手段を含むセル
スケジューラにおいて、前記複数のセルバッファが循環的にセルの送出を行うと
仮定した場合の各セルバッファのキュー長を推定する手
段を設け、前記選択手段は、この推定する手段により推定されたキ
ュー長が実際のキュー長を下回るセルバッファに前記最
後尾のセルが含まれるときこのセルバッファに前記優先
権を付与する手段を含み、前記優先権を付与する手段は、前記パケットの長さにし
たがって優先順位を設定する手段を含むことを特徴とす
るセルスケジューラ。
【請求項２】前記優先順位を設定する手段は、所定の
パケット長よりもパケット長が短いパケットに対し前記
所定のパケット長よりもパケット長が長いパケットに比
較して上位の優先順位を設定する手段を含む請求項１記
載のセルスケジューラ。
【請求項３】前記優先順位を設定する手段により前記
優先順位が設定されたセルバッファに対し前記最後尾の
セルが送出されるまでセルの送出を許可する送出権を付
与する手段を備えた請求項２記載のセルスケジューラ。
【請求項４】前記送出権を付与する手段は、前記送出
権が付与されたセルバッファが前記最後尾のセルを送出
したときには、その送出権を他のセルバッファに移行す
る手段を備えた請求項３記載のセルスケジューラ。