(一)概述
     路由算法是用于获取路由表中的路由项目。它是路由选择协议的核心。

为了说明路由表的组成,先看一个主机路由表:

   1: 内核 IP 路由表
   2: Destination     Gateway         Genmask         Flags   MSS Window  irtt Iface
   3: 10.0.2.0        *               255.255.255.0   U         0 0          0 eth0
   4: link-local      *               255.255.0.0     U         0 0          0 eth0
   5: default         10.0.2.2        0.0.0.0         UG        0 0          0 eth0

对路由表的说明
(1)Destination:目的IP地址或网络地址;
(2)Gateway:即下一站路由器,*表示无须经过下一站路由器就可以直接到达目的地址或目的网络;
(3)Genmask:子网掩码;
(4)Flags:标志字段,这里可能出现U,G,H,D,M,R等,U表示可用;G表示Gateway字段是个路由器,否则表示是个直接出口;H表示Destination是个主机IP地址,没有H表示Destination是网络地址;D表示该路由项由ICMP重定向报文创建;M表示该路由项由ICMP报文修改而来;R表示由动态选路协议恢复的路由项。
多数系统内核对路由表的实现都包含上述内容,其它字段视系统而定。
 
查看路由表的方法:
(1)netstat –r
(2)route
(3)查看相关文件:/proc/net/route

(二)路由算法的分类和选路过程
     从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来分,可以分为两类。
  • 静态路由选择策略
    • 静态路由选择也叫非自适应路由选择,其特点是简单和开销较小,但不能适应网络变化
  • 动态路由选择策略
    • 动态路由选择也叫自适应路由选择,特点是能适应网络变化,实现起来复杂,开销也比较大。

IP路由选择过程

      IP的路由处理是一个相当简单并没有多少变化的过程,它与网络的大小无关。这个过程非常重要,以终端A通过一个路由器访问外网的终端B为例,描述一下IP路由选择过程:

因特网控制报文协议(lCMP)创建一个回应请求数据包

——>> ICMP将此包转交给IP 

——>>IP协议判断目的IP地址是处在本地网络中,还是处在一个远程网络上

——>> 这是一个远程请求,这个数据包需要被发送到默认网关(这也就是为什么要在终端上配置网关)

——>>根据ARP缓存中的网关MAC地址,将数据进行帧(Frame)的封装(此时数据已经从网络层到数据链路层)

——>> 帧到物理层位(Bit)的形式传输

——>>传输完成,校验数据,并向上解包,直到网络层

——>>  在路由表中检查其IP目的地址

——>> 此路由表中必须包含有目的地址网络,否则将丢弃数据,并返回"destination network unavailable"的ICMP信息,并被发送回原设备

——>> 数据包被交换到输出接口的缓存区

——>>检查ARP缓存是否有目的地址,如果没有,则向目的主机发出ARP请求,取得地址

——>>根据网关MAC地址,将数据进行帧(Frame)的封装 

——>> 帧到物理层位(Bit)的形式传输

——>> 传输完成,校验数据,并向上解包,直到网络层

——>>  核对IP,正确后交付给ICMP,ICMP会丢弃这个数据包,产生一个新负荷来作为回应应答

——>>创建应答,添加源方和目的方的地址、协议字段和有效负荷,此时目的方设备为主机A。然后就是经历一个相反的过程,将应答返回终端A。

    有一点需要提示一下,当数据包在返回源主机的途中被丢弃时,由于这是一个未知的错误,通常你将会看到“request timed out” 的信息。如果出现的错误是一个已知的错误,如假设在去往目的设各的路途中路由表内没有可用的路曲,你将会得到“destination unreachable” 的信息。根据这些信息,你可以判断问题是发生在去往目的的路上,还是在返回的途中。在这里要理解的关键问题是,即使对于一个非常大的网络,这个处理过程也将是同样的。在一个较大的互联网络中,数据包在找到目的主机之前,需要通过更多的路由器。

    另外,硬件地址总是保存在本地,它们决不会跨过路由器的接口。理解这个过程是至关重要的,所以要将它刻在你的记忆中! 例如:主机A将向主机B发送出一个ARP请求,路由器将如何响应这个请求?由于MAC地址必须限定于本地网络内,路由器将用连接主机A接口的MAC地址响应这个请求,于是当主机A要发送数据包时,会将所有的数据帧发往路由接口的MAC地址。


