路由过程详解

1. 数据包从二层交换到三层路由流程

  

(1)源主机在发起通信之前,将自己的IP地址与目的主机的IP地址进行比较,如果源主机判断目的主机与自己位于不同网段时,它需要通过网关来递交报文的,所以它首先需要通过一个ARP请求报文获取网关的MAC地址(在源主机不知道网关MAC地址的情形下),即源主机先发送ARP请求帧以获取网关IP地址对应的MAC地址。

  (2)网关在收到源主机发来的ARP请求报文后以一个ARP应答报文进行回应,在应答报文中的“源MAC地址”就包含了网关的MAC地址。
  (3)在得到网关的ARP应答后,源主机再用网关MAC地址作为报文的“目的MAC地址”,以源主机的IP地址作为报文的“源IP地址”,以目的主机的IP地址作为“目的IP地址”,先把发送给目的主机的数据发给网关。
  (4)网关在收到源主机发送给目的主机的数据后,由于查看得知源主机和目的主机的IP地址不在同一网段,于是把数据报上传到三层交换引擎(ASIC芯片),在里面查看有无目的主机的三层转发表。
  (5)如果在三层硬件转发表中没有找到目的主机的对应表项,则向CPU请求查看软件路由表,如果有目的主机所在网段的路由表项,则还需要得到目的主机的MAC地址,因为数据包在链路层是要经过帧封装的。于是三层交换机CPU向目的主机所在网段发送一个ARP广播请求包,以获得目的主机MAC地址。
  (6)交换机获得目的主机MAC地址后,向ARP表中添加对应的表项,并转发由源主机到达目的主机的灵气包。同时三层交换机三层引擎会结合路由表生成目的主机的三层硬件转发表。

   以后到达目的主机的数据包就可以直接利用三层硬件转发表中的转发表项进行数据交换,不用再查看CPU中的路由表了。


2. 路由表

  

路由器在接收到数据时,要对其传输路径进行选择。为了实现这一目标,路由器需要维护一个称为“路由表”的数据结构。路由表包含若干条目,供路由器选路时查询数据传输路径。路由表中的一个条目至少要包含:

  1. 数据的目的地址(通常是目的主机所在网络的地址)。
  2. 下一跳路由器(即从本路由器出发按所给路径到给定目的地所要通过的下一个路由器)的地址。
  3. 相应的网络接口。
  4. 一般情况下还应该有标志位等内容。

  由于Internet规模太大,分布范围太广,所以路由表中对应每一个目的网络都有一个条目是不可能的;同样,也不可能采用一个全局的路由算法或协议。因此,Internet将整个网络划分为若干个相对自治的局部系统,即自治系统。自治系统可以定义为同一机构下管理的路由器和网络的集合。一个自治系统内部还可以再划分几个小的路由域,也称作区域。


3. 路由协议

  

根据功能不同路由协议可以分为内部网关协议(IGP,Interior Gateway Protocol)和外部网关协议(EGP,Exterior Gateway Protocol)两大类。内部网关协议是用于自治系统内部的动态路由协议:如RIP和OSPF。外部网关协议是用于自治系统之间拓扑信息交换的路由协议:如BGP。

  根据算法不同路由协议可分为距离矢量路由选择协议和链路状态路由选择协议
  距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器周期地和相邻路由器交换路由表中的信息。这种信息是由若干(V,D)对组成的表项,其中,V代表矢量,指出该路由器可以达到的目的地;D表示去往目标V的距离。各个路由器根据收到的信息重新计算到各目的节点的距离,对自己的路由表进行修正。
  链路状态路由选择协议也被称为最短路径优先协议,它基于链路状态路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓扑结构的无向图G(V,E),在图G中,节点V表示路由器,边E表示连接路由器的链路,因此G又可以称为L-S(链路-状态)图,各路由器的路由表通过L-S图计算。
  链路状态路由算法的基本步骤如下:
  (1)每一个路由器(节点)启动后,首先执行对相邻节点的发现工作,并获取它们的地址。
  (2)各路由器主动测试到每一个相邻路由器的链路时延或成本,并根据测试结果设置相关链路的状态。
  (3)各路由器构造自己的L-S(Link-State,链路状态)信息包,L-S信息的内容包括本路由器的标号、本路由器的邻居路由器列表、本路由器到各邻居路由器的链路状态(时延或成本)、该L-S信息包的序号和生存时间等。
  (4)各路由器向所有参与链路状态交互的路由器广播其L-S信息,可以是周期性地发送,也可在链路状态发生变化时发送。
  (5)每个路由器在收到所有的L-S信息后,可以构造或更新表示整个网络拓扑结构的图G(V,E),顶点V表示路由器,边E表示连接路由器的链路;这时路由器就可以用Dijkstra算法从图G中计算出到所有目的路由器的最短路径,也就是构造以自己为根节点的SPF树。
  链路状态路由协议OSPF用到的算法为Dijkstra, 主要原理如下:
  设目的节点(就构造SPF树而言,是根节点)为k,任一条链路(i,j)的长度为dij,每个节点到k的最短路径长度估计为Dik;定义所有节点的集合为A,定义集合P∈A,并设定集合的初始值为P={k}。
  在算法迭代的过程中,如果Dik已经变成一个确定值,则将i标记为固定点,并将其加入集合P。在算法的每一步迭代中,在P以外的节点中,选择与目的节点k最近的节点加入到P中。

路由过程详解

上一篇:APP防CC为什么复杂


下一篇:HDU 1242 Rescue (优先队列 + 广搜)