完整後設資料紀錄
DC 欄位語言
dc.contributor.author蔡宗翰en_US
dc.contributor.authorTsai, Tsung-Hanen_US
dc.contributor.author譚建民en_US
dc.contributor.author陳玉專en_US
dc.contributor.authorTan, Jimmy J.M.en_US
dc.contributor.authorChen, Y-Chuangen_US
dc.date.accessioned2015-11-26T00:55:32Z-
dc.date.available2015-11-26T00:55:32Z-
dc.date.issued2015en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT079755878en_US
dc.identifier.urihttp://hdl.handle.net/11536/125847-
dc.description.abstract拓撲性質對於分析網絡之間互連研究已成為是一種普及和重要的領域, n維超立方體是用於網絡間互連最廣泛討論的拓撲結構中的一種,並且通常包括在介紹的基本原理和網絡設計的方法,交換超立方體EH(s, t) 是具有略超過超立方體的一半的邊之一個新的變型,並保持該超立方體的若干有價值且所期望的性質,例如:小直徑,泛偶圈和超級連通性。 在本篇論文當中,我們研究了在交換超立方體EH(s, t) 中的寬直徑和損壞直徑,我們建構出在交換超立方體EH(s, t) (3 ≤ s ≤ t) 中任何兩點之平行路由會產生出s+1 (或 t+1) 條不相交的路徑,而且也證明其(s + 1)-寬直徑和s-損壞直徑都是s + t + 3。除此之外,我們提出了一個方法是針對交換超立方體EH(s, t) 從起始點至目標點的最短路徑路由演算法,其時間複雜度為O(n),其中n = s +t+1且1 ≤ s ≤ t。然後,我們專注在邊壅塞度,它是在互連網絡中成本分析和性能測量的一個重要指標。基於我們的最短路徑路由演算法,我們證明了在交換超立方體EH(s, t) 的邊壅塞度是3 · 2^(s+t+1) − 2^(s+1) − 2^(t+1)。最後,我們驗證了我們的最短路徑路由演算法關於交換超立方體EH(s, t) 的邊壅塞度是一個最佳的路由策略。zh_TW
dc.description.abstractTopological properties have become a popular and important area of focus for studies that analyze interconnections between networks. The n-dimensional hypercube is one of the most widely discussed topological structures for interconnections between networks and is usually covered in introductions to the basic principles and methods for network design. The exchanged hypercube EH(s, t) is a new variant of the hypercube that has slightly more than half as many edges and retains several valuable and desirable properties of the hypercube such as a small diameter, bipancyclicity, and super connectivity. In this dissertation, we study the wide diameter and fault diameter of exchanged hypercubes EH(s, t). We construct s+1 (or t+1) internally ver-tex-disjoint paths between any two vertices for parallel routes in the exchanged hypercube EH(s, t) for 3 ≤ s ≤ t. We also show that both the (s + 1)-wide diameter and s-fault diameter of the exchanged hypercube EH(s, t) are s + t + 3 for 3 ≤ s ≤ t. Moreover, we propose an approach for shortest path routing algorithms from the source vertex to the destination vertex in EH(s, t) with time complexity O(n), where n = s +t+1 and 1 ≤ s ≤ t. Then, we focus on edge congestion, which is an important indicator for cost analyses and performance measurements in interconnection networks. Based on our shortest path routing algorithm, we show that the edge congestion of EH(s, t) is 3 · 2^(s+t+1) − 2^(s+1) − 2^(t+1). Finally, we prove that our shortest path routing algorithm is an optimal routing strategy with respect to the edge congestion of EH(s, t).en_US
dc.language.isoen_USen_US
dc.subject超立方體zh_TW
dc.subject交換超立方體zh_TW
dc.subject連結網路zh_TW
dc.subject不相交的路徑zh_TW
dc.subject寬直徑zh_TW
dc.subject損壞直徑zh_TW
dc.subject最短路徑路由zh_TW
dc.subject邊壅塞度zh_TW
dc.subjecthypercubeen_US
dc.subjectexchanged hypercubeen_US
dc.subjectinterconnection networken_US
dc.subjectinternally vertex disjoint pathsen_US
dc.subjectwide diameteren_US
dc.subjectfault diameteren_US
dc.subjectshortest path routingen_US
dc.subjectedge congestionen_US
dc.title交換超立方體的拓撲性質之研究zh_TW
dc.titleA Study on Topological Properties of Exchanged Hypercubesen_US
dc.typeThesisen_US
dc.contributor.department資訊科學與工程研究所zh_TW
顯示於類別:畢業論文