计算机通信网络性能分析 The objective of this seminar is to cover all aspects of Asynchronous Transfer Mode (ATM) Traffic Management (TM) from the basics to the details. ATM is designed to transport a wide variety of traffic classes (CBR, VBR, ABR, UBR) with different characteristics and performance objectives. The cell delay variation (CDV), cell transfer delay (CTD), and cell loss ratio (CLR) are the key Quality of Service (QoS) parameters used to specify the required network performance. Several techniques have been defined to allow for the management and control of traffic and congestion in ATM networks in order to meet the performance targets. These include: Connection admission Control (CAC), Usage parameters control (UPC), priority control, and Traffic shaping. As the evolution to high-speed, multi-service networks continues, it is becoming vital for any telecommunications professional to understand and master the traffic management issues. About the presenter: Dr. Bilel Jamoussi is an Advisor on ATM Traffic Management and Advanced Internet Protocols. He has been working in Passport Development for the past four years. Bilel has been responsible for the development of ATM TM algorithms and their implementation and for emerging Internet Protocols. Bilel holds a BS, MS and Ph.D. degrees in Computer Engineering from the Pennsylvania State University. He received his Ph.D. in 1995 in the area of TCP/IP Traffic Characterization and Its Applications to ATM Network Design. Bilel authored and presented several technical papers in various IEEE International conferences. Dr. Sameh Rabie, Manager, Passport Traffic Management and Performance is acknowledged for his many contributions to the seminar material.

课程定位 定位： 1) 学会用数学的语言研究计算机通信网 2) 学会用随机的思想看待计算机通信网 3) 掌握各种计算机通信网的性能分析技巧 4) 加深对计算机通信网工作原理的理解 -- 不仅要知其然，还要知其所以然 内容梗概： 本课程主要讲授计算机通信网的性能分析、资源分配与流量控制理论，传授如何采用应用概率论、随机过程以及排队论的手法解决计算机通信网的设计与优化问题

课程章节安排 第一章 计算机通信网络概述 第二章 随机过程与随机服务过程概论 第三章 重要的概率分布和重要的随机过程 第一章 计算机通信网络概述 第二章 随机过程与随机服务过程概论 第三章 重要的概率分布和重要的随机过程 第四章 马尔可夫链和马尔可夫过程 第五章 排队论 第六章 计算机网络性能分析 第七章 计算机网络模拟 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

参考文献 - 排队理论(英文) L. Kleinrock: "Queueing Systems：vol.1, Theory. vol.2, Computer Applications"，John Wiley and Sons, 1975/76. R. B. Cooper, “Introduction to Queueing Theory”, 2nd ed, North-Holland,1981 D. Gross and C. M. Harris, “Fundamentals of Queueing Theory”, 2nd ed John Wiley & Sons, New York, 1985 E. Gelenbe and G. Pujolle, “ Introduction to queueing networks”, Chichester New York Wiley, 1987. H. Takagi, “Queueing Analysis, A Foundation of Performance Evaluation”, vol.1-3, North-Holland, 1993. M. F. Neuts: "Matrix-Geometric Solutions in Stochastic Models: An algorithmic approach", Dover Publications, Inc., 1981. M. F. Neuts, "Structured Stochastic Matrices of M/G/1 Type and its applications", Marcel Dekker, 1989. V. B. Iversen, “Teletraffic Engineering Handbook”, ITU-D, http://www.tele.dtu.dk/teletraffic, 2001 R. Syski, “Introduction to Congestion Theory in Telephone Systems” (2nd ed), North-Holland, 1986 (1st ed in 1960) J. Roberts, “Traffic Theory and the Internet”, IEEE Commu. Mag., Jan. 2001. J.F.Hayes,”Modeling and Analysis of Computer Communications Networks, “448.7 H417

参考文献 - 排队理论(中文) 徐光辉:《随机服务系统》 陆凤山:《排队论及其应用》, 湖南科学技术出版社,1984 参考文献 - 排队理论(中文) 徐光辉:《随机服务系统》 陆凤山:《排队论及其应用》, 湖南科学技术出版社,1984 孟玉珂:《排队论基础及应用》, 同济大学出版社，1989 周炯磐:《通信网理论基础》, 人民邮电出版社，1991 陆传玺:《排队论》, 北京邮电学院出版社，1993 官建成：《随机服务过程及其在管理中的应用》，北京航空航天大学出版社，1994. 0931·1 3015 盛友昭:《排队论及其在计算机通信中的应用》, 北京邮电大学出版社，1998 .TN919 5345 陈鑫林:《现代通信中的排队论》, 电子工业出版社,1999 Kawashima, Machihara, Takahashi, Saito著，岳五一、吕廷杰译:《通信流理论基础与多媒体通信网》, 清华大学出版社，2000 唐应辉等著：《排队论(基础与应用)》， 电子科大出版社，2000 林闯:《计算机网络和计算机系统的性能评价》, 清华大学出版社，2001 田乃硕:《休假随机服务系统》，北京大学出版社,2001 孙荣恒,李建平：《排队论基础》，科学出版社，2002

