[發(fā)明專利]輪詢式分組排隊(duì)輸出調(diào)度方法及分組交換節(jié)點(diǎn)

有效

• 申請?zhí)枺?/td>: 200910143125.9
• 申請日: 2009-05-14
• 公開（公告）號: CN101557346A
• 公開（公告）日: 2009-10-14
• 發(fā)明（設(shè)計(jì)）人: 劉文波;郭云飛;程東年;傅敏;陳庶樵;劉勤讓;張建偉;馬海龍;李丹;趙博
• 申請（專利權(quán)）人: 中國人民解放軍信息工程大學(xué)
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司
• 代理人: 逯長明;王寶筠

1.一種輪詢式分組排隊(duì)輸出調(diào)度方法，其特征在于，包括：

預(yù)先處理步驟：構(gòu)建二維動態(tài)調(diào)度表，所述二維動態(tài)調(diào)度表包括多個(gè)列表，一輪數(shù)據(jù)發(fā)送對應(yīng)一個(gè)列表，不為空的列表中包括至少一個(gè)調(diào)度表項(xiàng)，每個(gè)調(diào)度表項(xiàng)都對應(yīng)一個(gè)分組流，一個(gè)調(diào)度表項(xiàng)用于提示在輪詢到所述調(diào)度表項(xiàng)所在的列表時(shí)發(fā)送所述調(diào)度表項(xiàng)對應(yīng)的分組流中需要最先被發(fā)送的一個(gè)數(shù)據(jù)包；

調(diào)度表處理步驟：在執(zhí)行預(yù)先處理步驟之后，對于任意一個(gè)分組流，當(dāng)所述分組流有數(shù)據(jù)包需要被發(fā)送時(shí)，以當(dāng)前輪數(shù)據(jù)發(fā)送為基礎(chǔ)，根據(jù)預(yù)先分配給所述分組流在每輪數(shù)據(jù)發(fā)送中對應(yīng)的發(fā)送份額及所述分組流中需要最先被發(fā)送的第一數(shù)據(jù)包的長度，確定第一數(shù)據(jù)包被發(fā)送的輪數(shù)，根據(jù)確定的輪數(shù)確定對應(yīng)的列表，并且，如果在確定的列表中沒有對應(yīng)所述分組流的調(diào)度表項(xiàng)，則在所述確定的列表中增加對應(yīng)所述分組流的調(diào)度表項(xiàng)，其中，所述分組流在每輪數(shù)據(jù)發(fā)送中對應(yīng)的發(fā)送份額為分組交換網(wǎng)絡(luò)中長度最短的數(shù)據(jù)包的長度與所述分組流對應(yīng)的權(quán)值的乘積，所述分組流對應(yīng)的權(quán)值為分配給所述分組流的帶寬與分配給所有的分組流的帶寬中的最小帶寬的比值；

其中，按照下述方式具體執(zhí)行調(diào)度表處理步驟：確定所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送中的最大數(shù)據(jù)發(fā)送量；

比較第一數(shù)據(jù)包的長度與所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送中的最大數(shù)據(jù)發(fā)送量；

如果第一數(shù)據(jù)包的長度不大于所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送中的最大數(shù)據(jù)發(fā)送量時(shí)，則確定第一數(shù)據(jù)包在當(dāng)前輪數(shù)據(jù)發(fā)送中被發(fā)送，確定當(dāng)前輪數(shù)據(jù)發(fā)送對應(yīng)的列表，并且，如果在當(dāng)前輪數(shù)據(jù)發(fā)送對應(yīng)的列表中沒有對應(yīng)所述分組流的調(diào)度表項(xiàng)，則在當(dāng)前輪數(shù)據(jù)發(fā)送對應(yīng)的列表中增加對應(yīng)所述分組流的調(diào)度表項(xiàng)；

