paper地址：NLSR: Named-data Link State Routing Protocol

摘要（Abstract）

本文介紹了一種用于命名數(shù)據(jù)網(wǎng)絡(luò)（NDN， Named Data Network）的路由協(xié)議——命名數(shù)據(jù)鏈路狀態(tài)路由協(xié)議（NLSR喇伯，Named-data Link State Routing Protocol）的設(shè)計(jì)。由于NDN使用名稱來標(biāo)識和檢索數(shù)據(jù)雀瓢，所以NLSR將可達(dá)性傳播到名稱前綴而不是IP前綴。此外，NLSR區(qū)別于基于IP的鏈路狀態(tài)路由協(xié)議当纱，有兩個(gè)最基本的特征嘀略。首先恤溶，NLSR使用興趣包（Interest Packet）和數(shù)據(jù)包（Data Packet）來傳播路由更新，直接受益于NDN內(nèi)生的數(shù)據(jù)包驗(yàn)證帜羊，更加安全咒程；其次，NLSR為每一個(gè)名稱前綴生成一個(gè)按一定規(guī)則（比如讼育，開銷）排好序的轉(zhuǎn)發(fā)選項(xiàng)列表帐姻，給實(shí)現(xiàn)NDN自適應(yīng)的轉(zhuǎn)發(fā)策略做支撐稠集。在本文中，我們將討論NLSR主要設(shè)計(jì)思想饥瓷，主要包括以下幾個(gè)部分：

• 一個(gè)適用于路由器剥纷、安全密碼（keys，包括公私鑰那些）呢铆、和路由更新的層次化命名方案晦鞋；

• 一個(gè)適用于單個(gè)管理域的層次化信任模型；

• 一個(gè)逐條同步協(xié)議棺克，用于替代傳統(tǒng)的使用網(wǎng)絡(luò)泛洪的方式傳播路由更新悠垛；

• 一個(gè)給多路徑轉(zhuǎn)發(fā)選項(xiàng)排序的簡單算法。

與基于IP的鏈路狀態(tài)路由協(xié)議相比逆航，NLSR提供更高效的路由更新傳播鼎文，擁有內(nèi)建的路由更新認(rèn)證而且原生支持多路徑轉(zhuǎn)發(fā)。

關(guān)鍵詞（Keywords）

Routing, NDN, Trust Model

介紹（Introduction）

命名數(shù)據(jù)網(wǎng)絡(luò)（NDN）[3, 4]是一種新型的網(wǎng)絡(luò)體系結(jié)構(gòu)因俐，是對當(dāng)前基于IP的Internet體系結(jié)構(gòu)一次大刀闊斧的整改拇惋。NDN在每個(gè)包（packet）中都放置一個(gè)數(shù)據(jù)名稱，而不是攜帶目標(biāo)IP地址抹剩；數(shù)據(jù)的消費(fèi)者發(fā)送一個(gè)興趣包（Interest packet）來獲取數(shù)據(jù)撑帖，興趣包中包含了所要獲取數(shù)據(jù)的名稱標(biāo)識，一個(gè)包含相同名字的數(shù)據(jù)包（Data packet）可以用來響應(yīng)這個(gè)興趣包（Interest Packet）澳眷，數(shù)據(jù)包中包含名稱胡嘿、數(shù)據(jù)以及一個(gè)由最初的數(shù)據(jù)生產(chǎn)者生成的對該數(shù)據(jù)包的簽名。通過給數(shù)據(jù)包進(jìn)行顯示的命名和簽名钳踊，NDN網(wǎng)絡(luò)支持一系列的特性衷敌，包括：網(wǎng)內(nèi)緩存（ in-network caching）、多路徑轉(zhuǎn)發(fā)（multipath forwarding）拓瞪、多播數(shù)據(jù)交付（multicast data delivery）和數(shù)據(jù)真實(shí)性校驗(yàn)（data authenticity）缴罗。

為了能使NDN在廣域網(wǎng)（wide-area networks）上能很好的工作，一個(gè)NDN的路由協(xié)議需要計(jì)算并將合適的轉(zhuǎn)發(fā)條目插入到NDN節(jié)點(diǎn)的FIB（NDN網(wǎng)絡(luò)的轉(zhuǎn)發(fā)表）表中祭埂。每個(gè)FIB表項(xiàng)包含一個(gè)名稱前綴和一個(gè)或多個(gè)下一條出口記錄面氓，NDN可以根據(jù)FIB表信息來轉(zhuǎn)發(fā)和FIB表項(xiàng)中名稱前綴相匹配的興趣包（Interest packet）。IP網(wǎng)絡(luò)下的路由協(xié)議必須使用單一的最佳下一跳或者限制其轉(zhuǎn)發(fā)到多個(gè)等成本的路徑蛆橡，來避免循環(huán)路徑的產(chǎn)生舌界，而NDN網(wǎng)絡(luò)有內(nèi)建的預(yù)防循環(huán)路徑產(chǎn)生的機(jī)制，所以可以自由的利用多個(gè)路徑泰演。因此呻拌，NDN網(wǎng)絡(luò)需要一個(gè)能夠支持基于名稱進(jìn)行多路徑路由的路由協(xié)議。

我們之前為NDN開發(fā)了一個(gè)OSPFN [8] 路由協(xié)議睦焕，它是OSPF路由協(xié)議的一個(gè)擴(kuò)展版本柏锄，適用于NDN酿箭，并將其部署在NDN的測試床上。OSPFN定義了一種新的不透明的鏈路狀態(tài)通告（LSA）趾娃，用于在路由消息中攜帶名稱前綴缭嫡。它為每個(gè)名稱前綴計(jì)算出最佳的下一跳，并插入到FIB表當(dāng)中抬闷，網(wǎng)絡(luò)管理員可以手動(dòng)為OSPFN配置一個(gè)除了最佳下一跳以外的可選下一跳列表妇蛀，并插入到FIB表中。雖然OSPFN可以構(gòu)建基于名稱前綴的FIB表笤成，但同樣存在很多限制评架。和傳統(tǒng)的基于IP的路由協(xié)議一樣，OSPFN仍然使用IP地址作為路由器的ID炕泳，依賴于GRE隧道來跨越傳統(tǒng)的IP網(wǎng)絡(luò)纵诞，并且對于每個(gè)名稱前綴值計(jì)算一個(gè)最佳的下一跳。我們在部署OSPFN的過程中發(fā)現(xiàn)培遵，管理IP地址和隧道是主要的操作問題浙芙，并且由于對多路徑的支持不夠，限制了NDN原有的優(yōu)勢（內(nèi)建的網(wǎng)內(nèi)緩存和防路徑循環(huán)機(jī)制等等）籽腕。

在本文接下來的部分嗡呼，我們將介紹命名數(shù)據(jù)鏈路狀態(tài)路由協(xié)議（NLSR）的詳細(xì)設(shè)計(jì)，并使其工作在NDN網(wǎng)絡(luò)上（換句話來說皇耗，NLSR使用NDN的興趣包和數(shù)據(jù)包來交換路由消息）南窗。OSPFN是一種與OSPF類似的鏈路狀態(tài)協(xié)議——鏈路狀態(tài)通告（LSA）在整個(gè)網(wǎng)絡(luò)中傳播，每個(gè)路由器構(gòu)建出了完整的網(wǎng)絡(luò)拓?fù)淅陕ァ：蚈SPF有所區(qū)別的是万伤，在OSPFN中，路由器不再只計(jì)算一條最短路徑呜袁，而是對所有符合策略的下一跳進(jìn)行排名敌买，并按序?qū)懭隖IB表當(dāng)中，其在本質(zhì)上提供了一個(gè)基于名稱的多路徑路由表傅寡，被用來作為NDN轉(zhuǎn)發(fā)策略的輸入（NDN的可以利用多路徑信息進(jìn)行豐富的轉(zhuǎn)發(fā)策略定制）放妈。

NLSR使用名稱而不是IP地址來標(biāo)識路由器和鏈接北救，因此它可以使用任何底層的通信渠道（例如：以太網(wǎng)荐操、IP隧道、TCP/UDP隧道等等）來交換路由消息珍策。NLSR直接受益于NDN內(nèi)建的數(shù)據(jù)認(rèn)證機(jī)制：由于每個(gè)路由更新消息都是由NDN數(shù)據(jù)包（Data packet）所攜帶的托启，并且NDN中每個(gè)數(shù)據(jù)包都帶有數(shù)據(jù)生產(chǎn)者的簽名，所以路由器可以通過驗(yàn)證每個(gè)路由消息的簽名來保證它是由指定的原始路由器生成的攘宙，并且在傳播過程中沒有被篡改（數(shù)據(jù)的完整性和有效性校驗(yàn)）屯耸。

作為NDN上第一個(gè)分布式的路由協(xié)議拐迁，NLSR的設(shè)計(jì)需要回答以下幾個(gè)在NDN上獨(dú)有的問題：

• 命名（Naming）：如何給路由器（routers）、鏈接（links）和路由更新（routing updates）命名疗绣？
• 信任（Trust）：如何分發(fā)路由器的加密密鑰（cryptographic keys）线召，以及如何獲得對這些密鑰的信任
• 信息傳播（Information Dissemination）：如何在網(wǎng)絡(luò)中傳播路由更新？（基于IP的路由協(xié)議采用推的方式將路由更新發(fā)送給其他路由器多矮，而在NDN網(wǎng)絡(luò)中則需要路由器主動(dòng)去拉取所有更新）
• 多路徑（Multipath）：如何產(chǎn)生并排序下一跳以促進(jìn)多跳轉(zhuǎn)發(fā)缓淹？

在本文中，我們描述了我們是如何選擇我們的設(shè)計(jì)方案的塔逃，并且闡明了這些選擇背后的基本原理讯壶。我們的目標(biāo)不是發(fā)明一種新的路由方案（因?yàn)樵诒举|(zhì)上來講NLSR也是一種鏈路狀態(tài)路由協(xié)議），而是為了證明在NDN網(wǎng)絡(luò)上建立一個(gè)路由協(xié)議的可行性和優(yōu)勢湾盗。

由于NDN的自適應(yīng)多路徑轉(zhuǎn)發(fā)能夠處理在轉(zhuǎn)發(fā)平面上存在的多個(gè)數(shù)據(jù)包傳遞問題（例如：環(huán)形路徑）伏蚊，使得路由平面的限制放寬了，設(shè)計(jì)可以更加自由格粪。舉例來說躏吊，路由協(xié)議將不用關(guān)心路由平面是否會(huì)產(chǎn)生環(huán)路，因?yàn)镹DN的FIB表項(xiàng)的合并操作將使得環(huán)路的產(chǎn)生變得不可能匀借。因此颜阐，一些原先在IP網(wǎng)絡(luò)中不起作用的路由協(xié)議設(shè)計(jì)現(xiàn)在可以在NDN網(wǎng)絡(luò)中使用，并且新型路由的設(shè)計(jì)也成為可能吓肋。探索其它類型的路由設(shè)計(jì)將是我們未來的工作之一凳怨。

本文接下來的部分將包含以下內(nèi)容：第二節(jié)簡要介紹了NDN網(wǎng)絡(luò)所提供的一些基本的功能，第三節(jié)介紹了設(shè)計(jì)的細(xì)節(jié)是鬼，第四節(jié)展示了實(shí)驗(yàn)測量和結(jié)果肤舞，第五節(jié)討論一些相關(guān)的工作，第六節(jié)將對全文進(jìn)行總結(jié)均蜜。

NDN的基本功能（NDN PRIMARY）

NDN在其轉(zhuǎn)發(fā)平面 [3] 中有三個(gè)主要的組件：

• 轉(zhuǎn)發(fā)信息庫（FIB李剖，Forwarding Information Base）：FIB即為NDN網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)表，用于存儲(chǔ)轉(zhuǎn)發(fā)條目囤耳，將興趣包與相匹配數(shù)據(jù)（與興趣包名稱相同的數(shù)據(jù)包）的潛在來源相關(guān)聯(lián)篙顺。與IP網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)表不同的是，對于每一個(gè)名稱前綴充择，他的傳出端口（下一跳）不止一個(gè)德玫，而是一個(gè)列表。FIB表中的表項(xiàng)可以手動(dòng)插入椎麦，也可以利用NDN路由協(xié)議中的控制平面進(jìn)行填充宰僧。
• 未決興趣表（PIT，Pending Interest Table ）：PIT表存儲(chǔ)了未被滿足的興趣包以及他們到來的face接口观挎，因此數(shù)據(jù)包可以通過查詢PIT表項(xiàng)被路由回到原始的發(fā)送興趣包的節(jié)點(diǎn)琴儿。
• 內(nèi)容緩存（CS段化，Content Store）：CS用來緩存數(shù)據(jù)。

當(dāng)一個(gè)興趣包到達(dá)路由器造成，路由器首先會(huì)檢查CS中是否有相匹配的數(shù)據(jù)显熏，如果有則將數(shù)據(jù)包從收到興趣包的端口上轉(zhuǎn)發(fā)出去，否則將其添加到PIT表當(dāng)中（同時(shí)記錄下興趣包的入口Face）晒屎。如果PIT表中存在相同名稱的條目佃延，新的端口編號將被添加到端口列表當(dāng)中，以便可以在數(shù)據(jù)包到來時(shí)向所有興趣包到來的端口發(fā)送一個(gè)數(shù)據(jù)包的副本夷磕。最后履肃，如果興趣包是第一次插入PIT表中（即 PIT表中不存在相同名字的興趣包），則該興趣包將通過查詢FIB表轉(zhuǎn)發(fā)至下一跳坐桩，如果FIB條目中存在多個(gè)下一跳尺棋，則一個(gè)成為“轉(zhuǎn)發(fā)策略”的模塊將會(huì)決定在多條路徑同時(shí)存在的情況下，該如何轉(zhuǎn)發(fā)興趣包绵跷。

設(shè)計(jì)（Design）

作為一種鏈路狀態(tài)路由協(xié)議膘螟，NLSR通過分發(fā)鏈路狀態(tài)通告（LSAs）來構(gòu)建網(wǎng)絡(luò)拓?fù)洳⒎职l(fā)名稱前綴可達(dá)性。NLSR路由器建立并維護(hù)與鄰接路由器的關(guān)系碾局，每當(dāng)它檢測到任意鏈接的故障或恢復(fù)荆残，或者是發(fā)現(xiàn)一個(gè)新的鄰居，都會(huì)生成一個(gè)新的LSA并傳播到整個(gè)網(wǎng)絡(luò)當(dāng)中净当。此外内斯，NLSR路由器還會(huì)向全網(wǎng)通告本地靜態(tài)配置的名稱前綴和local的內(nèi)容提供者動(dòng)態(tài)注冊的前綴。當(dāng)任意的名稱前綴被添加或者刪除時(shí)像啼，NLSR同樣會(huì)生成一個(gè)新的LSA并將其傳播到全網(wǎng)俘闯。最新版本的LSAs將會(huì)存儲(chǔ)在鏈路狀態(tài)數(shù)據(jù)庫（LSDB，Link State Data Base）忽冻。

這種拓?fù)浜涂蛇_(dá)性信息的分發(fā)方式最初看起來似乎有點(diǎn)過于直接了真朗，因?yàn)樵贗P路由器中已經(jīng)實(shí)現(xiàn)了類似的功能。然后僧诚，由于在NLSR中使用NDN的興趣包和數(shù)據(jù)包來進(jìn)行路由更新遮婶，路由協(xié)議的設(shè)計(jì)就必須對IP地址和IP數(shù)據(jù)推送等一些熟悉的概念（例如：在IP網(wǎng)絡(luò)中任何節(jié)點(diǎn)都可以簡單的將任何數(shù)據(jù)包發(fā)送到任何其它的節(jié)點(diǎn)）做一些轉(zhuǎn)變。因此湖笨，我們需要根據(jù)數(shù)據(jù)的名稱和數(shù)據(jù)的獲取方式來思考我們的設(shè)計(jì)旗扑。更具體來說，我們需要一個(gè)針對路由器和路由更新的系統(tǒng)的命名方案（3.1節(jié)詳細(xì)介紹）赶么。同時(shí)肩豁，路由器需要在不知道其它路由器何時(shí)會(huì)產(chǎn)生新的路由更新的情況下迅速的拉取到最新的路由更新脊串，因?yàn)榫W(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)名稱前綴隨時(shí)可能發(fā)生更改（而一旦網(wǎng)絡(luò)拓?fù)浠蛘呙Q前綴發(fā)生改變辫呻，就會(huì)產(chǎn)生新的路由更新）清钥。

在路由功能方面，NLSR與之前的鏈路狀態(tài)路由協(xié)議主要有以下兩個(gè)方面的不同：

• NLSR為每個(gè)名稱前綴提供多個(gè)路由放闺，而不是提供單個(gè)最短路徑祟昭；
• NLSR對每個(gè)LSA都進(jìn)行簽名和驗(yàn)證，這樣能保證每個(gè)路由器只產(chǎn)生自己的前綴和連接信息（不能偽造）

我們將在3.4節(jié)介紹我們的路徑計(jì)算算法怖侦， 在3.6節(jié)介紹NLSR的信任模型篡悟。

作為開發(fā)基于NDN的路由協(xié)議的第一步焙矛，NLSR最初的設(shè)計(jì)運(yùn)行在單個(gè)路由域中瞧筛，并且只使用簡單的單權(quán)限信任模型。我們現(xiàn)在正在將NLSR部署到我們的NDN測試床上绍移，我們相信這一初步設(shè)計(jì)的部署經(jīng)驗(yàn)可以為我們以后開發(fā)基于NDN的域間路由協(xié)議和設(shè)計(jì)域間路由的信任模型起到拋磚引玉的效果艳悔。

• 命名（Naming）

  也許我們設(shè)計(jì)中最重要的部分便是在路由系統(tǒng)中對每個(gè)元素及其相關(guān)的公鑰設(shè)計(jì)一個(gè)合適的命名方案急凰。基于我們現(xiàn)有網(wǎng)絡(luò)的結(jié)構(gòu)和操作經(jīng)驗(yàn)猜年，分層命名的方案可以很好的表示系統(tǒng)中各個(gè)組件的關(guān)系抡锈，還可以很容易區(qū)分路由器是否屬于同一個(gè)網(wǎng)絡(luò)，同時(shí)為給定的路由過程生成消息也變得簡單乔外。同樣的床三，分層命名的方案還有利于將密鑰和其擁有者關(guān)聯(lián)起來。

  在我們的設(shè)計(jì)中杨幼，每個(gè)路由器的命名都是根據(jù)它所在的網(wǎng)絡(luò)撇簿，所屬的站點(diǎn)以及其所屬站點(diǎn)為該路由器分配的名字組成的，即 /<network>/<site>/<router>差购。例如补疑，一個(gè)位于亞特蘭大（Atlanta）的一個(gè)PoP中的路由器的一個(gè)可能命名時(shí)這樣子的：/ATT/AtlantaPop1/router3。以這種方式命名的話歹撒，如果兩個(gè)路由器共享相同的名稱前綴/<network>莲组，則可以判斷這兩個(gè)路由器屬于同一個(gè)網(wǎng)絡(luò)下；如果兩個(gè)路由器共享相同的名稱前綴/<network>/<site>暖夭，則可以判斷這個(gè)兩個(gè)路由器屬于同一個(gè)網(wǎng)絡(luò)下的同一個(gè)站點(diǎn)锹杈。采用這種分層命名的方式，可以很容易的過濾出錯(cuò)誤的路由消息迈着。

  路由器上NLSR進(jìn)程的名字時(shí)根據(jù)路由器的名稱命名的竭望，具體的就是路由器的名稱作為前綴，后面跟上NLSR進(jìn)程的名字NLSR裕菠，即/<network>/<site>/<router>/NLSR咬清。這個(gè)路由進(jìn)程名字用于在相鄰NLSR路由器節(jié)點(diǎn)之間傳遞周期性的info消息，可以用來檢測鏈接是否失敗，以及檢測NLSR進(jìn)程本身的一些錯(cuò)誤（3.5節(jié)會(huì)詳細(xì)介紹）旧烧。

  在理想情況下影钉，任何由NLSR進(jìn)程產(chǎn)生的路由更新消息的命名都應(yīng)該以該NLSR路由進(jìn)程的名稱作為前綴，這樣就很容易可以辨別產(chǎn)生該消息的NLSR進(jìn)程掘剪。換句話說平委，一個(gè)LSA的名稱應(yīng)該時(shí)類似這種格式的：/<network>/<site>/<router>/NLSR/LSA，這樣可以標(biāo)識該LSA是由指定的NLSR進(jìn)程生成的夺谁。然而廉赔， 由于我們在實(shí)現(xiàn)的過程中使用了CNNx [5] 和 Repo [5] 來傳播同步LSA消息，而 CNNx repo 嚴(yán)格限制了所有參與同步的消息都要共享相同的前綴匾鸥，我們目前一個(gè)折衷的做法是所有路由器生成的LSA都共用一個(gè)前綴蜡塌。我們?yōu)槊總€(gè)LSA使用相同的前綴/<network>/NLSR/LSA（我們稱之為 <LSA-prefix>），并在此前綴后加上/<site>/router用以區(qū)分不同NLSR路由器生成的LSA勿负。

