Chulalongkorn University Theses and Dissertations (Chula ETD)

การจัดเส้นทางที่เหมาะสมที่สุดในโครงข่ายสื่อสาร แบบคอนเนกชันโอเรียนเตด โดยใช้ฮิวริสติกอัลกอริทึม

Other Title (Parallel Title in Other Language of ETD)

Optimum routing in a connection-oriented communication network using heuristic algoritm

Year (A.D.)

1997

Document Type

Thesis

First Advisor

วาทิต เบญจพลกุล

Faculty/College

Graduate School (บัณฑิตวิทยาลัย)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมไฟฟ้า

DOI

10.58837/CHULA.THE.1997.934

Abstract

เสนอการจัดเส้นทางวงจรเสมือนที่เหมาะที่สุด ในโครงข่ายสื่อสารที่ให้บริการแบบคอนเนกชันโอเรียนเตด และต้องการระบบการจัดเส้นทางแบบกึ่งสถิตโดยใช้ฮิวริสติกอัลกอริทึม ซึ่งพัฒนามาจากยีนส์นิติกอัลกอริทึม ทาบูเซอร์ช และอีโวลูชันนารีคอมพิวติง การจัดเส้นทางวงจรเสมือนพิจารณาจากความน่าจะเป็น ที่แพ็กเกตเกิดการสูญหายในวงจรเสมือน เนื่องจากแพ็กเกตเกิดการบล็อกขึ้นที่บัฟเฟอร์ด้านขาออก ของสวิตซ์ที่วงจรเสมือนผ่าน นอกจากนี้ยังได้เสนอวิธีการกำหนดคำตอบเริ่มต้น ที่ใช้ในการค้นหาคำตอบที่เหมาะที่สุด ของฮิวริสติกอัลกอริทึมสำหรับแก้ปัญหานี้ด้วย โดยกำหนดจากเซตของเส้นทางวงจรเสมือน ที่ได้จากเทคนิคการจัดเส้นทางที่มีจำนวนฮอบน้อยที่สุด และเทคนิคการจัดเส้นทางที่มีโหลดน้อยที่สุด ผลการทดสอบการจัดเส้นทางวงจรเสมือน โดยใช้ฮิวริสติกอัลกอริทึมสำหรับโครงข่ายทดสอบ พบว่าเส้นทางที่ได้จากการจัดเส้นทาง โดยใช้ฮิวริสติกอัลกอริทึมดีกว่า เส้นทางที่ได้จากการใช้เทคนิคการจัดเส้นทาง ที่มีจำนวนฮอบน้อยที่สุด และเทคนิคการจัดเส้นทางที่มีโหลดน้อยที่สุด วิทยานิพนธ์ฉบับนี้ได้เปรียบเทียบจำนวนรอบการประมวลผล ของฮิวริสติกอัลกอริทึมในการจัดเส้นทางวงจรเสมือน เมื่อกำหนดจำนวนของเวกเตอร์แม่และเวกเตอร์ลูกไว้ต่างๆ กัน ผลการทดสอบแสดงให้เห็นว่า การเพิ่มจำนวนของเวกเตอร์แม่และเวกเตอร์ลูก สามารถลดจำนวนรอบการประมวลผลของฮิวริสติกอัลกอริทึมลงได้

Other Abstract (Other language abstract of ETD)

Proposes an optimum semi-static virtual circuit routing method in connection-oriented communication network using Heuristic Algorithm, developed from Genetic Algorithm, Tabu Search, and Evolutionary Computing. The routing constraints are the probability of packet loss in virtual circuit due to the blocking of packet at the switch output buffer. This thesis also proposes a method to assign initial solution, used to search the optimum point of Heuristic Algorithm. The initial solution is assigned by either a set of virtual circuit route, obtained from minimum hop route technique or from least load route one. The tested result of optimum virtual circuit routing using the proposed Heuristic Algorithm for any network sizes shows that the routes obtained are better than those obtained from minimum hop route and least load route techniques. In this thesis, the comparison results of the number of iteration in calculation for Heuristic Algorithm which the number of mother vectors and the number of sun vectors are assigned by several values show that increasing the number of mother vectors and the number of sun vectors, the number of iteration is decreased.

Link to Full Text

Share

COinS