當前位置:成語大全網 - 書法字典 - 字典樹路由

字典樹路由

上圖是路由器如何轉發數據包的示例:有四個A類網絡由三臺路由器連接,每個網絡上可能有數千臺主機。如果路由表指示每臺主機應該如何轉發。要維護的路由表非常大。如果路由表指定如何轉發到某個網絡,則路由表中只有四行,每個網絡壹行。以路由器2的路由表為例:由於r 2同時連接到網絡2和網絡3,只要目標主機在網絡2或網絡3上,它就可以直接通過接口0或1或路由器R2發送(當然,使用ARP協議可以找到這些主機對應的MAC地址)。如果目標主機在網絡1中,下壹跳路由器是R1,其IP地址是20.0.0.7。路由器R2和R1同時連接到網絡2,因此很容易將數據包從路由器2轉發到R1。我們應該註意到每臺路由器必須至少有兩個不同的IP地址。簡而言之,在路由表中,每條路由最重要的信息是以下兩條信息:(目的網絡,下壹跳地址)我們根據目的網絡地址確定下壹跳路由器,因此我們可以得出以下結論:

雖然互聯網上的所有數據包轉發都基於目的主機所在的網絡,但在大多數情況下,它允許指示到特定主機的路由,這被稱為特定主機路由。使用特定的主機路由可以使網絡人員方便地管理和控制網絡以及測試網絡。

路由器還可以使用默認路由來減少路由表占用的空間和搜索路由表所需的時間。

當路由器接收到要轉發的數據報時,從路由表中獲得下壹跳路由器的IP地址後,它不會將此地址寫入IP數據報,而是將其發送到數據鏈路層的網絡接口軟件。網絡接口軟件將負責下壹跳的路由器的IP地址轉換為硬件地址(必須使用ARP),將硬件地址寫入MAC幀的報頭中,然後根據此硬件地址找到下壹跳路由器。可以看出,在發送壹系列數據報時,會不斷重復上述查找路由表、用ARP獲取硬件地址、將硬件地址寫入MAC地址頭的過程,產生壹定的開銷。

根據以上幾點,我們提出壹種包轉發算法:

這裏我們需要強調的是,路由表並不指示網絡到數據包的完整路徑(即首先通過哪個路由器,然後通過哪個路由器,以此類推)。路由表指出,要到達某個網絡,您應該首先到達某個路由器(下壹個路由器),然後在到達下壹跳路由器後繼續搜索路由表,以了解您下壹步應該到達哪個路由器。這種搜索壹步壹步地進行,直到最終到達目的網絡。

為什麽選擇子網?

為了解決上述問題,從1985引入了子網編號字段,使二級IP地址變成了三級IP地址。這種做法稱為子網劃分。

子網劃分的基本思想是:

子網劃分的使用案例

如上圖所示,某公司有壹個B類IP地址,網絡地址為145.13.0.0(網絡號為145.13),所有目的網絡為145.13.x.x的數據報都將發送到該網絡上的路由器R60。

現在網絡分成三個字網,假設子網號占用8位,那麽主機號只有16-8=8位,分成的三個字網分別是145.13.3.0、145.13.7.0。在145.13.0.0上收到路由器數據後,路由器會根據其目的地址將數據報轉換到相應的子網。

簡而言之,當沒有子網時,IP地址是兩段式結構。劃分子網後,IP地址變成三級結構。子網劃分只細分IP地址的主機號,不改變IP地址的原始網絡號。

假設壹個IP數據報(其目的地址為145.13.3.10)已經到達路由器R1,那麽該路由器如何將其轉發到子網145.13.3.0?

我們知道,從IP數據報的報頭中,我們無法看出源主機的目的主機所連接的網絡是否劃分了子網。這是因為32位IP地址本身和數據報的報頭不包含任何有關子網劃分的信息。因此,我們必須找到另壹種方法,那就是使用子網掩碼。

通過將三級IP地址的子網掩碼與接收到的目的地址的IP地址逐位進行AND運算,可以立即獲得網絡地址,剩下的步驟交給路由器進行數據包處理。

使用子網掩碼的好處是,無論網絡是否劃分了子網,只要子網掩碼和IP地址按位進行AND運算,就可以立即獲得網絡地址,這樣路由器在處理傳入的數據包時也可以這樣做。

不劃分子網時為什麽要使用子網掩碼?這是為了更容易找到路由表。現在互聯網規定所有網絡都必須使用子網掩碼,同時路由器的路由表中必須有子網掩碼壹欄。如果網絡未劃分子網,則網絡的子網掩碼是默認子網掩碼,默認子網掩碼中1的位置對應於IP地址的net-id字段。因此,如果您使用默認子網掩碼和未逐位劃分子網的IP地址,您應該能夠獲得該IP地址的網絡地址,這樣您就可以知道這是哪種IP地址,而無需查找地址的類別位。顯然:

圖4-21顯示了這三種IP地址的網絡地址和相應的默認子網掩碼:

子網掩碼是網絡或子網的壹個重要屬性。RFC950成為Internet標準後,當與相鄰路由器交換路由信息時,路由器必須告訴相鄰路由器自己網絡(或子網)的子網掩碼。對於路由器路由表中的每壹項,除了目的網絡地址外,還必須給出網絡的子網掩碼。如果路由器連接到兩個子網,它就有兩個網絡地址和兩個子網掩碼。

實施例4-2:

已知IP地址為141.14.72.24,子網掩碼為255.255.192.0。查找網絡地址:

解:255.255.192.0的二進制:11111165438。

