Expelling Policy Based Buffer Control during Congestion in Differentiated Service Routers

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.





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/