(57)【要約】【課題】１種類のマーキングによって精度良くフローの強制切断を行う。【解決手段】入口側パケット転送装置及び中継パケット転送装置は、強制切断レートがトークン補充レートである第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツ処理とを行い、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてマーキングを行い、出口側のパケット転送装置は、入口側のパケット転送装置から送信されるパケットのマーク割合と、受信レートと、定数とに基づいて切断後レートを算出し、入口側のパケット転送装置は、算出された切断後レートに基づいて、受付けたフローを切断する。【選択図】図１
2011135443.tif 000002
【特許請求の範囲】
【請求項１】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムであって、
前記入口側パケット転送装置及び前記中継パケット転送装置は、
予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、
前記トークンバケツ処理部による処理結果に応じて、前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うマーキング実施部と、を備え、
前記出口側のパケット転送装置は、
前記入口側のパケット転送装置から送信されるパケットの総量と、前記入口側のパケット転送装置から送信されるパケットのうち前記マーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、前記前記入口側のパケット転送装置から送信されるパケットの受信レートと、前記定数とに基づいて切断後レートを算出するマーキング集計部と、
前記マーキング集計部によって算出された前記切断後レートを、前記入口側のパケット転送装置に送信するパケット生成部と、を備え、
前記入口側のパケット転送装置は、
前記出口側のパケット転送装置から送信される前記切断後レートに基づいて、前記受付けたフローを切断する流入規制部と、を備える
ことを特徴とするパケット転送システム。
【請求項２】
前記トークンバケツ処理部は、
予め定められた受付制御レートがトークン補充レートである受付制御用トークンバケツによる受付制御用トークンバケツ処理を行い、
前記マーキング処理部は、
前記受付制御用トークンバケツ処理に応じて、予め定められた複数回に１回の割合で前記パケットに対するマーキングを行い、
前記出口側のパケット転送装置の前記パケット生成部は、
前記マーク割合に応じて前記入口側のパケット転送装置が前記パケットの受付を拒否するか否かを示す通知を前記入口側のパケット転送装置に送信し、
前記入口側のパケット転送装置の前記流入規制部は、
前記出口側のパケット転送装置から送信される前記通知に基づいて受付制御を行う
ことを特徴とする請求項１に記載されたパケット転送システム。
【請求項３】
前記マーキング実施部は、
既にマーキングされた前記パケットが入力され、自身によりマーキングを行わない場合には当該パケットに対応するバイト数をストック情報として加算して記憶し、マーキングされていない前記パケットが入力され、自身によりマーキングを行うと判定した場合には前記ストック情報が示すバイト数から当該パケットに対応するバイト数を減算し、当該パケットにマーキングを行わない
ことを特徴とする請求項１または請求項２に記載されたパケット転送システム。
【請求項４】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける前記入口側パケット転送装置または前記中継パケット転送装置であって、
予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、
前記トークンバケツ処理部による処理結果に応じて、前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うマーキング実施部と、
を備えることを特徴とするパケット転送装置。
【請求項５】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、前記トークンバケツ処理部による処理結果に応じて、前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行い、前記トークンバケツ処理部および前記マーキング実施部を有する中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける前記出口側パケット転送装置であって、
前記入口側のパケット転送装置から送信されるパケットの総量と、前記入口側のパケット転送装置から送信されるパケットのうち前記マーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、前記前記入口側のパケット転送装置から送信されるパケットの受信レートと、前記定数とに基づいて切断後レートを算出するマーキング集計部と、
前記マーキング集計部によって算出された前記切断後レートを、前記入口側のパケット転送装置に送信するパケット生成部と、
を備えることを特徴とするパケット転送装置。
【請求項６】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、前記トークンバケツ処理部による処理結果に応じて、前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行い、前記トークンバケツ処理部および前記マーキング実施部を有する中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行い、前記入口側のパケット転送装置から送信されるパケットの総量と、前記入口側のパケット転送装置から送信されるパケットのうち前記マーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、前記前記入口側のパケット転送装置から送信されるパケットの受信レートと、前記定数とに基づいて切断後レートを算出するマーキング集計部と、前記マーキング集計部によって算出された前記切断後レートを、前記入口側のパケット転送装置に送信するパケット生成部とを有する出口側パケット転送装置とを備えたパケット転送システムにおける前記入口側パケット転送装置であって、
前記出口側のパケット転送装置から送信される前記切断後レートに基づいて、前記受付けたフローを切断する流入規制部
を備えることを特徴とするパケット転送装置。
【請求項７】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムのパケット転送方法であって、
前記入口側パケット転送装置及び前記中継パケット転送装置が、
予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うステップと、
前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うステップと、
前記出口側のパケット転送装置が、
前記入口側のパケット転送装置から送信されるパケットの総量と、前記入口側のパケット転送装置から送信されるパケットのうち前記マーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、前記前記入口側のパケット転送装置から送信されるパケットの受信レートと、前記定数とに基づいて切断後レートを算出するステップと、
前記マーキング集計部によって算出された前記切断後レートを、前記入口側のパケット転送装置に送信するステップと、
前記入口側のパケット転送装置が、
前記出口側のパケット転送装置から送信される前記切断後レートに基づいて、前記受付けたフローを切断するステップと、
を備えることを特徴とするパケット転送方法。
【請求項８】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける前記入口側パケット転送装置または前記中継パケット転送装置のコンピュータに、
予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うステップと、
前記トークンバケツ処理部による処理結果に応じて、前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うステップと、
を実行させるパケット転送プログラム。
【請求項９】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、前記トークンバケツ処理部による処理結果に応じて、前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行い、前記トークンバケツ処理部および前記マーキング実施部を有する中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける前記出口側パケット転送装置のコンピュータに、
前記入口側のパケット転送装置から送信されるパケットの総量と、前記入口側のパケット転送装置から送信されるパケットのうち前記マーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、前記前記入口側のパケット転送装置から送信されるパケットの受信レートと、前記定数とに基づいて切断後レートを算出するステップと、
算出された前記切断後レートを、前記入口側のパケット転送装置に送信するステップと、
を実行させるパケット転送プログラム。
【請求項１０】
複数のパケット転送装置により構成されるドメインにて、前記ドメインの入口側に配置され前記ドメイン外から送信されるパケットを受信して前記ドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、前記強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、前記トークンバケツ処理部による処理結果に応じて、前記第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合には前記パケットに対するマーキングを行わず、前記第１のトークンバケツにおける前記トークン量が予め定められた閾値以下である場合には前記第２のトークンバケツ処理に応じて前記パケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、前記ドメイン内で送信されるパケットを受信して中継を行い、前記トークンバケツ処理部および前記マーキング実施部を有する中継パケット転送装置と、前記ドメインの出口側に配置され前記ドメインを通じてパケットを受信して前記ドメイン外に転送を行い、前記入口側のパケット転送装置から送信されるパケットの総量と、前記入口側のパケット転送装置から送信されるパケットのうち前記マーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、前記前記入口側のパケット転送装置から送信されるパケットの受信レートと、前記定数とに基づいて切断後レートを算出するマーキング集計部と、前記マーキング集計部によって算出された前記切断後レートを、前記入口側のパケット転送装置に送信するパケット生成部とを有する出口側パケット転送装置とを備えたパケット転送システムにおける前記入口側のパケット転送装置コンピュータに、
前記出口側のパケット転送装置から送信される前記切断後レートに基づいて、前記受付けたフローを切断するステップ
を実行させるパケット転送プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ網における少なくとも電話を含むリアルタイム通信において、装置等の故障などによるルート変更によって生じる輻輳に対して過剰になったフローを切断する技術に関する。
【背景技術】
【０００２】
ＩＰ（Internet Protocol）網においてリアルタイム通信を行う際、ネットワーク内に流入するフローを過剰に受け付けると、サービス中のフローにパケット損失や遅延、遅延揺らぎなどが発生することがある。このパケット損失や遅延、遅延揺らぎなどは特定のフローに集中するわけではなく、ネットワーク内の全てのフローにほぼ均一に発生するため、全てのフローの品質が劣化し、最終的には全てのフローがサービスとして成り立たなくなってしまう。このためリアルタイム通信を実現するには、ネットワークの混雑状況に応じて新たなフローの流入を規制しなければならない。このようにフローの流入規制を行う制御をフローの受付制御という。ここで、このようなフローの受付制御だけでは、受付済みのフローの品質を確保することはできない場合がある。ＩＰ網では故障などが発生すると自動的にルート切り替えが発生するようになっている。このルート切り替えが発生するとあるリンクに多量のフローが流入することとなる。これは受付制御では制御不可能である。そのため、受付済みのフローの品質を確保するためには、受付制御に加えて一部のフローに対して強制切断が必要である。
【０００３】
例えば、図１６に示すような、発信者端末１１００−１と着信者端末１１００−２とがリアルタイム通信を行うＩＰ網を考える。ここで、中継パケット転送装置１２００−１と中継パケット転送装置１２００−３との間の回線に故障が発生すると、ルート切り替えが行われて入口側の境界パケット転送装置１３００−１と出口側の境界パケット転送装置１３００−３との間のルートは、図１７のように切り替わる。すなわち、中継パケット転送装置１２００−１と中継パケット転送装置１２００−３との間のフローが、中継パケット転送装置１２００−２を介して接続される。これにより、中継パケット転送装置１２００−２と中継パケット転送装置１２００−３との間に受付制御済みのフローが大量に流入し、輻輳が発生する場合がある。この場合、輻輳発生リンクを経由する全てのフローの品質が劣化してしまい、リアルタイム通信が成り立たなくなることが発生し得る。このような事態を防ぐためには、一部のフローを切断することで残ったフローの品質を確保する必要がある。
【０００４】
ここで、ＩＥＴＦ（Internet Engineering Task Force）のＰＣＮ  ＷＧ（Congestion and Pre-Congestion Notification Working Group）では、パケットにマーキングをすることで輻輳を事前に検知、通知するリアルタイム通信のＱｏＳ（Quality of Service）確保技術であるＰＣＮが議論されている（例えば、非特許文献１参照）。ＰＣＮでは、パケット転送装置間の各リンクに対して２つのレート閾値（受付制御レート(ＡＲ：admissible rate)、強制切断レート(ＳＲ：supportable rate)）を設け、実際に流れるトラヒックレートが各レート閾値を超えたときにパケットに対してマークを行い、そのマークを入口側と出口側パケット転送装置とのペア毎に集計して受付制御、強制切断を実施する。各リンクにおけるトラヒックレートは、この２つのレート閾値により３つの領域に分類され、領域毎に通信が制御される。トラヒックレートが受付制御レートよりも低い領域においては、新規フローを受付ける。トラヒックレートが受付制御レートよりも高く、強制切断レートよりも低い領域においては、新規フローの受付を拒否する。トラヒックレートが強制切断レートよりも高い領域においては、新規フローの受付を拒否すると同時に受付制御済みのフローの強制切断を行う。このように２つのレート閾値によって各リンクを３つの領域に分割し、各リンクでのレートがどの領域に属するかをマークによって判別し、通信を制御する。
【０００５】
非特許文献１には、１種類のマーキングによりこのような３つの領域を判別しようとする技術が示されている。ここでは、受付制御レートを超えた場合に１種類のマーキングを行っており、強制切断レートに応じたマーキングは行っていない。そこで、受付制御用のマーク情報に基づいて、実際のトラヒックレートが強制切断レートを超えたかどうかを推定する。この方式では、受付制御用のマーキングとして超過レートマーキング(excess traffic marking)を使用している。超過レートマーキングは、非特許文献２によって規定されているマーキング方式である。超過レートマーキングとは、あるレートでトークンを補充しトークンバケツ内のトークンが無くなったら（最大のパケットサイズ分よりも少なくなったら）、到着したパケットにマーキングを行う方法である。このマーキング方法の目的は、トラヒックがトークン補充レートを超えたときに、超えた分だけにマークを行うことである。
【０００６】
非特許文献１における各パケット転送装置はこのようなマーキング機能を持っており、受付制御レートを超えたときに超過レートマーキングの方法でマーキングを行う。出口側パケット転送装置では、入口側パケット転送装置毎に、受信するパケットのマーク割合を指数重み付き移動平均(ＥＷＭＡ)によって計算し、その値が０ではないときに、一定時間ごとにマーキングがなされていないレートを計測する。このレートを入口側パケット転送装置に送信し、入口側パケット転送装置ではそのレートにある定数Ｕをかけたレートを強制切断レートとして超過した分のフローを強制切断する。このとき定数Ｕはネットワーク全体でひとつの値に設定する必要がある。これによりマーキングの種類を１つにすることができ、内部パケット転送装置に要求される機能を少なくすることができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Charny et al., “Pre-Congestion Notification Using Single Marking for Admission and Termination”, Internet Draft: draft-charny-pcn-single-marking-03.txt, Internet Engineering Task Force, November 2007
【非特許文献２】Eardley, ”Meteringand marking behaviour of PCN-nodes,” Internet Draft: draft-ietf-pcn-markingbehaviour-05.txt（RFC5670）, Internet Engineering Task Force, August 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１の技術では、強制切断レートを実際のトラヒックレートの定数倍として算出しており、実際のトラヒックレートが強制切断レート閾値を超えているかどうかについて推定を用いているため精度が低いという課題がある。すなわち、このような強制切断レートと実際のトラヒックレートとを比較することによる判定に基づいてフローの強制切断を行うと、強制切断の必要がない状況において強制切断を行ったり、強制切断の必要がある状況において強制切断を行わなかったりする場合があると考えられる。
【０００９】
本発明は、このような状況に鑑みてなされたもので、１種類のマーキングによって精度良くフローの強制切断を行うパケット転送システム、パケット転送装置、パケット転送方法、及びパケット転送プログラムを提供する。
【課題を解決するための手段】
【００１０】
上述した課題を解決するために、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムであって、入口側パケット転送装置及び中継パケット転送装置は、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、トークンバケツ処理部による処理結果に応じて、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うマーキング実施部と、を備え、出口側のパケット転送装置は、入口側のパケット転送装置から送信されるパケットの総量と、入口側のパケット転送装置から送信されるパケットのうちマーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、入口側のパケット転送装置から送信されるパケットの受信レートと、定数とに基づいて切断後レートを算出するマーキング集計部と、マーキング集計部によって算出された切断後レートを、入口側のパケット転送装置に送信するパケット生成部と、を備え、入口側のパケット転送装置は、出口側のパケット転送装置から送信される切断後レートに基づいて、受付けたフローを切断する流入規制部と、を備えることを特徴とするパケット転送システム。
【００１１】
また、本発明は、トークンバケツ処理部が、予め定められた受付制御レートがトークン補充レートである受付制御用トークンバケツによる受付制御用トークンバケツ処理を行い、マーキング処理部が、受付制御用トークンバケツ処理に応じて、予め定められた複数回に１回の割合でパケットに対するマーキングを行い、出口側のパケット転送装置のパケット生成部が、マーク割合に応じて入口側のパケット転送装置がパケットの受付を拒否するか否かを示す通知を入口側のパケット転送装置に送信し、入口側のパケット転送装置の流入規制部が、出口側のパケット転送装置から送信される通知に基づいて受付制御を行うことを特徴とする。
【００１２】
また、本発明は、マーキング実施部が、既にマーキングされたパケットが入力され、自身によりマーキングを行わない場合にはパケットに対応するバイト数をストック情報として加算して記憶し、マーキングされていないパケットが入力され、自身によりマーキングを行うと判定した場合にはストック情報が示すバイト数からパケットに対応するバイト数を減算し、パケットにマーキングを行わないことを特徴とする。
【００１３】
また、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける入口側パケット転送装置または中継パケット転送装置であって、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、トークンバケツ処理部による処理結果に応じて、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うマーキング実施部と、を備えることを特徴とする。
【００１４】
また、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、トークンバケツ処理部による処理結果に応じて、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行い、トークンバケツ処理部およびマーキング実施部を有する中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける出口側のパケット転送装置であって、入口側のパケット転送装置から送信されるパケットの総量と、入口側のパケット転送装置から送信されるパケットのうちマーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、入口側のパケット転送装置から送信されるパケットの受信レートと、定数とに基づいて切断後レートを算出するマーキング集計部と、マーキング集計部によって算出された切断後レートを、入口側のパケット転送装置に送信するパケット生成部と、を備えることを特徴とする。
【００１５】
また、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、トークンバケツ処理部による処理結果に応じて、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行い、トークンバケツ処理部およびマーキング実施部を有する中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行い、入口側のパケット転送装置から送信されるパケットの総量と、入口側のパケット転送装置から送信されるパケットのうちマーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、入口側のパケット転送装置から送信されるパケットの受信レートと、定数とに基づいて切断後レートを算出するマーキング集計部と、マーキング集計部によって算出された切断後レートを、入口側のパケット転送装置に送信するパケット生成部とを有する出口側パケット転送装置とを備えたパケット転送システムにおける入口側のパケット転送装置であって、出口側のパケット転送装置から送信される切断後レートに基づいて、受付けたフローを切断する流入規制部を備えることを特徴とする。
【００１６】
また、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムのパケット転送方法であって、入口側パケット転送装置及び中継パケット転送装置が、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うステップと、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うステップと、出口側のパケット転送装置が、入口側のパケット転送装置から送信されるパケットの総量と、入口側のパケット転送装置から送信されるパケットのうちマーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、入口側のパケット転送装置から送信されるパケットの受信レートと、定数とに基づいて切断後レートを算出するステップと、マーキング集計部によって算出された切断後レートを、入口側のパケット転送装置に送信するステップと、入口側のパケット転送装置が、出口側のパケット転送装置から送信される切断後レートに基づいて、受付けたフローを切断するステップと、を備えることを特徴とする。
【００１７】
また、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付ける入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行う中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける入口側パケット転送装置または中継パケット転送装置のコンピュータに、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うステップと、トークンバケツ処理部による処理結果に応じて、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うステップと、を実行させるパケット転送プログラムである。
【００１８】
また、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、トークンバケツ処理部による処理結果に応じて、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行い、トークンバケツ処理部およびマーキング実施部を有する中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行う出口側パケット転送装置とを備えたパケット転送システムにおける出口側のパケット転送装置のコンピュータに、入口側のパケット転送装置から送信されるパケットの総量と、入口側のパケット転送装置から送信されるパケットのうちマーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、入口側のパケット転送装置から送信されるパケットの受信レートと、定数とに基づいて切断後レートを算出するステップと、算出された切断後レートを、入口側のパケット転送装置に送信するステップと、を実行させるパケット転送プログラムである。
【００１９】
また、本発明は、複数のパケット転送装置により構成されるドメインにて、ドメインの入口側に配置されドメイン外から送信されるパケットを受信してドメイン内に送信することによりリアルタイム通信のフローを受付け、予め定められた強制切断レートがトークン補充レートである第１のトークンバケツによる第１のトークンバケツ処理と、強制切断レートに対して予め定められた定数倍がトークン補充レートである第２のトークンバケツによる第２のトークンバケツ処理とを行うトークンバケツ処理部と、トークンバケツ処理部による処理結果に応じて、第１のトークンバケツにおけるトークン量が予め定められた閾値を超える場合にはパケットに対するマーキングを行わず、第１のトークンバケツにおけるトークン量が予め定められた閾値以下である場合には第２のトークンバケツ処理に応じてパケットに対するマーキングを行うマーキング実施部とを有する入口側パケット転送装置と、ドメイン内で送信されるパケットを受信して中継を行い、トークンバケツ処理部およびマーキング実施部を有する中継パケット転送装置と、ドメインの出口側に配置されドメインを通じてパケットを受信してドメイン外に転送を行い、入口側のパケット転送装置から送信されるパケットの総量と、入口側のパケット転送装置から送信されるパケットのうちマーキング実施部によってマーキングされたパケットの量との比であるマーク割合と、入口側のパケット転送装置から送信されるパケットの受信レートと、定数とに基づいて切断後レートを算出するマーキング集計部と、マーキング集計部によって算出された切断後レートを、入口側のパケット転送装置に送信するパケット生成部とを有する出口側パケット転送装置とを備えたパケット転送システムにおける入口側のパケット転送装置のコンピュータに、出口側のパケット転送装置から送信される切断後レートに基づいて、受付けたフローを切断するステップを実行させるパケット転送プログラムである。
【発明の効果】
【００２０】
以上説明したように、本発明によれば、１種類のマーキングによって精度良くフローの強制切断を行うことができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態によるパケット転送システムの構成例を示す図である。
【図２】本発明の一実施形態によるパケット転送システムのマルチドメインの構成例を示すブロック図である。
【図３】本発明の一実施形態によるマーク割合とレートとの関係を示す図である。
【図４】本発明の一実施形態による中継パケット転送装置の構成例を示すブロック図である。
【図５】本発明の一実施形態による出回線対応部の構成例を示すブロック図である。
【図６】本発明の一実施形態によるトークンバケツの例を示すブロック図である。
【図７】本発明の一実施形態による境界パケット転送装置の例を示すブロック図である。
【図８】本発明の一実施形態によるパケット転送システムのマーキング処理の動作例を示すフローチャートである。
【図９】本発明の一実施形態によるパケット転送システムの切断後レート通理処理の動作例を示すフローチャートである。
【図１０】参考文献による受付制御を行う場合のマーク割合とレートとの関係を示す図である。
【図１１】参考文献による受付制御を行う擬似コードを示す図である。
【図１２】本実施形態により受付制御を行うトークンバケツの例を示す図である。
【図１３】本実施形態による受付制御を行う場合のマーク割合とレートとの関係を示す図である。
【図１４】参考文献による受付制御を行う擬似コードを示す図である。
【図１５】本実施形態による受付制御を行う場合のマーク割合とレートとの関係を示す図である。
【図１６】従来技術によるパケット転送システムの構成例を示す図である。
【図１７】従来技術によるパケット転送システムにおいてルート切り替えが行われた例を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の一実施形態について、図面を参照して説明する。
図１は、本実施形態によるパケット転送システム１の簡単な一構成例を示す図である。ここではシングルドメインを例にしており、発信者端末１００−１は入口側の境界パケット転送装置３００−１に接続され、境界パケット転送装置３００−１からは中継パケット転送装置２００−１と中継パケット転送装置２００−２とを経由して出口側の境界パケット転送装置３００−２に接続され、着信者端末１００−２に接続される。図１では、ひとつのドメイン内に発信者端末１００−１と着信者端末１００−２とが収容されている例を示しているが、図２のように複数ドメインをまたぐ場合には複数の境界パケット転送装置３００（入口側または出口側）は隣接するドメイン間を接続することになる。このようなマルチドメインの場合には、例えば、境界パケット転送装置３００−２が、自ドメイン内での処理結果を隣接するドメインの境界パケット転送装置３００−３に送信する。
【００２３】
本実施形態では、複数台の中継パケット転送装置２００（中継パケット転送装置２００−１〜中継パケット転送装置２００−４、・・・）、複数台の境界パケット転送装置３００（境界パケット転送装置３００−１〜境界パケット転送装置３００−４、・・・）を示して説明するが、同名の装置は同様の構成であるので、特に区別して説明する必要がない場合には中継パケット転送装置２００、境界パケット転送装置３００として説明する。本実施形態では、図１のようなシングルドメインを例に説明する。
【００２４】
まず、本実施形態のマーキングによって実現するマーク割合とトラヒックレートとの関係について説明する。図３は、本実施形態のリンクにおけるトラヒックレートとマーク割合とのグラフを示す。トラヒックレートが強制切断レート（ＳＲ）よりも低ければマーク割合を０とする。また、トラヒックレートが強制切断レート（ＳＲ）よりも高く、Ｗ×強制切断レート（ＳＲ）よりも低ければ、マーク割合ｍとレートｒとの間に以下式（１）によって示される比例関係がある。
【００２５】
ｍ＝ｒ／（Ｗ・ＳＲ）  （ＳＲ≦ｒ≦（Ｗ・ＳＲ））  ・・・（１）
【００２６】
ここで、入口側と出口側との境界パケット転送装置３００のペアでマーキングを観測している場合には、一般に複数のリンクを経由してくるためＳＲはわからない。しかし単一のボトルネックであればマーク割合と受信レートとの間に比例関係がある。また、ＳＲにおけるマーク割合は１／Ｗである。これらのことから、ｘを入口側・出口側パケット転送装置ペアの受信レートとし、ｙを入口側・出口側パケット転送装置ペアでのマーク割合とすると、提供可能なレート（強制切断を行わなくて良いレートの上限値）ｚは、以下式（２）により表される。
【００２７】
ｚ＝ｘ／Ｗｙ  ・・・（２）
【００２８】
ここで、管理対象のドメイン内に複数のボトルネックがある場合には、送信されるパケットが複数の中継パケット転送装置２００を経由してマークが累積することによりマーク割合と受信レートとの間の比例関係が成り立つとは限らない。複数ボトルネックの場合には、一度の切断ではなく複数回の切断により、最終的には単一ボトルネックになることが期待される。なぜならば複数ボトルネックの負荷がすべて同じということは極めて稀であると期待されるからである。複数回切断を行う際には、Ｗを比較的小さめに設定してマーキングされるパケットの量を増やすことにより、一回の強制切断でｘ＝Ｗになるように切断し、これを繰り返すことで最終的に必要な分の切断を行う。
【００２９】
次に、このようなマーク割合とトラヒックレートとの関係を実現して通信制御を行う中継パケット転送装置２００と境界パケット転送装置３００との構成を説明する。
図４は、中継パケット転送装置２００の構成を示すブロック図である。中継パケット転送装置２００は、複数の入り回線対応部２１０と、スイッチ部２２０と、複数の出回線対応部２３０とを備えている。ここで、複数の入り回線対応部２１０と複数の出回線対応部２３０とは、中継パケット転送装置２００が接続される物理回線に対応してそれぞれ装備される。ただし、異なる物理回線に接続される他は同様の構成であるので、特に区別して説明する必要がない場合には、それぞれ入り回線対応部２１０、出回線対応部２３０として説明する。
【００３０】
入り回線対応部２１０は、中継パケット転送装置２００に送信されたパケットを受信し、スイッチ部２２０に入力する前に一時的に保持する機能を持つ。
スイッチ部２２０は、自身の記憶領域に予め記憶したルーティングテーブルと、入り回線対応部３１０から入力されたパケットのパケットヘッダに含まれる宛先のアドレスとを比較して、中継パケット転送装置２００が備える複数の出回線対応部２３０のうち、宛先のアドレスに応じて適切な出回線対応部２３０にパケットを転送する。
【００３１】
出回線対応部２３０は、出力側回線の帯域（レート）に合うようにレートを成形し、パケットを送出する。また、出回線対応部２３０は送出するパケットにマーキング処理を行う。図５は、出回線対応部２３０の詳細な構成を示すブロック図である。出回線対応部２３０は、トークンバケツによる処理を行うトークンバケツ処理部２３１と、パケットに対するマーキングを行うマーキング実施部２３２と、パケットを待ちキューに入れ物理回線の帯域（レート）に成形する待ちキュー部２３３と、実際に物理回線にパケットを送出する物理回線対応部２３４とを備えている。
【００３２】
トークンバケツ処理部２３１は、スイッチ部２２０からパケットが入力されると、定められたトークンバケツ処理を行う。トークンバケツ処理部２３１は、図６のように２つのトークンバケツを用意する。ひとつ目のトークンバケツ（バケツ１、第１のバケツ）のトークン補充レートは強制切断レート（ＳＲ）とし、もうひとつのトークンバケツ（バケツ２、第２のバケツ）のトークン補充レートはＷ×強制切断レート（ＳＲ）とする。バケツ１には閾値(TB1.threshold)を設定する。通常のトークンバケツと同様にバケツからあふれたトークンは廃棄される。
【００３３】
マーキング実施部２３２は、トークンバケツ処理部２３１の処理結果に応じてパケットにマーキングを行う。マーキング実施部２３２は、トークンバケツ処理部２３１のトークンバケツ処理により、トークンがバケツ１の閾値よりも多く溜まっているときにはマーキングスイッチをＯＦＦとして一切マーキングを行わない。一方、マーキング実施部２３２は、バケツ１のトークンが閾値よりも少なくなっているときにはマーキングスイッチをＯＮとしてバケツ２に従ってマーキングを行う。
【００３４】
マーキング実施部２３２に入力されるパケットには、前段のパケット転送装置で既にパケットにマーキングがなされている場合があるが、簡単のため単一ボトルネックの場合、すなわち前段のパケット転送装置で一切マーキングがなされていないとした説明を行う。ここで、前段のパケット転送装置によって既にパケットにマーキングがなされている場合の処理について説明する。ここでは、パケットに既に前段のパケット転送装置によるマーキング有り無し、新規にマーキング有り無しの組み合わせにより４通りの場合がある。
【００３５】
１．既にマーキング無し、新規にマーキング無し
２．既にマーキング無し、新規にマーキング有り
３．既にマーキング有り、新規にマーキング無し
４．既にマーキング有り、新規にマーキング有り
【００３６】
１．の場合については両方マーキング無しであるので、トークンバケツ処理部２３１によるトークンバケツ処理のみを行ってマーキングを行なわずに転送する。４．の場合には本来新規にマーキングを行うところであるが、既にマーキングがなされているため、トークンバケツ処理のみを実施して転送する。３．の場合には新規にマーキングがされないが既にマーキングがなされているため、このまま転送してしまうとこのパケット転送装置で付くマークの割合が高くなってしまう。
【００３７】
そこで、マーキング実施部２３２は、この過剰についているマークパケット分のバイト数をトークンとは別にストックとして自身の記憶領域に記憶させる。マーキング実施部２３２は、３．の状況が発生するごとに到着したパケットのバイト数分だけストックを加算していく。そして、２．の状況が発生すると逆にストック分から到着パケットのバイト数分だけ減算し、減算すべきストックが存在するときにはマーキングを行わず、減算すべきストックがない、すなわちストックが０である場合にのみパケットにマーキングを行うようにする。
【００３８】
また、マーキング実施部２３２は、トークンバケツ処理部２３１によるトークンバケツ１のトークン量が閾値未満になり、そのときのトークンバケツ２のトークン量がトークンバケツ２のバケツサイズではない場合に、そのパケットにマーキングを行う。それ以外の場合にはマーキングはせずに待ちキュー部２３３にパケットを送る。このトークンバケツにより、レートがＳＲよりも低ければ一切マークされないことがわかる。
【００３９】
さらに参考文献１（Ｌ.クラインロック著：待ち行列システム理論（上）、マグロウヒル好学社、pp.17−18）により、パケットの到着過程がポアソン過程に従うならば、パケットのバイト数によらず、ＳＲ≦ｘ≦Ｗ・ＳＲのときにマーク割合ｍが上記式（１）で表されることが示されている。つまり使用率（ｘ／ＳＲ）は、ポアソン過程に従ってビジー割合（トークンが満タンでないか）を観測した値に一致する（ＰＡＳＴＡ（Poisson Arrivals See Time Average））。ここで、多数のフローが多重されているときには、そのフロー内のパケットの到着過程がポアソン過程に従わなくても、多重化されたものはポアソン過程で非常に良く近似されるため、近似的に上記式（１）が成り立つ。参考文献２(D.R.Cox: Renewal Theory, John Wiley & Sons, 1962.)に、フロー内のパケットの到着過程が再生過程に従うとき、フロー数無限大の極限でパケットの到着過程はポアソン過程になることが示されている。
【００４０】
マーキング実施部２３２によってマーキング処理が行われたパケットは、待ちキュー部２３３を経由して、物理回線対応部２３４によって中継パケット転送装置２００から送出される。
【００４１】
図７は、境界パケット転送装置３００の構成を示すブロック図である。境界パケット転送装置３００は、入り回線対応部３１０と、流入規制部３２０と、マーキング集計部３３０と、パケット生成部３４０と、スイッチ部３５０と、出回線対応部３６０とを備えている。ここで、入り回線対応部３１０、スイッチ部３５０、出回線対応部３６０は、中継パケット転送装置２００が備える同名の機能部である入り回線対応部２１０、スイッチ部２２０、出回線対応部２３０と同様の構成である。すなわち、境界パケット転送装置３００は中継パケット転送装置２００が備える全ての機能部と同様の構成を少なくとも備えている。
【００４２】
境界パケット転送装置３００は、ドメインの出口側として動作する場合と、入口側として動作する場合とで働きが異なる。まず出口側として動作する場合の処理を説明する。出口側の機能としては中継パケット転送装置２００の持つ機能に加えてマーキング集計部３３０とパケット生成部３４０とがある。入り回線対応部３１０がパケットを受信すると、受信されたパケットは流入規制部３２０を通って（出口側のときには流入規制部の働きはない）マーキング集計部３３０に到着する。
【００４３】
マーキング集計部３３０は、入力されるパケットを、ドメインの入口側の境界パケット転送装置３００ごとに分類する。また、マーキング集計部３３０は、マーク付きパケットを検出すると、予め決められた時間Ｔに到着したパケットの総バイト数と、到着したパケットのうちマーク付きパケットの総バイト数とを計測し、「マーク付きパケットの総バイト数／受信パケットの総バイト数」の値をマーク割合として算出する。また、マーキング集計部３３０は、「受信パケットの総バイト数／Ｔ」の値である受信レートを算出する。
マーキング集計部３３０は、算出したマーク割合が１／Ｗよりも小さい場合には、フロー切断後のレートを算出せずに再度マーク付きパケットの検出を行う。これらの計測結果から、切断後レートを「受信レート／(Ｗ×マーク割合)」として算出する。マーキング集計部３３０は、算出した切断後レートと、対応する入口側の境界パケット転送装置３００との情報をパケット生成部３４０に入力する。
パケット生成部３４０は、マーキング集計部３３０から入力された切断後レートの情報が含まれるパケットを生成し、スイッチ部３５０と出回線対応部３６０とを介して、対応する入口側の境界パケット転送装置３００に送信する。
【００４４】
次に、境界パケット転送装置３００が入口側として動作する場合の処理を説明する。入口側の境界パケット転送装置３００は、出口側の境界パケット転送装置３００から切断後レートが格納されたパケットが送信され、入り回線対応部３１０によって受信されると、流入規制部３２０が、切断後レートが格納されたパケットを受信したことを検出する。流入規制部３２０は、検出したパケットをマーキング集計部３３０に入力する。マーキング集計部３３０は、そのパケットの送信元である出口側の境界パケット転送装置３００を識別して判定し、判定した出口側の境界パケット転送装置３００への送信パケットのバイト数をフローごとに計測する。マーキング集計部３３０は、Ｔ時間後フローごとの総送信バイト数をＴで割ることでフローごとの送信レートを求める。全てのフローの送信レートの合計とフロー切断後のレートとの差のレートを求め、その差のレートと複数のフローの送信レートの合計値が一致するように切断するフローを選択する。マーキング集計部３３０は、選択したフローのリストを流入規制部３２０に送信する。流入規制部３２０は、自身の記憶領域に記憶させた保留中フローリストから選ばれたフローの情報を削除する。以後、流入規制部３２０は、切断されたフローに属するパケットが送信されてきても保留中フローリストに入っていないためネットワーク内部に転送せずそのパケットを廃棄する。これにより強制切断されることとなる。それら切断されたフローは再度受付制御により受付可能となれば再度保留中リストに加えられ、ネットワーク内部への流入が許可される。
【００４５】
次に、図面を参照して、本実施形態のパケット転送システム１の動作例を説明する。図８は、本実施形態の中継パケット転送装置２００によるマーキング処理の動作例を示すフローチャートである。ただし、境界パケット転送装置３００によるマーキング処理の動作例も同様である。
この図では、ｔａは中継パケット転送装置２００にパケットが到着した時間、ＬＣＴは一つ前のパケットが中継パケット転送装置２００に到着した時間、ｔｏｋｅｎ１、ｔｏｋｅｎ２はそれぞれバケツ１、バケツ２に溜めるトークン、Ｔｃ１、Ｔｃ２はそれぞれパケットが到着した時点でのバケツ１、バケツ２のトークン量、ＴＢ．Ｓｉｚｅ１、ＴＢ．Ｓｉｚｅ２はそれぞれバケツ１、バケツ２のサイズ、ｐｋ.Ｓｉｚｅはパケットサイズ[ｂｙｔｅ]である。Ｓｔｋはストックを表している。
【００４６】
マーキング実施部２３２は、処理開始段階では、ストック（ｓｔｋ）に０を代入する（ステップＳ１）。出回線対応部２３０にパケットが到着すると、トークンバケツ処理部２３１は、ｔｏｋｅｎ１にＳＲ×（ｔａ−ＬＣＴ）を代入し、ｔｏｋｅｎ２にＷ×ＳＲ×（ｔａ−ＬＣＴ）を代入する（ステップＳ３）。トークンバケツ処理部２３１は、バケツ１にトークンを追加した値（Ｔｃ１＋ｔｏｋｅｎ１）がバケツ１のサイズ（ＴＢ．Ｓｉｚｅ１）を超えているか、またバケツ２にトークンを追加した値（Ｔｃ２＋ｔｏｋｅｎ２）がバケツ２のサイズ（ＴＢ．Ｓｉｚｅ２）を超えているかを判定する（ステップＳ４）。
【００４７】
トークンバケツ処理部２３１は、ステップＳ４において、バケツ１にトークンを追加した値（Ｔｃ１＋ｔｏｋｅｎ１）がバケツ１のサイズ（ＴＢ．Ｓｉｚｅ１）を超えているか、またはバケツ２にトークンを追加した値（Ｔｃ２＋ｔｏｋｅｎ２）がバケツ２のサイズ（ＴＢ．Ｓｉｚｅ２）を超えていると判定すると、Ｔｃ１にＴＢ．Ｓｉｚｅ１の値を代入し、Ｔｃ２にＴＢ．Ｓｉｚｅ２の値を代入する（ステップＳ６）。一方、トークンバケツ処理部２３１は、ステップＳ４において、トークンを加えたバケツのトークン量がバケツサイズを超えていないと判定すれば、バケツにトークンを加算する（ステップＳ５）。
【００４８】
そして、トークンバケツ処理部２３１は、Ｔｃ１から、ｐｋ.Ｓｉｚｅを減算する（ステップＳ７）。そして、トークンバケツ処理部２３１は、Ｔｃ１が０より小さいか否かを判定する（ステップＳ８）。ここで、トークンバケツ処理部２３１が、Ｔｃ１が０より小さいと判定すれば、Ｔｃ１に０を代入する（ステップＳ９）。一方、トークンバケツ処理部２３１は、Ｔｃ１が０以上であると判定すれば、Ｔｃ１がＴＢ１の閾値以上であるか否かを判定する（ステップＳ１０）。Ｔｃ１がＴＢ１の閾値以上であると判定すれば、ステップＳ２０に進む。トークンバケツ処理部２３１が、Ｔｃ１はＴＢ１の閾値以上でないと判定すれば、マーキング実施部２３２は、ＴＣ２とＴｂ．Ｓｉｚｅ２とが一致するか否かを判定する（ステップＳ１１）。
【００４９】
マーキング実施部２３２は、ＴＣ２とＴｂ．Ｓｉｚｅ２が一致すると判定すると、パケットに既にマークがあるか否かを判定する（ステップＳ１２）。ここで、パケットに既にマークがあると判定すれば、マーキング実施部２３２は、パケットサイズをストックに加える（ステップＳ１３）。パケットにマークがないと判定すれば、ステップＳ２０に進む。ステップＳ１１において、マーキング実施部２３２が、ＴＣ２とＴｂ．Ｓｉｚｅ２とが一致しないと判定すると、パケットに既にマークがあるか否かを判定する（ステップＳ１４）。マーキング実施部２３２が、パケットに既にマークがあると判定すれば、ステップＳ２０に進む。
【００５０】
一方、ステップＳ１４において、マーキング実施部２３２が、パケットにマークがないと判定すれば、ストックは０より大きいか否かを判定する（ステップＳ１５）。マーキング実施部２３２が、ストックは０より大きいと判定すれば、ストックからパケットサイズを減算する（ステップＳ１６）。そして、マーキング実施部２３２は、ストックが０より小さいか否かを判定する（ステップＳ１７）。ストックが０より小さいと判定すれば、マーキング実施部２３２は、ストックを０として記憶する（ステップＳ１８）。ストックが０以上であると判定すれば、ステップＳ２０に進む。
【００５１】
ステップＳ１５において、ストックは０以下であると判定すれば、マーキング実施部２３２は、パケットにマーキングを行う（ステップＳ１９）。そして、バケツ２のトークン量からパケットサイズを減算する（ステップＳ２０）。トークンバケツ処理部２３１は、バケツ２のトークン量が０より小さいか否かを判定する（ステップＳ２１）。バケツ２のトークン量が０より小さいと判定すれば、トークンバケツ処理部２３１は、バケツ２のトークン量を０にする（ステップＳ２２）。バケツ２のトークン量が０以上であると判定すれば、ステップＳ２に戻る。
【００５２】
図９は、本実施形態の出口側の境界パケット転送装置３００による通知処理の動作例を示すフローチャートである。
マーキング集計部３３０は、流入規制部３２０を介して入力されるパケットのうちに、
マーク付きパケットが含まれるか否かを判定する（ステップＳ３０）。マーキング集計部３３０は、マーク付きパケットが含まれていなければ、ステップＳ３０の処理を繰り返す。マーク付きパケットが含まれていれば、受信レートとマーク割合とを算出する（ステップＳ３１）。そして、マーク割合が１／Ｗより大きいか否かを判定する（ステップＳ３２）。マーキング集計部３３０は、マーク割合が１／Ｗより大きいと判定すれば、ステップＳ３０に戻る。マーク割合が１／Ｗ以下であると判定すれば、受信レート／（Ｗ×マーク割合）の値を、切断後レートとして算出する（ステップＳ３３）。マーキング集計部３３０は、パケット生成部３４０に、切断後レートと、対応する入口側の境界パケット転送装置３００の情報とを通知する。パケット生成部３４０は、切断後レートを示す情報が格納されたパケットを生成して、対応する入口側の境界パケット転送装置３００の情報に送信する。
【００５３】
以上では、出回線対応部２３０が強制切断のためのマーキングを行う例を示したが、同一の種類のマーキングを用いて、受付制御を行うことができる。すなわち、出回線対応部２３０は、受付制御のためのマーキングと、強制切断のためのマーキングとを組み合わせたマーキング処理を行う。受付制御は、例えば、参考文献３（Satoh et al., ”Single PCN Threshold Marking by using PCN baseline encoding for both admission and termination controls,” Internet Draft: draft-satoh-pcn-st-marking-02.txt, Internet Engineering Task Force, September 2009)に記載された方式により行なう。
【００５４】
この方式では、図１０に示すようなレートとマーク割合との関係を実現しており、１種類のマークで３つの領域を区別している。この図においてマーク割合が１でないレートが受付制御を行う領域である。これにより、マークの累積により本来切断不要な場合に誤ってフローを切断することを防ぐことができる。図１１は、この方式によるトークンバケツ処理を示す擬似コードである。ここでは、受付制御レートでトークンが補充されるＳｗＴＢ（受付制御レートよりトラヒックのレートが低い場合には一切マークしないようにする目的に用いる)と、強制切断レートでトークンが補充されるＭｋＴＢ(受付制御レートよりもトラヒックのレートが高いときに部分的にトラヒックにマークを付ける目的に用いる）とのトークンバケツを用いている。
【００５５】
この図において、ＳｗＴＢ.ｓｉｚｅ、ＭｋＴＢ.ｓｉｚｅは、それぞれＳｗＴＢ、ＭｋＴＢのサイズを示し、ＳｗＴＢ.ｆｉｌｌ、ＭｋＴＢ.ｆｉｌｌは、それぞれＳｗＴＢ、ＭｋＴＢのトークン量を示し、ＳｗＴＢ.ｒａｔｅ、ＭｋＴＢ.ｒａｔｅは、それぞれＳｗＴＢ、ＭｋＴＢのトークン補充レート（すなわち受付制御レートと強制切断レート）を示し、ＳｗＴＢ.Ｔｈｒｅｓｈｏｌｄ、ＭｋＴＢ.Ｔｈｒｅｓｈｏｌｄは、それぞれＳｗＴＢ、ＭｋＴＢの閾値を示し、ｐａｃｋｅｔ.ｓｉｚｅは到着したパケットのサイズを示し、ｐａｃｋｅｔ.ｍａｒｋはパケットのマーク状態を示し、ｍａｒｋＣｎｔはカウンタを示し、ｌａｓｔＵｐｄａｔｅは２つのバケツで前回アップデートした時間を示し、ｎｏｗは現在の時間を示している。
【００５６】
上述の強制切断のトークンバケツ処理と、受付制御のトークンバケツ処理とを組み合わせる場合には、図１２のように３つのトークンバケツを使う。変更点は、新たに受付制御レートでトークンが補充されるバケツ（バケツ０）が加わることと、バケツ１におけるＴＢ１.ｔｈｒｅｓｈｏｌｄよりもトークンが溜まっているときに、マーキングスイッチＯＦＦではなく、Ｎパケット中で１パケットにマークを行うことである。新たに加わったバケツ０では、バケツ１と同様に閾値ＴＢ０.ｔｈｒｅｓｈｏｌｄが設定されており、この閾値よりもトークンが溜まっている場合には、マーキングスイッチをＯＦＦとして一切マークを付けない。ＴＢ０.ｔｈｒｅｓｈｏｌｄよりもトークンが下回った場合にはバケツ１へのマーキングスイッチをＯＮとしてバケツ１に従って処理を行う。パケット生成部３４０は、マーク付きパケットの割合に応じて、入口側の境界パケット転送装置３００がパケットの受付を拒否するか否かを示す通知が含まれるパケットを生成し、入口側の境界パケット転送装置３００に送信する。受付を拒否することを示す通知を受信した入口側の境界パケット転送装置３００の流入規制部３２０は、新規フローの受付を拒否する。
【００５７】
このような強制切断のトークンバケツ処理と、受付制御のトークンバケツ処理とを組み合わせると、レートとマーク割合との関係は図１３に示すようになる。ここで、レートが強制切断レートのときにマーク割合でギャップを作ることが重要である。すなわち本実施形態での強制切断レートのマーク割合を参考文献３におけるマーク割合よりも十分高くする必要がある。
【００５８】
あるいは、受付制御のマーキング処理として、参考文献４（Menth, M., et al., “A Survey of PCN-BasedAdmission Control and Flow Termination, IEEE Communications Survey and Tutorials,to appear.）および参考文献５（佐藤、上野、前田：単一マークで３つの帯域領域を表現するPCN アルゴリズムの性能評価、信学技報IN2009-88, pp.7-12, 2009.)に記載の受付制御方式を適用しても良い。この方式ではレートに対するマーク割合を、図１３に示した受付制御レートと強制切断レートとの間の直線を横軸に平行にしたものである。受付制御レートよりもトラヒックのレートが高いと１／Ｎの割合でマークがなされ、強制切断レートを超えると全てにマークがなされる。
【００５９】
図１４はこの方式の擬似コードを示す図である。Ｆｒ.ＴＢは１／Ｎの割合でマークを行うトークンバケツであり、Ｔｈ.ＴＢはすべてにマークを行うトークンバケツである。この場合にも、上述の方式と同様に強制切断レートでのマーク割合にギャップを作ることが重要である。このマーキングは分数マーキングと呼ばれる。ここでＦｒＴＢ．Ｓｉｚｅ、ＴｈＴＢ.Ｓｉｚｅは、それぞれＦｒＴＢ、ＴｈＴＢのサイズ、ＦｒＴＢＰ．ｆｉｌｌ、 ＴｈＴＢ.ｆｉｌｌは、それぞれＦｒＴＢ、ＴｈＴＢのトークン量、ＦｒＴＢ.Ｒａｔｅ、 ＴｈＴＢ．ｒａｔｅは、それぞれＦｒＴＢ、ＴｈＴＢのトークン補充レート、すなわち受付制御レートと強制切断レートであり、ＦｒＴＢ．Ｔｈｒｅｓｈｏｌｄ、ＴｈＴＢ．Ｔｈｒｅｓｈｏｌｄは、それぞれＦｒＴＢ、ＴｈＴＢの閾値、ｐａｃｋｅｔ．Ｓｉｚｅは到着したパケットのサイズ、ｐａｃｋｅｔ．ｍａｒｋはパケットのマーク状態、ｍａｒｋＣｎｔはカウンタ、ｌａｓｔＵｐｄａｔｅは２つのバケツで前回アップデートした時間、ｎｏｗは現在の時間である。
【００６０】
上述の強制切断のトークンバケツ処理と、この方式の受付制御のトークンバケツ処理とを組み合わせる場合には、図１５のように３つのトークンバケツを使う。変更点は、新たに受付制御レートでトークンが補充されるバケツ（バケツ０）が加わることと、バケツ１におけるＴＢ１.ｔｈｒｅｓｈｏｌｄよりもトークンが溜まっているときにマーキングスイッチＯＦＦではなく新たに加わったバケツ０に従ってマーキングを行うことである。すなわちバケツ１は新たに加わったバケツ０かバケツ２のどちらでマーキング処理をするのかを仕分けを行う。新たに加わったバケツ０では、上述と同様に閾値ＴＢ０.ｔｈｒｅｓｈｏｌｄが設定されており、この閾値よりもトークンが溜まっている場合には、一切マークを付けず、ＴＢ０.ｔｈｒｅｓｈｏｌｄよりもトークンが下回った場合には上記アルゴリズムに従い分数マーキングを行う。
【００６１】
以上説明したように、本実施形態によれば、フローが過剰になった場合に強制切断を行う切断量を、推定することなく、直接計測して求めることができる。また、Ｗに応じて強制切断レートを超えた場合のマーク割合が求まるため、受付制御レートを超えたことによるマークが複数のボトルネックリンクによるマークの累積を考慮したマーク割合よりも、強制切断レートを超えたときのマーク割合が高くなるようにＷを設定すれば、マークあり、マーク無しの状態しか表現できないという制約下でマーク割合により実際のトラヒックレートが強制切断レートを超えているかそうでないかを判別することができる。
【００６２】
また、従来技術では、過剰なフローの強制切断を行う際、１回の切断で決められた割合のレートを切断しこれを繰り返すことで最終的に必要な量を切断している。この場合、予め決められた割合分を小さく取ると精度があがるが、切断に時間がかかってしまう。一方、その割合を大きく取ると必要な分の切断にかかる時間は小さくなるが、精度が悪くなってしまうという。さらに実際のトラヒックのレートの強制切断レートからの超過分が一回の切断量よりも少ない場合には必ず過剰切断してしまう。すなわち、従来技術では、例えば一定割合でフローの強制切断を行っていき、最終的に単一ボトルネックになったとしても一定割合ででしか切断できないが、本実施形態によれば適切な量の切断が可能である。また本実施形態によれば、単一ボトルネックであれば適切な切断量がわかるため、一度に切断する量を従来技術よりも大きめに設定することが可能である。
【００６３】
なお、本発明における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより通信制御を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６４】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００６５】
１  パケット転送システム
１００−１  発信者端末
１００−２  着信者端末
２００  中継パケット転送装置
２１０  入り回線対応部
２２０  スイッチ部
２３０  出回線対応部
２３１  トークンバケツ処理部
２３２  マーキング実施部
２３３  待ちキュー部
２３４  物理回線対応部
３００  境界パケット転送装置
３１０  入り回線対応部
３２０  流入規制部
３３０  マーキング集計部
３４０  パケット生成部
３５０  スイッチ部
３６０  出回線対応部
【図１】
2011135443.tif 000003
【図２】
2011135443.tif 000004
【図３】
2011135443.tif 000005
【図４】
2011135443.tif 000006
【図５】
2011135443.tif 000007
【図６】
2011135443.tif 000008
【図７】
2011135443.tif 000009
【図８】
2011135443.tif 000010
【図９】
2011135443.tif 000011
【図１０】
2011135443.tif 000012
【図１１】
2011135443.tif 000013
【図１２】
2011135443.tif 000014
【図１３】
2011135443.tif 000015
【図１４】
2011135443.tif 000016
【図１５】
2011135443.tif 000017
【図１６】
2011135443.tif 000018
【図１７】
2011135443.tif 000019