CN1323530C - System and method for realizing GFR service in ATM switching equipment of access node - Google Patents

Abstract

A scheme for implementing GFR service in an ATM environment, e.g., an access node's ATM switch fabric. Regulation of a GFR flow is throttled between two modes, a guaranteed rate mode and a non-guaranteed rate mode, depending upon timestamps computed by applicable traffic policer/shaper algorithms. A scheduler is operably coupled to a policing block for scheduling cells from a guaranteed flow queue for transport via the ATM fabric at a guaranteed rate upon determining the onset of a guaranteed service frame. The scheduler switches to non-guaranteed rate mode for scheduling cells from the flow queue at a non-guaranteed rate when a timestamp (TSNGF) for transmission at the non-guaranteed rate is earlier than a timestamp (TSGF) for transmission of a next guaranteed service frame at the guaranteed rate.

Description

System and method for realizing GFR service in ATM switching equipment of access node

related application

The subject matter disclosed in this application is related to that disclosed in the following commonly-owned, co-pending U.S. patent applications: (i) James W. Dove et al., "Stackplane Architecture," filed December 22, 1999, Application No. 09/ 469,897; (ii) Eric Friedrichs et al., "Scalable Architecture For An Access Node," filed June 27, 2002, application number 10/280,604; (Attorney Docket: 1285-0090US); (iii) Thornton Collins "Integrated Gateway Functionality In An Access Network Element", filed on November 2, 2001, with application number 10/052,846; (iv) "Multicasting System And Method For Use In An Access" by Mudhafar Hassan-Ali et al. Node's ATM Switch Fabric", filed on the same day, US Application No. 10/280,959; (Attorney Docket No.: 1285-0100US); (v) "Virtual GroupConnection Scheme For ATM Architecture In by Mudhafar Hassan-Ali et al. An Access Node", filed on the same day, U.S. Application No. 10/280,604; (Attorney Docket No.: 1285-0099US); (vi) "Calendar Heap System And Method For Efficient Sorting," by Mudhafar Hassan-Ali et al. , filed on the same day, U.S. Application No. 10/281,033; (Attorney Docket No.: 1285-0101US); (vii) "Hierarchical Scheduler Architecture For Use With An Access Node," by Mudhafar Hassan-Ali et al., filed on the same 10/280,894; (Attorney Docket: 1285-0103US); these patent applications are incorporated herein by reference.

technical field

The present invention relates generally to the field of telecommunications. More particularly, but not limited thereto, the present invention relates to a system and method for implementing Guaranteed Frame Rate (GFR) service in an Asynchronous Transfer Mode (ATM) switching device of an access node.

Background technique

The remote access market is undergoing a major transformation. Three factors contributed to this shift. The first is the growth in the number of users, such as small office/home office (SOHO) users who require high-performance Internet and multimedia remote access. Government action to liberalize telecommunications is another factor, fostering broader competition by removing local market norms. The third and final factor is congestion in the public switched telephone network (PSTN), which was originally designed and developed for voice traffic only.

Several major advances in telecommunications technology have enabled high throughput in the backbone connections of telecommunications networks. For example, telecommunications networks can achieve data rates of several hundred megabits per second (Mbps) by implementing Asynchronous Transfer Mode (ATM) networking technology on a Synchronous Optical Network (SONET)/Synchronous Digital Hierarchy (SDH) physical layer. However, efforts to meet the bandwidth demands of remote access are limited by the existing twisted-pair copper infrastructure (i.e., the access network) between the telecom central office (CO) and the customer's remote site. Commonly known as the local loop. In the field of telecommunications, these constraints are sometimes collectively referred to as the "last mile" problem.

To avoid bottlenecks caused by the last mile problem, current access network solutions also use fiber optic technology in the local loop. As with the use of high-speed telecommunications networks, the architecture of fiber-based local loop infrastructure generally uses SONET as the physical layer technology. In addition to improvements in network design, recent advances in optical components and related optoelectronics have made broadband access more pervasive.

Furthermore, the dramatic growth in the number of Internet users has aroused interest in replacing the existing infrastructure used by current telecommunications networks with packet-switched network (PSN) infrastructures, such as those based on Internet Protocol (IP) addressing. Strong interest in circuit-switched network (CSN) infrastructure. From a network operator's perspective, the sheer volume of traffic inherent in the packet-switched infrastructure enables lower transport and infrastructure costs per end user. Ultimately, this cost reduction enables network operators to pass on the resulting savings to end users.

Therefore, a new type of service-centric network (different from the existing voice-centric and data-centric networks) is being developed to implement the well-known Next Generation Network (NGN) infrastructure, in which the Integrated voice/data/video applications in the infrastructure can be provided using packet transport mechanisms over the PSN in the end-to-end transport path. Alluded to earlier, it is believed that the use of packet network infrastructure in the access network can provide higher transmission efficiency, lower operating and operating costs, and uniform access.

