基于位置無關名字的可擴展幾何路由方案

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

(哈爾濱工業大學計算機科學與技術學院，黑龍江 哈爾濱150001)

研究與開發

基于位置無關名字的可擴展幾何路由方案

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

(哈爾濱工業大學計算機科學與技術學院，黑龍江 哈爾濱150001)

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

幾何路由;名字解析;名字路由;可擴展性

1 引言

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

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

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

無論采用直接路由還是名字解析，名字路由都面臨嚴重可擴展問題:一方面，由于互聯網節點和內容數量龐大并持續增長，海量網絡對象將產生龐大的位置無關的名字空間，導致路由表規模過大。同時，由于名字的位置無關性，名字相似的網絡對象很難來自相鄰節點，相同名字的網絡對象也可能分布在多個節點，導致名字聚合難以實現。另一方面，名字的位置無關性使得名字不包含位置和路由信息，導致路由效率低下。為解決以上問題，需要設計一種基于位置無關名字的可擴展路由方案。

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

本文主要研究基于名字解析的路由方案。傳統名字解析方法如名字字典、DNS等，多基于樹型結構或采用傳統DHT方案，存在路徑過長的問題。本文采用革命性的方式，擺脫傳統路由限制，在新型可擴展路由基礎上實現名字路由。

基于貪心嵌入的幾何路由［9］將網絡拓撲貪心嵌入度量空間，為每個節點分配一個坐標，根據坐標距離進行貪心路由。幾何路由作為一種位置相關的可擴展路由方案，具備良好的可擴展特性:路由表只需保存鄰居節點坐標;延展度上界和平均延展度可維持較低水平;任意兩節點之間可能存在多條可用的路徑;同時還支持節點間距離的計算?，F已被用于解決互聯網的路由可擴展問題。目前幾何路由研究多集中在圖的貪心嵌入、坐標壓縮以及降低路徑延展度等方面，屬于位置相關路由的范疇，而對位置無關路由研究很少，即給定一個網絡對象的名字，如何尋找該對象。

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

2 相關工作

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

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

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

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

本文在幾何路由基礎上提出名字路由方案GRIN，對幾何路由具有通用性，能同時滿足可擴展、位置無關、低延展度和可靠性等需求，不同情況下，其節點路由表項分別為）或當底層路由路徑延展度上界為O(k)時，名字解析的路徑延展度上界達到O(2k+1)。

3 基于位置無關名字的幾何路由

GRIN可分為位置相關路由和名字解析兩部分。位置相關路由處于物理網絡拓撲，采用混合幾何路由方案為名字解析和節點間通信提供路由支持;名字解析處于邏輯的名字空間拓撲，將網絡對象的名字映射為位置。下面首先介紹HGR，然后討論基于雙層稀疏群組的名字解析框架。

3.1 混合幾何路由

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

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

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

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

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

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

等距嵌入保證圖嵌入度量空間后不發生扭曲形變，其滿足貪心嵌入的條件;貪心嵌入則是為了將圖嵌入度量空間，使節點之間仍滿足貪心條件，進而保證貪心路由100%可達。

Kleinberg［9］證明了圖G的生成樹到某度量空間的貪心嵌入，即G到該度量空間的貪心嵌入。為將拓撲圖貪心嵌入度量空間，HGR首先提取生成樹，然后將生成樹等距嵌入度量空間，最后結合源路由和貪心路由實現節點間通信。因此，HGR可分為3部分:生成樹提取、生成樹等距嵌入和混合路由。

3.1.1 生成樹提取

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

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

3.1.2 生成樹等距嵌入

對于生成樹 T 中的節點 O，其坐標為(o1，o2，…，ok-1)，S為 O 的子節點集合，S=｛v0，v1，…，vs-1｝，s為子節點數量，s=｜S｜。

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

圖1 生成樹貪心嵌入

當父節點坐標為0時，子節點坐標完全來自編碼，按照式(4)可獲得節點坐標;當只有一個子節點時，子節點坐標完全來自父節點，無需對其編碼，按照式(3)可獲得節點坐標。初始時，根節點坐標設為0，經過一次生成樹的遍歷，可完成等距嵌入。

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

樹嵌入之后，根據lp范數空間的度量公式可得到圖G中的節點坐標距離。將X作為具有lp范數的k維度量空間，對于?x，y∈X，在 X 上的度量(坐標距離)d(x，y)=｜x-y｜p，可表示為:

