JP2000078188A - 優先経路制御方法及びルータ装置 - Google Patents

Abstract

(57)【要約】 【課題】 帯域確保を行うことなく、リアルタイム性の
高いデータから低いデータまでを最適な優先度でルーテ
ィング処理でき、ネットワークの帯域利用効率を向上可
能な優先経路制御方法及びルータ装置を提供すること。 【解決手段】 複数の入力ポート２１から入力された通
信パケットを複数の出力ポート２３へ出力するスイッチ
部２２を、通信パケットに付与された宛先アドレスに対
応してその経路を切り替える空間スイッチ２７ととも
に、複数の通信パケットの順序を任意に入れ替え可能な
時間スイッチ２８とで構成し、該時間スイッチ２８を複
数の通信パケットの順序が各通信パケットに付与された
送達希望時刻に対応する順序となるよう制御する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、通信パケットを高
速かつ効率良くルーティング可能な優先経路制御方法及
びルータ装置に関するものである。

【０００２】

【従来の技術】電気通信の分野において、通信ネットワ
ークを介して情報を効率良く交換・伝送するために、交
換機（ｅｘｃｈａｎｇｅ）やルータ（ｒｏｕｔｅｒ）等
の経路制御装置（以下、「ルータ装置」と呼ぶ。）が用
いられる。このルータ装置は、特に、インターネットを
介した情報データ通信で広く用いられており、インター
ネットを構成する上で重要な役割をはたしている。以
下、図１を参照して、従来のルータ装置について説明す
る。

【０００３】図１は従来のルータ装置の一例を示すもの
で、図中、１１は複数の入力ポート、１２はスイッチ
部、１３は複数の出力ポート、１４は経路制御部、１５
は通信パケットである。

【０００４】次に、従来のルータ装置の動作について図
１を参照して説明する。

【０００５】入力ポート１１から入力された通信パケッ
ト１５は、スイッチ部１２に入力される。それぞれの通
信パケット１５にはパケットの宛先を示す宛先アドレス
（例えばインターネットプロトコル（以下、「ＩＰ」と
記す。）で用いられているＩＰアドレス）１５ａが付加
されており、スイッチ部１２を制御する経路制御部１４
はこの宛先アドレス１５ａに基づいて、通信パケット１
５をどの出力ポート１３から出力すべきかを判断する。

【０００６】スイッチ部１２は空間スイッチ１６から構
成されており、通信パケット１５から宛先アドレス１５
ａを取り出して経路制御部１４に問い合わせると、経路
制御部１４はルーティングテーブルを検索し、通信パケ
ット１５をどの出力ポート１３にスイッチングすれば良
いかを得て、その結果を空間スイッチ１６に返し、空間
スイッチ１６がこの結果を受けて通信パケット１５をス
イッチングする。

【０００７】スイッチ部１２によって目的の出力ポート
１３にスイッチングされた通信パケット１５は、出力ポ
ート１３から出力される。

【０００８】入力ポート１１から同じ宛先への通信パケ
ットが大量に入力された場合、空間スイッチ１６におい
て輻輳が発生し、通信パケットは破棄される。

【０００９】

【発明が解決しようとする課題】ルータ装置の役割は、
入力された通信パケットをルーティング処理して出力す
ることであって、従来のルータ装置では、経由する通信
量が少なければ小さい遅延でルーティング可能である
が、通信量が多ければ遅延が大きくなり、また、空間ス
イッチの許容能力を越える通信パケットが入力される
と、通信パケットを破棄する。即ち、従来のルータ装置
は、通信パケットを転送するために最大限の努力をする
が、処理能力の限界や通信回線の速度限界によって通信
できないこともあるという、ベストエフォート型のネッ
トワークを提供する。

【００１０】電話の音声データや放送の動画像データ等
は、リアルタイム性の高いデータであり、通信の遅延時
間に大きなゆらぎが発生したり、通信パケットに欠落が
生じると、受信側において正確なデータ再生ができなく
なる。このため、これまでは、リアルタイム性の高いデ
ータに対して「帯域保証」という概念の下、予め必要な
通信路の帯域を確保して通信を行うようになしていた。

【００１１】しかし、帯域確保を行う場合、（ａ）送受
信者間の全ての回線で帯域を確保しなければならない、
（ｂ）通信量が変動する場合、その最大値で帯域を確保
しなければならないため、帯域利用効率が悪くなる、
（ｃ）ルータ装置において帯域確保のための処理負荷が
大きい、という問題があった。

【００１２】以上のことから、帯域確保という手段によ
ってリアルタイム性の高いデータを確実に届けることは
可能であるが、多くの問題を抱えていた。

【００１３】また、帯域保証の他に、個々の通信パケッ
ト毎に優先度が高いか低いかを表す値を付加し、リアル
タイム性の高い通信パケット等を優先度の高い通信パケ
ットとしてルーティングを行わせることにより、信頼性
を向上させる方法もある。

【００１４】しかし、この場合、優先度の高い通信パケ
ットは通過する全てのルータ装置において優先的に扱わ
れ、逆に優先度の低い通信パケットは全てのルータ装置
において優先度が低く扱われてしまうことになる。即
ち、通信パケットの重要の度合いが優先度が高いか低い
かという固定的なパラメータで表されるため、優先度の
高い通信パケットは必要以上に優先処理されるという状
況が生じ、また、通信料金も一律に高くつくという問題
があった。

【００１５】本発明の目的は、このような問題を解決
し、帯域確保を行うことなく、リアルタイム性の高いデ
ータからリアルタイム性を問わないバルクデータまでの
幅広いデータを最適な優先度でルーティング処理でき、
ネットワークの帯域利用効率を向上可能な優先経路制御
方法及びルータ装置を提供することにある。

【００１６】

【課題を解決するための手段】上記目的を達成するた
め、請求項１記載の発明では、通信パケット毎にラベル
付けされた宛先アドレスに基づいて、通信パケットの経
路を切替制御して送り出す経路制御方法において、宛先
アドレスとともに送達希望時刻をラベル付けし、この送
達希望時刻に基づいてパケット処理の優先順位を決定
し、経路制御を行うことを特徴とする。

【００１７】前記構成によれば、個々の通信パケットを
送達希望時刻に応じた順序で経路制御でき、リアルタイ
ム性の高いデータから低いデータまで最適な優先度でル
ーティング処理できるとともに、ネットワークリソース
を有効活用できる。

【００１８】また、請求項２記載の発明では、通信パケ
ットの送信元アドレス及び宛先アドレスより求められる
送受信者間のメトリック値、または通信パケットの発信
時刻及び送達希望時刻より求められる送達希望時刻まで
の残り時間、あるいはメトリック値と送達希望時刻まで
の残り時間とから求められる値、もしくはこれらの組み
合わせ、をパラメータとして通信料金を決定することを
特徴とする。

【００１９】前記構成によれば、データリンクの伝送帯
域・距離のみによる課金処理に代えて、空間軸あるいは
時間軸における情報の移動距離に基づいて個々のパケッ
ト毎にきめ細かい課金を行うことができる。

【００２０】また、請求項３記載の発明では、ルータ装
置のアドレス及び通信パケットの宛先アドレスより求め
られるルータ装置から宛先までのメトリック値、または
現在時刻及び送達希望時刻より求められる送達希望時刻
までの残り時間、あるいはメトリック値と送達希望時刻
までの残り時間とから求められる値、もしくはこれらの
組み合わせ、をパラメータとしてパケット処理の優先順
位を決定し、経路制御を行うことを特徴とする。

【００２１】前記構成によれば、上位レイヤを終端する
ことなく、情報の属性に応じて処理の差別化を図ること
が可能となり、ネットワークリソースを効率的に運用で
きるとともに、各ルータ装置において個々のパケット毎
に配送が遅れているのかあるいは進んでいるのかを知る
ことができる。

【００２２】また、請求項４記載の発明では、インター
ネットプロトコルバージョン６仕様における通信パケッ
トの中継点オプションヘッダ内に通信パケットの発信時
刻及び送達希望時刻を格納して作成した通信パケットを
用いることを特徴とする。

【００２３】前記構成によれば、既存のＩＰｖ６のパケ
ットフォーマットを変更することなく、通信パケットに
時間軸情報を付与することができる。

【００２４】また、請求項５記載の発明では、処理能力
以上の通信パケットにより輻輳が発生した場合、優先度
が低い通信パケットをルータ装置内の記憶装置に一時的
に退避させ、送達希望時刻が近づいて退避中の通信パケ
ットの優先度が上がった場合、あるいは輻輳が収まった
場合に、記憶装置から通信パケットを読み出して経路制
御を再開させることを特徴とする。

【００２５】前記構成によれば、トラヒック輻輳時にお
けるパケットの破棄を軽減することが可能となる。

【００２６】また、請求項６記載の発明では、通信パケ
ットを送達希望時刻までの残り時間の単位別に待ち合わ
させ、該単位毎に異なる確率で転送処理する場合、待ち
合わせ中に送達希望時刻までの残り時間の単位が変化し
た時は待ち合わせの単位を変更することを特徴とする。

【００２７】前記構成によれば、送達希望時刻までの残
り時間に対応した適切な転送処理が可能となる。

【００２８】また、請求項７記載の発明では、通信パケ
ットを送達希望時刻までの残り時間の単位別に待ち合わ
させ、該単位毎に異なる確率で転送処理する場合、前記
単位毎の転送確率を、該単位毎の待ち合わせ中のパケッ
ト数に応じて変更することを特徴とする。

【００２９】前記構成によれば、送達希望時刻までの残
り時間に応じた待ち合わせ中のパケット数の極端な差を
なくすことができる。

【００３０】また、請求項８記載の発明では、インター
ネットプロトコルバージョン６仕様における通信パケッ
トの中継点オプションヘッダ内に、迂回した際の迂回元
のルータ装置のＩＤ、送達希望時刻とは無関係な優先
度、送達希望時刻を越えた場合の扱いを格納して作成し
た通信パケットを用いることを特徴とする。

【００３１】前記構成によれば、経路の変更が可能とな
り、また、通信パケットを待ち合わせなしで最優先で処
理したり、また、送達希望時刻を越えた通信パケットを
そのまま待ち合わせさせたり、廃棄したりを指示でき
る。

【００３２】また、請求項９記載の発明では、ルータ装
置内の記憶装置の使用量及び空き容量、リンクの使用状
況、リンク上の隣接するルータの数、隣接するルータま
での往復にかかる時間等の情報を格納したパケットを隣
接するルータ装置間で交換し、前記情報に基づいて隣接
するルータ装置までのメトリック値を求め、該求めたメ
トリック値を用いてルータ装置から宛先までのメトリッ
ク値を動的に変更することを特徴とする。

【００３３】前記構成によれば、ネットワークが込み合
うような状況においても適応的なルーティングが可能と
なり、送達希望時刻を満たすパケットが著しく減少する
ことを防止できる。

【００３４】そして、これらの優先経路制御方法は、複
数の入力ポート及び複数の出力ポートと、複数の入力ポ
ート及び複数の出力ポート間を任意に切替接続可能な空
間スイッチと、入力ポートから入力された通信パケット
をその宛先アドレスに対応する出力ポートへ送出するよ
う空間スイッチを制御する経路制御部とを有するルータ
装置において、複数の通信パケットの順序を任意に入れ
替え可能な時間スイッチと、複数の通信パケットの順序
が各通信パケットに付与された送達希望時刻に対応する
順序となるよう時間スイッチを制御する優先制御部とを
設けたルータ装置、通信パケットの送信元アドレス及び
宛先アドレスより求められる送受信者間のメトリック
値、または通信パケットの発信時刻及び送達希望時刻よ
り求められる送達希望時刻までの残り時間、あるいはメ
トリック値と送達希望時刻までの残り時間とから求めら
れる値、もしくはこれらの組み合わせ、をパラメータと
して通信料金を決定する手段を備えた請求項１０記載の
ルータ装置、自装置のアドレス及び通信パケットの宛先
アドレスより求められる自装置から宛先までのメトリッ
ク値、または現在時刻及び送達希望時刻より求められる
送達希望時刻までの残り時間、あるいはメトリック値と
送達希望時刻までの残り時間とから求められる値、もし
くはこれらの組み合わせ、をパラメータとしてパケット
処理の優先順位を決定し、時間スイッチを制御する優先
制御部を備えた請求項１０記載のルータ装置、インター
ネットプロトコルバージョン６仕様における通信パケッ
トの中継点オプションヘッダ内に格納された通信パケッ
トの発信時刻及び送達希望時刻を用いる優先制御部を備
えた請求項１０乃至１２いずれか記載のルータ装置、通
信パケットを一時的に記憶する記憶装置と、処理能力以
上の通信パケットが入力されて輻輳が発生した場合、優
先度が低い通信パケットを記憶装置に一時的に退避さ
せ、送達希望時刻が近づいて退避中の通信パケットの優
先度が上がった場合、あるいは輻輳が収まった場合に、
記憶装置から通信パケットを読み出して優先経路制御を
再開させる制御手段とを備えた請求項１０乃至１３いず
れか記載のルータ装置、送達希望時刻までの残り時間の
単位別に分割された時間スイッチと、待ち合わせ中に送
達希望時刻までの残り時間の単位が変化した一の時間ス
イッチ内の通信パケットを、該変化後の単位に対応する
時間スイッチへ移す手段とを備えた請求項１０乃至１４
いずれか記載のルータ装置、送達希望時刻までの残り時
間の単位別に分割された時間スイッチと、前記単位毎の
時間スイッチにおける通信パケットの取り出し確率を、
該単位毎の時間スイッチにおける待ち合わせ中のパケッ
ト数に応じて変更する手段とを備えた請求項１０乃至１
５いずれか記載のルータ装置、インターネットプロトコ
ルバージョン６仕様における通信パケットの中継点オプ
ションヘッダ内に格納された迂回した際の迂回元のルー
タ装置のＩＤ、送達希望時刻とは無関係な優先度、送達
希望時刻を越えた場合の扱いを用いる優先制御部を備え
た請求項１０乃至１６いずれか記載のルータ装置、ルー
タ装置内の記憶装置の使用量及び空き容量、リンクの使
用状況、リンク上の隣接するルータの数、隣接するルー
タまでの往復にかかる時間等の情報を格納したパケット
を作成し、隣接するルータ装置間で交換する手段と、前
記パケット内の情報に基づいて隣接するルータ装置まで
のメトリック値を計算する手段と、前記求めたメトリッ
ク値を用いてルータ装置から宛先までのメトリック値を
動的に変更する手段とを備えた請求項１０乃至１７いず
れか記載のルータ装置、によって実現される。

【００３５】

【発明の実施の形態】以下、本発明の優先経路制御方法
及びルータ装置の実施の形態について、図面を参照して
詳細に説明する。

【００３６】図２は本発明の優先経路制御方法を用いた
ルータ装置の基本構成を示すもので、図中、２１は複数
の入力ポート、２２はスイッチ部、２３は複数の出力ポ
ート、２４は経路制御部、２５は優先制御部、２６は通
信パケットである。

【００３７】スイッチ部２２は、複数の入力ポート２１
と複数の出力ポート２３との間を自在に接続できる空間
スイッチ２７と、本ルータ装置に入力される通信パケッ
トの出力順を並べ替え可能な時間スイッチ２８とからな
り、空間スイッチ２７は経路制御部２４により制御さ
れ、時間スイッチ２８は優先制御部２５により制御され
る。

【００３８】本ルータ装置に入力される通信パケット２
６には、ＩＰアドレスのようなネットワーク層の宛先ア
ドレス２６ａの他、通信パケットの相手先の「送達希望
時刻２６ｂ」が含まれる。図１に示したような空間スイ
ッチのみからなる従来のルータ装置とは異なり、スイッ
チ部２２を空間スイッチ２７及び時間スイッチ２８で構
成し、宛先を示すネットワーク層アドレス（ＩＰアドレ
ス）２６ａに基づいた経路制御（空間スイッチの切り替
え）に加え、新たに「送達希望時刻２６ｂ」に基づいて
通信パケットの送出順を優先制御することにより、ネッ
トワークリソースを有効利用できる。

【００３９】なお、本発明でいう「送達希望時刻」と
は、唯一の時点を示す時刻である場合とともに、ある時
間幅を持つ場合（時間幅の指定方法としては、送達希望
の開始時刻及び最終時刻を指定する、開始時刻または最
終時刻と時間（予め取り決めておくことにより省略も
可）を指定する等）も含むものとする。

【００４０】以上が、請求項１及び１０記載の発明につ
いての説明である。

【００４１】次に「送達希望時刻」に基づく通信パケッ
トの優先制御の原理を図３により説明する。

【００４２】図３では情報の伝達を時間軸及び空間軸か
らなる２次元空間上の移動と捉えて表現しており、該２
次元空間の情報伝達ベクトルとして示している。即ち通
信、情報の伝達とは、図３のような２次元空間上のある
位置ベクトルから位置ベクトルへの空間ベクトルとして
表現できる。

【００４３】この時、時間軸要素は時刻であり、時刻自
身を時間軸上のアドレスとして用いることができる。一
方、空間軸要素はＩＰアドレス等のネットワーク層のア
ドレスであり、ＩＰバージョン４（以下、「ＩＰｖ４」
と記す。）ならば３２ビットの一次元空間であり、ＩＰ
バージョン６（以下、「ＩＰｖ６」と記す。）ならば１
２８ビットの一次元空間である。

【００４４】時刻が線形空間であるのに対し、ＩＰアド
レス空間は線形空間でないため、ＩＰアドレス間の距離
としてルータ装置間のメトリック値を用いる。

【００４５】本発明では、情報の伝達を上記の時刻−ネ
ットワーク層アドレスによる２次元空間上の空間ベクト
ルとして表現し、ベクトルの時間軸成分、空間軸成分、
大きさ、偏角といった各要素により、通信パケットが運
ぶ情報属性を分類し、ルータ装置内における処理の優先
度等の差別化を図るようになしている。

【００４６】図４は情報伝達の空間ベクトルの要素を示
すものである。情報伝達の空間ベクトルｚにおける始点
＝情報の出発点の時間軸成分は発信時刻ｔ_s、空間軸成
分は送信元ネットワーク層アドレスｓ_sである。また、
情報伝達の空間ベクトルにおける終点＝情報の到着（希
望）点の時間軸成分は情報の送達希望時刻（送達期限）
ｔ_d、空間軸成分は送達先ネットワークアドレスｓ_dであ
る。

【００４７】空間軸上の移動距離｜ｓ_d−ｓ_s｜はルータ
装置間メトリック値を基準にしたエンド−エンドのパケ
ットの移動距離であり、時間軸上の移動距離｜ｔ_d−ｔ_s
｜はパケット発信時に要求された送達希望時刻までの残
り（余裕）時間である。

【００４８】これらに加え、情報伝達の大きさ ｜ｚ｜＝｛（ｔ_d−ｔ_s）²＋（ｓ_d−ｓ_s）²｝^1/2 は情報伝達のエンド−エンドでの時空間上の移動距離を
表し、偏角 Θ_z＝ａｒｃｔａｎ｛｜ｓ_d−ｓ_s｜／｜ｔ_d−ｔ_s｜｝ は単位時間当たりの空間軸上の移動距離に対応してい
る。

【００４９】時空間上の移動距離が等しい場合でも、偏
角Θ_zが大きい情報伝達は単位時間当たりより遠くへ伝
達される必要があり、偏角Θ_zは通信コストあるいは通
信料金の算出パラメータとして利用できる。また、偏角
Θ_zの値が同一であっても、時空間上の移動距離｜ｚ｜
が大きければ、通過するルータ装置数や伝送距離が大き
いことを意味するため、｜ｚ｜も通信コストあるいは通
信料金の算出パラメータとして利用できる。

【００５０】これまでのデータリンクの伝送帯域や距離
のみによる料金算出に代わり、空間軸の移動距離｜ｓ_d
−ｓ_s｜、時間軸の移動距離｜ｔ_d−ｔ_s｜や、時空間上
のベクトルの大きさ｜ｚ｜、偏角Θ_zといった個々のパ
ラメータ、あるいはそれらの組み合わせによってパケッ
ト毎のより細かな課金が行えるようになる。

【００５１】以上が、請求項２及び１１記載の発明につ
いての説明である。

【００５２】また、図４中のｙは通信途中のルータ装置
における情報伝達の空間ベクトルを表している。この
時、ベクトルの始点の時間軸成分はルータ装置内に情報
が存在する時の現在時刻ｔ_cを表し、空間軸成分はルー
タ装置のネットワーク層アドレスｓ_cを表す。従って、
ｙは通信途上のルータ装置から最終目的地までの情報伝
達の空間ベクトルである。

【００５３】｜ｓ_d−ｓ_c｜はルータ間メトリック値を元
にした当該ルータ装置から相手先アドレスまでの残りの
距離を表し、｜ｔ_d−ｔ_c｜は現時点での送達期限までの
残り（余裕）時間を表す。また、ベクトルの大きさ ｜ｙ｜＝｛（ｔ_d−ｔ_c）²＋（ｓ_d−ｓ_c）²｝^1/2 は通信パケットを処理する現在のルータ装置から最終到
達点まで、時空間上でどれだけ移動距離が残っているか
を表しており、偏角 Θ_y＝ａｒｃｔａｎ｛｜ｓ_d−ｓ_c｜／｜ｔ_d−ｔ_c｜｝ は送達希望時刻ｔ_dまでに情報を伝達し終わるために、
今後、単位時間当たり空間軸上を移動しなければならな
い距離を表している。

【００５４】これら情報伝達ベクトルの各成分｜ｓ_d−
ｓ_c｜、｜ｔ_d−ｔ_c｜、｜ｙ｜、Θ_yのいずれか、あるい
はこれらを組み合わせたものをパラメータとしてルータ
装置はパケットルーティング処理の優先度を決定する。

【００５５】次に、｜ｙ｜やΘ_yによるルータ装置内の
優先処理について、図３及び図４を参照して説明する。
図３ではリアルタイムデータ転送とファイルデータ転送
という２つの種類の異なる情報伝達を空間ベクトルとし
て表現している。リアルタイム転送では短時間のエンド
−エンド情報伝達が要求されるため、ファイルデータ転
送と比較してベクトルの偏角Θが大きい。

【００５６】途中のルータ装置では、偏角Θ_yの大きな
リアルタイムデータと偏角Θ_yの小さなファイルデータ
のいずれも処理しなければならない場合、偏角Θ_yの値
により処理の優先度を決定するのであれば、ファイルデ
ータをルータ装置内に蓄積し、待ち合わせを行うことで
優先度の高いリアルタイムデータを先に処理・送出する
ことが可能となる。

【００５７】このように従来のルータ装置とは異なり、
現在時刻と送達希望時刻の差異や空間軸上の残りの距離
から上位レイヤの終端をすることなく、情報の属性に応
じて処理の差別化を図ることが可能となり、ネットワー
クリソースを効率的に運用できる。

【００５８】以上が、請求項３及び１２記載の発明につ
いての説明である。

【００５９】また、送達希望時刻は、ルータ装置内での
廃棄メカニズムの目安として捉えることもできる。例え
ば、ルータ装置内で、送達希望時刻を過ぎたパケットに
ついてはこれを受信先へ送達しても意味の無い情報であ
ると判断できるため（リアルタイムで再生されるストリ
ームデータ等）、輻輳状態に至らなくともルータ装置内
で積極的に廃棄することができる（ルータ装置における
現在時刻ｔ_c＞送達希望時刻ｔ_dの場合）。

【００６０】また、偏角Θは現在時刻ｔ_cの関数である
ため、初期値Θ_zとルータ装置内での現在値Θ_yを比較す
ることで、通信パケットの送達が予定より遅れている
か、進んでいるかを判断することができ、これをルータ
装置内での処理の優先度に反映させることも可能とな
る。

【００６１】以上が、請求項３及び８記載の発明につい
ての補足説明である。

【００６２】図５はＩＰｖ６における時間軸情報の格納
例を示すものである。空間軸成分、即ち送信元ＩＰアド
レスｓ_s及び宛先のＩＰアドレスｓ_dはＩＰｖ６ヘッダと
してそれぞれ１２８ｂｉｔで表現されている。時間軸成
分、即ち発信時刻ｔ_sと、送達希望時刻ｔ_dはＩＰｖ６ヘ
ッダの後に続く中継点オプションヘッダを用いて、これ
らをそれぞれ３２ｂｉｔで表現し、格納する。

【００６３】ＩＰｖ６におけるヘッダ処理の優先度は、
ＩＰｖ６ヘッダ＞中継点オプションヘッダ（ｈｏｐ−ｂ
ｙ−ｈｏｐ ｏｐｔｉｏｎｓ ｈｅａｄｅｒ）＞終点オ
プションヘッダ（ｄｅｓｔｉｎａｔｉｏｎ ｏｐｔｉｏ
ｎｓ ｈｅａｄｅｒ）＞経路制御ヘッダ（ｒｏｕｔｉｎ
ｇ ｈｅａｄｅｒ）＞断片ヘッダ（ｆｒａｇｍｅｎｔｈ
ｅａｄｅｒ）＞認証ヘッダ（ａｕｔｈｅｎｔｉｃａｔｉ
ｏｎ ｈｅａｄｅｒ）＞暗号ペイロード（ｅｎｃａｐｓ
ｕｌａｔｉｎｇ ｓｅｃｕｒｉｔｙ ｐａｙｌｏａｄ）
＞終点オプションヘッダ＞上位層ヘッダ（ＴＣＰあるい
はＵＤＰ等）であり、中継点オプションヘッダは、オプ
ションヘッダとしては最も高い優先度で処理される。

【００６４】この時、先頭のＩＰｖ６ヘッダ内の次ヘッ
ダ番号には中継点オプションヘッダ（ＨＢＨ）を表現す
る「０」が入る。発信時刻、送達希望時刻を格納する中
継点オプションヘッダの次ヘッダ番号には次に続くヘッ
ダが例えば、ＴＣＰヘッダであれば「６」という値が格
納される。

【００６５】拡張ヘッダ長は当該中継点オプションヘッ
ダ長（１２８ビット）を８バイト単位（６４ビット）で
表現して−１した値、即ち「１」が入る。

【００６６】オプション番号は８ビットの識別子であ
り、上位２ビットでルータ装置がオプションを認識でき
なかった場合の動作を示し、次の１ビットでオプション
が配送経路上で変更可能かどうかを表し、下位５ビット
はオプションの内容を示すオプション番号部分となる。
本ルータ装置で用いるＩＰｖ６ヘッダの場合、動作は
「００」（認識できない場合は続み飛ばすという意）、
経路上変更可能ビットは「ＯＦＦ」、オプション番号部
分については、ＩＡＮＡ（Ｉｎｔｅｒｎｅｔ Ａｓｓｉ
ｇｎｅｄ Ｎｕｍｂｅｒｓ Ａｕｔｈｏｒｉｔｙ）に登
録することによってＲＦＣに記述される新しい番号を入
れる。オプションデータ長は当該オプションデータ長を
バイト表現したもので「１２」が入る。

【００６７】その後には発信時刻ｔ_s及び送達希望時刻
ｔ_dが、情報伝達ベクトルの始点及び終点アドレスとし
て３２ビットずつ格納される。中継点オプションヘッダ
の最後の４バイトは時刻情報の単位等の付加情報の格納
用として予約するが、時刻情報の単位をミリ秒（ｍ
ｓ）、秒（ｓ）、時間（ｈｏｕｒ）のように３段階で荒
く表現する場合はＩＰｖ６ヘッダの優先度（４ビット）
を利用して時刻情報の単位を表して（格納して）も良
い。

【００６８】以上が、請求項４及び１３記載の発明につ
いての説明である。

【００６９】ＩＰｖ６の中継点オプションヘッダを用い
ることで既存のＩＰｖ６のパケットフォーマットを変更
せずに時間軸成分を運ぶことができ、従来の時間軸成分
を情報として持たない既存のパケットと同等に処理する
ことも可能となる。

【００７０】また、パケットに格納される発信時刻や送
達希望時刻は、例えばＭＰＥＧファイルのような等時性
（アイソクロナス性）情報を運ぶ際の再生タイミングを
表現していると言える（ＭＰＥＧのＴＳフレームのよう
な）。即ち、通信パケットに添付されている送達希望時
刻は受信先でアイソクロナスデータを再生するタイムス
タンプとして利用できるため、ネットワークは遅延の揺
らぎを抑えるといったアイソクロナス性保証のための転
送メカニズムを実装する必要がなくなる。

【００７１】さらに、送達希望時刻は通信パケットの絶
対的なシーケンス番号とみなすことも可能であり、元情
報を再構成することが可能であるため、ネットワークは
通信パケット到着の順序性を保証する必要がなくなり、
ルータ装置はより簡便な転送メカニズムを実装できる。

【００７２】以上が、請求項４及び１３記載の発明につ
いての補足説明である。

【００７３】次に、本発明のルータ装置の具体例につい
て説明する。

【００７４】図６はルータ装置の全体構成を示すもの
で、同図(a)は全体斜視図、同図(b)は配線図である。図
中、３１Ａ，３１Ｂ，３１Ｃ，３１Ｄは全二重通信路を
有しかつ図２で述べた経路制御部、優先制御部及び時間
スイッチを構成する入出力部、３２はディスクアレイ用
コンピュータ（ＰＣ）、３３は入出力部３１Ａ〜３１Ｄ
及びディスクアレイ用ＰＣ３２間を空間的にスイッチン
グするスイッチ（ＳＷ）部、３４は制御用コンピュータ
（ＰＣ）、３５はこれらを接続する専用バックプレー
ン、３６はディスクアレイである。

【００７５】制御用ＰＣ３４には他のルータ装置との間
でリンクステート情報をやり取りするルーティングプロ
トコルが実装され、ルータ装置間の空間軸上の距離を測
定する如くなっている。

【００７６】前述した入出力部３１Ａ〜３１Ｄは全て同
一構成であり、図７にその詳細構成の一例、ここではネ
ットワークとのデータのやりとりを光信号で行うように
なした場合の例を示す。図中、３１１ａは光入力部（Ｏ
ｐｔ ｉｎ）、３１１ｂは光出力部（Ｏｐｔ ｏｕ
ｔ）、３１２はシリアル・パラレル変換器（Ｓ／Ｐ）、
３１３はデータリンク層終端部、３１４はＦＰＧＡ（Ｆ
ｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ ａｒ
ｒａｙ）、３１５は信号処理プロセッサ（ＤＳＰ）、３
１６ａ，３１６ｂ，３１６ｃはシンクロナスＳＲＡＭ
（ＳＳＲＡＭ）等からなる高速メモリ、３１７は連想メ
モリ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅ
ｍｏｒｙ：ＣＡＭ）、３１８はシンクロナス（ｓｙｎ
ｃ．）ＦＩＦＯメモリ、３１９はインタフェース部（Ｉ
／Ｆ）である。

【００７７】以下、入出力部が前述した経路制御部、優
先制御部及び時間スイッチを構成するようすをその動作
概要とともに説明する。

【００７８】図示しないネットワークから光ファイバを
介して届いたパケットデータは、光入力部３１１ａで光
電変換され、Ｓ／Ｐ３１２でシリアル・パラレル変換さ
れた後、ギガビットイーサネット（Ｇｉｇａｂｉｔ Ｅ
ｔｈｅｒｎｅｔ）等のデータリンク層終端部３１３を経
てＩＰデータグラムとして取り出され、ＦＰＧＡ３１４
において時間軸成分の精度（単位）により振り分けられ
る。

【００７９】ここで、時間軸成分の表示単位は、図５に
示したようにＩＰｖ６ヘッダの優先度あるいは時間軸成
分を格納する中継点オプションヘッダの末尾部分に格納
されている。図７の例では、時間軸成分の単位をミリ秒
（ｍｓ）、秒（ｓ）、時間（ｈｏｕｒ）の３段階に分類
している。

【００８０】ＦＰＧＡ３１４により時間軸成分の表示単
位毎に分類されたデータはＩＰデータグラムのまま、ミ
リ秒（ｍｓ）用，秒（ｓ）用，時間（ｈｏｕｒ）用の高
速メモリ３１６ａ，３１６ｂ，３１６ｃへ格納される。
この時、ＩＰデータグラムはメモリ内に順に格納され、
メモリはリングバッファとして利用される。

【００８１】一方、高速メモリ３１６ａ〜３１６ｃへ格
納されるＩＰデータグラムのヘッダ部（中継点オプショ
ンヘッダを含む。）は、経路計算及び情報伝達ベクトル
の偏角Θ_y計算用のＤＳＰ３１５へ渡される。

【００８２】ＤＳＰ３１５はＩＰヘッダの相手先アドレ
スｓ_dから経路を計算し、当該パケットをどの方路から
送出すべきか、即ちＳＷ部３３を介して次にどの入出力
部へ送出すべきかを決定する。

【００８３】この方路情報は、時間軸成分の単位、高速
メモリ３１６ａ〜３１６ｃへＩＰパケットを格納した際
のライトアドレス（ｗｐ）とともにＣＡＭ３１７へ格納
される。この時、｛方路、単位、ｗｐ｝を格納するＣＡ
Ｍ３１７のライトアドレスはＤＳＰ３１５で計算された
Θ_yの逆数を用いる。

【００８４】ＣＡＭ３１７は通常のメモリとは異なり、
アドレスを与えて格納されているデータへアクセスする
のではなく、検索ワードを与え、これに一致するデータ
が格納されているアドレスを知るというメモリである。

【００８５】例えば、ＣＡＭ３１７に検索ワードとし
て、方路及び単位を与えることで、特定の方路及び単位
の情報だけを取り出すことができる。方路及び単位が一
致する情報が複数格納されている場合、ＣＡＭ３１７は
格納されているデータの中から最小アドレスを返すた
め、｛方路、単位、ｗｐ｝を格納するＣＡＭ３１７のラ
イトアドレスにΘ_yの逆数を用いることで、特定方路行
きの特定単位の最大Θ_y情報、即ち最大Θ_yを持つＩＰデ
ータグラムの高速メモリ３１６ａ〜３１６ｃへの格納位
置ｗｐを知ることができる。

