动态带宽算法

动态带宽算法（共7篇）

动态带宽算法 篇1

摘要：本文简要介绍了以太网无源光网络 (EPON) 技术的基本原理, 并主要针对EPON的动态带宽分配算法问题 (DBA) 进行深入研究和分析。

关键词：EPON,DBA,轮询

0、引言

随着光纤通信成为现代通信的主流技术，在向着全光网络的发展过程中，EPON结合以太网和无源光网络技术，具有协议简单、成本低、带宽高、易于兼容等优点，成为解决"最后一公里问题"[1]的最佳解决方案之一。但与APON相比，EPON存在一个天然的缺陷，即不能很好的支持QoS (Quality of service) ，不能很好的满足三网合一的需求。要成为宽带接入的主流技术并大举进入市场，必须既能稳定地支持传统的电话业务、数据业务，又能高效地保证新兴实时性业务如网络电视，视频点播 (VOD, video on demand) 等的质量，因此进一步对EPON的带宽分配算法的研究有着非常重要的意义。

1、EPON的基本原理

EPON是采用PON的拓扑结构实现以太网接入的网络，由三个部分组成：光线路终端（OLT）、光分配网络 (ODN) 和光网络单元 (ONU/ONT) [2][3]。如图1所示，OLT处于局端，可以是一个交换机或路由器，也可以是一个提供面向无源光纤网络接口的多业务平台，向上介入上一层网络，向下为ONU或用户提供带宽分配、网络安全和管理等功能。ODN是一个光分路器，分光能力在1:16到1:128之间。ONU处于用户一侧，根据采用的配置方案（如FTTH、FTTB等）不同，具体的位置也不同，全光网络中ONU可置于用户家中，ONU可通过层叠为多个终端用户提供共享高带宽的服务。

EPON网络中，采用可变长的数据包，最高可达1518字节，上行方向采用1310nm波长，下行方向采用1550nm，波长传输速率为1.25Gbit/s。如图2 (a) 所示，由OLT到ONU下行采用广播的方式，通过ODN将数据包发送给所有的ONU，由于每个ONU在注册时都被分配了唯一的ID，通过读取数据包中的ID，只有与本ONU的ID符合的才会被接收，其他的数据包将被丢弃。如图2 (b) 所示，上行采用TDMA技术，实现多点到点的接入，帧与帧之间需要一个时间空隙，即保护时间，OLT可以在这段时间内对接收器进行调整电平的增益，保护带宽最大为2us。因为多路信号要共享一根光纤，有可能会出现碰撞现象。EPON利用多点控制协议（MPCP）进行OLT和ONU之间的通信，由OLT根据网络情况，统一为ONU分配带宽（使用时隙），基于网络严格同步的情况下，既可以避免碰撞（非初始注册过程）现象，又可以利用一定的带宽分配算法，实现高效的带宽利用率。一个完善的DBA方案应包括轮询机制和带宽分配算法两部分，下面从这两个方面入手来对EPON系统的带宽、包时延、丢包率、Qos等性能参数进行研究。

2、轮询机制

EPON的MPCP提供的REPROT和DATE帧为OLT和ONU之间的信息互动提供了支持，这种Request-Grant问答机制，为带宽分配提供了实现手段。轮询的顺序也有多种选择，可以按根据注册先后顺序确定的固定顺序轮询、按负载的轻重重的在前轻的在后或者反过来等等，结合各自算法的特点来进行选择。典型的轮询是基于周期的，在一个周期内，OLT对ONU逐个询问需求情况，并根据请求授权带宽。因此从轮询周期的角度又可以分为：固定周期轮询、可变周期轮询 (自适应周期轮询) }]和周期一定受限的轮询[4]。

轮询周期固定，一定固定时间内的下行授权帧数就固定，不会随着上行网络负载的增大下行授权控制的插销。但是当系统带宽满足了所有ONU的请求后还有残余时，却因为周期的固定性而无法顺延至下一轮继续使用，降低了带宽利用率。

典型的可变周期轮询是IPACT算法，它根据ONU上报的队列长度进行带宽授权，从而在一周轮询下来得到的轮询周期是不固定的。这种轮询周期的带宽利用率比较高，上行信道利用率可以逼近于1，但它的不足在于：轻负载时，轮询周期很小，授权帧的发送频率极高，会消耗相当一部分的下行信道带宽；一部分业务量大的用户总能得到足够的带宽，从而使周期变长，使得业务量少的用户的时延加大，违反了公平性的原则。

周期可变的轮询机制，为周期设定了一个范围，一定程度上解决以上的问题。同时，此时的轮询周期的大小可以一定程度上反映网络负载的情况。目前，考虑到公平性问题，防止个别高负载的用户垄断着信道，OLT会以一定的标准来限制对每一个ONU的开窗大小进行限制，称为最大带宽限制问题，在重负载的情况下，它就可以决定最大的轮询周期，但是如果开窗过大，就会导致所有的帧的延时更长，如果太小，就会把带宽浪费在保护带宽上。目前对于轮询周期的下限还讨论不多。

除了上面介绍的轮询机制以外，带宽分配机制将对DiffServ[5]的处理反映在了轮询机制上。OLT对同一优先级的用户进行集中授权，这样做的好处就是保证了高优先级业务的带宽，提高服务质量。为了算法的需要，则是将数据与控制帧分离，此时ONU上报的队列长度更加接近上传时刻的队列长度值，可以减小时延，同样它也需要增加保带宽。

总之，轮询机制是时隙分配机制的一个组成部分，根据不同的算法和追求目标的不同，可以适当选择自己的轮询分配机制，同时也可以通过轮询机制来弥补算法中的不足。

3、带宽分配算法

带宽的分配主要分为静态和动态两种:静态带宽分配 (SBA，又叫固定时隙分配) 按照各ONU预定的带宽进行初始配置，运行期间不管实际的网络状况如何该值不变。SBA简单，容易实现，但是没有实现带宽的统计复用，带宽的利用率低。动态带宽分配 (.DBA) 是指OLT根据即时的网络业务情况对每一个ONU逐个分配带宽，一个周期更新一次，很明显，DBA的带宽利用率比SBA要高，上行带宽毕竟是有限的，为了让所有的终端用户都能尽可能的满意，DBA更能满足要求。下面就来分析几个主要的DBA算法。:

3.1 带宽受限分配算法（LBA)

LBA通过REPORT/GATE来跟踪业务量，每个ONU的可分配的最大带宽根据用户等级、业务类别等来确定。如果请求的带宽长度小于这个值时，就分配给它请求的带宽，否则就按这个值来授权。LBA通过报告队列长度的方式来跟踪业负载，由于业务流量是动态的，所以它的分配时隙大小也是变化的，因为每个轮询分配的时隙也是不同的，所以最终导致它的轮询周期也是变化的。LBA的保守性表现在通过对每个ONU的授权的限制来抑制了带宽的恶性竞争，不会出现业务量大的用户独霸着带宽，业务量小的用户得不到带宽的现象。LBA也是目前使用最广泛，性能最好的DBA算法之一，它的带宽利用率比较高。

3.2 基于信用的带宽分配算法 (CBA)

在REPORT/GATE机制下，每个ONU发送完REPORT帧后都经历了一段等待时间后才能继续发送缓冲区内的数据。ONU在t1时刻上报队列长度，在t3时刻开始上传数据，在t1到t3这段等待时间内，仍然有可能有新数据进入缓冲区内。如果在t1时刻上报队列长度时，对下面等待时间内可能新到的业务量进行估算，那么新到的数据帧就不需要多等一个周期再发送。CBA就是把这部分等待周期内可能新进入的数据帧也考虑进去，在原来上报的队列长度的基础上再加上了一个信用C，这里C可以是常数，也可以是线性表达式。线性信用是基于网络业务的可预测性，因为一般长突发业务会持续一段时间，前一周期的信息对后一周期的等待周期的新增业务量具有价值，可以进行一定程度的预测。

这种带估算的带宽分配方法的好处在于可以减小部分帧时延，但是估算要根据不同业务的特点来设计，而且也不是任何估算都是有益的，因为以太帧是不定长的，如果估算分配的带宽不足以满足实际的帧通过，很可能带来新的带宽浪费。

3.3 弹性带宽分配算法 (EBA)

EBA是在LBA的基础上的一个变通。LBA中每一个ONU都有一个最大开窗，每个ONU的授权都不可以超过这个值，E-BA中取一个最大总授权带宽值，所有轻负载ONU使用完后残余的那部分带宽，在一个周期内进行再此分配。很明显这种分配方式往往是收集完所有的ONU的信息之配处理的，它必须与相应的轮询机制结合使用，同时这种算法容易实现公平性分配，是使用比较广泛的算法。

4、结论

EPON作为众多宽带接入的最佳方案之一，有着协议简单成熟、标准化程度高、建设维护成本低廉的巨大优势，要更好的满足用户的Qos，对EPON的带宽分配算法进行研究有着非常重要的意义。本文从EPON的工作原理入手，深入讨论了各种带宽分配算法的优势和劣势，不同的算法必须采用相应的轮询机制，对性能参数的制约也各有不同，因此必须进一步根据具体的网络用户的需求来设计制定带宽分配方案。

参考文献

[1]Kramer G, Pesavento G.Ethernet Passive Optical Network (EPON) :Building a Next-Generation Optical Access Network[J].IEEE Communica-tion Magazine, 2002, 40 (2) :66-73.

[2]孙学康张金菊.光纤通信原理.北京:人民邮电出版社, 2004

[3]原荣.宽带光接入网.北京.电子工业出版社.2003

[4]李莉莉符建.一种轮询周期受限的EPON双级动态带宽分配算法.光电工程.2006.33 (9) :110-114

[5]Yuanqiu Luo, Nirwan Ansari.Bandwidth Allocation for Multiservice Ac-cess on EPONs[J].IEEE Optical Communications, 2005, 43 (2) :16-21.

动态带宽算法 篇2

