微信服务号

微信订阅号

2025-4-3- 21
Home > Archive>Volume 20, Issue 2, 2009 >415-424
PDF HTML XML Export Cite reminder
Calculation on the Bisection Width of H-Torus Topology
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [15]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Two methods are presented to calculate the lower bound and upper bound on the bisection width of H-Torus topology. These two methods can also be applied to the 2D Torus topology. A method is presented to calculate the exact bisection width for H-Torus too. But this method has unacceptable complexity and can only be accepted with small scale. It is shown that H-Torus topology has larger bisection width. Regarding precision, the lower bound and upper bound introduced in this paper are greatly improved. This result strongly supports the design of scalable routers.

    Reference
    [1] Odlyzko AM. Internet traffic growth: Sources and implications. In: Dingel BB, ed. Proc. of the SPIE Optical Transmission Systems and Equipment for WDM Networking II. Orlando: SPIE, 2003. 1-15.
    [2] Keslassy I, Chuang ST, Yu K, Miller D, Horowitz M, Solgaard O, McKeown N. Scaling internet routers using optics. In: Feldmann A, ed. Proc. of the Special Interest Group on Data Communication (SIGCOMM). Karlsruhe: ACM Press, 2003. 189-200.
    [3] Chiussi FM, Francini A. Scalable electronic packet switches. IEEE Journal on Selected Areas in Communications, 2003,21(4): 486-500.
    [4] Chang CS, Lee DS, Jou YS. Load balanced Birkhoff-von Neumann switches, part I: One-Stage buffering. Computer Communications, 2002,25(6):611-622.
    [5] Dally, WJ. Performance analysis of k-ary n-cube interconnection networks. IEEE Trans. on Computers, 1990,39(6):775-785.
    [6] Dally WJ. Scalable switching fabrics for Internet routers. http://www.avici.com/technology/whitepapers/TSRfabric-WhitePaper.pdf
    [7] Zhao YJ, Yue ZH, Wu JP, Zhang XP. Topological properties and routing algorithms in cellular router. In: Proc. of the Int’l Conf. on Networking and Services (ICNS 2006). 2006. 101-106.
    [8] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company, 1979.
    [9] Bezrukov S, Els?sser R, Monien B, Preis R, Tillich JP. New spectral lower bounds on the bisection width of graphs. Theoretical Computer Science, 2004,320(2-3):155-174.
    [10] Mans B, Shparlinski I. Bisecting and gossiping in circulant graphs. In: Farach-Colton M, ed. Proc. of the LATIN 2004. Berlin, Heidelberg: Springer-Verlag, 2004. 589-598.
    [11] Chen MS, Shin KG, Kandlur DD. Addressing, routing, and broadcasting in hexagonal mesh multiprocessors. IEEE Trans. on Computers, 1990,39(1):10-18.
    [12] Sullivan H, Bashkow TR. A large scale, homogeneous, fully distributed parallel machine, I. In: Proc. of the 4th Annual Symp. on Computer Architecture. New York: IEEE, 1977. 105-117.
    [13] Kalman D, White JE. Polynomial equations and circulant matrices. American Mathematical Monthly, 2001,108(9):821-841.
    [14] Lu KC. Combinatorics. 2nd ed., Beijing: Tsinghua University Press, 1991. 21-22 (in Chinese). 附中文参考文献:
    [14] 卢开澄.组合数学.第2版,北京:清华大学出版社, 1991.21-22.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

乐祖晖,赵有健,吴建平,张小平. H-Torus拓扑结构等分带宽的计算.软件学报,2009,20(2):415-424

Copy
Share
Article Metrics
  • Abstract:5185
  • PDF: 7538
  • HTML: 0
  • Cited by: 0
History
  • Received:December 25,2006
  • Revised:September 06,2007
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2032470Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063