Loading...
墨滴

张春成

2021/11/05  阅读:30  主题:默认主题

乌合之众

乌合之众

系统中多个成员的复杂关系一般可以用网络进行描述, 在该网络中的信息传递效率是值得关注的关键点。

通过本文的模拟可以看到, 一个无中心的, 单纯依靠节点之间的互信进行信息传递的网络, 其网络容量令人难以置信的低。

本文是之前“行路难”系列的延伸, 与之不同的是,本文提供了一个实时模拟和显示代码, 让读者可以“看到”网络中消息“流动”和“迟滞”的动态过程。


有限资源下的网络消息传递模型

本文模拟了这样一个网络,它包含若干节点。 节点的组织结构十分简单,我们使用 dijkstra 算法建立节点之间的连接通路。 这样我们就得到了一个“全局连接最小”的网络连接方案

Graph 1
Graph 1

接下来,我们在网络中随机生成一些消息。 这些消息从a点生成到达b点, 由于dijkstra算法的通路唯一性可知, 必有唯一一条通路,满足它的起点和终点分别为ab

这样,我们把这个消息想象成一个互联网中的典型的socket, 并且把节点想象成一个个的“路由节点”。 因此,这个消息很确定的知道自己的全部路由过程。

而我们的路由(节点)的转发能力是有限的, 它在一个时刻只能发送一条消息到目标路由。 但好在它的接收和存储能力很强, 对于无法即时转发的消息, 它可以把它们存储一下, 之后以“先入先出”的形式,对这些缓存的消息进行逐一处理。

实时模拟及显示

为了模拟并展示这个系统传递这些消息的动态过程, 我编写了代码,实时模拟并显示这个过程, 可以展示的信息为

  • 各个节点的消息“拥堵”程度,见节点大小和下方的条形图;
  • 每条消息达到终点时,受到“拖延”的程度,见右方的条形图。

对于这样一个模型,我设置了几种情况, 主要变量是节点数量与每段时间生成的消息数量。

  1. 节点数量为 ,消息生成数量为

    从视频中可以看到,系统中总存在这样一些节点, 消息在其中不断累积, 并且累积程度越来越严重, 使得累积的消息永远不能达到它们的终点。 系统就这么崩溃掉了。

    【这是一段棒到不行的视频】

  2. 节点数量为 ,消息生成数量为

    我们尝试降低节点数量,从而降低网络的复杂程度, 同样的系统崩溃现象同样发生了, 这至少说明,这样的网络无法容纳每次 条的信息生成速率。

    【这是一段棒到不行的视频】

  3. 节点数量为 ,消息生成数量为

    我们再尝试降低消息数量, 可以看到,网络崩溃现象再没有发生。 当然,这并不是说信息不会拥堵, 而是说系统不断动态地传递消息, 当拥堵出现,系统也有能力不断消化掉这些堵塞。

    【这是一段棒到不行的视频】

从以上实验中可以看到,单纯依靠节点之间的连接进行信息传递, 很有可能导致网络无法处理一定量的消息, 这些消息会不断累积并堵塞在某些节点上, 而永远无法达到自己的终点。 我们可以说,这样的网络对消息的容量的非常小的。

怎么解决这样的问题呢? 我在下面进行了一些分析。

简要说明

我已经在在线笔记本 中呈现了全部开源代码, 其中也包括了较为详细的说明。 现抄录如下,

The Packages' Tour

It is the simulation of how the network delivers packages. The outcome sounds crazy, since it shows

What a small capacity is, when we only focus on the Global Efficiency of a larger network.

It also hints that

It is a bad idea for the members communicate with its neighbors, instead of using a control center.

Basic Idea

Network

Assume we have a system. It can be a city or computer network, where the member connects to another.

If the goal is to reach the high global efficiency,

We use dijkstra algorithm to establish the connections, it makes the graph has the lowest overall cost.

Packages

Then we suppose the network delivers packages, and the packages follow the rules:

  • The package has start and finish points;
  • It has a fix path estimated by the dijkstra algorithm, since the graph of the network is fixed;
  • Every node has a limited power of delivering a package, it only delivers one package at each loop;
  • For the packages remain on the node, the node restores them and deliver them using FIFO rules;
  • Last but not least, in every loop, several packages are generated randomly by some nodes, to simulate the input of the system.

The simulation is the dynamic of the packages' tour.

Simulation

We simulate the dynamic process, in which we record how the packages are delivered and restored in the network. The dynamic is displayed in real-time.

  • The network shows the Nodes and the network connections;
  • On the bottom, we present the number of restored packaged in each node;
  • On the right, we present the delay of the latest 50 finished packages.

Results

Run the simulation, and you will see that

  • The capacity of the network is amazingly small. Supposing we have 70 nodes and generate 7 packages to be translated through the network to its end, there are Always some nodes reach its delivering limit, and its storage grows forever.
  • The reason is simple, in a global-efficiency optimized network, there are nodes sitting on the crossroads. It makes almost all the package needs to pass them, and they have very limited power to deal with all the incoming. Then they stuck.
  • As long as it happens, it will never recover by itself and can only go worse. You can see the latest finished packages have a very long delay in the meantime, since they have waited on the key nodes for long enough.
  • The situation is horrible since the packages may never reach its end, since the delay grows forever.
  • The more nodes in the system, the more likely the situation happens.

Solution

Then the question is how to solve the issue. My answer is to add a control center to translate the packages, instead of letting the network fails.

Here is the thinking

  • One possible solution is to increase the power limit of the key nodes. Say, let it delivers not 1 but n packages for every loop. But it may cause the same problem to its neighbors, and their neighbors, and soon. It may end up boost every node, which is an unacceptable solution since the resource is reasonably limited.
  • The other way is to put a center controller to do the package translation job. It may be not so fast to deal the packages in one loop, and it is acceptable to allow it costs n loops for each package. There are several advantages, for one, the delay is estimated-able, which allows the nodes to arrange their workflow; and on the other hand, the horrible situation will never happen, in which the package will never reach its end.

张春成

2021/11/05  阅读:30  主题:默认主题

作者介绍

张春成