(57)【特許請求の範囲】
【請求項１】
一意に識別するためのアドレスが割り当てられた通信用インターフェイスを有し、該通信用インターフェイスを介してパケットの送信及び受信を行うユーザ通信機器と、一意に識別するためのアドレスが割り当てられた通信用インターフェイスを少なくとも１つ有し、該通信用インターフェイスを介してパケットの転送を行うとともにパケットを転送するための経路計算を行うルータとが接続された通信ネットワークであって、複数の部分ネットワークに分割され、該部分ネットワークは部分ネットワーク識別子及びその中で使用する部分アドレス集合を有し、他の部分ネットワークに対する経路計算は部分アドレス集合単位に行われ、各部分ネットワーク内のルータは部分ネットワーク内に属するより小規模のサブネットワーク間を接続するためのバックボーン・ネットワークとそれ以外のネットワークとに分けられ、あるルータから宛先に対する経路が少なくとも１つ存在する通信ネットワークにおいて、
ユーザ通信機器間の通信品質を保証するための通信資源の予約を前記部分ネットワーク内と部分ネットワーク間とに分けて行い、部分ネットワーク内のルータのうち、他の部分ネットワークと接続されている境界ルータが部分ネットワーク間の資源予約を行い、部分ネットワーク内の資源予約は前記部分ネットワーク内のルータが行い、
前記部分ネットワーク間の資源予約については、各部分ネットワーク内のユーザ通信機器が送受信する通信及び隣接する部分ネットワーク間を転送する通信を同一の部分ネットワークを宛先とする通信毎にまとめて行い、
バックボーン・ネットワーク内のルータ間の通信に関しては、各バックボーン・ネットワーク内のルータがパケットが到来する到来インターフェイス及びパケットを送出する送出インターフェイスの組み合わせ単位に待ち行列を設けてパケットを管理し、前記待ち行列に前記資源予約により取得した資源量に基づいて転送用資源を割り当て、到来してくるパケットが割り当てられた転送用資源以内であることを監視し、
前記資源を超過した場合にはパケットを廃棄し、割り当てられた転送用資源内で送出インターフェイスを用いてパケットを送出し、
各部分ネットワーク内のユーザ通信機器が送出し、前記ユーザ通信機器が属する部分ネットワーク以外の部分ネットワークに属するユーザ通信機器に到着するパケットに関しては、転送されていく経路の中で最初の前記ユーザ通信機器が属する部分ネットワークのバックボーン・ネットワーク内のルータがパケットを前記パケットの属するセッション毎に管理し、前記資源予約時に割り当てられたセッションの資源量以内であることを監視し、
前記資源を超過した場合にはパケットを廃棄し、割り当てられた転送用資源内であれば、前記バックボーン・ネットワーク内のルータが前記到来インターフェイスと送出インターフェイス単位にパケットを管理することによってパケットを送出する
ことを特徴とする通信品質保証方法。
【請求項２】
前記各部分ネットワークが行う資源予約は送信側から受信側への方向または受信側から送信側への方向に行い、
送信側から受信側に向かって行う時には宛先となる部分ネットワーク及び予約資源量を含むメッセージを、受信側から送信側に向かって行う時には送信元となる部分ネットワーク、宛先となる部分ネットワーク及び予約資源量を含むメッセージをパケットが転送される経路に沿って送信し、
各ルータは前記部分ネットワークへの経路が分岐する時は前記メッセージに指定された資源量を各経路に分割して複数のメッセージとして送信し、また、宛先あるいは送信元となる部分ネットワークが同一であるメッセージを全てのメッセージの要求を満たすことのできる資源量に変更し、１つの資源予約要求メッセージにまとめて伝搬させることで資源予約を行う
ことを特徴とする請求項１記載の通信品質保証方法。
【請求項３】
あるルータがある宛先となる部分ネットワークに対する経路を変更する場合、実際に変更を行う前に変更前の経路及び変更後の経路に、
送信側から受信側に向かって資源予約を行う時には変更量、宛先となる部分ネットワーク、宛先となる部分ネットワークへの経路の分岐した分岐度及び分岐した経路が合流した合流度を含む予約資源変更要求メッセージを、受信側から送信側に向かって資源予約を行う時には変更量、宛先となる部分ネットワーク、送信元の部分ネットワーク、前記分岐度及び合流度を含む予約資源変更要求メッセージを送信し、
各ルータは前記部分ネットワークへの経路が分岐する時は前記予約資源変更要求メッセージに含まれる資源量を分割して複数のメッセージとして送信し、
全てのメッセージを受信したルータまたは宛先となる部分ネットワークの境界ルータが協調して全てのメッセージを受信したことを確認して、前記予約資源変更要求メッセージが送信されてきた方向と逆向きに変更要求配送の完了を通知し、
前記通知を受けた変更後の経路のルータは資源を変更し、前記経路を変更するルータは前記通知を受けた後に経路を変更する
ことを特徴とする請求項２記載の通信品質保証方法。
【請求項４】
到来インターフェイスと送出インターフェイス単位にパケットを管理することによってパケット送出を行う方法として、
通信回線を流れる一連のパケット列の各パケットに直前のパケットとの間の時間間隔であるパケット間隔を持たせ、
前記一連のパケット列がルータの到来インターフェイスから各パケットの宛先に応じた送出インターフェイスに分岐して前記パケット列とは異なる送出インターフェイス毎のパケット列になる際に、前記パケット間隔を前記送出インターフェイス毎のパケット列のパケット間隔に変更し、
送出インターフェイスからパケットを送信する際には、到来インターフェイス毎のキューにパケットを格納し、
各キューからパケットを取り出して送信するべき時刻である到来インターフェイス毎適格時刻と、送出インターフェイスから最後にパケットを送信した時刻である送出インターフェイス毎最終送信時刻とを管理し、
パケット内に格納されているパケット間隔及び到来インターフェイス毎適格時刻の和を新たな到来インターフェイス毎適格時刻とし、
前記到来インターフェイス毎適格時刻が現在の時刻と等しいか過去であるキューのうち最小の前記到来インターフェイス毎適格時刻を有するキューを選択し、該選択したキューに格納されたパケットをキューから取り出し、
取り出したパケット内のパケット間隔を前記到来インターフェイス毎適格時刻と送出インターフェイス毎最終送信時刻との差に再設定するとともに、到来インターフェイス毎適格時刻を送出インターフェイス毎最終送信時刻に設定する
ことを特徴とする請求項１記載の通信品質保証方法。
【請求項５】
到来インターフェイス毎適格時刻の計算方法として、
到来インターフェイス毎適格時刻、各キューが使用できる帯域及び最終送信パケットのサイズから計算される帯域に適合した次のパケットを送信するべき時刻と、パケット内に格納されているパケット間隔及び到来インターフェイス毎適格時刻の和とのうち小さい方を到来インターフェイス毎適格時刻とする
ことを特徴とする請求項４記載の通信品質保証方法。
【請求項６】
到来インターフェイス毎適格時刻及び送出インターフェイス毎最終送信時刻の設定方法として、
到来インターフェイス毎のキューから最後にパケットを送信した時刻である到来インターフェイス毎最終送信時刻を管理し、
到来インターフェイス毎適格時刻については、到来インターフェイス毎最終送信時刻、各キューが使用できる帯域及び最終送信パケットのサイズから計算される帯域に適合した次のパケットを送信するべき時刻と、パケット内に格納されているパケット間隔及び到来インターフェイス毎最終送信時刻の和とのうち小さい方を前記到来インターフェイス毎適格時刻とし、
送出インターフェイス毎最終送信時刻として実際にパケットを送出した時刻を用い、送出する際にパケットに再設定するパケット間隔として該送出インターフェイス毎最終送信時刻とパケット送信を開始する時刻との差を用い、
前記パケット送信を開始する時刻を前記送出インターフェイス毎最終送信時刻及び到来インターフェイス毎最終送信時刻に設定する
ことを特徴とする請求項５記載の通信品質保証方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信ネットワークにおける、通信品質の保証方法に関するものである。
【０００２】
【従来の技術】
近年のインターネットに代表される通信ネットワークの発展に伴い、メール、ファイル転送、ワールドワイドウェブ、ライブ中継等の様々なアプリケーションが利用されるようになってきている。今後のユーザ層のさらなる拡大によって、より高品質な動画・音声アプリケーションや企業活動に密接に関係したアプリケーション、また、医療やプラント制御等、より確実性の要求されるアプリケーションへと通信ネットワークの利用が拡大してくると予想される。
【０００３】
このようなアプリケーションの中には、ネットワークによって提供される通信品質に対して敏感なものが存在し、帯域幅、絶対的な通信遅延時間、遅延時間の変動によって、アプリケーションがユーザに提供する動画・音声の品質が劣化する、企業が契約上提供することを約束したサービスを提供できなくなる、あるいは遠隔医療の分野では緊急時により確実な診断が行えない等の問題が発生する。
【０００４】
本発明は、このような通信ネットワークを用いるアプリケーションのうち、より通信品質に敏感で予測可能な品質を必要とするようなアプリケーションを用いるための、通信品質の保証方法に関するものである。
【０００５】
従来のこの種の技術としては、
・IntServ（S.Shenker et al.,"Integrated services in the Internet arechitecture: an overvier",IETF RFC 1663）
・DiffServ（Y.Bernet et al.,"A framework for differentiated services",IETF Internet draft, draft-ietf-diffserv-framework-02.txt）
・SCORE（I.Stoica et al.,"Providing Guaranteed Services Without Per Flow Management",Proceedings of 1999 ACM SIGCOMM Conference, pp.81-94）
がある。
【０００６】
IntServは、各アプリケーションが用いるフロー毎にネットワーク資源の予約を行うことを特徴としている。通常、各フローはインターネットで用いられるプロトコルの場合、送信アドレス、受信アドレス、送信ポート、受信ポートで識別される。
【０００７】
この予約を行うプロトコルの１つであるＲＳＶＰ（Resource Reservation Protocol: R.Braden et al.,"Resource Reservation Protocol", RFC 2205, 1997）では、送信側から受信側に対してパス・メッセージと呼ばれるメッセージを送信して資源予約を行うべき場所を各ルータが経路状態として管理し、受信側から送信側に向かって資源予約要求を行っていく。資源予約の行われたルータではセッション毎にパケットを識別し、個々のフローのために用意された待ち行列を用いることによって予約された資源の通信品質を保証する。
【０００８】
DiffServでは、パケットが比較的少数のクラスに分割され、そのパケットの扱い方に差をつけることを特徴とする。この扱い方のポリシーはそのネットワークの管理者によって異なり、ネットワーク中にポリシーを同一にするドメインが存在する。あるドメインにパケットが入ってくると、そのドメインの境界部分のルータがパケットに付けられたクラスをもとにポリシング、クラスの変更、優先度制御等を行う。
【０００９】
SCOREでは、ネットワークのSCOREと呼ばれるドメイン内とそれ以外の場所が存在する。SCOREの外ではIntServと同様に、パケットはセッションによって区別される。また、SCORE内はＭＰＬＳ（Multi protocol Label Switching: R.Callon et al.,"A framework for multiprotocol label switching",Internet draft, draft-ietf-mpls-framework-02.txt, 1997）等を用いてパケットが転送され、SCORE外では各セッション用に予約された資源を用いてパケットが転送される。
【００１０】
【発明が解決しようとする課題】
本発明が解決しようとする課題は、
・各フローへの必要な通信品質の提供
・通信品質の保証のための待ち行列の数の削減
・経路変更時の品質劣化の防止
であり、以下、それぞれについて説明する。
【００１１】
＜各フローへの必要な品質の提供＞
前述したように、本発明は、通信ネットワークを用いるアプリケーションのうち、より通信品質に敏感で、予測可能な品質を必要とするようなアプリケーションのためのものである。しかし、DiffServでは、各クラスへの割り当て通信資源、クラス分けのポリシーが各ドメインで個別に行われることから他のトラフィックの影響を受け易い。よって、他のトラフィックの状況に依存して、あるアプリケーションが必要とする通信品質を提供できない状況が発生することになる。
【００１２】
＜通信品質保証のための待ち行列の削減＞
ルータ内で予約された通信資源を提供する機構は、パケット・スケジューラと呼ばれる待ち行列によって実現される。近年、通信回線の広帯域化に伴い、ルータのパケット転送がハードウェア化される傾向にある。よって、十分なルータのパフォーマンスを得るためには、パケット・スケジューラはハードウェアで実装される必要がある。しかし、パケット・スケジューラは多くのハードウェア量を必要とすることから、十分なパケット転送能力が要求されるネットワークにおいてはコストが膨大となり、現実的に多くのパケット・スケジューラを実装することは困難である。
【００１３】
IntServでは、スケジューラは最大、そのルータを通過するフローの数となり、特に多くのトラフィックが流れる基幹のネットワークにおいてスケジューラの数が膨大になる。SCOREでは、ＭＰＬＳのドメインを大きくすることによって、フロー毎のパケット・スケジューラを用意しなければならないネットワークを少なくできる。しかし、逆に、ＭＰＬＳのドメインが大きくなることによってラベルの数が多くなり、多くのスケジューラを用意しなければならなくなる。
【００１４】
＜経路変更時の品質劣化の防止＞
インターネットでは、ルータや回線の故障、メンテナンスのためのネットワーク機器の停止、新しいネットワークの追加等の理由で、現在使用中の経路が変更されることがある。しかし、IntServ及びSCOREでは、現在の経路が利用できる場合でさえ、経路変更が行われた後、受信側または送信側の計算機が新しい経路に対して資源予約プロセスを実行して受理されるまで、通信品質が保証・提供できなくなる。また、ＲＳＶＰにおいて、ルート・ピニングと呼ばれる方法があるが、これを用いた場合にはその経路を利用しているアプリケーションが存在する間は経路変更できなくなる。
【００１５】
以上述べたように、従来、前記３つの課題を同時に解決することは困難であった。
【００１６】
【課題を解決するための手段】
本発明では、前記課題を解決するため、
・各ルータにおいて、パケットが到来するインターフェイス（以下、到来インターフェイスと呼ぶ。）及びパケットを送出するインターフェイス（以下、送出インターフェイスと呼ぶ。）毎に通信資源を管理する、
・各ルータが各部分ネットワーク単位に予約資源量を管理する、
・ある部分ネットワークに対する経路を変更するルータは、その部分ネットワーク宛ての旧経路上に資源量減少の通知を行い、新経路上に資源量増加の通知を行い、分岐度と合流度を用いて全ての資源量減少と資源量増加メッセージが必要なルータに到着したことを確認する、
という手段を用いる。
【００１７】
本発明では、前記構成によって、その到来インターフェイスから送出インターフェイスに沿った経路を用いるフローの資源をまとめて管理する。このことによって、第１に、各ルータが実装しなければならない待ち行列の数を削減する。今、ルータにｎ個のインターフェイスが存在した場合、待ち行列の数はｎ（ｎ−１）である。第２に、ある送信側となるアプリケーションから受信側となるアプリケーションへのフローに提供される通信資源を、上記到来インターフェイスと送出インターフェイスの組み合わせの連鎖に基づいて階層的に管理する。このことによって、各アプリケーションのフローに対してネットワーク中のルータが分担して通信資源管理を行い、各フロー毎に必要な通信品質を提供する。
【００１８】
次に、前記構成によって、経路変更時にある宛先となる部分ネットワーク宛ての経路を変更するルータが、変更される経路によって影響を受ける通信資源を旧経路から新経路へ移動させることを可能とする。そして、前記構成によって、経路変更に伴う資源変更が必要なルータに変更が全て行き渡ったことを確認した後に、経路を変更することで、経路変更の前後で予約資源を同一とし、品質劣化を防止する。
【００１９】
【発明の実施の形態】
【００２０】
【実施の形態１】
＜前提＞
本実施の形態では、請求項で述べた通信ネットワークとしてインターネットを用いた実施の形態を説明する。この場合、部分ネットワークを自律システムとし、予約資源量としては予約帯域幅を用いる。
【００２１】
図１はインターネットにおける部分ネットワークである自律システム、ルータ、ユーザ通信機器（端末）の例を示す。ここでは、自律システムとしてＡＳ１，ＡＳ２，ＡＳ３及びＡＳ４が存在する。各自律システムにはルータとユーザ通信端末が接続されている。図中、○印で示したものがルータであり、□印で示したものがユーザ通信端末Ｓ１，Ｓ２，……，Ｄ１，Ｄ２，……である。各自律システム間はそれぞれのルータによって接続される。この図では、自律システムＡＳ１のユーザ通信端末Ｓ１から自律システムＡＳ３のユーザ通信端末Ｄ３への通信及び自律システムＡＳ３のユーザ通信端末Ｓ３から自律システムＡＳ１のユーザ通信端末Ｄ１への通信が示されている。
【００２２】
通常、インターネットの経路の計算は、自律システム内と自律システム間に分けられ、それぞれ別のルーティング・プロトコルによって計算される。計算された経路は、それぞれのルータにルーティング・テーブルという形で管理されている。ルーティング・テーブルは、宛先アドレス、マスク及び宛先に至る経路上の次のルータの情報を含んでいる。これらは自律システム内及び自律システム間に拘わらず、１つの宛先アドレスに対して、少なくとも１つの次のルータが存在し得る。このルーティング・テーブル上の各レコードをあるルータから次のルータへの方向性のある枝として表すと、ある宛先に対して、ＤＡＧ（Directed Acyclic Graph）であり、かつ出次数が０であるノードがただ１つだけ存在するものとなる。
【００２３】
＜概要＞
本発明を実施するために、各ルータ部分に
１．予約された資源量に基づいたパケット転送機能
２．自律システム間で必要な資源予約を行う機能
３．経路変更時に予約済み資源の変更を行う機能
という機能を導入する。
【００２４】
以下、それぞれについて説明する。
【００２５】
＜１．予約された資源量に基づいたパケット転送機能＞
本発明では、上述のように、到来インターフェイスと送出インターフェイスの組み合わせ単位に通信資源量を管理する待ち行列を導入する。図２は、ルータに導入される待ち行列とインターフェイスとの関係の一例を示している。この例では、ルータは全部で４つのインターフェイスを有する。また、各インターフェイスから他のインターフェイス向きの待ち行列を有する。
【００２６】
即ち、インターフェイス１からはインターフェイス２，３，４用の待ち行列Ｑ２，Ｑ３，Ｑ４、インターフェイス２からはインターフェイス１，３，４用の待ち行列Ｑ１，Ｑ３，Ｑ４、インターフェイス３からはインターフェイス１，２，４用の待ち行列Ｑ１，Ｑ２，Ｑ４、インターフェイス４からはインターフェイス１，２，３用の待ち行列Ｑ１，Ｑ２，Ｑ３を有する。
【００２７】
この各待ち行列部分で、Virtual Clock（L.Zhang,"A New Architcture for Packet Switched Network Protocols",マサチューセッツ工科大学博士論文、１９８９）等のパケット・スケジューラを用いてポリシング及びシェーピングを行う。
【００２８】
図３はＡＳ３に対するトラフィックが到来インターフェイスと送出インターフェイスの組み合わせによって管理されているようすを表している。ＡＳ４からのトラフィックはＲ２でＲ１⇒Ｒ３として、Ｒ３でＲ２⇒Ｒ５として、Ｒ５でＲ３⇒Ｒ６として、Ｒ６でＲ５⇒Ｒ８として、Ｒ８でＲ６⇒Ｒ９として管理される。また、ＡＳ１からのトラフィックは、Ｒ５でＲ４⇒Ｒ６として管理され、ＡＳ４からのトラフィックとマージされて管理される。
【００２９】
＜２．自律システム間で必要な資源予約を行う機能＞
自律システム間の通信に必要な資源を予約するために「資源予約メッセージ」を用い、各ルータのポリシーに基づいて宛先となる自律システムへの経路に沿って本メッセージを処理・変更しながら伝搬させて必要なルータへの資源予約を行う。また、各宛先自律システム毎に予約帯域幅を管理する。
【００３０】
以下に、ルータのポリシー、本メッセージのフォーマット、メッセージ伝搬方法及びルータの管理する資源予約状態を述べる。
【００３１】
（ポリシー）
各ルータのポリシーは、
１．最大転送帯域幅
２．隣接ルータの間の比率
という２つのパラメータを含む。
【００３２】
「最大転送帯域幅」は、ある隣接ルータからもう一方の隣接ルータに転送する帯域幅の最大値である。様々な隣接ルータが資源予約要求メッセージがきた時に許可する帯域幅の最大値を表す。
【００３３】
「隣接ルータの間の比率」は、ある宛先となる部分ネットワークに対して、複数の経路を利用する、即ち、あるルータからある宛先となる部分ネットワークに至る経路が分岐し、これを利用するよう設定されていた場合、各経路に対して予約帯域幅を割り振る比率を表す。
【００３４】
（資源予約メッセージのフォーマット）
本メッセージは、
・宛先となる自律システムのアドレス
・予約帯域幅
という情報を含む。
【００３５】
（資源予約メッセージ伝搬方法）
１．初期状態として、各ルータは、そのルータに直接接続されているユーザ通信端末が必要とする、宛先となる自律システム毎の上記資源予約メッセージを作成する。
【００３６】
２．上記ルータは上記資源を予約し、上記メッセージを各宛先に至る経路上の次のルータに送信する。
【００３７】
３．あるルータｋが隣接するルータｉから、宛先自律システムｊへの資源予約メッセージを受信し、その予約帯域幅がｒi(k)（ｊ）であったとする。また、あるルータｋにおける宛先自律システムｊに至る経路上の次のルータ及び前のルータの集合をそれぞれＮj(k)及びＰj(k)とし、ルータｋにおける隣接ルータｉのための隣接ルータ間の比率をｔi(k)とすると、ルータｉが宛先自律システムｊに対して次のルータｌに送る資源予約メッセージの予約帯域幅は、
【００３８】
【数１】
0003686345.tif 000002
【００３９】
とする。
【００４０】
４．ルータｉにおいて、隣接ルータｋからのパケットを受け取るインターフェイスを到来インターフェイスとして、隣接ルータｊへフォワードされるパケットを送出するインターフェイスを送出インターフェイスとするトラフィックのための待ち行列の予約帯域幅を
【００４１】
【数２】
0003686345.tif 000003
【００４２】
によって計算する（但し、ｌは宛先自律システムを表している。）。
【００４３】
図４に前記資源予約時の処理の流れ図を示す。
【００４４】
（ルータの管理する資源予約状態）
ルータの管理する資源予約状態を図５に示す。この図に示したように、資源予約状態を表すテーブルは自律システム及び帯域幅を含む。
【００４５】
＜３．経路変更時に予約済み資源の変更を行う機能＞
あるルータがある宛先自律システム宛ての経路を変更する時には、経路を変更するルータが変更前の次のルータと変更後の次のルータに対して「予約資源変更要求メッセージ」を送信し、宛先自律システムに向かう経路に沿って伝搬させること、「予約資源変更要求メッセージ」の伝搬が終了したことを判定し、終了したことを「予約資源変更要求メッセージ」を受け取った他のルータに通知する。
【００４６】
以下に、本メッセージのフォーマット及び予約資源変更要求メッセージの伝搬方法を述べる。
【００４７】
（予約資源変更要求メッセージのフォーマット）
本メッセージは、
・宛先となる自律システムのアドレス
・予約変更帯域幅
・分岐度
・合流度
という情報を含む。
【００４８】
（予約資源変更要求メッセージ伝搬方法）
１．初期状態として、ある宛先自律システムｄへの経路を変更するルータは、ｄへの予約帯域Ｒについて、旧経路にＲの減少要求、新経路にＲの増加要求を送る。この時、分岐度及び合流度は共に１である。
【００４９】
２．ルータが予約資源変更要求メッセージを受け取ると、そのメッセージに含まれる宛先自律システムへの経路変更をロックする。
【００５０】
３．各ルータは、予約資源変更要求メッセージを受け取ると、その予約変更帯域幅を資源予約メッセージの予約帯域幅の処理方法と同じ方法で変更し、次のルータへのメッセージを作成する。
【００５１】
４．この時、分岐度及び合流度の処理は次のようにする。今、予約資源変更要求メッセージｉ（１≦ｉ≦Ｎ）の分岐度及び合流度をそれぞれＦi及びＪiとする。この時、Ｎ個のメッセージをマージして送る場合は新しいメッセージｎの分岐度及び合流度はそれぞれ、
【００５２】
【数３】
0003686345.tif 000004
【００５３】
及び
【００５４】
【数４】
0003686345.tif 000005
【００５５】
とする。また、あるメッセージｉがＭ個の複数の経路に分岐する時には、合流度は変更なし、分岐度はＭ・Ｆiとする。
【００５６】
５．受け取ったメッセージｉの分岐度をＦiとし、合流度をＪiとすると、
【００５７】
【数５】
0003686345.tif 000006
【００５８】
ならば、全ての予約資源変更要求メッセージを受信したと判断する。
【００５９】
６．新経路及び旧経路について予約資源変更要求メッセージの受信完了を判断したルータは、予約資源変更要求メッセージを送ってきたルータに対して資源予約変更要求配送完了メッセージを送る。
【００６０】
７．予約資源変更要求配送完了メッセージを受け取ったルータは、同様に予約資源変更要求メッセージを送ってきたルータに対して、予約資源変更要求配送完了メッセージを送る。
【００６１】
８．経路を変更するルータは、新経路のための資源獲得を指示する。完了後、経路の変更を行う。
【００６２】
９．経路を変更後、経路を変更するルータは旧経路の資源変更を指示する。
【００６３】
図６に経路変更時の処理の流れ図を示す。
【００６４】
（予約資源変更要求メッセージ伝搬の例）
図７は予約資源変更要求メッセージの伝搬のようすを表している。この図では、ルータＲ１が、Ｒ１０が含まれる自律システムへの経路をＲ２からＲ１２に変更している。この時、Ｒ１⇒Ｒ１２、Ｒ１２⇒Ｒ１３、Ｒ１３⇒Ｒ２、Ｒ１３⇒Ｒ５、Ｒ１⇒Ｒ２、Ｒ２⇒Ｒ３、Ｒ３⇒Ｒ４、Ｒ３⇒Ｒ５、Ｒ４⇒Ｒ６、Ｒ５⇒Ｒ７、Ｒ６⇒Ｒ７の資源が変更される。ルータＲ７，Ｒ８，Ｒ９，Ｒ１０は、予約資源変更要求完了を判断でき、ルータＲ１に向かって予約資源変更要求配送完了メッセージを伝搬させていく。
【００６５】
【実施の形態２】
本実施の形態は、実施の形態１の＜１．予約された資源量に基づいたパケット転送機能＞において、一連のパケット列の各パケット間の時間間隔を調整するようになしたもので、それ以外の部分については実施の形態１と同様である。
【００６６】
本パケット転送機構は、図８に示すように、ルータの到来インターフェイス部分にパケット間隔調整部ａｄを持たせ、送出インターフェイス部分に集約フロー・スケジューラ部ｓｃを持たせることで実現する。
【００６７】
以下、本パケット転送機構で用いるパケット間隔について説明し、続いてパケット間隔調整部及び集約フロー・スケジューラ部について説明する。
【００６８】
（パケット間隔）
本パケット転送機構では、ある到来インターフェイスを通して到着する一連のパケット列について、各パケットに直前のパケットとの間の時間間隔であるパケット間隔を挿入して用いる。なお、ここで言うパケット間隔としては、各パケットの送信開始時刻の間隔を用いるものとする。
【００６９】
（パケット間隔調整部）
ルータのある到来インターフェイスに到着するパケットは、そのパケットの宛先に応じて送出インターフェイスが決められる。一般的には、一つの到来インターフェイスに到着するパケット列は、各送出インターフェイス毎のパケット列に分岐する。この時、あるパケットの直前のパケットがそのパケットとは異なる送出インターフェイスに向かって異なるパケット列になった時、パケット内に含まれているパケット間隔が直前のルータによって設定されたパケット間隔と異なった値となる。
【００７０】
これを補正するために、パケット間隔調整部は、各送出インターフェイス毎にそのインターフェイスに向かうパケットに含まれるパケット間隔の操作量を管理する表を持つものとする。この表を、以下、パケット間隔操作表と呼ぶことにする。パケット間隔操作表の各レコードは、２つの値の対応を管理する。一つ目は、送出インターフェイスの識別子であり、二つ目は、パケットに含まれるパケット間隔に加算する時間である。
【００７１】
ここで、到来インターフェイスの識別子がｊ、送出インターフェイスの識別子がｋである時、前記加算する時間をａj,kと表す。ａj,kの初期値は、全てのｊ及びｋについて０とする。
【００７２】
今、パケット間隔ｇを含むパケットが、識別子ｊを有する到来インターフェイスに到着し、そのパケットの送出インターフェイスの識別子がｋである時、パケット間隔操作表及びパケットに含まれるパケット間隔ｇを
【００７３】
【数６】
0003686345.tif 000007
【００７４】
のように操作する。
【００７５】
（集約フロー・スケジューラ部）
集約フロー・スケジューラ部は、各到来インターフェイスから送られてくるパケットを区別して格納するためのキュー（図示せず）を有し、各キューからパケットを取り出して送信するべき時刻（以下、到来インターフェイス毎適格時刻と呼ぶ）、到来インターフェイス毎のキューから最後にパケットを送信した時刻（以下、到来インターフェイス毎最終送信時刻と呼ぶ）、送出インターフェイスから最後にパケットを送信した時刻（以下、送出インターフェイス毎最終送信時刻と呼ぶ）、到来インターフェイスと送出インターフェイスの組み合わせ毎に利用できる帯域を管理する。
【００７６】
今、識別子ｊの到来インターフェイスから識別子ｋの送出インターフェイスに割り当てられた通信資源である帯域をｒj,k、識別子ｋの送出インターフェイスにおける識別子ｊの到来インターフェイスのための到来インターフェイス毎適格時刻をｑj,k、識別子ｋの送出インターフェイスにおける識別子ｊの到来インターフェイスのための到来インターフェイス毎最終送信時刻をｌj,k、識別子ｋの送出インターフェイスの送出インターフェイス毎最終送信時刻をｏkとする。また、ルータｉにおいて識別子ｊの到来インターフェイスから識別子ｋの送出インターフェイスに送信されるパケットのうちｎk番目のパケットのサイズ（長さ）を
【００７７】
【数７】
0003686345.tif 000008
【００７８】
とする。
【００７９】
集約フロー・スケジューラ部では、以下に述べる３つの手法のいずれかにより、到来インターフェイス毎適格時刻ｑj,kを求めてパケットを送信するとともに、パケット内のパケット間隔の値を設定する。
【００８０】
まず、第１の手法（請求項５に対応）では、ｑj,k及びｏkの初期値については、最初のパケットが到着した時刻とする。次に、集約フロー・スケジューラ部は、パケットを送信する度または空のキューにパケットが入った時に、
【００８１】
【数８】
0003686345.tif 000009
【００８２】
をキューが空でない到来インターフェイスｊについて計算し、ｑj,kが最小となるｊを求める。
【００８３】
次に、ｑj,kが現在の時刻と等しいかまたは小さい時、パケットの送信を行う。パケットを送信する際には、パケット内のパケット間隔の値をｑj,k−ｏjに設定し、その後、ｏj＝ｑj,kとする。
【００８４】
また、第２の手法（請求項６に対応）では、ｑj,k及びｏkの初期値については、最初のパケットが到着した時刻とする。次に、集約フロー・スケジューラ部は、パケットを送信する度または空のキューにパケットが入った時に、
【００８５】
【数９】
0003686345.tif 000010
【００８６】
をキューが空でない到来インターフェイスｊについて計算し、ｑj,kが最小となるｊを求める。
【００８７】
次に、ｑj,kが現在の時刻と等しいかまたは小さい時、パケットの送信を行う。パケットを送信する際には、パケット内のパケット間隔の値をｑj,k−ｏjに設定し、その後、ｏj＝ｑj,kとする。
【００８８】
さらに、第３の手法（請求項７に対応）では、ｑj,kの初期値については、最初のパケットが到着した時刻とし、ｌj,k及びｏkは、識別子がｋの送出インターフェイスにおいて、それぞれ、到来インターフェイス毎のキューから最後に送出したパケットの送信時刻及び識別子ｋの送出インターフェイスからパケットを送出した時刻を設定するものとする。
【００８９】
次に、集約フロー・スケジューラ部は、パケットを送信する度または空のキューにパケットが入った時に、
【００９０】
【数１０】
0003686345.tif 000011
【００９１】
をキューが空きでない到来インターフェイスｊについて計算し、ｑj,kが最小となるｊを求める。
【００９２】
次に、ｑj,kが現在の時刻と等しいかまたは小さい時、パケットの送信を行う。パケットを送信する際には、ｐを現在時刻として、パケット内のパケット間隔の値をｐ−ｏjに設定し、ｏj＝ｐ及びｌj,k＝ｐとする。
【００９３】
【発明の効果】
以上説明したように、本発明によれば、
・到来インターフェイス及び送出インターフェイス毎に通信資源を管理する、
・各ルータが各部分ネットワーク単位に予約資源量を管理する、
・ある部分ネットワークに対する経路を変更するルータは、その部分ネットワーク宛ての旧経路上に資源量減少の通知を行い、新経路上に資源量増加の通知を行い、分岐度と合流度を用いて全ての資源量減少と資源量増加メッセージが必要なルータに到着したことを確認する、
ことによって、前述した
・各フローへの必要な通信品質の提供、
・通信品質の保証のための待ち行列の数の削減、
・経路変更時の品質劣化の防止
という課題を解決できる。
【図面の簡単な説明】
【図１】インターネットにおけるパケットの配送のようすを示す図
【図２】本発明におけるルータの構造を示す図
【図３】本発明におけるトラフィック管理の一例を示す図
【図４】資源予約時の処理の流れ図
【図５】ルータの管理する資源予約状態の一例を示す図
【図６】経路変更時の処理の流れ図
【図７】予約資源変更要求メッセージの伝搬のようすの一例を示す図
【図８】実施の形態２に対応するルータの構造を示す図
【符号の説明】
Ｓ１，Ｓ２，……，Ｄ１，Ｄ２，……：ユーザ通信端末、Ｒ１，Ｒ２，……：ルータ、ＡＳ１〜ＡＳ４：自律システム、Ｑ１〜Ｑ４：待ち行列、ａｄ：パケット間隔調整部、ｓｃ：集約フロー・スケジューラ部。
【図１】
0003686345.tif 000012
【図２】
0003686345.tif 000013
【図３】
0003686345.tif 000014
【図４】
0003686345.tif 000015
【図５】
0003686345.tif 000016
【図６】
0003686345.tif 000017
【図７】
0003686345.tif 000018
【図８】
0003686345.tif 000019