【TT】计算机网络有趣的选路算法、传输层中的滑动窗口思想

你好，我的名字是TT。

在这篇文章中，我们来谈谈计算机的另一个主要知识点——计算机网络中的算法。当然，计算机网络也是一个历史悠久的科学研究方向。可以说，现在的计算机世界之所以如此繁荣，是因为计算机网络发挥着巨大的作用，是整个互联网世界的基石。

许多算法问题自然出现在复杂的计算机网络中。例如，许多经典的图论算法诞生于计算机网络的研究背景。本章我们将选择几个有趣的问题一起讨论，主要涉及两个场景，计算机网络网络层的路由算法，传输层协议TCP中的滑动窗口思想。

今天我们先来学习一下路由算法，有时候也叫路由算法。相信你应该对“路由”这个词很熟悉。是的，它指的是路由器中的路由。

路由

我们知道，计算机网络的作用是通过将不同的节点连接在一起来交换信息和共享资源，每个节点通过网络形成一个拓扑关系网络。

例如，在局域网中，节点A要向节点B发送消息，如果A和B没有通过网络直接相连，可能需要被其他路由设备多次转发。这时，我们需要在整个网络拓扑图中查找。需要一条可达路径才能将消息发送到其目的地。

每个路由器都是一个网络设备，也就是网络中的一个节点，其中存储着一张路由表。决定如何转发数据。

您的计算机也是网络上的一个节点。我们可以通过Mac上的命令看到我们节点的路由表：

网络统计 -nr

我在本地得到的路由表如下：

路由表的每一行代表一个路由规则，其中至少包含两条信息，即路由表的前两列：

1.目的网络地址（Destination）：表示IP包去往的目的网络。

2.下一跳地址（网关）：与当前路由器相邻的路由器，命中此规则的数据包应通过此路由器转发到最终目的地。

我将在这里简要介绍最后三列。flag是一些关于路由的信息，netif是指物理网络接口，expire代表过期时间。有兴趣的可以参考Linux手册了解详情。

因为每个数据包都包含目的地址，路由器工作的基本原理是网卡根据路由表匹配数据包对应的规则，并转发到下一跳路由器，直到到达目的地。

路由表

这个路由表是怎么来的？主要有两种方式。

一是我们手动管理配置。Linux提供了简单的配置命令，可以根据路由IP配置路由表，也可以根据一定的策略进行配置，参考Linux手册即可。这种方法也称为静态路由表，在网络的早期由网络管理员手动配置。但是如果网络结构发生变化，手动修改的成本非常高。

为了解决这个问题，第二种方法，动态路由表应运而生。它可以根据协议通过网络中节点之间的通信自主生成，也可以在网络结构发生变化时自动调整。

生成动态路由表的算法就是我们的路由算法。所以，路由算法所做的就是建立一个动态路由表来帮助每个数据包选择到目标IP的最快路径。

那么在路由问题中，最快的路径是什么？

我们知道，信息在网络上的传输必须是物理传输的。设备之间的距离和不同设备的网络连接不同，都会影响节点之间的传输时间。如果我们把不同节点之间的通信时间看成距离，那么在整个拓扑图上寻找最快路径的过程其实就相当于在图上寻找最短路径的问题。

相信大家对求解最短路径的算法已经了解了不少，比如基于BFS的SPFA、基于贪心思维的Dijkstra、基于动态规划思维的Bellman-Ford等算法。这些算法也用于路由问题。最经典的两个是基于 Dijkstra 的链路状态算法和基于 Bellman-Ford 的距离向量算法。

今天我们先学习大名鼎鼎的 Dijkstra 算法，看看它是如何解决最短路径问题的。

Dijkstra 算法

Dijkstra 的算法是解决单源最短路径问题的非常经典的算法，但它有一个巨大的局限性：它只能用于没有边且权重为负的图。

在分析这个限制之前，让我们严格定义最短路径问题。

假设我们有一个图 G=(V,E)，其中有 v 个节点和它们之间的 e 条无向边。其中，每个节点的集合用V表示，边的集合用E表示，边的权重表示边的两点之间的距离。

单源最短路径问题就是在这个图上找到源点s到图上任意一点距离最短的路径。路径的长度/距离是该路径上所有边的权重之和。怎么做？

估计你也想到了。一个更直观的想法是贪婪思维。我们从离s最近的点开始记录，然后找到下一个点和下一个点，逐步前进。

它必须是最接近直接连接到 s 的节点之一。这是因为所有与s形成二度关系的节点都会经过一个与s直连的节点，并且距离不会比这个直连节点短，所以这个节点一定是与s距离最近的节点s 在所有节点中，我们将第一个节点记录为 v1。

这时，刚刚找到的v1可能会成为第二最短路径的一部分。我们需要在与 s 和 v1 直接相邻的节点中找到除 v1 之外与 s 的距离最短的节点。它必须是剩余的节点。中到 s 最近的节点。

Dijkstra 的算法实际上就是这样做的，它引入了一种称为最短路径树的构造方法。根据刚才提到的基于贪心的思想，可以逐步找到离源点s最近和次近的点，就可以得到G的一个子图，其中包含s和从s可以到达的所有节点，并且他们以 s 为根。它们一起形成一棵树，最短路径树。找到这棵树后，我们自然会找到从 s 到所有节点的最短距离和路径。

