(57)【特許請求の範囲】
【請求項１】
複数の他のパケット交換機または端末に接続可能に構成され、接続されている他のパケット交換機または端末のいずれかから受信したパケットに含まれる該パケットの最終送信先を示すデータに基づいて、接続されている他のパケット交換機または端末のうちのいずれのパケット交換機または端末に該パケットを送出するかを決定し、決定した他のパケット交換機または端末に該パケットを送出するパケット交換機であって、
所定のタイミングで信号を発生する信号発生手段と、
パケットの最終送信先と、この最終送信先を示すデータが含まれるパケットを接続されている他のパケット交換機のうちのどのパケット交換機に送出するかを示す送出先情報とを対応づけて記憶する第１の記憶手段と、
前記第１の記憶手段に対応づけて記憶されている前記最終送信先と送出先情報とのうちの一部が記憶される、前記第１の記憶手段よりも高速の第２の記憶手段と、
前記第２の記憶手段に記憶されている前記最終送信先と送出先情報とのそれぞれに対応して設けられたフラグから構成される複数のカウント手段と、
前記信号発生手段が前記信号を発生したときの前記複数のカウント手段のフラグを少なくとも１回分記憶するカウント記憶手段と、
接続されている他のパケット交換機からパケットを受信したときに、前記第２の記憶手段を参照して、該受信したパケットに含まれる最終送信先を示すデータに対応する前記送出先情報を抽出する第１の抽出手段と、
前記第１の抽出手段が前記第２の記憶手段から前記送出先情報を抽出したときに、該送出先情報に対応するフラグをオンする第１のカウント制御手段と、
前記第１の抽出手段が前記第２の記憶手段から前記送出先情報を抽出できなかったときに、前記第１の記憶手段から受信したパケットに含まれる最終送信先を示すデータに対応する前記送出先情報を抽出する第２の抽出手段と、
前記信号発生手段が前記信号を発生したときの前記カウント手段を構成するフラグと前記カウント記憶手段が記憶しているフラグとに基づいて、前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを、受信したパケットに含まれる最終送信先と該最終送信先に対応する送出先情報であって、前記第２の抽出手段が前記第１の記憶手段から抽出した最終送信先と送出先情報と、に更新する更新手段と、を備える
ことを特徴とするパケット交換機。
【請求項２】
前記更新手段は、前記信号発生手段が前記信号を発生したときの前記カウント手段を構成するフラグと前記カウント記憶手段が記憶しているフラグとに基づいて、前記第２の記憶手段に記憶されている最終送信先と送信先情報とのうちの更新されるべき候補を選出する手段と、この手段が選出した前記候補を参照して、前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを前記第２の抽出手段が前記第１の記憶手段から抽出したものに更新する手段とを備える
ことを特徴とする請求項１に記載のパケット交換機。
【請求項３】
前記更新手段は、前記第２の抽出手段が前記第１の記憶手段から前記送出先情報を抽出したときに、第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを更新する、
ことを特徴とする請求項１または２に記載のパケット交換機。
【請求項４】
前記更新手段は、前記信号発生手段が前記信号を発生する毎に、前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを更新する、
ことを特徴とする請求項１または２に記載のパケット交換機。
【請求項５】
前記第２の抽出手段によって対応する前記送出先情報が抽出された最終送出先を記憶する第３の記憶手段を備え、
前記更新手段は、前記第３の記憶手段に記憶されている最終送出先と該最終送出先に対応する送出先情報を前記第２の記憶手段に記憶させる、
ことを特徴とする請求項４に記載のパケット交換機。
【請求項６】
前記更新手段が前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを更新したときに、前記複数のカウント手段をクリアする第２のカウント制御手段を備える、
ことを特徴とする請求項４または５に記載のパケット交換機。
【請求項７】
前記信号発生手段は、所定の時間間隔を計時する計時手段を有し、この計時手段が前記所定の時間間隔を計時する毎に前記信号を発生する、
ことを特徴とする請求項１乃至６のいずれか１項に記載のパケット交換機。
【請求項８】
前記第１のカウント制御手段と、前記第２の抽出手段と、前記更新手段とは、同一の処理装置によって構成されている、
ことを特徴とする請求項１乃至７のいずれか１項に記載のパケット交換機。
【請求項９】
前記信号発生手段は、処理装置の動作状態を識別する動作状態識別手段を有し、この動作状態識別手段が所定の動作状態を識別しているときに前記信号を発生する、
ことを特徴とする請求項１乃至８のいずれか１項にに記載のパケット交換機。
【請求項１０】
前記第１の抽出手段は、受信したパケットに含まれる該パケットの最終送信先を示すデータを前記第２の記憶手段に記憶されている最終送信先のそれぞれと比較する複数の比較器と、
前記比較器が一致を検出した最終送信先に対応する送出先情報を選択して出力する選択器と、を備える
ことを特徴とする請求項１乃至９のいずれか１項に記載のパケット交換機。
【請求項１１】
前記更新手段は、前記カウント手段を構成するフラグと前記カウント記憶手段が記憶しているフラグとに基づいて、少なくとも２所定期間の間続けて送出先情報の抽出が無かった前記第２の記憶手段のアドレスを先入れ先出し方式で記憶する、
ことを特徴とする請求項１乃至１０のいずれか１項に記載のパケット交換機。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットの送出先を高速に決定するパケット交換機に関する。
【０００２】
【従来の技術】
コンピュータシステムにおいて、限られた容量の高速メモリを有効に利用する場合など、資源の量に対して需要が大きい場合に、資源の利用効率を上げるため、データベースから検索した個々のデータなどの資源を利用する単位（以下、プロセスと呼ぶ）での資源の実際の使用実績に基づいて資源を割り当てる方法が知られている。このようなプロセスによる資源の使用（以下、参照という）の頻度を測るアルゴリズムとして、ＬＲＵ方式が知られている。
【０００３】
ＬＲＵ方式では、プロセスの参照頻度を管理するために、リストが用いられている。プロセスは、参照される毎にリストの先頭にくる。すなわち、リストが先頭から順に１→２→３→４→５→６→７→８→９→１０であるときに、プロセス５が参照されると、リストは先頭から順に５→１→２→３→４→６→７→８→９→１０となる。新たなプロセス１１が参照されたときには、リストの最後尾にある最も長い間参照されなかったプロセス１０が追い出される。
【０００４】
【発明が解決しようとする課題】
このようにＬＲＵ方式では、プロセスが参照される度に、ＬＲＵ用のリスト管理のためのプログラムを起動し、リストを並び替えなければならない。このプログラムは、参照したプロセスがリスト中のどこに存在するかを検索し、その前後のプロセス同士を探してリストでつなぎ、さらに、参照したプロセスをリストの先頭につなぐという一連の作業を要する。従って、このリスト管理のためのプログラムのオーバーヘッドが大きくなり、本来のプロセスの処理能力が低下することとなる。
【０００５】
また、パケット送信においては、データは所定長のパケットを単位として送信される。このパケットには、最終送信先のデータが含まれており、パケット交換網内の各パケット交換機は、この最終送信先のデータから受信したパケットを送出すべきパケット交換機を決定し、決定したパケット交換機に対して送出する。
【０００６】
ところで、パケット送信において送信すべきデータは、１つ１つのパケットの長さを越えるときが多い。この場合には、送信すべきデータは複数のパケットに分割され、それぞれに同一の最終送信先がデータとして割り付けられる。そして、これらの複数のパケットが次々と送信される。つまり、各パケット交換機は、１つのパケットを受信した後に、それと同一の最終送信先のデータを有するパケットを受信する可能性が非常に大きい。従って、次々と連続的に受信する同一の最終送信先のデータを有するパケットに対して、送出先のパケット交換機をいかに高速に決定するかが、パケット交換機の能力を向上させるために非常に重要な課題となっている。
【０００７】
本発明は、パケットの送出先を高速に決定することができるパケット交換機を提供することを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、本発明のパケット交換機は、
複数の他のパケット交換機または端末に接続可能に構成され、接続されている他のパケット交換機または端末のいずれかから受信したパケットに含まれる該パケットの最終送信先を示すデータに基づいて、接続されている他のパケット交換機または端末のうちのいずれのパケット交換機または端末に該パケットを送出するかを決定し、決定した他のパケット交換機または端末に該パケットを送出するパケット交換機であって、
所定のタイミングで信号を発生する信号発生手段と、
パケットの最終送信先と、この最終送信先を示すデータが含まれるパケットを接続されている他のパケット交換機のうちのどのパケット交換機に送出するかを示す送出先情報とを対応づけて記憶する第１の記憶手段と、
前記第１の記憶手段に対応づけて記憶されている前記最終送信先と送出先情報とのうちの一部が記憶される、前記第１の記憶手段よりも高速の第２の記憶手段と、
前記第２の記憶手段に記憶されている前記最終送信先と送出先情報とのそれぞれに対応して設けられたフラグから構成される複数のカウント手段と、
前記信号発生手段が前記信号を発生したときの前記複数のカウント手段のフラグを少なくとも１回分記憶するカウント記憶手段と、
接続されている他のパケット交換機からパケットを受信したときに、前記第２の記憶手段を参照して、該受信したパケットに含まれる最終送信先を示すデータに対応する前記送出先情報を抽出する第１の抽出手段と、
前記第１の抽出手段が前記第２の記憶手段から前記送出先情報を抽出したときに、該送出先情報に対応するフラグをオンする第１のカウント制御手段と、
前記第１の抽出手段が前記第２の記憶手段から前記送出先情報を抽出できなかったときに、前記第１の記憶手段から受信したパケットに含まれる最終送信先を示すデータに対応する前記送出先情報を抽出する第２の抽出手段と、
前記信号発生手段が前記信号を発生したときの前記カウント手段を構成するフラグと前記カウント記憶手段が記憶しているフラグとに基づいて、前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを、受信したパケットに含まれる最終送信先と該最終送信先に対応する送出先情報であって、前記第２の抽出手段が前記第１の記憶手段から抽出した最終送信先と送出先情報と、に更新する更新手段と、を備える
ことを特徴とする。
【０００９】
このパケット交換機では、カウント手段がフラグから構成され、カウント手段のフラグとカウント記憶手段に記憶されている従前のフラグとに基づいて、高速メモリによって構成される第２の記憶手段に記憶される最終送信先と送出先情報とが更新される。そして、受信したパケットに含まれる最終送信先のデータが第２の記憶手段に記憶されているときは、ここから高速に送出先情報が抽出される。このため、パケット交換機の処理能力が向上する。一方、更新されて第２の記憶手段から追い出される最終送信先と送出先情報とを選ぶために、送出先情報の抽出時にカウント手段を構成するフラグの制御を行えばよく、構成と制御が比較的容易である。従って、この処理のオーバーヘッドによって、本来の処理である送出先情報の抽出の能力がそれほど低下することがない。
【００１０】
上記パケット交換機において、
前記更新手段は、前記信号発生手段が前記信号を発生したときの前記カウント手段を構成するフラグと前記カウント記憶手段が記憶しているフラグとに基づいて、前記第２の記憶手段に記憶されている最終送信先と送信先情報とのうちの更新されるべき候補を選出する手段と、この手段が選出した前記候補を参照して、前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを前記第２の抽出手段が前記第１の記憶手段から抽出したものに更新する手段とを備えるものとすることができる。
【００１１】
上記パケット交換機において、
前記更新手段は、前記第２の抽出手段が前記第１の記憶手段から前記送出先情報を抽出したときに、第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを更新するものとすることができる。
【００１２】
また、前記更新手段は、前記信号発生手段が前記信号を発生する毎に、前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを更新するするものとすることもできる。
【００１３】
この場合、上記パケット交換機は、さらに、
前記第２の抽出手段によって対応する前記送出先情報が抽出された最終送出先を記憶する第３の記憶手段を備えるものとすることができる。このとき、
前記更新手段は、前記第３の記憶手段に記憶されている最終送出先と該最終送出先に対応する送出先情報を前記第２の記憶手段に記憶させるものとすることができる。
【００１４】
さらに、上記パケット交換機は、
前記更新手段が前記第２の記憶手段に対応づけて記憶する最終送信先と送出先情報とを更新したときに、前記複数のカウント手段をクリアする第２のカウント制御手段を備えるものとしてもよい。
【００１６】
上記パケット交換機において、
前記信号発生手段は、所定の時間間隔を計時する計時手段を有し、この計時手段が前記所定の時間間隔を計時する毎に前記信号を発生するものとしてもよい。
【００１７】
上記パケット交換機において、
前記第１のカウント制御手段と、前記第２の抽出手段と、前記更新手段とは、同一の処理装置によって構成されているものとしてもよい。すなわち、例えば、同一のＣＰＵ（中央処理装置）が前記第１のカウント制御手段、前記第２の抽出手段及び前記更新手段が行う処理を実行するものとしてもよい。
【００１８】
この場合、上記パケット交換機において、
前記信号発生手段は、処理装置の動作状態を識別する動作状態識別手段を有し、この動作状態識別手段が所定の動作状態を識別しているときに前記信号を発生するものとしてもよい。
【００１９】
上記パケット交換機において、
前記第１の抽出手段は、受信したパケットに含まれる該パケットの最終送信先を示すデータを前記第２の記憶手段に記憶されている最終送信先のそれぞれと比較する複数の比較器と、前記比較器が一致を検出した最終送信先に対応する送出先情報を選択して出力する選択器と、を備えるものとすることを好適とする。
【００２０】
このように第１の抽出手段をハードウェアによって構成することによって、送出先情報を非常に高速に抽出することができる。一方、送出先情報の抽出を行うハードウェアは、ソフトウェアで同一の機能を実現する場合に比べると非常に高価である。従って、このように抽出頻度が高い送出先情報をハードウェアによって抽出することができるようにした上記構成のパケット交換機は、処理の高速化が図れると共に、コスト的にも十分に見合ったものを製造することができる。
また、上記パケット交換機において、前記更新手段は、前記カウント手段を構成するフラグと前記カウント記憶手段が記憶しているフラグとに基づいて、少なくとも２所定期間の間続けて送出先情報の抽出が無かった前記第２の記憶手段のアドレスを先入れ先出し方式で記憶する、ように構成してもよい。
【００２１】
【発明の実施の形態】
以下、添付図面を参照して、本発明の実施の形態について説明する。
以下の第１〜第６の実施の形態では、パケット交換機等に設けられているパケットの送信先データを検出するデータ検索装置を例にして説明する。以下の第７の実施の形態では、ハード的にパケットの送出先を策出するパケット交換機を例にして説明する。
【００２２】
［第１の実施の形態］
図１は、この実施の形態にかかるデータ検索装置の構成を示すブロック図である。
図示するように、このデータ検索装置は、互いにバス１０を介して接続されたＣＰＵ（中央処理装置）１１と、ＭＭＵ（主記憶装置）１２と、磁気ディスク装置１３と、タイマ１４と、Ｉ／Ｆ（インタフェース）１５とから構成されている。
【００２３】
ＣＰＵ１１は、ＭＭＵ１２に記憶された処理プログラムを実行すると共に、このデータ検索装置の各部を制御する。
【００２４】
ＭＭＵ１２は、半導体メモリによって構成され、ＣＰＵ１１の処理プログラム（後述するデータ検索タスク及びリスト管理タスクのプログラムを含む）を記憶する領域の他に、後述するキャッシュ領域、ビットマップ及びリストを記憶する領域を有する。
【００２５】
磁気ディスク装置１３は、この実施の形態で検索対象となるパケットの送信先データをすべて記憶している。磁気ディスク装置１３は、ＭＭＵ１２よりも記憶容量が大きいが、アクセス時間の点では低速である。
【００２６】
タイマ１４は、例えば、設定値からクロック入力毎にカウントダウンするダウンカウンタによって構成されている。タイマ１４は、設定値を記憶するためのレジスタを内部に有する。タイマ１４は、カウント値が０になるとＣＰＵ１１にトリガ信号を出力すると共に、レジスタに記憶されている設定値を初期値としてカウンタにセットする。
【００２７】
Ｉ／Ｆ１５は、パケットの送信先データの検索の要求の入力したり、検索した送信先データの出力したりするためのインタフェースである。すなわち、このデータ検索装置へのデータの入出力は、すべてＩ／Ｆ１５を介して行われる。
【００２８】
この実施の形態のデータ検索装置は、ＣＰＵ１１がＭＭＵ１２に記憶された処理プログラムを実行することによって、図２に示すような機能を実現するものである。
図２に示すように、このデータ検索装置の機能は、キャッシュ領域２０と、ビットマップ２１と、データ検索タスク２２と、リスト管理タスク２３と、リスト２４と、磁気ディスク装置１３と、タイマ１４とから構成される。
【００２９】
キャッシュ領域２０は、ＭＭＵ１２内に設けられ、磁気ディスク１３に記憶されているパケットの送信先データの一部が記憶される領域である。送信先データの検索が要求されたとき、当該送信先データがキャッシュ領域２０に記憶されているときは、このキャッシュ領域から読み出されて出力される。キャッシュ領域２０に記憶されていない送信先データの場合は、磁気ディスク装置１３から読み出されてキャッシュ領域２０に書き込まれる。この実施の形態において、キャッシュ領域２０には、パケットの送信先データがその１つ１つを単位として記憶される。なお、以下の説明において、このパケットの送信先データの１つ１つが処理の単位となるので、これをプロセスと呼ぶ。また、キャッシュ領域２０からの送信先データを読み出すこと、或いは磁気ディスク装置１３から送信先データを読み出し、キャッシュ領域２０に書き込むことをプロセスの参照と呼ぶ。
【００３０】
ビットマップ２１は、ＭＭＵ１２内に設けられ、キャッシュ領域２０に記憶された各プロセスに対応する複数のカウンタによって構成される。ビットマップ２１の各カウンタは、対応するプロセスの送信先データに対して検索が実行されると、ＣＰＵ１１の処理によって１カウントアップされる。但し、カウンタの値が最高値（２進４ビットの場合は、１１１１）となっているときは、それ以上カウントアップされない。
【００３１】
データ検索タスク２２は、Ｉ／Ｆ１５を介して入力されたパケットの送信先データの検索要求に対して当該データの検索を実行し、検索結果をＩ／Ｆ１５を介して出力するタスクである。データ検索タスク２２は、パケットの送信先データの検索要求に応答して、まず、ＭＭＵ１２に設けられたキャッシュ領域２０を調べる。当該データがキャッシュ領域２０に記憶されていた場合は、当該データは、キャッシュ領域２０から読み出されて出力される。当該データをキャッシュ領域２０から策出することができなかった場合は、データ検索タスク２２は、さらに、磁気ディスク装置１３を調べて当該データを読み出し、Ｉ／Ｆ１５を介して出力すると共に、リスト２４の最後尾にある要素に対応するプロセスを追い出し、そこに読み出したデータを新たなプロセスとして書き込む。また、データ検索タスク２２は、プロセスが参照される毎に、対応するビットマップ２１のカウンタをカウントアップする。
【００３２】
リスト管理タスク２３は、タイマ１４からＣＰＵ１１にトリガ信号が入力される毎に起動される。リスト管理タスク２３は、ビットマップ２１の各プロセスに対応するカウンタに基づいてリスト２４の要素を並べ替える処理を行い、ビットマップ２１をクリアする処理を行う。
【００３３】
リスト２４は、キャッシュ領域２０に記憶されている（但し、リストの並べ替えの間にプロセスの追い出しがない場合）プロセスの記憶位置を示すデータと次のデータの記憶位置を示すポインタによって各要素が構成される単方向リストである。リスト２４は、キャッシュ領域２０に記憶されているプロセスの参照頻度順に各プロセスに対応する要素を並べて管理するものである。リスト２４は、先頭の要素の記憶位置を示すポインタを別に有する。
【００３４】
以下、この実施の形態のデータ検索装置における動作について説明する。
Ｉ／Ｆ１５を介してパケットの送信先データの検索要求がＣＰＵ１１に入力されると、ＣＰＵ１１は、データ検索タスク２２を起動する。
【００３５】
データ検索タスク２２は、まず、当該検索要求によって要求されたパケットの送信先データがプロセスとしてキャッシュ領域２０に記憶されているかどうかを調べる。キャッシュ領域２０に該当する送信先データがプロセスとして記憶されていた場合には、データ検索プロセス２２は、その送信先データをＩ／Ｆ１５を介して出力する。これにより、その送信先データのプロセスは参照されたこととなるので、ビットマップ２１の当該プロセスに対応するカウンタを１カウントアップする。
【００３６】
データ検索タスク２２は、キャッシュ領域２０に該当する送信先データがプロセスとして記憶されていなかった場合は、磁気ディスク装置１３にアクセスして、該当する送信先データを読み出す。次に、読み出した送信先データをどこに記憶するかを定めるため、リスト２４にアクセスして、その最後尾にある要素に対応するプロセスを調べる。そして、バッファ領域２０の中で、リスト２４の最後尾にあるプロセスを記憶している領域に読み出した送信先データを上書きする。これにより、新たにキャッシュ領域２０に書き込まれた送信先データのプロセスが参照されたこととなる。そこで、ビットマップ２１の当該プロセスに対応するカウンタに１をセットする。
【００３７】
一方、タイマ１４は、クロックに従って設定値からカウントダウンしていき、その値が０となったところでトリガ信号を発生する。このトリガ信号がＣＰＵ１１に入力されると、ＣＰＵ１１は、リスト管理タスク２３を起動する。
【００３８】
図３は、この実施の形態におけるリスト管理タスク２３の処理を示すフローチャートである。
このフローチャートの処理が開始すると、ＣＰＵ１１は、ＭＭＵ１２内に記憶されているビットマップを読み出し、ＣＰＵ１１の内部レジスタに記憶する（ステップＳ１１）。
【００３９】
次に、ＣＰＵ１１は、内部レジスタに記憶されたビットマップの各プロセスに対応するカウンタの値を参照して、カウンタの値が大きいものから降順となるように、リスト２４の要素を並び替える。このリスト２４の要素の並び替えは、例えば、ヒープソート、バブルソートなどの公知のソートアルゴリズムに従って実行することができる。但し、カウンタの値が同一のプロセス同士では、並び替え前のリスト２４でのプロセスの順番に従うものとする（ステップＳ１２）。
【００４０】
リスト２４の要素の並び替えの処理を終了すると、ＭＭＵ１２内に記憶されているビットマップをすべてのビットが０であるデータによって上書きして、クリアする（ステップＳ１３）。
そして、このフローチャートの処理を終了する。
【００４１】
ここで、例えば、ＣＰＵ１１にトリガ信号が入力される前、すなわち図３のフローチャートの処理が実行される前、ビットマップ２１の各プロセスに対応するカウンタの値が、図４（Ａ）に示すとおりであり、リスト２４の状態が図５（Ａ）に示すとおりであったとする。このとき、プロセス▲４▼に対応するカウンタの値が、「０１０１」で最も大きいので、プロセス▲４▼に対応する要素が新たなリストの先頭となる。プロセス▲１▼とプロセス▲２▼に対応するカウンタの値が、「００１１」で次に大きいが、並び替え前の状態でプロセス▲１▼の方が先にきているので、プロセス▲１▼に対応する要素が新たなリストの２番目、プロセス▲３▼に対応する要素が３番目となる。さらに、対応するカウンタの値に従ってプロセス▲５▼に対応する要素が４番目、プロセス▲２▼に対応する要素が５番目となるように、リスト２４の要素が並び替えられ、図５（Ｂ）に示すようなリストが新たなリストとして生成される（ステップＳ１２）。こうして新たなリストが生成されると、図４（Ｂ）に示すように、ビットマップ２１がクリアされる。
【００４２】
以上示した処理を何度も繰り返していくうちに、参照頻度の小さいプロセスに対応する要素は、リスト２４の後方へと移動していくこととなる。
【００４３】
以下、この実施の形態のデータ検索装置における動作の一連の流れを、図６のタイミングチャートを参照して説明する。なお、このタイミングチャートにおいては、説明を簡単にするため、各プロセスを参照するための時間はすべて同一であり、ＣＰＵ１１は他の処理を実行しないものとする。また、プロセスの参照は、すべてキャッシュ領域２０に記憶されているパケットの送信先データの読み出しのみであり、トリガ信号がＣＰＵ１１に入力してから次のトリガ信号が入力するまでに、プロセスのキャッシュ領域２０からの追い出しはないものとする。
【００４４】
図示するように、タイミングｔ００においてトリガ信号がタイマ１４からＣＰＵ１１に入力されると、タイミングｔ０１までの間、ＣＰＵ１１は、リスト管理タスク２３を起動して実行する。リスト管理タスク２３の処理が終了したタイミングｔ０１から次にトリガ信号がＣＰＵ１１に入力されるタイミングｔ１０まで、ＣＰＵ１１は、次々とプロセスの参照を行っている。そして、タイミングｔ１０においてトリガ信号が入力されると、ＣＰＵ１１は、再びリスト管理タスク２３を起動して、リスト２４の要素の並べ替えの処理等を行う。
【００４５】
これに対し、この実施の形態のデータ検索装置における効果を示すため、図７のタイミングチャートを参照して、比較例として従来例のＬＲＵ方式の動作について説明する。このタイミングチャートにおいても、各プロセスを参照するための時間はすべて同一であり、ＣＰＵ１１は他の処理を実行しないものとする。また、プロセスの参照は、すべてキャッシュ領域２０に記憶されているパケットの送信先データの読み出しのみであり、プロセスのキャッシュ領域２０からの追い出しはないものとする。
【００４６】
図示するように、ＣＰＵ１１は、データ検索タスク２２による１回のプロセスの参照が終了すると、その都度リスト管理タスク２３を起動して、リスト２４の要素を並び替える。データ検索タスク２２による１回当たりの処理は、図６の場合に比べて、ビットマップ２１のカウンタをカウントアップする処理がないため、若干短くできる。
【００４７】
しかし、図７の処理においては、カウントアップの処理よりも実行する命令数が遙かに多く、大幅に処理時間が大きいリスト管理タスク２３の処理をプロセスを１回参照する都度実行しなければならない。これに対し、図６の処理では、複数回のプロセスの参照に対して、リスト管理タスク２３の処理を１回実行すればよい。このため、図６の処理では、リスト管理タスク２３のオーバーヘッドが図７に示した場合よりも大幅に小さくなる。
【００４８】
このオーバーヘッドの低減をＮ個の要素からなるリストを例として説明する。要素を先頭に持ってくるためには、ポインタをたどり、当該要素を探す処理（最大Ｎステップ）、当該要素の前後の要素のポインタをつなぐ処理（１ステップ）、先頭ポインタが当該要素を指すための処理（１ステップ）、当該要素のポインタがそれまで先頭だった要素を指すための処理（１ステップ）の最大Ｎ＋３ステップが必要となる。一方、ビットマップのビット操作は、それぞれ１ステップで行うことができる。
【００４９】
個々で、特定のプロセスが所定時間内に２０回参照されるとすると、リストの要素の並べ替えのために、この実施の形態の方法では、１×２０＋Ｎ＋３＝Ｎ＋２３ステップが必要となる。これに対して、従来のＬＲＵの手法による場合は、Ｎ＋３＋４×１９＝Ｎ＋７９ステップ必要となる。この結果、この実施の形態の方法によるオーバーヘッドの低減の効果が表れていることがわかる。
【００５０】
以上説明したように、この実施の形態のデータ検索装置では、プロセスの参照頻度を管理するためのリスト２４の要素の並べ替えのための処理のオーバーヘッドを小さくすることができ、かつ従来より用いられていたＬＲＵ方式による場合とほぼ同一の機能が得られる。
【００５１】
［第２の実施の形態］
この実施の形態のデータ検索装置の構成及び動作は、第１の実施の形態のものと実質的に同一である。但し、この実施の形態では、リスト２４の構造が異なり、ビットマップ２１の各カウンタが示す値が同一であったプロセスには、順序づけを行わない。また、この実施の形態では、リスト２４の構造が異なるため、リスト管理タスク２３における処理が異なる。
【００５２】
図８は、この実施の形態におけるリスト２４の構造を示す図である。
図示するように、このリスト２４の各要素は、データ２４１と、水平ポインタ２４２と、垂直ポインタ２４３とから構成される。また、先頭の要素の記憶位置を示すための先頭ポインタ２４０を有する。データ２４１には、プロセスの記憶位置が書き込まれる。このリスト２４においては、参照頻度が同一（ビットマップのカウンタ値が同一）のプロセスは、水平ポインタ２４２でつながれる。参照頻度が異なるプロセスは、参照頻度順に垂直ポインタ２４３でつながれる。
【００５３】
以下、この実施の形態におけるリスト管理タスク２３の処理について説明する。
図９は、この実施の形態におけるリスト管理タスク２３の処理を示すフローチャートである。この実施の形態においても、リスト管理タスク２３は、タイマ１４からＣＰＵ１１にトリガ信号が入力されることによって起動される。
【００５４】
このフローチャートの処理が開始すると、ＣＰＵ１１は、ＭＭＵ１２内に記憶されているビットマップ２１を読み出し、ＣＰＵ１１の内部レジスタに記憶する（ステップＳ１１）。
【００５５】
ビットマップ２１の読み出しが終了すると、ＣＰＵ１１は、ループ１（ステップＳ２１−Ｓ２１’）、ループ２（ステップＳ２２−Ｓ２２’）の２重ループの処理を行う。ループ１では、変数を０からビットマップ２１の各プロセスに対応するカウンタの最大値（２進４桁の場合は、「００００」〜「１１１１」まで）まで変化させる。一方、ループ２では、各プロセスに対応するカウンタを並び順に対応してキャッシュ領域２０に記憶された全プロセス分となるまで、変数を変化させ、カウンタの値を参照していく。
【００５６】
ループ１及びループ２内での処理では、ＣＰＵ１１は、参照したカウンタ値がループ１におけるそのときの変数に一致しているかどうかを判定する（ステップＳ２３）。ステップＳ２３でカウンタ値が変数に一致していると判定したときは、さらに、そのカウンタ値が当該変数において１番目のものであるかどうかを判定する（ステップＳ２４）。
【００５７】
ステップＳ２４で当該変数が１番目のものであると判定したときは、前回までの処理によってリスト２４に接続されている最後の要素の垂直ポインタ２４３が当該プロセスに対応する要素を指し示すよう処理する（ステップＳ２５）。そして、そのときの変数によるループ２の処理を終了する。ステップＳ２４で当該変数が１番目のものでないと判定したときは、前回までの処理によってリスト２４に接続されている最後の要素の水平ポインタ２４２が当該プロセスに対応する要素を指し示すよう処理する（ステップＳ２６）。そして、そのときの変数によるループ２の処理を終了する。
【００５８】
一方、ステップＳ２３でカウンタ値が変数に一致していないと判定したときは、そのまま、そのときの変数によるループ２の処理を終了する。
以上のループ１及びループ２の処理を終了することによって、リスト２４の要素の並び替えが終了する。
【００５９】
リスト２４の要素の並び替えの処理を終了すると、ＭＭＵ１２内に記憶されているビットマップをすべてのビットが０であるデータによって上書きして、クリアする（ステップＳ１３）。
そして、このフローチャートの処理を終了する。
【００６０】
以上説明したように、この実施の形態では、プロセスに対応するカウンタの値が同一である場合に、それらのプロセスに対応する要素間で順序に差異を設けない図８に示すようなリスト２４を使用した。このとき、リスト管理タスク２３によるリスト２４の要素の並び替えの処理は、２重ループによっているが、ループ１（ステップＳ２１−Ｓ２１’）では、変数は０〜カウンタの最大値までである。従って、例えば、ビットマップ２１の各カウンタが２進２桁であり、これに対してキャッシュ領域２０に記憶されるプロセス数が２０ビット分（約１００万個）ある場合には、第１の実施の形態の場合よりも高速な処理が可能となる。
【００６１】
［第３の実施の形態］
この実施の形態のデータ検索装置の構成及び動作は、第１の実施の形態のものと実質的に同一である。但し、この実施の形態では、タイマ１４が有するレジスタにセットする設定値を外部から変えることができる。また、リスト管理タスク２３は、タイマ１４が有するレジスタにセットする設定値を変えるための処理をさらに備える。リスト管理タスク２３中のデータには、設定値の初期値と後述する設定値の増減のための閾値（Ｍ）が含まれている。このデータ検索装置の起動時には、タイマ１４が有する内部レジスタには、この初期値が書き込まれている。
【００６２】
図１０は、この実施の形態におけるリスト管理タスク２３の処理を示すフローチャートである。この実施の形態においても、リスト管理タスク２３は、タイマ１４からＣＰＵ１１にトリガ信号が入力されることによって起動される。
このフローチャートの処理が開始すると、ＣＰＵ１１は、ＭＭＵ１２内に記憶されているビットマップ２１を読み出し、ＣＰＵ１１の内部レジスタに記憶する（ステップＳ１１）。
【００６３】
次に、ＣＰＵ１１は、内部レジスタに記憶されたビットマップの各プロセスに対応するカウンタの値を参照して、カウンタの値が大きいものから降順となるように、リスト２４の要素を並び替える。このリスト２４の要素の並び替えは、例えば、ヒープソート、バブルソートなどの公知のソートアルゴリズムに従って実行することができる。但し、カウンタの値が同一のプロセス同士では、並び替え前のリスト２４でのプロセスの順番に従うものとする（ステップＳ１２）。
【００６４】
ＣＰＵ１１は、内部レジスタに記憶されたビットマップの各プロセスに対応するカウンタの値を参照して、カウント値が所定数より小さいプロセスの数を求め、変数ｍに代入する（ステップＳ３１）。
ＣＰＵ１１は、ステップＳ３１で求めたプロセスの数ｍと、リスト管理タスク２３中のデータに含まれる閾値Ｍとを比較する（ステップＳ３２）。
【００６５】
ステップＳ３２でプロセスの数ｍが閾値Ｍより大きいと判定したときは、タイマ１４の内部レジスタに設定された設定値を所定値だけ増加して（ステップＳ３３）、ステップＳ１３の処理に進む。
ステップＳ３２でプロセスの数ｍが閾値Ｍと等しいと判定したときは、そのままステップＳ１３の処理に進む。
ステップＳ３２でプロセスの数ｍが閾値Ｍより小さいと判定したときは、タイマ１４の内部レジスタに設定された設定値を所定値だけ減少して（ステップＳ３４）、ステップＳ１３の処理に進む。
【００６６】
ステップＳ１３では、ＭＭＵ１２内に記憶されているビットマップ２１をすべてのビットが０であるデータによって上書きして、クリアする。
そして、このフローチャートの処理を終了する。
【００６７】
以上説明したように、この実施の形態のデータ検索装置では、全体でのプロセスの参照の頻度に応じてタイマ１４の内部レジスタに設定する設定値が増減させられる。このため、プロセスの参照頻度が多いときはリスト２４の要素の並べ替えの回数を多く、プロセスの参照頻度が少ないときはリスト２４の要素の並べ替えの回数が少なくなる。従って、全体でのプロセスの参照の頻度に応じて、最適なタイミングでリスト２４の要素を並び替えることができる。
【００６８】
［第４の実施の形態］
この実施の形態のデータ検索装置の構成及び動作は、第１の実施の形態のものとほぼ同一であるが、タイマ１４の構成が異なり、後述するようにトリガ信号Ａとトリガ信号Ｂとの２種類のトリガ信号を発生する。また、タイマ１４が２種類のトリガ信号を発生することにより、リスト管理タスク２３は、第１の実施の形態の場合と異なり、それぞれのトリガ信号に応じた処理を行うものとなる。
【００６９】
この実施の形態において、タイマ１４は、第３の実施の形態と同様のダウンカウンタと内部レジスタからなる組を２組有し、それぞれがトリガ信号Ａ用、トリガ信号Ｂ用となる。トリガ信号Ａ用の内部レジスタには、トリガ信号Ａの発生間隔を示す設定値Ｔａが記憶される。トリガ信号Ｂ用の内部レジスタには、トリガ信号Ａの発生間隔を示す設定値Ｔｂが記憶される。リスト管理タスク２３は、トリガ信号Ａ用、Ｂ用のそれぞれの設定値Ｔａ、Ｔｂの増減を判断するための閾値Ｍ１、Ｍ２をデータとして有している。また、トリガ信号Ｂを発生させる（オンする）か発生させない（オフする）かがリスト管理タスク２３の処理のよって制御される。
【００７０】
以下、この実施の形態のリスト管理タスクの処理について説明する。
図１１は、タイマ１４からＣＰＵ１１にトリガ信号Ａが入力されたときのリスト管理タスク２３の処理を示すフローチャートである。
このフローチャートの処理が開始すると、ＣＰＵ１１は、ＭＭＵ１２内に記憶されているビットマップ２１を読み出し、ＣＰＵ１１の内部レジスタに記憶する（ステップＳ１１）。
【００７１】
次に、ＣＰＵ１１は、内部レジスタに記憶されたビットマップの各プロセスに対応するカウンタの値を参照して、カウンタの値が大きいものから降順となるように、リスト２４の要素を並び替える。このリスト２４の要素の並び替えは、例えば、ヒープソート、バブルソートなどの公知のソートアルゴリズムに従って実行することができる。但し、カウンタの値が同一のプロセス同士では、並び替え前のリスト２４でのプロセスの順番に従うものとする（ステップＳ１２）。
【００７２】
ＣＰＵ１１は、内部レジスタに記憶されたビットマップの各プロセスに対応するカウンタの値を参照して、カウント値が所定数より小さいプロセスの数を求め、変数ｍに代入する（ステップＳ４１）。
ＣＰＵ１１は、ステップＳ４１で求めたプロセスの数ｍと、リスト管理タスク２３中のデータに含まれる閾値Ｍ１とを比較する（ステップＳ４２）。
【００７３】
ステップＳ４２でプロセスの数ｍが閾値Ｍ１より大きいと判定したときは、タイマ１４の内部レジスタに設定された設定値Ｔａを所定値だけ増加して（ステップＳ４３）、ステップＳ４５の処理に進む。
ステップＳ４２でプロセスの数ｍが閾値Ｍと等しいと判定したときは、そのままステップＳ４５の処理に進む。
ステップＳ４２でプロセスの数ｍが閾値Ｍより小さいと判定したときは、タイマ１４の内部レジスタに設定された設定値Ｔａを所定値だけ減少して（ステップＳ４４）、ステップＳ４５の処理に進む。
【００７４】
ステップＳ４５では、タイマ１４の内部レジスタに設定されたトリガ信号Ａ用の設定値Ｔａがトリガ信号Ｂ用の設定値Ｔｂよりも大きいかどうかを判定する。ステップＳ４５で設定値Ｔａが設定値Ｔｂよりも大きいと判定したときは、トリガ信号Ｂの発生をオフして（ステップＳ４６）、ステップＳ４８の処理に進む。ステップＳ４５で設定値Ｔａが設定値Ｔｂよりも大きくないと判定したときは、トリガ信号Ｂの発生をオンして（ステップＳ４７）、ステップＳ４８の処理に進む。
【００７５】
ステップＳ４８では、ＭＭＵ１２内に記憶されているビットマップ２１をすべてのビットが０であるデータによって上書きして、クリアする。
そして、このフローチャートの処理を終了する。
【００７６】
図１２は、タイマ１４からＣＰＵ１１にトリガ信号Ｂが入力されたときのリスト管理タスク２３の処理を示すフローチャートである。
このフローチャートの処理は、図１１のフローチャートの処理とほぼ同様であるが、ステップＳ５２において、ステップＳ４１で求めたプロセスの数ｍと、リスト管理タスク２３中のデータに含まれる閾値Ｍ２とを比較する。また、ステップＳ５３またはＳ５４で増減の対象となるのは、トリガ信号Ｂ用の設定値Ｔｂである。
【００７７】
また、ステップＳ４６またはステップＳ４７の処理を終了した後は、ビットマップ２１の各カウンタの値をクリアすることなく、そのままこのフローチャートの処理を終了する。
【００７８】
以上説明したように、この実施の形態のデータ検索装置では、リストの要素の並び替えは、トリガ信号Ａ、ＢのいずれがＣＰＵ１１に入力された場合にもなされる。すなわち、リスト２４の要素のつなぎ順は、頻繁に更新される。一方、ビットマップ２１の各カウンタの値は、トリガ信号Ｂが発生した場合には、クリアされない。このため、トリガ信号Ａの発生から発生までの間におけるプロセスの参照回数に基づいて、リストの要素を並び替えることができる。
【００７９】
また、トリガ信号Ｂの発生間隔がトリガ信号Ａの発生間隔よりも短い場合には、トリガ信号Ｂが発生しないので、トリガ信号Ｂの発生間隔が短く調整されてリストの並べ替えが頻繁に行われることをさけることができる。
【００８０】
［第５の実施の形態］
図１３は、この実施の形態のデータ検索装置の機能を示す機能ブロック図である。
このデータ検索装置の機能構成は、第１の実施のものとほぼ同じであるが、フラグ２１０が付加されている点が異なる。また、データ検索タスク２２及びリスト管理タスク２３の処理もフラグ２１０を利用することで、第１の実施の形態のものと若干異なる。
【００８１】
フラグ２１０は、ＭＭＵ１２内に設けられ、ビットマップ２１の各カウンタ、すなわちキャッシュ領域２０に記憶された各プロセスに対応する数の、それぞれ１ビットからなる複数のフラグによって構成される。データ検索タスク２２は、プロセスを参照したときに、ビットマップ２１の中の対応するカウンタをカウントアップすると共に、対応するビットのフラグをセットする。リスト管理タスク２３は、フラグ２１０を参照して、ビットマップ２１のカウンタの読み出しを行う。リスト管理タスク２３は、また、フラグ２１０をリセットする。
【００８２】
図１４は、この実施の形態におけるリスト管理タスク２３の処理を示すフローチャートである。この実施の形態においても、リスト管理タスク２３は、タイマ１４からＣＰＵ１１にトリガ信号が入力されることによって起動される。
このフローチャートの処理が開始すると、ＣＰＵ１１は、ＭＭＵ１２内に記憶されているフラグ２１０を読み出し、ＣＰＵ１１の内部レジスタに記憶する（ステップＳ６１）。
【００８３】
フラグ２１０の読み出しが終了すると、ＣＰＵ１１は、ループ１（ステップＳ６２−Ｓ６２’）の処理を行う。ループ１では、キャッシュ領域２０に記憶された個々のプロセスに対応するフラグを順次参照していく。
【００８４】
ループ１内では、ＣＰＵ１１は、まず、変化させられている変数に対応するフラグの値が１であるか０であるか、すなわちフラグがセットされているかリセットされているかどうかを判定する（ステップＳ６３）。
ステップＳ６３でフラグがリセットされていると判定した場合は、次の変数についての処理に進むか、或いはすべての変数についての処理を終了した場合はループ１の処理を終了する。
【００８５】
ステップＳ６３でフラグがセットされていると判定したときは、ＣＰＵ１１は、変数の値に対応するビットマップ２１中のカウンタの値を読み出す（ステップＳ６４）。そして、ＣＰＵ１１は、当該変数に対応するリスト２４の要素を抜き出し、カウンタに従って降順となるようにその要素をつなぐ。なお、抜き出された要素の前後の要素は、ポインタでつながれる（ステップＳ６５）。ステップＳ６５の処理が終了すると、次の変数についての処理に進むか、或いはすべての変数についての処理を終了した場合はループ１の処理を終了する。
【００８６】
ループ１の処理を終了すると、ＭＭＵ１２内に記憶されているフラグ２１０をすべてリセットする（ステップＳ６６）。さらに、ＭＭＵ１２内に記憶されているビットマップをすべてのビットが０であるデータによって上書きして、クリアする（ステップＳ６７）。
そして、このフローチャートの処理を終了する。
【００８７】
以上説明したように、この実施の形態のデータ検索装置では、ビットマップ２１の各カウンタの内、対応するフラグがセットされているものだけを読み出せばよい。すなわち、キャッシュ領域２０に記憶されているプロセスが全部で１２８個、ビットマップ２１の各カウンタが１６ビット、参照されたプロセス数が３２個であるとき、第１の実施の形態で読み出す必要があるビット数は、１２８×１６＝２０４８（ビット）であるのに対して、この実施の形態では、１２８＋１６×３２＝６４０（ビット）で済むこととなる。このため、比較的時間のかかるＭＭＵ１２からのデータの読み出し数を少なくすることができると共に、ＣＰＵ１１の内部レジスタの数、或いはＭＭＵ１２に確保するワークエリアが小さくても済む。
【００８８】
また、リスト２４の要素を並び替えるときに、セットされているフラグに対応する要素を抜き出し、前後の要素をつなぎ変えればよい。従って、セットされていないフラグに対応する要素は、並び替え時に考慮しなくてもよいので、リスト管理タスク２３における処理を速くすることができる。
【００８９】
［第６の実施の形態］
図１５は、この実施の形態にかかるデータ検索装置の構成を示すブロック図である。
図示するように、このデータ検索装置は、互いにバス１０を介して接続されたＣＰＵ１１と、ＭＭＵ１２と、磁気ディスク装置１３と、Ｉ／Ｆ（インタフェース）１５と、動作状態識別装置３１とから構成されている。
【００９０】
ＣＰＵ１１と、ＭＭＵ１２と、磁気ディスク装置１３と、Ｉ／Ｆ（インタフェース）１５との構成は、第１の実施の形態のデータ検索装置（図１参照）のものと実質的に同一である。動作状態識別装置３１は、ＣＰＵ１１の動作状態がアイドル状態にあるかどうか、すなわちＭＭＵ１２または磁気ディスク装置１３に記憶されているデータの検索処理などの処理が所定頻度以上で実行されていないかどうかを識別するものである。動作状態識別装置３１は、ＣＰＵ１１の動作状態がアイドル状態にあると識別すると、ＣＰＵ１１にトリガ信号を出力する。
【００９１】
この実施の形態のデータ検索装置は、ＣＰＵ１１がＭＭＵ１２に記憶された処理プログラムを実行することによって、図１６に示すような機能を実現するものである。
図１６に示すように、このデータ検索装置の機能は、キャッシュ領域２０と、ビットマップ２１と、データ検索タスク２２と、リスト管理タスク２３と、リスト２４と、磁気ディスク装置１３と、動作状態識別装置３１とから構成される。
【００９２】
この機能において、キャッシュ領域２０と、ビットマップ２１と、データ検索タスク２２と、リスト管理タスク２３と、リスト２４と、磁気ディスク装置１３とは、第１の実施の形態のデータ検索装置（図２参照）のものと実質的に同一である。但し、リスト管理タスク２３は、タイマからのトリガ信号ではなく、動作状態識別装置３１からのトリガ信号に従って、動作する。
【００９３】
この実施の形態のデータ検索装置の動作は、第１の実施の形態のデータ検索装置におけるタイマ１４からのトリガ信号を動作状態識別装置３１からのトリガ信号に置き換えれば、他の処理は同一である。
【００９４】
以上説明したように、この実施の形態のデータ検索装置によれば、動作状態識別装置３１がＣＰＵ１１の動作状態を監視している。そして、ＣＰＵ１１がアイドル状態にあるとき、すなわち本来の処理であるデータ検索を行っていないときに、リスト２４の要素の並べ替えが行われる。このため、この実施の形態のデータ検索装置では、リスト２４の要素の並べ替えによるオーバーヘッドによって、本来の処理であるデータ検索の処理が中断されることがない。
【００９５】
［第７の実施の形態］
この実施の形態では、受信したパケットの送出先をハードウェアによって高速に抽出することができるパケット交換機について説明する。
【００９６】
図１７は、この実施の形態にかかるパケット交換網を示すブロック図である。図示するように、このパケット交換網において、パケット交換機４−１は、複数のパケット交換機４−２〜４−ｎに接続されている。パケット交換機４−１は、接続されているパケット交換機４−２〜４−ｎのいずれかから送出されたパケットを受信すると共に、受信したパケットを後述する最終送信先データに基づいてパケット交換機４−２〜４−ｎのいずれかに送出する。
もっとも、パケット交換機４−１にパケットを送信するのは、パーソナルコンピュータなどの端末でもよく、パケット交換機４−１からのパケットの送出先はパーソナルコンピュータなどの端末でもよい。
【００９７】
図１８は、図１７のパケット交換網で送信されるパケットのデータフォーマットを示す図である。
図示するように、送信すべきデータは、所定長のパケットに分割されている。各パケットには、当該パケットの最終送信先のデータが付される。同一の送信すべきデータから分割された複数のパケットに付されている最終送信先のデータは、すべて同一である。また、各パケットには、分割されたパケットを再度組み立てるための管理情報が付される。
【００９８】
図１９は、図１７のパケット交換機４−１の構成を示すブロック図である。なお、他のパケット交換機４−２〜４−ｎは、パケット交換機４−１と同一の構成であっても、異なる構成であってもよい。
図示するように、パケット交換機４−１は、ハードウェアテーブル４１と、ハードウェアテーブル管理部４２と、ＣＰＵ４３と、主記憶装置（ＭＭＵ）４４と、フラッシュメモリ４５とから構成されている。
【００９９】
ハードウェアテーブル４１は、受信したパケットに含まれる最終送信先データに基づいて、送出先情報をハードウェア的に抽出するものである。
ハードウェアテーブル４１は、図２０に示すように、メモリ４１１と、比較器４１２と、セレクタ４１３とから構成される。
【０１００】
メモリ４１１は、高速のＳＲＡＭによって構成され、パケットの最終送信先と次のパケット交換機４−２〜４−ｎを示す送出先情報とを対応づけて各アドレスに記憶する。メモリ４１１に記憶される最終送信先と送出先情報とは、後述するタイマ４２１からのトリガ信号によって後述するＣＰＵ４３の処理によって更新される。比較器４１２は、受信したパケットから抽出した最終送信先データとメモリ４１１の各アドレスに記憶されている最終送信先とを比較し、一致するものがあったときに、一致するもののアドレスに対応する制御信号をセレクタ４１３に出力する。比較器４１２は、一致するものがあった場合となかった場合とのそれぞれについて所定の制御信号をＣＰＵ４３に送る。セレクタ４１３は、比較器４１２からの制御信号に対応するメモリ４１１のアドレスに記憶されている送出先情報を選択して記憶する。
【０１０１】
ハードウェアテーブル管理部４２は、タイマ４２１と、ビットマップ４２２と、アドレスキュー４２３とを備える。タイマ４２１は、第１の実施の形態のデータ検索装置のタイマ１４と同様に構成されており、所定時間間隔でトリガ信号を発生する。ビットマップ４２２は、メモリ４１１の各アドレスに対応してそれぞれ１ビットずつ設けられており、対応するアドレスから送出先情報が抽出されたときに当該ビットが「１」にセットされる。ビットマップ４２２は、タイマ４２１が所定の時間間隔を計時する毎に参照されるが、例えば、過去１回分のビットマップの情報は、ＭＭＵ４４のワークエリアに記憶されている。アドレスキュー４２３は、タイマ４２１が所定の時間間隔を計時したときのビットマップ４２２の内容と、ワークエリアに記憶されている過去１回分のビットマップの内容とに基づいて、２所定期間続けて送出先情報の抽出がなかったメモリ４１１のアドレスを先入れ先出し方式で記憶するものである。
【０１０２】
ＣＰＵ４３は、ＭＭＵ４４に記憶されたプログラムを実行し、受信したパケットから抽出した最終送信先データに対応する送出先情報をフラッシュメモリ４５から抽出して出力する。また、ＣＰＵ４３は、ＭＭＵ４４に記憶されたプログラムの実行により、タイマ４２１が所定時間間隔を計測する毎に、ビットマップ４２２とＭＭＵ４４のワークエリアとを参照して、メモリ４１１に記憶する最終送信先と送出先情報とを更新するための処理を行う。ＣＰＵ４３は、一致があったことを示す制御信号を比較器４１２から受信したときは、送出先情報の抽出の処理を中止する。
【０１０３】
主記憶装置（ＭＭＵ）４４は、ＤＲＡＭによって構成され、ＣＰＵ４３の処理プログラムを記憶すると共に、ＣＰＵ４３のワークエリアとして用いられる。なお、フラッシュメモリ４５から送出先情報が抽出されたときには、受信したパケットが有する最終送信先データに対応する最終送信先と送出先情報とがＭＭＵ４４のワークエリアに一次記憶される。なお、前述したワークエリアに記憶されているビットマップの内容は、メモリ４１１に最終送信先と送信先情報とが更新されて書き込まれたときには、更新されたアドレスに対応するビットは「１」にセットされる。
【０１０４】
フラッシュメモリ４５は、ブロック毎にデータの一括消去が可能な不揮発性の記憶媒体であり、対象となるパケットの最終送信先のすべてと、これらの最終送信先のそれぞれに対応する次のパケットの送信先となるパケット交換機４−２〜４−ｎを示す送出先情報を記憶する。
【０１０５】
以下、このパケット交換機４−１における動作について説明する。
パケット交換機４−１では、接続されているパケット交換機４−２〜４−ｎのいずれかからパケットを受信すると、そのパケットに含まれている最終送信先データがデータ抽出手段（図示せず）によって抽出される。抽出された最終送出先データは、ハードウェアテーブル４１の比較器４１２に供給されると共に、ＣＰＵ４３に供給される。
【０１０６】
ハードウェアテーブル４１では、受信したパケットから抽出された最終送信先データと一致する最終送信先がメモリ４１１のいずれかのアドレスに記憶されているかどうかが比較器４１２によって調べられる。比較器４１２による比較の結果、一致する最終送信先があるときには、その最終送信先を記憶するアドレスに対応する制御信号がセレクタ４１３に供給されると共に、一致を示す制御信号がＣＰＵ４３に供給される。セレクタ４１３は、比較器４１２から供給された制御信号に基づいて、メモリ４１１の対応するアドレスに記憶されている送出先情報を出力する。また、ビットマップ４２２の複数のビットのうち、送出先情報が抽出されたアドレスに対応するビットが「１」にセットされる。そして、セレクタ４１３から出力された送出先情報に基づいて、受信したパケットがパケット交換機４−２〜４−ｎのいずれかに出力される。
【０１０７】
ＣＰＵ４３は、所定の処理プログラムに基づいて、受信したパケットから抽出された最終送信先データと一致する最終送信先に対応する送出先情報をフラッシュメモリ４５から読み出す。この読み出しの処理の間に、比較器４１２から一致を示す制御信号を受け取ったときは、ＣＰＵ４３はこの処理を中止する。一方、比較器４１２から不一致を示す制御信号を受け取ったときは、ＣＰＵ４３は読み出しの処理を続行し、読み出した送出先情報を出力する。こうして送出先情報が出力されたときは、最終送信先と送出先情報とがＭＭＵ４４のワークエリアに記憶される。そして、ＣＰＵ４３から出力された送出先情報に基づいて、受信したパケットがパケット交換機４−２〜４−ｎのいずれかに出力される。
【０１０８】
このようなパケットの受信、送出が次々と行われている間に、タイマ４２１は、そのダウンカウンタの値がクロックに基づいてカウントダウンされている。そして、ダウンカウンタの値が「０」となったときに、トリガ信号を発生し、ＣＰＵ４３に供給する。
【０１０９】
ＣＰＵ４３は、トリガ信号が入力されると、ハードウェアテーブル管理部４２のビットマップ４２２の内容を読み出す。ＣＰＵ４３は、また、ＭＭＵ４４のワークエリアに記憶されている最終送信先と送出先情報とをメモリ４１１のアドレスキュー４２３の先頭に記憶されているアドレスから順次記憶していく。但し、読み出したビットマップ４２２の対応するビットが「１」にセットされているアドレスは除かれる。これにより、前回のトリガ信号の入力から今回のトリガ信号の入力までの所定時間間隔で送出先情報が抽出された最終送信先と対応する送出先情報とがメモリ４１１に記憶されることとなる。
【０１１０】
ＣＰＵ４３は、さらに、読み出したビットマップ４２２の内容をＭＭＵ４４のワークエリアに記憶させる。そして、前回の処理でＭＭＵ４４のワークエリアに記憶されたビットマップの内容と読み出したビットマップとの内容とに基づいて、２所定時間間隔で連続して送出先情報の抽出が行われていないメモリ４１１のアドレスをアドレスキュー４２３に記憶させる。また、読み出したビットマップ４２２の対応するビットが「１」にセットされているアドレスがアドレスキュー４２３に記憶されている場合は、当該アドレスをアドレスキュー４２３から削除する。これにより、送出先情報の抽出がないアドレスがほぼ抽出のない期間順でアドレスキュー４２３に先頭から記憶されることになる。
【０１１１】
以上説明したように、この実施の形態のパケット交換機では、受信したパケットに含まれる最終送信先データに対応する最終送信先と送出先情報とは、タイマ４２１が計測する所定時間間隔で更新されてメモリ４１１に記憶される。そして、このメモリ４１１に記憶されることによってハードウェア的に高速に送出先情報の抽出が可能となる。従って、パケット交換機の処理能力が非常に向上する。
【０１１２】
一方、メモリ４１１に記憶される最終送信先と送出先情報との更新は、タイマ４２１が所定時間間隔を計測した場合のみである。このため、メモリ４１１に記憶される最終送信先と送出先情報との更新の処理によるオーバーヘッドによって、本来の処理である送出先情報の抽出に影響が生じることが少ない。
【０１１３】
さらに、この実施の形態のパケット交換機は、ハードウェアによる送出先情報の抽出を頻度が高いことが予想されるものだけとしている。従って、コスト的な負担をそれほど大きくすることなく、パケット交換機の処理能力を大幅に向上させることができる。
【０１１４】
［実施の形態の変形］
本発明は、上記の第１〜第７の実施の形態のものに限定されるものではなく、種々の変形が可能である。以下、本発明の実施の形態の変形態様について説明する。
【０１１５】
上記の第１〜第６の実施の形態では、プロセスの参照頻度を管理するためのリスト２４は、単方向リストによって構成されていたが、双方向リストであってもよい。また、要素がポインタでつながれている構造のものであれば、例えば、木構造リストなどであっても構わない。
【０１１６】
上記の第１〜第５の実施の形態では、トリガ信号を発生するための設定値の初期値は、タイマ１４内部に予めセットされているか、或いはリスト管理タスク２３の処理によってセットされていた。しかしながら、これをオペレータが外部からの操作入力によって設定できるようにしてもよい。また、第３の実施の形態で示した設定値の増減値も、オペレータが外部からの操作入力によって設定できるようにしてもよい。
【０１１７】
上記の第２、第４の実施の形態では、カウント値が所定値より小さいプロセス数が閾値と同一であるときは、タイマ１４の内部レジスタにセットする設定値の増減を行っていなかった。しかしながら、この場合に、設定値の増加または減少のいずれかを行ってもよい。
【０１１８】
上記の第４の実施の形態では、トリガ信号Ａ、Ｂのいずれについても、ビットマップ２１の各カウンタの値によってその発生間隔が調整されていたが、いずれか一方のみの発生間隔を調整するものとしても、いずれのトリガ信号の発生間隔を固定としてもよい。
【０１１９】
上記第１〜第５の実施の形態では、タイマ１４からのトリガ信号によってリスト２４の要素を並べ替える場合について説明した。上記の第６の実施の形態では、動作状態識別手段３１によるトリガ信号によってリスト２４の要素を並べ替える場合について説明した。本発明では、タイマと動作状態識別手段との双方からの識別信号によってリスト２４の要素を並べ替える場合にも適用することができる。
【０１２０】
上記の第７の実施の形態では、ビットマップ４２２自体の内容とＭＭＵ４４のワークエリアに記憶された過去１回分のビットマップの内容の合計２回分のビットマップの内容に従って、メモリ４１１のアドレスがアドレスキュー４２３に記憶されていた。しかしながら、本発明は、上記のようなアドレスキュー４２３を有さず、ビットマップ４２２自体の内容に従って、メモリ４１１に記憶する最終送信先と送出先情報とを更新する場合にも適用することができる。また、ワークエリアに記憶するビットマップの内容は過去２回分以上であってもよい。
【０１２１】
上記の第７の実施の形態では、メモリ４１１に記憶する最終送信先と送出先情報との更新は、タイマ４２１のトリガ信号の発生のみによって行われていた。しかしながら、第７の実施の形態のパケット交換機でも、第６の実施の形態で示したのと同様の動作状態識別装置３１を設け、ＣＰＵ４３がアイドル状態にある時、或いはパケットの交換処理を行っていないときに、に最終送信先と送出先情報との更新を行ってもよい。また、第１の実施の形態の場合と同様に、送出先情報がフラッシュメモリ４５から読み出されたときに、その場合の最終送信先と送出先情報とを、メモリ４１１のアドレスキュー４２３の最初に記憶されているアドレスに上書きして更新してもよい。
【０１２２】
上記の第１〜第６の実施の形態で説明したデータ検索タスク２２或いはリスト管理タスク２３の処理を実現するためのプログラムは、例えば、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記憶した形式で提供してもよい。そして、このような記録媒体に記憶されたプログラムを磁気ディスク装置１３にインストールしてもよい。
【０１２３】
上記の第１〜第７の実施の形態では、本発明をパケット交換機などでパケットの送信先のデータを検索するためのデータ検索装置に適用し、パケットの送信先データを資源使用のためのプロセスとし、プロセスの参照頻度をリストによって管理する場合について説明した。しかしながら、本発明は、仮想記憶におけるページの参照頻度や、キャッシュメモリにおけるブロックの参照頻度を管理するためのリストなどにも適用することができる。これらの場合、仮想記憶におけるページやキャッシュメモリにおけるブロックが、上記のプロセスに対応するものとなる。また、当該ページやブロックからプログラム（命令）を読み出すことや、当該ページやブロックにデータの読み書きを行うことが、上記のプロセスの参照に対応するものとなる。
【０１２４】
【発明の効果】
以上説明したように、本発明のパケット交換機では、カウント手段のカウント値に基づいて、すなわち、受信したパケットの最終送信先の数に基づいて、高速メモリによって構成される第２の記憶手段に記憶される最終送信先と送出先情報とが所定時間毎に更新される。そして、第２の記憶手段に受信したパケットに含まれる最終送信先のデータが第２の記憶手段に記憶されているときは、ここから高速に送出先情報が抽出される。このため、パケット交換機の処理能力が向上する。一方、第２の記憶手段の記憶内容の更新は、計時手段が所定の時間間隔を計時することで行われるため、この記憶内容の更新のオーバーヘッドによって、本来の処理である送出先情報の抽出の能力が低下することがない。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態にかかるデータ検索装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態にかかるデータ検索装置の機能を示す機能ブロック図である。
【図３】本発明の第１の実施の形態におけるリスト管理の処理を示すフローチャートである。
【図４】ビットマップのカウンタの値を示す図であり、（Ａ）はトリガ信号入力前のものを、（Ｂ）はトリガ信号入力後のものを示す。
【図５】リストの接続順を示す図であり、（Ａ）はトリガ信号入力前のものを、（Ｂ）はトリガ信号入力後のものを示す。
【図６】本発明の第１の実施の形態における動作を示すタイミングチャートである。
【図７】本発明の第１の実施の形態の比較例（従来例）における動作を示すタイミングチャートである。
【図８】本発明の第２の実施の形態におけるリスト構造を示す図である。
【図９】本発明の第２の実施の形態におけるリスト管理の処理を示すフローチャートである。
【図１０】本発明の第３の実施の形態におけるリスト管理の処理を示すフローチャートである。
【図１１】本発明の第４の実施の形態におけるトリガ信号Ａ時のリスト管理の処理を示すフローチャートである。
【図１２】本発明の第４の実施の形態におけるトリガ信号Ｂ時のリスト管理の処理を示すフローチャートである。
【図１３】本発明の第５の実施の形態にかかるデータ検索装置の機能を示す機能ブロック図である。
【図１４】本発明の第５の実施の形態におけるリスト管理の処理を示すフローチャートである。
【図１５】本発明の第６の実施の形態にかかるデータ検索装置の構成を示すブロック図である。
【図１６】本発明の第６の実施の形態にかかるデータ検索装置の機能を示す機能ブロック図である。
【図１７】本発明の第７の実施の形態にかかるパケット交換網を示すブロック図である。
【図１８】パケットのデータフォーマットを示す図である。
【図１９】図１７のパケット交換機の構成を示すブロック図である。
【図２０】図１９のハードウェアテーブルの構成を示すブロック図である。
【符号の説明】
１１  ＣＰＵ
１２  主記憶装置（ＭＭＵ）
１３  磁気ディスク装置
１４  タイマ
１５  インタフェース（Ｉ／Ｆ）
２０  キャッシュ領域
２１  ビットマップ
２２  データ検索タスク
２３  リスト管理タスク
２４  リスト
３１  動作状態識別装置
４−１〜４−ｎ  パケット交換機
４１  ハードウェアテーブル
４２  ハードウェアテーブル管理部
４３  ＣＰＵ
４４  主記憶装置（ＭＭＵ）
４５  フラッシュメモリ
【図１】
0003541817.tif 000002
【図２】
0003541817.tif 000003
【図３】
0003541817.tif 000004
【図４】
0003541817.tif 000005
【図５】
0003541817.tif 000006
【図６】
0003541817.tif 000007
【図７】
0003541817.tif 000008
【図８】
0003541817.tif 000009
【図９】
0003541817.tif 000010
【図１０】
0003541817.tif 000011
【図１１】
0003541817.tif 000012
【図１２】
0003541817.tif 000013
【図１３】
0003541817.tif 000014
【図１４】
0003541817.tif 000015
【図１５】
0003541817.tif 000016
【図１６】
0003541817.tif 000017
【図１７】
0003541817.tif 000018
【図１８】
0003541817.tif 000019
【図１９】
0003541817.tif 000020
【図２０】
0003541817.tif 000021