【００８６】こうして得られたｗｐを高速メモリ３１６
ａ〜３１６ｃのリードアドレス（ｒｐ）に用いること
で、常に特定方路行きの特定単位の最大Θ_yを持つＩＰ
データグラムを高速メモリ３１６ａ〜３１６ｃから取り
出すことができる。

【００８７】このようにしてＩＰデータグラムの中から
取り出された、最大のΘ_yとなるＩＰデータグラムはＩ
／Ｆ３１９を経て、バックプレーン３５を介してＳＷ部
３３へ転送される。

【００８８】一方、ＳＷ部３３からバックプレーン３５
を介して到着したＩＰデータグラムは、Ｉ／Ｆ３１９を
経てＳｙｎｃ．ＦＩＦＯメモリ３１８で受信される。Ｓ
ｙｎｃ．ＦＩＦＯメモリ３１８に格納されたＩＰデータ
グラムは順次、データリンク層終端部３１３、Ｓ／Ｐ３
１２、光出力部３１１ｂへ送られ、光信号に変換されて
ネットワークへ送出される。

【００８９】図８は前述したスイッチ部（ＳＷ部）の詳
細構成を示すもので、同図(a)は回路構成図、同図(b)は
切替接続の説明図である。図中、３３１は高速クロスバ
スイッチチップで構成される５×５スイッチ構成のクロ
スバスイッチであり、その５つの入力ポート及び出力ポ
ートには４つの入出力部３１Ａ〜３１Ｄとともに、ディ
スクアレイ用ＰＣ３２が接続されている。また、３３２
は切替制御用のＣＰＵであり、クロスバスイッチ３３１
を、タイミングを管理しつつ、同図(b)に示すような各
入出力ポートのｌ対１接続を全て網羅する５つのフェー
ズに切り替え制御する如くなっている。なお、フェーズ
とフェーズとの間にはガードタイムが設定されている。

【００９０】ディスクアレイ用ＰＣ３２は、送達希望時
刻ｔ_dが∞（無限大）に設定されているような優先度の
低いＩＰデータグラムを格納するための大容量の記憶装
置、ここではディスクアレイ３６を制御するためのもの
である。

【００９１】送達希望時刻までの余裕が大きい場合や、
送達希望時刻が無限大に設定されているような通信パケ
ットは、入出力部３１Ａ〜３１ＤからＳＷ部３３及びＰ
Ｃ３２を介して、一旦、ディスクアレイ３６に蓄積さ
れ、然るべき時間経過を待ってＰＣ３２及びＳＷ部３３
を介して再度、入出力部へ読み出される。

【００９２】この際、送達希望時刻を無限大に設定する
ことにより、時刻を問わず送達して構わないデータであ
ることを指定できるので、ルータ装置内の記憶装置に蓄
積しながら、確実に伝達されるという情報伝達サービス
クラスを新たに定義することができる。また、トラフィ
ック輻輳時においても低優先度パケットを廃棄するので
はなく、記憶装置に待避させることができるため、パケ
ット廃棄率を改善でき、その結果、エンド−エンドの簡
便な送達確認メカニズムを持つトランスポートレイヤに
より信頼性の高いデータ転送が実現できる。

【００９３】以上の説明のうち、ディスクアレイ３６に
データを退避させる点が、請求項５及び１４記載の発明
と対応している。

【００９４】ところで、前述した実施の形態において、
高速メモリ３１６ａ〜３１６ｃへのパケットデータの格
納は、時間軸成分の単位（ミリ秒、秒、時間）毎に単純
に受信した順に行われ、また、高速メモリ３１６ａ〜３
１６ｃからのパケットデータの取り出しは、方路毎及び
時間軸成分の単位毎に単純に優先度（Θ_y）の高い順に
行われていた。

【００９５】従って、ネットワークが込み合うような状
況下において、ある時間軸成分の単位、例えば時間
（ｈ）に対応したメモリ３１６ｃ内に格納されたパケッ
トデータの送達希望時刻までの残り（余裕）時間が少な
くなったりしても、他のメモリ３１６ａ，３１６ｂ内の
パケットデータの転送が優先され、その結果、メモリ３
１６ｃに格納されたパケットデータの送達希望時刻が守
られなくなる場合があり得るという問題があった。

【００９６】図９は前述した点を改良した本発明のルー
タ装置の実施の形態の他の例の要部、ここでは高速メモ
リ３１６ａ〜３１６ｃに対するパケットデータの格納
（キューイング：ｑｕｅｕｉｎｇ）及び取り出し制御に
かかわる部分を示すものである。

【００９７】本実施の形態では、各高速メモリ３１６ａ
〜３１６ｃ内におけるパケットデータのキューイングを
優先度（Θ_y）順に行うとともに、待ち合せ等によって
送達希望時刻までの残り時間の単位（オーダ）が変化し
た場合にはキューイングするメモリそのものを変更す
る。また、パケットデータの取り出しは高速メモリ３１
６ａ〜３１６ｃ毎に優先度の高いものから行うが、各高
速メモリ３１６ａ〜３１６ｃからの取り出し（転送）確
率（割合）を、キューイングしているデータ量に応じて
変化させる。

【００９８】前述した各高速メモリ３１６ａ〜３１６ｃ
内におけるパケットデータの優先度順のキューイング
は、連想メモリ３１７から優先度順に取り出されるアド
レスによって並べ替えることにより実現され、優先度
（Θ_y）が高いものほど各高速メモリ３１６ａ〜３１６
ｃの先頭（出口）に近く、低いものほど後尾（入口）に
近くなるように配列される。

【００９９】各高速メモリ３１６ａ〜３１６ｃに格納さ
れたパケットデータは、それぞれのメモリ内で優先度の
高いもの、即ちＡ、Ｂ、Ｃから取り出される。

【０１００】この際、長時間の待ち合わせ等により送達
希望時刻までの残り時間のオーダが変化してしまった場
合、例えばオーダが時間（ｈ）のメモリ３１６ｃ内のパ
ケットＣの送達希望時刻までの残り時間が５９分５９秒
以下になった場合、オーダ遷移制御部４１によりｃ１の
ルートを通って速やかに秒（ｓ）のメモリ３１６ｂの最
後尾に移る。また、同様にオーダが秒（ｓ）のメモリ３
１６ｂ内のパケットＢの送達希望時刻までの残り時間が
９９９ｍｓ以下になった場合、オーダ遷移制御部４１に
よりｂ１のルートを通ってミリ秒（ｍｓ）のメモリ３１
６ａの最後尾に移る。これは連想メモリ３１７における
時間軸成分の単位のビットを書き替えることにより実現
される。

【０１０１】また、各高速メモリ３１６ａ〜３１６ｃか
らのパケットデータの取り出しに関しては取り出し制御
部４２によって、さらに詳細に制御される。

【０１０２】即ち、取り出し制御部４２は各メモリ３１
６ａ〜３１６ｃ内の格納パケットデータ数（キューの長
さ）の変動を観測しており、それによりメモリ３１６ａ
〜３１６ｃ毎の取り出し確率を変化させる。但し、取り
出し確率は０＜確率＜ｌの範囲での変動とし、待ち合わ
せ及び到着パケットの全くないメモリが存在しない限
り、特定のメモリのみから取り出したり、特定のメモリ
に関して全く取り出さなかったりということはない。

【０１０３】図１０、図１１はパケットの受信時のキュ
ーイング及びオーダ遷移制御アルゴリズムを表すフロー
チャートである。また、図１２〜図１４はパケット送信
時の取り出し制御アルゴリズムを表すフローチャートで
ある。

【０１０４】以上が、請求項６、７及び１５、１６記載
の発明についての説明である。

【０１０５】図１５は図５と同様、ＩＰｖ６における時
間軸情報の他の格納例を示すものである。ここで、送達
希望時刻としてｔｄ１，ｔｄ２という２種類が存在する
が、これは送達希望時刻としてｔｄ１より後、ｔｄ２よ
り前という指定を可能とするものである。即ち、図５と
同様のｔｄの扱いにするためにはｔｄ１＝０とすれば良
く、また、ｔｄ１＝ｔｄ２とした場合は、ちょうどその
時刻に送達されるようにパケットの転送を行う。

【０１０６】また、送信先が込み合っている場合等で迂
回を行う時、パケットループを防ぐために迂回元のルー
タＩＤを記述する。迂回していない場合は「０」であ
る。この変更を行うため、オプションタイプの経路上変
更可能ビットは図５と異なり、「１」となる。

【０１０７】さらに優先度及び時刻ｔｄのオーダのフィ
ールドを設ける。優先度が「１」の場合、最も優先度が
高いものとして、ルータが受信したパケットはキューイ
ングを行わずに素早く次のルータへ送る。この場合、送
達希望時刻のフィールドは参照せず、従って優先度Θの
計算も行わない。「０」の場合は通常通り、送達希望時
刻のオーダ毎のキューイングを行う。

