吳國福，韓崗，竇文華

（國防科技大學(xué) 計算機學(xué)院，湖南 長沙 410073）

1 引言

P2P系統(tǒng)中 Peer節(jié)點顯示或隱式地形成覆蓋(overlay)網(wǎng)絡(luò)。短路徑優(yōu)先的覆蓋網(wǎng)絡(luò)構(gòu)建策略使邏輯連接盡可能限制在自治域范圍內(nèi)，能有效減少主干網(wǎng)流量，加快信息的傳播速度。短路徑優(yōu)先策略需要獲知節(jié)點之間的網(wǎng)絡(luò)延遲，如果直接測量網(wǎng)絡(luò)延遲，隨著系統(tǒng)規(guī)模的增大，探測報文產(chǎn)生的開銷將遠(yuǎn)大于覆蓋網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化帶來的收益。理想的方案應(yīng)該是低成本、分布式、易擴展的。

網(wǎng)絡(luò)坐標(biāo)系統(tǒng)[1]將網(wǎng)絡(luò)中節(jié)點映射到有限維度度量空間，使用節(jié)點在度量空間的距離估算網(wǎng)絡(luò)延遲。本文提出基于被動路標(biāo)的網(wǎng)絡(luò)距離預(yù)測技術(shù)，利用 Internet上已經(jīng)部署的服務(wù)器對探測報文的響應(yīng)，獲得節(jié)點到路標(biāo)的網(wǎng)絡(luò)延遲，通過Lipschitz[1]變換將節(jié)點網(wǎng)絡(luò)延遲映射到有限維度量空間中的元素，然后使用網(wǎng)絡(luò)距離函數(shù)估算網(wǎng)絡(luò)距離。

網(wǎng)絡(luò)距離預(yù)測技術(shù)以較小的網(wǎng)絡(luò)開銷準(zhǔn)確地估算節(jié)點間的網(wǎng)絡(luò)延遲，新的問題是節(jié)點如何快速定位臨近節(jié)點。一種好的思路是先快速篩選一組可能的臨近節(jié)點，縮小計算范圍；然后從中選擇距離最近的臨近節(jié)點。本文引入空間填充曲線(SFC,space filling curve)[2]技術(shù)并提出基于查表的映射算法完成快速篩選的預(yù)處理工作。

綜合網(wǎng)絡(luò)坐標(biāo)技術(shù)和空間填充曲線技術(shù)，本文提出短路徑優(yōu)先的覆蓋網(wǎng)絡(luò)構(gòu)建策略。通過較小的網(wǎng)絡(luò)開銷和計算代價，節(jié)點獲得臨近節(jié)點的信息并與之建立邏輯連接。短路徑優(yōu)先策略使得邏輯覆蓋網(wǎng)絡(luò)與底層物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)盡可能匹配，有效減少物理鏈路上的重復(fù)報文。實驗結(jié)果表明，本文方法構(gòu)建的覆蓋網(wǎng)絡(luò)具備良好的性能。

文章的后續(xù)組織如下：第2節(jié)介紹相關(guān)工作，第 3節(jié)提出基于被動路標(biāo)的網(wǎng)絡(luò)距離預(yù)測技術(shù)，第4節(jié)提出基于查表的對角線空間填充曲線映射算法，第5節(jié)給出短路徑優(yōu)先的覆蓋網(wǎng)絡(luò)構(gòu)造方法，第6節(jié)實驗驗證本文方案的有效性，第7節(jié)是結(jié)束語。

2 相關(guān)工作

P2P應(yīng)用系統(tǒng)中，消息沿著覆蓋網(wǎng)絡(luò)中繼傳輸，其質(zhì)量對系統(tǒng)性能有重要影響。覆蓋網(wǎng)絡(luò)中一跳對應(yīng)物理網(wǎng)絡(luò)中的一條端到端路徑。邏輯路徑P對應(yīng)的物理路徑集合，稱為實際路徑。以邏輯路徑P的起始節(jié)點開頭，在物理網(wǎng)絡(luò)中遍歷 P上所有 Peer節(jié)點的具有某種最優(yōu)屬性（如最短距離）的路徑P’，稱之為理想路徑（理想路徑可能不只一條）。如果實際路徑中Peer節(jié)點的訪問順序與理想路徑中Peer節(jié)點的訪問順序一致，稱之為路徑完美匹配。如果覆蓋網(wǎng)絡(luò)中所有的邏輯路徑都是路徑完美匹配的，則稱覆蓋網(wǎng)絡(luò)是拓?fù)渫昝榔ヅ涞?。實現(xiàn)拓?fù)渫昝榔ヅ涫抢щy的，實際中學(xué)者一般利用某種網(wǎng)絡(luò)結(jié)構(gòu)信息優(yōu)化覆蓋網(wǎng)絡(luò)，使其與物理網(wǎng)絡(luò)在拓?fù)渖媳M量匹配。實現(xiàn)拓?fù)淦ヅ溆?種策略：一是直接構(gòu)造拓?fù)淦ヅ涞馗采w網(wǎng)絡(luò)；二是動態(tài)優(yōu)化覆蓋網(wǎng)絡(luò)，使其與物理網(wǎng)絡(luò)相匹配。下面介紹相關(guān)文獻(xiàn)中的典型方法。

S.Ratnasamy[3]等提出基于節(jié)點分類的方法構(gòu)建拓?fù)淦ヅ涞母采w網(wǎng)絡(luò)。物理網(wǎng)絡(luò)中距離近的節(jié)點劃為同一類別，稱之為一個bin。分類方法如下：網(wǎng)絡(luò)中部署一組路標(biāo)節(jié)點，節(jié)點測量到各個路標(biāo)節(jié)點的網(wǎng)絡(luò)距離；按照從小到大的順序排列網(wǎng)絡(luò)距離，從而獲得路標(biāo)節(jié)點的序列，將該序列作為節(jié)點的bin。節(jié)點選取鄰居節(jié)點時，首先從同一個bin中選取，數(shù)量不夠時從差別最小的bin中繼續(xù)選取。

