Exploiting Petri Nets to Reduce Switch Crosstalk and Path-Dependent-Loss in Optical Interconnection Networks

Abstract

ABSTRACT: Although optical communication systems promise to meet demands of communication networks and multiprocessors in fast communication, they suffer from challenges such as path dependent loss and switch crosstalk. An innovative approach proposed in the present thesis is centered upon modelling OMINs with Petri nets and using P-invariants method for determination of the minimum number of stages that is sufficient for realization of demanded communication patterns in an OMIN with variable number of stages. Being composed of stages an OMIN of the minimal structure provides the least values for the path dependent loss and switch crosstalk. Based on complexity results, we make sure about feasibility of our approach. Firstly, we prove that the P/T-nets created in the present research are in polynomial dependence on the problem size, which alleviates memory consumption significantly and reassures the fact that the task according to our approach can be completed in feasible time. Secondly, we compare P/T-nets obtained in the present reasearch with the complete unfoldings created in our previous reasearch and show that P/T-nets in the latter work are more compact in the size than the ones considered in the former research. This is improvement of the complexity results obtained in our previous work. Finally, we verify validation of our approach through performing series of computer tests and showing that the results of the computer experiments agree with known analytical results. ………………………………………………………………………………………………………………………… ÖZ: Optik interkoneksiyon ağları, bilgisayar iletişim ağlarının ve çok işlemcili sistemlerin hızlı iletişime olan ihtiyaçlarını karşılamanın yanı sıra yola bağımlı kayıplar ve anahtarlamada hatların karışması gibi zorluklardan etkilenirler. Bu tezde önerilen yenilikçi yaklaşımın temelinde optik interkoneksiyon ağlarının Petri ağları ile modellenmesi ve P-invariantlar metodunu uygulayarak çok basamaklı optik interkoneksiyon ağlarında verilen permütasyona göre en küçük basamak sayısının bulunması yatar. En küçük basamak sayılı optik interkoneksiyon ağında yola bağımlı kayıplar ve anahtarlamada hatların karışması en küçük düzeyde seyredilir. Önerilen metodun uygulanabilirliğinden emin olmak için bir karmaşıklık analizi yapılmıştır. Öncelikle tasarlanan P/T-ağların büyüklüğünün artış hızının polinomyal olduğu ispat edilmiştir. Bu olgu, P/T-ağ oluşumunda hafıza tüketiminin önemli ölçüde azaltarak, sıkça rastlanan “durum patlaması”ndan uzakta tutulabileceğini göstermektedir. Sonra takdim edilen çalışmada elde edilen P/T-ağlarını, bir önceki çalışmamızda tasarlanan tamamen açılmış Petri ağlarıyla kıyasladık. Sonuç olarak elde ettiğimiz Petri ağlarının daha küçük olduğu ispat edilmiştir. Alınan analitik ve kuramsal sonuçların geçerliliği yapılan bilgisayar testleri ile kanıtlanmıştır.