一種SRIO網(wǎng)絡(luò)負(fù)載均衡最短路徑路由算法

李嘉偉,張 激,趙俊才,丁如藝

(中國(guó)電子科技集團(tuán)公司第三十二研究所,上海 201808)

0 概述

串行高速輸入-輸出(Serial Rapid Input and Output,SRIO)采用將高速差分信號(hào)傳輸與交換技術(shù)相結(jié)合,以其高帶寬、低時(shí)延、高可靠性等優(yōu)點(diǎn)逐漸取代并行總線架構(gòu)[1-3]。SRIO總線支持點(diǎn)對(duì)點(diǎn)通信,也可以通過交換機(jī)實(shí)現(xiàn)星型、網(wǎng)型拓?fù)浣Y(jié)構(gòu),滿足嵌入式領(lǐng)域所需要的靈活性、可擴(kuò)展性、魯棒性等要求[4]。

傳統(tǒng)SRIO系統(tǒng)有著固定的網(wǎng)絡(luò)拓?fù)潢P(guān)系,但在新的SRIO網(wǎng)絡(luò)管理功能中,固定拓?fù)浞绞綗o法更好地滿足高靈活性、高擴(kuò)展性及負(fù)載均衡等需求。為此,眾多學(xué)者利用SRIO協(xié)議的機(jī)制,通過網(wǎng)絡(luò)遍歷探測(cè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),實(shí)現(xiàn)了節(jié)點(diǎn)枚舉及全網(wǎng)多源最短路徑探索,進(jìn)而動(dòng)態(tài)地完成節(jié)點(diǎn)入網(wǎng)、節(jié)點(diǎn)退網(wǎng)、最短路徑計(jì)算、負(fù)載均衡等高級(jí)SRIO網(wǎng)絡(luò)管理功能。

在以往小規(guī)模SRIO網(wǎng)絡(luò)中,常采用靜態(tài)配置方法更新內(nèi)置路由表,動(dòng)態(tài)配置則通過RapidIO維護(hù)包的方式實(shí)現(xiàn)。動(dòng)態(tài)配置可通過交換設(shè)備的任意一個(gè)端口進(jìn)行,實(shí)現(xiàn)對(duì)交換設(shè)備的靈活配置[5-6]。Linux下枚舉RapidIO網(wǎng)絡(luò)采用的算法是遞歸的、深度優(yōu)先圖表遍歷的算法[7]。文獻(xiàn)[8]提出一種深度優(yōu)先搜索的算法對(duì)SRIO網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行枚舉,在硬件平臺(tái)上實(shí)現(xiàn)了路由自動(dòng)搜索及配置功能。文獻(xiàn)[9]分析了深度優(yōu)先搜索算法的不足,提出使用非遞歸的廣度優(yōu)先算法實(shí)現(xiàn)路由配置,該算法有效減少了平均跳數(shù),但該算法仍需要一個(gè)深度遍歷的輔助函數(shù)。文獻(xiàn)[10]針對(duì)Linux內(nèi)核中RapidIO網(wǎng)絡(luò)路徑分配在負(fù)載均衡方面存在的不足,以鏈路限定帶寬為約束,使用估價(jià)函數(shù)h(n)=0的A*算法搜索節(jié)點(diǎn)間的最短路徑。但當(dāng)估價(jià)函數(shù)h(n)=0時(shí),A*算法退化為廣度優(yōu)先搜索算法,即該算法是一個(gè)基于廣度優(yōu)先搜索(Breadth First Search,BFS)的最小跳數(shù)路由算法。文獻(xiàn)[11]提出約束嚴(yán)苛度的概念,使用Dijkstra最短路徑計(jì)算不同約束度量下的最短路徑,通過不同路徑下的約束嚴(yán)苛度選擇路由路徑。文獻(xiàn)[12]引入流量驅(qū)動(dòng)機(jī)制,提出了最小隔離塊的概念和流量驅(qū)動(dòng)能量感知路徑算法,但該算法仍采用深度優(yōu)先遍歷的算法對(duì)SRIO網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行枚舉。

上述算法在對(duì)SRIO網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)配置的同時(shí)缺少對(duì)鏈路負(fù)載均衡方面的研究,且SRIO網(wǎng)絡(luò)的路由是交換節(jié)點(diǎn)到設(shè)備節(jié)點(diǎn)的多源最短路徑問題,對(duì)于該問題采用Dijkstra算法進(jìn)行計(jì)算存在重復(fù)計(jì)算、時(shí)間復(fù)雜度較高等問題。多源最短路徑可以采用基于動(dòng)態(tài)規(guī)劃思想的Floyd-Warshall算法進(jìn)行計(jì)算。

為彌補(bǔ)以上算法在負(fù)載均衡方面研究的不足,本文提出負(fù)載均衡最短路徑靜態(tài)路由算法。該算法使用廣度搜索算法對(duì)SRIO網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行枚舉,以改進(jìn)的Floyd-Warshall算法計(jì)算網(wǎng)絡(luò)中交換節(jié)點(diǎn)之間的K最短路徑,并提出端口期望負(fù)載的概念,將路由分解為交換節(jié)點(diǎn)之間和交換節(jié)點(diǎn)與設(shè)備節(jié)點(diǎn)之間兩部分,在交換節(jié)點(diǎn)之間采用負(fù)載均衡算法從K最短路徑中選路,使路由均衡地通過SRIO網(wǎng)絡(luò)。

