[發明專利]一種在服務鏈環境下保障數據流截止時間的調度方法

有效

• 申請號: 201710447404.9
• 申請日: 2017-06-16
• 公開（公告）號: CN107332786B
• 公開（公告）日: 2019-08-13
• 發明（設計）人: 李克秋;張建輝;齊恒;喻海生;金英偉
• 申請（專利權）人: 大連理工大學
• 主分類號: H04L12/863
• 分類號: H04L12/863;H04L12/867;H04L12/875;H04L12/803
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 溫福雪;侯明遠

1.一種在服務鏈環境下保障數據流截止時間的調度方法，其特征在于，所述的調度方法分為DRFQ速率分配、確定數據流調度順序以及路徑選擇算法三部分；

(1)DRFQ速率分配：

在多資源環境下，進入網絡功能設備的數據流的數據包依次在多種硬件資源上被處理，首先在CPU上被處理，然后被放入內存，最后再推送到網卡；經過不同網絡功能處理時，數據包在不同硬件資源上所需要的處理時長不相同；

DRFQ使用時間戳來標記每個數據包在不同資源上的開始和結束時間；DRFQ在進行時間戳標記時，假設該設備上只有一個數據流f_i，即DRFQ對于不同數據流進行彼此獨立的時間戳標記，以此來測量每個數據流單獨通過該設備時得到的服務時長；數據包所得到的時間戳都是虛擬的開始時間和結束時間，因為實際上通過該設備的數據流并非只有f_i；假設該設備中共有n種硬件資源，f_i的第k個數據包在第個資源上的開始時間和結束時間分別被標記為：

其中，表示數據包在該資源上的處理時長，而表示為：

表示的實際到達時刻；表示數據包到達時第個資源上正在被處理的數據包的集合；如果該集合不為空，則將當前正在被處理的數據包中具有最大開始時間戳的數據包的時間戳賦給如果在該資源上的結束時間大于那么否則

在多資源環境下，每個數據包在多個硬件資源上有多個開始時間，DRFQ使用一個數據包最大的開始時間戳做為該數據包用于調度時的時間戳，以測量該數據流所得到的服務時長；在多個數據流當中，DRFQ挑選具有最小時間戳的數據包執行調度，通過這種方式來平衡不同數據流所得到的服務時長，得到調度的數據包都具有較小的時間戳標記；當f_i以較高速率到達網絡功能設備時，該設備的處理能力不足以快速完成對該數據流的處理，那么f_i的數據包會積壓在隊列中；對于一個積壓的數據流f_i，到達時還沒有開始它在硬件資源上的處理，即擁有較大的時間戳標記；假設在所有資源上而數據包在各個資源上的開始時間簡化為：

其中，將在各個資源上的開始時間都設為0；數據包最終用于調度的時間戳表示為：

其中，表示在各個資源上消耗最多的處理時長；

現假設有兩條積壓的數據流f_i和f_j，它們各自數據包所得到的時間戳之間的間隔分別是和假設在時刻t，兩個來自它們的數據包擁有相同的時間戳標記S；一段時間后，又有兩個數據包得到相同的時間戳標記S'，S'表示為：

在之后的調度周期中，f_i共有個數據包被處理；所有數據包在到達隊列時就確定了其時間戳，而數據包之間的時間戳間隔又是固定的，故數據流f_i和f_j的數據包將按照固定次序依次調度，并且該調度周期將循環，直至某個數據流完成它的傳輸；如果f_i的每個數據包大小為s(p_i)，那么在每個調度周期中，它所得到的傳輸速率為：

數據流f_j的傳輸速率也被確定；

(2)確定數據流調度順序：

數據流通常擁有不同的數據量、生成時間以及截止時間，分別表示為s(f_i)、a_i和d_i；如果一個數據流剛好在它的截止時間完成傳輸，那它所需要的最小傳輸速率為：

優先調度速率需求最高的數據流；

(3)路徑選擇算法：為每個新到達的數據流選擇適當的傳輸路徑；在此過程中有兩個因素被考慮：保障數據流的截止時間要求以及提高網絡吞吐量；新數據流的加入會占用一部分網絡功能設備內的資源，必然影響先前數據流的傳輸；因此，設計提高網絡吞吐量的機制以使網絡容納更多的數據流；

截止時間保障機制，用于保障先前數據流不會因為新數據流得到調度而錯過它們的截止時間；假設f_i是下一個應該被調度的數據流，并且在它的源端和目的端之間共有x條路徑，而每條路徑上部署m個多功能網絡設備；基于對功能網絡設備上數據流信息的分析，包括數據包的大小以及所執行的網絡功能類型，依據DRFQ所實現的速率分配特性，得到f_i在第個設備上所能得到的速率為進而得到f_i在第x條路徑上所能得到的最大速率為：

同樣地，f_i在所有路徑上所得到的最大傳輸速率都可得到；根據DRFQ速率分配的特性，f_i的調度會影響與它經過相同網絡功能設備的先前數據流的傳輸速率；因此，并非所有路徑都能成為f_i的可行傳輸路徑；f_i的可行傳輸路徑指的是，當f_i在這條路徑上進行傳輸時，經過相同網絡功能設備的先前得到調度的數據流并不會錯過它們的截止時間；

當把f_i傳輸到某個網絡功能設備上時，根據網絡功能設備上當前的負載，依據DRFQ的速率分配特性，計算調度f_i之后所有數據流得到的傳輸速率；如果有任意一個數據流f_j的速率降低到低于它所需的最低速率r_j，那么該設備所在的這條路徑不能成為f_i的可行傳輸路徑；該截止時間保障機制適用于這條路徑上的所有網絡功能設備；只有當f_i在一條路徑中所有的網絡功能設備上都不會使先前數據流錯過它們的截止時間時，這條路徑被標識為它的可行傳輸路徑；通過截止時間保障機制，先前得到調度的數據流安全地在它們的截止時間之前完成數據傳輸；而在f_i的多條可行傳輸路徑中，選擇一條路徑作為它最終的傳輸路徑；

提高網絡吞吐量機制，用于在數據流f_i的多條可行傳輸路徑當中選擇一條作為它最終的傳輸路徑，同時最大化網絡吞吐量；使用如下公式計量網絡吞吐量：

其中，表示網絡中所有數據流的集合，包括剛得到調度的數據流f_i；r_j表示假設調度數據流f_i后數據流f_j的速率更新后的值；對應f_i不同的可行傳輸路徑；有不同的取值，取值越大，表示f_i加入后網絡的吞吐量越高；為了使網絡容納更多的數據流，選擇獲得最大值的可行傳輸路徑作為新數據流f_i最終的傳輸路徑。