• 鏈路狀態(tài)通告（LSAs）

  NLSR設(shè)計(jì)了兩種類型的LSA岗照，分別是鄰接LSA（Adjacency LSA）和前綴LSA（Prefix LSA），其中鄰接LSA用于對外宣告一個(gè)NDN路由器與其所有鄰居相連的活動(dòng)的鏈路笆环，而前綴LSA則用于對外宣告在當(dāng)前的NDN路由器已經(jīng)注冊的名稱前綴攒至。他們所包含的內(nèi)容如下表所示：

  Type	Content
  Adjacency LSA	#Active Links (N), Neighbor 1 Name, Link 1 Cost, ...,Neighbor N Name, Link N Cost
  Prefix LSA	isValid, Name Pre?x

  一個(gè)鄰接LSA（Adjacency LSA）的命名通常是這樣的：/<LSA-prefix>/<site>/<router>/LsType.1/<version>，其中<router>指的是產(chǎn)生該LSA的路由器的名字躁劣，<version>指的是LSA的版本號（這個(gè)版本號是隨時(shí)間變化的迫吐，路由器每產(chǎn)生一個(gè)新的同類型的 LSA，版本號就會(huì)改變）账忘，在目前的實(shí)現(xiàn)里志膀，LSA的<version>使用的是LSA創(chuàng)建時(shí)的時(shí)間戳（實(shí)際上，和OSPF類似鳖擒，用序列號來表示也是可以的）溉浙。如表1所示，鄰接LSA包含了所有與當(dāng)前路由器相連的處于激活狀態(tài)的鏈接蒋荚，每一項(xiàng)包含鄰居路由器的名字戳稽，和鏈路開銷（link cost）。它是在路由器啟動(dòng)的時(shí)候創(chuàng)建的期升，且每當(dāng)路由器的鏈接狀態(tài)發(fā)生改變時(shí)（路由器的鏈接狀態(tài)的改變是由周期性的 info 興趣包檢測到的惊奇，在3.5節(jié)會(huì)），都會(huì)創(chuàng)建新的鄰接LSA播赁。

  一個(gè)前綴LSA（Prefix LSA）的命名通常是這樣的：/<LSA-prefix>/<site>/<router>/LsType.2/LsId.<ID>/<version>颂郎，需要提一嘴的是，每個(gè)名稱前綴都是使用單獨(dú)的前綴LSA來向外通告的容为。由于一個(gè)路由器通常需要宣告多個(gè)前綴乓序，所以我們在前綴LSA的命名中使用ID來標(biāo)識不同前綴的LSA（前綴LSA的ID可以是手動(dòng)配置的寺酪，也可以是基于要宣告的名稱前綴計(jì)算得來的）。我們這樣設(shè)計(jì)前綴LSA是有所考慮的替劈，如果我們將所有的前綴都塞到單個(gè)LSA中進(jìn)行傳播可能會(huì)放不下寄雀，而且更新的效率不高（因?yàn)槊慨?dāng)有前綴添加或刪除的時(shí)候就需要生成新的前綴 LSA，如果所有的前綴都用一個(gè)前綴 LSA來通告的話抬纸，就會(huì)傳遞很多冗余信息）。每個(gè)前綴LSA包含一個(gè)isValid標(biāo)記（初始時(shí)耿戚，isValid = 1）和要宣告的前綴名稱湿故。當(dāng)一個(gè)名稱前綴被取消注冊時(shí)膜蛔，NLSR會(huì)將對應(yīng)的前綴LSA的isValid標(biāo)記設(shè)置為0呜呐，并且將新的LSA傳播給其它節(jié)點(diǎn)洋魂，其它的NLSR節(jié)點(diǎn)收到這個(gè)LSA會(huì)將這個(gè)名稱前綴從LSDB中刪除并且更新FIB表項(xiàng)中對應(yīng)的表項(xiàng)豁翎。

  為了移除由于路由器故障來不及移除的過時(shí)的LSA刘陶，每個(gè)路由器會(huì)周期性的為每個(gè)要通告的前綴生成新版本的前綴LSA捍掺，而且每個(gè)LSA會(huì)有一個(gè)生存期（lifetime）不瓶，一旦生存期失效麦备，這個(gè)LSA就會(huì)被路由器從LSDB中移除呛梆。因此融痛，一旦某個(gè)路由器發(fā)生故障奔潰责语，其之前通告的的LSA不會(huì)在其它路由器的LSDB中保存太長時(shí)間智末，會(huì)很快失效代兵。路由器在計(jì)算路由時(shí)谓媒，不應(yīng)該收到NLSR中過時(shí)的LSA的影響淆院，一旦路由器奔潰何乎，其鄰居將會(huì)更新它們LSA的狀態(tài)，這樣網(wǎng)絡(luò)流量就不會(huì)向通往這個(gè)奔潰路由器的無效鏈路上傳送了土辩。因?yàn)槲覀儾皇褂盟⑿聶C(jī)制來處理丟包和包損壞（這些將由 CNNx Sync 處理）支救，而且過期的LSA并不影響路由計(jì)算，因此刷新器的刷新間隔可以設(shè)置成較大的間隔拷淘，例如：可以每天刷新一次各墨。

