网络层-路由算法

Scroll Down

网络层-路由算法

网络层的核心功能就是路由和转发,路由器根据转发表将到达的数据报转发至目的地址,转发表中的重要信息来源于路由算法,将路由信息记录在转发表中供路由器使用.

网络抽象:图

image-20200206132752284

图的抽象在网络领域应用很广泛,例如P2P应用中的网络连接也可以抽象成图的形式

图中链路标注的权值,也称为网络的费用,也可以称为代价或者距离,描述链路的费用大小或者成本大小

在描述路径的费用越小越好,成本越小

所以路由中关键问题是:源到目的的最小费用路径是什么?

可以抽象成最短路径问题,在网络中所有的路由器都需要具有的算法能力

路由算法:寻找最小费用路径的算法

路由算法分类

两种典型路由算法分类

静态路由 vs 动态路由

静态路由

  • 手工配置,通常来说由网络管理员配置路由的下一步的配置
  • 路由更新慢
  • 同等条件下,首选静态路由,优先级高

动态路由

  • 动态的计算路由,得到新的路由信息去更新转发表,路由更新速度快,大部分路由使用定期更新,可以及时响应链路费用或者网络拓扑发生变化时,可以动态响应

全局信息 vs 分散信息

全局信息:

  • 所有路由器掌握完整的网络拓扑和链路费用信息
  • 具有代表性的,现在在Internet广泛使用的是E.g.链路状态(LS)路由算法

分散信息:

  • 路由器只掌握物理相连的邻居以及链路费用
  • 邻居间信息交换,并且通过多次的运算的迭代过程规划处到达目的网络最佳的路由信息
  • 具有代表性的是E.g.距离向量(DV)路由算法

链路状态路由算法-Dijkstra算法

所有节点(路由器)掌握网络拓扑和链路费用

如何能够知道每一个路由器与之相连的链路费用?

链路状态广播

每一个路由器需要构建一个链路状态分组,路由器将与相邻的路由器的IP地址以及链路费用(探测),收集到以后构造一个链路状态分组,每个路由器都向相邻的路由器进行广播,当收集齐了网络中所有的信息后,所有节点拥有相同的信息.

计算从一个结点到达所有其他结点的最短路径.

迭代:K次迭代后,得到到达K个目的节点的最短路径

符号:

  • c(x,y):结点x到结点y链路费用,如果x和y不直接相连,则=∞
  • D(v):从源到目的v的当前路径的费用值
  • p(v):沿着当前路径,从源主机到v的前序节点
  • N':称为一个集合,已经找到最小费用路径的节点集合
    image-20200206211258634
    image-20200206211916765
  1. 首先先列出u到各个节点的路径,选出最短的路径uw
  2. 在选出uw路径中最短的路径,就得到了uwx的路径
  3. 在根据uwx选出相连中最短的路径,uwxy
  4. 在根据uwxy获得最短的uwxvy路径,最后获得uwxvyz路径,则将所有节点的最短路径都找到了

获得最短路径树:image-20200206212128808

dijkstra算法可能存在震荡现象:

假设链路费用是该链路承载的通信量,假设D,B会有1个单位的报文发送给A,C有e个单位报文发给A,所以此时初始状态为:

image-20200206214626156

此时B认为从B->C->A是最短的,C认为从C->D->A是最短的,D认为D->A是最短的

过了一段时间交换链路状态后,变为:image-20200206214720986

导致路径就完全相反,过了一段时间后就反复,路径又会相反
image-20200206214720986

这个时候会导致有数据在传输过程中,路径来回变换,导致报文的TTL最终减少为0,报文被丢弃,通常会用延迟交换链路状态的机制减少该问题产生

距离向量(Distance Vector)路由算法

Bellman-Ford方程(动态规划)

令:dx(y):=从x到y最短路径的费用(距离)

则dx(y)=min{c(x,v)+dv(y)}

image-20200206215121070

动态规划举例

求解u到z的最短路径费用

image-20200206215415851

作为u来说不需要知道整个网络拓扑,只需要u知道到达u的邻居的费用以及u的邻居到z的费用

对于u的重点来说:结点获得最短路径的下一跳,用于该节点的转发表中
image-20200206220048120

核心思想:

  • 每个结点不定时的将其自身的DV(距离向量)发送给其邻居

  • 当x接收到邻居的新的DV时,即根据动态规划更新其自身的距离向量估计:

image-20200206215954246

  • 每次更新之后,x也会告知他的邻居,最终Dx(y)将最终收敛于实际的最小费用dx(y)

