[發明專利]輪詢式分組排隊輸出調度方法及分組交換節點

有效

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

技術領域

本發明涉及分組交換技術，尤其涉及輪詢式分組排隊輸出調度技術。

背景技術

隨著互聯網的深入應用與發展，互聯網正逐步成為多種通訊設施統一的網絡傳輸平臺。人們希望各種業務均可由互聯網來承載，并以互聯網為基礎，最終實現數據、語音、圖像等不同業務的網絡融合。互聯網是一個分組交換網絡，分組交換與統計復用是其本質特征，互聯網的基本設計原則只要求了各個分組交換節點要盡力而為地進行分組數據轉發。隨著互聯網應用多樣性的增加，出現了多種不同的業務，例如數據文件傳輸業務和視頻交互業務，而不同的業務對網絡傳輸服務提出了不同的服務質量(QoS)要求。

對于不同的業務，網絡中的各個分組交換節點需要按照業務對網絡傳輸服務提出的服務質量要求進行處理。網絡中的各個分組交換節點進行分組交換的一個理論基礎和決策依據是分組排隊輸出調度理論。分組排隊輸出調度理論主要研究分組交換中統計復用的合理性和合理性保證機制等問題，即，解決在有多個分組流共享復用一個服務資源(端口或線路)的情況下，分組交換節點依據預定的資源分配比例、分組到達的時間、抖動范圍等事先規定的約束，在多個共享服務資源的分組流中選取一個最合適的分組流進行發送服務的問題。

適用于分組交換的分組排隊輸出調度方法主要分為兩類，一類是基于通用處理器共享(GPS，General?Processor?Sharing)時間標簽排序的分組排隊調度方法，另一類是基于幀的輪詢式分組排隊輸出調度方法。其中，基于GPS時間標簽排序的分組排隊調度方法的計算復雜度比較高，在共享服務資源的分組流的數量比較多的情況下，無法提供高速的輸出調度，不適用于大容量、高速的分組交換節點。基于幀的輪詢式分組排隊輸出調度方法的計算復雜度要比基于GPS時間標簽排序的分組排隊調度方法的計算復雜度低，適用于大容量、高速的分組交換節點。

但是，本發明的發明人在仔細研究基于幀的輪詢式分組排隊調度方法后發現，使用這種方法進行分組排隊輸出調度時，各個分組流之間的輸出延時較大，或者說，服務等待延時比較大。

發明內容

本發明提供輪詢式分組排隊輸出調度方法及分組交換節點，用以減少分組交換節點使用基于幀的輪詢式分組排隊調度方法進行分組排隊輸出調度過程中的服務等待延時。

本發明提供一種輪詢式分組排隊輸出調度方法，包括：預先處理步驟，構建二維動態調度表，所述二維動態調度表包括多個列表，一輪數據發送對應一個列表，不為空的列表中包括至少一個調度表項，每個調度表項都對應一個分組流，一個調度表項用于提示在輪詢到所述調度表項所在的列表時發送所述調度表項對應的分組流中需要最先被發送的數據包；調度表處理步驟，在執行預先處理步驟之后，對于任意一個分組流，當所述分組流有數據包需要被發送時，以當前輪數據發送為基礎，根據預先分配給所述分組流在每輪數據發送中對應的發送份額及所述分組流中需要最先被發送的第一數據包的長度，確定第一數據包被發送的輪數，根據確定的輪數確定對應的列表，并且，如果在確定的列表中沒有對應所述分組流的調度表項，則在所述確定的列表中增加對應所述分組流的調度表項，其中，所述分組流在每輪數據發送中對應的發送份額為分組交換網絡中長度最短的數據包的長度與所述分組流對應的權值的乘積；輪詢步驟，在執行預先處理步驟之后，依次輪詢所述二維動態調度表的每個列表，其中，當輪詢到任意一個列表中的任意一個調度表項時，發送所述調度表項對應的分組流中需要最先被發送的數據包。