Mithos[4]基于網(wǎng)絡(luò)坐標(biāo)系統(tǒng)構(gòu)建連接高效覆蓋網(wǎng)絡(luò)。節(jié)點加入系統(tǒng)時根據(jù)初始鄰近節(jié)點的網(wǎng)絡(luò)坐標(biāo)計算自身網(wǎng)絡(luò)坐標(biāo)；節(jié)點以自身為中心在每個象限內(nèi)尋找最近節(jié)點與之建立鄰居關(guān)系。該方案初始加入過程冗長，節(jié)點需要經(jīng)過多次迭代才能在系統(tǒng)中找到臨近節(jié)點；節(jié)點坐標(biāo)一旦確定后不再變化，這與P2P系統(tǒng)的動態(tài)特性不相適應(yīng)。

Zhichen Xu[5]等結(jié)合基于路標(biāo)的分類技術(shù)和小范圍直接測量技術(shù)選擇鄰近節(jié)點。使用基于路標(biāo)的分類技術(shù)選擇與自身類別相同或相似的部分節(jié)點，然后直接測量網(wǎng)絡(luò)距離以選取最近的節(jié)點。系統(tǒng)將節(jié)點到路標(biāo)的網(wǎng)絡(luò)距離信息作為系統(tǒng)軟狀態(tài)分布保存在相關(guān)節(jié)點上，其他節(jié)點根據(jù)到路標(biāo)的距離信息查找到相關(guān)節(jié)點獲取同類別或相似類別的節(jié)點信息。

SAT-Match[6]是一種針對結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)CAN[7]的局部優(yōu)化措施。每次迭代由2個階段組成：探測階段和跳轉(zhuǎn)階段。在探測階段，節(jié)點S在限定范圍內(nèi)（比如兩跳內(nèi)）泛洪探測報文，收集限定區(qū)域內(nèi)節(jié)點的IP地址，然后測量網(wǎng)絡(luò)傳輸延時。在跳轉(zhuǎn)階段，判斷是否跳轉(zhuǎn)應(yīng)該對比跳轉(zhuǎn)前后該區(qū)域內(nèi)所有節(jié)點平均邏輯連接長度的變化，如果變小則進(jìn)行跳轉(zhuǎn)。在結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)中節(jié)點狀態(tài)與節(jié)點位置密切相關(guān)，SAT-Match優(yōu)化過程需要大量跳轉(zhuǎn)操作，狀態(tài)遷移和探測報文會給系統(tǒng)代理沉重的負(fù)擔(dān)。

Quasi-Chord[8]直接利用GNP[9]技術(shù)預(yù)測網(wǎng)絡(luò)距離構(gòu)建Chord[10]覆蓋網(wǎng)絡(luò)。首先使用網(wǎng)路距離預(yù)測技術(shù) GNP獲取節(jié)點網(wǎng)絡(luò)坐標(biāo)，然后使用二維卡托空間填充曲線對網(wǎng)絡(luò)坐標(biāo)作映射得到節(jié)點序號，最后使用序號作為標(biāo)識符構(gòu)建環(huán)形覆蓋網(wǎng)絡(luò)。

LTM[11]是一種分布式的基于位置感知局部優(yōu)化技術(shù)，其主要使用2種操作提高拓?fù)淦ヅ涠龋杭糁Σ僮?、加邊操作。剪枝操作主要針對圖1(a)和圖1(b)2種情況，在圖1(a)中，節(jié)點S向外泛洪TTL＝2的探測報文，節(jié)點P接收到節(jié)點S發(fā)送的探測報文和節(jié)點N1轉(zhuǎn)發(fā)的探測報文，計算出連接PS、PN1和SN1的長度LPS、L1PN、L1SN。如果LPS或者L1PN明顯長于其他2條連接，則將其剪除。同樣在圖1(b)中，節(jié)點P獲取L1PN、L2PN、L1SN、L2SN的長度，如果L1PN或者L2PN明顯長于其他3條連接，則將其剪除。加邊操作發(fā)生在圖1(c)的情形，節(jié)點S與節(jié)點P之間沒有直接連接，節(jié)點P接收泛洪報文后主動探測到節(jié)點S的網(wǎng)絡(luò)傳輸延遲LPS，如果LPS明顯長于L1PN、L1SN，則不需添加新邊，否則添加新邊PS。LTM存在一些不足：①需要大量迭代才能取得較好的效果；②節(jié)點要保持時間同步，現(xiàn)有的網(wǎng)絡(luò)時間協(xié)議服務(wù)精度有限，影響優(yōu)化效果。

圖1 LTM中的剪枝、加邊操作

3 基于被動路標(biāo)的網(wǎng)絡(luò)距離預(yù)測

本節(jié)提出一種基于被動路標(biāo)的網(wǎng)絡(luò)距離預(yù)測方法，從而獲得物理網(wǎng)絡(luò)的拓?fù)湫畔⒁灾笇?dǎo)覆蓋網(wǎng)絡(luò)的構(gòu)建。

3.1 網(wǎng)絡(luò)距離預(yù)測方案

在基于網(wǎng)絡(luò)坐標(biāo)系統(tǒng)的網(wǎng)絡(luò)距離預(yù)測方案[1]中，大都引入路標(biāo)節(jié)點。路標(biāo)或者全局固定不變，或者由隨機選擇的普通節(jié)點擔(dān)當(dāng)，2種方法各有缺陷。前者部署成本昂貴，通用性差；后者容易產(chǎn)生誤差積累并且坐標(biāo)易陷于局部最優(yōu)。目前 Internet上存在大量的高性能穩(wěn)定的服務(wù)器節(jié)點，如 DNS服務(wù)器、Web服務(wù)器等，響應(yīng)端節(jié)點的探測報文。如果利用這些節(jié)點充當(dāng)路標(biāo)，既解決路標(biāo)全局不變方案中部署成本昂貴的問題，又解決路標(biāo)隨機選擇方案中的誤差累積和局部性問題。但是這些服務(wù)器節(jié)點只被動響應(yīng)客戶端請求，無法主動對外探測，需要特殊方法利用其路標(biāo)功能。

Internet上的節(jié)點是按一定層次結(jié)構(gòu)組織的，這種結(jié)構(gòu)使得區(qū)域內(nèi)節(jié)點間延遲小，而區(qū)域間節(jié)點間延遲大。網(wǎng)絡(luò)距離近節(jié)點往往處在同一區(qū)域中，到路標(biāo)的網(wǎng)絡(luò)距離較為接近；網(wǎng)絡(luò)距離遠(yuǎn)節(jié)點可能處在不同區(qū)域中，到路標(biāo)的網(wǎng)絡(luò)距離差異較大。直接使用節(jié)點到路標(biāo)的網(wǎng)絡(luò)傳輸延遲作為節(jié)點的網(wǎng)絡(luò)坐標(biāo)，坐標(biāo)值之間的歐式距離能夠反映出節(jié)點的網(wǎng)絡(luò)距離。

鑒于上述認(rèn)識，提出基于被動路標(biāo)的網(wǎng)絡(luò)距離預(yù)測方法（PLNDP, passive-landmark based network distance prediction）。PLNDP整體思路是：在Internet上搜索已經(jīng)部署的高性能服務(wù)器作為路標(biāo)節(jié)點；普通節(jié)點提前獲知路標(biāo)通信地址并測量到各個路標(biāo)的網(wǎng)絡(luò)延遲，使用Lipschitz變換獲取網(wǎng)絡(luò)坐標(biāo)；通過中心服務(wù)器交換網(wǎng)絡(luò)坐標(biāo)，普通節(jié)點使用特定的距離函數(shù)計算網(wǎng)絡(luò)坐標(biāo)在向量空間Rn中的距離，進(jìn)而預(yù)測節(jié)點間的網(wǎng)絡(luò)距離。

3.2 網(wǎng)絡(luò)距離預(yù)測方法執(zhí)行過程

3.2.1 路標(biāo)節(jié)點的選擇

Internet上已經(jīng)部署高性能服務(wù)器節(jié)點大多數(shù)響應(yīng)客戶端的探測報文，端節(jié)點使用ping命令很容易獲得到服務(wù)器的網(wǎng)絡(luò)延遲。選擇哪些服務(wù)器節(jié)點作為路標(biāo)需要解決下面的問題。①路標(biāo)節(jié)點的數(shù)量k，數(shù)量過多產(chǎn)生大量探測報文，同時會提供冗余信息；數(shù)量太少使得預(yù)測結(jié)果偏差過大。實驗結(jié)果表明，數(shù)量在8～10之間就可獲得較高的預(yù)測準(zhǔn)確度?？紤]到路標(biāo)節(jié)點的失效，認(rèn)為路標(biāo)數(shù)量在 12個比較合適。②路標(biāo)節(jié)點的分布區(qū)域，為了發(fā)揮參考作用，路標(biāo)應(yīng)該分布在合理的范圍。其范圍取決于應(yīng)用程序的使用范圍，如果應(yīng)用程序面向整個Internet，則路標(biāo)節(jié)點應(yīng)該分布在全球各個地方；如果應(yīng)用程序是區(qū)域性的，比如面向中國大陸地區(qū)，則路標(biāo)節(jié)點應(yīng)該限制在區(qū)域以內(nèi)。③路標(biāo)節(jié)點的相對位置，距離太近的路標(biāo)提供的信息存在很大的冗余，因此路標(biāo)節(jié)點應(yīng)該盡可能分散。實驗表明隨機選擇即可。本文在應(yīng)用程序使用范圍內(nèi)搜集性能穩(wěn)定的大型服務(wù)器，從中選擇數(shù)量合適、均勻分布的服務(wù)器作為路標(biāo)節(jié)點，其他服務(wù)器留作備份使用。

3.2.2 普通節(jié)點獲取網(wǎng)絡(luò)坐標(biāo)

路標(biāo)節(jié)點的地址和序號提前發(fā)送給普通節(jié)點，普通節(jié)點i發(fā)送echo request 探測報文到所有路標(biāo)節(jié)點，接收到echo replay響應(yīng)報文后計算往返傳輸延遲RTT，則節(jié)點i到對應(yīng)路標(biāo)的網(wǎng)絡(luò)延遲近似為RTT/2。普通節(jié)點可多次測量 RTT，選擇延遲的最小值或者平均值來規(guī)避網(wǎng)絡(luò)暫時擁塞帶來的影響。當(dāng)測得到所有路標(biāo)節(jié)點的網(wǎng)絡(luò)延遲后，普通節(jié)點使用Lipschitz變換獲得自身網(wǎng)絡(luò)坐標(biāo)。失效路標(biāo)節(jié)點對應(yīng)的坐標(biāo)元素值為0。

3.2.3 網(wǎng)絡(luò)距離預(yù)測

普通節(jié)點獲取自身網(wǎng)絡(luò)坐標(biāo)后，向中心服務(wù)器注冊。普通節(jié)點通過中心服務(wù)器或者其他節(jié)點獲取感興趣節(jié)點的網(wǎng)絡(luò)坐標(biāo)，使用距離函數(shù)計算兩者之間的網(wǎng)絡(luò)距離。假設(shè)路標(biāo)節(jié)點的數(shù)量為 n，普通節(jié)點 a、b坐標(biāo)分別為 ( a1, a2,… ,an)、(b1, b2,… ,bn)。原始坐標(biāo)不能直接進(jìn)行距離計算，要對其進(jìn)行兩方面的預(yù)處理。首先去除失效路標(biāo)，失效路標(biāo)對應(yīng)的坐標(biāo)元素值為 0，去除失效路標(biāo)對應(yīng)的坐標(biāo)元素得到新坐標(biāo)。由于路標(biāo)節(jié)點是性能穩(wěn)定的服務(wù)器，失效概率很低，該方法完全可應(yīng)對路標(biāo)失效問題。其次去除冗余路標(biāo)，如果普通節(jié)點a、b到路標(biāo)節(jié)點A、B的網(wǎng)絡(luò)傳輸延時之差相當(dāng)，則認(rèn)為A、B對a、b的參考作用相同，A、B相對于a、b而言是互為冗余的，保留一個即可。將失效路標(biāo)和冗余路標(biāo)對應(yīng)的坐標(biāo)元素去除后，a、b的新坐標(biāo)變?yōu)?a1′ , a2′ ,… ,am′ )、( b1′ , b2′ ,… ,bm′)，m為有效路標(biāo)節(jié)點數(shù)目，則 a、b之間的網(wǎng)絡(luò)距離由下面的距離函數(shù)計算得到：

