网络演算 互联网确定性排队系统理论

华为数据通信. 基础理论系列

丛书主编·徐文伟

网络演算：互联网确定性排队系统理论

（瑞士）让-伊夫·勒布代克（Jean-Yves Le Boudec）　（比）帕特里克·蒂兰（Patrick Thiran）　著

李峭　赵露茜　何锋　赵琳　周璇　译

张嘉怡　王心远　王童童　审校

人民邮电出版社

北京

图书在版编目（CIP）数据

网络演算：互联网确定性排队系统理论/ （瑞士）让-伊夫·勒布代克（Jean-Yves Le Boudec），（比）帕特里克·蒂兰（Patrick Thiran）著，李峭等译.--北京：人民邮电出版社，2022.3

（华为数据通信. 基础理论系列）

ISBN　978-7-115-58463-2

Ⅰ.①网… Ⅱ.①让… ②帕… ③李… Ⅲ.①排队论-研究Ⅳ.①O226

中国版本图书馆CIP数据核字（2022）第017827号

定价：99.00元

读者服务热线：（010）81055552　印装质量热线：（010）81055316

反盗版热线：（010）81055315

广告经营许可证：京东市监广登字20170147号

内容提要

本书主要阐述网络演算的理论，介绍对互联网确定性排队系统性能的界限分析方法。第一部分结合应用实例，给出网络演算综述及概念解释，介绍时延、积压、输出流量行为等界限分析方法。第二部分详细介绍网络演算的形式化数学理论研究，基于最小加代数的分析体系，对更通用、更复杂的系统进行建模和分析。第三部分介绍结合互联网特性的进阶研究，包括最优多媒体平滑、聚合调度、自适应保证与数据包尺度速率保证、时变整形器、有损系统等场景，给出积压等界限分析方法及其结果。

本书开创性地确立了互联网确定性排队系统的理论基础，可供通信、计算机网络专业的研究生学习，亦可供从事互联网、实时系统等设计、分析、验证的工程师参考。

华为数据通信·基础理论系列编委会

主任

胡克文 华为数据通信产品线总裁

副主任

刘少伟 华为数据通信产品线研发部总裁

编委

钱骁 华为数据通信研究部部长

付洁 华为2012实验室网络技术实验室主任

王建兵 华为数据通信架构与设计部部长

金闽伟 华为数据通信IP研究部部长

江兴烽 华为数据通信WLAN&以太网技术研究部部长

解明震 华为企业数据通信解决方案使能部部长

孟文君 华为数据通信数字化信息和内容体验部部长

朱正宏 华为2012实验室语言服务一部部长

译者简介

李峭，北京航空航天大学工学博士，北京航空航天大学电子信息工程学院副教授，曾在沈阳飞机设计研究所担任客座航空电子工程师，主要研究领域涉及实时系统、数字通信、数据通信和计算机网络，承担过多项航空电子综合化网络工程课题。从2002年开始学习并熟悉网络演算理论，并将其应用于航空电子网络（如AFDX网络和TTE网络）技术的推广工作中。目前主要研究时间敏感网络（TSN）和航空电子无线机舱内互连（WAIC）网络，致力于利用确定性网络演算和随机网络演算进行网络性能评价。

赵露茜，北京航空航天大学工学博士，2017年前往丹麦技术大学从事博士后研究工作，获玛丽·居里学者称号，2019年年底开始在慕尼黑工业大学从事科研工作。主要研究方向为实时通信网络形式化方法（确定性网络演算）下实时性能的分析以及网络配置研究，主要研究对象为针对实时和安全关键性应用的以太网新一代子标准时间敏感网络（TSN）。在相关领域发表10余篇论文，谷歌学术h因子为10。

何锋，北京航空航天大学工学博士，北京航空航天大学电子信息工程学院副教授，2014—2015年作为公派访问学者赴法国INP-ENSEEIHT（法国工程师学校，图卢兹大学成员）从事合作研究。主要研究领域涉及实时通信系统、嵌入式网络、实时性能评估（主要聚焦于航空电子和车载电子领域），以及航空电子综合技术。已出版2部专著，发表76篇论文。

赵琳，北京航空航天大学工学博士，中国航天科工集团有限公司工程师。主要研究方向为安全关键性网络和实时网络性能评估，近3年在通信与信息系统专业领域发表7篇学术论文，包含2篇SCI检索期刊论文和1篇最佳会议论文。

周璇，北京航空航天大学工学学士，现攻读北京航空航天大学信息与通信工程博士学位。主要研究领域为实时通信系统调度设计与性能评估，已在实时计算机网络领域发表5篇学术论文，包含1篇最佳会议论文。

审校者简介

张嘉怡：清华大学博士。在华为公司从事网络演算的应用研究、网络建模和性能评估工作。

王心远：河北工业大学硕士。在华为公司从事高速以太接口、网络演算的研究工作。

王童童：瑞典林雪平大学硕士。在华为公司从事网络SLA保障关键技术研究和标准化工作，担任IEEE 802.1DF编委。

总序

“2020年12月31日，华为CloudEngine数据中心交换机全球销售额突破10亿美元。”

我望向办公室的窗外，一切正沐浴在旭日玫瑰色的红光里。收到这样一则喜讯，倏忽之间我的记忆被拉回到2011年。

那一年，随着数字经济的快速发展，数据中心已经成为人工智能、大数据、云计算和互联网等领域的重要基础设施，数据中心网络不仅成为流量高地，也是技术创新的热点。在带宽、容量、架构、可扩展性、虚拟化等方面，用户对数据中心网络提出了极高的要求。而核心交换机是数据中心网络的中枢，决定了数据中心网络的规模、性能和可扩展性。我们洞察到云计算将成为未来的趋势，云数据中心核心交换机必须具备超大容量、极低时延、可平滑扩容和演进的能力，这些极致的性能指标，远远超出了当时的工程和技术极限，业界也没有先例可循。

作为企业BG的创始CEO，面对市场的压力和技术的挑战，如何平衡总体技术方案的稳定和系统架构的创新，如何保持技术领先又规避不确定性带来的风险，我面临一个极其艰难的抉择：守成还是创新？如果基于成熟产品进行开发，或许可以赢得眼前的几个项目，但我们追求的目标是打造世界顶尖水平的数据中心交换机，做就一定要做到业界最佳，铸就数据中心带宽的“珠峰”。至此，我的内心如拨云见日，豁然开朗。

我们勇于创新，敢于领先，通过系统架构等一系列创新，开始打造业界最领先的旗舰产品。以终为始，秉承着打造全球领先的旗舰产品的决心，我们快速组建研发团队，汇集技术骨干力量进行攻关，数据中心交换机研发项目就此启动。

CloudEngine 12800数据中心交换机的研发过程是极其艰难的。我们突破了芯片架构的限制和背板侧高速串行总线（SerDes）的速率瓶颈，打造了超大容量、超高密度的整机平台；通过风洞试验和仿真等，解决了高密交换机的散热难题；通过热电、热力解耦，突破了复杂的工程瓶颈。

我们首创数据中心交换机正交架构、Cable I/O、先进风道散热等技术，自研超薄碳基导热材料，系统容量、端口密度、单位功耗等多项技术指标均达到国际领先水平，“正交架构+前后风道”成为业界构筑大容量系统架构的主流。我们首创的“超融合以太”技术打破了国外FC（Fiber Channel，光纤通道）存储网络、超算互联IB（InfiniBand）网络的技术封锁；引领业界的AI ECN（Electronic Communication Network，电子通信网络）技术实现了RoCE（RDMA over Converged Ethernet，基于聚合以太网的远程直接存储器访问）网络的实时高性能；PFC（Power Factor Correction，功率因数校正）死锁预防技术更是解决了RoCE大规模组网的可靠性问题。此外，华为在高速连接器、SerDes、高速AD/DA（Analog to Digital/Digital to Analog，模数/数模）转换、大容量转发芯片、400GE光电芯片等多项技术上，全面填补了技术空白，攻克了众多世界级难题。

2012年5月6日，CloudEngine 12800数据中心交换机在北美拉斯维加斯举办的Interop展览会闪亮登场。CloudEngine 12800数据中心交换机闪耀着深海般的蓝色光芒，静谧而又神秘。单框交换容量高达48 Tbit/s，是当时业界最高水平的3倍；单线卡支持8个100GE端口，是当时业界最高水平的4倍。业界同行被这款交换机超高的性能数据所震撼，业界工程师纷纷到华为展台前一探究竟。我第一次感受到设备的LED指示灯闪烁着的优雅节拍，设备运行的声音也变得如清谷幽泉般悦耳。随后在2013年日本东京举办的Interop展览会上，CloudEngine 12800数据中心交换机获得了DCN（Data Center Network，数据中心网络）领域唯一的金奖。

我们并未因为CloudEngine 12800数据中心交换机的成功而停止前进的步伐，我们的数据通信团队继续攻坚克难，不断进步，推出了新一代数据中心交换机——CloudEngine 16800。

华为数据中心交换机获奖无数，设备部署在90多个国家和地区，服务于3800多家客户，2020年发货端口数居全球第一，在金融、能源等领域的大型企业以及科研机构中得到大规模应用，取得了巨大的经济效益和社会效益。

数据中心交换机的成功，仅仅是华为在数据通信领域众多成就的一个缩影。CloudEngine 12800数据中心交换机发布一年多之后，2013年8月8日，华为在北京发布了全球首个以业务和用户体验为中心的敏捷网络架构，以及全球首款S12700敏捷交换机。我们第一次将SDN（Software Defined Network，软件定义网络）理念引入园区网络，提出了业务随行、全网安全协防、IP（Internet Protocol，互联网协议）质量感知以及有线和无线网络深度融合四大创新方案。基于可编程ENP（Ethernet Network Processor，以太网络处理器）灵活的报文处理和流量控制能力，S12700 敏捷交换机可以满足企业的定制化业务诉求，助力客户构建弹性可扩展的网络。在面向多媒体及移动化、社交化的时代，传统以技术设备为中心的网络必将改变。

多年来，华为以必胜的信念全身心地投入数据通信技术的研究，业界首款2T路由器平台NetEngine 40E-X8A/X16A、业界首款T级防火墙USG9500、业界首款商用Wi-Fi 6产品AP7060DN……随着这些产品的陆续发布，华为IP产品在勇于创新和追求卓越的道路上昂首前行，持续引领产业发展。

这些成绩的背后，是华为对以客户为中心的核心价值观的深刻践行，是华为在研发创新上的持续投入和厚积薄发，是数据通信产品线几代工程师孜孜不倦的追求，更是整个IP产业迅猛发展的时代缩影。我们清醒地意识到，5G、云计算、人工智能和工业互联网等新基建方兴未艾，这些都对IP网络提出了更高的要求，“尽力而为”的IP网络正面临着“确定性”SLA（Service Level Agreement，服务等级协定）的挑战。这是一次重大的变革，更是一次宝贵的机遇。

我们认为，IP产业的发展需要上下游各个环节的通力合作，开放的生态是IP产业成长的基石。为了让更多人加入到推动IP产业前进的历史进程中来，华为数据通信产品线推出了一系列图书，分享华为在IP产业长期积累的技术、知识、实践经验，以及对未来的思考。我们衷心希望这一系列图书对网络工程师、技术爱好者和企业用户掌握数据通信技术有所帮助。欢迎读者朋友们提出宝贵的意见和建议，与我们一起不断丰富、完善这些图书。

华为公司的愿景与使命是“把数字世界带入每个人、每个家庭、每个组织，构建万物互联的智能世界”。IP网络正是“万物互联”的基础。我们将继续凝聚全人类的智慧和创新能力，以开放包容、协同创新的心态，与各大高校和科研机构紧密合作。希望能有更多的人加入IP产业创新发展活动，让我们种下一份希望、发出一缕光芒、释放一份能量，携手走进万物互联的智能世界。

徐文伟

华为董事、战略研究院院长

2021年12月

“华为数据通信·基础理论系列”序言

20世纪30年代，英国学者李约瑟（Joseph Needham）曾提出这样的疑问：为什么在公元前1世纪到公元15世纪期间，中国文明在获取自然知识并将其应用于人的实际需要方面要比西方文明更有成效？然而，为什么近代科学蓬勃发展没有出现在中国？这就是著名的“李约瑟难题”，也称“李约瑟之问”。对这个“难题”的理解与回答，中外学者见仁见智。有一种观点认为，在人类探索客观世界的漫长历史中，技术发明曾经长期早于科学研究。古代中国的种种技术应用，更多地来自匠人经验知识的工具化，而不是学者科学研究的产物。

近代以来，科学研究的累累硕果带来了技术应用的爆发和社会的进步。力学、热学基础理论的进步，催生了第一次工业革命；电磁学为电力的应用提供了理论依据，开启了电气化时代；香农（Shannon）创立了信息论，为信息与通信产业奠定了理论基础。如今，重视并加强基础研究已经成为一种共识。在攀登信息通信技术高峰的30多年中，华为公司积累了大量成功的工程技术经验。在向顶峰进发的当下，华为深刻认识到自身理论研究的不足，亟待基础理论的突破来指导工程创新，以实现技术持续领先。

“华为数据通信·基础理论系列”正是基于这样的背景策划的。2019年年初，华为公司数据通信领域的专家们从法国驱车前往位于比利时鲁汶的华为欧洲研究院，车窗外下着大雨，专家们在车内热烈讨论数据通信网络的难点问题，不约而同地谈到基础理论突破的困境。由于具有“统计复用”和“网络级方案”的属性，数据通信领域涉及的理论众多，如随机过程与排队论、图论、最优化理论、信息论、控制论等，而与这些理论相关的图书中，适合国内从业者阅读的中文版很少。华为数据通信产品线研发部总裁刘少伟当即表示，我们华为可以牵头，与业界专家一起策划一套丛书，一方面挑选部分经典图书引进翻译，另一方面系统梳理我们自己的研究成果，让从业者及相关专业的高校老师和学生能更系统、更高效地学习理论知识。

在规划丛书选题时，我们考虑到随着通信技术和业务的发展，网络的性能受到了越来越多的关注。在物理层，性能的关键点是提升链路或者Wi-Fi信道的容量，这依赖于摩尔定律和香农定律；网络层主要的功能是选路，通常路径上链路的瓶颈决定了整个业务系统所能实现的最佳性能，所以网络层是用户业务体验的上界，业务性能与系统的瓶颈息息相关；传输层及以上是用户业务体验的下界，通过实时反馈精细调节业务的实际发送，网络性能易受到网络服务质量（如时延、丢包）的影响。因此，从整体网络视角来看，网络性能提升优化是对“业务要求+吞吐率+时延+丢包率”多目标函数求最优解的过程。为此，首期我们策划了《排队论基础》（第5版）（Fundamentals of Queueing Theory ,Fifth Edition）、《网络演算：互联网确定性排队系统理论》（Network Calculus:A Theory of Deterministic Queuing Systems for the Internet）和《MIMO-OFDM技术原理》（Technical Principle of MIMO-OFDM）这三本书，前两本介绍与网络服务质量保障相关的理论，后一本介绍与Wi-Fi空口性能研究相关的技术原理。

由美国乔治·华盛顿大学荣誉教授唐纳德·格罗斯（Donald Gross）和美国乔治·梅森大学教授卡尔·M.哈里斯（Carl M. Harris）撰写的《排队论基础》自1974年第1版问世以来，一直是排队论领域的权威指南，被国外多所高校列为排队论、组合优化、运筹管理相关课程的教材，其内容被7000余篇学术论文引用。这本书的作者在将排队论应用于多个现实系统方面有丰富的实践经验，并在40多年中不断丰富和优化图书内容。本次引进翻译的是由美国乔治·梅森大学教授约翰·F.肖特尔（John F. Shortle）、房地美公司架构师詹姆斯·M.汤普森（James M. Thompson）、唐纳德·格罗斯和卡尔·M.哈里斯于2018年更新的第5版。由让-伊夫·勒布代克（Jean-Yves Le Boudec）和帕特里克·蒂兰（Patrick Thiran）撰写的《网络演算：互联网确定性排队系统理论》一书于2002年首次出版，是两位作者在洛桑联邦理工学院从事网络性能分析研究、系统应用时的学术成果。这本书出版多年来，始终作为网络演算研究者的必读书目，也是网络演算学术论文的必引文献。让-伊夫·勒布代克教授的团队在2018年开始进行针对时间敏感网络的时延上界分析，其方法就脱胎于《网络演算：互联网确定性排队系统理论》这本书的代数理论框架。本次引进翻译的是作者于2020年9月更新的最新版本，书中详细的理论介绍和系统分析，对实时调度系统的性能分析和设计具有指导意义。

《MIMO-OFDM技术原理》的作者是华为WLAN LAB以及华为特拉维夫研究中心的专家多伦·埃兹里（Doron Ezri）博士和希米·希洛（Shimi Shilo）。从2007年起，多伦·埃兹里一直在特拉维夫大学教授MIMO-OFDM技术原理的研究生课程，这本书就是基于该课程讲义编写的中文版本。相比其他MIMO-OFDM图书，书中除了给出MIMO和OFDM原理的讲解外，作者团队还基于多年的工程研究和实践，精心设计了丰富的例题，并给出了详尽的解答，对实际无线通信系统的设计有较强的指导意义。读者通过对例题的研究，可进一步深入地理解MIMO-OFDM系统的工程约束和解决方案。

数据通信领域以及整个信息通信技术行业的研究最显著的特点之一是实用性强，理论要紧密结合实际场景的真实情况，通过具体问题具体分析，才能做出真正有价值的研究成果。众多学者看到了这一点，走出了象牙塔，将理论用于实践，在实践中丰富理论，并在著书时鲜明地体现了这一特点。本丛书书目的选择也特别注意了这一点。这里我们推荐一些优秀的图书，比如，排队论方面，可以参考美国卡内基·梅隆大学教授莫尔·哈肖尔-巴尔特（Mor Harchol-Balter）的Performance Modeling and Design of Computer Systems :Queueing Theory in Action（中文版《计算机系统的性能建模与设计：排队论实战》已出版）；图论方面，可以参考加拿大滑铁卢大学两位教授约翰·阿德里安·邦迪（John Adrian Bondy）和乌帕鲁里·西瓦·拉马钱德拉·莫蒂（Uppaluri Siva Ramachandra Murty）合著的Graph Theory；优化方法理论方面，可以参考美国加州大学圣迭戈分校教授菲利普·E.吉尔（Philip E. Gill）、斯坦福大学教授沃尔特·默里（Walter Murray）和纽约大学教授玛格丽特·H.怀特（Margaret H. Wright）合著的Practical Optimization；网络控制优化方面，推荐波兰华沙理工大学教授米卡尔·皮奥罗（Michal Pioro）和美国密苏里大学堪萨斯分校的德潘卡·梅迪（Deepankar Medhi）合著的Routing,Flow,and Capacity Design in Communication and Computer Networks；数据通信网络设备的算法设计原则和实践方面，则推荐美国加州大学圣迭戈分校教授乔治·瓦尔盖斯（George Varghese）的Network Algorithmics:An Interdisciplinary Approach to Designing Fast Networked Devices；等等。

基础理论研究是一个长期的、难以快速变现的过程，几乎没有哪个基础科学理论的产生是由于我们事先知道了它的重大意义与作用从而努力研究形成的。但是，如果没有基础理论的突破，眼前所有的繁华都将是镜花水月、空中楼阁。在当前的国际形势下，不确定性明显增加，科技对抗持续加剧，为了不受制于人，更为了有助于全面提升我国的科学技术水平，开创未来30年的稳定发展局面，重视基础理论研究迫在眉睫。为此，华为公司将继续加大投入，将每年20%∼30%的研发费用用于基础理论研究，以提升通信产业的原始创新能力，真正实现“向下扎到根”。华为公司也愿意与学术界、产业界一起，为实现技术创新和产业创新打好基础。

首期三本书的推出只是“华为数据通信·基础理论系列”的开始，我们也欢迎各位读者不吝赐教，提出宝贵的改进建议，让我们不断完善这套丛书。如有任何建议，请您发送邮件至networkinfo@huawei.com，在此表示衷心的感谢。

推荐序一

互联网经过50多年的发展，在消费领域取得了巨大的成功。时至今日，互联网开始被应用于实体经济，互联网的发展也正式进入“下半场”。当前的应用场景在要求网络具备海量连接能力的同时，也要求网络具备确定性的服务质量，“尽力而为”的传统互联网协议（Internet Protocol,IP）网络架构面临着巨大的挑战。人们对未来网络的愿景是智能、安全、柔性、可定制，未来网络要适应与实体经济的深度融合。未来，每个行业、企业、用户，甚至每个应用都将拥有定制化的网络，运营商的商业模式将从传统的卖带宽转变为提供定制化的网络服务，全网利用率将从目前的约50%提升至90%以上，用户使用成本将进一步降低。

当前基于IP、以太网技术的互联网面对虚拟现实、增强现实、工业互联网、智能电网、无人驾驶及远程医疗等新应用的出现，开始显露出“力不从心”的“疲态”。尤其是随着5G网络的部署，用户对网络带宽以及网络所承载业务的时延的要求愈加严苛：网络需要提供可承诺的端到端小于10 ms的有界时延、微秒级的抖动、零丢包和高可靠性等。而传统的IP/以太网“尽力而为”的工作方式需要转变为提供“准时、准确”的可承诺服务等级协定（Service Level Agreement,SLA）能力的工作方式。在互联网中进行创新研究、探索基础理论，进一步给出具体网络的部署及配置方法，最终使能IP/以太网，提供确定性、可承诺SLA能力及相应的解决方案成为当前全球关注的热点。

目前，IEEE 802.1工作组致力于时间敏感网络的标准化。因特网工程任务组（Internet Engineering Task Force,IETF）的DetNet工作组专注于网络层及更高层次的广域确定性网络技术。这些标准化的工作进一步推动业界在确定性及可承诺SLA领域进行系统的技术研究及探索，网络演算也是备受关注的一个领域。

网络演算（network calculus），或译为网络微积分，是一种基于最小加代数（min-plus algebra）的数学理论，一般包括确定性网络演算（Deterministic Network Calculus,DNC）和随机网络演算（Stochastic Network Calculus,SNC）。1991年，美国加利福尼亚大学圣迭戈分校的勒内·莱昂纳多·克鲁兹（Rene Leonardo Cruz）教授首先提出确定性网络演算的基本概念和方法，1996年，瑞士洛桑联邦理工学院的让–伊夫·勒布代克（Jean-Yves Le Boudec）教授正式引入最小加代数理论，促使确定性网络演算发展为完整的理论体系。随后确定性网络演算成功应用于分析互联网服务质量（Quality of Service,QoS）体系、异步传输方式（Asynchronous Transfer Mode,ATM）、机载航空电子全双工交换式以太网（Avionics Full-Duplex Switched Ethernet,AFDX）等网络的时延、SLA和实时性保证。

让–伊夫·勒布代克与帕特里克·蒂兰（Patrick Thiran）于2001年联合编著了Network Calculus:A Theory of Deterministic Queuing Systems of the Internet，系统地论述了确定性网络演算的基本概念、最小加代数基础及理论，并结合互联网的流量及调度机制等进行具体分析。我很高兴看到华为技术有限公司与北京航空航天大学合作完成这部专著中文版的翻译工作，希望这部译著能够推动对互联网提供基于确定性承载、可承诺时延及带宽等的业务保障方面的创新研究及探索，最终让网络可以更好地服务用户，推动经济发展。

最后祝愿网络演算及相关研究不断砥砺前行，取得新的进展，实现关键技术的创新与突破。

刘韵洁

中国工程院院士

推荐序二

很荣幸受邀为让–伊夫·勒布代克和帕特里克·蒂兰教授的Network Calcu-lus:A Theory of Deterministic Queuing Systems of the Internet一书的中文译本撰写序言，这本书是我进入网络演算领域最先阅读的参考文献之一。据我了解，大多数网络演算的研究者都由此起步。即便到今天，在经过对网络演算15年的深入研究之后，我依旧认为本书以及其他几篇开拓性论文仍然是研究者进行研究的主要参考资料和灵感来源。

网络演算理论于约30年前被提出，这一理论的目的是对存在非概率分布流量的网络进行性能分析。网络演算的基本思想是通过描述流量的最大突发度，控制和量化这些突发数据，使得这些突发数据可以在系统中无损传输，以便根据最大突发度计算网络中端到端延迟的确定性上界。虽然对网络未知行为的模拟通常采用概率分布的假设，然而在网络演算中，研究者替代性地采用了具有确定性约束的非精准描述的方法，而不是通过统计的方法计算最差情况下的时延上界，这一方法将勒内·莱昂纳多·克鲁兹教授早期的研究工作形式化为最小加代数，并最终发展为网络演算。

网络演算最初应用于网络中的某些QoS应用。例如，为每条流预留资源的互联网综合服务（IntServ）、带宽预留协议、区分服务（DiffServ）等。2000年后，关键系统（例如飞机和航天器中的嵌入式系统）的发展为这一理论提供了新的推动力，并开拓出了实时演算（real-time calculus）这一新的研究方向。网络演算具有高效的准周期性建模能力，模块化使它成为计算大型网络中最差情况下性能的良好工具。网络演算甚至被用于部分A380飞机的适航认证。此后网络演算也被应用于片上网络、传感器网络的分析。

这本书的原著出版于近20年前，无论是对网络演算应用感兴趣的从业者，还是对网络演算基础理论感兴趣的数学家，都能从本书中找到适合自己的内容。

本书的第一部分给出网络演算的综述，并结合应用实例介绍主要概念。这部分基于形式化的理论进行描述，并给出了每个概念的解释。初学者可以判断这个理论是否能够用于解决自己的问题，从而在本书的其余部分找到更多解答。

第二部分是形式化的数学理论。事实上，网络演算非常依赖最小加代数。如果以电子电路领域的情况进行类比，也可以将它称为最小加代数中的滤波理论，即经过低通滤波器后的输出信号是输入信号和该滤波器冲激响应的卷积。在网络演算中，服务器的离开过程是到达过程和服务过程的最小加卷积。最小加代数的两个算子在这些系统中具有直观的物理映射：加性模型用来描述基于时间或经过网元数据在时间上的累积量，以及某些事件之间求最大或最小的同步操作。例如在一个队列系统中，同步指的是一个报文完成其服务，随之开始下一个报文的服务的过程。这一部分也涉及最大加代数理论。

第三部分提出了进阶的研究课题，很好地说明了网络演算的潜力，并给出了网络在各种策略和变化下的分析方法。同时还介绍了处理各种场景的方法，如网络的动态行为、应对丢包等。

随着5G的出现，网络可以承诺提供更可靠和更高速的通信，网络演算似乎成为适用于分析该类型网络的有力工具。网络切片的设计体现了IntServ或Diffserv的技术演进。通过设计新的调度器，可以使通信网络的调度更加精确，并适应网络中不同类型的流。近期，包括TSN、DetNet在内的标准要求网络支持确定性分析来保证最差情况下的端到端延迟上界，而这正是网络演算所能提供的能力。网络演算的另一个典型应用场景是uRLLC场景，该场景要求亚毫秒级的传输时延，可靠性达到99.9999%等。

然而利用网络演算给出性能上界的分析并不是拿来即用的，这种方法依然存在许多问题需要解决，只有解决了这些问题，网络演算才能成为分析5G等网络的必要工具。以下列出其中3个关键问题。

（1）网络中新增的流量及其性能需求具有高度动态性。网络如何为这样的需求提供服务，这样的需求对现有网络产生什么样的影响，网络如何动态地适应其负载，这些都是需要考虑的问题。

（2）当前研究已扩展出随机网络演算的多种理论，以适当放松对丢包或时延越界概率的要求（这也正是uRLLC等场景的要求），并计算这种概率下的最高时延。然而直到笔者在2020年年底撰写该序言时，现有的分析技术也无法很好地匹配仿真结果。

（3）流循环的依赖问题还没有被完全解决。有一些技术可以处理这些依赖性，例如转向禁止（turn-prohibition）或加入整形器。前一种解决方案可能会引起流数量的增加，从而产生性能瓶颈，而后一种解决方案的实现较困难，会导致网络建设成本的增加。

希望这一中文译本能有助于网络演算在性能评估领域的推广。我的母语不是英语，因此能够深深体会到，使用母语版本的参考资料对研究者熟悉一个领域大有裨益。本书不仅提供了网络演算的基础知识，还包括了进阶的学术研究内容，可以帮助研究者更快地了解网络演算的理论。

安妮·布亚尔（Anne Bouillard）

安妮·布亚尔自2020年起入职华为技术有限公司巴黎研究所，担任研究科学家。2005年，获得里昂高等师范学校（ENS Lyon）博士学位。2006—2017年，任卡尚高等师范学校（ENS Cachan）和巴黎高等师范学校（ENS Paris）助理教授。2017—2019年，在法国诺基亚贝尔实验室担任研究工程师。主要研究方向包括网络演算的离散事件系统、性能评估和概率分析。著有Deterministic Network Calculus:From Theory to Practical Implementation一书。

引言

网络演算（network calculus）是近年发展出来的一套分析方法，这套方法对人们解决网络中流（flow）的问题提供深层次的理解。网络演算的基础是双子（dioid）代数理论，特别是最小加（min-plus）双子（也被称为最小加代数）。采用网络演算，我们能够理解综合服务（integrated service）网络、窗口流控、调度，以及缓冲或延迟定量的一些基本属性。

本书分为3个部分。第一部分（第1章和第2章）是关于网络演算的初级教程。该部分自成体系，可用作本科生或研究生入门课程的教材，但初学者需要先学习线性代数和微积分等本科生课程。第1章给出了初级教程中主要的一组分析结果——到达曲线（arrival curve）和服务曲线（service curve），以及功能强大的串联分析结果，这一章分别对这些结果进行介绍、推导并以图表进行展示。在合理的框架下，这一章给出了一些实用的定义，例如漏桶（leaky bucket）模型、通用信元速率算法，并推导了它们的基本属性。这一章还对整形器的本质属性进行了推导。第2章展示了第1章给出的基本结果如何应用于互联网。例如，说明了为什么互联网综合服务能够将任意路由器抽象为一种“速率–时延”服务曲线。这一章还给出了用于区分服务（differentiated service）的一些性能界限的理论基础。

第二部分介绍了本书各章都会用到的基础知识。第3章包含相关的初级数学知识。例如，以简明的方式阐释了最小加卷积（min-plus convolution）和次可加闭包（sub-additive closure）的概念。第3章引用了第一部分的大量内容，但仍是自成体系的。第3章的目的是提供便于读者进一步使用网络演算方法的数学知识。第4章给出了最小加代数的一些高级的结论，涉及不动点方程式等在第一部分未提到的内容。

第三部分包含一些进阶的内容，适合用于研究生课程。第5章展示了在保证服务的网络中如何应用网络演算确定优化的回放延迟（playback delay），这种方法解释了如何确定多媒体流的基本性能界限。第6章介绍了带有聚合调度（aggregate scheduling）的系统。尽管本书中介绍的网络演算的大部分内容适用于采用调度器将流分隔开的系统，但仍能够从聚合调度系统推导出一些有趣的结论。第7章进一步扩展了第1章对服务曲线的定义，对自适应保证（adaptive guarantee）进行分析，自适应保证被用于互联网区分服务。第8章分析时变整形器，时变整形器是第1章基本结论的扩展，考虑到由于自适应方法会导致系统参数发生变化，这一章给出了一种关于可重新协商预留服务的应用。最后，第9章介绍如何应对有损系统，其基础的结论是给出一种在流系统中表达损失的新方法，这种新方法能够用于在复杂系统中界定丢弃数据包损失的概率或拥塞的概率。

网络演算属于“异构代数”（exotic algebra）或“专题代数”（topical algebra）类代数方法。这是一类数学结果的集合，通常具有很高的描述复杂性（description complexity），可用于解释人造的信息系统，这些系统包含并发程序、数字电路，当然也包含通信网络。Petri网也属于这类数学结果。对于这个有前景的研究领域的一般讨论，请参考相应的概述性论文[1]和专著[2]。

我们希望能够使读者清楚地认识到：从本书所用的方法中，可以推导出一整套在很大程度上尚未被发现的、基础性的关系。例如在第1章推导出的“整形器保持到达约束”或“突发一次性准则”（pay burst only once）的结论具有相应的物理解释，并且对网络工程师而言具有实践上的重要意义。

本书所有的结果都是确定性的。更先进的网络演算专著应揭示随机系统与本书推导的确定关系之间的关联，但这些内容超出了本书的范围。感兴趣的读者可参阅参考文献[2,3]。本书的最后还提供了书中定义的术语的索引。

网络演算：计算机网络的系统论

接下来将要重点介绍网络演算与所谓的“系统论”（system theory）之间的相似关系。如果读者不熟悉系统论，可以跳过这些内容。

网络演算是在计算机网络中出现的确定性排队系统（deterministic queuing system）理论，它也被看作应用于计算机网络的系统论。网络演算与常规（已成功应用于电子电路设计中）的系统论的主要区别在于，网络演算考虑了另一种代数结构，对算子（operator）进行了如下替换：加法（+）替换成计算最小（min），乘法（×）替换成加法（+）。

在进入本书的主题之前，我们简要地展示一些最小加系统理论与常规系统理论之间的相似点与区别，其中前者应用于本书的通信网络，后者应用于电子电路。

让我们从一个非常简单的电路谈起，例如图0.1(a)所示的“电阻电容”（Resistor Capacitor,RC）电路单元。如果输入电压信号x(t)∈R，则这个简单电路的输出y(t)∈R是x与该电路冲激响应的卷积，其中冲激响应为，t≥0。

图0.1的说明：RC电路与贪婪整形器在它们各自的代数结构下是基本的线性系统。

现在考虑通信网络的节点，将其理想地抽象为一个（贪婪）整形器（greedy shaper），如图0.1(b)所示。（贪婪）整形器是一种将输入信号x(t)强行约束为某种输出信号y(t)的装置，其中输出信号y(t)服从由流量包络σ（整形曲线）给定的速率集，（贪婪）整形器会导致经过缓冲器的流的时延增大。此处所指的输入和输出“信号”是累积流，定义为在时间区间[0,t]观测到的数据流的比特数。输入和输出函数是关于参数t非递减的，参数t可以是连续或离散的。在本书中我们将看到x和y的关系如下式所示。

该关系定义了σ和x的最小加卷积。

在常规系统理论中，卷积既满足交换律又满足结合律，该属性很容易将对小规模电路的分析扩展到对大规模电路的分析。例如，图0.2(a)所示的串联线性电路的冲激响应是各个基本单元电路冲激响应的卷积。

在第1章中，我们将发现同样的属性也适用于贪婪整形器。图0.2(b)所示的第2个整形器的输出为y(t)=(σ⊗x)(t)，其中

这将帮助我们理解前文提到的“突发一次性准则”。

图0.2的说明：两个串联的线性电路的冲激响应是它们各自冲激响应的卷积，两个串联的整形器的整形曲线是它们各自整形曲线的卷积。

因此，“常规”的电路和系统理论与网络演算存在明显的相似之处。但二者也存在重要的区别。

首要的区别在于线性系统对多个输入之和的响应。这对于线性电路[例如用于从加性噪声n(t)中将信号x(t)去噪的线性低通滤波器，如图0.3(a)所示]和计算机网络[例如具有输出链路容量C的缓冲器节点的链路，其中研究者所关心的流x(t)与背景流量n(t)多路复用，如图0.3(b)所示]，都是非常普遍的情况。

图0.3的说明：线性电路对两个输入之和x(t)+n(t)的响应ytot(t)是它们各自的响应之和，见图0.3(a)；然而，聚合流量贪婪整形器对两个输入之和x(t)+n(t)的响应ytot(t)不是它们各自的响应之和，见图0.3(b)。

因为图0.3(a)所示的电子电路是线性系统，所以两个输入之和的响应是各自信号的独立响应之和。定义y(t)是线性系统对纯信号x(t)的响应，yn(t)是对噪声n(t)的响应，并且ytot(t)是对被噪声干扰的信号x(t)+n(t)的响应。则ytot(t)=y(t)+yn(t)。这种有用的属性已经应用于设计最优线性系统，以尽可能地滤除噪声。

如果在输出链路上流量尽快地接受先入先出（First Input First Output,FIFO）的服务，则图0.3(b)所示的节点等效于贪婪整形器，其整形曲线对于t≥0，有σ(t)=Ct。因此它也是线性系统，只不过这个情况下是在最小加代数的范畴里的线性系统。这意味着，对两个输入中较小者的响应是系统对每个单独输入的最小响应。然而，这也意味着对两个输入之和的响应不再是系统对每个单独输入的响应之和，因为现在x(t)+n(t)是对两个输入x(t)和n(t)进行非线性运算，所以加法起到了常规系统论中乘法的作用。这样确实很遗憾，线性属性不能被应用于聚合x(t)和n(t)的情况。因此，对于多路复用的聚合流，我们掌握的知识仍然很少。第6章将向读者介绍一些新的数学成果，以及一些看上去简单但至今仍然有待解决的问题。

在电子学和计算机网络中均会非常频繁地遇到非线性系统。然而，电路理论和网络演算对非线性系统的处理有很大差异。

以基本非线性电路为例，该电路只包含一个双极晶体管（Bipolar Junction Transistor,BJT）的晶体管放大电路，如图0.4(a)所示。为了分析这种非线性电路，电子工程师首先输入x∗（这是直流分析，x∗为一个固定的电压常量），并计算该电路的静态工作点y∗。接下来，电子工程师在静态工作点附近将非线性元件（晶体管）线性化，以得到所谓的小信号模型，它是冲激响应h(t)的线性模型（这是交流分析）。现在，xlin(t)=x(t)−x∗是在x∗小范围变化的时段内的时变函数，因此，ylin(t)=y(t)−y∗可由ylin(t)≈(h⊗xlin)(t)逼近得到，该模型如图0.4(b)所示。将输入信号限制在工作点附近的小范围内变化，这样就绕过了完全非线性分析的难点。于是可以采用线性化模型，该模型足以满足对我们所关注的性能测度进行评价的准确性要求，如分析放大器的增益。

图0.4的说明：一个基本非线性电路[图0.4(a)]被一个（简化的）小信号线性模型[图0.4(b)]替代；一个带有缓冲窗口流控制器的非线性网络[图0.4(c)]被一个最坏情况下的线性系统[图0.4(d)]替代。

在网络演算中，我们不将输入分解为一个小范围时变的部分和另一个较大但不变的部分。然而，我们确实采用线性系统替代了非线性元件，但现在前者是非线性系统的下界。第1章将介绍以服务曲线表达的例子：非线性系统y(t)=Π(x)(t)被线性系统ylin(t)=(β⊗x)(t)替代，其中β表示该服务曲线。这个模型对于所有t≥0和所有可能的输入x(t)存在ylin(t)≤y(t)。这也将允许我们计算性能测度，例如非线性系统中的延迟和积压。一个例子是图0.4(c)展示的窗口流控制器，第4章将对其进行分析。一条流x通过网络中的缓冲窗口流控制器馈入，实现某种映射y=Π(x)。缓冲窗口流控制器限制网络中准许输入的数据量，通过这种方法，网络中传输的数据的总量总是小于某个正数（窗口的大小）。我们不知道确切的映射 Π，假设知道这条流的一条服务曲线β，这样就能够用图0.4(d)的线性系统替代图0.4(c)中的非线性系统，以得到关于端到端延迟或传输中数据量的确定性界限。

阅读本书的时候，熟悉“常规”的电路与系统理论的读者将会发现两种系统论之间还有其他的相似或不同之处。然而，必须强调的是，读者并不需要预习系统论的知识，也可以学会本书讲解的网络演算知识。

致谢

我们衷心地感谢学者张正尚（Cheng-Shang Chang）和勒内·利奥纳多·克鲁兹的开创性的工作，我们之间的讨论对本书产生了深刻的影响。我们感谢安娜·沙尔尼（Anna Charny）、西尔维娅·乔达诺（Silvia Giordano）、奥利维尔·维舍尔（Olivier Verscheure）、弗雷德里克·沃尔姆（Frédéric Worm）、容·贝内（Jon Bennett）、肯特·本森（Kent Benson）、维桑特·乔尔维（Vicente Cholvi）、威廉·库尔特内（William Courtney）、朱昂·埃查格（Juan Echaguë）、费利克斯·法卡斯（Felix Farkas）、热拉尔·赫布特恩（Gérard Hébuterne）、米兰·沃伊诺维奇（Milan Vojnović）和张志力（Zhi-Li Zhang）提供的卓有成效的协助。在这里还要感谢与拉杰夫·阿格拉沃尔（Rajeev Agrawal）、马修·安德鲁斯（Matthew Andrews）、弗朗索瓦·巴切利（François Baccelli）、纪尧姆·于尔瓦（Guillaume Urvoy）和洛塔尔·蒂勒（Lothar Thiele）之间的交流。感谢霍利·科里亚蒂（Holly Cogliati）帮助准备手稿。

第一部分 网络演算基础知识

第1章 网络演算

本章介绍网络演算中到达曲线、服务曲线和整形器的基本概念。本章给出的应用与提供预留服务的基本网络有关，如异步传输方式（Asynchronous Transfer Mode,ATM）和互联网综合服务（IntServ）。其他情景下的应用将在后文中给出。

首先，本章给出累积量函数的定义，该函数能够处理连续和离散的时间模型。文中将展示如何用累积量函数初步解释播放缓冲器（playout buffer）问题，该问题将在第5章中进一步详细讨论。然后，本章在合适的到达曲线框架下描述漏桶和通用信元速率算法的概念。最后，本章详细地介绍最重要的到达曲线——分段线性函数和阶梯函数。读者可以使用阶梯函数厘清间距与到达曲线的关系。

本章还将介绍服务曲线的概念，它是一种应用于各种网络节点的通用模型。一般情况下，为ATM或互联网综合服务提出的所有调度器，均能够用一族简单的服务曲线描述，这样的服务曲线被称为“速率–时延”服务曲线。接下来，本章介绍一些网络的物理属性，诸如“突发一次性准则”“贪婪整形器保持到达约束”。读者可以发现贪婪整形器是最小加时不变系统。随后，本章还将介绍最大服务曲线的概念，该曲线能够被用于解释固定延迟或最大速率。本章的最后将展示如何将这些成果用于实际的缓冲区计量，给出用于处理固定延迟（如传播延迟）的实用性指南，此外，本章也介绍了由于数据包长度的变化而导致的畸变。

1.1 数据流的模型

1.1.1 累积量函数、离散时间与连续时间模型

使用累积量函数R(t)描述数据流很方便：R(t)定义为在时间间隔[0,t]内观测到的比特数。为了方便，除非特别说明，否则令R(0)=0。函数R是广义递增的，即属于第3.1.3节定义的空间F，在这个空间中我们能够使用离散时间或连续时间模型。在真实系统中，总是存在一个最小的粒度（比特、字、信元或数据包），因此总是可以假设R(t)被定义在一个具有有限元素的离散时间集合上。然而，在连续时间上考虑问题通常会令计算更为简便（函数R可以连续，也可以不连续）。如果R(t)是连续函数，则得到一种流体模型（fluid model）。否则，按照习惯应令R(t)为右连续或左连续的（这在实际情况中造成的差异不大）[1]。图1.1展示了这些定义。

例：用广义递增函数R(t)描述流。除非特别说明，在本书中通常考虑下列几种模型。

● 离散时间模型：t∈N={0,1,2,3,…}。

● 流体模型：t∈R+=[0,+∞)，并且R(t)是连续函数。

● 连续时间模型：t∈R+，并且R(t)是左连续或右连续函数。

图1.1是输入和输出函数的例子，用于展示术语定义与惯例。R1和R^∗₁表示连续时间的连续函数[流体模型，如图1.1(a)所示]，该函数中假设对于每个数据包以1个时间单位的持续时段逐比特到达。R2和R^∗₂表示连续时间下数据包到达时刻不连续的函数[如图1.1(b)所示的时刻1、4、8、8.6和14]：在这里假设只有数据包已经被完全接收才算被观测到。实心圆点表示在不连续点上的值：按照惯例，假设函数是左连续或右连续的。R3和R^∗₃表示离散时间模型的函数，如图1.1(c)所示，系统只有在时刻0、1、2才被观测。

我们假设R(t)具有导数则（这时得到了一个流体模型），此时r被称为率函数。然而在这一步可以看出，与率函数相比，累积量函数R更加简单。与使用标准代数不同，使用最小加代数不需要函数具有“好的”性质（例如具有导数）。

通过选择时隙δ，并且依据式（1.1）进行采样，总是可以将连续时间模型R(t)映射到离散时间模型S(n)，n∈N。

S(n)=R(nδ) （1.1）

通常这个结果损失了信息。对于逆映射，使用下面的公式。式（1.2）可以从S(n)导出连续时间模型[2]，其中，n∈N。

正如我们已经要求的那样，得到的函数R′总是左连续的。图1.1(b)展示了这种映射在δ=1，S=R3，R′=R2时的情形。

得益于式（1.1）的映射，任何连续时间模型的结果也可以应用于离散时间模型。除非另有证明，本书所有的结果既可应用于连续时间模型，又可应用于离散时间模型。离散时间模型一般用于ATM场景。反之，处理变长数据包通常使用连续时间模型（但不必是流体模型）。需要注意的是，处理变长数据包需要一些特定的机制，参见第1.7节的描述。

现在设想某个系统S，将其看作一个黑盒。S接收输入的数据，用它的累积量函数R(t)表示，并经过一段可变延迟后发送数据。将R^∗(t)称为输出函数，其含义是系统S输出端的累积量函数。系统S可能有以下情况——单一的恒定速率缓冲器、复杂的通信节点，甚至是一个完整的网络。图1.1以不同形式展示了一个单服务队列的输入和输出函数，其中每个数据包接受服务恰好花费3个时间单位。对于输出函数R^∗₁（流体模型），假设数据包能够在第1个比特到达后立即以恒定速率接受服务（直通假设），且能够逐比特观察数据包以恒定速率离去，例如，第1个数据包在时刻1与2之间到达，在时刻1与4之间离开。对于输出函数R^∗₂，假设在数据包被全部接收之后立即为它提供服务，并且只有当数据包全部被发送后才算离开系统（存储转发假设）。这里，第1个数据包在时刻1之后立即到达，并且在时刻4之后立即离开。对于输出函数R^∗₃（离散时间模型），第1个数据包在时刻2到达，在时刻5离开。

1.1.2 积压与虚拟延迟

从输入函数到输出函数，可以导出下面两个有价值的定量关系。

定义1.1.1（积压与虚拟延迟） 对于一个无损系统，在时刻t的积压为R(t)−R^∗(t)；在时刻t的虚拟延迟为d(t)=inf{τ≥0:R(t)≤R^∗(t+τ)}。

积压是系统中缓存的比特数。如果系统为单缓冲器，则积压是队列的长度。反之，如果系统更加复杂，则积压是假设能够同时观测输入和输出的情况下“正在传输”的比特数。时刻t的虚拟延迟的定义如下：对于某个在时刻t到达的比特，如果在它之前接收的所有比特先于它被服务，则这个在时刻t到达的比特应该经历的延迟为虚拟延迟。如图1.1(a)所示，积压被记为x(t)，是输入和输出函数之间的垂直偏差；虚拟延迟是水平偏差。如果输入/输出函数是连续的（流体模型），则容易看出R^∗(t+d(t))=R(t)，且d(t)是满足该等式的最小值。

从图1.1中可以看到3种函数中积压和虚拟延迟的值略有不同。对于图1.1(a)，第1个数据包的最后1个比特的延迟是d(2)=2个时间单位。反之，在图1.1(b)中延迟是d(1)=3个时间单位。当然，这是由各自函数中的不同假设造成的。类似地，在图1.1(b)中第4个数据包的延迟是d（8.6）=5.4个时间单位，这包含2.4个时间单位的等待时间和3个时间单位的服务时间。反之，在图1.1(c)中，d(9)=6个时间单位，其差异源于离散化造成的精确度损失。

1.1.3 例子：播放缓冲器

累积量函数是研究延迟与缓冲的有力工具之一，下面以简单的播放缓冲器问题来展示累积量函数的作用，一个简单的播放缓冲器的例子如图1.2所示。例如，在模仿电路分析（参见引言）的案例中，设想一个分组交换网络，从信源以恒定比特率r承载以比特为单位的信息，采用流体模型。先设定一个系统S，带有输入函数R(t)=rt的网络。因为排队，该网络会存在一些可变延迟，所以输出R^∗(t)不再具有恒定比特率r。如何能够再生成一个恒定比特率流呢？标准的机制是在播放缓冲器中平滑延迟的可变部分。具体操作如下：当数据的第1个比特在时刻dr(0)到达后，便被存储于缓冲器中，直到经历一段固定时间∆，其中是函数d的右极限[3]。接着，当缓冲器非空时，缓冲器以恒定比特率r接受服务。这里给出第二个系统S′，它带有输入R∗(t)和输出S(t)的网络。

假设网络延迟的可变范围被∆限制。这意味着对于每个时刻t，虚拟延迟（在本例中也是真实的延迟）满足

−∆≤d(t)−dr(0)≤∆

这样，因为采用流体模型，所以存在

r·(t−dr(0)−∆)≤R∗(t)≤r·(t−dr(0)+∆)

其中，两端的限制在图1.2(b)中以两条与R(t)平行的直线D1和D2表示。图1.2(b)表明，对于播放缓冲器S′，其输入R∗(t)总是在直线D2之上，意味着该播放缓冲器从未缺乏流量。这表明，输出S(t)由S(t)=r·(t−dr(0)−∆)给出。

正式的证明如下。我们使用反证法，假设缓冲器在一些时间饥饿，并且令t1为第1次饥饿发生的时刻。显然，播放缓冲器将在时刻t1为空，这样R^∗(t1)=S(t1)。存在时间间隔[t1,t1+ε]，在此间隔内到达播放缓冲器的比特数少于rε，如图1.2(c)所示。于是d(t1+ε)>dr(0)+∆这个不等式是不可能成立的。时刻t的积压等于R∗(t)−S(t)，这是直线D1和直线D2之间的垂直偏差，记为2r∆。

我们已经展示了播放缓冲器能够消除由网络造成的延迟变化，总结如下。

命题1.1.1 设想一个速率为r的恒定比特率流。这个流受到网络的影响，导致产生可变延迟，但是无损。得到的流被放入一个播放缓冲器，该播放缓冲器将流中的第1个比特延迟∆，并且以速率r读取该流。假设由网络造成的延迟可变性在∆的界限之内，则：

（1）播放缓冲器从不饥饿，并且以速率r形成一个恒定速率输出；

（2）缓冲器的容量为2r∆就足以避免溢出。

第5章将采用本章介绍的网络演算概念更仔细地研究播放缓冲器。

1.2 到达曲线

1.2.1 到达曲线的定义

如果想要为数据流提供保证，就需要网络提供某些特定支持，这将在第1.3节进行介绍。相应地，还需要限制从源端发送的流量。在综合服务网络（ATM网络或综合服务互联网）中，采用如下表述定义到达曲线的概念。

定义1.2.1（到达曲线） 给定一个t≥0的广义递增函数α，称流R受到α的约束，当且仅当对于所有s≤t下式成立

R(t)−R(s)≤α(t−s)

也称α是R的到达曲线，或R是α-平滑的。

注意，该条件在一组重叠的时间间隔上都成立，如图1.3所示。

仿射到达曲线 例如，若α(t)=rt，则该约束表示在宽度为τ的任何时间窗口上，流的比特数受到rτ的限制。在这种情况下，称这条流受到峰值速率约束。已知到达链路的流受到物理比特率r的限制时，就将发生这种情况。这种只受到峰值速率约束的流通常（但并不恰当地）被称为“恒定比特率”（Constant Bit Rate,CBR）流或者“确定比特率”（Deterministic Bit Rate,DBR）流。

若将α(t)=b作为到达曲线，b为常数，则意味着该流发送的比特数最多等于b。

在更一般的情况下，由于到达曲线与漏桶（leaky bucket）模型的关系，通常使用仿射到达曲线γr,b，该曲线的定义为：当t>0时，γr,b(t)=rt+b；否则γr,b(t)=0。若将γr,b作为到达曲线，则意味着源端允许一次发送b bit，但在更长的周期内，速率不超过r bit/s。参数b和r分别被称为突发容限（以数据量为单位）和速率（以单位时间传输的数据量为单位）。这种约束如图1.3所示。

