WFQ的平均带宽分配模型

文摘

提出了一种新的迭代法计算的平均带宽分配流量使用WFQ调度器在基于IP的NGN网络。带宽分配的计算是基于链接速度,分配权重,到达率和平均分组长度或输入的交通流量。我们证明了模型的结果与使用NS2模拟器实例和仿真结果。

1。介绍

目前的趋势在电信基础设施与面向数据包的网络提出的问题支持的服务质量(QoS)。方法,能够将优先分配给流或数据包,然后根据不同的服务需要在网络节点,提出了QoS要求的支持。队列调度纪律(QSD)算法负责选择包输出队列。他们是为了把输出能力比较和优化。算法能够做出这个决定根据优先级是现代QoS支持网络的基本组成部分(1]。

这些算法的最优配置,我们需要计算或模拟的结果,我们对QoS设置期望的影响。网络节点可以使用马尔可夫链的建模模型(2]。

大多数现有的WFQ带宽分配模型不考虑变量利用队列或带宽分配未赋值的链接能力。因为这个原因我们提出迭代WFQ带宽分配的数学模型。模型可以用于分析的影响权重设置,分析系统的稳定性和建模的延迟和交通类的队列长度。

下一小节将论文的结构如下。起初,WFQ算法紧随其后的是一个简短的陈述共同使用的带宽约束模型。论文的第三部分描述了该模型的平均带宽分配WFQ WFQ带宽分配的例子和仿真结果证明了提出的模型。

2。带宽分配

有很多的调度算法和一些带宽分配模型提出了带宽分配的评估。我们专注于WFQ和带宽分配模型提出了MPLS流量工程。

2.1。加权公平排队

WFQ Demers等人在1989年被引入,张3,4]。该算法根据分配的权重提供公平的输出带宽共享。决定哪些包应该从数据包队列读取和发送是通过计算一个虚拟的完成时间。调度程序完成时间分配到每个数据包到达队列。时间与时间,发送的数据包会完全一点一点地从每个队列的通用处理器共享(GPS)算法。在一个回合中计算对应的比特数分配权重。最小完成时间的包是选择输出。WFQ保证每个交通类获得部分输出带宽和股份比例分配权重。

2.2。带宽约束模型

DiffServ或MPLS流量工程的目标之一是为不同的服务保证带宽预订类。对这些目标定义两个函数(5]:(我)类类型(CT)是一组交通流,基于QoS的设置,共享相同的带宽预订;(2)带宽约束(BC)的一部分输出带宽,CT可以使用。

bc之间的映射和CTs的最大分配模型(MAM)、马克斯分配有保留地(MAR)和俄罗斯娃娃模型(RDM)定义。

最大的分配模型
老妈模型(6]地图一个公元前一个CT。整个带宽是严格划分和CTs之间没有共享是被允许的。

