基于IPv4地址的無(wú)分類(lèi)編址CIDR技術(shù)研究

賀興亞+楊云

摘要：為提高IPv4地址空間利用率，IETF提出無(wú)類(lèi)域間路由CIDR地址結(jié)構(gòu)。分析無(wú)分類(lèi)編址CIDR與分類(lèi)編址的轉(zhuǎn)換、CIDR工作方式、地址分配方法與標(biāo)記技術(shù)，推導(dǎo)最長(zhǎng)地址前綴匹配查找算法。提出基于CIDR的快速計(jì)算地址塊、網(wǎng)絡(luò)ID與構(gòu)建超網(wǎng)方法。研究表明，無(wú)分類(lèi)編址CIDR與分類(lèi)編址都是基于IPv4地址的分配方法，均可用無(wú)分類(lèi)編址CIDR表示。

關(guān)鍵詞關(guān)鍵詞：計(jì)算機(jī)網(wǎng)絡(luò)；無(wú)分類(lèi)編址；IPv4；可變長(zhǎng)子網(wǎng)掩碼

DOIDOI：10.11907/rjdk.171835

中圖分類(lèi)號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）011020605

0引言

為解決IPv4地址資源匱乏、IPv4地址分類(lèi)帶來(lái)的資源浪費(fèi)問(wèn)題，IETF（因特網(wǎng)工程任務(wù)組）試圖通過(guò)設(shè)置“內(nèi)部IP地址”、“可變長(zhǎng)子網(wǎng)掩碼VLSM”、“無(wú)分類(lèi)編址CIDR”等技術(shù)，解決IPv4地址資源管理問(wèn)題，提高IPv4地址使用效率。

由于IPv4地址設(shè)計(jì)本身結(jié)構(gòu)性矛盾（32位）無(wú)法解決，只有通過(guò)IPv6地址（128位）解決。而目前Internet基礎(chǔ)設(shè)施大部分不支持IPv6，其應(yīng)用推廣技術(shù)遇到瓶頸，試圖通過(guò)“雙協(xié)議棧技術(shù)”、“隧道技術(shù)”等方法解決[1，2]。IPv4到IPv6的過(guò)渡也遇到了困難[3]：雙棧技術(shù)解決了網(wǎng)絡(luò)能力問(wèn)題，但I(xiàn)Pv4與IPv6不能互通，同時(shí)存在能用IPv4為何還要用IPv6的疑問(wèn)；隧道解決了孤島問(wèn)題[4]，但I(xiàn)Pv4與IPv6仍然不能互通，同時(shí)跨越不同網(wǎng)絡(luò)時(shí)，必須與雙棧共同使用。清華大學(xué)李星[5]教授等提出的“翻譯技術(shù)”概念，試圖實(shí)現(xiàn)IPv4與IPv6互聯(lián)互通，翻譯解決了互通問(wèn)題，但存在單點(diǎn)故障及應(yīng)用層協(xié)議支持問(wèn)題，因此每一種過(guò)渡技術(shù)都無(wú)法單獨(dú)使用。

無(wú)分類(lèi)編址CIDR正式名字是“無(wú)分類(lèi)域間路由CIDR （Classless InterDomain Routing）”[6]，它是目前解決IPv4地址資源匱乏、資源浪費(fèi)的最好方法。無(wú)分類(lèi)編址CIDR與分類(lèi)編址一樣，都是IPv4地址的分配方法。

1無(wú)分類(lèi)編址CIDR概述

1.1CIDR研究目的

1.1.1問(wèn)題提出

某企業(yè)用300臺(tái)計(jì)算機(jī)構(gòu)建一個(gè)局域網(wǎng)，要對(duì)這些主機(jī)分配IP地址，請(qǐng)給出一種分配方案。討論：①分配一個(gè)C類(lèi)地址。一個(gè)C類(lèi)地址僅有256個(gè)IP地址，地址數(shù)量不夠，使用2個(gè)C類(lèi)地址，必須增加一臺(tái)路由器，否則許多主機(jī)不能直接通信，同時(shí)成本增加；②分配一個(gè)B類(lèi)地址。一個(gè)B類(lèi)地址共有256×256個(gè)IP地址，地址數(shù)量太多，形成浪費(fèi)。

1.1.2問(wèn)題分析

采用的IP地址是分類(lèi)編址，使得IP地址資源分配不合理。需找到一種IP地址分配方法，可以根據(jù)用戶需求，自由分配或組合IP地址，不受分類(lèi)地址的束縛。

CIDR是一種無(wú)分類(lèi)編址技術(shù)，消除了傳統(tǒng)A類(lèi)、B類(lèi)、C類(lèi)地址以及劃分子網(wǎng)的概念[7]，可以更加有效地分配 IPv4 的地址空間，解決以前分類(lèi)地址策略的低效性[8]。

通過(guò)劃分子網(wǎng)可以提高IP地址使用效率，減少了數(shù)據(jù)交換，但加重了路由器負(fù)擔(dān)，路由器的路由表項(xiàng)呈指數(shù)級(jí)增長(zhǎng)，影響了路由器轉(zhuǎn)發(fā)效率。為了解決路由器中路由表項(xiàng)過(guò)多問(wèn)題，通過(guò)“可變長(zhǎng)子網(wǎng)掩碼VLSM”可以部分緩解路由器壓力，減少路由器路由表項(xiàng)，但不能從根本上解決路由表項(xiàng)過(guò)多問(wèn)題，提高路由器工作效率，這是因?yàn)閂LSM是基于分類(lèi)的IPv4地址。

無(wú)分類(lèi)編址CIDR通過(guò)“地址塊”概念，可以大大減少路由器路由表項(xiàng)[9]。

1.2無(wú)分類(lèi)編址CIDR含義

CIDR記為 IP地址 ：：= {<網(wǎng)絡(luò)前綴>， <主機(jī)號(hào)>} 或CIDR地址= <網(wǎng)絡(luò)前綴>/<主機(jī)號(hào)>

（1）IP 地址從三級(jí)編址（使用子網(wǎng)掩碼）回到二級(jí)編址。CIDR使用各種長(zhǎng)度的“網(wǎng)絡(luò)前綴”代替分類(lèi)地址中的網(wǎng)絡(luò)號(hào)與子網(wǎng)號(hào)；使用二級(jí)編址簡(jiǎn)化了路由表結(jié)構(gòu)、路由表項(xiàng)，可以提高路由器轉(zhuǎn)發(fā)效率。

（2）“斜線記法”與分類(lèi)IP地址都是IPv4地址的分配方法。CIDR不采用傳統(tǒng)的標(biāo)準(zhǔn)IPv4地址分類(lèi)方法，而采用“斜線記法”表示IP地址，但無(wú)法從地址本身直接判斷網(wǎng)絡(luò)號(hào)的長(zhǎng)度。對(duì)于無(wú)分類(lèi)IP地址：200.16.23.1/20 =11001000 00010000 00010111 00000001，/20被稱(chēng)為網(wǎng)絡(luò)前綴長(zhǎng)度（或地址前綴長(zhǎng)度），11001000 00010000 0001被稱(chēng)為地址前綴比特值（或網(wǎng)絡(luò)號(hào)），0111 00000001被稱(chēng)為主機(jī)號(hào)。

（3）CIDR將剩余IP地址按可變大小的地址塊分配。與傳統(tǒng)的標(biāo)準(zhǔn)分類(lèi)IP地址及子網(wǎng)地址劃分方式相比，CIDR是以任意二進(jìn)制倍數(shù)的大小來(lái)分配地址。

（4）CIDR將網(wǎng)絡(luò)前綴都相同、連續(xù)的 IP 地址組成“CIDR地址塊” 。這是理解CIDR時(shí)需要重點(diǎn)分析的內(nèi)容，因?yàn)樗苯雨P(guān)系到對(duì)CIDR概念的理解與對(duì)CIDR技術(shù)的掌握。①CIDR地址塊。一個(gè)CIDR地址塊由地址塊的起始地址（地址塊中地址數(shù)值最小一個(gè)）與地址塊中地址數(shù)來(lái)定義。如果一個(gè)IP地址的前N位與一個(gè)CIDR地址塊的前綴相同，這個(gè)地址則屬于這個(gè)CIDR地址塊，也可以說(shuō)是與CIDR地址塊的前綴匹配。因?yàn)镮Pv4地址度總是32位，N位長(zhǎng)的CIDR前綴就意味著地址里32N位不匹配。這些位有232N種不同的組合，即232N個(gè)IPv4地址與CIDR地址塊的前綴匹配。前綴越短就能匹配越多地址，越長(zhǎng)就匹配得越少。一個(gè)地址可能與多個(gè)長(zhǎng)度不同的CIDR前綴匹配；②地址聚合、路由聚合。由于一個(gè)CIDR地址塊可以表示很多地址，在路由表中就利用CIDR地址塊查找目的網(wǎng)絡(luò)（這種地址的聚合稱(chēng)為“路由聚合”），路由聚合有利于減少路由器之間的路由選擇信息交換，提高整個(gè)Internet的性能；③構(gòu)建超網(wǎng)。將地址前綴數(shù)（網(wǎng)絡(luò)號(hào)值）與網(wǎng)絡(luò)前綴長(zhǎng)度相同、個(gè)數(shù)是2的冪的地址塊組成“超網(wǎng)”。endprint

2分類(lèi)編址與無(wú)分類(lèi)編址比較

本節(jié)用圖例解析CIDR結(jié)構(gòu)特征。

2.1分類(lèi)編址表示

分類(lèi)編址中每一類(lèi)地址都被劃分為固定數(shù)目的地址塊，并且每一個(gè)地址塊大小固定（見(jiàn)圖1-圖5）。

2.2用無(wú)分類(lèi)編址表示分類(lèi)編址

使用無(wú)分類(lèi)編址可以表示分類(lèi)編址中的A、B、C、D、E類(lèi)地址，其對(duì)應(yīng)關(guān)系見(jiàn)圖6-圖10。

3無(wú)分類(lèi)編址CIDR技術(shù)

3.1工作方式

CIDR將所有IP地址與子網(wǎng)掩碼翻譯為二進(jìn)制符號(hào)；將IP地址分為32個(gè)值的集合，代替在分類(lèi)編址系統(tǒng)中使用的4個(gè)值；網(wǎng)絡(luò)大小有了更多變化；CIDR不定義基于IP地址的缺省子網(wǎng)掩碼，而是根據(jù)實(shí)際需要確定。

3.2以任意二進(jìn)制倍數(shù)大小分配地址

從CIDR的表示可知，CIDR是通過(guò)網(wǎng)絡(luò)前綴分配地址塊，而網(wǎng)絡(luò)前綴的取值范圍為0～255。其對(duì)應(yīng)關(guān)系如表1所示。

3.3CIDR地址塊計(jì)算

無(wú)分類(lèi)編址地址塊由地址塊的起始地址（地址塊中數(shù)值最?。┡c最大地址（地址塊中數(shù)值最大）定義。

首先，根據(jù)網(wǎng)絡(luò)前綴長(zhǎng)度確定地址前綴長(zhǎng)度（網(wǎng)絡(luò)號(hào)長(zhǎng)度）與主機(jī)號(hào)長(zhǎng)度，明確1與0的分界處（對(duì)應(yīng)字節(jié)），再將IP地址中對(duì)應(yīng)字節(jié)處的十進(jìn)制數(shù)用二進(jìn)制數(shù)表示。其次，計(jì)算最小地址，將按照網(wǎng)絡(luò)前綴長(zhǎng)度確定的IP地址主機(jī)號(hào)部分全部取0，計(jì)算其對(duì)應(yīng)的二進(jìn)制數(shù)，所得值即為最小地址；同理，計(jì)算最大地址，將按照網(wǎng)絡(luò)前綴長(zhǎng)度確定的IP地址主機(jī)號(hào)部分全部取1，計(jì)算其對(duì)應(yīng)的二進(jìn)制數(shù)，所得值即為最大地址；地址塊范圍為最小地址～最大地址。

對(duì)于地址162.82.0.0/11計(jì)算其所屬地址塊。先找出掩碼中1與0的交界處，發(fā)生在第2個(gè)字節(jié)（8+3=11），再將十進(jìn)制數(shù)82用二進(jìn)制數(shù)表示為01010010，取其前3位，并把后5位都寫(xiě)成0，即010 00000，它等于十進(jìn)制數(shù)64，因此，最小地址為162.64.0.0。同樣將后5位都寫(xiě)成1，即010 11111，它等于十進(jìn)制數(shù)95，最大地址為162.95.255.255。所以地址162.82.0.0/11包含在地址塊162.64.0.0 /11 ～ 162.95.255.255/11中。

通過(guò)計(jì)算可以發(fā)現(xiàn)：斜線記法除了表示一個(gè)IP地址（或地址塊）外，同時(shí)還提供了其它一些重要信息：

