Clique‐partitioning connections‐scheduling with faulty switches in dilated benes network

Abstract

In Dilated Optical Multistage Interconnection Networks constructed by 2 ×2 photonic switches, each input‐to‐output connection can be established along one path through the network. If two connections compete for the same switch, only one connection can be established at a time. For a given set of requested connections with/ without faulty switches, it is desirable to establish them in as few rounds as possible. Optical crosstalk is a problem in Optical Multistage Interconnection Networks and a switch is said to be faulty if it causes excessive crosstalk(s) above a given threshold, whose value can be determined according to certain criteria. In this paper, we study the problem of connections‐scheduling with faulty switches in a dilated re‐arrangeable photonic network, a Dilated Benes Network (DBN). We map the connections‐scheduling problem to a variant of the clique partitioning problem, and then use a heuristic algorithm for scheduling the connections. The simulation results show that the proposed method is efficient and it can maintain the reliability of the DBN network by tolerating some faulty switches.

Key words:

• DOMINs
• faulty switch
• connections‐scheduling
• clique partitioning problem

Notes

Corresponding author. (Tel: [phone]; Fax: [phone]; Email: [email protected])