信息通信网络概论：Chapter3 Fundamentals of Communication Networking Theory

Ch3FundamentalsofCommunicationNetworkingTheory概念：优化网络结构、优化网络运行管理网络拓扑学——讨论网络的连通性、最短树、最大流等静态理论。排队论——讨论业务的阻塞率、丢失率、延迟时间、通过率等由于业务的随机性造成的对网络性能的影响。实际网络规模巨大、业务具有很强的随机特性

了解基本理论问题，借助近似数值分析和网络仿真。第3章通信网理论基础3.1网络拓扑与通信网结构3.2排队论通信网业务分析与优化3.3通信网的可靠性3.4多址接入系统分析

第3章通信网理论基础3.1网络拓扑与通信网结构3.1.1网络拓扑基础3.1.2通信网结构设计3.2排队论通信网业务分析与优化3.3通信网的可靠性3.4多址接入系统分析

3.1.1网络拓扑基础0.图及其运算1．节点的度数2．边序列、链、径、环3．联结图4．树5．联结图的主树6．割和环7．图的矩阵表示8．图的权0.图及其运算网络拓扑(Topology)的基础:图论(GraphTheory)

图G={V，E}，节点V(Vertex,Vertices),节点间连线即边E(Edge)有向图、无向图、空图和孤点图

0.图及其运算子图：若A的节点集与边集分别为G的节点集与边集的子集，则A为G的子图。若AG，且AG，则A为G的真子集真子集---G中至少有一个元素不在A内若A=G，则AG，AG0.图及其运算图的运算：设A={e1，e2},e1=（v1，v3）,e2=（v3，v2）设B={e1，e3},e1=（v1，v3）,e3=（v1，v4）0.图及其运算并：A∪B={e1，e2，e3}——A，B所有元素组成交：A

∩B={e1

}——A，B公共元素

若A∩B=φ，则A∪B=A+B称直和AυBA∩B0.图及其运算差：A-B={e2}—属A但不属B之元素，A中去掉B的公共边环和：AB={e2，e3}

——属A或属B，但不同属A与B(特有边)A-BA

B1.节点的度数(Degree)节点的度数是指某节点所关联的边数，记为

性质1：对于n节点，m条边的图，有性质2：任何图中度数为奇数的节点数目必为偶数个(或零)。2．边序列、链、径、环边序列：有限条相邻边的串序排列

(边、点可重复出现)链：是没有重复边的边序列径：是既无重复边又无重复节点的边序列环：是起点和终点为同一节点的链3.联结图

联结图(ConnectedGraph)：

任何两个节点间至少有一条径的图

非联结图(DisconnectedGraph)： G=A∪B∪C=A+B+C4.树(Tree)

任何两节点间有且仅有一条径的图性质1：树是无环的联结图性质2：树是最小的联结图性质3：若树有m条边和n个节点，则有性质4：除单点树外，树至少有两个节点的度数为1。4.树(Tree)根树

星树

线树5.联结图的主树(SpanningTree)

若树T是联结图G的子图，即T包含于G中，且T含有G的所有节点，则T是G的主树。主树是覆盖联结图所有节点的树。 树枝数目——图G的阶（表示主树大小），记为 连枝数目——图G的空度（越大，图的联结性越好），记为5.联结图的主树(SpanningTree)根树

星树

线树6.割和环割（Cut）是指图的某些子集，去掉这些子集就使图的部分数增加(a)割节点、割节点集、最小割节点集最小割节点集中的节点数称为图的联结度，它表示了要破坏图联结性的难度(b)割边、割边集、割集（最小割边集）

若S的任何真子集都不是割边集，则称S为割集在割集中所含边数最小的数目，称为图的结合度，表示图的连通程度6.割和环割节点集

割边集

6.割和环(c)基本割集与基本环取一条树枝，与某些连枝一定能构成一割集，这种割集称为基本割集从主树的树枝出发得到联结图的基本割集，再用环和求得所有割集。6.割和环取一条连枝可与某些树枝构成环，这种仅包含一条连枝的环为联结图的基本环。若从主树的连枝出发，可得到基本环和所有环。

7.图的矩阵表示——借助计算机（a）关联阵(IncidenceMatrix)关联阵是表示节点与边相互联系的矩阵

全关联阵（不是线性独立的）

7.图的矩阵表示

关联阵（线性独立矩阵）

联结图主树的数目

7.图的矩阵表示（b）割阵和环阵割阵对应于某一个主树，每行对应一个基本割集，每一列对应一条边，(n-1)×m的矩阵对有向图，基本割集的方向取树枝的方向为正7.图的矩阵表示上述割阵的行向量的环和可得全部割集的矩阵将Q阵中边的次序重排，把树枝放在前面7.图的矩阵表示环阵是以基本环为行，边为列的矩阵环阵的行向量环和可形成所有环的矩阵