（1）地址塊162.82.0.0/11中含有221個(gè)主機(jī)號(hào)。

（2）地址聚合：地址前綴數(shù)相同均為162.64。

162.64.0.0/11，10100010 01000000 00000000 00000000

162.82.0.0/11，10100010 01010010 00000000 00000000

162.95.255.255/11， 1010001001111111 111111111 11111111

（3）通過(guò)無(wú)分類(lèi)地址可以計(jì)算網(wǎng)絡(luò)ID，最小地址恰為子網(wǎng)網(wǎng)絡(luò)地址，最大地址恰為子網(wǎng)廣播地址。

3.4標(biāo)記技術(shù)分析

3.4.1分類(lèi)編址轉(zhuǎn)換為無(wú)分類(lèi)編址

分類(lèi)編址子網(wǎng)掩碼中，連續(xù)“1”的個(gè)數(shù)即為無(wú)分類(lèi)編址的網(wǎng)絡(luò)前綴長(zhǎng)度（見(jiàn)表2）。

3.4.2無(wú)分類(lèi)編址計(jì)算網(wǎng)絡(luò)ID

根據(jù)無(wú)分類(lèi)編址CIDR中網(wǎng)絡(luò)前綴長(zhǎng)度，確定地址前綴長(zhǎng)度，計(jì)算出地址前綴值（最小地址）即為網(wǎng)絡(luò)ID（見(jiàn)表3）。

3.4.3無(wú)分類(lèi)編址最長(zhǎng)前綴匹配

在配置基于CIDR的網(wǎng)絡(luò)時(shí)，查找路由表時(shí)可能會(huì)得到不止一個(gè)匹配結(jié)果。因?yàn)榫W(wǎng)絡(luò)前綴越長(zhǎng)，其地址塊就越小，因而路由就越具體，所以應(yīng)當(dāng)從匹配結(jié)果中選擇具有最長(zhǎng)網(wǎng)絡(luò)前綴的路由，這稱(chēng)為“最長(zhǎng)前綴匹配”。

顯然，若一個(gè)目的IP地址同時(shí)與兩個(gè)（或以上）CIDR地址塊匹配，則網(wǎng)絡(luò)前綴短的地址塊包含網(wǎng)絡(luò)前綴長(zhǎng)的地址塊。

表4說(shuō)明，目的IP地址為206.0.71.130的數(shù)據(jù)報(bào)，由于其與206.0.68.0/22及206.0.71.128/25均匹配，根據(jù)最長(zhǎng)前綴匹配原則，最終路由選擇為206.0.71.128/25。

匹配

目的IP地址與表項(xiàng)2網(wǎng)絡(luò)前綴作與運(yùn)算10.217.112.0/20匹配 √

對(duì)于表5的路由表，考慮4個(gè)目的地址10.1.0.14、10.1.4.6、10.2.1.3、10.4/16：①10.1.0.14中兩條路由都符合，根據(jù)最長(zhǎng)掩碼匹配原則，下一跳地址應(yīng)該是192.168.2.2；②10.1.4.6 只與第二條路由網(wǎng)段匹配，所以下一跳地址為192.168.3.3；③10.2.1.3 與哪條都不匹配，所以只能走默認(rèn)路由，下一跳地址為192.168.1.1；③10.4/16 與哪條都不匹配，將被路由器丟棄。

當(dāng)采用無(wú)分類(lèi)編址進(jìn)行路由轉(zhuǎn)發(fā)時(shí)，若未啟動(dòng)IP Classless命令，若目的IP地址不在路由表中，將采取丟包策略，而不會(huì)走默認(rèn)路由。

IP Classless命令最早在cisco IOS 10.0被介紹，在cisco IOS 11.3后，IP Classless就缺省有效了。其作用為：①I(mǎi)P classless命令作用于路由轉(zhuǎn)發(fā)進(jìn)程，告訴路由器在無(wú)分類(lèi)環(huán)境下工作；②它能讓路由器超越分類(lèi)網(wǎng)絡(luò)的邊界，根據(jù)最長(zhǎng)匹配條目轉(zhuǎn)發(fā)數(shù)據(jù)包；③當(dāng)目的網(wǎng)絡(luò)沒(méi)有出現(xiàn)在路由表中時(shí)，通過(guò)默認(rèn)路由轉(zhuǎn)發(fā)數(shù)據(jù)包，而不是簡(jiǎn)單丟棄；③如果路由器工作在分類(lèi)編址環(huán)境下，當(dāng)目的網(wǎng)絡(luò)出現(xiàn)在路由表中但無(wú)具體網(wǎng)絡(luò)匹配時(shí)，防火墻將丟棄數(shù)據(jù)包。

