基于位置無關(guān)名字的可擴(kuò)展幾何路由方案

孫彥斌，張宇，張宏莉，方濱興

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001)

研究與開發(fā)

基于位置無關(guān)名字的可擴(kuò)展幾何路由方案

孫彥斌，張宇，張宏莉，方濱興

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001)

名字路由已成為未來網(wǎng)絡(luò)的研究熱點(diǎn)之一，由于網(wǎng)絡(luò)中節(jié)點(diǎn)和信息規(guī)模的持續(xù)增長，可擴(kuò)展問題成為其瓶頸。幾何路由作為新型可擴(kuò)展路由方案，可同時滿足路由表規(guī)模和路由路徑的可擴(kuò)展，但難以支持名字路由。首先在幾何路由基礎(chǔ)上提出了一種通用的基于位置無關(guān)名字的可擴(kuò)展幾何路由方案——GRIN，結(jié)合源路由和貪心路由實(shí)現(xiàn)混合幾何路由，在混合幾何路由上引入基于雙層稀疏群組的名字解析(映射)。然后理論分析了節(jié)點(diǎn)狀態(tài)及名字映射的路徑延展度上界。最后通過仿真驗(yàn)證了GRIN具備可擴(kuò)展、低延展度以及高可靠性等特征，并優(yōu)于其他名字路由方案。

幾何路由;名字解析;名字路由;可擴(kuò)展性

1 引言

名字路由采用位置無關(guān)(location-independent)的名字(標(biāo)識)進(jìn)行尋址，其將標(biāo)識/位置分離，是解決當(dāng)前互聯(lián)網(wǎng)絡(luò)IP語義過載問題的重要手段，提高網(wǎng)絡(luò)移動性并消除地址管理分配的負(fù)擔(dān)。同時，互聯(lián)網(wǎng)正朝著面向內(nèi)容的方向發(fā)展，重新設(shè)計(jì)互聯(lián)網(wǎng)體系結(jié)構(gòu)成為未來互聯(lián)網(wǎng)研究的趨 勢 。ICN(information centric networking)［1］采 用 以 內(nèi) 容 為中心的設(shè)計(jì)方案，將網(wǎng)絡(luò)關(guān)注的重心由位置(where)轉(zhuǎn)向內(nèi)容(what)，是Internet最有可能的替代者之一。為實(shí)現(xiàn)位置無關(guān)的內(nèi)容尋址，名字路由成為ICN的關(guān)鍵技術(shù)。可見，名字路由已成為當(dāng)前及未來互聯(lián)網(wǎng)絡(luò)研究的重點(diǎn)。

名字路由采用標(biāo)識和位置分離方案，依靠位置無關(guān)的名字尋址。本文中，名字具有廣義的概念，是任意網(wǎng)絡(luò)對象(如主機(jī)、內(nèi)容或服務(wù))的身份標(biāo)識，具備全局性、唯一性和持續(xù)性。全局和唯一指不同對象之間名字唯一，且全局可見。持續(xù)性是指保證名字不受其所有者、位置、時間等因素影響。

名字路由可分為兩類:一類直接根據(jù)名字路由，ROFL［2］根據(jù)節(jié)點(diǎn)ID采用貪心路由實(shí)現(xiàn)主機(jī)間通信，CCN［3］用名字替代IP地址，采用類似OSPF的路由方案實(shí)現(xiàn)內(nèi)容或服務(wù)查詢;另一種采用基于名字解析的路由方式，先通過名字解析獲得對象的位置信息，再選擇合適的位置通信，如LISP［4］、Disco［5］、TRIAD［6］、DONA［7］、NetInf［8］。

無論采用直接路由還是名字解析，名字路由都面臨嚴(yán)重可擴(kuò)展問題:一方面，由于互聯(lián)網(wǎng)節(jié)點(diǎn)和內(nèi)容數(shù)量龐大并持續(xù)增長，海量網(wǎng)絡(luò)對象將產(chǎn)生龐大的位置無關(guān)的名字空間，導(dǎo)致路由表規(guī)模過大。同時，由于名字的位置無關(guān)性，名字相似的網(wǎng)絡(luò)對象很難來自相鄰節(jié)點(diǎn)，相同名字的網(wǎng)絡(luò)對象也可能分布在多個節(jié)點(diǎn)，導(dǎo)致名字聚合難以實(shí)現(xiàn)。另一方面，名字的位置無關(guān)性使得名字不包含位置和路由信息，導(dǎo)致路由效率低下。為解決以上問題，需要設(shè)計(jì)一種基于位置無關(guān)名字的可擴(kuò)展路由方案。

可擴(kuò)展的名字路由應(yīng)滿足以下條件:位置無關(guān)，采用任意(隨機(jī))的名字進(jìn)行路由，保證名字與位置無關(guān);可擴(kuò)展(scalability)，保證路由表與網(wǎng)絡(luò)規(guī)模呈亞線性關(guān)系，使得存儲、計(jì)算等資源滿足網(wǎng)絡(luò)規(guī)模的增長;低延展度(low stretch)，延展度即節(jié)點(diǎn)間實(shí)際路徑長度與最短路徑長度的比值，低延展與可擴(kuò)展相互矛盾，二者折中是可擴(kuò)展路由成功的關(guān)鍵;可靠性(reliability)，當(dāng)部分節(jié)點(diǎn)或鏈路失效時，仍保證路由盡可能可達(dá)。

本文主要研究基于名字解析的路由方案。傳統(tǒng)名字解析方法如名字字典、DNS等，多基于樹型結(jié)構(gòu)或采用傳統(tǒng)DHT方案，存在路徑過長的問題。本文采用革命性的方式，擺脫傳統(tǒng)路由限制，在新型可擴(kuò)展路由基礎(chǔ)上實(shí)現(xiàn)名字路由。

基于貪心嵌入的幾何路由［9］將網(wǎng)絡(luò)拓?fù)湄澬那度攵攘靠臻g，為每個節(jié)點(diǎn)分配一個坐標(biāo)，根據(jù)坐標(biāo)距離進(jìn)行貪心路由。幾何路由作為一種位置相關(guān)的可擴(kuò)展路由方案，具備良好的可擴(kuò)展特性:路由表只需保存鄰居節(jié)點(diǎn)坐標(biāo);延展度上界和平均延展度可維持較低水平;任意兩節(jié)點(diǎn)之間可能存在多條可用的路徑;同時還支持節(jié)點(diǎn)間距離的計(jì)算。現(xiàn)已被用于解決互聯(lián)網(wǎng)的路由可擴(kuò)展問題。目前幾何路由研究多集中在圖的貪心嵌入、坐標(biāo)壓縮以及降低路徑延展度等方面，屬于位置相關(guān)路由的范疇，而對位置無關(guān)路由研究很少，即給定一個網(wǎng)絡(luò)對象的名字，如何尋找該對象。

