基于名的平坦路由

裘正定 熊 軻

摘要:路由是信息網絡的基礎,分布于網絡的各個層面。現有互聯網采用了基于IP地址的網絡層路由技術和基于域名解析的域名服務器(DNS)應用層路由技術。由于IP地址和域名的結構化特點和身份位置緊耦合特點,使得互聯網面臨路由可擴展性、安全性、資源服務遷徙移動支持性差等嚴峻問題。基于名的平坦路由采用了平面化的身份命名方式,實現了身份位置分離,可有效提高網絡路由的可擴展性、可配置性、安全性、服務支持的魯棒性、資源移動的支持性等。

關鍵詞:網絡路由;平坦路由;路由體系

Abstract: Routing plays a basic role in information networks, and it works on each layer of networks. Current Internet adopts IP-based network-layer routing and name resolution-based Domain Name System (DNS) application-layer routing. With the structured IP addresses and domain names, as well as with the closely coupled identification and location of both IP and domain names, the Internet are now facing several intractable problems such as bad routing scalability, weak security, weak ability of supporting resource migration and moving. Name-based flat routing uses flat names for the identifications, which achieves the splitting of identification and location. The name-based flat routing can effectively improve network routing scalability, configurability, security, robustness of service providing and ability of supporting resource migration and moving.

Key words: network routing; flat routing; routing system

路由技術是分組網絡的核心支撐技術,目的是為分組包確定一條從通信源端到目的端的傳輸路徑,用以解決多跳連接邏輯設備或物理設備間的可達性問題。路由技術分布于網絡的各個層面。應用層的域名服務器(DNS)技術、P2P技術、內容傳送網絡(CDN)路由技術,疊加于IP層以上的Overlay路由技術,網絡層的IP路由技術以及鏈路層的以太網橋技術[1]等都屬于網絡路由的范疇。網絡路由性能的優劣直接決定著網絡通信能力和業務質量的高低。

隨著互聯網規模的不斷擴大,網絡層的路由可擴展問題日益嚴重,已成為制約網絡進一步發展的重大隱患。網絡的移動、多家鄉、流量工程等導致路由表前綴的聚合能力越來越差,雖然硬件的處理速度在不斷提高,但相對網絡的發展和路由表的增長卻明顯顯得力不從心。2009年7月的統計顯示,核心網BGP路由表的前綴數目已接近30萬條,而且仍在高速增長[2]。除此之外,現有路由機制對移動的支持能力也很差。2009年的調查顯示全世界范圍內已有40億移動用戶,其中高于20%的用戶開通了數據業務。未來的手機、個人數字助理(PDA)等手持終端的功能會愈來愈強,開通互聯網數據業務量也會隨之飛速增加。這將給網絡帶來前所未有的挑戰。安全性問題是互聯網的又一嚴峻問題,而且日益緊迫。雖然網絡已引入入侵檢測、防火墻等技術,但互聯網的安全性問題仍未得到有效解決。這些問題都與路由體系緊密相關,僅在基于IP的現有路由體系上進行小的修補,難以很好解決互聯網的這些問題。

為方便用戶的使用,現有網絡在應用層引入了域名機制來標志網絡資源。采用DNS將資源與地址進行對應,達到網絡資源共享的目的。由于域名相對IP地址更加方便用戶的記憶,因而,DNS得到了迅速發展,成為了互聯網上最大的解析系統。然而,隨著網絡業務量的不斷增長,基于樹狀結構的DNS逐步暴露出一些致命缺點,如不支持數據移動和復制[3],域名解析系統魯棒性不強等問題,并引發了人們對互聯網域名解析與資源查找系統的重新思考[4-7]。

與路由密切相關的就是網絡節點或資源的地址定義,不同的地址定義需要不同的路由運行機制與之相配合以實現網絡路由功能。研究分析發現,無論是應用層的域名解析系統還是網絡層的IP路由技術都具有一個共同特點,那就是它們都是基于層次化、結構化的網絡實體地址。IP路由基于結構化的IP地址,DNS基于層次化的域名定義。這些結構化的地址定義方式給網絡早期的發展帶來了很多實現好處,而今卻成為網絡所遇問題難以解決的根本性原因。與結構化地址相對的便是平坦(面)化的地址定義方式。平面化地址打破了傳統的結構化的地址定義,隨之也產生了與現有路由機制大相徑庭的路由方式。近年來,很多研究者的研究都體現了平坦路由的思想。平坦路由打破了現有基于結構化地址的路由方式與網絡體系機構,為有效解決現有路由難以解決的問題提供了的新的研究思路和方法,已成為新一代路由研究的熱點方向之一。

1 現有路由存在的問題

1.1 網絡層路由存在的問題

(1)路由可擴展問題

因為IP地址具有身份與位置的雙重特性,因而現有互聯網的可擴展性存在一個基本假設即IP地址按網絡拓撲分配或按地理位置分配。身份特性要求IP地址保持穩定性和唯一性,而位置特性要求IP與網絡拓撲地址相對應。因而,網絡要支持移動性、多家鄉等就會出現IP的兩個屬性沖突的問題,這造成路由表難以很好聚合。造成IP難以聚合另外一個原因是,現有IP的分配很不合理。美國作為國際互聯網的領頭軍,獲得了70%以上的IP資源。眾所周知,美國麻省理工學院一所大學擁有的IP地址比中國全國的擁有量還多。其他國家為使用互聯網不得不引入其他技術,如網絡地址轉換(NAT)技術,這造成網絡的復雜性越來越高,亦與身份屬性要求的唯一性相矛盾。

(2)地址分配不靈活

正是因為IP的雙重屬性和IP資源擁有的“貧富”差異巨大,造成IP地址的分配受限很多,且很多情況下的分配都不合理。這反過來又制約了網絡的發展和路由的擴展性。

(3)IP地址的配置方便性差

對于網絡和計算機知識較缺乏的用戶,要實現上網,在獲得IP地址后,要進行IP的配置無疑是一件很不方便的事情。盡管因引入了動態主機配置協議(DHCP),簡化了用戶的操作,卻給網絡帶來了很大的負擔,而且DHCP打破了一個身份對應唯一一個終端的假定。

(4)移動性支持差

現有網絡中,因為IP具有地址信息,終端在移動后不得不改變地址以實現通信,由于IP的身份與位置緊耦合,將導致移動中終端的身份不得不發生變化。而身份的變化會導致通信的中斷,為實現IP網絡的移動性,不得不引入大量的操作來管理和實現轉交地址與原IP地址的轉換。

(5)安全性差

由于IP地址同時包含身份與位置信息,網絡的惡意竊聽者都可以根據一個IP地址獲得其身份信息和拓撲位置信息。

1.2 應用層路由存在的問題

應用層的DNS系統由于其設計初期考慮的比較簡單,隨著用戶數量的飛速攀升和數據移動性的增強,在當前的應用中亦逐步暴露出很多致命問題。

(1)DNS管理權限的不平衡性

DNS根服務器扮演了十分重要的角色,所有本地DNS服務器不能解析的域名解析請求都需要被送到DNS根服務器進行處理。由于這些DNS根服務器的管理權與控制權在美國政府的手中,美國可以對DNS根服務器中的ROOTZONE文件的記錄進行修改,從而使得一些國家從互聯網世界中消失成為可能。

(2)配置復雜,魯棒性、安全性差

DNS需要手動配置,隨著系統的復雜程度逐步提高,配置出錯的概率以不斷增高,給網絡的可靠性和安全性帶來了隱患和大量的損失。

(3)易引起網絡域名所有權糾紛

因為網絡域名帶有語義,不可避免涉及到所有權歸屬問題,從而帶來可能的法律糾紛,如www.yaoming.com是否可以被姚明以外的別人注冊,一旦被他人注冊,所發布的信息很可能會對姚明的某些利益造成損害。

(4)不支持數據的移動與遷移

因為DNS是面向主機的,當主機上面的數據被移動或復制后,DNS無法再次為該數據提供服務,用戶用以前的名字便無法找到相應的資源。

(5)負載不均衡

因為域名的不同字段的不同符號具有不同含義。在DNS服務器中,處于業務需要,負責.com域名解析的服務器相對于負責.org等域名解析的服務器負載要重很多,這導致.org的DNS服務器資源利用不足,而.com的服務器負荷過重。