GPON系统是基于GSR (Gigabit Service Requirements) 制定的, GSR规定了GPON所要达到的关键指标, 是系统设计的依据, 它确保GPON比其它的PON能更加贴近实际需求。GPON系统是由ONU、OLT和ODN组成, OLT位于局端, 是整个GPON系统的核心部件, 向上提供广域网接口, 具有集中带宽分配、控制光分配网 (ODN) 、实时监控、运行维护管理光网络系统的功能;ONU放在用户侧, 为用户提供10/100Base T、T1/E1和DS-3等应用接口, 适配功能在具体实现中可以集成于ONU中;ODN是一个连接OLT和ONU的光无源设备, 其功能是分发下行数据和集中上行数据。GPON中下行数据采用广播方式发送, 上行数据采用基于统计复用的时分多址方式接入方式。

2 多等级服务动态检测GPON动态带宽分配算法

2.1 宽带动态检测算法

假设在GPON系统中共有N个ONU, 在一个周期时间T内可用带宽为Wti, 经过时间k后, 传输的总宽带为Wt (k) , 则有:

根据定义1, 式 (2) 具有以下性质:

性质1:若带宽以尺度因子进行分解或伸缩, 则ΔW (k) 保持不变。

证明:设ΔW' (k) 为以尺度因子s进行伸缩后的当前平均动态改变宽度, 因此:

同理可以证明以尺度因子s进行分解后ΔW (k) 保持不变。

性质2:由于ONU的对象不同, 从而对带宽的需求也就不同。假设在时间k时, ONU对带宽的需求发生改变, 则改变后GPON系统分给ONU带宽的剩余 (缺少) 部分可以用新的带宽信息进行补充, 此时, 当前平均动态改变宽度ΔW (k) 发生变化。

证明:设ΔW' (k) 为包含ONU带宽需求改变的当前平均动态改变宽度, 则有:

因此, ΔW (k) 发生变化。

若在时间k时, ONU的带宽需求发生变化, 从带宽动态分配的角度分析, 也就是将剩余 (缺少) 带宽部分调制到原有带宽上, 即为:

其中a为调制因子, 且a≥1。根据式 (2) 可得:

其中Ec (k) 为时间k内, ONU需求带宽改变的总和。根据式 (5) 可知, 在动态宽带分配中, 只需要对当前周期需求带宽改变总和进行补偿, 且补偿变量为blaΔP (k) 就可以实现对原有带宽的调制。从另一个角度分析, blaΔP (k) 可以作为评判ONU带宽需求改变的判据。同样根据式 (5) 可知, blaΔP (k) 与ΔW'p (k) 具有相关性, 因此, 可以利用blaΔP (k) 与ΔW'p (k) 的互相关函数来表达ONU带宽需求的改变。假设相互关联函数为,

根据定义可知, ΔP (k) 、ΔW (k) 相互独立, 从而E[ΔP (k) ΔW (k) ]=0, 基于此, 可以根据a E[ΔP (k) ) 2]的大小判断ONU需求带宽改变的程度。假设在GPON动态宽带检测中, 系统的误差概率为a, 设定ONU需求带宽改变阈值a E[ΔP (k) ) 2]/2, 则有:

2.2 多等级服务动态检测GPON动态带宽分配算法

多等级服务就是根据各种业务 (语音、E-mail等) 需求的不同将接入业务分为高、中、低三个等级, 并且由OLT统一对三个等级进行带宽分配, 在初始时刻高等级业务分配为固定带宽, 中、低等级业务分别分配为确保带宽和普通带宽。在本文提出的多等级服务动态检测GPON动态带宽分配算法中结合了多等级服务原则和当前平均动态改变宽度的宽带动态检测, 从而带宽随着ONU需求而发生改变, 改善了GPON系统带宽分配不公平的问题, 同时, 通过动态带宽需求检测可以降低丢包率。具体算法步骤如下:

步骤1初始化, 假设GPON系统中共有N个ONU, 总宽带为Wj (k) , j=1, 2, 3…m为第j个高等级需求在时间k时的固定带宽, m为高等级需求的个数, Wi (k) , i=1, 2, 3…n为第i个中等级需求在时间k时的普通带宽, 则低等级需求的普通带宽可以表示如下:

式中Wl (k) 为第l个低等级需求的普通带宽, L为低等级需求的个数。

步骤2多等级服务带宽分配, 原则:确保高等级业务带宽的需求, 根据宽带动态检测算法式 (6) 、 (7) 判断ONU业务等级的变化, 根据式 (5) 对剩余带宽进行动态分配, 以响应ONU业务等级变化而需要的带宽改变。若ONU业务等级发生改变剩余带宽为ΔP (k) , 则Wj (k+1) , j=1, 2, 3…m为第j个高等级需求在时间k+1时的固定带宽可表示如下:

则Wi (k+1) , i=1, 2, 3…n为第i个中等级需求在时间k+1时的普通带宽可表示如下:

步骤3循环判断动态带宽分配, 根据式 (9) , (10) , 确定了下个周期的高、中等级业务带宽, 根据宽带动态检测算法检测多等级业务带宽需求, 若不发生带宽需求改变, 则保持式 (8) 、 (9) 、 (10) 对带宽的分配, 若发生需求改变则重新按照步骤2进行动态分配。

3 结论

本文针对GPON网络中带宽分配及传输延时的问题, 提出了一种多等级服务动态检测的GPON动态带宽分配算法。通过理论分析及推导, 给出了一种当前平均动态改变宽度的几何宽度变量, 结合面向多等级服务原则, 得到了基于当前平均动态改变宽度的多等级服务动态检测GPON动态带宽分配算法。

摘要：针对如何实现吉比特无源光网络 (GPON) 带宽分配公平性, 降低网络丢包率及传输延时的问题, 开展了多等级服务动态检测的GPON动态带宽分配算法研究。首先分析了GPON工作基本原理, 提出了一种针对带宽几何宽度的变量——当前平均动态改变宽度, 基于该变量推导了当前平均动态改变宽度的宽带动态检测算法, 其次将此算法与面向多等级服务原则相结合, 得到了基于当前平均动态改变宽度的多等级服务动态检测GPON动态带宽分配算法。

动态带宽算法 篇3

1 OFDM-PON技术

OFDM-PON技术是将OFDM应用到PON(Passive Optical Network)系统中,利用了OFDM的频分复用技术,增加了频谱利用率和可接入用户容量。

OFDM-PON系统在上行和下行方向使用光纤进行传输[5]。在下行传输方向,光线路终端OLT(Optical Line Terminal)从网络端接收数据包,进行OFDM调制、光调制后经光分配网ODN(Optical Distribution Network)将光波信号以广播的形式发送给各个光网络单元ONU(Optical Network Unit)。各ONU端将接收到的光波信号通过光接收机进行解调[5],再进行OFDM解调,将得到的数据发送给各个用户。在OFDM-PON下行传输方向由OLT以广播的形式向各个ONU发送数据,是点到多点的方式,各个ONU取到自己所需要的数据即可。所以,在OFDM-PON下行传输方向上不会产生带宽分配的冲突[7]。OFDM-PON的下行传输如图1所示。

在上行传输方向,各ONU统计各用户所需要上传的数据总量,再将统计好的数据进行OFDM调制、光调制后通过ODN向OLT进行传输。在OLT接收端利用光接收机将光波信号解调后进行OFDM解调,再将数据发送出去。OFDM-PON的上行传输如图2所示。

2 OFDM光纤传输性能

OFDM信号在光纤传输系统中传输时,在发送端经过一系列变换产生OFDM的电域信号,经过光调制后在光纤信道中传输。在接收端采取直接检测的方式对光信号进行光解调,恢复成电信号之后再进行OFDM解调,传输过程如图3所示。

由图3可知,在发送端,当数据流进入到OFDM光纤传输系统后,先进行串并变换,将快速的串行数据流变成n路慢速的并行数据流,其周期也相应扩展n倍。串并变换后对并行数据流分别进行星座映射,将二进制数在星座图上映射成复数形式,在OFDM光纤传输过程中一般都采用正交幅度调制(Quadrature Amplitude Modulation,QAM)来进行星座映射。星座映射后对信号进行IFFT和循环前缀的添加,循环前缀可以有效抑制符号间干扰(ISI)。对加入循环前缀的符号进行并串变换、数模转换。提取OFDM符号的实部和虚部,进行上变频。用射频(RF)OFDM信号加载到光载波,利用马赫-曾德调制器(MZM)对信号进行光调制[8],将调制好的信号在光纤信道内进行传输。在系统接收端,利用光电探测器(PD)采取直接检测的方式对接收到的光信号进行光电转换,得到输出数据。

本地激光器频率设为f0,由于OFDM光纤传输系统的MZM工作在线性区域,光OFDM信号为

s(t)=exp(j2πf0t)+γexp[j2π(f0+Δf)t]sB(t) (1)

经过光纤信道传输后,OFDM信号可以表示为

$r(t)=\exp [\text{j}(2\text{π}f{}_{0}t+\Phi {}_D(-\text{Δ}f)+\phi (t))]+\gamma \exp \{\text{j}[2\text{π}(f{}_0+\text{Δ}f)t+\phi (t)]\}\cdot {\displaystyle \sum _{k=-{\rm N}/2+1}^{{\rm N}/2}x}{}_{ik}\exp (\text{j}2\text{π}f{}_{k}t+\Phi {}_D(f{}_k))(2)$

其中,$\Phi {}_D(f{}_k)=\text{π}cD{}_t\frac{f{}_k^2}{f{}_0^2}$,表示由色散引起的位移。

在信号经过光纤信道后,在接收端,采用直接检测的方式,将PD光电检测器接收到的光信号进行检测,如图4所示。

将PD光电检测器的检测方式看成平方律检波,则可将经过PD检测器后的光电流表示成

$\begin{array}{l}{\rm I}(t)=R\left|r(t)\right|{}^2\\ \left|r(t)\right|{}^2=1+2\gamma \mathrm{Re}\{\exp (\text{j}2\text{π}\text{Δ}ft){\displaystyle \sum _{k=-{\rm N}/2+1}^{{\rm N}/2}x}{}_{ik}\exp \\ [\text{j}2\text{π}f{}_{k}t+\Phi {}_D(f{}_k)-\Phi {}_D(-\text{Δ}f)]\}+\left|\gamma {}^2\right|{\displaystyle \sum _{k=-{\rm N}/2+1}^{{\rm N}/2}}\\ {\displaystyle \sum _{q=-{\rm N}/2+1}^{{\rm N}/2}x}{}_q^{*}x{}_k\exp [\text{j}2\text{π}(f{}_k-f{}_q)t+\Phi {}_D(f{}_k)-\Phi {}_D(f{}_q)]\end{array}(3)$

