基于負載均衡的隨機作業流密碼服務調度算法

李莉，史國振，耿魁，董秀則，李鳳華,,5

（1. 西安電子科技大學通信工程學院，陜西 西安 710071；2. 北京電子科技學院電子信息工程系，北京 100070；3. 北京電子科技學院信息安全系，北京 100070；4. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；5. 中國科學院大學網絡空間安全學院，北京100049）

1 引言

天地一體化網絡作為無處不在的網絡服務的基礎支撐，是國家信息化的關鍵。在安全形勢日益嚴峻的今天，天地一體化網絡的安全對于實現國家安全戰略目標具有重要的意義。天地一體化網絡的安全保障離不開相應的密碼防護，通過配備高性能的密碼服務器，采用密碼計算資源的虛擬化、密碼服務的高并發調度運行來保障數據安全。天地一體化信息網絡由于跨陸、海、空、天多域及天基網絡的特殊性，拓撲結構具有動態變化的特點，且傳輸鏈路具有高延時、大方差、間歇性的特點，異構互聯也致使網絡設備類型多、密碼資源多、業務需求量大[1]。因此服務于天地一體化網絡的密碼服務器存在接收業務海量高并發且不同業務隨機交叉的現象，如何保證來自不同網絡應用端的不同密碼服務請求得到有效、快速的解決，防止業務流阻塞，業務流的調度及并發運算起著至關重要的作用。文獻[2]針對安全領域中海量業務安全需求多樣性導致的多種密碼算法運算隨機交叉的現象，提出了具有關聯判斷的基于業務標識的分層硬件調度方法——HHS-ACDID，通過兩級調度完成業務流與密碼算法IP核間的映射以及隨機交叉業務流中關聯作業包的正確有序處理，從而實現了高速數據流下多對多通信中多密碼算法、多數據流的隨機交叉加解密問題。

由于多算法密碼服務器屬于典型的異構多核系統，各密碼算法處理節點的處理能力和存儲容量不同，業務流到達各處理節點的時間不一致，如果不能進行合理的作業包與處理節點間的映射，則可能導致處理節點負載輕重不一，影響整個處理系統的吞吐率。本文針對多算法密碼服務器的特點，考慮實際處理需求，在文獻[2]的基礎上，抽象出與實際密切吻合的任務模型，在充分考慮處理節點運算速率和節點存儲容量的基礎上，以負載均衡為調度目標，將處理節點的實際處理能力作為靜態參數，處理節點任務隊列的剩余容量作為動態參數，采用靜態參數和動態參數相結合的方法，設計了一種支持非關聯任務和關聯任務的兩級負載均衡動態調度算法，在不額外增加系統硬件成本的條件下，實現了高速的密碼處理吞吐率。

2 相關研究

多處理器任務調度問題是一種NP-hard問題，其最優解往往與具體應用有關，需要針對實際問題進行建模，很多文獻從不同角度（如負載均衡、吞吐量最大化、資源利用率最大化、減少功耗等方面）對其進行了研究。為獲得資源的最大利用率和并行任務的最短執行時間，Liu等[3]根據歷史調度信息，采用Apriori分類數據挖掘算法，通過建立任務和處理器之間的關聯規則來進行多核處理器調度。該算法提高了內核利用率，但是沒有考慮決定系統調度成敗的歷史調度信息的產生；另外，由于該算法必須考慮關聯規則外任務的調度，使該算法實現復雜。文獻[4]提出一種基于異構多核處理器的 PIE（performance impact estimated）調度算法，該算法以進程在各個內核上能夠獲得性能的評估結果作為任務調度的參考依據，以求充分利用處理器資源，提高任務執行率。其中，性能采集模塊以及評估參數寄存器的使用在一定程度上降低了該算法的易用性。