本文以幾何路由為基礎(chǔ)，提出一種通用的基于位置無關(guān)名字的幾何路由方案——GRIN(geometric routing on location-independent name)，結(jié)合底層幾何路由和上層名字解析實(shí)現(xiàn)名字路由。本文主要貢獻(xiàn)在于:在幾何路由基礎(chǔ)上提出源路由和貪心路由相結(jié)合的混合幾何路由(hybrid geometric routing，HGR)方案;基于稀疏群組(sloppy group)［5］思想提出基于雙層稀疏群組的名字解析框架實(shí)現(xiàn)名字到位置的映射;分析了HGR和GRIN在節(jié)點(diǎn)狀態(tài)以及路徑延展度的理論上界;通過仿真模擬驗(yàn)證GRIN在路由表規(guī)模、路徑延展度以及可靠性等方面都優(yōu)于其他路由方法。

2 相關(guān)工作

可擴(kuò)展的名字路由設(shè)計(jì)多基于可擴(kuò)展路由?，F(xiàn)有的可 擴(kuò) 展 路 由 主 要 包 括 :層 次 路 由 (hierarchical routing)［10］、DHT 路 由［11］、緊 致 路 由 (compact routing)［5，12］和 幾 何 路 由(geometric routing)［9，13］。后三者可廣泛應(yīng)用于名字路由。與本文相近的名字路由有基于DHT路由的VRR［11］和基于緊致路由的Disco［5］，二者均用于主機(jī)名空間，而本文可用于主機(jī)、內(nèi)容或服務(wù)等多種網(wǎng)絡(luò)對象的名字空間，支持扁平和層次名字。

DHT路由將名字分布式發(fā)布到網(wǎng)絡(luò)節(jié)點(diǎn)，多與其他路由相結(jié)合實(shí)現(xiàn)節(jié)點(diǎn)間通信。VRR(virtual ring routing)［11］將DHT與源路由相結(jié)合。節(jié)點(diǎn)采用扁平名字，根據(jù)名字大小形成虛擬環(huán)，每個節(jié)點(diǎn)存儲環(huán)上前驅(qū)和后繼節(jié)點(diǎn)的物理路徑以及鄰居信息，(同時節(jié)點(diǎn)v與其前驅(qū)/后繼u的物理路徑上的每個節(jié)點(diǎn)都存儲到v和u的物理路徑)，路由時選擇與目的節(jié)點(diǎn)名字大小最接近的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。VRR能保證平均路由表項(xiàng)數(shù)為(n為網(wǎng)絡(luò)規(guī)模)，但部分節(jié)點(diǎn)路由表項(xiàng)過多，且無延展度上界，最壞情況可達(dá)到O(n)。部分DHT 方案與 傳統(tǒng) IP 路由 相結(jié)合 ，如 αRoute［14］、MDHT［15］。αRoute基于符號劃分提出樹型的名字DHT方案，將名字根據(jù)其符號分布式發(fā)布到網(wǎng)絡(luò)節(jié)點(diǎn)，為降低路徑延展度，建立了DHT拓?fù)涞降讓油負(fù)涞挠成?，但解析信息分布是否均勻依賴于對名字庫的分析。MDHT基于解析域構(gòu)建層次DHT，域內(nèi)采用傳統(tǒng)DHT方案，域間則為樹型層次結(jié)構(gòu)，名字被發(fā)布到本地解析域以及對應(yīng)的上層域，雖然該方案支持本地解析，但本地解析失敗易產(chǎn)生長路徑。

緊致路由將部分拓?fù)湫畔嚎s到節(jié)點(diǎn)地址或報文頭部，路由表只需保存部分路由信息，從而達(dá)到路由表規(guī)?？蓴U(kuò)展和路徑低延展度的折中。Disco采用層疊網(wǎng)設(shè)計(jì)。底層采用位置相關(guān)路由NDDisco，通過鄰域和LandMark(LM)信息實(shí)現(xiàn)節(jié)點(diǎn)間路由，上層通過稀疏群組實(shí)現(xiàn)名字解析(映射)。Disco路由表項(xiàng)達(dá)到，路徑延展度≤7。NIHDLR［16］提出無標(biāo)度網(wǎng)絡(luò)上的名字路由，選擇節(jié)點(diǎn)度大的節(jié)點(diǎn)作為LM節(jié)點(diǎn)，并基于LM實(shí)現(xiàn)名字解析，路徑延展度降為min｛3，2+d｝，但加重了LM的負(fù)擔(dān)。LM作為以上兩種路由的重要節(jié)點(diǎn)，所有通信都要經(jīng)過LM，LM可能會成為路由的瓶頸;同時，由于將路由信息嵌入節(jié)點(diǎn)地址，路由可靠性難以保證。

幾何路由將網(wǎng)絡(luò)拓?fù)淝度攵攘靠臻g，為每個節(jié)點(diǎn)分配一個度量空間的坐標(biāo)，并基于坐標(biāo)距離實(shí)現(xiàn)貪心路由。PIE［13］采用多層貪心嵌入方法，將嵌入分為 lbn層，在第 i層將圖劃分為2i部分，分別提取生成樹并嵌入O(lb2n)維、l∞范數(shù)(norm)空間。PIE節(jié)點(diǎn)只需存儲鄰居節(jié)點(diǎn)坐標(biāo)，在標(biāo)度系數(shù)為2～3的無標(biāo)度網(wǎng)絡(luò)及部分隨機(jī)網(wǎng)絡(luò)中其延展度上界為O(lbn)，但PIE不支持名字路由。參考文獻(xiàn)［17-19］提出幾何路由上的名字路由方案，基于幾種特殊的幾何路由(如前綴嵌入幾何路由、雙曲空間嵌入幾何路由)，將名字映射為度量空間上的坐標(biāo)，直接通過貪心路由找到距離其最近的節(jié)點(diǎn)作為其解析節(jié)點(diǎn)。但以上方案均針對單一幾何路由方案，不具備通用性，且解析信息分布難以保證均勻。

本文在幾何路由基礎(chǔ)上提出名字路由方案GRIN，對幾何路由具有通用性，能同時滿足可擴(kuò)展、位置無關(guān)、低延展度和可靠性等需求，不同情況下，其節(jié)點(diǎn)路由表項(xiàng)分別為）或當(dāng)?shù)讓勇酚陕窂窖诱苟壬辖鐬镺(k)時，名字解析的路徑延展度上界達(dá)到O(2k+1)。

3 基于位置無關(guān)名字的幾何路由

GRIN可分為位置相關(guān)路由和名字解析兩部分。位置相關(guān)路由處于物理網(wǎng)絡(luò)拓?fù)?，采用混合幾何路由方案為名字解析和?jié)點(diǎn)間通信提供路由支持;名字解析處于邏輯的名字空間拓?fù)洌瑢⒕W(wǎng)絡(luò)對象的名字映射為位置。下面首先介紹HGR，然后討論基于雙層稀疏群組的名字解析框架。

3.1 混合幾何路由

