Narrowing the Search for Optimal Call-Admission Policies Via a Nonlinear Stochastic Knapsack Model

详细信息    查看全文

• 作者：Marco Cello (1)
  Giorgio Gnecco (2) (3)
  Mario Marchese (1)
  Marcello Sanguineti (3)
  
  1. Department of Telecommunications ; Electronic ; Electric ; and Naval Engineering (DITEN) ; University of Genoa ; Via Opera Pia ; 11-16145聽 ; Genova ; Italy
  2. Institute for Advanced Studies (IMT) ; Piazza S. Ponziano ; 6-55100聽 ; Lucca ; Italy
  3. Department of Computer Science ; Bioengineering ; Robotics ; and Systems Engineering (DIBRIS) ; University of Genoa ; Via Opera Pia ; 13-16145聽 ; Genova ; Italy
  
• 关键词：Stochastic knapsack ; Nonlinear constraints ; Call admission control ; Coordinate ; convex policies ; Structural properties ; 90B15 ; 90B18 ; 90C10 ; 90C27 ; 68M10
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：164
• 期：3
• 页码：819-841
• 全文大小：862 KB
• 参考文献：1. Ross, K, Tsang, D (1989) The stochastic knapsack problem. IEEE Trans. Commun. 37: pp. 740-747 CrossRef
  2. Kleywegt, AJ, Papastavrou, JD (2001) The dynamic and stochastic knapsack problem with random sized items. Oper. Res. 49: pp. 26-41 CrossRef
  3. Dean, BC, Goemans, MX, Vondrak, J (2008) Approximating the stochastic knapsack problem: the benefit of adaptivity. Math. Oper. Res. 33: pp. 945-964 CrossRef
  4. Keller, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin Heidelberg (2004)
  5. Kesidis, G, Walrand, J, Chang, CS (1993) Effective bandwidths for multiclass Markov fluids and other ATM sources. IEEE ACM Trans. Netw. 1: pp. 424-428 CrossRef
  6. Ross, K.W.: Multiservice Loss Models for Broadband Telecommunication Networks. Springer, New York (1995)
  7. Aswakul, C, Barria, J (2002) Analysis of dynamic service separation with trunk reservation policy. IEE Proc. Commun. 149: pp. 23-28 CrossRef
  8. Guerin, R, Ahmadi, H, Naghshineh, M (1991) Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE J. Sel. Areas Commun. 9: pp. 968-981 CrossRef
  9. Tse, D, Gallager, R, Tsitsiklis, J (1995) Statistical multiplexing of multiple time-scale Markov streams. IEEE J. Sel. Areas Commun. 13: pp. 1028-1038 CrossRef
  10. Javidi, T, Teneketzis, D (2003) An approach to connection admission control in single-hop multiservice wireless networks with QoS requirements. IEEE Trans. Veh. Technol. 52: pp. 1110-1124 CrossRef
  11. Cello, M., Gnecco, G., Marchese, M., Sanguineti, M.: Structural properties of optimal coordinate-convex policies for CAC with nonlinearly-constrained feasibility regions. In: Proceedings of IEEE INFOCOM鈥?1 Mini-Conf., pp. 466鈥?70 (2011)
  12. Cello, M, Gnecco, G, Marchese, M, Sanguineti, M (2011) CAC with nonlinearly-constrained feasibility regions. IEEE Commun. Lett. 15: pp. 467-469 CrossRef
  13. Dasylva, A., Srikant, R.: Bounds on the performance of admission control and routing policies for general topology networks with multiple call classes. In: Proceedings of IEEE INFOCOM鈥?9, vol. 2, pp. 505鈥?12 (1999)
  14. Cello, M, Gnecco, G, Marchese, M, Sanguineti, M (2013) Optimality conditions for coordinate-convex policies in CAC with nonlinearly feasibility boundaries. IEEE ACM Trans. Netw. 21: pp. 1363-1377 CrossRef
  15. H枚rmander, L.: Notions of Convexity. Birk盲user, Boston (2007)
  16. Likhanov, N., Mazumdar, R.R., Theberge, F.: Providing QoS in large networks: Statistical multiplexing and admission control. In: Boukas, E., Malhame, R. (eds.) Analysis, Control and Optimization of Complex Dynamic Systems, pp. 137鈥?67. Kluwer (2005)
  17. Barnhart, C., Wieselthier, J., Ephremides, A.: An approach to voice admission control in multihop wireless networks. In: Proceedings of IEEE INFOCOM鈥?3, vol. 1, pp. 246鈥?55 (1993)
  18. Bolla, R, Davoli, F, Marchese, M (1997) Bandwidth allocation and admission control in ATM networks with service separation. IEEE Commun. Mag. 35: pp. 130-137 CrossRef
  19. Little, JDC (1961) A proof for the queuing formula: $$l= \lambda w$$ l = 位 w. Oper. Res. 9: pp. 383-387 CrossRef
  20. Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)
  21. Comtet, L.: Advanced Combinatorics: the Art of Finite and Infinite Expansions. Kluwer, Amsterdam (1974)
  
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878

文摘

Call admission control with two classes of users is investigated via a nonlinear stochastic knapsack model. The feasibility region represents the subset of the call space, where given constraints on the quality of service have to be satisfied. Admissible strategies are searched for within the class of coordinate-convex policies. Structural properties that the optimal policies belonging to such a class have to satisfy are derived. They are exploited to narrow the search for the optimal solution to the nonlinear stochastic knapsack problem that models call admission control. To illustrate the role played by these properties, the numbers of coordinate-convex policies by which they are satisfied are estimated. A graph-based algorithm to generate all such policies is presented.