This thesis proposes and studies distributed spanning tree algorithms for the protection/restoration of Dense Wavelength Division Multiplexing (DWDM) networks. A heuristic algorithm using tokens to construct a maximum spanning tree in a distributed manner as well as the corresponding protection/restoration schemes are proposed. One algorithm involves a triangular structure on which we have proposed a triangular tree protection/restoration scheme. Since we need a root to build a spanning tree, we give three root selection algorithms to select a proper root. Properties of these algorithms are then studied. Performance analysis in terms of mean path length, capacity ratio and restorability of the spanning tree to the mesh network and number of messages transmitted during the construction of the spanning tree are provided in this thesis. We also compare the spanning tree algorithms with another distributed spanning tree algorithm in the performance. It shows that the tree protection schemes can be an alternative to the DWDM network protection/restoration.
展开▼
