【文章內(nèi)容簡介】 就 必須 被丟棄，因?yàn)楦?節(jié)點(diǎn)當(dāng)前所保存的信息相比，接收到的信息更加陳舊。 另外，節(jié)點(diǎn)為了修 復(fù)路由路徑中丟失了的或者過期了的下一跳時(shí)，可能會改變其路由表項(xiàng) 中的目的序列號，這也是除了以上情況以外唯一要改變目的序列號的情況。節(jié)點(diǎn)通過查詢其路由表來查詢都有哪些目的節(jié)點(diǎn)使用了這個(gè)不可使用的下一跳節(jié)點(diǎn)。在這種情況下，對于每一個(gè)使用這個(gè)節(jié)點(diǎn)的目的節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)都會增加其序列號并把此路徑標(biāo)記為不可用（并見 ， ）。一旦節(jié)點(diǎn)接收到了一個(gè)足夠新的（也就是包含大于等于本節(jié)點(diǎn)所記錄的序號），并且是來自于已經(jīng)標(biāo)記相應(yīng)路由表項(xiàng)為不可用的節(jié)點(diǎn) 的路由信息時(shí)，當(dāng)前節(jié)點(diǎn)應(yīng)該以新的信息來更新其路由表信息。 RFC 3561 AODV 路由 2020 年 7 月 Perkins, et. Al. 試驗(yàn)版 原文頁碼 13 節(jié)點(diǎn)需要改變目的路由表項(xiàng)中的序列號，當(dāng)以下情況發(fā)生時(shí)： 它自己就是目的節(jié)點(diǎn)，并且提供了一個(gè)到它自己的新的路由，或者 它接收到了一個(gè)擁有關(guān)于目的節(jié)點(diǎn)序列號的新信息的 AODV消息，或者 朝向目的 節(jié)點(diǎn) 的路徑過期了或者崩潰了。 . 路由表項(xiàng)和先驅(qū)列表 當(dāng)一個(gè)節(jié)點(diǎn)從它的鄰居接收到一條 AODV 控制包時(shí)，以及為某個(gè)特定的目的節(jié)點(diǎn)或目的子網(wǎng)創(chuàng)建或更新它的路由表的時(shí)候，它就會去檢查它的路由表里是否有一個(gè)表項(xiàng)對應(yīng)到那個(gè)目的。當(dāng)沒有相關(guān)的表項(xiàng)時(shí)，新 的表項(xiàng)就會被創(chuàng)建。序列號要么就是從 AODV 控制消息里提取的，要么就干脆在路由表項(xiàng)里“序列號有效”這個(gè)位置標(biāo)明“無效”。僅在新的序列號滿足下列三種條件時(shí)路由會更新： (i) 新序列號要比路由表里原來的原目的序列號大。 (ii) 序列號相等，但是新信息里包含的跳數(shù)加一還要比原來的跳數(shù)小。 (iii) 新序列號是未知的。 路由表里的“有效期”要么從控制包里得到，要么設(shè)置為 ACTIVE_ROUTE_TIMEOUT（有效路由超時(shí)）。這條路由現(xiàn)在就可以用作發(fā)送數(shù)據(jù)包，并且能滿足其他的路由請求。 每當(dāng)一條路由被用來轉(zhuǎn)發(fā)一個(gè)數(shù)據(jù)包時(shí)，它里面源 、目的和下一條節(jié)點(diǎn)的“路由有效期”這一項(xiàng)會被更新，新的值不小于當(dāng)前時(shí)間加上 ACTIVE_ROUTE_TIMEOUT。由于每對發(fā)起節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的路由應(yīng)當(dāng)是對稱的，每個(gè)節(jié)點(diǎn)的上一跳的路由有效期（即回到發(fā)起節(jié)點(diǎn)路徑上的下一個(gè)節(jié)點(diǎn)）也會被更新為不小于當(dāng)前時(shí)間加上 ACTIVE_ROUTE_TIMEOUT。不管目的是單個(gè)的節(jié)點(diǎn)還是一個(gè)子網(wǎng)，每當(dāng)路由被用到的時(shí)候，路由有效期都會被更新。 RFC 3561 AODV 路由 2020 年 7 月 Perkins, et. Al. 試驗(yàn)版 原文頁碼 14 對每個(gè)放在路由表項(xiàng)里的有效路由，節(jié)點(diǎn)還會維護(hù)一張先驅(qū)表，這些先驅(qū)可能會沿著這條路由轉(zhuǎn)發(fā)數(shù)據(jù)包。當(dāng)檢測到下一跳斷開時(shí)，這 些先驅(qū)就會從本節(jié)點(diǎn)收到通知。路由表項(xiàng)里的先驅(qū)列表包含的是都是本節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，路由回復(fù)信息將會被發(fā)送到這些節(jié)點(diǎn)。 . 生成路由請求 當(dāng)一個(gè)節(jié)點(diǎn)無法找到一個(gè)可用的到某個(gè)節(jié)點(diǎn)的路由時(shí)，它就會廣播一條 RREQ 消息。出現(xiàn)這種情況可能是由于這個(gè)節(jié)點(diǎn)以前并不知道有這么一個(gè)目的節(jié)點(diǎn)，也可能是由于以前到該目的節(jié)點(diǎn)的有效路由過期了，或是被標(biāo)記為無效。 RREQ 消息的“ Destination Sequence Number”這個(gè)域應(yīng)當(dāng)填最近一次獲得的該節(jié)點(diǎn)的目的節(jié)點(diǎn)序列號，這個(gè)序列號直接 就 從路由表里的“ Destination Sequence Number”域復(fù)制過去。 如果尚未獲得任何目的節(jié)點(diǎn)序列號，則“序列號未知”標(biāo)志必須被置位。 RREQ 里的“ Originator Sequence Number”就是發(fā)起節(jié)點(diǎn)自己的序列號，在把它放入 RREQ 消息里時(shí)，它得先自增 1。消息里“ RREQ ID”則是將當(dāng)前節(jié)點(diǎn)以前用過的 RREQ ID 加一。每個(gè)節(jié)點(diǎn)只維護(hù)一個(gè) RREQ ID?！?Hop Count”填 0。 在廣播 RREQ 消息之前，發(fā)起節(jié)點(diǎn)會將消息的 RREQ ID 和 Originator IP address（就是它自己的 IP 地址）緩存一段時(shí)間 ，這個(gè)時(shí)間由“ PATH_DISCOVERY_TIME”來決定。這樣，當(dāng)這個(gè)節(jié)點(diǎn)從鄰居那里收到具有相同 RREQ ID 和 Originator IP address 的 RREQ 消息時(shí)，它將會認(rèn)為這是一個(gè)發(fā)回來的包而 將它丟棄。 一個(gè)發(fā)起節(jié)點(diǎn)總是想和目的節(jié)點(diǎn)建立雙向的通信，即，僅僅是發(fā)起節(jié)點(diǎn)有到目的節(jié)點(diǎn)的路由還不夠，目的節(jié)點(diǎn)還必須擁有回到發(fā)起節(jié)點(diǎn)的路由。為了 盡力有效的實(shí)現(xiàn)這個(gè)特性，每個(gè)中間節(jié)點(diǎn)在生成 RREP 回發(fā)給發(fā)起節(jié)點(diǎn)的同時(shí)（見 節(jié)），還必須執(zhí)行某種操作，用于告知目的節(jié)點(diǎn)一條返回發(fā)起節(jié)點(diǎn)的路由。 當(dāng)發(fā)起節(jié)點(diǎn)需要讓 中間節(jié)點(diǎn)作出上述操作的時(shí)候，它需要將 RREQ 的“ G”標(biāo)志位置位 （ Gratuitous RREP flag 免費(fèi)路由回復(fù)標(biāo)志） 。有關(guān)中間節(jié)點(diǎn)如何處理帶“ G”標(biāo)志位的 RREQ 消息的細(xì)節(jié)，請見 節(jié)。 一個(gè)節(jié)點(diǎn)每秒鐘發(fā)出的 RREQ 消息數(shù)目受到 RREQ_RATELIMIT 的限制，當(dāng)廣播出去一個(gè) RREQ 消息后， 它會等待 RREP 消息（或其他帶有目的節(jié)點(diǎn)的當(dāng)前路由信息的控制消息 ）。如果路由信息在 NET_TRAVERSAL_TIME 毫秒內(nèi)還沒被收到，這個(gè)節(jié)點(diǎn)就可以嘗試著發(fā)送一個(gè)新的 RREQ 消息來再次尋找路由。最多可 以以最大的 TTL 值發(fā)送RREQ_RETRIES 次請求。 每次發(fā)送新的 RREQ 都必須將 RREQ ID 加一。 IP 頭里的 TTL 值由 節(jié)描述的法則來確定，用來控制 RREQ 消息的散布范圍。 RFC 3561 AODV 路由 2020 年 7 月 Perkins, et. Al. 試驗(yàn)版 原文頁碼 15 等待路由的數(shù)據(jù)包（比如在送出 RREQ 消息后還在等待 RREP 消息）應(yīng)當(dāng)被存在緩沖區(qū)里。緩沖應(yīng)當(dāng)遵循“先進(jìn)先出”原則。如果一個(gè)路由尋找過程已經(jīng)在最大的 TTL 值下嘗試了 RREQ_RETRIES 次而還沒有收到 RREP 時(shí)， 所有被緩沖的送往這個(gè)目的的數(shù)據(jù)包都應(yīng)當(dāng)被丟棄，并且還應(yīng)當(dāng)向應(yīng)用程序回送一個(gè)“目的不可達(dá)”消息。 為減少網(wǎng)絡(luò)擁塞 ，源節(jié)點(diǎn)向單個(gè)目的節(jié)點(diǎn)建立連接的嘗試必須遵從二 的 冪 次 遞減原則。當(dāng)節(jié)點(diǎn)第一次廣播一個(gè) RREQ消息時(shí)，它會等待 NET_TRAVERSAL_TIME 毫秒來接收 RREP消息。如果在這段時(shí)間內(nèi) RREP 沒有到達(dá)，源節(jié)點(diǎn)就會送出一個(gè)新的 RREQ。第二個(gè) RREQ的回復(fù)消息 RREP 的等待時(shí)間就應(yīng)當(dāng)遵從二的冪 次 遞減原則 ，也就是，這個(gè)等待時(shí)間應(yīng)該為2 NET_TRAVERSAL_TIME 毫秒。如果在這段時(shí)間內(nèi) RREP 消息仍然沒到，另一個(gè) RREQ就又可以送出去了。在第一個(gè) RREQ 消息發(fā)出去以后，最多還可以再嘗試 RREQ_RETRIES次。對每一次的嘗試，它的等待時(shí)間都應(yīng)當(dāng)是上一次嘗試時(shí)間的 2 倍。這樣就從等待時(shí)間上保證遵從了網(wǎng)絡(luò)協(xié)議的二的冪次遞減原則。 . 控制路由請求消息的傳播 為了防止 RREQ 消息在整個(gè)網(wǎng)絡(luò)內(nèi)散布得到處都是，發(fā)起節(jié)點(diǎn)應(yīng)當(dāng)逐次的擴(kuò)大搜索范圍。在范圍逐次擴(kuò)大的搜索中，發(fā)起節(jié)點(diǎn)最初會設(shè)置 RREQ 包的 IP 頭內(nèi)的 TTL 值為TTL_START ， 設(shè) 置 等待 RREP 的超時(shí)時(shí)間為 RING_TRAVERSAL_TIME 毫秒。RING_TRAVERSAL_TIME 的 計(jì) 算 方 法 會 在 第 10 節(jié) 描 述 。 用 于 計(jì) 算RING_TRAVERSAL_TIME 的 TTL_VALUE 的值被設(shè)置成等于 IP 頭中的 TTL 值。如果發(fā)出RREQ 后等待 RREP 超時(shí)，發(fā)起節(jié)點(diǎn)將再次廣播 RREQ，而這次的 TTL 值將被加上TTL_INCREMENT。這樣一直持續(xù)到 RREQ 包內(nèi)的 TTL 達(dá)到閾值 TTL_THRESHOLD。在達(dá)到閾值后，每次使用的 TTL 都將被設(shè)置為 NET_DIAMETER。每次等待 RREP 的超時(shí)時(shí)間都是 RING_TRAVERSAL_TIME。如果需要每次路由尋找都在整個(gè) Ad Hoc 網(wǎng)絡(luò)范圍內(nèi)進(jìn)行，可以將 TTL_START 和 TTL_INCREMENT 都設(shè)置為等于 NET_DIAMETER 來達(dá)到目的。 RFC 3561 AODV 路由 2020 年 7 月 Perkins, et. Al. 試驗(yàn)版 原文頁碼 16 在一條失效的路由表項(xiàng)里存儲的跳數(shù)（ Hop Count）代表的是最后一次獲得的到目的節(jié)點(diǎn)的跳數(shù)。如果 又需要新建一條到達(dá)該目的節(jié)點(diǎn)的路由（比如路由丟失的情況），發(fā)出的RREQ 的 IP 頭內(nèi)的 TTL 值將會被設(shè)置成 這個(gè)失效的 跳數(shù)加上 TTL_INCREMENT。從這以后的每次超時(shí)， TTL 都將增加 TTL_INCREMENT，直到 TTL 等于 TTL_THRESHOLD，在此以后， TTL 將等于 NET_DIAMETER。一旦 TTL 等于 NET_DIAMETER，等待 RREP 的超時(shí)時(shí)間就將被設(shè)置成 NET_TRAVERSAL_TIME，就像在 節(jié)里被討論的那樣。 一條失效的路由表項(xiàng)仍然需要在路由表里保存到當(dāng)前時(shí)刻加上擦除時(shí)間（ current_time + DELETE_PERIOD），在此期間不應(yīng)當(dāng)被擦除（見 節(jié)）。否則，和這條路由有關(guān)的軟件信息（比如失效前最后一次獲得的跳數(shù) Hop Count）就會丟失。此外， 還可以將路由表項(xiàng)從失效到被擦除的時(shí)間配置 得 更 長一些。任何正在等待 RREP 的路由表項(xiàng)都不應(yīng)當(dāng)在（ current_time + 2 NET_TRAVERSAL_TIME）這個(gè)時(shí)刻之前被擦除 掉。 . 處理和轉(zhuǎn)發(fā)路由請求 當(dāng)一個(gè)節(jié)點(diǎn)收到一條 RREQ 消息時(shí)，它首先創(chuàng)建一個(gè)到前一跳節(jié)點(diǎn)的路由，或者更新原 來已有 的，但 序列號 不對的 到上一 跳的路 由（見 節(jié)）。然后 檢查它 在PATH_DISCOVERY_TIME 時(shí)間內(nèi)是否受到過具有相同 Originator IP Address 和 RREQ ID 的RREQ 消息。如果已經(jīng)接收過了，那么這個(gè)節(jié)點(diǎn)就 會丟棄這個(gè) RREQ，不作任何操作。這一節(jié)的余下部分將討論對沒有丟棄的 RREQ 請求該如何處理。 首先，該節(jié)點(diǎn)會將 RREQ 消息內(nèi)的跳數(shù)加一，表明該 RREQ 又跳過了一個(gè)中間節(jié) 點(diǎn)。然后該節(jié)點(diǎn)會搜索到發(fā)起節(jié)點(diǎn) IP 地址的反向路由（見 節(jié)），使用的是最長前綴匹配法。如果有必要，這條路由會被創(chuàng)建，或者用 RREQ 消息內(nèi)的 Originator Sequence Number 來更新。當(dāng)該節(jié)點(diǎn)接收到一條 RREP 需要回傳到發(fā)起節(jié)點(diǎn)時(shí)，這條路由就會被用到（ RREP 消息送達(dá)的目的如果和 RREQ 消息內(nèi)的 Originator IP Address 一樣，則說明這條 RREP 消息是對該 RREQ 的回復(fù) ，于是在接收 RREQ 時(shí)創(chuàng)建的反向路由就可以被用到了） 。 當(dāng)反向路由被創(chuàng)建或更新時(shí)，將對它執(zhí)行以下操作。 1. RREQ 消息內(nèi)的 Originator Sequence Number（發(fā)起節(jié)點(diǎn)序列號）會被用來和反向路由里對應(yīng)的目的節(jié)點(diǎn)序列號比較，如果比已經(jīng)在路由表里的那個(gè)大，那么就會被復(fù)制到路由表里面。 2. 路由表項(xiàng)里“序列號有效”一欄會被設(shè)置為“有效” 3. 反向路由表項(xiàng)里的“下一跳”將被設(shè)置為傳遞 RREQ 給本節(jié)點(diǎn)的那個(gè)相鄰節(jié)點(diǎn)（這個(gè)地址就是 RREQ 數(shù)據(jù)包 IP 頭內(nèi)的源 IP 地址，且大多數(shù)情況下它并不等于 RREQ 消息內(nèi)的發(fā)起節(jié)點(diǎn)地址） RFC 3561 AODV 路由 2020 年 7 月 Perkins, et. Al. 試驗(yàn)版 原文頁碼 17 4. 反向路由表項(xiàng)里“跳數(shù)”直接從 RREQ 消息內(nèi)的“跳數(shù)”復(fù)制而來。 每當(dāng)接收到一條 RREQ 消 息時(shí)，指向發(fā)起節(jié)點(diǎn) IP 地址的反向路由的有效期將被設(shè)置為ExistingLifetime 和 MinimalLifetime 中的較大者。這里： MinimalLifetime = (current time + 2 NET_TRAVERSAL_TIME – 2 HopCount NODE_TRAVERSAL_TIME) 節(jié)點(diǎn)可以用這條反向路由來轉(zhuǎn)發(fā)其他路由的數(shù)據(jù)包，只要它們走的路徑相同。 如果一個(gè)節(jié)點(diǎn)不 生成 RREP 消息（按照 節(jié)的處理規(guī)則來生成），并且 接收到的 RREQ包 IP 頭里的 TTL 大于 1，那么這個(gè)節(jié)點(diǎn)就將更新這條 RREQ 消息并且在它的每個(gè)網(wǎng)絡(luò)接口上向 廣播這個(gè) RREQ 消息（見 節(jié)）。對 RREQ 做的更新是： IP 頭內(nèi) TTL或者跳數(shù)限制將被減一， RREQ 消息內(nèi)的“跳數(shù)”則將被加一，用于對新的一跳計(jì)數(shù)。最后，Destination Sequence number 這一欄將被設(shè)置為 RREQ 消息內(nèi)對應(yīng)值和節(jié)點(diǎn)本身維護(hù)的目的節(jié)點(diǎn)序列號之間的大者。 但是，轉(zhuǎn)發(fā)節(jié)點(diǎn)一定不能修改它維護(hù)的目的節(jié)點(diǎn)序列號，即使接收到的 RREQ 消息內(nèi)的這個(gè)序列號比當(dāng)前維護(hù)的值要大也不行。 反之，如果 一個(gè)節(jié)點(diǎn)生成 RREP 消息，那么它就會丟棄掉 RREQ。注意，如果 中間節(jié)點(diǎn)對送往特定目的節(jié)點(diǎn)的 RREQ 的每一次傳遞都作出回復(fù)的話，可能會導(dǎo)致目的節(jié)點(diǎn)收不到任何路由發(fā)現(xiàn)信息 （有