為解決現有IP層和應用層路由的問題,很多研究者將目光發在了平面路由方式上。VRR[8]研究了基于分布式哈希表(DHT)環的路由協議,直接工作于鏈路層之上的協議。CANON[9]給出了一般性構造DHT環的方法,研究了多個DHT換的合并算法。ROFL[10]對CANON進行了擴展,使之能夠支持更多的互聯網策略。SEATTLE針對小規模以太網給出了平坦路由的實現方法。在文獻[7]中提出名為DONA的映射系統,用扁平名字方式提供新服務的接入接口。在文獻[5]中提出了DHT形式的命名與解析,實現了身份與地址的分離,身份信息只用于名字解析,地址信息用于路由。在文獻[6]中提出用改進的DHT系統OpenDHT來實現命名與解析。在文獻[7]中提出了雙層結構來提高DHT系統的查詢效率,這種結構給我們名字解析映射系統的設計提供了新的思路。

2 基于名的平坦路由

2.1 基于名的單DHT環平坦路由

采用單個DHT環管理整個網絡的路由運作。下面給出基于名的單DHT環平坦路由的工作原理與過程。

在基于名的平坦路由體系中,網絡每個終端節點擁有一個平面化的無含義的標志來代表其身份。用網絡路由器節點的子集構成一個邏輯相互可達的DHT環,環上的節點分布式管理并負責一部分終端的位置注冊與查找。其工作過程主要可分為3個階段,即位置注冊、位置查找和數據路由3部分。位置注冊過程的主要任務是,終端在接入網絡時向其對應的網絡位置管理節點注冊自己的接入位置。位置查找過程主要是指,通信終端通過通信對端的名字向網絡查詢其對應的接入位置。而數據路由過程主要負責的是數據的路由優化及正確傳輸。

以圖1為例,大圓環代表DHT環,小圓圈節點代表位于DHT環的路由節點,正方形節點代表終端節點。

(1)位置注冊過程

如圖1(a)所示,當終端Ha接入網絡時,其接入路由器Ra根據Ha的名字Ha采用Hash算法計算出Ha對應的位置注冊節點為Re,然后向Re發送消息,在RE上注冊Ha的接入位置Ra。

(2)位置查找過程

如圖1(b)所示,終端Hb的接入路由器為Rb。當Hb想向Ha發送數據時,Rb需要知道Ha的接入位置,才能進行路由。首先,Hb向Rb發送Request(Ha)查詢Ha的接入位置,若Rb的Cache里沒有Ha的位置表項,便用Ha哈希出其位置注冊節點為Re,然后向Re發送Request(Ha)請求;Re收到查詢消息后,查得位置信息對,并將此信息回復給Rb;至此,Rb獲知Ha的接入位置為Ra。

(3)數據路由過程

如圖1(c)所示,Hb以[Ha, Hb]為通信的目的、源標志對向網絡發送數據包;Rb收到Hb發送給Ha的數據包,知道Ha的接入位置為Ra,便將數據包轉發給Ra;Ra收到數據包后,將其發送給Ha。

上述3個階段可實現基于名的單DHT環的平坦路由過程與通信。

2.2 基于名的多DHT環平坦路由實現過程

顯然,單DHT環的平坦路由只適合于小規模網絡。考慮到大規模網絡的路由擴展性問題和DHT環的管理難度,需對主機名進行擴展。這里提出了一種擴展方法,采用了層次DHT的方式,將整個互聯網分成若干個邏輯域,每個邏輯域由一個DHT環負責管理和路由。每個域中設置一個或多個域間位置管理節點(可由高性能路由器擔當),各個域的域間位置管理節點邏輯上亦相互連通,并組成一個二級DHT路由環,如圖2所示。

記擴展后的主機名為E_Ha,其高x 位表示所在域的域號Ai,低n -x 位為域內身份標志Ha,因而,E_Ha=Ai +Ha。其中Ai,Ha均為平面化的一串字符。下面以圖2為例詳細敘述雙層DHT環的域間路由實現過程。圖2中標號為“1”的虛箭頭所示為主機E_Ha接入注冊過程,標號為“2”的虛箭頭表示主機E_Hb向E_Ha發送數據前查詢E_Ha位置的過程,標號“3”為數據路由過程。

