（计算机应用技术专业论文）基于拍卖机制的无线网络带宽分配方法的研究.pdf

南京l i i | j i 也人学硕： ：研究生学位论文 摘要 摘要 下一代互联网的精髓在于网络融合，即建设一个能够提供话音、数据、多媒体等多种业 务的，集通信、信息、电子商务、娱乐于一体，满足自由通信的融合网络。这种趋势使得现 有的i n t e m e t 资源分配方案不能适应当前网络应用。由于用户特征呈多元化，资源利用率不再 是资源分配唯一的优化对象，必须在分配过程中考虑用户满意度、系统效益等要素。如何合 理分配有限的资源为不同服务质量需求的应用提供服务，提高资源使用效率，是亟待解决的 问题。 本文总结了目前网络资源分配的特点，对目前网络资源的分配现状进行了研究，分析了 目前保障网络服务质量的相关技术原理，论述了采用拍卖作为利用市场机制实现网络资源有 效配置首选方案的原因，引入了基于微观经济学的拍卖方式，利用效用( u t i l i t y ) 函数来评估 用户的满意度，在微观经济学方法的累进第二价格拍卖( p r o g r e s s i v es e c o n dp r i c e ，p s p ) 模 型基础上，在多速率多时隙系统( m u l t i r a t em u l t i s l o t t e ds y s t e m ) 中，给出了一种使用可变 的保留价格( r e s e r v ep r i c e ) 的拍卖算法来进行无线网络资源分配的方案，定义效用函数的最 小效用和最小数据需求量的概念，实现了最大用户群体中的满意用户的数量的首要目标，在 不能增加满意用户之后最大化系统的吞吐量。最后通过模拟仿真，把无线网络资源分配方案 与最大化系统吞吐量的t h r o u g h p u tm a x 方案和最公平的f a i r n e s s 方案进行比较，实现了较好 的用户满意比例，同时系统的吞吐量也和t h r o u g h p u tm a x 方案的效果接近，达到了预计目标。 关键词：无线网络资源分配微观经济学累进第二价格拍卖 南京邮电火学烦j ：研究生学位论义 a b s t r a c t a b s t r a c t t h es o u lo fn e x tg e n e r a t i o nn e t w o r ki st h ec o n v e r g e n c eo fn e t w o r k s ，t h a ti st os a yt ob u i l d ac o n v e r g e dp a c k e tn e t w o r kw h i c hc a l lp r o v i d ev o i c e ，d a t a ，m u l t i m e d i as e r v i c e sa n di n c l u d e c o m m u n i c a t i o n ，i n f o r m a t i o n ，e l e c t r o n i cb u s i n e s sa n de n t e r t a i n m e n t t h i st r e n dc a u s e st h a tt h e c u r r e n tr e s o u r c e sa l l o c a t i o ns c h e m eo fi n t e r n e td o e sn o ta d a p tw e l la n de n c o u n t e rm a n y p r o b l e m s s i n c et h eu s e r s c h a r a c t e r sa l ed i f f e r e n t ，t h ee f f i c i e n c yo fr e s o u r c e su s a g ei sn o tt h e o n l yo b j e c to fo p t i m i z a t i o n ，t h eu s e r s d e g r e eo fs a t i s f a c t i o na n dt h es y s t e m sb e n e f i ts h o u l da l s o b et a k e ni n t oa c c o u n t w i t ht h ed e v e l o p m e n to fi n t e r a c ta p p l i c a t i o n ，t h es c a r c i t yo fn e t w o r k r e s o u r c e si si n c r e a s i n g l ys e r i o u s i ti si m p o r t a n tt os t u d yh o wt oa l l o c a t et h el i m i t e dr e s o u r c e r a t i o n a l l yf o rd i f f e r e n ta p p l i c a t i o na n di m p r o v et h eu t i l i z a t i o no ft h er e s o u r c e i nt h i st h e s i s ，c o n c l u d e dt h ec h a r a c t e ro fn e t w o r kr e s o u r c ea l l o c a t i o n ，s t u d i e dt h es i t u a t i o n o fe x i s t e dn e t w o r kr e s o u r c ea l l o c a t i o n ，a n a l y z e dt h et h e o r yo fe n s u r e dq u a l i t yo fs e r v i c e ，s h o w e d t h er e a s o nt h a tc h o s ea u c t i o na sf i r s tm e c h a n i s mt oa l l o c a t en e t w o r kr e s o u r c e se f f i c i e n t l y , i m p o r t e dt h ea u c t i o nm e c h a n i s mb a s e do nm i c r o e c o n o m i c s ，u s e du t i l i t yf u n c t i o na sat o o lt o e v a l u a t et h eu s e r s s a t i s f a c t i o n ，b a s e do np r o g r e s s i n gs e c o n dp r i c em o d e li nm i c r o e c o n o m i c s ， p r o p o s e das c h e m eb a s e do na u c t i o nu s i n gv a r i e t yr e s e r v ep r i c et oa l l o c a t i o nn e t w o r kr e s o u r c ei n m u l t i r a t em u l t i s l o t t e ds y s t e m ，i n t r o d u c e dt h ec o n c e p to fm i n i m u mu t i l i t ya n dm i n i m u md a t a r e q u i r e m e n t ，i m p l e m e n t e dt h eo b j e c to fm a x i m i z i n gt h en u m b e ro fs a t i s f i e d u s e r sa n d m a x i m i z i n gt h et h r o u g h p u t a tl a s t ，c o m p a r e ds c h e m ep r o p o s e dw i t ht h r o u g h p u tm a x s c h e m e a n df a i r n e s ss c h e m eu s i n gn s 2s o f t w a r e ，g o tt h eh i g hp e r c e n t a g eo fs a t i s f i e du s e r sa n dt h e s y s t e mt h r o u h t p u tw a sc l o s et ot h r o u g h p u tm a xs c h e m e k e ) ，w o r d s ：w i r e l e s sn e t w o r k s ，r e s o u r c ea l l o c a t i o n ，m i c r o e c o n o m i c s ，p s p 南京邮电大学硕j 二研究生学位论文 参考文献 缩略词 缩略词英文全称 中文名称 b a b e h a v i o ra g g r e g a t e行为聚集 d c c d y n a m i cc a p a c i t yc o n t r a c t i n g 动态能力协约 l s pl a b e ls w i t c hp a t h标签交换路径 l s r l a b e ls w i t c h i n gr o u t e r标签交换路由器 p f p p r o p o r t i o n a lf a i r n e s sp r i c i n g 比例公平计费 p m pp a r i s - m e t r op r i c i n g巴黎地铁计费 p s p p r o g r e s s i v es e c o n dp r i c e 累进第二价格拍卖 s l as e r v i c el e v e la g r e e m e n t服务等级协议 t c at r a f f i cc o n d i t i o n i n ga g r e e m e n t流量调节协定 t o s t y p eo fs e r v i c e 服务类型 南京邮电大学学位论文原创i i 生声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：立箍聋捆日期：趁望军生。2 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：玺i 毛丰量丑 导师签名： 南京邮i 乜大学颂j ：研究生学位论文第一章绪论 1 1 引言 第一章绪论 近年来，i n t e r n e t 正逐步向商业性、服务公众化、多主干的全球网转变，并已成为全球 信息基础设施的原型i l j 。为适应这一变化， n t e m e t 管理、运营和维护逐渐转由多家i n t e m e t 服务提供商负责，i s p 以不同的标准向各类用户提供连接访问、视频点播( r o d ) 、w e b 查询、 新闻组( u s e n e t ) 、e m a i l 等多种网络服务，向用户收取服务费用，这既加快了i n t e m e t 由 学术科研究性网络向商业网络的转变，也为运用价格杠杆来促进i n t e r a c t 网络资源的合理 使用，为用户提供良好的服务质量奠定了基础。随着i n t e m e t 应用的迅猛发展，现有网络 呈现出资源相对稀缺、服务多样化、资源分布化和应用商业化等4 大特点f 2 】 3 】f 4 】，针对这 些特点，无论是用户还是网络运营商，都对i p 网络的研究和进一步发展提出了更高的要求。 首先，用户需要更好的网络服务质量，要求提供服务质量的保障。 网络的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 1 5 1 1 6 是指用户的业务在网络传输过程中所表 现出的各种性能，可以用一组性能参数对其进行描述。具体包括：到达速率或带宽( r a t eo r b a n d w i d t h ) 、吞吐量( t h r o u g h p u t ) 、丢失率( 1 0 s s ) 、时延( d e l a y ) 、时延抖动( d e l a y j i t t e r ) 、 连接的可用性( a v a i l a b i l i t yo f t h ec o n n e c t i o n ) 、安全性( s e c u r i t y ) 、可靠性( r e l i a b i l i t y ) ， 它们共同构成q o s 参数集，常用的q o s 参数是前五项。这些服务性能的聚集效应，决定 了用户的某一业务对网络所提供的通信服务的满意程度。不同的业务( 应用) 对q o s 参数 集的不同分量有不同的要求。交互式的实时应用程序( 如语音通信等) 对端到端时延和抖 动很敏感。如果时延大，则将削弱通信的交互性。非交互式的实时应用程序( 如单向广播 等) 对端到端时延不敏感，但对抖动敏感。非实时应用程序往往对时延不敏感。当前的以 i n t e m e t 为代表的i p 网络只提供尽力而为的服务，并不能保障用户业务的这些q o s 要求。 i p 网的q o s 保障功能是为了商业应用的要求而“后天”加入的，需要通过对i p 网络控制 机制进行扩展而实现。 用户业务所获得的q o s 保障取决于其实际占用的网络资源。网络上最重要的资源是路 由器的缓存容量和输出链路带宽。几个输入数据流共享同一个输出链路，根据香农信息理 论，任何个带宽为h ( h z ) ，信噪比为s n 的信道，其最大数据传数速率为 c = h l o g ，( 1 + s ) 。路由器的转发速率r 必须小于或等于信道容量c 。如果r c ，则在理 南京邮电火学硕 研究生学位论文第一章绪论 论上无差错传输就是不可能的。如果总的分组到达速率超过r ，多余的分组将在这个端口 建立排队等待。如果没有足够的缓存空间存储，分组就会被丢弃。而分组的排队时延和丢 弃是影响q o s 的主要因素。因此，网络资源分配是q o s 保障机制的核心问题之一【7 】1 1 0 1 。 其次，网络运营商要求提供更加有效的资源分配方式。对网络运营商而言，资源分配 机制的研究有着更加实际的经济价值1 6 9 】： 1 与网络用户的几何级数增长相比较，硬件设备的扩容和技术更新较为缓慢，带宽、 缓冲等网络资源相对匮乏，不能满足日益增长的用户需求，必须设计高效、合理的资源分 配策略以充分利用资源f 9 1 。 2 不同应用的服务质量要求和资源需求不同，现有的单一尽力服务型网络模式不能很 好地提供区分服务，这就要求网络采取措施，提供不同质量级别的多种服务，把稀缺的网 络资源分配给对其价值评价最高的用户，并收取相应费用，使i s p 获得尽可能大的用户市 场及利润【1 0 1 。 3 i n t e m e t 己发展为遍布全球的服务网络，具有商业化特点，迫切要求引入合理的价格 机制和体系，体现资源的价值，为网络市场运作提供基础。同时，计费管理也是i n t r a n e t ， e x t r a n e t 的重要组成部分，它为企业内部各部门或相关企业之间信息共享和传输的财务结 算提供依据。但是计费必须与资源分配相结合，才有实际意义【i l 】。 因此，从各个角度讲，资源分配都应当是网络研究的核心课题。 1 2 网络资源分配存在的问题 当前i n t e m e t 无法满足用户和网络运营商的要求，这主要是由于当前的i n t e m e t 资源分 配机制已不适应网络资源相对稀缺、服务多样化、资源分布化和应用商业化的发展趋势。 但是，i n t e m e t 的巨大成功带来了新的问题。越来越多的用户和i s p 要求i n t e r n e t 提供 更多的多媒体业务，与传统业务相比，其对服务质量的要求更高，如通信质量有保证的服 务，在不同的业务间服务质量有差异的区分服务，更强有力的q o s 保障等1 1 4 】。因而，i p 网络上承载的通信业务除了在数量上持续快速地增长外，其构成也在沿着多样化的方向演 进，已成为包括基于t c p i p 的数据业务和多媒体与实时业务在内的综合业务量，对网络 资源分配的研究面临新的前提： 1 用户对网络资源的总需求大大超过网络的供给，企图在网络规划阶段即通过超量供 给( o v e rp r o v i s i o n i n g ) 来同时为所有业务提供足够的带宽是不现实的。网络资源已成为一 种典型的稀缺资源。 南京邮电大学坝- _ k i o f 究生学位论文第一章绪论 2 不同的业务之间，不同的用户之间对网络资源的需求存在很大的差异，在它们之间 均分资源既不公平也无效率，因而分配策略的制定成为个关键的问题。 3 业务的多元化也促进了用户的多元化，i n t e r a c t 已从一个为科研服务的网络转变为商 业性质的网络。不同的用户之间，用户与网络( i s p ) 之间在网络资源分配的问题上必然存 在利益冲突，完全依靠用户问的合作来实现分配策略是不现实的【1 5 】。 1 3 网络资源分配的研究现状和发展 目前在网络资源分配的实践主要都是利用单一计费( f l a t r a t ep r i c i n g ) 方式为用户单 位时间内提供服务并收取固定的费用，而与用户的使用量无关。用户根据和网络服务提供 商所签服务合同的时间长短来支付费用。在合同有效期间，用户可以使用多少网络资源并 没有明确的规定。既然没有拒绝就是允许，用户可以随心所欲的使用网络资源，而不必担 心为此多向网络服务提供商支付费用。这种事先定价的网络计费方法，就像一个餐馆，向 用餐者收取一定的费用，然后就任其食用一样，对资源造成了一定程度的浪费。这种计费 方法一定程度上使网络成为公共物品，既然是“公共资源”，也就难逃“公共资源的悲剧”。 公共资源悲剧也叫哈定悲剧，是由哈定提出的。一群牧民面对向他们开放的草地，如果多 养头羊增加的利益大于其购买和放养成本，每个牧民都会多养羊。当羊的数量超过牧场 的合理载畜量后，再增加羊的数量只会使整个牧区羊的单位收益因为平均草量的下降而下 降。由于草地是公共产品，没有人关心其可持续发展，也就没有人愿意减少牲畜数量，草 地最终将因为过度放牧发生退化，最终变为荒漠，致使所有牧民的羊都饿死。目前采用的 单一计费是网络运营商根据般用户使用网络资源的行为来决定的。在网络中实施很容 易，不需要对i s p 的网络进行大的改造。同时，使用该方法，用户能够预知自己使用网络 所支付的费用，从而控制自己的开支。单一计费的便捷使其在现有的网络计费方法中大行 其道。虽然如此，单一计费方法有自身固有的严重缺点。研究认为单一计费方法造成了网 络使用的无效率，在单一计费方法中，用户支付的费用事先决定，在此期间i s p 为提供服 务所付的成本只能事后确定。这样就存在i s p 提供不够本服务的可能性。以至于网络运营 商无法获利，也就没有动力来提供新的服务。单一计费方法造成资源浪费，其社会成本很 高。因为所有人都收取一样的费用，使用网络资源比较少的用户就需要补贴使用网络资源 多的用户。 基于经济机制的网络资源分配方式，为网络传输的商业运作提供基础。基于微观经济 学方法的网络资源分配研究适应现代网络的发展，为古老的资源分配问题提出全新的研究 南京邮电大学硕二i j 研究生学位论文 第一章绪论 思路，具有重大意义，目前越来越多的人开始关注这一领域的研究。在这方面的研究中， 国外学者已取得了一些成果，而国内从事这方面的研究较少。 1 4 论文主要工作 因特网在过去的十几年中经历了爆炸式的增长，同时伴随多媒体技术的飞速发展，因 特网上多媒体应用层出不穷多媒体信息的数量与日俱增。目前因特网的服务模式仍为单一 的“尽最大努力服务”，与此相对应的它主要支持传统的数据应用，例如网页浏览、文件 传输、电子邮件、远程登录等。然而伴随多媒体技术的飞速发展，因特网上新多媒体应用 层出不穷，多媒体信息的数量与日俱增，因特网将逐步由单一的数据传送网向数据、语音、 图像等多媒体信息的综合传输网演化。因特网络资源相对稀缺，网络资源的增长速度远远 落后于网络用户的几何级数增长速度，直接导致了全球范围的网络资源紧张。因特网已从 一个为大学研究者服务的科研网络转变为商业性质的网络。在商业化环境下不同的用户之 间，用户与网络服务提供商之间在网络资源分配的问题上必然存在利益冲突，需要高效合 理的网络资源分配方式。目前在网络资源分配的实践主要都是利用单一计费方式为用户单 位时间内提供服务并收取固定的费用，而与用户的使用量无关。 本文总结了目前网络资源分配的特点，对目前网络资源的分配现状进行了研究，分析 了目前保障网络服务质量的相关技术原理，论述了采用拍卖作为利用市场机制实现网络资 源有效配置首选方案的原因，引入了基于微观经济学的拍卖方式，利用效用函数来评估用 户的满意度，在微观经济学方法的累进第二价格拍卖( p s p ) 模型基础上，在多速率多时 隙系统( m u l t i r a t em u l t i s l o t t e ds y s t e m ) 中，给出了一种使用可变的保留价格( r e s e r v ep r i c e ) 的拍卖算法来进行无线网络资源分配的方案，定义效用函数的最小效用和最小数据需求量 的概念，实现了最大用户群体中的满意用户的数量的首要目标。鉴于引入基于经济机制作 为网络资源分配方式国内外研究较晚，此领域研究仍存在很多困难，本文对未来可能的研 究领域和方法进行了展望。 1 5 论文安排 本文前四章对无线网络资源分配进行了理论分析。第一章主要介绍目前网络资源分配 机制存在的问题，网络资源分配的现状和发展，以及论文的主要工作。第二章研究了网络 资源分配相关技术，着重介绍了基于微观经济学的方法。第三章分析了微观经济学拍卖方 式的研究现状和发展，介绍了拍卖的类型，着重介绍了基于博弈论的p s p 模型，并给出了 4 南京邮i 乜大学硕i j 研究生学位论文 第一币绪论 基于此拍卖模型的理由。第四章介绍了效用函数的定义和几种形式，阐述了在网络分配中 引入效用概念的意义，在此基础上给出了本文采用的效用函数。 第五章提出了基于拍卖的无线网络资源分配方案，对几个关键点分别进行了阐述，详 细介绍了算法步骤，给出了理论上的性能分析。第六章介绍了n s 2 仿真软件，给出了模拟 网络的场景，并对仿真结果进行分析，证明了本文提出的资源分配方案的可行性。第七章 对文章进行总结和展望。 南京邮 乜大学硕士研究生学位论文第二章网络资源分配相关技术的研究 第二章网络资源分配相关技术的研究 2 1 网络资源分配原理 当前i n t e m e t 的资源分配是通过用户端的流量控制和网络上路由器的控制机制综合作 用而实现的。路由器控制业务流所占用的网络资源有两个手段：调度策略( 带宽分配) 和 缓冲区管理( 缓存分配) 策略。缓冲区管理负责将分组存入缓冲区以等待传输并在出现拥 塞时选择丢弃哪些分组，调度策略则负责从缓冲区中选择相应的分组传输【l l 】。显然，两者 之间是相互关联的。给某个特定的业务流分配更多的带宽有助于降低该业务流所需要的缓 冲区容量，相反地，改变业务流的缓冲区容量可以对该业务流所占有的带宽产生影响。 i n t e m e t 路由器一般采用先来先服务( f i r s tc o m ef i r s ts e r v i c e ，f c f s ) 的调度算法和当缓冲 区满时丢弃所有后到分组的丢尾( d r o p t a i l ，d t ) 策略。当网络上发生拥塞时，路由器不 加区分地丢弃后到分组，源端的传输控制协议t c p 通过发现重传计数器( r t o ) 超时或收 到3 个相同a c k 确认帧，判定网络发生拥塞( t c p 这一假定是基于由传输引起的数据包 损坏和丢失的概率很小) ，缩小发送窗口，从而减少入网流量，缓解拥塞。由此可见，传 统i n t e m e t 的资源分配主要在用户端进行，即利用t c p 在用户端进行端到端、分布式的流 量控制。路由器的功能主要局限在寻找路由上，并不主动参与网络资源分配，也不对单个 业务流的流量进行控制【1 2 l 。 i n t e m e t 在过去十几年中经历的爆炸式增长和获得的巨大成功，说明原有的网络资源分 配机制对传统的l p 业务是有效的，有其独特的优点。传统的i p 网承载的业务，如t e l n e t 、 f t p 、e - m a i l 、w w w 等应用对q o s 的要求有两个共同特点： 1 这些应用都为同步非时间紧要应用或异步传输应用，它们对时延的忍受能力很强， 只要求简单的连通性( 传输服务可以维持) ，即对q o s 的要求很低。 2 这些应用对q o s 的要求没有多大差异。用户端t c p 主导的资源分配机制对所有用 户使用相同的流量控制机制( 据统计，目前i n t e r n e t 上仍有9 5 的数据流使用的是t c p 协 议f 9 】) ，通过合作实现基于最大最小公平( m a x i m u mm i n i m u mf a i r n e s s ) 的网络资源平均 分配策略。显然，由于应用对q o s 的要求没有多大差异，因而平均分配策略是合理的。在 这种资源分配策略下，当前的i n t e m e t 只提供一种简单的服务：尽力而为地传输数据报。 这种最简化的服务使得路由器是状态无关的( s t a t e l e s s ) ，除了高度聚集的路由信息外，网 络上的路由器无需保持任何关于业务流的状态信息。这使得今天的i n t e m e t 具有很好的可 6 雨京邮l u 人学硕士研究生学位论文第二章网络资源分配相关技术的研冗 扩展性( s c a l a b i l i t y ) 和鲁棒性( r o b u s t n e s s ) 。因为路由器的复杂度与经过该路由器的业务 流数目以及整个网络的节点数目无关，网络是可扩展的。网络是鲁棒的，因为当一个路由 器出现故障，或从故障中恢复时，其它路由器只需更新很少的状态信息【1 3 】。 网络资源分配主要有两种手段：通过工程控制方法来主动地分配网络资源，通过计费 的手段给用户提供货币激励，使之合理地利用网络资源。 1 网络资源分配的工程控制方法 网络本身要参与到拥塞控制中去，主动地进行资源分配己成为一个不可回避的研究方 向。因而，出现了以i n t s e r v 与d i f s e r v 为代表的端到端q o s 保障机制，使网络具有了在不 同的业务流之间分配稀缺资源的能力，为不同于均分的其他分配策略在i n t e m e t 上实现提 供了技术上的保证。但这些技术本身并不能提供什么是最优的分配策略。传统的机制如先 来先服务( 优点是简单) ，按优先级分配( 能够实现区分服务) ，按业务类型分配等从根本 上讲都是有缺陷的： ( 1 ) 先来先服务没有解决同时到达的服务请求有冲突时该如何分配的问题，更重要的 是它会鼓励用户在没有通信业务的时候也提出服务请求，以免在有通信业务的时候没有发 送的机会； ( 2 ) 按优先级分配没有解决优先级本身应当如何在用户中分配的问题； ( 3 ) 按业务类型分配在技术实现上有困难。i n t e m e t 的分层体系结构使得应用层信息在 网络层完全被屏蔽掉，网络无法知道用户的应用类型，也不能指望用户真实地报告这一信 息。更重要的是按业务类型分配并不一定是合理的，比如，一个用于消遣的v o d 就会抢 占商业应用中的e m a i l 的网络资源。 出现上述问题，是由于现有的i pq o s 理论框架本身存在局限： 第一，没有为网络优化提供依据。i pq o s 技术不能增加网络资源，它只能管理网络资 源。当对网络资源的需求超过供给时，网络发生拥塞，此时保护某些应用的q o s 就意味着 降低另外一些应用的q o s 。现有的i pq o s 理论框架无法确定这样的技术决策是否是合理 的。 第二，i pq o s 技术与计费脱节。已提出的i pq o s 模型虽然有计费模块，但并没有考 虑计费策略对网络资源分配的影响。现有的与用户对网络资源使用无关的单一计费会使得 诸如d i f f s e r v 等i pq o s 模型无法实用【2 4 】。 第三，网络资源的集中化控制与i n t e m e t 本性不符。从控制的角度来看，资源分配方 式有中心化控制和非中心化控制两种。中心化控制是指网络端根据用户需求，采用某种先 验公式确定资源分配准则，其优化依赖于所有用户的信息，网络控制端相当于一个掌握着 7 南京邮l 乜人学颂t ：自j f 究生学位论文第二章劂络资源分配相关技术的研t 全部资源的管理者，它可以根据系统目标寻求最优分配方案。非中心化控制是指资源分配 不完全由网络端控制的一种机制，即不存在集中的管理者，网络只为用户间的行为提供规 范。现有的i pq o s 模型均由网络方集中控制资源分配，而分散控制才是i n t e m e t 发展的方 向。i n t e m e t 由遍布全球的i s p 商业网络、政府网络等共同构成，不属于任何一个权力机构， 因而不可能有统一的资源控制和管理。用户和用户资源的分散性，网络规模的庞大也使得 中心化控制不可想象。 综合以上的原因，目前网络资源分配的工程控制方法离实用还有很大距离。而且所面 临的困难在现有的i pq o s 技术框架内难于解决。网络资源分配研究需要新的思路，需要新 的方法论作指导。 2 网络资源分配的定价和计费机制 目前国内外在实践操作中最流行的网络计费方式是单一计费。在单一计费机制中，用 户为其每单位时间的网络服务支付固定的费用而与其用量无关，通常的包月计费就是这种 机制。当前因特网快速发展的一个原因就是其计费采用这种简单的机制。单一计费主要有 着几个个优点瞄1 【2 6 】： 第一，从技术实现角度看，不需要复杂的测量和计量机制： 第二，用户需要支付的费用和网络的收入简单清楚： 第三，用户可以很随意的接入网络，鼓励了网络的使用。 其缺点主要表现在： 第一，用于用户的支付的费用与用量无关，因此与大用量用户相比对小用量用户不公 平； 第二，因为单一计费的价格在长时间段内是不变的，对用户的行为在短时间段没有激 励作用，从而它不能与拥塞控制或者流量管理结合起来； 第三，单一计费方式没有考虑用户的效用，用户用量没有什么限制，网络资源分配经 济效率低下，会导致“公物悲剧”； 第四，不适用于区分服务网络。 尽管单一计费是目前网络计费的主要方式，大部分学者认为网络计费发展的方向是基 于用量的计费( u s a g e b a s e dp r i c i n g ) 陋】1 2 6 1 2 7 1 2 8 。顾名思义基于用量的计费方式下，用户的 费用与用户使用网络资源情况有关。基于用量的计费有主要有着几个个优点： 第一，提高了公平性： 第二，对用户有激励作用，可以与拥塞控制或者流量管理结合起来； 第三，使得用户有效的使用网络资源，网络资源可以得到优化分配： r 南京邮电大学硕_ t j 研究生学位论文第二章网络资源分配相关技术的1 i 】f 冗 第四，可以支持区分服务。 基于用量的计费的缺点是： 第一，增加了计费的复杂程度； 第二，可能抑制网络的使用，特别是对于教育和科研用户。 如图2 1 所示，基于用量的计费通常包括测量( m e t e r i n g ) 、计量( a c c o u n t i n g ) 、定价 ( p r i c i n g ) 、费用( c h a r g i n g ) 和账单( b i l l i n g ) 等几个部分。 图2 1 基于用量的计贾 其中测量部分主要完成原始数据的采集工作，计量部分根据原始数据完成用户用量的 统计工作，定价部分根据当前的网络状况和计费策略确定当前的价格和费用计算方法，费 用部分根据用户的用量和当前的价格计算用户需要支付的费用，账单部分生成用户费用清 单。 i n t e r n e t 服务定价的研究热点有i 删： ( 1 ) 采用什么样的服务定价模型； ( 2 如何利用价格杠杆，根据用户q o s 需求调度分配资源； ( 3 ) 如何对特殊服务进行服务定价； ( 4 ) 实现计费机制的有效工程途径； 其中，定价模型是基础，基于不同的定价模型可以有不同的资源管理方案。资源调度 与分配则要求服务定价系统能根据网络上的负载和应用情况，在合理分配和调度资源的同 时，针对不同的用户和负载给出相应的价格参数，通过价格调节和控制用户的资源要求。 另外，由于i n t e m e t 上的各类特殊服务越来越多，如组播、v o d 、电视会议、i n t e m e t 电话、 i n t e m e t 传真等，针对特殊服务的定价有利于资源的合理利用。 9 南京邮也人学硕二 j 研究生学位论文第- 二章网络资源分配相关技术的研究 2 2 基于非经济学的方法 从广义上来说，网络服务质量可以包括网络性能、可用性、可靠性和安全性等各种指 标，因为这切都和网络的使用者能够感受到的服务质量相关，服务质量控制是为了提高 网络保证性能的能力。和性能相关的主要q o s 参数有带宽、延迟( d e l a y ) 延迟抖动( d e l a y j i t t e r ) 、分组丢失率( p a c k e tl o s sr a t e ) 掣5 2 1 。根据这些性能参数，可以定义绝对的( 确 定性) 和相对的( 不确定性) 两种性能保证形式。和提供尽力服务的网络相比，支持q o s 的网络的特点就在于可以提供服务质量保证，服务保证的具体形式由网络服务提供商i s p 和客户之问签署的服务等级协议( s e r v i c el e v e la g r e e m e n t ，s l a ) 决定1 5 3 1 。 无论是i n t s e r v 、d i f t s e r v 还是m p l s 机制，其技术的核心的都是要在适当的层次和粒 度上对流量进行必要的管理，其中包括接入控制、流量整形、队列管理，调度和拥塞控制 等诸多方面。 1 i n t s e r v 在服务定义层次上，i n t s e r v 提供端到端的质量保证服务或可控负载服务。在实现层次 上，现有方案需要所有路由器在控制路径上处理每个流的信令消息并维护每个流的路径状 态和预约状态，在数据路径上执行基于流的分类、调度和缓冲管理。具体而言，i n t s e r v 依 靠资源预留协议【划( r e s o u r c er e s e r v a t i o np r o t o c o l ，r s v p ) j 丕节点建立或拆除每个流的资源 预留状态；依靠接入控制( a d m i s s i o nc o n t r o l ，a c ) 决定链路或网络节点是否有足够的资 源满足q o s 请求；依靠传输控制( t r a f f i cc o n t r 0 1 ) 将i p 分组分类成传输流，并根据每个 流的状态对分组实施q o s 路由、传输调度( s c h e d u l i n g ) 等控制。 在i n t s e r v 流中，定义了三种类型的业务：即保证业务( g u a r a n t e e ds e r v i c e ，g s ) 、受控 负载业务( c o n t r o l l e dl o a ds e r v i c e ，c l s ) 、尽最大努力服务的业务。i n t s e r v 是基于流、状 态相关的体系结构。与原来的i p 状态无关的体系结构相比，i n t s e r v 提供的服务具有更高 的灵活性和更好的服务级别保证。然而，要实现具有q o s 保证的i n t s e r v 比较困难，需要 基于流的、复杂的资源预留、接入控制、q o s 路由和调度机制。而在复杂、大规模网络中 链路的状态是不确定的，有效地预留带宽是一件困难的工作。而且，i n t s e r v 具有某种面向 连接的特性，而i p 网络不具有面向连接的特性。更本质的问题是，i n t s e r v 面临着可扩展 问题和鲁棒性问题【5 5 】，这限制了r s v p 和i n t s e r v 在整个i n t e m e t 网络中的应用。 2 d i f t s e r v 在非经济学方法实现的d i f f s e r v 机制中，采用的是边缘节点调节网络流量的方法， d i f f s e r v 是单向的，其标记机制是基于发送方，并不考虑接收者的q o s 要求。d i f f s e r v 目 l o 南京邮电大学硕士硼f 究生学位论文第二章网络资源分配相关技术的移f 冤 标在于以简单有效的方式提供q o s 服务，以满足实际应用对可扩展性的要求，通过简化网 络内部节点的服务机制和网络内部节点的服务对象来实现。核心路由器则仅仅根据每跳行 为( p e rh o pb e h a v i o r ，p h b ) 将i p 分组转发划分为多个模式1 5 6 1 。p h b 是指每个节点转发i p 分组的方法，包括为i p 分组指定排队队列，调度策略和拥塞阂值设定等。通过在上游网络 和下游d s 区域之间建立s l a 或流量调节协定( t r a f f i cc o n d i t i o n i n ga g r e e m e n t ，t c a ) ， 区分服务可以扩展到多个d s 区域。区分服务采用i p v 4 分组头中的服务类型( t y p eo f s e r v i c e ，t o s ) 字段或i p v 6 分组头中的优先级( t r a f f i cc l a s s p r i o r i t y ) 域作为d s 字段。不 同的d s 值定义不同的p h b ，即定义不同的分组转发模式。服务水平协议是服务提供商和 用户通过协商在服务质量、优先权和责任义务等方面达成的协议。当用户与服务提供商签 订s l a 后，将按照所接受的服务向服务提供商付费，同时监督服务提供商所提供的服务质 量。而服务提供商则有义务为用户提供相应的服务并保证其能够获得签约的服务质量。区 分服务业务网络中可以根据区分业务的转发模式进行服务类型划分，通过s l a 将不同的转 发模式映射到相应的服务类型中去。边界节点根据t c a 对入域流或出域流进行调节，以 确保入域流或出域流符合t c a 中所规定的要求，标记数据流的d s c p 值，并将其加入相 应的行为聚集( b e h a v i o ra g g r e g a t e ，b a ) 。具体如下图2 2 所示。 _ 数据包 图2 2 分类器和调节器的逻辑结构和功能 分类器根据数据包头部的某些域对数据包进行分类，d i f f s e r v 定义了两种类型的分类 器：b a 分类器和多域( m u l t i p l ef i e l d ，m f ) 分类器。前者只根据报文中的d s c p 来对报 文进行分类，而后者根据报文头部中多个域内容来进行分类，如源地址、目标地址、协议 标识、源端口号以及目标端口号等，经分类器分类后的报文进入到调节器中进行进一步处 理。数据流计量器根据t c a 中所规定的数据流要求测量被分类器所选定的数据流的时间 属性，并将所测量的每个数据包的统计信息送往其它的调节功能模块。标记器设置报文的 d s 域为一特定的d s c p ，并将标识了的报文添加到一特定的d s 行为局集中，标记器可以 将所有送入的报文标记为同个d s c p 值，也可以配置成根据计量器的统计信息将其标记 为同一p h b 组内的p h b 所对应的d s c p 值。整形器、丢包器为了使数据流符合数据流规 南京i l l f f l 0 入学颂。i ：i i j f 究生学位论文第二章网络资源分配相关技术的研究 范，延迟或丢弃数据流中的部分或全部报文。 现有的调节器技术包括基于令牌桶的调节器、基于时间滑移窗i z l 的调节器等。基于令 牌桶的调节器通过限制数据包的平均速率、峰值速率和突发尺寸来调节发送方的数据发送 速率，达到流量调节的目的。 3 m p l s m p l s 是为了解决目前i p 网络面临的问题而产生的，其基本思想是对协议堆栈进行简 化，实现i p 和链路层的紧密结合【5 7 1 。m p l s 对分组进行分类，使用标签来标志属于同一转 发类型的分组，在网络中使用标签作为决定转发的唯一标志。m p l s 是一种混合技术，它 把路由选择和数据转发分开，在边界实现传统的路由，在核心提供极快速的转发，消除了 在数据传输路径上每个包在每台路由器上都需要进行的路由查询开销。m p l s 将第2 层的 高速交换能力和第3 层的灵活特性结合起来，使i p 网具备高速交换、流量控制、q o s 等功 能。m p l s 有两种途径对q o s 支持： ( 1 ) 使标签本身就具有t o s 的意义； ( 2 ) 用标签条目中的e x p ( e x p a n d ) 域来标示传送分组的t o s 。 m p l s 数据包的服务质量类型由t o s 等参数来决定。标签交换路由器( l a b e ls w i t c h i n g r o u t e r ，l s r ) 根据t o s 来决定输出队列和丢包优先级，如对到达同一目的地的i p 包，可 根据标签中e x p 域的t o s 值来建立不同的转发路径。不同的转发路径对应不同的拥塞控 制机制和丢包优先级，达到其对传输质量的要求。同时通过对特殊路由的管理，还