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

Abstract

วิทยานิพนธ์ฉบับนี้มีจุดมุ่งหมายเพื่อเสนออัลกอริทึมการจัดเส้นทางแบบมัลติคาสต์บนโครงข่ายเอทีเอ็มโดยอาศัยแนวคิดของโครงข่ายเสมือน (virtual network), การจัดเส้นทางแบบ shortest path ซึ่งเป็นการจัดเส้นทางสำหรับการสื่อสารข้อมูลแบบจุดต่อจุด (point-to-point) ที่ใช้บนโครงข่ายเอทีเอ็ม และการนำแนวคิด Steiner Tree มาใช้ช่วยในการสร้างเส้นทางแบบมัลติคาสต์ อัลกอริทีมที่เสนอมี 2 ชุด คืออัลกอริทึม p1 และ p2 โดยที่ p2 ไม่ได้ใช้ Steiner node วิธีที่เสนอจะนำไปเปรียบเทียบกับอัลกอริทึมที่เสนอโดย Jia (1995) ที่เป็นอัลกอริทึมที่อยู่บนพื้นฐานของ spanning tree โดยมีฟังก์ชันวัตถุประสงค์ประกอบด้วยต้นทุนของแบนด์วิดท์ ต้นทุนของการต่อถึงกัน และต้นทุนของการสวิตซ์ VP และ VC ผลการจำลองแบบแสดงให้เห็นว่าอัลกอริทึม p1 ให้ค่าต้นทุนของแบนดวิดท์ต่ำกว่าอัลกอริทึมของ Jia 0.35%-11.31% และต้นทุนการสวิตซ์ VP ลดลง 13.51%-45.16% ขณะเดียวกันต้นทุนการต่อถึงกัน เพิ่มขึ้น 0.09%-24% และต้นทุนของการสวิตซ์ VC เพิ่มขึ้น 0.09%-20% ซึ่งช่วงของการเปลี่ยนแปลงต้นทุนเหล่านี้มีความสัมพันธ์กับจำนวน Steiner Node ที่ใช้ในแต่ละช่วง สำหรับอัลกอริทึม p2 ให้ต้นทุนใกล้เคียงกับต้นทุนที่ได้จากอัลกอริทึมของ Jia แต่ใช้เวลาในการคำนวณเร็วกว่า เมื่อเปรียบเทียบค่าความยาววิถีและเวลาที่ใช้ในการคำนวณ พบว่าอัลกอริทึมที่เสนอใหม่มีความยาววิถีสั้นกว่าและใช้เวลาในการคำนวณน้อยกว่าอัลกอริทึมของ Jia นอกจากนี้ได้ทำการปรับแต่งอัลกอริทึมที่เสนอใหม่ทั้งสองเพื่อไปใช้ในการทำ dynamic multicast พบว่าขนาดของโครงข่ายที่เหมาะสมสำหรับอัลกอริทึมที่ปรับแต่งแล้วควรจะต่ำกว่า 40 โนด