JP4761078B2 - マルチキャストノード装置とマルチキャスト転送方法ならびにプログラム - Google Patents

Description

本発明はマルチキャストノード装置およびそれに用いる損失パケット補完の方法ならびにプログラムに関し、特に、マルチパスを用いたパケット冗長配信を行う際に損失パケット補完時の待ち時間の最適値を決定する装置、方法並びにプログラムに関する。

ブロードバンドネットワークの普及に伴い、従来の狭帯域ネットワークでは困難であった高画質映像配信サービスが実現されつつある。また映像パケットの配信にマルチキャスト技術を用いることで、サーバやネットワークの帯域を節約しつつ、多数のユーザへの配信が可能である。ＩＰ(Internet Protocol)層におけるマルチキャスト転送技術には、以下のような課題がある。

第１の課題は、ＩＰマルチキャスト転送を用いるためには、配信経路中にあるすべてのルータが、ＩＰマルチキャストに対応している必要がある、ということである（図１参照）。分岐点におけるマルチキャストパケットの複製は、ＩＰ層で行う必要があるため、ＩＰ層の処理を行うルータが行う必要がある。図１において、分岐点のノード１２、１３、１４、１５、１６、１７において、ＩＰ層の処理を行うルータが、マルチキャストパケットの複製を行っている。

現在、広く使われているルータ装置は、アーキテクチャやソフトウェアなどの問題から、ＩＰマルチキャストに対応していない場合が多い。

第２の課題は、正しく設定されていないＩＰマルチキャストネットワークでは、ループが発生した場合、パケットの複製が繰り返されることで、ネットワーク帯域やルータのリソースを浪費してしまい、他の通信に悪影響を与える可能性がある、ということである。

このような運用上の理由により、マルチキャストに対応しているルータを用いたネットワークにおいても、その機能（マルチキャスト）を使用しないように設定してある場合が多い。このため、既存のネットワーク上において、ＩＰマルチキャストの使用を開始するにあたっては、
・ＩＰマルチキャスト非対応のルータを対応しているルータに置き換えるか、
又は、
・既設のルータがＩＰマルチキャストに対応している場合には、使用しないように設定してあるＩＰマルチキャスト機能に対して、問題が発生しないように適切に設定を行う
必要がある。

これらの問題を回避するために、アプリケーションレベルマルチキャスト方式が提案されている（図２参照）。この方式は、ＩＰ層で行っていたパケットの複製を、アプリケーション層で行う。図２において、分岐点のノード装置１２、１３、１４、１５、１６、１７において、パケットの複製を、ＩＰ層の上層のアプリケーション層で行う（分岐ノードを２段構成で示す)。

アプリケーションレベルマルチキャストのノード装置間の通信には、ＩＰ層のユニキャストパケットを使用するため、従来のＩＰマルチキャスト非対応のネットワークにおいてもこの方式を使用することができる。

ＩＰネットワークを用いたリアルタイム映像配信には、
・パケット到着間隔のゆらぎ、
・パケット欠損
という課題がある。

映像の配信を行うストリーミングサーバは、一般に映像の再生間隔にあわせてパケットの送出を行う。仮に、ネットワーク中の伝送遅延が一定であれば、受信端末は、受信したパケットをそのまま再生すればよい。しかしながら、ネットワーク中の伝送遅延は一定ではなく、ばらつきが発生する。この遅延のばらつき（ゆらぎ）を吸収するために、受信端末では受信したパケットを、一定時間バッファリングし、ばらつきによる影響を吸収している。このとき、映像再生のタイミングは、パケットの受信直後ではなく、ストリーミングサーバが配信時にパケット毎につけたタイムスタンプを基に、伝送遅延を考慮にいれた待ち時間を加えた値を使用している。このことにより、受信側における映像の再生は、ネットワーク中の伝送遅延のばらつきの影響をうけずに、ストリーミングサーバのパケットの送出と同じタイミングで行うことができる。

ＩＰネットワークにおいては、ルータの負荷やネットワークの輻輳などさまざまな要因によりパケットの欠損が発生する。パケットの欠損はコマ落ちによる映像の再生品質の悪化につながる。

この問題に対して、訂正符号技術を用いた前方誤り訂正（Ｆｏｒｗａｒｄ Ｅｒｒｏｒ Ｃｏｒｒｅｃｔｉｏｎ）という技術が提案されている。この手法では、あらかじめ冗長にパケットを送信し、欠損パケットの補完を行う技術である。

しかし、この手法を用いる場合、以下の問題がある。

この手法では、冗長パケットを送出する必要があるため、ネットワークの帯域を余計に使用することとなり、このことがかえってパケットの損失率をあげてしまう可能性がある。単発的なパケットの欠損に対しては高い確率で欠損パケットの復元が可能であるが、パケットが連続して欠損する状況では、パケットの復元ができない場合が多い。

このような状況は、ＩＰ層やより下位層におけるリンクの切断や中継装置の故障などにより発生し、このような状況下でのパケット欠損にはＦＥＣの技術のみでは対応できないことになる。

パケットの連続欠損に対しては、リンクやノードを共有しない排他的なパスを複数用意し、それぞれのパスに同一のパケットを冗長に送出する事が考えられる。

しかしながら、一般にＩＰ層における配信経路は、管理者が明示的にきめることができない。仮に、パケットを冗長に送出したとしても同一経路を通ることになり、連続欠損を防ぐことが難しい。このため、この手法は一般的なＩＰマルチキャストでは用いることができない。

一方、アプリケーションレベルマルチキャストにおいては、ノード間の通信における経路については、ＩＰマルチキャストと同様に、明示的に決めることができないが、どのノードを経由していくかについては、管理者が決めることができる。

このため、アプリケーションレベルマルチキャストのノードをネットワーク中に適切に配置し、通過するリンクやノードを共有しないように、経由するノードをうまく選ぶことで、排他的なパスを構成することができる。

