新聞中心

EEPW首頁 > 設(shè)計應(yīng)用 > T-S-T三級交換網(wǎng)絡(luò)路徑搜索算法的研究

T-S-T三級交換網(wǎng)絡(luò)路徑搜索算法的研究

作者:陳臘梅,周正道 時間:2008-12-11 來源:現(xiàn)代電子技術(shù) 收藏

1 引 言

本文引用地址:http://m.butianyuan.cn/article/90169.htm

  技術(shù)的飛速發(fā)展使得目前高速通訊網(wǎng)絡(luò)性能的瓶頸集中在高速交換系統(tǒng),研究、設(shè)計和制造高速交換系統(tǒng)對目前高速通訊網(wǎng)絡(luò)具有極其重要的意義。而且隨著電信網(wǎng)和計算機網(wǎng)絡(luò)的高速發(fā)展,高速大容量的交叉連接或交換設(shè)備和芯片的性能也在大幅度的提高。同時由于現(xiàn)在的交換機在不停地更新?lián)Q代,對新的交換算法的需求也在不斷增加。

  本文的研究工作旨在利用矩陣置換的思想,模擬開發(fā)一種基于T(時分)-S(空分)-T(時分)交換網(wǎng)絡(luò)的調(diào)度算法。提出一種新的三級交換的矩陣模型,并在這種模型上設(shè)計相應(yīng)的無阻塞交換算法。利用矩陣作為數(shù)學模型,可以利用矩陣的置換操作搜索交換的設(shè)置。算法設(shè)計和實現(xiàn)的過程中,大量的實驗表明,本算法具有良好的特性,而且通過芯片級聯(lián)可實現(xiàn)。

  本算法不同于以往的基于圖論的尋徑調(diào)度算法,力圖通過對這個算法的研究,為未來的大型綜合數(shù)字交換網(wǎng)絡(luò)奠定理論和實踐基礎(chǔ),并為變化多端的網(wǎng)絡(luò)環(huán)境下快速建立有保障的網(wǎng)絡(luò)服務(wù)提供先期的技術(shù)研究。

2 數(shù)字交換網(wǎng)絡(luò)結(jié)構(gòu)

  典型的數(shù)字交換網(wǎng)絡(luò)可以用圖1的模型描述。

 

  整個交換網(wǎng)絡(luò)以S接線器為核心組織。對于一個具有N條輸入復用線和N條輸出復用線的交換網(wǎng)絡(luò)而言,需要配置2N套T接線器,其中N套在輸入側(cè),為初級T接線器,完成用戶的發(fā)送時隙到交換網(wǎng)絡(luò)內(nèi)部的公共時隙的交換;N套在輸出側(cè),稱為次級T接線器,完成將交換網(wǎng)絡(luò)內(nèi)部的公共時隙上的住處傳送到另一用戶的接收時隙上。因此,交換網(wǎng)絡(luò)內(nèi)部提供的公共時隙的數(shù)量就決定了交換網(wǎng)絡(luò)中能夠形成的話音通路的數(shù)量。中間的S接線器主要由一個N×N的交叉接點和具有N個存儲器的控制存儲器組來組成,用來完成將交換網(wǎng)絡(luò)內(nèi)部運載的用戶信息從一條輸入側(cè)復用線上交換到規(guī)定的一條輸出復用線上。

3 交換網(wǎng)絡(luò)數(shù)學模型的建立

3.1 問題的描述

  在建立T-S-T交換網(wǎng)絡(luò)的數(shù)學模型之前,首先給出這樣的數(shù)學抽象:用1個n×n的輸入矩陣inport表示輸入數(shù)據(jù)流,每一行代表1個T-S-T交換網(wǎng)絡(luò)的輸入鏈路,也就是說每一行代表l根鏈路HW,每一行內(nèi)元素的位置代表1個時隙內(nèi)各個數(shù)據(jù)幀的次序關(guān)系。由于T交換是對同一根鏈路的不同時隙之間進行的交換,故將其抽象為矩陣的行內(nèi)置換。因此當輸入矩陣inport經(jīng)過一級T交換后,得到1個中間矩陣after_t1,此矩陣是inport矩陣通過每一行數(shù)據(jù)的行內(nèi)變換得到。同理,由于S交換是在不同鏈路的相同時隙之間進行的交換,類似于對一個矩陣在其同一列內(nèi)進行列內(nèi)變換,稱其為列內(nèi)置換。這樣當after_tl又經(jīng)過S交換,得到另外一個中間矩陣after_s,此矩陣是after_tl矩陣通過列內(nèi)變換得到的。最后,又經(jīng)過第二級的T交換,產(chǎn)生outport矩陣,類似地,他是after_s矩陣通過行內(nèi)變換得到。于是,可以將交換算法這樣描述:對于初始矩陣inport,怎樣能找到一種滿足T-S-T三級交換的變換方式,最終得到1個輸出矩陣outport。而且對于用戶要求的任意outport(此矩陣與inport是單播關(guān)系),都可以通過算法找到其變換方式,即可以找到2個中間矩陣。