马克斯分配与预订
3月(7是类似于一个老妈最大的带宽分配给每个CT。然而,通过使用带宽保留和保护机制,CTs可以超过他们的带宽分配的条件下没有拥挤但回到他们的分配带宽过载和拥塞发生时(6]。

俄罗斯娃娃模型
RDM模型更有效带宽共享。它分配BCs CTs组。例如CT7最高的都有自己的BC7 QoS要求。较低的CT6 QoS要求股票与CT7 BC6,等等。在极端情况下,低优先级得到他们需要更少的带宽,甚至饿死(8]。

3所示。WFQ带宽分配模型

一般来说,WFQ WRR,和一些其他的调度算法到WF²Q +等等分配带宽的不同部分中描述的模型2.2。服务类之间的可用带宽划分或等待队列根据分配权重。未使用的共享带宽允许又分为其他队列根据分配权重。

提出的模型是一个研究的一部分造型NGN网络的流量参数,修改一个WRR算法,提出模型的带宽分配到,将进一步用于延迟和队列长度建模的算法。

3.1。定义和符号

我们假设一个网络节点优先级类或等待队列。每个队列有一个重量分配。数据包进入队列的到达率和平均数据包大小。这两个变量的乘积表示的输入带宽优先级: 总的可用输出带宽将优先类之间和他们每个人将得到什么。

带宽计算的迭代方法将被使用。的th的迭代会注意到。

3.2。模型的建议

描述WFQ的带宽分配,我们必须分析所有可能会发生的情况。我们将使用一个迭代的方法分析。

让我们看一下可能的情况下,可以出现在第一步的带宽分配。WFQ算法工作原理,所代表的重量值的比特数立即被发送到一个虚拟的输出。位然后重组原始数据包的包是完全以这种方式传播作为第一列中移除。这保证恰当队列之间带宽分配根据分配权重。可用带宽的分配可以写成:

带宽分为队列后根据(2),有三个可能的情况。(我)第一种可能性是,每个队列获取和使用带宽计算(2)。没有额外的共享未使用的带宽将会发生。这将发生 (2)第二个选择是每个队列满意分配的带宽。在这种情况下:

在这两种情况下,带宽分配是在第一个迭代完成的步骤。没有其他未使用的带宽需要分为队列。一个队列的带宽需要(1)或带宽的比例根据WFQ规则(2):

这个(5)也代表了我们的第一次迭代步骤。

如果条件(3)或(4)没有得到满足,我们必须在下一次迭代计算带宽分配步骤。这意味着一些队列需要更多的带宽比被分配使用(2),一些人只使用带宽计算(1),其余的带宽是未使用的和可以共享。我们将重新分配之间的未使用的带宽只有队列的需求并不满意。队列,不需要更多的带宽可以确定如下:

如果队列满足带宽需求,的结果(6)将是零。另一方面一个正数表明队列需要更多的带宽。这将帮助我们确定队列与带宽足够的带宽或短缺。

重新分配的未使用的容量只做队列之间的带宽要求不满意,直到所有能力划分或所有队列的需求,可以见面在最坏的情况下的步骤。可以编写下一个迭代的步骤如下:

方程(7)将用于所有其他的迭代计算来。计算后必须停止队列的所有带宽需求得到满足,否则它会导致除零。计算的终止条件如下。(我)整个输出队列之间的带宽已经分布: (2)或所有队列的需求得到满足:

这些条件也满足如果在下一次迭代中没有发生再分配的带宽:

4所示。分析不同行为的变异

让我们证明我们的模型的性能比较与WFQ一些例子。在这些例子中,我们将假定4优先类。我们将展示4不同的行为。第一个例子介绍了情况,所有交通类得到所需的带宽。第二个显示了瓶颈链路的情况下需要有能力比和分布是根据包的大小和重量。第三个例子向我们展示了发生最坏的情况下重新分配的带宽和计算带宽迭代。最后一个例子演示了也重新分配带宽,但不到后的重新分配过程将停止迭代。

例1。在这个示例中,我们将假定一个100 Mbps的输出链接。第一个类代表一个VoIP流高流量。平均数据包大小设置为100 B等于什么。数据包进入系统意味着国米包间隔10 ms,代表的到达率。第二个类代表一个视频会议和。第三类代表相同的视频参数。最后第四类传输数据与最低优先级设置。交通参数和。
输入带宽计算使用(1),,,。
权重设置在以下方式:,,,。带宽分配队列根据(2)是40 Mbps, 30 Mbps, 20 Mbps,和10 Mbps,这比所有的队列。在这种情况下,迭代停止后的第一步(5)和带宽使用的队列的低价值这个方程。我们停止迭代中定义的条件(9)。

例2。下面的例子使用了交通设置示例相同1。唯一的区别是,设置为50 kbps输出链接能力。
带宽分配计算(2)是20 kbps, 15 kbps, 10 kbps, 5 kbps。这代表了整个50 kbps输出能力。交通类都没有足够的能力重新分配和带宽分配是在第一个迭代完成的。

例3。在这个示例中,我们将展示最坏情况下的带宽分配最大后停止步骤。我们将使用相同的数据包大小在所有队列。权重再次设置如下:,,,。有不同的到达率设置修改所需的带宽和现在的重新分配。将到达率,,,。输出链接容量设置为10 Mbps。
这个设置结果为以下带宽需求计算使用(1):3 Mbps, 3.125 Mbps, 3 Mbps,和1.25 Mbps,这些带宽的总和大于输出能力。所有的带宽计算也可见表1。
在第一个迭代中带宽分配使用(2)是4 Mbps, 3 Mbps, 2 Mbps, 1 Mbps。第一个交通类只能使用3 Mbps的分配能力和剩余的1 Mbps分为剩下的3类。这个结果符合该模型(5)。
在第二个迭代的结果(6第一流)等于零这意味着剩下的容量将分为2类,3和4。剩下的1 Mbps再次划分根据权重以下列方式:0.5 Mbps, 0.333 Mbps, 0.167 Mbps和添加到已经分配带宽。
在第三次迭代中剩余容量0.375 Mbps的类之间的3和4除以2的比例:1由于分配权重。这种能力被添加到先前指定的和结果成3 Mbps, 3.125 Mbps, 2.583 Mbps, 1.292 Mbps。
在第四和最后一个重新分配的带宽类4是重新分配的未使用的容量0.042 Mbps到最后不满意3班和充分利用。由此产生的带宽分配如下:3 Mbps, 3.125 Mbps, 2.625 Mbps, 1.25 Mbps。
所有这些结果符合该模型(5)和(7)。

例4。这个例子描述了带宽分配,计算后必须停止条件(8)或(9)。
重量和数据包大小的设置与前面的示例相同3。再次输出带宽设置10 Mbps。到达率设置为1000,1000年、750年和500年pps(每秒数据包)。这些设置会导致带宽的要求3,3,2.25和1.5 Mbps的结果(1)。
在第一个迭代中使用(2)我们分配4、3、2和1 Mbps的队列。在这种情况下,第一个队列1 Mbps剩下的再分配和第二队列已经满意分配带宽。
第二次迭代抽调1 Mbps /使用比率2:1到3和4的队列。带宽分配给他们2.667 Mbps, 1.333 Mbps,但是队列3只需要2.25 Mbps产出能力和剩余的部分能力可以重新分配到最后不满意队列4。
在第三次迭代中我们3 Mbps分配给第一个队列,队列2 Mbps的第二,第三个队列2.25 Mbps, 1.75 Mbps到最后队列。第四个队列只需要1.5 Mbps,这意味着所有队列的带宽需求。迭代停止在这一刻根据(9)否则,模型会导致除以零。
我们可以改变750年第四队列pps的到达率,提高2.25 Mbps带宽需求。在这种情况下,在第三次迭代中带宽分配3,3,2.25和1.75 Mbps。这意味着整个产出能力划分队列(8),我们可以停止迭代。否则每下一步会导致同样的结果。

5。模拟

proove我们数学模型的结果用来模拟在NS2仿真软件9与DiffServ4NS补丁[](版本2.29)10]。