アプリケーションレベルマルチキャストにおけるマルチパスの例を、図３に示す。送信者３１から受信者４１、４２へのパスは、ノード１１、１２、２２、２３、１３、１４と、ノード１１、１２、１６、１５、１４からなり、通過するリンクやノードを共有しないように、排他的なマルチパスを構成している。これに対して、図２のマルチキャストでは、送信者３１から受信者４１、４２へのパスは、ノード１１、１２、２２、２３、１３において同一パスとされる。

なお、特許文献１には、映像配信サーバからメディアデータ及び配信時刻を示す情報を含むマルチキャストパケットを各端末装置に配送し、各端末装置では、マルチキャストパケットを受信し、配信時刻と受信時刻をある端末装置に集め、例えば最大の配信遅延時間を算出し、この最大配信遅延時間から各端末装置での遅延時間を減算することで、自端末装置におけるメディアデータの受信から再生までの待ち時間を求めるようにして、配信映像の同時再生を行うようにした方法、システム、端末装置が開示されている。

特開２００３−２３５０２７号公報

上記したように、従来のマルチキャストシステムは、下記記載の問題点を有している。

第一の問題点は、マルチパスによるパケット補完技術を利用した場合、適切な待ち時間を決めるのが困難である、ということである。

ここで、待ち時間とは、ノード装置からパケットを送出する時刻から送信元のパケット送出時刻を引いた値である（例えば図４の６６参照）。そして、待ち時間が長いということは、パケット毎のバッファリング時間が長くなり、それだけノード装置内に滞留するパケットの量が大きくなることを意味している。

また、ノード装置内でのバッファリング時間が大きいということは、パケットの到達遅延も大きくなる。このため、可能な限り待ち時間は短い方がよい。

しかしながら、待ち時間が短い場合、各パスにおける遅延のばらつきを吸収できない可能性がある。

ＩＰネットワークにおいては、パケットの伝送遅延は一定ではなく、ばらつきが生じる。このためマルチパスの場合、遅延の小さいほうのパスで欠損したパケットを、他方のパスで補完する必要があるときに、後者のパスの遅延の増大により、待ち時間中にパケットが到着しない可能性がある。以下、本発明者の検討結果に基づき説明する。

図４のタイミングダイアグラムを用いて説明する。なお、図４は、本発明者が、課題を説明するために作成したものである。図４において、５１はパケットの送信元のタイムラインを示しており、横軸は時間の経過を表している。ＲＴＰ（Real-Time Transport Protocol）などのリアルタイム転送を目的としたプロトコルでは送信基において、パケットにはそれぞれシーケンス番号が付与されて送出される。ここでは、パケット１１、１２、１３にはそれぞれ、シーケンス番号６１７、６１８、６１９が付与されているとする。図４において、５２および５３は、それぞれ、これらのパケットがマルチパスを構成するパス１およびパス２を通じて、合流点であるノード装置に到着したときのタイムラインを表している。シーケンス番号６１７のパケット１１は、パス１、パス２ともに、送信元のパケット送出からそれぞれのパスの平均遅延時間経過後に、ノード装置に到着しているものとする。

パス１経由でノード装置に到着したパケット２１は、パケット中のタイムスタンプに待ち時間６６足した値を送出時刻として、パケットの送出を行う（パケット４１）。ここでパス１におけるパケット２１のバッファリング時間６５とは、待ち時間６６からパケット２１の伝送遅延（今回は平均遅延６２）を引いた値である。

パス２経由で到着したパケット３１は、パス１経由で到達するパケット２１がパス中で失われ到着しなかった場合に、パケット２１に代わってパケット４１として送出される。

図４の例では、パケット２１が失われずノード装置まで到達しているために、パケット３１は、受信後、破棄される。シーケンス番号６１７のパケット１１は、それぞれのパスにおいての平均遅延時間の伝送遅延でノード装置に到着しているが、一般には、シーケンス番号６１８で送出されるパケット１２のように、平均遅延時間を超える伝送遅延６７が発生してノード装置に到着したり（パケット２２）、平均遅延時間を下回る伝送遅延６８でノード装置に到着したりする（パケット３２）。

送信元から送出されたシーケンス番号６１９のパケット１３が、パス１中に失われた場合について考える。この場合、パス２を通って到着するシーケンス番号６１９のパケット３３を、パケット２３の代わりとして送出することでパケットの補完を行う。しかし、図４のように、パケット３３が待ち時間よりも大きな遅延で到着した場合、パケット４３の送信時刻を超えているため、パケットの補完ができない。

このように、待ち時間を短くすると、パケットを補完できない可能性が高くなる。

したがって、本発明の目的は、目標パケット補完率を満たしつつ、最小の待ち時間を求めることを可能とし、マルチパスを用いたパケットの補完を行うノード装置に用いて好適とされる装置、方法及びプログラムを提供することにある。

前記課題を解決する手段として、本発明の第一の側面に係るノード装置は、
装置外部のネットワークと接続するネットワークインターフェイスと、
前記ネットワークインターフェイスを介して、冗長パスを構成する複数のパスから同一のパケットを受信するパケット受信部と、
前記受信したパケットの遅延に関する統計情報をパス毎に収集する統計処理部と、
前記パス毎に収集した統計情報を基に前記パケットの待ち時間を決定する待ち時間計算部と
を備える。

本発明において、前記パケット受信部は、マルチキャストパケットを受信する。前記パケット受信部は、シーケンス番号とタイムスタンプとを含むパケットを受信する。前記パケット受信部が受信したパケットのシーケンス番号を参照し、送信バッファに対して、未格納のシーケンス番号を持つパケットを格納するパケット同期部を持つ。前記統計処理部は、パケットの遅延の平均値を求める。前記統計処理部は、パケットの遅延の分散を求める。

本発明において、前記待ち時間計算部は、パケットの受信パス毎に確率分布関数を用いて待ち時間を決定する。前記統計処理部は、パケットの遅延に関する度数分布を用いて待ち時間を決定する。

本発明において、前記ノード装置において、パケットの到達率を測定する到達率測定部をさらに備え、前記待ち時間計算部は、前記到達率測定部により測定された到達率を用いて、待ち時間を決定する。前記待ち時間計算部は、パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に待ち時間と到着率の関係を表す到着率テーブルを作成し、前記到着率テーブルを用いて目標のパケット到着率を満たす最小の待ち時間を求める。

本発明の他の側面に係る方法は、受信したパケットを送出時刻に送出するパケット転送方法であって、
冗長パスを構成する複数のパスから同一のパケットを受信する工程と、前記受信パケットの遅延に関する統計情報をパス毎に収集する工程と、
前記パス毎に収集した統計情報を基に、前記パケットの待ち時間を計算する工程と
を含む。

本発明に係る方法において、前記パケットを受信する工程は、マルチキャストパケットを受信する。前記パケットを受信する工程は、シーケンス番号とタイムスタンプとを含むパケットを受信する。前記パケットを受信する工程において受信したパケットのシーケンス番号を参照し、未送出のシーケンス番号を持つパケットを送出時刻に送出する工程を有する。前記統計情報を収集する工程において、パケットの遅延の平均値を求める。

本発明に係る方法において、前記統計情報を収集する工程において、パケットの遅延の分散を求める。

本発明に係る方法において、前記待ち時間を計算する工程は、パケットの受信パス毎に確率分布関数を用いて、待ち時間を決定する。

本発明に係る方法において、前記待ち時間を計算する工程は、パケットの遅延に関する度数分布を用いて、待ち時間を決定する。

本発明に係る方法において、パケットの到達率を測定する工程をさらに含み、前記待ち時間を計算する工程は、測定された到達率を用いて待ち時間を決定する。前記待ち時間を計算する工程において、パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に、待ち時間と到着率の関係を表す到着率テーブルを作成し、前記到着率テーブルを用いて目標パケット補完率（到着率）を満たす最小の待ち時間を求める。

本発明の他の側面に係るコンピュータプログラムは、パケット転送のプログラムであって、前記プログラムはコンピュータに、
冗長パスを構成する複数のパスから同一のパケットを受信する処理と、
前記受信パケットから遅延値に関する統計情報を受信パス毎に収集する処理と、
前記受信パス毎に収集した統計情報を基に、パケットの待ち時間を計算する処理と
を実行させる。

本発明に係るコンピュータプログラムにおいて、前記パケットを受信する処理は、マルチキャストパケットを受信する。前記パケットを受信する処理は、シーケンス番号とタイムスタンプとを含むパケットを受信する。前記パケットを受信する処理において受信したパケットのシーケンス番号を参照し、未送出のシーケンス番号を持つパケットを送出時刻に送出する工程を有する。前記統計情報を収集する処理において、パケットの遅延の平均値を求める処理を含む。

本発明に係るコンピュータプログラムにおいて、前記統計情報の収集処理において、パケットの遅延の分散を求める処理を含む。

本発明に係るコンピュータプログラムにおいて、前記待ち時間を計算する処理は、パケットの受信パス毎に確率分布関数を用いて、待ち時間を決定する処理を含む。

本発明に係るコンピュータプログラムにおいて、前記待ち時間を計算する処理は、パケットの遅延に関する度数分布を用いて、待ち時間を決定する処理を含む。

本発明に係るコンピュータプログラムにおいて、パケットの到達率を測定する処理と、前記測定された到達率を用いて待ち時間を決定する処理とを前記コンピュータに実行させる。パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に、待ち時間と到着率の関係を表す到着率テーブルを作成する処理と、前記到着率テーブルを用いて目標パケット到着率を満たす最小の待ち時間を求める処理とを前記コンピュータに実行させる。
本発明の他の側面に係るノード装置は、
アプリケーションレベルのパケット転送機能を有するノード装置が、
前記ノード装置外部のネットワークと接続を行うネットワークインターフェイスと、
前記ネットワークインターフェイス経由で、パケット送出時のタイムスタンプ情報とシーケンス情報を含む同一のパケットを、冗長パスを構成する複数のパスから受信し、ピアと送信元と宛先情報の対応を格納したテーブルを参照して、受信パケットから、送信元と宛先情報より、対応する上流ピアを特定し、前記受信パケットを特定された上流ピアに対応する受信バッファに送るパケット受信部と、
ピア単位に受信したパケットの遅延の平均値、分散、度数分布、パケット損失率の少なくとも１つの情報の収集をパス毎に行う統計処理部と、
前記統計処理部でパス毎に収集した情報を基に、パケット待ち時間を計算する待ち時間計算部と、
複数の上流パスから受信し前記受信バッファに格納されたパケットから、上流ピア、下流ピアの対応を管理するテーブルを参照して、前記特定された上流ピアに対応する下流ピアを特定し、前記特定された下流ピアに対応する送信バッファにパケットを格納するパケット同期部と
を備える。
本発明に係るノード装置において、前記送信バッファ中のパケットに関して、ピアと送信元と宛先情報の対応を格納したテーブルを参照して下流ピアで使用する送信元と宛先の情報に基づき、前記パケットを対応するネットワークインターフェイスを通して送出するパケット送信部と、パケット受信部、パケット送信部、パケット同期部のテーブルの内容を管理するパス管理部とを備える。前記待ち時間計算部は、パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に、待ち時間と到着率の関係を表す到着率テーブルを作成し、前記到着率テーブルを用いて、目標パケット到着率を満たす最小の待ち時間を求める。パケットの到達率を測定する到達率測定部をさらに備え、前記待ち時間計算部は、前記到達率測定部により測定された到達率を用いて、待ち時間を決定する。
本発明の他の側面に係る通信システムは、
ネットワークと
前記ネットワークと接続するネットワークインターフェイスと、
前記ネットワークインターフェイスを介して、冗長パスを構成する複数のパスから同一のパケットを受信するパケット受信部と、
前記受信したパケットの遅延に関する統計情報をパス毎に収集する統計処理部と、
前記パス毎に収集した統計情報を基に前記パケットの待ち時間を決定する待ち時間計算部と
を備える。

