计算机网络之Ch5网络层:控制平面

Posted on

5 网络层: 控制平面

5.1 概述

  • 计算维护和安装转发表和流表
  • 两种可能方法:
    • 每路由器控制: 每台路由器运行一种路由选择算法
    • 逻辑集中式控制: 需要控制代理CA和控制器通信并且按控制器命令行事, CA不能直接相互交互, 也不主动参与计算转发表

5.2 路由选择算法

  • 路由选择算法的目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径.

  • 不同的路由策略:

    • 集中式路由选择算法:
      • 用完整的全局性的网络制式计算出源到目的地之间的最低开销路径
      • 具有全局状态信息的算法称为链路状态(LS)算法
    • 分散式路由选择算法:
      • 路由器以迭代, 分布式的方式计算出最低开销路径
      • 没有结点拥有关于所有网络链路开销的完整信息
      • 例如距离向量(DV)算法

  • 洪泛:

    • 不需要网络信息
    • 分组转发到路由器的每个邻居
    • 很多副本到达目的地
    • 缺点: 多副本, 环路问题
    • 优点:
      • 尝试所有路径, 鲁棒
      • 至少一个分组采用最小消耗道路
      • 访问所有路由器
  • 随机路由: 随机选取一个输出路径
  • 最小消耗算法:
    • Dijkstra算法
    • Bellman-Ford算法

5.2.1 链路状态(LS)路由选择算法

  • 在该算法中，网络拓扑和所有链路开销都是已知的。实践中是通过让每个节点向网络中广播链路状态分组来完成的。其中链路状态分组包含和自己相连的链路的开销信息，这常常由 链路状态广播算法完成(洪泛)
  • 使用协议：OSPF，使用的算法：Dijkstra算法，复杂度$O(|V|^2)$.

Dijstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1   Initialization: 
2    N’ = {u} 
3    for all nodes v 
4      if v is a neighbor of u 
5        then D(v) = c(u, v) 
6      else D(v) = ∞ 
7  
8   Loop
9    find w not in N’ such that D(w) is a minimum 
10   add w to N’ 
11   update D(v) for each neighbor v of w and not in N’: 
12         D(v) = min(D(v), D(w)+ c(w, v) ) 
13    /* new cost to v is either old cost to v or known 
14     least path cost to w plus cost from w to v */ 
15  until N’= N
  • 找给定源到其他所有节点之间的最短路
  • k次迭代后得到k个目的节点的最低开销路径
  • 例子见书P246
  • 存在的问题：拥塞敏感的选择振荡
    • 在拥塞敏感且将路径负载当作开销的情况下，所有路由器同时运行LS算法，会使得由于选择了某一条目前最短开销路径而导致网络中路径开销改变，LS算法得出的最短开销路径会不断摇摆振荡。
    • 解决办法是 使每台路由器广播链路状态分组的时间随机化。

5.2.2 距离向量(DV)路由选择算法

  • 该算法是一种 迭代的，异步的，分布式的算法，使用的协议有BGP，RIP.
  • 使用的算法：Bellman-ford算法，复杂度$O(|V||E|)$，算法关键为$d_x(y)=\min_v\{c(x,v)+d_v(y)\}$

Bellman-Ford算法

在每个节点x:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1  Initialization: 
2    for all destinations y in N: 
3       Dx(y)= c(x, y)/* if y is not a neighbor then c(x, y)= ∞ */ 
4    for each neighbor w 
5       Dw(y) = ? for all destinations y in N 
6    for each neighbor w 
7       send distance vector  Dx = [Dx(y): y in N] to w 
8 
9  loop 
10    wait  (until I see a link cost change to some neighbor w or 
11            until I receive a distance vector from some neighbor w) 
12 
13    for each y in N: 
14        Dx(y) = min_v {c(x, v) + Dv(y)} 
15 
16 if Dx(y) changed for any destination y 
17       send distance vector Dx = [Dx(y): y in N] to all neighbors 
18 
19 forever
  • 每个节点维护一张路由选择表, 包含 该点和它的所有邻居 到 所有节点 的开销
  • 初始计算自己的距离向量$D_x=[D_x(y):y\in N]$,发送自己的距离向量给相邻节点
  • 保存相邻节点距离向量，并依据其更新自己的距离向量，再循环
  • 例子:

DVtable

存在的问题：无穷计数

  • 当DV算法稳定后，网络中某条链路开销突然改变后，可能会出现路由选择环路，节点间的最短路径互相依赖，结果会在节点间不断来回变换，直到最后稳定，变换的次数和链路开销改变后的值相关，值足够大时会导致变换很多次，因此被称为无穷计数问题.
  • 解决方法：毒性逆转，即某一结点z到达x的最小开销路径的下一跳是y的话，z发送给y的信息中，z到x的最小开销为正无穷，使得此时y不可能通过依赖z来选择到达x的最小开销链路，从而避免无穷计数. 毒性逆转并不能完全解决无穷计数问题.

两者对比

LS:

  • 链路状态通过洪泛告知其他节点
  • 每个节点有复杂的拓扑, 构造自己的路由表
  • 鲁棒性好
  • 收敛快

DV:

  • 每个节点维护距离向量
  • 向量和邻居节点交换
  • 分布式构建路由表
  • 报文简单
  • 鲁棒性差
  • 收敛慢

