JP2004140538A - Arbiter compatible matching large capacity and low delay performance and router employing the same - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To build up a large capacity router taking into account the QoS (Quality of Service), a small-sized and low delay arbiter, and a switch. <P>SOLUTION: The arbiter adopting a tree structure is provided with a request selector 102 at its branch part and can attain preferential resolution corresponding to each bit of a highest preferential number. One arbiter structure can express priorities. Further, the arbiter acts like a switching arbiter having a switching capability by directly passing data through the inside of the arbiter. Moreover, the structure of the switching arbiter attains wire rate performance to enhance an effective throughput. Since the arbiter places a limit on the band, even when a reserved band overflows, a request whose cancellation is undesirable can be delayed without cancellation to reduce a re-transmission cost attended with the cancellation. Further, using information of flow control decides the priority and performs the flow control to avoid congestion and attain further enhancement of the effective throughput of the entire network. <P>COPYRIGHT: (C)2004,JPO

Description

であり、全比較器数はｎ−１である。
図１４に示すラウンドロビンアービタは、構成により最優先順位だけでなく、それ以下の順位もラウンドロビンで回るという利点がある。
図１５は従来のラウンドロビンアービタにおいて、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した図である。図１４のアービタは、図１５に示すように最も高い優先順位だけでなく、それ以下の順位についても均等かつ順序よく優先順位が巡る。しかしながら、優先順位毎に木構造を必要とするため論理回路量が多い。
その他の手法として、クロック毎に要求を１つずつ処理する構造がある。トークンをクロック毎に移動させ、トークンを獲得できたアービタ入力が最優先順位となり、そのアービタ入力に存在する要求のみ処理する。この手法によりある程度の論理回路規模の削減は見込めるが、各クロックで１つの要求のみ評価するため遅延が問題となる。
図１４に示す優先順位別に備えたアービタ構成要素を１つにして固定優先順位とした構成は、論理回路規模が少ないが要求のスタベーションが起こる可能性がある。特開平１０−２３２７６５号の図７がこれに相当する。
ＩＰの分野では回線速度が論理回路の処理速度を上回ろうとしており、たとえ大容量回線を導入してもその実効スループットが低下するという問題を抱えている。この問題を解決するには、現状の論理回路を単純化し、回線速度と同等の処理速度を維持することで実効スループットを向上させる必要がある。
また、障害発生時のＱｏＳについても考慮する必要がある。従来は障害発生時のＱｏＳを維持するために、帯域保障値の再設定を促すことで解決を図る。
【０００４】
【発明が解決しようとする課題】
本発明の目的は、ＱｏＳを考慮した上でアービタおよびクロスバの論理回路規模を削減し、ルータの大容量化、低遅延化、低コスト化を図ることにある。特に大容量化に於いては、回線容量の総和ではなく実効スループットの向上が必要である。
本発明では従来手法の次のような課題を解決する。
１．Ｐ３２２１４３６は、スケジューリングに特化した発明であり、要求を受理する予約テーブル（タイムスロット）に順次要求を生める方式である。クロスバの利用効率は高くなるが、予約テーブルとその制御機構に於ける論理回路量が大きい。また、該発明では、要求の優先順位を考慮していない。要求の優先順位を考慮して予約テーブルを埋めるには、優先順位の種類に比例した計算量が必要となり小規模化と低遅延化が困難である。
２．特開２０００−４００６１号はバスアービタに関する発明であり、スタベーションを防ぐことができる。該発明で用いられるアービタは、バス使用権調停部（特開２０００−４００６１号図１の６３）であり、その内部はバス使用権の調停方式の説明図（該明細書の図５）に示されている。これは４種類のバスの調停を行う単純なアービタであるが、調停の判断材料となる９種類の信号入力について、３３通りの組み合わせを考慮して調停結果を算出せねばならず、回路規模が大きく、遅延も増大する。
帯域や実時間性の保証に伴う優先順位制御はルータの重要な役割である。特に、伝送完了時刻、および実時間データに関連した帯域の確保は計算コストや論理回路量を必要とするため、遅延を生む原因となる。従来手法では次のような課題が存在する。
３．伝送完了時刻に関連した帯域の確保について、特開平１１−３４１０６１号は帯域保証の指示と実際の転送が別パケットで、帯域幅の算出は各端末が行う。特開２００１−２３７８８６号についても、帯域幅は送信側の端末が保障するため、帯域幅の算出は各端末が行う。これらの２つの実施例では、パケット毎に帯域を保障できないため適応ルーティングに対応できない。
４．実時間データに関連した帯域の確保について、特開平９−４６３６７号はコネクションベースであり、経路により帯域が決定されるためパケット毎に実時間性を保障できないため適応ルーティングに対応できない。特開２００１−１１１６１９号は、パケット毎に帯域が指定できるが、キューベースの調停により帯域の保証を行うため、回路規模、遅延共に大きくなる。Ｐ２００１−１７７５６２Ａは、送信バッファ部がシェーパとなり帯域を制御するため、シェーパの回路規模が大きく、またシェーパの性能を向上するために大きな出力バッファが必要となる。特開２００１−２２３７０９号および特開２００１−２８５３５２号は、キューベースの帯域制御を行うため、回路規模、遅延共に大きくなる。特開２００１−３２０４０９号はサーバを設置し帯域制御情報をデータベースの情報を元に全体を制御する。従ってネットワーク全体を集中管理する仕組みを提供する発明であり、この発明を用いて各パケットの帯域を管理すると集中管理の負荷が高く実効スループットが向上しない。
５．従来、アービタとクロスバは別々に設けられている。アービタの制御とクロスバの制御を効率よく行わなければ、出力のパケット間にバブルが発生しワイヤレートが達成できない原因となる。また、クロスバをＡＳＩＣで実装する場合、接点の各スイッチに相当する論理回路（３ステートバッファやワイヤレートＯＲ等）が用意されていない場合がある。また、存在しても、静的遅延解析や、３ステートバッファバスのディレイチューニング、電力見積もりが困難となる場合や、自動診断による故障検出率が低下する等の問題が伴うことが多い。
６．障害発生時のＱｏＳについて、従来は障害発生時のＱｏＳを維持するために、帯域保障値の再設定を促すことで解決を図っていた。障害により帯域が制限されているにもかかわらず、帯域保障値の再設定を促すトラフィックを新たに必要とし、ルータ単体での解決が行えずシステム全体での解決を必要とする。従って、障害発生時必要以上にネットワークが混乱する、障害の対応に時間がかかる等の問題がある。
【０００５】
【課題を解決するための手段】
上述した課題を解決するために、本発明では次のような手段を用いる。
１．２進木構造の、葉にアービタ入力、枝に要求セレクタを備え、付属する優先順位の決定を行うカウンタもしくはスケジューラに従って要求セレクタを制御することにより優先順位を解決するアービタを用いる。構造が簡単であるため、論理実装規模が少なく、高速動作が可能で低遅延化を図ることができる。
２．前記アービタは、優先順位の比較に於いて、まず優先順位の高いほうを優先し、優先順位が等しい場合は、カウンタもしくはスケジューラの出力のいずれかを用い、優先する方を決定するセレクタにより構成される。その結果、全要求の優先順位が等しい場合でも、最優先順位はラウンドロビンで巡り、それ以外の順位についても公平に巡るアービタを構成することができる。また、優先順位が不均等に巡るアービタの構成も可能である。
３．前記アービタに直接パケットを通すことでクロスバと同等の能力をもつ交換器を内包したアービタとして利用する共に、回路数の削減による大容量化、低遅延化、低コスト化を行う。このアービタは、可変長パケットをワイヤレート（入力の実効スループットと出力の実効スループットが等しい理想的な状態）で交換でき、実効スループットも向上する。
４．前記アービタの制御はパケット等の要求毎で行うことができる。従って、帯域幅を予約する場合にセットアップメッセージが不要であるため、適応型ルーティング上でも帯域幅を予約、保証できる。また、実時間性の保障にはグローバルな時間を管理することができる。
５．前記アービタの構造をルータに適用することで、帯域および実時間性保障が可能となる。このルータでは帯域および実時間性保障に係わる処理を全てアービタが行う。結果、大容量な出力バッファとそれを制御するシェーパが不要となり、出力バッファサイズの削減、および低コスト化を図ることができる。
６．前記アービタが帯域を制限するため、前段の入力キューが相手ルータと流量制御（ｃｒｅｄｉｔ　ｂａｓｅｄ　ｆｌｏｗ　ｃｏｎｔｒｏｌやバックプレッシャー等）を行えば、予約した帯域を溢れる通信を行ったとしても破棄が好ましくないパケットは廃棄せず遅延させることができる。結果廃棄に伴う要求の再送が不要となり、ネットワーク全体の実効スループットが向上する。
７．障害発生などにより帯域が削減され混雑が発生した際、普段より交換している流量制御情報により混雑度合を知ることができる。この情報によりルータが自主的に帯域を制限することが可能となる。結果、障害発生時のＱｏＳの維持における不要なネットワークの混乱を避け、障害の対応を迅速に行うことができる。本発明の一形態によれば、通信を行うルータは帯域および実時間性を保障する前記アービタとそれに付随もしくは融合された交換器を備える。
【０００６】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら説明する。尚、以下の実施の形態ではルータを例に用いるが、本発明は特にルータに限らず、要求の調停が必要とされる場合に適用できる。
実施例１
図１に本発明に於けるアービタの構成例を示す。この図では８個のアービタ入力１０１について示しているが、アービタ入力数が
【０００７】
【数式１】

について同様に拡張、もしくは縮退が可能である。
ここでは一般的にアービタ入力数が
【０００８】
【数式１】

である場合を示す。この時、以下のような構成となる。
１．ｎ個のアービタ入力１０１がある場合、段数は
【０００９】
【数式２】

であり、ｒ段目には
【００１０】
【数式３】

個の要求セレクタ１０２がある（全体ではｎ−１個の要求セレクタがある）。優先順位決定カウンタ１０３のビット幅は
【００１１】
【数式２】

