โปรโตคอลการกำหนดเส้นทางสถานะลิงก์

Q: ข้อมูลสำคัญเกี่ยวกับ โปรโตคอลการกำหนดเส้นทางสถานะลิงก์

โปรโตคอลการกำหนดเส้นทางแบบลิงก์สเตทเป็นหนึ่งในสองประเภทหลักของโปรโตคอลการกำหนดเส้นทางที่ใช้ใน เครือข่าย

โปรโตคอลการกำหนดเส้นทางแบบลิงก์สเตทเป็นหนึ่งในสองประเภทหลักของโปรโตคอลการกำหนดเส้นทางที่ใช้ใน เครือข่าย การสลับแพ็กเก็ตสำหรับการสื่อสารคอมพิวเตอร์อีกประเภทหนึ่งคือโปรโตคอลการกำหนดเส้นทางแบบเวกเตอร์ระยะทาง^{[ 1 ]}ตัวอย่างของโปรโตคอลการกำหนดเส้นทางแบบลิงก์สเตท ได้แก่Open Shortest Path First (OSPF) และIntermediate System to Intermediate System (IS-IS) ^{[ 2 ]}

โปรโตคอลสถานะลิงก์จะดำเนินการโดยโหนดสวิตช์ ทุกโหนด ในเครือข่าย (เช่น โหนดที่เตรียมพร้อมที่จะส่งต่อแพ็กเก็ต ในอินเทอร์เน็ตโหนดเหล่านี้เรียกว่าเราเตอร์ ) ^{[ 3 ]}แนวคิดพื้นฐานของการกำหนดเส้นทางสถานะลิงก์คือ โหนดทุกโหนดสร้างแผนที่การเชื่อมต่อกับเครือข่ายในรูปแบบของกราฟซึ่งแสดงว่าโหนดใดเชื่อมต่อกับโหนดอื่นใด^{[ 4 ]} จากนั้นแต่ละโหนดจะคำนวณ เส้นทางตรรกะที่ดีที่สุดถัดไปจากโหนดนั้นไปยังปลายทางที่เป็นไปได้ทั้งหมดในเครือข่ายโดยอิสระ^{[ 5 ]} ชุดของเส้นทางที่ดีที่สุดแต่ละชุดจะก่อให้ เกิดตารางการกำหนดเส้นทางของแต่ละโหนด^{[ 6 ]}

สิ่งนี้แตกต่างจากโปรโตคอลการกำหนดเส้นทางเวกเตอร์ระยะทาง ซึ่งทำงานโดยให้แต่ละโหนดแบ่งปันตารางการกำหนดเส้นทางกับเพื่อนบ้าน ในโปรโตคอลสถานะลิงก์ ข้อมูลเดียวที่ส่งผ่านระหว่างโหนดคือข้อมูลที่เกี่ยวข้องกับการเชื่อมต่อ [ ^{7 ] บาง}ครั้งอัลกอริทึมสถานะลิงก์ถูกอธิบายอย่างไม่เป็นทางการว่าเราเตอร์แต่ละตัว "บอกให้โลกรู้เกี่ยวกับเพื่อนบ้านของมัน" ^{[ 8 ]}

ภาพรวม

ในโปรโตคอลการกำหนดเส้นทางแบบ Link-State แต่ละเราเตอร์จะมีข้อมูลเกี่ยวกับโครงสร้างเครือข่าย ทั้งหมด จากนั้นแต่ละเราเตอร์จะคำนวณหา Next Hop ที่ดีที่สุดจากตัวมันเองสำหรับทุกปลายทางที่เป็นไปได้ในเครือข่าย โดยใช้ข้อมูลภายในของโครงสร้างเครือข่าย ชุดของ Next Hop ที่ดีที่สุดเหล่านี้จะก่อให้เกิดตารางการกำหนดเส้นทาง

สิ่งนี้แตกต่างจากโปรโตคอลการกำหนดเส้นทางแบบเวกเตอร์ระยะทางซึ่งทำงานโดยให้แต่ละโหนดแบ่งปันตารางการกำหนดเส้นทางกับโหนดข้างเคียง ในโปรโตคอลแบบสถานะลิงก์ ข้อมูลเพียงอย่างเดียวที่ส่งผ่านระหว่างโหนดคือข้อมูลที่ใช้ในการสร้างแผนที่การเชื่อมต่อ

ประวัติศาสตร์

สิ่งที่เชื่อกันว่าเป็นเครือข่ายการกำหนดเส้นทางแบบปรับตัวได้ครั้งแรกของคอมพิวเตอร์ โดยใช้การกำหนดเส้นทางแบบสถานะลิงก์ ได้รับการออกแบบและนำไปใช้ในช่วงปี 1976–1977 โดยทีมงานจากPlessey Radarนำโดย Bernard J Harris โครงการนี้มีไว้สำหรับ "Wavell" ซึ่งเป็นระบบควบคุมและสั่งการด้วยคอมพิวเตอร์สำหรับกองทัพอังกฤษแนวคิดการกำหนดเส้นทางแบบสถานะลิงก์ครั้งแรกได้รับการตีพิมพ์ในปี 1979 โดยJohn M. McQuillan (ขณะนั้นอยู่ที่Bolt, Beranek and Newman ) ในฐานะกลไกที่จะคำนวณเส้นทางได้เร็วขึ้นเมื่อสภาพเครือข่ายเปลี่ยนแปลง และนำไปสู่การกำหนดเส้นทางที่เสถียรยิ่งขึ้น^[⁹^]^[¹⁰^]

