高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)實(shí)時調(diào)度方法仿真

鄒小花，夏 容

(南昌航空大學(xué)科技學(xué)院，江西 南昌 332020)

1 引言

高性能網(wǎng)絡(luò)業(yè)務(wù)數(shù)量的不斷增加，帶動當(dāng)代交換技術(shù)突飛猛進(jìn)的發(fā)展。而多級交換技術(shù)為了滿足人們的需要，朝著更高性能、高擴(kuò)展性與高經(jīng)濟(jì)水平目標(biāo)改進(jìn)。單級交換結(jié)構(gòu)由于環(huán)境影響、使用局限性的問題，其結(jié)構(gòu)擴(kuò)展性受到極大限制。為此各國學(xué)者、科研人員開始嘗試使用若干個小型單級交換結(jié)構(gòu)組成大型的多級交換網(wǎng)絡(luò)，并利用網(wǎng)絡(luò)多級交換技術(shù)優(yōu)點(diǎn)，設(shè)計(jì)具有高性能與多端口的交換結(jié)構(gòu)，為今后網(wǎng)絡(luò)交換技術(shù)實(shí)時調(diào)度研究奠定基礎(chǔ)。

殷曉超、韓國棟等人[1]使用交換網(wǎng)絡(luò)多并行總線結(jié)構(gòu)，同時完成多個信息流輸入與輸出的匹配，但由于調(diào)度方法繁瑣和端口數(shù)量諸多，其結(jié)構(gòu)擴(kuò)展能力低，為此提出一種全新交換結(jié)構(gòu)。該方法先使用模XY方式形成路由最小路徑和網(wǎng)絡(luò)信息流的平衡，再利用輸出排隊(duì)方法對路由各節(jié)點(diǎn)端口地方進(jìn)行實(shí)時調(diào)度，最后根據(jù)信息控制方式對信息流包進(jìn)行輸送。該方法結(jié)構(gòu)富有較高的擴(kuò)展性，但是網(wǎng)絡(luò)吞吐量較少；申志軍、烏日更等人[2]針對交換結(jié)構(gòu)中的信元矛盾、信元次序混亂、交換程序繁瑣等問題，使用逆向傳輸機(jī)制對交換結(jié)果進(jìn)行實(shí)時調(diào)度。首先使用crossbar逆向傳輸設(shè)備，很容易獲得任意輸入端口與其鄰近端口的調(diào)度情況，同時對該端口反饋數(shù)據(jù)做改正處理，其次根據(jù)改正數(shù)據(jù)做調(diào)度計(jì)算，得到的結(jié)果可以有效解決信元矛盾與信元次序混亂，也不用在端口重新設(shè)立排序緩存。該方法可以對交換結(jié)構(gòu)與調(diào)度過程中得到更高的時延能力，但沒有保證網(wǎng)絡(luò)負(fù)載均衡；臧韋菲、蘭巨龍等人[3]發(fā)現(xiàn)多路徑路由方式會導(dǎo)致信息中心網(wǎng)絡(luò)負(fù)載不均衡與吞吐量減少，對此引入交換技術(shù)對多路徑路由進(jìn)行實(shí)時調(diào)度并改進(jìn)。先使用SDN方法得到全部網(wǎng)絡(luò)視圖情況，再通過輪詢與動態(tài)流調(diào)度方式進(jìn)行網(wǎng)絡(luò)負(fù)載均衡，提升網(wǎng)絡(luò)吞吐量。為了降低控制器和設(shè)備間交換所帶來其它負(fù)載，根據(jù)交換結(jié)構(gòu)特征重新對信息流進(jìn)行實(shí)時調(diào)度，最后使用分段路由方式對實(shí)時調(diào)度結(jié)果改進(jìn)，得到嶄新的路由，并進(jìn)一步提升信息流量輸送效率。該方法可以提升信息中心網(wǎng)絡(luò)吞吐量，減少信息流完成時間，同時具有良好的負(fù)載均衡能力，但是其交換結(jié)構(gòu)簡單，擴(kuò)展能力較低。

針對上述問題，本文提出高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)實(shí)時調(diào)度方法研究。通過信元交換方式組建多級交換結(jié)構(gòu)基本元素，完成高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)設(shè)計(jì)，實(shí)現(xiàn)了高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)實(shí)時調(diào)度，最后根據(jù)仿真結(jié)果驗(yàn)證了本文方法的有效性。