下面舉例說明PLNDP的具體操作。在圖2所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，選擇節(jié)點 ACDEFH作為路標(biāo)節(jié)點，abc為普通節(jié)點，連接線上的數(shù)字表示節(jié)點間的傳輸延遲。假設(shè)路標(biāo)E對節(jié)點a是失效的，則節(jié)點 a、b、c的坐標(biāo)分別為（3，3，6，0，9，13）、（13，9，6，6，3，3）、（8，6，1，7，4，8）。計算 a、b之間的距離時，剔除失效路標(biāo)得到坐標(biāo)（3，3，6，9，13），（13，9，6，3，3），無冗余路標(biāo)，計算得到Lab=12.78。計算b、c之間的距離時，b、c到路標(biāo)A、D的距離差都是5，所以A、D相互冗余，去掉路標(biāo)D，同樣路標(biāo)E、F也是相互冗余的，去掉路標(biāo)F，得到新坐標(biāo)（13，9，6，3），（8，6，7，8），計算得到Lbc= 6.71。同理可得Lac= 7.7。a、b、c之間的實際距離為Mab=12、Mbc=7、Mac= 7，預(yù)測誤差分別為6.5%、4.1%、10%。預(yù)測距離與實際距離較為接近，該方法具有較高的預(yù)測準(zhǔn)確度。

圖2 隨機連接網(wǎng)絡(luò)

3.3 動態(tài)網(wǎng)絡(luò)環(huán)境下PLNDP的處理

在網(wǎng)絡(luò)環(huán)境動態(tài)變化情況下，將網(wǎng)絡(luò)看作由一系列快照組成，快照持續(xù)時間為τ，在時間τ內(nèi)，網(wǎng)絡(luò)變化可忽略。PLNDP每隔周期 T更新節(jié)點的網(wǎng)絡(luò)坐標(biāo)，如果限制 T＜τ/2，則保證坐標(biāo)測量和預(yù)測在同一網(wǎng)絡(luò)快照內(nèi)完成，仍然可以看作PLDNP在靜態(tài)網(wǎng)絡(luò)中運行。只要合理設(shè)置更新周期T，PLDNP在動態(tài)網(wǎng)絡(luò)中仍保持高的預(yù)測準(zhǔn)確性。

4 基于查表的空間填充曲線快速映射算法

基于被動路標(biāo)的網(wǎng)絡(luò)距離預(yù)測較為準(zhǔn)確地預(yù)測節(jié)點之間的距離信息。當(dāng)節(jié)點需要獲取臨近節(jié)點集合時，最直觀的方法是計算到所有節(jié)點網(wǎng)絡(luò)距離，然后挑選最近的節(jié)點集合。在大規(guī)模分布式系統(tǒng)中，這種方式將導(dǎo)致計算資源緊張。一種有效方法是首先快速篩選出一組粗糙節(jié)點集合，然后通過精確計算確定所需的節(jié)點。本文引入空間填充曲線技術(shù)完成快速篩選工作。本節(jié)主要介紹基于查表的空間填充曲線快速映射算法，快速篩選方案在下一節(jié)給出。

4.1 空間填充曲線介紹

空間填充曲線是數(shù)據(jù)降維處理的典型方法，在多維空間元素映射與整數(shù)之間建立一一映射關(guān)系。皮亞諾[12]首先提出空間填充曲線的概念，給出單位長度到單位正方形的連續(xù)滿射函數(shù)，即皮亞諾曲線。希爾伯特[13]擴展了空間填充曲線的概念，給出單位長度到單位d維立方體映射的幾何構(gòu)造。空間填充曲線一個良好性質(zhì)是映射具有臨近性，即2個元素在D維空間中臨近，像點在數(shù)值上保持接近。圖3給出了幾種典型的2維空間曲線填充示例。

4.2 對角線空間填充曲線

圖3 2維空間填充曲線

已有文獻(xiàn)給出的空間填充曲線映射算法或者局限在二維空間內(nèi)，或者計算較為復(fù)雜。本文給出對角線空間填充曲線的映射算法，計算簡單且容易擴展到高維空間。在下面的描述中假定原始空間的維度為m，每一維度上有個格點，格點的序號從1開始計數(shù)。首先規(guī)定對曲線的訪問規(guī)則，假設(shè)格點C = (c1,c2,…,cm)和 C′=( c1′, c2′,…,cm′)的序號分別為p、q，令則 p＜q當(dāng)且僅當(dāng)下列條件之一成立：① k

4.3 對角線空間填充曲線映射算法

當(dāng)m=2時格點的訪問順序很直觀，求解的方法很多；對于高維空間m＞ 2 中的格點C =( c1, c2,… ,cm)，如果簡單使用遞歸方法求解其計算量隨m和g成指數(shù)規(guī)模增長。下面給出基于查表的空間填充曲線快速映射算法。

首先引入等勢面的概念，等勢面是指坐標(biāo)元素之和相等的所有格點集合，用符號Ek表示，其中下標(biāo) 表示等勢面高度，即格點坐標(biāo)元素之和，顯然k≥ 2 。對于格點令由必要條件知格點 C的順序 SFC_Order(C)決定于Ei中元素的數(shù)量|Ei|(i ＜k)和C在Ek中的順序Ek_Order(C)，即

下面分別介紹Ek中元素數(shù)量|Ek|和C在Ek中順序Ek_Order(C)的計算方法。

本文使用函數(shù) f ( k, g, m) 表示等勢面 Ek中元素的數(shù)量。由于k是格點的坐標(biāo)元素之和，所以k的有效取值范圍是[0,m( g- 1 )]，規(guī)定

當(dāng)m=1時每個等勢面只有一個格點，即

k=0當(dāng)且僅當(dāng)格點坐標(biāo)每個元素值都為 0，也就是說等勢面E0中僅有一個元素，即

等勢面 Ek中格點 C =(c1, c2,…,cm)的坐標(biāo)元素值之和為k，首先考慮cm的取值，當(dāng)cm取0時其他m-1個元素之和必須為 k，即 cm取 0時共有f( k, g, m- 1 )個格點在 Ek中，同理當(dāng) cm取i∈[0,g -1]時，共有f( k -i ,g, m- 1 )個格點在Ek中，因此可得

這樣m維等勢面元素數(shù)量可用多個(m-1)維等勢面元素數(shù)量之和表示。同樣m維高度為k-1的等勢面元素數(shù)量可表示為

式(7)、式(8)相減得到函數(shù) f ( k, g, m )的遞推關(guān)系。

f( k, g, m )- f( k- 1 ,g, m )=f( k- 0 ,g, m- 1)-f( k-1 -g+ 1 ,g, m-1)

即

