اقرأ في هذا المقال
- ما هو بروتوكول توجيه متجه المسافات
- أساسيات خوارزمية توجيه متجه المسافة
- ما هي خوارزمية بيلمان فورد في خوارزمية توجيه متجه المسافة
- كيفية عمل خوارزمية توجيه متجه المسافة
- ميزات خوارزمية توجيه متجه المسافات
- ماهي مفاتيح عمل خوارزمية توجيه متجه المسافة
- كيفية إنشاء جدول التوجيه وتحديثه في خوارزمية توجيه متجه المسافة
تُعرف خوارزمية توجيه متجه المسافات بأسماء أخرى، حيث يتم توزيع خوارزمية التوجيه “Bellman-Ford” وخوارزمية “Ford-Fulkerson”، وذلك بشكل عام بعد أن أنشأها الباحثون “Bellman” و”Ford and Fulkerson”.
ما هو بروتوكول توجيه متجه المسافات
بروتوكول توجيه متجه المسافات: هو بروتوكول “توجيه ديناميكي”، وباستخدام هذا البروتوكول يقوم كل جهاز توجيه في الشبكة بإنشاء جدول توجيه يساعده في تحديد أقصر مسار عبر الشبكة، وجميع أجهزة التوجيه في الشبكة على دراية بكل جهاز توجيه آخر في الشبكة وتستمر في تحديث جدول التوجيه الخاص بها بشكل دوري ويستخدم هذا البروتوكول مبدأ خوارزمية بيلمان-فورد.
أساسيات خوارزمية توجيه متجه المسافة
كل مسار له بعض التكلفة أو المسافة المرتبطة به والتي يجب على مخطط البيانات سدادها للانتقال من عقدة إلى أخرى، حيث تُعد المسارات ذات التكلفة الأقل أكثر جاذبية ويتم تفضيلها على المسار بتكلفة أكبر للوصول إلى الوجهة، كما ينظم كل جهاز توجيه في النظام هذه المعلومات في جدول متجه مسافات أو جدول توجيه.
يقوم كل جهاز توجيه بالإعلان عن جدول توجيه متجه المسافات هذا إلى أجهزة التوجيه المجاورة له فقط بعد فترات منتظمة، حيث تستخدم أجهزة التوجيه التي تتلقى هذا الإعلان متجه المسافات لتحديث جدول التوجيه الخاص بها وحساب أقصر مسار عبر الشبكة، وبعد التحديث ترسل أجهزة التوجيه جدول متجه مسافة محدث إلى أجهزة التوجيه المجاورة، وبالتالي يتم تحديث جدول التوجيه لكل جهاز توجيه بشكل دوري.
ما هي خوارزمية بيلمان فورد في خوارزمية توجيه متجه المسافة
يستخدم بروتوكول توجيه متجه المسافات المبدأ الأساسي لخوارزمية “Bellman-Ford” لتحديد أقصر مسار عبر الشبكة، حيث يرتبط كل مسار يربط بين العقد بالتكلفة لذلك لحساب أقصر مسافة اتبع الخطوات التالية:
- مبدئياً، يتم تعيين التكلفة أو المسافة بين العقدة نفسها على 0.
- يتم تعيين تكلفة أي عقدة لأي عقدة أخرى على اللانهاية “∞” إذا لم تكن العقد متصلة بشكل مباشر.
- يتم حساب الحد الأدنى للمسافة بين العقدتين في الرسم البياني باستخدام الطريقة “dig = minute {(Ci1 + D1j) ، (Ci2 + D2j) ، … (CiN + DNj)} |”، حيث أنّ “Dij” هي أقصر مسافة بين العقدة i وj و”Ci1cost” بين العقدة i والعقدة 1.
- تتكرر هذه الخوارزمية حتى نجد أقصر متجه مسافة بين عقدتين.
كيفية عمل خوارزمية توجيه متجه المسافة
تم تصميم خوارزمية “Bellman-Ford” بحيث يكون هناك جميع المعلومات الأولية حول كل عقدة في الرسم البياني في نفس المكان، لذلك تمكنت خوارزمية “Bellman-Ford” من توليد نتيجة لكل عقدة بشكل متزامن.
في خوارزمية توجيه متجه المسافات يتعين إنشاء جدول التوجيه لأجهزة التوجيه في النظام المستقل وفي النظام الذاتي يمكن أن تكون هناك تغييرات، مثل إضافة جهاز توجيه جديد إلى النظام أو أنّ بعض الشبكات أوقفت الخدمات إلى جهاز التوجيه أو فشل الارتباط.
في مثل هذه الحالات يجب تحديث جدول التوجيه لكل جهاز توجيه بشكل غير متزامن، وذلك لأنّ جهاز التوجيه يجب أن يقوم بتحديث جدول التوجيه الخاص به على أساس المعلومات، والتي يتلقاها من أجهزة التوجيه المجاورة له ولذلك تحتاج خوارزمية “Bellman-Ford” إلى التعديل لتكوين خوارزمية توجيه متجه المسافات:
- في خوارزمية توجيه متجه المسافات، يتم اعتبار التكلفة على أنها عدد القفزات أي عدد الشبكات التي تم إرسالها للانتقال إلى العقدة الوجهة.
- لذلك تم تعيين التكلفة بين جهازي توجيه متجاورين على 1.
- يعمل كل جهاز توجيه بتطوير جدول التوجيه الخاص به عندما يتلقى المعلومات أي متجه المسافة من أجهزة التوجيه المجاورة.
- بعد تطوير جدول التوجيه الخاص به، يجب على جهاز التوجيه إعادة توجيه نتائجه إلى جهاز التوجيه المجاور، وحتى يتمكنوا من تحديث جدول التوجيه الخاص بهم.
- يحتفظ كل جهاز توجيه بالمعلومات الثلاثة في جدول التوجيه الخاص به، أي الشبكة الوجهة والتكلفة والخطوة التي تليها.
- يرسل جهاز التوجيه معلومات كل مسار كسجل “R”.
ميزات خوارزمية توجيه متجه المسافات
- ترسل أجهزة التوجيه معرفة إطار العمل المستقل بالكامل.
- يتم تبادل البيانات مع الجيران فقط.
- يتم تعليق إرسال البيانات على فترات منتظمة ثابتة، يعلن عنها كل “30 ثانية”.
- في هذه الخوارزمية يعمل كل جهاز توجيه بتقدير المسافة بينه وبين كل وجهة يمكن الوصول إليها.
- يتم تحقيق ذلك من خلال تقييم المسافة بين جهاز التوجيه وجميع أجهزة التوجيه المجاورة له وإضافة حسابات أجهزة التوجيه المجاورة للمسافة بين هذا الجار وجيرانه القريبين.
ماهي مفاتيح عمل خوارزمية توجيه متجه المسافة
أولاً: معرفة حول الشبكة بالكامل
- يرسل كل جهاز توجيه معرفته حول الشبكة بالكامل.
- ينقل جميع معارفه المتصلة بالشبكة إلى جيرانه.
ثانياً: التوجيه فقط إلى الجيران
- يشارك كل مسار المعلومات التي لديه حول الشبكة بشكل متكرر فقط مع أجهزة التوجيه تلك مع الاتصال المناسب.
- ينقل أي معرفة لديه عن الشبكة الكاملة بجميع أجزائها.
- يتم الحصول على هذه البيانات وحفظها من خلال كل جهاز توجيه مجاور ويمكنها ترقية بيانات أجهزة التوجيه الخاصة بالشبكة.
ثالثاً: تبادل المعلومات على فترات منتظمة
- في توجيه متجه المسافات، يبعث كل موجه بشكل متكرر المعلومات التي يمتلكها حول الشبكة بأكملها مع جيرانه.
- وعلى سبيل المثال بعد “40 ثانية” يشارك كل جهاز توجيه بياناته حول شبكة جاره بالكامل.
- كما أنّه في الشبكات المحلية يكون الرقم المتوفر داخل كل مربع مستطيل هو معرف شبكة “LAN“.
- ترتبط شبكات “LAN” هذه بجهاز توجيه، موصوفاً في المربعات مثل A وB وC وD وE.
- تشير المربعات المربعة إلى اتصال أجهزة التوجيه بجيرانها.
كيفية إنشاء جدول التوجيه وتحديثه في خوارزمية توجيه متجه المسافة
- يحتوي هذا الجدول على ثلاثة أعمدة تحتوي على معلومات حول معرف الشبكة والتكلفة والخطوة التالية ويجب ترك الجداول الأصلية لكل جهاز توجيه تكون.
- سيقوم كل جهاز توجيه بتحديث نفسه وما إلى ذلك.
- يتم التحقق من خوارزمية التحديث من قيام جهاز التوجيه أولاً بإضافة قفزة إلى حقل عدد القفزات لكل مسار معلن عنه.
- يجب أن يطبق جهاز التوجيه هذه القواعد.
- إذا لم تكن الوجهة المعروضة موجودة في جدول التوجيه، فيجب على جهاز التوجيه إدخال تلك البيانات المعروضة في الجدول.
- إذا كانت الوجهة المعروضة موجودة في جدول التوجيه، فيمكن أن يحدث شيئين.
- إذا كان حقل الخطوة التالية مشابهاً، يجب على جهاز التوجيه استعادة إدخال الجدول مع الإدخال المعروض.
- إذا لم يكن حقل القفزة التالية مشابهاً وإذا كان عدد القفزات المعروضة أقل من الموجود على الجدول، فيجب على جهاز التوجيه استعادة الإدخال في الجدول مع الإدخال الجديد.
- إذا لم يكن عدد القفزات المعروضة أقل، فلا يجب على جهاز التوجيه فعل أي شيء.