环阵B和割阵Q的关系：

7.图的矩阵表示（c）邻接阵(AdjacencyMatrix)表达节点与节点间关系的矩阵为邻接阵

这是有向图的邻接阵；对于无向图，是一对称阵7.图的矩阵表示

8.图的权（Weight/Cost）节点和边被赋值的图被称为有权图节点的权值，代表着交换机的容量或造价等链路的权值，代表着信道的传输容量、传输时间、几何长度和造价等第3章通信网理论基础3.1网络拓扑与通信网结构3.1.1网络拓扑基础3.1.2通信网结构设计最短径问题流量分配问题3.2排队论通信网业务分析与优化3.3通信网的可靠性3.4多址接入系统分析

最短径问题

图论中最短径问题，实质是关于通信网拓扑结构的优化和通信路由选择问题。最短主树端间最短径1.最短主树

已知联结图G有n个节点，且节点间距离，若

和

间无边，可令

，求最短主树：即n-1条边的权的和最小的联结子图。

(a)无约束条件的最小主树

Prim算法和Kruskal算法

1.最短主树P算法：(顺序取节点的普列姆(PRIM)算法)1.最短主树K算法：(顺序取边的克鲁斯格尔(Kruskal)算法)d12，d25，d54，d23，d35，d14,d15，d341.最短主树(b)有约束条件的最小主树约束条件：转接次数，线路的业务量等等穷举法调整法E—W算法：(Esau—Williams算法)Kruskal算法2.端间最短径(a)指定端至其它端的最短径Dijkstra算法(D算法)

VSV1V2V3V4V5V6置定最短径长0∞∞∞∞∞∞VSWs=00.521.5∞∞∞V1W1=0.5∞V3W3=1.5V4W4=1.728.45.5V2W2=28.45.1V6W6=5.18.4V5W5=8.4V1VsV2V3V4V5V61.54.05.06.72.端间最短径（b）所有端间的最短径算法

用D算法作n次运算，每次取一个不同的节点作为指定节点便可

F算法，它实际上是将n次D算法用矩阵的方法描述出来2.端间最短径（c）次短径和可用径 求次短径和可用径，用作备用或迂回路由，以防主路由业务量溢出或发生故障 次短径的寻找方法一种是寻找与最短径边分离(无分共边)的次短径另一种是寻找与最短径节点分离(无公共节点)的次短径可用径是指寻找一批满足某些约束条件的节点间路径而并不要求它们端分离或径分离2.端间最短径（d）网的中心和中点一个节点在网内的位置：用最长的最短径长来表示网的中心：所有节点位置的最小值所对应的节点叫网的中心

至最远节点距离最短网中心可用作维修、服务中心

2.端间最短径网的中点：平均最短径长最小的节点叫网的中点若边的权值均取1，网的中点就是平均转接次数最小的问题，所以网的中点可用作全网的交换或控制中心

2.端间最短径网的直径：

网内两端间最短径的最大值叫网的直径V1V2V3V4V5V6Vsti7.913.513.58.4si19.756.838.119.2网中心是V4，网中点是Vs，直径是13.5V1VsV2V3V4V5V61.54.05.0

6.7第3章通信网理论基础3.1网络拓扑与通信网结构3.1.1网络拓扑基础3.1.2通信网结构设计最短径问题流量分配问题3.2排队论通信网业务分析与优化3.3通信网的可靠性3.4多址接入系统分析

流量分配问题网的工作­­—把一定的业务流从源送出网的控制—流量控制、路由控制、计费控制流

量—泛指传输速率控制目标—流量最大、分配合理、提高效率、充分利用资源非任意性—受限于网的拓扑和容量（边和节点），为在某些条件限制下的优化问题优化问题—最大流，最小代价。业务有随机性，简化起见仅限于讨论平均流量流量分配问题1.流量分配的一般性问题2.最大流问题3.最佳流问题

1.流量分配的一般性问题对G={V,E}(n,m)

:

设：边的容量实际流量若网络中有

一组流使得单源单宿时F源宿点间的总流量则

须满足下述两个限制条件：

1.流量分配的一般性问题①非负性、有限性2m个条件②连续性n个条件满足上述两条件式的流称为可行流可行流不止一个。124356423454121243542333112435642345411243542353334一个可行流：5一个可行流：7图1图21.流量分配的一般性问题

1.流量分配的一般性问题另外还有：

转接容量限制

多信息流问题（多源和多宿）

可能还有网的质量指标、呼损率、延时等因素制约，尤其再涉及流量的随机性，其复杂程度使解析解几乎不可能。

2.最大流问题割集：

,，

