(57)【特許請求の範囲】
【請求項１】
スイッチを介して相互に接続された複数のパケット転送装置を有し、該パケット転送装置のそれぞれが、自装置に接続されたネットワークから宛先に関する情報を含むヘッダ情報が付与されたパケットを受信し、該受信パケットを、前記ヘッダ情報に基づいて、前記宛先となるネットワークが接続されたパケット転送装置に転送するパケット処理システムであって、
前記複数のパケット転送装置のそれぞれと前記スイッチを介して接続された外部バッファ装置を有し、
前記複数のパケット転送装置のそれぞれは、前記受信パケットを転送するためのパケット処理に対する負荷の状態が、自装置内に保持した前記受信パケットの量が閾値より少ない低負荷状態から前記受信パケットの量が前記閾値より大きな別の閾値を超える高負荷状態に遷移すると、自装置で処理しきれないパケットを前記外部バッファ装置へ送信して保持させ、前記負荷の状態が前記高負荷状態から前記低負荷状態に遷移すると、前記外部バッファ装置から前記保持させたパケットを取得し、該取得したパケットに対する前記パケット処理を実行するように構成されており、
さらに、前記複数のパケット転送装置のそれぞれは、前記低負荷状態から前記高負荷状態への遷移時から前記高負荷状態から前記低負荷状態への遷移時までの期間中に自装置が前記外部バッファ装置へ送信したパケットの数をカウントしてその値を保持するとともに、前記高負荷状態から前記低負荷状態への遷移後、前記外部バッファ装置からパケットを受信する度に、タイマーを所定値にセットし、カウントダウンを始め、該タイマーが切れた場合に、および、前記外部バッファ装置から取得したパケットの数が前記保持したカウント値と一致した場合に、前記外部バッファ装置から取得したパケットに対する前記パケット処理を実行する、パケット処理システム。
【請求項２】
前記複数のパケット転送装置のそれぞれは、
内部バッファと、
供給されたパケットを順に蓄積する監視キューと、
前記監視キューに格納されたパケットのキュー長が第１の閾値を超えると、前記高負荷状態を示す第１の信号を送出し、前記キュー長が前記第１の閾値より小さな第２の閾値を下回ると、前記低負荷状態を示す第２の信号を送出するキュー監視部と、
供給されたパケットの転送順のスケジューリングを行うスケジューラと、
前記監視キューから蓄積したパケットを蓄積順に取り出して前記パケット処理を実行し、該パケット処理を施したパケットを前記スケジューラに供給するパケット処理部と、
自装置と接続された前記ネットワークから到着するパケットを入力とし、前記キュー監視部から前記第１の信号を受信すると、該入力パケットを直接、前記スケジューラに供給し、前記第１の信号を受信した後に前記キュー監視部から前記第２の信号を受信すると、該入力パケットを前記内部バッファに供給するとともに、前記第２の信号の受信直後に前記スケジューラに供給されるパケットのヘッダに、前記外部バッファ装置に保持されている当該パケット転送装置から送信したパケットを返送する旨の返送指示を付与するパケットスキップ部と、を有し、
前記パケットスキップ部は、前記返送指示に応じて前記外部バッファ装置が返送したパケットを全て前記監視キューに供給した後、前記内部バッファに格納したパケットを前記監視キューに供給する、請求項１に記載のパケット処理システム。
【請求項３】
前記外部バッファ装置は、
パケット用バッファと、
前記複数のパケット転送装置から、自装置で処理しきれない前記パケットを受信し、該受信したパケットを、パケット転送装置毎に、受信した順序で前記パケット用バッファに格納するバッファリング部と、を有し、
前記バッファリング部は、前記パケット用バッファに格納したパケットの送信元であるパケット転送装置から返送指示を受けると、該パケット転送装置に関するパケットを、前記受信した順序で前記パケット用バッファから読み出して該パケット転送装置に返送する、請求項１または２に記載のパケット処理システム。
【請求項４】
前記複数のパケット転送装置は、自装置で処理しきれない前記パケットとして、送信元を識別可能な識別子と返送の有無を示す返送指示情報とを含むヘッダ情報が付与されたパケットを前記外部バッファ装置に向けて送信し、
前記バッファリング部は、
前記複数のパケット転送装置のいずれかの装置から、自装置で処理しきれない前記パケットを受信すると、該受信パケットのヘッダ情報に基づいて、該受信パケットの送信元のパケット転送装置を特定するとともに、返送指示の有無を確認するヘッダ解析部と、
前記ヘッダ解析部で特定される送信元のパケット転送装置毎に、前記パケット用バッファにおけるメモリ領域を割り当てるメモリ領域割り当て部と、
前記複数のパケット転送装置から受信した、自装置で処理しきれない前記パケットを、前記メモリ領域割り当て部で割り当てた、対応するメモリ領域に格納するとともに、前記ヘッダ解析部が、特定した前記送信元のパケット転送装置からのパケットについて、返送指示が有ると判断した場合に、特定した前記送信元のパケット転送装置に関するパケットを、前記パケット用バッファの対応するメモリ領域から読み出すパケットリード／ライト部と、を有する、請求項３に記載のパケット処理システム。
【請求項５】
送信元のパケット転送装置が、自装置に接続されたネットワークから宛先に関する情報を含むヘッダ情報が付与されたパケットを受信し、該受信パケットを、前記ヘッダ情報に基づいて、前記宛先となるネットワークが接続されたパケット転送装置に転送する第１のステップと、
前記送信元のパケット転送装置が、前記受信パケットを転送するためのパケット処理に対する負荷の状態が、自装置内に保持した前記受信パケットの量が閾値より少ない低負荷状態から前記受信パケットの量が前記閾値より大きな別の閾値を超える高負荷状態に遷移すると、自装置で処理しきれないパケットを外部バッファ装置へ送信して保持さ、前記負荷の状態が前記高負荷状態から前記低負荷状態に遷移すると、前記外部バッファ装置から前記保持させたパケットを取得し、該取得したパケットに対する前記パケット処理を実行する第２のステップと、を含み、
前記第２のステップは、前記送信元のパケット転送装置が、前記低負荷状態から前記高負荷状態への遷移時から前記高負荷状態から前記低負荷状態への遷移時までの期間中に自装置が前記外部バッファ装置へ送信したパケットの数をカウントしてその値を保持するとともに、前記高負荷状態から前記低負荷状態への遷移後、前記外部バッファ装置からパケットを受信する度に、タイマーを所定値にセットし、カウントダウンを始め、該タイマーが切れた場合に、および、前記外部バッファ装置から取得したパケットの数が前記保持したカウント値と一致した場合に、前記外部バッファ装置から取得したパケットに対する前記パケット処理を実行するステップを含む、パケット処理方法。
【請求項６】
前記第２のステップは、
自装置と接続された前記ネットワークから到着したパケットを到着順に監視キューに格納するステップと、
前記監視キューから蓄積したパケットを蓄積順に取り出して前記パケット処理を実行するステップと、
前記監視キューに格納されたパケットのキュー長が第１の閾値を超えると、前記パケット処理の負荷が前記高負荷状態であると判断し、前記キュー長が前記第１の閾値より小さな第２の閾値を下回ると、前記パケット処理の負荷が前記低負荷状態であると判断するステップと、を含む、請求項５に記載のパケット処理方法。
【請求項７】
ネットワークに接続されるネットワーク側インタフェースと、
他のパケット転送装置および外部バッファ装置のそれぞれとバックプレーンを介して接続されるバックプレーン側インタフェースと、
前記ネットワーク側インタフェースを通じて前記ネットワークから宛先に関する情報を含むヘッダ情報が付与されたパケットを受信し、該受信パケットを、前記ヘッダ情報に基づいて、前記宛先となるネットワークが接続されたパケット転送装置に、前記バックプレーン側インタフェースを通じて転送するプロセッサとを有し、
前記プロセッサは、前記受信パケットを転送するためのパケット処理に対する負荷の状態が、自装置内に保持した前記受信パケットの量が閾値より少ない低負荷状態から前記受信パケットの量が前記閾値より大きな別の閾値を超える高負荷状態に遷移すると、自装置で処理しきれないパケットを前記外部バッファ装置へ送信して保持させ、前記負荷の状態が前記高負荷状態から前記低負荷状態に遷移すると、前記外部バッファ装置から前記保持させたパケットを取得し、該取得したパケットに対する前記パケット処理を実行する、パケット転送装置であって、
前記プロセッサは、前記低負荷状態から前記高負荷状態への遷移時から前記高負荷状態から前記低負荷状態への遷移時までの期間中に自装置が前記外部バッファ装置へ送信したパケットの数をカウントしてその値を保持するとともに、前記高負荷状態から前記低負荷状態への遷移後、前記外部バッファ装置からパケットを受信する度に、タイマーを所定値にセットし、カウントダウンを始め、該タイマーが切れた場合に、および、前記外部バッファ装置から取得したパケットの数が前記保持したカウント値と一致した場合に、前記外部バッファ装置から取得したパケットに対する前記パケット処理を実行する、パケット転送装置。
【請求項８】
ネットワークに接続されるとともに、他のパケット転送装置および外部バッファ装置のそれぞれとバックプレーンを介して接続されるパケット転送装置に用いられるプログラムであって、
前記ネットワークから宛先に関する情報を含むヘッダ情報が付与されたパケットを受信し、該受信パケットを、前記ヘッダ情報に基づいて、前記宛先となるネットワークが接続されたパケット転送装置に転送する第１の処理と、
前記受信パケットを転送するためのパケット処理に対する負荷の状態が、自装置内に保持した前記受信パケットの量が閾値より少ない低負荷状態から前記受信パケットの量が前記閾値より大きな別の閾値を超える高負荷状態に遷移すると、自装置で処理しきれないパケットを前記外部バッファ装置へ送信して保持させ、前記負荷の状態が前記高負荷状態から前記低負荷状態に遷移すると、前記外部バッファ装置から前記保持させたパケットを取得し、該取得したパケットに対する前記パケット処理を実行する第２の処理と、を前記パケット転送装置のコンピュータに実行させ、
前記第２の処理は、前記低負荷状態から前記高負荷状態への遷移時から前記高負荷状態から前記低負荷状態への遷移時までの期間中に自装置が前記外部バッファ装置へ送信したパケットの数をカウントしてその値を保持するとともに、前記高負荷状態から前記低負荷状態への遷移後、前記外部バッファ装置からパケットを受信する度に、タイマーを所定値にセットし、カウントダウンを始め、該タイマーが切れた場合に、および、前記外部バッファ装置から取得したパケットの数が前記保持したカウント値と一致した場合に、前記外部バッファ装置から取得したパケットに対する前記パケット処理を実行する処理を含む、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ通信システムに関し、特に、ネットワークから受信したデータパケットをその宛先のネットワークへ転送するパケット処理システムに関する。
【背景技術】
【０００２】
ネットワークと回線を介して接続され、ネットワークから到着したパケットを、そのヘッダに格納されている宛先情報に応じて宛先のネットワークへと転送するパケット処理システムが知られている。このパケット処理システムは、それぞれがネットワークに接続された複数のパケット転送装置と、これらパケット転送装置が接続されるスイッチとから構成される。パケット転送装置は、パケットの送受信、パケットのあて先の調査、パケットの転送順のスケジューリングなどを行う。スイッチは、パケット転送装置から転送されたパケットを適切なパケット転送装置へと送り届ける。
【０００３】
パケット転送装置には、パケットを処理するためのプロセッサが内蔵されている。プロセッサの負荷は、パケットに施すプロトコルの数や経路情報などの検索時間に応じて変化する。プロセッサの負荷状況によっては、パケット転送装置に到着するパケットの量が、プロセッサが処理することができるデータ量を超える場合がある。そのような場合は、プロセッサの負荷が軽くなるまで、到着したパケットをパケット転送装置内に設けられた内部バッファに蓄積する。内部バッファは、一定数のパケットが蓄積できる容量を有する。これにより、パケット廃棄の回数を減らすことが可能となる。
【０００４】
非特許文献１には、出力側のポートで輻輳が発生すると、共有バッファにパケットを一旦退避させる技術が記載されている。
【０００５】
また、非特許文献２には、配下のエッジルータを共有バッファとして用いる光パケットルータが記載されている。この光パケットルータでは、出回線で衝突したパケットを一時的にエッジルータで電気変換して保持する。出回線に空きができた時点で、光パケットルータは、エッジルータで保持してあったパケットを再び送出する。
【非特許文献１】D.Pao, S.Leung, "Sharing buffer in an input-output buffered ATM switch without scaling up memory bandwidth requirement" ,Computer Communications and Networks, 1995. Proceedings., Fourth International Conference on 20-30 sept. 1995 Page(s):339-343
【非特許文献２】佐々木純、高橋達郎、”エッジルータを共通バッファとして用いる光パケットルータのトラヒック制御法”、電子情報通信学会論文誌Vol J87, No.7 pp.963-971
【発明の開示】
【発明が解決しようとする課題】
【０００６】
パケット転送装置内にバッファを有するものにおいては、パケット転送装置に到着するパケットの量が、プロセッサが処理することができるデータ量を超える場合に、パケットをバッファに蓄積することで、パケット廃棄を回避することができる。しかし、この場合は、輻輳時にプロセッサが処理することができる量を超えて到着するパケットの量が、内部バッファの容量を超えた場合には、内部バッファの容量を超えた分については、パケット廃棄を回避することは困難である。確実にパケット廃棄を回避するためには、プロセッサが処理することができるデータ量を超えて到着し得るパケットの最大量に応じた記憶容量を有する内部バッファを用いる必要がある。しかし、この場合は、記憶容量の大きな内部バッファを各パケット転送装置に設けることになるため、パケット転送装置およびシステムのコストが高くなる他、パケット転送装置自体の消費電力も増大する。
【０００７】
非特許文献１，２に記載のものはいずれも、出力側のポート（出回線）における輻輳によるパケットの廃棄を回避することを目的としており、入力側のポート（入回線）では、全てのパケットが処理できていることを前提にしている。一方、上記の問題は入力側のポートでパケット処理ができない状況において生じるものである。よって、これら非特許文献１，２に記載のものでは、上記の問題を解決することはできない。
【０００８】
本発明の目的は、上記問題を解決し、各パケット転送装置に大容量の内部バッファを設ける必要がなく、輻輳によるパケットの廃棄を確実に回避することのできる、低コストのパケット処理システムを提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明のパケット処理システムは、
スイッチを介して相互に接続された複数のパケット転送装置を有し、該パケット転送装置のそれぞれが、自装置に接続されたネットワークから宛先に関する情報を含むヘッダ情報が付与されたパケットを受信し、該受信パケットを、前記ヘッダ情報に基づいて、前記宛先となるネットワークが接続されたパケット転送装置に転送するパケット処理システムであって、
前記複数のパケット転送装置のそれぞれと前記スイッチを介して接続された外部バッファ装置を有し、
前記複数のパケット転送装置のそれぞれは、前記受信パケットを転送するためのパケット処理に対する負荷の状態が、自装置内に保持した前記受信パケットの量が閾値より少ない低負荷状態から前記受信パケットの量が前記閾値より大きな別の閾値を超える高負荷状態に遷移すると、自装置で処理しきれないパケットを前記外部バッファ装置へ送信して保持させ、前記負荷の状態が前記高負荷状態から前記低負荷状態に遷移すると、前記外部バッファ装置から前記保持させたパケットを取得し、該取得したパケットに対する前記パケット処理を実行する。
さらに、前記複数のパケット転送装置のそれぞれは、前記低負荷状態から前記高負荷状態への遷移時から前記高負荷状態から前記低負荷状態への遷移時までの期間中に自装置が前記外部バッファ装置へ送信したパケットの数をカウントしてその値を保持するとともに、前記高負荷状態から前記低負荷状態への遷移後、前記外部バッファ装置からパケットを受信する度に、タイマーを所定値にセットし、カウントダウンを始め、該タイマーが切れた場合に、および、前記外部バッファ装置から取得したパケットの数が前記保持したカウント値と一致した場合に、前記外部バッファ装置から取得したパケットに対する前記パケット処理を実行する。
【００１０】
上記のパケット処理システムによれば、各パケット転送装置は、自装置の負荷状態が高負荷状態なると、自装置で処理しきれないパケットを外部バッファ装置に格納しておき、自装置の負荷状態が低負荷状態になった時点で、外部バッファ装置に格納してあったパケットを処理するようになっている。外部バッファ装置は、各パケット転送装置に共通のものであり、各パケット転送装置に大容量の内部バッファを設ける必要はない。
【発明の効果】
【００１１】
本発明によれば、各パケット転送装置に大容量の内部バッファを設ける必要がないので、パケット転送装置のコストを削減することができ、かつ、システム全体のコストも削減することができる。加えて、大容量の内部バッファを必要としない分、パケット転送装置の消費電力を低減することができ、その結果、システム全体の消費電力も低減することができる。
【発明を実施するための最良の形態】
【００１２】
次に、本発明の実施形態について図面を参照して説明する。
【００１３】
図１は、本発明の一実施形態であるパケット処理システムの概略構成を示すブロック図である。図１を参照すると、パケット処理システムは、３台の転送装置１と、１つの外部バッファ装置２と、これら転送装置１および外部バッファ装置２がそれぞれ接続されるスイッチ３とから構成される。なお、スイッチ３に接続される転送装置１の数は、適宜変更することができる。
【００１４】
転送装置１および外部バッファ装置２のそれぞれはバックプレーンを介してスイッチ３に接続されており、転送装置１および外部バッファ装置２の各装置間でバックプレーンを通じたパケット交換が可能となっている。転送装置１は、ネットワークからパケットを受け取る。パケットを受信した転送装置は、受信パケットのヘッダの情報に基づいて宛先となる転送装置（送信先の転送装置）を認識し、その転送装置に向けて受信パケットを転送する。送信先の転送装置は、送信元の転送装置から受け取ったパケットを宛先のネットワーク上に送出する。送信元の転送装置は、自装置で処理しきれなくなったパケットを外部バッファ装置２に送る。外部バッファ装置２は、送信元の転送装置から受信したパケットを保持し、送信元の転送装置の負荷が低下した後に、その保持したパケットを送信元の転送装置へ戻す。
【００１５】
図２に、バックプレーンを流れるパケットに添付されるヘッダの構成を示す。図２を参照すると、パケットのヘッダは、送信先送信元識別子１０および返送フラグ１１からなる。送信先送信元識別子１０は、送信元の転送装置と送信先の転送装置の対応関係で一意に決まる識別子である。この送信先送信元識別子１０に基づいて、送信元の転送装置と送信先の転送装置を識別することができる。返送フラグ１１は、送信元の転送装置が外部バッファ装置２に対して、保持したパケットを返送するように指示するためのフラグである。パケットには、ヘッダに続いてペイロード１２が設けられている。このペイロード１２には、転送装置に到着した状態のままのパケットが格納される。
【００１６】
次に、外部バッファ装置２について説明する。外部バッファ装置２は、転送装置１から送られてきたパケットを到着順に蓄積する。このパケットの蓄積は、転送装置１から返送する旨の指示を受けるまで行われる。返送指示を受け取ると、外部バッファ装置２は、蓄積したパケットを到着した順に転送装置１へ送信する。
【００１７】
図３に、外部バッファ装置２の構成を示す。図３を参照すると、外部バッファ装置２は、送受信部２０、バッファリング部２１、およびバッファ２２を有する。送受信部２０は、バックプレーンを通じて転送装置１との間でパケットの送受信を行う。バッファリング部２１は、送受信部２０で受信したパケットのヘッダを解析してバッファ２２に格納する。
【００１８】
バッファリング部２１は、ヘッダ解析部２１ａ、メモリ領域割り当て部２１ｂ、およびパケットリード／ライト部２１ｃから構成される。ヘッダ解析部２１ａは、送受信部２０から供給されるパケットのヘッダを解析するものであって、パケットを送信した転送装置の情報を取得したり、返送フラグのチェックの有無を調べたりする。メモリ領域割り当て部２１ｂは、受信パケットを格納するためのメモリ領域（転送装置用バッファ）および転送装置−確保メモリ対応テーブル２２ａを転送装置ごとに用意する。パケットリード／ライト部２１ｃは、パケットを上書きしないようにバッファ２１ｃに書き込んだり、バッファ２１ｃからパケットを読み出したりする。
【００１９】
図４は、外部バッファ装置２の動作を説明するためのフローチャートである。外部バッファ装置２では、送受信部２０が転送装置１からパケットを受信する（ステップＳ１）。受信パケットは、送受信部２０からバッファリング部２１へ供給される。バッファリング部２１では、ヘッダ解析部２１ａが、受信パケットのヘッダ内にある送信元送信先識別子に基づいて、そのパケットの送信元の転送装置を割り出す（ステップＳ２）。
【００２０】
次に、パケットリード／ライト部２１ｃが、転送装置−確保メモリ対応テーブルを参照して、その割り出した送信元の転送装置に関するメモリ領域がバッファ２２内に存在するか否かを確認する（ステップＳ３）。メモリ領域が存在する場合は、パケットリード／ライト部２１ｃは、そのメモリ領域に存在するパケットが今回到着したパケットの前に到着したパケットであると判断し、バッファ２２内からパケットを転送する際の送信順序が逆転することがないように、今回到着したパケットをそのメモリ領域に格納する（ステップＳ４）。メモリ領域が存在しない場合は、メモリ領域割り当て部２１ｂが、送信元の転送装置に関するメモリ領域をバッファ２２内に確保して転送装置−確保メモリ対応テーブルを作成する（ステップＳ５）。
【００２１】
ステップＳ４、Ｓ５のいずれかの処理を実行後、ヘッダ解析部２１ａが、受信パケットのヘッダの返送フラグをチェックする（ステップＳ６）。返送フラグが「on」である場合は、ヘッダ解析部２１ａは、送信元の転送装置からバッファ２２に蓄積してあるパケットを返送する旨の指示を受けたと判断し、パケットリード／ライト部２１ｃに対して、返送指示のあったことを通知する。返送指示の通知を受けたパケットリード／ライト部２１ｃは、バッファ２２から、該当する送信元の転送装置のパケットを蓄積した順に読み出し、読み出したパケットを送受信部２０を通じて順次、転送元の転送装置へ送信する（ステップS７）。返送フラグが「off」である場合は、処理を終了し、次のパケットの到着を待つ。
【００２２】
次に、転送装置１の構成を具体的に説明する。図５に、転送装置１の主要部の構成を示す。図５を参照すると、転送装置１は、ネットワーク側インタフェース１００、デバイス間スイッチ１０１、バックプレーン側インタフェース１０２、プロセッサ１０３、および記憶部１０４からなる。
【００２３】
ネットワーク側インタフェース１００は、ネットワークと接続され、ネットワークを通じて信号を送受信する。バックプレーン側インタフェース１０２は、バックプレーンに接続され、バックプレーンを通じて信号を送受信する。記憶部１０４は、半導体メモリまたはＣＤ−ＲやＤＶＤに代表される記憶媒体を利用する記憶装置であって、転送装置１を動作させるためのプログラム１０４ａやデータが格納される。
【００２４】
デバイス間スイッチ１０１は、ネットワーク側インタフェース１００、バックプレーン側インタフェース１０２、およびプロセッサ１０３のそれぞれの間で信号の受け渡しを行う。プロセッサ１０３は、記憶部１０４に格納されたプログラムに従って種々の処理を実行する。プロセッサ１０３によって実行される処理としては、パケット送受信処理、パケットスキップ処理、パケット処理、キュー監視処理、スケジューリング処理などがある。
【００２５】
転送装置１では、ネットワークから到着したパケットは、ネットワーク側インタフェース１００で処理された後、プロセッサ１０３に送られる。プロセッサ１０３は、ネットワーク側インタフェース１００から供給されたパケットに対して必要な処理を実行する。プロセッサ１０３で処理が施されたパケットは、バックプレーン側インタフェース１０２に送られる。バックプレーン側インタフェース１０２は、プロセッサ１０３から受け取ったパケットを、バックプレーンを介して他の転送装置または外部バッファ装置２に送る。各インタフェース１００、１０２とプロセッサ１０３との間のパケットのやり取りは、デバイス間スイッチ１０１を介して行われる。デバイス間スイッチ１０１は、入力されたパケットをあて先へと出力する役割を果たす。なお、パケットの転送先は、各インタフェース１００、１０２やプロセッサ１０３で自由に設定することが可能である。このような装置間を結ぶインタフェースとしては、ＯＩＦ（Optical Networking Forum）で規定されたＳＰＩ４（System Packet Interface level 4）などがある。
【００２６】
図６に、プロセッサ１０３の概略構成を示す。図６を参照すると、プロセッサ１０３は、受信部１１０、内部バッファ１１１、パケットスキップ部１１２、キュー監視部１１３、監視キュー１１４、パケット処理部１１５、スケジューラ１１６、および送信部１１７から構成される。
【００２７】
受信部１１０は、デバイス間スイッチ１０１からパケットを受信する。パケット処理部１１５は、受信したパケットに対してあて先の調査などを含むパケット転送を行うのに必要な処理を行う。スケジューラ１１６は、パケットの転送順のスケジューリングを行う。送信部１１７は、スケジューラ１１６から出力されたパケットをデバイス間スイッチ１０１へ送出する。これら受信部１１０、パケット処理部１１５、スケジューラ１１６、および送信部１１７は従来の転送装置のプロセッサに備えられているものと基本的には同じものであり、これら各部に、パケットのメモリ上の格納位置やヘッダ情報などが書かれているパケット処理に必要な情報を与えることで、パケットに対する各処理が実行される。
【００２８】
パケットスキップ部１１２、キュー監視部１１３、および監視キュー１１４は、プロセッサ１０３の負荷が高くなったときに、パケットの処理を行わずに、パケットを外部バッファ装置２に送るための処理を行う部分である。
【００２９】
監視キュー１１４は、プロセッサ１０３のパケット処理機能の負荷状況を測定するためのキューであって、パケット処理部１１５の入力段に設けられている。監視キュー１１４には、受信部１１０で受信したパケットがパケットスキップ部１１２を介して供給されている。内部バッファ１１１は、パケットスキップ部１１２の処理で一時的に処理用データを保持する場合に使用される。
【００３０】
キュー監視部１１３は、監視キュー１１４に蓄えられたパケット処理用データのキュー長を監視するものである。図７に、キュー監視部１１３によるキュー長の監視を模式的に示す。キュー監視部１１３は、パケット処理用データのキュー長が第１の閾値（高負荷閾値）を超えると、パケット処理機能が高負荷状態になっていることを示す信号をパケットスキップ部１１２に供給し、パケット処理用データのキュー長が第２の閾値（低負荷閾値）を下回ると、パケット処理機能が低負荷状態になったことを示す信号をパケットスキップ部１１２に供給する。なお、転送装置の起動時は、パケット処理用データのキュー長は第２の閾値（スキップ処理解除閾値）を下回った状態にあるので、キュー監視部１１３は、低負荷状態である旨の信号をパケットスキップ部１１２に供給する。
【００３１】
パケットスキップ部１１２は、キュー監視部１１３から高負荷状態である旨の信号を受信すると、受信部１１０から供給されるパケットをスケジューラ１１６に供給する（スキップ処理）。また、パケットスキップ部１１２は、キュー監視部１１３から低負荷状態である旨の信号を受信すると、受信部１１０から供給されるパケットを監視キュー１１４に供給する（スキップ解除処理）。
【００３２】
上記のように構成されたプロセッサ１０３では、パケット処理に対する負荷が高くなると、すなわちパケット処理部１１５が輻輳を起こすと、パケットスキップ部１１２は、パケット処理用データを送る相手をパケット処理部１１５からスケジューラ１１６に変更する。そして、パケット処理部１１５での輻輳が解消されると、パケットスキップ部１１２は、データを送る相手をスケジューラ１１６からパケット処理部１１５に戻す。
【００３３】
図８に、キュー監視部１１３とパケットスキップ部１１２の動作状態の遷移図を示す。この動作状態によれば、以下の「状態１」〜「状態５」が繰り返えされる。
【００３４】
［状態１］
パケットスキップ部１１２は、パケット処理部１１５が低負荷状態のとき、すなわち、キュー監視部１１３から高負荷状態を示す信号を受信するまでは、到着したパケットの処理用データを監視キュー１１４に入れる。パケット処理部１１５は、リソースが空くと監視キュー１１４に入っているパケット処理用データを先頭から取り出し、取り出したデータを用いてパケットに処理を施した後、処理用データをスケジューラ１１６に送る。
【００３５】
［状態２］
パケット処理部１１５が高負荷状態になると、リソースがなかなか空かなくなるため、監視キュー１１４からパケットを取り出す頻度が減少する。パケットスキップ部１１２が処理用データを監視キュー１１４に入れる頻度が、パケット処理部１１５が監視キュー１１４から処理用データを取り出す頻度より大きくなると、監視キュー１１４のキュー長が増加する。キュー長が第１の閾値（高負荷閾値）を越えると、キュー監視部１１３がそれを検知して、パケットスキップ部１１２に対して、パケット処理部１１５が高負荷状態になったことを通知する。パケットスキップ部１１２は、高負荷状態である旨の通知を受信すると、パケット処理用データの送り先を監視キュー１１４からスケジューラ１１６に変更する。この変更の際、パケットスキップ部１１２は、スケジューラ１１６に送ったパケット処理用データの数をカウンタＡでカウントする。また、パケットスキップ部１１２は、スケジューラ１１６にパケット処理用データを送る際、データに対応するパケットが外部バッファ装置２に到着するように、バックプレーンに転送する際に添付されるヘッダの送信先が外部バッファ装置２になるように設定する。
【００３６】
［状態３］
監視キュー１１４にパケットが入らなくなるため、時間の経過とともに、監視キュー１１４のキュー長は減少する。キュー長が第２の閾値（低負荷閾値）を下回ると、キュー監視部１１３がそれを検知して、パケットスキップ部１１２に対して、パケット処理部１１５が低負荷状態になったことを通知する。パケットスキップ部１１２は、低負荷状態である旨の通知を受信すると、それ以降、ネットワークから供給されたパケットの処理用データを内部バッファ１１１に蓄積する。また、パケットスキップ部１１２は、外部バッファ装置２に対して、自転送装置から送られたパケットを送り返すよう指示するために、低負荷状態の通知を受けた直後にスケジューラ１１６へ送る処理用データに対応するパケットのバックプレーン用ヘッダの返送フラグを「on」にする。そして、パケットスキップ部１１２は、それまで動かしていたカウンタＡをストップさせ、そのカウント値を保持する。
【００３７】
［状態４］
外部バッファ装置２は、返送フラグが「on」とされたパケットを受信すると、それまで蓄積したあった送信元の転送装置に関するパケットを蓄積した順に読み出し、読み出したパケットを順次、送信元の転送装置へ返送する。外部バッファ装置２２から送り返されてきたパケットが転送装置に到着する。転送装置では、外部バッファ装置２から返送されたパケットが受信部１１０を介してパケットスキップ部１１２に供給される。パケットスキップ部１１２は、外部バッファ装置２から返送されたパケットの処理用データを監視キュー１１４に入れるとともに、外部バッファ装置２から到着したパケットの数をカウンタＢによりカウントする。
【００３８】
［状態５］
パケットスキップ部１１２は、カウンタＢのカウント値が、上記［状態３］で保持したカウントＡのカウント値（外部バッファ装置２に転送したパケット数）になると、外部バッファ装置２からのパケット返送が終了したとみなす。そして、パケットスキップ部１１２は、内部バッファ１１１からそれまで蓄積していたパケット処理用データを読み出して監視キュー１１４に入れる。パケット処理部１１５は、監視キュー１１４から蓄積された処理用データを読み出してパケット処理を行う。
【００３９】
なお、外部バッファ装置２から転送装置へパケットが送り返される際、カウンタＢを用いて、外部バッファ装置２からのパケット数をカウントしているが、この場合、外部バッファ装置２からのパケットが転送装置に到着するまでの間にロスすると、外部バッファ装置２からのパケット返送の終了を判断することができなくなる可能性がある。これを防ぐために、パケットスキップ部１１２は、外部バッファ装置２からパケットが到着するたびに、タイマーをセットし、一定時間経過しても次のパケットが到着しない場合は、外部バッファ装置２からのパケット返送が終了したものとみなす。
【００４０】
また、内部バッファ１１１内に蓄積されたパケット処理用データが全て読み出されると、上記の「状態１」に戻り、パケットスキップ部１１２が、ネットワークから到着するパケットの処理用データを直接監視キュー１１４に入れる。
【００４１】
以上の「状態１」〜「状態５」の動作サイクルを繰り返して、外部バッファ装置２への転送処理を実現する。
【００４２】
以上説明した本実施形態のパケット処理システムによれば、各転送装置１は、自装置の負荷状態が高負荷状態になると、自装置で処理しきれないパケットを外部バッファ装置２に格納しておき、自装置の負荷状態が低負荷状態になった時点で、外部バッファ装置２に格納してあったパケットを処理するようになっている。外部バッファ装置２は、各転送装置１に共通のものであり、各パケット転送装置１には、大容量の内部バッファを設ける必要はない。よって、転送装置１のコストを削減することができ、かつ、システム全体のコストも削減することができる。加えて、大容量の内部バッファを必要としない分、転送装置１の消費電力を低減することができ、その結果、システム全体の消費電力も低減することができる。
【００４３】
（他の実施形態）
上述の実施形態において、転送装置１のプロセッサ１０３は１つであるが、このプロセッサを、ネットワークからバックプレーンに送られるパケット用（入力側プロセッサ）と、バックプレーンからネットワークに送られるパケット用（出力側プロセッサ）とから構成してもよい。ここでは、本発明の他の実施形態であるパケット処理システムとして、そのような入力側プロセッサおよび出力側プロセッサを設けた転送装置を有するパケット処理システムを説明する。
【００４４】
本他の実施形態であるパケット処理システムの基本的な構成は、図１に示したシステムと同じであるが、転送装置１の構成が異なる。図９に、本発明の他の実施形態であるパケット処理システムに用いられる転送装置の構成を示す。
【００４５】
図９を参照すると、転送装置は、ネットワーク側インタフェース１００、デバイス間スイッチ１０１、転送先プロセッサ指定機能付きバックプレーン側インタフェース１０２ａ、パケット処理機能付き入力側プロセッサ１０３ａ、および出力側プロセッサ１０３ｂからなる。ネットワーク側インタフェース１００およびデバイス間スイッチ１０１は、図５に示したものと同じである。
【００４６】
この転送装置では、外部バッファ２からバックプレーン側インタフェース１０２ａに到着したパケットは、入力側プロセッサ１０３ａに供給される必要がある。これを実現するために、バックプレーン側インタフェース１０２ａは、パケットが到着すると、到着パケットのヘッダに格納されている送信元送信先識別子を参照して、外部バッファ２から到着したパケットならば入力側プロセッサ１０３ａに、そのほかのパケットならば出力側プロセッサ１０３ｂに送信する、といった出力プロセッサ指定処理を行う。
【００４７】
図１０に、バックプレーン側インタフェース１０２ａの主要部の構成を示す。図１０に示すように、バックプレーン側インタフェース１０２ａは、プロセッサ向け信号送受信部１０２０、出力プロセッサ指定部１０２１、およびバックプレーン向け信号送受信部１０２２からなる。出力プロセッサ指定部１０２１は、バックプレーン向け信号送受信部１０２２から渡されたパケットのヘッダの送信元送信先識別子を調べ、該パケットが外部バッファ２からの返送パケットであるか否かを判断する。返送パケットである場合は、出力プロセッサ指定部１０２１は、バックプレーン向け信号送受信部１０２２から渡されたパケットを入力側プロセッサ１０３ａへ送る。返送パケットでない場合は、出力プロセッサ指定部１０２１は、バックプレーン向け信号送受信部１０２２から渡されたパケットを出力側プロセッサ１０３ｂへ送る。
【００４８】
上記の返送パケットの判断において、外部バッファ２が送信元の転送装置に蓄積していたパケットを返送する際に、すべての返送パケットのヘッダの返送フラグを「ｏｎ」にするように構成し、出力プロセッサ指定部１０２１が、受信パケットのヘッダの返送フラグを調べ、返送フラグが「ｏｎ」となっているか否かで、外部バッファ２からの返送パケットであるか否かを判断してもよい。
【００４９】
入力側プロセッサ１０３ａは、出力プロセッサ指定部１０２１から受信したパケットに対して前述の実施形態で説明したパケット処理スキップの処理を実行する。出力側プロセッサ１０３ｂは、出力プロセッサ指定部１０２１から受信したパケット（バックプレーンを介して接続された他の転送装置が宛先となるネットワークと接続された当該転送装置に向けて送出したパケット）を受信した順に、ネットワーク側インタフェース１００からネットワーク上に送出するための処理を行う。
【００５０】
上述した各実施形態のパケット処理システムは、本発明の一例であり、その構成および動作は発明の趣旨を逸脱しない範囲で適宜に変更することができる。
【００５１】
以上説明した本発明のパケット処理システムは、データ通信網を構成するルータなどのネットワーク装置に適用することができる。図１１に、ネットワーク装置の構成を示す。図１１を参照すると、ネットワーク装置は、転送装置３０１ａ、３０１ｂ、外部バッファ装置３０２、スイッチ３０３、およびこれらを収容する筐体３０４からなる。筐体３０４の背面には、バックプレーンインタフェース３００が設けられている。転送装置３０１ａ、３０１ｂ、外部バッファ装置３０２、およびスイッチ３０３は、バックプレーンインタフェース３００に接続される。このネットワーク装置は、前述の各実施形態で説明したような処理を行うことができる。
【００５２】
バックプレーンインタフェースのトポロジは、スター型やメッシュ型などの任意のトポロジが使用可能である。一例として、図１２に、バックプレーンインタフェースのトポロジがメッシュ型のパケット処理システムの構成を示す。このパケット処理システムでは、転送装置１、外部バッファ装置２がそれぞれ個別に接続されたスイッチ３のそれぞれが、バックプレーンを介して相互に接続されている。なお、バックプレーンインタフェースのトポロジがスター型のパケット処理システムとしては、図１に示したパケット処理システムがある。
【図面の簡単な説明】
【００５３】
【図１】本発明の一実施形態であるパケット処理システムの概略構成を示すブロック図である。
【図２】バックプレーンを流れるパケットに添付されるヘッダの構成を説明するための図である。
【図３】図１に示す外部バッファ装置の主要部の構成を示すブロック図である。
【図４】図３に示す外部バッファ装置の動作を説明するためのフローチャートである。
【図５】図１に示す転送装置の主要部の構成を示すブロック図である。
【図６】図５に示すプロセッサの概略構成を示すブロック図である。
【図７】図６に示すキュー監視部によるキュー長の監視を説明するための模式図である。
【図８】図６に示すキュー監視部およびパケットスキップ部の動作を説明するための状態遷移図である。
【図９】本発明の他の実施形態であるパケット処理システムに用いられる転送装置の構成を示すブロック図である。
【図１０】図９に示すバックプレーン側インタフェースの主要部の構成を示すブロック図である。
【図１１】本発明のパケット処理システムを適用するネットワーク装置の構成を説明するための斜視図である。
【図１２】本発明の別の実施形態であるバックプレーンインタフェースのトポロジがメッシュ型のパケット処理システムの構成を示すブロック図である。
【符号の説明】
【００５４】
１  転送装置
２  外部バッファ装置
３  スイッチ
２０  送受信部
２１  バッファリング部
２２  バッファ
２１ａ  ヘッダ解析部
２１ｂ  メモリ領域割り当て部
２１ｃ  パケットリード／ライト部
１００  ネットワーク側インタフェース
１０１  デバイス間スイッチ
１０２  バックプレーン側インタフェース
１０３  プロセッサ
１０４  記憶部
【図１】
0004630231.tif 000002
【図２】
0004630231.tif 000003
【図３】
0004630231.tif 000004
【図４】
0004630231.tif 000005
【図５】
0004630231.tif 000006
【図６】
0004630231.tif 000007
【図７】
0004630231.tif 000008
【図８】
0004630231.tif 000009
【図９】
0004630231.tif 000010
【図１０】
0004630231.tif 000011
【図１１】
0004630231.tif 000012
【図１２】
0004630231.tif 000013