雙扭立方體的拓蹼特性

Abstract

在連結網路中網路架構的拓蹼特性是決定這個網路執行效率好壞的一個重 要考量因素. 在選擇一個連結網路時我們都會考慮到一些參數, 例如 : 直徑(diameter), 度數(degree), 連通性(connectivity)以及對稱性( symmetry). 而超立方體(Hypercube)是一個很受歡迎的連結網路由於它具 有很高的連通性和對稱性, 但是超立方體的一個缺點是它的直徑是隨著 n 成線性增加的. 而雙扭立方體(Twisted cubes), 是由 Hilbers, Koopman 及 Vande Snepscheut 所提出來的一種超立方體的變形體, 它 有著和超立方體一樣多的點和線.這種雙扭立方體的架構是將原先在超立 方體上某些線的接法如果滿足某些規則時, 則把這些線雙扭(twist), 因 此雙扭立方體可以保持和超立方體一樣多的線. 許多有關於雙扭立方體的 其它特性已經在其它文章中被提出來了. 我們知道超立方體的直徑, 廣域直徑(wide diameter)以及缺陷直徑(fault diameter)分別是 n, n+1 以及 n+1. 而雙扭立方體的直徑已經被證明是 ceiling(n+1/2), 幾 乎是超立方體的一半. 在這篇論文中, 我們要證明雙扭立方體的廣域直 徑是 ceiling(n/2)+2 以及缺陷直徑也是 ceiling(n/2)+2,而這些參數 的值幾乎是超立方體所相對應值的一半. Network topological is a crucial factor of interconnection network since itdetermines the performance of the network. Many factors such as diameter,degree, connectivity, and symmetry are considered while choosing aninterconnection network. The binary hypercube, is one of the most populartopological of interconnection network because of its high connectivity andsymmetry. One drawback of hypercube is its diameter grows linearly withrespect to n. Many variations of hypercube have been proposed to improve thisdrawback. Twisted cube, is one of variations of hypercubes, with the samenumber of nodes and edges. This topology is proposed by Hilbers, Koopman, andvan de Snepscheut. This topology is to remove some links from the hypercubeand to replace them with links that span two dimensions in such a manner thatthe total number of links are conserved. Many topological properties of thisvariation are studied in literatures. It is known that the diameter, widediameter, and fault diameter of hypercube are n, n+1, and n+1 respectively.It has been shown that the diameter of twisted cube is ceiling(n+1/2), almosta factor of 2 improvement. In this paper, we prove that the connectivity oftwisted cube is n and the wide diameter of twisted cube is ceiling(n/2)+2,fault diameter of twisted cube is ceiling(n/2)+2. Thus, all these parametersare almost the half of the corresponding parameters of the hypercube's.