模拟一个简单的网络模型与4传输节点(1 - 4)和四个接收节点(6 - 9)。发射和接收节点相互连接与一个节点0和5之间的联系。节点0使用WFQ调度数据包在这个瓶颈链路带宽提到在哪里集合。所有其他的链接有一个100 Mbps的能力。模型如图1。队列的节点0有足够的能力所以没有包丢失。

我们使用两种类型的流量来源。第一个生成包只有一个数据包大小和常数包时间间隔。这些设置更容易模仿和代表一个D / D / 1 /∞马尔可夫过程的模型。

第二个流量来源类型代表一个M / M / 1 /∞模型。缺乏可能与不同的数据包大小产生交通量NS2模拟器。因为这个原因的M / M / 1源建模使用开/关源,每个节点和一个随机生成一个数据包大小(指数分布)和为下一个包传输是一个随机的时间间隔(同样与指数分布随机数)。

输入数据的一个例子时生成一个节点的数据包大小375 B和到达率1000 pps如图2和3。红色的线条代表的生成相应的数据包数量指数概率计算这些设置和蓝色酒吧代表包中生成的直方图模拟持续了100年。

我们做了许多模拟不同参数设置下。描述的结果提出符合或呈现不同的极端例子设置。模拟的结果的M / M / 1和D / D / 1模型,我们的模型结果如表所示2。

