Computer Network Notes 5：Network Layer (2)

Posted on Edited on In , Symbols count in article: 7.1k Reading time ≈ 6 mins.
把老师的 PPT 变成 md 文件之计算机网络第四章网络层：控制平面

路由选择算法

路由协议

路由协议的目标：确定从发送主机到接收主机之间，通过路由器的网络 “较好” 的路径 (等价于路由器的序列)

  • 路径：路由器的序列，分组会沿着该序列从源主机到达最后的目标主机
  • “较好”：最小代价、最快的、最不拥塞
  • 一个路由器到另一个路由器的最佳路径

路由 (route)

路由：按照某种指标 (传输延迟、所经过的站点数目等) 找到一条从源节点到目标节点的较好路径

  • 较好路径：按照某种指标较小的路径
  • 指标：站数、延迟、费用、队列长度等，或者是一些单纯指标的加权平均
  • 采用什么样的指标，标示网络使用者希望网络在什么地方表现突出，什么指标完了过使用者比较重视

路由器 - 路由器之间的最优路径 = 主机对之间的最优路径

  • 路由器连接子网，子网到路由器之间的跳数只有一跳，必须要走
  • 路由器到下一跳路由器 (节点到节点) 之间的最优路径也就是从源子网向目标子网所有主机对之间的最优路径
  • 大大降低路由计算的规模
  • 在路由计算中按照子网到子网的路径计算为目标，而不是主机到主机

路由选择算法 (routing algorithm)：网络层软件的一部分，完成路由功能

最优化原则 (optimality principle)

汇集树 (sink tree)

  • 此节点到所有其它节点的最优路径形成的树
  • 路由选择算法就是为所有路由器找到并使用汇集树

路由选择算法的原则

  • 正确性 (correctness)：算法必须是正确的、完整的，使分组一站一站接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项，没有处理不了的目标站地址
  • 简单性 (simplicity)：算法在计算机上应简单；最优但复杂的算法延迟大，不实用，不应为了获取路由信息增加很多通信量
  • 健壮性 (robustness)：算法应能适应通信量和网络拓扑的变化；通信量变化，网络拓扑的变化算法能很快适应；不向很拥挤的链路发数据，不向断了的链路发数据
  • 稳定性 (stability)：产生的路由不应该摇摆
  • 公平性 (fairness)：对每一个站点都公平
  • 最优性 (optimality)：某一个指标的最优，时间、费用等指标，或综合指标；实际上，获取最优的结果代价较高，可以是次优的

路由算法分类

全局或局部路由信息

全局：

  • 所有的路由器拥有完整的拓扑和便的代价的信息
  • link state 算法

分布式：

  • 路由器只知道与它又物理连接关系的邻居路由器，和到相应邻居路由器的代价值
  • 迭代地与邻居交换路由信息、计算路由信息
  • distance vector 算法

静态或动态

静态：路由随时间变化缓慢

  • 非自适应路由选择算法 (non-adaptive algorithm)：不能适应网络拓扑和通信量的变化，路由表是事先计算好的

动态：路由变化很快；周期性更新，根据链路代价的变化而变化

  • 自适应路由选择算法 (adaptive algorithm)：能适应网络拓扑和信息量的变化

配置 LS 路由选择算法的路由工作过程

  • 个点通过各种渠道获得整个网络拓扑，网络中所有链路代价等信息 (与算法本身没有关系，属于协议和实现)
  • 使用 LS 路由算法，计算本站点到其它站点的最优路径 (汇集树)，得到路由表
  • 按照此路由表转发分组 (datagram 方式)
    • 严格意义上说不是一个路由的步骤
    • 分发到输入端口的网络层

获得网络拓扑和链路代价信息 -> 是用最短路由算法得到路由表 -> 使用此路由表