1 SRIO網(wǎng)絡(luò)特征分析

1.1 SRIO網(wǎng)絡(luò)結(jié)構(gòu)

串行RapidIO采用邏輯層、傳輸層和物理層三層分級(jí)體系結(jié)構(gòu)。邏輯層定義全部協(xié)議和包的格式,為端點(diǎn)設(shè)備器件發(fā)起和完成事務(wù)提供必要的信息;傳輸層定義SRIO地址空間和在端點(diǎn)器件間傳輸包所需要的路由信息;物理層定義設(shè)備級(jí)的接口細(xì)節(jié),如包傳輸機(jī)制、流量控制、電器特性和低級(jí)錯(cuò)誤管理。物理層采用串行差分模擬信號(hào)傳輸,可雙向傳輸。

SRIO操作均基于請(qǐng)求和響應(yīng),其中包是系統(tǒng)中的基本通信單元。源設(shè)備發(fā)起一次SRIO操作會(huì)向SRIO路由交換網(wǎng)絡(luò)發(fā)送一個(gè)請(qǐng)求事務(wù),交換網(wǎng)絡(luò)向源設(shè)備返回控制符號(hào)以確認(rèn)收到該請(qǐng)求事務(wù),然后交換設(shè)備將請(qǐng)求事務(wù)轉(zhuǎn)發(fā)至目的設(shè)備;目的設(shè)備根據(jù)請(qǐng)求事務(wù)類型完成相應(yīng)的操作,隨即產(chǎn)生響應(yīng)事務(wù)并傳遞至SRIO路由交換網(wǎng)絡(luò),最后傳遞至源設(shè)備中,響應(yīng)事務(wù)在源設(shè)備確認(rèn)后,該次SRIO操作全部完成。交換芯片根據(jù)包的包頭數(shù)據(jù),通過內(nèi)置路由表映射的方式將SRIO網(wǎng)絡(luò)包從輸入端口傳送至不同的輸出端口,實(shí)現(xiàn)遠(yuǎn)程設(shè)備之間的互聯(lián)通信。事務(wù)在SRIO系統(tǒng)中傳遞流程如圖1所示。

圖1 SRIO網(wǎng)絡(luò)中的事務(wù)傳遞流程

SRIO具有多種事務(wù)類型,其中包括Maintenance事務(wù)、Nread事務(wù)、Nwrite事務(wù)、Swrite事務(wù)、Doorbell事務(wù)、Message事務(wù)等。Maintenance事務(wù)主要用于SRIO網(wǎng)絡(luò)的維護(hù)操作,包括配置路由、檢查鏈路狀態(tài)等。對(duì)SRIO交換網(wǎng)絡(luò)自動(dòng)搜索未知節(jié)點(diǎn),檢查交換芯片鏈路狀態(tài),校驗(yàn)芯片器件號(hào),識(shí)別芯片類型,配置內(nèi)置路由表等均需要使用Maintenance事務(wù)對(duì)芯片的寄存器進(jìn)行操作。Nread事務(wù)為普通讀操作,可以直接從端內(nèi)存讀取數(shù)據(jù),通常數(shù)據(jù)包最大為256 Byte;Nwrite事務(wù)可以直接往端內(nèi)存寫數(shù)據(jù);Doorbell事務(wù)的包頭和攜帶的信息都很短,該事務(wù)用于提供一個(gè)快速的短消息通知;Message事務(wù)用于傳輸大數(shù)據(jù)包,每次最多4 kB[13]。

1.2 SRIO網(wǎng)絡(luò)包交換屬性

RapidIO總線是基于包交換的傳輸協(xié)議,包是RapidIO協(xié)議中基本的傳輸單位。如圖2所示,RapidIO網(wǎng)絡(luò)通常由設(shè)備節(jié)點(diǎn)和交換節(jié)點(diǎn)兩種器件構(gòu)成。設(shè)備節(jié)點(diǎn)是各種處理器節(jié)點(diǎn),包括DSP、FPGA以及各種CPU等。設(shè)備節(jié)點(diǎn)是數(shù)據(jù)包的源端和目的端,在網(wǎng)絡(luò)中作為數(shù)據(jù)交換的發(fā)起方或接收方;交換節(jié)點(diǎn)為RapidIO交換芯片。交換芯片通常不發(fā)起請(qǐng)求包,其作用是根據(jù)內(nèi)置路由表將包含不同目的ID的數(shù)據(jù)包傳送到不同的端口,目前典型的交換設(shè)備是美國(guó)IDT公司的第二代RapidIO交換芯片CPS1848,該芯片符合RapidIO 2.1規(guī)范,具有18個(gè)端口,每個(gè)端口提供256個(gè)緩存來存儲(chǔ)設(shè)備路由表,對(duì)外提供48路全雙工高速串行通道,峰值吞吐量可達(dá)240 Gb/s,是目前較先進(jìn)的RapidIO交換芯片[14-15]。CPS1848每個(gè)端口都可以靈活配置成1x、2x、4x 3種模式,支持1.25 Gb/s、2.5 Gb/s、3.125 Gb/s、5.0 Gb/s、6.25 Gb/s等多種傳輸速率,然而這只是理論值,低效的傳輸機(jī)制設(shè)計(jì)或繁瑣的實(shí)現(xiàn)過程都會(huì)導(dǎo)致其傳輸速率大幅降低[16]。

