خوارزميات التوجيه

تحسب خوارزميات التوجيه المسارات التي تتبعها الحزم عبر الشبكة، عادةً عن طريق إيجاد مسارات الأقل تكلفة عبر رسم بياني للموجهات والروابط باستخدام إما عرض حالة الرابط الشامل أو حساب متجه المسافة الموزع من جار إلى جار.

Definition

خوارزمية التوجيه هي إجراء يحدد مسارات الأقل تكلفة (أو المفضلة بطريقة أخرى) عبر شبكة مصممة كرسوم بيانية مرجحة، وتنتج قرارات التوجيه التي تستخدمها الموجهات لنقل الحزم نحو وجهاتها.

Scope

يغطي هذا الموضوع الخوارزميات التي تملأ جداول التوجيه: نموذج الرسم البياني للشبكة مع تكاليف الروابط؛ توجيه حالة الرابط باستخدام خوارزمية أقصر مسار لديجكسترا مع طوبولوجيا مشتركة عالميًا؛ توجيه متجه المسافة باستخدام حساب بيلمان-فورد الموزع مع تبادلات الجيران؛ سلوك تقاربها والاعتلالات مثل مشكلة العد إلى اللانهاية؛ والتوجيه الهرمي لقابلية التوسع. يعالج الخوارزميات بشكل مجرد، تاركًا البروتوكولات الملموسة (OSPF, RIP, BGP) وتنظيمها داخل/بين النطاقات لموضوع بروتوكولات التوجيه.

Core questions

• كيف يتم نمذجة الشبكة كرسوم بيانية مرجحة للتوجيه؟
• كيف تحسب خوارزمية حالة الرابط أقصر المسارات من عرض طوبولوجي كامل؟
• كيف تتقارب خوارزمية متجه المسافة باستخدام تبادلات الجيران فقط؟
• ما هي مشاكل التقارب والاستقرار، مثل العد إلى اللانهاية، وكيف يتم التخفيف منها؟
• لماذا يتم جعل التوجيه هرميًا، وكيف يؤثر ذلك على مثالية المسار؟

Key concepts

• رسوم بيانية شبكية مرجحة
• مسارات الأقل تكلفة
• توجيه حالة الرابط
• خوارزمية ديجكسترا
• توجيه متجه المسافة
• معادلة بيلمان-فورد
• مشكلة العد إلى اللانهاية
• الأفق المقسم والانعكاس المسموم
• التوجيه الهرمي

Key theories

توجيه حالة الرابط (ديجكسترا)

يقوم كل موجه بإغراق تكاليف روابطه بحيث تشارك جميع الموجهات الطوبولوجيا الكاملة، ثم يقوم كل موجه بشكل مستقل بتشغيل خوارزمية ديجكسترا لحساب أقصر المسارات؛ يتقارب هذا بسرعة وبشكل يمكن التنبؤ به ولكنه يتطلب تبادل معلومات عالمي.

توجيه متجه المسافة (بيلمان-فورد)

تتبادل الموجهات تقديراتها الحالية لأقل تكلفة لكل وجهة مع جيرانها وتحدثها عبر معادلة بيلمان-فورد؛ الحساب موزع ويستخدم معلومات محلية فقط ولكنه قد يتقارب ببطء ويعاني من مشكلة العد إلى اللانهاية.

التوجيه الهرمي

نظرًا لأن التوجيه المسطح لا يتوسع ليشمل الإنترنت بأكمله، يتم تجميع الموجهات في مناطق (أنظمة مستقلة) مع معالجة التوجيه محليًا داخل كل منطقة وتلخيصه بينها، مما يضحي ببعض مثالية المسار من أجل قابلية التوسع والاستقلالية الإدارية.

Clinical relevance

تحدد خوارزميات التوجيه مدى كفاءة وموثوقية تدفق حركة المرور: خوارزميات حالة الرابط تكمن وراء البروتوكولات الداخلية مثل OSPF التي تتقارب بسرعة بعد الأعطال، بينما تظهر أفكار متجه المسافة في RIP وفي نهج متجه المسار لـ BGP. يعد فهم سلوك تقاربها ضروريًا لتصميم شبكات مستقرة وتشخيص حلقات التوجيه والتعافي البطيء بعد أعطال الرابط أو الموجه.

History

تسبق خوارزميات أقصر مسار التي هي جوهر التوجيه شبكات الكمبيوتر: عمل بيلمان وفورد على مشاكل التوجيه في أواخر الخمسينيات وخوارزمية أقصر مسار لديجكسترا عام 1959. مع نمو شبكات الحزم، تم تكييف هذه الخوارزميات لتصبح توجيه متجه المسافة وتوجيه حالة الرابط، وجعل الهيكل الهرمي في أنظمة مستقلة التوجيه يتوسع إلى الإنترنت العالمي.

Debates

توجيه حالة الرابط مقابل توجيه متجه المسافة

يتقارب توجيه حالة الرابط بسرعة ويتجنب مشكلة العد إلى اللانهاية ولكنه يتطلب من كل موجه الاحتفاظ بالطوبولوجيا الكاملة والقيام بمزيد من الحسابات، بينما توجيه متجه المسافة أبسط وأكثر محلية ولكنه قد يتقارب ببطء ويشكل حلقات عابرة؛ تجمع الشبكات الحقيقية بين الفكرتين على نطاقات مختلفة.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

ما هي مشكلة العد إلى اللانهاية؟

إنها اعتلال في متجه المسافة حيث، بعد فشل رابط، تزيد الموجهات ببطء تقديراتها للمسافة إلى وجهة غير قابلة للوصول عن طريق تبادل معلومات قديمة، معتقدة خطأً أن المسار لا يزال موجودًا عبر بعضها البعض. تشمل التخفيفات الأفق المقسم، والانعكاس المسموم، وتحديد الحد الأقصى للمسافة.

لماذا يتم استخدام كل من حالة الرابط ومتجه المسافة؟

إنهما يناسبان نطاقات مختلفة. توفر بروتوكولات حالة الرابط مثل OSPF تقاربًا سريعًا وخاليًا من الحلقات ضمن نطاق إداري واحد حيث يكون مشاركة الطوبولوجيا الكاملة مقبولاً. تتوسع مناهج متجه المسافة ومتجه المسار بشكل أفضل وتكشف تفاصيل داخلية أقل عبر النطاقات، وهذا هو السبب في أن BGP يستخدم تصميم متجه المسار بين الشبكات.