並行システム
システム情報系/情報工学域,
システム情報工学研究群/情報理工学位プログラム
システム情報工学研究科/コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2021/2021-05-21
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
- 分散アルゴリズム distributed algorithms
- マルチキャスト multicast
- 出版・購読モデル
- 事例
- メーリングリスト
- ISIS CBCAST
- IPマルチキャスト IP multicast
- ネットワーク・ニュース network news(Usenet)
- 冗長リンク redundant links
- 履歴 histroy
- Path:
- UUCP
（集中）システムで問題を解くための指令の集まり。
要素間のメッセージの伝達の方法の集まり
Message exchanges among nodes
- どのコンピュータもシステム全体の状態(global state)に関して完全な情報(complete information)を持たない。
- コンピュータは、ローカルな情報(local information)だけで決定する。
- １台のコンピュータが故障しても、全体が破滅しない。
singlepoint of failure を回避したい。
- (グローバルな時計が存在しない/ No global clocks)
時計を使うアルゴリズムもある。
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.
- 電話で放送 Broadcast with telephone
- 電話で多数決 Voting with telephone
- 時計を合わせる Synchronize clocks
- 日本の戸籍、住民登録 Census register and resident registration of Japan
- 筑波大学安否確認アルゴリズム Safety confirmation system in University of Tsukuba
5月22日の資料参照。
２つの重要なパタン two important patterns
- クライアント・サーバ client-server
- グループ通信(マルチキャスト) group communication (multicasting)
- Andrew S. Tannenbaum: "Distributed Operating Systems", Prentice-Hall
(1995). Section 2.5 Group Communication
- one-to-one, point-to-point, unicast
- one-to-many, multicast
図? 1対1の通信の繰り返し / by releated unicast send()
図? 1対多の通信/ by single multicast send()
マルチキャストなら、あるプロセスが１回 send() すると、同じメッセージが
複数のプロセスに届けられる。send() の宛先のアドレス(destination address)は、1個。
- 放送(broadcast)は、特定の物理的なネットワーク(a physical network)に
属するプロセス「全部(all)」にメッセージを送る。受信するプロセスに受信の
意志を問わずに強制的に送ってしまう（受け取ったプロセスは、受け取ったメッ
セージを処理するか、捨てるかする）。
- マルチキャスト(multicast)は、特定のプロセスにだけ送る。受け取りたい
という意志を示しているプロセスにだけ送る。受け取ったプロセスは、メッセー
ジを処理する。
マルチキャストは、いろいろな分散アルゴリズムでよく使われる。
それが使えれば、非常に便利。しかし、実装が難しい。
何が難しいか
- グループが動的 dynamic
- 新しいグループ new groups
- 新しいメンバ new members
- 使えるハードウェア。
下のネットワークで放送やマルチキャストがサポートされているか。
なければ、unicast で実現される。
- バッファリング(buffering)。再送(retransmission)のためのコピーをいつまで持つか。
- 原子性(atomicity)。all or nothing。
全プロセスに送り届けるか、全プロセスに届かないかどちらかにしたい。
望ましい性質だが、非常に難しい。
- メッセージの順番(order of messages)。複数のプロセスが「同時」にメッセージを送信したら、
どのような順番で届くのか。通信システムが保証できるのか。
- open/closed。グループ外から送れればopen。
- peer group or hierarchical group。全プロセスは同等か/階層的(hierarchical)（親子関係、木構造(tree)的になっているか、コーディネータがいるか(with a coordinator)）
並列処理では、closedが多い。
IPマルチキャスト のように、オープンでないとどうしようもないものもある。
対等だと、クラッシュに強い（single point of failure がない）が、何をす
るにもすぐ投票が必要になる。
グループサーバを持つか持たないか。
難しいのは、メンバのプロセスがクラッシュした時。
何も言わずにグループから抜ける。
- プロセスの名前付けと同じように、１つのアドレスで指定する（直接、間接）
- 個々のアドレスのリスト(list)を使う。メンバの管理を呼出し側でやる。
- 述語アドレス指定(predicate addressing)。全部に送られるが、メッセージに含まれている述語が真の時だけ受け取られる。
one-to-oneの通信と同じにしたい。しかし、次のような事が難しい。
- RPC の意味。SunRPC の放送型RPC。
- atomicity
- メッセージの順番 Message ordering
障害がなければ、それほど難しくはない。
障害を扱おうとすると、非常に難しい。
- 送信プロセスが、下位層の放送機能などを使って
グループ内のプロセスに
メッセージを送る。（メッセージは落ちるかもしれない。）
タイマを設定し、必要に応じて再送する。
- 各プロセスは、メッセージを受け取ると、始めて受け取ったものならば、
グループの他のプロセスに送る。タイマを設定し、必要に応じて再送する。
一度受け取ったものなら、なにもしない。
最終的にそのうちに(eventually)、全プロセスに必ずメッセージが届く。
図? 簡単なatomic broadcastのアルゴリズム
one-to-one でも問題があるのに、group 通信だとさらに複雑。
total ordering は、グループ通信では実現が難しすぎる。弱いものが実現さ
れる。
プロセスが複数のグループに属していると、１つのメッセージについての順序
だけ考えていてはすまなくなる。
ノード数が増えた時に動くか。
障害に備えて、複数の機器、複数のネットワーク・リンクを用意する。
冗長性があると、メッセージの重複をうまく扱う必要がでてくる。
下手をすると、メッセージが増幅しながいつまでもぐるぐる回る。
集中システムでは、あるプロセスが共有メモリ(shared memory) や共有ファイ
ル(shared files)に書いて、他のプロセスが読むということで、用が足りるこ
とも多い。
「データが更新された」というイベントを、複数のプロセスにきちんと送り届
けようとすると、分散システムのマルチキャストと同じ話になる。
Unix の signal は、ハードウェアの割り込みと同様に、落ちることがある。
- 送信者は、メッセージを出版(publish)する。
- 受信者は、自分が欲しいメッセージを指定して購読(subscribe)する。
１つのメッセージを複数の受信者が受信することもある。
送信者と受信者の関係が粗結合(loosely coupled)。
粗結合は、分散システムの構築技法では良いこと。
送信者と受信者を仲介するプログラム、ブローカ(broker)と呼ばれるサーバを
使って実装することが多い。
- 送信者は、メッセージをブローカに送信する(publish)。
- 受信者は、自分が欲しいメッセージをブローカに伝える(subsribe)。
- ブローカは、送信者からメッセージを受信すると、
メッセージと受信者のマッチングを行う。
- ブローカは、マッチした受信者に、通知を行う(notification)。
- 受信者は、通知が届けば、ブローカにメッセージの受信を要求して受信する。
メッセージが小さければ、通知の中にメッセージを含めることもできる。
図? 出版・購読モデルによるメッセージの受け渡し
LAN等でマルチキャストが使えれば、マルチキャストで実装することもできる。
ブローカは存在しない。
図? ブロードキャストによる出版・購読モデルの実装
メーリング・リストも、マルチキャストの一実装と考えることもできる。
- one-to-one: 普通のメール
- one-to-many: メーリング・リスト(アドレスを並べるのではない)
図? マルチキャストとしてのメーリング・リスト/a mailing list as an implementation of multicast$
- メンバシップの管理は、コーディネータに集中。
- 運営方針としては、open/closed/moderated 等がある。
open なら、誰でも投げられる。closed ならメンバだけ。
moderated なら、特定の人だけ。
- メッセージの到達の保証はない。(one-to-oneのメールでもない。) ただし、
個々のリンクで、受信側のサーバが落ちていた時には定期的に転送を試みる。
- メッセージの順番の保証はない。(one-to-oneのメールでもない。) ただし、
コーディネータに届いた順番を数えてメッセージに付加することはできる。
- １つのサーバに複数の人が受信する時には、本文はネットワーク上で１回
だけしかながれない。サーバに届いた後に、個人のそれぞれのメールボックス
にコピーされる。(宛先のアドレスが長すぎて、UUCPの上限を超えたトラブルがあった。)
- ネストも可能。グループのグループができる。
- 冗長リンクがあると、同じメールが重複して届くことがある。
- ループの検出が弱い。グループにループができると、非常に危険。
- メールの中継回数(Received: 行)に上限が設定されている。
上限に達したら中継しない。
分散アプリケーションのためのツールキット。
コーネル大学。
1983年-1994年。
http://www.cs.cornell.edu/info/projects/isis/
- Kenneth P. Birman and Thomas A. Joseph: "Reliable communication
in the presence of failures", ACM Transactions on Computer Systems
(TOCS), Vol.5, No.1, pp.47-76 (1987).
http://dx.doi.org/10.1145/7351.7478.
- RFC 992,K. P. Birman and T. A. Joseph:
"On Communication Support for Fault Tolerant Process Groups",1986
- Ken Birman, Heesung Sohn: "Hosting Dynamic Data in the Cloud with
Isis2 and the Ida DHT", ACM Conference on Timely Results in Operating
Systems (TRIOS), 15 pages, 2013.
http://dx.doi.org/10.1145/2524211.2524212
- 同期システム(synchronous system)
- イベント(マルチキャスト)の順序が厳密に逐次的に発生する。オーバーラッ
プしない。イベント（マルチキャストを含む）は、完了までの時間は、０秒。
実現不可能。
- 緩やかな同期システム(loosly synchronous system)
- イベントは有限時間で届く。
- 仮想的な同期システム(virtually synchronous system)
- 因果関係が成り立つようにがんばる。（並行なものは、手抜き。）
- ABCAST (atomic multicast)
- 緩やかな同期
- CBCAST (causal multicast)
- 仮想的な同期
- GBCAST (group multicast)
- 仮想的な同期(グループのメンバシップ用)
ABCAST は、２相コミットにより実装。
Phase 1:
- 送信者は、タイムスタンプを含むメッセージを全てのメンバに送る。
- 各メンバは、送信、または、受信したメッセージで最大のものを最初の送信者に送る。
Phase 2:
- 送信者は、全ての返事を受け取ると、最大のものを選び、メンバにコミット・メッセージを送る。コミット・メッセージは、タイムスタンプの順に届けられる。
メッセージを送ったのに、あるプロセスから返事がこないことがある。その時
は、コミット・メッセージではなくて、アボート・メッセージを送る。メッセー
ジは、送られなかったことにする。
CBCASTの実現
メンバの数：ｎ
各プロセスは、グループごとに、長さｎのベクトルＶを持つ。
ｉ番目の要素は、プロセスｉから正しい順序で受信したメッセージの最後の番号。
０に初期化される。
- プロセスは、送信すべきメッセージがあると、
ベクトルの自分のスロットを増加させ、メッセージの一部として送信する。
- メッセージのベクトルをＶ、メモリ中のベクトルをＬとする。
メッセージがｊから送られてきたものとすると、次の条件の時に受け取る。
そうでないものは、この条件が満たされるまでバッファリングされる。
図? ISISでのCBCASTの実現/ Implementation of ISIS CBCAST.
送信者が１人で、受信者が複数のメッセージをIP のネットワークで送信するこ
と。UDP(データグラム)のみ。TCP(ストリーム)は対応していない。
動画像や音声など大量のデータを配信する時、複数人で同じデータを受信する
時に、同じメッセージを共有できる。
例：筑波大学で、１００人の人が同じ 1M bps の動画像の「生中継(live)」データを
見る
- 単純な方法:
100人 * 1M bps == 100 M bps のデータが、大学と学外を結ぶ線を流れる。
- IPマルチキャスト: 人数にかかわらず、1M bps のデータが流れる。
IPv4 では、IP マルチキャスト用のアドレス
としてクラス D (224.0.0.0-239.255.255.255) を使う。
IPv6 では、IP マルチキャスト用のアドレスとしてff から始まるもの
(ff00::/8) を使う。
送信側(sender):
- UDP でマルチキャストのアドレスを指定する。
- setsockopt() IP_MULTICAST_TTL/IPV6_JOIN_GROUPを指定して、マルチキャスト
の到達範囲制御できる。
- メッセージの送信には、sendto() 等の unicast と同
じシステム・コールを使う。
受信側(receiver):
- setsockopt() で
IP_ADD_MEMBERSHIP/IPV6_JOIN_GROUP を指定して、受信する意志をルータに伝
える。
- 実際に受信するのは、recvfrom() 等のシステム・コールを使う。
ルータは、そのネットワークに特定のマルチキャスト・アドレスでメッセージ
を受信するプロセスが存在するかどうかを管理する（メンバシップ管理）。他
のルータにも伝える。アドレス毎にマルチキャストのルーティング・テーブル
を維持する。
送信側と受信側の間にあるすべてのルータがマルチキャストに対応していない
と、受信できない。多くの IPv4 ルータは、マルチキャストのオプションを無
効にしている。
ルータは、個々のプロセスにメッセージを届ける時には、ネットワークのブロー
ドキャストが使える場合には使う。たとえば、イーサネットでは、ブロードキャ
ストを使う。
IP MBone は、1990年代に IP Multicast を使った実験的なネットワーク。間に
マルチキャストに対応していないルータがあったとしても、ユニキャストによ
るトンネリング(tunneling by unicast)で接続する。
日本の法律の用語(Japanese law term)。IP マルチキャストを使った、「放送
(broadcasting)」。「放送」とは、テレビやラジオや有線放送など。
今までは、インターネットで「放送」といっても、著作権法上は、「通信」に
分類されており、著作権管理の手間が大きかった。
2006年、著作権法が改定され、「IPマルチキャスト放送」を「放送」として位
置づけられるようになった。
- 同じ IP アドレスを持つサーバを、複数(地理的に分散して)動かす。
- クライアントが要求を送ると、一番良い(近い)サーバに届く。
図? 通常の IP アドレスによるメッセージの送信
図? IP anycast によるメッセージの送信
使われている場所
- DNS root サーバ
- DNS cache サーバ, Cloudflare + APNIC (1.1.1.1),
Google public DNS (8.8.8.8), OpenDNS 等
- Content distribution network (CDN)
特徴
- IP anycast は、マルチキャストではない。送信者と受信者は、 1 対 1 。
- 運用が面倒。トラブルシューティングが難しい。
ネットワーク・ニュース(Network news)、または、
ネットニュース(Netnews)。
英語では、Usenet と呼ぶ人も多い。
- ある個人が作成した１つのメッセージ（記事(article)）を大勢の人が読む仕組
- １対ｎの通信（マルチキャスト、グループ通信）。
one-to-many communication (multicast, group communication)
- 膨大な数の記事をニュース・グループに分類して保存
編集でカットされない、誰でもメッセージを発信できるという意味では、ｎ対
ｎの通信。
ニュース・システムは、ネットワーク・ニュースを実装しているプログラムの集合。
- (中央のサーバなしに)仮想的に集中化されたメッセージの共有空間を作る。
Implement virtually centralized message sharing spaces without centralized servers.
- 投稿された記事を世界中のニュース・サーバにコピーする（マルチキャスト、グループ通信）
Copy a posted article to news servers in the world (multicast, group communication).
- サーバや通信回線の「部分的な故障」に冗長性で対応する。
Realize robustness against partial failures of servers and links by redundancy.
- 単一障害箇所(single point of failure)がない。
Avoid single point of failure.
- 利用者の数が増えても対応できる（高いスケーラビリティ）。
Realize high scalable in terms of number of users.
- 構成の変化に局所的に対応できる。
Deal with configuration changes locally.
P2P (Peer to Peer) で、成功している例。
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)が
維持管理を担当しています。
出所 (題名と日付) を明示する限りにおいて、引用、転載、複製等は、
著作者等に断りなしに、自由におこなって構いません。
文書の一部を他の著作物に流用する等の利用は、完全に自由とします。
-
Newsgroups:
- ニュース・グループ
-
From:
- 差出人の電子メールアドレス
-
Subject:
- 記事の題名（題目、表題）。
-
Date:
- 記事が書かれた日付
-
Message-ID:
- メッセージ識別子。その記事に対して世界中で重複がないように付けられた文字
-
Path:
- 記事が通過したサーバ。
Network News Transfer Protocol (NNTP).
図? ネットニュースの記事の配送の仕組/Article transfer mechanism in Netnews
A server
- 各LANにサーバを置きく。
Each LAN has a server.
- 各サーバは、LAN 内の限られた利用者に記事を提供する。
利用者が増えたら、サーバを追加する。
Each server serves articles to a limited number of users in a LAN.
When the number of users increases, we increase the number of servers.
- サーバは、投稿された記事や隣のサーバから受け取った記事を、隣のサー
バへ転送する。
Each server sends posted articles and received articles to neighbors.
NNTPは、ニュースの記事を受け渡しする形式を決めたもの。
NNTP defines the procedures to exchange articles
- インターネット上のニュース・サーバ間の記事の転送 between two servers on the Internet
- ＬＡＮ上のサーバとニュースリーダの間 between a server and a news reader in a LAN
NNTP(Network News Transfer Protocol) とは、ネットワーク・ニュースの記
事の転送や、記事の読み書きを行うためのプロトコルである。mnews や GNUS
などのネットワーク・ニュースを読み書きするソフトウェアは、クライアント
として NNTP サーバとの間に TCP/IP による通信路を開設する。そして、クラ
イアントは、記事を要求する文字列や、ニュース・グループの一覧を要求する
コマンドをサーバに送る。これに対してサーバは、要求された記事やニュース・
グループの一覧をクライアントに返す。表４に、クライアントからサーバへ送
られるNNTPのコマンド、表５に、サーバからクライアントへ返される応答を示
す。
表? NNTPのコマンド/ commands in NNTP
- GROUP newsgroup
-
ニュース・グループnewsgroupを選択する。結果として、記事の数、記事の番号
の上限と下限が返される。
- ARTICLE num
-
記事番号 num の記事の内容を得る。ニュース・グループが選択されている状態の
時に使える。
- ARTICLE <message-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![[←]](../icons/screen-return.gif)
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.
% ![[]](../icons/screen-cursor.gif)
ここで、強調で示した部分が、キーボードからのタイプである。
この例では、ホスト $NNTPSERVER のポート番号119(nntp)のポート
に、TCP/IPにより接続を試みている。続く３行は、telnet コマンドによる定
型的な表示である。通信路が開設されると、サーバは、"200"
という応答を返している。これは、NNTP で定義されている応答であり、サー
バが、要求を受け付け可能であり、かつ、要求としては投稿要求（POST）も受
け付けることを意味している。"200" 以降の文字列は、コメン
トである。
接続されると、"group" というコマンドをサーバに送っ
ている。これに対して、サーバは、"211" という応答に続けて、
記事の数、記事番号の上限、下限、ニュース・グループ名を送っている。
次に "article" コマンドを送っている。これによ
り記事が転送されている。記事の最後には、"." からなる行が
ある。これが、articleコマンドに対する応答の終
りを示している。
最後に "quit" というコマンドをサーバに送ってい
る。これにたいして、サーバは、205 という応答を返し、続いて TCP/IP の通
信路を切断している。その下の Connection closed... は
telnet コマンドが生成したメッセージである。
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%
TCP/IP が普及する以前は、UUCP (Unix to Unix CoPy) という仕組みで、
ネットワーク・ニュースが配られていた。1990年代前半まで主流。
図? UUCP によるファイルのコピー/Copying a file with UUCP
- Unix コンピュータにダイヤルアップ(dial-up)接続用のシリアルポート
(serial ports)にモデム(modem, modulator-demodulator)を接続する。モデムは、電話回線に接続する。
普通は、人間が必要な時に電話回線経由で接続して、「文字端末」として利用
する(PPP とかSLIPではない)。
- UUCP では、2台の Unix コンピュータが接続する。
片方のコンピュータが定期的にもう一方を呼び出す。
- 接続された2台のコンピュータでは、2つのプロセスが文字だけで通信しあ
い、相互にファイルをコピーする。
- ファイルを受け取ると、いくつかのプログラムを実行する。
- ネットワーク・ニュースの記事を受け取る
- 電子メールを受け取る
- そのコンピュータのユーザのホーム・ディレクトリにファイルをコピーする。
- さらに次のコンピュータにファイルをコピーする。
ファイルのコピーの例(copying a file): uucp command
% uucp file1 host2!host3!host4!~user1/dir1
図? uucp コマンドによるファイルのコピー/Copying a file with the uucp command
メールの送信の例(sending an email): 「!」を含むメールアドレスによるメールの送信
% mail -s "hello" host2!host3!host4!user1
途中のホストは、次にどのホストに転送すれば良いかを知っている。自分とは
無関係のホストのメールを中継することもある。誰が電話代を払うか、そもそ
も(日本では)法律的にそのような中継をしてよいのかが議論があった。
サーバやネットワークが落ちることがある。
核攻撃が無くても落ちる。
- 隣へ転送できなかった記事のリストを保存する。
Make lists of articles to be sent to neighbors.
- 冗長のリンクを持つ。 Have redundant links.
- 各サーバは複数のサーバと記事を交換する。
Each server exchanges articles with multiple servers over multiple links.
- 少なくとも１台のサーバに到達できれば、記事は落ちない。
Articles are not lost if at least one server is reachable.
図? 冗長リンクを含むニュースの配送/ Network news transfer with redundant links
問題: 同じ記事が複数の隣接するサーバから送られて来る。
Duplicate articles are sent from multiple neighbors.
履歴(history)を利用する。
- 受け取った記事の Message-ID: を保存する。これを、履歴(history) という。
The server saves the message-id of an article to a file, called a history file.
- 記事を受け取るたびに履歴をしらべ、履歴にあれば捨てる。
Each time a server receives an article, the server checks if it has received the article.
If the server finds the message-id in the history file, it drops the article.
- 履歴は、メッセージがループする可能性がある時間より長く保存する。
Each server keeps the history file longer than the period that aricles can loop.
- 古すぎる記事は、捨てる。(ループしている可能性があるので捨てる。)
Each server drops old articles.
履歴の例 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%
「Path:」の利用
- 受け取った記事の Path: に自分の名前を先頭に追加する。
When a server receives an artilce,
it perpends the host name to the Path header of the article.
- Path: に隣のサーバの名前がない時だけ送る。
A server sends an article when the name of the next server is not included in the Path header.
図? 冗長リンクを含むニュースの配送/ 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 という名前の特殊なニュース・グループにある。
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
| 名前 | 説明 |
|---|
| cancel <message-id> | 記事のキャンセル |
| newgrop groupname [moderated] | ニュース・グループの作成 |
| rmgroup groupname | ニュース・グループの削除 |
| checkgroups | activeファイルの確認 |
| ihave systemname | 送りたい記事のリスト |
| sendme systemname | 送って欲しい記事のリスト |
| sendsys | sysファイルの転送要求 |
| version | ニュース・システムのバージョンの転送 |
ihave/sendme は、UUCP で冗長リンクを作る時に使う。
- 主リンクでは、記事本体をすぐに送る。
- 副リンク(主リンク以外)では、 Message-ID: だけを含む
ihave コントロール・メッセージとしてを作成して送る。
記事本体は送らない。電話代の節約になる。
- 隣接ノードから ihave コントロール・メッセージを受け取ると、自分が持っていない記事のリストを
sendme コントロール・メッセージを作成して、隣接ノードに送り返す。
(主リンクで記事が失われたとみなす。)
- sendme コントロール・メッセージを受け取ると、記事本体を送る。
初期のニュース・システムは、権限のない制御メッセージに弱かった。
Early news sytems were vulnerable to attacks by unauthorized control messages.
- ニュースグループ管理のためのコントロール・メッセージの発信権を管理人へ集中
- ディジタル署名を使う
送られてきたメッセージが送信者本人のものであることを識別・確認する。
- 受信側は、送信者が誰であるのかを照会することができる。
- 送信者は、後でそのメッセージを送ったことを否定できない。
- 暗号技術を使う
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).
各ノードは、次のデータを持つ。
定期的に次のことを行なう。
- スプールから保存期間が過ぎたある記事を削除する。
- 履歴から保存期間が過ぎたMessage-ID: を削除する。
履歴の保存期間は、記事の保存期間より長い。
ローカルの利用者から記事を受け取った時
- ローカルのスプールに記事を保存する。
- 履歴に Message-ID を保存する。
- sysファイルと記事の Path: や Newsgroups: を参照して、隣接するノードに送る。
- 隣接ノードがオンラインなら、NNTP ihave で提示する。
- 隣接ノードがオフラインなら、Message-ID: をファイルに保存し、後で転送を試みる。
- UUCP の主リンクなら、UUCP で記事本体を送る。
- UUCP の副リンクなら ihave コントロール・メッセージを作成する。
隣接するノードから NNTP ihave で記事を提示された時
- 履歴にあれば、受け取りを拒む。
- 履歴になければ、記事を受け取る。
- 記事の日付が履歴の保存期間より古ければ捨てる。
- 以後、ローカルの利用者から記事を受け取った時と同じ。
隣接するノードから UUCP で ihave コントロール・メッセージを受け取った時
- 履歴にないメッセージのみを選び、sendme コントロール・メッセージを、その隣接ノードに送る。
隣接するノードから UUCP で sendme コントロール・メッセージを受け取った時
- その隣接ノードに指定された記事本体を送る。
ニュース・システムに見られる分散システム構築の技術
Techniques for building distributed systems used in news systems.
- 各サーバは、局所的な情報だけで動作する。全世界で共有する情報はない。
Each server runs by using local information.
Complete information on global state is not needed.
- 利用者の数が増えても対応できる（高いスケーラビリティ）。
Realize high scalable in terms of number of users.
- 構成の変化に局所的に対応できる。
Deal with configuration changes locally.
- 冗長なリンクによる故障への対応
Realize robustness against partial failures of servers and links by redundancy.
- Message-ID: の履歴(history)
- Path:
- セキュリティ Security
- ディジタル署名 Digital signature
- atomic ではない。No atomicity.
- 因果律も満たさない。No causality.
- 非常に高いスケーラビリティを持つ。High scalable.
- 冗長性を使っている。Using redundancy.
- 貧弱なネットワーク、UUCP でも動く。Runable in a poor network, such as a UUCP network.
無線通信を使ったマルチキャスト。
特定の基地局にいる全ノードにメッセージが届く。
- 緊急地震速報 Earthquake Early Warning
- 緊急速報、「エリアメール」
購読不要(no subscribing is required)。高いスケーラビリティ。
ブロックチェーン技術 Ethereum で使われる、一時的(transient)なメッセージ
送受信技術。
- メッセージは、暗号化され、P2P ネットワークで配送される。
- メッセージの送信先と送信元を隠そうと思えば隠せる。
- マルチキャストをサポートしている。
送信(post)、受信(watch, subscribe)する時に、アドレスとして、topics が使える。
- topics が隠せる。
データ転送では、topics は、SHA3-256 でハッシュ値が計算され、
その先頭の 4 バイトだけが使われる。
- ユニキャストなら、相手の公開鍵で暗号化できる。
送信の時に、To: を付ける。
送信する時に、ディジタル署名を付けることもできる。
送信の時に、From: を付ける。
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 ...
});
参考:
メーリングリストをマルチキャストの実装として考えた時、どのような性質があるかを考えなさい。
各項目で、2つの選択肢から1つを選びなさい。
(二択問題が4つあります。)
Consider the features of the mailing service as an implementation of mulicast.
Choose one of two selections in each item.
(There are four questions. Each question has two selections.)
- メンバシップの管理において、各メーリングリストは、グループサーバを持つ／待たない。
In membership management, each mailing list has a group server or do not.
- アドレス指定において、各メーリングリストは、１つのアドレスで指定できる／できない。
In addressing, each mailing list can be referred with a single address or cannot.
- メーリングリストは、原子性(atomicity)を提供する／しない。
Mailing list provides atomicity or does not.
- メーリングリストは、メッセージ到着の順番を保存する／しない。
Mailing list preserves the order of message arrivals or does not.
マルチキャストの実装という観点でメーリングリストと比較して
ISIS CBCAST(causal multicast)
の重要な優位性を１つ選び、簡単に説明しなさい。
Choose an important advantage of ISIS CBCAST(causal multicast)
over mailing lists in terms of implications of multicast.
Describe this important advantage briefly.
ニュース・システムは、冗長リンクを利用している。
その理由を説明しなさい。
この冗長リンクは、ある問題を引き起こす。
その問題を説明しなさい。
その問題を解決する方法を示しなさい。
The news system uses redundant links.
Describe its reason.
Using redundant links causes a problem.
Describe the problem.
Show a method that solves the problem.
Last updated: 2021/05/19 18:09:35
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>