新幾何路由方案設(shè)計(jì)不是本節(jié)研究重點(diǎn)，本節(jié)主要目的是改進(jìn)幾何路由使其適用于名字路由。鑒于PIE實(shí)現(xiàn)方便、計(jì)算簡單等特點(diǎn)，HGR選擇在PIE基礎(chǔ)上進(jìn)行設(shè)計(jì)，但HGR具有通用性，其并不局限于PIE，同樣適用于其他幾何路由。下面首先明確基于貪心嵌入幾何路由的基本表示和定義，然后給出HGR的具體方案。

給定圖G(V，E)，G為無向連通圖，V為節(jié)點(diǎn)集合，E為邊集，對于圖G中的任意節(jié)點(diǎn)v，Nv為v的鄰居集合。(X，d)為度量空間，其中，X為空間集合，d為X上的度量(距離)。

定義1 ?f∶V→X，f為 V到度量空間 X的映射，對?v，u∈V，?γ＞0，使得:

當(dāng)D=1時，則稱映射f為圖G到X的等距嵌入。d′為G上的度量，γ為伸縮系數(shù)，D為形變系數(shù)。

定義2 ?f∶V→X，f為 V到度量空間 X的映射，對?v，u∈V，(u?Nv)，?w∈Nv，使得:

則稱映射f為圖G到X的貪心嵌入。即在度量空間X中，當(dāng)數(shù)據(jù)分組到達(dá)任意非目的節(jié)點(diǎn)f(v)，總能找到一個鄰居節(jié)點(diǎn) f(w)，使得 f(w)到 f(u)的距離小于 f(v)到 f(u)的距離。

等距嵌入保證圖嵌入度量空間后不發(fā)生扭曲形變，其滿足貪心嵌入的條件;貪心嵌入則是為了將圖嵌入度量空間，使節(jié)點(diǎn)之間仍滿足貪心條件，進(jìn)而保證貪心路由100%可達(dá)。

Kleinberg［9］證明了圖G的生成樹到某度量空間的貪心嵌入，即G到該度量空間的貪心嵌入。為將拓?fù)鋱D貪心嵌入度量空間，HGR首先提取生成樹，然后將生成樹等距嵌入度量空間，最后結(jié)合源路由和貪心路由實(shí)現(xiàn)節(jié)點(diǎn)間通信。因此，HGR可分為3部分:生成樹提取、生成樹等距嵌入和混合路由。

3.1.1 生成樹提取

Cvetkovski等人［20］研究發(fā)現(xiàn)對于基于生成樹貪心嵌入的幾何路由，生成樹選擇是影響延展度的主要因素之一，要保證低延展度，生成樹的邊應(yīng)盡可能地與最短路徑重合，并提出最大權(quán)重生成樹(權(quán)重指最短路徑經(jīng)過該邊的次數(shù))和最小直徑生成樹兩種探索性方法。

由于最大權(quán)重生成樹和最小直徑生成樹分別在邊權(quán)重獲取和圖核心節(jié)點(diǎn)查找等方面的限制，無法找到高效的分布式算法。因此，首先為每一個節(jié)點(diǎn)分配節(jié)點(diǎn)ID，ID由兩部分組成:節(jié)點(diǎn)度和隨機(jī)值。然后選擇ID最大的節(jié)點(diǎn)作為根節(jié)點(diǎn)，其后每一個節(jié)點(diǎn)選擇到根節(jié)點(diǎn)距離最小的節(jié)點(diǎn)作為父節(jié)點(diǎn)。具體實(shí)現(xiàn)可采用STP［21］。該方法可有效減小樹的直徑以及坐標(biāo)長度，盡可能地保證低延展度。

3.1.2 生成樹等距嵌入

對于生成樹 T 中的節(jié)點(diǎn) O，其坐標(biāo)為(o1，o2，…，ok-1)，S為 O 的子節(jié)點(diǎn)集合，S=｛v0，v1，…，vs-1｝，s為子節(jié)點(diǎn)數(shù)量，s=｜S｜。

HGR將生成樹T等距嵌入l∞范數(shù)空間，T的等距嵌入過程與PIE類似:假設(shè)已知節(jié)點(diǎn)O的坐標(biāo)，首先為其子節(jié)點(diǎn) vi分 配 一 個 哈 夫 曼 編 碼然 后 根 據(jù) 編碼和父節(jié)點(diǎn)的坐標(biāo)計(jì)算 vi坐標(biāo)Ci由兩部分組成，一部分ci1來自父節(jié)點(diǎn)O的坐標(biāo)，另一部分ci2根據(jù)編碼獲得，dT(vi，O)為 vi與 O在樹上的邊權(quán)值，按照式(3)、式(4)可獲得節(jié)點(diǎn)坐標(biāo)。具體例子如圖1所示，節(jié)點(diǎn)a的坐標(biāo)為3，其包含兩個子節(jié)點(diǎn):b和c，a分別為b和c分配哈夫曼編碼:1(用“+”表示)和 0(用“-”表示)。對于節(jié)點(diǎn)c，ac邊權(quán)重為2，由于a坐標(biāo)3＞0，則前一部分坐標(biāo) ci1=3+2;由于c的編碼為0，所以后半部分坐標(biāo)為ci2=-2。由此可得 c 的坐標(biāo)(5，-2)。

圖1 生成樹貪心嵌入

當(dāng)父節(jié)點(diǎn)坐標(biāo)為0時，子節(jié)點(diǎn)坐標(biāo)完全來自編碼，按照式(4)可獲得節(jié)點(diǎn)坐標(biāo);當(dāng)只有一個子節(jié)點(diǎn)時，子節(jié)點(diǎn)坐標(biāo)完全來自父節(jié)點(diǎn)，無需對其編碼，按照式(3)可獲得節(jié)點(diǎn)坐標(biāo)。初始時，根節(jié)點(diǎn)坐標(biāo)設(shè)為0，經(jīng)過一次生成樹的遍歷，可完成等距嵌入。

為降低坐標(biāo)長度，HGR采用不等概率的哈夫曼編碼分配坐標(biāo)。對于節(jié)點(diǎn)O，des(O)表示節(jié)點(diǎn)O的子孫節(jié)點(diǎn)數(shù)量。節(jié)點(diǎn)O的子節(jié)點(diǎn)vi的子孫節(jié)點(diǎn)數(shù)量可表示為des(vi)。則vi的編碼概率P(vi)=des(vi)/des(O)。編碼概率越大，被分配的編碼長度越短。在生成樹層數(shù)不變的情況下，子樹的節(jié)點(diǎn)數(shù)量越多，其編碼越短，從而可有效降低節(jié)點(diǎn)平均坐標(biāo)長度。

樹嵌入之后，根據(jù)lp范數(shù)空間的度量公式可得到圖G中的節(jié)點(diǎn)坐標(biāo)距離。將X作為具有l(wèi)p范數(shù)的k維度量空間，對于?x，y∈X，在 X 上的度量(坐標(biāo)距離)d(x，y)=｜x-y｜p，可表示為:

