[發明專利]基于排隊論的樹形網絡拓撲結構的優化方法

有效

• 申請號: 201710255427.X
• 申請日: 2017-04-19
• 公開（公告）號: CN106936645B
• 公開（公告）日: 2019-10-11
• 發明（設計）人: 徐展琦;翟波濤;劉楊;張玉帥
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/753
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 韋全生;王品華

1.一種基于排隊論的樹形網絡拓撲結構的優化方法，其特征在于，包括如下步驟：

(1)給定基礎樹形網絡拓撲結構：包括N級基本交換模塊，其中N≥2，最高級基本交換模塊的數量為1，且其包含Q_N個速率相同的下行低速端口；第k級基本交換模塊的數量為X_k＝Q_k+1X_k+1，k＝1,2,...,N-1，且每個基本交換模塊包含Q_k個速率相同的下行低速端口和1個上行高速端口，該N級基本交換模塊中較低級基本交換模塊的下行低速端口數大于或等于較高級基本交換模塊的下行低速端口數，第1級的基本交換模塊的下行低速端口與用戶節點連接，其余各級基本交換模塊的下行低速端口分別依次與下一級的上行高速端口連接；

(2)給定基礎樹形網絡拓撲結構的業務模型和路由算法，其中業務模型為目的節點均勻分布、分組到達網絡的過程為泊松過程、分組服務時間服從負指數分布且所有分組長度歸一化為1；路由算法采用最短路徑確定性路由算法；

(3)利用排隊論和最短路徑確定性路由算法確定的路由過程，并建立樹形網絡拓撲結構各級基本交換模塊的排隊節點模型，實現步驟為：

(3a)將樹形網絡拓撲結構中除N級外的基本交換模塊的上行分組轉發方式和下行分組轉發方式，分別等效為上行排隊節點和下行排隊節點，得到除第N級外的基本交換模塊的排隊節點模型；

(3b)將第N級的上行轉發方式等效為上行排隊節點，將分組在該級的向下轉發過程等效為下行排隊節點，得到第N級基本交換模塊的排隊節點模型；

(4)按照給定基礎樹形網絡拓撲結構中基本交換模塊的連接關系，將各級基本交換模塊的排隊節點模型連接起來，得到樹形網絡拓撲結構的排隊網絡模型；

(5)根據排隊網絡模型進行理論計算，得到樹形網絡拓撲結構的吞吐量TP、平均端到端時延T_d和平均丟失率LR的理論值，實現步驟為：

(5a)根據給定的樹形網絡拓撲結構的業務模型和最短路徑確定性路由算法，推導出排隊網絡模型第k級上行排隊節點的分組向k+1級傳輸的路由概率和直接傳輸到下行排隊節點的路由概率的計算公式：

(5b)根據給定的樹形網絡拓撲結構的業務模型和最短路徑確定性路由算法，推導出排隊網絡模型第k級下行排隊節點的分組通過目的節點所在的低速端口傳輸到k-1級的路由概率r_k,dw的計算公式：

(5c)利用步驟(5a)中的路由概率和最短路徑確定性路由算法，推導出排隊網絡模型中分組在第k級完成交換的概率R_k的計算公式：

(5d)利用給定的樹形網絡拓撲結構的業務模型以及步驟(5a)和步驟(5b)中的路由概率，推導出排隊網絡模型中第k級上行排隊節點的到達率λ_k,up和下行排隊節點的到達率λ_k,_dw的計算公式：

其中，λ_u表示分組通過第一級上行排隊節點進入網絡的到達率，lr_k,up和lr_k,dw分別表示第k級每個基本交換模塊上行排隊節點和下行排隊節點的丟失概率；

(5e)利用排隊論，建立排隊網絡模型的上行排隊節點的狀態轉移方程和下行排隊節點的狀態轉移方程，分別為方程式(7)和(8)：

其中，μ_k,up和μ_k,dw分別表示第k級每個基本交換模塊上行排隊節點和下行排隊節點的服務速率，C_k,up和C_k,dw分別表示第k級每個基本交換模塊上行排隊節點和下處于狀態行排隊節點的緩存容量，p_k,up(i)和p_k,dw(i)分別表示上行排隊節點和下行排隊節點處于狀態i的概率，且k＝1,2,...,N，N表示基本交換模塊的級數；

(5f)利用步驟(5e)中的兩個狀態轉移方程，推導排隊網絡模型中第k級每個基本交換模塊上行排隊節點處于狀態i的概率p_k,up(i)和下行排隊節點處于狀態i的概率p_k,dw(i)的計算公式：

(5g)利用步驟(5f)中上行排隊節點的狀態概率和排隊論中的Little定理，推導出排隊網絡模型中各級上行排隊節點的丟失率lr_k,up和時延t_k,up的計算公式：

lr_k,up＝p_k,up(C_k,up) k＝1,2,...,N (11)