ต่อมาเทคนิคนี้ได้รับการดัดแปลงเพื่อใช้ในโปรโตคอลการกำหนดเส้นทางสถานะลิงก์ร่วมสมัย IS-IS และ OSPF เอกสารของ Ciscoอ้างถึงEnhanced Interior Gateway Routing Protocol (EIGRP) ว่าเป็นโปรโตคอล "ไฮบริด" ^{[ 11 ]}แม้ว่าจะแจกจ่ายตารางการกำหนดเส้นทางแทนแผนที่โทโพโลยีก็ตาม อย่างไรก็ตาม มันจะซิงโครไนซ์ตารางการกำหนดเส้นทางเมื่อเริ่มต้นเหมือนกับที่ OSPF ทำ และส่งการอัปเดตเฉพาะเมื่อมีการเปลี่ยนแปลงโทโพโลยีเท่านั้น

ในปี พ.ศ. 2547 Radia Perlmanเสนอให้ใช้การกำหนดเส้นทางสถานะลิงก์สำหรับ การส่งต่อเฟรม เลเยอร์ 2ด้วยอุปกรณ์ที่เรียกว่าสะพานกำหนดเส้นทางหรือ Rbridges คณะทำงานด้านวิศวกรรมอินเทอร์เน็ตได้กำหนด มาตรฐานโปรโตคอล Transparent Interconnection of Lots of Links (TRILL) เพื่อให้บรรลุเป้าหมายนี้^{[ 12 ]}

เมื่อไม่นานมานี้ เทคนิคการจัดลำดับชั้นนี้ถูกนำไปประยุกต์ใช้กับเครือข่ายไร้สายแบบเมชโดยใช้ โปรโตคอลการกำหนดเส้นทางสถานะลิงก์ที่ปรับให้เหมาะสม (Optimized Link State Routing Protocolหรือ OLSR) ในกรณีที่คุณภาพของการเชื่อมต่ออาจแตกต่างกัน คุณภาพของการเชื่อมต่อสามารถนำมาใช้เพื่อเลือกการเชื่อมต่อที่ดีกว่าได้ วิธีการนี้ใช้ในโปรโตคอลการกำหนดเส้นทางแบบเฉพาะกิจ บางอย่าง ที่ใช้การส่งสัญญาณคลื่นความถี่วิทยุ

การแจกจ่ายแผนที่

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

แต่ละโหนดจะส่งข้อความสั้นๆ เป็นระยะ (และในกรณีที่มีการเปลี่ยนแปลงการเชื่อมต่อ) ซึ่งเรียกว่าการประกาศสถานะการเชื่อมต่อ โดยมีเนื้อหาดังนี้:

ระบุโหนดที่สร้างสิ่งนั้นขึ้นมา
ระบุโหนดอื่นๆ ทั้งหมด (ไม่ว่าจะเป็นเราเตอร์หรือเครือข่าย) ที่เชื่อมต่อโดยตรง
ประกอบด้วย 'หมายเลขลำดับ' ซึ่งจะเพิ่มขึ้นทุกครั้งที่โหนดต้นทาง สร้างข้อความเวอร์ชันใหม่

ข้อความนี้จะถูกส่งไปยังทุกโหนดในเครือข่าย ก่อนอื่น โหนดแต่ละโหนดในเครือข่ายจะจดจำหมายเลขลำดับของข้อความสถานะลิงก์ล่าสุดที่ได้รับจากโหนดเพื่อนบ้านแต่ละโหนดเมื่อโหนดใดได้รับข้อความแจ้งสถานะลิงก์ โหนดนั้นจะตรวจสอบหมายเลขลำดับที่เก็บไว้สำหรับแหล่งที่มาของข้อความสถานะลิงก์นั้น หากข้อความนี้ใหม่กว่า (เช่น มีหมายเลขลำดับสูงกว่า) ข้อความนั้นจะถูกบันทึก หมายเลขลำดับจะถูกอัปเดต และสำเนาจะถูกส่งไปยังโหนดเพื่อนบ้านแต่ละโหนด กระบวนการนี้จะทำให้สำเนาของข้อความแจ้งสถานะลิงก์เวอร์ชันล่าสุดของแต่ละโหนดส่งไปยังทุกโหนดในเครือข่ายได้อย่างรวดเร็ว

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

การคำนวณตารางเส้นทาง