阶梯函数到达曲线 在ATM场景中，还可以采用kvT,τ形式的到达曲线，其中vT,τ(t)为阶梯函数，vT,τ(t)的定义为：当t>0时，；否则vT,τ(t)=0（相关说明请参见第3.1.3节）。注意，由于vT,τ(t)=vT,0(t+τ)，因此vT,τ(t)是由vT,0在坐标系中向左移动τ个时间单位得到的。参数T（间隔）和τ（容限）以时间为单位。为了更好地理解vT,τ(t)的使用方法，设想一条发送固定长度（等于k个数据单位）数据包的流（如一条ATM流），假设数据包间隔至少为T个时间单位，一个恒定比特率的语音编码器就是这样一个示例，它在通话突发期间周期性地生成数据包，否则保持沉默。这样的流就具有kvT,0形式的到达曲线。

接下来假设该流与其他流复用，可以简单地假设该流的数据包和其他流的数据包一起被放入队列，这种情况通常出现在工作站、操作系统或者ATM适配器中。排队强加了一部分可变延迟，假设这个可变延迟受到限制，限制值等于τ个时间单位，我们将在本章的后续部分特别是第2章中说明这些界限是如何得到的。将R(t)和R∗(t)分别作为流在多路复用器的输入和输出累积量函数，那么有R^∗(s)≥R(s−τ)，据此可以得到

R∗(t)−R^∗(s)≤R(t)−R(s−τ)≤kvT,0(t−s+τ)=kvT,τ(t−s)

因此，输出累积量函数R∗(t)的到达曲线为kvT,τ。至此，可以证明一条周期为T、数据包长度为k、经历了可变延迟小于等于τ的周期流具有kvT,τ形式的到达曲线。参数τ通常被称为“单点信元延迟可变量”（one-point cell delay variation），这是由于该参数对应于一条周期流在一个单独的节点可观察到的偏差。

通常情况下，函数vT,τ可以被用来表示数据包之间的最小间隔（minimum spacing），正如下面的命题所述。

命题1.2.1（到达约束间隔） 设想一条具有累积量函数R(t)的流，它生成具有k个数据单位的固定长度数据包，并且数据包是瞬时到达的。假设时间是离散或连续的，并且R(t)为左连续。令tn为第n个数据包的到达时刻，则以下两种属性是等价的。

属性1：对于所有的m、n，tm+n−tm≥nT−τ。

属性2：流量的到达曲线为kvT,τ。

数据包长度和数据包生成的条件意味着R(t)具有nk的形式，n∈N；间隔条件意味着前后两个数据包之间的时间间隔大于等于T−τ，中间被一个数据包隔开的两个数据包之间的时间间隔大于等于2T−τ，以此类推。

证明：假设属性1成立，考虑任意间隔(s,t]，令n为在某一时间间隔内到达的数据包个数，假设这些数据包编号为m+1,…,m+n，那么s<tm+1≤…≤tm+n≤t，因此可以得到

t−s>tm+n−tm+1

结合属性1，则有

t−s>(n−1)T−τ

根据vT,τ的定义，上式可以变为vT,τ(t−s)≥n。因此，R(t)−R(s)≤kvT,τ(t−s)，这样就完成了第一部分的证明，即如果属性1成立，则属性2也成立。

反过来，现在假设属性2成立，如果模型的时间是离散的，则可以利用式（1.2）中的映射将该模型的时间转换为连续的，因此可以认为该模型均处于连续时间的情况。考虑任意整数m、n，对于所有ε>0，根据命题的假设有

R(tm+n+ε)−R(tm)≥(n+1)k

因此，根据vT,τ(t)的定义可知

tm+n−tm+ε>nT−τ

由于上式对所有ε>0均成立，因此tm+n−tm>nT−τ。

本小节后续将阐明由仿射函数和阶梯函数定义的到达曲线的约束之间的关系。首先，这需要一个技术性的引理，即总是可以将到达曲线退化为左连续的。

引理1.2.1（退化为左连续的到达曲线） 设想一条具有累积量函数R(t)的流，以及t≥0时的一个广义递增函数α(t)。假设R是左连续或右连续的，用αl(t)表示α在t的左极限（由于α为广义递增函数，因此该极限在每个时间点上都存在），并且有。若α为R的到达曲线，则αl亦然。

证明：首先假设R(t)为左连续。对于某s<t，令tn为收敛于t的一组时间增序列，且s<tn≤t。由于R(tn)−R(s)≤α(tn−s)≤αl(t−s)，R为左连续，，因此R(t)−R(s)≤αl(t−s)。

若R(t)为右连续的，令sn为收敛于上述s的一组时间递减序列，且s≤sn<t。类似地，有R(t)−R(sn)≤α(t−sn)≤αl(t−s)以及成立。因此，R(t)−R(s)≤αl(t−s)。

基于上述引理，到达曲线总是可以简化为左连续的[4]，注意，γr,b和vT,τ均为左连续的。此外，本书按照惯例假设累积量函数[如R(t)]为左连续的；然而这纯粹只是依照惯例，读者仍然可以选择右连续的累积量函数。相反，到达曲线总是只能设为左连续，而不是右连续。

在某些情况下，由γr,b和vT,τ定义的约束存在着等价关系。例如，一条ATM流（流的每个数据包长度是固定的，与一个数据单元相等）受到γr,b的约束，其中且b=1，等效于受到达曲线vT,0的约束。通常情况下，可以得到以下命题。

命题1.2.2 设想一条左连续或右连续的流R(t)，t∈R+；或一条离散时间的流R(t)，t∈N+，这条流生成具有k个数据单元的固定长度数据包，并且数据包是瞬时到达的。对于给定的T和τ，令及，则R受到γr,b的约束与R受到kvT,τ的约束是等价的。

证明：由于任意离散时间的流都可以转化为左连续的连续时间的流，因此这里只需考虑左连续的流R(t)，t∈R+。另外，不失一般性地，令k=1，即将数据单元设为一个数据包的长度。那么通过命题1.2.2中的参数映射，总是存在vT,τ≤γr,b。因此，如果vT,τ是R的到达曲线，那么γr,b亦是。

反过来，若假设γr,b为R的到达曲线。那么对于所有s≤t，都有R(t)−R(s)≤rt+b。又由于R(t)−R(s)∈N，因此可以得到R(t)−R(s)≤rt+b。令α(t)=rt+b，利用引理1.2.1，可以得到αi(t)=rt+b−1=vT,r(t)。

值得注意的是，这种等价关系成立的前提条件为数据包长度固定，且等于kvT,τ约束中的阶跃度（step size）。而在通常情况下，两族到达曲线给出的约束并不相同。例如，设想一条数据包长度为1个数据单位的ATM流，该条流受到形式为kvT,τ（k>1）的到达曲线的约束，而这条流可能是由多条ATM流叠加而成的。因此，该约束kvT,τ并不能映射成形式为γr,b的约束。第1.4.1节中将回顾这个例子。

1.2.2 漏桶模型和通用信元速率算法

到达曲线约束的起源可以追溯到漏桶模型和通用信元速率算法概念的提出。下面将证明漏桶模型中的控制器（漏桶控制器）对应仿射到达曲线γr,b，而通用信元速率算法对应阶梯函数vT,τ。对于具有固定数据包长度的流，如ATM信元，两者是等价的。

定义1.2.2（漏桶控制器） 漏桶控制器是一种按照下述方式分析流R(t)数据的设备。假设有一个容量为b的流体桶（池），桶的初始状态为空。桶底有一个小孔，当桶非空时，流体以每秒r个单位的速率漏出，如图1.4(a)所示。

来自流R(t)的数据必须向桶中倒入与数据量相等的流体。导致漏桶溢出的数据被称为不符合（non-conformant）数据，否则被称为符合（conformant）数据。

图1.4的说明：图1.4(a)给出了上述定义的示意，漏桶模型中的流体并不代表数据，然而它与数据使用相同的计量单位。图1.4(b)中的粗虚线表示输入流体在漏桶中的高度x(t)。首先假设r=0.4 kbit/时刻，b=1.5 kbit。那么，在时刻t=8.6，到达的数据包导致的流体累加将超过b=1.5 kbit，因此该数据包为不符合数据，此时不会有新的流体倒入漏桶。而如果假设b=2 kbit，那么所有数据包都将是符合数据。

不能将流体倒入漏桶的数据称为不符合数据。对于ATM系统，要么丢弃不符合数据，将其标记为低优先级以表示丢弃（所谓的“红色”信元）；要么将其放入缓冲区（缓冲漏桶控制器）。对于综合服务互联网，原则上不标记不符合数据，只是简单地将其流量类型设置为尽力传输（普通的IP流量）。

接下来将证明漏桶控制器将到达曲线强制约束为γr,b，首先给出以下引理。

引理1.2.2 设想一个以恒定比特率r提供服务的缓冲器。假设在时刻0，缓冲区为空，输入由累积量函数R(t)描述。若在时间区间[0,t]内没有流量溢出，则在时刻t的缓冲量由下式给出

证明：该引理可以通过推论1.5.2获得，但是在此给出直接证明。对于所有满足s≤t的s，r(t−s)为在区间(s,t]输出比特数的上界，因此

R(t)−R(s)−x(t)+x(s)≤(t−s)r

那么

x(t)≥R(t)−R(s)+x(s)−(t−s)r≥R(t)−R(s)−(t−s)r

也就证明了。

反过来，令t0为在时刻t之前缓冲区为空的最迟时刻，即

t0=sup{s:s≤t,x(s)=0}

若x(t)>0，则t0为t所在繁忙时段的开始时刻。那么，在区间(t0,t]内，队列一直为非空。由于输出的比特率为r，因此有

x(t)=x(t0)+R(t)−R(t0)−(t−t0)r （1.3）

假设R(t)为左连续的（否则证明会复杂一些），那么x(t0)=0，并且x(t)≤。

现在如果使漏桶模型的行为完全类似于容量为b且以恒定比特率r提供服务的缓冲区，则需满足流的累积量函数R(t)的数据是符合数据，即当且仅当漏桶高度x(t)在任意时刻不会超过b。根据引理1.2.2，需满足

即等价于对于所有s≤t，满足

R(t)−R(s)−r(t−s)≤b

因此，得出以下命题。

命题1.2.3 泄漏速率为r且容量为b的漏桶控制器会强制流量受到达曲线γr,b的约束，即承载符合数据的流具有到达曲线γr,b；若输入流量的到达曲线为γr,b，则流量的所有数据均为符合数据。

第1.4.1节将对漏桶模型的参数给出一个简单的解释，即r为服务流量所需的最小速率，b为以恒定速率向流提供服务时所需缓冲区的大小。

与漏桶模型概念大致相同的另一组模型是与ATM一起使用的通用信元速率算法（Generic Cell Rate Algorithm,GCRA）。

定义1.2.3[GCRA(T,τ)] 带有参数T和τ的通用信元速率算法用于固定长度数据包（称为“信元”）。与之一致的信元有如下定义，以信元的到达时刻t作为输入并返回结果，那么它具有一个内部（静态）变量的理论到达时刻（theoretical arrival time,tat）。在下面的算法伪码中，“τ”用tau表示。

● initially,tat=0

● when a cell arrives at time t,then

表1.1和表1.2的示例对GCRA的定义进行了说明，表中给出信元的到达时刻、信元到达之前内部变量tat的值以及信元状态（符合或不符合）。从表1.1和表1.2中可以看出，流量可以维持的长期速率为1/T（单位时间内的信元）；而τ表示容限，用于量化两个信元相对于理想间隔T可以提前到达的上限。例如，在表1.1的示例中，假设信元可以提早两个时间单位到达（到达时刻为从18到48的信元），但提前到达的信元不计入累积量，否则流量的到达速率将超过1/T（到达时刻为57的信元）。

通常会得到下面的结果，它建立了GCRA与阶梯函数vT,τ(t)的关系。

命题1.2.4 设想一条具有累积量函数R(t)的流，它生成长度为k个数据单位的固定长度数据包，并且数据包是瞬时到达的。设时间是离散或连续的，并且R(t)是左连续的，则以下两种属性等价。

属性1：流符合GCRA(T,τ)。

属性2：流的到达曲线为kvT,τ。

证明：命题的证明涉及最大加代数。首先假设属性1成立。θn表示第n个数据包（或信元）到达后的tat值，且θ0=0；tn表示第n个数据包的到达时刻。根据GCRA的定义，有θn=max{tn,θn−1}+T。将该等式应用于所有m≤n，并用符号∨表示求最大，根据∨的加法分配律可得到下列一组等式。

此外，由于θ0=0且t1≥0，有(θ0+nT)∨(t1+nT)=t1+nT，因此上面最后一个等式可以简化为θ1+(n−1)T=t1+nT。从最后一个等式开始，依次将等式迭代到前一个等式上，可得

θn=(tn+T)∨(tn−1+2T)∨…∨(t1+nT) （1.4）

现在考虑第(m+n)个数据包的到达时刻（m,n∈N，且m≥1），根据属性1，该数据包为符合数据，因此有

tm+n≥θm+n−1−τ （1.5）

根据式（1.4），对于任意1≤j≤m+n−1，有θm+n−1≥tj+(m+n−j)T。那么，令j=m，则可以得到θm+n-1≥tm+nT，再结合式（1.5），得出tm+n≥tm+nT−τ。根据命题1.2.1可知属性2成立。

反过来，假设属性2成立。利用数学归纳法证明第n个数据包是符合数据。首先当n=1时，总是有tm+1≥tm+T−τ成立，因此数据包总是符合数据，属性1成立；假设对于任意m≤n的数据包是符合数据，那么按照上述推导思路，式（1.4）对n成立，并将其改写为的形式。根据命题1.2.1可知，对于任意1≤j≤n，tn+1≥tj+(n−j+1)T−τ成立，因此。再结合上述θn的表达式，可以得到tn+1≥θn−τ，因此第(n+1)个数据包也是符合数据。

注意式（1.4）与引理1.2.2的类比。实际上，根据命题1.2.2，对于固定长度数据包，仿射函数γr,b(t)的到达约束和阶梯函数vT,τ(t)的到达约束具有等价关系，并给出以下推论。

推论1.2.1 对于一条具有固定长度数据包的流，满足GCRA(T,τ)等价于满足漏桶控制器，其中恒定比特率r和突发容限b为：

式中，δ是以数据单位表示的数据包的长度。

推论1.2.1也能够通过GCRA将漏桶控制器直接等价表示出来。将ATM信元作为数据单位，上述结果表明：对于一条ATM信元流，符合GCRA(T,τ)等价于将vT,τ(t)作为到达曲线，也等价于将作为到达曲线。

设想一组数量为I的漏桶控制器（或GCRA），其参数分别为ri、bi，对于任意i具有1≤i≤I。如果将它们并行地用于同一条流，则这条流的符合数据对于每个独立的漏桶控制器都是符合的。这条具有符合数据的流的到达曲线为

由此能够容易地表明，以这种方式获得的到达曲线族是一组分段线性凹函数，包括有限数量的分段。第1.5节将给出一些不属于该族的函数示例。

在ATM网络和互联网上的应用 漏桶模型和GCRA被用于定义与综合服务网络中流量相符的标准模型。ATM的恒定比特率连接由一个参数为T和τ的GCRA（或等效的漏桶模型）定义，T为理想信元间隔，τ被称为信元延迟可变容限（Cell Delay Variation Tolerance,CDVT）。ATM的可变比特率（Variable Bit Rate,VBR）连接由一条对应于两个漏桶模型或GCRA控制器的到达曲线定义；综合服务网络框架也使用相同的到达曲线族，例如

α(t)=min{M+pt,rt+b} （1.6）

其中，M表示最大数据包的长度，p表示峰值速率，b表示突发容限，r表示可持续速率，如图1.5所示。在综合服务互联网的术语中，四元组(p,M,r,b)也被称为流量规范（T-SPEC）。

1.2.3 次可加性和到达曲线

本节对最小加代数和到达曲线的关系进行讨论，首先以一个具有启发性的例子展开讨论。

设想一条流R(t)∈N，t∈N（例如一条ATM信元流，以信元计数）。为了简化讨论，可以认为时间是离散的。假设已知这条流受到达曲线的约束为3v10,0，例如这条流是由3条恒定比特率连接叠加而成的，每条恒定比特率连接的峰值速率为每单位时间0.1个信元。此外，假设已知这条流以每单位时间1个信元的物理特性在某条链路上到达观测点，这样能够总结出该流还受到达曲线的约束为v1,0。因此，显然它受到的约束可被表示为α1=min{3v10,0,v1,0}，如图1.6所示。

图1.6的说明：图1.6(a)为到达曲线α1=min{3v10,0,v1,0}，它的次可加闭包（良态函数，good function）如图1.6(b)所示。时间为离散的，图中的线段可方便读者观察。

通过到达曲线α1可知，R(10)≤3，R(11)≤6。然而，由于链路的约束，单位时间内最多只能有1个信元到达，因此也可以得出R(11)≤R(10)+[R(11)−R(10)]≤α1(10)+α1(1)=4。换言之，R受到α1的约束，然而可以得到比α1本身更优的上界。这是因为根据上述用例可以看出，α1不是一个良态函数。

定义1.2.4 设想函数α∈F，若其满足以下任一等价属性，则可以说α为良态函数。

属性1 α是次可加（sub-additive）的，且α(0)=0；

属性2 α=α⊗α；

属性3 ；

属性4 （α的次可加闭包）。

该定义使用了第3章中定义的次可加性、最小加卷积、最小加解卷积（min-plus deconvolution）和次可加闭包，上述4项属性的等价性来自推论3.1.1和推论3.1.13。次可加性（属性1）表示α(s+t)≤α(s)+α(t)。若α不是次可加的，那么α(s)+α(t)就可能是比α(s+t)还好的界限，如图1.6(a)中α1所示。属性2、3、4利用了第3章中定义的最小加卷积、最小加解卷积和次可加闭包，特别根据定理3.1.10 可知，函数α的次可加闭包是满足的最大良态函数；此外，若α∈F，则。

关于到达曲线的主要结论是：任何到达曲线都可以由其次可加闭包表示的良态到达曲线所替代。如图1.6(b)中所示。

定理1.2.1（到达曲线退化为次可加闭包曲线） 若一条流被一个广义递增函数α约束，则等价于该条流被该函数的次可加闭包所约束。

下面给出定理的相关证明，该证明可以体现到达曲线概念的核心，即与最小加代数中线性关系的理论基础有关。

引理1.2.3 当且仅当R≤R⊗α时，流R受到达曲线α的约束。

证明：R≤R⊗α表示对于∀t，R(t)≤(R⊗α)(t)。最小加卷积R⊗α在第3章中进行了定义。由于R(s)和α(s)的定义仅对于s≥0成立，因此R⊗α满足。从而，∀s∈[0,t]，R≤R⊗α与R(t)≤R(s)+α(t−s)等价。

引理1.2.4 若α1和α2均为流R的到达曲线，那么α1⊗α2也为流R的到达曲线。

证明：根据第3章可知，若α1和α2为广义递增函数，则α1⊗α2亦是。余下部分的证明可以直接根据引理1.2.3以及“⊗”的结合律得出。

定理1.2.1的证明：由于α为到达曲线，因此根据引理1.2.4，α⊗α亦是到达曲线；通过迭代，对于所有n≥1，α(n)同样是到达曲线；根据δ0的定义，δ0亦是到达曲线。因此次可加闭包也是到达曲线。

反过来，由于，因此，若为到达曲线，则α亦是。

例：因此应将到达曲线的选择限制为次可加函数。可以预测第1.2.1节中给出的γr,b和vT,τ函数是次可加的。另外，由于t=0时，它们的函数值为0，因此它们为良态函数（根据定义1.2.4，属性1）。根据第1章的内容可知，任意α(0)=0的凹函数α都是次可加的，因此γr,b为次可加的。

函数vT,τ不是凹函数，但它仍然是次可加的。这是因为根据其定义，上取整函数为次可加的，这样有

回到开始的例子α1=min{3v10,0,v1,0}，正如文中所讨论的，α1不是次可加的。根据定理1.2.1，可以通过式（3.13），将α1替换为它的次可加闭包，该计算通过以下引理得以简化，引理可以直接由定理3.1.11得出。

引理1.2.5 令γ1和γ2为良态函数，则min{γ1,γ2}的次可加闭包为γ1⊗γ2。

若将上述引理应用于α1=min{3v10,0∧v1,0}，由于vT,τ为良态函数，因此α1的次可加闭包为，如图1.6所示。

最后讨论等价命题，由于该命题的证明很简单，因此留给读者自行证明。

命题1.2.5 对于一个给定的α(0)=0的广义增函数α，考虑其定义的源为R(t)=α(t)（贪婪源，greedy source）。当且仅当α为良态函数时，α可作为源的到达曲线。

VBR到达曲线 测试通过漏桶或GCRA组合获得的到达曲线族，这些到达曲线是凹分段线性函数。根据第3章可知，如果γ1和γ2为凹函数，且满足γ1(0)=γ2(0)=0，那么γ1⊗γ2=γ1∧γ2。因此，任何满足α(0)=0的凹分段线性函数均为良态函数。特别地，若通过以下方式定义VBR连接或综合服务流的到达曲线，有

如图1.5所示，则α为良态函数。

从引理1.2.1可以看出，到达曲线α总是可以由其左极限αl代替。那么它应该如何与次可加闭包进行组合？这两种操作是否满足交换律[是否满足]？通常情况下，若α为左连续的，那么不能保证也是左连续的，因此无法保证操作的可交换性。然而，如果为良态函数，则有。因此，首先对到达曲线α取次可加闭包，然后取左极限进行改进，得到的到达曲线为良态函数，也是左连续函数（极良态函数），并且由α产生的约束等同于由产生的约束。

最后，利用一致连续性的论据可以很容易地证明：如果α在任何有界时间间隔内的取值是有限的，并且α是左连续的，那么也是左连续的，并且有。这个假设在离散时间内是始终正确的，并且在大多数实际情况下也是如此。

1.2.4 最小到达曲线

现在设想一条给定的流R(t)，应该确定它的最小到达曲线。例如，当R的流量值是通过测量得到的，就会引出如何确定最小到达曲线的问题。下面的定理说明R(t)存在一条最小到达曲线。

定理1.2.2（最小到达曲线） 给定一条流R(t)t≥0，那么：

● 函数是该流的到达曲线；

● 对于任何一条可以约束流的到达曲线α，总有；

● 是一个良态函数。

称函数为流R的最小到达曲线。

最小到达曲线的定义使用了第3章中定义的最小加解卷积。图1.7展示了一个例子，测量得到流R的最小到达曲线为。

证明：通过的定义，有，满足是一条到达曲线。

现在假设某条到达曲线α也是流R的到达曲线。由引理1.2.3可知，R≤(R⊗α)。根据第3章定理3.1.12的规则14，有。表明是流R的最小到达曲线。最后，根据定理3.1.12的规则15，可知是一个良态函数。

设想一个贪婪源R(t)=α(t)，α为良态函数，那么其最小到达曲线是什么？[5] 最后，好奇的读者或许想要知道是否是左连续的，证明如下。假设R是右连续或左连续的，根据引理1.2.1可知，的左极限也是一条到达曲线，并且其上界为。由于是最小到达曲线，它遵循，因此是左连续的（并且为良态函数）。

在很多情况下，我们并不关心此处给出的绝对最小到达曲线，而是关心在一族到达曲线中[例如，在所有γr,b(t)函数中]找到最小到达曲线。关于这方面的研究，请参阅参考文献[4]。

图1.7的说明：时间为离散的，且设单位时间为40 ms。图1.7(a)和图1.7(b)给出了2种MPEG视频流的迹线，该迹线以各时隙中数据帧到达数量的数据绘制而成，两种迹线看上去很像，但它们所对应的服务曲线不同，每个数据帧具有固定帧长（416 Byte）。图1.7(c)显示了第一条迹线和第二条迹线的最小到达曲线。第一条迹线中的大突发度出现较早，因此其最小到达曲线较大。

1.3 服务曲线

1.3.1 服务曲线的定义

我们已经看出综合服务网络的第一个原则是用到达曲线约束流。为了提供预留，网络节点反过来需要为流提供一些保障，这是由数据帧的调度[5]完成的。本节介绍和研究了服务曲线的概念，利用这一概念可以抽象出数据帧调度的详细内容。由于服务曲线比到达曲线更加抽象，因此本节将结合一些例子进行解释。

首先，设想一个简单的通用处理器共享（Generalized Processor Sharing,GPS）[6]节点的调度器的例子，这里只给出简单的定义，第2章将给出更多细节。GPS节点并行服务多条流，假设每条流都被分配了给定的速率。可以保证的是，流在节点上产生积压所持续的t时间段内将获得至少等于rt的服务量，其中r为分配给流的速率。GPS节点是一个理论概念，实际上无法实现，因为它依赖于流体模型，而在真实网络中使用的是数据帧。第2.1节将介绍如何解决实际方案与GPS模型之间的差异。设想一条输入流R经过一个速率为r的GPS节点后，对应的输出流为R^∗，另外假设节点的缓冲区足够大，因此不会发生溢出，读者将在本节中学习如何计算满足上述假设的缓冲区的大小。对于有损系统的分析参见第9章的内容。在这些假设下，对于所有时刻t，令t0为距离时刻t最近的忙周期的开始时刻，根据GPS的假设，有

R∗(t)−R^∗(t0)≥r(t−t0)

像往常一样假设R为左连续的，那么在时刻t0，流量的积压为0，因此有R(t0)−R^∗(t0)=0。结合前一个公式，有

R∗(t)−R(t0)≥r(t−t0)

因此，对于所有时刻t，有，也可以写成

R^∗≥R⊗γr,0 （1.7）

注意，GPS节点的局限性案例是速率为r的恒定比特率服务器，该服务器专门用于服务单条流。第2章将详细研究GPS。

接下来介绍第二个例子，假设关于网络节点唯一的信息是，给定流R的比特的最大延迟，由某个定值T限制，并按先进先出的顺序服务流的比特。我们将在第1.5节中介绍，这种假设与一族被称为“最早截止期限优先（Earliest Deadline First,EDF）”的调度器一起使用。可以将该假设转换为对于所有t的延迟界限为d(t)≤T。由于R∗总是广义递增的，因此根据d(t)的定义可以得出R^∗(t+T)≥R(t)。相反地，如果R∗(t+T)≥R(t)，那么d(t)≤T。换言之，最大延迟受到T的限制等价于对于所有t，有R∗(t+T)≥R(t)，又可以写为