圖 G上任意兩點 u、v，其坐標分別為 Cu和 Cv，根據 l∞空間度量公式，則其坐標距離可表示為:

3.1.3 混合路由

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

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

鄰域可由集中式或分布式方法獲得。集中式方法，每個節點根據網絡拓撲計算以自身為根節點的最短路徑樹，然后選擇每個群組中距離該節點最近的前k'個節點作為鄰域節點;分布式方法，每個節點從其鄰居節點獲得鄰居路由表中的鄰域信息，建立自己的鄰域。當某節點鄰域發生變化時，將變化的路由表項通知其鄰居節點，其鄰居節點通過判斷是否為某群組前k'個最近節點進行相應更新。

HGR整體采用貪心路由，局部采用源路由。當節點u收到目的節點為v的數據分組時，路由可分兩種情況討論:

· 若u為目的節點v，則路由結束;

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

數據分組通過源路由沿最短路徑達到w，w重復以上過程，直到到達目的節點。當源路由部分路徑失效時，則返回前一貪心節點，通知其路徑失效，重新貪心以保證路由成功到達。

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

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

3.1.4 HGR與PIE

HGR繼承了PIE的多個優點:路由存在多條貪心路徑，能盡量保證部分鏈路中斷或節點失效時，路由仍可達;坐標距離為整數間的加減運算，坐標運算簡單;支持加權圖上的路由。

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

3.2 名字解析框架

GRIN名字解析與底層路由相互結合，采用稀疏群組［5］思想構建雙層名字解析框架，充分利用底層物理拓撲中的節點坐標及鄰域信息，有效限制名字解析時的路徑長度。

3.2.1 雙層名字解析框架

根據節點名字，稀疏群組可將網絡節點分為多個相互獨立的部分，形成邏輯的名字空間拓撲。每個節點的名字被散列成唯一的二進制串。由于名字結構對散列沒有影響，因此，GRIN可同時支持扁平名字和層次名字。二進制串前k bit(k＜lbn)相同的節點可作為一個群組，網絡被劃分為2k個群組。如圖2所示，GRIN將網絡分為物理網絡拓撲和邏輯名空間拓撲，在網絡拓撲中節點被分為3個類(黑、白、灰)，每一類在名空間拓撲中代表一個群組，其中名空間拓撲中的橢圓即代表白色節點組成的群組。

圖2 雙層稀疏群組

對于群組內部節點，可繼續按照稀疏群組的方法，根據二進制串的前k～k+h bit再分組，形成子群組。圖2名字空間拓撲中橢圓上相同顏色的節點為一個子群組?？梢愿鶕W絡對象的數量動態調整h的值，以便提高名字解析的效率和頑健性。當h=0時，只有一個子群組;當時，幾乎每個節點都可作一個子群組。由此，由群組和子群組構成了GRIN的雙層名字空間拓撲。

名字空間拓撲上的通信由群組間通信、子群組間通信以及子群組內部通信3部分組成。HGR的鄰域在通信過程中發揮重要作用。由于鄰域節點分布在不同群組，可將相互獨立的群組關聯起來，節點可通過其鄰域與其他群組相連，繼而實現了群組間通信。在群組內部，節點可建立子群組表，保存每個子群組中距該節點最近(坐標距離)的前l個節點的坐標信息，通過這些節點與其他子群組相連。同時，每個節點保存其所在子群組的所有節點的坐標信息，直接通過幾何路由實現子群組內部節點的通信。以上3種情況，任意兩節點間的通信都由底層HGR支持。

3.2.2 名字發布和解析

網絡對象的發布以子群組為單位。當網絡對象的名字/地址映射信息到達其所在子群組的某一節點時，該節點將映射信息廣播到子群組內的所有節點，每個節點保存一份映射信息。其優勢在于名字解析時，只需找到該子群組中任意節點即可完成解析，可有效減小名字解析的路徑長度。

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

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

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

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

GRIN的名字解析方案可有效降低名字解析的路徑延展度。在名字空間拓撲上，GRIN至多兩步就可完成名字解析:首先查詢鄰域節點;然后通過鄰域節點查詢名字所在的子群組節點。GRIN名字解析雖然建立在名字空間拓撲，但其將名字空間拓撲和物理拓撲更緊密的結合。名字空間拓撲可利用鄰域以及坐標距離保證兩步查詢的路徑為最短或近似最短。同時保證若查詢節點周圍存在最優的名字解析節點，則有很大概率被找到。

4 分析

4.1 節點狀態

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

GRIN和HGR的名字解析表規模和路由表規模與策略選擇有關。若選擇名字/地址解析信息數量最優，則將每個節點代表一個子群組。假設群組數量為O(x)，子群組數量達到最大值O(n/x)，由于鄰域數量與群組相等，則GRIN需要保存的路由信息為O(x+n/x)。當時，O(x+n/x)達到最優，此時，HGR和GRIN的路由表項規?？稍O置為名字解析表規模近似為O(B/n)(B為網絡對象數量)。

若選擇路由表規模最優，假設群組數量、子群組數量、子群組內部節點數量分別為O(x)、O(y)、O(z)，則路由表規模為 O(x+y+z)，根據均值不等式，當x、y、z均為時，HGR和GRIN路由表規模達到最優，為此時名字解析表規模為

4.2 路徑延展度上界

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

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

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

根據三角不等式 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實現分析

GRIN實現方案簡單可行，主要包括兩種方案，可分別借鑒鏈路狀態路由協議和距離向量路由協議。前一種方案可分為兩步:節點通過鏈路狀態廣播LSA將其周圍的拓撲信息廣播給其他節點，每個節點建立鏈路狀態數據庫LSDB，最終得到一份完整一致的網絡拓撲;基于網絡拓撲，各節點選擇一個相同的根節點構建生成樹，并計算出自己的坐標、鄰域節點及所在的群組和子群組。后一種方案可分為3步:采用SPF協議構建生成樹，通過一次樹遍歷獲取網絡規模n，并通知給各節點;采用類似距離矢量算法，為每個節點尋找鄰域節點;通過鄰域節點獲得群組以及群組內部節點信息。

5 仿真結果

本文基于C++設計了一種靜態路由模擬器。為支持大規模模擬，采用集中式方法設計簡化的模擬器，模擬器主要包括拓撲類和節點類。拓撲類保存所有節點，負責拓撲生成、路由表構建、名字發布和解析等。節點類保存節點ID、路由表、解析表、鄰居鏈表以及統計信息等，并負責轉發報文。拓撲生成主要由文件讀取和由拓撲模型 (如ER模型、BA模型、GLP模型等)生成，拓撲生成過程中，每個節點被隨機分配一個名字，并通過SHA-1將名字散列為128 bit的比特串。路由表構建需要完成生成樹提取、貪心嵌入、鄰域以及子群組獲取，均可基于全局拓撲信息實現。名字發布/解析時，先設置源節點以及要發布/解析的名字，然后可調用各節點的轉發方法實現路由轉發。根據名字散列以及路由信息匹配選擇轉發的下一跳，并保存相關統計信息。下一跳節點繼續進行匹配轉發，直到達到解析節點，將發布信息存入解析表或根據解析表查詢對應的解析信息。

分別在真實網絡拓撲和虛擬網絡拓撲進行仿真。實驗中網絡拓撲均作為無向連通圖。真實網絡拓撲為CAIDA［22］在2012年1月采集的10 683個節點的Internet AS拓撲數據集;模擬網絡拓撲采用無標度網絡的經典模型 (BA模型)［23］生成，設置其初始節點數為 3，平均節點度為 4。

Disco為目前較好的名字路由，基于主機名字空間設計，為與Disco及其底層路由NDDisco比較，采用與Disco相同的路由表規模并將子群組數量設置為最大，此時，GRIN與基于主機名字空間的路由類似。分別從坐標長度、節點的節點狀態、路徑延展度以及可靠性4個方面分析HGR和GRIN。

5.1 坐標長度

分別在真實拓撲和模擬拓撲測量等概率哈夫曼編碼和不等概率哈夫曼編碼產生的坐標長度，圖3為真實拓撲下坐標長度分布，不等概率編碼坐標長度集中在10～15，平均長度為14.94，而等概率編碼坐標長度則集中在15～20，平均長度為16.17。圖4為模擬拓撲在不同網絡規模下的坐標平均長度，x軸取對數?？梢钥闯?，平均坐標長度與lbn近似呈線性關系，采用不等概率編碼的平均坐標長度明顯優于等概率編碼的坐標長度。

