خوارزميات التوجيه في شبكات الحاسوب Routing Algorithms

اقرأ في هذا المقال


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

ما هي خوارزميات التوجيه

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

تستخدم خوارزميات التوجيه المختلفة طرقاً مختلفة لتحديد أفضل مسار، فعلى سبيل المثال تحسب خوارزمية متجه المسافات “distance vector” رسماً بيانياً لجميع المسارات المتاحة، ومن خلال جعل كل نقطة تسمى عقدة تحدد “تكلفة” التنقل إلى كل جار مباشر، كما يتم جمع هذه المعلومات لكل عقدة لإنشاء جدول مسافة واستخدامها لتحديد أفضل مسار من عقدة إلى أخرى.

أنواع خوارزميات التوجيه

أولاً: خوارزميات التوجيه التكيفية

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

أنواع خوارزميات التوجيه التكيفية

1- الخوارزمية المركزية

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

2- خوارزمية معزولة

تقوم هذه الخوارزمية بشراء معلومات التوجيه باستخدام المعلومات المحلية بدلاً من جمع المعلومات من العقد الأخرى.

3- الخوارزمية الموزعة

هذه خوارزمية لامركزية تجد المسافة الأقل تكلفة بين المصدر والوجهة بشكل متكرر بطريقة موزعة.

ثانياً: خوارزميات التوجيه غير التكيفية

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

أنواع خوارزميات التوجيه غير التكيفية

1- الفيضان “the flood”

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

2- مسارات عشوائية

هذه خوارزمية احتمالية، حيث يتم إرسال حزمة بيانات بواسطة جهاز التوجيه إلى أي من جيرانه بشكل عشوائي.

أساسيات خوارزمية التوجيه في شبكات الحاسوب

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

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

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

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

مبدأ عمل خوارزمية التوجيه

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

وأولًا يتم تطبيقه في “ARPANET” وسرعان ما تصبح هذه التقنية مرهقة عندما يزداد عدد العقد، حيث يجب أن يتم حمل الكثير من عقدة المعلومات إلى العقدة، وبروتوكول معلومات التوجيه “RIP” هو أفضل مثال على بروتوكول يستعمل متجه المسافات.

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

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

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

عندما يتلقى جهاز التوجيه معلومات تغير جدول التوجيه الخاص به، فإنّه يقوم بإعلام جميع أجهزة التوجيه المتداخلة في تكوينه، ونظراً لأنّ كل عقدة لها هيكل الشبكة وتكاليف كل ارتباط يمكن اعتبار التوجيه مركزياً في كل عقدة، كما يقوم “OSPF” بتنفيذ هذه التقنية وهي الجيل الثاني من بروتوكولات الإنترنت.

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

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

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

  • “OSPF” هي اختصار لـ “Open-Shortest-Path-First”.
  • “BGP” هي اختصار لـ “Border-Gateway-Protocol”.
  • “RIP” هي اختصار لـ “Routing-Information-Protocol”.
  • “ARPANET” هي اختصار لـ “Advanced-Research-Projects-Agency-Network”.

المصدر: COMPUTER NETWORKING / James F. Kurose & Keith W. RossComputer Networks - The Swiss BayCOMPUTER NETWORKS LECTURE NOTES / B.TECH III YEAR – II SEM (R15)An Introduction to Computer Networks / Peter L Dordal


شارك المقالة: