Ad-Hoc Routing Protocol (DSDV, AODV, DSR)

อธิบาย Routing Protocol Algo. ประกอบ แผนภูมิแสดงความเกี่ยวเนื่อง (ตระกูล, สายพันธุ์)

Routing Algo. ตระกูล “DV” จะทำการ Broadcast ข้อมูล Routing Table ให้แก่ Node ข้างเคียงทราบ (by Event, by Periodic) โดยที่ค่า Distance Vector → Routing Table ซึ่งเป็นข้อมูลที่ประกอบไปด้วย destination node address, hop count, next hop node, etc.

เช่นตอนนี้ Node = กทม. จะมี Routing Table เป็น

Destination

Hop Count

Next Hop Node

เชียงใหม่

8 ( สมมติ )

อยุธยา

สงขลา

12 ( สมมติ )

สมุทรสาคร

  • พยายามแยกแยะระหว่าง Routing Table และ Routing Entry เวลาอ่าน, เนื่องจาก Routing Entry หมายถึง Record ของ Routing Table ที่บันทึกเส้นทางไปยังแต่ละ Destination
  • ตัวอย่างการทำงานของ Routing Protocol ที่แสดงต่อไปนี้ อ้างอิงจาก [Boppana1999] ซึ่งได้อาศัย ns-2 + Extension “CMU” เพื่อทดสอบ

Destination-Sequenced Destance Vector (DSDV)

  • “DSDV” บอก DV table ให้ “Neighbor Node” ทราบเป็น Periodic (ไม่ต้องคอยถาม) โดยที่ข้อมูลใหม่ที่มีการเปลี่ยนแปลง Routing จะมีการประทับ “Sequence Number” เพื่อป้องกันการซ้ำซ้อน

  • Node ที่รับรู้ว่า Routing เปลี่ยนแปลง ทำการเพิ่มค่า Seq แล้วส่งต่อ Routing Table “ใหม่” ให้ Node ข้างเคียง

  • ข้อเสียที่พบคือ Bandwidth ที่เสียไปกับ Overhead ในการ Update Routing Table

Ad-Hoc On-Demand Distance Vector (AODV)

แทนที่การ Update ข้อมูล Routing Table แบบ Periodic, หาก Node ต้องการส่งข้อมูลไปยังปลายทางที่ข้อมูลใน Routing Table ไม่มีหรือไม่ถูกต้อง, AODV กำหนดให้ Node ดังกล่าวทำการร้องขอเส้นทาง (อาศัย Route Request, RREQ) ด้วยวิธีการ Flooding ทั่วทั้ง Network ซึ่งจะทำให้ได้ Routing Table (Route Response, RREP) แจ้งกลับมา

ข้อมูล DV → Routing Table ที่แต่ละ Node มีอยู่มีการจำกัดระยะเวลา หากไม่ได้รับการตรวจสอบนานเกินกว่าระยะเวลาหนึ่ง จะให้ถือว่า Routing Table นั้นไม่ถูกต้อง (Invalid) หรือหาก “Next Hop Node” ไม่อยู่แล้ว ก็ให้ถือว่าเป็นเส้นทางไม่ถูกต้องเช่นกัน ซึ่งจำเป็นต้องแจ้งให้ Neighbour Node ที่มี Next Hop Node เป็น Node นี้รับทราบ

สรุปว่าหาก

  • ไม่เคยถามถึง” หรือ “หาไม่เจอ” ให้ Flooding Network เพื่อหาเส้นทาง

  • ทราบว่าไม่อยู่” หรือ “นานแล้วไม่มีการส่งข้อมูลถึง” ให้ Routing Invalid แล้วแจ้งให้ Neighbour Node ทราบ

Dynamic Source Routing (DSR)

ลักษณะ Routing Table ที่ Source จะต่างจากตระกูล DV คือ ในส่วนของ Routing Path แทนที่จะมีแค่ Next Hop Node แต่จะบรรจุทั้งหมดของเส้นทางไว้รวมกับ Data Packet (ซึ่ง Packet จำต้องเดินทางตามนั้น)

Destination

Hop Count

Next Hop Node

เชียงใหม่

8 ( สมมติ )

อยุธยา , อ่างทอง , สิงห์บุรี , …

สงขลา

12 ( สมมติ )

สมุทรสาคร , สมุทรสงคราม , …

หาก Source ไม่มีเส้นทางไปยัง Destination จะทำกระบวนการ “Route Discovery” เช่นเดียวกับ AODV เพียงแต่ต่างกันที่ RREQ จะสะสมรายละเอียดเส้นทางครบทุก Node ไปยังจุดหมาย และตอบกลับมาให้ Source Node ทราบผ่าน RREP

แน่นอนว่ากรรมวิธีดังกล่าวจะเพิ่ม Overhead เป็นอันมาก ทั้งยังเป็นการยากที่จะทำให้เกิดการประหยัดพลังงาน เพราะ แต่ละ Node ต้องคอย “ดักฟัง (Snoop, Promiscuous)” เส้นทางไป Destination ต่างๆ จากทุกๆ Packet ข้อมูลที่วิ่งผ่าน ดังนั้นจึงได้มีแนวทางคิด Optimization เพื่อเพิ่มประสิทธิภาพ เช่น ทำงานแบบไม่ต้องคอยดักฟัง (Non-snooping DSR, NSDSR) หรือให้มีการดักฟังได้ต่อมีเกิดกระบวนการ Route Discovery (Selective Snooping DSR, SSDSR) เท่านั้น

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s