详解IP协议(下)

素颜马尾好姑娘i 2023-10-03 10:31 6阅读 0赞

### 一、网络层控制层面 ###

#### 路由选择算法 ####

用无向图来表示网络结构，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算法，核心思路如下：  
    ![image-20210622212018985][]
    
    查找从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)算法
    
    距离向量算法是一种迭代的、异步的和分布式的算法
    
    分布式：每个节点只从它的邻居节点收集数据，然后计算到每个已知节点的最小开销，然后再将计算结果分发给邻居
    
    迭代：该过程从开始便一直执行，直达邻居节点之间没有可以交换的数据
    
    异步：不需要所有节点步伐一致的操作
    
    ![image-20210624154814551][]
    
    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节点的最小开销路径，然后在本地路由选择表进行保存(目标节点、下一跳节点以及最小开销)
    
     *  链路开销改变和链路故障
        
        ![image-20210624161652072][]
        
         *  当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内部协议的路由选择信息，已决定到达每个网关的最低开销，选择具有最小最低开销的网关，最后从转发表确定通过最低开销网关的接口

[image-20210622212018985]: https://img-blog.csdnimg.cn/img_convert/d1e27e7f4ffea1a8121e820e145c8a76.png
[image-20210624154814551]: https://img-blog.csdnimg.cn/img_convert/a6e76d386db525d206671d077233587b.png
[image-20210624161652072]: https://img-blog.csdnimg.cn/img_convert/1053b35782e75c9873b3d0170be700bc.png