自适应GRED、REDD和GRED-线性分析模型的性能研究

Journalof King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.com主动队列管理方法的性能研究：自适应GRED、REDD和GRED-线性分析模型侯赛因·阿卜杜勒-贾比尔沙特阿拉伯阿拉伯开放大学信息技术和计算系计算机研究学院接收日期：2014年7月23日;修订日期：2014年12月4日;接受日期：2015年1月26日2015年9月11日在线发布摘要拥塞控制是保证计算机网络性能的重要研究课题之一本文比较了三种主动队列管理（AQM）方法，即自适应温和随机早期检测（Adaptive GRED）、随机早期动态检测（Random Early Dynamic Detection，REDD）和GRED线性分析模型（GRED LinearAnalytical Model）在不同性能指标上的差异自适应GRED和REDD是基于模拟实现的，而GRED线性是作为一个离散时间的分析模型实现的。通过几个性能指标主要是平均队列长度、吞吐量、平均排队延迟、溢出丢包率和丢包率来评估比较方法的有效性最终目的是确定在非拥塞或拥塞情况下提供最高满意性能的方法基于不同分组到达概率值的第一次比较结果表明，在拥塞情况下，GRED Linear比Adaptive GRED和REDD方法提供更好的平均队列长度、平均排队延迟和分组溢出概率此外，使用相同的评估措施，自适应GRED提供了一个更令人满意的性能比REDD重拥塞时当队列容量有限时，GRED线性模型的平均队长和平均排队时延性能最好，而所有比较方法的吞吐量性能相近。然而，当有限容量值较大时，比较的方法在分组溢出和分组丢弃的概率方面具有相似的结果。©2015作者制作和主办：Elsevier B.V.代表沙特国王大学 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍电子邮件地址：habdeljaber@arabou.edu.sa沙特国王大学负责同行审查随着现代通信和计算机网络的出现，网络源需要足够的 资 源 将 其 数 据 传 送 到 目 的 地 （ Tanenbaum ，2002）。资源不足会导致拥塞，当传入数据包的数量超过可用网络时就会发生拥塞http://dx.doi.org/10.1016/j.jksuci.2015.01.0031319-1578© 2015作者制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词自适应GRED;离散时间排队; GRED线性分析模型;业绩计量;REDD主动队列管理方法资源（Welzl，2005年）。拥塞会导致网络性能的几种形式的下降，例如：（1）平均队列长度的不稳定，因此许多到达的分组将由于路由器缓冲区的拥塞内容而被丢弃，(2)分组的高丢失和平均转发延迟，（3）低吞吐量，以及（4）网络资源在网络源之间的不平衡共享。拥塞控制对于提高网络性能是重要的，并且可以使得 用 户 能 够 有 效 地 使 用 网 络 （ Aweya 等 人 ， 2001;Welzl，2005）。由于网络流量的敏感性，拥塞控制是一个挑战（Welzl，2005）。随着实时性和按需性的发展，拥塞控制成为一个非常活跃的研究领域。目前，可以在网上找到几种媒体业务应用，例如视频会议、IP语音（VoIP）、视频点播（VoD）、视频流等。使用这些媒体流量应用的用户数量在基于TCP的网络应用中，当拥塞发生时，TCP流会降低自身的传输速率来管理拥塞。因此，产生了网络流的公平份额。相比之下，当拥塞发生在非TCP网络应用中时，非TCP流将继续以其原始速率传输，这导致网络资源的不公平共享。几个研究人员已经提出了拥塞控制机制，诸如丢弃尾部（Brandauer等人，2001）和主动队列管理（AQM）Abdeljaber等人，2011;Aweya等人，2001; Feng等人，1999;Floyd和Jacobson，1993; Floyd等人，2001; Floyd，2000.当路由器缓冲区溢出时，丢弃尾部确定拥塞（Braden等人，1998; Brandauer等人，2001年）。因此，拥塞是在路由器缓冲区变满后识别的，这意味着丢弃尾中的拥塞是在后期发现的。AQM机制在路由器缓冲区变满之前识别拥塞。换句话说，AQM机制在早期发现拥塞。随机早期检测（RED）（Floyd和Jacobson，1993）及其变体（Floyd等人，2001; Floyd，2000）被提出作为AQM机制来控制拥塞，并且是基于仿真构建的。已经提出了RED的变体来处理RED的缺陷，例如以下：（1）RED的拥塞度量（平均队列长度（aql））随着拥塞水平而变化，使得当存在轻度拥塞时，aql值接近RED路由器缓冲器上的最小阈值位置（min阈值）。相反，当发生严重拥塞时，aql值接近RED路由器缓冲器上的最大阈值位置（maxthreshold）（2）RED对参数（最小阈值、最大阈值、最大丢包概率值（pdmax）和队列权重（qw））敏感。(3)aql值取决于TCP流的数量。因此，当TCP流的数量高时，aql值可能超过最大阈值(4)当存在繁忙业务时，RED不能将aql值保持在最小阈值和最大阈值位置之间。因此，aql值可能超过最大阈值位置，这导致严重拥塞。本文的目的是评估三个主动队列管理方法在一个单一的队列节点的性能。基于仿真实现了自适应GRED和REDD两种主动队列管理方法，方法建立了离散时间排队分析模型，称为GRED线性分析模型。本文批判性地比较了拥塞控制方法，主要是自适应GRED ， REDD 和 GRED 线 性 使 用 不 同 的 评 估 措 施（mql，T，D，PL和DP）。本文在深入分析了丢包率对平均队列长度、平均排队延迟和包溢出的影响后，性能测量结果的结果可以帮助选择可以在诸如因特网的计算机网络中应用为拥塞控制方法的方法本文的结构如下：相关的工作在第2节进行了审查。第3第6节中介绍了GRED和自适应GRED方法之间的先前比较。自适应GRED和REDD的模拟细节在第7节中演示。第8节介绍了不同的分析建模方法，以及使用仿真进行验证和最后，第9节和第10节显示了基于分组到达概率的变化值和队列的有限容量的变化值的自适应GRED、REDD和GRED线性的性能评估结果。结论和对未来工作的建议见第11。2. 相关工作AQM机制的其他示例是基于离散时间队列方法提出的分析模型（Abdeljaber等人，2008，2008; Al-Diabat等人， 2012）和基于仿真的不同AQM机制。Woodward写了一本关于建立离散时间队列分析模型的书，其中这些分析模型是通过对排队系统（如计算机通信和网络）的性能进行建模和分析而建立的（Woodward，1993）。Abdeljaber等人（2008，2008）和Al-Diabat etal. （2012）建立了基于DRED、GRED和BLUE机制的离散时间排队分析模型。Bonald等人（2000年）提出了另一个基于RED的分析模型。这些分析模型通过将数据包到达概率从固定值降低到另一个值或线性降低来控制拥塞。（Lim等人，2011）被提出作为分析模型，并且使用聚集的互联网业务作为不同类别的业务的源。 该分析模型作为队列管理机制工作，用于在路由器缓冲器上将排队延迟维持在特定水平（Lim等人， 2011年）。 该开发模型利用闭环反馈的控制方法（Lim等人，2011）通过隐式地通知到达速率和通过移动排队阈值来限制平均排队延迟（Lim等人，2011年）。该模型以网络流量模型为基础，利用N马尔可夫调制伯努利过程-2（MMBP-2）的到达过程的叠加来表示网络流量的聚集，推导出了网络流量聚集阈值与平均排队时延之间的关系根据推导出的排队阈值与平均排队延迟之间的关系以及对平均排队延迟反馈的评价，对排队阈值进行了修正。数据包可以丢弃四氢呋喃的1aiap.Σ418 H. 阿卜杜勒-贾比尔动态地根据分组阈值和分组丢失事件的修改（Lim等人， 2011年）。Wang等人（2011）作为建模系统引入并且作为用于单个缓冲器的分析方法小于最小阈值且小于两倍Max阈值值为例如，当maxthreshold6aqldouble maxthreshold时，路由器缓冲区<1-Dmax并将平均排队延迟控制为在各种交通网络流中的必要价值的丢弃数据包的概率为Dmax（Abdeljaber等人， 2011年）。2最大阈值应 用 的 敏 感 延 迟 可 以 使 用 该 方 法 在 其 服务质 量（QoS）性能方面得到改善（Wang等人， 2011年）。Wang等人（2011），提出了一种基于离散时间排队的解析模型，推导了平均排队延迟与排队阈值之间的关系. 该分析模型使用各种交通流，这些交通流已经使用二项分布作为到达过程来建模（Wang等人，2011年）。对排队门限进行了修正，作为平均排队时延的控制方法。数据包作为拥塞通知被丢弃到到达过程以更新它们的速率。Al-Bahadili等人（2011）提出了一个包含多队列节点的网络的分析模型。该模型导出了两个性能指标，即系统利用率和队列节点。 Al-Bahadili等人（2011）提出了两个场景，展示了在几种路由概率和系统规模下，系统利用率和队列节点与队列节点丢弃概率的变化。Kamoun（2006）提出了一个精确的瞬态和平衡分析的离散时间排队的统计多路复用器使用相关的到达过程与有限数量的输入链接。该模型还使用了恒定数量的恒定数据包长度。该分析模型有助于获得参考缓冲容量的瞬时概率的生成函数（Kamoun，2006）。Andrzej和Chrost（2011）研究了基于队列长度和作业到达被阻塞然后丢失的时间的概率。主动队列管理算法在这项研究中使用本研究的输出这些解析解还包含阻塞概率，例如丢弃函数。3. 自适应GRED提出了自适应GRED以增强GRED在mql、T和PL方面的性 能 测 量 （ Abdeljaber 等 人 ， 2011 年 ） 。 类 似 于GRED ， 自 适 应 GRED 使 用 aql 作 为 拥 塞 度 量（Abdeljaber等人，2011年）。自适应GRED也被开发为 识 别 网 络 内 的 早 期 拥 塞 的 拥 塞 控 制 方 法（Abdeljaber等人，2011年）。此外，自适应GRED旨在改善最大阈值（位于自适应GRED路由器缓冲区）和pdmax（最大数据包丢弃概率值从pdmax到0.5，因为AQL值从最大阈值到双最大阈值变化。因此，自适应GRED在配置maxthreshold和pdmax参数时增强了GRED（Floyd，2000）。最后，如果aql值等于或大于双最大阈值，则发生严重拥塞，并且路由器缓冲区丢弃每个到达的数据包。4. GRED线性分析模型GRED线性模型是一种离散时间队列分析模型，被提出用于对单个队列节点的性能进行建模和分析（见图1）（Abdeljaber等人，2008年）。GRED线性模型的性能测量结果可以用作拥塞控制方法的性能结果。因此，GRED线性模型可以用作拥塞控制方法。在GRED线性模型中，如果当前队列长度（ql）小于最小阈值位置，则不会发生拥塞并且不会丢弃分组（DP=0.0）。此外，分组到达GRED线性路由器缓冲器的概率为1。如果当前ql值等于或大于最小阈值的值并且小于最大阈值的值，则存在拥塞。为了控制拥塞，分组到达概率值从a1线性减小到ai，其中i是队列状态，一的11我 最 小阈值Δ1-Δ2 μ m，双最大阈值-最小阈值如果min_threshold是 max_threshold的两倍，并且ai依赖于状态转换图（参见图2），则该部分建议方法意味着分组到达概率值基于队列状态（i）而减小，并且当i大于 或 等 于 min_threshold 并 且 小 于 路 由 器 缓 冲 器 处 的max_threshold的两倍a1，a1>a2。 图2显示了GRED线性模型的状态转换图GRED 线 性 模 型 的 平 衡 方 程 在 方 程 中 进 行 评 估 。（1）-（10）使用图 二、p01 2 3 45 67891011 12 13 1415 16 17 18 19p1¼a1p0½a1b1-a11-b]p1½b1-a1]p22pK21-b]pK-121-b]pK10其中K=双最大阈值+X，双最大阈值=最大阈值+J，最大阈值=最小阈值+一. 因此，K也可以表示为：K¼min阈值让ciai1-b;i1; 2：12b1-ai及cai1-b;其中，最小阈值6是最大阈值的两倍<一般而言b1-aið13Þpi½a11-b]pi-1½ a1b 1-a1 1-b]pi½b 1-a1]pi1;其中i/2; 3; 4;. ;最小阈值-2ð3Þp最小阈值d-1/4½a1/1-b1/2]p最小阈值-2最小阈值-1½bp最小阈值1/2a1/1-bn]p最小阈值-1/2a最小阈值db最小阈值½b当量公式（13）用于简化获得均衡概率（pi，i=min阈值，min阈值+1，min阈值+2，. . ，双最大阈值1），这些概率有助于提供GRED线性分析模型的性能测量。等式内容表示在每个队列状态i处，在该队列状态i处的分组到达概率（ai）乘以1减去分组离开概率（Ib）。 然后将结果除以分组离开概率（b）乘以1减去在该队列状态i处的分组到达概率（1 -ai）。我420H. 阿卜杜勒-贾比尔XYY“.YY不-.ΣQa1a21-bajQc1c21-a1cc1min阈值1/4 1-c1min阈值-b1-c1 min阈值c1min阈值c 1-a1 min阿利什卡槽位¼槽位¼i¼0i插槽1220QJ0T¼b1/4b 1-p0数据包=插槽21GRED线性模型的平衡概率是通过递归求解平衡方程和应用方程组来计算的。（12）和（13）。平衡概率如方程所示。（14）K1/4pi¼1 17doublemaXxthreshold-1p双最大阈值公司简介1#101-b1-c11，1-二氯苯基i/4 min阈值Jj/4 min阈值1-ai1-bLl/4 min阈值ð18Þ总的来说a1i1-bi-1c1iGRED线性模型的性能指标计算如下。首先是mql，它是平均队列pi¼bi 1-a 1i p01/2- b1/2p0;其中i 1; 2; 3;... ;最小阈值-114当量（14）表示均衡概率（p0，p1，. . ，pmin 阈 值 -1），并且这些概率再次有助于提供每个GRED线性分析模型的测量。长度，应尽可能小，以避免建立了路由器缓冲区的内容。使用生成函数P（z）计算mql，其在等式2中示出。（十九）、mql等于P（z）在z=1处的一阶导数，如等式2所示。（20）.XKPz我2c1-c1min阈值d½c1min阈值1-c1min]c1min阈值1-a1min3mql<$P11< $p01-c16double m aXxthreshold-1i-1双最大阈值-1！7我21-b公司简介双最大阈值d1-c21-c2X11c2-c2X1½1 X1-c2]2005年i/4 min阈值j/4 min阈值J1-ai1-a2l/4 min阈值Lð20Þa1min阈值1- bi-1Qi-1a我0其次，T是吞吐量，可以定义为最小阈值pbi1-a1最小阈值-11-aj成功通过路由器的数据包数缓冲液T在Eq中获得。（21）.我j/4 min阈值c1min阈值1-a1Qi-1cK最小阈值jp：1500XY1/1我其中i=最小阈值，最小阈值+1，最小阈值+2，.. . ，double max threshold1 and aj=1，if j目标aql并且{最大阈值（K-最小阈值））分组到达分组离开//如下增加maxthreshold2：最大阈值=最大阈值+ 2;双最大阈值最大阈值min阈值}在路由器缓冲区图3 REDD的伪代码图4自适应GRED的单个路由器缓冲区422H. 阿卜杜勒-贾比尔最大阈值目标aqlmin阈值分组离开B的1标记/丢弃每个标记/丢弃数据包不标记/丢弃到达数据包的概率分组到达在路由器缓冲区图5 REDD的单个路由器缓冲区图6每个时间段都有到达和离开的离散时间队列的状态（Woodward，1993）结果与分组到达概率的值无关。当分组到达概率为60： 6 3时，自适应GRED和GRED的PL和DP结果相似当分组到达概率大于0.63时，自适应GRED的PL性能优于GRED，而D-P性能优于自适应GRED。7. 自适应GRED和REDD在一个固定的时间单位命名为时隙（伍德沃德，1993年）的数据包到达自适应GRED/REDD路由器缓冲区的概率是1。b是时隙中数据包从自适应GRED/REDD的 路 由 器 缓 冲 区 离 开 的 概 率 。 伯 努 利 过 程（Woodward，1993）用于对分组到达进行建模，而分组离开使用几何分布进行建模。数据包到达间隔时间是几何分布的，平均值为1。数据包离开时间是几何分布的，平均值为1。分组到达或离开概率发生在时隙中。每个时隙可以包含数据包到达和/或离开事件，或者不包含这些事件（Woodward，1993）。自适应GRED和REDD模拟了单个队列节点的网络，如图2和图3所示。分别为4和5。数据包以单一方式到达和离开一个路由器。网络的路由规则是FCFS。8. 不同的分析建模方法通过对排队网络系统的建模和分析，建立了排队网络系统的分析模型分析模型的结果可以是：（1）平衡方程，（2）稳态概率，以及性能指标，如平均队长，吞吐量等。一般来说，每一个系统都可以用Kendall 的 符 号 描 述 为 五 个 组 成 部 分 （ Woodward ，1993），如下所示1. 到达过程：一个随机过程，显示客户（数据包）如何到达排队系统。到达过程记为A。2. 服务过程：一个随机过程，说明客户（数据包）在服务器上花费的时间。服务过程表示为B。3. 服务器数量（C）。4. 系统容量：它代表了最大数量的5. 客户人数：它表示参与到货流程的客户总数的限制。客户群体表示为P。应该注意的是，还有另一个与Kendall的组件相关的因素，即先到先服务（FCFS）、后到先服务（LCFS）和处理器共享（PS）是这种情况的例子K和P分量可以被移除，在这种情况下，这些分量被认为是无穷大值。C、K和P分量是正整数，并且A和B分量基于描述符的集合来选择。本节介绍了两种不同的方法来建立分析模型，这取决于对排队系统的建模和分析，它们是连续时间队列 （ Ross ， 2010 ） 和 离 散 时 间 队 列 （ Woodward ，1993）。8.1. 离散时间排队法离散时间排队是一种建模和分析通信和计算机网络中排队系统性能的方法（Woodward，1993）。在离散时间排队系统中，到达间隔时间和服务时间是“几何”分布的，在多次到达和多次离开的情况下，指数分布是可能的。使用称为时隙的基本时间单位，其中在每个时隙中可能发生单个或多个事件。单个事件的示例是分组到达或离开的发生通常，分组到达发生在时隙开始之后，并且分组离开发生在时隙结束时隙n中的到达和离开的数量由{a，n，n = 0，1，2，. . }和{dn+1，n=0，1，2，. . . }，其中{an}表示具有特定分布的相同且独立分布（i.i.d）的随机变量的序列。 d0= 0，因为没有分组可以在它们到达之前离开。图1描述了一个离散时间排队的状态，每个时隙都有到达和离开。 六、在时隙边界处的队列长度的过程由{y n，n = 0，1，2，3，.. .{0}，y0是任意的。因此，Eq。（25）介绍。yn1ynan-dn1 25当量（26）表示到达发生后的队列长度的处理{Xn= n = 0，1，2，.. . }.系统内的客户（分组），包括当前的分组，在服务中系统容量记为K。Xn1 ¼Xn -dn1anð26ÞSlot1插槽nanSlot1一个月1日Dndn1yn2011年1月1XnXn1主动队列管理方法的性能研究423-fg这后一个公约（Eq.（26）），有时称为“departure-ture first”，将用于本文的模型中。其中一个随机过程被称为马尔可夫过程，它的一个特殊类型是马尔可夫链（伍德沃德，1993）。马尔可夫过程是一种随机过程，它被称为无记忆性的马尔可夫性质所专门化，该性质可以作为指数分布以及泊松过程的到达间隔时间中的一种性质存在。因此，泊松过程是马尔可夫过程的一个特例假设x={x，n=x; n= 0，1，2，.. . }，xeX是一个马尔可夫链，其中xn是时间n的状态，n是时间离散化后的时间指数，n得到连续的非负整数值{0，1，2，. . }. x是可以具有在{0，1，2，. . }，并且X是状态空间{0，1，2，.. . （Woodward，1993）.马尔可夫性质的表达式如下：Pxn1jx0;x1;x2;. . . ;x nn. .这意味着在时间n的给定状态中，时间n +1的状态与时间0、1、2、.的所有过去状态无关。. ，n1。马尔可夫链的演化由其一步转移概率P ij（n）解释，即给定时间n的状态i，链将在时间n+1移动到状态j。PijnPXn1ii;j2X;n1/40;1;2;. . .马尔可夫链上的一步转移概率不依赖于时间指数n的例子被称为时间齐次（Woodward，1993），并且这被提供如下：pi;jnpij;i;j 2 X;n <$0; 1; 2;.. .ð27Þ以下是离散时间队列的示例，可以对这些队列进行建模和分析以构建分析模型：M/D/1排队系统可用于为计算机通信网络中的用户建模缓冲区（Woodward，1993）。在该分组系统中，M表示该系统具有几何分布的到达间隔时间，其中在一个时隙中允许零个或一个分组到达。此外，D表示该系统具有恒定的服务时间，其中允许零个或一个分组在时隙中服务。服务器的数量是一个，系统容量和客户数量是无限的，并且部署规则是FCFS。离散时间排队系统的第二个例子是M/M/1，第一个M表示排队系统具有地理分布的到达间隔时间，其中允许一个或零个分组在时隙中到达。第二个M表示系统具有几何分布的服务时间，在一个时隙中允许零或一个离开。8.2. 连续时间排队法连续时间队列用于通信和计算机网络中的性能排队系统的建模和分析（Woodward，1993）。连续时间排队和离散时间排队一样使用Kendall在连续时间队列中是必要的。例如，竞争对手之间的时间是泊松过程，服务时间是连续时间马尔可夫链是一个过程x t;tP0，在{0，1，2，3，.. . }，例如假设过去，现在和未来是独立的PXtyjjXyi;Xuxu;06uyB）和非拥塞（即，a1B）和非拥塞（即，a1b）。因此，当前的研究可以评估自适应GRED，REDD和GRED线性模型在有和没有拥塞的情况下的性能，并且将K设置为20的原因与之前提到的相同，即在小缓冲区大小的情况下测量性能。minthreshold、maxthreshold、qw和pdmax的值分别设置为3、9、0.02和0.1，类似于RED方法（Floyd和Jacobson，1993）。双最大阈值设置为18，类似于GRED方法（Floyd，2000） 。时 隙是 离散 时间 队列 方法 （Woodward，1993）中使用的时间单位，用于产生当系统达到稳态时到期的预热期自适应吞吐量平均排队延迟溢出丢包率主动队列管理方法的性能研究4255.00E-014.00E-013.00E-012.00E-011.00E-010