划分子网和构造超.ppt

《划分子网和构造超.ppt》由会员分享，可在线阅读，更多相关《划分子网和构造超.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.3.1 划分子网划分子网1.从两级从两级 IP 地址到三级地址到三级 IP 地址地址 q 在在 ARPANET 的的早早期期，IP 地地址址的的设设计计确确实实不不 够合理够合理IP 地址空间的利用率有时很低地址空间的利用率有时很低给给每每一一个个物物理理网网络络分分配配一一个个网网络络号号会会使使路路由由表变得太大因而使网络性能变坏表变得太大因而使网络性能变坏两级的两级的 IP 地址不够灵活地址不够灵活4.3 划分子网和构造超网划分子网和构造超网q 从从 1985 年起在年起在 IP 地址中又增加了一个地址中又增加了一个“子子网号字段网号字段”，使两级的，使两级的 IP 地址变成为地址变

2、成为三级的三级的 IP 地址地址。q 这种做法叫作这种做法叫作划分子网划分子网(subnetting)。划分子。划分子网已成为因特网的正式标准协议网已成为因特网的正式标准协议 RFC950。三级三级 IP 地址地址 q 划划分分子子网网纯纯属属一一个个单单位位内内部部的的事事情情。单单位位对对外外仍仍然表现为没有划分子网的网络。然表现为没有划分子网的网络。q 从从主主机机号号借借用用若若干干个个比比特特作作为为子子网网号号 subnet-id，而主机号而主机号 host-id 也就相应减少了若干个比特。也就相应减少了若干个比特。划分子网的基本思路划分子网的基本思路 IP地址地址:=,(6-2)

3、q 凡凡是是从从其其他他网网络络发发送送给给本本单单位位某某个个主主机机的的 IP 数数据据报报，仍仍然然是是根根据据 IP 数数据据报报的的目目的的网网络络号号 net-id，先找到连接在，先找到连接在本单位网络上的路由器本单位网络上的路由器。q 然然后后此此路路由由器器在在收收到到 IP 数数据据报报后后，再再按按目目的的网网络络号号 net-id 和和子子网网号号 subnet-id 找找到到目目的的子子网。网。q 最后就将最后就将 IP 数据报直接交付给目的主机。数据报直接交付给目的主机。划分子网的基本思路（续）划分子网的基本思路（续）145.13.3.10145.13.3.11145

4、.13.3.101145.13.7.34145.13.7.35145.13.7.56145.13.21.23145.13.21.9145.13.21.8所有到网络所有到网络 145.13.0.0145.13.0.0的分组的分组均到达此路由器均到达此路由器我的网络地址我的网络地址是是 145.13.0.0R1R3R2网络145.13.0.0一个未划分子网的一个未划分子网的 B 类网络类网络划分为三个子网后对外仍是一个网络划分为三个子网后对外仍是一个网络 145.13.3.10145.13.3.11145.13.3.101145.13.7.34145.13.7.35145.13.7.56145.1

5、3.21.23145.13.21.9145.13.21.8子网子网 145.13.21.0子网子网 145.13.3.0 子网 145.13.7.0所有到达网络所有到达网络 145.13.0.0的分组均到达的分组均到达此路由器此路由器网络网络145.13.0.0R1R3R2路由器R1收到数据报后，再根据其目的地址转发到相应子网。q 当当没没有有划划分分子子网网时时，IP 地地址址是是两两级级结结构构，地地址址的的网网络络号号字字段段也也就就是是 IP 地地址址的的“因因特特网网部部分分”，而主机号字段是，而主机号字段是 IP 地址的地址的“本地部分本地部分”。q 划划分分子子网网后后 IP 地

6、地址址就就变变成成了了三三级级结结构构。划划分分子子网网只只是是将将 IP 地地址址的的本本地地部部分分进进行行再再划划分分，而而不不改变改变 IP 地址的因特网部分地址的因特网部分。划分子网后变成了三级结构划分子网后变成了三级结构 q 从从一一个个IP数数据据报报的的首首部部并并无无法法判判断断源源主主机机或或目目的的主主机机所所连连接接的的网网络络是是否否进进行行了了子子网网的的划划分。分。q 使使用用子子网网掩掩码码(subnet mask)可可以以找找出出 IP 地地址址中的子网部分。中的子网部分。2.子网掩码子网掩码4.3.1 划分子网划分子网(续续)IP 地址的各字段和子网掩码地址

7、的各字段和子网掩码 网络号网络号 net-id主机号主机号 host-id两级两级 IP 地址地址网络号网络号net-idhost-id三级三级 IP 地址地址主机号主机号subnet-id子网号子网号子网掩码子网掩码因特网部分因特网部分本地部分本地部分因特网部分因特网部分本地部分本地部分划分子网时划分子网时的网络地址的网络地址1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0net-idsubnet-idhost-id 为全为全 0(IP 地址地址)AND(子网掩码子网掩码)=网络地址网络地址网络号 net-id主机号

8、 host-id两级两级 IP 地址地址网络号三级三级 IP 地址地址主机号net-idhost-idhost-idsubnet-idsubnet-id子网号子网掩码子网掩码因特网部分因特网部分本地部分本地部分因特网部分因特网部分本地部分本地部分划分子网时划分子网时的网络地址的网络地址1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0net-idsubnet-idhost-id 为全为全 0ANDnet-idnet-idhost-id 为全为全 0net-id网络地址网络地址A类类地地址址默认子网掩码默认子网掩码255.

9、0.0.0网络地址网络地址B类类地地址址默认子网掩码默认子网掩码255.255.0.0网络地址网络地址C类类地地址址默认子网掩码默认子网掩码255.255.255.01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 10 0 0 0 0 0 0 0host-id 为全为全 0host-id 为全为全 0A

10、类、类、B 类和类和 C 类类 IP 地址的地址的默认默认子网掩码子网掩码 q 网络网络 不设子网的网络不设子网的网络不设子网的网络不设子网的网络172.16.0.0172.16.0.1 172.16.0.2 172.16.0.3.172.16.255.253 172.16.255.254q 网络网络 设置子网的网络设置子网的网络设置子网的网络设置子网的网络172.16.1.0172.16.2.0172.16.3.0172.16.4.0子网地址子网地址子网地址子网地址172.16.2.200172.16.2.2172.16.2.160172.16.2.1172.16.3.5172.16.3.1

11、00172.16.3.150E0172.16网络网络网络网络端口端口172.16.0.0172.16.0.0E0E1原路由表原路由表 2160主机主机.172.16.3.1E1子网地址子网地址子网地址子网地址E0E1172.162160网络网络主机主机.网络网络端口端口E0E1新路由表新路由表子网子网子网掩码子网掩码子网规划举例子网规划举例Q:已分配了一个已分配了一个C类地址：类地址：，假设需要，假设需要20个个子网，子网，每个子网有每个子网有5台台主机主机,试确定各子网地址和子网掩码。试确定各子网地址和子网掩码。A:1）对）对C类地址，要从最后类地址，要从最后8位中分出位中分出几位几位作为子

12、网地址：作为子网地址：242025 选择选择5位作为子网地址，共可提供位作为子网地址，共可提供30个子网地址。个子网地址。2）检查剩余的）检查剩余的位数位数能否满足每个子网中主机台数的要求：能否满足每个子网中主机台数的要求：235+2 可以满足每子网可以满足每子网5台主机的要求。台主机的要求。3）11111000B=248 子网掩码子网掩码为。为。4）子网地址子网地址可在可在8、16、24、32、240共共30个地址中个地址中 任意选择任意选择20个。个。子网划分举例子网划分举例子网划分举例子网划分举例Other Subnets。192.168.5.24192.168.5.8192.168.5

13、.16现有现有C类地址：类地址：192.168.5.0 要划分：要划分：20 个子网个子网5 主机主机/子网，如何划分？子网，如何划分？为避免网络和子网号混淆，为避免网络和子网号混淆，不使用不使用192.168.5.00000000子网子网为避免网络和子网的广播地址混淆，为避免网络和子网的广播地址混淆，不使用不使用192.168.5.11111000子网子网可使用的子网为：可使用的子网为：192.168.5.00001000,192.168.5.00010000,192.168.5.11110000所以，可用子网为所以，可用子网为25-2=30个，个，每个子网内可有每个子网内可有23-2=6台

