US6084855A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for providing fair traffic scheduling among aggregated internet protocol flows
Assignee: Nokia Technologies Oy
•
Filing: 1997-02-18
•
Granted: 2000-07-04
•
Expires: 2017-02-18
Abstract
Abstract A method and apparatus is disclosed for providing fair traffic scheduling of L2 connections based on the number of IP flows and a priority coefficient for flow groups in the L2 connection. IP flows are scheduled according to a priority coefficient. The system identifies a number of IP flows for a plurality of connections, assigns a priority coefficient for each of the IP flows and schedules the IP flows according to the priority coefficient. The assignment of a priority coefficient results in a probability P i that a data unit belonging to a flow carried over connection A i will be selected for forwarding as defined by σ i *x i /Σ(x 1 . . . x n ), i={1,2, . . . n}, where x i is the number of flows carried over connection A i , σ i is the priority and n is the number of connections. The relationship between the number of flows x i and the priority σ i is defined by Σ.sub.(e=1-n) (σ i *x i )/Σ.sub.(i=1-n) x i =1.
Inventors
- 👤 Timo Soirinsuo
- 👤 Outi Markki
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 19:58
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L47/00; H04L47/10; H04L69/00; H04L69/16; H04L69/167; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/568
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
59 words
A method of prioritizing the scheduling of Internet Protocol (IP) flows, comprising the steps of: identifying a number of IP flows for each of a plurality of connections; assigning a priority to each of the plurality of connections based on the identified number of IP flows; and scheduling packet forwarding of the IP flows according to the assigned priority.
Claim 2
Independent Claim
59 words
A method of prioritizing the scheduling of Internet Protocol (IP) flows, comprising the steps of: identifying a number of IP flows for each of a plurality of connections; assigning a priority to each of the plurality of connections based on the identified number of IP flows; and scheduling packet forwarding of the IP flows according to the assigned priority.
Claim 3
Dependent Claim
89 words
The method of claim 1 wherein the step of assigning a priority further comprises the step of defining a probability P i that a data unit belonging to a flow carried over a connection A i of n total connections, A i , . . . A n , is selected for forwarding according to: ##EQU3## where x i represents a number of flows carried over the connection A i , σ i represents a priority assigned to flows x i and n represents a total number of connections.
Claim 4
Dependent Claim
24 words
The method of claim 2 wherein a relationship between the number of flows x i and the priority σ i is defined by: ##EQU4##
Claim 5
Dependent Claim
63 words
The method of claim 1 wherein the step of identifying the number of IP flows further comprises the steps of: monitoring packets carried over a connection; extracting address information from the packets for a predetermined sample period; storing the extracted address information; counting the number of extractions stored; and estimating the number of IP flows based upon the number of stored extractions counted.
Claim 6
Dependent Claim
26 words
The method of claim 4 wherein the step of extracting address information comprises the step of extracting full source address:port and destination address:port from the packets.
Claim 7
Dependent Claim
30 words
The method of claim 4 wherein the step of extracting address information comprises the step of extracting only a host or port part of an IP address from the packets.
Claim 8
Dependent Claim
23 words
The method of claim 4 wherein the step of storing the address information further comprises the step of compressing the extracted address information.
Claim 9
Dependent Claim
28 words
The method of claim 4 wherein the step of monitoring packets comprises the steps of: replicating PDUS; and directing the replicated PDUs to a processor for address extraction.
Claim 10
Dependent Claim
13 words
The method of claim 4 wherein the processor is outside the data path.
Claim 11
Dependent Claim
22 words
The method of claim 4 wherein the step of monitoring packets comprises the step of sampling the packets along the data path.
Claim 12
Dependent Claim
15 words
The method of claim 4 wherein the predetermined sample period comprises a selected time duration.
Claim 13
Dependent Claim
21 words
The method of claim 4 wherein the predetermined sample period comprises the time required to sample a predetermined number of packets.
Claim 14
Dependent Claim
27 words
The method of claim 1 wherein the step of assigning a priority further comprises the step of giving a higher priority to a connection having more users.
Claim 15
Dependent Claim
25 words
The method of claim 1 wherein the step of assigning a priority further comprises the step of differentiating a flow based on a management parameter.
Claim 16
Dependent Claim
14 words
The method of claim 14 wherein the management parameter represents operational and administrative considerations.
Claim 17
Dependent Claim
22 words
The method of claim 1 wherein the step of assigning a priority is based upon a compensation structure for different flow types.
Claim 18
Independent Claim
62 words
An apparatus for scheduling Internet Protocol (IP) flows, comprising: a monitor that identifies a number of IP flows for each of a plurality of connections; a prioritizer, operatively coupled to the monitor, the prioritizer assigning a priority coefficient for each of the connections; and a scheduler, operatively coupled to the monitor, the scheduler scheduling the IP flows according to the priority coefficient.
Claim 19
Independent Claim
62 words
An apparatus for scheduling Internet Protocol (IP) flows, comprising: a monitor that identifies a number of IP flows for each of a plurality of connections; a prioritizer, operatively coupled to the monitor, the prioritizer assigning a priority coefficient for each of the connections; and a scheduler, operatively coupled to the monitor, the scheduler scheduling the IP flows according to the priority coefficient.
Claim 20
Dependent Claim
65 words
The apparatus of claim 17 wherein the priority coefficient assigned by the prioritizer results in a probability that a data unit belonging to a flow carried over connection A i is selected for forwarding as defined by: ##EQU5## where x i represents a number of flows carried over connection A i , σ i represents a priority coefficient and n represents a number of connections.
Claim 21
Dependent Claim
25 words
The apparatus of claim 18 wherein a relationship between the number of flows x i and the priority coefficient σ i is defined by: ##EQU6##20.
Claim 22
Dependent Claim
68 words
The apparatus of claim 17 wherein the monitor further comprises: means for analyzing packets carried over a connection; means for extracting address information from the packets for a predetermined sample period; a memory for storing the extracted address information; a counter for counting the number of extractions stored in the memory; and a processor for estimating the number of IP flows based upon the number of extractions counted.
Claim 23
Dependent Claim
26 words
The apparatus of claim 20 wherein the means for extracting address information further comprises means for extracting full source address:port and destination address:port from the packets.
Claim 24
Dependent Claim
30 words
The apparatus of claim 20 wherein the means for extracting address information further comprises means for extracting only a host part of an IP address and port from the packets.
Claim 25
Dependent Claim
19 words
The apparatus of claim 20 wherein the processor further comprises data compression means for compressing the extracted address information.
Claim 26
Dependent Claim
27 words
The apparatus of claim 17 wherein the monitor further comprises: means for replicating PDUs; and means for directing the replicated PDUs to a processor for address extraction.
Claim 27
Dependent Claim
13 words
The apparatus of claim 20 wherein the processor is outside the data path.
Claim 28
Dependent Claim
15 words
The apparatus of claim 20 wherein the processor samples the packets along the data path.
Claim 29
Dependent Claim
15 words
The apparatus of claim 20 wherein the predetermined sample period comprises a selected time duration.
Claim 30
Dependent Claim
21 words
The apparatus of claim 20 wherein the predetermined sample period comprises a time required to sample a predetermined number of packets.
Claim 31
Dependent Claim
19 words
The apparatus of claim 17 wherein the priority coefficient represents a higher priority for a connection having more users.
Claim 32
Dependent Claim
20 words
The apparatus of claim 17 wherein the priority coefficient is used to differentiate a flow based on a management parameter.
Claim 33
Dependent Claim
14 words
The apparatus of claim 30 wherein the management parameter comprises operational and administrative considerations.
Claim 34
Dependent Claim
19 words
The apparatus of claim 17 wherein the priority coefficient is based upon a compensation structure for different flow types.
References Cited (Backward Citations)
US5278830A
Cited
US5499238A
Cited
US5717858A
Cited
US5872771A
Cited
EP0763915A2
Cited
WO1997013346A1
Cited
US5828653A
Cited
WO1998026510A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-04 | 2004-01-03 | 2004-07-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-04 | 2008-01-03 | 2008-07-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-04 | 2012-01-03 | 2012-07-04 | $7700.00 | Window Closed / Lapsed |