想法

为了在编程语言中更准确地描述我们直观的想法，我们需要引入一个叫做“relax”的操作，并用例子来解释这个过程。

假设现在有一个有向图G，其中包含0、1、2、3、4个等5个节点，节点之间的边权重代表距离，全部On该图，例如节点 0 和节点 1 之间的边权重/距离为 2。

假设0节点是源点s，那么我们如何构造这个以s为根的最短距离树T呢？

整个构建过程是从原点一步步展开的ip:选路表和选路算法 读书笔记，我们可以用一个数组dis来标记源点s到其他节点的距离。由于一开始树T中只有根节点s，此时：

例如，对于节点 0，1 是当前候选集中最接近 s 的节点。

每次选择最短节点u加入T后，T的候选集显然有了更多的选择，可以找到u的所有相邻节点及其到树的距离。

但是 u 的邻居 v 和源 s 之间的距离有两种可能。

例如，从图中的 1 个节点中搜索 4 个节点时就是这种情况。我们可以把v加到T上，记录dis[v] = dis[u]+edge[u][v]，这显然是目前找到的到v的最短距离，但是以后还是有可能更新为它遍历，我们称之为“松弛操作”。

更新操作其实是“松弛”，但我个人认为“松弛”并不是一个很好理解的术语，因为松弛操作实际上让路径变短了，而是因为Dijkstra用“松弛”来描述这个Update操作；所以我们也翻译成松弛操作。

我们再用例子梳理一下整个搜索过程。

在整个构建过程中，0、1、3、2、4个节点会依次入队。当它们入队时，它们是从候选集到 s 距离最短的节点。

在没有负边的情况下，这样保证了剩余节点之间的距离一定比这个节点长，不会出现入队后节点距离还需要更新的情况。添加到树中的每个节点的距离是在加入的那一刻。已经修复了。

在加入队列的时候，我们也探索了一些可能连接到树并且离s更近的节点，我们需要将它们“松弛”并加入候选集。

比如0-3节点之间的距离一开始是7：但是1个节点加入候选集后，我们可以通过1到3，3到0的距离会更新为5，而不是7不再；这时候第3个节点(0-1-3）已经是所有剩余节点中离s最近的节点了，我们把它加到树上，dis[3]=5就没有机会了由其他节点更新。。

代码

我们可以使用我们今天学习的 Dijkstra 算法来解决这个问题。实现代码贴在这里供您参考：

类解决方案{

上市：

int networkDelayTime(vector>& times, int n, int k) {

// 标记未探索的节点距离

常量 inf = INT_MAX / 2;

// 邻接表

向量> g(n, 向量(n, inf));

// 作品

对于（自动时间：次）{

g[时间[0] – 1][时间[1] – 1] =时间[2]；

}

向量距离（n，inf）；// 当所有节点都没有被探索时，距离被初始化为无穷大

使用的向量（n，假）；// 标记是否已添加到树中

距离 [k – 1] = 0; //记录原点距离为0

对于 (int i = 0; 我

整数 x = -1；

// 在候选集中找到到 S 距离最短的节点 for (int y = 0; y

if (!used[y] && (x == -1 || dist[y]

}

}

// 加入树

使用 [x] = 真；

// 基于 x 松弛 x 的所有邻居 for (int y = 0; y

dist[y] = min(dist[y], dist[x] + g[x][y]);}

}

// 获取最短路径中的最大值

int ans = *max_element(dist.begin(), dist.end());

返回 ans == inf ？-1：答案；

}

};

代码中的dist用来标记距离，used用来标记树中的节点。每次我们都会从候选节点中选出s最短的节点，并以此为基础对其相邻节点进行“松弛”操作；解决了道路问题，最后从所有距离取最大值。

时间复杂度也得到了很好的分析。整个代码中有两层循环。外层循环是每次向树中添加一个节点，总共执行n次；内循环有两个部分，用于找到最短节点并对所有邻居执行“松弛”操作，最多不超过 2*n 次计算。因此，整体时间复杂度为 O(n^2).

总结

网络路由算法的核心是帮助路由器基于在动态变化的网络中检测和寻找最快传输路径的思想建立路由表，使每个数据包能够快速、正确地传播到正确的目的地.

首先ip:选路表和选路算法 读书笔记，我们需要找到解决最短路径问题的方法。Dijkstra 就是这样一种算法，用于求解没有负边的图中的单源最短路径。基于贪心思想，我们可以构造一个最短路径树来找到源点。网络中所有节点的最短路径。核心是松弛操作。添加最短节点后，我们还需要根据它来探索相邻节点之间的距离是否更短，例如从不可达到可达，或者从更长的路径到改变。进入更短的路径。

Dijkstra 的算法仍然难以实现。你可以试着找几个问题来测试一下学习效果。另一种有效的测试方法是参考费曼学习法。你可以试着告诉你的朋友。为什么 Dijkstra 的算法不支持负边也是 Dijkstra 算法的一个非常重要的约束。如果你能解释清楚，你就会明白本质。

借助 Dijkstra 算法，我们还可以解决网络路由中的最短路径问题。