14、主机。台主机。广播地址可达范围举例广播地址可达范围举例广播地址可达范围举例广播地址可达范围举例172.16.1.0172.16.2.0172.16.3.0172.16.4.0172.16.3.255(Directed broadcast)255.255.255.255(Local network broadcast)X X172.16.255.255(All subnets broadcast)广播到此为止广播地址练习广播地址练习广播地址练习广播地址练习地址地址类别类别子网子网广播地址广播地址201.222.10.60 子网掩码子网掩码15.16.193.6 128.16.32.13 153.

15、50.6.27 广播地址练习（答案）广播地址练习（答案）广播地址练习（答案）广播地址练习（答案）地址地址类别类别子网子网广播地址广播地址201.222.10.60 C子网掩码子网掩码15.16.193.6 A128.16.32.13 B153.50.6.27 Bq在不划分子网的两级在不划分子网的两级 IP 地址下，从地址下，从 IP 地址得出网络地址地址得出网络地址是个很简单的事。是个很简单的事。q但在划分子网的情况下，从但在划分子网的情况下，从IP地址却不能惟一地得出网络地址却不能惟一地得出网络地址来，这是因为网络地址取决于那个网络所采用的子网地址来，这是因为网络地址取决于那个网络所采用的子

16、网掩码，但数据报的首部并没有提供子网掩码的信息。掩码，但数据报的首部并没有提供子网掩码的信息。q使用子网划分后，路由表中的每行所包括的主要内容是：使用子网划分后，路由表中的每行所包括的主要内容是：目的网络地址、子网掩码、下一跳地址目的网络地址、子网掩码、下一跳地址 q因此分组转发的算法也必须做相应的改动。因此分组转发的算法也必须做相应的改动。4.3.2 使用子网掩码的分组转发过程使用子网掩码的分组转发过程在划分子网的情况下路由器转发分组的算法在划分子网的情况下路由器转发分组的算法(1)从收到的分组的首部提取目的 IP 地址 D。(2)用路由器直连的各网络的子网掩码和 D 逐比特相“与”，看是否

17、和相应的直连网络地址匹配。若匹配，则将分组直接交付。否则就是间接交付，执行(3)。(3)若路由表中有目的地址为 D 的特定主机路由，则将 分组传送给指明的下一跳路由器；否则，执行(4)。(4)对路由表中的每一行的子网掩码和 D 逐比特相“与”，若其结果与该行的目的网络地址匹配，则将分组传送 给该行指明的下一跳路由器；否则，执行(5)。(5)若路由表中有一个默认路由，则将分组传送给路由表 中所指明的默认路由器；否则，执行(6)。(6)向源结点发送一个ICMP包报告转发分组出错。目的网络地址目的网络地址子网掩码子网掩码下一跳下一跳128.30.33.0128.30.33.128128.30.36.

18、0255.255.255.128255.255.255.128255.255.255.0接口接口 0接口接口 1128.30.33.129128.30.33.10128.30.33.13H1子网子网1：网络地址网络地址 128.30.33.0 子网掩码子网掩码 255.255.255.128128.30.33.130R1 的路由表（未给出默认路由器）的路由表（未给出默认路由器）R11R2子网子网2：网络地址：网络地址 128.30.33.128 子网掩码子网掩码 255.255.255.128H2128.30.33.13801128.30.33.129H3128.30.36.2子网子网3：网络

19、地址：网络地址 128.30.36.0 子网掩码子网掩码 255.255.255.0128.30.36.12划分子网后分组的转发举例划分子网后分组的转发举例 主机主机 H1 要发送分组给要发送分组给 H2 目的网络地址目的网络地址子网掩码子网掩码下一跳下一跳128.30.33.0128.30.33.128128.30.36.0255.255.255.128255.255.255.128255.255.255.0接口接口 0接口接口 1128.30.33.129128.30.33.10R1 的路由表（未给出默认路由器）的路由表（未给出默认路由器）128.30.33.13H1子网子网1：网络地址网