式中,R代表平方律检测的响应度,其中直流项可以通过隔直滤波器将其去掉,通过加大保护间隔也可以将非线性的失真项去掉,这样就只剩下含有OFDM的线性信息成分。在将光信号转换成电信号后,对电信号进行与OFDM发送端相反的逆过程:去循环前缀、串并转换、FFT、数字解调等,这样就得到了解调后的数据流,完成了OFDM光纤传输。

采用Matlab软件对OFDM光纤信道传输进行建模仿真,定义各个部分的参数:随机伪序列长度220,在数字调制过程中采用16QAM调制,子载波数为512,光纤信道是1 550 nm标准单模光纤,光纤色散系数为17 ps/(nm·km)。传输距离、系统速率与误码率关系如图5所示。

传输距离取值500～1 000 km,系统速率取值10 Gbit·s-1、15 Gbit·s-1以及20 Gbit·s-1。由图5可知,在系统速率相同的情况下,误码率随传输距离的增加而增大;在传输距离相同的情况下,误码率随系统速率的增加而增大。在误码容限10-3以内,以10 Gbit·s-1的系统速率传输时,传输距离可以达到580 km。

3 改进CP算法设计

CP算法是众多带宽分配算法中较为常用的一种。CP算法可根据用户所需上传数据中不同类型的业务,对时延特性的敏感程度调整发送顺序,尽量满足用户对不同业务的时延要求。一般情况下,需要上传的业务按照优先等级分为EF、AF、BE业务,其中EF业务优先级越高,对时延最敏感,AF其次,BE业务优先级最低,时延不敏感。

3.1 传统CP算法

设在OFDM-PON中存在3个ONU,运用CP算法为其分配带宽,算法的时序过程如图6所示。

CP算法一个周期内的工作流程如下:

(1)在一个周期开始阶段,向各个ONU发送此周期内各ONU获得子载波的数量。在图6中用G表示发送的分配载波通知。

(2)各ONU接收到分配通知后,根据自身所获得子载波数量进行业务上传,在上传过程中,将业务划分为EF、AF、BE这3种类型分别上传,并在子载波的末尾添加下个周期上传业务量的请求。

(3)OLT接收到各ONU上传的数据后,将需要上传到服务器的数据进行上传,并在子载波的末尾接受下一个周期业务量的请求,将所有ONU的请求汇总后,进行CP算法的运算,首先进行ONU之间的分配。在进行ONU间分配后,OLT还需要根据各ONU上传业务类型的不同进行ONU内部带宽分配。传统CP算法将ONU得到的带宽依次分配给EF、AF、BE业务。进行完ONU间和ONU内分配后,CP带宽算法分配完成。

在应用传统CP算法时,由于在系统中存在轮询这一过程,会有图6中TIDLE的出现,在TIDLE这一时间段内上行链路没有上传任何数据,使得上行链路存在浪费,造成上行链路利用率低。同时,在重负载下,各ONU得到所分配的带宽后,率先为EF以及AF分配带宽,BE业务最后分得带宽。当用户重负载时,BE业务始终得不到分配的上传带宽,导致BE业务一直堆积,使得BE业务的时延变大,超出用户的承受范围。

3.2 改进CP算法

改进CP算法从上传业务方式和ONU内分配方式两方面对传统CP算法进行了改进。

改进CP算法在上传方式上较传统的CP算法有所不同,传统CP算法是将所有ONU的申请集中到一起进行运算和分配,向各ONU发送带宽分配信息。各ONU得到带宽分配信息后再将EF、AF、BE业务分别上传;而改进CP算法是向ONU分配固定的子载波数量用来上传EF业务,对不同ONU的AF、BE业务进行轮询,控制各ONU上传带宽。改进CP算法时序流程如图7所示。

在改进CP算法中,ONU间带宽分配方式与传统CP算法相同。在进行ONU间分配后,各ONU得到OLT所分配的带宽,开始进行ONU内部分配。

如图8所示,Hrest代表将一部分带宽分配给EF业务后剩余的带宽;hi,2,hi,3分别为ONU内部带宽分配中AF、BE得到的带宽,当进行ONU间带宽分配后,OLT需要进行ONU内分配。与传统的CP算法不同,改进CP算法会根据不同的负载情况进行不同的分配方式。改进CP算法与传统CP算法的ONU内带宽分配方式不同:传统CP算法依次向EF、AF、BE业务进行带宽分配;而改进CP算法充分考虑到重负载时BE业务的时延问题,更合理的将带宽进行按比例分配

$h{}_{i,2}={\rm H}{}_{\text{r}\text{e}\text{s}\text{t}}\times \frac{R{}_{AF{}_i}}{R{}_{AF{}_i}+R{}_{BE{}_i}},h{}_{i,3}={\rm H}{}_{\text{r}\text{e}\text{s}\text{t}}\times \frac{R{}_{BE{}_i}}{R{}_{AF{}_i}+R{}_{BE{}_i}}$ (4)

4 仿真与分析

用OPNET软件对OFDM-PON进行建模,对传统CP算法和改进CP算法分别进行仿真,仿真场景参数如表1所示。

在不同场景下其链路利用率对比如图9所示。

由图9可知,在3个场景情况下,改进CP算法的上行链路利用率都高于传统CP算法,是因为在改进CP算法下,EF业务的传输不需要轮询的控制;在传统CP算法下,进行轮询时,所有业务是停止上传的,故改进CP算法下的链路利用率比传统CP算法高。

在轻度负载和中度负载时,传统CP算法和改进CP算法在业务时延特性的仿真结果基本相同。在重负载时,EF、AF、BE业务时延对比如图10所示。

在重度负载下,改进CP算法下BE业务的时延远小于CP算法下BE业务的时延,与此同时,改进CP算法下的AF时延较CP算法下有少量增加。这是因为在改进CP算法下,合理安排了AF业务和BE业务的子载波分配情况,通过牺牲一部分AF业务的时延而保证了BE业务时延,满足了客户在重度负载情况下的BE业务上行传输需求。而CP算法下是满足EF业务传输后,先传输AF业务而后传输BE业务,并不能保证BE业务的时延,故在改进CP算法下BE业务的时延远小于CP算法下BE业务的时延,保证了客户需求。

5 结束语

文中对OFDM-PON的原理进行了论述,通过对OFDM光纤信道的传输进行建模和仿真,分析并验证了OFDM在光纤信道传输中的可行性。对传统CP算法和改进CP算法分别进行了建模,对不同业务类型的时延特性和整个系统的链路利用率进行了仿真,得到了在传统CP算法和改进CP算法下的系统传输特性,验证并分析了改进CP算法相对于CP算法的优越性。

摘要：正交频分复用是一种多载波调制技术,用于解决各种无线和有线通信系统中因信道色散引起的符号间干扰问题。近年来的研究表明,OFDM在无源光网络方面有广泛地应用前景。文中以OFDM-PON为对象,对其传输性能、动态带宽分配算法进行了研究。提出了基于传统CP算法的改进算法,使OFDM-PON系统的上行带宽分配性能得到改善。经过建模仿真证明,系统上行业务时延和链路利用率都得到了提高。

关键词：OFDM-PON,动态带宽分配,CP算法,服务质量

参考文献

[1]彭木根,王文博.下一代宽带无线通信系统OFDM[M].北京:机械工业出版社,2007.

[2]张海滨.正交频分复用技的基本原理和关键技术[M].北京:国防工业出版社,2006.

[3]曹志刚,钱亚生.现代通信原理[M].北京:清华大学出版社,2006.

[4]尹长川,罗涛,乐光新.多载波宽带无线通信技术[M].北京:北京邮电大学出版社,2004.

[5]WILLIAM S,IVAN D.Orthogonal frequency division multi-plexing for optical communications[M].USA:Academic Press,2010.

[6]邓大鹏.光纤通信原理[M].北京:人民邮电出版社,2003.

[7]SCHMIDT B J C,LOWERY A J,ARMSTRONG J.Experi-mental demonstration of20Gbit/s direct-detection optical OFDM and12Gbit/s with a colorless transmitter[C].Ana-heim,CA:Proceeding Optics Fiber Communication Confer-ence,2007:18.

动态带宽算法 篇4

EPON (Ethernet Passive Optical Network, 以太无源光网络) 是光接入网的一种重要技术, 以其高带宽、易维护和廉价等优势成为接入技术的一个发展趋势[1]。为了适应不同用户的各种业务需求, EPON必须能够支持业务QoS需求, 并且利用动态带宽分配提高上行带宽的利用率, 为用户提供更好的服务, 介质访问控制 (Medium access control, MAC) 是以太网无源光学网络设计中的一个关键问题。EPON由三部分组成:OLT (Optical Line Terminator) 、ONU (Optical Network Unit) 以及ODN (Optical Distribution Network) 。EPON采用多点到点上行链路模式, 多个ONU共用一个信道, 主要数据传输方式为TDMA[2]。OLT集中控制各个ONU的上行数据传输, 主要利用Gate和Report机制来动态地分配带宽。现在的MAC机制有:停等机制 (图1) , 交叉询问机制 (图2) 。

如图1所示:在停等机制中, OLT向某一ONU发送GATE帧, 在此ONU回复OLT之前, OLT是不接受其他ONU的任何数据和报告的。当受到此ONU的数据报告后, 再向下一个ONU发送GATE帧。由此可见, 在OLT等待某一ONU的报告的这段时间内上下行信道都是空闲的, 没有任何数据的传输, 这是对带宽的极大浪费。对此进行改进就有了交叉询问机制。

如图2 所示, 在交叉询问机制中, OLT连续发送GATE帧给所有在线的ONU, 然后ONU顺序发送自己的报告。由此可见, 上下行信道得到了充分利用。但是, 因为信道的带宽是有限的, 因此, 又引发了一个问题, 当前面几个ONU的带宽报告把全部的带宽给占据后, 那么报告的ONU将不可能分配的带宽, 这严重违反了公平性的原则。

为了进一步改善上述两种MAC机制, 针对上述两种机制的问题, 提出了停等交叉询问机制, 如图3所示, 首先, 它与交叉询问机制一样顺序发送GATE帧给所有在线的ONU, 然后, 停止计算所有ONU的报告, 然后再分配给ONU带宽。

1 改进的带宽分配算法

