2. 湖南武陵生态农业智能控制技术重点实验室, 湖南 怀化 418008;
3. 嘉兴学院 数学物理与信息工程学院, 浙江 嘉兴 314001
2. Key Laboratory of Intelligent Control Technology for Wuling-Mountain Ecological Agriculture in Hunan Province, Huaihua 418008, Hunan, P. R. China;
3. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, Zhejiang, P. R. China
在无线网络接入有线网络时,存在着许多的不公平现象。在多条上行的(transmission control protocal,TCP)流共存时,存在着吞吐率不公平现象。在上行的TCP流和下行的TCP流共存时,存在着上行TCP流吞吐率远大于下行TCP流的现象。在多速率的无线网络中,由于慢速的TCP流过多的占用无线信道时间,造成了TCP流无线信道占用时间不公平现象。
1 研究现状对于无线网络接入有线网络存在的拥塞控制问题,人们开展了一系列的研究,提出了多种公平性算法[1-8],以解决这些问题。
上行TCP流的公平性问题:对于拥塞窗口大的TCP流,由于(ACKnowledgement,ACK)分组数量较多,且具有累计确认效应,在超时重传之前收到ACK分组,就不会引发超时重传,部分ACK分组丢失,并不会影响上行TCP流发送速率。对于拥塞窗口小的TCP流,ACK分组丢失会使得TCP流发送速率的减少,造成上行流之间吞吐率的不公平性。针对上行流间的公平性问题,文献[9]提出了公平调度的解决方法。由于每流的ACK分组平均到达间隔时间与拥塞窗口的大小成反比,为此对ACK分组设置一个到达间隔时间上限,当ACK分组到达间隔时间超过这个上限时,就优先发送。拥塞窗口小TCP流的ACK分组发送间隔时间大,容易得到优先发送,从而获得了上行流间吞吐率公平性。
上下行TCP流的公平性问题:在下行流中,下行TCP流的Data分组和上行流的ACK分组同时竞争下行缓存,下行TCP流Data分组的丢失会造成发送端的发送速度下降,而ACK具有累计确认效应,ACK分组的丢失对上行流的发送速率影响不大。也就是说,下行的TCP流对Data分组的丢失和上行TCP流对ACK分组丢失的敏感性不一致,造成了上下行TCP流吞吐率的不公平性。
Ferrero提出了单队列(least attained service,LAS)调度机制[10-14],根据到达分组序号,确定TCP流的到达分组数量,到达分组数量较少流的分组插入缓存队列的位置靠前,在系统的轮询调度中优先出队,从而解决了上下行TCP流吞吐率不公平的问题。文献[15-18]提出在无线网络接入有线网络接入点(access point,AP)的下行缓存队列中,把缓存分成多个子队列,采用多队列调度机制,通过调整下行流的DATA分组和上行流的ACK分组出队概率,保证吞吐率的公平性。
然而这些都忽视了无线网络的多信道速率带来的不同速率流占用信道时间的不公平性问题,要保证吞吐率的公平性,慢速的TCP流必定占用更多的信道时间,从而挤占了快速的TCP流占用信道的时间,造成网络总体效率的下降。解决这个问题,只能在吞吐率公平性和网络总体效率之间找到一个平衡点,做一个理想的折中[19-20]。目前,无线网络公平性策略的目标都具有一定的局限,例如:对上下行流吞吐率的公平性仅考虑无线信道的速度相同的情况,对上行流之间吞吐率的公平性,仅考虑方向一致的情况。这些基于吞吐率公平性策略,使得多速率无线网络在信道速率不同时,网络的总体效率下降。而一个好的公平性策略,往往是尽可能考虑多个公平性目标,成为多个目标的最优方案[21-22]。
2 LAS的改进算法TFLAS鉴于以上所述情况,提出一个基于(least attains service,LAS)的改进算法(time fairness of LAS,TFLAS)以实现2种目标:当无线信道速率相同时,通过调节下行缓存队列中的Data和ACK流的出队概率来保证吞吐率的公平性。当信道速率不同时,根据不同信道速率调整各流的调度概率,保证各TCP流公平的占用信道时间,解决慢速的TCP流挤占过多信道的问题,从而提高网络整体的性能。
2.1 调度模型LAS算法是以保证上下行流吞吐率的公平性为目标,在多信道速率的情况下,会造成了慢速流占用了较多的信道时间,从而降低了网络的总体效率。
为解决这个问题,新的调度算法TFLAS,以无线信道的速率为依据,设计一个状态变量流的阻塞因子(echmasis factor of flow,EFF),以阻塞因子的大小反映流的速度慢与快,按照阻塞因子的大小和每流到达分组数多少,决定流插入到缓存队列的前后位置。当这个值大时,插入到缓存队列较后的位置上,反之插入在缓存队列较前位置。这样的优越性在于既保证吞吐率的公平性,也保证了每流占用信道的时间公平性,提高网络的整体效率。
2.2 阻塞因子Eff的计算忽略传输时延,流i分组占用信道的时间为:ti=si/ri+tov,其中si是分组的长度,ti是分组的速度,tov是控制开销时延。用smax、rmax、tmax分别表示最大速率流分组长度和速度及占用信道时间,那么tmax=smax/rmax+tov。
流i阻塞因子设计为Eff(i)=ti/tmax…(1),即Eff(i)=(si/ti+tov)/(smax/tmax+tov)
从公式(1)可以推知,最大速率流的阻塞因子Eff=1,其他流由于分组占用信道时间ti大于tmax,阻塞因子Eff(i)>1,这样阻塞因子的大小反映了流分组速率的快慢,阻塞因子大流分组速率就慢,阻塞因子小流分组速率就大。
2.3 TFLAS算法描述为反映流到达分组的个数,对流i的分组设置一个递增分配关键码Keyi,其值取到达分组的个数。依据流的关键码和阻塞因子的乘积把分组插入到缓存队列相应位置,关键码和阻塞因子的乘积小的分组插入到缓存队列较前的位置,从而到达分组较少和阻塞因子小的流获得了优先发送。实施步骤
1) 在AP下行缓存队列中,接到流i的一个分组,如果是流i的第一个分组,关键码Keyi取1,否则,关键码Keyi加1。
2) 根据公式(1)计算阻塞因子:Eff(i)。
3) 分组标记Keyi。
4) 分组进入缓存队列,如果缓存队列满,分组丢弃,否则计算:Keyi*Eff,其值小的排在队列前面。
算法描述如下:
On receive Packet P
{ i=classify(P);
if P is NO.1,Keyi=1
else Keyi=Keyi+1;
Mark_packet(Keyi,P);//标记Keyi
Count_Eff(i);//计算Eff
bi=Eff(i);
j=0;
while(j<buffer_size and
bj*Keyj>bi*Keyi)
j++;
if(j=buffer_size) Drop(P);
eles Insert(P,Pj);//分组P插入到Pj前
}
3 仿真实验与分析通过仿真实验来验证TFLAS算法的效能,实验网络拓扑图如图 1所示,有线网络节点S1、S2、S3与路由器链路带宽为15 Mbps,路由器与无线网络接入点AP的链路带宽为15 Mbps,时延为2 ms,各节点的传输控制协议采用TCP NewReno,无线网络MAC层采用IEFE 802.11 b协议,实验分别对尾部丢弃Droptail、LAS、TFLAS算法进行测试,实验时间为60 s,分别比较3种算法上下行流时间公平性和网络总吞吐率。
由于实际情况是下行流量通常高于上行流量,因此设定2条下行流和1条上行流共存,节点S1、S2分别向D1、D2发送TCP下行流,无线发送速率固定为11 Mbps,节点D3向S3发送TCP上行流,开始时无线发送速率固定为11 Mbps,以后逐步减小,在时间点20 s、40 s,无线发送速率分别降为,5.5 Mbps,2 Mbps,这样提供了一个多速率的无线网络场景。实验对3种算法的上下行平均每流信道占用时间比以及网络总吞吐率进行统计,上下行流平均每流占用信道时间比如图 2所示,网络总吞吐率如图 3所示。
上下行平均每流占用时间比越接近为1,上下行每流信道时间公平性就越好。从图 2可以看到,TFLas算法的上下行每流平均占用信道时间接近1,每流平均占用信道时间公平性最好。Las算法上下行平均每流占用时间比高于TFLas算法,低于Droptail算法,公平性居中,Droptail算法上下行平均每流占用时间比最高,反映上行流严重挤占了下行流的信道占用时间,时间公平性最差。随着D3节点无线信道速率的逐渐下降,三种算法网络总体吞吐率的差异显现出来,TFLAS算法的吞吐率最高,LAS算法吞吐率居中,Droptail尾部丢弃算法吞吐率在信道速率变化的情况下明显下降,这反映了在保证吞吐率公平的情况下,慢速的TCP流占用了较多的信道时间,造成网络总吞吐率下降。
4 结 论在无线网络接入有线网络的接入点容易出现网络拥塞和网络资源分配不公平现象,成为无线网络的瓶颈。针对多速率无线网络环境下不同速率TCP流存在的时间分配不公平、网络总吞吐率下降的情况进行了分析,并提出了解决问题的算法。通过调整慢速TCP流的发送时间,避免低速率流占用大量信道时间,从而提高了网络整体效率。新的算法还可以调整流的阻塞因子,轻松的实现QoS级别流的区分服务,具有较好的扩展性。经过NS网络仿真实验,证明了新的拥塞控制算法TFLAS在网络吞吐率和上下行平均每流占用信道时间的公平性有了较大的改进。
[1] | Mansour S, Ehsan H. Transient chaotic neural network-based disjoint multipath routing for mobile ad-hoc networks[J]. Neural Computing and Applications, 2012, 21(6): 1403–1412. DOI:10.1007/s00521-011-0594-6 |
[2] | Shreedhar M, George V. Efficient fair queueing using deficit round robin[J]. IEEE/ACM Transactions on networking, 1996, 4(3): 375–385. DOI:10.1109/90.502236 |
[3] | Wang D L, Fattouche M. Range estimation in a time varying multipath channel[J]. Wireless Personal Communications, 2013, 71(2): 887–908. DOI:10.1007/s11277-012-0850-9 |
[4] | Faissal E B, Hussain B A, Mostafa B. New results for Shannon capacity over generalized multipath fading channels with MRC diversity[J]. Eurasip Journal on Wireless Communications and Networking, 2012(1): 1–12. |
[5] | Parekh A K, Gallager R G. A generalized processor sharing approach to flow Control in integrated services networks:The single-node case[J]. IEEE/ACM Transactions on networking, 1993, 1(3): 344–357. DOI:10.1109/90.234856 |
[6] | Stiliadis D, Varma A. Effieient fair queueing algorithms for packet-switched networks[J]. IEEE/ACM Transactions on networking, 1998, 6(2): 175–185. DOI:10.1109/90.664266 |
[7] | Goel S, Jemal H. Abawajy, Tai K. Performance analysis of receive diversity in wireless sensor networks over GBSBE models[J]. Sensors, 2010, 10(12): 11021. DOI:10.3390/s101211021 |
[8] | Li Q X, Lin Y. A briefing to grey systems theory[J]. Journal of Systems Science and Information, 2014, 2(2): 178–192. |
[9] | Li P, Liu J. Design and pricing of chinese contingent convertible bonds[J]. Journal of Systems Science and Information, 2014, 2(5): 428–436. |
[10] | Yang YB, Cai F, Guo W M. On error detection of intermediate nodes Offour-Node network with small downstream links[J]. Wuhan University Journal of Natural Sciences, 2015, 20(1): 39–46. DOI:10.1007/s11859-015-1056-2 |
[11] | Katevenis M, Sidiropoulos S, Courcoubetis C. Weighted round-robin cell multiplexing in a general-purpose ATM switch chip[J]. IEEE Journal on Selected Areas in Communications, 1991, 9(8): 1265–1279. DOI:10.1109/49.105173 |
[12] | Hao W, Nan L, Li Z H, et al. A unified algorithm for mobility load balancing in 3GPP LTE multi-cell networks[J]. Science China Information Sciences, 2013, 56(2): 1–11. |
[13] | Lin D S, Xiao M, Li S Q. Packet combining based on cross-packet coding[J]. Science China Information Sciences, 2013, 56(2): 1–10. |
[14] | Mirhakkak M, Schult N, et al. Dynamic bandwidth management and adaptive applieations for a variable bandwidth wireless environment[J]. IEEE Journal On Seleeted Area in Communieations, 2001, 19(10): 1984–1997. DOI:10.1109/49.957313 |
[15] | EIRakabawy S M, Lindermann C. A practical adaptive pacing scheme for TCP in multihop wireless networks[J]. Networking, 2011, 19(4): 75–988. |
[16] | Jorge A, Mohamed G. Time-shift scheduling:Fair seheduling of flow in high-speed networks[J]. IEEE/ACM Transactions on networking, 1998, 6(3): 274–285. DOI:10.1109/90.700891 |
[17] | Afanasyev A, Tilley N, Reiher P, Kleinrock L. Host to host congestion control for TCP[J]. Communications Surverys &Tutorials, 2010, 12(3): 304–342. |
[18] | Peng L Z, Yang B, Chen Y H. Effective packet number for early stage internet traffic identification[J]. Neurocomputing, 2015, 156(25): 252–267. |
[19] | Jiang Q M, Mi C Q, Yue G X. A dynamic network QoS control mechanism based on traffic prediction[J]. Journal of Chongqing University (English Edition), 2015, 14(2): 73–78. |
[20] | Wang Y L, Song M, Wei Y F. Improved ant colony-based multi-constrained QoS energy-saving routing and throughput optimization in wireless Ad-hoc networks[J]. The Journal of China Universities of Posts and Telecommunications, 2014, 21(1): 43–53. DOI:10.1016/S1005-8885(14)60267-3 |
[21] | Qiao Y Y, Lei Z M, Yuan L, et al. Offline traffic analysis system based on Hadoop[J]. The Journal of China Universities of Posts and Telecommunications, 2013, 20(5): 97–103. DOI:10.1016/S1005-8885(13)60096-5 |
[22] | Wang R Y, Liu Z, Zhang L. Method of data cleaning for network traffic classification[J]. The Journal of China Universities of Posts and Telecommunications, 2014, 21(3): 35–45. DOI:10.1016/S1005-8885(14)60299-5 |