20、络地址 128.30.33.0 子网掩码子网掩码 255.255.255.128128.30.33.130R11R2子网子网2：网络地址：网络地址 128.30.33.128 子网掩码子网掩码 255.255.255.128H2128.30.33.13801128.30.33.129H3128.30.36.2子网子网3 3：网络地址：网络地址 128.30.36.0128.30.36.0 子网掩码子网掩码 255.255.255.0255.255.255.0128.30.36.12要发送的分组的目的 IP 地址：128.30.33.138 主机主机主机主机 HH1 1 将分组的目的将分组的目的

21、将分组的目的将分组的目的 IP IP 地址地址地址地址 与自己所在网络的与自己所在网络的与自己所在网络的与自己所在网络的子网掩子网掩子网掩子网掩码码码码 逐比特相逐比特相逐比特相逐比特相“与与与与”(ANDAND 操作操作操作操作)：10000000 00011110 00100001 100 01010 11111111 11111111 11111111 100 00000 =10000000 00011110 00100001 100 00000 “与与”运算结果不等于主机运算结果不等于主机H1自己所在网络地址，由此自己所在网络地址，由此IP地址地址128.30.33.138 128.3

22、0.33.138 的的的的目的目的主机不在主机不在主机不在主机不在H1H1所在的子网中，所以须所在的子网中，所以须所在的子网中，所以须所在的子网中，所以须间接交付间接交付间接交付间接交付。前图中子网地址的计算举例前图中子网地址的计算举例IP地址地址子网掩码子网掩码=该该 IP地址的网络号地址的网络号前图寻路过程祥析如下：前图寻路过程祥析如下：qH1 首先检查目的主机首先检查目的主机 128.30.33.138 是否连接在是否连接在H1自己直自己直连的网络上。如果是，则直接交付；否则，就间接交付，连的网络上。如果是，则直接交付；否则，就间接交付，送交路由器送交路由器 R1。结果：不连接在自己直连

23、的网上结果：不连接在自己直连的网上q H1 必须把分组间接交付、传送到路由器必须把分组间接交付、传送到路由器 R1，然后逐项查，然后逐项查找路由表找路由表q路由器路由器 R1 收到分组后就用和路由表中第收到分组后就用和路由表中第 1 个表项的子网个表项的子网掩码逐比特掩码逐比特 AND 操作。操作。结果：不匹配结果：不匹配q路由器路由器 R1 再用和路由表中第再用和路由表中第 2 个表项的子网掩码逐比特个表项的子网掩码逐比特 AND 操作。操作。结果：匹配结果：匹配q路由器路由器R1断定第二个表项的网络断定第二个表项的网络(子网子网2)就是收到的分组所就是收到的分组所要寻找的目的网络，于是要寻

24、找的目的网络，于是R1将分组从接口将分组从接口1直接交付给主直接交付给主机机H2 划分子网在一定程度上缓解了因特网在发展划分子网在一定程度上缓解了因特网在发展中中遇遇到到的的困困难难。然然而而当当前前因因特特网网使使用用的的寻寻址址方方案案面临三个必须尽早解决的问题，这就是：面临三个必须尽早解决的问题，这就是：q IPv4 A类地址已全部分完，类地址已全部分完，B类只有极少数未类只有极少数未 分配，分配，C类地址也已所剩无几；类地址也已所剩无几；q 因特网主干网路由器中的路由表项急剧增长因特网主干网路由器中的路由表项急剧增长 (从几千个增长到几万个从几千个增长到几万个),导致查找速度变慢；导致

25、查找速度变慢；q 按目前地址分配速度，按目前地址分配速度，2008 年左右会全部分年左右会全部分 完，整个完，整个 IPv4 的地址空间最终将全部耗尽。的地址空间最终将全部耗尽。4.3.3 无分类编址无分类编址 CIDR1.网络前缀网络前缀q1987 年年，RFC 1009 就就指指明明了了在在一一个个划划分分子子网网的的网网络络中中可可同同时时使使用用几几个个不不同同的的子子网网掩掩码码。使使用用变变长长子子网网掩掩码码 VLSM(Variable Length Subnet Mask)可进一步提高可进一步提高 IP 地址资源的利用率。地址资源的利用率。q在在 VLSM 的的基基础础上上又又

