一種基于Clos交換結(jié)構(gòu)的路由算法

楊 琦

(中國電子科技集團(tuán)公司第二十研究所，陜西 西安 710068)

?

一種基于Clos交換結(jié)構(gòu)的路由算法

楊 琦

(中國電子科技集團(tuán)公司第二十研究所，陜西 西安 710068)

隨著互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)的爆炸性增長，網(wǎng)絡(luò)中的關(guān)鍵節(jié)點——交換機(jī)的“電子瓶頸”問題成為限制網(wǎng)絡(luò)吞吐能力的重要原因。設(shè)計了一種適用于Clos交換結(jié)構(gòu)的平面間路由算法，按照業(yè)務(wù)傳輸路徑的特性和業(yè)務(wù)之間的位置關(guān)系，為業(yè)務(wù)快速選擇最合適的傳輸路徑。仿真表明，該算法在減少業(yè)務(wù)阻塞率、降低時延方面表現(xiàn)出色，有效改善了交換設(shè)備的路由性能。

Clos結(jié)構(gòu)；電子瓶頸；業(yè)務(wù)路徑

0 引 言

Clos網(wǎng)絡(luò)結(jié)構(gòu)于1953年由貝爾實驗室的Charles Clos提出[1]。它是由多個較小容量的交換單元構(gòu)建而成的大容量交叉矩陣，具有良好的可擴(kuò)展性[2-3]、靈活性、可靠性，可以適應(yīng)網(wǎng)絡(luò)規(guī)模的快速增長，滿足網(wǎng)絡(luò)傳輸業(yè)務(wù)的多樣化、綜合化，能夠適應(yīng)不同傳輸設(shè)備的要求。這些特性使得Clos網(wǎng)絡(luò)結(jié)構(gòu)成為目前熱門的多級交換結(jié)構(gòu)。

路由算法主要實現(xiàn)業(yè)務(wù)傳輸路徑的快速分配，提高業(yè)務(wù)吞吐率，在很大程度上決定了交換設(shè)備的性能。本文從Clos結(jié)構(gòu)和業(yè)務(wù)特性出發(fā)提出一種路由算法，在快速下發(fā)業(yè)務(wù)的同時也降低了時延和阻塞率。

1 問題建模

1.1 Clos交換結(jié)構(gòu)業(yè)務(wù)特性

以一個簡單的3級Clos結(jié)構(gòu)為例(如圖1所示)，第1級結(jié)構(gòu)是由r個n×m交換單元組成；第2級結(jié)構(gòu)由m個r×r交換單元組成；第3級結(jié)構(gòu)由r個m×n交換單元組成。每個中間級單元與每個輸入和輸出單元只有一條鏈路連接，而從輸入級任一端口到達(dá)輸出級任一端口可供選擇的鏈路有m條。3級Clos交換結(jié)構(gòu)的總端口數(shù)等于輸入模塊的端口個數(shù)n，乘以輸出模塊的個數(shù)r。輸入級模塊的輸出端口共有m個，因此每個輸入級模塊都有m條鏈路可供選擇。

在工程應(yīng)用中，當(dāng)業(yè)務(wù)從輸入端口到來后，交換設(shè)備需要通過路由算法得到每條業(yè)務(wù)的下發(fā)路徑，也就是業(yè)務(wù)要被分配到的中間級模塊。

為實現(xiàn)輸入端的業(yè)務(wù)分發(fā)到每個平面，采用提前一次統(tǒng)計出到達(dá)每個輸入端口業(yè)務(wù)之后，進(jìn)行分平面路徑設(shè)置。因為輸入/輸出對的業(yè)務(wù)個數(shù)是隨機(jī)數(shù)，所以用1個業(yè)務(wù)矩陣統(tǒng)計輸入/輸出對的業(yè)務(wù)個數(shù)。為了描述交換結(jié)構(gòu)的業(yè)務(wù)特性，這里采用業(yè)務(wù)矩陣的方式，業(yè)務(wù)矩陣的行代表輸入端口，列代表輸出端口，業(yè)務(wù)矩陣的具體取值代表了從某行(輸入端口)到某列(輸出端口)的業(yè)務(wù)數(shù)量,圖2是一個N×N規(guī)模的業(yè)務(wù)矩陣。

