ネットワーク・プロトコル#67

Contact Graph Routing — 時刻表の上で最短経路を探す

常時接続を前提とするインターネットのダイクストラ法は、接続が時間窓としてしか存在しない惑星間ネットワークでは使えない。接触機会を時間窓付きのエッジとしてグラフ化する「Contact Graph」と、それを探索するCGRアルゴリズムを、蓄積遅延も含めた形で数式的に理解し、全67回のカリキュラムを締めくくる。

前提知識: dtn、ltp

DTNCGRグラフ理論経路制御ION

この回で学ぶこと

これまでの回で、深宇宙通信は地上のインターネットとはまったく異なる制約の上に成り立っていることを繰り返し見てきました。DTN(Delay/Disruption Tolerant Networking) は、送信元から宛先まで常にエンドツーエンドの経路がつながっているという地上インターネットの大前提が崩れる環境——ノード間の接続が時間窓としてしか存在しない環境——のために設計されたアーキテクチャでした。そして LTP(Licklider Transmission Protocol) は、その1本1本のリンク(ローバー↔周回機、周回機↔地上局など)が持つ長大な伝搬遅延の中でも確実にデータを転送するための、リンク層に近い信頼性プロトコルでした。

しかし、これらはいずれも「1本のリンクをどう使うか」「1つのノードでデータをどう蓄積・転送するか」という、ローカルな問題への答えでした。実際の惑星間ネットワークは1本のリンクだけでできているわけではありません。火星には複数の周回機が飛び、月には複数の中継衛星と複数の地上局が存在し、それぞれが異なる軌道・異なる可視時間帯で接続機会を提供します。あるノードに届いたデータを、次にどのノード宛てのどの接続機会に載せて転送すれば、最終的な宛先に最も早く、確実に届くのか。 これはもはや1本のリンクの問題ではなく、ネットワーク全体を見渡した**経路制御(ルーティング)**の問題です。

地上のインターネットには、この問いに答えるための洗練されたルーティング理論がすでに存在します。OSPFのようなリンクステート型プロトコルは、ネットワークをグラフとしてモデル化し、ダイクストラ法で最短経路木を計算します。しかし、この回で見ていくように、地上のルーティングアルゴリズムが暗黙のうちに置いている前提——グラフのエッジは(切れない限り)常に存在し続ける——が、DTN環境では成り立ちません。この回では、ノード間の接続を時間窓付きのエッジとして表現する Contact Graph(接触グラフ) という考え方と、それを探索する CGR (Contact Graph Routing) アルゴリズムを、グラフ理論・最短経路アルゴリズムとの対比の中で数式的に理解します。全67回にわたって物理層の変調から積み上げてきた探査機通信の階層を、ネットワーク層のこの話題で締めくくります。

直感的導入: 「道路網」ではなく「時刻表」

地上のインターネットルーティングを直感的に例えるなら、道路網です。ノード(ルータ)同士を結ぶ道路(リンク)は、故障や輻輳がない限り、いつでも通行可能だと仮定してよいものでした。だからこそダイクストラ法のような静的グラフ上の最短経路アルゴリズムがそのまま使えます。ある時刻にネットワークのスナップショットを1枚撮れば、そのグラフ構造は(短い時間スケールでは)ほとんど変化しないという前提が成り立っているからです。

ところが惑星間ネットワークでは、この前提がまったく成り立ちません。火星周回機とローバーの間の接続は、中継通信アーキテクチャの回で見たように、周回機がローバーの上空を通過する数分〜十数分のパスの間しか開きません。地上局とのリンクも、地球の自転によってアンテナが可視範囲に入っている間しか使えません。深宇宙ネットワークにおける「接続」は、道路のようにいつでも通れるものではなく、列車の時刻表のように、決まった時間帯にしか発着しないものなのです。

この比喩を続けましょう。荷物をA駅からD駅まで送りたいとして、A→B行きの列車が朝9時発、B→D行きの列車が朝9時20分発だとします。もしA→B列車が9時21分にB駅に着くのであれば、たとえ「A→B→D」という経路がグラフ上に存在していても、実際には間に合わず使えません。一方で、B駅で1本後の列車を待てば(あるいは別の経路B→C→Dを使えば)結局もっと早く着くかもしれません。「経路が存在するかどうか」だけでなく「いつ、その経路の各区間に間に合うか」を考えなければ、最短経路は決まらない——これが地上のインターネットルーティングと惑星間ネットワークのルーティングを決定的に分けるポイントです。

