Gradient scheduling algorithm for fair delay guarantee in logarithmic pricing scenario

ABSTRACT

In this paper we propose a packet scheduling scheme for ensuring delay as a Quality of Service (QoS) requirement. For customers, fair service is given while optimizing revenue of the network service provider. Gradient type algorithm for updating the weights of a packet scheduler is derived from a revenue-based optimization problem in the logarithmic pricing scenario. Algorithm is simple to implement. We compared algorithm with optimal brute-force method. The weight updating procedure is independent on the assumption of the connection's statistical behavior, and therefore it is robust against erroneous estimates of statistics.

REFERENCES

• 1: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 2: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.1-12, Sep. 1989
• 3: Sally Floyd , Van Jacobson, Link-sharing and resource management models for packet networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.365-386, Aug. 1995 [doi>10.1109/90.413212]
• 4: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 5: Ion Stoica , Hui Zhang, Providing guaranteed services without per flow management, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.81-94, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 6: F. P. Kelly, "Charging and rate control for elastic traffic". European Transaction on Telecommunication., vol. 8, 1997, pp. 33--37.
• 7: Richard J. La , Venkat Anantharam, Utility-based rate control in the Internet for elastic traffic, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 8: Steven H. Low, Equilibrium bandwidth and buffer allocations for elastic traffics, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.373-383, June 2000 [doi>10.1109/90.851983]
• 9: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 10: Jyrki Joutsensalo, Timo Hämäläinen, Alexander Sayenko, and Mikko Pääkkönen, "QoS- and Revenue Aware Adaptive Scheduling Algorithm", Journal of Communications and Networks, Vol. 6, No. 1 March 2004, pp. 68--77.
• 11: Jyrki Joutsensalo, Timo Hämäläinen, Kari Luostarinen, and Jarmo Siltanen, "Adaptive Scheduling Method for Maximizing Revenue in Flat Pricing Scenario.", AEU - International Journal of Electronics and Communications, vol. 60, issue 2, February 2006, pp. 159--167.
• 12: UCB/LBNL/VINT. Network simulator ns-2. http://www.isi.edu/nsnam/ns.
• 13: A. Sayenko, "Adaptive scheduling for the QoS supported networks", Dissertation, University of Jyväskylä, 2005, 216 p.

INDEX TERMS

Keywords:
Quality of Service (QoS), bandwidth, delay, pricing, revenue optimization