矩陣中第0行第2列的“7”代表從0號輸入端口到2號輸出端口有7條業(yè)務(wù)需要下發(fā)。對基于Clos交換結(jié)構(gòu)的設(shè)備，業(yè)務(wù)路由要解決的就是將業(yè)務(wù)下發(fā)到合適的中間級，雖然每個中間級模塊理論上都可以承載業(yè)務(wù)到對應(yīng)的輸出端口，但每個中間級模塊的業(yè)務(wù)容量上限固定。當(dāng)大量業(yè)務(wù)都需要轉(zhuǎn)發(fā)的時候，就要盡可能讓每條業(yè)務(wù)選擇合適的中間級模塊將所有業(yè)務(wù)最大化下發(fā)出去。

傳統(tǒng)路由算法根據(jù)業(yè)務(wù)矩陣的規(guī)模，逐行逐列進(jìn)行業(yè)務(wù)查找，在業(yè)務(wù)矩陣中找到業(yè)務(wù)后，只需判斷下發(fā)到的業(yè)務(wù)平面中該位置的行、列已有業(yè)務(wù)是否達(dá)到上限。若達(dá)到上限，尋找下一個業(yè)務(wù)平面；若還未達(dá)到上限，則插入業(yè)務(wù)，完成操作。如圖3所示。

但這種方法輪詢的時候只考慮當(dāng)前位置業(yè)務(wù)能否下發(fā)，沒有考慮對之后該位置同一行、同一列位置處的業(yè)務(wù)下發(fā)是否造成影響。

1.2 加速路由算法

在傳統(tǒng)路由算法基礎(chǔ)上，提出一種加速路由算法，圖4是該算法的業(yè)務(wù)矩陣輪詢示意圖。

步驟2：從i=SR，j=SL開始輪詢。判斷業(yè)務(wù)矩陣是否還有業(yè)務(wù)未分配；是否存在還未分配業(yè)務(wù)的平面。

(1) 若m為0，則不存在未分配業(yè)務(wù)的平面，則提取所有連接矩陣作為平面的路由設(shè)置依據(jù)，程序結(jié)束。

(2) 若存在未分配業(yè)務(wù)的平面，但是業(yè)務(wù)矩陣Hm[i,j]中元素全為零，則提取已分配的連接矩陣作為平面的路由設(shè)置依據(jù)，程序結(jié)束。

(2) 若選取的列上元素為零或者該列計數(shù)器值已超過了上限值，則重復(fù)步驟3輪詢行i的下一列j=(j+1)mod(N)。

(2) 選取的列上元素為零或者該列計數(shù)器值已超過了上限值，則重復(fù)步驟4，輪詢行i的下一列j1=(j1-1)mod(N)。

步驟5：判斷輪詢的行i是否等于起始行SR，若等于起始行，則m=m-1，SR=(i+1)mod(N)、SL=(j+1)mod(N)，SL1=(j1-1)mod(N),并回到步驟2；若不等于起始行，則回到步驟3，輪詢下一行i，列j=(j+1)mod(N)。

1.3 仿真驗證

下面通過VS2010軟件，對設(shè)計算法的業(yè)務(wù)處理時延、阻塞率進(jìn)行驗證。假設(shè)業(yè)務(wù)矩陣的規(guī)模是512×512，每個輸入輸出端口到達(dá)的業(yè)務(wù)數(shù)最多3 000個，業(yè)務(wù)平面有100個。每個平面來自每個端口的業(yè)務(wù)數(shù)上限值為30個。

圖5是業(yè)務(wù)負(fù)載率從10%～100%多種情形下，2種算法在處理時延方面的對比圖。

