Networks

IP中的路由选择

1

​ 网络这个东西是很复杂得，像一张蜘蛛网一样，将每一台通信设备连在一起，在上图中，工作站A想要访问工作站C，有不止一条路可以走，在现实中可能这样的路有非常多，这些路有远有近，有快的有慢得，那么在连接网络时，设备是如何知道哪一条路是最优的呢？通常，通信设备中都会有一个路由表（Routing Table），其实就是一张二维表格，记录着这台设备如果要去某个地方需要线通过哪些设备中转。

​ 下面是我本机（mac系统）中的路由表（只是部分截图），不光是路由器，每个接入网络的设备都会有路由表：

333

​ 上图是一张典型的主机路由表，执行netstate命令，-r选项是列出路由表，-n选项是以数字格式打印出IP地址（默认情况会打印网络名加主机名），本机的路由表大致由7列组成，下面介绍一下每一列的作用：

  • Destination：目标网络地址；
  • Gateway：网关地址，要去目标网络，需要先走这条路；
  • Flags：此条路由记录的标志，可以设置的标志大致有：
    1. U Up，该路由可以被使用；
    2. G Gateway，该路由是到一个网关（路由器），如果没有设置该标志，说明该条路由不是一个网关，是一条直接路由，Gateway列给出的是外出接口的IP地址；
    3. H Host，该路由是到一个主机，即Destination列给出的是一个完整的主机地址，如果没有设置该标志，说明该路由是到一个网络，而Destination列出的是一个网络地址：一个网络号，或者网络号与子网号的组合；
    4. D Dynamically，该路由是由ICMP重定向报文创建的；
    5. M Modified，该路由已被重定向报文修改；
  • Refs：正在使用该路由的活动进程个数，面向连接的协议如TCP在建立连接时需要固定路由，如果我们用Telnet连接10.158.51.78，它的值将增加1；
  • Use：通过该路由发送的分组数；
  • Netif：该记录使用的网络接口;
  • Expire：该记录过期时间。

​ 标志G是非常重要的，因为它区分了直接路由和间接路由（对于直接路由来说没有标志G）。间接和直接路由的区别在于，发往直接路由的分组中不但具有指明目的端的IP地址，还具有链路层地址，可以理解为数据报中的目的IP地址和链路层目的地址是一样的。当分组被发往一个间接路由时，IP地址指明的是最终的目的地，但是链路层地址指明的是网关（即下一站路由器），可以理解为可以理解为数据报中的目的IP地址和链路层目的地址是不一样的。

​ 标志G和H之间的区别：都代表通行设备，不过功能不一样，G标志区分了直接路由和间接路由，而H标志表明目的地址是一个完整的主机地址。若没有设置H标志，则说明目的地只是一个网络地址（主机号部分为0）。当为某个目的IP地址搜索路由表时，主机地址项必须与目的地址完全匹配，而网络地址项只需要匹配目的地址的网络号和子网号。

路由算法

静态路由选择策略

​ 静态路由选择策略即非自适应路由选择，只在交换机启动时计算和交换路由，此后路由不再改变。特点是简单并且开销较小，但不能及时适应网络状态的变化。具体可以分为以下三种：

  1. 扩散式路由选择

    一个网络节点从A线路收到分组后，立即把分组发向除A线路外的所有其他输出线路上，任何节点只接受最先到达的报文分组，不接受重复报文。适用于规模较小，对可靠性、健壮性要求很高的场合，还可被用于分发信息、判断可达性、寻找最短路径等。

  2. 固定路由选择

    所有网络节点都保存一张路由表，路由表中记录着所有为了到达某个目的节点而选择的下一个节点或链路，并不记录到该目的节点的所有中间节点。所以当一个分组到达节点时，只需要在查找这个路由表查找到对应的下一个节点，并发送分组。因为所有的路由都保存在一张表中，所以很简单，适合于一个负载稳定拓扑变化不大的网络中运行，但灵活度很差，无法对网络的拥塞和故障做出及时地反映。

  3. 随即路由选择

    当分组到达某节点后，随意选择一条线路进行分组转发。随即选择的路由不一定是最佳路由，增加了不必要的负载，而且分组传播延迟不可预期。

动态路由选择策略

​ 动态路由选择策略即自适应路由选择，在交换机启动时进行初始化，当网络发生阻塞或故障时能够随时进行更新。

  1. 孤立路由选择

    每个节点并不利用其他节点来的网络信息，仅根据本节点看到的信息来确定路由。最短等待法，将具有最短队列的链路作为最好路由你想学习算法（backward learning），将逆向的路由节点数最少的链路作为最好路由。

  2. 集中路由选择

    和固定路由选择一样，所有节点都保存一张路由表，和固定路由的区别在于固定路由算法中路由表的建立是手工完成的，而集中路由选择中路由表的建立是由网络中设置的一个路由控制中心RCC来几种完成的（收集、计算、分发）。缺点：离RCC较近的地方通信量的开销比较大，因为要周期性地从所有节点手机网络的状态信息的报告，同时还要生成路由表并从RCC发送到网内的所有节点；另一个是可靠性问题，一旦RCC出现故障，则整个网络就失去控制。

  3. 分布路由选择

    根据来自于相邻节点的信息，并通过一个最短花费路由算法计算出到每个目的地的路由。

动态路由选择中常用的两种算法：

  1. 距离向量路由协议（Distance Vector Routing，DVR）

  2. 链路状态路由协议（Link State Routing）

​ 路由选择是个非常复杂的问题，它既要 网络中所有节点协同工作，也需要路由选择适应环境的不断变化，并且这种变化是事先无法知道的，比如节点故障、网络拥塞等。

参考：《TCP／IP详解 卷1:协议》