أساسيات الشبكات توجيه Routing الرزم ضمن الشبكات الحاسوبية

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

اقتباس

نعيد التأكيد على تمييزٍ مهمٍ بين التمرير forwarding والتوجيه routing. إذ يتكون التمرير من استلام رزمة والبحث عن عنوان وجهتها في جدول، ثم إرسال الرزمة في اتجاه يحدّده هذا الجدول. وقد رأينا عدّة أمثلة عن عمليات التمرير سابقًا. فهي عملية بسيطة ومحدَّدة جيدًا تُجرى محليًا في كلّ عقدة، وغالبًا ما يشار إليها على أنّها مستوى بيانات data plane الشبكة. أمّا التوجيه فهو العملية التي تُنشَأ من خلالها جداول التمرير، إذ يعتمد على خوارزميات موزَّعة ومعقدة، وغالبًا ما يُشار إليه باسم مستوى التحكم control plane في الشبكة.

سنميّز الآن بين مصطلحي جدول التمرير وجدول التوجيه. حيث يُستخدَم جدول التمرير عند تمرير الرزمة، وبالتالي يجب أن يحتوي على معلومات كافية لإنجاز وظيفة التمرير. أي أنه لابد أن يحتوي كل صف في جدول التمرير على ربطٍ بين بادئة شبكة مع واجهة صادرة وبعض معلومات MAC، مثل عنوان إيثرنت لموجّه القفزة التالية. ومن ناحية أخرى، يُعَدّ جدول التوجيه الجدول الذي أنشأته خوارزميات التوجيه على أساس مقدِّمة لبناء جدول التمرير. حيث يحتوي على روابطٍ mappings بين بادئات الشبكة وموجّهات القفزة التالية. كما قد يحتوي أيضًا على معلومات حول كيفية تعلّم على هذه المعلومات، بحيث يتمكن الموجّه من تحديد متى يجب عليه تجاهُل بعض المعلومات.

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

بينما يقدّم الجدول التالي مثالًا لصفٍ من جدول التمرير، والذي يحتوي على معلومات حول كيفية تمرير رزمة إلى عقدة القفزة التالية: أرسِلْ الرزمة عبر الواجهة رقم 0 مع عنوان MAC الذي هو 8:0:2b:e4:b:1:2. لاحظ أنّ آخر جزءٍ من المعلومات، يوفّره بروتوكول ARP:

نحتاج إلى تذكير أنفسنا بسؤالٍ رئيسي قبل الدخول في تفاصيل التوجيه، والذي يجب طرحه في أيّ وقت نحاول فيه بناء آلية للإنترنت: (هل يتوسّع هذا الحل؟) الإجابة عن هذا السؤال باستخدام الخوارزميات والبروتوكولات الموضَّحة في هذا القسم هي (ليست كافية جدًا). فهذه الحلول مصمَّمة لشبكات ذات حجم متواضع إلى حدٍّ يصل لبضع مئات من العقد. ولكن تعمل الحلول التي ستُشرح الآن كلبنةٍ أساسيّة لبنية التوجيه الهرمي التحتية المستخدَمة في الإنترنت اليوم. حيث تُعرَف كلّ البروتوكولات الموضَّحة في هذا القسم باسم **بروتوكولات التوجيه داخل النطاق ** intradomain routing protocols، أو **بروتوكولات البوّابة الداخلية ** interior gateway protocols أو اختصارًا IGPs. نحتاج إلى تحديد نطاق التوجيه routing domain لفهم هذه المصطلحات. والتعريف الجيد هو شبكة متشابكة internetwork تخضع فيها جميع الموجّهات لنفس التحكم الإداري (مثل حرم جامعي واحد أو شبكة مزوّد خدمة إنترنت واحدة). حيث ستظهر أهمية هذا التعريف لاحقًا عندما ننظر إلى **بروتوكولات التوجيه بين النطاقات ** interdomain routing protocols. أمّا الشيء المهم الآن فهو دراستنا لمشكلة التوجيه في سياق الشبكات الصغيرة إلى متوسطة الحجم، وليس في سياق شبكةٍ بحجم الإنترنت.

الشبكة كرسم بياني Network as a Graph

يوضِّح الشكل الآتي رسمًا بيانيًا لشبكةً سُميت عُقَد الرسم البياني فيها من A إلى F، والتي قد تكون مضيفين hosts، أو مبدّلات، أو موجّهات، أو شبكات. سنركّز في مناقشتنا الأولية على الحالة التي تكون فيها العقد عبارة عن موجّهات. حيث تتوافق أضلاع الرسم البياني مع روابط الشبكة. وكلّ ضلعٍ له تكلفة مرتبطة به، مما يعطي بعض المؤشرات على الرغبة في الإرسال عبر هذا الرابط. لاحظ أنّ نماذج الشبكات (الرسوم البيانية) المُستخدَمة في هذا المقال لها أضلاع غير موجّهة undirected edges، أُسندت إليها تكلفة واحدة. ولكن الأضلاع الموجَّهة أدق، مما يعني عادةً أنه سيكون هناك زوجٌ من الأضلاع بين كلّ عقدة، فيتدفق كلٌّ منها باتجاهٍ مختلف، بحيث يكون لكلّ منهما تكلفة ضلع خاصة به.

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

• لا يعالج فشل العقدة أو الرابط.
• لا يفرض إضافة عقد أو روابط جديدة.
• وهذا يعني أن تكاليف الضلع غير قابلة للتغيير، على الرغم من أننا قد نرغب في تغيير تكاليف الرابط بمرور الوقت (مثل إسناد تكلفة عالية لرابطٍ محمَّل كثيرًا).

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

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

افترِض أنّ تكاليف الضلع في الشبكة معروفة. سنشرح الصنفين الرئيسيتين من بروتوكولات التوجيه، وهما مُتجه المسافة distance vector، وحالة الرابط link state. لنعود إلى مشكلة حساب تكاليف الضلع بطريقة مفيدة لاحقًا.

متجه المسافة Distance-Vector باستخدام بروتوكول RIP

الاسم الشائع الآخر لهذا الصنف من الخوارزمية هو بيلمان- فورد Bellman-Ford تيمُّنًا بمخترعَيها. وفيه تبني كلّ عقدة مصفوفة أحادية البُعد (متجه) تحتوي على مسافات distances أو تكاليف costs جميع العقد الأخرى، ثم توزِّع هذا المتّجه على الجيران المباشِرين. يكون الاعتبار الأولي لتوجيه متجّه المسافة: أنّ كلّ عقدة تعرف تكلفة روابط كلّ جيرانها المتصلين مباشرةً بها. وقد تتوفّر هذه التكاليف عندما يضبط مديرُ الشبكة الموجّه. وتُسنَد تكلفة لانهائية للرابط المعطّل.

من الأسهل التفكير في مثال مشابه لذلك الموضَّح في الشكل السابق لمعرفة كيفية عمل خوارزمية توجيه متجّه المسافات. حيث تُضبَط تكلفة كلّ رابط على القيمة 1، بحيث يكون المسار الأقلّ تكلفةً هو ببساطة رابط مع أقلّ عدد من القفزات (بما أنّ جميع الأضلاع لها نفس التكلفة، فلن نعرض التكاليف في الرسم البياني). حيث يمكن تمثيل معرفة كلّ عقدة بالمسافات بينها وبين جميع العقد الأخرى بجدولً مُشابه للجدول السابق. لاحظ أنّ كلّ عقدة تعرف فقط المعلومات الموجودة في صفٍ واحد من الجدول (الذي يحمل اسم هذه العقدة في العمود الأيسر). والرؤية العامة global view المقدَّمة هنا غير متاحة في أيّ نقطة من الشبكة.

