(57)【要約】【課題】処理遅延バラツキが小さく、処理順序逆転による待ち合わせのための処理性能パフォーマンス低下が生じにくく、受付バッファ量の増大による遅延増大が発生しにくい負荷分散の手法を提供する。【解決手段】複数の処理部を有し、入力パケットデータを処理振り分け部により前記処理部のいずれか一つに振り分けて負荷分散しながら所定のネットワーク処理を行うネットワーク装置であって、前記処理振り分け部は、入力パケットデータの一部のキー情報に基づいて処理種別を取得する手段と、取得した処理種別に対応する固定処理時間を取得する手段と、取得した固定処理時間に基づき、入力パケットデータを前記処理部のそれぞれに振り分けたと仮定した場合の前記処理部の各々の処理時間の分布情報を算出する手段と、処理時間の分布が最も均等になる前記処理部に入力パケットデータを振り分ける手段とを備える。【選択図】図５
2010258660.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理部を有し、入力パケットデータを処理振り分け部により前記処理部のいずれか一つに振り分けて負荷分散しながら所定のネットワーク処理を行うネットワーク装置であって、
前記処理振り分け部は、
入力パケットデータの一部のキー情報に基づいて処理種別を取得する手段と、
取得した処理種別に対応する固定処理時間を取得する手段と、
取得した固定処理時間に基づき、入力パケットデータを前記処理部のそれぞれに振り分けたと仮定した場合の前記処理部の各々の処理時間の分布情報を算出する手段と、
処理時間の分布が最も均等になる前記処理部に入力パケットデータを振り分ける手段と
を備えたことを特徴とするネットワーク装置。
【請求項２】
請求項１に記載のネットワーク装置において、
前記分布情報を算出する手段は、
前記処理部内で直前と同一の処理種別の入力パケットデータを処理する場合は固定処理時間のうちのキャッシュヒット分を処理時間の計算に使用し、
直前と異なる処理種別の入力パケットデータを処理する場合は固定処理時間のうちのキャッシュ未ヒット分を処理時間の計算に使用する
ことを特徴とするネットワーク装置。
【請求項３】
請求項１または２のいずれか一項に記載のネットワーク装置において、
前記分布情報を算出する手段は、
共有リソースへのアクセスが競合する処理につき、アクセスが競合しないよう処理時間の時間帯の補正を行う
ことを特徴とするネットワーク装置。
【請求項４】
請求項１乃至３のいずれか一項に記載のネットワーク装置において、
前記処理部は、実際に処理が完了した入力パケットデータの処理種別毎の固定処理時間を前記処理振り分け部にフィードバックする手段
を備えたことを特徴とするネットワーク装置。
【請求項５】
請求項１乃至４のいずれか一項に記載のネットワーク装置において、
前記処理振り分け部は、入力パケットデータの一部のキー情報に基づいて優先度を識別し、優先クラス毎に前記処理部への入力パケットデータの振り分けを行う
ことを特徴とするネットワーク装置。
【請求項６】
複数の処理部を有し、入力パケットデータを処理振り分け部により前記処理部のいずれか一つに振り分けて負荷分散しながら所定のネットワーク処理を行うネットワーク装置の処理方法であって、
前記処理振り分け部は、
入力パケットデータの一部のキー情報に基づいて処理種別を取得する工程と、
取得した処理種別に対応する固定処理時間を取得する工程と、
取得した固定処理時間に基づき、入力パケットデータを前記処理部のそれぞれに振り分けたと仮定した場合の前記処理部の各々の処理時間の分布情報を算出する工程と、
処理時間の分布が最も均等になる前記処理部に入力パケットデータを振り分ける工程と
を備えたことを特徴とする負荷分散処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信パケットデータのルーティング、フィルタリング、編集・加工等の処理を行うルータやゲートウェイ装置等のネットワーク装置に関する。
【背景技術】
【０００２】
ＩＰ（Internet Protocol）ネットワーク等に用いられるネットワーク装置は、近年の伝送速度の高速化やパケットデータ処理の高度化・複雑化に対応するため、ハードウェアによる処理の高速化および高度化（高レイヤ処理）がトレンドとなっている。すなわち、同一装置内または装置間に複数の処理部を設け、各処理部によりパケットデータ処理を並列処理（負荷分散）することで性能パフォーマンスを高めている。
【０００３】
入力したパケットデータを複数の処理部で並列処理を行うにあたっては、複数の処理部に対して入力したパケットデータの処理振り分けを行う必要があり、ハッシュ方式やラウンドロビン方式による処理振り分けが一般的である。ハッシュ方式とは、入力したパケットデータのヘッダ情報等の一部に対してハッシュ演算を行い、ハッシュ値の法（modulo）をとることで、振り分ける処理部を決定するものである。ラウンドロビン方式とは、複数の処理部に対してパケットデータを順番に振り分けるものである。
【０００４】
しかし、ハッシュ方式やラウンドロビン方式による処理振り分けでは、パケットデータの偏り（ハッシュ結果が分散しない）や処理時間（ＴＡＴ：Turn Around Time）のバラツキにより、処理部の負荷に偏りが生じ、最適に処理リソースを使用することができないという問題がある。
【０００５】
そのため、処理部の受付バッファ（処理キュー）の残量や処理の輻輳情報を取得し、これに基づいて処理振り分けを行うようにした技術が提案されている（例えば、特許文献１、２参照。）。特許文献１は、パケット分配制御部が、パケットプロセッサの負荷レベル（バッファ保持パケット量、処理中断パケット数、パケット処理の種類等）に応じて返送される応答により、負荷の少ないパケットプロセッサを分配先として決定するようにしている。特許文献２は、ネットワーク処理部（分配部相当）が、複数のインタフェース処理部と複数のルート検索部の負荷状況（パケット属性毎にパケットメモリ保存のパケット数）を監視し、負荷判断手段により負荷が最も小さいと判断されたものに分散するようにしている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−２２２３７４号公報
【特許文献２】特開２０００−３６８３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述した処理部の受付バッファの残量や処理の輻輳情報に基づいて処理振り分けを行うようにした従来の技術では、処理中の状態あるいは処理後の結果から処理部の負荷を判定するため、
（１）処理遅延バラツキの増大
（２）処理順序逆転による待ち合わせのための処理性能パフォーマンス低下
（３）受付バッファ量の増大による遅延増大
という問題があった。
【０００８】
以下、これらの問題の発生につき、より詳細に説明する。
【０００９】
図１は従来のネットワーク装置の概略構成を示す図であり、入力パケットデータを処理振り分け部によりｎ個の処理部＃１〜＃ｎに振り分け、それぞれの処理部＃１〜＃ｎから処理後の出力パケットデータを得る。各処理部＃１〜＃ｎは、受付バッファ（処理キュー）とＣＰＵ（Central Processing Unit）コアと情報送信部とを備えている。
【００１０】
受付バッファは、振り分けられたパケットデータを受付順に保持する。ＣＰＵコアは、受付バッファの先頭のパケットデータから順次に処理を行う。なお、ＣＰＵコアは、処理に際してメモリやＩ／Ｏ（Input Output）デバイス等の共有リソースのアクセスを行う。
【００１１】
情報送信部は、受付バッファの残量等に基づく残量・輻輳情報を処理振り分け部に通知する。例えば、受付バッファの蓄積量が第１の所定値よりも多くなった場合には、残量・輻輳情報として、処理振り分けの停止を通知し、受付バッファの蓄積量が第２の所定値よりも少なくなった場合には、処理振り分けの再開を通知する。
【００１２】
図２は図１のネットワーク装置による処理振り分けの例を示す図であり、処理部の数ｎを４としている。
【００１３】
今、処理部＃１には、パケット処理サイクルが「１００」かかるパケットが１個、処理部＃２、＃３、＃４にはパケット処理サイクルが「１０」かかるパケットが２個ずつ、処理待ち状態にあるものとする。この状態の時に、入力パケットがＡ１、Ａ２、Ａ３、Ｂ１、Ｃ１の順で到着したとする。なお、入力パケットＡ１、Ａ２、Ａ３、Ｂ１、Ｃ１のパケット処理サイクルは全て「１０」であるものとする。
【００１４】
ここで、入力パケットＡ１〜Ａ３の３パケットは、ＴＣＰ（Transmission Control Protocol）やＵＤＰ（User Datagram Protocol）のパケットのように複数のＩＰパケットにまたがるものとする。そのため、ＴＣＰやＵＤＰのレイヤでの処理完了は、３つのパケットＡ１〜Ａ３全てが完了することである。
【００１５】
先ず、最初に到着したパケットＡ１は、最もバッファリングされたパケット数が少ない処理部＃１へ振り分けられる。
【００１６】
その次のパケットＡ２は、全ての処理部でのバッファリングされたパケット数が同一のため、任意の処理部、ここでは処理部＃２へ振り分けられる。
【００１７】
他のパケットについても同じ論理にて各処理部へ振り分けられ、均等にパケット数が保たれてスケジューリングされることになる。ただし、パケット数は同一であるが、処理時間の合計は処理部＃１〜＃４において、それぞれ「１２０」「３０」「３０」「３０」と異なるものとなる。
【００１８】
図３は上記の処理振り分け結果に基づく処理実行の例を示す図である。
【００１９】
処理部＃１は、時間「０」から「１００」サイクルかかる処理を行っているため、パケットＡ１の処理は時間「１００」から開始され、時間「１１０」に処理を完了する。
【００２０】
処理部＃２は、時間「２０」からパケットＡ２の処理を開始し、時間「３０」に処理を完了するが、処理逆転によりパケットＡ１の処理が完了していないため、時間「１１０」まで待ち合わせのためストールする。処理部＃３も同様に同時刻までストールする。ＴＣＰパケットのように複数のＩＰパケットから構成されるものを再組み立てして処理するケースでは、異なる処理部に振り分けられた結果、処理逆転が発生し、処理が完了しても待ち合わせのために次のパケットの処理に移行できなくなる。従って、処理部＃２、＃３の時間「３０」から「１１０」までは、後続のパケットを処理できないロス時間となる。このロス時間は、パケット処理性能を下げる要因となり、パケット単位の処理時間に差が大きいほど影響が大きくなる。
【００２１】
次に、パケットＢ１は待ち処理時間の少ない処理部＃４に振り分けられ、パケットＣ１は待ち処理時間の少ない処理部＃１に振り分けられているため、パケットＢ１の処理完了時間が時間「３０」、パケットＣ１の処理完了時間が「１２０」となる。パケットＢ１の処理完了時間とパケットＣ１の処理完了時間には「９０」の差が生まれる。この時間差は処理遅延のゆらぎや増大という問題で表面化する。また、パケット当りの最小処理時間と最大処理時間の差が大きいほど、遅延バラツキが大きくなる。
【００２２】
次に、図４は受付バッファのバッファ量と処理振り分けの送信／停止の関係の例を示す図である。
【００２３】
図４において、各処理部＃１〜＃４は、受付バッファの蓄積量（パケット数）が送信停止閾値Xon（パケット数）を超えた場合に、処理振り分け部に残量・輻輳情報として送信停止を要求するものとする。また、受付バッファの蓄積量が送信再開閾値Xoff（パケット数）を下回った場合に処理振り分け部に送信再開を要求するものとする。また、受付バッファの最大蓄積量をＹ（パケット数）とする。受付バッファから処理振り分け部に残量・輻輳情報が届くまでの経過時間をTAT1とする。残量・輻輳情報が処理振り分け部から各処理部＃１〜＃４へのパケットデータの送信・停止に反映されるまでの経過時間をTAT2とする。この場合、各処理部＃１〜＃４の受付バッファが空にならずオーバフローしないための条件としては、
TAT1＋TAT2  ＜  Xoff  ×  パケット当たりの最小処理時間
TAT1＋TAT2  ＜  （Ｙ−Xon）  ×  パケット当たりの最大処理時間
となる。
【００２４】
従って、TAT1＋TAT2を固定値とし、Xoff、XonをＹにおける所定の比率とした場合、処理部の受付バッファ量Ｙはパケット当りの最小処理時間が短いほど大きくなり、受付バッファに入ってから処理が完了するまでの遅延時間が長くかかる。受付バッファ量を小さくすれば、受付バッファが空になって処理部のアイドル時間により処理性能が低下する可能性がある。
【００２５】
上記の従来の問題点に鑑み、処理遅延バラツキが小さく、処理順序逆転による待ち合わせのための処理性能パフォーマンス低下が生じにくく、受付バッファ量の増大による遅延増大が発生しにくい負荷分散の手法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
このネットワーク装置の一実施態様では、複数の処理部を有し、入力パケットデータを処理振り分け部により前記処理部のいずれか一つに振り分けて負荷分散しながら所定のネットワーク処理を行うネットワーク装置であって、前記処理振り分け部は、入力パケットデータの一部のキー情報に基づいて処理種別を取得する手段と、取得した処理種別に対応する固定処理時間を取得する手段と、取得した固定処理時間に基づき、入力パケットデータを前記処理部のそれぞれに振り分けたと仮定した場合の前記処理部の各々の処理時間の分布情報を算出する手段と、処理時間の分布が最も均等になる前記処理部に入力パケットデータを振り分ける手段とを備える。
【発明の効果】
【００２７】
開示のネットワーク装置にあっては、入力したパケットデータを、処理時間を考慮して予めスケジューリングしてから処理部に振り分けるため、処理遅延バラツキの低減、処理順序逆転による処理性能パフォーマンス低下の防止、受付バッファ量の増大による遅延増大の防止を図ることができる。
【図面の簡単な説明】
【００２８】
【図１】従来のネットワーク装置の概略構成を示す図である。
【図２】処理振り分けの例を示す図である。
【図３】処理振り分け結果に基づく処理実行の例を示す図である。
【図４】受付バッファのバッファ量と処理振り分けの送信／停止の関係の例を示す図である。
【図５】一実施形態にかかるネットワーク装置の構成例を示す図である。
【図６】識別番号取得テーブルのデータ構造例を示す図である。
【図７】処理時間取得テーブルのデータ構造例を示す図である。
【図８】固定処理時間情報の表現形式の例を示す図である。
【図９】処理時間管理部の構成例を示す図である。
【図１０】実行用時間キューの構成例を示す図である。
【図１１】データ書き込み／補正部の処理例を示すフローチャートである。
【図１２】「競合相手の後ろに補正」の処理例を示すフローチャートである。
【図１３】「競合相手を補正」の処理例を示すフローチャートである。
【図１４】処理振り分けの例を示す図である。
【図１５】処理振り分け結果に基づく処理実行の例を示す図である。
【図１６】アクセス経路の例を示す図（その１）である。
【図１７】固定処理時間情報の補正の例を示す図である。
【図１８】アクセス経路の例を示す図（その２）である。
【図１９】アクセス経路の例を示す図（その３）である。
【発明を実施するための形態】
【００２９】
以下、本発明の好適な実施形態につき説明する。
【００３０】
＜構成＞
図５は一実施形態にかかるネットワーク装置の構成例を示す図である。
【００３１】
図５において、ネットワーク装置１は、回線対応部２と処理振り分け部３とデータバッファ４１およびデータディスクリプタ４２と処理部５＃１〜５＃ｎと共有リソース６＃１〜６＃ｍと送信制御部８とを備えている。
【００３２】
回線対応部２は、ＧｂＥ（Gigabit Ethernet(登録商標)）、ＰＯＳ（PPP(Point to Point Protocol) over SONET(Synchronous Optical Network)）等の回線データとのインタフェースを行う部分である。回線対応部２は、回線データに対する物理（ＰＨＹ）レイヤの処理を行う回線終端部２１、２４と、Ｅｔｈｅｒｎｅｔ(登録商標)、ＰＰＰ等のレイヤ２の処理を行うＬ２終端部２２、２３とを備えている。
【００３３】
処理振り分け部３は、回線対応部２から入力したパケットデータを処理部５＃１〜５＃ｎのいずれかに振り分ける部分である。処理振り分け部３は、パケット識別部３１と処理時間管理部３２とスケジューリング判定部３３と実行用時間キュー３４とを備えている。
【００３４】
パケット識別部３１は、入力したパケットデータのパケットヘッダ情報やペイロードの情報の一部から処理種別（パケット処理識別番号）を識別し、その処理種別のパケットデータの処理部５＃１〜５＃ｎでの処理に必要な固定処理時間を取得する部分である。パケット識別部３１は、シーケンス番号付与部３１１と検索部３１２と識別番号取得テーブル３１３と処理時間取得テーブル３１４とを備えている。
【００３５】
シーケンス番号付与部３１１は、入力したパケットデータに対してシーケンス番号を付与する機能を有している。検索部３１２は、パケットデータに含まれるＩＰ種別、ＩＰ−ＤＡ（Destination Address）／ＳＡ（Source Address）等のキー情報を抽出し、識別番号取得テーブル３１３を検索してパケット処理識別番号を取得する機能を有している。また、検索部３１２は、検索して得たパケット処理識別番号に基づき、処理時間取得テーブル３１４を検索して固定処理時間情報を取得する機能を有している。
【００３６】
識別番号取得テーブル３１３は、ＣＡＭ（Content Addressable Memory）等により実装されるものであり、図６に示すように、ＩＰ種別、ＩＰ−ＤＡ／ＳＡ等のキー情報とパケット処理識別番号とが予め対応付けて格納されている。
【００３７】
処理時間取得テーブル３１４は、ＳＲＡＭ（Static Random Access Memory）もしくはＤＲＡＭ（Dynamic Random Access Memory）等により実装されるものであり、図７に示すように、パケット処理識別番号と固定処理時間情報とが対応付けて格納されている。この対応付けは、予めオペレータ等の作業により行なわれる場合と、処理部５＃１〜５＃ｎからのフィードバックにより自動的に行われる場合とがある。
【００３８】
また、固定処理時間情報には、キャッシュヒット固定処理時間とキャッシュ未ヒット固定処理時間とが含まれている。キャッシュヒット固定処理時間とは、各処理部５＃１〜５＃ｎ内で直前と同一の処理種別のパケットデータを処理する場合の固定処理時間である。キャッシュ未ヒット固定処理時間とは、各処理部５＃１〜５＃ｎ内で直前と異なる処理種別のパケットデータを処理する場合の固定処理時間である。図７では、命令実行による処理時間をＣ１、共有リソースアクセスの処理時間をＣ２としており、命令実行による処理時間Ｃ１はキャッシュヒットの場合は短くなる。
【００３９】
図８は固定処理時間情報の表現形式の例を示す図であり、その後の処理を実施しやすくするため、ビット表現により実現したものである。すなわち、命令実行をサイクル数分のビット「１」で表し、共有リソースアクセスをサイクル数分のビット「０」で表している。図示の例では、時間軸上に命令実行が５サイクル、その後に共有リソースアクセスが５サイクル、再度の命令実行が５サイクルからなる処理について、「１１１１１０００００１１１１１」＝「０ｘ７Ｃ１Ｆ」と表現している。なお、図示の例では共有リソースアクセスが１回であるが、複数回の共有リソースアクセスについても同様に表現することができる。また、１アクセス目に共有リソースアクセスが発生することはないため（処理部は命令実行により共有リソースアクセスを行うため）、全ビット長がアクセスサイクル数となる。
【００４０】
なお、図８は２つの実行内容を１ビットで表現した例であるが、複数の実行内容を表現したい場合、例えば異なる種別の共有リソースが複数ある場合などは、多ビットを１アクセスサイクルに対応付けることにより表現することができる。
【００４１】
図５に戻り、処理時間管理部３２は、パケット識別部３１により取得した固定処理時間情報に基づき、パケットデータを処理部５＃１〜５＃ｎのそれぞれに別々に振り分けたと仮定した場合の処理部５＃１〜５＃ｎの各々の処理時間の分布情報（平均偏差合計値）を算出する部分である。なお、処理時間管理部３２は、直前の振り分け情報を実行用時間キュー３４から取得し、最新の状態に更新された状態で分布情報の算出を行う。
【００４２】
処理時間管理部３２は、各処理部５＃１〜５＃ｎに対応する処理部＃１計算用時間キュー３２１＃１〜処理部＃ｎ計算用時間キュー３２１＃ｎを備えている。処理部＃１計算用時間キュー３２１＃１は、パケットデータを処理部５＃１に振り分けたと仮定した場合の各処理部５＃１〜５＃ｎの各々の処理時間の分布情報を算出する。処理部＃ｎ計算用時間キュー３２１＃ｎは、パケットデータを処理部５＃ｎに振り分けたと仮定した場合の各処理部５＃１〜５＃ｎの各々の処理時間の分布情報を算出する。処理時間管理部３２の内部構成の詳細については後述する。
【００４３】
スケジューリング判定部３３は、処理時間管理部３２の算出した分布情報に基づき、処理時間の分布が最も均等な処理部（処理部５＃１〜５＃ｎのいずれか）を決定する部分である。パケットデータの優先度に基づく制御を行う場合、スケジューリング判定部３３は、パケット処理識別番号から優先度を識別し、優先クラス毎に処理部５＃１〜５＃ｎへの入力パケットデータの振り分けを行う。
【００４４】
実行用時間キュー３４は、スケジューリング判定部３３により決定された処理部（処理部５＃１〜５＃ｎのいずれか）に対するスケジューリング済の情報を保持し、各処理部５＃１〜５＃ｎに対して入力パケットデータを振り分ける部分である。また、実行用時間キュー３４は、必要に応じ、共有リソース６＃１〜６＃ｍに対して共有リソース割り当て情報（アクセス許可要求）を与える。
【００４５】
データバッファ４１は、パケット識別部３１の検索部３１２を介して処理対象のパケットデータを保持するとともに、各処理部５＃１〜５＃ｎによる処理済のパケットデータを保持する部分である。
【００４６】
データディスクリプタ４２は、データバッファ４１に保持されたパケットデータのアドレスを示すパケットバッファポインタとシーケンス番号とを対応付けて保持する部分である。
【００４７】
処理部５＃１〜５＃ｎは、処理振り分け部３により振り分けられたパケットデータに対して処理種別に応じた所定の処理を実行する部分である。各処理部５＃１〜５＃ｎは、受付バッファ（処理キュー）５１とパケットデータ領域５２とプログラム／キャッシュ領域５３とＣＰＵコア５４と共有リソースアクセス部５５とＴＡＴ保持／送信部５６とを備えている。ＴＡＴ保持／送信部５６は、固定処理時間情報のフィードバックによる自動的な更新を行わない場合は省略することができる。
【００４８】
受付バッファ５１は、処理振り分け部３により振り分けられたデータパケットのシーケンス番号とパケット処理識別番号を格納する部分である。パケットデータ領域５２は、データバッファ４１からシーケンス番号に基づいて取得したパケットデータおよび処理済のパケットデータを格納する部分である。プログラム／キャッシュ領域５３は、処理のためのプログラムおよび一時的データを格納する部分である。ＣＰＵコア５４は、処理を実行する部分である。共有リソースアクセス部５５は、アクセス経路７を介して共有リソース６＃１〜６＃ｍにアクセスする部分である。ＴＡＴ保持／送信部５６は、受付バッファ５１から処理対象のパケットが取り出されるタイミングとＣＰＵコア５４および共有リソースアクセス部５５の処理状態から、直前の処理の実際の固定処理時間を把握し、処理振り分け部３のパケット識別部３１の処理時間取得テーブル３１４にフィードバックする部分である。
【００４９】
共有リソース６＃１〜６＃ｍは、処理部５＃１〜５＃ｎからアクセスされる、メモリやＩ／Ｏデバイス等である。
【００５０】
送信制御部８は、データバッファ４１から処理済のパケットデータを回線対応部２を介して出力する制御を行う部分である。
【００５１】
次に、図９は処理時間管理部３２の構成例を示す図である。
【００５２】
図９において、処理時間管理部３２の処理部＃１計算用時間キュー３２１＃１〜処理部＃ｎ計算用時間キュー３２１＃ｎは同様の構成であるため、処理部＃１計算用時間キュー３２１＃１について説明する。
【００５３】
処理部＃１計算用時間キュー３２１＃１は、データ書き込み／補正部３２２と平均偏差合計値生成部３２３とデータ出力部３２４と処理部＃１用時間キューＰＱ＃１〜処理部＃ｎ用時間キューＰＱ＃ｎと共有リソース＃１用時間キューＲＱ＃１〜共有リソース＃ｍ用時間キューＲＱ＃ｍとを備えている。
【００５４】
データ書き込み／補正部３２２は、処理部＃１用時間キューＰＱ＃１〜処理部＃ｎ用時間キューＰＱ＃ｎおよび共有リソース＃１用時間キューＲＱ＃１〜共有リソース＃ｍ用時間キューＲＱ＃ｍに対してデータを書き込むとともに、共有リソース＃１用時間キューＲＱ＃１〜共有リソース＃ｍ用時間キューＲＱ＃ｍにおける時間的な競合がなくなるように補正を行う部分である。なお、データ書き込み／補正部３２２は、前回の処理対象となったパケットデータのパケット処理識別番号（前回パケット処理識別番号）を保持している。
【００５５】
平均偏差合計値生成部３２３は、データ書き込み／補正部３２２による補正が完了した後に、処理部＃１用時間キューＰＱ＃１〜処理部＃ｎ用時間キューＰＱ＃ｎのキュー長の平均偏差合計値を計算する部分である。平均偏差合計値の計算は、処理部＃１用時間キューＰＱ＃１〜処理部＃ｎ用時間キューＰＱ＃ｎの時間キュー長の平均値を算出し、各々の時間キュー長と平均値との偏差（絶対値）の合計を計算することで行う。
【００５６】
データ出力部３２４は、平均偏差合計値生成部３２３により計算された平均偏差合計値を後続のスケジューリング判定部３３に出力する部分である。
【００５７】
処理部＃１用時間キューＰＱ＃１〜処理部＃ｎ用時間キューＰＱ＃ｎは、それぞれにポインタテーブルＴ１とデータテーブルＴ２とデータテーブルＴ３とを備えている。ポインタテーブルＴ１は、シーケンス番号SEQ_NO、パケット処理識別番号、補正前次ポインタNext_Pointer1、補正後次ポインタNext_Pointer2の項目を有している。括弧内は、説明の便宜のためにパケットデータを区別するインデックスである。図においては、下から上方向に積み上げていくものとしており、１段目のインデックスは「０」、２段目のインデックスは「１」としている。データテーブルＴ２は、補正前の処理時間が格納され、各処理時間の先頭アドレスを前回のパケットデータに対応する補正前次ポインタNext_Pointer1が指している。データテーブルＴ３は、補正後の処理時間が格納され、各処理時間の先頭アドレスを前回のパケットデータに対応する補正後次ポインタNext_Pointer2が指している。
【００５８】
共有リソース＃１用時間キューＲＱ＃１〜共有リソース＃ｍ用時間キューＲＱ＃ｍは、それぞれにポインタテーブルＴ４とデータテーブルＴ５とデータテーブルＴ６とを備えている。ポインタテーブルＴ４は、シーケンス番号SEQ_NO、処理部番号CNT、補正前先頭ポインタPointer_s_1、補正前末尾ポインタPointer_e_1、補正後先頭ポインタPointer_s_2、補正後末尾ポインタPointer_e_2の項目を有している。処理部番号CNTは、該当する共有リソースにアクセスする処理部５＃１〜５＃ｎを識別する番号である。データテーブルＴ５は、補正前の共有リソースアクセスの処理時間が格納され、各処理時間の先頭アドレスを補正前先頭ポインタPointer_s_1が指し、末尾アドレスを補正前末尾ポインタPointer_e_1が指している。データテーブルＴ６は、補正後の共有リソースアクセスの処理時間が格納され、各処理時間の先頭アドレスを補正後先頭ポインタPointer_s_2が指し、末尾アドレスを補正後末尾ポインタPointer_e_2が指している。
【００５９】
図１０は実行用時間キュー３４の構成例を示す図である。
【００６０】
図１０において、実行用時間キュー３４は、データ書き込み／出力部３４１と処理部＃１用時間キューＰＱＰ＃１〜処理部＃ｎ用時間キューＰＱＰ＃ｎと共有リソース＃１用時間キューＲＱＰ＃１〜共有リソース＃ｍ用時間キューＲＱＰ＃ｍとを備えている。
【００６１】
データ書き込み／出力部３４１は、処理部＃１用時間キューＰＱＰ＃１〜処理部＃ｎ用時間キューＰＱＰ＃ｎおよび共有リソース＃１用時間キューＲＱＰ＃１〜共有リソース＃ｍ用時間キューＲＱＰ＃ｍに対してデータを書き込むとともに、これらの内容を先頭（図の下側）から後続の処理部５＃１〜５＃ｎに出力する部分である。
【００６２】
処理部＃１用時間キューＰＱＰ＃１〜処理部＃ｎ用時間キューＰＱＰ＃ｎは、それぞれにポインタテーブルＴＰ１とデータテーブルＴＰ３とを備えている。ポインタテーブルＴＰ１は、シーケンス番号SEQ_NO、パケット処理識別番号、次ポインタNext_Pointerの項目を有している。データテーブルＴＰ３は、処理時間（処理時間管理部３２による補正後の処理時間）が格納され、各処理時間の先頭アドレスを前回のパケットデータに対応する次ポインタNext_Pointerが指している。
【００６３】
共有リソース＃１用時間キューＲＱＰ＃１〜共有リソース＃ｍ用時間キューＲＱＰ＃ｍは、それぞれにポインタテーブルＴＰ４とデータテーブルＴＰ６とを備えている。ポインタテーブルＴＰ４は、シーケンス番号SEQ_NO、処理部番号CNT、先頭ポインタPointer_s、末尾ポインタPointer_eの項目を有している。データテーブルＴＰ６は、共有リソースアクセスの処理時間（処理時間管理部３２による補正後の処理時間）が格納され、各処理時間の先頭アドレスを先頭ポインタPointer_sが指し、末尾アドレスを末尾ポインタPointer_eが指している。
【００６４】
＜動作＞
先ず、図５に基づいてネットワーク装置１の全体的な動作について説明する。
【００６５】
回線対応部２の回線終端部２１は、入力したＧｂＥ、ＰＯＳ等の回線データに対して物理（ＰＨＹ）レイヤの処理を行い、ビット列をＬ２終端部２２に引き渡す。Ｌ２終端部２２は、Ｅｔｈｅｒｎｅｔ(登録商標)、ＰＰＰ等のレイヤ２の処理を行い、Ｅｔｈｅｒパケット、ＰＰＰパケット等のパケットデータを処理振り分け部３に与える。
【００６６】
処理振り分け部３のパケット識別部３１は、検索部３１２により、パケットデータに含まれるＩＰ種別、ＩＰ−ＤＡ／ＳＡ等のキー情報を抽出し、識別番号取得テーブル３１３を検索してパケット処理識別番号を取得する。また、識別番号取得テーブル３１３から取得したパケット処理識別番号により処理時間取得テーブル３１４を検索し、固定処理時間情報を取得する。また、検索部３１２は、入力したパケットデータ毎にシーケンス番号付与部３１１からシーケンス番号を取得する。
【００６７】
検索部３１２は、入力したパケットデータをデータバッファ４１に格納するとともに、格納したアドレスを示すパケットバッファポインタとシーケンス番号をデータディスクリプタ４２に格納する。また、検索部３１２は、シーケンス番号とパケット処理識別番号と固定処理時間情報を処理時間管理部３２に与える。
【００６８】
処理時間管理部３２は、処理部＃１計算用時間キュー３２１＃１〜処理部＃ｎ計算用時間キュー３２１＃ｎにより、新たなパケットデータを処理部５＃１〜５＃ｎのそれぞれに別々に振り分けたと仮定した場合の各処理部用の時間キューの平均偏差合計値を計算してスケジューリング判定部３３に与える。処理時間管理部３２は、新たなパケットデータをいったん処理部５＃１〜５＃ｎに機械的に仮に振り分けた後、共有リソースの競合がある場合には時間帯の補正を行い、補正後の状態に基づいて時間キューの平均偏差合計値を計算する。処理時間管理部３２における処理の詳細については後述する。
【００６９】
スケジューリング判定部３３は、平均偏差合計値が最も小さい、すなわち、処理時間の分布が最も均等になる処理部を決定し、処理部用の時間キューと共有リソース用の時間キューの更新データを実行用時間キュー３４に与える。これは、処理遅延差を最小化するために各処理部５＃１〜５＃ｎに対して均等に処理するものであるが、処理種別毎に優先順位をつけて処理部５＃１〜５＃ｎを選択することも可能である。この場合、スケジューリング判定部３３は、パケット処理識別番号から優先度を識別し、優先クラス毎に処理部５＃１〜５＃ｎへの入力パケットデータの振り分けを行う。また、リアルタイム性の高いメディアに関して、対応する処理部用時間キュー長を他の処理部用時間キューより短くすることにより、低遅延な優先制御を行うことができる。優先順位が高いものの分布のバラツキの少ないものを選択するか、全体の分布のバラツキが少ないものを選択するかは、装置事情による。
【００７０】
なお、実行用時間キュー３４からは、処理時間管理部３２に対して最新の更新データが与えられ、処理時間管理部３２は次のパケットデータの計算前に、振り分けが完了した最新の状態に更新される。
【００７１】
実行用時間キュー３４は、所定のタイミングで、各処理部用時間キューからシーケンス番号とパケット処理識別番号を処理部５＃１〜５＃ｎに与える。また、実行用時間キュー３４は、所定のタイミングで、各共有リソース用時間キューから、処理部番号と処理時間を含む共有リソース割り当て情報（アクセス許可要求）を共有リソース６＃１〜６＃ｍに与える。なお、共有リソース６＃１〜６＃ｍが共有リソース割り当て情報を必要としない場合は、その付与を省略することができる。
【００７２】
処理部５＃１〜５＃ｎの受付バッファ５１は、受け取ったシーケンス番号とパケット処理識別番号を処理キューに格納するとともに、シーケンス番号に基づいてデータディスクリプタ４２からパケットバッファポインタを取得してパケットデータ領域５２に与える。また、パケットデータ領域５２から、そのパケットバッファポインタに基づいてデータバッファ４１からパケットデータを取得して格納する。
【００７３】
また、ＣＰＵコア５４は、受付バッファ５１の先頭からシーケンス番号とパケット処理識別番号を取得し、パケット処理識別番号に応じた処理をプログラム／キャッシュ領域５３のプログラムに基づいて実行し、処理済のパケットデータをパケットデータ領域５２に格納する。この処理に際して共有リソース６＃１〜６＃ｍにアクセスする必要がある場合は、共有リソースアクセス部５５からアクセス経路７を介して共有リソース６＃１〜６＃ｍにアクセスする。
【００７４】
また、ＴＡＴ保持／送信部５６は、受付バッファ５１から出力されるパケット処理識別番号のタイミングを起点として、次のパケット処理識別番号を受信するまで、サイクル毎に実行内容を各パケット処理識別番号の固定処理時間情報として保持する。すなわち、共有リソースアクセス部５５からＲＥＱ（Request）が発行されていない時間を命令実行サイクル、ＲＥＱ発行後ＡＣＫ（Acknowledge）受信までを共有リソースアクセスサイクルとする。また、ＣＰＵコア５４からキャッシュヒット／キャッシュ未ヒットを認識する。そして、ＴＡＴ保持／送信部５６は、パケット処理識別番号と固定処理時間（キャッシュヒット／キャッシュ未ヒットの別を含む）を処理時間取得テーブル３１４にフィードバックする。処理時間取得テーブル３１４は、フィードバックされた内容に更新を行う。
【００７５】
一方、パケットデータ領域５２は、処理が完了したタイミングで、データバッファ４１に処理済のパケットデータを格納し、データディスクリプタ４２にシーケンス番号とパケットバッファポインタを格納する。
【００７６】
そして、送信制御部８は、処理部５＃１〜５＃ｎの受付バッファ５１から処理が完了したパケットデータのシーケンス番号を取得し、そのシーケンス番号に基づいてデータディスクリプタ４２からパケットバッファポインタを取得する。そして、送信制御部８はそのパケットバッファポインタからのデータ出力をデータバッファ４１に指示し、回線対応部２のＬ２終端部２３および回線終端部２４を介して回線データを出力する。
【００７７】
次に、図９に示した処理時間管理部３２の動作につき、図１１のフローチャートに基づいて説明する。
【００７８】
図１１において、新たなパケットデータを入力して処理を開始すると（ステップＳ１０１）、該当する処理部用時間キューのポインタテーブルＴ１に新SEQ_NO(z)とパケット処理識別番号を追加格納する（ステップＳ１０２）。該当する処理部用時間キューとは、処理部＃１計算用時間キュー３２１＃１であれば処理部＃１用時間キューＰＱ＃１であり、処理部＃ｎ計算用時間キュー３２１＃ｎであれば処理部＃ｎ用時間キューＰＱ＃ｎである。
【００７９】
次いで、該当する共有リソース用時間キューのポインタテーブルＴ４に新SEQ_NO(z)とCNT(z)を追加格納する（ステップＳ１０３）。該当する共有リソース用時間キューとは、パケット処理識別番号で示される処理でアクセスする共有リソースである。パケット処理識別番号とアクセスする共有リソースの対応関係は図示しないテーブル等により管理される。
【００８０】
次いで、前回と今回のパケット処理識別番号が同じであれば、固定処理時間情報のうちキャッシュヒット部分を処理時間（補正前）とし、異なればキャッシュ未ヒット部分を処理時間（補正前）として抽出する（ステップＳ１０４）。
【００８１】
次いで、該当する処理部用時間キューのポインタテーブルＴ１のSEQ_NO(y)のNext_Pointer1(y)より、データテーブル（補正前）Ｔ２上のアドレスを求め、そこに処理時間（補正前）を格納する（ステップＳ１０５）。
【００８２】
次いで、処理時間（補正前）のデータサイズからをNext_Pointer1(z)を算出し、該当する処理部用時間キューのポインタテーブルＴ１に格納する（ステップＳ１０６）。
【００８３】
次いで、処理時間（補正前）の共有リソース処理部分の先頭アドレスPointer_s_1(z)と最終アドレスPointer_e_1(z)の値を算出し、該当する共有リソース用時間キューのポインタテーブルＴ４に格納する（ステップＳ１０７）。
【００８４】
次いで、該当する共有リソース用時間キューのポインタテーブルＴ４のアドレスPointer_s_1(z)は競合なしか否か判断する（ステップＳ１０８）。競合なしか否かの判断は、そのポインタテーブルＴ４の他のPointer_s_1〜Pointer_e_1の範囲内にPointer_s_1(z)が含まれるか否かにより判断する。
【００８５】
Pointer_s_1(z)が競合なしの場合（ステップＳ１０８のＹｅｓ）、該当する共有リソース用時間キューのポインタテーブルＴ４のアドレスPointer_e_1(z)は競合なしか否か判断する（ステップＳ１０９）。
【００８６】
Pointer_e_1(z)が競合なしの場合（ステップＳ１０９のＹｅｓ）、該当する共有リソース用時間キューのポインタテーブルＴ４のアドレスPointer_s_1(z)からPointer_e_1(z)は競合なしか否か判断する（ステップＳ１１０）。
【００８７】
Pointer_s_1(z)からPointer_e_1(z)が競合なしの場合（ステップＳ１１０のＹｅｓ）、補正は不要として、該当する共有リソース用時間キューのポインタテーブルＴ４のPointer_s_2(z)、Pointer_e_2(z)にそれぞれPointer_s_１(z)、Pointer_e_１(z)を格納し、データテーブル（補正後）Ｔ６に処理時間（補正前）の共有リソース処理部分を格納する（ステップＳ１１１）。
【００８８】
次いで、該当する処理部用時間キューのポインタテーブルＴ１のNext_Pointer2(z)にNext_Pointer1(z)を格納し、データテーブル（補正後）Ｔ３に処理時間（補正前）を格納する（ステップＳ１１２）。
【００８９】
次いで、今回のパケット処理識別番号を内部的に保持し（ステップＳ１１３）、処理を終了する（ステップＳ１１６）。
【００９０】
一方、Pointer_s_1(z)が競合する場合（ステップＳ１０８のＮｏ）、「競合相手の後ろに補正」の処理を行い（ステップＳ１１４）、処理を終了する（ステップＳ１１６）。処理の詳細については後述する。
【００９１】
また、Pointer_e_1(z)が競合する場合（ステップＳ１０９のＮｏ）あるいはPointer_s_1(z)からPointer_e_1(z)が競合する場合（ステップＳ１１０のＮｏ）、「競合相手を補正」の処理を行い（ステップＳ１１５）、処理を終了する（ステップＳ１１６）。処理の詳細については後述する。
【００９２】
図１２は「競合相手の後ろに補正」の処理例を示すフローチャートである。
【００９３】
図１２において、先ず、Pointer_s_1(z)と競合するSEQ_NO(a)を算出する（ステップＳ１２１）。
【００９４】
次いで、該当する共有リソース用時間キューのポインタテーブルＴ４のアドレスPointer_e_1(a)+1から[Pointer_e_1(z)-Pointer_s_1(z)]分は競合なしか否か判断する（ステップＳ１２２）。
【００９５】
競合する場合（ステップＳ１２２のＮｏ）、aの次の値をaに代入し（ステップＳ１２３）、競合の判断（ステップＳ１２２）に戻る。
【００９６】
競合なしの場合（ステップＳ１２２のＹｅｓ）、補正値α[Pointer_e_1(a)+1-Pointer_s_1(z)]を算出する（ステップＳ１２４）。
【００９７】
次いで、該当する共有リソース用時間キューのポインタテーブルＴ４のPointer_s_2(z)、Pointer_e_2(z)にそれぞれPointer_s_1(z)+α、Pointer_e_1(z)+αを格納し、データテーブル（補正後）Ｔ６に処理時間（補正前）の共有リソース処理部分を格納する（ステップＳ１２５）。
【００９８】
次いで、該当する処理部用時間キューのポインタテーブルＴ１のNext_Pointer2(z)にNext_Pointer1(z)+αを格納し、データテーブル（補正後）Ｔ３に処理時間（補正前）を格納する（ステップＳ１２６）。
【００９９】
図１３は「競合相手を補正」の処理例を示すフローチャートである。
【０１００】
図１３において、先ず、該当する共有リソース用時間キューのポインタテーブルＴ４のPointer_s_2(z)、Pointer_e_2(z)にPointer_s_１(z)、Pointer_e_１(z)を格納し、データテーブル（補正後）Ｔ６に処理時間（補正前）を格納する（ステップＳ１３１）。
【０１０１】
次いで、該当する処理部用時間キューのポインタテーブルＴ１のNext_Pointer2(z)にNext_Pointer1(z)を格納し、データテーブル（補正後）Ｔ３に処理時間（補正前）を格納する（ステップＳ１３２）。
【０１０２】
次いで、Pointer_e_1(z)もしくはPointer_s_1(z)と競合するSEQ_NO(a)を算出する（ステップＳ１３３）。
【０１０３】
次いで、補正値α[Pointer_e_1(z)+1-Pointer_s_1(a)]を算出する（ステップＳ１３４）。
【０１０４】
次いで、該当する共有リソース用時間キューのポインタテーブルＴ４のａ以降のｉにつきPointer_s_2(i)、Pointer_e_2(i)にそれぞれPointer_s_1(i)+α、Pointer_e_1(i)+αを格納し、データテーブル（補正後）Ｔ６に以前の処理時間（補正後）を格納する（ステップＳ１３５）。
【０１０５】
次いで、該当する処理部用時間キューのポインタテーブルＴ１のｉ以降のｊにつきNext_Pointer2(j)にNext_Pointer1(j)+αを格納し、データテーブル（補正後）Ｔ３に以前の処理時間（補正後）を格納する（ステップＳ１３６）。
【０１０６】
次いで、該当する共有リソース用時間キューのポインタテーブルＴ４のｉ以降のｊにつきPointer_s_2(ｊ)、Pointer_e_2(ｊ)にそれぞれPointer_s_1(j)+α、Pointer_e_1(j)+αを格納し、データテーブル（補正後）Ｔ６に以前の処理時間（補正後）を格納する（ステップＳ１３７）。
【０１０７】
＜具体的動作例＞
図１４は処理振り分けの例を示す図であり、処理部の数ｎを４としている。図２に示した従来の処理振り分けと対比しやすくするため、同じ状況を想定している。
【０１０８】
今、処理部５＃１には、パケット処理サイクルが「１００」かかるパケットデータが１個、処理部５＃２、５＃３、５＃４にはパケット処理サイクルが「１０」かかるパケットデータが２個ずつ、処理待ち状態にあるものとする。処理部５＃１〜５＃４に振り分けられたパケットデータの状態は、処理時間管理部３２において予め行われているスケジューリングにより把握されており、処理部用時間キューがその状態を示している。図１４では、各処理部５＃１〜５＃４の処理待ちのパケットデータに要する処理時間の長さを網掛けのバーで併記している。
【０１０９】
この状態の時に、入力パケットがＡ１、Ａ２、Ａ３、Ｂ１、Ｃ１の順で到着したとする。なお、入力パケットＡ１、Ａ２、Ａ３、Ｂ１、Ｃ１のパケット処理サイクルは全て「１０」であるものとする。
【０１１０】
先ず、入力パケットＡ１については、処理時間が「１０」と認識され、処理部５＃２〜５＃４のいずれに振り分けても分布の均等さは変わらないものと判断し、処理部５＃２に振り分ける。
【０１１１】
後続の入力パケットＡ２、Ａ３、Ｂ１、Ｃ１についても同様に振り分けが行われ、結果として、処理部５＃１には振り分けられず、処理部５＃２には入力パケットＡ１、Ｂ１が、処理部５＃３には入力パケットＡ２、Ｃ１が、処理部５＃４には入力パケットＡ３が振り分けられる。
【０１１２】
図１５は上記の処理振り分け結果に基づく処理実行の例を示す図である。図３に示した従来の処理実行と比べ、「１００」サイクルかかる処理を行っている処理部５＃１には新たなパケットデータが振り分けられないため、連続して到来するパケットデータＡ１、Ａ２、Ａ３、Ｂ１、Ｃ１はほぼ同時期に処理が行われる。そのため、処理遅延バラツキが小さく抑えられるとともに、ＴＣＰパケットのように再組み立てのための待ち合わせが発生しないため、処理性能の低下もきたさない。
【０１１３】
＜共有リソースへのアクセス経路の違いによる変更点等＞
図１６は処理部５＃１〜５＃ｎと共有リソース６＃１〜６＃ｍを接続するアクセス経路７としてシリアルバスもしくはパラレルバスを用いたものである。
【０１１４】
シリアルバスもしくはパラレルバスの場合、バスが共有型になるため、複数の共有リソース６＃１〜６＃ｍが接続される場合においても処理振り分け部３の共有リソース用時間キューは、共有リソース単位ではなく、共有バス単位に具備する必要がある。
【０１１５】
また、シリアルバスとパラレルバスでは、処理部５＃１〜５＃ｎからバスへ信号を送出するまでの時間が異なる。このため、シリアルバスとパラレルバスが混在する構成では、パケット識別部３１からの固定処理時間情報をバス種別により補正する必要がある。パケット識別部３１で設定される固定処理時間情報がパラレルバス基準の場合、処理時間管理部３２の最初の段階においてシリアルバス用の補正を行う。補正値はバスの構造上から決定されるものであるため、固定値である。
【０１１６】
図１７は固定処理時間情報の補正の例を示す図であり、パケット識別部３１からの固定処理時間情報に対し、シリアルバス用に必要なＳ／Ｐ（Serial/Parallel）変換時間を共有リソースアクセスの前後に加えて補正を行っている。
【０１１７】
図１８はアクセス経路７の他の例を示す図であり、処理部５＃１〜５＃ｎと共有リソース６＃１〜６＃ｍを接続するアクセス経路７としてトークンリングバスやＴＤＭ（Time Division Multiplexing）バスを用いたものである。なお、コントローラ７１は、処理振り分け部３からの共有リソース割り当て情報をもとに、タイムスロットの割り当てやトークンの発行を行う。
【０１１８】
トークンリングバスやＴＤＭバスの場合は、各処理部５＃１〜５＃ｎに割り当てられるスロット（周期的）が決まっているため、バスを時分割で共有することになり、１本のトークンリングバスやＴＤＭバスの上に複数の共有リソース６＃１〜６＃ｍが接続されていても、各処理部５＃１〜５＃ｎは同時に別々の共有リソースにアクセスすることができる。このため、処理振り分け部３の共有リソース用時間キューは、共有リソース単位に実装する。
【０１１９】
図１９はアクセス経路７の他の例を示す図であり、処理部５＃１〜５＃ｎと共有リソース６＃１〜６＃ｍを接続するアクセス経路７としてＰ−Ｐ（Point to Point）接続やＳＷ（Switch）接続を用いたものである。アクセス経路７は処理振り分け部３からの共有リソース割り当て情報をもとに、処理部５＃１〜５＃ｎと共有リソース６＃１〜６＃ｍの間の接続経路を確立する。
【０１２０】
Ｐ−Ｐ接続やＳＷ接続の場合は、各処理部５＃１〜５＃ｎは同時に別々の共有リソース６＃１〜６＃ｍにアクセスするため、処理振り分け部３の共有リソース用時間キューは、共有リソース単位に実装する。
【０１２１】
＜総括＞
以上説明したように、本実施形態によれば、従来の方式に比して次のような利点がある。
（１）従来の受付バッファ量を監視する方式の場合、これから処理を振り分けるパケットデータの処理完了時間が予測できないため、その時点で受付バッファに余裕のある処理部に振り分けるしかない。その結果、処理時間が長いパケットデータを振り分けられた処理部は処理完了までに時間を要し、その後に振り分けられたパケットデータの処理完了が遅くなり、遅延バラツキが大きくなる。この点、本実施形態では、入力したパケットデータを、処理時間を考慮してスケジューリングしてから処理部に振り分けるため、遅延パラツキを最小限に抑えた負荷分散を行うことができる。また、遅延バラツキを最小限に抑えることができるため、一つの処理部内で、遅延に厳しいトラフィックとそうでないトラフィックとを混在させて処理することも可能となる。
（２）従来の受付バッファ量を監視する方式の場合、パケットデータ単位に処理開始時間が異なるため、ＴＣＰパケットのように複数のＩＰパケットから構成されるものを処理して再組み立てするケースでは、各処理部での処理順序が守られない。このため、全パケットデータの処理が完了してから再組み立てすることが必要となり、待ち合わせの時間が無駄となる。この点、本実施形態では、事前のスケジューリングにより一連のパケットデータについてほぼ同時期に処理を行うことができるため、待ち合わせ時間がほとんど発生せず、逐次処理が可能となって処理性能が向上する。
（３）従来の受付バッファ量を監視する方式の場合、受付バッファが空となってアイドル時間が発生しないようにするには受付バッファ量を増やすしかなく、その結果、遅延時間が増大してしまう。この点、本実施形態では、事前にスケジューリングすることにより振り分けを行うものであり、受付バッファ量を監視しないため、受付バッファ量による遅延時間の増大という問題は発生しない。
（４）バス接続、リング接続、ＴＤＭ接続、Ｐ−Ｐ接続、スイッチ接続等の種々の経路で接続される共有リソースに対応することができる。
（５）優先度の高いパケットデータを所定の処理部に振り分けることにより、優先度の高い高いリアルタイム性が要求されるトラフィックの透過保証を実現することができる。
【０１２２】
以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。
（付記１）
複数の処理部を有し、入力パケットデータを処理振り分け部により前記処理部のいずれか一つに振り分けて負荷分散しながら所定のネットワーク処理を行うネットワーク装置であって、
前記処理振り分け部は、
入力パケットデータの一部のキー情報に基づいて処理種別を取得する手段と、
取得した処理種別に対応する固定処理時間を取得する手段と、
取得した固定処理時間に基づき、入力パケットデータを前記処理部のそれぞれに振り分けたと仮定した場合の前記処理部の各々の処理時間の分布情報を算出する手段と、
処理時間の分布が最も均等になる前記処理部に入力パケットデータを振り分ける手段と
を備えたことを特徴とするネットワーク装置。
（付記２）
付記１に記載のネットワーク装置において、
前記分布情報を算出する手段は、
前記処理部内で直前と同一の処理種別の入力パケットデータを処理する場合は固定処理時間のうちのキャッシュヒット分を処理時間の計算に使用し、
直前と異なる処理種別の入力パケットデータを処理する場合は固定処理時間のうちのキャッシュ未ヒット分を処理時間の計算に使用する
ことを特徴とするネットワーク装置。
（付記３）
付記１または２のいずれか一項に記載のネットワーク装置において、
前記分布情報を算出する手段は、
共有リソースへのアクセスが競合する処理につき、アクセスが競合しないよう処理時間の時間帯の補正を行う
ことを特徴とするネットワーク装置。
（付記４）
付記３に記載のネットワーク装置において、
前記処理部と前記共有リソースとの接続形態がシリアルバスもしくはパラレルバスの共有バスである場合、前記分布情報を算出する手段は、個々の共有バスについて固定処理時間のうちのリソースアクセス分の処理時間を管理し、当該リソースアクセス分の処理時間の競合を回避する補正を行う
ことを特徴とするネットワーク装置。
（付記５）
付記３に記載のネットワーク装置において、
前記処理部と前記共有リソースとの接続形態がリング接続、ＴＤＭ接続、ポイントツーポイント接続、スイッチ接続のいずれかである場合、前記分布情報を算出する手段は、個々の前記共有リソースについて固定処理時間のうちのリソースアクセス分の処理時間を管理し、当該リソースアクセス分の処理時間の競合を回避する補正を行う
ことを特徴とするネットワーク装置。
（付記６）
付記１乃至５のいずれか一項に記載のネットワーク装置において、
前記処理部は、実際に処理が完了した入力パケットデータの処理種別毎の固定処理時間を前記処理振り分け部にフィードバックする手段
を備えたことを特徴とするネットワーク装置。
（付記７）
付記１乃至６のいずれか一項に記載のネットワーク装置において、
前記処理振り分け部は、入力パケットデータの一部のキー情報に基づいて優先度を識別し、優先クラス毎に前記処理部への入力パケットデータの振り分けを行う
ことを特徴とするネットワーク装置。
（付記８）
複数の処理部を有し、入力パケットデータを処理振り分け部により前記処理部のいずれか一つに振り分けて負荷分散しながら所定のネットワーク処理を行うネットワーク装置の処理方法であって、
前記処理振り分け部は、
入力パケットデータの一部のキー情報に基づいて処理種別を取得する工程と、
取得した処理種別に対応する固定処理時間を取得する工程と、
取得した固定処理時間に基づき、入力パケットデータを前記処理部のそれぞれに振り分けたと仮定した場合の前記処理部の各々の処理時間の分布情報を算出する工程と、
処理時間の分布が最も均等になる前記処理部に入力パケットデータを振り分ける工程と
を備えたことを特徴とする負荷分散処理方法。
【符号の説明】
【０１２３】
１                          ネットワーク装置
２                          回線対応部
２１、２４                  回線終端部
２２、２３                  Ｌ２終端部
３                          処理振り分け部
３１                        パケット識別部
３１１                      シーケンス番号付与部
３１２                      検索部
３１３                      識別番号取得テーブル
３１４                      処理時間取得テーブル
３２                        処理時間管理部
３２１＃１〜３２１＃ｎ      処理部計算用時間キュー
３２２                      データ書き込み／補正部
３２３                      平均偏差合計値生成部
３２４                      データ出力部
ＰＱ＃１〜ＰＱ＃ｎ          処理部用時間キュー
ＲＱ＃１〜ＲＱ＃ｍ          共有リソース用時間キュー
Ｔ１、Ｔ４                  ポインタテーブル
Ｔ２、Ｔ３、Ｔ５、Ｔ６      データテーブル
３３                        スケジューリング判定部
３４                        実行用時間キュー
３４１                      データ書き込み／出力部
ＰＱＰ＃１〜ＰＱＰ＃ｎ      処理部用時間キュー
ＲＱＰ＃１〜ＲＱＰ＃ｍ      共有リソース用時間キュー
ＴＰ１、ＴＰ４              ポインタテーブル
ＴＰ３、ＴＰ６              データテーブル
４１                        データバッファ
４２                        データディスクリプタ
５＃１〜５＃ｎ              処理部
５１                        受付バッファ
５２                        パケットデータ領域
５３                        プログラム／キャッシュ領域
５４                        ＣＰＵコア
５５                        共有リソースアクセス部
５６                        ＴＡＴ保持／送信部
６＃１〜６＃ｍ              共有リソース
７                          アクセス経路
８                          送信制御部
【図１】
2010258660.tif 000003
【図２】
2010258660.tif 000004
【図３】
2010258660.tif 000005
【図４】
2010258660.tif 000006
【図５】
2010258660.tif 000007
【図６】
2010258660.tif 000008
【図７】
2010258660.tif 000009
【図８】
2010258660.tif 000010
【図９】
2010258660.tif 000011
【図１０】
2010258660.tif 000012
【図１１】
2010258660.tif 000013
【図１２】
2010258660.tif 000014
【図１３】
2010258660.tif 000015
【図１４】
2010258660.tif 000016
【図１５】
2010258660.tif 000017
【図１６】
2010258660.tif 000018
【図１７】
2010258660.tif 000019
【図１８】
2010258660.tif 000020
【図１９】
2010258660.tif 000021