針對多處理器平臺中公平調度問題，Li等[5]基于時間片輪轉（RR，round robin）調度算法，分別提出了面向同構的多核處理器（DWRR，distributed weighted round robin）調度算法和面向異構的多核處理器（ADWRR，asymmetric distributed weighted round robin）調度算法[6]，實現核間的負載均衡，并保證了全局調度公平性。但并未考慮關聯任務的調度問題。針對多核處理器平臺上關聯任務的調度問題，楊茂林等[7]提出一種資源敏感的實時任務調度算法。該算法采用任務分組策略將存在共享資源敏感的任務劃分為若干個相關任務子集，將同一相關任務子集上的任務盡量分配到同一內核上；對于無法分配在內核上的相關任務子集采用任務拆分策略進行拆分。該算法可以減少核間任務阻塞。但是，當系統中任務數較少或較多時，可能會因為任務相關度評價耗時過長，造成任務的等待，降低系統吞吐率。文獻[8]考慮到云計算環境處理節點的安全性和可用性以及任務之間的相互依賴關系，采用有向無環圖（DAG）描述一個應用中相互依賴的任務，提出一種云計算環境下融合安全與可用性的 DAG任務調度策略。文獻[9]提出一種包含優先級和條件邊的集成控制流信息，擴展并行有向無環圖任務模型，提高對條件任務的解決效率，減少傳統的零星DAG任務系統的調度分析時間。

在異構系統中，基于負載均衡的調度使用最多的是 RR算法和啟發式算法[10]。RR算法采用處理節點輪詢的方式，對任務進行調度，算法簡單、快速，比較適用于硬件實現，但是沒有考慮不同任務間的差異以及關聯任務的執行。考慮QoS需求，已有不少學者基于多目標約束，對經典的啟發式算法，如遺傳算法[11]、蟻群算法[12-14]、Sufferage[15]等進行改進并提出新的調度方案。文獻[16]提出一種雙目標優化粒子群算法（DPSO, discrete particle swarm optimization），在滿足任務安全需求的前提下，縮短系統對任務的響應時間。文獻[17]基于完成時間最快和用戶支出費用最少2個目標，面向商業云提出一種基于完成時間和支付費用權重函數的動態工作流調度算法，為任務選取合適的處理節點。文獻[18]針對多核異構分布式系統中流程序的執行，提出了 2種新的啟發式分區算法：KLA（Kernighan-Linadapted）算法和CA（congestion avoidance）算法來解決空間圖分割流程序的劃分問題，以提高系統的吞吐率。文獻[19]提出采用統計的方法來進行線程的分配，給每個線程分配一個隨機樣本，通過減少需要測量的候選解決方案數量的統計方法來降低線程分配時間，獲得最佳性能。文獻[20]采用多目標優化為約束條件，提出了一種基于混沌蟻群的遺傳算法（GA-CAS），獲得了優于其他啟發式算法的收斂速度。

由于在實際應用中具有許多時刻變化的因素，通過靜態調度找出最優調度方案幾乎不可能，容易造成調度和過程優化控制相互脫節，因此，大規模動態復雜調度始終是研究中的熱點與難點。本文基于海量高并發隨機交叉密碼服務的應用場景，建立一個與實際應用更接近的任務模型，在文獻[2]提出的兩級調度的基礎上，通過對不同運算需求業務流的感知，實現作業包在處理節點上的合理分配，充分發揮異構多核的優勢，實現快速的業務流處理。

3 任務模型

3.1 任務集

在流數據處理系統中，數據需要以包的形式進行傳輸和處理。根據作業包的大小不同，一個作業需要拆分為若干個作業包。假設系統中有n個作業，作業集合記為 J = { J1, J2,… ,Ji, … ,Jn}，作業 Ji劃分為m個作業包，可以表示為 Ji= { Ji1, Ji2,… ,Jid,… ,Jim}。根據文獻[2]中的描述，作業Ji的第a個作業包Pia表示為