يمكن عدّ كلّ صف في الجدول السابق مثل قائمة بالمسافات بين عقدة واحدة وجميع العقد الأخرى، والتي تمثّل المعتقدات الحالية لتلك العقدة. تُحدِّد كلّ عقدة تكلفةً مقدارها 1 لجيرانها المتصلين مباشرةً، وما لا نهاية (∞) لجميع العقد الأخرى في البداية. وبالتالي تعتقد العقدة A مبدئيًا أنه من الممكن الوصول إلى العقدة B بقفزة واحدة، في حين لا يمكن الوصول إلى العقدة D. يعكس جدول التوجيه المخزَّن في العقدة A هذه المجموعة من المعتقدات ويتضمّن اسم العقدة التالية التي قد تستخدمها العقدة A للوصول إلى أيّة عقدة ممكن الوصول إليها. إذًا سيبدو جدول توجيه العقدة A في البداية مثل الجدول التالي:

الخطوة التالية في توجيه متّجه المسافة هي احتواء كل عقدة ترسل رسالة إلى جيرانها المتصلين مباشرةّ، على قائمة المسافات الشخصية الخاصة بها. حيث تُخبر العقدة F العقدة A بإمكانية وصولها إلى العقدة G بتكلفة 1، كما تعرف العقدة A أيضًا قدرتها على الوصول إلى F بتكلفة 1، لذلك تجمع هذه التكاليف للحصول على تكلفة الوصول إلى العقدة G عن طريق العقدة F. هذه التكلفة الإجمالية 2 أقل من التكلفة الحالية ∞، لذلك تسجّل العقدة A إمكانية وصولها إلى العقدة G بتكلفة 2 من خلال العقدة F. تتعلم العقدة A من العقدة C أنه يمكن الوصول إلى العقدة D عن طريق العقدة C بتكلفة 1، وتضيف هذا إلى تكلفة الوصول إلى C (1) وتقرر إمكانية الوصول إلى العقدة D عبر العقدة C بتكلفة 2، وهو أفضل من التكلفة القديمة ∞. كما تتعلم العقدة A من العقدة C إمكانية الوصول إلى العقدة B عن طريق العقدة C بتكلفة 1، لذلك تستنتج أنّ تكلفة الوصول إلى العقدة B عبر العقدة C هي 2. وبما أنّها أسوأ من التكلفة الحالية للوصول إلى B (1)، ستتجاهل المعلومات الجديدة. وعندها يمكن للعقدة A تحديث جدول التوجيه الخاص بها باستخدام التكاليف وعقد القفزة التالية وذلك لجميع العقد في الشبكة، والنتيجة موضَّحة في الجدول التالي:

لا يتطلّب الأمر سوى عددٍ قليل من عمليات تبادل المعلومات بين العقد المتجاورة، قبل احتواء كلّ عقدة على جدول توجيه كامل في حالة عدم وجود أيّ تغييرات في مخطط الشبكة. وتُسمى عملية الحصول على معلومات توجيه مستقرّة لجميع العقد بالتقارب convergence. يوضح الجدول الآتي المجموعة النهائية من التكاليف من كلّ عقدة إلى جميع العقد الأخرى عند تقارب التوجيه، أي أنّه يمثّل الرؤية العامة Global View. حيث يجب التأكيد على عدم وجود عقدة واحدة في الشبكة تحتوي على جميع المعلومات الواردة في هذا الجدول، كما تعرف كلّ عقدة فقط محتويات جدول التوجيه الخاص بها. ويكمن جمال الخوارزمية الموزعة هذه، في تمكينها لجميع العقد من تحقيق رؤية مستقرّة للشبكة في غياب وجود أية سلطة مركزية.

هناك بعض التفاصيل الواجب ملؤها قبل اكتمال مناقشتنا لتوجيه متجّه المسافة. حيث نلاحظ أولًا وجود حالتين مختلفتين تقرِّر بموجبهما عقدةٌ معيّنة إرسال تحديثٍ في التوجيه إلى جيرانها. وإحدى هاتين الحالتين هي التحديث الدوري periodic update، حيث ترسل كلّ عقدة تلقائيًا رسالة تحديث بين الحين والآخر في هذه الحالة، حتى لو لم يتغيَّر شيء. كما يعمل ذلك على السماح للعقد الأخرى بمعرفة أنّ هذه العقدة لا تزال قيد التشغيل، إلى جانب تأكُّدها من استمرار حصولها على المعلومات التي قد تحتاج إليها إذا أصبحت مساراتها الحالية غير متاحة. يختلف تكرار هذه التحديثات الدورية من بروتوكولٍ لآخر، ويتراوح عادةً من عدّة ثوانٍ إلى عدّة دقائق. أمّا الآلية الثانية التي تسمى أحيانًا التحديث المحفَّز triggered update، تحدث عندما تلاحظ العقدة فشل رابطٍ أو تتلقى تحديثًا من إحدى العقد المجاورة لها مما يتسبب في تغيير أحد المسارات في جدول التوجيه الخاص بها. حيث ترسل العقدة تحديثًا إلى العقد المجاورة لها عندما يتغيّر جدول توجيهها، مما قد يؤدّي إلى تغيير في جداول هذه العقد ويتسبب في إرسال هذه العقد بدورها تحديثًا إلى جيرانها.

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

لفهم حالة اكتشاف العقدة فشل رابط، افترض ما سيحدث عندما تكتشف العقدة F فشل الرابط الذي يربطها بالعقدة G. أولًا، تحدّد العقدة F المسافة الجديدة إلى العقدة G بالقيمة ∞، وتمرر هذه المعلومات إلى العقدة A. بما أن العقدة A تعرف أن مسارها المكوَّن من قفزتين إلى العقدة G يمر عبر العقدة F، فإن العقدة A ستحدد أيضًا المسافة إلى العقدة G بالقيمة ∞. ولكن ستتعلم العقدة A مع التحديث التالي من العقدة C أن العقدة C لديها مسارٌ مكون من قفزتين إلى العقدة G. وهكذا ستعرف العقدة A أنه من الممكن الوصول إلى العقدة G في 3 قفزات عبر العقدة C، وهذا أقل من ∞، وبالتالي ستحدّث العقدة A الجدول الخاص بها تبعًا لذلك. وعند إعلانها عن هذا إلى العقدة F، فستتعلم العقدة F أنّ بإمكانها الوصول إلى العقدة G بتكلفة 4 عبر العقدة A، وهي أقل من ∞، وسيصبح النظام مستقرًا مرةً أخرى.

قد تمنع ظروف مختلفة قليلًا استقرار الشبكة لسوء الحظ. افترض، على سبيل المثال، أن الرابط من العقدة A إلى العقدة E معطّلٌ. فتعلن العقدة A عن مسافة لا نهائية (∞) إلى العقدة E في الدورة التالية من التحديثات، لكن العقدتين B و C يعلنان عن مسافة 2 إلى العقدة E. قد يحدث ما يلي اعتمادًا على التوقيت الدقيق للأحداث: تستنتج العقدة B، عند سماع أن العقدة E يمكن الوصول إليها عبر قفزتين من العقدة C، أنه يمكن الوصول إلى العقدة E في 3 قفزات وتعلن عن ذلك إلى العقدة A، لتستنتج العقدة A أنه يمكنها الوصول إلى العقدة E في 4 قفزات وتعلن عن ذلك للعقدة C، وبالتالي تستنتج العقدة C أنه يمكنها الوصول إلى العقدة E في 5 قفزات، وهَلُمَّ جرًّا. تتوقف هذه الدورة فقط عندما تصل المسافات إلى رقم كبير بما يكفي لعدّه ∞. لا تعرف أي من العقد فعليًا أن العقدة E لا يمكن الوصول إليها في غضون ذلك، وأن جداول توجيه الشبكة لا تستقر. يُعرف هذا الموقف باسم مشكلة العد إلى اللانهاية count to infinity.