3.2 矩陣模型的建立

  將T變換對應(yīng)于矩陣的行內(nèi)變換,而S變換對應(yīng)于矩陣的列內(nèi)變換,這樣上面的這一段敘述就可以描述為inport矩陣經(jīng)過一系列的行內(nèi)變換得到after_t1矩陣,after_t1矩陣經(jīng)過一系列的列內(nèi)變換得到after_s矩陣,after_s矩陣又經(jīng)過一系列的行內(nèi)變換得到outport矩陣如圖2所示。

 

4 交換算法的設(shè)計思想

從上面論述可以看到,本文已經(jīng)將具體的路徑選擇問題,抽象成純粹的數(shù)學問題。接下來,本文將從純數(shù)學的角度來找出一種算法,從而解決這個交換問題。

4.1 問題的數(shù)學分析

  觀察從輸入矩陣inport→中間矩陣after_t1→中間矩陣after_s→輸出矩陣outport整個的變換過程,輸入矩陣先后經(jīng)過2次時間變換,而只經(jīng)過1次空間變換。也就是說,當輸入矩陣inport中的某個元素,要發(fā)生列變換時,他只有1次變換機會,此情況對于inport中的任意一個元素都是適用的。所以,時間變換只起到調(diào)整作用,因此本文要重點考察空間變換,試圖從空間變換S變換中找出矩陣的特點。

  不難發(fā)現(xiàn),中間矩陣after_s(n×m)(一般情況下,本文取m=n,無阻塞的交換網(wǎng)絡(luò))有這樣的特點:每一列的n個元素,他們的行號包含從1~n的所有行號。如上面的例子可以看到這一點。這樣,將after_s矩陣經(jīng)過1個空間變換,向空間變換的反方向變換的時候,這n個元素就會回到在inport矩陣原來的行上,在經(jīng)過1個時間變換的反變換就可以變成為輸入矩陣inport。

  在發(fā)現(xiàn)中間矩陣after_s的特點之后,就有了基本的思路。這里的算法只要能夠使得outport矩陣經(jīng)過1個時間變換的反變換后能夠變成為滿足中間矩陣after_s的特點的矩陣,那么,也就找到一種矩陣的變換方式。解決了這個交換問題。有沒有一個從inport到outport的變換的問題,轉(zhuǎn)換成能不能找到一個滿足after_s矩陣要求的問題,此after_s矩陣只是outport矩陣經(jīng)過一個時間變換得到。

  這樣,對于任意輸入矩陣inpott,經(jīng)過矩陣的行內(nèi)、列內(nèi)、行內(nèi)3次變換可以得到任意輸出矩陣outport,從而成功的完成了T-S-T交換。本文為了方便描述inport和T-S-T交換的核心算法,不妨將inport定義為順序矩陣n×n,就是以行為序,從0~n×n-1,例如n=4,inport被定義為:

 

  而outport將是inport的任意置換矩陣。在這里也不妨將outport假設(shè)為:

 

  為了從inport矩陣變換到outport矩陣,必須找到兩個中間矩陣after_t1和after_s,從而完成交換路徑的接續(xù)。因此本文的目標是研究一種算法,根據(jù)輸入矩陣和輸出矩陣產(chǎn)生這兩個中間矩陣,從而使處理機可以根據(jù)4個矩陣往寄存器陣列中填值,這樣就可以實現(xiàn)T-S-T網(wǎng)絡(luò)交換。為了以后敘述方便,3個寄存器陣列定義為:Tregister1(時分)、Sregister(空分)、Tregister2(時分)。

  由于在實際的T-S-T交換中,CPU根據(jù)各個控制寄存器中的值來完成交換。由交換的特點可知,每個控制寄存器的值是由輸入序列和輸出序列決定的。其中Tregisterl的值可以由inport和after_t1決定,同理,Sregister的值由after_t1和after_s決定,Tregister2的值由after_s和outport決定。

