ABSTRACT DYNAMIC ROUTING AND WAVELENGTH ASSIGNMENT IN WAVELENGTH-DIVISION MULTIPLEXED (WDM) OPTICAL NETWORKS USING NEURO-DYNAMIC PROGRAMMING Serkan Yeşildağ M.S. in Electrical and Electronics Engineering Supervisor: Assist. Prof. Dr. Murat Alanyalı July 2001 In this thesis work, dynamic routing and wavelength assignment (RWA) problem in optical networks is studied. Assuming memory less interarrival and holding times for calls, minimizing the average call blocking rate can be viewed as a Markov Decision Problem. Dynamic programming is the direct method to ob tain an exact solution. However, this method is intractable for large networks encountered in practice. Therefore, we use neuro-dynamic programming (NDP) which is a simulation based dynamic programming methodology to obtain suc cessful policies. In this approach the cost-to-go function is approximated using predetermined features of the network state, so the obtained policies are based on these features. In the present context, features are selected from the most com monly used heuristics for the RWA problem. Simulation results shows that NDP approach gives significantly lower blocking rates compared to the heuristics. Keywords: Wavelength-Division Multiplexing (WDM), Wavelength Routing, Wavelength assignment, Optical Networks, Dynamic Programming, Neuro- Dynamic Programing. m

ÖZET OPTİK DALGABOYU BÖLÜNMELİ ÇOĞULLAMA AĞLARINDA SİNİRSEL DİNAMİK PROGRAMLAMA KULLANILARAK DİNAMİK YOL VE DALGABOYU ATAMA Serkan Yeşildağ Elektrik ve Elektronik Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Yrd. Doç. Dr. Murat Alanyalı Temmuz 2001 Bu tezde, optik ağlarda yol ve dalgaboyu atama problemi ele alınmaktadır. Çağrılar için hafızasız varış arası zamanları ve üssel dağılımlı sürme zaman ları kabul edildiğinde, ortalama reddedilme sıklığının en aza indirilmesi Markov karar verme problemi olarak görülebilir. Dinamik programlama kesin sonucu elde etmede direkt yöntemdir. Fakat bu yöntemin pratikte karşılaşılan büyük ağlar için çözümü zordur. Bu yüzden, başarılı stratejiler elde etmek için ben zetime dayalı dinamik programlama yöntemi olan sinirsel dinamik programlama kullanmaktayız. Bu yaklaşımda gidiş-ücreti fonksiyonu ağ durumunun önceden belirlenmiş özellikleri kullanılarak yaklaştırıldığı için elde edilen stratejiler bu özelliklere dayalıdır. Bu durumda özellikler yol ve dalgaboyu atama problemi için sıkça kullanılan buluşsal yöntemlerden seçilmiştir. Anahtar Kelimeler: Dalgaboyu Bölünmeli Çoğullama, Dalgaboyu Yönlendirme, Dalgaboyu Atama, Optik Ağlar, Dinamik Programlama, Sinirsel Dinamik Pro gramlama. iv

52