他に何かすべきことがあったような気もするんだけどな….音ゲーとか.
ネットワーク符号化の基礎
とりあえず,メリットとデメリット,画期的なところをさらっと理解.出版社の森北出版は,理工系の学生が知識や概念を速習するには使い勝手がよいと思います.一方で,理学的な厳密性を片っ端から求めていくような人にはあまり向いていない気がします.ブルーバックスよりは厳密だけれども,専門書よりは厳密性よりも分かりやすさを追求しているような感覚.
第一章
導入
ネットワーク符号化を採用したデータ転送方式と,従来方式(ルーティング方式)の二種類のデータ転送方式を話題にあげて,ネットワーク符号化の概念を説明している.
- 従来方式…蓄積-転送(store and forward)
中継ノードに到着したパケット*1を送出すべきインターフェース*2に送り出すだけ.
- ネットワーク符号化を採用した方式…蓄積-符号化-転送
従来方式の中継ノードが新たに符号化の機能をもつ.
バタフライネットワークでの比較
従来方式とネットワーク符号化方式の違いを,バタフライネットワークというネットワーク*3を用いて説明している.次のpdfの前半で殆ど同じことが述べられているので,興味がある方は読んでみるとよいでしょう.
ポストモダン符号理論としてのネットワーク,置換,形式化2:ネットワーク符号 / 萩原 学
バタフライネットワーク上でネットワーク符号化を利用すると,平均スループット*4が上昇する.従来方式も適切に符号化を定義すれば表現可能である.
多品種フロー問題*5
従来の情報理論では,ネットワーク上を流れる(flow)複数の情報を混合させて処理することでは,スループット性能の改善は期待できないとされていたが,ネットワーク符号化はその反例として存在している.これにより,ネットワーク符号化理論はネットワーク情報フロー理論(network information flow theory)と呼ばれるようになってきている.
ネットワーク符号化と従来の符号化の比較
まず,従来の符号化処理は次の二種類に大別される.
- 情報源符号化…データ圧縮が目的
送出する情報の冗長性を抑えること(圧縮)で,通信効率の向上を図る.通信の速度向上を狙うのがこっち.
- 通信路符号化…誤り*6の検出訂正が目的
送出する情報に冗長性を付与することで,通信路で発生する誤りの検出・訂正を図る.通信の信頼性向上を狙うのがこっち.
ネットワーク符号化の目的は,平均スループット性能の向上にあるので,この点では情報源符号化の目的と一致している.
ネットワーク符号化のメリットとデメリット
メリット
⇒ 通信効率の向上
- トラフィックのロードバランシングが可能
⇒ 通信を行う複数の端末のうち,一つの端末に処理が偏らない通信が可能
- ネットワーク信頼性の向上
⇒ 損失した情報の復元が容易
などなど…
デメリット
- 時空間的複雑さの増大
⇒ ネットワーク符号化により計算量が増大
また,復号には全てのデータが揃わなければならず,バッファリング*9の負荷が大きい
- トポロジー依存性
⇒ 符号化がネットワークの形状に依存するため,ネットワーク構成の変化に弱い
- 連鎖反応による復号遅延
⇒ ある一か所の情報損失が他所に伝播し,復号に要する時間がその一か所の損失に引きずられ,長引く
- セキュリティ問題
⇒ 実現のうえで,セキュアなネットワーク符号化の研究が課題になっている
一章のざっくりまとめ
伝統的な情報理論では,異なる複数の情報を一つ圧縮することでは通信の効率化を図れないとされてきたが,ネットワーク符号化の発想はその常識に一石を投じるものとして現れた.しかし実用化を考えるには,符号化・復号処理の計算時間や前述の遅延,セキュリティの問題など,課題は山積みらしい.
おわりに
卒論ではネットワーク符号の一種,線形ネットワーク符号上の誤り訂正符号として知られているGabidulin符号(())の実装をテーマに学習していました.代数的構造の理解は進んだけれども,思い返すとネットワークに関する知識はあまり深く掘り下げられていなかったので,これを機に勉強してみようと思います.研究も楽しいけれど,最近は自分の理解力が何らかの形で社会に活かせたらいいなと,少しずつ前向きな気持ちになれてきています.本当に少しずつ….自分自身の関心とは離れたところでもね,ではでは.
*1:データの塊.送りたいデータの他に,このデータが何に関するデータか,誰から送られたもので誰に送るものか,などの情報を持っている.
*2:データを受け取る窓口のようなもの.送られたデータが受信しても安全なのか判断したりもする.
*3:グラフ理論の発想を物理的実体へ応用したもの.グラフ理論では主にグラフの形状や性質を研究するが,ネットワーク理論では各辺や頂点に距離・重さなどの意味を与えて現実の解釈に応用する.
*4:単位時間あたりに目的の場所に送り込める情報量
*5:ネットワーク上を流れる異なる複数の情報を"ある意味で"効率に送るにはどうすればよいか考える問題.
*6:僕は,誤り(error)が大好きです.
*7:一対一通信
*8:一対不特定多数通信
*9:一時的にデータを蓄えたり,データの集まりからデータを取得する作業