圖2 典型SRIO網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

RapidIO數(shù)據(jù)包由包頭、可選載荷數(shù)據(jù)和16位CRC校驗(yàn)組成。RapidIO協(xié)議邏輯層定義了操作協(xié)議和相應(yīng)的包格式,如圖3所示,包頭由不同功能字段組成,包括TT、FType、Destination ID、Source ID、Logical Transaction等;每包的載荷數(shù)據(jù)長(zhǎng)度不超過256 Byte,這有利于減少傳輸時(shí)延,簡(jiǎn)化硬件實(shí)現(xiàn)。傳輸層定義了包交換的路由和尋址機(jī)制,每個(gè)終端設(shè)備具有唯一的器件ID,交換設(shè)備根據(jù)包的目的設(shè)備ID,交換設(shè)備本身沒有設(shè)備ID。物理層一般使用1x/4x串行協(xié)議,采用差分交流耦合信號(hào)進(jìn)行通信,具有抗干擾能力強(qiáng)、速率高、傳輸距離較遠(yuǎn)等優(yōu)點(diǎn)。由RapidIO協(xié)議傳輸層的特點(diǎn)分析可知,SRIO網(wǎng)絡(luò)的節(jié)點(diǎn)枚舉和路由表配置實(shí)質(zhì)是一個(gè)路徑分配問題,即在交換設(shè)備中為每一個(gè)終端設(shè)備分配一個(gè)端口,用于將包轉(zhuǎn)發(fā)到設(shè)備節(jié)點(diǎn)。

圖3 RapidIO數(shù)據(jù)包結(jié)構(gòu)

1.3 深度遍歷的路由自動(dòng)搜索及配置方法分析

當(dāng)前在工程實(shí)踐中使用較為廣泛的是基于深度搜索算法實(shí)現(xiàn)的網(wǎng)絡(luò)搜索和枚舉算法。深度優(yōu)先搜索也稱為深度優(yōu)先遍歷,可對(duì)每一個(gè)可能的分支路徑深度搜索到不能再深入為止,而且每一個(gè)節(jié)點(diǎn)只能訪問一次,其實(shí)質(zhì)是一個(gè)遞歸算法。深度搜索算法的結(jié)果是一顆多叉樹,難以完整保留網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),導(dǎo)致難以對(duì)路由進(jìn)行優(yōu)化。對(duì)于圖2所示的典型SRIO網(wǎng)絡(luò),若采用深度優(yōu)先搜索算法對(duì)網(wǎng)絡(luò)中的路由進(jìn)行配置,將Device0作為枚舉算法的主節(jié)點(diǎn),則將可能生如圖4所示的網(wǎng)絡(luò)生成樹,生成的路由表如表1所示。

圖4 深度遍歷算法生成的多叉樹

Table 1 SRIO network routing table configured by depth first algorithm

Switch0Switch1Switch2DeviceIDPortDeviceIDPortDeviceIDPort050101161111212521313631414045515056

深度優(yōu)先搜索算法比較適合節(jié)點(diǎn)較少網(wǎng)絡(luò),此時(shí)一方面不需要進(jìn)行過多的深度遍歷算法的回溯操作,另一方面小型網(wǎng)絡(luò)對(duì)于網(wǎng)絡(luò)負(fù)載均衡方面沒有過高的要求。但深度優(yōu)先搜索路徑分配算法的網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模和網(wǎng)絡(luò)結(jié)構(gòu)較為復(fù)雜,當(dāng)網(wǎng)絡(luò)連通度較高時(shí)存在一些局限性。在深度優(yōu)先搜索算法形成的樹形網(wǎng)絡(luò)中,主節(jié)點(diǎn)是根,交換節(jié)點(diǎn)為中間節(jié)點(diǎn),設(shè)備節(jié)點(diǎn)是葉子節(jié)點(diǎn)。顯然,使用深度搜索算法分配的路徑并不是最優(yōu)路徑,深度搜索算法忽略了從節(jié)點(diǎn)與高層次節(jié)點(diǎn)之間的其他物理通路,而只與直接高層次節(jié)點(diǎn)形成通路。其原因是深度優(yōu)先搜索算法在遍歷過程中未完整記錄和使用節(jié)點(diǎn)的鄰接點(diǎn)信息,無法根據(jù)網(wǎng)絡(luò)真實(shí)的拓?fù)浣Y(jié)構(gòu)從多條路徑中選出最優(yōu)路徑。