LS 路由的基本工作过程

  1. 发现相邻节点，获知对方网络地址
    • 一个路由器上电之后，向所有线路发送 HELLO 分组
    • 其它路由器收到 HELLO 分组，回送应答，在应答分组中告知自己的名字 (全局唯一)
    • 在 LAN 中，通过广播 HELLO 分组获得其它路由器信息，可以认为引入一个人工节点
  2. 测量到相邻节点的代价 (延迟、开销)
    • 实测法，发送一个分组要求对方立即响应
    • 会送一个 ECHO 分组
    • 通过测量时间可以估算出延迟情况
  3. 组装一个 LS 分组，描述它到相邻节点的代价情况
    • 发送者名称
    • 序号、年龄
    • 列表：给出它相邻节点，而它到相邻节点的延迟
  4. 将分组通过扩散的方法发到所有其它路由器
    • 顺序号：用于控制无穷的扩散，每个路由器都记录 (源路由器，顺序号)，发现重复或老的就不扩散
      具体问题：
      • 循环使用问题
      • 路由器崩溃之后序号从 0 开始
      • 序号出现错误
    • 解决问题的办法：年龄字段 (age)
      • 生成一个分组时，年龄字段不为 0
      • 每隔一段时间， AGE 字段减 1
      • AGE 字段为 0 的分组将被抛弃
    • 扩散分组的数据结构
      • Source：从哪个节点收到 LS 分组
      • Seq，Age：序号，年龄
      • Send flags：发送标记，必须向指定的哪些相邻站点转发 LS 分组
      • ACK flags：本站点必须向那斜相邻站点发送应答
      • DATA：来自 source 站点的 LS 分组
      • eg. 节点 B 的数据结构

以上 4 步让每个路由器获得拓扑和边代价
5. 通过 Dijkstra 算法找出最短路径 (这一步才是路由算法)

  • 每个节点独立算出来到其它节点 (路由器 = 网络) 的最短路径
  • 迭代算法：第 k 步能够直到本节点到 k 个其它节点的最短路径

LS 的应用情况

  • OSPF 协议是一种 LS 协议，被用于 Internet 上
  • IS-IS (intermediate system - intermediate system)：被用于 Internet 主干中，Netware

算法复杂度：n 节点

  • 每一次迭代：需要检查所有不在永久集合 N 中节点
  • n(n+1)/2 次比较：O(n2)
  • 有效实现时：O(nlogn)

可能带来路径震荡：链路代价 = 链路承载的流量

距离矢量路由选择 (distance vector routin)

基本思想：

  • 各路由器维护一张路由表
  • 各路由器与相邻路由器交换路由表
  • 根据获得的路由信息，更新路由表

代价及相邻节点减代价的获得

  • 跳数 (hops)，延迟 (delay)，队列长度
  • 相邻节点间代价的获得：实测

路由信息的更新

  • 根据实测，得到本节点 A 到相邻站点的代价 (如延迟)
  • 根据各相邻站点声称它们到目标站点 B 的代价
  • 计算出本站点 A 经过各相邻站点到目标站点 B 的代价
  • 找到一个最小的代价和相应的下一个节点 Z，到达节点 B 经过此节点 Z，并且代价为 A-Z-B 的代价
  • 其它所有的目标节点都使用上述算法

距离矢量算法

  • Dx(y) = 节点 x 到 y 代价最小值的估计
    • x 节点维护距离矢量 Dx = [Dx(y): y ∈ N]
  • 节点 x：
    • 知道到所有邻居 v 的代价：c(x,v)
    • 收到并维护一个它邻居的距离矢量集
    • 对于每个邻居，x 维护 Dv = [Dv(y): y ∈ N]
  • 核心思路：
    • 每个节点都将自己的距离矢量估计值传送给邻居，定时或者 DV 有变化时，让对方去算
    • 当 x 从邻居收到 DV 时，自己运算，更新它自己的距离矢量
      • 采用 B-F equation
    • Dx(y) 估计值最终收敛于实际的最小代价值 dx(y)
      • 分布式、迭代算法

异步式、迭代：每次本地迭代被以下事件触发

  • 本地链路代价变化
  • 从邻居收到 DV 的更新消息

分布式：

  • 每个节点只是在自己的 DV 改变之后向邻居通告
  • 邻居在有必要时通知它们的邻居

DV 的无穷计算问题

  • DV 的特点：好消息传得快，坏消息传得慢
  • 好消息的传播以每一个交换周期前进一格路由器的速度进行
    • 好消息：某个路由器接入或有更短的路径
  • 坏消息传播速度非常慢 (无穷计算问题)
  • 水平分裂 (split horizon) 算法：一种对无穷计算问题的解决方法
    • 在某些拓扑形式下会失败 (存在环路)