由于10.2.3.3是分類(lèi)匹配，可以使用默認(rèn)路由，而10.4/16是無(wú)分類(lèi)匹配，不能使用默認(rèn)路由，只能丟棄。但當(dāng)啟動(dòng)了IP Classless命令后，10.4/16與10.2.3.3一樣，都可以通過(guò)默認(rèn)路由轉(zhuǎn)發(fā)數(shù)據(jù)包。endprint

因此，使用了IP Classless命令，路由器成為無(wú)分類(lèi)路由環(huán)境，當(dāng)目的數(shù)據(jù)包到達(dá)時(shí)，不進(jìn)行分類(lèi)匹配，而是進(jìn)行無(wú)分類(lèi)匹配，即進(jìn)行最長(zhǎng)前綴匹配；當(dāng)采用最長(zhǎng)前綴匹配時(shí)，若目的IP地址不在路由表內(nèi)，路由器將把它交給默認(rèn)路由，通過(guò)默認(rèn)路由將數(shù)據(jù)包送出。

3.4.4網(wǎng)絡(luò)前綴設(shè)置

根據(jù)骨干網(wǎng)路由器路由表前綴長(zhǎng)度的分布統(tǒng)計(jì)發(fā)現(xiàn)，路由前綴長(zhǎng)度至少為8，路由前綴并不是按長(zhǎng)度平均分布，路由表前綴長(zhǎng)度在13～27之間的占98.9%，僅前綴長(zhǎng)度為23的占50%左右，前綴長(zhǎng)度在其它區(qū)間的很少。因此，一般網(wǎng)絡(luò)前綴取值在13～27之間[10]，將網(wǎng)絡(luò)前綴設(shè)置成比原來(lái)分類(lèi)編址子網(wǎng)掩碼的1比特長(zhǎng)，其主要目的是基于無(wú)分類(lèi)編址CIDR的網(wǎng)絡(luò)與基于分類(lèi)編址的網(wǎng)絡(luò)能相互支持。

事實(shí)上，由于CIDR標(biāo)記法應(yīng)用范圍廣、使用靈活，當(dāng)主機(jī)軟件支持CIDR時(shí)，網(wǎng)絡(luò)前綴可以比原來(lái)的掩碼長(zhǎng)度短，如表6所示。

由此得到結(jié)論：使用無(wú)分類(lèi)編址CIDR，可以標(biāo)記任意的地址塊。同時(shí)，合理、科學(xué)地分配地址塊顯得非常重要。

3.4.5超網(wǎng)構(gòu)建

所謂“超網(wǎng)”就是將若干個(gè)網(wǎng)絡(luò)前綴長(zhǎng)度相同、地址前綴值相等、地址個(gè)數(shù)是2的冪的IP地址進(jìn)行聚合，也稱(chēng)為“

路由聚合”。聚合方法就是對(duì)IP地址進(jìn)行“全排列運(yùn)算”或“與或運(yùn)算”。一個(gè)超網(wǎng)就是一個(gè)CIDR地址塊，其中包含了多個(gè)IP地址。

根據(jù)表6，可以很方便地構(gòu)建超網(wǎng)，建立CIDR地址塊。

某公司需要600個(gè)地址，下面哪一組IP地址塊可以用于這個(gè)公司構(gòu)成超網(wǎng)？

（1）198.47.32.0，198.47.33.0，198.47.34.0

（2）198.47.32.0，198.47.42.0，198.47.52.0，198.47.62.0

（3）198.47.31.0，198.47.32.0，198.47.33.0，198.47.34.0

（4）198.47.32.0，198.47.33.0，198.47.34.0，198.47.35.0

分析：①I(mǎi)P地址個(gè)數(shù)不是2的冪，不能構(gòu)建超網(wǎng)；②網(wǎng)絡(luò)ID不連續(xù)，不能構(gòu)建超網(wǎng)；③4個(gè)連續(xù)的IP地址，但地址前綴值不相等（即不屬于同一個(gè)網(wǎng)絡(luò)ID），不能構(gòu)建超網(wǎng)；④可以構(gòu)建超網(wǎng)，超網(wǎng)地址塊為198.47.32.0/22。

