خوارزمية توجيه MENTOR

خوارزمية التوجيه MENTOR هي خوارزمية تُستخدم في توجيه الشبكات المتشابكة ، وتحديدًا فيما يتعلق ببنيتها الأولية . طُوّرت هذه الخوارزمية عام 1991 على يد آرون كيرشنباوم، وبارفيز كرماني، وجورج أ. غروف، ونُشرت من قِبل معهد مهندسي الكهرباء والإلكترونيات (IEEE).

أظهرت الملاحظة التجريبية أن فئة تعقيد هذه الخوارزمية هي O(N²)، أو تربيعية . وهذا يمثل "تحسناً كبيراً مقارنةً بالخوارزميات المستخدمة حالياً، [مع الحفاظ على] جودة الحلول التي تنافس الإجراءات الأخرى الأبطأ بكثير".

تفترض الخوارزمية أن ثلاثة أشياء تؤدي إلى طوبولوجيا منخفضة "التكلفة" (أي الحد الأدنى من المسافة المقطوعة والوقت بين الوجهات): أن المسارات ستميل إلى أن تكون مباشرة وليست دائرية؛ وأن الروابط ستكون "عالية الاستخدام" - أي أنها ستستخدم إلى أقصى قدرة تشغيلية تقريبًا؛ وأن "الروابط الطويلة ذات السعة العالية [سيتم استخدامها] كلما أمكن ذلك".

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

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

• آرون كيرشنباوم، بارفيز كرماني، جورج أ. جروفر. "MENTOR: خوارزمية لتحسين طوبولوجيا وتوجيه شبكات المش" ، معاملات IEEE في الاتصالات ، أبريل 1991. تم الاطلاع عليه في 4 نوفمبر 2007.