4.2 算法思想的設(shè)計

  算法設(shè)計要求:

  (1)對于任意給定的輸入矩陣和輸出矩陣,都能夠得到2個中間矩陣;

  (2)由輸入矩陣到第一個中間矩陣只能經(jīng)過一系列行內(nèi)置換;

  (3)由第一個中間矩陣到第二個中間矩陣只能經(jīng)過一系列列內(nèi)置換;

  (4)由第二個中間矩陣到輸出矩陣只能經(jīng)過一系列行內(nèi)置換。

  由行內(nèi)變換和列內(nèi)變換的性質(zhì)可以推斷出after_t1(AT)和after_s(AS)矩陣的特點如下:

  AT的特點:ATij=INij'(只能在同一行上進行置換);AS的特點:AS是inport的一個置換矩陣;AS的同一列上不可能出現(xiàn)inport同一行上的元素。

  這是由于AT同一列上不可能出現(xiàn)inport同一行上的元素,而AT到AS經(jīng)過的是列內(nèi)變換。

  現(xiàn)在有了inport和outport,目標是通過這2個矩陣找到after_t1和after_s。從上面的設(shè)計要求和模型2個中間矩陣的特點可以看出,由inport到outport所經(jīng)過的置換與由outport到inport所經(jīng)過的置換是對稱的,所以由outport到inpott置換所得的2個中間矩陣也是問題的解。而且inport相對于output較為確定,因此為了方便描述和算法實現(xiàn),本文采用逆推法,由outport經(jīng)過一系列的行內(nèi)變換逆推出after_s,由after_s經(jīng)過一系列的列內(nèi)變換逆推出after_t1。很容易發(fā)現(xiàn)從after_s到after_t1只需要一個簡單的排序就可以完成,因此算法的關(guān)鍵是由outport推導after_s。

  這樣本文研究的交換網(wǎng)絡(luò)調(diào)度算法要解決的關(guān)鍵問題等效后分解為:將一個任意置換矩陣經(jīng)過一系列的行內(nèi)變換變成為同一列上不存在輸入矩陣的同一行數(shù)據(jù)的置換矩陣(這是由AS的特點所決定的)。將解決這個關(guān)鍵問題的算法稱為交換網(wǎng)絡(luò)調(diào)度算法的核心算法。

5 關(guān)鍵矩陣算法的思想和步驟

5.1 高沖突值行優(yōu)先排列算法

  一些約定和定義:

  規(guī)則:矩陣after_s同一列上不存在矩陣inport同一行上的數(shù)據(jù)。

  那么對于任一給定輸出矩陣outport(OP),本算法的任務(wù)是;根據(jù)“規(guī)則”將outport的每一行元素放到after_s(AS)同行的適當位置上。例如假設(shè)現(xiàn)在開始第i行的排列,也就是說,第0行到第i~l行的數(shù)據(jù)已經(jīng)初步放置完畢(考慮到回溯,所以說“初步”),則前i行的每一列元素的初始矩陣行可以組成1個一維矩陣,一共n個一維矩陣,定義為垂直行陣v[0],v[1]。…,v[n一1];而OP的第i行的所有元素的初始矩陣行又可以組成1個一維矩陣(元素的初始矩陣行等于該元素整除矩陣維數(shù)的商),定義為水平行陣h,數(shù)據(jù)結(jié)構(gòu)如圖3所示:

 

  定義:垂直沖突值:vRepeat[n],其中vRepeat[i](i=0,1,2,…,n-1)等于u[i]中的元素在h中的重復次數(shù)的和。

  水平?jīng)_突值:hRepeat[n],其中hRepcat[i](i=0,1,…,n-1)等于k[i]在v中的重復次數(shù)的和。

  生存數(shù)(lifenum):假設(shè)vRepeat[j]等于k,也就是說,O[i]中有k個元素不能放在AS的第j列,能放在這一列的元素個數(shù)只有n-k個,定義為生存數(shù)(lifenum),將這n-k個元素下標取出形成向量,定義為生存空間(lifespace)

5.2 高沖突值行優(yōu)先排列算法的實現(xiàn)

  算法安放數(shù)據(jù)元素時,首先從vRepeat最大的那一列開始安放hRepeat最大的符合“規(guī)則”的元素,再逐次安放vRepeat中較小的且符合“規(guī)則”的列。這樣,大沖突值的元素得到優(yōu)先安放,重排或回溯的可能性就大大減小。