和界上的边集将、分开前向边、反向边割量（割容量）（前向边容量之和）由连续性和非负性，可证源宿节点的总流量必有

2.最大流问题路 无重复边无重复节点的边序列中：

前向边中分饱和边、非饱和

反向边中分零流量边、非零流量边 可增流路：若一条路中，所有前向边都未饱和，所有反向边都是非零流量的，则这条路称为可增流路可增流量为：2.最大流问题源宿点间达到最大流的充要条件：

如果可行流已使源宿点间的流量达到最大值，则从到的每一条路上至少有一个饱和的前向边或一个零流的反向边，也就是不存在一条可增流的路。2.最大流问题最大流量—最小割量定理（Ford-Fulkerson定理）： 当源宿点的流量达到最大时，总存在这样一个割 集，其每条正向边都是饱和的，且该割量在各割集中为最小值并等于最大流量。

k为所有割集数

依据上述思路，对给定网络搜索每一条从源点到宿点的路是否可增流，并对可增流路增流直至不存在可增流路，这便有了求源宿点间最大流量的标记算法(M算法)。

2.最大流问题

求源宿点间最大流量的标记算法(M(mark)算法)：M0：起始，令

，对所有i,j

M1：标源点为（+，S，∞）作为已标未查端。M2：查已标未查端Vi，即查Vi所有邻端Vj，并按下列原则标注：若

，则标为

，符号中前两个表示从Vi到Vj有边，是正向的，

表示可增流量的值，且

，

为Vi点中已标定的值。

若，则标，表示从Vj到Vi有边，为反向的，可以减流，且。2.最大流问题续M2:此时Vj为已标未查端。若Vj不满足条件，即表示无增流和减流的路通过Vj，则不标。当Vi的所有邻节点都查完，并标上值或不标，则称Vi为已查。M3：若Vt已标，则沿可增流路增流

，返回M1。若各节点都已查，而Vt未标，结束算法。2.最大流问题2.最大流问题以上是对单源单宿的有向图进行求解，对M算法还可作以下几种推广：

无向图情况端容量限制时多源多宿情况3.最佳流问题最佳流典型问题描述：

对给定网络

，边容量为

和边代价为

，总流量要求达Fst，且要求总代价最小。

负阶环算法(N算法)流量分配问题

实际网络复杂的拓扑结构 通信业务流具有随机性 各种因素的合理性制约

实际网络的设计会复杂困难得多。

3.2排队论通信网业务分析与优化

3.2.1排队论QueuingTheory

排队论基础

排队模型分析3.2.2通信网参量与指标分析3.2.3通信网络优化排队论基础（1）排队系统（2）排队系统的三要素（3）排队系统的统计分布（4）排队系统的工作方式（5）排队系统的主要指标（6）排队系统的表示形式(1)排队系统排队系统构成：顾客：要求服务服务员：提供服务产生排队原因：“顾客”的到达与“服务”的进行具有随机性目标：满足服务质量、提高资源利用率→高效的排队系统排队论是在随机过程基础上发展起来的一种数学方法

a.窗口数m——服务系统的资源量m=1，单窗口排队系统m>1，多窗口排队系统,可同时给多个顾客提供服务（2）排队系统的三要素（2）排队系统的三要素b.顾客的到达率定义：单位时间内到达顾客的统计平均数随机性统计平均值设前后顾客平均到达时间间隔则愈小，系统负载愈轻，反之则愈重。

（2）排队系统的三要素c.系统的服务率定义：单位时间内顾客接受完服务离去的数目的统计平均值设平均服务时间

则（3）排队系统的统计分布三要素不足以充分描述排队系统并分析其运行状态和结果排队系统的性能主要取决于顾客到达时间间隔与服务时间的统计分布和排队规则对一般的系统统计分布，尚无通用的解析求解方法常用的指数分布系统，有较完善的求解方法许多实际排队系统统计分布都与之较吻合或可转化成这种系统（3）排队系统的统计分布泊松过程是最简单的随机过程之一

（只有一个参数）泊松随机过程三特性：平稳性独立性（无后效性）稀疏性推论1：若顾客达到为泊松过程，则

顾客到达时间间隔为服从指数分布的随机变量证：把分成N等份，每份为；根据无后效性和稀疏性，的概率密度函数应为： 两边消去，并令得：注：（3）排队系统的统计分布推论2：在T期间内有K个顾客到达的概率分布为

泊松分布(Poisson)证：将T分为N等份，每份为。T内有k个顾客到达可分布在其中任意K个中，则有令得：

（3）排队系统的统计分布同理，若服务过程也符合泊松过程三特性，则服务时间的概率密度亦服从指数分布

T时间内有K个顾客接受完服务离去的概率分布也服从泊松分布

（3）排队系统的统计分布