现有的EPON带宽分配算法大多是基于MPCP协议的, 如IPACT[3]算法;BGP[4]算法; CBR算法等。但现有的算法都存在着问题, 如QoS实时业务的保证问题, 公平性问题, 带宽利用率问题, 轻负荷恶化问题等;结合了APON (ATM Passive Optical Network) 的最小分配法和最少业务量损失法[5], 提出改进的动态带宽分配算法, 并构建了基于OPNET的系统仿真模型, 仿真结果表明该算法有效地解决了, 轻负荷恶化问题, 低EF等级时延抖动等问题。

改进的算法中采用了支持服务等级协议 (SLA) [6], 将业务划分为:EF业务实时性比较强, 对时延非常敏感, 必须保证带宽按时送达, 优先级最高;AF:对时延有一定的要求, 带宽必须保证, 优先级次之;BE:对时延和带宽没有要求, 尽量传送, 优先级最低。

其中, 对高优先级的EF业务采用固定带宽分配, 对中低优先级的AF、BE业务采用根据负载情况分配的原则。在Report帧中只有中、低优先级队列大小, 高优先级业务占非常小的带宽。

高优先级的业务分配的带宽为G${}_i^{{\rm H}}$为:G${}_i^{{\rm H}}$=R${}_i^{{\rm H}}$, 中优先级的业务分配的带宽G${}_i^{{\rm M}}$为:

$G{}_i^{{\rm M}}=\min \left(R{}_i^{{\rm M}}‚\left(B{}_{\text{t}\text{o}\text{t}\text{a}\text{l}}-{\displaystyle \sum _{r=1}^{n}G}{}_i^{{\rm H}}\right)\frac{R{}_i^{{\rm M}}}{{\displaystyle \sum _{i=1}^{n}R}{}_i^{{\rm M}}}\right)$

低优先级的业务分配的带宽G${}_i^L$为:

$G{}_i^L=\left(B{}_{\text{t}\text{o}\text{t}\text{a}\text{l}}-{\displaystyle \sum _{r=1}^n(}G{}_i^{{\rm H}}+G{}_i^{{\rm M}})\right)\frac{R{}_i^L}{{\displaystyle \sum _{i=1}^{n}R}{}_i^L}$

每个ONU的参考授权带宽为:

$B{}_i=\frac{({\rm T}{}_{\text{c}\text{y}\text{c}\text{l}\text{e}}-{\rm N}*G{}^{{\rm H}})*W{}_i*R{}_u}{8*{\displaystyle \sum _{i=1}^{{\rm N}}W}{}_i}$

实际的授权带宽:

