鄒小花，夏 容

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

1 引言

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

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

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

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

2.1 高性能網(wǎng)絡(luò)多級(jí)交換結(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è)立緩存，緩存裝置能夠有效解決多級(jí)交換網(wǎng)絡(luò)存在問(wèn)題，使其具有高吞吐量、負(fù)載均衡，有效縮短調(diào)度計(jì)算時(shí)間。

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

(2)

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

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

(3)

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

(4)

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

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

(5)

ui=R′，i≥0

(6)

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

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

(7)

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

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

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

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

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

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

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

(8)

(9)

(10)

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

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

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

(11)

公式中第一項(xiàng)代表同一條輸出線路只能接收一個(gè)信元。(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。在每一個(gè)時(shí)間隙中，該矩陣由每個(gè)序列的第一個(gè)信元的目的地址所組成。如果選擇的信元沒(méi)有擁堵時(shí)，該項(xiàng)目最小。第二項(xiàng)則代表優(yōu)先級(jí)，如果選擇的高優(yōu)先級(jí)的信元最多，該項(xiàng)也是最小。該函數(shù)依據(jù)序列長(zhǎng)度決定優(yōu)先級(jí)，而在比較長(zhǎng)序列里信元富有極高優(yōu)先級(jí)

(12)

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

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

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

(13)

其中Uij代表神經(jīng)元的輸入，Vij代表神經(jīng)元輸出，A，B，C，g均為正整數(shù)。因此HNN經(jīng)?？梢允諗康紼的最小點(diǎn)，該神經(jīng)元能夠直接表示一個(gè)時(shí)間隙內(nèi)輸送的最優(yōu)無(wú)擁堵信元集合。

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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