特点:

异步迭代:

  • 引发每次局部迭代的因素
    • 局部链路费用改变
    • 来自邻居的DV更新

分布式:

  • 每个结点只有DV变化时才通告给邻居,只有在必要时才通告给它们的邻居

每个结点:主要有三个阶段

  • 等待(本地局部链路费用变化或者受到邻居的DV更新)
  • 重新计算DV估计
  • 如果DV中到达任一目的距离发生改变,通告所有邻居,之后重新进入等待阶段

举例:
image-20200206222147182

首先初始化各自的距离向量,然后互相交换链路状态,例如结点X,获得结点y发送的链路状态,则将DV进行修改,结点z也同步接收x和y的链路状态,z也进行更新,当x和z的距离向量信息更新后,再次向邻居进行发送最新的链路状态,此时发现x,y,z的向量信息都不变,则此次向量同步结束,将对应的向量信息更新到对应结点的路由表中

链路费用变化:

每个节点通常处于等待状态,只要链路费用或者邻居发送向量变化,就会开始重新计算,如果发生变化后,需要通知相邻邻居,如果不变,则就此停止,重新进入等待状态

链路费用变化过程:

  • 结点定时检测本地链路费用变化
  • 更新路由信息,重新计算距离向量
  • 如果DV变化,通过所有邻居,如果邻居的DV也变化,也会通告邻居的邻居

当链路费用由大变小的时候,重新计算很快,而如果链路费用由小变大的时候,会导致一个链路无穷计数的问题出现

链路无穷计数问题

image-20200206225322778

  1. 当y->x的距离从4变成60时,此时y->x的距离变成60,
  2. 而z通告的z到x的距离还是以前的5,所以此时y会变成y->z->x=1+5=6,此时y->变成6,
  3. 当y到z的距离向量发生变化时,重新发送给z,z此时发现之前由z->y->z的距离由4变成了6,此时z重新运算得到z->y->x=1+6=7
  4. 以此类推可以一直进行下去,最后z才会发现经过y到达的距离大于z->x的50距离更大了,重新维护成z->x的链路为50,y也接到z的向量变化后重新运算得知y->z的最小距离为51,自此之后停止计算
毒性逆转(poisoned reverse)
  • 如果一个结点(z)到达某目的(y)的最小费用路径是通过某个邻居(y),则:通告给该邻居结点到达到达该目的的距离为无穷大.例如:z->y->x是最小路径,则z通告y的费用为z->x的费用是无穷大

image-20200206225613321

定义最大度量(maximum metric)
  • 定义一个最大的有效费用值,如15跳步,第16跳步则表示为∞

image-20200206225741285

定义一个最大度量的方法,会在有限的交换步骤中,会达到最终收敛状态

层次路由

之前的方式是将网络抽象成一张图,使用dijkstra算法或者distance Vector算法计算最短路径,过于理想化,对于实际网络或者大规模的网络中,不可行

如果考虑大规模的网络会导致:

  • 路由表几乎无法存储
  • 路由计算过程的信息交换量巨大,会淹没链路

有些网络管理员希望能够达到管理自治:

  • 每个人网络的管理可能期望自主控制网内的路由
  • 现有的网络可以说是各个自治的网络互连在一起

层次路由介绍

把大规模的网络再抽象一层,将一个区域或者一个组织内的路由器聚合在一个区域,并且给他一个16比特的编号,称为自制系统AS(autonomous systems)

  • 同一个AS内的路由器运行相同的路由协议(算法)

  • 不同自治系统内的路由器可以运行不通的AS内部路由协议

所以每个自制系统都需要一个特殊的路由器,称为网关路由器(gateway router)

网关路由器的特点为:

  • 位于各个AS的边缘
  • 通过链路连接其他AS的网关路由器

通过网关路由器可以交换跨越不同AS之间的数据

互连的AS

image-20200206231129439

AS的转发表由AS内部路由算法与AS间路由算法共同配置:

  • AS内部路由算法设置AS内部目的网络路由入口
  • AS内部路由算法与AS间路由算法共同设置AS外部目的网络路由入口

自治系统间路由任务

image-20200206231412405

自治系统间的路由解决的问题,假如AS1内某路由器接收到一个目的地址在AS1之外的数据报:路由器应该将数据报转发个哪个网关路由器?

  • 此时AS1必须知道哪些目的网络可以通过AS2到达,哪些可以通过AS3到达,通过自治系统间路由协议可以得知
  • 将这些网络可达性信息传播给AS1内部路由器

