计算机与网络（五）---- 网络层：控制平面

1.路由

路由协议的目标：确定从发送主机到接受主机之间，通过路由器的网络“较好”（最小代价、最快的、不拥塞）的路径
路由器-路由器之间的最优路径=主机之间的最优路径
路由选择算法：

路由器的集合:N=

链路集合:E={(u,x),(u,y)…},每条边都有代价

路由算法就是找到节点u-节点z的最小代价路径
- 最优化原则：
  - 汇集树：此节点到所有其他节点的最优路径形成的树，路由选择算法就是为所有路由器找到并使用汇集树
- 路由的原则：
  - 正确性：算法必须是正确和完整的
  - 简单性
  - 健壮性：能够适应网络拓扑和通信量的变量
  - 稳定性：产生的路由不能摇摆
  - 公平性：对每一个站点都公平
  - 最优性：综合指标最优
路由选择算法的分类
- 全局路由选择算法（集中式路由选择算法）：用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径，即知道所有节点之间的连通性以及链路的开销，也被称为链路状态算法（LS算法）。
- 分布式路由选择算法（分散式路由选择算法）：路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路的开销信息。
- 静态路由算法：与动态路由相反。
- 动态路由算法：随着网络流量负载或拓扑发生变化而改变的路由选择路径，比如距离矢量路由选择算法。
- 负载敏感算法：链路开销会反映底层链路的拥塞水平，路由选择会避开拥塞的链路
- 负载迟钝算法：与敏感相反。大部分路由算法都是负载迟钝的，因为某条链路的开销不明确的反应其当前的拥塞水平。
LS算法的工作过程：
1. 发现相邻节点，获知对方网络地址
2. 测量相邻节点代价
3. 组装LS分组，用于描述相邻节点的代价情况
4. 将分组通过扩散的方式发送给其他路由器，由此每个路由器获得了拓扑和边的代价
5. 通过**Dijkstra算法**找出最短路径
OSPF协议就是一种LS算法
距离矢量路由选择算法（DV算法）
- 各路由器维护一张路由器表
  
  To（目标） Next（下一个） Cost
  
  A Z 14
- 各路由器与相邻路由器交换路由表
- 根据获得的路由信息，更新路由表

To（目标）	Next（下一个）	Cost
A	Z	14

DV算法与LS算法比较

	消息复杂度	健壮性	收敛时间
LS	有n个节点，E条链路，发送O(nE)个报文	节点会通告不正确的链路代价，每个节点只计算自己的路由表，错误信息影响小	有可能发生路由震荡（由于链路的开销代价发生变化，导致路由的路径不一样）
DV	只和邻居交换信息	DV节点可能通告对全网所有节点的不正确路径代价，每一个节点的路由表可能被其他节点使用	可能存在路由环路问题

2.因特网中自治系统内部的路由选择

自治系统：随着路由器数目变得很大，涉及路由选择信息的通信、计算和存储的开销将高得不可实现。并且由于因特网是ISP的网络，每个ISP都有自己的路由器网络，ISP通常希望按自己的意愿运行路由器。通过将路由器组织进自制系统(Autonomous System，AS)来解决这两个问题。通常在一个ISP中的路由以及互联它们的链路组成一个自制系统。
RIP(Routing Information Protocol)：
- 使用DV算法，在邻居之间每30秒交换通告报文，每个通告在AS中至多25个目标网络的DV。
- 如果180秒没有收到通告信息，则表明邻居或者链路失效
- 采用UDP报文（网络层采用进程的方式，使用运输层的协议来实现自己的功能）
OSPF(开放最短路优先)：
- 使用LS算法
- 通告信息中携带：每一个邻居路由器一个表项
- 通告信息会传遍AS内部（通过泛洪）
- 特性：
  - 安全：所有的OSPF报文都是经过认证的
  - 允许有多个代价相同的路径存在
  - 对于每个链路，可以有多重代价矩阵
  - 在大型网络中支持层次性OSPF

3.ISP之间的路由选择

各个自治系统之间的路由选择

BGP边界网关协议：BGP协议提供给每个AS以下方法：
- eBGP：从相邻的ASes那里获得子网可达信息
- iBGP：将获得的子网可达信息传遍AS内部的所有路由器
- 根据子网可达信息和策略来决定到达子网的路径
- 允许子网向其他网络通告
- 基于DV算法，不仅仅有到各个AS的代价，还包括了到AS的详细路径
- 使用TCP连接

4.SDN控制平面

历史上都是由分布式、每个路由器实现控制平面功能。单个路由器包含了：交换设备硬件、私有路由协议和运行的互联网协议标准的实现。
传统方式：在每一个路由器中的单独路由器算法控件，在控制平面进行交互。
SDN方式：逻辑上集中的控制平面，一个不同的（远程）控制器与本地控制器代理（CA）交互
SDN的优点：
- 网络管理更加容易：避免路由器的错误配置
- 基于流表的转发（OpenFlow协议），允许“可编程”的路由器
- 控制平面的开放实现