JP3662859B2 - パケット中継装置 - Google Patents
パケット中継装置 Download PDFInfo
- Publication number
- JP3662859B2 JP3662859B2 JP2001161320A JP2001161320A JP3662859B2 JP 3662859 B2 JP3662859 B2 JP 3662859B2 JP 2001161320 A JP2001161320 A JP 2001161320A JP 2001161320 A JP2001161320 A JP 2001161320A JP 3662859 B2 JP3662859 B2 JP 3662859B2
- Authority
- JP
- Japan
- Prior art keywords
- packet
- random number
- field
- buffer
- uniform
- 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.)
- Expired - Fee Related
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
この発明は、蓄積中継方式によりパケットを中継するパケット中継装置に関するものである。
【０００２】
【従来の技術】
パケット中継装置におけるパケット送信待ちキューの輻輳回避のため、送信待ちキューの蓄積データ量に応じて確率的にパケットを廃棄、もしくはマークするアルゴリズムとして、ＲＥＤ（Random Early Detection）と称されるものが提案されている（S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance, ACM/IEEE Transactions on Networking, 1（4）: 397-413, 1993.）。こうしたアルゴリズムにおいては、パケットの廃棄やマークのための確率計算を実行する場合に乱数を生成する必要がある。このため、ＲＥＤのように確率計算を伴うアルゴリズムを実装するパケット中継装置では、送信待ちキューにパケットが到着する毎に動的に確率計算に必要な乱数を生成するのが一般的である。
【０００３】
【発明が解決しようとする課題】
ところで、上述した乱数の生成がプログラムによる場合には、乱数の精度によって異なるものにはなるものの、少なくとも数ステップの四則演算を含む一様乱数生成関数を実行する必要があり、パケット中継に伴う処理負荷増大の一因となる。こうした処理負荷増大の問題を解決するには、例えば特許第３０７４１０７号公報に示されているような専用の確率変数発生装置を適用し、ハードウェアによって乱数の生成を行うことが考えられる。
【０００４】
図５は、この種の確率変数発生装置の構成例を示したブロック図である。図５において、１０１は時間信号発生手段、１０２は一様乱数発生手段、１０３は記憶手段、１０４は四則演算手段、１０５は定数発生手段、１１０はこれらを含む確率変数発生装置である。この確率変数発生装置１１０は、一様乱数発生手段１０２の出力を、記憶手段１０３に記憶された所望の確率分布の累積度関数値を参照して変換し、四則演算手段１０４を経由して出力することで所望の確率分布に従う確率変数を適切なタイミングで発生するものであり、このタイミングを得るための時間信号発生手段１０１や四則演算手段１０４に定数を供給するための定数発生手段１０５を含んでいる。
【０００５】
上記のような確率変数発生装置１１０を内蔵するパケット中継装置によれば、ハードウェアによって乱数を生成するようにしているため、パケット中継に伴う処理負荷の増大を招来することがない。
【０００６】
しかしながら、こうしたハードウェアによって乱数を生成する場合には、図５に示したすべての構成や機構が必ずしも必要となることはないにせよ、最小限の構成や機構をパケット中継装置に内蔵させる必要がある。この結果、パケット中継装置の構成が複雑になるとともに、製造コストを増大することになる。
【０００７】
この発明は上記実情に鑑みてなされたもので、構成の複雑化およびコスト増を招来することなくパケット中継に伴う処理負荷の低減を図ることのできるパケット中継装置を得ることを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、この発明にかかるパケット中継装置は、パケットを格納するためのパケットバッファを初期化する際に一様乱数を発生させて該パケットバッファの各パケット格納フィールドに付随するフィールドに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに附随するフィールドの値を読み出してこれを乱数として用いることを特徴とする。
【０００９】
この発明によれば、パケットを格納したパケット格納フィールドに付随する乱数フィールドを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１０】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記パケット格納フィールドに付随するフィールドに格納した一様乱数を更新することを特徴とする。
【００１１】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってパケット格納フィールドに付随するフィールドに格納した一様乱数の値が更新される。
【００１２】
つぎの発明にかかるパケット中継装置は、パケットを格納するためのパケットバッファを初期化する際に、パケット格納フィールドと１対１に対応付けられたエントリを有する乱数テーブルを生成するとともに、一様乱数を発生させて該乱数テーブルのエントリに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに対応するエントリの値を読み出してこれを乱数として用いることを特徴とする。
【００１３】
この発明によれば、パケットを格納したパケット格納フィールドに簡単な規則で対応付けた乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１４】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記乱数テーブルのエントリに格納した一様乱数を更新することを特徴とする。
【００１５】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って乱数テーブルのエントリに格納した一様乱数が更新される。
【００１６】
つぎの発明にかかるパケット中継装置は、上記の発明において、前記パケットバッファに、各バッファ格納フィールドに付随するポインタフィールドを設けるとともに、該ポインタフィールドに格納したポインタの値に従って前記バッファ格納フィールドを前記乱数テーブルのエントリに１対１に対応付けたことを特徴とする。
【００１７】
この発明によれば、パケットを格納したパケット格納フィールドに付随するポインタフィールドから指示された乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１８】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って前記ポインタフィールドに格納したポインタの値を更新することを特徴とする。
【００１９】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってポインタフィールドに格納したポインタの値が更新される。
【００２０】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかるパケット中継装置の好適な実施の形態を詳細に説明する。
【００２１】
実施の形態１．
図１は、この発明に実施の形態１であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有するとともに、各パケット格納フィールド１１−１〜１１−ｎに付随して乱数を格納するｎ個の乱数フィールド１２−１〜１２−ｎを有している。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数をパケットバッファ１０の乱数フィールド１２−１〜１２−ｎにそれぞれ与える部分である。これは、例えばパケットバッファ１０の乱数フィールド１２−１〜１２−ｎとして８ビットのメモリ領域を用いる場合であれば、０〜２５５の範囲の値を同等の確率で生じるような一様乱数生成関数をプログラムし、パケットバッファ１０の初期化時にこの関数を起動して出力される値を乱数フィールド１２−１〜１２−ｎに格納することで実現することができる。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００２２】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により、乱数発生部２０において一様乱数を発生し、該一様乱数をパケットバッファ１０の各乱数フィールド１２−１〜１２−ｎに格納する処理を実施する。
【００２３】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１を割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００２４】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００２５】
この場合、本実施の形態１においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに附随する乱数フィールド１２−１〜１２−ｎの一様乱数値を用いる。乱数フィールド１２−１〜１２−ｎから読み出した値を乱数と見なすことができる理由は以下の通りである。すなわち、通常多くの端末が独立に送信したパケットをパケット中継装置が受信した場合、該パケット中継装置は、受信パケットの内容に依存することなく空いているパケット格納フィールド１１−１〜１１−ｎを任意に割り当てる。つまり、受信パケットをパケットバッファ１０のどのパケット格納フィールド１１−１〜１１−ｎに割り当てるかは、ランダムと見なすことができる。従って、パケットバッファ１０の初期化時にのみ乱数発生部２０において発生した一様乱数をパケットバッファ１０の乱数フィールド１２−１〜１２−ｎに格納する処理を実施し、その後、パケット格納フィールド１１−１〜１１−ｎに附随する乱数フィールド１２−１〜１２−ｎの値がパケット毎に都度変化しない場合であっても、パケット中継装置が受信する一連のパケットに対しそれらが格納されるパケットバッファ１０に附随する乱数フィールド１２−１〜１２−ｎを読み出して得られた値をランダムな数値列と見なすことができる。
【００２６】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随する乱数フィールド１２−１〜１２−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、唯一乱数発生部２０を設けるだけであり、図５に示した専用の確率変数発生装置、つまり時間信号発生部１０１、一様乱数発生部１０２、記憶部１０３、四則演算部１０４、定数発生部１０５等々、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００２７】
なお、上述した実施の形態１では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０のキューフィールド３１−１〜３１−ｍに転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、各パケットバッファのパケット格納フィールドにそれぞれ乱数フィールドを附随させ、パケット受信時にパケットを格納するパケットバッファ、つまり第１段となるパケットバッファのパケット格納フィールドに附随する乱数フィールドから得られる乱数値を順次コピーするようにしてもよい。あるいは、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、この最終段となるパケットバッファにのみ乱数フィールドを設けてその初期化時に各パケット格納フィールドに付随する乱数フィールドに一様乱数を格納するようにしてもよい。
【００２８】
また、上述した実施の形態１では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数フィールド１２−１〜１２−ｎに格納し直すことも可能である。このようにして乱数フィールド１２−１〜１２−ｎの値を更新した場合には、乱数フィールド１２−１〜１２−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００２９】
実施の形態２．
図２は、この発明に実施の形態２であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数テーブル５０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有している。乱数テーブル５０は、ｎ個のエントリ５１−１〜５１−ｎを有したもので、各エントリ５１−１〜５１−ｎが１対１の対応関係を与える簡単な規則でパケットバッファ１０の各パケット格納フィールド１１−１〜１１−ｎに対応付けてある。本実施の形態２においては、図３に示すような態様で、パケットバッファ１０の各パケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０の各エントリ５１−１〜５１−ｎとに１対１の対応関係を与えるようにしている。すなわち、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎにそれぞれ個々の位置を示す添字ｉを順次付すとともに、乱数テーブル５０のエントリ５１−１〜５１−ｎにそれぞれ個々の位置を示す添字ｉを順次付し、これらの添字ｉが同一となるものを互いに対応付けるようにしている。なお、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応関係は、必ずしもこれに限らず、両者が１対１に対応すれば、他の規則を用いても構わない。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎにそれぞれ与える部分である。これは、例えば乱数テーブル５０のエントリ５１−１〜５１−ｎが８ビットの長さを有するものであれば、０〜２５５の範囲の値を同等の確率で生じるような一様乱数生成関数をプログラムし、パケットバッファ１０の初期化時にこの関数を起動して出力される値をエントリ５１−１〜５１−ｎに格納することで実現することができる。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００３０】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により乱数発生部２０において一様乱数を発生し、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎに格納する処理を実施する。
【００３１】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１を割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００３２】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００３３】
この場合、本実施の形態２においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに簡単な規則で対応付けたエントリ５１−１〜５１−ｎの一様乱数値を用いる。乱数テーブル５０のエントリ５１−１〜５１−ｎから読み出した値を乱数と見なすことができる理由は実施の形態１と同様である。
【００３４】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに簡単な規則で対応付けた乱数テーブル５０のエントリ５１−１〜５１−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、乱数発生部２０および乱数テーブル５０を設けるだけであり、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００３５】
なお、上述した実施の形態２では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０のキューフィールド３１−１〜３１−ｍに転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、該最終段となるパケットバッファにのみ対応する乱数テーブルを設け、最終段となるパケットバッファの初期化時に、各パケット格納フィールドに対応付けた乱数テーブルのエントリに一様乱数を格納してもよい。
【００３６】
また、上述した実施の形態２では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数テーブル５０のエントリ５１−１〜５１−ｎに格納し直すことも可能である。このようにして乱数テーブル５０の値を更新した場合には、エントリ５１−１〜５１−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００３７】
実施の形態３．
図４は、この発明に実施の形態３であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数テーブル５０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有するとともに、各パケット格納フィールド１１−１〜１１−ｎに付随してポインタを格納するｎ個のポインタフィールド１３−１〜１３−ｎを有している。乱数テーブル５０は、ｎ個のエントリ５１−１〜５１−ｎを有したものである。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎやパケットバッファ１０のポインタフィールド１３−１〜１３−ｎに与える部分である。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００３８】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により乱数発生部２０において一様乱数を発生し、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎに格納する処理を実施する。さらに、パケット中継装置は、図中の矢印で示すように、パケットバッファ１０のポインタフィールド１３−１〜１３−ｎに、乱数テーブル５０のエントリ５１−１〜５１−ｎを１対１に指示するポインタを格納する。これらのポインタは、例えばポインタフィールド１３−１〜１３−ｎに対して乱数発生部２０により一様乱数を発生させ、これによって得た値ｊを用いてｊ番目のエントリ５１−１〜５１−ｎを対応付ける。次のポインタフィールド１３−１〜１３−ｎに対しては、再び乱数発生部２０により一様乱数を発生させ、これによって得た値ｋ（≠ｊ）を用いてｋ番目のエントリ５１−１〜５１−ｎを対応付ける。以下同様にしてランダムな手順により設定することができる。なお、ポインタによるポインタフィールド１３−１〜１３−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応付けは、必ずしも上述した手順に限らず、例えばｉ番目のポインタフィールド１３−１〜１３−ｎに対してｉ番目のエントリ５１−１〜５１−ｎを対応させるといった、ランダムでない手順を用いることも可能である。
【００３９】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１〜１１−ｎを割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００４０】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００４１】
この場合、本実施の形態３においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随するポインタフィールド１３−１〜１３−ｎからポインタによって指示された乱数テーブル５０のエントリ５１−１〜５１−ｎの一様乱数値を用いる。乱数テーブル５０のエントリ５１−１〜５１−ｎから読み出した値を乱数と見なすことができる理由は実施の形態１と同様である。
【００４２】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随するポインタフィールド１３−１〜１３−ｎから指示された乱数テーブル５０のエントリ５１−１〜５１−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、乱数発生部２０および乱数テーブル５０を設けるだけであり、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００４３】
なお、上述した実施の形態３では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０に転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、該最終段となるパケットバッファにのみポインタフィールドを設けるとともに、対応する乱数テーブルを設け、最終段となるパケットバッファの初期化時に、各パケット格納フィールドに対応付けた乱数テーブルのエントリ一様乱数を格納してもよい。
【００４４】
また、上述した実施の形態３では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数テーブル５０のエントリ５１−１〜５１−ｎに格納し直すことも可能である。このようにして乱数テーブル５０の値を更新した場合には、エントリ５１−１〜５１−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００４５】
さらに、上述した実施の形態３では、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様のランダムな手順を用いて乱数テーブル５０のエントリ５１−１〜５１−ｎとの１対１の対応関係を保ちつつ、ポインタフィールド１３−１〜１３−ｎのポインタを格納し直すことも可能である。このようにしてポインタフィールド１３−１〜１３−ｎのポインタを更新した場合、つまりパケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応付けを更新した場合には、ポインタフィールド１３−１〜１３−ｎのポインタがパケット毎には変化しないことに起因する乱数値の偏りを軽減することができる。
【００４６】
【発明の効果】
以上説明したように、この発明によれば、パケットを格納したパケット格納フィールドに付随する乱数フィールドを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００４７】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってパケット格納フィールドに付随するフィールドに格納した一様乱数の値が更新されるため、パケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００４８】
つぎの発明によれば、パケットを格納したパケット格納フィールドに簡単な規則で対応付けた乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００４９】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って乱数テーブルのエントリに格納した一様乱数が更新されるため、パケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００５０】
つぎの発明によれば、パケットを格納したパケット格納フィールドに付随するポインタフィールドから指示された乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００５１】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってポインタフィールドに格納したポインタの値が更新されるため、ポインタフィールドのポインタがパケット毎には変化しないことに起因する乱数値の偏りを軽減することができる。
【図面の簡単な説明】
【図１】 この発明に実施の形態１であるパケット中継装置の構成例を示すブロック図である。
【図２】 この発明に実施の形態２であるパケット中継装置の構成例を示すブロック図である。
【図３】 パケットバッファのパケット格納フィールドと乱数テーブルのエントリとの対応関係を例示する概念図である。
【図４】 図４は、この発明に実施の形態３であるパケット中継装置の構成例を示すブロック図である。
【図５】 従来のパケット中継装置に適用される確率変数発生装置の構成例を示したブロック図である。
【符号の説明】
１０ パケットバッファ、１１−１〜１１−ｎ パケット格納フィールド、１２−１〜１２−ｎ 乱数フィールド、１３−１〜１３−ｎ ポインタフィールド、２０ 乱数発生部、３０ 送信待ちキュー、３１−１〜３１−ｍ キューフィールド、４０ 中継制御部、５０ 乱数テーブル、５１−１〜５１−ｎ エントリ。
【発明の属する技術分野】
この発明は、蓄積中継方式によりパケットを中継するパケット中継装置に関するものである。
【０００２】
【従来の技術】
パケット中継装置におけるパケット送信待ちキューの輻輳回避のため、送信待ちキューの蓄積データ量に応じて確率的にパケットを廃棄、もしくはマークするアルゴリズムとして、ＲＥＤ（Random Early Detection）と称されるものが提案されている（S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance, ACM/IEEE Transactions on Networking, 1（4）: 397-413, 1993.）。こうしたアルゴリズムにおいては、パケットの廃棄やマークのための確率計算を実行する場合に乱数を生成する必要がある。このため、ＲＥＤのように確率計算を伴うアルゴリズムを実装するパケット中継装置では、送信待ちキューにパケットが到着する毎に動的に確率計算に必要な乱数を生成するのが一般的である。
【０００３】
【発明が解決しようとする課題】
ところで、上述した乱数の生成がプログラムによる場合には、乱数の精度によって異なるものにはなるものの、少なくとも数ステップの四則演算を含む一様乱数生成関数を実行する必要があり、パケット中継に伴う処理負荷増大の一因となる。こうした処理負荷増大の問題を解決するには、例えば特許第３０７４１０７号公報に示されているような専用の確率変数発生装置を適用し、ハードウェアによって乱数の生成を行うことが考えられる。
【０００４】
図５は、この種の確率変数発生装置の構成例を示したブロック図である。図５において、１０１は時間信号発生手段、１０２は一様乱数発生手段、１０３は記憶手段、１０４は四則演算手段、１０５は定数発生手段、１１０はこれらを含む確率変数発生装置である。この確率変数発生装置１１０は、一様乱数発生手段１０２の出力を、記憶手段１０３に記憶された所望の確率分布の累積度関数値を参照して変換し、四則演算手段１０４を経由して出力することで所望の確率分布に従う確率変数を適切なタイミングで発生するものであり、このタイミングを得るための時間信号発生手段１０１や四則演算手段１０４に定数を供給するための定数発生手段１０５を含んでいる。
【０００５】
上記のような確率変数発生装置１１０を内蔵するパケット中継装置によれば、ハードウェアによって乱数を生成するようにしているため、パケット中継に伴う処理負荷の増大を招来することがない。
【０００６】
しかしながら、こうしたハードウェアによって乱数を生成する場合には、図５に示したすべての構成や機構が必ずしも必要となることはないにせよ、最小限の構成や機構をパケット中継装置に内蔵させる必要がある。この結果、パケット中継装置の構成が複雑になるとともに、製造コストを増大することになる。
【０００７】
この発明は上記実情に鑑みてなされたもので、構成の複雑化およびコスト増を招来することなくパケット中継に伴う処理負荷の低減を図ることのできるパケット中継装置を得ることを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、この発明にかかるパケット中継装置は、パケットを格納するためのパケットバッファを初期化する際に一様乱数を発生させて該パケットバッファの各パケット格納フィールドに付随するフィールドに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに附随するフィールドの値を読み出してこれを乱数として用いることを特徴とする。
【０００９】
この発明によれば、パケットを格納したパケット格納フィールドに付随する乱数フィールドを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１０】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記パケット格納フィールドに付随するフィールドに格納した一様乱数を更新することを特徴とする。
【００１１】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってパケット格納フィールドに付随するフィールドに格納した一様乱数の値が更新される。
【００１２】
つぎの発明にかかるパケット中継装置は、パケットを格納するためのパケットバッファを初期化する際に、パケット格納フィールドと１対１に対応付けられたエントリを有する乱数テーブルを生成するとともに、一様乱数を発生させて該乱数テーブルのエントリに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに対応するエントリの値を読み出してこれを乱数として用いることを特徴とする。
【００１３】
この発明によれば、パケットを格納したパケット格納フィールドに簡単な規則で対応付けた乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１４】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記乱数テーブルのエントリに格納した一様乱数を更新することを特徴とする。
【００１５】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って乱数テーブルのエントリに格納した一様乱数が更新される。
【００１６】
つぎの発明にかかるパケット中継装置は、上記の発明において、前記パケットバッファに、各バッファ格納フィールドに付随するポインタフィールドを設けるとともに、該ポインタフィールドに格納したポインタの値に従って前記バッファ格納フィールドを前記乱数テーブルのエントリに１対１に対応付けたことを特徴とする。
【００１７】
この発明によれば、パケットを格納したパケット格納フィールドに付随するポインタフィールドから指示された乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１８】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って前記ポインタフィールドに格納したポインタの値を更新することを特徴とする。
【００１９】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってポインタフィールドに格納したポインタの値が更新される。
【００２０】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかるパケット中継装置の好適な実施の形態を詳細に説明する。
【００２１】
実施の形態１．
図１は、この発明に実施の形態１であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有するとともに、各パケット格納フィールド１１−１〜１１−ｎに付随して乱数を格納するｎ個の乱数フィールド１２−１〜１２−ｎを有している。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数をパケットバッファ１０の乱数フィールド１２−１〜１２−ｎにそれぞれ与える部分である。これは、例えばパケットバッファ１０の乱数フィールド１２−１〜１２−ｎとして８ビットのメモリ領域を用いる場合であれば、０〜２５５の範囲の値を同等の確率で生じるような一様乱数生成関数をプログラムし、パケットバッファ１０の初期化時にこの関数を起動して出力される値を乱数フィールド１２−１〜１２−ｎに格納することで実現することができる。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００２２】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により、乱数発生部２０において一様乱数を発生し、該一様乱数をパケットバッファ１０の各乱数フィールド１２−１〜１２−ｎに格納する処理を実施する。
【００２３】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１を割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００２４】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００２５】
この場合、本実施の形態１においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに附随する乱数フィールド１２−１〜１２−ｎの一様乱数値を用いる。乱数フィールド１２−１〜１２−ｎから読み出した値を乱数と見なすことができる理由は以下の通りである。すなわち、通常多くの端末が独立に送信したパケットをパケット中継装置が受信した場合、該パケット中継装置は、受信パケットの内容に依存することなく空いているパケット格納フィールド１１−１〜１１−ｎを任意に割り当てる。つまり、受信パケットをパケットバッファ１０のどのパケット格納フィールド１１−１〜１１−ｎに割り当てるかは、ランダムと見なすことができる。従って、パケットバッファ１０の初期化時にのみ乱数発生部２０において発生した一様乱数をパケットバッファ１０の乱数フィールド１２−１〜１２−ｎに格納する処理を実施し、その後、パケット格納フィールド１１−１〜１１−ｎに附随する乱数フィールド１２−１〜１２−ｎの値がパケット毎に都度変化しない場合であっても、パケット中継装置が受信する一連のパケットに対しそれらが格納されるパケットバッファ１０に附随する乱数フィールド１２−１〜１２−ｎを読み出して得られた値をランダムな数値列と見なすことができる。
【００２６】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随する乱数フィールド１２−１〜１２−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、唯一乱数発生部２０を設けるだけであり、図５に示した専用の確率変数発生装置、つまり時間信号発生部１０１、一様乱数発生部１０２、記憶部１０３、四則演算部１０４、定数発生部１０５等々、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００２７】
なお、上述した実施の形態１では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０のキューフィールド３１−１〜３１−ｍに転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、各パケットバッファのパケット格納フィールドにそれぞれ乱数フィールドを附随させ、パケット受信時にパケットを格納するパケットバッファ、つまり第１段となるパケットバッファのパケット格納フィールドに附随する乱数フィールドから得られる乱数値を順次コピーするようにしてもよい。あるいは、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、この最終段となるパケットバッファにのみ乱数フィールドを設けてその初期化時に各パケット格納フィールドに付随する乱数フィールドに一様乱数を格納するようにしてもよい。
【００２８】
また、上述した実施の形態１では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数フィールド１２−１〜１２−ｎに格納し直すことも可能である。このようにして乱数フィールド１２−１〜１２−ｎの値を更新した場合には、乱数フィールド１２−１〜１２−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００２９】
実施の形態２．
図２は、この発明に実施の形態２であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数テーブル５０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有している。乱数テーブル５０は、ｎ個のエントリ５１−１〜５１−ｎを有したもので、各エントリ５１−１〜５１−ｎが１対１の対応関係を与える簡単な規則でパケットバッファ１０の各パケット格納フィールド１１−１〜１１−ｎに対応付けてある。本実施の形態２においては、図３に示すような態様で、パケットバッファ１０の各パケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０の各エントリ５１−１〜５１−ｎとに１対１の対応関係を与えるようにしている。すなわち、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎにそれぞれ個々の位置を示す添字ｉを順次付すとともに、乱数テーブル５０のエントリ５１−１〜５１−ｎにそれぞれ個々の位置を示す添字ｉを順次付し、これらの添字ｉが同一となるものを互いに対応付けるようにしている。なお、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応関係は、必ずしもこれに限らず、両者が１対１に対応すれば、他の規則を用いても構わない。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎにそれぞれ与える部分である。これは、例えば乱数テーブル５０のエントリ５１−１〜５１−ｎが８ビットの長さを有するものであれば、０〜２５５の範囲の値を同等の確率で生じるような一様乱数生成関数をプログラムし、パケットバッファ１０の初期化時にこの関数を起動して出力される値をエントリ５１−１〜５１−ｎに格納することで実現することができる。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００３０】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により乱数発生部２０において一様乱数を発生し、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎに格納する処理を実施する。
【００３１】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１を割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００３２】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００３３】
この場合、本実施の形態２においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに簡単な規則で対応付けたエントリ５１−１〜５１−ｎの一様乱数値を用いる。乱数テーブル５０のエントリ５１−１〜５１−ｎから読み出した値を乱数と見なすことができる理由は実施の形態１と同様である。
【００３４】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに簡単な規則で対応付けた乱数テーブル５０のエントリ５１−１〜５１−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、乱数発生部２０および乱数テーブル５０を設けるだけであり、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００３５】
なお、上述した実施の形態２では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０のキューフィールド３１−１〜３１−ｍに転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、該最終段となるパケットバッファにのみ対応する乱数テーブルを設け、最終段となるパケットバッファの初期化時に、各パケット格納フィールドに対応付けた乱数テーブルのエントリに一様乱数を格納してもよい。
【００３６】
また、上述した実施の形態２では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数テーブル５０のエントリ５１−１〜５１−ｎに格納し直すことも可能である。このようにして乱数テーブル５０の値を更新した場合には、エントリ５１−１〜５１−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００３７】
実施の形態３．
図４は、この発明に実施の形態３であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数テーブル５０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有するとともに、各パケット格納フィールド１１−１〜１１−ｎに付随してポインタを格納するｎ個のポインタフィールド１３−１〜１３−ｎを有している。乱数テーブル５０は、ｎ個のエントリ５１−１〜５１−ｎを有したものである。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎやパケットバッファ１０のポインタフィールド１３−１〜１３−ｎに与える部分である。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００３８】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により乱数発生部２０において一様乱数を発生し、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎに格納する処理を実施する。さらに、パケット中継装置は、図中の矢印で示すように、パケットバッファ１０のポインタフィールド１３−１〜１３−ｎに、乱数テーブル５０のエントリ５１−１〜５１−ｎを１対１に指示するポインタを格納する。これらのポインタは、例えばポインタフィールド１３−１〜１３−ｎに対して乱数発生部２０により一様乱数を発生させ、これによって得た値ｊを用いてｊ番目のエントリ５１−１〜５１−ｎを対応付ける。次のポインタフィールド１３−１〜１３−ｎに対しては、再び乱数発生部２０により一様乱数を発生させ、これによって得た値ｋ（≠ｊ）を用いてｋ番目のエントリ５１−１〜５１−ｎを対応付ける。以下同様にしてランダムな手順により設定することができる。なお、ポインタによるポインタフィールド１３−１〜１３−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応付けは、必ずしも上述した手順に限らず、例えばｉ番目のポインタフィールド１３−１〜１３−ｎに対してｉ番目のエントリ５１−１〜５１−ｎを対応させるといった、ランダムでない手順を用いることも可能である。
【００３９】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１〜１１−ｎを割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００４０】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００４１】
この場合、本実施の形態３においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随するポインタフィールド１３−１〜１３−ｎからポインタによって指示された乱数テーブル５０のエントリ５１−１〜５１−ｎの一様乱数値を用いる。乱数テーブル５０のエントリ５１−１〜５１−ｎから読み出した値を乱数と見なすことができる理由は実施の形態１と同様である。
【００４２】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随するポインタフィールド１３−１〜１３−ｎから指示された乱数テーブル５０のエントリ５１−１〜５１−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、乱数発生部２０および乱数テーブル５０を設けるだけであり、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００４３】
なお、上述した実施の形態３では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０に転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、該最終段となるパケットバッファにのみポインタフィールドを設けるとともに、対応する乱数テーブルを設け、最終段となるパケットバッファの初期化時に、各パケット格納フィールドに対応付けた乱数テーブルのエントリ一様乱数を格納してもよい。
【００４４】
また、上述した実施の形態３では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数テーブル５０のエントリ５１−１〜５１−ｎに格納し直すことも可能である。このようにして乱数テーブル５０の値を更新した場合には、エントリ５１−１〜５１−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００４５】
さらに、上述した実施の形態３では、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様のランダムな手順を用いて乱数テーブル５０のエントリ５１−１〜５１−ｎとの１対１の対応関係を保ちつつ、ポインタフィールド１３−１〜１３−ｎのポインタを格納し直すことも可能である。このようにしてポインタフィールド１３−１〜１３−ｎのポインタを更新した場合、つまりパケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応付けを更新した場合には、ポインタフィールド１３−１〜１３−ｎのポインタがパケット毎には変化しないことに起因する乱数値の偏りを軽減することができる。
【００４６】
【発明の効果】
以上説明したように、この発明によれば、パケットを格納したパケット格納フィールドに付随する乱数フィールドを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００４７】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってパケット格納フィールドに付随するフィールドに格納した一様乱数の値が更新されるため、パケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００４８】
つぎの発明によれば、パケットを格納したパケット格納フィールドに簡単な規則で対応付けた乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００４９】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って乱数テーブルのエントリに格納した一様乱数が更新されるため、パケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００５０】
つぎの発明によれば、パケットを格納したパケット格納フィールドに付随するポインタフィールドから指示された乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００５１】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってポインタフィールドに格納したポインタの値が更新されるため、ポインタフィールドのポインタがパケット毎には変化しないことに起因する乱数値の偏りを軽減することができる。
【図面の簡単な説明】
【図１】 この発明に実施の形態１であるパケット中継装置の構成例を示すブロック図である。
【図２】 この発明に実施の形態２であるパケット中継装置の構成例を示すブロック図である。
【図３】 パケットバッファのパケット格納フィールドと乱数テーブルのエントリとの対応関係を例示する概念図である。
【図４】 図４は、この発明に実施の形態３であるパケット中継装置の構成例を示すブロック図である。
【図５】 従来のパケット中継装置に適用される確率変数発生装置の構成例を示したブロック図である。
【符号の説明】
１０ パケットバッファ、１１−１〜１１−ｎ パケット格納フィールド、１２−１〜１２−ｎ 乱数フィールド、１３−１〜１３−ｎ ポインタフィールド、２０ 乱数発生部、３０ 送信待ちキュー、３１−１〜３１−ｍ キューフィールド、４０ 中継制御部、５０ 乱数テーブル、５１−１〜５１−ｎ エントリ。
Claims (6)
- パケットを格納するためのパケットバッファを初期化する際に一様乱数を発生させて該パケットバッファの各パケット格納フィールドに付随するフィールドに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに附随するフィールドの値を読み出してこれを乱数として用いることを特徴とするパケット中継装置。
- パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記パケット格納フィールドに付随するフィールドに格納した一様乱数を更新することを特徴とする請求項１に記載のパケット中継装置。
- パケットを格納するためのパケットバッファを初期化する際に、パケット格納フィールドと１対１に対応付けられたエントリを有する乱数テーブルを生成するとともに、一様乱数を発生させて該乱数テーブルのエントリに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに対応するエントリの値を読み出してこれを乱数として用いることを特徴とするパケット中継装置。
- パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記乱数テーブルのエントリに格納した一様乱数を更新することを特徴とする請求項３に記載のパケット中継装置。
- 前記パケットバッファに、各バッファ格納フィールドに付随するポインタフィールドを設けるとともに、該ポインタフィールドに格納したポインタの値に従って前記バッファ格納フィールドを前記乱数テーブルのエントリに１対１に対応付けたことを特徴とする請求項３または４に記載のパケット中継装置。
- パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って前記ポインタフィールドに格納したポインタの値を更新することを特徴とする請求項５に記載のパケット中継装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001161320A JP3662859B2 (ja) | 2001-05-29 | 2001-05-29 | パケット中継装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001161320A JP3662859B2 (ja) | 2001-05-29 | 2001-05-29 | パケット中継装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2002354026A JP2002354026A (ja) | 2002-12-06 |
| JP3662859B2 true JP3662859B2 (ja) | 2005-06-22 |
Family
ID=19004618
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001161320A Expired - Fee Related JP3662859B2 (ja) | 2001-05-29 | 2001-05-29 | パケット中継装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3662859B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100443556B1 (ko) * | 2001-11-30 | 2004-08-09 | 주식회사 네오텍리서치 | 신호전달의 불확정성을 최소화하기 위한 배선 회로 |
-
2001
- 2001-05-29 JP JP2001161320A patent/JP3662859B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2002354026A (ja) | 2002-12-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3532037B2 (ja) | 並列計算機 | |
| US6553031B1 (en) | Communication node apparatus with routing tables in cache memories | |
| JP4154213B2 (ja) | パケット処理装置 | |
| WO1996034479A1 (en) | Packet switching engine | |
| SK62193A3 (en) | Packet switch | |
| US7089407B2 (en) | Packet processing device processing input packet data in a packet routing device | |
| US20010028659A1 (en) | Data switching arbitration arrangements | |
| US7174394B1 (en) | Multi processor enqueue packet circuit | |
| CN111310908A (zh) | 深度神经网络硬件加速器与其操作方法 | |
| JP3662859B2 (ja) | パケット中継装置 | |
| WO1999029071A1 (en) | Resource sharing | |
| US20110149985A1 (en) | Data processing apparatus and method of controlling the same | |
| US5535413A (en) | System including plurality of data driven processors connected to each other | |
| US6912566B1 (en) | Memory device and method for operating the memory device | |
| CN111832048B (zh) | 一种基于双端口ram的数据包排序方法和系统 | |
| US7076517B2 (en) | Serial communication device with dynamic filter allocation | |
| EP1279260A2 (en) | Memory management with data discard | |
| CA2241683A1 (en) | Switching apparatus | |
| US7219211B1 (en) | Precompute logic for software packet processing | |
| JPH09282287A (ja) | 通信処理システム | |
| JP2000299686A (ja) | スケジューリング装置 | |
| US7032049B2 (en) | Apparatus for relaying received interrupt requests | |
| US6807594B1 (en) | Randomized arbiters for eliminating congestion | |
| US7161908B2 (en) | Deterministic bandwidth throttling to facilitate operation of a control unit | |
| JPH10341240A (ja) | 交換装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050304 |
|
| 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: 20050322 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050324 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080401 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090401 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100401 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100401 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110401 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120401 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120401 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130401 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130401 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140401 Year of fee payment: 9 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |