MPLS網絡中基于QoS約束的路由和準入控制*

崔瀟宇，沈慶國

（陸軍工程大學，江蘇 南京，210000）

0 引 言

多協議標記交換（MLPS）網絡是專為IP流提供端到端的服務質量而設計的。QoS很重要，如對于交互式音頻應用程序，動態流的準入控制是網絡中基于QoS需求和可用資源接受或拒絕一個新流程的核心機制。如果沒有這種機制，網絡會不斷允許新的數據流通過，以致過載一條或多條鏈路，導致一些流程的服務質量下降。此環境中，業務路由選擇也是一種尋找到達目的路由器的路徑的重要機制，同時遵循QoS約束。準入控制可以利用路由的結果，但是它也可能從路由中獨立出來。比如，即使存在一條平滑的路徑，準入控制可能根據流量監控拒絕一個流。不過，大多數準入控制機制是基于路由的。

通常，QoS約束包括兩方面：線性約束和路徑約束。線性約束適用于本地鏈接，而路徑約束是端到端的。路徑約束主要有端到端的延遲、丟包率、抖動和帶寬，這些約束也可以被用于本地鏈接。

準入控制可以是集中式[1-2]或分布式[3-4]的，前者是服務器通過在網絡中聚集信息作出決策，后者是邊緣路由器在網絡上保留完整或部分信息，在入口結點處作出決策。這意味著核心服務器在建立時可能產生高時延，而區分的方法會受到非最優決策的影響。另外，準入控制可以是基于預留[1]或是測量的[5]。

目前，許多學者從事這個領域的研究，大部分已提出的機制想要滿足新需求的端到端延遲或丟包率約束，但明顯沒有考慮已經允許的流。當前，尚沒有提出不經過重路由能解決所有流的端到端延遲或是丟包率約束的解決方法。本文中，“重路由”表示為一個流尋找一條新的路徑，并通過它將所有數據包聚集成這個流。由于重路由可能影響服務質量，因此需要盡量避免。

本文提出了兩種MPLS網絡中業務流在聯合路由和準入控制（JRAC）問題方面的模型。聯合路由和準入控制意味著這個決策不能和路由過程同時允許一個新流，也就是說，這個新流要尋找一條到達目的端的標簽交換路徑（LSPs）。第一個模型滿足端到端的時延約束，第二個模型滿足丟包約束。這些約束不僅針對新的業務流，也對所有已經允許通過的流。目標函數是求一個新業務流端到端時延的最小值。

1 準備工作

1.1 符號表示

1.1.1 集合