由以上分析可以看出,深度優(yōu)先搜索算法在RapidIO交換網(wǎng)絡(luò)路徑配置方面有較大的局限性。其主要原因是該算法的網(wǎng)絡(luò)生成樹忽略了節(jié)點(diǎn)之間的拓?fù)湫畔?進(jìn)而無法對(duì)路徑選路進(jìn)行優(yōu)化。針對(duì)這種情況,本文對(duì)SRIO網(wǎng)絡(luò)圖遍歷算法加以改進(jìn),采用廣度優(yōu)先搜索算法對(duì)SRIO網(wǎng)絡(luò)進(jìn)行一次遍歷,使用鄰接表完整地保留網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。并在遍歷過程中分別對(duì)終端設(shè)備節(jié)點(diǎn)和交換設(shè)備枚舉各自獨(dú)立的唯一ID,用于設(shè)備唯一標(biāo)識(shí)。針對(duì)路徑選路非最優(yōu)的問題,本文設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法用于最優(yōu)選路。

2 SRIO網(wǎng)絡(luò)模型

2.1 SRIO網(wǎng)絡(luò)路由模型

在網(wǎng)絡(luò)算法研究中常用圖論工具來描述。SRIO總線技術(shù)采用全雙工通信,因此可以采用無向圖G(V,E)來表示SRIO網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。V中的元素代表兩類網(wǎng)絡(luò)節(jié)點(diǎn),分為交換節(jié)點(diǎn)(Switch)和設(shè)備節(jié)點(diǎn)(Device)。其中,n表示V中交換節(jié)點(diǎn)的個(gè)數(shù),m表示V中終端節(jié)點(diǎn)的個(gè)數(shù)(0

在SRIO網(wǎng)絡(luò)中,任意兩個(gè)Device節(jié)點(diǎn)之間的路由Ri,j可通過有限個(gè)Switch節(jié)點(diǎn)轉(zhuǎn)發(fā)實(shí)現(xiàn)。假設(shè)Di、Dj表示Device節(jié)點(diǎn),S1,S2,…,Sk為最短路徑路由通過的k個(gè)Switch節(jié)點(diǎn),則路由路徑為:

由于Di必須通過掛接的S1節(jié)點(diǎn)與網(wǎng)絡(luò)中的其他終端節(jié)點(diǎn)進(jìn)行通信,Dj必須通過Sk節(jié)點(diǎn)接收網(wǎng)絡(luò)中其他節(jié)點(diǎn)的包,則如式(1)所示,RDi,Dj可以分解成三段路由,其中,RDi,S1、RSk,Dj固定不可更改,RS1,Sk表示交換節(jié)點(diǎn)S1至Sk的路由。

RDi,Dj=RDi,S1+RS1,Sk+RSk,Dj

(1)

由以上分析可知,在實(shí)際路由配置中,路由算法只需要計(jì)算Switch節(jié)點(diǎn)到達(dá)Device節(jié)點(diǎn)的最短路徑,并可以通過為Sk上的每一個(gè)Device節(jié)點(diǎn)配置不同RS1,Sk,以達(dá)到負(fù)載均衡的目的。因此,如圖5所示SRIO網(wǎng)絡(luò)的路由配置可以抽象為以Switch為源節(jié)點(diǎn)、以Device為目的節(jié)點(diǎn),通過中間Switch節(jié)點(diǎn)構(gòu)建的單向路徑。Switch節(jié)點(diǎn)的內(nèi)置路由表中存儲(chǔ)該節(jié)點(diǎn)指向Device節(jié)點(diǎn)的端口號(hào)。由于設(shè)備節(jié)點(diǎn)ID使用枚舉算法遞增生成,因此在算法運(yùn)行過程中內(nèi)置路由表可以使用直接Hash表存儲(chǔ),以便降低算法時(shí)間復(fù)雜度。

圖5 SRIO網(wǎng)絡(luò)路由表配置的抽象模型

Fig.5Abstract model of SRIO network routing tableconfiguration

2.2 期望負(fù)載

定義1源節(jié)點(diǎn)Si為Switch節(jié)點(diǎn),Dj為Device節(jié)點(diǎn),源和目的節(jié)點(diǎn)對(duì)(Si,Dj)之間的路由通過端口PSi,Dj進(jìn)行轉(zhuǎn)發(fā),則定義源目的節(jié)點(diǎn)對(duì)(Si,Dj)路由通過的端口PSi,Dj的端口期望負(fù)載為Φ(PSi,Dj)。Si節(jié)點(diǎn)在端口P上的總端口期望負(fù)載ΨSi(P)定義如下:

(2)

為簡(jiǎn)化網(wǎng)絡(luò)模型,設(shè)交換節(jié)點(diǎn)至任意一個(gè)設(shè)備節(jié)點(diǎn)的端口期望負(fù)載Φ(PSi,Di)為1。端口期望負(fù)載與內(nèi)置路由表中端口的使用數(shù)目呈正相關(guān)。

定義2Device節(jié)點(diǎn)對(duì)(Di,Dj)之間存在路由,且該路由通過鏈路I的期望負(fù)載如下:

T(Di,Dj)=pi,j×Qi,j

(3)

在鏈路I上的總的期望負(fù)載I被定義為如下等式:

(4)

其中,pi,j為終端節(jié)點(diǎn)(Di,Dj)之間的通信概率,Qi,j為終端節(jié)點(diǎn)(Di,Dj)之間的通信帶寬。為簡(jiǎn)化模型,假定任意兩個(gè)設(shè)備節(jié)點(diǎn)之間的通信負(fù)載T(Di,Dj)均相等。

結(jié)合文獻(xiàn)[17]對(duì)網(wǎng)絡(luò)多路徑負(fù)載均衡算法的闡述,以及MPLS網(wǎng)絡(luò)鏈路預(yù)期負(fù)載分析的啟發(fā),本文針對(duì)SRIO網(wǎng)絡(luò)協(xié)議傳輸層的特點(diǎn)引入了端口期望負(fù)載這一概念。其中,端口期望負(fù)載ΨSi(P)和節(jié)點(diǎn)對(duì)(Di,Dj)之間的鏈路期望負(fù)載∏I是靜態(tài)的,因?yàn)樗鼈兪怯删W(wǎng)絡(luò)拓?fù)錄Q定的,只有當(dāng)網(wǎng)絡(luò)拓?fù)涓淖儠r(shí)才改變。因此,端口期望負(fù)載只需要離線預(yù)先計(jì)算,且當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)才重新計(jì)算。

