切割和网络流

任何网络的主干分析都广泛使用图论及其算法来完成。性能限制是 可靠性、延迟/吞吐量 我们的目标是 将成本降到最低。

在网络主干网设计中，关注的要点和考虑事项包括：

1. 主干拓扑应该是什么？
2. 线路容量的分配。
3. 线路和整个网络的流量分配。

一些常见的定义：

• 网络： 网络是一个电路，它是一系列相邻节点返回到起始节点。包含图中所有节点的回路称为 哈密顿电路。
• 生成树： 图的生成树是一个子图，包含图的所有节点和一些选定的弧集合，以便每对节点之间只有一条路径。
• 切： 图论中的一个概念是割，它有助于对网络的承载能力进行建模。X-Y切割是一组圆弧，其删除将断开节点X与节点Y的连接。
  

  加权图中的割

  Four A-H cuts are shown in the figure above.
  
  Cut 1 : AB, AE (capacity = 11)
  Cut 2 : AB, ED, JF, JK (capacity = 23)
  Cut 3 : BC, FG, KL (capacity = 10)
  Cut 4 : CH, CL (capacity = 12)

• 最小切割： 它是一个替换其任何成员重新连接图形的组件。换句话说，在最小切割中，所有圆弧都是必不可少的。弧AB、AE和FG的集合形成A-H切割，但切割不是最小的，因为恢复弧FG不会将节点A重新连接到节点H。
• 最小切割： 在加权图中，每个割都有容量。具有最小容量的切割是最小切割。在上图中，容量为10的切口-3是最小切口。
• 最大流最小割定理： 任何图中任意两个节点之间的最大流不能超过分隔这两个节点的最小割的容量。
• 投票： 网络上的每个站点都按预定顺序进行轮询。在两次轮询之间，站点会在队列中累积消息，但在被轮询之前不会传输消息。连续邀请线路上的终端发送数据的过程。这可以通过让主站使用轮询列表来邀请终端发送数据，或者通过每个终端按顺序向下一个终端发送轮询消息以使其可以发送数据，或者通过使用令牌环中的令牌来控制数据的发送来实现。
• 轮询序列： 邀请终端发送数据的顺序。这可能基于轮询列表，在该列表中，终端ID按要轮询的顺序存储。
• 轮询技术：
  

  典型的投票网络

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

  点名轮询和中心轮询

  对于有效的网络，我们需要考虑上面提到的点。此外，还可以使用 排队论 排队系统可以用来模拟顾客到达、等待轮到服务、接受服务，然后离开的过程。 这个 链路赤字算法 也用于确定网络的有效主干。