使用式(3)～式(6)以及式(9)，可依次快速求解各個維度上不同高度的等勢面中含有的元素數(shù)量。

確定格點順序還需要求解格點 C= (c1, c2,…,cm)在等勢面中的順序。求解思路如下：假設(shè)格點 X =( x1, x2, …,xm-1,xm)位于等勢面 Ek中并且X在中的順序p小于C在Ek中的順序q，根據(jù)條件(2)求解滿足條件的數(shù)量。先考慮 x1的取值，當(dāng) x1∈[0,c1-1]，xi∈[0,g-1](i ∈[2,m])時，因為x1＜c1，根據(jù)條件(2)得知p＜q，這種情況下 X的數(shù)量固定 x1= c1，考慮 x2的取值，當(dāng) x2∈[0,c2-1]，xi∈ [ 0,g- 1 ](i∈[ 3,m])時，因為x1=c1且x2＜c2，由條件(2)得知 p＜q，這種情況下 X 的數(shù)量依次可得顯然Nm=0。上述推導(dǎo)過程中各個Ni之間沒有重疊部分且涵蓋X所有可能取值，所以滿足條件的X數(shù)量為則C在等勢面中的順序為N+1，即

結(jié)合式(2)和式(10)得格點 C = (c1, c2,… ,cm)在對角線空間填充曲線中的訪問順序為

等勢面中格點元素數(shù)量表可離線構(gòu)造，函數(shù) f值通過查表獲得，根據(jù)式（11）在O(mg)時間內(nèi)可得到格點C在對角線空間填充曲線中的訪問順序。

5 短路徑優(yōu)先的覆蓋網(wǎng)絡(luò)構(gòu)建

5.1 傳輸路徑對傳輸效率的影響

P2P系統(tǒng)中，覆蓋網(wǎng)絡(luò)與物理網(wǎng)絡(luò)的拓?fù)淦ヅ涑潭葘ο⒌膫鬏斝视兄匾绊?。兩者不相匹配?dǎo)致消息傳輸效率低下，例如當(dāng)北京大學(xué)的節(jié)點發(fā)送消息到清華大學(xué)的節(jié)點經(jīng)過斯坦福大學(xué)中的節(jié)點中繼時，會極大增加傳輸延遲。短路徑優(yōu)先策略使得節(jié)點在2個網(wǎng)絡(luò)中的相對位置盡量一致。圖4展示了采用短路徑建立覆蓋網(wǎng)絡(luò)的優(yōu)勢。圖4(a)顯示的是原始物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，假設(shè)每條鏈路的傳輸延遲為單位1，圖4(b)、圖4(c)分別展示2種不同結(jié)構(gòu)的覆蓋網(wǎng)絡(luò)，其中圖4(b)采用短路徑將節(jié)點連接在一起。當(dāng)節(jié)點1有單位消息發(fā)送到其他3個節(jié)點時，圖4 (b)中拓?fù)鋬H需要3個單位的時間，每條物理鏈路上僅通過一次消息；圖4(c)中拓?fù)鋭t需要6個單位時間，其中鏈路l23上通過3次消息，鏈路l34上通過2次消息。

圖4 不同覆蓋網(wǎng)絡(luò)對消息傳輸?shù)挠绊?/p>

5.2 覆蓋網(wǎng)絡(luò)構(gòu)建過程

本節(jié)綜合運用網(wǎng)絡(luò)距離估計技術(shù)和空間填充曲線技術(shù)，采用短路徑優(yōu)先覆蓋（SPF-overlay,shorter path first overlay）的策略構(gòu)建拓?fù)淦ヅ涞木W(wǎng)絡(luò)。使用基于被動路標(biāo)的網(wǎng)絡(luò)距離估計技術(shù)估算節(jié)點之間的傳輸延遲，在空間填充曲線技術(shù)的輔助下，快速選擇距離最近節(jié)點與之建立鄰居關(guān)系。下面詳細(xì)描述其過程。

1) 生成、存儲網(wǎng)絡(luò)坐標(biāo)

普通節(jié)點P測量到路標(biāo)的網(wǎng)絡(luò)距離獲取自身網(wǎng)絡(luò)坐標(biāo)Cp。如果直接對Cp進(jìn)行空間填充曲線映射（假設(shè)Cp中元素均為整數(shù)），由于Cp變化范圍較大，像點稀疏地分布在巨大數(shù)值空間中，給快速檢索帶來困難。因此對Cp中元素進(jìn)行量化處理，采用具有g(shù)個量化等級的非均勻量化方法，前g-1個等級的量化步長為t ms，最后一個量化等級的量化步長為+∞大，這樣Cp中元素ci的量化值為ri=min{cimod t,g-1}。將量化后的坐標(biāo)值進(jìn)行對角線SFC映射得到像點fp。節(jié)點p將網(wǎng)絡(luò)坐標(biāo)Cp、fp以及通信地址發(fā)送至中心匯聚節(jié)點RP。匯聚節(jié)點RP以fp為索引存儲網(wǎng)絡(luò)坐標(biāo)Cp及其通信地址。為提高查找速度，存儲采用如下策略：如果SFC值域空間D大小低于閾值W，則使用哈希鏈表存儲節(jié)點記錄；否則值域空間D等分為S個不同的子空間，fp屬于子空間i則將節(jié)點記錄存儲在子集合si中。閾值W大小取決于匯聚節(jié)點可用存儲空間大小。

2) 快速篩選臨近節(jié)點

節(jié)點 p需要獲取臨近節(jié)點信息建立鄰居關(guān)系時，向匯聚節(jié)點RP發(fā)送請求信息。請求中包括節(jié)點p的網(wǎng)絡(luò)坐標(biāo)映射值fp以及要求的鄰居節(jié)點數(shù)量k。匯聚節(jié)點RP查找與節(jié)點p臨近的一組節(jié)點（例如 2k），并通告給節(jié)點 p。查找臨近節(jié)點策略與存儲策略相對應(yīng)。當(dāng)采用散列鏈表存儲節(jié)點記錄時，匯聚節(jié)點在以節(jié)點p的映射值fp為中心，半徑依次增大的超立方體中尋找臨近節(jié)點。圖5顯示了在二維空間的搜索過程，RP首先在節(jié)點 p所處的格點中查找有無臨近節(jié)點，然后查找半徑d=1的所有格點，依次擴大搜索范圍，直至發(fā)現(xiàn)所需數(shù)量的臨近節(jié)點。當(dāng)采用子集策略存儲節(jié)點記錄時，根據(jù)fp確定其所屬子集si，然后以子集si為中心，在左右延伸的子集中尋找足夠數(shù)量臨近節(jié)點。

