第2章 网络设计基础及应用

1、第二章第二章 网络设计基础及应用网络设计基础及应用p第一节第一节 排队论基础排队论基础p第二节第二节 图论基础知识图论基础知识p第三节第三节 网络拓扑设计网络拓扑设计1. 排队论基础排队论基础p生活中的排队现象生活中的排队现象p通信中的排队通信中的排队节点节点顾客顾客服务者服务者1. 排队论基础排队论基础p顾客：顾客：要求服务的一方，如待传送的分组要求服务的一方，如待传送的分组p服务机构：服务机构：提供服务的一方，如交换设备、信提供服务的一方，如交换设备、信息传输网络等息传输网络等p服务员（或服务窗口）：服务员（或服务窗口）：服务机构内的具体设服务机构内的具体设施，如中继线、信道等施，如中继线

2、、信道等1. 排队论基础排队论基础p排队系统排队系统(或随机服务系统或随机服务系统)由要求由要求随机性服务随机性服务的的顾客顾客和和服务机构服务机构两方面构成两方面构成的系统的系统虚线框图为虚线框图为排队系统排队系统。排队排队服务机构服务机构顾客到达顾客到达输入输入排队规则排队规则服务规则服务规则顾客离去顾客离去输出输出排队模型排队模型问题：请画出排队系统的排队模型。问题：请画出排队系统的排队模型。排队论的概念排队论的概念p顾客需求的随机性顾客需求的随机性和和服务设施的有限性，服务设施的有限性，是产生是产生排队现象的根本原因。排队现象的根本原因。p排队论：排队论：即利用即利用概率论概率论和和随

3、机过程理论随机过程理论，研究随机服务系统内服务机构与顾客研究随机服务系统内服务机构与顾客需需求求之间的关系，以便之间的关系，以便合理地设计和控制合理地设计和控制排队系统。排队系统。 排队系统的基本参数排队系统的基本参数p排队系统的排队系统的基本参数基本参数包括：包括：顾客到达率顾客到达率服务员数目服务员数目m服务员服务速率服务员服务速率7 排队系统的基本参数排队系统的基本参数p顾客到达率顾客到达率单位时间内单位时间内平均平均到达排队系统的到达排队系统的顾客数量顾客数量单位时间内平均到达分组交换节点的单位时间内平均到达分组交换节点的分组数分组数量量反映了顾客到达系统的反映了顾客到达系统的快慢快慢

4、程度，程度， 越越大大，说明系统的说明系统的负载越重负载越重8 排队系统的基本参数排队系统的基本参数p顾客到达率顾客到达率T Ti i: :任意相邻两顾客到达的任意相邻两顾客到达的时间间隔时间间隔，是一个随，是一个随机变量机变量T T： T Ti i的统计平均值，表示顾客到达的平均时间间隔的统计平均值，表示顾客到达的平均时间间隔= 1/T= 1/T T T为顾客到达时间间隔为顾客到达时间间隔9 排队系统的基本参数排队系统的基本参数p顾客到达率顾客到达率在观察时间在观察时间t t内有内有n(tn(t) )个顾客到达，在个顾客到达，在平稳条件平稳条件下下平稳性平稳性在某一指定时间间隔在某一指定时间