参考文献- 计算机网络中的应用 D. Bertsekas and R. Gallager, “Data Networks”, Prentice Hall, 1992 （中文翻译：《数据网络》，人民邮电出版社，2004） McDysan, “QoS and Traffic Management in IP and ATM networks”, McHill,1999. M. Schwartz: “Telecommunication Networks：Protocols，Modeling，and Analysis”，Addison-Wiley，1987. （中译本：“电信网：协议，建模与分析”,人民邮电出版社, 1991） M. Schwartz, “Mobile Wireless Communications”, Cambridge Univ. Press,2005 P. G. Harrison, N. M. Patel: "Performance Modeling of Communication Networks and Computer Architectures", Addison-Wesley, 1992. Minoli, "Broadband Network Analysis and Design", Arche-House, 1993. Thomas G. Robertazzi, “Computer networks and systems : queueing theory and performance evaluation”. New York : Springer-Verlag, 1990. John N. Daigle, “Queueing theory for telecommunications”, Addison-Wesley Pub. Co., 1992.

主要参考科技期刊与国际会议 “Queueing Systems: Theory and Applications (QUESTA)”, Baltzer Publisher (Netherland) “Performance Evaluations”, North-Holland “Stochastic Models”, Marcel Dekker “J. of Operation Research Society of America (ORSA)” “J. of Operation Research Society of Japan (ORSJ)” “The Bell System Technical Journal” “IEEE Trans. Commun.” “IEEE J. Selected Area on Commun. (JSAC)” “IEEE/ACM Trans. Networking” “International Teletraffic Congress (ITC)” and ITC Seminars “International Federation of Operation Research Societies (IFORS) World Congress” “Asian Federation of Operation Research Societies (AFORS)” TIMS (The Institute of Management Science) IEEE Infocom, Globecom, ICC, etc

学术期刊和会议文献 [1] 电子学报 [2] 通信学报 [3] IEEE Trans. on Communications [4] IEEE Trans. on Networks [5] Computer Communications [6] ICC [7] INFOCOM [8] GLBCOM