圖 G上任意兩點(diǎn) u、v，其坐標(biāo)分別為 Cu和 Cv，根據(jù) l∞空間度量公式，則其坐標(biāo)距離可表示為:

3.1.3 混合路由

貪心嵌入使得每個節(jié)點(diǎn)被分配一個坐標(biāo)，可通過貪心路由進(jìn)行通信。為支持名字解析，HGR引入鄰域(vicinity)［5］的概念，基于鄰域提出了源路由和貪心路由相結(jié)合的混合路由。

節(jié)點(diǎn)的鄰域即距離該節(jié)點(diǎn)距離最近的前k個節(jié)點(diǎn)的集合?；诿纸馕鲋械姆纸M設(shè)計(jì)(網(wǎng)絡(luò)節(jié)點(diǎn)在邏輯上被劃分為多個群組)重新定義了鄰域:節(jié)點(diǎn)s的鄰域即每個群組中距離s最近的前k'個節(jié)點(diǎn)的集合。每個節(jié)點(diǎn)的路由表保存鄰域和鄰居的并集，并記錄到各鄰域節(jié)點(diǎn)的最短路徑。

鄰域可由集中式或分布式方法獲得。集中式方法，每個節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)拓?fù)溆?jì)算以自身為根節(jié)點(diǎn)的最短路徑樹，然后選擇每個群組中距離該節(jié)點(diǎn)最近的前k'個節(jié)點(diǎn)作為鄰域節(jié)點(diǎn);分布式方法，每個節(jié)點(diǎn)從其鄰居節(jié)點(diǎn)獲得鄰居路由表中的鄰域信息，建立自己的鄰域。當(dāng)某節(jié)點(diǎn)鄰域發(fā)生變化時，將變化的路由表項(xiàng)通知其鄰居節(jié)點(diǎn)，其鄰居節(jié)點(diǎn)通過判斷是否為某群組前k'個最近節(jié)點(diǎn)進(jìn)行相應(yīng)更新。

HGR整體采用貪心路由，局部采用源路由。當(dāng)節(jié)點(diǎn)u收到目的節(jié)點(diǎn)為v的數(shù)據(jù)分組時，路由可分兩種情況討論:

· 若u為目的節(jié)點(diǎn)v，則路由結(jié)束;

·否則，采用貪心選擇策略從路由表獲得最優(yōu)下一跳w。

數(shù)據(jù)分組通過源路由沿最短路徑達(dá)到w，w重復(fù)以上過程，直到到達(dá)目的節(jié)點(diǎn)。當(dāng)源路由部分路徑失效時，則返回前一貪心節(jié)點(diǎn)，通知其路徑失效，重新貪心以保證路由成功到達(dá)。

HGR的貪心策略與幾何路由中常用的貪心策略不同。后者只選擇距離目標(biāo)最近的下一跳節(jié)點(diǎn)，其判斷的依據(jù)是下一跳節(jié)點(diǎn)與目的節(jié)點(diǎn)的坐標(biāo)距離。而HGR選擇使當(dāng)前節(jié)點(diǎn)和目的節(jié)點(diǎn)距離最小的鄰居或鄰域節(jié)點(diǎn)，其依據(jù)在于當(dāng)前節(jié)點(diǎn)到鄰居或鄰域節(jié)點(diǎn)的最短路徑距離與該鄰居或鄰域節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的坐標(biāo)距離之和是否最小。

對于任意節(jié)點(diǎn) u，v，w(v?Vu，w∈Vu)，Vu為 u 節(jié)點(diǎn)的鄰居和鄰域集合的并集，w為Vu中的節(jié)點(diǎn)，則節(jié)點(diǎn)u到v的貪心策略可表示為:，D(u，w)代表 u和w的最短路徑距離，d(w，v)代表w和v之間的坐標(biāo)距離。

3.1.4 HGR與PIE

HGR繼承了PIE的多個優(yōu)點(diǎn):路由存在多條貪心路徑，能盡量保證部分鏈路中斷或節(jié)點(diǎn)失效時，路由仍可達(dá);坐標(biāo)距離為整數(shù)間的加減運(yùn)算，坐標(biāo)運(yùn)算簡單;支持加權(quán)圖上的路由。

二者的主要區(qū)別表現(xiàn)在3個方面:PIE采用多層樹嵌入，而HGR采用單棵樹嵌入，可避免坐標(biāo)過長及多個圖嵌入產(chǎn)生的復(fù)雜通信;PIE采用等概率的哈夫曼編碼隨機(jī)分配坐標(biāo)，而HGR采用不等概率編碼，降低了平均坐標(biāo)長度;PIE采用基于坐標(biāo)的貪心路由，而HGR采用源路由和貪心路由相結(jié)合的混合路由，可有效降低路徑延展度，并支持名字解析，但是鄰域的引入會導(dǎo)致HGR路由表規(guī)模增大。

3.2 名字解析框架

GRIN名字解析與底層路由相互結(jié)合，采用稀疏群組［5］思想構(gòu)建雙層名字解析框架，充分利用底層物理拓?fù)渲械墓?jié)點(diǎn)坐標(biāo)及鄰域信息，有效限制名字解析時的路徑長度。

3.2.1 雙層名字解析框架

根據(jù)節(jié)點(diǎn)名字，稀疏群組可將網(wǎng)絡(luò)節(jié)點(diǎn)分為多個相互獨(dú)立的部分，形成邏輯的名字空間拓?fù)?。每個節(jié)點(diǎn)的名字被散列成唯一的二進(jìn)制串。由于名字結(jié)構(gòu)對散列沒有影響，因此，GRIN可同時支持扁平名字和層次名字。二進(jìn)制串前k bit(k＜lbn)相同的節(jié)點(diǎn)可作為一個群組，網(wǎng)絡(luò)被劃分為2k個群組。如圖2所示，GRIN將網(wǎng)絡(luò)分為物理網(wǎng)絡(luò)拓?fù)浜瓦壿嬅臻g拓?fù)?，在網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)被分為3個類(黑、白、灰)，每一類在名空間拓?fù)渲写硪粋€群組，其中名空間拓?fù)渲械臋E圓即代表白色節(jié)點(diǎn)組成的群組。

圖2 雙層稀疏群組

對于群組內(nèi)部節(jié)點(diǎn)，可繼續(xù)按照稀疏群組的方法，根據(jù)二進(jìn)制串的前k～k+h bit再分組，形成子群組。圖2名字空間拓?fù)渲袡E圓上相同顏色的節(jié)點(diǎn)為一個子群組?？梢愿鶕?jù)網(wǎng)絡(luò)對象的數(shù)量動態(tài)調(diào)整h的值，以便提高名字解析的效率和頑健性。當(dāng)h=0時，只有一個子群組;當(dāng)時，幾乎每個節(jié)點(diǎn)都可作一個子群組。由此，由群組和子群組構(gòu)成了GRIN的雙層名字空間拓?fù)洹?/p>

名字空間拓?fù)渖系耐ㄐ庞扇航M間通信、子群組間通信以及子群組內(nèi)部通信3部分組成。HGR的鄰域在通信過程中發(fā)揮重要作用。由于鄰域節(jié)點(diǎn)分布在不同群組，可將相互獨(dú)立的群組關(guān)聯(lián)起來，節(jié)點(diǎn)可通過其鄰域與其他群組相連，繼而實(shí)現(xiàn)了群組間通信。在群組內(nèi)部，節(jié)點(diǎn)可建立子群組表，保存每個子群組中距該節(jié)點(diǎn)最近(坐標(biāo)距離)的前l(fā)個節(jié)點(diǎn)的坐標(biāo)信息，通過這些節(jié)點(diǎn)與其他子群組相連。同時，每個節(jié)點(diǎn)保存其所在子群組的所有節(jié)點(diǎn)的坐標(biāo)信息，直接通過幾何路由實(shí)現(xiàn)子群組內(nèi)部節(jié)點(diǎn)的通信。以上3種情況，任意兩節(jié)點(diǎn)間的通信都由底層HGR支持。

3.2.2 名字發(fā)布和解析

網(wǎng)絡(luò)對象的發(fā)布以子群組為單位。當(dāng)網(wǎng)絡(luò)對象的名字/地址映射信息到達(dá)其所在子群組的某一節(jié)點(diǎn)時，該節(jié)點(diǎn)將映射信息廣播到子群組內(nèi)的所有節(jié)點(diǎn)，每個節(jié)點(diǎn)保存一份映射信息。其優(yōu)勢在于名字解析時，只需找到該子群組中任意節(jié)點(diǎn)即可完成解析，可有效減小名字解析的路徑長度。

網(wǎng)絡(luò)對象的名字解析和名字發(fā)布類似。對于節(jié)點(diǎn)s，V(s)為其鄰域集合，G(s)為s所在的群組，SG(s)為s所在的子群組。當(dāng)對象t的解析請求到達(dá)s時，可分3種情況討論:

(1)若 t∈G(s)且 t∈SG(s)，表示 s保存了 t的解析信息，則可由s將t的名字映射成地址;

(2)若 t∈G(s)但 t?SG(s)，則s從其子群組表獲得節(jié)點(diǎn)u，使得t∈SG(u)，并將解析請求轉(zhuǎn)發(fā)給 u，u重復(fù)過程(1);

(3)若 t?G(s)，則s將請求轉(zhuǎn)發(fā)到其鄰域節(jié)點(diǎn) v，使得t∈G(v)，在v中重復(fù)過程(1)、(2)完成名字解析。

GRIN的名字解析方案可有效降低名字解析的路徑延展度。在名字空間拓?fù)渖?，GRIN至多兩步就可完成名字解析:首先查詢鄰域節(jié)點(diǎn);然后通過鄰域節(jié)點(diǎn)查詢名字所在的子群組節(jié)點(diǎn)。GRIN名字解析雖然建立在名字空間拓?fù)?，但其將名字空間拓?fù)浜臀锢硗負(fù)涓o密的結(jié)合。名字空間拓?fù)淇衫绵徲蛞约白鴺?biāo)距離保證兩步查詢的路徑為最短或近似最短。同時保證若查詢節(jié)點(diǎn)周圍存在最優(yōu)的名字解析節(jié)點(diǎn)，則有很大概率被找到。

4 分析

4.1 節(jié)點(diǎn)狀態(tài)

節(jié)點(diǎn)狀態(tài)即節(jié)點(diǎn)中保存的用于路由和名字解析的信息的規(guī)模。HGR路由需要保存鄰居節(jié)點(diǎn)集合和鄰域節(jié)點(diǎn)集合的并集，這里認(rèn)為鄰居集合數(shù)量為常數(shù)，所以分析時只考慮鄰域集合數(shù)量。GRIN則保存兩類信息:名字解析表保存名字/地址映射信息;路由表保存鄰域節(jié)點(diǎn)集合、子群組集合和子群組內(nèi)的節(jié)點(diǎn)集合。

GRIN和HGR的名字解析表規(guī)模和路由表規(guī)模與策略選擇有關(guān)。若選擇名字/地址解析信息數(shù)量最優(yōu)，則將每個節(jié)點(diǎn)代表一個子群組。假設(shè)群組數(shù)量為O(x)，子群組數(shù)量達(dá)到最大值O(n/x)，由于鄰域數(shù)量與群組相等，則GRIN需要保存的路由信息為O(x+n/x)。當(dāng)時，O(x+n/x)達(dá)到最優(yōu)，此時，HGR和GRIN的路由表項(xiàng)規(guī)?？稍O(shè)置為名字解析表規(guī)模近似為O(B/n)(B為網(wǎng)絡(luò)對象數(shù)量)。

若選擇路由表規(guī)模最優(yōu)，假設(shè)群組數(shù)量、子群組數(shù)量、子群組內(nèi)部節(jié)點(diǎn)數(shù)量分別為O(x)、O(y)、O(z)，則路由表規(guī)模為 O(x+y+z)，根據(jù)均值不等式，當(dāng)x、y、z均為時，HGR和GRIN路由表規(guī)模達(dá)到最優(yōu)，為此時名字解析表規(guī)模為

4.2 路徑延展度上界

HGR是基于PIE的幾何路由，PIE已證明在標(biāo)度系數(shù)為2～3的冪律圖以及部分隨機(jī)圖上其延展度上界為O(1bn)。雖然HGR路徑延展度的理論上界與PIE相同，但實(shí)驗(yàn)證明，由于鄰域的使用，HGR的路徑延展度要優(yōu)于PIE。

GRIN名字解析的路徑延展度則由HGR的延展度決定。假設(shè)HGR路由延展度上界為O(k)，則GRIN名字解析的路徑延展度上界為O(2k+1)?？筛鶕?jù)名字解析的3種情況分析:對于前兩種情況，解析節(jié)點(diǎn)t分別為請求節(jié)點(diǎn)s自身或者與s在相同群組時，可直接解析或通過HGR路由實(shí)現(xiàn)解析，此時GRIN延展度上界為O(k)。當(dāng)解析節(jié)點(diǎn)t與請求節(jié)點(diǎn)s在不同群組時，則s與t通過s的鄰域u通信，可根據(jù)三角不等式分析其延展度上界。假設(shè)L(s，t)為s到t的實(shí)際路徑長度，可表示為:

其中，D(s，t)為其最短路徑長度，d(s，t)為 HGR 路由的路徑長度。

根據(jù)三角不等式 D(u，t)≤D(s，u)+D(s，t)可得:

由于 u 為 s的鄰域，則 D(s，u)≤D(s，t)，因此，可得 L(s，t)≤O(2k+1)D(s，t)。此時，GRIN 名字解析的延展度上界為O(2k+1)。