圖5 二維空間中臨近節(jié)點搜索過程

3) 計算確定最近節(jié)點集合

匯聚節(jié)點只是對臨近節(jié)點進(jìn)行粗糙篩選，節(jié)點p通過距離函數(shù)獲得更準(zhǔn)確的信息。節(jié)點p使用網(wǎng)絡(luò)距離公式計算到臨近節(jié)點的距離，選擇距離最近的k個節(jié)點與之建立鄰居關(guān)系，其余節(jié)點作為候選鄰居節(jié)點。

4) 建立鄰居關(guān)系

節(jié)點p向距離最近的k個節(jié)點發(fā)送建立連接請求，如果臨近節(jié)點能夠接納新的連接則響應(yīng)請求，并在鄰居列表中添加新的記錄；否則拒絕。如果被接受，節(jié)點p增加新的鄰居記錄；否則從候選節(jié)點中選擇新節(jié)點請求與之建立鄰居關(guān)系，直至鄰居節(jié)點的數(shù)量達(dá)到要求。

5.3 覆蓋網(wǎng)絡(luò)構(gòu)造協(xié)議的其他部分

覆蓋網(wǎng)絡(luò)連通性保證：分布式方式建立鄰居關(guān)系，不能保證建立的覆蓋網(wǎng)絡(luò)是連通的；同時節(jié)點根據(jù)網(wǎng)絡(luò)狀況調(diào)整鄰居關(guān)系也有可能導(dǎo)致覆蓋網(wǎng)絡(luò)的分裂，因此需要一定的機制來保證網(wǎng)絡(luò)的連通性。采用如下的連通性保證機制：根節(jié)點周期性向外廣播連通性報文，報文序號標(biāo)識報文的新舊。節(jié)點接收到連通性報文后，對比記錄中的序號，如果新接收的報文序號大于記錄中的序號，則將報文轉(zhuǎn)發(fā)給鄰居節(jié)點，并且更新記錄中的序號和時戳，否則不采取任何動作。節(jié)點在一定時間間隔內(nèi)沒有更新連通性報文序號，則假定覆蓋網(wǎng)絡(luò)已經(jīng)形成網(wǎng)絡(luò)孤島，節(jié)點以一定概率建立新的連接。采用上述保證機制，在每個周期內(nèi)節(jié)點接收和發(fā)送的報文數(shù)量是其鄰居數(shù)量的2倍，對系統(tǒng)影響可以忽略。

局部動態(tài)優(yōu)化：節(jié)點加入覆蓋網(wǎng)絡(luò)后動態(tài)調(diào)整鄰居關(guān)系以適應(yīng)網(wǎng)絡(luò)的變化。鄰居節(jié)點相互交換臨近節(jié)點列表以選擇更近的鄰居節(jié)點。節(jié)點將鄰居節(jié)點的數(shù)量限制在k～2k之間，當(dāng)發(fā)現(xiàn)更近節(jié)點或鄰居數(shù)量不夠時嘗試建立新的鄰居關(guān)系；當(dāng)網(wǎng)絡(luò)資源緊張或者鄰居節(jié)點不能為該連接提供足夠資源（包括鄰居節(jié)點失效）時，則剔除部分鄰居關(guān)系。

節(jié)點退出系統(tǒng)：P2P系統(tǒng)一個重要特性是節(jié)點的不穩(wěn)定性。節(jié)點退出系統(tǒng)時，向鄰居節(jié)點和匯聚節(jié)點發(fā)送退出消息。匯聚節(jié)點收到退出消息后刪除該節(jié)點對應(yīng)的記錄。鄰居節(jié)點收到退出消息后，檢查該節(jié)點是否在臨近節(jié)點列表中，如果在則刪除相關(guān)記錄并將退出消息轉(zhuǎn)發(fā)給鄰居節(jié)點以刪除鄰居節(jié)點緩存的信息。節(jié)點退出使得鄰居節(jié)點連接數(shù)量減少，可能觸發(fā)建立新的鄰居關(guān)系。節(jié)點被動失效（如強行殺死進(jìn)程、網(wǎng)絡(luò)斷掉）在交換內(nèi)容消息時檢測，節(jié)點一旦發(fā)現(xiàn)鄰居節(jié)點失效，向匯聚節(jié)點通告，在刪除本地對應(yīng)記錄同時通告其他鄰居節(jié)點。

更新節(jié)點網(wǎng)絡(luò)坐標(biāo)：節(jié)點周期性測量到路標(biāo)的網(wǎng)絡(luò)延遲重新計算其網(wǎng)絡(luò)坐標(biāo)，如果新、舊網(wǎng)絡(luò)坐標(biāo)之間的距離超過門限值則需要更新網(wǎng)絡(luò)坐標(biāo)，并將新的網(wǎng)絡(luò)坐標(biāo)通告匯聚節(jié)點和鄰居節(jié)點。網(wǎng)絡(luò)坐標(biāo)關(guān)聯(lián)一個順序號，每更新一次順序號遞增，這樣不會因網(wǎng)絡(luò)延遲等原因混淆。

路標(biāo)失效的處理：網(wǎng)絡(luò)擁塞或者路標(biāo)失效導(dǎo)致無法測得到路標(biāo)的網(wǎng)絡(luò)延遲，其網(wǎng)絡(luò)坐標(biāo)中對應(yīng)的元素值為 0。對網(wǎng)絡(luò)坐標(biāo)中的零元素進(jìn)行量化時，假定節(jié)點在該維度上與所有其他節(jié)點都是臨近的，即零元素的量化值分布在每個量化等級上，相當(dāng)于將節(jié)點復(fù)制g份（g為量化等級）。

6 實驗分析

本節(jié)通過模擬實驗驗證方案 SPF-overlay的有效性，旨在構(gòu)建拓?fù)淦ヅ涞母哔|(zhì)量覆蓋網(wǎng)絡(luò)，減少消息傳播時間。本文引入匹配度來定量描述覆蓋網(wǎng)絡(luò)與底層物理網(wǎng)絡(luò)的拓?fù)淦ヅ涑潭?。稱覆蓋網(wǎng)絡(luò)中路徑為實際路徑，稱物理網(wǎng)絡(luò)中的最短路徑為理想路徑。下面給出路徑匹配度和拓?fù)淦ヅ涠鹊亩x。