Traditional access systems allow access to digital local voice switches, such as Category 5 switches, by extending multiple metal rings and grouping them into a bundle to efficiently carry time-division multiplexed (TDM) voice traffic. Generally, the architecture of this access network uses one or more access nodes in various configurations. The aforementioned configurations may be, for example, point-to-point chains, rings, etc., wherein the access nodes themselves may include multiple channel groups. The line interface provided by the operator serves a large number of users.

However, in order to provide better functions and services, the current access network is required to support advanced transmission technologies, such as SONET, and the same is true for the internal structure of nodes. In these nodes, ATM is used to bear the weight of most user traffic except traditional TDM business, such as T1 and TDM-DS3 business. Therefore, the access node design needs to support TDM and ATM switching equipment.

The ATM Forum provides a set of specifications to manage different aspects of ATM switching equipment, including traffic policing/shaping functions that support different classes of service (CoS), such as constant bit rate (CBR), variable bit rate (VBR ), Guaranteed Frame Rate (GFR) and similar classes of traffic. Although specific data applications are particularly urgent to provide GFR services, the standard ATM specification does not give specific implementation or design details.

On the other hand, it was found that the known GRF implementations in current ATM applications are deficient in certain important problems. First, existing GRF schemes usually require the use of large amounts of memory because the buffer structures they use are shared between the guaranteed and non-guaranteed parts of the GFR stream. Furthermore, combining these schemes is not diverse enough to match the applicable GFR service attributes in the ATM specification.

Contents of the invention

Therefore, the present invention provides a solution for implementing GFR services in an ATM environment (such as an ATM switching device of an access node), which effectively overcomes the aforementioned disadvantages. According to the timestamp calculated by the traffic policer/shaper algorithm used, the adjustment of GRF flow is switched between two modes, guaranteed rate mode and non-guaranteed rate mode, so that when the bandwidth is available, it can achieve higher than the minimum The rate at which the rate is guaranteed.

In one aspect, the present invention relates to a method for implementing a Guaranteed Frame Rate (GFR) service in an access network element having an Asynchronous Transfer Mode (ATM) switching device, comprising the steps of compressing an identified incoming cell for Guaranteeing the service Enter the guaranteed flow queue; when it is determined to ensure that the service frame starts, dispatch cells from the guaranteed flow queue, and transmit with the guaranteed rate by the ATM switching equipment; determine the future time stamp (TS _GF ) of scheduling the next guaranteed service frame ); determine the future timestamp (TS _NGF ) of scheduling cells at a non-guaranteed rate from the guaranteed flow queue; when the TS _NGF is earlier than the TS _GF , schedule cells from the guaranteed flow queue to The non-guaranteed rate transmission; and, when arriving at the TS _GF , scheduling cells of the next guaranteed service frame to be transmitted at the guaranteed rate.

In another aspect, the present invention relates to a system for implementing Guaranteed Frame Rate (GFR) services in an access network element having an Asynchronous Transfer Mode (ATM) switching device, comprising: a GFR supervisory block configured to Incoming cells for guaranteed services are pushed into guaranteed flow queues; a scheduling device, when determining the start of a guaranteed service frame, dispatches cells from the guaranteed flow queues, and transmits them at a guaranteed rate through the ATM switching equipment; determines scheduling means for the future time stamp (TS _GF ) of the next guaranteed traffic frame; means for determining the future time stamp (TS _NGF ) for scheduling cells from the guaranteed flow queue at a non-guaranteed rate; when the TS _NGF is earlier than the The TS _GF is a device for scheduling cells from the guaranteed flow queue to be transmitted at a non-guaranteed rate; and, when arriving at the TS _GF , a device for scheduling cells of the next guaranteed frame to be transmitted at the guaranteed rate .

Description of drawings

Through following detailed description, in conjunction with accompanying drawing, can have more comprehensive understanding to the present invention, in accompanying drawing:

Fig. 1 has provided exemplary access node, can realize content of the present invention advantageously in the ATM switching equipment of this node;

Fig. 2 has provided a kind of implementation mode of multi-layer multi-plane dispatcher, and it realizes GFR service in the ATM switching equipment shown in Fig. 1;

The high-level functional block diagram that Fig. 3 describes has illustrated the scheduler leaky bucket module and the priority queue module that realize content of the present invention;

Figure 4 is a flowchart illustrating various operations used in an exemplary method of implementing GFR services in accordance with the teachings of the present invention;

Fig. 5 has provided the system that realizes the GFR service of the present invention;

