US5956340A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Space efficient fair queuing by stochastic Memory multiplexing
Assignee: Ramot at Tel Aviv University Ltd
•
Filing: 1997-08-05
•
Granted: 1999-09-21
•
Expires: 2017-08-05
Abstract
Abstract A method for multiplexing the buffer space used to store messages of backlogged flows at the output port of a switch. The buffer space is partitioned among queues of variable length, with the first queue long enough to accommodate the largest expected backlog, the second queue long enough to accommodate the second-largest expected backlog, etc. Messages are dequeued from the queues for transmission in Round-Robin order. Incoming messages are enqueued in a manner that guarantees that messages of heavily backlogged flows tend to be enqueued in the longer queues, while preserving FIFO message order. If the messages are all of the same length, then the queues are partitioned into locations, of the same length as the messages, each location having an ordinal index in its queue, and the messages are enqueued so that each message of a particular flow is enqueued in a location with a different ordinal index. If the messages are of different lengths, the queues are partitioned into bins large enough to accommodate the longest messages, one or more messages may be stored in each bin, the round in which each incoming message is to be transmitted is computed in advance, and a similar enqueueing algorithm is used that is based on matching successive transmission rounds of messages of a given flow to successively indexed bins of different queues. The present invention may be used in any application involving Round Robin scheduling.
Inventors
- 👤 Yehuda Afek
- 👤 Yishay Mansour
- 👤 Zvi Ostfeld
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 03:01
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/30
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
209 words
A method for allocating space in a memory for storing messages of equal length to be transmitted via an output port of a link, and then transmitting the messages, each of the messages being associated with a flow having a flow index, the flow indices being in a certain order, the method comprising the steps of: (a) dividing the memory among a plurality of queues, each of said queues having at least one location, each of said locations being at least as long as one of the messages, at least one of said queues having a maximum number of said locations, and at least one of said queues having a number of said locations less than said maximum number of said locations, each of said locations in one of said queues having an ordinal index within said queue; (b) storing each of the messages in one of said queues so that each message of a flow is stored in a location having a different ordinal index than any other location used to store any other message of said flow; and (c) for each of said queues in which at least one message is stored, transmitting said message that is stored in said location that has a lowest ordinal index.
Claim 2
Independent Claim
209 words
A method for allocating space in a memory for storing messages of equal length to be transmitted via an output port of a link, and then transmitting the messages, each of the messages being associated with a flow having a flow index, the flow indices being in a certain order, the method comprising the steps of: (a) dividing the memory among a plurality of queues, each of said queues having at least one location, each of said locations being at least as long as one of the messages, at least one of said queues having a maximum number of said locations, and at least one of said queues having a number of said locations less than said maximum number of said locations, each of said locations in one of said queues having an ordinal index within said queue; (b) storing each of the messages in one of said queues so that each message of a flow is stored in a location having a different ordinal index than any other location used to store any other message of said flow; and (c) for each of said queues in which at least one message is stored, transmitting said message that is stored in said location that has a lowest ordinal index.
Claim 3
Dependent Claim
27 words
The method of claim 1, wherein, if a flow has only one message, said only one message is stored in a location having said lowest ordinal index.
Claim 4
Dependent Claim
17 words
The method of claim 1, wherein each of said queues has a different number of said locations.
Claim 5
Dependent Claim
65 words
The method of claim 1, wherein each of said queues has a queue index, wherein a single longest of said queues has said maximum number of said locations, and wherein each of said queues that is shorter than said longest queue has a number of said locations equal to said maximum number divided by said queue index of said queue and truncated to an integer.
Claim 6
Dependent Claim
21 words
The method of claim 4, wherein said queue indices are consecutive integers, said queue index of said longest queue being 1.
Claim 7
Dependent Claim
33 words
The method of claim 1, wherein said step of transmitting said messages is effected by steps including moving said messages from said locations of lowest ordinal index, substantially simultaneously, to a transmission buffer.
Claim 8
Dependent Claim
28 words
The method of claim 1, wherein said step of transmitting said messages is effected by steps including sequentially retrieving said messages from said locations of lowest ordinal index.
Claim 9
Dependent Claim
36 words
The method of claim 7, wherein each of said queues has a queue index, said queue indices being in a certain order, and wherein said sequential retrieval is effected in said order of said queue indices.
Claim 10
Dependent Claim
39 words
The method of claim 7, wherein each of said queues has a queue index, said queue indices being in a certain order, and wherein said sequential retrieval is effected in a permutation of said order of said queue indices.
Claim 11
Dependent Claim
18 words
The method of claim 7, wherein said sequential retrieval is effected in the order of the flow indices.
Claim 12
Dependent Claim
21 words
The method of claim 7, wherein said sequential retrieval is effected in a permutation of the order of the flow indices.
Claim 13
Dependent Claim
13 words
The method of claim 11, wherein said permutation is a Round Robin permutation.
Claim 14
Dependent Claim
13 words
The method of claim 11, wherein said sequential retrieval emulates Stochastic Fair Queuing.
Claim 15
Independent Claim
324 words
A method for allocating space in a memory for storing messages to be transmitted via an output port of a link, and then transmitting the messages, each message having a certain length bounded above by a maximum message length, each message being associated with a flow having a flow index, the flow indices being in a certain order, the method comprising the steps of: (a) dividing the memory among a plurality of queues, each of said queues having a queue index, each of said queues having at least one bin, at least one of said queues having a maximum number of said bins, and at least one of said queues having a number of said bins less than said maximum number of said bins, each of said bins having an ordinal index within said queue; (b) for each message, computing a transmission round in which the message is to be transmitted; (c) for each message, storing the message in at least one of said bins whose ordinal indices are related to said transmission round, so that, for said queues of said at least one of said bins whose ordinal indices are related to an earlier transmission round and in which at least a part of at least one of the messages to be transmitted in said earlier transmission round is stored, a largest of said queue indices is at least as great as a largest of said queue indices of said queues of said at least one of said bins whose ordinal indices are related to a later transmission round and in which at least a part of at least one of the messages to be transmitted in said later transmission round is stored; and (d) for each of said queues in which at least part of one of the messages is stored in said bin having a lowest ordinal index, retrieving said at least part of said one of the messages for transmission.
Claim 16
Independent Claim
324 words
A method for allocating space in a memory for storing messages to be transmitted via an output port of a link, and then transmitting the messages, each message having a certain length bounded above by a maximum message length, each message being associated with a flow having a flow index, the flow indices being in a certain order, the method comprising the steps of: (a) dividing the memory among a plurality of queues, each of said queues having a queue index, each of said queues having at least one bin, at least one of said queues having a maximum number of said bins, and at least one of said queues having a number of said bins less than said maximum number of said bins, each of said bins having an ordinal index within said queue; (b) for each message, computing a transmission round in which the message is to be transmitted; (c) for each message, storing the message in at least one of said bins whose ordinal indices are related to said transmission round, so that, for said queues of said at least one of said bins whose ordinal indices are related to an earlier transmission round and in which at least a part of at least one of the messages to be transmitted in said earlier transmission round is stored, a largest of said queue indices is at least as great as a largest of said queue indices of said queues of said at least one of said bins whose ordinal indices are related to a later transmission round and in which at least a part of at least one of the messages to be transmitted in said later transmission round is stored; and (d) for each of said queues in which at least part of one of the messages is stored in said bin having a lowest ordinal index, retrieving said at least part of said one of the messages for transmission.
Claim 17
Dependent Claim
17 words
The method of claim 14, wherein each of said queues has a different number of said bins.
Claim 18
Dependent Claim
56 words
The method of claim 15, wherein a single longest of said queues has said maximum number of said bins, and wherein each of said queues that is shorter than said longest queue has a number of said bins equal to said maximum number divided by said queue index of said queue and truncated to an integer.
Claim 19
Dependent Claim
21 words
The method of claim 16, wherein said queue indices are consecutive integers, said queue index of said longest queue being 1.
Claim 20
Dependent Claim
27 words
The method of claim 14, wherein all of said bins are equal in size, said bin size being at least as great as the maximum message length.
Claim 21
Dependent Claim
17 words
The method of claim 14, wherein all of each message is stored in one of said bins.
Claim 22
Dependent Claim
21 words
The method of claim 19, wherein all the messages stored in one of said bins are associated with the same flow.
Claim 23
Dependent Claim
55 words
The method of claim 14, wherein said step of retrieving said at least part of the one of the messages from each of said queues, in which said at least part of one of the messages is stored in said bin having said lowest ordinal index, is effected substantially simultaneously for all of said queues.
Claim 24
Dependent Claim
49 words
The method of claim 14, wherein said step of retrieving said at least part of the one of the messages from each of said queues, in which said at least part of one of the messages is stored in said bin having said lowest ordinal index, is effected sequentially.
Claim 25
Dependent Claim
28 words
The method of claim 22, wherein said queue indices are in a certain order, and wherein said sequential retrieval is effected in said order of said queue indices.
Claim 26
Dependent Claim
19 words
The method of claim 22, further comprising the step of: (e) mapping said queue indices into the flow indices.
Claim 27
Dependent Claim
22 words
The method of claim 24, further comprising the step of: (f) transmitting the retrieved messages in the order of the flow indices.
Claim 28
Dependent Claim
25 words
The method of claim 24, further comprising the step of: (f) transmitting the retrieved messages in a permutation of the order of the flow indices.
Claim 29
Dependent Claim
12 words
The method of claim 26, wherein said transmitting emulates Deficit Round Robin.
Claim 30
Dependent Claim
12 words
The method of claim 26, wherein said transmitting emulates Weighted Fair Queuing.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-20 | 2003-03-22 | 2003-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-20 | 2007-03-22 | 2007-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-20 | 2011-03-22 | 2011-09-21 | $7700.00 | Window Closed / Lapsed |