多AS之间传输数据的工作过程
image-20200206232126110

假如一个AS1内的数据需要传输数据给子网X,可以通过多个AS连接,例如图1d该送到AS2还是AS3网络?:**使用热土豆路由:将分组发送给最近的网关路由器**

  1. 通过AS间路由协议可以学习到子网x可以通过多个网关到达
  2. 利用AS内部路由协议获得的路由信息确定到达每个网关的最小费用路径的费用
  3. 热土豆路由:选择最小费用路径的网关
  4. 通过转发表,确定去往最小费用网关接口

Internet路由

AS内部路由

  • Internet采用层次路由
  • AS内部路由协议也称为内部网络协议IGP(interior gateway protocols)
  • 常见的AS内部路由协议
    • 路由信息协议:RIP(Routing Information Protocol)
    • 开发最短路径优先:OSPF(Open Shortest Path First)
    • 内部网关路由协议:IGRP(Interior Gateway Routing Protocol),是思科私有的协议

RIP协议

遭遇1982年随BSD-UNIX操作系统发布,使用的是距离向量路由算法:

  • 距离度量:最大跳步数是max = 15 hops,每条链路1个跳步
  • 每隔30秒,不管变化与否,进行交换一次DV,成为通告(advertisement)
  • 每次通告:最多25个目的子网(以IP地址形式)
  • 通告时将路径的下一跳也给发送给邻居,可以避免无穷计数问题,是一种变相的毒性逆转方式
RIP:链路失效,回复
  • 如果180秒(6次通告时间)没有收到通告->推断邻居/链路失效
    • 经过该邻居的路由不可用,需要重新计算路由
    • 向邻居发送新的通告
    • 邻居再一次向外发送通告(如果转发表改变的话)
    • 链路失效信息能否快速传播到全网?可能会发送无穷计数问题,不过RIP设置了最大跳步数是15步,可以在有限的部署内获得最终的步数
    • 毒性逆转技术用于解决乒乓环路问题
RIP路由表的处理
  • RIP路由表利用一个称作route-d的守护进程,是一个标准的应用层进程进行管理
  • 通告报告周期性的的通过UDP数据报发送通告

为什么使用应用层的进程来实现的协议要属于是网络层?

  • 通常并不是根据协议的具体实现形式来划分的,而是通过功能来划分的,做的功能是哪一层的,就属于哪一层,可能通过高层进程或硬件实现,但是只根据功能来划分是哪个层次的协议

OSPF 协议

  • 开放:公众可用

  • 采用链路状态路由算法

    • 构造链路状态分组,并在网络中扩散(通告)
    • 每个路由器都收集全了链路状态分组后,会维护一个链路状态数据库,逻辑上就有了一个网络拓扑
    • 利用dijkstra算法计算路由
  • OSPF通告中每个入口对应一个邻居路由器,多少个邻居与其相连,就有多少个入口,会存放邻居的id,链路的费用等

  • OSPF通告在整个AS范围内泛洪

    • 构造OSPF报文直接封装到IP数据报中
  • 与OSPF极其相似的路由协议:IS-IS路由协议(基于OSI的7层网络模型设计的协议),使用的算法也是链路状态路由算法

OSPF相对于RIP的优点
  • 安全:所有的OSPF报文需要可以被认证(预防恶意入侵),必须来源自已认真的路由器发送

  • 允许同时使用多条到达目的的相同费用的路径(RIP只能保留一条),有大量的数据到达网络时,可以分散路由到多条链路上,可以达到一个流量负载分担

  • 对于每条链路,可以针对IP数据报不同的TOS(服务类型)设置多个不同的费用度量,例如有些链路不想发送多媒体数据,就将多媒体Tos的分组费用设置为高,将其他的数据分组费用设置为低,即可达到针对不同服务类型设置不同的费用度量

  • 继承单播路由与多播路由:多播OSPF协议(MOSPF)与OSPF利用相同的网络拓扑数据,可以使用相同的链路状态数据库,很容易就可以根据单播路由实现多播路由

  • 最大优点:OSPF在针对一个大规模的AS,可以支持内部分层

image-20200207171244226

分层的使用需要引入一种特殊的身份路由器,区边界路由器:,既是主干区内的路由器,也是局部区的路由器,汇总到达所在区网络的距离,通告给其他区边界路由器,这样区域内部其他路由器可以通过边界路由器访问其他区域网路