CGRは、この「時刻表を見ながら乗り継ぎを計算する」という発想を、グラフ理論・最短経路アルゴリズムの言葉で厳密に定式化したものです。

接触機会(Contact)とContact Graph

まず、地上のインターネットルーティングが前提とする通常のグラフを思い出しましょう。ノード集合 $V$ 、エッジ集合 $E$ からなるグラフ $G=(V,E)$ があり、各エッジ $(i,j)\in E$ には固定のコスト(伝搬遅延やホップ数) $w_{ij}$ が割り当てられています。ダイクストラ法は、このコストが時間によらず一定であることを前提に、始点から各ノードへの最短距離を貪欲に確定させていくアルゴリズムでした。

DTN環境では、この「エッジ」を次のように拡張します。ノード $i$ とノード $j$ が時刻 $t_{start}$ から $t_{end}$ の間だけ通信可能であるとき、これを**接触機会(contact)**と呼び、次の組で表します。

c = (i,\ j,\ t_{start},\ t_{end},\ R_{ij})

ここで $R_{ij}$ はその接触機会で使えるデータレート(bps)です。周回機の軌道周期や地上局の可視時間帯は、軌道力学の計算から数週間〜数年先まで正確に予測できるため、これらの $t_{start}, t_{end}, R_{ij}$ はあらかじめ**契約された運用計画(コンタクトプラン)**として、地上局のスケジューリング(前々回までのDSNスケジューリングの回と同種の予測)から決定論的に得られます。

このような接触機会の集合 $\mathcal{C} = \{c_1, c_2, \ldots, c_n\}$ 全体を、ノード集合 $V$ の上に並べたものを Contact Graph(接触グラフ) と呼びます。

G_{contact} = (V,\ \mathcal{C})

通常のグラフとの決定的な違いは、同じノード対 $(i,j)$ の間に、時間帯の異なる複数の接触機会が並存しうることです。たとえば周回機Aは1日に2回ローバー上空を通過するので、ローバーと周回機Aの間には $c_1=(rover, A, t_1, t_2, R)$ と $c_2=(rover, A, t_3, t_4, R)$ という2つの独立な接触機会エッジが存在します。これは静的グラフには存在しない構造であり、CGRのアルゴリズムはこの「時間で多重化されたエッジ」を正しく扱えるように設計されています。

到達可能時刻の伝播: ダイクストラ法の時間拡張

CGRの核心は、ダイクストラ法の貪欲な最短距離確定というアイデアを保ちながら、エッジのコストを「時間に依存する量」に置き換えることです。

通常のダイクストラ法では、ノード $i$ までの最短距離が $d_i$ と確定したとき、隣接ノード $j$ への距離候補を

d_j \leftarrow \min(d_j,\ d_i + w_{ij})

という緩和(relaxation)操作で更新していきます。CGRでは、「距離」の代わりにそのノードにデータが到達しうる最早時刻(earliest arrival time) $A(v)$ を管理し、次のように緩和操作を書き換えます。

あるノード $i$ に、データが時刻 $A(i)$ に到達しているとします。ノード $i$ から $j$ への接触機会 $c=(i,j,t_{start},t_{end},R_{ij})$ を使ってデータを転送しようとするとき、実際の送信開始時刻は、データが手元に届いている時刻と接触機会が開く時刻の遅い方になります。

t_{depart}(c) = \max\big(A(i),\ t_{start}\big)

このとき、 $t_{depart}(c)$ が接触機会の終了時刻 $t_{end}$ を超えてしまっていたら、その接触機会にはもう間に合わないので利用不可能として棄却します。

t_{depart}(c) \ge t_{end} \quad \Longrightarrow \quad c\ \text{は利用不可}

利用可能な場合、送信にかかる時間(データ量 $V$ をレート $R_{ij}$ で送るのにかかる時間 $V/R_{ij}$ )と、電波の伝搬遅延(光の速さで決まる一方向光時間、OWLT: One-Way Light Time) $\tau_{ij}$ を加えて、ノード $j$ への到達候補時刻が決まります。

A_{cand}(j\ \text{via}\ c) = t_{depart}(c) + \frac{V}{R_{ij}} + \tau_{ij}

そしてダイクストラ法とまったく同じ発想で、この候補時刻が現在の $A(j)$ の記録より早ければ更新します。

A(j) \leftarrow \min\Big(A(j),\ A_{cand}(j\ \text{via}\ c)\Big)

