[發(fā)明專利]時(shí)間觸發(fā)調(diào)度模型的訓(xùn)練、時(shí)間觸發(fā)調(diào)度方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 202111137291.5
• 申請(qǐng)日: 2021-09-27
• 公開（公告）號(hào): CN114006827B
• 公開（公告）日: 2023-01-24
• 發(fā)明（設(shè)計(jì)）人: 萬(wàn)海;賈宏宇;趙曦濱
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): H04L41/16
• 分類號(hào): H04L41/16;H04L41/12
• 代理公司: 北京聿宏知識(shí)產(chǎn)權(quán)代理有限公司 11372
• 代理人: 陳超德;吳昊

本發(fā)明公開一種時(shí)間觸發(fā)調(diào)度模型的訓(xùn)練、時(shí)間觸發(fā)調(diào)度方法及裝置，包括：將由鏈路的基礎(chǔ)特征向量、嵌入向量和全局向量拼接獲得的目標(biāo)向量輸入策略網(wǎng)絡(luò)，確定待調(diào)度TT流的第一下一跳鏈路、第一轉(zhuǎn)發(fā)相位及第一時(shí)隙；若當(dāng)前調(diào)度所到達(dá)的網(wǎng)絡(luò)設(shè)備不是終點(diǎn)，則更新目標(biāo)向量以及時(shí)隙占用情況，并將更新后的目標(biāo)向量輸入策略網(wǎng)絡(luò)確定待調(diào)度TT流的第二下一跳鏈路、第二轉(zhuǎn)發(fā)相位及第二時(shí)隙，并利用第二時(shí)隙和第二下一跳鏈路對(duì)待調(diào)度TT流進(jìn)行調(diào)度，直至達(dá)到終點(diǎn)；在到達(dá)預(yù)設(shè)調(diào)度終止條件時(shí)，利用策略梯度算法更新時(shí)間觸發(fā)調(diào)度模型的參數(shù)，利用更新后的時(shí)間觸發(fā)調(diào)度模型繼續(xù)對(duì)待調(diào)度TT流進(jìn)行調(diào)度，直至目標(biāo)函數(shù)取值最大時(shí)，獲得目標(biāo)時(shí)間觸發(fā)調(diào)度模型。

技術(shù)領(lǐng)域

本發(fā)明涉及互聯(lián)網(wǎng)技術(shù)領(lǐng)域，具體而言，涉及一種時(shí)間觸發(fā)調(diào)度模型的訓(xùn)練、時(shí)間觸發(fā)調(diào)度方法及裝置。

背景技術(shù)

實(shí)時(shí)數(shù)據(jù)的確定性傳輸在汽車、火車、航空航天等關(guān)鍵領(lǐng)域有著強(qiáng)烈的需求。基于以太網(wǎng)的實(shí)時(shí)網(wǎng)絡(luò)，如時(shí)間敏感網(wǎng)絡(luò)(Time-Sensitive Networking，TSN)和時(shí)間觸發(fā)以太網(wǎng)(Time-Triggered Ethernet，TTE)提供了具有高帶寬的實(shí)時(shí)數(shù)據(jù)傳輸能力。TSN和TTE是在傳統(tǒng)以太網(wǎng)上做的改進(jìn)，不僅可以提供傳統(tǒng)的盡力而為(Best-Effort，BE)數(shù)據(jù)傳輸服務(wù)，還具有時(shí)間觸發(fā)(Time-Triggered，TT)數(shù)據(jù)傳輸能力，通過(guò)時(shí)間觸發(fā)的方式實(shí)現(xiàn)實(shí)時(shí)數(shù)據(jù)的確定性傳輸。TT幀的傳輸機(jī)制主要以兩個(gè)方面為基礎(chǔ)：基于調(diào)度表的幀傳輸和精確時(shí)間同步。每個(gè)TT幀的準(zhǔn)確到達(dá)和轉(zhuǎn)發(fā)時(shí)間都是提前計(jì)算出來(lái)的，并保存在調(diào)度表中。然后所有網(wǎng)絡(luò)設(shè)備(包括終端節(jié)點(diǎn)和交換機(jī)等)根據(jù)一個(gè)全局時(shí)間周期性地發(fā)送TT幀，其中所有設(shè)備需要提前與全局時(shí)間進(jìn)行同步，同步方案可以通過(guò)SAE AS6802、IEEE 802.1AS和IEEE1588協(xié)議來(lái)實(shí)現(xiàn)。