其中，taski為作業包所屬業務的編號，同一作業的不同作業包該字段相同，是作業的唯一標識，同時保證處理完作業包的正確返回。cmdi為處理命令，決定對數據的具體操作，如加密、解密、簽名、驗簽等。cypi為密碼算法模塊id號，決定數據的處理節點，c y pi={c luster _ i d | |i p _ i d }，其中，高位表示簇號，低位表示簇內的算法處理節點號，即在流數據打包的軟件層就確定了作業包與算法 IP核間的映射關系。modei為密碼算法工作模式，決定對密碼算法處理節點入口數據的處理，如對于ECB模式可以將數據直接送入算法處理節點，而對于CBC模式，則需要將數據與同一個業務的前一組數據的運算結果進行異或后，再送入算法處理節點。Noi為作業包的序號，long為作業包中運算數據的長度，dia為運算數據。由于不同業務作業包的大小不盡相同，且不同的工作模式、不同算法的運算速度不同，因此在軟件層無法精確地預知處理節點的負載狀況，從而導致處理節點負載不均衡，影響系統的整體吞吐率。為此，本文將 cypi修改為cypi={c luster _ i d }，即在軟件調度層僅確定作業包所需送至的算法處理節點簇，相同的算法實現處于相同的算法節點簇中。作業包與算法IP核間的具體映射關系由硬件調度模塊根據處理節點的工作能力和負載情況實時確定。

流數據處理系統如圖1所示，來自不同應用線程的業務通過作業提交模塊將作業包發送至流數據處理系統的作業接收模塊，作業接收模塊按照時間順序依次接收到各作業包。

圖1 流數據處理系統

用i表示時間戳，則該時間戳的作業包為Ti。多任務環境下，由于數據傳輸路徑、速度等不同，不同業務請求的作業包到達作業調度系統的作業接收模塊時間不同。所以對于同一個業務來說，雖然各作業提交模塊按序提交各業務作業包，但是在作業接收模塊中的作業包是亂序的，即存在不同業務間的交叉接收。因此定義作業接收模塊中的任務集為

其中，nmax為一個作業窗口中作業接收模塊能夠接收的最大作業包的個數。

通過有向無環圖（DAG，directed acyclic graph）對流數據任務集進行描述，可以清晰地表示流數據作業包的傳遞及作業包間的數據相關關系。圖 2為流數據任務集 DAG，共有 4個任務： J OB1={T1, T2}， J OB2= { T3,T5,T9}， J OB3={T4,T7,T8,T11}，JOB4= {T6,T10}。

圖2 流數據任務集DAG

其中，JOB1、JOB2、JOB4為依賴任務，JOB3為非依賴任務。以 CBC加密模式為例介紹密碼運算中的依賴任務：假設2.JOBmode CBC= ，首先將明文分成3種固定長度的作業包，選取初始向量IV，對第一個作業包T3進行加密，得到密文T3′；然后，將密文T3′與下一個作業包T5異或后作為初始向量加密，得到密文T5′；最后，將密文T5′與下一個作業包T9異或后加密，得到密文T9′。加密過程如圖3所示。

圖3 JOB2 CBC加密

圖2 中TS為任務集的入口節點，TE為任務集的出口節點，實線箭頭為數據關聯線有序邊。前序節點：數據關聯線有序邊的起點處的節點為終點處節點的前序節點。由圖3可知，T3是T5的前序節點，T5是T9的前序節點。后繼節點：數據關聯線有序邊的終點處的節點為起點處節點的后繼節點。由圖 3可知，T5是T3的后繼節點，T9是T5的后繼節點。虛線箭頭為數據非關聯線有序邊，其有序僅表現為時間傳遞上的有序性，并沒有數據相關性。

通過流數據任務集的DAG模型可以看出，任務集有以下2種特點：同一業務的作業包在任務集中的排列是有序的；同一業務的作業包序列中穿插有其他業務的作業包。

3.2 作業窗口

作業調度系統根據作業接收模塊中的任務集，對作業包進行調度。假設作業接收模塊的存儲容量為m，數據流的傳輸速率為s bit/s，作業包大小為p，則作業窗口時間t必須滿足

且在t作業窗口時間內，作業接收模塊能夠接收到的作業包的個數最大為

作業包的大小是可變的，由規則化數據結構中的數據長度決定，作業窗口的大小必須保證作業接收模塊能夠完整地接收作業提交系統傳遞過來的作業包。

