マルチキャスト、ISIS、IPマルチキャスト、ニュース・システム/Multicast, ISIS, IP multicast, News system

並行システム

                               システム情報系/情報工学域,
			       システム情報工学研究群/情報理工学位プログラム
			       システム情報工学研究科/コンピュータサイエンス専攻
                               新城 靖
                               <yas@cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2023/2023-05-26
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/

■今日の重要な話

■分散アルゴリズム Distributed algorithms

◆(集中)アルゴリズム / Normal (centralized) algorithms

(集中)システムで問題を解くための指令の集まり。

◆分散アルゴリズム/ distributed algorithms

要素間のメッセージの伝達の方法の集まり Message exchanges among nodes 時計を使うアルゴリズムもある。 Some algorithms use global clocks.

James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, Dale Woodford: "Spanner: Google's Globally-Distributed Database", 10th USENIX Symposium on Operating Systems Design and Implementation, 2012.

◆コンピュータを使わない分散アルゴリズムの例/ Examples of distributed algorithms with no computer

■プロセス間通信/ Interprocess Communication

5月12日の資料参照

2つの重要なパタン two important patterns

■マルチキャスト(グループ通信)/Multicast (group communication)

◆参考文献

Newer versions in English is available for free at https://www.distributed-systems.net/index.php/books/ . 日本語訳は、「分散システム」という名前で第2版(2009)まである。 2003年の第1版も良い。

◆通信の分類 classification of communication

send()4回、4つの数のプロセスが同じメッセージをreceive()。

図? 1対1の通信の繰り返し / by releated unicast send()

send()1回、4つの数のプロセスが同じメッセージをreceive()。

図? 1対多の通信/ by single multicast send()

マルチキャストなら、あるプロセスが1回 send() すると、同じメッセージが 複数のプロセスに届けられる。send() の宛先のアドレス(destination address)は、1個。

◆ブロードキャストとマルチキャスト/ broadcast and multicast

◆マルチキャスト実装の難しさ/difficulties in multicast implementation

マルチキャストは、いろいろな分散アルゴリズムでよく使われる。 それが使えれば、非常に便利。しかし、実装が難しい。

何が難しいか

◆設計の論点/ Design issues

並列処理では、closedが多い。 IPマルチキャスト のように、オープンでないとどうしようもないものもある。

対等だと、クラッシュに強い(single point of failure がない)が、何をす るにもすぐ投票が必要になる。

◆メンバシップの管理/Membership management

グループサーバを持つか持たないか。

難しいのは、メンバのプロセスがクラッシュした時。 何も言わずにグループから抜ける。

◆アドレス指定/ Addressing

◆通信プリミティブ/Communication primitives

one-to-oneの通信と同じにしたい。しかし、次のような事が難しい。 障害がなければ、それほど難しくはない。 障害を扱おうとすると、非常に難しい。

◆atomic broadcastの簡単なアルゴリズム/ Simple algorithm to realize atomic broadcast

最終的にそのうちに(eventually)、全プロセスに必ずメッセージが届く。

図? 簡単なatomic broadcastのアルゴリズム

◆メッセージの到着順/ Message ordering

one-to-one でも問題があるのに、group 通信だとさらに複雑。

total ordering は、グループ通信では実現が難しすぎる。弱いものが実現さ れる。

プロセスが複数のグループに属していると、1つのメッセージについての順序 だけ考えていてはすまなくなる。

◆スケーラビリテイ scalability

ノード数が増えた時に動くか。

◆冗長性 redundancy

障害に備えて、複数の機器、複数のネットワーク・リンクを用意する。

冗長性があると、メッセージの重複をうまく扱う必要がでてくる。

下手をすると、メッセージが増幅しながいつまでもぐるぐる回る。

◆集中システムでは in centralized sysems

集中システムでは、あるプロセスが共有メモリ(shared memory) や共有ファイ ル(shared files)に書いて、他のプロセスが読むということで、用が足りるこ とも多い。

「データが更新された」というイベントを、複数のプロセスにきちんと送り届 けようとすると、分散システムのマルチキャストと同じ話になる。

Unix の signal は、ハードウェアの割り込みと同様に、落ちることがある。

■出版・購読モデル / Publish Subscribe Model

1つのメッセージを複数の受信者が受信することもある。 送信者と受信者の関係が粗結合(loosely coupled)。 粗結合は、分散システムの構築技法では良いこと。

◆ブローカによる実装 / implementation with a broker

送信者と受信者を仲介するプログラム、ブローカ(broker)と呼ばれるサーバを 使って実装することが多い。 メッセージが小さければ、通知の中にメッセージを含めることもできる。

送信者がブローカにpublish、ブローカが受信者にnotify、受信者がreceive

図? 出版・購読モデルによるメッセージの受け渡し

◆マルチキャストによる実装 / implementation by multicasting

LAN等でマルチキャストが使えれば、マルチキャストで実装することもできる。 ブローカは存在しない。

送信者がLANにブロードキャスト、受信者がreceive

図? ブロードキャストによる出版・購読モデルの実装

◆マッチングの条件 / matching conditions

■事例1: メーリング・リスト/ Case 1: Mailing lists

メーリング・リストも、マルチキャストの一実装と考えることもできる。

メーリング・リスト、個人、個人、ネスト、個人

図? マルチキャストとしてのメーリング・リスト/a mailing list as an implementation of multicast$

■事例2: ISIS システム

分散アプリケーションのためのツールキット。 コーネル大学。 1983年-1994年。

http://www.cs.cornell.edu/info/projects/isis/

◆同期性(synchrony)

同期システム(synchronous system)
イベント(マルチキャスト)の順序が厳密に逐次的に発生する。オーバーラッ プしない。イベント(マルチキャストを含む)は、完了までの時間は、0秒。 実現不可能。
緩やかな同期システム(loosly synchronous system)
イベントは有限時間で届く。
仮想的な同期システム(virtually synchronous system)
因果関係が成り立つようにがんばる。(並行なものは、手抜き。)

◆ISISの通信プリミティブ/ Communication primitives in ISIS

ABCAST (atomic multicast)
緩やかな同期
CBCAST (causal multicast)
仮想的な同期
GBCAST (group multicast)
仮想的な同期(グループのメンバシップ用)

◆ABCAST(atomic multicast)

ABCAST は、2相コミットにより実装。

Phase 1:

  1. 送信者は、タイムスタンプを含むメッセージを全てのメンバに送る。
  2. 各メンバは、送信、または、受信したメッセージで最大のものを最初の送信者に送る。
Phase 2:
  1. 送信者は、全ての返事を受け取ると、最大のものを選び、メンバにコミット・メッセージを送る。コミット・メッセージは、タイムスタンプの順に届けられる。
メッセージを送ったのに、あるプロセスから返事がこないことがある。その時 は、コミット・メッセージではなくて、アボート・メッセージを送る。メッセー ジは、送られなかったことにする。

◆CBCAST(causal multicast)

CBCASTの実現

メンバの数:n

各プロセスは、グループごとに、長さnのベクトルVを持つ。 i番目の要素は、プロセスiから正しい順序で受信したメッセージの最後の番号。 0に初期化される。

  1. プロセスは、送信すべきメッセージがあると、 ベクトルの自分のスロットを増加させ、メッセージの一部として送信する。
  2. メッセージのベクトルをV、メモリ中のベクトルをLとする。 メッセージがjから送られてきたものとすると、次の条件の時に受け取る。 そうでないものは、この条件が満たされるまでバッファリングされる。

M1が届くまでM2の配送を遅延。

図? ISISでのCBCASTの実現/ Implementation of ISIS CBCAST.

■事例3: IPマルチキャスト/ Case 3: IP multicast

送信者が1人で、受信者が複数のメッセージをIP のネットワークで送信するこ と。UDP(データグラム)のみ。TCP(ストリーム)は対応していない。

動画像や音声など大量のデータを配信する時、複数人で同じデータを受信する 時に、同じメッセージを共有できる。

例:筑波大学で、100人の人が同じ 1M bps の動画像の「生中継(live)」データを 見る

◆IP マルチキャストのプログラミング/ Programming IP multicast

IPv4 では、IP マルチキャスト用のアドレス としてクラス D (224.0.0.0-239.255.255.255) を使う。 IPv6 では、IP マルチキャスト用のアドレスとしてff から始まるもの (ff00::/8) を使う。

送信側(sender):

受信側(receiver):

◆IP マルチキャスト可能なルータ/ IP-multicast-capable routers

ルータは、そのネットワークに特定のマルチキャスト・アドレスでメッセージ を受信するプロセスが存在するかどうかを管理する(メンバシップ管理)。他 のルータにも伝える。アドレス毎にマルチキャストのルーティング・テーブル を維持する。

送信側と受信側の間にあるすべてのルータがマルチキャストに対応していない と、受信できない。多くの IPv4 ルータは、マルチキャストのオプションを無 効にしている。

ルータは、個々のプロセスにメッセージを届ける時には、ネットワークのブロー ドキャストが使える場合には使う。たとえば、イーサネットでは、ブロードキャ ストを使う。

◆IP Mbone

IP MBone は、1990年代に IP Multicast を使った実験的なネットワーク。間に マルチキャストに対応していないルータがあったとしても、ユニキャストによ るトンネリング(tunneling by unicast)で接続する。

◆「IPマルチキャスト放送」/Broadcasting by IP multicast in Japan

日本の法律の用語(Japanese law term)。IP マルチキャストを使った、「放送 (broadcasting)」。「放送」とは、テレビやラジオや有線放送など。

今までは、インターネットで「放送」といっても、著作権法上は、「通信」に 分類されており、著作権管理の手間が大きかった。

2006年、著作権法が改定され、「IPマルチキャスト放送」を「放送」として位 置づけられるようになった。

◆IP Anycast

4つのクライアントによるsend、1つのサーバによるreceive

図? 通常の IP アドレスによるメッセージの送信

4つのクライアントによるsend、3つのサーバによるreceive

図? IP anycast によるメッセージの送信

使われている場所 特徴

■事例4:ニュース・システム/ Case 4: News systems

◆ネットワーク・ニュース/ Network News

ネットワーク・ニュース(Network news)、または、 ネットニュース(Netnews)。 英語では、Usenet と呼ぶ人も多い。 編集でカットされない、誰でもメッセージを発信できるという意味では、n対 nの通信。

ニュース・システムは、ネットワーク・ニュースを実装しているプログラムの集合。

◆ニュースシステムの設計目標/ Goals of news systems

P2P (Peer to Peer) で、成功している例。

◆RFCs

◆ニュースの記事の形式/Article format

Path: gama.is.tsukuba.ac.jp!ie.u-ryukyu.ac.jp!CALA-MUZIK!rlss-news!orie-news!not-for-mail
From: committee@fj-news.org
Newsgroups: fj.news.lists,fj.news.group,fj.archives.documents
Subject: Active Newsgroups List of fj (2007/01/15)
Followup-To: fj.news.group
Date: Mon, 15 Jan 2007 00:00:01 +0900
Organization: fj Newsgroups Management Committee
Lines: 1095
Sender: kgk@film.rlss.okayama-u.ac.jp
Approved: committee@fj-news.org
Expires: 24 Feb 2007 00:00:01 +0900
Message-ID: <active-newsgroups.part1.20070115@fj-news.org>
Reply-To: committee@fj-news.org
NNTP-Posting-Host: film.rlss.okayama-u.ac.jp
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-2022-JP
Content-Transfer-Encoding: 7bit
X-Trace: orie.rlss.okayama-u.ac.jp 1168786802 14625 192.168.0.104 (14 Jan 2007 15:00:02 GMT)
X-Complaints-To: news@film.rlss.okayama-u.ac.jp
NNTP-Posting-Date: Sun, 14 Jan 2007 15:00:02 +0000 (UTC)
Xref: gama.is.tsukuba.ac.jp fj.news.lists:240 fj.news.group:185 fj.archives.documents:205

Archive-name: fj-news/active-newsgroups/part1
Original-author: saitoh@ics.es.osaka-u.ac.jp (SAITOH akinori)
Last-change: 2006/07/20 by kgk@film.rlss.okayama-u.ac.jp

fjのニュースグループの一覧とその解説

・現在 fj にあるニュースグループ 412 個の名前と説明文です。

・この文書は「JUNET利用の手引 (第1版)」に由来するもので、
  現在はfjニュースグループ管理委員会(committee@fj-news.org)が
  維持管理を担当しています。

  出所 (題名と日付) を明示する限りにおいて、引用、転載、複製等は、
  著作者等に断りなしに、自由におこなって構いません。
  文書の一部を他の著作物に流用する等の利用は、完全に自由とします。

◆重要な記事のヘッダ/Important article headers

Newsgroups:
ニュース・グループ
From:
差出人の電子メールアドレス
Subject:
記事の題名(題目、表題)。
Date:
記事が書かれた日付
Message-ID:
メッセージ識別子。その記事に対して世界中で重複がないように付けられた文字
Path:
記事が通過したサーバ。

◆NNTPを使った記事の配送の仕組/Article transfer mechanism with NNTP

Network News Transfer Protocol (NNTP).

nnptd, nntp クライアント, インターネット

図? ネットニュースの記事の配送の仕組/Article transfer mechanism in Netnews

A server NNTPは、ニュースの記事を受け渡しする形式を決めたもの。 NNTP defines the procedures to exchange articles

◆NNTP commands and responses

NNTP(Network News Transfer Protocol) とは、ネットワーク・ニュースの記 事の転送や、記事の読み書きを行うためのプロトコルである。mnews や GNUS などのネットワーク・ニュースを読み書きするソフトウェアは、クライアント として NNTP サーバとの間に TCP/IP による通信路を開設する。そして、クラ イアントは、記事を要求する文字列や、ニュース・グループの一覧を要求する コマンドをサーバに送る。これに対してサーバは、要求された記事やニュース・ グループの一覧をクライアントに返す。表4に、クライアントからサーバへ送 られるNNTPのコマンド、表5に、サーバからクライアントへ返される応答を示 す。

表? NNTPのコマンド/ commands in NNTP

GROUP newsgroup
ニュース・グループnewsgroupを選択する。結果として、記事の数、記事の番号 の上限と下限が返される。
ARTICLE num
記事番号 num の記事の内容を得る。ニュース・グループが選択されている状態の 時に使える。
ARTICLE <message-id>
メッセージID <message-id>の記事の内容を得る。
LIST
ニュースグループの一覧を得る。
HELP
ヘルプ・メッセージの表示
QUIT
終了
POST
記事を投稿する。
IHAVE <message-id>
この記事を転送(送信)したい。

表? NNTPの応答/ Responses in NNTP

応答コード 説明
100 ヘルプのテキストが続く。
200 要求受け付け可能である(投稿可)。
201 要求受け付け可能である(投稿不可)。 
205 通信路を切断する。
211 ニュース・グループが選ばれた。記事の数、記事番号の上限、下限、ニュース・グループ名。
235 記事の転送は成功した。
335 記事を送れ。最後は、CR-LF . CR-LF 。
400 サービスを中断する。
411 そのようなニュース・グループがない。
421 もうそのニュース・グループには次の記事がない。
435 その記事は欲しくない。(もう既に受け取っている)
436 転送に失敗した。後でもう一度転送しB$iて欲しい。
437 転送に失敗した。もう転送するな。
500 コマンドが認識できなった。
501 コマンドの文法に誤りがあった。
502 アクセスが制限されている。

以下に、telnet コマンドを利用して、NNTP サーバに接続した様子を示す。
% telnet $NNTPSERVER 119[←]
Trying 130.158.80.241...
Connected to gama.cs.tsukuba.ac.jp.
Escape character is '^]'.
200 gama.is.tsukuba.ac.jp InterNetNews NNRP server INN 2.4.1 ready (posting ok).
group fj.news.lists[←]
211 120 127 254 fj.news.lists
article 240[←]
220 240 <active-newsgroups.part1.20070115@fj-news.org> article
Path: gama.is.tsukuba.ac.jp!ie.u-ryukyu.ac.jp!CALA-MUZIK!rlss-news!orie-news!not-for-mail
From: committee@fj-news.org
Newsgroups: fj.news.lists,fj.news.group,fj.archives.documents
Subject: Active Newsgroups List of fj (2007/01/15)
Followup-To: fj.news.group
Date: Mon, 15 Jan 2007 00:00:01 +0900
Organization: fj Newsgroups Management Committee
Lines: 1095
Sender: kgk@film.rlss.okayama-u.ac.jp
Approved: committee@fj-news.org
Expires: 24 Feb 2007 00:00:01 +0900
Message-ID: <active-newsgroups.part1.20070115@fj-news.org>
Reply-To: committee@fj-news.org
NNTP-Posting-Host: film.rlss.okayama-u.ac.jp
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-2022-JP
Content-Transfer-Encoding: 7bit
X-Trace: orie.rlss.okayama-u.ac.jp 1168786802 14625 192.168.0.104 (14 Jan 2007 15:00:02 GMT)
X-Complaints-To: news@film.rlss.okayama-u.ac.jp
NNTP-Posting-Date: Sun, 14 Jan 2007 15:00:02 +0000 (UTC)
Xref: gama.is.tsukuba.ac.jp fj.news.lists:240 fj.news.group:185 fj.archives.documents:205