• LSDB 同步（LSDB Synchronization）

  為了從概念上簡化我們的設(shè)計(jì)，我們將LSDB看作一個(gè)數(shù)據(jù)的集合启涯，把LSA的傳播問題看作由路由器維護(hù)的LSDBs的同步問題贬堵。路由器周期性地交換他們LSDB的hash值來檢測不一致性，如果發(fā)現(xiàn)不一致則從不一致中恢復(fù)结洼。這種逐跳的同步方法可以避免不需要的網(wǎng)絡(luò)泛洪黎做，當(dāng)網(wǎng)絡(luò)穩(wěn)定時(shí)，鄰居之間只需要相互交換LSDB的hash值即可松忍，而不用互相傳遞所有的LSAs蒸殿。此外，這種數(shù)據(jù)同步方式時(shí)接收方驅(qū)動(dòng)的鸣峭，這意味著路由器只會(huì)在具有CPU周期時(shí)去拉取LSAs宏所，因此路由器基本不會(huì)被頻繁的路由器更新整奔潰。

  我們當(dāng)前的實(shí)現(xiàn)使用的是 CNNx 同步協(xié)議或 Sync [5] 來將LSAs傳播到鄰居路由器摊溶。Sync和CNNx的Repo相關(guān)聯(lián)爬骤，它允許應(yīng)用程序在Repo中定義命名數(shù)據(jù)集合，這個(gè)集合被稱之為slice莫换，并保持當(dāng)前路由器與相鄰路由器中定義相同的slice的同步盖腕。Sync會(huì)為Slice中所有的數(shù)據(jù)計(jì)算一個(gè)Hash樹赫冬，并且在相鄰路由器之間交換根Hash的值來檢測不一致性。如何檢測到Hash值不一致溃列，則兩個(gè)鄰居節(jié)點(diǎn)會(huì)交換Hash樹下一層節(jié)點(diǎn)的Hash值劲厌，直到他們檢測到導(dǎo)致不一致性的葉子節(jié)點(diǎn)，兩個(gè)鄰居路由器就會(huì)交換對應(yīng)的數(shù)據(jù)來達(dá)成新的一致性听隐。

  圖1 路由器之間使用 CNNx Sync/repo 相互傳播LSA示意圖（圖中虛線代表周期性消息）

  上圖1顯示了LSA是如何在網(wǎng)絡(luò)中傳播的：

  • 為了同步包含LSAs的Slice补鼻，Sync協(xié)議（路由器B）周期性的對外發(fā)送被稱為Root Advise的特殊興趣包，這個(gè)興趣包攜帶了發(fā)送路由器的Slice的hash值（步驟 1）雅任；

  • 當(dāng)路由器A創(chuàng)建了一個(gè)LSA风范，并把它寫入到Sync的Slice當(dāng)中（步驟 2），此時(shí)路由器A計(jì)算的Hash值與路由器B的不同沪么；

  • 這將導(dǎo)致路由器A的Sync回復(fù)路由器B的 Root Advise（通常硼婿，在兩個(gè)路由器計(jì)算得到的hash值相同的情況下，是不需要回復(fù) Root Advise 的禽车，當(dāng)路由器有有新的LSA產(chǎn)生或者移除時(shí)會(huì)導(dǎo)致路由器的Hash值不一致寇漫，此時(shí)才需要回復(fù) Root Advise），這個(gè)回復(fù)中攜帶了路由器A本地計(jì)算得到的新的Hash值殉摔；（步驟3）

  • 收到回復(fù)后州胳，路由器B的 Sync 會(huì)比對收到的Hash值，并遞歸的獲取到Hash樹下一層級的Hash值逸月，直到定位到導(dǎo)致不一致性的葉子節(jié)點(diǎn)栓撞，最終，路由器B的 Sync 會(huì)識別出需要同步的數(shù)據(jù)（這里所說的數(shù)據(jù)即為 NLSR 語境下的 LSA）碗硬，并發(fā)送對應(yīng)的興趣包將需要同步的數(shù)據(jù)從路由器A中拉取過來（步驟 4 和 5）瓤湘；

    • 接著，路由器B的 Sync 會(huì)將新收到的數(shù)據(jù)名字發(fā)給本地的NLSR進(jìn)行（步驟 6）
    • 然后路由器B的NLSR進(jìn)程就會(huì)發(fā)送對應(yīng)名字的興趣包給本地的 repo 來拉取同步過來的LSA數(shù)據(jù)（步驟 7 和 8）恩尾，最后更新到本地的LSDB當(dāng)中（步驟 9）弛说。

  每個(gè) Root Advise 興趣包都有一個(gè)存活期（lifetime），路由器在 Root Advise 興趣包到期后會(huì)發(fā)送一個(gè)新的 Root Advise 興趣包特笋。這種周期性傳輸機(jī)制的設(shè)計(jì)是為了防止 Root Advise 興趣包丟包的發(fā)生（試設(shè)想剃浇，如果Root Advise 興趣包的存活期無限大，會(huì)一直等待回復(fù)猎物，如果 Root Advise 興趣包在傳輸?shù)倪^程中丟失了虎囚，而發(fā)送方又不知道，且不重傳蔫磨，那么發(fā)送方會(huì)以為沒有新的更新淘讥，一直不去拉取最新的更新），從而降低由于丟包帶來的路由收斂延遲堤如。但是蒲列，如果數(shù)據(jù)包的丟失率很低窒朋，頻繁的發(fā)送 Root Advise 興趣包亦會(huì)帶來無意義的額外開銷。在理想情況下蝗岖，我們希望根據(jù)路由需求和網(wǎng)絡(luò)特性來調(diào)整 Root Advise 興趣包的發(fā)送頻率侥猩。為了支持這個(gè)特性并解決 CNNx Sync 實(shí)現(xiàn)中的一些其它問題，我們正在致力于開發(fā)內(nèi)建有同步機(jī)制的新版本的NLSR抵赢，以實(shí)現(xiàn)相同的LSA逐跳傳播的效果欺劳。

• 多路徑計(jì)算（Multipath Calculation）

  基于 鄰接LSAs（Adjacency LSAs）提供的網(wǎng)絡(luò)節(jié)點(diǎn)間的連接信息，每個(gè)NLSR節(jié)點(diǎn)都能構(gòu)建出完整的網(wǎng)絡(luò)拓?fù)淝稹＝又酚善髦恍柽\(yùn)行一個(gè)簡單的擴(kuò)展 Dijkstra 算法便可以為每一個(gè)目的節(jié)點(diǎn)計(jì)算出多跳路由划提。從 前綴LSAs（Prefix LSAs）中，我們可以知道每個(gè)路由器都關(guān)聯(lián)了哪些前綴邢享。我們可以綜合上述的信息計(jì)算出到達(dá)每個(gè)名稱前綴的下一跳列表鹏往。

  我們設(shè)計(jì)的NLSR中某個(gè)路由器計(jì)算多路徑路由的方式如下：

  • 首先路由器移除（并非斷開，只是排除）到除了一個(gè)鄰居外的其它直接相連的鄰居的路勁（即骇塘，只保留一個(gè)直接相連的鄰居）伊履；
  • 然后使用 Dijstra 算法計(jì)算計(jì)算當(dāng)前路由器到網(wǎng)絡(luò)拓?fù)渲衅渌泄?jié)點(diǎn)的開銷，并記錄绪爸；
  • 接著對每一個(gè)鄰居都重復(fù)上述過程湾碎；
  • 最后路由器到網(wǎng)絡(luò)上任意的其它節(jié)點(diǎn)都會(huì)有多條路徑宙攻，并且每條路徑都有一個(gè)開銷奠货，然后根據(jù)開銷進(jìn)行排名，就能得到到每個(gè)目的地的排好序的下一跳列表座掘。

  需要提一嘴的是递惋，NLSR支持讓用戶自行配置對某個(gè)名稱前綴最多能有幾條路勁插入到FIB當(dāng)中，這樣當(dāng)路由器的鄰居很多的情況下FIB表的大小也是可控的溢陪。但是計(jì)算開銷仍然會(huì)隨著 Face 接口數(shù)量的增加而增加萍虽，因?yàn)槲覀冃枰闅v所有的 Face 接口來找到所有可能的路徑。我們計(jì)劃探索其它多路徑計(jì)算算法來解決這個(gè)問題形真。

  與IP不同的是杉编，NDN中的路由信息僅作為轉(zhuǎn)發(fā)平面的提示信息（參考信息），轉(zhuǎn)發(fā)平面可以根據(jù)PIT表中維持的狀態(tài)來觀察數(shù)據(jù)交付的性能咆霜，然后結(jié)合實(shí)際觀測值和來自路由協(xié)議排名信息來對每個(gè)名稱前綴的多條路徑進(jìn)行排序邓馒。即便如此，路由協(xié)議中的排名信息對于初始時(shí)將一個(gè)興趣包轉(zhuǎn)發(fā)到指定前綴以及在當(dāng)前路由無法檢索數(shù)據(jù)時(shí)用于探索別的可用路由都是非常重要的蛾坯。

• 故障與恢復(fù)檢測（Failure and Recovery Detection）

  NLSR通過周期性的向每個(gè)鄰居節(jié)點(diǎn)發(fā)送 info 興趣包來檢測鏈路故障和遠(yuǎn)端的NLSR進(jìn)程故障光酣，如果 info 興趣包超時(shí)了，則NLSR會(huì)在較短的間隔內(nèi)多次發(fā)送 info 興趣包脉课，這樣可以防止 info 興趣包丟包帶來的影響救军。如果在此期間（這個(gè)時(shí)間包含info興趣包超時(shí)后的若干次重傳時(shí)間）鄰居節(jié)點(diǎn)沒有響應(yīng)财异，則NLSR會(huì)將這個(gè)鄰居節(jié)點(diǎn)的狀態(tài)判別為 down ，與該鄰居節(jié)點(diǎn)相連的鏈路也標(biāo)記為鏈路故障唱遭。檢測到故障之后戳寸，NLSR仍然會(huì)向故障鄰居發(fā)送 info 興趣包來檢測故障是否恢復(fù)，但此時(shí)發(fā)送 info 興趣包的時(shí)間間隔應(yīng)該相對長一點(diǎn)拷泽，避免由于長期故障導(dǎo)致較大的無用開銷庆揩。需要注意的是，檢測到故障時(shí)NLSR時(shí)無法區(qū)分是鏈路的故障還是遠(yuǎn)端NLSR進(jìn)程的故障跌穗，但是無論是哪種故障發(fā)生订晌，故障鏈路都不會(huì)用于傳輸數(shù)據(jù)，所以在目前的設(shè)計(jì)里不區(qū)分這兩種故障也無傷大雅蚌吸。

  當(dāng)鄰居節(jié)點(diǎn)從故障中恢復(fù)時(shí)锈拨，NLSR會(huì)收到對 info 興趣包的恢復(fù)，接著NLSR便會(huì)將該鄰居的狀態(tài)標(biāo)記為 Active 羹唠。這個(gè)操作會(huì)導(dǎo)致 鄰接LSA 的更新（產(chǎn)生新版本的鄰接 LSA）奕枢，并將新的鄰接LSA傳播到網(wǎng)絡(luò)中，并準(zhǔn)備啟動(dòng)路由表計(jì)算任務(wù)佩微。下圖2展示了節(jié)點(diǎn)A是如何檢測到節(jié)點(diǎn)C的故障缝彬，以及時(shí)如何檢測到節(jié)點(diǎn)B從故障中恢復(fù)的。

  圖2 鄰居故障檢測和恢復(fù)

• 安全（Security）

  每個(gè)NDN的數(shù)據(jù)包（Data Packet）都是經(jīng)過數(shù)字簽名的哺眯，并且生成的數(shù)字簽名是數(shù)據(jù)包組成數(shù)據(jù)包的一部分谷浅。簽名包含名字、內(nèi)容和少量對簽名驗(yàn)證有用的支持?jǐn)?shù)據(jù) [3] 奶卓，支持?jǐn)?shù)據(jù)中很重要的一部分是key locator [1, 3]一疯，它指示了用于給這個(gè)數(shù)據(jù)包簽名的 key 的名稱，這樣接收者就能通過這個(gè)名稱去拉取到給這個(gè)數(shù)據(jù)包簽名的 key（當(dāng)然我們只能拉取到公鑰或證書夺姑，不能拉取到私鑰）墩邀，進(jìn)而驗(yàn)證這個(gè)數(shù)據(jù)包的簽名。

  一個(gè)具有有效簽名的LSA（即盏浙，這個(gè) LSA的簽名是驗(yàn)證通過的）僅僅說明了這個(gè)LSA的簽名是由其 key locator 域指向的 key 的私鑰簽名的眉睹，它并沒有告訴我們擁有這個(gè) key 的路由器是否能合法的生成LSA。舉個(gè)例子來說废膘，攻擊者可以使用其私鑰簽名一個(gè) 前綴LSA（Prefix LSA）竹海，并將該LSA注入到路由系統(tǒng)中（此時(shí)該 LSA的簽名驗(yàn)證是可以通過的，但是實(shí)際上這個(gè)LSA不是一個(gè)合法的 LSA）殖卑。為了檢測簽名信息的有效性站削，我們需要驗(yàn)證此LSA是否是由授權(quán)的NLSR進(jìn)程簽名的，換句話說孵稽，我們需要驗(yàn)證 key 的名字中包含的相關(guān)的NLSR進(jìn)程是授權(quán)的许起。即便如此十偶，攻擊者還是可以使用與某個(gè)有效 key 相同的名字的包，塞入攻擊者自己的key园细。所以惦积，我們需要一個(gè)信任模型來驗(yàn)證 key 的有效性。

  NLSR是一個(gè)域內(nèi)路由協(xié)議（intra-domain routing protocol）猛频，在單個(gè)網(wǎng)絡(luò)域中狮崩，通常會(huì)有一個(gè)網(wǎng)絡(luò)管理員（信任錨）可以驗(yàn)證網(wǎng)絡(luò)中 keys 的真實(shí)性。因此我們將這個(gè)信任錨用于給網(wǎng)絡(luò)中的 key 進(jìn)行簽名和驗(yàn)證鹿寻，這樣做易于構(gòu)建和管理睦柴。我們可以簡單的讓信任錨對所有路由器的公鑰進(jìn)行簽名，但實(shí)際上用一個(gè) key 來對大量的 key 簽名是存在很大的安全風(fēng)險(xiǎn)的毡熏。為了解決這個(gè)問題坦敌，我們在信任錨上設(shè)計(jì)了一個(gè)劃分5個(gè)等級的層級結(jié)構(gòu)，它將信任錨中 key 的簽名職責(zé)限制到一個(gè)較小的范圍痢法。表2展示了每個(gè)等級 key 的命名狱窘，需要注意的是，所有 key 名稱的最后一個(gè)組件（component）都是這個(gè) key 的hash值（在表中未展示出來）财搁，所以當(dāng)某個(gè)路由器發(fā)送興趣包拉取一個(gè) key 時(shí)蘸炸， 總能保證拉取到的 key 是和名稱所匹配的。

  Key Owner	Key Name
  Root	/<network>/keys
  Site	/<network>/keys/<site>
  Operator	/<network>/keys/<site>/%C1.O.N.Start/<operator>
  Router	/<network>/keys/<site>/%C1.O.R.Start/<router>
  NLSR	/<network>/keys/<site>/%C1.O.R.Start/<router>/NLSR

  首先在頂層的是 Root key尖奔，為當(dāng)前網(wǎng)絡(luò)的管理員所擁有搭儒，第二層包含一系列的 site keys，由網(wǎng)絡(luò)中某個(gè)網(wǎng)站的管理員所擁有越锈，并且使用 Root key 進(jìn)行簽名的仗嗦。每個(gè) site key 可以簽名一系列的 operator keys（通常一個(gè)網(wǎng)站由多個(gè)操作員）膘滨，每個(gè) operator key 又能簽名一系列的 router keys甘凭，每個(gè) router key 又能給運(yùn)行在同一個(gè)路由器上的NLSR進(jìn)程簽名NLSR使用的 key，最后火邓，路由器使用 NLSR key 給每個(gè)由NLSR生成的數(shù)據(jù)簽名丹弱。需要注意的是，我們目前的設(shè)計(jì)里使用 CNNx sync/repo 來傳播 keys铲咨，所以所有的 keys 都共享一個(gè)同一個(gè)前綴 /<network>/keys （前文中有提到過這是 CNNx 機(jī)制限制的躲胳，所有用于同步的數(shù)據(jù)都需要共享同一個(gè)相同的前綴），但是我們現(xiàn)在設(shè)計(jì)的 keys 命名方案確實(shí)是一個(gè)層級的結(jié)構(gòu)纤勒。此外坯苹，我們使用兩個(gè)標(biāo)記 %C1.O.N.Start 和 %C1.O.R.Start 來分別指示 operator keys 和 router keys。
  

  圖 3 每個(gè)NLSR包的簽名和認(rèn)證鏈

  NLSR嚴(yán)格執(zhí)行基于信任錨的信任模型摇天，圖3描繪了每個(gè)NLSR包的簽名和認(rèn)證的流程粹湃。當(dāng)NLSR路由器發(fā)送一個(gè)LSA到網(wǎng)絡(luò)中時(shí)恐仑，它會(huì)使用它的 NLSR key 對數(shù)據(jù)包進(jìn)行簽名，并把用來簽名的 NLSR key 的名字放在數(shù)據(jù)包（Data Packet）的 SignedInfo/KeyLocator/KeyName 域里面为鳄。每當(dāng)收到一個(gè)LSA裳仆，NLSR路由器會(huì)從本地的內(nèi)容緩存（content store）或者 repo （key 可能已經(jīng)通過 key repo 進(jìn)行分發(fā) ）中獲取包中指定的 key，并驗(yàn)證內(nèi)容的簽名孤钦，同時(shí)NLSR會(huì)檢查這 key 是否確實(shí)屬于生成LSA的那個(gè)NLSR進(jìn)程歧斟。接著重復(fù)上述過程，直到NLSR拉取到信任錨的自簽 key偏形。如果在這個(gè)過程中任意一步的 key 拉取失敗静袖，或者NLSR發(fā)現(xiàn)拉取到的 key 是由一個(gè)未授權(quán)的 key 簽名的，亦或是最后的驗(yàn)證步驟沒有到達(dá)信任錨俊扭，都認(rèn)為該LSA是非法的勾徽。需要注意的是，一旦一個(gè) key 被驗(yàn)證有效了统扳，我們將記錄這個(gè)信息喘帚，以后再收到由該 key 簽名的數(shù)據(jù)包時(shí)，不需要再對這個(gè) key 進(jìn)行重復(fù)驗(yàn)證咒钟。

