JP2002094522A - アービタ回路及びそれに用いる出力セルのアービトレーション方法 - Google Patents
アービタ回路及びそれに用いる出力セルのアービトレーション方法Info
- Publication number
- JP2002094522A JP2002094522A JP2000277412A JP2000277412A JP2002094522A JP 2002094522 A JP2002094522 A JP 2002094522A JP 2000277412 A JP2000277412 A JP 2000277412A JP 2000277412 A JP2000277412 A JP 2000277412A JP 2002094522 A JP2002094522 A JP 2002094522A
- Authority
- JP
- Japan
- Prior art keywords
- round robin
- round
- robins
- queue
- information
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5679—Arbitration or scheduling
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】
【課題】 比較的簡素な構成で、キューが膨大な数にな
っても平等なアービトレーションを行うことが可能なア
ービタ回路を提供する。 【解決手段】 ラウンドロビン１の配下にラウンドロビ
ン２−１〜２−ｋが配置し、各ラウンドロビン２−１〜
２−ｋの配下にキュー４１−１〜４１−ｋ，４２−１〜
４２−ｋ，……，４ｌ−１〜４ｌ−ｋを配置すること
で、ラウンドロビン１，２−１〜２−ｋを多段構成とし
ている。また、各ラウンドロビン１，２−１〜２−ｋへ
の入力本数は必要な時間内に十分処理することができる
数となっている。
っても平等なアービトレーションを行うことが可能なア
ービタ回路を提供する。 【解決手段】 ラウンドロビン１の配下にラウンドロビ
ン２−１〜２−ｋが配置し、各ラウンドロビン２−１〜
２−ｋの配下にキュー４１−１〜４１−ｋ，４２−１〜
４２−ｋ，……，４ｌ−１〜４ｌ−ｋを配置すること
で、ラウンドロビン１，２−１〜２−ｋを多段構成とし
ている。また、各ラウンドロビン１，２−１〜２−ｋへ
の入力本数は必要な時間内に十分処理することができる
数となっている。
Description
【０００１】
【発明の属する技術分野】本発明はアービタ回路及びそ
れに用いる出力セルのアービトレーション方法に関し、
特にＡＴＭ（Ａｓｙｎｃｈｏｒｏｎｏｕｓ Ｔｒａｎｓ
ｆｅｒ Ｍｏｄｅ：非同期転送モード）交換機における
各ＶＣ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ）毎のキュー
イングに関する。
れに用いる出力セルのアービトレーション方法に関し、
特にＡＴＭ（Ａｓｙｎｃｈｏｒｏｎｏｕｓ Ｔｒａｎｓ
ｆｅｒ Ｍｏｄｅ：非同期転送モード）交換機における
各ＶＣ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ）毎のキュー
イングに関する。
【０００２】
【従来の技術】従来、ＡＴＭ交換機においては、よりき
め細かなトラフィックコントロールを実現するために、
各ＶＣ毎にセルを個別のキュー（Ｑｕｅｕｅ）に蓄積す
る「Ｐｅｒ ＶＣ Ｑｕｅｕｉｎｇ」という方法が採ら
れている。
め細かなトラフィックコントロールを実現するために、
各ＶＣ毎にセルを個別のキュー（Ｑｕｅｕｅ）に蓄積す
る「Ｐｅｒ ＶＣ Ｑｕｅｕｉｎｇ」という方法が採ら
れている。
【０００３】この「Ｐｅｒ ＶＣ Ｑｕｅｕｉｎｇ」と
いう方法はＡＴＭ交換機にＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒ
ｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）を実
装した際のＶＣマージ等にも用いられている。
いう方法はＡＴＭ交換機にＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒ
ｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）を実
装した際のＶＣマージ等にも用いられている。
【０００４】上記のＡＴＭ交換機におけるＶＣ毎のキュ
ーイングについては、特開平１０−２２４３６４号公
報、特開平１１−１９１７７４号公報、特許第２７９７
９８９号公報等に開示されている。
ーイングについては、特開平１０−２２４３６４号公
報、特開平１１−１９１７７４号公報、特許第２７９７
９８９号公報等に開示されている。
【０００５】
【発明が解決しようとする課題】しかしながら、「Ｐｅ
ｒ ＶＣ Ｑｕｅｕｉｎｇ」という方法を用いることに
よって、ＶＣ毎のトラフィックコントロールが可能にな
るが、その反面、キューが膨大な数（数万個）になる可
能性がある。
ｒ ＶＣ Ｑｕｅｕｉｎｇ」という方法を用いることに
よって、ＶＣ毎のトラフィックコントロールが可能にな
るが、その反面、キューが膨大な数（数万個）になる可
能性がある。
【０００６】そのため、出力でのアービトレーションの
処理時間が長くなり、一定時間内に処理が終了しないと
いう問題が発生する。よって、その問題を解決するため
のアービトレーションの方法が必要となる。
処理時間が長くなり、一定時間内に処理が終了しないと
いう問題が発生する。よって、その問題を解決するため
のアービトレーションの方法が必要となる。
【０００７】そこで、本発明の目的は上記の問題点を解
消し、比較的簡素な構成で、キューが膨大な数になって
も平等なアービトレーションを行うことができるアービ
タ回路及びそれに用いる出力セルのアービトレーション
方法を提供することにある。
消し、比較的簡素な構成で、キューが膨大な数になって
も平等なアービトレーションを行うことができるアービ
タ回路及びそれに用いる出力セルのアービトレーション
方法を提供することにある。
【０００８】
【課題を解決するための手段】本発明によるアービタ回
路は、出力セルを蓄積するキューと、前記キュー各々に
順番に出力セルを出力する権利を与えるラウンドロビン
とを含むアービタ回路であって、前記ラウンドロビンを
多段構成とし、前記ラウンドロビン各々への入力本数を
必要な時間内に十分処理可能な数として前記ラウンドロ
ビン各々へのトラフィックの平均化を行うよう構成して
いる。
路は、出力セルを蓄積するキューと、前記キュー各々に
順番に出力セルを出力する権利を与えるラウンドロビン
とを含むアービタ回路であって、前記ラウンドロビンを
多段構成とし、前記ラウンドロビン各々への入力本数を
必要な時間内に十分処理可能な数として前記ラウンドロ
ビン各々へのトラフィックの平均化を行うよう構成して
いる。
【０００９】本発明による出力セルのアービトレーショ
ン方法は、出力セルを蓄積するキューと、前記キュー各
々に順番に出力セルを出力する権利を与えるラウンドロ
ビンとを含むアービタ回路の出力セルのアービトレーシ
ョン方法であって、前記ラウンドロビンを多段構成と
し、前記ラウンドロビン各々への入力本数を必要な時間
内に十分処理可能な数として前記ラウンドロビン各々へ
のトラフィックの平均化を行うようにしている。
ン方法は、出力セルを蓄積するキューと、前記キュー各
々に順番に出力セルを出力する権利を与えるラウンドロ
ビンとを含むアービタ回路の出力セルのアービトレーシ
ョン方法であって、前記ラウンドロビンを多段構成と
し、前記ラウンドロビン各々への入力本数を必要な時間
内に十分処理可能な数として前記ラウンドロビン各々へ
のトラフィックの平均化を行うようにしている。
【００１０】すなわち、本発明の出力セルのアービトレ
ーション方法は、「Ｐｅｒ ＶＣＱｕｅｕｉｎｇ」を行
うＡＴＭ交換機において、出力セルのアービトレーショ
ンを行う方法に関するものである。
ーション方法は、「Ｐｅｒ ＶＣＱｕｅｕｉｎｇ」を行
うＡＴＭ交換機において、出力セルのアービトレーショ
ンを行う方法に関するものである。
【００１１】アービトレーションは、（ａ）異なるサー
ビスクラス間で固定的（静的）に優先度を決める方法
と、（ｂ）同一サービスクラス内で平等に出力させる方
法とに分けられる。本発明は（ｂ）の同一サービスクラ
ス内のアービトレーションにおいて、キューの数が多く
なった場合の各キュー間の平等性の確保を、入出力を含
めたシステム全体での閉ループを使用せずに簡素な方法
で実現可能としたことを特徴とする。
ビスクラス間で固定的（静的）に優先度を決める方法
と、（ｂ）同一サービスクラス内で平等に出力させる方
法とに分けられる。本発明は（ｂ）の同一サービスクラ
ス内のアービトレーションにおいて、キューの数が多く
なった場合の各キュー間の平等性の確保を、入出力を含
めたシステム全体での閉ループを使用せずに簡素な方法
で実現可能としたことを特徴とする。
【００１２】（ａ）のアービトレーションにおける異な
るサービスクラス間の優先度は固定的であり、高優先の
セルがキューに蓄積されている間、低優先のセルが出力
されることはない。これによって、高優先のセルの遅延
特性を確保することを可能としている。
るサービスクラス間の優先度は固定的であり、高優先の
セルがキューに蓄積されている間、低優先のセルが出力
されることはない。これによって、高優先のセルの遅延
特性を確保することを可能としている。
【００１３】（ｂ）の同一サービスクラス内でのアービ
トレーションでは全キューについて平等であることが求
められる。通常、ラウンドロビン（ＲＲ：Ｒｏｕｎｄ
Ｒｏｂｉｎ）を用いることによって、各キューに順番に
セルを出力する権利を与えることを可能とし、さらに該
当するキューにセルが蓄積されていない時には次のキュ
ーへ権利を移すことが可能となる。但し、「Ｐｅｒ Ｖ
Ｃ Ｑｕｅｕｉｎｇ」を行う場合には、同一サービスク
ラスのキューの数が数万個になる可能性があり、処理時
間が追いつかないという問題が生じる。
トレーションでは全キューについて平等であることが求
められる。通常、ラウンドロビン（ＲＲ：Ｒｏｕｎｄ
Ｒｏｂｉｎ）を用いることによって、各キューに順番に
セルを出力する権利を与えることを可能とし、さらに該
当するキューにセルが蓄積されていない時には次のキュ
ーへ権利を移すことが可能となる。但し、「Ｐｅｒ Ｖ
Ｃ Ｑｕｅｕｉｎｇ」を行う場合には、同一サービスク
ラスのキューの数が数万個になる可能性があり、処理時
間が追いつかないという問題が生じる。
【００１４】ラウンドロビンの代わりに、Ｔｉｍｅ Ｗ
ｈｅｅｌを用いて動的に帯域を制御することができれば
この問題を解決することができるが、この場合には入力
側を含んだシステム全体での複雑な閉ループ制御が必要
となる。
ｈｅｅｌを用いて動的に帯域を制御することができれば
この問題を解決することができるが、この場合には入力
側を含んだシステム全体での複雑な閉ループ制御が必要
となる。
【００１５】そこで、本発明のアービトレーション方法
では、ラウンドロビンを多段構成とし、各ラウンドロビ
ンへの入力の本数を必要な時間内に十分処理可能な数に
している。これによって、各ラウンドロビンへ入力する
キューについて平等にセル出力の権利が与えられる。但
し、これは通常時のことであり、輻輳時には各キュー間
の平等性が失われる恐れがある。
では、ラウンドロビンを多段構成とし、各ラウンドロビ
ンへの入力の本数を必要な時間内に十分処理可能な数に
している。これによって、各ラウンドロビンへ入力する
キューについて平等にセル出力の権利が与えられる。但
し、これは通常時のことであり、輻輳時には各キュー間
の平等性が失われる恐れがある。
【００１６】例えば、第１のラウンドロビンに比較的入
力セルレートの高いキューが集中し、第２のラウンドロ
ビンに入力セルレートの高いキューが１つとその他のレ
ートの極小さなキューからのセルが入力される場合を考
える。輻輳によって入力レートの合計が出力レートを超
過してしまう場合には、入力レートが同じであるにも関
わらず、第２のラウンドロビンのキューの出力レートは
第１のラウンドロビンのキューよりも高くなり、キュー
間の出力の平等性が崩れてしまうことになる。
力セルレートの高いキューが集中し、第２のラウンドロ
ビンに入力セルレートの高いキューが１つとその他のレ
ートの極小さなキューからのセルが入力される場合を考
える。輻輳によって入力レートの合計が出力レートを超
過してしまう場合には、入力レートが同じであるにも関
わらず、第２のラウンドロビンのキューの出力レートは
第１のラウンドロビンのキューよりも高くなり、キュー
間の出力の平等性が崩れてしまうことになる。
【００１７】このような問題を回避するために、本発明
のアービトレーション方法では、各ラウンドロビンへの
入力レートが等しくなるように調整する機構を持つ。各
ラウンドロビンは配下のキューまたはラウンドロビンか
ら自回路へと入力される予定のセルレートの情報を持
つ。さらに、配下がラウンドロビンの場合には、配下の
ラウンドロビンの中で最も入力レートが低いラウンドロ
ビン及び２番目にレートが低いラウンドロビンの情報を
持つ。これらの情報はコネクションを張る際に申請され
る情報を基に作成される。
のアービトレーション方法では、各ラウンドロビンへの
入力レートが等しくなるように調整する機構を持つ。各
ラウンドロビンは配下のキューまたはラウンドロビンか
ら自回路へと入力される予定のセルレートの情報を持
つ。さらに、配下がラウンドロビンの場合には、配下の
ラウンドロビンの中で最も入力レートが低いラウンドロ
ビン及び２番目にレートが低いラウンドロビンの情報を
持つ。これらの情報はコネクションを張る際に申請され
る情報を基に作成される。
【００１８】コネクションが新たに張られる場合には、
最上位のラウンドロビンの情報から配下のラウンドロビ
ンの中で最も低い入力レートのラウンドロビンを選択す
る。選ばれたラウンドロビンの持つ情報からさらに配下
のラウンドロビンの中で最も低いレートのラウンドロビ
ンを選択する。このように最終段まで繰り返し、その配
下にキューを配置することによって、各ラウンドロビン
において入力されるセルレートができるだけ等しくなる
ように、キューが配置される。
最上位のラウンドロビンの情報から配下のラウンドロビ
ンの中で最も低い入力レートのラウンドロビンを選択す
る。選ばれたラウンドロビンの持つ情報からさらに配下
のラウンドロビンの中で最も低いレートのラウンドロビ
ンを選択する。このように最終段まで繰り返し、その配
下にキューを配置することによって、各ラウンドロビン
において入力されるセルレートができるだけ等しくなる
ように、キューが配置される。
【００１９】各キューの出力の平等性をさらに増すため
には、新たなコネクションが追加されるか、もしくは削
除される度に全てのキューのレートを計算して各ラウン
ドロビンへ再分配する必要があるが、システムの簡単化
のため、本発明のシステムでは行わない。
には、新たなコネクションが追加されるか、もしくは削
除される度に全てのキューのレートを計算して各ラウン
ドロビンへ再分配する必要があるが、システムの簡単化
のため、本発明のシステムでは行わない。
【００２０】上記のように、多段のラウンドロビンと各
ラウンドロビンへのトラフィックの平均化を行うことに
よって、「Ｐｅｒ ＶＣ Ｑｕｅｕｉｎｇ」によってキ
ューが膨大な数になっても平等なアービトレーションを
行うことが可能となる。また、トラフィックを平均化す
ることによって、輻輳時にも上記の効果が得られる。さ
らに、装置全体の閉ループ制御とＴｉｍｅ Ｗｈｅｅｌ
との組合せを用いることなく、比較的簡素な構成で上記
の効果が得られる。
ラウンドロビンへのトラフィックの平均化を行うことに
よって、「Ｐｅｒ ＶＣ Ｑｕｅｕｉｎｇ」によってキ
ューが膨大な数になっても平等なアービトレーションを
行うことが可能となる。また、トラフィックを平均化す
ることによって、輻輳時にも上記の効果が得られる。さ
らに、装置全体の閉ループ制御とＴｉｍｅ Ｗｈｅｅｌ
との組合せを用いることなく、比較的簡素な構成で上記
の効果が得られる。
【００２１】
【発明の実施の形態】次に、本発明の実施の形態につい
て図面を参照して説明する。図１は本発明の実施の形態
によるアービタ回路の構成を示すブロック図である。図
１において、本発明の実施の形態によるアービタ回路は
ラウンドロビン（ＲＲ：ＲｏｕｎｄＲｏｂｉｎ）１，２
−１〜２−ｋを多段構成にし、各ラウンドロビン１，２
−１〜２−ｋへの入力本数を、必要な時間内に十分処理
することができる数にしている。
て図面を参照して説明する。図１は本発明の実施の形態
によるアービタ回路の構成を示すブロック図である。図
１において、本発明の実施の形態によるアービタ回路は
ラウンドロビン（ＲＲ：ＲｏｕｎｄＲｏｂｉｎ）１，２
−１〜２−ｋを多段構成にし、各ラウンドロビン１，２
−１〜２−ｋへの入力本数を、必要な時間内に十分処理
することができる数にしている。
【００２２】すなわち、ラウンドロビン１の配下にはラ
ウンドロビン２−１〜２−ｋが配置され、各ラウンドロ
ビン２−１〜２−ｋの配下にはキュー（Ｑｕｅｕｅ）４
１−１〜４１−ｋ，４２−１〜４２−ｋ，……，４ｌ−
１〜４ｌ−ｋが配置されている。
ウンドロビン２−１〜２−ｋが配置され、各ラウンドロ
ビン２−１〜２−ｋの配下にはキュー（Ｑｕｅｕｅ）４
１−１〜４１−ｋ，４２−１〜４２−ｋ，……，４ｌ−
１〜４ｌ−ｋが配置されている。
【００２３】これによって、各ラウンドロビン２−１〜
２−ｋへ入力するキュー４１−１〜４１−ｋ，４２−１
〜４２−ｋ，……，４ｌ−１〜４ｌ−ｋについて平等に
セル出力の権利が与えられる。但し、これは通常時のこ
とであり、輻輳時には各キュー４１−１〜４１−ｋ，４
２−１〜４２−ｋ，……，４ｌ−１〜４ｌ−ｋ間の平等
性が失われる恐れがある。
２−ｋへ入力するキュー４１−１〜４１−ｋ，４２−１
〜４２−ｋ，……，４ｌ−１〜４ｌ−ｋについて平等に
セル出力の権利が与えられる。但し、これは通常時のこ
とであり、輻輳時には各キュー４１−１〜４１−ｋ，４
２−１〜４２−ｋ，……，４ｌ−１〜４ｌ−ｋ間の平等
性が失われる恐れがある。
【００２４】図２は本発明の実施の形態によるアービタ
回路で一時的に輻輳した時の問題点を示す図である。図
２に示すように、ラウンドロビン２−１に比較的入力セ
ルレートの高いキュー４１−１〜４１−３が集中し、ラ
ウンドロビン２−２には入力セルレートの高いキュー４
２−１が１つ（キュー４１−１〜４１−３と同じレー
ト）とその他のレートの極小さなキュー４２−２，４２
−３からのセルが入力される場合を考える。
回路で一時的に輻輳した時の問題点を示す図である。図
２に示すように、ラウンドロビン２−１に比較的入力セ
ルレートの高いキュー４１−１〜４１−３が集中し、ラ
ウンドロビン２−２には入力セルレートの高いキュー４
２−１が１つ（キュー４１−１〜４１−３と同じレー
ト）とその他のレートの極小さなキュー４２−２，４２
−３からのセルが入力される場合を考える。
【００２５】輻輳によって入力レートの合計が出力レー
トを超過してしまう場合には、入力レートが同じである
にも関わらず、キュー４２−１の出力レートはキュー４
１−１〜４１−３よりも高くなり、キュー４２−１〜４
２−３間の出力の平等性が崩れてしまう。
トを超過してしまう場合には、入力レートが同じである
にも関わらず、キュー４２−１の出力レートはキュー４
１−１〜４１−３よりも高くなり、キュー４２−１〜４
２−３間の出力の平等性が崩れてしまう。
【００２６】このような問題を回避するために、本発明
の実施の形態によるアービタ回路は各ラウンドロビン
１，２−１，２−２への入力レートが等しくなるように
調整する機構を持つ。各ラウンドロビン１，２−１，２
−２は配下のキュー４１−１〜４１−３，４２−１〜４
２−３またはラウンドロビン２−１，２−２から自回路
へと入力される予定のセルレートの情報を持つ。
の実施の形態によるアービタ回路は各ラウンドロビン
１，２−１，２−２への入力レートが等しくなるように
調整する機構を持つ。各ラウンドロビン１，２−１，２
−２は配下のキュー４１−１〜４１−３，４２−１〜４
２−３またはラウンドロビン２−１，２−２から自回路
へと入力される予定のセルレートの情報を持つ。
【００２７】さらに、配下がラウンドロビン２−１，２
−２の場合には、配下のラウンドロビン２−１，２−２
の中で最も入力レートが低いラウンドロビン及び２番目
にレートが低いラウンドロビンの情報を持つ。これらの
情報はコネクションを張る際に申請される情報を基に作
成される。
−２の場合には、配下のラウンドロビン２−１，２−２
の中で最も入力レートが低いラウンドロビン及び２番目
にレートが低いラウンドロビンの情報を持つ。これらの
情報はコネクションを張る際に申請される情報を基に作
成される。
【００２８】コネクションが新たに張られる場合には、
最上位のラウンドロビンの情報から配下のラウンドロビ
ンの中で最も低い入力レートのラウンドロビンを選択す
る。選ばれたラウンドロビンの持つ情報からさらに配下
のラウンドロビンの中で最も低いレートのラウンドロビ
ンを選択する。
最上位のラウンドロビンの情報から配下のラウンドロビ
ンの中で最も低い入力レートのラウンドロビンを選択す
る。選ばれたラウンドロビンの持つ情報からさらに配下
のラウンドロビンの中で最も低いレートのラウンドロビ
ンを選択する。
【００２９】このように、ラウンドロビンの選択を最終
段まで繰り返し、その配下にキューを配置することによ
って、各ラウンドロビンにおいて入力されるセルレート
ができるだけ等しくなるように、キューが配置される。
段まで繰り返し、その配下にキューを配置することによ
って、各ラウンドロビンにおいて入力されるセルレート
ができるだけ等しくなるように、キューが配置される。
【００３０】各キューの出力の平等性をさらに増すため
には、新たなコネクションが追加されるか、もしくは削
除される度に全てのキューのレートを計算して各ラウン
ドロビンへ再分配する必要があるが、システムの簡単化
のため、本発明のシステムでは行わない。
には、新たなコネクションが追加されるか、もしくは削
除される度に全てのキューのレートを計算して各ラウン
ドロビンへ再分配する必要があるが、システムの簡単化
のため、本発明のシステムでは行わない。
【００３１】図３は本発明の一実施例によるアービタ回
路の構成を示すブロック図であり、図４は図３の各ラウ
ンドロビンが持つ情報を示す図であり、図５は図３の各
ラウンドロビンが持つコネクション追加後の情報を示す
図であり、図６は図３の各ラウンドロビンが持つコネク
ション削除後の情報を示す図である。
路の構成を示すブロック図であり、図４は図３の各ラウ
ンドロビンが持つ情報を示す図であり、図５は図３の各
ラウンドロビンが持つコネクション追加後の情報を示す
図であり、図６は図３の各ラウンドロビンが持つコネク
ション削除後の情報を示す図である。
【００３２】また、図７及び図８は本発明の一実施例に
よるアービタ回路におけるコネクション追加または削除
後の情報の更新処理を示すフローチャートである。これ
ら図３〜図８を参照して本発明の一実施例によるアービ
タ回路の構成及び動作について説明する。
よるアービタ回路におけるコネクション追加または削除
後の情報の更新処理を示すフローチャートである。これ
ら図３〜図８を参照して本発明の一実施例によるアービ
タ回路の構成及び動作について説明する。
【００３３】以下の説明では簡単化のためにラウンドロ
ビンの多段構成を３段構成とし、ラウンドロビン１を最
上位のラウンドロビンする。また、ラウンドロビン１の
配下にはそれぞれラウンドロビン２−１〜２−４があ
り、ラウンドロビン２−１の配下にラウンドロビン３−
１〜３−３がある。尚、ラウンドロビン２−２〜２−４
の配下のラウンドロビンについては省略する。
ビンの多段構成を３段構成とし、ラウンドロビン１を最
上位のラウンドロビンする。また、ラウンドロビン１の
配下にはそれぞれラウンドロビン２−１〜２−４があ
り、ラウンドロビン２−１の配下にラウンドロビン３−
１〜３−３がある。尚、ラウンドロビン２−２〜２−４
の配下のラウンドロビンについては省略する。
【００３４】一方、ラウンドロビン３−１〜３−３の配
下にはＶＣ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ）毎のセ
ルを蓄積するキューがあり、各ＶＣのセルレートはそれ
ぞれ図３に示す通りである。すなわち、キュー４１−１
〜４１−３のレートはそれぞれ２Ｍｂｐｓ、４Ｍｂｐ
ｓ、６Ｍｂｐｓであるので、ラウンドロビン３−１のレ
ートは１２Ｍｂｐｓである。
下にはＶＣ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ）毎のセ
ルを蓄積するキューがあり、各ＶＣのセルレートはそれ
ぞれ図３に示す通りである。すなわち、キュー４１−１
〜４１−３のレートはそれぞれ２Ｍｂｐｓ、４Ｍｂｐ
ｓ、６Ｍｂｐｓであるので、ラウンドロビン３−１のレ
ートは１２Ｍｂｐｓである。
【００３５】また、キュー４２−１〜４２−３のレート
はそれぞれ２０Ｍｂｐｓ、１１Ｍｂｐｓ、８Ｍｂｐｓで
あるので、ラウンドロビン３−２のレートは３９Ｍｂｐ
ｓであり、キュー４３−１〜４３−３のレートはそれぞ
れ１４Ｍｂｐｓ、７Ｍｂｐｓ、６Ｍｂｐｓであるので、
ラウンドロビン３−３のレートは２７Ｍｂｐｓである。
はそれぞれ２０Ｍｂｐｓ、１１Ｍｂｐｓ、８Ｍｂｐｓで
あるので、ラウンドロビン３−２のレートは３９Ｍｂｐ
ｓであり、キュー４３−１〜４３−３のレートはそれぞ
れ１４Ｍｂｐｓ、７Ｍｂｐｓ、６Ｍｂｐｓであるので、
ラウンドロビン３−３のレートは２７Ｍｂｐｓである。
【００３６】各ラウンドロビン１，２−１〜２−４，３
−１〜３−３は、図４に示すように、入力セルレートと
配下の最低レートのラウンドロビンと配下で２番目にレ
ートの低いラウンドロビンとからなる情報を持つ。
−１〜３−３は、図４に示すように、入力セルレートと
配下の最低レートのラウンドロビンと配下で２番目にレ
ートの低いラウンドロビンとからなる情報を持つ。
【００３７】次に、図３〜図８を参照して、本発明の一
実施例によるアービタ回路におけるコネクション追加ま
たは削除後の動作及び各ラウンドロビン１，２−１〜２
−４，３−１〜３−３の情報の更新について説明する。
実施例によるアービタ回路におけるコネクション追加ま
たは削除後の動作及び各ラウンドロビン１，２−１〜２
−４，３−１〜３−３の情報の更新について説明する。
【００３８】新たにレート５Ｍｂｐｓのコネクションを
追加する場合（図７ステップＳ１）、最上位のラウンド
ロビン１の配下で最低レートのラウンドロビンを探索す
る（図７ステップＳ２）。この探索で配下のラウンドロ
ビンがあるかどうかが判定される（図７ステップＳ
３）。配下のラウンドロビンがあればステップＳ４に移
行し、配下のラウンドロビンがなければ、ステップＳ６
に移行する。
追加する場合（図７ステップＳ１）、最上位のラウンド
ロビン１の配下で最低レートのラウンドロビンを探索す
る（図７ステップＳ２）。この探索で配下のラウンドロ
ビンがあるかどうかが判定される（図７ステップＳ
３）。配下のラウンドロビンがあればステップＳ４に移
行し、配下のラウンドロビンがなければ、ステップＳ６
に移行する。
【００３９】この場合、図４に示すように、ラウンドロ
ビン２−１が探索され、その配下のラウンドロビン３−
１〜３−３があるので、ラウンドロビン２−１の配下で
最低レートのラウンドロビンを探索する（図７ステップ
Ｓ４）。この探索で配下のラウンドロビンがあるかどう
かが判定される（図７ステップＳ５）。配下のラウンド
ロビンがあればステップＳ４に移行し、配下のラウンド
ロビンがなければ、ステップＳ６に移行する。
ビン２−１が探索され、その配下のラウンドロビン３−
１〜３−３があるので、ラウンドロビン２−１の配下で
最低レートのラウンドロビンを探索する（図７ステップ
Ｓ４）。この探索で配下のラウンドロビンがあるかどう
かが判定される（図７ステップＳ５）。配下のラウンド
ロビンがあればステップＳ４に移行し、配下のラウンド
ロビンがなければ、ステップＳ６に移行する。
【００４０】この場合、図４に示すように、ラウンドロ
ビン３−１が探索されるが、その配下のラウンドロビン
がないので、ラウンドロビン３−１の配下にキュー４１
−４を追加し、新しいコネクションのセルを蓄積できる
ようにする（図７ステップＳ６）。
ビン３−１が探索されるが、その配下のラウンドロビン
がないので、ラウンドロビン３−１の配下にキュー４１
−４を追加し、新しいコネクションのセルを蓄積できる
ようにする（図７ステップＳ６）。
【００４１】キュー４１−４の追加後、ラウンドロビン
３−１の情報を更新する（図７ステップＳ７）。その
際、ラウンドロビン３−１の情報は現在のセルレート１
２Ｍｂｐｓに、新たに追加された５Ｍｂｐｓを加算して
１７Ｍｂｐｓとなる（図５参照）。
３−１の情報を更新する（図７ステップＳ７）。その
際、ラウンドロビン３−１の情報は現在のセルレート１
２Ｍｂｐｓに、新たに追加された５Ｍｂｐｓを加算して
１７Ｍｂｐｓとなる（図５参照）。
【００４２】続いて、ラウンドロビン３−１の直近上位
のラウンドロビン２−１の情報を更新する（図７ステッ
プＳ８）。その際、ラウンドロビン２−１の配下で２番
目に低いレートのラウンドロビン３−３のセルレート２
７ＭｂｐｓとステップＳ６で更新された情報とを比較し
てから情報の更新が行われる。
のラウンドロビン２−１の情報を更新する（図７ステッ
プＳ８）。その際、ラウンドロビン２−１の配下で２番
目に低いレートのラウンドロビン３−３のセルレート２
７ＭｂｐｓとステップＳ６で更新された情報とを比較し
てから情報の更新が行われる。
【００４３】その結果、ラウンドロビン３−１（１７Ｍ
ｂｐｓに更新）の方がラウンドロビン３−３（２７Ｍｂ
ｐｓ）より小さいので、ラウンドロビン２−１の情報に
おいて最低レートのラウンドロビン及び２番目に低いレ
ートのラウンドロビンは変化しない。また、ラウンドロ
ビン２−１の情報においては現在のセルレート７８Ｍｂ
ｐｓに追加された５Ｍｂｐｓを加算して８３Ｍｂｐｓと
なる（図５参照）。
ｂｐｓに更新）の方がラウンドロビン３−３（２７Ｍｂ
ｐｓ）より小さいので、ラウンドロビン２−１の情報に
おいて最低レートのラウンドロビン及び２番目に低いレ
ートのラウンドロビンは変化しない。また、ラウンドロ
ビン２−１の情報においては現在のセルレート７８Ｍｂ
ｐｓに追加された５Ｍｂｐｓを加算して８３Ｍｂｐｓと
なる（図５参照）。
【００４４】この後、情報が更新されたラウンドロビン
の直近上位のラウンドロビンが最上位のラウンドロビン
かどうかが判定される（図７ステップＳ９）。最上位の
ラウンドロビンでなければステップＳ８に戻り、最上位
のラウンドロビンであればステップＳ１０に移行する。
の直近上位のラウンドロビンが最上位のラウンドロビン
かどうかが判定される（図７ステップＳ９）。最上位の
ラウンドロビンでなければステップＳ８に戻り、最上位
のラウンドロビンであればステップＳ１０に移行する。
【００４５】この場合、情報が更新されたラウンドロビ
ン２−１の直近上位のラウンドロビン１が最上位のラウ
ンドロビンであるので、ラウンドロビン１の情報を更新
する（図７ステップＳ１０）。その際、ラウンドロビン
１の配下で２番目に低いレートのラウンドロビン２−４
のセルレート８０ＭｂｐｓとステップＳ８で更新された
情報とを比較してから情報の更新が行われる。
ン２−１の直近上位のラウンドロビン１が最上位のラウ
ンドロビンであるので、ラウンドロビン１の情報を更新
する（図７ステップＳ１０）。その際、ラウンドロビン
１の配下で２番目に低いレートのラウンドロビン２−４
のセルレート８０ＭｂｐｓとステップＳ８で更新された
情報とを比較してから情報の更新が行われる。
【００４６】その結果、ラウンドロビン２−１（８３Ｍ
ｂｐｓに更新）の方がラウンドロビン２−４（８０Ｍｂ
ｐｓ）より大きくなったため、ラウンドロビン１配下の
全ラウンドロビン２−１〜２−４の情報を参照し、最低
レートのラウンドロビンをラウンドロビン２−４に、２
番目に低いレートのラウンドロビンをラウンドロビン２
−１に更新する。また、ラウンドロビン１の情報におい
ては現在のセルレート４２５Ｍｂｐｓに追加された５Ｍ
ｂｐｓを加算し、４３０Ｍｂｐｓに更新する。上記のよ
うな新しいコネクションの追加が終わった後の各ラウン
ドロビン１，２−１〜２−４，３−１〜３−３の情報を
図５に示す。
ｂｐｓに更新）の方がラウンドロビン２−４（８０Ｍｂ
ｐｓ）より大きくなったため、ラウンドロビン１配下の
全ラウンドロビン２−１〜２−４の情報を参照し、最低
レートのラウンドロビンをラウンドロビン２−４に、２
番目に低いレートのラウンドロビンをラウンドロビン２
−１に更新する。また、ラウンドロビン１の情報におい
ては現在のセルレート４２５Ｍｂｐｓに追加された５Ｍ
ｂｐｓを加算し、４３０Ｍｂｐｓに更新する。上記のよ
うな新しいコネクションの追加が終わった後の各ラウン
ドロビン１，２−１〜２−４，３−１〜３−３の情報を
図５に示す。
【００４７】次に、キュー４２−１のコネクションを削
除する場合（図７ステップＳ１）、削除したキューにつ
ながるラウンドロビン３−２の情報を更新する（図８ス
テップＳ１１）。ラウンドロビン３−２の情報において
は現在のセルレート３９Ｍｂｐｓからキュー４２−１の
レート２０Ｍｂｐｓを減算し、１９Ｍｂｐｓに更新され
る。
除する場合（図７ステップＳ１）、削除したキューにつ
ながるラウンドロビン３−２の情報を更新する（図８ス
テップＳ１１）。ラウンドロビン３−２の情報において
は現在のセルレート３９Ｍｂｐｓからキュー４２−１の
レート２０Ｍｂｐｓを減算し、１９Ｍｂｐｓに更新され
る。
【００４８】続いて、ラウンドロビン３−２につながる
直近上位のラウンドロビン２−１の情報を更新する（図
８ステップＳ１２）。その際、ラウンドロビン２−１の
配下で最低レートのラウンドロビン３−１のレート１２
ＭｂｐｓとステップＳ１１で更新されたレートとを比較
してから情報の更新が行われる。
直近上位のラウンドロビン２−１の情報を更新する（図
８ステップＳ１２）。その際、ラウンドロビン２−１の
配下で最低レートのラウンドロビン３−１のレート１２
ＭｂｐｓとステップＳ１１で更新されたレートとを比較
してから情報の更新が行われる。
【００４９】その結果、ラウンドロビン３−２（１９Ｍ
ｂｐｓに更新）よりもラウンドロビン３−１（１２Ｍｂ
ｐｓ）の方が小さいため、ラウンドロビン２−１の情報
における最低レートのラウンドロビンは変化しない。
ｂｐｓに更新）よりもラウンドロビン３−１（１２Ｍｂ
ｐｓ）の方が小さいため、ラウンドロビン２−１の情報
における最低レートのラウンドロビンは変化しない。
【００５０】また、ラウンドロビン２−１の配下で２番
目にレートの低いラウンドロビン３−３のレート２７Ｍ
ｂｐｓとステップＳ１１で更新されたレートとを比較す
ると、ラウンドロビン３−２（１９Ｍｂｐｓに更新）の
方がラウンドロビン３−３（２７Ｍｂｐｓ）より小さく
なったため、２番目にレートの低いラウンドロビンはラ
ウンドロビン３−２に更新される。さらに、ラウンドロ
ビン２−１の情報においては、現在のセルレート７８Ｍ
ｂｐｓからキュー４２−１の２０Ｍｂｐｓを減算し、５
８Ｍｂｐｓに更新される。
目にレートの低いラウンドロビン３−３のレート２７Ｍ
ｂｐｓとステップＳ１１で更新されたレートとを比較す
ると、ラウンドロビン３−２（１９Ｍｂｐｓに更新）の
方がラウンドロビン３−３（２７Ｍｂｐｓ）より小さく
なったため、２番目にレートの低いラウンドロビンはラ
ウンドロビン３−２に更新される。さらに、ラウンドロ
ビン２−１の情報においては、現在のセルレート７８Ｍ
ｂｐｓからキュー４２−１の２０Ｍｂｐｓを減算し、５
８Ｍｂｐｓに更新される。
【００５１】この後、情報が更新されたラウンドロビン
の直近上位のラウンドロビンが最上位のラウンドロビン
かどうかが判定される（図８ステップＳ１３）。最上位
のラウンドロビンでなければステップＳ１２に戻り、最
上位のラウンドロビンであればステップＳ１４に移行す
る。
の直近上位のラウンドロビンが最上位のラウンドロビン
かどうかが判定される（図８ステップＳ１３）。最上位
のラウンドロビンでなければステップＳ１２に戻り、最
上位のラウンドロビンであればステップＳ１４に移行す
る。
【００５２】この場合、情報が更新されたラウンドロビ
ン２−１の直近上位のラウンドロビン１が最上位のラウ
ンドロビンであるので、ラウンドロビン１の情報を更新
する（図８ステップＳ１４）。その際、ラウンドロビン
１の配下で最低レートのラウンドロビンがラウンドロビ
ン２−１であるため（図４参照）、情報の更新は行われ
ない。また、ラウンドロビン１の情報においては、現在
のセルレート４２５Ｍｂｐｓから削除された２０Ｍｂｐ
ｓを減算し、４０５Ｍｂｐｓに更新される。錠のような
コネクションの削除が終了した後の各ラウンドロビン
１，２−１〜２−４，３−１〜３−３の情報を図６に示
す。
ン２−１の直近上位のラウンドロビン１が最上位のラウ
ンドロビンであるので、ラウンドロビン１の情報を更新
する（図８ステップＳ１４）。その際、ラウンドロビン
１の配下で最低レートのラウンドロビンがラウンドロビ
ン２−１であるため（図４参照）、情報の更新は行われ
ない。また、ラウンドロビン１の情報においては、現在
のセルレート４２５Ｍｂｐｓから削除された２０Ｍｂｐ
ｓを減算し、４０５Ｍｂｐｓに更新される。錠のような
コネクションの削除が終了した後の各ラウンドロビン
１，２−１〜２−４，３−１〜３−３の情報を図６に示
す。
【００５３】以上の手順によってコネクションの追加ま
たは削除が行われる。この方法によって、比較的簡素な
方法で各ラウンドロビン１，２−１〜２−４，３−１〜
３−３のトラフィックの平均化を行うことができ、「Ｐ
ｅｒ ＶＣ Ｑｕｅｕｉｎｇ」でキューの数が増えても
平等なアービトレーションを行うことができる。
たは削除が行われる。この方法によって、比較的簡素な
方法で各ラウンドロビン１，２−１〜２−４，３−１〜
３−３のトラフィックの平均化を行うことができ、「Ｐ
ｅｒ ＶＣ Ｑｕｅｕｉｎｇ」でキューの数が増えても
平等なアービトレーションを行うことができる。
【００５４】このように、多段のラウンドロビンと各ラ
ウンドロビンへのトラフィックの平均化を行うことによ
って、「Ｐｅｒ ＶＣ Ｑｕｅｕｉｎｇ」でキューが膨
大な数になっても平等なアービトレーションが行うこと
ができる。
ウンドロビンへのトラフィックの平均化を行うことによ
って、「Ｐｅｒ ＶＣ Ｑｕｅｕｉｎｇ」でキューが膨
大な数になっても平等なアービトレーションが行うこと
ができる。
【００５５】また、各ラウンドロビン１，２−１〜２−
４，３−１〜３−３のトラフィックを平均化することに
よって、輻輳時にも上記の効果が得られる。さらに、装
置全体の閉ループ制御とＴｉｍｅ Ｗｈｅｅｌとの組合
せを用いることなく、比較的簡素な構成で、上記の効果
を得られる。
４，３−１〜３−３のトラフィックを平均化することに
よって、輻輳時にも上記の効果が得られる。さらに、装
置全体の閉ループ制御とＴｉｍｅ Ｗｈｅｅｌとの組合
せを用いることなく、比較的簡素な構成で、上記の効果
を得られる。
【００５６】
【発明の効果】以上説明したように本発明によれば、出
力セルを蓄積するキューと、キュー各々に順番に出力セ
ルを出力する権利を与えるラウンドロビンとを含むアー
ビタ回路において、ラウンドロビンを多段構成とし、ラ
ウンドロビン各々への入力本数を必要な時間内に十分処
理可能な数としてラウンドロビン各々へのトラフィック
の平均化を行うことによって、比較的簡素な構成で、キ
ューが膨大な数になっても平等なアービトレーションを
行うことができるという効果がある。
力セルを蓄積するキューと、キュー各々に順番に出力セ
ルを出力する権利を与えるラウンドロビンとを含むアー
ビタ回路において、ラウンドロビンを多段構成とし、ラ
ウンドロビン各々への入力本数を必要な時間内に十分処
理可能な数としてラウンドロビン各々へのトラフィック
の平均化を行うことによって、比較的簡素な構成で、キ
ューが膨大な数になっても平等なアービトレーションを
行うことができるという効果がある。
【図１】本発明の実施の形態によるアービタ回路の構成
を示すブロック図である。
を示すブロック図である。
【図２】本発明の実施の形態によるアービタ回路で一時
的に輻輳した時の問題点を示す図である。
的に輻輳した時の問題点を示す図である。
【図３】本発明の一実施例によるアービタ回路の構成を
示すブロック図である。
示すブロック図である。
【図４】図３の各ラウンドロビンが持つ情報を示す図で
ある。
ある。
【図５】図３の各ラウンドロビンが持つコネクション追
加後の情報を示す図である。
加後の情報を示す図である。
【図６】図３の各ラウンドロビンが持つコネクション削
除後の情報を示す図である。
除後の情報を示す図である。
【図７】本発明の一実施例によるアービタ回路における
コネクション追加または削除後の情報の更新処理を示す
フローチャートである。
コネクション追加または削除後の情報の更新処理を示す
フローチャートである。
【図８】本発明の一実施例によるアービタ回路における
コネクション追加または削除後の情報の更新処理を示す
フローチャートである。
コネクション追加または削除後の情報の更新処理を示す
フローチャートである。
１，２−１〜２−ｋ，３−１〜３−３ ラウンドロビン ４１−１〜４１−ｋ，４２−１〜４２−ｋ，４ｌ−１〜
４ｌ−ｋ キュー
４ｌ−ｋ キュー
Claims (12)
- 【請求項１】 出力セルを蓄積するキューと、前記キュ
ー各々に順番に出力セルを出力する権利を与えるラウン
ドロビンとを含むアービタ回路であって、前記ラウンド
ロビンを多段構成とし、前記ラウンドロビン各々への入
力本数を必要な時間内に十分処理可能な数として前記ラ
ウンドロビン各々へのトラフィックの平均化を行うよう
構成したことを特徴とするアービタ回路。 - 【請求項２】 前記ラウンドロビン各々は、該当するキ
ューにセルが蓄積されていない時には次のキューへ権利
を移すよう構成したことを特徴とする請求項１記載のア
ービタ回路。 - 【請求項３】 前記ラウンドロビン各々は、配下のキュ
ー及び配下のラウンドロビンから自回路へと入力される
予定のセルレートの情報を持つよう構成したことを特徴
とする請求項１または請求項２記載のアービタ回路。 - 【請求項４】 前記ラウンドロビン各々は、配下がラウ
ンドロビンの場合に当該配下のラウンドロビンの中で最
も入力レートが低いラウンドロビン及び２番目にレート
が低いラウンドロビンの情報を持つよう構成したことを
特徴とする請求項３記載のアービタ回路。 - 【請求項５】 前記ラウンドロビン各々が持つ情報はコ
ネクションを張る際に申請される情報を基に作成するよ
う構成したことを特徴とする請求項３または請求項４記
載のアービタ回路。 - 【請求項６】 前記コネクションが新たに張られる場合
に、配下のラウンドロビンの中でもっとも低い入力レー
トのラウンドロビンを順次選択し、最終段のラウンドロ
ビンの配下にキューを配置するよう構成したことを特徴
とする請求項５記載のアービタ回路。 - 【請求項７】 出力セルを蓄積するキューと、前記キュ
ー各々に順番に出力セルを出力する権利を与えるラウン
ドロビンとを含むアービタ回路の出力セルのアービトレ
ーション方法であって、前記ラウンドロビンを多段構成
とし、前記ラウンドロビン各々への入力本数を必要な時
間内に十分処理可能な数として前記ラウンドロビン各々
へのトラフィックの平均化を行うようにしたことを特徴
とするアービトレーション方法。 - 【請求項８】 前記ラウンドロビン各々は、該当するキ
ューにセルが蓄積されていない時には次のキューへ権利
を移すようにしたことを特徴とする請求項７記載のアー
ビトレーション方法。 - 【請求項９】 前記ラウンドロビン各々は、配下のキュ
ー及び配下のラウンドロビンから自回路へと入力される
予定のセルレートの情報を持つようにしたことを特徴と
する請求項７または請求項８記載のアービトレーション
方法。 - 【請求項１０】 前記ラウンドロビン各々は、配下がラ
ウンドロビンの場合に当該配下のラウンドロビンの中で
最も入力レートが低いラウンドロビン及び２番目にレー
トが低いラウンドロビンの情報を持つようにしたことを
特徴とする請求項９記載のアービトレーション方法。 - 【請求項１１】 前記ラウンドロビン各々が持つ情報は
コネクションを張る際に申請される情報を基に作成する
ようにしたことを特徴とする請求項９または請求項１０
記載のアービトレーション方法。 - 【請求項１２】 前記コネクションが新たに張られる場
合に、配下のラウンドロビンの中でもっとも低い入力レ
ートのラウンドロビンを順次選択し、最終段のラウンド
ロビンの配下にキューを配置するようにしたことを特徴
とする請求項１１記載のアービトレーション方法。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000277412A JP3570366B2 (ja) | 2000-09-13 | 2000-09-13 | アービタ回路及びそれに用いる出力セルのアービトレーション方法 |
| US09/946,472 US7065049B2 (en) | 2000-09-13 | 2001-09-06 | Arbitration method and arbiter circuit |
| US11/380,557 US7817548B2 (en) | 2000-09-13 | 2006-04-27 | Traffic arbitration |
| US12/869,584 US8705358B2 (en) | 2000-09-13 | 2010-08-26 | Traffic arbitration |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000277412A JP3570366B2 (ja) | 2000-09-13 | 2000-09-13 | アービタ回路及びそれに用いる出力セルのアービトレーション方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2002094522A true JP2002094522A (ja) | 2002-03-29 |
| JP3570366B2 JP3570366B2 (ja) | 2004-09-29 |
Family
ID=18762743
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000277412A Expired - Fee Related JP3570366B2 (ja) | 2000-09-13 | 2000-09-13 | アービタ回路及びそれに用いる出力セルのアービトレーション方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (3) | US7065049B2 (ja) |
| JP (1) | JP3570366B2 (ja) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3570366B2 (ja) * | 2000-09-13 | 2004-09-29 | 日本電気株式会社 | アービタ回路及びそれに用いる出力セルのアービトレーション方法 |
| US20070174529A1 (en) * | 2005-12-29 | 2007-07-26 | Intel Corporation | Queue manager having a multi-level arbitrator |
| US8331392B2 (en) * | 2006-05-17 | 2012-12-11 | Telefonaktiebolaget Lm Ericsson (Publ) | Method and device for allocation of transmission rate in a radio telecommunication network |
| US8909462B2 (en) | 2011-07-07 | 2014-12-09 | International Business Machines Corporation | Context-based traffic flow control |
Family Cites Families (32)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5130983A (en) * | 1990-03-27 | 1992-07-14 | Heffner Iii Horace W | Method of polling to determine service needs and the like |
| US5301333A (en) * | 1990-06-14 | 1994-04-05 | Bell Communications Research, Inc. | Tree structured variable priority arbitration implementing a round-robin scheduling policy |
| US5265207A (en) * | 1990-10-03 | 1993-11-23 | Thinking Machines Corporation | Parallel computer system including arrangement for transferring messages from a source processor to selected ones of a plurality of destination processors and combining responses |
| US5325356A (en) * | 1992-05-20 | 1994-06-28 | Xerox Corporation | Method for aggregating ports on an ATM switch for the purpose of trunk grouping |
| JP2797989B2 (ja) | 1994-12-21 | 1998-09-17 | 日本電気株式会社 | セルトラヒックシェーパ |
| JPH10224364A (ja) | 1997-02-10 | 1998-08-21 | Fujitsu Ltd | Ａｔｍ交換機 |
| US6046982A (en) * | 1997-03-18 | 2000-04-04 | Cabletron Systems, Inc. | Method and apparatus for reducing data loss in data transfer devices |
| JP3805880B2 (ja) | 1997-12-25 | 2006-08-09 | 株式会社東芝 | Ａｔｍ中継装置 |
| US6198723B1 (en) * | 1998-04-14 | 2001-03-06 | Paxonet Communications, Inc. | Asynchronous transfer mode traffic shapers |
| US7177308B2 (en) * | 1998-07-22 | 2007-02-13 | Synchrodyne Networks, Inc. | Switching methods with common time reference and plurality of time frame durations |
| DE19851780A1 (de) * | 1998-11-10 | 2000-05-11 | Will E C H Gmbh & Co | Vorrichtung zum Ausschleusen von Blattlagen aus einer Förderlinie |
| JP3684308B2 (ja) * | 1998-12-15 | 2005-08-17 | 富士通株式会社 | スケジューリング制御装置および交換機 |
| US6556578B1 (en) * | 1999-04-14 | 2003-04-29 | Lucent Technologies Inc. | Early fair drop buffer management method |
| US6556571B1 (en) * | 1999-05-25 | 2003-04-29 | Nec Usa, Inc. | Fast round robin priority port scheduler for high capacity ATM switches |
| JP2001016206A (ja) | 1999-06-28 | 2001-01-19 | Nec Corp | 帯域共有制御装置 |
| JP3570366B2 (ja) * | 2000-09-13 | 2004-09-29 | 日本電気株式会社 | アービタ回路及びそれに用いる出力セルのアービトレーション方法 |
| US20020100135A1 (en) * | 2000-10-31 | 2002-08-01 | Kevin Machesky | Squeegee having at least one tapered end |
| US7046661B2 (en) * | 2000-11-20 | 2006-05-16 | Polytechnic University | Scheduling the dispatch of cells in non-empty virtual output queues of multistage switches using a pipelined hierarchical arbitration scheme |
| US7103056B2 (en) * | 2000-11-20 | 2006-09-05 | Polytechnic University | Scheduling the dispatch of cells in multistage switches using a hierarchical arbitration scheme for matching non-empty virtual output queues of a module with outgoing links of the module |
| US7173931B2 (en) * | 2000-11-20 | 2007-02-06 | Hung-Hsiang Jonathan Chao | Scheduling the dispatch of cells in multistage switches |
| US6940851B2 (en) * | 2000-11-20 | 2005-09-06 | Polytechnic University | Scheduling the dispatch of cells in non-empty virtual output queues of multistage switches using a pipelined arbitration scheme |
| EP1215931B1 (en) * | 2000-12-14 | 2006-10-11 | Lucent Technologies Inc. | Distributed scheduler for packet switches and passive optical networks |
| US7023840B2 (en) * | 2001-02-17 | 2006-04-04 | Alcatel | Multiserver scheduling system and method for a fast switching element |
| US6553571B1 (en) * | 2002-01-29 | 2003-04-29 | Wilson Sporting Goods Co. | Baseball glove with finger wrap |
| US7283558B2 (en) * | 2002-06-04 | 2007-10-16 | Lucent Technologies Inc. | Distributed weighted fair arbitration and forwarding |
| JPWO2003104886A1 (ja) * | 2002-06-11 | 2005-10-13 | 古河電気工業株式会社 | 波長分割多重光再生システム及び波長分割多重光再生方法 |
| US7463703B2 (en) * | 2003-04-14 | 2008-12-09 | Bae Systems Information And Electronic Systems Integration Inc | Joint symbol, amplitude, and rate estimator |
| US20040210688A1 (en) * | 2003-04-21 | 2004-10-21 | Becker Matthew E. | Aggregating data |
| US7688815B2 (en) * | 2003-08-18 | 2010-03-30 | BarracudaNetworks Inc | Method and system for a multi-stage interconnect switch |
| US7590102B2 (en) * | 2005-01-27 | 2009-09-15 | Intel Corporation | Multi-stage packet switching system |
| US7519054B2 (en) * | 2005-01-27 | 2009-04-14 | Intel Corporation | Replication of multicast data packets in a multi-stage switching system |
| TWI343190B (en) * | 2007-12-21 | 2011-06-01 | Univ Nat Chiao Tung | Method and apparatus of multi-stage network for iterative decoding |
-
2000
- 2000-09-13 JP JP2000277412A patent/JP3570366B2/ja not_active Expired - Fee Related
-
2001
- 2001-09-06 US US09/946,472 patent/US7065049B2/en not_active Expired - Fee Related
-
2006
- 2006-04-27 US US11/380,557 patent/US7817548B2/en not_active Expired - Fee Related
-
2010
- 2010-08-26 US US12/869,584 patent/US8705358B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US7065049B2 (en) | 2006-06-20 |
| JP3570366B2 (ja) | 2004-09-29 |
| US8705358B2 (en) | 2014-04-22 |
| US7817548B2 (en) | 2010-10-19 |
| US20020031138A1 (en) | 2002-03-14 |
| US20060193324A1 (en) | 2006-08-31 |
| US20110019548A1 (en) | 2011-01-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Mekkittikul et al. | A practical scheduling algorithm to achieve 100% throughput in input-queued switches | |
| US9781060B2 (en) | Crossbar switch and recursive scheduling | |
| JP4879382B2 (ja) | パケットスイッチ、スケジューリング装置、廃棄制御回路、マルチキャスト制御回路、およびＱｏＳ制御装置 | |
| US7400629B2 (en) | CAM based system and method for re-sequencing data packets | |
| US20030035422A1 (en) | Packet switching | |
| JPH06112940A (ja) | パケット通信ネットワーク | |
| WO1996000487A1 (en) | System and method for providing multiple loss and service priorities | |
| WO1996000474A1 (en) | Packet processor having service priority and loss priority features | |
| CN110768829B (zh) | 一种基于dpdk实现流量分析业务性能线性增长的方法 | |
| US20040083326A1 (en) | Switch scheduling algorithm | |
| Bianco et al. | Frame-based matching algorithms for input-queued switches | |
| Hu et al. | On iterative scheduling for input-queued switches with a speedup of $2-1/N$ | |
| JPH1174909A (ja) | 資源を共有するシステムにおけるサービス要求受付管理方法 | |
| Lee et al. | Queueing system with multiple delay and loss priorities for ATM networks | |
| US20110134933A1 (en) | Classes of service for network on chips | |
| JP2002094522A (ja) | アービタ回路及びそれに用いる出力セルのアービトレーション方法 | |
| US20070127514A1 (en) | Packets switching system for telecommunication network node | |
| JP2002237839A (ja) | スケジューリング方法及びその装置 | |
| CN112491736A (zh) | 一种拥塞控制方法、装置、电子设备及存储介质 | |
| WO2021002022A1 (ja) | 通信装置、通信方法及びプログラム | |
| EP2209270A1 (en) | Method and apparatus for frame-aware and pipelined hierarchical scheduling | |
| JP3906231B2 (ja) | パケット転送装置 | |
| US7477596B1 (en) | Policing engine providing dynamic adjustment of peak and sustained data cell rates and efficient transfer of AAL5 cells | |
| Kesselman et al. | Best effort and priority queuing policies for buffered crossbar switches | |
| JPH08237282A (ja) | Ａｔｍセルの優先制御装置および輻輳制御方法および輻輳制御装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20031202 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040202 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040224 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040405 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040601 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040614 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313111 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070702 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080702 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090702 Year of fee payment: 5 |
|
| LAPS | Cancellation because of no payment of annual fees |