[發明專利]隊列索引方法及裝置和流量整形的方法及裝置

有效

• 申請號: 200810080989.6
• 申請日: 2008-02-29
• 公開（公告）號: CN101237417A
• 公開（公告）日: 2008-08-06
• 發明（設計）人: 鄭勤;卞云峰;崔靖杰;施雪峰;程柏
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京中博世達專利商標代理有限公司
• 代理人: 申健

技術領域

本發明涉及通信技術領域，尤其涉及一種隊列索引方法及裝置和流量整形的方法及裝置。

背景技術

隨著用戶數量的快速增長，在有限的網絡帶寬下對用戶隊列進行流量控制時，通常采用多層次隊列組的索引技術。利用隊列索引技術的流量整形是一種常見的流量控制方式。

現有技術中對用戶隊列進行索引的方法通常有兩種，一種是串行索引的方法，另一種是并行索引的方法。下面分別介紹兩種方法的實現過程。

根據用戶隊列的容量和用戶需求，可以將用戶隊列歸屬為不同級數的隊列組進行索引，在此，以用戶隊列屬于四級隊列組的情況為例進行說明。在對用戶隊列進行索引之前，首先為每級隊列組配置隊列組號索引表，每一級的隊列組號索引表中包括屬于該級隊列的隊列組號。

串行索引采用逐級收斂的方式對用戶隊列進行索引，其原理如圖1所示，該方法每完成一級隊列組的索引后，利用獲得的結果查找下一級隊列組號索引表，找到下一級隊列組號。具體方法如下：首先用隊列號通過查找第一級隊列組號索引表找到用戶隊列所屬的第一級隊列組號；再利用該第一級隊列組號查找第二級隊列組號索引表，找到用戶隊列所屬的第二級隊列組號；然后利用該第二級隊列組號查找第三級隊列組號索引表，找到用戶隊列所屬的第三級隊列組號，用同樣的方法，最后獲得用戶隊列所屬的第四級隊列組號。

并行索引采用直接索引的方式一次獲得用戶隊列所屬四級的隊列組號，其原理如圖2所示，具體方法如下：對四級隊列組中的每一個隊列都分配一個存儲空間，該存儲空間中存儲了該四級隊列組中每一級隊列組的隊列組號索引表。進行并行索引時，利用隊列號在該存儲空間中同時查詢該四級隊列組號索引表，一次直接獲得隊列所屬四級的隊列組號。

在實現本發明的過程中，發明人發現現有技術中至少存在如下問題：

串行索引的方法采取逐級索引的方式，每一級的隊列組索引需要一個時鐘周期，完成四級隊列組的索引至少需要四個時鐘周期，索引速度低，周期長。利用該方法對四級隊列組進行流量整形時，進行一次四級隊列組索引和流量整形至少需要五個時鐘周期，導致流量整形速度下降或延時過大，降低了高帶寬條件下的包處理速度。

并行索引的方法需要對每一個隊列都分配一個存儲空間，該存儲空間需要存儲每一級的隊列組號索引表，占用了大量的存儲器資源。當對大規模隊列組進行索引時，該方法資源消耗大。因而，利用該方法對用戶隊列進行流量整形時，需要消耗大量的存儲器資源。

發明內容

一方面，本發明實施例提供了一種靈活快速、節省資源的隊列索引裝置。

本發明實施例采用的技術方案如下：一種隊列索引裝置，該裝置包括：

第一存儲單元，用于存儲一級隊列組號索引表，所述一級隊列組號索引表包括第二級隊列組號索引表；

第二存儲單元，用于存儲二級隊列組號索引表，所述二級隊列組號索引表中至少包括第三級隊列組號索引表和第四級隊列組號索引表；

第一隊列組號獲得單元，用于根據第一級隊列組號查詢所述一級隊列組號索引表，獲得第二級隊列組號；

第二隊列組號獲得單元，用于根據所述第二級隊列組號查詢所述二級隊列組號索引表，同時獲得至少兩級隊列組號。

本發明實施例提供的隊列索引裝置通過第一存儲單元和第二存儲單元設置了隊列組號索引表，其中，第一存儲單元，存儲了一級隊列組號索引表，所述一級隊列組號索引表包括第二級隊列組號索引表；第二存儲單元，存儲了二級隊列組號索引表，所述二級隊列組號索引表中至少包括第三級隊列組號索引表和第四級隊列組號索引表，但至多也不會包括所有級數的隊列組號索引表。根據該隊列組號索引表，通過第一隊列組號獲得單元，利用串行索引的方法逐級獲得隊列組號；通過第二隊列組號獲得單元，利用并行索引的方法一次直接獲得至少兩級隊列組號。

本發明實施例提供的隊列索引裝置不需要給每一個隊列都配置一個包括了所有多級隊列組號的存儲空間，而且在一次的索引過程中能夠同時獲得多級隊列組號。本發明實施例利提供的隊列索引裝置通過第一、二存儲單元和第一、二隊列組號獲得單元采用串并行混合索引的方法進行隊列索引，能夠在節省資源的同時靈活快速地進行隊列索引。

另一方面，本發明實施例提供了一種靈活快速、節省資源的隊列索引方法。

本發明實施例采用的技術方案如下：一種隊列索引方法，該方法包括：

根據第一級隊列組號查詢一級隊列組號索引表，獲得第二級隊列組號，所述一級隊列組號索引表包括第二級隊列組號索引表；