Archive-name: fj-news/active-newsgroups/part1
Original-author: saitoh@ics.es.osaka-u.ac.jp (SAITOH akinori)
Last-change: 2006/07/20 by kgk@film.rlss.okayama-u.ac.jp

fjのニュースグループの一覧とその解説

・現在 fj にあるニュースグループ 412 個の名前と説明文です。

・この文書は「JUNET利用の手引 (第1版)」に由来するもので、
  現在はfjニュースグループ管理委員会(committee@fj-news.org)が
  維持管理を担当しています。

  出所 (題名と日付) を明示する限りにおいて、引用、転載、複製等は、
  著作者等に断りなしに、自由におこなって構いません。
  文書の一部を他の著作物に流用する等の利用は、完全に自由とします。

<中略>
.
quit[←]
205 .
Connection closed by foreign host.
% []
ここで、強調で示した部分が、キーボードからのタイプである。 この例では、ホスト $NNTPSERVER のポート番号119(nntp)のポート に、TCP/IPにより接続を試みている。続く3行は、telnet コマンドによる定 型的な表示である。通信路が開設されると、サーバは、"200" という応答を返している。これは、NNTP で定義されている応答であり、サー バが、要求を受け付け可能であり、かつ、要求としては投稿要求(POST)も受 け付けることを意味している。"200" 以降の文字列は、コメン トである。

接続されると、"group" というコマンドをサーバに送っ ている。これに対して、サーバは、"211" という応答に続けて、 記事の数、記事番号の上限、下限、ニュース・グループ名を送っている。

次に "article" コマンドを送っている。これによ り記事が転送されている。記事の最後には、"." からなる行が ある。これが、articleコマンドに対する応答の終 りを示している。

最後に "quit" というコマンドをサーバに送ってい る。これにたいして、サーバは、205 という応答を返し、続いて TCP/IP の通 信路を切断している。その下の Connection closed... は telnet コマンドが生成したメッセージである。

◆INN newsfee (sysファイル)

newsfeed は、ニュースシステム INN で、記事を送信する隣のサーバを設定す るファイル。(Bnews では sys ファイルという)。 The newsfeeed file contains neighbor news servers in the news system INN. This file is used to send articles to neighbor servers.
ME:!*/!local::
news.ie.u-ryukyu.ac.jp/ie.u-ryukyu.ac.jp:fj.*,okinawa.*:Tm:innfeed!
nadesico.cc.tsukuba.ac.jp/nadesico.cc.tsukuba.ac.jp:comp.*,sci.*,rec.*,news.*,soc.*,talk.*,misc.*,fj.*,gnu.*,tsukuba.*,campus.*,tnn.*:Tm:innfeed!
news.esys.tsukuba.ac.jp/news.esys.tsukuba.ac.jp:coins.*,tsukuba.*:Tm:innfeed!
keknews.kek.jp/keknews:tsukuba.*:Tm:innfeed!
転送の様子
maple% telnet gama.is.tsukuba.ac.jp nntp[←]
Trying 130.158.80.241 ...
Connected to gama.is.tsukuba.ac.jp.
Escape character is '^]'.
200 gama.is.tsukuba.ac.jp InterNetNews server INN 1.5.1sec2 25-Jul-1997 ready
IHAVE  <YAS.98Feb2175819@is.tsukuba.ac.jp>
335
Newsgroups: denjo.test[←]
Path: is.tsukuba.ac.jp!gama.is.tsukuba.ac.jp!is.tsukuba.ac.jp!yas[←]
From: yas@is.tsukuba.ac.jp (Yasushi Shinjo)[←]
Subject: from maple[←]
Date: Mon, 2 Feb 1998 08:58:17 GMT[←]
Nntp-Posting-Host: hlla-gw[←]
Organization: Institute of Information Sciences and Electronics, University of[←]
Tsukuba[←]
Sender: news@is.tsukuba.ac.jp (News Manager)[←]
Message-ID: <YAS.98Feb2175819@is.tsukuba.ac.jp>[←]
Lines: 2[←]
[←]
fake Path: gama.is.tsukuba.ac.jp!is.tsukuba.ac.jp!yas[←]
1998/02/02 17:58:13[←]
.[←]
235
QUIT[←]
205 .
Connection closed by foreign host.
maple% []