為了能確定具體的路由路徑,必須把每一個(gè)端口上的端口期望負(fù)載轉(zhuǎn)化為該交換設(shè)備上的端口轉(zhuǎn)發(fā)成本,這樣才能實(shí)現(xiàn)負(fù)載均衡的路由選路算法。本文設(shè)計(jì)的算法將以端口期望負(fù)載為成本,從SRIO網(wǎng)絡(luò)路由的K最短路徑中選擇端口期望負(fù)載最低的端口對(duì)SRIO網(wǎng)絡(luò)路由表進(jìn)行配置,以達(dá)到負(fù)載均衡的目的。

2.3 保存網(wǎng)絡(luò)節(jié)點(diǎn)信息的結(jié)構(gòu)體定義

為了對(duì)SRIO網(wǎng)絡(luò)的路由進(jìn)行優(yōu)化,必須在搜索和枚舉過程中,由配置主機(jī)將各網(wǎng)絡(luò)節(jié)點(diǎn)信息存入到結(jié)構(gòu)體rioSwitch中,結(jié)構(gòu)體rioSwitch如下:

typedef struct rioSwitch{

u16 Identity;

u16 DeviceID;

u16 issearched;

u16 rioid[MAX_ROUTE_TABLE];

u16 distance[MAX_ROUTE_TABLE];

struct rioSwitch*port[MAX_SWITCH_PORTS];

}rioSwitch;

在結(jié)構(gòu)體rioSwitch中,identity記錄節(jié)點(diǎn)類型,分別為交換節(jié)點(diǎn)Switch和設(shè)備節(jié)點(diǎn)Device。DeviceID字段為網(wǎng)絡(luò)節(jié)點(diǎn)枚舉的唯一ID,但交換節(jié)點(diǎn)和設(shè)備節(jié)點(diǎn)ID是分別枚舉的;issearched是標(biāo)記該節(jié)點(diǎn)是否已經(jīng)被搜索過;rioid[]字段為直接Hash存儲(chǔ)的路由表,數(shù)組下標(biāo)為設(shè)備節(jié)點(diǎn)的枚舉ID,數(shù)組中對(duì)應(yīng)存儲(chǔ)的值是該Switch節(jié)點(diǎn)路由至設(shè)備節(jié)點(diǎn)的端口號(hào);distance為對(duì)應(yīng)路由表中各路由的長(zhǎng)度;port指針用于模擬交換節(jié)點(diǎn)間的物理連接。

3 算法描述

負(fù)載均衡最短路徑靜態(tài)路由算法主要由以下3個(gè)部分組成:1)使用寬度搜索算法實(shí)現(xiàn)節(jié)點(diǎn)ID枚舉和網(wǎng)絡(luò)拓?fù)涮綔y(cè);2)使用動(dòng)態(tài)規(guī)劃算法計(jì)算Switch節(jié)點(diǎn)之間的K最短路徑;3)結(jié)合端口期望負(fù)載概念對(duì)Switch的內(nèi)置路由表進(jìn)行選路,均衡鏈路的期望負(fù)載。

3.1 網(wǎng)絡(luò)節(jié)點(diǎn)枚舉和拓?fù)涮綔y(cè)

拓?fù)涮綔y(cè)的過程就是以一定規(guī)則的算法遍歷系統(tǒng)中所有的交換節(jié)點(diǎn)和設(shè)備節(jié)點(diǎn),建立起各個(gè)節(jié)點(diǎn)之間的拓?fù)潢P(guān)系。針對(duì)這個(gè)問題,本文將節(jié)點(diǎn)之間的鏈路看做一條長(zhǎng)度為1的邊,定義Switch[n]數(shù)組存儲(chǔ)各個(gè)節(jié)點(diǎn)的物理信息和拓?fù)潢P(guān)系,定義swList結(jié)構(gòu)體用于存儲(chǔ)K最短路徑,保存其最短路徑的端口信息。其結(jié)構(gòu)定義如下:

typedef struct swList{

int num;

u16 port[MAX_SWITCH_PORTS];

int distance;

}swList;

