Expelling Policy Based Buffer Control during Congestion in Differentiated Service Routers

Authors: Kumar Padmanabh, Rajarshi Roy

Abstract:

In this paper a special kind of buffer management policy is studied where the packet are preempted even when sufficient space is available in the buffer for incoming packets. This is done to congestion for future incoming packets to improve QoS for certain type of packets. This type of study has been done in past for ATM type of scenario. We extend the same for heterogeneous traffic where data rate and size of the packets are very versatile in nature. Typical example of this scenario is the buffer management in Differentiated Service Router. There are two aspects that are of interest. First is the packet size: whether all packets have same or different sizes. Second aspect is the value or space priority of the packets, do all packets have the same space priority or different packets have different space priorities. We present two types of policies to achieve QoS goals for packets with different priorities: the push out scheme and the expelling scheme. For this work the scenario of packets of variable length is considered with two space priorities and main goal is to minimize the total weighted packet loss. Simulation and analytical studies show that, expelling policies can outperform the push out policies when it comes to offering variable QoS for packets of two different priorities and expelling policies also help improve the amount of admissible load. Some other comparisons of push out and expelling policies are also presented using simulations.

Keywords: Buffer Management Policy, Diffserv, ATM, Pushout Policy, Expeling Policy.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078927

References:

[1] Cidon, I.; Georgiadis, L.; Guerin, R.; Khamisy, A.; "Optimal buffer sharing" IEEE Journal on Selected Areas in Communications, ,Volume: 13 , Issue: 7 , Sept.1995 Pages:1229 - 1240.
[2] Sharma, S.;Viniotis,Y.; "Optimal buffer management policies for sharedbuffer ATM switches", IEEE/ACM Transactions on Networking ,Volume: 7 , Issue: 4 , Aug.1999 Pages:575 - 587
[3] M. Schwarz, Broadband Integrated Networks, Prentice Hall, Inc. 1996.
[4] F. A. Tobagi, "Fast Packet Switch Architectures for Broadband Integrated Services Digital Networks," Proc. IEEE, vol. 78, no. 1, Jan. 1990, pp. 13367.
[5] M. Devault, J. Cochennec, and M. Servel, "The Prelude ATD Experiment : Assessments and Future Prospects," IEEE JSAC, vol. 6, no. 9, Dec. 1988, pp. 157686.
[6] T. Kozaki et al., "32x32 Shared Buffer Type Switch VLSIs for BISDN," Proc. IEEE ICC '91, June 1991, pp. 7115.
[7] N. Endo et al., "Shared Buffer Memory Switch for an ATM Exchange," IEEE Trans. Commun., vol. 41, no. 1, Jan. 1993, pp. 23745.
[8] M. Irland, "Buffer Management in a Packet Switch," IEEE Trans. Commun., vol. COM-26, no. 3, Mar. 1978, pp. 32837.
[9] F. Kamoun and L. Kleinrock, "Analysis of Shared Finite Storage in a Computer Network Node Environment under General Traffic Conditions," IEEE Trans. Commun., vol. COM-28, no. 7, July 1980, pp. 9921003.
[10] G. Latouch, "Exponential Servers Sharing a Finite Storage: Comparison of Space Allocation Policies," IEEE Trans. Commun., vol. COM-28, no. 6, June 1980, pp. 9105.
[11] G. J. Foschini and B. Gopinath, "Sharing Memory Optimally," IEEE Trans. Commun., vol. COM-31, no. 3, Mar. 1983, pp. 35260.
[12] A. K. Choudhury and E. L. Hahne, "Dynamic Queue Length Thresholds for Shared-Memory Packet Switches," IEEE/ACM Trans. Commun., vol. 6, no. 2, Apr. 1998, pp. 13040.
[13] H. G. Perros and K. M. Elsayed, "Call Admission Control Schemes: A Review," IEEE Commun. Mag., Nov. 1996, pp. 8291.
[14] A. Erramilli and J. L. Wang, "Monitoring Packet Levels," Proc. IEEE GLOBECOM '94, vol. 1, Dec. 1994, pp. 27480.
[15] B. R. Collier and H. S. Kim, "Efficient Analysis of Shared Buffer Management Strategies in ATM Networks under Non-Uniform Bursty Traffic," Proc. IEEE Magazine, Mar. 1996, pp. 6718.
[16] A. K. Thareja and A. K. Agrawala, "On the Design of Optimal Policy for Sharing Finite Buffers," IEEE Trans. Commun., vol. COM-32, no. 6, June 1984, pp. 73740.
[17] I. Cidon et al., "Optimal Buffer Sharing," IEEE JSAC, vol. 13, no. 7, Sept. Page 17 1995, pp. 122939.
[18] A. Baiocchi et al., "Loss Performance Analysis of an ATM Multiplexer Loaded with High-Speed ON-OFF Sources," IEEE JSAC, vol. 9, no. 3, Apr. 1991, pp. 388-92.
[19] Cisco LightStream 1010 product documentation, available at http://www.cisco.com/univercd/cc/td/doc/pcat/
[20] S. X. Wei, E. J. Coyle, and M. T. Hsiao, "An Optimal Buffer Management Policy for High-Performance Packet Switching," Proc. IEEE GLOBECOM '91, vol. 2, Dec. 1991, pp. 92428.
[21] K. Nichols, V. Jacobson and L.Zhang, ``A Tow-bit Differentiated Services Architecture for the Internet", Internet Draft, July, 1999.
[22] Rajarshi Roy and S. S. Panwar, "Optimal Space Priority Policies for Shared Memory ATM Systems", Proceedings of the 35th Annual Allerton Conference on Communications, Control and Computing, pp.604-613, September-October, 1997.
[23] Rajarshi Roy and S. S. Panwar, "Efficient Buffer Sharing in Shared Memory ATM Systems With Space Priority Traffic", IEEE Communications Letters, Vol. 6, No. 4, April 2002.
[24] Analysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Conditions Kamoun, F.; Kleinrock, L.; IEEE Transactions on Communications,Volume: 28, Issue: 7 , Jul 1980, Pages:992 - 1003.
[25] G.J.Foschini and B.Gopinath, " Sharing Memory Optimally", IEEE Transactions on Communications,Vol. COM-31, No.3, March 1983.
[26] An optimal buffer management policy for high-performance packet switching Wei, S.X.; Coyle, E.J.; Hsiao, M.-T.T.; Global Telecommunications Conference, 1991. GLOBECOM '91. Pages:924 - 928 vol.2.
[27] L. Tassiulas, Y. C. Hung and S. S. Panwar, ``Optimal Buffer Control during congestion in an ATM network Node", IEEE/ACM Transactions on Networking, August 1994, Vol. 2, No. 4, pp. 374-386.
[28] "Competitive Algorithms for High-Speed QoS Switches,'' PhD Thesis, Tel Aviv University, 2004 by Dr. Alexander Kesselman.
[29] Kumar Padmanabh and Rajarshi Roy, "Expelling Policies for Shared Memory Fast Packet Switches with Variable size Packets of Multiple Priorities", IEEE, High Performance Switching and Routing HPSR- 2005.
[30] http://www.caida.org/analysis/AIX/plen_hist/
[31] H.J.Chao and N Uzun, "A VLSI sequencer chip for ATM traffic shaper and queue manager" IEEE Journal of Solid state circuits pp. 1634-1643, nov 1992.
[32] Internet Engineering task Force (IETF) http://www.ietf.org/