Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An analytical approach to the dynamic topology problem

  • Published:
Telecommunication Systems Aims and scope Submit manuscript

Abstract

Currently, it is possible to modify (say, hourly) the topology of a data communications network by adding or deleting network links and/or by increasing or decreasing bandwidth on existing links in response to changing traffic loads and/or projected network conditions. The intent of this paper is to study a Markov decision process (MDP) model of the dynamic topology problem (DTP), the problem of activating and/or deleting links, as a function of the current traffic in the network and of the most recent network topology design. We present a decomposition of this model and structural results for the decomposition. The decomposition and structural results enhance the tractability of procedures for determining optimal link control policies. A numerical example is used to illustrate these results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. E. Altman and P. Nain, Optimal control of theM/G/1 queue with repeated vacations of the server, IEEE Trans. Auto. Control 38(1993)1766–1775.

    Article  Google Scholar 

  2. D. Bertsekas,Dynamic Programming: Deterministic and Stochastic Models (Prentice-Hall, Englewood Cliffs, 1987).

    Google Scholar 

  3. R.M. Bournas, F.J. Butler and D. Teneketzis, Optimal flow control allocation policies in communications networks with multiple message classes, IEE Trans. Auto. Control 38(1993) 390–403.

    Article  Google Scholar 

  4. R.M. Bournas, F.J. Butler and D. Teneketzis, Properties of optimal hop-by-hop allocation policies in networks with multiple transmitters and linear equal holding costs, IEEE Trans. Auto. Control 36(1991)1450–1463.

    Article  Google Scholar 

  5. C. Derman, On optimal replacement rules when changes of state are Markovian, in:Mathematical Optimization Techniques, ed. R. Bellman (University of California Press, Berkeley, CA, 1963).

    Google Scholar 

  6. R.-H. Hwang, Routing in high-speed networks, Ph.D. Dissertation, Department of Computer Science, University of Massachusetts, Amherst (1993).

    Google Scholar 

  7. L. Kleinrock,Queueing Systems Volume II: Computer Applications (Wiley, 1976).

  8. L. LeBlanc and J.H. Harder, Optimization models for design and routing in wide-area data-communication networks, Stud. Locational Anal. 6(1994)3–18.

    Google Scholar 

  9. L. LeBlanc, Design and operation of packet-switched networks with uncertain message requirements, IEEE Trans. Commun. 38(1990)1223–1230.

    Article  Google Scholar 

  10. L. LeBlanc and R. Simmons, Continuous models for capacity design of large packet-switched telecommunications networks, ORSA J. Comp. 1(1989)271–286.

    Google Scholar 

  11. A.M. Makowski and A. Shwartz, On constrained optimization of the Klimov network and related Markov decision processes, IEEE Trans. Auto. Control 38(1993)354–359.

    Article  Google Scholar 

  12. R.L. Moose, Modeling networks with dynamic topologies, ORSA J. Comp. 1(1988)223–231.

    Google Scholar 

  13. R.L. Moose and R.E. Nance, Link models for networks with dynamic topologies, Technical Report SRC 87-006, Systems Research Center, Virginia Polyrechnic Institute and State University (1987).

  14. R.E. Nance and R.L. Moose, Link capacity assignment in dynamic hierarchical networks, Comp. Networks and ISDN Syst. 15(1988)189–202.

    Article  Google Scholar 

  15. M.D. Noakes, J.B. Cain, J.W. Nieto and E.L. Althouse, An adaptive link assignment algorithm for dynamically changing topologies, IEEE Trans. Commun. 41(1993)694–706.

    Article  Google Scholar 

  16. K.W. Ross and D.H.K. Tsang, Optimal circuit access policies in an ISDN environment: A Markov decision approach, IEEE Trans. Commun. 37(1989)934–939.

    Article  Google Scholar 

  17. G.N. Rouskas and M.H. Ammar, Dynamic reconfiguration in multihop WDM networks,Proc. Photonics, 1993.

  18. J. Shor and T.G. Robertazzi, Traffic sensitive algorithms and performance measures for the generation of self-organizing radio network schedules, IEEE Trans. Commun. 41(1993)16–21.

    Article  Google Scholar 

  19. C.C. White and K. Schlussel, Suboptimal design for large-scale multi-module systems, Oper. Res. 29(1981)865–875.

    Google Scholar 

  20. C.C. White and K. Schlussel, Optimal replacement policies for completely observed multi-component systems,Proc. Southeastcon, Williamsburg, VA, 1977.

  21. C.C. White and D.J. White, Markov decision processes, Euro. J. Oper. Res. 39(1989)1–16.

    Article  Google Scholar 

  22. I.S. Gopal and T.E. Stern, Optimal call blocking policies in an integrated services environment,Conf. Inform. Sci. Syst., Johns Hopkins University, 1983, pp. 383–388.

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Operations Engineering, University of Michigan, 48109-2117, Ann Arbor, MI, USA

    Chelsea C. White III

  2. Department of Systems Engineering, University of Virginia, Thornton Hall, 22903-2442, Charlottesville, VA, USA

    Edward A. Sykes

  3. U.S. Army Foreign Science and Technology Center, 220 Seventh Street NE, 22903, Charlottesville, VA, USA

    Janet A. Morrow

Authors
  1. Chelsea C. White III
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edward A. Sykes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Janet A. Morrow
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research supported by ARO Contract No. DAAG-29-85-K0089, NSF Grant No. ECS-8708183, and DCA Contract No. DCA 100-89-C-0031.

Rights and permissions

Reprints and permissions

About this article

Cite this article

White, C.C., Sykes, E.A. & Morrow, J.A. An analytical approach to the dynamic topology problem. Telecommunication Systems 3, 397–413 (1994). https://doi.org/10.1007/BF02110313

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02110313

Keywords

Search

Navigation