である。
２．ｎ個のアービタ入力をそれぞれ、（０，１）、（０，２）、‥‥、（０，ｎ）とする。また、ｒ段目の要求セレクタをそれぞれ（ｒ，１）、（ｒ，２）、‥‥、
【００１２】
【数式４】

とする。
３．ｒ段目の要求セレクタ（ｒ，ｃ）は、ｒ−１段目の要求セレクタもしくはアービタ入力である（ｒ−１，２ｃ−１）と（ｒ−１，２ｃ）の２つの出力を入力とし、優先順位決定カウンタのｒビット目の出力を元に選択を行い、ｒ＋１段目の要求セレクタ
【００１３】
【数式５】

に結果を渡す。
４．ｒ段目の要求セレクタ（ｒ，ｃ）は、優先順位決定カウンタのビットｒが出力する優先順位決定信号１０４に従い、この要求セレクタの前記２つの入力のどちらかを優先して選択する。順次選択を行うと最終的に１つが残り選択出力１０５となる。
要求セレクタにおける選択には、次の様な方式がある。
ａ．優先順位決定信号に従い無条件に出力を決定する。従って、単独の要求（他に競合する要求が存在しない）があったとしても、最優先順位が得られなければ処理されない。
ｂ．要求が競合するときのみ、優先順位決定信号に従い出力を決定する。
図２にこの場合の要求セレクタの構造を示す。要求の入力Ａ２０１と入力Ｂ２０２には、それぞれＩＤ２０３と、そのＩＤが有効か無効かを示すＶＡＬＩＤ２０４が含まれている。要求セレクタ制御回路２０５の出力に従い、セレクタがどちらかの入力を選択する。要求セレクタ制御回路の動作内容は次の通りである。
【００１４】
ｉ）どちらの入力のＶＡＬＩＤもネゲート状態である（非活動状態である）場合は、ＶＡＬＩＤの出力をネゲートすれば十分であり、ＩＤは何を出力してもかまわない。従って、ＩＤ、ＶＡＬＩＤはどちらを出力してもよい。
【００１５】
ｉｉ）どちらかの入力のＶＡＬＩＤのみアサート状態である（活動状態である）場合は、ＶＡＬＩＤがアサート状態である側のＩＤとＶＡＬＩＤを出力する。
【００１６】
ｉｉｉ）両方の入力のＶＡＬＩＤがアサート状態である場合、どちらかを選択する必要があるため優先順位決定信号１０４によりＩＤのどちらかが選ばれる。例えば、優先順位決定信号がネゲートされていれば、入力Ａ２０１が、優先順位決定信号１０４がアサートされていれば、入力Ｂ２０２が選ばれる。
図３は要求セレクタの内部に含まれる要求セレクタ制御回路の例を示した図である。この場合の要求セレクタ制御回路は、図３の例に示す様に単純な構造となる。また、前記ａと異なり、単独の要求は優先順位にかかわらず選択可能となる。
ｃ．各要求が持つ優先順位に従って要求を処理するが、同じ優先順位であった場合のみ、優先順位決定信号に従い出力を決定する。この場合の要求セレクタ制御回路の動作内容について、どちらの入力もＶＡＬＩＤがネゲートされている場合は前記ｂのｉと、どちらかの入力のＶＡＬＩＤのみアサートされている場合は前記ｂのｉｉと同様である。両方のＶＡＬＩＤがアサートされている場合は、それぞれの要求が持つ優先順位の高いほうを選択する。優先順位が等しい場合は、優先順位決定信号によりＩＤのどちらかが選ばれる。
要求セレクタ制御回路の例は、入力ＡのＶＡＬＩＤをＶａ、入力ＢのＶＡＬＩＤをＶｂ、入力Ａの優先順位をＰａ、入力Ｂの優先順位をＰｂ、優先順位決定信号をＤとすると、論理式で、
【００１７】
【数式５】

と表せる。
図４は本発明に於けるアービタを、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した表図である。優先順位決定カウンタの値は、選択出力１０５を決定する度に１増やす。また、０からｎ−１までカウントするとラップラウンドして０に戻る。例えば、優先順位カウンタの値が０の場合、各ｂｉｔ全て０（ここではネゲート状態を０とする）であるため、全ての要求セレクタが上からの入力を優先し、一番上が最も優先順位が高くなる。優先順位カウンタの値が１（ここではアサート状態を１とする）の場合、１ｂｉｔ目のみ１となることから１段目の要求セレクタだけが下からの入力を優先し、アービタ入力が８個ある場合の優先順位は順に２、１、４、３、６、５、８、７となる。アービタ入力が８個ある場合の全優先順位を図４に列挙する。
このアービタを用いると、最優先順位はラウンドロビンで巡るが、それ以外は変則的な巡り方となる。しかしながら、最優先順位以外の各順位についても等しい確立で巡るため公平さは失われていない。単純なカウンタと、セレクタに小さな制御回路を付与することにより、最優先順位毎にアービタを準備することなく、図１４と同等の公平なアービタを構築することができる。
【００１８】
実施例２
アービタ入力数ｎが
【００１９】
【数式１】

でない場合について、アービタの構成例を示す。この場合、段数は
【００２０】
【数式７】

であり、ｒ段目には
【００２１】
【数式８】

個の要求セレクタがある（全体ではｎ−１個の要求セレクタがある）。優先順位決定カウンタのビット幅は
【００２２】
【数式７】

である。
まず、
【００２３】
【数式９】

となる最大のｔについて、
【００２４】
【数式１０】

個のアービタ入力に於ける実施例１の構成を基本とする。この実施例の１段目を２段目とし、新たに１段目に、
【００２５】
【数式１１】

個の要求セレクタをアービタ入力の変わりに接続する。取り外されたアービタ入力と残りの
【００２６】
【数式１１】

個のアービタ入力を、新たに付けた要求セレクタの入力に接続する。
優先順位決定カウンタは０からｎ−１まで変化させと、追加して設ける要求セレクタは１段目のどの位置であっても、各アービタ入力に最優先順位がラウンドロビンで回ることには変わりがない。
図５にアービタ入力数が１０の場合の構成例を示す。アービタ入力数が１０であるため、段数は全４段で３段が実施例と同じ構成である。従って、図１と同じ３段の要求セレクタ構成に２個の要求セレクタと残りの２つのアービタ入力加え、全体で１０個のアービタ入力とする。この場合、カウンタを０から９まで変化させることで、優先順位の２番目以降は均等に巡らないが、最優先順位はラウンドロビンで巡るアービタを構成することができる。
【００２７】
実施例３
本発明に於けるアービタについて、優先順位の割り当てを不均等にする例を述べる。
本発明のアービタは優先順位決定カウンタのｂｉｔ数と、それに繋げられた木構造の要求セレクタにより構成する。この木の構造やカウンタの開始数、ラップラウンド数や、カウント値を自由に変化させることで、優先順位を不均等に与える。
具体例として、４つのアービタ入力それぞれについて、要求の処理比を７：３：２：１にする場合を述べる。
図６は各アービタ入力について、不均等な優先順位を割り当てることができるアービタの例を示した図である。
まず木を図６に示す構造にする。この図のように、優先順位決定信号が全て結合していない構造や、完全木ではない不均衡な２進木の構造もとることができる。図６の構造において、優先順位決定カウンタが０から次にラップラウンドする１５までカウントすると、最優先順位となる数は、アービタ入力１が８回、アービタ入力２が４回、アービタ入力３が２回、アービタ入力４が２回となる。カウント値を０から１４までとすることで、最優先順位となる数は、アービタ入力１が８回、アービタ入力２が４回、アービタ入力３が２回、アービタ入力４が１回となる。さらに、優先順位決定カウンタが途中の４のカウントを飛ばし、カウントの開始値を１ではなく２にしてアービタ入力１が最優先順位となる数を１減らす。以上により、最優先順位となる数をアービタ入力１が７回、アービタ入力２が４回、アービタ入力３が２回、アービタ入力４が１回となり、結果、要求が処理される比が７：３：２：１となる。
【００２８】
実施例４
本発明に於けるアービタをクロスバ等の交換器と融合する例を述べる。
クロスバは各入力および出力のバーの交点にスイッチが設けられており、これらのスイッチを開閉することで競合しない限り、最多の入力と出力の組を自由に生成できるため、交換能力が高い。しかしながら、従来のルータやスイッチでは、アービタにより要求を調停した後、その結果に従ってクロスバで交換する構造をとるため、発生する遅延はアービタの遅延とクロスバの遅延の和となる。また、アービタとクロスバが効率よく稼動できなければパケット間にバブルが発生し、高速化やワイヤレート達成が困難となる。本発明では、アービタとクロスバ等の交換器を融合した交換アービタによりこれらの問題を解決する。
本発明に於けるアービタの各アービタ入力に要求ではなく直接パケットを投入し、図１の要求セレクタ１０２の中をパケットが直接通過する構成とすればクロスバが不要となる。この様な交換アービタは次のような利点がある。
１．拡張した要求セレクタにより構成された交換アービタを出力毎に設け、出力毎に全アービタ入力の競合が解決すれば、競合しない限り最多の入力と出力の組を自由に生成できる。従って、交換アービタはクロスバと同等の交換能力を持ち、クロスバ構成時に伴う３ステートバッファやワイヤードＯＲの問題を解決できる。
２．オメガ網などのＭＩＮ（Ｍｕｌｔｉｓｔａｇｅ　Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ　Ｎｅｔｗｏｒｋ）もセレクタ群により構成される画、ＭＩＮの多くはクロスバ程交換能力が高くない。また、クロスバと同等の交換能力を持つＭＩＮは構造と制御が複雑化する。交換アービタは交換能力においてクロスバと同等であるだけでなく、交換能力以外でもクロスバと同等の能力を持つ。例えば、クロスバ同様、複数の出力で同じ入力を選択すればマルチキャストを行うことができる。交換アービタは、クロスバとあらゆる意味で等価である。
３．交換アービタは、クロスバの遅延かアービタの遅延のどちらかを隠蔽できる。また、各要求セレクタが要求の選択とパケットの受け渡しを同時に行うパイプライン動作とすることで要求選択に伴う待ち時間も隠蔽できるため、低遅延化を図ることができる。
４．各要求セレクタや、一部の要求セレクタにバッファを設けることでパイプライン動作する交換アービタが構築可能である。段数が大きい場合や、パケットのｂｉｔ幅が大きい場合、動作周波数を高めたい場合など、構成が複雑化し処理時間が増大するため、パイプライン化された交換アービタが有効である。交換アービタは各段毎にパイプライン化することができ、高速化やワイヤレートの達成が容易である。
交換アービタに於ける交換の粒度はパケットの粒度に合わせる。即ち、パケットが自由に分断可能であれば、その分断可能な粒度に応じて優先順位決定カウンタの値を切り替える。切り替えるタイミングを変化させることで、各入力についての帯域保証を行う。
【００２９】
実施例５
ＩＰやＡＴＭ等に於けるルータやスイッチ（以下、単純にルータと呼ぶ）への本発明の応用について述べる。これらのルータに於いては、パケット毎の帯域幅の保証や実時間性の保障は重要な機能である。通常、これらの保障に伴う処理は出力バッファ（図１２の１２０４）に付与されたシェーパ（１２０５）で行われる。シェーパには、大容量の出力バッファ、制御論理回路、処理遅延が伴うが、本発明のアービタや交換アービタを適用することによりこれらの問題を解決することができる。
ここでは、要求セレクタ制御回路を用いた、パケット毎の帯域幅や実時間性の保障について述べる。
図７は本発明に於けるルータで用いるパケットフォーマットの例を示した図である。
パケットには帯域予約情報７０１および到着指定時刻７０２、優先順位７０３が記載されている。帯域予約情報や到着指定時刻、優先順位等の情報を明示的でも、暗黙的でも有していれば（例えば、前パケットと同様であるなどの情報等）、処理の単位はパケットでも、パケットを細かく分けたマイクロパケットやセルの形式でもよい。また、ＴＣＰやＩＰｖ４、ＩＰｖ６に含まれる情報を元に前記帯域予約情報や到着時刻を算出してもよい。
図８に本発明を適用したルータの構造の例を示す。ここでは交換アービタ８０２を利用する例を示すが、アービタとクロスバが別でもよい。図９にこのルータにおける交換アービタの構造を示す。各要求セレクタに指令を出す部位は、優先順位決定カウンタ１０３でも、優先順位決定スケジューラ９０３でもよい。このルータに於ける処理手順は以下の通りである。
まず、パケットは入力バッファ８０１に投入される。同時に、パケット解析部１００１において、宛先情報から出力ポートを特定する。この時、入力バッファを出力別に振り分けてもよい。また、帯域予約情報７０１および到着指定時刻７０２、優先順位情報７０３を抽出する。その後、パケットは入力バッファ８０１に投入される。
次に、交換アービタ８０２は入力バッファ８０１からパケットを引き出して前記抽出情報を元に調停を行う。調停を行う際には、各種サービスクラスへの対応が必要である。
ルータが備えるべきサービスクラスとしては、ＡＴＭに於けるＣＢＲ（Ｃｏｎｓｔａｎｔ　Ｂｉｔ　Ｒａｔｅ）、ｎｒ−ＶＢＲ（ｒｅａｌｔｉｍｅ−Ｖａｒｉａｂｌｅ　Ｂｉｔ　Ｒａｔｅ）、ｎｒｔ−ＶＢＲ（ｎｏｎｒｅａｌｔｉｍｅ−Ｖａｒｉａｂｌｅ　Ｂｉｔ　Ｒａｔｅ）、ＵＢＲ（Ｕｎｓｐｅｃｉｆｉｅｄ　ＢｉｔＲａｔｅ）、ＵＢＲ＋や、ＩＰに於けるＤＳ−ＥＦ（Ｄｉｆｆｓｅｒｖ―Ｅｘｐｅｄｉｔｅｄ　Ｆｏｒｗａｒｄｉｎｇ）、ＤＳ―ＡＦ（Ｄｉｆｆｓｅｒｖ−Ａｓｓｕｒｅｄ　Ｆｏｒｗａｒｄｉｎｇ）、ＢＥ（Ｂｅｓｔ　Ｅｆｆｏｒｔ）、ＩＳ−ＣＬ（ＩｎｔＳｅｒｖ−Ｃｏｎｔｒｏｌｌｅｄ　Ｌｏａｄ　Ｓｅｒｖｉｃｅ）、ＩＳ−ＧＳ（ＩｎｔＳｅｒｖ−Ｇｕａｒａｎｔｅｅｄ　Ｓｅｒｖｉｃｅ）等が知られている。ここでは、ＡＴＭのサービスクラスへの対応について述べる。それ以外についても同様に対応が可能である。
図９は本発明に於けるルータに含まれるアービタについて、帯域や実時間性をサポートする構造の例を示した図である。優先順位決定カウンタは単に値の増減を行うだけではなく、その値をスケジュールすることで様々なサービスクラスに対応することができる。サービスクラスへの対応方式には、優先順位決定カウンタを用い、各要求セレクタを複雑化して前記抽出情報を元に選択を行うことで対応する方式（方式Ｃ）と、各要求セレクタは単純で優先順位決定カウンタを優先順位決定スケジューラとすることで対応する方式（方式Ｓ）がある。
図１０に優先順位決定スケジューラを用いた場合のサービスクラスに対応する部位の構造を示す。要求セレクタを複雑化する場合は、スケジューラ設定部１００４の入力情報もデータとともにアービタに投入され、前記入力情報を元に各要求セレクタがどちらかの入力を決定する。
サービスクラスへの対応方法を述べる。まず、各入力に設けた帯域保証カウンタ９０１の値を、図７のへッダの帯域予約情報７０１を元にリセットする。この際、最も単純なリセット値を求める方式は、帯域予約情報と帯域保障カウンタの初期値を同一にすることである。その他にも、上位レイアの内部情報、管理者による設定、過去の通信履歴等を踏まえる方式がある。
方式Ｓでは、優先順位決定スケジューラ９０３に、全帯域を総量が変動可能なサイクリックバッファ（ＦＩＦＯ）９０４を設ける。優先順位決定スケジューラはカウンタの値を直接優先順位決定信号として用いるのではなく、サイクリックバッファ９０４の値を順次参照し優先順位決定信号として出力する。さらに、各入力に備え付けられた帯域保証カウンタ９０１の値に従ってサイクリックバッファ９０４に要求を書き込む。この要求が処理され、アービタを要求が通過するたびにサイクリックバッファの次の情報を読み出す。また、サイクリックバッファであるため、読み出して優先順位の決定を行うのと同時に、スケジュールの書き込みが可能である。サイクリックバッファが一周してある一定の場所を通過する毎に（例えばアドレス０）帯域保証カウンタ９０１をリセットする。サイクリックバッファが一周する前に全ての帯域保証カウンタが０になった場合は、キューが空ではない入力について引き続き転送を許可することでベストエフォート型の転送をサポートする。
各サービスクラスへの対応方法は以下のとおりである。ここでは、方式Ｃの要求セレクタもしくは方式Ｓのサイクリックバッファを決定因子と呼ぶ。
１．ＣＢＲでは、指定された帯域保証カウンタの値を忠実に守るため、キューが空であっても帯域保証カウンタが０になるまで決定因子に要求を出す。この場合要求に対する応答があってもキューが空であるため何も出力しない。
２．ｒｔ−ＶＢＲでは、指定された帯域保証カウンタの帯域が無くなっても追加して帯域を獲得できる。従って、帯域保証カウンタが０であってもキューが空でなければ決定因子に要求を出す。
３．ｎｒｔ−ＶＢＲでは、前記ｒｔ−ＶＢＲの方式に加えて追加要求が出せる数を制限できるように複数の帯域予約情報を用いる。まず、最低帯域保証値で帯域保証カウンタをリセットし、そのカウンタが０になった時点で最大帯域獲得可能値により最大帯域保障カウンタ９０２をリセットする。再び０になった場合は決定因子に要求を出さない。もしくは、最低帯域保証値で帯域保証カウンタを、最大帯域獲得可能値で最大帯域保証カウンタ９０２をリセットし、同時に両カウンタを減らす構成とする。
４．ＵＢＲは遅延や帯域に鈍感なため、他のカウンタが０である場合に決定因子に要求を出す、もしくはＵＢＲに固定な帯域保証値に従って帯域保証カウンタ９０１をリセットする等して実現する。
５．ＵＢＲ＋では平均速度が定義される。まず、平均帯域保証値で帯域保証カウンタ９０１をリセットする。帯域保証カウンタが０になった後もキューが空でなければ追加で決定因子に要求を出し、要求が通れば別の平均帯域保証カウンタを減ずる。それ以外の場合は平均帯域保証カウンタを増加させる。方式Ｃでは独自に設けた全体のサイクルを管理するカウンタ、方式Ｓサイクリックバッファが一周したとき再び平均帯域保証値で帯域保証カウンタをリセットするが、このとき平均帯域保証カウンタの値を加味することで平均帯域を守る。
この様に、複数の帯域保証値やカウンタを操作することで種々のサービスカテゴリに対応する。
全帯域カウンタが０になっても、まだ帯域保証カウンタが０でない場合は、キューの中にある該当要求を廃棄するかスムージングするかを選択する。この選択手段としてはへッダに明示的に破棄可能かどうかを記載する方式や、上位レイヤの情報に従う方式、管理者が直接指定する方式、該当する帯域保証サービスクラスにより指定する方式、上位レイアでＩＰを用いている場合はＴＣＰ／ＵＤＰ別で指定する方式等がある。
これらの帯域保障と同時に、実時間性の保障を行う。現在時刻時計１００２と、到着指定時刻７０２の差を猶予時間算出器１００３で随時求める。時刻情報はＧＭＴ等の基準となる時刻に変換して用いるか、ロケール情報付与したローカルタイムを利用する。この時、到着指定時刻および猶予時間の粒度が細かすぎると情報量が増え、荒すぎると細やかな管理ができなくなるため、利用するアプリケーション毎に粒度がある程度自由に設定する（例えば、動画であればそのフレーム速度に合わせる等）。
以上の各入力より集められた帯域保障カウンタ９０１の値、最大帯域保障カウンタ９０２の値、猶予時間算出器１００３の値を元に調停を行う。
方式Ｃでは、帯域保障カウンタ９０１の値、最大帯域保障カウンタ９０２の値より出される要求の有無（ＶＡＬＩＤ）と猶予時間を元に、実施例１のｃの方式に従って要求セレクタ制御回路を動作させる。構造が非常に単純で、小型化、高速化が容易な方式である。
方式Ｓでは、スケジューラ設定部１００４に於いて前記帯域保障カウンタ９０１の値、最大帯域保障カウンタ９０２の値、猶予時間算出器１００３の値を元にサイクリックバッファ９０４の設定を行う。この設定に本発明におけるアービタを再び用いると、方式Ｓと類似した調停結果となる。また、その他の方式によりサイクリックバッファの値を決定することで柔軟性が増す。例えば、乱数により任意抽出する方式、プログラムにより制御する方式等がある。しかしながら方式によっては規模や遅延が増大する可能性がある。
方式Ｃと方式Ｓのハイブリッド構成も可能である。例えば、帯域保障については方式Ｓを用い、実時間保障については方式Ｃを用いる等が可能である。
【００３０】
実施例６
より忠実な優先順位処理を行うアービタもしくは交換アービタの構成として、優先順位毎にアービタを設ける例を示す。
図１１にアービタを複数準備する場合の構成を示す。パケットは、優先順位毎に用意されたアービタ１１０１に投入される。アービタの出力はさらに、優先順位選択器１１０２により優先順位毎に重みをつけて選択され最終的な出力となる。この優先順位選択器にも本発明に於けるアービタを適用する。アービタを複数準備するため論理回路規模が大きくなり実装が困難となる場合は、アービタを優先順位毎に時分割で利用する。
本発明により、パケットもしくは要求毎といった粒度の細かい帯域予約と保証、実時間性の保証を少ない論理回路規模、かつ低遅延で実現可能である。が行えることで、ネットワークを有効に活用し、種々のサービスに対応することができる。
【００３１】
実施例７
流量制御に用いる情報を元に適応ルーティングを行う例について述べる。
本発明によるルータは入力バッファのみ流量制御を行えば、廃棄が好ましくないパケットを破棄せずに遅延させることが可能となる。また、この流量管理により得られる情報を元に、適応ルーティングを行うことができる。本発明によるルータは適応ルーティングを行うような場合でも帯域を保障することができ、流量制御を用いた適応ルーティングに適している。
流量制御の手段として用いられるバックプレッシャーやｃｒｅｄｉｔ　ｂａｓｅｄ　ｆｌｏｗ　ｃｏｎｔｒｏｌを利用する。ｃｒｅｄｉｔ（相手スイッチに於ける空きバッファ容量の情報）、もしくは、バックプレッシャーに於けるハンドシェイク頻度を解析すると相手スイッチの混雑度を知ることができる。この結果を利用して、ホットスポットを回避する適応ルーティングや優先順位決定する。
あるパケットが複数の出力ＡとＢを選択可能である場合、出力Ａのｃｒｅｄｉｔ数が出力Ｂのｃｒｅｄｉｔ数よりも多い場合、出力Ａの方が混雑していないと予想できるため、出力Ａを選択する。バックプレッシャーを利用する場合は、最近の転送停止時間を計測する。転送停止時間が長いほど混雑していると予想できる。
また、上記流量制御に用いる情報を実施例６における決定因子の判断材料に用いることも可能である。通常、帯域制限情報を正しく設定し正常に通信が行われていれば、スタベーションを回避したいパケットのスタベーションが回避できる。しかしながら、設定を誤った際や、回線不良により他回線が迂回してくることに伴う実質帯域の不足が発生したときには、混雑による輻輳が発生し帯域が保障できなくなる。この場合、帯域が保障されるべきパケット全体について、割り当てられた帯域を均等に削減することが望ましい。流量制御に用いる情報を元に混雑状況を知ることで、混雑状況に応じてパケットの帯域の保障値を均等に削減することができる。
【００３２】
【発明の効果】
本発明によれば、回路規模が小さく低遅延で公平なアービタを構築することができ、ルータに適用することで、小規模かつ、大容量、低遅延、低コストであり、帯域と実時間性を保障するルータが実現可能となる。
本発明に於けるアービタは、その構造が単純であるばかりではなく、直接パケットをアービタに投入することでクロスバと同等の能力をもつ交換器を構成することが可能となる。
また、アービタ自体が帯域や実時間性の保証を行うため、出力バッファにシェーパと呼ばれる回路や、それに伴う大容量の出力バッファが不要となる。入力バッファからのパケットの取り出し方や、アービタ内部の通過の仕方により帯域および実時間性が保障されるため、入力バッファのみ流量制御されていれば輻輳の際にも破棄が好ましくないパケットを破棄せず遅延させることが可能となる。この流量制御の情報を用いて優先順位の決定や流量制御を行うことで混雑および輻輳の回避や、ネットワーク全体の負荷分散を図ることができる。
今後のネットワーク社会においては、ストリーム等の大容量トラフィックに於けるアプリケーション単位での帯域や品質が問われるが、その対応を可能とする。
【図面の簡単な説明】
【図１】本発明に於けるアービタ構成の例として、８個のアービタ入力について最も均等に優先順位が割り当てられる構成を示したブロック図である。
【図２】本発明に於けるアービタの内部に含まれる各要求セレクタの構成例を示したブロック図である。
【図３】要求セレクタの内部に含まれる要求セレクタ制御回路の例を示したブロック図である。
【図４】本発明に於けるアービタを、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した表図である。
【図５】本発明に於けるアービタを、１０個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の例を示したブロック図である。
【図６】各アービタ入力について、不均等な優先順位を割り当てることができるアービタの例を示したブロック図である。
【図７】本発明に於けるルータで用いるパケットフォーマットの例を示したフォーマット図である。
【図８】本発明に於けるルータの構成例を示したブロック図である。
【図９】本発明に於けるルータに含まれるアービタについて、帯域や実時間性をサポートする構造の例を示したブロック図である。
【図１０】帯域や実時間性をサポートするため、優先順位決定カウンタを拡張した優先順位決定スケジューラにより各種サービスクラスに対応する構造の例を示したブロック図である。
【図１１】本発明に於けるルータについて、各優先順位毎に異なるアービタを適用した例を示したブロック図である。
【図１２】従来の帯域や実時間処理を行うルータの構成例を示したブロック図である。
【図１３】従来のキューベースのアービタの構成例を示したブロック図である。
【図１４】従来のラウンドロビンアービタの構成例を示したブロック図である。
【図１５】従来のラウンドロビンアービタにおいて、８個のアービタ入力で最も均等に優先順位配分が行われる様に構成した場合の、各順位の優先順位割り当てを示した表図である。
【符号の説明】
１０１　　　　　　アービタ入力
１０２　　　　　　要求セレクタ
１０３　　　　　　優先順位決定カウンタ
１０４　　　　　　優先順位決定信号
１０５　　　　　　選択出力
２０１　　　　　　要求の入力Ａ
２０２　　　　　　要求の入力Ｂ
２０３　　　　　　ＩＤの入力
２０４　　　　　　ＶＡＯＩＤの入力
２０５　　　　　　要求セレクタ制御回路
８０１　　　　　　本発明に於けるルータで用いる入力バッファ
８０２　　　　　　交換アービタ
９０１　　　　　　帯域保証カウンタ
９０２　　　　　　最大帯域保証カウンタ
９０３　　　　　　優先順位決定スケジューラ
１００１　　　　　サイクリックバッファ
１１０１　　　　　優先順位毎に設ける交換アービタ
１１０２　　　　　優先順位選択器
１２０１　　　　　従来の入力バッファ
１２０２　　　　　従来のアービタ
１２０３　　　　　クロスバ
１２０４　　　　　出力バッファ部
１２０５　　　　　シェーパ
１３０１　　　　　要求振分け器
１３０２　　　　　要求キュー
１３０３　　　　　選択器
１４０１　　　　　固定優先順位アービタの一例。[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a large-capacity packet low-delay switching system in communication, and more particularly to a packet switch (for example, a crossbar) and an arbiter (arbiter) thereof in a large-capacity packet low-delay switching system. As the packet, in particular, an Ethernet frame or an ATM cell is accepted.
[0002]
[Prior art]
[Patent Document 1]
JP-A-2000-198715
[Patent Document 2]
JP 2001-326688 A
[Patent Document 3]
JP-A-10-232765
[Patent Document 4]
Patent No. 322436
[Patent Document 5]
JP-A-2000-40061
[Patent Document 6]
JP-A-11-341061
[Patent Document 7]
JP-A-2001-237886
[Patent Document 8]
JP-A-9-46367
[Patent Document 9]
JP-A-2001-11116
[Patent Document 10]
JP-A-2001-177562
[Patent Document 11]
JP-A-2001-223709
[Patent Document 12]
JP 2001-285352A
[Patent Document 13]
JP-A-2001-320409
[Non-patent document 1]
Crossbar Networks in "Interconnection Networks: an Engineering Approach, Jose Duato, et al., IEEE Computer Science Press, ISBN: 0818870803".
[Non-patent document 2]
"Study on Performance of Traffic Shaping Mechanism" (IEICE Technical Report SSE96-115)
In the communication field, various router and switch configuration technologies satisfying demands for broadband, high quality, and low delay have been proposed. In particular, the crossbar and the arbiter, which are the components of the router, are important parts related to broadband, high quality, and low delay.
The operation will be described based on the configuration of the conventional basic router shown in FIG. For each packet input to a plurality of inputs of the router, information such as the destination, priority, and designated arrival time is checked in the input buffer 1201 of the router, and the information is transmitted to the arbiter 1202 as a request. The arbiter processes the requests at the plurality of arbiter inputs and determines an appropriate arbiter input and arbiter output pair. The crossbar 1203 sets a route based on this set of information, so that the packet is transferred from the input buffer 1201 to the output buffer 1204.
For the crossbar 1203 and the arbiter 1202, which are the basic configurations of the router, refer to “Interconnection Networks: an Engineering Approach, Jose Duato, et al., IEEE Computer Science Press, ISBN: 08876800kN. Also, regarding the shaper 1205 for performing processing such as bandwidth guarantee in the output buffer, see JP-A-2000-198715 and JP-A-2001-326688, and “Study on Performance of Traffic Shaping Mechanism” (IEICE Technical Report). SSE96-115).
In order to increase the capacity, reduce the delay, and reduce the cost of the router, it is necessary to simplify and reduce the size of the logic circuit. As a result of the miniaturization of the logic circuit, large-capacity wiring and high-speed logic inside the chip can be sufficiently used, and the cost can be reduced by reducing the number of chips and the board area. On the other hand, the support of advanced QoS (Quality of Service) involves complicated processing, which causes an increase in logical scale and an increase in delay. In general, the delay of a router used in a SAN (System Area Network) is several hundred ns, whereas the delay of an IP router is several tens μs, which is about two digits apart. It has contributed.
In order to increase the capacity, reduce the delay, and reduce the cost of the router, the present invention focuses on arbiters and crossbars, which are the components of the router. First, an existing configuration example of the arbiter will be described.
FIG. 13 shows a queue-based arbiter. Each request is stored in the request queue 1302 for each priority or destination by the distributor 1301. Each of the requests stored in the request queue 1302 is received by the selector 1303 in descending order of priority. This method has high fairness because it has queues composed of FIFOs for each priority, and fine arbitration control is possible according to the number of queues. However, the memory required for the queue is large, and a large logical scale is required for processing for managing the queue (processing when the queue overflows, etc.), which cannot contribute to a reduction in delay. The selector 1303 also needs to be devised to prevent starvation (a state in which only the request with the highest priority is continuously received, and other requests are not accepted). If fairness is pursued, it becomes complicated.
The round robin arbiter is an arbiter in which the highest priorities are evenly distributed in order and the highest priorities are always equally allocated. The round robin arbiter has various configurations.
FIG. 14 shows a structure in which a plurality of tree structures 1401 having different highest priorities are prepared by the distributor 1301 and the priorities are determined. The tree structure has fewer comparison stages than the daisy chain structure. Each comparator gives priority to an arbiter input from above or an arbiter input from below. If all the comparators give priority to the arbiter input from the top, the top has the highest priority, and if the arbiter input from the bottom has priority, the bottom has the highest priority. If there are n comparison targets, the number of stages is
[0003]
[Formula 7]

And the total number of comparators is n-1.
The round-robin arbiter shown in FIG. 14 has an advantage that not only the highest priority but also lower-priority orders are round-robin depending on the configuration.
FIG. 15 is a diagram showing priority order assignment in each order in a conventional round-robin arbiter in a case where priority order distribution is performed evenly with eight arbiter inputs. The arbiter shown in FIG. 14 not only has the highest priority as shown in FIG. However, since a tree structure is required for each priority, the number of logic circuits is large.
As another method, there is a structure in which one request is processed for each clock. The token is moved every clock, and the arbiter input which has acquired the token has the highest priority, and only the request existing in the arbiter input is processed. Although this technique can be expected to reduce the logic circuit size to some extent, delay is a problem because only one request is evaluated for each clock.
In the configuration shown in FIG. 14 in which the arbiter components provided for each priority are fixed and the priority is fixed, the logic circuit scale is small, but the starvation of the request may occur. FIG. 7 of JP-A-10-232765 corresponds to this.
In the field of IP, the line speed is going to exceed the processing speed of the logic circuit, and even if a large capacity line is introduced, there is a problem that the effective throughput is reduced. To solve this problem, it is necessary to simplify the existing logic circuit and improve the effective throughput by maintaining a processing speed equivalent to the line speed.
It is also necessary to consider the QoS at the time of failure. Conventionally, in order to maintain QoS at the time of occurrence of a failure, a solution is sought by prompting resetting of a bandwidth guarantee value.
[0004]
[Problems to be solved by the invention]
An object of the present invention is to reduce the logic circuit scale of an arbiter and a crossbar in consideration of QoS, and to achieve a large capacity, low delay, and low cost of a router. In particular, in increasing the capacity, it is necessary to improve the effective throughput, not the sum of the line capacities.
The present invention solves the following problems of the conventional method.
1. P322214 is an invention specializing in scheduling, in which requests are sequentially generated in a reservation table (time slot) for receiving requests. Although the use efficiency of the crossbar increases, the amount of logic circuits in the reservation table and its control mechanism is large. Further, the invention does not consider the priority of requests. Filling the reservation table in consideration of the priority of the request requires a calculation amount proportional to the type of the priority, and it is difficult to reduce the size and reduce the delay.
2. Japanese Patent Application Laid-Open No. 2000-40061 is an invention relating to a bus arbiter and can prevent starvation. The arbiter used in the present invention is a bus use right arbitration unit (63 in FIG. 1 of Japanese Patent Application Laid-Open No. 2000-40061), the inside of which is shown in an explanatory diagram (FIG. 5 in the specification) of the bus use right arbitration system. Have been. This is a simple arbiter that arbitrates four types of buses. However, arbitration results must be calculated in consideration of 33 combinations for nine types of signal inputs that are used to determine arbitration. Large and the delay also increases.
Priority control along with guaranteeing bandwidth and real-time performance is an important role of a router. In particular, securing the band associated with the transmission completion time and the real-time data requires calculation cost and the amount of logic circuits, which causes a delay. The conventional method has the following problems.
3. Regarding the securing of the bandwidth related to the transmission completion time, Japanese Patent Application Laid-Open No. H11-341061 discloses that the instruction of the bandwidth guarantee and the actual transfer are different packets, and each terminal calculates the bandwidth. Also in Japanese Patent Laid-Open No. 2001-237886, each terminal calculates the bandwidth because the terminal on the transmitting side guarantees the bandwidth. These two embodiments cannot cope with adaptive routing because the bandwidth cannot be guaranteed for each packet.
4. Japanese Patent Application Laid-Open No. 9-46367 discloses a method of securing a bandwidth related to real-time data, which is connection-based and cannot determine adaptive bandwidth because the bandwidth is determined by a route, so that real-time performance cannot be guaranteed for each packet. In Japanese Patent Application Laid-Open No. 2001-11619, the bandwidth can be specified for each packet. However, since the bandwidth is guaranteed by queue-based arbitration, both the circuit size and the delay increase. In P2001-177562A, the transmission buffer unit serves as a shaper to control the band, so that the circuit size of the shaper is large, and a large output buffer is required to improve the performance of the shaper. In JP-A-2001-223709 and JP-A-2001-285352, both the circuit scale and the delay increase because the queue-based band control is performed. Japanese Patent Application Laid-Open No. 2001-320409 installs a server and controls the entire band control information based on information in a database. Therefore, the present invention provides a mechanism for centrally managing the entire network. If the bandwidth of each packet is managed using this invention, the load of centralized management is high and the effective throughput is not improved.
5. Conventionally, the arbiter and the crossbar are provided separately. If the control of the arbiter and the control of the crossbar are not performed efficiently, a bubble will be generated between the output packets, which may not be able to achieve the wire rate. When the crossbar is implemented by an ASIC, a logic circuit (such as a three-state buffer or a wire rate OR) corresponding to each contact switch may not be provided. Even if it is present, problems such as a difficulty in static delay analysis, delay tuning of a three-state buffer bus, and power estimation, and a decrease in a failure detection rate by automatic diagnosis often accompany.
6. Conventionally, the QoS at the time of occurrence of a failure has been solved by prompting the resetting of the bandwidth guarantee value in order to maintain the QoS at the time of the occurrence of the failure. Despite the fact that the bandwidth is limited due to the failure, new traffic is required to prompt the resetting of the bandwidth guarantee value, and the solution cannot be solved by the router alone, but must be solved by the entire system. Therefore, there are problems that the network is unnecessarily confused when a failure occurs, and that it takes time to deal with the failure.
[0005]
[Means for Solving the Problems]
In order to solve the above-mentioned problem, the present invention uses the following means.
1. An arbiter which has an arbiter input on leaves and a request selector on a branch and which resolves the priority by controlling the request selector according to a counter or scheduler for determining the priority which is attached is used. Since the structure is simple, the logic implementation scale is small, high-speed operation is possible, and low delay can be achieved.
2. The arbiter is configured by a selector that prioritizes the higher priority first in the comparison of the priority and, when the priorities are equal, uses either the counter or the output of the scheduler to determine the priority. You. As a result, even when the priorities of all the requests are equal, an arbiter that circulates the highest priority in a round-robin manner and fairly traverses the other priorities can be configured. It is also possible to configure an arbiter in which the priorities are unequal.
3. By directly passing packets through the arbiter, an arbiter having a switch equivalent to a crossbar is used as an arbiter, and at the same time, the capacity, the delay, and the cost are reduced by reducing the number of circuits. This arbiter can exchange variable-length packets at the wire rate (the ideal state where the effective input throughput and the effective output throughput are equal), and the effective throughput is also improved.
4. The arbiter can be controlled for each request such as a packet. Therefore, a setup message is not required when reserving a bandwidth, so that the bandwidth can be reserved and guaranteed even on adaptive routing. In addition, global time can be managed for real-time security.
5. By applying the structure of the arbiter to a router, it is possible to guarantee bandwidth and real-time performance. In this router, the arbiter performs all processes related to bandwidth and real-time guarantee. As a result, a large-capacity output buffer and a shaper for controlling the output buffer are not required, so that the output buffer size can be reduced and the cost can be reduced.
6. Since the arbiter limits the bandwidth, if the input queue in the preceding stage performs flow control (credit based flow control, back pressure, etc.) with the partner router, even if communication over the reserved bandwidth is performed, packets that are not discarded are preferable. It can be delayed without discarding. It is not necessary to retransmit the request accompanying the result discarding, and the effective throughput of the entire network is improved.
7. When the bandwidth is reduced due to a failure or the like and congestion occurs, the degree of congestion can be known from the flow control information that is exchanged from usual. This information allows the router to voluntarily limit the bandwidth. As a result, unnecessary confusion of the network in maintaining the QoS when a failure occurs can be avoided, and the failure can be quickly dealt with. According to one aspect of the present invention, a router for communication includes the arbiter for ensuring bandwidth and real-time performance and an associated or integrated switch.
[0006]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings. In the following embodiments, a router is used as an example, but the present invention is not limited to a router, and can be applied to a case where arbitration of requests is required.
Example 1
FIG. 1 shows a configuration example of an arbiter according to the present invention. In this figure, eight arbiter inputs 101 are shown.
[0007]
[Formula 1]