5.2.1 主流程

  (1)排列第1行數(shù)據(jù),row=0;

  (2)row=row+1,如果row≥n,則停止,否則轉(zhuǎn)下一步;

  (3)統(tǒng)計沖突值,調(diào)用判回溯算法判斷是否回溯,如果回溯,調(diào)用回溯算法,否則轉(zhuǎn)下一步;

  選擇vRepeat沖突值最大的列,根據(jù)“規(guī)則”安放hRepeat中最大的元素;

  (5)更新vRepeat和hRepeat;

  (6)判斷這一行的數(shù)據(jù)是否都安放完畢,如果是,轉(zhuǎn)(2),否則轉(zhuǎn)(3)。

5.2.2 判斷回溯算法

  回溯條件:生存數(shù)為k,生存空間相同的列的個數(shù)和大于生存數(shù)k,則回溯,原因是某生存空間“不夠分配”。例如,第i列和第j列(i不等于j)的生存數(shù)都為1和生存空間都為{2},這樣第2個元素只能放在一個位置上,也就是說,無論如何排列都無法滿足“規(guī)則”,需要回溯。

  定義節(jié)點數(shù)據(jù)結(jié)構(gòu)如圖4所示:

 

  判回溯的算法流程:

  (1)將生存數(shù)相同的所有節(jié)點串成鏈表,鏈表的序號等于生存數(shù);

  (2)從鏈表序號為0向鏈表序號為n順序掃描鏈表,統(tǒng)計生存空間相同的節(jié)點個數(shù),當出現(xiàn)節(jié)點個數(shù)大于生存數(shù)的情況,需要回溯,否則轉(zhuǎn)下一步;

  (3)將本鏈并入下一個鏈表;

  (4)如果所有鏈表都不出現(xiàn)生存空間相同的節(jié)點個數(shù)和大于生存數(shù)的情況,則不需要回溯。

5.2.3 回溯算法

  定義經(jīng)歷表:在回溯過程中,各元素所“呆過”的位置序列。

  回溯算法流程:

  (1)確定回溯元素(沖突值最大原則);

  (2)為回溯元素找一個“合法位置”;

  合法條件:

  規(guī)則:沖突值小于當前情況;位置不在經(jīng)歷表中。

  (3)為其他元素找“合法位置”;

6 算法的正確性證明和復雜度分析

  從前面的分析可以知道,要解決整個交換算法的關(guān)鍵是確定和尋找中間矩陣after_s,也就是說,在解決問題之前,必須確定問題有解。如何確定after_s一定存在,這里可以通過組合數(shù)學中的抽屜原理證明必然存在這樣的矩陣,證明過程比較簡單,本文在這里不做推導證明。

  從前面的理論分析中知道,衡量交換算法有2個重要的指標:交換次數(shù)和比較次數(shù)。為了統(tǒng)計本文所研究的交換算法的性能,本文針對不同階數(shù)矩陣的交換次數(shù)和比較次數(shù)做了系統(tǒng)的統(tǒng)計:

  (1)對于每一行數(shù)據(jù),由于統(tǒng)計沖突值、判回溯算法和元素的安放算法都是多項式復雜度,所以,在不存在回溯的條件下,本算法是多項式復雜度。

  (2)在本算法中,“沖突”起著非常重要的作用,本身回避了許多回溯可能。即使回溯,本行可供回溯元素和非回溯元素“待”的位置個數(shù)非常有限,所以元素回溯的空間很小。

  下面本文給出在不回溯的情況下,對高沖突行優(yōu)先排列算法在階數(shù)遞增變化時,50次平均交換次數(shù)和比較次數(shù)統(tǒng)計結(jié)果如表1所示。

 

  從前面對該算法的描述可知,該算法通過使每個元素“找到”盡可能適合自己的位置,從而回避了重新排列的許多可能,對于一行來說,完全避免了全排列,而且大大減小回溯概率。由于對大多數(shù)(約80%)矩陣來說,是不會出現(xiàn)回溯的,只有類似這樣的矩陣才有可能出現(xiàn)回溯(也可能不回溯),即,AS的某些行,可供選擇的初始行太少。所以,該算法是一個近似多項式的算法,在不回溯的情況下,是多項式算法。該算法基本上能夠完成交換網(wǎng)絡(luò)的路徑接續(xù),他有一個很大的優(yōu)勢就是在交換過程中交換的次數(shù)達到最小,這樣也就大大提高了尋找交換路徑的效率。本算法具有良好的特性,而且通過芯片級聯(lián)可實現(xiàn)。



關(guān)鍵詞: T-S-T 光纖通訊

評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