(57)【特許請求の範囲】
【請求項１】
入力回線に対応し、同一出力方路宛の優先度の高いパケットから順にブロックを形成し、該形成されたブロックを組み立てたデータを送出する入力バッファ部と、
前記送出されたデータの競合調整を行うスケジューラ部と、
前記競合調整に基づき前記データの出力回線への接続を切り替えるスイッチ部と、を有し、
前記スケジューラ部は、前記入力バッファ部からの転送要求信号を基に前記データの競合調整を行い、該競合調整の結果を転送許可信号として前記入力バッファ部に送出し、同時に接続アドレス信号を前記スイッチ部に送出することを特徴とするパケット交換装置。
【請求項２】
前記入力回線および出力回線はＮ（但し、Ｎは２以上の正の整数）回線であり、前記スイッチ部は前記Ｎ個の入力回線および出力回線に対応したＮ×Ｎ回線の切替器であることを特徴とする請求項１記載のパケット交換装置。
【請求項３】
前記入力バッファ部は、出力方路別およびＱｏＳクラス別のＦＩＦＯ（First In Firt Out）とパケット分配部と入力バッファ制御部とブロック生成部とを具備して構成され、
前記パケット分配部は、前記入力回線から入力されたパケットを、前記パケットの付随するヘッダの情報を基に該当する前記ＦＩＦＯに分配し、
前記入力バッファ制御部は、各ＦＩＦＯの蓄積パケット数を管理し、前記スケジューラ部に対して前記転送要求信号を送出し、該スケジューラ部から前記転送許可信号を受け取った際に、ブロック生成許可信号を前記ブロック生成部に送出し、
前記ブロック生成部は、前記ブロック生成許可信号を受け取り、前記データを構築して前記スケジューラ部に送出することを特徴とする請求項１記載のパケット交換装置。
【請求項４】
入力バッファ部と、スイッチ部と、スケジューラ部と、を有するパケット交換装置におけるパケット交換方法であって、
前記入力バッファ部が、入力回線に対応し、同一出力方路宛の優先度の高いパケットから順にブロックを形成し、該形成されたブロックを組み立てたデータを前記スケジューラ部に送出する入力バッファ工程と、
前記スケジューラ部が、前記送出されたデータの競合調整を行うスケジューラ工程と、
前記スイッチ部が、前記競合調整に基づき前記データの出力回線への接続を切り替えるスイッチ工程と、を行い、
前記スケジューラ工程は、前記スケジューラ部が、前記入力バッファ部からの転送要求信号を基に前記データの競合調整を行い、該競合調整の結果を転送許可信号として前記入力バッファ部に送出し、同時に接続アドレス信号を前記スイッチ部に送出することを特徴とするパケット交換方法。
【請求項５】
前記入力回線および出力回線はＮ（但し、Ｎは２以上の正の整数）回線であり、前記スイッチ工程は、前記スイッチ部が、前記Ｎ個の入力回線および出力回線に対応したＮ×Ｎ回線の切り替えを行うことを特徴とする請求項４記載のパケット交換方法。
【請求項６】
前記入力バッファ部は、出力方路別およびＱｏＳクラス別のＦＩＦＯ（First In Firt Out）とパケット分配部と入力バッファ制御部とブロック生成部とを具備しており、
前記入力バッファ工程は、前記パケット分配部が、前記入力回線から入力されたパケットを、前記パケットの付随するヘッダの情報を基に該当する前記ＦＩＦＯに分配し、
前記入力バッファ制御部が、各ＦＩＦＯの蓄積パケット数を管理し、前記スケジューラ部に対して前記転送要求信号を送出し、該スケジューラ部から前記転送許可信号を受け取った際に、ブロック生成許可信号を前記ブロック生成部に送出し、
前記ブロック生成部が、前記ブロック生成許可信号を受け取り、前記データを構築して前記スケジューラ部に送出することを特徴とする請求項４記載のパケット交換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット交換装置に関し、例えば、パケット通信技術を用いて特定の入力ポートと出力ポートの間でスイッチングするＡＴＭ（Asynchronous Transfer Mode；非同期転送モード）、インターネット等へ適用されるパケット交換装置およびパケット交換方法に関する。
【０００２】
【従来の技術】
従来、パケット交換装置は、最近のインターネットの普及に伴い、需要が高まっている。また、この需要の高まりと共に、大容量で、かつＱｏＳ（Quality ofService）を保証できるような交換機が必要とされている。この大容量の交換機を実現する手段としては、メモリアクセス速度、所要バッファ量を抑えられる入力バッファ型の交換機が有力視されている。
【０００３】
しかし、入力バッファ型交換機の場合、バッファの先頭に達する位値のパケットが転送されるまで、後続のパケットは目的の出力方路が空の状態であっても転送することができないＨＯＬ（Head of Line）ブロッキングが発生し、スループットが低下するという問題点がある。
【０００４】
この問題点を回避するために、入力バッファ側で出力方路別、ＱｏＳのクラス別のＦＩＦＯ（First In Firt Out）を有する考え方が提案されている。この提案を実現するにあたり、入力バッファから送出されるデータが出力方路間で衝突しないために、スケジューリングを行うスケジューラが必要となる。ここで、ＱｏＳを保証するために、図５に示すようなＱｏＳのクラス別にスケジューラを有する構成が提案されている。本従来例では、優先度の高低により二つのスケジューラ部３０、３１を有し、優先度のより高いＦＩＦＯからの転送要求信号を一方のスケジューラ部３０で、優先度のより低いＦＩＦＯからの転送要求信号を他方のスケジューラ部３１で、それぞれ処理する。
【０００５】
第１に、一方のスケジューラ部３０にてスケジューリングを行う。そのスケジューリングの結果により、優先度の低いＦＩＦＯからの転送要求信号に関して、既にスケジューラ部３０で転送許可信号を出した方路については、この信号をマスクする。
【０００６】
第２に、マスク処理を施した転送要求信号に対して、他方のスケジューラ部３１にてスケジューリングを行う。これにより、高優先側で許可が得られた方路に関しては、低優先側で許可が得られることはなく、ＱｏＳが保証される。
【０００７】
【発明が解決しようとする課題】
しかしながら、上記従来のパケット交換装置およびパケット交換方法は、以下の問題点を伴う。この第１の問題点は、ＱｏＳのクラス別にスケジューラ部が必要となり、スケジューラ部の規模が大きくなることである。
【０００８】
大容量の交換機を実現する手段として、回線のＲａｔｅを増加すると共に方路数を増加する傾向にある。この増加により、スケジューラ部では非常に複雑な処理を高速で実現することが求められており、この結果、スケジューラ部の規模は大きくならざるを得ない。ここで、クラス別にスケジューラ部を持つことは、かなりの規模を要することとなり実現が困難となる。
【０００９】
第２の問題点は、スケジューラ部間の制御が必要となるということである。上述したように、ＱｏＳを保証するためには、優先度の高いスケジューラ部３０から処理を開始し、このスケジューリング結果を、優先度の低いスケジューラ部３１の処理に反映させる必要がある。このため、クラス別のスケジューラ部間の制御を行う必要がでてくる。１クラスに１スケジューラの構成をとる場合、サポートするクラス数分のスケジューラ部間の制御が必要となり、更に処理が複雑化し、規模の面でも増大化する。
【００１０】
本発明は、規模の小さいスケジューラでＱｏＳを保証するパケット交換装置およびパケット交換方法を提供することを目的とする。
【００１１】
より詳細には、本発明は、同一出願人による先願発明の特願平１１−０３４４０９号に示されている複数のパケットからブロックを構成し、このブロックをデータ送出の単位とする考え方を用いて、上記に掲げた従来の方法での問題点を解決するパケット交換装置およびパケット交換方法を提供することを目的とする。
【００１２】
【課題を解決するための手段】
かかる目的を達成するために、本発明にかかるパケット交換装置は、入力回線に対応し、同一出力方路宛の優先度の高いパケットから順にブロックを形成し、該形成されたブロックを組み立てたデータを送出する入力バッファ部と、送出されたデータの競合調整を行うスケジューラ部と、競合調整に基づきデータの出力回線への接続を切り替えるスイッチ部と、を有し、スケジューラ部は、入力バッファ部からの転送要求信号を基にデータの競合調整を行い、該競合調整の結果を転送許可信号として入力バッファ部に送出し、同時に接続アドレス信号をスイッチ部に送出することを特徴とする。
【００１３】
また、本発明にかかるパケット交換装置は、入力回線および出力回線はＮ（但し、Ｎは２以上の正の整数）回線であり、スイッチ部はＮ個の入力回線および出力回線に対応したＮ×Ｎ回線の切替器であることを特徴とする。
【００１４】
また、本発明にかかるパケット交換装置は、入力バッファ部は、出力方路別およびＱｏＳクラス別のＦＩＦＯ（First In Firt Out）とパケット分配部と入力バッファ制御部とブロック生成部とを具備して構成され、パケット分配部は、入力回線から入力されたパケットを、パケットの付随するヘッダの情報を基に該当するＦＩＦＯに分配し、入力バッファ制御部は、各ＦＩＦＯの蓄積パケット数を管理し、スケジューラ部に対して転送要求信号を送出し、該スケジューラ部から転送許可信号を受け取った際に、ブロック生成許可信号をブロック生成部に送出し、ブロック生成部は、ブロック生成許可信号を受け取り、データを構築してスケジューラ部に送出することを特徴とする。
【００１５】
また、本発明にかかるパケット交換方法は、入力バッファ部と、スイッチ部と、スケジューラ部と、を有するパケット交換装置におけるパケット交換方法であって、入力バッファ部が、入力回線に対応し、同一出力方路宛の優先度の高いパケットから順にブロックを形成し、該形成されたブロックを組み立てたデータをスケジューラ部に送出する入力バッファ工程と、スケジューラ部が、送出されたデータの競合調整を行うスケジューラ工程と、スイッチ部が、競合調整に基づきデータの出力回線への接続を切り替えるスイッチ工程と、を行い、スケジューラ工程は、スケジューラ部が、入力バッファ部からの転送要求信号を基にデータの競合調整を行い、該競合調整の結果を転送許可信号として入力バッファ部に送出し、同時に接続アドレス信号をスイッチ部に送出することを特徴とする。
【００１６】
また、本発明にかかるパケット交換方法は、入力回線および出力回線はＮ（但し、Ｎは２以上の正の整数）回線であり、スイッチ工程は、スイッチ部が、Ｎ個の入力回線および出力回線に対応したＮ×Ｎ回線の切り替えを行うことを特徴とする。
【００１７】
また、本発明にかかるパケット交換方法は、入力バッファ部は、出力方路別およびＱｏＳクラス別のＦＩＦＯ（First In Firt Out）とパケット分配部と入力バッファ制御部とブロック生成部とを具備しており、入力バッファ工程は、パケット分配部が、入力回線から入力されたパケットを、パケットの付随するヘッダの情報を基に該当するＦＩＦＯに分配し、入力バッファ制御部が、各ＦＩＦＯの蓄積パケット数を管理し、スケジューラ部に対して転送要求信号を送出し、該スケジューラ部から転送許可信号を受け取った際に、ブロック生成許可信号をブロック生成部に送出し、ブロック生成部が、ブロック生成許可信号を受け取り、データを構築してスケジューラ部に送出することを特徴とする。
【００１８】
【発明の実施の形態】
次に、添付図面を参照して本発明によるパケット交換装置およびパケット交換方法の実施の形態を詳細に説明する。図１から図４を参照すると、本発明のパケット交換装置およびパケット交換方法の一実施形態が示されている。図１は、本発明のパケット交換装置およびパケット交換方法の全体の構成を説明するための図である。図２は、入力バッファ部のより詳細な構成例を示す図である。図３はブロック生成部のブロック構成例を示し、また図４はこのブロック生成部から出力されるデータのブロックフォーマット例を示す図である。
【００１９】
（構成）
図１は、本発明のパケット交換装置およびパケット交換方法の原理的な構成図を示す。本実施形態のパケット交換装置およびパケット交換方法は、入力バッファ型の交換装置であり、各入力回線に対応した入力バッファ部１−１〜１−Ｎ、および競合調停を行うスケジューラ部６を有する。スケジューラ部６は、入力バッファ部１−１〜１−Ｎからの転送要求信号２−１〜２−Ｎを基にスケジューリングを行い、そのスケジューリング結果を転送許可信号３−１〜３−Ｎとして入力バッファ部１−１〜１−Ｎに送出し、同時に接続アドレス信号５−１〜５−ＮをＮ×Ｎスイッチ部４に送出する。
【００２０】
次に、入力バッファ部１−１のより詳細な構成例を表す図２を用いて、入力バッファ部１−１〜１−Ｎの詳細な構成について説明する。なお、入力バッファ部１−２〜１−Ｎも入力バッファ部１−１〜１−Ｎと同様の構成をとる。入力バッファ部１−１は、出力方路別、ＱｏＳクラス別のＦＩＦＯ（First In Firt Out）１−１１Ｈ〜１−１ＮＬ、パケット分配部１０、入力バッファ制御部１２、ブロック生成部１５から構成される。
【００２１】
パケット分配部１０は、入力回線１から入力されたパケットをそのヘッダの情報を基に、該当するＦＩＦＯ１−１１Ｈ〜１−１ＮＬに分配する。入力バッファ制御部１２は、各ＦＩＦＯの蓄積パケット数を管理し、スケジューラ部６に対して転送要求信号２−１を送出する。スケジューラ部６から転送許可信号３−１を受け取った際には、ブロック生成許可信号１４をブロック生成部１５に送出する。ブロック生成部１５は、ブロック生成許可信号１４を受け取ると、図４に示すブロックを組み立てたデータを構築し、この構築したデータを送出する。
【００２２】
図３は、データとして送出されるブロックの構成を表す。ブロックは同一出力方路宛のＱｏＳの異なるパケットから構成される。但し、ＱｏＳを保証するために優先度の高いパケットから順にブロックを形成するものとする。
【００２３】
上記のパケット交換装置およびパケット交換方法は、複数パケットをまとめたブロックをデータ送出の単位とし、同一出力方路宛でＱｏＳ（Quality of Service）の異なるパケットを１つのブロックとして送出することで、規模の小さいスケジューラでＱｏＳを保証する構成を取っている。
【００２４】
本実施形態のパケット交換装置およびパケット交換方法の各入力バッファ部１−１〜１−Ｎからスケジューラ部６に対して、転送要求信号２−１〜２−Ｎが送出される。スケジューラ部６でスケジューリングを行い、その結果、入力バッファ部１−１〜１−Ｎに転送許可信号３−１〜３−Ｎを、Ｎ×Ｎスイッチ部４に接続アドレス信号５−１〜５−Ｎを、それぞれ送出する。転送許可を得た入力バッファ部１−１〜１−Ｎは、図３のブロック生成部１５により図４に示すブロックを生成し、データとして送出する。この内容を以下に詳述する。
【００２５】
（動作）
本発明の実施例の動作を、図１から図４を参照して説明する。
初めに、図１の入力バッファ部１−１の構成を表した図２を例として、入力バッファ部の動作を示す。入力回線１から入力されたパケットは、そのヘッダの情報を基に、パケット分配部１０により出力方路別、ＱｏＳクラス別のＦＩＦＯ１−１１Ｈ〜１−１ＮＬの該当するＦＩＦＯに蓄積される。ここでパケット分配部１０は、入力バッファ制御部１２に対し、パケットが新たに蓄積されたことを表すパケット管理信号１１を送出する。
【００２６】
入力バッファ制御部１２は、各ＦＩＦＯに対応したマップを有し、蓄積されたパケット数を記憶しておく。各ＦＩＦＯにおける蓄積パケット数が、ブロックの先頭に達するタイミングを転送要求条件とし、同一方路宛の高／低優先ＦＩＦＯのいずれかがこの条件を満たした場合に、図１のスケジューラ部６に対して出力方路毎の転送要求信号２−１を送出する。この「ブロックの先頭に達するタイミング」とは、例えば、１ブロックの単位パケット数を“Ｋ”とした場合に、１、Ｋ＋１、２×Ｋ＋１、……、とする。
【００２７】
図１のスケジューラ部６は、各入力回線に対応した入力バッファ部１−１〜１−Ｎから転送要求信号２−１〜２−Ｎを受け取り、各入力バッファ部１−１〜１−Ｎから送出されるデータが衝突しないように、スケジューリングを行う。このスケジューリングの結果、転送許可信号３−１〜３−Ｎを入力バッファ部１−１〜１−Ｎに送出する。同時に、図１のＮ×Ｎスイッチ部４に対しても接続アドレス信号５−１〜５−Ｎを送出する。
【００２８】
ここで、転送許可信号３−１〜３−Ｎはデータの送出先である出力方路アドレスを表したものであり、接続アドレス信号５−１〜５−Ｎは各出力方路における受信先である入力方路アドレスを表したものである。Ｎ×Ｎスイッチ部４は、接続アドレス信号５−１〜５−Ｎを基に入力バッファ部１−１〜１−Ｎから送出されたデータをスイッチングし、該当する出力回線にデータを送出する。
【００２９】
図２において、スケジューラ部６から転送許可信号３−１を受け取った入力バッファ制御部１２は、許可が得られた場合にブロック生成部１５に対してブロック生成許可信号１４を送出する。
【００３０】
図３に、図２の出力方路１宛のＦＩＦＯを例に挙げて、高優先ＦＩＦＯ１−１１Ｈ、低優先ＦＩＦＯ１−１１Ｌ、ブロック生成部１５の詳細図を示す。また、図４に生成されるデータブロックの構成図を表す。
【００３１】
図３において、ブロック生成許可信号１４を受け取ったブロック生成部１５は、高優先ＦＩＦＯ１−１１Ｈ、低優先ＦＩＦＯ１−１１Ｌに蓄積されたパケットからデータブロックを形成する。ブロックの先頭には、データの宛先となる出力方路のアドレス等の情報を付加する。ブロックを形成する場合、ＱｏＳを保証するために、高優先ＦＩＦＯ１−１１Ｈに蓄積されたパケットＨ１〜Ｈ３から順番に組み立てる。高優先ＦＩＦＯ１−１１Ｈのパケット数が、ブロック単位パケット数“Ｋ”に満たない場合、低優先ＦＩＦＯ１−１１Ｌに蓄積されたパケットで補ってブロックを形成する。この時、ブロックを形成したパケット数を、高優先ＦＩＦＯ１−１１Ｈ、低優先ＦＩＦＯ１−１１Ｌのそれぞれについてブロック構成信号１３として、図２の入力バッファ制御部１２に送出する。入力バッファ制御部１２は、この信号に基づき蓄積されたパケット数を管理していたマップの値を更新する。
【００３２】
（効果）
上記の実施例による第１の効果は、ＱｏＳのクラス別のスケジューラが不要であるということである。このため、スケジューラの規模においてかなりの縮小が図れる。その理由は、ＱｏＳの異なるパケットを同一のデータとして処理することにより、スケジューラではクラスを意識しない構成が可能となっているからである。
【００３３】
第２の効果は、入力バッファ、スケジューラの処理時間を長くとることができるということである。このため、入力バッファ、スケジューラの処理が容易となり、規模の縮小が図れる。その理由は、複数のパケットから構成されたブロックをデータ送出の単位として処理するため、入力バッファでのデータの送出、スケジューラでのスケジューリングをブロック送出にかかる時間で処理すればよく、パケットをデータ送出の単位として処理するものに比べ、かなりの時間の余裕が生じるからである。
【００３４】
第３の効果は、トラヒックにおいて高いスループットを得ることができることである。その理由として次の点が挙げられる。ブロックを単一のＱｏＳのクラスから形成することを考えた場合、ＱｏＳを保証するために、高優先ＦＩＦＯのパケット数がブロック単位のパケット数に満たない場合でも次々に送出しなければならない。この場合、ブロックに満たない部分へは空のパケットを詰めるなどしてデータを送出することになり、交換機からの出力平均遅延が増大する。これらに対し、本実施例では、ＱｏＳの異なるパケットを１つのブロックとして形成することで、ブロックを形成するパケット数を単位パケット数に近づけることができ、上記に挙げたブロック単位故の欠点を補い、高いスループットを得ることができる。
【００３５】
（他の実施例）
本発明の他の実施例について説明する。
図２において、スケジューラ部６に対する転送要求信号２−１は、同一出力方路宛の高優先ＦＩＦＯ１−１１Ｈ、低優先ＦＩＦＯ１−１１Ｌのいずれかのパケット数が条件を満たした場合に送出するものとした。ここで、転送要求信号２−１を送出する条件を、高優先ＦＩＦＯ１−１１Ｈに蓄積されたパケット数が条件を満たした場合のみとする例が考えられる。但し、この場合、出力方路１宛の高優先ＦＩＦＯ１−１１Ｈにパケットが蓄積されない時には、スケジューラ部６に対して転送要求信号２−１が送出されることがなく、低優先ＦＩＦＯ１−１１Ｌに蓄積されたパケットが送出されないことが考えられる。この問題点を回避するため、高優先ＦＩＦＯ１−１１Ｈにパケットが蓄積されていない場合に、低優先ＦＩＦＯ１−１１Ｌに蓄積されたパケット数があるしきい値を越えた場合には、転送要求信号２−１を送出するような処理が必要となる。
【００３６】
更に異なる実施例について説明する。
本発明では、実施例において２クラスのＱｏＳについて具体的に述べてきた。ここで、Ｚ（Ｚ＞２）クラスのＱｏＳを保証する場合を考える。１つのスケジューラ部において、２クラスにまたがった転送要求信号を基準にスケジューリングを行うとし、Ｚ／２のスケジューラ部を用いて、優先度の高い順にスケジューリング処理を進めていくものとする。この場合、Ｚ／２のスケジューラ部間の制御が必要になるが、１つのクラスに対し１つのスケジューラ部を用いる場合に比べて、半分の数のスケジューラ部で構成することが可能となる。この様に、スケジューラ部で処理する転送要求信号を複数クラス（クラス数は任意）にまたがるものとすることで、更なるスケジューラ部の規模の縮小化が期待できる。
【００３７】
尚、上述の実施形態は本発明の好適な実施の一例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施が可能である。
【００３８】
【発明の効果】
以上の説明より明らかなように、本発明のパケット交換装置およびパケット交換方法は、入力回線に対応し、同一出力方路宛の優先度の高いパケットから順にブロックを形成したブロックを組み立てたデータを送出し、送出されたデータの競合調停を行い、この競合調整に基づきデータの出力回線への接続を切り替える。これにより、ＱｏＳを保証しつつＱｏＳのクラス別のスケジューラが不要となり、スケジューラの規模においての縮小化が図れ、スケジューラではクラスを意識しない構成が可能となる。さらに、入力バッファ、スケジューラの処理時間を長くとることができ、入力バッファ、スケジューラの処理が容易となり、トラヒックにおいて高いスループットを得ることができる。
【図面の簡単な説明】
【図１】本発明のパケット交換装置およびパケット交換方法の実施形態を示すブロック構成図である。
【図２】入力バッファ部のより詳細なブロック構成図１である。
【図３】入力バッファ部のより詳細なブロック構成図２である。
【図４】ブロックフォーマットの構成例を示す図である。
【図５】従来のパケット交換措置の構成例を示すブロック図である。
【符号の説明】
１−１〜１−Ｎ  入力バッファ部
２−１〜２−Ｎ  転送要求信号
３−１〜３−Ｎ  転送許可信号
４  Ｎ×Ｎスイッチ部
５−１〜５−Ｎ  接続アドレス信号
６  スケジューラ部
１０  パケット分配部
１１  パケット管理信号
１２  入力バッファ制御部
１３  ブロック構成信号
１４  ブロック生成許可信号
１５  ブロック生成部
１−１１Ｈ〜１−１ＮＨ  高優先ＦＩＦＯ
１−１１Ｌ〜１−１ＮＬ  低優先ＦＩＦＯ
３０、３１  スケジューラ部
【図１】
0003543725.tif 000002
【図２】
0003543725.tif 000003
【図３】
0003543725.tif 000004
【図４】
0003543725.tif 000005
【図５】
0003543725.tif 000006