通信网络数学基础建模方法

2.1 Link-path公式的网络流示例

“节点”*(node)*是识别网络中不同类型的路由或交换设备的通用术语。

“需求量”(demand volume)表示一对节点之间的流量（例如互联网或电话网络）或者所需带宽（例如同步光网络SONET），通常采用 $\hat{h}$ 表示，这样的一对节点被称为“需求对”(demand pair)，通常采用 $\langle i,j \rangle$ 表示。为了区分需求和链路，我们采用 $i-j$ 表示“链路”(link)。需求既可以是无向的，也可以是有向的，这里假设需求和链路是无向的。

如果需求对之间有多条路径可以进行路由，“需求路径-流变量”*(demand path-flow variables)*表示每条路径上分配的需求量，通常采用 $\hat{x}_{ij}$ 表示。通常需要满足公式 $\hat{x}_{12}+\hat{x}_{132}=\hat{h}_{12}$ ，其中 $\hat{x}_{12} \geqslant 0,\hat{x}_{132} \geqslant 0$ 。

“链路容量”*(link capacity)*表示直接连接的两个节点间的链路带宽，通常采用 $\hat{c}$ 表示，单位和需求量相一致。通常需要满足公式 $\hat{x}_{12}+\hat{x}_{123}+\hat{x}_{213} \leqslant \hat{c}_{12}$ 。

根据以上约束条件联立线性方程和不等式，即可得到“Link-path”公式。一般可以求出多个可行解，我们定义“可行流”*(feasible flows)*作为所有可行解的集合，通常采用 $\hat{x}$ 表示。为了从众多可行解中选取最优解，我们需要确定优化目标。假设我们的目标是最小化总路由成本，将每条路径的单个链路的路由成本设置为1，则所有流变量的总路由成本可以表示为： $F=\hat{x}_{12}+2\hat{x}_{132}+\hat{x}_{13}+2\hat{x}_{123}+\hat{x}_{23}+2\hat{x}_{213}$ 。

上述问题是“多商品网络流问题”*(multi-commodity network flow problem)*的一个例子，很容易就可以计算得到最优解为： $\hat{x}_{12}^*=5,\hat{x}_{13}^*=7,\hat{x}_{23}^*=8$ ，最佳总成本为： $F^*=20$ 。

注意：①改变目标函数会影响一个问题的最优解，以及找到它的方式，有时会非常显著。

②我们需要仔细理解和使用特定网络的正确目标或目标函数；否则，得到的最优解可能没有意义。

2.2 Node-Link公式

假设链路和需求都是有向的，并考虑固定需求对和固定节点。“流守恒定律”*(flow conservation law)*指出：考虑某个需求，进入某节点的总流量等于从该节点输出的该需求的总流量。

“弧线”*(arcs)*表示有向链路，无向链路 $1-2$ 可以被两个弧线替代： $1 \rightarrow 2,2 \rightarrow 1$ 。我们采用非负变量 $\tilde{x}_{13,12}$ 表示需求 $\hat{h}_{12}$ 在弧上分配的流量，下标的第一部分是弧 $1 \rightarrow 3$ ，第二部分是有向的需求对 $\langle i:j \rangle$ 。假设输入为负，输出为正，每个节点都可以根据流守恒定律建立线性方程。

注意：我们假设每个无向链接都由两个弧组成，并且对于每个需求对，它在其中一个弧上的流等于零，这是因为一个链路上的净流量才是真正重要的。

根据链路容量约束，我们可以建立一系列线性不等式，联立线性方程和不等式，即可得到“Node-Link”公式。

2.3 概念和符号

2.1节采用的表示法被称作“基于节点标识符的表示法”(node-identifier-based notation)，此符号会产生以下问题：

①当每条路径可能通过不同数量的中间节点时，没有一种简单的方法来表示特定需求对的多条路径。

②即使网络允许最多有两个中间节点的路径，由于节点之间的距离等问题，并不是所有有两个中间节点的路径都是可以接受的。

③该符号不能直接处理两个节点之间有多个链接的情况，即多重图(即非简单图)的情况。

④在同一对节点之间有多个需求的情况也不能显式处理。

⑤实际上难以写出多条路径求和的表达式。