ip141.14 . 72 . 24二進制:11111165438+。

00000000

IP地址二進制和子網掩碼二進制的AND運算為:111111165438+。

即網絡IP為141.14.64.0。

在劃分子網的情況下,必須改變數據包轉發的算法。使用子網劃分後,路由表應包含以下內容:

在子網劃分的情況下,路由器轉發數據包的算法如下:

實施例4-4:

圖4-24有三個字網、兩個路由器和路由器R1的部分路由表。現在,源主機H1向目的主機H2發送數據包。試討論R1收到H1發送到H2的數據包後檢查路由表的過程。

解決方案:

源主機H1向目的主機H2發送的數據包的目的地址是128.30.33.138。

源主機H1和該子網的子網掩碼255.255.128以及H2的IP地址128得到128。這表明主機H2和主機H1不在同壹個網段上,因此H1無法將數據包直接發送到H2。它必須被移交到子網中的默認路由R1並由R1轉發。

收到此數據包後,路由表會在路由表中逐行匹配和搜索。

先看R1的路由表第壹行:用這壹行的子網掩碼255.255.255.128與H2IP地址交互得到128.30.33.128,然後用同樣的方法用這壹行做第二行,發現相位出來了。所以妳不用繼續找了。R1直接將數據包從接口1傳送到主機H2(它們都在壹個子網中)。

劃分子網的網絡中可以使用幾種不同的子網掩碼。使用VLSM(可變長度子網掩碼)可以進壹步提高IP地址資源的利用率。在VLSM的基礎上,進壹步研究了不分類編譯方法。它的正式名稱是無類域間路由(CIDR)。

CIDR有兩個主要特點:

CIDR也使用斜杠符號,即在IP地址後添加壹個斜杠/,然後寫入網絡前綴所占用的位數。例如,IP地址128.14.35.7/20是CIDR地址緩存中的壹個地址,其中前20位是網絡前綴,接下來的14位是主機位。如圖所示:

當然,所有主機號都為0且所有地址都為1的地址通常不會使用。該地址塊* * *有2個12地址。我們可以在地址塊中使用最小的地址和網絡前綴來表示此地址很快。例如,上述地址塊可以寫成128.14.32.0/20。

為了使路由更方便,CIDR使用32位地址掩碼。地址掩碼由壹串1和壹串0組成,1的數字是網絡前綴的數量。盡管CIDR不使用子網,但出於某些原因,CIDR使用的地址掩碼仍可稱為子網掩碼。在斜線記法中,斜線後面的數字是1的數字。例如/20地址的快速地址掩碼是111111165438。在斜線記法中,斜線後面的數字是地址掩碼中的數字1。

斜杠符號的另壹個優點是它不僅可以表示壹個IP地址,還可以提供壹些其他重要信息。我們舉以下例子:

例如,192.199.170.82/27的地址不僅意味著IP地址為192.199.170.82,還意味著此地址的網絡前綴為27位(其余5位為主機號),因此此地址很快。通過計算還可以得出,該地址塊的最小地址為192.199.170.64,最大地址為192.6438+099.438+070。95。具體計算方法如下:找出地址掩碼中的1和0的交界處出現在地址中的哪個字節,現在是第四個字節,所以只需用二進制表示此字節的十進制82:82的二進制為01010010,取其前三位(這三位加上前三位)然後將後五位寫為0,即0100000 從而找到快速地址為192.199.170.64的最小地址,然後將後五位設置為1,即0106544。 在十進制中等於95,這將找到地址塊中最大的地址:192.199.438+070.95。

因為CICR地址塊中有許多地址,所以CIDR地址塊用於在路由表中查找目的網絡。這種地址聚合通常被稱為路由聚合,它使路由表中的壹個條目能夠代表原始傳統分類地址的許多路由。路由聚合也稱為超網劃分,它有助於減少路由器之間路由信息的交換,從而提高整個互聯網的性能。

每個CIDR地址塊中的地址數量必須是2的整數冪,這就是構建超網的來源。

網絡前綴越短,它在地址塊中包含的地址越多,而在三級結構的IP地址中,子網劃分使網絡前綴越長。

使用CIDR時,由於網絡前綴的表示法,IP地址由網絡前綴和主機號組成,因此路由表中的項目應相應地更改。此時,每個條目都由網絡前綴和下壹跳地址組成,但在查找路由表時可能會得到多個匹配結果,這就帶來了壹個問題:我們應該從這些匹配結果中選擇哪條路由?

正確答案是:應該從匹配結果中選擇具有最長網絡前綴的路由,這稱為長前綴匹配,因為網絡前綴越長,地址塊越小,因此路由越具體,最長前綴匹配也稱為最長匹配或最佳匹配。

使用CIDR後,查找最長的前綴匹配非常復雜。當路由表中的條目數量很大時,如何減少路由表的平均搜索時間成為壹個非常重要的問題。現在常用的是二元trie,這是壹種結構特殊的樹。IP地址中從左到右的位值決定了從根節點延伸到下層的路徑,二進制trie中的每條路徑都代表路由表。

圖4-26舉例說明了二叉樹線索的結構,圖中給出了五個IP地址。為了簡化二進制線索的結構,我們可以首先找出每個IP地址對應的唯壹前綴。所謂的唯壹前綴在表中的所有IP地址中是唯壹的,因此我們可以使用這些唯壹前綴來構造二進制線索。搜索時,只要它能匹配唯壹前綴。

二叉樹的根節點從上到下的深度最多為32層,每層對應IP地址中的壹位。