2 多級交換結(jié)構(gòu)實(shí)時調(diào)度方法實(shí)現(xiàn)

2.1 高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)設(shè)計(jì)

由于高性能網(wǎng)絡(luò)內(nèi)部鏈路擁擠，理想的交換結(jié)構(gòu)需使用繁瑣的集中式調(diào)度方式[4]，但在現(xiàn)實(shí)交換設(shè)備中不容易實(shí)現(xiàn)。為此引入一種想法：在交換網(wǎng)絡(luò)中設(shè)立緩存，緩存裝置能夠有效解決多級交換網(wǎng)絡(luò)存在問題，使其具有高吞吐量、負(fù)載均衡，有效縮短調(diào)度計(jì)算時間。

2.1.1 多級交換結(jié)構(gòu)基本元素組建

高性能網(wǎng)絡(luò)多級交換系統(tǒng)是由初始輸入級、中間級、輸出級三部分組成，其中，初始輸入級與輸出級使用都沒有緩存空間交換結(jié)構(gòu)，都是由r個沒有緩存交換元素構(gòu)成，n×m與m×n分別表示交換元素端口大小；而中間級則是由m個帶有緩存輸入端口r×r大小的交換元素構(gòu)成，隨意一個IS的入端口與CS的輸入端口間僅僅只有一個緩存鏈路連接，而全部網(wǎng)絡(luò)多級交換結(jié)構(gòu)組成一個為N×N模式的交換系統(tǒng)，即N=n×r。每一條鏈路上緩存都是由一個分路設(shè)備與合路設(shè)備管理，各自完成鏈路上不相同目的端口信元的分路與合路作用。

為此，設(shè)定多級交換網(wǎng)絡(luò)依然使用信元交換方法，在線路端口處完成信息包的分割和重組。鏈路輸送與收到一個信元所經(jīng)歷的時間叫作一個時間隙[5]。交換結(jié)構(gòu)的實(shí)時調(diào)度需在一個時間隙中完成，至此完成高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)基本元素的組建。

2.1.2 多級交換結(jié)構(gòu)性能特征測算

為了更直觀描述多級交換結(jié)構(gòu)的特征，先給出一個簡單例子：設(shè)定有一個信息流多級交換結(jié)構(gòu)的初始傳入端口為1號，輸出端口為OS如圖1所示。

圖1 多級交換信元實(shí)時調(diào)度過程

從圖1中可以看到該結(jié)構(gòu)中刪除了與信息流無關(guān)的交換元素與內(nèi)部鏈路。

多級交換結(jié)構(gòu)中信元實(shí)時調(diào)度流程[6]被認(rèn)為是信息流經(jīng)初始級負(fù)載均衡到中間級，然后調(diào)度出整個多級交換結(jié)構(gòu)的流程。即在初始輸入級，調(diào)度設(shè)備依據(jù)中間級緩存與鏈路的情況，把此信息流的信元均衡匹配到和其相鄰全部中間級交換元素中，隨后信元通過中間級元素與輸出級實(shí)時調(diào)度出路由多級交換網(wǎng)絡(luò)。同時把該部分信息流均衡到中間級鏈路流程里，其中有m個途徑選擇，該均衡特征可以由下面說明。

1)多級交換結(jié)構(gòu)的擴(kuò)展比

設(shè)定R表示多級交換結(jié)構(gòu)能支撐最大端口鏈路速度，R′表示中間級模擬序列能支撐信元最大離開速度，則多級交換結(jié)構(gòu)的擴(kuò)展比用式(1)表示

(1)

多級交換結(jié)構(gòu)的擴(kuò)展比能夠展現(xiàn)出其結(jié)構(gòu)的規(guī)模[7]、內(nèi)部途徑數(shù)量、中間級鏈路使用情況、擴(kuò)展能力等。在研究多級交換網(wǎng)絡(luò)內(nèi)部矛盾時，S越大，該內(nèi)部矛盾發(fā)生情況就越小，在研究多級交換結(jié)構(gòu)中間級鏈路使用價值時，并不是S值越大，使用價值越高。為此，要想得到多級交換結(jié)構(gòu)較高性能與較小實(shí)現(xiàn)價值，就必須全方面考慮S的取值。

當(dāng)S>n時，多級交換結(jié)構(gòu)是穩(wěn)定的。