(三)自治系统
     因特网将整个互联网划分成许多较小的自治系统,一般简称为AS。自治系统有以下特点:
  • 自治系统有权决定自己的路由选择协议
  • 所有的网络都属于一个行政单位管辖
  • 所有的路由器在本自治系统内都必须是连通的
(四)路由选择协议的分类
  • 内部网关协议IGP
    • 即在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用的最多,如RIP和OSPF协议。
  • 外部网关协议EGP
    • 若源站和目的站处在不相同的自治系统中,当数据报传到一个自治系统的边界时,就需要使用外部网关协议将路由选择信息传递到另一个自治系统中。目前外部网关协议使用最多的是BGP-4.
(五)RIP路由信息协议(Routing Information Protocol)
  • 路由信息协议RIP是一种分布式的基于距离向量的路由选择协议,是因特网标准协议。
  •  RIP协议将“距离”定义如下:
    • 从一路由器到直接连接的网络的距离定义为1,从一路由器到非直接链接的网络的距离定义为所经过的路由器加1。因此,直接链接的网络的距离定义为1。
    •  RIP允许一条路径最多只能包含15个路由器。因此距离的最大值为16,相当于不可达。可见RIP只适用于小型互联网。
  • RIP的距离向量算法为(Bellman-Ford算法)(详情请谷歌or查阅算法导论)
  • RIP协议报文格式:
    • RIP协议使用运输层的用户数据报UDP进行传送。

    

    • 命令字段:1表示请求路由信息,2表示请求路由信息的响应或未被请求而发出的路由更新协议
    • 必为0字段:用来四字节对齐
    • 地址族标识符:该字段用来标识所使用的地址协议
    • 路由标记:填入自治系统的编号,这是因为考虑到有可能收到本自治系统以外的路由选择信息。
(六)内部网关协议OSPF
  • OSPF开放最短路径优先协议(OpenShortestPathFirst)用于在单一自治系统(autonomous system,AS)内决策路由。是对链路状态路由协议的一种实现。OSPF使用了Dijkstra提出的最短路径算法。
  • OSPF分组的格式

  

    • 版本:当前的版本号为2
    • 类型:可以是5种类型分组中的一种
      • 类型1:问候分组(hello),用来发现和维持邻站的可达性
      • 类型2:数据库描述分组,向邻站给出自己的链路状态数据库中的所有链路状态项目摘要信息。
      • 类型3:链路状态请求分组,向对方请求发送某些链路状态项目的详细信息
      • 类型4:链路状态更新分组,用洪泛法对全网更新链路状态
      • 类型5:链路状态确认分组,对链路状态更新分组确认。
    • 分组长度:包括OSPF首部在内的分组长度,以字节为单位
    • 路由器标识符:标志发送该分组的路由器的接口IP地址
    • 区域标识符:分组属于的区域
    • 检验和:用来检测分组中的差错。
    • 鉴别类型:0(不用),1(口令8个字符)
  • OSPF是除RIP外的另一个内部网关协议,它克服了RIP的所有限制,RFC 1247 [Moy 1991]中对第2版OSPF进行了描述;
  • 与采用距离向量的RIP协议不同的是,OSPF是一个链路状态协议:
    • 距离向量的意思是:RIP发送的报文包含一个距离向量(跳数),每个路由器都根据它所接收到邻站的这些距离向量来更新自己的路由表;
    • 在一个链路状态协议中:路由器并不与其邻站交换距离信息,它采用的是每个路由器主动地测试与其邻站相连链路的状态,将这些信息发送给它的其他邻站,而邻站将这些信息在自治系统中传播出去;每个路由器接收这些链路状态信息,并建立起完整的路由表;
    • 从实际角度来看:二者的不同点是链路状态协议总是比距离向量协议收敛更快:
      • 收敛的意思是在路由发生变化后,例如在路由器关闭或链路出故障后,可以稳定下来;
  • [ Perlman 1992]的9.3节对这两种类型的选路协议的其他方面进行了比较:
    • OSPF与RIP(以及其他选路协议)的不同点在于:OSPF直接使用IP,也就是说,它并不使用UDP或TCP;对于IP首部的protocol字段,OSPF有其自己的值,回顾一下IP数据报格式及首部中的各字段,如图:

      • 另外,作为一种链路状态协议而不是距离向量协议,OSPF还有着一些优于RIP的特点:
        • OSPF可以对每个IP服务类型计算各自的路由集,这意味着对于任何目的,可以有多个路由表表项,每个表项对应着一个I P服务类型;
        • 给每个接口指派一个无维数的费用;可以通过吞吐率、往返时间、可靠性或其他性能来进行指派;可以给每个IP服务类型指派一个单独的费用;
        • 当对同一个目的地址存在着多个相同费用的路由时,OSPF在这些路由上平均分配流量,我们称之为流量平衡;
        • OSPF支持子网:子网掩码与每个通告路由相连,这样就允许将一个任何类型的IP地址分割成多个不同大小的子网;到一个主机的路由是通过全1子网掩码进行通告的,默认路由是以IP地址为0 . 0 . 0 . 0、网络掩码为全0进行通告的;
        • 路由器之间的点对点链路不需要每端都有一个IP地址,我们称之为无编号网络,这样可以节省IP地址—现在非常紧缺的一种资源;
        • 采用了一种简单鉴别机制:可以采用类似于RIP-2机制的方法指定一个明文口令;
        • OSPF采用多播,而不是广播形式,以减少不参与OSPF的系统负载;
        • 随着大部分厂商支持OSPF,在很多网络中OSPF将逐步取代RIP;
