この記事は、Competitive Programming Advent Calendar Div2013（← リンク先が閉鎖したのかスパムと化していたのでリンク削除済み）の11日目の記事です。
さて、以前にTeXで競技プログラミングは可能か？という記事を見たことがあります。TeXで競技プログラミングはジャッジサーバーさえあれば可能であろうという結論でしたが、ではルーターではどうでしょう。
というわけで、今回はルーターで競技プログラミングを行うことは可能か？について考えていきます。他の日のみなさんが書いているような有益な記事を期待している方には申し訳ありません。また、そのため、競技プログラミングの知識は必要ありません。
まずは入出力について考えましょう。ルーターで扱える形式でなければなりませんので、今回は情報のやりとりにUDPのパケット（IP（インターネット・プロトコル）上で情報をやりとりする単位）を用い、情報はそのポート番号を用いることにしましょう。ポート番号は本来、サービスの種類を識別したりするもので、パケットごとに行き先のポート番号が設定されており、それを見ながら必要なアプリケーションにパケットを渡したり、
たくさんのルーターの間でポート番号を情報としたパケットをやりとりすることで、処理が行えるかどうかについて考えます。
さて、まずはルーターとして何を使うか決めましょう。ルーターといってもそのへんで売っているようなブロードバンドルーターだとつらそうな気がしますし（可能かどうかはわかりませんが）、どちらにしても数をたくさん用意するのは大変そうに見えます。ということで、Linuxのiptablesを用います。iptablesはLinuxをルーターとして使ったことがある方なら聞いたことがあるかもしれませんが、この記事はiptablesを見たことがないことを一応前提として書くことにします（ソースコード一行一行の説明はしないので、ソースコードは無視してください）。
iptablesはLinuxカーネルの機能として存在するパケットフィルタを設定したりするためのツールですが、便宜上、パケットを制御する機能をiptablesが持つものとして扱いましょう。iptablesでは、到着したパケットの行き先のIPアドレスやポート番号を書き換え（てその後のルーティングで目的地に迎えるようにする）たり、破棄したりといったことができます。また、フラッグを記憶することができるので、例えば不正アクセスを試みようと一分間に何回もssh（遠隔操作に用いるプロトコル）のポートにアクセスしてきたりする人を弾く、といったことや、特定のポートを事前に叩くことで別のポートを開ける、といったこともできます。これはメモリ上の変数として利用できますね。
今回はiptablesのみで実現可能なもののみを行う、ただしiptablesのみで実現可能だがより短く書くために外部コマンドを使うのはありとします（iptablesの実行は初回一回走るのみで、計算時間には関係ないので……）
ではまず、環境を構築しましょう。余計なパケットが飛び交っていると色々面倒なので、専用のネットワークを用意します。今回は家のESXi上に仮想スイッチを用意し、全ての仮想マシンをつなぎました。家にESXiがある人は画面の「構成」から「ネットワーク」を選択し「ネットワークの追加」をクリックすることで追加できますし、ESXiではないものの似た機能を持つソフトウェアであれば似たような方法でできますが、家にはそういうものはないなぁ、という場合で、かつこのページの内容をどうしても再現した場合はさくらのクラウドやAmazon EC2などのクラウドサービスを利用しましょう。
続いてこのネットワーク（と便宜上インターネットに繋がるネットワーク）に接続したUbuntu仮想マシンを何台か作りましょう。画像では7台ありますが、実際には5台しか使いませんでした。それぞれのメモリ割り当ては最低限で大丈夫です。
それぞれに、プライベートIPアドレスを割り当てて、このスイッチ上でパケットをやりとりできるようにしましょう。今回は、5台それぞれに192.168.150.1から192.168.150.5を割り当てました。それぞれのマシンに手動で設定しましょう。
それぞれのマシンではIPアドレスに加えて、IPの転送を許可する設定をします。Ubuntuの場合は /etc/sysctl.conf にある「net.ipv4.ip_forward = 1」のコメントアウトを外した後、rootで「sysctl -p /etc/sysctl.conf」します。
さて本題に入りましょう。
今回は問題として、Topcoder SRM 596のDiv 1の250点問題を取り上げます。問題の解説が目的ではないので詳しい解説は省略しますが、入力それぞれについて2進で表記した時に立っているビット数の合計と、それぞれについて2進で表記した時の桁数の最大値の和から1を減じたものが答えとなります。
では、解いていきましょう。
まず、答えの入出力を行うノードを決めます。192.168.150.1のマシンにしました。このマシンから問題を含むUDPのパケットを飛ばし、問題を解くことを指示するパケットを飛ばし、答えが返ってくるか試してみます。
パケットは、
$ nc -u <宛先IPアドレス> <宛先ポート>
とコマンドを書き、Enterを一回押すととりあえず飛びます。飛んだら、Ctrl+Cを押してncから抜けましょう。
パケットの送受信を確認するために、パケットを傍受する必要があります。
$ sudo tcpdump -i eth1
などとコマンドを書くことで、そのコンピュータ上でやりとりされているパケットを見ることができます。eth1の部分はマシンごとに合わせてください。
まずは、「入力それぞれ2進表記した際に立っているビットの合計」を求める事を考えましょう。これは192.168.150.2に担当させます。
2進表記した時の立っているビットの数については、今回めんどくさいので埋め込むことにしましょう。
iptablesではフラッグを叩いた回数を記憶することができるので、別のノードに一旦叩いて欲しい回数を指示するパケットを投げ、1ずつ減らしていって0になるまでそのフラッグを叩くことにします。話は少し変わりますが、この方法で繰り返し処理も実現可能なように見えますね。
「2進の桁数の最大値」については、パケットが来たら桁数に該当するフラッグを叩き、解答を求められた時にフラッグを上から見ていくことで実現できます。
最後にその二つを足すことを考えましょう。一つパケットが到着したらそのパケットのフラッグを記憶し、次に到着したらそのフラッグを元に目的の値のポートで、答えを求めているノードに投げましょう。
方針が定まりました。実際のソースコードです（面倒くさいと思うので読み飛ばしてください）。
192.168.150.2では以下のものを実行しましょう
#!/bin/bash
iptables -F
iptables -t nat -F
iptables -X
modprobe ipt_recent ip_pkt_list_tot=200
iptables -P INPUT ACCEPT
iptables -P FORWARD ACCEPT
iptables -P OUTPUT ACCEPT
for((i=100; i>=1; i--))
do
iptables -A PREROUTING -p udp --dport `expr $i + 32768` -m recent --name MEMORY --set -t nat -j DNAT --to 192.168.150.4:`expr $i + 32768`
iptables -A PREROUTING -p udp --dport `expr $i + 16384` -t nat -j DNAT --to 192.168.150.4:`perl bits.pl $i 32769`
iptables -A PREROUTING -p udp --dport $i -t nat -j DNAT --to 192.168.150.3:$i
done
for((i=100; i>=1; i--))
do
iptables -A PREROUTING -m recent --name MEMORY --rcheck --seconds 60 --hitcount $i -p udp --dport 40000 -t nat -j DNAT --to 192.168.150.5:$i
done
だたしbits.plは
#/usr/bin/perl
my $ret = 0;
for(my $i=0; $i<20; $i++){
if($ARGV[0]>>$i& 1){
$ret++;
}
}
print $ret + $ARGV[1];
192.168.150.3
#!/bin/bash
iptables -F
iptables -t nat -F
iptables -X
iptables -P INPUT ACCEPT
iptables -P FORWARD ACCEPT
iptables -P OUTPUT ACCEPT
for((i=100; i>=1; i--))
do
iptables -A PREROUTING -p udp --dport $i -m recent --name MEM`perl highest.pl $i 0` --set -t nat -j DNAT --to 192.168.150.2:`expr $i + 16384`
iptables -A PREROUTING -m recent --name MEM$i --rcheck -p udp --dport 40000 -t nat -j DNAT --to 192.168.150.5:$i
echo $i
done
ただしhighest.plは
#/usr/bin/perl
my $highest = 0;
for(my $i=0; $i<20; $i++){
if($ARGV[0]>>$i& 1){
$highest = $i;
}
}
print $highest + $ARGV[1];
192.168.150.4では
#!/bin/bash
iptables -F
iptables -t nat -F
iptables -X
iptables -P INPUT ACCEPT
iptables -P FORWARD ACCEPT
iptables -P OUTPUT ACCEPT
for((i=32868; i>=32768; i--))
do
iptables -A PREROUTING -p udp --dport $i -t nat -j DNAT --to 192.168.150.2:`expr $i - 1`
echo $i
done
192.168.150.5では
#!/bin/bash
iptables -F
iptables -t nat -F
iptables -X
iptables -P INPUT ACCEPT
iptables -P FORWARD ACCEPT
iptables -P OUTPUT ACCEPT
for((i=100; i>=1; i--))
do
iptables -A INPUT -p udp --dport 50000 -j DROP
done
for((i=100; i>=1; i--))
do
for((j=100; j>=1; j--))
do
iptables -A PREROUTING -p udp --dport $i -m recent --name FIRST$j --seconds 60 --rcheck -t nat -j DNAT --to 192.168.150.1:`expr $j + $i`
done
echo $i
iptables -A INPUT -p udp --dport $i -m recent --name FIRST$i --set -j DROP
done
実行してみましょう。(18, 16, 14)を投げるので、答えは10になるはずです。仕様は省略しますが、今回の実装では解答を得るためには二箇所のノードにパケットを投げる必要があります。
nhirokinet@testvm1:~$ nc -u 192.168.150.2 18
^C
nhirokinet@testvm1:~$ nc -u 192.168.150.2 16
^C
nhirokinet@testvm1:~$ nc -u 192.168.150.2 14
^C
nhirokinet@testvm1:~$ nc -u 192.168.150.2 40000
^C
nhirokinet@testvm1:~$ nc -u 192.168.150.3 40000
^C
事前に走らせておいたtcpdumpから該当するパケットを探しましょう。
22:53:04.278019 IP 192.168.150.1.55863 > 192.168.150.1.10: UDP, length 1
お、正しい答えが返ってきましたね。
あまりまとまっていませんが、そろそろまとめに入らないと日付が変わってしまうので、まとめに入ります。
とりあえず、ルーター（iptables）のみを用いて、計算を行うプログラムを書くことができました。より多くのノードを用いることにより、またより多くのフラッグを用いることによって、また16ビット以上の数字についても前半後半に分割することによって、一応複雑な計算もできるものと思われます。
しかし、ルーターはやはりパケットのルーティングに用いるべきであり、計算に使うにはあまり実用的でないように感じます。どうしても部屋にプログラマブルな装置がルーターしかなく、その環境で計算が行いたい場合でも、ルーターでプログラムを書くよりは、ポケットコンピュータを買いに行くか手で計算したほうが実用的だと思われます。
また当然ですが、おそらく世の中にはルーターを用いて競技プログラミングを行うようなジャッジサーバーは存在しないと思われるため、これで競技プログラミングをすることは現状ではできません。誰かが将来的に作ればもしかしたらできるようになるかもしれません。
こんな記事ですが、コメントや追加実験等あれば是非コメント欄にお願いします。
