- خوارزمية ناقل المسافة هي خوارزمية ديناميكية.
- يتم استخدامه بشكل أساسي في ARPANET و RIP.
- يحتفظ كل جهاز توجيه بجدول مسافة يُعرف باسم المتجه .
ثلاثة مفاتيح لفهم عمل خوارزمية توجيه ناقل المسافة:
خوارزمية توجيه متجه المسافة
دع دس(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) = ∞ 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 & E. B sends its routing table to A & C. C sends its routing table to B & D. D sends its routing table to E & C. E sends its routing table to A & 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). الخيار الأول هو الأقل تكلفة، لذلك يتم الاحتفاظ به وإسقاط الخيار الثاني.
- تستمر عملية إنشاء جدول التوجيه لجميع أجهزة التوجيه. يتلقى كل جهاز توجيه المعلومات من الأجهزة المجاورة، ويقوم بتحديث جدول التوجيه.
فيما يلي جداول التوجيه النهائية لجميع أجهزة التوجيه: