(57)【特許請求の範囲】
【請求項１】
物理回線から受信するパケットを複数の物理回線へ振り分けて送信するパケット中継装
置であって、
物理回線からパケットを送受信する送信部と、
物理回線からパケットを受信する受信部と、
複数の物理回線に対応する回線グループを決定する回線グループ決定部と、
パケットのクラスを判定するクラス判定部と、
前記回線グループ内のクラスごとに設定されている帯域制限と、受信パケットのパケット長に基づいて受信パケットの送信時刻を計算する回線グループ制御部とを有する。
【請求項２】
請求項１記載のパケット中継装置であって、
前記回線グループは、リンクアグリゲーションで集約される複数の物理回線又はＭＰＬ
Ｓの保護ＬＳＰを収容する物理回線と該保護ＬＳＰに対応する予備ＬＳＰを収容する物理
回線とに対応する。
【請求項３】
請求項１記載のパケット中継装置であって、
前記受信部で受信したパケットに、前記回線グループ決定部で決定された回線グループ
を付加する回線グループ付加部を有する。
【請求項４】
請求項１記載のパケット中継装置であって、
前記回線グループ決定部で決定されたパケットを回線毎に蓄積する複数のバッファを有
する。
【請求項５】
請求項４記載のパケット中継装置であって、
前記回線毎のバッファは、パケットの通信品質及び種類及び優先順位のいずれかを示す
クラス毎に分かれた複数のクラス別バッファを含む。
【請求項６】
請求項４記載のパケット中継装置であって、
前記回線グループ制御部は、前記バッファ毎に当該バッファから前記送信部へパケット
を送るタイミング又は量を制御する。
【請求項７】
請求項１記載のパケット中継装置であって、
前記回線グループ制御部は、前記回線グループに含まれる複数の物理回線の帯域を監視
してパケットの「遵守」「違反」を判定し、当該判定の結果に基づいて当該パケットの転
送優先度の判定又は廃棄判定を実行する。
【請求項８】
請求項１記載のパケット中継装置であって、
前記回線グループ制御部は、前記物理回線より入力したパケットのヘッダ情報に基づい
てフロー束番号を判定するフロー検出部を備え、当該フロー束番号毎に所定帯域を越えた
か否かを監視する。
【請求項９】
請求項８記載のパケット中継装置であって、
前記フロー検出部は、
送信元アドレスと宛先アドレスとアプリケーション情報とパス情報と物理回線番号との
うち少なくとも一つの情報を備えたフローエントリを格納するフローテーブルと、
前記入力したパケットのヘッダ情報又は当該パケットを入力した物理回線番号と前記フ
ローエントリの情報との一致比較を行い当該パケットの属するフローを判定する制御部と
、
前記制御部で判定したフロー毎にフロー束番号を格納するフロー束テーブルとを備える
。
【請求項１０】
請求項１記載のパケット中継装置であって、
前記回線グループ毎に入力又は出力の入出力制御情報を記憶する入出力制御記憶部を有
し、
前記回線グループ制御部の前記回線グループ毎の制御は、当該回線グループに対応する
前記入出力制御記憶部の入出力制御情報に基づく。
【請求項１１】
請求項１１記載のパケット中継装置であって、
前記入出力制御記憶部は、前記入出力制御情報として回線グループに属するパケットを
受信又は送信する時刻又は間隔又は帯域又はパケット数を示す情報を記憶する。
【請求項１２】
請求項１０記載のパケット中継装置であって、
前記入出力制御記憶部は、最低帯域及び最大帯域のそれぞれに対応する入出力制御情報
を記憶する。
【請求項１３】
請求項１０記載のパケット中継装置であって、
前記入出力制御記憶部は、パケットを送信する送信時刻を前記回線グループに属するパ
ケットのクラス毎に管理するパケット送信管理部と、前記回線グループに属するパケット
のクラス毎の最大帯域及び最低帯域の少なくとも一方を記憶する帯域ポリシー蓄積部とを
含み、
前記回線グループ制御部は、前記帯域ポリシー蓄積部で記憶している最大帯域又は最低
帯域に基づいて前記回線グループに属するパケットのクラス毎の送信時刻を計算して前記
パケット送信管理部に格納し、格納した送信時刻が現在時刻を過ぎているとき、対応する
パケットを前記送信部へ出力するよう制御する。
【請求項１４】
請求項１３記載のパケット中継装置であって、
前記回線グループ制御部は、前記帯域ポリシー蓄積部に記憶された前記回線グループに
属するパケットのクラス毎の最大帯域に基づく送信時刻と、前記回線グループに属するパ
ケットのクラス毎の最低帯域に基づく送信時刻とをそれぞれ計算して前記パケット送信管
理部に格納し、前記回線グループに属するパケットのクラスに対応するパケットについて
現在時刻と比較し、最低帯域に基づく送信時刻を過ぎたパケットを前記送信部へ出力し且
つ最大帯域に基づく送信時刻前のパケットの出力は保留するよう制御する。
【請求項１５】
請求項１０記載のパケット中継装置であって、
前記出力制御記憶部の出力制御情報を設定入力する出力制御設定入力部を有する。
【請求項１６】
請求項１記載のパケット中継装置であって、
前記回線グループ制御部は、前記受信部で受信したパケットに含まれるヘッダ情報に基
づいて当該パケットを送信する送信部又は物理回線を決定する。
【請求項１７】
物理回線から受信するパケットを複数の物理回線へ振り分けて送信するパケット中継装
置であって、
物理回線からパケットを受信する受信部と、
前記受信部で受信したパケットを蓄積する複数のバッファと、
前記受信部で受信したパケットに含まれる情報に基づいて、前記複数のバッファのうち
どのバッファに当該パケットを蓄積するかを決定するバッファ決定部と、
前記複数のバッファのうちグループ化された複数のバッファについて、当該グループに
対応する制御ポリシーに基づきパケットの読み出すバッファ読み出し部と、
前記グループ内のクラスごとに設定されている帯域制限と、受信パケットのパケット長に基づいて受信パケットの送信時刻を計算する制御部と、
前記バッファ読み出し部から読み出されたパケットを物理回線へ送信する送信部とを有
する。
【請求項１８】
請求項１７記載のパケット中継装置であって、
リンクアグリゲーションで集約された複数の物理回線に対応する複数のバッファをグル
ープ化して、当該グループに対する制御ポリシーを記憶するグループ記憶部を有する。
【請求項１９】
請求項１７記載のパケット中継装置であって、
ＭＰＬＳの保護ＬＳＰを収容する物理回線に対応するバッファと該保護ＬＳＰに対応す
る予備ＬＳＰを収容する物理回線に対応するバッファとをグループ化して、当該グループ
に対する制御ポリシーを記憶する記憶部を有する。
【請求項２０】
物理回線から受信するパケットを複数の物理回線へ振り分けて送信するパケット中継装
置が実行するパケット送信方法は以下のステップを含む、
A）パケットを受信し、
B）受信したパケットを送信する、複数の物理回線に対応する回線グループと、パケッ
トのクラスとを判定し、
C）当該判定した回線グループとクラスとに対応するバッファにパケットを蓄積し、
D）回線グループとクラスとに対応する制御情報に基づいて前記バッファからパケット
を読み出し、
E）当該読み出したパケットを送信する。
前記D）ステップは以下を含む、
F）回線グループとクラスとに対応して設定された帯域、受信したパケットのパケット長に基づいて送信時刻を決定し、
G）決定した送信時刻と現在時刻とを比較して現在時刻が送信時刻を過ぎている回線グ
ループとクラスとに対応するパケットを前記バッファから読み出す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、ネットワークを流れるパケットの帯域を制御するシェーピング機能や帯域監視機能を備えるパケット中継装置に関する。
【背景技術】
【０００２】
IPネットワークで用いられるパケット型通信方式では、多数のユーザが同じ回線を共用使用できるため、帯域あたりのコストを低く抑えることができる。このパケット型通信方式の低コスト性のため、従来、専用のネットワークで実現していた各企業の電話網や業務用ネットワークを、IPネットワークで実現する動きがある。このため、専用ネットワークで実現されてきた音声データやミッションクリティカルデータに対する通信品質の確保と高可用性を実現することが、IPネットワークに求められている。
【０００３】
音声データやミッションクリティカルデータの通信品質を確保するためには、IPネットワークを構成するパケット中継装置が、通信品質制御機能を備えることが必要となる。通信品質制御機能としては、例えば、シェーピング機能が知られている。シェーピング機能を実行するシェーピング装置に関しては、特許文献1に記載されている。本文献記載のシェーピング装置は、固定長のパケットであるセルをコネクション（VC（Virtual Connection））毎に蓄積するキューを備え、VC毎に予め設定した帯域で該キューからパケットを送信してVC毎の帯域を確保する。IPネットワークの管理者は、例えば、トラヒックが集中する回線に本技術を適用したシェーピング装置を配置し、音声データやミッションクリティカルデータにVCを割り当てて帯域を確保することで、本データ用の通信品質を確保できる。
【０００４】
他のシェーピング装置としてはWFQ（Weighted Fair Queuing）が知られている。非特許文献1には、SCFQ（Self Clocked Fair Queuing）と呼ばれるアルゴリズムに基づいたWFQのシェーピング装置が記載されている。本文献のシェーピング装置は、複数のセッションk（=1〜N）を管理し、前記セッションk毎に重みWkを備える。パケットp_k_iがシェーピング装置に到着すると、この到着パケットp_k_iをキューに蓄積すると同時に、パケットp_k_i毎の変数F_k_iを下式に基づいて計算する。
F_k_i = L_k_i /Wk ＋ max（F_(k-1)_i, V(ta_k_i)）
ここで、L_k_iはパケットp_k_iのパケット長、ta_k_iはパケットp_k_iの到着時刻、V（t）は時刻ｔにおいてキューから出力されるパケットのF_k_iの値を返す関数である。パケットを出力時には、最小のF_k_iを持つパケットp_k_iを出力することで、各セッションの重みWkに比例したパケット出力を実現する。IPネットワークの管理者は、例えば、音声データやミッションクリティカルデータに一つのセッションkを割り当てて（Wk /Wkの総和）×回線帯域分の帯域を確保することで、本データ用の通信品質を確保できる。
【０００５】
他の通信品質制御機能としては、例えば、非特許文献4記載の帯域監視機能が知られている。本文献のCBR (Constant Bit Rate)サービスでは、ユーザ−ネットワーク間で最大帯域(PCR:Peak Cell Rate)が契約され、帯域監視機能は受信したセルをこの最大帯域で監視し、「違反」と判定したセルを廃棄する。IPネットワークの管理者は、例えば、ネットワークの入口のノードが備えるこの帯域監視機能により、ユーザ毎のデータの帯域を制限して、あるユーザのデータが他ユーザの音声データやミッションクリティカルデータに与える影響を排除することで、特定ユーザの音声データやミッションクリティカルデータの通信品質を確保できる。
【０００６】
一方、非特許文献2において、スイッチにおける高可用性を実現する手段として複数の物理回線（物理リンク）を論理的な一つの集約回線(Link Aggregation Group)として扱い、この集約回線をあたかも一つの物理回線と同様に扱うことを可能とするリンクアグリゲーション技術が記載されている。集約回線の一つの物理回線が故障しても少なくとも一つの物理回線は正常であるため、集約回線で接続されているスイッチ間の通信が途切れることはない。そのため、IPネットワークの管理者は、スイッチ間を接続している単一回線を複数回線で接続してリンクアグリゲーションを適用することで、ネットワークの可用性を向上できる。
【０００７】
また、LSP（Label Switching Path）と呼ばれるパスを設定するMPLS（Multi Protocol Label Switching）ネットワークにおける高可用性を実現する手段として、非特許文献3記載のファストリルート（Fast Reroute）技術がある。本文献には、LSPを流れるトラヒックを保護する方式である１対１バックアップ（one-to-one backup）方式とファシリティバックアップ（facility backup）方式が記載されている。１対１バックアップ方式では、保護されるLSP（保護LSP（protected LSP）と呼ぶ）に対応する一つの予備LSP（backup LSP）が設定され、ファシリティバックアップ方式では、複数の保護LSPに対応する一つの予備LSPが設定されると記載されている。保護LSPに障害が発生した時には、本LSPを流れるトラヒックは予備LSPへと迂回される。IPネットワークの管理者が保護LSPに対する予備LSPを設定して、保護LSPの障害時に前記迂回を実施することで、ネットワークの可用性を向上できる。
【０００８】
【特許文献１】特開平６−３１５０３４号公報
【非特許文献１】S.Golestani, “A Self-Clocked Fair Queuing Scheme for Broadband Applications”, In proc. of INFOCOM’94, pp.636-646,1994.
【非特許文献２】Link Aggregation according to IEEE standard 802.3ad（http://www.itworld.com/Net/1750/NWW001113tech/pfindex.html 参照）
【非特許文献３】“Fast Reroute Extensions to RSVP-TE for LSP Tunnels”IETF RFC 4090
【非特許文献４】The ATM Forum Specification version 4.0  4.5章
【発明の開示】
【発明が解決しようとする課題】
【０００９】
前述した特許文献1、非特許文献1のシェーピング装置は、単一の回線へのパケット出力の制御を前提としており、複数回線へのパケット出力の制御を考慮していない。そのため、特許文献1または非特許文献1を適用したシェーピング装置は、非特許文献2記載の集約回線に出力するパケットの総帯域を制御できない。そのため、リンクアグリゲーション技術を適用したスイッチからなるIPネットワークにおいて、音声データやミッションクリティカルデータに対する通信品質が確保されない課題がある。
【００１０】
また、非特許文献3記載のファストリルート技術を適用したネットワークにおいては、パケット中継装置が、別々の出力回線に設定された保護LSPと予備LSPにパケットを送信することも考えられる。特許文献1または非特許文献1を適用したシェーピング装置は、複数回線へのパケット出力の制御を考慮していないため、保護LSPと対応する予備LSPのパケットの総帯域を制御できない。そのため、ファストリルート技術を適用したスイッチからなるIPネットワークにおいて、音声データやミッションクリティカルデータに対する通信品質が確保されない課題がある。
【００１１】
また、同様に非特許文献4の帯域監視機能は、単一回線からの入力パケットや単一回線への出力パケットの制御を前提としており、複数回線からのパケット入力や複数回線へのパケット出力の制御を考慮していない。そのため、非特許文献4を適用した帯域監視機能は、非特許文献2記載の集約回線から入力するパケットや集約回線へ出力するパケットの総帯域を制御できない。そのため、リンクアグリゲーション技術を適用したスイッチからなるIPネットワークにおいて、音声データやミッションクリティカルデータに対する通信品質が確保されない課題がある。
【００１２】
また、非特許文献3記載のファストリルート技術を適用したネットワークにおいては、パケット中継装置が、別々の入力回線に設定された保護LSPと予備LSPからのパケットを受信したり、別々の出力回線に設定された保護LSPと予備LSPへパケットを送信したりすることも考えられる。非特許文献4を適用した帯域監視機能は、複数回線からのパケット入力や複数回線へのパケット出力を考慮していないため、保護LSPと予備LSPから入力するパケットや保護LSPと予備LSPへ出力するパケットの総帯域を制御できない。そのため、ファストリルート技術を適用したスイッチからなるIPネットワークにおいて、音声データやミッションクリティカルデータに対する通信品質が確保されない課題がある。
【課題を解決するための手段】
【００１３】
そこで、上述した課題を解決するために、例えば、物理回線から受信するパケットを複数の物理回線へ振り分けて送信するパケット中継装置であって、物理回線からパケットを送受信する送信部と、物理回線からパケットを受信する受信部と、複数の物理回線に対応する回線グループを決定する回線グループ決定部と、前記回線グループ決定部で決定された回線グループ毎にパケットの流れを制御する回線グループ制御部とを有するパケット中継装置を提供する。
【００１４】
上記以外の本願が解決しようとする課題、その解決手段は、本願の「発明を実施するための最良の形態」の欄および図面で明らかにされる。
【発明の効果】
【００１５】
例えば上述の手段を採用することで、複数回線から入力するパケットや複数回線へ出力するパケットの総帯域を制御することができる。
【発明を実施するための最良の形態】
【００１６】
以下、図１から３７を用いて本発明に好適な実施例を説明する。ただし、本発明はこの実施例に限定されるものではない。
【実施例１】
【００１７】
シェーピング機能を備えるルータ
（１）ルータの概要動作
まず、本実施例のシェーピング機能を備えるパケット中継装置200の概要動作を説明する。
【００１８】
図１は、本実施例のパケット中継装置200の構成例を示す。パケット中継装置200は、パケットが入力するNの入力回線201-i（i=1-N）とNの出力回線202-i（i=1-N）と、インターフェース部210と、パケットの蓄積とシェーピングを実施する本実施形態特有のシェーピング部100とヘッダ処理部230とプロセッサ240とから構成される。本実施例ではNが4の場合を説明するが、Nは他の値であっても良い。インターフェース部210は、各入力回線201-iに対応するパケットの送受信処理を行うNのパケット送受信回路211-i（i=1-N）より構成される。ヘッダ処理部230は、経路判定部231と、ヘッダ情報等に基づいて該パケットが属する通信品質のクラス（以下、単に「クラス」と呼ぶ）を判定するフロー検出部232から構成される。図１では、ヘッダ処理部230とパケット送受信回路211-1のみが接続されるように記載されているが、ヘッダ処理部230と全てのパケット送受信回路211-iは接続されている。なお、クラスは通信品質そのものを表すものではなく、パケットの種類（例えば音声＝VoIPや映像等）を示すものや、優先順位を示すものであっても良い。
【００１９】
図２は、入力回線201-iより入力するパケットのフォーマットの一例を示す。本フォーマットはヘッダ部310とデータ部320から構成される。ヘッダ部310はデータリンク層の送信元アドレスである送信元MACアドレス316（Source MAC Address：以下「SMAC」という。）、宛先アドレスである宛先MACアドレス317（Destination MAC Address：以下「DMAC」という。）と、ネットワーク層の送信元アドレス（送信端末のアドレス）である送信元IPアドレス311（Source IP Address：以下「SIP」という。）と、宛先アドレス（受信端末のアドレス）である宛先IPアドレス（Destination IP Address：以下「DIP」と呼ぶ。）312と、プロトコル（＝上位アプリケーション）を表す送信元ポート（Source Port：以下「SPORT」と呼ぶ。）313と宛先ポート（Destination Port：以下「DPORT」と呼ぶ。）314とネットワーク内の転送優先度を表すDSCP315から構成される。また、データ部320はユーザデータ321から構成される。
【００２０】
図３は、パケット中継装置200内部のパケットフォーマットの一例を示す。本フォーマットは、図２のフォーマットに内部ヘッダ部330が備わる。この内部ヘッダ部330は入力パケットのバイト長を表すパケット長331と、該パケットが入力した回線の番号である入力回線番号332と、該パケットの出力回線の番号である出力回線番号336と、該パケットの出力回線グループの番号である出力回線グループ333と、該パケットのクラス334と、該パケットの出力ラベルグループ335から構成される。なお、出力回線グループと出力ラベルグループに関しては後述する。なお、出力回線グループと出力ラベルグループとを総称して出力グループと呼ぶこともある。
【００２１】
以下では、パケットが入力回線201より入力し、出力回線202に出力されるまでの流れを説明する。パケットが入力回線201より入力すると図４に詳細を記載したパケット送受信回路211の内部ヘッダ付加回路510は内部ヘッダ部330を付加し、該パケットのバイト長をカウントしてパケット長331に、該パケットが入力した入力回線201の番号を入力回線番号332に書き込んで、該パケットをパケット一時蓄積バッファ520に蓄積する。
【００２２】
さらに、パケットヘッダ送信部550は、パケット一時蓄積バッファ520内のパケットのヘッダ部310と内部ヘッダ部330の情報を、パケットヘッダ情報21としてヘッダ処理部230の経路判定部231とフロー検出部232に送信する。なお、この際、出力回線番号336、出力回線グループ333、クラス334と出力ラベルグループ335の値は意味のない値となっている。
【００２３】
経路判定部231は、受信したパケットヘッダ情報21のDIPまたはDMACの情報から出力回線グループの番号（出力回線グループ番号と呼ぶ）を判定し、パケット出力回線情報22としてパケット送受信回路211に送信する。ここで出力回線グループは、パケットが出力される出力回線の候補の集合である。パケット中継装置200がリンクアグリゲーションを実施している際には、出力回線グループは集約回線に対応し、また、本装置がファストリルートを実施している際には、保護LSPと該LSPの予備LSPを収容する2つの出力回線に対応する。
【００２４】
ヘッダ処理部230のフロー検出部232は、受信したパケットヘッダ情報21から該パケットのクラスを判定し、パケットクラス情報23としてパケット送受信回路211に送信する。
【００２５】
パケット送受信回路211のヘッダ書き込み回路560はパケット出力回線情報22とパケットクラス情報23とを受信すると、パケット一時蓄積バッファ520内のパケットの出力回線グループ333とクラス334の各フィールドに受信した情報を書き込む。さらに、図４のパケット読み出し回路530は、パケットをパケット一時蓄積バッファ520より読み出してパケット送信信号24と共にシェーピング部100へ送信する。
【００２６】
図２と図３ではMPLSではないネットワーク及びパケット中継装置200内におけるパケットのフォーマット例を説明したが、MPLSネットワークにおけるパケット（MPLSパケットと呼ぶ）のフォーマットを図５に、パケット中継装置200内のフォーマットを図６に示す。本フォーマットは、図２および図３のフォーマットと比べてラベル318が追加されている。この際、図２の経路判定部231は、受信したパケットヘッダ情報21の入力回線番号336とラベル318から出力ラベルグループの番号（出力ラベルグループ番号と呼ぶ）を判定する。ここで出力ラベルグループは、保護LSPと該LSPの予備LSP集合である。さらに、これらの情報をパケット出力回線情報22としてパケット送受信回路211に送信する。パケット送受信回路211のヘッダ書き込み回路560は、パケット出力回線情報22内の出力ラベルグループ番号とパケットクラス情報23内のクラスを出力ラベルグループ335とクラス334に書き込む。
【００２７】
シェーピング部100は、各出力回線グループが備えるクラス毎に送信帯域を制御する場合には、出力回線202毎、クラス毎にFIFO: First In First Out（キュー）を備える。シェーピング部100は、パケット送受信回路211からパケットを受信すると、ヘッダ310内の少なくとも一つの情報に基づいて（出力回線グループ333フィールドに設定される）出力回線グループを構成する出力回線の候補の中から一つの最終的な出力回線を判定する。さらに、該出力回線と内部ヘッダ部330のクラス334より決まるFIFOに該パケットを蓄積する。シェーピング部100は、出力回線グループに属するクラス毎に送信するパケットの帯域を制御して、出力回線に対応するパケット送受信回路211にパケットを送信する。
【００２８】
一方、複数の出力回線に跨った保護LSPと予備LSPの送信帯域をまとめて制御する場合のシェーピング部は、出力ラベルグループ毎にFIFOを備える。シェーピング部はパケット送受信回路211からパケットを受信すると、ヘッダ310内の少なくとも一つの情報に基づいて出力ラベルグループに属するLSPと該LSPが設定される出力回線の中から、一つのLSPのラベル（出力ラベルと呼ぶ）と最終的な出力回線を判定する。さらに、判定した出力ラベルをヘッダ部310のラベル318に書き込み、該出力回線と出力ラベルグループ335より決まるFIFOに該パケットを蓄積する。シェーピング部100は、出力ラベルグループ毎に送信するパケットの帯域を制御して、出力回線に対応するパケット送受信回路211にパケットを送信する。
【００２９】
パケット送受信回路211は、受信したパケットを一旦、パケット一時蓄積バッファ570に蓄積し、内部ヘッダ削除回路580が内部ヘッダ部330を削除し、出力回線202に送信する。
【００３０】
（２）出力回線グループが備えるクラス毎に送信帯域を制御する場合の詳細動作
以下では、本実施形態固有のシェーピング部100が、出力回線グループが備えるクラス毎に送信帯域を制御する際の詳細動作を説明する。以下の実施例ではクラスの数が2の場合に限って説明するが、それ以外の値であっても良い。
【００３１】
図７は、シェーピング部の第１の構成例を示すブロック図である。シェーピング部100は、パケットを蓄積するFIFOを出力回線毎およびクラス毎に複数備えるパケットバッファ110と、パケットを一時的に蓄積するパケット一時蓄積バッファ120と、パケットを蓄積するFIFOを判定する蓄積FIFO判定部140と、パケットライト部130と、パケットリード部150と、出力回線番号テーブル600と、出力回線毎の多重回路1〜4より構成される。出力回線数が4で、クラスの数が2の場合のパケットバッファ110は、各出力回線212-i対応のFIFO i1およびFIFO i2を4出力回線分（即ち、計8 FIFO）備えている。
【００３２】
シェーピング部100がパケット送受信回路211よりパケットを受信すると、パケット一時蓄積バッファ120は該パケットを蓄積する。次に、パケットライト部130は、パケット一時蓄積バッファ120に蓄積されたパケットのヘッダ部310と内部ヘッダ部330の情報を読み出して、蓄積FIFO判定部140に送信する。蓄積FIFO判定部140は、内部ヘッダ部330内の出力回線グループ333（図３及び図６参照）に対応した一つ乃至は複数の出力回線番号の候補を判定し、これらの候補の中から一つの出力回線番号を選択してパケットライト部130に送信する。
【００３３】
出力回線番号の候補の判定は、例えば、蓄積FIFO判定部140が図８記載の出力回線番号テーブル600を参照することで実現される。出力回線番号テーブル600は、4つの出力回線番号を記載するエントリ610-i （i =1〜4）を出力回線グループ毎に備える。エントリ610-i が4つ未満の出力回線番号を格納する際には、有効な出力回線番号をエントリ610-iの左側から格納する。ここでは、出力回線グループ1が出力回線1、出力回線グループ2が出力回線2、出力回線グループ3が出力回線3と4から構成される例を説明する。図中の”＊”は有効な値が設定されていないことを表す。蓄積FIFO判定部140は、出力回線グループ333をアドレスとして出力回線番号テーブル600を読み出し、読み出した情報を出力回線番号の候補と判定すれば良い。
【００３４】
出力回線番号の候補の中から、一つの出力回線番号を判定する方法としては、例えば、4つのハッシュ関数H4(x)、H3(x)、H2(x)、H1(x)を用いた方式が考えられる。H4(x) は引数xに対してハッシュ値として1〜4の中から一つの整数を、H3(x)は1〜3中から一つの整数を、H2(x) は1、2の中から一つの整数を、H1(x)は1を出力する。エントリ610の最も左側の出力回線番号から順にハッシュ値1、2、3および4に対応している。
【００３５】
蓄積FIFO判定部140は、出力回線番号テーブル600の参照により得られた有効な出力回線番号の数である’h’と対応したハッシュ関数Hh(x)を選択する。例えば、出力回線グループ1、または2の場合にはハッシュ関数H1(x)を、出力回線グループ3の場合にはハッシュ関数H2(x)を選択する。さらに、パケットライト部130より受信したヘッダ部310の情報のうち、少なくともひとつの情報から構成される値を引数xとして、Hh(x)の値を計算する。例えば、引数xの値としては、SIP311、DIP312、SPORT313、DPORT314を連結した情報などが考えられるが、それ以外の情報であっても良い。最後に、蓄積FIFO判定部140はハッシュ値に対応した出力回線番号の候補を最終的な出力回線番号と判定すれば良い。
【００３６】
パケットライト部130は最終的な出力回線番号を受信すると、パケット一時蓄積バッファ120に対し、蓄積しているパケットをパケットバッファ110に送信するように通知し、前記最終的な出力回線番号と内部ヘッダ330内のクラス334をパケットバッファ部110に、前記最終的な出力回線番号と内部ヘッダ330内のクラス334と出力回線グループ333をパケットリード部150に送信する。最終的な出力回線番号と内部ヘッダ330内のクラスに対応するFIFOij（iは最終的な出力回線番号、jはクラス334に対応）は、パケット一時蓄積バッファ120より受信したパケットを蓄積する。
【００３７】
パケットリード部150は、出力回線グループ333のクラス毎にパケットバッファ110からのパケット読み出しを管理/制御して、パケットを送信する出力回線番号とクラスを判定し、これらの情報をパケットバッファ110に送信する。本実施例では、クラス数が2であるが、1クラスまたは3クラス以上であっても良い。クラス数が1の場合には、出力回線グループ毎に出力パケットが制御される。
【００３８】
パケットリード部150の一実現例を図１３に示す。パケットリード部150は制御部710と、出力回線グループのクラス毎にパケット送信用の管理情報を格納するパケット送信管理テーブル720と、出力回線のクラス毎のFIFOijに蓄積されているパケットの数を格納するFIFO管理テーブル730と、各クラスの制限帯域や帯域の割り当て等のポリシーを格納する帯域ポリシー蓄積部740と、出力回線グループテーブル750と、タイマー760より構成される。
【００３９】
図９および図１０にパケット送信管理テーブル720およびFIFO管理テーブル730の一実現例を示す。図９のパケット送信管理テーブル720には、出力回線グループ番号毎、クラス毎に次パケットの送信時刻（次パケット送信時刻）が格納されている。図１０のFIFO管理テーブル730は、出力回線番号毎、クラス毎にFIFOijの蓄積パケット数を格納するのエントリ731を備える。例えば、エントリ731-3は、出力回線2のクラス1のFIFO21が6パケットを蓄積していることを表す。
【００４０】
出力回線グループの各クラスの最大帯域を制限する場合の帯域ポリシー蓄積部740の一例を図１１に示す。帯域ポリシー蓄積部740は出力回線グループのクラス毎の最大帯域を設定するエントリ741から構成される。図１１の帯域ポリシー蓄積部740には、出力回線グループ1のクラス1、クラス2にはそれぞれ20Mbps、80Mbpsが、出力回線グループ2のクラス1、クラス2にはそれぞれ50Mbps、100Mbpsが、出力回線グループ3のクラス1、クラス2にはそれぞれ40Mbps、120Mbpsが最大帯域として設定されている。
【００４１】
出力回線グループテーブル750の一例を図１２に示す。出力回線グループテーブル750は、各出力回線が属する出力回線グループの番号を記載したエントリ751を格納する。設定値は、図８の出力回線番号テーブル600の設定値と矛盾無く設定される。
パケットリード部150の処理はパケットライト時処理と、本処理とは非同期に実行されるパケットリード時処理から構成される。以下では、それぞれの詳細について説明する。
【００４２】
＜パケットライト時処理＞
図１３の制御部710が、出力回線番号と内部ヘッダ330内のクラス334と出力回線グループ333を受信すると、FIFO管理テーブル730より受信した出力回線番号とクラスに対応するエントリ731を読み出し、読み出した情報に1を加えて同一エントリ731に書き戻す。
【００４３】
＜パケットリード時処理＞
以下では、パケットリード時処理の詳細を、出力回線k（出力回線番号が’k’の出力回線）用のフローチャート（図１４）を用いて説明する。
パケットリード部150の制御部710がパケット送受信回路211よりパケット送信要求信号25-k （k=1〜4）を受信すると、本処理を開始する（ステップ1200）。まず、制御部710は出力回線グループテーブル750の出力回線番号’k’に対応するエントリ751-k （k=1〜4）を読み出し、出力回線番号’k’が属する出力回線グループを判定する（ステップ1201）。
【００４４】
次に、制御部710はFIFO管理テーブル730の出力回線番号’k’に対応するエントリ731を2エントリ読み出し （ステップ1202）、正の整数を格納するエントリ731の存在有無をチェックして、パケットが蓄積されているクラスを判定する（ステップ1203）。チェック結果が「有り」の場合、パケットが蓄積されている出力回線kのクラスに対応するパケット送信管理テーブル720のエントリ721を全て読み出し、次パケット送信時刻が最も早い（次パケット送信時刻が最も小さい）クラスを「送信クラス」と判定する（ステップ1204）。例えば、出力回線1の場合、図１０によるとクラス1のパケットしか蓄積されていないため、出力回線1のクラス1を「送信クラス」と判定する。また、出力回線2の場合、クラス1、2のパケットが蓄積されているため、次パケット送信時刻が小さな出力回線2のクラス1を「送信クラス」と判定する。チェック結果が「無し」の場合には、パケットリード時処理とは非同期に実施される前述のパケットライト時処理により、出力回線番号’k’に対応するエントリ731の値が’0’から正の整数に変化するまで待機する（ステップ1214）。正の整数に変化すると再度ステップ1202、1203を行う。なお、ステップ1214実行後のステップ1203において、制御部710は「有り」と判定するため常にステップ1204に進む。
【００４５】
次にタイマー760の示す現時刻と送信クラスの次パケット送信時刻を比較し（ステップ1205）、次パケット送信時刻 ≧ 現時刻（即ち、次パケット送信時刻が現時刻または過去の時刻）である場合には、出力回線番号’k’と送信クラスをパケット送信回線/クラス情報としてパケットバッファ110に通知する（ステップ1206）。パケット送信回線/クラス情報に対応するFIFOijは、先頭のパケット（即ち、蓄積パケットのうち、最も過去に到着したパケット）を読み出して多重回路に送信し、多重回路は同一の出力回線202行きのパケットを時間多重してパケット送受信回路211に送信すると同時に、内部ヘッダ部330のパケット長331を送信パケット長情報12としてパケットリード部150に送信する（ステップ1207）。
【００４６】
一方、次パケット送信時刻 ＜ 現時刻（即ち、次パケット送信時刻が未来の時刻）の場合、該次パケット送信時刻となるまで待機する。この待ち時間の間にパケットライト時処理により、出力回線番号’ｋ’に対応するFIFOにパケットが蓄積されエントリ731が0から正の整数に変化する場合がある。この際、次パケット送信時刻が最も早い「送信クラス」が変化する可能性がある。例えば、FIFO管理テーブル730、パケット送信管理テーブル720の格納値がそれぞれ図１０、図９に記載された値であって、出力回線1のクラス1のパケット出力を待機している場合を考える。この際、出力回線１のクラス2のパケットが入力されると、次パケット送信時刻がより早いクラス2が送信クラスとなる。そのため、制御部710は再度エントリ121を読み出し（ステップ1202）、値が正の整数であるのエントリ731の有無をチェックし（ステップ1203）、再度、送信クラスの判定を行う（ステップ1204）。
【００４７】
次パケット送信時刻を経過しステップ1206が終了すると、制御部710は出力回線グループ、送信クラスに対応するエントリ741を帯域ポリシー蓄積部740より読み出し（ステップ1208）、読み出した最大帯域と多重回路より受信したパケット長（byte）から決まる次パケット送信時刻を計算する（ステップ1209）。次パケット送信時刻の計算は以下の式に基づいて行われる。
次パケット送信時刻 ＝ 現時刻 ＋ パケット長(byte)×8／最大帯域(bit/秒)…式1
計算後、帯域ポリシー蓄積部740に新たな次パケット送信時刻を書き戻す（ステップ1210）。最後に、出力回線kの送信クラス対応するFIFO管理テーブル730のエントリ731を読み出し（ステップ1211）、’1’減算して（ステップ1212）、FIFO管理テーブル730に書き戻し（ステップ1213）、ステップ1200に戻る。
【００４８】
また、ステップ1205の待機中には、各クラスの次パケット送信時刻が、同一出力回線グループに属する他の出力回線m（m≠k）のステップ1210処理により、変化する場合がある。例えば、FIFO管理テーブル730、パケット送信管理テーブル720の格納値がそれぞれ図１０、図９に記載された値であって、出力回線3のクラス2のパケット出力を待機している場合を考える。この際、同一出力回線グループ3の出力回線4クラス2のパケットが出力されると、出力回線グループ3の次パケット送信時刻が更新される。そのため、制御部710は再度エントリ721を読み出し（ステップ1202）、値が正であるのエントリ731の有無をチェックし（ステップ1203）、再度、送信クラスの判定を行う（ステップ1204）。
【００４９】
以上に説明した様に本実施形態のシェーピング部100のパケットリード部150は、次パケット送信時刻を出力回線グループのクラス毎に計算する。該次パケット送信時刻が現在あるいは過去となった場合にのみ各クラスのパケットを送信するため、シェーピング部100は出力回線グループのクラスに設定される最大帯域を遵守したパケット送信を実現できる。例えば、出力回線グループ3のクラス1、2のパケットは、それぞれ40Mbps、120Mbps以下の帯域で出力回線202-3および4に出力される。
【００５０】
以上の実施例では、各クラスの最大帯域を制限する場合を記載したが、本実施形態のシェーピング部100は他のポリシーに基づいて帯域を制御することも可能である。例えば、各クラスの最低帯域を確保してパケットを送信しつつ、各出力回線グループの総帯域に余剰が存在する場合には、最低帯域を超えて送信することも可能である。ここで総帯域とは、出力回線グループを構成する出力回線の物理帯域の総和である。例えば、出力回線202がファーストイーサネットであり物理帯域が100Mbpsの場合、出力回線グループ3が出力回線3と4から構成される本実施例においては、出力回線グループ3の総帯域は200Mbps（＝100Mbps×2回線）となる。総帯域の余剰が発生するのは、各クラスの最低帯域の総和が総帯域よりも小さい場合や、各クラスの最低帯域の総和が総帯域より大きい場合でも特定クラスのパケットが入力されず、最低帯域分のパケット出力が無い場合である。
【００５１】
最低帯域を確保するシェーピング部100の帯域ポリシー蓄積部740は、最大帯域の代わりに最低帯域をエントリ741に格納することとなる。図１１の設定値の場合、出力回線グループ3のクラス1とクラス2の最低帯域はそれぞれ40Mbps、120Mbpsである。シェーピング部100はステップ1208における次パケット送信時刻を、式1と同様の下記の式2に基づいて計算する。
次パケット送信時刻 ＝ 現時刻 ＋ パケット長(byte)×8／最低帯域(bit/秒)…式2
さらに、各クラスに余剰帯域を割り当てるため、ステップ1205では次パケット送信時刻の値に関係なくステップ1206に進む。本ステップ1205の変更により余剰の帯域が各クラスの最低帯域の比率に基づき分配される。例えば、最低帯域が図１１の値であり、出力回線グループ3のクラス1、2のそれぞれ150Mbpsパケットが本実施形態のパケット中継装置200に入力する場合を考える。出力回線3と4がファーストイーサネットである場合には、出力回線グループ3の余剰帯域である40Mbps（= 200Mbps−(40Mbps＋120Mbps)）が、各クラスにそれぞれの最低帯域の比率で分配され、各クラスの送信帯域は50Mbpsと150 Mbpsとなる。
【００５２】
また、別の例として、各クラスの最大帯域を制限しつつ最低帯域を確保することも可能である。その際の帯域ポリシー蓄積部2440と、パケット送信管理テーブル2520をそれぞれ図１５と図１６に示す。帯域ポリシー蓄積部2440は、最低帯域と最大帯域を格納するクラス毎のエントリ2441から構成され、テーブル2520は最低帯域用の次パケット送信時刻と最大帯域用の次パケット送信時刻を格納するクラス毎のエントリ2521から構成される。
【００５３】
図１４のステップ1208、1209においては、制御部710は帯域ポリシー蓄積部2440のエントリ2441を読み出し、最低帯域用の次パケット送信時刻と最大帯域用の次パケット送信時刻を、それぞれ式１および式2に基づいて計算する。また、ステップ1204において、制御部710はパケットが蓄積されている出力回線kのクラスに対応するパケット送信管理テーブル2520のエントリ2521を全て読み出す。次に、最低帯域用の次パケット送信時刻が最も早いクラスと最大帯域用の次パケット送信時刻が最も早いクラスを、それぞれ「最低帯域用の送信クラス」と「最大帯域用の送信クラス」と判定する。ステップ1205では、最低帯域用の送信クラスと最大帯域用の送信クラスの次パケット送信時刻を現時刻と比較する。ステップ1206では、最低帯域用の送信クラスの次パケット送信時刻 ≧ 現時刻である場合には、出力回線番号’k’と最低帯域用の送信クラスをパケット送信回線/クラス情報としてパケットバッファ110に通知する。一方、最低帯域用の送信クラスの次パケット送信時刻 ＜ 現時刻の場合、最大帯域用の送信クラスの次パケット送信時刻 ≧ 現時刻である場合には、出力回線番号’k’と最大帯域用の送信クラスをパケット送信回線/クラス情報としてパケットバッファ110に通知する。また、最大帯域用の送信クラスの次パケット送信時刻 ＜ 現時刻の場合には、最大帯域用の次パケット送信時刻となるまで待機する。
【００５４】
また、別の例として各出力回線グループの出力回線201の総帯域を重みWに基づいて分配するWFQ（Weighted Fair Queuing）を適用しても良い。帯域ポリシー蓄積部740に設定される最低帯域の値として、各クラスのWに比例した任意の帯域を設定すれば良い。なお、同一出力回線グループの最低帯域の総和は総帯域よりも小さい必要がある。前述したように、最低帯域の比率で出力回線グループの総帯域が割り当てられるため、実装/動作は最低帯域を確保するシェーピング部の実装/動作と同一である。
【００５５】
以上に説明した様に、本実施形態のシェーピング部100のパケットリード部150は、出力回線グループ毎、クラス毎に出力するパケットの帯域を管理することにより、複数の出力回線へ出力するパケットの総帯域を制御できる。
【００５６】
また、別の例として各クラスに優先度を付与し、優先度が高いクラスのパケットが存在する場合に該クラスのパケットを送信し、該クラスのパケットが存在しない場合に優先度が低いクラスのパケットを送信することも可能である。例えば、クラス１とクラス2が存在する本実施例において、高優先のクラスをクラス１と低優先のクラスをクラス2とした場合、クラス１のパケットが存在する際には、クラス1のパケットが、クラス1のパケットが存在しない時だけクラス2のパケットが送信される。
この際、帯域ポリシー設定部740とパケット送信管理テーブル720は不要となる。また、ステップ1204において、制御部710はステップ1203のチェック結果が「有り」と判定したクラスの中で一番優先度の高いクラスを送信クラスと判定し、ステップ1205では、現時刻に関係なくステップ1206に進むようにすれば良い。
【００５７】
（３）出力ラベルグループ毎に送信帯域を制御する場合の詳細動作
次に、（２）のようにクラス毎ではなく、出力ラベルグループ毎に送信帯域を制御するシェーピング部の詳細動作を説明する。なお、説明を簡単にするため出力ラベルグループ数が3の場合に限って説明するが、それ以外の値であっても良い。
【００５８】
図１７は、シェーピング部の第２の構成例を示す。シェーピング部1500は、パケットを蓄積するFIFO（キュー）を出力回線毎および出力ラベルグループ毎に備える。それ以外の構成は図７のシェーピング部100と同一であり、各部の番号のみが異なっている。
【００５９】
シェーピング部1500がパケット送受信回路211よりパケットを受信すると、パケット一時蓄積バッファ120は該パケットを蓄積する。パケットライト部1530は、パケット一時蓄積バッファ120に蓄積されたパケットのヘッダ部310と内部ヘッダ部330の情報を読み出して、蓄積FIFO判定部1540に送信する。蓄積FIFO判定部1540は、内部ヘッダ部330内の出力ラベルグループ335（図３及び６参照）に対応した1つ乃至は2つの出力回線番号と出力ラベルの候補を判定し、これらの候補の中から一つの出力回線番号と出力ラベルを選択してパケットライト部1530に送信する。
【００６０】
出力回線番号と出力ラベルの候補の判定は、出力回線番号テーブル600の代わりに出力ラベルグループ毎に、2つの出力回線番号と出力ラベルを記載するエントリ1610-i （i=1〜4）を備える図１８記載の出力回線番号テーブル1600を用いる。図１８のテーブル1600には、出力ラベルグループ1に対応する出力回線番号は1、2、対応するラベルが5、6であり、出力ラベルグループ2に対応する出力回線番号は2、3、対応するラベルが7、8であり、出力ラベルグループ3に対応する出力回線番号は3、4、対応するラベルが9、10である場合が記載されている。
【００６１】
蓄積FIFO判定部1540は、出力ラベルグループ333をアドレスとして出力回線番号テーブル1600を読み出し、読み出した情報を出力回線番号と出力ラベルの候補と判定すれば良い。出力回線番号と出力ラベルの候補の中から、一つの出力回線番号を判定する方法としては、例えば、前述のハッシュ関数H2(x)、H1(x)のみを用いた方式等を用いれば良い。
【００６２】
パケットライト部1530は選択した出力回線番号と出力ラベルを受信すると、パケット一時蓄積バッファ120に対し、該出力ラベルのラベル318への書き込みと、蓄積パケットのパケットバッファ1510への送信を通知する。さらに、前記最終的な出力回線番号と出力ラベルグループ335をパケットバッファ部110とパケットリード部150に送信する。本通知を受けたパケット一時蓄積バッファ120は、該出力ラベルをラベル318に書き込み、パケットをパケットバッファ1510へ送信する。出力回線番号と出力ラベルグループ335に対応するFIFOij（iは最終的な出力回線番号、jは出力ラベルグループに対応）は、受信したパケットを蓄積する。
【００６３】
パケットリード部1550は、出力ラベルグループ毎にFIFOijからのパケット読み出しを管理し、パケットを送信する出力回線と出力ラベルグループを判定し、本情報をパケットバッファ1510に送信する。本情報を受信したパケットバッファ1510は対応するFIFOijよりパケットを送信することとなる。本実施形態のパケットリード部1550が、出力ラベルグループ335毎にパケットの読み出しを制御することにより、出力ラベルグループを構成する複数のLSPに属するパケットの出力を制御することができる。
【００６４】
パケットリード部1550の一実現例を図１９に示す。図２０および図２１にパケット送信管理テーブル1620およびFIFO管理テーブル1630の一実現例を示す。図２０のパケット送信管理テーブル1620には、出力ラベルグループ毎に次パケット送信時刻が格納され、図２１のFIFO管理テーブル1630には、出力回線番号毎、出力ラベルグループ毎にFIFOijの蓄積パケット数が格納される。
【００６５】
出力ラベルグループの最大帯域を制限する場合の帯域ポリシー蓄積部1640の一例を図２２に示す。帯域ポリシー蓄積部1640は出力ラベルグループの最大帯域を設定するエントリ1641から構成される。
【００６６】
出力ラベルグループテーブル1650の一例を図２３に示す。出力ラベルグループテーブル1650は、各出力回線に設定されるLSPが属する出力ラベルグループの番号を3つ記載するエントリ1651を格納する。本エントリ1651により各出力回線に設定される出力ラベルグループ数が3の場合まで対応可能であるが、4以上に対応するために本エントリ1651が4つ以上の出力ラベルグループ数を備えるようにしても良い。
【００６７】
本テーブルの設定値は、図１８の出力回線番号テーブル1600の設定値と矛盾無く設定される。
【００６８】
以下では、パケットリード部1550の処理であるパケットライト時処理と、パケットリード時処理の詳細について説明する。
【００６９】
＜パケットライト時処理＞
図１９の制御部1610が、出力回線番号と内部ヘッダ330内の出力回線グループ333を受信すると、FIFO管理テーブル1630より受信した出力回線番号と出力ラベルグループに対応するエントリ1631を読み出し、読み出した情報に1を加えて同一エントリ1631に書き戻す。
【００７０】
＜パケットリード時処理＞
以下では、パケットリード時処理の詳細を、出力回線k用のフローチャート（図２４）を用いて説明する。
【００７１】
パケットリード部1650の制御部1610がパケット送受信回路211よりパケット送信要求信号25-k （k=1〜4）を受信すると、本処理を開始する（ステップ2100）。まず、制御部1610は出力回線グループテーブル1650の出力回線番号’k’に対応するエントリ1651-k （k=1〜4）を読み出し、出力回線kに設定される出力ラベルグループを判定する（ステップ2101）。例えば、kが’2’である場合には、出力ラベルグループ1と2が、出力回線2に設定される出力ラベルグループと判定する。
【００７２】
次に、制御部1610はFIFO管理テーブル1630の出力回線番号’k’とステップ2101で判定した出力ラベルグループに対応する全てのエントリ1631を読み出し （ステップ2102）、正の整数を格納するエントリ1631の存在有無をチェックする（ステップ2103）。チェック結果が「有り」の場合、正の整数を格納するエントリ1631に対応する出力ラベルグループに対応する全てのエントリ1621を読み出し、次パケット送信時刻が最も早い出力ラベルグループを「送信ラベルグループ」と判定する（ステップ2104）。チェック結果が「無し」の場合には、パケットリード時処理とは非同期に実施される前述のパケットライト時処理により、出力回線番号’k’に対応するエントリ1631の値が’0’から正の整数に変化するまで待機する（ステップ2114）。正の整数に変化すると再度ステップ2102、2103を行う。
【００７３】
次にタイマー1660の示す現時刻と送信クラスの次パケット送信時刻を比較し（ステップ2105）、次パケット送信時刻 ≧ 現時刻である場合には、出力回線番号’k’と出力ラベルグループをパケット送信回線/出力グループ情報151としてパケットバッファ1510に通知する（ステップ2106）。パケット送信回線/出力グループ情報151に対応するパケットバッファ1510のFIFOijは、先頭のパケットを読み出して多重回路に送信し、多重回路は同一の出力回線202行きのパケットを時間多重してパケット送受信回路211に送信すると同時に、内部ヘッダ部330のパケット長331を送信パケット長情報12としてパケットリード部1550に送信する（ステップ2107）。
一方、次パケット送信時刻 ＜ 現時刻の場合、該次パケット送信時刻となるまで待機する（ステップ2105）。この待ち時間の間に出力回線番号’ｋ’に対応するFIFOにパケットが蓄積してエントリ1631が0から正の整数に変化した場合、制御部1610は再度エントリ121を読み出し（ステップ2102）、正の整数を格納するエントリ1631の有無をチェックし（ステップ2103）、「送信ラベルグループ」の判定を行う（ステップ2104）。
【００７４】
次パケット送信時刻を経過しステップ2106が終了すると、制御部1610は出力ラベルグループ335に対応するエントリ1641を帯域ポリシー蓄積部1640より読み出す（ステップ2108）。さらに、読み出した最大帯域と多重回路より受信したパケット長（byte）から決まる次パケット送信時刻を、前述の式1に基づいて計算し（ステップ2109）、パケット送信管理テーブル1620に新たな次パケット送信時刻を書き戻す（ステップ2110）。最後に、出力回線kの送信クラス対応するFIFO管理テーブル1630のエントリ1631を読み出し（ステップ2111）、’1’減算して（ステップ2112）、FIFO管理テーブル1630に書き戻し（ステップ2113）、ステップ2100に戻る。
【００７５】
また、ステップ2105の待機中には、各出力ラベルグループの次パケット送信時刻が、同一出力ラベルグループに属するLSPが設定される他の出力回線のステップ2110処理により、変化する場合がある。この際、制御部1610は再度エントリ1631を読み出し（ステップ2102）、正の整数が格納されるエントリ1631の有無をチェックし（ステップ2103）、「送信ラベルグループ」の判定を行う（ステップ2104）。
【００７６】
以上に説明した様に本実施形態のシェーピング部1500のパケットリード部1550は、次パケット送信時刻を出力ラベルグループ毎に計算する。各出力ラベルグループのパケットを該次パケット送信時刻が現在あるいは過去となった場合にのみ送信するため、シェーピング部1500は出力ラベルグループに設定される最大帯域を遵守したパケット送信を実現できる。
【００７７】
なお（２）と（３）では、最大又は最低帯域に基づく送信時刻を計算して用いる例を説明したが、これに代えて例えば送信間隔やパケット数を帯域ポリシー蓄積部に蓄積し、シェーピング部が該情報に用いて出力パケットを制御しても良い。
【００７８】
（４）帯域ポリシーの設定
最後に、パケットリード部の帯域ポリシー蓄積部740、1640、2440の設定について説明する。パケット中継装置200の管理者は、外部の制御端末10から帯域ポリシー蓄積部の設定を行う。帯域ポリシー蓄積部740、1640設定時に制御端末10に入力されるコマンドの一例を図２５に示す。これらのコマンド：shaperは、2201記載の集約回線の2202記載のクラスに、2203記載の最大帯域の値を設定するコマンドである。制御端末10はこれらのコマンドが入力されると、全ての情報をプロセッサ240に送信する。
【００７９】
コマンドを受けたプロセッサ240は、パケットリード部150（または1550）の制御部710（または1610）に2201、2202、2203の情報と、本情報の書き込み指示を送信する。制御部710（または1610）は本情報を受信すると、2201、2202に対応するエントリ741（または1641）に2203の値を書き込む。また、最低帯域の値を設定する際には、コマンド中の”peak_rate”を”minimum_rate”とすれば良い。さらに、帯域ポリシー蓄積部2440の最大帯域と最低帯域を設定する際には、”peak_rate X Mbps”を、” peak_rate X Mbps, minimum_rate Y Mbps”とすれば良い。ここでXとYはそれぞれ最大帯域、最低帯域として設定される帯域である。
【実施例２】
【００８０】
帯域監視機能を備えるルータ
（１）ルータの概要動作
まず、本実施例の帯域監視機能を備えるパケット中継装置2600の概要動作を説明する。
本実施例の帯域監視機能は、入力回線グループを構成する入力回線より入力したパケットの帯域を制御したり、出力回線グループを構成する出力回線へ出力するパケットの帯域を制御したりする。ここで、入力回線グループとは、リンクアグリゲーションを構成する複数の入力回線、又はMPLSの保護LSPと予備LSPが設定される複数の入力回線のことを、また、出力回線グループとは、リンクアグリゲーションを構成する複数の出力回線、又はMPLSの保護LSPと予備LSPが設定される複数の出力回線の集合ことをいう。
【００８１】
さらに、本実施例の帯域監視機能は、入力ラベルグループに属するパケットの帯域を制御したり、出力ラベルグループに属するパケットの帯域を制御したりする。ここで、入力ラベルグループとは、入力回線グループを構成する複数の入力回線に設定された保護LSPと予備LSPの集合のことを、出力ラベルグループとは、出力回線グループを構成する複数の出力回線に設定された保護LSPと予備LSPの集合のことをいう。
【００８２】
図26は、本実施例のパケット中継装置2600の構成例を示す。図１の中継装置200と同一の構成要素に関しては、同一の数値が付されている。パケット中継装置2600は、パケットが入力するNの入力回線201-i（i=1-N）とNの出力回線202-i（i=1-N）と、インターフェース部2610と、シェーピング部100と本実施形態固有のヘッダ処理部2630とプロセッサ240とから構成される。インターフェース部2610は、各入力回線201-iに対応するパケットの送受信処理を行うNのパケット送受信回路2611-i（i=1-N）より構成される。ヘッダ処理部2630は、経路判定部231と、ヘッダ情報等に基づいて該パケットが属するフローを判定し、該フローが属する複数フローの集合であるフロー束の番号(フロー束番号と呼ぶ)を判定するフロー検出部2632と、フロー束毎の帯域を計測し、この帯域と予めフロー束に割り当てられた帯域に応じ、パケットの通過/廃棄やパケットの転送優先度であるDSCP値を判定する帯域監視部2633から構成される。図26では、実施例1と同様にヘッダ処理部2630とパケット送受信回路2611-1のみが接続されるように記載されているが、ヘッダ処理部2630と全てのパケット送受信回路2611-iは接続されている。
【００８３】
また、入力回線201-iより入力するパケットのフォーマット、該パケットのパケット中継装置2600内部のパケットフォーマット、MPLSパケットのフォーマット、該パケットのパケット中継装置2600内のフォーマットは、実施例1と同一である。
【００８４】
以下では、パケットが入力回線201より入力し、出力回線202に出力されるまでの流れを説明する。パケットが入力回線201より入力すると、図27記載のパケット送受信回路2611の内部ヘッダ付加回路510は内部ヘッダ部330を付加する。さらに、該パケットのバイト長をカウントしてパケット長331に、該パケットが入力した入力回線201の番号を入力回線番号332に書き込んで、該パケットをパケット一時蓄積バッファ520に蓄積する。さらに、内部ヘッダ付加回路510は入力回線201に対応する入力回線グループの番号である入力回線グループ番号を判定してパケット一時蓄積バッファ520に送信し、該バッファ520は本情報をパケット共に蓄積する。この判定は図12記載の出力回線グループテーブル750と同フォーマットの入力回線グループテーブルを参照することで実現される。入力回線グループテーブルは、各入力回線が属する入力回線グループ番号を記載したエントリを格納する。内部ヘッダ付加回路510はパケットの入力回線201に対応するエントリを参照して入力回線グループ番号を判定することとなる。
【００８５】
次に、パケットヘッダ送信部550は、パケット一時蓄積バッファ520内のパケットのヘッダ部310と内部ヘッダ部330と入力回線グループ番号を、パケットヘッダ情報21としてヘッダ処理部2630の経路判定部231とフロー検出部2632と帯域監視部2633に送信する。なお、この際、出力回線番号336、出力回線グループ333、クラス334と出力ラベルグループ335の値は意味のない値となっている。
【００８６】
パケットヘッダ情報21を受信した経路判定部231は、実施例1と同様に情報21内のDIPまたはDMACの情報から出力回線グループ番号を判定し、パケット出力回線情報22としてパケット送受信回路2611に送信する。
【００８７】
ヘッダ処理部2630のフロー検出部2632は、受信したパケットヘッダ情報21から受信したパケットが属するフローの判定と、該フローの複数の集合であるフロー束の番号(フロー束番号と呼ぶ)を判定して、該フロー束番号を帯域監視部2633に通知する。帯域監視部2633はこのフロー束に属するパケットの帯域を計測し、予め設定された帯域に対して超過したか否かを判定する。さらに、この判定結果に基づきネットワーク内の優先度であるDSCPを判定し、パケット送受信回路2611にDSCP情報26として送信する。なお、実施例１のフロー検出部232では、シェーピング部100にて使用するクラスの判定を行うが、本実施例2では、シェーピング部100にてクラスに相当する情報が必要ないため、フロー検出部2632はクラスの判定を行わないこととする。
【００８８】
この際に、フロー検出部2632が入力回線グループを構成する複数の入力回線からのパケットに同一のフロー束番号を割り当てることで、複数の入力回線グループを構成する入力回線からのパケットの帯域を纏めて計測し、帯域を制御することができる。また、フロー検出部2632が、ある入力回線Aから入力しヘッダ情報や入力回線番号が特定の条件Aを満たすパケットと、入力回線Aと同一の入力回線グループを構成する他の入力回線Bから入力し、ヘッダ情報や入力回線番号が特定の条件Bを満たすパケットに対して、同一のフロー束番号を割り当てることで、入力回線Aかつ条件Aを満たすパケットと入力回線Bかつ条件Bを満たすパケットの帯域をまとめて制御することができる。例えば、前記条件Aとして、入力回線Aに設定される保護LSPのラベルの値が、条件Bとして、入力回線Bに設定される予備LSPのラベル値が使用されれば、入力ラベルグループ(ここでは、保護LSPと予備LSPの集合)に属するパケットの帯域を制御できる。
【００８９】
パケット送受信回路2611のヘッダ書き込み回路560はパケット出力回線情報22とDSCP情報26を受信すると、パケット一時蓄積バッファ520内のパケットの出力回線グループ333とDSCP315の各フィールドに受信した情報を書き込む。さらに、図27のパケット読み出し回路530は、パケットをパケット一時蓄積バッファ520より読み出してパケット送信信号24と共にシェーピング部100へ送信する。なお、この際、該パケットのクラス334と出力回線番号336は無意味な情報のままとなっている。
【００９０】
一方、MPLSネットワークのパケット中継装置200内における経路判定部231は、実施例１の場合と同様に受信したパケットヘッダ情報21の入力回線番号336とラベル318から出力ラベルグループ番号を判定する。さらに、これらの情報をパケット出力回線情報22としてパケット送受信回路2611に送信することとなる。パケット送受信回路2611のヘッダ書き込み回路560は、パケット出力回線情報22内の出力ラベルグループ番号とDSCP情報26内のDSCPをそれぞれ出力ラベルグループ335とDSCP315に書き込む。
【００９１】
次に実施例１に対するシェーピング部100動作の変更点を説明する。本実施例2では、シェーピング部100は帯域の制御を行わないため、パケットを出力回線毎に備えた複数FIFOのうち一つのFIFOに蓄積し、対応する出力回線202の物理帯域で該FIFOからパケット送受信回路2611に送信する。そのため、実施例１とは異なり、パケットライト部130は、全パケットを蓄積FIFO判定部140が判定した出力回線のクラス１のFIFOに蓄積する。さらに、パケットリード部150の該FIFOに対応する帯域ポリシー蓄積部740のエントリ741には、該出力回線の物理帯域よりも大きな値が記載され、パケットリード部150はパケット送受信回路2611よりパケット送信要求信号25を受信すると、該FIFOからパケットを直ぐに読み出してパケット送受信回路2611に送信することとなる。また、本実施例では、シェーピング部100が送信したパケットに対して、出力回線番号に基づいて再度帯域監視を実行することとなる。このため、パケットライト部130はパケット一時蓄積バッファ120内のパケットの出力回線番号336を蓄積FIFO判定部140が判定した出力回線番号で上書きする。これら以外のシェーピング部100の動作は実施例１と同一である。
【００９２】
シェーピング部100が送信したパケットをパケット送受信回路2611が受信すると、該パケットをパケット一時蓄積バッファ570に蓄積する。パケットヘッダ送信部550は、該パケットのヘッダ部310と内部ヘッダ部330の情報を、パケットヘッダ情報21としてヘッダ処理部2630のフロー検出部2632と帯域監視部2633に送信する。ヘッダ処理部2630のフロー検出部2632は、再度、パケットヘッダ情報21からフロー束番号を判定して帯域監視部2633に通知することとなる。
【００９３】
帯域監視部2633は、前述した動作と同様に、フロー束に属するパケットの帯域を計測し、予め設定された帯域に対して超過したか否かを判定する。さらに、判定結果に基づきネットワーク内の優先度であるDSCPを判定し、パケット送受信回路2611にDSCP情報26として送信する。この際、フロー検出部2632が出力回線グループを構成する複数の出力回線からのパケットに同一のフロー束番号を割り当てることで、出力回線グループを構成する複数の出力回線へのパケットの帯域を纏めて計測し、帯域を制御することができる。
また、フロー検出部2632がある出力回線Cへ出力し、ヘッダ情報や出力回線番号が特定の条件Cを満たすパケットと、出力回線Cと同一の出力回線グループを構成する他の出力回線Dへ出力し、ヘッダ情報や出力回線番号が特定の条件Dを満たすパケットに対して同一のフロー束番号を割り当てることで、出力回線Cかつ条件Cを満たすパケットと出力回線Dかつ条件Dを満たすパケットの帯域を制御することができる。例えば、前記条件Cとして、出力回線Cに設定される保護LSPのラベルの値が、条件Dとして、入力回線Dに設定される予備LSPのラベル値が使用されれば、出力ラベルグループ(ここでは、保護LSPと予備LSPの集合)に属するパケットの帯域をまとめて制御できる。なお、出力ラベルグループを構成するLSP数が3以上となっても同様である。
【００９４】
最後にパケット送受信回路2611は、受信したパケットの内部ヘッダ部330を削除し、出力回線202に送信する。
【００９５】
（２）フロー検出部の詳細動作
次に図28乃至33を用いて本実施形態のフロー検出部2632の詳細動作について説明する。まず、入力回線201よりパケット送受信回路2611がパケットを受信し、該パケットに対応するパケットヘッダ情報21を受信した際（パケット受信時と呼ぶ）の動作について説明する。シェーピング部100よりパケット送受信回路2611がパケットを受信し、該パケットに対応するパケットヘッダ情報21を受信した際（パケット送信時と呼ぶ）の動作については後述する。
【００９６】
図28にフロー検出部2632のブロック図を、図29にフロー検出部2632が備えるフローテーブル3002のフォーマットを示す。フローテーブル3002が複数備えるフローエントリ3110-i(i=1〜N)はフローを識別するための条件としてSIP3101-iとDIP3102-iとSPORT3103-iとDPORT3104-iと入力回線番号3105-iと出力回線番号3106-iと入力ラベル3108-i、出力ラベル3109-i、入力回線グループ3111-i、出力回線グループ3112-iおよびパケット受信または送信時のいずれに有効なフローエントリ3110であるかを記載するIn/Out3107が設定される。ここで、In/Out3107は’1’がパケット受信時に有効でパケット送信時に無効なエントリ3110であることを、’0’がパケット送信時に有効でパケット受信時に無効なエントリ3110であることを表す。  なお、本パケット中継装置2600の管理者は制御端末10によりフローエントリ3110-iを設定する。制御端末10がパケット中継装置2600にフローテーブル3002への書き込み命令と、フローテーブル3002のアドレスと、フローテーブル3002に書き込む書き込み情報(SIP3101、DIP3102、SPORT3103、DPORT3104、入力回線番号3105、出力回線番号3106、 入力ラベル3108、出力ラベル3109、入力回線グループ3111、出力回線グループ3112、
In/Out3107に対応する情報)を送信すると、制御部3001がフローテーブル3002の前記アドレスに書き込み情報を書き込む。なお、パケット受信時においては、パケットヘッダ情報21内に出力回線番号、出力ラベルおよび出力回線グループに対応する情報は含まれていない。そのため、エントリ3110の出力回線番号3106、出力ラベル3109と出力回線グループ3112には、フローエントリ識別条件として使用しないことを示すマスク値(“*”と記載する)が設定されることとなる。
【００９７】
フロー検出部2632の制御部3001は、パケットヘッダ情報21を受信すると、テーブルアドレスが’1’のフローエントリ3110-1を読み出し、In/Out3107内の情報が’1’である場合には、SIP3101、DIP3102、SPORT3103、DPORT3104、入力回線番号3105、入力ラベル3108、入力回線グループ3111とパケットヘッダ情報21内のSIP311、DIP312、SPORT313、DPORT314、入力回線番号332、ラベル318、入力回線グループと比較する(マスク値”*”が設定されている出力回線番号3106、出力ラベル3109と出力回線グループ3112とは比較しない)。一致した場合、テーブルアドレスである’1’ を一致アドレス情報13としてフロー束判定部3003へ送信する。一致しない場合、前記テーブルアドレスに1を加算して前述のエントリ3110の読み出しと比較動作を繰り返し、最初に一致したフローエントリ3110のアドレスを一致アドレス情報13としてフロー束判定部3003へ送信する。この一つの一致アドレス情報13が一つのフローに対応することとなる。
フロー束判定部3003はこの一致アドレス情報13毎に（即ちフロー毎に）、フロー束の識別子であるフロー束番号を割り当てて、フロー束番号14として帯域監視部2633へ送信する。フロー束判定部3003が同一の入力回線グループの入力回線から入力するパケットのフロー束番号を同一の値とする事により、複数の入力回線から入力したパケットを一つのフロー束として扱うことが可能となる。  フロー束判定部3003の一例を図30に示す。制御部3201が一致アドレス情報13を受信すると、この値をそのままフロー束テーブル3202の読み出しアドレスとして送信する。図31にフロー束テーブル3202のフォーマットを示す。フロー束テーブル3202は前記読み出しアドレスに対応するフロー束番号3310-j(j=1〜N)をフロー束番号14として出力する。
【００９８】
同一の入力回線グループから入力するパケットを一つのフロー束として扱う場合を考えてみる。この際、フローテーブル3002のフローエントリ3110-iの入力回線番号3105に入力回線グループを構成する入力回線の番号を、それ以外の条件には何れの値も指定しないマスク”*”を設定し、それぞれのエントリ3110に対応するフロー束番号3310を同一の値とすれば良い。
入力回線グループがnの入力回線から構成される場合、nのフローエントリ3110とnのフロー束番号3310の設定が必要となる。設定されるフローエントリ3110とフロー束番号3310を削減するため、エントリ3110の入力回線グループ3111に検出するグループの番号を、それ以外の条件にはマスク”*”を設定しても良い。この際、１つのフローエントリ3110とフロー束番号3310のみが設定されることとなる。
【００９９】
ある入力回線Aから入力し、ヘッダ情報や入力回線番号が特定の条件Aを満たすパケットと、入力回線Aと同一の入力回線グループを構成する他の入力回線Bから入力し、ヘッダ情報や入力回線番号が特定の条件Bを満たすパケットを一つのフロー束で扱うことも可能である。例えば、前記条件Aとして、入力回線Aに設定される保護LSPのラベルの値が、条件Bとして、入力回線Bに設定される予備LSPのラベル値が使用されれば、入力ラベルグループ(ここでは、保護LSPと予備LSPの集合)に属するパケットの帯域がまとめて制御される。この際、フローテーブル3002のフローエントリ3110の入力回線番号3105と入力ラベル3108にそれぞれ入力回線Aと保護LSPのラベルが、他のフローエントリ3110の入力回線番号3105と入力ラベル3108にそれぞれ入力回線Bと予備LSPのラベルが設定される。なお、これらのフローエントリ3110のその他のフィールドはマスク”*”となる。さらに、それぞれのエントリ3110に対応するフロー束番号3310は同一の値に設定されることとなる。
この際、2つのフローエントリ3110とフロー束番号3310の設定が必要となるが、所望の条件A、Bを満たすパケットが入力回線AあるいはBの何れより入力するか不明であったり、どちらの入力回線からも入力したりする場合にはさらに多くの設定が必要となる。例えば、保護ラベルと予備ラベルを備えるパケットが、入力回線AとBの両入力回線より入力する場合を考える。この際、フローを検出する条件として入力回線Aかつ保護LSPのラベル値、入力回線Aかつ予備LSPのラベル値、入力回線Bかつ保護LSPのラベル値、入力回線Bかつ予備LSPのラベル値をそれぞれ記載した4つのフローエントリ3110と、それぞれに対応する4つのフロー束番号3310を設定する必要がある。
設定されるフローエントリ3110とフロー束番号3310を削減するため、フローを検出する条件として検出すべき入力回線グループ番号を入力回線グループ3111に、保護LSPのラベル値を入力ラベル3108に記載したエントリ3110と当該グループの番号と予備LSPのラベル値を記載したエントリ3110を設定し、さらに、当該エントリ3110に対応するフロー束番号3310を設定しても良い。この際、フローエントリ3110の条件として入力回線グループの番号を指定することで、設定すべきフローエントリ3110とフロー束番号3310の数を4から2に削減されることとなる。この様に本発明のパケット中継装置2600はフローエントリ3110内に入力回線グループ3111を備えることにより、フローエントリ3110の設定数を削減することを可能とする。
【０１００】
パケット中継装置2600の管理者は制御端末10によりフローテーブル3002の該フローエントリ3110およびフロー束テーブル3202のフロー束番号3310を設定する。ある入力回線グループを構成する入力回線2、3、4を一つのフロー束：flow_group1に集約するコマンドの例を図32の上段の3行に示す。図32に記載したコマンド：flowは、3502, 3503, 3504, 3505, 3506、3507、3510、3511、3512、3513、3509の各フィールドをフローエントリ3110のSIP3101, DIP3102, SPORT3103, DPORT3104, 入力回線番号3105、出力回線番号3106、入力ラベル3108、出力ラベル3109、入力回線グループ3111、出力回線グループ3112、In/Out3107の各フィールドに、3508の値を該エントリ3110に対応するフロー束番号3310に設定するコマンドである。図32の上段3行のコマンドflow j(j=1-3)は、フローエントリ3110-j(j=1-3)のSIP3101-j, DIP3102-j, SPORT3103-j, DPORT3104-j、出力回線番号3106-j、入力ラベル3108-j、出力ラベル3109-j、入力回線グループ3111、出力回線グループ3112に”*”を、入力回線番号3105-1、2、3にそれぞれ2、3、4を、In/Out3107にinを表す’1’を設定し、フロー束テーブル3202のフロー束番号3310-j(j = 1-3)に’1’を設定するコマンドである。
【０１０１】
制御端末10にこれらのコマンド(flow j(=1-3))が入力されると、制御端末10はパケット中継装置2600にフローテーブル3002への書き込み命令と、該テーブルのアドレス (図32のコマンドが入力された際にはj)と、該アドレスに対応する書き込み情報(図32のコマンドが入力された際には入力回線番号が2、3、4、In/Outが1、その他がマスク”*”)を送信する。フロー検出部2632が本情報を受信すると制御部3001が前記アドレスに対応する書き込み情報をフローテーブル3002に書き込む。同様に、制御端末10はパケット中継装置2600にフロー束テーブル3202への書き込み命令と、該テーブルのアドレスと(図32のコマンドが入力された際にはj(=1-3))と、該アドレスに対応する書き込み情報(図32のコマンドが入力された際には全て1)を送信する。フロー検出部2632のフロー束判定部3003が本情報を受信すると制御部3201が前記アドレスに対応する書き込み情報をフロー束テーブル3202に書き込む。
他のコマンドの例を図32の下段の1行に示す。本コマンドは入力回線2、3、4をこれらの入力回線が構成する入力回線グループ1として取り扱い、一つのフロー束：flow_group1に集約するコマンドである。この際のパケット中継装置2600のテーブル設定動作は設定値が異なる以外はflow1〜3の場合と同様である。
【０１０２】
他のコマンドの例として、ある入力回線グループを構成する入力回線2、3、4から受信するパケットのうち、入力回線番号が2であり、かつSIP3101とDIP3102がそれぞれ10.10.10.*、10.10.40.*であるか、入力回線番号が3であり、かつSIP3101とDIP3102がそれぞれ10.10.20.* 10.10.40.*であるか、入力回線番号が4であり、かつSIP3101とDIP3102がそれぞれ10.10.30.*、10.10.40.*であるパケットをflow_group2に集約するコマンドを図33に示す。この際のパケット中継装置2600のテーブル設定動作も前述の動作と同様である。
【０１０３】
これまでパケット受信時のフロー検出部2632の詳細動作について説明したが、パケット送信時のフロー検出部2632では、一致アドレス情報13の判定条件が異なるだけである。即ち、制御部3001がパケットヘッダ情報21を受信するとフローエントリ3110-1を読み出し、In/Out3107内の情報が’0’（パケット受信時には’1’）である場合に、SIP3101、DIP3102、SPORT3103、DPORT3104、出力回線番号3106、出力ラベル3108、出力回線グループ3112とパケットヘッダ情報21内のSIP311、DIP312、 SPORT313、DPORT314、出力回線番号336、ラベル318(出力用のラベルが設定される)、出力回線グループ333とを比較する(マスク値”*”が設定されている入力回線番号3105、入力ラベル3108と入力回線グループ3111とは比較しない)。一致した場合、一致したフローエントリ3110に対応するテーブルアドレスを一致アドレス情報13としてフロー束判定部3003へ送信することとなる。また、パケット受信時のフロー検出部2632と同様にフローエントリ3110内に出力回線グループ3112を備えることにより、フローエントリ3110の設定数を削減できる。
【０１０４】
（３）帯域監視部の詳細動作
以下、フロー束番号14を受信した帯域監視部2633の詳細動作について図34乃至37を用いて説明する。帯域監視のアルゴリズムとして固定長パケットであるセルの監視アルゴリズムであるcontinuous state Leaky Bucket Algorithm(以下リーキーバケットアルゴリズム)を可変長パケットの帯域監視用に拡張したアルゴリズムを使用する場合について説明する。リーキーバケットアルゴリズムに関しては例えばThe ATM Forum Specification version 4.0の4.4.2章に記載されている。リーキーバケットアルゴリズムはある深さを持った漏れバケツのモデルで、バケツに水が入っている間は監視帯域で水は漏れ、セル到着時にはバケツに１セル分の固定量の水が注ぎ込まれる。セルのバースト到着を許容するためにバケツに深さを持ち、バケツが溢れないうちは入力セルを「遵守」と、溢れると「違反」と判定する。本実施例ではパケット到着時に注ぎ込む水の量を可変とすることにより、可変長パケットの帯域監視を実現する。
【０１０５】
図34に帯域監視部2633のブロック図を示す。帯域監視部2633はバケツ蓄積量判定部2710と、監視結果判定部2720と、帯域監視テーブル2730と、帯域監視テーブル制御部2740より構成される。図35に帯域監視テーブル2730のフォーマットを示す。帯域監視テーブル2730はM個（≦N：フローエントリ3310-iのエントリ数）の帯域監視制御エントリ2800-k (k=1〜M)を備える。帯域監視部2633は一つの帯域監視制御エントリ2800-kにより一つのフロー束の帯域監視を実行する。
【０１０６】
帯域監視制御エントリ2800-kはバースト許容度を表すバケツの深さTHR(Threshold)2801(Byte)と、監視帯域を表すバケツが漏れる速度POLR(Policing Rate)2802(Byte/sec)と、同一のフロー束番号14が割り当てられたパケットが前回到着した時刻であるTS(Time Stamp)2803(sec)と、前パケットの帯域監視直後にバケツに蓄積していた水の量であるCNT(Count)2804(Byte)と、「遵守」および「違反」と判定したパケットに割り当てるDSCP値であるCDSCP (Conformant DSCP)2805とNDSCP (Non-Conformant DSCP)2806より構成される。THR2801とPOLR2802は、受信したパケットの「遵守」「違反」と判定する境界条件であり、CNT2804とTS2803は受信したパケットの到着履歴に対応する。
【０１０７】
図36に帯域監視部2633のフローチャートを示す。帯域監視部2633の処理は帯域監視開始処理2900、バケツ蓄積量判定処理2910、監視結果判定処理2920より構成される。2910、2920の二処理はそれぞれバケツ蓄積量判定部2710と、監視結果判定部2720が主に実行する。
【０１０８】
帯域監視部2633がパケットヘッダ情報21を受信すると、パケット長331を監視結果判定部2720のパケット長蓄積部2722に蓄積する(ステップ2901)。帯域監視テーブル制御回路2741はフロー束番号14に対応する帯域監視テーブル2730の読み出しアドレスを作成し、帯域監視制御エントリ2800を読み出し、THR2801とCDSCP2805とNDSCP2806を監視結果判定部2720のそれぞれTHR蓄積部2723、CDSCP蓄積部2724、NDSCP蓄積部2725に、POLR2802とTS2803とCNT2804をバケツ蓄積量判定部2710のそれぞれPOLR蓄積部2713、TS蓄積部2714、CNT蓄積部2715に蓄積する(ステップ2902)。
【０１０９】
バケツ蓄積量判定処理2910では、バケツ蓄積量判定部2710はパケット入力直前のバケツの水の量(バケツ蓄積量)を計算する。まず、バケツ蓄積量判定回路2711は現時刻をカウントするタイマー2712の値とTS蓄積部2714内の前パケットの到着時刻であるTS2803(sec)との差分を計算し、前パケット到着からの経過時間(sec)を計算する(ステップ2911)。次に経過時間(sec)にPOLR蓄積部2713内のPOLR2802(Byte/sec)を乗じて、前パケット到着から漏れた水の量(バケツ減少量)を計算する(ステップ2912)。さらに、CNT蓄積部2715内の前パケットの帯域監視直後のバケツ蓄積量であるCNT2804からバケツ減少量を減算してパケットが入力する直前のバケツ蓄積量を判定する(ステップ2913)。前記バケツ蓄積量の正負を判定し(ステップ2914)、判定結果が負の場合にはバケツ蓄積量を"０"(バケツは空)に修正する(ステップ2915)。
【０１１０】
監視結果判定処理2920では、監視結果判定部2720の監視結果判定回路2721は入力パケットのパケット長に相当する水がバケツに入るか否かを判定する。まず、バケツ蓄積量判定処理2910で計算したバケツ蓄積量(Byte)にパケット長蓄積部2722内のパケット長331(Byte)を加算する(ステップ2921)。THR蓄積部2723に蓄積されているバケツの深さTHR2801と前記加算値との大小比較を行い(ステップ2922)、バケツ蓄積量＋パケット長＞THR2801であって、パケット長に相当する水を入力した場合にバケツが溢れてしまう時には、入力パケットを「違反」と判定してNDSCP蓄積部2725内のNDSCP2806をDSCP情報26としてパケット送受信回路2611に送信する。さらに、「バケツ蓄積量」の値を帯域監視直後のバケツ蓄積量を表すバケツ蓄積量情報16として帯域監視テーブル制御回路2741に送信する(ステップ2924) 。一方、バケツ蓄積量＋パケット長≦THR2801の時には、入力パケットを「遵守」と判定してCDSCP蓄積部2724内のCDSCP2805をDSCP情報26としてパケット送受信回路2611に送信する。さらに、入力パケットに相当する水をバケツに加えるために「バケツ蓄積量＋パケット長」の値をバケツ蓄積量情報16として帯域監視テーブル制御回路2741に送信する(ステップ2923)。
【０１１１】
帯域監視テーブル制御回路2741はバケツ蓄積量情報16とタイマー2712の値を、それぞれ帯域監視直後のバケツ蓄積量およびパケットの到着時刻として、フロー束番号14に対応するエントリ2800のCNT2804とTS2803に書き戻す(ステップ2925)。
【０１１２】
これまで、上記帯域監視部2633がフロー束番号14毎に帯域の監視を行い、この監視結果に基づいてDSCP値を判定する場合について説明したが、「遵守」と判定されたパケットに対してはDSCP値を指定し、「違反」と判定されたパケットに対しては該パケットを廃棄することも可能である。例えば、パケット受信時には、パケット送受信回路2611が、DSCP情報26のDSCP値：”0”をパケット廃棄を表す値と解釈し、DSCP値が”0”の場合には図27のパケット送受信回路2611のパケット読み出し回路530がパケット一時蓄積バッファ520内のパケットを読み出さなければ良い。この際、該バッファ520内のパケットは入力回線201より次に入力されるパケットに上書きされて最終的に廃棄される。
【０１１３】
なお、制御端末10は帯域監視テーブル制御回路2741経由で帯域監視制御エントリ2800を設定する。図37に、flow_group1のパケットを監視帯域：100Mbps、バースト許容度：20kbyteで制限し、「遵守」と判定されたパケットに対してDSCPとして5を、「違反」と判定されたパケットに対して6を割り当てるコマンドを示す。このコマンド：policingにおいては、フロー束番号が3701、監視帯域とバースト許容度が3702と3703に、「遵守」および「違反」と判定されたパケットのDSCPが3704、3705に設定される。
【０１１４】
制御端末10にこれらのコマンドが入力されると、制御端末10はパケット中継装置2600に監視テーブル2730への書き込み命令と、該テーブルのアドレスと(図37のコマンドが入力された際には1))と、該アドレスに対応する書き込み情報(図37のコマンドが入力された際には100Mbps、20kbyte、5、6)を送信する。帯域監視部2633が本情報を受信すると帯域監視テーブル制御部2740の帯域監視テーブル制御回路2741は監視帯域である100MbpsをPOLR2802に、バースト許容度である20kbyteをTHR2801に、「遵守」または「違反」と判定されたパケットのDSCPである5および6をそれぞれCDSCP2805とNDSCP2806に書き込み、さらに、TS2803、CNT2804にはそれぞれ初期値であるタイマー2712値と0を書き込む。以上に説明した設定によりフロー束番号毎の帯域監視の設定が実現される。
【図面の簡単な説明】
【０１１５】
【図１】パケット中継装置200の構成の一例を示す図。
【図２】パケット中継装置200が送受信するパケットのフォーマットの一例を示す図。
【図３】パケット中継装置200におけるパケットのフォーマットの一例を示す図。
【図４】パケット送受信回路211の一構成例を示す図。
【図５】パケット中継装置200が送受信するMPLSパケットのフォーマットの一例を示す図。
【図６】パケット中継装置200におけるMPLSパケットのフォーマットの一例を示す図。
【図７】シェーピング部100の構成の一例を示す図。
【図８】出力回線番号テーブル600の一構成例を示す図。
【図９】パケット送信管理テーブル720の一構成例を示す図。
【図１０】FIFO管理テーブル730の一構成例を示す図。
【図１１】帯域ポリシー蓄積部740の一構成例を示す図。
【図１２】出力回線グループテーブル750の一構成例を示す図。
【図１３】パケットリード部150の一構成例を示す図。
【図１４】パケットリード部150のパケットリード時処理のフローチャート。
【図１５】帯域ポリシー蓄積部2440の一構成例を示す図。
【図１６】パケット送信管理テーブル2520の一構成例を示す図。
【図１７】シェーピング部1500の構成の一例を示す図。
【図１８】出力回線番号テーブル1600の一構成例を示す図。
【図１９】パケットリード部1550の一構成例を示す図。
【図２０】パケット送信管理テーブル1620の一構成例を示す図。
【図２１】FIFO管理テーブル1630の一構成例を示す図。
【図２２】帯域ポリシー蓄積部1640の一構成例を示す図。
【図２３】出力ラベルグループテーブル1650の一構成例を示す図。
【図２４】パケットリード部1550のパケットリード時処理のフローチャート。
【図２５】帯域ポリシー蓄積部を設定するコマンドの一例を示す図。
【図２６】パケット中継装置2600の構成の一例を示す図。
【図２７】パケット送受信回路2611の一構成例を示す図。
【図２８】フロー検出部2632の一構成例を示す図。
【図２９】フローテーブル3002の一構成例を示す図。
【図３０】フロー束判定部3003の一構成例を示す図。
【図３１】フロー束テーブル3202の一構成例を示す図。
【図３２】フローテーブル3002とフロー束テーブル3202を設定するコマンドの例を示す図。
【図３３】フローテーブル3002とフロー束テーブル3202を設定するコマンドの一例を示す図。
【図３４】帯域監視部2633の構成の一例を示す図。
【図３５】帯域監視テーブル2730の一構成例を示す図。
【図３６】帯域監視部2633のフローチャート。
【図３７】帯域監視テーブル2730を設定するコマンドの一例を示す図。
【符号の説明】
【０１１６】
11…パケット送信回線/クラス情報
12…送信パケット長情報
13…一致アドレス情報
14…フロー束番号
16…バケツ蓄積量情報
21…パケットヘッダ情報
22…パケット出力回線情報
23…パケットクラス情報
24…パケット送信信号
25…パケット送信要求信号
26… DSCP情報
100…シェーピング部
110…パケットバッファ
120…パケット一時蓄積バッファ
130…パケットライト部
140…蓄積FIFO判定部
150…パケットリード部
151…パケット送信回線/出力グループ情報
240…プロセッサ
【図１】
0004547341.tif 000002
【図２】
0004547341.tif 000003
【図３】
0004547341.tif 000004
【図４】
0004547341.tif 000005
【図５】
0004547341.tif 000006
【図６】
0004547341.tif 000007
【図７】
0004547341.tif 000008
【図８】
0004547341.tif 000009
【図９】
0004547341.tif 000010
【図１０】
0004547341.tif 000011
【図１１】
0004547341.tif 000012
【図１２】
0004547341.tif 000013
【図１３】
0004547341.tif 000014
【図１４】
0004547341.tif 000015
【図１５】
0004547341.tif 000016
【図１６】
0004547341.tif 000017
【図１７】
0004547341.tif 000018
【図１８】
0004547341.tif 000019
【図１９】
0004547341.tif 000020
【図２０】
0004547341.tif 000021
【図２１】
0004547341.tif 000022
【図２２】
0004547341.tif 000023
【図２３】
0004547341.tif 000024
【図２４】
0004547341.tif 000025
【図２５】
0004547341.tif 000026
【図２６】
0004547341.tif 000027
【図２７】
0004547341.tif 000028
【図２８】
0004547341.tif 000029
【図２９】
0004547341.tif 000030
【図３０】
0004547341.tif 000031
【図３１】
0004547341.tif 000032
【図３２】
0004547341.tif 000033
【図３３】
0004547341.tif 000034
【図３４】
0004547341.tif 000035
【図３５】
0004547341.tif 000036
【図３６】
0004547341.tif 000037
【図３７】
0004547341.tif 000038