(七)BGP:边界网关协议
  • BGP是一种不同自治系统的路由器之间进行通信的外部网关协议,BGP是ARPANET所使用的老EGP的取代品                         
  • BGP系统与其他BGP系统之间交换网络可到达信息,这些信息包括数据到达这些网络所必须经过的自治系统AS中的所有路径,这些信息足以构造一幅自治系统连接图;然后,可以根据连接图删除选路环,制订选路策略;
  •             
  • 首先,我们将一个自治系统中的IP数据报分成本地流量和通过流量;在自治系统中,本地流量是起始或终止于该自治系统的流量;也就是说,其信源IP地址或信宿IP地址所指定的主机位于该自治系统中;其他的流量则称为通过流量;在Internet中使用BGP的一个目的就是减少通过流量;
  • 可以将自治系统分为以下几种类型:
    • 残桩自治系统(stub AS),它与其他自治系统只有单个连接,stub AS只有本地流量;
    • 多接口自治系统(multihomed AS),它与其他自治系统有多个连接,但拒绝传送通过流量;
    • 转送自治系统(transit AS),它与其他自治系统有多个连接,在一些策略准则之下,它可以传送本地流量和通过流量;
  • 这样,可以将Internet的总拓扑结构看成是由一些残桩自治系统、多接口自治系统以及转送自治系统的任意互连;残桩自治系统和多接口自治系统不需要使用BGP——它们通过运行EGP在自治系统之间交换可到达信息;
  •               
  • BGP与RIP和OSPF的不同之处在于BGP使用TCP作为其传输层协议;两个运行BGP的系统之间建立一条TCP连接,然后交换整个BGP路由表,从这个时候开始,在路由表发生变化时,再发送更新信号;
  • BGP通过定期发送keepalive报文给其邻站来检测TCP连接对端的链路或主机失败;两个报文之间的时间间隔建议值为30秒;
    • 应用层的keepalive报文与TCP的keepalive选项是独立的;
(八)CIDR:无类型域间选路
  • 无类型域间选路(CIDR)是一个防止Internet路由表膨胀的方法,它也称为超网(supernetting);                                        
    • 为使用这个特性,网络要有一下3个特性:
      • 为进行选路要对多个IP地址进行总和时,这些IP地址必须具有相同的高位地址比特;
      • 路由表和选路算法必须扩展成根据32 bit IP地址和32 bit掩码做出选路决策;
      • 必须扩展选路协议使其除了32 bit地址外,还要有32 bit掩码
        • OSPF和RIP-2都能够携带第4版BGP所提出的32 bit掩码;
    • CIDR同时还使用一种技术,使最佳匹配总是最长的匹配;
参考链接:    http://www.cnblogs.com/newwy/p/3225416.html
                    http://blog.csdn.net/secondjanuary/article/details/9062253
                    http://blog.csdn.net/ericming200409/article/details/6347670
                    http://blog.csdn.net/fansongy/article/details/6709616
                     《TCP/IP详解卷一》
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