在結(jié)構(gòu)定義中,num字段保存滿足當(dāng)前K最短路徑的端口個(gè)數(shù);port數(shù)組中保存K最短路徑的端口信息;distance字段保存距離信息,宏定義MAX_SWITCH_PORTS為交換節(jié)點(diǎn)支持的最大端口數(shù),例如交換芯片CPS1848的端口數(shù)為18。如式(5)所示,定義最短路徑端口隊(duì)列矩陣List[n][n]保存各個(gè)設(shè)備之間的端口信息和距離信息,初始時(shí)設(shè)置距離為無限大,并在第一次廣度搜索SRIO網(wǎng)絡(luò)對(duì)交換節(jié)點(diǎn)進(jìn)行枚舉時(shí),更新所有相鄰的交換節(jié)點(diǎn)最短路徑端口信息,并以鄰接的路徑信息計(jì)算其他節(jié)點(diǎn)間的最短路徑。

(5)

1.3節(jié)分析了深度搜索算法的不足,本文通過廣度優(yōu)先搜索遍歷所有交換節(jié)點(diǎn)組成的子網(wǎng),并在遍歷交換節(jié)點(diǎn)的過程中,遞增枚舉掛接在該交換節(jié)點(diǎn)上的所有設(shè)備節(jié)點(diǎn)的設(shè)備ID,廣度遍歷搜索算法流程如圖6所示。

圖6 廣度遍歷搜索算法流程

具體算法描述如下:

算法1網(wǎng)絡(luò)節(jié)點(diǎn)枚舉和拓?fù)涮綔y(cè)算法

步驟1將進(jìn)行枚舉的Device節(jié)點(diǎn)標(biāo)記為主節(jié)點(diǎn),將Device節(jié)點(diǎn)所連接的Switch節(jié)點(diǎn)加入隊(duì)列L。

步驟2若隊(duì)列非空,則取隊(duì)列頭節(jié)點(diǎn)H,遍歷該Switch節(jié)點(diǎn)H連接的所有節(jié)點(diǎn)。

步驟3如果節(jié)點(diǎn)N是Device節(jié)點(diǎn),且節(jié)點(diǎn)N未被訪問過,則將N標(biāo)記為已被訪問,并枚舉N的DeviceID。

步驟4如果節(jié)點(diǎn)N是Switch節(jié)點(diǎn),則在List[n][n]矩陣中更新相鄰交換節(jié)點(diǎn)的最短路徑端口,設(shè)置路由距離為1,若節(jié)點(diǎn)N已被訪問過則進(jìn)入步驟6,否則進(jìn)入步驟5。

步驟5配置節(jié)點(diǎn)N的SwitchID,將節(jié)點(diǎn)N加入隊(duì)列L。

步驟6如果隊(duì)列L非空,則跳轉(zhuǎn)到步驟2,否則算法結(jié)束。

當(dāng)主節(jié)點(diǎn)完成廣度搜索枚舉過程后,SRIO網(wǎng)絡(luò)的物理拓?fù)浣Y(jié)構(gòu)被保存在rioSwitch結(jié)構(gòu)體中,交換節(jié)點(diǎn)間相鄰的最短路徑信息被保存在List[n][n]中。枚舉程序?yàn)槊恳粋€(gè)Device節(jié)點(diǎn)和Switch節(jié)點(diǎn)分配唯一的DeviceID和SwitchID。使用該算法能夠有效保留SRIO網(wǎng)絡(luò)全部的拓?fù)潢P(guān)系,為下一步路由算法的優(yōu)化提供必要的信息,且該算法時(shí)間復(fù)雜度為O(V),僅與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)相關(guān),能夠快速地對(duì)SRIO網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行枚舉。

3.2 動(dòng)態(tài)規(guī)劃算法K最短路徑的計(jì)算

Floyd-WarShall算法是采用動(dòng)態(tài)規(guī)劃思想實(shí)現(xiàn)的經(jīng)典多源最短路徑算法,該算法可以求解出無向圖中任意兩點(diǎn)之間的最短路徑。但對(duì)于較為復(fù)雜的SRIO網(wǎng)絡(luò),往往存在多個(gè)最短路徑,而使用Floyd-WarShall算法時(shí),只能隨機(jī)地使用其中一個(gè)最優(yōu)路徑,難以最優(yōu)地解決鏈路負(fù)載均衡問題。但受動(dòng)態(tài)規(guī)劃思想的啟發(fā),本文在其基礎(chǔ)上修改了算法中的評(píng)價(jià)函數(shù),在保證實(shí)現(xiàn)最短距離不變的情況下,將最短距離相等的端口信息保存在List[n][n]中。算法偽代碼如下:

算法2動(dòng)態(tài)規(guī)劃算法計(jì)算Switch節(jié)點(diǎn)間的K最短路徑

輸入List[n][n],n

輸出List[n]

1.for(int k = 0; k < n; ++k)

2.for(int i = 0; i < n; ++i);

