哈工大计算机网络Mooc 第九章笔记（网络层（下））

落日映苍穹つ 2022-09-07 12:29 296阅读 0赞

### 文章目录 ###

*   *  前引
     *  第九章笔记
     *   *  路由算法总概
         *  链路状态(LS)路由算法
         *  距离向量路由算法
         *  层次路由
         *  RIP协议
         *  OSPF协议
         *  BGP协议
         *  采用不同的AS内与AS间路由协议的原因

--------------------

## 前引 ##

--------------------

**各位好 这里又是Love6 的 闲聊时间 ^^**  
**不知道为什么 这段时间学习计算机网络 确实觉得很没劲 而且感觉真的挺枯燥的 呜呜 这段时间很多时候看视频我都是在强迫自己看下去**

**哎 没办法啊 只能这样先慢慢强迫自己看下去 我是一个单线程的人 不能双线程的做事情 - - 看完之后考虑花个几天时间把从顶至下给看了 之后去做几个实验或者小项目 实践一下吧 先写到这里惹**

--------------------

## 第九章笔记 ##

--------------------

### 路由算法总概 ###

--------------------

**路由算法(协议)确定去往目的网络的最佳路径**  
**转发表确定在本路由器如何转发分组**

--------------------

**对于网络中的路由器 相关链接 抽象化就可以当作数据结构中的图**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

**一般配置路由可分为 静态路由 动态路由**  
**静态路由：**  
**1、手工配置  
2、路由更新慢  
3、优先级高**

**动态路由：  
路由更新快  
1、定期更新  
2、及时响应链路费用或网络拓扑变化**

--------------------

**路由计算在全局信息 与 局部信息有不同的算法**  
**全局信息（所有路由器掌握完整的网络拓扑和链路费用信息）：**  
**链路状态(LS)路由算法**

**分散信息（路由器只掌握物理相连的邻居以及链路费用）：**  
**距离向量(DV)路由算法**

--------------------

### 链路状态(LS)路由算法 ###

--------------------

**典型算法 Dijkstra算法 我对这个算法原来还写了专门的博客来总结**  
**我对这个算法的理解就是 局部性每次挑选最短路径 这样替换长的路径就会是最优解**

**这里贴一下链接**  
**时间复杂度(n^2)**  
**[算法C++面试常考算法Dijkstra + Floyd最小生成树算法代码 例题+算法理解 ][C_Dijkstra _ Floyd_ _]**

--------------------

**问题在于这里的就是 出现震荡问题**  
**就是比如通关链路承载通信量作为指标计算**  
**比如目的传输A->D**  
**在第一次计算后 A->B->C->D 是最好的 之后把数据设计了 并传输数据**  
**但由于到每个都在计算 新的费用累加后达到C点 发现新的费用累加后C->B->A->D是最好的 之后就会不断震荡 来回传输**  
**解决这个问题 或者说压制这个问题就是设置最大跳步数来解决**

--------------------

**Dijkstra算法 伪代码示意图如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 1]

--------------------

### 距离向量路由算法 ###

--------------------

**距离向量路由算法基于dp 动态规划的思想来实现的**  
**下面给及张图 更清晰一点**  
**这里就不详细介绍了 每次变更的时候向周围的设备更新数据即可 再重新计算**

**出现的问题就是无穷计数**  
**解决办法是（毒性逆转）并需要设置一个最大度量**

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 4]

--------------------

### 层次路由 ###

--------------------

**这个解决办法的提出 是由于我们不可能把Internet那么大个六亿个路由器全部串起来 当作一个图处理 而且不可能全部只用一个算法 或者说策略来管理**  
**IP地址那么多 先说转发表有多么大就不说了 动态的维护 计算 那我们不用传输数据了 全部瘫痪了 哈哈**

**这里我们就引入了层次路由这个概念**  
**把路由分成片区 串联再由边界串联的专门负责的路由器来传输这个区域的路由器信息**  
**每个片区都是一个自治系统(autonomous systems) 每个自制系统AS里面都可以有自己的协议（intra-AS）来规划路线 自制系统边界是由自治系统间（Inter-AS）管理**

**`热土豆路由: 将分组发送给最近的网关路由器`**

**下面是示意图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 5]

--------------------

### RIP协议 ###

--------------------

**RIP路由表是利用一个称作route-d (daemon)的应用层进程进行管理  
1、应用进程实现  
2、通告报文周期性地通过UDP数据报发送**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 7]

--------------------

### OSPF协议 ###

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 8]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 9]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 10]

--------------------

### BGP协议 ###

--------------------

**原谅我懒了一个 这三个协议我相信我自己也记不住… 能记多少记多少**  
**下面直接把关键信息贴图了**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 11]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 12]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 13]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 14]

--------------------

### 采用不同的AS内与AS间路由协议的原因 ###

--------------------

**策略(policy):  
inter-AS: 期望能够管理控制流量如何被路由，谁路由经过其网络等.  
intra-AS: 单一管理，无需策略决策**

**规模(scale):  
层次路由节省路由表大小，减少路由更新流量  
适应大规模互联网**

**性能(performance):  
inter-AS: 策略主导  
intra-AS: 侧重性能**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20220829/8740e0d7712a4b80bcf3808f25fecdb0.png
[C_Dijkstra _ Floyd_ _]: https://blog.csdn.net/qq_37500516/article/details/116032626
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 1]: /images/20220829/ed73765c45ae47d5a0eb742caedd490a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 2]: /images/20220829/088b814635fe4a23bf20acf787c9f795.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 3]: /images/20220829/a651ee2d974d4c84b296b4b1c90e5d0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 4]: /images/20220829/5d881d67570f4852b56560e5012d1969.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 5]: /images/20220829/4fca1ecc3f964583bf579cb4b12add17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 6]: /images/20220829/fb55d7ff41a74e18a4f57b32ee134bbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 7]: /images/20220829/c275c4b9537d4923b435b8cbadb7496b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 8]: /images/20220829/0b224210975340c58b0e3a99f484528c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 9]: /images/20220829/c0ac324fcc6b413aaa214f711236a9a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 10]: /images/20220829/7f87a991a8344796857221794d540f20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 11]: /images/20220829/0800bef2c1444e15ae5b5e342823daef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 12]: /images/20220829/74a531e0be404d32adf5e4742cdf345d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 13]: /images/20220829/f3cfe02d92eb45409233c5b59fb14b4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70 14]: /images/20220829/3944cdbfad2841c4aabe115a1f2a7f74.png