×

zbMATH — the first resource for mathematics

Flow control as a stochastic optimal control problem with incomplete information. (English) Zbl 1091.94003
Probl. Inf. Transm. 41, No. 2, 150-170 (2005); translation from Probl. Peredachi Inf. 2005, No. 2, 89-110 (2005).
Summary: A nonlinear stochastic control problem related to flow control is considered. It is assumed that the state of a link is described by a controlled hidden Markov process with a finite state set, while the loss flow is described by a counting process with intensity depending on a current transmission rate and an unobserved link state. The control is the transmission rate, and it has to be chosen as a nonanticipating process depending on the observation of the loss process. The aim of the control is to achieve the maximum of some utility function that takes into account losses of the transmitted information. Originally, the problem belongs to the class of stochastic control problems with incomplete information; however, optimal filtering equations that provide estimation of the current link state based on observations of the loss process allow one to reduce the problem to a standard stochastic control problem with full observations. Then a necessary optimality condition is derived in the form of a stochastic maximum principle, which allows us to obtain explicit analytic expressions for the optimal control in some particular cases. Optimal and suboptimal controls are investigated and compared with the flow control schemes used in TCP/IP (Transmission Control Protocols/Internet Protocols) networks. In particular, the optimal control demonstrates a much smoother behavior than the TCP/IP congestion control currently used.