(5h)利用步驟(5f)中下行排隊節點的狀態概率和排隊論中的Little定理，推導出排隊網絡模型中各級下行排隊節點的丟失率lr_k,dw和時延t_k,dw的計算公式：

lr_k,dw＝p_k,dw(C_k,dw) k＝1,2,...,N (13)

(5i)利用最短確定性路由算法和步驟(5g)和(5h)的結果，推導出排隊網絡模型中分組在第k級完成交換的丟失的概率lr_k和時延t_k的計算公式：

(5j)利用步驟(5c)得到的概率R_k和步驟(5i)得到的丟失概率lr_k和時延t_k，推導出給定基礎樹形網絡拓撲結構的平均丟失率LR和平均端到端時延T_d的計算公式：

(5k)利用步驟(5j)得到的平均丟失率LR，推導出給定基礎樹形網絡拓撲結構的吞吐量TP的計算公式：

TP＝λ_u(1-LR) (19)

(5l)利用步驟(5j)和步驟(5j)的計算公式，計算樹形網絡拓撲結構的吞吐量TP、平均端到端時延T_d和平均丟失率LR的值；

(6)根據樹形網絡拓撲結構的排隊網絡模型建立仿真模型，并利用仿真模型對樹形網絡拓撲結構的性能指標進行仿真，得到樹形網絡拓撲結構的吞吐量TP′、平均端到端時延T_d′和平均丟失率LR′的仿真值，實現步驟為：

(6a)設定樹形網絡拓撲結構各級基本交換模塊的下行端口數、第1級基本交換模塊的緩存大小、緩存分配方案、用戶節點的數量和分組的到達率，并根據設定的參數確定各級排隊節點的緩存大小和服務速率；

(6b)首先構建設定的樹形網絡拓撲結構的排隊網絡模型，確定該排隊網絡模型中各個排隊節點間的連接關系，并對各個排隊節點進行初始化，然后按照設定的用戶節點的業務強度，使用戶節點生成泊松分組流，并將分組輸入至第1級上行排隊節點；

(6c)遍歷排隊網絡模型的所有排隊節點，找到最先發生分組到達或分組離開的排隊節點，如果所找到的排隊節點發生的是分組到達事件，執行步驟(6d)；如果所找到的排隊節點發生的是分組離開事件就執行步驟(6e)；

(6d)給排隊節點的分組到達總數加1，分組到達后，如果排隊節點緩存滿時，丟棄該分組，同時給排隊節點的丟失分組數加1；如果排隊節點未滿時，記錄分組到達時間，并判斷服務員所處狀態，若處于空閑狀態，記錄分組的服務時間和服務完成后分組離開的時間，并執行步驟(6f)，若處于服務狀態，該分組在排隊節點中等待，并執行步驟(6f)；

(6e)記錄該分組的離開時間，根據最短路徑確定性路由算法確定分組將要流入的下一排隊節點，并對其分組到達時間更新，并判斷該排隊節點是否還有正排隊的分組，若是，位于隊頭的分組開始接受服務，記錄該分組的服務時間和服務完成后分組離開的時間，否則，執行步驟(6f)；

(6f)判斷樹形網絡拓撲結構中到達的分組數是否等于仿真的設定值，若是，統計網絡的性能指標，仿真完成，否則執行步驟(6c)；

(7)對步驟(5)得到的樹形網絡拓撲結構的吞吐量TP、平均端到端時延T_d和平均丟失率LR的理論值與步驟(6)中得到的樹形網絡拓撲結構的吞吐量TP′、平均端到端時延T_d′和平均丟失率LR′的仿真值分別進行比較，確定步驟(5)理論計算的正確性和步驟(4)排隊網絡模型的合理性；

(8)利用步驟(7)確定的排隊網絡模型，考慮業務強度、緩存、交換模塊和網絡拓撲結構等因素，對步驟(1)給定的基礎樹形網絡拓撲結構進行優化，給出以下三種優化實施實例：

(8a)給定包括用戶節點數和各級基本交換模塊下行端口數的樹形網絡拓撲結構和業務強度，在樹形網絡拓撲結構總緩存取不同值時，分別計算不同緩存分配方案下的樹形網絡拓撲結構的性能仿真值，根據所得的性能仿真值，并結合業務需求，選擇最優的樹形網絡拓撲結構；

(8b)給定用戶節點數和緩存分配方案，在不同業務強度下，分別計算不同樹形網絡拓撲結構的性能仿真值，根據所得的性能仿真值，并結合業務需求，選擇最優的樹形網絡拓撲結構；

(8c)給定包括用戶節點數和各級基本交換模塊的下行端口數的樹形網絡拓撲結構和緩存分配方案，在不同的業務強度下，分別計算基本交換模塊緩存不同的樹形網絡拓撲結構的性能仿真值，根據所得的性能仿真值，并結合業務需求，選擇最優的樹形網絡拓撲結構。