通信网理论分析

第 11章 通信网理论分析 11.1 图 论 基 础 11.2 最短路径算法 11.3 排队论基础 11.4 电路交换网分析 11.5 分组交换数据网分析 11.6 下一代网络性能分析 11.7 多址接入系统的分析 11.8 传输网性能分析 11.1 图 论 基 础 11.1.1 网络和图 1图的定义 设有端集： V = v1， v2， ， vn 边集： E = e1， e2， ， em 当边集 E是端集 V中两个元产生关系 R时， 则 V和 E组 成 图 G，即 G = V， E 由上述定 义 可知， 图 G中的 V集可任意 给 定，而 E集只是代 表 V集中两个元的关系。 当 Vi对 Vj有某种关系 R，为邻接关系 er时有： er E，每一个 er所对应的两个端 Vi和 Vj称为与 er有关联的端，存在 er的两个端 称为邻接端。 根据端 间 关系的性 质 ，可分 为 有向 图 和无向 图 ，当 Vi 对 Vj有某种关系等价于 Vj对 Vi有某种关系，就称 该图为 无向 图 ，反之 则 称 为 有向 图 。 图 是集合 V及其关系集 E的 综 合 V， E，集合 论 中的 许 多概念都可以移植 过 来。 若 图 A的端集和 边 集分 别 是 图 G的端集和 边 集的子集， 则 图 A是 图 G的子 图 ，表示 为 A G 若 A G 但 AG， 则 称 A是 G的真子 图 ；若 A G， A， 则 必有 A = G。且 G 2图的运算 设 A， B为任意集合。 A B称为 A与 B的并集 （ union set）， 定义为 A B = x | x A x B 称为并运算。 AB称为 A与 B的交集 （ intersection set）， 定义为 AB = x | x A x B 称为交运算。 AB称为 A与 B的差集 （ difference set）， 定义为 AB = x | x A xB 称为差运算。 A称为 A的补集 （ complement set）， 定义为 A = UA = x xA 称为补运算，它是一元运算，是差运算的特例。 说 明 图 的运算的示意 图 如 图 11.1所示。 图 11.1 图 的运算 （ 1）并图 设图 Ga、 Gb如图 10.1（ a）和（ b） 所示， Gc如图 10.1（ c） 所示。 从图中看出， Gc中的端集和边集分别是 Ga和 Gb中的端集 和边集的并，称图 Gc是 Ga和 Gb的并图。 记为 Gc = Ga Gb 对于边集和端集则有 Vc = Va Vb E = Ea Eb （ 2）交图 Gd如图 10.1（ d） 所示，则 Gd是 Ga和 Gb的交图， Gb是 Ga和 Gb的公共部分，同时有 Vd = VaVb Ed = EaEb （ 3）差 图 Ge如 图 10.1（ e）所示， 这 是从 Ga中去掉 Ga和 Gb的共有 边 和共有端，但保留未去掉的 边 关 联 的端。 Ge是 Ga和 Gb的差 图 。 记为 Ge = Ga Gb （ 4） 环 和 图 Gf如 图 10.1（ f）所示， 这 是从 Ga Gb中去掉 Ga和 Gb的共有 边 。 Gf是 Ga和 Gb的 环 和 图 。 记为 Gf = Ga Gb 一般来 说 存在 Ga Gb = GaGaGb 若 GaGb = f = 空 图 ， 则 Ga Gb = Ga+Gb，称 为 它 们 的直和。 若 Gb Ga = GaGb，称 为 它 们 的直差。 11.1.2 图的矩阵表示 射出 边 射入 边 1图的关联阵表示 关联阵是表达图的端与边的关联性的矩阵。 若图含有 m条边， n个端，则图的关联阵 A0是行数为端数， 列数为边数的 nm阵， A0 = aijnm 对于无向图则有 对于有向图而言，则有 关 联 矩 阵计 算用 书 如 图 11.2所示， 对 于如 图 11.2所示的有向 图 ，其关 联 矩 阵 可表示 为 ： 图 11.2 关联矩阵计算用图 从 图 的关 联 矩 阵 可以 进 一步来 计 算 图 的生成 树 的数量 。 连 通 图 的生成 树 的数量可以用以下公式来表示： （ 11.1） 式中 A是 连 通 图 的关 联 矩 阵 ， AT是 A阵 的 转 置。 即此 图 有生成 树 21棵。 以上所 讨论 的 图为 有向 图 ， 对 于无向 图 ，可以在 图 上 任意加箭 头 ，得到相 应 的有向 图 ， 这样 就可求得无向 图 的 生成 树 的数目。 以图 11.2为例，关联阵 A为式（ 11.1）所示，生成树数目 可以由上式算得： 2图的邻接阵的表示 图也可以用端与端之间的关系矩阵，即邻接阵来表示，邻 接阵的行和列都与图的端相对应。对于一个有几个端的图，邻 接阵是一个 nn的方阵，即 其中 对 于 图 11.2所示的有向 图 ，其 邻 接 阵为 （ 11.2 ） 对 于无向 图 ， 则 有 cij = eij 因此，无向 图 的 邻 接 阵 是一个 对 称 阵 。 1树和生成树 树是图论中一个十分重要的概念，在网络的组播，路由 选择中都有着广泛的应用，下面说明树的定义以及树的求法。 树定义为一个不包括环路的连通图，它具有以下性质。 树是无环的连通图，当对于任何不同的节点 i和 j都有 一个从 i到 j的路由时，图是连通图。 树是最小的连通图，即树中去掉任一边就成为非连通 图，失去了连通性，所以是最小的连通图。 若树有 m条边及 n个端，则有 m = n1 这可用数学归纳法来证明。因此，树可定义为有 n个端， n1条边的连通图。 树 的例子如 图 11.3所示。 图 11.3 树 的例子 生成 树 是 树 中的重要一 类 ，下面 说 明它 们 的定 义 。 设 T是 连 通 图 G的子 图 。 T G，若 T含有 G的所有端， 则 称 T是 G的生成 树 ，也就 是 说 生成 树 是覆盖 连 通 图 所有端的 树 。 只有 连 通 图 才有生成 树 ，反之，有生成 树 的 图 必然是 连 通 图 。 对于图中的某一生成树而言，生成树上的边称为树枝，非 树枝的边称为连枝，生成树就是树枝集，连枝的边集称为连树 集或树补。 在通信网的设计过程中，常涉及以下的问题：已给定一组 固定的节点，在这些节点上找出一颗使全部链路的权值最小的 生成树。这里的链路的权值，可以表示各种度量值，如费用、 距离、带宽、时间延迟等。 在某些情况下，所求的树可能还受到某些约束条件的限制 ，如一个典型的约束就是：必须把节点连通而使它们承载的业 务量不致造成链路过载。 求最小生成树的，需要借助于有效的算法，下面首先讨论 求解具有最小权但不受任何约束的一颗树的算法，然后找出有 约束条件的具有最小权的树。 2无约束的最小生成树 （ 1）普列姆（ Prim）算法 Prim算法具体操作是：从图中任意一个顶点开始， 首先把这个顶点包括在 MST里，然后在那些其一个端点已 在 MST里，另一个端点还不是 MST里的边，找权最小的一 条边，并把这条边和其不在 MST里的那个端点包括进 MST 里。如此进行下去，每次往 MST里加一个顶点和一条权最 小的边，直到把所有的顶点都包括进 MST里。 假设 V是图中顶点的集合， E是图中边的集合， TE 为最小生成树中的边的集合，则 prim算法的步骤如下。 初始化： U = u0， TE = e0 。此步骤设立一个只有节 点 u0的节点集 U和一个空的边集 TE作为最小生成树的初始状态 。 在所有 u U， v VU的边 (u， v) E中，找一条权最小 的边（ u0， v0），将此边加进集合 TE中，并将此边的非 U中顶点 加入 U中。 如果 U = V，则算法结束；否则重复步骤 2。可以把本步 骤看成循环终止条件。 该算法的特点是当前形成的集合 T始终是一棵树。将 T中 U 和 TE分别看作红点和红边集， V-U看作蓝点集，算法的每一步均 是在连接红、蓝点集的紫边中选择一条轻边扩充进 T中。 MST性 质保证了此边是安全的。 T从任意的根 r开始，并逐渐生长直至 U = V，即 T包含了 C中所有的顶点为止。 MST性质确保此时的 T 是 G的一棵 MST。 图 11.4 PRIM算法用图 依 P算法可 顺 序得 d23最小 d24最小 d21最小 d26最小 d45最小 其 邻 接 阵为 树 枝的 总长 度 为 （ 2）克鲁斯格尔（ Kruskal）算法 K算法每次选择 n1条边，所使用的准则是：从剩下的边中 选择一条不会产生环路的具有最小权值的边加入已选择的边的 集合中。注意到所选取的边若产生环路则不可能形成一棵生成 树。 K算法分 e步，其中 e是网络中边的数目。按权值递增的顺 序来考虑这 e条边，每次考虑一条边。当考虑某条边时，若将其 加入到已选边的集合中会出现环路，则将其抛弃，否则，将它 选入。 假设 W = (V， E)是一个含有 n个顶点的连通网， K算法的步骤如下。 先构造一个只含 n个顶点，而边集为空的子图，若将该子 图中各个顶点看成是各棵树上的根节点，则它是一个含有 n棵树 的一个森林。 从网的边集 E中选取一条权值最小的边，若该条边的两个 顶点分属不同的树，则将其加入子图，也就是说，将这两个顶 点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点 已落在同一棵树上，则不可取，而应该取下一条权值最小的边 再试之，依此类推。 直至森林中只有一棵树，也即子图中含有 n1条边为止 。 仍用 图 11.4来 说 明此算法。此 时 得到： 形成 环 路， 删 去 这 条 边 。 形成 环 路， 删 去 这 条 边 。 G7就是最小生成 树 ，如 图 案 11.4所示。 3有约束条件的最小生成树 图 11.5 E-W算法用图 E-W 算法用 图 如 图 11.5所示， 图 中 v1是中心 节 点， 其他 2、 3、 4、 5为 端站， 链 路上的 权值为 dij(i， j=1， 2 ， ， n)，各个端站的 业务 量 为 Fi(i = 2， 3， ， n)， dij的 值 示于 图 11.5的 边 上，各个端站的 业务 量示于 图 11.5的端的 边 上。 约 束条件：要求任意一个端所到 vj的 链 路数（ 边 数 ）小于 k，即 转 接次数小于 k 1， 边 上的 总业务 量不大 于 M。 其中 k是 给 定的整数，而 M是 给 定的 实 数，本例中 设 k=3， M=50分 组 /秒 ， 求符合 约 束条件的最小生成 树 。 根据公式 eij = dij D1i 计 算的 eij的矩 阵为 矩 阵 中 e34最小，取 该边 。 经 核 对满 足 约 束条件。 重新 计 算 eij的矩 阵 得 取 已有 边 。 相 连 后， 总业务 量 = 10 + 40 + 30 = 80，不符合 约 束条件。 ， ， ，均不符合 约 束条件。 ， 满 足 约 束条件，取 该边 。 ，符合 约 束条件。 ，符合 约 束条件。 ，不符合 约 束条件。 取 取 取 取 取 得如图 11.6的解。 业务量如图 11.6所示，节点上的数字为该节点的业务量。 图 11.7是无约束条件下的最小生成树，可以和有约束条件 下的生成树加以比较，说明约束条件在求解过程中的影响。 图 11.6 有约束条件下的最小生成树 图 11.7 无约束条件下的最小生成树 11.2 最短路径算法 11.2.1 Bellman-Ford算法 Bellman-Ford算法（也叫做 Ford-Fulkerson算法）是用 以求解到固定点的最短路径算法。其原理是：如果某个节点在 A和 B之间的最短路径上，则该节点到 A的路径必定是最短路径 ；同样，该节点到 B的路径也必定是最短路径。 图 11.8 Bellman-Ford算法用图 假定希望求得图 11.8中节点 2到节点 6（目的地）的最短 路径，为了到达目的地，节点 2的分组必须首先通过节点 1、 节点 4或节点 5中的某个节点。如果已经知道节点 1、节点 4、 节点 5到目的地（节点 6）的最短路径分别是 3、 3、 2，这样 ，如果节点 2的分组首先通过节点 1，则总距离（也可叫做总 费用）就等于 3+3 = 6；如果分组首先通过的是节点 4，则总 距离是 1+3 = 4；如果分组首先通过的是节点 5，则总距离是 4+2 = 6。因此，从节点 2到目的地的最短路径就是分组首先 通过节点 4时所得到的路径。 为了使这种想法形式化，首先固定目的地节点，并定义 Dj是 节点 j到目的地的最小费用（或最短距离）的当前预测值； Cij是 节点 i到节点 j的线路费用。例如，在图 11.8中， C12 = C21 = 2， C45 = 3，而从节点 i到其自身的费用定义为 0（即 Cii = 0）。如果 节点 i到节点 k之间没有直接相连的线路，则它们之间的线路费用 定义为无穷大。例如，在图 11.8中， C15 = C23 = 。根据这些定 义，可以求得从节点 2到目的地节点（节点 6）的最小费用为 D2 =min C21 + D1， C24 + D4， C25 + D5 =min 3 + 3， 1 + 3， 4 + 2 = 4 因此，节点 2到节点 6的最小费用为 4，且下一个访问的节点 是节点 4。 在计算节点 2到节点 6的最小费用时，假定已经知道了节点 1、 4、 5分别到目的地的最小费用。而实际上，这些节点并没 有执行同样的计算，它们到目的地的最小费用并不是已知的， 因此，为了得到这些节点的最小费用，应用同样的原理对这些 节点进行计算。例如， D1 =min C12 + D2， C13 + D3， C14 + D4 D4 =min C41 + D1， C42 + D2， C43 + D3， C45 + D5 可以看出，由于 D2依赖于 D1，而 D1又依赖于 D2，因此这些 方程是循环的。 只要不断地对这些方程进行迭代和更新，这个算法将收敛 到正确的结果。 例：利用 Bellman-Ford算法，求出图 11.8中每个节点到节 点 6（目的地节点）的最小费用，并求出沿最短路径的下一个节 点。 现在用符号（ n， Di）表示每个节点，这里 n是沿当前最短 路径的下一个节点， Di是节点 i到目的地的当前最小费用。从给 出最小费用的方程中的 j值可以求得下一个节点。如果下一个节 点没有定义，就将 n设置为 1。 v 现在用符号（ n， Di）表示每个节点，这里 n 是沿当前最短路径的下一个节点， Di是节点 i 到目的地的当前最小费用。从给出最小费用 的方程中的 j值可以求得下一个节点。如果下 一个节点没有定义，就将 n设置为 1。 表 11.1所示为 Bellman-Ford算法在每次迭代结束时的结果 。由于第 3次迭代结束后不再有变化出现，因而算法在此时结束 。表中的最后一行即每个节点到节点 6的最短路径费用及该路径 上的下一个节点。 表 11.1 Bellman-Ford算法计算结果示例 迭 代 节点 1 节点 2 节点 3 节点 4 节点 5 初始化 （ 1， ） （ 1， 77） （ 1， ） （ 1， ） （ 1， ） 1 （ 1， ） （ 1， ） （ 6， 1） （ 3， 3） （ 6， 2） 2 （ 3， 3） （ 4， 4） （ 6， 1） （ 3， 3） （ 6， 2） 3 （ 3， 3） （ 4， 4） （ 6， 1） （ 3， 3） （ 6， 2） 对于上面的例子，可以画出每个节点到目的地节点的最短路 径。由表 11.1中的最后一行可以看出，在每个节点的最短路径 上，节点 1的下一个节点是节点 3；节点 2的下一个节点是节点 4 ；节点 3的下一个节点是节点 6，等等。 Bellman-Ford算法的一个良好特性是它容易分布 实现 ， 这 样 ，每个 节 点就可以独立 计 算 该节 点到每个目的地的最小 费 用 ，并将最小 费 用矢量周期地广播 给 它的 邻 居 节 点。 为 加快收 敛 ，路由表中的 变 化也可用来触 发节 点向它的 邻 居 节 点广播最小 费 用， 这 种技 术 叫做触 发 更新。可以 证 明，在适当的假 设 条件 下，分布式算法也可以收 敛 到正确的最小 费 用上。一旦收 敛 ， 每个 节 点就会知道每个目的地的最小 费 用以及最短路径上相 应 的下一个 节 点。由于相 邻节 点之 间 交 换 的只有 费 用矢量（或距 离矢量），分布式 Bellman-Ford算法也常常被称 为 距离矢量算 法。参与距离矢量算法的每个 节 点都按下述方程 进 行 计 算： Dii = 0 Dij = mink Cik + Dkj， 这 里， Dij是 节 点 i到目的地 节 点 j的最小 费 用。一旦更新， 节 点 i就向它的相 邻节 点广播矢量 Di1 Di2 Di3 。分布 实现 方 式能 够 适 应线 路 费 用 变 化或者是拓扑 结 构 变 化的网 络 。 k i 11.2.2 Dijkstra算法 1 Dijkstra算法的原理 图 11.9 Dijkstra算法用图 利用图 11.9中所示的网作为例子来讨论 Dijkstra算法，其目的 是求出源节点到网中所有其他节点的最短路径。在求解过程中 ，采取步进的方式，建立一个以源节点 1为根的最短路径树，直 到包括最远的节点在内为止。到第 k步，计算出到离源节点最近 的 k个节点的最短路径。这些路径定义为在集 N内。 设 D(v)为 从源 节 点 1到 节 点 v的距离， l(ij)为节 点 i和 j之 间 的 距离。算法分两步 执 行。 第 1步：初始化。令 N = 1。 对 于不在 N中的每个 节 点 v， 设 置 D(v) = l(1， v)。（ 对 于与 1不直接相 连 的 节 点取 为 ） 第 2步：找到一个不在 N中的使 D(w)最小的 节 点 w，并将 w加 进 集 N中去，然后 计 算下式，以修改不在 N中的所有其他 节 点 的 D(v)： D(v)minD(v)， D(w)+l(w， v)（ 11.5） 重复第 2步直至全部 节 点包括在 N中。 表 11.2所示为求图 11.10中节点 1到其他节点最短路径的过程。 在表中画圆圈的数字表示该步骤中 D(w)的最小值。这样， 相应的节点 w就加到 N中， D(v)的值就按要求更改。因此，在初 始化后的第 1步，距离最小 D(4) = w，节点 4就加进集合 N中；在 第 2步， D(5) = 2，节点 5加进 N中；如此不断继续下去。第 5步 以后，所有的节点都在 N中，算法终止。 表 11.2 算法的计算过程 步 骤 N D（ 2） D（ 3） D（ 4） D（ 5） D（ 6） 初始 1 2 5 1 1 1， 4 2 4 2 2 1， 4， 5 2 3 1 4 3 1， 2， 4， 5 3 1 2 4 4 1， 2， 3， 4， 5 2 1 2 4 5 1， 2， 3， 4， 5， 6 2 3 1 2 图 11.10（ a）中示出了以源节点 1为根的最短距离树。它 的产生过程是：当一个节点加入集合 N时，它就连接到已在 N中 的适当点。每个节点下面圆圈内的数字代表在第 n步该节点加 入树的结构。由节点 1的最短距离树可以得到节点 1的路由选择 表，如图 11.10（ b）所示。该表指明了到相应的目的地节点所 应选的下一节点。同理，可以求得节点 2， 3， ， 6的路由选 择表。 图 11.10 节点 1到其他节点的最短距离 2 Dijkstra算法的应用 Dijkstra算法有时也被称为 SPF算法，这是因为最短路径优 先算法 SPF是 Dijkstra发明的。 SPF算法是 OSPF路由协议的基 础。该算法将每一个路由器作为根（ root）来计算其到每一个 目的地路由器的距离，每一个路由器根据一个统一的数据库会 计算出路由域的拓扑结构图，该结构图类似于一棵树，在 SPF 算法中，被称为最短路径树。在 OSPF路由协议中，最短路径树 的树干长度，即 OSPF路由器至每一个目的地路由器的距离，称 为 OSPF的 Cost。 作为一种典型的链路状态的路由协议， OSPF还得遵循链路 状态路由协议的统一算法。链路状态的算法非常简单，在这里 将链路状态算法概括为以下 4个步骤。 当路由器初始化或当网络结构发生变化（例如增减路由 器，链路状态发生变化等）时，路由器会产生链路状态广播数 据包（ Link-State Advertisement， LSA），该数据包里包含 路由器上所有相连链路，即所有端口的状态信息。 更新自己的数据库，并将该链路状态信息转送给与其相 邻的路由器，直至系统稳定。 当网络重新稳定下来，也可以说 OSPF路由协议收敛下 来时，所有的路由器会根据其各自的链路状态信息数据库计算 出各自的路由表。该路由表中包含路由器到每一个可到达目的 地的 Cost以及到达该目的地所要转发的下一个路由器。 当网络状态比较稳定时，网络中传递的链路状态信息是 比较少的，或者说，当网络稳定时，网络中是比较安静的。这 一点实际上是 OSPF路由协议的一个特性，这也正是链路状态路 由协议区别于距离矢量路由协议的一个特点。 v Edsger Wybe Dijkstra (May 11, 1930 August 6, 2002); Dutch pronunciation: ) was a Dutch（荷兰） computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000. v Shortly before his death in 2002, he received the ACM PODC Influential Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize the following year, in his honor. v Dijkstras algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. v 1 function Dijkstra(Graph, source): v 2 for each vertex v in Graph: / Initializations v 3 distv := infinity ; / Unknown distance function from source to v v 4 previousv := undefined ; / Previous node in optimal path from source v 5 end for ; v 6 distsource := 0 ; / Distance from source to source v 7 Q := the set of all nodes in Graph ; / All nodes in the graph are unoptimized - thus are in Q v 8 while Q is not empty: / The main loop v 9 u := vertex in Q with smallest distance in dist ; v 10 if distu = infinity: v 11 break ; / all remaining vertices are inaccessible from source v 12 end if ; v 13 remove u from Q ; v 14 for each neighbor v of u: / where v has not yet been removed from Q. v 15 alt := distu + dist_between(u, v) ; v 16 if alt 1/m2时 ，相 应 的平均 队长 和 时 延也随之增 大。另一方面，当 s2 1）组成，则在网路中传送时在系统中的平均 时延由下式计算： （ 11.61） 式中， 1/mF是全 满 数据分 组长 度， 单 位 为 bit（一般情况下， 1/mF 1/m，因 为 1/m是所有数据分 组 的平均 长 度，其中也包括 小于全 满长 度分 组 ）： 是全网 总 消息通 过 量， 单 位是（数据分 组 /秒）； 是 链 路平均利用率； 是消息 经过 的平均 链 路数； 是一个全 满 分 组 就所有 链 路 进 行平均的 传输时间 。 （ 11.62） （ 11.63） （ 11.64） （ 11.65） 11.5.3 分组交换吞吐量 除了用平均分 组时 延表示分 组 交 换 网的性能外， 还 有网 络 吞吐量。吞吐量是 单 位 时间 内 传 送成功的分 组 量。当 输 入 节 点的分 组 数在其 传输 容量范 围 以内 时 ，它将全部 输 出送往目 的地， 输 入与 输 出数量成比例， 输 入分 组 数接近 输 出容量 时 吞吐量 趋 于 饱 和。然而 实际 情况是，当 输 入量增加太快 时 ， 交 换节 点或路由器不再能 够应 付， 输 出分 组 数反而下降， 导 致情况 恶 化。在通信量非常高的情况下，网 络 完全阻塞，几乎 没有分 组 能 够发 送。 输 入 负 荷与吞吐量的关系如 图 11.32所示 。 造成拥塞的原因很多，如果突然之间分组流同时从多个输入 线到达，并且要求输出到同一线路，就将建立起队列。如果没 有足够的缓冲空间保存这些分组，有些分组就会丢失，在某种 程度上增加缓冲器容量会有所帮助。 图 11.32 分组交换网输入负荷与吞吐量 处理器的速度慢也会导致拥塞。如果路由器的 CPU处理速 度太慢，以至于不能正确执行像缓冲区排队、更新路由表等操 作，那么即使有多余的线路容量也可能使队列饱和。类似地， 低带宽线路也会导致拥塞。只升级线路不提高处理器性能，或 反之，不会有多大作用。 拥塞会导致恶性循环，如果节点没有空余缓冲区，它必须 丢掉新到的分组，当扔掉一个分组时，发送分组的节点会因超 时而重传该分组（可能重传多次）。由于发送方在没有收到确 认之前不能扔掉该分组，故接受端的拥塞迫使发送者不能释放 在正常情况下早应释放了的缓冲区，使拥塞加重。 11.6 下一代网络性能分析 11.6.1 下一代承载网的 QoS 1时延 由于当前 IP分组网使用低比特语音编解码器，使得 VoIP语 音分组的端到端时延要比电路交换网中的时延大得多，组成部 分也更为复杂， VoIP应用中网络通信结构和底层传输协议的多 样性，决定了时延成分的多样性。 端到端的时延可以分成两个部分，即固定时延和可变时延 。固定时延包括编解码器引入的时延和打包时延。固定时延和 采用的压缩算法、打包的语音数据量相关。可变时延包括承载 网上的传输、节点中排队、服务处理时延和去抖动时延，这些 和设备的端口速率、网络的负载情况、经过的网络路径、设备 对 QoS的支持方式、实现的 QoS算法等密切相关。 特别是去抖时延和承载网络的抖动指标密切相关，通过采 用合适的网络技术可以显著降低语音通过网络时引入的抖动， 减少去抖动时延。 IP网中语音分组的端到端时延， 100ms以下的时延，对 于大多数应用来说是可接受的； 150 400ms的时延，在用户 预知时延状况的前提下可以接受；大于 400ms的时延不可接受 。 目前，不同级别的网络设备，在正常情况下的数据包处理 时延为几十微秒到几毫秒，能够满足单跳时延要求，但承载网 的跳数设计不能超过以上端到端的时延要求，而且跳数越少越 好。 2时延抖动 时延抖动是指时延在平均值上下的起伏，根据实际测量发 现，抖动大于 500ms是不可接受的，而抖动达到 300ms时， 是可以接受的，此时为了消除抖动会引起较大的时延，综合时 延对语音质量的影响来考虑，要求承载网的抖动小于 80ms。 抖动会引起端到端的时延增加，会引起语音质量的降低。 影响抖动的因素一般和网络的拥塞程度相关。网络节点流量超 忙，数据包在各节点缓存时间过长，使得到达速率变化较大。 由于语音同数据在同一条物理线路上传输，语音包通常会由于 数据包的突发性而导致阻塞。 3丢包率 丢包率的形成原因主要有两点，一是传统 IP传输过程中的 误码，这种情况在目前的网络条件下发生的概率极低。另一个 是不能保障业务带宽造成的，当网络流量越拥塞，影响就越强 烈，丢包发生率也就越大。 丢包对 VoIP语音质量的影响较大，当丢包率大于 10%时 ，已不能接受，而在丢包率为 5%时，基本可以接受，因此，要 求 IP承载网的丢包率小于 5%。 软交换网对 IP承载网的要求包括媒体流和信令流两部分， 其中媒体流对承载网的最高 QoS指标为时延 100ms、时延抖 动 10ms、丢包率 1%；信令流对承载网基本 QoS的要求为： 时延 100ms、时延抖动 10ms、丢包率 0.1%、包差错率 10 。 4 11.6.2 承载网分组语音节点的时延 对 于分 组 网 络 中的 语 音 业务 ，采用排 队 模型来描述它。最直 观 的排 队 模型是： 输 入流看作是多周期流的叠加。 对 于分 组语 音网 络节 点，用 /D/1排 队 模型来代表 这 一 类 的 节 点。 排 队 模型，其 输 入 过 程是固定数量周期流的叠加，而其中的 每一流的特征是固定服 务时间 分布，而流的相位 则 是随机 选择 的。 根据 /D/1排 队 模型来 计 算由 语 音 业务 流 产 生的排 队 延 M/D/1排 队 之 间 的性能 进 行了比 较 ，在 链 路的利用率是高的 , 复用流是少量的情况下， M/D/1排 队 模型的 计 算 结 果偏大，而 对 于 链 路利用率是低的，复用的流 较 多的情况下， M/D/1和 /D/1的排 队 模型 应 用在 IP的网 络 中 时 延的 计 算 结 果是相近的。 /D/1 迟，也可导出缓冲器的需求值。有文献对于 /D/1和较简单的 因此，在大多数情况下，用 M/D/1来代替 时 延的估算同 样 有 较 大的准确性。 /D/1排队模型，对 软 交 换 网 络 中的 语 音通信量是基于分 组语 音技 术进 行的， 其排 队时 延可采用 M/D/1/队 列模型来 处 理。 M/D/1排 队 是 M/G/1排 队 中的一个特例。其求解可以根据 p-k公式来 进 行分析。 M/D/1排 队 ，字母 D表示确定的（ deterministic）服 务时间 。 这 是 M/G/1排 队 的一个特例，作 为 一个特例，令所有 顾 客（分 组 或呼叫）都具有相同的服 务长 度 1/m。 这样 ， s 2= 0， 则 有： 以及 （ 11.66） 以下 给 出 软 交 换 网 络时 延分析的例子。 例： 设软 交 换 网 络节 点是 M/D/1排 队 模型，分 组 到达率 70 000分 组 /秒，分 组 的平均 长 度 为 1 000bit， 链 路容量 为 155Mbit/s，求 节 点的平均 时 延和平均 队 列 长 度。 解： 平均 队 列 长 度 平均 时 延 = 0.009 1ms = 0.43 11.6.3 软交换网络的容量 软交换设备的容量通过设备的处理能力来表示，可利用忙时 呼叫处理能力（ BHCA）表示，信令网关设备的处理能力可以 通过 BHCA或信令链路数表示，中继媒体网关设备的处理能力 可以通过中继端口 DS0（ Digital Signal 0）数目来衡量。无论 测算的目标网络设备为何种类型，其测算的基本前提都包括 3 类参数：业务特性参数、业务流量流向参数和网络结构参数。 业务特性参数是与 NGN业务特性相关的参数，如语音业务的平 均通话时长；业务流量流向参数是端到端的业务量大小；网络 结构参数是指与网络结构方案相关的参数，如软交换服务区的 覆盖、 POP点范围、软交换设备数目等。 式中 Abi软 交 换 局或 软 交 换 网 络 忙 时输 入 话务 量 , 单 位取 爱 尔 兰 。 Ta为 一次呼叫的平均 时长 BHCA指的是交换系统在系统最忙时段所能支持的最大呼叫 次数。饱和呼叫量可以用两个参数来表示：忙时处理呼叫量（ BHCA）或者每秒处理呼叫数量（ CAPS）。 对于软交换网络的容量采用 BHCA即忙时呼叫处理次数来衡 量，对于传统的电路交换网，网络的容量采用所支持的电话门 数来衡量。 软交换网络以分组网作为承载网，已无门数的概念，则用忙 时呼叫处理能力来评价。设软交换局的忙时输入话务量为 Abi， 则软交换局的容量 BHCA可表示为 上述公式可用于软交换网容量的规划，经过预则得到软交换 网的忙时输入话务量，经过计算后可得到软交换的容量。据此可 以对处理器的能力提出要求。 BHCA和处理器的能力之间的关系可利用公式进行分析： s = a+bBHCA 其中： s：系统开销，是处理机时间资源的占用率； a：固有开销，是非与呼叫处理次数（话务量）无关的系统开销 ； b：处理一次呼叫的平均开销（非固有开销），是与呼叫处理次 数有关的系统开销； 例：某处理机忙时用于呼叫处理的时间开 销平均为 0.85，固有开销 a = 0.29，处理一个呼叫平均需时 32ms ，求其 BHCA为多少？ 0.85 = 0.29+(32103/3 600)BHCA BHCA = 63 000次 /小时 11.7 多址接入系统的分析 11.7.1 ALOHA技术 CSMA/CD（ Carrier Sense Multiple Access with Collision Detection）即具有冲突检测的载波侦听多址访问方法 ，是一种常用的随机访问方法。 在纯 ALOHA方式中，当某一站有数据分组需要发送时，它被 立即发出。如果收到 ACK信号，则表示发送成功；如果在规定的 时间内未收到 ACK信号，则该站重发此分组。由于每一站的分组 的发送都是随机的，因此，就存在两个站同时发送而产生冲突现 象。即使是前一个分组的最后一位和后一个分组的最前一位发生 重叠，也会造成这两个分组不能正确接收。当冲突现象发生以后 ，数据站隔一段时间重发该分组。 图 11.33（ a）所示 为纯 ALOHA方式中数 据分组发送、冲突、再 发送的过程。 图 11.33 ALOHA系统原理 时隙 ALOHA是纯 ALOHA的改进型式。在这种方式中，把 时间分成长度为 t的时隙，各个站只能在每个时隙的前沿发送数 据分组。这时，如果两个站同时发送而发生冲突，则两个数据分 组完全重叠，而不可能发生两个分组局部的重叠，这时发生冲突 的最大时间间隔为 t（一个分组的长度）。图 11.33（ b）所示为 时隙 ALOHA系统的原理。 设 G为时间 t内 发 送的 总 的分 组 数目，即网 络 的 总 的承 载负 荷； S为时间 t内 传输 成功的分 组 的数目，即网 络 的吞吐量；假 设发 送分 组 的数目服从泊松分布， 则 在 时间 t（一个分 组长 度）内 发 送 n个分 组 的概率 为 对 于 纯 ALOHA系 统 ， 发 生冲突的最 长时间间 隔 为 2t，在 时间 2t内不 发 送分 组 的概率 为 P0 = e2G，利用 S = GP0，可以得 到： S = Ge2G （ 11.67） 对 于 时 隙 ALOHA系 统 ， 发 生冲突的 时间间 隔 为 t，只要在 t内不 发 送分 组 ， 则 原来的分 组 将 传输 成功。可以得到： S = GeG （ 11.68） S与 G之间的关系如图 11.34所示。图中， S和 G均已归一化 。从图中可见，纯 ALOHA系统的最大吞吐量发生在 G = 0.5处， 而对应的 S值是 1/(2e)，即约为 0.184。而时隙 ALOHA的 S可能的 最大值为 1/e，即为 0.37。由于时隙 ALOHA系统采取了把时间分 成时隙的措施，它的有效吞吐量增加了 1倍。 图 11.34 ALOHA系统 S与 G之间的关系 11.7.2 CSMA技术、 CSMA/CD技术1 CSMA CSMA（载波侦听多此访问）技术是在随机访问技术的基 础上发展起来的。数据站在传输分组之前，首先对媒质进行监 听，以确定媒质是否已被其他站占用。如果媒质是空闲的，则 该站可以发送数据分组，否则，该站以某种算法延迟一段时间 以后再重新传输。在分组传输以后，需要等待对方的肯定答复 。 CSMA系统根据数据分组传输所遵守的规则又可以分为非 坚持 CSMA、 1-坚持 CSMA和 P-坚持 CSMA。 采用非坚持 CSMA，数据站在传输时遵守如下步骤。 对媒质进行监听，如果媒质闲就传输。 如果媒质忙，则等待一定的时间间隔后，再重复步骤 。 所等待的时间间隔是按一定的概率分布的。 在发现媒质忙以后再随机地等待一段时间，一方面可以减 小冲突，另一方面有可能使信道处于空闲状态。 1-坚持 CSMA进行分组传输时遵照下列步骤。 对媒质进行监听，如果媒质闲就传输。 如媒质忙，则继续监听，直至检测到媒质闲后立即传输。 如果不收 ACK信号，则等待一段随机量时间后重复步骤 。 p-坚持 CSMA是上述两种方法的一种折中，所遵循的步骤如 下。 对媒质进行监听，如果媒质闲，以概率 P传送数据，以概率 1P延迟一段时间间隔，该时间间隔通常等于最大传播延迟。 如果媒质忙，则重复步骤 。 如果延迟一段时间间隔后，则重复步骤 。 2 CSMA/CD技术 CSMA/CD技术是在 CSMA技术的基础上增加了冲突检 测，从而更进一步提高了信道的利用率。采用 CSMA技术时， 虽然在发送前进行载波侦听，但两个站发送的数据仍有可能发 送冲突。一个简单的例子是两个站同时侦听，在都发现媒质空 闲以后同时传输，则造成数据的冲突，而且发送方一直要等到 不能收到 ACK信号以后才知道数据发生了冲突。 CSMA/CD技 术是在发送数据后对冲突进行检测，如果检测到冲突，该站立 即停止发送数据分组，并发出一个短暂的阻塞信号。在发出阻 塞信号以后，再等待一段随机量时间，然后再采用 CSMA进行 传输。 冲突 检测 有不同的方法。基 带传输则 接收机 检测 高于 预 期 的 电压电 平； 宽带传输则 接收机把 发 送的数据和接收到的数 据 进 行逐比特的比 较 ，如果不一致 则说 明 发 生了冲突。 当冲突 发 生后， 该 站延 迟 一段随机量 时间 以后再重新 传 送。随机量 时间 的确定按照某种算法 进 行，常用的算法之一是 截断的二 进 制指数退避算法， 这时 延 迟时间 T表示 为 T = rt1 式中， r是在 2k 1和 0之间均匀分布的随机数， k = min(i ， 10)， i是已发生冲突的次数， t1等于 2倍传播时间。当冲突次 数大于 16时，则按照故障处理。 CSMA/CD技术的流程图如图 11.35所示。采用 CSMA/CD 技术并适当地选取延迟时间，可使信道的利用率达到 90%。 图 11.35 CSMA/CD技术的流程图 3 CSMA技术、 CSMA/CD技术性能分析 以下对 CSMA技术、 CSMA/CD性能进行分析。 设：帧为定长，一帧的发送时间为 T0， T为最大端到端的传输时延 a =T/T0称为归一化的传播时延； S为吞吐量； G为网络负载。 CSMA按监听到信道忙之后的策略可分为以下几种。 非坚持 CSMA：一旦监听到信道忙，就不再监听；延迟一个 随机时间后再次监听。 坚持 CSMA：监听到信道忙时，仍继续监听，直到信道空闲 。 1-坚持 CSMA：一听到信道空闲就立即发送数据（以概率 1 发送）。 p-坚持 CSMA：听到信道空闲时，以概率 p发送数据，即以 概率 1-p延迟一段时间后再发送。 以上策略都可以分 为 有 时 隙的和非 时 隙的， 则 有： 纯 ALOHA: S = Ge 时 隙 ALOHA： S = Ge 非 坚 持 CSMA： S = 时 隙非 坚 持 CSMA： S = 1-坚 持 CSMA： S = 时 隙 1坚 持 CSMA： S = ALOHA和几种 CSMA的性能 对 比如 图 11.36所示。 图 11.36 几种 CSMA与 ALOHA的 S-G曲线 由图上可以看出，由于 CSMA采用了先监听再发送的技术，而 不是像 ALOHA一样随意且盲目地发送，因此有效地减少了发生 冲突的概率，因此，网络的性能也得到了明显的改善，主要体现 在网络的吞吐量上面。从图中还可以看出，轻载时， 1-坚持 CSMA吞吐量最大；重载时，非坚持 CSMA吞吐量最大，因此， 可以根据实际的网络负荷来选择相应的随机接入机制，以获得最 佳的网络性能。 对 CSMD/CD性能 进 行分析，可得到： 对当 a = 0.01时，几种 CSMA/CD、 CSMA以及 ALOHA的 S-G 曲线如图 11.37所示。 图 11.37 当 a = 0.01时几种 CSMA/CD