计网笔记_5

第5章 网络层：控制平面

5.1 导论

传统方式：根据路由信息怎么算路由表；

SDN方式。

5.2 路由选择算法

Link state链路状态算法 & distance vector距离矢量算法

路由协议的目标：如何在网状网中，找到一条比较好的路径，跳数尽量少，所以以子网为单位减少路由表的计算和路由转播的压力很重要。

路由route的概念：

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

因为以子网为单位传输数据，而源主机所在的子网只需要交换机就可以分发到第一个路由，最后一个子网中也只需要交换机就可以从最后一个路由到目标主机，所以在节约路由表计算的同时，还把主机到主机的数据交换简化为了寻找网络中路由到路由的最佳路径问题。

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

大大减少了路由计算的规模。

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

最优化原则optimality principle：

汇集树sink tree：

此节点到所有其他节点的最优路径形成的树，由于取最优，所以只能是树；

路由选择算法就是为所有路由器找到并使用汇集树。

路由的原则：

路由选择算法的原则：

正确性correctness；简单性simplicity；健壮性/鲁棒性robustness；

稳定性stability；公平性fairness；最优性optimality。

路由算法分类：全局或局部路由信息：

全局：link state算法

所有的路由器拥有完整的拓扑和边的代价的信息；

分布式：distance vector算法

路由器只知道与它有物理连接关系的邻居路由器，和到对应邻居路由器的代价值；

迭代地与邻居交换路由信息、计算路由信息。

现在基本都是动态的。

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

各点通过各种渠道获得整个网络的拓扑（上帝视角），网络中所有链路代价等信息（这部分和算法没关系，属于协议和实现）；

使用LS路由算法，计算本站点到其他站点的最优路径（汇集树），得到路由表；

按照此路由表转发分组（datagram方式）。

链路状态路由选择link state routing：

LS路由的基本工作过程：

1.     发现相邻节点，获知对方网络地址；

2.     测量到相邻节点的代价（延迟，开销）；

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

4.     将分组通过扩散的方法，泛洪发到所有其他路由器（得带上类似ttl的字段，或者版本号，预防在网络中产生广播风暴）；

（以上四步让每个路由器获得拓扑和边代价，上帝视角）

5.     通过Dijkstra算法找出最短路径（这才是路由算法，传统Dijkstra复杂度为n^2，较好的实现方式的话，可以降低到nlogn）：

每个节点独立算出来到其他节点（路由器=网络）的最短路径（汇集树）；

迭代算法：第K步能够知道本节点到K个其他节点的最短路径。

链路状态路由选择的工作流程：

初始化：

除源节点外，所有节点都为临时节点；

节点代价除了与源节点代价相邻的节点外，都记为无穷；

从所有临时节点中找到一个节点代价最小的临时节点，将之标记为永久节点（当前节点）W；

对此节点的所有在临时节点集合中的邻节点（V）：

如果D(V) > D(W) + C(W, V)，则重新标注此点，(D(W) + C(W, V), W)；

否则，不重新标注。

开始一个新的循环。

距离矢量路由选择distance vector rating

动态路由选择算法之一。DV和LS。

距离矢量路由选择算法的主要思想：

各路由器维护一张路由表；

各路由器与相邻路由器交换路由表；

根据获得的路由信息，更新路由表。

Distance vector中，每个节点的邻节点都告诉该节点彼此之间的代价（通过交换距离矢量），形成一张表，在网络中迭代，取得最小值，和相应的下一跳，这样获得最短路径。

距离矢量算法是一种动态规划问题（过一阵子算法笔记里会写），Bellman-Ford方程：

（这是一个分布式的迭代算法）

d_x(y) = min{c(x, v) + d_v(y)}, d_x(y)表示从x到y的最小路径代价。

特性：好消息传得快，坏消息传得慢。

好消息：链路代价变小，无需重新迭代新的最短路径，直接按原路接着传，速度变快；

