プロトコル解説, referer bomb

July 05, 2004

プロトコル解説

昨日の UDP Reflector のプロトコル解説をざっと書いてみました。かぴのすけへの返事でも書きましたが、このページにあるアーカイブには .class、.java 両方とも含まれていますので、実際のソースコードを読んで動きを確認したい方はそちらをご参照ください。

下記プログラム¹を実行して www.digitune.org の 15315 番ポート宛に UDP パケットを送信してくれる人募集(笑²。出来ればそのときの送受信パケットダンプもあると助かるんですが…。

#include <sys/types.h>  
#include <sys/socket.h>  
#include <netinet/in.h>  
#include <sys/uio.h>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <unistd.h>  
#include <netdb.h>  
#include <arpa/inet.h>  
#include <sys/errno.h>  
  
extern int h_errno;  
  
int main(int argc, char *argv[])
{  
	int sd;  
	char buf[256];  
	int messagelength;  
	struct sockaddr_in server;  
	struct hostent *he;  
  
	/* 引数のエラー処理 */  
	if(argc != 4){  
		fprintf(stderr, "usage: %s SERVER_NAME SERVER_PORT MESSAGE\n", argv[0]);  
		exit(1);  
	}  
  
	/* socketの生成。SOCK_DGRAMがudp用 */  
	sd = socket(AF_INET, SOCK_DGRAM, 0) ;  
	if(sd < 0){  
		perror("socket: ");  
		exit(1);  
	}  
  
	memset((char *)&server, 0, sizeof(server));  
	server.sin_family = AF_INET;  
	server.sin_port  = htons(atoi(argv[2]));  
  
	/* gethostbyname による名前引き */  
	he = gethostbyname(argv[1]);  
	if(he == NULL){  
		fprintf(stderr, "gethostbyname() failed: %s\n", hstrerror(h_errno));  
		exit(1);  
	}  
	memcpy((void *) &(server.sin_addr), (void *) he->h_addr, he->h_length);  
  
	/* バッファの初期化 */  
	memset(buf,0,sizeof(buf));  
	strncpy(buf, argv[3], sizeof(buf) - 1);  
	messagelength = strlen(buf);  
  
	/* サーバーへの送信 */  
	if(sendto(sd, buf, messagelength, 0,  
			(struct sockaddr *) &server, sizeof(server)) == -1){  
		perror("sendto");  
		exit(1);  
	}  
  
	memset(buf,0,sizeof(buf));  
	buf[1] = 0x10;  
  
	/* サーバーへの送信 (2) */  
	if(sendto(sd, buf, 3, 0,  
			(struct sockaddr *) &server, sizeof(server)) == -1){  
		perror("sendto");  
		exit(1);  
	}  
  
	close(sd);  
	exit(0);  
}

referer bomb

昨日の日記の referer がエッチサイトで山盛りになってますね(笑。なんだかなぁ。

かぴのすけ (Tue, 06 Jul 2004 22:38:58): ソォス見た。ひさびさに java のコード見たけどキモいなこの言語。
インナークラスとか C++ でもできるけどまづやらんよ。

内容の方は即興にしちゃよく出来ておる。気はするがもっとスマートに
書けそう。クライアントの妥当性チェックとかはクライアントクラス側で
やるとか。

ＵＤＰの場合、やはり最大のネックは再送問題チックぽい。で、プロトコル
とも絡んでくるけどこの作りだと不十分ぽい感じがしないでもない感じ。
再送要求がさらにロストした場合とかだとマズ気。

そもそもリアルタイム系だと再送もあまりしたくないので、保険で同じパケット
を同時に２〜３個送っときたいわけだが、今の仕組みだとサーバが粘着気味
なので一個でもロストしよーもんなら再送要求がうざい。全部ロストしてたら
再送要求しなさいと。

それからグループ情報をエントリの折り返しのみで送ってるようだが、これ
だとエントリの順番で得られる情報に過不足が出まいか。誰かがエントリした
ら、その都度グループ情報をブロードキャストしれ。

なんかもう他にもいろいろあるけど、とりあえずこのぐらいってことでー。シーユー。
Digitune (Tue, 06 Jul 2004 23:18:17): おうおーうコメントさんきゅ。

> ひさびさに java のコード見たけどキモいなこの言語。
> インナークラスとか C++ でもできるけどまづやらんよ。

キモいとはなんだキモいとは。僕は特にインナークラス好きなのかもしれん。ときどき３ネストとかやっちゃって「うひょー」となるときがある。

> クライアントの妥当性チェックとかはクライアントクラス側で
> やるとか。

確かに。そういうメソッドを用意した方が意味的にはすっきりするね。

> 再送要求がさらにロストした場合とかだとマズ気。

再送要求のさらなるロストはまだいいんだが、今のプロトコルだとパケットの並び (シーケンス) にセンシティブ過ぎるのがヤバい。どっかでパケットがひっくりかえると必要以上の再送要求＆応答が飛びまくるような気がする。

> 今の仕組みだとサーバが粘着気味
> なので一個でもロストしよーもんなら再送要求がうざい。全部ロストしてたら
> 再送要求しなさいと。

サーバを粘着とするか淡白とするかは結構悩みどころ。今のトポロジだと再送要求出来るのはあくまでもとなりのノードまでなので、淡白にするといざ「やっぱロストしたやつが欲しい」と思った時に最高２ hop の通信が発生してしまう。それでもいいっちゃいいんだが。

トポロジについても普通に考えるとこれ以外考えられないが、例えば直接通信可能なクライアント同士は直接通信させるよう suggestion する、ってのも面白いか…しかしだーいぶ複雑になりそう。セキュリティ的なこととかも考えると失うものと得るもののバランスが良いとは言えないかな。

> それからグループ情報をエントリの折り返しのみで送ってるようだが、これ
> だとエントリの順番で得られる情報に過不足が出まいか。誰かがエントリした
> ら、その都度グループ情報をブロードキャストしれ。

グループ情報 (ってのはチャネルに参加してるクライアントの情報、ってことだよね？) は現在ノーケアだ。ENTRY への返事は ENTRY を投げてよこしたクライアントにしか送られない。仮想的にとはいえブロードキャストが可能なのだから、グループ情報については IP Messenger と同じように「HELLO をブロードキャスト」「全員が返答」というロジックでいいじゃん、と思っているんだがどうか。
Digitune (Tue, 06 Jul 2004 23:43:41): ちと追記。

> 「HELLO をブロードキャスト」「全員が返答」というロジックでいいじゃん。

というのはもちろんアプリケーション側ロジックとしてそういうのを用意して勝手にやればいいじゃん、という意味だ。インフラたる UDP Reflector 側がケアするもんでもなかろうと。このへんがレイヤー切替えポイントなわけだ。

とはいえその時点のクライアントのリストは UDP Reflector 側は保持してるわけで、ケチケチしないでそれをくれっ！という気持ちも分かる。実は最初はクライアントリストを得るコマンドも用意してたんだが、実装がめんどくさくなって削っちゃったんだよねー(笑。
かぴのすけ (Wed, 07 Jul 2004 01:13:53): つ〜か、サーバは一個だけ作れば良さそうなもんなのに対してクライアントはポコポコ作られた方が良いので、基本的にはサーバを超高機能野郎にしてクラ側はできるだけ簡素にしたい。

もちろん、ライブラリでうまいこと複雑さが隠蔽し切れれば中身が複雑でも構わんので、必ずしもクラ側が簡素でなければならないことはないわけだがー。

パケの順序問題はアクノリッジ見て次を出すか、先走ったパケをある程度キャッシュしとくか。既にパケ履歴は持ってるから後者が楽か。

あと、いくつか指摘。

パケが想定より古いかどうかのチェックを次のロジックで行っているが、これだと古くなくてもパケ番号だけラップアラウンドしたときに true になってしまう。oops!

// older packet?
if(sender.getNextReceiveSequence() > packet.getSequenceNumber() ||
(packet.getSequenceNumber() - sender.getNextReceiveSequence()) > 250){

スキップパケットを見つけた後に再送要求を出しているが、スキパケの一つ前を再送要求しているので二つ飛んでたりするとハマる。想定パケ番号で再送要求すべき。

あと再送要求が落ちるとフリーズしかねないので返事が来るまで再送要求をリピートすべき。

と、なんかまだまだたくさん出てきそうなんでとりあえずこのぐらいにしといたらー。
Digitune (Wed, 07 Jul 2004 08:06:22): > つ〜か、サーバは一個だけ作れば良さそうなもんなのに対してクライアントはポコポコ作られた方が良いので、基本的にはサーバを超高機能野郎にしてクラ側はできるだけ簡素にしたい。

僕は逆だと思うな。クライアントはバグってたらリスタートすればいいけど、サーバはずっと走り続けなければいけないわけで、バグやトラブルを避けるためにも可能なかぎりシンプルであるべき。シンプルで応用性が高い仕様にしといて、後はクライアント側が好き放題やる、というのが好みだ。

> パケの順序問題はアクノリッジ見て次を出すか、先走ったパケをある程度キャッシュしとくか。既にパケ履歴は持ってるから後者が楽か。

TCP のようにいちいち ACK を待つ、というのも最初考えたんだが、ゲームに使うプロトコルとしてはリッチ過ぎると感じた。先走ったパケットは今でも保持はしてるので、余計な再送要求が飛ぶことを厭わなければ今のままでもいいのかな。

> パケが想定より古いかどうかのチェックを次のロジックで行っているが、これだと古くなくてもパケ番号だけラップアラウンドしたときに true になってしまう。oops!
>
> // older packet?
> if(sender.getNextReceiveSequence() > packet.getSequenceNumber() ||
> (packet.getSequenceNumber() - sender.getNextReceiveSequence()) > 250){

|| の後ろでラップアラウンド時に対処してるつもりなんだけど、間違ってる？
通常のパターン→期待するシーケンス=5、やってきたシーケンス=4→前項が true
ラップアラウンド時のパターン→期待するシーケンス=0、やってきたシーケンス=255→後項が true
ラップアラウンドを挟んでパケットが５つ以上連続してロスト (または連続して 250 個以上パケットがロストする(！)) すると破綻しちゃうけどねー。

> スキップパケットを見つけた後に再送要求を出しているが、スキパケの一つ前を再送要求しているので二つ飛んでたりするとハマる。想定パケ番号で再送要求すべき。

これもわざとこうしてるわけだが、例えば３つロストした場合、とりあえず届いたパケットは保持しておいて、一つ前、二つ前、三つ前と順に再送要求 (期待している一番前のものがくるまでは必ず再送要求になるので) すればシーケンスが揃う。届いたパケットはスタックに保管してあるので上から pop していけば正しいシーケンスでパケットを発信出来る。

まぁ再送要求中に新規のパケットが送られてくることなんかに対処しないと本当はちゃんと動かないんだけどね。今のままだとスタックにむちゃくちゃな順序でパケットが積まれる可能性がある。本当は古いものや重複したものは適宜捨てて、順序通りに積まにゃならん。ここは要修正。

そういや昨日の淡白なサーバに対する考察だが、今のままの「シーケンス番号は隣接ノード間でのみ保持」というパターンだとそもそも再送要求出来ないことがあるね。大元の発信元のシーケンス番号をずっと引きまわすようにすると、クライアントは他の全てのクライアントのシーケンス番号を保持しなければならなくなる。ビミョー。

> あと再送要求が落ちるとフリーズしかねないので返事が来るまで再送要求をリピートすべき。

ゲームのためのサーバなので、かなりの頻度 (最低１秒に１回くらい。ちなみに FFXI なんかだと１秒に２〜３回くらい常にパケットをやりとりしている) で常に通信が行われていることを前提にしている (少なくとも keepalive のために３０秒に一回は通信しないといけないわけだし)。その前提では再送要求がロストしても、すぐに次の (新しすぎる) パケットがやってくるので、正しいパケットを得るまではずっと再送要求を出し続けることになる。再送要求は新しすぎるパケットの直前から順に繰り返されるため、新しいパケットが送られてくる回数分だけ再送シーケンスを繰り返すことになる。常に新しいパケットが送られてくる前提なら、いつかは全シーケンスが揃って正常系に戻ってくる。はず。

が、上記ロジックにはもちろんサーバ側の「新しすぎたパケットを保持するところ」がちゃんと順番に重複無しにパケットを保持することが前提になっているが、今の実装だとインチキ過ぎる。ここのところは直さないとね。
Digitune (Wed, 07 Jul 2004 08:29:24): > || の後ろでラップアラウンド時に対処してるつもりなんだけど、間違ってる？

わかった。ラップアラウンドを挟んで新しすぎるパケットが来た時 (パケットロストしたとき) に破綻するのか。
期待するシーケンス＝255、やってきたシーケンス＝0→前項が true。よって本当は再送要求が必要なのに単に捨てられてしまう。

前項も後項のように不等号化する必要がある、ってことだな。さんきゅ。
Digitune (Wed, 07 Jul 2004 08:54:54): 結局こんな感じにした。

// older packet?
int diff = sender.getNextReceiveSequence()
- packet.getSequenceNumber();
diff = (diff < 0) ? diff + 0x100 : diff;
if (diff > 0 && diff < 128) {

やってきたパケットが望んでいたものに対して前にあるか、後ろにあるかが問題で、後ろにあるものだけを捕捉したい、というわけでこんなんで良いと思うのだがどうだろう。
Digitune (Wed, 07 Jul 2004 09:15:31): お留守番中。

> ビミョー。

受信したパケットシーケンスの完全性や順序性を保証しなくてもいいアプリケーションもあるだろうから (常に時刻情報＋絶対的な値でデータをやりとりするやつらとか)、それらは上のレイヤーで良きに計らってよ、ということにして UDP Reflector のレベルでは一切気にしない、というのも手ではある。そうするとシーケンス番号に関するコントロールが一切なくなってさらに相当シンプルになる。

ここは IP のセオリーにしたがって、そういう完全性や順序性を保証したい人は TCP ベースのプログラムを使い、それらがいらない人は UDP ベースのプログラムを使うことにして、再送問題なんか考えないことにする、というのがいいのかなぁ。
かぴのすけ (Wed, 07 Jul 2004 14:14:16): ゆうきうモード〜。昨日から頭いてーのでソォス読みづらいYO!。

> クライアントはバグってたらリスタートすればいいけど、サーバはずっと走り続けなけ
> ればいけないわけで、バグやトラブルを避けるためにも可能なかぎりシンプルであるべき。

クライアントのためにサーバ作るわけで、クライアントのフリーズとか遅延とか
リスタートとかそういう不便さは避けたいわけだ。あと、クラ作るのを極力楽に
したい。まー、今のところはサーバ作り遊びでいーけども。

> 先走ったパケットは今でも保持はしてるので、余計な再送要求が飛ぶことを厭わなけ
> れば今のままでもいいのかな。

リッチなのはいいとして、アクノリッジだとレスポンスが懸念され得るわな。

> パケットが望んでいたものに対して前にあるか、後ろにあるかが問題で、後ろにある
> ものだけを捕捉したい、というわけでこんなんで良いと思うのだがどうだろう。

byte にキャストすれば一撃だと思うが、まーこれでもいーんじゃん。

> 一つ前、二つ前、三つ前と順に再送要求 (期待している一番前のものがくるまでは
> 必ず再送要求になるので) すればシーケンスが揃う

抜けた分全部をいちいち再送要求するのも重そうだから、これの方がいーのかな。

再送要求をリピートしない点などはクラ側で多くの面倒見る方向性ということで
理解した。が、クラであんまり面倒見たくないんだな。

パケ番管理に関しては現状で問題なかろう。隣接ノード間できっちり責任を果たせば
問題ない。

> ここは IP のセオリーにしたがって、そういう完全性や順序性を保証したい人は TCP
> ベースのプログラムを使い、それらがいらない人は UDP ベースのプログラムを使うこ
> とにして、再送問題なんか考えないことにする、というのがいいのかなぁ。

こっちはもともとカイレラみたいなのを想定してるんで完全性、順序性は必須なん
だよね。ＴＣＰの方が確実ではあるが、平均的なレスポンスはＵＤＰの方が良さそ
うな感じはする。一秒に数回ごときの確認パケでは全然レスポンス悪いので、ロス
パケに関してはもうちょい対策が必要だろう。同じパケを指定数分同時に送るとか。

それからＢＧでパケタイムアウト処理しているよーだが、安直なシンクロでは
タイミングによって例外が出てくる可能性もあろう。シンクロ専門オブジェクト
でタイミングを明示的にしてはどうか。まー、例外上等！なら別にいーが。

C++ への移植はちょっと考えといたらー。
Digitune (Thu, 08 Jul 2004 01:49:23): > 再送要求をリピートしない点などはクラ側で多くの面倒見る方向性ということで
> 理解した。が、クラであんまり面倒見たくないんだな。

プロトコル的には公平なんだが、サーバが粘着ポリシーなためにクライアントのやるべきことが多いように感じる、ってことだな。クライアントも粘着ポリシーならばサーバ側、クライアント側でやるべきことに差はない。

> こっちはもともとカイレラみたいなのを想定してるんで完全性、順序性は必須なん
> だよね。

「カイレラ」ってなんだ？ Internet 環境では数百 ms の遅延くらいは結構普通らしいから、一秒間に数回以上のレスポンスを望むのは難しいらしーぞ。逆に言えば、そのくらいのディレイがあっても破綻がないようなロジックを考える必要がある、と。

> それからＢＧでパケタイムアウト処理しているよーだが、安直なシンクロでは
> タイミングによって例外が出てくる可能性もあろう。シンクロ専門オブジェクト
> でタイミングを明示的にしてはどうか。まー、例外上等！なら別にいーが。

「シンクロ専門オブジェクトでタイミングを明示的に」の意味が良く分からないんだけど、例えば「クリーニング中」みたいなロックをかけて、その間は一切トランザクションを停止する (つまりジャイアントロック戦略)、ってこと？同期セクションは極小化せよ、というのはセオリーだと思っていたんだがな…。

「タイミングによって例外が出て」こないようにするためにきめ細かい同期処理を行っているわけで。

…とゆーわけで上にも書いたが再送処理は全部削除しちゃいました。TCP ならかぴのすけのサーバと大差ないから、クライアントも簡単に作れることでしょう。

Google して出てきたサイトにあったサンプルプログラムを少し改造して作ったんですが、元のサイトがどこだか分からなくなってしまいました…。すみません。 ↩︎
まだ検証出来てないのです。 ↩︎

Prev | Next

プロトコル解説, referer bomb

プロトコル解説

referer bomb

コメント