Selection of data for network transmission
DCFirst Claim
1. A circuitry implemented method for selecting data for transmission in a network, the method comprising:
- storing representations of data flows in storage structures S1, . . . SN, wherein N>
1, wherein each data flow is associated with a bandwidth to be given to the data flow;
transferring zero or more data flow representations from storage structures S1, . . . SN to a storage structure S0, wherein for each i (0<
i<
N), the frequency with which the zero or more data flow representations are transferred from structure Si to structure S0 is greater than the frequency with which zero or more data flow representations are transferred from structure S(i+1) to structure S0;
selecting a data flow representation from structure S0 to transmit data on the corresponding data flow;
transferring the selected data flow representation to a structure Sj (0≦
j≦
N) for subsequent transmission on the corresponding data flow, wherein the structure Sj is chosen from structures S0, . . . , SN based on the bandwidth to be given to the corresponding data flow.
10 Assignments
Litigations
0 Petitions
Accused Products
Abstract
Data flows are queued in an active queue (160.0) waiting for transmission. In each time slot, one data flow can be dequeued from the head of the active queue, and a data unit can be transmitted on the data flow. Then the data flow is placed in a queue “i” which is one of the queues 1, 2, . . . N. Data flows are transferred from queue “i” to the active queue once in every 2i time slots. When a data flow is dequeued from the active queue and transferred to queue i, the queue number “i” is determined as i=log Δ, rounded to an integer, where A is the number of time slots in which one data unit must be transmitted from the data flow in order to meet a data flow bandwidth parameter. If the data flow has waited for “d” time slots in the active queue before being dequeued, then i=log (Δ−d), rounded to an integer.
21 Citations
20 Claims
-
1. A circuitry implemented method for selecting data for transmission in a network, the method comprising:
-
storing representations of data flows in storage structures S1, . . . SN, wherein N>
1, wherein each data flow is associated with a bandwidth to be given to the data flow;
transferring zero or more data flow representations from storage structures S1, . . . SN to a storage structure S0, wherein for each i (0<
i<
N), the frequency with which the zero or more data flow representations are transferred from structure Si to structure S0 is greater than the frequency with which zero or more data flow representations are transferred from structure S(i+1) to structure S0;
selecting a data flow representation from structure S0 to transmit data on the corresponding data flow;
transferring the selected data flow representation to a structure Sj (0≦
j≦
N) for subsequent transmission on the corresponding data flow, wherein the structure Sj is chosen from structures S0, . . . , SN based on the bandwidth to be given to the corresponding data flow.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
for each i (0<
i<
N), the zero or more data flow representations are transferred from structure Si to structure S0 once in every 2i time units; and
when a data flow representation is selected for transmission, a data unit is transmitted from the corresponding data flow, and if the corresponding data flow has more data to transmit, the data flow representation is transferred to structure Sj where j=log Δ
, rounded to an integer, where Δ
is the number of the time units in which one data unit is to be transmitted on the data flow in accordance with the bandwidth to be given to the data flow.
-
-
4. The method of claim 2 further comprising incrementing or decrementing a counter once in every time unit, wherein the time unit is a length of time that it takes to transmit data from a data flow when the corresponding data flow representation is selected for transmission;
wherein when the counter is incremented or decremented, a number b is determined which is the number of the counter'"'"'s bit that changes from a predetermined first value to a predetermined second value, the bits being numbered from zero up starting with the least significant bit, and zero or more data flow representations are transferred to structure S0 from structure Si where i=b+1.
-
5. The method of claim 1 wherein for at least one data flow, the associated bandwidth is the minimal bandwidth to be given to the data flow;
- and
the method further comprises transmitting data on the corresponding data flow, when bandwidth is available, even when the corresponding data flow representation is not selected from structure S0, thereby giving additional bandwidth to the data flow in addition to the minimal bandwidth.
- and
-
6. The method of claim 1 wherein at least one data flow comprises a plurality of data flows.
-
7. The method of claim 1 wherein the storage structures S1, . . . SN and the storage structure S0 comprise data queues.
-
8. The method of claim 1 wherein the data flows are a type selected from a group consisting of ATM cells, IP packets, or TCP connections.
-
9. The method of claim 8 wherein the first data storage structures are identified as a Si data storage structure where 0<
- i<
N+1, wherein for each i (0<
i<
N), the frequency with which data flow representations are transferred from structure Si to second data storage structure is greater than the frequency with which data flow representations are transferred from structure S(i+1) to second data storage structure.
- i<
-
10. The method of claim 9 wherein the frequency with which data flow representations are transferred from a first data storage structure Si to the at least one second data storage structure is at least twice the frequency with which data flow representations are transferred from a first data storage structure S(i+1) to second data storage structure.
-
11. The method of claim 10 wherein data flow representations are transferred from the structure Si to the at least one second data storage structure once every 2i time units and when a data flow representation is selected for transmission, a data unit is transmitted from the corresponding data flow, and if the corresponding data flow has more data to transmit, the data flow representation is transferred to one of the first and second date structures in accordance with the bandwidth to be given to the data flow.
-
12. The method of claim 10 further comprising incrementing or decrementing a counter once every time unit, wherein the time unit is a length of time that it takes to transmit data from a data flow when the corresponding data flow representation is selected for transmission;
wherein when the counter is incremented or decremented, a number b is determined which is the number of the counter'"'"'s bit that changes from a predetermined first value to a predetermined second value, the bits being numbered from zero up starting with the least significant bit, and data flow representations are transferred to the second data storage structure from a first data storage structure Si of the plurality of first data storage structures where i=b+1.
-
13. An apparatus for transmitting data over a network, the apparatus comprising:
-
a computer storage for storing computer representations of data flows, wherein each data flow is associated with one or more bandwidth requirements for the data flow;
circuitry for storing the data flow representations in a plurality of first structures in the computer storage, for transferring data flow representations from the first structures to a second structure such that at least two of the first structures have their data flow representations transferred to the second structure with respective two different frequencies, the circuitry being operable to select a data flow representation from the second structure to be transmitted on the corresponding data flow based on a bandwidth requirement for the data flow and to transfer the selected data flow representation. - View Dependent Claims (14, 15, 16)
the circuitry is operable to store in the computer storage, for each data flow representation, a bandwidth parameter indicating how often a data unit needs to be transmitted on the corresponding data flow in order to satisfy a bandwidth requirement for the data flow;
when a data flow representation is selected from the second structure to transmit data on the corresponding data flow, the circuitry calculates when the next transmission on the data flow is to occur to satisfy the corresponding bandwidth parameter, and the circuitry is operable to transfer the data flow representation to the first data structure whose data flow representations will be transferred to the second data structure when the next transmission on the data flow needs to occur.
-
-
17. A circuitry implemented method for selecting data for transmission, the circuitry comprising a memory comprising a plurality of first data storage structures and at least one second data storage structure, the method comprising:
-
transferring data flow representations from the plurality of first data storage structures to the at least one second data storage structure such that at least two of the first data storage structures have data flow representations stored therein transferred to the at least one second data storage structure at two different rates; and
selecting a data flow representation from the at least one second data storage structure, so that data associated with the data flow is transmitted based on the bandwidth to be given to the corresponding data flow. - View Dependent Claims (18, 19, 20)
the method further comprises transmitting data on the at least one data flow, when bandwidth is available, even when a corresponding data flow representation is not selected from the at least one second data storage structure for transmission.
-
-
19. The method of claim 17 wherein the plurality of first data storage structures and the at least one second data storage structure comprise data queues.
-
20. The method of claim 17 wherein the data flows are a type selected from a group consisting of ATM cells, IP packets, or TCP connections.
Specification