(57)【特許請求の範囲】
【請求項１】
到着したセルのＶＣＩ(VirtualChannel Identifier)およびパケットを構成する最後尾のセルを識別するセル識別部と、
到着したセルをコネクション毎に格納する複数のセルバッファと、
コネクション毎に仮想キューをもち、前記セルバッファのセルを出力する毎に対応するコネクションの仮想キュー長を１加算させ、所定のセルスケジューリング法にしたがって選択されたコネクションの仮想キュー長を１減算する情報管理手段と、
前記セルバッファに前記最後尾のセルが格納されかつ前記仮想キュー長が０以下であるコネクションにセル送出許可を与える送出コネクション決定手段と
を備えたことを特徴とするセルスケジューラ。
【請求項２】
セル送出許可を与えるコネクションが複数あるときにはその複数のコネクションの中からラウンドロビンにより一つのコネクションを選択する手段を備えた請求項１記載のセルスケジューラ。
【請求項３】
前記セルバッファに格納された一連のセルにより構成されるパケット数を計数する手段が設けられ、この一連のセルの最後尾のセルが到着したセルバッファについてはこのパケット数を計数する手段の計数結果を当該セルバッファの格納セル数の値に更新する手段を備えた請求項１記載のセルスケジューラ。
【請求項４】
前記情報管理手段は、前記セルバッファに前記最後尾のセルがありかつ前記仮想キュー長に前記パケット数を計数する手段の計数結果を加算した値が０より大きいコネクションまたは前記仮想キュー長が０より大きいコネクションの中から、前記所定のスケジューリング法により仮想キュー長を１減算すべきコネクションを選択する手段を含む請求項１記載のセルスケジューラ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ：非同期転送モード）に利用する。本発明は上位レイヤのパケットを複数のセルに分割して転送するＡＴＭ通信に利用するに適する。本発明はＡＴＭ通信網を公平に利用する技術に関する。
【０００２】
【従来の技術】
ＡＴＭ通信網は、本来、セルネットワークであるが、最近、上位レイヤであるパケットを意識したセル転送制御が数多く提案されている。その中に、情報をセル単位ではなく、パケット単位で転送する技術がある。その従来技術の例を図８に示す。図８では、コネクション＃１のパケットサイズ３のパケットを構成するセルと、コネクション＃２のパケットサイズ２のパケットを構成するセルと、コネクション＃３のパケットサイズ３のパケットを構成するセルがＡＴＭスイッチに到着するとしている。ＡＴＭスイッチから出力されるセルは、セル単位の転送技術では、図８（ａ）に示すように、コネクション＃１、＃２、＃３、＃１、＃２、＃３、＃１、＃３の順番になる。一方、パケット単位の転送技術では、図８（ｂ）に示すように、コネクション＃１、＃１、＃１、＃２、＃２、＃３、＃３、＃３の順番になる。
【０００３】
【発明が解決しようとする課題】
このようなパケット単位の転送技術では、セル単位ではなく、パケット単位に情報を転送するので、ＡＴＭ交換機で用いられるセルスケジューリング法をそのまま用いることはできず、ルータやパケット交換機で用いられるセルスケジューリング法を用いることとなる。
【０００４】
このようなセルスケジューリング法で最も重要なことは、利用可能な帯域を現在通信を行っているアクティブなコネクション間で公平に分配できることである。そのため、公平に帯域を分配できるセルスケジューリング法が数多く提案されており、そのようなセルスケジューリング法の代表的なものとして、Ｄｅｆｉｃｉｔ  ｒｏｕｎｄ−ｒｏｂｉｎ（Ｍ．Ｓｈｒｅｅｄｈａｒ  ｅｔ  ａｌ．，”Ｅｆｆｉｃｉｅｎｔ  ｆａｉｒ  ｑｕｅｕｅｉｎｇ  ｕｓｉｎｇ  ｄｅｆｉｃｉｔ  ｒｏｕｎｄ  ｒｏｂｉｎ，”ＩＥＥＥ／ＡＣＭ  ｔｒａｎｓ，Ｎｅｔｗｏｒｋｉｎｇ，ｖｏｌ．４，ｎｏ．３，ｐｐ．３７５−３８５，Ｊｕｎｅ  １９９６）がある。
【０００５】
しかし、従来の技術では、ＡＴＭ交換機で用いられる任意のセルスケジューリング法でセルが送出された場合に、パケット単位のセル転送を行い、公平に帯域を分配する技術については示されていない。
【０００６】
本発明は、このような背景に行われたものであって、パケット単位のセル送出に最適なセルスケジューラを提供することを目的とする。本発明は、パケットを意識したセルスケジューリングを行いながら同一の帯域を共用している通信中のコネクション間の公平性を満足しつつ、かつパケット転送時間を短くすることができるセルスケジューラを提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明は、パケットを構成する一連のセルを連続して送出するようにパケット単位でセル転送制御を行うが、このときに、そのＡＴＭ通信網に適用されている任意のセルスケジューリング法によるセル転送の公平性を遵守しながらパケット単位のセル転送制御を行うことを特徴とする。
【０００８】
本願出願人は、先願（特願平１０−３１４５３８号、本願出願時に未公開）により、パケット単位のセル転送制御を行いながら、そのＡＴＭ通信網に適用されている任意のセルスケジューリング法によるセル転送の公平性を遵守するセルスケジューラを提案している。本願のセルスケジューラにおけるセルスケジューリング法は、先願のセルスケジューラにおけるセルスケジューリング法と比較すると、第一に、セルバッファにパケットを構成する最後尾のセルがあり、かつ仮想キュー長が０以下のコネクションの中からセルを送出するコネクションを選択するところが異なる。すなわち、コネクションｉ（ｉは１〜ｎのいずれか）の仮想キュー長が０以下とは、コネクションｉが現在までに利用した帯域が、各コネクション間で公平に帯域が利用された場合にコネクションｉが得る帯域と同じか、あるいは、それよりも少ないということである。したがって、現在までに利用した帯域と、公平に帯域が利用された場合に割り当てられる帯域とを比較することによって、各コネクション間に公平に帯域を分配することができる。
【０００９】
第二に、仮想キュー長が０より大きい、あるいは、セルバッファにパケットを構成する最後尾のセルがあり、かつ仮想キュー長にパケットベースキュー長を加算した値が０より大きいコネクションの中からあるコネクションの仮想キュー長を１だけ減算するところが異なる。すなわち、コネクションｉの仮想キュー長が０より大きいとは、コネクションｉが現在までに利用した帯域が、各コネクション間で公平に帯域が利用された場合にコネクションｉが得る帯域より多いということであり、また、コネクションｉのセルバッファにパケットを構成する最後尾のセルがあり、かつ仮想キュー長にパケットベースキュー長を加算した値が０より大きいコネクションとは、コネクションｉが現在までに利用した帯域が、各コネクション間で公平に帯域が利用された場合にコネクションｉが得る帯域に達していないということである。したがって、どのコネクションの仮想キュー長を減算するかを決定する際に、現在までに利用した帯域と、公平に帯域が利用された場合に割り当てられる帯域とを比較し、結果として、各コネクション間に公平に帯域を分配することができる。
【００１０】
第三に、コネクションｉのセルが出力されたときにそのコネクションのバーチャルキュー長を１だけ増加させるところが異なる。すなわち、コネクションｉがセルを出力したということは、コネクションｉが帯域を利用したということなので、そのコネクションの仮想キュー長を１だけ増加させる。したがって、仮想キュー長を増加させる場合に、帯域を利用したコネクションの仮想キュー長を増加させることにより、結果として、各コネクション間に公平に帯域を分配することができる。
【００１１】
これにより、本願は、先願と同様に、そのＡＴＭ通信網の任意のセルスケジューリング法にしたがいながらパケット単位のセル転送のための帯域を各コネクション間に公平に分配することができる。ただし、先願では、現在のパケットベースキュー長と、公平に帯域が利用された場合のキュー長とを比較することにより、各コネクション間に公平に帯域を分配するが、本願では、現在までに利用した帯域と、公平に帯域が利用された場合に割り当てられる帯域とを比較することにより、各コネクション間に公平に帯域を分配する。
【００１２】
すなわち、本発明はセルスケジューラであって、本発明の特徴とするところは、到着したセルのＶＣＩおよびパケットを構成する最後尾のセルを識別するセル識別部と、到着したセルをコネクション毎に格納する複数のセルバッファと、この複数のセルバッファが所定のセルスケジューリング法にしたがってセルの送出を行うと仮定した場合の各セルバッファの仮想キュー長を推定する手段と、前記セルバッファに前記最後尾のセルが格納されかつ前記仮想キュー長が０以下であるコネクションにセル送出許可を与える手段とを備えたところにある。
【００１３】
セル送出許可を与えるコネクションが複数あるときにはその複数のコネクションの中からラウンドロビンにより一つのコネクションを選択する手段を備えることが望ましい。
【００１４】
前記推定する手段は、セルを送出する毎に当該セルを送出したコネクションのセルバッファについてその仮想キュー長を１加算する手段を含むことが望ましい。
【００１５】
前記セルバッファに格納された一連のセルにより構成されるパケット数を計数する手段が設けられ、この一連のセルの最後尾のセルが到着したセルバッファについてはこのパケット数を計数する手段の計数結果を当該セルバッファの格納セル数の値に更新する手段を備えることが望ましい。
【００１６】
前記推定する手段は、前記セルバッファに前記最後尾のセルがありかつ前記仮想キュー長に前記パケット数を計数する手段の計数結果を加算した値が０より大きいコネクションまたは前記仮想キュー長が０より大きいコネクションについて前記所定のセルスケジューリング法により選択されたコネクションの前記仮想キュー長をセルが送出される毎に１減算する手段を含むことが望ましい。
【００１７】
これにより、パケット単位のセル送出に最適なセルスケジューラを実現することができる。すなわち、パケットを意識したセルスケジューリングを行いながら同一の帯域を共用している通信中のコネクション間の公平性を満足しつつ、かつパケット転送時間を短くすることができる。
【００１８】
【発明の実施の形態】
本発明実施例の構成を図１を参照して説明する。図１は本発明実施例のセルスケジューラの要部ブロック構成図である。
【００１９】
本発明は、セルスケジューラであって、本発明の特徴とするところは、図１に示すように、到着したセルのＶＣＩおよびパケットを構成する最後尾のセルを識別するセル識別部１と、到着したセルをコネクション毎に格納する複数のセルバッファ６１〜６ｎと、この複数のセルバッファ６１〜６ｎが所定のセルスケジューリング法にしたがってセルの送出を行うと仮定した場合の各セルバッファ６１〜６ｎの仮想キュー長を推定する手段である送出コネクション決定部３とを備え、この送出コネクション決定部３は、セルバッファ６１〜６ｎに前記最後尾のセルが格納されかつ前記仮想キュー長が０以下であるコネクションにセル送出許可を与えるところにある。
【００２０】
このとき、送出コネクション決定部３は、セル送出許可を与えるコネクションが複数あるときにはその複数のコネクションの中からラウンドロビンにより一つのコネクションを選択する。
【００２１】
また、送出コネクション決定部３は、セルを送出する毎に当該セルを送出したコネクションのセルバッファ６ｉについてその仮想キュー長を１加算する。
【００２２】
キュー長読取部４は、セルバッファ６１〜６ｎに格納された一連のセルにより構成されるパケット数を計数し、この一連のセルの最後尾のセルが到着したセルバッファ６ｉについてはこの計数結果を当該セルバッファ６ｉの格納セル数の値に更新する。また、送出コネクション決定部３は、セルバッファ６ｉに前記最後尾のセルがありかつ前記仮想キュー長に前記計数結果を加算した値が０より大きいコネクションまたは前記仮想キュー長が０より大きいコネクションについて前記所定のセルスケジューリング法により選択されたコネクションの前記仮想キュー長をセルが送出される毎に１減算する。
【００２３】
次に、本発明実施例の動作を図１ないし図７を参照して説明する。図２は本発明実施例の情報管理部の情報記録内容を示す図である。図３は本発明実施例のバーチャルキュー長の更新手順を示すフローチャートである。図４は本発明実施例のバーチャルキュー長の減算手順を示すフローチャートである。図５は本発明実施例のセル出力手順を示すフローチャートである。図６は本発明実施例のセル送出手順の具体例を示す図である。図７は、図６の具体例における情報管理部の情報記録内容を示す図である。
【００２４】
図１に示すように、セル識別部１は、到着したセルのＶＣＩとそのセルがパケットを構成する最後尾のセル（Ｅｎｄ  ｏｆ  Ｐａｃｋｅｔセル：ＥＯＰセル）であるかどうかを識別する。情報管理部２は、各コネクション毎に、ＥＯＰセル数、仮想キュー長であるバーチャルキュー長、パケット単位のキュー長であるパケットベースキュー長を管理している。送出コネクション決定部３は、情報管理部２の情報から次にセルを送出するコネクションを決定する。制御部５は、セルを送出するコネクションの番号を制御する。
【００２５】
以降、図６の具体例を基に本発明実施例を説明する。なお、図６の具体例における情報管理部２の情報記録内容は図７に示すとおりである。今、時刻はｔ＝１で、通信中のコネクションは３で、それぞれのセルバッファ６１、６２、６３には、セルがそれぞれ３個，０個，４個ずつあり、それぞれのＥＯＰセル数は１個、０個、２個であり、それぞれのバーチャルキュー長は−２、１、１であり、それぞれのパケットベースキュー長は３、０、４であり、ＩＤは３である。ここで、ＩＤが３であるということは、コネクション＃３のセルバッファ６３にセルの送出許可が与えられているということであり、もし、ＩＤが０であれば、送出許可を与える対象となるセルバッファが複数存在することを意味する。バーチャルキュー長は、ラウンドロビンにしたがって減少されるとする。また、以降、バーチャルキュー長をＶＱ、パケットベースキュー長をＰＱと示す。
（ｔ＝２）
図５にしたがい、制御部５は、ＩＤが０でなく３なので、コネクション＃３のセルを出力する。図４にしたがい、情報管理部２はＶＱを減算するが、コネクション＃１は、セルバッファ６１にＥＯＰセルがあり、かつＶＱ＋ＰＱ＝１＞０なので、コネクション＃１のＶＱから１を減算する。その結果−３になる。
【００２６】
図３にしたがい、情報管理部２はコネクション３のＶＱをＶＱ＝１＋１＝２に、ＰＱをＰＱ＝４−１＝３にそれぞれ更新する。出力したセルがＥＯＰセルなので、情報管理部２は、管理しているコネクション３のＥＯＰセル数から１を減算する。その結果１となる。また制御部５はＩＤを０にする。
（ｔ＝３）
図５にしたがい、制御部５は、ＩＤが０なので、送出コネクション決定部３に新たなセルを出力するコネクションを探索するように要求する。送出コネクション決定部３は、コネクション＃１がセルバッファ６１にＥＯＰセルがあり、かつＶＱ≦０なので、コネクション＃１を新たにセルを出力するコネクションとする。制御部５はＩＤに１を代入し、コネクション＃１のセルを出力する。
【００２７】
図４にしたがい、情報管理部２はＶＱを減算するが、コネクション＃２は、ＶＱ＞０なので、コネクション＃２のＶＱから１を減算する。その結果０になる。
【００２８】
図３にしたがい、情報管理部２はコネクション＃１のＶＱをＶＱ＝−３＋１＝−２に、ＰＱをＰＱ＝３−１＝２にそれぞれ更新する。
（ｔ＝４）
図５にしたがい、制御部５は、ＩＤが０でなく１なので、制御部５はコネクション＃１のセルを出力する。図４にしたがい、情報管理部２はＶＱを減算するが、コネクション＃３は、ＶＱ＞０なので、コネクション＃３のＶＱから１を減算する。その結果１になる。
【００２９】
図３にしたがい、情報管理部２はコネクション＃１のＶＱをＶＱ＝−２＋１＝−１に、ＰＱをＰＱ＝２−１＝１にそれぞれ更新する。
（ｔ＝５）
図５にしたがい、制御部５は、ＩＤが０でなく１なので、コネクション＃１のセルを出力する。
【００３０】
図４にしたがい、情報管理部２はＶＱを減算するが、コネクション＃１、＃２は、条件式を満足しないが、コネクション＃３はＶＱ＞０なので、コネクション＃３のＶＱから１を減算する。その結果０になる。
【００３１】
図３にしたがい、情報管理部２はコネクション＃１のＶＱをＶＱ＝−１＋１＝０に、ＰＱをＰＱ＝１−１＝０に更新する。出力したセルがＥＯＰセルなので、情報管理部２は、管理しているコネクション＃１のＥＯＰセル数から１を減算する。その結果０となる。また制御部５はＩＤを０にする。
（ｔ＝６）
図５にしたがい、制御部５は、ＩＤが０なので、送出コネクション決定部３に新たなセルを出力するコネクションを探索するように要求する。送出コネクション決定部３は、コネクション＃３がセルバッファ６３にＥＯＰセルがあり、かつＶＱ≦０なので、コネクション＃３を新たにセルを出力するコネクションとする。制御部５はＩＤに３を代入し、コネクション＃３のセルを出力する。
【００３２】
図４にしたがい、情報管理部２はＶＱを減算するが、コネクション＃３は、ＶＱ＋ＰＱ＞０なので、コネクション＃３のＶＱから１を減算する。その結果−１になる。図３にしたがい、情報管理部２はコネクション＃３のＶＱをＶＱ＝−１＋１＝０に、ＰＱをＰＱ＝３−１＝２にそれぞれ更新する。
【００３３】
以下、同様に、図３、４、５にしたがい、制御を行う。
【００３４】
【発明の効果】
以上説明したように、本発明によれば、パケット単位のセル送出に最適なセルスケジューラを実現することができる。これにより、パケットを意識したセルスケジューリングを行いながら同一の帯域を共用している通信中のコネクション間の公平性を満足しつつ、かつパケット転送時間を短くすることができる。
【図面の簡単な説明】
【図１】本発明実施例のセルスケジューラの要部ブロック構成図。
【図２】本発明実施例の情報管理部の情報記録内容を示す図。
【図３】本発明実施例のバーチャルキュー長の更新手順を示すフローチャート。
【図４】本発明実施例のバーチャルキュー長の減算手順を示すフローチャート。
【図５】本発明実施例のセル出力手順を示すフローチャート。
【図６】本発明実施例のセル送出手順の具体例を示す図。
【図７】図６の具体例における情報管理部の情報記録内容を示す図。
【図８】従来のセルをセル単位で転送する技術とパケット単位で転送する技術の差異を示す図。
【符号の説明】
１  セル識別部
２  情報管理部
３  送出コネクション決定部
４  キュー長読取部
５  制御部
６１、６２、６３〜６ｎ  セルバッファ
【図１】
0003578940.tif 000002
【図２】
0003578940.tif 000003
【図３】
0003578940.tif 000004
【図４】
0003578940.tif 000005
【図５】
0003578940.tif 000006
【図６】
0003578940.tif 000007
【図７】
0003578940.tif 000008
【図８】
0003578940.tif 000009