3.1、网络层概述.md

# 电路交换和分组交换

结点间数据交换方式主要有以下三种：

* 电路交换
* 分组交换
* 信元交换



电路交换和分组交换的区别

* 是否经过中间节点的存储/转发



## 电路交换

电路交换方式起源于电话系统。



电路交换三个阶段

* 建立电路
  * 在传送数据之前，由发送方发出建立电路请求，交换机根据该请求，设法选择一条空闲的信道连接到接收方。
  * 接收方收到该呼叫后，返回一应答信号确认本次连接。
* 传送数据
  * 建立电路连接后，发送方通过已建立的电路向接收方发送数据。
* 拆除电路
  * 数据传输完毕，发送方或接收方任一方发出拆线信号，终止电路连接，释放所占用的信道资源。



优缺点

* 优点：实时性，可靠性好。

* 缺点：信道利用率低。





## 分组交换

报文

* 一份完整的信息称为一个报文。 



分组（Packet ）

* 报文分组的简称，又叫信息包，将报文划分为若干格式化信息单位作为网络层的数据传输单元，这样的格式化信息单位称为报文分组。

* 分组的一般格式

  <img src="https://img-blog.csdnimg.cn/2021011219431350.png" alt="image-20210102205825788"  width="50%" />



基本原理

* 将一份完整的报文划分为若干组，每个分组以**存储/转发**方式独立的从源结点传输到目的结点，目的结点收到这些分组重新组装成原报文。



特点

* 化整为零
* 存储转发



优点

* 使多路数据能够复用一条链路，提高链路的利用率。
* 有利于差错控制。
* 减少结点缓冲区容量。



缺点

* 当网络拥塞时，会导致分组传输延迟增加，尽管对传输的文本文件，二进制文件影响并不大，但对流媒体影响较大。





# 虚电路和数据报

分组交换技术的两种实现方式

* 虚电路
* 数据报



虚电路和数据报区别

* 中间节点的路径是否事先确定



## 虚电路

主机 HA 要和HC 进行数据交换

* 首先主机 HA 向HC 发一虚呼叫（虚电路连接请求），该虚呼叫选择一条适当的路径传送到HC, 记下沿途所经过的路程作为虚电路，如 HA -A-E-B-C-HC，并给其赋一个虚电路号VC1 。
* 如果HC 准备就绪，则发一响应给HA ，HA 收到该响应，则虚电路VC1已建立完毕。
* HA 和HC 的数据交换必须通过该虚电路进行。
* 数据交换完毕，则释放虚电路 。



虚电路特征

* 通信前发送方和接收方之间必须建立连接（虚电路），所以虚电路 是面向连接的网络服务。
* 虚电路只是一种逻辑电路，而不是真正的物理电路。报文分组在虚电路上传输不像再物理线路上那样中畅通无阻。而是要中间节点的存储转发。
* 一条链路上允许建立多个虚电路。
* 一旦虚电路建立完毕，本地通信的所有分组必须经过该虚电路进行。因此，虚电路能够保证分组的顺序接收。
* 仅当建立虚电路时需要源/ 目的结点地址，数据分组需分配一个虚电路号而无须源/目的结点地址



虚呼叫沿途经过每一结点要向该结点提出请求，任一结点拒绝请求（由于资源不足），均导致虚电路建立失败

* 一条链路上允许建立多个虚电路。如下面的VC1 和VC2 共同复用了BC 链路。

  <img src="https://img-blog.csdnimg.cn/20210112194338496.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210102211056581"  width="40%"/>



## 数据报

数据报无需建立连接，每个报文分组携带完整的源/ 目的地址，独立的选择路径，通过不同的路径到达目的主机

<img src="https://img-blog.csdnimg.cn/20210112194408729.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210102211426302"  width="40%"/>



数据报的特征

* 无需建立连接就可传输报文分组，因此数据报称为无连接网络服务。
* 不同的报文分组可以通过不同的路由到达目的主机，先发出的分组未必先，因此数据报服务不能保证报文分组顺序接收。
* 每个报文分组携带完整的源/ 目的地址，独立的选择路径





数据报与虚电路的比较

<img src="https://img-blog.csdnimg.cn/20210112194432741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210102211944201"  width="50%"/>







# 路由选择

无论是虚电路，还是数据报都要进行路由选择。

* 虚电路：需要一次路由选择
* 数据报：每个分组要进行路由选择。



路由选择

* 根据某种策略，选择一条最佳的路径到达目的主机，对路由器而言，  路由选择实质上是选择最佳输出端口。



分类

* 静态策略
* 动态策略



## 静态策略

按某种固定的规则进行路由选择，不随网络流量和拓扑结构变化而变化



扩散法（洪泛法）

* 当结点收到一个分组后，把该分组向除进来的链路外的所有其他链路转发，结果至少有一个分组以最快的速度到达目的结点。
* 问题：扩散过程产生大量重复分组，导致网络无法运行。
* 解决措施：每个分组设置一个下跳数字段，每经过一个结点，下跳数减1 ，当下跳数为0



固定式路由选择

* 每个结点保存一张固定的路由表，当某一分组到达时，根据分组的目的结点，在路由表中找到其对应的输出链路，然后将分组从该链路转发出去。

* 路由表的结构一般包括以下几个字段

  <img src="https://img-blog.csdnimg.cn/20210112194455353.png" alt="image-20210102212408928"  width="40%"/>