3.for(int j = 0; j

4.if(List[i][k].distance+List[k][j].distance < List[i][j].distance){

5.List[i][j].distance=List[i][k].distance + List[k][j].distance;

6.List[i][j].num=1;

7.}else if(List[i][k].distance + List[k][j].distance==List[i][j].distance){

8.for(int x = 0; x < List[i][k].num; x++)

9.for(int y = 0; y < List[i][j].num; y++){

10.if(List[i][k].port[x] == List[i][j].port[y])

11.break;

12.if(y == List[i][j].num){

13.List[i][j].port[y] = List[i][k].port[x];

14.List[i][j].num++;

15.}

16.}

經(jīng)算法2的計(jì)算后,List[n][n]中已經(jīng)保留了所有交換節(jié)點(diǎn)之間K最短路徑的端口信息,這些端口信息將會(huì)用于第3階段負(fù)載均衡的選路算法中。路由的過程即為路由表不斷解析轉(zhuǎn)發(fā)端口的過程,如圖7所示,圖中節(jié)點(diǎn)均為Switch節(jié)點(diǎn),則節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑有4條,從節(jié)點(diǎn)i出發(fā)的端口有2個(gè),經(jīng)過動(dòng)態(tài)規(guī)劃算法以后,List[i][j].port[]保留了這2個(gè)端口。根據(jù)第2節(jié)中分析得知,Ri,j=min(Ri,k+Rk,j),結(jié)合中間節(jié)點(diǎn)k1、k2、k3、k4、k5中保留的指向節(jié)點(diǎn)j的端口信息,即可計(jì)算得到完成的4條最短路徑。

圖7 節(jié)點(diǎn)i到節(jié)點(diǎn)j的K最短路徑

3.3 負(fù)載均衡的選路算法

SRIO網(wǎng)絡(luò)交換節(jié)點(diǎn)采用靜態(tài)路由配置,內(nèi)置路由表中記錄的交換節(jié)點(diǎn)至設(shè)備節(jié)點(diǎn)的端口一經(jīng)確定就不會(huì)主動(dòng)更改,因此對(duì)于SRIO網(wǎng)絡(luò)負(fù)載均衡只能考慮在路由配置階段對(duì)Switch節(jié)點(diǎn)至Device節(jié)點(diǎn)的多路徑進(jìn)行負(fù)載均衡。算法2計(jì)算了各個(gè)交換節(jié)點(diǎn)之間的K最短路徑,結(jié)合文獻(xiàn)[18-19]中鏈路期望負(fù)載的方法,本文定義了端口期望負(fù)載這個(gè)概念來表示交換節(jié)點(diǎn)分發(fā)端口的期望負(fù)載,為達(dá)到負(fù)載均衡的目的,在路由的端口選路過程中,應(yīng)以最短路徑為約束,選擇K最短路徑中端口期望負(fù)載最小的端口轉(zhuǎn)發(fā)數(shù)據(jù),以此達(dá)到負(fù)載均衡的目的。具體算法過程如下:

算法3負(fù)載均衡的路由選路算法

輸入List[n][n],Switch[n],n

輸出Switch[n]

1.for(int I = 0; i < n; ++i)

2.int cost[MAX_SWITCH_PORTS] = {0};

3.int best_port = 0;

4.for(int j = 0; j < n; ++j)

5.for(int k = 0; k < MAX_SWITCH_PORTS; ++k)

6.if(Switch[j].port[k].identity ==DEVICE){

7.for(int x = 0; x < List[i][j].num; ++x)

8.if(cost[List[i][j].port[x] > cost[best_port]]

9.best_port = x;

10.Switch[i].rioid[Switch[j].port[k].DeviceID] = best_port;

11.cost[best_port]++;

12.}

13.}

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

4.1 仿真模型

為研究本文提出的負(fù)載均衡最短路徑路由算法的實(shí)際效果,使用C語(yǔ)言編寫了3種算法的仿真程序。仿真中假設(shè)每一個(gè)交換節(jié)點(diǎn)均連接4個(gè)終端設(shè)備節(jié)點(diǎn),這一假設(shè)符合常用工程項(xiàng)目的實(shí)際情況。分別生成交換節(jié)點(diǎn)規(guī)模為4～15的無向圖,如表2所示。隨機(jī)無向圖的生成方法采用:先生成隨機(jī)連通樹,再采用隨機(jī)選取2個(gè)節(jié)點(diǎn)互相連接的方式創(chuàng)建隨機(jī)無向圖。交換設(shè)備之間的連通數(shù)體現(xiàn)了網(wǎng)絡(luò)的連通度,為了使仿真實(shí)驗(yàn)與實(shí)際情況更相像,本次仿真實(shí)驗(yàn)中設(shè)計(jì)的交換節(jié)點(diǎn)之間互相連接的端口數(shù)為2個(gè)～8個(gè),隨網(wǎng)絡(luò)規(guī)模的增長(zhǎng)而隨機(jī)生成,不失一般性,對(duì)每一種規(guī)模的網(wǎng)絡(luò)均隨機(jī)生成10 000個(gè)隨機(jī)無向連通圖,并計(jì)算各個(gè)不同網(wǎng)絡(luò)規(guī)模下的網(wǎng)絡(luò)路由性能的平均值,其中包括路由平均跳數(shù)、交換節(jié)點(diǎn)之間鏈路的期望負(fù)載、鏈路期望負(fù)載的方差等,并對(duì)采集的10 000個(gè)連通圖的數(shù)據(jù)取平均值后進(jìn)行繪圖分析。

表2 隨機(jī)無向圖中節(jié)點(diǎn)間連通度參數(shù)

Table 2 Connectivity parameters of nodes in random undirected graphs

交換設(shè)備節(jié)點(diǎn)規(guī)模交換設(shè)備節(jié)點(diǎn)間最小連接數(shù)交換設(shè)備節(jié)點(diǎn)間最大連接數(shù)4～5236～8249～112512～14261527

4.2 結(jié)果分析

針對(duì)隨機(jī)生成的10 000個(gè)SRIO網(wǎng)絡(luò)拓?fù)鋱D,使用多種算法配置Switch節(jié)點(diǎn)的內(nèi)置路由表。圖8所示是深度遍歷路由配置算法、最小跳數(shù)算法、負(fù)載均衡最小跳數(shù)路由算法3種算法在不同節(jié)點(diǎn)規(guī)模下所有設(shè)備節(jié)點(diǎn)間路由的平均跳數(shù)。隨著節(jié)點(diǎn)規(guī)模的增長(zhǎng),最小跳數(shù)算法相比深度遍歷算法能夠有效降低路由平均跳數(shù),當(dāng)交換節(jié)點(diǎn)規(guī)模大于4時(shí),最小跳數(shù)路由算法能夠有效降低路由平均跳數(shù)。相比深度遍歷的路由配置算法,最小跳數(shù)路由算法減少了約61.7%的路由跳數(shù),這對(duì)于降低網(wǎng)絡(luò)傳輸延時(shí),保證網(wǎng)絡(luò)傳輸?shù)姆€(wěn)定性具有重要的意義。