路徑匹配度：覆蓋網(wǎng)絡(luò)中不相鄰的2個節(jié)點理想路徑與實際路徑長度的比率。

拓?fù)淦ヅ涠龋焊采w網(wǎng)絡(luò)中所有不相鄰節(jié)點之間路徑匹配度的均值。

在上述定義中沒有考慮覆蓋網(wǎng)絡(luò)中直接相連節(jié)點之間的匹配度，因為其路徑匹配度為常數(shù) 1，不能體現(xiàn)覆蓋網(wǎng)絡(luò)與物理網(wǎng)絡(luò)的匹配程度。

6.1 實驗設(shè)置

在討論拓?fù)淦ヅ鋾r使用如下的網(wǎng)絡(luò)模型：物理網(wǎng)絡(luò)由路由器節(jié)點相互連接構(gòu)成，端節(jié)點粘貼在與其相連的路由器節(jié)點上，到對應(yīng)路由器的網(wǎng)絡(luò)距離忽略不計，物理網(wǎng)絡(luò)與覆蓋網(wǎng)絡(luò)均采用最短路徑路由策略。

本文采用文獻(xiàn)[14]的方法生成具有10 000個路由器節(jié)點的物理網(wǎng)絡(luò)拓?fù)洹８采w網(wǎng)絡(luò)節(jié)點規(guī)模變化范圍為1 000～5 000，默認(rèn)數(shù)量為2 000。覆蓋網(wǎng)絡(luò)中節(jié)點的鄰居數(shù)量k取值范圍為4～10。PLNDP中路標(biāo)節(jié)點數(shù)量為10，在路由器節(jié)點中隨機選取。實驗中比較4種不同的覆蓋網(wǎng)絡(luò)構(gòu)造方案：①最短路徑方案，這是一種集中式的算法，每個節(jié)點測量到其他所有節(jié)點的距離，然后選擇距離最近的k個節(jié)點作為鄰居，同時保證整個覆蓋網(wǎng)絡(luò)的連通性，下文中以“best”標(biāo)識。②SPF-overlay方案，每個節(jié)點按照5.2節(jié)中介紹的過程分布式加入到覆蓋網(wǎng)絡(luò)中。網(wǎng)絡(luò)坐標(biāo)的量化等級設(shè)為 5，使用散列鏈表存儲節(jié)點記錄，在半徑依次增大的超立方體中尋找最近節(jié)點。覆蓋網(wǎng)絡(luò)構(gòu)造完成后繼續(xù)進(jìn)行局部動態(tài)優(yōu)化操作，本文初衷是直接構(gòu)造高質(zhì)量的覆蓋網(wǎng)絡(luò)，因此實驗中僅驗證 SPF-overlay方案中初始構(gòu)造的覆蓋網(wǎng)絡(luò)的質(zhì)量，下文中以“SPF”標(biāo)識；③隨機的覆蓋網(wǎng)絡(luò)構(gòu)造方案，節(jié)點隨機地選擇 個節(jié)點作為鄰居節(jié)點，下文中以“rand”標(biāo)識；④LTM方案，在隨機覆蓋網(wǎng)絡(luò)的基礎(chǔ)上進(jìn)行LTM中的優(yōu)化操作，下文中以“LTM”標(biāo)識。LTM方案中迭代的最大次數(shù)為200次，迭代終止條件為在一次迭代過程中優(yōu)化的連接數(shù)量小于整個覆蓋網(wǎng)絡(luò)連接數(shù)量的萬分之一。一次迭代過程指所有節(jié)點都向外泛洪一次探測報文并優(yōu)化連接。LTM中剪枝的截止系數(shù)設(shè)為1.6，也就是長邊長度至少是短邊的1.6倍時才被剪除；加邊的截止系數(shù)設(shè)為1.3，也就是增加的連接的長度最多不能超過現(xiàn)有相關(guān)連接的1.3倍。模擬實驗的硬件環(huán)境為普通桌面PC機，3.0GHz Pentium 4 CPU，2GB內(nèi)存，模擬軟件采用MATLAB 7.0。

6.2 實驗結(jié)果

圖6顯示了4種不同覆蓋網(wǎng)絡(luò)單跳邏輯連接長度的分布，可以看出best和SPF方案形成的覆蓋網(wǎng)絡(luò)中邊的長度比較集中且明顯比 LTM 和 rand方案中短。best方案較SPF方案優(yōu)勢更為明顯，但是 best方案中節(jié)點需要獲知全局網(wǎng)絡(luò)狀態(tài)信息，可擴展性差，網(wǎng)絡(luò)規(guī)模受到限制。LTM在迭代過程中每個節(jié)點平均調(diào)整 6.4條邏輯連接，其中平均增加邏輯連接 3.6條，剪除邏輯連接 2.8條（增加的邏輯連接比剪除的多是因為程序中放松了對節(jié)點度的限制）。圖7顯示了4種不同方案中節(jié)點之間邏輯路徑長度的累積分布，best方案中邏輯路徑平均長度最小且路徑長度分布范圍集中。SPF方案中路徑長度分布相對分散，不如其余三者集中，主要原因是選擇鄰居節(jié)點時由于預(yù)測誤差導(dǎo)致選取遠(yuǎn)距離的節(jié)點。但是相比LTM和rand方案還是具有優(yōu)勢，特別是短路徑所占比例明顯高于后兩者。例如SPF中路徑長度小于500的占所有路徑數(shù)量的57.2%，而LTM中為27.7%，rand中僅為10.5%。

圖6 邏輯連接長度的分布

圖7 邏輯路徑長度的累積分布

圖8顯示了路徑匹配度的分布，SPF的表現(xiàn)好于LTM和rand方案，特別是路徑匹配度小于0.25的路徑在SPF方案中所占比例極小，可以忽略。相反在 LTM 和 rand方案中大量路徑的匹配度小于0.25。4種方案的拓?fù)淦ヅ涠确謩e為0.616、0.438、0.366、0.306。

圖8 路徑匹配度的分布

