賀興亞+楊云

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

關鍵詞關鍵詞：計算機網(wǎng)絡；無分類編址；IPv4；可變長子網(wǎng)掩碼

DOIDOI：10.11907/rjdk.171835

中圖分類號：TP393

文獻標識碼：A文章編號文章編號：16727800（2017）011020605

0引言

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

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

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

1無分類編址CIDR概述

1.1CIDR研究目的

1.1.1問題提出

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

1.1.2問題分析

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

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

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

無分類編址CIDR通過“地址塊”概念，可以大大減少路由器路由表項[9]。

1.2無分類編址CIDR含義

CIDR記為 IP地址 ：：= {<網(wǎng)絡前綴>， <主機號>} 或CIDR地址= <網(wǎng)絡前綴>/<主機號>

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

（2）“斜線記法”與分類IP地址都是IPv4地址的分配方法。CIDR不采用傳統(tǒng)的標準IPv4地址分類方法，而采用“斜線記法”表示IP地址，但無法從地址本身直接判斷網(wǎng)絡號的長度。對于無分類IP地址：200.16.23.1/20 =11001000 00010000 00010111 00000001，/20被稱為網(wǎng)絡前綴長度（或地址前綴長度），11001000 00010000 0001被稱為地址前綴比特值（或網(wǎng)絡號），0111 00000001被稱為主機號。

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

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

2分類編址與無分類編址比較

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

2.1分類編址表示

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

2.2用無分類編址表示分類編址

使用無分類編址可以表示分類編址中的A、B、C、D、E類地址，其對應關系見圖6-圖10。

3無分類編址CIDR技術

3.1工作方式

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

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

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

3.3CIDR地址塊計算

無分類編址地址塊由地址塊的起始地址（地址塊中數(shù)值最小）與最大地址（地址塊中數(shù)值最大）定義。

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

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

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

（1）地址塊162.82.0.0/11中含有221個主機號。

（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）通過無分類地址可以計算網(wǎng)絡ID，最小地址恰為子網(wǎng)網(wǎng)絡地址，最大地址恰為子網(wǎng)廣播地址。

3.4標記技術分析

3.4.1分類編址轉(zhuǎn)換為無分類編址

分類編址子網(wǎng)掩碼中，連續(xù)“1”的個數(shù)即為無分類編址的網(wǎng)絡前綴長度（見表2）。

3.4.2無分類編址計算網(wǎng)絡ID

根據(jù)無分類編址CIDR中網(wǎng)絡前綴長度，確定地址前綴長度，計算出地址前綴值（最小地址）即為網(wǎng)絡ID（見表3）。

3.4.3無分類編址最長前綴匹配

在配置基于CIDR的網(wǎng)絡時，查找路由表時可能會得到不止一個匹配結果。因為網(wǎng)絡前綴越長，其地址塊就越小，因而路由就越具體，所以應當從匹配結果中選擇具有最長網(wǎng)絡前綴的路由，這稱為“最長前綴匹配”。

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

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

匹配

目的IP地址與表項2網(wǎng)絡前綴作與運算10.217.112.0/20匹配 √

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

當采用無分類編址進行路由轉(zhuǎn)發(fā)時，若未啟動IP Classless命令，若目的IP地址不在路由表中，將采取丟包策略，而不會走默認路由。

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

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

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

3.4.4網(wǎng)絡前綴設置

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

事實上，由于CIDR標記法應用范圍廣、使用靈活，當主機軟件支持CIDR時，網(wǎng)絡前綴可以比原來的掩碼長度短，如表6所示。

由此得到結論：使用無分類編址CIDR，可以標記任意的地址塊。同時，合理、科學地分配地址塊顯得非常重要。

3.4.5超網(wǎng)構建

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

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

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

某公司需要600個地址，下面哪一組IP地址塊可以用于這個公司構成超網(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

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

一般地，根據(jù)CIDR標記特點，聚合結果總是網(wǎng)絡ID地址最小/網(wǎng)絡前綴。

3.5CIDR地址分配方法

主要有二叉樹法與遞增法。

3.5.1二叉樹法

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

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

圖11CIDR地址分配的二叉樹法

3.5.2遞增法

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

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

3.5.3兩種地址分配方法比較

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

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

3.6最長地址前綴匹配查找算法

在分類地址結構體系下，可以通過目的IP地址前幾個比特位的值獲得該地址所對應的類，從而知道匹配地址前綴的長度，因此地址前綴查找比較簡單。

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

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

4結語

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

參考文獻參考文獻：

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

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

[3]包叢笑，李星.IPv4/IPv6過渡的核心技術標準RFC6052[J].中國教育網(wǎng)絡，2010，12（1）：2829.

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

[5]李星.互聯(lián)網(wǎng)核心技術創(chuàng)新與網(wǎng)絡強國[C].北京：2015年第四屆高等學校計算機網(wǎng)絡類專業(yè)教育與教學研討會，2015.

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

[7]姚秀情.CIDR的簡單應用分析機電技術[J].機電技術，2013（4）：6365.

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

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

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

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

[12]徐格.高級計算機網(wǎng)絡[M].北京：清華大學出版社，2012.

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

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

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

責任編輯（責任編輯：何麗）endprint