Can be similarly expanded or contracted.
Here, the number of arbiter inputs is generally
[0008]
[Formula 1]

Is shown. At this time, the configuration is as follows.
1. If there are n arbiter inputs 101, the number of stages is
[0009]
[Formula 2]

And in the r-th stage
[0010]
(Equation 3)

There are a number of request selectors 102 (a total of n-1 request selectors). The bit width of the priority determination counter 103 is
[0011]
[Formula 2]

It is.
2. The n arbiter inputs are (0, 1), (0, 2), ‥‥, (0, n), respectively. Also, the request selectors in the r-th stage are (r, 1), (r, 2),.
[0012]
(Equation 4)

And
3. The r-th stage request selector (r, c) receives two outputs, (r-1, 2c-1) and (r-1, 2c), which are r-1 stage request selectors or arbiter inputs. , The selection is performed based on the output of the r-th bit of the priority determination counter, and the request selector of the (r + 1) th stage
[0013]
(Equation 5)

Pass the result to.
4. The request selector (r, c) at the r-th stage selects one of the two inputs of the request selector with priority according to the priority determination signal 104 output from the bit r of the priority determination counter. When the selection is performed sequentially, one of them finally becomes the selection output 105.
There are the following methods for selection in the request selector.
a. The output is unconditionally determined according to the priority determination signal. Therefore, even if there is a single request (there is no other conflicting request), it is not processed unless the highest priority is obtained.
b. Only when the requests conflict, the output is determined according to the priority determination signal.
FIG. 2 shows the structure of the request selector in this case. Each of the input A201 and the input B202 of the request includes an ID 203 and a VALID 204 indicating whether the ID is valid or invalid. The selector selects one of the inputs according to the output of the request selector control circuit 205. The operation of the request selector control circuit is as follows.
[0014]
i) If the VALID of both inputs is negated (inactive), it is sufficient to negate the output of the VALID, and the ID can be anything. Therefore, either ID or VALID may be output.
[0015]
ii) If only one of the input VALIDs is asserted (active), the VALID outputs the asserted ID and VALID.
[0016]
iii) When the VALID of both inputs is in the asserted state, one of the IDs is selected by the priority determination signal 104 because it is necessary to select one of them. For example, if the priority determination signal is negated, the input A201 is selected, and if the priority determination signal 104 is asserted, the input B202 is selected.
FIG. 3 is a diagram showing an example of the request selector control circuit included in the request selector. The request selector control circuit in this case has a simple structure as shown in the example of FIG. Also, unlike the above a, a single request can be selected regardless of the priority.
c. The requests are processed according to the priority of each request, but only when the requests have the same priority, the output is determined according to the priority determination signal. The operation contents of the request selector control circuit in this case are the same as i of b above when VALID is negated for both inputs and the same as ii of b above when only VALID of either input is asserted. is there. If both VALIDs are asserted, the higher priority of each request is selected. If the priorities are equal, one of the IDs is selected by the priority determination signal.
An example of the request selector control circuit is represented by a logical expression, assuming that the VALID of the input A is Va, the VALID of the input B is Vb, the priority of the input A is Pa, the priority of the input B is Pb, and the priority determination signal is D. ,
[0017]
(Equation 5)

