logo

خوارزمية توجيه متجه المسافة

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

ثلاثة مفاتيح لفهم عمل خوارزمية توجيه ناقل المسافة:

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

خوارزمية توجيه متجه المسافة

دع دس(y) هي تكلفة المسار الأقل تكلفة من العقدة x إلى العقدة y. ترتبط التكاليف الأقل بمعادلة بيلمان-فورد،

 d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} 

أين the minv هي المعادلة المأخوذة لجميع الجيران x. بعد السفر من x إلى v، إذا أخذنا في الاعتبار المسار الأقل تكلفة من v إلى y، فإن تكلفة المسار ستكون c(x,v)+dفي(ذ). أقل تكلفة من x إلى y هي الحد الأدنى لـ c(x,v)+dفي(ذ) الاستيلاء على جميع الجيران.

باستخدام خوارزمية توجيه ناقل المسافة، تحتوي العقدة x على معلومات التوجيه التالية:

  • لكل جار v، التكلفة c(x,v) هي تكلفة المسار من x إلى الجار المتصل مباشرة، v.
  • متجه المسافة x، أي Dس= [دس(y) : y في N ]، تحتوي على تكلفتها لجميع الوجهات، y، في N.
  • متجه المسافة لكل من جيرانه، أي Dفي= [دفي(y) : y in N ] لكل جار v لـ x.

توجيه متجه المسافة هو خوارزمية غير متزامنة حيث ترسل العقدة x نسخة من متجه المسافة الخاص بها إلى جميع جيرانها. عندما تستقبل العقدة x متجه المسافة الجديد من أحد المتجهات المجاورة لها، v، فإنها تحفظ متجه المسافة لـ v وتستخدم معادلة بيلمان-فورد لتحديث متجه المسافة الخاص بها. المعادلة موضحة أدناه:

سلسلة jsonobject
 d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N 

قامت العقدة x بتحديث جدول متجه المسافة الخاص بها باستخدام المعادلة أعلاه وأرسلت جدولها المحدث إلى جميع جيرانها حتى يتمكنوا من تحديث متجهات المسافة الخاصة بهم.

خوارزمية

 At each node x, <p> <strong>Initialization</strong> </p> for all destinations y in N: D<sub>x</sub>(y) = c(x,y) // If y is not a neighbor then c(x,y) = &#x221E; for each neighbor w D<sub>w</sub>(y) = ? for all destination y in N. for each neighbor w send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to w <strong>loop</strong> <strong>wait</strong> (until I receive any distance vector from some neighbor w) for each y in N: D<sub>x</sub>(y) = minv{c(x,v)+D<sub>v</sub>(y)} If D<sub>x</sub>(y) is changed for any destination y Send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to all neighbors <strong>forever</strong> 

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

دعونا نفهم من خلال مثال:

مشاركة المعلومات

خوارزمية توجيه متجه المسافة
  • في الشكل أعلاه، تمثل كل سحابة الشبكة، ويمثل الرقم الموجود داخل السحابة معرف الشبكة.
  • يتم توصيل جميع الشبكات المحلية (LAN) بواسطة أجهزة التوجيه، ويتم تمثيلها في مربعات تحمل الحروف A وB وC وD وE وF.
  • تعمل خوارزمية توجيه متجه المسافة على تبسيط عملية التوجيه من خلال افتراض أن تكلفة كل رابط هي وحدة واحدة. ولذلك يمكن قياس كفاءة الإرسال بعدد الوصلات للوصول إلى الوجهة.
  • في توجيه متجه المسافة، تعتمد التكلفة على عدد القفزات.
خوارزمية توجيه متجه المسافة

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

جدول التوجيه

تحدث عمليتان:

  • إنشاء الجدول
  • تحديث الجدول

إنشاء الجدول

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

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

على سبيل المثال:

 A sends its routing table to B, F &amp; E. B sends its routing table to A &amp; C. C sends its routing table to B &amp; D. D sends its routing table to E &amp; C. E sends its routing table to A &amp; D. F sends its routing table to A. 

تحديث الجدول

  • عندما يتلقى A جدول توجيه من B، فإنه يستخدم معلوماته لتحديث الجدول.
  • يوضح جدول التوجيه B كيف يمكن أن تنتقل الحزم إلى الشبكتين 1 و4.
  • يعتبر B مجاورًا لجهاز التوجيه A، ويمكن أن تصل الحزم من A إلى B في قفزة واحدة. لذلك، تتم إضافة 1 إلى جميع التكاليف الواردة في جدول B وسيكون المجموع هو تكلفة الوصول إلى شبكة معينة.
خوارزمية توجيه متجه المسافة
  • بعد التعديل، يقوم A بعد ذلك بدمج هذا الجدول مع الجدول الخاص به لإنشاء جدول مدمج.
خوارزمية توجيه متجه المسافة
  • قد يحتوي الجدول المدمج على بعض البيانات المكررة. في الشكل أعلاه، يحتوي الجدول المدمج لجهاز التوجيه A على البيانات المكررة، لذلك فهو يحتفظ فقط بتلك البيانات ذات التكلفة الأقل. على سبيل المثال، يمكن لـ A إرسال البيانات إلى الشبكة 1 بطريقتين. الأول، الذي لا يستخدم جهاز التوجيه التالي، لذا فهو يكلف قفزة واحدة. وتتطلب الخطوة الثانية قفزتين (من A إلى B، ثم من B إلى الشبكة 1). الخيار الأول هو الأقل تكلفة، لذلك يتم الاحتفاظ به وإسقاط الخيار الثاني.
خوارزمية توجيه متجه المسافة
  • تستمر عملية إنشاء جدول التوجيه لجميع أجهزة التوجيه. يتلقى كل جهاز توجيه المعلومات من الأجهزة المجاورة، ويقوم بتحديث جدول التوجيه.

فيما يلي جداول التوجيه النهائية لجميع أجهزة التوجيه:

خوارزمية توجيه متجه المسافة