26、进进一一步步研研究究出出无无分分类类编编址址方方法法，它它的的正正式式名名字字是是无无分分类类域域间间路路由由选选择择 CIDR(Classless Inter-Domain Routing)。IP 编址问题的演进编址问题的演进 qCIDR 消消除除了了传传统统的的 A 类类、B 类类和和 C 类类地地址址以以及及划划分分子子网网的的概概念念，因因而而可可以以更更加加有有效效地地分分配配 IPv4 的地址空间。的地址空间。qCIDR使使用用各各种种长长度度的的“网网络络前前缀缀”(network-prefix)来代替分类地址中的网络号和子网号。来代替分类地址中的网络号和子网号。qIP 地地址址

27、从从三三级级编编址址（使使用用子子网网掩掩码码）又又回回到到了了两两级编址。级编址。CIDR 最主要的特点最主要的特点 q 无分类的两级编址的记法是：无分类的两级编址的记法是：q CIDR 还还使使用用“斜斜线线记记法法”(slash notation)，它它又又称称 为为CIDR记记法法，即即在在IP地地址址后后面面加加上上一一个个斜斜线线“/”，然后写上网络前缀所占的比特数（这个数值对应于然后写上网络前缀所占的比特数（这个数值对应于 三级编址中子网掩码中比特三级编址中子网掩码中比特 1 的个数）。的个数）。q CIDR 将网络前缀都相同的连续的将网络前缀都相同的连续的 IP 地址组成地址组

28、成 “CIDR地址块地址块”。IP地址地址:=,无分类无分类的两级编址的两级编址 CIDR 地址块地址块 q表表示示的的地地址址块块共共有有 212 个个地地址址（因因为为斜斜线线后后面面的的 20 是是网网络络前前缀缀的的比比特特数数，所所以以主主机机号号的的比比特特数数是是 12）。）。q在在不不需需要要指指出出地地址址块块的的起起始始地地址址时时，也也可可将将这这样样的地址块简称为的地址块简称为“/20 地址块地址块”。q这个地址块起始地址是这个地址块起始地址是 0000.00000000，地址块的地址块的最小地址：最小地址：地址块的最大地址：地址块的最大地址：一一般般，地地址址块块内内

29、全全 0 和和全全 1 的的地地址址不不能能分分配配给主机，分别表示该块的网络地址和广播地址。给主机，分别表示该块的网络地址和广播地址。表示的地址（表示的地址（212 个地址）：个地址）：10000000 00001110 00100000 0000000010000000 00001110 00100000 0000000110000000 00001110 00100000 0000001010000000 00001110 00100000 0000001110000000 00001110 00100000 0000010010000000 00001110 00100000 0000

30、010110000000 00001110 00111111 1111101110000000 00001110 00111111 1111110010000000 00001110 00111111 1111110110000000 00001110 00111111 1111111010000000 00001110 00111111 11111111所有地址所有地址的的 20 bit前缀都是前缀都是一样的一样的最小地址最小地址最大地址最大地址q一一个个 CIDR 地地址址块块可可以以表表示示很很多多地地址址，这这种种地地址址的的聚聚合合常常称称为为路路由由聚聚合合。用用CIDR地地址址块

31、块后后，可可以以使使路路由由表表中中的的表表项项大大大大减减少少，使使得得路路由由表表中中的的一一个个项项目目可可以以表表示示很很多多个个（例例如如上上千千个个）原原来来传传统统分类地址的路由。分类地址的路由。q路由聚合也称为路由聚合也称为构成超网构成超网(supernetting)。qCIDR 虽虽然然不不使使用用子子网网了了，但但仍仍然然使使用用“掩掩码码”这这一名词（但不叫子网掩码）。一名词（但不叫子网掩码）。q对对于于/20 地地址址块块，它它的的掩掩码码是是 20 个个连连续续的的 1。斜斜线线记法中的数字就是掩码中记法中的数字就是掩码中1的个数。的个数。路由聚合路由聚合(route

32、 aggregation)CIDR 记法的其他形式记法的其他形式 q 可可简简写写为为 10/10，也也就就是是将将点点分分十十进进制制中中低低位位连连续续的的 0 省略。省略。q 隐隐含含地地指指出出 IP 地地址址 10.0.0.0 的的掩掩码码是是。此此掩掩码码可可表表示示为为 11111111 11 000000 00000000 00000000q 网络前缀的后面加一个星号网络前缀的后面加一个星号*的表示方法的表示方法,如如 00001010 00*，在星号，在星号*之前是网络前缀，而星号之前是网络前缀，而星号*表表示示 IP 地址中的主机号，可以是任意值地址中的主机号，可以是任意值

