路由查找演算法
㈠ 使用二叉線索能否查找路由表
使用CIDR後，由於要尋找最長前綴匹配，使路由表的查找過程變得更加復雜了。當路由表的項目數很大時，怎樣設法減小路由表的查找時間就成為一個非常重要的問題。例如，連接路由器的線路的速率為10Gbit/s，而分組的平均長度為2000bit，那麼路由器就應當平均每秒鍾能夠處理500萬個分組(常記為5Mpps)。或者說，路由器處理一個分組的平均時間只有200ns(1ns=10-9秒)。因此，查找每一個路由所需的時間是非常短的。可見在路由表中必須使用很好的數據結構和使用先進的快速查找演算法，這一直是人們積極研究的熱門課題。對無分類編址的路由表的最簡單的查找演算法就是對所有可能的前綴進行循環查找。例如，給定一個目的地址D。對每一個可能的網路前綴長度M，路由器從D中提取前M個位成一個網路前綴，然後查找路由表中的網路前綴。所找到的最長匹配就對應於要查找的路由。這種最簡單的演算法的明顯缺點就是查找的次數太多。最壞的情況是路由表中沒有這個路由。在這種情況下，演算法仍要進行32次(具有32位的網路前綴是一個特定主機路由)。就是要找到一個傳統的B類地址(即/16)，也要查找16次。對於經常使用的默認路由，這種演算法都要經歷31次不必要的查找。為了進行更加有效的查找，通常是把無分類編址的路由表存放在一種層次的數據結構中，然後自上而下地按層次進行查找。這里最常用的就是二叉線索(binary trie)"，它是一種特殊結構的樹。IP地址中從左到右的比特值決定了從根節點逐層向下層延伸的路徑，而二叉線索中的各個路徑就代表路由表中存放的各個地址。
㈡ 路由器的原理
路由器的概念及基本構成
路由器是一種用於網路互連的計算機設備，它工作在 OSI 參考模型的第三層
(網路層)，為不同的網路之間報文尋徑並存儲轉發。
作為路由器，必須具備：
Ⅰ 兩個或兩個以上的介面：用於連接不同的網路。
Ⅱ 協議至少實現到網路層：只有理解網路層協議才能與網路層通訊。
Ⅲ 至少支持兩種以上的子網協議：異種子網互聯。
Ⅳ 具有存儲、轉發、尋徑功能 ：實現速率匹配與路由尋徑。
Ⅴ 一組路由協議：包括域內路由協議、域間路由協議。
路由器的作用
Ⅰ 異種網路互連：主要是具有異種子網協議的網路互連。
Ⅱ 子網協議轉換：不同子網間包括區域網和廣域網間協議轉換。
Ⅲ 路由(尋徑)：路由表建立、刷新、查找。
Ⅳ 速率適配：不同介面具有不同的速率，路由器可以利用自己 緩存及流控協議適配。
Ⅴ 隔離網路：防止廣播風暴，網路安全(防火牆)。
Ⅵ 報文分片與重組：介面的 MTU 不同，超過介面的 MTU 的報文會被分片，到達目的地的報文會被重組。
Ⅶ備份、流量流控：主備線路的切換及復雜的流量控制。
路由器工作原理
路由器中時刻維持著一張路由表，所有報文的發送和轉發都通過查找路由表。從相應埠發送。這張路由表可以是靜態配置的，也可以是動態路由協議產生的。物理層從路由器的一個埠收到一個報文，上送到數據鏈路層。數據鏈路層去掉鏈路層封裝，根據報文的協議域上送到網路層。網路層首先看報文是否是送給本機的，若是，去掉網路層封裝，送給上層。若不是，則根據報文的目的地址查找路由表，若找到路由，將報文送給相應埠的數據鏈路層，數據鏈路層封裝後，發送報文。若找不到路由，報文丟棄。
電子產品世界
路由器工作原理
手機與無線通信 作者：何富和 時間：2015-05-27來源：電子產品世界
導讀：說起路由器，大家對它一定非常熟悉吧，上網都靠他，但它是靠什麼原理工作的呢，它的工作流程是怎樣呢?今天小編帶大家了解一下路由器的工作原理。
路由器的概念及基本構成
路由器是一種用於網路互連的計算機設備，它工作在 OSI 參考模型的第三層
(網路層)，為不同的網路之間報文尋徑並存儲轉發。
作為路由器，必須具備：
Ⅰ 兩個或兩個以上的介面：用於連接不同的網路。
Ⅱ 協議至少實現到網路層：只有理解網路層協議才能與網路層通訊。
Ⅲ 至少支持兩種以上的子網協議：異種子網互聯。
Ⅳ 具有存儲、轉發、尋徑功能 ：實現速率匹配與路由尋徑。
Ⅴ 一組路由協議：包括域內路由協議、域間路由協議。
路由器的作用
Ⅰ 異種網路互連：主要是具有異種子網協議的網路互連。
Ⅱ 子網協議轉換：不同子網間包括區域網和廣域網間協議轉換。
Ⅲ 路由(尋徑)：路由表建立、刷新、查找。
Ⅳ 速率適配：不同介面具有不同的速率，路由器可以利用自己 緩存及流控協議適配。
Ⅴ 隔離網路：防止廣播風暴，網路安全(防火牆)。
Ⅵ 報文分片與重組：介面的 MTU 不同，超過介面的 MTU 的報文會被分片，到達目的地的報文會被重組。
Ⅶ備份、流量流控：主備線路的切換及復雜的流量控制。
路由器工作原理
路由器中時刻維持著一張路由表，所有報文的發送和轉發都通過查找路由表。從相應埠發送。這張路由表可以是靜態配置的，也可以是動態路由協議產生的。物理層從路由器的一個埠收到一個報文，上送到數據鏈路層。數據鏈路層去掉鏈路層封裝，根據報文的協議域上送到網路層。網路層首先看報文是否是送給本機的，若是，去掉網路層封裝，送給上層。若不是，則根據報文的目的地址查找路由表，若找到路由，將報文送給相應埠的數據鏈路層，數據鏈路層封裝後，發送報文。若找不到路由，報文丟棄。
子網尋徑及路由
標準的尋徑表表目是一個二維組(信宿網路地址，下一驛站地址)，其中不攜帶子網信息，不能滿足子網尋徑。引入子網編址以後，子網尋徑表的每一表目中加入子網模，於是子網尋徑表表目變為三維組：子網模、信宿網路地址、下一驛站地址。
路由演算法、路由協議、尋徑
路由器依據路由表來為報文尋徑，路由表由路由協議建立和維護。路由協議的設計則是依據某種路由演算法。
選徑是否是最佳：
以什麼參數來衡量路由，如時延、距離、中間網關數等。
簡潔性：路由演算法應設計的盡可能簡潔。
強壯性：路由演算法必須具有魯棒性，應經得起各種網路環境的考驗。
快速收斂性：即所有路由器就最優路徑達成一致的過程路由演算法如果收斂的慢，就會引起路徑循環或網路消耗。
靈活性、彈性：路由演算法能否適應網路環境的各種變化，例如網路帶寬、路由器的緩存、網路時延等發生變化，路由演算法能否根據這些變化做出調整。路由表包含的信息用來交換路由信息和選擇最佳路由路由表是路由器的核心，其中的路由信息來源有兩種：一種是手動添加的靜態路由，另外一種是路由器運行過程中由動態路由協議學習而得來。路由演算法使用了許多不同的權決定最佳路由。
通常採用的權如下：
Ⅰ 路徑距離：指所經過的每條鏈路的權值之和，有的路由協議指節點數目;
Ⅱ 可靠性：指網路鏈路是否容易出故障;
Ⅲ 時延：指網路鏈路造成的網路延時;
Ⅳ 帶寬：指鏈路傳輸信息流容量的能力;
Ⅴ 承載量：指網路資源如路由器的繁忙程度;
路由器與相關網路設備的比較
Hubs(中繼器)：對應 7 層模型的物理層，它的作用是放大電信號。主要用於連接具有相同物理層的 LAN。Hubs 還將乙太網的匯流排結構變成星狀結構。Bridges(Switches)：是一種在數據鏈路層實現互連的存儲轉發設備，廣泛用於區域網的擴展。Bridges 從一個網段接收完整的數據幀，進行必要的比較和驗證，然後決定是丟棄還是發送給另外一個網段。Bridges 具有隔離網段的作用。在網路上適當地使用 Bridges 可以調整網路負載，提高傳輸性能。
Router(路由器)：與 Bridges 相比，路由器實現網路互連是發生在網路層，它實現了相對復雜的功能：路由選擇、多路重發、錯誤檢測等。路由器的異構網互連能力、阻塞控制能力和網段的隔離能力要強於 Bridges。路由器可以阻止網路風暴、支持多協議、提供多種介面。
㈢ 使用子網掩碼和使用CIDR寫出網際網路的IP層查找路由的演算法。
(1) 從收到的分組的首部提取目的 IP 地址 D。
(2) 先用各網路的子網掩碼和 D 逐位相「與」，看是否和
相應的網路地址匹配。若匹配，則將分組直接交付。
否則就是間接交付，執行(3)。
(3) 若路由表中有目的地址為 D 的特定主機路由，則將
分組傳送給指明的下一跳路由器；否則，執行(4)。
(4) 對路由表中的每一行的子網掩碼和 D 逐位相「與」，
若其結果與該行的目的網路地址匹配，則將分組傳送
給該行指明的下一跳路由器；否則，執行(5)。
(5) 若路由表中有一個默認路由，則將分組傳送給路由表
中所指明的默認路由器；否則，執行(6)。
(6) 報告轉發分組出錯。
㈣ 路由演算法的類型有
路由演算法有很多種，如果從路由表對網路拓撲和通信量變化的自適應能力的角度劃分，可以分為靜態路由演算法和動態路由演算法兩大類，這兩大類又可細分為幾種小類型，比較典型常見的有以下幾種：
一、靜態路由演算法
1.Dijkstra演算法（最短路徑演算法）
Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權迴路。
Dijkstra演算法執行步驟如下：
步驟一：路由器建立一張網路圖，並且確定源節點和目的節點，在這個例子里我們設為V1和V2。然後路由器建立一個矩陣，稱為「鄰接矩陣」。在這個矩陣中，各矩陣元素表示權值。例如，[i,j]是節點Vi與Vj之間的鏈路權值。如果節點Vi與Vj之間沒有鏈路直接相連，它們的權值設為「無窮大」。
步驟二：路由器為網路中的每一個節點建立一組狀態記錄。此記錄包括三個欄位：
前序欄位———表示當前節點之前的節點。
長度欄位———表示從源節點到當前節點的權值之和。
標號欄位———表示節點的狀態。每個節點都處於一個狀態模式：「永久」或「暫時」。
步驟三：路由器初始化（所有節點的）狀態記錄集參數，將它們的長度設為「無窮大」，標號設為「暫時」。
步驟四：路由器設置一個T節點。例如，如果設V1是源T節點，路由器將V1的標號更改為「永久」。當一個標號更改為「永久」後，它將不再改變。一個T節點僅僅是一個代理而已。
步驟五：路由器更新與源T節點直接相連的所有暫時性節點的狀態記錄集。
步驟六：路由器在所有的暫時性節點中選擇距離V1的權值最低的節點。這個節點將是新的T節點。
步驟七：如果這個節點不是V2（目的節點），路由器則返回到步驟5。
步驟八：如果節點是V2，路由器則向前回溯，將它的前序節點從狀態記錄集中提取出來，如此循環，直到提取到V1為止。這個節點列表便是從V1到V2的最佳路由。
2.擴散法
事先不需要任何網路信息；路由器把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發送。將來會有多個分組的副本到達目的地端，最先到達的，可能是走了「最優」的路徑常見的擴散法是選擇性擴散演算法。
3.LS演算法
採用LS演算法時，每個路由器必須遵循以下步驟：
步驟一：確認在物理上與之相連的路由器並獲得它們的IP地址。當一個路由器開始工作後，它首先向整個網路發送一個「HELLO」分組數據包。每個接收到數據包的路由器都將返回一條消息，其中包含它自身的IP地址。
步驟二：測量相鄰路由器的延時（或者其他重要的網路參數，比如平均流量）。為做到這一點，路由器向整個網路發送響應分組數據包。每個接收到數據包的路由器返回一個應答分組數據包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，通過一個分組數據包從遠程主機返回的時間來測量。）該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。
步驟三：向網路中的其他路由器廣播自己的信息，同時也接收其他路由器的信息。
在這一步中，所有的路由器共享它們的知識並且將自身的信息廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網路的結構以及狀態。
步驟四：使用一個合適的演算法，確定網路中兩個節點之間的最佳路由。
路由演算法有哪些類型？路由演算法與路由協議的區別
在這一步中，路由器選擇通往每一個節點的最佳路由。它們使用一個演算法來實現這一點，如Dijkstra最短路徑演算法。在這個演算法中，一個路由器通過收集到的其他路由器的信息，建立一個網路圖。這個圖描述網路中的路由器的位置以及它們之間的鏈接關系。每個鏈接都有一個數字標注，稱為權值或成本。這個數字是延時和平均流量的函數，有時它僅僅表示節點間的躍點數。例如，如果一個節點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。
二、動態路由演算法
1.距離向量路由演算法
距離向量路由演算法，也叫做最大流量演演算法，其被距離向量協議作為一個演算法，如RIP、BGP、ISO IDRP、NOVELL IPX。使用這個演算法的路由器必須掌握這個距離表(它是一個一維排列-「一個向量」)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為「成本」)。這個在那個演算法中的度量公式是跳躍的次數，等待時間，流出數據包的數量，等等。在距離向量路由演算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。其優點是演算法簡單容易實現。缺點是慢收斂問題，路由器的路徑變化需要像波浪一樣從相鄰路由器傳播出去，過程緩慢。
每一個相鄰路由器發送過來的路由表都要經過以下步驟：
步驟一：對地址為X的路由器發過來的路由表，先修改此路由表中的所有項目：把」下一跳」欄位中的地址改為X，並把所有」距離」欄位都加1。
步驟二：對修改後的路由表中的每一個項目，進行以下步驟：
（1）將X的路由表(修改過的)，與S的路由表的目的網路進行對比。若在X中出現，在S中沒出現，則將X路由表中的這一條項目添加到S的路由表中。
（2）對於目的網路在S和X路由表中都有的項目進行下面步驟：
1）在S的路由表中，若下一跳地址是x，則直接用X路由表中這條項目替換S路由表中的項目。
2）在S的路由表中，若下一跳地址不是x，若X路由表項目中的距離d小於S路由表中的距離，則進行更新。
步驟三：若3分鍾還沒有收到相鄰路由器的更新表，則把此相鄰路由器記為不可到達路由器，即把距離設置為16。
2.鏈路狀態最短路由優先演算法SPF
1）發現鄰居結點，並學習它們的網路地址；
2）測量到各鄰居節點的延遲或者開銷；
3）創建鏈路狀態分組；
4）使用擴散法發布鏈路狀態分組；
5）計算到每個其它路由器的最短路徑。
㈤ BT達人們,在下虛心求教~~~~~~~~!
SP2的連接數只有10.這個用比特精靈的破解補丁就OK了.不過如果是你的上網方式是ADSL,就要看你的貓能不能受得了那麼多那麼多連接數了.如果不行,會造成斷流.也就是你說的網頁打不開,斷網再上又行了.這種情況下,把DHT功能關掉,就可以防止這一情況.所謂DHT,在這轉一個帖,解釋一下.
{BT軟體的DHT技術基礎——Kademlia協議原理簡介
一、前言
Kademlia協議（以下簡稱Kad）是美國紐約大學的PetarP. Maymounkov和David Mazieres.在2002年發布的一項研究結果《Kademlia: A peerto -peer information system based on the XOR metric》。
簡單的說，Kad是一種分布式哈希表（DHT）技術，不過和其他DHT實現技術比較，如Chord、CAN、Pastry等，Kad通過獨特的以異或演算法（XOR）為距離度量基礎，建立了一種全新的DHT拓撲結構，相比於其他演算法，大大提高了路由查詢速度。
在2005年5月著名的BiTtorrent在4.1.0版實現基於Kademlia協議的DHT技術後，很快國內的BitComet和BitSpirit也實現了和BitTorrent兼容的DHT技術，實現trackerless下載方式。
另外，emule中也很早就實現了基於Kademlia類似的技術（BT中叫DHT，emule中也叫Kad，注意和本文簡稱的Kad區別），和BT軟體使用的Kad技術的區別在於key、value和node ID的計算方法不同。
二、節點狀態
在Kad網路中，所有節點都被當作一顆二叉樹的葉子，並且每一個節點的位置都由其ID值的最短前綴唯一的確定。
對於任意一個節點，都可以把這顆二叉樹分解為一系列連續的，不包含自己的子樹。最高層的子樹，由整顆樹不包含自己的樹的另一半組成；下一層子樹由剩下部分不包含自己的一半組成；依此類推，直到分割完整顆樹。圖1就展示了節點0011如何進行子樹的劃分：
圖1：節點0011的子樹劃分
虛線包含的部分就是各子樹，由上到下各層的前綴分別為0，01，000，0010。
Kad協議確保每個節點知道其各子樹的至少一個節點，只要這些子樹非空。在這個前提下，每個節點都可以通過ID值來找到任何一個節點。這個路由的過程是通過所謂的XOR（異或）距離得到的。
圖2就演示了節點0011如何通過連續查詢來找到節點1110的。節點0011通過在逐步底層的子樹間不斷學習並查詢最佳節點，獲得了越來越接近的節點，最終收斂到目標節點上。
圖2：通過ID值定位目標節點
需要說明的是，只有第一步查詢的節點101，是節點0011已經知道的，後面各步查詢的節點，都是由上一步查詢返回的更接近目標的節點，這是一個遞歸操作的過程。
三、節點間距離
Kad網路中每個節點都有一個160bit的ID值作為標志符，Key也是一個160bit的標志符，每一個加入Kad網路的計算機都會在160bit的key空間被分配一個節點ID（node ID）值（可以認為ID是隨機產生的），<key,value>對的數據就存放在ID值「最」接近key值的節點上。
判斷兩個節點x,y的距離遠近是基於數學上的異或的二進制運算，d(x,y) = x⊕y，既對應位相同時結果為0，不同時結果為1。例如：
010101
XOR 110001
-------------
100100
則這兩個節點的距離為32＋4＝36。
顯然，高位上數值的差異對結果的影響更大。
對於異或操作，有如下一些數學性質：
d(x, x) = 0
d(x, y) > 0， if x ≠ y
∨x, y : d(x, y) = d(y, x)
d(x, y) + d(y, z) ≥ d(x, z)
d(x, y) ⊕ d(y, z) = d(x, z)
∨a≥ 0, b≥ 0, a + b≥ a ⊕ b
正如Chord的順時針旋轉的度量一樣，異或操作也是單向性的。對於任意給定的節點x和距離⊿≥0，總會存在一個精確的節點y，使得d(x,y)= ⊿。另外，單向性也確保了對於同一個key值的所有查詢都會逐步收斂到同一個路徑上，而不管查詢的起始節點位置如何。這樣，只要沿著查詢路徑上的節點都緩存這個<key,value>對，就可以減輕存放熱門key值節點的壓力，同時也能夠加快查詢響應速度。
四、K桶
Kad的路由表是通過一些稱之為K桶的表格構造起來的。這有點類似Tapestry技術，其路由表也是通過類似的方法構造的。
對每一個0≤i≤160，每個節點都保存有一些和自己距離范圍在區間 內的一些節點信息，這些信息由一些(IP address,UDP port,Node ID)數據列表構成（Kad網路是靠UDP協議交換信息的）。每一個這樣的列表都稱之為一個K桶，並且每個K桶內部信息存放位置是根據上次看到的時間順序排列，最近（least-recently）看到的放在頭部，最後（most-recently）看到的放在尾部。每個桶都有不超過k個的數據項。
一個節點的全部K桶列表如表1所示：
I 距離 鄰居
0
1
2
……
i
……
160
表1：K桶結構
不過通常來說當i值很小時，K桶通常是空的（也就是說沒有足夠多的節點，比如當i＝0時，就最多可能只有1項）；而當i值很大時，其對應K桶的項數又很可能會超過k個（當然，覆蓋距離范圍越廣，存在較多節點的可能性也就越大），這里k是為平衡系統性能和網路負載而設置的一個常數，但必須是偶數，比如k＝20。在BitTorrent的實現中，取值為k＝8。
由於每個K桶覆蓋距離的范圍呈指數關系增長，這就形成了離自己近的節點的信息多，離自己遠的節點的信息少，從而可以保證路由查詢過程是收斂。因為是用指數方式劃分區間，經過證明，對於一個有N個節點的Kad網路，最多隻需要經過logN步查詢，就可以准確定位到目標節點。這個特性和Chord網路上節點的finger table劃分距離空間的原理類似。
當節點x收到一個PRC消息時，發送者y的IP地址就被用來更新對應的K桶，具體步驟如下：
1．計算自己和發送者的距離：d(x,y) = x⊕y，注意：x和y是ID值，不是IP地址
2．通過距離d選擇對應的K桶進行更新操作。
3．如果y的IP地址已經存在於這個K桶中，則把對應項移到該該K桶的尾部
4．如果y的IP地址沒有記錄在該K桶中
⑴如果該K桶的記錄項小於k個，則直接把y的(IP address,UDP port,Node ID)信息插入隊列尾部
⑵如果該K桶的記錄項大於k個，則選擇頭部的記錄項（假如是節點z）進行RPC_PING操作
①如果z沒有響應，則從K桶中移除z的信息，並把y的信息插入隊列尾部
②如果z有響應，則把z的信息移到隊列尾部，同時忽略y的信息。
K桶的更新機制非常高效的實現了一種把最近看到的節點更新的策略，除非在線節點一直未從K桶中移出過。也就是說在線時間長的節點具有較高的可能性繼續保留在K桶列表中。
採用這種機制是基於對Gnutella網路上大量用戶行為習慣的研究結果，既節點的失效概率和在線時長成反比關系，如圖3（橫坐標為分鍾，縱坐標為概率）：
圖3：Gnutella網路中在線時長和繼續在線的概率關系
可以明顯看出，用戶在線時間越長，他在下一時段繼續在線的可能性就越高。
所以，通過把在線時間長的節點留在K桶里，Kad就明顯增加K桶中的節點在下一時間段仍然在線的概率，這對應Kad網路的穩定性和減少網路維護成本（不需要頻繁構建節點的路由表）帶來很大好處。
這種機制的另一個好處是能在一定程度上防禦DOS攻擊，因為只有當老節點失效後，Kad才會更新K桶的信息，這就避免了通過新節點的加入來泛洪路由信息。
為了防止K桶老化，所有在一定時間之內無更新操作的K桶，都會分別從自己的K桶中隨機選擇一些節點執行RPC_PING操作。
上述這些K桶機制使Kad緩和了流量瓶頸（所有節點不會同時進行大量的更新操作），同時也能對節點的失效進行迅速響應。
五、Kademlia協議操作類型
Kademlia協議包括四種遠程操作：PING、STORE、FIND_NODE、FIND_VALUE。
1、PING操作的作用是探測一個節點，用以判斷其是否仍然在線。
2、STORE操作的作用是通知一個節點存儲一個<key,value>對，以便以後查詢需要。
3、FIND_NODE操作使用一個160bit的ID作為參數。本操作的接受者返回它所知道的更接近目標ID的K個節點的(IP address,UDP port,Node ID)信息。
這些節點的信息可以是從一個單獨的K桶獲得，也可以從多個K桶獲得（如果最接近目標ID的K桶未滿）。不管是哪種情況，接受者都將返回K個節點的信息給操作發起者。但如果接受者所有K桶的節點信息加起來也沒有K個，則它會返回全部節點的信息給發起者。
4、FIND_VALUE操作和FIND_NODE操作類似，不同的是它只需要返回一個節點的(IP address,UDP port,Node ID)信息。如果本操作的接受者收到同一個key的STORE操作，則會直接返回存儲的value值。
註：在Kad網路中，系統存儲的數據以<key,value>對形式存放。根據筆者的分析，在BitSpirit的DHT實現中，其key值為torrent文件的info_hash串，其value值則和torrent文件有密切關系。
為了防止偽造地址，在所有RPC操作中，接受者都需要響應一個隨機的160bit的ID值。另外，為了確信發送者的網路地址，PING操作還可以附帶在接受者的RPC回復信息中。
六、路由查詢機制
Kad技術的最大特點之一就是能夠提供快速的節點查找機制，並且還可以通過參數進行查找速度的調節。
假如節點x要查找ID值為t的節點，Kad按照如下遞歸操作步驟進行路由查找：
1、 計算到t的距離：d(x,y) = x⊕y
2、 從x的第[㏒d]個K桶中取出α個節點的信息（「[」「]」是取整符號），同時進行FIND_NODE操作。如果這個K桶中的信息少於α個，則從附近多個桶中選擇距離最接近d的總共α個節點。
3、 對接受到查詢操作的每個節點，如果發現自己就是t，則回答自己是最接近t的；否則測量自己和t的距離，並從自己對應的K桶中選擇α個節點的信息給x。
4、 X對新接受到的每個節點都再次執行FIND_NODE操作，此過程不斷重復執行，直到每一個分支都有節點響應自己是最接近t的。
5、 通過上述查找操作，x得到了k個最接近t的節點信息。
注意：這里用「最接近」這個說法，是因為ID值為t的節點不一定存在網路中，也就是說t沒有分配給任何一台電腦。
這里α也是為系統優化而設立的一個參數，就像K一樣。在BitTorrent實現中，取值為α＝3。
當α＝1時，查詢過程就類似於Chord的逐跳查詢過程，如圖4。
圖4：α＝1時的查詢過程
整個路由查詢過程是遞歸操作的，其過程可用數學公式表示為：
= x(即查詢操作的發起者)
這個遞歸過程一直持續到 ＝t，或者 的路由表中沒有任何關於t的信息，即查詢失敗
由於每次查詢都能從更接近t的K桶中獲取信息，這樣的機制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少1bit）的效果，從而保證整個查詢過程的收斂速度為O(logN)，這里N為網路全部節點的數量。
當節點x要查詢<key,value>對時，和查找節點的操作類似，x選擇k個ID值最接近key值的節點，執行FIND_VALUE操作，並對每一個返回的新節點重復執行FIND_VALUE操作，直到某個節點返回value值。
一旦FIND_VALUE操作成功執行，則<key,value>對數據會緩存在沒有返回value值的最接近的節點上。這樣下一次查詢相同的key時就會更加快速的得到結果。通過這樣的方式，熱門<key,value>對數據的緩存范圍就逐步擴大，使系統具有極佳的響應速度，如圖5所示。
圖5：緩存原則
七、數據存放
存放<key,value>對數據的過程為：
1、 發起者首先定位k個ID值最接近key的節點；
2、 發起者對這k個節點發起STORE操作
3、 執行STORE操作的k個節點每小時重發布自己所有的<key,value>對數據。
4、 為了限制失效信息，所有<key,value>對數據在初始發布24小時後過期。
另外，為了保證數據發布、搜尋的一致性，規定在任何時候，當節點w發現新節點u比w上的某些<key,value>對數據更接近，則w把這些<key,value>對數據復制到u上，但是並不會從w上刪除。
八、節點加入和離開
如果節點u要想加入Kad網路，它必須要和一個已經在Kad網路的節點，比如w，取得聯系。
u首先把w插入自己適當的K桶中，然後對自己的節點ID執行一次FIND_NODE操作，然後根據接收到的信息更新自己的K桶內容。通過對自己鄰近節點由近及遠的逐步查詢，u完成了仍然是空的K桶信息的構建，同時也把自己的信息發布到其他節點的K桶中。
在Kad網路中，每個節點的路由表都表示為一顆二叉樹，葉子節點為K桶，K桶存放的是有相同ID前綴的節點信息，而這個前綴就是該K桶在二叉樹中的位置。這樣，每個K桶都覆蓋了ID空間的一部分，全部K桶的信息加起來就覆蓋了整個160bit的ID空間，而且沒有重疊。
以節點u為例，其路由表的生成過程為：
1． 最初，u的路由表為一個單個的K桶，覆蓋了整個160bitID空間，如圖6最上面的路由表；
2． 當學習到新的節點信息後，則u會嘗試把新節點的信息，根據其前綴值插入到對應的K桶中：
① 如果該K桶沒有滿，則新節點直接插入到這個K桶中；
② 如果該K桶已經滿了，
⑴ 如果該K桶覆蓋范圍包含了節點u的ID，則把該K桶分裂為兩個大小相同的新K桶，並對原K桶內的節點信息按照新的K桶前綴值進行重新分配
⑵ 如果該K桶覆蓋范圍沒有包節點u的ID，則直接丟棄該新節點信息
3． 上述過程不斷重復，最終會形成表1結構的路由表。達到距離近的節點的信息多，距離遠的節點的信息少的結果，保證了路由查詢過程能快速收斂。
圖6：節點000的路由表生成演化
在圖7中，演示了當覆蓋范圍包含自己ID值的K桶是如何逐步分裂的。
圖7：節點0100的K桶分裂過程
當K桶010滿了之後，由於其覆蓋范圍包含了節點0100的ID，故該K桶分裂為兩個新的K桶：0101和0100，原K桶010的信息會根據其其前綴值重新分布到這兩個新的K桶中。注意，這里並沒有使用160bit的ID值表示法，只是為了方便原理的演示，實際Kad網路中的ID值都是160bit的。
節點離開Kad網路不需要發布任何信息，Kademlia協議的目標之一就是能夠彈性工作在任意節點隨時失效的情況下。為此，Kad要求每個節點必須周期性的發布全部自己存放的<key,value>對數據，並把這些數據緩存在自己的k個最近鄰居處，這樣存放在失效節點的數據會很快被更新到其他新節點上。}
現在最新的BT軟體都講求功能強大,速度高,但只要好好調一下參數,你還是可以讓稍差一點的網路用戶端BT如飛的
㈥ 怎樣才能快速搜索路由表有哪些著名的搜索演算法
有三個路由器，a，b和c。路由器a的兩個網路介面f0和s0
分別連接在
10.1.0.0和10.2.0.0網段上；路由器b的兩個網路介面s0和s1
分別連接在
10.2.0.0和10.3.0.0網段上；路由器c的兩個網路介面s0和e0
分別連接在
10.3.0.0和10.4.0.0網段上；
如上圖中各路由表的前兩行所示，通過路由表的網路介面到與之直接相連的網
絡的網路連接，其向量距離設置為0。這即是最初的路由表。
當路由器b和a以及b和c之間相互交換路由信息後，它們會更新各自的路由表。
例如，路由器b通過網路埠s1收到路由器c的路由信息（10.3.0.0,s0,0）和(10.4.0.0,e0,0)後，在自己的路由表中增加一條(10.4.0.0,s1,1)路由信息。該信息表示：通過路由器b的網路接
口s1可以訪問到10.4.0.0網段，其向量距離為1,該向量距離是在路由器c的基礎上加1獲得的。
同樣道理，路由器b還會產生一條(10.1.0.0,s0,1)路由，這條路由是通過網路埠s0從路由器a
獲得的。如此反復，直到最終收斂，形成圖中所示的路由表。
概括地說，距離向量演算法要求每一個路由器把它的整個路由表發送給與它直接連接的其它路由
器。路由表中的每一條記錄都包括目標邏輯地址、相應的網路介面和該條路由的向量距離。當一個路
由器從它的相鄰處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條
新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的
向量距離與更新信息中的向量距離相加作為新路由的向量距離。
㈦ 什麼是路由啊 路由的組成 以及路由的演算法
路由：路由（routing）是指分組從源到目的地時，決定端到端路徑的網路范圍的進程。路由工作在OSI參考模型第三層——網路層的數據包轉發設備。路由器通過轉發數據包來實現網路互連。雖然路由器可以支持多種協議（如TCP/IP、IPX/SPX、AppleTalk等協議），但是在我國絕大多數路由器運行TCP/IP協議。路由器通常連接兩個或多個由IP子網或點到點協議標識的邏輯埠，至少擁有1個物理埠。路由器根據收到數據包中的網路層地址以及路由器內部維護的路由表決定輸出埠以及下一跳地址，並且重寫鏈路層數據包頭實現轉發數據包。路由器通過動態維護路由表來反映當前的網路拓撲，並通過網路上其他路由器交換路由和鏈路信息來維護路由表。
路由器的組成：
RAM（隨機存儲器）
功能：存放路由表；存放ARP告訴緩存；存放快速交換緩存；存放分組交換緩沖；存放解壓後的IOS；路由器加電後，存放running配置文件；
特點：重啟或者斷電後，RAM中的內容丟失。
NVRAM（非易失性RAM）
功能：存儲路由器的startup配置文件；存儲路由器的備份。
特點：重啟或者斷電後內容不丟失。
FLASH（快速快閃記憶體）
功能：存放IOS和微代碼。
特點：重啟或者斷電後內容不丟失；可存放多個IOS版本（在容量許可的前提下）；允許軟體升級不需替換CPU中的晶元。
ROM(只讀存儲器)
功能：存放POST診斷所需的指令；存放mini-ios；存放ROM監控模式的代碼。
特點：ROM中的軟體升級需要更換CPU的晶元（還好這種情況比較少遇到)
CPU（中央處理器）
衡量路由器性能的重要指標，負責路由計算，路由選擇等。
背板：
背板能力是一個重要參數，尤其在交換機中。
路由演算法：又名選路演算法，可以根據多個特性來加以區分。演算法的目的是找到一條從源路由器到目的路由器的「好」路徑（即具有最低費用的路徑[1]）。演算法設計者的特定目標影響了該路由協議的操作；具體來說存在著多種路由演算法，每種演算法對網路和路由器資源的影響都不同；由於路由演算法使用多種度量標准（metric），從而影響到最佳路徑的計算。
演算法分類：主要有RIP、IGRP（IGRP為 Cisco公司的私有協議）；鏈路狀態路由協議基於圖論中非常著名的Dijkstra演算法，即最短優先路徑（Shortest Path First， SPF）演算法，如OSPF。在距離向量路由協議中，路由器將部分或全部的路由表傳遞給與其相鄰的路由器；而在鏈路狀態路由協議中，路由器將鏈路狀態信息傳 遞給在同一區域內的所有路由器。 根據路由器在自治系統（AS）中的位置，可將路由協議分為內部網關協議 （Interior Gateway Protocol，IGP）和外部網關協議（External Gateway Protocol，EGP，也叫域 間路由協議）。域間路由協議有兩種：外部網關協議（EGP）和邊界網關協議（BGP）。EGP是為一個簡單的樹型拓撲結構而設計的，在處理選路循環和設置 選路策略時，具有明顯的缺點，已被BGP代替。
㈧ 路由器中的路由表是怎樣得出的
路由器中的路由表有直連路由，是本機算出來的，有手工指定的靜態路由，同時還有起的ergip、ospf、bgp等用戶起的動態路由進程學習到的，相鄰路由能夠起鄰居，相互之間學習到發布的路由指令。
所謂路由表，指的是路由器或者其他互聯網網路設備上存儲的表，該表中存有到達特定網路終端的路徑，在某些情況下，還有一些與這些路徑相關的度量。
在計算機網路中，路由表或稱路由擇域信息庫（RIB）是一個存儲在路由器或者聯網計算機中的電子表格（文件）或類資料庫。路由表存儲著指向特定網路地址的路徑（在有些情況下，還記錄有路徑的路由度量值）。路由表中含有網路周邊的拓撲信息。路由表建立的主要目標是為了實現路由協議和靜態路由選擇。
在現代路由器構造中，路由表不直接參與數據包的傳輸，而是用於生成一個小型指向表，這個指向表僅僅包含由路由演算法選擇的數據包傳輸優先路徑，這個表格通常為了優化硬體存儲和查找而被壓縮或提前編譯。
路由器的主要工作就是為經過路由器的每個數據包尋找一條最佳的傳輸路徑，並將該數據有效地傳送到目的站點。由此可見，選擇最佳路徑的策略即路由演算法是路由器的關鍵所在。為了完成這項工作，在路由器中保存著各種傳輸路徑的相關數據——路由表（Routing Table），供路由選擇時使用，表中包含的信息決定了數據轉發的策略。打個比方，路由表就像我們平時使用的地圖一樣，標識著各種路線，路由表中保存著子網的標志信息、網上路由器的個數和下一個路由器的名字等內容。路由表可以是由系統管理員固定設置好的，也可以由系統動態修改，可以由路由器自動調整，也可以由主機控制。
1．靜態路由表
由系統管理員事先設置好固定的路由表稱之為靜態（static）路由表，一般是在系統安裝時就根據網路的配置情況預先設定的，它不會隨未來網路結構的改變而改變。
2．動態路由表
動態（Dynamic）路由表是路由器根據網路系統的運行情況而自動調整的路由表。路由器根據路由選擇協議（Routing Protocol）提供的功能，自動學習和記憶網路運行情況，在需要時自動計算數據傳輸的最佳路徑。
路由器通常依靠所建立及維護的路由表來決定如何轉發。路由表能力是指路由表內所容納路由表項數量的極限。由於Internet上執行BGP協議的路由器通常擁有數十萬條路由表項，所以該項目也是路由器能力的重要體現。