本発明の第一の効果は、目標パケット補完率を満たしつつノード装置のバッファリングによる使用メモリ量を最小にすることができる点である。必要とするメモリ量が少なくなれば、ノード装置に搭載するメモリ量を少なくすることができるため、ノード装置のコストを抑えることができる。また搭載するメモリ量が同じであっても、本発明の手法を用いることで、より多くのストリーム配信を扱うことができる。

本発明の第二の効果は、目標パケット補完率を満たしつつパケット伝送における累積遅延を最小にすることができる点である。マルチパスの合流点にあるノード装置においては、パケット補完のためのバッファリングが必要であり、そのバッファリング時間分の遅延が発生する。さらに、マルチパスの合流点にあるノード装置以外のアプリケーションレベルマルチキャストのノード装置においては、受信したパケットを送信し終わるまでにある程度の遅延が発生する。本発明の手法を用いることで、マルチパスの合流点における遅延を必要最小限に抑えることができる。

ＩＰマルチキャストによるパケット転送を示すネットワーク図である。 アプリケーションレベルマルチキャストによるパケット転送を示すネットワーク図である。 アプリケーションレベルマルチキャストによるマルチパスパケット補完を示すネットワーク図である。 マルチパスパケット補完を示すタイムライン図である。 本発明の第一の実施形態のノード装置の構成を示すブロック図である。 本発明の第一の実施形態における上流ピア管理テーブルの構成を示す図である。 本発明の第一の実施形態におけるパステーブルの構成を示す図である。 本発明の第一の実施形態における下流ピア管理テーブルの構成を示す図である。 本発明の第一の実施形態において、各パスの遅延の平均値、分散の計算処理を示すフローチャートである。 本発明の第一の実施形態における待ち時間の決定処理を示すフローチャートである。 本発明の第一の実施形態における到着率テーブルの構成を示す図である。 本発明の第一の実施形態におけるパケットの同期処理を示すフローチャートである。 本発明の第二の実施形態のノード装置の構成を示すブロック図である。 本発明の第三の実施形態のノード装置の構成を示すブロック図である。 本発明の第三の実施形態における度数分布テーブルの構成を示す図である。 本発明の第三の実施形態における累積度数分布テーブルの構成を示す図である。 本発明の第三の実施形態における到着率テーブルの決定処理を示すフローチャートである。

符号の説明

７、７Ａ、７Ｂ マルチキャストノード装置（ルータ装置）
１１〜２５ ノード
３１ 送信者
４１〜４６ 受信者
１１１〜１１ｎ 統計処理部
１２１〜１２ｎ 受信バッファ
１３１ 待ち時間計算部
１３２ パケット同期部
１３２１ パステーブル
１３２２ ストリーム番号
１３２３ 下流ピア
１３２４ 上流ピア
１４１ パケット受信部
１４１１ 上流ピア管理テーブル
１４１２ ピア
１４１３、１４１５ アドレス
１４１４、１４１６ ポート番号
１４２ パケット送信部
１４２１ 下流ピア管理テーブル
１４２２ 下流ピア
１４２３、１４２５ アドレス
１４２４、１４２６ ポート番号
１４３ パス管理部
１４４ リアルタイムクロック
１５１〜１５ｍ ネットワークインターフェイス
１６１〜１６ｐ 送信バッファ
１７１１ 待ち時間
１７１２ 到着率
１８１〜１８ｎ 到着率測定部
１９１〜１９ｎ 度数分布対応統計処理部
１９１１、１９２１ 伝送遅延
１９１２ パケット数
１９２２ 累積パケット数

次に、本発明の実施の形態について図面を参照して詳細に説明する。

図５は、本発明の一実施例によるノード装置の機能構成を示すブロック図である。

図５において、本発明の一実施例によるルータ装置７は、統計処理部１１１〜１１ｎ、受信バッファ１２１〜１２ｎ、待ち時間計算部１３１、パケット同期部１３２、送信バッファ１６１〜１６ｐ、パケット受信部１４１、パケット送信部１４２、パス管理部１４３、リアルタイムクロック１４４、およびネットワークインターフェイス１５１〜１５ｍを備えている。

ネットワークインターフェイス１５１〜１５ｍは、ノード装置外部のネットワークと接続を行う。

パケット受信部１４１は、ネットワークインターフェイス１５１〜１５ｍ経由でパケットを受信し、上流ピア管理テーブル１４１１を参照し、パケットのピアを判定する。

ピアを特定したパケットは、受信バッファ１２１〜１２ｎのうち、上流ピアに対応するいずれかの受信バッファにパケットを送られる。

本発明におけるパケット受信部１４１においては、ＲＴＰなどパケット中にパケット送出時のタイムスタンプおよびシーケンス番号を含むパケットを取り扱うものとする。

ピアとは、アプリケーションレベル・マルチキャストのノード間におけるトランスポート層プロトコルでのコネクションである。

図６は、トランスポート層のプロトコルとしてＵＤＰ（User Datagram Protocol）を使用した場合に、受信パケットから対応する上流ピアを特定するためのテーブル（上流ピア管理テーブル１４１１）の一例を示す図である。図６を参照すると、この上流ピア管理テーブル１４１１は、ピア１４１２、送信元アドレス１４１３、送信元ポート番号１４１４、宛先アドレス１４１５、宛先ポート番号１４１６という項目から構成される。

パケット受信部１４１は、この上流ピア管理テーブル１４１１を参照することで、受信したパケットの送信元アドレスＡ１０、送信元ポート番号Ｐ１０、宛先アドレスＡ１１、宛先ポート番号Ｐ１１であった場合には、ピア１からの受信パケットであると判断することができる。

例えば図６のピア２のように宛先アドレスとして、ワイルドカード“＊”で表されている場合には、パケット受信部１４１は、任意の宛先アドレスのパケットがマッチするものとする。つまり、送信元アドレスがＡ２０、送信元ポート番号がＰ２０、宛先ポート番号がＰ２１であるパケットは、宛先アドレスの値がいずれの値であっても、ピア２に該当する。