從圖中可看出，當(dāng)業(yè)務(wù)負(fù)載量小于60%，加速路由算法的處理時延優(yōu)化效果不明顯，主要是因為業(yè)務(wù)矩陣中的業(yè)務(wù)較稀疏。加速路由算法在輪詢過程中花費在查找的時間不能減少，只是在雙向找到有效業(yè)務(wù)的情況下，處理時間能減少，所以不能夠達(dá)到業(yè)務(wù)處理時延減半的效果。

隨著業(yè)務(wù)負(fù)載量的增加，加速路由算法在處理大量業(yè)務(wù)時顯示出較好的效果，同時時延曲線的變化不會隨著業(yè)務(wù)負(fù)載量的增大有明顯的變化。主要是因為這種算法在查找業(yè)務(wù)時避免輸出模塊端口計數(shù)器過早達(dá)到上限，計算業(yè)務(wù)的時候也加快處理速度。而傳統(tǒng)路由算法由于查找業(yè)務(wù)的方法較單一，在下發(fā)前面端口業(yè)務(wù)的同時沒有考慮到對后面端口業(yè)務(wù)的影響，導(dǎo)致在查找上所花的時間較多，時延隨業(yè)務(wù)負(fù)載量的增加曲線變化很明顯。

圖6是業(yè)務(wù)負(fù)載率從85%～100%多種情形下，2種算法在阻塞率方面的對比圖。

在仿真過程中發(fā)現(xiàn)，當(dāng)業(yè)務(wù)負(fù)載率小于80%，下發(fā)業(yè)務(wù)所需的平面?zhèn)€數(shù)維持在91～97之間，不存在阻塞率。因此我們截取業(yè)務(wù)負(fù)載率85%～100%

這些情形進(jìn)行阻塞率對比。

當(dāng)業(yè)務(wù)負(fù)載率超過85%，加速路由算法逐漸顯示出較好的的阻塞率表現(xiàn)，尤其是當(dāng)業(yè)務(wù)負(fù)載率超過92%以后，2種算法的阻塞率差距逐漸拉大，主要是因為加速路由算法在前期查找合適位置的時候盡量避免計數(shù)器過早達(dá)到上限，不給后面平面下發(fā)業(yè)務(wù)造成限制,如圖7所示。

按照傳統(tǒng)路由算法，每行輪詢的時候都選擇第2列的業(yè)務(wù)，到第i-1行，該列計數(shù)器達(dá)到上限，到第i行，該位置的業(yè)務(wù)也不能夠再下發(fā)出去，造成業(yè)務(wù)阻塞。

2 結(jié)束語

本文針對Clos交換結(jié)構(gòu)的特性，設(shè)計了一種適用于大量業(yè)務(wù)的快速路由算法，通過計算機(jī)軟件驗證了算法在降低時延、阻塞率方面表現(xiàn)出的良好性能。下一步將考慮在提高業(yè)務(wù)處理速度等方面改善算法的性能。

[1] 陳浩.Clos網(wǎng)絡(luò)的綠色交換[D].西安：西安電子科技大學(xué)，2014.

[2] 熊慶旭，馮金鑫.基于矩陣分解的光交換機(jī)分組調(diào)度算法[J].通信學(xué)報，2006,27(4)：80-86.

[3] 李揮，王秉睿，黃佳慶.負(fù)載均衡自路由交換結(jié)構(gòu)[J].通信學(xué)報，2009,30(5)：7-15

A Routing Algorithm Based on Clos Switching Structure

YANG Qi

(The 20 Institute of China Electronic Technology Group Corporation,Xi'an 710068，China)

With the explosive growth of Internet business data,"electronic bottleneck" problem of switcher——the key node of network becomes the significant cause limiting network throughput.This paper designs a routing algorithm among planes for Clos switching structure,which rapidly chooses the most suitable transmission path for the business according to the characteristics of the transmission path and the location relationship between services.The simulation results show that:the proposed algorithm performs well in reducing the traffic blocking rate and reducing the time delay,so effectively improves the routing performance of switching devices.

Clos structure;electronic bottleneck;transmission path

2017-02-26

TP393.04

A

CN32-1413(2017)02-0089-03

10.16426/j.cnki.jcdzdk.2017.02.021