これを、始点ノード(データの発生源)から出発して、すべての接触機会について「今わかっている最早到達時刻から見て使えるかどうか」を確認しながら反復的に緩和していけば、ダイクストラ法と同じ貪欲法の正当性(一度確定した最早到達時刻はそれ以降更新されない、という性質)のもとで、宛先ノードへの最早到達時刻とその経路が求まります。

擬似コードにまとめると、次のようになります。

function CGR_route(source, destination, current_time, contact_plan):
    A[source] = current_time
    A[v] = +infinity  for all v != source
    predecessor[v] = None for all v
    pending = 全ての接触機会 c ∈ contact_plan

    while pending が空でない:
        # まだ確定していないノードのうち、最早到達時刻の候補が最小の接触機会を選ぶ
        c = pending の中で A_cand(j via c) が最小となるものを選択
        (i, j, t_start, t_end, R) = c

        if A[i] == infinity:
            continue   # まだ i 自体に到達できていない

        t_depart = max(A[i], t_start)
        if t_depart >= t_end:
            pending から c を除去; continue   # 間に合わない接触機会

        arrival_candidate = t_depart + V / R + owlt(i, j)

        if arrival_candidate < A[j]:
            A[j] = arrival_candidate
            predecessor[j] = c

        pending から c を除去

    # predecessor を宛先からたどって経路を復元
    return reconstruct_path(predecessor, destination)

これは本質的に、通常のダイクストラ法における「未確定ノードの中から最小コストのものを選んで確定させる」という優先度付きの貪欲選択を、「ノード」ではなく「接触機会(時間窓付きエッジ)」を単位にして行っているだけです。計算量のオーダーも、優先度付きキューを使えばダイクストラ法と同様 $O((|\mathcal{C}|+|V|)\log|\mathcal{C}|)$ 程度に抑えられます。グラフ理論の文脈では、こうした「時間とともに構造が変化するグラフ」は**時間依存グラフ(time-varying graph)あるいは時間展開グラフ(time-expanded graph)と呼ばれ、CGRが解いているのはその上での最早到着問題(earliest arrival problem)**の一種です。時間展開グラフの手法では、各ノード・各時刻のスナップショットを別々のノードとして複製した巨大な静的グラフを作ってから通常のダイクストラ法を適用しますが、CGRはこれを陽に展開せず、接触機会というコンパクトな表現のまま探索することで、計算コストと更新コストの両方を抑えている点に工学的な工夫があります。

蓄積遅延をコストに含める

上の定式化には、すでに重要な要素が1つ組み込まれています。それが 蓄積遅延(storage delay) です。データがノード $i$ に $A(i)$ の時刻に届いていても、次に使いたい接触機会が $t_{start} > A(i)$ からしか開かない場合、データはノード $i$ の機上メモリで

\Delta_{store} = t_{start} - A(i) \ \ (\ge 0)

の時間だけ待たされます。これはまさに中継通信アーキテクチャの回で見たStore-and-Forward運用の待ち時間そのものであり、CGRの経路コストにはこの待ち時間が明示的に組み込まれています。実際、1つの接触機会 $c$ を使う際の実効的な「エッジコスト」は、次の3項の和として書き下せます。

\text{cost}(c) = \underbrace{\big[t_{start}(c) - A(i)\big]_+}_{\text{蓄積遅延(待ち時間)}} + \underbrace{\frac{V}{R_{ij}}}_{\text{伝送時間}} + \underbrace{\tau_{ij}}_{\text{伝搬遅延(OWLT)}}

ここで $[x]_+ \equiv \max(x, 0)$ です。地上のダイクストラ法における静的な辺コスト $w_{ij}$ が、CGRでは**「今この瞬間にどのノードにいるか」に依存して値が変わる時間依存コスト**に置き換わっている、という点がここまでの議論の核心です。この待ち時間の項があるからこそ、「一見遠回りに見えるが、待たずにすぐ出発できる経路」が、「近道に見えるが、次の接触機会まで長時間待たされる経路」に勝つ、という地上のルーティングでは起こりえない逆転が正しく評価できるようになります。

また、この定式化は暗黙のうちにFIFO性(先に出発したデータが後から出発したデータに追い越されない) が成り立つ場合を想定していますが、実際には複数の異なる接触機会(たとえば高速だが遅く開く接触機会と、低速だが早く開く接触機会)が並存する場合、後から出発したデータの方が先に宛先へ着くという追い越しが起こりえます。ダイクストラ法の貪欲選択(常に最小到達時刻の候補から確定させていく)は、こうした追い越しが起こる状況でも正しく最早到達時刻を求められるように設計されている点が重要です。

実務での使われ方

NASA/JPLのION実装

