(57)【特許請求の範囲】
【請求項１】
出力セルを蓄積する複数のキューと、前記複数のキュー各々に順番に出力セルを出力する権利を与える複数の第１のラウンドロビンと、前記複数の第１のラウンドロビン各々に順番に出力セルを出力する権利を与える第２のラウンドロビンと、前記第１及び第２のラウンドロビン各々への入力レートが等しくなるように調整する機構とを有し、前記第１及び第２のラウンドロビンにより多段構成とし、前記第１及び第２のラウンドロビン各々へのトラフィックの平均化を行うよう構成したことを特徴とするアービタ回路。
【請求項２】
前記第１のラウンドロビン各々は、該当するキューにセルが蓄積されていない時には次のキューへ権利を移すよう構成したことを特徴とする請求項１記載のアービタ回路。
【請求項３】
前記第１及び第２のラウンドロビン各々は、配下のキュー及び配下のラウンドロビンから自回路へと入力される予定のセルレートの情報を持つよう構成したことを特徴とする請求項１または請求項２記載のアービタ回路。
【請求項４】
前記第２のラウンドロビンは、配下のラウンドロビンの中で最も入力レートが低いラウンドロビン及び２番目にレートが低いラウンドロビンの情報を持つよう構成したことを特徴とする請求項３記載のアービタ回路。
【請求項５】
前記第１及び第２のラウンドロビン各々が持つ情報はコネクションを張る際に申請される情報を基に作成するよう構成したことを特徴とする請求項３または請求項４記載のアービタ回路。
【請求項６】
前記コネクションが新たに張られる場合に、配下のラウンドロビンの中でもっとも低い入力レートのラウンドロビンを順次選択し、最終段のラウンドロビンの配下にキューを配置するよう構成したことを特徴とする請求項５記載のアービタ回路。
【請求項７】
出力セルを蓄積する複数のキュー各々に順番に出力セルを出力する権利を与える複数の第１のラウンドロビンと、前記複数の第１のラウンドロビン各々に順番に出力セルを出力する権利を与える第２のラウンドロビンとにより多段構成とし、前記第１及び第２のラウンドロビン各々への入力レートが等しくなるように調整して前記第１及び第２のラウンドロビン各々へのトラフィックの平均化を行うようにしたことを特徴とするアービトレーション方法。
【請求項８】
前記第１のラウンドロビン各々は、該当するキューにセルが蓄積されていない時には次のキューへ権利を移すようにしたことを特徴とする請求項７記載のアービトレーション方法。
【請求項９】
前記第１及び第２のラウンドロビン各々は、配下のキュー及び配下のラウンドロビンから自回路へと入力される予定のセルレートの情報を持つようにしたことを特徴とする請求項７または請求項８記載のアービトレーション方法。
【請求項１０】
前記第２のラウンドロビンは、配下のラウンドロビンの中で最も入力レートが低いラウンドロビン及び２番目にレートが低いラウンドロビンの情報を持つようにしたことを特徴とする請求項９記載のアービトレーション方法。
【請求項１１】
前記第１及び第２のラウンドロビン各々が持つ情報はコネクションを張る際に申請される情報を基に作成するようにしたことを特徴とする請求項９または請求項１０記載のアービトレーション方法。
【請求項１２】
前記コネクションが新たに張られる場合に、配下のラウンドロビンの中でもっとも低い入力レートのラウンドロビンを順次選択し、最終段のラウンドロビンの配下にキューを配置するようにしたことを特徴とする請求項１１記載のアービトレーション方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はアービタ回路及びそれに用いる出力セルのアービトレーション方法に関し、特にＡＴＭ（Ａｓｙｎｃｈｏｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ：非同期転送モード）交換機における各ＶＣ（Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌ）毎のキューイングに関する。
【０００２】
【従来の技術】
従来、ＡＴＭ交換機においては、よりきめ細かなトラフィックコントロールを実現するために、各ＶＣ毎にセルを個別のキュー（Ｑｕｅｕｅ）に蓄積する「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」という方法が採られている。
【０００３】
この「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」という方法はＡＴＭ交換機にＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）を実装した際のＶＣマージ等にも用いられている。
【０００４】
上記のＡＴＭ交換機におけるＶＣ毎のキューイングについては、特開平１０−２２４３６４号公報、特開平１１−１９１７７４号公報、特許第２７９７９８９号公報等に開示されている。
【０００５】
【発明が解決しようとする課題】
しかしながら、「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」という方法を用いることによって、ＶＣ毎のトラフィックコントロールが可能になるが、その反面、キューが膨大な数（数万個）になる可能性がある。
【０００６】
そのため、出力でのアービトレーションの処理時間が長くなり、一定時間内に処理が終了しないという問題が発生する。よって、その問題を解決するためのアービトレーションの方法が必要となる。
【０００７】
そこで、本発明の目的は上記の問題点を解消し、比較的簡素な構成で、キューが膨大な数になっても平等なアービトレーションを行うことができるアービタ回路及びそれに用いる出力セルのアービトレーション方法を提供することにある。
【０００８】
【課題を解決するための手段】
本発明によるアービタ回路は、出力セルを蓄積する複数のキューと、前記複数のキュー各々に順番に出力セルを出力する権利を与える複数の第１のラウンドロビンと、前記複数の第１のラウンドロビン各々に順番に出力セルを出力する権利を与える第２のラウンドロビンと、前記第１及び第２のラウンドロビン各々への入力レートが等しくなるように調整する機構とを有し、前記第１及び第２のラウンドロビンにより多段構成とし、前記第１及び第２のラウンドロビン各々へのトラフィックの平均化を行うよう構成している。
【０００９】
本発明による出力セルのアービトレーション方法は、出力セルを蓄積する複数のキュー各々に順番に出力セルを出力する権利を与える複数の第１のラウンドロビンと、前記複数の第１のラウンドロビン各々に順番に出力セルを出力する権利を与える第２のラウンドロビンとにより多段構成とし、前記第１及び第２のラウンドロビン各々への入力レートが等しくなるように調整して前記第１及び第２のラウンドロビン各々へのトラフィックの平均化を行うようにしている。
【００１０】
すなわち、本発明の出力セルのアービトレーション方法は、「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」を行うＡＴＭ交換機において、出力セルのアービトレーションを行う方法に関するものである。
【００１１】
アービトレーションは、（ａ）異なるサービスクラス間で固定的（静的）に優先度を決める方法と、（ｂ）同一サービスクラス内で平等に出力させる方法とに分けられる。本発明は（ｂ）の同一サービスクラス内のアービトレーションにおいて、キューの数が多くなった場合の各キュー間の平等性の確保を、入出力を含めたシステム全体での閉ループを使用せずに簡素な方法で実現可能としたことを特徴とする。
【００１２】
（ａ）のアービトレーションにおける異なるサービスクラス間の優先度は固定的であり、高優先のセルがキューに蓄積されている間、低優先のセルが出力されることはない。これによって、高優先のセルの遅延特性を確保することを可能としている。
【００１３】
（ｂ）の同一サービスクラス内でのアービトレーションでは全キューについて平等であることが求められる。通常、ラウンドロビン（ＲＲ：Ｒｏｕｎｄ  Ｒｏｂｉｎ）を用いることによって、各キューに順番にセルを出力する権利を与えることを可能とし、さらに該当するキューにセルが蓄積されていない時には次のキューへ権利を移すことが可能となる。但し、「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」を行う場合には、同一サービスクラスのキューの数が数万個になる可能性があり、処理時間が追いつかないという問題が生じる。
【００１４】
ラウンドロビンの代わりに、Ｔｉｍｅ  Ｗｈｅｅｌを用いて動的に帯域を制御することができればこの問題を解決することができるが、この場合には入力側を含んだシステム全体での複雑な閉ループ制御が必要となる。
【００１５】
そこで、本発明のアービトレーション方法では、ラウンドロビンを多段構成とし、各ラウンドロビンへの入力の本数を必要な時間内に十分処理可能な数にしている。これによって、各ラウンドロビンへ入力するキューについて平等にセル出力の権利が与えられる。但し、これは通常時のことであり、輻輳時には各キュー間の平等性が失われる恐れがある。
【００１６】
例えば、第１のラウンドロビンに比較的入力セルレートの高いキューが集中し、第２のラウンドロビンに入力セルレートの高いキューが１つとその他のレートの極小さなキューからのセルが入力される場合を考える。輻輳によって入力レートの合計が出力レートを超過してしまう場合には、入力レートが同じであるにも関わらず、第２のラウンドロビンのキューの出力レートは第１のラウンドロビンのキューよりも高くなり、キュー間の出力の平等性が崩れてしまうことになる。
【００１７】
このような問題を回避するために、本発明のアービトレーション方法では、各ラウンドロビンへの入力レートが等しくなるように調整する機構を持つ。各ラウンドロビンは配下のキューまたはラウンドロビンから自回路へと入力される予定のセルレートの情報を持つ。さらに、配下がラウンドロビンの場合には、配下のラウンドロビンの中で最も入力レートが低いラウンドロビン及び２番目にレートが低いラウンドロビンの情報を持つ。これらの情報はコネクションを張る際に申請される情報を基に作成される。
【００１８】
コネクションが新たに張られる場合には、最上位のラウンドロビンの情報から配下のラウンドロビンの中で最も低い入力レートのラウンドロビンを選択する。選ばれたラウンドロビンの持つ情報からさらに配下のラウンドロビンの中で最も低いレートのラウンドロビンを選択する。このように最終段まで繰り返し、その配下にキューを配置することによって、各ラウンドロビンにおいて入力されるセルレートができるだけ等しくなるように、キューが配置される。
【００１９】
各キューの出力の平等性をさらに増すためには、新たなコネクションが追加されるか、もしくは削除される度に全てのキューのレートを計算して各ラウンドロビンへ再分配する必要があるが、システムの簡単化のため、本発明のシステムでは行わない。
【００２０】
上記のように、多段のラウンドロビンと各ラウンドロビンへのトラフィックの平均化を行うことによって、「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」によってキューが膨大な数になっても平等なアービトレーションを行うことが可能となる。また、トラフィックを平均化することによって、輻輳時にも上記の効果が得られる。さらに、装置全体の閉ループ制御とＴｉｍｅ  Ｗｈｅｅｌとの組合せを用いることなく、比較的簡素な構成で上記の効果が得られる。
【００２１】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。図１は本発明の実施の形態によるアービタ回路の構成を示すブロック図である。図１において、本発明の実施の形態によるアービタ回路はラウンドロビン（ＲＲ：Ｒｏｕｎｄ  Ｒｏｂｉｎ）１，２−１〜２−ｋを多段構成にし、各ラウンドロビン１，２−１〜２−ｋへの入力本数を、必要な時間内に十分処理することができる数にしている。
【００２２】
すなわち、ラウンドロビン１の配下にはラウンドロビン２−１〜２−ｋが配置され、各ラウンドロビン２−１〜２−ｋの配下にはキュー（Ｑｕｅｕｅ）４１−１〜４１−ｋ，４２−１〜４２−ｋ，……，４ｌ−１〜４ｌ−ｋが配置されている。
【００２３】
これによって、各ラウンドロビン２−１〜２−ｋへ入力するキュー４１−１〜４１−ｋ，４２−１〜４２−ｋ，……，４ｌ−１〜４ｌ−ｋについて平等にセル出力の権利が与えられる。但し、これは通常時のことであり、輻輳時には各キュー４１−１〜４１−ｋ，４２−１〜４２−ｋ，……，４ｌ−１〜４ｌ−ｋ間の平等性が失われる恐れがある。
【００２４】
図２は本発明の実施の形態によるアービタ回路で一時的に輻輳した時の問題点を示す図である。図２に示すように、ラウンドロビン２−１に比較的入力セルレートの高いキュー４１−１〜４１−３が集中し、ラウンドロビン２−２には入力セルレートの高いキュー４２−１が１つ（キュー４１−１〜４１−３と同じレート）とその他のレートの極小さなキュー４２−２，４２−３からのセルが入力される場合を考える。
【００２５】
輻輳によって入力レートの合計が出力レートを超過してしまう場合には、入力レートが同じであるにも関わらず、キュー４２−１の出力レートはキュー４１−１〜４１−３よりも高くなり、キュー４２−１〜４２−３間の出力の平等性が崩れてしまう。
【００２６】
このような問題を回避するために、本発明の実施の形態によるアービタ回路は各ラウンドロビン１，２−１，２−２への入力レートが等しくなるように調整する機構を持つ。各ラウンドロビン１，２−１，２−２は配下のキュー４１−１〜４１−３，４２−１〜４２−３またはラウンドロビン２−１，２−２から自回路へと入力される予定のセルレートの情報を持つ。
【００２７】
さらに、配下がラウンドロビン２−１，２−２の場合には、配下のラウンドロビン２−１，２−２の中で最も入力レートが低いラウンドロビン及び２番目にレートが低いラウンドロビンの情報を持つ。これらの情報はコネクションを張る際に申請される情報を基に作成される。
【００２８】
コネクションが新たに張られる場合には、最上位のラウンドロビンの情報から配下のラウンドロビンの中で最も低い入力レートのラウンドロビンを選択する。選ばれたラウンドロビンの持つ情報からさらに配下のラウンドロビンの中で最も低いレートのラウンドロビンを選択する。
【００２９】
このように、ラウンドロビンの選択を最終段まで繰り返し、その配下にキューを配置することによって、各ラウンドロビンにおいて入力されるセルレートができるだけ等しくなるように、キューが配置される。
【００３０】
各キューの出力の平等性をさらに増すためには、新たなコネクションが追加されるか、もしくは削除される度に全てのキューのレートを計算して各ラウンドロビンへ再分配する必要があるが、システムの簡単化のため、本発明のシステムでは行わない。
【００３１】
図３は本発明の一実施例によるアービタ回路の構成を示すブロック図であり、図４は図３の各ラウンドロビンが持つ情報を示す図であり、図５は図３の各ラウンドロビンが持つコネクション追加後の情報を示す図であり、図６は図３の各ラウンドロビンが持つコネクション削除後の情報を示す図である。
【００３２】
また、図７及び図８は本発明の一実施例によるアービタ回路におけるコネクション追加または削除後の情報の更新処理を示すフローチャートである。これら図３〜図８を参照して本発明の一実施例によるアービタ回路の構成及び動作について説明する。
【００３３】
以下の説明では簡単化のためにラウンドロビンの多段構成を３段構成とし、ラウンドロビン１を最上位のラウンドロビンする。また、ラウンドロビン１の配下にはそれぞれラウンドロビン２−１〜２−４があり、ラウンドロビン２−１の配下にラウンドロビン３−１〜３−３がある。尚、ラウンドロビン２−２〜２−４の配下のラウンドロビンについては省略する。
【００３４】
一方、ラウンドロビン３−１〜３−３の配下にはＶＣ（Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌ）毎のセルを蓄積するキューがあり、各ＶＣのセルレートはそれぞれ図３に示す通りである。すなわち、キュー４１−１〜４１−３のレートはそれぞれ２Ｍｂｐｓ、４Ｍｂｐｓ、６Ｍｂｐｓであるので、ラウンドロビン３−１のレートは１２Ｍｂｐｓである。
【００３５】
また、キュー４２−１〜４２−３のレートはそれぞれ２０Ｍｂｐｓ、１１Ｍｂｐｓ、８Ｍｂｐｓであるので、ラウンドロビン３−２のレートは３９Ｍｂｐｓであり、キュー４３−１〜４３−３のレートはそれぞれ１４Ｍｂｐｓ、７Ｍｂｐｓ、６Ｍｂｐｓであるので、ラウンドロビン３−３のレートは２７Ｍｂｐｓである。
【００３６】
各ラウンドロビン１，２−１〜２−４，３−１〜３−３は、図４に示すように、入力セルレートと配下の最低レートのラウンドロビンと配下で２番目にレートの低いラウンドロビンとからなる情報を持つ。
【００３７】
次に、図３〜図８を参照して、本発明の一実施例によるアービタ回路におけるコネクション追加または削除後の動作及び各ラウンドロビン１，２−１〜２−４，３−１〜３−３の情報の更新について説明する。
【００３８】
新たにレート５Ｍｂｐｓのコネクションを追加する場合（図７ステップＳ１）、最上位のラウンドロビン１の配下で最低レートのラウンドロビンを探索する（図７ステップＳ２）。この探索で配下のラウンドロビンがあるかどうかが判定される（図７ステップＳ３）。配下のラウンドロビンがあればステップＳ４に移行し、配下のラウンドロビンがなければ、ステップＳ６に移行する。
【００３９】
この場合、図４に示すように、ラウンドロビン２−１が探索され、その配下のラウンドロビン３−１〜３−３があるので、ラウンドロビン２−１の配下で最低レートのラウンドロビンを探索する（図７ステップＳ４）。この探索で配下のラウンドロビンがあるかどうかが判定される（図７ステップＳ５）。配下のラウンドロビンがあればステップＳ４に移行し、配下のラウンドロビンがなければ、ステップＳ６に移行する。
【００４０】
この場合、図４に示すように、ラウンドロビン３−１が探索されるが、その配下のラウンドロビンがないので、ラウンドロビン３−１の配下にキュー４１−４を追加し、新しいコネクションのセルを蓄積できるようにする（図７ステップＳ６）。
【００４１】
キュー４１−４の追加後、ラウンドロビン３−１の情報を更新する（図７ステップＳ７）。その際、ラウンドロビン３−１の情報は現在のセルレート１２Ｍｂｐｓに、新たに追加された５Ｍｂｐｓを加算して１７Ｍｂｐｓとなる（図５参照）。
【００４２】
続いて、ラウンドロビン３−１の直近上位のラウンドロビン２−１の情報を更新する（図７ステップＳ８）。その際、ラウンドロビン２−１の配下で２番目に低いレートのラウンドロビン３−３のセルレート２７ＭｂｐｓとステップＳ６で更新された情報とを比較してから情報の更新が行われる。
【００４３】
その結果、ラウンドロビン３−１（１７Ｍｂｐｓに更新）の方がラウンドロビン３−３（２７Ｍｂｐｓ）より小さいので、ラウンドロビン２−１の情報において最低レートのラウンドロビン及び２番目に低いレートのラウンドロビンは変化しない。また、ラウンドロビン２−１の情報においては現在のセルレート７８Ｍｂｐｓに追加された５Ｍｂｐｓを加算して８３Ｍｂｐｓとなる（図５参照）。
【００４４】
この後、情報が更新されたラウンドロビンの直近上位のラウンドロビンが最上位のラウンドロビンかどうかが判定される（図７ステップＳ９）。最上位のラウンドロビンでなければステップＳ８に戻り、最上位のラウンドロビンであればステップＳ１０に移行する。
【００４５】
この場合、情報が更新されたラウンドロビン２−１の直近上位のラウンドロビン１が最上位のラウンドロビンであるので、ラウンドロビン１の情報を更新する（図７ステップＳ１０）。その際、ラウンドロビン１の配下で２番目に低いレートのラウンドロビン２−４のセルレート８０ＭｂｐｓとステップＳ８で更新された情報とを比較してから情報の更新が行われる。
【００４６】
その結果、ラウンドロビン２−１（８３Ｍｂｐｓに更新）の方がラウンドロビン２−４（８０Ｍｂｐｓ）より大きくなったため、ラウンドロビン１配下の全ラウンドロビン２−１〜２−４の情報を参照し、最低レートのラウンドロビンをラウンドロビン２−４に、２番目に低いレートのラウンドロビンをラウンドロビン２−１に更新する。また、ラウンドロビン１の情報においては現在のセルレート４２５Ｍｂｐｓに追加された５Ｍｂｐｓを加算し、４３０Ｍｂｐｓに更新する。上記のような新しいコネクションの追加が終わった後の各ラウンドロビン１，２−１〜２−４，３−１〜３−３の情報を図５に示す。
【００４７】
次に、キュー４２−１のコネクションを削除する場合（図７ステップＳ１）、削除したキューにつながるラウンドロビン３−２の情報を更新する（図８ステップＳ１１）。ラウンドロビン３−２の情報においては現在のセルレート３９Ｍｂｐｓからキュー４２−１のレート２０Ｍｂｐｓを減算し、１９Ｍｂｐｓに更新される。
【００４８】
続いて、ラウンドロビン３−２につながる直近上位のラウンドロビン２−１の情報を更新する（図８ステップＳ１２）。その際、ラウンドロビン２−１の配下で最低レートのラウンドロビン３−１のレート１２ＭｂｐｓとステップＳ１１で更新されたレートとを比較してから情報の更新が行われる。
【００４９】
その結果、ラウンドロビン３−２（１９Ｍｂｐｓに更新）よりもラウンドロビン３−１（１２Ｍｂｐｓ）の方が小さいため、ラウンドロビン２−１の情報における最低レートのラウンドロビンは変化しない。
【００５０】
また、ラウンドロビン２−１の配下で２番目にレートの低いラウンドロビン３−３のレート２７ＭｂｐｓとステップＳ１１で更新されたレートとを比較すると、ラウンドロビン３−２（１９Ｍｂｐｓに更新）の方がラウンドロビン３−３（２７Ｍｂｐｓ）より小さくなったため、２番目にレートの低いラウンドロビンはラウンドロビン３−２に更新される。さらに、ラウンドロビン２−１の情報においては、現在のセルレート７８Ｍｂｐｓからキュー４２−１の２０Ｍｂｐｓを減算し、５８Ｍｂｐｓに更新される。
【００５１】
この後、情報が更新されたラウンドロビンの直近上位のラウンドロビンが最上位のラウンドロビンかどうかが判定される（図８ステップＳ１３）。最上位のラウンドロビンでなければステップＳ１２に戻り、最上位のラウンドロビンであればステップＳ１４に移行する。
【００５２】
この場合、情報が更新されたラウンドロビン２−１の直近上位のラウンドロビン１が最上位のラウンドロビンであるので、ラウンドロビン１の情報を更新する（図８ステップＳ１４）。その際、ラウンドロビン１の配下で最低レートのラウンドロビンがラウンドロビン２−１であるため（図４参照）、情報の更新は行われない。また、ラウンドロビン１の情報においては、現在のセルレート４２５Ｍｂｐｓから削除された２０Ｍｂｐｓを減算し、４０５Ｍｂｐｓに更新される。錠のようなコネクションの削除が終了した後の各ラウンドロビン１，２−１〜２−４，３−１〜３−３の情報を図６に示す。
【００５３】
以上の手順によってコネクションの追加または削除が行われる。この方法によって、比較的簡素な方法で各ラウンドロビン１，２−１〜２−４，３−１〜３−３のトラフィックの平均化を行うことができ、「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」でキューの数が増えても平等なアービトレーションを行うことができる。
【００５４】
このように、多段のラウンドロビンと各ラウンドロビンへのトラフィックの平均化を行うことによって、「Ｐｅｒ  ＶＣ  Ｑｕｅｕｉｎｇ」でキューが膨大な数になっても平等なアービトレーションが行うことができる。
【００５５】
また、各ラウンドロビン１，２−１〜２−４，３−１〜３−３のトラフィックを平均化することによって、輻輳時にも上記の効果が得られる。さらに、装置全体の閉ループ制御とＴｉｍｅ  Ｗｈｅｅｌとの組合せを用いることなく、比較的簡素な構成で、上記の効果を得られる。
【００５６】
【発明の効果】
以上説明したように本発明によれば、出力セルを蓄積するキューと、キュー各々に順番に出力セルを出力する権利を与えるラウンドロビンとを含むアービタ回路において、ラウンドロビンを多段構成とし、ラウンドロビン各々への入力本数を必要な時間内に十分処理可能な数としてラウンドロビン各々へのトラフィックの平均化を行うことによって、比較的簡素な構成で、キューが膨大な数になっても平等なアービトレーションを行うことができるという効果がある。
【図面の簡単な説明】
【図１】本発明の実施の形態によるアービタ回路の構成を示すブロック図である。
【図２】本発明の実施の形態によるアービタ回路で一時的に輻輳した時の問題点を示す図である。
【図３】本発明の一実施例によるアービタ回路の構成を示すブロック図である。
【図４】図３の各ラウンドロビンが持つ情報を示す図である。
【図５】図３の各ラウンドロビンが持つコネクション追加後の情報を示す図である。
【図６】図３の各ラウンドロビンが持つコネクション削除後の情報を示す図である。
【図７】本発明の一実施例によるアービタ回路におけるコネクション追加または削除後の情報の更新処理を示すフローチャートである。
【図８】本発明の一実施例によるアービタ回路におけるコネクション追加または削除後の情報の更新処理を示すフローチャートである。
【符号の説明】
１，２−１〜２−ｋ，３−１〜３−３  ラウンドロビン
４１−１〜４１−ｋ，４２−１〜４２−ｋ，
４ｌ−１〜４ｌ−ｋ  キュー
【図１】
0003570366.tif 000002
【図２】
0003570366.tif 000003
【図３】
0003570366.tif 000004
【図４】
0003570366.tif 000005
【図５】
0003570366.tif 000006
【図６】
0003570366.tif 000007
【図７】
0003570366.tif 000008
【図８】
0003570366.tif 000009