ここでは、ＩＰヘッダ、ＵＤＰヘッダ中の値を用いることで、上流ピアの特定をしているが、受信したパケットから上流ピアを特定できるのであれば、どのような手法を採用してもよい。例えば、パケット中のいずれかの部分に、ピア毎に一意に識別するための値を入れるフィールドを用意しておき、該フィールドに格納された値により、上流ピアを特定するようにしてもよい。

再び図５を参照して、各受信バッファ１２１〜１２ｎに受信パケットが格納されるとき、統計処理部１１１〜１１ｎにおいて、ピア単位のパケット受信品質に関する統計情報（遅延の平均値、分散）の収集が行われる。

待ち時間計算部１３１は、統計処理部１１１〜１１ｎで収集した遅延、パケット損失率などの情報を基に、パケット待ち時間を計算し、パケット同期部１３２に計算した値を設定する。

パケット同期部１３２では、複数の上流パスから受信したパケットストリームをマージする。このとき、パケット同期部１３２は、パステーブル１３２１を参照し、下流ピアを特定し、対応する送信バッファ１６１〜１６ｐのいずれかにパケットを送る。

図７に、パステーブル１３２１の一例を示す。パステーブル１３２１は、ストリーム番号１３２２、下流ピア１３２３、上流ピア１３２４を項目として持つ。

例えば、
・受信したパケットの上流ピアがピア２であった場合、下流ピアは、ピアＸになる
・上流ピアがピア４出会った場合には、下流ピアはピアＹになる
である。

再び図５を参照して、パケット送信部１４２は、送信バッファ１６１〜１６ｐ中のパケットを送信予定時刻になったときに送出する。

パケット送信部１４２は、下流ピア管理テーブル１４２１を参照し、下流ピアで使用する送信元アドレス、送信元ポート番号、宛先アドレス、宛先ポート番号を検索する。

図８に、下流ピア管理テーブル１４２１の一例を示す。下流ピア１４２２で使用する送信元アドレス１４２３、送信元ポート番号１４２４、宛先アドレス１４２５、宛先ポート番号１４２６を備えている。これらの検索した情報を基に、ネットワークインターフェイス１５１〜１５ｍを通して、パケットを送出する。またパケット送信部１４２は、パケットの送出を送出予定時刻に従う方法ではなく、以下の方法で行ってもよい。
・直前に送信したパケットのシーケンス番号を記録しておく
・送信バッファ中のパケットのシーケンス番号のうち最小のものが、送信済みシーケンス番号の次の値の場合、そのパケットの送出を行う。
・送信バッファ中のパケットのシーケンス番号のうち最小のものが、送信済みシーケンス番号の次の値で無い場合、パケットの送出予定時刻まで待ち、それまでに送信済みシーケンス番号の次の値をもつパケットが送信バッファに入ってこない場合には、パケットの送出を行う。

再び図５を参照して、パス管理部１４３は、パスに関する情報を管理し、パステーブル１３２１、上流ピア管理テーブル１４１１および下流ピア管理テーブル１４２１に、それぞれ、適切な値を設定する。

パス管理部１４３へのパス情報の設定は、人手で行ってもよいし、あるいは、ネットワーク管理端末からネットワーク経由で行うようにしてもよい。

リアルタイムクロック１４４は、統計処理部１１１〜１１ｎ、パケット同期部１３２、パケット送信部１４２の各部からの要求に対し、現在時刻情報を供給する。

図９は、本発明の一実施形態の統計処理部１１ｉの動作を説明するための流れ図である。図５及び図９を参照して、図５の統計処理部１１ｉが遅延の平均値、分散を求める動作について説明する。

まず、各カウンタｃｉ、ｄｉ、ｓｉに、０を入れておく（ステップＳ１）。

パスｉからのパケットの受信を待ち、受信したパケット中のタイムスタンプを参照し、その値をｔｓとする（ステップＳ２）。

リアルタイムクロック１４４から、現在時刻ｔｎを取得する（ステップＳ３）。

現在時刻ｔｎとパケット送信時刻ｔｓの差を計算し、ｄｉに加える。このｄｉは、各パケットの遅延の合計値を意味している。また、差の二乗を計算し、ｓｉに加える。ｓｉは各パケットの遅延値の二乗の値の合計値を意味している。さらに、ｃｉに１を加える（ステップＳ４）。

次に、ｃｉの値が初期計測パケット数を超えているか否かを調べる（ステップＳ５）。初期計測パケット数は、あらかじめ人手で与えておくものとする。ｃｉの値が初期計測パケット数を超えていない場合には、ステップＳ２へと戻る。

ｃｉの値が初期計測パケット数を超えている場合には、次の計算を行う。

まず、ｄｉをｃｉで割った値ｍｉ（ｍｉ＝ｄｉ／ｃｉ）を求める。ｍｉは各パケットの伝送遅延の平均値を意味している。

また、ｓｉをｃｉで割った値から、ｍｉの二乗を引いた値の平方根ｖｉ（＝ｓｉ／ｃｉ−ｍｉ２）１／２を求める。このｖｉは、各パケットの伝送遅延の分散を意味している。

ここで、ステップＳ５は、受信したパケット数が所定の値を超えたら、ステップＳ２からステップＳ５のループ処理を終了しているが、一連の処理を開始してから一定時間経過後に終了することとしてもよい。

図１０は、本発明の一実施形態の待ち時間計算部１３１の動作を説明するための流れ図である。次に、図１０を参照して、図５の待ち時間計算部１３１が待ち時間を求める動作について説明する。

まず、各Ｌｉに対して、１の値を設定する（ステップＳ１１）。ｉは各ピアの到着率テーブルの列を表すインデックスである。

図１１を用いて、到着率テーブルについて説明する。到着率テーブルは、待ち時間１７１１（遅延）と、その待ち時間内で到着するパケットの確率（到着率）１７１２の関係を表すテーブルである。到着率テーブルは、図５において、例えば待ち時間計算部１３１内部の記憶装置に格納保持される。

