การจัดสรรความจุสำรองสำหรับความอยู่รอดของโครงข่าย DWDM ที่รองรับทราฟฟิกแบบมัลติคาสต์โดยอัลกอริทึมฮิวริสติกบนพื้นฐานของการค้นหาแบบทาบู

กนกภรณ์ วีสเพ็ญ

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/56695

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	ลัญฉกร วุฒิสิทธิกุลกิจ	-
dc.contributor.author	กนกภรณ์ วีสเพ็ญ	-
dc.contributor.other	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์	-
dc.date.accessioned	2018-01-04T03:20:02Z	-
dc.date.available	2018-01-04T03:20:02Z	-
dc.date.issued	2549	-
dc.identifier.uri	http://cuir.car.chula.ac.th/handle/123456789/56695	-
dc.description	วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2549	en_US
dc.description.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 ตามลำดับ จากน้อยไปมาก	en_US
dc.description.abstractalternative	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.	en_US
dc.language.iso	th	en_US
dc.publisher	จุฬาลงกรณ์มหาวิทยาลัย	en_US
dc.relation.uri	http://doi.org/10.14457/CU.the.2006.1334	-
dc.rights	จุฬาลงกรณ์มหาวิทยาลัย	en_US
dc.subject	เส้นใยนำแสง	en_US
dc.subject	จีเนติกอัลกอริทึม	en_US
dc.subject	ฮิวริสติกอัลกอริทึม	en_US
dc.subject	Optical fibers	en_US
dc.subject	Optical amplifiers	en_US
dc.subject	Genetic algorithms	en_US
dc.subject	Heuristic algorithms	en_US
dc.subject	Simulated annealing (Mathematics)	en_US
dc.title	การจัดสรรความจุสำรองสำหรับความอยู่รอดของโครงข่าย DWDM ที่รองรับทราฟฟิกแบบมัลติคาสต์โดยอัลกอริทึมฮิวริสติกบนพื้นฐานของการค้นหาแบบทาบู	en_US
dc.title.alternative	Spare capacity allocation for survivable multicast DWDM networks by heuristic algorithm based on tabu search	en_US
dc.type	Thesis	en_US
dc.degree.name	วิศวกรรมศาสตรมหาบัณฑิต	en_US
dc.degree.level	ปริญญาโท	en_US
dc.degree.discipline	วิศวกรรมไฟฟ้า	en_US
dc.degree.grantor	จุฬาลงกรณ์มหาวิทยาลัย	en_US
dc.email.advisor	wlunchak@chula.ac.th	-
dc.identifier.DOI	10.14457/CU.the.2006.1334	-
Appears in Collections:	Eng - Theses

Files in This Item:

File	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

Show simple item record