(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
【発明の開示】
【発明が解決しようとする課題】
【０００６】
パケット転送装置内にバッファを有するものにおいては、パケット転送装置に到着するパケットの量が、プロセッサが処理することができるデータ量を超える場合に、パケットをバッファに蓄積することで、パケット廃棄を回避することができる。しかし、この場合は、確実にパケット廃棄を回避するためには、プロセッサが処理することができるデータ量を超えて到着し得るパケットの最大量に応じた記憶容量を有するバッファを用意する必要がある。このように記憶容量の大きなバッファをパケット転送装置に設けることは、パケット転送装置のコストが高くなるばかりか、パケット転送装置の消費電力も増大する。
【０００７】
加えて、バッファに蓄積されたパケットに対する処理は、プロセッサの負荷がある程度低下するまで実行されない。このようにバッファに蓄積されたパケットは処理待ちの状態になるため、その分、ネットワークから到着したパケットをあて先のネットワークへ送信するまでに要する時間が長くなる。
【０００８】
非特許文献１，２に記載のものはいずれも、出力側のポート（出回線）における輻輳によるパケットの廃棄を回避することを目的としており、入力側のポート（入回線）では、全てのパケットが処理できていることを前提にしている。一方、上記の問題は入力側のポートでパケット処理ができない状況において生じるものである。よって、これら非特許文献１，２に記載のものでは、上記の問題を解決することはできない。
【０００９】
本発明の目的は、上記問題を解決し、大容量のバッファを必要とせず、輻輳によるパケットの処理待ちを抑制することのできる、低コストのパケット処理システムを提供することにある。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、第１の発明のパケット処理システムは、
別々のネットワークに接続される複数のパケット転送装置と、
前記複数のパケット転送装置が接続され、各パケット転送装置間におけるパケットの受け渡しを行うスイッチと、を有し、
前記複数のパケット転送装置のそれぞれは、自装置と接続されたネットワークから宛先に関する情報を含むヘッダ情報が付与されたパケットを受信し、該受信パケットを、前記ヘッダ情報に基づいて、前記宛先となるネットワークが接続された転送先のパケット転送装置に転送するプロセッサを有し、
前記受信パケットの転送元であるパケット転送装置において、前記プロセッサにおける前記受信パケットを転送するためのパケット処理に対する負荷の状態が、自装置内に保持した前記受信パケットの量が閾値より少ない低負荷状態から前記受信パケットの量が前記閾値より大きな別の閾値を超える高負荷状態に遷移した場合に、該プロセッサが処理することのできない受信パケットを、該プロセッサに代わって、他のパケット転送装置の前記プロセッサがパケット処理する、パケット処理システムであって、
前記転送元のパケット転送装置のプロセッサは、前記他のパケット転送装置に迂回させるパケットに迂回したパケットである旨を示す迂回フラグを付与し、
前記転送先のパケット転送装置のプロセッサは、
前記迂回フラグに基づいて、受信したパケットが前記転送元のパケット転送装置から直接受信した第１のパケットと前記他のパケット転送装置を迂回して受信した第２のパケットのいずれであるかを識別し、
受信した第１のパケットに対してパケット処理が実行される状態で、前記第２のパケットを受信した場合は、受信した第２のパケットを内部バッファに一時的に格納するとともに、前記第１のパケットを受信する度に、タイマーを所定値にセットし、新たにカウントダウンを始め、該タイマーが切れた場合に、前記第１のパケットよりなるパケット群の最後のパケットを受信したと判定して、前記内部バッファに格納した第２のパケットに対して前記パケット処理を実行し、
受信した第２のパケットに対してパケット処理が実行される状態で、前記第１のパケットを受信した場合は、受信した第１のパケットを前記内部バッファに一時的に格納するとともに、前記第２のパケットを受信する度に、タイマーを所定値にセットし、新たにカウントダウンを始め、該タイマーが切れた場合に、前記第２のパケットよりなるパケット群の最後のパケットを受信したと判定して、前記内部バッファに格納した第１のパケットに対してパケット処理を実行するように構成されている。
【００１１】
上記の第１の発明によれば、転送元のパケット転送装置がパケットを処理しきれなくなると、他のパケット転送装置が、転送元のパケット転送装置に代わって、その処理しきれなくなったパケットに対するパケット処理を行う。よって、各パケット転送装置は、処理しきれなくなったパケットを保持するための大容量のバッファを備える必要がない。
【００１２】
また、転送元のパケット転送装置によるパケット処理と他のパケット転送装置によるパケット処理とは並列に実行可能である。よって、従来のような、パケット転送装置が処理しきれなくなったパケットが処理待ちの状態になる、といった問題は生じない。
【００１３】
第２の発明のパケット処理システムは、
別々のネットワークに接続される複数のパケット転送装置と、
前記複数のパケット転送装置が接続され、各パケット転送装置間におけるパケットの受け渡しを行うスイッチと、
前記複数のパケット転送装置のそれぞれと前記スイッチを介して接続された少なくとも１つの共有転送装置を有し、
前記複数のパケット転送装置のそれぞれは、自装置と接続されたネットワークから宛先に関する情報を含むヘッダ情報が付与されたパケットを受信し、該受信パケットを、前記ヘッダ情報に基づいて、前記宛先となるネットワークが接続された転送先のパケット転送装置に転送するプロセッサを有し、
前記プロセッサは、前記受信パケットを転送するためのパケット処理に対する負荷の状態が、前記受信パケットの量が前記プロセッサによって処理可能な所定のデータ量より少ない低負荷状態から前記受信パケットの量が前記所定のデータ量を超える高負荷状態に遷移した場合に、前記受信パケットを、前記パケット処理を行わずに前記共有転送装置へ送信し、
前記共有転送装置は、高負荷状態となった前記プロセッサから受信したパケットに対して、該プロセッサに代わって前記パケット処理を実行し、該パケット処理を施したパケットを前記転送先のパケット転送装置に送信する、パケット処理システムであって、
前記受信パケットの転送元であるパケット転送装置のプロセッサは、前記共有転送装置に迂回させるパケットに迂回したパケットである旨を示す迂回フラグを付与し、
前記転送先のパケット転送装置のプロセッサは、
前記迂回フラグに基づいて、受信したパケットが前記転送元のパケット転送装置から直接受信した第１のパケットと前記共有転送装置を迂回して受信した第２のパケットのいずれであるかを識別し、
受信した第１のパケットに対してパケット処理が実行される状態で、前記第２のパケットを受信した場合は、受信した第２のパケットを内部バッファに一時的に格納するとともに、前記第１のパケットを受信する度に、タイマーを所定値にセットし、新たにカウントダウンを始め、該タイマーが切れた場合に、前記第１のパケットよりなるパケット群の最後のパケットを受信したと判定して、前記内部バッファに格納した第２のパケットに対してパケット処理を実行し、
受信した第２のパケットに対してパケット処理が実行される状態で、前記第１のパケットを受信した場合は、受信した第１のパケットを前記内部バッファに一時的に格納するとともに、前記第２のパケットを受信する度に、タイマーを所定値にセットし、新たにカウントダウンを始め、該タイマーが切れた場合に、前記第２のパケットよりなるパケット群の最後のパケットを受信したと判定して、前記内部バッファに格納した第１のパケットに対してパケット処理を実行するように構成されている。
【００１４】
第２の発明によれば、パケット転送装置がパケットを処理しきれなくなると、共有転送装置が、パケット転送装置に代わって、その処理しきれなくなったパケットに対するパケット処理を行う。よって、第２の発明においても、各パケット転送装置は、処理しきれなくなったパケットを保持するために、大容量のバッファを備える必要がない。
【００１５】
また、パケット転送装置によるパケット処理と共有転送装置によるパケット処理とは並列に実行可能である。よって、第２の発明においても、従来のような、パケット転送装置が処理しきれなくなったパケットが処理待ちの状態になる、といった問題は生じない。
【発明の効果】
【００１６】
本発明によれば、パケット転送装置のそれぞれに記憶容量の大きなバッファを設ける必要がないので、その分、パケット転送装置のコストを削減することができる。
【００１７】
また、パケット転送装置が処理しきれなくなったパケットが処理待ちの状態となることを抑制することができるので、従来のものと比較して、ネットワークから到着したパケットをあて先のネットワークへ送信するまでに要する時間を短くすることができる。
【発明を実施するための最良の形態】
【００１８】
次に、本発明の実施形態について図面を参照して説明する。
【００１９】
図１は、本発明の一実施形態であるパケット処理システムの概略構成を示すブロック図である。図１を参照すると、パケット処理システムは、３台の転送装置１と、１台の共有転送装置２と、これら転送装置１および共有転送装置２がそれぞれ接続されるスイッチ３とから構成される。なお、スイッチ３に接続される転送装置１および共有転送装置２の数は、適宜変更することができる。
【００２０】
転送装置１および共有転送装置２のそれぞれはバックプレーンを介してスイッチ３に接続されており、転送装置１および共有転送装置２の各装置間でバックプレーンを通じたパケット交換が可能となっている。転送装置１は、ネットワークからパケットを受け取る。パケットを受信した転送装置は、受信パケットのヘッダの情報に基づいて宛先となる転送装置（送信先の転送装置）を認識し、その転送装置に向けて受信パケットを転送する。送信先の転送装置は、送信元の転送装置から受け取ったパケットを宛先のネットワーク上に送出する。送信元の転送装置は、自装置で処理しきれなくなったパケットを共有転送装置２に送る。共有転送装置２は、送信元の転送装置から受信したパケットに対して、その送信元の転送装置に代わってパケット処理を行う。このパケット処理において、共有転送装置２は、受信パケットのヘッダの情報に基づいて送信先の転送装置を認識し、その転送装置に向けて受信パケットを転送する。
【００２１】
図２に、バックプレーンを流れるパケットに添付されるヘッダの構成を示す。図２を参照すると、パケットのヘッダは、送信先送信元識別子１０、迂回フラグ１１、および送信元転送装置固有情報１３からなる。送信先送信元識別子１０は、送信元の転送装置と送信先の転送装置の対応関係で一意に決まる識別子である。この送信先送信元識別子１０に基づいて、送信元の転送装置と送信先の転送装置を識別することができる。迂回フラグ１１は、転送装置１がパケットを共有転送装置２に送る際に、パケットを処理するよう指示するためのフラグである。転送装置１は、迂回フラグ１１を用いて共有転送装置２にパケットの処理を指示することができる。送信元転送装置固有情報１３は、転送装置１における入力ポートなどの情報であって、共有転送装置２のパケット処理に使用される。
【００２２】
パケットには、図２に示したヘッダに続いてペイロード１４が設けられている。このペイロード１４には、転送装置に到着した状態のままのパケットが格納される。
【００２３】
次に、転送装置１の構成を具体的に説明する。図３に、転送装置１の主要部の構成を示す。図３を参照すると、転送装置１は、ネットワーク側インタフェース１００、デバイス間スイッチ１０１、バックプレーン側インタフェース１０２、プロセッサ１０３、および記憶部１０４からなる。
【００２４】
ネットワーク側インタフェース１００は、ネットワークと接続され、ネットワークを通じて信号を送受信する。バックプレーン側インタフェース１０２は、バックプレーンに接続され、バックプレーンを通じて信号を送受信する。記憶部１０４は、半導体メモリまたはＣＤ−ＲやＤＶＤに代表される記憶媒体を利用する記憶装置であって、転送装置１を動作させるためのプログラムやデータが格納される。
【００２５】
デバイス間スイッチ１０１は、ネットワーク側インタフェース１００、バックプレーン側インタフェース１０２、およびプロセッサ１０３のそれぞれの間で信号の受け渡しを行う。プロセッサ１０３は、記憶部１０４に格納されたプログラムに従って種々の処理を実行する。プロセッサ１０３によって実行される処理としては、パケット送受信処理、パケットオーダリング用キュー処理、パケットスキップ処理、パケット処理、キュー監視処理、スケジューリング処理などがある。
【００２６】
転送装置１では、ネットワークから到着したパケットは、ネットワーク側インタフェース１００で処理された後、プロセッサ１０３に送られる。プロセッサ１０３は、ネットワーク側インタフェース１００から供給されたパケットに対して必要な処理を実行する。プロセッサ１０３で処理が施されたパケットは、バックプレーン側インタフェース１０２に送られる。バックプレーン側インタフェース１０２は、プロセッサ１０３から受け取ったパケットを、バックプレーンを介して他の転送装置または共有転送装置に送る。各インタフェース１００、１０２とプロセッサ１０３との間のパケットのやり取りは、デバイス間スイッチ１０１を介して行われる。デバイス間スイッチ１０１は、入力されたパケットをあて先へと出力する役割を果たす。なお、パケットの転送先は、各インタフェース１００、１０２やプロセッサ１０３で自由に設定することが可能である。このような装置間を結ぶインタフェースとしては、ＯＩＦ（Optical Networking Forum）で規定されたＳＰＩ４（System Packet Interface level 4）などがある。
【００２７】
図４に、プロセッサ１０３の概略構成を示す。図４を参照すると、プロセッサ１０３は、受信部１１０、パケットオーダリング用キュー処理部１１１、パケットスキップ部１１２、キュー監視部１１３、監視キュー１１４、パケット処理部１１５、スケジューラ１１６、および送信部１１７から構成される。
【００２８】
受信部１１０は、デバイス間スイッチ１０１からパケットを受信する。パケット処理部１１５は、受信したパケットに対してあて先の調査などを含むパケット転送を行うのに必要な処理を行う。スケジューラ１１６は、パケットの転送順のスケジューリングを行う。送信部１１７は、スケジューラ１１６から出力されたパケットをデバイス間スイッチ１０１へ送出する。これら受信部１１０、パケット処理部１１５、スケジューラ１１６、および送信部１１７は従来の転送装置のプロセッサに備えられているものと基本的には同じものであり、これら各部に、パケットのメモリ上の格納位置やヘッダ情報などが書かれているパケット処理に必要な情報を与えることで、パケットに対する各処理が実行される。
【００２９】
パケットスキップ部１１２、キュー監視部１１３、および監視キュー１１４は、プロセッサ１０３の負荷が高くなったときに、パケットの処理を行わずに、パケットを共有転送装置２に送るための処理を行う部分である。
【００３０】
監視キュー１１４は、プロセッサ１０３のパケット処理機能の負荷状況を測定するためのキューであって、パケット処理部１１５の入力段に設けられている。監視キュー１１４には、受信部１１０で受信したパケットがパケットオーダリング用キュー処理部１１１およびパケットスキップ部１１２を介して供給されている。
【００３１】
キュー監視部１１３は、監視キュー１１４に蓄えられたパケット処理用データのキュー長を監視するものである。図５に、キュー監視部１１３によるキュー長の監視を模式的に示す。キュー監視部１１３は、パケット処理用データのキュー長が第１の閾値（スキップ処理決定閾値）を超えると、パケット処理機能が高負荷状態になっていることを示す信号をパケットスキップ部１１２に供給し、パケット処理用データのキュー長が第２の閾値（スキップ処理解除閾値）を下回ると、パケット処理機能が低負荷状態になったことを示す信号をパケットスキップ部１１２に供給する。なお、転送装置の起動時は、パケット処理用データのキュー長は第２の閾値（スキップ処理解除閾値）を下回った状態にあるので、キュー監視部１１３は、低負荷状態である旨の信号をパケットスキップ部１１２に供給する。
【００３２】
パケットスキップ部１１２は、キュー監視部１１３から高負荷状態である旨の信号を受信すると、受信部１１０からパケットオーダリング用キュー処理部１１１を介して供給されるパケットをスケジューラ１１６に供給する（スキップ処理）。また、パケットスキップ部１１２は、キュー監視部１１３から低負荷状態である旨の信号を受信すると、受信部１１０からパケットオーダリング用キュー処理部１１１を介して供給されるパケットを監視キュー１１４に供給する（スキップ解除処理）。
【００３３】
図６に、キュー監視部１１３とパケットスキップ部１１２の動作状態の遷移図を示す。この動作状態によれば、以下の「状態１」〜「状態３」が繰り返えされる。
【００３４】
［状態１］
パケットスキップ部１１２は、パケット処理部１１５が低負荷状態のとき、すなわち、キュー監視部１１３から高負荷状態を示す信号を受信するまでは、到着したパケットの処理用データを監視キュー１１４に入れる。パケット処理部１１５は、リソースが空くと監視キュー１１４に入っているパケット処理用データを先頭から取り出し、取り出したデータを用いてパケットに処理を施した後、処理用データをスケジューラ１１６に送る。
【００３５】
［状態２］
パケット処理部１１５が高負荷状態になると、リソースがなかなか空かなくなるため、監視キュー１１４からパケットを取り出す頻度が減少する。パケットスキップ部１１２が処理用データを監視キュー１１４に入れる頻度が、パケット処理部１１５が監視キュー１１４から処理用データを取り出す頻度より大きくなると、監視キュー１１４のキュー長が増加する。キュー長が第１の閾値（スキップ処理決定閾値）を越えると、キュー監視部１１３がそれを検知して、パケットスキップ部１１２に対して、パケット処理部１１５が高負荷状態になったことを通知する。パケットスキップ部１１２は、高負荷状態である旨の通知を受信すると、パケット処理用データの送り先を監視キュー１１４からスケジューラ１１６に変更する。この変更後、パケットスキップ部１１２は、到着するパケットの処理用データをスケジューラ１１６に送るが、処理データに対応するパケットのバックプレーン用ヘッダの迂回フラグが「on」になるようにする。
【００３６】
［状態３］
監視キュー１１４にパケットが入らなくなるため、時間の経過とともに、監視キュー１１４のキュー長は減少する。キュー長が第２の閾値（スキップ処理解除閾値）を下回ると、キュー監視部１１３がそれを検知して、パケットスキップ部１１２に対して、パケット処理部１１５が低負荷状態になったことを通知する。パケットスキップ部１１２は、低負荷状態である旨の通知を受信すると、パケット処理用データの送り先をスケジューラ１１６から監視キュー１１４に変更する。この変更後、パケットスキップ部１１２は、到着するパケットの処理用データを監視キュー１１４に送るが、処理データに対応するパケットのバックプレーン用ヘッダの迂回フラグが「off」になるようにする。
【００３７】
パケットオーダリング用キュー処理部１１１は、ネットワーク側にパケットを送出する際に、送信元の転送装置から直接到着したパケットと共有転送装置を迂回して到着したパケットを、本来の正しい順序（ネットワークから送信元の転送装置に到着したパケットの順序）になるように並べる。パケットを並べる作業を行うために、タイマーを用いた時間管理を行うとともにパケットのバックプレーン用ヘッダ内に存在する迂回フラグを使用する。パケットオーダリング用キュー処理部１１１によるパケットの並べ替えにより、送信元の転送装置から直接受信したパケットと共有転送装置を迂回して到達したパケットの間で順序の逆転が起こらないようになっている。
【００３８】
図７に、パケットオーダリング用キュー処理部１１１の動作状態の遷移図を示す。この動作状態によれば、以下の状態１〜４が繰り返えされる。
【００３９】
［状態１］
送信元の転送装置が低負荷状態にあるときは、パケットの共有転送装置への迂回は行われないので、送信先の転送装置は、送信元の転送装置からのみパケットを受信することになる。送信先の転送装置では、パケットオーダリング用キュー処理部１１１は、送信元の転送装置から受信したパケットの処理用データをパケット処理部１１５に向けて送出する。
【００４０】
［状態２］
送信元の転送装置が高負荷状態になると、パケットの共有転送装置への迂回が行われるので、送信先の転送装置は、送信元の転送装置からパケットを受信するとともに、共有転送装置から迂回したパケットを受信することになる。
【００４１】
送信先の転送装置では、パケットオーダリング用キュー処理部１１１は、バックプレーン用パケットヘッダ内の送信元送信先識別子と迂回フラグの「on」の情報とに基づいて、共有転送装置から迂回したパケットを受信したことを検知する。そして、パケットオーダリング用キュー処理部１１１は、送信元の転送装置から直接受信したパケットについては、その処理用データをパケット処理部１１５に向けて送出し、共有転送装置を迂回したパケットについては、その処理用データを自処理部内のキュー（バッファ）に格納する。この処理は、送信先の転送装置から送られてきたパケットが到着するたびにセットされるタイマーが切れるまで行われる。タイマーが切れたときに、パケットオーダリング用キュー処理部１１１は、送信元の転送装置から直接送信される最後のパケットがすでに到着したと判断する。その後、再び、送信元の転送装置から直接送信されるパケットが到着するまで、到着したパケットをすべて共有転送装置から来たパケットと判断する。
【００４２】
［状態３］
送信元の転送装置からのパケットの直接受信が終了すると、送信先の転送装置では、パケットオーダリング用キュー処理部１１１が、内部バッファに格納した処理用データ、および共有転送装置から新たに到着する、迂回したパケットの処理用データをパケットの到着順にパケット処理部１１５に向けて送出する。
【００４３】
［状態４］
送信元の転送装置が低負荷状態に戻ると、送信先の転送装置は、共有転送装置から迂回したパケットを受信することに加えて、送信元の転送装置から直接パケットを受信することになる。
【００４４】
送信先の転送装置では、パケットオーダリング用キュー処理部１１１は、バックプレーン用パケットヘッダ内の送信元送信先識別子と迂回フラグの「off」の情報とに基づいて、送信元の転送装置からパケットを直接受信したことを検知する。そして、パケットオーダリング用キュー処理部１１１は、共有転送装置を迂回したパケットについては、その処理用データをパケット処理部１１５に向けて送出するとともに、送信元の転送装置から直接受信したパケットについては、その処理用データを自処理部内のキュー（バッファ）に格納する。この処理は、共有転送装置から送られて来たパケットが到着するたびにセットされるタイマーが切れるまで行われる。タイマー切れたときに、パケットオーダリング用キュー処理部１１１は、共有転送装置を迂回してきた最後のパケットがすでに到着したと判断する。その後、再び、共有転送装置から直接送信されるパケットが到着するまで、到着したパケットをすべて送信元の転送装置から直接来たパケットと判断する。
【００４５】
次に、共有転送装置２について具体的に説明する。共有転送装置２の主要部は、図３に示した転送装置１の主要部（ネットワーク側インタフェース１００、デバイス間スイッチ１０１、バックプレーン側インタフェース１０２、プロセッサ１０３、および記憶部１０４）と同様な構成となっているが、プロセッサの構成が転送装置１と異なる。
【００４６】
共有転送装置２は、迂回したパケットを処理するための専用装置であってもよいし、通常の転送装置の機能に迂回したパケットを処理する機能を加えた兼用型装置であってもよい。後者の転送兼用型の共有転送装置は、通常の転送装置として動作するとともに、共有転送装置としての役割を果たす。
【００４７】
図８に、兼用型の共有転送装置のプロセッサの構成を示す。図８を参照すると、プロセッサ２０３は、受信部２１０、迂回フラグ判定部２１１、パケット処理部２１２、スケジューラ２１３、および送信部２１４から構成される。図３に示した構成において、このプロセッサ２０３をプロセッサ１０３と置き換えたものが兼用型の共有転送装置となる。受信部２１０、パケット処理部２１２、スケジューラ２１３、および送信部２１４は既存の転送装置のものと同じである。
【００４８】
兼用型の共有転送装置は、共有転送装置として動作する第１の動作モードと、通常の転送装置として動作する第２の動作モードとを有する。第１のモードの場合は、パケットの送信元となる転送装置の情報を用いてパケット処理を行う。一方、第２のモードの場合は、自装置の情報を用いてパケット処理を行う。このように第１のモードと第２のモードとでは、パケット処理に使用する情報が異なるため、迂回フラグが共有転送装置で処理されるデータを明示するために使用される。このため、図８に示す兼用型の共有転送装置では、迂回フラグのon/offと送信元となる転送装置を識別する迂回フラグ判定部２１１が、パケット処理部２１２の入力段に設けられている。
【００４９】
なお、専用の共有転送装置では、兼用型の共有転送装置とは異なり、到着するパケットがすべて送信元の転送装置から到着するパケットであるため、迂回フラグ判定部を必要としない。
【００５０】
以上説明した本実施形態のパケット処理システムによれば、いずれかのパケット転送装置がパケットを処理しきれなくなると、共有転送装置が、パケット転送装置に代わって、その処理しきれなくなったパケットに対するパケット処理を行う。よって、各パケット転送装置は、処理しきれなくなったパケットを保持するために、大容量のバッファを備える必要がないので、その分、パケット転送装置のコストを削減することができる。
【００５１】
また、パケット転送装置によるパケット処理と共有転送装置によるパケット処理とは並列に実行可能であるので、従来のような、パケット転送装置が処理しきれなくなったパケットが処理待ちの状態になる、といった問題は生じない。このようにパケット転送装置が処理しきれなくなったパケットは、処理待ちの状態になることなく、共有転送装置にてパケット処理が実行されるので、従来のものと比較して、ネットワークから到着したパケットをあて先のネットワークへ送信するまでに要する時間を短くすることができる。
【００５２】
（他の実施形態）
上述の実施形態では、図３および図４に示したように、転送装置１のプロセッサ１０３は、パケット処理スキップ機能およびパケットオーダリング用キュー機能を有するが、このプロセッサ１０３に代えて、パケット処理スキップ機能を有する第１のプロセッサと、パケットオーダリング用キュー機能を有する第２のプロセッサとを用いてもよい。ここでは、本発明の他の実施形態であるパケット処理システムとして、そのような機能別のプロセッサを設けた転送装置を有するパケット処理システムを説明する。
【００５３】
本他の実施形態であるパケット処理システムの基本的な構成は、図１に示したシステムと同じであるが、転送装置１の構成が異なる。図９に、本発明の他の実施形態であるパケット処理システムに用いられる転送装置の構成を示す。
【００５４】
図９を参照すると、転送装置は、ネットワーク側インタフェース１００、デバイス間スイッチ１０１、転送先プロセッサ指定機能付きバックプレーン側インタフェース１０２ａ、パケット処理機能付き入力側プロセッサ１０３ａ、およびパケットオーダリング用キュー付き出力側プロセッサ１０３ｂからなる。ネットワーク側インタフェース１００およびデバイス間スイッチ１０１は、図３に示したものと同じである。
【００５５】
この転送装置では、転送装置が共有転送装置の機能を兼ねる場合も考慮し、転送先プロセッサ指定機能付きバックプレーン側インタフェース１０２ａに到着したパケットは、パケット処理スキップ機能付き入力側プロセッサ１０３ａに供給される。具体的には、バックプレーン側インタフェース１０２ａは、パケットが到着すると、到着パケットのヘッダに格納されている送信元送信先識別子と迂回グラフを参照して、到着パケットを処理する必要があるか否かを判断し、処理が必要であると判断した場合は、到着パケットを入力側プロセッサ１０３ａへ送り、処理が必要でないと判断した場合は、到着パケットを出力側プロセッサ１０３ｂへ送る。
【００５６】
図１０に、バックプレーン側インタフェース１０２ａの主要部の構成を示す。図１０に示すように、バックプレーン側インタフェース１０２ａは、プロセッサ向け信号送受信部１０２０、出力プロセッサ指定部１０２１、およびバックプレーン向け信号送受信部１０２２からなる。出力プロセッサ指定部１０２１は、バックプレーン向け信号送受信部１０２２から渡されたパケットのうち、迂回フラグが「ｏｎ」になっているパケットを入力側プロセッサ１０３ａへ送り、迂回フラグが「ｏｆｆ」になっているパケットを出力側プロセッサ１０３ｂへ送る。
【００５７】
入力側プロセッサ１０３ａは、受信したパケットに対して前述の実施形態で説明したパケット処理スキップの処理を実行する。図１１に、入力側プロセッサ１０３ａの主要部の構成を示す。入力側プロセッサ１０３ａは、図４に示したプロセッサの構成において、パケットオーダリング用キュー処理部１１１を取り除いた構成となっている。入力側プロセッサ１０３ａは、パケットオーダリング用キュー処理が行われない以外は、図４に示したプロセッサと同様な処理を行う。
【００５８】
出力側プロセッサ１０３ｂは、受信したパケットに対して前述の実施形態で説明したパケットオーダリング用キュー処理を行う。図１２に、出力側プロセッサ１０３ｂの主要部の構成を示す。出力側プロセッサ１０３ｂは、図４に示したプロセッサの構成において、パケットスキップ部１１２、キュー監視部１１３、および監視キュー１１４を取り除いた構成となっている。出力側プロセッサ１０３ｂは、パケット処理スキップの処理が行われない以外は、図４に示したプロセッサと同様な処理を行う。
【００５９】
上述した各実施形態のパケット処理システムは、本発明の一例であり、その構成および動作は発明の趣旨を逸脱しない範囲で適宜に変更することができる。例えば、図１に示したシステムにおいて、転送装置１に共有転送装置２の機能を加え、共有転送装置２に転送装置１の機能を加えてものよい。この場合は、転送元である転送装置において、パケット処理に対する負荷の状態が低負荷状態から高負荷状態に遷移した場合に、該転送元である転送装置が処理することのできない受信パケットを、該転送元である転送装置に代わって、他の転送装置がパケット処理することになる。このように構成することで、前述したバッファ量の削減、パケット処理時間の短縮、およびパケットロスの発生確率の低減という効果を、転送装置のパケット処理能力を向上させることなく、転送装置の利用率を向上させる形で実現することが可能となる。
【００６０】
また、上記の場合、高負荷状態の転送装置に代わってパケット処理を行う転送装置を予め決めておいてもよい。この場合、高負荷状態の転送装置に代わってパケット処理を行う転送装置として複数の転送装置を設定し、高負荷状態の転送装置が、その設定した複数の転送装置の負荷状態（例えば、監視キューのキュー長）を調べ、負荷状態の最も低い転送装置に、自装置で処理しきれなき受信パケットを送るようにしてもよい。
【００６１】
また、各転送装置間で、互いに、自装置の負荷状態の情報（例えば、監視キューのキュー長）を交換し、高負荷状態となった転送装置が、負荷状態の最も低い転送装置に、自装置で処理しきれなき受信パケットを送るようにしてもよい。
【００６２】
以上説明した本発明のパケット処理システムは、データ通信網を構成するルータなどのネットワーク装置に適用することができる。図１３に、ネットワーク装置の構成を示す。図１３を参照すると、ネットワーク装置は、転送装置３０１ａ、３０１ｂ、共有転送装置３０２ａ、３０２ｂ、スイッチ３０３、およびこれらを収容する筐体３０４からなる。筐体３０４の背面には、バックプレーンインタフェース３００が設けられている。転送装置３０１ａ、３０１ｂ、共有転送装置３０２ａ、３０２ｂ、およびスイッチ３０３は、バックプレーンインタフェース３００に接続される。このネットワーク装置は、前述の各実施形態で説明したような処理を行うことができる。
【００６３】
バックプレーンインタフェースのトポロジは、スター型やメッシュ型などの任意のトポロジが使用可能である。一例として、図１４に、バックプレーンインタフェースのトポロジがメッシュ型のパケット処理システムの構成を示す。このパケット処理システムでは、転送装置１、共有転送装置２がそれぞれ個別に接続されたスイッチ３のそれぞれが、バックプレーンを介して相互に接続されている。なお、バックプレーンインタフェースのトポロジがスター型のパケット処理システムとしては、図１に示したパケット処理システムがある。
【図面の簡単な説明】
【００６４】
【図１】本発明の一実施形態であるパケット処理システムの概略構成を示すブロック図である。
【図２】バックプレーンを流れるパケットに添付されるヘッダの構成を説明するための図である。
【図３】図１に示す転送装置の主要部の構成を示すブロック図である。
【図４】図３に示すプロセッサの概略構成を示すブロック図である。
【図５】図４に示すキュー監視部によるキュー長の監視を説明するための模式図である。
【図６】図４に示すキュー監視部およびパケットスキップ部の動作を説明するための状態遷移図である。
【図７】図４に示すパケットオーダリング用キュー処理部の動作を説明するための状態遷移図である。
【図８】兼用型の共有転送装置のプロセッサの構成を示すブロック図である。
【図９】本発明の他の実施形態であるパケット処理システムに用いられる転送装置の構成を示すブロック図である。
【図１０】図９に示すバックプレーン側インタフェースの主要部の構成を示すブロック図である。
【図１１】図９に示す入力側プロセッサの主要部の構成を示すブロック図である。
【図１２】図９に示す出力側プロセッサの主要部の構成を示すブロック図である。
【図１３】本発明のパケット処理システムを適用するネットワーク装置の構成を説明するための斜視図である。
【図１４】本発明の別の実施形態であるバックプレーンインタフェースのトポロジがメッシュ型のパケット処理システムの構成を示すブロック図である。
【符号の説明】
【００６５】
１  転送装置
２  共有転送装置
３  スイッチ
１００  ネットワーク側インタフェース
１０１  デバイス間スイッチ
１０２  バックプレーン側インタフェース
１０３  プロセッサ
１０４  記憶部
【図１】
0004669442.tif 000002
【図２】
0004669442.tif 000003
【図３】
0004669442.tif 000004
【図４】
0004669442.tif 000005
【図５】
0004669442.tif 000006
【図６】
0004669442.tif 000007
【図７】
0004669442.tif 000008
【図８】
0004669442.tif 000009
【図９】
0004669442.tif 000010
【図１０】
0004669442.tif 000011
【図１１】
0004669442.tif 000012
【図１２】
0004669442.tif 000013
【図１３】
0004669442.tif 000014
【図１４】
0004669442.tif 000015