一般地，根據(jù)CIDR標(biāo)記特點(diǎn)，聚合結(jié)果總是網(wǎng)絡(luò)ID地址最小/網(wǎng)絡(luò)前綴。

3.5CIDR地址分配方法

主要有二叉樹(shù)法與遞增法。

3.5.1二叉樹(shù)法

根據(jù)網(wǎng)絡(luò)前綴值形成的二叉樹(shù)進(jìn)行地址分配。將1個(gè)網(wǎng)絡(luò)前綴值為23 位的地址，可分為2個(gè)24 位的地址；1個(gè)24 位的地址，可分為2個(gè)25 位的地址，依此類(lèi)推。這樣，CIDR 地址的網(wǎng)絡(luò)前綴由短到長(zhǎng)依次向下形成了一個(gè)二叉樹(shù)形狀。

圖11表示將網(wǎng)絡(luò)192.268.2.0/23分為3個(gè)子網(wǎng)A、B、C，分別含有主機(jī)數(shù)為250臺(tái)、50臺(tái)、100臺(tái)的一種二叉樹(shù)法分配方案。當(dāng)然，在進(jìn)行二叉樹(shù)劃分時(shí)，必須滿足“子網(wǎng)聚合”原則，在上述劃分中，B與C 的地址中間出現(xiàn)間隔，說(shuō)明有段IP地址沒(méi)有進(jìn)行分配。

圖11CIDR地址分配的二叉樹(shù)法

3.5.2遞增法

根據(jù)主機(jī)數(shù)進(jìn)行IP 地址劃分。在給定IP 地址上不斷增加主機(jī)數(shù)，形成的新IP 地址就是子網(wǎng)IP。

由于A 網(wǎng)需要包含大于250 臺(tái)主機(jī)地址的IP地址，而256 =28，在原地址上加256，得到下一個(gè)子網(wǎng)的網(wǎng)絡(luò)號(hào)：192.268.3.0/24；C網(wǎng)需要包含大于100臺(tái)主機(jī)地址的IP地址計(jì)劃，因?yàn)?6 = 64 <100 < 128 =27，因此，C網(wǎng)子網(wǎng)的網(wǎng)絡(luò)號(hào)為：192.268.2.128/25。依此類(lèi)推，可以用地址加主機(jī)數(shù)方式實(shí)現(xiàn)IP地址的分配，顯然，得到遞增的IP 地址。

3.5.3兩種地址分配方法比較

二叉樹(shù)法得到的子網(wǎng)IP地址之間存在間斷，就是IP 地址分配不能夠連續(xù)。對(duì)于遞增法，當(dāng)主機(jī)臺(tái)數(shù)不相同時(shí)，如果按照問(wèn)題要求的順序，地址分配計(jì)劃是：A為192.268.2.0/24；B為192.268.3.0/26；C：192.268.3.64/25。由于小的IP 地址對(duì)應(yīng)的網(wǎng)絡(luò)前綴長(zhǎng)，而大的IP對(duì)應(yīng)的網(wǎng)絡(luò)前綴短，B與C部分地址出現(xiàn)了重復(fù)，IP 地址分配出現(xiàn)了錯(cuò)誤。

研究發(fā)現(xiàn)，二叉樹(shù)方法中的網(wǎng)絡(luò)前綴是自上而下依次增大，分配的IP地址不能保證從小到大、連續(xù)，但可以避免IP地址重復(fù)。主機(jī)數(shù)遞增的分配方法解決了IP地址從小到大連續(xù)的問(wèn)題，但大IP地址網(wǎng)絡(luò)前綴小于小IP地址網(wǎng)絡(luò)前綴，會(huì)導(dǎo)致重復(fù)。因此，兩種方法可以相互借鑒結(jié)合使用。

3.6最長(zhǎng)地址前綴匹配查找算法

在分類(lèi)地址結(jié)構(gòu)體系下，可以通過(guò)目的IP地址前幾個(gè)比特位的值獲得該地址所對(duì)應(yīng)的類(lèi)，從而知道匹配地址前綴的長(zhǎng)度，因此地址前綴查找比較簡(jiǎn)單。

