مقدمة خوارزميات التوجيه

TL;DR

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

1. The Mental Model

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

2. The Core Material

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

جداول التمرير المحلية تعمل معًا عبر الموجهات المختلفة لتوفير عملية التوجيه الشاملة (Routing) بين المصدر والهدف.

يمكن تمثيل خوارزميات التوجيه باستخدام المخطط (Graph)، وهو يتكون من:
* عقد (N Nodes): تمثل الموجهات أو نقاط الشبكة.
* حواف (E Edges): تمثل الوصلات بين العقد، وكل حافة هي زوج من العقد.

تصنيف خوارزميات التوجيه

تُصنف خوارزميات التوجيه بناءً على عدة معايير:

graph TD
    A["خوارزميات التوجيه"] --> B["حسب المعرفة بالشبكة"];
    A --> C["حسب طريقة إدخال الإعدادات"];
    A --> D["حسب الاستجابة لتغيرات الحمل"];

    B --> B1["مركزية (شاملة) Global (Centralized)"];
    B --> B2["غير مركزية Decentralized"];

    B1 --> B1_1["تستخدم معرفة كاملة بالشبكة (الروترات لديها جداول كاملة)"];
    B1 --> B1_2["تسمى خوارزميات حالة الوصلة (Link State (LS) Algorithms)"];
    B1 --> B1_3["تطبيق Dijkstra's algorithm"];
    B1 --> B1_4["تطبق في مزود خدمة شبكة واحد (Single ISP)"];

    B2 --> B2_1["لا يوجد عقدة لديها معلومات كاملة"];
    B2_2["كل عقدة تبدأ بمعرفة وصلاتها المباشرة"];
    B2 --> B2_3["تبادل المعلومات مع العقد المجاورة"];
    B2_4["تسمى خوارزميات شعاع المسافة (Distance Vector DV Algorithms)"];
    B2 --> B2_5["كل عقدة تحتفظ بمتجه تقدير الكلفة"];

    C --> C1["ستاتيكية Static"];
    C --> C2["ديناميكية Dynamic"];

    C1 --> C1_1["جداول توجيه تُبنى وتُعدّل يدوياً"];
    C1 --> C1_2["التعديلات تحدث بعد فترات طويلة"];

    C2 --> C2_1["تغيير سريع في جداول التوجيه"];
    C2 --> C2_2["يحدث عند تغير الطوبولوجيا أو حمل الحركة"];
    C2 --> C2_3["أكثر استجابة، لكن أكثر عرضة لمشاكل الحلقات والتذبذب"];

    D --> D1["حساسة للحمل Load Sensitive"];
    D --> D2["غير حساسة للحمل Load Insensitive"];

    D1 --> D1_1["كلفة الوصلة تتغير ديناميكياً لتعكس الازدحام"];
    D1 --> D1_2["مثل خوارزميات ARPAnet القديمة"];

    D2 --> D2_1["كلفة الوصلة لا تعكس بوضوح الازدحام الحالي"];
    D2 --> D2_2["مثل RIP, OSPF, BGP في الإنترنت حالياً"];

1. حسب معرفة حالة الشبكة:

• خوارزميات التوجيه المركزية (الشاملة) Global (Centralized) Routing Algorithms:

  • تحسب المسار الأقل تكلفة بمعرفة شاملة وكلية عن الشبكة.
  • تأخذ كمدخلات الاتصالية بين جميع العقد وجميع تكاليف الوصلات.
  • الموجهات لديها جداول تحتوي على معلومات كاملة عن طوبولوجيا الشبكة ووصلاتها وعقدها المتصلة وتكاليفها.
  • يجب أن تجمع هذه المعلومات قبل بدء الحسابات.
  • تُعرف باسم خوارزميات حالة الوصلة (Link State (LS) Algorithms) لأنها تكون مدركة تمامًا لتكلفة كل وصلة (عبر نشر رسالة Link State Routing Broadcast).
  • غالبًا ما تستخدم خوارزمية Dijkstra's algorithm.
  • تُطبق على مستوى مزود خدمة إنترنت واحد (Single ISP).

