[發明專利]一種基于剩余任務處理時間補償的網絡處理器負載均衡調度方法

有效

• 申請號: 201310612808.0
• 申請日: 2013-11-26
• 公開（公告）號: CN103685053B
• 公開（公告）日: 2017-01-11
• 發明（設計）人: 張建華;王國棟;李云春;李巍;李靖軒
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H04L12/803
• 分類號: H04L12/803;H04L12/863
• 代理公司: 北京永創新實專利事務所11121
• 代理人: 李有浩

1.一種基于剩余任務處理時間補償的網絡處理器負載均衡調度方法，其特征在于：該負載均衡調度方法包括有下列步驟；

步驟A：數據流的關聯信息

（A）一個多核處理器上包括有多個處理單元，采用集合形式表達為M＝{m₁,m₂,…,m_K}；K表示處理單元的總個數；

（B）一個多核處理器上運行有多條數據流，數據流采用集合形式表達為MD＝{F₁,F₂,…,F_X}；X表示運行在多核處理器上的數據流的總條數；

設置數據流被調度完成的時間，第一條數據流F₁被調度完成的時間記為第二條數據流F₂被調度完成的時間記為任意一條數據流F_X被調度完成的時間記為

（C）一條數據流中包括有多個數據包，采用集合形式表達為F_X＝{f₁,f₂,…,f_a-1,f_a,f_a+1,…,f_q}；a-1,a,a+1,q表示數據包的標識號；任意一個數據包f_q中至少包括有源IP地址、目的IP地址、源端口、目的端口和協議號；

（D）數據包f₁到達同一條數據流的截止時間記為數據包f₂到達同一條數據流的截止時間記為數據包f_a-1到達同一條數據流的截止時間記為數據包f_a到達同一條數據流的截止時間記為數據包f_a+1到達同一條數據流的截止時間記為數據包f_q到達同一條數據流的截止時間記為；多個數據包到達同一條數據流的截止時間采用集合形式表達為

（E）數據包f₁被調度的時間記為數據包f₂被調度的時間記為數據包f_a-1被調度的時間記為數據包f_a被調度的時間記為數據包f_a+1被調度的時間記為數據包f_q被調度的時間記為屬于同一數據流的多個數據包被調度的時間采用集合形式表達為

（F）相鄰兩個數據包到達同一條數據流的時間間隔記為則有與的時間間隔記為

步驟B：建立數據流映射表

將多核處理器接收到的數據流，依據先進先記錄的方式記錄入“數據流映射表”中；

表一數據流映射表的格式

Tab₁Tab₂Tab₃Tab₄Tab₅

Tab₁用于記錄運行在多核處理器上的數據流；

Tab₂用于記錄同一條數據流中每個數據包被調度的時間；在本發明中，將未調度的數據包的時間稱為剩余任務處理時間；

Tab₃用于記錄數據流當前運行的處理單元；

Tab₄用于記錄預設的數據流被調度完成的時間；

Tab₅用于記錄同一條數據流中的數據包總數；

步驟C：提取調度屬性

依據步驟B得到的“數據流映射表”的Tad₂項記載的信息，來判斷數據包是否被調度；若被調度，則數據包歸類至已調度任務隊列中，并且數據包運行在當前的處理單元上；若未調度，則數據包歸類至未調度任務隊列Qin={QinF1,QinF2,...,QinFX}]]>中，并執行步驟E；

在第一條數據流F₁中，當Tad₂項中記載有調度時間，則將所述調度時間對應的數據包提取出來，并把提取出的數據包歸類到已調度任務隊列中；讓提取出的數據包繼續運行在當前的處理單元上；將在Tad₂項中未體現調度時間的數據包歸類到未調度任務隊列中，并執行步驟E；

在第二條數據流F₂中，當Tad₂項中記載有調度時間，則將所述調度時間對應的數據包提取出來，并把提取出的數據包歸類到已調度任務隊列中；讓提取出的數據包繼續運行在當前的處理單元上；將在Tad₂項中未體現調度時間的數據包歸類到未調度任務隊列中，并執行步驟E；

在第X條數據流F_X中，當Tad₂項中記載有調度時間，則將所述調度時間對應的數據包提取出來，并把提取出的數據包歸類到已調度任務隊列中；讓提取出的數據包繼續運行在當前的處理單元上；將在Tad₂項中未體現調度時間的數據包歸類到未調度任務隊列中，并執行步驟E；

步驟D：判斷相鄰兩個數據流的任務相關性

依據任務關聯關系對未調度任務隊列中的數據包按照所屬數據流計算相鄰兩個數據包的任務相關性；

若r＝1，則說明前一數據包f_a-1與當前數據包f_a之間存在有任務相關性，并將存在相關性的數據包歸類到關聯隊列QS_有中，所述關聯隊列QS_有中的數據包仍然運行在當前的處理單元上；

若r＝0，則說明前一數據包f_a-1與當前數據包f_a之間不存在任務相關性，并將不存在相關性的數據包歸類到不關聯隊列QS_無中，則執行步驟F；

步驟E：提取未調度比值

遍歷完全“數據流映射表”，提取出每條數據流中調度過和未經調度的數據包的個數，然后匯總運行于多核處理器上的所有數據流的數據包總數以及未經調度過的數據包的個數最后計算未調度數占數據包總數的比值w，且

步驟F：計算隊列長度

依據負載關系對不關聯隊列QS_無進行統一化處理，得到每個處理單元上的負載然后選取出最小負載的處理單元記為m^min；將當前數據包f_a運行在所述m^min處理單元上；

w表示未調度的比例，0≤w≤1；

K表示多核處理器中的處理單元的總數。