IMS網(wǎng)絡(luò)中最優(yōu)負(fù)載均衡的服務(wù)觸發(fā)算法研究

張 慶，馮 晨，余江濤，羅 威，任 祥

(1.國網(wǎng)上海市電力公司，上海 200122；2.南京南瑞信息通信科技有限公司，江蘇 南京 211000；3.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

IMS[1-2](IP multimedia subsystem，IP多媒體子系統(tǒng))是支持SoIP(service on Internet protocol，因特網(wǎng)協(xié)議上的服務(wù))的常用系統(tǒng)，是多媒體服務(wù)和VoIP(voice over Internet protocol，因特網(wǎng)協(xié)議語音)的融合技術(shù)，被3GPP定義為多媒體通信的核心網(wǎng)域[3-5]。在IMS網(wǎng)絡(luò)中，AS(application server，應(yīng)用服務(wù)器)通過處理服務(wù)觸發(fā)分組和執(zhí)行服務(wù)邏輯在執(zhí)行各種多媒體服務(wù)中起著至關(guān)重要的作用。隨著服務(wù)和用戶數(shù)量的增加，現(xiàn)有AS負(fù)載量越來越大，這是導(dǎo)致系統(tǒng)錯(cuò)誤的主要原因。因此，許多通信服務(wù)公司在現(xiàn)有系統(tǒng)中增加了新的AS，更多、更穩(wěn)定地為更多用戶提供服務(wù)[6]。在這種情況下，AS供應(yīng)商可以與其他供應(yīng)商不同，并且可以向每個(gè)AS注冊不同的服務(wù)。在使用這些異構(gòu)AS時(shí)，AS之間的負(fù)載平衡始終是一個(gè)問題，因?yàn)榧辛髁康教囟ˋS是產(chǎn)生系統(tǒng)錯(cuò)誤的重要原因。要解決此問題，必須通過有效的服務(wù)觸發(fā)算法進(jìn)行負(fù)載均衡。

以往大多數(shù)關(guān)于服務(wù)觸發(fā)算法的研究都是基于單一或同類AS環(huán)境，主要集中在提高系統(tǒng)性能或減少會(huì)話建立延遲上。然而，現(xiàn)有關(guān)于異構(gòu)AS之間的負(fù)載均衡[7]的研究還不夠。文獻(xiàn)[8-13]中提及的負(fù)載均衡方案可以分類如下：循環(huán)；給每個(gè)AS加權(quán)(加權(quán)觸發(fā))；觸發(fā)每個(gè)服務(wù)到專用AS(專用AS觸發(fā))。

在商業(yè)化系統(tǒng)中，權(quán)重值由操作員手動(dòng)設(shè)定。使用手動(dòng)設(shè)置的權(quán)重值，很難執(zhí)行精確的負(fù)載平衡，也很難適應(yīng)系統(tǒng)的變化，如系統(tǒng)錯(cuò)誤，新AS的安裝或新服務(wù)的注冊等。因此，文中提出以自動(dòng)方式計(jì)算每個(gè)AS服務(wù)的最佳權(quán)重值，并執(zhí)行最佳負(fù)載平衡的方案。

1 異構(gòu)多應(yīng)用服務(wù)器系統(tǒng)模型

1.1 主要假設(shè)和系統(tǒng)結(jié)構(gòu)

考慮系統(tǒng)擁有N個(gè)AS和M個(gè)基于iFC(initial filter criterion，初始過濾標(biāo)準(zhǔn))的服務(wù)。注冊到AS的每個(gè)服務(wù)都是基于iFC的，并且S-CSCF(serving call session control function，服務(wù)會(huì)話控制功能)在S-CSCF生成服務(wù)觸發(fā)分組之前從HSS(home subscriber server，歸屬訂戶服務(wù)器)下載iFC信息。假設(shè)S-CSCF知道每個(gè)AS上的每個(gè)注冊服務(wù)以及每個(gè)服務(wù)是否通過iFC信息注冊到AS。

圖1 服務(wù)觸發(fā)的IMS構(gòu)架

