[發(fā)明專利]一種用于輸入隊(duì)列交換機(jī)的混合隊(duì)列架構(gòu)的混合調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910200066.8
• 申請(qǐng)日: 2019-03-15
• 公開（公告）號(hào): CN110011934B
• 公開（公告）日: 2020-09-15
• 發(fā)明（設(shè)計(jì)）人: 黃煬;胡冰
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)
• 主分類號(hào): H04L12/861
• 分類號(hào): H04L12/861;H04L12/863;H04L12/911;H04L12/931;H04L12/935
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 林超

1.一種用于輸入隊(duì)列交換機(jī)的混合隊(duì)列架構(gòu)的混合調(diào)度方法，其特征在于：方法采用輸入隊(duì)列交換機(jī)，輸入隊(duì)列交換機(jī)包括輸入端口（205）和輸出端口，輸入端口（205）作為交換結(jié)構(gòu)的輸入，輸出端口作為交換結(jié)構(gòu)的輸出，輸入端口（205）和輸出端口之間經(jīng)交換結(jié)構(gòu)進(jìn)行數(shù)據(jù)分組的傳輸，輸入端口（205）和交換結(jié)構(gòu)均連接中心調(diào)度器（206），由中心調(diào)度器（206）對(duì)輸入到輸入端口的數(shù)據(jù)分組進(jìn)行調(diào)度并對(duì)交換機(jī)的交換結(jié)構(gòu)進(jìn)行配置；輸入隊(duì)列交換機(jī)中，緩存位于各個(gè)輸入端口，每一個(gè)輸入端口中建立兩類虛擬輸出隊(duì)列，分別為端口虛擬輸出隊(duì)列(portQ，PortVOQ)和流虛擬輸出隊(duì)列(flowQ，F(xiàn)lowVOQ)，構(gòu)成了混合隊(duì)列架構(gòu)；對(duì)于每一個(gè)輸入端口，新到達(dá)輸入端口的數(shù)據(jù)分組經(jīng)過濾器（201）被分配至端口虛擬輸出隊(duì)列portQ（202）或流虛擬輸出隊(duì)列flowQ（203）中，由中心調(diào)度器（206）采用整合幀預(yù)留和基于時(shí)隙的混合調(diào)度方法進(jìn)行調(diào)度；

所述的整合幀預(yù)留和基于時(shí)隙的混合調(diào)度方法，具體分為端口預(yù)匹配和端口重匹配兩個(gè)階段：

在端口預(yù)匹配階段，中心調(diào)度器通過網(wǎng)絡(luò)控制協(xié)議（例如rsvp協(xié)議）實(shí)時(shí)傳輸獲取到確定性業(yè)務(wù)的帶寬資源預(yù)留信息，中心調(diào)度器根據(jù)確定性業(yè)務(wù)的帶寬資源預(yù)留信息，依次采用基于幀的矩陣拆解算法和基于通用處理器共享理論的流調(diào)度算法，預(yù)先獲得當(dāng)前一時(shí)間幀內(nèi)每個(gè)時(shí)隙預(yù)留帶寬資源的流虛擬輸出隊(duì)列flowQ（203）以及每個(gè)時(shí)隙下預(yù)留的流虛擬輸出隊(duì)列flowQ（203）對(duì)應(yīng)的輸入端口和輸出端口組成的端口對(duì)匹配方式，作為預(yù)匹配結(jié)果；

在端口重匹配階段，針對(duì)每一個(gè)時(shí)隙，中心調(diào)度器根據(jù)預(yù)匹配結(jié)果以及各個(gè)流虛擬輸出隊(duì)列flowQ（203）和端口虛擬輸出隊(duì)列portQ（202）的實(shí)時(shí)隊(duì)列狀態(tài)，保留當(dāng)前時(shí)隙下預(yù)留帶寬資源的且非空的流虛擬輸出隊(duì)列flowQ（203）所對(duì)應(yīng)的預(yù)匹配結(jié)果，并采用基于時(shí)隙迭代的調(diào)度方式將所有預(yù)留帶寬資源但未被使用的帶寬資源或者未預(yù)留的帶寬資源共享至所有的非空的端口虛擬輸出隊(duì)列portQ（202）。

