一種SRIO網絡負載均衡最短路徑路由算法

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

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

0 概述

串行高速輸入-輸出(Serial Rapid Input and Output,SRIO)采用將高速差分信號傳輸與交換技術相結合,以其高帶寬、低時延、高可靠性等優點逐漸取代并行總線架構[1-3]。SRIO總線支持點對點通信,也可以通過交換機實現星型、網型拓撲結構,滿足嵌入式領域所需要的靈活性、可擴展性、魯棒性等要求[4]。

傳統SRIO系統有著固定的網絡拓撲關系,但在新的SRIO網絡管理功能中,固定拓撲方式無法更好地滿足高靈活性、高擴展性及負載均衡等需求。為此,眾多學者利用SRIO協議的機制,通過網絡遍歷探測網絡拓撲結構,實現了節點枚舉及全網多源最短路徑探索,進而動態地完成節點入網、節點退網、最短路徑計算、負載均衡等高級SRIO網絡管理功能。

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

上述算法在對SRIO網絡進行動態配置的同時缺少對鏈路負載均衡方面的研究,且SRIO網絡的路由是交換節點到設備節點的多源最短路徑問題,對于該問題采用Dijkstra算法進行計算存在重復計算、時間復雜度較高等問題。多源最短路徑可以采用基于動態規劃思想的Floyd-Warshall算法進行計算。

為彌補以上算法在負載均衡方面研究的不足,本文提出負載均衡最短路徑靜態路由算法。該算法使用廣度搜索算法對SRIO網絡節點進行枚舉,以改進的Floyd-Warshall算法計算網絡中交換節點之間的K最短路徑,并提出端口期望負載的概念,將路由分解為交換節點之間和交換節點與設備節點之間兩部分,在交換節點之間采用負載均衡算法從K最短路徑中選路,使路由均衡地通過SRIO網絡。

1 SRIO網絡特征分析

1.1 SRIO網絡結構

串行RapidIO采用邏輯層、傳輸層和物理層三層分級體系結構。邏輯層定義全部協議和包的格式,為端點設備器件發起和完成事務提供必要的信息;傳輸層定義SRIO地址空間和在端點器件間傳輸包所需要的路由信息;物理層定義設備級的接口細節,如包傳輸機制、流量控制、電器特性和低級錯誤管理。物理層采用串行差分模擬信號傳輸,可雙向傳輸。

SRIO操作均基于請求和響應,其中包是系統中的基本通信單元。源設備發起一次SRIO操作會向SRIO路由交換網絡發送一個請求事務,交換網絡向源設備返回控制符號以確認收到該請求事務,然后交換設備將請求事務轉發至目的設備;目的設備根據請求事務類型完成相應的操作,隨即產生響應事務并傳遞至SRIO路由交換網絡,最后傳遞至源設備中,響應事務在源設備確認后,該次SRIO操作全部完成。交換芯片根據包的包頭數據,通過內置路由表映射的方式將SRIO網絡包從輸入端口傳送至不同的輸出端口,實現遠程設備之間的互聯通信。事務在SRIO系統中傳遞流程如圖1所示。

圖1 SRIO網絡中的事務傳遞流程

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

1.2 SRIO網絡包交換屬性

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

圖2 典型SRIO網絡拓撲結構

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

圖3 RapidIO數據包結構

1.3 深度遍歷的路由自動搜索及配置方法分析

當前在工程實踐中使用較為廣泛的是基于深度搜索算法實現的網絡搜索和枚舉算法。深度優先搜索也稱為深度優先遍歷,可對每一個可能的分支路徑深度搜索到不能再深入為止,而且每一個節點只能訪問一次,其實質是一個遞歸算法。深度搜索算法的結果是一顆多叉樹,難以完整保留網絡的拓撲結構,導致難以對路由進行優化。對于圖2所示的典型SRIO網絡,若采用深度優先搜索算法對網絡中的路由進行配置,將Device0作為枚舉算法的主節點,則將可能生如圖4所示的網絡生成樹,生成的路由表如表1所示。

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

Table 1 SRIO network routing table configured by depth first algorithm

Switch0Switch1Switch2DeviceIDPortDeviceIDPortDeviceIDPort050101161111212521313631414045515056

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

由以上分析可以看出,深度優先搜索算法在RapidIO交換網絡路徑配置方面有較大的局限性。其主要原因是該算法的網絡生成樹忽略了節點之間的拓撲信息,進而無法對路徑選路進行優化。針對這種情況,本文對SRIO網絡圖遍歷算法加以改進,采用廣度優先搜索算法對SRIO網絡進行一次遍歷,使用鄰接表完整地保留網絡的拓撲結構。并在遍歷過程中分別對終端設備節點和交換設備枚舉各自獨立的唯一ID,用于設備唯一標識。針對路徑選路非最優的問題,本文設計一個動態規劃算法用于最優選路。

2 SRIO網絡模型

2.1 SRIO網絡路由模型