LS 和 DV 算法比较

消息复杂度：DV 优

  • LS：有 n 个节点，E 条链路，发送报文 O(nE)个
    • 局部的路由信息，全局传播
  • DV：只和邻居交换信息
    • 全局的路由信息，局部传播

收敛时间：LS 优

  • LS：O(n2)
    • 有可能震荡
  • DV：收敛较慢
    • 可能存在路由环路
    • count-to-infinity 问题

健壮性：LS 优

  • LS：
    • 节点会通告不正确的链路代价
    • 每个节点只计算自己的路由表
    • 错误信息影响较小，局部，路由较健壮
  • DV：
    • DV 节点可能会通告对全网所有节点的不正确路径代价 (距离矢量)
    • 每一个节点的路由表可能被其它节点使用 (错误可以扩散到全网)

自治系统内部的路由选择 (内部网关协议)

RIP: Routing Information Protocol

基于 Distance Vector 算法

  • 距离矢量：每条链路 cost = 1，# of hops (max = 15 hops) 跳数
  • DV 每隔 30 秒和邻居交换 DV，通告
    • 定期，而且在改变路由时发送通告报文
    • 在对方的请求下可以发送通告报文
  • 每个通告包括：最多 25 个目标子网
    • 目标网络 + 跳数

链路失效和恢复

如果 180 秒没有收到通告信息 -> 邻居或者链路失效

  • 发现经过这个邻居的路由已失效
  • 新的通告报文会传递给邻居
  • 邻居因此发出新的通告 (如果路由变化)
  • 链路失效快速在整网中传播
  • 使用毒性逆转 (poison reverse) 阻止 ping-pong 回路 (不可达的剧里：跳数无限 = 16 段)

进程处理

RIP 以应用进程的方式实现：route-d (daemon)
通告报文通过 UDP 报文传送，周期性重复
网络层的协议使用了传输层的服务，以应用层实体的方式实现

OSPF: Open Shortest Path First

open：标准可公开获得
使用 LS 算法：

  • LS 分组在网络中 (一个 AS 内部) 分发
  • 全局网络拓扑、代价在每一个节点中都保持
  • 路由计算采用 Dijkstra 算法

OSPF 通告信息中携带：每一个邻居路由器一个表项
通告信息会传遍 AS 全部 (通过泛洪)

  • 在 IP 数据包上直接传送 OSPF 报文，而不是通过 UDP 和 TCP

IS-IS 路由协议：几乎和 OSPF 一样

OSPF “高级” 特性 (在 RIP 中没有)

安全：所有的 OSPF 报文都是经过认证的 (防止恶意攻击)
允许有多个代价相同的路径存在 (RIP 协议中只有一个)
对每一个链路，对不同的 TOS 有多重代价矩阵

  • eg. 卫星链路代价对于尽力而为的服务代价设置比较低，对实时服务代价设置的比较高
  • 支持按照不同代价计算最优路径，如按照时间和延迟分别计算最优路径

对单播和多播的集成支持：Multicast OSPF (MOSPF) 使用相同的拓扑数据库，就像在 OSPF 中一样

层次性的 OSPF 路由

在大型网络中支持层次性 OSPF

2 个级别的层次性：本地，骨干

  • 链路状态通告仅仅本地区与 Area 范围内进行
  • 每一个节点拥有本地区域的拓扑信息：关于其它区域，知道去它的方向，通过区域边界路由器 (最短路径)

区域边界路由器：“汇总 (聚集)” 到自己区域内网络的距离，向其它区域边界路由器通告
骨干路由器：仅仅在骨干区域内，运行 OSPF 路由
边界路由器：连接其它的 AS’s


ISP 之间的路由选择：BGP

一个平面的路由

平面路由

  • 一个网络中的所有路由器的地位一样
  • 通过 LS、DV 或其它路由算法，所有路由器都要知道其它所有路由器 (子网) 如何走
  • 所有路由器在一个平面