4 作業調度算法

4.1 作業調度模型

作業調度模型如圖4所示，包括7個部分：作業接收隊列、作業分轉模塊、簇任務隊列、負載均衡控制模塊、處理節點任務隊列、中間狀態存儲模塊和等待任務隊列。

作業接收隊列接收輸入的任務集；作業分轉模塊進行作業的第一級調度，按照cypi將作業包送至相應的簇任務隊列；負載均衡控制模塊進行作業的第二級調度，按照負載均衡策略，將作業包送至相應的處理節點任務隊列；處理節點任務隊列按照先來先服務的原則，將作業包送至處理節點進行算法處理；中間狀態存儲模塊用于暫存依賴作業前序作業包的中間結果，為后繼作業包提供中間數據；等待任務隊列是為了保證數據流的連續性，防止由于某個簇任務隊列滿導致的數據流阻塞，用于暫存已滿簇任務隊列的作業包。

4.2 計算資源

處 理 節 點 集 I P = { I Pi1, I Pi2, … ,I Pim, … ,I Pp1,… ,IPpn}為任務所能獲得的計算資源，每個處理節點具有各自的適用領域 field、運算速度 s和存儲容量cap。其中，適用領域描述該處理節點的功能，與任務屬性中的cypi對應；運算速度取決于處理節點本身的設計，以密碼算法IP核為例，包括密碼算法設計中的信號流水線處理、密鑰擴展的同步處理以及算法實現的工作頻率。存儲容量取決于處理節點任務隊列的大小，存儲容量必須為單元作業包的整數倍，否則會造成數據丟失。即

圖4 作業調度模型

4.3 作業調度策略

本文所研究的基于負載均衡的動態作業調度算法采用了靜態參數與動態參數結合的方法。以處理節點的實際處理能力為靜態參數，處理節點任務隊列的剩余容量為動態參數；按照可調節的比例得到一個權重來決定作業包的優先級。

1) 處理節點狀態表

每個算法簇的負載均衡控制模塊維護一個處理節點狀態表： Sip={tunit,c ap,n}。負載均衡調度算法根據此狀態表進行處理節點權重的計算，進行作業包調度的動態調整。其中，tunit為單元作業包Punit的處理時間，cap為處理節點的任務隊列存儲容量，n為任務隊列中已有的作業包的個數。處理節點任務隊列中每接收一個作業包，則n+1，每輸出一個作業包，則n-1。

由于每個處理節點上可以執行的操作類型不同，如加密、解密、簽名、驗簽，而不同的操作消耗的時間不同，因此單元作業包在不同處理節點上的處理時間為

其中，ti1表示第i個處理節點加密單元作業包的時間，ti2表示第i個處理節點解密單元作業包的時間，ti3表示第i個處理節點對單元作業包簽名需要的時間，ti4表示第i個處理節點對單元作業包驗簽需要的時間。因此，具有m個算法IP的算法i的處理節點狀態矩陣為

2) 處理節點權重

處理節點的權重與處理節點的剩余容量以及處理速度有關。由于處理節點的速度和容量的數量級不同，數據尺度的不統一對處理節點的選擇影響很大，必須進行調整。將節點的處理速度歸一化至[0,1]區間。

其中，mint 為簇上運算最快的節點處理單位作業包所需的時間，maxt 為簇上運算最慢的節點處理單位作業包所需的時間。以具有 m個算法 IP的算法 i的簇為例，有

因此，對于每一個處理節點來說，其速度權重為一固定向量。處理節點的剩余容量歸一化至[0, 1]區間。

其中，cap為處理節點的任務隊列容量，rcap為處理節點的任務隊列剩余容量，可通過隊列的容量減去已經使用的存儲偏移量獲得，p為作業包的大小，n表示任務隊列中已有n個作業包，n可以通過處理節點任務隊列計數器實現。則處理節點的權重函數為

其中，α為速度權重系數，β為剩余容量權重系數。為便于后期處理節點權重的計算，將處理節點狀態矩陣替換為

3) 選擇關系表

