ニュース・システム、ＮＴＰ

情報学類 分散システム					2009年02月03日

                                       筑波大学システム情報工学研究科
                                       コンピュータサイエンス専攻, 電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

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

■ニュース・システムの仕組み

◆ネットワーク・ニュース

ある個人が作成した１つのメッセージ（記事）を大勢の人が読む仕組
１対ｎの通信（放送、マルチキャスト、グループ通信）。
膨大な数の記事をニュース・グループに分類して保存

編集でカットされない、誰でもメッセージを発信できるという意味では、ｎ対ｎの通信。

◆ニュースシステムの設計目標

(中央のサーバなしに)仮想的に集中化されたメッセージの共有空間を作る。
投稿された記事を世界中のニュース・サーバにコピーする（マルチキャスト、グループ通信）
冗長性でサーバや通信回線の「部分的な故障」に対応する。
単一障害箇所(single point of failure)がない。
利用者の数が増えても対応できる（高いスケーラビリティ）。
構成の変化に局所的に対応できる。

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

表? NNTPのコマンド

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

表? NNTPの応答

応答コード説明

100 ヘルプのテキストが続く。

200 要求受け付け可能である（投稿可）。

201 要求受け付け可能である（投稿不可）。　

205 通信路を切断する。

211 ニュース・グループが選ばれた。記事の数、記事番号の上限、下限、ニュース・グループ名。

235 記事の転送は成功した。

335 記事を送れ。最後は、CR-LF . CR-LF 。

400 サービスを中断する。

411 そのようなニュース・グループがない。

421 もうそのニュース・グループには次の記事がない。

435 その記事は欲しくない。(もう既に受け取っている)

436 転送に失敗した。後でもう一度転送しB$iて欲しい。

437 転送に失敗した。もう転送するな。

500 コマンドが認識できなった。

501 コマンドの文法に誤りがあった。

502 アクセスが制限されている。

応答コード	説明
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により接続を試みている。続く３行は、telnet コマンドによる定型的な表示である。通信路が開設されると、サーバは、"200" という応答を返している。これは、NNTP で定義されている応答であり、サーバが、要求を受け付け可能であり、かつ、要求としては投稿要求（POST）も受け付けることを意味している。"200" 以降の文字列は、コメントである。

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

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

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

参考

◆INN newsfeed

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%

◆故障への対応

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

転送できなかった記事のリストを保存する。
冗長のリンクを持つ
- 各サーバは複数のサーバと記事を交換する。
- １ヵ所でも生きていれば記事は落ちない

冗長リンクを持つと、同じ記事が複数の隣接するサーバから送られて来る。

◆冗長のリンク

図? 冗長リンクを含むニュースの配送

◆記事の重複への対応(1)

履歴を利用する。

受け取った記事の Message-ID: を保存する。これを、履歴(history) という。
記事を受け取るたびに履歴をしらべ、履歴にあれば捨てる。
履歴は、メッセージがループする可能性がある時間より長く保存する。
古すぎる記事は、捨てる。

#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#

同じ記事を送ろうとしたとき。

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)

Path: の利用

受け取った記事の Path: に自分の名前を追加する。
Path: に隣のサーバの名前がない時だけ送る。

図? 冗長リンクを含むニュースの配送

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)

普通の記事と同じ仕組みで配送される
ニュースグループの作成削除、記事のキャンセルを行うための特殊な記事
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	ニュース・システムのバージョンの転送

◆問題点

ニュース・システムは、権限のない制御メッセージに弱かった。

制御メッセージの発信権を管理人へ集中
ディジタル署名

◆ディジタル署名

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

受信側は、送信者が誰であるのかを照会することができる。
送信者は、後でそのメッセージを送ったことを否定できない。
暗号技術を使う

◆ディジタル署名つきのコントロール・メッセージ

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年度)／ネットワーク・ニュースに関する資料

◆まとめ

ニュース・システムに見られる分散システム構築の技術

各サーバは、局所的な情報だけで動作する。全世界で共有する情報はない。
- 利用者数のスケーラビリティ
- 構成の変化
冗長なリンクによる故障への対応
- Message-ID: の履歴
- Path:
セキュリティ
- ディジタル署名

■物理クロック

◆論理クロックと物理クロック

論理クロック: 内部で一貫性がとれていればいい
物理クロック: 実際の時計と大きくずれていてはいけない

◆物理クロック同期の応用

ファイルの最終更新時刻、電子メールの日付を正確にする
キャッシュの一貫性, HTTP if-modified-since
メッセージ配信、ネットワーク・ニュース
認証チケットの時間切れ
トランザクション

◆物理クロックの基準

太陽: 地球の公転、自転は一定ではない。ふらつきがある。だんだん１日が長くなってきている。
原子時計: セシウム１３３が 9,192,631,770 回振動。実際の日とずれる。
UTC (Universal Coordinated Time)。: 閏秒で調整。

◆物理クロックを合わせる方法

GPS の普及で、正確な時刻が簡単に取り出せるようになった。 NTP (Network Time Protocol) がよく使われる。

まず古い方法から。

◆Sun rdate

初期の方法。rdate コマンドで特定のホストに合わせる。

# rdate orchid-nwa 
#

問題点

時間が不連続に飛ぶ
時間が逆行することがある

◆adjtime(2)

Unix のシステムコール。進みすぎたクロックを逆行させて戻す変わりに、ペースを落とす。

int adjtime(const struct timeval *delta, struct timeval *olddelta)

◆Cristianの方法

UTCを持っている時刻サーバに問い合わせる。

T₀: クライアントが要求を送る。
I : サーバ内の割込み処理
T₁: クライアントが応答を送る。

図？　時刻サーバに問い合わせる

単純な方法：クライアントの時刻を、送られた UTC に合わせる。

問題1: 時刻が逆行することがある。adjtime() を使う。
問題2: サーバの割込み処理の時間(I)だけずれてしまう。
問題3: 応答メッセージの転送時間は、0ではない。しかも、変動する。

Cristianの方法は、応答メッセージの遅延時間を測定するものである。転送時間や割込み処理の時間が不明な時には、次の式で転送時間を見積もり、補正する。

遅延を(T₁-T₀)/2 とする。
何回かやって、最小値を調べる。

サーバが１つなら、アルゴリズムとしては問題なし。しかし、次のような問題がある。

サーバが落ちている／ネットワークが落ちている
サーバが狂う

◆The Berkeley Algorithm

マスタとスレーブがある。

マスターを１台選ぶ。
スレーブから情報を定期的に集める。
時計の進み具合いの傾向を調べる。
あまりに大きくずれているものを除外する

単純に平均すると、嘘つきに弱い。実際にクロックが１００倍速く進むシステムがあった。

fault-tolerant average。往復時間の誤差。

◆NTP(The Network Time Protocol)

インターネット上のクライアントに UTC を提供
通信が切れても耐える。冗長性を持たせる。
高いスケーラビリティ。合わせる頻度を調整。
競合に強い。一種の認証技術を含む。

サーバが木構造で構成される。レベルを stratum (ストレータム) と呼ぶ。レベルの値が小さいほど正確。Stratum 1 は、UTC の供給源に直接接続されている。原子時計やGPSなど。

図？　NTP(Network Time Protocol)サーバのレベル(stratum)

同期方法

手続き呼出しモード
対称モード
マルチキャストモード

設定ファイルは、/etc/ntp.conf にある。orchid-nwa とその他のホストの設定が異なる。

Last updated: 2009/02/01 10:54:29

Yasushi Shinjo / <yas@is.tsukuba.ac.jp>

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