* 一般由网管中心根据最佳路由算法为每个路由产生固定路由表并发给该结点。固定路由表一旦生成，就不再改变，除非网管中心重新生成新的路由表

* 优点：简单

* 缺点：无法适应网络流量和拓扑结构的变化



最佳路由选择算法

* 一般采用最短路径算法。

* 最短路径就是指从源到目的结点所花费的“ 费用” 最小。“ 费用” 的含义非常广泛，可以是距离、平均通信量、延迟、下跳数等。

* 将网络看成连通图，每条链路以其“ 费用” 为权值，通过Dijkstra 最短路径算法求出任意两个结点之间的最短距离。

* 示例

  <img src="https://img-blog.csdnimg.cn/20210112194517329.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210102212734268"  width="30%"/>

  * 节点C的路由表

    <img src="https://img-blog.csdnimg.cn/20210112194538436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210102212833054"  width="30%" />



## 动态策略

动态策略根据当前拓扑结构和流量的变化来动态改变路由，又称为自适应路由。

* 孤立路由算法。
* 集中路由选择。
* 分布路由选择。



孤立路由算法（热土豆算法）

* 基本思想：当你手里拿着 一个烫手的热土豆时，你一定会想办法以最快的速度脱手。当一个结点收到一个分组后，选择一条输出队列最短的链路尽快的将其转发出去，而不管目的节点位于何方。
* 优点：提高链路的利用率。
* 缺点：具有很大盲目性。
* 改进：与固定路由算法混合使用。
  * 首先根据固定路由算法选择可能链路，并给这些链路赋上一定权值，
  * 再根据链路队列长度给赋上一定权值，选择这两个权值和最小的链路。



逆向自学习算法

* 算法思想
  * 每个分组中包含一个结点计数器，每经过一个结点，该结点计数器加1 。
  * 当一个结点R 从链路L 收到一个来自源结点S 的分组时，如果结点计数器为n ，就知道经L 到达S 的路径的距离不会超过n 。
  * 若它以前纪录到S 的最短路径超过n 时，则将链路L 作为到达S 的最短输出链路，纪录当前最短路径长度n 。
  * 经过一段时间的自学习，结点R 会找到它到其它结点的最短路径及最小距离值。
* 优点：对好消息反应灵敏
* 缺点：对于坏消息无法了解到（如一条链路崩溃）  
* 改进：每隔一段时间T ，删除这段时间内没有刷新的记录





分布路由选择---距离向量路由选择 (D-V 算法)

* 该算法最早在ARPANET 中使用，后在Internet 及Novell 网中的IPX 中使用，即 RIP 协议.

* 基本思想：每个结点都保存一张路由表，路由表包括三个主要字段，即目的地址，最短距离、最佳输出链路。

  * 与固定路由选择不同的是：相邻结点之间定期交换路由信息（如每隔十秒），并根据最新路由信息，刷新路由表。
  * 要交换的路由信息由二元组（V,D ）组成，其中V 为目的地址，D 为到达目的地址的距离。又称距离向量算法。

* 优缺点

  * 缺点：对网络变化需经若干周期才能作出反应。特别是对好消息反应快，对坏消息反应迟钝。
  * 优点：运算量和交换的信息量较小

* 无穷计数问题的解决方法

  * 规定足够大的数作为无穷大，如RIP 规定无穷大为16 ，负作用是限制了网络规模

  * 水平分割法（毒性逆转）

    * 基本思想：如果一个节点到目的个节点的最小距离要经过其中一个邻居节点，则在跟这个邻居节点交换路由信息的时候，把去目的节点的长度报告为无穷

      <img src="https://img-blog.csdnimg.cn/20210112194613851.png" alt="image-20210103154057279"  width="30%" />

    * 不论链路AB 出现故障，C 在向B 报告到A 的路由，都会自己把到A 的距离报告为∞

    * 水平分割有时会失败





分布路由选择---链路状态路由选择（L-S）

* 从1979 年开始，ARPANET 以及后来的 Internet 的内部网关协议由距离向量改为链路状态。

* 基本思想：每个结点定期广播路由信息，并根据最新路由信息刷新路由表。

* 主要步骤

  * 1、发现邻居结点。

    * 当一个路由器启动以后，它的第一个任务就是要知道谁是它的邻居结点。通过向每个端口发送特殊的HELLO 分组来发现邻居结点，收到HELLO 分组的路由器应返回一个应答来说明它的网络地址。

  * 2、测量链路开销。

    * 通过发送一个特殊的ECHO 分组来实现，测量其往返时间再除以2 。

  * 3、产生链路状态分组

    * 每个结点通过实测相邻的链路开销，可创建链路状态分组。

    * 示例

      <img src="https://img-blog.csdnimg.cn/20210112194155712.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210103155510576"  width="30%"/>

      --> D 结点当前链路状态分组

      <img src="https://img-blog.csdnimg.cn/20210112194220200.png" alt="image-20210103155559012"  width="10%"/>

  * 4、向所有结点广播L-S 分组

  * 5、结点获得最新L-S 状态后，用最短路径算法计算到每个其他结点的最短路由，并刷新路由表。

* L-S 算法优缺点

  * 优点：对网络反应迅速
  * 缺点：广播L-S 分组占用信道容量大
  * 应用：OSPF （开放路径优先）采用L-S 算法，作为Internet 的AS 内标准路由协议。





D-V 算法和L-S算法比较

<img src="https://img-blog.csdnimg.cn/2021011219424681.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210103155943475"  width="40%"/>