[發(fā)明專利]一種基于資源不可用約束的連接請求路由和重排方法

有效

• 申請?zhí)枺?/td>: 201210344839.8
• 申請日: 2012-09-18
• 公開（公告）號: CN102882807A
• 公開（公告）日: 2013-01-16
• 發(fā)明（設計）人: 陳錫蓮;許渤;邱昆
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L12/861
• 分類號: H04L12/861;H04L12/733;H04Q11/00
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平

1.一種基于資源不可用約束的連接請求路由和重排方法，其特征在于，包括以下步驟：

（1）、對于需要新建的連接請求r（I_m，O_m，s），在時隙矩陣的時隙s中，找出中間級模塊集合W(r)；其中，中間級模塊集合W(r)中的中間級模塊w滿足到連接請求r的輸入模塊I_m對應鏈路上的時隙s空閑，同時到連接請求r的輸出模塊O_m對應鏈路上的時隙s空閑；

如果中間級模塊W(r)不為空，進入步驟（2），如果中間級模塊W(r)為空，進入步驟（4）；

（2）、能否找到不發(fā)生資源不可用事件的中間級模塊w，能找到，則進入步驟（3），如果找不到，則選擇負載最輕的中間級模塊w，進入步驟（7）；

（3）、占用模塊w到連接請求r的輸入模塊I_m的對應時隙鏈路，到連接請求r的輸出模塊O_m的對應時隙鏈路，更新時隙矩陣，結束；

（4）、找出中間級模塊集合A(r)，找出中間級模塊B(r)；其中，中間級模塊集合A(r)中的中間級模塊a滿足到連接請求r的輸入模塊對應鏈路上的時隙s被占用，到連接請求r的輸出模塊對應鏈路上的時隙s有空閑，中間級模塊B(r)中的中間級模塊b滿足到連接請求r的輸入模塊I_m對應鏈路上的時隙s有空閑，到連接請求r的輸出模塊O_m對應鏈路上的時隙s被占用；

如果中間級集合A(r)或者B(r)為空，則進入步驟（5）否則進入步驟（6）；

（5）、不滿足重排要求，結束；

（6）、根據(jù)負載策略，在中間級模塊集合A(r)中選擇模塊a,在中間級模塊集合B(r)中選擇模塊b，進入PAULL重排；

（7）、在剩下的不滿足W(r)要求的中間模塊集合V(r)中尋找一個負載最輕的中間級模塊v，在中間級模塊w和中間級模塊v中進行聯(lián)合PAULL重排：

7.1）、如果中間級模塊v在時隙矩陣中輸入模塊I_m所對應的行出現(xiàn)，在輸出模塊O_m所對應的列沒有出現(xiàn)，則進入步驟7.2）；如果中間級模塊v在時隙矩陣中輸入模塊I_m所對應的行沒有出現(xiàn)，在輸出模塊O_m所對應的列出現(xiàn)，則進入步驟7.3）；如果中間級模塊v在時隙矩陣中輸入模塊I_m所對應的行、在輸出模塊O_m所對應的列均出現(xiàn)，則進入步驟7.4）；

7.2）、令i_v=I_m，在時隙矩陣i_v行時隙s中找到中間級模塊v，其列號為j，令j_w＝j，然后在時隙矩陣j_w列時隙s尋找中間模塊w，如果尋找到，則令i_v=i，i為找到的中間級模塊w的行號，繼續(xù)在時隙矩陣i_v行時隙s中尋找中間級模塊v，如果找到，則令j_w＝j，j為找到的中間級模塊v的行號，然后在時隙矩陣j_w列時隙s尋找中間模塊w，這樣重復，直到找不到中間級模塊w或者中間級模塊v為止，得到vwvw路徑，進入步驟7.5）；

7.3）、令j_v＝O_m，在時隙矩陣j_v列時隙s中找到中間級模塊v，其行號為i，令i_w=i，然后在時隙矩陣i_w行時隙s尋找中間級模塊w，如果尋找到，則令j_v＝j，j為找到的中間級模塊w的列號，繼續(xù)在時隙矩陣j_v列時隙s中尋找中間級模塊v，如果找到，則令i_w=i，j為找到的中間級模塊v的列號，然后在時隙矩陣i_w行時隙s尋找中間級模塊w，這樣重復，直到找不到中間級模塊w或者中間級模塊v為止，得到vwvw路徑，進入步驟7.5）；

7.4）、令i_v=I_m，j_v＝O_m，同時在時隙矩陣i_v行和j_v列時隙s兩個分支找到中間級模塊v，按行找到的中間級模塊v的列號為j、按列找到的中間級模塊v的行號為i，令j_w＝j，i_w=i，然后同時在時隙矩陣j_w列和i_w行時隙s兩個分支尋找到中間級模塊w；

如果兩個分支時隙s都找到中間級模塊w，按列找到的中間級模塊w的行號為i，按行找到的中間模塊w的列號為j，則令i_v=i，j_v＝j，如果i_v＝i_w且j_v＝j_w，即找到相同的中間模塊w，進入步驟7.5），否則繼續(xù)在時隙矩陣i_v行和時隙矩陣j_v列時隙s尋找中間級模塊v，如果都找到中間級模塊v，按行找到的中間級模塊v的列號為j、按列找到的中間級模塊v的行號為i，令j_w＝j，i_w=i，如果i_v=i_w且j_v＝j_w，即找到相同的中間模塊v，進入步驟7.5），否則，繼續(xù)在時隙矩陣j_w列和i_w行時隙s兩個分支尋找到中間級模塊v，這樣重復，直到一個分支找不到中間級模塊w或v，則這一個分支停止，另一個分支繼續(xù)，直到都找不到中間級模塊w或者中間級模塊v停止，最后得到一條連通的路徑vwvwv或是兩條不相交的路徑vwvw和vwvw，進入步驟7.5）；

7.5）、將得到的路徑上的中間模塊v換成w，w換成v，同時將中間級模塊v分配給新的連接請求r。