为了避免上述问题，我们将采用“基于链接需求-路径标识符的表示法”(link-demand-path-identifier-based notation)。

①对需求对进行标记和映射，数字从1到D（D指需求对的总数）。

②对链路进行标记和映射，数字从1到E（E指链路的总数）。

③对路径进行标记和映射，第一个下标表示需求对编号，第二个下标表示路径编号，数字从1到P（P指对应需求可选路径的总数）。

2.4 容量设计 dimensioning problem

考虑一个设计问题，其中我们要确定承载给定需求容量所需的需求流和链路容量，有时也被称为容量设计问题（dimensioning problem）。

当link容量是给定的，则使用 $\hat{c}$ 来表示；当link容量是一个变量时，则使用 $\hat{y}$ 来表示。

链路容量单元link capacity unit (LCU)，需求量单元demand volume unit (DVU)

与此同时，一个重要的问题仍然存在：我们在哪里以及如何将该框架应用于特定网络的建模设计问题？本章提供了回答这类问题的示例。

建模的思路：理解实际的问题，然后确定什么是相关的/可能的来进行建模，以及导致多商品网络流公式的某些假设和近似是否有意义。

在本章中，我们将选择一组重要的和具有代表性的技术案例，并描述相关的设计问题和适用于这些案例的相应的多商品网络流公式。这些只是少数几个样本，而且不可能公正地对待与研究人员多年来开发的基于多种商品流的框架相关的各种建模技术和方法。此外，我们的重点将停留在公式上，即，本章将不讨论任何解决方法。这些问题将在后面的章节中讨论。

其中，我们的第一个例子是互联网域内路由中的流量工程（第3.1节）。接下来，我们在第3.2节中提出了一个多协议标签交换(MPLS)网络的隧道优化问题

3.1 IP网络：域内流量工程 (最短路径路由问题)

在我们继续检查特定的问题公式之前，我们需要回顾一些关于域内环境中的IP技术的基础知识。域内数据由一组由IP链路连接的路由器组成。如果这个域是为服务于其他提供商的网络服务提供商ISP，那么一些路由器作为边缘路由器，而其他的则作为传输路由器.

典型域内路由协议：①OSPF协议*(open shortest-path first)，②IS-IS协议(intermediate system—intermediate system)*。两者都是具有相似功能的链路状态协议，这意味着基于两种协议的路由系统使用**某种链路度量（称为链路状态）**来确定路由器之间的最短路径，并将这些最短路径映射到路由表。当一个实际的数据包到达路由器时，路由器将其转发到这个数据包目的地的最短路径的下一跳（路由器）。

重要问题：如何确定链路度量（成本），以便在确定最短路径的同时，把最小化延迟作为整体网络目标？也就是说，设计一套网络链路权重（边的权重），在所有商品网络路由之中，最小化最拥塞链路的利用率（木桶效应，即这个越小，流量越均匀）

设计目标：最小化平均包延迟 $\longrightarrow$ 最小化最拥塞链路利用率。(在1.3.1当中说明，网络设计人员，一个熟练的技术专业人员，是设计一个网络，保持延迟到一些可接受的最低限度，并减少路由器数据包的损失（由于拥塞）。也就是说只考虑由于拥塞导致的时延，所有才能完成这个问题的转换。)

为了解决这两个相互相关的问题——最小化延迟作为网络目标和确定一个适当的链接度量系统——我们需要首先要了解这个问题的流量需求量，以及多商品网络流在哪里以及如何出现。一般是通过网络流量测量工具，估计网络中任何两个边缘路由器之间的需求量。对于两个流量生成路由器之间的需求d，我们需要以Mbps为单位指定需求量 $h_{d}$ (d=1,2，…，D)。我们也可以使用链路容量单元(LCU)中给出的链路e的容量 $c_{e}$ ，在这种情况下也可以是Mbps单位。

如果一个需求d有多条最短路径，那么根据被称为“等成本多路径”(ECMP)规则，在所有最短路径之间等分流（K短路算法）。假设我们可以为需求d确定一组可能的/允许的路径p=1,2，…， $p_{d}$ （而不是假设哪一个是最短的）。现在我们用 $x_{dp}(w)$ 来表示在链路度量系统w上引起需求d的路径p上的流。因此，可得：