MSC:
94A05 Communication theory
93C41 Control/observation systems with incomplete information
68M12 Network protocols
93E11 Filtering in stochastic control theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Jacobson, V., Congestion Avoidance and Control, in Proc. ACM SIGCOMM’88, New York: ACM, 1988, pp. 314–329.
[2] Allman, M., Paxson, V., and Stevens, W., TCP Congestion Control, RFC 2581, April, 1999. Available at http: //www.ietf.org/rfc/rfc2581.txt.
[3] Ramakrishnan, K., Floyd, S., and Black, D., The Addition of Explicit Congestion Notification (ECN) to IP, RFC 3168, September, 2001. Available at http://www.ietf.org/rfc/rfc3168.txt.
[4] Ramakrishnan, K. and Jain, R., A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with Connectionless Network Layer, ACM Trans. Comput. Syst., 1990, vol. 8, no.2, pp. 158–181. · doi:10.1145/78952.78955
[5] Altman, E., Avrachenkov, K., and Barakat, C., A Stochastic Model of TCP/IP with Stationary Random Losses, Comput. Commun. Rev., 2000, vol. 30, no.4, pp. 231–242. · doi:10.1145/347057.347549
[6] Altman, E., Avrachenkov, K., and Barakat, C., TCP in Presence of Bursty Losses, Perform. Eval., 2000, vol. 42, no.2–3, pp. 129–147. · Zbl 1052.68527 · doi:10.1016/S0166-5316(00)00027-4
[7] Barakat, C., TCP/IP Modeling and Validation, IEEE Network, 2001, vol. 15, no.3, pp. 38–47. · doi:10.1109/65.923939
[8] Altman, E., Avrachenkov, K.E., Barakat, C., and Dube, P., TCP over a Multi-state Markovian Path, in Performance and QoS of Next Generation Networking, New York: Springer, 2000, pp. 103–122.
[9] Davis, M.H.A., Markov Models and Optimization, London: Chapman & Hall, 1993. · Zbl 0780.60002
[10] Elliott, R.J., Aggoun, L., and Moore J.B., Hidden Markov Models: Estimation and Control, NewYork: Springer, 1995. · Zbl 0819.60045
[11] Fleming, W.H. and Rishel, R.W., Deterministic and Stochastic Optimal Control, Berlin: Springer, 1975. · Zbl 0323.49001
[12] Gilbert, E.N., Capacity of a Burst-Noise Channel, Bell Syst. Tech. J., 1960, vol. 39, no.5, pp. 1253–1265.
[13] Athuraliya, S. and Low, S., Optimization Flow Control with Newton-like Algorithm, Telecommun. Syst., 2000, vol. 15, no.3/4, pp. 345–358. · Zbl 1009.68946 · doi:10.1023/A:1019155231293
[14] Kelly, F.P., Mathematical Modelling of the Internet, Mathematics Unlimited: 2001 and Beyond, Engquist, B. and Schmid, W., Eds., Berlin: Springer, 2001, pp. 685–702.
[15] Kelly, F.P., Maulloo, A.K., and Tan, D.K.H., Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability, J. Oper. Res. Soc., 1998, vol. 49, no.3, pp. 237–252. · Zbl 1111.90313
[16] Kunniyur, S. and Srikant, R., End-to-End Congestion Control: Utility Functions, Random Losses and ECN Marks, IEEE/ACM Trans. Networking, 2003, vol. 11, no.5, pp. 689–702. · Zbl 05458707 · doi:10.1109/TNET.2003.818183
[17] Low, S.H. and Lapsley, D.E., Optimization Flow Control, I: Basic Algorithm and Convergence, IEEE/ACM Trans. Networking, 1999, vol. 7, no.6, pp. 861–874. · doi:10.1109/90.811451
[18] Massoulie, L. and Roberts, J., Bandwidth Sharing: Objectives and Algorithms, IEEE/ACM Trans. Networking, 2002, vol. 10, no.3, pp. 320–328. · Zbl 05458761 · doi:10.1109/TNET.2002.1012364
[19] Dumas, V., Guillemin, F., and Robert, P., A Markovian Analysis of Additive-Increase Multiplicative-Decrease (AIMD) Algorithms, Adv. in Appl. Probab., 2002, vol. 34, no.1, pp. 85–111. · Zbl 1002.60091 · doi:10.1239/aap/1019160951
[20] Gal’chuk, L.I., A Generalization of Girsanov’s Theorem on Substitution of Measures to the Case of Semi-Martingales with Jumps, Teor. Veroyatn. Primen., 1977, vol. 22, no.2, pp. 279–294 [Theory Probab. Appl. (Engl. Transl.), 1977, vol. 22, no. 2, pp. 271–285].
[21] Bremaud, P., Point Processes and Queues, Martingale Dynamics, New York: Springer, 1981. · Zbl 0478.60004
[22] Liptser, R.Sh. and Shiryaev, A.N., Statistics of Random Processes, New York: Springer, 1979. · Zbl 0556.60003
[23] Gikhman, I.I. and Skorokhod, A.V., Upravlyaemye sluchainye protsessy, Kiev: Nauk. Dumka, 1977. Translated under the title Controlled Stochastic Processes, New York: Springer, 1979.
[24] Yushkevich, A.A., Controlled Markov Models with Countable State Space and Continuous Time, Teor. Veroyatn. Primen., 1977, vol. 22, no.2, pp. 222–241 [Theory Probab. Appl. (Engl. Transl.), 1977, vol. 22, no. 2, pp. 215–235].
[25] Low, S.H., Paganini, F., and Doyle, J.C., Internet Congestion Control, IEEE Control Syst. Mag., 2002, vol. 22, no.1, pp. 28–43. · doi:10.1109/37.980245
[26] Miller, B.M. and Runggaldier, W.J., Kalman Filtering for Linear Systems with Coefficients Driven by a Hidden Markov Jump Process, Syst. Control Lett., 1997, vol. 31, no.2, pp. 93–102. · Zbl 0901.93069 · doi:10.1016/S0167-6911(97)00016-9
[27] Liptser, R.Sh. and Shiryaev, A.N., Teoriya Martingalov, Nauka, 1986. Translated under the title Theory of Martingales, Dordrecht: Kluwer, 1989.
[28] Wang, E. and Hajek, B., Stochastic Processes in Engineering Systems, New York: Springer, 1985. · Zbl 0545.60003
[29] Jacod, J. and Shiryaev, A.N., Limit Theorems for Stochastic Processes, Berlin: Springer, 1987. Translated under the title Predel’nye teoremy dlya sluchainykh protsessov, Moscow: Fizmatlit, 1994.
[30] Kabanov, Yu.M., On the Pontriagin Maximum Principle for SDEs with Poisson-type Driving Noise, Statistics and Control of Stochastic Processes. The Liptser Festschrift, Kabanov, Yu.M., Rozovskii, B.L., and Shiryaev, A.N., Eds., River Egde: World Scientific, 1997, pp. 173–190. · Zbl 0942.93045
[31] Tang, S. and Li, X., Necessary Conditions for Optimal Control of Stochastic Systems with Random Jumps, SIAM J. Control Optim., 1994, vol. 32, no.5, pp. 1447–1475. · Zbl 0922.49021 · doi:10.1137/S0363012992233858
[32] El Karoui, N. and Huang, S.-J., A General Result of Existence and Uniqueness of Backward Stochastic Differential Equations, in Backward stochastic differential equations (Paris, 1995–1996), Pitman Res. Notes Math. Ser., vol. 364, Harlow: Longman, 1997, pp. 27–36.
[33] Mathis, M., Semke, J., Mahdavi, J., and Ott, T., The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm, Comput. Commun. Rev., 1997, vol. 27, no.3, pp. 67–82. · doi:10.1145/263932.264023
[34] Padhye, J., Firoiu, V., Towsley, D., and Kurose, J., Modeling TCP Reno Performance: A Simple Model and Its Empirical Validation, IEEE/ACM Trans. Networking, 2000, vol. 8, no.2, pp. 133–145. · doi:10.1109/90.842137
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.