圖9顯示了拓?fù)淦ヅ涠入S系統(tǒng)規(guī)模的變化，best和SPF方案中略微增長，而LTM和rand方案中稍微有所下降。這是因為在保持節(jié)點度不變的情況下，隨著系統(tǒng)規(guī)模的增大，SPF中找到臨近節(jié)點的可能性增大，而 LTM 中邏輯路徑的跳數(shù)增加，需要更多的迭代次數(shù)才能保持匹配度不變。SPF方案相比LTM具有更好的擴展性。

圖9 拓?fù)淦ヅ涠入S系統(tǒng)規(guī)模的變化

假設(shè)鄰居節(jié)點數(shù)量為 k。best方案需要獲取全局信息，其通信開銷O(n2)。SPF通信開銷由2個主要部分組成，①測量到路標(biāo)的網(wǎng)絡(luò)延遲，路標(biāo)的數(shù)量為常數(shù)，測量開銷O(n)；②獲取臨近節(jié)點信息并與鄰居節(jié)點建立邏輯連接，通信開銷為O(kn)。LTM是在隨機網(wǎng)絡(luò)基礎(chǔ)上做局部優(yōu)化，建立隨機網(wǎng)絡(luò)的通信開銷為O(kn)；局部優(yōu)化時測量到2跳范圍內(nèi)節(jié)點的網(wǎng)絡(luò)延遲，測量開銷取決于鄰居節(jié)點的數(shù)量和迭代次數(shù)。圖10顯示SPF和LTM方案在不同的網(wǎng)絡(luò)規(guī)模下需要的通信消息數(shù)量。SPF的通信開銷遠(yuǎn)小于 LTM，但是 SPF方案在篩選臨近節(jié)點時需要一定的計算量。

圖10 額外通信開銷的比較

7 結(jié)束語

P2P應(yīng)用中消息沿著覆蓋網(wǎng)絡(luò)中的peer節(jié)點中繼傳輸，如果覆蓋網(wǎng)絡(luò)與底層物理網(wǎng)絡(luò)拓?fù)洳幌嗥ヅ洌粌H增大消息的傳播延時，而且增加主干網(wǎng)的網(wǎng)絡(luò)流量。因此構(gòu)建拓?fù)淦ヅ涞母采w網(wǎng)絡(luò)是提高大規(guī)模P2P應(yīng)用系統(tǒng)性能的關(guān)鍵因素之一。若有網(wǎng)絡(luò)拓?fù)湫畔⒌闹笇?dǎo)，節(jié)點在加入覆蓋網(wǎng)絡(luò)時會找到更好的鄰居節(jié)點。本文提出短路徑優(yōu)先的覆蓋網(wǎng)絡(luò)構(gòu)建策略，主要工作包括以下3個方面：①提出基于被動路標(biāo)的網(wǎng)絡(luò)距離預(yù)測算法，提供節(jié)點間較為準(zhǔn)確的網(wǎng)絡(luò)拓?fù)湫畔?；②提出基于查表的對角線空間填充曲線快速映射算法，解決快速提取具有相關(guān)拓?fù)湫畔⒐?jié)點的問題；③綜合網(wǎng)絡(luò)距離預(yù)測算法和空間填充曲線技術(shù)提出拓?fù)淦ヅ涞母采w網(wǎng)絡(luò)構(gòu)造算法SPF-overlay。實驗結(jié)果表明SPF-overlay方法構(gòu)造的覆蓋網(wǎng)絡(luò)比隨機網(wǎng)絡(luò)和 LTM 算法能夠更好的匹配底層物理網(wǎng)絡(luò)；同時本文以計算開銷代替網(wǎng)絡(luò)開銷，使得SPF-overlay的額外網(wǎng)絡(luò)負(fù)載開銷更小，具備良好的可擴展性，能夠提高大規(guī)模分布式系統(tǒng)的性能。

[1] LUA E, GRIFFIN T, PIAS M. On the accuracy of embeddings for internet coordinate systems[C]. Proc of IMC05[C]. USENIX Association Berkeley, CA, USA, 2005. 1-11.

[2] SAGAN H, Space Filling Curves[M]. Berlin: Sprubger, 1994.

[3] RATNASAMY S, HANDLE M, SHENKER S. Topologically-aware overlay construction and server selection[A]. Proc of INFOCOM 2002[C]. New York, USA, 2002.1190-1199.

[4] MARCEL W, RINALDI R. Efficient topologyaware overlay net-work[J]. ACM Computer Communication Review, 2003, 33(1):101-106.

[5] XU Z, TANG C, ZHANG Z. Building topology-aware overlays using global soft-state[A]. Proc of the 23rd International Conference on Distributed Computing Systems[C]. Washington, DC, USA, 2003. 500-508.

[6] REN S, GUO L, ZHANG X. SAT-match: a self-adaptive topology matching method to achieve low lookup latency in structured P2P overlay networks[A]. Proc of the 18th International Parallel and Distributed Processing Symposium(IPDPS'04)[C]. 2004. 83-91.

[7] RATNASAMY R, FRANCIS P, KARP R. A scalable content-addressable network[A]. Proc of SIGCOMM2001[C]. San Diego, CA, USA, 2001.161-172.

[8] SUN M, ZHANG Z. Quasi-chord: physical topology aware structured P2P network[A]. Proc of the 11th Joint Conference on Information Sciences[C]. Shenzhen, China, 2008.

[9] EUGENE T, ZHANG H. Predicting internet network distance with coordinates-based approaches[A]. Proc of INFOCOM2002[C]. New York, USA, 2002.170-179.

[10] STIUCA I, MORRUS R, BAKARISHNAN H. Chord: a scalable peer-to-peer lookup service for internet applications[A]. Proc of SIGCOMM 2001[C]. San Deigo, CA, USA, 2001.149-160.

[11] LIU Y, LIU X, ZHANG X. Location-aware topology matching in P2P systems[A]. Proc of Infocom2004[C]. Hong Kong, China, 2004.2220-2230.

[12] PEANO G. sur une courbe qui remplit toute une air plaine[J].Mathiematishe Annalen, 1981, 96(1): 157-160.

[13] HILBERT D. Ueber stetige abbildung einer linie auf ein flashenstuck[J]. Mathiematishe Annalen, 1981, 96(3): 459-460.

[14] ZEGURA E, CALVERT K, BHATTACHARJEE S. How to model an internetwork[A]. Proc of INFOCOM96[C]. San Francisco, CA, USA,1996. 594-602.