（管理科学与工程专业论文）基于市场驱动的网络资源最优分配问题的研究.pdf

l i j 东师范人学硕l ：学馘论文 基于市场驱动的网络资源最优分配问题的研究 摘要 随着近几年计算机网络突飞猛进的发展，i n t e r n e t 已经逐步由单一的数据 传送转向数据，语音，图像等多媒体信息的综合传输网络演化，随着这些应用的 增加，现有的网络正呈现出资源相对稀缺，服务多样化，资源分布化，应用商业 化四大特点。计算机网络的发展在给我们生活带来翻天覆地的变化的同时，也带 来很多我们必须面对的问题，最重要的是以带宽为代表的网络资源匮乏问题，网 络资源的分配和控制对于用户对网络服务的满意程度的提高和网络整体性能的 优化具有重要意义。单纯依靠技术手段来适应网络的发展是不现实的，目前用经 济学原理来研究网络资源分配成为研究的热点i 、口j 题，其中包括使用定价的理论、 博弈理论、均衡理论来控制网络资源分配问题。 本文在市场驱动的条件下，采用微观经济学相关原理研究了网路资源分配问 题，但与前面的研究又有很多不同点，现把本论文研究的主要内容和创新点总结 如下： ( 1 ) 覆盖网络的体系结构中，提出了一种网络资源分配的最优方在案，在该 方案中，我们采用经济代理，他们之间通过协商解决服务管理和资源管理问题， 同时也解决了定价和支付问题。将网络资源的优化模型分解为两层，通过对每一 层进行优化，从而使得整体得到优化，大大减少了计算的复杂性。并通过试验与 轮询算法作比较，证明了基于价格的策略的具有更好的性能。 ( 2 ) 针对不同的用户对服务有不同的需求，对同一个服务的满意度也不相 同，为此我们提出了一种基于服务等级的网络资源分配策略，将服务按照用户对 时延的敏感程度不同划分为不同的等级，在优化模型中采用拉格朗同方法，使得 i s p 收益最大，同时解决了最佳资源分配方案。跟以前研究不同，以前在资源分 配方案上只是在建模上研究的比较多，而涉及到具体分配方案的研究很少，本文 就在简单模型上实现了资源的最佳分配方案。同时通过仿真实验验证了该方案能 够保证各个服务等级的时延限制，与传统的资源分配相比，该方案能够使得i s p 获得更高的收益。 ( 3 ) 在基于服务等级的网络资源分配的基础上，设计了一种具有q o s 保证的 系统结构框架，在资源分配理论模型上采用严格基于等级的排队模型。在该系统 i i i i l i 尔l j f l j 池人学坝r 位论文 中更能体现出用户的支付意愿，化用户的被动性为主动性，同时该系统从市场机 制上体现了资源的分配原则，用户选择的优先级越高，支付的费用也就越高，得 到的服务质量也越高。 关键词：网络定价网络资源分配效用模型多级服务 分类号：t p 3 9 3 i v 山尔帅范人学坝卜芋使论文 t h er e s e a r c ho ni n t e m e tr e s o u r c eo p t i m a la l l o c a t i o nb a s e do n m a r k e t d r i v e n a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fi n t 锄e ti nr e c e n ty e a r s ，i n t e m e th a sd e v e l o p e d i n t oai n t e 粤a t i v et r a n s m i s s i o nn e t w o r kw i t hd a t a ，v o i c ea n di m a g ef r o ms i n g l ed a t a t r a n s m i s s i o n w i mt h ei n c r e m e n to fm o s e印p l i c a t i o n s ，t h ei n t e n l e t锄e 画n gt h e f o l l o w i n gc h a r a c t 舐s t i c s ：r e s o u r c es c a r c e ，s e v i c ed i v e r s e ，r e s o u r c ed i s t r i b u t e da n d a p p l i c a t i o nc o m m e r c i a l t h ed e v e l o p m e n to fi n t e m e tb r o u 曲to u r1 i f e 伊e a tc h a n g e s ，a t m es a m et i m ei ta l s eb r o u 曲tm a n yp r o b l e m sw em u s tf a c e t h em o s ti m p o r t a n t p r o b l e mi s t h es c a r c er e s o u r c e sr e p r e s e n t e db yt h eb a n d w i d t h t h ec o n t r o la n d a l l o c a t i o no fi n t e m e tr e s o u r c ea r eo f 蓼e a ts i g n i f i c a n c ef o ft h ee l e v a t i o no fu s e s s a t i s f a c t i o no ni n t e m e ts e r 证c e sa n dt h ep e r f o r n l a n c eo p t i m i z a t i o no ft h ew h o l e i n t e m e t i ti sn o tr e a l i s t i ct oa d a p tt h ed e v e l o p m e n to ft h ei n t e l n e tm e r e l yd e p e n d i n g o nt h et e c l l l l i cm e a n s t h e s ed a y s ，a d o p t i n gm i c r o e c n o m i cm e a n st os t u d yt h er e s o u r c e a l l o c a t i o n o b l 锄h a sb e c o m et h eh o ts p o t si s s u e s ，i nw h i c h i ti n c l u d e st h e 研c i n g t h e o t h eg 锄ep l a y i n gt h e o 巧a n dt h ee q u i l i b r i u mt h e o 阱 km yp a p e r ，b a s e do nt h em a r k e t d r i v e nc o n d i t i o n s ，w es t u d yt h ei n t e m e t r e s o u r c ea l l o c a t i o np r o b l e mt h r o u 曲t h em i c r o e c o n o m i ct h e o r i e s b u ti ti sd i f r e r e n t 矗o mt h ep r e v i o u ss t u d y ；n o wis u m m 撕z et h ec o n t e n ta n di n n o v a t i o no ft h i sp a p e ra s f 0 1 1 0 w i n g ： ( 1 ) lp u tf o n a r da no p t i m a lr e s 叫r c ea l l o c a t i o ns c h e h l eb a s e do nt h es e i c e o v e r l a yn e 锕o r ka r c h i t e c t u r e i nt h i ss c h 锄e ，ie n l p l o ye c o n o m i ca g e n t s ，t h r o u 曲t h e n e g o t i a t i o nb e t w e e n 也e mt h em a n a g e m e n to fs e r v i c ea n dr e s o u r c ea r er e s o l v e d o n t h eo t h e rs i d et h ep 订c i n ga n dc h a 哂n gp r o b l e n la r er e s o l v e d w ed e c o m p o s em e o p t i m i z a t i o nm o d e li n t o 觚o1 e v e lp r o b l 锄1 1 1 r o u 曲o p t i m i z a t i o ni ne a c hl e v e l ，t h e w h o l e o p t i m i z a t i o n a r er e s o l v e d t h i sm e t h o dc a i lr e d u c et h e c o m p l e x i t y 伊e a t l y t 1 1 r o u 曲t l l ec o m p a r i s o nb e 研e e i lt h e 皿c e b a s e ds c h e m ea i l dr o u n d r o b i n a l g o r i t h m ，t h ee x p e r i m e n tc e n i f ym e 埘c e - b a s e ds c h c i i l eh a v eb e t t e rp 曲姗a n c e v 山东师范人学坝l 学位论文 ( 2 ) a g a i n s td if i e r e n tu s e r sh a v ed i f 瓷r e n tn e e d sa n de v e nf o rt h es 锄es e r v i c e ， d i 仃打e n tu s c rh a sd i 虢r e n ts a t i s f a c t i o n ，f o rm i sr e a s o nw ep u tf o r 、v a r dar e s o u r c e a l l o c a t i o ns c h e m eb a s e do nq u a l i t yo fs e r v i c e i nw h i d l ，t h es e r v i c ea r ec l a s s i 6 e di n t 锄so fd i f f e r e n ts e n s i t i v i t yt od e l a yt i m ef o re a c hu s e r i i lm eo p t i m i z a t i o nm o d e l ，w e a d o p tt h el a 黟a n g ea l g o 一蚰1 f lt om a x i m i z em er e v e n u eo fi s p ，a tm es 锄et i m ew e f i n dt h eb e s tr e s o u r c ea 1 1 0 c a t i o ns c h e m e d i 虢r e n t 舶mt h ep r e v i o u ss t l l d y ；w ef i n d t h es p e c m cs c h e m ei ni n t e m e tr e s o u r c ea l l o c a t i o n t h em o s ts t u d yo n l ys p e n dm u c h t i m eo nh o wt ob u i l dt h em o d e l i nt h ee n d ，t 1 1 r o u 曲s i m u l a t i o niv a l i d a t em i sp l a nc a n c n s u r et h ed e l a yr e s t r i c t i o no fe v e d ，s e r v i c e1 e v e la n da tt h es a m et i m ec o m p a r e dt o t h ec o n v e n t i o n a lr e s o u r c ea l l o c a t i o ns c h e m e ，t h i sp l a nc a nm a k et h ei s pg e tm o r e r e v e n u e ( 3 ) b a s e do nt h eq u a l i t yo fs e i c e ，id e v i s eas y s t 锄a r c h i t e c t u r e 厅锄e w o r k e n s u r e db yq o s o nt h et h e o r e t i c a lm o d e lia d o p tm eq u e u i n gm o d e lb a s e do ns t r i c t 州o r i t y t l l i ss y s t 锄c a nb e t t e re x p r e s st h eu s e r s w i l l i n 萨e s st op a ya n dh a v em o r e i n i t i a t i v e a tm es 锄et i m em es y s t e mr e n e c tt h em a r k e t d r i v e nm o u 曲t ，t h eh i 曲e r p r i o r i t yc h o o s e db yu s e r ，t h em o r em o n e yp a y e dt oi s pa 1 1 dt h eb 甜e rq u a l i t yi s e n s u r e d k e yw o r d s ：i n t e m e tp r i c i n g ；r e s o u r c ea n o c a t i o n ；u t i l i t y 如n c t i o n ；q u a l i t yo fs e r v i c e ； c l a s s i f i c a t i o n ：t p 3 9 3 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名：平户匀2 易 导师签字： 学位论文版权使用授权书 叩冬 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数掘库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) i i 学位论文作者签名：邗鸟) 磊 签字同期：2 0 c y 7 年6 月多日 导师签字： 答字嗍瑚。夕 佼 r 蜩肜价妒广o菇年 山东师池久学蟛ii ：学位沦义 1 1 引言 第一章绪论 1 1 1 in t e r n e t 所面临的问题 随着近几十年i n t e m e t 计算机网络突飞猛进的发展，i n t e m e t 无论从规模上， 技术上，还是应用的种类上都有了很大的发展，联网主机量每年翻一番，力维网 站点每年翻一番。i n t e m e t 也逐步从单一的尽力型服务转向基于多服务的区分服 务，如目前i e t f 提出的基于区分服务的机制，能够在分组网络中以简单有效的 方式提供服务质量和等级服务。在应用上，i n t e m e t 已经逐步由单一的数据传送 转向数据，语音，图像等多媒体信息的综合传输网络演化，随着这些应用的增加， 现有的网络正呈现出资源相对稀缺，服务多样化，资源分布化，应用商业化四大 特点【l 捌。计算机网络的发展在给我们生活带来翻天覆地的变化的同时，也带来 很多我们必须面对的问题，现将分析如下： 首先i t e m e t 将要面临的最大问题是资源的稀缺性，网络资源主要是指带宽， 缓冲区。由于近几年网络用户呈几何级数增长，远远大于网络资源的增长速度， 这就造成了全球范围内网络资源的紧张。另一方面i n t e m e t 多媒体的应用也出现 多样化，如：组播，v o d ，i p 电话，视频会议等等，为了获取更好的性能，一些 实时应用往往采用u d p 协议而不采用t c p 协议传输数据，据统计，当前网络流 量主要协议类型为t c p 协议，占整个流量比例高达8 0 ，其次的u d p 为1 8 ， 其它的协议类型不足2 【3 1 。由于u d p 协议没有采用捐j 塞控制算法，经常会压倒 t c p 流，占用更多的网络的资源，造成网络拥塞，同时许多分布式多媒体应用具 有数据压缩、大容量、突发性等特点，而且用户往往希望自己获得越多的资源越 好，这就更容易造成网络的捌塞和q o s ( q u a l i t yo f s e i c e ) 恶化。网络资源对用户 来说永远是稀缺的，用户对网络资源的需求是永无止境的，如果仅仅依靠网络技 术来扩充现有的资源是不现实的，因此如何把有限的网络资源在用户之间进行有 效地分配，是当今i n t e m e t 面临的第一大难题。 再次，网络资源分配的不均衡问题，由于传统的网络采用单一的尽力而为的 服务，这种策略公平的对待每一个用户，不能够很好的提供区分服务，不能反映 用户对资源的真实需求。而随着i n t e m e t 的迅猛发展，多媒体的应用也出现了多 山鸯：卿池人? f 畎；j 学似论文 样化，有的应用对传输速率和服务质量有着更高的要求，如现在流行的p p l i v e ， 在线视频观看等等。这些应用为了得到更好的服务也宁愿付出更大的代价。虽然 在技术上已经实现了集成服务( i n t e 酉a t e ds e r v i c e s ) 和区分服务( d i 债e n t i a t c d s e r v i c e s ) 提供了一定的q o s 保证，但是这两种模式并没有考虑到用户的实际需 求，不能从经济意义上做到资源的最优配置。如何才能体现用户的真实需求，实 现资源的真实价值，使有限的资源在用户之问均衡合理的分配也是目前i n t e m e t 必须要面临的问题。 上面提到的一些问题是i n t e m e t 在商业化进程中无法规避的问题，对i n t e m e t 的发展形成了挑战，实际上这些问题我们也可以把他们归结为如何有效的分配网 络资源问题，也就是实现网络资源的最优分配问题。 1 2 目前网络资源分配的策略及其缺陷 1 2 1 传统的网络资源分配的主要策略 ( 1 ) 以路由器和主机为中心的分配方式 网络机制可以分为两大类，一种是将问题定位在网络内部，另一种是将问 题定位在网络边上。虽然网络中的路由器和网络边上的主机均参与资源分配， 但真j 下的问题是哪一个承担主要责任。在以路由器为中心的网络资源分配中， 每个路由器决定什么时候转发分组，哪些分组被丢弃，同时通知网上j 下在产尘 通信量的主机允许它发送的分组的数目。在以主机为中心的网络资源分配中， 端主机观测网络状态，并由此相应的调整他们的行为，这两种设计并不是互相 排斥的n 1 。 ( 2 ) 基于窗口式和基于速率式 流控制和资源分配都需要一种方式来向发送端传达允许其发送的数据量传 达这种信息通常有两种方法：窗口方式和速率方式。基于窗口的传输协议，如 t c p ，接收方向发送方通知一个窗口，这个窗口反映接收方的缓冲区大小以及对 发送方传输数据量的限制，即它支持流控制。窗口通知，可以用于网络中以预定 缓冲区空间，即它支持资源分配。用速率控制发送行为也是可以的，速率是指接 收方或网络每秒能够接收的比特数，在支持不同服务质量的基于预定的系统中， 2 i l l 东i j 巾抱j ：。i 欢l ：学 谚论爻 流的基于速率的特性只是一阶逻辑选择，发送方必须预定每秒的比特数，同时路 径上的每个路由器也需要在为它保留空间的情况下，决定是否支持这一速率。 1 2 2 改进的工程控制方法 由于基于窗口的t c p 传输协议并不能提供服务质量保证，只能通过调节端口 的发送速率来尽量的避免网络拥塞，因此具有一定服务质量保证的集成服务 i n t s e r v ( i n t e g r a t e ds e r v i c e s ) 和区分服务d i f f s e r v ( d i f f e r e n t i a t e d s e r v i c e s ) 应运而生。 i n t s e r v 模型的基本思想是“所有的业务流相关状态信息是在端系统上”。 它所使用的资源预留协议r s v p 是一种信令协议。工作时，发送端给接收端发送 一个p a t h 信息，以指定通信的特性。沿途的每个中l 日j 路由器把p a t h 信息转发给 由路由协议决定的下一个节点。当收到一个p a t h 信息时，接收端做出的反应是 、 用一个r e s v 信息为该业务流请求资源，包括带宽、时延等。沿途的每个中间路 由器可以拒绝或接受r e s v 信息请求。如果请求不符合要求( 合同) ，路由器将发 送一个差错信息给接收端，并且中断信令的处理过程。如果请求被接受，就按照 事先的约定，为该流分配链路带宽和缓冲区空间，并且把相关的业务流状态信息 装入路由器中。网络在传送过程中为每一个流( f l o w ，由两端的i p 地址、端口 号、协议号决定) 维护状态。同时，基于这个状态执行报文的分类、流量监管、 排队调度等。 d i f f s e r v 体系模型的核心思想是：在网络边界将数据流按q o s 要求进行简 单分类，不同的类别在内部节点的每次转发中实现不同的转发特性。d i f f s e r v 体系使得i s p 能够提供给每个用户不同等级和质量的服务。用户( 或网络边界节 点) 通过设置每个数据包的d s 字段( i p v 4 首标中的服务类型( t o s ) 字段或i p v 6 首标中的通信类( t r a f f i cc 1 a s s ) 字段) 的值要求特定的服务等级。其中，被 设置的d s 字段被称为区分服务码点( d s c p ) 。在每个支持d i f f s e r v 的网络节点 中，这个d s 值将数据报映射到一类转发行为p h b ( p e r h o pb e h a v i o r ) 中去，从 而在转发中区别对待。用户和i s p 之间有一个协定，此协定规定了该用户在每个 服务等级上所能发送的最大数据率。超过此最大速率的数据包或被丢弃，或无法 享受到它所要求的服务。d i f f s e r v 网络最大的特征是其可扩容性。此体系将许 3 山东卿范人学顺1 j 学位论文 多复杂的控制移到了网络边界，使内部节点能对叠加之后的数据流进行处理，而 不必对每个数据流分别处理，从而大大减小了网络内部应该记录的状态，简化了 网络内部节点的操作。 集成服务i n t s e r v 和区分服务d i f f s e r v 使网络具有了在不用业务流之间分配 稀缺的网络资源的能力，为不同于均分的其它网络资源分配策略在i n t e r n e t 提 供了技术保证畸1 。 统的网络资源分配机制已经不能满足当前i n t e r n e t 多样化，商业化的需要。 路由器在网路中的主要职责是负责选路和分组的转发，并不主动参与网络资源的 分配，也不对单个业务流的流量进行控制饰t 引。基于窗口的t c p 传输控制协议， 只是在用户端进行端到端的流量控制，其原理是通过减少源发送速率末控制拥 塞，为了在捌塞的情况下提供更好的服务质量，必须通过减少部分用户的发送量 来保持网络的稳定性，但它并没有减少用户的需求，更不能主动的满足用户的需 求，因此传统的资源分配机制只能说保证网络的正常运行，减少拥塞情况的产生， 而对资源在不同业务之间合理分配并没有起到多大作用。 现有的工程控制法虽然让网络参与了主动分配资源，使得网络能在不同业务 流之间分配稀有的网络资源的能力，但是它的粒度是基于流的，在实现的方法上 比较复杂，不能实现资源的最优分配。 传统的机制如先来先服务，按优先级服务，按业务类型分配从根本上说都是 有缺陷的： ( 1 ) 先来先服务没有解决同时到达的服务有冲突时该如何分配的问题，更 重要的是他会鼓励用户在没有通信业务的时候也提出服务请求，当有有通信业务 的时候就没有发送的机会。 ( 2 ) 按优先级分配没有解决优先级本身应该如何在用户中分配的问题。 ( 3 ) 按业务类型分配在技术上实现起来比较有困难：i n t e r n e t 的分层体系 结构使得应用层信息在网络层完全被屏蔽掉，网络无法知道用户的应用类型，也 不能指望用户真实的报告这一信息。更重要的是按业务类型分配不一定是合理 的，比如很难讲一个用于消遣的v o d 就应该抢占商业应用中的e m a i l 的网络资 源。 4 l 东帅弛久：坝l ：学位论文 1 2 3 网络资源分配中的计费机制 随着分布式多媒体应用的急剧增加，越来越多的应用要求网络提供更好的网 络服务质量( q o s ) 嘲，对网络资源的需求越来越大，而网络资源的稀缺性必然会 引起网络拥塞和q o s 恶化。传统的网络资源分配策略越来越不适应当今网络发展 的需要，因此有些人提出用经济学的观点来控制网络资源的分配，即用价格杠杆 来控制网络拥塞和进行网络资源分配，实践证明价格手段是一种网络资源分配的 有效手段。 ( 1 ) 计费机制 从经济学的观点看可以把用户看成购买商品的顾客，把网络资源看做商品， 根据供需关系进行价格调节，用价格杠杆来调节用户的需求和网络资源的供给， 最终达到合理使用资源，优化资源分配的目的。当用户较多可使用网络资源较少 使得网络资源搁塞时，网络资源价格上扬，从而抑制用户的需求，从而减少网络 拥塞的程度。当用户较少可使用网络资源的较多，网络资源价格下调，用户需求 增加，网络资源得到充分使用，当供需达到平衡时，网络资源处于优化状态。价 格机制是控制网络拥塞的有效手段，在合理的计费机制下用户行为得到很好的鼓 励，从而避免公物悲剧阳1 。 ( 2 ) 目前国际上网络资源分配的主要价格手段 目前国际上利用价格手段来进行网络资源分配的研究主要有静态定价策略， 动态定价及基于能力的定价策略。 静态定价主要有平坦式定价，巴黎地铁定价p m p ( p a r i s m e t r op r i c i n g ) 。 其中平坦式定价是最早使用且至今仍有很多i s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 沿用的服务定价策略，其服务价格由用户一次性支付的费用( 包括入网时的一次 性成本和用户设备成本) 和固定的连接成本组成。优点是定价方法简单，管理方 便。目前i n t e r n e t 大多采用类似的平坦式定价。国内外广泛使用的按小时、月 或年方式定价，本质上也是平坦式定价，这种定价方式存在以下缺点n 们： 1 对所有用户平等，从而无法用价格杠杆调节用户的资源需求，这不利于资源的 有效利用，从而容易导致网络拥塞。 2 当发生拥塞时，无法根据价格杠杆对用户进行控制和重新分配网络资源，以 减轻拥塞。 5 山力蛳! 范人学f 晚i 学位论爻 3 定价未考虑到用户对不同服务质量的需求，收费不合理。 动念定价策略是指价格会随着网络拥塞状况动态的变化，它要求逐报文，逐流的 测试，连续实时的对资源的需求变化做出反应，典型定价策略有s m a r t 市场。钉 和拍卖机制u 3 j 引。它们的设计是为了更好的控制网络拥塞，只有网络发生拥塞时， 才有价格的设定，此外传输一批报文的在很短的时间问隔内都能发生变化，因此 能够反映出网络的拥塞状况。收取费用的多少是通过拍卖的方式实现的，每一个 报文的包头都有一个投标位，当网络发生拥塞时，用户通过投标与报文相结合的 方式来显示报文的价值，该投标是用户传送此报文愿付的价格。在出现拥塞的路 由器中，只能接受一定数量的报文，网络将所有投标收集后排序，决定出门限制， 传送所有大于此门限值的报文，此门限值由网络容量决定。 该方法的优点在于能动态的反映出网络的变化对价格的影响，资源优化性 能高。缺点是要求系统维护大量的信息，计算复杂度大，收敛速度慢，实现困难。 基于能力的定价策略也可以称为基于优先级的定价策略，它并不是逐报文， 逐流的进行资源分配，而是为不同应用类别进行资源分配，用户的服务费用与用 户的优先级有关，当出现拥塞的时候，网络根据优先缴的设置对报文进行相应的 处理，如：优先服务，延时服务或丢弃等。 该算法的优点是算法开销小，能较好的反映资源变化对价格的影响，具有较 好的资源优化性能。 当今i n t e r n e t 应用的迅猛发展，使得网络出现服务多样化的需求，i n t e r n e t 正在向包括基于t c p i p 的数据业务和多媒体与实时业务在内的综合业务方向发 展，越来越多的用户对服务质量有着更高的要求，这罩的服务质量主要是指时延， 带宽，包丢失率的保证，同时，用户希望能实现不同业务之间服务质量有差别的 区分服务，实现用户或者应用的真实价值。显然传统的资源分配机制已经不能满 足当前的需求，这就对网络资源分配的研究提出了新的挑战，也给我提出了新的 研究课题，如何将有限的网络资源在用户之间合理有效的分配，使得网络的总供 给与用户对资源的需求达到一个平衡状态，如何应对不同的业务之间，不同的用 户之间对网络资源的需求存在很大的差异，更有效的实现区分服务。如何应对由 于业务的多元化导致的用户的多元化和网络商业话带来的不同用户之问，用户与 网络服务提供商( i s p ) 之间在网络资源分配问题上必然存在的利益冲突问题， 6 出尔i j 巾弛人学坎l j 学位沦爻 如果完全依靠用户之问的合作来实现分配是不现实的，所以分配策略的制定成为 个关键的问题。 新的网络发展背景为网络资源优化分配问题赋予了新的内涵，资源利用率不 再是网络资源分配追求的唯一目标，用户的满意度，系统的效益等要素在优化资 源分配中必须加以考虑，网络业务的多元化和用户群体的多元化需要i s p 更有效 的公平的分配网络资源，我们应该探索新的网络资源分配方法，使网络系统能够 在兼顾服务质量的前提下，最大化用户满意度，达到资源最优配置，使得物尽其 用。 1 3 在网络资源分配中引入市场机制及其意义 通过上面的分析我们可以看出，随着i n t e r n e t 的迅猛发展，现有的网络面 临着资源相对短缺和用户对服务的q o s 要求越来越高等问题，如果仅仅依靠技术 、 手段来满足用户的需求是不现实的，因为现在用户规模的增长速度远远超过了网 络的增长速度，因此我们必须采取一种有效的机制来充分发挥资源的使用率，最 大程度的满足用户的服务质量q o s 。 近年来，国外研究者尝试把市场机制引入到网络资源分配管理中，它们将信 息服务看成传统领域中的商品，利用经济学相关原理来研究网络资源的分配问 题。从经济学角度看i n t e r n e t 和传统的电信网有很大的不同。i n t e r n e t 是由遍 布全球的i s p 商业网络，政府网络共同构成的，不属于任何一个权利机构，因此 不能保证技术的一致性，相容性。不能保证服务的稳定性和可用性。传统电信网 络罩，对每次呼叫所分配的资源是固定的，使用价格则是通过呼叫数目来确定的； 而i n t e r n e t 服务的价格根据实际存在竞争的情况，而不是潜在可能的竞争来进 行调节的。相对传统的电信网络，i n t e r n e t 服务更新要快的多，需求不可预见， 网络可用资源的度量也很难实现。但是i n t e r n e t 和传统电信网一样仍然存在着 网络派生效用，用户通过大规模的网络互连和别的用户通信，随着网络规模的增 大，用户通过竞争的收益也会相应增多，用户还可以利用网络产生增值服务，例 如购买一种服务转用于另一种目的，或者从中衍生出另外几种新的服务，这些都 是i n t e r n e t 有别于经济领域中其它商品的特点。 市场机制的引入对网络资源分配的研究赋予了新的内涵，打开了新的思路， 7 【l 东 l i f i 池 、学 i ；3i j 学 讧论文 在市场机制中运用一些经济学原理如：一般均衡理论、n a s h 均衡、边际效用、 用户偏好等n 5 1 ，为网络资源的分配提供了依据，现把引入市场机制的依据总结如 下： ( 1 ) 传统的网络资源分配策略强调网络资源的共享和协同工作，没有把资 源的价格因素考虑进去，而在实际应用中很多资源并不是无偿被使用的，要吸引 资源的拥有者加入网络，就必须保证他们的利益。 ( 2 ) 网络是一个异构的、动态的分布式环境，对资源的使用和资源的供应 都在不断的变化之中。通过引入市场机制，特别是基于价格的市场机制，由价格 的浮动末反映资源的供需情况的动态变化，通过供需平衡柬实现资源最优化分 配。 ( 3 ) 网络资源分配的环境涉及到消费者和生产者的个体行为，这正好与微 观经济学模型匹配。 如今利用微观经济学的理论来研究网络资源的分配成为研究的热点问题，他 给网络资源分配的研究带来新的思路，使网络运营的理念正在逐步改变，以往通 信网络的建立和运营中，主要迎合用户对通信和信息获取的需要，而不考虑用户 对所获取资源的满意程度，运营商更多的是追求技术上的完善，追求各种技术指 标如：丢包率，时延，分配带宽或者缓存的大小等等。而不考虑用户的实际需求， 随着经济的进步和产业价值链的建立，人们越来越意识到这个问题，通信网络的 基本理念正在由技术驱动向运营驱动转变。另一方面在考虑用户的实际需求时往 往要和一些服务质量( q o s ) 指标联系起来，而这些指标又不能完全用技术指标 参数来表示，不同用户的不同业务对网络服务质量的要求差别往往比较大，很难 用工程指标来反映，这些指标之间的关系也比较复杂，对网络服务质量的影响很 难用简单的模型描述。来源于经济和决策论中的效用模型为网络资源的分配提供 了一种很好的数学可计算的建模方法，通过这个模型我们可以把网络资源的分配 问题用数学的形式描述出来，这对于我们寻求更有效的网络资源分配方式，获取 更好的经济效益具有重要意义。它适用了当今网络发展的需要，为网络资源分配 问题提出全新的思路。 山东! f l i 范：学帧：学位论支 1 4 本文的研究目标和内容 本文主要的研究目标是在市场机制的驱动下使得网络资源分配问题获得最 优方案，同时针对不同的用户有着不同的服务质量需求，设计一种具有区分服务 的网络资源分配策略，并强调该方案的可行性。 本文的主要研究内容包括在覆盖网络体系结构中，基于经济代理，研究资源 最优分配方案。针对不同用户具有不同的服务质量需求，对同一个服务用户的满 意度也不全相同，提出一种基于服务等级的网络资源分配策略。其次在基于服务 等级的网络资源分配的基础上，设计了一种具有q o s 保证的资源分配体系结构。 1 5 本文的结构安排 本文共分为六个章节。 第一章：绪论，介绍了本文选题的历史背景及面临的严峻挑战，给出了本文 的研究目的，阐述了引入市场机制的必要性。 第二章：网络资源分配的经济模型及微观经济学理论，包括n a s h 均衡理论， 效用函数等等。 第三章：在覆盖网络体系结构中给出了一种基于代理的网络资源分配方案。 第四章：给出一种基于服务等级的网络资源分配方案。 第五章：设计一种具有q o s 保证的系统结构框架。 第六章：在总结全文的基础上，给出本课题需要研究和深入的问题。 9 i j ! 彖师范，：学f i ! ：! i j 学位论文 第二章网络资源分配的经济模型 2 。1 引言 用市场机制的方法来研究网络资源的分配问题，就要考虑如何经济学原理建 模的问题，在第一章我们提到网络资源分配的问题在很多方面都是与经济学原理 相通的，要用经济学原理来研究网络资源分配问题，就要对网络中出现的问题合 理的抽象，建立适当的经济模型，网络资源分配经济模型一般把顾客看作购买商 品的顾客，把网络资源看作商品，通过价格机制调节用户的需求，控制网络资源 分配，以达到合理分配和使用网络资源的目的。在本文中主要研究的是带宽资源 的分配问题，网络资源的分配的市场框架模型如图2 1 所示。 张字 嬲户应用： 、， d 、 咆挽会议 e 喇i j l ，h c m o f t 只 澍销1 ：絮勰 l 圆 嫩琨缝济擘 伏绘蕊 争槐 路虫镪 a r m 交换机 以久纠交换 帆 幽2 一l 网络中市场模型框架 图中购买网络资源的顾客主要有用户应用，v o d ，电视会议，e m a i l 等。供 应商有主机，路由器，a t m 交换机，以太网交换机等等。顾客通过价格询问，资 源需求，价格协商等经济手段向网络市场购买一定的网络资源，而资源提供商则 根据供需的状况确定资源的价格，双方根据微观经济学原理相互作用以达到优化 网络资源分配的目的。通常在用户和资源提供商处都设有代理实现上述过程，用 户端的代理叫用户代理，资源端的代理称为资源代理。 本章将首先介绍相关经济学原理，目前研究网络资源分配问题用到的主要经 济学原理有一般均衡理论，n a s h 均衡，用户偏好等等。根据经济学研究理论， 存在这样一种价格均衡状态使得此时系统的效用最大化，资源配置也是最优状 态。根据这样的理论，我们研究资源分配方案的目标就是寻求一种合理的经济机 制，使得这种机制下存在价格均衡状态，并且在这种机制的运作中，能在悠闲地 时间趋向这个均衡状态。同时我们用效用函数表示用户对所获得资源的偏好程 度，效用模型在网络资源的分配中有着重要意义，在本章中将作简单介绍。接着 1 0 山东师范人学颐 ：学位论文 我们将分析比较两种典型的网络资源分配的经济模型。 2 2 相关经济学原理 2 2 1n a s h 均衡理论 设g 表示一个博弈，有n 个博弈方，每个博弈方的全部可选策略的集合称为“策 略空间”，用墨，s 。表示，s “墨， 表示博弈方i 的第j 个策略，其中j 可取有 限个值( 有限策略博弈) ，也可去无限个值( 无限策略博弈) 。博弈方i 的得益用“； 表示，“。是各博弈方策略的多元函数。n 个博弈方的博弈g 可以用 g = s 1 s 。：”1 埘。) 表示。 定义2 1 在博弈g = 墨s 。：“泓。 中，如果各个博弈方的各一个策略组成某 个策略组合( s ? ，5 ：) 中，任意博弈方i 的策略s ；都是对其余博弈方策略的组合 ( s j 二，s 二j ：) 的最佳对策，也即对v 岛墨，都有 “f ( j ? ，j 二l ，s ? ，s 二i ，j ：) “f ( s ? ，s 二，j ，s 二l ，j ：) 成立，则称( s ：，s ：) 是g 的一个纳什均衡( n a s he q u i l i b r i u m ) 定义2 1 是博弈理论中对n a s h 均衡的一般定义，我们把它放在网络资源分配的 环境罩则应该定义如下： 定义2 2 ：在博弈理论中，如果用户速率分配向量为石= ( 石? ，x ) 中任一用户 占用的资源为，此速率是给定其余用户所占用资源石：，= ( 工：，。，t ”。) 的 情况下，用户i 的最佳策略：其效用( 0 ，石：，) u ，( 一，石：，) v x ，彳i 1 ，n ) ， 那么速率分配向量z 就是博弈解。 博弈理论中定义n a s h 交易解为：满足p a r e t o 最优性( 经济学中称为p a r e t o 有效性) 、线性、对称性、和互不相干性的n a s h 均衡点。 n a s h 均衡在网络资源分配博弈中有两个意义： ( 1 ) 当所有用户在优化各自的收益函数时，从理论上讲，n a s h 均衡是最有 山东师兆人学坝l j 学位论文 可能出现的结果，因此n a s h 均衡是对资源分配博弈进行理论分析的基础； ( 2 ) 给定其他用户的行为( 策略) 不发生变化时，某一用户的行为( 策略) 不会偏离构成n a s h 的行为( 策略) 。这意味着n a s h 均衡的结果具有一定的稳定 性； 需要说明的是，n a s h 均衡并不是在所有的博弈中都存在，这罩不再展开论 述n a s h 均衡的存在性定理。 n a s h 均衡理论在网络资源的分配中应用比较广泛，虽然这种理论并没有给 出具体解决网络资源如何分配的方法，但是它告诉我们在网络资源分配中存在一 种状念，在这种状念下任何用户对资源分配策略的改变，都不会使网络资源分配 的系统效益达到最优。 2 2 2 一般均衡与价格均衡模型 目前利用经济学理论来研究网络资源的分配问题是一大热点问题，尤其是解 决网格中资源的分配问题，在本小节基于一般均衡理论提出了基于市场机制的一 种网络资源分配的经济模型，其主要思想是将整个网络系统看成是一个价格随供 求关系浮动的竞争市场，市场的参与者根据市场的价格和自身偏好自主决策购买 网络资源以满足个人的服务质量，市场机制通过价格浮动反映资源资源供需状况 的变化，通过供需平衡来实现资源的优化分配。下面将模型的一些符号定义如下： 对于m 个资源的集合“，吒，) ，为每个代理( 船e n t ) 定义一个向量 x = _ ，屯，) ，其中，再表示分配给这个代理的资源的数量。代理对资源分配 的优先选择由效用函数u ( x ) 表示，它表示用户对所分配资源的满意程度，这是 资源向量空间到实际数值的映射，如果有两个资源向量x 和