R∗(s)≥R(s−T),s≥T

第3章中介绍的“冲激”函数δT定义为：若0≤t≤T，则δT(t)=0；若t>T，则δT(t)=+∞。该函数具有以下性质：对于t≥0定义下的任意广义递增函数x(t)，若t≥T，则(x⊗δT)(t)=x(t−T)；否则，(x⊗δT)(t)=x(0)。因此，关于最大延迟的条件，可以写成

R∗≥R⊗δT （1.8）

对于上述的两个例子，存在相同形式的输入/输出关系[式（1.7）和式（1.8）]，这表明服务曲线的定义确实可以提供有用的结果。

定义1.3.1（服务曲线） 设想一个系统S，以及一条经过S的输入和输出函数为R和R∗的流。当且仅当β为广义递增函数，且满足β(0)=0和R∗≥R⊗β时，可以认为S为这条流提供的服务曲线是β。

图1.8展示了上述定义，输出R∗必须位于R⊗β之上，R⊗β为所有曲线的下包络。上述定义条件也可以表示为，β为广义递增函数，满足β(0)=0，且对于所有t≥0，有

实际上，如果β是连续的，则可以避免使用下确界。以下命题可以由定理3.1.8直接得到。

命题1.3.1 若β是连续的，则服务曲线的属性意味着对于所有t，可以找到t0≤t，使得

R∗(t)≥Rl(t0)+β(t−t0) （1.9）

其中为在t0的左极限，若R为左连续的，那么Rl(t0)=R(t0)。

对于恒定速率的服务器（以及任何严格服务曲线），可以将式（1.9）中的t0视为忙周期的开始；对于其他情况，则t0是未知的。然而，某些情况下，可以选择随t递增的t0。

命题1.3.2 若服务曲线β是凸的，那么可以找到某个广义递增函数τ(t)，使得式（1.9）中可以取t0=τ(t)。

注意，由于假设服务曲线为广义递增的，因此凸函数β必须为连续的。因而可以应用命题1.3.1的结论。

证明：这里给出当R为左连续时的证明，更一般情况下的证明基本上是相同的，仅涉及一些ε削减。考虑t1<t2，且当t=t1时，令τ1为式（1.9）中t0的值。同时考虑任意t′≤τ1，根据τ1的定义，有

R∗(t′)+β(t1−t′)≥R∗(τ1)+β(t1−τ1)

因此

R∗(t′)+β(t2−t′)≥R∗(τ1)+β(t1−τ1)−β(t1−t′)+β(t2−t′)

由于β为凸的，因此对于任意4个满足a≤c≤b、a≤d≤b以及a+b=c+d的数总有

β(a)+β(b)≥β(c)+β(d)

感兴趣的读者可以通过画图进行验证。将以上式子应用于a=t1−τ1、b=t2−t′、c=t1−t′、d=t2−τ1，有

R∗(t′)+β(t2−t′)≥R∗(τ1)+β(t2−τ1)

上式对所有t′≤τ1均成立。接下来固定t2，对于所有的t′≤t2，求R∗(t′)+β(t2−t′)的最小值。对于某些t′≥τ1，上式可以达到最小值。

第1.4节将给出服务曲线，保证服务曲线与到达曲线约束的结合构成综合服务网络中使用的确定性边界的基础。在此之前，先给出一个在实际中使用的经典服务曲线的示例。

1.3.2 经典服务曲线示例

保证延迟节点 对于第1.3.1节中第二个例子的分析可以被重现，表述如下。

命题1.3.3 对于无损的比特处理系统，任何比特的延迟都由某个定值T限制，等价于系统向流提供δT的服务曲线。高低优先级非抢占式服务如图1.9所示。

图1.9的说明：两条优先级流（H和L）在队列头部（Head of the Line,HOL）接受可抢占式服务。高优先级的流受到达曲线α的约束。

不可抢占式优先级节点 设想一个服务两条流RH(t)和RL(t)的节点，第一条流具有高于第二条流的不可抢占式优先级（见图1.9）。该示例说明了某些流类型比其他流类型具有高优先级时所使用的通用框架，如因特网的区分服务[7]。服务器的速率是恒定的，等于C；称R∗_H(t)和R∗_L(t)为两条流的输出。对于第一条高优先级流，在某个时刻t，令s为高优先级流积压周期的起始时刻。高优先级的服务可以因在s之前不久到达的低优先级数据帧延迟。但是，只要这个数据帧被服务完毕，服务器就会专用于高优先级。只要有高优先级的流排队，在时间区间(s,t]上，输出的比特数为C(t−s)。因此

R∗H(t)−R∗H(s)≥C(t−s)−lLmax

其中lLmax为低优先级数据帧的最大帧长。根据s的定义，有R∗H(s)=RH(s)，因此

R∗_H(t)≥RH(s)+C(t−s)−lLmax

又因为

R∗_H(t)−RH(s)=R∗_H(t)−R∗_H(s)≥0

从而可以得到

R∗_H(t)≥RH(s)+［C(t−s)−lLmax］+

函数被命名为“速率–时延”函数，其中速率为C、延迟为（参见参考文献[8]，本书中记为）。因此该函数为高优先级流的服务曲线。

接下来分析低优先级流。为了确保不出现饥饿现象，假设高优先级流受到到达曲线αH的约束。对于任意时刻t，令s′为服务忙周期的起始时刻（注意s′≤s）。在时刻s′，两条流的积压都为0，即满足R∗_H(s′)=RH(s′)和R∗_L(s′)=RL(s′)。在时间间隔(s′,t]上，输出为C(t−s′)。因此

R∗_L(t)−R∗_L(s′)≥C(t−s′)−[R∗_H(t)−R∗_H(s′)]

另外，由于

R∗_H(t)−R∗_H(s′)=R∗_H(t)−RH(s′)≤RH(t)−RH(s′)≤αH(t−s′)

以及R∗_H(t)−R∗_H(s′)≥0，那么有

R∗_L(t)−RL(s′)=R∗_L(t)−R∗_L(s′)≥S(t−s′)

其中，S(u)=[Cu−αH(u)]+。因此，若S为广义递增的，那么低优先级流获得的服务曲线为函数S。进一步假设αH=γr,b，即高优先级流受到漏桶控制器或GCRA的约束。在这种情况下，低优先级流的服务曲线S(t)为速率–时延函数βR,T(t)，其中R=C−r，。

因此，存在以下命题。

命题1.3.4 设想一个速率为C的恒定比特率服务器，它服务高、低优先级的两条流，并且高优先级流是非抢占式的。那么高优先级流具有速率为C和延迟为的速率–时延服务曲线，其中lLmax为低优先级流的最大帧长。此外，若高优先级流是γr,b-平滑的，且r<C，那么低优先级流具有速率为C−r和延迟为的速率–时延服务曲线。

这个例子表明了速率–时延服务曲线的重要性。在第2章（定理2.1.2）可以看到，实际情况下所有GPS的实现都提供了速率–时延类型的服务曲线。

严格服务曲线（strict service curve）对于一类重要的网络节点，服从以下的理论框架。

定义1.3.2（严格服务曲线） 如果在任意积压期间u内，流的输出至少等于β(u)，那么认为系统S为流提供了严格服务曲线β。

GPS节点作为这种示例，提供形式为β(t)=rt的严格服务曲线，利用第1.3.1节GPS节点示例中相同的忙周期分析，可以证明以下命题。

命题1.3.5 如果节点为某条流提供的严格服务曲线为β，那么β也是这条流的服务曲线。

严格服务曲线的性质提供了一种可视化服务曲线概念的边界方式：在这种情况下，β(u)是忙周期内保证的最小服务量。但是注意，定义1.3.1给出的服务曲线定义更加通用。贪婪整形器（见第1.5.2节）是一个将整形曲线作为服务曲线的系统示例，但它并不满足严格服务曲线的属性。相反，在本书后文可以看到，只有在采用严格服务曲线的定义时，某些属性才成立。第7章将给出严格服务曲线的更具一般性的讨论。

可变容量节点 设想一个为某条流提供可变服务容量的网络节点。在某些情况下，可以通过累积量函数M(t)对容量进行建模，其中M(t)为时刻0∼t为流提供的总服务容量。例如，对于ATM系统，将M(t)视为时刻0∼t可用于发送流信元的时隙数。假设节点的缓冲足够大，使溢出不可能发生，那么可以给出以下显而易见的命题，但该命题在实际应用中具有重要的意义。

命题1.3.6 如果对于某个固定的函数β，且对于所有0≤s≤t，可变容量满足最小的保证形式如下

M(t)−M(s)≥β(t−s) （1.10）

那么β为严格服务曲线。

因此，β也是该特定流的服务曲线。利用可变容量节点的概念建立服务曲线属性，也是一个便捷方法。对于实时系统（而不是通信网络）的应用，请参阅参考文献[9]。

第4章将提到可变容量节点的输出可由下式给出

最后，回到优先级节点，有以下命题。

命题1.3.7 命题1.3.4中针对高优先级流的服务曲线是严格的。

该命题的证明留给读者，它依赖于如下的事实，即恒定速率服务器是一种整形器。

1.4 网络演算基础

本节会给出几种主要的网络演算结果，它们是关于具有服务保证的无损系统的界限。

1.4.1 3种界限

第一个定理说明，积压界限由到达曲线和服务曲线之间的垂直距离确定。

定理1.4.1（积压界限） 假设流量的到达曲线为α，经过服务曲线为β的系统。那么对于所有t，积压R(t)−R∗(t)满足

证明：直接根据服务曲线和到达曲线的定义得

因此

接下来，利用水平距离的概念[具体可见第3章式（3.21）]，令

δ(s)=inf{τ≥0:α(s)≤β(s+τ)}

根据定义1.1.1，假设存在这样的系统，α为系统的输入，β为系统的输出，δ(s)为系统的虚拟延迟（换言之，假设α≤β）。那么，h(α,β)是δ(s)的所有值的上确界。第二个定理给出一般情况下的延迟界限。

定理1.4.2（延迟界限） 假设流的到达曲线为α，经过服务曲线为β的系统。那么对于所有t，虚拟延迟d(t)满足d(t)≤h(α,β)。

证明：考虑某个定值t≥0；根据虚拟延迟的定义，对于所有τ<d(t)，有R(t)>R∗(t+τ)。接下来，根据服务曲线在时刻t+τ的属性，表明存在某个s0，使得

R(t)>R(t+τ−s0)+β(s0)

根据上式可知t+τ−s0<t，因此

α(τ−s0)≥[R(t)−R(t+τ−s0)]>β(s0)

从而，τ≤δ(τ−s0)≤h(α,β)。这里对于所有τ<d(t)均成立，因此有d(t)≤h(α,β)。

定理1.4.3（输出流约束） 假设流的到达曲线为α，经过服务曲线为β的系统。输出流受到达曲线为的约束。

该定理利用了第3章介绍的最小加解卷积，该方法已经在证明定理1.2.2时被使用过。

证明：利用上述符号，对于0≤t−s≤t，考虑R∗(t)−R∗(t−s)，并在时刻t−s应用服务曲线的定义。假设inf在定义R⊗β中表示最小值，也就是说，存在某个u≥0，使得t−s−u≥0时

(R⊗β)(t−s)=R(t−s−u)+β(u)

因此有

R∗(t−s)−R(t−s−u)≥β(u)

且有

R∗(t)−R∗(t−s)≤R∗(t)−β(u)−R(t−s−u)

由于R∗(t)≤R(t)，因此

R∗(t)−R∗(t−s)≤R(t)−R(t−s−u)−β(u)≤α(s+u)−β(u)

而最后一项根据算子的定义，以为界。

接下来，放宽inf在定义R⊗β中表示最小值的假设。在这种情况下，证明基本上是相同的，只是复杂程度较低。对于所有ε>0，存在某个u≥0，使得t−s−u≥0时

(R⊗β)(t−s)≥R(t−s−u)+β(u)−ε

同理

上式对所有ε>0均成立。计算3种界限的示意如图1.10所示。

图1.10的说明：一条被漏桶约束的流，被某个提供速率–时延服务曲线的节点服务，图1.10展示了如何计算缓冲界限、延迟界限和输出流约束，这里要求缓冲容量能够承载可能的最大积压，即缓冲界限等于积压界限。如果r≤R，则缓冲界限为b+rT，延迟界限为，并且流的突发度增加rT。如果r>R，则这些界限是无限大的。

漏桶的简单示例 假设一条流受到漏桶的约束，其到达曲线的形式为α=γr,b，流经过一个服务曲线为βR,T的节点。感兴趣的读者可以找出图1.10中有关3种界限的结果。

对于T=0的特例，受漏桶约束的流以恒定速率R被服务。如果R≥r，则服务该流所需的缓冲区大小为b，否则为无穷大。漏桶参数中，r为流所需的最小服务速率，b是对于任意恒定速率大于等于r的流所需的缓冲区大小。

例：速率–时延服务曲线服务下的VBR流。对于一条由T-SPEC(M,p,r,b)定义的VBR流，意味着该流的到达曲线为α(t)=min{M+pt,rt+b}（见第1.2节）。假设流经过一个服务曲线为速率–时延函数β（β=βR,T）的节点，该示例为综合服务使用的标准模型。利用定理1.4.1和定理1.4.2，假设R≥r，即预留速率不小于流的可持续速率。

根据α和β之间的凸域（如图1.11所示），可以看到在α或β的某个角点处达到了垂直最大距离，从而

v=max{α(T),α(θ)−β(θ)}

其中。类似地，在一个角点处达到水平最大距离。在图1.11中，它标记为AA′或BB′的距离。因此，延迟界限d为

经过最大加代数运算，重新给出这些结果。

命题1.4.1（综合服务模型的缓冲界限和延迟界限） 一条满足T-SPEC(M,p,r,b)的VBR流经过一个服务曲线为速率–时延函数β=βR,T的节点，该流所需的缓冲界限为

该流的延迟界限为

此外，还可根据定理1.4.3算出输出流量的到达曲线α∗。根据（见第3章）的性质，有，注意

对于所有f均成立（左移）。

的计算参见定理3.1.14，计算中包括时间反转和平滑。然而如果α为凹函数，这里就能够给出直接的推导。对于一个凹函数α，定义t0为

t0=inf{t≥0:α′(t)≤R}

其中α′是左导数，并假设t0<+∞。除了可能在其定义区间的末尾，凹函数始终具有左导数。通过研究函数u→α(t+u)−Ru的变化可以发现：若s≥t0，则；若s<t0，则。

将各个部分放在一起，可以看出输出函数α∗是通过α得到的。

● 利用斜率为R的线性函数代替[0,t0]上的α，该线性函数在t=t0处具有与α相同的值，且在[t0,+∞)保持与α相同的值。

● 然后左移T。

图1.12展示了上述过程。注意，由于“⊗”满足交换律，因此可以以任意顺序执行上述两个步骤。请验证该过程与定理3.1.14的等效性。

如果将其应用于VBR连接，那么可以得到以下结果。

命题1.4.2（综合服务模型的输出上界） 与命题1.4.1采用相同的假设，输出流量的到达曲线α∗为

示例（ATM）考虑图1.13所示的示例，聚合流的到达曲线为阶梯函数10v25,4。该图说明所需的缓冲界限为10个ATM信元，最大延迟为18个时隙。根据推论1.2.1可知，GCRA约束与漏桶等效。因此，10个连接的每一个都受到仿射到达曲线γr,b的约束，其中并且。然而，如果将所得的仿射函数 10γr,b作为聚合流的到达曲线，则计算出的缓冲界限为11.6，延迟界限为19.6。仿射函数高估了缓冲区和延迟范围。请记住，阶梯函数和仿射函数之间的等价关系仅适用于数据包大小等于阶跃度的流量的情况，多个ATM连接的聚合流显然不属于这种情况。

图1.13的说明：假设ATM节点为10条ATM连接提供服务，每条连接都受GCRA(25,4)约束（以时隙计数）。节点向聚合流提供的服务曲线为βR,T，其中速率R为每时隙1个信元，延迟T为8个时隙。该图表明，通过仿射函数γr,b近似阶梯函数10v25,4会导致对边界高估。

定理1.4.3的直接应用表明，输出流的到达曲线为α∗₀(t)=α(t+T)=v25,12(t)。如果已知服务曲线为严格服务曲线，那么可以对边界略微进行改进，这将在第2章中进行讨论。

1.4.2 界限是紧致的吗

接下来讨论这3种界限各自的优化情况。对于积压界限和延迟界限，答案很简单。

定理1.4.4 对于定理1.4.1和定理1.4.2的积压界限和延迟界限，若满足

● α为良态函数[广义递增、次可加、α(0)=0]。

● β为广义递增函数，且β(0)=0。

则界限是紧致的。更确切地说，存在一个因果系统，其输入流为R(t)，输出流为R∗(t)，输入流受到α的约束，提供给流的服务曲线为β，则两个边界是紧致的。

因果系统意味着R(t)≤R∗(t)，定理1.4.4意味着定理1.4.1中的积压界限等于，延迟界限等于。其中，d(t)是定义1.1.1中给出的虚拟延迟。

证明：通过定义R=α，R∗=min{α,β}，构建一个系统R，R∗。由于R∗≤α=R，因此该系统为因果系统。假设任意时刻t，若α(t)<β(t)，那么

R∗(t)=R(t)=R(t)+β(0)

否则

R∗(t)=β(t)=R(0)+β(t)

上述任意一种情况，对于所有t，总是存在s≤t，使得R∗(t)≥R(t−s)+β(s)，这表明了服务曲线的性质。

当然，边界的紧致程度与服务曲线和到达曲线相同。可以看出，R(t)=α(t)的源端称为贪婪源端。因此，积压界限和延迟界限是贪婪源端所能达到的最坏界限。

实际上，即使具体的结果不太理想，输出的也是最坏情况下的界限。

定理1.4.5 假设：

1. α为良态函数[广义递增、次可加、α(0)=0]；

2. α为左连续的；

3. β为广义递增函数，且β(0)=0；

4. 的界限不受上述约束。

则定理1.4.3的输出界限是紧致的。更确切地说，存在一个因果系统，其输入流为R(t)，输出流为R∗(t)，输入流受到α的约束，提供给流的服务曲线为β，则由定理1.4.3给出的α∗是R∗的最小到达曲线。

根据第1.2节可知，前3个条件并非强制性的。首先讨论最后一个条件的含义，根据最大加解卷积（max-plus deconvolution）的定义

对于的解释如下。假设一个贪婪源端R(t)=α(t)，为在持续时间为t的间隔内到达源端比特数的最小值。若函数为广义递增的，那么最后一个条件意味着。比如，对于具有T-SPEC(p,M,r,b)的VBR源端，有且满足条件。如果到达曲线为阶梯函数，那么容易证明这种情况也是满足上述条件的。

证明定理1.4.5需要一些技巧，留在本章末尾进行证明。

读者可能会好奇，输出上界α∗是否为良态函数。然而，由于α∗(0)为积压界限，在合理的情况下为正数，因此答案是否定的。另外，由于α∗满足次可加性（证明很简单，留给读者自行证明），因此修正函数δ0∧α∗[t>0时，为α∗(t)；否则为0]为良态函数。若α为左连续的，δ0∧α∗甚至为极良态函数，通过定理1.4.5也可知δ0∧α∗是左连续的。

1.4.3 级联

到目前为止，已经讨论了基本网络元件的部分。接下来，讨论这些主要结论在网络元件串联中的应用。

定理1.4.6（节点的级联） 假设一条流依次流经系统S1和S2，假设Si（i=1,2）的服务曲线为βi，那么两个系统的级联为该流提供的服务曲线是β1⊗β2。

证明：令R1为节点1的输出、节点2的输入。根据服务曲线的性质，对于节点1，有

R1≥R⊗β1

对于节点2，有

例：对于提供速率–时延服务曲线（综合服务通常满足该假设）的两个节点，有

综合服务节点的级联相当于将单独节点的延迟相加，并且取服务速率中的最小值。

此外，还可以对速率–时延服务曲线模型进行另一种解释。已知βR,T=(δT⊗λR)(t)，可以将具有速率–时延服务曲线的节点看作保证延迟为T的节点与速率为R的恒定比特率节点的级联或与速率为R的GPS节点的级联。

突发一次性准则 通过级联定理，可以理解“突发一次性准则”的现象。对于两个节点的级联，每个节点提供速率–时延服务曲线（综合服务通常满足该服务曲线模型）。假设输入受到γr,b的约束，且r<R1、r<R2。比较通过以下两种方法计算的最坏延迟界限：通过网络的服务曲线；通过迭代分别计算网络中每个节点的延迟界限。

根据定理1.4.2，可以计算出延迟界限D0为

其中。接下来，应用第2种方法，根据定理1.4.2，节点1的延迟界限为

节点1的输出到达曲线α∗为

α∗(t)=b+r(t+T1)

那么节点2的延迟界限为

因此

由此看出，D0<D1+D2。换言之，根据全局服务曲线计算出的延迟界限优于单个节点延迟界限的累加。

更进一步地比较，根据单个节点计算出的延迟界限的形式为（节点1，项可以看作由输入流量的突发引起的延迟分量，而T1是由节点本身引起的延迟分量。可以看出，D1+D2包含两次形式的延迟分量，而D0只包含一次。这就是“突发一次性准则”现象。D0和D1+D2之间的另一个区别是项，这是由节点1上突发度的增加引起的。可以看出，突发度的增加不会造成整个延迟的增加。

定理1.4.6的一个推论是，端到端延迟界限不依赖于级联节点的顺序。

1.4.4 积压界限的改进

这里给出两种情况，可以稍微改进一下积压界限。

定理1.4.7 假设一条到达曲线为α的流通过一个严格服务曲线为β的无损节点，且存在某个u0>0，α(u0)≤β(u0)成立，那么忙周期的持续时间小于等于u0。此外，对于任意时刻t，积压R(t)−R∗(t)满足

该定理表明，对于积压界限的计算，考虑小于u0的时间间隔就足够了，这是由于忙周期的持续时间小于u0。

证明：假设某个缓冲区非空时的时刻为t，令s为t之前缓冲区为空的最后一个时刻。那么，根据严格服务曲线的性质，有

R∗(t)≥R∗(s)+β(t−s)=x(s)+β(t−s)

因此，时刻t的缓冲区b(t)=R(t)−R∗(t)满足

b(t)≤R(t)−R(s)−β(t−s)≤α(t−s)−β(t−s)

接下来，若t−s≥u0，那么可以找到一个时刻t′=s+u0，满足s+1≤t′≤t，使得b(t′)=0。这与s的定义矛盾，因此我们只能假设t−s<u0。

定理1.4.8 假设一条次可加到达曲线为α的流通过一个服务曲线为β的无损节点，β是超可加的，且存在某个u0>0，α(u0)≤β(u0)成立。那么对于任意时刻t，积压R(t)−R∗(t)满足

注意，α为次可加的条件并非强制性的。反之，β为超可加的条件是强制性的，它尤其适用于速率–时延服务曲线。该定理没有涉及忙周期，这与在此不假定严格服务曲线的事实相符。

证明：对于任意时刻t，积压满足

对于s≤t，定义、s′=ku0+s，因此有s≤s′≤t，且

t−u0<s′ （1.11）

由于β为超可加的，因此

R(t)−R(s)≤[R(t)−R(s′)−β(t−s′)]+[R(s′)−R(s)−β(s′−s)]

注意第二项满足

R(s′)−R(s)−β(s′−s)≤k[α(u0)−β(u0)]≤0

因此

R(t)−R(s)≤[R(t)−R(s′)−β(t−s′)]

说明定理成立。

1.5 贪婪整形器

1.5.1 定义

通过漏桶和GCRA的定义，我们介绍了强制执行一般到达曲线的两个设备示例。一般情况下，整形曲线为σ的管制器（policer）是对一条输入流的到达比特数进行计数的设备，并决定哪些比特符合σ的到达曲线；整形曲线为σ的整形器为比特处理设备，它会强制输出σ的到达曲线。贪婪整形器被定义为：只要发送的比特违反约束σ，整形器就在缓冲区中延迟输入的比特；但只要条件允许，这些被延迟的比特会被尽快输出。

对于ATM或互联网综合服务，通过一条连接或一条流发送的流量在网络边界被管制。执行管制是为了确保用户发送的数据不超过连接的合约规定的数据量。超过规定数据量的流要么被直接丢弃，要么在ATM的情况下被标记为低优先级而被丢弃，或者在互联网综合服务的情况下被转为“尽力传输”的流。在被转为“尽力传输”的流的情况下，IPv4网络没有标记机制，因此沿着流的路径，每个路由器都有必要再次执行管制功能。

网络中的管制设备通常是需要进行缓冲的，因此它们属于整形器。通常情况下，整形是必要的，因为缓冲区的输出通常不再与输入端指定的流量合约相符。

1.5.2 贪婪整形器的输入/输出特性

贪婪整形器的主要结论如下。

定理1.5.1（贪婪整形器的输入/输出特性） 设想一个整形曲线为σ的贪婪整形器。假设整形器缓冲区在时刻0为空，并且缓冲区足够大，因此不会丢失数据。那么对于输入流R，输出流R∗由下式表示

其中，为σ的次可加闭包。

证明：首先要回顾的是，若σ是次可加的，且σ(0)=0，则。通常情况下，已知可以用代替σ，而无须更改整形器的定义。因此，不失一般性地，假设。

定理的证明是最小加代数的应用。首先，设想一个虚拟系统，该系统将R作为它的输入，且输出S满足约束条件

这样的系统可以充当缓冲区（第一个方程表明输出来自输入），并且其输出将满足到达曲线σ的约束。然而，这样的系统不一定是贪婪整形器。例如，对于所有的t≥0，存在一个S(t)=0的惰性整形器！为了使该系统成为贪婪整形器，它必须尽快输出比特。对于满足式（1.13）给出的条件的系统，存在一般性的结论。

引理1.5.1（最小加线性系统） 假设σ为良态函数[满足次可加性，且σ(0)=0]。对于某一固定函数R，在满足式（1.13）的所有函数S(t)中，存在一个函数是所有函数的上界，该函数等于R⊗σ。

证明：该引理是第4章一般结果的特例。然而，也可以在此给出一个非常简单的证明，如下所示。

定义S∗=R⊗σ，由于σ为良态函数，因此可以马上知道S∗是满足式（1.13）的系统的解。接下来，假设S′为其他解决方案。由于S′≤R，因此