هناك عدة حلول جزئية لهذه المشكلة. الحل الأول هو استخدام عدد صغير نسبيًا كتقريب لما لا نهاية (∞). فقد نقرر أن الحد الأقصى لعدد القفزات لعبور شبكةٍ معينة لن يكون أبدًا أكثر من 16 على سبيل المثال، ولذا يمكننا اختيار القيمة 16 كقيمة تمثل اللانهاية. هذا على الأقل يحدْ من الوقت الذي يستغرقه العد إلى اللانهاية. ويمكن أن نواجه مشكلة أيضًا إذا نمت شبكتنا إلى نقطة تبعد عن بعض العقد بأكثر من 16 قفزة.

يُطلق على إحدى تقنيات تحسين وقت استقرار التوجيه اسم الانقسام الأفقي split horizon. فكرة هذه التقنية تقوم على أنه إذا أرسلت العقدة تحديث توجيه إلى العقد المجاورة لها، فإنها لا ترسل تلك المسارات إلى العقدة المجاورة التي تعلمت منها هذه المسارات. إذا احتوت العقدة B على المسار (E , 2 , A) في جدولها مثلًا، فإنها تعرف أنها تعلمت هذا المسار من العقدة A، وبالتالي كلما أرسلت العقدة B تحديث توجيه إلى العقدة A، فلا تضمّن المسار (E , 2) في هذا التحديث. يوجد شكلٌ أقوى من تقنية الانقسام الأفقي، يُسمى الانقسام الأفقي مع الانعكاس الهادم split horizon with poison reverse، حيث ترسل العقدة B بالفعل هذا المسار مرة أخرى إلى العقدة A، لكنها تضع معلومات سلبية في المسار للتأكد من أن العقدة A لن تستخدم العقدة B في النهاية للوصول إلى العقدة E. حيث ترسل العقدة B المسار (E , ∞) مثلًا إلى العقدة A. المشكلة في كلتا الطريقتين هي أنهما تعملان فقط مع حلقات التوجيه التي تتضمن عقدتين. لذلك يجب اتخاذ تدابير أكثر صرامة بالنسبة لحلقات التوجيه الأكبر. استكمالًا للمثال، لو انتظرت العقدتان B و C لفترة من الوقت بعد سماع فشل الرابط من العقدة A قبل الإعلان عن المسارات إلى العقدة E، لَكانتا قد اكتشفتَا أن أيًا منهما لم يكن لديه حقًا مسار إلى العقدة E. تؤخِّر طريقة التوجيه بمتجه المسافة لسوء الحظ من تقارب البروتوكول، فسرعة التقارب هي إحدى المزايا الرئيسية لمنافستها والتي هي طريقة التوجيه بحالة الرابط link-state routing، والتي سنتكلم عنها لاحقًا.

التطبيق Implementation

الشيفرة التي تطبق هذه الخوارزمية واضحةٌ جدًا. تحدد البنية Route كل مدخلة في جدول التوجيه، ويحدد الثابت MAX_TTL المدة التي تُحتفَظ بها مدخلةٌ في الجدول قبل التخلص منها.

#define MAX_ROUTES      128     /* الحجم الأقصى لِجدول التوجيه */
#define MAX_TTL         120     /* الوقت (مقدرًا بالثواني) حتى انتهاء صلاحية المسار */

typedef struct {
    NodeAddr  Destination;    /* عنوان الوجهة */
    NodeAddr  NextHop;        /* عنوان عقدة القفزة التالية */
    int        Cost;          /* مقياس المسافة */
    u_short   TTL;            /* (العُمر) time to live */
} Route;

int      numRoutes = 0;
Route    routingTable[MAX_ROUTES];

يعتمد الإجراء، الذي يحدّث جدول توجيه العقدة المحلية، على مسارٍ جديد يُعطَى باستخدام الدالة mergeRoute. تمسح دالة المؤقت، على الرغم من عدم ظهورها، قائمةَ المسارات في جدول توجيه العقدة دوريًا، وتقلل من حقل TTL لكل مسار، وتتجاهل أية مسارات لها زمن TTL يساوي 0. لكن لاحظ إعادة ضبط الحقل TTL بالقيمة MAX_TTL في أي وقت تُعيد فيه رسالةُ تحديثٍ قادمةٌ من عقدةٍ مجاورة تأكيدَ المسار:

void
mergeRoute (Route *new)
{
    int i;

    for (i = 0; i < numRoutes; ++i)
    {
        if (new->Destination == routingTable[i].Destination)
        {
            if (new->Cost + 1 < routingTable[i].Cost)
            {
                /* وُجِد مسارٌ أفضل */
                break;
            } else if (new->NextHop == routingTable[i].NextHop) {
                /* تغير مقياس عقدة القفزة التالية الحالية */
                break;
            } else {
                /* المسار غير جيد --- تجاهله فقط */
                return;
            }
        }
    }
    if (i == numRoutes)
    {
        /* هذا مسارٌ جديد تمامًا؛ فهل هناك حيزٌ لذلك؟ */
        if (numRoutes < MAXROUTES)
        {
            ++numRoutes;
        } else {
            /* لا يمكن احتواء هذا المسار في الجدول لذا استسلم */
            return;
        }
    }
    routingTable[i] = *new;
    /* TTL أعِد ضبط */
    routingTable[i].TTL = MAX_TTL;
    /* حساب قفزة للوصول إلى العقدة التالية */
    ++routingTable[i].Cost;
}

أخيرًا، تُعَد الإجرائية updateRoutingTable الإجرائية الرئيسية التي تستدعي الدالة mergeRoute لدمج كافة المسارات الموجودة في تحديث التوجيه الذي يصل من عقدة مجاورة.

void
updateRoutingTable (Route *newRoute, int numNewRoutes)
{
    int i;

    for (i=0; i < numNewRoutes; ++i)
    {
        mergeRoute(&newRoute[i]);
    }
}

بروتوكول معلومات التوجيه Routing Information Protocol

يُعد بروتوكول معلومات التوجيه RIP أحد بروتوكولات التوجيه الأكثر استخدامًا في شبكات IP. يرجع استخدامه على نطاق واسع منذ بدايات ظهور IP، إلى حقيقة أنه مُوزَّعٌ جنبًا إلى جنب مع إصدار يونيكس الشهير Berkeley Software Distribution الذي يُختصَرإلى BSD، والذي اُشتقَّت منه العديد من إصدارات يونيكس التجارية وهو أيضًا بسيط للغاية. بروتوكول RIP هو المثال الأساسي لبروتوكول التوجيه المبني على خوارزمية متجه المسافة الموصوفة سابقًا.

