1、现代骨干网与高速互联网技术Modern Backbone Network & High-Speed Internet Technology邬 春 学http:/ 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术第3部分 骨干网络路由与交换技术n3.1 路由技术概述n3.2 路由算法n3.3 路由协议n3.4 高速路由技术n3.5 交换路由技术n3.6 光交换技术现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.1 路由技术概述n路由技术是互联网的核心技术。n实现高速互联的一个重要方面是如何提高路由器的能力，使之与线路的高
2、速传输能力相适应。n计算机网络中的分组交换是由路由系统完成的。n路由系统是指实现分组存储转发的各个节点（由路由器或交换机组成）通过线路相互连接构成的系统。n路由系统是计算机网络数据传输的核心部分，它构成计算机网络中的通信子网。n组成路由系统的核心是路由器。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术图图2.1 2.1 路由系统构成的通信子网路由系统构成的通信子网现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术典型的路由方式：静态路由和动态路由1、静态路由静态路由策略不用测量也无须利用网络动态
3、信息，这种策略静态路由策略不用测量也无须利用网络动态信息，这种策略按某种固定规则进行路由选择。按某种固定规则进行路由选择。路由器中设置固定的路由表路由器中设置固定的路由表，除非管理员干预，否则静态路，除非管理员干预，否则静态路由不会发生变化。由不会发生变化。适合网络规模不大、拓扑结构固定的网络中适合网络规模不大、拓扑结构固定的网络中. .特点：简单、高效，灵活性差、无法应对阻塞和故障；在所特点：简单、高效，灵活性差、无法应对阻塞和故障；在所有的路由器中静态路由优先级最高。有的路由器中静态路由优先级最高。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交
4、换技术2、动态路由节点路由选择是由网络当前状态信息决定的策略被称为动态节点路由选择是由网络当前状态信息决定的策略被称为动态路由选择策略。路由选择策略。适合网络流量和拓扑结构变化的网络中适合网络流量和拓扑结构变化的网络中. .即网络规模大、网即网络规模大、网络拓扑复杂的网络。络拓扑复杂的网络。特点特点：算法复杂，会增加网络负担。有时反应慢甚至不起作：算法复杂，会增加网络负担。有时反应慢甚至不起作用。用。问题提出：网络动态会影响数据报的转发；如果网络不稳定问题提出：网络动态会影响数据报的转发；如果网络不稳定，会导致端到端传输性能下降。，会导致端到端传输性能下降。设计性能好的路由算法是路由研究中的一
5、个重要方面。设计性能好的路由算法是路由研究中的一个重要方面。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术整个互联网划分为多个自治域。自治域是指具有统一整个互联网划分为多个自治域。自治域是指具有统一管理机构，统一路由策略的网络。根据是否在一个自治域管理机构，统一路由策略的网络。根据是否在一个自治域内部使用，动态路由协议分为内部网关协议（内部使用，动态路由协议分为内部网关协议（IGP）和外）和外部网关协议（部网关协议（EGP）。）。IGP:内部协议需要计算有效路由，并在任何网络拓扑内部协议需要计算有效路由，并在任何网络拓扑结构发生变化之后很快重
6、复计算有效的路由。常用的有：结构发生变化之后很快重复计算有效的路由。常用的有：RIP,OSPF,IGRP(内部网关路由协议：Interior Gateway Routing Protocol), EIGRP, IS-IS(中间系统到中间系统的路由选择协议 Intermediate System to Intermediate System Routing Protocol )等。等。EGP:自治系统之间操作，协议有自治系统之间操作，协议有EGP和和BGP，现在，现在几乎都用几乎都用BGP。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.2
7、路由算法3.2.1 路由设计目标n优化n简单n稳健n快速收敛现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.2 路由算法3.2.2 路由算法中使用的度量n路径长度n可靠性n延迟n带宽n负载n通信成本现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术路由协议算法分类：n是否支持无类路由n有类路由协议：RIPv1n无类路由协议：RIPv2,OSPF,IS-IS,BGPv4n路由算法n距离向量路由协议(距离向量算法)：RIPn链路状态路由协议 (最短路径优先算法)：IS-IS,OSPF3.2 路由算
8、法现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.2.3 距离向量算法3.2 路由算法现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术距离向量路由协议路由更新n路由更新信息只传播到直连的邻居路由器路由表路由表所有路由所有路由现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术链路状态 路由协议 路由更新n链路状态的通告，广播到路由域的所有路由器链路状态的通告，广播到路由域的所有路由器n分层设计可以限制广播流量分层设计可以限制广播流量路由表路由表O
9、ne Route 现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术有类路由和无类路由选择协议 IP IP路由选择协议可分为有类路由和无类路由选择协路由选择协议可分为有类路由和无类路由选择协议。议。n 有类路由选择协议发送的路由选择更新不包含子网有类路由选择协议发送的路由选择更新不包含子网掩码信息，如掩码信息，如RIPv1RIPv1；n 无类路由选择协议发送的路由选择更新包含子网掩无类路由选择协议发送的路由选择更新包含子网掩码信息，如码信息，如RIPv2RIPv2，EIGRP,OSPFEIGRP,OSPF，IS-ISIS-IS和和BPGBPG。现
10、代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术有类路由路由传递n如果路由器收到有关一个网络的信息，并且如果接收接口属如果路由器收到有关一个网络的信息，并且如果接收接口属于同一网络（但在不同的子网），则路由器应用配置在接口于同一网络（但在不同的子网），则路由器应用配置在接口上的子网掩码。上的子网掩码。n如果路由器收到有关一个网络的信息，但该信息与接收接口如果路由器收到有关一个网络的信息，但该信息与接收接口上所配置的网络地址的信息不同，则路由器应用缺省的（根上所配置的网络地址的信息不同，则路由器应用缺省的（根据类别）子网掩码。据类别）子网掩码。10
11、.1.0.0/16172.16.2.0/2410.2.0.0/1610.1.0.010.2.0.0172.16.0.010.0.0.0172.16.1.0172.16.2.010.1.0.010.2.0.0172.16.1.0172.16.2.0172.16.1.0/24不包括路由掩不包括路由掩码信息码信息现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术无类路由路由传递n每个路由器具有全部网段的详细路由每个路由器具有全部网段的详细路由n允许手工配置汇总路由允许手工配置汇总路由10.1.0.0/16172.16.2.0/2410.2.0.0/16
12、10.1.0.010.2.0.0172.16.1.0172.16.2.0172.16.1.0/2410.1.0.010.2.0.0172.16.1.0172.16.2.010.1.0.010.2.0.0172.16.1.0172.16.2.0现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术有类路由子网划分n在同一网络内，所有路由器接口的子网掩码必须相同在同一网络内，所有路由器接口的子网掩码必须相同n可能造成对地址的浪费可能造成对地址的浪费192.168.5.129 /27192.168.5.98 /27192.168.5.33 /27192.1
13、68.5.65 /27192.168.5.97 /27S1S0E1E0E0实际只需要两个实际只需要两个地址地址,却分配了却分配了30个地址个地址现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术无类路由 子网划分n在同一网络内，所有路由器接口的子网掩码可以不同在同一网络内，所有路由器接口的子网掩码可以不同n支持支持VLSMVLSM（变长掩码）（变长掩码）n可以充分利用可用的地址可以充分利用可用的地址192.168.5.129 /27192.168.5.209 /30192.168.5.33 /27192.168.5.65 /27192.168.5
14、.210 /30S1S0E1E0E0满足满足2个主机个主机地址的需要地址的需要DDN现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.2.4 环路探测和保护n所谓所谓 路由收敛，是指网络拓扑结构发生变化（如线路故路由收敛，是指网络拓扑结构发生变化（如线路故障、网络结构改变、路由器失效等）或者路由策略（在障、网络结构改变、路由器失效等）或者路由策略（在BGPBGP中普遍使用）发生改变后，网络中各个路由器对当前中普遍使用）发生改变后，网络中各个路由器对当前网络结构重新形成一致认识的过程。网络结构重新形成一致认识的过程。n尽可能加快路由收敛是路由算
15、法设计中的一个重要方面。尽可能加快路由收敛是路由算法设计中的一个重要方面。n环路的产生是影响收敛性能的一个重要因素。环路的产生是影响收敛性能的一个重要因素。3.2 路由算法现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术几乎所有的路由算法协议在某种条件下都可能导致环路几乎所有的路由算法协议在某种条件下都可能导致环路。一旦形成环路，就会立即导致链路的失效。一旦形成环路，就会立即导致链路的失效。路由环路（路由环路（routing loopsrouting loops）问题，即到达某个目标网络）问题，即到达某个目标网络的网络的路由在多个路由器之间循环
16、传送。的网络的路由在多个路由器之间循环传送。有有2 2种应付环路的基本方法：种应付环路的基本方法：（1 1）环路预防：在任何分组发送到环路之前，应预防环）环路预防：在任何分组发送到环路之前，应预防环路形成；路形成；（2 2）环路缓和：采取一些措施来减少环路的负面影响。）环路缓和：采取一些措施来减少环路的负面影响。3.2.4 环路探测和保护现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术RIP的存在问题路由环路10.1.0.010.2.0.010.3.0.0E0S0S0S1S0E010.4.0.010.1.0.0E0010.2.0.0S0010.
17、3.0.0S0110.4.0.0S0210.2.0.0S0010.3.0.0S1010.4.0.0S1110.1.0.0S0110.3.0.0S0010.4.0.0E0Down10.2.0.0S0110.1.0.0S02现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术RIP的存在问题路由环路10.1.0.010.2.0.010.3.0.0E0S0S0S1S0E010.1.0.0E0010.2.0.0S0010.3.0.0S0110.4.0.0S0210.2.0.0S0010.3.0.0S1010.4.0.0S1110.1.0.0S1110.3.
18、0.0S0010.4.0.0E0210.2.0.0S0110.1.0.0S02现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术RIP的存在问题路由环路10.1.0.010.2.0.010.3.0.0E0S0S0S1S0E0现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术RIP的存在问题路由环路 (度量值趋向于无穷大度量值趋向于无穷大)10.1.0.010.2.0.010.3.0.0E0S0S0S1S0E00现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与
19、交换技术RIP的存在问题路由环路(RIPRIP定义最大值为定义最大值为1515)10.1.0.010.2.0.010.3.0.0E0S0S0S1S0E010.3.0.0S0S0S0S01210.1.0.010.2.0.010.4.0.0016E0S0S0S011610.1.0.010.4.0.010.3.0.010.2.0.000S0S1S1S016110.2.0.010.1.0.010.4.0.010.3.0.00016作为一种不可达的标记从路由自环产生的后果的角度来考虑问题，缺点是限制了网络的规模现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换
20、技术n一种消除路由环路并加快网络收敛的方法是通过叫做“水平分割”的技术实现的。n其规则就是不向原始路由更新的方向再次发送路由更新信息。n3台路由器ABC，B向C学习到访问网络10.4.0.0的路径以后，不再向C声明自己可以通过C访问10.4.0.0网络的路径信息，A向B学习到访问10.4.0.0网络路径信息后，也不再向B声明，而一旦网络10.4.0.0发生故障无法访问，C会向A和B发送该网络不可达到的路由更新信息，但不会再学习A和B发送的能够到达10.4.0.0的错误信息。 解决路由环路的方法：（1）水平分割现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路
21、由与交换技术解决路由环路的方法：（1）水平分割10.1.0.010.2.0.010.3.0.010.4.0.0E0S0S0S1S0E0现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术解决路由环路的方法： （2）确认收敛:毒性反转10.1.0.010.2.0.010.3.0.0E0S0S0S1S0E010.3.0.0S0S0S0S01210.1.0.010.2.0.010.4.0.00 1610.1.0.0E0S0S0S01210.4.0.010.3.0.010.2.0.00010.2.0.0S0S1S1E1PossiblyDown210.1.0
22、.010.4.0.010.3.0.000Subnet 10.4.0.0 metric 16当一条路径信息变为无效之后，路由器并不立即将它从路由表中删除，而是用16，即不可达的度量值将它广播出去。缺点增加了路由表的大小。 现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术n定义最大值在一定程度上解决了路由环路问题，但并不彻底，在达到最大值之前，路由环路还是存在的。路由中毒就可以彻底解决这个问题。n其原理：3台路由器ABC，当网络10.4.0.0出现故障无法访问的时候，路由器C便向邻居路由发送相关路由更新信息，并将其度量值标为无穷大，告诉它们网络10
23、.4.0.0不可到达，路由器B收到毒化消息后将该链路路由表项标记为无穷大，表示该路径已经失效，并向邻居A路由器通告，依次毒化各个路由器，告诉邻居10.4.0.0这个网络已经失效，不再接收更新信息，从而避免了路由环路。n当路由器B看到到达网络10.4.0.0的度量值为无穷大的时候，就发送一个叫做毒化逆转的更新信息给C路由器，说明10.4.0.0这个网络不可达到，这是超越水平分割的一个特列，这样保证所有的路由器都接受到了毒化的路由信息。解决路由环路的方法： （2）确认收敛:毒性反转现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术解决路由环路的方法：
24、 （3）触发更新10.2.0.010.3.0.010.4.0.0E0S0S0S1S0E0Xsubnet 10.4.0.0, metric 1610.1.0.0subnet 10.4.0.0, metric 16subnet 10.4.0.0, metric 16得知网络拓扑结构发生改变,不等待发送周期 ,立刻通告更新后全部的路由表。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术 正常情况下，路由器会定期将路由表发送给邻居路由器。而触发更新就是立刻发送路由更新信息。 检测到网络故障的路由器会立即发送一个更新信息给邻居路由器，并依次产生触发更新通
25、知它们的邻居路由器，使整个网络上的路由器在最短的时间内收到更新信息，从而快速了解整个网络的变化。 问题：有可能包含更新信息的数据包被某些网络中的链路丢失或损坏，其他路由器没能及时收到触发更新，因此就产生了结合抑制的触发更新，抑制规则要求一旦路由无效，在抑制时间内，到达同一目的地有同样或更差度量值的路由将会被忽略，这样触发更新将有时间传遍整个网络，从而避免了已经损坏的路由重新插入到已经收到触发更新的邻居中，也就解决了路由环路的问题。解决路由环路的方法： （3）触发更新现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术10.1.0.010.2.0.0
26、10.3.0.010.4.0.0E0S0S0S1S0E0hold-down倒记时以后更新路由表hold-down倒记时以后更新路由表等待网络中其它路由器收敛等待网络中其它路由器收敛, ,在该时间内不学习任何与该网在该时间内不学习任何与该网络相关的路由信息络相关的路由信息(RIP(RIP缺省缺省180180秒秒),),在倒记时期间继续向其在倒记时期间继续向其它路由器发送毒化信息它路由器发送毒化信息解决路由环路的方法：（4）Hold-down倒记时 （控制更新时间 （即抑制计时器）现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术抑制计时器用于阻止定
27、期更新的消息在不恰当的时间内重置一个已经坏掉的路由。抑制计时器告诉路由器把可能影响路由的任何改变暂时保持一段时间，抑制时间通常比更新信息发送到整个网络的时间要长。当路由器从邻居接收到以前能够访问的网络现在不能访问的更新后，就将该路由标记为不可访问，并启动一个抑制计时器，如果再次收到从邻居发送来的更新信息，包含一个比原来路径具有更好度量值的路由，就标记为可以访问，并取消抑制计时器。如果在抑制计时器超时之前从不同邻居收到的更新信息包含的度量值比以前的更差，更新将被忽略，这样可以有更多的时间让更新信息传遍整个网络。解决路由环路的方法：（4）Hold-down倒记时 （控制更新时间 （即抑制计时器）现
28、代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.2.5 链路状态算法n链路状态LS(Link Status)算法，也称为最短路径优先SPF（Shortest Path First）算法。n每个路由器拥有网络全部的拓扑结构信息n采用Dijkstra最短路径算法求得最短路径现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术获得链路状态n路由器周期性地发送短报文，询问相邻路由器是否可以到达并处于活动状态。n如果相邻路由器做出回答，说明两者之间的链接正常，否则认为链路故障。n避免抖动，采取n中取k原则3
29、.2.5 链路状态算法现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术SPF算法的优点n每个路由器使用相同的原始状态数据，不依赖中间结点的计算，可以独立计算出路由，确保了路由算法的收敛性；n链路状态报文仅包含单一路由器与相邻路由器的链接信息，报文长度与网络的规模无关，因此，算法适用于大型的互联网。3.2.5 链路状态算法现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术典型的链路状态协议n开放式最短路径优先OSPF（Open Shortest Path First）3.2.5 链路状态算法现代骨干
30、网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.2.6 混合路由算法n距离向量算法和链路状态算法各有特点，适合不同的场所。距离向量算法和链路状态算法各有特点，适合不同的场所。n混合路由算法集合这两种算法优点。混合路由算法集合这两种算法优点。nEIGRPEIGRP就是典型的混合路由算法协议，称为就是典型的混合路由算法协议，称为高级距离向量算高级距离向量算法。法。nEIGRPEIGRP同时具有距离向量算法和链路状态算法特点。同时具有距离向量算法和链路状态算法特点。nEIGRPEIGRP只向相邻路由器发送更新分组，路由更新信息包括本只向相邻路由器发送更新
31、分组，路由更新信息包括本机路由信息，使用水平分割的方法控制路由信息传送回送它机路由信息，使用水平分割的方法控制路由信息传送回送它的源端的源端类似于距离向量算法。类似于距离向量算法。n为了避免在传输过程中出错，引起路由问题，为了避免在传输过程中出错，引起路由问题， EIGRPEIGRP使用更使用更可靠的机制传输路由协议信息可靠的机制传输路由协议信息- -类似于链路状态算法。类似于链路状态算法。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术表：一些路由算法的性能比较距离向量距离向量高级距离向量高级距离向量 链路状态链路状态路径向量路径向量RIP,
32、IGRPEIGRPOSPFBGP可延展性低高良好优良带宽使用高低低低内存使用低适中高高CPU使用低低高适中收敛低快快适中现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.3 路由协议n互联网为不同的自治域；n每一个自治域内采用同样的管理策略；n路由协议分为：自治域内（RIP、OSPF、IS-IS、IGRP、EIGRP）和自治域间(BGP)的路由协议.n常用的协议：常用的协议：n开放最短路径优先(OSPF)协议n边界网关协议(BGP)现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 高速路
33、由器技术在高速互联网中，由于光传输技术的发展，实验室中线路传输能力已经达到上百Gbps，实际应用中在10 Gbps、40 Gbps。链路中的处理节点成为制约网络传输速度的瓶颈。高速路由器成为构造高速网络的核心。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术路由器由多个网卡和网络连接，由处理器、缓冲模块、路由器由多个网卡和网络连接，由处理器、缓冲模块、内部互连单元（交换结构）等基本的部分构成。内部互连单元（交换结构）等基本的部分构成。路由器的基本功能包括：路由器的基本功能包括：（1 1）路由处理）路由处理（2 2）数据分组转发）数据分组转发（3
34、 3）其他服务。）其他服务。3.4 高速路由器技术 3.4.1 路由器的基本结构和功能现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 高速路由器技术 3.4.1 路由器的基本结构和功能（1 1）路由处理）路由处理通过路由协议（通过路由协议（RIP,OSPF,BGPRIP,OSPF,BGP）等交换路由信息；）等交换路由信息；计算达到各个网络的路由；计算达到各个网络的路由；创建和维护路由表；创建和维护路由表；向相邻节点发布路由信息；向相邻节点发布路由信息；也可通过人工的方式管理和修改路由表（如设置静态路也可通过人工的方式管理和修改路由表（如
35、设置静态路由、缺省路由、添加或者删除路由等）。由、缺省路由、添加或者删除路由等）。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 高速路由器技术 3.4.1 路由器的基本结构和功能（2 2）数据分组转发）数据分组转发（3 3）其他服务）其他服务 加密、认证、访问控制、路由过滤、加密、认证、访问控制、路由过滤、SNMPSNMP节点等功能。节点等功能。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.2 3.4.2 加速路由表查找的算法加速
36、路由表查找的算法路由表查找是路由器分组转发功能中的重要步骤，也是提高路由器分组转发速度的瓶颈之一。由于采用CIDR技术，路由表查找采用“最长匹配”原则。现在主干网络路由表的路由超过11万条，路由器的端口速度达到OC-192（10Gbps）。因此，需要采用新的路由表查找算法和系统结构来实现高速查找。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.2 3.4.2 加速路由表查找的算法加速路由表查找的算法（1）基于软件的查找算法衡量查找算法通常需要考虑3个方面的问题：u 路由表查找速度u 路由表所
37、需存储空间的大小u 路由表插入/删除的难易程度（2）基于硬件的查找方法加大内存，用空间换时间；基于硬件的专业集成电路（ASIC）进行路由识别、计算和转发的新型路由器，其速度很快，就像通过传输线一样，被称为线速路由器和线速路由交换机。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.2 3.4.2 加速路由表查找的算法加速路由表查找的算法特点：（1 1）基于软件的查找算法）基于软件的查找算法 优点是灵活，但是速度慢，还依赖算法。优点是灵活，但是速度慢，还依赖算法。（2 2）基于硬件的查找方法）基
38、于硬件的查找方法 能提高速度，但是灵活性收到限制。能提高速度，但是灵活性收到限制。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.3 IP3.4.3 IP路由器的体系结构路由器的体系结构第一代路由器：单处理器共享总线式体系结构第一代路由器：单处理器共享总线式体系结构CPU内存网卡网卡网卡u 处理负担重；处理负担重；u 可扩展性较差，不适合于高速传输网络。可扩展性较差，不适合于高速传输网络。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4
39、 3.4 高速路由器技术高速路由器技术 3.4.3 IP3.4.3 IP路由器的体系结构路由器的体系结构第二代路由器：多处理器共享总线式体系结构第二代路由器：多处理器共享总线式体系结构 在每个网络接口卡上具有本地处理器和缓存。在每个网络接口卡上具有本地处理器和缓存。主CPU主内存缓存从处理器网卡缓存从处理器网卡缓存从处理器网卡现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.3 IP3.4.3 IP路由器的体系结构路由器的体系结构第二代路由器：多处理器共享总线式体系结构第二代路由器：多处理器共
40、享总线式体系结构 u 解决了第一代路由器解决了第一代路由器CPUCPU负担过重的问题；负担过重的问题；u 总线结构造成速度瓶颈；总线结构造成速度瓶颈；u 这种路由器不能运用到主干网。这种路由器不能运用到主干网。（主干网数据不具有局域（主干网数据不具有局域性，同时发生的数据流可以达到上百万个，对缓存的管理和维护带性，同时发生的数据流可以达到上百万个，对缓存的管理和维护带来很大困难；并且数据流的迅速变化，需要频繁调用主处理器，来很大困难；并且数据流的迅速变化，需要频繁调用主处理器，分分布式和缓存对提高效率的作用就不明显布式和缓存对提高效率的作用就不明显！）！）现代骨干网与高速互联网技术 邬春学 2
41、022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.3 IP3.4.3 IP路由器的体系结构路由器的体系结构第三代路由器：多处理器交换式体系结构第三代路由器：多处理器交换式体系结构 主CPU主内存从处理器网卡缓存从处理器网卡缓存从处理器网卡缓存交换交换结构结构现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.3 IP3.4.3 IP路由器的体系结构路由器的体系结构第三代路由器：多处理器交换式体系结构第三代路由器：多处理器交换式体系结
42、构 u 采取多处理器交换式体系结构，在接口之间传送数据采取多处理器交换式体系结构，在接口之间传送数据分组的带宽大大提高，能适应吉比特每秒的传输速率；分组的带宽大大提高，能适应吉比特每秒的传输速率；u 第三代路由器的瓶颈在于主处理器和主内存组成的转第三代路由器的瓶颈在于主处理器和主内存组成的转发引擎部分。在大量数据流存在的时候，主处理器成为发引擎部分。在大量数据流存在的时候，主处理器成为整个路由器性能提高的瓶颈。整个路由器性能提高的瓶颈。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.3 IP
43、3.4.3 IP路由器的体系结构路由器的体系结构第四代路由器：多转发引擎共享并行处理器交换式体系结构第四代路由器：多转发引擎共享并行处理器交换式体系结构 路由处理器网卡交换结构交换结构网卡网卡转发引擎转发引擎转发引擎现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.4 3.4.4 路由器的交换结构路由器的交换结构交换结构交换结构是指路由器内部各个模块之间进行数据交换的是指路由器内部各个模块之间进行数据交换的结构，特别是将数据分组从输入接口发送到输出接口的结构。结构，特别是将数据分组从输入接口发
44、送到输出接口的结构。u 交换结构是实现高速交换结构是实现高速IPIP路由器中的关键组件，是解决路由器中的关键组件，是解决高速分组转发的主要方式。高速分组转发的主要方式。u 交换结构的性能直接影响到路由器的整体性能交换结构的性能直接影响到路由器的整体性能u 交换结构实现方式可以分为三种交换结构实现方式可以分为三种: : 共享总线、共享内存和交叉开关阵列共享总线、共享内存和交叉开关阵列现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.4 3.4.4 路由器的交换结构路由器的交换结构共享总线结构：共
45、享总线结构：出现在早期的路由器中出现在早期的路由器中u CPUCPU内存和接口卡之间交换数据都要通过总线传输。内存和接口卡之间交换数据都要通过总线传输。u 可能发生多个模块同时访问总线的情况，需要采取一定可能发生多个模块同时访问总线的情况，需要采取一定的仲裁机制才能防止共享冲突。的仲裁机制才能防止共享冲突。u 共享总线易于扩展，也比较容易实现，但是速率相对较共享总线易于扩展，也比较容易实现，但是速率相对较低。低。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.4 3.4.4 路由器的交换结构
46、路由器的交换结构共享内存结构：共享内存结构：来自各个网络接口的数据分组将写入双向随即访问存储来自各个网络接口的数据分组将写入双向随即访问存储器中，数据分组头上加内部路由标记。器中，数据分组头上加内部路由标记。内存控制器通过读取数据分组头的标记来决定各个分组内存控制器通过读取数据分组头的标记来决定各个分组的读出顺序，包括优先级的处理。的读出顺序，包括优先级的处理。共享内存方式可以使各个接口共享输出能够吸收某个接共享内存方式可以使各个接口共享输出能够吸收某个接口的突发特性，实现各个接口相同的转发性能。口的突发特性，实现各个接口相同的转发性能。现代骨干网与高速互联网技术 邬春学 2022年4月22日
47、第第3 3部分部分 骨干网络路由与交换技术3.3 3.3 高速路由器技术高速路由器技术 3.4.4 3.4.4 路由器的交换结构路由器的交换结构共享内存结构：共享内存结构：缺点：缺点：要求共享内存和内存控制速度是各个接口速度的总和，要求共享内存和内存控制速度是各个接口速度的总和，才能达到各个接口能充分利用传输能力。才能达到各个接口能充分利用传输能力。共享方式实现简单、也可以达到比较高的速度。在配置共享方式实现简单、也可以达到比较高的速度。在配置8 8块块OC-48OC-48接口卡时，可以达接口卡时，可以达40 Gbps40 Gbps吞吐率。吞吐率。但是共享内存速率的进一步提高将受到内存速度的限
48、制，但是共享内存速率的进一步提高将受到内存速度的限制，很难有更大的突破。很难有更大的突破。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.4 3.4.4 路由器的交换结构路由器的交换结构交叉开关阵列结构：交叉开关阵列结构：现在越来越成为高速路由器的实现方式。现在越来越成为高速路由器的实现方式。可以实现接口到接口的直连通路，交换结构的带宽可以实现接口到接口的直连通路，交换结构的带宽与接口带宽相同即可，并且规模扩展性好，能够增加整与接口带宽相同即可，并且规模扩展性好，能够增加整个交换结构的规模。
49、个交换结构的规模。随着技术的发展，交换速率还可以进一步提高。随着技术的发展，交换速率还可以进一步提高。现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术路由处理器网卡交换结构交换结构网卡网卡转发引擎转发引擎转发引擎3.4 3.4 高速路由器技术高速路由器技术 3.4.4 3.4.4 路由器的交换结构路由器的交换结构交叉开关阵列结构：交叉开关阵列结构：现代骨干网与高速互联网技术 邬春学 2022年4月22日第第3 3部分部分 骨干网络路由与交换技术3.4 3.4 高速路由器技术高速路由器技术 3.4.4 3.4.4 路由器的交换结构路由器的交换结构
50、交叉开关阵列结构：交叉开关阵列结构：开关阵列需要解决的关键问题之一是阻塞问题，包括：开关阵列需要解决的关键问题之一是阻塞问题，包括： 线路头部阻塞、输入阻塞和输出阻塞。线路头部阻塞、输入阻塞和输出阻塞。开关阵列另外一个重要问题是队列调度。开关阵列另外一个重要问题是队列调度。为了支持不同的服务类型，路由器对对分组进行分类，为了支持不同的服务类型，路由器对对分组进行分类，放入不同的队列中。放入不同的队列中。在输出分组时，需要进行选择输出哪一个队列的分组，在输出分组时，需要进行选择输出哪一个队列的分组，这就是路由器的队列调度。这就是路由器的队列调度。现代骨干网与高速互联网技术 邬春学 2022年4月
