Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-12-05
2003-02-25
Patel, Ajit (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000
Reexamination Certificate
active
06526060
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for handling information sent through a digital network and, more specifically, to a method and apparatus for servicing cells at a switch within such a network.
BACKGROUND OF THE INVENTION
In Asynchronous Transfer Mode (ATM) or “cell switching”, digital information is segmented into equal sized units called “cells” that are transmitted from a source node to a destination node through a “connection” in a digital network. The digital network may be constructed of digital switches coupled together by digital communication links. At the destination node, the cells may be reassembled into user frames of data for presentation and/or further processing.
Within the digital network, each digital switch may be connected to many communication links. Furthermore, each communication link may carry many different connections simultaneously. Accordingly, cells belonging to each connection may need to be handled or serviced differently at each switch in order to meet overall network goals for supporting each connection.
Within each switch, a cell memory or buffer may be used for temporarily holding cells prior to transmission on a communication link. The cell memory may be arranged into logical queues. Several of such queues may be used for separating cells of different types of services and/or connections. For example, cells belonging to higher priority connections may be stored in queues that have a higher priority of service. In some cases, a separate queue may be assigned to each connection.
In such a digital switch, “servicing” of a queue may be accomplished by sending a cell of that queue out into the digital network on a communication link. In other words, the cell is removed from its associated queue and transmitted into the network. A service algorithm is employed to select a particular queue from among the number of logical queues of cells for service.
To date, however, there has not existed a means of fairly scheduling data traffic from multiple connections at a switch or other network node while at the same time providing for accurate explicit rate (ideally, per connection) feedback to upstream nodes or user end-systems.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a method and apparatus for efficiently servicing cells at a node in a digital network.
It is a further object of the invention to provide a fair means of scheduling data traffic at a network node (e.g., a digital switch), with the option of providing accurate explicit rate feedback to upstream nodes or end-systems within the network.
In one embodiment, a service controller for a cell switched network may be configured to service a plurality of connection queues within the network according to a fair rate. The fair rate may be weighted for each of the connection queues. The service controller may be further configured to service the connection queues by moving cells from one or more of the connection queues to a class of service queue and the fair rate may be computed according to the length of the class of service queue and cell arrival and departure rate to and from the class of service queue.
In some embodiments, the service controller may be configured to service the connection queues at the computed fair rate, a guaranteed minimum rate or a rate which is a combination of the fair rate and the minimum rate.
In a further embodiment, cells in a digital network may be serviced by computing a fair rate for servicing the cells from a plurality of connection queues and moving the cells from the connection queues to a class of service queue according to the fair rate. Each of the connection queues may have an associated weight and each connection queue may be serviced at a rate according to the fair rate and the weight associated with the connection queue being serviced. The fair rate may be computed by computing a target rate for servicing the connection queues, computing an observed arrival rate for cells arriving at the class of service queue, and computing the fair rate according to a ratio of the target rate to their observed arrival rate. The target rate may be approximated according to an amount of available bandwidth for the class of service queue and the number of cells serviced from the class of service queue in a period of time.
In some embodiments, the fair rate may be periodically recomputed or recomputed once a predetermined number of cells have been received or have departed (e.g., based or a cell count instead of a time period). Further, the fair rate may be multiplied by a fixed constant (e.g., doubled) at each recomputation if a class of service queue empties during the period preceding the recomputation.
In yet further embodiments, cells within a digital network may be stamped with a fair rate to provide explicit rate control within said network. The fair rate used for explicit rate control may be the same fair rate computed for servicing cells from connection queues at a node within the digital network.
In still further embodiments, the present invention provides for caching service decisions for a number of a plurality of queues of cells or packets in a network; and the servicing those service decisions. Servicing the service decisions may include replacing (e.g., by overwriting) old service decisions if new service requests for any of the queues are received, otherwise the old service decisions may be reserviced.
The new service requests may be generated for each of the queues according to a fair rate or respective weighted fair rates. The fair rate and/or the weighted fair rates may be bounded by at least a minimum rate.
These and other features and advantages provided by the present invention will be apparent from the detailed description which follows and upon references to the accompanying figures described therein.
REFERENCES:
patent: 4430712 (1984-02-01), Coulson et al.
patent: 4543626 (1985-09-01), Bean et al.
patent: 4849968 (1989-07-01), Turner
patent: 4894797 (1990-01-01), Walp
patent: 4991172 (1991-02-01), Cidon et al.
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5083369 (1992-01-01), Sybatake et al.
patent: 5121383 (1992-06-01), Golestani
patent: 5136582 (1992-08-01), Firoozmand
patent: 5157654 (1992-10-01), Cisneros
patent: 5214639 (1993-05-01), Henrion
patent: 5214642 (1993-05-01), Kunimoto et al.
patent: 5224099 (1993-06-01), Corbalis et al.
patent: 5247626 (1993-09-01), Firoozmand
patent: 5271002 (1993-12-01), Barri et al.
patent: 5274768 (1993-12-01), Traw et al.
patent: 5278828 (1994-01-01), Chao
patent: 5297137 (1994-03-01), Ofek et al.
patent: 5303078 (1994-04-01), Brackett et al.
patent: 5311509 (1994-05-01), Heddes et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5313582 (1994-05-01), Hendel et al.
patent: 5315707 (1994-05-01), Seaman et al.
patent: 5359592 (1994-10-01), Corbalis et al.
patent: 5379297 (1995-01-01), Glover et al.
patent: 5404550 (1995-04-01), Horst
patent: 5412655 (1995-05-01), Yamada et al.
patent: 5432908 (1995-07-01), Heddes et al.
patent: 5434848 (1995-07-01), Chimento, Jr. et al.
patent: 5469433 (1995-11-01), McAuley
patent: 5499238 (1996-03-01), Shon
patent: 5502719 (1996-03-01), Grant et al.
patent: 5502833 (1996-03-01), Byrn et al.
patent: 5517643 (1996-05-01), Davy
patent: 5528587 (1996-06-01), Galand et al.
patent: 5530698 (1996-06-01), Kozaki et al.
patent: 5539899 (1996-07-01), Huynh et al.
patent: 5541912 (1996-07-01), Choudhury et al.
patent: 5541919 (1996-07-01), Yong et al.
patent: 5542068 (1996-07-01), Peters
patent: 5546389 (1996-08-01), Wippenbeck et al.
patent: 5548587 (1996-08-01), Bailey et al.
patent: 5550823 (1996-08-01), Irie et al.
patent: 5555264 (1996-09-01), Sallberg et al.
patent: 5557604 (1996-09-01), Usumi et al.
patent: 5557607 (1996-09-01), Holden
patent: 5561663 (1996-10-01), Klausmeier
patent: 5568477 (1996-10-01), Galand et al.
patent: 5570348 (1996-10-01), Holden
patent: 5570360 (1996-10-01), Klausmeier et al.
patent: 5570362 (1996-10-01), Nishimura
patent: 5600820 (1997-02-01), Johnston
patent: 5617416 (1
Hughes David A.
Marathe Madhav V.
Blakely , Sokoloff, Taylor & Zafman LLP
Cisco Technology Inc.
Nguyen Hanh
Patel Ajit
LandOfFree
Dynamic rate-based, weighted fair scheduler with explicit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic rate-based, weighted fair scheduler with explicit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic rate-based, weighted fair scheduler with explicit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3182893