摘 要：約束路由問(wèn)題是IP網(wǎng)絡(luò)的一個(gè)核心功能，由于求解多約束路由問(wèn)題屬于NP完全問(wèn)題。所以大量的研究工作圍繞此展開(kāi)?；诜植际郊s束滿(mǎn)足的思想，設(shè)計(jì)多約束單路徑路由問(wèn)題求解算法，分析表明該求解算法降低計(jì)算復(fù)雜度，提高算法的性能。在分布式條件下完成算法的實(shí)現(xiàn)，經(jīng)實(shí)驗(yàn)表明，算法近似程度較好，求解速度快。

關(guān)鍵詞：IP；多約束；單路徑；路由算法

中圖分類(lèi)號(hào)：TP301．6 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言

約束路由問(wèn)題是IP網(wǎng)絡(luò)的一個(gè)核心功能，其主要目標(biāo)包括兩個(gè)：①為尋址的業(yè)務(wù)流提供服務(wù)質(zhì)量保證；②達(dá)到網(wǎng)絡(luò)全局資源的最佳利用。前者要求在多約束條件下計(jì)算出可行路徑；后者則要求在多條可行路徑中進(jìn)行優(yōu)化。優(yōu)化的方式通常是首先設(shè)計(jì)花費(fèi)(cost)函數(shù)，然后求解函數(shù)值最優(yōu)的可行路徑。

然而，通常多約束條件下求解可行路徑屬于NP完全問(wèn)題，不能在多項(xiàng)式時(shí)間內(nèi)精確求解。為此，人們?cè)O(shè)計(jì)了很多啟發(fā)式算法或近似算法。由于是近似算法，因此還存在以下三個(gè)方面的不足：①計(jì)算復(fù)雜度過(guò)高，導(dǎo)致不能在網(wǎng)絡(luò)中實(shí)際應(yīng)用；②算法性能過(guò)低，導(dǎo)致找不到實(shí)際存在的可行路徑；③大部分算法只是針對(duì)某些特定的約束路由問(wèn)題。

“注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”