評估（EVALUATION）

本節(jié)我們將就處理時(shí)間吹由、消息傳遞開銷v 和收斂時(shí)間三個(gè)方面評估NLSR的性能。所有的測試在六個(gè)具有不同操作系統(tǒng)和系統(tǒng)規(guī)格的異構(gòu)節(jié)點(diǎn)組成的網(wǎng)絡(luò)上進(jìn)行朱嘴，具體的網(wǎng)絡(luò)拓?fù)淙鐖D4所示倾鲫。需要特別說明的是，我們?yōu)榱嗽诙虝r(shí)間內(nèi)對協(xié)議進(jìn)行測試萍嬉，我們將刷新時(shí)間設(shè)置為30分鐘乌昔，而不是幾天。

圖 4 網(wǎng)絡(luò)拓?fù)?/div>

圖 5 每個(gè)節(jié)點(diǎn)上NLSR進(jìn)程的CPU的利用率

圖5展示了每個(gè)節(jié)點(diǎn)上NLSR進(jìn)程的CPU利用率壤追，圖中節(jié)點(diǎn)名稱后括號內(nèi)的數(shù)字代表該節(jié)點(diǎn)的度數(shù)（即該節(jié)點(diǎn)鄰居的個(gè)數(shù)）徐裸。從圖中可以看出形葬，具有較高連通性的節(jié)點(diǎn)的CPU占用率較高，換句話說，在同一個(gè)節(jié)點(diǎn)上缸棵，計(jì)算量隨鏈接數(shù)的增加而增加木柬。這是因?yàn)樵诿總€(gè)鏈路上都需要運(yùn)行Dijstra算法計(jì)算最短路徑（在 3.4 節(jié)有詳細(xì)的介紹）锐朴，這會(huì)帶來更高的消息傳遞開銷和更多的路由計(jì)算囱皿。

圖 6 平均CPU利用率

圖6展示了在使用和未使用信任模型時(shí)NLSR的處理開銷對比。從圖中可以看出肛走，即便使用了信任模型漓雅，需要使用多級的 key 來進(jìn)行簽名和驗(yàn)證，NLSR也幾乎不會(huì)產(chǎn)生太多額外的開銷。這是因?yàn)閷?shí)際上邻吞，NDN網(wǎng)絡(luò)本來就需要對所有傳出的數(shù)據(jù)包進(jìn)行簽名庶灿，使用信任模型只是多了驗(yàn)證的步驟，驗(yàn)證過程需要更多時(shí)間去本地的存儲(chǔ)庫中遞歸獲取多個(gè) key 并執(zhí)行驗(yàn)證吃衅。然后往踢，由于這些都是本地操作（作者的實(shí)驗(yàn)環(huán)境中，keys 應(yīng)該時(shí)提前分發(fā)到每個(gè)節(jié)點(diǎn)上的徘层，每個(gè)節(jié)點(diǎn)只需要去本地的 key repo 就能拉取到需要的 key ）而且只有需要新的 key 時(shí)才會(huì)去遞歸驗(yàn)證峻呕，已經(jīng)驗(yàn)證的 key 可以反復(fù)使用，所以這只需要較低的開銷趣效。圖6還展示了瘦癌，與使用單路徑路由相比，使用多路徑路由會(huì)占用更多的CPU跷敬。由于兩種方案的消息傳遞開銷時(shí)相同的讯私，這種差異的原因主要是多路徑路由計(jì)算的時(shí)候需要對每個(gè)鄰居計(jì)算一次然后合并，計(jì)算成本比較高西傀。

圖 7 數(shù)據(jù)包發(fā)送和接收的數(shù)量

圖7展示了每個(gè)節(jié)點(diǎn)平均的消息傳遞開銷斤寇，我們分別設(shè)置 Sync 的 Root Advise （RA）消息的存活時(shí)間為10 ~ 30秒（默認(rèn)為 20 秒），圖中數(shù)字描述的是每個(gè)節(jié)點(diǎn)的 NLSR 和 Sync 平均發(fā)送的興趣包的數(shù)量和接收到對應(yīng)數(shù)據(jù)包的數(shù)量拥褂。NLSR進(jìn)程只發(fā)送 info 興趣包娘锁，這個(gè)和 Root Advise （RA）的存活期長短是無關(guān)的，所以在只改變 RA 消息的存活期長短的情況下饺鹃，NLSR發(fā)送的 info 興趣包的數(shù)量是不變的莫秆。Sync 產(chǎn)生的興趣包主要是 RA 興趣包，RA 興趣包是周期性發(fā)送的悔详，但是只有在hash值不一致時(shí)才會(huì)收到回復(fù)镊屎，因此 RA 興趣包的數(shù)量會(huì)高于 RA 回復(fù)包的數(shù)量。正如預(yù)期的一樣茄螃，設(shè)置較長的發(fā)送 RA 興趣包的時(shí)間間隔缝驳，RA 興趣包的發(fā)送數(shù)量會(huì)降低。Sync 除了發(fā)送 RA 興趣包之外责蝠，還會(huì)發(fā)送 節(jié)點(diǎn)拉取（NF）興趣包党巾，來獲取 Sync 樹上的節(jié)點(diǎn)。NF 包帶來的消息傳遞開銷比 RA 包的要小驳规，尤其是當(dāng)網(wǎng)絡(luò)比較穩(wěn)定的時(shí)候。拉取 LSA 的興趣包是向所有的端口廣播的医男，但是只有擁有該缺失的 LSA 的鄰居會(huì)回復(fù)，所以 LSA 興趣包的數(shù)量要高于 LSA 數(shù)據(jù)包的數(shù)量刀森。