ขั้นตอนหลักที่สองในอัลกอริธึมสถานะลิงก์คือการสร้างตารางเส้นทางโดยการตรวจสอบแผนที่ แต่ละโหนดจะรันอัลกอริธึม อย่างอิสระ บนแผนที่เพื่อกำหนดเส้นทางที่สั้นที่สุดจากตัวมันเองไปยังทุกโหนดอื่นในเครือข่าย โดยทั่วไป จะใช้ อัลกอริธึมของ Dijkstra ในรูปแบบต่างๆ โหนดจะเก็บรักษาโครงสร้างข้อมูลสองแบบ ได้แก่โครงสร้างข้อมูลแบบต้นไม้ซึ่งประกอบด้วยโหนดที่ "เสร็จสิ้น" และรายการของโหนดที่อาจเป็นไปได้ อัลกอริธึมเริ่มต้นด้วยโครงสร้างทั้งสองว่างเปล่า จากนั้นจะเพิ่มตัวโหนดเองเข้าไปในโครงสร้างแรก อัลก อริธึมแบบโลภ (greedy algorithm) ใน รูปแบบต่างๆจะทำซ้ำขั้นตอนต่อไปนี้:

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

ขั้นตอนทั้งสองนี้จะถูกทำซ้ำไปเรื่อยๆ ตราบใดที่ยังมีโหนดเหลืออยู่ในรายการผู้สมัคร (เมื่อไม่มีโหนดเหลือแล้ว โหนดทั้งหมดในเครือข่ายจะถูกเพิ่มเข้าไปในต้นไม้) กระบวนการนี้จะสิ้นสุดลงเมื่อต้นไม้มีโหนดทั้งหมดในเครือข่าย สำหรับโหนดปลายทางใดๆ เส้นทางที่ดีที่สุดสำหรับปลายทางนั้นคือโหนดที่เป็นขั้นแรกจากโหนดราก ลงไปตามกิ่งในต้นไม้เส้นทางที่สั้นที่สุดซึ่งนำไปสู่โหนดปลายทางที่ต้องการ

การเพิ่มประสิทธิภาพอัลกอริทึม

ทุกครั้งที่มีการเปลี่ยนแปลงในแผนที่การเชื่อมต่อ จำเป็นต้องคำนวณโครงสร้างเส้นทางที่สั้นที่สุดใหม่ จากนั้นจึงสร้างตารางการกำหนดเส้นทางขึ้นใหม่ บริษัท BBN Technologies ค้นพบวิธีการคำนวณเฉพาะส่วนของโครงสร้างเส้นทางที่อาจได้รับผลกระทบจากการเปลี่ยนแปลงในแผนที่เท่านั้น

การลดโทโพโลยี

ในบางกรณี การลดจำนวนโหนดที่สร้างข้อความ LSA ถือเป็นเรื่องสมเหตุสมผล ด้วยเหตุนี้ จึงสามารถใช้กลยุทธ์การลดโทโพโลยีได้ โดยที่โหนดเครือข่ายเพียงบางส่วนเท่านั้นที่สร้างข้อความ LSA แนวทางการลดโทโพโลยีที่ได้รับการศึกษาอย่างกว้างขวางสองวิธี ได้แก่รีเลย์แบบหลายจุดซึ่งเป็นพื้นฐานของOptimized Link State Routing Protocol (OLSR) แต่ก็ได้รับการเสนอสำหรับ OSPF ด้วยเช่นกัน^{[ 13 ]}และชุดครอบงำที่เชื่อมต่อกันซึ่งได้รับการเสนอสำหรับ OSPF อีกครั้ง^{[ 14 ]}

การกำหนดเส้นทางรัฐฟิชอาย

ในการกำหนดเส้นทางแบบ Fisheye State Routing (FSR) ข้อความ LSA จะถูกส่งด้วยค่า time-to-live ที่แตกต่างกัน เพื่อจำกัดการแพร่กระจายและลดภาระงานที่เกิดจากข้อความควบคุม แนวคิดเดียวกันนี้ยังใช้ในHazy Sighted Link State Routing Protocolด้วย

โหมดความล้มเหลว

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

สิ่งนี้สามารถเกิดขึ้นได้เนื่องจากแต่ละโหนดคำนวณต้นไม้เส้นทางที่สั้นที่สุดและตารางการกำหนดเส้นทางโดยไม่โต้ตอบกับโหนดอื่นใด หากสองโหนดเริ่มต้นด้วยแผนที่ที่แตกต่างกัน อาจเกิดสถานการณ์ที่ลูปการกำหนดเส้นทางถูกสร้างขึ้น ในบางสถานการณ์ ลูปที่แตกต่างกันอาจถูกเปิดใช้งานภายในสภาพแวดล้อมมัลติคลาวด์ โหนดการเข้าถึงแบบแปรผันผ่านโปรโตคอลอินเทอร์เฟซอาจหลีกเลี่ยงปัญหาโหนดการเข้าถึงพร้อมกันได้เช่นกัน^{[ 15 ]}