(57)【要約】　　　（修正有）【課題】ＱｏＳを考慮したルータの大容量化、小さくかつ低遅延なアービタ、および交換器の構築。【解決手段】このアービタは木構造の各枝部に要求セレクタ１０２を設け、最優先順位番号の各ｂｉｔと対応する優先順位解決が可能である。１つのアービタ構造で、優先順位を表現可能。また、このアービタの内部に直接データを通過させることで、交換能力を持つ交換アービタである。また、交換アービタはその構造からワイヤレート達成ができ、実効スループットが向上する。アービタが帯域を制限するため、予約された帯域が溢れたとしても、廃棄が好ましくない要求を廃棄することなく遅延させることができる。破棄に伴う再送コストを削減できる。また、この流量制御の情報を用いて優先順位を決定し、流量制御を行うことで輻輳の回避や、ネットワーク全体の実効スループットもさらに向上する。【選択図】　図１
2004140538.tif 000002
【特許請求の範囲】
【請求項１】
木構造をもつアービタであって、
該木構造の葉にあるアービタ入力と、
該木構造の枝にある要求セレクタと、
該木構造に付随する優先順位の決定を行うコントローラと、を備え、
該コントローラに従って上記要求セレクタを制御してアービタ入力のいずれを出力するかを変化させるアービタ。
【請求項２】
上記コントローラは、優先順位決定カウンタおよび優先順位決定スケジューラのうちの少なくとも一つであるアービタ。
【請求項３】
上記優先順位決定カウンタは、アービタ入力の優先順位をラウンドロビンで均等に割り当てる請求項２記載のアービタ。
【請求項４】
上記優先順位決定スケジューラは、アービタ入力の優先順位をアービタ入力の保証帯域に基づいて割り当てる請求項２記載のアービタ。
【請求項５】
複数の要求の調停を行うアービタであって、
１つまたは複数の要求セレクタと、
優先順位を決定する制御手段と、
ｎ個（ただしｎは２のべき乗を）のアービタ入力と、を備え、
前記要求セレクタの段数をｔとしたときの、２のｔ乗がアービタ入力数ｎとなり、
１以上ｔ以下の自然数ｒについて、ｒ段目の前記要求セレクタの個数ｓ（ｒ）はｎを２のｒ乗で割った値となる構造を有し、
ｎ個のアービタ入力をそれぞれ、（０，１）、（０，２）、‥‥、（０，ｎ）とし、ｒ段目の要求セレクタをそれぞれ（ｒ，１）、（ｒ，２）、‥‥、（ｒ，ｓ（ｒ））とすると、
ｒ段目の要求セレクタ（ｒ，ｃ）は、ｒ―１段目の要求セレクタもしくはアービタ入力である（ｒ−１，２ｃ−１）と（ｒ−１，２ｃ）の２つの出力を入力とし、優先順位を決定するカウンタもしくはスケジューラのｒビット目の出力を元に、該要求セレクタの前記２つの入力について優先順位を解決した選択を行い、
ｃを２で割った切り上げをｐとするとｒ＋１段目の要求セレクタ（ｒ＋１，ｐ）の入力へ結果を出力する構造により、優先順位を考慮してアービタ入力の調停を行うことを特徴とするアービタ。
【請求項６】
複数の要求を調停するアービタであって、
１つまたは複数の要求セレクタと、
優先順位を決定するカウンタもしくはスケジューラと、
３以上で２のべき乗ではない数ｎとしたときの、ｎ個のアービタ入力と、を備え２のｔ乗のうちｎを超えない最大の自然数ｔとすると、前記要求セレクタの段数はｔ＋１であり、
１以上ｔ以下の自然数ｒについて、ｒ段目の前記要求セレクタの個数ｓ（ｒ）はｎを２のｒ乗で割った値であり、
ｔ＋１段目の前記要求セレクタの個数ｓ（ｒ＋１）はｎから２のｒ乗を引いた数である構造を有し、
ｔ段目までの要求セレクタは、請求項１と同様の結合であり、
ｔ＋１段目の要求セレクタは、該要求セレクタの出力をｔ段目の要求セレクタのどちらかの入力もしくは両方の入力に接続し、
ｒ段目の要求セレクタ（ｒ，ｃ）は、優先順位を決定するカウンタもしくはスケジューラのビットｒが出力する信号従い、どちらの入力を優先するかを決定することで優先順位を考慮してアービタ入力の調停を行うことを特徴とするアービタ。
【請求項７】
２進木構造をもつアービタであって、
該木構造の葉にあるアービタ入力と、
該木構造の枝にある要求セレクタと、
該木構造の最大段数以上のビット幅を持ち優先順位決定信号を出力するカウンタもしくはスケジューラと、を備え、
前記優先順位決定信号は、同じ段数にある要求セレクタについて共通に接続する構造を有し、
前記カウンタもしくはスケジューラの出力に従い、優先順位を考慮してアービタ入力の調停を行うことを特徴とするアービタ。
【請求項８】
各要求セレクタが要求として受け付ける有効か無効かを示す情報と、
上記要求セレクタが要求として受け付ける優先順位を示す情報と、
優先順位を決定するカウンタもしくはスケジューラが出力する信号と、のいずれか、もしくはその組み合わせにより、優先順位を考慮してアービタ入力を調停することを特徴とする
請求項１〜７のうちのいずれかに記載のアービタ。
【請求項９】
要求と共にパケットやデータを受け付け、アービタ全体でパケットの交換が行える、請求項１〜７のうちのいずれかに記載のアービタ。
【請求項１０】
請求項９のアービタを備え、
帯域保障に係わる１つもしくは複数のカウンタをアービタ入力部に備え、
そのカウンタの値により、帯域や実時間性を保証するための優先順位を決定するカウンタもしくはスケジューラの設定行うことを特徴とするルータ。
【請求項１１】
請求項９のアービタを優先順位毎に複数備え、
帯域保障に係わる１つもしくは複数のカウンタをアービタ入力部に備え、
そのカウンタの値により、優先順位を決定するカウンタもしくはスケジューラの設定を行うことで各優先順位毎に出力を決定し、
該優先順位毎に決定された出力について、さらに請求項５に示すアービタ、もしくは請求項６に示すアービタ構造のいずれかを用いて出力を決定することを特徴とするルータ。
【請求項１２】
ＩＰやＡＴＭ等に於けるルータおよびスイッチの構築方式であって、
入力バッファに於ける流量制御情報を元に適応ルーティングや帯域や実時間性を保証するための優先順位決定を行うことを特徴とするルータ。
【請求項１３】
ＩＰやＡＴＭ等に於けるルータおよびスイッチの構築方式であって、
請求項１０、請求項１１の少なくとも一つ組み合わせたルータの構造を備え、
入力バッファに於ける流量制御情報を元に適応ルーティングと、
前記情報を元に帯域や実時間性を保証するための優先順位を決定するカウンタもしくはスケジューラの制御と、のいずれか、もしくはそれらを組み合わせて行うことを特徴とするルータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信に於ける大容量パケットの低遅延交換システムに関わり、特に大容量パケットの低遅延交換システムに於けるパケットの交換器（例えばクロスバ）およびその調停器（アービタ）に関わる。パケットとしては、特にイーサネット・フレームやＡＴＭセルを受入れる。
【０００２】
【従来の技術】
【特許文献１】
特開２０００−１９８７１５号
【特許文献２】
特開２００１−３２６６８８号
【特許文献３】
特開平１０−２３２７６５号
【特許文献４】
特許３２２１４３６号
【特許文献５】
特開２０００−４００６１号
【特許文献６】
特開平１１−３４１０６１号
【特許文献７】は
特開２００１−２３７８８６号
【特許文献８】
特開平９−４６３６７号
【特許文献９】
特開２００１−１１１６１９号
【特許文献１０】
特開２００１−１７７５６２号
【特許文献１１】
特開２００１−２２３７０９号
【特許文献１２】
特開２００１−２８５３５２号
【特許文献１３】
特開２００１−３２０４０９号
【非特許文献１】
「Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ　Ｎｅｔｗｏｒｋｓ：　ａｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ａｐｐｒｏａｃｈ、Ｊｏｓｅ　Ｄｕａｔｏ　他著、ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　Ｐｒｅｓｓ、ＩＳＢＮ：０８１８６７８００３」のＣｒｏｓｓｂａｒ　Ｎｅｔｗｏｒｋｓ
【非特許文献２】
「トラヒックシェーピング機構の性能についての検討」（信学技報ＳＳＥ９６−１１５）
通信分野に於いては、広帯域化、高品質化、低遅延化の要求を満たす様々なルータやスイッチの構成技術が提案されている。特に、ルータの構成要素であるクロスバ、およびアービタは、広帯域化、高品質化、低遅延化に係わる重要な部位である。
図１２に示す従来の基本的なルータの構成に基づき、その動作を述べる。ルータの複数ある入力に投入されたパケットは、それぞれルータの入力バッファ１２０１において宛先や優先順位、到着指定時刻等の情報が調べられ、アービタ１２０２にそれらの情報を要求として伝える。アービタは、複数のアービタ入力にある要求を処理し、適切なアービタ入力とアービタ出力の組を決定する。クロスバ１２０３はこの組の情報を元に経路を設定することで、該パケットが入力バッファ１２０１から出力バッファ１２０４へ運ばれる。
ルータの基本構成であるクロスバ１２０３、およびアービタ１２０２については「Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ　Ｎｅｔｗｏｒｋｓ：　ａｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ａｐｐｒｏａｃｈ、Ｊｏｓｅ　Ｄｕａｔｏ　他著、ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　Ｐｒｅｓｓ、ＩＳＢＮ：０８１８６７８００３」のＣｒｏｓｓｂａｒ　Ｎｅｔｗｏｒｋｓを参照されたい。また、出力バッファにある帯域保証等の処理を行うためのシェーパ１２０５については、特開２０００−１９８７１５号および特開２００１−３２６６８８号や、「トラヒックシェーピング機構の性能についての検討」（信学技報ＳＳＥ９６−１１５）を参照されたい。
ルータの大容量化、低遅延化、低コスト化を図るためには、論理回路の単純化と小型化が必要である。論理回路の小型化の結果、チップ内部の大容量配線や高速論理を十分に利用することができ、チップ点数や基板面積を削減することで低コスト化を図ることができる。一方で高度なＱｏＳ（Ｑｕａｌｉｔｙ　ｏｆ　Ｓｅｒｖｉｃｅ）のサポートには複雑な処理が伴うため、論理規模の増大および遅延の増大を引き起こす。一般にＳＡＮ（Ｓｙｓｔｅｍ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）で用いられるルータの遅延が数百ｎｓであるのに対して、ＩＰのルータの遅延は数十μｓと２桁程度隔たりがあるのも、この高度なＱｏＳのサポートが一因となっている。
ルータの大容量化、低遅延化、低コスト化を図るために、本発明ではルータの構成要素であるアービタとクロスバに注目する。まず、アービタについて既存の構成例を示す。
図１３はキューベースアービタである。各要求は振分け器１３０１により優先順位や宛先別に要求キュー１３０２に蓄えられる。要求キュー１３０２に蓄えられた各要求は優先順位が高いものから順に選択器１３０３により受理される。この方式は優先順位別にＦＩＦＯにより構成されるキューを備えるため公平性が高く、キューの数により細かな調停制御が可能である。しかしながら、キューに必要なメモリ量が大きく、また、キューを管理する処理（キューが溢れたときの処理等）に多くの論理規模が必要となり低遅延化に貢献できない。選択器１３０３についてもスタベーション（最も優先順位が高い要求のみ受理し続け、それ以外は受理されない状態）を防ぐための工夫が必要であり、公平性を追及すると複雑になる。
ラウンドロビンアービタは最優先順位が均等に順序よく巡り、最優先順位が必ず均等に割り当てられるアービタである。ラウンドロビンアービタには各種の構成が存在する。
図１４は、振分け器１３０１により各最優先順位で異なる木構造１４０１を複数準備して優先順位を決定する構造である。木構造はデイジーチェイン構造よりも比較段数が少ない。各比較器は上からのアービタ入力、もしくは下からのアービタ入力を優先する。全ての比較器が上からのアービタ入力を優先すると一番上が最も高い優先順位となり、下からのアービタ入力を優先すると一番下が最も高い優先順位となる。ｎ個の比較対象があった場合、段数は
【０００３】
【数式７】
2004140538.tif 000003
であり、全比較器数はｎ−１である。
図１４に示すラウンドロビンアービタは、構成により最優先順位だけでなく、それ以下の順位もラウンドロビンで回るという利点がある。
図１５は従来のラウンドロビンアービタにおいて、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した図である。図１４のアービタは、図１５に示すように最も高い優先順位だけでなく、それ以下の順位についても均等かつ順序よく優先順位が巡る。しかしながら、優先順位毎に木構造を必要とするため論理回路量が多い。
その他の手法として、クロック毎に要求を１つずつ処理する構造がある。トークンをクロック毎に移動させ、トークンを獲得できたアービタ入力が最優先順位となり、そのアービタ入力に存在する要求のみ処理する。この手法によりある程度の論理回路規模の削減は見込めるが、各クロックで１つの要求のみ評価するため遅延が問題となる。
図１４に示す優先順位別に備えたアービタ構成要素を１つにして固定優先順位とした構成は、論理回路規模が少ないが要求のスタベーションが起こる可能性がある。特開平１０−２３２７６５号の図７がこれに相当する。
ＩＰの分野では回線速度が論理回路の処理速度を上回ろうとしており、たとえ大容量回線を導入してもその実効スループットが低下するという問題を抱えている。この問題を解決するには、現状の論理回路を単純化し、回線速度と同等の処理速度を維持することで実効スループットを向上させる必要がある。
また、障害発生時のＱｏＳについても考慮する必要がある。従来は障害発生時のＱｏＳを維持するために、帯域保障値の再設定を促すことで解決を図る。
【０００４】
【発明が解決しようとする課題】
本発明の目的は、ＱｏＳを考慮した上でアービタおよびクロスバの論理回路規模を削減し、ルータの大容量化、低遅延化、低コスト化を図ることにある。特に大容量化に於いては、回線容量の総和ではなく実効スループットの向上が必要である。
本発明では従来手法の次のような課題を解決する。
１．Ｐ３２２１４３６は、スケジューリングに特化した発明であり、要求を受理する予約テーブル（タイムスロット）に順次要求を生める方式である。クロスバの利用効率は高くなるが、予約テーブルとその制御機構に於ける論理回路量が大きい。また、該発明では、要求の優先順位を考慮していない。要求の優先順位を考慮して予約テーブルを埋めるには、優先順位の種類に比例した計算量が必要となり小規模化と低遅延化が困難である。
２．特開２０００−４００６１号はバスアービタに関する発明であり、スタベーションを防ぐことができる。該発明で用いられるアービタは、バス使用権調停部（特開２０００−４００６１号図１の６３）であり、その内部はバス使用権の調停方式の説明図（該明細書の図５）に示されている。これは４種類のバスの調停を行う単純なアービタであるが、調停の判断材料となる９種類の信号入力について、３３通りの組み合わせを考慮して調停結果を算出せねばならず、回路規模が大きく、遅延も増大する。
帯域や実時間性の保証に伴う優先順位制御はルータの重要な役割である。特に、伝送完了時刻、および実時間データに関連した帯域の確保は計算コストや論理回路量を必要とするため、遅延を生む原因となる。従来手法では次のような課題が存在する。
３．伝送完了時刻に関連した帯域の確保について、特開平１１−３４１０６１号は帯域保証の指示と実際の転送が別パケットで、帯域幅の算出は各端末が行う。特開２００１−２３７８８６号についても、帯域幅は送信側の端末が保障するため、帯域幅の算出は各端末が行う。これらの２つの実施例では、パケット毎に帯域を保障できないため適応ルーティングに対応できない。
４．実時間データに関連した帯域の確保について、特開平９−４６３６７号はコネクションベースであり、経路により帯域が決定されるためパケット毎に実時間性を保障できないため適応ルーティングに対応できない。特開２００１−１１１６１９号は、パケット毎に帯域が指定できるが、キューベースの調停により帯域の保証を行うため、回路規模、遅延共に大きくなる。Ｐ２００１−１７７５６２Ａは、送信バッファ部がシェーパとなり帯域を制御するため、シェーパの回路規模が大きく、またシェーパの性能を向上するために大きな出力バッファが必要となる。特開２００１−２２３７０９号および特開２００１−２８５３５２号は、キューベースの帯域制御を行うため、回路規模、遅延共に大きくなる。特開２００１−３２０４０９号はサーバを設置し帯域制御情報をデータベースの情報を元に全体を制御する。従ってネットワーク全体を集中管理する仕組みを提供する発明であり、この発明を用いて各パケットの帯域を管理すると集中管理の負荷が高く実効スループットが向上しない。
５．従来、アービタとクロスバは別々に設けられている。アービタの制御とクロスバの制御を効率よく行わなければ、出力のパケット間にバブルが発生しワイヤレートが達成できない原因となる。また、クロスバをＡＳＩＣで実装する場合、接点の各スイッチに相当する論理回路（３ステートバッファやワイヤレートＯＲ等）が用意されていない場合がある。また、存在しても、静的遅延解析や、３ステートバッファバスのディレイチューニング、電力見積もりが困難となる場合や、自動診断による故障検出率が低下する等の問題が伴うことが多い。
６．障害発生時のＱｏＳについて、従来は障害発生時のＱｏＳを維持するために、帯域保障値の再設定を促すことで解決を図っていた。障害により帯域が制限されているにもかかわらず、帯域保障値の再設定を促すトラフィックを新たに必要とし、ルータ単体での解決が行えずシステム全体での解決を必要とする。従って、障害発生時必要以上にネットワークが混乱する、障害の対応に時間がかかる等の問題がある。
【０００５】
【課題を解決するための手段】
上述した課題を解決するために、本発明では次のような手段を用いる。
１．２進木構造の、葉にアービタ入力、枝に要求セレクタを備え、付属する優先順位の決定を行うカウンタもしくはスケジューラに従って要求セレクタを制御することにより優先順位を解決するアービタを用いる。構造が簡単であるため、論理実装規模が少なく、高速動作が可能で低遅延化を図ることができる。
２．前記アービタは、優先順位の比較に於いて、まず優先順位の高いほうを優先し、優先順位が等しい場合は、カウンタもしくはスケジューラの出力のいずれかを用い、優先する方を決定するセレクタにより構成される。その結果、全要求の優先順位が等しい場合でも、最優先順位はラウンドロビンで巡り、それ以外の順位についても公平に巡るアービタを構成することができる。また、優先順位が不均等に巡るアービタの構成も可能である。
３．前記アービタに直接パケットを通すことでクロスバと同等の能力をもつ交換器を内包したアービタとして利用する共に、回路数の削減による大容量化、低遅延化、低コスト化を行う。このアービタは、可変長パケットをワイヤレート（入力の実効スループットと出力の実効スループットが等しい理想的な状態）で交換でき、実効スループットも向上する。
４．前記アービタの制御はパケット等の要求毎で行うことができる。従って、帯域幅を予約する場合にセットアップメッセージが不要であるため、適応型ルーティング上でも帯域幅を予約、保証できる。また、実時間性の保障にはグローバルな時間を管理することができる。
５．前記アービタの構造をルータに適用することで、帯域および実時間性保障が可能となる。このルータでは帯域および実時間性保障に係わる処理を全てアービタが行う。結果、大容量な出力バッファとそれを制御するシェーパが不要となり、出力バッファサイズの削減、および低コスト化を図ることができる。
６．前記アービタが帯域を制限するため、前段の入力キューが相手ルータと流量制御（ｃｒｅｄｉｔ　ｂａｓｅｄ　ｆｌｏｗ　ｃｏｎｔｒｏｌやバックプレッシャー等）を行えば、予約した帯域を溢れる通信を行ったとしても破棄が好ましくないパケットは廃棄せず遅延させることができる。結果廃棄に伴う要求の再送が不要となり、ネットワーク全体の実効スループットが向上する。
７．障害発生などにより帯域が削減され混雑が発生した際、普段より交換している流量制御情報により混雑度合を知ることができる。この情報によりルータが自主的に帯域を制限することが可能となる。結果、障害発生時のＱｏＳの維持における不要なネットワークの混乱を避け、障害の対応を迅速に行うことができる。本発明の一形態によれば、通信を行うルータは帯域および実時間性を保障する前記アービタとそれに付随もしくは融合された交換器を備える。
【０００６】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら説明する。尚、以下の実施の形態ではルータを例に用いるが、本発明は特にルータに限らず、要求の調停が必要とされる場合に適用できる。
実施例１
図１に本発明に於けるアービタの構成例を示す。この図では８個のアービタ入力１０１について示しているが、アービタ入力数が
【０００７】
【数式１】
2004140538.tif 000004
について同様に拡張、もしくは縮退が可能である。
ここでは一般的にアービタ入力数が
【０００８】
【数式１】
2004140538.tif 000005
である場合を示す。この時、以下のような構成となる。
１．ｎ個のアービタ入力１０１がある場合、段数は
【０００９】
【数式２】
2004140538.tif 000006
であり、ｒ段目には
【００１０】
【数式３】
2004140538.tif 000007
個の要求セレクタ１０２がある（全体ではｎ−１個の要求セレクタがある）。優先順位決定カウンタ１０３のビット幅は
【００１１】
【数式２】
2004140538.tif 000008
である。
２．ｎ個のアービタ入力をそれぞれ、（０，１）、（０，２）、‥‥、（０，ｎ）とする。また、ｒ段目の要求セレクタをそれぞれ（ｒ，１）、（ｒ，２）、‥‥、
【００１２】
【数式４】
2004140538.tif 000009
とする。
３．ｒ段目の要求セレクタ（ｒ，ｃ）は、ｒ−１段目の要求セレクタもしくはアービタ入力である（ｒ−１，２ｃ−１）と（ｒ−１，２ｃ）の２つの出力を入力とし、優先順位決定カウンタのｒビット目の出力を元に選択を行い、ｒ＋１段目の要求セレクタ
【００１３】
【数式５】
2004140538.tif 000010
に結果を渡す。
４．ｒ段目の要求セレクタ（ｒ，ｃ）は、優先順位決定カウンタのビットｒが出力する優先順位決定信号１０４に従い、この要求セレクタの前記２つの入力のどちらかを優先して選択する。順次選択を行うと最終的に１つが残り選択出力１０５となる。
要求セレクタにおける選択には、次の様な方式がある。
ａ．優先順位決定信号に従い無条件に出力を決定する。従って、単独の要求（他に競合する要求が存在しない）があったとしても、最優先順位が得られなければ処理されない。
ｂ．要求が競合するときのみ、優先順位決定信号に従い出力を決定する。
図２にこの場合の要求セレクタの構造を示す。要求の入力Ａ２０１と入力Ｂ２０２には、それぞれＩＤ２０３と、そのＩＤが有効か無効かを示すＶＡＬＩＤ２０４が含まれている。要求セレクタ制御回路２０５の出力に従い、セレクタがどちらかの入力を選択する。要求セレクタ制御回路の動作内容は次の通りである。
【００１４】
ｉ）どちらの入力のＶＡＬＩＤもネゲート状態である（非活動状態である）場合は、ＶＡＬＩＤの出力をネゲートすれば十分であり、ＩＤは何を出力してもかまわない。従って、ＩＤ、ＶＡＬＩＤはどちらを出力してもよい。
【００１５】
ｉｉ）どちらかの入力のＶＡＬＩＤのみアサート状態である（活動状態である）場合は、ＶＡＬＩＤがアサート状態である側のＩＤとＶＡＬＩＤを出力する。
【００１６】
ｉｉｉ）両方の入力のＶＡＬＩＤがアサート状態である場合、どちらかを選択する必要があるため優先順位決定信号１０４によりＩＤのどちらかが選ばれる。例えば、優先順位決定信号がネゲートされていれば、入力Ａ２０１が、優先順位決定信号１０４がアサートされていれば、入力Ｂ２０２が選ばれる。
図３は要求セレクタの内部に含まれる要求セレクタ制御回路の例を示した図である。この場合の要求セレクタ制御回路は、図３の例に示す様に単純な構造となる。また、前記ａと異なり、単独の要求は優先順位にかかわらず選択可能となる。
ｃ．各要求が持つ優先順位に従って要求を処理するが、同じ優先順位であった場合のみ、優先順位決定信号に従い出力を決定する。この場合の要求セレクタ制御回路の動作内容について、どちらの入力もＶＡＬＩＤがネゲートされている場合は前記ｂのｉと、どちらかの入力のＶＡＬＩＤのみアサートされている場合は前記ｂのｉｉと同様である。両方のＶＡＬＩＤがアサートされている場合は、それぞれの要求が持つ優先順位の高いほうを選択する。優先順位が等しい場合は、優先順位決定信号によりＩＤのどちらかが選ばれる。
要求セレクタ制御回路の例は、入力ＡのＶＡＬＩＤをＶａ、入力ＢのＶＡＬＩＤをＶｂ、入力Ａの優先順位をＰａ、入力Ｂの優先順位をＰｂ、優先順位決定信号をＤとすると、論理式で、
【００１７】
【数式５】
2004140538.tif 000011
と表せる。
図４は本発明に於けるアービタを、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した表図である。優先順位決定カウンタの値は、選択出力１０５を決定する度に１増やす。また、０からｎ−１までカウントするとラップラウンドして０に戻る。例えば、優先順位カウンタの値が０の場合、各ｂｉｔ全て０（ここではネゲート状態を０とする）であるため、全ての要求セレクタが上からの入力を優先し、一番上が最も優先順位が高くなる。優先順位カウンタの値が１（ここではアサート状態を１とする）の場合、１ｂｉｔ目のみ１となることから１段目の要求セレクタだけが下からの入力を優先し、アービタ入力が８個ある場合の優先順位は順に２、１、４、３、６、５、８、７となる。アービタ入力が８個ある場合の全優先順位を図４に列挙する。
このアービタを用いると、最優先順位はラウンドロビンで巡るが、それ以外は変則的な巡り方となる。しかしながら、最優先順位以外の各順位についても等しい確立で巡るため公平さは失われていない。単純なカウンタと、セレクタに小さな制御回路を付与することにより、最優先順位毎にアービタを準備することなく、図１４と同等の公平なアービタを構築することができる。
【００１８】
実施例２
アービタ入力数ｎが
【００１９】
【数式１】
2004140538.tif 000012
でない場合について、アービタの構成例を示す。この場合、段数は
【００２０】
【数式７】
2004140538.tif 000013
であり、ｒ段目には
【００２１】
【数式８】
2004140538.tif 000014
個の要求セレクタがある（全体ではｎ−１個の要求セレクタがある）。優先順位決定カウンタのビット幅は
【００２２】
【数式７】
2004140538.tif 000015
である。
まず、
【００２３】
【数式９】
2004140538.tif 000016
となる最大のｔについて、
【００２４】
【数式１０】
2004140538.tif 000017
個のアービタ入力に於ける実施例１の構成を基本とする。この実施例の１段目を２段目とし、新たに１段目に、
【００２５】
【数式１１】
2004140538.tif 000018
個の要求セレクタをアービタ入力の変わりに接続する。取り外されたアービタ入力と残りの
【００２６】
【数式１１】
2004140538.tif 000019
個のアービタ入力を、新たに付けた要求セレクタの入力に接続する。
優先順位決定カウンタは０からｎ−１まで変化させと、追加して設ける要求セレクタは１段目のどの位置であっても、各アービタ入力に最優先順位がラウンドロビンで回ることには変わりがない。
図５にアービタ入力数が１０の場合の構成例を示す。アービタ入力数が１０であるため、段数は全４段で３段が実施例と同じ構成である。従って、図１と同じ３段の要求セレクタ構成に２個の要求セレクタと残りの２つのアービタ入力加え、全体で１０個のアービタ入力とする。この場合、カウンタを０から９まで変化させることで、優先順位の２番目以降は均等に巡らないが、最優先順位はラウンドロビンで巡るアービタを構成することができる。
【００２７】
実施例３
本発明に於けるアービタについて、優先順位の割り当てを不均等にする例を述べる。
本発明のアービタは優先順位決定カウンタのｂｉｔ数と、それに繋げられた木構造の要求セレクタにより構成する。この木の構造やカウンタの開始数、ラップラウンド数や、カウント値を自由に変化させることで、優先順位を不均等に与える。
具体例として、４つのアービタ入力それぞれについて、要求の処理比を７：３：２：１にする場合を述べる。
図６は各アービタ入力について、不均等な優先順位を割り当てることができるアービタの例を示した図である。
まず木を図６に示す構造にする。この図のように、優先順位決定信号が全て結合していない構造や、完全木ではない不均衡な２進木の構造もとることができる。図６の構造において、優先順位決定カウンタが０から次にラップラウンドする１５までカウントすると、最優先順位となる数は、アービタ入力１が８回、アービタ入力２が４回、アービタ入力３が２回、アービタ入力４が２回となる。カウント値を０から１４までとすることで、最優先順位となる数は、アービタ入力１が８回、アービタ入力２が４回、アービタ入力３が２回、アービタ入力４が１回となる。さらに、優先順位決定カウンタが途中の４のカウントを飛ばし、カウントの開始値を１ではなく２にしてアービタ入力１が最優先順位となる数を１減らす。以上により、最優先順位となる数をアービタ入力１が７回、アービタ入力２が４回、アービタ入力３が２回、アービタ入力４が１回となり、結果、要求が処理される比が７：３：２：１となる。
【００２８】
実施例４
本発明に於けるアービタをクロスバ等の交換器と融合する例を述べる。
クロスバは各入力および出力のバーの交点にスイッチが設けられており、これらのスイッチを開閉することで競合しない限り、最多の入力と出力の組を自由に生成できるため、交換能力が高い。しかしながら、従来のルータやスイッチでは、アービタにより要求を調停した後、その結果に従ってクロスバで交換する構造をとるため、発生する遅延はアービタの遅延とクロスバの遅延の和となる。また、アービタとクロスバが効率よく稼動できなければパケット間にバブルが発生し、高速化やワイヤレート達成が困難となる。本発明では、アービタとクロスバ等の交換器を融合した交換アービタによりこれらの問題を解決する。
本発明に於けるアービタの各アービタ入力に要求ではなく直接パケットを投入し、図１の要求セレクタ１０２の中をパケットが直接通過する構成とすればクロスバが不要となる。この様な交換アービタは次のような利点がある。
１．拡張した要求セレクタにより構成された交換アービタを出力毎に設け、出力毎に全アービタ入力の競合が解決すれば、競合しない限り最多の入力と出力の組を自由に生成できる。従って、交換アービタはクロスバと同等の交換能力を持ち、クロスバ構成時に伴う３ステートバッファやワイヤードＯＲの問題を解決できる。
２．オメガ網などのＭＩＮ（Ｍｕｌｔｉｓｔａｇｅ　Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ　Ｎｅｔｗｏｒｋ）もセレクタ群により構成される画、ＭＩＮの多くはクロスバ程交換能力が高くない。また、クロスバと同等の交換能力を持つＭＩＮは構造と制御が複雑化する。交換アービタは交換能力においてクロスバと同等であるだけでなく、交換能力以外でもクロスバと同等の能力を持つ。例えば、クロスバ同様、複数の出力で同じ入力を選択すればマルチキャストを行うことができる。交換アービタは、クロスバとあらゆる意味で等価である。
３．交換アービタは、クロスバの遅延かアービタの遅延のどちらかを隠蔽できる。また、各要求セレクタが要求の選択とパケットの受け渡しを同時に行うパイプライン動作とすることで要求選択に伴う待ち時間も隠蔽できるため、低遅延化を図ることができる。
４．各要求セレクタや、一部の要求セレクタにバッファを設けることでパイプライン動作する交換アービタが構築可能である。段数が大きい場合や、パケットのｂｉｔ幅が大きい場合、動作周波数を高めたい場合など、構成が複雑化し処理時間が増大するため、パイプライン化された交換アービタが有効である。交換アービタは各段毎にパイプライン化することができ、高速化やワイヤレートの達成が容易である。
交換アービタに於ける交換の粒度はパケットの粒度に合わせる。即ち、パケットが自由に分断可能であれば、その分断可能な粒度に応じて優先順位決定カウンタの値を切り替える。切り替えるタイミングを変化させることで、各入力についての帯域保証を行う。
【００２９】
実施例５
ＩＰやＡＴＭ等に於けるルータやスイッチ（以下、単純にルータと呼ぶ）への本発明の応用について述べる。これらのルータに於いては、パケット毎の帯域幅の保証や実時間性の保障は重要な機能である。通常、これらの保障に伴う処理は出力バッファ（図１２の１２０４）に付与されたシェーパ（１２０５）で行われる。シェーパには、大容量の出力バッファ、制御論理回路、処理遅延が伴うが、本発明のアービタや交換アービタを適用することによりこれらの問題を解決することができる。
ここでは、要求セレクタ制御回路を用いた、パケット毎の帯域幅や実時間性の保障について述べる。
図７は本発明に於けるルータで用いるパケットフォーマットの例を示した図である。
パケットには帯域予約情報７０１および到着指定時刻７０２、優先順位７０３が記載されている。帯域予約情報や到着指定時刻、優先順位等の情報を明示的でも、暗黙的でも有していれば（例えば、前パケットと同様であるなどの情報等）、処理の単位はパケットでも、パケットを細かく分けたマイクロパケットやセルの形式でもよい。また、ＴＣＰやＩＰｖ４、ＩＰｖ６に含まれる情報を元に前記帯域予約情報や到着時刻を算出してもよい。
図８に本発明を適用したルータの構造の例を示す。ここでは交換アービタ８０２を利用する例を示すが、アービタとクロスバが別でもよい。図９にこのルータにおける交換アービタの構造を示す。各要求セレクタに指令を出す部位は、優先順位決定カウンタ１０３でも、優先順位決定スケジューラ９０３でもよい。このルータに於ける処理手順は以下の通りである。
まず、パケットは入力バッファ８０１に投入される。同時に、パケット解析部１００１において、宛先情報から出力ポートを特定する。この時、入力バッファを出力別に振り分けてもよい。また、帯域予約情報７０１および到着指定時刻７０２、優先順位情報７０３を抽出する。その後、パケットは入力バッファ８０１に投入される。
次に、交換アービタ８０２は入力バッファ８０１からパケットを引き出して前記抽出情報を元に調停を行う。調停を行う際には、各種サービスクラスへの対応が必要である。
ルータが備えるべきサービスクラスとしては、ＡＴＭに於けるＣＢＲ（Ｃｏｎｓｔａｎｔ　Ｂｉｔ　Ｒａｔｅ）、ｎｒ−ＶＢＲ（ｒｅａｌｔｉｍｅ−Ｖａｒｉａｂｌｅ　Ｂｉｔ　Ｒａｔｅ）、ｎｒｔ−ＶＢＲ（ｎｏｎｒｅａｌｔｉｍｅ−Ｖａｒｉａｂｌｅ　Ｂｉｔ　Ｒａｔｅ）、ＵＢＲ（Ｕｎｓｐｅｃｉｆｉｅｄ　ＢｉｔＲａｔｅ）、ＵＢＲ＋や、ＩＰに於けるＤＳ−ＥＦ（Ｄｉｆｆｓｅｒｖ―Ｅｘｐｅｄｉｔｅｄ　Ｆｏｒｗａｒｄｉｎｇ）、ＤＳ―ＡＦ（Ｄｉｆｆｓｅｒｖ−Ａｓｓｕｒｅｄ　Ｆｏｒｗａｒｄｉｎｇ）、ＢＥ（Ｂｅｓｔ　Ｅｆｆｏｒｔ）、ＩＳ−ＣＬ（ＩｎｔＳｅｒｖ−Ｃｏｎｔｒｏｌｌｅｄ　Ｌｏａｄ　Ｓｅｒｖｉｃｅ）、ＩＳ−ＧＳ（ＩｎｔＳｅｒｖ−Ｇｕａｒａｎｔｅｅｄ　Ｓｅｒｖｉｃｅ）等が知られている。ここでは、ＡＴＭのサービスクラスへの対応について述べる。それ以外についても同様に対応が可能である。
図９は本発明に於けるルータに含まれるアービタについて、帯域や実時間性をサポートする構造の例を示した図である。優先順位決定カウンタは単に値の増減を行うだけではなく、その値をスケジュールすることで様々なサービスクラスに対応することができる。サービスクラスへの対応方式には、優先順位決定カウンタを用い、各要求セレクタを複雑化して前記抽出情報を元に選択を行うことで対応する方式（方式Ｃ）と、各要求セレクタは単純で優先順位決定カウンタを優先順位決定スケジューラとすることで対応する方式（方式Ｓ）がある。
図１０に優先順位決定スケジューラを用いた場合のサービスクラスに対応する部位の構造を示す。要求セレクタを複雑化する場合は、スケジューラ設定部１００４の入力情報もデータとともにアービタに投入され、前記入力情報を元に各要求セレクタがどちらかの入力を決定する。
サービスクラスへの対応方法を述べる。まず、各入力に設けた帯域保証カウンタ９０１の値を、図７のへッダの帯域予約情報７０１を元にリセットする。この際、最も単純なリセット値を求める方式は、帯域予約情報と帯域保障カウンタの初期値を同一にすることである。その他にも、上位レイアの内部情報、管理者による設定、過去の通信履歴等を踏まえる方式がある。
方式Ｓでは、優先順位決定スケジューラ９０３に、全帯域を総量が変動可能なサイクリックバッファ（ＦＩＦＯ）９０４を設ける。優先順位決定スケジューラはカウンタの値を直接優先順位決定信号として用いるのではなく、サイクリックバッファ９０４の値を順次参照し優先順位決定信号として出力する。さらに、各入力に備え付けられた帯域保証カウンタ９０１の値に従ってサイクリックバッファ９０４に要求を書き込む。この要求が処理され、アービタを要求が通過するたびにサイクリックバッファの次の情報を読み出す。また、サイクリックバッファであるため、読み出して優先順位の決定を行うのと同時に、スケジュールの書き込みが可能である。サイクリックバッファが一周してある一定の場所を通過する毎に（例えばアドレス０）帯域保証カウンタ９０１をリセットする。サイクリックバッファが一周する前に全ての帯域保証カウンタが０になった場合は、キューが空ではない入力について引き続き転送を許可することでベストエフォート型の転送をサポートする。
各サービスクラスへの対応方法は以下のとおりである。ここでは、方式Ｃの要求セレクタもしくは方式Ｓのサイクリックバッファを決定因子と呼ぶ。
１．ＣＢＲでは、指定された帯域保証カウンタの値を忠実に守るため、キューが空であっても帯域保証カウンタが０になるまで決定因子に要求を出す。この場合要求に対する応答があってもキューが空であるため何も出力しない。
２．ｒｔ−ＶＢＲでは、指定された帯域保証カウンタの帯域が無くなっても追加して帯域を獲得できる。従って、帯域保証カウンタが０であってもキューが空でなければ決定因子に要求を出す。
３．ｎｒｔ−ＶＢＲでは、前記ｒｔ−ＶＢＲの方式に加えて追加要求が出せる数を制限できるように複数の帯域予約情報を用いる。まず、最低帯域保証値で帯域保証カウンタをリセットし、そのカウンタが０になった時点で最大帯域獲得可能値により最大帯域保障カウンタ９０２をリセットする。再び０になった場合は決定因子に要求を出さない。もしくは、最低帯域保証値で帯域保証カウンタを、最大帯域獲得可能値で最大帯域保証カウンタ９０２をリセットし、同時に両カウンタを減らす構成とする。
４．ＵＢＲは遅延や帯域に鈍感なため、他のカウンタが０である場合に決定因子に要求を出す、もしくはＵＢＲに固定な帯域保証値に従って帯域保証カウンタ９０１をリセットする等して実現する。
５．ＵＢＲ＋では平均速度が定義される。まず、平均帯域保証値で帯域保証カウンタ９０１をリセットする。帯域保証カウンタが０になった後もキューが空でなければ追加で決定因子に要求を出し、要求が通れば別の平均帯域保証カウンタを減ずる。それ以外の場合は平均帯域保証カウンタを増加させる。方式Ｃでは独自に設けた全体のサイクルを管理するカウンタ、方式Ｓサイクリックバッファが一周したとき再び平均帯域保証値で帯域保証カウンタをリセットするが、このとき平均帯域保証カウンタの値を加味することで平均帯域を守る。
この様に、複数の帯域保証値やカウンタを操作することで種々のサービスカテゴリに対応する。
全帯域カウンタが０になっても、まだ帯域保証カウンタが０でない場合は、キューの中にある該当要求を廃棄するかスムージングするかを選択する。この選択手段としてはへッダに明示的に破棄可能かどうかを記載する方式や、上位レイヤの情報に従う方式、管理者が直接指定する方式、該当する帯域保証サービスクラスにより指定する方式、上位レイアでＩＰを用いている場合はＴＣＰ／ＵＤＰ別で指定する方式等がある。
これらの帯域保障と同時に、実時間性の保障を行う。現在時刻時計１００２と、到着指定時刻７０２の差を猶予時間算出器１００３で随時求める。時刻情報はＧＭＴ等の基準となる時刻に変換して用いるか、ロケール情報付与したローカルタイムを利用する。この時、到着指定時刻および猶予時間の粒度が細かすぎると情報量が増え、荒すぎると細やかな管理ができなくなるため、利用するアプリケーション毎に粒度がある程度自由に設定する（例えば、動画であればそのフレーム速度に合わせる等）。
以上の各入力より集められた帯域保障カウンタ９０１の値、最大帯域保障カウンタ９０２の値、猶予時間算出器１００３の値を元に調停を行う。
方式Ｃでは、帯域保障カウンタ９０１の値、最大帯域保障カウンタ９０２の値より出される要求の有無（ＶＡＬＩＤ）と猶予時間を元に、実施例１のｃの方式に従って要求セレクタ制御回路を動作させる。構造が非常に単純で、小型化、高速化が容易な方式である。
方式Ｓでは、スケジューラ設定部１００４に於いて前記帯域保障カウンタ９０１の値、最大帯域保障カウンタ９０２の値、猶予時間算出器１００３の値を元にサイクリックバッファ９０４の設定を行う。この設定に本発明におけるアービタを再び用いると、方式Ｓと類似した調停結果となる。また、その他の方式によりサイクリックバッファの値を決定することで柔軟性が増す。例えば、乱数により任意抽出する方式、プログラムにより制御する方式等がある。しかしながら方式によっては規模や遅延が増大する可能性がある。
方式Ｃと方式Ｓのハイブリッド構成も可能である。例えば、帯域保障については方式Ｓを用い、実時間保障については方式Ｃを用いる等が可能である。
【００３０】
実施例６
より忠実な優先順位処理を行うアービタもしくは交換アービタの構成として、優先順位毎にアービタを設ける例を示す。
図１１にアービタを複数準備する場合の構成を示す。パケットは、優先順位毎に用意されたアービタ１１０１に投入される。アービタの出力はさらに、優先順位選択器１１０２により優先順位毎に重みをつけて選択され最終的な出力となる。この優先順位選択器にも本発明に於けるアービタを適用する。アービタを複数準備するため論理回路規模が大きくなり実装が困難となる場合は、アービタを優先順位毎に時分割で利用する。
本発明により、パケットもしくは要求毎といった粒度の細かい帯域予約と保証、実時間性の保証を少ない論理回路規模、かつ低遅延で実現可能である。が行えることで、ネットワークを有効に活用し、種々のサービスに対応することができる。
【００３１】
実施例７
流量制御に用いる情報を元に適応ルーティングを行う例について述べる。
本発明によるルータは入力バッファのみ流量制御を行えば、廃棄が好ましくないパケットを破棄せずに遅延させることが可能となる。また、この流量管理により得られる情報を元に、適応ルーティングを行うことができる。本発明によるルータは適応ルーティングを行うような場合でも帯域を保障することができ、流量制御を用いた適応ルーティングに適している。
流量制御の手段として用いられるバックプレッシャーやｃｒｅｄｉｔ　ｂａｓｅｄ　ｆｌｏｗ　ｃｏｎｔｒｏｌを利用する。ｃｒｅｄｉｔ（相手スイッチに於ける空きバッファ容量の情報）、もしくは、バックプレッシャーに於けるハンドシェイク頻度を解析すると相手スイッチの混雑度を知ることができる。この結果を利用して、ホットスポットを回避する適応ルーティングや優先順位決定する。
あるパケットが複数の出力ＡとＢを選択可能である場合、出力Ａのｃｒｅｄｉｔ数が出力Ｂのｃｒｅｄｉｔ数よりも多い場合、出力Ａの方が混雑していないと予想できるため、出力Ａを選択する。バックプレッシャーを利用する場合は、最近の転送停止時間を計測する。転送停止時間が長いほど混雑していると予想できる。
また、上記流量制御に用いる情報を実施例６における決定因子の判断材料に用いることも可能である。通常、帯域制限情報を正しく設定し正常に通信が行われていれば、スタベーションを回避したいパケットのスタベーションが回避できる。しかしながら、設定を誤った際や、回線不良により他回線が迂回してくることに伴う実質帯域の不足が発生したときには、混雑による輻輳が発生し帯域が保障できなくなる。この場合、帯域が保障されるべきパケット全体について、割り当てられた帯域を均等に削減することが望ましい。流量制御に用いる情報を元に混雑状況を知ることで、混雑状況に応じてパケットの帯域の保障値を均等に削減することができる。
【００３２】
【発明の効果】
本発明によれば、回路規模が小さく低遅延で公平なアービタを構築することができ、ルータに適用することで、小規模かつ、大容量、低遅延、低コストであり、帯域と実時間性を保障するルータが実現可能となる。
本発明に於けるアービタは、その構造が単純であるばかりではなく、直接パケットをアービタに投入することでクロスバと同等の能力をもつ交換器を構成することが可能となる。
また、アービタ自体が帯域や実時間性の保証を行うため、出力バッファにシェーパと呼ばれる回路や、それに伴う大容量の出力バッファが不要となる。入力バッファからのパケットの取り出し方や、アービタ内部の通過の仕方により帯域および実時間性が保障されるため、入力バッファのみ流量制御されていれば輻輳の際にも破棄が好ましくないパケットを破棄せず遅延させることが可能となる。この流量制御の情報を用いて優先順位の決定や流量制御を行うことで混雑および輻輳の回避や、ネットワーク全体の負荷分散を図ることができる。
今後のネットワーク社会においては、ストリーム等の大容量トラフィックに於けるアプリケーション単位での帯域や品質が問われるが、その対応を可能とする。
【図面の簡単な説明】
【図１】本発明に於けるアービタ構成の例として、８個のアービタ入力について最も均等に優先順位が割り当てられる構成を示したブロック図である。
【図２】本発明に於けるアービタの内部に含まれる各要求セレクタの構成例を示したブロック図である。
【図３】要求セレクタの内部に含まれる要求セレクタ制御回路の例を示したブロック図である。
【図４】本発明に於けるアービタを、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した表図である。
【図５】本発明に於けるアービタを、１０個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の例を示したブロック図である。
【図６】各アービタ入力について、不均等な優先順位を割り当てることができるアービタの例を示したブロック図である。
【図７】本発明に於けるルータで用いるパケットフォーマットの例を示したフォーマット図である。
【図８】本発明に於けるルータの構成例を示したブロック図である。
【図９】本発明に於けるルータに含まれるアービタについて、帯域や実時間性をサポートする構造の例を示したブロック図である。
【図１０】帯域や実時間性をサポートするため、優先順位決定カウンタを拡張した優先順位決定スケジューラにより各種サービスクラスに対応する構造の例を示したブロック図である。
【図１１】本発明に於けるルータについて、各優先順位毎に異なるアービタを適用した例を示したブロック図である。
【図１２】従来の帯域や実時間処理を行うルータの構成例を示したブロック図である。
【図１３】従来のキューベースのアービタの構成例を示したブロック図である。
【図１４】従来のラウンドロビンアービタの構成例を示したブロック図である。
【図１５】従来のラウンドロビンアービタにおいて、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した表図である。
【符号の説明】
１０１　　　　　　アービタ入力
１０２　　　　　　要求セレクタ
１０３　　　　　　優先順位決定カウンタ
１０４　　　　　　優先順位決定信号
１０５　　　　　　選択出力
２０１　　　　　　要求の入力Ａ
２０２　　　　　　要求の入力Ｂ
２０３　　　　　　ＩＤの入力
２０４　　　　　　ＶＡＯＩＤの入力
２０５　　　　　　要求セレクタ制御回路
８０１　　　　　　本発明に於けるルータで用いる入力バッファ
８０２　　　　　　交換アービタ
９０１　　　　　　帯域保証カウンタ
９０２　　　　　　最大帯域保証カウンタ
９０３　　　　　　優先順位決定スケジューラ
１００１　　　　　サイクリックバッファ
１１０１　　　　　優先順位毎に設ける交換アービタ
１１０２　　　　　優先順位選択器
１２０１　　　　　従来の入力バッファ
１２０２　　　　　従来のアービタ
１２０３　　　　　クロスバ
１２０４　　　　　出力バッファ部
１２０５　　　　　シェーパ
１３０１　　　　　要求振分け器
１３０２　　　　　要求キュー
１３０３　　　　　選択器
１４０１　　　　　固定優先順位アービタの一例。
【図１】
2004140538.tif 000020
【図２】
2004140538.tif 000021
【図３】
2004140538.tif 000022
【図４】
2004140538.tif 000023
【図５】
2004140538.tif 000024
【図６】
2004140538.tif 000025
【図７】
2004140538.tif 000026
【図８】
2004140538.tif 000027
【図９】
2004140538.tif 000028
【図１０】
2004140538.tif 000029
【図１１】
2004140538.tif 000030
【図１２】
2004140538.tif 000031
【図１３】
2004140538.tif 000032
【図１４】
2004140538.tif 000033
【図１５】
2004140538.tif 000034