在網絡算法研究中常用圖論工具來描述。SRIO總線技術采用全雙工通信,因此可以采用無向圖G(V,E)來表示SRIO網絡的拓撲結構。V中的元素代表兩類網絡節點,分為交換節點(Switch)和設備節點(Device)。其中,n表示V中交換節點的個數,m表示V中終端節點的個數(0

在SRIO網絡中,任意兩個Device節點之間的路由Ri,j可通過有限個Switch節點轉發實現。假設Di、Dj表示Device節點,S1,S2,…,Sk為最短路徑路由通過的k個Switch節點,則路由路徑為:

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

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

(1)

由以上分析可知,在實際路由配置中,路由算法只需要計算Switch節點到達Device節點的最短路徑,并可以通過為Sk上的每一個Device節點配置不同RS1,Sk,以達到負載均衡的目的。因此,如圖5所示SRIO網絡的路由配置可以抽象為以Switch為源節點、以Device為目的節點,通過中間Switch節點構建的單向路徑。Switch節點的內置路由表中存儲該節點指向Device節點的端口號。由于設備節點ID使用枚舉算法遞增生成,因此在算法運行過程中內置路由表可以使用直接Hash表存儲,以便降低算法時間復雜度。

圖5 SRIO網絡路由表配置的抽象模型

Fig.5Abstract model of SRIO network routing tableconfiguration

2.2 期望負載

定義1源節點Si為Switch節點,Dj為Device節點,源和目的節點對(Si,Dj)之間的路由通過端口PSi,Dj進行轉發,則定義源目的節點對(Si,Dj)路由通過的端口PSi,Dj的端口期望負載為Φ(PSi,Dj)。Si節點在端口P上的總端口期望負載ΨSi(P)定義如下:

(2)

為簡化網絡模型,設交換節點至任意一個設備節點的端口期望負載Φ(PSi,Di)為1。端口期望負載與內置路由表中端口的使用數目呈正相關。

定義2Device節點對(Di,Dj)之間存在路由,且該路由通過鏈路I的期望負載如下:

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

(3)

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

(4)

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

結合文獻[17]對網絡多路徑負載均衡算法的闡述,以及MPLS網絡鏈路預期負載分析的啟發,本文針對SRIO網絡協議傳輸層的特點引入了端口期望負載這一概念。其中,端口期望負載ΨSi(P)和節點對(Di,Dj)之間的鏈路期望負載∏I是靜態的,因為它們是由網絡拓撲決定的,只有當網絡拓撲改變時才改變。因此,端口期望負載只需要離線預先計算,且當網絡拓撲發生變化時才重新計算。

為了能確定具體的路由路徑,必須把每一個端口上的端口期望負載轉化為該交換設備上的端口轉發成本,這樣才能實現負載均衡的路由選路算法。本文設計的算法將以端口期望負載為成本,從SRIO網絡路由的K最短路徑中選擇端口期望負載最低的端口對SRIO網絡路由表進行配置,以達到負載均衡的目的。

2.3 保存網絡節點信息的結構體定義

為了對SRIO網絡的路由進行優化,必須在搜索和枚舉過程中,由配置主機將各網絡節點信息存入到結構體rioSwitch中,結構體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;

在結構體rioSwitch中,identity記錄節點類型,分別為交換節點Switch和設備節點Device。DeviceID字段為網絡節點枚舉的唯一ID,但交換節點和設備節點ID是分別枚舉的;issearched是標記該節點是否已經被搜索過;rioid[]字段為直接Hash存儲的路由表,數組下標為設備節點的枚舉ID,數組中對應存儲的值是該Switch節點路由至設備節點的端口號;distance為對應路由表中各路由的長度;port指針用于模擬交換節點間的物理連接。

3 算法描述

負載均衡最短路徑靜態路由算法主要由以下3個部分組成:1)使用寬度搜索算法實現節點ID枚舉和網絡拓撲探測;2)使用動態規劃算法計算Switch節點之間的K最短路徑;3)結合端口期望負載概念對Switch的內置路由表進行選路,均衡鏈路的期望負載。

3.1 網絡節點枚舉和拓撲探測

拓撲探測的過程就是以一定規則的算法遍歷系統中所有的交換節點和設備節點,建立起各個節點之間的拓撲關系。針對這個問題,本文將節點之間的鏈路看做一條長度為1的邊,定義Switch[n]數組存儲各個節點的物理信息和拓撲關系,定義swList結構體用于存儲K最短路徑,保存其最短路徑的端口信息。其結構定義如下:

typedef struct swList{

int num;

u16 port[MAX_SWITCH_PORTS];

int distance;

}swList;

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

(5)

1.3節分析了深度搜索算法的不足,本文通過廣度優先搜索遍歷所有交換節點組成的子網,并在遍歷交換節點的過程中,遞增枚舉掛接在該交換節點上的所有設備節點的設備ID,廣度遍歷搜索算法流程如圖6所示。

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

具體算法描述如下:

算法1網絡節點枚舉和拓撲探測算法