S′≤S0⊗σ=S∗

因此S∗为最大解。

注意，引理证明了系统[由式（1.13）定义]存在最大解。此外还要注意，在引理中，函数R不必是广义递增的。

接下来，可以用引理来证明R∗=S∗。函数R是广义递增的，因此S∗也是广义增的。显然，R∗是系统[满足式（1.13）]的一个解，因此对于所有t，R∗(t)≤S∗(t)。接下来，如果存在某个t值，使得R∗(t)≠S∗(t)，那么这将与贪婪整形器试图尽早输出比特的条件相矛盾。

可以直接得到以下的推论。

推论1.5.1（贪婪整形器的服务曲线） 设想一个整形曲线为σ的贪婪整形器。假设σ为次可加的，且σ(0)=0。则该系统为流提供等于σ的服务曲线。以这类服务曲线对流进行重整形的例子如图1.14所示。

例：重整形器的缓冲区大小。经常会在网络中引入重整形器，这是因为缓冲区的输出通常不再符合在输入时指定的流量合约。例如，设想一条到达曲线为σ(t)=min{pt+M,rt+b}的流，它经过若干节点，这些节点的服务曲线为β1=βR,T。在若干节点之后放置一个整形曲线为σ的贪婪整形器（如图1.14所示）。整形器的输入（图1.14中的R）的到达曲线为α∗，由命题1.4.2给出。推论1.5.1给出了贪婪整形器服务曲线的性质，因此贪婪整形器所需的缓冲区大小B为α∗与σ的垂直距离v(α∗,σ)。经过代数运算，得到

推论1.5.2（贪婪整形器的缓冲区占用） 设想一个整形曲线为σ的贪婪整形器，假设σ是次可加的，且σ(0)=0。令R(t)为输入函数。则在时刻t，缓冲区占用x(t)为

证明：积压的定义为x(t)=R(t)−R∗(t)，其中R∗为输出。利用定理1.5.1得到

注意，引理1.2.2是该推论的一个特例。

在最小加代数中，如果一个系统的输入/输出特性具有R∗=R⊗β的形式（其中，β不一定是次可加的），则该系统为线性时不变系统。因此，根据定理可以认为贪婪整形器是最小加线性时不变系统。但最小加线性时不变系统不一定是贪婪整形器。例如，具有恒定延迟T的节点，其输入/输出关系为

R∗=R⊗δT

与保证延迟的节点（具有以T为边界的可变延迟节点）相比，其输入/输出关系具有服务曲线的属性，即

R∗≥R⊗δT

本节的剩余部分也将进行类似的说明，即贪婪整形器的输入/输出特性R∗=R⊗σ比推论1.5.1中描述的服务曲线特性强大得多。

1.5.3 贪婪整形器的性质

参考图1.14，在第1.5.2节中，我们已经了解了如何计算贪婪整形器所需的缓冲区大小。接下来，如果沿着网络的传输路径引入贪婪整形器，那么在贪婪整形器上可能会导致一些比特的延迟，因而可能会增加端到端的延迟。然而，事实并非如此，以下结果表明，从全局的角度来看，“贪婪整形器是没有代价的”。

定理1.5.2（重整形不会增加延迟或缓冲需求） 假设一条受到达曲线α约束的流，按顺序输入网络S1和S2。假设在S1和S2之间插入一个整形曲线为σ（σ≥α）的贪婪整形器。定理1.4.2给出的积压界限和延迟界限对于没有整形器的系统和有整形器的系统都是有效的。

条件σ≥α意味着重整形可能只进行了部分的整形。

证明：令βi为Si的服务曲线，定理1.4.1中的积压界限由下式给出

v(α,β1⊗σ⊗β2)=v(α,σ⊗β1⊗β2) （1.15）

这表明如果将整形器放在网络的入口处，就能得到积压界限。显然，这不会引入积压，这表明整个积压不会受整形器的影响。同样的推理也适用于延迟界限。

如果读者比较细心，可能很难同意上一段的内容。的确，这里有一个微妙之处。第1.4节中的界限是紧致的，但是由于同时使用多个界限，因此在本节讨论的情况下不能再保证得到的界限是紧致的。在这一点上，只能说，如果把整形器放在前面，那么为带有整形器的系统计算的界限是相同的。仍然需要证明，对于这样的系统，具有或不具有整形器得到的界限是相同的。有多种证明方法，这里给出一种计算式的方法。该证明依赖于引理1.5.2，如下所示。

引理1.5.2 令α与σ均为良态函数，假设α≤σ。那么对于任意函数β，v(α,σ⊗β)=v(α,β)以及h(α,σ⊗β)=h(α,β)成立。

证明：利用第3.1.11节中的最小加解卷积，有

v(α,σ⊗β)=[α⊘(σ⊗β)](0)

根据定理3.1.12得α⊘(σ⊗β)=(α⊘σ)⊘β。此外，由于σ≥α，因此有α⊘σ≤α⊘α。又因为α为良态函数，所以α⊘α=α，于是

α⊘(σ⊗β)=α⊘β （1.16）

最后v(α,σ⊗β)=v(α,β)。

类似地，h(α,β)=inf{d|(α⊘β)(−d)≤0}，结合式（1.16）得出h(α,σ⊗β)=h(α,β)。

再次参考图1.14，假设将第一个网络元件与贪婪整形器放置在同一节点中。根据定理1.5.2，该组合节点所需的总缓冲区与输出端口没有贪婪整形器时的情况相同。因此，如果可以动态地给第一个网络元件与贪婪整形器分配缓冲区空间，那么贪婪整形器可以不占用任何内存。但是，根据式（1.14），仍需要为贪婪整形器分配一些缓冲区空间。同样，定理1.5.2表明，最坏情况下的延迟也不会额外增加。

然而，相比之下，放置贪婪整形器有着明显的优势。它减少了下一个网络元件准入流的突发度，从而减少了该网络元件中所需的缓冲区空间。更具体地说，对于第1.4.3节中“突发一次性准则”的示例，假设在第一个节点的输出端插入一个整形器，那么第二个节点的输入就具有与第一个节点输入相同的到达曲线，即γr,b而非。因此，节点2上的流量所需的缓冲区大小为b+rT2而不为b+r(T1+T2)。

以下定理阐述了贪婪整形器的另一个物理属性，表明整形不能相互抵消。

定理1.5.3（整形保留到达约束） 假设一条到达曲线为α的流量，通过一个整形曲线为σ的贪婪整形器。假设σ为良态函数，那么输出流量仍受原始到达曲线α的约束。

证明：

R∗=R⊗σ≤(β⊗α)⊗σ

根据条件R≤R⊗α，表明α为一条到达曲线，从而

R∗=R⊗σ⊗α=R∗⊗α

贪婪整形器输出的到达曲线为min{α,σ}，若α也是良态函数，则根据引理1.2.5可知，min{α,σ}的次可加闭包为α⊗σ。

示例（ATM多路复用器） 假设一个ATM交换机接收3条ATM连接，每条连接均受到GCRA(10,0)（周期性连接）的约束。交换机按照尽力工作（work conserving）的方式服务连接，且输出链路的速率为每个时隙1个信元。那么对于聚合输出来说，如何得到一条良态的到达曲线？

假设聚合输入的到达曲线为α=3v10,0，服务器是一个整形曲线为σ=v1,0的贪婪整形器，因此该服务器保留了到达曲线的约束形式。从而，输出流量受到3v10,0⊗v1,0的约束，该约束函数是一个良态函数，我们已经在图1.6中见到过这个约束函数的例子。

1.6 最大服务曲线、可变延迟和固定延迟

1.6.1 最大服务曲线

如果修改第1.3节中服务曲线定义下的不等式，那么可以得到一个被称为最大服务曲线的新概念，该概念可用于计算恒定延迟，或在某些情况下确定延迟和积压之间的关系。

定义1.6.1（最大服务曲线） 设想某系统S和一条流，这条流具有输入和输出函数R和R∗且通过S。当且仅当γ∈F且R∗≤R⊗γ时，S为流提供的最大服务曲线为γ。

注意，上述定义等价于γ是广义递增的，且

R∗(t)≤R(s)+γ(t−s)

对于任意t以及任意s≤t，上述定义也等价于

R∗(t)−R∗(s)≤B(s)+γ(t−s)

其中B(s)表示时刻s处的积压。整形曲线为σ的贪婪整形器可以同时将σ作为服务曲线和最大服务曲线。

通常，最大服务曲线的概念不如服务曲线的概念有影响力。然而，如下列命题所示，对于处理最大速率和恒定传播延迟，最大服务曲线是有用的。另外，第6章将介绍利用最大服务曲线可以找到聚合多路复用的良态边界。

以下命题给出两个特殊情况，其证明是容易的，留给读者证明。

命题1.6.1（最小延迟） 当且仅当无损节点强加的最小虚拟延迟等于T时，该节点提供等于δT的最大服务曲线。

命题1.6.2（输出端的到达约束） 假设无损节点的输出受某一到达曲线σ的约束，那么该节点提供等于σ的最大服务曲线。

与最小服务曲线类似，最大服务曲线可以级联。

定理1.6.1（节点的级联） 假设流量依次通过系统S1和S2，Si为流量提供的最大服务曲线为γi，i=1,2。那么，两个系统的级联为流量提供等于γ1⊗γ2的服务曲线。

证明：该证明可以效仿定理1.4.6的证明。

应用：设想一个最大输出速率等于c，且内部传输延迟等于T的节点。它遵循定理1.6.1以及之前的两个命题，即该节点向任何流量提供的最大服务曲线等于速率–时延函数βc,T(t)=[c(t−T)]+。

最大服务曲线不能使我们得出与（普通）服务曲线一样好的结果。然而，最大服务曲线可以用于减小输出边界。在某些情况下，它们还可以用于获得最小延迟界限。事实上，可以得到以下两个定理。

定理1.6.2（输出流，定理1.4.3的推广） 假设流在到达曲线α的约束下，经过一个提供服务曲线为β和最大服务曲线为γ的系统。那么，输出流受到达曲线α∗=(α⊗γ)⊘β的约束。

证明：与定理1.4.3的证明不同，证明定理1.6.2使用最小加代数更简单。令R和R∗为输入和输出函数，并令R∗的最小到达曲线为R∗⊘R∗。由于R∗≤R⊗γ且R∗≥R⊗β，因此

R∗⊘R∗≤(R⊗γ)⊘(R⊗β)

根据第3章定理3.1.12的规则12，将其应用于f=R⊗γ，g=R和h=β，可以得到

R∗⊘R∗≤{(R⊗γ)⊘R}⊘β

根据“⊗”的交换性和定理3.1.12中的规则13

{(R⊗γ)⊘R}={(γ⊗R)⊘R}≤{γ⊗(R⊘R)}

有

R∗⊘R∗≤{γ⊗(R⊘R)}⊘β≤(γ⊗α)⊘β

定理1.6.3（最小延迟界限） 假设一条在到达曲线α约束下的流量，经过一条提供最大服务曲线γ的系统，令γ(D)=0。那么对于任意t，虚拟延迟d(t)满足d(t)≥D。

证明：由于R∗(t)≤R(t−D)+γ(D)，因此R∗(t)≤R(t−D)。

注意，由于通常期望α⊗γ小于α，因此可以通过最大服务曲线的概念改进输出界限。相反，最小延迟界限仅在最大服务曲线中存在时延部分的情况下才能提供一些可供利用的新信息，这适用于最小延迟的情况，但通常不适用于输出的到达约束的情况。

示例（数值） 再次参考图1.13示例中设定的到达曲线和服务曲线。首先利用定理1.4.3，计算输出到达曲线α∗₀。具体过程如下。

α∗₀=10v25,4⊘β1,8=10v25,4⊘(λ1⊗δ8)

根据第3章定理3.1.12的规则15有

α∗₀=(10v25,4⊘δ8)⊘λ1

(10v25,4⊘δ8)(t)=10v25,4(t+8)=10v25,12(t)，并且直接根据⊘的定义最终可以直接得到α∗₀=v25,12。

接下来，假设我们拥有了更多关于节点的信息。假设节点S1表示两个调度器和一个固定延迟元件的级联，如图1.15所示。每个调度器向聚合流提供服务曲线，其中信元速率R0等于1（单位时隙的信元数），延迟T0等于2个时隙。延迟元件是一条链路，其最大速率等于单位时隙1个信元，且固定传播（propagation）和传输（transmission）延迟等于4个时隙。因此，延迟元件是整形曲线为λ1(t)=t的贪婪整形器和固定延迟元件为δ4的组合。可以验证节点1中3个元素的级联所提供的服务曲线等于β1,2⊗λ1⊗δ4⊗β1,2=β1,8。除此以外，根据延迟元件，节点还为聚合流提供了等于β1,4的最大服务曲线。根据定理1.6.2，输出流受到达曲线α∗₁的约束

α∗₁=(α⊗β1,4)⊘β1,8

该计算与α∗₀的计算类似，并涉及10v25,4⊗λ1的计算，它与图1.6所示的过程类似。最终得到

α∗₁(t)=(10v25,4⊗λ1)(t+4)

从图1.15中可以看出，与在不知道最大服务曲线性质的情况下得到的到达曲线α∗₀的边界相比，到达曲线α∗₁的边界更优。

接下来假设更改节点S1中延迟元件的顺序，并将其作为节点的最后一个元素，将S2作为该结果的节点。那么，由于最小加卷积的交换性，导致界限对延迟元件的顺序不敏感，前文的结论仍然成立。因此，到达曲线α∗₁也可以作为系统S2的输出。然而，在这种情况下，还可以将延迟元件建模为整形器的组合，即整形曲线λ1（对应于每个时隙1个信元的固定速率）加上固定延迟元件（4个时隙的固定延迟）。整形器输入的到达曲线为α⊘β1,4，其中α=10v25,4。因此，根据整形器的特点，其输出受到的约束为

α∗₂(t)=(α⊘β1,4)⊗λ1=10v25,8⊗λ1

由于固定延迟元件不会改变流的特点，因此系统S2输出的到达曲线为α∗₂。图1.15显示，α∗₂给出了比α∗₁更好的边界。

在一般情况下，以下结论通常是正确的：只要能够将网络元件建模为整形器，则这种模型所提供的边界就比最大服务更严格。

图1.15的说明：图1.15(a)中有两个节点S1和S2，它们是提供总服务曲线β1,8的系统的两种可能的实现形式；图1.15(b)描绘出到达曲线α和总服务曲线β1.8；图1.15(c)表示输出的约束。其中仅在使用服务曲线β1,8的情况下得到α∗₀（顶部粗实线）,α∗₁（中间粗虚线）是在假设系统为S1的情况下得到的，α∗₂（底部细实线）是在假设系统为S2的情况下得到的。

1.6.2 积压造成的延迟

一般情况下，无法根据服务曲线框架下的积压来约束延迟的界限，但有一种特殊且很重要的情况除外。

定理1.6.4 假设无损节点为一条流提供的最小服务曲线为β、最大服务曲线为γ，且满足β(t)=γ(t−v)。令f为最大加解卷积，即

那么积压B(t)以及虚拟延迟d(t)满足

f(d(t)−v)≤B(t)

此外，若γ具有超可加性（super-additive），则

β(d(t))≤B(t)

证明：对于某个定值t≥0，有d(t)=inf{Et}，其中集合Et定义为

Et={s≥0:R∗(t+s)≥R(t)}

由于R∗和R是广义递增的，因此Et是一个区间，则有

d(t)=sup{s≥0:R∗(t+s)<R(t)}

假设R∗和R是左连续的，则有

R∗(t+d(t))≤R(t)

对于某个任意值ε，可以找到某个s满足

R∗(t+d(t))≥R(s)+β(t−s+d(t))−ε

根据最大服务曲线的性质，有

R∗(t)−R(s)≤γ(t−s)

联立上面3个表达式，可得

B(t)=R(t)−R∗(t)≥β(t−s+d(t))−γ(t−s)−ε=γ(t−s+d(t)−v)−γ(t−s)−ε

因此有

根据f的定义，后一项为f(d(t)−v)。最后，若γ具有超可加性，那么。

上述定理能够被用于以下的实际情况。

推论1.6.1 假设无损节点为一条流提供的最小服务曲线为β=βr,v、最大服务曲线为γ=βr,v′，其中v′≤v。则积压B(t)和虚拟延迟d(t)满足

证明：利用定理1.6.4可以得出该推论。注意，由于γ是凸函数，因此它是超可加的。

1.6.3 可变延迟与固定延迟

一些网络元件具有固定延迟（传播和传输），而另一些网络元件具有可变延迟（排队）。在许多情况下，分别评估总延迟和延迟的可变部分是很重要的。例如，总延迟对于确定吞吐量和响应时间很重要；可变延迟对于确定播放缓冲区的大小很重要（相关的简单示例，参见第1.1.3节；对于更具一般性的讨论，参见第5章）。在第1.5.2节的结尾已经看到，具有固定延迟的节点可以被建模为最小加线性系统。除此以外，最大服务曲线的概念是区分可变延迟和固定延迟的工具，如下所示。

假设一个由网络元件1,…,I串联而成的网络，每个单元的延迟由固定延迟di和可变延迟组成。假设可变延迟部分提供的服务曲线为βi，固定延迟部分以同时作为服务曲线和最大服务曲线。定义β=β1⊗…⊗βI，网络提供的端到端服务曲线为，且端到端最大服务曲线为。假设输入流受到某到达曲线α的约束。根据定理1.4.2和定理1.6.3，端到端延迟d(t)满足

通过简单的观察可以发现，因此端到端延迟满足

0≤d(t)−(d1+…+dI)≤h(α,β)

在上述方程中，d1+…+dI是延迟的固定部分，h(α,β)是延迟的可变部分。因此，可以忽略固定部分的计算，只计算延迟的可变部分。

类似地，输出的到达曲线约束是

因此，计算输出界限时，可以忽略固定延迟。

对于积压，读者可以很容易地确定，但不能忽略固定延迟。总结如下。

命题1.6.3 为了计算积压和固定延迟界限，通过在服务曲线中引入δT函数，来对固定或可变延迟进行建模。由于“⊗”满足交换律，延迟可以沿串联的缓冲区以任意顺序插入，而不会改变延迟界限；对于可变延迟界限的计算或输出到达约束的计算，可以忽略固定延迟。

1.7 处理变长数据包

本章中的所有结果都直接应用于使用离散时间模型的ATM系统。变长的数据包（通常是IP服务的情况）还有一些额外的微妙之处可供讨论。接下来，我们将对其进行详细研究。本节的主要研究内容包括打包器（packetizer）的定义，以及打包器对于延迟、突发度和积压界限的影响；并且在变长数据包的情况下，重新讨论贪婪整形器的概念。在本节的其余部分中，均假设时间是连续的。

本节中，考虑数据包到达时刻Ti≥0的广义递增序列，并假设对于任意t，集合{i:Ti≤t}是有限的。

1.7.1 变长数据包引入不规则性的示例

本小节提供的问题来自这样一个事实：真正的分组交换系统通常输出整个数据包，而非连续的数据流。设想图1.16所示的例子，它给出一个恒定比特率为c的通道（trunk）输出，接收不同大小的数据包序列作为输入。令li、Ti分别表示第i（i=1,2…）个数据包的长度（比特）和到达时刻，那么输入函数为

在上面的方程中，1_{expr}为指示函数（indicator function）。若expr为真，则1_{expr} 等于1；否则1_{expr}等于0。与大多数系统一样，假设只观察到通道输出的整个数据包，如图1.16所示的R′(t)，它通过打包操作逐比特输出R∗得到[图1.16中，R(t)表示输入，R∗(t)表示贪婪整形器的输出，R′(t)表示最终输出，即打包器的输出]。根据第1.5节已知的R∗=R⊗λr，逐比特输出R∗是很好理解的。然而，打包器的作用是什么？第1.4节和第1.5节中的结论是否仍然成立？

图1.16的说明：一条数据包通道具有恒定比特率约束，且用于传输变长的数据包，可以被看作一个贪婪整形器和一个打包器的级联。该通道的输入是R(t)，贪婪整形器的输出是R∗(t)，最终的输出是打包器的输出，记为R′(t)。

当然，应该存在一些修正。例如，图1.16 中的逐比特输出R∗是整形曲线为λc的贪婪整形器的输出，因此其到达曲线为λc，但显然这对于R′并不成立。更糟糕的是，已知贪婪整形器会保持到达约束，因此如果R是σ-平滑的，那么R∗也是；然而，这对于R′也不成立。设想以下示例[10]，假设σ(t)=lmax+rt，且r<c；此外，假设输入流量R(t)在时刻T1=0时发送大小为l1=lmax的第一个数据包，且在时刻时发送大小为l2的第二个数据包。因此，R的确是σ-平滑的。第一个数据包的发送时刻为。假设第二个数据包的l2很小，具体而言，，那么两个数据包背靠背发送，第二个数据包的发送时刻为。此时，间距T′₂−T′₁小于，因此第二个数据包不符合要求。换言之，R′不是σ-平滑的。注意，如果所有数据包的大小均相同，则无法使用此示例。

在本节中，下面这个示例的情况将非常普遍：对变长数据包进行打包确实会引入一些额外的不规则性。然而，我们能够对其进行量化，并且将看到不规则性很小（但可能大于数据包长度的量级），大部分结果参见参考文献[11]。

1.7.2 打包器

首先需要一些定义。

定义1.7.1（累积数据包长度） 累积数据包长度的序列L是一个广义递增序列(L(0)=0,L(1),L(2),…)，使得

这个序列是有限的。

在本章中，将L(n)−L(n−1)解释为第n个数据包的长度。接下来，引入一种新的构造块[3]。

定义1.7.2 [函数PL(x)[3]] 设想一个累积数据包长度的序列L，其中L(0)=0。对于任意实数x，定义

图1.17说明了该定义。直观地讲，PL(x)是完全包含在x中的最大累积数据包长度，函数PL(x)是右连续的。如果R(t)是右连续的，那么PL(R(t))也是右连续的。例如，如果所有数据包都具有单位长度，则L(n)=n并且对于x>0，PL(x)=x。PL(x)的一个等价表征为

PL(x)=L(n)⇔L(n)≤x<L(n+1) （1.20）

定义1.7.3（打包器[3,12,13]） 设想一个累积数据包长度的序列L。L-打包器是将输入R(t)转换为PL(R(t))的系统。

对于图1.16中的例子，有R′(t)=PL(R∗(t))，因此系统可以解释为贪婪整形器和打包器的级联。

那么可以立即得到以下的不等式

x−lmax<PL(x)≤x （1.21）

定义1.7.4 若PL(R(t))=R(t)对所有t成立，则流R(t)是可“L-打包的”（L-packetized）。

以下性质的证明很容易，留给读者证明。

● （打包器的保序性）若x≤y，则对于所有x,y∈R有PL(x)≤PL(y)。

● （PL的幂等性）PL(PL(x))=PL(x)对于所有x∈R成立。

● （打包器的最优性）可以按照第1.5节对贪婪整形器表征的类似方式来描述打包器，对于所有满足下式的流x(t)，存在一个上界，即PL(R(t))。

对于最后一项性质的证明类似于引理1.5.1，它依赖于PL(x)的幂等性。

接下来，研究打包器对第1.4节中3种界限的影响。首先介绍一个定义。

定义 1.7.5（逐数据包的延迟） 设想一个系统，它具有L-打包的输入和输出，令Ti、T′_i为第i个数据包的到达和离去时刻。假设没有数据包丢失，那么每个数据包的延迟为。

本节的主要结论是以下定理，如图1.18所示。

定理1.7.1（打包器的影响） 设想一个（逐比特）系统，该系统具有L-打包的输入R和逐比特输出R∗，然后对R∗进行L-打包，最终生成打包输出R′。假设两个系统都是先入先出且无损的，将该组合系统（combined system）称为R映射到R′的系统。

1.组合系统的每个数据包的延迟是逐比特系统的最大虚拟延迟；

2.令B∗为逐比特系统的最大积压，B′为组合系统的最大积压。则有

B∗≤B′≤B∗+lmax

3.假设逐比特系统提供给流的最大服务曲线为γ、最小服务曲线为β。那么，组合系统提供给流的最大服务曲线为γ、最小服务曲线β′为

β′(t)=[β(t)−lmax]+

4.若某条流S(t)的到达曲线为α(t)，那么PL(S(t))的到达曲线为α(t)+lmax 1_{t>0}。

下面将给出定理1.7.1的证明。在此之前，先讨论其含义。定理中的第1条表示将打包器附加到节点上不会增加该节点的数据包延迟。然而，后文将会证明，打包会增加端到端的延迟。

再次考虑第1.7.1节中的示例，结合图1.16就会发现，打包增加了积压（或者所需的缓冲），如第2条所示。第4条表明，最终输出R′的到达曲线为σ′(t)=σ(t)+lmax 1_{t>0}，这与第1.7.1节中观察的一致：即使R∗是σ-平滑的，R′也不是σ-平滑的。我们将在第1.7.4节中看到存在一种比“打包贪婪整形器”（Packetized Greedy Shaper）的概念更强的结果。

定理的第3条是本节中最重要的结论，表明打包操作削弱了服务曲线的及时性保证，使之拖延了传输一个最大长度的数据包所需的时间。例如，若系统提供一条速率为R的速率–时延服务曲线，则附加到系统的打包器会将延迟增加。另外参考图1.16中的示例，将通道（trunk）和打包器组合在一起对系统进行建模。

● 最小服务曲线为。

● 最大服务曲线为λc。

定理1.7.1的证明：

第1条的证明：对于满足Ti≤t<Ti+1的t，有R(t)=L(i)，因此

又有

d(Ti)=T′_i−Ti

将两个等式结合可知

第2条的证明：可以由式（1.21）直接得出。

第3条的证明：最大服务曲线γ的结果可以由式（1.21）直接得到。接下来，考虑最小服务曲线属性。

对于某一时刻t，通过定义i₀。对于1≤i≤i₀以及Ti−1≤s<T₁，存在R(s)=R(Ti−1)和广义增函数β，因此

其中βr是β的右极限（相应地，Rl是R的左极限）。类似地，

由于β(0)=0，因此情况1：存在某个i≤i0，使得(R⊗β)(t)=Rl(Ti)+βr(t−Ti)；或情况2：(R⊗β)(t)=R(t)。

对于情况1，假设R∗(t)≥(R⊗β)(t)，因而