我们测量了带宽在实现“稳定状态。“测量开始后20年代的模拟带宽时稳定和队列填满等待包(11]。

数学模型的结果与仿真结果。D / D / 1的结果仿真模型更准确的将数据包大小的具体设置。小错误可能是由于测量错误,带宽计算在哪里停止紧密包的到来,当小到达率设置。由于确定性参数设置没有区别的运行模拟和没有结果出现差异。

提交结果的M / M / 1模拟是一个平均值计算从10模拟运行和运行的标准偏差。大多数参数设置的模拟运行持续了200年。在一个极端的情况下到达率低是1000年代我们扩展仿真时间。我们还提供与WF模拟²Q + (12代替WFQ)调度程序。仿真结果的记者提出的结果,证明了该模型也适用于其他基于WFQ的调度器使用数据包大小的出列顺序决定。

6。结论

我们提出了一个新的迭代带宽WFQ在基于IP的NGN网络分配模型。提出的模型使用的重量设置WFQ调度器和平均带宽计算的输入带宽不同的流动。不同的变量利用队列和包再分配被认为是在计算。该模型允许方便地预测调度程序的影响,交通牛头刨床和输入交通量的QoS运输数据。

的功能模型,提出了五种不同的例子和仿真证实了在NS2模拟器对D / D / 1和M / M / 1输入交通量。

提出的迭代与WF带宽分配模型进行了测试²Q +调度器使用相同的仿真结果。因此,我们可以说,模型也适用于其他基于WFQ的调度器。

这个带宽分配模型的结果将用于进一步研究延迟和丢包使用马尔可夫链的队列模型建模。

确认

这工作是一个研究活动的一部分在斯洛伐克布拉迪斯拉发技术大学电子工程与信息技术学院、电信学院范围内的项目”支持的卓越中心的智能技术,系统和服务。ERDF, itm 26240120029,得到。”

引用

1. t . Mišuth和i Baroňa排队系统在IP网络中的应用,”EEČAsopis Pre Elektrotechniku Energetiku》16卷,第94 - 91页,2010年。视图:谷歌学术搜索
2. t . Mišuth、大肠Chromy和m . Kavacky“预测的交通联系中心,”学报第六届电气与电子工程国际会议(ELECO ' 09)囊,页111 - 114年,土耳其,2009年11月。视图:谷歌学术搜索
3. a . Demers Keshav s, s . Shenker“公平排队算法的分析和仿真,”ACM计算机通信评审(SIGCOMM学报》89),3 - 12页,1989。视图:谷歌学术搜索
4. l .张“虚拟时钟:分组交换网络,新交通控制算法”计算机系统的ACM的诉讼事务,9卷,不。2、101 - 124年,1990页。视图:谷歌学术搜索
5. k . Molnar和m . Vlcek MPLS网络带宽约束评估模型”,电子产品1卷,第175 - 172页,2009年。视图:谷歌学术搜索
6. RFC 4125,最大分配带宽约束模型DiffServ-Aware MPLS流量什么,互联网协会,2005。
7. RFC 4126,马克斯与预约带宽分配Diffserv-Aware MPLS流量工程的约束模型和性能比较,互联网协会,2005。
8. RFC 4127,俄罗斯套娃为DiffServ-Aware MPLS流量什么带宽约束模型,互联网协会,2005。
9. 网络Simulator-ns-2,http://www.isi.edu/nsnam/ns/。
10. 塞吉奥Andreozzi。”DiffServ4NS。”http://sergioandreozzi.com/research/network/diffserv4ns/。视图:谷歌学术搜索
11. k . Pawlikowski h·d·j·宋和J.S.二r·李,“电信网络的仿真可信度研究。”IEEE通讯杂志,40卷,不。1,第139 - 132页,2002。视图:谷歌学术搜索
12. j·c·r·班纳特和h张“分层分组公平排队算法,”《IEEE / ACM交易网络,第689 - 675页,1997年。视图:谷歌学术搜索

版权

版权©2012 TomašBalogh和马丁Medvecky。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。