تصنيف خوارزميات التوجيه: المعرفة بالشبكة

TL;DR

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

1. The Mental Model

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

2. The Core Material

تصنيف خوارزميات التوجيه يعتمد على عدة معايير رئيسية:

• معرفة المعلومات الخاصة بحالة الشبكة: هل الخوارزمية لديها صورة كاملة للشبكة أم جزئية؟
• طريقة إدخال الإعدادات للموجهات: هل تتم الإعدادات يدوياً أم ديناميكياً؟
• الاستجابة المتعلقة بتغيرات الحمل: هل تتفاعل مع ازدحام الشبكة أم لا؟

دعنا نركز على المعيار الأول: المعرفة بالشبكة.

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

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

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

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

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

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

graph TD
    A[تصنيف خوارزميات التوجيه] --> B{المعرفة بحالة الشبكة؟}
    B --> C{معرفة شاملة وكلية}
    B --> D{معرفة جزئية وموزعة}

    C --> E[خوارزميات مركزية (شاملة) - Global Algorithms]
    E --> F[تتطلب جمع كل المعلومات قبل الحساب]
    E --> G[جداول الموجهات تحتوي معلومات كاملة]
    E --> H[تسمى Link State (LS) Algorithms]
    E --> I[تستخدم Dijkstra's algorithm]
    E --> J[تطبق على مستوى Single ISP]

    D --> K[خوارزميات لامركزية - Decentralized Algorithms]
    K --> L[الحسابات تفاعلية وموزعة]
    K --> M[كل عقدة تبدأ بمعرفة وصلاتها المباشرة فقط]
    K --> N[ت обмен معلومات مع الجيران تدريجياً]
    K --> O[تسمى Distance Vector (DV) Algorithms]

ملحوظة عن باقي التصنيفات (من أجل الفهم الكامل):

• خوارزميات التوجيه الحساسة للحمل (Load Sensitive Routing Algorithm): هنا، كلفة الوصلة تتغير ديناميكياً لتعكس مستوى الازدحام الحالي (مثل خوارزميات ARPAnet القديمة).
• خوارزميات التوجيه غير الحساسة للحمل (Load Insensitive Routing Algorithms): كلفة الوصلة لا تعكس بوضوح مستوى الازدحام الحالي (مثل RIP, OSPF, BGP في الإنترنت).
• خوارزميات التوجيه الثابتة (Static Routing Algorithm): جداول التوجيه تُبنى وتُعدّل يدوياً، ولا تتغير إلا بعد فترات طويلة.
• خوارزميات التوجيه الديناميكية (Dynamic Routing Algorithm): تحدث تغييرات سريعة في جداول التوجيه عند حدوث تغيرات في الشبكة (طوبولوجيا أو حمل)، وهي أكثر استجابة لكن عرضة لمشاكل مثل حلقات التوجيه.

3. Worked Example

لنفترض أن لديك شبكة صغيرة مكونة من 3 موجهات: R1, R2, R3.

• في حالة خوارزمية توجيه مركزية (Link State):
  قبل أن يبدأ أي موجه في توجيه البيانات، يجب على R1 و R2 و R3 جميعًا أن تعرف كل وصلة في الشبكة (مثلاً، R1 متصل بـ R2 بتكلفة 2، R2 متصل بـ R3 بتكلفة 3، و R1 غير متصل مباشرة بـ R3 لكن يمكن الوصول إليه عبر R2). سيتم تبادل هذه المعلومات الشاملة في رسالة "Link State Broadcast" أولاً. بعد جمع كل هذه المعلومات، يمكن لكل موجه، باستخدام خوارزمية Dijkstra، حساب المسار الأقل كلفة من أي نقطة إلى أي نقطة أخرى في الشبكة.

• في حالة خوارزمية توجيه لامركزية (Distance Vector):
  R1 يعرف فقط أنه متصل بـ R2 بتكلفة 2.
  R2 يعرف أنه متصل بـ R1 بتكلفة 2 وبـ R3 بتكلفة 3.
  R3 يعرف فقط أنه متصل بـ R2 بتكلفة 3.

  لا أحد يعرف الشبكة بالكامل. يبدأ الموجهون بتبادل تقديراتهم للمسافات مع جيرانهم. R1 يخبر R2 أن "الوصول إلى R1 يكلفني 0". R2 يخبر R1 و R3 عن تكلفته للوصول إليهم. بمرور الوقت، ومع تبادل المعلومات التفاعلي، سيبدأ R1 في معرفة أنه يمكن الوصول إلى R3 عبر R2 بتكلفة 2 (إلى R2) + 3 (من R2 إلى R3) = 5. هذه العملية تحدث تدريجياً دون أن يحوز أي موجه على صورة شاملة للشبكة.

4. Key Takeaways

• خوارزميات التوجيه تُصنف بناءً على عدة معايير، أهمها معرفتها بحالة الشبكة.
• الخوارزميات المركزية (Link State) تتطلب معرفة شاملة وكاملة بالشبكة قبل حساب المسارات.
• تعتمد الخوارزميات المركزية غالبًا على خوارزمية Dijkstra لإيجاد المسار الأقل كلفة.
• الخوارزميات اللامركزية (Distance Vector) تبني المعرفة بالشبكة تدريجياً عبر تبادل المعلومات مع الجيران.
• في الخوارزميات اللامركزية، لا يوجد موجه واحد لديه صورة كاملة عن كل وصلات الشبكة.
• تُستخدم خوارزميات حالة الوصلة المركزية غالبًا داخل مزود خدمة واحد.

Common mistakes the student should avoid:
- الخلط بين "معرفة شاملة" (Global/Centralized) و"معرفة جزئية" (Decentralized).
- افتراض أن جميع خوارزميات التوجيه تعرف كل تفاصيل الشبكة من البداية.
- عدم فهم أن "Link State" و"Distance Vector" هما مثالان رئيسيان لتصنيف المعرفة بالشبكة.

5. Now Try It

تخيل شبكة بسيطة مكونة من 4 موجهات (A, B, C, D) مع وصلات عشوائية بينها. ارسم هذه الشبكة وحدد كلفة لكل وصلة. ثم، اشرح في 5-7 جمل كيف يمكن لخوارزمية مركزية (مثل Link State) أن تجد المسار الأقل كلفة من A إلى D، ثم اشرح كيف يمكن لخوارزمية لامركزية (مثل Distance Vector) أن تفعل ذلك. ما هو الفرق الجوهري في طريقة حصولها على المعلومات؟ قارن بين تعقيد جمع المعلومات لكل نوع للحصول على المسار.