R′(t)≥R∗(t)−lmax≥Rl(Ti)+βr(t−Ti)−lmax

另一方面，由于R∗(t)≥Rl(Ti)=R(Ti−1)，且R是L-打包的，因此有

R′(t)≥Rl(Ti)

两者结合可知

R′(t)≥max{Rl(Ti),Rl(Ti)+βr(t−Ti)−lmax}

=Rl(Ti)+max{βr(t−Ti)−lmax,0}

=Rl(Ti)+β′_r(t−Tj)

对于任意定值ε>0，通过右极限的定义，能够找到某个s∈(Ti−1,Ti)，使得β(t−s)≤βr(t−Ti)+ε。又由于R(s)=Rl(Ti)，因此

R′(t)≥R(s)+β(t−s)−ε≥(R⊗β′)(t)−ε

上式对于所有ε>0均成立，因此R′(t)≥(R⊗β′)(t)，这证明服务曲线属性对于情况1成立。对于情况2的证明是显而易见的。

第4条的证明可以由式（1.21）直接得出。

例：GPS节点的级联 设想一个保证速率（Guaranteed Rate,GR）为R（参见第1.3.1节）的理论GPS节点与L-打包器的级联，假设该系统接收变长的数据包流。这里构建了一个理论上的节点，该节点可以作为一个GPS节点，但被限制只能传送整个数据包。这样的假设并不现实，第2章将介绍更符合真实情况的GPS节点，但这里假设的例子足以说明打包器的一个重要作用。

应用定理1.7.1，可以发现该节点提供了一条速率–时延服务曲线。接下来，级联m个这样的GPS节点，如图1.19所示。那么，端到端的服务曲线为速率–时延函数βR,T，其中

从该例子中可以看到，打包器引入的额外延迟的确与一个数据包的长度有关。然而，其效果还要与跳数相乘。

对于端到端延迟界限的计算，需要考虑定理1.7.1，也就是可以忽略最后一个打包器。因此，端到端延迟界限可以根据端到端路径上所提供的速率–时延服务曲线得到，其中

例如，如果原始输入流被速率为r、漏桶的大小为b的漏桶约束，如果r≤R，则端到端延迟界限为

敏锐的读者很容易发现该界限为最坏情况。这表明，在解释定理1.7.1时应该注意，打包器仅在最后一跳才没有增加延迟。可以这样理解该问题，打包器延迟了数据包前面的比特，进而对下游节点的处理造成延迟，该效果在式（1.23）中得以体现。

说明1.7.1 打包器不会增加其所在节点的最大延迟；然而，它们通常会增加端到端延迟。

第2章将介绍，很多实际的调度器都可以建模为一个提供服务曲线保证的节点和打包器的级联，后文将给出式（1.23）的实际推广。

1.7.3 贪婪整形器和打包器之间的关系

之前已经看到，在贪婪整形器上附加一个打包器会削弱输出的到达曲线。然而，有一种情况并非如此，这种情况对于第1.7.4节的结论很重要，其本身也有实际的应用。图1.20说明了定理1.7.2。

定理1.7.2 设想一个累积数据包长度的序列L，并令PL(x)为L-打包器，如果以算子形式表示，记为P_L（参见定义4.1.4）。另外考虑良态函数σ，并假设存在一个次可加函数σ0，以及l≥lmax，使得

σ(t)=σ0(t)+l1_{t>0} （1.24）

称Cσ是整形曲线为σ的贪婪整形器，则对于任何输入，合成（composition）[6] P_L◦Cσ◦P_L的输出是σ-平滑的。

在实际情况中，该定理的用法如下。设想一条L-打包的流，经过一个整形曲线为σ的贪婪整形器，并对输出进行打包。那么，得到的结果是σ-平滑的[假设σ满足定理中式（1.24）的条件]。

注意，一般来说，即使σ 满足定理中的条件，P_L◦Cσ的输出也不是L-打包的（感兴趣的读者可以很容易地找到一个反例）。同样，如果P_L◦Cσ的输入不是L-打包的，那么通常情况下输出也不是σ-平滑的。

在式（1.24）的条件下，该定理也可以这样表述

P_L◦Cσ◦P_L=Cσ◦P_L◦Cσ◦P_L

因为上述两个算子总是产生相同的输出。

式（1.24）中条件的讨论 若σ为凹函数，且σr(0)≥lmax，则在实际中式（1.24）是成立的，其中为σ在0处的右极限。例如，如果整形曲线是由漏桶的级联定义的，那么所有漏桶的深度至少等于最大数据包的长度。

这也为解释图1.16的示例提供了一些启发：出现问题是由于整形曲线λc不满足条件。

敏锐的读者也许会问，式（1.24）成立的充分条件是否为σ是次可加的，且σr(0)≥lmax。然而，很遗憾答案是否定的。例如，设想一个阶梯函数σ=lmax vT，有σr(0)=lmax，但如果试图将σ改写为σ(t)=σ0(t)+l1_{t>0}，则对于t∈(0,T]，必须有l=lmax并且σ0(t)=0；若强制认为σ0为次可加的，则意味着σ0=0，与式（1.24）并不相符[7]。

证明：使用与图1.20中相同的符号，以证明R(1)是σ-平滑的。首先有R∗=R⊗σ，接下来考虑满足s<t的任意s和t。根据最小加卷积的定义，对于任意ε>0，存在某个u≤s使得

(R⊗σ)(s)≥R(u)+σ(s−u)−ε （1.25）

接下来，考虑ε>0的集合E，以找到满足上述公式的u<s。可能有两种情况：0是E[8]的累积点（情况1），或0不是E的累积点（情况2）。

对于情况1：存在一个序列(εn,sn)，sn<s，使得

以及

(R⊗σ)(s)≥R(sn)+σ(s−sn)−εn

由于sn≤t，因此

(R⊗σ)(t)≤R(sn)+σ(t−sn)

结合上面两个不等式，有

(R⊗σ)(t)−(R⊗σ)(s)≤σ(t−sn)−σ(s−sn)+εn

由于t−sn>0且s−sn>0，因此

σ(t−sn)−σ(s−sn)=σ0(t−sn)−σ0(s−sn)

由于已经假设σ0为次可加的，又有t≥s，因此

σ0(t−sn)−σ0(s−sn)≤σ0(t−s)

前面已经展示了，对于所有n

(R⊗σ)(t)−(R⊗σ)(s)≤σ0(t−s)+εn

因此

(R⊗σ)(t)−(R⊗σ)(s)≤σ0(t−s)

根据式（1.21），有

R(1)(t)−R(1)(s)≤σ0(t−s)+lmax≤σ(t−s)

至此情况1证毕。

对于情况2：存在某个满足0<ε<ε0的值ε0，对于式（1.25）必须取u=s，那么有

(R⊗σ)(s)=R(s)

由于假设R为L-打包的，因此

R(1)(s)=PL((R⊗σ)(s))=PL(R(s))=R(s)=(R⊗σ)(s)

从而

R(1)(t)−R(1)(s)=PL((R⊗σ)(t))−(R⊗σ)(s)

≤(R⊗σ)(t)−(R⊗σ)(s)

由于R⊗σ的到达曲线为σ，因此

R(1)(t)−R(1)(s)≤σ(t−s)

至此情况2证毕。

例：基于虚拟完成时间的缓冲漏桶控制器 定理1.7.2给出了一个基于数据包整形器的实际应用。假设构建一个系统，以确保数据包流满足某个凹的分段线性的到达曲线（当然也是L-打包的），该系统可以通过按比特操作的缓冲漏桶控制器和打包器的级联实现。计算出数据包最后1 bit经过逐比特漏桶控制器的输出时间（等于完成时间），并在此完成时间立即释放整个数据包。若每个漏桶的大小至少等于最大数据包长度，那么通过定理1.7.2可知，最终的输出满足漏桶约束。

反例 若到达曲线是非凹函数，那么可以找到这样一条到达曲线σ，使t>0时，满足σ(t)≥lmax，但不满足式（1.24）。在这种情况下，定理1.7.2的结论就可能不再成立。图1.21给出这样一个例子，当σ为阶梯函数时，输出R(1)不是σ-平滑的。

图1.21的说明：10个数据包在时刻t=0突发到达，每个数据包的长度等于10个数据单位，并且σ=25v1。贪婪整形器在时刻0和时刻1发出25个数据单位，使打包器在时刻1产生一次3个数据包的突发，且这样R(1)不是σ-平滑的。

1.7.4 打包贪婪整形器

回顾图1.16的示例中所提出的问题，对打包贪婪整形器的问题进行更本质的研究。这里不像前文对贪婪整形器和打包器进行级联，而是给出与第1.5节一致的定义。

定义1.7.6（打包贪婪整形器） 根据式（1.18）的定义，设想一组输入的数据包序列R(t)。令L为累积数据包长度，系统为具有整形曲线σ的打包整形器，该系统的输出被强制设定为L-打包的，且具有σ作为到达曲线。这里将打包贪婪整形器称为打包整形器，该整形器的工作原理是每当发送的数据包违反约束σ时，都会延迟缓冲区中的输入数据包；但只要条件允许，这些被延迟的数据包会被尽快输出。

例：基于桶补充的缓冲漏桶控制器  的情况可以通过观察一组（M个）漏桶的控制器来实现，其中第m个漏桶的容量为bm，并以恒定速率rm流出。当数据包i被释放时，每个漏桶都会接收li单位的流体（li为数据包i的大小）。一旦漏桶m中的液位允许，即所有m的液位降到bm−li以下，那么该数据包就会被释放。至此，就基于“桶补充”(bucket replenishment)定义了一种缓冲漏桶控制器。显然，输出的到达曲线为σ，且是L-打包的，并且要求输出尽可能早地发送数据包。因此，缓冲漏桶控制器实现了打包贪婪整形器。注意，该实现（以下称其为前者）不同于第1.7.3节中介绍的基于虚拟完成时间的缓冲漏桶控制器（以下称其为后者）。对于后者，例如在只有漏桶m充满的时间段内，虚拟数据包分段释放速率为rm，漏桶m保持充满状态，然后（虚拟）分段在打包器中重新组装；而对于前者，如果某个漏桶充满，则控制器等待的时间至少要等于当前数据包长度的缓冲容量被输出所需的时间。因此，两个系统中流体的液位是不同的，前者是一个上限。而在推论1.7.1中，可以看到这两种实现是等价的。

该示例中，若漏桶的容量小于最大数据包的长度，则永远不可能输出数据包：所有数据包都滞留在缓冲区中，且输出。

命题1.7.1 若σr(0)<lmax，则打包贪婪整形器将一直阻塞所有数据包。因此，在本节中，假设t>0时σ(t)≥lmax恒成立。

对于实际情况，必须假设到达曲线σ在原点处的不连续性的阶跃大小至少等于一个最大数据包长度。

对两种情况进行比较，一种是打包贪婪整形器，另一种是由整形曲线为σ的贪婪整形器与一个打包器的级联，从图1.16的示例可知，后者输出的到达曲线为σ′(t)=σ(t)+lmax 1_{t>0}，而非σ。那么，级联是否实现了整形曲线为σ′的打包贪婪整形器呢？在给出一般性答案之前，先给出定理1.7.2的一个普遍性结论。

定理1.7.3（打包贪婪整形器的实现） 设想一个累积数据包长度的序列L和一个良态函数σ，假设σ满足式（1.24）的条件，且只有输入是L-打包的。那么打包贪婪整形器的L和σ可以根据整形曲线为σ的流体整形器和L-打包器的级联实现。通过逐比特的流体整形器和打包器的级联如图1.22所示。

图1.22的说明：假设式（1.24）成立，打包贪婪整形器可以通过逐比特的流体整形器和打包器的级联实现。实际上，这意味着可以通过计算虚拟的流体系统的完成时间，并在其完成时间内释放数据包，来实现打包贪婪整形器。

证明：令R(t)为打包输入，逐比特的流体整形器和打包器的级联的输出为R(1)(t)=PL(R⊗σ)(t)；令为打包贪婪整形器的输出。由于有，因此有以及

但由于是σ-平滑的，因此；且由于是L-打包的，因此 。前一个不等式可以改写为。相反，根据定理1.7.2，R(1)也是σ-平滑的，且为L-打包的。打包贪婪整形器的定义意味着成立（证明参见引理1.7.1），因此有。

由此可见，特别是当定理中的条件满足σ为凹函数且σr(0)≥lmax时（例如，如果整形曲线是由漏桶的级联定义的），所有漏桶的大小至少与最大数据包的大小相同。那么有以下推论。

推论1.7.1 对于L-打包的输入，基于桶补充和虚拟完成时间的缓冲漏桶控制器的实现是等价的。

如果放宽式（1.24）的条件，则打包贪婪整形器的构造会更加复杂。

定理1.7.4（打包贪婪整形器的I/O特征） 设想一个整形曲线为σ和累积数据包长度为L的打包贪婪整形器，假设σ是良态函数。那么打包贪婪整形器的输出为

其中R(1)(t)=PL((σ⊗R)(t))，且当i≥2时，R(i)(t)=PL((σ⊗R(i−1)(t))。

图1.23描述了该定理，并给出一个示例以显示输出的迭代构造过程。注意，此示例的整形曲线不满足式（1.24）。否则，从定理1.7.3可知迭代将在第一步停止，即。另外，还可以检查如下例子：若σ=λr（因此满足命题1.7.1的条件），则式（1.26）的结果为0。

图1.23的说明：图1.23左侧为贪婪整形器，右侧为输出的例子。图中的数据与图1.21中的相同。

证明：该证明是引理1.7.1的直接应用（引理本身是第4.3节通用方法的应用）。

引理1.7.1 设想一个累积数据包长度的序列L和一个良态函数σ。所有流量x(t)满足

那么存在一条流量是所有流量的上界，其由式（1.26）给出。

证明：该引理是定理4.3.1的直接应用，如第4.3.2节所述。然而，为了本章内容的完整，这里给出另一种直接而简短的证明。

若x为一个解，那么可以通过对i的归纳来直接证明x(t)≤R(i)(t)，因而。接下来，最困难的部分是证明确实为一个解。这需要证明式（1.27）中的3个条件成立。首先，R(1)≤R(t)，并通过对i进行归纳，对于所有i，R(i)≤R成立，因此有。

其次，考虑某个定值t，对于所有i≥1，R(i)(t)是L-打包的。令L(n0):=R(1)(t)。由于R(i)(t)≤R(1)(t)，因此R(i)(t)属于集合

{L(0),L(1),L(2),…,L(n0)}

这是一个有限集。因此，该集合元素的下界一定是该集合元素之一L(k)，k≤n0。这表明是L-打包的，且在任意时刻t上都是成立的。

最后，对于所有i

因此有

通过固定函数的卷积是上半连续的，也就意味着

这是第4章中所有最小加算子的一般性结果，基本证明如下。

因此

即满足了第3个条件。注意，是广义递增的。

打包贪婪整形器是否能够保持到达约束？图1.24给出了一个反例，即一条变长数据包流，在经过一个打包贪婪整形器之后，失去了其初始到达曲线的约束。但是，如果到达曲线是由漏桶定义的，就可以得到肯定的结果。

图1.24的说明：输入流R由3个长度为10个数据单位的数据包以及一个长度为5个数据单位的数据包组成，数据包之间的间隔为1个时间单位。它是α-平滑的，且α=10v1,0。流量是打包贪婪整形器的输出，σ=25v3,0。输出在时刻3具有15个数据单位数据包的突发度。它是σ-平滑的，但不是α-平滑的。

定理1.7.5（凹到达约束的守恒） 假设一条具有到达曲线α的L-打包的流量，它被输入具有一个累积数据包长度为L、整形曲线为σ的打包贪婪整形器。假设α和σ是凹函数，且αr(0)≥lmax、σr(0)≥lmax。那么，输出的流量仍然受到原到达曲线α的约束。

证明：由于σ满足式（1.24），根据定理1.7.3，。由于R是“α-平滑”的，因此不会被具有整形曲线α的逐比特贪婪整形器所修改，从而有R=α⊗R。将上述两式结合，并根据⊗的结合律，给出。根据假设，σ⊗α=min{σ,α}（参见定理3.1.6），因此σ⊗α满足式（1.24）。根据定理1.7.2，是“σ⊗α-平滑”的，因此也是α-平滑的。

整形器的串联分解

定理1.7.6 设想M个打包贪婪整形器串联，假设第m个整形器的整形曲线σm为凹函数，且σmr(0)≥lmax。对于L-打包输入，其串联等价于整形曲线为的打包贪婪整形器。

证明：这里仅对M=2的情况进行证明，但很容易扩展到M值更大的情况。令R(t)为打包输入，R′(t)为串联整形器的输出，是具有输入为R(t)的打包贪婪整形器的输出。

首先，根据定理1.7.3，有

R′=PL(σ2⊗PL(σ1⊗R))

对于所有m，满足σm≥σ，因此

R′≥PL(σ⊗PL(σ⊗R))

同样，再利用定理1.7.3，得到。此外，为L-打包的且是σ-光滑的，因此和，于是有

其次，R′是L-打包的，根据定理1.7.5，R′是σ-平滑的。因此，其串联是一个打包整形器（可能不是贪婪的）。由于R(t)是打包贪婪整形器的输出，因此一定满足。再结合式（1.28），至此证毕。

由此可知，具有整形曲线的整形器，其中对于满足bm≥lmax的所有m，可以通过M个单独的漏桶以任意顺序串联来实现。此外，根据推论 1.7.1，每个漏桶的个体可以独立地基于完成时间或桶补充规则运行。

如果不满足定理中的条件，则上述结论可能不成立。事实上，对于图1.24中的示例，具有曲线α和σ的打包贪婪整形器的串联并不具备α-平滑输出，因此它不能等价于具有曲线min{α,σ}的打包贪婪整形器。

第1.5节中提到的其他整形器属性通常都是不成立的。对于满足式（1.24）的整形曲线，当引入一个打包贪婪整形器时，需要根据定理1.7.1来计算端到端的服务曲线。

1.8 无损有效带宽和等效容量

1.8.1 流的有效带宽

利用本章的结论来为某条流定义一个函数，称为有效带宽（effective band-width）。该函数表明流所需的比特率。更精确地说，设想一条具有累积函数R的流，对于固定但任意的延迟D，将流的有效带宽eD(R)定义为：尽力工作模式下，用于流服务所需的比特率，使其虚拟延迟小于等于D。

命题1.8.1 流的有效带宽定义如下

对于到达曲线α，将有效带宽eD(α)定义为贪婪流量R=α的有效带宽。通过对式（1.29）的简单变换，可得出以下命题。

命题1.8.2 良态到达曲线的有效带宽定义如下

谨慎的读者可能会发现流R的有效带宽，也是其最小到达曲线R⊘R的有效带宽。例如，对于一条T-SPEC(p,M,r,b)约束的VBR流，其有效带宽是r与图1.25(a)中斜线(A1 A0)和(QA1)斜率的最大值。因此，有效宽带等于

图1.25的说明：图1.25(a)为VBR流，计算它的有效带宽。例如r=20个数据包/s，M=10个数据包，p=200个数据包/s，b=26个数据包[见图1.25(b)]。

假设α是次可加的。定义可持续速率，以及峰值速率。那么对于所有D，有m≤eD(α)≤p。此外，若α为凹函数，则有。若α是可微分的，则e(D)为到达曲线切线的斜率，从时间轴t=−D时刻绘制（见图1.26）。也可以直接根据式（1.29）中的定义得出

换言之，聚合流的有效带宽小于或等于各流有效带宽之和。若流的到达曲线都相同，则聚合流的有效带宽为I×eD(α1)。这里提到的聚合流与各条到达曲线的关系体现在“有效带宽”这一术语中。是缓冲增益，它告诉我们通过在流之间共享缓冲区，可以节省多少容量。

1.8.2 等效容量

如果将延迟约束替换为不超过固定缓冲区大小的要求，也会得到类似的结果。实际上，若C≥fB(R)，则具有恒定速率C的队列可保证流量R的最大积压为B（以bit为单位），即

类似地，对于一个良态函数α，有

将fB(α)称为等效容量，类似于参考文献[14]中的定义。与有效带宽类似，假设缓冲区也加在一起，异构混合流量的等效容量小于或等于各单独流量的等效容量之和。换言之，。图1.26给出了图形解释。

例如，对于一条T-SPEC(p,M,r,b)流，使用上述同样的方法，可得出以下等效容量

直接的计算结果表明fb(γr,b)=r。换言之，如果为一条受仿射函数γr,b约束的流分配一定的容量，该容量等于其可持续速率r，则一个等于这条流突发容限b的缓冲区就足以确保这条流无损运行。

接下来，考虑将一些符合流量规范T-SPEC(Mi,pi,ri,bi)的IntServ流（或VBR连接）混合起来，这些流聚合为一条流。如果为这条聚合流分配的速率为，该速率等于聚合流中所有流的可持续速率之和，那么缓冲区的需求为突发容限之和，无须再考虑峰值速率等其他参数。反之，式（1.35）也说明分配比突发容限更多的缓冲没有意义：若B>b，此时等效容量仍然为r。

上述内容说明，通过分配大于可持续速率的速率来减少所需的缓冲或延迟是可行的。在第2.2节中，描述了如何使用资源预留协议（Resource Reservation Protocol,RSVP）之类的协议来实现该操作。请注意，式（1.29）、式（1.33）可单独或一起用于根据测量的到达曲线估算流所需的容量。可将它们视为流函数R上的低通滤波器。

1.8.3 示例：FIFO多路复用器的接受域

假设由T-SPEC(Mi,pi,ri,bi)形式的流量规范定义两种类型的流，即类型1（即i=1）和类型2（即i=2），设想某个节点复用类型1的n1条流和类型2的n2条流，该节点具有恒定的输出速率C。接下来想获知该节点可以接受多少流。

若流被接受的唯一条件是所有流的延迟都受到某个值D的限制，那么(n1,n2)的可接受集由下式定义

eD(n1α1+n2α2)≤C

可以利用与式（1.31）的推导相同的凸参数，并将其应用于函数n1α1+n2α2。定义，且假设θ1≤θ2，则结果为

直接从前面的方程式得出可行集(n1,n2)，这要考虑两类到达曲线中凸起的角点所对应的参数（取值如表1.3所示）。如果考虑另一种情况，即接受条件取决于缓冲区的容量B，感兴趣的读者可以计算其等效容量。

注：① 以每秒发送的数据包个数计量；② 以数据包个数计量。

表1.3的说明：最大延迟设为D。表中列出了1型流和2型流的参数以及θi的结果。

回顾式（1.32），可以更一般地说，有效带宽是函数α的凸函数，即

eD(aα1+(1−a)α2)≤aeD(α1)+(1−a)eD(α2)

对于所有a∈[0,1]，等效容量函数亦是如此。

接下来，考虑某种请求（call）的接受准则，该准则要么单纯地受到延迟限制的约束，要么单纯地受到缓冲区最大容量的约束，要么兼有上述两种约束。假设I种连接的类型，并定义接受域A为满足接受准则的一组值(n1,…,nI)，其中ni是类型i的连接数。从有效带宽和等效容量函数的凸属性可以得出，接受域A是凸的。第9章将它与一些具有正丢包概率的系统的接受域进行比较。

可持续速率分配 如果读者仅对本书的结论感兴趣，可以重新考虑之前的解决方案，并仅考虑连接混合的可持续速率。聚合流受到α(s)=b+rs的约束，，且。定理1.4.1表明，只要C≥r，最大聚合缓冲区的占用量就由b限制。换言之，只要总缓冲区等于突发度，那么分配可持续速率就可以保证无损操作。

在更一般的设置下，假设聚合流的最小到达曲线为α，且假设参数r和b满足

因此，突发度为b的可持续速率r是一个紧致的界限。能够很容易地说明，若分配速率为C=r，那么最大的缓冲区占用为b。

接下来，考虑多路复用多个VBR连接的情况。如果没有可用的缓冲区，则必须进行无损操作来分配峰值速率的总和。反之，使用大小为b的缓冲区可以仅分配可持续速率。这就是所谓的缓冲增益（buffering gain），即通过添加一些缓冲获得峰值速率上的增益。缓冲增益是以增加延迟为代价的，这一结论易从定理1.4.2证明。

1.9 定理1.4.5的证明

步骤1：设想一个固定时刻t0，并假设在该步骤中，存在一个时刻u0达到α⊘β定义中的最大值。构造输入和输出函数R和R∗，使R受到α的约束，系统(R,R∗)满足因果性，且α∗(t0)=(R∗⊘R∗)(t0)，R和R∗由下式给出

很容易看出，定理1.4.5的证明类似于定理1.4.4的证明，R和R∗均为广义递增的，那么R∗≤R，且β为流的服务曲线，因此

R∗(u0+t0)−R∗(u0)=α(u0+t0)−R∗(u0)≥α(u0+t0)−β(u0)=α∗(t0)

证明定理1.4.5的步骤1如图1.27所示，系统在t0处获得输出边界。

步骤2：接下来，设想一个时间序列t0,t1,…,tn,…（不必一定是增序列）。假设在此步骤中，对于所有n，都存在一个值un达到(α⊘β)(tn)定义的上确界。证明存在函数R和R∗，使得R受到α的约束，系统(R,R∗)满足因果性，有β作为服务曲线，且对于所有n≥0，α∗(tn)=(R∗⊘R∗)(tn)。

通过对一组递增区间[0,s0],[0,s1],…,[0,sn],…进行归纳，构建R和R∗。归纳性质是：限定于时间间隔[0,sn]的系统满足因果性，将α作为输入到达曲线，β作为服务曲线，且对于i≤n满足α∗(ti)=(R∗⊘R∗)(ti)。

第一个间隔由s0=u0+t0定义；R和R∗根据步骤1定义在区间[0,s0]。显然，归纳性质对于n=0成立。假设在区间[0,sn]上构建了系统。接下来，定义sn+1=sn+un+tn+δn+1，选择δn+1使下式成立：对于所有s≥0，有

α(s+δn+1)−α(s)≥R(sn) （1.36）

根据定理的最后一个条件来看，上式是可能成立的。那么系统在区间(sn,sn+1]的定义为

证明定理1.4.5的步骤2如图1.28所示，系统在所有tn，n∈N处获得输出边界。

接下来，证明在区间[0,sn+1]上定义的系统满足到达曲线的约束。考虑R(t)−R(v)，其中t,v∈[0,sn+1]。若同时满足t≤sn且v≤sn，或t>sn且v>sn，则根据构造和归纳的性质，到达曲线的性质保持不变。因此可以假设t>sn且v≤sn，其实可以假设t≥sn+δn+1，因为如果不在这种假设条件下，该属性是显然成立的，无须证明。令t=sn+δn+1+s，有

R(t)−R(v)=R(sn+δn+1+s)−R(v)=R(sn)+α(s)−R(v)≤R(sn)+α(s)

根据式（1.36）有

R(sn)+α(s)≤α(s+δn+1)≤α(s+δn+1+sn−v)=α(t−v)

从这里可以看出到达曲线的特性。

通过使用与步骤1中相同的参数，可以很容易证明系统满足因果性，服务曲线为β，且满足

R∗(un+1+tn+1)−R∗(un+1)=α∗(tn+1)

至此证明了n+1的归纳性质也是成立的。

步骤3：与步骤2类似，设想时间序列t0,t1,…,tn,…（不必一定是增序列）。接下来，将步骤2中的结果推广到α∗=(α⊘β)(tn)定义中的上确界不一定达到的情况。首先假设α∗(tn)对所有n都是有限的，对于所有n,m∈N+，存在um,n使得

由(m,n)所构成的集合是可枚举的，假设用(M(i),N(i)),i∈N对该集合进行编号。利用与步骤2相同的构造过程，可以在递增区间[0,si]的序列上对i进行归纳，并建立一个因果关系系统(R,R∗)。该系统以α作为输入到达曲线，以β作为服务曲线，使得

对于一个任意的定值n，通过将上式应用于满足N(i)=n的所有i，可得

对于满足N(i)=n的所有i，集合属于N+，有

且因此(R∗⊘R∗)(tn)=α∗(tn)。至此，在所有n,α∗(tn)都为有限的情况下，步骤3证毕。

若α∗(tn)对于某个tn是无穷大的，则可以使用类似的推理。在这种情况下，用α(tn+um,n)−β(um,n)≥m替代式（1.37）。

步骤4：得出结论。若时间是离散的，则该定理在步骤3就得以证明。否则使用密度参数。非负有理数Q+的集合是可枚举的，因此可以将步骤3应用于Q+的所有元素的序列，并得到系统(R,R∗)，该系统满足对于所有q∈Q+，有

(R∗⊘R∗)(q)=α∗(q)

函数R∗是右连续的。因此，根据定理1.2.2末尾的讨论，R∗⊘R∗是左连续的。接下来证明α∗也是左连续的。对于所有t≥0，有

此外

由于α是左连续的，因此

可以看出α∗也是左连续的。

回到步骤4的主要论证目标，考虑任意的t≥0，集合Q+在非负实数集中是稠密的。因此存在有理数序列qn∈Q+,n∈N，使得qn≤t且。根据(R∗⊘R∗)和α∗的左连续性可以得到

1.10 参考文献说明

在参考文献[15]中，网络演算已被应用于ATM交换机的分析。参考文献[4]给出了一种确定ATM系统最小到达曲线的实用算法，它利用参考文献[16]给出的流量的突发度函数，定义如下。对于任意r，B(r)为使流量是平滑的最小值b，因此，如果流量以恒定速率r被服务，则B(r)是所需的缓冲区容量。注意，B(r)为流量的最小到达曲线σ的勒让德变换（Legendre transform），即，参考文献[4]给出了计算B(r)的快速算法。有趣的是，这个概念也被应用于计算文本中字符的分布。

参考文献[9]将到达曲线和服务曲线的概念用于分析实时处理系统。结果表明，可变容量节点的服务曲线一定是超可加的；反之，任何超可加函数都是可变容量节点的服务曲线。并且与具有次可加服务曲线的贪婪整形器进行对比，表明除了恒定比特率的通道外，贪婪整形器不能被建模为可变容量节点，反之亦然。

在参考文献[17]中，作者考虑交叉开关的交换结构，并令ri,j为服务于从输入端口i流至输出端口j的流量的速率。假设对于所有j满足，且对于所有i满足，并假设(ri,j)满足双随机矩阵，且利用其性质，给出一种简单的调度算法，该算法可以保证分配给从端口i流至端口j的流量的可变容量C满足：对于算法定义的某个值si,j，Ci,j(t)−Ci,j(s)≥ri,j(t−s)−si,j。因此，节点提供的服务曲线为速率–时延函数。

参考文献[3]介绍了一种应对变长数据包的对偶方法，包括利用“g-规整性”（g-regularity）概念代替到达曲线（或“σ-平滑度”)的定义。设想一条变长数据包的流量，其累积数据包长为L，并令Ti为第i个数据包的到达时间。若对于所有数据包编号i≤j，满足T(j)−T(i)≥g(L(j)−L(i))，则称这条流是“g-规整”（g-regular）的。该参考文献随后利用类似于贪婪整形器的概念形成一套理论，该理论用最大加卷积（max-plus convolution）代替最小加卷积。克鲁兹[18]最初引入的(b,r)调节器即该理论下的整形器，其输出为g-规整的，有。通常情况下，该理论与漏桶控制器的概念并不完全一致；更具体地说，满足g-规整与σ-平滑的流的集合之间没有明确的对应关系。这里用一个例子来解释。设想一组满足g-规整性的流的集合，其中，那么这组流的最小到达曲线为σ(t)=rt+lmax[3]。反之，若流是σ-平滑的，则不能保证它是g-规整的。事实上，以下数据包序列就是满足σ-平滑但不满足g-规整条件的流：流在时刻T1=0 产生一个短数据包（长度l1<lmax），随后在时刻产生一个具有最大帧长lmax的数据包。实际上，如果流是σ-平滑的，则它是g′-规整的，其中。