4.3 GRIN實(shí)現(xiàn)分析

GRIN實(shí)現(xiàn)方案簡單可行，主要包括兩種方案，可分別借鑒鏈路狀態(tài)路由協(xié)議和距離向量路由協(xié)議。前一種方案可分為兩步:節(jié)點(diǎn)通過鏈路狀態(tài)廣播LSA將其周圍的拓?fù)湫畔V播給其他節(jié)點(diǎn)，每個節(jié)點(diǎn)建立鏈路狀態(tài)數(shù)據(jù)庫LSDB，最終得到一份完整一致的網(wǎng)絡(luò)拓?fù)?基于網(wǎng)絡(luò)拓?fù)?，各?jié)點(diǎn)選擇一個相同的根節(jié)點(diǎn)構(gòu)建生成樹，并計(jì)算出自己的坐標(biāo)、鄰域節(jié)點(diǎn)及所在的群組和子群組。后一種方案可分為3步:采用SPF協(xié)議構(gòu)建生成樹，通過一次樹遍歷獲取網(wǎng)絡(luò)規(guī)模n，并通知給各節(jié)點(diǎn);采用類似距離矢量算法，為每個節(jié)點(diǎn)尋找鄰域節(jié)點(diǎn);通過鄰域節(jié)點(diǎn)獲得群組以及群組內(nèi)部節(jié)點(diǎn)信息。

5 仿真結(jié)果

本文基于C++設(shè)計(jì)了一種靜態(tài)路由模擬器。為支持大規(guī)模模擬，采用集中式方法設(shè)計(jì)簡化的模擬器，模擬器主要包括拓?fù)漕惡凸?jié)點(diǎn)類。拓?fù)漕惐４嫠泄?jié)點(diǎn)，負(fù)責(zé)拓?fù)渖伞⒙酚杀順?gòu)建、名字發(fā)布和解析等。節(jié)點(diǎn)類保存節(jié)點(diǎn)ID、路由表、解析表、鄰居鏈表以及統(tǒng)計(jì)信息等，并負(fù)責(zé)轉(zhuǎn)發(fā)報文。拓?fù)渖芍饕晌募x取和由拓?fù)淠Ｐ?(如ER模型、BA模型、GLP模型等)生成，拓?fù)渖蛇^程中，每個節(jié)點(diǎn)被隨機(jī)分配一個名字，并通過SHA-1將名字散列為128 bit的比特串。路由表構(gòu)建需要完成生成樹提取、貪心嵌入、鄰域以及子群組獲取，均可基于全局拓?fù)湫畔?shí)現(xiàn)。名字發(fā)布/解析時，先設(shè)置源節(jié)點(diǎn)以及要發(fā)布/解析的名字，然后可調(diào)用各節(jié)點(diǎn)的轉(zhuǎn)發(fā)方法實(shí)現(xiàn)路由轉(zhuǎn)發(fā)。根據(jù)名字散列以及路由信息匹配選擇轉(zhuǎn)發(fā)的下一跳，并保存相關(guān)統(tǒng)計(jì)信息。下一跳節(jié)點(diǎn)繼續(xù)進(jìn)行匹配轉(zhuǎn)發(fā)，直到達(dá)到解析節(jié)點(diǎn)，將發(fā)布信息存入解析表或根據(jù)解析表查詢對應(yīng)的解析信息。

分別在真實(shí)網(wǎng)絡(luò)拓?fù)浜吞摂M網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真。實(shí)驗(yàn)中網(wǎng)絡(luò)拓?fù)渚鳛闊o向連通圖。真實(shí)網(wǎng)絡(luò)拓?fù)錇镃AIDA［22］在2012年1月采集的10 683個節(jié)點(diǎn)的Internet AS拓?fù)鋽?shù)據(jù)集;模擬網(wǎng)絡(luò)拓?fù)洳捎脽o標(biāo)度網(wǎng)絡(luò)的經(jīng)典模型 (BA模型)［23］生成，設(shè)置其初始節(jié)點(diǎn)數(shù)為 3，平均節(jié)點(diǎn)度為 4。

Disco為目前較好的名字路由，基于主機(jī)名字空間設(shè)計(jì)，為與Disco及其底層路由NDDisco比較，采用與Disco相同的路由表規(guī)模并將子群組數(shù)量設(shè)置為最大，此時，GRIN與基于主機(jī)名字空間的路由類似。分別從坐標(biāo)長度、節(jié)點(diǎn)的節(jié)點(diǎn)狀態(tài)、路徑延展度以及可靠性4個方面分析HGR和GRIN。

5.1 坐標(biāo)長度

分別在真實(shí)拓?fù)浜湍M拓?fù)錅y量等概率哈夫曼編碼和不等概率哈夫曼編碼產(chǎn)生的坐標(biāo)長度，圖3為真實(shí)拓?fù)湎伦鴺?biāo)長度分布，不等概率編碼坐標(biāo)長度集中在10～15，平均長度為14.94，而等概率編碼坐標(biāo)長度則集中在15～20，平均長度為16.17。圖4為模擬拓?fù)湓诓煌W(wǎng)絡(luò)規(guī)模下的坐標(biāo)平均長度，x軸取對數(shù)?？梢钥闯觯骄鴺?biāo)長度與lbn近似呈線性關(guān)系，采用不等概率編碼的平均坐標(biāo)長度明顯優(yōu)于等概率編碼的坐標(biāo)長度。

圖3 節(jié)點(diǎn)坐標(biāo)長度分布

5.2 節(jié)點(diǎn)狀態(tài)

實(shí)驗(yàn)中節(jié)點(diǎn)狀態(tài)只比較路由表項(xiàng)數(shù)量，本文分別從概率分布和平均節(jié)點(diǎn)狀態(tài)兩方面分析節(jié)點(diǎn)狀態(tài)。圖5為各路由方案的節(jié)點(diǎn)狀態(tài)的概率分布?？梢钥闯觯鞣桨傅墓?jié)點(diǎn)狀態(tài)分布都比較集中。位置相關(guān)路由所需的狀態(tài)數(shù)均少于名字路由。對于具體路由方法，PIE存儲節(jié)點(diǎn)狀態(tài)數(shù)最少，主要集中在1～100，HGR節(jié)點(diǎn)狀態(tài)主要集中在500附近，由于鄰域的引入，HGR節(jié)點(diǎn)狀態(tài)的數(shù)量要高于PIE。與基于緊致路由的方案相比，HGR和GRIN分別優(yōu)于NDDisco和Disco。

圖4 平均坐標(biāo)長度

圖5 節(jié)點(diǎn)狀態(tài)概率分布

