Method and apparatus for guaranteeing data transfer rates and enforcing conformance with traffic profiles in a packet network
First Claim
1. In a packet-switched communication system including a plurality of data sources and a plurality of destinations, interconnected by a plurality of communication switches, an integrated shaping-scheduling mechanism responsive to shaped packet flows from a first set of data sources and to unshaped packet flows from a second set of data sources, for providing a single, multiplexed output flow of data packets from both the first and the second set of sources, the mechanism comprising:
- a receiver for organizing incoming packets from said plurality of data sources into a plurality of predetermined flow queues, a first partition of flow queues corresponding to shaped packet flows and a second partition of flow queues corresponding to unshaped packet flows, each shaped packet flow being associated with a separate traffic profile, said traffic profile being defined as means for expressing upper limits on the amount of data packets that the packet communication system is allowed to transmit for an associated shaped packet flow;
a plurality of traffic regulators, each traffic regulator being used for determining whether a corresponding flow is classified as either “
virtually compliant”
or “
virtually incompliant”
, where all unshaped flows are always virtually compliant, and shaped flows are virtually compliant as long as their traffic profiles are not close to be violated, and virtually incompliant when their traffic profiles are close to be violated;
a selector for determining the order of transmission of data packets associated with packet flows, the activity of the selector being driven by the values of a plurality of state variables associated with the packet flows;
a flow-dequeue element for removing a just-transmitted packet from its queue and modifying one or more of said plurality of state variables associated with that queue; and
a flow-enqueue element for updating one or more of said plurality of state variables when a new packet reaches the head of one of a plurality of packet queues, each of said packet queues being associated with a respective packet flow.
8 Assignments
0 Petitions
Accused Products
Abstract
A monolithic shaper-scheduler is used for the efficient integration of scheduling and dual-leaky-bucket shaping in a single structure. By making the evolution of the timestamps of the backlogged flows independent of their shaping parameters, the performance drawbacks of prior-art shaping architectures are overcome. The monolithic shaper-scheduler tests each packet flow as being either “virtually compliant” or “virtually incompliant” when a new packet arrives to the head of its queue. The test for “virtual compliance” is based on traffic profiles associated with the flows. The result of the test is used in conjunction with the timestamp and eligibility flag of each packet flow to efficiently schedule the transmission of packets.
118 Citations
20 Claims
-
1. In a packet-switched communication system including a plurality of data sources and a plurality of destinations, interconnected by a plurality of communication switches,
an integrated shaping-scheduling mechanism responsive to shaped packet flows from a first set of data sources and to unshaped packet flows from a second set of data sources, for providing a single, multiplexed output flow of data packets from both the first and the second set of sources, the mechanism comprising: -
a receiver for organizing incoming packets from said plurality of data sources into a plurality of predetermined flow queues, a first partition of flow queues corresponding to shaped packet flows and a second partition of flow queues corresponding to unshaped packet flows, each shaped packet flow being associated with a separate traffic profile, said traffic profile being defined as means for expressing upper limits on the amount of data packets that the packet communication system is allowed to transmit for an associated shaped packet flow;
a plurality of traffic regulators, each traffic regulator being used for determining whether a corresponding flow is classified as either “
virtually compliant”
or “
virtually incompliant”
, where all unshaped flows are always virtually compliant, and shaped flows are virtually compliant as long as their traffic profiles are not close to be violated, and virtually incompliant when their traffic profiles are close to be violated;
a selector for determining the order of transmission of data packets associated with packet flows, the activity of the selector being driven by the values of a plurality of state variables associated with the packet flows;
a flow-dequeue element for removing a just-transmitted packet from its queue and modifying one or more of said plurality of state variables associated with that queue; and
a flow-enqueue element for updating one or more of said plurality of state variables when a new packet reaches the head of one of a plurality of packet queues, each of said packet queues being associated with a respective packet flow. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20)
-
-
14. A method of scheduling service over a plurality of queues holding flows of packet data traffic, the method integrating shaping of packet flows and scheduling of both shaped and unshaped packet flows and defined by the steps of:
-
responsive to receiving a plurality of data packets from a plurality of data sources, identifying for each receiving data packet a respective queue for storage of said data packet;
storing each received data packet in its identified queue;
determining, for each shaped packet flow, a set of traffic-regulator parameters associated with a traffic profile of said packet flow;
for each packet flow, performing a “
virtual-compliance”
test every time a new packet reaches the head of the corresponding flow queue, wherein each unshaped flow is predetermined as being always classified as virtually compliant, and each shaped flow is determined to be classified as virtually compliant as long as the size of its head-of-queue packet does not create the possibility of violating the predetermined traffic-regulator parameters;
selecting a packet for transmission from among eligible packet flows and virtually-compliant packet flows, therefore always excluding from the selection data packets of packet flows that are both non-eligible and virtually-incompliant;
performing a flow-dequeue process subsequent to data packet transmission for recalibrating a plurality of state variables associated with the packet queue of the packet flow of the just transmitted data packet; and
performing a flow-enqueue process upon every arrival of a new packet to the head of a corresponding flow queue.
-
Specification