[發(fā)明專利]用于時(shí)間敏感網(wǎng)絡(luò)數(shù)據(jù)確定性調(diào)度方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 202111453210.2
• 申請(qǐng)日: 2021-11-30
• 公開（公告）號(hào): CN114268550A
• 公開（公告）日: 2022-04-01
• 發(fā)明（設(shè)計(jì)）人: 陳松;朱海龍;黃韜;何斌;謝人超
• 申請(qǐng)（專利權(quán)）人: 網(wǎng)絡(luò)通信與安全紫金山實(shí)驗(yàn)室
• 主分類號(hào): H04L41/12
• 分類號(hào): H04L41/12;H04L41/14;H04L47/283;H04L49/90
• 代理公司: 北京路浩知識(shí)產(chǎn)權(quán)代理有限公司 11002
• 代理人: 陳新生

本申請(qǐng)?zhí)峁┮环N用于時(shí)間敏感網(wǎng)絡(luò)數(shù)據(jù)確定性調(diào)度方法及裝置，所述方法包括：構(gòu)建時(shí)間敏感網(wǎng)絡(luò)模型，所述時(shí)間敏感網(wǎng)絡(luò)模型包括流子模型、交換機(jī)子模型、拓?fù)渥幽Ｐ?；基于局部搜索算法確定最優(yōu)解，所述最優(yōu)解包含每一流的發(fā)送時(shí)間；根據(jù)每一流的發(fā)送時(shí)間對(duì)時(shí)間敏感網(wǎng)絡(luò)的數(shù)據(jù)流進(jìn)行調(diào)度。本發(fā)明可以計(jì)算使用802.1QCH協(xié)議組建TSN網(wǎng)絡(luò)時(shí)各流的開始時(shí)間，既可以在TSN網(wǎng)絡(luò)各交換機(jī)隊(duì)列確定的情況下減少大量流之間的碰撞，提高TSN網(wǎng)絡(luò)能調(diào)度的流數(shù)量，又可以在調(diào)度全部流的情況下減少交換機(jī)所需的隊(duì)列長(zhǎng)度，降低時(shí)延和抖動(dòng)。相對(duì)于802.1QBV，本發(fā)明支持的拓?fù)涓訌?fù)雜，流的數(shù)量更多，且計(jì)算更加簡(jiǎn)單，耗時(shí)更少。

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

本申請(qǐng)涉及通信技術(shù)領(lǐng)域，具體涉及一種用于時(shí)間敏感網(wǎng)絡(luò)數(shù)據(jù)確定性調(diào)度方法及裝置。

背景技術(shù)

時(shí)間敏感網(wǎng)絡(luò)(Time Sensitive Networking,TSN)是IEEE802.1工作組中的TSN任務(wù)組正在開發(fā)的一套協(xié)議標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)定義了以太網(wǎng)數(shù)據(jù)傳輸?shù)臅r(shí)間敏感機(jī)制，為標(biāo)準(zhǔn)以太網(wǎng)增加了確定性和可靠性，以確保以太網(wǎng)能夠?yàn)殛P(guān)鍵數(shù)據(jù)的傳輸提供穩(wěn)定一致的服務(wù)級(jí)別。

IEEE 802.1QBV協(xié)議提供了通過門控調(diào)度時(shí)間敏感流(簡(jiǎn)稱“流”)的方法，但是門控的計(jì)算方法復(fù)雜，與拓?fù)漶詈喜灰资褂茫⑶译S著拓?fù)鋸?fù)雜程度的提高和流數(shù)量的增加，算法復(fù)雜程度提高耗時(shí)大量增加，甚至計(jì)算不出有效解。為了簡(jiǎn)化TSN交換機(jī)的設(shè)計(jì)，在IEEE 802.1QCH中通過將固定配置分配給TAS，提出了一種基于乒乓隊(duì)列的模型，稱為循環(huán)排隊(duì)和轉(zhuǎn)發(fā)(CQF)。多個(gè)設(shè)備輸出到一個(gè)交換機(jī)，如果轉(zhuǎn)發(fā)時(shí)沒有規(guī)劃每條流的發(fā)送時(shí)間，則大量周期性的流容易收斂在一部分隊(duì)列中。由于隊(duì)列長(zhǎng)度有限，一旦隊(duì)列溢出，許多對(duì)時(shí)間敏感的數(shù)據(jù)包將被丟棄。因此通過規(guī)劃每條流的發(fā)送時(shí)間，給部分流的開始發(fā)送時(shí)間時(shí)隙注入(Injection Time Planning,ITP)，延遲這部分流的開始發(fā)送時(shí)間可以緩解這個(gè)問題，使全局隊(duì)列利用率更加平衡。

但是，如何進(jìn)行調(diào)度使調(diào)度的流數(shù)量盡可能多，或減少交換機(jī)的隊(duì)列長(zhǎng)度，以降低時(shí)延是需要解決的技術(shù)問題。

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

本申請(qǐng)實(shí)施例提供一種用于時(shí)間敏感網(wǎng)絡(luò)數(shù)據(jù)確定性調(diào)度方法及裝置，用以解決TSN網(wǎng)絡(luò)能調(diào)度的流數(shù)量少，交換機(jī)隊(duì)列長(zhǎng)度長(zhǎng)的技術(shù)問題。

本發(fā)明提供一種用于時(shí)間敏感網(wǎng)絡(luò)數(shù)據(jù)確定性調(diào)度方法，包括：

構(gòu)建時(shí)間敏感網(wǎng)絡(luò)模型，所述時(shí)間敏感網(wǎng)絡(luò)模型包括流子模型、交換機(jī)子模型、拓?fù)渥幽Ｐ停?/p>

基于局部搜索算法確定最優(yōu)解，所述最優(yōu)解包含每一流的發(fā)送時(shí)間；

根據(jù)每一流的發(fā)送時(shí)間對(duì)時(shí)間敏感網(wǎng)絡(luò)的數(shù)據(jù)流進(jìn)行調(diào)度。

在一些實(shí)施例中，基于局部搜索算法確定最優(yōu)解，所述最優(yōu)解包含每一流的發(fā)送時(shí)間，包括：

利用隨機(jī)函數(shù)生成初始解；

基于所述初始解進(jìn)行刪除操作和/或進(jìn)行插入操作，生成鄰居解；

基于所述鄰居解進(jìn)行迭代搜索，輸出最優(yōu)解。

在一些實(shí)施例中，基于所述初始解進(jìn)行刪除操作和/或進(jìn)行插入操作，生成鄰居解，包括：

將已成功映射流的集合中的部分流轉(zhuǎn)移到未映射流的集合中進(jìn)行刪除操作生成鄰居解，和/或，

將已成功映射流的集合中的部分流轉(zhuǎn)移到未映射流的集合中進(jìn)行插入操作生成鄰居解。

在一些實(shí)施例中，基于所述鄰居解進(jìn)行迭代搜索，輸出最優(yōu)解，包括：

根據(jù)所述鄰居解構(gòu)建鄰域；

從鄰域中選擇最優(yōu)解，作為下次迭代的當(dāng)前解，直至達(dá)到最大迭代次數(shù)或連續(xù)執(zhí)行一定次數(shù)的鄰域切換策略都不能更新最優(yōu)解時(shí)，終止迭代，輸出最優(yōu)解。