第一章 计算机通信网概述 1.1 计算机网络概述 1.1.1 计算机网络的发展与分类 1.1.2 计算机网络的业务特性与性能需求 第一章 计算机通信网概述 主要内容: 计算机通信网的基本工作原理；计算机通信网理论分析的重要性；计算机通信网理论的范畴及其发展史 1.1 计算机网络概述 1.1.1 计算机网络的发展与分类 1.1.2 计算机网络的业务特性与性能需求 1.2 计算机网络理论概述 1.2.1 通信话务理论（通信流理论） 1.2.2 排队论 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第二章 随机过程与随机服务过程概论 主要内容（2、3、4章）: 通信业务的分类及其业务特性; 第二章 随机过程与随机服务过程概论 主要内容（2、3、4章）: 通信业务的分类及其业务特性; 通信业务源的概率模型化（纯随机业务/平滑业务/突发业务/相关业务的概率描述； 负指数分布/爱尔兰分布/超指数分布/几何分布/泊松分布的特性； 泊松过程/间歇泊松过程/交互泊松过程/ON-OFF模型/马尔可夫调制泊松过程的特性； 更新过程的基本概念； 方差系数/分散指数/相关系数的概念； 自相关业务模型； 通信网络的排队模型化（排队模型的基本组成；马尔可夫与非马尔可夫排队模型；生灭过程；电路交换/分组交换/ATM网络的建模） The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第二章 随机过程与随机服务过程概论 2.1 概率空间 2.2 条件概率 2.3 随机变量和随机过程 第二章 随机过程与随机服务过程概论 2.1 概率空间 2.2 条件概率 2.3 随机变量和随机过程 2.4 随机变量的分布函数和随机过程的概率分布 2.5 数学期望值与母函数 2.6 随机服务过程的基本概念 2.7 随机服务系统的组成部分 2.8 随机服务过程的几个主要数量指标 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第三章 重要的概率分布和重要的随机过程 3.1 负指数分布 3.2 k阶爱尔朗(Erlang)分布Ek 第三章 重要的概率分布和重要的随机过程 3.1 负指数分布 3.2 k阶爱尔朗(Erlang)分布Ek 3.3 二项式分布、几何分布和负二项式分布 3.4 泊松分布(Possion)、泊松过程 3.5 贝努利过程 3.6 生灭过程 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第四章 马尔可夫链与马尔可夫过程 4.1 马尔可夫链的定义与转移概率 4.2 马尔可夫链的状态分类 4.3 常返状态及其极限概率 第四章 马尔可夫链与马尔可夫过程 4.1 马尔可夫链的定义与转移概率 4.2 马尔可夫链的状态分类 4.3 常返状态及其极限概率 4.4 周期状态及其极限概率 4.5 马尔可夫过程定义 4.6 纯不连续马尔可夫过程 4.7 齐次可数的纯不连续马尔可夫过程 4.8 转移概率函数的极限特性和状态分类 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第五章 排队论 5.1 排队论的领域与特征 5.2 排队模型 5.3 马尔可夫排队模型 5.4 非马尔可夫排队模型 第五章 排队论 5.1 排队论的领域与特征 5.2 排队模型 5.3 马尔可夫排队模型 5.4 非马尔可夫排队模型 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第五章 排队论 主要内容: 排队模型与Kendall记号；排队模型的参数及性能指标；Little定理；PASTA定理；到达时刻与退去时刻状态概率等效性定理；#上述三个定理的证明及其推广. 马尔可夫型排队模型的性能分析: 全局平衡与局域平衡的概念；M/M/1, M/M/s, M/M/s(k)排队模型的队长分布及等待时间；Erlang-B公式的物理意义及其在电路交换网中的应用；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模型的辅助函数分析法；*M/G/1优先权排队模型的解析；#M/G/1模型的忙期(busy period); #GI/G/1排队模型的Lindley积分分析法； The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第六章 计算机网络性能分析 计算机网络资源分配、路由选择及流量控制理论 6.1 协议与设备 6.2 时分复用（TDM）网络性能分析 第六章 计算机网络性能分析 计算机网络资源分配、路由选择及流量控制理论 6.1 协议与设备 6.2 时分复用（TDM）网络性能分析 6.3 具有优先级的环形网络性能分析 6.4 轮询系统性能分析 6.5 拥挤和流控制分析 6.6 基于路由流分配性能分析 6.7 QoS性能分析 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

第一章 计算机网络概述 1.1 通信网的基本构成及其分类 􀂙 信息内容: 电话网、计算机网、电视网/CATV 第一章 计算机网络概述 1.1 通信网的基本构成及其分类 􀂙 信息内容: 电话网、计算机网、电视网/CATV 􀂙 复用方式: 频分、时分、码分、波分 􀂙 交换方式: 电路、报文交换、分组(帧中继、IP、ATM) 􀂙 传输方式：模拟/数字、有线/无线、光纤/电缆 The seminar is organized in five Chapters. Chapter 1 presents an overview of ATM Traffic Management (TM) by showing the need for ATM TM. Chapter 2 is an introduction to the ATM TM basics and strategy. In Chapter 3, we focus on the nodal level control mechanisms such as cell/frame switching, Intelligent buffer management, traffic shaping, and usage parameter control (UPC). In Chapter 4, we focus on the network level controls such as routing, flow control, and connection admission control. Chapter 5 is a collection of new and merging ATM TM features such as ABR, IMA, and Frame Relay to ATM interworking.

电路交换网络 Connection oriented: Information transfer as continuous stream Connection set up end-to-end before information transfer Resources reserved for the whole duration of connection Information transfer as continuous stream Before information transfer Delay (to set up the connection) During information transfer No overhead No extra delays

无连接的分组交换网络 Connectionless: Information transfer as discrete packets No connection set up No resources reservation Information transfer as discrete packets 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)

面向连接的分组交换网络 Connection oriented: virtual connections set up end-to-end before information 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 delays(less, due to the shorter address) Queueing delays( since packets compete for joint resources)

面向连接的信元交换 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 (small) 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 not reserved beforehand)

固定复用与统计复用 固定复用(Deterministic Multiplexing, e.g., TDM/FDM) 统计复用(Statistical Multiplexing, e.g., ATM)

Applications Demands

Optical Circuit Switching For each request, Set-up a static circuit (lightpath) Transfer data Release connection Pros: Suitable for smooth, longer-term, high-bandwidth applications Cons: Long circuit set-up latency Inefficient for short-term bursty applications

