几个概念

  • 默认路由器：一台主机直接连接到的路由器
  • 源路由器：源主机的默认路由器
  • 目的路由器：目的主机的默认路由器

将网络抽象成图

1
2
3
4
5
6
G = (N,E)

N Node 路由器集
E Edge 链路集

c(x,x') 节点x和x'之间的费用

目的是选择$\Sigma c$最小的算法

#TBS
选路算法的分类

  • 分法1

    • 全局选路算法
      • 所有路由器知道某个网络拓补图的结构
      • 链路状态算法(LS)
    • 分散式选路算法
      • 距离向量算法(DV)

  • 分法2

    • 静态选路算法
    • 动态选路算法

  • 分法3

    • 负载敏感算法
      • 链路费用明显受链路状态影响
    • 负载迟钝算法

链路状态选路算法

Dijkstra算法
（略）（略掉了算法复杂度分析和算法复杂度分析等玩意）
可能出现的问题
选路的结果对策略更改的影响过于明显（带宽的负载呈震荡变化）（体现了负载敏感的特性）
解决的方案

  • 强制链路费用不依赖于承载的流量
  • 避免所有路由器都同时使用该算法（路由器之间自同步），控制链路通告的时间

距离向量选路算法

Bellman-Ford算法
分步、迭代、自我终止、异步
$d_x(y) = min_v({c(x,v) + d_v(y)})$

距离向量
$D_X = [D_X(y):y\in N]$

具体工作方式

  • 初始化的时候会设置自己的距离向量（不是邻居的设置成$\inf$），然后和和邻居交换距离向量
  • 每个节点不定时向邻居发送自己距离向量的估计值
  • 当x从邻居接收到新的$D_V$估计值时，它使用B-F方程更新自己的$D_v$

1、距离向量算法：链路开销改变与链路故障


在一个环路中：
好消息传得快
负载减小的时候，能够很快达到收敛状态
坏消息传得慢
负载增大的时候，要迭代很多次才能收敛
（获取的距离信息有误，走了不必要的路径更新，即路由器之间有往返路径）

解决：毒性逆转
如果z到x的最短路径经过y，那么y向z查询距离向量$D_z$的时候获得的$D_z(x)$是无穷（因为到了z也是要折返的，不可能选这条路径）

但是毒性逆转也只适用于某些特定场景

复杂度

LS与DV路由选择算法的比较

  • 报文复杂性
  • 收敛速度
  • 健壮性

5.3 自治系统内部路由选择

自治系统AS(Autonomous System)

  • AS内执行完全相同的选路算法
    • 内部网关协议IGP
      • RIP,OSPF,IGRP
        • IGRP在2016年之前是Cisco专利

转发表是由AS内部选路算法和AS间选录算法共同决定的

开放最短路优先OSPF

RIP

  • 属于DV算法
  • 相邻两节点之间的费用设置为1，不考虑链路费用，只考虑要经过多少链路（或者多少跳）
  • 一条路径的最大费用限制为15
  • 选路信息每30s在邻居之间用RIP通告的形式进行交换
  • 180s后没有收到某个主机的RIP通告则认为其已经离线
  • 具体做法
    • 路由表构成
      • 目的网络号、下一跳路由器、距离

OSPF

  • 属于应用层
  • 向本自治系统的所有路由器发送信息（洪泛法flooding）
  • 实际上是dijkstra
  • 发送的信息就是与本路由器相邻的所有路由器的链路状态
  • 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息
  • 最终每个路由器都能获得一个完整的链路状态数据库（整个网络的拓扑图）
  • 一些细节

层次OSPF

  • 为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自 治系统再划分为若干个更小的范围，叫作区域
  • 每一个区域都有一个 32 bit 的区域标识符
  • 区域也不能太大，在一个区域内的路由器最好不超过 200 个
  • 区域边界路由器：分组向该区域之外的选路
  • 主干路由器：运行选路算法
  • 边界路由器：与AS外的网络通信

5.4 自治系统之间的路由选择BGP

边界网关协议BGP（Border Gateway Protocol）

#TBS BGP劫持？
场景：

  • 源到目标只有一条路径
  • 源到目标有多条路径
    • 热土豆选路：将报文发送到距离最近的路由器
eBGP(external)

从相邻的AS获取子网可达信息

iBGP(internal)

向AS内部路由器传递子网可达信息

BGP会话

通过半永久TCP连接交换BGP信息

路由通告

前缀+属性 = 路由
属性有：

  • AS-PATH
  • NEXT-HOP

网关可以决定接受的路由是否保留(可以制定特殊的策略)

BGP子网聚合

将小子网聚合成大子网，相当于AS成为一个大子网
对于子网网段不在聚合子网网段中的情况，用最长前缀匹配就能解决

BGP消息

AS内路由器对远程前缀转发表项的设置

路由路径选择

  • 本地偏好值：根据策略决定
  • 最短AS-PATH：传递到能把报文送到最近相邻AS的路由
  • 热土豆路由：选择AS内部开销最小的接口路径
  • 如果仍余下多条路由，该路由器使用BGP标识以选择路由
IP组播

将数据发送到属于同一个组的多台计算机

#TBS 书本5.4.5之后的内容