1、第第8 8章章 通信网规划理论基础通信网规划理论基础8.1 8.1 图论及其在通信网中的应用图论及其在通信网中的应用8.28.2 网路流量设计基础网路流量设计基础8.3 8.3 通信网可靠性分析通信网可靠性分析8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用一、图论基础知识一、图论基础知识 P231P231 图论是研究包含某种二元关系的问题图论是研究包含某种二元关系的问题或者系统，并把这种问题或者系统抽象为或者系统，并把这种问题或者系统抽象为点和线的集合，用点和线相互连接的图来点和线的集合，用点和线相互连接的图来表示。表示。在通信网设计中，图论可以用于确定在通信网设计中，图论可以
2、用于确定最佳网路结构、选择路由、分析网路可靠最佳网路结构、选择路由、分析网路可靠性等。性等。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用1.1.图的基本概念图的基本概念(1(1）图的定义）图的定义 图图8-18-1点线图是由若干个点和点间的连线所组成。点线图是由若干个点和点间的连线所组成。定义：定义：设有设有V V点集和边集点集和边集E E，如果对任一边，如果对任一边e ek kEE，有有V V中的一点对中的一点对(v vi i,v,vj j)与之对应，则图可用有与之对应，则图可用有序二元组序二元组(V,E)(V,E)表示，记为表示，记为G=(V,E)G=(V,E)。8.18
3、.1 图论及其在通信网中的应用图论及其在通信网中的应用(2(2）点的度数）点的度数定义：定义：与某点相关联的边数，记为与某点相关联的边数，记为d(vd(vi i)。两个性质两个性质 度数为奇数的点的数目必为偶数（或度数为奇数的点的数目必为偶数（或零）。零）。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用（3 3）链路、路径和回路）链路、路径和回路链路：链路：图图8-38-3 图中边和与之关联的端点依次排成点和图中边和与之关联的端点依次排成点和边的交替序列，则称该序列为链路。边的交替序列，则称该序列为链路。路径：路径：无重复的边和点的链路称为路径。无重复的边和点的链路称为路径。回
4、路：回路：如果路径的起点和终点重合，则称为回如果路径的起点和终点重合，则称为回路。路。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用（4 4）子图的概念）子图的概念 若图若图A A的点集和边集分别为图的点集和边集分别为图G G的点集和的点集和边集的子集，则称边集的子集，则称A A是是G G的子图。的子图。每个图都是它自己的子图；每个图都是它自己的子图；真子图除原图外，所有的子图；真子图除原图外，所有的子图；生成子图包含原图所有点的子图。生成子图包含原图所有点的子图。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用（5 5）图的分类）图的分类有限图和无限图有限图和无
5、限图简单图和复杂图简单图和复杂图自环自环:两个端点重合为一点的边称为自环。两个端点重合为一点的边称为自环。并行边：并行边：与同一对端点关联的两条或两条以上的边与同一对端点关联的两条或两条以上的边简单图简单图:没有自环和并行边的图。没有自环和并行边的图。简单图中，链路、路径和回路可以只用点序列表示。简单图中，链路、路径和回路可以只用点序列表示。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用（5)5)图的分类图的分类有限图和无限图有限图和无限图简单图和复杂图简单图和复杂图有向图和无向图有向图和无向图图图8-58-5有权图有权图连通图和非连通图连通图和非连通图图图8-68-68.18
6、.1 图论及其在通信网中的应用图论及其在通信网中的应用（6 6）几种特殊的连通图）几种特殊的连通图完全图完全图：任意两点间都有一条边的无向图。任意两点间都有一条边的无向图。完全图的点数叫做图的阶完全图的点数叫做图的阶n n。正则图正则图：所有点的度数均相等的连通图。所有点的度数均相等的连通图。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用一、图论基础知识一、图论基础知识 2.2.图的矩阵表示图的矩阵表示 权值矩阵权值矩阵 对于具有对于具有n n个点的简单图个点的简单图G G，其权值矩阵，其权值矩阵为为,其中：其中：8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用一
7、、图论基础知识一、图论基础知识 2.2.图的矩阵表示图的矩阵表示 8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用二、树二、树 P238P2381.1.树的基本概念树的基本概念(1(1）树的定义）树的定义定义：定义：一个无回路的连通图称为树。一个无回路的连通图称为树。树枝树中的边树枝树中的边 树干：树枝的两个端点度数都大于等于树干：树枝的两个端点度数都大于等于2 2 树尖：树枝的一个端点度数为树尖：树枝的一个端点度数为1 1，这个端点叫树，这个端点叫树叶。叶。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用二、树二、树 P238P2381.1.树的基本概念树的基本概
8、念(2(2）树的分类）树的分类8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用二、树二、树 P238P2381.1.树的基本概念树的基本概念(3(3）树的性质）树的性质具有具有n n个点的树共有个点的树共有n-1n-1个树枝。个树枝。树中任意两个点之间只存在一条路径。树中任意两个点之间只存在一条路径。树是连通的，但去掉任一条边便不连通，即树是树是连通的，但去掉任一条边便不连通，即树是最小连通图。最小连通图。树没有回路，但增加一条边便可得到一个回路。树没有回路，但增加一条边便可得到一个回路。任一棵树至少有两片树叶，也就是说树至少有两任一棵树至少有两片树叶，也就是说树至少有两个端的度
9、数为个端的度数为1 1。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用2.2.图的支撑树图的支撑树定义：定义：包含图中所有点的树称为该图的支撑树，又叫生成树。包含图中所有点的树称为该图的支撑树，又叫生成树。图8-12 图的支撑树8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用2.2.图的支撑树图的支撑树几个要点：几个要点：只有连通图才有支撑树，有支撑树的图必只有连通图才有支撑树，有支撑树的图必为连通图；为连通图；支撑树上的边组成树枝集；支撑树上的边组成树枝集；非树枝的边组成连枝集；非树枝的边组成连枝集；一个连通图至少有一棵支撑树。一个连通图至少有一棵支撑树。8.1
10、8.1 图论及其在通信网中的应用图论及其在通信网中的应用二、树二、树 P238P2383.3.最小支撑树最小支撑树 若连通图本身不是一棵树，其支撑树不止一若连通图本身不是一棵树，其支撑树不止一个，但满足一定条件的权值之和为最小的支撑树个，但满足一定条件的权值之和为最小的支撑树至少存在一个。至少存在一个。求解最小支撑树：求解最小支撑树：有限制条件下有限制条件下 无限制条件下（无限制条件下（K K方法、方法、P P方法）方法）8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用K K方法步骤：方法步骤：K0K0：将连通图：将连通图G G中所有的边中所有的边e e按权值非按权值非减次序排列
11、。减次序排列。K1K1：取权值最小的边作树枝，再按：取权值最小的边作树枝，再按K0K0的次序选边为树枝，使不与已选边形成回的次序选边为树枝，使不与已选边形成回路。若形成回路，则删去这条边。路。若形成回路，则删去这条边。K2K2：直到：直到n n个点的图选出个点的图选出n-1n-1条边结束。条边结束。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用三、通信网的路径选择和最短路径三、通信网的路径选择和最短路径 P243P243 通信网络结构设计和选择路由时遇到通信网络结构设计和选择路由时遇到的问题如：的问题如：如何确定能够连接所有城市并使线路费如何确定能够连接所有城市并使线路费用最小
12、的网路结构；用最小的网路结构；在一定网路结构下如何选择通信路由，在一定网路结构下如何选择通信路由，怎样确定首选路由和迂回路由等。怎样确定首选路由和迂回路由等。8.18.1 图论及其在通信网中的应用图论及其在通信网中的应用四、站址选择四、站址选择 P347P347点确定点确定 求最小支撑树、最短径求最小支撑树、最短径建新的交换局建新的交换局 站址选择（其位置应使路径最短站址选择（其位置应使路径最短或网的总费用最小）或网的总费用最小）一个：一个：单中位点问题单中位点问题 多个：多个：多中位点问题多中位点问题8.2 8.2 网络流量设计基础网络流量设计基础网络流量：网络流量：反应了人们对网络的需求和
13、网络具有的传送能力。反应了人们对网络的需求和网络具有的传送能力。流量设计：流量设计：根据根据业务流量预测值业务流量预测值和和服务指标要求服务指标要求确定交换设备和确定交换设备和线路的容量，并对网内流量进行合理分批。线路的容量，并对网内流量进行合理分批。应该结合网络结构设计进行。应该结合网络结构设计进行。基础理论：基础理论：排队论，或称随机服务系统理论。排队论，或称随机服务系统理论。8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念 P251P2511.1.排队系统的概念排队系统的概念排队现象：排队现象：排队现象的产生原因：排队现象的产生原因：顾客需求的随机性、
14、服务设施的有限性（构成随机服顾客需求的随机性、服务设施的有限性（构成随机服务系统或称排队系统）务系统或称排队系统）排队论：排队论：利用概率论与随机过程理论，研究随机服务系统内服利用概率论与随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系，以合理的设计和控制排队务机构与顾客需求之间的关系，以合理的设计和控制排队系统。系统。8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念1.1.排队系统的概念排队系统的概念排队模型：图排队模型：图8-218-21排队服务机构排队规则服务规则顾客到达输入顾客离去输出图8-21 排队模型排队系统：排队排队系统：排队+服务
15、机构服务机构排队模型：排队模型：4个环节个环节8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念2.2.排队系统的基本参数（排队系统的基本参数（、mm、）（1 1）顾客到达率）顾客到达率 单位时间内平均到达排队系统的顾客数量。单位时间内平均到达排队系统的顾客数量。顾客到达时间间隔顾客到达时间间隔T T 任意相邻两顾客到达的时间间隔任意相邻两顾客到达的时间间隔T T（随机变量）。（随机变量）。8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念2.2.排队系统的基本参数（排队系统的基本参数（、mm、）（2 2）服务员数目）服务员数
16、目m m 排队系统内可以同时提供的服务的设备或者窗口数。排队系统内可以同时提供的服务的设备或者窗口数。8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念2.2.排队系统的基本参数（排队系统的基本参数（、mm、）（3 3）服务员服务速率）服务员服务速率 单位时间内单位时间内由一个服务员服务由一个服务员服务而离开排队系统的顾客而离开排队系统的顾客数，系统的服务速率为数，系统的服务速率为m m。顾客被服务时间顾客被服务时间 任意相邻两顾客到达的时间间隔任意相邻两顾客到达的时间间隔T T（随机变量）。（随机变量）。8.2 8.2 网络流量设计基础网络流量设计基础一、排
17、队论基本概念一、排队论基本概念3.3.排队系统的排队系统的3 3个特征个特征排队系统排队系统3 3个过程的特征。个过程的特征。顾客输入过程（到达时间的分布函数）顾客输入过程（到达时间的分布函数）排队过程（排队规则）排队过程（排队规则）顾客接受服务的过程（服务时间的分布函数）顾客接受服务的过程（服务时间的分布函数）8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念（1 1）顾客到达时间的分布函数）顾客到达时间的分布函数顾客输入过程有多种形式：顾客输入过程有多种形式：成批成批/单个；单个；时间间隔固定时间间隔固定/随机；随机；先后到达的顾客之间有关联先后到达的顾客
18、之间有关联/无关联；无关联；到达频率与时间有关到达频率与时间有关/与时间无关。与时间无关。常见的分布函数常见的分布函数 最简单流最简单流M M分布分布、定长输入的、定长输入的D D分布、爱尔兰输入分布、爱尔兰输入E Ek k分分布、超指数输入布、超指数输入H Hk k分布等。分布等。8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念（1 1）顾客到达时间的分布函数）顾客到达时间的分布函数最简单流：最简单流：平稳性。平稳性。稀疏性。稀疏性。无后效性（独立性）。无后效性（独立性）。最简单流在最简单流在t t时间间隔内达到系统的顾客数量服从泊松分时间间隔内达到系统的
19、顾客数量服从泊松分布：布：8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念（1 1）顾客到达时间的分布函数）顾客到达时间的分布函数最简单流在最简单流在t t时间间隔内达到系统的顾客数量服从泊松分时间间隔内达到系统的顾客数量服从泊松分布：布：最简单流的顾客到达时间间隔最简单流的顾客到达时间间隔T T服从负指数分布：服从负指数分布：8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念（2 2）服务时间的分布函数）服务时间的分布函数顾客接受服务的过程如果也是最简单流：顾客接受服务的过程如果也是最简单流：则服务时间则服务时间的分布服从
20、负指数分布：的分布服从负指数分布：8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念（3 3）排队规则）排队规则 决定了排队过程的特征，对系统性能有很大影响。决定了排队过程的特征，对系统性能有很大影响。损失制系统（即时拒绝）损失制系统（即时拒绝）等待制系统（不拒绝）等待制系统（不拒绝）混合制系统（延时拒绝）混合制系统（延时拒绝）服务规则：服务规则：先到先服务先到先服务后到先服务后到先服务随机服务随机服务优先制服务优先制服务8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念4.4.排队系统的几个主要指标排队系统的几个主要指标排队
21、长度排队长度k k（队长）：（队长）：某时刻系统中顾客的数量，某时刻系统中顾客的数量，包括正在服务的顾客包括正在服务的顾客。k k的统计平均值为平均队长，用的统计平均值为平均队长，用N N表示。表示。等待时间等待时间w w：顾客到达系统到开始接受服务的时间。顾客到达系统到开始接受服务的时间。w w的统计平均值为平均等待时间，用的统计平均值为平均等待时间，用W W表示。表示。服务时间服务时间：顾客从开始被服务到离开系统的时间间隔。顾客从开始被服务到离开系统的时间间隔。8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念4.4.排队系统的几个主要指标排队系统的几个主
22、要指标排队长度排队长度k k（队长）：（队长）：平均队长，用平均队长，用N N表示。表示。等待时间等待时间w w：平均等待时间，用平均等待时间，用W W表示。表示。服务时间服务时间：系统时间系统时间s s：s=w+s=w+s s的统计平均值用的统计平均值用S S表示：表示：系统效率系统效率：平均窗口占用率。平均窗口占用率。系统稳定性系统稳定性：8.2 8.2 网络流量设计基础网络流量设计基础一、排队论基本概念一、排队论基本概念5.5.李特尔定律李特尔定律 对于一个平均到达率为对于一个平均到达率为的排队系统，在平均意义上的排队系统，在平均意义上有：有：8.2 8.2 网络流量设计基础网络流量设计
23、基础一、排队论基本概念一、排队论基本概念6.6.排队系统的分类排队系统的分类通常用符号通常用符号 X/Y/m/n X/Y/m/n 表示表示常见的排队系统：常见的排队系统：M/M/m/nM/M/m/n排队系统排队系统-包括包括M/M/1M/M/1排队系统排队系统M/D/1M/D/1排队系统排队系统M/EM/Ek k/1/1排队系统排队系统M/HM/Hk k/1/1排队系统排队系统 8.2 8.2 网络流量设计基础网络流量设计基础二、二、M/M/1M/M/1排队系统排队系统1.1.系统模型系统模型达到时间达到时间T T服从参数为服从参数为的负指数分布，平均到达时间间隔为的负指数分布，平均到达时间间
24、隔为1/1/；不拒绝；不拒绝；一个服务员，一个服务员，m=1m=1；服务时间服务时间服从参数为的服从参数为的负指数分布，平均服务时间为负指数分布，平均服务时间为1/1/；排队强度为排队强度为=/，0011服务机构N一个服务员泊松输入过程指数服务时间分布8.2 8.2 网络流量设计基础网络流量设计基础二、二、M/M/1M/M/1排队系统排队系统2.2.系统的指标系统的指标（1 1）平均队长）平均队长N N（2 2）平均系统时间）平均系统时间S S（3 3）平均等待时间）平均等待时间W W（4 4）系统效率）系统效率8.2 8.2 网络流量设计基础网络流量设计基础三、排队论在通信网中的应用三、排队
25、论在通信网中的应用1.1.在电话网中的应用在电话网中的应用M/M/m/m M/M/m/m 即时拒绝系统即时拒绝系统 8.2 8.2 网络流量设计基础网络流量设计基础三、排队论在通信网中的应用三、排队论在通信网中的应用2.2.在数据通信网中的应用在数据通信网中的应用例例8-108-108.38.3 通信网可靠性分析通信网可靠性分析一、通信网可靠性定义一、通信网可靠性定义 P261P2611.1.通信网可靠性定义通信网可靠性定义可靠性的一般定义：可靠性的一般定义：产品在规定的使用条件下、规定的时间内完成规定功能的产品在规定的使用条件下、规定的时间内完成规定功能的能力。能力。通信网可靠性：通信网可靠性：通信网在实际连续运行过程中，能完成用户正常通信需求，通信网在实际连续运行过程中，能完成用户正常通信需求，并能把服务质量保持在规定范围内的能力。并能把服务质量保持在规定范围内的能力。其定义包括了可靠性主体、规定条件、规定时间、规定功其定义包括了可靠性主体、规定条件、规定时间、规定功能和完成规定功能的概率这五项要素。能和完成规定功能的概率这五项要素。8.38.3 通信网可靠性分析通信网可靠性分析一、通信网可靠性定义一、通信网可靠性定义8.38.3 通信网可靠性分析通信网可靠性分析8.38.3 通信网可靠性分析通信网可靠性分析8.38.3 通信网可靠性分析通信网可靠性分析