圖 8 使用和不使用多路徑的情況下的收斂時(shí)間

image

在測試收斂時(shí)間時(shí)也是用和上面一樣的網(wǎng)絡(luò)拓?fù)洌趩?dòng)所有的節(jié)點(diǎn)后报账，等待足夠的時(shí)間研底，使得所有節(jié)點(diǎn)的 LSDBs 相互保持同步。當(dāng)網(wǎng)絡(luò)收斂后透罢，我們使用 ccnping 工具 [7] 來生成網(wǎng)絡(luò)流量榜晦。ccnping 服務(wù)器放置在 node6 上，在 node2 上啟動(dòng) ccnping 客戶端發(fā)送 ccnping 興趣包（ping）羽圃，設(shè)置超時(shí)時(shí)間為4秒乾胶。在60秒后，我們手動(dòng)關(guān)閉 node4朽寞，這將強(qiáng)制 node2 換一條路徑去訪問 node6 上的服務(wù)识窿。圖8展示了使用多路徑路由的好處：node2 不需要重新計(jì)算路徑，它只需要在檢測到 node4 故障時(shí)簡單切換到另一條可用的路徑即可脑融。相比之下腕扶，只使用單路徑路由花費(fèi)了大概1分鐘的時(shí)間才找到新的可用路徑，并且在180秒重新啟動(dòng) node4時(shí)回到原來的路徑吨掌。收斂的時(shí)間可以通過 info 興趣包的超時(shí)時(shí)間以及重試次數(shù)來控制半抱，默認(rèn)情況下，超時(shí)時(shí)間為60秒膜宋，在將節(jié)點(diǎn)或者鏈接聲明為down之前的重試次數(shù)為3（間隔 15秒）窿侈。

相關(guān)工作（Related Work）

據(jù)我們所知，在NDN網(wǎng)絡(luò)的路由領(lǐng)域只有非常有限的相關(guān)工作秋茫。Dai 等人提出的路由協(xié)議 [2] 表面上與NLSR類似史简，但還是與NLSR存在以下幾個(gè)方面的不同：

• 首先，他們使用 OSPF 收集網(wǎng)絡(luò)拓?fù)湫畔⒉⒂?jì)算最短路徑肛著，而我們使用 Sync 傳輸 LSAs圆兵，而不是用泛洪的方式殉农；
• 其次超凳，他們的路由消息不是作為興趣包/數(shù)據(jù)包發(fā)送的暂雹，因此無法享受簽名更新的好處（即安全性）杭跪；
• 最后，他們的多路徑轉(zhuǎn)發(fā)僅限于由多個(gè)生產(chǎn)者提供的內(nèi)容现斋，例如：在多個(gè)服務(wù)器副本中進(jìn)行任播庄蹋，雖然我們也支持這種情況，但是我們也支持同一生產(chǎn)者的多個(gè)路徑倦西。

在 [6]扰柠，作者提出了一種在NDN中基于控制器的路由方案（CRoS）∪霸妫控制器存儲(chǔ)網(wǎng)絡(luò)拓?fù)涮蛱冢?jì)算路由稳诚，并存儲(chǔ)命名數(shù)據(jù)的位置采桃，以便他們可以給網(wǎng)絡(luò)中任何的命名數(shù)據(jù)安裝路由普办。雖然這種使用分散控制器的想法很有趣徘钥，但是網(wǎng)絡(luò)仍然需要泛洪特殊格式的興趣包用來檢索控制器舆驶，這會(huì)帶來巨大的開銷沙廉。

結(jié)論（Conclution）

雖然基于IP網(wǎng)絡(luò)的鏈路狀態(tài)的路由協(xié)議設(shè)計(jì)是一個(gè)被研究的很透徹的一個(gè)話題撬陵，但是我們設(shè)計(jì)NLSR的過程也是一個(gè)很棒的學(xué)習(xí)經(jīng)歷。為了滿足NDN的路由要求草添，NLSR脫離了常規(guī)的路由協(xié)議使用單路徑的方法远寸，而是為每個(gè)名稱前綴提供多個(gè)轉(zhuǎn)發(fā)選項(xiàng)。

我們從這次實(shí)踐中獲得的主要收獲是NLSR作為一個(gè)在NDN上開發(fā)應(yīng)用程序的具體方案倡怎，它要求：

• 仔細(xì)考慮命名空間的設(shè)計(jì)监署；
• 一個(gè)用于驗(yàn)證的信任模型的開發(fā)钠乏；
• 使用興趣包/數(shù)據(jù)包交換來實(shí)現(xiàn)路由消息的更新這一NDN新的設(shè)計(jì)模式的調(diào)整晓避。

此外暑塑，使用命名數(shù)據(jù)通信也可以實(shí)現(xiàn)同步事格，這促進(jìn)了分布式系統(tǒng)中的數(shù)據(jù)集同步。我們的NLSR設(shè)計(jì)中使用 Sync 來使得路由協(xié)議更加健壯逢捺，而且在概念上更加簡單。

迄今為止我們的研究成果意味著我們邁向了基于NDN的路由系統(tǒng)開發(fā)的第一步余佛，我們正在進(jìn)行的工作包括實(shí)際部署和操作恨憎、探索新的路由方案并擴(kuò)展到域間路由憔恳。

引用（Reference）

[1] C. Bian, Z. Zhu, E. Uzun, and L. Zhang. Deploying key management on NDN testbed. Technical Report NDN-0009, Febryary 2013.

[2] H. Dai, J. Lu, Y. Wang, and B. Liu. A two-layer intra-domain routing scheme for Named Data Networking. Globecom 2012 - Next Generation Networking and Internet Symposium , December 2012.

[3] V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs, and R. L. Braynard. Networking named content. In Proceedings of ACMCoNEXT, 2009.

[4] L. Zhang et al. Named data networking (NDN) project. Technical Report NDN-0001, PARC, October 2010.

[5] PARC.CCNx open srouce platform. http://www.ccnx.org.

[6] J. Torres, L. Ferraz, and O. Duarte. Controller-based routing scheme for Named DataNetwork. Technical report, Electrical Engineering Program, COPPE/UFRJ,December 2012.

[7] University Of Arizona. ccnping. https://github.com/NDN-Routing/ccnping.

[8] L. Wang, A. M. Hoque, C. Yi, A. Alyyan, and B. Zhang. OSPFN:An OSPFbased routing protocol for Named Data Networking. Technical Report NDN-0003, July 2012.

[9] C. Yi, A. Afanasyev, L. Wang, B. Zhang, and L. Zhang. Adaptive forwarding in named data networking. SIGCOMM Comput. Commun. Rev., 42(3):62–67, June 2012.