【０１０８】また、このフィールド最後のビットを用い
て、送達希望時刻を越えたパケットの扱いを指定する。
「１」の場合は送達希望時刻を越えても捨てずに配送を
行う。「０」の場合は送達希望時刻を越えたパケットは
廃棄する。

【０１０９】以上が、請求項８及び１７記載の発明につ
いての説明である。

【０１１０】また、これまでの説明におけるルーティン
グプロトコルでは、固定的なメトリック値を用いてお
り、ネットワークを流れるトラフィックの変動に起因す
る、利用可能帯域の変動等による目的地までの処要時間
の変化に対して有効な対策を取り得ない。即ち、途中の
ルータが動作不能になる等、パケットが到達不能になら
ない限り、輻輳により転送効率が落ち、パケットロスが
発生し始めても、ルーティングテーブル作成時に「最短
である」とみなされた経路を採り続けるという問題が生
じる。このため、ネットワークのトラフィック状況によ
っては送達希望時刻を満たすパケットが著しく減少する
可能性がある。

【０１１１】前述した問題は隣接するルータ装置間でネ
ットワーク状況に関する情報を交換し、メトリック値を
動的に変更可能とすることにより解決できる。

【０１１２】図１６はＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓ
ｙｓｔｅｍ：自律システム）内のルーティング情報の伝
播の一例として、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓ
ｔＰａｔｈ Ｆｉｒｓｔ）のＬＳＡ（Ｌｉｎｋ Ｓｔａ
ｔｅ Ａｄｖｅｒｔｉｓｅｍｅｎｔ）パケットにおける
隣接ルータとの交換情報の格納例である。

【０１１３】詳しい情報の交換は隣接ルータとのみ行う
ため、ｆｌｏｏｄｉｎｇ ｓｃｏｐｅはＬｉｎｋ Ｌｏ
ｃａｌである。ここでいうＣＬＡＳＳはキュー（高速メ
モリ）の数と一致しており、ｍｓ，ｓ，ｈの３つのキュ
ーを持つのであればＣＬＡＳＳ＝３となる。

【０１１４】また、低優先度のパケットを退避させるた
め、大容量の半導体メモリ及びハードディスクをストレ
ージとして用いる場合は、その後のＳＴＲビットを立て
る。また、ｉｆ＿ｎｕｍはルータに挿してあるインタフ
ェースの総数である（但し、コミュニケーションポート
等、管理の時にしか使用しないインタフェースは除
く。）。ｑｌｅｎ＿ｕｓｅｄは各キュー内にキューイン
グされているパケット数であり、ｑｌｅｎ＿ｕｎｕｓｅ
ｄは各キューの空き、即ち格納可能なパケット数を示し
ている。

【０１１５】ｍｂｕｆ＿ｕｓｅｄ、ｍｂｕｆ＿ｕｎｕｓ
ｅｄはそれぞれメモリバッファの使用量、空き容量をｂ
ｙｔｅｓ単位で表す値である。同様にｍｅｍｏｒｙ＿ｕ
ｓｅｄ、ｍｅｍｏｒｙ＿ｕｎｕｓｅｄ及びｄｉｓｋ＿ｕ
ｓｅｄ、ｄｉｓｋ−ｕｎｕｓｅｄもストレージに関する
使用量、空き容量をＫｂｙｔｅｓ単位で表す値である。
これらのパケット数、容量は測定時の瞬間的な値ではな
く、ある時間区間毎の平均値である。

【０１１６】さらにｔｒ＿ｉｆはインタフェース毎の情
報をメンバに持つ構造体である。ｔｒ＿ｉｆ．ｉｎｔｅ
ｒｆａｃｅ＿ｉｄはルータ内でインタフェースを一意に
識別するＩＤであり、ｔｒ＿ｉｆ．ｉｆ＿ｂａｕｄｒａ
ｔｅはインタフェースの物理速度を示す。

【０１１７】ｔｒ＿ｉｆ．ｓｔａｔｉｓｔｉｃｓは一秒
あたりのそのインタフェースを経由してルータ内に入っ
てきたパケットのｂｙｔｅｓ数を示す。ｐｏｉｎｔ−ｔ
ｏ−ｐｏｉｎｔのリンクであれば、この数値がリンクの
使用状況を示し、また、ｐｏｉｎｔ−ｔｏ−ｍｕｌｔｉ
ｐｏｉｎｔのリンクであれば、リンク上の全てのルータ
のｓｔａｔｉｓｔｉｃｓを集計したものがリンクの使用
状況となる。

【０１１８】ｔｒ＿ｉｆ．ｒｏｕｔｅ＿ｎｕｍはそのリ
ンク上の隣接ルータの数である。ｔｒ＿ｉｆ．ｒｏｕｔ
ｅｒ＿ｉｄは隣接ルータのｉｄであり、ｔｒ＿ｉｆ．ｒ
ｔｔはその隣接ルータまでの往復にかかる時間ＲＴＴ
（Ｒｏｕｎｄ Ｔｒｉｐ Ｔｉｍｅ）である。

【０１１９】これらの情報を隣接ルータ間で交換し、隣
接ルータまでのメトリック値をそれぞれ計算する。その
際、各ルータへのメトリック値をｍｓ，ｓ，ｈ用にそれ
ぞれ３種類計算する。この計算式は得られた情報の関数
として計算される。よってメトリック値は動的なものと
なり、このうちｍｓのメトリック値を代表値としてＡＳ
内全てのルータにｆｌｏｏｄｉｎｇにより配布する。こ
のメトリック値を図３における空間アドレス上の距離に
相当するものとしてΘ_yを計算する。

【０１２０】ここで、ルータＣに対し隣接ルータＡから
送られる交換情報が構造体Ａのメンバとして与えられた
とし、ルータＡ内のｍｓのキューに存在するパケット数
の平均値及び格納可能なパケットの数の平均値がそれぞ
れＡ．ｑｌｅｎ＿ｕｓｅｄ［０］及びＡ．ｑｌｅｎ＿ｕ
ｎｕｓｅｄ［０］、また、同様にＡ内のメモリバッファ
の使用量及び残容量がそれぞれＡ．ｍｂｕｆ＿ｕｓｅｄ
及びＡ．ｍｂｕｆ＿ｕｎｕｓｅｄ、さらにルータＡとの
ＲＴＴがＡ．ＲＴＴ、ルータＡが存在するリンクの物理
速度をＡ．ｉｆ＿ｂａｕｄｒａｔｅ、ルータＡが存在す
るリンク上のルータＣに対する全ての隣接ルータより得
た使用状況から算出した当該リンクの使用状況をＡ．ｓ
ｔａｔｉｓｔｉｃｓとして与えられたとすると、これら
を用いて隣接ルータＡへのｍｓにおけるメトリック値｜
Ｓ_A−Ｓ_C｜_msを表すと、 ｜Ｓ_A−Ｓ_C｜_ms＝ｆ（Ａ．ｑｌｅｎ＿ｕｓｅｄ［０］，
Ａ．ｑｌｅｎ＿ｕｎｕｓｅｄ［０］，Ａ．ｍｂｕｆ＿ｕ
ｓｅｄ，Ａ．ｍｂｕｆ＿ｕｎｕｓｅｄ，Ａ．ｒｔｔ，
Ａ．ｉｆ＿ｂａｕｄｒａｔｅ，Ａ．ｓｔａｔｉｓｔｉｃ
ｓ） となる。以下、同様にｓ，ｈにおけるメトリック値は、 ｜Ｓ_A−Ｓ_C｜_s＝ｇ（Ａ．ｑｌｅｎ＿ｕｓｅｄ［１］，
Ａ．ｑｌｅｎ＿ｕｎｕｓｅｄ［１］，Ａ．ｍｂｕｆ＿ｕ
ｓｅｄ，Ａ．ｍｂｕｆ＿ｕｎｕｓｅｄ，Ａ．ｍｅｍｏｒ
ｙ＿ｕｓｅｄ，Ａ．ｍｅｍｏｒｙ＿ｕｎｕｓｅｄ，Ａ．
ｒｔｔ，Ａ．ｉｆ＿ｂａｕｄｒａｔｅ，Ａ．ｓｔａｔｉ
ｓｔｉｃｓ） ｜Ｓ_A−Ｓ_C｜_h＝ｈ（Ａ．ｑｌｅｎ＿ｕｓｅｄ［２］，
Ａ．ｑｌｅｎ＿ｕｎｕｓｅｄ［２］，Ａ．ｍｂｕｆ＿ｕ
ｓｅｄ，Ａ．ｍｂｕｆ＿ｕｎｕｓｅｄ，Ａ．ｄｉｓｋ＿
ｕｓｅｄ，Ａ．ｄｉｓｋ＿ｕｎｕｓｅｄ，Ａ．ｒｔｔ，
Ａ．ｉｆ＿ｂａｕｄｒａｔｅ，Ａ．ｓｔａｔｉｓｔｉｃ
ｓ） となる。