平面路由的问题

  • 规模巨大的网络中，路由信息的存储、传输和计算代价巨大
    • DV：距离矢量很大，且不能够收敛
    • LS：几百万个节点的 LS 分组的泛洪传输，存储以及最短路径算法的计算
  • 管理问题
    • 不同的网络所有者希望按照自己的方式管理网络
    • 希望对外隐藏自己网络的细节
    • 希望和其它网络互联

层次路由

层次路由：将互联网分成一个个 AS (路由器区域)

  • 某个区域内的路由器集合，autonomous systems (AS)
  • 一个 AS 用 AS Number (ASN) 唯一标示
  • 一个 ISP 可能包括 1 个或多个 AS

路由变成了 2 个层次路由

  • AS 内部路由：在同一个 AS 内路由器运行相同的路由协议
    • intra-AS routing protocol：内部网关协议
    • 不同的 AS 可能运行不同的内部网关协议，如 RIP、OSPF、IGRP
    • 能够解决规模和管理问题
    • 网关路由器：AS 边缘路由器，可以连接到其它 AS
  • AS 间运行 AS 间路由协议
    • inter-AS routing protocol：外部网关协议
    • 解决 AS 之间的路由问题，完成 AS 之间的互联互通

层次路由优点

  • 解决了规模问题
    • 内部网关协议解决：AS 内部数量有限的路由器互相到达的问题，AS 内部规模可控
      • 如 AS 节点太多，可分割 AS，使得 AS 内部节点数量有限
    • AS 之间的路由规模问题
      • 增加一个 AS，对于 AS 之间的路由从总体上来说只是增加了一个节点 = 子网 (每个 AS 可以用一个点来表示)
      • 对于其他 AS 来说只是增加了一个表项，即新增的 AS 如何走的问题
      • 扩展性墙：规模增大，但性能不会减得太多
  • 解决了管理问题
    • 各个 AS 可以运行不同的内部网关协议
    • 可以使自己网络的细节不向外透露

互联网 AS 间路由：BGP

BGP (Border Gateway Protocol)：自治区域间路由协议 “事实上的” 标准
BGP 提供给每个 AS：

  • eBGP：从相邻的 ASes 哪里获得子网可达信息
  • iBGP：将获得的子网可达信息传遍 AS 内部的所有路由器
  • 根据子网可达信息和策略来决定到达子网的 “好” 路径

允许子网向互联网其它网络通告 “我在这里”
基于距离矢量算法 (路径矢量)：不仅是距离矢量，还包括到达哥哥目标网络的详细路径 (AS 序号的列标)，能够避免简单 DV 算法的路由环路问题

网关路由器同时运行 eBGP 和 iBGP 协议

BGP 基础

BGP 会话：2 个 BGP 路由器 (peers) 在一个半永久的 TCP 连接上交换 BGP 报文：

  • 通告向不同目标子网前缀的 “路径” (BGP 是一个 “路径矢量” 协议)

路径的属性 & BGP 路由

当通告一个子网前缀时，通告包括 BGP 属性

  • prefix + attributes = route

两个重要属性：

  • AS-PATH：前缀的通告所经过的 AS 列标：AS 67 AS 17
    • 检测环路：多路径选择
    • 在向其它 AS 转发时，需要将自己的 AS 号加在路径上
  • NEXT-HOP：从当前 AS 到下一跳 AS 有多个链路，在 NEXT-HOP 属性中，告诉对方通过哪个 I 转发
  • 其它属性：路由偏好志保，如何被插入的属性

基于策略的路由：

  • 当一个网关路由器接收到一个路由通告，使用输入策略来接收或过来 (accept/decline)
    • eg. 不想经过某个 AS，转发某些前缀的分组
    • eg. 已经有了一条往某前缀的偏好路径
  • 策略决定了是否向它的邻居通告收到的这个路由信息

BGP 路径通告

BGP 报文

使用 TCP 协议交换 BGP 报文
BGP 报文：

  • OPEN：打开 TCP 连接，认证发送方
  • UPDATE：通告新路径 (或撤销原路径)
  • KEEPALIVE：在没有更新时保持连接，也用于对 OPEN 请求确认
  • NOTIFICATION：报告以前消息的错误，也用来关闭连接