2.根據(jù)權(quán)利要求1所述的一種用于輸入隊(duì)列交換機(jī)的混合隊(duì)列架構(gòu)的混合調(diào)度方法，其特征在于：每一個(gè)輸入端口采用單級(jí)的隊(duì)列結(jié)構(gòu)，被劃分為兩個(gè)虛擬輸出隊(duì)列集合，分別包括：

端口虛擬輸出隊(duì)列集合，分為N個(gè)獨(dú)立的端口虛擬輸出隊(duì)列portQ（202），每個(gè)端口虛擬輸出隊(duì)列portQ（202）存儲(chǔ)當(dāng)前輸入端口到同一個(gè)輸出端口的所有非確定性業(yè)務(wù)的數(shù)據(jù)分組；

流虛擬輸出隊(duì)列集合，分為M個(gè)獨(dú)立的流虛擬輸出隊(duì)列flowQ（203），每個(gè)流虛擬輸出隊(duì)列flowQ（203）存儲(chǔ)一條確定性業(yè)務(wù)流的數(shù)據(jù)分組。

3.根據(jù)權(quán)利要求1所述的一種用于輸入隊(duì)列交換機(jī)的混合隊(duì)列架構(gòu)的混合調(diào)度方法，其特征在于：所述的端口預(yù)匹配階段中，只有當(dāng)確定性業(yè)務(wù)的帶寬資源預(yù)留信息或者交換機(jī)的總帶寬資源發(fā)生變化時(shí)，才進(jìn)入端口預(yù)匹配階段；同時(shí)，中心調(diào)度器（206）不根據(jù)端口預(yù)匹配階段的預(yù)匹配結(jié)果進(jìn)行交換機(jī)的交換結(jié)構(gòu)配置，而是將預(yù)匹配結(jié)果用于作為端口重匹配階段的輸入信息。

4.根據(jù)權(quán)利要求1所述的一種用于輸入隊(duì)列交換機(jī)的混合隊(duì)列架構(gòu)的混合調(diào)度方法，其特征在于：所述的端口重匹配階段中，在每一個(gè)時(shí)隙均進(jìn)入端口重匹配階段，當(dāng)前時(shí)隙開始時(shí)進(jìn)行以下判斷：

若該時(shí)隙下，預(yù)留帶寬資源的流虛擬輸出隊(duì)列flowQ（203）非空，則將該流虛擬輸出隊(duì)列flowQ（203）對(duì)應(yīng)的預(yù)匹配結(jié)果保留；

若該時(shí)隙下，預(yù)留帶寬資源的流虛擬輸出隊(duì)列flowQ（203）為空且對(duì)應(yīng)的預(yù)留結(jié)果作為預(yù)留但未被使用的帶寬資源，或者存在未預(yù)留的帶寬資源，則采用基于時(shí)隙迭代的調(diào)度方式，將上述預(yù)留但未被使用或者未預(yù)留的帶寬資源共享至所有的非空的端口虛擬輸出隊(duì)列portQ（202）使用，即分配給所有的非空的端口虛擬輸出隊(duì)列portQ（202）使用；

具體如下：

在端口重匹配階段中，中心調(diào)度器為每個(gè)輸入端口和每個(gè)輸出端口分別維護(hù)一個(gè)輪詢指針，采用多次迭代的方式進(jìn)行輸入端口和輸出端口之間的匹配，每次的迭代包括：

S1、請(qǐng)求階段：

如果當(dāng)前為第一次迭代，則進(jìn)行以下處理：

如果當(dāng)前時(shí)隙內(nèi)，輸入端口中預(yù)留的流虛擬輸出隊(duì)列flowQ（203）為非空，則向該流虛擬輸出隊(duì)列flowQ對(duì)應(yīng)的輸出端口發(fā)送預(yù)留請(qǐng)求；