定义1.3.2 定义的严格服务曲线在参考文献[19]中被称为“强”服务曲线。

1.11 习题

习题1.1 分别针对以下3种情况，计算缓冲区初始为空且输入函数为的系统的最大缓冲区大小X。

1.若r(t)=a（常数）；

2.一个峰值速率为1 Mbit/s，“开”周期为1 s，“关”周期为τ s，且通道比特率为c=0.5 Mbit/s的开关连接；

3.若r(t)=c+c sin ωt，其中通道比特率c>0。

习题1.2 已知一个大小为X的固定缓冲区，其接收数据的输入为r(t)。假设缓冲区初始状态为空，求避免缓冲区溢出所需的输出速率c。

习题 1.3

1.对于恒定比特率为c的流，给出几条可能的到达曲线。

2.一条到达曲线为α(t)=B的流，其中B为常数。那么对流来说，这意味着什么？

习题1.4 如果一条流的到达曲线为γP,B，则认为该流是受(P,B)约束的。

1.若通道系统的缓冲区大小为B、比特率为P。请填空：若输入受到________约束，输出受到________约束，则系统是无损的。

2.一条受到(P,B)约束的流，流入以速率c服务的无限缓冲区。那么，该流在缓冲区中的最大延迟是多少？

习题1.5 On-Off流。

1.假设一条周期为T的周期性数据流，满足：当0≤t<T0时，r(t)=p；当T0≤t<T时，r(t)=0。

（1）画出。

（2）找出流的一条到达曲线；找出流的最小到达曲线。

（3）找出使流受(r,b)约束的最小(r,b)。

2.假设承载流量的流使用一条比特率为P bit/s的链路，数据以可变帧长的数据包发送，流受到漏桶(r,b)的控制。那么，最大数据包长度是多少？两个最大帧长数据包之间的最小时间间隔是多少？

应用：P=2 Mbit/s,r=0.2 Mbit/s；如果数据包长度为2 KB，那么所需的突发容限b是多少？数据包之间的最小间隔是多少？

习题1.6 考虑以下GCRA的替代定义。

定义1.11.1 GCRA(T,τ)是一种控制器，它将信元到达时刻t作为输入并输出返回值result。它有内部（静态）变量X（漏桶液位）和最近符合时刻（Last Conformance Time,LCT）。

● 初始状态，X=0,LCT=0

● 某个信元在时刻t到达，则

证明GCRA的两种定义方式是等价的。

习题1.7

1.对于以下流量以及GCRA(10,2)，指出符合与不符合的信元，时刻以链路速率下的信元时隙的个数作为单位，并在假设信元瞬间到达的情况下，绘制漏桶的行为。

（1）0,10,18,28,38。

（2）0,10,15,25,35。

（3）0,10,18,26,36。

（4）0,10,11,18,28。

2.对于GCRA(T,CDV T)，背靠背传输的信元的最大数量[最大“团”(clump)的大小]是多少？

习题1.8

1.对于以下流量以及GCRA(100,500)，指出符合与不符合的信元。时刻以链路速率下的信元时隙的个数作为单位。

（1）0,100,110,120,130,140,150,160,170,180,1000,1010。

（2）0,100,130,160,190,220,250,280,310,1000,1030。

（3）0,10,20,300,310,320,600,610,620,800,810,820,1000,1010,1020,1200,1210,1220,1400,1410,1420,1600,1610,1620。

2.假设一条信元流，其相邻信元发送时刻之间的最小间距为γ个时间单位（γ是两个信元传输开始之间的最小时间间隔）。那么GCRA(T,τ)的最大突发度是多少？发生两次最大突发之间的最小时间间隔是多少？

3.假设一条信元流，其信元间的最小间距为γ个时间单位，两次突发之间的最小间隔为TI。那么最大突发度是多少？

习题1.9 对于CBR连接，以下是ATM运行时的一些参数。

峰值信元速率（信元/s）=100,1000,10 000,100 000

CDVT（µs）=2900,1200,400,135

1.对于上述每种情况，以bit/s和bit为单位的(P,B)参数是多少？T与τ相比结果如何？

2.若一条连接需要的峰值速率为1000信元/s，信元延迟变化为1400µs，应该如何处理？

3.假设给缓冲中的每个连接分配峰值速率，那么确保无损的缓冲容量是多少？考虑以下每种情况下的应用，其中将峰值信元速率为P的N个相同连接进行多路复用。

习题1.10 以下两个问题是相互独立的。

1.假设一个ATM源受到GCRA（T=30个时隙，τ=60个时隙）的约束，其中时间以时隙为单位，一个时隙表示一个信元在链路上传输所需的时间。ATM源根据以下算法发送信元。

● 第一阶段。只要所有信元是符合的，那么信元在时刻t(1)=0,t(2)=15,t(3)=30,…,t(n)=15(n−1)进行发送。换言之，n是使得所有i≤n时，在时刻t(i)=15(i−1)发送的信元都是符合的情况下的最大值。在时刻t(n)发送第n个信元，意味着第一阶段的结束。

● 接下来进入第二阶段。在时刻t(n)之后最早的符合信元可以发送的时刻，用于随后第n+1个信元的发送，并以此重复。换言之，令t(k)为信元k的发送时间，其中k>n；那么t(k)是t(k−1)之后可以发送符合信元的最早时间。

那么，在时间间隔[0,151]内，源端发送了多少信元？

2.网络节点可以建模为具有恒定输出速率c（信元/s）的单个缓冲区。它接收I条ATM连接，分别标记为1,…,I。每条ATM连接都有一个峰值信元速率pi（信元/s）以及一个信元延迟变化容限τi(s),1≤i≤I。进入缓冲区的总输入速率至少与相当（这也相当于认为它是无限的）。那么，保证无损运行所需的缓冲区大小（信元）是多少？

习题1.11 在该问题中，时间以时隙为单位。一个时隙可以在链路上传输一个ATM信元。

1.假设一个ATM源S1受到GCRA（T=50个时隙，τ=500个时隙）的约束，S1根据以下算法发送信元。

● 第一阶段。只要所有信元是合格的，那么信元在时刻t(1)=0,t(2)=10,t(3)=20,…,t(n)=10(n−1)进行发送。换言之，n是使得所有i≤n时，在时刻t(i)=10(i−1)发送的信元都是合格的情况下的最大值。在时刻t(n)发送第n个信元，意味着第一阶段的结束。

● 接下来进入第二阶段。在时刻t(n)之后最早的合格信元可以发送的时刻，用于随后第n+1个信元的发送，并以此重复。换言之，令t(k)为信元k的发送时间，其中k>n；那么t(k)是t(k−1)之后可以发送合格信元的最早时间。

那么在时间间隔[0,401]内，源端发送了多少信元？

2.假设一个ATM源S2同时受到GCRA（T=10个时隙，τ=2个时隙）和GCRA（T=50个时隙，τ=500个时隙）的约束。S2从0时刻开始发送信元，且待发送信元的数量是无限的。S2会在GCRA组合允许的情况下尽快发送其信元。令t(n)为源发送第n个信元的时间，其中t(1)=0。那么t(15)的值是多少？

习题1.12 考虑流R(t)获得的服务满足最小服务曲线保证β，假设

● β为凹函数，且广义递增。

● R⊗β中的inf符号表示取最小值。

那么对于所有t，令τ(t)为满足下式的数值

(R⊗β)(t)=R(τ(t))+β(t−τ(t))

证明存在这样的τ，如果t1≤t2，那么τ(t1)≤τ(t2)。

习题1.13

1.在假设服务曲线为c(t)=r[t−T0]+的情况下，求出峰值速率为P以及信元延迟变化为τ的ATM CBR连接的最大积压和最大延迟。

2.在假设服务曲线为c(t)=r[t−T0]+的情况下，求出峰值速率为P，信元延迟变化为τ，可持续信元速率为M以及突发容限为τB(s)的ATM VBR连接的最大积压和最大延迟。

习题1.14 举证以下论点。

1.假设流受到(P,B)的约束，并且以速率c≥P被服务。那么，输出也受到(P,B)的约束。

2.假设a()存在一个有界的右导数。那么，受到a()约束的流，通过服务速率恒定为的缓冲区后的输出也受到a()的约束。

习题1.15

1.在假设服务曲线为c(t)=r[t−T0]+的情况下，求出峰值速率为P以及信元延迟变化为τ的ATM CBR连接的输出的到达曲线。

2.在假设服务曲线为c(t)=r[t−T0]+的情况下，求出峰值速率为P，信元延迟变化为τ，可持续信元速率为M以及突发容限为τ_B(s)的ATM VBR连接输出的到达曲线。

习题1.16 想象这样一幅图——某条流经过一个速率–时延服务曲线为βR,T的节点，推导其输出的到达曲线。如果图中的t0是无限的，也就是说，对于所有t,α′(t)>r，可以得出什么结论？

习题1.17 设想一组具有服务保证的节点，其服务曲线为ci(t)=ri[t−T_i]+。那么，经过该系统的受到(m,b)约束的流的最大延迟是多少？

习题1.18 一条受到T-SPEC(p,M,r,b)约束的流经过节点1和节点2，节点i的服务曲线为ci(t)=Ri[t−Ti]+。那么流在节点2所需的缓冲区大小为多少？

习题1.19 一条受到T-SPEC(p,M,r,b)约束的流依次经过节点1和节点2，节点i的服务曲线为ci(t)=Ri[t−Ti]+。在节点1和节点2之间放置一个整形器，整形器强制流的到达曲线满足z(t)=min{R2t,bt+m}。

1.该流在整形器所需的缓冲区大小为多少？

2.节点2所需的缓冲区大小为多少？若T1=T2，会得出什么结果？

3.对比采用或未采用重整形器的情况下，对于如前所述的缓冲区，所需的缓冲区容量总和。

4.给出节点2输出的到达曲线。

习题1.20 证明“重整形器的缓冲区大小”的例子中给出的公式（即式1.14）。

习题1.21 定理1.5.1 “贪婪整形器的输入输出特性”是否比推论1.5.1 “贪婪整形器的服务曲线”的结论更强？

习题1.22

1.解释“突发一次性准则”的含义。

2.简要概述整形器的主要属性。

3.使用⊗算子定义以下概念：服务曲线、到达曲线、整形器。

4.什么是贪婪源？

习题1.23

1.举证对于速率为c的恒定比特率通道，其时刻t的积压由以下公式给出

2.如果仅假设节点是一个提供β作为服务曲线的调度器，而不是一个恒定比特率的通道，那么上述公式会变成什么样子？

习题1.24 提供服务曲线β是否确实意味着，在长度为t的任意繁忙时段内，所获得的服务总量至少为β(t)？

习题1.25 流S(t)受到达曲线α的约束。将流通过整形曲线为σ的整形器，假设

α(s)=min{m+ps,b+rs}

以及

σ(s)=min{Ps,B+Rs}

假设p>r,m≤b,P≥R，整形器固定缓冲区的大小为X≥m。若要求缓冲区不溢出。

1.假设B=+∞，计算出保证没有缓冲区溢出的P的最小值P0。

2.不再假设B=+∞，但令P等于问题1计算的P0值。计算(B,R)的值(B0,R0)以保证没有缓冲区溢出，并最小化代价函数c(B,R)=aB+R，其中a是一个大于0的常数。

若(P,B,R)=(P0,B0,R0)，最大虚拟延迟是多少？

习题1.26 设想一个大小为X个信元的缓冲区，其以每秒c个信元的恒定速率服务。将N个相同的连接输入缓冲区，每个连接都受到GCRA(T1,τ1)和GCRA(T2,τ2)的约束。若想保证没有信元丢失，那么N的是大值是多少？

假设T1=0.5 ms,τ1=4.5 ms,T2=5 ms,τ2=495 ms,c=106信元/s，X=104个信元。

习题1.27 考虑由函数R(t)定义的流，其中R(t)表示从时刻t=0以来观测到的比特数。

1.将流输入一个缓冲区，并以速率r服务这个流。令q(t)表示缓冲区在时刻t的积压。假设缓冲区足够大，且初始为空。那么假设已知R(t)的情况下，q(t)的表达式是什么？

接下来，假设缓冲区的初始值（时刻t=0）不是0，而是某个q0≥0的值。那么q(t)的表达式是什么？

2.将流量输入一个漏桶管制器，漏桶的速率为r、大小为b。由于这是一个管制器，而非整形器，因此会丢弃不符合要求的比特。假设该漏桶足够大，且初始为空。那么，确保管制器不丢弃任何比特的R的条件是什么（换言之，流是符合的）？

接下来，假设漏桶的初始（时刻t=0）不是0，而是某个b0≥0的值。

那么，确保管制器不丢弃任何比特的R的条件是什么（换言之，流是符合的）？

习题1.28 设想一个可变容量的网络节点，其容量曲线为M(t)。证明存在一个最大函数S∗(t)，对于所有0≤s≤t，使得

M(t)−M(s)≥S∗(t−s)

证明S∗为超可加的。

反之，如果函数β是超可加的，证明存在一个容量函数为M(t)的可变容量的网络节点，使得对于所有0≤s≤t,M(t)−M(s)≥S∗(t−s)成立。

证明，除了一个明显的特例，整形器不能被建模为可变容量节点。

习题1.29

1.设想一个打包贪婪整形器，其整形曲线为σ(t)=rt,t≥0。假设L(k)=kM，其中M为定值。假设t>0，且R(0)=0，输入为R(t)=10M。计算打包贪婪整形器的输出序列R(i)(t),i=1,2,3,…。

2.当σ(t)=(rt+2M)1{t>0}时，求解与上述相同的问题。

习题1.30 设想一个源，由下面函数给出

因此，这条流包含B bit的瞬时突发。

1.这条流的最小到达曲线是什么？

2.假设服务于流的节点提供速率–时延类型的最小服务曲线，其中速率为r，时延为∆。那么流最后一位的最大时延是多少？

3.假设该流经过两个串联的节点N1和N2，其中Ni（i=1,2）为流提供速率–时延类型的最小服务曲线，速率为ri，时延为∆i。那么流的最后1 bit经过两个节点后产生的最大时延是多少？

4.在与前一个问题假设相同的情况下，令函数R1(t)为节点N1的输出（也是节点N2的输入）流的函数。那么，R1在最坏情况下的最小到达曲线是什么？

5.假设在N1和N2之间插入一个“重新格式化器”（reformatter）S。S的输入为R1(t)。令R′₁(t)为S的输出，R′₁(t)也是N2的输入。重新格式化器S的作用是对流量R1进行延迟，从而输出一条R的延迟流量R′₁。换言之，一定存在某个d，使得R′₁(t)=R(t−d)。假设重新格式化器S在选择尽可能小的d上是最优的。那么在最坏的情况下，d的最优值是多少？

6.在与前一个问题假设相同的情况下，经过串联节点N1、S、N2的最坏端到端延迟是多少？重新格式化器是否透明？

习题1.31 令σ为良态函数。设想一个整形曲线为σ的逐位贪婪整形器与L-打包器的级联，并假设σ(0+)=0。只考虑输入为L-打包的情况。

1.该系统对于σ是打包整形器吗？

2.它对于σ+l_max是打包整形器吗？

3.它对于σ+l_max是打包贪婪整形器吗？

习题1.32 假设σ为良态函数，且σ=σ0+lu0，其中u0为在t=0时的阶跃函数。那么能得出σ0是次可加的结论吗？

习题1.33 算子PL是上半连续的吗？

习题1.34

1.设想L-打包器与最小服务曲线为β、最大服务曲线为γ的网络元件级联，那么是否可以认为，组合系统提供的最小服务曲线为[β(t)−l_max]+、最大服务曲线为γ，并且与反方向级联情况下的结果一样。

2.设想提供保证服务为的GPS节点、L-打包器以及提供保证服务为的第二个GPS节点级联，证明组合系统提供速率为R=min{r₁,r₂}、延迟为的速率–时延服务曲线。

习题1.35 考虑节点向流R(t)提供的速率–时延服务曲线为β=SR,L。假设R(t)为L-打包的，数据包的到达时刻为T1,T2,…（且通常为左连续的）。证明（从而得到inf）。

习题1.36

1.假设K个连接（每个连接的峰值速率为p、可持续速率为m和突发容限为b）输入具有恒定服务速率为P、容量为X的FIFO缓冲区通道。计算系统无损失的K的条件。

2.若Km=P，那么对于K个连接，可接受的X的条件是什么？

3.若在p=2 Mbit/s、m=0.2 Mbit/s、X=10 MB、b=1 MB以及P=0.1 Mbit/s、1 Mbit/s、2 Mbit/s或10 Mbit/s的情况下，最大连接数是多少？

4.对于大小为X的固定缓冲区，当K和P为变量时，绘制可接受域。

习题1.37 给出fB(R)和fB(α)的表达式。

习题1.38

1.当D=1 ms、10 ms、100 ms、1 s时，p=2 Mbit/s、m=0.2 Mbit/s、b=100 KB的连接的有效带宽是多少？

2.在连接的参数为p、m、b的一般情况下，绘制有效带宽e与延迟约束的关系。

习题1.39

1.计算混合VBR连接1,…,I的有效带宽。

2.给出从公式中推导齐次情况的推导过程。

3.假设K个连接（每个连接的峰值速率为p、可持续速率为m和突发容限为b）输入具有恒定服务速率为P、容量为X的FIFO缓冲区通道。计算系统无损失的K的条件。

4.假设有两类连接Ki,i=1,2，输入具有恒定服务速率P以及无限容量X的FIFO缓冲区通道。只要连接的排队延迟不超过某个D，那么连接就是可接受的。绘制接受域，即连接准入控制器（CAC）接受的(K1,K2)集合。接受域是否为凸的？接受域的互补域是正象限凸的吗？这是否可以泛化出两种以上的类型？

第2章 网络演算应用于互联网

本章应用第1章的概念，介绍综合服务和区分服务的基础理论。综合服务定义了如何对流进行预留。本章详细解释该综合服务框架为什么受到GPS模型的深入影响。特别地，将假定每个路由器可被建模为一个节点，该节点提供最小服务曲线，即速率–时延函数，本章将说明RSVP等协议是如何使用该函数的。本章还分析了基于服务曲线调度的更加有效的框架，该框架使我们能够以简单的方式解决可调度性的复杂问题。

本章解释保证速率节点的概念。该节点与服务曲线元件相对应，但有一些区别，因为它使用最大加代数而不是最小加代数。本章将分析两种方法之间的关系。

区分服务的特点是按照逐服务等级（per-class of service）进行预留，而不是按照逐流（per-flow）进行预留。本章将介绍如何将第1章中有关界限的结论应用于求解延迟界限和积压界限。此外还介绍了“阻尼器”（damper），这是一种强化最大服务曲线的方法，并说明它如何从根本上减小延迟界限。

2.1 GPS和保证速率节点

本节将描述GPS及其派生方法：它们构成了定义互联网保证模型的基础。

2.1.1 数据包调度

只要流满足某些到达曲线的约束（见第2.2节），则保障服务网络会为流提供延迟和吞吐量保证。这就要求网络节点实现某种形式的数据包调度，也称为服务规则（service discipline）。在网络节点的每个缓冲器中，数据包调度被定义为确定不同数据包服务顺序的功能。

数据包调度的一种简单形式是FIFO：数据包按照到达顺序获得服务。延迟界限和所需的缓冲器大小取决于聚合流的最小到达曲线（见第1.8节）。如果其中一条流的流量很大，则所有流的延迟都增加，并且可能会发生数据包被丢弃的现象。

因此FIFO调度需要网络中所有节点的所有流严格执行到达曲线约束。同样，使用FIFO调度时所有流的延迟界限都是相同的。第2.6节将更详细地研究FIFO调度。

一种替代方法[5,20]是使用逐流排队（per-flow queuing），以便为流提供隔离，并提供不同的保证。首先介绍逐流排队的理想形式，该形式被称为“GPS”[6]，这一概念在第1章中已经被提到。

2.1.2 GPS及其实际运用

GPS节点并行服务多条流，总输出速率等于c bit/s。流i被分配指定的权重ϕi。我们称Ri(t)、R∗_i(t)为流i的输入和输出函数。在任何时刻t，如果流i没有积压[Ri(t)=R∗_i(t)]，GPS节点保证提供给流i的服务速率为0；否则，保证提供给流i的服务速率为，其中B(t)是时刻t的积压流的集合。

因此

在上面的表达式中，使用指示函数1_{expr}，如果表达式“expr”为真，则其取值为1，否则为0。

从而易得GPS节点提供给流i一条等于的服务曲线，其中。参考文献[21]表明，如果对于所有流，它们的一些到达曲线属性是已知的，则每条流可以获得更好的服务曲线。然而，利用简单的服务曲线的属性就可以充分理解综合服务模型。