如果第一數(shù)據(jù)包的長度大于所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送中的最大數(shù)據(jù)發(fā)送量，則確定在滿足不小于第一數(shù)據(jù)包的長度的條件下、所需的所述分組流在每輪數(shù)據(jù)發(fā)送中對應(yīng)的發(fā)送份額的數(shù)量，確定第一數(shù)據(jù)包被發(fā)送的輪數(shù)為所述確定的發(fā)送份額的數(shù)量，確定第一數(shù)據(jù)包被發(fā)送的輪數(shù)對應(yīng)的列表，并且，如果在第一數(shù)據(jù)包被發(fā)送的輪數(shù)對應(yīng)的列表中沒有對應(yīng)所述分組流的調(diào)度表項(xiàng)，則在第一數(shù)據(jù)包被發(fā)送的輪數(shù)對應(yīng)的列表中增加對應(yīng)所述分組流?的調(diào)度表項(xiàng)；

所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送中的最大數(shù)據(jù)發(fā)送量為所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送之前的一輪數(shù)據(jù)發(fā)送中的剩余數(shù)據(jù)發(fā)送量與所述分組流在每輪數(shù)據(jù)發(fā)送中對應(yīng)的發(fā)送份額之和，其中，所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送之前的一輪數(shù)據(jù)發(fā)送中的剩余數(shù)據(jù)發(fā)送量為所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送之前的一輪數(shù)據(jù)發(fā)送中的最大數(shù)據(jù)發(fā)送量與所述分組流在當(dāng)前輪數(shù)據(jù)發(fā)送之前的一輪數(shù)據(jù)發(fā)送中的實(shí)際數(shù)據(jù)發(fā)送量之差；

輪詢步驟：在執(zhí)行預(yù)先處理步驟之后，依次輪詢所述二維動態(tài)調(diào)度表的每個(gè)列表，其中，當(dāng)輪詢到任意一個(gè)列表中的任意一個(gè)調(diào)度表項(xiàng)時(shí)，發(fā)送所述調(diào)度表項(xiàng)對應(yīng)的分組流中需要最先被發(fā)送的一個(gè)數(shù)據(jù)包。

2.如權(quán)利要求1所述的方法，其特征在于，所述二維動態(tài)調(diào)度表包括的列表的數(shù)量為大于第一比值的整數(shù)，所述第一比值為分組交換網(wǎng)絡(luò)中最長的數(shù)據(jù)包的長度與最短的數(shù)據(jù)包的長度的比值。

3.如權(quán)利要求2所述的方法，其特征在于，所述二維動態(tài)調(diào)度表包括的列表的數(shù)量為大于第一比值的最小整數(shù)。

4.如權(quán)利要求1所述的方法，其特征在于，調(diào)度表處理步驟還包括：當(dāng)發(fā)送完第一數(shù)據(jù)包后，如果所述分組流還有數(shù)據(jù)包需要被發(fā)送，并且所述分組流在第一數(shù)據(jù)包被發(fā)送的輪數(shù)中的剩余數(shù)據(jù)發(fā)送量不小于所述分組流中需要最先被發(fā)送的第二數(shù)據(jù)包的長度，則在所述確定的列表中保留對應(yīng)所述分組流的調(diào)度表項(xiàng)；

按照下述方式執(zhí)行輪詢步驟：當(dāng)發(fā)送完第一數(shù)據(jù)包后，如果在所述確定的列表中在對應(yīng)所述分組流的調(diào)度表項(xiàng)之后還存在調(diào)度表項(xiàng)，則輪詢在對應(yīng)所述分組流的調(diào)度表項(xiàng)之后的調(diào)度表項(xiàng)，當(dāng)輪詢完所述確定的列表中的所有調(diào)度表項(xiàng)后，再從所述確定的列表中的第一個(gè)調(diào)度表項(xiàng)開始輪詢所述確定的列表中的每個(gè)調(diào)度表項(xiàng)，其中，當(dāng)輪詢到對應(yīng)所述分組流的調(diào)度表項(xiàng)時(shí)，發(fā)送第二數(shù)據(jù)包。