Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-06-17
2003-12-02
Marcelo, Melvin (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395400, C370S412000
Reexamination Certificate
active
06657959
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates in general to traffic scheduling in networking systems, and more particularly to supporting the Available Bit Rate (ABR) service category with guaranteed Minimum Cell Rate (MCR) transmissions in an Asynchronous Transfer Mode (ATM) networking system.
The need for faster communication among computers and other systems requires ever faster and more efficient networks. Today, networks typically use an amalgam of various software and hardware to implement a variety of network functions and standards. Network devices such as client computer systems, servers, hubs, routers, switches, network backbones, etc., are each complex devices that require digital processing in hardware and software to facilitate network communication. Some tasks performed in a network device include translation between different network standards such as Ethernet and ATM, reformatting data, traffic scheduling, routing data cells, packets messages, etc. Depending on the particular protocol being implemented, some tasks may be performed at different points in the network.
In conventional networking systems that implement ATM, data traffic is handled by a Virtual Channel, or Virtual Connection (VC). There are typically many VCs in each system and each VC has its own characteristics, such as packet type, packet size and protocols. For each VC, a descriptor which identifies the particular VC and its characteristics and requirements is stored in a memory. When a scheduler determines that a particular VC is ready for transmission, the VC descriptor is accessed and processed.
When scheduling transmissions for many VCs, several service categories are typically available, including Constant Bit Rate (CBR), Variable Bit Rate (VBR) and Available Bit Rate (ABR). The ABR category typically has the lowest priority, meaning that one or more CBR or VBR VCs may be transmitted before an ABR VC that is scheduled for transmission. In the ABR service category, a source may send cells at any rate between the Minimum Cell Rate (MCR) and the Allowed cell rate (ACR). Thus, for the ABR service category, it is desirable to transmit cells at rates close to or equal to the ACR for each VC while guaranteeing transmissions at the MCR lower bound rate for each VC.
SUMMARY OF THE INVENTION
The present invention provides novel techniques for guaranteeing MCR transmissions for ABR-category VCs. In particular, the techniques of the present invention provide for enhanced scheduling capabilities and increased throughput.
According to the invention, systems and methods are provided for maintaining cell transmissions at or above the minimum cell transfer rate for ABR-category VCs. An ABR schedule table (AST) in a memory stores ABR VCs scheduled for transmissions. A pointer to the AST indicates that the ABR VC currently addresses is ready to transmit a cell. The schedule pointer is incremented every cell transmission time. When a cell of a particular VC is sent, the VC is rescheduled in another time slot in the AST such that the next cell for that VC is transmitted at close to or equal to that VC's allowed cell transfer rate (ACR) while maintaining its minimum cell transfer rate (MCR). To determine the next time slot in which to reschedule the VC, the system uses an ACR bitmap that compresses the AST and which identifies entries that are not occupied by a VC scheduled for a transmission. The system determines the time slot in the AST that would allow the VC to be transmitted at its ACR. The system then checks the ACR bitmap to determine whether that ACR slot is unoccupied. If occupied, the system searches the ACR bitmap to locate the next empty slot in the AST. If all slots between the ACR slot and the slot which provides for an MCR transmission for that VC are occupied, the system searches an MCR bitmap, which compresses the AST, to determine which VC occupying the AST between the ACR slot and the MCR slot is to be replaced by the VC being rescheduled. The VC that is replaced is itself rescheduled. In this manner MCR is guaranteed for a VC being rescheduled.
According to an aspect of the invention, a method is provided for maintaining a transmission of cells at a minimum rate or above for each of a plurality of virtual connections (VCs) in a networking system device having a transmitting engine and a transmission schedule table for the plurality of VCs. The schedule table includes a plurality of entries, wherein each entry represents a time interval for transmission of a cell for a VC, and wherein the entries are continuously read in a sequential order to determine which VC is scheduled for a cell transmission during each time interval. The method typically comprises the steps of reading a first entry in the schedule table so as to identify a first VC scheduled for a cell transmission, and transmitting a cell for the first VC. The method also typically includes the step of rescheduling another cell transmission for the first VC based on an available cell rate (ACR) and a minimum cell rate (MCR) allowable for the first VC so as to maintain transmission of cells for the first VC at the MCR rate or above for the first VC.
According to another aspect of the invention, a networking system device coupled to one or more networks is provided. The device typically comprises a local memory for storing a schedule table having a plurality of entries, wherein each entry represents a time interval for transmission of a cell for a VC, and a network processor. The network processor typically includes a first and a second bitmap, each including a plurality of entries, wherein each first and second bitmap entry corresponds to an entry in the schedule table, wherein each first bitmap entry identifies whether the corresponding entry in the schedule table is occupied by a VC, and wherein each second bitmap entry identifies whether any VC occupying the corresponding entry in the schedule table has a minimum cell rate (MCR). The network processor also typically includes a transmit processor, coupled to the local memory and the first and second bitmaps, wherein the transmit processor reads a first entry in the schedule table to identify a first VC scheduled for a cell transmission, wherein the transmit processor transmits a cell for the first VC, and wherein the transmit processor reschedules another cell transmission for the first VC in the schedule table based on an available cell rate (ACR) and an MCR allowable for the first VC so as to maintain transmission of cells for the first VC at the MCR or above for the first VC.
REFERENCES:
patent: 4024507 (1977-05-01), Berkling et al.
patent: 4586134 (1986-04-01), Norstedt
patent: 4700294 (1987-10-01), Haynes
patent: 5218687 (1993-06-01), Ducousso et al.
patent: 5287537 (1994-02-01), Newmark et al.
patent: 5295135 (1994-03-01), Kammerl
patent: 5379297 (1995-01-01), Glover et al.
patent: 5394402 (1995-02-01), Ross
patent: 5414707 (1995-05-01), Johnston et al.
patent: 5481536 (1996-01-01), Reisch et al.
patent: 5515370 (1996-05-01), Rau
patent: 5517488 (1996-05-01), Miyazaki et al.
patent: 5535201 (1996-07-01), Zheng
patent: 5539729 (1996-07-01), Bodnar
patent: 5555256 (1996-09-01), Calamvokis
patent: 5555265 (1996-09-01), Kakuma et al.
patent: 5564051 (1996-10-01), Halliwell et al.
patent: 5574875 (1996-11-01), Stansfield et al.
patent: 5590128 (1996-12-01), Maloney et al.
patent: 5619650 (1997-04-01), Bach et al.
patent: 5638371 (1997-06-01), Raychaudhuri et al.
patent: 5640399 (1997-06-01), Rostoker et al.
patent: 5652872 (1997-07-01), Richter et al.
patent: 5659794 (1997-08-01), Caldarale et al.
patent: 5664116 (1997-09-01), Gaytan et al.
patent: 5684797 (1997-11-01), Aznar et al.
patent: 5684954 (1997-11-01), Kaiserwerth et al.
patent: 5696930 (1997-12-01), Garetz et al.
patent: 5701300 (1997-12-01), Jeon et al.
patent: 5726985 (1998-03-01), Daniel et al.
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5742772 (1998-04-01), Sreenan
patent: 5745477 (1998-04-01), Zheng et al.
patent: 5745790 (1998-04-01), Oskouy
patent: 5748630 (1998-05-01), Bergantino et a
Bleszynski Ryszard
Chong Simon
Blakely , Sokoloff, Taylor & Zafman LLP
Do Nhat
Marcelo Melvin
LandOfFree
Systems and methods for implementing ABR with guaranteed MCR does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for implementing ABR with guaranteed MCR, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for implementing ABR with guaranteed MCR will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158531