تختلف بروتوكولات التوجيه في الشبكات المتشابكة قليلًا عن نموذج الرسم البياني المثالي. الهدف من الموجّهات في الشبكة المتشابكة هو تعلم كيفية تمرير الرزم إلى شبكات مختلفة. وبالتالي تعلن الموجّهات عن تكلفة الوصول إلى الشبكات بدلًا من الإعلان عن تكلفة الوصول إلى الموجّهات الأخرى. يعلن الموجه C للموجِّه A في الشكل التالي، على سبيل المثال، حقيقةَ أنه يمكنه الوصول إلى الشبكات 2 و 3 (التي يتصل بها مباشرةً) بتكلفة 0، والشبكات 5 و 6 بتكلفة 1، والشبكة 4 بتكلفة 2.

يمكنك أن ترى دليلًا على ذلك في صيغة رزمة RIP (الإصدار 2) في الشكل الآتي. تُعالَج غالبية الرزمة بالثلاثية (العنوان، القناع، المسافة) (address, mask, distance). ولكن مبادئ خوارزمية التوجيه هي نفسها. فإذا تعلم الموجّه A، على سبيل المثال، من الموجّه B أنه يمكن الوصول إلى الشبكة X بتكلفة أقل عبر الموجّه B مقارنةً بعقدة القفزة التالية الموجودة في جدول التوجيه، فإن الموجّه A يحدّث التكلفة ومعلومات عقدة القفزة التالية لرقم الشبكة وفقًا لذلك.

بروتوكول RIP هو في الواقع تطبيق مباشر إلى حد ما لتوجيه متجه المسافة. ترسل الموجهات التي تشغّل بروتوكول RIP إعلاناتها كل 30 ثانية، حيث يرسل الموجّه أيضًا رسالة تحديث عندما يتسبب تحديثٌ من موجهٍ آخر في تغيير جدول التوجيه الخاص به. إحدى النقاط الهامة هي أن بروتوكول RIP يدعم عائلات عناوين متعددة، وليس عناوين IP فقط، وهذا هو سبب وجود الجزء Family ضمن الإعلانات. قدّم الإصدار 2 من بروتوكول RIP المسمَّى RIPv2 أيضًا أقنعة الشبكة الفرعية الموضحة سابقًا، بينما عمل الإصدار 1 من بروتوكول RIP مع عناوين IP القديمة.

يمكن استخدام مجموعة من المقاييس metrics أو التكاليف المختلفة للروابط في بروتوكول التوجيه. يتخذ بروتوكول RIP أبسط نهج، حيث تساوي جميع تكاليف الروابط القيمة 1، وبالتالي يحاول RIP دائمًا العثور على الحد الأدنى لقفز المسار. المسافات الصالحة هي من 1 إلى 15، وتمثل المسافة 16 اللانهاية. يحد هذا أيضًا من استخدام بروتوكول RIP بالعمل على شبكات صغيرة إلى حد ما، أي تلك الشبكات التي ليس لها مسارات أطول من 15 قفزة.

حالة الرابط link state باستخدام بروتوكول OSPF

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

الإغراق الموثوق Reliable Flooding

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

تنشئ كل عقدةٍ حزمة تحديث، تسمى أيضًا رزمة حالة الرابط link-state packet أو اختصارًا LSP، والتي تحتوي على المعلومات التالية:

• معرّف العقدة التي أنشأت رزمة LSP.
• قائمة بالعقد المجاورة المتصلة مباشرةً بتلك العقدة، مع تكلفة الرابط لكل منها.
• رقم تسلسلي.
• عُمر time to live هذه الرزمة.

أول عنصرين مطلوبين لتفعيل حساب المسار، و يُستخدَم العنصران الآخران في جعل عملية إغراق الرزمة لجميع العقد موثوقة. تتضمن هذه الوثوقية التأكد من أن لديك أحدث نسخة من المعلومات، حيث قد يكون هناك العديد من رزم LSP المتناقضة التي تعبر الشبكة من عقدة واحدة. ثبُتَ أن تحقيق الإغراق الموثوق أمرٌ صعب للغاية (تسبب إصدار قديم لتوجيه حالة الرابط المستخدَم في شبكة أربانت ARPANET في فشل هذه الشبكة في عام 1981 على سبيل المثال).

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

افترض العقدة X التي تتلقى نسخةً من رزمة LSP التي نشأت في عقدة أخرى هي Y. لاحظ أن العقدة Y قد تكون أي موجهٍ آخر في نفس نطاق التوجيه كالعقدة X. تتحقق العقدة X فيما إذا كانت قد خزّنت بالفعل نسخة من الرزمة LSP من العقدة Y. إن لم يحدث ذلك، فإنها تخزن رزمة LSP. وإذا كان لديها نسخة بالفعل، فإنها تقارن الأرقام التسلسلية، فإذا احتوت رزمة LSP الجديدة على رقم تسلسلي أكبر، فمن المفترض أن تكون الأحدث، وتخزّن رزمة LSP الجديدة، لتحل محل الرزمة القديمة. يشير الرقم التسلسلي الأصغر (أو المتساوي) إلى رزمة LSP أقدم (أو ليست أحدث) من الرزمة المخزَّنة، لذلك ستكون متجاهَلة وليس هناك حاجة إلى أي إجراء آخر. إذا كانت رزمة LSP المستلَمة هي الأحدث، عندها ترسل العقدة X نسخةً من رزمة LSP إلى جميع جيرانها باستثناء الجار الذي استلمت رزمة LSP منه للتو. تساعد حقيقة عدم إرسال رزمة LSP مرة أخرى إلى العقدة التي اُستلِمت منها في وضع حد لإغراق LSP. بما أن العقدة X تمرّر الرزمة LSP إلى جميع جيرانها، والذين يفعلون الشيء نفسه، فإن أحدث نسخة من رزمة LSP تصل في النهاية إلى جميع العقد.

يوضح الشكل السابق رزمة LSP المُغرَقة في شبكة صغيرة. تصبح كل عقدة مظللةً لأنها تخزّن رزمة LSP الجديدة. تصل رزمة LSP إلى العقدة X في القسم (أ) من الشكل السابق، والتي ترسلها إلى جيرانها وهما العقدتان A و C في القسم (ب) من الشكل السابق. لا ترسل العقدتان A و C رزمة LSP مرة أخرى إلى العقدة X، ولكن تُرسِلانها إلى العقدة B. بما أن العقدة B تتلقى نسختين متطابقتين من الرزمة LSP، فإنها ستقبل الرزمة التي تصل أولًا وتتجاهل الثانية كنسخةٍ مكررة. ثم تمرر رزمة LSP إلى العقدة D، والتي ليس لها جيران لِإغراقها، وتكتمل العملية.

تولّد كل عقدةٌ رزمَ LSP ضمن حالتين كما هو الحال في بروتوكول RIP. يمكن أن يتسبب انتهاء صلاحية مؤقتٍ دوري أو تغيير في مخطط الشبكة في أن تنشئ عقدةٌ رزمة LSP جديدة. ولكن السبب الوحيد المستند إلى مخطط الشبكة لأن تنشئ العقدة رزمةَ LSP هو تعطُّل أحد الروابط المتصلة مباشرةً بها أو عبر جيرانها المباشرين. يمكن الكشف عن فشل الرابط في بعض الحالات بواسطة بروتوكول طبقة الربط. يمكن اكتشاف زوال العقدة المجاورة أو فقدان الاتصال بها باستخدام الرزم الترحيبية hello packets الدورية. وترسل كل عقدةٍ هذه الرزم إلى جيرانها المباشرين على فترات زمنية محددّة. إذا مر وقت طويل وكافٍ دون تلقي رزمة ترحيبية من أحد الجيران، فستعلن بأنّ الرابط إلى هذا الجار مُعطَّل، وستنشئ رزم LSP جديدة لتبيّن هذه الحقيقة.

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