• خوارزميات التوجيه اللامركزية (Decentralized Routing Algorithms):

  • تحسب المسار الأقل تكلفة بطريقة تفاعلية وموزعة بين الموجهات.
  • لا توجد عقدة واحدة لديها معلومات كاملة عن تكاليف جميع وصلات الشبكة.
  • كل عقدة تبدأ بمعرفة تكاليف الوصلات المتصلة بها مباشرة فقط.
  • تقوم بحسابات تدريجية وتبادل معلومات مع العقد المجاورة لتحديد المسار الأقل تكلفة.
  • تُعرف باسم خوارزميات شعاع المسافة (Distance Vector (DV) Algorithms)، حيث تحتفظ كل عقدة بمتجه (شعاع) يمثل تقدير الكلفة (المسافة) لكل العقد الأخرى.

2. حسب الاستجابة لتغيرات الحمل:

• خوارزميات التوجيه الحساسة للحمل (Load Sensitive Routing Algorithms):

  • تتغير تكلفة الوصلة ديناميكيًا لتعكس مستوى الازدحام الحالي على الوصلة.
  • جميع خوارزميات ARPAnet القديمة كانت من هذا النوع.

• خوارزميات التوجيه غير الحساسة للحمل (Load Insensitive Routing Algorithms):

  • تكلفة الوصلة لا تعكس بوضوح مستوى الازدحام الحالي.
  • بروتوكولات التوجيه المستخدمة حاليًا في الإنترنت مثل RIP, OSPF, BGP هي من هذا النوع.

3. حسب طريقة إدخال الإعدادات:

• خوارزميات التوجيه الثابتة (Static Routing Algorithms):

  • تُبنى جداول التوجيه وتُدخل إعداداتها وتعديل تكلفة الوصلة يدويًا (بتدخل بشري).
  • لا تتغير إلا بعد فترات طويلة.

• خوارزميات التوجيه الديناميكية (Dynamic Routing Algorithms):

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

3. Worked Example

لنفترض لدينا شبكة بسيطة ممثلة بالمخطط التالي:
عقدة (أ) --5--> عقدة (ب)
عقدة (أ) --10--> عقدة (ج)
عقدة (ب) --2--> عقدة (د)
عقدة (ج) --3--> عقدة (د)

إذا كانت مهمتنا هي إيجاد المسار الأقل تكلفة من "عقدة أ" إلى "عقدة د" باستخدام خوارزمية مركزية (مثل Dijkstra's)، فالخطوات ستكون كالتالي:

1. جمع المعلومات الشاملة (Link State Broadcast): قبل البدء، تعرف الخوارزمية بشكل كامل على كل العقد والوصلات وتكاليفها: (أ-ب: 5)، (أ-ج: 10)، (ب-د: 2)، (ج-د: 3).
2. تطبيق الخوارزمية (Dijkstra's):
   • نبدأ من "عقدة أ"، تكلفتها لنفسها 0، وللبقية ما لا نهاية.
   • من "أ"، يمكننا الذهاب إلى "ب" بتكلفة 5، وإلى "ج" بتكلفة 10.
   • نختار المسار الأقل، وهو "أ --> ب" (تكلفة 5).
   • من "ب"، يمكننا الذهاب إلى "د" بتكلفة "5 (من أ إلى ب) + 2 (من ب إلى د)" = 7.
   • نرجع للمسارات الأخرى، من "أ" إلى "ج" بتكلفة 10.
   • من "ج"، يمكننا الذهاب إلى "د" بتكلفة "10 (من أ إلى ج) + 3 (من ج إلى د)" = 13.
   • بمقارنة المسارين المؤديين إلى "د": مسار "أ → ب → د" بتكلفة 7، ومسار "أ → ج → د" بتكلفة 13.
3. تحديد المسار الأفضل: المسار الأقل تكلفة من "أ" إلى "د" هو "أ → ب → د" بتكلفة إجمالية 7.

هذا يمثل كيف تعمل خوارزمية التوجيه المركزية، حيث يكون لديها "صورة كاملة" للشبكة لاتخاذ القرار.

4. Key Takeaways

• التوجيه هو وظيفة أساسية في طبقة الشبكة لإيجاد المسار الأقل تكلفة بين المصدر والهدف.
• الموجهات تستخدم جداول التمرير المحلية لاختيار منفذ الخرج المناسب للرزم.
• المخطط (Graph) يمثل الشبكة بعقد (Nodes) وحواف (Edges) لتسهيل عمل خ