518851 A7 B7 五 經濟部智慧財產局員工消費合作社印製 發明説明（1 ) 曼明背景· (請先閱讀背面之注意事項再填寫本頁) 本發明關於通訊，更具體地關於封包交換資料網路中 的封包拋棄。 在封包交換資料網路中，數位化資料的封包由原始點 傳送至目的地.，常基於原始點與目的地間不同網路鏈路的 容量及可用性而以不同的路由行之。資料經由鏈路而傳送 ’其連接實體地及邏輯地遍佈網路之網路節點，例如路由 器。資料可行經源自一節點的不同鏈路而傳送。 節點對於其可傳送的大量資料具有容量限制，而暫時 儲存以待傳送。當過量資料（以任一數量及尺寸之封包相 結合）匯入節點而超過該節點的容量（頻帶寬及/或緩衝 器空間）時，封包可予以拋棄或由節點儲存，以將送出該 節點的資料量降低至該特定節點的容量內。將拋棄之封包 可由不同的方式決定，包括選擇最長的佇列。 在完成封包網路的最長佇列拋棄（LQD)策略中，系統 內最長佇列的本體可由系統內的不同點判斷。執行該功能 所需的時間是系統內一緩衝器處理速度的限制因素。通常 一集合中最長佇列的決定是由進行排序功能之優先佇列（ 或堆積）來執行。然而優先佇列的實施傾向於需要〇（ l〇g2N)作業（例如算術（加、減等））邏輯（例如比較） ，或資料結構運用（例如記憶體存取）而在優先佇列中執 行插入、刪除或修改內容的功能，以判斷最長佇列。換言 之，優先佇列的實施隨著元素N的數量而線性增加所需的 時間。一般而言，記憶體存取在性能上有最大的影響。 -4 - 本紙張尺度適用中國國家標準（CNS ) A4規格（210X 297公釐） 518851 Μ Β7 經濟部智慧財產局員工消費合作社印製 五、發明説明（2 ) 發明槪述 本發明的具體實施例提供自許多資料佇列中拋棄較長 資料佇列的技術。佇列依據其長度而存入各種類及群組中 。種類可具有相同或不同的尺寸或尺寸範圍，例如相同百 分比的尺寸範圍。例如，每一種類的尺寸可從一特定尺寸 (例如64千位元組（Kbyte ))至該尺寸的兩倍（例如128 千位元組（Kbyte ))。在每一種類或群組中，佇列是或不 是依據尺寸進行儲存。當超出節點容量而一佇列將被拋棄 時，便選取與非空之最大範圍佇列相關的群組，並自該群 組拋棄一佇列。所拋棄的佇列是或不是群組內的最大佇列 。可以各種方式自所選取的種類挑選佇列，例如隨機或群 組中首先列出的佇列（例如位於儲存堆疊的頂部）。群組' 的尺寸範圍可予以變化，以降低群組中所拋棄之佇列與實 際最長佇列間可能的尺寸差異。即，群組的範圍規定在一 特定群組中最小的可能佇列是在該特定群組中最大的可能 佇列之預定的尺寸差異內，而該範圍可加以選擇/指定以 便將該預定的尺寸差異降至可接受的程度。 一般而言，在一觀點中，本發明提供一種傳送包封資 料的裝置，該裝置包括一接收包封資料的輸入；一記憶體 ，其連接該輸入並加以裝配以將包封資料儲存於佇列中， 其中每一佇列具有相關的尺寸；一傳輸連接該記憶體之包 封資料的輸出；及一控制器，其有效地連接該記憶體並加 以裝配以控制自該記憶體至該輸出之包封資料的傳輸，該 本紙張尺度適用中國國家標準（CNS ) Α4規格（210Χ297公釐） (請先閱讀背面之注意事項再填寫本貢」 Φ -5- 518851 A7 五、發明説明（3 ) 控制器進行裝配以判斷多個佇列尺寸範圍中，哪一個具有 最大的佇列尺寸範圍及至少一相關的佇列，並自至少一相 關的佇列中拋棄所選擇佇列的包封資料。 本發明的實施可包括一或多項下列特性。該控制器加 以裝配以藉由解除儲存包封資料之記憶體部分的配置而拋 棄包封資料。該控制器加以裝配以藉由重新配置儲存包封 資料之記憶體部分而拋棄包封資料。該控制器進一步加以 裝配以判斷是否超過節點的容量，而且其中該控制器加以 裝配以判斷複數個佇列尺寸範圍中，哪一個具有最大的佇 列尺寸範圍及至少一相關的佇列，以因應超過節點容量的 判斷。該控制器加以裝配而選擇佇列，如此一來相對於具 有所選擇ί宁列之相同尺寸範圍內尺寸的其他丨宁列的尺寸， 可與所選擇之佇列尺寸無關地拋棄資料。該控制器包括一 處理器’其加以裝配以執行軟體指令。該控制器包括硬體 ，可加以裝配而無關乎軟體指令地作業。 一般而言，在另一觀點中，本發明提供一種傳送包封 資料的系統，該裝置包括一接收包封資料的輸入；一記憶 體，其連接該輸入並加以裝配以將包封資料儲存於仔列中 ’其中每一佇列具有相關的尺寸；一傳輸連接該記憶體之 包封資料的輸出；及一控制裝置，其有效地連接該記憶體 以便自與特定佇列尺寸範圍相關之特定佇列中拋棄至少一 個資料封包，該特定佇列尺寸範圍大於任何其他具有至少 一相關佇列的佇列尺寸範圍。 本發明的實施可包括一或多項下列特性。該控制裝置 本紙張尺度適用中國國家標準（CNS ) A4規格（210X 297公釐） (請先閲讀背面之注意事項再填寫本頁) 訂_L-- 經濟部智慧財產局員工消費合作社印製 * ·111 ml mi emma 0 -6 - 518851 A7 ___B7 五、發明説明（4 ) (請先閲讀背面之注意事項再填寫本頁) 相對於與特定佇列尺寸範圍相關之任何其他佇列的尺寸， 可與該特定佇列尺寸無關地拋棄至少一個資料封包。該控 制裝置解除儲存遭拋棄之至少一個封包的記憶體部分配置 °該&制裝置重新配置儲存遭拋棄之至少一個封包的記憶 體部分。 一般而言，在另一觀點中，本發明提供一種方法，包 括將包封資料的佇列及該佇列尺寸的指標儲存於一網路節 點中’以便自該網路節點傳輸；判斷複數個佇列尺寸範圍 中’哪一個具有最大的佇列尺寸範圍及至少一個相關佇列 ;以及自該至少一個相關佇列中拋棄一所選擇佇列的包封 資料。 本發明的實施可包括一或多項下列特性。該拋棄包括 解除儲存該包封資料的記憶體配置。該拋棄包括重新配置 儲存該包封資料的記憶體。該方法可進一步包括判斷是否 超過節點容量，其中進行複數個佇列尺寸範圍中哪一個具 有最大的佇列尺寸範圍及至少一個相關佇列的判斷，以因 應超過節點容量的判斷。 經濟部智慧財產局員工消費合作社印製 一般而言，在另一觀點中，本發明提供一種傳輸資料 封包之網路節點中的資料流方法，該方法包括儲存該網路 節點中包封資料的佇列及該佇列尺寸的指標，以便自該網 路節點傳輸，相關的包封資料佇列具有儲存桶，其中具有 與該儲存桶相關之佇列的尺寸範圍；判斷哪一儲存桶至少 部分儲滿，並相對於任何其他至少部分儲滿的儲存桶而具 有最大的相關佇列尺寸範圍；自所判斷的儲存桶選擇依佇 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐） 518851 A7 B7 五、發明説明（5 ) 列；以及自所選擇的佇列拋棄包封資料。 (請先閲讀背面之注意事項再填寫本頁) 本發明的實施可包括一或多項下列特性。該拋棄包括 解除儲存該包封資料的記憶體配置。該方法可進一步包括 判斷是否超過節點傳輸包封資料的容量，其中進行哪一儲 存桶至少部分儲滿並相對於任何其他至少部分儲滿的儲存 桶而具有最大的相關佇列尺寸範圍的判斷，以因應超過節 點容量的判斷。 本發明的各項具體實施例可提供一或多項下列優點。 佇列可進行選擇，以便以少數（例如一項）作業便可判斷 將拋棄的佇列。佇列可進行選擇，以便拋棄至少最大佇列 的特定範圍內者。所拋棄佇列及最大實際佇列間的潛在尺 寸差異可加以選擇及/或調整。可選擇相當長但可能不是 最長的佇列，而以較拋棄最長佇列之保證選擇爲少的硬體 作業進行拋棄。佇列可進行選擇，以便儘管佇列的數量及 尺寸有異，卻仍以相當固定的時間量進行拋棄。 經由下列附圖、說明及申請專利範圍，該些及其他優 點以及發明本身將更加顯而易見。 經濟部智慧財產局B (工消費合作社印製 圖式簡述 圖1爲包括節點及節點鏈路的網路方塊圖。 圖2爲圖1所示網路中一節點的方塊圖。 圖3爲佇列儲存桶系統方塊圖。 圖4爲拋棄佇列的步驟方塊流程圖。 -8- 本紙張尺度適用中國國家標準（CNS ) A4規格（2丨〇X 297公釐） M8851 A7 B7 明説明（6 $要元件對照表 10 通訊系統 ^1-125 個人電腦 14 網路 1 6 卜 16 8 .網路節點 18 緩衝器 20 卜 2〇7 ί宁列 22 處理器 24〇-24η-ι 儲存桶 26 輸入線 28 輸入璋 30 輸出線 3 2 輸出埠 較具體實施例的詳細說明 (請先閲讀背面之注意事項再填寫本頁} 經濟部智慧財產局員工消費合作社印製 本發明提供選擇相當長資料佇列以便在封包交換網路 節點傳輸之線路的佇列間進行拋棄的技術。 參閱圖1，通訊系統10包括個人電腦12!-125及包括網 路節點16ι-168的網路14。電腦12如所示地經由諸如數據 機等適當裝備及適當軟體連接至節點16:及167。連接節點 1 6的鏈路1 8加以裝配以進行雙向通訊。節點16爲經由網 路14傳輸的路由器，例如知名的網際網路等全球封包交換 資料網路。節點16加以裝配以接收封包，並將其傳送至鄰 近節點16，例如，如同路由節點1 6所決定的，或在該節點 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐） -9- 518851 A7 B7 五、發明説明（7 ) 本身以內。節點1 6亦加以裝配以便在將封包傳輸至鄰近節 點1 6之前，對匯入封包提供適當的緩衝。節點1 6具有多 種緩衝及傳輸裝置的版本，如此資料可進行內部緩衝及傳 輸’而內部緩衝及傳輸可能造成擁塞，恰如資料緩衝器及 外部傳輸器在外部所造成的。節點1 6亦可能爲封包的原始 點及/或目的地。 參閱圖2，一範例的節點1 6 (此處爲節點1 6 4 )包括節 點緩衝器1 8，其加以裝配以儲存及傳輸資料封包的佇列2〇 。緩衝器1 8包括用於儲存資料的記憶體，其在處理器22 的控制下執行軟體。雖然節點1 6間的其他接點是可接受的 ，但如圖1中所示的，緩衝器18連接節點16!，163及167 ，以於其間接收及傳輸資料封包。封包於輸入埠28處經由 輸入線2 6而接收，並經由輸出線3 0自輸出璋3 2發送。資 料封包儲存於佇列20 (此處顯示爲佇列20!-207)，以便自 緩衝器1 8傳輸出去。 資料封包可以不同的順序傳輸出佇列20。例如，封包 可以Q!至Q7的佇列順序，依據配置予每一佇列20的頻帶 寬的量（每一佇列20的量可以不同）平行地傳輸。封包亦 可以若干技術的結合而傳輸，例如佇列2(^-203依數字的順 序傳輸，而且佇列2〇4-2〇7亦依數字的順序傳輸，但佇列 20i - 2(h之群組的封包則可依據所配置予各群組之頻帶寬而 平行地與佇列2〇4-2〇7之群組的封包一同傳輸。 緩衝器1 8及處理器22加以裝配而執行近乎最長佇列 拋棄（LQD )策略。較佳地，緩衝器的數字空間是固定的， 本紙張尺度適用中國國家標準（CNS ) A4規格（210X29?公釐） f請先閱讀背面之注意事項再填寫本頁) 訂 經濟部智慧財產局員工消費合作社印製 518851 經濟部智慧財產局員工消費合作社印製 A7 B7 五、發明説明（8 ) 如此一來對緩衝器記憶體而言則是有限的尺寸，僅小的正 整數可由緩衝器18及處理器22儲存。處理器22加以裝配 以依據軟體碼作業而控制緩衝器1 8，執行不同的功能而完 成近乎最長佇列拋棄（LQD )策略。 量是有限的，藉此當進行修改，一元素（佇列）的値 (尺寸）可以改變。一次自一丨宁列加入及移除一個封包， 因而一元素的値將僅由一封包的最大尺寸增加或減少。同 時，一「幾乎正確」的答案假設是可接受的。已顯示的是 甚至一尋找最長佇列的粗糙近似値便具有極好的性能。佇 列20以有限的尺寸範圍插入緩衝器18或自其移除。當佇 列20是空的時便進入系統而具有一封包，當其不具封包時 便自系統移除。所以一新插入的佇列20將具有大於〇並小 於或等於最大封包尺寸的尺寸，而一將被移除之佇列20將 具有0的尺寸。 緩衝器18加以裝配而以一系列相對於不同長度之佇列 的「儲存桶」結合佇列20。雖然可想像佇列20是儲存於儲 存桶中，但佇列20實體上不需儲存在一起。與其說儲存桶 是實體的不如說其是邏輯的群組。例如，儲存桶可以指示 物、連接表或其他表示佇列20屬於哪一儲存桶的指標來實 施。 參閱圖3，雖然僅顯示三個儲存桶24。-2心，但緩衝器 18包括η個儲存桶26-24^。與儲存桶24相關之佇列20的 最大尺寸以函數S表示，其中^表示將置於儲存桶24i中的 最大尺寸佇列。儲存桶^將包括長度〇位元組至S。位元組 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐） -11 - (請先閱讀背面之注意事項再填寫本頁)518851 A7 B7 Five Inventions printed by the Intellectual Property Bureau of the Ministry of Economic Affairs, Consumer Consumption Cooperatives (1) Man Ming Background · (Please read the notes on the back before filling out this page) This invention is about communication, and more specifically about packet exchange data networks The packets in are discarded. In a packet-switched data network, packets of digitized data are transmitted from the original point to the destination. They are often performed in different routes based on the capacity and availability of different network links between the original point and the destination. Data is transmitted via a link ’which connects network nodes, such as routers, physically and logically throughout the network. Data may be transmitted over different links originating from a node. A node has a capacity limit for the large amount of data it can transmit, and temporarily stores it for transmission. When excess data (combined with any number and size of packets) is imported into a node and exceeds the capacity (frequency bandwidth and / or buffer space) of the node, the packets can be discarded or stored by the node to be sent out of the node The amount of data is reduced to the capacity of that particular node. The packets to be discarded can be determined in different ways, including choosing the longest queue. In completing the longest queue discard (LQD) strategy of the packet network, the longest queue in the system can be judged by different points in the system. The time required to perform this function is a limiting factor in the processing speed of a buffer in the system. Usually the decision of the longest queue in a set is performed by the priority queue (or stack) that performs the sort function. However, the implementation of the priority queue tends to require 0 (10g2N) operations (such as arithmetic (addition, subtraction, etc.)) logic (such as comparison), or the use of data structures (such as memory access) to execute in the priority queue The ability to insert, delete, or modify content to determine the longest queue. In other words, the time required for the implementation of the priority queue to increase linearly with the number of elements N. In general, memory access has the biggest impact on performance. -4-This paper size applies Chinese National Standard (CNS) A4 (210X 297mm) 518851 Μ B7 Printed by the Consumer Cooperatives of the Intellectual Property Bureau of the Ministry of Economic Affairs 5. Description of the invention (2) Inventions describe specific embodiments of the present invention Provides techniques to abandon longer data queues from many data queues. Queues are stored in various classes and groups based on their length. The species may have the same or different sizes or size ranges, such as the same percentage size range. For example, the size of each category can range from a specific size (such as 64 kilobytes (Kbytes)) to twice the size (such as 128 kilobytes (Kbytes)). Within each category or group, queues are stored based on size or not. When a queue is discarded beyond the node capacity, a group related to the non-empty maximum range queue is selected, and a queue is discarded from the group. The queue that is discarded is or is not the largest queue in the group. Queues can be selected from the chosen category in a variety of ways, such as random or the first queue listed in a group (for example, at the top of a storage stack). The size range of the group can be changed to reduce the possible size difference between the queues abandoned in the group and the actual longest queue. That is, the range of a group specifies that the smallest possible queue in a particular group is within a predetermined size difference of the largest possible queue in that particular group, and the range can be selected / designated to make the predetermined The dimensional difference is reduced to an acceptable level. Generally speaking, in one aspect, the present invention provides a device for transmitting encapsulated data. The device includes an input for receiving the encapsulated data, and a memory connected to the input and assembled to store the encapsulated data in the frame. In a row, each of which has an associated size; an output that transmits the encapsulation data connected to the memory; and a controller that effectively connects the memory and assembles it to control the output from the memory to the output For the transmission of encapsulated data, this paper size is applicable to the Chinese National Standard (CNS) A4 specification (210 × 297 mm) (Please read the precautions on the back before filling in this tribute "Φ -5- 518851 A7 V. Description of the invention (3 The controller assembles to determine which of the multiple queue size ranges has the largest queue size range and at least one related queue, and discards the encapsulation data of the selected queue from the at least one related queue. The implementation of the present invention may include one or more of the following features. The controller is assembled to discard the encapsulated data by de-allocating the configuration of the memory portion storing the encapsulated data. The controller The controller is assembled to discard the encapsulated data by reconfiguring the memory portion storing the encapsulated data. The controller is further assembled to determine whether the capacity of the node is exceeded, and wherein the controller is assembled to determine a plurality of queues In the size range, which one has the largest queue size range and at least one related queue in order to respond to the judgment that exceeds the capacity of the node. The controller is assembled to select the queue, so that compared with the selected queue, The other dimensions of the same size range can be discarded regardless of the selected queue size. The controller includes a processor which is assembled to execute software instructions. The controller includes hardware, It can be assembled regardless of software instructions. Generally speaking, in another aspect, the present invention provides a system for transmitting encapsulated data. The device includes an input for receiving the encapsulated data; a memory connected to the Enter and assemble to store the encapsulation data in queues' where each queue has an associated size; a transmission link Output of encapsulated data of the memory; and a control device that is effectively connected to the memory to discard at least one data packet from a particular queue related to a particular queue size range, the particular queue size range being greater than any Other queue sizes with at least one related queue. Implementation of the present invention may include one or more of the following characteristics. The paper size of the control device is applicable to the Chinese National Standard (CNS) A4 specification (210X 297 mm) (Please read first Note on the back, please fill out this page) Order _L-Printed by the Consumer Cooperative of the Intellectual Property Bureau of the Ministry of Economic Affairs * · 111 ml mi emma 0 -6-518851 A7 ___B7 V. Description of the invention (4) (Please read the first Note: Please fill in this page again.) At least one data packet can be discarded regardless of the size of any other queue related to the specific queue size range. The control device de-allocates the memory portion storing the discarded at least one packet. The & control device re-arranges the memory portion storing the discarded at least one packet. Generally speaking, in another aspect, the present invention provides a method including storing a queue of encapsulated data and an indicator of the queue size in a network node for transmission from the network node; determining a plurality of 'Which of the queue size ranges has the largest queue size range and at least one related queue; and the encapsulation data of a selected queue is discarded from the at least one related queue. Implementations of the invention may include one or more of the following features. The discarding includes decomposing the memory configuration storing the encapsulated data. The discarding includes reallocating the memory storing the encapsulated data. The method may further include judging whether the node capacity is exceeded, in which a judgment of which of the plurality of queue size ranges has the largest queue size range and at least one related queue is made in response to the judgment of exceeding the node capacity. Printed by the Consumer Cooperative of the Intellectual Property Bureau of the Ministry of Economic Affairs In general, in another aspect, the present invention provides a data flow method in a network node for transmitting data packets. The method includes storing a data packet in the network node. The queue and an indicator of the queue size for transmission from the network node. The related encapsulation data queue has a bucket, which has the size range of the queue related to the bucket; determine which bucket is at least partly Fully filled, and has the largest relevant queue size range relative to any other at least partially filled bucket; the bucket selected from the judgment is based on the Chinese paper standard (CNS) A4 specification (210X297 mm) ) 518851 A7 B7 5. Column (5) of the description of the invention; and discard the encapsulation data from the selected queue. (Please read the notes on the back before filling out this page) The implementation of the present invention may include one or more of the following features. The discarding includes decomposing the memory configuration storing the encapsulated data. The method may further include determining whether the capacity of the node to transmit the encapsulated data is exceeded, in which a determination is made as to which bucket is at least partially filled and has the largest relevant queue size range relative to any other bucket that is at least partially filled, Based on the judgment of the capacity exceeding the node. Various embodiments of the present invention may provide one or more of the following advantages. Queues can be selected so that a few (for example, one) operations can determine which queues will be discarded. Queues can be selected to discard at least the specific range of the largest queue. The potential size difference between the abandoned queue and the largest actual queue can be selected and / or adjusted. You can choose a fairly long, but probably not the longest, queue and use fewer hardware operations than the longest queue to discard. Queues can be selected so that, despite the number and size of the queues, they are discarded for a fairly fixed amount of time. These and other advantages, as well as the invention itself, will become more apparent from the following drawings, descriptions, and scope of patent applications. Intellectual Property Bureau B, Ministry of Economic Affairs (Printed diagram of industrial and consumer cooperatives) Figure 1 is a block diagram of a network including nodes and node links. Figure 2 is a block diagram of a node in the network shown in Figure 1. Figure 3 is Block diagram of the queue bucket system. Figure 4 is the block flow chart of the steps to abandon the queue. -8- This paper size applies the Chinese National Standard (CNS) A4 specification (2 丨 〇X 297 mm) M8851 A7 B7 instructions ( 6 $ Requirement comparison table 10 Communication system ^ 1-125 Personal computer 14 Network 1 6 Bu 16 8. Network node 18 Buffer 20 Bu 2 07 Column 22 Processor 24〇-24η-ι Storage bucket 26 Input line 28 input 璋 30 output line 3 2 output port Detailed description of the specific embodiment (please read the notes on the back before filling out this page) Printed by the Consumer Cooperatives of the Intellectual Property Bureau of the Ministry of Economic Affairs The present invention provides a considerable selection of information 选择A technology for arranging to discard between the queues of lines transmitted by a packet switching network node. Referring to FIG. 1, a communication system 10 includes a personal computer 12! -125 and a network 14 including network nodes 16m-168. The computer 12 is Shown via numbers such as The appropriate equipment and software are connected to nodes 16: and 167. The link 18 connecting to node 16 is assembled for two-way communication. Node 16 is a router transmitted via network 14, such as the well-known Internet and other global Packet exchange data network. Node 16 is assembled to receive packets and transmit them to neighboring nodes 16, for example, as determined by routing node 16 or the Chinese paper standard (CNS) A4 specification applies to the paper size of the node (210X297 mm) -9- 518851 A7 B7 V. Description of invention (7) itself. Node 16 is also assembled to provide proper buffering of incoming packets before transmitting them to neighboring nodes 16. Node 1 6 has a variety of buffer and transmission device versions, so that data can be buffered and transmitted internally, and internal buffering and transmission may cause congestion, just as data buffers and external transmitters are caused externally. Node 1 6 may also be packetized Origin and / or destination. Referring to Figure 2, an example node 16 (here node 1 6 4) includes a node buffer 18 which is assembled to store And a queue 20 of data packets to be transmitted. The buffer 18 includes memory for storing data, which executes software under the control of the processor 22. Although other contacts between nodes 16 are acceptable, such as As shown in FIG. 1, the buffer 18 is connected to the nodes 16 !, 163, and 167 to receive and transmit data packets therebetween. The packet is received at the input port 28 via the input line 26 and output from the output line 30璋 3 2. Send. The data packet is stored in queue 20 (shown here as queue 20! -207) for transmission from buffer 18. Data packets can be transmitted out of queue 20 in different orders. For example, packets can be transmitted in parallel from Q! To Q7, in accordance with the amount of bandwidth allocated to each queue 20 (the amount of each queue 20 can be different). Packets can also be transmitted by a combination of several technologies, such as queue 2 (^-203 is transmitted in the order of numbers, and queues 204-207 are also transmitted in the order of numbers, but queues 20i-2 (h of the The packets of a group can be transmitted in parallel with the packets of the queues 204-207 according to the frequency bandwidth allocated to each group. The buffer 18 and the processor 22 are assembled and executed almost. The longest queue discard (LQD) strategy. Preferably, the digital space of the buffer is fixed. This paper size applies the Chinese National Standard (CNS) A4 specification (210X29? Mm) f Please read the notes on the back before filling (This page) Order printed by the Intellectual Property Bureau employee consumer cooperative of the Ministry of Economic Affairs 518851 Printed by the Intellectual Property Bureau employee consumer cooperative of the Ministry of Economic Affairs printed A7 B7 V. Invention description (8) As a result, the buffer memory has a limited size. Only small positive integers can be stored by the buffer 18 and the processor 22. The processor 22 is assembled to control the buffer 18 according to software code operations, perform different functions and complete the nearly longest queue rejection (LQD) strategy. Limited, borrow At this time, the size (size) of an element (queue) can be changed. One packet is added and removed from the queue at a time, so the size of an element will only be increased or decreased by the maximum size of a packet. At the same time An "almost correct" answer is assumed to be acceptable. It has been shown that even as long as a rough approximation of the longest queue is sought, queue 20 is inserted into or from buffer 18 with a limited size range. Remove. When queue 20 is empty, it enters the system and has a packet. When it has no packets, it is removed from the system. So a newly inserted queue 20 will have a value greater than 0 and less than or equal to the maximum packet size. Size, while the queue 20 to be removed will have a size of 0. The buffer 18 is assembled to combine the queue 20 in a series of "buckets" relative to queues of different lengths. Although queue 20 can be imagined They are stored in buckets, but queues 20 do not need to be stored physically. Buckets are not so much physical groups as logical groups. For example, buckets can be counters, linked tables, or other queues. The index of which bucket belongs to 20 is implemented. Referring to Fig. 3, although only three buckets 24 are shown. -2, the buffer 18 includes n buckets 26-24 ^. The maximum size of 20 is represented by the function S, where ^ indicates the maximum size queue to be placed in the bucket 24i. The bucket ^ will include a length of 0 bytes to S. The size of this paper applies the Chinese National Standard (CNS ) A4 size (210X297mm) -11-(Please read the precautions on the back before filling this page)
518851 Α7 Β7 五、發明説明（9 ) 的佇列20 ,儲存桶24!將包括長度So + 1位元組至Si位元 組的佇列20等等。 儲存桶24 (此處爲24。、24!及2心）儲存相對應尺寸範 圍R (此處爲R〇、Ri及RO內之尺寸的佇列20。除了最小 佇列尺寸.是〇以外，尺寸範圍R所包含的尺寸其中範圔R 之最大佇列尺寸S約爲範圍R之最小佇列尺寸的兩倍。例 如，範圍R。包括尺寸0位元組至63位元組的佇列，範圍 R!包括尺寸64位元組至127位元組的佇列，而範圍R;則包 括尺寸128位元組至25 5位元組的佇列。換言之，R〇二[〇 位元組，63位元組]，[2"位元組，2n + 1-l位元組]，其中 n = i + l。爲將一佇列分類，分析該尺寸的二進位指標以判斷 最高的位元是一個1。除了本範例中所提及者外，範圍R間 _ — - - - - - - — · 的其他關係是可接受的（例如η至I的不同關係）。儲存 桶的尺寸範圍R可以隨平均/最大佇列尺寸或尺寸分佈的 變化而動態地變化。然而，固定的尺寸可提供一較簡單的 進行。 在任意儲存桶24內的佇列20並不需依據其尺寸而儲 存。佇列20可依據其相對尺寸或無關乎其相對尺寸而儲存 ，例如依據首先抵達，最後抵達或隨機地。 緩衝器1 8及處理器22加以裝配而實施近乎最長佇列 拋棄（LQD )機制，適當地拋棄佇列20。依據該拋棄機制 ，緩衝器1 8及處理器22可輕易地判斷哪一儲存桶是非空 的（即至少部分儲滿），確認非空之儲存桶24中的至少〜 佇列20，以及輕易地自儲存桶24的任意佇列中拋棄一或多 本紙張尺度適用中國國家標準（CNS ) Α4規格（210Χ297公釐） (请先閱讀背面之注意事項再填寫本頁) 、1Τ 經濟部智慧財產局員工消費合作社印製 -12 518851 A7 B7_ 五、發明説明（10) (請先閱讀背面之注意事項再填寫本頁) 個封包。因而，遭拋棄之佇列20 (即，目標佇列中的一或 .多個封包將被拋棄）可能不是最長的佇列20，但關於最長 的佇列20的相對準確性則足以提供相對公平性。遭拋棄之 封包數是可變的，但較佳地是拋棄足夠的封包數，如此節 點1 64的容量便不會被未被拋棄之封包所超過。封包經由對 儲存被拋棄封包之記憶體進行解除配置及/或重新配置而 被拋棄，如此其他的資料便可寫入進行解除配置及/或重 新配置的記憶體。緩衝器1 8及處理器22的拋棄機制亦可 識別較少使用或從未使用的佇列，並自該些佇列中拋棄封 包。 經濟部智慧財產局員工消費合作社印製 參閱圖4並進一步參閱圖1至2，自佇列20拋棄封包 的步驟40包括階段42、44及46，其中爲（但不限於）說 明之故，網路節點164於階段42適當地接收一資料封包並 緩衝（儲存）該封包，該封包是經由輸入線26及輸入埠28 而被接收。包封資料以即時的方式，以一或多個佇列20儲 存於緩衝器1 8中。在階段44，所接收的封包判依據與其相 關之封包的指標而與佇列20相結合，例如經由指定至佇列 20。在階段46，所接收的封包依據與其相關之佇列20的尺 寸而進一步地與佇列儲存桶24相結合。儲存桶24隨著佇 列20的尺寸變化而變化。 在階段48，處理器22判斷是否超過節點1 64儲存封包 的容量。該判斷可因應正由節點164所接收的封包。若尙未 超過該節點的容量，那麼步驟40便返回至階段42並等待 另一將被接收的封包。替代地，容量判斷應定期實施，例 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐） " — ' -13- 518851 Α7 Β7 五、發明説明（11 ) 如由一計時器控制。在此例中，如虛線迴路49所示，若尙 未超過該節點的容量，那麼步驟40便仍處於階段48。若已 超過該節點的容量，那麼步驟40便前進至階段52。 在階段52，處理器22判斷娜一儲存桶24是非空的並 具有最大佇列尺寸範圍R。例如，該處理器可以遞減之佇歹ίί 尺寸範圍R的順序詢問每一儲存桶24，直至發現非空的儲 存桶24。 在階段54，在非空之具有最大佇列尺寸範圍R的儲存 桶24中選擇佇列20進行拋棄。處理器22隨機地或在儲存 桶24中選擇佇列20，不論所選擇的佇列20相對於儲存桶 24中的任何其他佇列20是否具有較大的尺寸。因而，所選 擇的佇列20可能不是最大的佇列20。 在階段56，階段54中所選擇的佇列20被拋棄。拋棄 可包括解除該封包的佇列以便自節點164傳輸，或解除儲存 將被拋棄封包之記憶體的配置。 圖4中所不步驟40是一範例並不侷限於此。相較於圖 4，階段可予以增加、刪減或重新安排。例如可刪除階段44 :例如，若所接收的封包與該封包中資訊所指示的佇列相 結合（例如在該封包的報頭）。同樣地，階段42、44及46 亦可予以刪除：例如，若資料封包的收訊未用於啓動拋棄 機制。 其他的具體實施例均在申請專利的精神及範圍內。例 如，上述由軟體所執行/控制的功能。由於軟體的特性， 功能可由軟體、硬體、韌體、硬接線或任意組合所執行/ 本紙張尺度適用中國國家標準（CNS ) Α4規格（210Χ297公釐） (請先閱讀背面之注意事項再填寫本頁) 訂 經濟部智慧財產局8工消費合作社印製 518851 A7 _B7_ 五、發明説明（12 ) (請先閱讀背面之注意事項再填寫本頁) 控制，而該些功能的實體實施則可實體地存在於上述以外 的位置，包括.分佈於不同位置。例如，處理器22可以是一 硬體邏輯（不同於軟體，或大部分不同）以執行所謂的功 能，其可能引發較使用軟體控制之處理器更快的作業。軟 體控制之處理器可用於處理連接至網路14外部的資料，同 時硬體則可用於處理連接至網路14內部的資料。雖然緩衝 器的優先性是表列的’但緩衝器的數字空間則不需固定， 經濟部智慧財產局員工消費合作社印製 藉著該量當一佇列進行修改時其尺寸可以改變而不需限制 :佇列可插入/移出緩衝器不需在限制的尺寸範圍內；而 且除了空的時間外，佇列可置入系統以得到封包，並可在 其具有至少一個封包時移除。儲存桶尺寸範圍R可以與所 討論的不同。尺寸範圍R可重疊。相對於其他之範圍的增 加程度可以與上述不同。例如，在較低的尺寸範圍內，範 圍R可以小量的增加，其可能或並不相同（例如64位元組 )，而在較高的尺寸範圍時，便可以較大量的增加，例如 所討論的爲最大尺寸的兩倍。較佳地，不論使用何種相關 的佇列20與儲存桶24的組合，結合佇列20與選擇佇列20 進行拋棄的步驟皆較排序佇列20及選擇最大者來得低廉（ 就成本及/或處理損耗而論）。 藉加壓於一或多個佇列可將佇列尺寸調整成有效的尺 寸。該有效的尺寸可用於結合丨宁列20與儲存桶24。所使用 之最小/門檻的有效尺寸必須符合佇列20，因其將成爲被 推出的目標。可以最小/門檻以下的有效尺寸而爲佇列20 建立一特殊的儲存桶’諸如該些具有〇位元組之有效/加 本紙張尺度適用中國國家標筚（CNS)A4規格（2i〇x297公釐） —n~~ 518851 A7 B7 五、發明説明（13) 壓的尺寸、渠等具有位元組。儘管不正常地取得拋棄資格 ，但使用該特殊儲存桶可使得渠等佇列成爲拋棄的目標。. 做爲拋棄目標的佇列可隨機地自該特殊儲存桶選取，或使 用確實符合最小/門檻的類似機制來鎖定佇列（例如，改 變最小/門檻）。 (請先閲讀背面之注意事項再填寫本頁) --- β mu mu - mu n>la 111 nm T 口 經濟部智慧財產局員工消費合作社印製 本紙浪尺度適用中國國家標準（CNS ) A4規格（21〇X297公釐） -16-518851 Α7 Β7 Fifth, queue 20 of invention description (9), bucket 24! Will include queue 20 of length So + 1 byte to Si byte, and so on. Bucket 24 (here 24, 24 !, and 2 cores) stores the corresponding size range R (here is the queue 20 of the size within R0, Ri, and RO. In addition to the minimum queue size. Is 0, The size range R includes the maximum queue size S of the range R, which is about twice the minimum queue size of the range R. For example, the range R. Includes queues of size 0 bytes to 63 bytes, The range R! Includes a queue of sizes 64 to 127 bytes, and the range R; includes a queue of sizes 128 to 25 5 bytes. In other words, R0 [0 bytes, 63 bytes], [2 " bytes, 2n + 1-l bytes], where n = i + l. To classify a queue, analyze the binary index of this size to determine the highest bit Is a 1. Except as mentioned in this example, other relationships between the range R — — — — — — — — — — are acceptable (for example, different relationships from η to I). The size range R of the bucket Can change dynamically with changes in average / maximum queue size or size distribution. However, fixed sizes can provide a simpler process. In any bucket 2 The queue 20 in 4 does not need to be stored according to its size. The queue 20 can be stored according to its relative size or regardless of its relative size, such as based on first arrival, last arrival or random. Buffer 18 and processor 22 is assembled to implement the nearly longest queue discard (LQD) mechanism, and the queue 20 is appropriately discarded. According to the discard mechanism, the buffer 18 and the processor 22 can easily determine which bucket is non-empty (that is, at least partly Full), confirm that at least ~ queue 20 in non-empty bucket 24, and easily discard one or more papers from any queue in bucket 24. Applicable to China National Standard (CNS) A4 specifications (210 × 297) (%) (Please read the notes on the back before filling out this page), 1T printed by the Consumer Cooperatives of the Intellectual Property Bureau of the Ministry of Economic Affairs-12 518851 A7 B7_ 5. Description of the invention (10) (Please read the notes on the back before filling in this Pages). Therefore, the discarded queue 20 (that is, one or more packets in the target queue will be discarded) may not be the longest queue 20, but the relative accuracy of the longest queue 20 It is sufficient to provide relative fairness. The number of discarded packets is variable, but it is preferable to discard enough packets so that the capacity of node 1 64 will not be exceeded by the packets that are not discarded. The memory of the discarded packet is discarded and / or reconfigured and discarded, so that other data can be written into the memory for deconfiguration and / or reconfiguration. The discard mechanism of buffer 18 and processor 22 can also be used. Identify queues that are rarely used or never used, and discard packets from those queues. Printed by the Consumer Cooperatives of the Intellectual Property Bureau of the Ministry of Economic Affairs Refer to Figure 4 and further to Figures 1 to 2 Step 40 includes phases 42, 44 and 46. For the purpose of (but not limited to) the description, the network node 164 appropriately receives a data packet and buffers (stores) the packet at phase 42. The packet is transmitted through the input line 26 and Input port 28 is accepted. The encapsulation data is stored in a buffer 18 in one or more queues 20 in a real-time manner. At stage 44, the received packet is determined to be combined with queue 20 based on the index of the packet associated with it, for example, by designating to queue 20. At stage 46, the received packet is further combined with the queue bucket 24 in accordance with the size of the queue 20 associated with it. The storage tank 24 changes as the size of the queue 20 changes. At stage 48, the processor 22 determines whether the capacity of node 1 64 to store the packet is exceeded. This determination may correspond to the packet being received by the node 164. If 尙 does not exceed the capacity of the node, then step 40 returns to stage 42 and waits for another packet to be received. Instead, the capacity judgment should be carried out regularly. For example, the paper size applies the Chinese National Standard (CNS) A4 specification (210X297mm) " — '-13- 518851 Α7 Β7 5. Description of the invention (11) If controlled by a timer . In this example, as shown by the dotted line 49, if 尙 does not exceed the capacity of the node, then step 40 is still in phase 48. If the capacity of the node has been exceeded, then step 40 proceeds to phase 52. At stage 52, the processor 22 determines that Na-a bucket 24 is non-empty and has a maximum queue size range R. For example, the processor may query each bucket 24 in order of decreasing size range R until a non-empty bucket 24 is found. At stage 54, queue 20 is selected from the non-empty buckets 24 having the largest queue size range R for disposal. The processor 22 selects the queue 20 randomly or in the bucket 24, regardless of whether the selected queue 20 has a larger size than any other queue 20 in the bucket 24. Therefore, the selected queue 20 may not be the largest queue 20. In stage 56, the selected queue 20 in stage 54 is discarded. Discarding may include dequeuing the packet for transmission from node 164, or de-allocating the configuration of the memory that will discard the packet. Step 40 shown in FIG. 4 is an example and is not limited thereto. Compared to Figure 4, phases can be added, deleted, or rearranged. For example, phase 44 may be deleted: for example, if the received packet is combined with the queue indicated by the information in the packet (for example, in the header of the packet). Similarly, phases 42, 44, and 46 can also be deleted: for example, if the reception of a data packet is not used to initiate the discard mechanism. Other specific embodiments are within the spirit and scope of the patent application. For example, the functions described above are performed / controlled by software. Due to the characteristics of the software, the functions can be performed by software, hardware, firmware, hard wiring or any combination. This paper size applies the Chinese National Standard (CNS) Α4 specification (210 × 297 mm) (Please read the precautions on the back before filling in (This page) Order printed by the Intellectual Property Bureau of the Ministry of Economic Affairs and printed by 518851 A7 _B7_ V. Description of the invention (12) (Please read the precautions on the back before filling this page) Control, and the physical implementation of these functions can be physically implemented Land exists in locations other than the above, including. Distributed in different locations. For example, processor 22 may be hardware logic (different from software, or largely different) to perform so-called functions, which may cause faster operations than a processor controlled using software. The processor controlled by software can be used to process data connected to the outside of the network 14, while the hardware can be used to process data connected to the inside of the network 14. Although the priority of the buffer is listed, the digital space of the buffer does not need to be fixed. It is printed by the Consumer Cooperatives of the Intellectual Property Bureau of the Ministry of Economic Affairs. The size can be changed without modification when a queue is modified. Restrictions: Queue insertable / removable buffers do not need to be within a limited size range; and in addition to empty time, queues can be placed into the system to get packets and can be removed when they have at least one packet. The bucket size range R may differ from that discussed. The size range R can overlap. The degree of increase relative to other ranges may be different from the above. For example, in the lower size range, the range R may be increased by a small amount, which may or may not be the same (for example, 64 bytes), and in the higher size range, it may be increased by a larger amount, such as The discussion is twice the maximum size. Preferably, no matter which combination of queue 20 and bucket 24 is used, the steps of combining queue 20 and selecting queue 20 to discard are cheaper than sorting queue 20 and selecting the largest one (in terms of cost and / Or processing loss). By pressing on one or more queues, the queue size can be adjusted to an effective size. This effective size can be used to combine Ning Li 20 with storage bucket 24. The effective size of the minimum / threshold used must be in line with queue 20 as it will be the target of the push. It is possible to create a special bucket for the queue 20 with the effective size below the minimum / threshold value. Such as those with 0 bytes of valid / additive paper sizes are applicable to China National Standard (CNS) A4 specifications (2i × 297mm) (Centimeter) —n ~~ 518851 A7 B7 V. Description of the invention (13) The dimensions and channels of the pressure have bytes. Although it is not properly qualified for disposal, the use of this special bucket can make queues such as canisters the target of disposal. The queues to be discarded can be randomly selected from the special bucket, or the queues can be locked using a similar mechanism that does meet the minimum / threshold (for example, changing the minimum / threshold). (Please read the precautions on the reverse side before filling out this page) --- β mu mu-mu n &la; la 111 nm T-mouth printed by the Intellectual Property Bureau of the Ministry of Economic Affairs Employees' Consumer Cooperatives This paper wave scale is applicable to China National Standard (CNS) A4 specifications (21〇X297 mm) -16-