Papersの最近のブログ記事

情報処理学会論文誌 Vol.37 No.4 Apr.1996

集合論をベースとし、形式的仕様からプログラムを合理的に導出することを目指した集合論プログラミングという新しいプログラミングパラダイムについて論じてある。
集合論による仕様では、以下のような集合式が許される。

{E(y, x):y∈F(x)|Q(y,x)}

この論文の目的は、Z言語などの仕様記述する言語から、自動的に効率的なプログラムへ変換するための、系統的な変換法を確立することである。
4.2 集合論仕様の等価変換がいまいち理解しきれていない。顔を洗って再度チャレンジしよう。

絶版になったZ言語の日本語版の本を、また読んでみることにしよう。そういえば、挫折したんだった。

IEEE Trans. on Communications, Vol.37 No. 5 MAY 1989

一般的なtopology algorithmはauxiliary infromation(seqnum, age, msg counter, time stamp等)を用いて、最新の情報か、また必ずそれぞれのノードで持つ情報が消されることを保証している。
この論文の手法はこれらのaux infoを全く用いないこと。periodic retransmitもしない。
1. 他のノードからupdate msgを受け取った。 2. リンク状態が変わったことをdetectした、
という二つの反応でupdate packetを投げる。
この方式の利点は、1. seqnumのような複雑な処理をしなくて済む(timer等も含め), 2. correctness proofが簡単になる。

細かいことは追記に。

Proceedings of the Spring 1988 European UNIX Users Group Conference, Apr. 1988
SunOSでの新しいＶＭの実装についての論文。結論としては、性能的なオーバーヘッドは
大きくなかった。このくらいの時期にオブジェクト指向が広まり始めたのか。
大体俺が小学校で鼻水たらさなくなったくらいの時代だ。

★このアーキテクチャが提供する機能
・mapped objectで表現されるアドレススペース
・shared mappingとprivate mapping(copy-on-write)のサポート
・large/sparse address spaceのサポート
・page level mapping control

★基本的な抽象化
・page構造体: virtual addressへのオブジェクトのマッピングはpage-levelで行われる。
物理メモリは、memory objectのキャッシュとして利用される。この構造体は、VM system
とobject managerがこのキャッシュを管理する上で必要となる情報を保持する。
・address space: 順序付けられたmappingのlinked-listで構成される。
・segment: 何かしらのentity上の連続(隣接)したmappingを示す。segmentは、異なる種類
のエンティティをmapできる。上位からは種類に透過的にsegmentを扱うことができる。
segment driverがsegmentの種類の違いを吸収する。
・hardware address translation(hat): machine dependent code. MMU内のページへの変換を管理

UNIX Internalsは、これを説明してるのだが、図14.3の全体図は理解不能。
あと基本的な抽象概念のところでanon構造体を紹介しているのが混乱のもとだな。
これは全体像をつかむには必要の無いもの。

Proceedings of the Summer 1987 USENIX Technical Conference, Jun, 1987, pp.81-94
UNIX Internalsの解説があいまいなのでreferされた論文読んだ。
やはり、VM周りはカーネルの構造を知る上での、一つの大きな山場だろう。関わる要素が
多いし、HWと密接に関わるので分かりにくい。

この論文ではSunOS4.0でサポートされた新しいVMアーキテクチャについて説明されている。
それまで(SunOS2,3)は、4.2BSDベースのVMを採用していたが、移植性や機能不足といった
問題があった。特に4.2BSDでは、VAXをターゲットとしており、他のプラットホームに
移植する場合は、VAXのメモリ・アーキテクチャをソフトウェアでエミュレートしていたし、
mapped-file I/Oもサポートされていなかった。

この論文のアーキテクチャでは、メモリ・ハンドリングの統一化、多くの機能をユーザランド
で実装可能(SYSV shared memoryとか)、移植性の向上、UNIX環境との整合性などを
達成した。

この論文のアーキテクチャは、後にSVR4に統合され、様々なシステムに影響を与えている。
そのうち暇があったらNetBSDで使われているUVM1999の論文でも読むか。

Infocom99の論文。さすがにちょっと古い。後、Distance Vector/Link-stateとしか
比較してないのだが、これらが役に立つのはEGPの世界なのでは、と思わせる。

基本的には、輻輳しているリンクを回避するように経路制御を行わせるアルゴリズムに
ついて書いてあるのだが、重要なアスペクトとして、