Optical Circuit Switching (cont.)

Optical Packet Switching A photonic packet contains a header and the payload Packet header is processed all-optically at each node and switched to the next hop Pros: Statistical multiplexing of data Suitable for bursty traffic Cons: buffer

Optical Burst Switching Multiple IP packets assembled into a burst An out-of-band control header transmitted ahead of each data burst Pros: Statistical multiplexing of data Suitable for bursty traffic Low data-transfer latency Electronic control plane (practically feasible) Optical data plane (high-speed)

Motivation for OBS

Layered Network Model

OBS Network Architecture

OBS Node Architecture

Question

JET协议比别的协议有更高的通过率,更低的丢包率,信道利用率较高 JET 协议的路由具有自己的特点, 在发送控制包时就应该知道要经过多少个节点, 这就需要源地址选路, 而不能像一般IP 分组交换进行逐步的路由选路。

1.2 通信网业务特性与性能指标 用户对通信网的基本要求 不同的通信网有着不同的性能要求 网络性能分析、优化设计与流量控制至关重要 连通性：任意、快速 可靠性：迂回路由、自愈恢复、信息安全 灵活性：突发业务、新业务 经济性：价格性能比、最优化 不同的通信网有着不同的性能要求 电话交换网(delay-sensitive) 低延迟、高接通性（迂回中继）；允许一定的信息丢失 数据交换网(loss-sensitive) 低丢失率、高通过率（缓存）；允许一定程度的延迟 多媒体网络(delay-and-loss sensitive) 低丢失率、低延迟、低抖动、高通过率；业务差分 网络性能分析、优化设计与流量控制至关重要

性能分析、优化设计与流量控制 Performance evaluation Traffic control System design Given the system and the incoming traffic, what’s the QoS experienced by the user? Traffic control Given the system and QoS requirements, what’s the maximum traffic load? System design Given the incoming traffic and the required QoS, how should the system be dimensioned?

性能分析、优化设计与流量控制

计算机网络主要性能指标 主要性能指标 阻塞率：用户连接建立请求被拒绝的概率(面向连接网络) 丢失率：信息传输过程中被丢失的概率(链路误码、网络拥塞） 通过率：信息被成功传送的概率（吞吐量） 连接建立延迟：建立通信连接所需的时间(面向连接网络) 信息传送延迟：信息在网络中的滞留时间 节点（交换、路由）处理延迟 排队等待延迟 传播延迟等

影响计算机网络性能的主要因素 网络的拓扑结构 网络的路由机制与流量控制（信令） 网络可提供的资源（带宽、缓存、功率等） 业务量 好的拓扑结构应该有利于负载均衡 网络的路由机制与流量控制（信令） 网络越来越复杂，网管信令开销的影响不可忽视 网络可提供的资源（带宽、缓存、功率等） 网络资源（带宽/缓冲器）是有限的、共享的 业务量 网络的设计（平均）容量永远大于（平均）需求（如果业务需求是确定性的，网络不会发生拥塞） 业务模式（随机性） 业务需求的随机性、特别是突发性会造成网络资源的浪费

业务的随机性是网络性能恶化的主要原因 考虑一个简单的随机服务系统。顾客以随机的方式到达，平均间隔为4分钟。服务者以随机的方式为顾客提供服务，平均时间为3分钟。 到达间隔和服务时间均为定长分布时，L=? 到达间隔和服务时间均为负指数分布时，L=? 到达间隔为负指数分布、但服务时间为定长分布时，L=?

普通电话呼叫的随机特性 The mean number 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,1973[36]).

拨号上网请求的随机特性 Number of calls per 15 minutes to a modem pool of Tele Danmark Internet.

电话持续时间的随机特性 Mean holding time for trunk lines as a function of time of days. The measurements exclude local calls

拨号上网用户占线时间的随机特性 Mean 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.

拨号上网用户的特性高度依赖于收费政策 Traffic Intensity (erl) = sessionLength x arrivals/second

Two-step Tariff and its Effect Time of Day

描述业务的随机性需要引入概率模型 通信网性能分析需要概率模型 通信网性能分析需要随机过程分析 当然，概率模型只是对实际业务的理想化/近似 业务需求的产生是随机的、突发的； 业务所需要的服务时间也是随机的; 有时甚至可得到的网络资源也是随机的 通信网性能分析需要随机过程分析 业务的随机性可能会随时间变化 当然，概率模型只是对实际业务的理想化/近似 “Errors using inadequate data are much less than those using no data at all” But caution is needed when conclusions are drawn

我们真的需要QoS吗？ No: Over-Provisioning（扩容）可以解决所有问题 业务的特性难以预测，而且越来越复杂 光传输和光交换技术的发展带来无限的传输带宽，不会再有拥塞发生 业务的特性难以预测，而且越来越复杂 概率模型要么不准确（过于近似）不实用、所建的数学模型要么太复杂无法求解 实际上，QoS更多的是用户的感觉、难以量化 基于效用和博弈论的资源管理模型 计算机仿真太耗时、且难以得出一般性结论

我们真的需要QoS吗？ Yes: 骨干网的传输成本会指数下降，但交换、管理成本不会指数下降，而且还有上升的趋势 End-to-end的带宽不会无穷大，总会有瓶颈节点存在 历史已经告诉我们：业务对带宽的需求以及不断出现的新业务永远会对网络带宽造成压力（带宽需求的贪婪性） 即使是在很低的负载下，业务的突发性和自相似特性还会导致网络拥塞 况且，传输成本永远不会无穷小！

我们需要什么样的QoS? “最优”的概念需要更新 网络的优化目标应该是可以动态调节的 确定性QoS和统计性QoS（Soft Qos) 业务源特性不再容易精确预测 业务源特性在不断动态变化 网络拓扑结构也有可能是动态的 网络优化设计应与网络动态控制紧密结合 网络的优化目标应该是可以动态调节的 通过Traffic Management实现网络优化 确定性QoS和统计性QoS（Soft Qos) PLR<10-5 vs P{PLR>10-5} < 10-3 E{PTD}<3ms vs P{PTD>3ms} < 10-3

计算机网络性能分析的重要性（例1） 􀂙 电话交换网的线路设计（大规模效应） 问：1）如果N’=2N, S’ {<, =, >} 2S ? 2）如果N’=N/2, S’ {<, =, >} S/2 ?

计算机网络性能分析的重要性（例2） 综合网络/集中排队 分散网络/集中排队 分散网络/独立排队

计算机网络性能分析的重要性（例3）

计算机网络性能分析的重要性（例4）

计算机网络性能分析的重要性（例5）

计算机网络性能分析的重要性（例6）

1.3 计算机网络性能分析的三种主要手段 现场试验(Trial Implementation) 最贴近实际网络，可以直接推广应用 多用于商业化运作之前的实际检验 但开销巨大，试验周期长 计算机仿真(Computer Simulation) 简便易行，比较接近实际网络 多用于复杂网络性能的评估和验证 但难以得到一般性结论，且稀疏事件难以仿真 理论分析(Performance Evaluation) 简便易行，且容易抓住问题的实质 多用于简单网络的性能预测和评估规划 但需要引入近似，且难以应用到大规模复杂网络 但无论是现场试验还是计算机仿真，都需要理论分析作为指导

计算机网络理论的范畴 网络拓扑学 网络控制理论 网络优化理论: 网络性能分析理论: 网络的连通性，最短树，最大流等静态理论 一般不考虑网络实际流量的随机特性 基础理论为图论 网络控制理论 控制论/正反馈/负反馈/动态控制/动态路由 网络优化理论: 网络资源分配与流量控制等问题 基础理论为线性/非线性规划法等最优化理论 网络性能分析理论: 主要讨论网络的阻塞率、延迟时间、通过率等用户的服务质量(QoS) 主要考虑业务的随机性对网络性能的影响 基础理论为应用概率论、运筹学及排队论

计算机网络的排队模型化

计算机网络性能分析理论 电信流量理论(Teletraffic Theory) 排队论(Queueing Theory) 又称电信话务量理论，主要研究电信网的优化设计 起源于1909年和1917年A. K. Erlang的论文，首次用概率论的手法解决了电信交换机容量的设计问题，且一致沿用至今 A.K. Erlang: “Probability and Telephones”, Nyt. 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 排队论(Queueing Theory) 主要研究有顾客等待（队列）的随机服务系统，是运筹学的一个重要分支 广泛应用于计算机网络、运输、生产、库存等各种资源共享随机服务系统

排队论的发展史 初期(10‘s-40‘s) 中期(40‘s-60’s) 近期(60‘s-今) 主要研究应用于电话网和远程通信系统等无队列排队系统 中期(40‘s-60’s) 推广应用到军事、运输、生产、社会服务等领域，主要研究有队列的排队系统和排队网络 近期(60‘s-今) 主要研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带有各种网络控制的排队系统的研究

Milestones of Queueing Theory 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 Norden 1951: Kendall published “Some Problems in the Theory of Queues” and in 1953 proposed to use Kendall’s 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