ネットワークの3軍問題

ネットワークには「ネットワークの3軍問題」というAck処理に関するパラドックスがあるという話.

1. 下記のようにA,C連合軍がB軍を挟撃できる状態で,AC軍が同時に突撃できればA,C軍が勝ち,
同時に突撃できないとB軍が勝つ.


A軍→ B軍 ←C軍
(A軍とC軍が同時に突撃できれば勝ち)


2. A,C連合軍は伝令役を使い,双方の突撃の意思が確認できたところで突撃する

3. ただし伝令役はB軍をまたいで向かう必要があり,途中でB軍に捕虜として
つかまる可能性がある.

上記のような条件を与えられた場合,A、C連合軍がB軍に勝つチャンスはない.

一見A軍がC軍に伝令を送り,C軍がA軍から伝令を受け取った時点で A軍に伝令を
送り返せば突撃はできそうに見える.しかし伝令はB軍 に捕まる可能性があるため,
C軍はA軍に正しく伝令が伝わったかどうか確認する術がなく,突撃できない.


ではA軍にC軍からの伝令が戻ってきた時点でさらにC軍に伝令を伝えてみてはどう
だろう?これも状況は同じで,A軍はC軍に正しく伝令が伝わったか確認できないため,
やはり突撃はできない.

この場合

A軍<->C軍のやりとり = パケット及びAck
B軍 = 信頼性のない通信路(例えばIPネットワーク)

と考えるとIP網においては正しい通信ができないことになってしまう.もちろん
このインターネット時代においてそんなことはありえないので,TCP/IPがこの問題に
ついてどう解決しているか これから考察してみる


結論から言うとネットワークの3軍問題に関する本質的な
解答は存在しない.


TCPにあるのは適当な時間にデータがこなかったら先方に
再送依頼を行う再送処理だけで,双方で同時に条件が一致
しないとダメという用件は必要ないので,問題はない.

この問題に関しては工学的にはいろいろな仮定をおくことで解決してる.
例えばたいていのケースにおいては正しくデータは届くということを前提に,
データを送り出したら終了(突撃)で,一定時間届いてなかったら再送依頼を出す
といった具合だ.


なおTCP/IPはデータの受け取りの終了に関して下記の方法を
とっている(参考まで)


1. データの受け取り側は最終データが届いたら終了通知(FIN)
 を先方に投げてFINの到着を確認することなく終了.


2. 送信側はハンドシェイク後はデータを最後まで送ったら
 FIN_WAIT待ちで待機し,FINが来たら終わり.FINがこなく
 ても一定時間再送処理がこなければ届いたと仮定して
 セッションを切ってしまう.


「ネットワークの3軍問題」は「データネットワーク」で初めて知った単語だ.
Google先生に聞いても検索できないので, これは翻訳者の造語なんだと思う.

なお「データネットワーク」はネットワークについての各種問題をきちんと
取り扱ってるすげーいい本なので、興味がある人は是非.
(日本語訳は第一版の訳で今は残念ながら絶版)

データネットワーク

データネットワーク

Data Networks (Pie)

Data Networks (Pie)

なんだかスゲー高いですな.学生時代によく2冊も買えたな…


(おしまい)

検索エンジン用キーワード:
「3軍問題」「三軍問題」「ネットワークの三軍問題」「ネットワークの3軍問題」

追記

ビザンチン将軍問題というらしいです.