對(duì)于特定的網(wǎng)絡(luò)配置，需要計(jì)算相應(yīng)的調(diào)度表。隨著網(wǎng)絡(luò)服務(wù)的日益開放，網(wǎng)絡(luò)配置的變化是不可避免的。節(jié)點(diǎn)/鏈路故障、新增節(jié)點(diǎn)和交換機(jī)的引入、上層應(yīng)用數(shù)據(jù)傳輸需求的變化等情況都會(huì)導(dǎo)致網(wǎng)絡(luò)配置的變化。因此需要及時(shí)重新計(jì)算進(jìn)度表。

基于求解器的調(diào)度算法將調(diào)度需求、網(wǎng)絡(luò)拓?fù)洹⒃O(shè)備狀態(tài)等建模為一組線性約束，以確保TT幀在每個(gè)鏈路上的傳輸是互斥的。然后調(diào)度算法利用可滿足模理論(satisfiability modulo theory，SMT)求解器或整數(shù)線性規(guī)劃(integer linearprogramming，ILP)求解器在這些約束條件下尋找解。一旦找到了解決方案，就可以基于該解決方案構(gòu)建TT調(diào)度表。但是上述基于求解器的方法比較耗時(shí)，不能用于TT調(diào)度表的快速計(jì)算。

與基于求解器的方法相比，基于啟發(fā)式的方法可以有效地減少求解時(shí)間。例如，啟發(fā)式列表調(diào)度器(heuristic list scheduler，HLS)通過(guò)兩個(gè)啟發(fā)式思想計(jì)算出一個(gè)有效的時(shí)間表：為每個(gè)TT流獲取有效路由的啟發(fā)式思想和另一個(gè)分配流轉(zhuǎn)發(fā)時(shí)間的啟發(fā)式思想。但是，設(shè)計(jì)良好的啟發(fā)式策略需要領(lǐng)域知識(shí)和專家人員。啟發(fā)式方法通常是針對(duì)特定場(chǎng)景手動(dòng)定義的，不能直接遷移到其他應(yīng)用場(chǎng)景。此外，當(dāng)面對(duì)復(fù)雜和大規(guī)模的網(wǎng)絡(luò)時(shí)，手工啟發(fā)式算法的性能可能會(huì)急劇下降。

因此，如何提高TT流調(diào)度效率是亟待解決的。

發(fā)明內(nèi)容

本發(fā)明提供了一種時(shí)間觸發(fā)調(diào)度模型的訓(xùn)練、時(shí)間觸發(fā)調(diào)度方法及裝置，能夠提高TT流的調(diào)度效率。具體的技術(shù)方案如下：

第一方面，本發(fā)明實(shí)施例提供了一種時(shí)間觸發(fā)調(diào)度模型的訓(xùn)練方法，所述方法包括：

提取由網(wǎng)絡(luò)設(shè)備構(gòu)成的拓?fù)鋱D中每條鏈路的基礎(chǔ)特征向量；所述基礎(chǔ)特征向量包括原始特征向量和可用資源向量，所述原始特征向量包括以下一項(xiàng)或多項(xiàng)的組合：待調(diào)度時(shí)間觸發(fā)TT流的起點(diǎn)、所述待調(diào)度TT流的終點(diǎn)、當(dāng)前鏈路是否被訪問(wèn)、合法的相位比例、帶寬的利用率以及所述待調(diào)度TT流的周期；

針對(duì)每條鏈路，根據(jù)所述鏈路的基礎(chǔ)特征向量和所述鏈路的鄰居向量，獲得所述鏈路的嵌入向量；所述鄰居向量為與所述鏈路相鄰的其他鏈路的基礎(chǔ)特征向量；