教育部国家级特色专业(计算机科学与技术)资助

网络流量整形与带宽控制技术黄今慧莫倩著北京内容简介本书主要介绍基于TCP/IP协议的网络流量整形与带宽控制技术,内容分为理论与工程实践两大部分.
理论部分(第1~7章)介绍了与流量整形和带宽控制相关的基础知识和最新的研究成果,包括异常流量检测、自适应流量控制等;工程实践部分(第8~11章)以自主研制的网牧系统为例,详细介绍了标识映射与分离模型、服务质量保障体系、智能化服务体系的总体设计,对部分关键实现代码进行了分析.
本书理论与实践紧密结合,配有网牧系统的实名制和服务保障体系的C语言源代码,供读者分析.
本书提供了一套完整的产品设计模型和代码,适合从事流量整形和带宽控制技术研发的工程技术人员阅读,也可以作为高等院校计算机网络、信息安全等专业在网络流量分析方面的教材.
图书在版编目(CIP)数据网络流量整形与带宽控制技术/黄今慧,莫倩著.
—北京:科学出版社,2013ISBN978-7-03-037300-7I.
①网…II.
①黄…②莫…III.
①计算机网络-流量-控制-研究IV.
①TP393中国版本图书馆CIP数据核字(2013)第073245号责任编辑:张濮王迎春马晓瑾/责任校对:宣慧责任印制:张倩/封面设计:迷底书装源海印刷有限责任公司印刷科学出版社发行各地新华书店经销*2013年4月第一版开本:B5(720*1000)2013年4月第一次印刷印张:171/400字数:342000定价:72.
00元(如有印装质量问题,我社负责调换)前言随着网络技术的迅速发展和各种网络业务应用的普及,网络传输的业务类型已从简单的低带宽要求的文件传送、电子邮件等变为数据、语音、视频等大流量业务,并且业务对网络传输的可靠性、实时性和安全性的要求也越来越高.
由于现在广为使用的TCP/IP固有的无连接特性和传统IP网络尽力而为(best-effort)的服务原则,传统的互联网无法向用户提供有效的服务质量(QualityofService,QoS)保障,也不能实现网络资源的有效监控和管理.
网络流量控制正是在此基础上提出的一种有效的网络服务质量解决方案,其本质在于有效解决拥塞控制问题和合理调度网络资源.
这些资源包括网络节点的处理能力、缓存空间和通信链路带宽.
这三者中的任何一个都有可能成为潜在的瓶颈,从而导致网络拥塞.
流量整形(trafficshaping)与带宽控制(trafficcontrol)是网络流量控制的两种基本手段.
利用流量整形和带宽控制技术,可以对网络流量进行识别和控制,避免网络产生不必要的拥塞和掉线.
因此,流量整形与带宽控制已成为下一代互联网的关键技术之一.
在网络与信息领域,另外一个值得关注的趋势是:以信息化为核心的新军事变革正在使现代战争形态发生深刻变化.
战争优势的竞争正逐渐向信息优势的竞争靠拢.
能打赢未来战争的部队,必定是高度信息化的部队.
全球信息栅格(GIG)、网络中心战等概念的提出,以及通信、计算机和网络技术的迅猛发展,推进了基于网络的作战指挥、基于网络的信息获取和基于网络的信息分发与共享,作战模式从以武器平台为中心转向以信息平台为中心.
夺取信息优势靠的是由高性能、高安全性的信息设备构建的适合于军事应用的综合电子信息系统.
它集指挥控制、情报侦察、预警探测、通信和电子对抗系统为一体,以军事信息网络为基础,以指挥控制为核心,来完成军事作战任务.
这种作战模式对军事信息网络提出了许多新的需求,如支持交互式多媒体等综合业务、动态组网、随遇接入、即插即用、无缝移动、按需分配带宽、可控可管和快速抗毁机构,提供集成的、安全的、快速的、一体化的端到端信息服务,允许用户间随时通信和访问共享数据,而不管他们身在何处.
上述这些能力只有通过构建栅格化的军事信息网络才能实现,栅格化军事信息网络不仅是军队通信系统发展的需要,也是军事通信技术的发展趋势,是技术发展和需求推动的必然要求.
在此背景下,作者有幸参与了全球信息栅格体系架构的研究,并主持了其中几个子系统的研究和开发,包括本书详细介绍的实名体系和服务保障体系.
从实际运行效果来看,网牧系统达到了初始设计目标;特别是在流量控制和带宽控制与服务保障方面,具有应用识别准确、流量控制精度较高等特点.
网络流量整形与带宽控制技术·ii·本书对作者近几年在流量整形和带宽控制方面所做的一些工作进行了总结和提炼.
为使全书知识点和结构完整,补充了与流量整形和带宽控制相关的基础知识和最新的研究成果介绍.
在阅读本书时,有一定网络知识基础的读者可以跳过第1章.
第2章介绍了Linux的网络过滤和连接分析,这是阅读第9~11章的源代码所必备的基础知识.
第3、4章介绍了流量整形和带宽控制方面已有的一些算法,这对于理解流量整形和带宽控制实现的原理是有极大帮助的.
建议读者至少掌握本书3.
4节介绍的令牌桶过滤器算法、4.
1节介绍的基于类的队列算法和4.
2节介绍的分层的令牌桶算法.
第5~7章介绍了多链路环境下流量控制算法、异常流量检测算法、自适应流量控制算法.
安排这些内容的目的是让读者从应用的角度掌握和理解流量控制的原理和技术.
这对了解和掌握本书第8~11章的相关内容是很有帮助的.
最后几个章节是本书的核心,建议有志于从事相关领域研究和开发的读者深入地阅读这些章节,并结合第2章介绍的知识,研究代码的结构和实现技巧.
本书配有实例源代码,读者可以从www.
sciencep.
com下载.
参与本书编写、修改和讨论的作者还有赵霞、万月亮、毛典辉、杨伟杰、黄黎慧等;在此,还要感谢我的学生赵威、林晓蕾、杨松鹤、范博学等,他们为本书做了很多辅助性工作.
本书由北京市学位与研究生教育专项(PXM2011_014213_113632)资助出版.
由于作者水平有限,不妥之处在所难免,恳请读者批评和指正.
作者2012年12月目录前言第1章流量整形与带宽控制·11.
1TCP/IP协议族简介11.
1.
1TCP/IP的分层与封装·21.
1.
2IP、UDP、TCP首部结构·31.
2流量整形与带宽控制的基本原理·41.
2.
1拥塞与流量控制·41.
2.
2国内外研究现状·71.
3典型流量整形与带宽控制的方法·81.
3.
1TCP流量控制81.
3.
2队列管理技术141.
3.
3分组调度技术151.
3.
4流量整形技术17第2章Linux网络过滤与连接分析·192.
1Linux系统简介192.
2Linux内核结构202.
2.
1Linux内核组成部分·202.
2.
2Linux内核代码目录结构·222.
2.
3Linux内核网络代码目录结构232.
3Linux网络过滤分析·232.
3.
1Netfilter框架·242.
3.
2Netfilter的主要函数和数据结构·262.
4Linux连接跟踪302.
4.
1连接跟踪的概念·302.
4.
2连接跟踪的原理·312.
4.
3连接建立过程332.
4.
4Netfilter的连接状态·36第3章无分类的流量控制算法·383.
1先进先出队列规定39网络流量整形与带宽控制技术·iv·3.
1.
1pfifo_fast原理·393.
1.
2pfifo_fast算法实现393.
2随机早期检测算法403.
2.
1RED原理413.
2.
2RED算法实现·413.
2.
3RED的优点和存在的问题·433.
3随机公平队列·443.
4令牌桶过滤器·453.
4.
1TBF原理·453.
4.
2TBF算法实现46第4章有分类的流量控制算法·504.
1基于类的队列·504.
1.
1CBQ原理·514.
1.
2CBQ算法的实现·524.
2分层令牌桶·544.
2.
1HTB原理544.
2.
2HTB算法的实现564.
3PRIO队列规定·58第5章多链路流量控制算法·605.
1负载均衡与流量控制605.
1.
1流量工程·605.
1.
2服务质量与路由优化方法·625.
2多逻辑链路间共享令牌调度流量负载模型655.
2.
1多逻辑链路共享令牌调度模型·655.
2.
2多逻辑链路共享令牌调度方法·655.
2.
3多逻辑链路共享令牌调度模型求解665.
2.
4多逻辑链路共享令牌调度算法设计675.
3多链路时延反馈共享令牌流量拥塞控制算法685.
3.
1基于时延反馈的流量拥塞控制模型685.
3.
2基于时延反馈的流量拥塞控制方法69第6章异常流量检测算法·726.
1网络异常流量检测概述726.
1.
1网络流量异常的分类726.
1.
2网络流量异常的检测方法·73目录·v·6.
2基于Netflow数据的典型异常流量检测·766.
2.
1基本概念·776.
2.
2基本分析·786.
2.
3深度分析·786.
3基于CUSUM算法的网络异常流量检测·826.
3.
1CUSUM算法简介826.
3.
2基于非参数CUSUM算法检测DDoS攻击异常流量·836.
4基于特征聚类的异常流量检测和过滤算法866.
4.
1常见异常流量特征分析·876.
4.
2异常流量特征聚类算法·88第7章自适应流量控制算法·927.
1自适应动态带宽分配策略927.
1.
1策略与排队模型·927.
1.
2排队模型分析947.
1.
3系统性能指标分析·967.
2基于网络处理器的流量控制算法·987.
2.
1网络处理器介绍·987.
2.
2基于网络处理器的动态带宽分配算法·1007.
2.
3DBAA-NP算法的实现102第8章网牧系统介绍·1128.
1网牧系统概述·1138.
2网牧系统总体结构114第9章网牧实名制体系设计·1159.
1几种身份与位置分离映射的机制·1159.
1.
1IP地址的身份与位置双重属性·1159.
1.
2主机标识协议1179.
1.
3标识位置网络协议·1239.
2标识与位置分离映射机制介绍·1269.
2.
1标识分离与映射总体模型·1269.
2.
2标识分离与映射的网络设计1289.
2.
3标识分离与映射模型和设计的优势1329.
2.
4各种身份与位置分离方案的对比与分析·1349.
3网牧实名制的体系设计与实现·1359.
3.
1软件结构·135网络流量整形与带宽控制技术·vi·9.
3.
2处理流程·1369.
3.
3内核模块程序分析·1369.
3.
4守护进程程序分析·175第10章网牧服务质量保障体系设计18110.
1几种服务质量保障模型介绍·18110.
1.
1IntServ模型18110.
1.
2DiffServ模型·18310.
1.
3IntServ模型与DiffServ模型比较18410.
2面向资源的服务标识模型18510.
2.
1服务标识设计·18510.
2.
2新映射系统设计18710.
2.
3新映射系统解决数据迁移问题18810.
2.
4连接建立阶段面向资源的设计19310.
2.
5选路传输阶段面向资源的设计19410.
3网牧服务体系设计与实现19510.
3.
1软件结构19510.
3.
2处理流程19610.
3.
3内核模块程序分析·19710.
3.
4守护进程程序分析·207第11章网牧智能化服务体系设计·23511.
1网牧服务智能化体系模型23711.
1.
1普适计算与服务发现·23711.
1.
2网络融合与服务发现·23811.
1.
3IMS体系架构·23911.
1.
4网牧服务映射和发现模型·24011.
2网牧多网融合平台设备的设计与实现·24211.
2.
1软件结构24211.
2.
2处理流程24211.
2.
3内核模块程序分析·24411.
2.
4守护进程程序分析·259参考文献264第1章流量整形与带宽控制1.
1TCP/IP协议族简介TCP/IP协议族起源于20世纪60年代末美国政府资助的一个分组交换网络研究项目,到20世纪90年代已发展成为计算机之间最常应用的组网形式.
它并不完全符合OSI的七层参考模型.
TCP/IP协议族的分层模型和OSI分层模型如图1.
1所示.
图1.
1TCP/IP协议族的分层模型和OSI分层模型(1)数据链路层,有时也称为物理层或网络接口层,通常包括操作系统中的设备驱动程序和计算机中对应的网络接口卡.
它们一起处理与电缆(或其他任何传输媒介)的物理接口细节.
(2)网络层,有时也称为互联网层,处理分组在网络中的活动,如分组的选路.
在TCP/IP协议族中,网络层协议包括IP(网际协议)、ICMP(互联网控制报文协议)和IGMP(互联网组管理协议).
(3)运输层主要为两台主机上的应用程序提供端到端的通信.
在TCP/IP协议族中,有两个互不相同的传输协议:TCP(传输控制协议)和UDP(用户数据报协议).
(4)应用层负责处理特定的应用程序细节.
几乎各种不同的TCP/IP实现都会提供下面这些通用的应用程序:Telnet(远程登录)、FTP(文件传输协议)、SMTP(简单邮件传送协议)、SNMP(简单网络管理协议)等.
本书第2章介绍Linux系统的网络过滤和连接分析,9.
3.
3节介绍了Linux网络代码中一个非常重要的数据结构sk_buff,这些都需要读者掌握TCP/IP的分层与数据封装.
下面对TCP/IP的分层与封装作一简短的描述,详细的描述请参考文献[1]~[3].
网络流量整形与带宽控制技术·2·1.
1.
1TCP/IP的分层与封装本节以以太网为例,描述TCP/IP的分层与封装.
图1.
2所示为以太网的分层结构图.
(1)数据链路层的以太网驱动程序负责接收以太网数据帧,剥离以太网数据帧的首部信息,形成IP数据报、ARP或RARP分组.
根据以太网数据帧的上层协议类型分别交付给上一层,如果是IP数据报则被送交网络层.
(2)网络层在接收以太网驱动程序送到的IP数据后按照IP数据帧中的协议种类对数据进行处理,去掉IP首部数据,形成TCP、UDP或ICMP报文.
如果得到TCP或UDP报文,则把数据报交付给运输层,否则对ICMP报文进行处理.
(3)运输层在得到UDP报文后按照UDP中的端口号分别送给不同的应用程序.
若运输层得到TCP报文,则要根据TCP的状态转换图进行处理.
(4)UDP或TCP进行协议处理、校验等处理后,根据端口号调用相应的应用程序.
ARP和RARP提供逻辑地址和物理地址之间的动态转换,发送站必须有接收站的物理地址才能完成报文的传输.
应用层的数据在网络中进行传输时就必须按照以太网的帧格式进行封装,而且这是一个逐级封装的过程.
数据封装过程如图1.
3所示.
图1.
3数据封装示意图由于UDP、TCP、ICMP等协议都可以向网络层传送数据,所以IP数据报中必须对IP的上层协议进行标识.
图1.
2以太网分层结构图第1章流量整形与带宽控制·3·网络层的IP和ARP都可以向数据链路层传送数据,所以也必须在以太网的帧首部中加入指明数据来源的类型域.
下面对IP层协议以及UDP和TCP首部结构进行简单介绍.
1.
1.
2IP、UDP、TCP首部结构1.
IP首部结构IP数据报的格式如图1.
4所示.
普通的IP首部长20字节,除非含有选项字段.
图1.
4IP数据报格式特别需要注意的是,IP选项很少被使用,并非所有的主机和路由器都支持这些选项.
选项字段一直都是以32位作为界限,在必要的时候插入值为0的填充字节.
这样就保证了IP首部始终是32位的整数倍(这是首部长度字段所要求的).
2.
UDP首部结构UDP数据报封装成一份IP数据报的格式如图1.
5所示.
图1.
5UDP封装UDP首部的各字段如图1.
6所示.
图1.
6UDP首部网络流量整形与带宽控制技术·4·3.
TCP首部结构TCP首部结构如图1.
7所示.
图1.
7TCP报文段首部格式1.
2流量整形与带宽控制的基本原理流量整形(trafficshaping)与带宽控制(trafficcontrol)是一种对流量进行控制的手段,就是对网络流量进行识别和控制,避免网络产生不必要的拥塞和掉线.
流量整形是一种主动调整流量输出速率的措施.
流量整形的典型作用是限制流出某一网络的某一连接的流量与突发,使这类报文以比较均匀的速度向外发送.
流量整形通常使用缓冲区和令牌桶来完成.
当报文的发送速度过快时,首先在缓冲区进行缓存,在令牌桶的控制下再均匀地发送这些被缓冲的报文.
流量整形的一个典型应用是基于下游网络节点的流量指标来控制本地流量的输出.
带宽控制是一种限制流量输出速率的措施.
带宽控制的作用是控制某个数据源(主机或某类应用)的发送速率,当这类报文的发送速率超过预定指标时,将其丢弃.
流量整形与带宽控制的主要区别在于,流量整形对流量监管中需要丢弃的报文进行缓存,通常是将它们放入缓冲区或队列内.
当令牌桶有足够的令牌时,再均匀地向外发送这些被缓存的报文.
流量整形与带宽控制的另一区别是,整形可能会增加延迟,而带宽控制几乎不引入额外的延迟,但会增加额外的丢包率.
1.
2.
1拥塞与流量控制拥塞是一种持续过载的网络状态,此时用户对网络资源(包括链路带宽、存储空间和处理器处理能力等)的需求超过了其固有的容量.
就Internet的体系结构而言,拥塞的发生是其固有的属性.
因为在事先没有任何协商和请求许可机制的资源共享网络中,几个IP分组同时到达路由器,并期望经过同一个输出端口转发的可能性是存在的.
显然,不是所有的分组都可以同时接受处理,必须有一个服务顺序,中间节点上的缓存为等候服务的分组提供了一定保护.
然而,如果此状况具有一定的持续性,当第1章流量整形与带宽控制·5·缓存空间被耗尽时,路由器只有丢弃分组.
表面上,增大缓存总可以防止由于拥塞引起的分组丢弃,但随着缓存的增加,端到端的时延也相应增大,这是因为分组的持续时间有限,超时的分组同样需要重传.
因此,过大的缓存空间有可能妨碍拥塞的恢复,有效分组白白浪费了网络的可用带宽.
拥塞导致的直接结果是分组丢失率提高,端到端时延加大,甚至有可能使整个系统发生崩溃.
当网络处于拥塞崩溃状态时,微小的负载增量都将使网络的有效吞吐量(goodput)急剧下降.
负载与吞吐量之间关系如图1.
8所示.
当负载较小时,吞吐量与负载之间呈线性关系;到达膝点之后,随着负载的增加,吞吐量的增量逐渐变小;当负载超过崖点之后,吞吐量却急剧下降.
通常将膝点附近称为拥塞避免区间,膝点和崖点之间是拥塞恢复区间,而崖点之外是拥塞崩溃区间.
为最大限度地利用资源,网络工作在轻度拥塞状态时应该是较为理想的,但这也增加了滑向拥塞崩溃的可能性,因此需要一定的拥塞控制机制加以约束和限制.
可以从两个方面考虑如何解决拥塞问题:一是增加网络资源,二是降低用户需求.
前者一般通过动态配置网络资源来提高系统容量.
例如,在高峰期增加接入线路,在卫星链路上增加发射功率来提高可用带宽,通过路径分裂,用多条不同的物理路径来满足用户需求.
而降低用户需求主要表现在3个方面:拒绝服务、降低服务质量和调度.
(1)拒绝服务:在拥塞发生时,拒绝接纳新的用户请求,如电话网中的忙音.
此方法多用于面向连接的网络.
(2)降低服务质量:在拥塞发生时降低所有用户(包括新用户)的发送速率,如分组交换网络中的滑窗算法等.
(3)调度:合理安排用户对网络资源的利用,保证总需求永远小于网络可用资源,如轮询、加入优先级、资源预留等.
降低用户需求的具体机制与策略是多种多样的,选择何种策略依据拥塞的严重程度和持续时间而定.
表1.
1描述了拥塞持续时间和选择拥塞控制方法之间的关系.
对频繁拥塞的网络,最好的方法是重新规划和设计,以匹配需求的模式;对偶发的适度拥塞,连接接纳控制是一种有效的措施;对拥塞持续时间少有连接持续时间的情形,端-端策略是可行的.
例如,在连接建立时,通过协商确定网络可以支持的业务量参数,借助漏桶算法实施监督、丢弃或标记分组,以防止用户对网络资源的无约束争用而可能导致的拥塞.
图1.
8负载与吞吐量之间的关系网络流量整形与带宽控制技术·6·表1.
1拥塞持续时间与拥塞控制机制的关系拥塞持续时间拥塞控制机制长短链路容量规划、网络设计连接接纳控制基于负载的动态路由内容动态压缩端-端反馈链路-链路反馈缓存实现服务质量(QualityofService,QoS)的一种方法是按照服务水平的要求分配资源给每一个数据流.
这种采用"资源预留"进行带宽分配的方法并不适合"尽力而为"型应用.
由于带宽资源是有限的,QoS的设计者引入了优先级概念,使得在资源预留后"尽力而为"服务的数据流的传输也能得到一定的保障.
因此,IPQoS可以分为两种基本类型.
(1)基于资源预留:网络资源按照某个业务的QoS要求进行分配,制定资源管理策略.
互联网工程任务组(InternetEngineeringTaskForce,IETF)提出的综合服务(IntegratedServices,IntServ)体系结构便是基于这种策略的,资源预留协议(ResourceReservationProtocol,RSVP)是其核心部分.
(2)基于优先级:网络边界节点对业务流进行分类、整形、标记.
核心节点按照资源管理策略分配资源,对QoS要求高的业务给以优先处理.
IETF提出的区分服务(DifferentiatedServices,DiffServ)便是基于这种策略的.
这些QoS方法可以被用于单个数据流或聚集的数据流(aggregateflow).
根据应用的数据流的不同,IPQoS可以分为以下两类.
(1)用于单个数据流:单个数据流为在两个应用(发送者和接收者)之间的单个的、单向的数据流.
可以用传输协议、源地址、源端口号、目的地址和目的端口号这5种参数来分类.
(2)用于聚集的数据流:聚集的数据流由两个或更多单个数据流组成,这些流在一个或多个参数、标记或优先数以及一些认证信息方面有一些共同点.
为了解决IPQoS问题,IETF已经提出了几种服务模型和机制,主要有如下3类.
(1)综合服务和资源预留协议(IntServ/RSVP):以RSVP信令向网络提出业务流传输规格(Flow-Spec),并建立和拆除传输路径上的业务流状态.
主机和路由器节点建立和保持业务流状态信息.
尽管RSVP经常用于单个数据流,但也用于聚集的数据流的资源预留.
(2)区分服务(Diffserv):在区分服务网络中,边界路由器根据用户的流规格(streamprofile)将用户流划分为不同的级别,再聚合成流聚集,聚集信息存放在IP包头的DS标记域,称为DS标记(DifferentiatedServicesCodePoint,DSCP).
内部节点则根据DSCP提供不同质量的调度转发服务.
第1章流量整形与带宽控制·7·(3)多协议标记交换(Multi-ProtocolLabelSwitching,MPLS):根据分组头的标记,通过网络路径控制提供流聚集带宽管理的子网带宽管理(SubnetBandwidthManagement,SBM);负责OSI第二层(数据链路层)的分类和优先级排列,同IEEE802网络进行共享和交换.
1.
2.
2国内外研究现状网络流量控制作为一种控制技术,其目的就是通过网络设备的配置达到基于用户、网段、应用或端口的流量控制.
它是一种使得目的端实体可以调节源端实体协议数据单元流量的控制机制,同时它也是为了防止网络拥塞和死锁的出现而采取的一种措施.
流量控制按照一系列标准区分用户流量,然后为每种数据包或者会话指定不同的优先级,最后按照优先级来传输.
同时,它能够跟踪每个应用程序所使用的实际带宽,并对每种流量模式可以使用的带宽进行限制或保证.
当前广泛部署的网络流量控制系统主要包括四部分:流量分类、队列管理、分组调度和流量整形.
流量分类是按照不同的优先级或者控制策略,将数据包注入到不同队列.
当前的流量分类技术主要分为基于端口、会话和内容的识别方式.
其经典算法包括Lakshman等提出的BV(BitVector)算法[4],Baboescu等提出的ABV(AggregatedBitVector)算法[5],以及LiJi等提出的改进型ABV算法、AFBV算法[6].
队列管理通过控制队列的平均深度来避免拥塞发生.
对于主动队列管理,常用的算法有RED(RandomEarlyDetection)[7]算法及其改进算法WRED和ECN(ExplicitCongestionNotification)算法.
RED算法简单且便于实现,因此被现有的大多数路由器所采用.
分组调度控制不同类型的分组对链路带宽的利用,使不同的数据流得到不同等级的服务.
相关算法有基于静态优先级的PQ(PriorityQueuing)算法、FQ(FairQueuing)算法、WFQ(WeightFairQueuing)算法、针对轮询的WRR(WeightedRoundRobin)[8]算法以及DWRR(DeficitWeightedRoundRobin)算法等.
流量整形使经过网络瓶颈的数据包平缓地注入主干网,减少数据包在边缘网关排队等待的时间,从而减少边缘网关缓存的大小和数据包丢失率.
流量整形主要采用两种基本方法:漏桶(LeakyBucket)算法和令牌桶(TokenBucket)算法.
另外,AmitAggarwal等提出的TCPPacing、Karandikar等提出的TCR算法[9],以及WeiHuanyun等提出的改进型TCR算法PostACK[10],都能够实现网络流量整形.
流量整形与带宽控制的研究目标是有效地为用户提供端到端的服务质量控制或保证.
QoS是指网络单元(如应用程序、主机或路由器)能够在一定级别上确保它的业务流和服务要求得到满足.
QoS并没有创造带宽,只是根据应用程序的需求以及网络状况管理带宽.
IPQoS有一套性能参数,主要包括如下几点.
网络流量整形与带宽控制技术·8·(1)业务可用性:用户到Internet业务之间连接的可靠性.
(2)传输延迟:指两个参照点之间发送和接收数据包的时间间隔.
(3)可变延迟:也称为延迟抖动(jitter),指在同一条路由上发送的一组数据流中数据包之间的时间差异.
(4)吞吐量:网络中发送数据包的速率,可用平均速率或峰值速率表示.
(5)丢包率:在网络中传输数据包时丢弃数据包的最高比率.
1.
3典型流量整形与带宽控制的方法1.
3.
1TCP流量控制目前,Internet上约95%的数据流使用TCP,非弹性的UDP业务只占据了很小的份额,围绕着TCP流量控制的拥塞控制一直是研究热点之一.
在Internet设计初期,对于拥塞的控制是通过TCP中端到端基于滑窗的流量控制完成的.
1988年,VanJacobson指出了TCP在控制网络拥塞方面的不足,并提出"慢开始"和"拥塞避免"算法,它们被所有的Internet主机支持.
在很长一段时间内,接收端驱动的TCP流量控制是唯一可行的拥塞控制方法,这也就是"流量控制"和"拥塞控制"经常混淆的原因.
实际上,前者只是后者的一种技术实现途径而已.
TCP使用慢开始、拥塞避免、快重传和快恢复等窗口管理机制进行流量控制,避免大量不合理的网络流量产生,有效地防止了网络状态从轻度拥塞滑向拥塞崩溃.
TCP是针对Internet的尽力服务提供方式设计的运输层协议,它采用丢包触发、窗口控制、加法递增乘法递减的拥塞控制机制来控制流量.
1.
TCP滑窗机制为提高报文的传输效率,TCP采用大小可变的滑动窗口进行流量控制.
窗口大小的单位是字节(B).
在TCP报文段首部的窗口字段中写入的数值就是当前给对方设置的发送窗口数值的上限.
发送窗口在连接建立时由双方商定.
但在通信的过程中,接收端可根据自己的资源状况,随时动态地调整对方的发送窗口上限值(可增大或减小).
图1.
9所示为TCP中窗口的概念.
图1.
9(a)表示发送端要发送900B的数据,划分为9个100B的报文段,而发送窗口确定为500B.
发送端只要收到了对方的确认,发送窗口就可前移.
发送TCP要维护一个指针.
每发送一个报文段,指针就向前移动一个报文段的距离.
当指针移动到发送窗口的最右端(窗口前沿)时就不能再发送报文段了.
图1.
9(b)表示发送端已发送了400B的数据,但只收到对前200B数据的确认,同时窗口大小不变.
这里注意,现在发送端还可发送300B.
图1.
9(c)表示发送端收到了对方当前400B数据的确认,但对方将窗口减小到了400B.
于是,发送端最多还可发送400B的数据.
第1章流量整形与带宽控制·9·发送端利用发送窗口(这个窗口取决于对方的接收窗口)调节向网络注入分组的速率,不仅仅是为了使接收端来得及接收,而且还是为了对网络进行拥塞控制.
从这个角度看,拥塞控制的目标就是将网络中的分组数量维持在一定的水平之下.
若网络中的分组数量超过这个水平,那么网络的性能就会急剧恶化.
图1.
9TCP中窗口概念示意图2.
TCP窗口管理发送端的主机在确定发送报文段的速率时,既要根据接收端的接收能力,又要从全局考虑不要使网络发生拥塞.
因此,对于每一个TCP连接,需要有以下两个状态变量.
(1)接收窗口(rwnd).
这是接收端根据其目前的接收缓存大小所许诺的最新的窗口值,是来自接收端的流量控制.
接收端将此窗口值放在TCP报文首部中的窗口字段,传送给发送端.
(2)拥塞窗口(cwnd).
这是发送端根据自己估计的网络拥塞程度而设置的窗口值,是来自发送端的流量控制.
在发送时,发送端并不能确定拥塞窗口的大小,因此发送端确定拥塞窗口的原则是:只要网络没有出现拥塞,发送端就使拥塞窗口再增大一些,以便将更多的分组发送出去;但只要网络出现拥塞,发送端就使拥塞窗口减小一些,以减小注入到网络中的分组数.
由于在发送拥塞时,路由器要丢弃分组,所以只要发送端没有按时接收到应当到达的确认报文ACK,就可以认为网络出现了拥塞.
网络流量整形与带宽控制技术·10·综上所述,发送端的发送窗口的上限值应当取为接收窗口rwnd和拥塞窗口cwnd这两个变量中较小的一个,即发送窗口上限值=min(rwnd,cwnd).
当rwndssthresh时,停止使用慢开始算法,改用拥塞避免算法;(3)当cwnd=ssthresh时,既可以使用慢开始算法,也可使用拥塞避免算法.
拥塞避免的机制是,一旦探测到拥塞超时,进行如下操作.
(1)将慢开始门限ssthresh设为当前拥塞窗口的一半,即ssthresh=cwnd/2.
(2)置cwnd=1,并启动慢开始过程,直至cwnd=ssthresh.
在该阶段,cwnd每收到一个ACK就加1.
(3)当cwnd>ssthresh时,则每经过一个往返时延就对cwnd加1.
图1.
10(b)示意了拥塞避免机制.
当拥塞超时发生时,ssthresh的值被设置为8,在达到该值之前,TCP使用指数慢开始过程来扩展拥塞窗口;在此之后,cwnd则按线性规律增加.
相比图1.
10(a),将cwnd恢复到最初需要花4个往返时延(RTT),而图1.
10(b)中要花11个RTT.
快重传和快恢复是对网络拥塞控制算法的改进.
起初,TCP窗口管理只包含了慢开始和拥塞避免两种算法,后来为了完善性能,又增加了快重传和快恢复算法,形成了TCPTahoe、TCPReno和TCPSACK等多种版本.
快重传算法规定,发送端只要一连收到3个重复的ACK即可断定有分组丢失了,就应立即重传丢失的报文段,而不必继续等待为丢失报文段设置的重传计时器的超时.
快重传和快恢复算法一般同时使用.
当收到3个重复ACK时,TCP最后进入的不是拥塞避免阶段,而是快速恢复阶段.
快恢复的思想是"数据包守恒"原则,即同一个时刻在网络中的数据包数量是第1章流量整形与带宽控制·11·恒定的,只有当"老"数据包离开了网络后,才能向网络中发送一个"新"数据包.
如果发送方收到一个重复的ACK,那么根据TCP的ACK机制,表明有一个数据包离开了网络,于是cwnd加1.
如果能够严格按照该原则执行,那么网络中很少会发生拥塞,事实上拥塞控制的目的也就在于修正违反该原则的地方.
图1.
10慢开始和拥塞避免快恢复的主要步骤如下.
(1)当收到3个重复ACK时,把ssthresh设置为cwnd的一半,把cwnd设置为ssthresh的值加3,然后重传丢失的报文段,加3的原因是收到3个重复的ACK,表明有3个"老"数据包离开了网络.
(2)当再收到重复的ACK时,cwnd加1.
(3)当收到新的数据包的ACK时,把cwnd设置为步骤(1)中的ssthresh的值.
原因是该ACK确认了新的数据,说明从重复ACK时开始传输的数据都已收到,该恢复过程已经结束,可以回到恢复之前的状态了,即再次进入拥塞避免状态.
网络流量整形与带宽控制技术·12·3.
TCP重传机制超时重传是TCP保证数据可靠性的另一个重要机制,其原理是在发送某一个报文段以后就开启一个计时器,在一定时间内如果没有得到发送的报文段的ACK,那么就重新发送报文段,直到发送成功为止.
由于TCP的下层是一个互联网环境,其中可能有高速局域网,也可能经过多个低速广域网,并且IP数据报所选择的路由还可能发生变化,时间设置得过短,则许多报文段的重传时间就太早了,给网络增加了许多不应有的负荷;但若超时时间设置得太长,则又会使网络的传输效率降低.
为此,TCP采用了一种自适应算法.
将发送报文段时间和收到相应确认报文段的时间差作为报文段的往返时延(RTT).
将各个报文段的往返时延样本加权平均,就得到报文段的平均往返时延.
并且,每测量到一个新的往返时延样本,就重新计算一次平均RTT.
平均RTT(RTT)(1R)()TTαα*+*=旧的新的样本若α接近于1,则表示新算出的平均RTT和原来的值相比变化不大,RTT更新较慢.
若α接近于0,则表示加权计算的平均RTT受新的RTT的影响较大,RTT更新较快.
显然,计时器设置的超时重传时间(RTO)应略大于平均RTT,即RTORTTβ=*平均β显然是一个大于1的系数.
β很接近于1,发送端可以及时地重传丢失的报文段,因此效率得到提高.
但若报文段并未丢失而仅仅是增加了一点时延,那么过早地重传未收到确认的报文段,反而会增加网络的负担.
因此,TCP的β一般取值为2.
实际的往返时间测量十分复杂,如图1.
11所示.
图1.
11往返时延测量TCP报文段1发出后,由于重传时间到了,所以重发报文段1(即图中报文段2);经过一段时间后,收到了确认报文段ACK,但无法判断是对报文段1的确认还是对重传报文段2的确认,这会造成往返时延和重传时间难以确认.
因此,Karn提出了一个算法:只要报文段重传了,就不采用其往返时延样本.
这样得出的平均往返时延和重第1章流量整形与带宽控制·13·传时间就比较准确.
同时,为了避免往返时延的突然增大而造成的重传时间无法更新,对Karn算法进行了修正:报文段每重传一次,就将重传时间增大一些;当不再发生报文段的重传时,才根据报文段的往返时延更新平均往返时延和重传时间的数值.
4.
TCP自同步机制自同步机制是TCP流量控制中的一个重要机制,它和"加性增加倍乘减小"一起构成了TCP拥塞控制的基础.
TCP源端的发送速率可由ACK的速率确定,但ACK的到达速率由源端与目的端直接往返路径上的瓶颈确定,该瓶颈可能是网络,也可能是目的端本身.
图1.
12描述了TCP的自同步机制.
图1.
12TCP自同步机制图1.
12(a)表示瓶颈出现在网络中.
网络被抽象为一个连接源端和目的端的管道.
管道的粗细与数据传输速率成比例.
连接源端和目的端的链路都是高速链路,中间较细一段管道代表形成瓶颈的低速链路.
每个报文段都用一个矩形表示,其中矩形的面积与报文段中所含的比特数成比例.
这样,当一个报文段被压进一条较细的管道时,它就会在时间上扩展开来.
时间Pb表示最慢链路上的最小报文段的间隔.
当报文段到达目的端时,即使数据速率增加,此间隔也将保持不变,这是因为到达间隔时间没有变化的缘故.
因此,接收方的报文段间隔Pr就等于Pb.
如果目的端在报文段到达时就作出确认,那么ACK报文段离开接收方的间隔就由报文段到达间隔决定,所以有ArPr=.
因为时隙Pb对ACK报文段肯定足够大,所以AbAr=,这样返回的ACK就起到同步信号的作用,使得在稳定状态时,发送方的报文速率和ACK到达速率相网络流量整形与带宽控制技术·14·匹配,即发送方的报文段速率等于其传送路径上最慢链路的速率.
这样一来,TCP就能自动感知网络瓶颈,并对其流量作出调整.
这种自同步机制在瓶颈处于接收方时也同样有效.
接收方由于其本身的处理能力或者其他连接上到来的报文段造成的压力,不能及时接收给定连接上的报文段.
如图1.
12(b)所示,假定网络中的最慢链路的带宽相对较高,大约是源端数据速率的一半,但目的端的管道较窄.
此时,ACK的发送速率就等于目的端的接收能力,通过ACK流速控制源端的速率,保证报文段只能以目的端可以处理的速率到达.
这表明了一个重要的事实:源端无法知道ACK的同步速率反映的是网络的负载情况,还是目的端的处理状态.
如果因为网络拥塞而导致ACK的到达变慢,那么源端应该以比ACK速率更慢的速率传输报文段,以缓解网络的拥塞状态;但如果是由于目的端处理能力的限制导致ACK速率变小,那么发送端以目前的速率传输报文段是恰当的.
1.
3.
2队列管理技术从排队论的角度来看,可以把分组流经网络传输节点的过程用顾客-服务器模型来描述.
而在网络传输节点的控制策略中设置队列缓冲的目的旨在通过一定程度上增大顾客的等待时间——分组的排队延迟,提高服务器的利用率——输出链路的带宽利用率.
随着网络技术的发展,用户对基于网络的实时、多媒体应用的兴趣和需求在不断提高,如何发展、规划、改造现有的网络,以适应这样的变化,满足用户多样的需求也成为研究领域和业界亟待解决的问题.
基于多队列的控制方案在业务隔离、资源公平分配等方面表现出极大的优势,已经成为网络传输控制的必然选择.
这里的队列管理是指对网络传输节点中队列缓冲资源的管理和分配,即缓冲管理.
在分组传输过程中,数据流经的网络传输节点通常采用队列缓存、延迟转发的服务方式提高输出链路的带宽利用率.
缓冲管理机制在分组到达队列前端时,依据一定的策略和信息来决定是否允许该分组进入缓冲队列,从另一个角度看,也就是作出是否丢弃该分组的决策,因此也称为丢弃控制.
就单个网络传输节点而言,其控制目标在于解决输出链路的带宽资源分配问题,把有限的资源公平而有效地分配给不同的服务类别(或用户流等).
而在众多网络传输节点构成的传输网的基础上,网络传输控制需要整合、规划所有的网络带宽资源的使用,为用户提供端到端的有服务质量保证的网络传输服务.
带宽资源的分配在网络传输节点上主要通过基于多个队列的分组调度机制来实现.
虽然缓冲管理机制直接涉及节点中的队列缓冲资源,直接的影响也只是分组丢失率性能,然而其对系统带宽分配的性能有着不可忽视的影响.
(1)合理的系统队列缓冲容量,对于平衡系统吞吐量和分组排队延迟起着至关要的作用.
第1章流量整形与带宽控制·15·(2)在多队列情况下,缓冲资源在不同队列之间的分配只有在与输出带宽的分配相互一致时,才能获得最佳的缓冲效果.
因此,更多的研究者注意到,把传统上相互独立、缺乏联系的缓冲管理机制和分组调度机制相结合,研究更优的资源分配方案,以期获得更优的系统性能.
如何与分组调度机制有效地配合,解决网络带宽资源的有效、公平分配问题,是缓冲管理机制的关键.
网络传输控制中通常采用的队列结构模型是为了提高输出链路的带宽利用率而设置的.
队列缓冲的设置使链路的带宽利用率和系统吞吐量得以改善,然而同时也增大了分组排队延迟,在队列缓冲空间的容量增大时情况尤为严重.
传统的Internet提供的数据传输业务只保证数据的正确性和完整性,并不提供基于数据传输延迟的保障.
而随着网络实时应用的发展,用户对数据传输延迟的要求越发苛刻,要求网络传输业务能够提供尽可能低的、稳定的传输延迟.
而分组在网络中传输遭遇的延迟的最主要部分,也是最容易控制好的部分,就是源于网络传输节点的排队延迟.
另外,从用户的角度来看,缓冲管理方案是一种接纳控制策略.
通常情况下,网络资源总是相对有限的,无法完全满足用户需求.
因此,不同用户间网络资源的公平分配成为必需且必要的手段.
但队列公平性的解决依赖于系统流量控制的粒度,只有基于用户流的细粒度控制才能完全解决公平性问题,这同时也带来了控制方案的复杂度和系统的可扩展性问题.
因此,如何保证队列间的公平性,如何设置合适的队列缓存空间容量,如何在网络运行期间合理地控制队列长度的动态变化,以及平衡系统吞吐量和分组排队延迟之间的矛盾,是缓冲管理乃至整个网络流量控制需要解决的重要问题.
本书第3章和第4章重点介绍几种队列管理算法.
1.
3.
3分组调度技术分组调度是实现网络流量控制的核心机制之一,是网络资源管理的重要内容,通过控制不同类型的分组对链路带宽的利用,使不同的数据流得到不同等级的服务.
分组调度的基本过程是根据一定的系统信息作出判断,控制各个队列占用链路带宽的频率,进而影响带宽分配、时延和时延抖动等.
如图1.
13所示,典型地,分组调度发生在路由器去往下一个路由器或主机的输出接口,但可以潜在地存在于路由器内部的任何发生资源竞争而需要排队等待调度的地方.
当一个分组到达网络节点后,分类器根据分组的上下文和粒度确认它所在的队列,分组进入相应队列排队等候,直至调度器将其选择发送.
分组调度规定了分组从每个队列离开的瞬时特性,通过流隔离,使得不同业务类的分组得到不同等级的服务.
具体表现为带宽分配、时延范围与抖动控制、不同业务类之间公平性和相对优先级.
网络流量整形与带宽控制技术·16·图1.
13队列调度(1)带宽分配:一个调度器可为特定业务类提供最低的带宽保证,以确保分组规则地从该类所在队列中取出(即确保队列被规则地服务).
一个调度器也可以用来进行速率整形以限制该类的队列被服务的频率.
根据调度器设计,它可能对每一队列既强调上限带宽又强调下限带宽,或对某些队列只强调上限或只强调下限带宽.
(2)时延控制:某些实时业务要求严格的时延范围保证和抖动控制,而某些非实时业务则需要较宽松的时延控制.
对于某个业务类,其平均服务速率R(s)与经历的排队时延D存在着关系Q=D*R(s),其中s为统计的时长;Q为该类所在队列的平均长度.
这个关系可以从以下两个方面来理解.
①对于具有一定到达速率的业务类,在不考虑分组丢失的情况下,带宽分配可以通过时延特性来反映.
②调度器通过控制各个业务类的速率分配,来实现对时延特性的控制.
(3)相对优先级控制:调度器使得重要的分组得到最好的服务,次要的分组得到较差的服务,表现出使用资源的一定的相对优先级.
这种优先级关系可以在系统初始化时设置为静态优先级,也可以在运行过程中根据系统状态进行调节,即计算动态优先级.
下面介绍三种常用的分组调度算法.
1)基于静态优先级的算法常见的基于静态优先级的分组调度算法是PQ算法.
它给每个队列赋予不同的优先级,在每次需要调度时,具有最高优先级的非空队列中的分组最先选择服务.
如果最高优先级队列为空,则服务具有次优先级的队列,如此类推.
这样,最重要的分组就能得到最好的服务,如最小的时延.
此类算法简单,容易实现,然而在高优先级队列源源不断地有分组到达时,低优先级的队列容易被"饿死",即在很长时间内得不到服务,因而公平性很差.
2)基于轮询的算法常见的基于轮询的算法有WRR和DRR(DeficitRoundRobin).
WRR算法给队列赋予不同的权值,代表一次完整循环队列被服务的分组数.
同时为每个队列维护一个计数器,初始化为权值.
每次轮询时,计数器为非零的队列发送一个分组,并把计数器减1.
当所有队列的计数器均为零时,重置为零值.
WRR算法可以更灵活地控制带宽第1章流量整形与带宽控制·17·在不同队列的分配,而且能以比较平滑的方式调度输出业务,但存在由于分组变长带来的不公平性.
为了解决WRR算法中由于分组变长带来的不公平性,DRR算法以字节为单位为每个队列分配一个带宽配额,该配额的比例对应于队列服务速率的比例.
同时,为每个队列维护一个计数器,初始化为其带宽配额.
每次轮询时,如果待发送分组长度小于或等于计数器值,则允许发送,并把计数器减去此分组长度值;如果待发分组长度大于计数器值,则检查下一个队列,同时把该队列计数器的差值累计到下一次循环.
DRR由于考虑了分组变长这一信息,很好地解决了带宽分配的公平性问题;但缺陷是不能很好地满足业务的时延特性,不能像WRR那样以较为平滑的方式调度输出.
3)分层链路共享算法常见的分层链路共享算法有CBQ(Class-BasedQueuing)[11]、H-PFQ(HierarchicalPacketFairQueuing)[12]等.
"链路共享"反映了在总体资源有限的情况下,为提高资源利用率,并在多个业务之间公平、合理地分配资源的要求.
从不同角度来看,链路共享存在多种情况.
例如,同一链路可以被多个公司、组织或代理共享,也可以被IP、SNA等多种协议共享,还可以被WWW、FTP、Telnet等多种应用共享.
随着网络规模的发展,单一层次的链路共享方式已不能满足复杂的系统要求.
因此,导致了分层链路共享策略的出现.
分层链路共享把不同类型的业务流划分成不同级别的类,并同时考虑业务的实时性和链路共享的需求,按照不同的层次进行分组调度,从而提供了在分层共享树内进行不同等级的共享链路带宽资源的方法.
为实现这一控制目标,系统需要设计两级调度器:常规调度器和链路共享调度器.
当系统没有出现拥塞时,使用常规调度器,使各类业务都能得到所需要的服务.
这里常规调度器可以采用许多具体的分组调度算法,如轮询调度、静态优先级调度等.
当系统出现拥塞时,启动链路共享调度器,对某些超出其额定带宽的业务类进行限制,对其"规范化".
这样,就能够在保持高链路资源利用率的情况下提供很好的带宽、时延保证和公平性.
本书第4章会详细介绍CBQ算法.
1.
3.
4流量整形技术在数据传输过程中,路由器将根据传输效果好的传输模式对流量进行整形.
传输整形是指调整数据传输的平均速率,使数据按照传输模式规定的速率进行传输,尽量避免突发性通信量导致的拥塞问题.
流量整形主要采用两种基本方法:漏桶(LeakyBucket)算法和令牌桶(TokenBucket)算法.
1)漏桶算法漏桶算法是将流量整形操作形象地比喻成一个底部带有一个小孔的水桶,无论流网络流量整形与带宽控制技术·18·入桶中的水速有多大,从底部小孔流出的水速是恒定的.
如果桶中无水,则速率为0;如果桶中水满,则流入桶中的水将从桶边溢出而流失掉.
漏桶相当于一个分组队列(缓冲区),当队列满时,分组被丢弃,队列按规定的速率向网络发送分组.
如果分组长度固定,则以分组为单位,每隔一定时间发送一个分组,否则应规定队列每次发送的最大字节数.
2)令牌桶算法漏桶算法的缺点是:无论数据量多大,总是以恒定的速率发送数据,且当漏桶满时,数据丢失.
而大多数应用程序希望有一种更好的算法,在突发数据到来时,能较快地给予响应,同时最好不要丢失数据,令牌桶就具有这样的特点.
如图1.
14所示,令牌桶装的是令牌而不是分组,每隔t时间产生一个令牌,放入令牌桶,令牌桶满后,新产生的令牌将丢弃.
分组在桶外缓冲区中排队,桶中有多少令牌就可以发送相应于令牌数的分组,当桶空时,停止发送数据,新来的数据就要等待生成新令牌或被丢弃.
由于突发性的输入流往往会导致拥塞发生,所以获得令牌的分组将被快速地输出,使突发性的输入流得以迅速地疏导.
图1.
14令牌桶算法示意图一个令牌表示可发送一个分组,也可表示发送一定数量的字节.
若一个令牌表示允许发送一个分组,则每隔t时间,令牌计数器的值加1(受桶容量限制).
每发送一个分组,计数器就减1,当计数器的值等于0时,则停止发送分组.
若一个令牌表示允许发送K字节,则令牌桶相当于一个字节计数器,每隔t时间,令牌计数器的值加K.
每发送一个分组,计数器的值减去分组长度(字节),当计数器的值小于下一个分组长度时,则停止发送.
令牌桶算法的优点是:当主机空闲时,可积累令牌,积累的令牌数量由令牌桶容量来确定,因此,令牌桶有利于发送突发性数据,突发数据量由令牌数量决定.
当令牌桶满时,丢弃的是令牌,而不是分组.
假设突发数据到达时,令牌桶是满的.
设突发长度为Ss,其容量为CB,令牌产生速率为rB/s,数据的峰值速率为MB/s,则MSCrS=+,即突发长度/()SCMr=,表明在开始时,可按峰值速率M连续发送Ss,然后以速率r继续发送,直到结束.
第2章Linux网络过滤与连接分析2.
1Linux系统简介Linux操作系统是一个自由的、免费的、源码开放的操作系统,也是开源软件中最著名的例子.
Linux具有开放性、多用户、多任务、丰富的网络功能等特点,同时也具备可靠的系统安全性、良好的可移植性,具有标准兼容性,良好的用户界面(命令界面、图形界面等),以及出色的速度性能.
如图2.
1所示,Linux是一个和UNIX相似、以内核为基础的、完全内存保护、多任务、多进程的操作系统.
Linux系统分为三个层次.
最下面的是硬件层,Linux支持广泛的计算机硬件,包括X86、Alpha、SPARC、MIPS、PPC、ARM、NEC、Motorola等现有的大部分芯片.
图2.
1Linux体系结构中间层是Linux内核,内核是Linux系统的心脏,是运行程序和管理外围硬件设备(如磁盘和打印机等)的核心程序.
网络流量整形与带宽控制技术·20·处于最上层的是用户空间的各类应用程序,包括系统的用户界面Shell,它提供了用户和内核进行交互操作的一种接口.
它接收用户输入的命令并把它送入内核去执行,是一个命令解释器.
但它不仅是命令解释器,而且还是高级编程语言(Shell编程).
标准的Linux操作系统都会有一套应用程序,如XWindow、OpenOffice等.
2.
2Linux内核结构2.
2.
1Linux内核组成部分Linux内核主要由五个子系统组成:进程调度、内存管理、虚拟文件系统、网络接口、进程间通信.
Linux内核结构如图2.
2所示.
图2.
2Linux内核结构1)进程调度(ProcessScheduling,PSched)进程调度控制进程对CPU的访问.
当需要选择下一个进程运行时,由调度程序选择最值得运行的进程.
可运行进程实际上是仅等待CPU资源的进程,如果某个进程在等待其他资源,则该进程是不可运行的进程.
Linux使用了比较简单的基于优先级的进程调度算法来选择新的进程.
2)内存管理(MemoryManagement,MM)内存管理允许多个进程安全地共享主内存区域.
Linux的内存管理支持虚拟内存,第2章Linux网络过滤与连接分析·21·即在计算机中运行的程序,其代码、数据、堆栈的总量可以超过实际内存的大小,操作系统只是把当前使用的程序块保留在内存中,其余的程序块则保留在磁盘中.
必要时,操作系统负责在磁盘和内存间交换程序块.
内存管理从逻辑上分为硬件无关部分和硬件相关部分.
硬件无关部分提供了进程的映射和逻辑内存的对换,硬件相关部分为内存管理硬件提供了虚拟接口.
3)虚拟文件系统(VirtualFileSystem,VFS)虚拟文件系统隐藏了各种硬件的具体细节,为所有的设备提供了统一的接口,它提供了多达数十种不同的文件系统.
虚拟文件系统可以分为逻辑文件系统和设备驱动程序.
逻辑文件系统指Linux所支持的文件系统,如ext2、FAT等,设备驱动程序指为每一种硬件控制器所编写的设备驱动程序模块.
文件系统是文件存放在磁盘等存储设备上的组织方法,Linux支持多种文件系统,如ext3、ext2、NFS、SMB、ISO9660等.
4)网络接口(Network,NET)网络接口提供了对各种网络标准的存取和各种网络硬件的支持.
网络接口可分为网络协议和网络驱动程序.
网络协议部分负责实现每一种可能的网络传输协议.
网络设备驱动程序负责与硬件设备通信,每一种可能的硬件设备都有相应的设备驱动程序.
5)进程间通信(Inter-ProcessCommunication,IPC)进程间通信支持进程间各种通信机制.
所有其他的子系统都依赖处于中心位置的进程调度,因为每个子系统都需要挂起或恢复进程.
一般情况下,当一个进程等待硬件操作完成时,它被挂起;当操作真正完成时,进程被恢复执行.
例如,当一个进程通过网络发送一条消息时,网络接口需要挂起发送进程,直到硬件成功地完成消息的发送;当消息被成功地发送出去以后,网络接口给进程返回一个代码,表示操作的成功或失败.
其他子系统以相似的理由依赖于进程调度.
Linux各个子系统之间的依赖关系如图2.
3所示.
图2.
3Linux内核各部分的依赖关系进程调度与内存管理之间的关系:这两个子系统互相依赖.
在多道程序环境下,程序要运行就必须为之创建进程,而创建进程的第一件事情就是将程序和数据装入内存.
进程间通信与内存管理之间的关系:进程间通信子系统要依赖内存管理,并支持