إحدى الطرق السهلة لتقليل الحِمل هي تجنب توليد رزم LSP ما لم يكن ذلك ضروريًا للغاية. ويمكن القيام بذلك باستخدام مؤقتات طويلة جدًا، غالبًا في حدود الساعات، لإنشاء رزم LSP الدورية. بما أن بروتوكول الإغراق يمكن الاعتماد عليه حقًا عند تغيُّر مخطط الشبكة، فمن الآمن افتراض أن الرسائل التي تقول "لم يتغير شيء" لا تحتاج إلى إرسالها كثيرًا.

تحمل رزم LSP أرقامًا تسلسلية للتأكد من استبدال المعلومات القديمة بمعلومات أحدث. حيث تزيد العقدة الرقم التسلسلي بمقدار 1 في كل مرة تُنشِئ فيها رزمة LSP جديدة. لا يُتوقع أن تلتف هذه الأرقام التسلسلية على عكس معظم الأرقام التسلسلية المستخدمة في البروتوكولات، لذا يجب أن يكون الحقل كبيرًا جدًا (64 بت مثلًا). إذا تعطّلت عقدة ثم عادت مرة أخرى، فإنها تبدأ برقم تسلسلي 0. وإذا كانت العقدة معطّلةً لفترة طويلة، فستنتهي مهلة جميع رزم LSP القديمة لتلك العقدة. وبخلاف ذلك، ستتلقى هذه العقدة في النهاية نسخةً من رزمة LSP الخاصة بها مع رقمٍ تسلسلي أعلى، والتي يمكنها بعد ذلك زيادة قيمتها واستخدامها كرقمٍ تسلسلي خاص بها. وسيَضمَن ذلك أن تحِل رزمة LSP الجديدة الخاصة بها محلَ أي من رزم LSP القديمة الموجودة قَبل تعطّل العقدة.

تحمل رزم LSP أيضًا عُمرًا time to live. والذي يُستخدم لضمان إزالة معلومات حالة الرابط القديمة من الشبكة. تعمل العقدة دائمًا على تقليل قيمة TTL الخاصة برزمة LSP المستلَمة حديثًا قبل إغراقها في جيرانها. كما تعمل على إعطاء عمرٍ لرزمة LSP أثناء تخزينها في العقدة. تُعيد العقدة إغراق رزمة LSP باستخدام TTL بقيمة 0، عندما تصل قيمة TTL إلى 0، والذي تفسره جميع العقد في الشبكة كإشارة لحذف رزمة LSP.

حساب المسار Route Calculation

تستطيع العقدة حساب خارطة كاملة لمخطَّط الشبكة بمجرد أن تحصل على نسخة من رزمة LSP من كل عقدة أخرى، ويمكنها تحديد أفضل مسار لكل وجهة من خلال هذه الخارطة. إذًا السؤال هو بالضبط كيف تُحسب المسارات من خلال هذه المعلومات؟ يعتمد الحل على خوارزمية معروفة جيدًا في نظرية الرسم البياني، والتي هي خوارزمية Dijkstra الأقصر مسارًا.

سنُعرِّف أولًا خوارزمية Dijkstra باستخدام مصطلحات نظرية الرسم البياني. تخيّل أن العقدة تأخذ جميع رزم LSP التي تلقتها وتبني تمثيلًا رسوميًا للشبكة، حيث يرمز N إلى مجموعة العقد في الرسم البياني، ويرمز l (i ، j) إلى التكلفة غير السلبية (الوزن) المرتبط بالضلع بين العقدتين i و j في المجموعة N بحيث تكون l (i ، j) = ∞ إن لم يكن هناك ضلع يربط العقدتين i و j. تُشير العقدة s في المجموعة N في الوصف الآتي إلى العقدة التي تنفّذ الخوارزمية للعثور على أقصر مسار لجميع العقد الأخرى في N. تحافظ الخوارزمية أيضًا على المتغيرين التاليين: M تشير إلى مجموعة العقد المتضمّنة في الخوارزمية حتى الآن، وتشير C(n) إلى تكلفة المسار من العقدة s إلى كل عقدة n. تُعرَّف الخوارزمية على النحو التالي بالنظر إلى هذه التعريفات:

M = {s}
for each n in N - {s}
    C(n) = l(s,n)
while (N != M)
    M = M + {w} such that C(w) is the minimum for all w in (N-M)
    for each n in (N-M)
    C(n) = MIN(C(n), C(w)+l(w,n))

تعمل الخوارزمية على النحو التالي: نبدأ بالمجموعة M التي تحتوي على العقدة s ثم نهيّئ جدول تكاليف (أو المصفوفة C (n)) العقد الأخرى باستخدام التكاليف المعروفة للعقد المتصلة مباشرةً. ثم نبحث عن العقدة التي يمكن الوصول إليها بأقل تكلفة (w) ونضيفها إلى المجموعة M. أخيرًا، نحدّث جدول التكاليف من خلال النظر في تكلفة الوصول إلى العقد من خلال العقدة w. نختار مسارًا جديدًا للعقدة n. في السطر الأخير من الخوارزمية، التي تمر عبر العقدة w إذا كانت التكلفة الإجمالية للانتقال من المصدر إلى العقدة w ثم من العقدة w إلى العقدة n أقلّ من المسار القديم إلى العقدة n. يتكرر هذا الإجراء حتى تصبح جميع العقد ضمن المجموعة M.

يحسب كل مبدّل جدول التوجيه الخاص به مباشرةً من رزم LSP التي جمعها باستخدام تحقيقٍ خوارزمية Dijkstra المُسماة خوارزمية البحث الأمامي forward search. حيث يحتفظ كل مبدلٍ بقائمتين، تُعرفان باسم Tentative تجريبية وConfirmed مؤكدة. تحتوي كل من هذه القوائم على مجموعة من مدخلاتٍ من النموذج (Destination, Cost, NextHop). تعمل الخوارزمية على النحو التالي:

1. هيّئ القائمة المؤكدة Confirmed بمدخلةٍ لك، هذه المدخلة لها تكلفة 0.
2. أطلق على العقدة التي أُضيفت للتو إلى القائمة Confirmed في الخطوة السابقة اسم العقدة Next وحدّد رزمة LSP الخاصة بها.
3. احسب تكلفة Cost الوصول إلى العقدة المجاورة Neighbor لكل عقدةٍ مجاورة Neighbor للعقدة Next، بحيث تساوي مجموع التكلفة من عندك إلى العقدة Next ومن العقدة Next إلى العقدة Neighbor.
   1. إن لم تكن العقدة Neighbor حاليًا في القائمة Confirmed أو في القائمة Tentative، فأضِف (Neighbor, Cost, NextHop) إلى القائمة Tentative، حيث يكون NextHop هو الاتجاه الذي تستخدمه للوصول إلى العقدة Next.
   2. إذا كانت العقدة Neighbor حاليًا في القائمة Tentative، وكانت التكلفة Cost أقل من التكلفة المدرجَة حاليًا للعقدة Neighbor، فاستبدل المدخلة الحالية بـ (Neighbor, Cost, NextHop) حيث NextHop هو الاتجاه الذي تستخدمه للوصول إلى العقدة Next.
4. إذا كانت القائمة Tentative فارغة، فتوقف. وإلا فاختر المدخلة من القائمة Tentative بأقل تكلفة، وانقله إلى القائمة Confirmed، ثم عُدْ إلى الخطوة 2.

سيصبح فهم ذلك أسهل كثيرًا عندما ننظر إلى مثال، حيث افترض الشبكة الموضحة في الشكل السابق. لاحظ أن هذه الشبكة بها مجموعة من تكاليف الأضلاع المختلفة. يتتبع الجدول الآتي خطوات بناء جدول توجيه العقدة D. نشير إلى مخارج العقدة D باستخدام أسماء العقد التي تتصل بها، B و C. لاحظ الطريقة التي تتبعها الخوارزمية، حيث تبدأ فيها باستخدام المسارات الخاطئة (مثل مسار التكلفة المكون من 11 وحدة إلى العقدة B والذي كان أول إضافة إلى القائمة Tentative ولكنها تنتهي بالمسارات الأقل تكلفة لجميع العقد.

تتميز خوارزمية توجيه حالة الرابط بالعديد من الخصائص الرائعةهي: لقد ثبت أنها تستقر بسرعة، ولا تولّد الكثير من حركة مرور البيانات، وتستجيب بسرعة لتغييرات مخطط الشبكة أو فشل العقدة، ولكن يمكن أن يكون مقدار المعلومات المخزَّنة في كل عقدة (رزمة LSP واحدة لكل عقدة أخرى في الشبكة) كبيرًا جدًا. هذه واحدة من المشكلات الأساسية للتوجيه وهي مثال عن المشكلة العامة ألا وهي قابلية التوسع.

اقتباس

إنّ خوارزميتي متجّه المسافة وحالة الرابط خوارزمياتُ توجيه موزعة، لكن تعتمدان استراتيجيات مختلفة. حيث تتحدث كل عقدة فقط مع جيرانها المتصلين بها مباشرة، لكنها تخبرهم بكل ما تعلمته (أي المسافة إلى جميع العقد) في خوارزمية متجه المسافة. بينما تتحدث كل عقدة مع جميع العقد الأخرى، لكنها تخبرهم فقط بما تعرفه على وجه اليقين (أي حالة روابطها المتصلة مباشرة فقط) في خوارزمية حالة الرابط. سننظر في نهجٍ أكثر مركزية للتوجيه لاحقًا عندما نقدم الشبكات المعرَّفة بالبرمجيات Software Defined Networking أو اختصارًا SDN.

بروتوكول المسار المفتوح الأقصر أولا Open Shortest Path First Protocol

يُعد بروتوكول OSPF أحد أكثر بروتوكولات توجيه حالة الرابط استخدامًا. تشير الكلمة الأولى، مفتوح Open، إلى حقيقة أنه معيار مفتوح وغير مملوك، أُنشئ تحت رعاية فريق Internet Engineering Task Force أو اختصارًا IETF. يأتي جزء "SPF" من اسمٍ بديل لتوجيه حالة الرابط. يضيف بروتوكول OSPF العديد من الميزات إلى خوارزمية حالة الرابط الأساسية بما في ذلك ما يلي:

• استيثاق رسائل التوجيه Authentication of routing messages: تتمثل إحدى ميّزات خوارزميات التوجيه الموّزعة في أنها تنشر المعلومات من عقدة واحدة إلى العديد من العقد الأخرى، وبالتالي يمكن أن تتأثر الشبكة بأكملها بمعلومات سيئة من عقدة واحدة. لذلك من الجيد التأكد من إمكانية الوثوق بجميع العقد المشاركة في البروتوكول، حيث يساعد استيثاق رسائل التوجيه في تحقيق ذلك. استخدمت الإصدارات القديمة من بروتوكول OSPF كلمة مرور بسيطة مؤلفة من 8 بايتات للاستيثاق. وهذا ليس شكلًا قويًا من أشكال الاستيثاق لمنع المستخدمين الضارين، ولكنه يخفّف من بعض المشكلات التي تسببها أخطاء الضبط misconfiguration أو الهجمات العرَضية (أُضيف شكلٌ مماثل من الاستيثاق إلى بروتوكول RIP في الإصدار 2)، وأُضيف استيثاق تشفير قوي لاحقًا.
• الهرمية الإضافية Additional hierarchy: تُعد الهرمية أحد الأدوات الأساسية المستخدمة لجعل الأنظمة أكثر قابلية للتوسُّع. يقدّم بروتوكول OSPF طبقةً أخرى من الهرمية في التوجيه من خلال السماح بتقسيم نطاقٍ domain إلى مناطق areas. هذا يعني أن الموجّه داخل النطاق لا يحتاج بالضرورة إلى معرفة كيفية الوصول إلى كل شبكة داخل هذا النطاق، فقد يكون قادرًا على الوصول من خلال معرفة كيفية الوصول إلى المنطقة الصحيحة فقط. وبالتالي هناك انخفاض في كمية المعلومات التي يجب نقلها وتخزينها في كل عقدة.
• موازنة الحمل Load balancing: يسمح بروتوكول OSPF بإسناد مساراتٍ متعددة إلى نفس المكان بنفس التكلفة، وسيؤدي إلى توزيع حركة مرور البيانات بالتساوي على تلك المسارات، وبالتالي الاستفادة بصورة أفضل من سعة الشبكة المتاحة.

هناك عدة أنواع مختلفة من رسائل OSPF، ولكن جميعها تبدأ بالترويسة نفسها، كما هو موضح في الشكل السابق. يُضبَط الحقل Version حاليًا على القيمة 2، وقد يأخذ حقل النوع Type القيم من 1 إلى 5. يحدّد الحقل SourceAddr مُرسل الرسالة، والحقل AreaId هو معرّف مؤلفٌ من 32 بتًا للمنطقة التي تُوجد بها العقدة. الرزمة بأكملها، باستثناء بيانات الاستيثاق، محميةٌ بواسطة مجموع اختباري مؤلف من 16 بتًا باستخدام نفس الخوارزمية التي تستخدمها ترويسة IP. حقل نوع الاستيثاق Authentication type هو 0 في حال لم يُستخدَم أي استيثاق، وخلاف ذلك، قد يكون 1 مما يعني ضِمنًا استخدام كلمة مرور بسيطة، أو 2 مما يشير إلى استخدام المجموع الاختباري للاستيثاق المشفّر. ويحمل حقل الاستيثاق Authentication كلمة المرور أو المجموع الاختباري المشفَّر في الحالات الأخيرة.

من بين أنواع رسائل OSPF الخمسة، النوع 1 هو الرسالة الترحيبية "hello"، التي يرسلها الموجّه إلى نظرائه لإعلامهم بأنه ما زال يعمل ومتّصِل. تُستخدم الأنواع المتبقية لطلب رسائل حالة الرابط وإرسالها والإشعار باستلامها. اللبنة الأساسية لرسائل حالة الرابط في بروتوكول OSPF هي إعلان حالة الرابط link-state advertisement أو اختصارًا LSA، فقد تحتوي رسالةٌ واحدة على العديد من إعلانات LSA.

يجب أن يوفّر بروتوكول OSPF معلومات حول كيفية الوصول إلى الشبكات مثل بقية بروتوكولات التوجيه عبر شبكة متشابكة. وبالتالي يجب أن يوفر بروتوكول OSPF معلومات أكثر قليلًا من البروتوكول البسيط القائم على الرسم البياني. فقد يُنشئ الموجّه الذي يشغّل بروتوكول OSPF رزمَ حالة الرابط التي تعلن عن واحدة أو أكثر من الشبكات المتصلة مباشرة بهذا الموجه. يجب أيضًا أن يعلن الموجه المتصل بموجّهٍ آخر عن طريق رابطٍ عن تكلفة الوصول إلى هذا الموجه عبر هذا الرابط. هذان النوعان من الإعلانات ضروريان لتمكين جميع الموجّهات الموجودة في نطاقٍ ما من تحديد تكلفة الوصول إلى جميع الشبكات في هذا النطاق وتحديد موجّه القفزة التالية المناسبة لكل شبكة.

يوضّح الشكل السابق صيغة رزمة إعلان حالة الرابط من النوع 1. تعلن إعلانات LSA من النوع 1 عن تكلفة الروابط بين الموجّهات. تُستخدَم إعلانات LSA من النوع 2 للإعلان عن الشبكات التي يتصل بها الموجّه المُعلِن، بينما تُستخدم الأنواع الأخرى لدعم الهرمية الإضافية وسيُشرح لاحقًا في الفصول القادمة. يجب أن تكون العديد من الحقول في إعلان LSA مألوفة من المناقشة السابقة. الحقل LS Age هو الحقل الذي يعادل حقل TTL، باستثناء أنه يكون متزايدًا وتنتهي صلاحية إعلان LSA عندما يصل العمر age إلى قيمة قصوى محددة. يخبرنا الحقل Type أن هذا هو النوع 1 من إعلانات LSA.

يكون الحقل Link state ID والحقل Advertising router متطابقين في النوع 1 من إعلانات LSA. يحمل كل منهما معرّفًا مؤلفًا من 32 بت للموجّه الذي أنشأ إعلان LSA. يمكن استخدام عدد من استراتيجيات الإسناد لإسناد هذا المعرّف، فمن الضروري أن يكون فريدًا في نطاق التوجيه، وأن يستخدم موجّهٌ معينٌ نفس معرّف الموجّه باستمرار. تتمثل إحدى طرق اختيار معرّف الموجه الذي يُلبي هذه المتطلبات في اختيار أقل عنوان IP من بين جميع عناوين IP المُسنَدة لهذا الموجّه. (تذّكر أن الموجّه قد يكون له عنوان IP مختلف على كلّ واجهةٍ من واجهاته).

يُستخدَم حقل LS sequence number لاكتشاف إعلانات LSA القديمة أو المكررة. الحقل LS checksum مشابه للحقول الأخرى التي رأيناها في البروتوكولات الأخرى، حيث يُستخدَم بالطبع للتحقق من عدم تلف البيانات. وهو يغطّي جميع الحقول في الرزمة باستثناء الحقل LS Age، لذلك ليس من الضروري إعادة حساب المجموع الاختباري في كل مرة يزداد فيها الحقل LS Age. الحقل Length هو طول إعلان LSA الكامل مقدرًا بالبايت.

نصل الآن إلى معلومات حالة الرابط الفعلية. وقد أصبح هذا الأمر معقدًا بعض الشيء بسبب وجود معلومات نوع الخدمة type of service أو اختصارًا TOS. يُمثَّل كل رابط في LSA بواسطة الحقول Link ID، و Link Data، و metric، حيث يحدّد أول حقلين من هذه الحقول الرابط، وتتمثل الطريقة الشائعة للقيام بذلك في استخدام معرّف الموجّه الخاص بالموجه في الطرف البعيد من الرابط بعدّه كحقل Link ID ثم استخدام حقل Link Data لإزالة الغموض بين الروابط المتوازية المتعددة إن لزم الأمر. والحقل metric هو بالطبع تكلفة الرابط. ويخبرنا الحقل Type بشيء عن الرابط، على سبيل المثال إذا كان رابطًا من نقطة لنقطة.

تسمح معلومات TOS لِبروتوكول OSPF باختيار مساراتٍ مختلفة لِرزم IP بناءً على القيمة الموجودة في حقل TOS الخاص بهذه الرزم. يمكن إسناد مقاييس مختلفة بناءً على قيمة TOS للبيانات بدلًا من إسناد مقياسٍ واحد لرابط. إذا كان لدينا رابط في شبكتنا وهو جيدٌ جدًا لحركة مرور البيانات الحساسة للتأخير على سبيل المثال، فيمكن إعطاء هذا الرابط مقياسًا منخفضًا لقيمة TOS التي تمثل تأخيرًا منخفضًا ومقياسًا عاليًا لكل شيء آخر. سيختار بروتوكول OSPF بعد ذلك أقصر مسار مختلفٍ لتلك الرزم التي ضُبِط حقل TOS الخاص بها على تلك القيمة. من الجدير بالذكر أنه في وقت كتابة النسخة الإنجليزية من هذا الكتاب لم تُنشَر هذه القدرة على نطاقٍ واسع بعد.

المقاييس Metrics

تفترض المناقشة السابقة أن تكاليف الرابط، أو المقاييس، معروفةٌ عند تنفيذ خوارزمية التوجيه. سنناقش في هذا القسم بعض طرق حساب تكاليف الرابط التي أثبتت فعاليتها عمليًا. أحد الأمثلة التي رأيناها بالفعل، والذي هو بسيطٌ للغاية، هو إسناد التكلفة 1 لجميع الروابط، وبالتالي سيكون المسار الأقل تكلفة هو المسار الذي يحتوي على أقل عدد من القفزات. لكن هذا النهج له عيوبٌ عديدة. أولًا، لا يُميّز بين الروابط على أساس وقت الاستجابة، وبالتالي فإن رابطًا فضائيًا ذو وقت استجابة قدره 250 ميلي ثانية يجده بروتوكولُ التوجيه جذابًا كرابطٍ أرضي بوقت استجابة قدره 1 ميلي ثانية. ثانيًا، لا يفرّق بين المسارات على أساس السعة، مما يجعل رابطًا بسرعة 1 ميجا بت في الثانية يبدو جيدًا كرابطٍ بسرعة 10 جيجابت في الثانية. أخيرًا، لا يميز بين الروابط بناءً على حِملها الحالي، مما يجعل من المستحيل التوجيه باستخدام الروابط المحمَّلة تحميلًا زائدًا. اتضح أن هذه المشكلة الأخيرة هي الأصعب لأنك تحاول التقاط خصائص الرابط المعقدة والديناميكية بتكلفة قياسية واحدة.

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

قام مقياس توجيه ARPANET الأصلي بقياس عدد الرزم التي وُضِعت في الرتل منتظرةً إرسالها على كل رابط، مما يعني أنه أُسند وزن تكلفةٍ أكبر للرابط الذي يحتوي على 10 رزم في الرتل التي تنتظر إرسالها، مقارنةً برابطٍ يحتوي على 5 رزم في رتل الإرسال. ولكن استخدام طول الرتل كمقياسٍ للتوجيه لم يعمل جيدًا، نظرًا لأن طول الرتل هو مقياسٌ مصطنعٌ للحِمل، فهو يحرك الرزم نحو أقصر رتل بدلًا من توجيهها نحو الوجهة، وذلك موقفٌ مألوفٌ جدًا لنا عندما نقفز من رتلٍ لآخر في محل البقالة. عانت آلية توجيه ARPANET الأصلية من حقيقة أنها لم تهتم بحيز نطاق الرابط التراسلي bandwidth أو وقت استجابته latency.

اهتم الإصدار الثاني من خوارزمية توجيه ARPANET بكلٍ من حيز نطاق الرابط التراسلي ووقت الاستجابة واستخدم التأخير delay، بدلًا من طول الرتل، كمقياسٍ للحِمل. وتم ذلك على النحو التالي. أولًا، وُضعت علامةٌ زمنية لكل رزمة واردة بوقت وصولها إلى الموجّه ArrivalTime، وسُجِّل وقت مغادرته من الموجّه DepartTime أيضًا. ثانيًا، حَسبَت العقدةُ تأخيرَ Delay تلك الرزمة عند استلام الجانب الآخر إشعارًا ACK على مستوى الرابط كما يلي:

Delay = (DepartTime - ArrivalTime) + TransmissionTime + Latency

حيث عُرِّف وقت الإرسال TransmissionTime ووقت الاستجابةLatency تعريفًا ثابتًا للرابط وهما يلتقطان حيّز نطاق الرابط التراسلي ووقت استجابته على التوالي. لاحظ أنه في هذه الحالة، يمثّل ناتج DepartTime - ArrivalTime مقدار الوقت الذي تأخرت فيه الرزمة (وُضِعت في الرتل) في العقدة بسبب الحِمل. إذا لم يصل إشعار ACK، ولكن انتهت مهلة الرزمة بدلًا من ذلك، فسيُعاد ضبط وقت المغادرة DepartTime إلى وقت إعادة إرسال الحزمة. يلتقط DepartTime - ArrivalTime في هذه الحالة موثوقية الرابط، فكلما زاد تكرار إعادة إرسال الرزم، قلّت وثوقية الرابط، وكلما زادت رغبتنا في تجنُّبه. أخيرًا، اُشتقّ الوزن المُسنَد لكل رابط من متوسط التأخير الذي اختبرته الرزم المرسَلة مؤخرًا عبر هذا الرابط.

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

كانت هناك مشكلة أخرى وهي أن نطاق قيم الرابط كان كبيرًا جدًا، فقد يبدو الرابط المحمَّل كثيرًا بسرعة 9.6 كيلوبت في الثانية أكثر تكلفة بـ 127 مرة من الرابط المحمَّل بصورة خفيفة بسرعة 56 كيلوبت في الثانية. (ضع في بالك أننا نتحدث عن شبكة ARPANET حوالي عام 1975). وهذا يعني أن خوارزمية التوجيه ستختار مسارًا به 126 قفزة من الروابط التي تحمَّل بصورة خفيفة بسرعة 56 كيلوبت في الثانية بدلًا من مسار مؤلفٍ من 1 قفزة بسرعة 9.6 كيلو بت في الثانية. يُعَد التخلص من بعض حركة مرور البيانات من خط محمّل بصورة زائدة فكرةً جيدة، إلّا أنّ جعلهُ غير جذاب لدرجة أن يفقد كل حركة مروره أمرٌ متهوّر. ويُعَد استخدام 126 قفزة بدلًا من قفزة واحدة استخدامًا سيئًا لموارد الشبكة. عوقبت الروابط الفضائية بلا داعٍ أيضًا، بحيث بدا الرابط الفضائي الخامل بسرعة 56 كيلوبت في الثانية أكثر تكلفة بكثير من الرابط الأرضي الخامل بسرعة 9.6 كيلوبت في الثانية، على الرغم من أن الأول سيعطي أداءً أفضل للتطبيقات ذات حيز النطاق التراسلي العالي.

تناول نهج ثالث هذه المشاكل. فتمثلت التغييرات الرئيسية في ضغط نطاق المقياس الديناميكي بصورة كبيرة لصالح نوع الرابط، وتقليل تباين المقياس مع مرور الوقت. يتحقق تقليل التباين هذا من خلال عدة آليات. أولًا، تحويل قياس التأخير إلى استخدامية رابط، وحساب متوسط هذا الرقم مع آخر استخداميةٍ مبلَّغٍ عنها لمنع التغييرات المفاجئة. ثانيًا، كان هناك حد صارم لِمدى تغير المقياس من دورة قياس إلى أخرى. تقل احتمالية أن تتخلى جميع العقد عن المسار مرة واحدة بصورة كبيرة من خلال تقليل التغييرات في التكلفة .

تحقّقَ ضغط النطاق الديناميكي عن طريق تزوّيد الاستخدامية utilization المُقاسة، ونوع الرابط، وسرعة الرابط في عمليةٍ تظهر بيانيًا في الشكل التالي. لاحظ ما يلي:

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

تعني كل هذه العوامل أنه من غير المرجح أن يحدث تخلي عن الرابط بشكلٍ شامل، نظرًا لأنه يمكن أن تجعل الزيادة في التكلفة بمقدار ثلاثة أضعاف الرابطَ غير جذاب لبعض المسارات ولكنها تتركه بمثابة الخيار الأفضل للآخرين. وصلنا إلى المنحدرات slopes والإزاحات offsets ونقاط التوقف breakpoints الخاصة بالمنحنيات في الشكل السابق من خلال قدرٍ كبير من التجربة والخطأ، والضبط بعنايةٍ لتوفير أداءٍ جيد.

اتضح أنه نادرًا ما تتغير المقاييس في غالبية عمليات نشر الشبكة في العالم الحقيقي، وإن وجدت تحدث فقط تحت سيطرة مسؤول الشبكة، وليس تلقائيًا. والسبب في ذلك جزئيًا هو أن الحكمة التقليدية السائدة ترى الآن أن المقاييس المتغيرة ديناميكيًا غير مستقرة للغاية، على الرغم من أن هذا ربما لا يكون صحيحًا. والأهم من ذلك، أن العديد من الشبكات اليوم تفتقر إلى التباين الكبير في سرعات الروابط وأوقات الاستجابة التي سادت في شبكات ARPANET. وبالتالي فإن المقاييس الثابتة هي القاعدة. أحد الأساليب الشائعة لتحديد المقاييس هو استخدام ثابتٍ مضروب في 1/link_bandwidth.

اقتباس

لماذا ما زلنا نروي قصةً عن خوارزمية عمرها عقود ولم تعد قيد الاستخدام؟ لأنها توضح درسين قيّمين بصورة مثالية. الأول هو أن أنظمة الحواسيب غالبًا تُصمَّم بصورة متكررة بناءً على الخبرة، وتُحقَّق نادرًا بالصورة الصحيحة في المرة الأولى، لذلك من المهم نشر حل بسيط عاجلًا وليس آجلًا، ونتوقع تحسينه بمرور الوقت. إنّ البقاء عالقًا في مرحلة التصميم إلى أجلٍ غير مسمى خطةً غير جيدة. والثاني هو مبدأ KISS المعروف جيدًا: ، فإن القليل من التعقيد غالبًا ما يكون كثيرًا عند بناء نظام معقد. إن فرصَ ابتكار تحسينات معقدة وفيرةٌ، وهي فرصة مغرية للمتابعة. ولكن مثل هذه التحسينات لها قيمة قصيرة المدى في بعض الأحيان، ومن المثير للصدمة عدد المرات التي يثبت فيها النهج البسيط أنه الأفضل بمرور الوقت. لأن الحفاظ على كل جزءٍ بسيطًا قدر الإمكان هو أفضل طريقة عندما يحتوي النظام على العديد من الأجزاء المتحركة، كما هو الحال مع الإنترنت بالتأكيد.

ترجمة -وبتصرّف- للقسم Routing من فصل Internetworking من كتابComputer Networks: A Systems Approach.

اقرأ أيضًا

• المقال التالي: تطبيق مبدلات وموجهات الشبكات الحاسوبية برمجيا وعتاديا
• المقال السابق: الشبكات الفرعية والعناوين والأخطاء في بروتوكول IP
• التوجيه Routing بين الأجهزة المتنقلة في الشبكات الحاسوبية