4.通信网络 - Shane Lorien

在分布式系统和多处理器计算机中，核心问题是如何高效地连接个输入和个输出。

1. 通信网络的四大衡量指标

设计一个网络拓扑时，我们审视以下四个属性：

需要的交换机数量、大小
Degree (度数): 每个节点引出的边数（受硬件物理接口数量限制，理想情况下应为常数）。
Diameter (直径): 任意输入到输出的最短路径的最大长度（决定了信号传输的最大延迟）。
Congestion (拥塞度): 在所有可能的“一对一”通信排列中，经过某条边的最大包数量（决定了网络的吞吐瓶颈）。

排列

一个从到的函数，将映射到，当且仅当。

对于个输入输出，从第个输入到其对应输出的记作。 拥塞度 ：所有通过的最多的边被通过的次数的最大值。例如，对二叉树，这个值可能是 (输入输出的父节点一样)，也可能是 (所有输入都要经过最顶上的节点才能到输出)，那么其拥塞度就是。

2. 几种结构

二叉树(Binary Tree)

底端是输入输出。

指标： 直径 , 需要台交换机。
致命伤： 拥塞度。

graph TD
    A((A))
    B((B))
    C((C))
    D((D))
    E((E))
    F((F))
    G((G))

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

完全二部图 (Complete Bipartite Network)

每个输入直接连向每个输出。

指标： 直径，拥塞度。
致命伤： 需要一台的交换机。

graph LR
    subgraph U
        U1((u₁))
        U2((u₂))
        U3((u₃))
    end
	
    subgraph V
        V1((v₁))
        V2((v₂))
        V3((v₃))
    end

    U1 --- Switch
    U2 --- Switch
    U3 --- Switch
    Switch --- V1
    Switch --- V2
    Switch --- V3

B. 二维网格 (2-D Mesh)

的阵列。

指标： 度数，需要台的交换机，拥塞度。
缺点： 直径。

graph TD
    A11(In1) --- A12((1,2)) --- A13((1,3)) --- A14((1,4))
    A21(In2) --- A22((2,2)) --- A23((2,3)) --- A24((2,4))
    A31(In3) --- A32((3,2)) --- A33((3,3)) --- A34((3,4))
    A41(In4/Out1) --- A42(Out2) --- A43(Out3) --- A44(Out4)

    A11 --- A21
    A12 --- A22
    A13 --- A23
    A14 --- A24

    A21 --- A31
    A22 --- A32
    A23 --- A33
    A24 --- A34

    A31 --- A41
    A32 --- A42
    A33 --- A43
    A34 --- A44

Theorem：拥塞度=2

[!证明] 如此行走：为从向右走到，再向下走到输出。对于节点，它只可能从左或上方被经过，那么只可能来自和到达的两种情况，故不超过，显然有排列可以达到。

蝶形网络 (Butterfly Network)

为了解决延迟问题，我们引入了分层递归。一个的蝶形网络由两部分的子网络组成。

结构： 共有层，每层个节点。
路由逻辑： 节点地址为二进制。在第层，比较目标地址的第位：
- 若为 0，走向左下方的子网络；
- 若为 1，走向右下方的子网络。
指标：
- Size:
- Degree: 4
- Diameter: （巨大突破！ 个节点，直径仅约 20）。
- Congestion: （在中间层会发生严重的“交通堵塞”）。

graph LR
    subgraph Inputs
        In0[In 0]
        In1[In 1]
        In2[In 2]
        In3[In 3]
    end

    subgraph Layer_0
        L0_0((00))
        L0_1((01))
        L0_2((10))
        L0_3((11))
    end

    subgraph Layer_1
        L1_0((00))
        L1_1((01))
        L1_2((10))
        L1_3((11))
    end

    subgraph Layer_2
        L2_0((00))
        L2_1((01))
        L2_2((10))
        L2_3((11))
    end

    subgraph Outputs
        Out0[Out 0]
        Out1[Out 1]
        Out2[Out 2]
        Out3[Out 3]
    end

    %% 输入连接
    In0 --- L0_0
    In1 --- L0_1
    In2 --- L0_2
    In3 --- L0_3

    %% Layer 0 -> Layer 1 (跨度为 2)
    L0_0 === L1_0
    L0_0 -.- L1_2
    L0_1 === L1_1
    L0_1 -.- L1_3
    L0_2 === L1_2
    L0_2 -.- L1_0
    L0_3 === L1_3
    L0_3 -.- L1_1

    %% Layer 1 -> Layer 2 (跨度为 1)
    L1_0 === L2_0
    L1_0 -.- L2_1
    L1_1 === L2_1
    L1_1 -.- L2_0
    L1_2 === L2_2
    L1_2 -.- L2_3
    L1_3 === L2_3
    L1_3 -.- L2_2

    %% 输出连接
    L2_0 --- Out0
    L2_1 --- Out1
    L2_2 --- Out2
    L2_3 --- Out3

    %% 样式美化
    style L0_0 fill:#fff,stroke:#333
    style L1_0 fill:#fff,stroke:#333
    linkStyle 4,6,8,10,12,14,16,18 stroke:#333,stroke-width:2px;
    linkStyle 5,7,9,11,13,15,17,19 stroke:#666,stroke-dasharray: 5 5;

如果用二进制表示输入的编号，那么要达到输出，只要如此：如果这两个相同，则前行，否则跳到上一块或下一块蝴蝶状的小网络上。

Benes网络

由两个蝴蝶网络背靠背组成，其阻塞度为。

graph LR
    subgraph Inputs
        I0[In 0]
        I1[In 1]
        I2[In 2]
        I3[In 3]
    end

    subgraph Butterfly_Forward
        L0_0(( )) --- L1_0(( ))
        L0_0 -.- L1_2(( ))
        L0_1(( )) --- L1_1(( ))
        L0_1 -.- L1_3(( ))
        L0_2(( )) --- L1_2
        L0_2 -.- L1_0
        L0_3(( )) --- L1_3
        L0_3 -.- L1_1
    end

    subgraph Butterfly_Backward
        L1_0 --- L2_0(( ))
        L1_0 -.- L2_1(( ))
        L1_1 --- L2_1
        L1_1 -.- L2_0
        L1_2 --- L2_2(( ))
        L1_2 -.- L2_3(( ))
        L1_3 --- L2_3
        L1_3 -.- L2_2
    end

    subgraph Outputs
        L2_0 --- O0[Out 0]
        L2_1 --- O1[Out 1]
        L2_2 --- O2[Out 2]
        L2_3 --- O3[Out 3]
    end

    %% 输入到第一层连接
    I0 --- L0_0
    I1 --- L0_1
    I2 --- L0_2
    I3 --- L0_3

[!] 考虑的情形，由于网络去掉首尾列再保留上半部分仍然是一个网络，可以运用归纳法证明。对的情形，简单枚举可知成立。归纳假设即命题，可将的情形拆成个的网络加上首尾的节点的情形，此时，只要较好地分配进入上下子网络的方式，就可以利用归纳假设得证。具体的，我们需要让子网络的输入端只接受一个信号，那么由于每个输入端都有两条指向他们的箭头，我们需要一种策略使得每个输入端只留下一个，输出同理。构造约束图，画出原图的输入端，把指向同一个子网络输入端的节点之间连线。节点：。边类型 A（输入）：将指向同样子网络输入端连起来，表示它们必须去往不同子网络。边类型 B（输出）：如果输入的目的地是，输入的目的地是，且属于同一个输出交换机，则将和连起来。这个约束图中每个节点的度数恰好为 2（一条输入约束边，一条输出约束边）。