主干路由器:在主干区内运行OSPF路由算法

AS边界路由器:用于连接其他的AS系统,与区边界路由器的区别为,一个是内部分层的是在同一个AS系统内,AS边界路由器用于连接其他AS系统

AS间路由协议:BGP(Border Gateway Protocol)

现在运行的就是BGP4协议,是事实上的标准域间路由协议,是将Internet粘合为一个整体的关键

BGP为每个AS提供了一种手段:

  • eBGP:从邻居AS子网可达性信息
  • iBGP:向所有AS内部路由器传播子网可达性信息
  • 基于可达性信息与策略,确定到达其他网络的好路径

BGP基础

  • BGP会话(session):两个BGP路由器(通常使用术语 peers)交换BGP报文:

    • 通告去往不通目的前缀(prefix)的路径(路径向量协议,两者之间交换的是到达一个完整的自治系统的路径),通常会用一个前缀代表一个子网或者一个大的IP网络
    • 报文交换基于半永久的TCP连接,基于应用层来实现,由于BGP协议的特殊性,当两个路由器之间的TCP连接建立后,通常很长时间都不会拆除,所以称为半永久
  • BGP报文:四种不用的报文类型

    • OPEN报文:与peer建立TCP,向对方请求TCP连接,并认证发送方
    • UPDATE报文:当一个peer向另外一个peer通告一个新路径或者修改路径时,则需要发送该类报文
    • KEEPALIVE报文:在长时间无UPDATE报文时,保活连接,也用于对OPEN请求的确认
    • NOTIFICATION报文:报告先前报文的差错,也被用于关闭一个BGP会话

BGP协议通告

当AS3通告一个前缀给AS1时:

  • AS3承诺可以将数据报转发给该子网

  • AS3在通告中会尽量聚合网络前缀,减少网络传输量

BGP分发路径信息

  • 在两个自治系统之间建立会话并分发路径信息时,使用eBGP会话进行交换可达性信息

  • 内部会话可以通过iBGP向AS1内的所有路由器分发新的前缀可达性信息

  • 当路由器获得新的前缀可达性时,即在其转发表中增加关于该前缀的入口

image-20200207173524330

路径属性与BGP路由

通告的前缀信息包括BGP属性,前缀+属性=路由

两个重要属性:

  • AS-PATH(AS路径):包含前缀通告所经过的AS序列:e.g.,AS 67,AS 17

  • NEXT-HOP(下一跳):开始一个AS-PTH的路由器接口,指向下一跳AS

  • AS-PATH(AS路径):包含前缀通告所经过的AS序列:录入e.g.,AS 67,AS 17

  • NEXT-HOP(下一跳):开始一个AS-PATH的路由器接口,指向下一跳AS.

比如3a向1c通过eBGP会话,发送AS-PATH和NEXT-HOP,下一跳是指向开始一个AS-PATH的路由器接口

image-20200207174450002

如图:3a向1c发送一个eBGP报文的时候,不仅要带上AS-PATH,还需要带上下一跳的地址(3a本身),这样1c就知道下一跳的IP地址是3a.

当一个AS到达另一个AS有多种路径时,如图2c和2b连接其他网络来说,AS-PATH是相同的,但是NEXT-HOP是不同的,指向2c或者2b

BGP路由选择

  • 网关路由器收到路由通告后,利用其输入策略决策接受/拒绝该路由

    • 根据一个策略,可能会从不接受路由到某个路由,当其他路由通告时,会根据策略接受或拒绝
    • 基于策略路由
  • 路由器可能获知到达某目的AS的多条路由,基于以下准则选择:

    • 本地偏好值属性:人为的为某些路径设置一些偏好值,偏好值越大就优先级越高,称为策略决策
    • 当本地偏好值无法选择出路径时,根据最短AS-PATH,路径越短越好
    • 最近的NEXT-HOP路由器:热土豆路由
    • 可以附加其他的准则

BGP路由选择策略

image-20200207192521971

提供商网络只为他的客户服务!

为什么采用不同的AS内与AS间路由协议

策略:

  • inter-AS(不同的AS系统间):期望能够管理控制流量如何路由,谁路由经过其网络等
  • intra-AS(自治AS系统内):单一管理,无需策略决策

规模:

  • 层次路由可以节省路由表大小,减少路由更新流量
  • 可以适应大规模互联网

性能:

  • intra-AS:侧重性能
  • inter-AS:由策略主导,不一定按照性能来主导