[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Optimal layouts on a chain ATM network

Extended abstract

  • Session 9. Chair: Jan van Leeuwen
  • Conference paper
  • First Online:
Algorithms — ESA '95 (ESA 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 979))

Included in the following conference series:

  • 158 Accesses

Abstract

We study a routing problem which occurs in high-speed (ATM) networks, termed the “one-to-many virtual path layout problem” on chain networks. This problem is essentially a tree embedding problem on a chain host graph. We present four performance measures to the quality of such an embedding which have practical implications, and find optimal solutions for each of them. We first show that the search can be restricted to the class of layouts with no crossovers. Given bounds on the load ℓ and number of hops h in a layout, we then present a family of ordered trees \(\mathcal{T}\)(l, h), within which an optimal solution can be found (if one exists at all); this holds for either the worst-case or average-case measures, and for a chain of length n, with n ≤ \(\left( {\begin{array}{*{20}c}{l + h} \\l \\\end{array} } \right)\). For the worstcase measures these trees are used in characterizing, constructing, and proving the optimality of the solutions. For the average-case measures polynomial dynamic programming algorithms are presented which find optimal solutions for all cases.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. B. Awerbuch, A. Bar-Noy, N. Linial, and D. Peleg. Compact distributed data structures for adaptive routing. In 21st Symp. on Theory of Computing, pages 479–489, 1989.

    Google Scholar 

  2. B. Awerbuch and D. Peleg. Routing with polynomial communicationspace tradeoff. SIAM Journal on Discrete Math, 5(2):151–162, May 1992.

    Article  Google Scholar 

  3. S. Ahn, R.P. Tsang, S.R. Tong, and D.H.C. Du. Virtual path layout design on ATM networks. In IEEE Infocom'94, pages 192–200, 1994.

    Google Scholar 

  4. H.L. Bodlaender, G. Tel, and N. Santoro. Trade-offs in non-reversing diameter. Nordic Journal of Computing, 1:111–134, 1994.

    Google Scholar 

  5. I. Cidon, O. Gerstel, and S. Zaks. A scalable approach to routing in ATM networks. In G. Tel and P.M.B. Vitányi, editors, The 8th International Workshop on Distributed Algorithms (LNCS 857), pages 209–222, Terschelling, The Netherlands, October 1994.

    Google Scholar 

  6. T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1989.

    Google Scholar 

  7. R. Cohen and A. Segall. Connection management and rerouting in ATM networks. In IEEE Infocom'94, pages 184–191, 1994.

    Google Scholar 

  8. G.N. Frederickson and R. Janardan. Separator-based strategies for efficient message routing. In 27th Symp. on Foundations of Computer Science, pages 428–437, 1986.

    Google Scholar 

  9. R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, 1989.

    Google Scholar 

  10. O. Gerstel and A. Segall. Dynamic maintenance of the virtual path layout. In IEEE Infocom'95, pages 330–337, April 1995.

    Google Scholar 

  11. O. Gerstel and S. Zaks. The virtual path layout problem in fast networks. In The 13th ACM Symp. on Principles of Distributed Computing, pages 235–243, Los Angeles, USA, August 1994.

    Google Scholar 

  12. R. Händler and M.N. Huber. Integrated Broadband Networks: an introduction to ATM-based networks. Addison-Wesley, 1991.

    Google Scholar 

  13. ITU recommendation. I series (B-ISDN), Blue Book, November 1990.

    Google Scholar 

  14. L. Kleinrock and F. Kamoun. Optimal clustering structures for hierarchical topological design of large computer networks. Networks, 10:221–248, 1980.

    Google Scholar 

  15. F.Y.S. Lin and K.T. Cheng. Virtual path assignment and virtual circuit routing in ATM networks. In IEEE Globecom '93, pages 436–441, 1993.

    Google Scholar 

  16. D. Peleg and E. Upfal. A tradeoff between space and efficiency for routing tables. In 20th Symp. on Theory of Computing, pages 43–52, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Technion, 32000, Haifa, Israel

    Ornan Gerstel & Shmuel Zaks

  2. Department of Applied Mathematics and Computer Science, The Weizmann Institute, 76100, Rehovot, Israel

    Avishai Wool

Authors
  1. Ornan Gerstel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Avishai Wool
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shmuel Zaks
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Paul Spirakis

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gerstel, O., Wool, A., Zaks, S. (1995). Optimal layouts on a chain ATM network. In: Spirakis, P. (eds) Algorithms — ESA '95. ESA 1995. Lecture Notes in Computer Science, vol 979. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60313-1_167

Download citation

  • DOI: https://doi.org/10.1007/3-540-60313-1_167

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60313-9

  • Online ISBN: 978-3-540-44913-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics