loading...
Distributed Scheduling Algorithms for Wavelength Convertible WDM Optical Interconnects
Nice, France April 22-April 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213170International Parallel and Distribute ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Zhenghao Zhang, State University of New York at Stony Brook
Yuanyuan Yang, State University of New York at Stony Brook
Optical communication is attracting more and more attentions because of its huge bandwidth to meet the ever increasing demand of emerging computing/networking applications. In this paper we study distributed scheduling algorithms to resolve output contentions in WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion, including the full range wavelength conversion. Two types of limited range wavelength conversions, circular symmetrical and non circular symmetrical, are studied. We introduce the request graph and show that finding the largest group of contention-free connection requests to achieve maximum network throughput is equivalent to finding a maximum matching in the request graph. Compared with the existing algorithm for finding a maximum matching in an arbitrary bipartite graph with time complexity 0(N^{\frac{3}{2}} k^{\frac{3}{2}} d), the algorithms we present have time complexity of O(k) and O(dk) (independent of interconnect size N) for non-circular symmetrical and circular symmetrical wavelength conversion, respectively, where k is the number of wavelengths per fiber and d is the conversion degree. In addition, our algorithms can be easily implemented in hardware, and used for time slotted WDM optical interconnects where connections hold for different number of time slots.
Index Terms:
Wavelength-division-multiplexing (WDM), optical switches, optical interconnects, wavelength conversion, limited range wavelength conversion, scheduling algorithms, distributed algorithms, maximum matching, convex bipartite graph, contention-free
Citation:
Zhenghao Zhang, Yuanyuan Yang, "Distributed Scheduling Algorithms for Wavelength Convertible WDM Optical Interconnects," ipdps, pp.72a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.