根據(jù)上面研究得到，想要知道多級交換結(jié)構(gòu)是否穩(wěn)定，僅需觀察一個信息流經(jīng)過交換網(wǎng)絡(luò)內(nèi)部緩存過程中，所組成序列系統(tǒng)的穩(wěn)定情況，假設(shè)此序列系統(tǒng)是穩(wěn)定的，則該交換網(wǎng)絡(luò)內(nèi)部緩存是穩(wěn)定的，多級交換網(wǎng)絡(luò)結(jié)構(gòu)是非常穩(wěn)定的；反之，則不穩(wěn)定。

不改變原有基礎(chǔ)上，依舊僅研究初始端口1號輸入地方，而目的端口為送出端口的信息流，詳情如圖1所示。設(shè)定P表示此信息流經(jīng)過交換網(wǎng)絡(luò)內(nèi)部緩存過程中組成的序列系統(tǒng)。

針對該序列系統(tǒng)P，則假設(shè)λ表示信元送達(dá)流程中服從參數(shù)，得到λ≤R。同時為了滿足該過程中流量均衡情況，設(shè)定λx(1≤x≤m，0≤λx≤λ)表示隨意第x個中間級鏈路中VQ信元送達(dá)流程中服從參數(shù)，獲得隨意信元送達(dá)流程中服從參數(shù)與假設(shè)服從參數(shù)之間的關(guān)系式(2)

(2)

由于各中間級VQ位置是一樣的，則設(shè)定初始級交換元素可以得到正確負(fù)載均衡，如式(3)所示

λx=λy，x≠y，1≤x，y≤m

(3)

式中，λy(1≤y≤m，0≤λy≤λ)表示隨意第y個中間級鏈路中VQ信元送達(dá)流程中服從參數(shù)。根據(jù)式(2)與式(3)可知

(4)

關(guān)于中間級中每個VQ，其代表整個調(diào)度中信元提供服務(wù)流程。

而各VQ可以由n個初始端口的信息流共享，各信元進(jìn)入與送達(dá)流程可以認(rèn)為(n×λ)/m是輸入服從參數(shù)的流程，M/M/1是服務(wù)時間服從參數(shù)為R′的序列系統(tǒng)。基于此設(shè)定VQ組成該序列系統(tǒng)為系統(tǒng)Q，為此序列系統(tǒng)m可以由P個序列系統(tǒng)Q組成。該系統(tǒng)出生率與死亡率分別表示為式(5)與式(6)

(5)

ui=R′，i≥0

(6)

式中i表示序列系統(tǒng)Q中用戶數(shù)量。

下面驗(yàn)證序列系統(tǒng)Q穩(wěn)定性。采用平穩(wěn)分布方式對M/M/1系統(tǒng)穩(wěn)定性進(jìn)行描述。并根據(jù)出生與死亡流程有關(guān)知識可知出生率與死亡率的比例和

(7)

2)多級交換結(jié)構(gòu)吞吐量能力分析

穩(wěn)定性是多級交換結(jié)構(gòu)取得高性能最關(guān)鍵條件，根據(jù)多級交換結(jié)構(gòu)內(nèi)部加入緩存，能夠有效解決多級交換網(wǎng)絡(luò)內(nèi)部競爭所導(dǎo)致網(wǎng)絡(luò)擁堵，該性能的升高直觀表現(xiàn)在多級交換結(jié)構(gòu)的吞吐量情況，以下推論過程反映出多級交換結(jié)構(gòu)真實(shí)吞吐量性能情況。

當(dāng)S>n時，多級交換結(jié)構(gòu)可以達(dá)到100%吞吐量。根據(jù)該結(jié)構(gòu)穩(wěn)定性高，當(dāng)S>n時，多級交換結(jié)構(gòu)是非常穩(wěn)定的，而中間級隨意緩存情況都是穩(wěn)定的，為此可以有效保存由競爭導(dǎo)致?lián)矶碌男旁员ＷC信元不被丟棄[8]，根據(jù)吞吐量定義得到，此刻多級交換結(jié)構(gòu)可以取得100%的吞吐量。

2.2 多級交換結(jié)構(gòu)的實(shí)時調(diào)度

為了在每個時間隙傳送更多信元，則采用HNN方式對其進(jìn)行調(diào)度原則規(guī)定：①相同輸出路線只可能收到一個信元；②相同輸入線路中如果出現(xiàn)一樣的地址的信元要依次按照先后順序進(jìn)行實(shí)時調(diào)度；③在提取出信元集合中，使用高優(yōu)先級方法得出信元數(shù)最大化；④如果選擇機(jī)會多時，盡可能降低輸入同一傳送線的信元多于一個的機(jī)會。

根據(jù)多級交換結(jié)構(gòu)性能擴(kuò)展到中間級緩存區(qū)，因此調(diào)度原則②做擴(kuò)展時就符合要求了；調(diào)度原則③使用長隊(duì)列高優(yōu)先級方式，如果序列長度大于序列平均長度時，此序列的信元就被認(rèn)為高優(yōu)先級，在相同條件下，該系統(tǒng)應(yīng)首先輸送高優(yōu)先級的信元；調(diào)度原則④，在相同時間隙上同一輸入線路上可以多輸送一個信元，如果條件選擇多時，盡量避免這種事情發(fā)生。調(diào)度原則③與④的加入能夠有效提升中間級緩存使用率，加強(qiáng)多級交換結(jié)構(gòu)性能，縮短計(jì)算時間，降低平均時延。

使用HNN方法中的動態(tài)方程與能力方程分別為

(8)

(9)

(10)

式中τ表示電路時間常數(shù)，g表示增加系數(shù)。

采用的HNN是由N×S個神經(jīng)元構(gòu)成，N表示多級交換結(jié)構(gòu)的輸入線數(shù)，S表示輸入序列數(shù)，(i，j)代表第i條輸入線號，第j個輸入序列的神經(jīng)元。各神經(jīng)元代表各序列的第一個信元。為了符合同一輸入線路是同一個輸出地址的信元，就需要按照先后次序輸出，即原則(2)。

能量公式依據(jù)調(diào)度原則得到式(11)

(11)

公式中第一項(xiàng)代表同一條輸出線路只能接收一個信元。(N×S)×(N×S)代表銜接矩陣H規(guī)模大小，Hij，pq代表神經(jīng)元(i，j)與(p，q)之間連接權(quán)重。假設(shè)信元ij與信元pq有一樣的目的地址，則Hij，pq=1，否則Hij，pq=0。在每一個時間隙中，該矩陣由每個序列的第一個信元的目的地址所組成。如果選擇的信元沒有擁堵時，該項(xiàng)目最小。第二項(xiàng)則代表優(yōu)先級，如果選擇的高優(yōu)先級的信元最多，該項(xiàng)也是最小。該函數(shù)依據(jù)序列長度決定優(yōu)先級，而在比較長序列里信元富有極高優(yōu)先級

(12)

第三項(xiàng)使得神經(jīng)元結(jié)束得出收斂數(shù)為1或者0。第四項(xiàng)代表盡可能降低同一輸入線路的信元多余1個事情發(fā)生。當(dāng)中T=1/5×it2，it代表第it次檢測。增加這一項(xiàng)是為了驗(yàn)證前幾次檢測結(jié)果，盡可能調(diào)整同一輸入線路的信元，降低在該符合條件時多級交換結(jié)構(gòu)將一條輸入線路輸送若干個信元情況。隨著檢測次數(shù)越多，此項(xiàng)結(jié)果越接近0。

能量函數(shù)的最后三項(xiàng)能夠有效提升中間級緩存設(shè)備的使用價值、減少信元時延、降低信元缺失、提升吞吐量、提高HNN收斂。

根據(jù)式(8)到式(12)可以知道HNN的被動公式為

(13)

其中Uij代表神經(jīng)元的輸入，Vij代表神經(jīng)元輸出，A，B，C，g均為正整數(shù)。因此HNN經(jīng)常可以收斂到E的最小點(diǎn)，該神經(jīng)元能夠直接表示一個時間隙內(nèi)輸送的最優(yōu)無擁堵信元集合。

綜上所述，完成了高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)實(shí)時調(diào)度方法。

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

為了驗(yàn)證高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)實(shí)時調(diào)度方法的有效性，進(jìn)行了一次仿真。

從某企業(yè)的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)庫中隨機(jī)抽取2000個信元，以多級交換結(jié)構(gòu)的擴(kuò)展比S為指標(biāo)，采用文獻(xiàn)[2]方法和文獻(xiàn)[3]方法做本文方法的對比方法，進(jìn)行對比實(shí)驗(yàn)驗(yàn)證，得到多級交換結(jié)構(gòu)的擴(kuò)展比S的測試結(jié)果如表1所示。

