网络层（三）

博主： Xherlock
发布时间：2022 年 06 月 03 日
348 次浏览
暂无评论
4946字数
分类：计算机网络

# 网络层（三）

## 路由选择算法

**网络层必须为发送方到接收方的分组确定所采用的路径**

与主机直接相连的路由器称为主机的默认路由器（default router），也称为该主机的第一跳路由器（first-hop router）。源主机的默认路由器称为源路由器，目的主机的默认路由器称为目的路由器，一个分组从源主机到目的主机的路由选择问题可归结为从源路由器到目的路由器的路由选择问题

* **按全局（global）或分散式（decentralized）分类**

* 全局式路由选择算法：LS，Link State链路状态算法，需要知道每条链路的费用
  * 分散式路由选择算法：以迭代分布式的方式计算出最低费用路径，DV，Distance-Vector距离向量算法，每个结点需要维护到网络中其他所有结点的费用（距离）估计的向量
* **按静态或动态分类**
* **按负载敏感或迟钝分类**

### 链路状态路由选择算法

网络拓扑（network topology）和链路代价（link cost）已知

迪杰斯特拉算法（Dijkstra）：计算从某个结点到网络中其他所有结点的最低费用路径，属于迭代算法

* c(x,y)：从结点x到y的链路代价，如果不相邻则值为无穷
* D(v)：从源点到目标结点v的最小代价路径的值
* p(v)：从源点到目标结点最小代价路径中，结点v的前继结点
* N'：已经确定在最小代价路径中的结点集合

**算法步骤**

![image-20220529160750982.png](http://xherlock.top/usr/uploads/2022/06/2937931539.png)

案例

![image-20220529160931843.png](http://xherlock.top/usr/uploads/2022/06/4232426737.png)

![image-20220529161048515.png](http://xherlock.top/usr/uploads/2022/06/2183830513.png)

u的转发表：(看下一跳的结点)

| destination | link |
| :-----------: | :-----: |
|      v      | (u,w) |
|      w      | (u,w) |
|      x      | (u,x) |
|      y      | (u,w) |
|      z      | (u,w) |

存在的问题：震荡（可以采用确保并非所有路由器同时运行LS算法）

假设链路费用等价承载的流量，w为目的路由器

![image-20220529162514689.png](http://xherlock.top/usr/uploads/2022/06/1488241078.png)

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

Bellman-Ford方程：$d_{x}(y)=min_{v}\{c(x,v)+d_{v}(y)\}$，结点x到结点y的最小代价路径，v为x的所有邻居，这个方程可以看出属于迭代的算法

eg：

![image-20220529163236326.png](http://xherlock.top/usr/uploads/2022/06/2646909209.png)

遍历u的邻居结点有vxw，$d_{v}(z)=5, d_{x}(z)=3, d_{w}(z)=3$

由上述贝尔曼福特方程，$d_{u}(z)=min\{c(u,v)+d_{v}(z),c(u,x)+d_{x}(z),c(u,w)+d_{w}(z)\}=min\{2+5,1+3,5+3\}=4$

$D_{x}(y)$为结点x到结点y的最小**估计**代价/费用

**每个结点都要维护**

1. 自己到邻居的代价
2. 自己到所有结点的最短路径代价估计值（自己的距离向量）
3. 所有邻居结点v的距离向量，即邻居到所有结点的最短路径代价估计值

每个结点不时地向它的每个邻居发送距离向量副本，**当结点x从它的任何一个邻居v接收到一个新距离向量，保存v的距离向量，然后使用上述方程更新自己的距离向量**

分布式——>每个结点只有自己的DV发生变化才通知邻居

**算法步骤**

![image-20220529164845295.png](http://xherlock.top/usr/uploads/2022/06/4286014366.png)

更新DV过程

![CB89CF1894A196DF171613D490847AA5.png](http://xherlock.top/usr/uploads/2022/06/2510991830.png)

第二列到第三列中由于y未发生变化，只需x、z更新

1. 但距离向量存在好消息传得快，坏消息传得慢的情况
2. 距离向量算法：增加毒性逆转（poisoned reverse）

如果z通过y路由选择到目的地x，则z将通告y，它到x的距离是无穷大，即$D_{z}(x)=\infty$
3. LS和DV对比

DV中每个结点仅与它直接相连的邻居交谈，但它为其邻居提供了从它自己到网络中所有其他节点的最低费用估计

LS中每个结点与所有其他结点交谈，但它仅告诉他们与它直接相连链路的费用

### 层次路由选择算法

路由器特点

规模：数目越来越大

管理自治（administrative autonomy）：一个组织按自己的意愿运行和管理网络

解决方案：自治系统（Autonomous System，AS）

在相同的AS下路由器采取同样的路由选择算法，称其为自治系统内部路由选择协议（intra-autonomous system routing protocol，intra-AS）

AS彼此互联是必须的，因此在一个AS内的一台或多台路由器还要负责向在本AS之外的目的地转发分组，称这些路由器为网关路由器（gateway router）

![image-20220530221411929.png](http://xherlock.top/usr/uploads/2022/06/2404029261.png)

当AS只有一个网关路由器：AS内部的路由选择协议已经决定了从内部路由器到网关路由器的最低费用路径，因此每台内部路由器知道如何转发分组

当AS有两条或多条链路通向外部AS：需要提供自治系统间路由选择协议（inter-AS）——BGP4

如上图，假设1d路由器可以经过AS2或AS3到达子网x，必须决定通过1b还是1c——热土豆路由选择：AS尽可能快地扔掉分组，即选择源路由器距离网关路由器最短路径代价中最小的网关，作为其转发表对应的接口

## 因特网中的路由选择

intra-AS routing也被称为interior gateway protocol（IGP）内部网关协议

主要有：

* OSPF：开放最短路径优先（Open Shortest Path First）
* RIP：路由选择信息协议（Routing Information Protocol）
* IGRP：

### OSPF

通常设置在上层ISP，使用**LS算法**，每当一条链路状态发生变化时，广播链路状态信息（即使未发生变化）。还要检查链路正在运行，允许OSPF路由器获得相邻路由器的网络范围链路状态的数据库；**OSPF报文由IP承载**

优点：安全（使用了鉴别）、多条相同费用的路径、对单播与多播路由选择的综合支持、支持在单个路由选择域内的**层次结构**

![image-20220530224546891.png](http://xherlock.top/usr/uploads/2022/06/3466276415.png)

### RIP

通常设置在下层ISP，使用DV算法，使用跳（hop），是沿着从源路由器到目的子网的最短路径所经过的子网数量；使用位于IP之上的UDP（端口520）传输；**是应用层协议**

路由选择信息在邻居间通过使用RIP响应报文来交换，大约每30s换一次；响应报文又被称为（RIP通告，advertisement）

NOTE: RIP中的DV代价由源路由器到目的子网决定

![image-20220531074831669.png](http://xherlock.top/usr/uploads/2022/06/1075388074.png)

一台路由器超过180s未收到邻居的报文，则该邻居不再认为可达；在这种情况下RIP修改本地路由选择表，然后向相邻路由器（可达的）发出通告传播该消息

### BGP

Border Gateway Protocol，边界网关协议，自治系统间路由选择协议

BGP给每个AS：

* eBGP（跨越两个AS的BGP会话）：从相邻AS处获得子网可达性信息
* iBGP（在同一个AS中的两台路由器之间的BGP会话）：向本AS内部的所有路由器传播可达性信息
* 基于可达性信息和AS策略，决定到达子网的“好”路由

#### BGP基本知识

BGP会话：两个BGP路由器交换BGP消息

* 向不同目的网络前缀通告路径
* 使用179端口的半永久TCP连接来交换路由选择信息

在BGP中目的地不是主机而是CDIR化的前缀（prefix），每个前缀表示一个子网或者一个子网的集合

eg：4个子网和AS2连接，138.16.64/24，138.16.65/24，138.16.66/24，138.16.67/24；AS2聚合四个子网并使用BGP向AS1通告单一前缀138.16.64/22

#### 路径属性和BGP路由

prefix+attributes=“route”，**带有属性的前缀被称为一条路由**

* AS-PATH：包含了前缀的通告已经通过的那些AS；用来检测和防止循环通告
* NEXT-HOP：向下一跳AS指明特定内部自治系统接口，用于正确配置转发表

当一台网关路由器接收到一台路由器通告时，使用其输入策略（import policy）来决定是否接受或过滤该路由

#### BGP路由选择

如果对相同前置u存在2条及以上路由，BGP顺序调用下列消除规则

1. 路由被指派一个本地偏好值作为它们的属性之一
2. 选择最短的AS-PATH路由
3. 选择最靠近NEXT-HOP路由器的路由（热土豆路由选择）
4. 仍留下多条路由，则路由器使用BGP标识符来选择路由

BGP消息由TCP连接进行交换

#### 路由选择策略

![image-20220603220118340.png](http://xherlock.top/usr/uploads/2022/06/1996190994.png)

A、B、C是主干提供商网络，W、X、Y是桩网络（stub network），X是一个多宿桩网络（multi-homed stub network）

X不希望转发B与C之间的流量，X向B和C 通告它没有通向任何其他（除自身）目的地的路径

A向B通告AW路径，B向X通告BAW路径，但B不会向C通告BAW路径，否则AC之间的流量将流经B，使B自己承担了传送流量负担费用

最后修改：2022 年 06 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Win11新机鼓捣记录
浏览次数: 2233
Reverse（十一）
浏览次数: 1571
栈~数制转换
浏览次数: 1501
C++学习
浏览次数: 1498
Python实现文件管理系统（重命名和删除）
浏览次数: 1472

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

为数据快速添加引号
浏览次数: 745
公钥密码体制
浏览次数: 391
pytorch学习4
浏览次数: 414
并发控制和备份恢复
浏览次数: 395
网络层（三）
浏览次数: 349

网络层（三）

Xherlock • 2022 年 06 月 03 日

# 网络层（三）

## 路由选择算法

**网络层必须为发送方到接收方的分组确定所采用的路径**

* **按全局（global）或分散式（decentralized）分类**

### 链路状态路由选择算法

网络拓扑（network topology）和链路代价（link cost）已知

迪杰斯特拉算法（Dijkstra）：计算从某个结点到网络中其他所有结点的最低费用路径，属于迭代算法

**算法步骤**

![image-20220529160750982.png](http://xherlock.top/usr/uploads/2022/06/2937931539.png)

案例

![image-20220529160931843.png](http://xherlock.top/usr/uploads/2022/06/4232426737.png)

![image-20220529161048515.png](http://xherlock.top/usr/uploads/2022/06/2183830513.png)

u的转发表：(看下一跳的结点)

| destination | link |
| :-----------: | :-----: |
|      v      | (u,w) |
|      w      | (u,w) |
|      x      | (u,x) |
|      y      | (u,w) |
|      z      | (u,w) |

存在的问题：震荡（可以采用确保并非所有路由器同时运行LS算法）

假设链路费用等价承载的流量，w为目的路由器

![image-20220529162514689.png](http://xherlock.top/usr/uploads/2022/06/1488241078.png)

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

Bellman-Ford方程：$d_{x}(y)=min_{v}\{c(x,v)+d_{v}(y)\}$，结点x到结点y的最小代价路径，v为x的所有邻居，这个方程可以看出属于迭代的算法

eg：

![image-20220529163236326.png](http://xherlock.top/usr/uploads/2022/06/2646909209.png)

遍历u的邻居结点有vxw，$d_{v}(z)=5, d_{x}(z)=3, d_{w}(z)=3$

由上述贝尔曼福特方程，$d_{u}(z)=min\{c(u,v)+d_{v}(z),c(u,x)+d_{x}(z),c(u,w)+d_{w}(z)\}=min\{2+5,1+3,5+3\}=4$

$D_{x}(y)$为结点x到结点y的最小**估计**代价/费用

**每个结点都要维护**

分布式——>每个结点只有自己的DV发生变化才通知邻居

**算法步骤**

![image-20220529164845295.png](http://xherlock.top/usr/uploads/2022/06/4286014366.png)

更新DV过程

![CB89CF1894A196DF171613D490847AA5.png](http://xherlock.top/usr/uploads/2022/06/2510991830.png)

第二列到第三列中由于y未发生变化，只需x、z更新

1. 但距离向量存在好消息传得快，坏消息传得慢的情况
2. 距离向量算法：增加毒性逆转（poisoned reverse）

如果z通过y路由选择到目的地x，则z将通告y，它到x的距离是无穷大，即$D_{z}(x)=\infty$
3. LS和DV对比

DV中每个结点仅与它直接相连的邻居交谈，但它为其邻居提供了从它自己到网络中所有其他节点的最低费用估计

LS中每个结点与所有其他结点交谈，但它仅告诉他们与它直接相连链路的费用

### 层次路由选择算法

路由器特点

规模：数目越来越大

管理自治（administrative autonomy）：一个组织按自己的意愿运行和管理网络

解决方案：自治系统（Autonomous System，AS）

在相同的AS下路由器采取同样的路由选择算法，称其为自治系统内部路由选择协议（intra-autonomous system routing protocol，intra-AS）

AS彼此互联是必须的，因此在一个AS内的一台或多台路由器还要负责向在本AS之外的目的地转发分组，称这些路由器为网关路由器（gateway router）

![image-20220530221411929.png](http://xherlock.top/usr/uploads/2022/06/2404029261.png)

当AS只有一个网关路由器：AS内部的路由选择协议已经决定了从内部路由器到网关路由器的最低费用路径，因此每台内部路由器知道如何转发分组

当AS有两条或多条链路通向外部AS：需要提供自治系统间路由选择协议（inter-AS）——BGP4

## 因特网中的路由选择

intra-AS routing也被称为interior gateway protocol（IGP）内部网关协议

主要有：

* OSPF：开放最短路径优先（Open Shortest Path First）
* RIP：路由选择信息协议（Routing Information Protocol）
* IGRP：

### OSPF

优点：安全（使用了鉴别）、多条相同费用的路径、对单播与多播路由选择的综合支持、支持在单个路由选择域内的**层次结构**

![image-20220530224546891.png](http://xherlock.top/usr/uploads/2022/06/3466276415.png)

### RIP

路由选择信息在邻居间通过使用RIP响应报文来交换，大约每30s换一次；响应报文又被称为（RIP通告，advertisement）

NOTE: RIP中的DV代价由源路由器到目的子网决定

![image-20220531074831669.png](http://xherlock.top/usr/uploads/2022/06/1075388074.png)

### BGP

Border Gateway Protocol，边界网关协议，自治系统间路由选择协议

BGP给每个AS：

#### BGP基本知识

BGP会话：两个BGP路由器交换BGP消息

* 向不同目的网络前缀通告路径
* 使用179端口的半永久TCP连接来交换路由选择信息

在BGP中目的地不是主机而是CDIR化的前缀（prefix），每个前缀表示一个子网或者一个子网的集合

eg：4个子网和AS2连接，138.16.64/24，138.16.65/24，138.16.66/24，138.16.67/24；AS2聚合四个子网并使用BGP向AS1通告单一前缀138.16.64/22

#### 路径属性和BGP路由

prefix+attributes=“route”，**带有属性的前缀被称为一条路由**

* AS-PATH：包含了前缀的通告已经通过的那些AS；用来检测和防止循环通告
* NEXT-HOP：向下一跳AS指明特定内部自治系统接口，用于正确配置转发表

当一台网关路由器接收到一台路由器通告时，使用其输入策略（import policy）来决定是否接受或过滤该路由

#### BGP路由选择

如果对相同前置u存在2条及以上路由，BGP顺序调用下列消除规则

BGP消息由TCP连接进行交换

#### 路由选择策略

![image-20220603220118340.png](http://xherlock.top/usr/uploads/2022/06/1996190994.png)

A、B、C是主干提供商网络，W、X、Y是桩网络（stub network），X是一个多宿桩网络（multi-homed stub network）

X不希望转发B与C之间的流量，X向B和C 通告它没有通向任何其他（除自身）目的地的路径

A向B通告AW路径，B向X通告BAW路径，但B不会向C通告BAW路径，否则AC之间的流量将流经B，使B自己承担了传送流量负担费用

发表评论 取消回复

网络层（三）

发表评论取消回复