dsal 削减和网络流量

削减和网络流量

原文： https://www.geeksforgeeks.org/cuts-and-network-flow/

任何网络的骨干分析都可以通过使用图论及其算法来广泛完成。性能限制是可靠性，延迟/吞吐量，目标是最小化成本。

在网络的骨干设计中，有关的点和注意事项是：

骨干拓扑应该是什么？
线路容量分配。
线路的流分配，从而分配整个网络。

一些常见定义：

网络：网络是一个环路，该环路是一系列相邻节点的序列，这些序列又回到起始节点。包含图的所有节点的环路称为哈密顿环路。
生成树：图的生成树是一个子图，其中包含该图的所有节点以及一些选定的圆弧集合，因此每对节点之间只有一条路径。
Cut：图理论中的一个概念，可用于对网络的承载能力进行建模。 X-Y 切割是一组圆弧，它们的移除将节点 X 与节点 Y 断开连接。
最小剪切：这是替换其任何成员重新连接图形的图形。换句话说，在最小限度的切割中，所有电弧都是必不可少的。弧 AB，AE 和 FG 的集合形成了 A-H 切割，但是切割并不是最小的，因为恢复弧 FG 不会将节点 A 重新连接到节点 H。
最小切割：在加权图中，每个切割都有容量。具有最小容量的切割是最小切割。在上面显示的图表中，容量为 10 的 Cut-3 是最小切割。
最大流量最小割定理：任何图中任意两个任意节点之间的最大流量不能超过分隔这两个节点的最小割的容量。
轮询：以某种预定顺序轮询网络上的每个站点。两次轮询之间，工作站将消息堆积在其队列中，但直到被轮询后才进行传输。依次邀请线路上的终端发送数据的过程。这可能是由于让主站使用轮询列表来邀请终端发送数据，或者每个终端依次向下一个终端发送轮询消息以使其可以发送数据，或者通过使用令牌（如令牌环来控制数据的发送。
轮询序列：邀请终端发送数据的序列。这可以基于轮询列表，在该列表中，将按要轮询的终端 ID 的顺序存储终端 ID。
Polling Techniques :

典型的轮询网络
1. 点名轮询：主站使用一个或多个轮询列表来确定要轮询的下一个终端。每个站都必须由中央计算机（控制器）依次轮询。站点发送了其积压的消息后，它会将最后一个数据包的后缀通知中央控制器。收到此后缀数据包后，控制器将按轮询顺序将轮询发送到下一个站点。
2. 集线器轮询：当前处于轮询模式的终端按顺序轮询下一个终端。在这种情况下，前进（后缀）包包含下一个站地址。
  
  必须提供一个监视信道，以向相应的站指示它应该开始发送。从本质上讲，准入直接从一个站传输到另一个站。
3. 令牌传递：令牌传递到网络上的下一个设备（环或总线），该设备可以使用令牌来传输数据或可以将其传递给下一个设备。
点名轮询和集线器轮询