计算机网络原理 笔记 5

控制平面

路由选择算法

在路由器中寻找到最短路径，对于一个路由器，主要寻找到将其数据转发到其他路由器所需要的最短路径
算法分类方式

  • 根据信息量
    • 集中式路由选择：全局，了解该路由网络的全部信息并据此进行计算
    • 分散式路由选择：局部，每个节点只知道与自己到相邻接点的花销
  • 根据可变性
    • 静态：路由基本不随时间变化
    • 动态：随着网络流量或拓扑变化而动态改变路径，更加方便但是受一些特殊问题的影响
  • 对负载敏感性：
    • 敏感：趋近于绕开拥塞链路
    • 迟钝：拥塞无影响，现代多采用这种，原因是链路开销不明确反映拥塞水平

LS

信息的全局性通过链路状态广播算法来完成

之后使用——伟大的Dijkstra!!!

路由振荡问题：

如图的链路为了避免选择高拥塞的道路，每次LS之后都会改变道路，导致了路由实际上处在振荡之中，并且从结果上来看，其选择的也并不是全局最优解

解决方案：

  • 要求链路开销不依赖负载（不合理）
  • 确保并非所有路由器同时运行LS，但是由于自同步的存在很困难，避免自同步可以采用链路通告随机化的方式

DV

  • 迭代：循环计算直到没有更多信息需要交换
  • 异步：不要求所有计算同步执行
  • 分发式：每个节点计算接收邻居的信息，执行计算之后再发回去

基本原理是动态规划Bellman-Ford方程：

dx→y=min⁡v∈Γ(x)(cx→v+dv→y)d_{x\to y} = \min_{v\in\Gamma(x)}(c_{x\to v} + d_{v\to y})

算法如下：

  • 给定图G=(V,E)G = (V, E)
  • ∀x∈V\forall x \in V，维护如下信息：
    • 其与每个直接邻居的开销cx→vc_{x\to v}
    • 距离向量Dx→=[Dx→y: ∀y∈V]\overrightarrow{D_{x}} = [D_{x\to y}:\text{ } \forall y \in V]
    • 其所有邻居的距离向量
  • 每个节点不时向邻居发送自己的距离向量
  • 某个节点接收到邻居的信息或发现与自己连接的链路开销有变的时候，根据BF方程更新自己的距离向量
  • 如果距离向量发生了变化，则发送给邻居

可以证明，lim⁡Dx→y→dx→y\lim D_{x\to y} \to d_{x\to y}


注：图中cx→yc_{x\to y}应该是22而非2121

链路开销改变与链路故障

当链路开销增加时，很容易导致链路故障，如下图

右边的图会出现选择选择环路，即：

  • Init: Dz→x=5(z→y→∗x),Dy→x=4(y→z→∗x)D_{z\to x} = 5(z \to y \to^{*}x), D_{y\to x} = 4(y \to z \to^{*}x)
  • 1st forward: Dy→x=6(y→z→∗x),Dz→x=7(z→y→∗x)D_{y\to x} = 6(y \to z \to^{*}x), D_{z\to x} = 7(z \to y \to^{*}x)
  • 2nd forward: Dz→x=8(z→y→∗x),Dy→x=9(y→z→∗x)D_{z\to x} = 8(z \to y \to^{*}x), D_{y\to x} = 9(y \to z \to^{*}x)
  • …
  • Until: Dz→x=50(z→x),Dy→x=51(y→z→x)D_{z\to x} = 50(z\to x), D_{y\to x} = 51(y\to z \to x)

在最终情况之前，y,zy, z所保存的到xx的路径都是错误的，当变化后的开销（此处是4→604\to 60）过大的时候，迭代轮次会过大导致传播速率迅速降低

毒性逆转

解决上述特定问题的方式（对于节点度数超过33的环路将无法解决）

如果zz需要通过yy到达xx，则在zz发送过去的信息中，记Dz→x=∞D_{z\to x} = \infty

善意的小谎言~

两种算法的比较

记n=∣V∣,m=∣E∣n = |V|, m = |E|：

  • 报文复杂性：由于LS是全局的，因此其需要O(mn)O(mn)个报文进行初始化，并且在一条链路发生改变时需要传递给所有节点，更复杂
  • 收敛速度：LS复杂度O((m+n)log⁡n)O((m + n)\log n)，DV收敛很慢
  • 鲁棒性：LS鲁棒性更强，因为全局算法相对来说路由器是解耦的，但是DV中一个不正确的节点会扩散到全局

OSPF

自治系统：由一组通常处在相同管理控制下的路由器组成，通常一个ISP中的路由器和其链路构成同一个AS，一个自治系统内的路由选择算法为自治系统内部路由选择协议

OSPF是一种LS，也即一个自治系统内采用全局广播的形式，并且即使未发生变化，也要周期性的广播链路状态，同时各条链路的开销，同时要检查链路运行状态，并允许路由器向相邻路由器广播

优点：

  • 安全：能够鉴别OSPF路由器之间的交换，防止数据入侵
  • 并发：允许使用多条相同开销的路径
  • 可综合：容易扩展为MOSPF，从而支持多播
  • 可层次化：支持一个AS中的层次化，即一个自治系统可以被划分为多个区域，每个区域之间可以相互交流，并且只包含一个主干

BGP

用于AS之间的通信，是一种分布式、异步的协议。