圖1為系統(tǒng)的基本考慮模型[14-15]。S-CSCF在用戶認(rèn)證期間從HSS獲得iFC信息，并基于該信息確定AS的候選集合。在AS候選集確定之后，根據(jù)在DNS(domain name server，域名服務(wù)器)中設(shè)置的權(quán)重值確定用于觸發(fā)到每個(gè)AS服務(wù)的傳輸概率，并且S-CSCF應(yīng)該在傳輸之前通過查詢DNS來知道它。S-CSCF基于該傳輸概率經(jīng)由SIP(session initiation protocol，會(huì)話發(fā)起協(xié)議)消息向AS發(fā)送服務(wù)觸發(fā)分組。

在大多數(shù)基于IMS的商業(yè)化設(shè)備中，都會(huì)安裝作為統(tǒng)計(jì)服務(wù)器的EMS(element management server，元素管理服務(wù)器)以便于系統(tǒng)管理。EMS包含監(jiān)視系統(tǒng)的信息，例如每個(gè)服務(wù)的呼叫數(shù)，用戶數(shù)或錯(cuò)誤歷史。通過利用來自EMS的信息，可以獲得服務(wù)觸發(fā)分組的概率分布，即用戶使用每個(gè)服務(wù)的頻率。如果知道服務(wù)觸發(fā)器的正確概率分布，則可以執(zhí)行負(fù)載平衡。文中假設(shè)EMS使用SOAP[8](simple object access protocol，簡單對象訪問協(xié)議)定期更新DNS中服務(wù)數(shù)據(jù)包的概率分布，并且S-CSCF通過查詢DNS來學(xué)習(xí)概率的準(zhǔn)確分布。

1.2 元素矩陣的定義

在大多數(shù)情況下，系統(tǒng)操作員通過存儲在HSS中的iFC知道哪些服務(wù)是在特定AS上注冊的信息。因此，如果服務(wù)j未在ASi中注冊，Wi,j可以在計(jì)算最佳權(quán)重之前將其設(shè)置為0，且除非該服務(wù)新注冊到AS，否則該值無需更改。換句話說，在計(jì)算最佳權(quán)重值之前，S-CSCF可以在WM的整個(gè)元素之間區(qū)分非零元素和零元素。從下面開始，會(huì)用W代表WM。

最后一個(gè)是資源矩陣(RM)，表示負(fù)載與每個(gè)AS的比率。RM在計(jì)算WM時(shí)扮演著資源約束的角色。通過調(diào)整RM中元素的值，運(yùn)算符可以控制每個(gè)AS的負(fù)載比。這個(gè)矩陣是N×1。文中用R表示該矩陣。

利用上面描述的3個(gè)矩陣，可以用如下等式表示此系統(tǒng)。

WP=R

(1)

在該系統(tǒng)中，矩陣P的元素值通過EMS得到，矩陣R由操作員手動(dòng)設(shè)置。因此，如果通過預(yù)先確定矩陣P與矩陣R的值以及S-CSCF由矩陣W中的元素計(jì)算出向特定AS觸發(fā)服務(wù)的條件概率來計(jì)算矩陣W，就可以執(zhí)行最佳的負(fù)載平衡。計(jì)算W中元素值的方法將在下一節(jié)中介紹。

2 多AS系統(tǒng)中的負(fù)載均衡方案

2.1 基本算法

為了執(zhí)行文中算法，首先將矩陣W進(jìn)行分解：

W=XQ

(2)

其中，Q矩陣是M×M對角矩陣，其元素可表示如下：

(3)

如果矩陣Q如上述定義，QP變?yōu)樵厝?的M×1矩陣，那么原先系統(tǒng)轉(zhuǎn)換為以下表達(dá)式：

(4)

通過將矩陣W分解為矩陣X乘以矩陣Q，每個(gè)與矩陣X相乘的元素都變?yōu)?。因此可以執(zhí)行更簡單的計(jì)算。此處將矩陣X定義為輔助矩陣。矩陣X的特點(diǎn)是每行中每個(gè)元素的總和與矩陣R的行相同，并且每列中每個(gè)元素的總和成為服務(wù)的特定觸發(fā)概率(pj)?？梢杂靡韵路匠瘫硎荆?/p>

(5)

(6)