33、。25519200掩码中有掩码中有 10 个连续的个连续的 1构成超网构成超网 q前前缀缀长长度度不不超超过过 23 bit 的的 CIDR 地地址址块块都都包包含含了了多多个个 C 类地址。类地址。q这这些些 C 类类地地址址合合起起来来就就构构成成了了超超网网。如如地地址址块块和和 就聚合成超网，而地址块、和就聚合成超网，而地址块、和 就聚合成超网就聚合成超网。qCIDR 地址块中的地址数一定是地址块中的地址数一定是 2 的整数次幂。的整数次幂。q网网络络前前缀缀越越短短，其其地地址址块块所所包包含含的的地地址址数数就就越越多多。而而在在三三级级结结构构的的IP地地址址中中，划划分分子子网

34、网是是使使网网络络前前缀缀变长。变长。CIDR 地址块全地址块全0和全和全1地址限制问题地址限制问题 需要注意的是：在早期的 RFC 950 文档规定中，网络划分为子网后，子网号全0和全1的地址不能分配给子网，这是为了避免网络与0号子网两者的网络地址相同而产生二义性问题、同时也避免了网络与全1子网两者的广播地址相同而产生的二义性问题，这个规定仍应遵守。但是，在无类别域间路由在无类别域间路由(CIDR)中中用前缀表示地址块的范围，不存在子网号全不存在子网号全0和全和全1的限制问题的限制问题，如网络地址 和、广播地址和无二义性问题；但地址块内全但地址块内全 0 和全和全 1 的地址仍然不能的地址仍

35、然不能分配给主机分配给主机，它们分别用于表示该地址块的网络地址和该地址块的广播地址。CIDR 地址块划分举例地址块划分举例 因特网206.0.68.0/22206.0.64.0/18ISP大学大学 X一系二系三系四系206.0.71.128/26206.0.71.192/26206.0.68.0/25206.0.68.128/25206.0.69.0/25206.0.69.128/25206.0.70.0/26206.0.70.64/26206.0.70.128/26206.0.70.192/26206.0.70.0/24206.0.71.0/25206.0.71.0/26206.0.71.6

36、4/26206.0.71.128/25206.0.68.0/23 单位 地址块 二进制表示 地址数 ISP 206.0.64.0/18 11001110.00000000.01*16384 大学 206.0.68.0/22 11001110.00000000.010001*1024 一系 206.0.68.0/23 11001110.00000000.0100010*512 二系 206.0.70.0/24 11001110.00000000.01000110.*256 三系 206.0.71.0/25 11001110.00000000.01000111.0*128 四系 206.0.71.

37、128/25 11001110.00000000.01000111.1*128CIDR 地址块划分举例地址块划分举例 因特网206.0.68.0/22206.0.64.0/18ISP大学 X一系二系三系四系206.0.71.128/26206.0.71.192/26206.0.68.0/25206.0.68.128/25206.0.69.0/25206.0.69.128/25 206.0.70.0/26206.0.70.64/26206.0.70.128/26206.0.70.192/26206.0.70.0/24206.0.71.0/25206.0.71.0/26206.0.71.64/26

38、206.0.71.128/25206.0.68.0/23 这个这个 ISP 共有共有 64 个个 C 类网络。如果不采用类网络。如果不采用 CIDR 技术，则技术，则在与该在与该 ISP 的路由器交换路由信息的每一个路由器的路由表中，的路由器交换路由信息的每一个路由器的路由表中，就需要有就需要有 64 个项目。但采用地址聚合后，只需用路由聚合后的个项目。但采用地址聚合后，只需用路由聚合后的 1 个项目个项目 206.0.64.0/18 就能找到该就能找到该 ISP。2.最长前缀匹配最长前缀匹配q使使用用CIDR时时，路路由由表表中中每每个个项项目目由由“目目的的网网络络(网网络络前前缀缀)”和

39、和“下下一一跳跳地地址址”组组成成。在在查查找找路路由由表表时时可可能能会会得得到到不不止一个匹配结果，如欲转发止一个匹配结果，如欲转发目的地址目的地址 的信包时的信包时：q应应当当从从匹匹配配结结果果中中选选择择具具有有最最长长网网络络前前缀缀的的路路由由：最最长长前前缀匹配缀匹配(longest-prefix matching)。q网络前缀越长，其地址块就越小，因而路由就越具体。网络前缀越长，其地址块就越小，因而路由就越具体。q最长前缀匹配又称为最长前缀匹配又称为最长匹配最长匹配或或最佳匹配最佳匹配。目的网络目的网络(网络前缀网络前缀)下一跳地址下一跳地址206.0.68.0/22202.

40、195.1.1206.0.71.128/25202.195.2.1最长前缀匹配举例最长前缀匹配举例收到的分组的目的地址收到的分组的目的地址 D=206.0.71.130路由表中的项目路由表中的项目：206.0.68.0/22 （大学X）206.0.71.128/25 （四系）先查找路由表中的第先查找路由表中的第 1 1 个项目：个项目：AND D=206.0.010001 11.130第第 1 个项目个项目 206.0.68.0/22 的掩码的掩码 M 有有 22 个连续的个连续的 1。M=11111111 11111111 11111100 00000000因此只需把因此只需把 D 的第的第

41、 3 个字节转换成二进制。个字节转换成二进制。M=11111111 11111111 111111 00 00000000 206.0.010001 00.0与与 206.0.68.0/22 匹配匹配最长前缀匹配举例最长前缀匹配举例收到的分组的目的地址收到的分组的目的地址 D=206.0.71.130路由表中的项目：路由表中的项目：206.0.68.0/22 （大学X）206.0.71.128/25 （四系）（四系）再查找路由表中的第再查找路由表中的第 2 2 个项目：个项目：AND D=206.0.71.1 0000010第第 2 个项目个项目 206.0.71.128/25 的掩码的掩码

42、M 有有 25 个连续的个连续的 1。M=11111111 11111111 11111111 10000000因此只需把因此只需把 D 的第的第 4 个字节转换成二进制。个字节转换成二进制。M=11111111 11111111 11111111 1 0000000 206.0.71.1 0000000也与也与 206.0.71.128/25 匹配匹配最长前缀匹配最长前缀匹配D AND(11111111 11111111 11111100 00000000)匹配匹配D AND(11111111 11111111 11111111 10000000)匹配匹配q 选择选择两个匹配的地址中更具体两

43、个匹配的地址中更具体的一个，即选择最长的一个，即选择最长前缀的地址，应该选择后者。前缀的地址，应该选择后者。3.使用二叉线索查找路由表使用二叉线索查找路由表q当当路路由由表表的的项项目目数数很很大大时时，怎怎样样设设法法减减小小路路由由表表的的查找时间就成为一个非常重要的问题。查找时间就成为一个非常重要的问题。q为为了了进进行行更更加加有有效效的的查查找找，通通常常是是将将无无分分类类编编址址的的路路由由表表存存放放在在一一种种层层次次的的数数据据结结构构中中，然然后后自自上上而而下下地地按按层层次次进进行行查查找找。这这里里最最常常用用的的就就是是二二叉叉线线索索(binary trie)。qIP 地地址址中中从从左左到到右右的的比比特特值值决决定定了了从从根根结结点点逐逐层层向向下下层层延延伸伸的的路路径径，而而二二叉叉线线索索中中的的各各个个路路径径就就代代表表路由表中存放的各个地址。路由表中存放的各个地址。q为为了了提提高高二二叉叉线线索索的的查查找找速速度度，广广泛泛使使用用了了各各种种压压缩技术。缩技术。