Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-08-10
2002-06-11
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395430, C370S412000
Reexamination Certificate
active
06404737
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to Asynchronous Transfer Mode (ATM) telecommunications. More particularly, the invention relates to a method and apparatus which allows both shaped and unshaped virtual circuits (VCs) to be provisioned in a single virtual path (VP).
2. State of the Art
Perhaps the most awaited, and now fastest growing technology in the field of telecommunications is known as Asynchronous Transfer Mode (ATM) technology. ATM is providing a mechanism for removing performance limitations of local area networks (LANs) and wide area networks (WANS) and providing data transfers at a speed of on the order of gigabits/second. The variable length packets of LAN and WAN data are being replaced with ATM cells which are relatively short, fixed length packets. Because ATM cells can carry voice, video and data across a single backbone network, the ATM technology provides a unitary mechanism for high speed end-to-end telecommunications traffic.
Current ATM service is offered in different categories according to a user's needs. Some of these categories include constant bit rate (CBR), variable bit rate (VBR), and unspecified bit rate (UBR). The CBR and VBR categories are subject to a contract where the network service provider guarantees a certain level of service. The UBR category is given the network service provider's “best efforts” after the CBR and VBR categories are serviced.
In an ATM network, an ATM cell is routed on the basis of VPI (virtual path identifier) and VCI (virtual channel identifier) values contained in the cell. On a particular virtual path (VP), defined by the value of the VPI field in the ATM cells on a particular physical link, there may be a number of virtual channels (VCs), each identified by a particular VCI value. As is well known, the VPI and VCI values are neither globally unique nor fixed; the values may change from node to node across a network.
In an ATM switch, traffic on each virtual channel is monitored and routed individually (different VCs on a common VP may, for example be routed differently within the switch). Incoming traffic is normally “policed” to ensure that the incoming traffic of individual VCs is conforming with its traffic contract, and the outgoing traffic is “shaped” to ensure that the outgoing traffic of individual VCs is conforming with its traffic contract (for example to alleviate any cell clumping that may have occurred in the switch), to reduce the risk of cells being discarded by a subsequent policing mechanism. Shaping is not performed on UBR connections.
In certain network configurations, an ATM switch may receive cells from multiple VCs all having a common VPI. Conversely, multiple VCs may be destined for transmission along a single VP over a common physical link. As mentioned above, each VC would conventionally be treated independently; this is required as each is required to meet its QoS (quality of service) objectives.
Prior art
FIG. 1
illustrates portions of a state-of-the-art APEX E-Series ATM switch manufactured by General DataComm, Inc., Middlebury, Conn. The ATM switch includes one or more Line Interface Modules (LIMs)
10
, each of which is associated with an E-Series Controller Card (ECC)
12
, and one Switch Fabric Card
14
through which all of the ECCs are interconnected. On the ingress side of the LIM
10
, the LIM deserializes the incoming bit stream and passes a parallel 16-bit cell stream over to the ECC
12
. Each ATM cell has a fixed length of 53-bytes and its structure is dependent on the switch interface. The User-Network Interface (UNI) cell structure is used if the interface is between the user and the switch. The Network-Network Interface (NNI) cell structure is used if the interface is between switches.
Prior art
FIGS. 2 and 3
illustrate the UNI and NNI cell structures respectively in a 16-bit parallel format. As mentioned above, the routing information for each cell is identified in the VPI and VCI fields. The PT (payload type) field indicates whether the cell contains user information or network management information. The CLP field indicates cell loss priority and the cell header can be checked against transmission errors using the HEC (header error check) field. In the UNI structure, the GFC (generic flow control) field is set to all zeros.
Returning now to prior art
FIG. 1
, the RCMP chipset
16
in the ECC
12
examines each ATM cell received from the LIM
10
. If the connection specified in the cell header has not been provisioned, the cell is discarded. If the connection has been provisioned, and the “policer” has been enabled, the cell is policed according to the user's contract. If the cell is not discarded, internal routing information provided by the VC record table
17
is appended to the cell header. According to the system used by the APEX Switch, three 16-bit words are appended to the beginning of the cell as illustrated in prior art
FIG. 4
for the case of a UNI cell. The CELL ID field has two possible values: 00 for a user cell or host inserted cell and 11 for a backward reporting OAM (operations, administration, and maintenance) cell. The CL field is set to 1 to enable CLP marking. The MGT field is set to 1 to identify a management or extracted cell for the host. The CP field is set to one of four possible cell priority values: 00, 01, 10, 11, where 00 is the lowest priority. Switch Header
1
includes five fields: SCP, Link Dest, Spare, EFCI, and S. SCP is set to 1 for high priority (CP=10 or 11). Link Dest is a three bit address for indicating one of six links (
000
through
101
), for indicating a multicast cell (
110
), and for indicating a management cell (
111
). EFCI is set to 1 to enable EFCI (explicit forward congestion indication) marking. The S field is set to 1 for VPC (virtual path connection) flows and to 0 for VCC (virtual channel connection) flows.
With assistance from an ingress FPGA (field programmable gate array)
18
, the RCMP
16
sends the cell with the appended internal routing information to the switch fabric card
14
. Based on the internal routing information, the switch fabric card
14
routes the cell to the egress side of the desired slot (LIM and ECC pair). At the egress side of the ECC
12
, the MAKER chipset
20
, with the assistance of an egress FPGA
22
(and any buffering provided by buffers
24
) receives the cell from the switch fabric card
14
and performs traffic shaping on shaped connections. Traffic shaping involves three stages: enqueueing, scheduling, and dequeueing.
Referring now to prior art
FIG. 5
, the enqueueing function involves setting up a separate dynamic buffer queue
32
a
-
32
n
and
34
a
-
34
n
for each provisioned VC where the buffer space is allocated according to Equation (1) where T(U) is the per VC queue allowed; Tf is the minimum buffer size set by management software; y is −8 for CBR and rt-VBR, −4 for nrt-VBR, and 0 for UBR; B is the total queue available (65535 for CBR, rt-VBR and UBR, 64511 for nrt-VBR); and U is the total queue usage.
T
(
U
)=
Tf+
(2*exp(
y
)*(
B−U
)) (1)
The amount of per VC queue allowed is used to compare with the total number of enqueued cells via a cell counter (not shown). If the latter is less than the prior, then the cell is enqueued (to a location pointed by a link list free pointer). Otherwise, the cell is discarded.
The cells in each of the buffers
32
a
-
32
n
are scheduled for dequeueing by a VC scheduler
36
which uses a continuous state leaky bucket algorithm from ITU-T I.371 to enforce cell emission rates from multiplexer
38
. The leaky bucket algorithm is used to determine cell emission rates of shaped connections either at a peak shaping rate (PSR) or a sustained shaping rate (SSR). Cells are emitted at PSR if the current bucket level is less than or equal to a predetermined threshold. Otherwise, cells are emitted at SSR. The bucket level is updated after each cell is dequeued for emission and the emission time for the next cell is determined. Once the emis
Cumberton John
Luu Cuong T.
Novick Ronald P.
Ahead Communications Systems, Inc.
Ho Duc
Hsu Alpus H.
Patton & Boggs LLP
LandOfFree
Multi-tiered shaping allowing both shaped and unshaped... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-tiered shaping allowing both shaped and unshaped..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-tiered shaping allowing both shaped and unshaped... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2950476