例：设某电话系统的电话呼叫按每小时平均30次的泊松过程变化，问在5分钟间隔内无呼叫和有3次呼叫的概率分别是多少?

解：次/小时，T=5/60小时，因而，根据泊松分布有：

（3）排队系统的统计分布（3）排队系统的统计分布将符合前述三个条件的顾客流称为泊松流这种指数分布所导致的排队过程，具有马尔柯夫（Markov）性，所以被称作M分布实际的排队过程通常不会严格符合前述条件（平稳性、独立性、稀疏性），看作近似。为了对排队系统作更切实际的研究，除上述的分布外，通信系统中还经常用到、、D分布等。

按服务规则划分(a)先到先服务(b)后到先服务(c)优先权服务（4）排队系统的工作方式（4）排队系统的工作方式通常的排队方式有：（4）排队系统的工作方式按排队规则划分(a)无限排队等待型（不拒绝系统）(b)截止拒绝型：即时拒绝系统延时拒绝系统(a)排队长度，简称队长K，平均队长

(系统数)(b)等待时间(c)服务时间(d)系统时间(S)

Little公式(e)系统效率(f)稳定性

——用排队系统强度来描述

（5）排队系统的主要指标用数学的方法来描述排队系统A：顾客到达规律B：服务规律

（M、Er、HR、D、G等）m：窗口数N：潜在顾客总数(无限潜在顾客，可省略)N：截止队长（对不拒绝系统，该项可省略）如M|M|m(N，n)等。

（6）排队系统的表示形式分析排队系统的常规步骤：(a)选定合适的排队系统特征模型(b)选择与定义状态变量

(c)根据所选状态变量以及排队系统模型，列出状态方程(组)，然后求解方程(组)并得出有关网络参量指标（1）M|M|1排队系统分析（2）M|M|m(n)排队系统分析.排队模型分析

M|M|1是顾客到达时间间隔和服务时间均为指数分布的、单窗口、不拒绝系统。

设系统中平均到达率为，平均服务率为，取队长作为状态变量来建立系统状态方程。

（1）M|M|1排队系统分析

令为时刻队长为K的概率，取为足够小的时间间隔，则在时系统处于K状态的概率取决于下述三种情况：（1）M|M|1排队系统分析 (a)在时刻t处于K-1状态，在内有一个顾客到达而无顾客离去，其状态转移概率为：

(b)在时刻t处于K+1状态，在内有一个顾客离去而无顾客到达，其状态转移概率为：

(c)在时刻t处于K状态，在内有一个顾客到达和一个顾客离开，或恰好无顾客离开和到达，其状态转移概率为：（1）M|M|1排队系统分析以上三个事件是互相独立的，根据全概率公式：（1）M|M|1排队系统分析得状态方程：

（1）M|M|1排队系统分析

对于M|M|1模型，可直接由哥尔莫柯洛夫（Kolmogorov）方程画出概率状态转移图（1）M|M|1排队系统分析……令

利用概率归一化性质

（1）M|M|1排队系统分析求解系统的有关参数：平均队长平均系统时间系统效率（1）M|M|1排队系统分析（2）M|M|m(n)排队系统分析直接按哥尔莫柯洛夫方程画出状态转移图：令

，利用

其中

（2）M|M|m(n)排队系统分析

几种特例

a.m=1，即模型：

b.m=1，，即模型：（2）M|M|m(n)排队系统分析 c.n=m，即为即时拒绝模型：该模型的拒绝概率为：

爱尔兰（Erlang）公式 呼叫量：（2）M|M|m(n)排队系统分析 d.，即多窗口不拒绝模型： 有了的通式，同样可计算排队系统的各有关参量（2）M|M|m(n)排队系统分析3.2.2通信网参量与指标分析

通信网和排队系统之间的关系描述通信网性能指标的术语业务量和呼叫量阻塞率和呼损通信网呼损与延时通过量和信道利用率业务量和呼叫量（1）业务量：在指定时间内线路被占用的总时间。

R(t)是t时刻被占用信道数，对遍历过程来讲，业务量与t无关。 业务量的量纲是：时间

呼叫量（业务量强度）定义：线路占用时间与观察时间之比 实际中R(t)一般是非平稳的，更不能说是遍历的，通常取小时呼叫量或小时爱尔兰来作为网络设计的依据。

业务量和呼叫量（2）通信网术语排队系统术语信道数服务窗口数m单位时间内的平均呼叫数单位时间到达分组平均数顾客到达率λ每次呼叫（每个分组）占用线路的平均时间系统平均服务时间τ呼叫量a≥m，拥塞ρ=λ/mμ≥1，不拒绝系统不稳定业务量和呼叫量（3）阻塞率和呼损（1）

