Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2000-12-19
2004-11-30
Vincent, David (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
C370S235000
Reexamination Certificate
active
06826147
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to exchanging data over a data communications network and, more particularly, to managing aggregate flows between network edges so as to better prevent and manage congestion at the core of a differentiated services network.
BACKGROUND OF THE INVENTION
Differentiated services (DiffServ) has recently gained acceptance as one way to address Quality of Service (QoS) issues in an Internet Protocol (IP) network. Service Level Agreements (SLAs) are used to define flows between network domains, and the level of service to be guaranteed for those flows. In one possible example, an SLA may include a committed information rate (CIR) and a peak information rate (PIR) for each aggregate. The SLAs are enforced at the edges of the different domains by edge routers, which use the SLAs to mark packets belonging to different flows with drop precedences corresponding to the level of service guaranteed for the flow by the SLAs. For example, when a flow's measured traffic is below its CIR, its packets are marked with the lowest drop precedence, dp
0
. When a flow's measured traffic is above its CIR but below its PIR, its packets are marked with a higher drop precedence, dp
1
. When a flow's measured traffic is above its PIR, its packets are marked with the highest drop precedence, dp
2
.
At the core of the network, simple differentiated forwarding mechanisms are used. One example forwarding mechanism is called Assured Forwarding (AF) Per Hop Behaviors (PHB). AF PHB establishes how packets are treated at the core of the network during times of congestion. Specifically, during congestion, packets marked with a dp
1
marking have a higher probability of being dropped than packets with a dp
0
marking, and packets having a dp
2
marking have a higher probability of being dropped than packets with a dp
1
marking.
The rationale behind this scheme is that well-behaved flows (those staying within their CIR) will not be punished as severely when the network core becomes congested, so that parties to SLAs are assured a level of service in accordance with the negotiated fee for that service. However, many factors cause this scheme to become unfair with respect to factors such as bandwidth and delay.
For example, consider what happens between two aggregates, each with different numbers of micro-flows. In an over-provisioned network, the aggregate with a larger number of TCP micro-flows will obtain a greater share of the excess bandwidth, even if both aggregates are within their CIRs. This is because each TCP micro-flow will have a corresponding congestion window with a minimum segment size.
As another example, unfairness may arise from TCP-UDP interactions. In other words, a paying Diffserv customer may inject both TCP and UDP traffic into the network. The UDP traffic, which is unresponsive to congestion in the network, may adversely impact the TCP traffic. Clearly, however, responsive TCP flows should be protected from the unresponsive UDP flows, while maintaining an equal protection for UDP flows which tend to handle multimedia traffic.
Further, there is the effect of different packet sizes in aggregates. Specifically, when two aggregates send different sized TCP packets, the effect is similar two the case where to aggregates contain different numbers of microflows. All else being equal, the aggregate containing the larger packets will consume more of the available bandwidth, because the congestion windows in its TCP flows will grow more quickly.
Traffic latency and delay issues may also arise in DiffServ networks. For example, when congestion occurs in the network due to an offending aggregate, short TCP flows in a non-offending aggregate will get punished by having their traffic queued at the core along with all the other long-lived flows.
Further, inter-packet delay for streaming UDP traffic may vary depending on the presence of competing traffic from other aggregates. Congestion at core network nodes will cause traffic to be delayed by varying amounts, thereby introducing jitter. This can be a serious problem for multimedia UDP traffic.
Finally, the problems mentioned above wherein conformant aggregates are punished because of the congestion caused by non-conformant aggregates becomes even greater when there are multiple congestion points in the core.
SUMMARY OF THE INVENTION
The present invention relates to a method and apparatus for managing aggregate flows of data in a differentiated services computer network.
Generally, the present invention improves fairness in a differentiated services (DS) network by enforcing congestion control at the edges of the network, rather than relying on congestion to accumulate at the core of the network This is done by establishing a credit system for each aggregate flow through the edge. Only if credit is available for the flow will data from an edge node be forwarded to the edge node's DS traffic conditioner where the data packets can be marked using DiffServ labels. If credit is not available, the data will be queued at the edge node.
Each time data belonging to an aggregate flow is forwarded to the traffic conditioner, the amount of credit for the flow is decremented. Credit for the flow is incremented only when control packets can be inserted into the flow. Specifically, the present invention establishes control flows associated with each aggregate flow. A control packet (i.e. a header packet) is injected into the flow for every fixed amount of data belonging to the flow. Credit generation, and hence the queueing of data at the edge, is thus determined by the state (or the congestion window) of the control flow.
In accordance with one aspect of the invention, a method of managing an aggregate flow of data between a first edge device and a second edge device, the first edge device and the second edge device being in packet communication with each other via a network core, comprises the steps of: maintaining an available credit for the aggregate flow, detecting data packets belonging to the aggregate flow at the first edge device, inserting control packets in the aggregate flow at the first edge device, marking the detected data packets and the control packets with labels in accordance with a differentiated services agreement, and controlling the forwarding of the detected data packets to the network core in accordance with the available credit.
In accordance with another aspect of the invention, an apparatus for managing an aggregate flow of data between a first edge device and a second edge device, the first edge device and the second edge device being in packet communication with each other via a network core, comprises: means for maintaining an available credit for the aggregate flow, means for detecting data packets belonging to the aggregate flow at the first edge device, means for inserting control packets in the aggregate flow at the first edge device, means for marking the detected data packets and the control packets with labels in accordance with a differentiated services agreement, and means for controlling the forwarding of the detected data packets to the network core in accordance with the available credit.
In accordance with a further aspect of the invention, an edge device comprises: an aggregate flow control coupled to receive packets from the packet forwarding architecture of the edge device, the aggregate flow control including a classifier that associates certain of the received packets with a plurality of aggregate flows between the edge device and a plurality of receiver edge devices in packet communication with the edge device via a network core, a flow control unit that determines whether to forward the associated certain packets in accordance with corresponding credit available for the plurality of aggregate flows and a control stack that inserts control packets in the aggregate flows and monitors their drop occurrence in the network core, the corresponding credit available for the aggregate flows being adjusted in correspondence with the monitored drop occurrence
Chapman Alan S.
Ethridge Jeremy G.
Lakas Abderrahmane
Nandy Biswajit B.
Nortel Networks Limited
Steubing McGuiness & Manaras LLP
Vincent David
LandOfFree
Method and apparatus for aggregate flow control in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for aggregate flow control in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for aggregate flow control in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310426