表1 三種不同方法的擴(kuò)展比對比結(jié)果

分析表1結(jié)果得出，文獻(xiàn)[2]方法所設(shè)計(jì)的多級交換結(jié)構(gòu)，其平均擴(kuò)展比為1，文獻(xiàn)[3]方法所設(shè)計(jì)的多級交換結(jié)構(gòu)，其平均擴(kuò)展比為1，本文方法設(shè)計(jì)的多級交換結(jié)構(gòu)，其平均擴(kuò)展比為4。根據(jù)方法步驟可知，擴(kuò)展比S值越大，結(jié)構(gòu)越穩(wěn)定，因此對比實(shí)驗(yàn)結(jié)果得出，本文方法的擴(kuò)展比最大，說明本文方法構(gòu)建的多級交換結(jié)構(gòu)最穩(wěn)定。

吞吐量是判定實(shí)時調(diào)度效果的最直觀指標(biāo)，因此分別采用文獻(xiàn)[2]方法、文獻(xiàn)[3]方法和本文方法進(jìn)行多級交換結(jié)構(gòu)的實(shí)時調(diào)度。得到對比結(jié)果如圖2所示：

圖2 三種不同方法吞吐量對比結(jié)果

分析圖2可知，采用文獻(xiàn)[2]方法進(jìn)行多級交換結(jié)構(gòu)的實(shí)時調(diào)度，其吞吐量曲線隨著信元數(shù)量的增加呈下降趨勢，平均吞吐量約為55%；采用文獻(xiàn)[3]方法進(jìn)行多級交換結(jié)構(gòu)的實(shí)時調(diào)度，其吞吐量曲線隨著信元數(shù)量的增加呈上升趨勢，平均吞吐量約為60%；采用本文方法進(jìn)行多級交換結(jié)構(gòu)的實(shí)時調(diào)度，其吞吐量曲線隨著信元數(shù)量的增加先呈上升趨勢，在信元數(shù)量達(dá)到600個時，保持穩(wěn)定，平均吞吐量約為70%，穩(wěn)定在80%。對比三種方法的實(shí)驗(yàn)結(jié)果得出，本文方法的吞吐量遠(yuǎn)高于兩種傳統(tǒng)方法的吞吐量，因此說明本文方法的實(shí)時調(diào)度效果最好。

負(fù)載均衡效果是評判實(shí)時調(diào)度效果是否理想的另一重要指標(biāo)，分別測試文獻(xiàn)[2]方法、文獻(xiàn)[3]方法和本文方法三種方法的負(fù)載頻率幅值對比結(jié)果如圖3所示。

圖3 三種不同方法的負(fù)載頻率幅值對比結(jié)果

根據(jù)圖3的實(shí)驗(yàn)結(jié)果可以知道，文獻(xiàn)[2]方法的負(fù)載頻率幅值波動較大，但幅值變化較為規(guī)律，文獻(xiàn)[3]方法的負(fù)載頻率幅值不僅波動較大，且幅值變化也不規(guī)律，本文方法的負(fù)載頻率幅值波動較小，且幅值變化規(guī)律穩(wěn)定。充分說明，本文方法的負(fù)載均衡性較好，實(shí)時調(diào)度效果最為理想。

4 結(jié)論

多級交換結(jié)構(gòu)是實(shí)現(xiàn)網(wǎng)絡(luò)路由交換器的關(guān)鍵部分，為此本文提出一種高性能網(wǎng)絡(luò)多級交換結(jié)構(gòu)實(shí)時調(diào)度方法。

1)首先構(gòu)建網(wǎng)絡(luò)多級交換系統(tǒng)，然后分析該系統(tǒng)結(jié)構(gòu)功能，最后得到其具有較高穩(wěn)定性與較高吞吐量。

2)實(shí)驗(yàn)結(jié)果表明，該方法簡單操作，保證信元不被丟失，吞吐量接近100%，平均擴(kuò)展比為4，負(fù)載均衡效果較高，為此該方法是解決網(wǎng)絡(luò)實(shí)時調(diào)度的極佳方法。

3)本文所提方法可以為下一步網(wǎng)絡(luò)數(shù)據(jù)安全的研究提供參考意見，為計(jì)算機(jī)項(xiàng)目的開發(fā)奠定了實(shí)用性的基礎(chǔ)。