在無(wú)分類(lèi)地址CIDR結(jié)構(gòu)體系下，路由表的規(guī)模得到了一定控制，但是地址前綴查找工作變得非常復(fù)雜。在CIDR地址結(jié)構(gòu)下，地址前綴表中前綴表項(xiàng)長(zhǎng)度是任意的，類(lèi)的概念將不存在，所以不能從目的地址前幾個(gè)比特推斷出該地址所對(duì)應(yīng)的地址長(zhǎng)度，從而地址查找操作不再能簡(jiǎn)單地轉(zhuǎn)化為關(guān)鍵字的精確匹配[11]。

CIDR地址結(jié)構(gòu)下的地址前綴查找，不僅需要與前綴的比特位進(jìn)行匹配查找，而且需要考慮地址前綴的長(zhǎng)度?；诖?，最長(zhǎng)地址前綴查找可以從地址前綴值與地址前綴長(zhǎng)度兩個(gè)方面考慮。目前主要的最長(zhǎng)地址匹配查找算法有：二進(jìn)制Trie樹(shù)、路徑壓縮Trie樹(shù)、多分支Trie樹(shù)（步寬為k）、前綴長(zhǎng)度的二分查找、地址區(qū)間的二分查找等[1214]。

4結(jié)語(yǔ)

通過(guò)分析無(wú)分類(lèi)編址CIDR地址體系結(jié)構(gòu)可知，無(wú)分類(lèi)編址CIDR與分類(lèi)編址都是IPv4地址的分配方法，CIDR技術(shù)可以緩解IP資源緊張狀況，控制路由表規(guī)模，在IP4向IP6發(fā)展過(guò)渡期有獨(dú)特的重要作用[15]。但在CIDR結(jié)構(gòu)體系下，地址前綴的查找變得復(fù)雜，需合理設(shè)計(jì)最長(zhǎng)地址匹配查找算法。

參考文獻(xiàn)參考文獻(xiàn)：

[1]王浩.IPv4與IPv6相互轉(zhuǎn)換技術(shù)研究[J].計(jì)算機(jī)與數(shù)字工程，2010，38（1）：114117.

[2]張軍超.基于MPBGP擴(kuò)展的4over6隧道技術(shù)的實(shí)現(xiàn)[J].計(jì)算機(jī)與數(shù)字工程，2012，40（12）：119122.

[3]包叢笑，李星.IPv4/IPv6過(guò)渡的核心技術(shù)標(biāo)準(zhǔn)RFC6052[J].中國(guó)教育網(wǎng)絡(luò)，2010，12（1）：2829.

[4]張平.IPv4與IPv6隧道技術(shù)的研究及實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012，22（8）：127130.

[5]李星.互聯(lián)網(wǎng)核心技術(shù)創(chuàng)新與網(wǎng)絡(luò)強(qiáng)國(guó)[C].北京：2015年第四屆高等學(xué)校計(jì)算機(jī)網(wǎng)絡(luò)類(lèi)專(zhuān)業(yè)教育與教學(xué)研討會(huì)，2015.

[6]吳功宜.計(jì)算機(jī)網(wǎng)絡(luò)：第3版[M].北京：清華大學(xué)出版社，2011.

[7]姚秀情.CIDR的簡(jiǎn)單應(yīng)用分析機(jī)電技術(shù)[J].機(jī)電技術(shù)，2013（4）：6365.

[8]陳宜冬.基于CIDR的網(wǎng)絡(luò)劃分方案[J].信息技術(shù)，2004，6（6）：6263.

[9]譚毓銀.CIDR在IP子網(wǎng)劃分中的應(yīng)用[J].信息安全與技術(shù)，2013，4（5）：7577.

[10]謝希仁.計(jì)算機(jī)網(wǎng)絡(luò)：第6版[M].北京：電子工業(yè)出版社，2015.

[11]潘登.基于軟件的高速路由查找算法研究[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2014.

[12]徐格.高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2012.

[13]曹道林.基于動(dòng)態(tài)規(guī)劃和B+樹(shù)的IP路由查找技術(shù)研究[D].長(zhǎng)沙：湖南大學(xué)，2015.

[14]杜慧軍.基于CIDR表的哈希地址二分查找算法的改進(jìn)[J].系統(tǒng)工程與電子技術(shù)，2009，31（3）：698701.

[15]李瑞俊.基于CIDR的網(wǎng)絡(luò)IP地址規(guī)劃及應(yīng)用[J].長(zhǎng)春師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，33（5）：3336.

責(zé)任編輯（責(zé)任編輯：何麗）endprint