(57)【要約】      （修正有）【課題】入来データキューに格納したデータパケットを公平に処理する方法を提供する。【解決手段】各ルーター２０は、受信したデータパケットを１以上の入来データキュー４８に格納する。入来データキュー４８に格納されるパケットは、動的に調整されるパケットフローレートにおいてルーター２０によって処理される。入来データキュー４８は、データキューヘッド構造を有し、そこには、処理すべきパケットのフィールドが含まれる。処理すべきパケットフィールドは、所定の処理インターバルにおいて、入来データキュー４８からの処理されるべきパケット数を示す値を有する。この手法において、入来データキュー４８のパケットフローレートは、ルーター２０の現在の動作状態（現在のプロセッサ４４及びメモリ４６の稼働率）に応じて、処理すべきパケットフィールドの値を変化することにより調整される。【選択図】図２
2011130457.tif 000002
【特許請求の範囲】
【請求項１】
ルーターにおけるデータパケットの処理を制御する方法であって、前記ルーターは受信したデータパケットを入来データキューに格納し、前記入来データキューに格納されているパケットが、前記ルーターによって選択されたパケットフローレートにおいて処理される場合に、前記方法は、
前記パケットフローレートを、前記ルーターにおける現在の動作状態に基づいて調整する工程を備えることを特徴とする方法。
【請求項２】
前記入来データキューが、所定の処理インターバルにおいて前記ルータによって処理されるべき前記入来データキューに保持されたパケット数を示す値を有する処理すべきパケットフィールドを含む、データキューヘッド構造を有し、
前記パケットフローレートが、前記処理すべきパケットフィールドの値を増加又は減少することにより調整されることを特徴とする請求項１に記載の方法。
【請求項３】
前記データキューヘッド構造はさらに、持続的データレートフィールドと、バーストデータレートフィールドとを含み、
もし、前記入来データキューにおいてデータバーストが検出されなければ、前記処理すべきパケットフィールドの値が、前記持続的データレートフィールドの値に基づき、
もし、前記入来データキューにおいてデータバーストが検出されれば、前記処理すべきパケットフィールドの値が、所定期間において前記バーストデータレートフィールドの値に基づくことを特徴とする請求項２に記載の方法。
【請求項４】
前記データキューヘッド構造がさらに、処理すべきパケットフィールドの値を、バーストデータレートフィールドの値に依存させるための選択された期間を示す値を格納するバースト期間フィールドを含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記バーストデータレートフィールド及び前記バースト期間フィールドの一方もしくは両方の値が、前記ルーターの現在の動作状態に基づいて調整されることを特徴とする請求項４に記載の方法。
【請求項６】
前記入来データキューにおいてデータバーストが受信されているかどうかを検出する工程と、
受信したデータバーストの検出に応じて、前記パケットフローレートを一時的に増加する工程と
を更に備えることを特徴とする請求項１に記載の方法。
【請求項７】
前記入来データキューが、持続的データレートフィールドを含むデータキューヘッド構造を有し、データのバーストが受信されたかどうかの判定が、
持続的データレートフィールドの値を選択された非バーストパケットフローレートに設定する工程と、
前記入来データキューの現在のパケットフローレートを計算する工程と、
前記計算したパケットフローレートと前記持続的データレートフィールドの値とを比較する工程と
によって実行されることを特徴とする請求項６に記載の方法。
【請求項８】
データキューヘッド構造が更に、タイムスタンプフィールドと、処理バイトフィールドを含み、前記前記入来データキューの現在のパケットフローレートが、
前記タイムスタンプフィールドの値を、現在のパケットフローレートの計算が最後に行われた時間に設定し、
パケットフローレートの最後の計算以降に処理されたデータのバイト数を反映するように前記処理バイトフィールドの値を設定し、
前記タイムスタンプフィールドと前記処理バイトフィールドの値のそれぞれに基づいて、前記入来データキューのパケットフローレートを計算する
ことにより計算されることを特徴とする請求項７に記載の方法。
【請求項９】
前記ルーターがメモリを備え、前記入来データキューが、受信したデータパケットを格納するために前記メモリのうち所定量を割り当てられており、
前記メモリの現在の稼働率に基づいて、前記入来データキューにデータパケットを格納するために割り当てられるメモリの量を調整する工程をさらに備えることを特徴とする請求項１に記載の方法。
【請求項１０】
前記ルーターが共同して共通制御機能を実行する１以上のプロセッサを有し、前記１以上のプロセッサがプロセッサ稼働率を有し、前記入来データキューの前記パケットフローレートは、現在の前記プロセッサ稼働率に応じて調整されることを特徴とする請求項１に記載の方法。
【請求項１１】
前記ルーターはメモリを有し、前記入来データキューの前記パケットフローレートは、メモリの現在の稼働率に応じて調整されることを特徴とする請求項１に記載の方法。
【請求項１２】
複数の仮想ルーターインスタンスを有し、前記各仮想ルーターインスタンスが受信データを１以上のキューに格納するルーターにおけるデータの処理を制御する方法であって、いずれかのキューに格納されているパケットは、前記ルーターによって前記各キューと関連するデータ処理レートにおいて処理される場合に、前記方法は、
第１の仮想ルーターインスタンスに関連する１以上のキューの前記データ処理レートを、前記ルーターにおける現在の動作状態に基づいて調整する工程を備えることを特徴とする方法。
【請求項１３】
第２の仮想ルーターインスタンスに関連する１以上のキューの前記データ処理レートを、前記ルーターにおける現在の動作状態に基づいて調整する工程を更に備えることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記第１の仮想ルーターインスタンスに関連する前記１以上のキューのデータ処理レートが、前記第２の仮想ルーターインスタンスに関連する前記１以上のキューのデータ処理レートとは独立して調整されることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記ルーターの同一の現動作状態に応じて、前記第１の仮想ルーターインスタンスと関連する前記１以上のキューのデータ処理レートは減少され、第２の仮想ルーターインスタンスと関連する前記１以上のキューのデータ処理レートは増加されることを特徴とする請求項１３に記載の方法。
【請求項１６】
メモリと複数の仮想ルーターインスタンスを有し、前記各仮想ルーターインスタンスは受信データパケットを１以上の各入来データキューに格納するパケットデータルーターにおいて、メモリの稼働率を制御する方法であって、いずれかの入来データキューに格納されているパケットは、前記ルーターによって前記１以上の各入来データキューと関連するパケットフローレートにおいて処理される場合に、前記方法は、
第１の仮想ルーターインスタンスに関連する１以上の入来データキューの前記パケットフローレートを、前記ルーターにおける現在の動作状態に基づいて周期的に調整する工程を備えることを特徴とする方法。
【請求項１７】
第２の仮想ルーターインスタンスに関連する１以上の入来データキューの前記パケットフローレートを、前記ルーターにおける現在の動作状態に基づいて周期的に調整する工程を更に備えることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記第１の仮想ルーターインスタンスに関連する前記１以上の入来データキューのパケットフローレートが、前記第２の仮想ルーターインスタンスに関連する前記１以上の入来データキューのパケットフローレートとは独立して調整されることを特徴とする請求項１７に記載の方法。
【請求項１９】
複数のルーターと複数の仮想ルーターインスタンスを備えるシステムにおけるデータの処理を制御する方法であって、少なくとも第１の仮想ルーターインスタンスが第１のルーター及び第２のルーターの両方に現れ、各仮想ルーターインスタンスは、受信データを、前記仮想ルーターインスタンスが現れる各ルータ内の１以上の各データキューに格納し、どのデータキューに格納されるデータも、前記各ルーターによって前記各データキューに関連するデータ処理レートにおいて処理される場合に、前記方法は、
前記第１のルーターの現在の動作状態に基づいて、前記第１及び第２のルーターのそれぞれにおける前記第１の仮想ルーターインスタンスに関連する１以上のデータキューのデータ処理レートを調整する工程を備えることを特徴とする方法。
【請求項２０】
前記第１のルーター上に位置する前記各１以上のデータキューの前記データ処理レートは、前記第２のルーター上に位置する前記各１以上のデータキューの前記データ処理レートとは独立して調整されることを特徴とする請求項１９に記載の方法。
【請求項２１】
前記第１及び第２のルーターの両方に現れる第２の仮想ルーターインスタンスが更に、
前記第１のルーターの現在の動作状態に基づいて、前記第１及び第２のルーターのそれぞれにおける前記第２の仮想ルーターインスタンスに関連する１以上のデータキューのデータ処理レートを調整する工程を備えることを特徴とする請求項１９に記載の方法。
【請求項２２】
前記第１仮想ルーターインスタンスに関連する前記データキューの前記データ処理レートは、前記第２仮想ルーターインスタンスに関連する前記データキューの前記データ処理レートとは独立して調整されることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記第１のルーターの現在の動作状態に応じて、
前記第１のルーター上に位置する前記第１の仮想ルーターインスタンスに関連する前記１以上のデータキューのデータ処理レートが減少され、
前記第２のルーター上に位置する前記第１の仮想ルーターインスタンスに関連する前記１以上のデータキューのデータ処理レートが増加され、
前記第１のルーター上に位置する前記第２の仮想ルーターインスタンスに関連する前記１以上のデータキューのデータ処理レートが増加され、
前記第２のルーター上に位置する前記第２の仮想ルーターインスタンスに関連する前記１以上のデータキューのデータ処理レートが減少されることを特徴とする請求項２１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にパケットデータネットワークの分野に属し、より詳細には、１以上のパケットデータルーターにおいてデータパケットのフローを規制し管理するためのシステムアーキテクチャ及び方法に関連する。
【背景技術】
【０００２】
典型的なパケットデータルーターにおいて、様々なソースロケーションから発生したパケットは、複数の通信インタフェースを介して受信される。各パケットは、目的地アドレス（destination address）のような、例えばルーティングテーブル又はパケット転送プロトコルによってルータのそれぞれの通信インタフェースと関連づけられているルーティング情報を含む。ルーターは、各受信パケットのルーティング情報をリードし、もし当該情報を認識すると、目的地へのさらなる送信のために、当該パケットを適切な通信インタフェースへ転送する。既知の目的地アドレスや転送プロトコル情報を有しないパケットは、典型的にはドロップされる。
【０００３】
パケットデータトラヒックパターン或いはボリュームの増減により、パケットデータルーターは、新たに受信したパケットのそれぞれを指定の通信インタフェースへ直ちにルーティングできないかもしれない。特に、パケットデータトラヒックは、小休止を伴うハイアクティビティのバーストを有する傾向にある。このようにパケットデータルーターは、持続的データレート(sustained data rate)とバーストデータレートを有するものとして特徴づけても良い。バーストしたパケットトラヒックを受信すると、ルーターは、パケットをそれぞれの通信インタフェースへ処理及び転送するための処理能力を有するようになるまで、一時的に受信したパケットを関連するメモリーに格納する。ルーターの持続的又はバーストのデータレートが所定の時間を超える場合、さらなる入来パケットがドロップされるのは避けられなくなる。もちろん、時には回避しがたい一方で、ソースはリカバリー処理の一部としてドロップされたパケットを再送信するであろうから、パケットルーターの過密状態を延長することになるとともに、未処理パケットをさらにドロップする原因ともなるので、未処理パケットのドロップは好ましくない。
【０００４】
パケットデータネットワークユーザーが、サービスプロバイダーからの単一ルーター又はルーターシステムのいずれかをシェアすることはしばしばある。複数の異なるインターネットユーザーは、例えば、それぞれのデータモデムもしくは一時群速度インタフェース（ＰＲＩ）を介して、インターネットサービスプロバイダー（ＩＳＰ）によってオペレーションされている単一のインターネットプロトコル（ＩＰ）ルーター又は、ＩＰルーターシステムに接続する。これらのエンドユーザー自身は、単一顧客（single customers）であってもよいし、又は、ＩＳＰによって単一顧客アカウントに結合された複数の（ネットワークでつながった）ユーザーであってもよい。それぞれの顧客アカウントは、ＩＳＰによって、契約したサービス接続性のタイプ及びレベルに応じて、サービスプライオリティ及びパケットスループット帯域幅の各レベルに配置されてもよい。
【０００５】
説明の目的のためにここで引用する“ルーター”とは、共同して単一制御機能を実行する１以上のプロセッサの制御下にある所定数の物理的通信インタフェース（例えば、モデム）を有する、（論理的と反対の意味における）物理的存在として定義される。典型的に、単一物理的ルーターは、単一ルーティングドメイン下において動作する。即ち、ここでは、どんな通信インタフェースにおいて受信されたパケットも、ルーターの同一又は他のどの通信インタフェースにだけ転送されても良い。ここで引用する“ルーターシステム”は、選択的に共通（入来）パケットデータトラヒックをシステム内の各ルーターに方向付ける外部コントローラーを備える、２以上の独立したルーターとして定義される。
【０００６】
単一ルータ内に、１以上の仮想的ルーターインスタンス（ＶＲＩ）を実装することが知られている。各ＶＲＩは、独自の通信インタフェースのサブセットもしくは、共有通信インタフェース上の論理回路と、独自のルーティングドメインを備えるが、依然として、ルータによって扱われるパケットトラヒックと共に共通制御機能の制御下に置かれている。特にＶＲＩは、ＴＣＰ／ＩＰプロトコルモデルのレイヤーにほぼ相当する、ルーターによって実行される処理の集合として存在する。例えば、プライベートネットワークは、パケットデータが同一ネットワーク内のエンドユーザー間においてのみ交換されてもよいように、ＶＲＩとして構築することができる。単一ＶＲＩを、ルーターシステムにおける複数ルーターの橋渡しさせることが提案されたりもした。例えば、実装に関するある提案は、専用インタフェースリンクに、共通ＶＲＩを有する複数ルーターの各通信インタフェースの橋渡しをさせることである。
【０００７】
他の経済要素と同様に、成長率（growth rate）は可変かつ、時に予測不可能であるから、パケットルーター又はパケットルーターシステムは、サービスしようとする全てのユーザー又はＶＲＩに、契約した帯域幅割当てを同時に提供するために必要な処理及びメモリ容量を必ずしも有しないだろう。さらに、様々なユーザーは、ＩＰルーターに異なる時間帯、或いはしばしば予測不可能な時間帯に、様々なレート及び帯域幅を必要として接続するであろう。
【０００８】
ＩＰルーターは、典型的に、リアルタイムオペレーティングシステム（ＲＴＯＳ）で制御されている。これは、異なるプライオリティの複数の処理が、（例えば、単一中央処理ユニットにおける）共通制御機能の制御下において共存することを可能とする。例えば、ＲＴＯＳは、所定のユーザーに対する現在の稼働特性（usage characteristics）に関するフィードバック情報を与えるセンサーを有しても良い。これは、要求の変化に応じてＲＴＯＳ動作パラメータを調整するために利用される。ＲＴＯＳのための共通アプリケーションは、処理制御、動作制御及び所定のアプリケーションにおけるコマンド及び制御である。
【０００９】
問題は、これらのオペレーティングシステムが、ＩＳＰのエンドユーザー顧客によって契約された異なるプライオリティ及び帯域幅の要求に効果的に順応できない場合が時々あることである。動作制御システムでは、例えば、センサーからの情報の流れはシステムにもたらされ、制御信号の流れはシステムの外にもたらされる。多くのセンサーが有っても良いし、制御されているサブシステムが多くあっても良い。しかし、入力情報は、システムを通過して巡回して出力となることはない。これは、システムを制御するためには非効率な、ＲＴＯＳ処理／タスクのプライオリティの特徴を特有に制御する効果がある。
【００１０】
特に、典型的なＩＰルーターは、“パケット駆動”システムである。より多くのデータパケットを受信すると負荷が大きくなり、当該負荷が（全ての実践的な目的について）入力が出力になるように全体のシステムを妨害する。このように、最も多くのパケットを扱っているルーターへ接続しているユーザーは、システムリソースを独占しがちである。
【００１１】
例えば、２つの異なるＶＲＩに分割されるルータを考えてみる。ここで、各ＶＲＩは、ほぼ同数のエンドユーザーを有し、同一のプライオリティ及び帯域幅要求を含む同一のサービス品質（ＱＯＳ）についてＩＳＰにペイしているものとする。よって、ルーターは、各ＶＲＩのエンドユーザーに毎秒のビット数（ＢＰＳ）が同一のシステムスループットを提供できるべきである。しかしながら、ここではルーターは、１つのＶＲＩのピーク負荷を、未処理パケットをドロップすることなく扱うのに充分な処理能力を有しているのがやっとだと仮定する。この場合、もし、第１のＶＲＩのユーザーが、事実上、ルータースループット処理能力とタイアップするならば、第２のＶＲＩのユーザーは、本来与えられるはずのサービスプライオリティ及び帯域幅を受け入れないであろう。
【００１２】
このように、パケットデータルーター又はルータシステムを通じたデータパケットの処理を、より公平に調整するための方法及びシステム構成が必要とされている。ここでは、サービス品質は、各ユーザー及び／又はＶＲＩについてバランスされ、高い負荷が発生した場合でも、システムは安定に保たれる。
【発明の概要】
【００１３】
本発明の第１の側面によれば、ルーターの現在の動作状態に基づいて各入来データキューに保持されているパケットが処理されるレートを動的に調整することにより、パケットデータルータにおけるデータパケットの処理を提供する。
【００１４】
好適な実施形態においては、入来データキューは、処理すべきパケットフィールド及び持続的データレートフィールドを含むデータキューヘッド構造（data queue head structure）を有する。処理すべきパケットフィールドは、所定の処理インターバルにおいてルータによって処理されるべき入来データキューに保持されたパケット数を示す値を格納する。この手法において、入来データキューのパケットフローレートは、プロセッサやメモリの稼働率のような、ルーターの現在の動作状態に基づいて、処理すべきパケットフィールドの値を増減することによって調整されてもよい。持続的データレートフィールドは、各入来データキューについてのターゲットの（例えば最大の）データ処理レートをｂｐｓにて示す。処理すべきパケットフィールドの値は、一般には入来データキューの持続的データレートフィールドに基づく。
【００１５】
本発明のさらなる側面によれば、入来データキューのパケットフローを動的に調整する方法は、データパケットのバーストが、当該キューで受信された（又は受信されている）かどうかの検出を含む。好適な実施形態においては、データキューヘッド構造は、バーストデータレートフィールドとバースト期間フィールドの両方を含む。バーストデータレートフィールドは、受信したデータパケットのバーストが検出された場合の、入来データキューに保持されるデータパケットの処理の所定のレートを示す値を格納する。データバーストが検知されると、処理すべきパケットフィールドは、持続的データレートの代わりに、バーストデータレートに基づいて再計算される。バースト期間フィールドは、バーストデータレートに基づき、入来データキューの処理レートを持続させる時間を示す値を格納する。この手法において、入来データキューのパケットフローレートは、バーストデータレートフィールド又はバースト期間フィールドの値を増減することによってさらに制御される。
【００１６】
本発明のさらなる側面によれば、入来データキューのデータキューヘッド構造にはまた、キュー深度フィールドが与えられる。これは、入来データキューに格納されるデータパケットに割り当てられるルーターメモリの現在の量を示す値を格納する。一旦この限界に到達すると、当該入来データキューに対するどんなパケットもドロップされるであろう。ルーターの現在の動作状態に依存して、キュー深度フィールドは、所定のインターバルにおいて、処理のためにルーターメモリに保持されるパケット数を制限することにより、ルーターのメモリの稼働率を調整するために増減されても良い。
【００１７】
本発明のさらなる側面によれば、ルーターの現在の動作状態に基づいて複数の各入来データキューに保持されているパケットが処理されるレートを動的に調整することにより、パケットデータルータにおけるデータパケットの処理する方法が提供される。
【００１８】
好適な実施形態においては、各入来データキューのパケットフローレートは、他の入来データキューのパケットフローとは独立に調整される。よって、入来データキューレベルの柔軟な管理及び制御が可能となる。当該方法は、好ましくは、複数の入来データキューの少なくとも一つにおいてデータのバーストが受信されたかどうかの検出を含む。例えば、第１の入来データキューのパケットフローレートが増加する一方で、同時に、第２の入来データキューのパケットフローレートが減少しても良い。これは、システム全体のスループット及びルーターの動作の安定性を脅かすことなく、第１のキューにおいて受信されたパケットのバーストの処理を調整するためのものである。
【００１９】
本発明のさらなる側面においては、複数の入来データキューのそれぞれについてのデータキューヘッド構造には、キュー深度フィールドが与えられる。これは、各入来データキューにデータパケットを格納するために割り当てられたメモリの現在の量を示す値を格納するものである。好適な実施形態では、各入来データキューのキュー深度フィールドは、所定のインターバルにおいて所定の入来データキュー上で、処理のためにルーターメモリに保持されるパケット数を制限することにより、ルーターのメモリの稼働率を調整するために別個に増減されても良い。好適な実施形態においては、メモリの稼働率は、１以上の入来データキューのパケットフローレートを調整することによっても制御される。
【００２０】
本発明のさらなる側面においては、複数の仮想ルーターインスタンス（ＶＲＩ）を諷するルーターにおいて、ルーターの現在の動作状態に応じて、１以上のＶＲＩと関連する１以上の入来データキューに保持されるパケットが処理されるそれぞれのレートを動的に調整することにより、パケットデータトラヒックを制御する方法が提供される。
【００２１】
好ましくは、各ＶＲＩと関連する入来データキューの各パケットフローレートは、別個に調整される。例えば、好適な実施形態では、第１の仮想ルーターインスタンスと関連する１以上の入来データキューのパケットフローレートは減少され、第２の仮想ルーターインスタンスと関連する１以上の入来データキューのパケットフローレートは増加される。これらは、ルーターの同一の現動作状態に応じて各々に実行される。
【００２２】
本発明のさらなる側面においては、共同して単一制御機能を実行する１以上のプロセッサとを有するルーターにおけるパケットデータトラヒックと、ルータの動作期間におけるプロセッサ稼働率との制御を、複数の仮想ルーターインスタンス（ＶＲＩ）をも有するルーターの現在の処理稼働率に応じて、１以上のＶＲＩと関連する１以上の入来データキューに保持されるパケットが処理される所定のレートを動的に調整することにより実行する方法が提供される。さらに、各ＶＲＩと関連する入来データキューの各パケットフローレートは、好ましくは別個に調整される。
【００２３】
例えば、好適な実施形態においては、第１の仮想ルーターインスタンスと関連する１以上の入来データキューのパケットフローレートは減少され、第２の仮想ルーターインスタンスと関連する１以上の入来データキューのパケットフローレートは増加される。これらは、同一の現動作状態に応じて各々に実行される。
【００２４】
本発明のさらなる側面においては、１以上のＶＲＩと関連する１以上の入来データキューのパケットフローレートは、プロセッサの稼働率、もしくは、メモリの稼働率、又は、両方を所定の動作範囲において維持するために周期的に調整される。
【００２５】
本発明のさらなる側面においては、１以上のＶＲＩと関連する１以上の入来データキューにパケットを格納するために割り当てられるメモリ量は、メモリの稼働率を所定の動作範囲に維持するために周期的に調整される。
【００２６】
本発明のさらなる側面においては、データパケットの処理を制御する方法が、複数のルーターを有し、複数の仮想ルーターインスタンス（ＶＲＩ）をサポートするように構成されるパケットデータルーターシステムについて提供される。ここで、少なくとも１のＶＲＩが複数のルーター上に現れ、各仮想ルーターインスタンスは、受信データパケットを、仮想ルーターインスタンスがある各ルータ内の１以上のキューに格納する。どのキューに格納されるデータも、各ルーターによって各キューに関連するデータ処理レートにおいて処理される。
【００２７】
好適な実施形態では、当該方法は、第１のルーターに位置する第１のＶＲＩと関連する１以上の入来データキューのデータ処理レートと、第２のルーターに位置する第１のＶＲＩと関連する１以上の入来データキューのデータ処理レートの、第１又は第２のルーターの現在の動作状態に基づいた独立の調整を含む。例えば、第１のルーターに位置する第１のＶＲＩと関連する１以上の入来データキューのデータ処理レートは減少され、その一方で、第２のルーターに位置する第１のＶＲＩと関連する１以上の入来データキューのデータ処理レートは増加される。これらは、第１のルーターの現在の動作状態に応じて実行される。
【００２８】
更に好適な実施形態では、第１及び第２のＶＲＩが第１及び第２のルーターの両方に現れ、当該方法は、当該ルーターの一方又は両方の現在の動作状態に応じた、両方のルーターに位置する第１及び第２のＶＲＩに関連する１以上のキューの各データ処理レートの調整を含む。特に、第１のＶＲＩに関連するキューのデータ処理レートは、第２のＶＲＩに関連するキューのデータ処理レートとは独立に調整される。
【００２９】
例えば、第１のルーターに位置する第１のＶＲＩと関連する１以上の入来データキューのデータ処理レートは減少され、第２のルーターに位置する第１のＶＲＩと関連する１以上の入来データキューのデータ処理レートは増加される。その一方で、同時に、第１のルーターに位置する第２のＶＲＩと関連する１以上の入来データキューのデータ処理レートは増加され、第２のルーターに位置する第２のＶＲＩと関連する１以上の入来データキューのデータ処理レートは減少される。これらは、第１又は第２ののルーターの同一の現動作状態に応じて実行される。
【００３０】
本発明の好適な実施形態は一例として示されるものであって、限定を加えるものではない。また、添付する図面においては、共通する構成要素は同一の参照番号を付してある。
【図面の簡単な説明】
【００３１】
【図１】複数のエンドユーザーのためのインターネットゲートウェイとして利用される好適なパケットデータルーターの構成を示すブロック図である。
【図２】図１のルーターのメモリに格納される入来データキューのブロック図である。
【図３】図１のルーターにおける好適なパケットフロー及びメモリ管理処理を示すブロック図である。
【図４】入来データキューにおける受信パケットデータバーストを検出し調整するための、図１における好適な方法のフローチャートである。
【図５】複数の顧客ネットワークのためのインターネットゲートウェイとして利用される好適なパケットデータルーターシステムのブロック図である。
【図６】システムの各ルーターへのアップストリームパケットの分配を示す、図５のルーターシステムのブロック図である。
【図７】図５のルーターシステムにおける好適なパケットフロー及びメモリ管理処理を示すブロック図である。
【発明を実施するための形態】
【００３２】
図１は、インターネットサービスプロバイダー（ＩＳＰ）２２によってインターネットゲートウェイとして利用される好適なパケットデータルーター２０を示す。ルーター２０は、“アップストリーム”データパケットを、複数の異なるエンドユーザー２４から受信する。各受信データパケットに含まれるルーティング情報に基づいて、ルーター２０は、（１）パケットを各インターネットサーバー３８に転送、（２）ルーター２０に接続されたエンドユーザー２４に転送、又は（３）不知の目的地アドレスを有するか又は、配信不可能であることを理由にパケットをドロップする処理のうち、いずれかを実行する。ルーター２０はまた、“ダウンストリーム”データパケットをインターネットサーバー３８から受信し、可能で有れば、受信したダウンストリームパケットを各エンドユーザー２４に転送する。
【００３３】
エンドユーザー２４は、例えば、ダイヤルアップモデム接続２８やＩＳＤＮ回線３０を介した従来の公衆交換電話網（ＰＳＴＮ）を通じてルーター２０に接続されている。各エンドユーザーネットワーク３２Ａ及び３２Ｂは、それぞれ実質的な数のエンドユーザー２４を備え、ルーター２０に、ＰＳＴＮ２６の一部として提供されるそれぞれの専用線Ｔ１回線３４Ａ及び３４Ｂを介して接続されている。ＰＳＴＮ２６からは、各通信リンクが複数の専用回線３６を介して、ＩＳＰ２２のルーター２０へ接続されている。他の通信リンクもまた利用可能であり、例えば、（不図示の）無線モデムリンクや、（不図示の）ケーブルテレビジョンネットワークにより提供される同軸ケーブルモデム接続のようなものがある。
【００３４】
図２を参照すると、ルーター２０は、共同で単一制御機能を実行するための１以上のプロセッサを含むが、図２ではこれらを単純化のためにまとめて示し、単一中央処理ユニット（ＣＰＵ）４４と呼ぶ。ルーター２０はまた、共有されるバッファメモリ４６を含む。これは、好ましくはダイナミックランダムアクセスメモリ（ＤＲＡＭ）で実装される。ルーター２０では、ＰＳＴＮ２６からの通信回線３６は、通信インタフェース４０で終端される。この通信インタフェース４０は、ソフトウェアを実装可能な複数のデジタル信号処理器（ＤＳＰ）４２を備える。ＤＳＰ４２によって処理（例えば復調）されるアップストリームパケットは、まずメモリ４６においてリンクされたリストとして形成される入来データキュー４８において保持される。
【００３５】
当業者が理解するように、入来データキュー４８は、ＦＩＦＯ形式での処理のための格納パケットを保持するソフトウェアデータ構造を有する。ルーター２０に実装される入来データキュー４８は、“深度”即ち、各キューが保持可能な各パケットの最大数の概念を有している。入来データキュー４８のメモリ４６における特定の構造は、ここで示す発明の概念から離れることなく変更されても良い。特に、図２に示す実施形態では、各エンドユーザー２４、ネットワークで接続されたエンドユーザーグループ３２Ａ／３２ＢもしくはＶＲＩ５０／５２は、ルーター２０から受信したパケットを格納するために１以上の専用入来データキュー４８を有していても良い。
【００３６】
例えば、第１のエンドユーザーグループ３２Ａから受信したデータパケット及び、グループ３２Ａから受信した単なるパケットは、第１の専用の複数の入来データキュー４８Ａに格納される。同様に、第２のエンドユーザーグループ３２Ｂから受信したデータパケット及び、グループ３２Ｂから受信した単なるパケットは、第２の専用の複数の入来データキュー４８Ｂに格納される。また、２以上のエンドユーザー２４は１以上の入来データキュー４８を、多くの可能構成において共有しても良い。
【００３７】
図２に示す実施形態では、入来データキュー４８Ａはルーター２０内に、第１のＶＲＩ５０として実装され、入来データキュー４８Ｂは第２のＶＲＩ５２として実装され、各ＶＲＩ５０及び５２は、固有のルーティングドメインを有する。特に、ＶＲＩ５０又はＶＲＩ５２のパケット処理もしくは“フローレート”は、対応する各入来データキュー４８Ａ及び４８Ｂのフローレートである。
【００３８】
さらなるＶＲＩをルーター２０内に実装しても良いが、本発明の概念を説明に当たり簡単のために第１及び第２のＶＲＩ５０及び５２のみを示す。重要なのは、ルーター２０内の各ＶＲＩが、１以上の管理可能な入来データキュー４８に割り当てられていることである。
【００３９】
別の好適な実施形態では、管理可能なキューは、ＶＲＩプロトコルレイヤーの間に位置しても良い。ここでは、入来地点とは違って、パケットドロップ及び遅延パラメータは既知である。
【００４０】
ＣＰＵ４４は選択的に、ＦＩＦＯ形式で入来データキュー４８からパケットを検索し、それらを各出力目標と関連づけられた（不図示の）出力キューへ転送するか、さもなくば、送信不可能なパケットをドロップする。各入来データキュー４８からのパケットは、ＣＰＵ４４において所定のパケットフローレートで処理される。このレートは、所定の処理インターバル間においてＣＰＵ４４によって処理される各入来データキュー４８からのパケット数で定義される。各入来データキュー４８からのパケットのパケットフローレートは異なっても良いし、より詳細に記載するように、フロー管理処理、又はルーター２０のＲＴＯＳの一部である“フローマネージャ”５３によって制御されてもよい。
【００４１】
もし、ＣＰＵ４４により所定の入来データキュー４８に保持されているパケットを直ちに処理することが困難な場合、キューの長さはそれに応じて増加することは明らかである。もちろん、メモリ４６がパケットを格納するための容量は有限であり、各入来データキュー４８が割り当てられるのは、メモリ４６のバッファスペースの所定量に限られる。各入来データキュー４８に格納されたパケット数は、メモリ管理処理又は、ルーター２０のＲＴＯＳの一部である“メモリマネージャ”５３により監視される。特に、格納されたパケットの長さは変化する。
【００４２】
一般的に、ＤＲＡＭのような共有されるバッファメモリは、それらが比較的安価であり、コンパクトな形状ながら高い格納容量を有するので、パケットデータルーターにおける利用によく適している。しかしながら、メモリ４６へのリード、ライトそれぞれのアクセスには比較的時間を有する。というのも、ＣＰＵ４４とメモリ４６の間のデータバスの帯域幅の制限や、ＤＲＡＭが本来有する行アドレスのストローブのレイテンシが有るためである。言い換えれば、ＣＰＵ４４が各データパケットをメモリ４６へ格納（ライト）又はメモリ４６から検索（retreive）（リード）するために消費する相対的時間及びプロセッサリソースである。
【００４３】
図３を参照すると、フローマネージャ５４の機能は、入来データキュー４８のデータフローを管理・制御することである。本好適な実施形態では、フローマネージャ５４はシステムタスクとして実装される。これは、例えば、毎秒１回等、所定のインターバルにおいて入来データキュー４８のそれぞれについて反復される。フローマネージャ５４は、各入来データキュー４８に保持されているデータパケットの処理を監視して、ルーター２０の全体のデータフローと、特に、ＣＰＵ４４及びメモリ４６の稼働率を管理する。
【００４４】
この目的のために、フローマネージャ５４は、メモリ４６に格納されているデータキューヘッド構造を、各入来データキュー４８へのヘッダーとして維持する。データキューヘッド構造５５は、フローマネージャ５４によって、パケットフローレートを制御し、各入来データキュー４８に割り当てられるメモリの量を制御するために利用されるいくつかのデータフィールドを含む。好適な実施形態においては、データキューヘッド構造５５におけるデータフィールドは、以下のものが含まれる。
【００４５】
（１）“処理すべきパケット（packets-to-be-processed）”フィールド５６は、ＣＰＵ４４によって所定の処理インターバルにて処理される、各データキュー４８に保持されているパケット数を示す値を有する。
【００４６】
（２）“キューカウント(queue count)”フィールド５８は、現在、各入来データキュー４８に保持されているパケット数を示す値を有する。
【００４７】
（３）“処理バイト(bytes-processed)”フィールド６０、所定の処理インターバルにおいて処理された各データキュー４８からのデータバイト数を表す値を有する。
【００４８】
（４）“持続的データレート（sustained-data-rate）”フィールド６２は、例えば、ＩＳＰ２２による顧客サービス契約（costomer serveice agreement）に基づいた、データキュー４８それぞれについての、ターゲット最大データ処理レートをｂｐｓで示す値を有する。
【００４９】
（５）“バーストデータレート（burst-data-rate）”フィールド６４は、データバーストの受信に基づいて一時的に実施された、各データキュー４８についての増加した最大データ処理レートをｂｐｓで示す値を有する。
【００５０】
（６）  “バースト期間（burst-duration）”フィールド６６は、バーストデータレートフィールド６４において規定されるデータレートが、データバーストを受信に応じて維持される最大時間を秒（又は他の単位で）表す値を有する。
【００５１】
（７）“キュー深度（queue-depth）”フィールド６８は、各データキュー４８に一度に保持可能なパケットの最大数を示すものである。即ち、パケット数が最大に達した場合は、現在格納されているパケットが処理され、他を格納するための余地ができない限りは、新たに受信したパケットがドロップされてしまう。
【００５２】
（８）“バーストスタート（burst-start）”フィールド７０は、各データキュー４８でデータバーストの受信を検知した時を示す時間スタンプ値を保持するためのものである。
【００５３】
（９）“システムタイムスタンプ（system-time-stamp）”フィールド７２は、データキューヘッド構造５５のポールが最後に実行された時を示すタイムスタンプ値を保持するためのものである。
【００５４】
当業者には理解されるように、データフィールド（１）から（９）の実際の順番は、特別に重要なものではなく、ここに開示する本発明の概念から逸脱することなく多くの変更が可能である。
【００５５】
本発明の一般的な側面によれば、フローマネージャ５４及びメモリマネージャ５３は、継続的に現在のルーター２０の動作状況、例えば、プロセッサやメモリの稼働状況を監視する。各データキューヘッド構造５５のデータフィールド（１）から（９）は、いくつかのタスクを実行するためにフローマネージャ５４とメモリマネージャ５３によって利用される。当該タスクには、フローレートの監視及び調整、バーストデータレートの監視、各入来データキュー４８についてのメモリ割当て及び稼働率の調整が含まれる。
【００５６】
フローマネージャ５４はまた、例えば、周期的なタスクとして、各入来データキュー４８の各フローレートを監視し、もし適切で有れば、エンドユーザーのサービス品質（ＱＯＳ）への影響が最小で済むようにシステム全体の安定性を確保するために、１以上の入来データキュー４８のパケットフローレートの対応する調整を行う。特に、ルーター２０のシステム安定性、及び、より重要な、ルーター２０によってサービスされる、各ユーザー２４、ユーザーグループ３２Ａ／３２Ｂ及び／又はＶＲＩ５０／５２のＱＯＳは、各パケットフローレート及び個々の入来データキュー４８に対する比例的なメモリ割当ての制御を通して最良に管理されてもよい。
【００５７】
例えば、本発明の一般的な側面によれば、もしプロセッサ稼働率が、所望の動作範囲の上限に到達するか、又は、これを越えた場合、フローマネージャ５４は、１以上の入来データキュー４８のパケットフローレートを、対応する処理すべきパケットフィールド５６の値を減ずることにより減少させるであろう。逆に、もしプロセッサ稼働率が、所望の動作範囲の下限に到達するか、又はこれを下回った場合は、対応する処理すべきパケットフィールド５６の値を増やすことにより、１以上の入来データキュー４８のパケットフローレートを増加させてもよい。
【００５８】
入来データキューレベルにおいてデータパケット処理を制御することの利点は、個々のエンドユーザー２４、ユーザーグループ３２Ａ／３２Ｂ、もしくはＶＲＩ５０／５２が反比例的に影響を受けることなく、ルーター２０のシステムリソースが公平に分配され、制限されることである。一方、ルーターの従来のＲＴＯＳは、同一ＱＯＳを有するが、異なる入来データキュー上でルーターにアクセスしているエンドユーザー間では差別化できなかった。
【００５９】
説明のために、ＶＲＩ５０及びＶＲＩ５２が同一のＱＯＳプロフィールを有するが、ある場合において、ＶＲＩ５０は唯一のアクティブなエンドユーザー２４をそのネットワーク上に有する一方で、ＶＲＩ５２が１９のアクティブなエンドユーザー２４を有すると仮定する。従来のルーターＲＯＴＳシステムは、リソースを異なるユーザー内で均等に割り当てる（及び制限する）。即ち、各エンドユーザー２４に対しトータル帯域幅の５％が割り当てられる。実際は、ＶＲＩ５０の唯一のエンドユーザー２４は、利用可能なルーター帯域幅の半分（５０％）が割り当てられ、ＶＲＩ５２の１９のエンドユーザー２４が残りの半分を彼らでシェアするはずであるにもかかわらずである。
【００６０】
個々の入来データキューのフローレートを制御可能とすることにより、本発明は従来の技術におけるこの問題点を解消するものである。また、個々のユーザー又はＶＲＩの帯域幅保証（即ち、入来データキューレベルにおけるもの）が本発明により可能となる。さらに、入来データキュー４８のデータ処理速度を制御することにより、ＩＳＰ２２はサブレート帯域幅レート（sub-rate bandwidth rates）を高速モデム上で実行してもよい。例えば、ＱＯＳプロフィールが２８．８Ｋでしかないエンドユーザーについて５６．８Ｋモデム接続を可能とする。より重要なことに、入来データキュー４８についての独立した制御により、ピークトラヒック負荷を扱う場合において、より予測がたてやすくなる。
【００６１】
本発明のこの側面に応じて、フローマネージャ５４は好ましくは、入来データキュー４８の各フローレートを互いに独立に調整する。ＩＳＰ２２において維持されるＱＯＳプロフィール７４のそれぞれに基づいて、フローマネージャ５４は、どのエンドユーザー２４、ユーザーグループ３２Ａ又は３２Ｂ及び／又はＶＲＩ５０又は５２のＱＯＳ基準についても不利な影響を最小とする入来データキュー４８のフローレートを調整する。
【００６２】
各顧客ＱＯＳプロフィールのある側面は、各入来データキュー４８のデータキューヘッド構造５５において維持される。例えば、持続的データレートフィールド６２は、各入来データキュー４８についてのターゲット最大データ処理レートを示す。これにより、各データキュー４８についての処理すべきパケットフィールド５６の値が計算される。好適な実施形態では、入来データキュー４８についての持続的データレートフィールド６２は、まず、各データキュー４８と関連したエンドユーザー２４、ユーザーグループ３２Ａ／３２Ｂ、もしくはＶＲＩ５０／５２の最大の割当レート（maximum alloted rate）に基づいて決定される。その後、各入来データキュー４８についての持続的データレート６２は、現在のルーター２０の動作状態に動的に基づく。例えば、ＶＲＩ５０及び／又はＶＲＩ５２と関連した１以上のデータキュー４８Ａのパケットフローレートは、ルーター２０のプロセッサ稼働率を所定の動作範囲内に維持するように周期的に調整されても良い。
【００６３】
フローマネージャ５４はまた、各入来データキュー４８において受信されてもよいデータバーストを管理する。ＱＯＳユーザープロフィール７４は、突発的なバーストパケットトラヒックに順応するために、短い期間においてパケット処理帯域幅の付加的量が与えられるように、好ましくはエンドユーザー２４に提供される。例えば、エンドユーザー２４は、大きなファイルを月に一度送信する必要があっても良い。費用がかかる持続的なデータレート帯域幅のために支払いさせる代わりに、ＩＳＰ２２はエンドユーザー２４に付加的な“バーストデータレート”を特定の時間（例えばバースト期間）において提供することができる。
【００６４】
好適な実施形態では、各入来データキュー４８についてのバーストデータレート６４は、まず、ＩＳＰ２２によって各入来データキュー４８に関連するどのエンドユーザー２４に対しても保証される、最大バーストデータレートの最も高いもの（highest maximum burst data rate）に基づいて決定される。同様に、各入来データキュー４８についてのバースト期間フィールド６６は、まず、ＩＳＰ２２によって各入来データキュー４８に関連するどのエンドユーザー２４に対しても保証される、最高の最大バースト期間に基づいて決定される。その後、バーストデータレート６４及びバースト期間６６は、現在のルーター２０の動作状態に基づいて、各入来データキュー４８について動的に調整される。
【００６５】
とりわけ、フローマネージャ５４は、異なる持続的データレート６２、バーストデータレート６４、及びバースト期間６６の値を、１以上の入来データキュー４８について、例えば、“日中における変動（time of day variances）”のような、オフピーク稼働基準（off-peak usage criteria）に基づいて割り当てても良いが、どの入来データキュー４８のフローレートについても、システムの完全性を保持するための絶対的に必要とならない限り、好ましくは、ＩＳＰ２２によって（例えば、当該ユーザーのＱＯＳプロフィールに基づいて）どのエンドユーザー２４にも保証されている最大の最小限レートよりも低くは減少させないであろう。
【００６６】
図４は、フローマネージャ５４が、データバーストが各入来データキュー４８において受信されているかどうかを検出するための、ある好適な処理を示す。フローマネージャ５４は、周期的に各入来データキュー４８をポーリングし、現在のデータフローレート７８（ｂｐｓにて）を計算する（ステップ７８）。好適な実施形態では、フローマネージャ５４は、各入来データキュー４８についてのデータヘッドキュー構造５５の処理バイトフィールド６０の値に８を乗ずることによって現在のフローレートを計算する。結果物は、現在の時間とシステムタイムスタンプフィールド７２の値との差分によって割られる。フローマネージャ５４は、（ステップ８０において）計算した現在のパケットフローレートと、持続的データレート６２における値を比較する。
【００６７】
もし、計算されたレートが持続的データレートよりも大きい場合は、フローマネージャ５４はデータバーストが各入来データキュー４８において発生したとみなす。フローマネージャ５４は、（ステップ８２において）処理すべきパケットフィールド５６の値を、バーストデータレートフィールド６４の値に基づいて再計算し、バーストスタートフィールド７０に現在の時間のタイムスタンプをセットする。もし受信バーストが検出されない場合は、即ち、計算されたデータレートが持続的データレートフィールド６２と等しいか、より小さい場合は、フローマネージャ５４は、（ステップ８５において）、システムタイムスタンプフィールド７２を更新し、処理バイトフィールド６０の値を、次のポーリングサイクルのためにリセットする。
【００６８】
もしデータバーストが入来データキュー４８において検出されると、フローマネージャ５４は、（ステップ８４において）周期的にデータバーストの期間を、現在の時間とバーストスタートフィールド７０のタイムスタンプとの差分を算出することにより計算する。フローマネージャは、（ステップ８６において）計算されたバースト期間と、バースト期間フィールド６６の値とを比較する。
【００６９】
現在のデータバースト期間が、バースト期間フィールド６６の値よりも小さい場合は、フローマネージャは（ステップ８８において）、処理すべきパケットフィールド５６の値を、バーストデータレートフィールド６４の値に基づいて保持する。もし、バースト期間が、バースト期間フィールド６６の値よりも長く継続した場合は、フローマネージャ５４は処理すべきパケットフィールド５６の値を持続的データレートフィールド６２の値に基づいて再計算する。
【００７０】
好適な実施形態では、バーストデータレートフィールド６４の値及びバースト期間フィールド６６の値は、フローマネージャ５４によって、ルーターにおける現在の動作状態に基づいて調整されても良い。例えば、顧客サービスに役立つものとして、ＩＳＰ２２は、フローマネージャ５４を、バーストデータレートフィールド６４とバースト期間フィールドの値を、ルーター２０のプロセッサ稼働率が規定された動作範囲以下である限り増加するように構成しても良い。
【００７１】
図３に戻って、メモリマネージャ５３は、各入来データキュー４８についての各キューカウント及びキュー深度フィールド５８及び６８を、メモリ管理処理の一環として監視する。もし、ルータメモリ４６の全体の稼働率が、所望の範囲の上限に到達したか、又はこれを越えた場合、メモリマネージャ５３は、１以上の入来データキュー４８に割り当てられているメモリ量を、対応するキュー深度フィールド６８の値を減ずることにより減少させるであろう。逆に、もしメモリ４６の稼働率が、所望の範囲の下限に到達したか、又はこれを下回った場合は、メモリマネージャ５３は、１以上の入来データキュー４８に割り当てられているメモリ量を、対応するキュー深度フィールド６８の値を増加することにより増やすであろう。好適な実施形態においては、メモリマネージャ５３は、入来データキュー４８のキュー深度フィールド６８を、受信データバーストの検出に応じて増加する。そうすることにおいて、１以上の他の入来データキュー４８のキュー深度フィールド６８を、メモリ稼働率を維持するために同時に減少することが必要となるかもしれない。
【００７２】
パケットフローレートと同様に、各入来データキュー４８にパケットを格納するために割り当てられるメモリの量は、好ましくは、全ての他のキュー４８について割り当てられるメモリとは独立して決定される。好適な実施形態においては、キュー深度フィールド６８はまず、各データキュー４８に関連する全てのエンドユーザー２４、ユーザーグループ３２Ａ／３２Ｂ、及び／又はＶＲＩ５０／５２に対して割り当てられたメモリの全体的な最大量に基づいて決定される。その後、各入来データキュー４８にについてのキュー深度フィールド６８は、ルーター２０の現在の動作状態に動的に基づく。例えば、ＶＲＩ５０及び／又はＶＲＩ５２に関連する１以上のデータキュー４８Ａのキュー深度フィールド６８は、所定の範囲内にメモリの稼働率が維持されるように、周期的に調整されても良い。
【００７３】
メモリマネージャ５３は、例えばＩＳＰ２２において維持されるＱＯＳプロフィール７４のそれぞれに基づいて、どのエンドユーザー２４、ユーザーグループ３２Ａ又は３２Ｂ及び／又はＶＲＩ５０又は５２のＱＯＳ基準についても不利な影響を最小とする入来データキュー４８のキュー深度フィールド６８を調整するであろう。好ましくは、メモリマネージャ５３は、各データキュー４８に関連するエンドユーザー２４、ユーザーグループ３２Ａ又は３２Ｂ及び／又はＶＲＩ５０又は５２の全体について、ＩＳＰ２２によって保証される最小レートのうち最高のものを下回るまでには、どの入来データキュー４８についてもキュー深度フィールド６８を減少させない。
【００７４】
各メモリマネージャ５３とフローマネージャ５４を構成するオペレーティングプロセスは、好ましくは、ルーター２０のために管理ツールを改善するためにリンクされる。例えば、プロセッサリソースが利用可能であれば、フローマネージャ５４は１以上の入来データキュー４８のパケットフローレートを減少させるであろう。即ち、格納されたパケットのバックロードの処理レートを上げて、メモリの稼働率を下げる。実際、もし可能で有れば、ＱＯＳの観点から一時的に、最高のキューカウントフィールド５８を有する入来データキュー４８のパケットフローレートを増加させることは、キュー深度フィールド６８を減少させることよりも、パケットのドロップを避ける、又は最小限にするためには好ましい。
【００７５】
図５は、ＩＳＰ１００によってインターネットゲートウェイとして利用される代替的な好適なパケットデータルーターシステム１１０を示す。ルーターシステム１１０は、複数のルーター１１２，１１４，１１６及び１１８を含み、それぞれは、データパケットを複数の異なるエンドユーザーネットワーク１２４から、ＰＳＴＮ２６を介して受信し、処理する。各受信データパケットに含まれるルーティング情報に基づいて、ルーターシステム１１０は、パケットを各インターネットサーバー３８に転送、エンドユーザーネットワーク１２４にパケットを転送、又は、不知の目的地アドレスを有するか又は、配信不可能であることを理由にパケットをドロップする処理のうち、いずれかを実行する。ルーターシステム１１０はまた、“ダウンストリーム”データパケットをインターネットサーバー３８から受信し、可能で有れば、受信したダウンストリームパケットを各エンドユーザーネットワーク１２４に転送する。
【００７６】
エンドユーザーネットワーク１２４は、少なくとも３つの別個の顧客アカウント１２４（Ａ）、１２４（Ｂ）及び１２４（Ｃ）を含む。ルーターシステム１１０は、個人及びネットワークの両方を含む、膨大な数の他のエンドユーザー及び顧客アカウントを有してもよい。しかしながら、本発明の更なる側面を説明において簡単のために、ネットワーク１２４（Ａ）、１２４（Ｂ）及び１２４（Ｃ）のみを示す。
【００７７】
図６を参照すると、ルーターシステム１１０の各ルーター１１２、１１４、１１６及び１１８は、実質的にルーター２０と同一に構成されている。各ルーター１１２、１１４、１１６及び１１８は、共同して単一制御機能を実行する１以上のプロセッサを有するが、ここではこれらを単純化のためにまとめて示し、単一中央処理ユニット（ＣＰＵ）１４４とする。ルーター１１２、１１４、１１６及び１１８はまた、共有されるバッファメモリ１４６を含む。これは、好ましくはＤＲＡＭで実現される。
【００７８】
図示された好適な実施形態においては、ＰＳＴＮ２６からの通信回線３６は、通信インタフェース１４０で終端される。この通信インタフェース１４０は、ソフトウェアを実装可能な複数のＤＳＰ１４２を備える。別の実施形態では、１以上の個々のルーター１１２、１１４、１１６及び１１８は入来したパケットトラヒックをシフトすることを可能とする他の各ルータへの少なくとも１のインタフェース接続と共に、それぞれが独自に通信インタフェースを有している。
【００７９】
ＤＳＰ１４２によって処理（例えば復調）されるアップストリームパケットは、まず各ルーター１１２、１１４、１１６及び１１８のメモリ１４６においてリンクされたリストとして形成される各入来データキュー４８において保持される。ルーター２０における入来データキュー４８について上述したように、ルーターシステム１１０の各ルーター１１２、１１４、１１６及び１１８の入来データキュー１４８は、ＦＩＦＯ形式での処理のための格納パケットを保持するソフトウェアデータ構造を有する。各キュー１４８は、“深度”即ち、各キューが保持可能な格納パケットの最大数の概念を有している。ここで詳細に記載されるように、ルータシステム１１０はシステムＱＯＳコントローラ１２０を含んでいる。これは、各ルーター１１２、１１４、１１６及び１１８の動作状態を監視し、どのようにアップストリームパケットデータトラヒックを様々な入来データキュー１４８に分配するかを動的に制御するものである。
【００８０】
図７を参照すると、各ルーター１１２、１１４、１１６及び１１８における１以上の入来データキュー１４８Ａが、顧客Ａ（ＶＲＩ−Ａ）のための第１のＶＲＩとして実装されており、ルーター１１２及び１１６における１以上の入来データキュー１４８Ｂが、顧客Ｂ（ＶＲＩ−Ｂ）のための第２のＶＲＩとして実装されている。また、ルーター１１４及び１１８における１以上の入来データキュー１４８Ｃが、顧客Ｃ（ＶＲＩ−Ｃ）のための第３のＶＲＩとして実装されている。各ＶＲＩは、それが現れる各ルーター内に固有のルーティングドメインを有する。各ルーター１１２、１１４、１１６及び１１８は１以上のさらなるＶＲＩを有しても良いが、ＶＲＩ−Ａ、ＶＲＩ−Ｂ及びＶＲＩ−Ｃのみを簡単のために示す。
【００８１】
システム１１０の各ルーター１１２、１１４、１１６及び１１８は、ＱＯＳマネージャ１５２、フローマネージャ１５４及びメモリマネージャ１５６を含み、これらは全て各ルータのＲＯＴＳの一部である。ＱＯＳマネージャ１５２は、各ルーター１１２、１１４、１１６及び１１８の各フロー及びメモリマネージャ１５４及び１５６と、システムＱＯＳコントローラ１２０との間の制御インタフェースである。ルーター２０のフロー及びメモリマネージャ５４及び５３と同様に、各ルーター１１２、１１４、１１６及び１１８の各メモリ及びフローマネージャ１５４及び１５６は、各ルーターの入来データキュー１４８のデータフローを管理し制御する。本好適な実施形態のいて、フロー及びメモリーマネージャ１５４及び１５６は、システムタスクとして実装される。これは、例えば、毎秒１回等、所定のインターバルにおいて、各ルーター１１２、１１４、１１６及び１１８の各入来データキュー１４８のそれぞれについて反復される。
【００８２】
特に、フロー及びメモリーマネージャ１５４及び１５６は、各入来データキュー１４８に保持されているデータパケットの処理を監視して、ルーターの全体のデータフローと、特に、ＣＰＵ４４及びメモリ４６の稼働率を管理する。フロー及びメモリーマネージャ１５４及び１５６のそれぞれは、各ルーター１１２、１１４、１１６及び１１８の各入来データキュー１４８について、ルーター２０のデータキューヘッド構造５５における各フィールドと同一のものを含むデータキューヘッド構造を監視及び維持する。このように、ルーター２０と同様に、ルーターシステム１１０の各ルーター１１２、１１４、１１６及び１１８は、個々にパケットフローレートを制御し、各入来データキュー１４８に割り当てられたメモリを制御する能力がある。さらに、システムＱＯＳコントローラ１２０は、ルーターＱＯＳマネージャ１５２と結合して、ルーターの動作状態に応じて、各ルーター１１２、１１４、１１６及び１１８の各入来データキュー１４８間で入来パケットトラヒックをシフトする能力がある。
【００８３】
例えば、本発明のさらなる側面によれば、各ルーター１１２、１１４、１１６及び１１８上のＶＲＩ−Ａと関連する１以上の入来データキュー１４８のデータ処理レートがルーター１１２の現在の動作状態に基づいて調整される。好ましくは、各ルーター１１２、１１４、１１６及び１１８上のＶＲＩ−Ａと関連する１以上の入来データキュー１４８のデータ処理レートは、他のルーター上のＶＲＩ−Ａと関連する１以上の入来データキュー１４８の処理レートとは独立して調整される。個々のデータキューのフローレートの調整に加えて、システムＱＯＳコントローラ１２０は、ＶＲＩのどれか１つと関連する入来データキュー１４８間において、システム負荷をよりよくバランスさせるために、入来パケットトラヒックを再割当てしても良い。
【００８４】
本発明の好適な実施形態及びアプリケーションが示され、記載された一方で、当業者には理解されるように、多くの修正及び応用は、本発明の概念から逸脱することなく可能である。このように、開示された発明の範囲は、特許請求の範囲に対応することなく限定されるものではない。
【図１】
2011130457.tif 000003
【図２】
2011130457.tif 000004
【図３】
2011130457.tif 000005
【図４】
2011130457.tif 000006
【図５】
2011130457.tif 000007
【図６】
2011130457.tif 000008
【図７】
2011130457.tif 000009
【手続補正書】
【提出日】平成23年2月7日(2011.2.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
選択されたパケットフローレートにおいて、ルーターにおける１つ以上の入来データキューのパケットの処理を制御する方法であって、
前記ルーターのメモリ内に保持されている前記１つ以上の入来データキューのそれぞれのパケットフローレートを、それぞれの前記入来データキューのヘッダとしてデータキューヘッド構造を利用することで管理及び制御する工程を備え、
前記データキューヘッド構造は、所定の処理インターバルにおいて前記ルータによって処理されるべき前記１つ以上の入来データキューに保持されたパケット数を示す値を有する処理すべきパケットフィールドを含む複数のデータフィールドを有し、
前記パケットフローレートが、前記処理すべきパケットフィールドと、目標最大パケット処理レートを示す持続的データレートフィールドとの値を増加又は減少させることにより調整され、
データバーストを受信したかどうかの判定が、
前記持続的データレートフィールドの値を選択された非バーストパケットフローレートに設定し、
前記１つ以上の入来データキューの現在のパケットフローレートを計算し、
前記計算したパケットフローレートと前記持続的データレートフィールドの値とを比較する
ことにより実行される、ことを特徴とする方法。
【請求項２】
各入来データキューの前記データキューヘッド構造はさらに、増加された最大データ処理レートを示すバーストデータレートフィールドを含み、
もし、前記１つ以上の入来データキューにおいてデータバーストが検出されなければ、前記処理すべきパケットフィールドの値は、前記持続的データレートフィールドの値に基づき、
もし、前記１つ以上の入来データキューにおいてデータバーストが検出されれば、前記処理すべきパケットフィールドの値が、選択された期間において前記バーストデータレートフィールドの値に基づく
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記データキューヘッド構造がさらに、処理すべきパケットフィールドの値を、バーストデータレートフィールドの値に依存させるための選択された期間を示す値を格納するバースト期間フィールドを含む、ことを特徴とする請求項２に記載の方法。
【請求項４】
前記バーストデータレートフィールド及び前記バースト期間フィールドの値が、前記ルーターの現在の動作状態に基づいて調整されることを特徴とする請求項３に記載の方法。
【請求項５】
前記１つ以上の入来データキューうちの１つにおいてデータバーストが受信されているかどうかを検出する工程と、
前記データバーストの受信を検出した場合に、受信したデータバーストの検出に応じて、前記１つ以上の入来データキューのうちの前記１つの前記パケットフローレートを一時的に増加させる工程と
を更に備えることを特徴とする請求項１に記載の方法。
【請求項６】
データキューヘッド構造が更に、タイムスタンプフィールドと、処理バイトフィールドとを含み、
前記１つ以上の入来データキューの現在のパケットフローレートが、
前記タイムスタンプフィールドの値を、現在のパケットフローレートの計算が最後に行われた時間に設定し、
パケットフローレートの最後の計算以降に処理されたデータのバイト数を反映するように前記処理バイトフィールドの値を設定し、
前記タイムスタンプフィールドと前記処理バイトフィールドの値のそれぞれに基づいて、前記１つ以上の入来データキューのパケットフローレートを計算する
ことにより計算されることを特徴とする請求項１に記載の方法。
【請求項７】
前記１つ以上の入来データキューのそれぞれには、受信パケットを格納するためにルータ内でメモリ容量が割り当てられ、
前記メモリの現在の稼働率に基づいて、前記１つ以上の入来データキューのそれぞれに前記受信パケットを格納するために割り当てられるメモリ容量を調整する工程と、
前記１つ以上の入来データキューのそれぞれにおける前記受信パケットに割り当てられるべきメモリ容量を所定範囲で最適化するためにキュー深度フィールドとキューカウントフィールドとを監視し調整する工程と
をさらに備え、
前記１つ以上の入来データキューのそれぞれの前記データキューヘッド構造は、
関連する入来データキューで保持可能な最大パケット数を示す前記キュー深度フィールドと、前記関連する入来データキュー内に現在保持されているパケット数を示す前記キューカウントフィールドとを含み、
前記キュー深度フィールドは、前記１つ以上の入来データキューにおける他の入来データキューと関連付けられたキュー深度フィールドと同時に調整可能である
ことを特徴とする請求項１に記載の方法。
【請求項８】
前記１つ以上の入来データキューの前記パケットフローレートを、ルータプロセッサの現在の稼働率に基づいて調整する工程を更に備えることを特徴とする請求項１に記載の方法。
【請求項９】
前記ルーターはメモリを有し、
前記入来データキューの前記パケットフローレートは、前記メモリの現在の稼働率に基づいて調整されることを特徴とする請求項１に記載の方法。
【請求項１０】
前記１つ以上の入来データキューのそれぞれのパケット処理レートは、他の全ての入来データキューのパケット処理レートとは独立に調整されることを特徴とする請求項１に記載の方法。
【請求項１１】
第１のキューのパケット処理レートを増加させる工程と、
前記第１のキューでのデータバースト受信の検出に応じて第２のキューのパケット処理レートを減少させる工程と、
を更に備えることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記ルーターが共同して共通制御機能を実行する１以上のプロセッサを有し、
前記１以上のプロセッサがプロセッサ稼働率を有し、
前記第１のキューの前記パケット処理レートと、前記第２のキューの前記パケット処理レートとは、独立に調整される
ことを特徴とする請求項１１に記載の方法。
【請求項１３】
選択されたパケットフローレートにおいて、ルーターにおける１つ以上の入来データキューのパケットの処理を制御する装置であって、
前記ルーターのメモリ内に保持されている前記１つ以上の入来データキューのそれぞれのパケットフローレートを、それぞれの前記入来データキューのヘッダとしてデータキューヘッド構造を利用することで管理及び制御するフローマネージャを備え、
前記データキューヘッド構造は、
目標最大パケット処理レートを示す持続的データレートフィールドと、
所定の処理インターバルにおいて前記ルータによって処理されるべき前記１つ以上の入来データキューに保持されたパケット数を示す値を有する処理すべきパケットフィールドと、
処理すべきパケットフィールドの値を、バーストデータレートフィールドの値に依存させるための選択された期間を示す値を格納するバースト期間フィールドと
を含む複数のデータフィールドを有し、
前記パケットフローレートが、前記処理すべきパケットフィールドと、目標最大パケット処理レートを示す前記持続的データレートフィールドとの値を増加又は減少させることにより調整され、
もし、前記１つ以上の入来データキューにおいてデータバーストが検出されなければ、前記処理すべきパケットフィールドの値は、前記持続的データレートフィールドの値に基づき、もし、前記１つ以上の入来データキューにおいてデータバーストが検出されれば、前記処理すべきパケットフィールドの値が、選択された期間において前記バーストデータレートフィールドの値に基づき、
前記フローマネージャは、データバーストを受信したかどうかの判定を、
前記持続的データレートフィールドの値を選択された非バーストパケットフローレートに設定し、
前記１つ以上の入来データキューの現在のパケットフローレートを計算し、
前記計算したパケットフローレートと前記持続的データレートフィールドの値とを比較する
ことにより行なうことを特徴とする装置。
【請求項１４】
前記フローマネージャは、前記バーストデータレートフィールド及び前記バースト期間フィールドの値を、前記ルーターの現在の動作状態に基づいて調整することを特徴とする請求項１３に記載の装置。
【請求項１５】
前記フローマネージャは、
前記１つ以上の入来データキューうちの１つにおいてデータバーストが受信されているかどうかを検出し、
受信した前記データバーストの検出に応じて、前記１つ以上の入来データキューの前記パケットフローレートを一時的に増加する
ことを特徴とする請求項１３に記載の装置。
【請求項１６】
前記データキューヘッド構造が更に、
前記データキューヘッド構造のポールが最後に実行された時を示すタイムスタンプフィールドと、
現在の処理インターバルにおいて処理されたデータバイト数を示す処理バイトフィールドと
を含み、
前記タイムスタンプフィールドと前記処理バイトフィールドとの値のそれぞれに基づいて、前記１つ以上の入来データキューのそれぞれのパケットフローレートを計算するために、前記タイムスタンプフィールドと前記処理バイトフィールドとの値が利用される
ことを特徴とする請求項１３に記載の装置。
【請求項１７】
前記１つ以上の入来データキューのそれぞれには、受信パケットを格納するためにルータ内でメモリ容量が割り当てられ、
前記装置は、前記メモリの現在の稼働率に基づいて、前記１つ以上の入来データキューのそれぞれに前記受信パケットを格納するために割り当てられるメモリ容量を監視し調整するメモリマネージャを更に備え、
前記データキューヘッド構造は、関連する入来データキューで保持可能な最大パケット数を示すキュー深度フィールドと、前記関連する入来データキュー内に現在保持されているパケット数を示すキューカウントフィールドとを含み、
前記メモリマネージャは、サービス品質基準に対する不利な影響を最小とする、前記１つ以上の入来データキュー内の前記キュー深度フィールドを調整する
ことを特徴とする請求項１３に記載の装置。
【外国語明細書】
2011130457000001.pdf