ここで、各ピアの到着率テーブルの列数のうち最大の値をｎとする。この時点で最大値はわからないので、十分に大きな値を用意し、それをｎとすればよい。

Ｌｉは、パスごとの到着率テーブルのｉ列目における、累積損失率を表す。

再び図１０を参照して、次に未処理の上流ピアのうち、遅延の平均値が一番小さい上流ピアａを選択する（ステップＳ１２）。

次に、上流ピアａの遅延の平均値ｍａおよび分散ｖａを用いて確率分布関数から、ピアａの到着率テーブルを作成する（ステップＳ１３）。

ここでは、正規分布の確率分布関数を用いるが、ネットワークの特性に合わせて異なる分布の確率分布関数を用いてもよい。

なお、図１１の到着率テーブルにおける到着率は、伝送遅延１ｍｓ毎に求められているが、本発明はかかる構成に制限されるものでない。到着率テーブルの作成の際の伝送遅延の間隔は、例えば管理者が任意の値を設定してよい。

図１０のステップＳ１４では、ステップＳ１３で作成した到着率テーブルに対して、以下の処理を行う。

ここで、到着率テーブルのｉ列目の値をｘｉ、ピアａのパケット推定到達率をｌａとすると、（１−ｘｉ）×（１−ｌａ）を求め、ｙｉとする。

ｙｉを、到着率テーブルすべての列について計算を行う。

パケット推定到達率ｌａは、パケットがパス中で損失せずに到達する確率である。例えば５％のパケット損失が予想されるパスのパケット推定到達率は、０．９５になる。

このパケット推定到達率は、
・管理者が任意の値を設定するか、
もしくは、
・ネットワーク管理端末などからネットワーク経由で設定する。

ｙｉは、パスａにおいて、待ち時間以内にパケットが到着しない確率、および、パスａ中にパケットが失われることで、ノードまでパケットに到着しない確率との積であり、パスａのｉ列目の待ち時間における損失率を表している。

パスａの到着率テーブルのｉ列目の待ち時間が５５ｍｓであるとすると、５５ｍｓ以内にパスａにおいてパケットが到達しない確率を表している。

次に、パスａの到着率テーブルの各列ｉに対して、Ｌｉにｙｉの値を掛ける（ステップＳ１５）。

このＬｉは、累積損失率であり、到着率テーブルのｉ列目の待ち時間が５５ｍｓだったとすると、５５ｍｓ以内に、ここまで処理したパスのいずれからも、パケットが到達しない確率を表している。

次に、上流ピアａを処理済とし（ステップＳ１６）、他に未処理の上流ピアが残っているか否かを調べる（ステップＳ１７）。未処理の上流ピアが残っている場合には、ステップＳ１２へ戻る。

上流ピアすべてに対し処理が終了している場合、これまでの計算で求めたＬｉを用いて、全体到着率テーブルを作成する。

このとき、１−Ｌｉを、全体到着率テーブルのｉ列目における到着率とする（ステップＳ１８）。

次に、全体到着率テーブルから目標到達率ｌｔを上回る遅延値のうち、最小の値ｄｔを求める（ステップＳ１９）。

求めたｄｔをパケット同期部に設定する（ステップＳ２０）。

図１２は、本発明の一実施形態のパケット同期部１３２の動作を説明するための流れ図である。図１２を参照して、パケット同期部１３２の処理を説明する。

パケットの受信を待つ（ステップＳ２１）。

パケットを受信したら、そのパケット中のシーケンス番号ｑ、タイムスタンプｔｓを取得する（ステップＳ２２）。

送信バッファを走査し、同一のシーケンス番号のパケットが存在するか否かを確認する（ステップＳ２３）。

同一シーケンス番号のパケットが送信バッファに存在している場合、当該パケットを廃棄し（ステップＳ２４）、ステップＳ２１に戻る。

同一シーケンス番号のパケットが送信バッファに無い場合、ｔｓ＋ｄｓを計算し、送信予定時刻ｔｏとする（ステップＳ２５）。

次にリアルタイムクロック１４４から現在時刻ｔｎを取得する（ステップＳ２６）。

現在時刻ｔｎが送信予定時刻ｔｏを過ぎているか否かを調べ（ステップＳ２７）、過ぎている場合には、ステップＳ２４に戻る。

現在時刻ｔｎが、送信予定時刻ｔｏを過ぎていない場合には、パケットを送信バッファに送り（ステップＳ２８）、送ったパケットの送信予定時刻を送信バッファに設定する（ステップＳ２９）。

次に、本発明の第二の実施の形態について説明する。図１３は、本発明の第二の実施の形態のノード装置７Ａの構成を示す図である。図１３を参照すると、ノード装置７Ａには、図５の構成に、さらに到達率測定部１８１〜１８ｎを備えている。到達率測定部１８１〜１８ｎは、受信バッファ１２１〜１２ｎに格納されるパケットのシーケンス番号を調べ、単位時間当たりのパケットの到達率を調べる。調べたパケット到達率は、パケット同期部１３２に渡される。

図５に示した前記第一の実施形態では、図１０に示した手順において、待ち時間を求める際に、パケット到達率として推定される値を、あらかじめ決めておく必要があった。

これに対して、本発明の第二の実施形態においては、到達率測定部１８１〜１８ｎにて、パス毎の実際のパケット損失率を測定することで、ネットワークの状態の変動に応じたより適当な待ち時間を求めることができる。

次に、本発明の第三の実施の形態について説明する。図１４は、本発明の第三の実施の形態のノード装置の構成を示す図である。図１４を参照すると、本発明の第三の実施の形態において、ノード装置７Ｂは、度数分布対応統計処理部１９１〜１９１ｎを有する。度数分布対応統計処理部１９１〜１９ｎは、パケット受信部１４１から受信した各パケット毎にパケットから取得したタイムスタンプの値を、リアルタイムクロック１４４から取得した現在時刻から引くことで、パケットの伝送遅延を算出する。

