1、21) 学会用数学的语言研究计算机通信网学会用数学的语言研究计算机通信网2) 学会用随机的思想看待计算机通信网学会用随机的思想看待计算机通信网3) 掌握各种计算机通信网的性能分析技巧掌握各种计算机通信网的性能分析技巧4) 加深对计算机通信网工作原理的理解加深对计算机通信网工作原理的理解 - 不仅要不仅要知其然知其然，还要，还要知其所以然知其所以然 本课程主要讲授计算机通信网的性能分析、资源分配与流量控本课程主要讲授计算机通信网的性能分析、资源分配与流量控制理论，传授如何采用应用概率论、随机过程以及排队论的手法解制理论，传授如何采用应用概率论、随机过程以及排队论的手法解决计算机通信网的设计与优化
2、问题决计算机通信网的设计与优化问题3第一章第一章 计算机通信网络概述计算机通信网络概述第二章第二章 随机过程与随机服务过程概论随机过程与随机服务过程概论第三章第三章 重要的概率分布和重要的随机过程重要的概率分布和重要的随机过程第四章第四章 马尔可夫链和马尔可夫过程马尔可夫链和马尔可夫过程第五章第五章 排队论排队论第六章第六章 计算机网络性能分析计算机网络性能分析第七章第七章 计计算机网络模拟算机网络模拟4参考文献参考文献 - 排队理论排队理论(英文英文)1.L. Kleinrock: Queueing Systems：vol.1, Theory. vol.2, Computer Applica
3、tions，John Wiley and Sons, 1975/76.2. R. B. Cooper, “Introduction to Queueing Theory”, 2nd ed, North-Holland,19813.D. Gross and C. M. Harris, “Fundamentals of Queueing Theory”, 2nd ed John Wiley & Sons, New York, 19854.E. Gelenbe and G. Pujolle, “ Introduction to queueing networks”, Chichester New Y
4、ork Wiley, 1987.5.H. Takagi, “Queueing Analysis, A Foundation of Performance Evaluation”, vol.1-3, North-Holland, 1993.6.M. F. Neuts: Matrix-Geometric Solutions in Stochastic Models: An algorithmic approach, Dover Publications, Inc., 1981.7.M. F. Neuts, Structured Stochastic Matrices of M/G/1 Type a
5、nd its applications, Marcel Dekker, 1989.8.V. B. Iversen, “Teletraffic Engineering Handbook”, ITU-D, http:/www.tele.dtu.dk/teletraffic, 20019.R. Syski, “Introduction to Congestion Theory in Telephone Systems” (2nd ed), North-Holland, 1986 (1st ed in 1960)10. J. Roberts, “Traffic Theory and the Inter
6、net”, IEEE Commu. Mag., Jan. 2001.11. J.F.Hayes,”Modeling and Analysis of Computer Communications Networks, “448.7 H4175参考文献参考文献 - 排队理论排队理论(中文中文)1.徐光辉:随机服务系统随机服务系统2.陆凤山:排队论及其应用排队论及其应用, 湖南科学技术出版社,19843.孟玉珂:排队论基础及应用排队论基础及应用, 同济大学出版社，19894.周炯磐:通信网理论基础通信网理论基础, 人民邮电出版社，19915.陆传玺:排队论排队论, 北京邮电学院出版社，19936.官
7、建成：随机服务过程及其在管理中的应用随机服务过程及其在管理中的应用，北京航空航天大学出版社，1994. 09311 30157.盛友昭:排队论及其在计算机通信中的应用排队论及其在计算机通信中的应用, 北京邮电大学出版社，1998 .TN919 53458.陈鑫林:现代通信中的排队论现代通信中的排队论, 电子工业出版社,19999.Kawashima, Machihara, Takahashi, Saito著，岳五一、吕廷杰译:通信流理论基础与多媒体通信网通信流理论基础与多媒体通信网, 清华大学出版社，200010. 唐应辉等著：排队论排队论(基础与应用基础与应用)， 电子科大出版社，20001
8、1. 林闯:计算机网络和计算机系统的性能评价计算机网络和计算机系统的性能评价, 清华大学出版社，200112. 田乃硕:休假随机服务系统休假随机服务系统，北京大学出版社,200113. 孙荣恒,李建平：排队论基础排队论基础，科学出版社，20026参考文献参考文献- 计算机网络中的应用计算机网络中的应用1. D. Bertsekas and R. Gallager, “Data Networks”, Prentice Hall, 1992 （中文翻译：数据网络，人民邮电出版社，2004）2.McDysan, “QoS and Traffic Management in IP and ATM ne
9、tworks”, McHill,1999.3.M. Schwartz: “Telecommunication Networks：Protocols，Modeling，and Analysis”，Addison-Wiley，1987. （中译本：“电信网：协议，建模与分析”,人民邮电出版社, 1991）4.M. Schwartz, “Mobile Wireless Communications”, Cambridge Univ. Press,20055.P. G. Harrison, N. M. Patel: Performance Modeling of Communication Netwo
10、rks and Computer Architectures, Addison-Wesley, 1992.6.Minoli, Broadband Network Analysis and Design, Arche-House, 1993.7.Thomas G. Robertazzi, “Computer networks and systems : queueing theory and performance evaluation”. New York : Springer-Verlag, 1990.8.John N. Daigle, “Queueing theory for teleco
11、mmunications”, Addison-Wesley Pub. Co., 1992.7主要参考科技期刊与国际会议主要参考科技期刊与国际会议1. “Queueing Systems: Theory and Applications (QUESTA)”, Baltzer Publisher (Netherland)2.“Performance Evaluations”, North-Holland3.“Stochastic Models”, Marcel Dekker4.“J. of Operation Research Society of America (ORSA)”5.“J. of
12、Operation Research Society of Japan (ORSJ)”6.“The Bell System Technical Journal”7.“IEEE Trans. Commun.”8.“IEEE J. Selected Area on Commun. (JSAC)”9.“IEEE/ACM Trans. Networking”10. “International Teletraffic Congress (ITC)” and ITC Seminars 11. “International Federation of Operation Research Societie
13、s (IFORS) World Congress”12. “Asian Federation of Operation Research Societies (AFORS)”13. TIMS (The Institute of Management Science)14. IEEE Infocom, Globecom, ICC, etc8学术期刊和会议文献学术期刊和会议文献1 电子学报电子学报2 通信学报通信学报3 IEEE Trans. on Communications4 IEEE Trans. on Networks5 Computer Communications 6 ICC7 INF
14、OCOM8 GLBCOM9第一章第一章 计算机通信网概述计算机通信网概述1.1 计算机网络概述 1.1.1 计算机网络计算机网络的发展与分类 1.1.2 计算机网络的业务特性与性能需求1.2 计算机网络计算机网络理论概述 1.2.1 通信话务理论（通信流理论） 1.2.2 排队论 主要内容主要内容: 计算机通信网的基本工作原理；计算机通信网理论计算机通信网的基本工作原理；计算机通信网理论分析的重要性；计算机通信网理论的范畴及其发展史分析的重要性；计算机通信网理论的范畴及其发展史10第二章第二章 随机过程与随机服务过程概论随机过程与随机服务过程概论主要内容（主要内容（2、3、4章）章）:1. 通
15、信业务的分类及其业务特性通信业务的分类及其业务特性;2. 通信业务源的概率模型化（纯随机业务通信业务源的概率模型化（纯随机业务/平滑业务平滑业务/突发业务突发业务/相关业务的概率描述；相关业务的概率描述；3. 负指数分布负指数分布/爱尔兰分布爱尔兰分布/超指数分布超指数分布/几何分布几何分布/泊松分布的特性；泊松分布的特性；4. 泊松过程泊松过程/间歇泊松过程间歇泊松过程/交互泊松过程交互泊松过程/ON-OFF模型模型/马尔可夫调制泊松过程的特性；马尔可夫调制泊松过程的特性；5. 更新过程的基本概念；更新过程的基本概念；6. 方差系数方差系数/分散指数分散指数/相关系数的概念；相关系数的概念；
16、7. 自相关业务模型；自相关业务模型；8. 通信网络的排队模型化（排队模型的基本组成；马尔可夫与非马尔可夫排队模型；生通信网络的排队模型化（排队模型的基本组成；马尔可夫与非马尔可夫排队模型；生灭过程；电路交换灭过程；电路交换/分组交换分组交换/ATM网络的建模）网络的建模）11第二章第二章 随机过程与随机服务过程概论随机过程与随机服务过程概论2.1 概率空间概率空间2.2 条件概率条件概率2.3 随机变量和随机过程随机变量和随机过程2.4 随机变量的分布函数和随机过程的概率分布随机变量的分布函数和随机过程的概率分布2.5 数学期望值与母函数数学期望值与母函数2.6 随机服务过程的基本概念随机服
17、务过程的基本概念2.7 随机服务系统的组成部分随机服务系统的组成部分2.8 随机服务过程的几个主要数量指标随机服务过程的几个主要数量指标12第三章第三章 重要的概率分布和重要的随机过程重要的概率分布和重要的随机过程3.1 负指数分布负指数分布3.2 k阶爱尔朗阶爱尔朗(Erlang)分布分布Ek3.3 二项式分布、几何分布和负二项式分布二项式分布、几何分布和负二项式分布3.4 泊松分布泊松分布(Possion)、泊松过程、泊松过程3.5 贝努利过程贝努利过程3.6 生灭过程生灭过程13第四章第四章 马尔可夫链与马尔可夫过程马尔可夫链与马尔可夫过程4.1 马尔可夫链的定义与转移概率马尔可夫链的定
18、义与转移概率4.2 马尔可夫链的状态分类马尔可夫链的状态分类4.3 常返状态及其极限概率常返状态及其极限概率4.4 周期状态及其极限概率周期状态及其极限概率4.5 马尔可夫过程定义马尔可夫过程定义4.6 纯不连续马尔可夫过程纯不连续马尔可夫过程4.7 齐次可数的纯不连续马尔可夫过程齐次可数的纯不连续马尔可夫过程4.8 转移概率函数的极限特性和状态分类转移概率函数的极限特性和状态分类14第五章第五章 排队论排队论5.1 排队论的领域与特征排队论的领域与特征5.2 排队模型排队模型5.3 马尔可夫排队模型马尔可夫排队模型5.4 非马尔可夫排队模型非马尔可夫排队模型15第五章第五章 排队论排队论 主
19、要内容主要内容: 排队模型与排队模型与Kendall记号；排队模型的参数及性能指记号；排队模型的参数及性能指标；标；Little定理；定理；PASTA定理；到达时刻与退去时刻状态概率等效性定定理；到达时刻与退去时刻状态概率等效性定理；理；#上述三个定理的证明及其推广上述三个定理的证明及其推广. 马尔可夫型排队模型的性能分析马尔可夫型排队模型的性能分析: 全局平衡与局域平衡的概念；全局平衡与局域平衡的概念；M/M/1, M/M/s, M/M/s(k)排队模型的队排队模型的队长分布及等待时间；长分布及等待时间；Erlang-B公式的物理意义及其在电路交换网中的公式的物理意义及其在电路交换网中的应用
20、；应用；M/M/s排队系统的退去过程与排队系统的退去过程与Burke定理；定理；*Engest公式；公式；*多维多维马尔可夫排队系统解析；马尔可夫排队系统解析；#马尔可夫排队系统的瞬态分析马尔可夫排队系统的瞬态分析 非马尔可夫型排队模型的性能分析非马尔可夫型排队模型的性能分析: M/G/1和和GI/M/1的嵌入马尔可夫链分析法；的嵌入马尔可夫链分析法；M/G/1模型的模型的P-K公式；公式；M/G/1(k)模型阻塞率的求解；模型阻塞率的求解；M/G/1型群到达排队系统的分析；型群到达排队系统的分析；GI/M/s模型的几何形式解；模型的几何形式解；*M/G/1与与GI/M/1模型的辅助函数分析法
21、；模型的辅助函数分析法；*M/G/1优先权排队模型的解析；优先权排队模型的解析；#M/G/1模型的忙期模型的忙期(busy period); #GI/G/1排排队模型的队模型的Lindley积分分析法；积分分析法；16第六章第六章 计算机网络性能分析计算机网络性能分析6.1 协议与设备协议与设备6.2 时分复用（时分复用（TDM）网络性能分析）网络性能分析6.3 具有优先级的环形网络性能分析具有优先级的环形网络性能分析6.4 轮询系统性能分析轮询系统性能分析6.5 拥挤和流控制分析拥挤和流控制分析6.6 基于路由流分配性能分析基于路由流分配性能分析6.7 QoS性能分析性能分析计算机网络资源分
22、配、路由选择及流量控制理论计算机网络资源分配、路由选择及流量控制理论17第一章第一章 计算机网络概述计算机网络概述 信息内容信息内容: 电话网、计算机网、电视网/CATV 复用方式复用方式: 频分、时分、码分、波分 交换方式交换方式: 电路、报文交换、分组(帧中继、IP、ATM) 传输方式：传输方式：模拟/数字、有线/无线、光纤/电缆18电路交换网络电路交换网络 Connection oriented: Connection set up end-to-end before information transfer Resources reserved for the whole durati
23、on of connection Information transfer as continuous stream Before information transfer Delay (to set up the connection) During information transfer No overhead No extra delays19无连接的分组交换网络无连接的分组交换网络 Connectionless: No connection set up No resources reservation Information transfer as discrete packets
24、 Varying length Global address( of the destination) Before information transfer No delay During information transfer Overhead (header bytes) Packet processing delays Queueing delays( since packets compete for joint resources)20 Connection oriented: virtual connections set up end-to-end before inform
25、ation transfer No resources reservation Information transfer as discrete packets Varying length local address( logical channel index) Before information transfer Delay (to set up the virtual connection) During information transfer Overhead (however,less than in connectionless mode) Packet processing
26、 delays(less, due to the shorter address) Queueing delays( since packets compete for joint resources)21 Connection oriented: virtual connections set up end-to-end before information transfer resources reservation possible but not mandatory Information transfer as discrete packets (cells) Fixed (smal
27、l) length local address Before information transfer Delay (to set up the virtual connection) During information transfer Overhead (per packet even more than in connectionless mode) Packet processing delays(less, due to the shorter address and the fixed length of cells) Queueing delays ( if resources
28、 not reserved beforehand)222324Set-up a static circuit (lightpath)Transfer dataRelease connectionSuitable for smooth, longer-term, high-bandwidth applicationsLong circuit set-up latencyInefficient for short-term bursty applications2526Packet header is processed all-optically at each node and switche
29、d to the next hopStatistical multiplexing of dataSuitable for bursty trafficbuffer27An out-of-band control header transmitted ahead of each data burstStatistical multiplexing of dataSuitable for bursty trafficLow data-transfer latencyElectronic control plane (practically feasible)Optical data plane
30、(high-speed)2829Layered Network Model30OBS Network Architecture31OBS Node Architecture32Question33 JET协议比别的协议有更高的通过率协议比别的协议有更高的通过率,更低的丢包率更低的丢包率,信道利用率较高信道利用率较高JET 协议的路由具有自己的特点协议的路由具有自己的特点, 在发送控制包时就应该知道要经过多少个在发送控制包时就应该知道要经过多少个节点节点, 这就需要源地址选路这就需要源地址选路, 而不能像一般而不能像一般IP 分组交换进行逐步的路由选路分组交换进行逐步的路由选路。34连通性：任意
31、、快速可靠性：迂回路由、自愈恢复、信息安全灵活性：突发业务、新业务经济性：价格性能比、最优化电话交换网(delay-sensitive) 低延迟、高接通性（迂回中继）；允许一定的信息丢失数据交换网(loss-sensitive) 低丢失率、高通过率（缓存）；允许一定程度的延迟多媒体网络(delay-and-loss sensitive) 低丢失率、低延迟、低抖动、高通过率；业务差分35 Performance evaluationGiven the system and the incoming traffic, whats the QoS experienced by the user? T
32、raffic controlGiven the system and QoS requirements, whats the maximum traffic load? System designGiven the incoming traffic and the required QoS, how should the system be dimensioned?3637 主要性能指标主要性能指标用户连接建立请求被拒绝的概率(面向连接网络)信息传输过程中被丢失的概率(链路误码、网络拥塞）信息被成功传送的概率（吞吐量）建立通信连接所需的时间(面向连接网络)：信息在网络中的滞留时间 节点（交换、
33、路由）处理延迟 排队等待延迟排队等待延迟 传播延迟等38好的拓扑结构应该有利于负载均衡网络越来越复杂，网管信令开销的影响不可忽视网络资源（带宽/缓冲器）是有限的、共享的网络的设计（平均）容量永远大于（平均）需求（如果业务需求是确定性的，网络不会发生拥塞）业务需求的随机性、特别是突发性会造成网络资源的浪费39 考虑一个简单的随机服务系统。顾客以随机的方式到达，平均间隔为4分钟。服务者以随机的方式为顾客提供服务，平均时间为3分钟。到达间隔和服务时间均为定长分布时，L=?到达间隔和服务时间均为负指数分布时，L=?到达间隔为负指数分布、但服务时间为定长分布时，L=?40The mean number
34、of calls per minute to a switching centre taken as an average for periods of 15 minutes during 10 working days (Monday Friday). At the time of the measurements there were no reduced rates outside working hours ( Iversen,197336).41Number of calls per 15 minutes to a modem pool of Tele Danmark Interne
35、t.42Mean holding time for trunk lines as a function of time of days.The measurements exclude local calls43Mean holding time in seconds as a function of time of days for calls arriving inside the period considered. Tele Danmark Internet. Tuesday 1999.01.19.44 Traffic Intensity (erl) = sessionLength x
36、 arrivals/second45Time of Day46业务需求的产生是随机的、突发的；业务所需要的服务时间也是随机的;有时甚至可得到的网络资源也是随机的业务的随机性可能会随时间变化“Errors using inadequate data are much less than those using no data at all”But caution is needed when conclusions are drawn47 光传输和光交换技术的发展带来无限的传输带宽，不会再有拥塞发生 概率模型要么不准确（过于近似）不实用、所建的数学模型要么太复杂无法求解 基于效用和博弈论的资源管
37、理模型4849 业务源特性不再容易精确预测 业务源特性在不断动态变化 网络拓扑结构也有可能是动态的 网络优化设计应与网络动态控制紧密结合 通过Traffic Management实现网络优化 PLR10-5 10-3 EPTD3ms 10-350 电话交换网的线路设计（大规模效应） 问：1）如果N=2N, S 2S ? 2）如果N=N/2, S S/2 ?51 综合网络/集中排队 分散网络/集中排队 分散网络/独立排队5253545556最贴近实际网络，可以直接推广应用多用于商业化运作之前的实际检验但开销巨大，试验周期长简便易行，比较接近实际网络多用于复杂网络性能的评估和验证但难以得到一般性结
38、论，且稀疏事件难以仿真简便易行，且容易抓住问题的实质多用于简单网络的性能预测和评估规划但需要引入近似，且难以应用到大规模复杂网络57网络的连通性，最短树，最大流等静态理论一般不考虑网络实际流量的随机特性基础理论为图论控制论/正反馈/负反馈/动态控制/动态路由网络资源分配与流量控制等问题基础理论为线性/非线性规划法等最优化理论5859又称电信话务量理论，主要研究电信网的优化设计起源于1909年和1917年A. K. Erlang的论文，首次用概率论的手法解决了电信交换机容量的设计问题，且一致沿用至今 A.K. Erlang: “Probability and Telephones”, Nyt.
39、Tidsskr. Mat. Ser. B, vol.20,pp.33-39, 1909 A. K. Erlang: “Solution of Some Problems in the Theory of Probabilities ofSignificance in Automatic Telephone Exchanges”, Post Office Elec. Eng. J.,vol.10, pp.189-197, 1917主要研究有顾客等待（队列）的随机服务系统，是运筹学的一个重要分支广泛应用于计算机网络、运输、生产、库存等各种资源共享随机服务系统60主要研究应用于电话网和远程通信系统等
40、无队列排队系统推广应用到军事、运输、生产、社会服务等领域，主要研究有队列的排队系统和排队网络主要研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带有各种网络控制的排队系统的研究61 1909: Erlang published his first paper on queueing theory 1917: Erlang published his famous paper “Solution .” 1936-47: Palm published “Repairmen in Serving Automatic Machines” Industritidn Norde
41、n 1951: Kendall published “Some Problems in the Theory of Queues” and in 1953 proposed to use Kendalls notation 1953-57: Kendall, Lindley, Pollaczek & Khinchin studied M/G/1 with embedded Markov chain method 1961: Little proved the Little Formula 1975/6: Kleinrock published the best known textbook in queueing theory 1982: Wolff proved and popularized the PASTA principle 1981: Neuts introduced the matrix analytic method