◆UUCP

TCP/IP が普及する以前は、UUCP (Unix to Unix CoPy) という仕組みで、 ネットワーク・ニュースが配られていた。1990年代前半まで主流。

端末、サーバ、シリアル回線、モデム、アナログ音声、uucp、

図? UUCP によるファイルのコピー/Copying a file with UUCP

ファイルのコピーの例(copying a file): uucp command
% uucp file1 host2!host3!host4!~user1/dir1 [←]

uucp link, host1, host2, host3, host4, file1, ~user1/dir/file1

図? uucp コマンドによるファイルのコピー/Copying a file with the uucp command

メールの送信の例(sending an email): 「!」を含むメールアドレスによるメールの送信
% mail -s "hello" host2!host3!host4!user1 [←]
途中のホストは、次にどのホストに転送すれば良いかを知っている。自分とは 無関係のホストのメールを中継することもある。誰が電話代を払うか、そもそ も(日本では)法律的にそのような中継をしてよいのかが議論があった。

◆故障への対応/Dealing with failure

サーバやネットワークが落ちることがある。 核攻撃が無くても落ちる。

図? A!B!C!D!E!Fのつながり。冗長リンクを含む。

図? 冗長リンクを含むニュースの配送/ Network news transfer with redundant links

◆冗長のリンクの問題/ The problem with having redundant links

問題: 同じ記事が複数の隣接するサーバから送られて来る。 Duplicate articles are sent from multiple neighbors.

◆記事の重複への対応(1)/Dealing with duplicate articles (1)

履歴(history)を利用する。 履歴の例 Example of the history file。
#gama[lib-news] 113# tail history
<19980131213101.QAA14061@ladder03.news.aol.com> 886406952~-~886282319   rec.collecting.sport.hockey/46595
<8E8622E.0015000738.uuout@venture.fipnet.fi>    886406953~-~886231080   comp.sys.ibm.pc.demos/3590
<34D57354.592B@pp.kolumbus.fi>  886406953~-~886403924   comp.sys.ibm.pc.games.action/24913
   886406953~-~886282077   control/403867
<01bd2b53$921e9680$LocalHost@santotan>  886406953~-~886282077
<6b3s6k$85k$1@talia.mad.ibernet.es>     886406953~-~886403962   comp.sys.ibm.pc.games.flight-sim/52150
<34cd5ecb.20149236@nntp.best.com>       886406953~-~885929344   rec.arts.sf.tv.babylon5.moderated/10108
<34d4eeb3.2546651@news.txdirect.net>    886406953~-~886370114   rec.backcountry/9841
  886406954~-~885923414   misc.fitness.weights/21696
<6b3s8r$dp0@sjx-ixn5.ix.netcom.com>     886406954~-~886404085   comp.sys.ibm.pc.games.flight-sim/52151
#gama[lib-news] 114# ls -l history*
-rw-rw-r--   1 news     110490739 Feb  2 17:09 history
-rw-rw-r--   1 news          122 Feb  2 17:14 history.dir
-rw-rw-r--   1 news      8294372 Feb  2 17:09 history.pag
#gama[lib-news] 115#
同じ記事を送ろうとしたとき。 An server tries to send a duplicate article.
maple% telnet gama.is.tsukuba.ac.jp nntp[←]
Trying 130.158.80.241 ...
Connected to gama.is.tsukuba.ac.jp.
Escape character is '^]'.
200 gama.is.tsukuba.ac.jp InterNetNews server INN 1.5.1sec2 25-Jul-1997 ready
Trying 130.158.80.241 ...
Connected to gama.is.tsukuba.ac.jp.
Escape character is '^]'.
200 gama.is.tsukuba.ac.jp InterNetNews server INN 1.5.1sec2 25-Jul-1997 ready
IHAVE  <YAS.98Feb2175819@is.tsukuba.ac.jp>
435 Duplicate
QUIT[←]
205 .
Connection closed by foreign host.
maple% []

◆記事の重複への対応(2)/Dealing with duplicate articles (2)

「Path:」の利用

図? A!B!C!D!E!Fのつながり。冗長リンクを含む。