【０１２１】ｆ（），ｇ（），ｈ（）の具体例として、
以下の数式を示す。

【０１２２】｜Ｓ_A−Ｓ_C｜_ms＝｛α_ms（Ａ．ｑｌｅｎ＿
ｕｓｅｄ［０］＋β_msＡ．ｑｌｅｎ＿ｕｎｕｓｅｄ
［０］）＋γ_ms（Ａ．ｍｂｕｆ＿ｕｓｅｄ＋δ_msＡ．ｍ
ｂｕｆ＿ｕｎｕｓｅｄ）｝・Ａ．ｒｔｔ／｛１・１・
（Ａ．ｉｆ＿ｂａｕｄｒａｔｅ−Ａ．ｓｔａｔｉｓｔｉ
ｃｓ）｝ ｜Ｓ_A−Ｓ_C｜_s＝｛α_s（Ａ．ｑｌｅｎ＿ｕｓｅｄ［１］
＋β_sＡ．ｑｌｅｎ＿ｕｎｕｓｅｄ［１］）＋γ_s（Ａ．
ｍｂｕｆ＿ｕｓｅｄ＋δ_sＡ．ｍｂｕｆ＿ｕｎｕｓｅ
ｄ）＋ε_s（Ａ．ｍｅｍｏｒｙ＿ｕｓｅｄ＋ζ_sＡ．ｍｅ
ｍｏｒｙ＿ｕｎｕｓｅｄ）｝・Ａ．ｒｔｔ／｛１・１・
（Ａ．ｉｆ＿ｂａｕｄｒａｔｅ−Ａ．ｓｔａｔｉｓｔｉ
ｃｓ）｝ ｜Ｓ_A−Ｓ_C｜_h＝｛α_h（Ａ．ｑｌｅｎ＿ｕｓｅｄ［２］
＋β_hＡ．ｑｌｅｎ＿ｕｎｕｓｅｄ［２］）＋γ_h（Ａ．
ｍｂｕｆ＿ｕｓｅｄ＋δ_hＡ．ｍｂｕｆ＿ｕｎｕｓｅ
ｄ）＋ε_h（Ａ．ｄｉｓｋ＿ｕｓｅｄ＋ζ_hＡ．ｄｉｓｋ
＿ｕｎｕｓｅｄ）｝・Ａ．ｒｔｔ／｛１・１・（Ａ．ｉ
ｆ＿ｂａｕｄｒａｔｅ−Ａ．ｓｔａｔｉｓｔｉｃｓ）｝ 上式中、１は全て１秒を表しており、それぞれの式を無
次元化するために挿入してある。また、αは平均パケッ
トサイズ、β〜ζは全て実定数であり、γ，εに関して
は正、β，δ，ζに関しては負である。

【０１２３】このｍｓ，ｓ，ｈにおける３種のメトリッ
ク値を用い、それぞれでルーティングテーブルを作成す
る。但し、他のルータに配布するメトリック値は前述の
通りｍｓのメトリック値のみであり、逆に他のルータか
ら配布されてくるメトリック値もｍｓのもののみであ
る。即ち、３種のメトリック値は自ルータから隣接ルー
タまでのメトリック値のみであり、ｓ，ｈのメトリック
値によるルーティングテーブルは迂回に用いる。

【０１２４】即ち、代表として他のルータに配布するｍ
ｓのメトリック値を最適なパスとして通常用いるが、そ
のパスが込み合ってきた場合、ｓ，ｈのオーダのキュー
にあるパケットに関してはｓ，ｈのメトリック値による
ルーティングテーブルを参照し、迂回が可能であれば迂
回を行う。その際、図１５に示したＩＰｖ６の中継点オ
プションヘッダ内に迂回元ルータＩＤを記述する。

【０１２５】以上が、請求項９及び１８記載の発明につ
いての説明である。

【０１２６】

【発明の効果】以上説明したように、本発明によれば、
以下のような効果を得ることができる。

【０１２７】即ち、請求項１記載の発明によれば、個々
の通信パケットを送達希望時刻に応じた順序で経路制御
でき、リアルタイム性の高いデータから低いデータまで
最適な優先度でルーティング処理できるとともに、ネッ
トワークリソースを有効活用できる。

【０１２８】また、請求項２記載の発明によれば、デー
タリンクの伝送帯域・距離のみによる課金処理に代え
て、空間軸あるいは時間軸における情報の移動距離に基
づいて個々のパケット毎にきめ細かい課金を行うことが
できる。

【０１２９】また、請求項３記載の発明によれば、上位
レイヤを終端することなく、情報の属性に応じて処理の
差別化を図ることが可能となり、ネットワークリソース
を効率的に運用でき、また、各ルータ装置において、個
々のパケット毎に配送が遅れているのか、あるいは進ん
でいるのかを知ることができる。

【０１３０】また、請求項４記載の発明によれば、既存
のＩＰｖ６のパケットフォーマットを変更することな
く、通信パケットに時間軸情報を付与することができ
る。

【０１３１】また、請求項５記載の発明によれば、トラ
ヒック輻輳時においてパケットの破棄を軽減することが
可能となる。

【０１３２】また、請求項６記載の発明によれば、送達
希望時刻までの残り時間に対応した適切な転送処理が可
能となり、可能な限り送達希望時刻を満たすような配送
が可能となる。

【０１３３】また、請求項７記載の発明によれば、送達
希望時刻までの残り時間に応じた待ち合わせ中のパケッ
ト数の極端な差をなくすことができ、可能な限り送達希
望時刻を満たすような配送が可能となる。

【０１３４】また、請求項８記載の発明によれば、経路
の変更が可能となり、また、通信パケットを待ち合わせ
なしで最優先で処理したり、また、送達希望時刻を越え
た通信パケットをそのまま待ち合わせさせたり、廃棄し
たりを指示できる。

【０１３５】また、請求項９記載の発明によれば、ネッ
トワークが込み合うような状況においても適応的なルー
ティングが可能となり、送達希望時刻を満たすパケット
が著しく減少することを防止できる。

【０１３６】また、請求項１０乃至１８の発明によれ
ば、前述した優先経路制御を実行可能なルータ装置を提
供できる。

【図面の簡単な説明】

【図１】従来のルータ装置の一例を示すブロック構成図

【図２】本発明のルータ装置の基本構成を示すブロック
構成図

【図３】送達希望時刻に基づく通信パケットの優先制御
の原理の説明図

【図４】情報伝達の空間ベクトルの要素の説明図

【図５】ＩＰｖ６における時間軸情報の格納例の説明図

【図６】本発明のルータ装置の実施の形態の一例を示す
構成図

【図７】図６中の入出力部の詳細構成図

【図８】図６中のスイッチ部の詳細構成図

【図９】本発明のルータ装置の実施の形態の他の例の要
部を示す構成図

【図１０】パケット受信時のキューイング及びオーダ遷
移制御アルゴリズムを表すフローチャート

【図１１】パケット受信時のキューイング及びオーダ遷
移制御アルゴリズムを表すフローチャート

【図１２】パケット送信時の取り出し制御アルゴリズム
を表すフローチャート

【図１３】パケット送信時の取り出し制御アルゴリズム
を表すフローチャート

【図１４】パケット送信時の取り出し制御アルゴリズム
を表すフローチャート

【図１５】ＩＰｖ６における時間軸情報の他の格納例の
説明図

【図１６】ＬＳＡパケットにおける隣接ルータ装置との
交換情報の格納例の説明図

【符号の説明】