如果當(dāng)前時(shí)隙內(nèi)，輸入端口中預(yù)留的流虛擬輸出隊(duì)列flowQ（203）為空或者輸入端口沒有預(yù)留的流虛擬輸出隊(duì)列flowQ（203），則向所有非空的端口虛擬輸出隊(duì)列portQ（202）對(duì)應(yīng)的輸出端口發(fā)送非預(yù)留請(qǐng)求；

如果當(dāng)前不為第一次迭代，則進(jìn)行以下處理：

如果當(dāng)前時(shí)隙內(nèi)，輸入端口已經(jīng)在該時(shí)隙的前幾次迭代的接受階段接受了輸出端口，則跳過請(qǐng)求階段，不發(fā)送任何的預(yù)留請(qǐng)求或非預(yù)留請(qǐng)求；

如果當(dāng)前時(shí)隙內(nèi)，輸入端口沒有在該時(shí)隙的前幾次迭代的接受階段接個(gè)輸出端口且輸入端口中預(yù)留的流虛擬輸出隊(duì)列flowQ（203）為空或者輸入端口沒有預(yù)留的流虛擬輸出隊(duì)列flowQ（203），則向所有非空的端口虛擬輸出隊(duì)列portQ（202）對(duì)應(yīng)的輸出端口發(fā)送非預(yù)留請(qǐng)求；

S2、授權(quán)階段：

如果當(dāng)前為第一次迭代，則進(jìn)行以下處理：

如果輸出端口收到預(yù)留請(qǐng)求，則直接授權(quán)該預(yù)留請(qǐng)求，然后發(fā)回授權(quán)請(qǐng)求；

如果輸出端口收到了來自一個(gè)或多個(gè)輸入端口的非預(yù)留請(qǐng)求，則從輪詢指針的最高優(yōu)先級(jí)開始輪詢，選擇輪詢到的第一個(gè)發(fā)送了非預(yù)留請(qǐng)求的輸入端口，輸出端口授權(quán)被選擇的輸入端口發(fā)過來的預(yù)留請(qǐng)求，向該輸入端口發(fā)送授權(quán)請(qǐng)求；

如果當(dāng)前不是第一次迭代，則進(jìn)行以下處理：

如果輸出端口已經(jīng)在該時(shí)隙的前幾次迭代的接受階段被輸入端口所接受，則跳過授權(quán)階段，不發(fā)送任何的授權(quán)請(qǐng)求；

如果輸出端口沒有在該時(shí)隙的前幾次迭代的接受階段被輸入端口所接受，且收到了來自一個(gè)或多個(gè)輸入端口的非預(yù)留請(qǐng)求，則從輪詢指針的最高優(yōu)先級(jí)開始輪詢，選擇輪詢到的第一個(gè)發(fā)送了非預(yù)留請(qǐng)求的輸入端口，輸出端口授權(quán)被選擇的輸入端口發(fā)過來的預(yù)留請(qǐng)求，向該輸入端口發(fā)送授權(quán)請(qǐng)求；

S3、接受階段：

如果當(dāng)前時(shí)隙內(nèi)，輸入端口中預(yù)留的流虛擬輸出隊(duì)列flowQ（203）為非空，則直接接受向該流虛擬輸出隊(duì)列flowQ對(duì)應(yīng)的輸出端口，并向該輸出端口發(fā)送接受請(qǐng)求；

如果當(dāng)前時(shí)隙內(nèi)，輸入端口中預(yù)留的流虛擬輸出隊(duì)列flowQ（203）為空且收到了多個(gè)授權(quán)請(qǐng)求，則從輪詢指針的最高優(yōu)先級(jí)開始輪詢，選擇輪詢到的第一個(gè)發(fā)送了授權(quán)請(qǐng)求的輸出端口，輸入端口接受該輸出端口并向其發(fā)送接受請(qǐng)求，同時(shí)將輪詢指針的最高優(yōu)先級(jí)更新為被接受的輸出端口的下一個(gè)端口；

由此一次迭代完成；

重匹配階段歷經(jīng)多次同樣的迭代，中心調(diào)度器（206）根據(jù)重匹配階段的結(jié)果進(jìn)行交換機(jī)的交換結(jié)構(gòu)配置。