優先経路制御方法及びルータ装置
【課題】 帯域確保を行うことなく、リアルタイム性の高いデータから低いデータまでを最適な優先度でルーティング処理でき、ネットワークの帯域利用効率を向上可能な優先経路制御方法及びルータ装置を提供すること。
【解決手段】 複数の入力ポート21から入力された通信パケットを複数の出力ポート23へ出力するスイッチ部22を、通信パケットに付与された宛先アドレスに対応してその経路を切り替える空間スイッチ27とともに、複数の通信パケットの順序を任意に入れ替え可能な時間スイッチ28とで構成し、該時間スイッチ28を複数の通信パケットの順序が各通信パケットに付与された送達希望時刻に対応する順序となるよう制御する。
【解決手段】 複数の入力ポート21から入力された通信パケットを複数の出力ポート23へ出力するスイッチ部22を、通信パケットに付与された宛先アドレスに対応してその経路を切り替える空間スイッチ27とともに、複数の通信パケットの順序を任意に入れ替え可能な時間スイッチ28とで構成し、該時間スイッチ28を複数の通信パケットの順序が各通信パケットに付与された送達希望時刻に対応する順序となるよう制御する。
【発明の詳細な説明】
【0001】
【発明の属する技術分野】本発明は、通信パケットを高速かつ効率良くルーティング可能な優先経路制御方法及びルータ装置に関するものである。
【0002】
【従来の技術】電気通信の分野において、通信ネットワークを介して情報を効率良く交換・伝送するために、交換機(exchange)やルータ(router)等の経路制御装置(以下、「ルータ装置」と呼ぶ。)が用いられる。このルータ装置は、特に、インターネットを介した情報データ通信で広く用いられており、インターネットを構成する上で重要な役割をはたしている。以下、図1を参照して、従来のルータ装置について説明する。
【0003】図1は従来のルータ装置の一例を示すもので、図中、11は複数の入力ポート、12はスイッチ部、13は複数の出力ポート、14は経路制御部、15は通信パケットである。
【0004】次に、従来のルータ装置の動作について図1R>1を参照して説明する。
【0005】入力ポート11から入力された通信パケット15は、スイッチ部12に入力される。それぞれの通信パケット15にはパケットの宛先を示す宛先アドレス(例えばインターネットプロトコル(以下、「IP」と記す。)で用いられているIPアドレス)15aが付加されており、スイッチ部12を制御する経路制御部14はこの宛先アドレス15aに基づいて、通信パケット15をどの出力ポート13から出力すべきかを判断する。
【0006】スイッチ部12は空間スイッチ16から構成されており、通信パケット15から宛先アドレス15aを取り出して経路制御部14に問い合わせると、経路制御部14はルーティングテーブルを検索し、通信パケット15をどの出力ポート13にスイッチングすれば良いかを得て、その結果を空間スイッチ16に返し、空間スイッチ16がこの結果を受けて通信パケット15をスイッチングする。
【0007】スイッチ部12によって目的の出力ポート13にスイッチングされた通信パケット15は、出力ポート13から出力される。
【0008】入力ポート11から同じ宛先への通信パケットが大量に入力された場合、空間スイッチ16において輻輳が発生し、通信パケットは破棄される。
【0009】
【発明が解決しようとする課題】ルータ装置の役割は、入力された通信パケットをルーティング処理して出力することであって、従来のルータ装置では、経由する通信量が少なければ小さい遅延でルーティング可能であるが、通信量が多ければ遅延が大きくなり、また、空間スイッチの許容能力を越える通信パケットが入力されると、通信パケットを破棄する。即ち、従来のルータ装置は、通信パケットを転送するために最大限の努力をするが、処理能力の限界や通信回線の速度限界によって通信できないこともあるという、ベストエフォート型のネットワークを提供する。
【0010】電話の音声データや放送の動画像データ等は、リアルタイム性の高いデータであり、通信の遅延時間に大きなゆらぎが発生したり、通信パケットに欠落が生じると、受信側において正確なデータ再生ができなくなる。このため、これまでは、リアルタイム性の高いデータに対して「帯域保証」という概念の下、予め必要な通信路の帯域を確保して通信を行うようになしていた。
【0011】しかし、帯域確保を行う場合、(a)送受信者間の全ての回線で帯域を確保しなければならない、(b)通信量が変動する場合、その最大値で帯域を確保しなければならないため、帯域利用効率が悪くなる、(c)ルータ装置において帯域確保のための処理負荷が大きい、という問題があった。
【0012】以上のことから、帯域確保という手段によってリアルタイム性の高いデータを確実に届けることは可能であるが、多くの問題を抱えていた。
【0013】また、帯域保証の他に、個々の通信パケット毎に優先度が高いか低いかを表す値を付加し、リアルタイム性の高い通信パケット等を優先度の高い通信パケットとしてルーティングを行わせることにより、信頼性を向上させる方法もある。
【0014】しかし、この場合、優先度の高い通信パケットは通過する全てのルータ装置において優先的に扱われ、逆に優先度の低い通信パケットは全てのルータ装置において優先度が低く扱われてしまうことになる。即ち、通信パケットの重要の度合いが優先度が高いか低いかという固定的なパラメータで表されるため、優先度の高い通信パケットは必要以上に優先処理されるという状況が生じ、また、通信料金も一律に高くつくという問題があった。
【0015】本発明の目的は、このような問題を解決し、帯域確保を行うことなく、リアルタイム性の高いデータからリアルタイム性を問わないバルクデータまでの幅広いデータを最適な優先度でルーティング処理でき、ネットワークの帯域利用効率を向上可能な優先経路制御方法及びルータ装置を提供することにある。
【0016】
【課題を解決するための手段】上記目的を達成するため、請求項1記載の発明では、通信パケット毎にラベル付けされた宛先アドレスに基づいて、通信パケットの経路を切替制御して送り出す経路制御方法において、宛先アドレスとともに送達希望時刻をラベル付けし、この送達希望時刻に基づいてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする。
【0017】前記構成によれば、個々の通信パケットを送達希望時刻に応じた順序で経路制御でき、リアルタイム性の高いデータから低いデータまで最適な優先度でルーティング処理できるとともに、ネットワークリソースを有効活用できる。
【0018】また、請求項2記載の発明では、通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定することを特徴とする。
【0019】前記構成によれば、データリンクの伝送帯域・距離のみによる課金処理に代えて、空間軸あるいは時間軸における情報の移動距離に基づいて個々のパケット毎にきめ細かい課金を行うことができる。
【0020】また、請求項3記載の発明では、ルータ装置のアドレス及び通信パケットの宛先アドレスより求められるルータ装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする。
【0021】前記構成によれば、上位レイヤを終端することなく、情報の属性に応じて処理の差別化を図ることが可能となり、ネットワークリソースを効率的に運用できるとともに、各ルータ装置において個々のパケット毎に配送が遅れているのかあるいは進んでいるのかを知ることができる。
【0022】また、請求項4記載の発明では、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に通信パケットの発信時刻及び送達希望時刻を格納して作成した通信パケットを用いることを特徴とする。
【0023】前記構成によれば、既存のIPv6のパケットフォーマットを変更することなく、通信パケットに時間軸情報を付与することができる。
【0024】また、請求項5記載の発明では、処理能力以上の通信パケットにより輻輳が発生した場合、優先度が低い通信パケットをルータ装置内の記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して経路制御を再開させることを特徴とする。
【0025】前記構成によれば、トラヒック輻輳時におけるパケットの破棄を軽減することが可能となる。
【0026】また、請求項6記載の発明では、通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した時は待ち合わせの単位を変更することを特徴とする。
【0027】前記構成によれば、送達希望時刻までの残り時間に対応した適切な転送処理が可能となる。
【0028】また、請求項7記載の発明では、通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、前記単位毎の転送確率を、該単位毎の待ち合わせ中のパケット数に応じて変更することを特徴とする。
【0029】前記構成によれば、送達希望時刻までの残り時間に応じた待ち合わせ中のパケット数の極端な差をなくすことができる。
【0030】また、請求項8記載の発明では、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に、迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを格納して作成した通信パケットを用いることを特徴とする。
【0031】前記構成によれば、経路の変更が可能となり、また、通信パケットを待ち合わせなしで最優先で処理したり、また、送達希望時刻を越えた通信パケットをそのまま待ち合わせさせたり、廃棄したりを指示できる。
【0032】また、請求項9記載の発明では、ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを隣接するルータ装置間で交換し、前記情報に基づいて隣接するルータ装置までのメトリック値を求め、該求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更することを特徴とする。
【0033】前記構成によれば、ネットワークが込み合うような状況においても適応的なルーティングが可能となり、送達希望時刻を満たすパケットが著しく減少することを防止できる。
【0034】そして、これらの優先経路制御方法は、複数の入力ポート及び複数の出力ポートと、複数の入力ポート及び複数の出力ポート間を任意に切替接続可能な空間スイッチと、入力ポートから入力された通信パケットをその宛先アドレスに対応する出力ポートへ送出するよう空間スイッチを制御する経路制御部とを有するルータ装置において、複数の通信パケットの順序を任意に入れ替え可能な時間スイッチと、複数の通信パケットの順序が各通信パケットに付与された送達希望時刻に対応する順序となるよう時間スイッチを制御する優先制御部とを設けたルータ装置、通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定する手段を備えた請求項10記載のルータ装置、自装置のアドレス及び通信パケットの宛先アドレスより求められる自装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、時間スイッチを制御する優先制御部を備えた請求項10記載のルータ装置、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された通信パケットの発信時刻及び送達希望時刻を用いる優先制御部を備えた請求項10乃至12いずれか記載のルータ装置、通信パケットを一時的に記憶する記憶装置と、処理能力以上の通信パケットが入力されて輻輳が発生した場合、優先度が低い通信パケットを記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して優先経路制御を再開させる制御手段とを備えた請求項10乃至13いずれか記載のルータ装置、送達希望時刻までの残り時間の単位別に分割された時間スイッチと、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した一の時間スイッチ内の通信パケットを、該変化後の単位に対応する時間スイッチへ移す手段とを備えた請求項10乃至14いずれか記載のルータ装置、送達希望時刻までの残り時間の単位別に分割された時間スイッチと、前記単位毎の時間スイッチにおける通信パケットの取り出し確率を、該単位毎の時間スイッチにおける待ち合わせ中のパケット数に応じて変更する手段とを備えた請求項10乃至15いずれか記載のルータ装置、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを用いる優先制御部を備えた請求項10乃至16いずれか記載のルータ装置、ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを作成し、隣接するルータ装置間で交換する手段と、前記パケット内の情報に基づいて隣接するルータ装置までのメトリック値を計算する手段と、前記求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更する手段とを備えた請求項10乃至17いずれか記載のルータ装置、によって実現される。
【0035】
【発明の実施の形態】以下、本発明の優先経路制御方法及びルータ装置の実施の形態について、図面を参照して詳細に説明する。
【0036】図2は本発明の優先経路制御方法を用いたルータ装置の基本構成を示すもので、図中、21は複数の入力ポート、22はスイッチ部、23は複数の出力ポート、24は経路制御部、25は優先制御部、26は通信パケットである。
【0037】スイッチ部22は、複数の入力ポート21と複数の出力ポート23との間を自在に接続できる空間スイッチ27と、本ルータ装置に入力される通信パケットの出力順を並べ替え可能な時間スイッチ28とからなり、空間スイッチ27は経路制御部24により制御され、時間スイッチ28は優先制御部25により制御される。
【0038】本ルータ装置に入力される通信パケット26には、IPアドレスのようなネットワーク層の宛先アドレス26aの他、通信パケットの相手先の「送達希望時刻26b」が含まれる。図1に示したような空間スイッチのみからなる従来のルータ装置とは異なり、スイッチ部22を空間スイッチ27及び時間スイッチ28で構成し、宛先を示すネットワーク層アドレス(IPアドレス)26aに基づいた経路制御(空間スイッチの切り替え)に加え、新たに「送達希望時刻26b」に基づいて通信パケットの送出順を優先制御することにより、ネットワークリソースを有効利用できる。
【0039】なお、本発明でいう「送達希望時刻」とは、唯一の時点を示す時刻である場合とともに、ある時間幅を持つ場合(時間幅の指定方法としては、送達希望の開始時刻及び最終時刻を指定する、開始時刻または最終時刻と時間(予め取り決めておくことにより省略も可)を指定する等)も含むものとする。
【0040】以上が、請求項1及び10記載の発明についての説明である。
【0041】次に「送達希望時刻」に基づく通信パケットの優先制御の原理を図3により説明する。
【0042】図3では情報の伝達を時間軸及び空間軸からなる2次元空間上の移動と捉えて表現しており、該2次元空間の情報伝達ベクトルとして示している。即ち通信、情報の伝達とは、図3のような2次元空間上のある位置ベクトルから位置ベクトルへの空間ベクトルとして表現できる。
【0043】この時、時間軸要素は時刻であり、時刻自身を時間軸上のアドレスとして用いることができる。一方、空間軸要素はIPアドレス等のネットワーク層のアドレスであり、IPバージョン4(以下、「IPv4」と記す。)ならば32ビットの一次元空間であり、IPバージョン6(以下、「IPv6」と記す。)ならば128ビットの一次元空間である。
【0044】時刻が線形空間であるのに対し、IPアドレス空間は線形空間でないため、IPアドレス間の距離としてルータ装置間のメトリック値を用いる。
【0045】本発明では、情報の伝達を上記の時刻−ネットワーク層アドレスによる2次元空間上の空間ベクトルとして表現し、ベクトルの時間軸成分、空間軸成分、大きさ、偏角といった各要素により、通信パケットが運ぶ情報属性を分類し、ルータ装置内における処理の優先度等の差別化を図るようになしている。
【0046】図4は情報伝達の空間ベクトルの要素を示すものである。情報伝達の空間ベクトルzにおける始点=情報の出発点の時間軸成分は発信時刻ts、空間軸成分は送信元ネットワーク層アドレスssである。また、情報伝達の空間ベクトルにおける終点=情報の到着(希望)点の時間軸成分は情報の送達希望時刻(送達期限)td、空間軸成分は送達先ネットワークアドレスsdである。
【0047】空間軸上の移動距離|sd−ss|はルータ装置間メトリック値を基準にしたエンド−エンドのパケットの移動距離であり、時間軸上の移動距離|td−ts|はパケット発信時に要求された送達希望時刻までの残り(余裕)時間である。
【0048】これらに加え、情報伝達の大きさ|z|={(td−ts)2+(sd−ss)2}1/2は情報伝達のエンド−エンドでの時空間上の移動距離を表し、偏角Θz=arctan{|sd−ss|/|td−ts|}
は単位時間当たりの空間軸上の移動距離に対応している。
【0049】時空間上の移動距離が等しい場合でも、偏角Θzが大きい情報伝達は単位時間当たりより遠くへ伝達される必要があり、偏角Θzは通信コストあるいは通信料金の算出パラメータとして利用できる。また、偏角Θzの値が同一であっても、時空間上の移動距離|z|が大きければ、通過するルータ装置数や伝送距離が大きいことを意味するため、|z|も通信コストあるいは通信料金の算出パラメータとして利用できる。
【0050】これまでのデータリンクの伝送帯域や距離のみによる料金算出に代わり、空間軸の移動距離|sd−ss|、時間軸の移動距離|td−ts|や、時空間上のベクトルの大きさ|z|、偏角Θzといった個々のパラメータ、あるいはそれらの組み合わせによってパケット毎のより細かな課金が行えるようになる。
【0051】以上が、請求項2及び11記載の発明についての説明である。
【0052】また、図4中のyは通信途中のルータ装置における情報伝達の空間ベクトルを表している。この時、ベクトルの始点の時間軸成分はルータ装置内に情報が存在する時の現在時刻tcを表し、空間軸成分はルータ装置のネットワーク層アドレスscを表す。従って、yは通信途上のルータ装置から最終目的地までの情報伝達の空間ベクトルである。
【0053】|sd−sc|はルータ間メトリック値を元にした当該ルータ装置から相手先アドレスまでの残りの距離を表し、|td−tc|は現時点での送達期限までの残り(余裕)時間を表す。また、ベクトルの大きさ|y|={(td−tc)2+(sd−sc)2}1/2は通信パケットを処理する現在のルータ装置から最終到達点まで、時空間上でどれだけ移動距離が残っているかを表しており、偏角Θy=arctan{|sd−sc|/|td−tc|}
は送達希望時刻tdまでに情報を伝達し終わるために、今後、単位時間当たり空間軸上を移動しなければならない距離を表している。
【0054】これら情報伝達ベクトルの各成分|sd−sc|、|td−tc|、|y|、Θyのいずれか、あるいはこれらを組み合わせたものをパラメータとしてルータ装置はパケットルーティング処理の優先度を決定する。
【0055】次に、|y|やΘyによるルータ装置内の優先処理について、図3及び図4を参照して説明する。図3ではリアルタイムデータ転送とファイルデータ転送という2つの種類の異なる情報伝達を空間ベクトルとして表現している。リアルタイム転送では短時間のエンド−エンド情報伝達が要求されるため、ファイルデータ転送と比較してベクトルの偏角Θが大きい。
【0056】途中のルータ装置では、偏角Θyの大きなリアルタイムデータと偏角Θyの小さなファイルデータのいずれも処理しなければならない場合、偏角Θyの値により処理の優先度を決定するのであれば、ファイルデータをルータ装置内に蓄積し、待ち合わせを行うことで優先度の高いリアルタイムデータを先に処理・送出することが可能となる。
【0057】このように従来のルータ装置とは異なり、現在時刻と送達希望時刻の差異や空間軸上の残りの距離から上位レイヤの終端をすることなく、情報の属性に応じて処理の差別化を図ることが可能となり、ネットワークリソースを効率的に運用できる。
【0058】以上が、請求項3及び12記載の発明についての説明である。
【0059】また、送達希望時刻は、ルータ装置内での廃棄メカニズムの目安として捉えることもできる。例えば、ルータ装置内で、送達希望時刻を過ぎたパケットについてはこれを受信先へ送達しても意味の無い情報であると判断できるため(リアルタイムで再生されるストリームデータ等)、輻輳状態に至らなくともルータ装置内で積極的に廃棄することができる(ルータ装置における現在時刻tc>送達希望時刻tdの場合)。
【0060】また、偏角Θは現在時刻tcの関数であるため、初期値Θzとルータ装置内での現在値Θyを比較することで、通信パケットの送達が予定より遅れているか、進んでいるかを判断することができ、これをルータ装置内での処理の優先度に反映させることも可能となる。
【0061】以上が、請求項3及び8記載の発明についての補足説明である。
【0062】図5はIPv6における時間軸情報の格納例を示すものである。空間軸成分、即ち送信元IPアドレスss及び宛先のIPアドレスsdはIPv6ヘッダとしてそれぞれ128bitで表現されている。時間軸成分、即ち発信時刻tsと、送達希望時刻tdはIPv6ヘッダの後に続く中継点オプションヘッダを用いて、これらをそれぞれ32bitで表現し、格納する。
【0063】IPv6におけるヘッダ処理の優先度は、IPv6ヘッダ>中継点オプションヘッダ(hop−by−hop options header)>終点オプションヘッダ(destination options header)>経路制御ヘッダ(routing header)>断片ヘッダ(fragmentheader)>認証ヘッダ(authentication header)>暗号ペイロード(encapsulating security payload)>終点オプションヘッダ>上位層ヘッダ(TCPあるいはUDP等)であり、中継点オプションヘッダは、オプションヘッダとしては最も高い優先度で処理される。
【0064】この時、先頭のIPv6ヘッダ内の次ヘッダ番号には中継点オプションヘッダ(HBH)を表現する「0」が入る。発信時刻、送達希望時刻を格納する中継点オプションヘッダの次ヘッダ番号には次に続くヘッダが例えば、TCPヘッダであれば「6」という値が格納される。
【0065】拡張ヘッダ長は当該中継点オプションヘッダ長(128ビット)を8バイト単位(64ビット)で表現して−1した値、即ち「1」が入る。
【0066】オプション番号は8ビットの識別子であり、上位2ビットでルータ装置がオプションを認識できなかった場合の動作を示し、次の1ビットでオプションが配送経路上で変更可能かどうかを表し、下位5ビットはオプションの内容を示すオプション番号部分となる。本ルータ装置で用いるIPv6ヘッダの場合、動作は「00」(認識できない場合は続み飛ばすという意)、経路上変更可能ビットは「OFF」、オプション番号部分については、IANA(Internet Assigned Numbers Authority)に登録することによってRFCに記述される新しい番号を入れる。オプションデータ長は当該オプションデータ長をバイト表現したもので「12」が入る。
【0067】その後には発信時刻ts及び送達希望時刻tdが、情報伝達ベクトルの始点及び終点アドレスとして32ビットずつ格納される。中継点オプションヘッダの最後の4バイトは時刻情報の単位等の付加情報の格納用として予約するが、時刻情報の単位をミリ秒(ms)、秒(s)、時間(hour)のように3段階で荒く表現する場合はIPv6ヘッダの優先度(4ビット)を利用して時刻情報の単位を表して(格納して)も良い。
【0068】以上が、請求項4及び13記載の発明についての説明である。
【0069】IPv6の中継点オプションヘッダを用いることで既存のIPv6のパケットフォーマットを変更せずに時間軸成分を運ぶことができ、従来の時間軸成分を情報として持たない既存のパケットと同等に処理することも可能となる。
【0070】また、パケットに格納される発信時刻や送達希望時刻は、例えばMPEGファイルのような等時性(アイソクロナス性)情報を運ぶ際の再生タイミングを表現していると言える(MPEGのTSフレームのような)。即ち、通信パケットに添付されている送達希望時刻は受信先でアイソクロナスデータを再生するタイムスタンプとして利用できるため、ネットワークは遅延の揺らぎを抑えるといったアイソクロナス性保証のための転送メカニズムを実装する必要がなくなる。
【0071】さらに、送達希望時刻は通信パケットの絶対的なシーケンス番号とみなすことも可能であり、元情報を再構成することが可能であるため、ネットワークは通信パケット到着の順序性を保証する必要がなくなり、ルータ装置はより簡便な転送メカニズムを実装できる。
【0072】以上が、請求項4及び13記載の発明についての補足説明である。
【0073】次に、本発明のルータ装置の具体例について説明する。
【0074】図6はルータ装置の全体構成を示すもので、同図(a)は全体斜視図、同図(b)は配線図である。図中、31A,31B,31C,31Dは全二重通信路を有しかつ図2で述べた経路制御部、優先制御部及び時間スイッチを構成する入出力部、32はディスクアレイ用コンピュータ(PC)、33は入出力部31A〜31D及びディスクアレイ用PC32間を空間的にスイッチングするスイッチ(SW)部、34は制御用コンピュータ(PC)、35はこれらを接続する専用バックプレーン、36はディスクアレイである。
【0075】制御用PC34には他のルータ装置との間でリンクステート情報をやり取りするルーティングプロトコルが実装され、ルータ装置間の空間軸上の距離を測定する如くなっている。
【0076】前述した入出力部31A〜31Dは全て同一構成であり、図7にその詳細構成の一例、ここではネットワークとのデータのやりとりを光信号で行うようになした場合の例を示す。図中、311aは光入力部(Opt in)、311bは光出力部(Opt out)、312はシリアル・パラレル変換器(S/P)、313はデータリンク層終端部、314はFPGA(Field Programmable Gate array)、315は信号処理プロセッサ(DSP)、316a,316b,316cはシンクロナスSRAM(SSRAM)等からなる高速メモリ、317は連想メモリ(Content Addressable Memory:CAM)、318はシンクロナス(sync.)FIFOメモリ、319はインタフェース部(I/F)である。
【0077】以下、入出力部が前述した経路制御部、優先制御部及び時間スイッチを構成するようすをその動作概要とともに説明する。
【0078】図示しないネットワークから光ファイバを介して届いたパケットデータは、光入力部311aで光電変換され、S/P312でシリアル・パラレル変換された後、ギガビットイーサネット(Gigabit Ethernet)等のデータリンク層終端部313を経てIPデータグラムとして取り出され、FPGA314において時間軸成分の精度(単位)により振り分けられる。
【0079】ここで、時間軸成分の表示単位は、図5に示したようにIPv6ヘッダの優先度あるいは時間軸成分を格納する中継点オプションヘッダの末尾部分に格納されている。図7の例では、時間軸成分の単位をミリ秒(ms)、秒(s)、時間(hour)の3段階に分類している。
【0080】FPGA314により時間軸成分の表示単位毎に分類されたデータはIPデータグラムのまま、ミリ秒(ms)用,秒(s)用,時間(hour)用の高速メモリ316a,316b,316cへ格納される。この時、IPデータグラムはメモリ内に順に格納され、メモリはリングバッファとして利用される。
【0081】一方、高速メモリ316a〜316cへ格納されるIPデータグラムのヘッダ部(中継点オプションヘッダを含む。)は、経路計算及び情報伝達ベクトルの偏角Θy計算用のDSP315へ渡される。
【0082】DSP315はIPヘッダの相手先アドレスsdから経路を計算し、当該パケットをどの方路から送出すべきか、即ちSW部33を介して次にどの入出力部へ送出すべきかを決定する。
【0083】この方路情報は、時間軸成分の単位、高速メモリ316a〜316cへIPパケットを格納した際のライトアドレス(wp)とともにCAM317へ格納される。この時、{方路、単位、wp}を格納するCAM317のライトアドレスはDSP315で計算されたΘyの逆数を用いる。
【0084】CAM317は通常のメモリとは異なり、アドレスを与えて格納されているデータへアクセスするのではなく、検索ワードを与え、これに一致するデータが格納されているアドレスを知るというメモリである。
【0085】例えば、CAM317に検索ワードとして、方路及び単位を与えることで、特定の方路及び単位の情報だけを取り出すことができる。方路及び単位が一致する情報が複数格納されている場合、CAM317は格納されているデータの中から最小アドレスを返すため、{方路、単位、wp}を格納するCAM317のライトアドレスにΘyの逆数を用いることで、特定方路行きの特定単位の最大Θy情報、即ち最大Θyを持つIPデータグラムの高速メモリ316a〜316cへの格納位置wpを知ることができる。
【0086】こうして得られたwpを高速メモリ316a〜316cのリードアドレス(rp)に用いることで、常に特定方路行きの特定単位の最大Θyを持つIPデータグラムを高速メモリ316a〜316cから取り出すことができる。
【0087】このようにしてIPデータグラムの中から取り出された、最大のΘyとなるIPデータグラムはI/F319を経て、バックプレーン35を介してSW部33へ転送される。
【0088】一方、SW部33からバックプレーン35を介して到着したIPデータグラムは、I/F319を経てSync.FIFOメモリ318で受信される。Sync.FIFOメモリ318に格納されたIPデータグラムは順次、データリンク層終端部313、S/P312、光出力部311bへ送られ、光信号に変換されてネットワークへ送出される。
【0089】図8は前述したスイッチ部(SW部)の詳細構成を示すもので、同図(a)は回路構成図、同図(b)は切替接続の説明図である。図中、331は高速クロスバスイッチチップで構成される5×5スイッチ構成のクロスバスイッチであり、その5つの入力ポート及び出力ポートには4つの入出力部31A〜31Dとともに、ディスクアレイ用PC32が接続されている。また、332は切替制御用のCPUであり、クロスバスイッチ331を、タイミングを管理しつつ、同図(b)に示すような各入出力ポートのl対1接続を全て網羅する5つのフェーズに切り替え制御する如くなっている。なお、フェーズとフェーズとの間にはガードタイムが設定されている。
【0090】ディスクアレイ用PC32は、送達希望時刻tdが∞(無限大)に設定されているような優先度の低いIPデータグラムを格納するための大容量の記憶装置、ここではディスクアレイ36を制御するためのものである。
【0091】送達希望時刻までの余裕が大きい場合や、送達希望時刻が無限大に設定されているような通信パケットは、入出力部31A〜31DからSW部33及びPC32を介して、一旦、ディスクアレイ36に蓄積され、然るべき時間経過を待ってPC32及びSW部33を介して再度、入出力部へ読み出される。
【0092】この際、送達希望時刻を無限大に設定することにより、時刻を問わず送達して構わないデータであることを指定できるので、ルータ装置内の記憶装置に蓄積しながら、確実に伝達されるという情報伝達サービスクラスを新たに定義することができる。また、トラフィック輻輳時においても低優先度パケットを廃棄するのではなく、記憶装置に待避させることができるため、パケット廃棄率を改善でき、その結果、エンド−エンドの簡便な送達確認メカニズムを持つトランスポートレイヤにより信頼性の高いデータ転送が実現できる。
【0093】以上の説明のうち、ディスクアレイ36にデータを退避させる点が、請求項5及び14記載の発明と対応している。
【0094】ところで、前述した実施の形態において、高速メモリ316a〜316cへのパケットデータの格納は、時間軸成分の単位(ミリ秒、秒、時間)毎に単純に受信した順に行われ、また、高速メモリ316a〜316cからのパケットデータの取り出しは、方路毎及び時間軸成分の単位毎に単純に優先度(Θy)の高い順に行われていた。
【0095】従って、ネットワークが込み合うような状況下において、ある時間軸成分の単位、例えば時間(h)に対応したメモリ316c内に格納されたパケットデータの送達希望時刻までの残り(余裕)時間が少なくなったりしても、他のメモリ316a,316b内のパケットデータの転送が優先され、その結果、メモリ316cに格納されたパケットデータの送達希望時刻が守られなくなる場合があり得るという問題があった。
【0096】図9は前述した点を改良した本発明のルータ装置の実施の形態の他の例の要部、ここでは高速メモリ316a〜316cに対するパケットデータの格納(キューイング:queuing)及び取り出し制御にかかわる部分を示すものである。
【0097】本実施の形態では、各高速メモリ316a〜316c内におけるパケットデータのキューイングを優先度(Θy)順に行うとともに、待ち合せ等によって送達希望時刻までの残り時間の単位(オーダ)が変化した場合にはキューイングするメモリそのものを変更する。また、パケットデータの取り出しは高速メモリ316a〜316c毎に優先度の高いものから行うが、各高速メモリ316a〜316cからの取り出し(転送)確率(割合)を、キューイングしているデータ量に応じて変化させる。
【0098】前述した各高速メモリ316a〜316c内におけるパケットデータの優先度順のキューイングは、連想メモリ317から優先度順に取り出されるアドレスによって並べ替えることにより実現され、優先度(Θy)が高いものほど各高速メモリ316a〜316cの先頭(出口)に近く、低いものほど後尾(入口)に近くなるように配列される。
【0099】各高速メモリ316a〜316cに格納されたパケットデータは、それぞれのメモリ内で優先度の高いもの、即ちA、B、Cから取り出される。
【0100】この際、長時間の待ち合わせ等により送達希望時刻までの残り時間のオーダが変化してしまった場合、例えばオーダが時間(h)のメモリ316c内のパケットCの送達希望時刻までの残り時間が59分59秒以下になった場合、オーダ遷移制御部41によりc1のルートを通って速やかに秒(s)のメモリ316bの最後尾に移る。また、同様にオーダが秒(s)のメモリ316b内のパケットBの送達希望時刻までの残り時間が999ms以下になった場合、オーダ遷移制御部41によりb1のルートを通ってミリ秒(ms)のメモリ316aの最後尾に移る。これは連想メモリ317における時間軸成分の単位のビットを書き替えることにより実現される。
【0101】また、各高速メモリ316a〜316cからのパケットデータの取り出しに関しては取り出し制御部42によって、さらに詳細に制御される。
【0102】即ち、取り出し制御部42は各メモリ316a〜316c内の格納パケットデータ数(キューの長さ)の変動を観測しており、それによりメモリ316a〜316c毎の取り出し確率を変化させる。但し、取り出し確率は0<確率<lの範囲での変動とし、待ち合わせ及び到着パケットの全くないメモリが存在しない限り、特定のメモリのみから取り出したり、特定のメモリに関して全く取り出さなかったりということはない。
【0103】図10、図11はパケットの受信時のキューイング及びオーダ遷移制御アルゴリズムを表すフローチャートである。また、図12〜図14はパケット送信時の取り出し制御アルゴリズムを表すフローチャートである。
【0104】以上が、請求項6、7及び15、16記載の発明についての説明である。
【0105】図15は図5と同様、IPv6における時間軸情報の他の格納例を示すものである。ここで、送達希望時刻としてtd1,td2という2種類が存在するが、これは送達希望時刻としてtd1より後、td2より前という指定を可能とするものである。即ち、図5と同様のtdの扱いにするためにはtd1=0とすれば良く、また、td1=td2とした場合は、ちょうどその時刻に送達されるようにパケットの転送を行う。
【0106】また、送信先が込み合っている場合等で迂回を行う時、パケットループを防ぐために迂回元のルータIDを記述する。迂回していない場合は「0」である。この変更を行うため、オプションタイプの経路上変更可能ビットは図5と異なり、「1」となる。
【0107】さらに優先度及び時刻tdのオーダのフィールドを設ける。優先度が「1」の場合、最も優先度が高いものとして、ルータが受信したパケットはキューイングを行わずに素早く次のルータへ送る。この場合、送達希望時刻のフィールドは参照せず、従って優先度Θの計算も行わない。「0」の場合は通常通り、送達希望時刻のオーダ毎のキューイングを行う。
【0108】また、このフィールド最後のビットを用いて、送達希望時刻を越えたパケットの扱いを指定する。「1」の場合は送達希望時刻を越えても捨てずに配送を行う。「0」の場合は送達希望時刻を越えたパケットは廃棄する。
【0109】以上が、請求項8及び17記載の発明についての説明である。
【0110】また、これまでの説明におけるルーティングプロトコルでは、固定的なメトリック値を用いており、ネットワークを流れるトラフィックの変動に起因する、利用可能帯域の変動等による目的地までの処要時間の変化に対して有効な対策を取り得ない。即ち、途中のルータが動作不能になる等、パケットが到達不能にならない限り、輻輳により転送効率が落ち、パケットロスが発生し始めても、ルーティングテーブル作成時に「最短である」とみなされた経路を採り続けるという問題が生じる。このため、ネットワークのトラフィック状況によっては送達希望時刻を満たすパケットが著しく減少する可能性がある。
【0111】前述した問題は隣接するルータ装置間でネットワーク状況に関する情報を交換し、メトリック値を動的に変更可能とすることにより解決できる。
【0112】図16はAS(Autonomous System:自律システム)内のルーティング情報の伝播の一例として、OSPF(Open ShortestPath First)のLSA(Link State Advertisement)パケットにおける隣接ルータとの交換情報の格納例である。
【0113】詳しい情報の交換は隣接ルータとのみ行うため、flooding scopeはLink Localである。ここでいうCLASSはキュー(高速メモリ)の数と一致しており、ms,s,hの3つのキューを持つのであればCLASS=3となる。
【0114】また、低優先度のパケットを退避させるため、大容量の半導体メモリ及びハードディスクをストレージとして用いる場合は、その後のSTRビットを立てる。また、if_numはルータに挿してあるインタフェースの総数である(但し、コミュニケーションポート等、管理の時にしか使用しないインタフェースは除く。)。qlen_usedは各キュー内にキューイングされているパケット数であり、qlen_unusedは各キューの空き、即ち格納可能なパケット数を示している。
【0115】mbuf_used、mbuf_unusedはそれぞれメモリバッファの使用量、空き容量をbytes単位で表す値である。同様にmemory_used、memory_unused及びdisk_used、disk−unusedもストレージに関する使用量、空き容量をKbytes単位で表す値である。これらのパケット数、容量は測定時の瞬間的な値ではなく、ある時間区間毎の平均値である。
【0116】さらにtr_ifはインタフェース毎の情報をメンバに持つ構造体である。tr_if.interface_idはルータ内でインタフェースを一意に識別するIDであり、tr_if.if_baudrateはインタフェースの物理速度を示す。
【0117】tr_if.statisticsは一秒あたりのそのインタフェースを経由してルータ内に入ってきたパケットのbytes数を示す。point−to−pointのリンクであれば、この数値がリンクの使用状況を示し、また、point−to−multipointのリンクであれば、リンク上の全てのルータのstatisticsを集計したものがリンクの使用状況となる。
【0118】tr_if.route_numはそのリンク上の隣接ルータの数である。tr_if.router_idは隣接ルータのidであり、tr_if.rttはその隣接ルータまでの往復にかかる時間RTT(Round Trip Time)である。
【0119】これらの情報を隣接ルータ間で交換し、隣接ルータまでのメトリック値をそれぞれ計算する。その際、各ルータへのメトリック値をms,s,h用にそれぞれ3種類計算する。この計算式は得られた情報の関数として計算される。よってメトリック値は動的なものとなり、このうちmsのメトリック値を代表値としてAS内全てのルータにfloodingにより配布する。このメトリック値を図3における空間アドレス上の距離に相当するものとしてΘyを計算する。
【0120】ここで、ルータCに対し隣接ルータAから送られる交換情報が構造体Aのメンバとして与えられたとし、ルータA内のmsのキューに存在するパケット数の平均値及び格納可能なパケットの数の平均値がそれぞれA.qlen_used[0]及びA.qlen_unused[0]、また、同様にA内のメモリバッファの使用量及び残容量がそれぞれA.mbuf_used及びA.mbuf_unused、さらにルータAとのRTTがA.RTT、ルータAが存在するリンクの物理速度をA.if_baudrate、ルータAが存在するリンク上のルータCに対する全ての隣接ルータより得た使用状況から算出した当該リンクの使用状況をA.statisticsとして与えられたとすると、これらを用いて隣接ルータAへのmsにおけるメトリック値|SA−SC|msを表すと、|SA−SC|ms=f(A.qlen_used[0],A.qlen_unused[0],A.mbuf_used,A.mbuf_unused,A.rtt,A.if_baudrate,A.statistics)
となる。以下、同様にs,hにおけるメトリック値は、|SA−SC|s=g(A.qlen_used[1],A.qlen_unused[1],A.mbuf_used,A.mbuf_unused,A.memory_used,A.memory_unused,A.rtt,A.if_baudrate,A.statistics)
|SA−SC|h=h(A.qlen_used[2],A.qlen_unused[2],A.mbuf_used,A.mbuf_unused,A.disk_used,A.disk_unused,A.rtt,A.if_baudrate,A.statistics)
となる。
【0121】f(),g(),h()の具体例として、以下の数式を示す。
【0122】|SA−SC|ms={αms(A.qlen_used[0]+βmsA.qlen_unused[0])+γms(A.mbuf_used+δmsA.mbuf_unused)}・A.rtt/{1・1・(A.if_baudrate−A.statistics)}
|SA−SC|s={αs(A.qlen_used[1]+βsA.qlen_unused[1])+γs(A.mbuf_used+δsA.mbuf_unused)+εs(A.memory_used+ζsA.memory_unused)}・A.rtt/{1・1・(A.if_baudrate−A.statistics)}
|SA−SC|h={αh(A.qlen_used[2]+βhA.qlen_unused[2])+γh(A.mbuf_used+δhA.mbuf_unused)+εh(A.disk_used+ζhA.disk_unused)}・A.rtt/{1・1・(A.if_baudrate−A.statistics)}
上式中、1は全て1秒を表しており、それぞれの式を無次元化するために挿入してある。また、αは平均パケットサイズ、β〜ζは全て実定数であり、γ,εに関しては正、β,δ,ζに関しては負である。
【0123】このms,s,hにおける3種のメトリック値を用い、それぞれでルーティングテーブルを作成する。但し、他のルータに配布するメトリック値は前述の通りmsのメトリック値のみであり、逆に他のルータから配布されてくるメトリック値もmsのもののみである。即ち、3種のメトリック値は自ルータから隣接ルータまでのメトリック値のみであり、s,hのメトリック値によるルーティングテーブルは迂回に用いる。
【0124】即ち、代表として他のルータに配布するmsのメトリック値を最適なパスとして通常用いるが、そのパスが込み合ってきた場合、s,hのオーダのキューにあるパケットに関してはs,hのメトリック値によるルーティングテーブルを参照し、迂回が可能であれば迂回を行う。その際、図15に示したIPv6の中継点オプションヘッダ内に迂回元ルータIDを記述する。
【0125】以上が、請求項9及び18記載の発明についての説明である。
【0126】
【発明の効果】以上説明したように、本発明によれば、以下のような効果を得ることができる。
【0127】即ち、請求項1記載の発明によれば、個々の通信パケットを送達希望時刻に応じた順序で経路制御でき、リアルタイム性の高いデータから低いデータまで最適な優先度でルーティング処理できるとともに、ネットワークリソースを有効活用できる。
【0128】また、請求項2記載の発明によれば、データリンクの伝送帯域・距離のみによる課金処理に代えて、空間軸あるいは時間軸における情報の移動距離に基づいて個々のパケット毎にきめ細かい課金を行うことができる。
【0129】また、請求項3記載の発明によれば、上位レイヤを終端することなく、情報の属性に応じて処理の差別化を図ることが可能となり、ネットワークリソースを効率的に運用でき、また、各ルータ装置において、個々のパケット毎に配送が遅れているのか、あるいは進んでいるのかを知ることができる。
【0130】また、請求項4記載の発明によれば、既存のIPv6のパケットフォーマットを変更することなく、通信パケットに時間軸情報を付与することができる。
【0131】また、請求項5記載の発明によれば、トラヒック輻輳時においてパケットの破棄を軽減することが可能となる。
【0132】また、請求項6記載の発明によれば、送達希望時刻までの残り時間に対応した適切な転送処理が可能となり、可能な限り送達希望時刻を満たすような配送が可能となる。
【0133】また、請求項7記載の発明によれば、送達希望時刻までの残り時間に応じた待ち合わせ中のパケット数の極端な差をなくすことができ、可能な限り送達希望時刻を満たすような配送が可能となる。
【0134】また、請求項8記載の発明によれば、経路の変更が可能となり、また、通信パケットを待ち合わせなしで最優先で処理したり、また、送達希望時刻を越えた通信パケットをそのまま待ち合わせさせたり、廃棄したりを指示できる。
【0135】また、請求項9記載の発明によれば、ネットワークが込み合うような状況においても適応的なルーティングが可能となり、送達希望時刻を満たすパケットが著しく減少することを防止できる。
【0136】また、請求項10乃至18の発明によれば、前述した優先経路制御を実行可能なルータ装置を提供できる。
【図面の簡単な説明】
【図1】従来のルータ装置の一例を示すブロック構成図
【図2】本発明のルータ装置の基本構成を示すブロック構成図
【図3】送達希望時刻に基づく通信パケットの優先制御の原理の説明図
【図4】情報伝達の空間ベクトルの要素の説明図
【図5】IPv6における時間軸情報の格納例の説明図
【図6】本発明のルータ装置の実施の形態の一例を示す構成図
【図7】図6中の入出力部の詳細構成図
【図8】図6中のスイッチ部の詳細構成図
【図9】本発明のルータ装置の実施の形態の他の例の要部を示す構成図
【図10】パケット受信時のキューイング及びオーダ遷移制御アルゴリズムを表すフローチャート
【図11】パケット受信時のキューイング及びオーダ遷移制御アルゴリズムを表すフローチャート
【図12】パケット送信時の取り出し制御アルゴリズムを表すフローチャート
【図13】パケット送信時の取り出し制御アルゴリズムを表すフローチャート
【図14】パケット送信時の取り出し制御アルゴリズムを表すフローチャート
【図15】IPv6における時間軸情報の他の格納例の説明図
【図16】LSAパケットにおける隣接ルータ装置との交換情報の格納例の説明図
【符号の説明】
21:入力ポート、22:スイッチ部、23:出力ポート、24:経路制御部、25:優先制御部、26:通信パケット、26a:宛先アドレス、26b:送達希望時刻、27:空間スイッチ、28:時間スイッチ、31A,31B,31C,31D:入出力部、32:ディスクアレイ用PC、33:スイッチ(SW)部、34:制御用PC、35:バックプレーン、36:ディスクアレイ、311a:光入力部(Opt in)、311b:光出力部(Opt out)、312:シリアル・パラレル変換器(S/P)、313:データリンク層終端部、314:FPGA、315:信号処理プロセッサ(DSP)、316a〜316c:高速メモリ、317:連想メモリ(CAM)、318:シンクロナス(sync.)FIFOメモリ、319:インタフェース部(I/F)、331:クロスバスイッチ、332:制御用CPU、41:オーダ遷移制御部、42:取り出し制御部。
【0001】
【発明の属する技術分野】本発明は、通信パケットを高速かつ効率良くルーティング可能な優先経路制御方法及びルータ装置に関するものである。
【0002】
【従来の技術】電気通信の分野において、通信ネットワークを介して情報を効率良く交換・伝送するために、交換機(exchange)やルータ(router)等の経路制御装置(以下、「ルータ装置」と呼ぶ。)が用いられる。このルータ装置は、特に、インターネットを介した情報データ通信で広く用いられており、インターネットを構成する上で重要な役割をはたしている。以下、図1を参照して、従来のルータ装置について説明する。
【0003】図1は従来のルータ装置の一例を示すもので、図中、11は複数の入力ポート、12はスイッチ部、13は複数の出力ポート、14は経路制御部、15は通信パケットである。
【0004】次に、従来のルータ装置の動作について図1R>1を参照して説明する。
【0005】入力ポート11から入力された通信パケット15は、スイッチ部12に入力される。それぞれの通信パケット15にはパケットの宛先を示す宛先アドレス(例えばインターネットプロトコル(以下、「IP」と記す。)で用いられているIPアドレス)15aが付加されており、スイッチ部12を制御する経路制御部14はこの宛先アドレス15aに基づいて、通信パケット15をどの出力ポート13から出力すべきかを判断する。
【0006】スイッチ部12は空間スイッチ16から構成されており、通信パケット15から宛先アドレス15aを取り出して経路制御部14に問い合わせると、経路制御部14はルーティングテーブルを検索し、通信パケット15をどの出力ポート13にスイッチングすれば良いかを得て、その結果を空間スイッチ16に返し、空間スイッチ16がこの結果を受けて通信パケット15をスイッチングする。
【0007】スイッチ部12によって目的の出力ポート13にスイッチングされた通信パケット15は、出力ポート13から出力される。
【0008】入力ポート11から同じ宛先への通信パケットが大量に入力された場合、空間スイッチ16において輻輳が発生し、通信パケットは破棄される。
【0009】
【発明が解決しようとする課題】ルータ装置の役割は、入力された通信パケットをルーティング処理して出力することであって、従来のルータ装置では、経由する通信量が少なければ小さい遅延でルーティング可能であるが、通信量が多ければ遅延が大きくなり、また、空間スイッチの許容能力を越える通信パケットが入力されると、通信パケットを破棄する。即ち、従来のルータ装置は、通信パケットを転送するために最大限の努力をするが、処理能力の限界や通信回線の速度限界によって通信できないこともあるという、ベストエフォート型のネットワークを提供する。
【0010】電話の音声データや放送の動画像データ等は、リアルタイム性の高いデータであり、通信の遅延時間に大きなゆらぎが発生したり、通信パケットに欠落が生じると、受信側において正確なデータ再生ができなくなる。このため、これまでは、リアルタイム性の高いデータに対して「帯域保証」という概念の下、予め必要な通信路の帯域を確保して通信を行うようになしていた。
【0011】しかし、帯域確保を行う場合、(a)送受信者間の全ての回線で帯域を確保しなければならない、(b)通信量が変動する場合、その最大値で帯域を確保しなければならないため、帯域利用効率が悪くなる、(c)ルータ装置において帯域確保のための処理負荷が大きい、という問題があった。
【0012】以上のことから、帯域確保という手段によってリアルタイム性の高いデータを確実に届けることは可能であるが、多くの問題を抱えていた。
【0013】また、帯域保証の他に、個々の通信パケット毎に優先度が高いか低いかを表す値を付加し、リアルタイム性の高い通信パケット等を優先度の高い通信パケットとしてルーティングを行わせることにより、信頼性を向上させる方法もある。
【0014】しかし、この場合、優先度の高い通信パケットは通過する全てのルータ装置において優先的に扱われ、逆に優先度の低い通信パケットは全てのルータ装置において優先度が低く扱われてしまうことになる。即ち、通信パケットの重要の度合いが優先度が高いか低いかという固定的なパラメータで表されるため、優先度の高い通信パケットは必要以上に優先処理されるという状況が生じ、また、通信料金も一律に高くつくという問題があった。
【0015】本発明の目的は、このような問題を解決し、帯域確保を行うことなく、リアルタイム性の高いデータからリアルタイム性を問わないバルクデータまでの幅広いデータを最適な優先度でルーティング処理でき、ネットワークの帯域利用効率を向上可能な優先経路制御方法及びルータ装置を提供することにある。
【0016】
【課題を解決するための手段】上記目的を達成するため、請求項1記載の発明では、通信パケット毎にラベル付けされた宛先アドレスに基づいて、通信パケットの経路を切替制御して送り出す経路制御方法において、宛先アドレスとともに送達希望時刻をラベル付けし、この送達希望時刻に基づいてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする。
【0017】前記構成によれば、個々の通信パケットを送達希望時刻に応じた順序で経路制御でき、リアルタイム性の高いデータから低いデータまで最適な優先度でルーティング処理できるとともに、ネットワークリソースを有効活用できる。
【0018】また、請求項2記載の発明では、通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定することを特徴とする。
【0019】前記構成によれば、データリンクの伝送帯域・距離のみによる課金処理に代えて、空間軸あるいは時間軸における情報の移動距離に基づいて個々のパケット毎にきめ細かい課金を行うことができる。
【0020】また、請求項3記載の発明では、ルータ装置のアドレス及び通信パケットの宛先アドレスより求められるルータ装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする。
【0021】前記構成によれば、上位レイヤを終端することなく、情報の属性に応じて処理の差別化を図ることが可能となり、ネットワークリソースを効率的に運用できるとともに、各ルータ装置において個々のパケット毎に配送が遅れているのかあるいは進んでいるのかを知ることができる。
【0022】また、請求項4記載の発明では、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に通信パケットの発信時刻及び送達希望時刻を格納して作成した通信パケットを用いることを特徴とする。
【0023】前記構成によれば、既存のIPv6のパケットフォーマットを変更することなく、通信パケットに時間軸情報を付与することができる。
【0024】また、請求項5記載の発明では、処理能力以上の通信パケットにより輻輳が発生した場合、優先度が低い通信パケットをルータ装置内の記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して経路制御を再開させることを特徴とする。
【0025】前記構成によれば、トラヒック輻輳時におけるパケットの破棄を軽減することが可能となる。
【0026】また、請求項6記載の発明では、通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した時は待ち合わせの単位を変更することを特徴とする。
【0027】前記構成によれば、送達希望時刻までの残り時間に対応した適切な転送処理が可能となる。
【0028】また、請求項7記載の発明では、通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、前記単位毎の転送確率を、該単位毎の待ち合わせ中のパケット数に応じて変更することを特徴とする。
【0029】前記構成によれば、送達希望時刻までの残り時間に応じた待ち合わせ中のパケット数の極端な差をなくすことができる。
【0030】また、請求項8記載の発明では、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に、迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを格納して作成した通信パケットを用いることを特徴とする。
【0031】前記構成によれば、経路の変更が可能となり、また、通信パケットを待ち合わせなしで最優先で処理したり、また、送達希望時刻を越えた通信パケットをそのまま待ち合わせさせたり、廃棄したりを指示できる。
【0032】また、請求項9記載の発明では、ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを隣接するルータ装置間で交換し、前記情報に基づいて隣接するルータ装置までのメトリック値を求め、該求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更することを特徴とする。
【0033】前記構成によれば、ネットワークが込み合うような状況においても適応的なルーティングが可能となり、送達希望時刻を満たすパケットが著しく減少することを防止できる。
【0034】そして、これらの優先経路制御方法は、複数の入力ポート及び複数の出力ポートと、複数の入力ポート及び複数の出力ポート間を任意に切替接続可能な空間スイッチと、入力ポートから入力された通信パケットをその宛先アドレスに対応する出力ポートへ送出するよう空間スイッチを制御する経路制御部とを有するルータ装置において、複数の通信パケットの順序を任意に入れ替え可能な時間スイッチと、複数の通信パケットの順序が各通信パケットに付与された送達希望時刻に対応する順序となるよう時間スイッチを制御する優先制御部とを設けたルータ装置、通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定する手段を備えた請求項10記載のルータ装置、自装置のアドレス及び通信パケットの宛先アドレスより求められる自装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、時間スイッチを制御する優先制御部を備えた請求項10記載のルータ装置、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された通信パケットの発信時刻及び送達希望時刻を用いる優先制御部を備えた請求項10乃至12いずれか記載のルータ装置、通信パケットを一時的に記憶する記憶装置と、処理能力以上の通信パケットが入力されて輻輳が発生した場合、優先度が低い通信パケットを記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して優先経路制御を再開させる制御手段とを備えた請求項10乃至13いずれか記載のルータ装置、送達希望時刻までの残り時間の単位別に分割された時間スイッチと、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した一の時間スイッチ内の通信パケットを、該変化後の単位に対応する時間スイッチへ移す手段とを備えた請求項10乃至14いずれか記載のルータ装置、送達希望時刻までの残り時間の単位別に分割された時間スイッチと、前記単位毎の時間スイッチにおける通信パケットの取り出し確率を、該単位毎の時間スイッチにおける待ち合わせ中のパケット数に応じて変更する手段とを備えた請求項10乃至15いずれか記載のルータ装置、インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを用いる優先制御部を備えた請求項10乃至16いずれか記載のルータ装置、ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを作成し、隣接するルータ装置間で交換する手段と、前記パケット内の情報に基づいて隣接するルータ装置までのメトリック値を計算する手段と、前記求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更する手段とを備えた請求項10乃至17いずれか記載のルータ装置、によって実現される。
【0035】
【発明の実施の形態】以下、本発明の優先経路制御方法及びルータ装置の実施の形態について、図面を参照して詳細に説明する。
【0036】図2は本発明の優先経路制御方法を用いたルータ装置の基本構成を示すもので、図中、21は複数の入力ポート、22はスイッチ部、23は複数の出力ポート、24は経路制御部、25は優先制御部、26は通信パケットである。
【0037】スイッチ部22は、複数の入力ポート21と複数の出力ポート23との間を自在に接続できる空間スイッチ27と、本ルータ装置に入力される通信パケットの出力順を並べ替え可能な時間スイッチ28とからなり、空間スイッチ27は経路制御部24により制御され、時間スイッチ28は優先制御部25により制御される。
【0038】本ルータ装置に入力される通信パケット26には、IPアドレスのようなネットワーク層の宛先アドレス26aの他、通信パケットの相手先の「送達希望時刻26b」が含まれる。図1に示したような空間スイッチのみからなる従来のルータ装置とは異なり、スイッチ部22を空間スイッチ27及び時間スイッチ28で構成し、宛先を示すネットワーク層アドレス(IPアドレス)26aに基づいた経路制御(空間スイッチの切り替え)に加え、新たに「送達希望時刻26b」に基づいて通信パケットの送出順を優先制御することにより、ネットワークリソースを有効利用できる。
【0039】なお、本発明でいう「送達希望時刻」とは、唯一の時点を示す時刻である場合とともに、ある時間幅を持つ場合(時間幅の指定方法としては、送達希望の開始時刻及び最終時刻を指定する、開始時刻または最終時刻と時間(予め取り決めておくことにより省略も可)を指定する等)も含むものとする。
【0040】以上が、請求項1及び10記載の発明についての説明である。
【0041】次に「送達希望時刻」に基づく通信パケットの優先制御の原理を図3により説明する。
【0042】図3では情報の伝達を時間軸及び空間軸からなる2次元空間上の移動と捉えて表現しており、該2次元空間の情報伝達ベクトルとして示している。即ち通信、情報の伝達とは、図3のような2次元空間上のある位置ベクトルから位置ベクトルへの空間ベクトルとして表現できる。
【0043】この時、時間軸要素は時刻であり、時刻自身を時間軸上のアドレスとして用いることができる。一方、空間軸要素はIPアドレス等のネットワーク層のアドレスであり、IPバージョン4(以下、「IPv4」と記す。)ならば32ビットの一次元空間であり、IPバージョン6(以下、「IPv6」と記す。)ならば128ビットの一次元空間である。
【0044】時刻が線形空間であるのに対し、IPアドレス空間は線形空間でないため、IPアドレス間の距離としてルータ装置間のメトリック値を用いる。
【0045】本発明では、情報の伝達を上記の時刻−ネットワーク層アドレスによる2次元空間上の空間ベクトルとして表現し、ベクトルの時間軸成分、空間軸成分、大きさ、偏角といった各要素により、通信パケットが運ぶ情報属性を分類し、ルータ装置内における処理の優先度等の差別化を図るようになしている。
【0046】図4は情報伝達の空間ベクトルの要素を示すものである。情報伝達の空間ベクトルzにおける始点=情報の出発点の時間軸成分は発信時刻ts、空間軸成分は送信元ネットワーク層アドレスssである。また、情報伝達の空間ベクトルにおける終点=情報の到着(希望)点の時間軸成分は情報の送達希望時刻(送達期限)td、空間軸成分は送達先ネットワークアドレスsdである。
【0047】空間軸上の移動距離|sd−ss|はルータ装置間メトリック値を基準にしたエンド−エンドのパケットの移動距離であり、時間軸上の移動距離|td−ts|はパケット発信時に要求された送達希望時刻までの残り(余裕)時間である。
【0048】これらに加え、情報伝達の大きさ|z|={(td−ts)2+(sd−ss)2}1/2は情報伝達のエンド−エンドでの時空間上の移動距離を表し、偏角Θz=arctan{|sd−ss|/|td−ts|}
は単位時間当たりの空間軸上の移動距離に対応している。
【0049】時空間上の移動距離が等しい場合でも、偏角Θzが大きい情報伝達は単位時間当たりより遠くへ伝達される必要があり、偏角Θzは通信コストあるいは通信料金の算出パラメータとして利用できる。また、偏角Θzの値が同一であっても、時空間上の移動距離|z|が大きければ、通過するルータ装置数や伝送距離が大きいことを意味するため、|z|も通信コストあるいは通信料金の算出パラメータとして利用できる。
【0050】これまでのデータリンクの伝送帯域や距離のみによる料金算出に代わり、空間軸の移動距離|sd−ss|、時間軸の移動距離|td−ts|や、時空間上のベクトルの大きさ|z|、偏角Θzといった個々のパラメータ、あるいはそれらの組み合わせによってパケット毎のより細かな課金が行えるようになる。
【0051】以上が、請求項2及び11記載の発明についての説明である。
【0052】また、図4中のyは通信途中のルータ装置における情報伝達の空間ベクトルを表している。この時、ベクトルの始点の時間軸成分はルータ装置内に情報が存在する時の現在時刻tcを表し、空間軸成分はルータ装置のネットワーク層アドレスscを表す。従って、yは通信途上のルータ装置から最終目的地までの情報伝達の空間ベクトルである。
【0053】|sd−sc|はルータ間メトリック値を元にした当該ルータ装置から相手先アドレスまでの残りの距離を表し、|td−tc|は現時点での送達期限までの残り(余裕)時間を表す。また、ベクトルの大きさ|y|={(td−tc)2+(sd−sc)2}1/2は通信パケットを処理する現在のルータ装置から最終到達点まで、時空間上でどれだけ移動距離が残っているかを表しており、偏角Θy=arctan{|sd−sc|/|td−tc|}
は送達希望時刻tdまでに情報を伝達し終わるために、今後、単位時間当たり空間軸上を移動しなければならない距離を表している。
【0054】これら情報伝達ベクトルの各成分|sd−sc|、|td−tc|、|y|、Θyのいずれか、あるいはこれらを組み合わせたものをパラメータとしてルータ装置はパケットルーティング処理の優先度を決定する。
【0055】次に、|y|やΘyによるルータ装置内の優先処理について、図3及び図4を参照して説明する。図3ではリアルタイムデータ転送とファイルデータ転送という2つの種類の異なる情報伝達を空間ベクトルとして表現している。リアルタイム転送では短時間のエンド−エンド情報伝達が要求されるため、ファイルデータ転送と比較してベクトルの偏角Θが大きい。
【0056】途中のルータ装置では、偏角Θyの大きなリアルタイムデータと偏角Θyの小さなファイルデータのいずれも処理しなければならない場合、偏角Θyの値により処理の優先度を決定するのであれば、ファイルデータをルータ装置内に蓄積し、待ち合わせを行うことで優先度の高いリアルタイムデータを先に処理・送出することが可能となる。
【0057】このように従来のルータ装置とは異なり、現在時刻と送達希望時刻の差異や空間軸上の残りの距離から上位レイヤの終端をすることなく、情報の属性に応じて処理の差別化を図ることが可能となり、ネットワークリソースを効率的に運用できる。
【0058】以上が、請求項3及び12記載の発明についての説明である。
【0059】また、送達希望時刻は、ルータ装置内での廃棄メカニズムの目安として捉えることもできる。例えば、ルータ装置内で、送達希望時刻を過ぎたパケットについてはこれを受信先へ送達しても意味の無い情報であると判断できるため(リアルタイムで再生されるストリームデータ等)、輻輳状態に至らなくともルータ装置内で積極的に廃棄することができる(ルータ装置における現在時刻tc>送達希望時刻tdの場合)。
【0060】また、偏角Θは現在時刻tcの関数であるため、初期値Θzとルータ装置内での現在値Θyを比較することで、通信パケットの送達が予定より遅れているか、進んでいるかを判断することができ、これをルータ装置内での処理の優先度に反映させることも可能となる。
【0061】以上が、請求項3及び8記載の発明についての補足説明である。
【0062】図5はIPv6における時間軸情報の格納例を示すものである。空間軸成分、即ち送信元IPアドレスss及び宛先のIPアドレスsdはIPv6ヘッダとしてそれぞれ128bitで表現されている。時間軸成分、即ち発信時刻tsと、送達希望時刻tdはIPv6ヘッダの後に続く中継点オプションヘッダを用いて、これらをそれぞれ32bitで表現し、格納する。
【0063】IPv6におけるヘッダ処理の優先度は、IPv6ヘッダ>中継点オプションヘッダ(hop−by−hop options header)>終点オプションヘッダ(destination options header)>経路制御ヘッダ(routing header)>断片ヘッダ(fragmentheader)>認証ヘッダ(authentication header)>暗号ペイロード(encapsulating security payload)>終点オプションヘッダ>上位層ヘッダ(TCPあるいはUDP等)であり、中継点オプションヘッダは、オプションヘッダとしては最も高い優先度で処理される。
【0064】この時、先頭のIPv6ヘッダ内の次ヘッダ番号には中継点オプションヘッダ(HBH)を表現する「0」が入る。発信時刻、送達希望時刻を格納する中継点オプションヘッダの次ヘッダ番号には次に続くヘッダが例えば、TCPヘッダであれば「6」という値が格納される。
【0065】拡張ヘッダ長は当該中継点オプションヘッダ長(128ビット)を8バイト単位(64ビット)で表現して−1した値、即ち「1」が入る。
【0066】オプション番号は8ビットの識別子であり、上位2ビットでルータ装置がオプションを認識できなかった場合の動作を示し、次の1ビットでオプションが配送経路上で変更可能かどうかを表し、下位5ビットはオプションの内容を示すオプション番号部分となる。本ルータ装置で用いるIPv6ヘッダの場合、動作は「00」(認識できない場合は続み飛ばすという意)、経路上変更可能ビットは「OFF」、オプション番号部分については、IANA(Internet Assigned Numbers Authority)に登録することによってRFCに記述される新しい番号を入れる。オプションデータ長は当該オプションデータ長をバイト表現したもので「12」が入る。
【0067】その後には発信時刻ts及び送達希望時刻tdが、情報伝達ベクトルの始点及び終点アドレスとして32ビットずつ格納される。中継点オプションヘッダの最後の4バイトは時刻情報の単位等の付加情報の格納用として予約するが、時刻情報の単位をミリ秒(ms)、秒(s)、時間(hour)のように3段階で荒く表現する場合はIPv6ヘッダの優先度(4ビット)を利用して時刻情報の単位を表して(格納して)も良い。
【0068】以上が、請求項4及び13記載の発明についての説明である。
【0069】IPv6の中継点オプションヘッダを用いることで既存のIPv6のパケットフォーマットを変更せずに時間軸成分を運ぶことができ、従来の時間軸成分を情報として持たない既存のパケットと同等に処理することも可能となる。
【0070】また、パケットに格納される発信時刻や送達希望時刻は、例えばMPEGファイルのような等時性(アイソクロナス性)情報を運ぶ際の再生タイミングを表現していると言える(MPEGのTSフレームのような)。即ち、通信パケットに添付されている送達希望時刻は受信先でアイソクロナスデータを再生するタイムスタンプとして利用できるため、ネットワークは遅延の揺らぎを抑えるといったアイソクロナス性保証のための転送メカニズムを実装する必要がなくなる。
【0071】さらに、送達希望時刻は通信パケットの絶対的なシーケンス番号とみなすことも可能であり、元情報を再構成することが可能であるため、ネットワークは通信パケット到着の順序性を保証する必要がなくなり、ルータ装置はより簡便な転送メカニズムを実装できる。
【0072】以上が、請求項4及び13記載の発明についての補足説明である。
【0073】次に、本発明のルータ装置の具体例について説明する。
【0074】図6はルータ装置の全体構成を示すもので、同図(a)は全体斜視図、同図(b)は配線図である。図中、31A,31B,31C,31Dは全二重通信路を有しかつ図2で述べた経路制御部、優先制御部及び時間スイッチを構成する入出力部、32はディスクアレイ用コンピュータ(PC)、33は入出力部31A〜31D及びディスクアレイ用PC32間を空間的にスイッチングするスイッチ(SW)部、34は制御用コンピュータ(PC)、35はこれらを接続する専用バックプレーン、36はディスクアレイである。
【0075】制御用PC34には他のルータ装置との間でリンクステート情報をやり取りするルーティングプロトコルが実装され、ルータ装置間の空間軸上の距離を測定する如くなっている。
【0076】前述した入出力部31A〜31Dは全て同一構成であり、図7にその詳細構成の一例、ここではネットワークとのデータのやりとりを光信号で行うようになした場合の例を示す。図中、311aは光入力部(Opt in)、311bは光出力部(Opt out)、312はシリアル・パラレル変換器(S/P)、313はデータリンク層終端部、314はFPGA(Field Programmable Gate array)、315は信号処理プロセッサ(DSP)、316a,316b,316cはシンクロナスSRAM(SSRAM)等からなる高速メモリ、317は連想メモリ(Content Addressable Memory:CAM)、318はシンクロナス(sync.)FIFOメモリ、319はインタフェース部(I/F)である。
【0077】以下、入出力部が前述した経路制御部、優先制御部及び時間スイッチを構成するようすをその動作概要とともに説明する。
【0078】図示しないネットワークから光ファイバを介して届いたパケットデータは、光入力部311aで光電変換され、S/P312でシリアル・パラレル変換された後、ギガビットイーサネット(Gigabit Ethernet)等のデータリンク層終端部313を経てIPデータグラムとして取り出され、FPGA314において時間軸成分の精度(単位)により振り分けられる。
【0079】ここで、時間軸成分の表示単位は、図5に示したようにIPv6ヘッダの優先度あるいは時間軸成分を格納する中継点オプションヘッダの末尾部分に格納されている。図7の例では、時間軸成分の単位をミリ秒(ms)、秒(s)、時間(hour)の3段階に分類している。
【0080】FPGA314により時間軸成分の表示単位毎に分類されたデータはIPデータグラムのまま、ミリ秒(ms)用,秒(s)用,時間(hour)用の高速メモリ316a,316b,316cへ格納される。この時、IPデータグラムはメモリ内に順に格納され、メモリはリングバッファとして利用される。
【0081】一方、高速メモリ316a〜316cへ格納されるIPデータグラムのヘッダ部(中継点オプションヘッダを含む。)は、経路計算及び情報伝達ベクトルの偏角Θy計算用のDSP315へ渡される。
【0082】DSP315はIPヘッダの相手先アドレスsdから経路を計算し、当該パケットをどの方路から送出すべきか、即ちSW部33を介して次にどの入出力部へ送出すべきかを決定する。
【0083】この方路情報は、時間軸成分の単位、高速メモリ316a〜316cへIPパケットを格納した際のライトアドレス(wp)とともにCAM317へ格納される。この時、{方路、単位、wp}を格納するCAM317のライトアドレスはDSP315で計算されたΘyの逆数を用いる。
【0084】CAM317は通常のメモリとは異なり、アドレスを与えて格納されているデータへアクセスするのではなく、検索ワードを与え、これに一致するデータが格納されているアドレスを知るというメモリである。
【0085】例えば、CAM317に検索ワードとして、方路及び単位を与えることで、特定の方路及び単位の情報だけを取り出すことができる。方路及び単位が一致する情報が複数格納されている場合、CAM317は格納されているデータの中から最小アドレスを返すため、{方路、単位、wp}を格納するCAM317のライトアドレスにΘyの逆数を用いることで、特定方路行きの特定単位の最大Θy情報、即ち最大Θyを持つIPデータグラムの高速メモリ316a〜316cへの格納位置wpを知ることができる。
【0086】こうして得られたwpを高速メモリ316a〜316cのリードアドレス(rp)に用いることで、常に特定方路行きの特定単位の最大Θyを持つIPデータグラムを高速メモリ316a〜316cから取り出すことができる。
【0087】このようにしてIPデータグラムの中から取り出された、最大のΘyとなるIPデータグラムはI/F319を経て、バックプレーン35を介してSW部33へ転送される。
【0088】一方、SW部33からバックプレーン35を介して到着したIPデータグラムは、I/F319を経てSync.FIFOメモリ318で受信される。Sync.FIFOメモリ318に格納されたIPデータグラムは順次、データリンク層終端部313、S/P312、光出力部311bへ送られ、光信号に変換されてネットワークへ送出される。
【0089】図8は前述したスイッチ部(SW部)の詳細構成を示すもので、同図(a)は回路構成図、同図(b)は切替接続の説明図である。図中、331は高速クロスバスイッチチップで構成される5×5スイッチ構成のクロスバスイッチであり、その5つの入力ポート及び出力ポートには4つの入出力部31A〜31Dとともに、ディスクアレイ用PC32が接続されている。また、332は切替制御用のCPUであり、クロスバスイッチ331を、タイミングを管理しつつ、同図(b)に示すような各入出力ポートのl対1接続を全て網羅する5つのフェーズに切り替え制御する如くなっている。なお、フェーズとフェーズとの間にはガードタイムが設定されている。
【0090】ディスクアレイ用PC32は、送達希望時刻tdが∞(無限大)に設定されているような優先度の低いIPデータグラムを格納するための大容量の記憶装置、ここではディスクアレイ36を制御するためのものである。
【0091】送達希望時刻までの余裕が大きい場合や、送達希望時刻が無限大に設定されているような通信パケットは、入出力部31A〜31DからSW部33及びPC32を介して、一旦、ディスクアレイ36に蓄積され、然るべき時間経過を待ってPC32及びSW部33を介して再度、入出力部へ読み出される。
【0092】この際、送達希望時刻を無限大に設定することにより、時刻を問わず送達して構わないデータであることを指定できるので、ルータ装置内の記憶装置に蓄積しながら、確実に伝達されるという情報伝達サービスクラスを新たに定義することができる。また、トラフィック輻輳時においても低優先度パケットを廃棄するのではなく、記憶装置に待避させることができるため、パケット廃棄率を改善でき、その結果、エンド−エンドの簡便な送達確認メカニズムを持つトランスポートレイヤにより信頼性の高いデータ転送が実現できる。
【0093】以上の説明のうち、ディスクアレイ36にデータを退避させる点が、請求項5及び14記載の発明と対応している。
【0094】ところで、前述した実施の形態において、高速メモリ316a〜316cへのパケットデータの格納は、時間軸成分の単位(ミリ秒、秒、時間)毎に単純に受信した順に行われ、また、高速メモリ316a〜316cからのパケットデータの取り出しは、方路毎及び時間軸成分の単位毎に単純に優先度(Θy)の高い順に行われていた。
【0095】従って、ネットワークが込み合うような状況下において、ある時間軸成分の単位、例えば時間(h)に対応したメモリ316c内に格納されたパケットデータの送達希望時刻までの残り(余裕)時間が少なくなったりしても、他のメモリ316a,316b内のパケットデータの転送が優先され、その結果、メモリ316cに格納されたパケットデータの送達希望時刻が守られなくなる場合があり得るという問題があった。
【0096】図9は前述した点を改良した本発明のルータ装置の実施の形態の他の例の要部、ここでは高速メモリ316a〜316cに対するパケットデータの格納(キューイング:queuing)及び取り出し制御にかかわる部分を示すものである。
【0097】本実施の形態では、各高速メモリ316a〜316c内におけるパケットデータのキューイングを優先度(Θy)順に行うとともに、待ち合せ等によって送達希望時刻までの残り時間の単位(オーダ)が変化した場合にはキューイングするメモリそのものを変更する。また、パケットデータの取り出しは高速メモリ316a〜316c毎に優先度の高いものから行うが、各高速メモリ316a〜316cからの取り出し(転送)確率(割合)を、キューイングしているデータ量に応じて変化させる。
【0098】前述した各高速メモリ316a〜316c内におけるパケットデータの優先度順のキューイングは、連想メモリ317から優先度順に取り出されるアドレスによって並べ替えることにより実現され、優先度(Θy)が高いものほど各高速メモリ316a〜316cの先頭(出口)に近く、低いものほど後尾(入口)に近くなるように配列される。
【0099】各高速メモリ316a〜316cに格納されたパケットデータは、それぞれのメモリ内で優先度の高いもの、即ちA、B、Cから取り出される。
【0100】この際、長時間の待ち合わせ等により送達希望時刻までの残り時間のオーダが変化してしまった場合、例えばオーダが時間(h)のメモリ316c内のパケットCの送達希望時刻までの残り時間が59分59秒以下になった場合、オーダ遷移制御部41によりc1のルートを通って速やかに秒(s)のメモリ316bの最後尾に移る。また、同様にオーダが秒(s)のメモリ316b内のパケットBの送達希望時刻までの残り時間が999ms以下になった場合、オーダ遷移制御部41によりb1のルートを通ってミリ秒(ms)のメモリ316aの最後尾に移る。これは連想メモリ317における時間軸成分の単位のビットを書き替えることにより実現される。
【0101】また、各高速メモリ316a〜316cからのパケットデータの取り出しに関しては取り出し制御部42によって、さらに詳細に制御される。
【0102】即ち、取り出し制御部42は各メモリ316a〜316c内の格納パケットデータ数(キューの長さ)の変動を観測しており、それによりメモリ316a〜316c毎の取り出し確率を変化させる。但し、取り出し確率は0<確率<lの範囲での変動とし、待ち合わせ及び到着パケットの全くないメモリが存在しない限り、特定のメモリのみから取り出したり、特定のメモリに関して全く取り出さなかったりということはない。
【0103】図10、図11はパケットの受信時のキューイング及びオーダ遷移制御アルゴリズムを表すフローチャートである。また、図12〜図14はパケット送信時の取り出し制御アルゴリズムを表すフローチャートである。
【0104】以上が、請求項6、7及び15、16記載の発明についての説明である。
【0105】図15は図5と同様、IPv6における時間軸情報の他の格納例を示すものである。ここで、送達希望時刻としてtd1,td2という2種類が存在するが、これは送達希望時刻としてtd1より後、td2より前という指定を可能とするものである。即ち、図5と同様のtdの扱いにするためにはtd1=0とすれば良く、また、td1=td2とした場合は、ちょうどその時刻に送達されるようにパケットの転送を行う。
【0106】また、送信先が込み合っている場合等で迂回を行う時、パケットループを防ぐために迂回元のルータIDを記述する。迂回していない場合は「0」である。この変更を行うため、オプションタイプの経路上変更可能ビットは図5と異なり、「1」となる。
【0107】さらに優先度及び時刻tdのオーダのフィールドを設ける。優先度が「1」の場合、最も優先度が高いものとして、ルータが受信したパケットはキューイングを行わずに素早く次のルータへ送る。この場合、送達希望時刻のフィールドは参照せず、従って優先度Θの計算も行わない。「0」の場合は通常通り、送達希望時刻のオーダ毎のキューイングを行う。
【0108】また、このフィールド最後のビットを用いて、送達希望時刻を越えたパケットの扱いを指定する。「1」の場合は送達希望時刻を越えても捨てずに配送を行う。「0」の場合は送達希望時刻を越えたパケットは廃棄する。
【0109】以上が、請求項8及び17記載の発明についての説明である。
【0110】また、これまでの説明におけるルーティングプロトコルでは、固定的なメトリック値を用いており、ネットワークを流れるトラフィックの変動に起因する、利用可能帯域の変動等による目的地までの処要時間の変化に対して有効な対策を取り得ない。即ち、途中のルータが動作不能になる等、パケットが到達不能にならない限り、輻輳により転送効率が落ち、パケットロスが発生し始めても、ルーティングテーブル作成時に「最短である」とみなされた経路を採り続けるという問題が生じる。このため、ネットワークのトラフィック状況によっては送達希望時刻を満たすパケットが著しく減少する可能性がある。
【0111】前述した問題は隣接するルータ装置間でネットワーク状況に関する情報を交換し、メトリック値を動的に変更可能とすることにより解決できる。
【0112】図16はAS(Autonomous System:自律システム)内のルーティング情報の伝播の一例として、OSPF(Open ShortestPath First)のLSA(Link State Advertisement)パケットにおける隣接ルータとの交換情報の格納例である。
【0113】詳しい情報の交換は隣接ルータとのみ行うため、flooding scopeはLink Localである。ここでいうCLASSはキュー(高速メモリ)の数と一致しており、ms,s,hの3つのキューを持つのであればCLASS=3となる。
【0114】また、低優先度のパケットを退避させるため、大容量の半導体メモリ及びハードディスクをストレージとして用いる場合は、その後のSTRビットを立てる。また、if_numはルータに挿してあるインタフェースの総数である(但し、コミュニケーションポート等、管理の時にしか使用しないインタフェースは除く。)。qlen_usedは各キュー内にキューイングされているパケット数であり、qlen_unusedは各キューの空き、即ち格納可能なパケット数を示している。
【0115】mbuf_used、mbuf_unusedはそれぞれメモリバッファの使用量、空き容量をbytes単位で表す値である。同様にmemory_used、memory_unused及びdisk_used、disk−unusedもストレージに関する使用量、空き容量をKbytes単位で表す値である。これらのパケット数、容量は測定時の瞬間的な値ではなく、ある時間区間毎の平均値である。
【0116】さらにtr_ifはインタフェース毎の情報をメンバに持つ構造体である。tr_if.interface_idはルータ内でインタフェースを一意に識別するIDであり、tr_if.if_baudrateはインタフェースの物理速度を示す。
【0117】tr_if.statisticsは一秒あたりのそのインタフェースを経由してルータ内に入ってきたパケットのbytes数を示す。point−to−pointのリンクであれば、この数値がリンクの使用状況を示し、また、point−to−multipointのリンクであれば、リンク上の全てのルータのstatisticsを集計したものがリンクの使用状況となる。
【0118】tr_if.route_numはそのリンク上の隣接ルータの数である。tr_if.router_idは隣接ルータのidであり、tr_if.rttはその隣接ルータまでの往復にかかる時間RTT(Round Trip Time)である。
【0119】これらの情報を隣接ルータ間で交換し、隣接ルータまでのメトリック値をそれぞれ計算する。その際、各ルータへのメトリック値をms,s,h用にそれぞれ3種類計算する。この計算式は得られた情報の関数として計算される。よってメトリック値は動的なものとなり、このうちmsのメトリック値を代表値としてAS内全てのルータにfloodingにより配布する。このメトリック値を図3における空間アドレス上の距離に相当するものとしてΘyを計算する。
【0120】ここで、ルータCに対し隣接ルータAから送られる交換情報が構造体Aのメンバとして与えられたとし、ルータA内のmsのキューに存在するパケット数の平均値及び格納可能なパケットの数の平均値がそれぞれA.qlen_used[0]及びA.qlen_unused[0]、また、同様にA内のメモリバッファの使用量及び残容量がそれぞれA.mbuf_used及びA.mbuf_unused、さらにルータAとのRTTがA.RTT、ルータAが存在するリンクの物理速度をA.if_baudrate、ルータAが存在するリンク上のルータCに対する全ての隣接ルータより得た使用状況から算出した当該リンクの使用状況をA.statisticsとして与えられたとすると、これらを用いて隣接ルータAへのmsにおけるメトリック値|SA−SC|msを表すと、|SA−SC|ms=f(A.qlen_used[0],A.qlen_unused[0],A.mbuf_used,A.mbuf_unused,A.rtt,A.if_baudrate,A.statistics)
となる。以下、同様にs,hにおけるメトリック値は、|SA−SC|s=g(A.qlen_used[1],A.qlen_unused[1],A.mbuf_used,A.mbuf_unused,A.memory_used,A.memory_unused,A.rtt,A.if_baudrate,A.statistics)
|SA−SC|h=h(A.qlen_used[2],A.qlen_unused[2],A.mbuf_used,A.mbuf_unused,A.disk_used,A.disk_unused,A.rtt,A.if_baudrate,A.statistics)
となる。
【0121】f(),g(),h()の具体例として、以下の数式を示す。
【0122】|SA−SC|ms={αms(A.qlen_used[0]+βmsA.qlen_unused[0])+γms(A.mbuf_used+δmsA.mbuf_unused)}・A.rtt/{1・1・(A.if_baudrate−A.statistics)}
|SA−SC|s={αs(A.qlen_used[1]+βsA.qlen_unused[1])+γs(A.mbuf_used+δsA.mbuf_unused)+εs(A.memory_used+ζsA.memory_unused)}・A.rtt/{1・1・(A.if_baudrate−A.statistics)}
|SA−SC|h={αh(A.qlen_used[2]+βhA.qlen_unused[2])+γh(A.mbuf_used+δhA.mbuf_unused)+εh(A.disk_used+ζhA.disk_unused)}・A.rtt/{1・1・(A.if_baudrate−A.statistics)}
上式中、1は全て1秒を表しており、それぞれの式を無次元化するために挿入してある。また、αは平均パケットサイズ、β〜ζは全て実定数であり、γ,εに関しては正、β,δ,ζに関しては負である。
【0123】このms,s,hにおける3種のメトリック値を用い、それぞれでルーティングテーブルを作成する。但し、他のルータに配布するメトリック値は前述の通りmsのメトリック値のみであり、逆に他のルータから配布されてくるメトリック値もmsのもののみである。即ち、3種のメトリック値は自ルータから隣接ルータまでのメトリック値のみであり、s,hのメトリック値によるルーティングテーブルは迂回に用いる。
【0124】即ち、代表として他のルータに配布するmsのメトリック値を最適なパスとして通常用いるが、そのパスが込み合ってきた場合、s,hのオーダのキューにあるパケットに関してはs,hのメトリック値によるルーティングテーブルを参照し、迂回が可能であれば迂回を行う。その際、図15に示したIPv6の中継点オプションヘッダ内に迂回元ルータIDを記述する。
【0125】以上が、請求項9及び18記載の発明についての説明である。
【0126】
【発明の効果】以上説明したように、本発明によれば、以下のような効果を得ることができる。
【0127】即ち、請求項1記載の発明によれば、個々の通信パケットを送達希望時刻に応じた順序で経路制御でき、リアルタイム性の高いデータから低いデータまで最適な優先度でルーティング処理できるとともに、ネットワークリソースを有効活用できる。
【0128】また、請求項2記載の発明によれば、データリンクの伝送帯域・距離のみによる課金処理に代えて、空間軸あるいは時間軸における情報の移動距離に基づいて個々のパケット毎にきめ細かい課金を行うことができる。
【0129】また、請求項3記載の発明によれば、上位レイヤを終端することなく、情報の属性に応じて処理の差別化を図ることが可能となり、ネットワークリソースを効率的に運用でき、また、各ルータ装置において、個々のパケット毎に配送が遅れているのか、あるいは進んでいるのかを知ることができる。
【0130】また、請求項4記載の発明によれば、既存のIPv6のパケットフォーマットを変更することなく、通信パケットに時間軸情報を付与することができる。
【0131】また、請求項5記載の発明によれば、トラヒック輻輳時においてパケットの破棄を軽減することが可能となる。
【0132】また、請求項6記載の発明によれば、送達希望時刻までの残り時間に対応した適切な転送処理が可能となり、可能な限り送達希望時刻を満たすような配送が可能となる。
【0133】また、請求項7記載の発明によれば、送達希望時刻までの残り時間に応じた待ち合わせ中のパケット数の極端な差をなくすことができ、可能な限り送達希望時刻を満たすような配送が可能となる。
【0134】また、請求項8記載の発明によれば、経路の変更が可能となり、また、通信パケットを待ち合わせなしで最優先で処理したり、また、送達希望時刻を越えた通信パケットをそのまま待ち合わせさせたり、廃棄したりを指示できる。
【0135】また、請求項9記載の発明によれば、ネットワークが込み合うような状況においても適応的なルーティングが可能となり、送達希望時刻を満たすパケットが著しく減少することを防止できる。
【0136】また、請求項10乃至18の発明によれば、前述した優先経路制御を実行可能なルータ装置を提供できる。
【図面の簡単な説明】
【図1】従来のルータ装置の一例を示すブロック構成図
【図2】本発明のルータ装置の基本構成を示すブロック構成図
【図3】送達希望時刻に基づく通信パケットの優先制御の原理の説明図
【図4】情報伝達の空間ベクトルの要素の説明図
【図5】IPv6における時間軸情報の格納例の説明図
【図6】本発明のルータ装置の実施の形態の一例を示す構成図
【図7】図6中の入出力部の詳細構成図
【図8】図6中のスイッチ部の詳細構成図
【図9】本発明のルータ装置の実施の形態の他の例の要部を示す構成図
【図10】パケット受信時のキューイング及びオーダ遷移制御アルゴリズムを表すフローチャート
【図11】パケット受信時のキューイング及びオーダ遷移制御アルゴリズムを表すフローチャート
【図12】パケット送信時の取り出し制御アルゴリズムを表すフローチャート
【図13】パケット送信時の取り出し制御アルゴリズムを表すフローチャート
【図14】パケット送信時の取り出し制御アルゴリズムを表すフローチャート
【図15】IPv6における時間軸情報の他の格納例の説明図
【図16】LSAパケットにおける隣接ルータ装置との交換情報の格納例の説明図
【符号の説明】
21:入力ポート、22:スイッチ部、23:出力ポート、24:経路制御部、25:優先制御部、26:通信パケット、26a:宛先アドレス、26b:送達希望時刻、27:空間スイッチ、28:時間スイッチ、31A,31B,31C,31D:入出力部、32:ディスクアレイ用PC、33:スイッチ(SW)部、34:制御用PC、35:バックプレーン、36:ディスクアレイ、311a:光入力部(Opt in)、311b:光出力部(Opt out)、312:シリアル・パラレル変換器(S/P)、313:データリンク層終端部、314:FPGA、315:信号処理プロセッサ(DSP)、316a〜316c:高速メモリ、317:連想メモリ(CAM)、318:シンクロナス(sync.)FIFOメモリ、319:インタフェース部(I/F)、331:クロスバスイッチ、332:制御用CPU、41:オーダ遷移制御部、42:取り出し制御部。
【特許請求の範囲】
【請求項1】 通信パケット毎にラベル付けされた宛先アドレスに基づいて、通信パケットの経路を切替制御して送り出す経路制御方法において、宛先アドレスとともに送達希望時刻をラベル付けし、この送達希望時刻に基づいてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする優先経路制御方法。
【請求項2】 通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定することを特徴とする請求項1記載の優先経路制御方法。
【請求項3】 ルータ装置のアドレス及び通信パケットの宛先アドレスより求められるルータ装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする請求項1記載の優先経路制御方法。
【請求項4】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に通信パケットの発信時刻及び送達希望時刻を格納して作成した通信パケットを用いることを特徴とする請求項1乃至3いずれか記載の優先経路制御方法。
【請求項5】 処理能力以上の通信パケットにより輻輳が発生した場合、優先度が低い通信パケットをルータ装置内の記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して経路制御を再開させることを特徴とする請求項1乃至4いずれか記載の優先経路制御方法。
【請求項6】 通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した時は待ち合わせの単位を変更することを特徴とする請求項1乃至5いずれか記載の優先経路制御方法。
【請求項7】 通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、前記単位毎の転送確率を、該単位毎の待ち合わせ中のパケット数に応じて変更することを特徴とする請求項1乃至6いずれか記載の優先経路制御方法。
【請求項8】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に、迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを格納して作成した通信パケットを用いることを特徴とする請求項1乃至7いずれか記載の優先経路制御方法。
【請求項9】 ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを隣接するルータ装置間で交換し、前記情報に基づいて隣接するルータ装置までのメトリック値を求め、該求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更することを特徴とする請求項1乃至8いずれか記載の優先経路制御方法。
【請求項10】 複数の入力ポート及び複数の出力ポートと、複数の入力ポート及び複数の出力ポート間を任意に切替接続可能な空間スイッチと、入力ポートから入力された通信パケットをその宛先アドレスに対応する出力ポートへ送出するよう空間スイッチを制御する経路制御部とを有するルータ装置において、複数の通信パケットの順序を任意に入れ替え可能な時間スイッチと、複数の通信パケットの順序が各通信パケットに付与された送達希望時刻に対応する順序となるよう時間スイッチを制御する優先制御部とを設けたことを特徴とするルータ装置。
【請求項11】 通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定する手段を備えたことを特徴とする請求項10記載のルータ装置。
【請求項12】 自装置のアドレス及び通信パケットの宛先アドレスより求められる自装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、時間スイッチを制御する優先制御部を備えたことを特徴とする請求項10記載のルータ装置。
【請求項13】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された通信パケットの発信時刻及び送達希望時刻を用いる優先制御部を備えたことを特徴とする請求項10乃至12いずれか記載のルータ装置。
【請求項14】 通信パケットを一時的に記憶する記憶装置と、処理能力以上の通信パケットが入力されて輻輳が発生した場合、優先度が低い通信パケットを記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して優先経路制御を再開させる制御手段とを備えたことを特徴とする請求項10乃至13いずれか記載のルータ装置。
【請求項15】 送達希望時刻までの残り時間の単位別に分割された時間スイッチと、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した一の時間スイッチ内の通信パケットを、該変化後の単位に対応する時間スイッチへ移す手段とを備えたことを特徴とする請求項10乃至14いずれか記載のルータ装置。
【請求項16】 送達希望時刻までの残り時間の単位別に分割された時間スイッチと、前記単位毎の時間スイッチにおける通信パケットの取り出し確率を、該単位毎の時間スイッチにおける待ち合わせ中のパケット数に応じて変更する手段とを備えたことを特徴とする請求項10乃至15いずれか記載のルータ装置。
【請求項17】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを用いる優先制御部を備えたことを特徴とする請求項10乃至16いずれか記載のルータ装置。
【請求項18】 ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを作成し、隣接するルータ装置間で交換する手段と、前記パケット内の情報に基づいて隣接するルータ装置までのメトリック値を計算する手段と、前記求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更する手段とを備えたことを特徴とする請求項10乃至17いずれか記載のルータ装置。
【請求項1】 通信パケット毎にラベル付けされた宛先アドレスに基づいて、通信パケットの経路を切替制御して送り出す経路制御方法において、宛先アドレスとともに送達希望時刻をラベル付けし、この送達希望時刻に基づいてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする優先経路制御方法。
【請求項2】 通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定することを特徴とする請求項1記載の優先経路制御方法。
【請求項3】 ルータ装置のアドレス及び通信パケットの宛先アドレスより求められるルータ装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、経路制御を行うことを特徴とする請求項1記載の優先経路制御方法。
【請求項4】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に通信パケットの発信時刻及び送達希望時刻を格納して作成した通信パケットを用いることを特徴とする請求項1乃至3いずれか記載の優先経路制御方法。
【請求項5】 処理能力以上の通信パケットにより輻輳が発生した場合、優先度が低い通信パケットをルータ装置内の記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して経路制御を再開させることを特徴とする請求項1乃至4いずれか記載の優先経路制御方法。
【請求項6】 通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した時は待ち合わせの単位を変更することを特徴とする請求項1乃至5いずれか記載の優先経路制御方法。
【請求項7】 通信パケットを送達希望時刻までの残り時間の単位別に待ち合わさせ、該単位毎に異なる確率で転送処理する場合、前記単位毎の転送確率を、該単位毎の待ち合わせ中のパケット数に応じて変更することを特徴とする請求項1乃至6いずれか記載の優先経路制御方法。
【請求項8】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に、迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを格納して作成した通信パケットを用いることを特徴とする請求項1乃至7いずれか記載の優先経路制御方法。
【請求項9】 ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを隣接するルータ装置間で交換し、前記情報に基づいて隣接するルータ装置までのメトリック値を求め、該求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更することを特徴とする請求項1乃至8いずれか記載の優先経路制御方法。
【請求項10】 複数の入力ポート及び複数の出力ポートと、複数の入力ポート及び複数の出力ポート間を任意に切替接続可能な空間スイッチと、入力ポートから入力された通信パケットをその宛先アドレスに対応する出力ポートへ送出するよう空間スイッチを制御する経路制御部とを有するルータ装置において、複数の通信パケットの順序を任意に入れ替え可能な時間スイッチと、複数の通信パケットの順序が各通信パケットに付与された送達希望時刻に対応する順序となるよう時間スイッチを制御する優先制御部とを設けたことを特徴とするルータ装置。
【請求項11】 通信パケットの送信元アドレス及び宛先アドレスより求められる送受信者間のメトリック値、または通信パケットの発信時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとして通信料金を決定する手段を備えたことを特徴とする請求項10記載のルータ装置。
【請求項12】 自装置のアドレス及び通信パケットの宛先アドレスより求められる自装置から宛先までのメトリック値、または現在時刻及び送達希望時刻より求められる送達希望時刻までの残り時間、あるいはメトリック値と送達希望時刻までの残り時間とから求められる値、もしくはこれらの組み合わせ、をパラメータとしてパケット処理の優先順位を決定し、時間スイッチを制御する優先制御部を備えたことを特徴とする請求項10記載のルータ装置。
【請求項13】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された通信パケットの発信時刻及び送達希望時刻を用いる優先制御部を備えたことを特徴とする請求項10乃至12いずれか記載のルータ装置。
【請求項14】 通信パケットを一時的に記憶する記憶装置と、処理能力以上の通信パケットが入力されて輻輳が発生した場合、優先度が低い通信パケットを記憶装置に一時的に退避させ、送達希望時刻が近づいて退避中の通信パケットの優先度が上がった場合、あるいは輻輳が収まった場合に、記憶装置から通信パケットを読み出して優先経路制御を再開させる制御手段とを備えたことを特徴とする請求項10乃至13いずれか記載のルータ装置。
【請求項15】 送達希望時刻までの残り時間の単位別に分割された時間スイッチと、待ち合わせ中に送達希望時刻までの残り時間の単位が変化した一の時間スイッチ内の通信パケットを、該変化後の単位に対応する時間スイッチへ移す手段とを備えたことを特徴とする請求項10乃至14いずれか記載のルータ装置。
【請求項16】 送達希望時刻までの残り時間の単位別に分割された時間スイッチと、前記単位毎の時間スイッチにおける通信パケットの取り出し確率を、該単位毎の時間スイッチにおける待ち合わせ中のパケット数に応じて変更する手段とを備えたことを特徴とする請求項10乃至15いずれか記載のルータ装置。
【請求項17】 インターネットプロトコルバージョン6仕様における通信パケットの中継点オプションヘッダ内に格納された迂回した際の迂回元のルータ装置のID、送達希望時刻とは無関係な優先度、送達希望時刻を越えた場合の扱いを用いる優先制御部を備えたことを特徴とする請求項10乃至16いずれか記載のルータ装置。
【請求項18】 ルータ装置内の記憶装置の使用量及び空き容量、リンクの使用状況、リンク上の隣接するルータの数、隣接するルータまでの往復にかかる時間等の情報を格納したパケットを作成し、隣接するルータ装置間で交換する手段と、前記パケット内の情報に基づいて隣接するルータ装置までのメトリック値を計算する手段と、前記求めたメトリック値を用いてルータ装置から宛先までのメトリック値を動的に変更する手段とを備えたことを特徴とする請求項10乃至17いずれか記載のルータ装置。
【図1】
【図2】
【図3】
【図6】
【図4】
【図5】
【図7】
【図8】
【図9】
【図11】
【図10】
【図12】
【図13】
【図14】
【図15】
【図16】
【図2】
【図3】
【図6】
【図4】
【図5】
【図7】
【図8】
【図9】
【図11】
【図10】
【図12】
【図13】
【図14】
【図15】
【図16】
【公開番号】特開2000−78188(P2000−78188A)
【公開日】平成12年3月14日(2000.3.14)
【国際特許分類】
【出願番号】特願平10−343946
【出願日】平成10年12月3日(1998.12.3)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成12年3月14日(2000.3.14)
【国際特許分類】
【出願日】平成10年12月3日(1998.12.3)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]