BGP 路径选择

路由器可能获得一个网络前缀的多个路径，路由器必须进行路径的选择，路由选择可基于：

  • 本地偏好值属性：偏好策略决定
  • 最短 AS-PATH：AS 的跳数
  • 最近的 NEXT-HOP 路由器：热土豆路由
  • 附加的判据：使用 BGP 标示

一个前缀对应着多种路径，采用消除规则直到留下一条路径

为什么内/外部网关协议如此不同

策略：

  • Inter-AS：管理员需要控制通信路径，谁在使用它的网络进行数据传输
  • Intra-AS：一个管理者，无需策略；AS 内部的各子网的主机进肯能地利用资源进行快速路由

规模：

  • AS 间路由必须考虑规模问题，以便支持全网的数据转发
  • AS 内部路由规模不是大问题
    • 如果 AS 太大，可继续分为小的 AS，规模可控
    • 或 AS 内部路由支持层次性，层次性路由节约表空间，降低更新数据流量

性能：

  • Intra-AS：关注性能
  • Inter-AS：策略比性能更重要

SDN 控制平面

Software Defined Networking (SDN)

逻辑上集中的控制平面
一个不同的 (通常是远程的) 控制器与本地控制代理 (CAs) 交互

逻辑上集中的控制平面：网络管理更容易；基于流表的转发，允许 “可编程” 的路由器；控制平面的开放实现

SDN 特点

通用 “flow based”，基于流的匹配 + 行动
控制平面和数据平面分离
控制平面功能在数据交换设备之外实现
可编程控制应用，在控制器之上以网络应用形式实现各种网络功能

SDN 架构

数据平面交换机

快速、简单、商业化交换设备，采用硬件实现通用转发功能
流表被控制器计算和安装
基于南向 API (如 OpenFlow)，SDN 控制器访问基于流的交换机：定义了哪些可以被控制，哪些不能
定义了和控制器的协议 (如 OpenFlow)

SDN 控制器 (网络 OS)

维护网络状态信息
通过上面的北向 API 和网络控制应用交互
拖过下面的南向 API 和网络交换机交互
逻辑上集中，但在实现上通常由于性能、可扩展性、容错性以及鲁棒性采用分布式方法实现

网络控制应用

控制的大脑：采用下层提供的服务 (SDN 控制器提供的 API)，实现网络功能

  • 路由器 交换机
  • 接入控制 防火墙
  • 负载均衡
  • 其它功能

非绑定：可以被第三方提供，与控制器厂商通常上可以不同，与分组交换机厂商也可以不同

OpenFlow：控制器-交换机报文

关键的控制器到交换机的报文：

  • 特性：控制器查询交换机特性，交换机应答
  • 配置：交换机查询/设置交换机的配置参数
  • 修改状态：增加删除修改 OpenFlow 表中的流表
  • packet-out：控制器可以将分组通过特定的端口发出

关键的交换机到控制器的报文：

  • 分组进入：将分组 (和他的控制) 传给控制器，见来自控制器的 packet-out 报文
  • 流移除：在交换机上删除流表项
  • 端口状态：报告控制器端口的变化

网络管理员不需要直接通过创建/发送流表来变成交换机，可采用控制器上的 app 自动运算和配置

OpenDaylight (ODL) 控制器

ODL lithium 控制器
网络应用可以在 SDN 控制内或外面
服务抽象层 SAL：和内部以及外部应用以及服务进行交互

ONOS 控制器

控制应用和控制器分离 (应用 app 在控制器外部)
意图架构服务的高级规范：描述什么，而不是如何
相当多的重点聚焦在分布式核心上，以提高服务的可靠性、性能的可扩展性

SDN 的挑战

强化控制平面：可靠、可信、性能可扩展性、安全的分布式系统

  • 对于失效的鲁棒性：利用为控制平面可靠分布式系统的强大理论
  • 可信任、安全：从开始就进行铸造

网络、协议满足特殊任务的需求

  • eg. 实时性、超高可靠性、超高安全性

互联网络范围内的扩展性

  • 全网部署，而不是仅仅在一个 AS 内部部署