選擇關系表用于描述進入處理節點任務隊列的依賴任務ID和處理節點ID間的對應關系，為一個二元表： c hoose_ l ist = {t a ski,ip _ i d }。選擇關系表的長度choose_list.length取決于算法簇處理節點的個數，每個算法簇維護一個選擇關系表。若某算法簇中的處理節點為n個，則

4.4 調度算法

1) 第一級分轉調度

根據cypi進行調度，按照先來先服務的原則將不同算法處理需求的作業包放入對應算法簇任務隊列中；當任務集中某一算法處理需求的作業包大量流入導致相應的簇任務隊列滿時，將當前作業包放入等待任務隊列中，并置mask為1，標識此單元被占用，繼續進行下一個作業包的調度；當簇任務隊列有數據移出時，則查詢等待任務隊列，將先進入的同一算法需求的作業包取出放入簇任務隊列中，如圖5所示。

圖5 第一級分轉調度模型

等待任務隊列能夠使任務集中的作業包不斷地流入，避免了因某個算法簇的任務執行速度慢導致隊列滿，進而導致數據流的停滯。

2）第二級負載均衡調度

策略 1 為保證信號的快速處理，優先考慮算法的存儲容量，當存儲容量不能滿足時，就沒有必要再考慮運算速度。當存儲容量滿足時，選取權重大的處理節點進行作業包的處理。

策略 2 當某依賴任務的前序作業包在處理節點i上運算時，其后繼作業包也必須在此處理節點上運算。此策略可以免除數據遷移帶來的傳輸時延，獲得較好的數據本地化。

具體作業調度算法步驟如下所示。

Step1 根據工作模式modei，判斷依賴性。

若modei為CBC|OFB|CFB，則此作業屬于依賴作業。首先查詢選擇關系表，若選擇關系表中存在此作業包的itask表項，則將此作業包放置于此表項對應的處理節點ip_id的任務隊列中，進入Step7；若選擇關系表中不存在此作業包的itask表項，則將此itask加入選擇關系表中，進入Step2。

若作業為非依賴作業，進入Step2。

Step2 根據處理節點狀態表，獲取本簇處理節點的剩余容量 c apr= c ap ? n p 。

Step3 根據處理節點狀態表和處理算法類型，獲取剩余容量非空處理節點的速度權重。

Step4 計算剩余容量非空處理節點的權重，選取權重最大的處理節點。

Step5 若作業包屬于依賴作業，將此處理節點ip_id加入itask對應的表項；否則，進入Step6。

Step6 將作業包放入處理節點ip_id的任務隊列中。

Step7 若作業包為依賴作業包，在作業包處理完成時，判斷此作業包是否為作業的最后一個分片，若是則從選擇關系表中將此作業包itask對應的表項刪除，并將運算結果直接返回業務請求端；否則將此作業包的運算結果作為中間狀態保存至中間狀態存儲模塊。若作業包不屬于依賴作業包，則將運算結果直接返回業務請求端。

5 分析及驗證

本文對任務調度負載均衡性和執行效率進行了仿真，并與基于業務標識的分層硬件調度方法HHS-ACDID進行對比分析。仿真在Windows環境下，通過C++語言實現算法。由于每一個簇的調度過程是相似的，選取一個簇下的調度進行仿真。

任務集信息參數設置如表1所示。其中，itask為作業編號；Noi為不同作業包編號；flag為依賴作業標識；arrivalTime為作業包進入作業調度模塊的時刻；long為作業包大小。

表1 任務集的參數設置

仿真實驗1 權重系數α、β對完成時間的影響。假設當α=αi時，系統獲得最小完成時間。IP核數=4，隨機生成 4組處理速度 ti meij∈[16,36],i, j ∈ [1 ,4]。改變處理節點隊列存儲容量初始值CAP，觀察CAP與αi之間的關系如圖6(a)所示，可見在其他參數相同的情況下，取得最小完成時間的αi的取值隨CAP的增大而減小。IP核數=4，單位作業包完成時間分別為 t ime1∈ ( 8,28)， t ime2∈ ( 16,36)，time3∈ ( 32,52)，t i me4∈ ( 64,84)，C AP= 2 00，仿真結果如圖6(b)所示，取得最小完成時間的αi的變化趨勢與圖6(a)基本一致。

圖6 α、β與完成時間關系

仿真實驗 2 權重系數對負載均衡性和執行效率的影響。采用相同的任務集，作業包總數=600，IP核數=4， ti meij∈[16,36],i, j ∈ [1 ,4]，改變α∈[0,1]，β∈[0,1]的取值，負載分布和完成時間如圖7所示。

圖7 α、β對調度結果的影響

從圖7可以看出，隨著處理節點速度權重系數α增大，IP核負載分布趨向于不均衡；系統完成時間先減小后增大，最后趨于不變。其中，當α=0.05時，完成時間取得最小值，負載分布較均衡。由此可知，α、β的取值影響任務調度過程中 IP核的負載分布和完成時間，以下實驗都將在完成時間最小的前提下討論。

仿真實驗 3 算法的負載均衡性。處理節點性能不變， ti meij∈[16,36],i, j ∈ [1 ,4]，IP核數=4，作業包總數分別為100、200、300、400、500、600、700，負載分布情況如圖8所示。

圖8 4個IP核的負載分布

IP核數為10，作業包數分別為500、700、1000、1100、1300、1500，負載分布情況如圖9所示。

圖9 10個IP核的負載分布

當處理節點數分別為4和10時，反映出相同的規律：隨著作業包數的增加，調度結果保持良好的負載均衡性。

仿真實驗4 從2個方面比較本文算法與分層硬件調度方法 HHS-ACDID的執行效率：固定 IP核數，改變作業包數；固定作業包數，改變IP核數。

1) 固定 IP核數為 4，作業包總數變化（100～700）；固定 IP核數為 10，作業包數變化（500～1500），本文算法與HHS-ACDID算法的執行時間比較分別如圖10和圖11所示。

圖10 4個IP核的完成時間

圖11 10個IP核的完成時間

由圖10和圖11可知，在相同的實驗環境下，本文算法的執行效率明顯優于HHS-ACDID算法，執行時間比HHS-ACDID算法減少約10.6%～15.3%，并且隨著作業包數的增多，其優勢更加明顯。這主要是因為與HHS-ACDID算法相比，本文算法同時考慮不同處理節點的處理性能和當前負載情況，保證了處理節點的負載均衡和任務的處理速度，使高性能的處理節點得到更多的使用率。

2) 固定任務數=1 000，IP核數變化（4～10個IP核）時，本文算法與HHS-ACDID算法執行時間如圖12所示。

圖12 不同IP核下的任務完成時間對比

由圖 12可知，對于相同的任務集，本文算法的執行時間比HHS-ACDID算法少10.3%～15.3%。IP核數量較少時優勢明顯；隨著IP數量的增加，其優勢有所降低。

可見，通過硬件實時監控處理節點任務隊列的剩余容量，在任務數較大時，提高速度權重系數，減小剩余容量權重系數；任務數較小時，提高剩余容量權重系數，減小速度權重系數，能獲得較佳的負載均衡效果。根據測試結果，在作業量增大的趨勢下，本文算法展現出更大的優勢。

6 結束語

本文針對多算法密碼流系統模型，提出了一種基于負載均衡的兩級作業調度算法，首先根據作業包的算法標識cypi把任務遞交到相應的簇；然后根據作業包的工作模式 modei以及處理節點狀態表進行二級均衡調度。該算法適用于關聯任務和非關聯任務以及混合情況，實現上采用三級存儲層次的流水架構，通過作業分轉模塊、負載均衡控制模塊以及等待任務隊列，保證了數據流傳輸的連續性，不存在作業的重分配以及因作業需求類型不同導致的某個作業長期占用計算資源，而其他作業得不到響應的情況，也起到了隱藏傳輸時延、改善帶寬效應的作用。仿真結果表明，該算法在保證系統負載均衡的基礎上，執行效率比 HHS-ACDID算法高12%左右。