خوارزمية التحديث المنتشر

خوارزمية التحديث المنتشر ( DUAL ) هي الخوارزمية التي يستخدمها بروتوكول التوجيه EIGRP من سيسكو ^{[ 1 ]} لضمان إعادة حساب أي مسار بشكل شامل كلما كان من المحتمل أن يتسبب في حلقة توجيه . وقد طوّرها جيه جيه غارسيا لونا أسيفيس في معهد SRI الدولي . الاسم الكامل للخوارزمية هو آلة الحالة المحدودة DUAL (DUAL FSM). يتولى بروتوكول EIGRP مسؤولية التوجيه داخل النظام المستقل ، وتستجيب خوارزمية DUAL للتغيرات في بنية التوجيه وتُعدّل جداول التوجيه الخاصة بالموجّه تلقائيًا.

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

عندما لا يتوفر مسار مناسب إلى الوجهة، تستخدم خوارزمية DUAL ^{[ 2 ]} عملية حسابية مُشتِّتة ^{[ 3 ]} لضمان إزالة جميع آثار المسار المُشكِل من الشبكة. وعندها تُستخدم خوارزمية بيلمان-فورد العادية لاستعادة مسار جديد.

يستخدم بروتوكول DUAL ثلاثة جداول منفصلة لحساب المسارات. تُنشأ هذه الجداول باستخدام المعلومات المتبادلة بين أجهزة توجيه EIGRP. تختلف هذه المعلومات عن تلك المتبادلة في بروتوكولات توجيه حالة الارتباط . في EIGRP، تشمل المعلومات المتبادلة المسارات، و" مقياس " أو تكلفة كل مسار، والمعلومات اللازمة لتكوين علاقة الجوار (مثل رقم النظام المستقل، والمؤقتات، وقيم K). فيما يلي شرح مفصل للجداول الثلاثة ووظائفها:

• يحتوي جدول الجوار على معلومات حول جميع أجهزة التوجيه الأخرى المتصلة مباشرةً. يوجد جدول منفصل لكل بروتوكول مدعوم (IP، IPX، إلخ). يتوافق كل إدخال مع جار، مع وصف لواجهة الشبكة وعنوانها. بالإضافة إلى ذلك، يتم تهيئة مؤقت لتفعيل الكشف الدوري عن حالة الاتصال. يتم ذلك من خلال حزم "Hello" . إذا لم يتم استلام حزمة "Hello" من جار لفترة زمنية محددة، يُفترض أن جهاز التوجيه معطل ويتم حذفه من جدول الجوار.
• يحتوي جدول الطوبولوجيا على مقياس (معلومات التكلفة) جميع المسارات إلى أي وجهة داخل النظام المستقل. تُستقى هذه المعلومات من أجهزة التوجيه المجاورة الموجودة في جدول الجوار. يتم تحديد المسارات الأساسية (الخلف) والثانوية (الخلف الممكن) إلى الوجهة باستخدام المعلومات الموجودة في جدول الطوبولوجيا. من بين أمور أخرى، يحتوي كل إدخال في جدول الطوبولوجيا على ما يلي:

"FD (المسافة الممكنة)): المقياس المحسوب للمسار إلى وجهة داخل النظام المستقل.

"RD (المسافة المُبلغ عنها)": هي المقياس إلى وجهة معينة كما يُعلن عنها جهاز توجيه مجاور. تُستخدم RD لحساب FD، ولتحديد ما إذا كان المسار يفي بشرط الجدوى.

حالة المسار : يُصنّف المسار إما على أنه "نشط" أو "غير نشط". المسارات "غير النشطة" مستقرة ويمكن استخدامها لنقل البيانات. أما المسارات "النشطة" فيتم إعادة حسابها، و/أو أنها غير متاحة.

• يحتوي جدول التوجيه على أفضل مسار (أو مسارات) إلى وجهة معينة (من حيث أقل "مقياس"). هذه المسارات هي المسارات اللاحقة لجدول الطوبولوجيا.

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

لكي يصبح مسار ما مسارًا بديلًا مناسبًا، يجب أن يكون بُعده المرجعي (RD) أصغر من بُعد المسار البديل (FD). إذا تحقق شرط الجدوى هذا، فلا يمكن أن تؤدي إضافة هذا المسار إلى جدول التوجيه إلى حدوث حلقة.

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

أسطورة:

+ = جهاز التوجيه

- أو | = رابط

(X) = مقياس الرابط

 أ (2) ب (1) ج + - - - - - + - - - - - + | | (2)| | (3) | | + - - - - - + د (1) هـ

الآن، يرغب عميل على جهاز التوجيه E في التواصل مع عميل على جهاز التوجيه A. وهذا يعني ضرورة وجود مسار بين جهاز التوجيه A وجهاز التوجيه E. ويتم حساب هذا المسار كما يلي:

الجيران المباشرون للموجه E هما الموجه C والموجه D. يطلب الأمر DUAL في الموجه E المسافة المُبلغ عنها (RD) من الموجهين C و D على التوالي إلى الموجه A. وفيما يلي النتائج:

الوجهة: جهاز التوجيه أ

عبر D: RD(4)

عبر C: RD(3)

وبالتالي، فإن المسار عبر C هو الأقل تكلفة. في الخطوة التالية، تُضاف المسافة من الموجه E إلى الجيران إلى المسافة المُبلغ عنها للحصول على المسافة الممكنة (FD):

الوجهة: جهاز التوجيه أ

عبر D: RD(4)، FD(5)

عبر C: RD(3)، FD(6)

وبناءً على ذلك، يجد نظام DUAL أن المسار عبر D هو الأقل تكلفة إجمالية. عندئذٍ، يُصنّف المسار عبر D على أنه "مسار بديل"، ويُمنح حالة سلبية، ويُسجّل في جدول التوجيه. أما المسار عبر C فيُحتفظ به على أنه "مسار بديل مُمكن"، لأن قيمة RD الخاصة به أقل من قيمة FD للمسار البديل.

الوجهة: جهاز التوجيه أ

عبر D: RD(4)، FD(5) الخلف

عبر C: RD(3)، FD(6) خليفة ممكن