Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-06-11
2002-04-23
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S468000, C370S230100
Reexamination Certificate
active
06377583
ABSTRACT:
I. FIELD OF THE INVENTION
This invention relates to packet switched communication networks and, more particularly, to traffic shaping for causing the time multiplexed packet flows at queuing points within such networks or network elements to conform to specified traffic descriptors.
II. CROSS REFERENCES TO RELATED APPLICATIONS
For other concurrent filings on traffic shaping see application Ser. No. 08/872,327 now U.S. Pat. No. 6,064,677 by Christopher J. Kappler et al., entitled “Multiple Rate Sensitive Priority Queues for Reducing Relative Data Transport Unit Delay Variations in Time Multiplexed Outputs from Output Queued Routing Mechanisms,” application Ser. No. 08/872,756 now U.S. Pat. No. 6,064,651 by Landis C. Rogers et al., entitled “Rate Shaping in Per-Flow Output Queued Routing Mechanisms for Statistical Bit Rate Service,” U.S. Pat. No. 5,926,459 entitled “Rate Shaping in Per-Flow Queued Routing Mechanisms for Available Bit Rate Service,” by Joseph B. Lyles et al., application Ser. No. 08/868,287 now U.S. Pat. No. 6,038,217 entitle “Rate Shaping in Per-Flow Output Queued Routing Mechanisms for Available Bit Rate (ABR) Service in Networks Having Segmented ABR Control Loops,” by Joseph B. Lyles, application Ser. No. 08/873,064 now U.S. Pat. No. 6,064,650 entitled “Rate Shaping in Per-Flow Output Queued Routing Mechanisms Having Output Links Servicing Multiple Physical Layers” by Christopher J. Kappler et al.
III. BACKGROUND OF THE INVENTION
A. Traffic Contracts/Definitions
Most applications that are currently running on packet switched communication networks can function acceptably with whatever bandwidth they happen to obtain from the network because they have “elastic” bandwidth requirements. The service classes that support these applications is known as “best efforts” service in the Internet community and as “Available Bit Rate” (ABR) in the Broadband ISDN/ATM community.
There is, however, a growing demand for network services that provide bounded jitter or, in other words, bounded packet delay variation (commonly referred to as cell delay variation in an ATM context). For example, this type of service is required for real time applications, such as circuit emulation and video. It is not clear whether and how the Internet community will respond to this demand, but the Broadband ISDN/ATM community has responded by introducing the notion of a user-network negotiated traffic contract.
As is known, a user-network ATM contract is defined by a traffic descriptor which includes traffic parameters, tolerances and quality of service requirements. A conformance definition is specified for each of the relevant traffic parameters. Accordingly, ATM services may make use of these traffic parameters and their corresponding conformance specifications to support different combinations of Quality of Service (QoS) objectives and multiplexing schemes.
Partially overlapping sets of ATM traffic classes have been defined by the Telecommunications Standardization Sector of the International Telecommunications Union (ITU-T) and the ATM Forum. In some instances, traffic classes which have essentially identical attributes have been given different names by these two groups, so the following name translation table identifies the existing equivalent counterparts:
ITU-T Traffic Class
ATM Forum Traffic Class
ABR
ABR
Deterministic Bit Rate (DBR)
Constant Bit Rate (CBR)
Statistical Bit Rate (SBR)
Variable Bit Rate (VBR)
(No existing counterpart, but
Real time Variable Bit Rate (rt-VBR)
understudy)
(No existing counterpart, but
Unspecified Bit Rate (UBR)
understudy)
An ATM service contract for a virtual circuit (VC) connection or a virtual path (VP) connection may include multiple parameters describing the service rate of the connection. This includes the Peak Cell Rate (PCR), the Sustainable Cell Rate (SCR) the Intrinsic Burst Tolerance (IBT), and the Minimum Cell Rate (MCR). Not all of these parameters are relevant for every connection or every service class, but when they are implied or explicitly specified elements of the service contract, they must be respected. VC connections are the primary focus of the following discussion, but it will be understood the VP connections can also be so specified. The data transport unit for an ATM connection usually is referred to as a “cell.” In this disclosure, however, the term “packet” is sometimes used to refer to the data transport unit because this more general terminology is consistent with some of the broader aspects of the innovations.
The Generic Cell Rate Algorithm (GCRA), which is specified in ITU-T Recommendation I.371, is well suited for testing a packet or cell flow for conformance with a traffic descriptor. To perform such testing, the GCRA requires the specification of an emission interval (i.e., the reciprocal of a flow rate) and a tolerance, &tgr;. In practice, this tolerance may depend on a variety of factors, including the connection, the connection setup parameters, or the class of service. As will be seen, the GCRA can be employed as a Boolean function, where for a flow of fixed size packets or cells on a connection, the GCRA (emission interval, tolerance) is false if the flow is conforming to a peak rate or true if the flow is conforming to a minimum rate. For example, a source of cells conforms to a PCR if GCRA (1/PCR, &tgr;
PCR
) is false. Likewise, a connection or flow conforms to an MCR if GCRA (1/MCR, &tgr;
MCR
) is false. As will be appreciated the “emission interval” is the reciprocal of the “cell rate.”
A DBR traffic contract is appropriate for a source which establishes a connection in the expectation that a static amount of bandwidth will be continuously available to the connection throughout its lifetime. Thus, the bandwidth the network commits to a DBR connection is characterized by a PCR value. Further, the cell or packet flow on such a connection complies with the traffic contract if it conforms to GCRA (1/PCR, &tgr;
PCR
). On the other hand, an SBR traffic contract is suitable for an application which has known traffic characteristics that allow for an informed selection of an SCR and &tgr;
IBT
, as well as a PCR and &tgr;
PCR
. An SBR or rt-SBR flow complies with its traffic contract if the flow not only conforms to GCRA (1/PCR, &tgr;
PCR
), but also to GCRA (1/SCR, &tgr;
IBT
).
As previously indicated, an ABR traffic contract is appropriate for applications that can tolerate the dynamic variations in the information transfer rate that result from the use of unreserved bandwidth. A PCR and an MCR are specified by the source establishing such a connection, and these parameters may be subject to negotiation with the network. Thus, the bandwidth that is available on an ABR connection is the sum of the MCR (which can be 0) and a variable cell rate that results from a sharing of unreserved bandwidth among ABR connections via a defined allocation policy (i.e., the bandwidth a source receives above its specified MCR depends not only on the negotiated PCR, but also on network policy). Feedback from the network enables the source application to dynamically adjust the rate it feeds cells or packets into an ABR connection. An ABR flow always complies with its traffic contract if it conforms to GCRA (1/MCR, &tgr;
MCR
), and is always non-compliant if it does not conform to GCRA (1/PCR, &tgr;
PCR
). Conformance in the region between MCR and PCR is dependent on the ABR feedback and is thus dynamically determined.
A UBR traffic contract is similar to the ABR contract, except that the UBR contract does not accommodate the specification of an MCR and has no dynamic conformance definition. Therefore, a UBR flow complies with its traffic contract if it conforms to GCRA (1/PCR, &tgr;
PCR
).
B. Traffic Shaping
ITU-T Recommendation I.371 addresses the possibility of reshaping traffic at a network element for the purpose of bringing the traffic into conformance with a traffic descriptor in the following terms:
“Traffic shaping is a mechanism that alters the traffic characteristics of a stream of cells on a VCC or a VPC to achieve a desired mod
Kappler Christopher J.
Lyles J. Bryan
Rogers Landis C.
Lee Andy
Nguyen Chau
LandOfFree
Rate shaping in per-flow output queued routing mechanisms... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rate shaping in per-flow output queued routing mechanisms..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate shaping in per-flow output queued routing mechanisms... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2864739