阻塞和呼损均指拒绝状态占全部状态的百分比从系统角度——阻塞从用户角度——呼损 在实际的电路交换网中，为了工作的稳定而多采用截止型排队系统，阻塞率和呼损都是指拒绝状态占全部状态的百分比。

时间阻塞率：总观察时间内阻塞时间所占的百分比。

呼叫阻塞率(又称呼损)：被拒绝呼叫次数占总呼叫次数的百分比。

阻塞率和呼损（2）

：随机时刻观察系统处于状态n的概率

：顾客到达时刻观察系统处于状态n的概率 对于一般情形，由于系统出现阻塞期间可能并没有顾客(或呼叫)到达，则。但若在纯随机呼叫情况下，相当于顾客以泊松流到达，则。

一般情形，Pc≤Pn；泊松流时，Pc=Pn。阻塞率和呼损（3）

通信网呼损与延时（1）

对于电路交换通信网来讲，呼叫须在端到端之间建立，因此呼损也就与网络及转接次数有关。设网内的某对源宿间有向径共有r条边，各边上的呼损为，那么通过该径的源宿间呼损（端到端的呼损）将为：延时（在分组交换中尤为重要）总延迟=TRANS+PROP+QD+PROC分组大小/传输速率距离/光(电)速排队时间交换机或路由器处理时间，非常短时可以忽略,否则归入ττωS（主要的延时时间）通信网呼损与延时（2）

分组交换网中，端到端总延时需考虑：途中所有链路系统延时途中所有链路传播延时分组在宿端重新排序造成的延时

对于电路交换网，常采用即时拒绝，等待时间几乎为零，呼损是主要衡量参数。对于分组交换网，一般用延时拒绝或不拒绝系统，延时是一个很重要的衡量参数。由此可见，对不同性质的业务和通信网络，延时的考虑应有所不同。

通信网呼损与延时（4）

通过量和信道利用率（1）

通过量：单位时间通过的呼叫量注意:要区别两种情况点到点（线路）端到端（网络）若线路的容量为Cr，则定义信道利用率为：

应注意这里的a和Pn、

Pc各代表了什么？通过量和信道利用率（2）

全网效率：通信网中若有M条边，相当于M条线路，则全网效率可用各线路的通过量Tr之和与各线路的容量之和的比来表示。

通过量和信道利用率（3）

全网通过量：从各端进入网内而能达到宿端的业务量（设全网有n个端到端业务）注意：它并不是各线路通过量之和

通过量和信道利用率（4）

3.2.3通信网络优化

在网络随机模型的分析前提下：

优化网络结构，优化网络运行管理前面介绍了哪些？提高通信网效率的主要方法通信网的优化提高通信网效率的主要方法

本小节是在考虑通信网随机业务流基础上，用技术的手段提高信道利用率和降低呼损提高信道利用率和降低呼损的技术手段：

1.大群化技术

2.延迟方法

3.综合化方法

4.迂回方法1).大群化技术通常，社会服务资源在一定范围内统一利用优于分散经营，通信资源也是如此。在一定的质量指标要求下，信道统一调配可比分散利用传送更多的业务量，从而增加信道的利用率。1).大群化技术——电路交换网对于电路交换网:

常为即时拒绝系统呼损为主要指标aPcm11010010.50.910.9930.06250.750.971010-70.2150.9030～01.7×10-70.7100～0～00.076业务量大，所需的信道数多，系统效率也提高，且业务量与信道数不是线性关系。1).大群化技术——电路交换网两种设计方法的比较：

1).大群化技术——电路交换网

业务量越大，即大群化规模越大，效益提高越明显。

对于分组交换网：常为延时拒绝或不拒绝系统延时（主要是系统时间）是主要指标当ρ一定时，μ愈大则时延愈小，而1).大群化技术——分组交换网若把n个到达率为λ的业务集中到一个大容量的线路中去希望保持η或ρ不变，延时将减小之1/n

λ增加到n倍，

μ也需增加到n倍

即信道容量c须增加到n倍。

此时延时可减小至1／n。1).大群化技术——分组交换网2.希望保持系统时间不变，信道容量C就不用增加到n倍。例：设十个分别排队的业务，各自的，集中在一起时，总的到达率为 设集中后的服务率为，则容量仅须增加5.5倍，就可使延时不变，效率提高0.50.91

1).大群化技术——分组交换网以为例，设截止队长为

只要允许一个呼叫等待，呼损就明显下降，代价是有的顾客须等待的时间。2).延迟方法综合化方法是指将各种不同性质、不同信息流的通信综合到一个网络中，提高网络的效率、降低呼损和延时。从本质上讲，综合化方法在物理意义上是与大群化方法一致的，只不过它是对多种业务的大群化。

3).综合化方法迂回方法：

最短径：主路由