Figure 6 is a representation of the GFR regulatory scheme;

The flowchart in Figure 7 describes the operations used in the GFR regulatory scheme;

Figure 8 is a flowchart describing the operations used in timeout handling in accordance with the teachings of the present invention; and

Figure 9 shows the multi-segment timing window scheme for verifying the expiration time value.

Detailed ways

According to the U.S. patent application titled "HierarchicalScheduler Architecture For Use With An Access Node" submitted by Mudhafar Hassan-Ali et al. One embodiment of the present invention is presented based on the teachings of the US Patent Application (hereinafter referred to as the Hierarchical Scheduler Architecture Application), which is incorporated herein by reference. It is detailed in that application that the telecommunications nodes in the access network may include a scalable architecture in which TDM and ATM switching equipment is provided to support increased levels of performance.

In addition, the scheduling function associated with the ATM switching device can be based on the service category (that is, the service plane), and across multiple levels of data pipeline sets (that is, sub-port, bus level, shelf level, stack level, and pipeline level, etc., as various aggregation layers), which is necessary for scalable hardware architectures, so that traffic contract compliance, as well as the necessary connection isolation and fair bandwidth allocation can be effectively achieved in the ATM switching equipment of the access network nodes .

Referring now to the drawings of this patent application, wherein the same or similar elements are marked with the same reference numerals in several figures, the various elements given are not necessarily drawn to scale, especially with reference to Figure 1, which depicts a An exemplary access node 100 has a high level functional representation of an ATM switching device 102 which may advantageously implement the teachings of the present invention. As explained in the previously referenced Hierarchical Scheduler Architecture application, the general functions of switching device 102 include: supervision; operations, administration and maintenance (OAM); header translation; queuing and admission control; and scheduling and traffic shaping. It can be easily seen that traffic destined for switching device 102 is provided through multiple interfaces. The transmission interface 104 is used to connect the equipment of the node to the backbone network, such as the ATM network 105 . The stack interface 106 is used to link the traffic from the auxiliary rack group chain 107 (for example, the channel group 506-1 to 506-4 shown in Figure 5 including the hierarchical scheduler architecture application, and the channel group 508-1 to 508-4 ) to the switching device 102. Various service sources such as xDSL, T1, ISDN, DS-3/OC-3, etc. are exemplified by multiple user interfaces through line units (LU) 107-1 to 107-N, which may be routed through appropriate bus Level ports 109 - 1 to 109 -N are connected to the switching device 102 . One of the line unit interfaces may be connected to RT 111 which is part of an access network (not shown in the figure).

Two types of ATM connections can be defined for internal ATM traffic: virtual channel connection (VCC) and virtual channel connection (VPC). VCC is generally the smallest unit that an ATM connection can have, and can be represented by a unique value including a pair of identifiers on a physical interface, that is, a virtual channel identifier (VCI) and a virtual channel identifier (VPI). A VPC is defined as a group of all flows that share the same VPI value and common resource pool (such as bandwidth, etc.). Thus, it can be seen that a VP is a bundle of VCs, which simplifies connection management in an ATM environment by reducing the number of components to be managed, where each connection is identified by its unique VPI/VCI pair.

From a topological point of view, a VCC or VPC can be one of two types: (i) point-to-point connection, where a bidirectional connection is established and the sources in each direction can be different, and (ii) point-to-multipoint Connection, which usually uses multiple unidirectional connections to implement multicast transmission between devices.

In addition, another layer of ATM connection hierarchy, called Virtual Group Connection or VGC, can also be implemented in the present invention. Details about the implementation of VGC are submitted on the same day by Mudhafar Hassan-Ali et al. entitled "Virtual Group Connection Scheme For ATMA Architecture In An Access Node", U.S. Patent Application No.: 10/280,604; (Proxy Docket No.: 1285-0099US) is given in a commonly owned co-pending US patent, which is incorporated by reference.