如果獲得的輔助矩陣X有了上述限制，則可以通過來自EMS信息已知的矩陣Q得到矩陣W。通過基于該矩陣W執(zhí)行服務(wù)觸發(fā)，可以以與矩陣R相同的比率完成負(fù)載均衡。為獲得矩陣X，將應(yīng)用以下算法：

(1)如果服務(wù)j未向ASi注冊，設(shè)置Xi,j為0。

(2)在未分配列中選擇具有最多零的一列。如果非零元素?cái)?shù)量相同，則選擇包含更高優(yōu)先級服務(wù)的列。

(3)調(diào)查每一行并驗(yàn)證每行中未分配的非零元素(Ni,j)的數(shù)量。當(dāng)Xi,j=0時(shí)，Ni,j被設(shè)置為無效。如果Ni,j的每個(gè)元素都通過了驗(yàn)證，則繼續(xù)執(zhí)行步驟4。

(7)

(6)如果存在更多要分配的列，繼續(xù)執(zhí)行步驟2，否則結(jié)束算法。

通過上述算法可以獲得矩陣X，并通過已知的矩陣X乘上矩陣P來計(jì)算矩陣W。如果按照矩陣W執(zhí)行服務(wù)觸發(fā)，最佳負(fù)載平衡是可能實(shí)現(xiàn)的。

2.2 存在同類列集時(shí)的簡化算法

在上述算法中，應(yīng)該搜索每個(gè)元素并驗(yàn)證每個(gè)時(shí)間點(diǎn)Ni,j和ri的分配。隨著服務(wù)種類或AS數(shù)量的增加，進(jìn)行矩陣X的運(yùn)算也會(huì)增加。因此，為了支持具有大量AS的服務(wù)，就需要一個(gè)簡化算法來減少計(jì)算量。

通常，服務(wù)的數(shù)量遠(yuǎn)遠(yuǎn)大于AS的數(shù)量，并且由于成本問題，許多公司希望以盡可能少的AS支持盡可能多的服務(wù)。例如，KT(Korea Telecom，韓國電信)用4個(gè)AS來支撐27個(gè)應(yīng)用服務(wù)。因此，多數(shù)會(huì)將一些服務(wù)注冊到具有同類模式的相同AS中。換句話說，矩陣X中擁有相同分配結(jié)構(gòu)的列也是可以存在的。此外，如果2M(每個(gè)服務(wù)注冊到AS的可能模式的數(shù)量)小于服務(wù)的數(shù)量(N)，這些列的集合顯然符合Pigeon-hole原則[8]。

使用相同的列結(jié)構(gòu)，可以很容易地注意到應(yīng)該將相同的元素值分配給具有相同結(jié)構(gòu)的列。因此可以得出結(jié)論，一旦完成一列的分配，可以容易地分配具有相同結(jié)構(gòu)的列的值而無需額外計(jì)算?；谶@個(gè)想法，文中提出了一種改進(jìn)的算法來減少計(jì)算量。

為了指定算法，定義了同類列和同類列集。同類列是具有相同特定列結(jié)構(gòu)的列。例如，在表1中，服務(wù)#3是服務(wù)#1的同類列，這是因?yàn)樗鼈兙哂邢嗤淖越Y(jié)構(gòu)。同類列集是包含特定列的同類列的組。同類列集的元素是彼此的同類列。例如，集合{服務(wù)#1，服務(wù)#3}是服務(wù)#1和服務(wù)#3的同類列集。

在新算法中，已分配列的值被復(fù)制并自動(dòng)分配到其同類列而無需進(jìn)一步計(jì)算。修改后的算法如下：

(1)如果服務(wù)j沒有在ASi中被注冊，則矩陣X中每個(gè)Xi,j的值為零。

(2)選擇未被分配的列中具有最多零的列。如果非零元素?cái)?shù)量相同，則選擇包含更高優(yōu)先級服務(wù)的列。

(3)調(diào)查每一行并驗(yàn)證每行中未分配的非零元素(Ni,j)的數(shù)量，當(dāng)Xi,j=0時(shí)，Ni,j被設(shè)置為無限。如果Ni,j中每個(gè)元素進(jìn)行了驗(yàn)證，則繼續(xù)執(zhí)行步驟4。