其它路径：辅助路由

可用作主路径故障时的备份

亦可用来转接主路径中溢出的业务

（溢出是由于业务的随机性）“迂回”可以减小呼损，提高通信网效率。4).迂回方法例：下图所示为有四个交换站的电路交换网络，站间的呼叫彼此间都是aij=1爱尔兰，i,j=1,2,3,4，i≠j，各边均为两信道的双向线路。每边每方向排队模型：

M/M/2(2)4).迂回方法当无迂回方法时，各站间业务均由直通路由传输，各边各方向上的呼损均为：V1V2V4V34).迂回方法若对业务按下列路由表选择迂回路由：各边在各方向上都承截着相同的业务流，即一条主路由业务，两条迂回路由业务。（观测e12）V1V2V4V3V1V2V4V34).迂回方法辅路由2辅路由1

由于是一个对称网络，各边各方向上的阻塞率都相同，设B代表该阻塞率。V1V2V4V3V1V2V4V3A12为等效呼叫量V1V2V4V34).迂回方法解方程可得，B=0.28。此时源宿点间业务的呼损为：与无迂回时相比，具体边上的呼叫阻塞率增加。

但源宿点间业务的呼损下降了几乎一倍。

4).迂回方法由爱尔兰公式的阻塞率为：

增加迂回路径后，

求解：

各边信道利用率；

全网效率；

全网通过量。4).迂回方法通信网的优化通信网的优化：对通信网的设计和控制进行最佳的选择，以提高网资源的利用率。本小节是在实际网络业务模型动态业务分析的前提下进行，介绍基本方法思路。

1.电路交换网的优化

2.分组交换网的优化这里主要考虑网络拓扑结构已确定后控制的优化和信道容量的选择问题。首先讨论全网呼损的计算；再讨论如何控制以达到最佳，亦即呼损最小，或要求在呼损不超过某定值下，设施的投资最少。

1).电路交换网的优化1).电路交换网的优化电路交换网的呼损

全网呼损：所有源宿间业务的平均阻塞率。

A为全网的总呼叫量

:端间呼叫量

:端间呼损

要求得全网的呼损就必须先求得所有源宿节点间的呼损，而这些求解通常是在以下三个条件前提下：（a）网络的拓扑结构给定。（b）网络各边容量及节点间业务量已知。（c）网络的源宿节点间路由表给定。不同的路由表，可有不同的呼损。1).电路交换网的优化计算全网呼损可分三步进行：

(a)令各边的阻塞率为Bl。根据路由表分析各边的等效业务量(假设溢出业务仍为泊松流)。

(b)根据等效业务量和线路容量，依据爱尔兰公式列出各边阻塞率的方程组，并解该方程组，求出各边的Bl，并求出。

(c)依照全网呼损公式，求出最终结果。1).电路交换网的优化电路交换网的优化通常是以全网呼损作为限制条件，来对某些目标函数进行优化设计。主要有两种：

a.对路由控制的优化

b.对线路容量的选择优化1).电路交换网的优化a.路由控制的优化：

假设线路容量已定，求呼损最小的路由表。最优化：把所有可能的路由表组合都用前述方法计算出对应的全网呼损，然后选出其中的最小网络呼损的路由组合。大网？准最佳解：满足一定全网呼损要求前提下，从任一路由树开始，试探修改路由并计算网络呼损。

当然还有动态路由控制问题则更复杂。

1).电路交换网的优化b.线路容量的选择优化优化的目标函数为：总代价优化的方法：在一定的呼损指标前提下，即

选择线路容量Ni，使得Z最小或准最小

1).电路交换网的优化分组交换网通常为延时拒绝系统，因而其主要衡量指标不是呼损而是信息的平均延时。 一条信息在一段链路上的延时？ 一条信息穿过网络的延时？ 多条信息穿过网络的延时？

全网平均延时？

2).分组交换网的优化全网的平均延时

设Vs点到Vd点的业务到达率为λsd包／秒，它的平均延时为Tsd，(对每个有序端对（s,d）可用λw、Tw表示)。若网内有W个源宿点间的业务流，则全网的平均延时为：

2).分组交换网的优化

对链路延时的计算通常可采用

当网内只有第w

个业务时，其在第l

条边上的平均延时为：

若网中共有的W种业务是相互独立的2).分组交换网的优化全网的平均延时将为

2).分组交换网的优化

在分组数据网中，全网平均延时为网络优化的主要指标。 观察上式，全网平均延时和什么因素有关？2).分组交换网的优化

网络平均延时与各业务量、线路的容量、线路上的流量有关 分组网的优化主要有二个方面:

a.容量配置

b.流量分配2).分组交换网的优化a.链路容量配置的优化 优化的目标函数：（流量fl确定） 全网总代价 优化的方法：在满足全网平均延时T指标前提下，合理选择Cl，使F最小2).分组交换网的优化b.流量分配的优化 流量分配，实际上是路由选择问题 流量分配的优化——在链路容量一定时，选择分流系数，使全网平均延时最小。 路由控制，流量控制2).分组交换网的优化3.3通信网的可靠性（1）

可靠性是指系统运行某段时间T内不发生故障的概率，或者说它是两次故障间隔时间大于T的概率。 两次故障间隔的平均时间越大，可靠性就越高。 若设a为平均故障率，1／a则是平均故障时间(MTBF：

MeanTimeBetweenFailure)且故障间隔统计特性具有指数分布的话，则系统在T时间内无故障的概率为：

3.3通信网的可靠性（2）

对于通信网而言，仅就网络传输线路可靠性讲，若网络每条线路的可靠性为r，对应故障率为P，则r=1-P，且设各线路故障发生彼此独立，当网络有m条线路时，同时有i条线路发生故障，而m-i条保持畅通的概率为：

3.3通信网的可靠性（3）

对整个网络的故障应结合具体的网络拓扑结构来分析。

3.3通信网的可靠性（4）

一般而言，网络故障概率可用下式表示： 式中Q为最小线路割集的大小，称为结合度;Ai为网络中含有i条线路的割集数。

对应的网络可靠性为R＝l一P。3.4多址接入(Multi-Access)系统分析(1)

−前面所论述的网络结构和业务分析=基本上都是针对电路转接或信息转接的=各用户都接到一个交换站≡所有信息都在那里排队或被拒绝或被转接出去−多址接入是另一种网络结构和信息处理方式=源宿节点分布在信道各处，相互通过公用信道联系=共享的多接入媒体，传输媒体是广播方式的

≡一个工作站发送信息时，

其它所有的工作站都能听得到它所发出的信息≡两个或两个以上的工作站同时发送时，

它们的信号可能会碰撞会相互干扰

3.4多址接入系统分析(3)3.4多址接入系统分析(4)静态分配——最简单的多址方式固定分配，如FDMA、TDMA、CDMA，相当于全连接或部分连接。举例：卫星通信系统、蜂窝移动通信系统等缺点：仅适用于站点较少、站点数目相对固定且每个站点通信量均较大的情形，不适于突发性数据。信道利用率明显不高，不符合大群化和综合化网络高效设计的基本思想。3.4多址接入系统分析(5)动态分配或占用信道资源的多址接入方式目的：为了提高多址网络系统的资源利用率需要解决问题：要有效避免两个以上分布的源点同时使用信道而造成信息“碰撞”，致使信息无效须重新发送，既浪费了信道资源又造成信息传输的延时。

3.4多址接入系统分析(6)动态分配的前提：5个假定(1)站模型假定：各站独立，且以呼叫率产生帧。在成功发送一帧之前，站点不会产生新帧(2)单信道假定：只有一个信道，各站平等共享该信道(3)冲突假定：若有冲突（两帧有重叠），必须重发(4)时间假定连续时间：帧可以在任何时刻发送

