اقرأ في هذا المقال
- ما هي خوارزمية تحديث توجيه حالة الارتباط
- مفاتيح فهم خوارزمية توجيه حالة الارتباط
- مراحل خوارزمية توجيه حالة الارتباط
- رموز خوارزمية توجيه حالة الارتباط
- أساسيات خوارزمية توجيه حالة الارتباط
من عيوب خوارزمية تحديث توجيه حالة الارتباط يتم إنشاء حركة مرور كثيفة في توجيه حالة الخط بسبب فيضان البيانات، كما يمكن أن يتسبب الفيضان في حدوث حلقات لا نهائية ويمكن حل هذه المشكلة باستخدام حقل الوقت للمغادرة وتنظيم نقل البيانات.
ما هي خوارزمية تحديث توجيه حالة الارتباط
خوارزمية توجيه حالة الارتباط: هو تقنية يشارك فيها كل جهاز توجيه معرفة جواره مع كل جهاز توجيه آخر في الشبكة البينية.
مفاتيح فهم خوارزمية توجيه حالة الارتباط
أولاً: المعرفة حول الحي
بدلاً من إرسال جدول التوجيه الخاص به يرسل جهاز التوجيه المعلومات حول الحي فقط، ويبث جهاز التوجيه هوياته وتكلفة الارتباطات المتصلة مباشرة بأجهزة التوجيه الأخرى.
ثانياً: الفيضان
يرسل كل جهاز توجيه المعلومات إلى كل جهاز توجيه آخر على الشبكة البينية باستثناء جيرانه، وتُعرف هذه العملية بالفيضان، كما يرسل كل جهاز توجيه يستقبل الحزمة النسخ إلى جميع الأجهزة المجاورة وأخيراً يتلقى كل جهاز توجيه نسخة من نفس المعلومات.
ثالثاً: مشاركة المعلومات
يرسل جهاز التوجيه المعلومات إلى كل جهاز توجيه آخر فقط عند حدوث التغيير في المعلومات.
مراحل خوارزمية توجيه حالة الارتباط
أولاً: فيضانات موثوقة
- الحالة الأولية: تعرف كل عقدة تكلفة جيرانها.
- الحالة النهائية: تعرف كل عقدة الرسم البياني بأكمله.
ثانياً: حساب الطريق
- تستخدم كل عقدة خوارزمية “Dijkstra” على الرسم البياني لحساب المسارات المثلى لجميع العقد.
- تُعرف خوارزمية توجيه حالة الارتباط أيضاً باسم خوارزمية “Dijkstra” التي تُستخدم للعثور على أقصر مسار من عقدة إلى كل عقدة أخرى في الشبكة.
- خوارزمية “Dijkstra” هي خوارزمية تكرارية ولها خاصية أنّه بعد التكرار “kth” للخوارزمية، فإنّ المسارات الأقل تكلفة معروفة جيداً لعقد الوجهة k.
رموز خوارزمية توجيه حالة الارتباط
- c (i، j): تكلفة الارتباط من العقدة i إلى العقدة j، وإذا لم يتم ربط العقدتين i وj بشكل مباشر فإنّ c (i ، j) = ∞.
- D (v): يحدد تكلفة المسار من الكود المصدري إلى الوجهة v بأقل تكلفة حالياً.
- P (v): تحدد العقدة السابقة أي المجاورة لـ “v” جنباً إلى جنب مع المسار الحالي الأقل تكلفة من المصدر إلى “v”.
- N: هو العدد الإجمالي للعقد المتاحة في الشبكة.
أساسيات خوارزمية توجيه حالة الارتباط
في التوجيه عن بعد تعرف كل عقدة حداً أدنى من طوبولوجيا الشبكة، وفهي لا تعرف شيئاً عن الروابط التي تتجاوز تلك التي تربطها بجيرانها المباشرين، وفي نهج حالة الارتباط تحتفظ كل عقدة بأقصى قدر من معلومات الشبكة أي خريطة كاملة لجميع العقد وجميع الروابط، وبعد ذلك يتم حساب المسارات محلياً من هذه الخريطة باستخدام الخوارزمية الأقصر مساراً أولاً.
يسمح وجود هذه الخريطة ومن الناحية النظرية بحساب طرق مختلفة لمتطلبات جودة الخدمة المختلفة كما تسمح الخريطة أيضاً بحساب طريق جديد بمجرد وصول أخبار فشل المسار الحالي، ومن ناحية أخرى يجب أن تنتظر بروتوكولات متجه المسافات أخبار مسار جديد بعد فشل مسار موجود.
توزع بروتوكولات حالة الارتباط معلومات خريطة الشبكة من خلال شكل معدل لبث حالة كل ارتباط فردي حيث عندما يلاحظ أي من جانبي الرابط أنّ الارتباط قد انتهى، أو إذا لاحظت العقدة أنّ ارتباطاً جديداً أصبح متاحاً فإنّه يرسل حزم حالة الارتباط “LSPs” التي “تغمر” الشبكة، كما تسمى عملية البث هذه بالفيضان الموثوق به.
كما لا تتوافق آليات البث مع الشبكات التي تحتوي على حلقات طوبولوجية أي المسارات الزائدة عن الحاجة وقد تدور حزم البث حول الحلقة إلى ما لا نهاية، حيث يجب تصميم بروتوكولات حالة الارتباط بعناية للتأكد من أنّ كل جهاز توجيه يرى كل مزود خدمة “LSP”، وكذلك عدم تداول مزودي خدمة “LSP” بشكل متكرر.
كما يستخدم “IS-IS” الاختصار “LSP” والاختصار المفضل الذي يستخدمه “OSPF” هو “LSA”، كما يتم إرسال “LSPs” فوراً عند تغييرات حالة الارتباط، مثل التحديثات التي تم تشغيلها في بروتوكولات متجه المسافات باستثناء عدم وجود التنافس بين “الطرق السيئة” و”الطرق الصحيحة”.
من الممكن وجود حلقات توجيه سريعة الزوال، وعلى سبيل المثال إذا تلقى أحد الموجهين “LSP” لكن الآخر لم يستقبله فقد يكون لديهم عرض غير متناسق للشبكة وبالتالي يتجهون إلى بعضهم البعض، ومع ذلك بمجرد وصول “LSP” إلى جميع أجهزة التوجيه المعنية يجب أن تختفي الحلقة، كما لا توجد “شروط سباق” كما هو الحال مع توجيه متجه المسافات ويمكن أن يؤدي إلى حلقات توجيه مستمرة.
تتجنب خوارزمية إغراق حالة الارتباط المشاكل المعتادة للبث في وجود الحلقات من خلال جعل كل عقدة تحتفظ بقاعدة بيانات لجميع رسائل “LSP”، حيث يتضمن منشئ كل “LSP” هويته ومعلومات حول الارتباط الذي تم تغيير حالته وأيضاَ رقم تسلسلي، كما تحتاج أجهزة التوجيه الأخرى فقط إلى الاحتفاظ بحزمة “LSP” بأكبر رقم تسلسلي في قواعد بياناتها ويمكن التخلص من “LSPs” الأقدم.
وعندما يستقبل جهاز التوجيه “LSP”، فإنّه يتحقق أولاً من قاعدة البيانات الخاصة به لمعرفة ما إذا كان “LSP” قديماً أو حالي ولكن تم استلامه من قبل وفي هذه الحالات لم يتم اتخاذ أي إجراء آخر، ومع ذلك إذا وصل “LSP” برقم تسلسلي لم يتم رؤيته من قبل فعندئذٍ بطريقة البث النموذجية، حيث يتم إعادة إرسال “LSP” عبر جميع الروابط باستثناء واجهة الوصول.
افترض أنّ حالة الارتباط تتغير من “A – E”، حيث يرسل A إلى “LSPs” إلى C وB، وكلاهما سيرسلان “LSPs” إلى D، ولنفترض أنّ “B” تصل أولاً، ثم يقوم D بإعادة توجيه “LSP” إلى C وقد يتقاطع “LSP” المرسل C → D و”LSP” المرسل D → C على السلك، وسيتجاهل D نسخة “LSP” الثانية التي يتلقاها من C وسيتجاهل C النسخة الثانية التي يتلقاها من D.
من المهم ألّا تلتف أرقام تسلسل “LSP”، ةعادة ما تحتوي البروتوكولات التي تسمح لحقل رقمي بالالتفاف حولها على فكرة واضحة عن “النطاق النشط”، والذي يمكن استخدامه لاستنتاج أنّ الترقيم قد تم التفافه بدلاً من إعادة تشغيله، ويصعب القيام بذلك في سياق حالة الارتباط، كما يستخدم “OSPF” ترقيم تسلسل المصاصة هنا، حيث تبدأ الأرقام التسلسلية من “-231” وتزداد إلى “231-1”.
وعند هذه النقطة يلتفون حول العودة إلى الصفر وهكذا طالما أنّ الرقم التسلسلي أقل من الصفر فإنّه مضمون فريد، وفي الوقت نفسه لن يتوقف التوجيه إذا كانت هناك حاجة إلى أكثر من “231 تحديثاً، حيث تستخدم تطبيقات حالة الارتباط الأخرى أرقام تسلسل “64 بت”، وغالباً ما تمنح عمليات التنفيذ الفعلية لحالة الارتباط أقصى عمر لسجلات حالة الارتباط ويجب تجديد الإدخالات بشكل دوري.
- “LSP” هي اختصار لـ “Layered Service Provider”.
- “OSPF” هي اختصار لـ “Open Shortest Path First”.