一定間隔毎に区切られた伝送遅延の階級幅毎にパケット数を集計することで、度数分布テーブルを作成する。図１５に、度数分布テーブル、図１６に累積度数分布テーブルの例を示す。伝送遅延の各区間に対応してパケットの数が記録される。図１５、図１６の度数分布テーブル、累積度数分布テーブルでは、階級の幅が１ｍｓとなっているが、この値は管理者が任意の値に設定してよい。度数分布テーブル、累積度数分布テーブルは、度数分布対応統計処理部１９１〜１９ｎに備えてもよいし、あるいは、待ち時間計算部１３１に備えてもよい。

次に、図１７の流れ図を参照して、本実施形態における度数分布テーブルから到着率テーブルを作成する手順について説明する。なお、到着率テーブルは、図１１を参照して説明した形式のものが用いられる。

まず、ｃに０を、ｉに１を設定する（ステップＳ３１）。ここで、ｉは、度数分布テーブル中の列を示す変数である。

次に、ｃにｆｉの値を加える。ｆｉは度数分布テーブルのｉ列目のパケット数を表している。次にｉに１を加える（ステップＳ３２）。

累積度数分布テーブルのｉ列目の累積パケット数のエントリに登録する（ステップＳ３３）。累積度数分布テーブルは、図１６に示したものが用いられる。

次に、度数分布テーブルの全ての列について計算を終了したかを調べ、終了していなかったら、ステップＳ３２に戻る（ステップＳ３４）。

すべての列について計算が終了している場合、ステップＳ３５へと進む。この時点でｃの値は、度数分布テーブルに集計されているパケット数の合計値を表している。

次にｒに０を、ｉに１を代入する（ステップＳ３５）。

次に、ｆｉをｃで割った値を、ｒに代入する。またｉに１を加える（ステップＳ３６）。

ｒを到着率テーブルのｉ列目の到着率のエントリに登録する（ステップＳ３７）。

累積度数分布テーブル（図１６）の全ての列について計算を終了したかを調べ、終了していなかったら、ステップＳ３６に戻る（ステップＳ３８）。

すべての列について計算が終了している場合、処理を終了する。

ここで得られた到着率テーブルから待ち時間を計算する手順については、本発明の第一の実施例と同様である。

図５を参照して説明した第一の実施形態においては、確率分布関数から到着率テーブルを求める際に、多数の実数演算を行う必要がある。

本実施形態においては、唯一の実数演算は、図１７のステップＳ３６での除算のみ（ｆｉ/ｃ）であり、他は整数の加算のみで構成されている。このため、第一の実施例と比べると、より低い負荷で、目的を実現できる。

本発明は、ＩＰネットワークを用いたライブ映像配信に用いて好適とされる。

以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみに制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。

Claims (35)

1. 装置外部のネットワークと接続するネットワークインターフェイスと、
   前記ネットワークインターフェイスを介して、冗長パスを構成する複数のパスから同一のパケットを受信するパケット受信部と、
   前記受信したパケットの遅延に関する統計情報をパス毎に収集する統計処理部と、
   前記パス毎に収集した統計情報を基に前記パケットの待ち時間を決定する待ち時間計算部と
   を備えることを特徴とするノード装置。
2. 前記パケット受信部は、マルチキャストパケットを受信することを特徴とする請求項１に記載のノード装置。
3. 前記パケット受信部は、シーケンス番号とタイムスタンプとを含むパケットを受信することを特徴とする請求項１又は２に記載のノード装置。
4. 前記パケット受信部が受信したパケットのシーケンス番号を参照し、送信バッファに対して、未格納のシーケンス番号を持つパケットを格納するパケット同期部を持つことを特徴とする請求項３に記載のノード装置。
5. 前記統計処理部は、パケットの遅延の平均値を求めることを特徴とする請求項１から請求項４のいずれかに記載のノード装置。
6. 前記統計処理部は、パケットの遅延の分散を求めることを特徴とする請求項１から請求項５のいずれかに記載のノード装置。
7. 前記待ち時間計算部は、パケットの受信パス毎に確率分布関数を用いて待ち時間を決定することを特徴とする請求項１から請求項６のいずれかに記載のノード装置。
8. 前記統計処理部は、パケットの遅延に関する度数分布を用いて待ち時間を決定することを特徴とする請求項１から請求項４のいずれかに記載のノード装置。
9. 前記ノード装置において、パケットの到達率を測定する到達率測定部をさらに備え、
   前記待ち時間計算部は、前記到達率測定部により測定された到達率を用いて、待ち時間を決定することを特徴とする請求項１から請求項８のいずれかに記載のノード装置。
10. 前記待ち時間計算部は、パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に待ち時間と到着率の関係を表す到着率テーブルを作成し、
    前記到着率テーブルを用いて目標のパケット到着率を満たす最小の待ち時間を求めることを特徴とする請求項１から請求項９のいずれかに記載のノード装置。
11. 受信したパケットを送出時刻に送出するパケット転送方法であって、
    冗長パスを構成する複数のパスから同一のパケットを受信する工程と、
    前記受信パケットの遅延に関する統計情報をパス毎に収集する工程と、
    前記パス毎に収集した統計情報を基に、前記パケットの待ち時間を計算する工程と
    を含むことを特徴とするパケット転送方法。