(1)位置注冊過程

當E_Ha在Ra上接入時,Ra首先根據E_Ha的Ha字段Hash出其域內位置管理節點Re,然后將注冊到Re上,與此同時,Ra也向域I的域間位置管理節點Da發送E_Ha的接入消息。Da收到E_Ha的接入消息后,用E_Ha的Ai 字段Hash出其域間的位置注冊節點Dc,然后將E_Ha的接入域位置信息注冊到Dc上。至此,E_Ha完成域內、域間的位置注冊過程。

(2)位置查找過程

當域II的E_Hb想向E_Ha發送數據時,E_Hb首先向自己的接入路由器Rz發送位置查詢消息,若Rz的Chache中沒有E_Ha的位置緩存,而且根據E_Ha的Ai 字段判斷發現E_Ha的位置在II域內,便向域II的域間位置管理節點Db發送Request(E_Ha)消息查詢E_Ha的接入位置;若Db的Chache中亦沒有E_Ha的位置緩存表項,Db就根據E_Ha的Ai 字段Hash出其域間位置管理節點Dc,于是向Dc查詢得E_Ha的域間接入節點位置為Da;接著,Db向Da發出E_Ha的接入位置查詢信息,若Da的Chache中亦沒有E_Ha的位置緩存表項,Da便根據E_Ha的Ai 字段Hash出其域內接入位置Re,然后將查詢消息發送給Re;Re收到查詢請求消息后,直接將查詢結果返回給Rz。于是Rz獲知E_Ha的接入位置為Ra。

(3)數據路由過程

此后,E_Hb開始以[E_Ha, E_Hb]通信的目的、源標志向E_Ha發送數據;Rz接收到數據包后直接向Ra轉發;Ra再將數據包送至E_Ha。至此,完成域間路由和數據傳輸過程。

需要說明的是上述兩小節僅給出了基于名的平坦路由在小網絡和大網絡的最基本方案和工作過程。在具體實施時,還需對各個細節進行優化以提高系統性能,如,可在相關節點加入高速緩存機制,提高查詢速度,減小查詢開銷等。

3 基于名的平坦路由優點分析

基于名的平坦路由,由于采用了無含義平面化的標志來代表網絡實體的身份,實現了網絡實體的身份ID與位置ID的分離。能夠有效解決現有網絡路由體系難以處理的問題,具體表現如下。

3.1 工作于網絡層的優勢

將基于名的平坦路由應用于網絡層,其方案與工作過程前面已有了較為全面的描述。本節重點分析在網絡層實施平坦路由帶來的好處。

(1)實現了用戶(主機)名空間與網絡名空間的分離,提高了網絡優化的靈活性和可行性。在平坦路由體系中,用戶名不再具有地址信息,與網絡拓撲沒有聯系,因而用戶與網絡被“隔離”開來。對于網絡而言,路由器節點的數量要遠遠小于用戶主機的數量,因而可以考慮采用不等長的地址長度定義路由器的地址和主機名。用較少位數的二進制串定義路由器節點的地址,因路由器移動的可能性很小,故仍可采用如IPv4實現。對于用戶名空間,由于數量龐大需采用較多二進制位表示,如128位或160位。這樣的好處是,數據一旦進入網絡可以按短地址進行傳輸,提高傳輸效率,而不像現有的IPv4或IPv6網絡,主機地址與路由節點地址長度相同。此外,用戶空間名與網絡名空間分離后,運營商在對路由設備進行調整或對核心網重新部署、調整和優化時,能夠使用戶感覺不到網絡的變化,這大大增加了網絡維護的靈活性和可操作性。而現有網絡因主機IP與網絡位置密切關聯,一旦接入路由器的地址發生變化,用戶主機也需重新配置,這是嚴重制約現有網絡進行優化的重要因素。