GPS满足隔离流和提供区分保证的要求。如果知道每条流的到达曲线，则可以使用第1章的结论来计算每条流的延迟界限和缓冲器需求。但是，GPS节点是一个理论上的概念，它并不是真正可行的。这是由于它依赖于流模型，并且假定数据包是可无限分割的。如何才能实际运用GPS？一种简单的解决方案是使用虚拟完成时间，就像第1.7.3节中对缓冲漏桶控制器所做的那样：对于每个数据包，在GPS下计算其完成时间θ，然后在时刻θ将数据包提供给多路复用器，此复用器以速率c服务数据包。图2.1（a）显示了多条流到达并离开的示例的完成时间。它还说明了该方法的主要缺点：在时刻3和时刻5，复用器将处于空闲状态；而在时刻6，它将为突发的5个数据包进行服务。需要特别说明的是，这样的调度器不是尽力工作的。

这就是促使研究人员寻找其他GPS实际运用方法的原因。本节研究了一种GPS的实现，这种实现是逐数据包地进行处理，被称为数据包通用处理器共享（Packet Generalized Processor Sharing,PGPS）[6]。GPS的其他实现将在第2.1.3节中讨论。

PGPS对GPS的近似模拟如下所述。每条流有一个FIFO队列。调度器一次处理一个数据包，直到数据包以系统速率c完成传输为止。对于每个数据包，计算它在GPS下的完成时间（称为“GPS完成时间”）。然后，每当一个数据包完成传输时，在所有现存的数据包中具有最早GPS完成时间的那个数据包被选择为下一个数据包进行传输。图2.1显示了一个多条流到达并离开的示例。可以看出，与之前讨论的简单方案不同，PGPS是尽力工作的。但是这样做的代价是，可能会在GPS数据包的完成时间之前调度该数据包。

可以在以下命题中量化PGPS和GPS之间的差异。第2.1.3节将介绍如何导出服务曲线属性。

命题2.1.1 PGPS的完成时间最多为GPS的完成时间加上，其中c为总速率，L为最大数据包长度[6]。

图2.1的说明：流0的权重为0.5，流1至流5的权重为0.1。所有数据包具有相同的传输时间，等于1个时间单位。

证明：按照数据包的离开顺序，称D(n)为PGPS下聚合输入流中第n个数据包的完成时间，称θ(n)为GPS下聚合输入流中第n个数据包的完成时间。称n0为开始繁忙时段的数据包编号，数据包n在此繁忙时段离开。请注意，PGPS和GPS具有相同的繁忙时段，因为如果仅观察聚合流，则PGPS和GPS之间没有区别。

在PGPS中可能有一些数据包在数据包n之前离开，但在GPS下仍然有一些数据包的离去时刻迟于数据包n。如果这种情况发生，令m0为最大数据包编号，且有m0≥n0；否则令m0=n0−1。在这个命题中，称l(m)为数据包m的比特长度。在PGPS下，数据包m0在时刻开始服务，该服务必须早于数据包m（m=m0+1,…,n）的到达时刻。事实上，除非根据PGPS的定义，PGPS调度器将在数据包m0前调度数据包m（m=m0+1,…,n）。现在观察GPS系统，根据m0的定义，数据包m=m0+1,…,n在不晚于数据包n时离开；它们已在时刻后到达。根据区间内的总服务量，发现

现在由于数据包m0,…,n处在同一个繁忙时段，因此有

通过联立上面的两个表达式，发现，这表明命题在m0≥n0时成立。

如果m0=n0−1，则在GPS下的所有数据包n0,…,n都在数据包n之前离开，并且相同的推理表明

其中t0是繁忙时段的开始时刻，并且

因此，在这种情况下D(n)≤θ(n)。

2.1.3 GR节点和最大加代数方法

可以从对偶的角度探讨较早定义的服务曲线概念，该角度包括研究数据包的到达时刻和离开时刻，而不是研究函数R(t)（此函数计算时间t内到达的比特数）。研究函数R(t)到达时刻和离去时刻的方法会得出最大加代数（与最小加代数具有相同的属性），由于可以处理变长的数据包，最大加代数更适合考查细节，但仅在服务曲线为速率–时延类型的曲线时才有效。当节点不能被假设为逐流FIFO时，节点也是有用的，例如DiffServ（见第2.4节）。

GR模型框架还允许表明很多调度器具有速率–时延服务曲线属性。事实上，参考文献中已经提出了除PGPS之外的大量GPS的实际运用，本书中提到了虚拟时钟调度[22]、PGPS[6]和自计时公平排队[23,24]。有关GPS实际运用的详细讨论，请参见参考文献[23,25]。这些实际运用与实现它们的复杂度以及可获得的界限不同。所有这些实际运用都适用于被称为“保证速率”的模型框架[26]。本文还将分析它与最小加代数的关系。

定义2.1.1（GR节点[26]） 设想一个为流提供服务的节点，数据包按照到达顺序进行编号。令an≥0、dn≥0分别为到达时刻和离去时刻。如果保证dn≤fn+e[fn由式（2.1）定义]，则该节点是这个流的GR节点，其中速率为r，延迟为e。

变量fn（保证速率时钟）可以被解释为从一个FIFO恒定速率服务器（速率为r）中离开的时间。参数e表示节点偏离量。但请注意，GR节点不一定被限定为FIFO。GR节点也被称为“速率–时延服务器”。

例：GPS 设想一个理想的GPS调度器，该调度器将速率分配给流i。该调度器是流i的GR节点，速率为Ri，时延为0（读者自行证明）。

定义2.1.2（调度器与GPS的单向偏差） 称调度器S与GPS偏离e，如果对于所有数据包n，离去时刻满足

dn≤gn+e （2.2）

其中，gn是从假想的GPS节点离开的时间，该GPS节点向该流分配速率r=（假设该流的编号为1）。

将此定义解释为与假想的GPS调度器的比较，该调度器为相同的流提供服务。

定理2.1.1 如果调度器满足式（2.2），则它是速率为r、时延为e的GR节点。

证明：gn≤fn，其余易得。

例：PGPS 设想一个PGPS调度器，为流i分配速率。PGPS调度器是流i的GR节点，速率为Ri，时延为，其中，L是最大数据包长度（在调度器中出现的所有流，来自命题2.1.1）。

定理2.1.2（GR节点的最大加表示） 设想一个系统，其中数据包按到达顺序编号为1,2,…。称an、dn为数据包n的到达和离去时刻，ln为数据包n的长度。按照惯例定义d0=0。系统是一个速率为r、时延为e的GR节点，当且仅当对于所有n都存在k∈{1,…,n}时，有

证明：式（2.1）可以使用与命题1.2.4的证明相同的最大加代数迭代求解。定义

则得到

其余易得。

式（2.3）是服务曲线定义的对偶[参见式（1.9）]，其中β(t)=r[t−e]+。现在阐明这种关系。

定理2.1.3（等效于服务曲线） 设想一个具有“L-打包”输入的节点。

1.如果该节点保证一条最小服务曲线等于速率–时延函数β=βr,v。并且如果该节点是FIFO节点，则它是速率为r和时延为v的GR节点。

2.相反，速率为r且时延为e的GR节点是服务曲线元件的级联，服务曲线等于速率–时延函数βr,v和L-打包器的级联：如果GR节点是FIFO的，则服务曲线元件也是如此。

证明很长，将在本节末尾给出。

通过应用定理1.7.1，可以得到推论2.1.1。

推论2.1.1 GR节点提供最小服务曲线，此服务曲线可用于获得r积压界限。

定理2.1.4（延迟界限） 对于在速率为r、时延为e的（可能是非FIFO的）GR节点中服务的α-平滑流，任何数据包的延迟都由下式限定

证明：根据定理2.1.2，对于任意固定的n，可以找到1≤j≤n，使得

数据包n的延迟为

dn−an≤fn+e−an

定义t=an−aj。通过假设

lj+…+ln≤αr(t)

其中αr(t)是在t上α的右极限。因此

现在则有。

注释：注意式（2.4）是到达曲线α和速率–时延服务曲线（速率为r，时延为e）之间的水平偏差公式。因此，对于FIFO GR节点，定理2.1.4遵循定理2.1.2，而对于计算延迟，可以忽略打包器。定理2.1.4也适用于非FIFO节点。

2.1.4 GR节点的级联

FIFO节点 对于逐流FIFO的GR节点，适用于通过服务曲线方法获得的级联结果。

定理2.1.5 具体来说，速率为rm和时延为em的M个GR节点（逐流FIFO）的级联是速率为和时延为的GR节点，其中Lmax是该流的最大数据包长度。

如果对于所有m有rm=r，则额外项为；这是由于受到打包器的影响。

证明：根据定理2.1.3的第2点，可以将系统i分解为Si、Pi的级联，其中Si提供服务曲线，Pi是打包器。

称S是如下元件的级联，有

S1,P1,S2,P2,…,Sn−1,Pn−1,Sn

根据定理2.1.3的第2点，S是FIFO的，并提供服务曲线βr,e。根据定理2.1.3的第1点，它是速率为r和时延为e的GR节点。现在Pn不会影响每个数据包最后1 bit的完成时间。

注意这里略微有一点变化：定理2.1.5的证明表明，在用 代替时，该定理也有效。

端到端延迟界限 因此，通过GR节点级联的端到端延迟界限为

这是参考文献[26]中的公式，它是式（1.23）的泛化。

合成节点（composite node） 我们详细分析一个特定的示例，该示例在实践中通常是在对路由器建模时出现的。设想一个由两个元件组成的合成节点。前者（可变延迟元件）对数据包施加范围为[δmax−δ,δmax]的延迟。后者是FIFO的，并向其输入提供数据包尺度速率保证，其中速率为r，时延为e。可以证明，如果已知可变延迟元件是FIFO的，那么得到一个简单的结果。首先给出以下引理，该引理本身具有一些意义。

引理2.1.1（可变延迟GR节点） 设想已知保证延迟小于等于δmax的节点。不限定该节点是否为FIFO节点。称lmin为最小数据包长度，对于任意r>0，该节点是时延为和速率为r的GR节点。

证明：用本节的标准符号表示。该假设意味着对于所有n≥1，有dn≤an+δmax。用式（2.1）定义fn，则有，因此dn−fn≤。

定理2.1.6（具有FIFO可变延迟元件的合成GR节点） 设想两个节点的级联。前者对数据包施加的延迟小于等于δmax。后者是速率为r和时延为e的GR节点。两个节点都是FIFO节点。两个节点以任意顺序的级联都是速率为r和时延为e′′=e+δmax的GR节点。

证明：对于任意r′>r，前一个节点是GR节点。根据定理2.1.5（及其后的注释），两个节点的级联是GR节点。令r′趋于+∞即证。

非逐流FIFO的GR节点 非逐流FIFO的GR节点的级联结果不再为真。我们将详细研究这种合成节点。

定理2.1.7 设想两个节点的级联。第一个节点对数据包施加范围为[δmax−δ,δmax]的延迟。第二个节点是FIFO的，并为其输入提供保证速率时钟服务，该服务的速率为r，时延为e。不假定第一个节点为FIFO的，因此到达第二个节点的数据包顺序与到达第一个节点的数据包顺序不同。假设新的输入受连续到达曲线α(·)的约束。两个节点的级联按此顺序向新的输入提供保证速率时钟服务，该服务的速率为r，时延为

证明在第2.1.5节给出。

应用：对于α(t)=ρt+σ，发现

2.1.5 证明

1.定理2.1.3的证明

第1部分：设想服务曲线元件S。假设为了简化说明，输入和输出函数R和R∗是右连续的。设想虚拟系统S0，它由整形曲线为λr的逐比特贪婪整形器和随后的恒定逐比特延迟元件组成。逐比特贪婪整形器是恒定比特率服务器，速率为r。因此数据包n的最后1 bit恰好在时刻fn离开，由式（2.1）定义，则数据包n的最后1 bit在时刻d0n=fn+e离开S0。S0的输出函数是R0=R⊗βr,e。通过假设R∗≥R0，并根据FIFO假设，表明S中的延迟由S′中的延迟限定。因此dn≤fn+e。

第2部分：设想虚拟系统S，其输出S(t)由下式定义

若di−1<t≤di

则

S(t)=min{R(t),max{L(i−1),L(i)−r(di−t)}} （2.6）

有关说明请参见图2.2。从而易得R′(t)=PL(S(t))。

还要考虑虚拟系统S0，其输出为

S0(t)=(βr,v⊗R)(t)

S0是恒定速率服务器，延迟为v。现在的目标是证明S≥S0。

称d0i为数据包i的最后1 bit在S0的离去时刻（如图2.2所示的i=2的例子，虚拟系统输出是S(t)）。令u=d0i−di。GR节点的定义表示u≥0。现在由于S0是移动的常速率服务器，因此有

且，因此，并且

从而易得

如果d0i−1+u<s<d0i，则S0(s)≤max{L(i−1),L(i)−r(d0i−s)} （2.7）

现在考虑某些t∈(di−1,di]，并令s=t+u。如果S(t)=R(t)，由于R≥S0，则显然有S(t)≥S0(t)。否则，由式（2.1）得S(t)=max{L(i−1),L(i)−r(di−t)}。有d0i−s=di−t，因此与式（2.7）结合，得出S0(s)≤S(t)。现在s≥t，从而最终有S0(s)≤S(t)。也很容易看出如果对于所有i有di−1≤di，那么S是FIFO的。

2.定理2.1.7的证明

定理2.1.7的证明使用的符号和约定详见定理7.5.3的证明过程。使用相同类型的缩减也能够假设所有数据包的到达时刻是不同的。

令n≥1；根据定理2.1.2，可充分地说明存在某些k∈{1,…,n}使得

根据假设，存在某些j，使得bj≤bn和

不能假设j≤n；因此，将k定义为在间隔[bj,bn]中最早到达的数据包，换句话说，k=inf{i≥1:bj≤bi≤bn}，必然有k≤n。

在[bj,bn]中到达第2个节点的任何数据包必须在数据包k之后或与其一起到达节点1，且必须在bn前到达。因此B[bj,bn]≤A[ak,bn]。现在bn≤an+δ。因此有（详细过程见定理7.7.1）

B[bj,bn]≤A[ak,an]+A(an,bn]

≤A[ak,an]+α(δ)−lmin

且bj≤bk≤ak+δ，并由式（2.9）得

dn≤ak+e+δ+α(δ)+A[ak,an]−lmin

这也说明了式（2.8）是成立的。

2.2 IETF的综合服务模型

2.2.1 保证服务

互联网支持不同的预留原则，定义了两种服务：“保证”服务，以及“受控负载”服务。它们的不同之处在于前者提供了真正的保证，而后者仅提供近似保证。本节将重点介绍它们的区别。在这两种情况下，预留原则基于“准入控制”，其操作如下。

●为了接收保证服务或受控负载服务（controlled load service），必须首先在配置阶段执行预留流。

● 流必须遵循形式为α(t)=min{M+ρt,rt+b}的到达曲线，称为T-SPEC（见第1.2.2节）。在预留阶段声明T-SPEC。

● 路径上的所有路由器接受或拒绝预留。对于保证服务，路由器只有在能够提供服务曲线保证和足够缓冲以进行无损运行时才接受预留。服务曲线在预留阶段的表示如下所述：对于受控负载服务，没有严格定义接受预留的含义。最有可能的是，这意味着路由器具有一个估计模块，该模块决定预留是否可以在大概率条件下被接受，并且几乎不会发生丢包；这里没有服务曲线或保证延迟。

本章会重点介绍保证服务。提供受控负载服务依赖于有损模型，这将在第9章进行讨论。

2.2.2 互联网路由器的综合服务模型

假设预留阶段所有路由器都可以使用非常简单的模型导出其特征。该模型基于以下观点：综合服务路由器实际实现了GPS的近似，例如PGPS，或GR节点。第2.1.3节中已经表明，实现保证速率的路由器向流提供的服务曲线是速率–时延函数，速率为R，时延为T，满足以下关系

C为流的最大数据包长度。，其中L是路由器中所有流的最大数据包长度，c是调度器的总速率。这是为互联网节点定义的模型[8]。

事实2.2.1 路由器的综合服务模型是提供给流的服务曲线始终是速率–时延函数，其参数之间的关系形式为式（2.10）。

C和D的值取决于路由器的特定实现，对于GR节点的情况请参见推论2.1.1。注意，路由器不必实现近似于GPS的调度方法。实际上，我们在第2.3节中讨论了一个调度器系列，它比GPS具有更多优势。如果路由器采用的方法与GPS有很大不同，则必须找到一条服务曲线，该服务曲线边界低于路由器提供的最好服务曲线保证。在某些情况下，这可能意味着没有充分利用部分有关路由器的重要信息。例如，在综合服务模型中，不可能通过第2.4.3节中讨论的广义服务曲线最早截止期限优先（the generalization of the Service Curve Earliest Deadline-first,SCED）之类的系统来实现为流提供固定延迟的网络。

2.2.3 通过RSVP进行预留设置

设想由T-SPEC(M,p,r,b)定义的流，其经过节点1,…,N。通常，节点1和节点N是终端系统，而节点n（1<n<N）是路由器。综合服务模型假定流路径上的节点n提供了速率–时延服务曲线，并进一步假定Tn具有以下形式

其中Cn和Dn是取决于节点n的特性的常数。

预留实际上是通过诸如RSVP之类的流建立过程进行的。在过程结束时，路径上的节点n已为流分配了值Rn≥r。这等效于分配了服务曲线。由定理1.4.6可知，提供给流的端到端服务曲线是速率–时延函数，其中速率R和时延T由下式给出

令和。可以将后一个等式改写为

其中

项Sn在节点n处被称为“局部松弛”项。

从命题1.4.1可以立即得出以下命题。

命题2.2.1 如果R≥r，则在上述条件下，端到端延迟界限为

现在可以使用RSVP描述预留的建立。使用RSVP建立预留的一些细节如图2.3所示。该过程涉及建立两个RSVP流：广告（advertisement，记为“PATH”）流和预留（reservation，记为“RESV”）流。首先描述点对点的情况。

● PATH消息由源端A发送。该消息包含流的T-SPEC（源T-SPEC），在传输过程中未进行修改，消息中的另一个字段是ADSPEC，该字段沿路径进行累积。在目的端B,ADSPEC字段除了其他参数之外，还包含式（2.13）中使用的Ctot、Dtot值。PATH消息不会引起任何预留。

● RESV消息由目的端B发送，并发起实际的预留。该消息遵循由PATH消息标记的反向路径。RESV消息包含值R′（作为所谓的R-SPEC的一部分），该值是发送路径沿途的路由器必须保留的速率参数Rn的下限。遵循下面的描述过程，R′的值由目的端B基于端到端延迟目标dobj确定。RESV消息通常不会被中间节点更改。

定义函数f为

换句话说，f是定义端到端延迟界限的函数，其假设沿路径的所有节点都将预留Rn=R′。目的端B计算R′，R′的值为满足f(R′)≤dobj条件的最小值（且R′≥r）。仅当Dtot<dobj时，R′的取值存在。

在图2.3中，目的端B需要满足延迟可变量（delay variation）为0.6 s的目标，这就要求速率最小值为R′=622 kbit/s。R′的值被发送到PATH消息的R-SPEC字段中的下一个上游节点。中间节点不知道完整的Ctot和Dtot取值，也不知道总的延迟变动目标。考虑所有中间节点都是真正PGPS调度器的简单情况。节点n简单地检查它是否能为流保留Rn=R′。这涉及验证预留速率的总和是否小于调度器的总速率，以及是否有足够的缓冲可用。如果是这样，则在所有中间节点都接受预留的情况下，它将RESV消息传递到上游，直至目的端。如果预留被拒绝，则节点通常将其丢弃并通知源端A。在这种简单情况下，所有节点都应将其速率设置为Rn=R′。因此R=R′，式（2.13）确保端到端延迟界限被保证。

实际上，由于RSVP的设计者还希望RSVP支持其他调度器，因此有一个小的附加元素（松弛项）。R-SPEC中的松弛项的用法如图2.4所示，我们看到由目的端B设置的端到端延迟可变量要求为1.0 s。在这种情况下，目的端预留的最小速率为512 kbit/s。即使这样，延迟可变量目标Dobj也大于式（2.13）给出的界限Dmax。差异Dobj−Dmax用松弛项S写入，并传递给RESV消息中的上游节点。上游节点无法计算式（2.13），因为它没有端到端的参数值。但是，除了广告的内容之外，上游节点还可以使用松弛项来提高其内部延迟的目标。例如，保证速率节点可以增加其v值（定理2.1.2），从而减少执行预留所需的内部资源。由图2.4可知，R1将松弛项减少了0.1 s，这等同于将Dtot参数增加0.1 s，但不修改Dtot。

这里考虑的延迟是总的（固定的加上可变的）延迟。RSVP还包含一个用于广告固定延迟部分的字段，该字段可用于计算端到端的固定延迟。然后通过减法获得延迟的可变部分（称为延迟抖动）。

2.2.4 流建立算法

节点有许多不同的方法来决定应分配的参数。在这里提出一种可能的算法。如果所有节点都预留持续速率r，则目的端计算得到最坏情况下的延迟可变量。如果产生的延迟可变量是可接受的，则目的端设置R=r，且中间节点可以利用所得的松弛度，在它们广告的延迟可变量（由参数C和D定义）的基础上加上本地延迟值。否则，目的端B将R设置为支持端到端延迟可变量目标的最小值Rmin，并将松弛项设置为0。作为结果，沿路径的所有节点都必须预留Rmin。与以前的情况一样，节点可以分配一个速率，该速率大于节点通过上游传递的R的值，以减少它们对缓冲的需求。

定义2.2.1（流建立算法）

● 在目的端系统I，计算

如果Dobj>Dmax，则为流分配速率RI=r和附加的延迟可变量dI≤Dobj−Dmax；设置SI=Dobj−Dmax−dI，并将预留请求RI、SI发送到端I−1。否则（如果Dobj≤Dmax）找到最小Rmin，使得Dobj−Dtot（如果它存在）。向端I−1发送预留请求RI=Rmin和SI=0。如果Rmin不存在，则拒绝该预留或增加延迟可变量目标Dobj。

● 在中间系统i：从系统i+1接收预留请求Ri+1和Si+1。

● 如果Si=0，则对速率Ri+1进行预留。如果成功预留，则向端i−1发送预留请求Ri=Ri+1和Si=0。

● 否则（Si>0），对速率Ri+1进行预留，并增加一些额外的延迟可变量di≤Si+1。如果成功，则将预留请求Ri=Ri+1和Si=Si+1−di发送到端i−1。

算法确保了预留速率恒定。容易验证端到端延迟可变量是否受Dobj的限制。

2.2.5 多播流

现在考虑多播情况。源端S沿着多播树发送数据流到多个目的端。PATH消息沿多播树转发，在分支点处进行复制。在同一个分支点，RESV消息将合并。设想这样一个分支点，将其称为节点i，并假定它接收到针对相同T-SPEC但具有各自参数R′_in、S′_in、R′′_in、S′′_in的预留请求。节点使用定义2.2.1的语义在内部执行预留。然后节点必须合并发送给节点i−1的预留请求。使用以下规则进行合并。

R-SPEC合并规则 合并预留的R、S由下式给出

R=max{R′,R′′}

S=min{S′,S′′}

现在考虑应用定义2.2.1的树。我们想说明对于所有目的端，端到端延迟界限都得到了保证。

使用此算法无法减小从目的端到源端的路径上的速率。因此，沿着树向目的端的最小速率是在目的端设置的速率。

RSVP的其他一些特征如下。

● 节点中的状态需要刷新；如果未被刷新，则预留被释放（软状态）。

● 路由与流的预留不协调。

到目前为止，我们仅关注了延迟约束。缓冲需求可以使用命题1.4.1中的值来计算。

2.2.6 ATM流建立

使用ATM时，存在以下差异。

● 路径仅在流建立时确定。不同的连接可能会根据它们的需求遵循不同的路由，并且一旦建立连接，连接将始终使用相同的路径。

● 使用标准的ATM信令，连接设置在源端启动，并由目的端和所有中间系统确认。

2.3 可调度性

到目前为止，每条流都是被单独考虑的，并假设节点能够提供某种调度或服务曲线保证。在本节中将解决资源分配的总体问题。

当节点执行预留时，有必要检查本地资源是否充足。通常，用于此目的的方法包括将节点分解为构建块网络，例如调度器、整形器和延迟元件。主要考虑两种资源：比特率（称为“带宽”）和缓冲器。主要困难是比特率的分配。根据参考文献[27]，本节将介绍的分配速率等于分配服务曲线。它也等同于可调度性概念。

考虑具有输出速率C的PGPS调度器的简单情况。如果要为流i分配速率ri，则对于每个i，可以将GPS权重分配给流i。假设

则从命题2.1.1和推论2.1.1可知，每条流i都被保证了速率为ri和时延为的速率–时延服务曲线。换句话说，PGPS的可调度性条件很简单，见式（2.14）。但是，接下来将看到可调度性条件并不总是那么简单。还请注意，端到端延迟不仅取决于分配给流的服务曲线，还取决于其到达曲线约束。

许多调度器已经被提出，其中一些调度器不适合GR框架。在保证服务中最通用的框架是SCED[27]。本节给出固定长度数据包和时隙理论。变长数据包一般理论的某些方面是已知的[3]，还有一些理论尚待完成。不失一般性地，假设每个数据包的长度为1个数据单元。

2.3.1 EDF调度器

SCED是基于EDF调度器的概念。EDF调度器根据某种方法将截止期限Dni分配给流i的第n个数据包。假设截止期限在流中是广义递增的。在每个时隙，调度器从存在的所有数据包中选择截止期限最小的数据包。有多种计算截止期限的方法。基于延迟的调度器（Delay Based Scheduler,DBS）[28]设置Dni=An+di，其中An是流i的第n个数据包的到达时刻，并且di是分配给流i的延迟预算。如果di独立于i，则EDF调度器等同于一个FIFO调度器。可以看出上述情况是SCED的特殊情况，SCED将其视为计算截止期限的非常通用的方法。

EDF调度器是尽力工作的，也就是说，如果系统中至少存在一个数据包，则EDF调度器不能处于空闲状态。结果是来自不同流的数据包不一定按照它们的截止期限顺序接受服务。例如，设想基于延迟的EDF调度器，并假设流1具有较大的延迟预算d1，而流2具有较小的延迟预算d2。即使流1的数据包的截止期限t1+d1大于流2的数据包的截止期限，流1的数据包（在时刻t1到达）也可能在流2的数据包（在时刻t2到达）之前获得服务。