基于分布式約束滿足的多約束單路徑路由問題求解

摘 要：約束路由問題是IP網絡的一個核心功能，由于求解多約束路由問題屬于NP完全問題。所以大量的研究工作圍繞此展開。基于分布式約束滿足的思想，設計多約束單路徑路由問題求解算法，分析表明該求解算法降低計算復雜度，提高算法的性能。在分布式條件下完成算法的實現，經實驗表明，算法近似程度較好，求解速度快。

關鍵詞：IP；多約束；單路徑；路由算法

中圖分類號：TP301．6 文獻標識碼：A

1 引言

約束路由問題是IP網絡的一個核心功能，其主要目標包括兩個：①為尋址的業務流提供服務質量保證；②達到網絡全局資源的最佳利用。前者要求在多約束條件下計算出可行路徑；后者則要求在多條可行路徑中進行優化。優化的方式通常是首先設計花費(cost)函數，然后求解函數值最優的可行路徑。

然而，通常多約束條件下求解可行路徑屬于NP完全問題，不能在多項式時間內精確求解。為此，人們設計了很多啟發式算法或近似算法。由于是近似算法，因此還存在以下三個方面的不足：①計算復雜度過高，導致不能在網絡中實際應用；②算法性能過低，導致找不到實際存在的可行路徑；③大部分算法只是針對某些特定的約束路由問題。

“注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”