（通信与信息系统专业论文）网络资源分配问题的研究.pdf

! ! 塑窒望叁兰竺! ：兰些堡兰 堕竺兰堡坌些塑塑! ! ! ! 塑 摘要 i n t e m e t 在近十几年获得了飞速的发展。随着i n t e m e t 用户访问 需求和新业务需求的增长，呈上升趋势的分组丢失率和网络性能的 下降导致了用户的不满，而对一些新业务的支持的力不从心也严重 地阻碍了对服务质量敏感的应用的普及。在这种情况下，研究如何 在众多的相互竞争的用户之间公平合理地分配网络资源是具有极大 应用前景的。 资源分配是个很复杂的问题，本文在全局的资源分配确定的前 提下对某一个流在网络节点处的资源分配问题进行讨论。本文主要 采用分类比较的方法研究资源分配的三个主要环节。其中，接纳控 制是通过在不损坏对已有流的服务保证的条件下决定一个新的服务 请求是否可以满足来限制网络的负载，鉴于本文的前提，只讨论连 接接纳控制，即当网络高层资源分配方案确定了一条端到端路径后， 该路径上的节点对于是否接纳新到流的控制方法；活动队列管理是 通过对网络节点缓冲区队列的管理，尽早检测到拥塞并识别和惩 罚不规矩的流；而调度则定义链路出口的排队服务原则，决定何时 以何种顺序发送队列中的分组。 本文分析比较现有的机制和算法，最后指出了资源分配领域还 有待进一步研究的问题。 关键词：资源分配流接纳控制活动队列管理i j , a z i ! 变窭望叁兰塑! ：望些堡苎； ! = ! 竺塑塑坌丝塑墨塑婴垄 a b s t r a c t w i t ht h ee x p l o s i v eg r o w t ho fi n t e m e t ，t h e r ea r ei n c r e a s i n g l ym o r e u s e rb r o w s ea n dn e ws e r v i c er e q u e s t s b u tt h ei n c r e a s i n gp a c k e tl o s sa n d t h e d e g r a d a t i o n l e a dt om o r ea n dm o l e c o m p l a i n s a n d p r e v e n t t h e a p p l i c a t i o n s w h i c ha r es e n s i t i v et o q u a l i t y o fs e r v i c e ( q o s ) f r o m p r e v a l e n c e i n t h i sc a s e ，t h e s t u d y o fr e s o u r c ea l l o c a t i o n a m o n ga c o l l e c t i o no f c o m p e t i n gu s e r si sm u c hv a l u a b l e r e s o u r c ea l l o c a t i o ni sac o m p l e xi s s u ea n dh a sb e e nt h es u b j e c to f m u c hs t u d ye v e rs i n c et h ef i r s tn e t w o r kw a sd e s i g n i ti ss t i l la na c t i v e a r e ao fr e s e a r c h s u p p o s i n gt 1 1 a tg l o b a lr e s o u r c eh a sb e e na l l o c a t e d w e f o c u so nt h ea p p r o a c h e so fd e t a i ll e s o u r e ca l l o c a t i o nb a s e do n p e rf l o wa t p e rn o d e s i nt h i st h e s i s ，w em a i n l yd i s c u s sa d m i s s i o nc o n t r 0 1 a c t i v e q u e u em a n a g e m e n t a n d s c h e d u l i n gb yc l a s s i f i c a t i o na n dc o m p a r i s o n 1 1 1 e i d e ab e h i n da d m i s s i o nc o n t r o li ss i m p l e w h e ns o m en e wf l o ww a n t st o r e c e i v eap a r t i c u l a rl e v e lo fs e r v i c e 。a d m i s s i o nc o n t r o lt r i e st od e c i d ei f t h ed e s i r e ds e r v i c ec a nb ep r o v i d e dt ot h a ta m o u n to f t r a f f i c ，g i v e nt h e c u r r e n t l ya v a i l a b l er e s o u r c e s ，w i t h o u tc a u s i n ga n yp r e v i o u s l ya d m i t t e d f l o wt or e c e i v ew o r s es e r v i c et h a ni th a dr e q u e s t e d i fi tc a np r o v i d et h e s e r v i c e t h ef l o wi sa d m i t t e d ；o t h e r w i s ei ti sd e n i e d e a c hr o u t e rm u s t i m p l e m e n ts o m eq u e u i n gd i s c i p l i n e ，c a l l e da c t i v eq u e u em a n a g e m e n t ( a q m ) ，t og o v e r n h o wp a c k e t sa r eb u f f e r e dw h i l e w a i t i n g t ob e t r a n s m i t t e d a q m e a r lb et h o u g h to fa sa l l o c a t i n gb o t hb a n d w i d t h ( w h i c h p a c k e t sg e tt r a n s m i t t e d ) a n db u f f e rs p a c e ( w h i c hp a c k e t sg e td i s c a r d e d ) a st o p a c k e ts c h e d u l i n g ，i td e c i d e sw h e na n dh o wt h ep a c k e t st ob e t r a n s m i t t e d w bi n t r o d u c et h ep r e s e n tm e c h a n i s m sa n d a l g o r i t h m sa b o u tt h et h r e e a s p e c t s i nt h ee n d ，w ep r e s e n tt h eo p e ni s s u e si nr e s o u r c ea l l o c a t i o ni n i n t e m e t k e y w o r d s ：r c s o u r c ea l l o c a t i o n f l o wa d m i s s i o nc o n t m l a q m s c h e d u l i a g ! ! 立銮望盔兰堡：! 兰些堡兰 塑垒塑翌坌堡塑墨堕! 堕墨 1 综述 i m e m e t 在近十几年获得了飞速的发展。随着w w w 的广泛普及， i n t e m e t 的用户访问需求和新业务需求产生了巨大的增长。随着它们 的增长，传统网络技术的弱点也表现的越来越明显，呈上升趋势的分 组丢失率和网络性能的下降导致了用户的不满，而对一些新业务的支 持的力不从心也严重地阻碍了对服务质量( q o s ：q u a l i t y o f s e r v i c e ) 敏感的应用的普及。在这种情况下，对如何在众多的相互竞争的用户 之间公平合理地分配网络资源的研究，是具有极大应用前景的。 在展开讨论之前，让我们先来考虑一个重要问题：当多数网络问 题都能通过增加网络带宽来解决时，我们是否还需要再提资源分配这 个问题? 在理论上，在一个极其高速的无阻塞的网络上是无需考虑资 源分配问题的，路由器总是可以不停顿地进行分组转发；但是，在实 际应用中，这种情况几乎不可能出现。首先，对于一个大型的网络， 它的骨干总是按照业务需求而设计，并以一定的业务量复用模型来支 持最终用户，网络骨干将承受前所未有的巨大流量：其次，网络中的 流量有很大一部分是突发的，对于突发流量而言，可能在一小段时间 内发生拥塞：第三，路由协议并不了解网络负荷情况，因此可能在有 些路径上发生拥塞，而在另一些路径上带宽空闲，而且，在l a n ( 局 域网) 和w a n ( 广域网) 的边缘还存在着速率不匹配的问题，就算 是很快的w a n ，来自l a n 的流量也可能造成拥塞：最后，即使有极 大的带宽也无法单独保证低的、可预见的时延，因为有可能发生实时 应用阻塞在大文件传输后面的情况。因此，一个再高速的网络，特别 ! ! 立奎望叁堂堕主望些堡兰 旦塑苎堂堑塑旦塑壁! ! ! ! 翌 是公众服务网络，没有有效的资源分配，网络带宽就很容易因为不合 理地使用而不公平地消耗掉，这就好比一条宽阔的马路会因为不遵守 交通规则的驾驶员造成塞车一样。因此对网络的资源分配是很有必要 的。 1 1 对i n t e r n e t 提出的新需求 现有的i n t e r n e t 的设计思想是牺牲所有的q o s 要求，只进行尽力 转发，以此换取网络实现的简单。而随着i n t e m e t 的发展，出现了越 来越多的实时的多媒体的应用，人们希望网络能对这些应用提供比尽 力转发更好的、具有一定q o s 保证的服务，比如为i p 电话应用提供 一定的时延保证等等。因此，将传统的尽力服务的网络转变为能提供 q o s 保证的网络，才能更好地为对q o s 敏感的应用提供服务，这是 用户的需要。而在一个商业网络中，不同的用户往往希望支付合理的 价格获得合理的服务，没有合理的q o s 保证，也就不可能采用不同 的、公平的服务价格策略。因此，在实际应用中如何保证服务质量是 宽带网络成功的关键因素之一，这是网络运营商的需要。 而保证q o s 所要解决的问题主要是如何控制用户通信的延时、 吞吐和丢失。目前的i n t e m e t 基本上没有很好的延时控制手段，它的 延时取决于通信路径和当时的网络拥挤程度。目前的i n t e m e t 也没有 很好的吞吐率控制，虽然，本地上网的吞吐率基本取决于连接链路， 但是，由于采用的接入设备和路由器基本上是阻塞式的设备，因此， 往往达不到访问链路速率；同时由于没有好的链路分享机制，吞吐率 与网络路径有很大的关系，不同的接入点，采用同样的接入线路，用 北方交通大学硕士毕业论文 网络资源分配问题的研究 户所享受到的吞吐率并不公平( 如图1 - l 所示) 。目前i n t e m e t 也没有 很好的丢包控制，由于没有很好的优先分类，丢弃分组时缺乏针对优 先类别的选择性；由于通常采用f i f o 排队和通用处理芯片，流的相 关性分析代价也较昂贵，丢弃分组时缺乏流的相关性选择。目前 i n t e m e t 采用t c p 的慢启动、快速重传和快速恢复机制实现端到端的 流控。i n t e m e t 上依靠t c p 实现尽力转发，它采用简单的先进先出 ( f i f o ：f i r s ti nf i r s to u t ) 排队与端到端的t c p 拥塞控制实现。而 t c p 的拥塞控制算法主要是靠发送源在检测到由于队列溢出丽造成 丢包之后来降低它的发送速率来实现的。但采用这种方式通常是在发 送源检测到丢包时距路由器实际丢包时刻已经有很长一段时间了；同 时，在这段时间内往往由于发送源仍然以网络不能支持的速度发送报 文而造成大量的资源浪费。 图1 一li n t e m e t 缺乏链路分享机制 可以把对服务质量的要求分为如下三类：( 1 ) 弹性应用，这类应 用对端到端的传输时延没有要求，如f t p 或者电子邮件，w e b 对时 延有一定的要求，但它对服务质量的影响因人而异，暂且归入此类； ( 2 ) 适应性应用，这类应用能够根据网络性能的变化调节服务质量 和发送速率，但是超过一定界后服务质量劣化到无法忍受，如i p 电 话、r e a l p l a y 等；( 3 ) 关键应用，这类应用要求严格的端到端时延保 证，旦违反时延保证则服务质量迅速下降，如高质量电视会议等。 些立奎望苎兰堡主兰些堡墨堕垡兰塑坌垦塑塑! ! ! ! 丝 1 2 解决新需求的方法 针对上述现状，i e t f 主要提出了集成服务( i n t s e r v ：i n t e g r a t e d s e r v i c e ) 和区分服务( d i f f s e r v ：d i f f e r e n t i a t e ds e r v i c e ) 这两种服务质 量模型来解决i n t e m e t 的服务质量问题，它们的模型分别如图l 一2 和 图1 3 所示。 i n t s e r v 和d i f f s e r v 在对业务的定义和实现结构方面都大不相同。 在对业务的定义上，i n t s e r v 基于每个流( 单个的或是汇聚的) 提供端 到端的保证或是受控负载的服务( c o n t r o l l e d 1 0 a ds e r v i c e ) ，而d i f f s e l v 只提供有限的几类服务。在实现结构方面，目前的i n t s e r v 要求每个 路由器处理每个流的信令消息，并在控制平台保持每个流的数据转发 状态和q o s 状态，同时在数据平台执行每个流的分类、调度和缓冲 区管理。这样就严重影响了网络的可扩展性和鲁棒性( r o b u s t n e s s ) ， 因为基于每个流的处理的复杂性是流的数量的函数，而在分布网络环 境下复制每个流的状态并实现动态一致是很困难的。虽然有些建议为 减小网络中流的数量把相同路径的微流汇聚成宏流，但这只是在一定 程度上缓解了问题，并没有从根本上解决问题，网络边缘路由器上宏 流的数量依然很大。另一方面，d i f f s e r v 区别对待边缘路由器和核心 路由器，边缘路出器要基于更细的流量粒度处理分组( 如基于每个 流) ，而核心路由器不用保持细粒度的状态信息，只要基于每个分组 包头的每一跳行为( p h b ：p e rh o pb e h a v i o r ) 处理分组。d i f f s e r v 通过 把复杂推到网络边缘来保证网络核心的简单，因此d i f f s e r v 的数据平 台比i m s e r v 更具可扩展性，但仍需要在控制平台进行接纳控制，同 时d i f f s e r v 所提供的服务就不如i n t s e r v 那样灵活，对网络的利用方 北方交通大学硕上毕业论文 网络资源分配问题的研究 面和对业务的服务质量保证方面也不如i n t s c r v 。 尽管i n t s e r v 和d i f f s e r v 有着这样大的差别，但是无论采用哪一 种q o s 模型，实现过程都需要完成路由查找、接纳控制、流量控制、 活动队列管理、排队调度和报文交换几个阶段。其中，路由查找决定 报文的传输的路径；接纳控制是指根据目前的资源决定是否可以满足 某个通信服务请求：流量控制是指对具体的数据流特征进行整形以符 合预定的特征参数：活动队列管理是为了尽早检测到拥塞；排队调度 决定什么时间以什么样的次序来发送报文：报文交换是指如何把输入 的报文快速交换到指定的输出接口。在每个阶段采用不同的技术会有 不同吞吐特性、时延特性、隔离特性和公平特性等等。而除了流量控 制和报文交换，其它的阶段都是在对网络的资源进行分配。 图卜2 综合业务通信模型 ! ! 塑奎望叁兰堡主兰兰竺堡兰 塑竺兰望坌里塑壁! ! ! ! 垄 1 3 资源分配 图1 3 分类业务的通信模型 资源分配是个很复杂的问题，因为它不止涉及网络协议堆栈中的 某一个层次，如何在众多的相互竞争的用户中公平合理地分配资源是 个跨整个协议栈的问题。从设计第一代网络开始，就有很多与资源分 配相关的研究。到现在，资源分配仍然是一个活跃的学术领域。 先让我们来明确一下何谓资源分配。所谓资源分配，是指网络元 素尽力满足应用对网络资源的要求的过程。网络资源主要包括网络路 径、链路的带宽和路由器或交换机的缓冲区。显然，网络资源是有限 的，而对资源的需求是日益增加的，满足所有的需求通常是不可能的， 这就意味着一些用户或应用得到的资源会比它们想要的少，甚至在资 源缺乏的情况下一些用户或应用被拒绝。 j ! 塑奎望盔兰壁生兰些堡茎上生盟墅堕坌墅旦堂i ! ! 堕 资源分配有两个层面，即全局的资源分配和在全局的资源分配确 定后的资源共享。所谓全局的资源分配，就是在全网的范围内给每个 应用分配一定的资源，这首先就要确定该应用的路径，而路由问题本 身就是很复杂。由于时间和篇幅的限制，本文不讨论与选路有关的问 题，只针对全局的资源分配确定后，网络的节点对于某一个应用的资 源分配问题。 1 3 1 “流”的概念 在讨论资源分配问题时，我们不得不提到“流”，它是资源分配中 一个抽象但很重要的概念。所谓“流”是指一系列包的信源和信宿是 相同的一对主机，而且当这些包通过网络时经过的路由器也是相同 的。流实质上类似通道( c h a n n e l ) ，只不过流对于网络中的路由器而 言是可见的，而通道只是端到端的抽象。 可能会有多个相关的包流过同一个路由器，因而有时有必要记录 一下每个流的某些状态，用来对属于同一流的包作资源分配的决定。 这种状态称为“软状态”，它不同于硬状态，不必通过信令显式地创 建或删除。软状态介于纯无连接网络( 不在路由器上记录任何状态) 和纯面向连接网络( 在路由器上记录硬状态) 之间。虽然就总体而言， 网络的正确运作并不依赖于所记录的状态，但当路由器记录了包所属 的流的软状态后，路由器就能更好地处理这个包。 流既可以隐式地定义，又可以显式地建立。隐式地定义的情况是 指路由器通过检查包头地址发现具有相同的信源信宿对，就认为这 些包属于同一个流；显式地定义的情况是指信源在发信之前先向网络 发流建立的消息，表面看来显式定义流与在面向连接的网络中建立连 7 ! ! 查奎堡查兰堡主兰些堡苎 塑竺兰望坌垦塑丝! ! ! 堕 接没什么不同，但即使是显式建立的流，也不意昧着在端到端进行可 靠的顺序的传输，它仅仅是资源分配的需要。 1 3 2 资源分配方法的分类 有多种方法可以实现资源分配，但每种方法各有不同。我们大致 可以从三个方面来描述资源分配的方法。 以路由器为主和以主机为主 资源分配机制可以分为两类：把问题交给网络内部来解决( 即路 由器或交换机) 或者把问题交给网络边缘来解决( 即主机或是传输层 协议) 。因此问题的关键在于主要由哪个方面来完成资源分配的任务。 在以路由器为主的设计中，每个路由器负责决定何时转发包和丢弃哪 个包，并告知发送包的主机允许其发送的包数量。在以主机为主的设 计中，端主机观察网络的情况( 如成功通过网络的包的数量) 并根据 观察到的结果调整自己的行为。但这两类并非相互排斥的。打个比方 来说，网络把主要的拥塞管理的任务交给路由器，但仍希望端主机能 相应路由器发出的忠告性的消息：而在使用端到端拥塞控制的网络 中，路由器也采用一些策略( 无论多么简单) 来决定当队列溢出时丢 弃哪个包。 基于预留的和基于反馈的 资源分配机制也可以按照是基于预留的或是基于反馈的来分类。 在基于预留的资源分配的网络中，当一个流建立时，端主机会向网络 申请一定的资源，每个路由器将会按要求为该流分配足够的资源( 如 缓冲区和定比例的链路带宽) 来满足主机的请求。如果这种请求在 某些路由器因为资源不足而不能满足，路由器就会拒绝这个流。这类 ! ! 查奎望叁兰堡：! 垩兰竺丝兰 塑塑塑翌坌垦旦堂! 塑! ! 翌 似在打电话时遇上忙音的情况。在基于反馈的系统中，端主机开始发 数据时并不预留任何资源，只是按照收到的反馈来调整发送包的速 率。反馈可以是显式的( 如拥塞路由器向主机发送“请慢点发送”的 消息) 也可以是隐式的( 如端主机按照观察到的网络的行为，比如丢 包率，来调整发送的速率) 。 通常基于预留的系统就意味着用的是以路由器为主的资源分配机 制。因为每个路由器必须理解自己由多少资源被预留，并要确保每个 流只能使用为它所预留的资源。如果某个流以比它所申请的速率快的 速率发送包，那么如果路由器拥塞，该主机发出的包将会被丢弃。另 方面，基于反馈的系统暗指以路由器为主或是以主机为主的资源分 配机制。如果反馈是显式的，那么路由器至少在某种程度上参与了资 源分配；反之，如果反馈是隐式的，那么几乎所有的资源分配的任务 都是由端主机来完成，路由器只是在拥塞时丢弃包。 基于窗口的和基于速率的 对资源分配方法的第三种分类是将其分为基于窗口的和基于速率 的两种。在发送方要有一种方式来表示允许发送多少包，一般用窗口 或是速率来表示。正如我们熟悉的基于窗口的传输协议，如t c p ，接 收方告知发送方一个窗口，对应着接收方有多少缓冲区，这也就限制 发送方可以发送的数据的数量。一个类似的机制窗口通告机制一 一可以用来在网络中预留资源( 主要是缓冲区) ，在x 2 5 中就是这么 用的。也可以用速率来控制发送方的行为，即接收方或网络每秒可接 收多少比特。虽然目前还没有基于速率的传输层协议，但我们可以想 象它是用来支持视频应用的：接收方只能处理1 m b p s 的视频帧，则 发送方必须受此速率的限制。实际上在支持不同服务质量的基于预留 韭查奎望奎兰堡：! 兰兰竺笙塞 璺竺篓翌坌垦旦塑! ! 竺塑 的系统中流的基于速率的特征是一个逻辑的选择发送方做出每 秒多少比特的预留，沿路的每个路由器来决定若可支持该速率是否会 影响其它的流的服务。 上面描述了三种对资源分配方法的分类办法，每种又分为两类， 所以共有八种组合。常用的是其中两种，这两种资源分配机制是和网 络所提供的业务相结合的。一方面，尽力服务通常用的是反馈机制， 因为这种业务不允许用户预留网络资源，于是拥塞控制的任务就落到 端主机上( i n t e m e t 采用的是基于窗口的信息) ，路由器或许也提供一 些帮助。另一方面。基于q o s 的业务意味着预留某些资源，这就要 路由器的参与，例如对包就要按照他们预留的资源的程度来排队。而 且，由于窗口和需要网络多少带宽并没有直接的关系，因此很自然地 要用速率来表示预留。 1 3 3 最佳资源分配的判据 提出一种资源分配机制后，要来评价一下它的性能的优劣。 对于无0 0 s 要求的资源分配，我们用两个指标来分析其性能：有 效性和公平性。评价一种资源分配机制的有效性的出发点是要考察网 络的两个主要的参数：吞吐量和时延。显然我们希望得到尽量大的吞 吐量和尽量小的时延。有人建议用吞吐量和时延的比率作为评价资源 分配机制的有效性的指标，就是要最大化这个比率，因为它是网络负 载的函数，而网络负载是由资源分配机制确定的，比率曲线如图1 - 4 所示，理想的资源分配机制应落在该曲线的尖峰处。在尖峰的左侧， 资源被过分预留了，比较浪费：在尖峰的右侧，较多的包流入网络导 致了时延的增加；在曲线的最右侧。由于网络的负载过重，最终造成 0 ! ! 查奎里查兰堕主兰些燕塞 堕垒壅塑坌墼塑望! ! 里堕 拥塞崩溃的严重后果。做为网络运营者，希望网络性能是稳定的，即 使在重负荷下也要求包能够通过网络，因此在选择资源分配机制时总 希望能尽量落在曲线的尖峰附近。 l 喜 f 萋 厂 l 尊 l l |最佳负载负载 i i |图1 4 负载与吞吐量，时筵的关系曲线 1 评价资源分配机制时，还要考察公平性。公平性的基本原则就是 任何一个流都不能过多的占用网络资源。但在资源分配中，公平是个 相对的概念。一个机制是否公平，取决于所采用的公平理念或公平准 则，在不同的公平准则下，答案是不同的。在不支持o o s 的情况下， 或在不明确指定实施某种特定的公平准则时，我们般假定采用的是 普遍公平准则，也就是说，所有的流在所处的网络环境大致相同的情 况下应该能够被分配到大致相同的资源，目前i n t e m e t 上较为公认的 也正是这个公平理念。实际上还要考虑到路径长短的问题，如图1 5 所示，我们怎么能希望一个四跳的流和三个一跳的流公平地竞争带宽 呢? 些变銮望查兰堡! ：兰些堡苎一坐塑墅曼坌墼塑堡! ! ! 堕 ! ! 查奎望叁兰堡! 兰些堡! 一旦垒童竖坌堡旦垦! ! ! ! 堕 送队列中的分组。 图i - 6 网络资源分配框架 1 4 本文讨论范围 在数据业务迅速增长的今天，用户希望能得到更好的服务质量， 网络运营商希望能在现有网络的基础上为更多的用户提供服务，因此 人们开始关注网络资源分配这个问题。因为，合理的网络资源分配能 使资源得到更有效地利用，并保证用户得到更好的服务质量。这正是 我们研究这一课题的意义之所在。 本文研究i n t e r a c t 中的网络节点的资源分配方案，包括路由问题 的全局资源分配不在本文讨论之列。本文主要讨论节点资源分配问题 中的三个方面的内容，具体安排如下：在第二章主要讨论接纳控制问 题；第三章讨论了活动队列管理：而第四章主要研究的是调度问题； 第五章对本文的工作做了相应的总结，并提出了在资源分配领域还有 待进一步探讨的问题。 ! ! 塑窒望查兰堡：! 兰些笙茎 堕竺塞堡坌里旦璧! ! ! 堕 2 接纳控制 2 1 接纳控制的概念 在未来的多业务的网络中，如何规划网络资源来满足突发业务的 服务质量是很关键的问题。这种资源的规划必须通过接纳控制来实 现。接纳控制是一个很大的题目，也是资源分配中一个很重要的环节。 本文只讨论连接接纳控制，就是对某一个连接实施的接纳控制，即当 网络高层资源分配方案确定了一条端到端路径后，该路径上的节点对 于是否接纳新到业务的控制方法。 在一次通信开始前，用户必须提出它的流量的特征和希望得到的 服务，网络根据网络资源和管理策略来决定接受或是拒绝该用户，而 不影响现有用户得到所需的服务质量。实际上网络是通过某种接纳控 制来做这个决定的，而接纳控制是通过限制某类流的接纳数量来保证 该类流所要求的服务质量。 接纳控制必须考虑网络的性能，既要让网络资源得到充分的利用， 又要确保流得到所需的服务质量。如果不必要地拒绝了本该被接纳的 流，那么网络的利用率就降低了：同样，若允许过多的流接纳，结果 必然是服务质量恶化。考察一种接纳控制的性能，常常考虑以下几个 参数：丢包率、时延以及网络利用率。 一直以来，接纳控制都是i n t e m e t 中的难点，很多人都提出了各 种各样的方法。纵观这些方法，大致可分为基于参数的和基于测量的 两种。 4 北方交通夫学硕士毕业论史 网络资源分配问题的研究 2 2 基于参数的接纳控制 所谓基于参数的接纳控制，就是预先给出流的特征描述，建立相 应的数学模型，通过计算决定是否允许流进入。最简单的基于参数的 接纳控制就是保证需求带宽的总和不超过链路容量，即i - + r “ b ) ) ，接纳控制就变成判断t ) b ) ，其中q 为队长，b 为缓冲区容量。 ! ! 查奎墨盔兰堕：! 望些垦壅 堕垒壅翌坌堡塑壁! ! ! 堕 一、d a n i c k 等人在【1 4 提出在调制m a r k o v 情况下，b k e 一， 而k * 1 ，则e = p 一，所以万= 一l o g 百( p 一1 ) ，占即为等效带宽。 二、r g u e r i n 等人在 1 1 采用了另一种方法计算等效带宽， _ ) = 。，+ 鲁，其中y ，= 嫩v a 出， 0 4 ，所以占= 一下l o g ( p t ) 。 这种方法比第一种方法的利用信息多了一项y 。 另外，每个流的等效带宽是独立于其它所有的流的性质的，也 独立于流的数量和链路容量c ，它只由该流的特征、要求达到的丢 包率只和缓冲区大小b 决定。 2 2 3 丢包率曲线法 丢包率曲线表示的是丢包率与缓冲区大小之间的关系。加性等 效带宽法的丢包率曲线是呈指数性的，由只= e 。确定，但p “对于 丢包率只的逼近比较保守，对于某些信源来说误差较大。于是就产生 了寻找能更好地表示所观察到的丢包率曲线的方法。 n s h r o f f 等人提出的方法【1 5 】- 来源于对j p e g 的观察，这种方法 是通过观察得出v i d e o 速率的直方图量化后通常只有有限几个速率， 在此基础上再采用近似平稳估计。但是这种方法只适用于缓冲区很小 的情况，当缓冲区很大时误差较大。为修正这个误差，n s h r o f f 等人 提出在小缓冲区情况下用直方图模型，而在大缓冲区情况下用指数逼 近，在分界点处用两种方法计算出的结果的平均值来表示。这种方法 i ! 查奎望盔兰堕主生些堡奎旦竺塞塑坌里旦墨盟翌堕 被称为混合模型，适用于包到达过程是普通的调制m a r k o v 过程，而 对于调制m a r k o v 流状信源而言，耻_ 1e 。饥( 卜射一这勘t 为f 状态的平稳概率，丑为j 状态的到达概率。 a e l w a l i d 等人在 1 6 】提出，对于调制m a r k o v 流状信源而言，k 可以用无缓冲区的复用器中的k 代替，而k 可由c h e m o f f 定理来确 定，占可以是等效带宽法中的最大特征值，这样k 就远小于1 ，从而 提高等效带宽法的精度。 2 2 4 最大方差法 在 1 7 中，如果记=- t ，s - c , ，则尾丢包率为 p ( q 曰) = 尸( s u p x 。 bl 。最大方差法是基于如下观察：如果置是 高斯分布的，则p ( q 曰) 就可以得到很好的近似。由于x ，是由多个 流汇聚而来的，故假设置是高斯的是较为合理的。以的最大方差为 盯；= m a x v a t x , ) 虿五瓦矿。 当x ，为盯；时p ( x ， 占) 也达到最大值，因 比p ( 、s 。u p x , b ) z m a x p ( x , b ) ，这样j d ( 一 曰) 就容易解决了。 e k n i g h t l y 提出了随机包络方法 1 8 】，定义了流的随机包络r ( f ) 为蚴m a ( 等型卜删眵这样的流汇聚起删黔 j ! 查奎塑奎堂堡兰生兰竺垦茎 坚垒壅翌坌堡塑垦! ! ! ! 翌 数为f2 8 v a t ) 的高斯包络，则由此可以计算缓冲区的丢包率。 2 2 5 由大偏差理论改进的等效带宽法 等效带宽方法有两大缺陷，一是不适用于长相关的流，二是它不 可用于大数量的流。于是有人提出了另一个等效带宽的定义方法 1 9 ， 2 0 ，2 1 ，即e j ( s ，f ) ：1 0 9 e e a , l 。“，于是队长分布的尾丢包率满足 熙专l o g p ( q b ) = s u p i 母l s , e ，b 易( s , t ) - s ( b + c t ) j ，扩展资源到 c = n c ，b = n b ，j 类的源为n p j 个。这个结果是基于大偏差理论的。 另外，大偏差理论还用于长相关过程。e g l y r m 等人发现【2 2 】，对 于一大类的随机过程有l o g p ( a b ) 一国，而对于自相似或长相关过 程，尾丢包率可能不是指数的 2 3 ，2 4 。为解决这个问题，n g d u f f i e l d 等人用大偏差理论得到对于这类问题的解 2 0 ，即 l o g p ( q b ) 一g ( b ) ，这里g p ) 是曰的增函数，但不一定是线性的。 但是他们没给出g ( 8 1 的精确形式。 值得注意的是，这类方法在某种意义上来说不是加性的，因为某 个流需要的资源依赖于其它流的行为。因此，这类计算方法较为复杂。 2 2 6 仿真比较结论 e k n i g h t l y 通过仿真比较了上述五类基于参数的接纳控制的方 法，得出以下结论 2 5 1 ： 1 没有缓冲区的复用器性能大为劣化： 1 9 些塑奎婆叁兰堡主兰兰堡垒苎堡堑堕堡坌堡旦壁! ! 里堕 2 3 4 5 复用的流的数量对实现高精度至关重要： 丢包率曲线很可能不是呈指数性的； 要得到合理的统计复用增益和统计q o s 保证必须修正现有的 信源模型； 负指数开关信源得出的精度不能精确地保证压缩视频模型。 2 3 基于测量的接纳控制 所谓基于测量的接纳控制，就是在一个流进入网络之前，先测量 现有的网络资源的占用情况。测量网络就是以流所要求的速率向网络 发测量包。这些测量包在流过网络时可能被丢掉或是被打上e c n 拥 塞标记。测量包的丢包率或是被打上e c n 拥塞标记的概率能从侧面 反映出网络资源的占用情况，基于测量的接纳控制就是依据这一测量 结果来判定是否接纳该流。 在设计基于测量的接纳控制算法时，很自然地会希望算法达到 两个目标；一是要能提供一个参数，该参数要能准确地估计出导致服 务失败的级别；二是在给定服务失败级别情况下，实现尽可能高的网 络利用率。( 注：本文中服务失败是用丢包来表示的) 【4 2 】。现在不少 研究者已经提出了一些基于测量的接纳控制算法，如【2 6 ，【2 v ，【3 5 ， 3 7 【3 9 ，【4 0 ， 4 q ， 4 4 】， 4 5 ， 4 6 ， 4 7 ，这些算法或显式或隐式尽量 达到上述的两个目标。 虽然这些算法都是为了达到类似的目的，但它们在以下四个方面 也有所不同。首先有些算法是具有普遍意义的，基于某个数学公式( 如 大偏差理论) ；而另一些算法是在特定情况下使用的，缺乏理论基础。 苎查奎望查兰堡主皇些堕塞 翌堡壅塑坌兰塑垦篓堕塑 其次，用于判定接纳的式子也大有分别。第三。所有的算法都有个参 数，这个参数确定算法所实现的性能和利用率，有一些算法会校准这 个参数，使它成为所实现的性能的精确估计；而另一些算法默认为网 络运营商会实时将网络配置调整到适当的情况，它们不再做校准参数 的工作。最后，用于估计网络负载情况的测量过程是各不相同的，从 简单的样本点估计到指数加权平均，再到基于所测得的负载的均值和 方差做出的估计。 下面我们就简单地分析一下几种基于测量的接纳控制算法，我们 用丢包来表示服务失败，用丢包率来表征所得到的服务质量。由于网 络需要的是扩展性好的接纳控制算法，因此这里我们只考虑无须记录 每个流的状态的基于测量的接纳控制算法( m b a c ) ，即测量是针对聚 合的流量的，而不是针对单个流的。与此同时，我们也不考虑带有任 何假设的算法，无论假设是显式的还是隐式的，因为实际网络是不带 任何假设的。 设信源模型为令牌桶模型( ，6 ) ，定义p 为新流的峰值速率，i 为现 有负载的估计值，口为链路带宽， 为目标带宽利用率，一为已接纳 的流的数量，s 为h o e f f d i n g 界的参数。 m e a s u r e ds u m ( m s ) 。这种算法 4 0 】在满足( r + 口) c 缸的情况下允许新 流进入。这里对现有的流的速率的估计是用时域窗口估计器来实现 的。 h o e f f d i n gb o u n d s ( h b ) 。【4 7 中描述的接纳控制算法用h o e f f d i n g 界 来计算组流的等效带宽，如果( p + 口) c 舢，就允许新流进入，这里i ! ! 查窒望盔兰堡主兰些笙兰 壁堑窭堡坌鲤塑望! ! ! ! 塑 为测量得到的等效带宽。对负载的估计是通过指数平均测量机制实现 的饿。 t a n g e n t a tp e a k ( t p ) 。 3 7 】中提到了四种基于测量的接纳控制算法， t p 算法是其中之一，它是基于从h o e f f d i n g 界计算出的等效带宽曲线 的峰处的正弦值的。如果印( j e 一”) + e - s p 口s p ，就允许新流进入，这里 用的是样本点测量过程。 t a n g e n t a to r i g i n 口o ) 。【3 7 q b 提到了另一种基于测量的接纳控制算 法用的是等效带宽曲线的原点处的正弦值。如果c ”f s f ，就允许新流 进入。这里用的也是样本点测量过程。 m e a s u r ec a c ( m c ) 。 3 5 】中的算法是基于大偏差理论的，如果 ( p + i ) c p ，就允许新流进入，这里口为测量得到的现有的流的带宽。 估计带宽时将目标丢失率作为输入，同时使用了到达过程的扩展累积 发生函数。 a g g r e g a t e t r a f f i ce n v e l o p e s e ) 。【4 5 】中使用了对聚合的流量的最大 流量包络的测量，捕捉不同时刻的变化。这些流量包络的均值和方差 以及目标丢失率都作为该算法的输入。 上述六种m b a c 的理论基础、测量方法和接纳控制等式各有不 同，但它们也有相似的地方，例如每种算法都有基于测量到的流量的 负载估计，而且依据这个负载估计来做接纳判定。 l b r e s l a u 等人通过仿真( 网络拓扑是最简单的单条链路，链路 带宽为1 0 m b p s ，包长1 2 8 字节，缓冲区可容1 6 0 个包，采用两种信 源模型开关模型和令牌桶模型) 比较了这几种m b a c 4 2 。他们 从两个角度来评价算法的性能：第一是每种算法实现的丢包率和负载 ! ! 查銮翌- 犬堂堡主兰兰竺堡塞 堕竺塑塑坌堡塑丝! ! ! ! 翌 是如何折中的。这就是要考察算法如何在为单个用户提供良好的q o s 和实现较高的网络利用率( 即为更多的用户提供服务) 这对矛盾中找 到平衡点的。仿真结果表明，各种算法的性能基本差不多，没有哪一 种特别突出的。对于m b a c 而言，1 ) 测量过程和判定过程是去耦的； 2 ) 不同的流产生的性能的不同是由策略造成的，而不是由于算法不 同；3 ) 在长相关情况下，m b a c 的性能更好一些，在某些时候甚至 比基于参数的接纳控制算法更优。 第二个评价的角度是算法所提供的可调参数在多大程度上可以 使网络运营商通过设定不同的参数达到调节网络性能的目的，也就是 说通过调节参数改变网络在性能曲线上的作用点。但仿真的结果是令 人失望的，虽然有些算法的性能相对好一些，但没有一种算法能可靠 地使网络的实际性能与预期的目标相匹配。因此网络运营商不得不通 过监测网络来学习如何设定参数。在这一方面，今后的算法要如何改 进还是一个有待进一步讨论的问题。 上面主要是从算法本身对m b a c 进行讨论，下面我们再从实现 的角度来考察一下现有的m b a c 。 首先，测量包由谁来发呢? 有两种可能，一种是由信源自己来发， 另一种就是由网络边缘路由器来发。我们认为由谁来发测量包并无多 大影响，关键在于信源是否是诚实的，即在允许进入后，信源是否以 其在测量网络前所声称的速率发送的数据流。若信源有欺诈行为，即 以较低的速率发测量包，又以较高的速率发数据包，就会影响网络的 性能和网络中其它流得到的服务。 其次，测量过程是如何进行的? 在测量过程中，测量包可能是和 后来的数据包有相同的优先级别，也可能测量包的优先级低于数据 韭查窭望查堂竺! 兰些堡壅 堕垒塑翌坌堡塑塑! ! ! ! 塑 包，因此我们称前者为带内测量，称后者为带外测量。同对，网络所 用的拥塞指示也有两种：丢包或是e c n 标记，依此可以将基于测量 的接纳控制分为四类 3 0 】。在i 3 1 ，3 3 】中所描述的方法是基于丢包的 带外测量，测量包的优先级低于数据包。在 3 4 ，3 8 1 0 0 ，使用的就是 基于代价( p r i c i n g ) 的e c n 标记的带内测量，对测量包和数据包一视同 仁，拥塞了就打上标记，每个流可以以任意速率发送包，但必须为打 上拥塞标记的包付出代价。在这种情况下，接纳控制是由第三方( 或 是网络本身) 提供的服务，由此为流提供某种得以保证的代价( 就象 传统的集成服务中的服务级别保证) 。于是就产生了这样的疑问：( 1 ) 丢包或是e c n 标记作为拥塞指示，哪个的性能更好? ( 2 ) 带内测量 和带外测量，哪个的性能更优? 从理论上来看，若接纳门限设为f ，则测量时间就要持续s 。的 几倍，这样的话，对以丢包作为拥塞指示而言，丢包率低( 即接纳门 限小) 就意味着测量时间长，这将导致网络带宽的浪费和数据传输时 延的增加。而采用带外测量虽然实现起来较复杂，但丢包率显然会低 于带内测量，所以可以采用基于带外测量和丢包的接纳控制。另一方 面，由于e c n 标记的概率高于丢包率，因此在门限的选择上，采用 e c n 标记方法的门限必然要大于采用丢包方法的门限。因此可以采用 基于带外测量和丢包的接纳控制或是基于e c n 标记的接纳控制。但 这两种方案也存在着不足之处。那就是选择合适接纳门限并同时达到 合适的数据包丢包级别很困难。 l b r e s l a u 等人通过仿真 3 0 l 发现，基于带外测量的接纳控制的性 能并非是总优于基于带内测量的接纳控制，但基于e c n 标记的接纳 ! ! 查奎里奎鲎堡主兰些堡奎 塑竺望! 曼坌墼塑丝堕竺堕 控制和基于带外测量的接纳控制以及这两者的结合接纳控制的好处 就在于能在一定的测量时间内能实现较低的数据包丢包率，但是