almost 90% of all Internet traffic is destined to 10% of　the networks, and the top 1% destinations receive　more than 50% of all network traffic, both in bytes and packets.

つまりこれらの"hot" destinationへのトラフィックだけを、違う経路に通してやれば、
輻輳は軽減するだろうという発想。選択的に特定の経路だけをいじるのがアイデア。

Stanfordの人の論文。ACM SIGCOMM CCR 2003.
とりあえず、この論文の内容の覚書。
基本的には、Stanfordで行われているTRIADという新しいインターネット・アーキテクチャの
研究の一環として、"Wide-area Relay Addressing Protocol(WRAP) Packet Delivery"ってのが
あって、そいつのルーティングに関して書いてあるのだが。。。

主張はBGPは以下の理由でだめだ。
　　1. 一つのルータによる攻撃でやられる。弱い。
　　2. 将来的にスケーラビリティが心配
　　3. 収束が遅い。(平均3分)
で、解決策としてstructual informationとdynamic informationをわけたんだそうだ。
structual informationとはリンク・ステートのこと。dynamic informationとは経路情報の
こと。

このルーティングの方式の特徴は、
　　1. ASレベルのリンク・ステート型経路制御でASNでソースルーティングを行う。
　　2. 各PeeringがEdge(Link)とみなされ、そのEdgeに付随する属性としては以下の3種類
　　のルールセットであり、src/dstアドレスのprefix matchを行う。
　　　　1. positive rule set: これに引っかからないと、そのdstはその先にない
　　　　2. negative rule set: これに引っかかると、そのdstにはこのEdgeを使っていけない
　　　　3. traffic enginnering rule set: こいつはAccess Routerがみて、送ったり送らなかったりする。
　　3. エンドASはボーダーにAccess Router, Transit ASはTransit Routerをおく。
　　4. エンドAS内部では普通にInterior Routingされて、Access Routerへ。
　　5. Access Routerはpropagateされた情報を元に、そのdstへのAS Pathを考える。で、
　　IP headerと上位プロトコルの間にAS Listを入れたshim headerをはさんで送る。

みたいな感じ。で、途中のルータがそれを見て送るわけだが、dst側で受け取るときは
A-B-CみたいなAS Listで来た場合は、C-B-Aという風に帰りの順序を知ることができる
（ようだ。Homepageの情報によると。。。)

で、本質的なアルゴリズムは、
1. structual information propagation
2. route quality monitoring
3. measurement based routing preference
であり、access routerは広告された全てnetwork prefixに対して2つの経路を考える。
そして、それぞれのqualityを調べて、いいほうを使う。

本音は、追記に書くとするか。

情報処理学会論文誌2003年10月号 Vol.44 No.10 p.2437--2443

概要としては、Peerが頻繁に離脱・再参加するP2P技術を用いたデータ共有システムに
おいて、ある暗号化されたデータを復号できるPeerが、その権限を他のPeerに時間制限
などを設けて、委譲する方法について述べられている。これを実現するために
「変換サーバ」と呼ばれる第三者機関を利用している。

この論文では変換サーバが完全に信頼できる場合の基本方式、単一の変換サーバでは
信頼できない場合の拡張方式の二つが記述されている。
基本的には、ElGamal暗号を用いて、差をうまく利用している。
拡張方式はいまいち理解し切れてない。

送信者、受信者が同一である4.4暗号化データのアクセス制御以外、
あんまりいい使い道も思い浮かばない。

久しぶりに論文読んだ。CMUの人がSIGCOMM 2001で発表した
"Topology Discovery for Large Ethernet Networks"。
Remos systemの一環。実装などはここからゲットできる。

概要としては、Ethernetのトポロジをどうやって把握するかということ。
これまでは、ネットワーク全体のEthernet bridgeのテーブルを、ほとんどのノードが
テーブルに載っている状態で取得する必要があったが、この論文に書いてある方法を
用いると、partial setでもok。

main contributionはINFOCOM2000 "Topology discovery in heterogeneous IP Networks"で
示されているDirect Connection TheoremとShared Segment Theoremから、
Simple Connection Theorem(直接はつながっていないかもしれないがそっち側の何ホップ
か先につながっていること)とこの定理を使うための３つの最小要件: Minimum Knowledge
requirementを導いたこと。
Minimum Knowledge Requirementが分かりづらいな。

とりあえず、詳しくは追記に書く。