• 原创美文
  • 经典文章
  • 情感美文
  • 伤感文章
  • 散文
  • 美文随笔
  • 感人文章
  • 人生哲理
  • 学生美文
  • 民族文化
  • 说说大全
  • 网名大全
  • 范文大全
  • 当前位置: 佩佩美文网 > 情感美文 > 正文

    路由器算法的基本工作原理 [路由器工作原理]

    时间:2019-10-16 08:29:34来源:佩佩美文网 本文已影响 佩佩美文网手机站
    -->

    1.1 路由器工作原理

    1.1.1 概述

    路由器的主要作用是转发数据包,将每一个IP数据包由一个端口转发到另一个端口。转发行为既可以由硬件完成,也可以由软件完成,显然硬件转发的速度要快于软件转发的速度,无论那种转发都根据“转发表”或“路由表”来进行,该表指明了到某一目的地址的数据包将从路由器的某个端口发送出去,并且指定了下一个接收路由器的地址。每一个IP数据包都携带一个目的IP地址,沿途的各个路由器根据该地址到表中寻找对应的路由,如果没有合适的路由,路由器将丢弃该数据包,并向发送改包的主机送一个通知,表明要去的目的地址“不可达”。

    路由表如何形成是路由器软件系统的核心内容,动态路由协议就是用来收集路由信息,为路由表的创建提供原始素材。简单来讲,当路由器加电后经过人工适当配置后,如指定端口IP地址等,路由器已经能够识别它的各个接口卡上的所有已经启动并且经过配置的端口所连接的网络,路由器就有了最初的路由表,这时各个端口所连的网络就可以互通了。如何将最初的路由表告知其他路由器,这就是动态路由协议的任务了。路由器将自身的路由信息通过路由协议所规定的数据格式发送出去,接收到该信息的路由器如果也运行了相同的路由协议,就可以将改信息加以保存,根据规则对收到的信息加工处理,这样它的路由表得到扩充与丰富,再将变化后的路由表发送给其他路由器,经过一段时间,所有的路由器都得到了关于整个网络的路由信息,该过程也称为路由收敛。当网络拓扑结构发生变化时,路由信息要重新进行收敛。

    动态路由协议有许多种,它们的适用范围与特性各不相同,ZXR10支持常用的几种路由协议:路由信息协议(RIP v2)、开放最短路径优先(OSPF v2)、边界网关协议(BGP v4)。这几种路由协议同时运行时,各自收集到路由信息按照优先权顺序安装到路由表中,只有优先权最高的路由信息起到转发作用,其他的做为备份,当最高优先权的路由信息失效时,次优先权的路由信息得以启用。

    为进一步理解路由器的工作原理,需要了解TCP/IP协议栈的背景知识,以下几节对此作简要介绍。

    1.1.2 网络模型与协议

    TCP/IP协议栈是一组不同层次上的多个协议的组合。通常,TCP/IP被认为是一个四层协议的体系结构,它是国际标准化组织(ISO)的开放系统互联(OSI)七层参考模型的简化,两者的结构图2-3所示:

    图2-3 网络模型

    每一层的功能如下:

    1) 应用层:负责处理各种应用程序的细节,常见的通用的应用程序有:

     Telnet 远程登录

     FTP 文件传输协议

     SMTP 简单邮件传送协议

     SNMP 简单网络管理协议

    2) 传输层:为两台主机上的程序提供端到端的通信,该层有两种协议:TCP(传输控制协议)和UDP(用

    户数据报协议)。TCP为两台主机提供高可靠性的通信连接,有着复杂的控制机制。UDP是比较简单的协议,不保证数据包的可靠传输,任何必须的可靠性必须由上层程序来提供。两个传输协议将应用程序的数据加上自身格式的首部字段后交给下一层进行处理。UDP首部各字段如图2-4所示:

    图2-4 UDP首部 TCP首部各字段如图2-5所示:

    图2-4 TCP首部

    一台主机可以运行多个应用程序,那么有多个TCP和UDP连接同时存在,这里源端口号在

    区分各个连接时起到了作用,一般而言,源端口号是随机分配的,目的端口号是通过知名端口来识别的,这样服务器接收到该数据包时根据数据包中的目的端口号就可以知道对应的服务类型,如FTP服务器的TCP端口号为21,Telnet服务器的TCP端口号为23,TFTP(简单文件传输协议)服务器的端口号为69,RIP路由信息协议的UDP端口号为520。详尽的知名端口号的分配可参考RFC1700文件。

    TCP连接是并发进行的,应用程序通过TCB传输控制块来对应进程的,TCB是由源、目的

    端口和源、目的主机IP地址这四个参数组成的,具有唯一性。而UDP连接是单进程进行的,多个连接需排队顺序处理,也用源、目的IP地址和端口来标识各个连接。

    3) 网络层:有时也称为互联网层,处理分组数据在网络中的活动,如路由选择等。由于该层应用了

    包含逻辑地址的IP数据包来传输数据,完全独立于底层的各种各样的硬件类型和技术,使得应用TCP/IP协议栈的网络完全实现互联互通,最终形成了规模庞大的遍布全球的因特网。但该层提供的是不可靠的服务,只是尽最大努力将分组数据从源端传送到目的端,可靠性完全由上层协议来保证。该层协议包括IP协议(网际协议)、ICMP协议(网际控制报文协议)、IGMP(网际组管理协议)。其中IP数据包的首部格式如图2-5所示:

    图2-5 IP首部 这里的协议标识可用来区分封装在IP包中的其它协议类型,如协议标识为6表示封装的是TCP数据包,协议标识为17表示封装的是UDP数据包,协议标识为89表示封装的是OSPF数据包,协议标识为1表示封装的是ICMP数据包,协议标识为2表示封装的是IGMP数据包。

    TTL(time-to-live)生存时间字段设置了数据包可以经过的最多路由器数,目的是防止数据包在网络上的无限循环。该值由源主机设置(通常为32或64),一旦经过一个路由器,路由器就将它减1,当某路由器检查该值为1且目的地址不在本路由器直联的网络上时,该数据包就被丢弃,并发送ICMP报文通知源主机。当TTL值改变后,首部检验和也要改变。一般路由器在转发IP数据包时,仅仅改变这两个字段。

    首部检验和的计算过程是:先将该字段置为0,然后对首部中每个16bit进行二进制反码求和,将结果存在检验和字段中。当路由器收到一份IP数据包后,同样对首部中每个16比特进行二进制反码求和,如果结果为FF才表示IP数据包正确。出错的数据包将被丢弃,但不发送ICMP报文,上层协议可以检测到出错并对该数据包重传。

    首部长度指的是首部占32比特(双字)的数目,包括任选项。普通IP数据包是没有选择项的,因此该字段的值为5。路由器收到IP包后对此字段要做检查,带选项的IP数据包在转发前要做特殊处理。

    版本字段为4,这表示这种IP首部格式是IPV4的格式,IPV4是当前Internet所使用的IP版本,其实也是第一个版本,下一代的版本为IPV6。

    4) 链路层:也称为数据链路层或网络接口层,通常包括操作系统中的设备驱动程序和网络接口硬件。该

    层将IP数据包按照链路协议定义的格式进行封装,并按照硬件接口的编码方式形成合适的基带信号发送到传输介质上。如常见的以太网(Ethernet II)协议的封装格式为:

    两字节的协议类型字段区分了封装的协议类型:0800表示封装的是IP数据包,0806表示封装的是ARP地址解析协议数据包。封装好的数据帧协议在线路空闲时(用CSMA/CD载波侦听多路存取/碰撞检测的方法来检测)按照曼彻斯特编码将数据变成电平发送到线路上。

    线速路由器中常用的另一种链路层协议为PPP点到点协议,IP数据包被封装成PPP数据帧,PPP数据帧再映射进同步数字序列SDH中去透明传输,路由器上这样的接口常称为POS接口(Packer over SDH)。PPP帧格式为:

    协议字段为0021时表示数据部分为IP数据包,C021表示数据部分为LCP链路控制协议,8021为NCP网络控制协议,C023为PAP密码验证,C223为CHAP质询握手验证协议。详细信息可参考RFC1661RFC、RFC1662文档。

    1.1.3 IP编址和路由选择

    地址有网络层地址和链路层地址,它们的作用各不相同。整个网络中的寻址是根据网络层的地址进行的,因为网络层地址有不依赖于硬件的独立性,有利于统一规划与编排,它的“分层”设计将地址分为网络部分与主机部分,这更加有利于路由的构建和选择。传输链路上数据包的识别是根据链路层地址进行的,链路层的地址编排依赖于传输链路的技术本身,不同的链路协议采用不同的编址方式,如以太网的链路层地址为48位编码的唯一地址,PPP链路层地址用统一的FF表示,帧中继网络的链路层地址用连接标识符DLCI表示,ATM网络用PVC永久虚电路、SVC交换虚电路来标识。

    IP协议栈中的网络层地址就是指常见的IP地址,分为A、B、C、D、E五类,常用的为前三类,D类地址为网络组播地址,E类地址保留。IP地址有两部分组成,一部分为网络号,一部分为主机号,两者的确定是由子网掩码来决定的。子网掩码与IP地址一样也是32bit长度,并且两者是一一对应的,子网掩码中数字为“1”所对应的IP地址中的部分为网络号,为“0”所对应的部分为主机号。子网掩码中数字“1”和“0”都是连续的,不允许间插,且数字“1”在前,数字“0”在后。常规IP地址分类结构如下:

    这种地址划分方法的初衷是为路由协议的设计提供便利,只从IP地址的首部特征位就可以判定子网掩码了。随着互联网的急剧膨胀,地址短缺的问题愈来愈突出,因为这种分类方法使得地址空间无法得到最大限度的利用。目前出现的无类域间路由(CIDR)技术淡化了IP地址的类的概念,多种路由协议在路由条目更新中都带有子网掩码,无需利用IP地址的首部特征位去判定子网掩码了,这在一定程度上缓解了目前IP地址短缺的问题,但最终的解决方案是应用下一代的IPV6编址方法,其地址长度为128位。关于IP地址的规定:

    1) 0.0.0.0 用于没有IP地址的主机启动时使用,通过RARP、BOOTTP、DHCP来获得地址。

    在路由表中该地址还用作缺省路由。

    2) 255.255.255.255 用于广播的目的地址,不能作源地址。

    3) 127.X.X.X 称为环回地址,即使不知道主机的实际IP地址,也可用该地址代表“本机”。

    4) 仅主机部分全1表示广播到特定的网络。

    5) 合法的主机IP地址其网络部分或主机部分都不能全0或全1。

    主机通信只能在具有相同网络号的IP地址之间进行,不同网络号的主机之间的通信必须经过路由器进行转发,这是包含IP协议栈的各类操作系统所共同遵守的。路由器的多个端口连接到多个IP网络上,一般而言,不同的端口对应不同的IP子网,每个端口的IP地址的网络号必须与所连接的IP子网的网络号相同。

    当应用程序需要与其它主机连接时,操作系统判断目的主机的IP地址是否与本主机在同一个子网上,如果在同一子网上则寻找目的主机的MAC地址,然后封装成链路层帧格式发送出去。如果不在同一子网上且配置了缺省网关,系统将数据转发给与之相连的路由器上。路由器收到数据包后将检测数据包的目的

    地址,并用它与路由表中条目进行“最长匹配”。如果匹配成功,则路由器将数据包从与目的地址匹配的本地接口转发出去。如果在路由表中没有目的地址的入口,并且也没有缺省路由,那么数据包将被丢失。

    可见,路由查找的过程就是“最长匹配”的过程,如何实现该过程完全由路由表的数据结构决定。直观上来讲,理解了子网划分的技术,可以“看出”哪个表项是“最长匹配”。举例来讲,路由表有这样几个目的网络(斜杠后的数字为子网掩码长度):192.24.96.64/27,192.24.96.96/27,192.24.96.128/26,192.24.96.192/27,192.24.96.224/28,192.24.96.240/28,那么到IP地址为192.24.96.163主机的路由将选中192.24.96.128/26这一表项。其实,该网络地址的主机范围为192.24.96.129~192.24.96.190,唯一包含了目的主机的IP地址。但是,路由查找软件是没有这样的“判断”的,假设路由表中没有192.24.96.128/26这一项,软件查找的结果就是192.24.96.192/27为最长匹配了,显然这是错误的,因为该网络地址的主机范围为192.24.96.193~192.24.96.222,不包括192.24.96.163。

    1.1.4 路由表的建立、维护、构成

    路由表由静态路由表项和动态路由表项组成,静态路由入口由网络管理者手工配置的静态路由组成,动态路由入口由路由协议如RIP、OSPF、BGP交换的路由表信息组成。

    一般而言,在同一个路由域中所有路由器的各个路由协议都有一个“收敛”(convergence)状态或过程。当所有路由器达到一个稳定、准确、一致的网络拓扑状态时,就会获得“收敛”状态。也许该状态是短暂的,网络拓扑的变化会使路由器重新进行“收敛”。路由器如何获得收敛状态是由它们的配置和路由协议所绝定的。

    RIP只维护一张表:路由表,它们定期与相邻路由器交换全部路由表,如果一个路由被宣布为不可达,则该路由被标记为“possible down”,并被置为抑制状态。过一定时间若仍未从原来的源端重新学习,该路由将被清除。

    OSPF、BGP除了维护一张路由表外,还维护另外的两张表:相邻路由器表和拓扑表或路径表。相邻路由器通过HELLO数据包来建立和维护相邻路由器表。一旦正确建立了邻居关系后,彼此交换路由表信息,此过程建立了拓扑数据库。根据拓扑数据库,OSPF实现最短路径优先算法,并将结果放在主路由表中。

    理解路由表的各个构成项的功能对了解路由器的路由过程非常重要。一般路由表有以下七项:

    路由信息的起源

    目的地址

    管理距离

    度量值

    下一跳

    计时

    本地接口

    1.1.5 路由器的组成结构

    路由器主要由以下几个部分组成:输入/输出接口部分、包转发或交换结构部分(switching fablic)、路由计算或处理部分。

    输入/输出部分实现数据链路层的封装和解封装,并按一定的路由查询算法,根据输入数据包的目的IP地址查找到转发的输出端口,该功能可用专用集成电路(ASIC)实现纯硬件查找和数据包的拆包与打包处理,也可以由专用的网络处理器实现微码转发。普通路由器中该部分的功能完全由路由器的中央处理器来执行,制约了数据包的转发速率(每秒几千到几万个数据包)。高端路由器中普遍实现了分布式硬件处理,接口部分有强大的CPU处理器和大容量的高速缓存,使接口数据速率达到10Gbps,满足了高速骨干网络的传输要求。

    路由器的转发机制对路由器的性能影响很大,常见的转发方式有:进程转发、快速转发、优化转发、分布式快速转发。进程转发将数据包从接口缓存拷贝到处理器的缓存中进行处理,先查看路由表再查看ARP表,重新封装数据包后将数据包拷贝到接口缓存中准备传送出去,两次查表和拷贝数据极大的占用CPU的处理时间,所以这是最慢的交换方式,只在低档路由器中使用。快速交换将两次查表的结果作了缓存,也无需拷贝数据,所以CPU的处理数据包的时间缩短了。优化交换在快速交换的基础上略作改进,将缓存表的数据结构作了改变,用深度为4的256叉树代替了深度为32的2叉数或哈希表(hash),CPU的查找时间进一步缩短。这两种转发方式在中高档路由器中普遍加以应用。在骨干路由器中由于路由表条目的成倍增加,路由表或ARP表的任何变化都会引起大部分路由缓冲失效,以前的交换方式都不再适用,最新的交换方式是分布式快速交换,它在每个接口处理板上构建一个镜像(mirror)路由表和MAC地址表相结合的转发表,这仍是深度为4的256叉表,但每个节点的数据部分是指向另一个称为邻接表的指针,这种结构使得转发表完全由路由表和ARP表来同步更新,本身也不再需要一个老化进程,克服了其它交换方式需要不断对缓存表进行老化的缺陷。

    交换结构最常见的有总线型、共享内存型、Cross-bar。总线型结构最简单,但在调度共享数据传输通道上必须花费一定的开销,而且总线带宽制约了交换容量的扩张,在中档路由器用使用这种结构。共享内存结构中,用存储器来缓冲数据包,数据的交换是通过指针调用实现的,它受限于内存的访问速度和存储器的管理效率,在早期的中低档路由器中普遍应用。Cross-bar结构相当于多条并行工作的总线,对流经它的数据不断进行开关切换,可见开关速度决定了交换容量,随着各种高速器件的不断涌现,这种结构的交换容量普遍达到几十Gbps以上,成为目前高端路由器和交换机的首选交换结构。

    路由处理部分主要是运行动态路由协议。接收和发送路由信息,计算出路由表,为数据包的转发提供依据。各种档次的路由器的路由表条目的大小存在很大差异,从几千条到几百万条不等,因此高端路由器的路由表的构造对路由查找速度影响很大,其路由表的数据结构常采用二叉数的形式,查找与更新的速度都比较快。

    一般而言,路由器对一个数据包的交换要经过一系列的复杂处理,主要有以下几个方面:

     压缩和解压缩

     加密和解密

     用输入/输出访问列表进行报文过滤

     输入速率限制

     进行网络地址翻译(NAT)

     处理影响本报文的任何策略路由

     应用防火墙特性对包进行检查

     处理Web页缓冲的重定向

     物理广播处理,如帮助性地址(ip help address)

     单播反向路径检查(unicast reverse path checking)

     利用启用的QoS机制对数据包排队

     TTL值的处理

     处理IP头部中的任选项

     检查数据包的完整性

    1.1.6 路由器的软件体系

    路由器是在软件控制下进行工作的,与普通操作系统相比,其软件系统比较简洁、全部驻留在存储器且受限于原始平台的一种操作系统。在商用实时操作系统的内核基础上开发一个包含TCP/IP协议栈的接口平台,辅以各种功能模块,形成完整的软件系统。为最大限度地增加路由器快速交换报文的能力,该操作系统被设计为具有最小的操作性开销,同时允许CPU使用最大的带宽进行报文交换。其体系结构如图2-6所示:

    图2-6 路由器软件体系结构

    路由器的软件系统主要有五个组成部分:

     进程:执行特定任务的独立线程和相关的数据,如系统配置维护的telnet守护进程、客户端进程,ftp

    进程、TFTP进程,SNMP进程,各种协议进程:IP、TCP、UDP、RIP、OSPF、BGP、ARP、ICMP、IGMP,其它有加解密进程、报文过滤进程、NAT进程等。

     内核:为系统的其它部分提供基本的系统服务,如存储器管理、进程调度、定时器和时钟管理。它为

    进程提供了硬件(CPU和存储器)资源的管理。

     报文缓冲:用来存放将要被交换的报文。

     设备驱动程序:控制网络接口硬件设备及其它外围设备(如Flash)。设备驱动程序接口位于进程、内

    核、硬件之间,同时与交换控制软件有接口。

     交换控制软件:根据转发方式控制报文的交换,在高端线速路由器中该部分功能由硬件实现。

    • 路由器算法的基本工作原理 [路由器工作原理] 相关文章: