nips nips2001 nips2001-177 nips2001-177-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Timothy X. Brown
Abstract: In packet switches, packets queue at switch inputs and contend for outputs. The contention arbitration policy directly affects switch performance. The best policy depends on the current state of the switch and current traffic patterns. This problem is hard because the state space, possible transitions, and set of actions all grow exponentially with the size of the switch. We present a reinforcement learning formulation of the problem that decomposes the value function into many small independent value functions and enables an efficient action selection.
[1] Boyan, J.A., Littman, M.L., “Packet routing in dynamically changing networks: a reinforcement learning approach,” in Cowan, J.D., et al., ed. Advances in NIPS 6, Morgan Kauffman, SF, 1994. pp. 671–678.
[2] Brown, T.X, Lui, K.H., “Neural Network Design of a Banyan Network Controller,” IEEE JSAC, v. 8, n. 8, pp. 1428–1438, Oct., 1990.
[3] Brown, T.X, Tong, H., Singh, S., “Optimizing admission control while ensuring quality of service in multimedia networks via reinforcement learning,” in Advances NIPS 11, ed. M. Kearns et al., MIT Press, 1999.
[4] Brown, T.X, Gabow, H.N., “Future Information in Input Queueing,” submitted to Computer Networks, April 2001.
[5] Gabor, Z., Kalmar, Z., Szepesvari, C., “Multi-criteria Reinforcement Learning,” International Conference on Machine Learning, Madison, WI, July, 1998. (¢1
[6] J. Hopcroft and R. Karp, “An algorithm for maximum matchings in bipartite graphs”, SIAM J. Computing 2, 4, 1973, pp 225-231.
[7] Marbach, P., Mihatsch, M., Tsitsiklis, J.N., “Call admission control and routing in integrated service networks using neuro-dynamic programming,” IEEE J. Selected Areas in Comm., v. 18, n. 2, pp. 197–208, Feb. 2000.
[8] McKeown, N., Anantharam, V., Walrand, J., “Achieving 100% Throughput in an Input-Queued Switch,” Proc. of IEEE INFOCOM ’96, San Francisco, March 1996.
[9] Park, Y.-K., Lee, G., “NN Based ATM Scheduling with Queue Length Based Priority Scheme,” IEEE J. Selected Areas in Comm., v. 15, n. 2 pp. 261–270, Feb. 1997.
[10] Pattavina, A., Switching Theory: Architecture and Performance in Broadband ATM Networks, John Wiley and Sons, New York, 1998.
[11] Singh, S.P., Bertsekas, D.P., “Reinforcement learning for dynamic channel allocation in cellular telephone systems,” in Advances in NIPS 9, ed. Mozer, M., et al., MIT Press, 1997. pp. 974–980.
[12] Sutton, R.S., Barto, A.G., Reinforcement Learning: an Introduction, MIT Press, 1998.
[13] Tarjan, R.E., Data Structures and Network Algorithms, Soc. for Industrial and Applied Mathematics, Philidelphia, 1983.