CGRは理論だけの存在ではなく、NASAジェット推進研究所(JPL)が開発した ION (Interplanetary Overlay Network) というオープンソースソフトウェアスタックの中核ルーティングエンジンとして実装され、実際に運用されています。IONはDTNのBundle Protocol、LTP(前回)、そしてCGRを含む一連のDTNプロトコル群をひとまとめにした実装で、2008年にはDINET (Deep Impact Networking) 実験として、太陽系空間を飛行中のEPOXI(旧Deep Impact)探査機を使い、深宇宙環境で実際にDTNプロトコルスイートを動作させる世界初の実証実験が行われました。それ以降もISS(国際宇宙ステーション)搭載機器での technology demonstration など、複数のミッションでIONとCGRの運用実績が積み重ねられています。

CGRのアルゴリズム自体は、JPLのScott Burleighらによって考案され、後にCCSDSの正式勧告として標準化が進められました。現在はCCSDSの**SABR (Schedule-Aware Bundle Routing)**勧告(CCSDS 734.3-B)として、コンタクトプランに基づくスケジュール認識型のバンドルルーティングの標準仕様が規定されており、CGRはこの標準の代表的な実装アルゴリズムという位置づけになっています。

月・火星の将来的なメッシュ状ネットワークへの応用

CGRが真価を発揮するのは、中継ノードが1つではなく、複数の中継衛星・複数の地上局が入り組んだメッシュ状のネットワークを構成する場合です。中継通信アーキテクチャの回で触れたNASAのLunaNet構想やESAのMoonlight計画では、月を周回する複数の中継衛星、月面の複数の拠点、地球側の複数のDSN局が、それぞれ異なる軌道・異なる可視スケジュールで接続機会を提供することになります。このような環境では、「今どの中継衛星を経由すれば、目的の月面拠点、あるいは地球に最も早くデータを届けられるか」という問いに、運用者が手作業で答えることはもはや現実的ではありません。

軌道要素からあらかじめ計算されたコンタクトプラン(数週間から数ヶ月先までの接触機会のスケジュール)を各ノードに配布しておけば、各ノードはCGRのアルゴリズムを使って、通信のたびにネットワーク全体を見渡した最適経路を自律的に計算できます。これは、地上のインターネットのようにリアルタイムで経路広告(ルーティングアップデート)をやり取りする方式が、光時間の遅延ゆえに現実的でない惑星間ネットワークにおいて、決定論的な将来予測に基づく経路計算という代替手段を与えるものです。将来の月・火星の通信インフラが、単一の中継衛星に依存する脆弱な構成から、CGRによって自律的に経路選択される冗長なメッシュ・ネットワークへと進化していくことが期待されています。

演習問題

ノード $i$ にデータが時刻 $A(i)=100$ (単位: 分、ミッション開始からの経過時間とする)に到着しているとする。ノード $i$ から $j$ への接触機会が $c=(i, j, t_{start}=130, t_{end}=180, R_{ij}=500\ \text{kbps})$ 、送るデータ量が $V=6000\ \text{kbit}$ 、伝搬遅延(OWLT)が $\tau_{ij}=8$ 分であるとき、この接触機会は利用可能か判定し、利用可能ならノード $j$ への到達候補時刻 $A_{cand}(j)$ と、その内訳(蓄積遅延・伝送時間・伝搬遅延)を求めよ。
上の問題の状況で、もし接触機会の終了時刻が $t_{end}=145$ だった場合、この接触機会は利用可能か。利用できない理由を、本文中の判定条件 $t_{depart}(c) \ge t_{end}$ を用いて説明せよ。
ノード $i$ から宛先ノード $k$ へは、次の2つの経路が考えられるとする。経路Aは接触機会 $c_1$ ( $i\to m$ 、待ち時間5分、伝送+伝搬合計20分)と接触機会 $c_2$ ( $m\to k$ 、 $c_1$ 着後すぐ利用可、伝送+伝搬合計10分)の乗り継ぎ。経路Bは接触機会 $c_3$ ( $i\to k$ の直接接続だが、 $t_{start}$ まで40分の待ち時間が生じ、伝送+伝搬合計は5分)の1本。それぞれの総所要時間(= $A(k)-A(i)$ )を計算し、CGRのダイクストラ的な貪欲選択がどちらの経路を選ぶかを説明せよ。
地上のインターネットで使われるダイクストラ法をそのままDTN環境の経路計算に適用しようとすると、どのような問題が起きるか。本文で述べた「エッジコストが時間に依存する」という性質と、蓄積遅延の概念を踏まえて、自分の言葉で説明せよ。

