Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

An Efficient Construction of Node Disjoint Paths in OTIS Networks

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4847))

  • 934Accesses

Abstract

We investigate the problem of constructing the maximal number of node disjoint paths between two distinct nodes in Swapped/OTIS networks. A general construction of node disjoint paths in any OTIS network with a connected basis network is presented, which is independent of any construction of node disjoint paths in its basis network. This general construction is effective and efficient, which can obtain desirable node disjoint paths of length at mostD + 4 inO(Δ2 + Δf(N1/2)) time if the basis network of sizen has a shortest routing algorithm of time complexityO(f(n)), whereD,Δ andN are, respectively, the diameter, the degree and the size of the OTIS network. Further, for OTIS networks with maximally fault tolerant basis networks, we give an improved version of a conventional construction of node disjoint paths by incorporating the above general construction. Finally, we show the effectiveness and efficiency of these constructions applied to OTIS-Hypercubes.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Chatterjee, S., Pawlowski, S.: All Optical Networks. Comm. ACM 42(6), 74–83 (1999)

    Article  Google Scholar 

  2. Day, K.: Optical Transpose k-ary n-cube Networks. J. Systems Architecture 50, 697–705 (2004)

    Article  Google Scholar 

  3. Day, K., Al-Ayyoub, A.: Topological Properties of OTIS-Networks. IEEE Trans. Parallel and Distributed Systems 14(4), 359–366 (2002)

    Article MathSciNet  Google Scholar 

  4. Hsieh, H.-J., Duh, D.-R.: Constructing Node-Disjoint Paths in Enhanced Pyramid Networks. In: Jesshope, C., Egan, C. (eds.) ACSAC 2006. LNCS, vol. 4186, pp. 380–386. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  5. Jana, P.K.: Polynomial Interpolation and Polynomial Root Finding on OTIS-Mesh, Parallel Computing 32, 301–312 (2006)

    Article MathSciNet  Google Scholar 

  6. Kim, J., Moh, S., Chung, I., Yu, C.: Robust Multipath Routing to Exploit Maximally Disjoint Paths for Wireless Ad Hoc Networks. In: Shen, H.T., Li, J., Li, M., Ni, J., Wang, W. (eds.) Advanced Web and Network Technologies, and Applications. LNCS, vol. 3842, pp. 306–309. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  7. Marsden, G., Marchand, P., Harvey, P., Esener, S.: Optical Transpose Interconnection System Architecture. Optical Letters 18, 1083–1085 (1993)

    Article  Google Scholar 

  8. Osterloh, A.: Sorting on the OTIS-Mesh. In: Proc. 14th Int’l Parallel and Distributed Processing Symp., pp. 269–274 (2000)

    Google Scholar 

  9. Parhami, B.: Swapped Interconnection Networks: Topological, Performance, and Robustness Attributes. J. Parallel and Distributed Computing 65, 1443–1452 (2005)

    Article MATH  Google Scholar 

  10. Rajasekaran, S., Sahni, S.: Randomized Routing, Selection, and Sorting on the OTIS-Mesh. IEEE Trans. Parallel and Distributed Systems 9(9), 833–840 (1998)

    Article  Google Scholar 

  11. Rayn, J.: WDM: North American Development Trend. IEEE Comm. 32(2), 40–44 (1998)

    Article  Google Scholar 

  12. Saad, Y., Schultz, M.: Topological properties of hypercubes. IEEE Transactions on Computers 37, 867–871 (1988)

    Article  Google Scholar 

  13. Wang, C.-F., Sahni, S.: Image Processing on the OTIS-Mesh Optoelectronic Computer. IEEE Trans. Parallel and Distributed Systems 11(2), 97–109 (2000)

    Article  Google Scholar 

  14. Wang, C.-F., Sahni, S.: Matrix Multiplication on the OTIS-Mesh Optoelectronic Computer. IEEE Trans. Computers 50(7), 635–646 (2001)

    Article  Google Scholar 

  15. West, D.B.: Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs, NJ (2001)

    Google Scholar 

  16. Wu, R.-Y., et al.: Node-disjoint paths in hierarchical hypercube networks. Information Sciences 177, 4200–4207 (2007)

    Article MATH MathSciNet  Google Scholar 

  17. Yeh, C.-H., Parhami, B.: Swapped Networks: Unifying the Architectures and Algorithms of a Wide Class of Hierarchical Parallel Processors. In: Proc. Int’l Conf. Parallel and Distributed Systems, pp. 230–237 (1996)

    Google Scholar 

  18. Zane, F., Marchand, P., Paturi, R., Esener, S.: Scalable Network Architectures Using the Optical Transpose Interconnection System (OTIS). J. Parallel and Distributed Computing 60(5), 521–538 (2000)

    Article MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, South China University of Technology, Guangzhou 510641, China

    Weidong Chen & Wenjun Xiao

  2. Department of Computer Science, South China Normal University, Guangzhou 510631, China

    Weidong Chen

  3. Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA 93106-9560, USA

    Behrooz Parhami

Authors
  1. Weidong Chen

    You can also search for this author inPubMed Google Scholar

  2. Wenjun Xiao

    You can also search for this author inPubMed Google Scholar

  3. Behrooz Parhami

    You can also search for this author inPubMed Google Scholar

Editor information

Ming Xu Yinwei Zhan Jiannong Cao Yijun Liu

Rights and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Chen, W., Xiao, W., Parhami, B. (2007). An Efficient Construction of Node Disjoint Paths in OTIS Networks. In: Xu, M., Zhan, Y., Cao, J., Liu, Y. (eds) Advanced Parallel Processing Technologies. APPT 2007. Lecture Notes in Computer Science, vol 4847. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76837-1_22

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp