一、网络层控制层面
路由选择算法
用无向图来表示网络结构，G=(N，E)表示一个N个节点和E条边的集合，其中每条边是取自N的一对节点。对于E中的任一条边(x,y)，我们用c(x,y)表示节点x和y间边的开销，如果节点(x,y)不属于E，则置c(x,y)=无穷大；如果(x,y)属于E，节点y被称为节点x的邻居。
G=(N，E)中的一条路径是一个节点序列(x1,x2,x3……xp)，这样每一对(x1,x2)，(x2,x3)……(xp-1,xp)是E中的边，给定任何两个节点x和y，通常这两个节点之间有许多条路径，每条路径都有一个开销，这些路径中的一个或多个是最低开销路径，最小开销路径通常也是最短路径。
-
链路状态(Link State,LS)算法
LS路由算法是一种全局的算法，在计算最优路径之前，需要获取网络中所有链路
- D(v)：源节点到目标节点的最小开销
- P(v)：从源到达目标的最小路径的前一个节点
- N：节点子集，如果从源到v的最低开销路径已确知，v在N中
LS路由的工作过程：
- 各点通过各种渠道获得整个网络拓扑，网络中所有链路代价等信息(这部分属于收集构成图的数据)
- 使用LS路由算法，计算本站点到其他站点的最优路径(汇集树)，得到路由表
- 按照路由表转发分组
LS的路由算法叫做Dijkstra算法，核心思路如下：
查找从A到C的最优路径：
- 初始化阶段，A到邻居B、G的当前最低开销分别是2和6，所以B(2,A)，G(6,A)
- B和G在确认到各自邻居C、E和H、E的开销，此时C(9,B)，H(10,G)，而对于E节点来说，它既是B的邻居，又是G的邻居，所以它要保持的最小开销是E(4,B)
- 依次类推F(6,E)、C(6,F)、H(8,F)、D(10,H)
- 由上面计算出来的A到每个节点的最优路径，可以得出A—C的最优路径是A-B-E-F-C(开销为8)
-
距离向量(Distance-Vector,DV)算法
距离向量算法是一种迭代的、异步的和分布式的算法
分布式：每个节点只从它的邻居节点收集数据，然后计算到每个已知节点的最小开销，然后再将计算结果分发给邻居
迭代：该过程从开始便一直执行，直达邻居节点之间没有可以交换的数据
异步：不需要所有节点步伐一致的操作
DV算法的公式，另dx(y)表示从x节点到y节点的最低开销路径：
dx(y) = Minv{c(x,y)+dv(y)}
该Bellman-Ford方程表示x节点到y节点的最低开销路径等于x到邻居节点的距离，加上邻居节点到y节点的最小开销路径，然后选择开销最小的路径。
以上图为例：dA©
dA© = Min(c(A,B)+dB©，c(A,G)+dG©)
然后dB©和dG©表示它们到C的最小开销，通过计算比较，A节点可以知道到达C节点的最小开销路径，然后在本地路由选择表进行保存(目标节点、下一跳节点以及最小开销)
-
链路开销改变和链路故障
-
当y节点检测到x到y的开销变为1时，更新自己的路由表，同时将变更信息发送给邻居z节点，z节点更新到x的最小开销，同时再通知它的邻居节点(很快传遍全网)
-
当y节点检测到x到y的开销变为60时，重新计算从y到x的最小开销路径，因为z中之前保存的从z到x的最小开销路径为5，所以y计算的最小开销为6，更新自己的路由表，当y需要向x发送数据时，会把数据发送给z，而z保存的到x的最小开销的下一跳却是y节点，于是z又把数据发送给y节点，依次循环，形成路由选择链路。
y记录的达到x的最小开销路径更新后，一段时间后会把更新信息发送给节点z，z节点重新计算到x的最小开销，再次同步给y，它们统计的开销按照1的步长增加，直到超过50后，才从这个循环退出
好消息传的快，坏消息传的慢解决办法：毒性逆转(无法检测3个以上节点的循环问题)
-
-
-
LS和DV的比较
- LS算法需要直到所有节点间的开销，所以当两个节点间的链路开销发生变化时，需要发送给全网的所有节点，而DV算法只需要将变更信息发送给邻居节点
- 健壮性上，LS算法各个节点独立计算，就算某个链路开销出错，对全网的影响也是有限的，但DV算法中，会向所有节点通告不正确的最低开销链路
路由协议
全世界有太多的网络节点，不可能全部存储进行计算，采用自治系统(Autonomous System，AS)来解决，各个自治系统内部的节点之间进行最小开销路径的计算
-
自治系统内部的路由选择：OSPF
OSPF是一种链路状态协议，使用泛洪链路状态信息和Dijkstra最低开销路径算法。
OSPF可以像网络子网一样，支持在单个AS中的层次结构。一个OSPF自治系统能够层次化地配置多个区域。
-
ISP之间的路由选择：BGP(基于距离矢量算法)
AS间路由选择协议涉及多个AS之间的协调，所以AS通信必须运行相同的AS间路由选择协议。在因特网中，所有的AS运行相同的AS间路由选择协议，称为边界网关协议(Border Gateway Protocol，BGP)
各个AS之间通过一个路由网关相连，两个AS的BGP连接称为外部BGP(eBGP)连接，相同的AS中的两台路由器之间的BGP会话称为内部BGP(iBGP)连接。
在BGP中，分组被路由到CIDR化的前缀，每个前缀表示一个子网或一个子网的集合。一个目的地可以采用138.16.68/22的形式，路由器的转发表将具有形式为(x,I)的表项，x是前缀，I是该路由器的接口之一的接口号。
每一个子网都可以向英特网的其余部分通告它的存在，当需要向目的地发送分组时，从AS间协议学到经过多个网关可以到达子网x，然后使用AS内部协议的路由选择信息，已决定到达每个网关的最低开销，选择具有最小最低开销的网关，最后从转发表确定通过最低开销网关的接口
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153693.html