步驟1將進行枚舉的Device節點標記為主節點,將Device節點所連接的Switch節點加入隊列L。

步驟2若隊列非空,則取隊列頭節點H,遍歷該Switch節點H連接的所有節點。

步驟3如果節點N是Device節點,且節點N未被訪問過,則將N標記為已被訪問,并枚舉N的DeviceID。

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

步驟5配置節點N的SwitchID,將節點N加入隊列L。

步驟6如果隊列L非空,則跳轉到步驟2,否則算法結束。

當主節點完成廣度搜索枚舉過程后,SRIO網絡的物理拓撲結構被保存在rioSwitch結構體中,交換節點間相鄰的最短路徑信息被保存在List[n][n]中。枚舉程序為每一個Device節點和Switch節點分配唯一的DeviceID和SwitchID。使用該算法能夠有效保留SRIO網絡全部的拓撲關系,為下一步路由算法的優化提供必要的信息,且該算法時間復雜度為O(V),僅與網絡節點個數相關,能夠快速地對SRIO網絡中的節點進行枚舉。

3.2 動態規劃算法K最短路徑的計算

Floyd-WarShall算法是采用動態規劃思想實現的經典多源最短路徑算法,該算法可以求解出無向圖中任意兩點之間的最短路徑。但對于較為復雜的SRIO網絡,往往存在多個最短路徑,而使用Floyd-WarShall算法時,只能隨機地使用其中一個最優路徑,難以最優地解決鏈路負載均衡問題。但受動態規劃思想的啟發,本文在其基礎上修改了算法中的評價函數,在保證實現最短距離不變的情況下,將最短距離相等的端口信息保存在List[n][n]中。算法偽代碼如下:

算法2動態規劃算法計算Switch節點間的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.}

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

圖7 節點i到節點j的K最短路徑

3.3 負載均衡的選路算法

SRIO網絡交換節點采用靜態路由配置,內置路由表中記錄的交換節點至設備節點的端口一經確定就不會主動更改,因此對于SRIO網絡負載均衡只能考慮在路由配置階段對Switch節點至Device節點的多路徑進行負載均衡。算法2計算了各個交換節點之間的K最短路徑,結合文獻[18-19]中鏈路期望負載的方法,本文定義了端口期望負載這個概念來表示交換節點分發端口的期望負載,為達到負載均衡的目的,在路由的端口選路過程中,應以最短路徑為約束,選擇K最短路徑中端口期望負載最小的端口轉發數據,以此達到負載均衡的目的。具體算法過程如下:

算法3負載均衡的路由選路算法

輸入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 仿真結果與分析

4.1 仿真模型

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

表2 隨機無向圖中節點間連通度參數

Table 2 Connectivity parameters of nodes in random undirected graphs

交換設備節點規模交換設備節點間最小連接數交換設備節點間最大連接數4～5236～8249～112512～14261527

4.2 結果分析

針對隨機生成的10 000個SRIO網絡拓撲圖,使用多種算法配置Switch節點的內置路由表。圖8所示是深度遍歷路由配置算法、最小跳數算法、負載均衡最小跳數路由算法3種算法在不同節點規模下所有設備節點間路由的平均跳數。隨著節點規模的增長,最小跳數算法相比深度遍歷算法能夠有效降低路由平均跳數,當交換節點規模大于4時,最小跳數路由算法能夠有效降低路由平均跳數。相比深度遍歷的路由配置算法,最小跳數路由算法減少了約61.7%的路由跳數,這對于降低網絡傳輸延時,保證網絡傳輸的穩定性具有重要的意義。

圖8 隨網絡規模變化的路由平均跳數

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

統計經過不同算法配置路由表之后SRIO網絡中鏈路的平均期望負載,統計結果如圖9所示,從圖中可以看出,最小跳數路由算法能夠有效降低鏈路的平均期望負載,其原因是最小跳數路由算法采用廣度搜索算法,最大限度地保留了網絡拓撲結構,能夠有效利用所有的交換節點之間的鏈路對網絡路由進行優化;同時,最小跳數路由算法的平均跳數低于深度優先遍歷的路由配置算法,減小了包傳遞長度,降低了網絡的總負載。因此,最小跳數路由算法在降低網絡總負載方面優于深度遍歷路由配置算法。

圖9 隨網絡規模變化的鏈路平均期望負載

圖10 隨網絡規模增長的負載方差

4.3 算法時間復雜度比較

當SRIO網絡拓撲或者鏈路發生變化時需要重新計算并更新路由表,因此路由表的計算時間是影響算法選擇的重要因素。本文在Inter 7700KCPU環境下進行仿真,統計10 000個網絡交換節點規模為15的SRIO網絡路由表計算時間,結果如表3所示,負載均衡最小跳數路由算法的平均計算時間為0.04 ms,滿足SRIO網絡的實際工程需求。

表3 算法復雜度和路由表的計算時間

Table 3 Algorithm complexity and routing table computation time

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

5 結束語

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