(5)如果存在任何滿足的元素Xi,j>rl，則設(shè)定該元素的Ni,j=。然后，使并且分配每個(gè)Xi,j為：

(8)

重復(fù)該步驟直到每一個(gè)Xi,j≤ri都在j列中。

(6)從整個(gè)未分配的列中，搜索在步驟5中分配的列的同類列。如果存在同類列，則復(fù)制這個(gè)被分配的列并將其分配給其同類列集中的每個(gè)元素。如果存在任何滿足Xl,j>rl的元素，執(zhí)行步驟5。在分配之后，同類列集中的每個(gè)元素都被認(rèn)為是已分配的，并且不會(huì)參與進(jìn)一步的計(jì)算。如果存在更多要分配的列，就繼續(xù)執(zhí)行步驟2。否則，結(jié)束算法。

當(dāng)存在同類列集時(shí)，應(yīng)該使用改進(jìn)算法，因?yàn)楫?dāng)不存在同類列時(shí)，搜索同類列的過程浪費(fèi)時(shí)間。通常，系統(tǒng)操作員知道同類列是否存在。因此，系統(tǒng)操作員可根據(jù)預(yù)先知道的服務(wù)注冊模式選擇使用哪種算法。

3 仿 真

3.1 仿真環(huán)境

在具有多個(gè)AS的IMS網(wǎng)絡(luò)中進(jìn)行了實(shí)驗(yàn)。注冊服務(wù)總數(shù)為8，AS數(shù)量設(shè)置為4。每個(gè)AS的服務(wù)安排模式不同，模式如表1所示。如果服務(wù)在AS上注冊，則在表中標(biāo)記O，否則被標(biāo)記為X。為方便起見，假設(shè)S-CSCF的數(shù)量為1。

表1 每個(gè)AS的已注冊服務(wù)模式

3.2 仿真結(jié)果與分析

圖2顯示了當(dāng)每個(gè)服務(wù)具有相同的執(zhí)行概率時(shí)，現(xiàn)有的3種不同方案(循環(huán)，專用AS觸發(fā)和建議方案)中每個(gè)AS的接收觸發(fā)數(shù)。從圖中可以輕松驗(yàn)證兩個(gè)所提方案和專用AS觸發(fā)比循環(huán)具有更好的負(fù)載均衡性能。因?yàn)橛|發(fā)呼叫是以AS中注冊服務(wù)的數(shù)量比率分配的，所以循環(huán)觸發(fā)在負(fù)載均衡中表現(xiàn)不佳。另一方面，如果服務(wù)執(zhí)行的概率對于每個(gè)服務(wù)是相同的，則提出方案或?qū)Ｓ肁S觸發(fā)可以均勻地分配負(fù)載。

圖2 每個(gè)AS在同類服務(wù)概率中接收的觸發(fā)數(shù)

圖3 每個(gè)AS在異構(gòu)服務(wù)概率中接收的觸發(fā)數(shù)

圖3顯示了當(dāng)服務(wù)執(zhí)行概率彼此不同時(shí)的負(fù)載均衡性能。即使在相同的服務(wù)執(zhí)行概率下表現(xiàn)出良好的性能，專用AS觸發(fā)也無法實(shí)現(xiàn)負(fù)載均衡，這是因?yàn)榉?wù)執(zhí)行的概率變得不同。然而，即使服務(wù)概率彼此不同，文中提出的方案也顯示出了良好的負(fù)載均衡性能。

圖4 存在系統(tǒng)錯(cuò)誤時(shí)，每個(gè)AS收到的觸發(fā)數(shù)

圖4顯示了發(fā)生錯(cuò)誤時(shí)每個(gè)AS的負(fù)載平衡性能。當(dāng)觸發(fā)1 000 000個(gè)呼叫時(shí)，AS#4在隨機(jī)時(shí)間內(nèi)發(fā)生錯(cuò)誤。在錯(cuò)誤期間，AS#4無法接收觸發(fā)器，所有呼叫都應(yīng)分配給其他3個(gè)AS。在該圖中，由于系統(tǒng)錯(cuò)誤，每個(gè)方案的AS#4觸發(fā)器數(shù)量已減少。在圖中，可以通過使用提議方案來配置AS#1，AS#2和AS#3，即使AS#4出錯(cuò)，也可以接收相似數(shù)量的觸發(fā)數(shù)據(jù)包。但是，在發(fā)生系統(tǒng)錯(cuò)誤時(shí)，已證明循環(huán)或?qū)Ｓ肁S觸發(fā)無法實(shí)現(xiàn)負(fù)載均衡，而該圖可以很容易地驗(yàn)證，文中方案在錯(cuò)誤環(huán)境中的負(fù)載均衡性能優(yōu)于其他兩種方案。

圖5 每個(gè)AS接收的具有不同服務(wù) 執(zhí)行概率的觸發(fā)器數(shù)

圖5顯示了在操作期間更改服務(wù)執(zhí)行概率時(shí)的負(fù)載均衡性能，比較了具有固定權(quán)重值的服務(wù)觸發(fā)算法和文中提出的方案。可以發(fā)現(xiàn)，具有固定權(quán)重值的方案未能實(shí)現(xiàn)負(fù)載均衡，而文中提出的方案則成功實(shí)現(xiàn)。要糾正系統(tǒng)，操作員應(yīng)根據(jù)結(jié)果手動(dòng)改變權(quán)重值。文中方案以自動(dòng)的方式調(diào)整權(quán)重值且具有良好性能，并且很好地適應(yīng)系統(tǒng)環(huán)境的變化。據(jù)此可以得出結(jié)論，文中方案可以快速收斂到系統(tǒng)的變化。

實(shí)際上，在操作系統(tǒng)時(shí)，系統(tǒng)錯(cuò)誤經(jīng)常發(fā)生，服務(wù)執(zhí)行概率通常是異構(gòu)的，負(fù)載均衡失敗會(huì)導(dǎo)致特定系統(tǒng)負(fù)載的增加，這就可能導(dǎo)致系統(tǒng)連續(xù)出錯(cuò)。仿真結(jié)果表明，當(dāng)服務(wù)執(zhí)行的概率異構(gòu)或系統(tǒng)處于錯(cuò)誤環(huán)境時(shí)，文中提出的方案比以前的方案表現(xiàn)出更好的負(fù)載均衡性能。此外，由于諸如用戶數(shù)量或注冊的服務(wù)模式之類的系統(tǒng)環(huán)境的改變，服務(wù)執(zhí)行概率本身可以被改變。在這種情況下，快速調(diào)整新系統(tǒng)就變得尤為重要。使用手動(dòng)設(shè)置的重量值，很難快速響應(yīng)系統(tǒng)的變化，而文中方案可以自動(dòng)設(shè)置權(quán)重值，并且能夠高速收斂到系統(tǒng)變化。

4 結(jié)束語

提出了一種在IMS網(wǎng)絡(luò)中使用多個(gè)異構(gòu)AS時(shí)對服務(wù)觸發(fā)數(shù)據(jù)包進(jìn)行負(fù)載均衡的方案?？梢詮腅MS的統(tǒng)計(jì)信息中獲取每個(gè)服務(wù)的執(zhí)行概率，以及從HSS下載的iFC是在哪個(gè)AS上注冊哪些服務(wù)的信息。基于以上兩條信息，可以通過調(diào)整每個(gè)AS的服務(wù)觸發(fā)概率來執(zhí)行負(fù)載均衡。該負(fù)載均衡方案可以自動(dòng)設(shè)置權(quán)重值，而現(xiàn)有方案基于操作員手動(dòng)設(shè)置。因此，該方案可以更好地適應(yīng)系統(tǒng)的變化，如系統(tǒng)錯(cuò)誤，新服務(wù)的注冊或新的AS添加到網(wǎng)絡(luò)。此外，還提出了一種在同類列集存在時(shí)減少計(jì)算的方法。仿真結(jié)果表明，該方案比現(xiàn)有方案(例如循環(huán)和專用AS觸發(fā)器)具有更好的負(fù)載均衡性能，尤其是當(dāng)系統(tǒng)發(fā)生變化時(shí)。