Abstract
在這篇文章中，我們研究了如何利用Survivable Rings來確保WDM網路上存活能力。若有數條光徑形成環狀結構，則當環狀結構上的某條光徑無法傳送資料時，可以藉由環狀結構上的其他光徑來繼續傳送資料，所以說環狀結構上的光徑都具有存活能力，而為了使得每條光徑都具有存活能力，所有的光徑都必須是某個環狀結構的一部分，若是無法形成完整的環狀結構，則增加額外的光徑來形成完整的環狀結構，而這方面研究的成本考量，是希望使用較少的額外光徑，同樣也代表著希望使用較少的電子終端設備，在一般的實體拓樸上(general topology)，有[5,6]兩篇論文著手於研究這類的問題，而這類的問題的最佳化已經被證明是NP-Hard，所以他們各自提出近似演算法(approximation algorithm)，用Maximum Matching來規劃環狀結構，使得光徑盡量共用電子終端設備，但是Maximum Matching會拆散完整的環狀結構，所以[6]提出先使用preprocessing的步驟找出較小的環狀結構，而後再利用Maximum Matching，以避免將完整的環狀結構拆散，[5,6]兩篇中的近似演算法可分別得到確保小於1.6倍最佳解與小於(1.5+ε)倍最佳解的結果。 我們觀察到目前提出的近似演算法PIM[6]仍然存在著兩個可以改善的地方，第一個是因為每個iteration利用Maximum Matching，以光徑共用最多的電子終端設備的觀點為考量，卻沒有考慮到光徑共用電子終端設備後，所形成的環狀結構是否會使用較少的額外光徑，且有可能將較佳的光徑組合拆散，雖然光徑在每個iteration共用最多的電子終端設備，但是卻不一定會使得最後共用的電子終端設備最多，也就不一定會使得所需的額外光徑數目較少，第二個是因為preprocessing的步驟中是找出較小的環狀結構，卻不是找出可以符合目標，也就是使得所需的額外光徑數目較少的環狀結構，所以我們的動機是要改善上面所提及的兩點，尋找解決問題的方法。這篇論文主要的貢獻有兩個，第一個貢獻是我們跳脫Maximum Matching的做法，提出新的想法與方法，來解決這一類的問題，並且在選擇環狀結構時，放棄選擇較小的環狀結構，改以兩個Greedy演算法選擇較適當的環狀結構讓所需的額外光徑數目較小，與PIM[6]相比，最少可以減少12.36%的額外光徑數目，最多可以減少16.01 %的額外光徑數目，的確可以節省所需額外光徑數目。第二個貢獻是我們發現光徑的路徑也會影響結果，若是利用有效的光徑(lightpath)繞徑方式，使得所有光徑的路徑盡量平均分散在網路上，若是路徑不重疊就可以共用電子終端設備，使得可以共用電子終端設備的機會增加，並且使用較少的額外光徑形成具有存活能力的環狀結構，以節省成本，可以發現有效的光徑繞徑方式對於PIM[6]與我們的方法都有幫助，而我們方法與PIM[6]相比，最少可以減少16.45%的額外光徑數目，最多可以減少27.43 %的額外光徑數目，也的確可以節省所需額外光徑數目。若是當實體拓樸上的平均每個節點的degree越大時，鏈結數目越多，也可以使得所有光徑盡量平均分散在網路上，也可以減少所需的額外光徑數目。