Thus, ingress traffic management of flows entering switching equipment 102 (which may function in the form of ATM cross-connect switching equipment (XCF) cards) generally includes three phases: policing, VC queue/buffer allocation, and shaping/scheduling. In one embodiment, the hardware associated with these stages can be integrated into the XCF card. The main function of the policer is to ensure that received cells are consistent with the applied connection descriptor. If they are inconsistent, the incoming cells can be discarded or marked (that is, marked) by clearing/setting the cell drop priority (CLP) in the cell header. Generally, supervisory functions are implemented using well-known algorithms described in the ITU-T1.371 and ATM Forum ATMF-TM-121 standards. In fact, these algorithms (commonly known as the Generalized Cell Rate Algorithm or GCRA) employ so-called credit counters, called buckets, and credits, called tokens. When a cell is received, if the counter (ie bucket) has enough credits (ie token), then the cell is admitted; otherwise, the cell is marked as a low priority cell or discarded. Furthermore, as explained in the Hierarchical Scheduler Architecture Application, GCRA-based algorithms can be implemented in so-called Leaky Bucket Modules (LBMs) for several ATM classes of service (based on class of service (CoS) ordering, where the class of traffic is represented by Traffic policing and traffic shaping (ie, scheduling) defined by factors such as time sensitivity, peak and sustained bandwidth guarantees, burstiness and delivery guarantees.

The hierarchical scheduling function is implemented through the Priority Queue Module (PQM) (not shown in the figure), wherein each layer implements the scheduling function for the entry, and according to the flow set, the entry can be one of the following: sub-port, bus, port, and pipe . In practice, when a switching device receives a cell of a new flow, the data flow is represented by an entry in the scheduler as follows. Received flow ID (that is, FID) from LBM, based on CoS/QoS, flow data (that is, FID and timestamp or TS), is stored in the first layer data structure of the application. Among all competing sub-ports in the first layer (such as different streams of line units), the layer arbiter will only select a sub-port with the smallest TS, and then forward it to the arbitration mechanism of the next layer, that is, the second layer arbitration. The second-level data structure correspondingly contains "winning FID/TS" data of different subports. Likewise, only one entry with the smallest TS is selected and forwarded to the third layer. This process is repeated for other aggregation layers, and finally the winning nomination of each service priority class (that is, the FID/TS data of the winning cell) is obtained. It is also pointed out in the layered scheduler architecture application that this layer-based arbitration is performed for each service class plane, resulting in a winner nomination for each plane, such that a timestamp-based arbitrator considering CoS The winners will be arbitrated to select the final winner.

Thus, it should be appreciated that arbitration of each tier involves managing the PQ structure associated therewith for selection of the winner for that tier. In general, the PQ structure is implemented in the form of a tree, where data nodes (representing eg TS/FIDs of admitted cells or cells selected by lower layers) are arranged according to certain insertion/deletion criteria. FIG. 2 shows an implementation manner of a multi-layer and multi-plane scheduler 200, which implements a scheduling function in the ATM switching device shown in FIG. 1, and provides services for MC flows. Each PQ entity of the scheduler 200 of each aggregation layer is shown in a tree structure, and the total nested tree solution of each service plane is obtained. The following table shows various exemplary services and related parameter information:

Table 1

Service category Application Parameters Real-time constant bitrate (CBR), real-time variable bitrate (rt-VBR) Voice (single channel or trunk), VBR video, game Peak Cell Rate (PCR), Cell Delay Variation Tolerance (CDVT) Non-real-time variable bit rate (nrt-VBR) data, multimedia, email, video streaming PCR, CDVT, Sustainable Cell Rate (SCR), Maximum Burst Size (MBS) Guaranteed Frame Rate (GFR) Additional Data, Browse Pages, Internet PCR, CDVT, MBS, Maximum Cell Rate (MCR), Maximum Frame Size (MFS) Best effort (no bitrate or UBR specified) Cheap Data, Page Views, and the Internet PCR, CDVT

Additional details related to parameter data and QoS levels can be found in the Hierarchical Scheduler Architecture application. Continuing with Figure 2, the labels 206-1 to 206-6 refer to the following service planes respectively: rt[CBR/VBR]-high plane, rt[CBR/VBR]-middle plane, rt[CBR/VBR]-low plane, nrt- VBR and GFR planes, GFR planes, and UBR (ie, best available) planes. Reference numeral 208 refers to a PQ tree corresponding to the subport arbiter 1305-i, wherein the PQ tree is generated based on the VC connections supported by the corresponding subport. In fact, each subport of the scheduler adopts (or constructs) a PQ, which is a data structure storing all active FIDs (that is, the VC queue related to the FID has at least one cell). The winners of all subport arbiters (eg, subport arbiters 222-i and 222-j) are forwarded, populating the next level of PQ tree structure 210 associated with bus level arbiter 224-1. Likewise, bus-level arbiters 224 - 1 and 224 - k forward the respective selections to shelf-level PQ fabric 212 . Shelf level arbiter 214, stack interface 216, transport layer interface 218 forward their selections to pipe level arbiter 220, which selects a winning nomination for a particular traffic plane.

Various data structures can be used to implement the tree-based PQ used in the hierarchical scheduling proposed in this patent application. In an exemplary embodiment of the present invention, the PQ entity may be implemented in a heap structure. While a heap implementation typically excels in memory usage, it is limited by its algorithmic complexity, which can limit throughput in high-speed designs. Therefore, in another implementation, each layer-specific PQ entity is implemented as a comprehensive "calendar heap" structure, the detailed description of which is presented by Mudhafar Hassan-Ali et al. Heap System And Method For Efficient Sorting," U.S. Application No. 10/281,033; (Attorney Docket: 1285-0101US), which is incorporated by reference.

Referring now to FIG. 3, a high level block diagram is shown illustrating a switching equipment card 300 including a scheduler block 310 for implementing GFR traffic in an access node in accordance with the teachings of the present invention. Scheduler block 310 includes PQM 302 and LBM 308, a number of interfaces between which enable message/data communication related to scheduler operations. These interfaces include expire interface 314 , winner stream interface 316 , stack/flow reconnect interface 318 , and stack/flow insert interface 320 . The PQM block 302 also interfaces with a plurality of memory blocks 304-1 through 304-4 for storing various PQ data structures associated with the hierarchical scheduler architecture described above. A control memory 306 connected to the PQM block 302 stores control program code related to the operation of the PQM.

LBM block 308 also interfaces with one or more memory blocks, such as memory 312, for storing information related to the LBM-implemented policing and shaping algorithm processing. In one implementation, the LBM uses a leaky bucket calculator as a state machine that decides whether a cell is eligible or not based on the traffic contract and the history of the connection it belongs to. When used for supervision, the state machine determines whether the incoming cell meets the requirements, and when used for shaping, it determines the moment when the cell meets the service requirements. According to different business categories, one or more specific algorithm processing with specific parameters (that is, traffic descriptors, leaky bucket parameters (theoretical arrival time or TAT, TS value, cell arrival time, etc.) Realize the supervision and shaping operation of LBM. Will describe in detail below, the GFR service of the present invention adopts two kinds of different algorithm LBs to process and realize, and every kind of algorithm has different parameter sets, can be used for adjusting respectively to guarantee flow part and non-guaranteed flow part.

The LBM block 308 is also interfaced with a context memory module (CMM) 332 and a queue core module (QCM) 332 to realize its overall function and maintain leaky bucket information for all flows served by the ATM switching device. The cell arrival interface 348 associated with the CMM block 332 serves as the entry point for incoming cells. A context store 334 associated with the CMM module 332 is used to store flow-based information such as QoS, FID, leaky bucket parameters, destination path tag (DPT) information, and the like. Additionally, a statistics memory block 336 may be provided for collecting performance monitoring data related to the connections serviced by the ATM switching equipment card 300 . Ingress flow context information and egress flow context information are provided to QCM block 322 via interfaces 338 and 340, respectively. Head/tail pointer memory 352 and statistics memory 354 are connected to QCM block 322 . The cell pointer interface 356 associated therewith points to cells that meet traffic conditions based on scheduling operations.

The interfaces between the QCM block 322 and the LBM block 308 include the following interfaces: flow activation interface 324 , flow reconnection and deactivation interface 326 , close connection interface 328 and timeout interface 330 . The winning cell interface 342 provided between the LBM block 308 and the CMM block 332 is used for sending related information of the winning cell. Additionally, a clock management block 344 and a processor interface module 346 having a processor interface 350 are provided.

Considering the various structural blocks described above, the overall functionality of the LBM block 308 includes the following:

Flow Activation: When a cell arrives or the cell buffer associated with its FID was previously empty, the QCM sends a Flow Activation message to the LBM. This interface contains the information found in the context store associated with the stream.

Winning streams and stream reconnection/deactivation: When a PQM selects a certain stream as a winner, the stream is removed from the different heaps it belongs to (e.g. according to the aggregation layer). If there are remaining cells in the cell buffer of a particular flow, the LBM recalculates the TS value and reconnects the flow in the PQ data structure. If there are no cells left, the LBM calculates the TS value of the flow and stores it in the leaky bucket until another cell of the flow arrives.

Close the connection: If the CAC suppresses a flow, the cell buffer is cleared and the FID can be reused for other connections. To prevent old parameters from being used for new connections, the LBM must be notified that the stream is no longer valid.

Timeouts: Check leaky bucket storage, preferably periodically, to prevent storage expiration times.

FIG. 4 is a flowchart illustrating various operations used in an exemplary method of implementing GFR service in an ATM device in accordance with the teachings of the present invention. When cells arrive (block 402), the GFR policing mechanism performs traffic policing so that eligible cells are correctly entered into guaranteed flow queues (block 402). In one implementation, the policer can use the CLP bit to mark the cell in case of non-compliance; the cell can then be queued in a buffer with a threshold GFR _TH . At this point, an appropriate cell discarding mechanism can be employed, which is described in detail in the Hierarchical Scheduler Architecture application.

In fact, the shaping of the GFR flow enables two independent sub-flows, one of which is generated using GCRA processing with traffic descriptor parameters Peak Cell Rate (PCR) and Cell Delay Variation Tolerance (CDVT), the other A stream generation utilizes a process called Frame GCRA or F-GCRA, which has Maximum Cell Rate (MCR) and Maximum Burst Size (MBS) parameters in addition to PCR and CDVT parameters. After determining that the start of the frame is guaranteed (ie, guaranteed service frame start), the cells of the guaranteed flow queue including the frame are adjusted for guaranteed rate transmission using GCRA processing (block 404). As mentioned elsewhere, the guaranteed rate can be predetermined according to the traffic contract employed. At the end of the guaranteed service frame adjustment (ie, the last cell of the frame is scheduled), the future time stamp (TS _GF ) of the next guaranteed service frame is determined using F-GCRA processing (block 406). The TS _GF is inserted into the appropriate PQ buffer associated with the guaranteed traffic sub-flow. Another timestamp, denoted TS _NGF , is also determined using GCRA processing in the LBM and is used to schedule cells from the guaranteed flow queue for transmission at the non-guaranteed rate (block 408). The TS _NGF is inserted into the PQ buffer, which can be used for non-guaranteed traffic rates, such as best available traffic or UBR traffic.

Switching from guaranteed mode of scheduling (i.e. GFR mode) to non-guaranteed mode (i.e. "GFR-" mode, which can be based on UBR) is based on two future timestamps, namely the TS _GF and TSN _GF calculated previously proposed value. A decision is made to verify whether the TS _NGF value is less than the TS _GF value; in other words, whether TS _NGF occurs earlier than TS _GF . If so, switch the flow to non-guaranteed mode, ie, schedule cells from the queue to be sent at a non-guaranteed rate (block 410), where the GCRA handles shaping the UBR/BE traffic flow. When the TS _GF time is up, the flow mode switches back to GFR mode, wherein the cells of the next guaranteed traffic frame are scheduled to be sent at a predetermined guaranteed rate (412). Furthermore, if any cells of incomplete frames are scheduled by UBR mode when switching to GFR mode, these uncompleted frames are discarded.

Referring now to FIG. 5, an exemplary system 500 for implementing the GFR service of the present invention is shown. Alluded to earlier, a GFR regulatory block 502 is provided to ensure compliance with traffic contracts using CLP based marking. Ingress marked cells are pushed into the queue using guaranteed flow queue 504 with an appropriate threshold. The algorithm processing mechanism 506 forms part of the LBM block described above, which calculates the two types of timestamps required to switch between GFR and UBR modes. Obviously, the function of the algorithm processing mechanism 506 can be realized by hardware, software or any combination of the two. Reference numeral 508A represents a PQ structure (that is, a stack) associated with the GFR scheduling mode for sending GFR cells, and the aforementioned GFR cells can be considered to be sent from the subflow queue 510A involving guaranteed service frames. Likewise, reference numeral 508B represents the PQ structure associated with the non-guaranteed rate mode for sending UBR/BE cells, which can be considered to be sent from the sub-flow queue 510B. As explained above, the algorithm processor block 506 calculates the future time stamp based on GCRA and F-GCRA processing at the end of the guaranteed service frame, and switches between guaranteed and non-guaranteed modes according to the TS value.

Figure 6 is a graphical representation of a GFR regulatory scheme that can be implemented with respect to the present invention. The GRF regulatory scheme consists of two phases, both of which involve leaky bucket implementations. The first stage is to determine whether the packet (or frame) is eligible. This is done by testing the following conditions: (i) cell arrival consistent with available GCRA capabilities with PCR and CDVT descriptors; (ii) all cells in a frame have the same CLP value; and (iii) frame size does not exceed MFS value. Reference numeral 602 represents the portion of the cell stream examined by the GCRA process. The second stage (also a leaky bucket implementation) works at the frame level, using F-GCRA processing with appropriate traffic descriptor parameters. Reference numeral 604 represents the portion of the cell stream examined by the F-GCRA process. It should be understood that the final result of implementing GFR supervision is to distinguish eligible frames guaranteed to be sent by the MCR from unqualified frames that may be considered to use UBR/BE type services. The flowchart of Figure 7 describes additional details of the GFR regulatory approach. When the ta cell arrives (block 702), it is determined whether the cell is the first cell of the frame (block 704). If so, certain calculations and comparisons involving leaky bucket parameters are performed, as shown in blocks 706 and 708, where X represents the value of the leaky bucket counter, LPT is the last pass time, and X' is an auxiliary variable. If X' is greater than L or the cell has its CLP set (that is, CLP=1), then the frame is considered non-compliant. Therefore, either the best available schedule or an appropriate drop strategy is implemented (block 710). Otherwise, the frame is considered eligible and the bucket counter and LPT parameters are calculated as shown in block 712 . As such, eligible frames are scheduled at the guaranteed rate (block 714).

If the cell is not the first cell of the frame, another decision is made to determine if the cell belongs to an eligible frame (decision block 716). If yes, certain LB parameters are calculated in block 720, where LPT is set equal to t _a . Thereafter, guaranteed rate scheduling is performed on eligible frames (block 722). On the other hand, if the cell does not belong to a guaranteed frame, then implement the best available scheduling or implement an appropriate drop policy (block 718).

Those skilled in the art will recognize that one of the problems with computing LB parameters (TS, TAT, etc.) with the algorithms previously proposed for GFR implementations is that the available word sizes to represent the parameters and the system clock are limited. Therefore, once all counters and clocks employed in the LB calculation reach their respective limits, they roll over back to 0. Of course, this limitation is not limited to GRF traffic; any CoS implementation involving LB-based computation suffers from the same problem. Because of this hardware limitation, after performing an LB parameter update, there could be a potential problem where a connection's flow queue becomes empty. One solution is to store the update results and associate them with the incoming flow queue. Later, when the flow becomes active again and the first cell of the flow arrives, the stored LB data can be used. However, there is no mechanism to indicate if this clock has rolled over, so that the stored values are no longer valid (because they are "invalidated"). As such, some improvement is needed to track and maintain parameter data without risk of failure. In addition, it is desirable to have a scheme similar to background processes to minimize the impact on throughput.

The present invention advantageously provides a solution to the problems raised in the preceding discussion. In fact, the algorithm handles the timeout conditions used to determine the LB parameters involved in various CoS implementations. Upon detection of a timeout condition, the new value is substituted, and the stream that is active again can participate in scheduling when appropriate. The flowchart of Figure 8 describes the operations used in timeout processing in accordance with the teachings of the present invention. Time update processing 802 is preferably implemented as a background process. As alluded to earlier, the LB parameters are calculated based on the traffic class; thus, a determination is made regarding the CoS involved (block 804). For CBR/UBR type, check TAT1 (single barrel TAT) and TS (block 806A). For VBR services, check TAT1, TAT2 (double-barrel TAT value) and TS. Likewise, for GFR/UBT+ traffic, in addition to the TAT1 and TAT2 values, two timestamps (TS=TS _NGF and tf/TS+=TS _GF ) are checked (block 806C). Then, it is determined whether any of these values has an expired value (decision block 808). If not, processing continues into a loop (block 822). Decision block 810 determines whether any expiration time values are stored in the PQ tree. If so, another determination is made for the multicast connection (decision block 812). If a time value is associated with a multicast connection, the expiration interface (shown in Figure 3) between the LBM and PQM is used to delete the expired tree and insert a new time value. New values are also provided to the LBM. These operations are fixed as block 814 . The timeout interface between LBM and QCM is used to clear the cell buffer if the connection is not multicast. Afterwards, using the expire interface, the flow is removed from the tree. Then, set the FC parameter to 0 in the LBM. Block 816 consolidates these operations in the flowchart. If no expiration time values are stored in the PQ tree (decision block 810), only new values are provided to the LBM; no expiration or timeout interfaces are available for deletion or purge (block 820).

FIG. 9 shows a multi-segment timing window 900 for verifying expiration of time-related parameter values in accordance with the teachings of the present invention. Timing window 900 is composed of four segments 902A-D of predetermined duration, forming two trees 904A and 904B, each consisting of two segments. Expiration verification is performed twice in window 900; once in the first segment 902A to verify that the time used in the second tree 904B has expired, and a second time in the third segment 902C to verify the first tree 904A Whether the time used in has expired. When the actual time reaches the predetermined value for the appropriate time period, the check starts. If the PQM allows expiration processing (that is, processing has enough time to process the expiration command), then at each cell period, the expiration block checks the timing parameters associated with a flow. As can be seen earlier, depending on the CoS, up to 4 time values need to be checked. A time value is considered out of date when its most significant bit (MSB) differs from the MSB of the actual time. Additionally, a connection is considered expired if it is checked that a time value associated with the connection has expired. Afterwards, provide appropriate processing to update the new time value as described previously.

Based on the foregoing discussion, it should be understood that the present invention provides an innovative solution for realizing GFR services in an ATM environment, which effectively overcomes the defects and deficiencies in the current GFR implementation. The aforementioned ATM environment can be a switch in an access node. equipment, or a transmission network within a region. By processing the guaranteed and non-guaranteed parts of a cell flow into two distinct subflows, with associated traffic shaping rules, not only is the overall memory requirement reduced, but throughput is also improved. In addition, those skilled in the art can easily understand that although the multicast scheme of the present invention is proposed for the hierarchical scheduler of the ATM switching equipment of the access node, the technologies included here are not limited to this environment; they can also be used in other implemented in ATM applications.

The operation and construction of the present invention are believed to be apparent from the foregoing detailed description. The embodiments of the invention shown and described are exemplary and it is to be understood that various changes and modifications may be made without departing from the scope of the invention as set forth in the appended claims.

Claims (12)

1. A method for realizing a guaranteed frame rate service in an access network element with an ATM switching device, comprising steps: Push the identified incoming cells for guaranteed services into guaranteed flow queues; When it is determined that the guaranteed service frame starts, scheduling cells from the guaranteed flow queue, and transmitting at a guaranteed rate through the asynchronous transfer mode switching device; Determine the future timestamp for scheduling the next guaranteed service frame; determining a future timestamp for scheduling cells from the guaranteed flow queue at a non-guaranteed rate; When the future time stamp of the scheduled cell at the non-guaranteed rate is earlier than the future time stamp of the scheduled next guaranteed traffic frame, scheduling cells from the guaranteed flow queue for transmission at the non-guaranteed rate; and When the future time stamp of the scheduled next guaranteed service frame arrives, the cells of the next guaranteed service frame are scheduled to be transmitted at the guaranteed rate. 2. The method for realizing guaranteed frame rate services in an access network element according to claim 1, wherein the future time stamp of the next guaranteed service frame is scheduled by a parameter with parameters peak cell rate, cell delay variation tolerance speed, maximum cell rate, and maximum burst size are determined by algorithmic processing. 3. The method for realizing a guaranteed frame rate service in an access network element according to claim 1, wherein the future time stamp of scheduling cells at a non-guaranteed rate is determined by parameters with parameters peak cell rate and cell delay variation tolerance Degree of algorithmic processing to determine. 4. The method for realizing a guaranteed frame rate service in an access network element according to claim 1, wherein before the incoming cell is pushed into the guaranteed flow queue, the incoming cell is supervised by a guaranteed frame rate supervision mechanism , to satisfy the condition. 5. The method for realizing a guaranteed frame rate service in an access network element according to claim 1, wherein when scheduling the last cell of the guaranteed service frame, the future time of scheduling the cell at a non-guaranteed rate is determined stamp. 6. The method for implementing a guaranteed frame rate service in an access network element according to claim 1, wherein the non-guaranteed rate is used to support an unspecified bit rate service. 7. The method for implementing a guaranteed frame rate service in an access network element according to claim 1, wherein the non-guaranteed rate is used to support the best service available. 8. The method for implementing a guaranteed frame rate service in an access network element according to claim 1, further comprising the step of discarding unfinished frames scheduled to be transmitted at the non-guaranteed rate. 9. The method for realizing a guaranteed frame rate service in an access network element according to claim 1, further comprising the steps of: verifying that the future time stamp of the scheduled next guaranteed traffic frame is expired; and If expired, update the future timestamp of the scheduled next guaranteed traffic frame with an appropriate new value. 10. The method for realizing a guaranteed frame rate service in an access network element according to claim 1, further comprising the steps of: verifying that the future timestamp of the scheduled cell at the non-guaranteed rate is expired; and If expired, update the future timestamp of said scheduled cell at a non-guaranteed rate with an appropriate new value. 11. A system for realizing a guaranteed frame rate service in an access network element having an asynchronous transfer mode switching device, comprising: A guaranteed frame rate supervision block, which is used to push the identified incoming cells for guaranteed services into the guaranteed flow queue; A scheduling device, when determining the start of a guaranteed service frame, schedules a cell from the guaranteed flow queue, and transmits at a guaranteed rate through the asynchronous transfer mode switching device; means for determining a future time stamp for scheduling the next guaranteed traffic frame; means for determining a future timestamp for scheduling cells from said guaranteed flow queue at a non-guaranteed rate; When the future time stamp of the scheduled cell at the non-guaranteed rate is earlier than the future time stamp of the scheduled next guaranteed traffic frame, scheduling the cell from the guaranteed flow queue for transmission at a non-guaranteed rate; and When the future time stamp of the scheduled next guaranteed service frame arrives, the cell of the next guaranteed frame is scheduled to be transmitted at the guaranteed rate. 12. The system for realizing guaranteed frame frequency services in access network elements according to claim 11, wherein the scheduling of the future time stamp of the next guaranteed service frame is performed by a system with parameters peak cell rate, cell delay change Tolerance, maximum cell rate, and maximum burst size are determined by the algorithmic processing of the leaky bucket module.

Images