Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-19T09:09:35.240Z Has data issue: false hasContentIssue false
  • English
  • Français

Reordering heuristics for routing in communications networks

Published online by Cambridge University Press:  14 July 2016

Donald M. Topkis
Donald M. Topkis*
Affiliation:
AT&T Bell Laboratories
*
∗Present address: Graduate School of Administration, University of California, Davis, CA 95616, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Move-to-front and move-to-back heuristics are considered for adaptively reordering routing tables in communications networks. Limiting properties are established for Markov chain models of these heuristics. The limiting distributions of the number of path attempts per call for the two heuristics and for a fixed random permutation are stochastically ordered.

Keywords

MARKOV CHAIN MODELS
Type
Research Papers
Information
Journal of Applied Probability , Volume 23 , Issue 1 , March 1986 , pp. 130 - 143
Copyright
Copyright © Applied Probability Trust 1986 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Anderson, E. J., Nash, P. and Weber, R. R. (1982) A counterexample to a conjecture on optimal list ordering. J. Appl. Prob. 19, 730–732.Google Scholar
[2] Ash, G. R., Kafker, A. H. and Krishnan, K. R. (1981) Servicing and real-time control of networks with dynamic routing. Bell System Tech. J. 60, 1821–1845.Google Scholar
[3] Bentley, J. L. and Cole, C. (1982) Worst-case analyses of self-organizing sequential search heuristics. Proc. 20th Allerton Conf. on Comm., Control, and Comput. , 452–461.Google Scholar
[4] Bitner, J. R. (1979) Heuristics that dynamically organize data structures. SIAM J. Comput. 8, 82–110.CrossRefGoogle Scholar
[5] Burville, P. J. and Kingman, J. F. C. (1973) On a model for storage and search. J. Appl. Prob. 10, 697–701.Google Scholar
[6] Gonnet, G. H., Munro, J. I. and Suwanda, H. (1981) Exegesis of self-organizing linear search. SIAM J. Comput. 10, 613–637.CrossRefGoogle Scholar
[7] Heggestad, H. M. (1980) A flexible routing algorithm for the future Defense Switched Network. Proc. IEEE Natl. Telecomm. Conf. , 74.3.1–74.3.5.Google Scholar
[8] Hendricks, W. J. (1972) The stationary distribution of an interesting Markov chain. J. Appl. Prob. 9, 231–233.CrossRefGoogle Scholar
[9] Hendricks, W. J. (1976) An account of self-organizing systems. SIAM J. Comput. 5, 715–723.CrossRefGoogle Scholar
[10] Heyman, D. P. and Sobel, M. J. (1982) Stochastic Models in Operations Research , Vol. I. McGraw-Hill, New York.Google Scholar
[11] Kan, Y. C. and Ross, S. M. (1980) Optimal list order under partial memory constraints. J. Appl. Prob. 17, 1004–1015.Google Scholar
[12] Knuth, D. E. (1973) The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley, Reading, Ma.Google Scholar
[13] Lehmann, E. L. (1955) Ordered families of distributions. Ann. Math. Statist. 26, 399–419.Google Scholar
[14] Mccabe, J. (1965) On serial files with relocatable records. Operat. Res. 13, 609–618.CrossRefGoogle Scholar
[15] Meketon, M. S. and Topkis, D. M. (1983) Adaptive routing for damaged networks. Proc. IEEE Mil. Comm. Conf. , 282–288.Google Scholar
[16] Nelson, P. R. (1979) A prediction interval search scheme for the move-to-front replacement algorithm. J. Inst. Maths. Appl. 24, 231–236.CrossRefGoogle Scholar
[17] Nelson, P. R. (1982) The transposition replacement policy with a partial memory. J. Appl. Prob. 19, 733–736.Google Scholar
[18] Rivest, R. (1976) On self-organizing sequential search heuristics. Comm. ACM 19, 63–67.Google Scholar
[19] Sleator, D. D. and Tarjan, R. E. (1985) Amortized efficiency of list update and paging rules. Comm. ACM 28, 202–208.Google Scholar
[20] Tenenbaum, A. (1978) Simulations of dynamic sequential search algorithms. Comm. ACM 9, 790–791.CrossRefGoogle Scholar
[21] Tenenbaum, A. M. and Nemes, R. M. (1982) Two spectra of self-organizing sequential search algorithms. SIAM J. Comput. 11, 557–566.Google Scholar
[22] Tsetlin, M. L. (1963) Finite automata and models of simple forms of behavior. Russian Math. Surveys 18, 1–27.CrossRefGoogle Scholar