まとめと次回予告(このカリキュラム全体の締めくくりとして)

Contact Graph Routingは、地上のインターネットが前提としてきた「常時接続」という土台を取り払い、接続を時間窓付きの接触機会として明示的にモデル化し、ダイクストラ法の貪欲最短経路探索を「時間依存のエッジコスト」の上で成り立たせるという、グラフ理論とネットワーク工学の見事な融合でした。蓄積遅延という一見地味な概念が、経路コストの数式の中にきちんと居場所を持つことで、惑星間ネットワークという極めて特殊な環境でも、地上のルーティング理論の精神——グラフ上の最短経路を見つける——がそのまま生き続けていることを見てきました。

そしてこの回をもって、探査機通信システムを構成するすべての階層を、私たちは一通り旅してきたことになります。振り返ってみましょう。旅は物理層の最も基本的な問いから始まりました。ビットという抽象的な情報を、電波の位相の揺れという物理量に変えるPCM/PSK/PMの3段構成、そしてQPSKやGMSKのような、より電力効率とスペクトル効率に優れた変調方式へと発展し、畳み込み符号とビタビ復号からLDPC符号・ターボ符号に至る誤り訂正符号の理論が、シャノンの通信路容量という情報理論の限界にどこまで迫れるかを競い合ってきました。

その上には、測距・追跡層がありました。数億kmの彼方で雑音に埋もれかけた微弱な残留搬送波を、PLLがフィードバック制御によって片時も見失わずに追い続け、トランスポンダのコヒーレントターンアラウンドが、往復の電波遅延から探査機までの距離とドップラー速度を測距・DDORといった手法で精密に測り出し、それが軌道決定や、時には一般相対性理論の検証にまで使われてきたことも見ました。

さらにその上には、この精密な信号を実際に地上で受け止めるシステム層がありました。DSNの巨大なパラボラアンテナ群、マーザー低雑音増幅器が生み出す限界近くのG/T性能、そして近年ますます存在感を増すSDR(ソフトウェア無線)による柔軟な信号処理基盤。これらは全世界のミッションを支える有限な資源であり、DSNスケジューリングの複雑な制約充足問題や、国際相互運用の標準化の枠組みが、その資源を公平かつ効率的に配分してきました。

そして今回、その最も高い階層——ネットワーク層——にたどり着きました。中継通信アーキテクチャによって複数ホップに分割された通信路を、DTNが「常時接続を前提としない」という発想で束ね直し、LTPが1本1本のリンクの信頼性を担保し、そして今回のContact Graph Routingが、複数の中継ノードが織りなすネットワーク全体を見渡して、データが最も早く届く経路を選び取る——物理層のたった1ビットの位相の揺れから始まった旅は、惑星規模、そして将来は太陽系規模のネットワーク全体を俯瞰する視点にまで、私たちを連れてきてくれました。

この67回で学んだ各階層は、独立した技術のようでいて、実は互いに支え合っています。変調方式が決めるビット誤り率は誤り訂正符号の設計を規定し、誤り訂正符号が確保するリンク信頼性はDTNのバンドル転送の前提となり、DTNが可能にする蓄積転送はCGRが探索する接触グラフのエッジそのものになる——探査機と地球を結ぶ1本の通信リンクは、これほど多くの物理学・数学・工学が積み重なって、ようやく成立しているのです。次に夜空を見上げて、数億km彼方を飛ぶ探査機からの電波を思うとき、その電波が辿ってきたこの長い階層の旅を、ぜひ思い出してみてください。

参考文献

S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, K. Scott, H. Weiss, “Delay-Tolerant Networking: An Approach to Interplanetary Internet,” IEEE Communications Magazine, 2003
S. Burleigh, “Contact Graph Routing,” IETF Internet-Draft (draft-burleigh-dtnrg-cgr)
CCSDS 734.2-B, CCSDS Bundle Protocol Specification
CCSDS 734.3-B, Schedule-Aware Bundle Routing (SABR)
CCSDS 734.1-B, Licklider Transmission Protocol (LTP) for CCSDS
NASA/JPL, Interplanetary Overlay Network (ION) DTN Implementation, オープンソースソフトウェア一式および付属ドキュメント
E. J. Birrane et al., “An Analysis of Contact Graph Routing in Delay Tolerant Networking,” JPL/NASA report
A. Casteigts, P. Flocchini, W. Quattrociocchi, N. Santoro, “Time-Varying Graphs and Dynamic Networks,” International Journal of Parallel, Emergent and Distributed Systems, 2012
J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76