Can be expressed as
FIG. 4 is a table showing priority assignment in each order when the arbiter according to the present invention is configured so that the priority distribution is most evenly performed with eight arbiter inputs. The value of the priority determination counter is incremented by one each time the selection output 105 is determined. When counting from 0 to n-1, the lap round is performed and the wrap round is returned to 0. For example, when the value of the priority counter is 0, all bits are 0 (here, the negated state is 0), so that all request selectors give priority to input from the top, and the highest priority is the highest priority. Will be higher. When the value of the priority order counter is 1 (asserted state is 1 in this case), only the first bit becomes 1, so only the first-stage request selector gives priority to the input from below, and there are eight arbiter inputs. In this case, the priorities are 2, 1, 4, 3, 6, 5, 8, and 7, respectively. FIG. 4 lists all priorities when there are eight arbiter inputs.
When this arbiter is used, the top priority is round robin, but otherwise, it is an irregular way. However, fairness is not lost because each rank other than the highest priority has the same probability. By providing a simple counter and a small control circuit for the selector, a fair arbiter equivalent to that shown in FIG. 14 can be constructed without preparing an arbiter for each highest priority.
[0018]
Example 2
Arbiter input number n is
[0019]
[Formula 1]

If not, an example of the configuration of the arbiter will be described. In this case, the number of stages
[0020]
[Formula 7]

And in the r-th stage
[0021]
(Equation 8)

There are (n-1) request selectors in total. The bit width of the priority determination counter is
[0022]
[Formula 7]

It is.
First,
[0023]
Equation 9

For the largest t
[0024]
(Equation 10)

Basically, the configuration of the first embodiment in the number of arbiter inputs is used. The first stage of this embodiment is the second stage, and the first stage is newly
[0025]
[Equation 11]

Request selectors instead of arbiter inputs. Removed arbiter input and remaining
[0026]
[Equation 11]