5.3 因特网中自治系统内部路由协议

  • 自治系统AS: 一个ISP中的路由器以及互联他们的链路构成一个AS
  • 同一个AS中使用同一个路由协议

  • 网关:

    • AS之间的路由
    • 同AS内与其他路由器之间的路由

  • IGP—自治系统内部协议

    • RIP: 使用距离向量
    • OSPF: Open Shortest Path First, 使用链路状态
  • EGP—自治系统之间
    • BGP

RIP

  • 使用DV算法，应用于应用层
  • 在路由表或报文中Distance Matric表明当前节点(路由器)到达目的子网的跳数，取值为[0,15]，到达和路由器直接相连的子网跳数为0，取值为16则表示正无穷。后来不仅使用跳数，还增加了队列长度作为链路开销
  • 各个路由器每30s中向相邻节点发送一次路由表信息
  • 超过180s没有接收到相邻节点的路由表信息则认为已经失去和相邻节点的连接

OSPF

  • 使用LS算法和洪泛链路状态信息，周期性广播链路状态

  • 每一个路由器上都储存了一个含有着整个自治系统网络信息的有向图，其中路由器，主机，子网都是节点，他们之间的关联作为图的边

  • 通过在本地运行LS算法，生成一个以自己为根的最短路径树(SPF Tree)

  • OSPF的优点：
    • 安全：所有OSPF消息都经过身份验证，以防止恶意入侵。
    • 多条相同开销的路径：当存在多条相同开销的路径时，OSPF允许使用多条路径
    • 对单播和多播路由选择综合支持
    • 支持在单个AS中的层次结构：在AS内部可以划分区域，每个区域运行自己的OSPF,然后由一个主区域为其他区域之间流量提供路由选择

5.4 ISP之间的路由选择: BGP

  • 分组跨越多个AS进行路由的时候, 需要一个自治系统间路由选择协议

  • 因特网中所有的AS运行相同的AS间路由选择协议, 称为边界网关协议BGP

  • 在BGP中，分组并不是路由到一个具体的目的地，而是一个CIDR化的前缀，即路由到一个子网或一个子网的集合，所以运行BGP协议的路由器的转发表项格式大致为(前缀，接口)

  • 路由器分为:

    • 网关路由器: 位于AS边缘的路由器, 直接连接到在其他AS中的一台或多台路由器
    • 内部路由器: 仅仅连接在它自己AS内的主机和路由器

  • BGP连接分为:

    • 外部BGP(eBGP)连接: 跨越2个AS的BGP连接
    • 内部BGP(iBGP)连接: 在相同AS中的两台路由器之间的BGP连接

  • 例子见书P258

  • BGP给每个AS提供了如下工具：

    • 通告路由信息：
      • 通过eBGP(external BGP)来确保AS内部某个子网被整个因特网中其他AS所知。
      • 通过iBGP(internal BGP)来确保这个信息在其他AS内部传播到所有BGP路由器上。
    • 确定到目的前缀”最好的”路由：
      • 当BGP通告前缀的时候，前缀中会带有一些BGP属性比如AS-PATH和NEXT-HOP.
        • 当一个前缀通过某个AS时，该AS会在该前缀的AS-PATH上加上自己的AS number. 该属性用来检测和防止环路，当路由器在AS-PATH中看到了自己所在的AS的number,则说明有环路，拒绝该通告。
        • NEXT-HOP是AS-PATH中起始的路由器接口的IP地址。
      • 热土豆路由选择：选择的路由是到 开始该路由的NEXT-HOP路由器的最小开销，即自己AS内部开销最小，而不管其他AS。
      • 路由选择算法:(1)本地偏好优先。(2)最短AS-PATH优先。(3)热土豆选择。(4)BGP标识符选择

IP任播

  • 常用于DNS中，使得每个用户能够从最靠近自己的服务器上获得想要的内容。
  • 比如DNS根IP只有13个，但是每一个IP被分配在不同地方多个DNS根服务器上，通过BGP通告后，这些不同地方会被当作到达同一地址的不同路径，然后在用户申请访问的时候，根据上面说的路由选择算法，选择最靠近自己的服务器。

5.6 ICMP: 因特网控制报文协议

  • 数据承载于IP分组中, 协议类型1, 不可靠
  • 被主机和路由器用来彼此沟通网络层的信息, 传递控制信息和差错信息

ICMP

  • 使用ICMP: Ping
    • 测试目的地可达性
    • 源发送回显请求echo request(ICMP类型8编码0的报文)
    • 远程系统收到ICMP包, 则发送回一个echo reply包给源
    • 从而还可以计算来回的时间和跳数(用TTL)
  • 使用ICMP: Traceroute
    • 得到到达目的地需要的跳数
    • 源主机向目的地主机发送一系列普通的IP数据报, 每个携带一个具有不可达UDP端口号的UDP报文
    • 第一个数据报TTL为1, 第二个为2, 以此类推
    • 第n个数据报到达第n台路由器时, 路由器观察到数据报的TTL正好过期, 丢弃该数据报并发送一个ICMP告警报文给源主机(类型11编码0)
    • 数据报之一会到达目的主机, 因为UDP端口不可达, 目的主机发送一个端口不可达的ICMP报文(类型3编码3). 源主机收到后, 就知道不用再发送另外的探测分组.
  • 使用ICMP: path MTU
    • 决定路径中的最小MTU
    • 发送带有don’t fragment的IP包, 如果超过路径MTU, 则会返回错误信息parameter unintelligible. 减少IP包大小直到不报错.
    • 路径必须固定, 结果方法: 使用源路由