圖6為不同網(wǎng)絡(luò)規(guī)模下平均節(jié)點(diǎn)狀態(tài)統(tǒng)計(jì)，可以看出，除PIE外，其他路由的節(jié)點(diǎn)規(guī)模均符合理論節(jié)點(diǎn)狀態(tài)數(shù)的分析。GRIN存在一定的波動，主要原因在于不同規(guī)模網(wǎng)絡(luò)可能使用相同數(shù)量的比特位劃分稀疏群組，使得群組內(nèi)節(jié)點(diǎn)數(shù)量出現(xiàn)波動，其有利于支持一定程度的網(wǎng)絡(luò)規(guī)模變化。由于Disco節(jié)點(diǎn)狀態(tài)數(shù)量基數(shù)較大，其波動不明顯。

圖6 平均節(jié)點(diǎn)狀態(tài)

5.3 路徑延展度

路徑延展度反映了路徑被拉伸的程度，是衡量路由可擴(kuò)展性的重要標(biāo)志之一。可擴(kuò)展路由除保證路由表可擴(kuò)展外，還需保證低延展度。圖7分別為真實(shí)網(wǎng)絡(luò)拓?fù)渲形恢孟嚓P(guān)路由和名字路由的延展度累積分布。對于位置相關(guān)路由，HGR是三者中最好的，HGR和PIE的結(jié)果遠(yuǎn)優(yōu)于NDDisco。HGR的最短路徑 (延展度為1的路徑)比例占80%左右，而PIE和 NDDisco分別為75%和20%左右，且HGR的最大路徑延展度不超過2.5。對于名字路由，GRIN優(yōu)于Disco，二者最短路徑所占的比例分別為19%和15%。最壞情況下，GRIN路徑延展度不超過3.5。

圖7 路由路徑延展度累積分布

為進(jìn)一步說明路徑延展度的區(qū)別，對比了平均路徑延展度。圖8為不同網(wǎng)絡(luò)規(guī)模下平均路徑延展度，各方案延展度大小關(guān)系與圖7相同，GRIN平均延展度明顯低于Disco。同一路由方案在不同網(wǎng)絡(luò)規(guī)模下路徑延展度波動很小，HGR和GRIN的平均延展度都小于1.5?？梢?，雖然HGR和GRIN在符合條件的圖中理論延展度上界達(dá)到O(lbn)，但在具體網(wǎng)絡(luò)拓?fù)渲?，延展度上界和平均延展度都能保持較低值，且遠(yuǎn)低于理論值。

圖8 平均路徑延展度

為比較各方案路徑長度，本文統(tǒng)計(jì)了不同網(wǎng)絡(luò)規(guī)模下的平均路徑長度(如圖9所示)和最大路由直徑(如圖10所示)?？梢钥闯?，各路由方案的平均路徑長度的大小關(guān)系與平均路徑延展度的實(shí)驗(yàn)結(jié)果一致，GRIN平均長度優(yōu)于Disco，接近于NDDisco。而對于最大路由直徑，各路由之間的差距不明顯，PIE與HGR完全重合，HGR和GRIN相比于NDDisco和Disco分別具備微弱優(yōu)勢。

圖9 平均路徑長度

圖10 最大路由直徑

GRIN采用雙層名字解析框架，子群組規(guī)?？蓜討B(tài)調(diào)整，通過在子群組中選擇較近節(jié)點(diǎn)進(jìn)行名字解析，利于降低路徑長度。為評價子群組規(guī)模與路徑長度的關(guān)系，隨機(jī)產(chǎn)生并發(fā)布50萬個名字到真實(shí)網(wǎng)絡(luò)拓?fù)?，將子群組對應(yīng)的比特串長度h分別設(shè)置為0、2、4，對每一個名字，隨機(jī)選擇一個節(jié)點(diǎn)作為源節(jié)點(diǎn)進(jìn)行名字解析。圖11為不同子群組規(guī)模下的名字解析路徑長度分布。隨著子群組規(guī)模的增大，解析路徑的跳數(shù)逐漸減小，當(dāng)h=4時，解析路徑長度集中在2～6跳。由于網(wǎng)絡(luò)對象以子群組為單位進(jìn)行發(fā)布和解析，子群組規(guī)模擴(kuò)大會導(dǎo)致解析表增大，因此在解析表規(guī)?？山邮芊秶鷥?nèi)，可盡可能提高子群組規(guī)模。

圖11 路徑長度分布

5.4 可靠性

假設(shè)路由過程中部分節(jié)點(diǎn)失效，而路由表還沒有及時更新，在不考慮備份路徑的情況下會產(chǎn)生一定程度的路由失敗。在真實(shí)AS拓?fù)渲?，隨機(jī)將一定比例的節(jié)點(diǎn)設(shè)為失效狀態(tài)，同時隨機(jī)選擇不同的400萬對節(jié)點(diǎn)對(節(jié)點(diǎn)對中不包括失效節(jié)點(diǎn))路由，并統(tǒng)計(jì)路由失敗率。

從圖12可以看出，HGR和GRIN的路由失效率低于其他3種路由方式，即使在節(jié)點(diǎn)失效率達(dá)到10%的情況下，二者路由失敗率依然低于15%。主要原因在于幾何路由采用貪心方式進(jìn)行路由，路徑不唯一，同時鄰域節(jié)點(diǎn)的加入為路由提供了更多的貪心選擇。位置相關(guān)路由優(yōu)于其對應(yīng)的基于名字的路由，名字解析增加路徑長度，必然導(dǎo)致基于名字的路由失敗概率增大。

6 結(jié)束語

圖12 路由失效率

本文在幾何路由基礎(chǔ)上提出了一種基于位置無關(guān)名字的可擴(kuò)展幾何路由方案GRIN。證明了路由表規(guī)模與網(wǎng)絡(luò)規(guī)模呈亞線性關(guān)系，GRIN名字解析路徑延展度上界與HGR的延展度上界存在線性關(guān)系，并通過仿真驗(yàn)證了GRIN具備可擴(kuò)展、低延展、可靠性等特征。GRIN應(yīng)用范圍廣泛，無論在當(dāng)前Internet還是未來以內(nèi)容為中心的網(wǎng)絡(luò)中都具有巨大的發(fā)展?jié)摿Α２粌H可用于主機(jī)名字空間解決當(dāng)前網(wǎng)絡(luò)IP語義過載引起的可擴(kuò)展、移動等問題，還可應(yīng)用于內(nèi)容名字空間解決ICN的路由可擴(kuò)展問題。

未來工作包括4個方面:第一，研究幾何路由的貪心嵌入理論，本文中名字解析的路徑延展度決定于底層路由，設(shè)計(jì)出具有良好延展度上界的幾何路由是限制名字解析路徑長度行之有效的方法;第二，在名字空間規(guī)模巨大情況下，名字/地址解析信息的存儲和查詢也將影響路由可擴(kuò)展能力，因此研究有效的壓縮存儲和快速查詢方法十分必要;第三，在協(xié)議層次實(shí)現(xiàn)GRIN，分析GRIN協(xié)議的消息負(fù)載;第四，將GRIN應(yīng)用于ICN，該方法是解決內(nèi)容中心網(wǎng)絡(luò)路由可擴(kuò)展問題的可行方法之一。