図? 冗長リンクを含むニュースの配送/ Network news transfer with redundant links

Aで投稿された記事が、B,C,Dを通って E までやってきた時には、Path: には、通ってきたニュースのサイトの名前が入る。

Path: E!D!C!B!A!username
サイト E のサーバは、この記事は サイト A を通ったと判断し、その記事を サイト A には送らない。

実際の Path: の例。

Path: orchid-news.coins.tsukuba.ac.jp!gama.is.tsukuba.ac.jp!
nadesico.cc.tsukuba.ac.jp!news-sv.sinet!newsfeed.mesh.ad.jp!
newsgate1.web.ad.jp!news501.nifty.com!not-for-mail

◆コントロール・メッセージ(Control Message)

Path: gama.is.tsukuba.ac.jp!is.tsukuba.ac.jp!hagi!ume!igakukei!news.cs.ritsumei.ac.jp!kuis-news!kuee-news!tamaru-news!Q.T.Honey!news.hbl.or.jp!news.ksi.co.jp!spinosk!threeWeb-news!nf2.iij.ad.jp!nr0.iij.ad.jp!news.iij.ad.jp!newsgw.yokohama.tao.or.jp!news.yokohama.tao.or.jp!citron!miyano
From: fj-committee@cow.nara.sharp.co.jp
Newsgroups: fj.rec.trading-cards
Subject: cmsg newgroup fj.rec.trading-cards
Control: newgroup fj.rec.trading-cards
Date: 12 Jan 1998 23:53:28 GMT
Message-ID: <newgroup.fj.rec.trading-cards.19980113@cow.nara.sharp.co.jp>

For your newsgroups file:
fj.rec.trading-cards	Topics and discussions on trading-cards

◆よく使われるコントロール・メッセージの種類/ Popular control message types

名前説明
cancel <message-id> 記事のキャンセル
newgrop groupname [moderated] ニュース・グループの作成
rmgroup groupname ニュース・グループの削除
checkgroups activeファイルの確認
ihave systemname 送りたい記事のリスト
sendme systemname 送って欲しい記事のリスト
sendsys sysファイルの転送要求
version ニュース・システムのバージョンの転送

ihave/sendme は、UUCP で冗長リンクを作る時に使う。

◆問題点/Problems

初期のニュース・システムは、権限のない制御メッセージに弱かった。 Early news sytems were vulnerable to attacks by unauthorized control messages.

◆ディジタル署名/Digital signature

送られてきたメッセージが送信者本人のものであることを識別・確認する。

◆ディジタル署名つきのコントロール・メッセージ/A control message with a digital signature

Path: bounce-back
From: committee@fj-news.org (Fj Newsgroups Management Committee)
Newsgroups: fj.comp.dev.pc-card
Subject: cmsg newgroup fj.comp.dev.pc-card
Control: newgroup fj.comp.dev.pc-card
Approved: yas@is.tsukuba.ac.jp
Message-ID: <newgroup.fj.comp.dev.pc-card.19990112@fj-news.org>
Date: Tue, 12 Jan 1999 07:12:37 -0000
Lines: 26
X-Info: ftp://ftp.isc.org/pub/pgpcontrol/README.html
	ftp://ftp.isc.org/pub/pgpcontrol/README
X-PGP-Sig: 2.6.3ia Subject,Control,Message-ID,Date,From,Sender
	iQCVAwUBNpr16hf4TH9gf12pAQHabwP/SLnIuV26QMrAB6EdSahCzHniDvlmwjWB
	EXbPine+y0zcoSWYtj0h1ZBuY9HTV8h/Y3WMGEbsZ7UTDrK8HKYh3agEB1ZRQEe8
	jY3Ya1WCTk8ht7WGqf6mfihJB9pyXy2tkTLjaJ3CwjyQ/OGx+Ogo+4kr1oZeJ/Vt
	pC9OH+/G0CI=
	=KxP+

For your newsgroups file:
fj.comp.dev.pc-card	Discussion on PC Card(JEIDA/PCMCIA Card).

◆共通科目「情報処理」インターネットの仕組み(2005年度)/ネットワーク・ニュースに関する資料

◆ニュースシステムの分散アルゴリズム/The distributed algorithm of news systems

各ノードは、次のデータを持つ。 定期的に次のことを行なう。 ローカルの利用者から記事を受け取った時
  1. ローカルのスプールに記事を保存する。
  2. 履歴に Message-ID を保存する。
  3. sysファイルと記事の Path: や Newsgroups: を参照して、隣接するノードに送る。