圖8 隨網(wǎng)絡(luò)規(guī)模變化的路由平均跳數(shù)

Fig.8 Average number of routing hops changing with network size

統(tǒng)計(jì)經(jīng)過不同算法配置路由表之后SRIO網(wǎng)絡(luò)中鏈路的平均期望負(fù)載,統(tǒng)計(jì)結(jié)果如圖9所示,從圖中可以看出,最小跳數(shù)路由算法能夠有效降低鏈路的平均期望負(fù)載,其原因是最小跳數(shù)路由算法采用廣度搜索算法,最大限度地保留了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),能夠有效利用所有的交換節(jié)點(diǎn)之間的鏈路對(duì)網(wǎng)絡(luò)路由進(jìn)行優(yōu)化;同時(shí),最小跳數(shù)路由算法的平均跳數(shù)低于深度優(yōu)先遍歷的路由配置算法,減小了包傳遞長(zhǎng)度,降低了網(wǎng)絡(luò)的總負(fù)載。因此,最小跳數(shù)路由算法在降低網(wǎng)絡(luò)總負(fù)載方面優(yōu)于深度遍歷路由配置算法。

圖9 隨網(wǎng)絡(luò)規(guī)模變化的鏈路平均期望負(fù)載

圖10 隨網(wǎng)絡(luò)規(guī)模增長(zhǎng)的負(fù)載方差

4.3 算法時(shí)間復(fù)雜度比較

當(dāng)SRIO網(wǎng)絡(luò)拓?fù)浠蛘哝溌钒l(fā)生變化時(shí)需要重新計(jì)算并更新路由表,因此路由表的計(jì)算時(shí)間是影響算法選擇的重要因素。本文在Inter 7700KCPU環(huán)境下進(jìn)行仿真,統(tǒng)計(jì)10 000個(gè)網(wǎng)絡(luò)交換節(jié)點(diǎn)規(guī)模為15的SRIO網(wǎng)絡(luò)路由表計(jì)算時(shí)間,結(jié)果如表3所示,負(fù)載均衡最小跳數(shù)路由算法的平均計(jì)算時(shí)間為0.04 ms,滿足SRIO網(wǎng)絡(luò)的實(shí)際工程需求。

表3 算法復(fù)雜度和路由表的計(jì)算時(shí)間

Table 3 Algorithm complexity and routing table computation time

算法算法復(fù)雜度10 000個(gè)無向圖的路由表總計(jì)算時(shí)間/10-3 sDFS算法O(V)37最小跳數(shù)路由算法O(V3s+V)411負(fù)載均衡最小跳數(shù)路由算法O(V3s+V2s+V)442

5 結(jié)束語(yǔ)

本文針對(duì)SRIO網(wǎng)絡(luò)深度優(yōu)先搜索分配路徑非最優(yōu)問題,引入端口期望負(fù)載概念,并結(jié)合K最短路徑算法,提出一種負(fù)載均衡最小跳數(shù)路由選路算法。該算法使用廣度搜索算法對(duì)SRIO網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行枚舉,以改進(jìn)的Floyd-WarShall算法計(jì)算網(wǎng)絡(luò)中交換節(jié)點(diǎn)之間的K最短路徑,并通過理論闡述和時(shí)延驗(yàn)證對(duì)路由選路算法進(jìn)行分析。實(shí)驗(yàn)結(jié)果表明,與深度遍歷路由配置算法、最小跳數(shù)路由算法、負(fù)載均衡最小跳數(shù)路由算法相比,該算法在降低路由平均跳數(shù)、實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡等方面具有較好的表現(xiàn)。下一步將在負(fù)載均衡最小跳數(shù)路由選路算法中加入傳輸錯(cuò)誤處理和網(wǎng)絡(luò)拓?fù)渥詣?dòng)枚舉更新策略,以提高算法的可適用性。