Network Coding

2008/3/28

最近巷で話題の「Network Coding」です(どんだけニッチな「巷」だよ！という突っ込みは自重願います)。既にご存知の方には今更かも知れませんが、最近これを知って発想に結構感動したので紹介してみました。

グラフ理論系の話で、「Routingでは出来ないけどCodingならできる」というキーワードが良く登場します。個人的には、まだ使いどころが良く理解できていないのですが、話としては非常に面白かったです。

XORを使って重ねる

Network Codingの最大の特徴は、途中ノードがXORで重ねる事によって伝送に必要な情報量を削減することです。以下の図は、最も単純な例を示したものです(wikipediaにあるpublic domainの図に加筆)。

まず、AとBという情報があります。このAとBを2箇所ずつ、合計4箇所に送りたいとします。このとき、1つのデータを送信するには、1つの「経路」が必要とします。

図のトポロジでは、上半分と下半分をつなぐ「経路」は3本しかないため、通常は同時にAとBを送信することは不可能です。 Network Codingでは、この解決不可能な問題を解くために、途中ノードであるxがAとBをA+BとしてXORで固めます。 yは受け取ったA+Bをそのまま転送します。

r1はAとA+Bを受け取り、r2はBとA+Bを受け取ります。 r1はAを知っているのでA+BからXORを使ってBを抽出できます。 r2はBを知っているので同様にA+BからAを導けます。

このようにして、図中上下の途中経路が3本のトポロジで4つのデータを送信することに成功します。

この「同時」にという概念は、複数の回線上を同時に流れるビットであったり、パケットであったり、回路中の電気信号であったりという応用例があるそうです。

Coding-aware Routing

このCodingと経路制御を同時に考えようと提唱されたのがCoding Aware Routingです。複数のフローを普通にShortest Pathで考えると、Codingとして集約できるフロー数が少ないようなトポロジでも、Codingに最適化した経路制御をして集約できるフロー数を増やせばより効果的にNetwork Codingができると提唱しています。

P2PとNetwork Coding

P2PとNetwork Codingは相性が悪いのではないかという論文もあります。確かに、Network Codingは決まったトポロジで行うのが効果的である事が予想されますね。コロコロとトポロジが変化するようなP2Pオーバーレイネットワークでは、使いどころが難しいような気がします。

で、どこで使うんだろう？

最初に発想を聞いたときは結構感動したNetwork Codingですが、どこで使うのが良いのかが良くわかりませんでした。 XORなので、結局まとめあげて効果的なのは2フローなんですよね。。。まあ、2つ以上をまとめあげることは可能ではありますが、例えば10個まとめあげたら、9個のオリジナルがなければ10個全部を分離する事ができないわけなので、事実上「節約」できるのは2つのうちの1つだけなんですよね。

というより、トポロジを考えないと「節約」にすらならないんですよね。 XORを解くのにオリジナルが1つは必要で、うまくやらないと2つの情報を得るために2つの情報を流すという事になり、全く「節約」になりません。

Network Codingが最初に提唱されたのは衛星通信の論文であるようです。確かに、衛星通信＋その他という考え方であれば、トポロジもガッチリ決まってますし効果がありそうです。 Network Codingを扱った論文は無線と絡めたものが多めな気もします。

いや、でも一般論として使ったら「すげーーー！」というのがありそうな気もするのですが、思いつけていないのが私の弱いところなのかも知れません。

参考

過去記事

過去記事一覧

超凄いIPv6解説書(488ページ)を無料配布します！