２１：入力ポート、２２：スイッチ部、２３：出力ポー
ト、２４：経路制御部、２５：優先制御部、２６：通信
パケット、２６ａ：宛先アドレス、２６ｂ：送達希望時
刻、２７：空間スイッチ、２８：時間スイッチ、３１
Ａ，３１Ｂ，３１Ｃ，３１Ｄ：入出力部、３２：ディス
クアレイ用ＰＣ、３３：スイッチ（ＳＷ）部、３４：制
御用ＰＣ、３５：バックプレーン、３６：ディスクアレ
イ、３１１ａ：光入力部（Ｏｐｔ ｉｎ）、３１１ｂ：
光出力部（Ｏｐｔ ｏｕｔ）、３１２：シリアル・パラ
レル変換器（Ｓ／Ｐ）、３１３：データリンク層終端
部、３１４：ＦＰＧＡ、３１５：信号処理プロセッサ
（ＤＳＰ）、３１６ａ〜３１６ｃ：高速メモリ、３１
７：連想メモリ（ＣＡＭ）、３１８：シンクロナス（ｓ
ｙｎｃ．）ＦＩＦＯメモリ、３１９：インタフェース部
（Ｉ／Ｆ）、３３１：クロスバスイッチ、３３２：制御
用ＣＰＵ、４１：オーダ遷移制御部、４２：取り出し制
御部。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 尾花 和昭 東京都新宿区西新宿３丁目19番２号 日本 電信電話株式会社内 Ｆターム(参考） 5K030 GA03 HC01 HD03 LB05 9A001 JJ18 KK56

Claims (18)

【特許請求の範囲】
1. 【請求項１】 通信パケット毎にラベル付けされた宛先
   アドレスに基づいて、通信パケットの経路を切替制御し
   て送り出す経路制御方法において、 宛先アドレスとともに送達希望時刻をラベル付けし、 この送達希望時刻に基づいてパケット処理の優先順位を
   決定し、経路制御を行うことを特徴とする優先経路制御
   方法。
2. 【請求項２】 通信パケットの送信元アドレス及び宛先
   アドレスより求められる送受信者間のメトリック値、ま
   たは通信パケットの発信時刻及び送達希望時刻より求め
   られる送達希望時刻までの残り時間、あるいはメトリッ
   ク値と送達希望時刻までの残り時間とから求められる
   値、もしくはこれらの組み合わせ、をパラメータとして
   通信料金を決定することを特徴とする請求項１記載の優
   先経路制御方法。
3. 【請求項３】 ルータ装置のアドレス及び通信パケット
   の宛先アドレスより求められるルータ装置から宛先まで
   のメトリック値、または現在時刻及び送達希望時刻より
   求められる送達希望時刻までの残り時間、あるいはメト
   リック値と送達希望時刻までの残り時間とから求められ
   る値、もしくはこれらの組み合わせ、をパラメータとし
   てパケット処理の優先順位を決定し、経路制御を行うこ
   とを特徴とする請求項１記載の優先経路制御方法。
4. 【請求項４】 インターネットプロトコルバージョン６
   仕様における通信パケットの中継点オプションヘッダ内
   に通信パケットの発信時刻及び送達希望時刻を格納して
   作成した通信パケットを用いることを特徴とする請求項
   １乃至３いずれか記載の優先経路制御方法。
5. 【請求項５】 処理能力以上の通信パケットにより輻輳
   が発生した場合、 優先度が低い通信パケットをルータ装置内の記憶装置に
   一時的に退避させ、 送達希望時刻が近づいて退避中の通信パケットの優先度
   が上がった場合、あるいは輻輳が収まった場合に、記憶
   装置から通信パケットを読み出して経路制御を再開させ
   ることを特徴とする請求項１乃至４いずれか記載の優先
   経路制御方法。
6. 【請求項６】 通信パケットを送達希望時刻までの残り
   時間の単位別に待ち合わさせ、該単位毎に異なる確率で
   転送処理する場合、待ち合わせ中に送達希望時刻までの
   残り時間の単位が変化した時は待ち合わせの単位を変更
   することを特徴とする請求項１乃至５いずれか記載の優
   先経路制御方法。
7. 【請求項７】 通信パケットを送達希望時刻までの残り
   時間の単位別に待ち合わさせ、該単位毎に異なる確率で
   転送処理する場合、前記単位毎の転送確率を、該単位毎
   の待ち合わせ中のパケット数に応じて変更することを特
   徴とする請求項１乃至６いずれか記載の優先経路制御方
   法。
8. 【請求項８】 インターネットプロトコルバージョン６
   仕様における通信パケットの中継点オプションヘッダ内
   に、迂回した際の迂回元のルータ装置のＩＤ、送達希望
   時刻とは無関係な優先度、送達希望時刻を越えた場合の
   扱いを格納して作成した通信パケットを用いることを特
   徴とする請求項１乃至７いずれか記載の優先経路制御方
   法。
9. 【請求項９】 ルータ装置内の記憶装置の使用量及び空
   き容量、リンクの使用状況、リンク上の隣接するルータ
   の数、隣接するルータまでの往復にかかる時間等の情報
   を格納したパケットを隣接するルータ装置間で交換し、 前記情報に基づいて隣接するルータ装置までのメトリッ
   ク値を求め、 該求めたメトリック値を用いてルータ装置から宛先まで
   のメトリック値を動的に変更することを特徴とする請求
   項１乃至８いずれか記載の優先経路制御方法。
10. 【請求項１０】 複数の入力ポート及び複数の出力ポー
    トと、複数の入力ポート及び複数の出力ポート間を任意
    に切替接続可能な空間スイッチと、入力ポートから入力
    された通信パケットをその宛先アドレスに対応する出力
    ポートへ送出するよう空間スイッチを制御する経路制御
    部とを有するルータ装置において、 複数の通信パケットの順序を任意に入れ替え可能な時間
    スイッチと、 複数の通信パケットの順序が各通信パケットに付与され
    た送達希望時刻に対応する順序となるよう時間スイッチ
    を制御する優先制御部とを設けたことを特徴とするルー
    タ装置。
11. 【請求項１１】 通信パケットの送信元アドレス及び宛
    先アドレスより求められる送受信者間のメトリック値、
    または通信パケットの発信時刻及び送達希望時刻より求
    められる送達希望時刻までの残り時間、あるいはメトリ
    ック値と送達希望時刻までの残り時間とから求められる
    値、もしくはこれらの組み合わせ、をパラメータとして
    通信料金を決定する手段を備えたことを特徴とする請求
    項１０記載のルータ装置。
12. 【請求項１２】 自装置のアドレス及び通信パケットの
    宛先アドレスより求められる自装置から宛先までのメト
    リック値、または現在時刻及び送達希望時刻より求めら
    れる送達希望時刻までの残り時間、あるいはメトリック
    値と送達希望時刻までの残り時間とから求められる値、
    もしくはこれらの組み合わせ、をパラメータとしてパケ
    ット処理の優先順位を決定し、時間スイッチを制御する
    優先制御部を備えたことを特徴とする請求項１０記載の
    ルータ装置。
13. 【請求項１３】 インターネットプロトコルバージョン
    ６仕様における通信パケットの中継点オプションヘッダ
    内に格納された通信パケットの発信時刻及び送達希望時
    刻を用いる優先制御部を備えたことを特徴とする請求項
    １０乃至１２いずれか記載のルータ装置。
14. 【請求項１４】 通信パケットを一時的に記憶する記憶
    装置と、 処理能力以上の通信パケットが入力されて輻輳が発生し
    た場合、優先度が低い通信パケットを記憶装置に一時的
    に退避させ、送達希望時刻が近づいて退避中の通信パケ
    ットの優先度が上がった場合、あるいは輻輳が収まった
    場合に、記憶装置から通信パケットを読み出して優先経
    路制御を再開させる制御手段とを備えたことを特徴とす
    る請求項１０乃至１３いずれか記載のルータ装置。
15. 【請求項１５】 送達希望時刻までの残り時間の単位別
    に分割された時間スイッチと、 待ち合わせ中に送達希望時刻までの残り時間の単位が変
    化した一の時間スイッチ内の通信パケットを、該変化後
    の単位に対応する時間スイッチへ移す手段とを備えたこ
    とを特徴とする請求項１０乃至１４いずれか記載のルー
    タ装置。
16. 【請求項１６】 送達希望時刻までの残り時間の単位別
    に分割された時間スイッチと、 前記単位毎の時間スイッチにおける通信パケットの取り
    出し確率を、該単位毎の時間スイッチにおける待ち合わ
    せ中のパケット数に応じて変更する手段とを備えたこと
    を特徴とする請求項１０乃至１５いずれか記載のルータ
    装置。
17. 【請求項１７】 インターネットプロトコルバージョン
    ６仕様における通信パケットの中継点オプションヘッダ
    内に格納された迂回した際の迂回元のルータ装置のＩ
    Ｄ、送達希望時刻とは無関係な優先度、送達希望時刻を
    越えた場合の扱いを用いる優先制御部を備えたことを特
    徴とする請求項１０乃至１６いずれか記載のルータ装
    置。
18. 【請求項１８】 ルータ装置内の記憶装置の使用量及び
    空き容量、リンクの使用状況、リンク上の隣接するルー
    タの数、隣接するルータまでの往復にかかる時間等の情
    報を格納したパケットを作成し、隣接するルータ装置間
    で交換する手段と、 前記パケット内の情報に基づいて隣接するルータ装置ま
    でのメトリック値を計算する手段と、 前記求めたメトリック値を用いてルータ装置から宛先ま
    でのメトリック値を動的に変更する手段とを備えたこと
    を特徴とする請求項１０乃至１７いずれか記載のルータ
    装置。