圖3 節點坐標長度分布

5.2 節點狀態

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

圖4 平均坐標長度

圖5 節點狀態概率分布

圖6為不同網絡規模下平均節點狀態統計，可以看出，除PIE外，其他路由的節點規模均符合理論節點狀態數的分析。GRIN存在一定的波動，主要原因在于不同規模網絡可能使用相同數量的比特位劃分稀疏群組，使得群組內節點數量出現波動，其有利于支持一定程度的網絡規模變化。由于Disco節點狀態數量基數較大，其波動不明顯。

圖6 平均節點狀態

5.3 路徑延展度

路徑延展度反映了路徑被拉伸的程度，是衡量路由可擴展性的重要標志之一?？蓴U展路由除保證路由表可擴展外，還需保證低延展度。圖7分別為真實網絡拓撲中位置相關路由和名字路由的延展度累積分布。對于位置相關路由，HGR是三者中最好的，HGR和PIE的結果遠優于NDDisco。HGR的最短路徑 (延展度為1的路徑)比例占80%左右，而PIE和 NDDisco分別為75%和20%左右，且HGR的最大路徑延展度不超過2.5。對于名字路由，GRIN優于Disco，二者最短路徑所占的比例分別為19%和15%。最壞情況下，GRIN路徑延展度不超過3.5。

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

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

圖8 平均路徑延展度

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

圖9 平均路徑長度

圖10 最大路由直徑

GRIN采用雙層名字解析框架，子群組規模可動態調整，通過在子群組中選擇較近節點進行名字解析，利于降低路徑長度。為評價子群組規模與路徑長度的關系，隨機產生并發布50萬個名字到真實網絡拓撲，將子群組對應的比特串長度h分別設置為0、2、4，對每一個名字，隨機選擇一個節點作為源節點進行名字解析。圖11為不同子群組規模下的名字解析路徑長度分布。隨著子群組規模的增大，解析路徑的跳數逐漸減小，當h=4時，解析路徑長度集中在2～6跳。由于網絡對象以子群組為單位進行發布和解析，子群組規模擴大會導致解析表增大，因此在解析表規?？山邮芊秶鷥?，可盡可能提高子群組規模。

圖11 路徑長度分布

5.4 可靠性

假設路由過程中部分節點失效，而路由表還沒有及時更新，在不考慮備份路徑的情況下會產生一定程度的路由失敗。在真實AS拓撲中，隨機將一定比例的節點設為失效狀態，同時隨機選擇不同的400萬對節點對(節點對中不包括失效節點)路由，并統計路由失敗率。

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

6 結束語

圖12 路由失效率

本文在幾何路由基礎上提出了一種基于位置無關名字的可擴展幾何路由方案GRIN。證明了路由表規模與網絡規模呈亞線性關系，GRIN名字解析路徑延展度上界與HGR的延展度上界存在線性關系，并通過仿真驗證了GRIN具備可擴展、低延展、可靠性等特征。GRIN應用范圍廣泛，無論在當前Internet還是未來以內容為中心的網絡中都具有巨大的發展潛力。不僅可用于主機名字空間解決當前網絡IP語義過載引起的可擴展、移動等問題，還可應用于內容名字空間解決ICN的路由可擴展問題。

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

［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，FALL 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］唐明董，劉建勛，張國清，等.無標度網絡上名字無關的緊湊路由研究［J］.計算機學報，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，FANG 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

國家重點基礎研究發展計劃(“973”計劃)基金資助項目(No.2011CB302605，No.2013CB329602);國家自然科學基金資助項目(No.61202457，No.61402149)

孫彥斌(1987-)，男，哈爾濱工業大學計算機科學與技術學院博士生，主要研究方向為可擴展路由和未來網絡。

張宇(1979-)，男，博士，哈爾濱工業大學計算機科學與技術學院副教授，主要研究方向為網絡安全、網絡測量和未來網絡。

張宏莉(1973-)，女，博士，哈爾濱工業大學計算機科學與技術學院教授、博士生導師，主要研究方向為網絡安全、網絡測量和網絡計算。

方濱興(1960-)，男，中國工程院院士，哈爾濱工業大學計算機科學與技術學院教授、博士生導師，主要研究方向為網絡與信息安全、并行計算和分布式系統。