12. 前記パケットを受信する工程は、マルチキャストパケットを受信することを特徴とする請求項１１に記載のパケット転送方法。
13. 前記パケットを受信する工程は、シーケンス番号とタイムスタンプとを含むパケットを受信することを特徴とする請求項１１又は１２に記載のパケット転送方法。
14. 前記パケットを受信する工程において受信したパケットのシーケンス番号を参照し、未送出のシーケンス番号を持つパケットを送出時刻に送出する工程を有することを特徴とする請求項１３に記載のパケット転送方法。
15. 前記統計情報を収集する工程において、パケットの遅延の平均値を求めることを特徴とする請求項１１から請求項１４のいずれかに記載のパケット転送方法。
16. 前記統計情報を収集する工程において、パケットの遅延の分散を求めることを特徴とする請求項１１から請求項１５のいずれかに記載のパケット転送方法。
17. 前記待ち時間を計算する工程において、パケットの受信パス毎に確率分布関数を用いて、待ち時間を決定することを特徴とする請求項１１から請求項１６のいずれかに記載のパケット転送方法。
18. 前記待ち時間を計算する工程において、パケットの遅延に関する度数分布を用いて、待ち時間を決定することを特徴とする請求項１１に記載のパケット転送方法。
19. パケットの到達率を測定する工程をさらに有し、
    前記待ち時間を計算する工程は、測定された到達率を用いて待ち時間を決定することを特徴とする請求項１１から請求項１８に記載のパケット転送方法。
20. 前記待ち時間を計算する工程において、パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に、待ち時間と到着率の関係を表す到着率テーブルを作成し、前記到着率テーブルを用いて目標パケット補完率（到着率）を満たす最小の待ち時間を求めることを特徴とする請求項１１から請求項１９のいずれかに記載のパケット転送方法。
21. パケット転送のプログラムであって、前記プログラムはコンピュータに、
    冗長パスを構成する複数のパスから同一のパケットを受信する処理と、
    前記受信パケットから遅延値に関する統計情報を受信パス毎に収集する処理と、
    前記受信パス毎に収集した統計情報を基に、パケットの待ち時間を計算する処理と
    を実行させることを特徴とするプログラム。
22. 前記パケットを受信する処理は、マルチキャストパケットを受信することを特徴とする請求項２１に記載のプログラム。
23. 前記パケットを受信する処理は、シーケンス番号とタイムスタンプとを含むパケットを受信することを特徴とする請求項２１又は２２に記載のプログラム。
24. 前記パケットを受信する処理において受信したパケットのシーケンス番号を参照し、未送出のシーケンス番号を持つパケットを送出時刻に送出する工程を有することを特徴とする請求項２３に記載のプログラム。
25. 前記統計情報を収集する処理において、パケットの遅延の平均値を求める処理を含むことを特徴とする請求項２１から請求項２４のいずれかに記載のプログラム。
26. 前記統計情報を収集する処理において、パケットの遅延の分散を求める処理を含むことを特徴とする請求項２１から請求項２５のいずれかに記載のプログラム。
27. 前記待ち時間を計算する処理は、パケットの受信パス毎に確率分布関数を用いて、待ち時間を決定する処理を含むことを特徴とする請求項２１から請求項２６のいずれかに記載のプログラム。
28. 前記待ち時間を計算する処理は、パケットの遅延に関する度数分布を用いて、待ち時間を決定する処理を含むことを特徴とする請求項２１に記載のプログラム。
29. パケットの到達率を測定する処理と、
    前記測定された到達率を用いて待ち時間を決定する処理と
    を前記コンピュータに実行させることを特徴とする請求項２１から請求項２８のいずれかに記載のプログラム。
30. パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に、待ち時間と到着率の関係を表す到着率テーブルを作成する処理と、
    前記到着率テーブルを用いて目標パケット到着率を満たす最小の待ち時間を求める処理と
    を前記コンピュータに実行させることを特徴とする請求項２１から請求項２９のいずれかに記載のプログラム。
31. アプリケーションレベルのパケット転送機能を有するノード装置が、
    前記ノード装置外部のネットワークと接続を行うネットワークインターフェイスと、
    前記ネットワークインターフェイス経由で、パケット送出時のタイムスタンプ情報とシーケンス情報を含む同一のパケットを、冗長パスを構成する複数のパスから受信し、ピアと送信元と宛先情報の対応を格納したテーブルを参照して、受信パケットから、送信元と宛先情報より、対応する上流ピアを特定し、前記受信パケットを特定された上流ピアに対応する受信バッファに送るパケット受信部と、
    ピア単位に受信したパケットの遅延の平均値、分散、度数分布、パケット損失率の少なくとも１つの情報の収集をパス毎に行う統計処理部と、
    前記統計処理部でパス毎に収集した情報を基に、パケット待ち時間を計算する待ち時間計算部と、
    複数の上流パスから受信し前記受信バッファに格納されたパケットから、上流ピア、下流ピアの対応を管理するテーブルを参照して、前記特定された上流ピアに対応する下流ピアを特定し、前記特定された下流ピアに対応する送信バッファにパケットを格納するパケット同期部と
    を備えていることを特徴とするノード装置。
32. 前記送信バッファ中のパケットに関して、ピアと送信元と宛先情報の対応を格納したテーブルを参照して下流ピアで使用する送信元と宛先の情報に基づき、前記パケットを対応するネットワークインターフェイスを通して送出するパケット送信部と、
    パケット受信部、パケット送信部、パケット同期部のテーブルの内容を管理するパス管理部と
    を備えていることを特徴とする請求項３１に記載のノード装置。
33. 前記待ち時間計算部は、パケットの受信パスの前記遅延の平均値、分散から得られる確率分布関数と、あらかじめ与えられたパス毎の損失率を基に、待ち時間と到着率の関係を表す到着率テーブルを作成し、前記到着率テーブルを用いて、目標パケット到着率を満たす最小の待ち時間を求めることを特徴とする請求項３１記載のノード装置。
34. パケットの到達率を測定する到達率測定部をさらに備え、
    前記待ち時間計算部は、前記到達率測定部により測定された到達率を用いて、待ち時間を決定することを特徴とする請求項３１に記載のノード装置。
35. ネットワークと
    前記ネットワークと接続するネットワークインターフェイスと、
    前記ネットワークインターフェイスを介して、冗長パスを構成する複数のパスから同一のパケットを受信するパケット受信部と、
    前記受信したパケットの遅延に関する統計情報をパス毎に収集する統計処理部と、
    前記パス毎に収集した統計情報を基に前記パケットの待ち時間を決定する待ち時間計算部と
    を備えることを特徴とする通信システム。

Images