N表示路由結點的集合；M 表示單向鏈接的集合；L表示單向LSPs的集合；hP表示由至多h條LSPs組成的連接所有源結點和目的結點的路徑集合；T表示已經允許通過的流的集合。其中，一個流Tt∈在結點NtO∈)(開始、NtD∈)(結束，它的通信量需求為tα（單位：b/s），最大時延限制為tβ（單位：s），最大端到端的丟包率限制為tφ。

1.1.2 常量

令為0-1常量，滿足當且僅當流t∈T通過鏈路為0-1常量，滿足當且僅當LbaLSP∈),(通過鏈路Mji∈),(。

1.1.3 時延和丟包率函數

令dij( fij)為鏈路(i, j)上的時延，pij( fij)為鏈路(i, j)上的丟包率，rij( fij)為鏈路(i, j)上數據包的傳送速率，即本文使用M/M/1/k排隊模型，因此：

其中，是鏈路(i, j)上的平均到達速率（單位：包/秒）；ρ是鏈路(i, j)的平均利用率；k是緩沖區的大?。▎挝唬喊?；l是平均包長（單位：bit）；cij是鏈路(i, j)的容量（單位：b/s）；fij是鏈路(i, j)的最終通信量（單位：b/s）；aij是鏈路(i, j)上的傳輸時延與在結點i∈N的過程時延（單位：s）。

本文選擇這個模型，主要是因為它便于分析，且任何時延和丟包率模型都可以和已提出的JRAC模型結合使用。實際上，時延和丟包率參數僅僅是JRAC模型的輸入參數。實際網絡中，一條鏈路上的時延和丟包率可以通過路由測定，且只需使用增量參數即可，如隨機模型。

1.1.4 變量

令xab是0-1變量，滿足xab=1當且僅當新流通過LSP(a,b)；yij是0-1變量，當且僅當新流通過鏈路 (i, j)。

1.2 問題公式化及預處理

本文提出的聯合路由和準入控制問題在于考慮網絡中已經允許通過的流，為從源結點o到目的結點d的新流尋找一條路徑，且滿足流量需求α、端到端的時延限制β和丟包率限制?。如果這種路徑不存在，那么新的流將被阻塞。

我們認為一種合理的拓撲結構已經建立。這種拓撲由邊緣結點之間的LSPs組成。本文中，每一對邊緣結點間都有一條LSP。拓撲中，一條LSP被視作一跳。LSPs的路徑選擇使用Dijkstra最短路徑算法，帶寬根據接受的新流調整，可以根據一些協議如RSVP[6]來調整LSPs的帶寬。既然一個流可以使用多種LSPs，那么在一條LSP終止時檢查IP頭部，計算當前的結點是否是目的結點或者數據包是否需要繼續通過另一條LSP。

為了將數學模型公式化，預處理十分必要。注意，如果一個新流不通過鏈路(i, j)，那么這條鏈路上的通信量為：

鏈路(i, j)上的時延丟包率為數據包的交換率為Rij=1-Pij。否則，鏈路上的通信量為：

鏈路(i,j)上的時延為丟包率為數據包的傳輸速率為

類似地，如果新流不通過LSP(a,b)，端到端時延、傳輸速率和丟包率分別為：

否則，如果新流通過LSP(a,b)，那么：

2 模型建立

2.1 時延約束的準入控制

MPLS網絡中不發生重路由，滿足端到端的時延約束的聯合路由和準入控制的數學模型，可表示為JRAC-D（Joint Routing and Admission Control with Delay Constraints），給出JRAC-D：

JRAC-D的目標函數（13）是求新流的端到端時延的最小值，約束條件（14）表示變量yij等于新流通過鏈路(i, j)時利用的LSPs的數量，且這個數量小于等于1，也就是說新流只能至多通過鏈路一次。注意，yij可以從模型中消去（即約束條件（14）和約束條件（15）可以合并，那么式（17）中的yij由約束條件（14）表示。通過變量約束條件（16）限制路徑中新流使用的LSPs數量至多為h，模型更加易于理解。這些限制條件使準入控制過程更加容易實現，只需要使用基于路徑的方法。相比于在準入控制過程中觀測每一個流，只需要觀測由1,2,…h條LSPs組成的可能路徑。約束條件（17）表示網絡中每一條已經被允許通過的流遵循端到端的時延限制，約束條件（18）表示新流也遵循端到端的時延限制。約束條件（17）和約束條件（18）很重要，因為它們使得所有流都遵循QoS需求。條件（19）表示流的守恒約束，約束條件（20）是完整性約束。

JRAC-D是NP難題[7]（Non-deterministic Polynomialtime Hard），由最短權重的路徑約束問題轉化而來。因為整數變量的數量很少，JRAC-D模型可以在極短的時間使問題的實際大小變得最優。

2.2 丟包約束的準入控制

MPLS網絡中不發生重路由，滿足端到端的丟包約束的聯合路由和準入控制的數學模型，可表示為JRAC-P（Joint Routing and Admission Control with Packet Loss Constraints），如下給出。

滿足式（14）～式（16）、式（19）式（20）和：

JRAC-P的目標函數（21）是求新流的端到端時延的最小值，使用這個目標函數是因為時延是衡量大多數應用的一個重要的QoS參數。約束條件（22）和約束條件（23）使得所有流都遵循丟包需求，這些線性約束是通過對數轉換算法得到的。為了使這些約束條件成立，預處理中應該證明對任意t∈T，有1＜φ和1＜tφ；對任意Mji∈),（，有對任意(a,b)∈L，有

相對于JRAC-D模型，JRAC-P也是NP問題，同時能夠進一步證明它得到實際情況下問題的最優解所需要的計算時間更少。

3 結 語

本文提出在MPLS網絡中關于業務流的聯合路由和準入控制問題的兩種數學模型。第一種模型滿足端到端的時延約束，第二種模型滿足端到端的丟包約束。這些端到端的QoS約束不僅針對網絡中的新流，也針對所有已經允許通過的流。目標函數是求一個新流使用路徑的端到端時延的最小值。通過準入控制策略，這些模型能夠預處理后準確地解答。對于這個問題，還有一些其他研究方法?？梢詢炏瓤紤]其他目標函數，如收益函數。一般通過有效探索，快速尋找擬最優解。在多重約束模型中，試驗將會是有意義的。

[1] Antonio C,Luigi F,Fabio M.Dynamic Routing of Bandwidth Guaranteed Connections in MPLS Networks[J].International Journal on Wireless & Optical Communications,2012,1(01):75-86.

[2] Widyono R.The Design and Evaluation of Routing Algorithms for Real-time Channels[D].Berkeley:University of California,1994.

[3] Ali N A,Mouftah H T,Gazor S.Online Distributed Statistical-delay MBAC with QoS Guarantees for VPLS Connections[C].International Conference on Telecommunications IEEE,2005(02):383-390.

[4] Reeves D S,Salama H F.A Distributed Algorithm for Delay-constrained Unicast Routing[J].IEEE/ACM Transactions on Networking,1997,8(02):239-250.

[5] Uzunalioglu H,Houck J D,Wang T Y.Call Admission Control for Voice over IP[J].International Journal of Communication Systems,2010,19(04):363-380.

[6] Zhang L,Berson S,Herzog S,et al.Resource ReSerVation Protocol(RSVP)--Version 1 Functional Specification[J].Ietf Rfc,1997,40(05):116-127.

[7] Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[J].1979,23(02):555-565.