作用

在BGP中，一个路由器的转发表具有(xi,I)(x_{i}, I)的形式，分别代表前缀与接口号

  1. 从邻接AS处获得前缀的可达性信息
  2. 并且每个子网可以向其他部分广播自己的存在性
  3. 确定到该前缀的最优路由

可达性通告

如上图，每对路由器中间使用179端口的半永久TCP连接，每个AS内部的会话为iBGP，跨AS的称为eBGP，于是通告路径如下：

  • xx子网向自己所在的AS的网关路由器发报文通知自己存在
  • 网关路由器3a3a告知邻接的AS网关路由器：AS3中存在子网xx
  • 2c2c接收到这个消息，并通知AS2内的所有路由器
  • 2a2a将信息发送给相邻的AS1，告知其xx存在AS3内，并且可由AS2到达

同样的，不同AS之间可以增加对等链路，这样会导致子网和路由器之间存在多条路径

最优路由选择

在通告的子网前缀中增加一些属性，称为BGP属性，前缀及其属性称为路由，比较重要的属性包括：

  • AS-PATH：这个AS是一条路由器路径中的一个，包含了已经通过的路由器列表，可以用于防止环路
  • NEXT-HOP：AS-PATH的起始路由器接口地址，每个AS的不同路由器接收到的NEXT-HOP属性可能不一样，用于指示从该路由器出发怎么找到子网

热土豆

查找AS内部路由转发信息，找到通往不同NEXT-HOP的最低开销路径，进而选择开销最低的那条
也即，热土豆追求的是贪心的尽快将报文传递出这个AS

路由器选择

当一个路由器希望到达一个前缀时，会将到该前缀的路由集合进行优先级排序，优先级如下：

  • 每个路由增加一个本地偏好属性，属性值取决于管理员，本地偏好越高越优先
  • 本地偏好相同时，选择AS-PATH最短的路由，由此规则确定路由之后通过DV决定路径
  • 都相同时，采用热土豆
  • 热土豆仍然无法选择时，采用BGP标识符

IP 任播

用于DNS中的服务，通常用语降低时延，例如CDN会向其下的多台服务器分配相同的IP，这样当一台路由器向这个IP发送信息的时候，路由器会向最近的一个服务器转发请求

路由选择策略

  1. 客户网络在多宿的情况下，可能会有类似提供商网络的行为，因此，其需要向相邻的所有提供商网络通告自己不能连通任何其他目的地，这样可以确保客户与提供商身份的相对稳定性
  2. 任何穿越ISP主干网的流量必须是其源或目的中至少一个唯一ISP的客户网络中（商业原因）

SDN

SDN体系结构具有4个关键特征：

  • 基于流的转发：分组转发规则被规定在流表中，SDN控制平面用于计算、管理和安装流表项
  • 数据平面和控制平面分离
  • 位于数据平面交换机外部的网络控制：控制平面独立于数据平面之外
  • 可编程的网络：网络控制应用程序是可编程的

控制器与控制程序

控制器的功能需要有：

  • 通信层：负责控制器与数据平面之间的交流，称为南向API
  • 网络范围管理层：控制决定层，配置流表以完成端到端转发、负载均衡、防火墙等功能
  • 与应用程序接口：负责控制器与控制程序之间的交流，称为北向API

OpenFlow协议

运行在实现了OpenFlow API的设备上，例如SDN控制器和数据平面之间，基于TCP，默认端口6653
控制器发送的重要报文包括：

  • 配置：查询并设置交换机的配置参数
  • 修改状态：增加、删除或修改交换机的流表项，设置交换机端口特性
  • 发送分组：在交换机的特定端口发送特定报文

交换机发送的重要报文报告：

  • 流删除：通知控制器删除一个流表项
  • 端口状态：通知控制器端口状态的变化
  • 分组入：将分组发送给控制器，如果该分组不能被流表匹配则控制器会做额外处理，如果可以匹配则会将该分组作为一个动作

实例

ICMP

主机和路由器之间用来沟通网络层信息的协议，最典型的用途是差错报告
通常被认为是IP的一部分，体系上位于IP之上，其内容作为IP报文的有效载荷
报文中包含一个类型字段和一个编码字段，包含引发该ICMP的IP的首部和前8个字节

这些报文可被用于探测，例如Traceroute程序利用ICMP来探测路由器的名字与IP地址

网络管理和SNMP

定义是一个冗长的单句：

网络管理框架

网络管理关键组件
网络管理关键组件

如上图，关键组件包括：

  • 管理服务器：控制网络管理信息的收集、处理、分析与显示，由人类控制
  • 被管设备：被管理的真实设备，有若干个被管对象组成，被管对象包括实际硬件与配置参数
  • MIB：位于一个被管设备中收集被管对象的关联信息的数据库，其每个对象由SMI语言定义
  • 网络管理代理：运行在被管设备中的进程，用于与管理服务器通信
  • 网络管理协议：运行在管理服务器和被管设备之间的协议，为管理者提供了相应操作的能力

SNMP

一种网络管理协议，最常用的是请求响应模式，即管理服务器向代理发送请求，通常用于检索或修改MIB对象。其次可被用于代理向管理服务器发送陷阱报文，通知服务器有异常情况导致了MIB对象的改变

SNMP的PDU通过UDP传输，超时重传由管理服务器决定

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。