ما هي خوارزميات أقصر مسار توجيه في شبكة الحاسوب Shortest Path Routing

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

ما هي خوارزميات أقصر مسار توجيه Shortest Path Routing

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

أساسيات خوارزميات أقصر مسار توجيه

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

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

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

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

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

يعني أقصر مسار المسار الذي يتم فيه تصغير أي شخص أو أكثر من المقاييس، حيث قد يكون المقياس هو المسافة وعرض النطاق الترددي، ومتوسط ​​حركة المرور وتكلفة الاتصال ومتوسط ​​طول قائمة الانتظار والتأخير المقاس أو أي عامل آخر، كما يتم استخدام خوارزمية “Dijkstra” في الغالب لهذا الغرض والهدف الأساسي للخوارزمية هو تسمية كل عقدة بمسافة من العقدة المصدر على طول المسار الأكثر شهرة.

مبدأ عمل خوارزميات أقصر مسار توجيه

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

أنواع خوارزميات أقصر مسار توجيه Shortest Path Routing

أولاً: خوارزمية بيلمان فورد Ford’s Bellman algorithm

• تحل خوارزمية “Bellman-Ford” مشكلة المصدر الواحد في الحالة العامة، حيث يمكن أن يكون للهوامش أوزان سالبة ويتم توجيه الرسم البياني.

• إذا كان الرسم البياني غير المخطط، فسيجب تعديله بتضمين هامشين في كل اتجاه لجعله موجهاً.

• يتمتع “Bellman-Ford” بخاصية تمكنه من اكتشاف دورات الوزن السالب التي يمكن الوصول إليها من المصدر، ممّا يعني عدم وجود أقصر مسار.

• في حالة وجود دورة وزن سالب، يمكن أن يعمل المسار بلا حدود في تلك الدورة ممّا يقلل تكلفة المسار إلى “− ∞”.

• إذا لم تكن هناك دورة وزن سالبة، فسيقوم “Bellman-Ford” بإرجاع وزن أقصر مسار مع المسار نفسه.

• المدخلات هي رسم بياني يمثل الشبكة وعقدة المصدر “s”.

• النواتج هي أقصر مسار من “s” إلى جميع العقد الأخرى.

• تهيئة المسافات من “s” إلى جميع العقد على أنها لانهائية (∞) والمسافة إلى نفسها تساوي “0”، وصفيف “dist []” بالحجم | V | أي عدد العقد مع كل القيم “∞” باستثناء التوزيعات.

ثانياً: خوارزمية ديكسترا Dijkstra’s algorithm

المدخلات هي رسم بياني يمثل الشبكة وعقدة المصدر “s”.

• النواتج هي أقصر شجرة مسار “spt []” مع s كعقدة جذر.

• التهيئة هي مجموعة مسافات [] من الحجم | V | (عدد العقد)، حيث “dist [s] = 0 و dist [u] = ∞” أي لانهائي، حيث تمثل “u” عقدة في الرسم البياني باستثناء “s”.

• مصفوفة “Q” تحتوي على جميع العقد في الرسم البياني، وعندما تكتمل الخوارزمية سيصبح “Q” فارغاً.

• مجموعة فارغة “S”، هي سيتم إضافة العقد التي تمت زيارتها، وعندما تكتمل الخوارزمية ستحتوي “S” على جميع العقد في الرسم البياني.

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

• إنّه يضع قيداً واحداً على الرسم البياني، ولا يمكن أن يكون هناك هامش سالبة للوزن ومع ذلك بالنسبة لهذا القيد الوحيد، فإنّ “Dijkstra” يتحسن بشكل كبير في وقت تشغيل “Bellman-Ford”.

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

ثالثاً: خوارزمية فلويد وارشال Floyd Warshall’s algorithm

• المدخلات هي مصفوفة تجاور التكلفة مجاورة [] []، تمثل المسارات بين العقد في الشبكة.

• النواتج هي مصفوفة تكلفة أقصر مسار والتكلفة [] [] وتوضح أقصر المسارات من حيث التكلفة بين كل زوج من العقد في الرسم البياني.

• تعمل خوارزمية “Floyd-Warshall” على حل مشكلة أقصر المسارات المكونة من أزواج.

• يستخدم نهج البرمجة الديناميكي للقيام بذلك.

• قد يكون وزن الحافة السالب موجوداً في “Floyd-Warshall”.

رابعاً: خوارزمية جونسون Johnson’s Algorithm

• بينما يعمل “Floyd-Warshall” جيداً مع الرسوم البيانية الكثيفة أي بمعنى العديد من الحواف، فإنّ خوارزمية جونسون تعمل بشكل أفضل مع الرسوم البيانية المتفرقة.

• في الرسوم البيانية المتفرقة تتميز خوارزمية جونسون بوقت تشغيل مقارب أقل مقارنةً بـ “Floyd-Warshall”.

• تستفيد خوارزمية جونسون من مفهوم إعادة الوزن، وتستخدم خوارزمية “Dijkstra “على العديد من الرؤوس للحصول على أقصر مسار بمجرد الانتهاء من إعادة وزن الحواف.