JP3662859B2

JP3662859B2 - Packet relay device

Info

Publication number: JP3662859B2
Application number: JP2001161320A
Authority: JP
Inventors: 尚一郎妹尾; 貞利中村
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 2001-05-29
Filing date: 2001-05-29
Publication date: 2005-06-22
Anticipated expiration: 2021-05-29
Also published as: JP2002354026A

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.）。こうしたアルゴリズムにおいては、パケットの廃棄やマークのための確率計算を実行する場合に乱数を生成する必要がある。このため、ＲＥＤのように確率計算を伴うアルゴリズムを実装するパケット中継装置では、送信待ちキューにパケットが到着する毎に動的に確率計算に必要な乱数を生成するのが一般的である。
【０００３】
【発明が解決しようとする課題】
ところで、上述した乱数の生成がプログラムによる場合には、乱数の精度によって異なるものにはなるものの、少なくとも数ステップの四則演算を含む一様乱数生成関数を実行する必要があり、パケット中継に伴う処理負荷増大の一因となる。こうした処理負荷増大の問題を解決するには、例えば特許第３０７４１０７号公報に示されているような専用の確率変数発生装置を適用し、ハードウェアによって乱数の生成を行うことが考えられる。
【０００４】
図５は、この種の確率変数発生装置の構成例を示したブロック図である。図５において、１０１は時間信号発生手段、１０２は一様乱数発生手段、１０３は記憶手段、１０４は四則演算手段、１０５は定数発生手段、１１０はこれらを含む確率変数発生装置である。この確率変数発生装置１１０は、一様乱数発生手段１０２の出力を、記憶手段１０３に記憶された所望の確率分布の累積度関数値を参照して変換し、四則演算手段１０４を経由して出力することで所望の確率分布に従う確率変数を適切なタイミングで発生するものであり、このタイミングを得るための時間信号発生手段１０１や四則演算手段１０４に定数を供給するための定数発生手段１０５を含んでいる。
【０００５】
上記のような確率変数発生装置１１０を内蔵するパケット中継装置によれば、ハードウェアによって乱数を生成するようにしているため、パケット中継に伴う処理負荷の増大を招来することがない。
【０００６】
しかしながら、こうしたハードウェアによって乱数を生成する場合には、図５に示したすべての構成や機構が必ずしも必要となることはないにせよ、最小限の構成や機構をパケット中継装置に内蔵させる必要がある。この結果、パケット中継装置の構成が複雑になるとともに、製造コストを増大することになる。
【０００７】
この発明は上記実情に鑑みてなされたもので、構成の複雑化およびコスト増を招来することなくパケット中継に伴う処理負荷の低減を図ることのできるパケット中継装置を得ることを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、この発明にかかるパケット中継装置は、パケットを格納するためのパケットバッファを初期化する際に一様乱数を発生させて該パケットバッファの各パケット格納フィールドに付随するフィールドに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに附随するフィールドの値を読み出してこれを乱数として用いることを特徴とする。
【０００９】
この発明によれば、パケットを格納したパケット格納フィールドに付随する乱数フィールドを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１０】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記パケット格納フィールドに付随するフィールドに格納した一様乱数を更新することを特徴とする。
【００１１】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってパケット格納フィールドに付随するフィールドに格納した一様乱数の値が更新される。
【００１２】
つぎの発明にかかるパケット中継装置は、パケットを格納するためのパケットバッファを初期化する際に、パケット格納フィールドと１対１に対応付けられたエントリを有する乱数テーブルを生成するとともに、一様乱数を発生させて該乱数テーブルのエントリに前記一様乱数を格納しておき、パケット中継時においては任意の空きパケット格納フィールドを割り当てる一方、送信時の確率計算を行う場合にはパケットを格納したパケット格納フィールドに対応するエントリの値を読み出してこれを乱数として用いることを特徴とする。
【００１３】
この発明によれば、パケットを格納したパケット格納フィールドに簡単な規則で対応付けた乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１４】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って一様乱数を発生させ、前記乱数テーブルのエントリに格納した一様乱数を更新することを特徴とする。
【００１５】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って乱数テーブルのエントリに格納した一様乱数が更新される。
【００１６】
つぎの発明にかかるパケット中継装置は、上記の発明において、前記パケットバッファに、各バッファ格納フィールドに付随するポインタフィールドを設けるとともに、該ポインタフィールドに格納したポインタの値に従って前記バッファ格納フィールドを前記乱数テーブルのエントリに１対１に対応付けたことを特徴とする。
【００１７】
この発明によれば、パケットを格納したパケット格納フィールドに付随するポインタフィールドから指示された乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができる。
【００１８】
つぎの発明にかかるパケット中継装置は、上記の発明において、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って前記ポインタフィールドに格納したポインタの値を更新することを特徴とする。
【００１９】
この発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってポインタフィールドに格納したポインタの値が更新される。
【００２０】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかるパケット中継装置の好適な実施の形態を詳細に説明する。
【００２１】
実施の形態１．
図１は、この発明に実施の形態１であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有するとともに、各パケット格納フィールド１１−１〜１１−ｎに付随して乱数を格納するｎ個の乱数フィールド１２−１〜１２−ｎを有している。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数をパケットバッファ１０の乱数フィールド１２−１〜１２−ｎにそれぞれ与える部分である。これは、例えばパケットバッファ１０の乱数フィールド１２−１〜１２−ｎとして８ビットのメモリ領域を用いる場合であれば、０〜２５５の範囲の値を同等の確率で生じるような一様乱数生成関数をプログラムし、パケットバッファ１０の初期化時にこの関数を起動して出力される値を乱数フィールド１２−１〜１２−ｎに格納することで実現することができる。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００２２】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により、乱数発生部２０において一様乱数を発生し、該一様乱数をパケットバッファ１０の各乱数フィールド１２−１〜１２−ｎに格納する処理を実施する。
【００２３】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１を割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００２４】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００２５】
この場合、本実施の形態１においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに附随する乱数フィールド１２−１〜１２−ｎの一様乱数値を用いる。乱数フィールド１２−１〜１２−ｎから読み出した値を乱数と見なすことができる理由は以下の通りである。すなわち、通常多くの端末が独立に送信したパケットをパケット中継装置が受信した場合、該パケット中継装置は、受信パケットの内容に依存することなく空いているパケット格納フィールド１１−１〜１１−ｎを任意に割り当てる。つまり、受信パケットをパケットバッファ１０のどのパケット格納フィールド１１−１〜１１−ｎに割り当てるかは、ランダムと見なすことができる。従って、パケットバッファ１０の初期化時にのみ乱数発生部２０において発生した一様乱数をパケットバッファ１０の乱数フィールド１２−１〜１２−ｎに格納する処理を実施し、その後、パケット格納フィールド１１−１〜１１−ｎに附随する乱数フィールド１２−１〜１２−ｎの値がパケット毎に都度変化しない場合であっても、パケット中継装置が受信する一連のパケットに対しそれらが格納されるパケットバッファ１０に附随する乱数フィールド１２−１〜１２−ｎを読み出して得られた値をランダムな数値列と見なすことができる。
【００２６】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随する乱数フィールド１２−１〜１２−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、唯一乱数発生部２０を設けるだけであり、図５に示した専用の確率変数発生装置、つまり時間信号発生部１０１、一様乱数発生部１０２、記憶部１０３、四則演算部１０４、定数発生部１０５等々、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００２７】
なお、上述した実施の形態１では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０のキューフィールド３１−１〜３１−ｍに転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、各パケットバッファのパケット格納フィールドにそれぞれ乱数フィールドを附随させ、パケット受信時にパケットを格納するパケットバッファ、つまり第１段となるパケットバッファのパケット格納フィールドに附随する乱数フィールドから得られる乱数値を順次コピーするようにしてもよい。あるいは、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、この最終段となるパケットバッファにのみ乱数フィールドを設けてその初期化時に各パケット格納フィールドに付随する乱数フィールドに一様乱数を格納するようにしてもよい。
【００２８】
また、上述した実施の形態１では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数フィールド１２−１〜１２−ｎに格納し直すことも可能である。このようにして乱数フィールド１２−１〜１２−ｎの値を更新した場合には、乱数フィールド１２−１〜１２−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００２９】
実施の形態２．
図２は、この発明に実施の形態２であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数テーブル５０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有している。乱数テーブル５０は、ｎ個のエントリ５１−１〜５１−ｎを有したもので、各エントリ５１−１〜５１−ｎが１対１の対応関係を与える簡単な規則でパケットバッファ１０の各パケット格納フィールド１１−１〜１１−ｎに対応付けてある。本実施の形態２においては、図３に示すような態様で、パケットバッファ１０の各パケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０の各エントリ５１−１〜５１−ｎとに１対１の対応関係を与えるようにしている。すなわち、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎにそれぞれ個々の位置を示す添字ｉを順次付すとともに、乱数テーブル５０のエントリ５１−１〜５１−ｎにそれぞれ個々の位置を示す添字ｉを順次付し、これらの添字ｉが同一となるものを互いに対応付けるようにしている。なお、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応関係は、必ずしもこれに限らず、両者が１対１に対応すれば、他の規則を用いても構わない。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎにそれぞれ与える部分である。これは、例えば乱数テーブル５０のエントリ５１−１〜５１−ｎが８ビットの長さを有するものであれば、０〜２５５の範囲の値を同等の確率で生じるような一様乱数生成関数をプログラムし、パケットバッファ１０の初期化時にこの関数を起動して出力される値をエントリ５１−１〜５１−ｎに格納することで実現することができる。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００３０】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により乱数発生部２０において一様乱数を発生し、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎに格納する処理を実施する。
【００３１】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１を割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００３２】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００３３】
この場合、本実施の形態２においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに簡単な規則で対応付けたエントリ５１−１〜５１−ｎの一様乱数値を用いる。乱数テーブル５０のエントリ５１−１〜５１−ｎから読み出した値を乱数と見なすことができる理由は実施の形態１と同様である。
【００３４】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに簡単な規則で対応付けた乱数テーブル５０のエントリ５１−１〜５１−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、乱数発生部２０および乱数テーブル５０を設けるだけであり、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００３５】
なお、上述した実施の形態２では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０のキューフィールド３１−１〜３１−ｍに転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、該最終段となるパケットバッファにのみ対応する乱数テーブルを設け、最終段となるパケットバッファの初期化時に、各パケット格納フィールドに対応付けた乱数テーブルのエントリに一様乱数を格納してもよい。
【００３６】
また、上述した実施の形態２では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数テーブル５０のエントリ５１−１〜５１−ｎに格納し直すことも可能である。このようにして乱数テーブル５０の値を更新した場合には、エントリ５１−１〜５１−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００３７】
実施の形態３．
図４は、この発明に実施の形態３であるパケット中継装置の構成例を示すブロック図である。ここで例示するパケット中継装置は、蓄積転送型のもので、パケットバッファ１０、乱数テーブル５０、乱数発生部２０、送信待ちキュー３０および中継制御部４０を備えている。パケットバッファ１０は、パケット受信時にパケットを格納する一方、パケット送信時にパケットを読み出すｎ個のパケット格納フィールド１１−１〜１１−ｎを有するとともに、各パケット格納フィールド１１−１〜１１−ｎに付随してポインタを格納するｎ個のポインタフィールド１３−１〜１３−ｎを有している。乱数テーブル５０は、ｎ個のエントリ５１−１〜５１−ｎを有したものである。乱数発生部２０は、パケットバッファ１０の初期化時に一様乱数を発生させ、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎやパケットバッファ１０のポインタフィールド１３−１〜１３−ｎに与える部分である。送信待ちキュー３０は、送信待ち行列を格納するバッファであり、送信方路毎にｍ個のキューフィールド３１−１〜３１−ｍを有している。中継制御部４０は、受信したパケットのパケットヘッダ情報に基づいて送信方路を決定する部分である。
【００３８】
以下、上記パケット中継装置の動作について説明する。まず、パケット中継装置は、上述したように、パケットバッファ１０の初期化時に中継制御部４０からの指示により乱数発生部２０において一様乱数を発生し、該一様乱数を乱数テーブル５０のエントリ５１−１〜５１−ｎに格納する処理を実施する。さらに、パケット中継装置は、図中の矢印で示すように、パケットバッファ１０のポインタフィールド１３−１〜１３−ｎに、乱数テーブル５０のエントリ５１−１〜５１−ｎを１対１に指示するポインタを格納する。これらのポインタは、例えばポインタフィールド１３−１〜１３−ｎに対して乱数発生部２０により一様乱数を発生させ、これによって得た値ｊを用いてｊ番目のエントリ５１−１〜５１−ｎを対応付ける。次のポインタフィールド１３−１〜１３−ｎに対しては、再び乱数発生部２０により一様乱数を発生させ、これによって得た値ｋ（≠ｊ）を用いてｋ番目のエントリ５１−１〜５１−ｎを対応付ける。以下同様にしてランダムな手順により設定することができる。なお、ポインタによるポインタフィールド１３−１〜１３−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応付けは、必ずしも上述した手順に限らず、例えばｉ番目のポインタフィールド１３−１〜１３−ｎに対してｉ番目のエントリ５１−１〜５１−ｎを対応させるといった、ランダムでない手順を用いることも可能である。
【００３９】
上述した状態から、上記パケット中継装置は、パケットを受信する場合に中継制御部４０がパケットバッファ１０の中で空いているものの一つ、例えばパケット格納フィールド１１−１〜１１−ｎを割り当て、これに受信パケットを格納する。この場合、受信パケットの内容に依存することなく、空いているパケット格納フィールド１１−１〜１１−ｎを割り当てる。さらにパケット中継装置は、中継制御部４０がパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットのパケットヘッダ情報を読み出して処理するとともに、該受信パケットの送信方路を決定する。例えば、パケット格納フィールド１１−１に格納された受信パケットは、中継制御部４０によって送信方路に送信待ちキュー３０の該当するキューフィールド３１−１に転送され、該キューフィールド３１−１に保持されて送信処理が行われる。
【００４０】
ここで、上述したＲＥＤのように確率的にパケットを廃棄、もしくはマークするアルゴリズムを適用している場合には、送信待ちキュー３０に保持する以前に、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎについて確率計算を行う必要がある。
【００４１】
この場合、本実施の形態３においては、従前のごとくプログラムによる乱数生成関数や専用の確率変数発生装置を用いるのではなく、確率計算で必要となる乱数として、受信パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随するポインタフィールド１３−１〜１３−ｎからポインタによって指示された乱数テーブル５０のエントリ５１−１〜５１−ｎの一様乱数値を用いる。乱数テーブル５０のエントリ５１−１〜５１−ｎから読み出した値を乱数と見なすことができる理由は実施の形態１と同様である。
【００４２】
このように、上記パケット中継装置によれば、パケットを格納したパケット格納フィールド１１−１〜１１−ｎに付随するポインタフィールド１３−１〜１３−ｎから指示された乱数テーブル５０のエントリ５１−１〜５１−ｎを読み出すことにより乱数値を取得するようにしているため、ＲＥＤに伴う確率計算の際に、数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することができる。しかも、乱数を生成するためのハードウェア構成としては、乱数発生部２０および乱数テーブル５０を設けるだけであり、多数の構成や機構を含んだ確率変数発生装置が不要となる。従って、パケット中継装置の構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。因に、上記パケット中継装置にあっては、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段として、必ずしも乱数発生部２０を設ける必要はなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることが可能である。
【００４３】
なお、上述した実施の形態３では、パケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎに格納した受信パケットをそのまま送信待ちキュー３０に転送させるようにしているが、受信パケットを適宜コピーしながら複数段のパケットバッファを経由して送信待ちキューに転送させるようにしたパケット中継装置にも適用することが可能である。この場合、最終段となるパケットバッファのパケット格納フィールドが選択される際のランダム性を利用し、該最終段となるパケットバッファにのみポインタフィールドを設けるとともに、対応する乱数テーブルを設け、最終段となるパケットバッファの初期化時に、各パケット格納フィールドに対応付けた乱数テーブルのエントリ一様乱数を格納してもよい。
【００４４】
また、上述した実施の形態３では、パケットバッファ１０の初期化時にのみ一様乱数を発生するようにしているが、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様の方法を用いて一様乱数を発生させ、乱数テーブル５０のエントリ５１−１〜５１−ｎに格納し直すことも可能である。このようにして乱数テーブル５０の値を更新した場合には、エントリ５１−１〜５１−ｎの値がパケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００４５】
さらに、上述した実施の形態３では、パケット中継装置の処理負荷が低い時、あるいは定期的に、パケットバッファ１０の初期化時と同様のランダムな手順を用いて乱数テーブル５０のエントリ５１−１〜５１−ｎとの１対１の対応関係を保ちつつ、ポインタフィールド１３−１〜１３−ｎのポインタを格納し直すことも可能である。このようにしてポインタフィールド１３−１〜１３−ｎのポインタを更新した場合、つまりパケットバッファ１０のパケット格納フィールド１１−１〜１１−ｎと乱数テーブル５０のエントリ５１−１〜５１−ｎとの対応付けを更新した場合には、ポインタフィールド１３−１〜１３−ｎのポインタがパケット毎には変化しないことに起因する乱数値の偏りを軽減することができる。
【００４６】
【発明の効果】
以上説明したように、この発明によれば、パケットを格納したパケット格納フィールドに付随する乱数フィールドを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００４７】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってパケット格納フィールドに付随するフィールドに格納した一様乱数の値が更新されるため、パケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００４８】
つぎの発明によれば、パケットを格納したパケット格納フィールドに簡単な規則で対応付けた乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００４９】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従って乱数テーブルのエントリに格納した一様乱数が更新されるため、パケット毎には変化しないことに起因する乱数値の偏りを軽減することが可能になる。
【００５０】
つぎの発明によれば、パケットを格納したパケット格納フィールドに付随するポインタフィールドから指示された乱数テーブルのエントリを読み出すことにより乱数値を取得するようにしているため、確率計算の際に数ステップの四則演算を含む一様乱数生成関数を実行する必要がなくなり、処理負荷を著しく低減することが可能になる。しかも、パケット毎に乱数を発生する必要がないため、乱数を生成するための手段としては、必ずしもハードウェアを用いる必要がなく、ソフトウェアによって生成した疑似乱数を一様乱数として用いることができるため、多数の構成や機構を含んだ確率変数発生装置を設けることに起因して構成が複雑化する事態やコストを増大させる事態を招来する虞れがない。
【００５１】
つぎの発明によれば、パケット中継時の処理負荷が低い場合、もしくは所定の周期に従ってポインタフィールドに格納したポインタの値が更新されるため、ポインタフィールドのポインタがパケット毎には変化しないことに起因する乱数値の偏りを軽減することができる。
【図面の簡単な説明】
【図１】この発明に実施の形態１であるパケット中継装置の構成例を示すブロック図である。
【図２】この発明に実施の形態２であるパケット中継装置の構成例を示すブロック図である。
【図３】パケットバッファのパケット格納フィールドと乱数テーブルのエントリとの対応関係を例示する概念図である。
【図４】図４は、この発明に実施の形態３であるパケット中継装置の構成例を示すブロック図である。
【図５】従来のパケット中継装置に適用される確率変数発生装置の構成例を示したブロック図である。
【符号の説明】
１０パケットバッファ、１１−１〜１１−ｎパケット格納フィールド、１２−１〜１２−ｎ乱数フィールド、１３−１〜１３−ｎポインタフィールド、２０乱数発生部、３０送信待ちキュー、３１−１〜３１−ｍキューフィールド、４０中継制御部、５０乱数テーブル、５１−１〜５１−ｎエントリ。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a packet relay apparatus that relays packets by a storage relay system.
[0002]
[Prior art]
In order to avoid congestion of the packet transmission queue in the packet relay device, an algorithm called RED (Random Early Detection) is proposed as an algorithm for discarding or marking packets stochastically according to the amount of data stored in the transmission queue. (S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance, ACM / IEEE Transactions on Networking, 1 (4): 397-413, 1993.). In such an algorithm, it is necessary to generate a random number when performing probability calculation for discarding or marking a packet. For this reason, in a packet relay apparatus that implements an algorithm involving probability calculation such as RED, it is common to dynamically generate a random number necessary for probability calculation every time a packet arrives in the transmission queue.
[0003]
[Problems to be solved by the invention]
By the way, when the random number generation described above is performed by a program, it is necessary to execute a uniform random number generation function including at least a few steps of four arithmetic operations, although it varies depending on the accuracy of the random number. Contributes to increased load. In order to solve such a problem of an increase in processing load, it is conceivable to apply a dedicated random variable generator as disclosed in Japanese Patent No. 3074107 and generate random numbers by hardware.
[0004]
FIG. 5 is a block diagram showing a configuration example of this type of random variable generation device. In FIG. 5, 101 is a time signal generation means, 102 is a uniform random number generation means, 103 is a storage means, 104 is an arithmetic operation means, 105 is a constant generation means, and 110 is a random variable generation apparatus including these. The random variable generator 110 converts the output of the uniform random number generator 102 with reference to the cumulative degree function value of the desired probability distribution stored in the storage unit 103, and outputs it via the four arithmetic units 104. Thus, a random variable according to a desired probability distribution is generated at an appropriate timing, and includes a time signal generating means 101 for obtaining this timing and a constant generating means 105 for supplying constants to the four arithmetic operation means 104. It is out.
[0005]
According to the packet relay device incorporating the random variable generator 110 as described above, random numbers are generated by hardware, so that an increase in processing load associated with packet relay is not caused.
[0006]
However, when generating random numbers using such hardware, it is not always necessary to have all the configurations and mechanisms shown in FIG. 5, but it is necessary to incorporate the minimum configurations and mechanisms in the packet relay apparatus. is there. As a result, the configuration of the packet relay device becomes complicated and the manufacturing cost increases.
[0007]
The present invention has been made in view of the above circumstances, and an object of the present invention is to provide a packet relay apparatus capable of reducing the processing load accompanying packet relay without incurring a complicated configuration and an increase in cost.
[0008]
[Means for Solving the Problems]
In order to achieve the above object, the packet relay apparatus according to the present invention generates a uniform random number when initializing a packet buffer for storing a packet, and assigns it to a field associated with each packet storage field of the packet buffer. The uniform random number is stored, and an arbitrary empty packet storage field is allocated at the time of packet relay. On the other hand, when the probability calculation at the time of transmission is performed, the value of the field attached to the packet storage field storing the packet is read. This is used as a random number.
[0009]
According to the present invention, the random number value is obtained by reading the random number field associated with the packet storage field that stores the packet. Therefore, a uniform random number generation function including four arithmetic operations in several steps at the time of probability calculation Is no longer necessary. Moreover, since it is not necessary to generate random numbers for each packet, it is not always necessary to use hardware as means for generating random numbers, and pseudo-random numbers generated by software can be used as uniform random numbers.
[0010]
In the packet relay apparatus according to the next invention, in the above invention, when the processing load at the time of packet relay is low, or the uniform random number is generated according to a predetermined cycle, and the uniform stored in the field associated with the packet storage field The random number is updated.
[0011]
According to the present invention, when the processing load at the time of packet relay is low, or the value of the uniform random number stored in the field associated with the packet storage field is updated according to a predetermined cycle.
[0012]
When initializing a packet buffer for storing a packet, the packet relay device according to the next invention generates a random number table having an entry associated with the packet storage field on a one-to-one basis, and uniform random numbers To store the uniform random number in an entry of the random number table and assign an arbitrary empty packet storage field at the time of packet relay, while when calculating the probability at the time of transmission, the packet storing the packet The value of the entry corresponding to the storage field is read out and used as a random number.
[0013]
According to the present invention, the random number value is obtained by reading the entry of the random number table associated with the packet storage field storing the packet according to a simple rule. There is no need to execute a uniform random number generation function including. Moreover, since it is not necessary to generate random numbers for each packet, it is not always necessary to use hardware as means for generating random numbers, and pseudo-random numbers generated by software can be used as uniform random numbers.
[0014]
The packet relay device according to the next invention is the above invention, wherein the processing load at the time of packet relay is low, or a uniform random number is generated according to a predetermined cycle, and the uniform random number stored in the entry of the random number table is updated. It is characterized by doing.
[0015]
According to the present invention, the uniform random number stored in the random number table entry is updated when the processing load at the time of packet relay is low or according to a predetermined cycle.
[0016]
In the packet relay apparatus according to the next invention, in the above invention, the packet buffer is provided with a pointer field associated with each buffer storage field, and the buffer storage field is assigned to the random number according to the value of the pointer stored in the pointer field. It is characterized in that the table entries are associated one-to-one.
[0017]
According to the present invention, since the random number value is obtained by reading the entry in the random number table indicated from the pointer field attached to the packet storage field storing the packet, the four rules of several steps are used in the probability calculation. It is not necessary to execute a uniform random number generation function including an operation. Moreover, since it is not necessary to generate random numbers for each packet, it is not always necessary to use hardware as means for generating random numbers, and pseudo-random numbers generated by software can be used as uniform random numbers.
[0018]
The packet relay apparatus according to the next invention is characterized in that, in the above invention, the value of the pointer stored in the pointer field is updated when the processing load at the time of packet relay is low or according to a predetermined cycle.
[0019]
According to the present invention, the value of the pointer stored in the pointer field is updated when the processing load at the time of packet relay is low or according to a predetermined cycle.
[0020]
DETAILED DESCRIPTION OF THE INVENTION
Exemplary embodiments of a packet relay device according to the present invention will be explained below in detail with reference to the accompanying drawings.
[0021]
Embodiment 1 FIG.
FIG. 1 is a block diagram showing a configuration example of a packet relay apparatus according to Embodiment 1 of the present invention. The packet relay apparatus exemplified here is of a storage and transfer type, and includes a packet buffer 10, a random number generation unit 20, a transmission waiting queue 30, and a relay control unit 40. The packet buffer 10 has n packet storage fields 11-1 to 11-n for reading packets at the time of packet reception and reading packets at the time of packet transmission, and is attached to each packet storage field 11-1 to 11-n. And n random number fields 12-1 to 12-n for storing random numbers. The random number generation unit 20 is a part that generates a uniform random number when the packet buffer 10 is initialized, and supplies the uniform random number to the random number fields 12-1 to 12-n of the packet buffer 10. For example, if an 8-bit memory area is used as the random number fields 12-1 to 12-n of the packet buffer 10, a uniform random number generation function that generates a value in the range of 0 to 255 with an equal probability. Can be realized by starting the function when the packet buffer 10 is initialized and storing the output values in the random number fields 12-1 to 12-n. The transmission queue 30 is a buffer for storing a transmission queue, and has m queue fields 31-1 to 31-m for each transmission route. The relay control unit 40 is a part that determines the transmission route based on the packet header information of the received packet.
[0022]
Hereinafter, the operation of the packet relay apparatus will be described. First, as described above, the packet relay device generates a uniform random number in the random number generation unit 20 according to an instruction from the relay control unit 40 when the packet buffer 10 is initialized. A process of storing in the random number fields 12-1 to 12-n is performed.
[0023]
From the state described above, when the packet relay apparatus receives a packet, the packet controller 10 allocates one of the vacant packets in the packet buffer 10, for example, the packet storage field 11-1, and receives the received packet. Store. In this case, vacant packet storage fields 11-1 to 11-n are assigned without depending on the contents of the received packet. Further, the packet relay apparatus reads and processes the packet header information of the received packet stored in the packet storage fields 11-1 to 11-n by the relay control unit 40, and determines the transmission route of the received packet. For example, the received packet stored in the packet storage field 11-1 is transferred to the corresponding queue field 31-1 of the transmission queue 30 by the relay control unit 40 and held in the queue field 31-1. Transmission processing is performed.
[0024]
Here, when an algorithm for discarding or marking a packet stochastically is applied as in the above-described RED, the packet storage field 11-1 storing the received packet is stored before being held in the transmission queue 30. It is necessary to perform probability calculation for ˜11-n.
[0025]
In this case, in the first embodiment, instead of using a random number generation function by a program or a dedicated random variable generator as in the past, a packet storage field 11 that stores a received packet as a random number required for probability calculation. Uniform random numbers in random number fields 12-1 to 12-n attached to -1 to 11-n are used. The reason why the values read from the random number fields 12-1 to 12-n can be regarded as random numbers is as follows. In other words, when a packet relay apparatus receives a packet that is normally transmitted independently by many terminals, the packet relay apparatus stores empty packet storage fields 11-1 to 11-n without depending on the contents of the received packet. Assign arbitrarily. That is, to which packet storage field 11-1 to 11-n of the packet buffer 10 the received packet is assigned can be regarded as random. Accordingly, the process of storing the uniform random numbers generated in the random number generator 20 in the random number fields 12-1 to 12-n of the packet buffer 10 only when the packet buffer 10 is initialized is performed, and then the packet storage field 11-1 Even when the values of the random number fields 12-1 to 12-n associated with .about.11-n do not change every packet, the packet buffer 10 in which they are stored for a series of packets received by the packet relay device. The values obtained by reading the random number fields 12-1 to 12-n attached to can be regarded as a random numerical sequence.
[0026]
As described above, according to the packet relay apparatus, the random number value is acquired by reading the random number fields 12-1 to 12-n attached to the packet storage fields 11-1 to 11-n storing the packets. Therefore, it is not necessary to execute a uniform random number generation function including four arithmetic operations in several steps in the probability calculation accompanying RED, and the processing load can be significantly reduced. Moreover, as a hardware configuration for generating random numbers, only the random number generator 20 is provided, and the dedicated random variable generator shown in FIG. 5, that is, the time signal generator 101 and the uniform random number generator 102 are provided. , The random number generator including a large number of configurations and mechanisms, such as the storage unit 103, the four arithmetic operations unit 104, the constant generation unit 105, and the like, is not necessary. Therefore, there is no possibility of causing a situation where the configuration of the packet relay apparatus becomes complicated or a situation where the cost increases. Incidentally, in the packet relay device, since it is not necessary to generate a random number for each packet, it is not always necessary to provide the random number generator 20 as a means for generating a random number, and a pseudo-random number generated by software Can be used as a uniform random number.
[0027]
In the first embodiment described above, the received packets stored in the packet storage fields 11-1 to 11-n of the packet buffer 10 are directly transferred to the queue fields 31-1 to 31-m of the transmission queue 30. However, the present invention can also be applied to a packet relay device in which a received packet is appropriately copied and transferred to a transmission queue via a plurality of stages of packet buffers. In this case, a random number field is attached to the packet storage field of each packet buffer, and a random number value obtained from the packet buffer that stores the packet when receiving the packet, that is, the random number field that is attached to the packet storage field of the first stage packet buffer May be copied sequentially. Alternatively, using the randomness when the packet storage field of the packet buffer at the final stage is selected, a random number field is provided only in the packet buffer at the final stage, and a random number associated with each packet storage field at the time of initialization A uniform random number may be stored in the field.
[0028]
In the first embodiment described above, a uniform random number is generated only when the packet buffer 10 is initialized. However, when the processing load of the packet relay apparatus is low or periodically, the initial value of the packet buffer 10 is set. It is also possible to generate a uniform random number by using the same method as that at the time of conversion, and store it again in the random number fields 12-1 to 12-n. When the values of the random number fields 12-1 to 12-n are updated in this way, the bias of the random number values due to the fact that the values of the random number fields 12-1 to 12-n do not change for each packet is reduced. It becomes possible to do.
[0029]
Embodiment 2. FIG.
FIG. 2 is a block diagram showing a configuration example of a packet relay apparatus according to the second embodiment of the present invention. The packet relay apparatus exemplified here is of a storage and transfer type, and includes a packet buffer 10, a random number table 50, a random number generator 20, a transmission queue 30 and a relay controller 40. The packet buffer 10 has n packet storage fields 11-1 to 11-n for storing packets when receiving packets and reading packets when transmitting packets. The random number table 50 has n entries 51-1 to 51-n, and each packet of the packet buffer 10 has a simple rule that gives a one-to-one correspondence between the entries 51-1 to 51-n. Corresponding to storage fields 11-1 to 11-n. In the second embodiment, a pair of packet storage fields 11-1 to 11-n of the packet buffer 10 and entries 51-1 to 51-n of the random number table 50 are paired in a manner as shown in FIG. 1 correspondence is given. That is, subscripts i indicating individual positions are sequentially attached to the packet storage fields 11-1 to 11-n of the packet buffer 10, and subscripts indicating individual positions are respectively assigned to the entries 51-1 to 51-n of the random number table 50. i is sequentially attached, and those having the same subscript i are associated with each other. Note that the correspondence relationship between the packet storage fields 11-1 to 11-n of the packet buffer 10 and the entries 51-1 to 51-n of the random number table 50 is not necessarily limited to this. Other rules may be used. The random number generation unit 20 is a part that generates a uniform random number when the packet buffer 10 is initialized, and supplies the uniform random number to the entries 51-1 to 51-n of the random number table 50, respectively. For example, if the entries 51-1 to 51-n of the random number table 50 have a length of 8 bits, a uniform random number generation function that generates a value in the range of 0 to 255 with an equal probability is used. This can be realized by programming and starting this function when the packet buffer 10 is initialized and storing the values output in the entries 51-1 to 51-n. The transmission queue 30 is a buffer for storing a transmission queue, and has m queue fields 31-1 to 31-m for each transmission route. The relay control unit 40 is a part that determines the transmission route based on the packet header information of the received packet.
[0030]
Hereinafter, the operation of the packet relay apparatus will be described. First, as described above, the packet relay device generates a uniform random number in the random number generation unit 20 according to an instruction from the relay control unit 40 when the packet buffer 10 is initialized, and the uniform random number is generated in the entry 51 of the random number table 50. The process of storing in −1 to 51-n is performed.
[0031]
From the state described above, when the packet relay apparatus receives a packet, the packet controller 10 allocates one of the vacant packets in the packet buffer 10, for example, the packet storage field 11-1, and receives the received packet. Store. In this case, vacant packet storage fields 11-1 to 11-n are assigned without depending on the contents of the received packet. Further, the packet relay apparatus reads and processes the packet header information of the received packet stored in the packet storage fields 11-1 to 11-n by the relay control unit 40, and determines the transmission route of the received packet. For example, the received packet stored in the packet storage field 11-1 is transferred to the corresponding queue field 31-1 of the transmission queue 30 by the relay control unit 40 and held in the queue field 31-1. Transmission processing is performed.
[0032]
Here, when an algorithm for discarding or marking a packet stochastically is applied as in the above-described RED, the packet storage field 11-1 storing the received packet is stored before being held in the transmission queue 30. It is necessary to perform probability calculation for ˜11-n.
[0033]
In this case, in the second embodiment, instead of using a random number generation function by a program or a dedicated random variable generator as before, a packet storage field 11 that stores a received packet as a random number required for probability calculation is used. Uniform random numbers of entries 51-1 to 51-n associated with −1 to 11-n with simple rules are used. The reason why the values read from the entries 51-1 to 51-n of the random number table 50 can be regarded as random numbers is the same as in the first embodiment.
[0034]
As described above, according to the packet relay apparatus, by reading the entries 51-1 to 51-n of the random number table 50 associated with the packet storage fields 11-1 to 11-n storing the packets according to a simple rule. Since the random value is acquired, it is not necessary to execute a uniform random number generation function including four arithmetic operations in several steps in the probability calculation accompanying RED, and the processing load can be significantly reduced. Moreover, as a hardware configuration for generating random numbers, only the random number generation unit 20 and the random number table 50 are provided, and a random variable generation device including a large number of configurations and mechanisms becomes unnecessary. Therefore, there is no possibility of causing a situation where the configuration of the packet relay apparatus becomes complicated or a situation where the cost increases. Incidentally, in the packet relay device, since it is not necessary to generate a random number for each packet, it is not always necessary to provide the random number generator 20 as a means for generating a random number, and a pseudo-random number generated by software Can be used as a uniform random number.
[0035]
In the second embodiment, the received packets stored in the packet storage fields 11-1 to 11-n of the packet buffer 10 are transferred as they are to the queue fields 31-1 to 31-m of the transmission queue 30. However, the present invention can also be applied to a packet relay device in which a received packet is appropriately copied and transferred to a transmission queue via a plurality of stages of packet buffers. In this case, using the randomness when the packet storage field of the packet buffer at the final stage is selected, a random number table corresponding to only the packet buffer at the final stage is provided, and the packet buffer at the final stage is initialized. Sometimes, a uniform random number may be stored in a random number table entry associated with each packet storage field.
[0036]
In the second embodiment, the uniform random number is generated only when the packet buffer 10 is initialized. However, when the processing load of the packet relay apparatus is low or periodically, the initial value of the packet buffer 10 is set. It is also possible to generate a uniform random number using a method similar to that at the time of conversion, and store it again in entries 51-1 to 51-n of the random number table 50. When the values of the random number table 50 are updated in this way, it is possible to reduce the random value bias caused by the values of the entries 51-1 to 51-n not changing for each packet.
[0037]
Embodiment 3 FIG.
FIG. 4 is a block diagram showing a configuration example of the packet relay apparatus according to the third embodiment of the present invention. The packet relay apparatus exemplified here is of a storage and transfer type, and includes a packet buffer 10, a random number table 50, a random number generator 20, a transmission queue 30 and a relay controller 40. The packet buffer 10 has n packet storage fields 11-1 to 11-n for reading packets at the time of packet reception and reading packets at the time of packet transmission, and is attached to each packet storage field 11-1 to 11-n. And n pointer fields 13-1 to 13-n for storing pointers. The random number table 50 has n entries 51-1 to 51-n. The random number generation unit 20 generates a uniform random number when the packet buffer 10 is initialized, and the uniform random number is generated in the entries 51-1 to 51-n of the random number table 50 and the pointer fields 13-1 to 13- of the packet buffer 10. This is the part given to n. The transmission queue 30 is a buffer for storing a transmission queue, and has m queue fields 31-1 to 31-m for each transmission route. The relay control unit 40 is a part that determines the transmission route based on the packet header information of the received packet.
[0038]
Hereinafter, the operation of the packet relay apparatus will be described. First, as described above, the packet relay device generates a uniform random number in the random number generation unit 20 according to an instruction from the relay control unit 40 when the packet buffer 10 is initialized, and the uniform random number is generated in the entry 51 of the random number table 50. The process of storing in −1 to 51-n is performed. Further, the packet relay device instructs the pointer fields 13-1 to 13-n of the packet buffer 10 one-to-one with the entries 51-1 to 51-n of the random number table 50 as indicated by arrows in the drawing. Stores a pointer. For these pointers, for example, the random number generator 20 generates uniform random numbers for the pointer fields 13-1 to 13-n, and the jth entries 51-1 to 51-n are obtained using the value j obtained thereby. Associate. For the next pointer fields 13-1 to 13-n, the random number generator 20 generates a uniform random number again, and the value k (≠ j) obtained thereby is used to generate the kth entries 51-1 to 51-1. 51-n is associated. In the same manner, it can be set by a random procedure. The association between the pointer fields 13-1 to 13-n by the pointers and the entries 51-1 to 51-n of the random number table 50 is not necessarily limited to the above-described procedure, and for example, the i-th pointer field 13-1 to 13-n. It is also possible to use a non-random procedure such as associating the i-th entries 51-1 to 51-n with 13-n.
[0039]
From the state described above, when receiving a packet, the packet relay apparatus allocates one of the vacant packets in the packet buffer 10 when the relay control unit 40 receives the packet, for example, packet storage fields 11-1 to 11-n. The received packet is stored in. In this case, vacant packet storage fields 11-1 to 11-n are assigned without depending on the contents of the received packet. Further, the packet relay apparatus reads and processes the packet header information of the received packet stored in the packet storage fields 11-1 to 11-n by the relay control unit 40, and determines the transmission route of the received packet. For example, the received packet stored in the packet storage field 11-1 is transferred to the corresponding queue field 31-1 of the transmission queue 30 by the relay control unit 40 and held in the queue field 31-1. Transmission processing is performed.
[0040]
Here, when an algorithm for discarding or marking a packet stochastically is applied as in the above-described RED, the packet storage field 11-1 storing the received packet is stored before being held in the transmission queue 30. It is necessary to perform probability calculation for ˜11-n.
[0041]
In this case, in the third embodiment, a random number generation function by a program and a dedicated random variable generator are not used as in the past, but a packet storage field 11 that stores a received packet as a random number required for probability calculation. The uniform random values of the entries 51-1 to 51-n of the random number table 50 indicated by the pointers from the pointer fields 13-1 to 13-n associated with -1 to 11-n are used. The reason why the values read from the entries 51-1 to 51-n of the random number table 50 can be regarded as random numbers is the same as in the first embodiment.
[0042]
As described above, according to the packet relay apparatus, the entry 51-1 in the random number table 50 indicated by the pointer fields 13-1 to 13-n attached to the packet storage fields 11-1 to 11-n storing the packets. Since the random number value is acquired by reading ~ 51-n, it is not necessary to execute a uniform random number generation function including four arithmetic operations in several steps in the probability calculation associated with RED, and the processing load is reduced. It can be significantly reduced. Moreover, as a hardware configuration for generating random numbers, only the random number generation unit 20 and the random number table 50 are provided, and a random variable generation device including a large number of configurations and mechanisms becomes unnecessary. Therefore, there is no possibility of causing a situation where the configuration of the packet relay apparatus becomes complicated or a situation where the cost increases. Incidentally, in the packet relay device, since it is not necessary to generate a random number for each packet, it is not always necessary to provide the random number generator 20 as a means for generating a random number, and a pseudo-random number generated by software Can be used as a uniform random number.
[0043]
In the third embodiment described above, the received packets stored in the packet storage fields 11-1 to 11-n of the packet buffer 10 are transferred as they are to the transmission waiting queue 30, but the received packets are copied as appropriate. However, the present invention can also be applied to a packet relay device that is transferred to a transmission queue via a plurality of stages of packet buffers. In this case, using the randomness when the packet storage field of the packet buffer that is the last stage is selected, a pointer field is provided only in the packet buffer that is the last stage, and a corresponding random number table is provided. At initialization of the packet buffer, the random number entry uniform random number associated with each packet storage field may be stored.
[0044]
In the third embodiment, the uniform random number is generated only when the packet buffer 10 is initialized. However, when the processing load of the packet relay apparatus is low or periodically, the initial value of the packet buffer 10 is set. It is also possible to generate a uniform random number using a method similar to that at the time of conversion, and store it again in entries 51-1 to 51-n of the random number table 50. When the values of the random number table 50 are updated in this way, it is possible to reduce the random value bias caused by the values of the entries 51-1 to 51-n not changing for each packet.
[0045]
Further, in the above-described third embodiment, when the processing load of the packet relay apparatus is low or periodically, entries 51-1 to 51-1 of the random number table 50 are used using a random procedure similar to that at the time of initializing the packet buffer 10. The pointers of the pointer fields 13-1 to 13-n can be stored again while maintaining a one-to-one correspondence with 51-n. When the pointers of the pointer fields 13-1 to 13-n are updated in this way, that is, between the packet storage fields 11-1 to 11-n of the packet buffer 10 and the entries 51-1 to 51-n of the random number table 50. When the association is updated, it is possible to reduce the random value bias caused by the fact that the pointers in the pointer fields 13-1 to 13-n do not change for each packet.
[0046]
【The invention's effect】
As described above, according to the present invention, since the random number value is obtained by reading the random number field associated with the packet storage field storing the packet, four steps of arithmetic operations are performed in the probability calculation. It is not necessary to execute a uniform random number generation function including the processing function, and the processing load can be significantly reduced. Moreover, since it is not necessary to generate a random number for each packet, it is not always necessary to use hardware as a means for generating a random number, and a pseudo-random number generated by software can be used as a uniform random number. There is no possibility of incurring a situation where the structure becomes complicated due to the provision of a random variable generation device including a large number of structures and mechanisms, and a situation where the cost increases.
[0047]
According to the next invention, when the processing load at the time of packet relay is low, or the value of the uniform random number stored in the field associated with the packet storage field is updated according to a predetermined cycle, it does not change for each packet. It is possible to reduce the bias of the random number value caused by.
[0048]
According to the next invention, the random number value is acquired by reading the entry of the random number table associated with the packet storage field storing the packet according to a simple rule. There is no need to execute a uniform random number generation function including computation, and the processing load can be significantly reduced. Moreover, since it is not necessary to generate a random number for each packet, it is not always necessary to use hardware as a means for generating a random number, and a pseudo-random number generated by software can be used as a uniform random number. There is no possibility of incurring a situation where the structure becomes complicated due to the provision of a random variable generation device including a large number of structures and mechanisms, and a situation where the cost increases.
[0049]
According to the next invention, when the processing load at the time of packet relay is low, or the uniform random number stored in the random number table entry is updated according to a predetermined cycle, the random number value resulting from no change for each packet Can be reduced.
[0050]
According to the next invention, the random number value is obtained by reading the specified random number table entry from the pointer field associated with the packet storage field storing the packet. There is no need to execute a uniform random number generation function including four arithmetic operations, and the processing load can be significantly reduced. Moreover, since it is not necessary to generate a random number for each packet, it is not always necessary to use hardware as a means for generating a random number, and a pseudo-random number generated by software can be used as a uniform random number. There is no possibility of incurring a situation where the structure becomes complicated due to the provision of a random variable generation device including a large number of structures and mechanisms, and a situation where the cost increases.
[0051]
According to the next invention, when the processing load at the time of packet relay is low, or the pointer value stored in the pointer field is updated according to a predetermined cycle, the pointer field pointer does not change for each packet. It is possible to reduce the bias of random number values.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a configuration example of a packet relay device according to a first embodiment of the present invention.
FIG. 2 is a block diagram showing a configuration example of a packet relay apparatus according to a second embodiment of the present invention.
FIG. 3 is a conceptual diagram illustrating the correspondence between a packet storage field of a packet buffer and a random number table entry.
FIG. 4 is a block diagram showing a configuration example of a packet relay apparatus according to a third embodiment of the present invention.
FIG. 5 is a block diagram showing a configuration example of a random variable generator applied to a conventional packet relay device.
[Explanation of symbols]
10 packet buffer, 11-1 to 11-n packet storage field, 12-1 to 12-n random number field, 13-1 to 13-n pointer field, 20 random number generator, 30 transmission queue, 31-1 to 31 -M Queue field, 40 relay control unit, 50 random number table, 51-1 to 51-n entries.

Claims

When a packet buffer for storing packets is initialized, a uniform random number is generated, and the uniform random number is stored in a field associated with each packet storage field of the packet buffer. A packet relay apparatus characterized in that, when a free packet storage field is assigned, a field value associated with a packet storage field storing a packet is read out and used as a random number when probability calculation at the time of transmission is performed.

2. The uniform random number stored in a field associated with the packet storage field is updated when a processing load at the time of packet relay is low or when a uniform random number is generated according to a predetermined cycle. Packet relay device.

When a packet buffer for storing a packet is initialized, a random number table having an entry associated with the packet storage field in a one-to-one correspondence is generated, and a uniform random number is generated to generate an entry in the random number table. The uniform random number is stored, and an arbitrary empty packet storage field is allocated at the time of packet relay. On the other hand, when the probability calculation at the time of transmission is performed, the value of the entry corresponding to the packet storage field storing the packet is read. A packet relay device characterized by using this as a random number.

4. The packet relay apparatus according to claim 3, wherein a uniform random number is generated according to a predetermined cycle when a processing load during packet relay is low, or the uniform random number stored in an entry of the random number table is updated. .

The packet buffer is provided with a pointer field associated with each buffer storage field, and the buffer storage field is associated one-to-one with the random number table entry according to the value of the pointer stored in the pointer field. The packet relay device according to claim 3 or 4.

6. The packet relay device according to claim 5, wherein the value of the pointer stored in the pointer field is updated when a processing load at the time of packet relay is low or according to a predetermined cycle.