Arbiter inputs are connected to the inputs of the newly attached request selector.
When the priority determination counter is changed from 0 to n−1, the additional priority of the request selector provided at any position of the first stage is such that the highest priority is round-robin for each arbiter input. Absent.
FIG. 5 shows a configuration example when the number of arbiter inputs is 10. Since the number of arbiter inputs is 10, the number of stages is four in total, and three stages have the same configuration as the embodiment. Therefore, two request selectors and the remaining two arbiter inputs are added to the same three-stage request selector configuration as in FIG. 1 to make a total of ten arbiter inputs. In this case, by changing the counter from 0 to 9, it is possible to configure an arbiter that does not go round evenly after the second priority but rounds the highest priority round robin.
[0027]
Example 3
An example in which the arbiters according to the present invention make the assignment of priorities uneven will be described.
The arbiter of the present invention is composed of the number of bits of the priority order determination counter and a request selector having a tree structure connected to the number of bits. By freely changing the structure of the tree, the number of start counters, the number of wrap rounds, and the count value, priority is given unevenly.
As a specific example, a case where the request processing ratio is set to 7: 3: 2: 1 for each of the four arbiter inputs will be described.
FIG. 6 is a diagram showing an example of an arbiter to which unequal priorities can be assigned to each arbiter input.
First, the tree is structured as shown in FIG. As shown in this figure, a structure in which all the priority determination signals are not combined or a structure of an imbalanced binary tree which is not a complete tree can be obtained. In the structure of FIG. 6, when the priority determination counter counts from 0 to 15 at which the next lap round occurs, the highest priority numbers are 8 for arbiter input 1, 4 for arbiter input 2, and 2 for arbiter input 3. Arbiter input 4 twice. By setting the count value from 0 to 14, the highest priority numbers are eight for arbiter input 1, four for arbiter input 2, two for arbiter input 3, and one for arbiter input 4. Further, the priority order determination counter skips the count of 4 in the middle and sets the start value of the count to 2 instead of 1, thereby reducing the number of arbiter inputs 1 having the highest priority by 1. As described above, the number of the highest priority is 7 for arbiter input 1, 4 for arbiter input 2, 2 for arbiter input 3, and 1 for arbiter input. As a result, the request processing ratio is 7: 3: 2: 1.
[0028]
Example 4
An example in which the arbiter according to the present invention is integrated with an exchanger such as a crossbar will be described.
The crossbar is provided with a switch at the intersection of each input and output bar, and as long as there is no conflict by opening and closing these switches, the maximum number of input and output pairs can be freely generated, and thus the exchange capacity is high. However, in a conventional router or switch, a request is arbitrated by an arbiter, and then a crossbar is exchanged in accordance with the result. Therefore, the generated delay is the sum of the arbiter delay and the crossbar delay. Also, if the arbiter and the crossbar cannot operate efficiently, bubbles will be generated between packets, making it difficult to achieve high speed and achieve a wire rate. In the present invention, these problems are solved by a switching arbiter in which an arbiter and a switch such as a crossbar are integrated.
In the present invention, if a packet is directly input instead of a request to each arbiter input of the arbiter, and the packet passes directly through the request selector 102 in FIG. 1, a crossbar becomes unnecessary. Such an exchange arbiter has the following advantages.
1. If an exchange arbiter constituted by an extended request selector is provided for each output and the conflict of all arbiter inputs is resolved for each output, the maximum number of input and output pairs can be freely generated as long as no conflict occurs. Therefore, the exchange arbiter has the same exchange capability as the crossbar, and can solve the problems of the three-state buffer and the wired OR associated with the configuration of the crossbar.
2. An MIN (Multistage Interconnection Network) such as an omega network is also composed of a group of selectors, and many MINs do not have as high an exchange capability as a crossbar. The MIN having the same exchange capacity as the crossbar has a complicated structure and control. The exchange arbiter is not only equivalent to the crossbar in exchange ability, but also has the same ability as the crossbar other than exchange ability. For example, similarly to a crossbar, multicasting can be performed by selecting the same input for a plurality of outputs. An exchange arbiter is equivalent in every way to a crossbar.
3. The switching arbiter can hide either the crossbar delay or the arbiter delay. In addition, since each request selector performs a pipeline operation in which selection of a request and delivery of a packet are performed at the same time, a waiting time associated with the selection of a request can be concealed, so that a delay can be reduced.
4. By providing a buffer for each request selector or some request selectors, a switching arbiter that operates in a pipeline can be constructed. When the number of stages is large, when the bit width of the packet is large, or when it is desired to increase the operating frequency, the configuration becomes complicated and the processing time increases. Therefore, a pipelined switching arbiter is effective. The switching arbiter can be pipelined for each stage, and it is easy to achieve a high speed and a wire rate.
The granularity of the exchange in the exchange arbiter matches the granularity of the packet. That is, if the packet can be freely divided, the value of the priority determination counter is switched according to the granularity at which the packet can be divided. By changing the switching timing, the bandwidth is guaranteed for each input.
[0029]
Example 5
An application of the present invention to a router or a switch (hereinafter, simply referred to as a router) in an IP or an ATM will be described. In these routers, the guarantee of the bandwidth for each packet and the guarantee of real-time performance are important functions. Usually, the processing accompanying these guarantees is performed by the shaper (1205) provided to the output buffer (1204 in FIG. 12). The shaper involves a large output buffer, a control logic circuit, and a processing delay. These problems can be solved by applying the arbiter and the switching arbiter of the present invention.
Here, the guarantee of the bandwidth and the real-time property of each packet using the request selector control circuit will be described.
FIG. 7 is a diagram showing an example of a packet format used in the router according to the present invention.
In the packet, bandwidth reservation information 701, designated arrival time 702, and priority 703 are described. If the information such as the bandwidth reservation information, the designated arrival time, and the priority is explicitly or implicitly included (for example, information such as the same as the previous packet), the processing unit is the packet. It may be in the form of micro-packets or cells that are subdivided. Further, the band reservation information and the arrival time may be calculated based on information included in TCP, IPv4, and IPv6.
FIG. 8 shows an example of the structure of a router to which the present invention is applied. Here, an example in which the exchange arbiter 802 is used is shown, but the arbiter and the crossbar may be different. FIG. 9 shows the structure of the switching arbiter in this router. The part that issues a command to each request selector may be the priority determination counter 103 or the priority determination scheduler 903. The processing procedure in this router is as follows.
First, a packet is input to the input buffer 801. At the same time, the packet analyzer 1001 specifies an output port from the destination information. At this time, the input buffer may be assigned to each output. In addition, band reservation information 701, designated arrival time 702, and priority order information 703 are extracted. Thereafter, the packet is input to the input buffer 801.
Next, the switching arbiter 802 extracts a packet from the input buffer 801 and performs arbitration based on the extracted information. When arbitrating, it is necessary to respond to various service classes.
The service classes that the router should have are as follows: CBR (Constant Bit Rate), nr-VBR (realtime-Variable Bit Rate), nrt-VBR (nonrealtime-Variable Bit Rate), UBR (UnifiedBite, UBR + UnlimitedBite) in ATM. DS-EF (Diffserv-Expected Forwarding), DS-AF (Diffserv-Assured Forwarding) in IP, BE (Best Effort), IS-CL (IntServ-Control-Service-Government Service) ) Are known. Here, the correspondence of the ATM to the service class will be described. The other cases can be similarly handled.
FIG. 9 is a diagram showing an example of a structure that supports the bandwidth and the real-time property of the arbiter included in the router according to the present invention. The priority determination counter does not merely increase or decrease the value, but can respond to various service classes by scheduling the value. As a method for responding to a service class, a priority order determination counter is used, each request selector is complicated, and a selection is made based on the extracted information (method C). There is a corresponding method (method S) by using the priority determination counter as a priority determination scheduler.
FIG. 10 shows a structure of a part corresponding to a service class when the priority determination scheduler is used. When the request selector is complicated, the input information of the scheduler setting unit 1004 is also input to the arbiter along with the data, and each request selector determines one of the inputs based on the input information.
This section describes how to handle service classes. First, the value of the bandwidth guarantee counter 901 provided for each input is reset based on the bandwidth reservation information 701 of the header in FIG. At this time, the simplest method of obtaining the reset value is to make the initial value of the bandwidth reservation information and the bandwidth guarantee counter the same. In addition, there is a method based on internal information of the upper layer, a setting by an administrator, a past communication history, and the like.
In the method S, a cyclic buffer (FIFO) 904 capable of varying the total amount of the entire band is provided in the priority determination scheduler 903. The priority determination scheduler does not use the value of the counter directly as the priority determination signal, but sequentially refers to the value of the cyclic buffer 904 and outputs it as the priority determination signal. Further, a request is written to the cyclic buffer 904 according to the value of the bandwidth guarantee counter 901 provided for each input. This request is processed and the next information in the cyclic buffer is read each time the request passes through the arbiter. Further, since the buffer is a cyclic buffer, it is possible to write a schedule at the same time as reading and determining the priority. The bandwidth guarantee counter 901 is reset every time the cyclic buffer passes a certain place (for example, address 0). If all the bandwidth guarantee counters become 0 before the cyclic buffer makes one round, the best-effort transfer is supported by continuously permitting transfer of an input whose queue is not empty.
The corresponding method for each service class is as follows. Here, the request selector of the method C or the cyclic buffer of the method S is called a determinant.
1. In CBR, in order to adhere to the value of the designated bandwidth guarantee counter, a request is issued to the determinant until the bandwidth guarantee counter becomes 0 even if the queue is empty. In this case, even if there is a response to the request, nothing is output because the queue is empty.
2. In rt-VBR, a bandwidth can be additionally acquired even if the designated bandwidth guarantee counter runs out of bandwidth. Therefore, even if the bandwidth guarantee counter is 0, if the queue is not empty, a request is issued to the determinant.
3. In nrt-VBR, a plurality of bandwidth reservation information is used so that the number of additional requests can be limited in addition to the rt-VBR method. First, the bandwidth guarantee counter is reset with the minimum bandwidth guarantee value, and when the counter becomes 0, the maximum bandwidth guarantee counter 902 is reset with the maximum bandwidth obtainable value. When it becomes 0 again, no request is made to the determinant. Alternatively, the bandwidth guarantee counter is reset with the minimum bandwidth guarantee value, and the maximum bandwidth guarantee counter 902 is reset with the maximum bandwidth obtainable value, and both counters are simultaneously reduced.
4. Since UBR is insensitive to delay and bandwidth, it is realized by issuing a request to a determinant when another counter is 0, or resetting the bandwidth guaranteed counter 901 according to a bandwidth guaranteed value fixed to UBR.
5. UBR + defines an average speed. First, the bandwidth guarantee counter 901 is reset with the average bandwidth guarantee value. If the queue is not empty even after the bandwidth guarantee counter becomes 0, a request is additionally issued to the determinant, and if the request passes, another average bandwidth guarantee counter is reduced. Otherwise, the average bandwidth guarantee counter is increased. In method C, a unique counter for managing the entire cycle, and method S, the bandwidth guaranteed counter is reset again with the average bandwidth guaranteed value when the cyclic buffer makes one round. At this time, the value of the average bandwidth guaranteed counter must be added. To protect the average band.
As described above, by operating a plurality of band guarantee values and counters, various service categories are supported.
If the bandwidth guarantee counter is not yet 0 even if the total bandwidth counter becomes 0, the user selects whether to discard or smooth the corresponding request in the queue. This selection means includes a method for explicitly indicating whether the header can be discarded, a method according to the information of the upper layer, a method directly specified by the administrator, a method specified by the corresponding bandwidth guarantee service class, a method specified by the upper layer. In the case where the IP is used, there is a method of specifying each TCP / UDP.
At the same time as ensuring these bandwidths, real-time security is guaranteed. The difference between the current time clock 1002 and the designated arrival time 702 is obtained by the grace time calculator 1003 as needed. The time information is converted into a reference time such as GMT and used, or a local time provided with locale information is used. At this time, if the granularity of the designated arrival time and the grace time is too fine, the amount of information increases, and if the granularity is too rough, fine management cannot be performed. Adjust to the frame speed).
Arbitration is performed based on the value of the bandwidth security counter 901, the value of the maximum bandwidth security counter 902, and the value of the grace time calculator 1003 collected from the above inputs.
In the method C, the request selector control circuit is operated in accordance with the method c in the first embodiment based on the value of the bandwidth guarantee counter 901, the presence / absence (VALID) of the request issued from the value of the maximum bandwidth guarantee counter 902, and the grace time. This method has a very simple structure, and can be easily reduced in size and speed.
In the system S, the scheduler setting unit 1004 sets the cyclic buffer 904 based on the value of the bandwidth guarantee counter 901, the value of the maximum bandwidth guarantee counter 902, and the value of the grace time calculator 1003. If the arbiter of the present invention is used again for this setting, an arbitration result similar to the method S will be obtained. Further, the flexibility is increased by determining the value of the cyclic buffer by another method. For example, there are a method of random extraction using random numbers, a method of controlling by a program, and the like. However, the scale and delay may increase depending on the system.
A hybrid configuration of scheme C and scheme S is also possible. For example, it is possible to use the method S for bandwidth guarantee and the method C for real time security.
[0030]
Example 6
An example in which an arbiter is provided for each priority as a configuration of an arbiter or an exchange arbiter that performs more faithful priority processing will be described.
FIG. 11 shows a configuration for preparing a plurality of arbiters. The packet is input to an arbiter 1101 prepared for each priority. The output of the arbiter is further weighted for each priority by the priority selector 1102 and is selected as a final output. The arbiter of the present invention is applied to this priority selector. When a plurality of arbiters are prepared and the logic circuit scale becomes large and mounting becomes difficult, arbiters are used in a time-division manner for each priority.
According to the present invention, it is possible to realize the reservation and guarantee of the bandwidth with a fine granularity such as for each packet or request, and the guarantee of the real-time property with a small logic circuit scale and low delay. Can effectively utilize the network and can cope with various services.
[0031]
Example 7
An example in which adaptive routing is performed based on information used for flow control will be described.
If the router according to the present invention controls the flow rate of only the input buffer, it is possible to delay the packets that are not desirably discarded without discarding them. In addition, adaptive routing can be performed based on information obtained by the flow rate management. The router according to the present invention can guarantee a band even when adaptive routing is performed, and is suitable for adaptive routing using flow control.
Back pressure or credit based flow control used as a flow control means is used. By analyzing the credit (information on the free buffer capacity of the partner switch) or the handshake frequency in the back pressure, the congestion degree of the partner switch can be known. Utilizing this result, adaptive routing or priority order for avoiding hot spots is determined.
If a certain packet can select a plurality of outputs A and B, and if the number of credits of the output A is larger than the number of credits of the output B, the output A can be expected to be less congested. I do. When using back pressure, the latest transfer stop time is measured. It can be expected that the longer the transfer stop time, the more crowded.
Further, the information used for the flow rate control can be used as a material for determining a determinant in the sixth embodiment. Normally, if the bandwidth limitation information is set correctly and communication is normally performed, the starvation of a packet whose starvation is to be avoided can be avoided. However, when the setting is erroneous or when a substantial bandwidth shortage occurs due to a detour of another line due to a line failure, congestion due to congestion occurs and the bandwidth cannot be guaranteed. In this case, it is desirable to uniformly reduce the allocated bandwidth for the entire packet whose bandwidth is to be guaranteed. Knowing the congestion state based on the information used for the flow rate control makes it possible to uniformly reduce the guaranteed value of the packet bandwidth according to the congestion state.
[0032]
【The invention's effect】
According to the present invention, a fair arbiter with a small circuit size and low delay can be constructed. By applying the present invention to a router, a small-scale, large-capacity, low-delay, low-cost, bandwidth and real-time A router that guarantees is feasible.
The arbiter according to the present invention not only has a simple structure, but also can construct a switch having the same capability as a crossbar by directly inputting a packet to the arbiter.
In addition, since the arbiter itself guarantees the bandwidth and real-time performance, a circuit called a shaper and a large-capacity output buffer associated with the output buffer are not required. Bandwidth and real-time performance are guaranteed by the way packets are extracted from the input buffer and how they pass through the arbiter. Delay. By determining the priority and controlling the flow rate using the information on the flow rate control, congestion and congestion can be avoided, and the load on the entire network can be balanced.
In the future network society, the bandwidth and quality of each application in large-capacity traffic such as streams are required.
[Brief description of the drawings]
FIG. 1 is a block diagram showing, as an example of an arbiter configuration according to the present invention, a configuration in which priority is assigned to eight arbiter inputs most evenly.
FIG. 2 is a block diagram showing a configuration example of each request selector included in an arbiter according to the present invention.
FIG. 3 is a block diagram illustrating an example of a request selector control circuit included in the request selector.
FIG. 4 is a table showing priority order assignment of each order when the arbiter according to the present invention is configured so that the priority order is distributed most equally by eight arbiter inputs.
FIG. 5 is a block diagram showing an example of a case where the arbiter according to the present invention is configured so that priority order distribution is performed most evenly with ten arbiter inputs.
FIG. 6 is a block diagram showing an example of an arbiter that can assign unequal priorities to each arbiter input;
FIG. 7 is a format diagram showing an example of a packet format used in a router according to the present invention.
FIG. 8 is a block diagram showing a configuration example of a router according to the present invention.
FIG. 9 is a block diagram showing an example of a structure for supporting a band and real-time property of an arbiter included in a router according to the present invention.
FIG. 10 is a block diagram showing an example of a structure corresponding to various service classes by a priority determination scheduler in which a priority determination counter is extended to support a band and real-time property.
FIG. 11 is a block diagram showing an example in which a different arbiter is applied for each priority in the router according to the present invention.
FIG. 12 is a block diagram illustrating a configuration example of a conventional router that performs bandwidth and real-time processing.
FIG. 13 is a block diagram showing a configuration example of a conventional queue-based arbiter.
FIG. 14 is a block diagram showing a configuration example of a conventional round robin arbiter.
FIG. 15 is a table showing priority order assignment of each order in a conventional round robin arbiter in a case where priority order distribution is performed most evenly with eight arbiter inputs.
[Explanation of symbols]
101 Arbiter input
102 Request selector
103 Priority determination counter
104 Priority decision signal
105 Selection output
201 Request input A
202 Request input B
203 Enter ID
204 Input of VAOID
205 Request selector control circuit
801 Input buffer used in router in the present invention
802 exchange arbiter
901 Bandwidth guarantee counter
902 Maximum bandwidth guarantee counter
903 priority decision scheduler
1001 cyclic buffer
1101 Switching arbiter provided for each priority
1102 Priority selector
1201 Conventional input buffer
1202 Conventional arbiter
1203 Crossbar
1204 Output buffer
1205 Shaper
1301 Request distributor
1302 Request queue
1303 Selector
1401 An example of a fixed priority arbiter.

Claims (13)

An arbiter with a wooden structure,
An arbiter input at a leaf of the tree structure;
A request selector on a branch of the tree structure;
And a controller for determining a priority order associated with the tree structure,
An arbiter for controlling the request selector according to the controller to change which of the arbiter inputs is output. The arbiter is at least one of a priority determination counter and a priority determination scheduler. 3. The arbiter according to claim 2, wherein said priority order determination counter equally assigns priority of arbiter inputs in a round robin manner. 3. The arbiter according to claim 2, wherein the priority determination scheduler assigns the priority of the arbiter input based on the guaranteed bandwidth of the arbiter input. An arbiter for arbitrating multiple requests,
One or more request selectors;
Control means for determining priorities;
n (where n is a power of 2) arbiter inputs;
When the number of stages of the request selector is t, 2 to the power of t is the number of arbiter inputs n,
For a natural number r of 1 or more and t or less, the number s (r) of the request selectors in the r-th stage has a structure in which n is divided by 2 to the power of r,
The n arbiter inputs are respectively (0, 1), (0, 2), ‥‥, (0, n), and the rth request selector is (r, 1), (r, 2), ‥‥, (r, s (r)),
The r-th stage request selector (r, c) receives two outputs, (r-1, 2c-1) and (r-1, 2c), which are r-1 stage request selectors or arbiter inputs. , Based on the output of the r-th bit of the counter or scheduler for determining the priority, makes a selection of the two inputs of the request selector with the priority resolved,
Arbiter arbitration is performed by taking into account the priority order and arbitrating the arbiter input by using a structure in which the result is output to the input of the request selector (r + 1, p) at the (r + 1) th stage, where p is a round-up obtained by dividing c by 2. . An arbiter that mediates multiple requests,
One or more request selectors;
A counter or scheduler for determining priority,
If n is the number that is not a power of 2 and is not a power of 2, and n is the largest natural number t that does not exceed n out of 2 to the power of t, the number of stages of the request selector is t + 1. ,
For a natural number r from 1 to t, the number s (r) of the request selectors in the r-th stage is a value obtained by dividing n by 2 to the power of r.
The number s (r + 1) of the request selectors at the (t + 1) th stage has a structure obtained by subtracting 2 to the power of r from n,
The request selectors up to the t-th stage are the same combination as in claim 1,
The request selector at the (t + 1) th stage connects the output of the request selector to one or both inputs of the request selector at the tth stage,
The request selector (r, c) at the r-th stage determines which input has priority according to the signal output from the bit r of the counter or the scheduler that determines the priority and determines the arbiter input in consideration of the priority. An arbiter characterized by arbitration. An arbiter with a binary tree structure,
An arbiter input at a leaf of the tree structure;
A request selector on a branch of the tree structure;
A counter or scheduler having a bit width equal to or greater than the maximum number of stages of the tree structure and outputting a priority determination signal,
The priority order determination signal has a structure commonly connected to request selectors in the same number of stages,
An arbiter which arbitrates arbiter inputs in consideration of priority according to the output of the counter or the scheduler. Information indicating whether each request selector accepts the request as valid or invalid;
Information indicating the priority order that the request selector accepts as a request;
The arbiter input is arbitrated in consideration of the priority by one of a counter for determining the priority or a signal output by the scheduler, or a combination thereof. Arbiter as described. The arbiter according to any one of claims 1 to 7, wherein the arbiter receives packets and data together with the request, and can exchange packets with the entire arbiter. An arbiter according to claim 9,
One or more counters related to bandwidth guarantee are provided in the arbiter input unit,
A router characterized by setting a counter or a scheduler that determines a priority order for guaranteeing bandwidth and real-time performance based on the value of the counter. A plurality of arbiters according to claim 9 are provided for each priority,
One or more counters related to bandwidth guarantee are provided in the arbiter input unit,
By setting a counter or scheduler that determines the priority according to the value of the counter, the output is determined for each priority,
7. A router for determining an output determined for each of the priorities using one of the arbiter shown in claim 5 and the arbiter structure shown in claim 6. A router and switch construction method in IP, ATM, etc.,
A router that performs adaptive routing and priority determination for guaranteeing bandwidth and real-time performance based on flow control information in an input buffer. A router and switch construction method in IP, ATM, etc.,
It has the structure of the router which combined at least one of Claim 10 and Claim 11,
Adaptive routing based on flow control information in the input buffer,
A router for performing control of a counter or a scheduler for determining a priority order for guaranteeing a bandwidth or real-time performance based on the information, or a combination thereof.

Images