坏消息：链路前面的代价变大，或者链路断掉，这样后面的节点仍然认为自己可达目标节点，向源节点申请，但是节点收到分组之后，其实还是传回那个代价增大甚至断掉的节点，就会形成环路，需要再次迭代，耗费时间。

LS和DV算法的比较：

消息复杂度：DV小，只和邻居节点交换分组消息，而LS算法中，若有n个节点E条链路，每个节点要发送nE个分组，在全网范围内泛洪，每个路由都尽量给所有路由都发一个分组；

收敛时间：LS快，复杂度为n^2，可以降到nlogn，而DV因为需要迭代计算，收敛速度很慢，而且有可能存在路由环路（坏消息传得慢），也有可能有count-to-infinity问题。

健壮性/鲁棒性：LS更好，每个节点都只计算自己的路由表，错误信息影响小；而DV中，一个节点的错误信息会被所有邻居获取利用，若路由表被其他节点使用，节点出错的影响可能会扩散到全网。

所以不能全网直接使用LS或DV，运算量太大，管理起来也很困难，需要把整个网络分成两个层面，在把网络划分为一个个小区域/自治区域之后，就只需要解决自治区域之内和自治区域之间的路由选择。分块解决，就可以满足功能和规模的需要。

5.3   自治系统内部的路由选择

自治区域内的路由选择协议：RIP、OSPF

RIP（routing information protocol）路由信息协议：

DV算法中，限制最大跳数，规定每过30s和邻居交换一次DV，通告advertisements，每个通告包括最多25个目标子网，在对方的请求下也可以发通告。

如果180s没收到通告，则认为邻居宕机或者链路断路，发送新的通告给邻居，更换路径，然后消息逐渐传遍整个网络，最大跳数为。

RIP在网络层，采用应用层的进程的方式实现，route-d(daemon)，使用传输层的UDP协议进行报文发送，周期性重复。

OSPF（Open Shortest Path First）开放式最短路径优先：

高级特性（RIP没有的）：

安全：所有OSPF报文都是经过认证的，防止恶意攻击；

允许多个代价相同的路径存在，RIP中只允许一个；

对于每一个链路，对不同的TOS有多重代价矩阵，按照不同的代价指标（如时间、延迟、跳数和拥塞程度等）分别计算最优路径；

对单播和多播的集成支持：Multicast OSPF (MOSPF) 使用OSPF相同的拓扑数据库；

大型网络支持层次性OSPF，网络很大的话进行分层，大体分为本地和骨干backbone，链路状态通告只在区域内泛洪，限制泛洪范围和数量，区域外的话需要先到backbone，所以需要区分边界路由器和骨干路由器。

5.4 ISP之间的路由选择：BGP

自治区域之间的协议：BGP Border Gateway Protocol边界网关协议。

太多个区域之间如何管理依然是个问题。

BGP是一个“事实上的”标准，大家在长时间的摸索之后达成的一个普遍遵守的规定，最后成了BGP协议，并非某一个组织事先拟定好的。

BGP分两个部分：eBGP external-BGP和iBGP internal-BGP：

eBGP：（AS间）从相邻的ASes获得子网可达信息，通告；

iBGP：（AS内）将获得的子网可达信息传输到AS内部的所有路由器。

BGP会话：两个BGP路由器peers之间建立半永久的TCP连接，之后交换BGP报文。

5.5 SDN控制平面

SDN还是一个在进展中的技术。

网络设备通过南向接口上报状态，SDN控制器的操作系统计算流表再下发，也可以通过南向接口完成修改流表等操作，SDN控制器也可以通过南向接口对网络路由下达指令。

南向接口协议：OpenFlow

网络控制器（0S）：OpenDaylight ODL，ONOS，等。

SDN控制器还可以通过北向接口与其操作系统上的应用做交互。

北向接口目前还没有很统一的协议。

SDN面临的挑战：

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

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

网络、协议满足特殊任务的需求：实时性、超高可靠性、超高安全性等；

互联网网络范围内的扩展性：不只是在一个AS的内部部署，要可以在全网部署。