Кіріспе

Constrained Shortest Path First (CSPF) - ең қысқа жол алгоритмдерінің кеңейтімі. CSPF көмегімен есептелген жол - бұл шектеулер жиынтығын орындайтын ең қысқа жол. Бұл дегеніміз, ол белгілі бір шектеулерді бұзатын сілтемелерді кескеннен кейін ең қысқа жол алгоритмін орындайды. Шектеу бір сілтемеге қажетті ең төменгі жолақты кеңдік (осыны да жолақты кеңдікке кепілдік берілген шектеу деп атайды), аяғынан аяғына дейін кідіріс, өтетін сілтемелердің ең көп саны, түйіндерді қосу / алып тастау болуы мүмкін. CSPF MPLS Traffic Engineering-де кеңінен қолданылады. CSPF-ті пайдаланатын маршрут шектеулерге негізделген маршрут деп аталады. CSPF пайдалану арқылы есептелген жол OSPF және IS IS-тен есептелген жолмен дәл бірдей болуы мүмкін немесе ол орындалатын шектеулердің жиынтығына байланысты мүлдем басқаша болуы мүмкін.

Жазылу диапазоны шектелуімен мысал

Оң жақтағы желіге назар аударыңыз, онда маршрут A маршруттандырушыдан C маршруттандырушыға x бірлікпен шектелген жолақты қанағаттандыратын маршрут есептелуі керек, ал әр сілтеме үшін сілтеме құны хоп санағына негізделеді (яғни 1). Егер x = 50 бірлік болса, онда CSPF жолды береді A → B → C. Егер x = 55 бірлік болса, онда CSPF жолды береді A → D → E → C. Егер x = 90 бірлік болса, онда CSPF жолды береді A → D → E → F → C. Осы жағдайлардың бәрінде OSPF және IS IS жолды береді A → B → C. Алайда, егер осы топологиядағы байланыс шығындары әртүрлі болса, CSPF сәйкесінше басқа жолды анықтай алады. Мысалы, бұрын болғандай, hop count барлық сілтемелердің шығыны ретінде қолданылады, бірақ A → B және B → C, бұл үшін шығыны 4. Бұл жағдайда: Егер x = 50 бірлік болса, онда CSPF жолды береді A → D → E → C. Егер x = 55 бірлік болса, онда CSPF жолды береді A → D → E → C. Егер x = 90 бірлік болса, онда CSPF жолды береді A → D → E → F → C.