1、概述
转发表（在基于目的地转发的场景中）和流表（在通用转发的场景中）是链接网络层的数据平面和控制平面的首要元素。
控制平面：这些转发表和流表是如何计算、维护和安装的。
工作的两种方法：每路由器控制（每个路由器里面都要完成转发和路由选择功能）和逻辑集中式控制（匹配加动作抽象）
SDN就采用了逻辑集中式控制。
2、路由选择算法
路由选择算法的天然目标是找出从源到目的地间的最低开销路径。
路由选择算法的分类方法：
- 一、
一般而言，路由选择算法的一种分类方式是根据该算法是集中式还是分散式来划分：
1）集中式路由选择算法：
用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径。集中式算法具有关于连通性和链路开销方面的完整信息。具有全局状态信息的算法通常被称为链路状态算法（LS）
2）分散式路由选择算法：
以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息，每个节点仅有与其直接相连链路的开销知识。例如距离向量算法（DV）的分散式路由选择算法。 - 二、根据算法是静态的还是动态的进行分类：静态路由选择算法（通常是人工进行调整）和动态路由选择算法（反应较快但是也会有存在一些问题）。
- 三、根据是负载敏感还是负载迟钝分为负载敏感算法（链路开销会动态地根据变化以反映出底层链路的当前拥塞水平）和负载迟钝的算法。
2.1链路状态路由选择算法
网络拓扑和所有的链路开销都是已知的。节点会进行广播，结果是所有节点都具有该网络统一的、完整的视图。
Dijkstra算法：
D（v）：到算法的本次迭代，从源节点到目的节点v的最低开销路径的开销
p（v）：从源到v沿着当前最低开销路径的前一节点（v的邻居）
N’：节点子集；如果从源到v的最低开销路径已确知，v在N’中
例子：
如图为一个网络拓扑，其中边上的值代表链路开销。计算从u到所有可能目的地的最低开销路径如下：
第一行：u的直连邻居有xvw，且开销分别是125，而其他的不能达到的节点的开销就是正无穷。所以取最小开销1，将节点x加入N’。
第二行：例如到节点w，原来是u直达w，开销是5，现在v也在N’里面，所以还有第二条就是经过x到w，开销是4，所以取最小的，就是第二条，开销是4，并且这个时候的前一个节点就是x，而不是u了。
下面的计算都是一样的。
在这种算法之下，复杂性是O(N^2)，并且是很容易出现振荡的。这样的话，我们就需要每个节点上算法执行的时机不同。
2.2距离向量路由选择算法
距离向量算法是一种迭代的、异步的和分布式的算法。
分布式：每个节点要从一个或者多个直接相连邻居接收某些信息，执行计算，然后将结果发送给邻居。
迭代的：过程要一直持续到邻居之间没有更多的信息需要进行交换。
异步的：不要求所有节点的运行步伐一致。
令dx(y)是从节点x到节点y的最低开销路径的开销，那么
dx(y)=min{c(x,v)+dv(y)}
也就是从x到y的最低开销是对所有邻居v的c(x,v)+dv(y)的最小值。
DV算法是分布的，每个节点等待邻居的更新。
例子：
如图，最左边一列是厨师路由向量表。节点x将它的距离向量[0,2,7]发送给节点y和z，这样的话，每个节点就可以进行更新：
比如Dx(x)=0
Dx(y)=min{c(x,y)+Dy(y),c(x,z)+Dz(y)}=min{2+0,7+1}=2
Dx(z)=min{c(x,z)+Dz(z),c(x,y)+Dy(z)}=min{7+0,2+1}=3
这个时候x节点的距离向量Dx就会变成[0，2，3]。节点重新计算之后就会向邻居发送更新的距离向量。同理可以更新所有节点的距离向量。
2.3
2.3.1距离向量算法：链路开销改变与链路故障
如图，x和y之间的开销从4变成1，然后就需要进行距离向量的更新，并且对邻居进行通知。那么节点z收到更新报文并且重新计算，得到z到x的最低开销从5变成2。节点y也是如此。之后就进入了静止状态。这就是好消息传得快
但是当x和y之间的开销从4变成60时，如图：
在变化之前，Dy(x)=4 Dy(z)=1 Dz(y)=1 Dz(x)=5
所以在链路开销修改之后，Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+5}=6。在这个时候，从节点y到x的链路选择上，选择了第二条（y到z再到y再到x），这就是路由选择环路。
在Dy(x)更新之后，Dz(x)也可以进行重新计算min{c(z,x)+Dx(x),c(z,y)+Dy(x)}={50+0,1+6}=7，这样就会再往下计算，重新计算Dy(x)，直到最后在min{50,.}的选择中选择了50.。这就是坏消息传的慢。
2.3.2距离向量算法：增加毒性逆转
上文的循环场景可以通过毒性逆转的技术来避免。比如y到z再到y再到x这条路径里面，z就会通告y，它到x的距离是无穷大的，这样的话，y就不会经过z去到达x。所以在链路改变之后Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+无穷}=60，Dz(x)也可以进行重新计算min{c(z,x)+Dx(x),c(z,y)+Dy(x)}={50+0,1+60}=50，这个时候选择的就是从z直接到x，Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+50}=51，所以最后y到x选择的是y到z再到X，而不会再经过y。
2.3.3LS与DV路由选择算法的比较
DV和LS算法采用互补的方法来解决路由选择计算问题。并且DV中每个节点只和它的直接相连的邻居交换，LS算法却需要掌握全局信息。
- 1）报文复杂性：LS算法当一个开销改变时，需要向所有节点都发送这个改变的信息，但是DV只需要邻居之间交换报文。
- 2）收敛速度：LS算法的实现是一个要求O(|N||E|)个报文的O(|N^2|)算法，DV算法收敛很慢，且在收敛时会遇到路由选择环路。
- 3）健壮性：LS会像其连接的链路广播不正确的开销，但是每个节点只用计算自己的转发表，在某些程度上，路由计算是分离的。但是在DV中，一个不正确的节点计算会了扩散到整个网络。
3、因特网中自治系统内部的路由选择：OSPF
自治系统AS，可能希望按照自己的意愿来管理自己这一部分的路由器。
开放最短路有限OSPF：被广泛的应用于因特网的AS内部路由选择。是一种链路状态协议。需要知道全局的信息，来计算出一个以自己为根节点的到所有子网的最短路径树。路由器会向自治系统内所有其他路由器广播路由选择信息，而不仅仅是向其相邻路由广播。
优点：
1）安全：能够鉴别OSPF路由器之间的交换。
2）多条相同开销的路径：允许使用多条相同开销的路径
3）对单播与多播路由选择的综合支持
4）支持在单个AS中的层次结构：一个OSPF自治系统能够层次化的配置多个区域，每个区域都运行自己的OSPF链路状态路由选择算法。
4、ISP之间的路由选择：BGP
AS内使用OSPF协议，但是在AS间进行路由的时候，我们需要一个自治系统间路由选择协议。因为跨过多个AS，所以AS通信必须运行相同的AS间路由协议。在因特网中，所有的AS运行相同的AS间路由选择西医，称为边界网关协议BGP。
4.1BGP的作用
BGP是一种异步的、分布式的协议。
作为一种AS间路由选择协议，BGP为每一台路由器提供了一种完成以下任务的手段：
- 1）从邻居AS获得前缀的可达性信息：BGP确保在因特网中的所有AS都知道这个子网的存在
- 2）确定到该前缀的“最好的”路由：这个最好的路由将基于策略以及可达性信息来确定。
4.2通告BGP路由信息
网关路由器是一台位于AS边缘的路由器；内部路由器仅仅连接在它自己AS中的主机和路由器。
如图，1c，2a就是网关路由器，1b，1d是内部路由器。每条直接连接以及所有通过该连接发送的BGP报文，称为BGP连接。
- eBGP：跨越两个AS的BGP连接成为外部BGP
- iBGP：在相同AS中的两台路由器之间的BGP会话称为内部BGP。
iBGP连接并不总是与物理链路对应
如图，网关3a向2c发送eBGP报文 AS3 x，2c向AS2里面的其他路由器发送iBGP报文AS3 x，然后2a向1c发送eBGP报文 AS2 AS3 x，最好1c向AS1里面的其他路由器发送iBGP报文 AS2 AS3 x。
4.3确定最好的路由
BGP属性：NEXT-HOP（是AS-PATH起始；路由器接口的IP地址）、AS-PATH（包含了通告已经通过的AS的列表）。
如AS2 AS3 x：其中的AS-PATH属性是AS2 AS3，NEXT-HOP属性是路由器2a左边接口的IP地址。
4.3.1热土豆路由选择
“烫手的热土豆”：往往只关心自己，而不考虑全局，只关系以自己为中心的最小开销。也就是选择的路由到开始该路由的NEXT-HOP路由器具有最小的开销。
如图，1b学习有两条路径：AS2 AS3和AS3，第一条中到起始路由器的开销是2（按照链路数来衡量），第二条是3，所以会选择第一条.
在路由器转发表中添加AS外部目的地的步骤：
- 1）从AS间西医学到经多个网关可以到达子网；2）使用来自AS内部协议的路由选择ixnxi，以决定到达每个网关的最低开销路径的开销；3）热土豆路由选择；4）从转发表确定通往最低开销网关的接口I，在转发表中加入表项(x,I)
4.3.2路由器选择算法
选择顺序：
本地偏好值（一个属性，可以由路由器设置也可能由在相同AS中的另一台路由器学习到）——AS-PATH（使用的是AS跳的跳数而不是路由器跳的跳数）——NEXT-HOP（热土豆算法）——BGP标识符
4.4IP任播
如图，使用IP任播将用户引向最近的CDN服务器（最近是由BGP路由选择算法决定的）。其中，这些CDN服务器是相同物理地址的不同路径（类似于映射），例如图中的CDN服务器A和B，虽然是不同的服务器，但是他们通告出去的IP地址是一样的。这就是CDN公司为它的多台服务器指派相同的IP地址。这在DNS里面也被用到。IP任播被DNS系统广泛用于将DNS请求指向最近的根DNS服务器。根域名服务器的IP地址全球只有十几个，但是每个地址都有多个根域名服务器，当一个请求向这几个IP地址发送的时候，会发送给最近的DNS服务器。
4.5路由选择策略
- 桩网络：例如X自身是进入/离开X的所有流量的源/目的地。
- 这种强制实现，就需要BGP路由的通告的控制来实现。例如，X不会通告给BC它有除了自身之外的任何其他目的地路径。同样的，即使B知道AW可以到达A，它会告诉自己的客户W，但是它不会告诉C，不然C就可以经过BAW到达W，这样就让C免费乘车到达W了。
4.6例子
具有若干服务器的小型公司网咯，有一台描述公司产品服务的公共Web服务器，一台获得电子邮件报文的电子邮件服务器和一台DNS服务器。需要任何人可以访问自己的WEB站点获取产品信息进行宣传，并且雇员可以向任何潜在客户进行电子邮件的接收发送。
- 1）获得因特网连接：与本地ISP签订合同进行连接。这样就会有一台网关路由器。本地ISP会为自己提供一个IP地址范围，手下的设备就会有IP地址。
- 2）获取域名：与因特网注册机构签订合同获取域名，我们需要向注册公司提供我们的DNS服务器的IP地址，这样，外部世界才会通过我们的DNS服务器获得我们服务器的IP地址
- 3）在DNS服务器中添加自己的Web服务器的IP地址，让用户可以与我们的web服务器进行TCP连接。这就需要将我们的web服务器主机名映射到它的IP地址。
- 4）用户发送的IP数据报，要经过很多的AS，最终到达WEB服务器。所以每一台路由器都需要知道我们公司的前缀，这就需要BGP进行广播学习。
5、SDN控制平面
SDN的关键特点：
- 1）通过流表来进行动作；SDN控制平面的工作是计算、管理和安装所有网络交换机中的流表项。
- 2）数据平面和控制平面分离开：数据平面由网络交换机组成，控制平面由服务器以及决定和管理交换机流表的软件组成。
- 3）网络控制功能：SDN控制平面由软件实现。控制平面的组件：一个SDN控制器（网络操作系统）和若干个网络控制应用程序。
- 4）可编程网络
互联网的工作模式：传统工作模式（垂直集成、分布式）和SDN（远程、集中式）
如图，SDN控制器通过北向接口与网络控制应用程序连接，通过南向接口与SDN控制的交换机连接。
5.1SDN控制平面：SDN控制器和SDN网络控制应用程序
SDN可以根据很多字段来转发分组。
SDN控制器用来维护整个状态，通过南向接口上报状态，包括链路状态等等，也会通过南向接口下发流表。
控制器的功能：
- 1）通信层：SDN控制器和受控网络设备之间的通信。需要一个协议来传送控制器与其他设备之间的信息（OpenFlow）
- 2）网络范围状态管理层：由SDN控制平面作出的最终控制决定。
- 3）对于网络控制应用程序层的接口：可以通过北向接口与网络控制程序交互，允许其在状态管理层之间读/写网络状态和流表。
5.2OpenFlow协议
运行在SDN控制器和SDN控制的交换机或其他实现OpenFlowAPI设备之间。运行在TCP之上。
5.3数据平面和控制平面交互的例子
如图，当s1和s2的链路断开之后，s1 s3 s4的入和出流转发规则都受到影响。
- 1）s1使用OpenFlow“端口状态：报文向SDN控制器通报该链路状态的更新。
- 2）SDN控制器收到报文并且通告给链路状态管理器，进行更新状态库。
- 3）应用程序收到链路更新的通告。
- 4）链路状态路由选择应用程序与状态管理器相互作用，得到新的链路状态，进行计算最低开销路径
- 5）链路状态路由选择应用与流表管理器交互，流表管理器决定更新的流表
- 6）流表管理器使用OpenFlow协议进行更新。
6、ICMP：因特网控制报文协议
- ICMP被主机和路由器用来彼此沟通网络层的信息。例如在某个位置，IP路由器不能找到一条通往HTTP请求中所指定的主机的路径，这个路由器就会向主机生成并发送一个ICMP报文来指示这个错误。ICMP报文是作为IP有效载荷承载的。
-
- ICMP是源抑制报文。让拥塞的路由器向一个主机发送一个ICMP源抑制报文，以强制这个主机减小发送速率。