透過您的圖書館登入
IP:44.210.99.209
  • Journals
  • OpenAccess

Θ(N(superscript 5/6)) Time Complexity of Fault Diagnosis Algorithms in N×N Dilated Blocking Photonic Switching Networks

Parallel abstracts


Dilated Optical Multistage Interconnection Networks (DOMINs) based on 2×2 directional coupler photonic switches play an important role in all-optical high-performance networks, especially for the emerging IP over DWDM architectures. The problem of crosstalk within photonic switches is underestimated due to the aging of the switching element, control voltage, temperature and polarization, and thus causes undesirable coupling of the signal from one path to the other. Previous works [18] designed an efficient diagnosing disjoint faults algorithm in small sized networks, which reduced the number of tests required by overlapping the tests with computations to one half in photonic switching networks. Furthermore, this paper generically derives algorithms and mathematical modules to find the optimal degree of parallelism of faults diagnosis for N×N dilated blocking networks, as the size of network is larger. Taking advantage of the properties of disjoint faults, diagnosis can be accelerated significantly because the optimal degree of parallel fault diagnosis may grow exponentially. To reduce the diagnosis time, an algorithm is proposed herein to find the maximum number of disjoint faults. Rather than requiring up to 4MN tests as a native approach, a two-phase diagnosis algorithm is proposed to reduce the testing requirement to 4N tests. This study extends the concept of disjoint faults to reduce the number of tests to the time efficiency of Θ(N(superscript 5/6)) for N×N DOMINs.

Cited by


張世昭(2002)。擴張型可重新排列光電開關網路串音偵錯之容錯排程演算法〔碩士論文,元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611335587
Huang, I. F. (2005). 光通訊網路之高效能故障管理方案研究 [doctoral dissertation, Yuan Ze University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611292333

Read-around