Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/56695
| Title: | การจัดสรรความจุสำรองสำหรับความอยู่รอดของโครงข่าย DWDM ที่รองรับทราฟฟิกแบบมัลติคาสต์โดยอัลกอริทึมฮิวริสติกบนพื้นฐานของการค้นหาแบบทาบู |
| Other Titles: | Spare capacity allocation for survivable multicast DWDM networks by heuristic algorithm based on tabu search |
| Authors: | กนกภรณ์ วีสเพ็ญ |
| Advisors: | ลัญฉกร วุฒิสิทธิกุลกิจ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Advisor's Email: | wlunchak@chula.ac.th |
| Subjects: | เส้นใยนำแสง จีเนติกอัลกอริทึม ฮิวริสติกอัลกอริทึม Optical fibers Optical amplifiers Genetic algorithms Heuristic algorithms Simulated annealing (Mathematics) |
| Issue Date: | 2549 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | วิทยานิพนธ์ฉบับนี้นำเสนออัลกอริทึมฮิวริสติกบนพื้นฐานของการค้นหาแบบทาบูสำหรับการจัดสรรความจุสำรองในโครงข่ายมัลติคาสต์แบบมัลติเพลกซ์เชิงความยาวคลื่นหนาแน่นเพื่อให้สามารถปกป้องความเสียหายหนึ่งข่ายเชื่อมโยงได้ โดยได้พิจารณากลยุทธการปกป้องสองประเภทคือ LR (Light-Tree Reconfiguration) และ LIR (Light-Free-Interrupted Reconfiguaration) กับระบบที่มีการใช้และไม่ใช้อุปกรณ์แปลงผันความยาวคลื่น วัตถุประสงค์ของการออกแบบคือหาผลเฉลยของการจัดสรรต้นไม้เชิงแสงและความยาวคลื่นที่มีประสิทธิภาพ โดยมีความต้องการความจุสำรองต่ำ ภายใต้เงื่อนไขว่าสามารถปกป้องโครงข่ายจากความเสียหายหนึ่งข่ายเชื่อมโยงได้ทุกกรณี อัลกอริทึมที่เสนอได้นำมาทดสอบกับการออกแบบโครงข่ายหลายขนาดตั้งแต่ 8 ถึง 14 โนดกับทราฟฟิกมัลติคาสต์ สำหรับผลการทดสอบกับโครงข่ายขนาดเล็ก (8 โนด 14 ข่ายเชื่อมโยง) พบว่าอัลกอริทึมที่เสนอให้ผลการออกแบบที่ใกล้เคียงกับผลที่ได้จากวิธีที่เหมาะสมที่สุด ซึ่งแสดงให้เห็นว่าอัลกอริทึมฮิวริสติกที่เสนอมีประสิทธิภาพ สำหรับปัญหาของโครงข่ายที่มีขนาดใหญ่ขึ้นพบว่าการใช้วิธี ILP ไม่สามารถหาผลเฉลยได้ภายในเวลาจำกัด ในขณะที่อัลกอริทึมฮิวริสติกสามารถให้ผลเฉลยที่มีประสิทธิภาพภายในเวลาที่สมเหตุสมผล อย่างไรก็ตาม ผลจากการศึกษาได้แสดงให้เห็นว่าประสิทธิภาพของอัลกอริทึมขึ้นอยู่กับการตั้งค่าพารามิเตอร์ที่เหมาะสม เช่นขนาดของ tabu list เกณฑ์การหยุด ขนาดของแคนดิเดท ซึ่งจะพบว่าค่าพารามิเตอร์ที่ทำให้อัลกอริทึมฮิวริสติกให้นำเสนอมีประสิทธิภาพนั้น จะต้องใช้ tabu list ที่เป็นแบบพลวัตที่มีช่วงอยู่ระหว่าง 5 ถึง 12 ครั้งสำหรับโครงข่ายขนาด 8 โนด 14 ข่ายเชื่อมโยง และโครงข่ายขนาด 10 โนด 21 ข่ายเชื่อมโยง ในขณะที่โครงข่าย 14 โนด 21 ข่ายเชื่อมโยง จะต้องใช้ tabu list แบบพลวัตที่มีช่วงอยู่ระหว่าง 5 ถึง 15 ครั้ง โดยใช้เกณฑ์การหยุดเท่ากับ 4,000 10,000 และ 6,000 ตามลำดับ โครงข่ายที่ใช้ทดสอบทั้งหมดจะต้องกำหนดให้ขนาดของแคนดิเดทเท่ากับ 4 เช่นเดียวกันภายใต้กระบวนการ 100,000 รอบ จากการทดลองในวิทยานิพนธ์นี้ พบว่าการจัดสรรความจุสำรองโดยใช้กลยุทธ์ LR_VLT จะมีต้นทุนของโครงข่ายต่ำสุด LIR_VLT LR_LT และ LIR_LT จะเป็นกลยุทธ์การป้องกันที่ต้องการต้นทุนมากกว่าวิธี LR_VLT ตามลำดับ จากน้อยไปมาก |
| Other Abstract: | This thesis proposes heuristic algorithms based on tabu search for spare capacity allocation in survivable multicast dense wavelength division multiplexed (DWDM) networks with single link failute protection capability. Two types of protection strategies, namely Light-Tree Reconfiguaration (LR) and Light-Tree Interrupted Reconfiguration (LIR) strategies, are considered for systems with and without wavelength conversion. The objective is to determine efficient light-tree and wavelength assignment that minimizes the spare capacity requirement while providing full protection against all single link failures. The proposed algorithms are applied to tested networks of different sizes from 8 to 14 nodes with certain multicast traffic demands. It is found that the design outcomes of the small network case (8 nodes and 14 links) are comparable to that of optimal ILP-based approach, signifying the effectiveness of the proposed heuristic algorithms. For larger network problems, the ILP-based approach requires excessive computational time, while the heuristic algorithms are able to provide efficient design solutions within reasonable time. However, study has also shown that the effectiveness of the algorithms depends on appropriate parameter settings, types of tabu list, tabu list sizes, stop criteria and candidate sizes. Dynamic tabu list with length ranging from 5 to 12 times is suitable for network size 8 and 10 while length ranging from 5 to 20 times is suitable for network size 14 under candidate size parameter of 4 and stop criteria of 4,000 6,000 and 10,000 respectively in process of 100,000 iterations. It is found that LR_VLT is the strategy that requires spare capacity allocation at minimum cost in survivable DWDM networks when compared with other techniques: LIR_VLT, LR_LT and LIR_LT. |
| Description: | วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2549 |
| Degree Name: | วิศวกรรมศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิศวกรรมไฟฟ้า |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/56695 |
| URI: | http://doi.org/10.14457/CU.the.2006.1334 |
| metadata.dc.identifier.DOI: | 10.14457/CU.the.2006.1334 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| kanokporn_we_front.pdf | 1.18 MB | Adobe PDF | View/Open | |
| kanokporn_we_ch1.pdf | 652.31 kB | Adobe PDF | View/Open | |
| kanokporn_we_ch2.pdf | 769.55 kB | Adobe PDF | View/Open | |
| kanokporn_we_ch3.pdf | 1.17 MB | Adobe PDF | View/Open | |
| kanokporn_we_ch4.pdf | 927.49 kB | Adobe PDF | View/Open | |
| kanokporn_we_ch5.pdf | 1.59 MB | Adobe PDF | View/Open | |
| kanokporn_we_ch6.pdf | 338.89 kB | Adobe PDF | View/Open | |
| kanokporn_we_back.pdf | 6.03 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.