时隙：帧必须在时隙开始时发送(5)载波假定有载波：站点可以检测到信道是否空闲 无载波：站点在发送之前无法判断信道是否空闲{{3.4多址接入系统分析(7)3.4.1纯ALOHA系统3.4.2时隙ALOHA3.4.3载波检测多址接入系统(CSMA)3.4.4轮询方式3.4.5总结PureALOHAPureALOHA工作原理：（1968年夏威夷大学项目，岛间通讯）设有无限个用户分布共享一个信道用户的总呼叫是以λ为均值的泊松流站点只要有信息要发送，便立即产生“定长”信息包，并发送到信道上（随机抢占信道）规定时间内若收到应答，表示发送成功；否则重发重发策略：等待一段随机的时间，然后重发；如再次冲突，则再等待一段随机的时间，直到重发成功为止。缺点：极容易冲突。性能：吞吐量

0.184PureALOHAA1帧产生B1A2A2B1冲突t1超时时间+随机延时t2B2A2t3B2t4B3A3

站A站B信道上的总效应A1B1A2B2纯ALOHA系统的工作原理图PureALOHAPureALOHA设信息包长度P=1，则呼叫量a=λP=λ，t时间内有r个信息包发上信道的概率为：t时间内无信息包发出的概率则为：成功发送的概率即为在连续两个包长时间内没有其它信息要发送的概率所以，成功发送一个信息包的概率为：PureALOHASlottedALOHASlotted-ALOHA系统工作原理：构成条件与业务流性质、定义与纯ALOHA系统相同所不同的仅仅是有信息包要发送上信道时的方法不同Timeisdividedupintodiscreteintervals,eachintervalcorrespondingtooneframe.Aterminalisnotpermittedtosenduntilthebeginningofthenextslot.

SlottedALOHAA1帧产生B3A2A2B1冲突超时时间+随机延时t1t2B2B2B3A3

站A站B信道上的总效应A1B1A2B2A3时隙ALOHA系统的工作原理图SlottedALOHA

由于每个信息包被限定在固定的时隙中发送，因而成功发送一个信息包的概率，为在一个包长时间内无信息包要发送的概率，即： 对于业务量a，该系统的通过量r为：

SlottedALOHASlottedALOHASlotted-ALOHA比Pure-ALOHA系统通过量提高了一倍。代价：必须建立全网的统一时钟。00.511.522.533.544.5500.4时隙ALOHAALOHA通过率ｒ呼叫量ａSlottedALOHA S-Aloha应用：

无线通信网络中，

如GSM：S-Aloha+TDMA+FDMA

160CarrierSenseMultipleAccessprotocols

CSMA——CarrierSenseMultipleAccessProtocolCSMAimprovesonALOHAbysensingthechannel!Userdoesn’tsendifitsensessomeoneelseVariationsonwhattodoifthechannelisbusy1-persistent(greedy)sendsassoonasidleNonpersistentwaitsarandomtimethentriesagainp-persistentsendswithprobabilitypwhenidle161CarrierSenseMultipleAccessprotocols

1-persistentCSMA(CarrierSenseMultipleAccess):Tosenddata,astationfirstlistenstothechanneltoseeifanyoneelseistransmitting.Ifso,thestationwaits(keepssensingit)untilthechannelbecomesidle.Otherwise,ittransmitsaframe.Ifacollisionoccurs,thestationwaitsarandomamountoftimeandstartsalloveragain.Itiscalled1-persistentbecausethestationtransmitswithaprobabilityof1wheneveritstartssensingthechannelandfindsthechannelidle.ClassicEthernetusesthe1-persistentCSMA/CDalgorithm

162CollisionsinCSMA

HowcouldcollisionshappeninCSMA

?Whenevermorethanonestationdetectanidlechannelandtheirtransmissiontimesoverlap.Discussions:What'stheeffectofsignalpropagationdelay

?Thelongerthedelay,themorethecollisions,andtheworsetheperformanceoftheprotocol.Howaboutzeropropagationdelay

?Therestillexistchancesofcollisions.IsthisprotocolanybetterthanALOHA(bothpureandslotted)

?Yes,becausebothstationshavethedecencytodesistfrominterferingwiththethirdstation'sframe.163CarrierSenseMultipleAccessprotocols

Non-persistentCSMA

Tosenddata,astationfirstlistenstothechanneltoseeifanyoneelseistransmitting.Ifso,thestationwaitsarandomperiodoftime(insteadofkeepingsensinguntiltheendofthetransmission)andrepeatsthealgorithm.Otherwise,ittransmitsaframe.Ifacollisionoccurs,thestationwaitsarandomamountoftimeandstartsalloveragain.Thisprotocolhasbetterchannelutilizationandlongerdelaysthan1-persistentCSMA.

164CarrierSenseMultipleAccessprotocols

p-persistentCSMA(appliedtoslottedchannels):Tosenddata,astationfirstlistenstothechanneltoseeifanyoneelseistransmitting.Ifthechannelisidle,ittransmitswithaprobabilityp.Withaprobabilityq=p–1,itdefersuntilthenextslot.Ifthenextslotisalsoidle,iteithertransmitsordefersagain,withprobabilitiespandq.Thisprocessisrepeateduntileithertheframehasbeentransmittedoranotherstationhasbeguntransmitting.Inthelattercase,itwaitsarandomtimeandstartsagain.Ifacollisionoccurs,thestationwaitsarandomamountoftimeandstartsalloveragain.Ifthechannelis(initially)busy,itwaitsuntilthenextslotandapplytheabovealgorithm.802.11

usesarefinementofp-persistentCSMA165PersistentandNon-persistentCSMAComparisonofthechannelutilizationversusloadforvariousrandomaccessprotocols.CarrierSenseMultipleAccessprotocols

CSMA/CD(CSMAwithCollisionDetection)(1)Improvementistodetect/abortcollisionsReducedcontentiontimesimproveperformanceCollisiontimeismuchshorterthanframetimeCarrierSenseMultipleAccessprotocols

CSMA/CD(2)Theworst-casedelayincollisiondetectionLetthetimeforasignaltopropagatebetweenthetwofartheststationsbeτ.AbeginstotransmittingBdetects

thecollisionBt0+2τABt0+τABt0+τ-εAt0ABBbeginstotransmittingAdetects

thecollisionProblems:6CarrierSenseMult