5、间隔t内，到达内，到达n个顾客的概个顾客的概率只与率只与t 的长度有关，而与这间隔的的长度有关，而与这间隔的起始时刻无关起始时刻无关。ttnt)(lim10 排队系统的基本参数排队系统的基本参数p服务员数目服务员数目m排队系统内可以排队系统内可以同时同时提供服务的设备或窗口数提供服务的设备或窗口数在计算机通信网中，在计算机通信网中，m常指分组交换节点的常指分组交换节点的输输出信道数量出信道数量。11 排队系统的基本参数排队系统的基本参数p服务员服务速率服务员服务速率单位时间内由单位时间内由一个服务员一个服务员进行进行服务所离开服务所离开排排队系统的队系统的平均顾客数平均顾客数对于对于m m1

6、1系统，系统， 就是就是系统系统的服务速率的服务速率对于对于m 1m 1系统，系统，系统系统的服务速率为的服务速率为m m的倒数的倒数1/1/就是单个服务员对顾客的平均服就是单个服务员对顾客的平均服务时间，也就是务时间，也就是一个顾客一个顾客在系统内在系统内接受服务接受服务的的平均时间平均时间服务员服务速率说明服务员服务速率说明p1/1/就是单个服务员对顾客的平均服务时间，也就是一个顾客就是单个服务员对顾客的平均服务时间，也就是一个顾客在系统内在系统内接受服务的平均时间接受服务的平均时间p计算机通信网中，计算机通信网中，分组的平均长度分组的平均长度通常表示为通常表示为1/ (bit)(bit)

7、 p若信道容量为若信道容量为C bit/s，则，则分组平均发送时间为分组平均发送时间为1/(C C) (s) p则每个输出信道发送分组的速率为则每个输出信道发送分组的速率为C(C(即服务员的服务速率即服务员的服务速率) )p若有若有m m条信道条信道，则整个系统发送分组的速率为，则整个系统发送分组的速率为m mC C 。所以，在计算机通信网中，所以，在计算机通信网中，C C对应着排队论中的对应着排队论中的笼统说顾客时，其服务员的服务速率用笼统说顾客时，其服务员的服务速率用，具体说，具体说分组时，输出分组时，输出信道发送分组的速率用信道发送分组的速率用C C排队系统的三个特征排队系统的三个特征排

8、队系统在运行中包括排队系统在运行中包括三个过程三个过程：p顾客输入过程顾客输入过程说明了顾客到达的规律，与顾客的到达率、到达说明了顾客到达的规律，与顾客的到达率、到达时间的随机性有关时间的随机性有关p排队过程排队过程排队的规则、算法排队的规则、算法p顾客接受服务过程顾客接受服务过程取决于服务机构的取决于服务机构的服务效率和服务时间长短服务效率和服务时间长短排队系统的三个特征排队系统的三个特征排队系统的特征，就是排队系统三个过程的特征：排队系统的特征，就是排队系统三个过程的特征：p顾客输入过程的特征顾客输入过程的特征用相邻两顾客到达的间隔用相邻两顾客到达的间隔时间的分布函数来描述时间的分布函数来

9、描述p排队过程的特征用排队过程的特征用排队的规则表示排队的规则表示p顾客接受服务过程的特征顾客接受服务过程的特征用服务时间的分布函用服务时间的分布函数来描述数来描述上述是影响上述是影响排队系统性能的主要因素排队系统性能的主要因素顾客到达间隔时间的分布函数顾客到达间隔时间的分布函数p顾客到达的规律通常采用顾客到达的规律通常采用到达间隔时间到达间隔时间来来描述描述p到达间隔时间通常有以下几种分布：到达间隔时间通常有以下几种分布：最简单流最简单流M分布（要求）分布（要求）定长输入的定长输入的D分布分布k阶爱尔兰输入阶爱尔兰输入Ek分布分布k阶超指数输入阶超指数输入Hk分布分布最简单流分布最简单流分布

10、p什么是最简单流？什么是最简单流？满足以下三个条件（都是针对满足以下三个条件（都是针对顾客到达概率顾客到达概率）平稳性平稳性在某一指定时间间隔在某一指定时间间隔t内，到达内，到达k个顾客的概率个顾客的概率只与只与t 的长度的长度有关，而与这间隔的有关，而与这间隔的起始时刻无关起始时刻无关。稀疏性稀疏性将将t分成分成n个足够小的区间个足够小的区间t,t,在在t t内到达内到达两两个或两个个或两个以上顾客的概率为以上顾客的概率为0，即：在，即：在t t内只有一个内只有一个顾客到达或没有顾客到达。顾客到达或没有顾客到达。无后效性（或独立性）无后效性（或独立性）在互不重叠的时间段内，在互不重叠的时间段

11、内，顾顾客到达的概率客到达的概率相互独立，即相互独立，即不同不同t t内顾客到达的概率内顾客到达的概率无关无关17最简单流分布最简单流分布最简单流分布最简单流分布 泊松分布泊松分布p泊松分布：在给定泊松分布：在给定时间间隔时间间隔t内内系统有系统有 k个个顾客顾客到达的概率为：到达的概率为：tkkekttp!)()(k 0，1，2，顾客到达的顾客到达的概率概率泊松分布参数单位时泊松分布参数单位时间内顾客到达数间内顾客到达数在在t时间内顾客到时间内顾客到达的个数达的个数T:顾客到达时间间隔，顾客到达时间间隔，0Tp概率分布函数概率分布函数p概率密度函数概率密度函数)()(tTPtFT在时间在时间

12、t内有顾客到达的概率内有顾客到达的概率tetPtTP)()(0在时间在时间t内没有顾客到达内没有顾客到达(k=0)的概率的概率tTetPtTPtTPtF1)(1)(1)()(0tTTedttdFtf)()(如果将如果将T看成是数轴上的随机点的看成是数轴上的随机点的坐标坐标，那么，分布函数，那么，分布函数FT (t)在在t处的处的函数值函数值就表示就表示T落在区间落在区间(-,t上上的的概率概率 tkkekttp!)()(19p例例2.1 计算机通信网中，设分组到达率计算机通信网中，设分组到达率=35=35分组分组/ /分钟（分钟（minmin） , ,输入过程满输入过程满足最简单流条件，求分组

13、到达时间间足最简单流条件，求分组到达时间间隔在隔在0.1min0.1min以内的概率和在以内的概率和在0.1min-0.1min-0.3min0.3min之间的概率。之间的概率。20最简单流分布最简单流分布 泊松分布泊松分布p泊松分布：在给定泊松分布：在给定时间间隔时间间隔t内内系统有系统有 k个个顾客顾客服务的概率为：服务的概率为：k 0，1，2，顾客服务的顾客服务的概率概率泊松分布参数单位时泊松分布参数单位时间内顾客服务人数间内顾客服务人数在在t时间内顾客服时间内顾客服务个数务个数同理可得服务时间的分布函数和概率密度函数同理可得服务时间的分布函数和概率密度函数tkkekttp!)()(21

14、为顾客的服务时间为顾客的服务时间p概率分布函数概率分布函数p概率密度函数概率密度函数同理可得服务时间的分布函数和概率密度函数同理可得服务时间的分布函数和概率密度函数)()(tPtFtetPtP)()(0式中式中为平均服务率，为平均服务率，1/为平均服务时间为平均服务时间 tetPtPtPtF1)(1)(1)()(0tedttdFtf)()(在时间在时间t内有顾客服务离去的概率内有顾客服务离去的概率在时间在时间t内没有顾客服务离去内没有顾客服务离去的概率的概率22p计算机通信网中，由于计算机通信网中，由于发送分组的速率发送分组的速率为为C C，所以，分组发送时间的概率密，所以，分组发送时间的概率

15、密度函数为：度函数为：CtCetf)(p无论是顾客输入过程，还是服务过程，无论是顾客输入过程，还是服务过程，只要是最只要是最简单流，则所对应的概率分布函数简单流，则所对应的概率分布函数（输入过程对（输入过程对应的是顾客到达间隔时间的分布函数，服务过程应的是顾客到达间隔时间的分布函数，服务过程对应的是服务时间的分布函数）对应的是服务时间的分布函数）都为负指数分布都为负指数分布，又称为，又称为M分布分布p称为称为M分布的原因分布的原因是这种分布使排队过程具有是这种分布使排队过程具有马马尔柯夫尔柯夫（Markov）性性（马尔柯夫最基本的性质是（马尔柯夫最基本的性质是无记忆性无记忆性，即某顾客到达所需

16、要的时间与过去一，即某顾客到达所需要的时间与过去一个顾客到达所需要的时间无关）个顾客到达所需要的时间无关）排队规则排队规则&服务规则服务规则p排队系统采用的排队系统采用的排队规则决定了排队过排队规则决定了排队过程的特征，程的特征，对系统的性能有很大的影响对系统的性能有很大的影响。p排队规则排队规则是指服务机构是指服务机构是否允许排队是否允许排队，在排队等待情形下在排队等待情形下服务的顺序服务的顺序是什么是什么。排队规则排队规则&服务规则服务规则p排队系统排队系统通常分成以下通常分成以下三种情形：三种情形：顾客到达时顾客到达时，如果，如果所有服务窗口所有服务窗口均被均被占满占满损

17、失制系统（即时拒绝方式）损失制系统（即时拒绝方式）立即立即遭到遭到拒绝拒绝，即服务机构即服务机构不不允许顾客排队允许顾客排队等待等待（电话通信网采（电话通信网采用）用）等待制系统等待制系统（不拒绝方式）（不拒绝方式）允许排队，且队允许排队，且队长没有限制，但应满足稳定性要求，即长没有限制，但应满足稳定性要求，即1混合制系统混合制系统（延时拒绝方式）（延时拒绝方式）允许排队，但允许排队，但队长有限制队长有限制（计算机通信网采用）（计算机通信网采用）m26排队规则排队规则&服务规则服务规则p具有等待性质的排队系统（包括等待制系统和混合制系统）具有等待性质的排队系统（包括等待制系统和混合制系

18、统）相相应的应的服务规则服务规则主要有主要有：先到先服务：先到先服务：顾客顾客按照到达的先后顺序按照到达的先后顺序接受服务（计算机通接受服务（计算机通信网常用）信网常用）后到先服务：后到先服务：服务顺序与到达顺序相反服务顺序与到达顺序相反随机服务：随机服务：随机从等待的顾客中选择顾客服务随机从等待的顾客中选择顾客服务优先服务：优先服务：某些顾客特别照顾，有服务的优先权（计算机通某些顾客特别照顾，有服务的优先权（计算机通 信网有时也用）信网有时也用）p通信网通信网中一般采取的是中一般采取的是先到先服务先到先服务，有时有时根据情况根据情况也也采用优先制服务采用优先制服务方式。方式。p在排队系统的研

19、究中，在排队系统的研究中，排队的长度排队的长度和和服务规则无关服务规则无关p顾客在系统中的顾客在系统中的等待时间及逗留时间等待时间及逗留时间（指（指服务时间服务时间）的长短和）的长短和服务规则有服务规则有关关，不同的，不同的服务规则服务规则直接影响顾客在直接影响顾客在系统中耗费系统中耗费时间的长短时间的长短。 排队系统的几个主要指标排队系统的几个主要指标p排队长度排队长度k k（简称队长）（简称队长）: :某时刻系统中顾客的数量，包括正在被服某时刻系统中顾客的数量，包括正在被服务的顾客，与务的顾客，与输入过程、服务员数目和服务时间输入过程、服务员数目和服务时间均有关系均有关系K K是离散随机变

20、量，其是离散随机变量，其统计平均值记为统计平均值记为 , ,为平均队长为平均队长, ,用用N N表示表示p等待时间等待时间：顾客从到达系统开始接受服务的时间，连续随机变量顾客从到达系统开始接受服务的时间，连续随机变量p服务时间服务时间：顾客从开始接受服务离开系统的时间顾客从开始接受服务离开系统的时间p系统时间系统时间s：顾客从到达系统离开系统的时间，包括顾客的顾客从到达系统离开系统的时间，包括顾客的等待时等待时间及服务时间间及服务时间：s , ,p系统效率系统效率：即平均窗口占用率即平均窗口占用率m m为窗口为窗口( (服务员服务员) )个数，个数，为占用的窗口数为占用的窗口数，为统计平均值为

21、统计平均值p稳定性稳定性：排队强度排队强度为顾客到达率，为顾客到达率，m m为系统服务速率为系统服务速率mmks29排队系统的几个指标排队系统的几个指标p稳定性稳定性：排队强度排队强度为顾客到达率，为顾客到达率，m m为为系统服务速率系统服务速率系统稳定：系统稳定：1,1,即即mm, ,顾客到达率小于系顾客到达率小于系统的服务速率，或者说单位时间内平均达到系统的服务速率，或者说单位时间内平均达到系统的顾客数小于平均离开系统的顾客数，系统统的顾客数小于平均离开系统的顾客数，系统稳定，可以不采取拒绝方式，即采用不拒绝方稳定，可以不采取拒绝方式，即采用不拒绝方式的系统，应该满足式的系统，应该满足11

22、1,1,即即m m, , 说明单位时间内平均达到说明单位时间内平均达到系统的顾客数多于平均离开系统的顾客数，系系统的顾客数多于平均离开系统的顾客数，系统稳定性无法保障，采用拒绝方式才能保障稳统稳定性无法保障，采用拒绝方式才能保障稳定性，即当系统采取拒绝方式时，允许定性，即当系统采取拒绝方式时，允许1 1计算机通信网中，计算机通信网中，的定义为：的定义为：mCm李特尔（李特尔（Little）定律）定律p对于一个平均到达率为对于一个平均到达率为的排队系统，有的排队系统，有skN注：此定律在稳定状态下（即注：此定律在稳定状态下（即t）下得出，二是它适合于）下得出，二是它适合于任何种类的排队系统任何种

23、类的排队系统s31p表示：表示：X/Y/m/nX为为顾客到达间隔时间顾客到达间隔时间的分布，的分布，Y 为为服务时间服务时间的分布，的分布，m为为服务服务员员的个数，的个数，n为排队系统中为排队系统中允许允许的的顾客数顾客数(队长队长) n为为时为时为不拒绝方式不拒绝方式，可省略；，可省略；无特别说明，顾客源均为无限且采取顺序服务（先到先服务）无特别说明，顾客源均为无限且采取顺序服务（先到先服务）方式。方式。p分类分类M/M/m/n排队系统（掌握）排队系统（掌握）M/D/1排队系统排队系统M/Ek/1排队系统排队系统M/Hk/1排队系统排队系统其中，其中，M：负指数时间分布；：负指数时间分布；

24、D：定长时间分布；：定长时间分布；Ek：k阶爱尔兰时间分阶爱尔兰时间分布；布；Hk：k阶超指数时间分布阶超指数时间分布排队系统的表示与分类排队系统的表示与分类32M/M/m/n排队系统排队系统p顾客到达间隔时间的分布与服务时间的分布均为负顾客到达间隔时间的分布与服务时间的分布均为负指数分布指数分布p当队长不受限时，当队长不受限时， n=时为时为不拒绝方式不拒绝方式，可省略，可省略，表示为表示为M/M/mp当当mn时，为时，为混合制排队系统混合制排队系统 （延时拒绝方式）（延时拒绝方式）p当当n=m时，为时，为损失制系统损失制系统（即时拒绝即时拒绝方式，因为队方式，因为队长包括正在接受服务的人，

25、长包括正在接受服务的人， n=m 表示没有人排队，表示没有人排队，全部在接受服务）全部在接受服务）p当当m=1且且n=时时，为，为M/M/1系统，是最简单的排队系系统，是最简单的排队系统统(为不拒绝方式为不拒绝方式)33服务机构服务机构n泊松输入过程泊松输入过程一个服一个服务员务员指数服务指数服务时间分布时间分布图图 M/M/1排队模型排队模型M/M/1排队系统排队系统p特点：特点：顾客到达间隔时间顾客到达间隔时间T服从参数为服从参数为的的负指数分布负指数分布( (泊泊松分布松分布) )，概率密度函数为，概率密度函数为平均到达时间间隔为平均到达时间间隔为1/1/，平均服务时间，平均服务时间1/

26、1/到达的顾客到达的顾客能全部能全部进入系统进入系统排队排队，然后接受服务，然后接受服务系统只有一个服务员系统只有一个服务员(m=1)(m=1)一个顾客的服务时间一个顾客的服务时间服从参数为服从参数为的的负指数分布，负指数分布，概率密度函数概率密度函数为为 排队强度排队强度为为 / /)0()()(tedttdFtftTT)0()(tetftM/M/1系统指标（重要公式）系统指标（重要公式）系统稳定时系统稳定时(t)队长为队长为k的概率的概率即系统里面有即系统里面有K个顾客的概率个顾客的概率N1111)1 (NS011pkk 10pkkp)1(1.)32)(1 ()1 (3200kkkkkkp

27、kN平均队长平均队长或或平均系统时间平均系统时间平均等待时间平均等待时间系统效率系统效率1)1 (10kppkk / NsW11111136计算机通信网中的计算机通信网中的M/M/1系统指标系统指标将以下所有的将以下所有的换成换成C C：系统稳定时队长为系统稳定时队长为k的概率的概率 10pkkp)1(1.)32)(1 ()1 (3200kkkkkkpkN平均队长平均队长或或平均系统时间平均系统时间平均等待时间平均等待时间系统效率系统效率1)1 (10kppkkCNCCNS1111)1 (CNCCCsW111111 /( C)Cpkk01137011pkk为了提高效率，希望为了提高效率，希望大

28、些，但是平均等待时间也会增大，大些，但是平均等待时间也会增大，又希望又希望小一些，所以，系统效率和平均等待时间之间小一些，所以，系统效率和平均等待时间之间有矛盾，有矛盾， 的取值要兼顾一下两者，以求取得最佳结果。的取值要兼顾一下两者，以求取得最佳结果。NsW111.1111111平均等待时间平均等待时间系统效率系统效率38p例例2.2 在以在以M/M/1为模型的分组传输系统中，设分组的平均到为模型的分组传输系统中，设分组的平均到达率达率=1.25=1.25分组分组/s(/s(秒秒) )，分组长度服从指数分布，平均长度，分组长度服从指数分布，平均长度为为1/1/=960bit/=960bit/分

29、组，输出链路的传输速率分组，输出链路的传输速率C=2400(bit/s).C=2400(bit/s).求求: :（1 1）每一分组在系统中所经过的平均时延；）每一分组在系统中所经过的平均时延；（2 2）系统中平均分组数；）系统中平均分组数；（3 3）系统效率）系统效率CCNS1111)1 (CN /(C)Cpkk011392011年年p(1)(1)可求出可求出C C，分组平均长度为，分组平均长度为1/1/; ;CNCNCCCsW111111402012年年10月月CCNS1111)1 (CN41p45.某某M/M/1排队系统。设顾客的平均到达率排队系统。设顾客的平均到达率为为2.5(顾顾客客/

30、秒秒)。系统平均队长为。系统平均队长为5（顾客）。试计算：（顾客）。试计算：p（1）系统的平均服务速率；）系统的平均服务速率；p（2）每位顾客在系统中的平均等待时间。）每位顾客在系统中的平均等待时间。NNsW11111142p48.一个以一个以M/M/1为模型的数据集中器，统计时分复用，共连为模型的数据集中器，统计时分复用，共连10个终端，假个终端，假设每个终端平均设每个终端平均8秒输出一个数据分组，每个分组的长度服从指数分布，其秒输出一个数据分组，每个分组的长度服从指数分布，其平均长度为平均长度为960比特比特/分组，输出链路的传输速率为分组，输出链路的传输速率为2400比特比特/秒。秒。p

31、（1）求该集中器的缓存器的平均占用量，单位分组。）求该集中器的缓存器的平均占用量，单位分组。p（2）如果终端增加到）如果终端增加到20个系统的稳定性如何个系统的稳定性如何CN1.)32)(1 ()1 (3200kkkkkkpkN第二节第二节 图论基础知识图论基础知识p图的定义图的定义设有点集设有点集V=v1, v2, vn和边集和边集E=e1,e2,em,如果对任一属于如果对任一属于E的边的边ek,有有V中的一个中的一个点对点对(vi, vj)与之对应，则图可与之对应，则图可用有序二元组用有序二元组(V,E)表示，记为表示，记为 G = (V,E)一、图的基本概念一、图的基本概念44第二节第二

32、节 图论基础知识图论基础知识p相关概念相关概念端点端点:如果边如果边ek与点对与点对(vi, vj)相对应，则相对应，则vi, vj是是ek的的端点，记为端点，记为ek=( vi, vj)关联关联: 点点vi, vj 与边与边ek关联关联相邻点相邻点: vi与与vj 互为相邻点互为相邻点相邻边相邻边:两条边与同一端点相关联，则这两条边为相两条边与同一端点相关联，则这两条边为相邻边邻边度数度数(或次数或次数):与同一端点相关联的边的个数与同一端点相关联的边的个数图例图例p图记为图记为G=(V, E)V=v1,v2,v3,v4,v5E=e1, e2, e3, e4, e5, e6, e7p边用关联

33、的点对表示为边用关联的点对表示为V3V1V4V5V2e3e1e5e7e2e4e6e1 = (v1, v2), e2 = (v2, v3), e3 = (v1, v3)e4 = (v3, v4), e5 = (v3, v5), e6 = (v4, v5)e7 = (v1, v5)v1 与与e1 , e3, e7关联，关联， v1的度数为的度数为3 v1与与v2,v3,v5是相邻点是相邻点e1 与与e2 , e3， e7是相邻边是相邻边46p一个图只由它的一个图只由它的点集点集V、边、边E和点与边的关系和点与边的关系所确所确定，与定，与点的位置、边的长度与形状无关点的位置、边的长度与形状无关，即一

34、个，即一个图所对应的几何图形不是惟一的。图所对应的几何图形不是惟一的。p以下表示相同的图。以下表示相同的图。V3V1V4V5V2e3e1e5e7e2e4e6e6V3V1V4V5V2e3e1e5e7e2e4链路、路径与回路链路、路径与回路p链路链路对于图对于图G=(V,E)，其中，其中k(2)条边和与之关联条边和与之关联的端点依次排成点和边的交替序列，此序列为的端点依次排成点和边的交替序列，此序列为链路链路。边的数目边的数目k称为称为链路长度链路长度。p路径路径无重复边和点的链路。无重复边和点的链路。p回路回路起点和终点重合的路径。起点和终点重合的路径。链路：链路：v1, e3, v3, e4,

35、 v4, e8, v3, e5, v5, e6, v4,长度为长度为5路径：路径：v1, e1, v2, e2, v3, e5, v5,长度为长度为3回路：回路：v1, e1, v2, e2, v3, e5, v5, e7, v1 ,长长度为度为4V3V1V4V5V2e3e1e5e7e2e4e6e9e8链路、路径与回路链路、路径与回路p链路链路对于图对于图G=(V,E)，其中，其中k(2)条边和与之关联条边和与之关联的端点依次排成点和边的交替序列，此序列为的端点依次排成点和边的交替序列，此序列为链路链路。边的数目边的数目k称为称为链路长度链路长度。p路径路径无重复边和点的链路。无重复边和点的链

36、路。p回路回路起点和终点重合的路径。起点和终点重合的路径。链路：链路：v1, e3, v3, e4, v4, e8, v3, e5, v5, e6, v4,长度为长度为5路径：路径：v1, e1, v2, e2, v3, e5, v5,长度为长度为3回路：回路：v1, e1, v2, e2, v3, e5, v5, e7, v1长度为长度为4V3V1V4V5V2e3e1e5e7e2e4e6e9e849链路、路径与回路链路、路径与回路自环两个端点重合为一点的边称为自环。如自环两个端点重合为一点的边称为自环。如e9并行边与同一对端点关联的两条或两条以上的边。如并行边与同一对端点关联的两条或两条以上

37、的边。如e4和和e8V3V1V4V5V2e3e1e5e7e2e4e6e9e8图的分类图的分类p有限图和无限图有限图和无限图集合集合V和和E都是都是有限集有限集所构成的图称为所构成的图称为有限图，有限图，否则为否则为无限图无限图p简单图和复杂图简单图和复杂图没有自环和并行边没有自环和并行边的图称为的图称为简单图简单图，否则为，否则为复杂图复杂图p有向图和无向图有向图和无向图图的图的任一条边任一条边都对应一个都对应一个有序点对有序点对则为则为有向图有向图，否则为，否则为无向图无向图p有权图与无权图有权图与无权图图的图的每条边每条边都有一个都有一个实数值实数值对应，则称为对应，则称为有权图有权图，否

38、则为，否则为无权图无权图p连通图与非连通图连通图与非连通图图中图中任意两点之间至少存在一条路径任意两点之间至少存在一条路径，则为，则为连通图，连通图，否则为否则为非连通图非连通图非连通图是由几部分组成的，所谓的部分就是非连通图的一个组成部非连通图是由几部分组成的，所谓的部分就是非连通图的一个组成部分，且这个部分图是连通的。分，且这个部分图是连通的。51p有向图有向图用尖括号表示其中的端点是有序的用尖括号表示其中的端点是有序的与与是两条不同的边是两条不同的边通常在几何图形中用点通常在几何图形中用点vi指向指向vj的箭头表示边的箭头表示边用点用点vj 指向指向vi的箭头表示边的箭头表示边p无向图无

39、向图在无向图中，（在无向图中，（vi, vj）=（vj, vi），表示同一条边），表示同一条边52p例例2.3 写出图写出图2-2-4（a）和（）和（b）的点）的点集、边集和边的权值集、边集和边的权值53子图、真子图、生成子图子图、真子图、生成子图p图图G的点集和边集分别是图的点集和边集分别是图G的点集和边集的子集，的点集和边集的子集，则称为图则称为图G是图是图G的的子图子图。记为。记为G Gp若若G G，但，但GG,则称则称G是是G的的真子图真子图。p若若V=V,E E，则称，则称G是是G的的生成子图生成子图。p即即含有含有G的所有顶点的子图的所有顶点的子图称为称为G的的生成子图生成子图。p

40、一个图一个图不只一个不只一个生成子图。生成子图。原图原图真子图真子图真子图真子图生成子图生成子图树树p树的定义树的定义树树一个无回路的连通图称为树一个无回路的连通图称为树树枝树枝树中的边（包括树干和树尖）树中的边（包括树干和树尖）树干树干两个端点两个端点都至少与两条边都至少与两条边关联的树枝关联的树枝树尖、树叶树尖、树叶树枝的树枝的一个端点仅与此边关联一个端点仅与此边关联，此树枝为树尖，该端点为树叶此树枝为树尖，该端点为树叶树尖树尖树尖树尖 树尖树尖树尖树尖树尖树尖树尖树尖树叶树叶树叶树叶树叶树叶树叶树叶树叶树叶树干树干树干树干树干树干55树树p树的定义树的定义树可记为树可记为T，用，用全部的

41、树枝的集合全部的树枝的集合来表示。来表示。T= e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12 p树的分类树的分类根树根树星树：每一条边都是树尖星树：每一条边都是树尖线树：端点的度数最多不超过线树：端点的度数最多不超过2，只有两个树，只有两个树尖与树叶尖与树叶57p树的性质（枝路连回叶）树的性质（枝路连回叶）具有具有n个点的树共有个点的树共有n1个树枝个树枝树中任意两个点之间只存在一条路径树中任意两个点之间只存在一条路径树是连通的，去掉任一条边便不连通，即最小树是连通的，去掉任一条边便不连通，即最小连通图连通图树无回路，但增加一条边便可构成回

42、路树无回路，但增加一条边便可构成回路任一棵树至少有任一棵树至少有两片树叶两片树叶,即树至少有即树至少有两个端的两个端的度数为度数为1图的支撑树图的支撑树p支撑树（生成树）支撑树（生成树）如果一棵如果一棵树树T为一个连通图为一个连通图G的的子图子图，且，且包括包括G中所有中所有的点的点，则该树为，则该树为G的的支撑树支撑树。只有连通图才有支撑树只有连通图才有支撑树一个连通图一个连通图至少至少有一棵支撑树有一棵支撑树支撑树上的边构成支撑树上的边构成树枝集树枝集，支撑树外的边构成，支撑树外的边构成连枝集连枝集。原图原图支撑树支撑树1支撑树支撑树2图的阶和空度图的阶和空度p阶阶连通图连通图G的的支撑树

43、支撑树T的树枝数的树枝数称为称为图的阶图的阶，记作，记作若图若图G有有n个端点，则它的个端点，则它的阶阶为为n1p空度空度连枝数连枝数图的支撑树以外的边图的支撑树以外的边连通图连通图G的连枝数称为的连枝数称为图的空度图的空度，记作，记作当图当图G G有有m m条边时，其空度条边时，其空度m mn n1 1，即，即m m空度的意义空度的意义表示主树覆盖图的程度，表示主树覆盖图的程度，越小，覆盖程度越高，越小，覆盖程度越高， =0=0表示图表示图G G本身就是一棵树本身就是一棵树反映图的联结程度，反映图的联结程度， 越大，连枝数越多，图的联结性越大，连枝数越多，图的联结性越好，越好， =0=0表示

44、最低联结性表示最低联结性割割p割端割端令令v是图是图G的一个端，的一个端，去掉去掉v和与之相关联的边后，和与之相关联的边后，若使若使G的的部分数增加部分数增加或使或使G变为变为非连通的非连通的，则，则v是是G的的割端割端部分部分是原图的一部分（子图），且是连通的是原图的一部分（子图），且是连通的p割端集割端集去掉几个端后，使非连通图的部分数增加，或使去掉几个端后，使非连通图的部分数增加，或使连通图变为非连通图，则这些端的集合称为连通图变为非连通图，则这些端的集合称为割端割端集集右图的割端集：右图的割端集：v4,v2,v3,v2,v4,v3,v4v1,v4其中其中v4为割端为割端V3V1V4V5

45、V2V6p割边集割边集令令S是连通图是连通图G的边子集，如果的边子集，如果在在G中去掉中去掉S能使能使G成为非连通图成为非连通图，则，则S是是G的割边集的割边集p割集割集若若S的任何真子集都不是割边集的任何真子集都不是割边集，则，则S为为割割集，即最小割边集集，即最小割边集右图的割边集是右图的割边集是e1,e2,e3,e5，但不是，但不是割集，因为其真子集割集，因为其真子集e1,e2是割边集是割边集割集为：割集为：e1,e3,e5,e1,e2,e4,e5,e1,e3,e4,e2,e3,e5,e2,e3,e4V3V1V4V2e1e2e4e5e3联结度、结合度、连通度联结度、结合度、连通度p联结度

46、：最小割端集的端数联结度：最小割端集的端数称为图的联结度。称为图的联结度。p结合度：最小割集的边数结合度：最小割集的边数称为图的结合度。称为图的结合度。p连通度：联结度和结合度统称为连通度。连通度：联结度和结合度统称为连通度。联结度是点连通度联结度是点连通度结合度是边连通度结合度是边连通度对于通信网来说，连通度越高，可靠性对于通信网来说，连通度越高，可靠性越好越好最短路径最短路径p最短路径最短路径即最小支撑树（即最小支撑树（MST）图的支撑树中，具有权值之和最小的支撑树图的支撑树中，具有权值之和最小的支撑树p最小支撑树的应用最小支撑树的应用路由计算路由计算p求最小支撑树的方法求最小支撑树的方法

47、Kruskal方法方法(K方法方法)Prim方法方法(P方法方法)Kruskal方法（方法（K方法）方法）p将连通图将连通图G中的所有边按权值中的所有边按权值递增的次序递增的次序排列排列(如果如果有两条以上的权值相等，可任意排列有两条以上的权值相等，可任意排列)p选取选取G中中权值最小的边为权值最小的边为树枝，然后每下一步从树枝，然后每下一步从G中中所有所有留下边中留下边中选取与前次选出的选取与前次选出的诸边不构成回路诸边不构成回路的的另一条另一条最短边最短边（如几条相同，可依次选取）（如几条相同，可依次选取）p重复前两步重复前两步直至直至n-1条边条边已经选完已经选完p按上述方法选出的按上述

48、方法选出的n-1条边就构成最小支撑树条边就构成最小支撑树K方法例题方法例题1V3V1V4V5V2V6V2V3V4V5V6V1310934V2715138V3101116V4815V510顺顺序序边边距距离离顺顺序序边边距距离离顺序顺序边边距距离离1(v1,v2)36(v4,v5)811(v3,v5)112(v1,v5)37(v1,v4)912(v2,v5)133(v1,v6)48(v1,v3)1013(v2,v4)154(v2,v3)79(v3,v4)1014(v4,v6)155(v2,v6)810(v5,v6)1015(v3,v6)161.先选先选(v1,v2)为树枝，权值为为树枝，权值为3

49、2.选选(v1,v5)为树枝，权值为为树枝，权值为3，没构成回路，没构成回路3.选选(v1,v6)为树枝，权值为为树枝，权值为44.选选(v2,v3)为树枝，权值为为树枝，权值为75.选选(v2,v6)为树枝，权值为为树枝，权值为8，构成回路，舍去，构成回路，舍去6.选选(v4,v5)为树枝，权值为为树枝，权值为8权值（距离）递增排列（权值（距离）递增排列（km）K方法例题方法例题2例题例题2例题例题2例题例题2例题例题2例题例题2例题例题273Prim方法（方法（P方法）方法）pPrim方法（方法（P方法）思路：方法）思路：任意选择一个点任意选择一个点vi，将它与，将它与vj相连，同时使（相

50、连，同时使（vi, vj）具有的权值最小，再从）具有的权值最小，再从vi,vj以外的其他各点以外的其他各点中选取一点中选取一点vk与与vi或或vj相连，同时使所连两点的相连，同时使所连两点的边具有最小的权值，重复这一过程，直到将所边具有最小的权值，重复这一过程，直到将所有点相连，就可得到连接有点相连，就可得到连接n个节点最小支撑树。个节点最小支撑树。pP方法实现的几种：方法实现的几种：根据观察各连的权值直接得出最小支撑树根据观察各连的权值直接得出最小支撑树利用权值矩阵找出最小支撑树利用权值矩阵找出最小支撑树加权因数法加权因数法54741234655651732546123465132 设最小支

51、撑树的节点集合为设最小支撑树的节点集合为U，对应的边集合为，对应的边集合为E，初始时，初始时U与与E均为空。均为空。从节点开始，选最小权值的边从节点开始，选最小权值的边1，节点（，节点（，）入）入U;边（，边（，）加入）加入 E；从从G-E中选最小权值边中选最小权值边4，且对应节点，且对应节点不在不在U中，中， 入入U;边（边（， ）加入）加入 E从从G-E中选最小权值边中选最小权值边2，且对应节点，且对应节点不在不在U中，中， 入入U;边（边（ ， ）加入）加入 E从从G-E中选最小权值边中选最小权值边5，且对应节点不在，且对应节点不在U中，入中，入U;边（边（ ， ）加入）加入 E从从G-

52、E中选最小权值边中选最小权值边3，且对应节点不在，且对应节点不在U中，中， 入入U;边（边（ , ）加入）加入 E753.具有约束条件的最小支撑树具有约束条件的最小支撑树p在计算机通信网的网络结构设计中，经常会提出在计算机通信网的网络结构设计中，经常会提出一些特殊的要求，如一些特殊的要求，如某交换节点或某段线路上的某交换节点或某段线路上的业务量不能过大，任意两点间经过转接的次数不业务量不能过大，任意两点间经过转接的次数不能过多能过多等，这时的问题就变为求等，这时的问题就变为求有约束条件的最有约束条件的最小支撑树小支撑树的问题的问题p求有约束条件的最小支撑树的方法：求有约束条件的最小支撑树的方法

53、：先先按上述介按上述介绍的绍的K方法或方法或P方法方法求出无约束条件求出无约束条件的最小支撑树，的最小支撑树，然后根据所给的约束条件，对网络结构然后根据所给的约束条件，对网络结构进行调整进行调整，使之既满足约束条件，又尽量接近最小支撑树。使之既满足约束条件，又尽量接近最小支撑树。第三节第三节 网络拓扑设计网络拓扑设计p对计算机通信网的对计算机通信网的基本要求基本要求有以下几点有以下几点(连可快高经灵连可快高经灵)：连通性：连通性：网内任意两个用户可以互通信息，影响连通性网内任意两个用户可以互通信息，影响连通性因素：因素：业务量超过容量；出现故障业务量超过容量；出现故障可靠性：可靠性：通信网内的

54、信道和设备通信网内的信道和设备不易出故障不易出故障（平均故障（平均故障时间要长），即使某些设备或信道有故障时，有备用设时间要长），即使某些设备或信道有故障时，有备用设备和信道可以利用或迂回。备和信道可以利用或迂回。快速通信：快速通信：处理与传输时延尽量小处理与传输时延尽量小高质量：信噪比大，误码率低高质量：信噪比大，误码率低，但并不要求全网的质量，但并不要求全网的质量指标完全一致。指标完全一致。灵活性：灵活性：新用户进网、提供新业务、与其他网连网与不新用户进网、提供新业务、与其他网连网与不断扩容的灵活性断扩容的灵活性经济合理性：综合考虑经济合理性：综合考虑可靠性与经济性等指标，达到可靠性与经济

55、性等指标，达到合合理。理。对计算机通信网的基本要求对计算机通信网的基本要求 连通性连通性 可靠性可靠性 快速通信快速通信 高质量高质量 灵活性灵活性 经济合理性经济合理性网络拓扑设计问题或内容网络拓扑设计问题或内容:p网络拓扑设计的问题（或或内容）网络拓扑设计的问题（或或内容）是指：是指：在给定交换节点和终端在给定交换节点和终端（包括计算机）（包括计算机）位置的情况下，通过选择合适的通路位置的情况下，通过选择合适的通路（即如何连接各节点和终端）（即如何连接各节点和终端），合理地，合理地分配线路的容量和流量，保证一定的可分配线路的容量和流量，保证一定的可靠性、时延和吞吐量靠性、时延和吞吐量（吞吐

56、量为网络每（吞吐量为网络每秒钟所能通过的总的分组数），秒钟所能通过的总的分组数），并使网并使网络成本（费用）最低。络成本（费用）最低。网络拓扑设计问题或内容网络拓扑设计问题或内容:已知已知:节点位置节点位置 终端位置终端位置待求待求:(1)通路选择通路选择 可靠性可靠性 (2)通路容量、流量的分配通路容量、流量的分配 导致不同导致不同 时延时延 (3)成本最低成本最低 费用低费用低 吞吐量吞吐量网络拓扑设计方法网络拓扑设计方法p网络拓扑设计的一般方法网络拓扑设计的一般方法：将整个网络划分为小的子网将整个网络划分为小的子网在子网内再进行拓扑设计在子网内再进行拓扑设计比较常用的方法比较常用的方法

57、：将整个网络划分为两：将整个网络划分为两大部分，即大部分，即主干网主干网（Backbone）和本地）和本地接入网接入网（Access Network）.网络拓扑设计方法网络拓扑设计方法p主干网主干网:主干网也称为干线网，它是整个网络的骨干，它将分组交换主干网也称为干线网，它是整个网络的骨干，它将分组交换 节点连接节点连接成一个成一个分布式分布式的多路由网络，其的多路由网络，其可靠性和链路速率可靠性和链路速率均较高。均较高。p本地接入网本地接入网:也称本地访问网，它将用户的数据送往主干网，其也称本地访问网，它将用户的数据送往主干网，其链路速链路速 率较低率较低，一，一般没有必要采用分布式的拓扑结

58、构。本地接入网般没有必要采用分布式的拓扑结构。本地接入网是整个网是整个网 络的基础络的基础。 当本地接入网内有许多终端时，可以将众多的终端通过终端控制当本地接入网内有许多终端时，可以将众多的终端通过终端控制 器与器与集中器相连，然后再由集中器连到主干网。集中器相连，然后再由集中器连到主干网。对一个集中器来说，一对一个集中器来说，一 个终端控制器的接入就相当于一个终端的接入。个终端控制器的接入就相当于一个终端的接入。通常将直接与集中器相连的设备称为一个客户场地通常将直接与集中器相连的设备称为一个客户场地(Customer Site，可能是一个或通过终端控制器连接起来的多个终端可能是一个或通过终端

59、控制器连接起来的多个终端)终端控制器又称为群集器终端控制器又称为群集器，它具有，它具有报文转发、差错控制和轮询报文转发、差错控制和轮询等功能，等功能，但不如集中器那样有足够的智能可以进行复用和速率转换但不如集中器那样有足够的智能可以进行复用和速率转换。本地接入网的特点是采用本地接入网的特点是采用树状或星形树状或星形拓扑，以便使路由问题变得很简拓扑，以便使路由问题变得很简单。单。网络划分网络划分p两大子网两大子网主干网主干网本地接入网本地接入网p本地接入网设计内容本地接入网设计内容集中器位置的规定集中器位置的规定客户场地的分配客户场地的分配(哪一个客户场地应连接到哪一个集中哪一个客户场地应连接到

60、哪一个集中器器)终端的布局终端的布局(客户场地内终端如何分布客户场地内终端如何分布-最小生成树或支最小生成树或支撑树撑树)p主干网设计内容主干网设计内容主干网的主干网的拓扑拓扑主干网的主干网的时延时延主干网的主干网的线路容量线路容量主干网的主干网的流量分配流量分配本地接入网设计内容本地接入网设计内容 集中器集中器 群集器群集器(T.C) 终端终端 选址选址 客户场地客户场地 布局布局 分配分配客户场地的分配客户场地的分配(哪一个客户场地应连接到哪一个集中器哪一个客户场地应连接到哪一个集中器) j i 0 1 1 2 2 3 7 4 8 m n终端布局终端布局 k方法方法求最小支撑树求最小支撑树 （最短路径）（最短路