(2)實現了更簡單、靈活的主機名分配方式。現有IP地址是身份與位置的緊耦合體,既代表了網絡終端節點的身份也包含著網絡終端的位置信息。因此IP地址的在分配時除了考慮全局唯一性外還必須與網絡拓撲密切聯系。然而,由于IP資源占有的不均衡性和網絡發展的無尺度特性,使得IP地址的分配與理想差距越來越遠。正是因為IP地址分配的不合理性,使得IP網絡發展到今天出現了很多難以解決的問題。在平坦路由體系中,平面化的名稱是一串無含義的二進制碼串,只需保障全局唯一即可,因此分配與管理起來要方便和靈活得多。

(3)縮小了核心網絡路由節點的路由表規模,提高了路由可擴展性。因為用戶名空間被分離開來,大大減小了核心網路由器所需存儲的路由條目。通過統一的Hash函數確定終端位置,網絡中終端位置信息被均衡分布在所有路由節點上存儲,相比全平面化基于主機路由方式構建的路由系統,減輕了每個節點的路由表存儲開銷,提高了系統資源使用的均衡性。在平坦路由體系中,因身份名與地址無關,終端的移動并不會引起路由表的條目和聚合難度的增長,因而可保證路由的可擴展性。

(4)更安全、可靠。對于主機名的分配可采用文獻[10]所述的自認證公私鑰體制方式,能有效杜絕和降低現有的IP地址欺騙等攻擊行為,增強網絡的安全性。在基于名的平坦路由體系中,通信的雙方僅通過“名字”相互通信,并不知道對方的具體位置,保護了用戶位置信息的隱秘性,提高了通信的安全性。此外,由于用戶空間與核心網空間的解耦合,使得惡意用戶難以利用地址對核心網路由設備實施攻擊,這也大大增強了核心網的安全性。

(5)對移動、多家鄉的有效支持。根據第2節的工作原理描述可清晰看出,平坦路由體系通過在DHT環上的相應節點存儲終端接入位置信息,終端在網絡內發生微移動時,僅通過統一的Hash函數便可確定位置,進行通信。終端的地址和“名”不需要發生任何變化,有效減少了網絡維護終端移動的開銷,提高了對移動的支持性。對于多家鄉而言,一個終端若在兩個位置進行了接入,只需在位置注冊節點進行注冊,不需要再分配底層通信的臨時地址,也不用增加路由表項,因而基于名的平坦路由可有效支持多家鄉。

(6)用戶配置簡單。用戶上網不用再進行復雜配置,特別對于移動用戶,在不斷更換接入位置的情況下,不用像在IP網中一樣,換一個接入網關就需要重新配置一次IP信息。

3.2 工作于應用層的優勢

將基于名的平坦路由體系用于應用層的DNS系統或P2P網絡,其過程與第3節所述過程相似。不同之處在于,此時代表“名”的二進制碼串標志的是一個資源實體而不是主機。注冊過程和查找過程與圖1相似,但代表的是資源位置的注冊過程和資源的位置查找過程。基于名的平坦路由應用于服務資源查找系統的優勢在于。

(1)數據安全性增強。因平面名字不帶有語義信息,所以不存在某個國家對整個解析映射系統的控制,因為無法從沒有語義信息的名字中區分哪些名字屬于那些國家或單位,因此打破了現有DNS系統權限不均衡性,有效消除了現有DNS系統的隱患。

(2)配置簡單,系統的魯棒性、安全性得到增強。平面名字不需要手動配置,生成過程由系列算法實現,從而避免了手動配置的任務,消除了人為錯誤配置所產生的安全隱患。

(3)消除了域名注冊中的商業糾紛隱患。因平面名字不帶有語義信息,所以在全局唯一的前提下隨便使用不會帶來商業糾紛。

(4)支持數據移動和遷移。因平面名字是面向數據的,與資源的位置無關。當主機上面的數據移動或復制以后,數據的名字永遠不變是唯一的,所以可以用以前的名字來找到相應的資源。

(5)實現了資源查找系統的負載均衡。平面解析映射系統一般采用Hash算法,而Hash算法是一種散列算法,他可以將不均勻的分布變為均勻分布,所以,實現解析映射系統的負載均衡。

4 結束語

隨著互聯網的不斷發展和用戶數量的不斷增長,現有的基于結構化地址的路由方式已暴露出許多難以解決的問題。作為網絡的核心支撐技術——路由技術,直接決定著網絡的繼續發展與成敗。為此,本文給出了基于名的平坦路由的實施方案,首次提出了多域間的平坦路由實現過程。由于平面化名稱使得網絡資源和主機等實體與其位置信息分離開來,可很好地提高網絡的路由可擴展性、移動支持性、路由安全性、可配置性、遷移與復制資源查找的支持性以及網絡負載均衡等性能。基于名的平坦路由打破了傳統的路由體系,是有效解決網絡現有路由問題的一種新的研究思路與方案技術。然而,平坦路由的研究仍處于起步階段,很多實現方案細節還很不完善,如平面化名稱如何定義更有效、大規模網絡的平坦路由問題,如何在平坦路由中實施路由策略,流量工程等問題都還有待于進一步研究。

5 參考文獻

[1] KIM C, CAESAR M, REXFORD J. Floodless in SEATTLE: A scalable Ethernet architecture for large enterprises[C]// Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM08), Aug 17-22, 2008, Seattle, WA, USA. New York, NY,USA:ACM,2008:3-14.

[2] AS65000 BGP routing table analysis report[EB/OL]. [2009-6-26]. http://bgp.potaroo.net/as2.0/bgp-active.html.

[3] WALFISH M, BALAKRISHNAN H, SHENKER S. Untangling the Web from DNS[C]// Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation(NSDI'04), Mar 29-31,2004,San Francisco, CA,USA. Berkeley, CA, USA: USENIX Association, 2004:225-238.

[4] RAY S, GUERIN A, SOFIA R. A distributed hash table based address resolution scheme for large scale Ethernet networks[C]// Proceedings of IEEE International Conference on Communications (ICC07), Jun 24-27, 2007, Scotland, UK. Piscataway, NJ,USA:IEEE,2007: 6446-6453.

[5] KOPONEN T, CHAWLA M, BYUNG G C, et al. A data-oriented (and beyond) network architecture[C]// Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM07), Aug 27-31, 2007, Kyoto, Japan. New York, NY,USA:ACM, 2007:181-192.

[6] RHEA S, GODFREY B, KARP B, et al. OpenDHT: A public DHT service and its uses[C]// Proceedings of Conference on Applications, Technologies,Architectures, and Protocols for Computer Communications (SIGCOMM05), Aug 22-26, 2005, Philadelphia, PA, USA. New York, NY,USA:ACM, 2005:73-84.

[7] MIZRAK A, CHENG Y, KUMAR V, et al. Structured superpeers: Leveraging heterogeneity to provide constanttime lookup[C]//Proceedings of the 3rd Workshop on Internet Applications (WIAPP'03), Jun 23-24, 2003, San Jose, CA,USA. Los Alamitos, CA,USA: IEEE Computer Society,2003: 104-111.

[8] CAESAR M, CASTRO M., NIGHTINGALE E B,et al. Virtual ring routing : network routing inspired by DHTs[C]// Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06), Sep 11-15, 2006, Pisa, Italy. New York, NY,USA:ACM, 2006:351-362.

[9] GANESAN P, GUMMADI K, GARCIA-MOLINA H. Canon in G major: Designing DHTs with hierarchical structure[C]// Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS04), Mar 23-26, 2004, Tokyo, Japan. Piscataway, NJ,USA:IEEE, 2004: 263-272.

[10] CAESAR M, CONDIE T, KANNAN J. ROFL: Routing on flat labels[C]// Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06), Sep 11-15, 2006, Pisa, Italy. New York, NY,USA:ACM, 2006:363-374.

收稿日期:2009-08-30

裘正定,北京交通大學計算機與信息技術學院信息科學研究所教授,中國通信學會會士、中國電子學會會士、鐵道學會高級會員,主要研究領域為多媒體通信、下一代互聯網絡、信號與信息處理等。已發表SCI/EI檢索論文100余篇。

熊軻,北京交通大學計算機與信息技術學院信息科學研究所在讀博士生,主要研究方向為多媒體通信、下一代互聯網絡、信號與信息處理等。已發表論文10余篇。