［1］AHLGREN B，DANNEWITZ C，IMBRENDA C，et al.A survey of information-centric networking［J］.Communications Magazine，2012，50(7):26-36.

［2］CAESAR M，CONDIE T，KANNAN J，et al.ROFL:routing on flat labels ［J］.ACM Sigcomm Computer Communication Review，2006，36(4):363-374.

［3］JACOBSON V，SMETTERS D K，JAMES D，et al.Networking named content ［C］//Proceedings of Conference on Emerging Networking Experiments and Technology，December 1-4，2009，Rome，Italy.New York:ACM Press，2009:1-12.

［4］The Locator/ID Separation Protocol:RFC6830:2013 ［S/OL］.［2015-7-25］.http://www.rfc-base.org/rfc-6830.html.

［5］SINGLA A，GODFREY P B，F(xiàn)ALL K，et al.Scalable routing on flat names［J］.Eprint Arxiv，2013:1-12.

［6］GRITTER M，CHERITON D R.An architecture for content routing supportin the Internet ［C］//ProceedingsofUnix Symposium on Internet Technologies，March 26-28，2001，San Francisco，California，USA.New York:ACM Press，2001:4.

［7］KOPONEN T，CHAWLA M，CHUN B G，et al.A data-oriented(and beyond)network architecture［J］.ACM Sigcomm Computer Communication Review，2007，37(4):181-192.

［8］DANNEWITZ C，KUTSCHER D，OHLMAN B，et al.Network of Information (NetInf)-An information-centric networking architecture［J］.Computer Communications，2013，36(7):721-735.

［9］KLEINBERG R.Geographic routing using hyperbolic space［C］//Proceedings of IEEE International Conference on Computer Communications，May 6-12，2007，Anchorage，Alaska，USA.New Jersey:IEEE Press，2007:1902-1909.

［10］KLEINROCK L，KAMOUN F.Hierarchical routing for large networks:Performance evaluation and optimization［J］.Computer Networks，1977，1(3):155-174

［11］CAESAR M，CASTRO M，NIGHTINGALE E，et al.Virtual ring routing:network routing inspired by DHTs ［J］.ACM Sigcomm Computer Communication Review，2006，36(4):351-362.

［12］THORUP M， ZWICK U.Compactroutingschemes ［C］//Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures，July 4-6，2001，Crete Island，Greece.New York:ACM Press，2001:1-10

［13］HERZEN J，WESTPHAL C，THIRAN P.Scalable Routing Easy as PIE:a Practical Isometric Embedding Protocol ［C］//Proceedings of the 19th IEEE International Conference on Network Protocols，October 17-20，2011，Vancouver，Canada.New Jersey:IEEE Press，2011:49-58.

［14］AHMED R，BARI M F，CHOWDHURY S R，et al.alpha Route:A name based routing scheme for Information Centric Networks ［C］//Proceedings of the IEEE International Conference on Computer Communications，April 14-19，2013，Turin，Italy.New Jersey:IEEE Press，2013:90-94.

［15］DAMBROSIO M，DANNEWITZ C，KARL H，et al.MDHT:a hierarchicalname resolution service forinformation-centric networks ［C］//Proceedings of Conference of the Special Interest Group on Data Communication，August 15-19，2011，Toronto，Canada.New York:ACM Press，2011:7-12.

［16］唐明董，劉建勛，張國清，等.無標(biāo)度網(wǎng)絡(luò)上名字無關(guān)的緊湊路由研究［J］.計(jì)算機(jī)學(xué)報，2014，37(11):2353-2365.TANG M D，LIU J X，ZHANG G Q，et al.Name-independent compact routing in scale-free networks ［J］.Chinese Journal of Computers，2014，37(11):2353-2365.

［17］WANG L，WALTARI O，KANGASHARJU J.Mobiccn:mobility support with greedy routing in content-centric networks ［C］//Proceedings of IEEE Global Communications Conference(GLOBECOM)，December9-13，2013，Atlanta，USA.New Jersey:IEEE Press，2013:2069-2075.

［18］HOFER A，ROOS S，STRUFE T.Greedy embedding，routing and content addressing for darknets.Proceeds of Conference on Networked Systems，March 11-15，2013，Stuttgart，Germany.New Jersey:IEEE Press，2013:43-50.

［19］SUN Y，ZHANG Y，SU S，et al.Geometric name routing for ICN in dynamic world［J］.Communications，2015，12(7):47-59.

［20］CVETKOVSKI A，CROVELLA M.On the choice of a spanning tree for greedy embedding of network graphs ［J］.Networking Science，2013，3(1-4):2-12.

［21］PERLMAN R.An algorithm for distributed computation of a spanning tree in an extended LAN［J］.ACM Sigcomm Computer Communication review，1985，15(4):44-53.

［22］The IPv4 routed/24 AS links dataset ［EB/OL］. ［2015-07-15］.http://www.caida.org/data/active//ipv4-routed-topology-aslinksdataset.xml.

［23］BARABASI A L，ALBERT R.Emergence of scaling in random networks［J］.Science，1999，286(5439):509-512.

Scalable geometric routing scheme based on location-independent names

SUN Yanbin，ZHANG Yu，ZHANG Hongli，F(xiàn)ANG Binxing
School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China

Name-based routing has become one of the hot topics in future network.However，due to the sustained growth of the size of nodes and information，the scalability issue is becoming one of the bottlenecks of name-based routing.As a new type of scalable routing，geometric routing provides both scalable routing tables and low routing paths，but it is difficult to support name-based routing.A universal scalable geometric routing scheme based on location-independent names(GRIN)was proposed.GRIN implemented a hybrid geometric routing(HGR)combining greedy routing with source routing，introduced a distributed name resolution using 2-level sloppy groups.Then the state and the path stretch upper bound of GRIN were analyzed.The simulation results show that GRIN guarantees scalability，low stretch and reliability.It outperformanced other similar routing schemes.

geometric routing，name resolution，name-based routing，scalability

s:The National Basic Research Program of China (973 Program)(No.2011CB302605，No.2013CB329602)，The National Natural Science Foundation of China(No.61202457，No.61402149)

TP301

A

10.11959/j.issn.1000-0801.2016001

2015-07-25;

2015-12-08

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(“973”計(jì)劃)基金資助項(xiàng)目(No.2011CB302605，No.2013CB329602);國家自然科學(xué)基金資助項(xiàng)目(No.61202457，No.61402149)

孫彥斌(1987-)，男，哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院博士生，主要研究方向?yàn)榭蓴U(kuò)展路由和未來網(wǎng)絡(luò)。

張宇(1979-)，男，博士，哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、網(wǎng)絡(luò)測量和未來網(wǎng)絡(luò)。

張宏莉(1973-)，女，博士，哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、網(wǎng)絡(luò)測量和網(wǎng)絡(luò)計(jì)算。

方濱興(1960-)，男，中國工程院院士，哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、并行計(jì)算和分布式系統(tǒng)。