$B{}_i=\{\begin{array}{l}R{}_i=(R{}_i^{{\rm H}}+R{}_i^{{\rm M}}+R{}_i^L)\text{i}\text{f}(R{}_i＜B{}_i)\\ B{}_i\text{i}\text{f}(R{}_i\ge B{}_i)\end{array}$

其中, B${}_i^{{\rm H}}$是第i个ONU高优先级业务请求的带宽, R${}_i^{{\rm M}}$是第i个ONU中优先级业务请求的带宽, Ri是第i个ONU低优先级业务请求的带宽, Wi为各个ONU的授权因子, 因为在整个网络中各个ONU的等级不一定相同, 有些要用作专线。

为了公平性, 方针业务量大的ONU长期占据网络资源, 在OLT端对ONU设置的传输窗口, 其最大值为W${}_i^{\text{Μ}\text{A}\text{X}}$, 则最大轮询周期TCmax就是:

${\rm T}{}^{C\text{m}\text{a}\text{x}}={\displaystyle \sum _{i=1}^{n}W}{}_i^{\text{Μ}\text{A}\text{X}}/R{}_U+({\rm N}-1)*t{}_g$

同时, 在OLT端对EF业务的带宽并不是一直固定不变的, 而是通过设定一个查询周期, 这个周期比固定的轮询周期要大的多, 可以是几个过十几个轮询周期。

2 仿真与结果分析

为了能体现改进的算法的性能, 在OPNET下分别对现有的动态带宽分配算法和改进的算法分别作了仿真并对仿真结果作了相关分析。网络模型是由一个OLT、两个ODN以及10个ONU组成。主要仿真参数如下:下行数据链路传输速率RL=1000Mbps, 各个模拟数据源的速率为:RU=100Mbps, 仿真中1∶N光分路器中的N设定为8, 上行数据帧长2ms, ONU上行数据之间的保护时隙tg=5μs, 最大传出窗口W${}_i^{\text{Μ}\text{A}\text{X}}$=15000bytes, 设定所有ONU占用W${}_i^{\text{Μ}\text{A}\text{X}}$进行上传输数据, 网络负载取用户实际得到上行速率Ri与RU的比值。

当有效的网络装载是低时, 所有包的延时很少, 不管ONU装载情况如何。这是改进的带宽分配算法的明显优势:当网络装载是低的, 低优先业务将得到更多带宽, 这就解决了轻负载恶化问题。相反, 在ONU的低负载网络装载量高时, 网络整体延时很高。 导致此现象的原因是网络突发业务。这时, 轮询周期Tcycle将增加, 以便接受大于WMAXi得突发业务量。结果可能导致低等级的业务延时增加甚至超过一个轮询周期。网络负载量小于80%时, 包的丢失率为零或者很小可以忽略, 但是当网络负载量超过90%ONU的负载量超过50%时, 包的丢失率超过50%, 这同样是因为突发业务。此时, 可以适当的调小ONU的W${}_i^{\text{Μ}\text{A}\text{X}}$, 以降低包的丢失率。

从图4-6可以看出, 在轻负载时, 两种算法的平均帧延时非常接近, 但随着负载越来越大, 改进算法的优势就越来越明显, 而且高优先级的优势先开始呈现。图4中EF从网络负载0.3开始, 改进算法的时延开始低于现有动态带宽分配算法, 随着网络负载的越来越重时延差距越来越大, 图5中现有动态带宽分配的AF业务时延从网络负载0.45左右开始逐渐超过改进的算法, 图6是BE业务的时延比较图, 从网络负载0.55左右开始, 两种算法的时延曲线开始分叉, 改进的算法也明显优于现有的动态带宽分配算法。

3 结束语

EPON是解决接入网瓶颈问题的最佳解决方案, 因此动态分配算法就显得尤其重要。文中提出了一种改进的动态带宽分配算法, 首先, 针对现有的MAC机制的问题, 提出了一种改进的机制, 同时, 进行了方针, 从方针结果上看, 有效地保证整个EPON网络的QoS以及带宽分配公平性。在网络负载时, 在没有影响AF、BE业务的前提下, 使得EF业务的延时得到了改善。在网络负载超过50%时, 不论是EF业务, 还是AF、BE业务都有明显的改善。由此可见, 改进算法有效提高了上行信道的带宽利用率, 减小了EF等级业务的时延抖动, 具有较好的时延特性。

参考文献

[1]MCGARRY MP, MAIER M, REISSLEIN M.Ethernet PONs:A Sur-vey of Dynamic Bandwidth Allocation (DBA) Algorithms[J].IEEEOptical Communications, 2004 (8) :8-15.

[2]王亚民, 郭俊娜.一种改进的EPON动态带宽分配算法[J].光通信技术, 2007 (11) .

[3]KRAMER G, MUKHERJEE B, DIXITS, et al.Supporting differenti-ated classes of service in Ethernet passive optical networks[J].Opt.Networks.2002:280-298.

[4]MA M, ZHU Y, CHENG T H.A bandwidth guaranteed pollingMACprotocol for Ethernet passive optical networks[C].San Francis-co//Proc.IEEE INFOCOM, 2003:22-31.

[5]曾清海, 邱昆, 唐明光.一种APON上行带宽分配方案[J].通信学报, 2001, 22:86-91.

动态带宽算法 篇5

关键词：数据网格,数据复制,动态下载,带宽,模型

0 引言

数据网格是网格计算中的一种[1],数据网格管理着存储在许多计算机并扩散在许多站点的大量数据。它的目标是使在不同计算机上的不同用户能共享数据。在网格中,用户可以从本地或其他具有目标文件的计算机上并行下载文件,然而跨越Internet传输大量的数据是非常费时的。2002年,这种单并行下载模型开始提出[2],但当每个用户都使用并行下载时,他们将竞争系统资源,导致效率下降。同样,当更多用户使用并行下载模型时存在一个不公平的问题,各用户为了完成各自的工作,单个下载用户必定存在较长时间的等待。并行下载模型在管理从多个服务器下载的文件上存在一定的额外延时,因此,如果没有足够的控制机制,多服务器并行下载的效率将大打折扣。

1 相关研究

1.1 静态服务器选择模型

在网络中,当客户机找到具有目标文件的很多服务器时,下一步就是选择合适的服务器和大小合适的数据块来下载。本节概述具有一些静态因素(如网格拓扑结构、服务器资源等)的静态服务器选择。

文献[3]首先提出了通过考虑服务器—客户机带宽来选择服务器。如果服务器到客户机具有较低的带宽,那么它具有较低的优先级,选择优先级高的服务器来下载。

文献[4]提出一种为并行下载识别服务器选择的拓扑结构。服务器传输数据到瓶颈链之后,下载速度限制了整个并行传输。即使有许多具有目标文件的服务器,传输速度也受瓶颈带宽的限制。如图1所示。在图1中,假设各服务器的带宽分别是4MB、4MB,5MB,5MB和6MB,如果没有瓶颈链,客户机将具有24MB/S的下载带宽,但如果客户机与服务器之间具有2MB/S的瓶颈带宽,则客户机的下载带宽将减到2MB/S。因此,如果客户机在瓶颈链之后选择太多的服务器,并行下载的流量将由于存在瓶颈链带宽的限制而减弱。

此外,文献[5]提出了一种考虑网络扩缩性和服务器资源的服务器选择方法,通过比较带宽和资源来选择服务器。

静态服务器选择并不可靠,因为网络环境总是变化的。用静态服务器选择实现并行下载非常容易,但只适合于所有服务器都不共享相同瓶颈链和网络环境是固定的情况。

1.2 动态服务器选择模型

动态服务器选择是为适应网络环境和服务器负载的变化而提出的。

1.2.1 Pablo Rodriguez模型[2]

Pablo Rodriguez提出了一种适应性的并行下载方法,它将目标文件分割成较小的数据块,客户机从服务器中下载以数据块作为传输单元。首先,客户机分别从每一个服务器请求下载一个数据块,如果某个服务器完成了一个数据块的下载,客户机再从该服务器请求下载一个尚未下载过的数据块,直到所有的数据块都被下载完全为止。

最小的数据块大小取决于网络环境和系统负载。理论上,划分成的数据块的大小越小,需要处理的块就越多,因此需要更多的并行机制。然而,分块越多也意味着更多的控制信息(包括请求和响应信息)。到目前为止,在并行下载开始时,还没有一种方法来定制最佳的数据块大小。本文将提出一种确定目标文件分块数量上限的机制。

1.2.2 Junchi Funasaka模型[6]

Junchi Funasaka提出了一种方法,首先计算每一个服务器流量来获得历史平均传输速率进而划分数据块,然后客户机据此速率决定下一次向该服务器请求的数据块的大小。例如,有3个服务器,从服务器C请求的数据块大小由,这里A、B、C分别是各自服务器的平均流量,Rest为被下载文件余下的尚未下载的文件大小。如果某一服务器在以往有较大的流量,系统就分配给该服务器较大的数据块。

1.2.3 Chih-Huang Chao模型[7]

Chih——Huang Chao进一步完善了Junchi Funasaka提出的并行下载方法。他把目标文件划分为大小相等的数据块,在同时请求或依次请求时,一个数据块被分配给不同的服务器来下载。假定对服务器的请求顺序都按服务器序号及目标文件分块后的逻辑顺序申请。通过使用多个服务器下载相同的数据块,最快的服务器能首先完成。例如在表1中,每一个数据块被分配给2个服务器。假定只能选择服务器1和4进行下载,且服务器4的速度比服务器1要快,那么数据块3的下载就有可能在服务器1完成数据块2的下载之前完成。因此,当服务器1完成下载数据块2后,它可以跳过下载数据块3。

此外,文献[8]研制了并行下载工具软件,它允许用户控制使用的线程数量、确定传输块的大小、确定多大的内存缓冲区专用于下载的数据块等。当大量的站点同时访问同一服务器的同一目标文件时,由于基础结构的瓶颈,复制时的性能减弱将发生。

2 基于带宽的文件分块动态并行下载模型

为了防止不同的并行下载作业同时相互影响。本文提出了一种考虑服务器输出带宽和客户机输入带宽的文件分块动态并行下载模型,我们将它划分为以下三个阶段。

2.1 初始化阶段

初始化阶段主要是确定服务器的优先级、目标文件的数据块大小以及用到的系统参数等。如表2所示。

(1)选择服务器

客户机通过复制定位服务RLS(Replica Location Service)程序将包含目标文件的服务器列出,假定有N个服务器含有这个目标文件。为了选择服务器,我们根据优先级给服务器排序。首先按下式给每个服务器分配权重:

这里,SWi为服务器i的权值,PTi JWi的含义见表2。如果服务器i与客户机在相同的站点,则PTi=0,PTi可以通过Ping实用程序来估计;服务器的权值越大,它的选择优先级就越低。假设n是目标文件等分后的数据块数,通常n远大于N,因此所有的N个服务器都可被选中以实现并行下载。如果n

(2)确定数据块数量n

为了计算最合适的n值,必须考虑并行下载存在的额外延时,包括内部和外部的额外延时[9]。

●内部额外延时(10)这类额外延时指伴随每个数据块下载发生的额外延时量。如建立或重新建立TCP连接的时间、数据块的排序时间以及数据块重新组合成目标文件的时间。

●外部额外延时(EO)理论上,这类额外延时发生在整个并行下载过程中,它包括初始连接的同步时间、缓冲区准备时间以及建立其他协议的时间等等。

EO和IO的值是动态的,根据所用传输设备和传输介质的不同而不同,使用不同的网格软件获取,EO和IO的值可能不同。如果一个服务器分到m块来下载,它的总额外延时量为:EO+(m-1)×IO。

从一个服务器的下载时间最好等于该服务器的最大带宽。为了防止在最快的服务器上有太多的额外延时。总的额外延时量应小于实际的数据块的传输时间,我们据此计算目标文件被等分后的数据块的数量。假定我们分配的数据块大小适合服务器的带宽,同时设服务器f是最快的服务器(具有最大带宽),那么,分配给服务器f的数据块数为:

式中的Bki、MTi的含义见表2。为了使额外延时量小于数据块传输时间,我们有:

由式(2),可以推算出n的上限。例如,假定有4个服务器A、B、C和D,它们具有的最大带宽分别是:40MB、30MBPS、20MBPS和10MBPS。我们根据它们的最大带宽来分配数据块给服务器。本例中服务器A是最快的服务器,因此根据式(2),有:

化简后,得:

结果表明了数据块数n与目标文件大小F之间的关系。假设EO=3S,IO=1S且F=800MB,算得n≤15。也即,在最快的服务器上,为了保证网格系统的额外延时小于数据块的下载时间,数据块数不能大于15。

2.2 运行阶段

(1)并行下载开始时,选择优先级在前2位的服务器来下载目标文件这两个服务器一边传输数据,一边监测客户机的下载速度。客户机的下载速度受它所用网卡的速度和它所连接的路由器速度的限制,在互联网协议中,通过使用严格的路由选择,设置从客户机到路由器的连接及由路由器返回到客户机的路由通路,可以测到客户机端的最大流量。

(2)根据客户机带宽适时增减参与并行下载的服务器如果下载速度没有达到客户机的最大下载带宽,将增加一个服务器来下载剩下的数据块。如果客户机达到了最大的下载带宽,将不再需要分配服务器来完成并行下载作业。

(3)动态调整服务器下载数据块的数量根据服务器流量,从服务器i中分配BKi个数据块来下载,但当服务器正在下载时,网络环境在不断变化。因此,我们提出动态地改变分配给每一个服务器的数据块数量。通过计算每一个服务器已下载的块数来决定那一个服务器有较好的流量。在客户机未达到最大下载带宽的情况下,我们进一步将目标服务器划分为三种类型,即低速服务器、中速服务器和高速服务器。用hi表示服务器i实际已经传输到客户机的数据块数,假定现在使用K个服务器,那么,如果hi≤(h1+h2+…+hk)/3,则服务器i为低速服务器;如果(h1+h2+…hk)/3≤hi≤(h1+/h2+…+hk)/2,则服务器i为中速服务器;如果hi≥(h1+h2+…+hk)/2,则服务器i为高速服务器。对低速服务器,每次分配1块,对中速服务器,每次分配2块,对高速服务器,每次分配3块。为防止较快服务器变慢并锁定分配给它的块数,在下一次分配之前,服务器类型将再次检测并重新划分。

2.3 结束阶段

(1)监测最后一个数据块的请求和传输结束阶段的主要工作是尽可能地及时确认每一个服务器完成的最后请求,关注最后一块的下载效率。这一工作很重要,如果最后一块传输缓慢或服务器死机,将增加整个并行下载的时间。

(2)高速服务器帮助低速服务器完成最后一块的传输如果一个高速服务器或中速服务器完成了它的最后一块的数据传输,可能还有许多较慢的服务器还在传输各自的最后一块,已经完成的服务器将被随机地分配单一的原先已分配给低速服务器的数据块来并行下载,直到客户端已经全部下载完所有的数据块为止。

3 模拟实验与分析

3.1 网络拓扑结构

在我们的实验中,利用计算机通过互联网建立如图2所示的网络连接来测试这种并行下载模型。主干带宽约为2.488Gbps,交换机和路由器之间采用千兆以太网,带宽约lGbps。

3.2 本模型与静态、动态并行下载模型的比较实验

实验中有3个目标文件,文件大小分别为100MB、500MB和1GB。有9个结点并且每一个结点具有不同的文件组合类型。表3为复制分布情况。在表3中,符号“√”表示该结点上有相应的目标文件,符号“X”表示该结点无此目标文件。有6个作业请求要下载相应的目标文件。例如,网格结点S01、S03、G03和G05(表中的序号为1,3,7,8)都具有供下载的100MB的目标文件,网格结点S01、S05和G03(表中的序号为1,5,7)都具有供下载的500MB的目标文件,网格结点S01、S04、G05和G07(表中的序号为1,4,8,9)都具有供下载的1GB的目标文件;网格结点S02(表中序号为2)有作业1请求下载1GB的文件,网格结点G05(表中序号为8)的作业6请求下载500MB的文件等。

表4表示用于下载的服务器以及文件分块后划分给每个作业下载的数据块数。在表4中,对于静态并行下载,数据块数等于并行下载的服务器数。对于动态并行下载,我们使用的数据块数分别有10、12和15,并且所有的服务器都可能同时被使用。对于本文的模型,首先必须选择两个服务器来初始化下载任务,其他服务器在下载期间随时增加。以作业1为例,作业1的优先级使用式(1)计算,结果如表5所示。

由于MTi(服务器i的最大流量)不能大于该服务器网卡的带宽,假定MT1=MT2=MT3=MT4=MT5=125MB/S,MT6=MT7=MT8=MT9=50MB/S。经我们的网格环境实际测试,此时的EO≈0.6S,IO≈0.5S。

此时,BK1=[125/(125+125+50+50)×n]=0.357n,根据式(2),有:

求得n≤15.8。因此,我们的作业1和作业4最大n为15。通过相似计算,作业2和作业6的n≈7.53,因此最大数据块数n取7,作业3和作业5的n≈1.1,因此最大数据块数n取2(在我们的模型中,块数不能小于2块)。

图3给出各种模型下的实验结果。实验表明,使用10块或15块的动态并行下载的效率小于使用12块的效率。甚至,本文模型的并行下载性能优于其他动态并行下载的性能,同时还发现,较大目标文件具有较好的并行下载性能。

实现中还有两个变量可以影响并行下载的性能。一个是客户机的状态,另一个是网络环境。例如在图3中,作业2和作业4具有相似的参数,然而,作业4获得较好的性能,原因是这2个客户机归属另一个部门,除我们的网格作业之外,它们还担负其他作业的运行并且是在我们的控制之外。同样,服务器之间的连接要通过互联网,互联网环境更为复杂,这两个因素导致不同的性能。

4 小结

4.1 影响动态并行下载效率的三个主要因素

动态并行下载模型的提出是为了提高下载速度,并与其他下载模型的性能相比较。以下三个因素影响并行下载的效率:

(1)目标文件大小如果目标文件太小,并行下载的额外延时相对于下载时间就过于浪费,其结果是较大文件比较小文件具有较好的下载效率。

(2)服务器选择为了避免并行下载过程中过度使用服务器而降低效率,需使用到客户机的最大下载带宽信息。如果客户机的下载速度已经达到它获得的最大带宽,此时不再需要增加服务器。

(3)数据块大小较小的数据块更能适合多变的网络环境,因为它减少了较慢服务器获得较大部份目标文件的机会。但如果数据块太小,将增加较多额外的控制信息而增加下载时间。因此确定并行下载的最佳数据块的大小是很重要的,它直接影响并行下载的效率。

4.2 基于带宽的文件分块动态下载模型的主要步骤

以前的并行下载方法,没有考虑多并行下载过程中彼此的相互影响。为了从服务器中下载,有两个因素限制最大下载速度,一个是服务器输出的带宽以及客户机输入带宽,另一个就是目标文件大小及文件分块的数量。我们提出了一个考虑了机器带宽、目标文件大小和分块数量的动态下载模型。本模型在多并行下载环境中比单个下载提供较好的效率,且在没有降低自身并行下载效率的情况下,避免了服务器的过度使用,本模型实施的主要步骤归结如下:

(1)确定优先级以选择较好的两个或两个以上服务器来下载;

(2)根据需要,服务器一个接一个地加入并行下载,直到客户机达到它的最大下载带宽;

(3)考虑目标文件的大小、内部和外部额外延时以及服务器的能力来计算目标文件的分块数量;

(4)在客户机未达到最大下载带宽的情况下,根据以往的下载数据将服务器分为三种类型的队列,即低速服务器队列、中速服务器队列和高速服务器队列,据此选择服务器并动态确定分配多少个数据块给该服务器来下载;

(5)及时监测最后剩余数据块的传输速度,必要时分派高速服务器并行下载最后剩余块,以避免传输过程中无限循环等待或饥饿状态的发生。

参考文献

[1]Ian Foster,Carl Kesselman,Steven Tuecke.The anatomy of the grid: Enabling scalable virtual organization[C]//Proceedings of the International Journal of Supercomputer Application,2001,15(3):200-222.

[2]Pablo Rodriguez,Ernst W Biersack.Dynamic Parallel access to replicated content in the internet[C]//IEEE/ACM Transactions on Networking, 2002,10(4):445-465.

[3]Sandra G,Dykes,Kay A Robbins,Cliton L Jeffery.An empirical evaluation of client-side server selection algorithms[C]//Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies,2000(3):1361-1370.

[4]Yoshinori Higashi,Shingo Ata,Chikato Fujiwara.Topology-aware the Consumer Communications and Networking Conference(CCNC)[C]. January,2005:235-300.

[5]Zhou Xu,Lu Xianliang,Hou mengshu,et al.A speed-based adaptive dynamic parallel downloading technique[C]//Proceedings of ACM Special Interest Group Operating System Review,2005,39(1):63- 69.

[6]Junchi Funasaka,Nozomi Nakawaki.A parallel download method of coping with variable bandwidth[C]//Proceedings of the 23rd International Conference on Distributed Computing System Workshops,May,2003:14 -19.

[7]Chih Hung Chao,Jung Shian Li.A novel BiB-based parallel download scheme[C]//Proceeding of the Asia-Pacific Conference on Circuits and System,December,2004:461-464.

[8]Scott Atchley,Stephen Soltesz,James S Plank,et al.Video IBPster[J]. Future Generation Computer Systems,2003,19(6):861-870.

动态带宽算法 篇6

随着Internet日益成为未来全球统一的通信平台, 需要支持大量的实时多媒体应用, 如话音、交互视频、在线游戏等, 对网络带宽要求日益增高, 数据流量逐渐变大, 同时大量的P2P业务的流量吞噬有限的带宽, 很大程度上加重了网络拥塞, 妨碍了相关的网络业务的开展和关键应用的普及, 因此必须配置相应的网络QoS保证一些重要的, 交互性的且具有商业价值的数据流 (如VOIP, e-business, ERP) 稳定的通过网关, 不至于被FTP或P2P流量阻塞。现今运营商IP网络的QoS部署主要基于区分服务 (DiffServ) 模型, 基本原理是将网络中的流量分成多个类, 每个类接受不同的处理, 尤其是网络出现拥塞时不同的类会享受不同的优先处理, 从而得到不同的丢弃率、时延以及时延抖动。流量监管则是IP QoS机制中一项非常重要的功能, 主要用来管理用户注入的流量, 使其完全匹配设定的流量参数。而令牌桶算法作为一种实现方法, 已被一些国际标准组织采纳。

在标准化文件里, 令牌桶算法只是应用在单独类型的流量上, 对于多个类型的流量使用却很少涉及。通常, 需要为每个类型的流量设置一个独立的令牌桶来进行流量整形, 这样比较容易实施但不是很合理。首先, 我们假定网络边界接点 (接入侧) 设置了令牌桶算法来实现流量监管, 且所有的不符合的分组都可能被丢弃, 在此情况下提出一种关联令牌桶来处理多个类型的流量, 使用户定制的带宽能充分地被利用。例如, 一个用户可能为其两个类型的流量A和B定制了相对应的带w1和w2, 假设类型A比类型B具有更高的QoS要求。因此, 对于同等量的数据, 类型A将比类型B要求获得更多的带宽来发送数据。从用户的角度来说, 他会十分愿意使用类型A的空闲带宽传送类型B的数据流, 反之亦然, 而这是使用独立工作的令牌桶无法完成的工作。

2 研究相关内容介绍

2.1 区分服务 (DiffServ)

区分服务的基本思想是将用户的数据流按照服务质量要求来划分等级, 任何用户的数据流都可以自由进入网络, 但是当网络出现拥塞时, 级别高的数据流在排队和占用资源时比级别低的数据流有更高的优先权。区分服务只承诺相对的服务质量, 而不对任何用户承诺具体的服务质量指标。这是一种基于类的QoS技术, 现今主要应用于骨干网。

在区分服务机制下, 用户和网络管理部门之间需要预先商定服务等级合约 (SLA) , 根据SLA, 用户的数据流被赋予一个特定的优先等级, 当数据流通过网络时, 路由器会采用相应的方式来处理流内的分组。

区分服务的不足之处是不能绝对保证质量, 且服务质量提供也不是端到端的, 而是限于一个区分服务域。但是, 区分服务能够很好地与IP网络相适应, 其只包含有限数量的业务级别, 状态信息的数量少, 因此可扩展性、实现的简单性、可操作性和部署能力使得区分服务逐渐成为目前主流的IP QoS体系结构。

2.2 令牌桶概念

令牌桶算法是目前IP QoS中最常采用的一种流量测量方法, 广泛应用于约定访问速率技术、通用流量整形技术以及物理接口总速率限制等技术中。令牌桶是一种特殊应用的网络设备内部存储池, 令牌则是以给定速率填充令牌桶的虚拟信息包, 每个令牌对应一个分组包或一定量的比特数。令牌桶的基本处理过程可以描述为 (图1) :当数据流到来时, 如果令牌桶中有足够的令牌可用于发送数据, 则数据可以通过;令牌桶中的令牌数量随着数据的通过而逐渐地减少, 当令牌桶中的令牌不再满足数据的发送条件时, 则发送的数据要么丢弃或者再标记这个数据包 (流量控制) , 要么等待令牌桶中有足够的令牌 (流量整形) ;当令牌桶内令牌已经满了, 则产生的令牌将被丢弃。

令牌桶的重要参数决定了令牌桶的性能和功能, 不同的应用有不同的参数值。令牌桶容量σ:决定了桶中可放置的最大令牌数, 也是瞬时可用的最大令牌数。令牌产生速率ρ:令牌进入令牌桶的设定速率, 主要决定了数据通过的平均速率。令牌数x:令牌桶中现存的可用令牌数量。我们这里使用参数 (σ, ρ) 来定义一个令牌桶的特性, 在下面介绍关联令牌桶时会做具体探讨。

3 关联令牌桶的研究

我们已经介绍了令牌桶处理单个类型的流量的流程, 在本章中将对关联令牌处理多个类型的流量进行着重研究。如果系统中存在n种类型的流量, 依据区分服务模型的基本思想, 一般需要有n个令牌桶来整形n个队列, 就像前面提到的, 每一个独立工作的令牌桶仅处理一种类型的流量, 各种类型的流量所获得的带宽无法超过预先配置的带宽, 即使有剩余带宽也不能被利用, 从而造成带宽资源的浪费。这种情况也许不是用户愿意看到的, 因为用户接入端可能设置了多种类型的队列 (图2) , 高级别类型流量的带宽可能暂时没有被充分利用, 但为了给各个流量类型提供带宽保证, 在低级别类型流量的带宽被完全占用情况下, 系统也无法使用剩余的带宽来发送低级别类型的数据流。假定配置了两种类型的流量, 类型1比类型2具有更高的优先级, 相对应其各自类型的令牌桶参数。一个理论上可实施的方法是使用来管理类型2的流量, 同时再使用对类型1与2总流量进行管理。依此类推, 当有n种类型的流量时, 即需要设置n个令牌桶, 则第j桶 (1≤j≤n) 参数可以管理前j种类型的总流量。实际上, 关联令牌桶的设计就以上述理论为基础, 能够保证较高级别类型流量的带宽使用, 在数据突发的情况下也可以获取低级别的闲置带宽, 以提高单位带宽的使用价值。

关联令牌桶是由n个令牌生成器, n个令牌桶及一个令牌放置模块组成的, 其中最关键是令牌放置模块的设计, 它会依据系统配置来决定一个新产生的令牌放置到哪个令牌桶里, 通过令牌的选择性放置来实现带宽的借用 (如图3) 。

假定类型i的令牌生成器TBGi以速率ρ1产生令牌ti, 此时令牌桶i已存有的令牌数量为xi;类型j是优先级大于类型i的流量, 类型l是优先级小于类型i的流量, 类型k是借用令牌的流量, 每种类型的流量对应唯一的队列;这里还需要引入新的参数Si与Li来为每种类型标记, 两个参数都是在令牌放置模块内设置, Si是令牌借用参数, 初始值Si=0;Li是类型i借用的令牌阈值, n种类型可以有不同的阈值;利用Si与Li两个参数可以限制某一个级别的流量对闲置带宽的长时间占用, Li初始值小于零。

如图4所示, 基于优先级的令牌桶放置模块的调度策略:

(1) 当TBGi (第i个令牌生成器) 生成一个新的令牌ti, 如果对应的令牌桶i不满, 就把令牌放置进桶内, 调度终止;

(2) 令牌桶i已经满了, 对所有j (j为优先级大于i的类型) 的令牌桶进行扫描, 找出所有xj=0 (令牌个数为零) 或缓存队列非空的令牌桶, 如果存在这样的令牌桶, 转至4;

(3) 找出所有0

(4) 从中筛选出一个令牌桶k (iLj (满足借用条件) 且类型优先级最高的, 将令牌ti放置进k (相对优先级最高的类型) 的令牌桶中, 修改参数Sk=Sk-1与Si=Si+1, 调度终止, 否则转至3;

(5) 所有j类型不符合借用令牌条件, 重 (2) - (4) 中的流程, 但要把所有j下标的参数改为l下标 (优先级小于i的所有流量类型) , 即对所有优先级小于i的令牌桶做选择, 将令牌ti借用给令牌桶k (1

通常情况下, 这个“溢出”的令牌经过令牌放置模块管理后, 会被放入“合适”的令牌桶内。在这个调度策略里, 参数Li决定了一种类型的借用极限, 而类型i从某个时刻起可以持续借用的令牌数等于Si-Li, 是这种类型借用闲置带宽来持续发送数据的总量;参数Li一般会设置为固定值, Si的动态数值起决定作用, 它的值域范围[Li, +∞) 。

因此, 可以为P2P类型的流量设置一个绝对值较小的借用阈值, 使它能够在繁忙时借用到一定的空闲带宽来传送数据, 又可以限定它的借用总量。当借用参数SP2P等于Lp2p时, P2P类型的流量就不能再获得“溢出”的令牌, 令牌将被放置到其他符合条件的令牌桶里, 让空闲带宽可以轮换给其他类型的数据流利用。相对的, 一些高优先级且保证突发的类型, 可以设置Li=-∞, 即没有令牌借用限制, 能不被限制地借用空闲带宽。如果类型i的令牌桶满了, 产生的令牌ti借给了其他类型, 则借用参数Si=Si+1, 作为借出令牌的类型i也就得到了一个“补偿承诺”, 即在条件允许下可以持续借用到更多的令牌。

4 小结

随着网络业务的转型, 传统的通信业务正向信息娱乐, 数字化生活领域扩展, IPTV, VoIP以及P2P应用业务种类的不断丰富, 就需要严格控制业务对资源的使用, 从而避免业务对资源的争夺, 保障网络资源的合理使用, 制定合理的QoS方案就成为最基本的要求。本文中提出的基于令牌桶的流量监管策略还是比较合理的, 可以有效的调度带宽的分配, 即考虑到用户对各类型数据传输的基本带宽要求, 又可以灵活的配置闲置带宽, 保证用户所定制的带宽能得到充分利用。该策略研究尚存在一些有待改进的地方, 可以对类型的优先级与Si间关系进行考虑, 以便使算法易于实现且整体性更好。

参考文献

[1]D.Nandita, J.Kuri, and H.S.Jamadagni.Optimal call admission control in generalized processor sharing (GPS) schedulers, IEEE Infocom, 2001, 4

[2]E.P.Rathgeb.Modeling and performance comparison of policing mechanisms for ATM networks, IEEE J.Sel.Areas Commun, 1991, 9 (3) :325～334

[3]Traffic management specification, version4.0, ATM Forum/95-0013R8, 1995, 10

[4]杨勇, 王雪晶, 陈良臣.QoS在IP中的研究和应用.计算机技术与发展, 2007, 17 (5)

[5]刘伟, 鱼滨.基于QoS的动态服务组合研究.计算机技术与发展, 2007, 17 (5)

[6]陈彪.支持链路共享的流量整形器.浙江大学学报 (工学版) , 2005, 39 (8)

[7]孙鹏, 韩正之.一种基于控制理论的网络流量控制策略.通信技术, 2003, (3)

动态带宽算法 篇7

IntServ网络中采用资源预留的方式来保证业务的QoS的同时,其可扩展性受到了严重的限制。而DiffServ因其良好的可扩展性得到了广泛的关注。DiffServ网络中的路由器可以分为两类:边缘路由器和核心路由器。边缘路由器负责将所有到来的网络流量根据其不同的服务需求分为三个聚集类,即为EF(Expedited Forwarding,加速转发)、AF(Assured Forwarding,确保转发)和BE(Best Effort,尽力而为)。其中AF中包括AF1-AF4四个子类。核心路由器负责对流量负载以聚集类中聚集流的形式进行调度。

从而我们可以知道,聚集类中的流量负载是随时间动态变化的。然而传统的调度算法(如WFQ)总是以一种固定不变的方式进行带宽分配,无论聚集类中的流量负载如何变化,每个聚集类分得的带宽总是固定不变的。在这种情况下,必然会导致一些不公平的现象发生。

为了改变这种情况,在进行带宽分配时能够做到按需分配,并对各项业务能够提供相对公平的服务,动态带宽分配引起了广泛的关注[3,4,5,6,7,8]。

该方面的研究大体可以分为两类。第一类在进行带宽分配主要考虑了流量自身的特性,如聚集类中流的数量。文本[3,4,6]中采用了不同的方法估计聚集类中流的数量,并据此做动态带宽分配,我们称此类方法为基于流数量的方法。第二类[5,7,8]首先研究业务的QoS与其得到的带宽之间的关系(用效用函数来表示),再做带宽分配。在上述基于流数量的方法中只考虑了流的因素,而只有当所有流的发送速率都一致时,该方法才能够达到公平,否则也将是不公平的。因此,在带宽分配中,包的因素也是非常值得考虑的。从下面的例子中我们可以看到这一点。

例1:如图1中所示,LinkR2-R3的链路带宽为3Mib/s,AF1和AF2中各有两条流,流的到达速率分别为2Mbps和1Mbps,那么AF1和AF2中的流量负载分别为4Mbit/s和2Mbit/s。假设AF1比AF2的优先级高,也就是说AF1中的流应该得到比AF2中的流等级高的服务。为了保证这一点,在分配带宽时可以将AF1和AF2的权重分别设为1.5和1.0。AF1和AF2分得的带宽分别为1.8Mbit/s和1.2Mbit/s。经过时间间隔t,二者在队列中等待的包的总大小,也就是队列长度,将分别增加2.2Mbit/s*t和0.8Mbit/s*t。如果每个聚集类的缓存大小相同,AF1的缓存会更早用尽,也就是说,AF1中会更早发生丢包,AF1中的流也就不可能得到比AF2更好的服务。这就造成了带宽分配的不公平性。

为了解决这个问题,本文中提出了一种新的动态带宽分配方法。与基于流数量的方法不同的是,我们综合考虑聚集类中包的因素作为流量负载来进行动态带宽分配。

本文中余下部分的安排如下。第1部分中介绍了相关的研究现状。第2部分详细介绍了本文提出的动态带宽分配方法,具体的仿真实验及性能分析在第3部分中给出。最后在第4部分对全文做了简要总结。

1 研究现状

DiffServ网络中的动态带宽分配已经得到了广泛的研究。文献[9]分析了DiffServ网络中的带宽保障情况,并得出五个因素(流量负载特征)能够对业务得到的吞吐量产生影响。现有的动态带宽分配方法主要是基于这些因素的来进行的。表1中给出了涉及到的因素及其相关文献的情况。

Huang等[3]通过测量所有连接中所有数据包的到达速率,估计每个聚集类中流的数量,并进而进行动态带宽分配。在流数量估计过程中,Maki等[10]采用了zombie list[11]的方法,而J.S. Li和C.S. Mao[4]是借助于bloom filter[2]进行实现的。

除了流的数量,数据包的大小和目标速率也是考虑的重要因素。Park等[13]提出了用目标速率来作为权重进行带宽分配。Minagawa等[10]采用目标速率作为带宽分配时的权重,同时数据包的大小作为参数进行动态调整。

Shimonishi等[6]借用了[10]中zombie list的思想,估计目标速率和流的数量。当网络拥塞时,根据聚集类中目标速率之和进行动态带宽分配;当网络状况良好、有剩余带宽时,则将一部分带宽根据目标速率进行分配,余下的部分根据流的数量来分配。

在文献[3,4,10]中认为公平是公平的资源(如带宽),即同等优先级的聚集类中的每条流分配相等的带宽,高优先级聚集类中的流要比低优先级聚集类中的流得到更多的带宽。而在文献[6,13,14]认为公平是公平的服务等级(如丢包率),即同优先级的聚集类中的流得到服务等级相同,不同优先级的聚集类得到有区别的服务等级。例1已经清楚地说明,服务等级与流量负载存在不可忽视的关系。因此,本文中我们认同[6,13,14]中对公平的定义,充分考虑每个聚集类中的流量负载情况,进行动态带宽分配。

2 基于流量负载的动态带宽分配

本文提出了一种在DiffServ网络中基于流量负载的动态带宽分配方法。下面我们将从流量负载估计和带宽分配两个部分,分别给出具体的操作过程。

2.1 流量负载估计

在本文中,流量负载指的是在一个特定时间间隔(如1秒)内到达链路的所有数据包大小的总和。在此我们将其分为两部分,一部分为一到达便立即被发送出去的数据包,另一部分为没能够被立即发送出去,在队列中等待发送的数据包。前一部分可以认为是当前分得的带宽,后一部分则是在这段时间间隔内队列长度的增加部分,我们称之为队列增量。

假设现有N个聚集类,分别用AFi表示,i∈[1,N],N∈[1,4]。这些聚集类中的流量负载用LAFi表示,分配的带宽表示为BAFi。所有分配的带宽之和应为一个常数,即链路带宽LINKR2-R3。要注意的是,当流量负载总和小于链路带宽时,所有数据包无需等待均能以其到达速率发送出去,也就不存在带宽分配的问题。因此,在此流量负载LAFi之和应该不小于链路带宽LINKR2-R3,而给每个聚集类分配的带宽BAFi应不大于其相应的流量负载LAFi。在经过一个时间间隔t后,每个聚集类的队列增量就是其中的流量负载减去分得的带宽,即LAFi-BAFi。

AFi当前分得的带宽占总带宽的比例可以用公式(1)计算得到。

undefined (1)

同时,从公式(2)中可以得到AFi的队列增量占总队列增量的比例。

undefined (2)

根据成比例定理(1),如果BPAFi=QAFi=a,那么undefined,这样的话,我们就得到了要估计的流量负载。然而在实际计算中小数点后面可能出现很多位的问题,BPAFi的计算结果有可能不和理论中那样与QAFi绝对相等。因此,在比较过程中我们设定了一个小数δ作为置信区间,即若这两个值之差比δ小,我们就认为二者是相等的,否则就认为它们不相等,也就需要进一步通过下面公式来计算和估计流量负载。

LεAFi=BPAFi+QAFi (3)

undefined (4)

其中LεPAFi表示估计得到的AFi的流量负载在总流量负载中所占的比例。

2.2 动态带宽分配

根据估计得到的流量负载比例LεPAFi,我们可以进行动态带宽分配,具体的操作过程如算法1。

Require: 当前带宽在总带宽中所占比例BPAFi;

实时得到的队列增量在总增量中所占比例QAFi.

Ensure: 新分配的带宽BNAFi.

初始化:

定义初始化分配的带宽在总带宽中所占比例BPAFi;

定义AFi的权重参数αAFi;

定义时间间隔t;

δ⇐0.01;

Time⇐0;

While now.time == Time+t do

if ︳BPAFi-QAFi︳>δ then

根据公式(3)和(4)估计LεAFi;

根据(5)和(6)计算BPNAFi和BNAFi;

BPAFi⇐BPNAFi

Timenow.time.

end if

end While

带宽分配中综合考虑了流量负载和权重参数两方面的因素。从公式(5)中,我们可以得到动态带宽分配过程中聚集类分得的带宽占总带宽的比例。

BPNAFi=LεAFi·aAFi (5)

其中aAFi表示AFi的权重参数。

在带宽分配中设置权重参数时,如果AFi比AFi的优先级高,就会将aAFi设得比aAFi大一些。反之亦然。如果AFi和AFi的优先级相同,则aAFi将与aAFi相同。

最后,每个聚集类分得的带宽大小将由公式(6)计算得到,其中BNAFi将替换BAFi作为当前带宽,用于下一个时间间隔的带宽分配过程。

undefined (6)

至此,我们已经完成了一个时间间隔的带宽分配过程。如前面所说,网络流量是随时间动态变化的。因此,在一个时间间隔t之后,我们要回到最前面,重新估计流量负载,再次进行带宽分配。如此循环往复,才能形成根据流量负载的动态变化而不断的进行动态带宽分配的过程。

需要注意的是,时间间隔t也不是随便设置的。如果t设的太小,某些聚集类的队列长度还没有发生变化,而其他聚集类的队列长度却已发生变化,这样在计算过程中得到的新带宽的动态波动会非常大,很难反映流量变化的真实情况。而如果t设的太大,所有的队列长度都会发生较大变化,带宽分配的结果一定会很精确,但是太长的反应时间就很难体现出动态带宽分配的实时性了。

3 实验结果

在这部分我们将通过仿真实验来验证以上方法的有效性,主要从两方面来进行验证。首先对估计得到的流量负载与实际流量负载做比较,验证估算过程的准确性。然后从带宽分配后各个聚集类的QoS性能指标,即吞吐量、时延和丢包率三个方面分别验证本文提出的动态带宽分配方法的有效程度。

3.1 准确性验证

在以上的计算过程中,我们用LεPAFi来估计真实的流量负载比例LPAFi。在此,我们需要对估计过程的准确性进行验证。

在2.1部分中,每个聚集类中的流量负载被定义为LAFi,那么真实的流量负载比例LPAFi可以由公式(7)得到,而估计的流量负载比例已经在公式(4)中得到。

undefined (7)

为了简单起见,在实验过程中我们只用到了两个聚集类,即AF1和AF2。如果要计算它们的真实流量负载比例与估计流量负载比例,那么在已经得到了AF1和AF2各自真实的流量负载LAF1和LAF2以及估计的流量负载LεAF1和LεAF2时,还需分别计算3次才能得到相应的比例。而如果计算AF1与AF2之比,即LAF1/LAF2和LεAF1和LεAF2,只需分别计算1次便能够得到实验结果,大大减少了计算量。因此,在此我们计算并比较两个聚集类的流量负载之比进行准确性验证。

undefined (8)

undefined (9)

有关估计的流量负载比例的准确性验证的实验过程:①随机变量:LAF1,LAF2,BAF1和BAF2;②服从条件:BAF1

for (i=0; i<100; i++)

{随机生成LAF1,LAF2,BAF1和BAF2;

计算LAF1/LAF2和LεAF1/LεAF2的值;

在图中画出并进行比较上述计算结果.}

图2即为通过上面的实验过程得到的结果,体现了估计流量负载比例与真实的流量负载比例的接近程度。为了不失一般性,该实验过程重复了100次。从实验结果图中可以看到,LAF1/LAF2与LεAF1/LεAF2非常接近。就此可以说明,估计过程具有较高的准确性。

3.2 吞吐量、时延和丢包率

这部分我们将分别从吞吐量、时延、丢包率三个方面,通过与基于流数量的方法比较,检验本文提出的方法的性能。

3.2.1 实验部分

仿真实验中我们采用了图1作为网络拓扑图,其中R2和R3之间的链路为瓶颈链路,链路容量为2Mbit/s。从节点A到节点C的流量标记为AF1,从节点B到节点D的流量标记为AF2。

实验过程在两种条件下分别进行。第一种条件为同等条件,认为AF1和AF2具有同等优先级且应该得到相同服务,那么他们的权重参数也应该是相等的。第二种条件为区分条件,认为AF1比AF2的优先级高,此时AF1的权重参数应该比AF2的大,在实验中我们可以将他们的权重参数分别设为2和1。

仿真过程我们是用NS2实现的。在带宽分配中,我们采用WFQ作为基本的调度算法。为了模拟聚集类中流量负载的动态变化,我们定义了3个UDP流,分别为A、B和C,发送速率分别为0.5Mbit/s、1.0Mbit/s和1.5Mbit/s。表2中为聚集类中流量负载随时间动态变化的情况。另外,赋予BAF1/BAF2的初始值为1.5,则分配给AF1和AF2的初始带宽分别为1.2Mbit/s和0.8Mbit/s。

3.2.2 实验结果

我们将从吞吐量、时延和丢包率三个方面对实验结果进行比较。比较过程分为两种情况,首先是在平等条件下比较本文中提出的方法与基于流数量的方法,其次是对本于文提出的方法比较其在平等条件下和区分条件下的性能。

实验结果中,AF1-new和AF2-new表示在平等条件下,采用本文提出的方法AF1和AF2得到的实验结果,而AF1-old和AF2-old则表示同等条件下采用基于流数量的方法的实验结果。AF1-diff和AF2-diff表示在区分条件下,采用本文提出的方法得到的实验结果。

(1)吞吐量比较:

图3为对吞吐量进行比较的实验结果,从图中可以看到,与前面设置的一致,AF1和AF2的初始吞吐量皆分别为1.2Mbit/s和0.8Mbit/s。

从图3(a)中可以看到,基于流数量的方法的吞吐量走势与FℓσwAF1/FℓσwAF2一致。而本文提出的方法则基本上是随着流量负载动态变化的。

如图3(b)所示,由于在动态带宽分配过程中皆采用了基于流量负载的动态带宽分配方法,因此无论在同等条件还是在区分条件下,得到的实验结果都是随着流量负载动态变化的,且因为设置的权重参数的不同,得出的两组曲线是相互平行的。而区分条件下AF1和AF2之间的差距比同等条件下大得多,正是权重参数发挥的作用。

(2)时延比较:

图4为时延比较的结果。如图4(a)所示,基于流数量的方法中不考虑流量负载,只要AF1中的流数量比AF2中的多,AF1得到的带宽也就永远比AF2得到的多,AF2中的时延也就永远比AF1中的大。然而,采用本文提出的方法所得到的时延是随着流量负载动态变化的。另外,从整体情况看来,在同等条件下,本文提出的方法得到的两个聚集类之间的时延差距比起基于流的方法来说较小一些。

从图4(b)中可以看出,AF1和AF2的时延值基本与分配的带宽之比成反比,即AF1分得带宽所占的比例越大,其得到的时延越小,与AF2的时延差距也越大。

(3)丢包率比较:

表3中给出了仿真实验得到的丢包率情况。在同等条件下采用本文提出的方法时,得到的AF1和AF2的丢包率基本相同,而采用基于流数量的方法时,得到的丢包率之间存在很大差距。在区分条件下采用本文提出的方法时,能够得到很好的区分服务,即AF1能够得到比AF2低的丢包率。由此可以很好的说明本文提出方法的有效性。

4 结束语

为了提高DiffServ网络中聚集类之间的公平性,本文提出了一种基于流量负载的动态带宽分配方法。与以往的基于流数量的带宽分配方法不同,该方法中将每个聚集类中所有数据包的大小总和作为流量负载。在动态带宽分配的过程中,每个聚集类当前分配的带宽占总带宽的比例和队列增量占所有队列增量的比例之和用于计算应该分配的带宽占总带宽的比例。

在仿真实验中,准确性验证部分说明了估计结果与真实值的接近程度,业务的QoS性能指标(包括吞吐量、时延以及丢包率)的实验结果则说明了该方法在提高公平程度上的有效性。

摘要：在DiffServ网络中,流量以聚集类的形式存在,聚集类中的流量负载是随时间不断地发生动态变化的。当不同聚集类中的流量负载与调度算法(如WFQ)为其分配的资源(如带宽)不成比例时,即使两个聚集类的优先级相同,它们中的数据包也会得到不公平的待遇。为此,DiffServ网络中面向公平的动态带宽分配引起了广泛的研究。本文中为了实现公平的带宽分配,提出了一种基于流量负载的动态带宽分配的方法,其中在动态计算各个聚集类应分得的新带宽时主要考虑了当前分得的带宽和聚集类的队列长度增量这两个因素。仿真实验结果说明了该方法的有效性。