隣接するノードから NNTP ihave で記事を提示された時
  1. 履歴にあれば、受け取りを拒む。
  2. 履歴になければ、記事を受け取る。
  3. 記事の日付が履歴の保存期間より古ければ捨てる。
  4. 以後、ローカルの利用者から記事を受け取った時と同じ。
隣接するノードから UUCP で ihave コントロール・メッセージを受け取った時
  1. 履歴にないメッセージのみを選び、sendme コントロール・メッセージを、その隣接ノードに送る。
隣接するノードから UUCP で sendme コントロール・メッセージを受け取った時
  1. その隣接ノードに指定された記事本体を送る。

◆ニュースシステムのまとめ/Conclusion of news systems

ニュース・システムに見られる分散システム構築の技術 Techniques for building distributed systems used in news systems.

◆マルチキャストの一実装としてのネットワーク・ニュースの性質/ Features of news systems as an implementation of multicast

■その他のマルチキャストの事例/ Other examples of multicast

携帯電話アリア同報/ Cellphone Area Broadcast

無線通信を使ったマルチキャスト。 特定の基地局にいる全ノードにメッセージが届く。 購読不要(no subscribing is required)。高いスケーラビリティ。

Ethereum Whisper

ブロックチェーン技術 Ethereum で使われる、一時的(transient)なメッセージ 送受信技術。 API
shh.post({
    optionally "from": owned public key,
    optionally "to": public key,
    "topics": [..., ...],
    "payload": ...,
    "ttl", integer,
    "priority": integer
});

var w = shh.watch({
    optionally "to": owned public key,
    "topics": [..., ...],
});
w.arrived(function(m)
{
    ... m.payload ...
});

参考:

■練習問題(exercise)6 マルチキャスト、ISIS、IPマルチキャスト、ニュース・システム/Multicast, ISIS, IP multicast, News system

★問題(601) マルチキャストの実装としてのメーリングリスト/Mailing list as a multicast implementation

メーリングリストをマルチキャストの実装として考えた時、どのような性質があるかを考えなさい。 各項目で、2つの選択肢から1つを選びなさい。 (二択問題が3つあります。)

Consider the features of the mailing service as an implementation of mulicast. Choose one of two selections in each item. (There are three items. Each item has two choices.)

★問題(602) ISIS

マルチキャストの実装という観点でメーリングリストと比較して ISIS CBCAST(causal multicast) の重要な優位性を1つ選び、簡単に説明しなさい。

Choose an important advantage of ISIS CBCAST(causal multicast) over mailing lists in terms of implications of multicast. Describe this important advantage briefly.

★問題(603) ニュースシステムの記事転送(1)/ Transfering articles in the News System (1)

ネットニュースのサーバ A, B, C, D が以下の図のように接続され、記事を 交換したいとする。個々のサーバは、記事本体と記事の Message-ID を保持し た履歴ファイルを持ち、その初期値が以下のようになっていたとする。

Consider that four servers of the News System, A, B, C, and D are connected as in the following figure, and they exchange news articles. At the first time, each server has articles and the history file that contains the message IDs of the articles as shown in this figure.

図? A!B!C!Dのつながり。冗長リンクを含む。

図? ネットワーク・ニュースのサーバの接続例

サーバ A が、自分が持つている記事のうち、次の記事をサーバ B に送ろうと したとする。 Server A tries to send the following article to Server B. サーバ B の動作を答えなさい。 Describe the actions of Server B.

その記事の日付は、転送する範囲に含まれており、記事はヘッダに "Path A!user" を含むものとする。 Note that the date of the article is good for transfer and the article has "Path: A!user" in the header.

★問題(604) ニュース・システムの記事転送(2)/ Transfering articles in the News System (2)

問題(603) で、 サーバ A が、自分が持つている記事のうち、次の記事をサーバ B に送ろうとしたとする。 In Question (603), Server A tries to send the following article to Server B. サーバ B の動作を答えなさい。 Describe the actions of Server B.

その記事の日付は、転送する範囲に含まれており、記事はヘッダに "Path A!user" を含むものとする。 Note that the date of the article is good for transfer and the article has "Path: A!user" in the header.


Last updated: 2023/05/26 08:09:57
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>