基于位置關聯Chord的名址分離映射系統

穆晏如，江凌云

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

信息技術飛速發展的20年間，網絡技術和應用的更新迭代影響著現代信息社會。其中，互聯網以其開放透明、資源共享等特性分布最廣，是現代通信網絡的重要組成部分，以其分層結構為藍本的新型網絡也在各領域發揮著重要的作用。但隨著互聯網與人類社會生活的深度融合，傳輸和存儲的成本降低，信息爆炸式的增長，互聯網應用層出不窮，人們對于互聯網的使用需求已不僅僅是“盡力而為”的端到端傳輸。傳統的互聯網在應對高移動等新型應用場景時暴露出許多不足，引發了未來網絡體系及其核心技術的研究熱潮。

IP地址既標識網絡實體的身份，也標識其在網絡中的位置，這樣的設計為早期的互聯網“會話”提供了極大的便利。但隨著互聯網用戶激增、大量移動設備接入，IP地址的雙重身份導致核心路由器路由表項急劇擴張，傳統的移動解決方案Mobile IP流量繞行和切換延時的弊端凸顯。為了解決這些問題，Cisco提出了名址分離的思想[1]。通過對可尋址網絡元素的實體(例如網絡設備、內容、服務)進行統一的身份標識，在IP層之上替代IP地址成為“瘦腰”部分來更好地支持網絡的移動性。將網絡實體的身份與位置解耦后，網絡實體的身份不會隨著位置的變化而改變，名稱與地址不再是一一對應的關系，而是可注冊、可更改、可查詢的靈活綁定，所以需要設計一個映射系統來管理名稱和地址的綁定，為網絡提供解析服務。

地址采用層次化的編址方式能夠有效地實現路由表項的聚合，大多數的研究中仍然沿用IP地址。身份標識采用扁平化的名稱空間可以實現自認證，同時可以避免名稱空間的內部結構對移動性的限制。DNS利用域名的層級組成樹狀目錄結構，來完成域名到IP地址的解析查找，所以不適用于扁平化標識與地址的映射。此外，DNS主要通過大量的緩存來提高解析性能，在移動場景下，名稱與地址的綁定緩存失效過快，而DNS的更新傳播需要一天或更長時間，這樣會導致服務器的負載增加，查詢的時延提高。所以無法沿用DNS構建名稱與地址的映射系統。

該文提出了一種基于位置關聯Chord的名址分離映射系統，將映射綁定信息分級管理，最大限度地減少更新流量對網絡的影響，同時在Chord算法中嵌入位置信息便于快速查找，解決Chord物理網絡和邏輯網絡的失配問題。

1 相關工作

映射解析服務的理想狀態是能夠在任何時間任何地點快速準確地獲得用戶查找的網絡實體的位置信息，為實現這一目標，主流的研究思路是將標識與地址的綁定信息復制后尋找合適的位置托管。這種思路存在兩個技術難點，一是綁定信息的副本越多，用戶越能夠在就近的位置查詢到服務的位置，但是副本過多，綁定信息的更新流量將占用大量的網絡帶寬，且不易同步，導致較高的誤查詢率。二是什么位置適合托管綁定信息。基于該思路，許多研究組織進行了很多的嘗試和實踐。

主流的方案分為兩大類，一類是非結構化副本放置方案，包括隨機定位副本放置的DMap[2]，關注需求的動態副本放置方案Auspice[3]，以及地理感知分層聚合的GMap[4]。這類方案復雜度較高，容易占用大量的網絡資源，而且需要借助緩存策略和搜索方法。另一類是結構化副本放置方案，主要是借助于分布式哈希表(distributed hash table，DHT)的思想，按照一定的規則分割映射表，每個存儲節點維護一部分的數據和鄰居信息。其中，LISP—DHT[5]就是利用DHT的組織和查詢功能實現映射信息管理和解析的分布式系統，基于可聚合的層次ID，將含ID前綴的最大值作為一個域的標識，每個域選取一個權威服務器組建Chord[6]環，借助Chord協議來實現域間的查找。

Chord協議是一種經典的P2P協議，只執行一個操作：給對象分配一個Chord ID，將其映射到一個哈希環上。在映射系統中，對象分為兩類，服務器節點和需要存儲的名稱和地址綁定條目。將名稱的ID映射到哈希環上后，順時針找到最近的服務器節點，將自己的綁定條目存儲到該服務器上。每個節點會維護一個Finger表，相當于哈希環上的路由表，其中記錄了鄰近節點的信息便于查詢和路由。Chord可以實現負載均衡，在節點離開和新節點加入時能保持系統穩定性。但由于Chord是基于ID的哈希值來構建環結構，與底層的物理網絡脫離，會導致出現物理上的最短距離和邏輯上的最短距離不一致的現象[7]。基于這個問題，該文提出的方案結合兩級映射的思路，在Finger表中添加網絡號，將物理位置信息嵌入邏輯網絡中，同時改進了搜索方法，能夠有效降低查找時延。

2 基于位置關聯Chord的名址分離映射系統

2.1 總體設計思想

基于位置關聯Chord的映射系統修改了LISP—DHT系統，讓域內的所有解析服務器都映射到Chord環上，而不是只有一個權威解析服務器，這樣可以降低單點失效的風險。如圖1所示，下層是以地理區域劃分的物理網絡，上層為Chord結構。名址分離映射系統與域名解析系統最大的不同就是，域名與IP地址的綁定關系相對固定，少有變動，而名稱與地址的綁定關系正好相反。

圖1 映射系統架構

在實際的移動應用場景中，局域移動仍然占據了很高的比例[8]。由于區域網絡劃分之后網絡地址(network address，NA)固定不變，所以采用域內的綁定、域間的綁定方式將綁定條目的更新范圍盡可能縮小。

名址分離映射系統設置副本是為了增加查詢時鄰近命中的概率，增加副本的個數必然可以增大命中的概率，但是設備移動帶來的綁定條目的更新會反過來限制查詢的效率。當移動大多發生在地理區域內部時，如果區域內部映射服務器數量有限，可以采用泛洪的方式將的綁定關系傳遞給所有的映射服務器(如果區域范圍很大、映射服務器很多，可以另行使用DHT組織，與總體架構不沖突)。同時的綁定關系是相對固定的，可以在域間適當地增加副本的個數。

當的綁定條目向域外尋找托管位置時，ID通過哈希函數固定地映射到環上的同一點，例如K10，如果沒有其他服務器節點的加入或退出，K10將順時針地托管在N17上。當另外的設備發起查詢時，如果在域內的映射服務器中沒有查找到，會通過同樣的哈希函數計算出K10找到N17。而當這臺設備在跨域移動后，的綁定條目仍然會映射到K10，在N17處托管。所以N17可以通過統計該ID的查詢率和跨域更新率來動態地調整域外副本的個數。

DHT中物理網絡與邏輯網絡的“失配”問題會造成查詢時“繞遠路”[9]，例如圖1中N4與N23在同一個地理區域網絡內，彼此只相隔一跳的距離，但是在Chord環上需要沿順時針進行遞歸查找。為了解決這個問題，對Chord節點的finger表進行了修改，如表1所示。

表1 Chord節點路由表結構

由于映射服務器所屬的網絡地址是固定不變的，所以通過在節點路由表項中增加后繼節點的網絡地址，來聚合Chord節點路由表，同時跳出邏輯網絡的遞歸搜索來避免“繞遠路”的問題。

2.2 工作機制

(1)注冊：設備新入網時，需要向最近的映射服務器注冊自己的名稱地址綁定信息，服務器收到后，向網絡中部署副本，過程如圖2所示。①終端連接區域內路由器，得到分配的IP地址，成功入網。②該路由器向最近的映射服務器發送分組消息，注冊的綁定信息。映射服務器收到消息后，將該信息存儲在本地緩存中，并向區域內部的映射服務器泛洪發送(圖中⑤)。③映射服務器對ID進行哈希計算，得到ID在哈希環上的位置K10，修改的綁定信息為。④沿順時針找到節點N17，將的信息存放在N17。注冊流程中的綁定消息不設置計時器，當終端離開該區域，由連接的路由器主動向映射服務器發送刪除報文，該服務器經過同樣的流程發送公告。

圖2 映射系統注冊過程

(2)查詢解析：當一臺設備初次連接該ID標識的設備時，需要向鄰近的映射服務器發起解析請求，映射服務器接收到請求后查找本地緩存，如果存有ID的條目則返回IP，如果沒有，開始查詢，流程如圖3所示。

圖3 映射解析流程

步驟1：該映射服務器向本域內的其他映射服務器發起查詢請求，如果存有，則返回結束解析過程，沒有，轉步驟2；

步驟2：計算hash(ID)，得到K10，在本域內查找邏輯網絡中距離K10最近的服務器節點，本例中為N5，轉步驟3；

步驟3：遍歷N5的Chord節點路由表，逐條搜索，如果命中(即如果存在N10，則K10應當存儲在N10上)，則返回，否則在整張表中找到與K10邏輯最接近的服務器節點，并返回該節點的網絡地址RNA(Relay NA)，訪問RNA，從RNA中查找在邏輯網絡中距離K10最近的服務器節點，重復步驟3，直到查找到托管K10的節點N17為止，從N17處獲取并返回，轉步驟4；

步驟4：從NA中獲取，返回查詢結果，緩存在本機并設置TTL，結束解析過程。

(3)移動更新：當設備在區域內移動時，的綁定關系會發生變化，離開入網的路由器時，由路由器主動地向映射服務器注銷該綁定條目。在區域內的另一處重新入網時，同樣由接入路由器負責向映射服務器注冊，映射服務器在區域內泛洪廣播該綁定條目，因為的綁定關系沒有發生變化，所以不向域外發送。當設備跨域移動時，離開本區域時由接入路由器主動申請注銷綁定，然后在新的區域內按照(1)的步驟重新注冊入網。

(4)域間緩存：設置綁定信息副本的目的是為了提高鄰近命中的幾率，當大量的域間解析請求到達N17查詢K10時，說明域外對于此ID的連接需求較大，N17可以沿Chord環順時針傳送的綁定信息，增大緩存面積，便于更多的查詢請求在鄰近命中。同時為發送的副本信息設置TTL。當大量的K10更新請求到達N17時，表明此ID處于較高頻率的移動狀態，應該適當減少副本的TTL，而且如果再向Chord環中持續地增加副本個數會影響查詢一致性，導致查詢解析出錯。所以域外的副本個數應該與此ID的查詢率成正比，與此ID的更新率成反比。設此ID為i，i的域外副本個數為r，查詢率為qi，更新率為ui，則關系如式(1)所示，其中μ是調控參數。

(1)

2.3 查詢效率分析

設映射服務器節點數為N，邏輯網絡為L={l1,l2,…,li,…,lN},1≤i≤N。其中li代表Chord環上的節點，且l1≤l2≤…≤li≤…≤lN，即l2是l1的后繼節點，lN是l1的前驅節點，其他關系類似。設物理區域網絡的個數為M，M≤N，物理網絡為G={g1,g2,…,gj,…,gM},1≤j≤M。其中gj表示一個網絡的網絡地址NA。由于哈希函數是隨機映射關系，所以不失一般性，假設服務器節點均勻地分布在各區域網絡中，每個區域網絡中有n個服務器節點，其中n=N/M。在不考慮域間緩存的情況下，假設lj1(1≤j1≤N)查找存儲Kα映射綁定條目的服務器節點，lj1在物理區域pj上，其中pj上的邏輯網絡節點集合為{lj1,lj2,…,ljn}?L,lj1≤lj2≤…≤ljn。根據查詢解析流程可得，如果Kα在pj中沒有命中托管服務器節點，則會搜索ljn的Chord路由表，查找與Kα最鄰近的節點所在的物理網絡，并重復以上流程。Chord算法中指出，一個節點對順時針方向上越靠近自己位置的Chord區域，了解的節點數目越多[10]。所以可得，整個查找Kα的過程中，物理區域網絡上的路徑是單向的[11]，而且是可以收斂的，從這個方面來說，位置關聯Chord優于原始Chord。

(2)

3 仿真測試

該文采用OMNET++[13]進行仿真實驗，包括在該環境下開發的INET框架[14]和Oversim框架[15]，使用C++語言編寫。OMNET++是一個離散時間仿真環境，主要應用于模擬通信網絡領域，是廣泛普及的網絡仿真平臺[13]，因其擁有豐富的GUI能夠清楚地顯示網絡拓撲和連接信息而被廣泛使用。OMNET++提供了用于描述實際系統結構的工具，包括分層次嵌入式模塊、靈活的模塊參數等。模塊可以復用、可以嵌套，嵌套的深度沒有限制，這些都可以通過NED[13]語言描述。INET框架是一個開源的通信網絡仿真包，由密歇根大學開發的一個AS級拓撲產生器，該框架包括從物理層到應用層的網絡協議，主要用于互聯網的仿真[15]。Oversim是建立在INET框架上的P2P協議仿真框架，包含了Chord、Pastry協議的實現，具有靈活性、可擴展性、不同的路由模式等特點[15]。

設置區域個數為20，依次增加映射服務器節點規模，可得平均查詢路徑長與平均查詢時延，如圖4、圖5所示。與理論分析結果一致，隨著N的增加，平均查詢路徑長逐漸增大，而且查詢時延與查詢的跳數相關，也呈增長趨勢。由于位置關聯Chord在邏輯節點的路由表中增加了物理拓撲的信息，域間的查詢是單向的，提高了查詢效率。從圖4中可以看出，實際的位置關聯Chord的查詢路徑長與理論值存在一定的差距，這是由于在理論分析時，默認域內的服務器節點均勻地分布在Chord環上，這在實際的應用環境中是比較難達到的理想狀態。

圖4 M=20平均查詢路徑長測試

圖5 M=20平均查詢時延測試

設定系統中映射服務器節點個數為2 000，逐漸增加區域的個數，可得映射解析性能，如圖6、圖7所示。從圖中可以看出，LISP-DHT方案隨著區域個數的增加，查詢路徑長沒有太大的變化，但查詢會有更大的概率跨域進行，域間的傳輸時延比域內的傳輸時延大40 ms，所以查詢時延有增加的趨勢。位置關聯Chord方案隨著區域個數的增加，每個節點路由表中保存的區域相關信息更多，更加能夠快速地命中映射條目，提高系統查詢解析的性能。

圖6 平均查詢路徑長測試

圖7 平均查詢時延測試

4 結束語

設計了一個基于位置關聯Chord的名址分離映射系統，通過在邏輯網絡中節點的路由表內添加物理網絡的拓撲信息，改變了Chord環的遞歸查找過程，在查詢時一個物理網絡只經過一次，有效地避免了邏輯網絡與物理網絡失配導致的“繞遠路”問題。此外，名稱與地址的綁定關系分域內域外兩級管理，域內直接綁定IP地址，域外更換綁定信息為名稱與網絡地址，通過增加一跳的查詢將綁定信息更新范圍盡可能地縮小在域內。采用查詢率與更新率的比值動態調控緩存個數，維持在一定更新成本下的查詢效率。并且通過理論分析和仿真實驗證明了此映射系統的性能優于LISP-DHT。提高的查詢性能是通過增加路由表信息換來的，表項可以聚合，不會對存儲造成壓力，但是會對系統的可擴展性造成一定的影響，希望后續的研究工作能夠盡量地解決這一問題。