SDN：逻辑上集中的控制平面

一个不同的（通常是远程）控制器和CA交互，控制器决定分组
转发的逻辑（可编程），CA所在设备执行逻辑。

SDN的主要思路

• 网络设备数据平面和控制平面分离
• 数据平面-分组交换机
  • 将路由器、交换机和目前大多数网络设备的功能进一步抽象成：按照流表（由控制平面设置的控制逻辑）进行PDU帧、分组）的动作（包括转发、丢弃、拷贝、泛洪、阻塞）
  • 统一化设备功能：SDN交换机（分组交换机），执行控制逻辑

SDN控制平面和数据平面分离的优势

• 水平集成控制平面的开放实现（而非私有实现），创造出好的产业生态，促进发展
• 集中式实现控制逻辑，网络管理容易
• 基于流表的匹配+行动的工作方式允许“可编程的”分组交换机
  网络操作系统上的应用可以收集信息。计算流表，按照南向接口来下发流表，网络可编程。通过网络操作系统上的网络应用，编程结果，形成流表，通过数据平面和控制平面的南向接口，将流表下发给分组交换机。南向接口将分组交换机当前控制器上报给SDN控制器

SDN 架构: 数据平面交换机

数据平面交换机

• 快速，简单，商业化交换设备采用硬件实现通用转发功能
• 流表被控制器计算和安装
• 基于南向API（例如OpenFlow），SDN控制器访问基于流的交换机
• 也定义了和控制器的协议 (e.g., OpenFlow)

路由选择算法

路由(route)的概念

• 路由：按照某种指标（传输延迟，所经过的站点数目等）找到一条从源节点到目标节点的较好路径。（一个路由器到另一个路由器）

最优化原则(optimality principle)

• 汇集树
  - 此节点到所有节点的最优路径形成的树
  - 路由选择算法就是为所有路由器找到并使用汇集树
  
  不可能会出现回路

路由的原则

• 路由选择算法的原则
  • 正确性（correctness）：算法必须是正确且完整的，能够正确找到目标站，在路由表中都能找到完整的表项
  • 简单性（simplicity）：最优但是复杂的算法，时间延迟大，不实用
  • 健壮性（robustness）：算法能够适应通信量和网络拓扑的变化

路由算法的分类

全局或者局部路由信息？
全局：

• 所有的路由器拥有完整的拓扑和边的代价信息
• “link state”算法
  分布式（各邻居到其它子网的信息，在我自己这里做一个汇集）：
• 路由器只知道与它物理连接关系的邻居路由器，和到相应邻居路由器的代价值
• 迭代地与邻居交换路由信息，计算路由信息
• “distance vector”算法
  静态还是动态的？
  静态：
• 路由随时间变化缓慢
  动态：
• 路由变化很快
  • 周期性更新
  • 根据链路代价的变化而变化
    非自适应算法(non-adaptive algorithm)：不能适应网络拓扑和通信量的变化,路由表是事先计算好的
    自适应路由选择(adaptive algorithm)：能适应网络拓扑和通信量的变化

LS路由工作过程（相当于一个上帝）

• 配置LS路由选择算法的路由工作过程
• 各点通过各种渠道获得整个网络拓扑, 网络中所有链路代价等信息（这部分和算法没关系，属于协议和实现）
• 使用LS路由算法，计算本站点到其它站点的最优路径(汇集树),得到路由表
  

链路状态路由选择(link state routing)

• LS路由的基本工作过程
  1.发现相邻节点,获知对方网络地址
  

  2.测量到相邻节点的代价(延迟,开销)
  

  3.组装一个LS分组,描述它到相邻节点的代价情况
  

  4.将分组通过扩散的方法发到所有其它路由器以上4步让每个路由器获得拓扑和边代价
  
  

  5.通过Dijkstra算法找出最短路径（这才是路由算法）
  
  

• 有两类节点

  • 临时节点(tentative node) :还没有找到从源节点到此节点的最优路径的节点
  • 永久节点(permanent node) N’:已经找到了从源节点到此节点的最优路径的节点

• 初始化

  • 除了源节点外,所有节点都为临时节点
  • 节点代价除了与源节点代价相邻的节点外,都为∞

• 从所有临时节点中找到一个节点代价最小的临时节点,将之变成永久节点(当前节点)W

• 对此节点的所有在临时节点集合中的邻节点(V)

• 开始一个新的循环

例;

Dijkstra算法的讨论

算法复杂度: n节点

• O(n2)
  
  后面可能轻载变拥塞，变成重载路径。

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

• 动态路由算法之一
• 每个节点定期测量与邻居距离矢量，选代价最小的。
• 代价及相邻节点间代价的获得
  • 跳数(hops), 延迟(delay),队列长度
  • 相邻节点间代价的获得：通过实测
• 路由信息的的更新
  找到一个最小的代价，和相应的下一个节点Z，到达节点B经过此节点Z，并且代价为A-Z-B的代价
  
  
  

距离矢量算法

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

• 我到邻居链路代价发生变化
• 邻居将距离矢量传给我，这个距离矢量变化了，就导致我对距离矢量做迭代更新。
  分布式：
• 每个节点只是在自己的DV改变之后向邻居通告

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

• DV的特点
  好消息传得快，坏消息传得慢。
  • 好消息:某个路由器接入或有更短的路径
  • 坏消息的传播速度非常慢(无穷计算问题）可能形成环路