Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-06-26
2002-03-19
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S428000
Reexamination Certificate
active
06359884
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of broadband communications. More specifically, it relates to the design of packet schedulers that are deployed within telecommunications switches.
BACKGROUND OF THE INVENTION
Packet schedulers basically maintain queues of pointers to packets that are buffered in the switch memory, and determine the times at which each buffered packet is transmitted from the switch.
A conventional packet scheduler is implemented using a single monolithic component such as an application specific integrated circuit (ASIC), or a single software system. This one-component architecture has become undesirable however, for at least two reasons. The first reason is that the feature-set that has to be supported by schedulers has become too varied to be economically implemented on a single component. More particularly, as it has become necessary to implement a wider array of new features in packet schedulers, and as it has therefore become increasingly infeasible for switch manufacturers to implement a full feature-set in every packet scheduler, the need has arisen to design a customized scheduler for each specific type of packet switch that is produced. This trend, in turn, has driven up design costs for switch manufacturers.
A second reason for the undesirability of continuing with the use of a single monolithic component to implement a scheduler, arises because the definitions, let alone the implementations, of several of the aforementioned new scheduler features have yet to be stabilized. This means that switch designers have had to frequently redesign entire schedulers every time any unstable part of the overall feature-set changes.
Partitioning of an architecture involves mapping a plurality of features that have traditionally been implemented by a single component, to a plurality of components that replace the traditional single-component. Partitioning is difficult because the process demands that several factors be simultaneously considered. These factors include the requirement of implementing the total feature-set that was implemented by the single traditional component, using the plurality of components. The factors also include the preference that each component be mapped to a set of features whose implementations tend to change at the same time. Such mappings reduce upgrade costs for the entire architecture.
Another factor to be considered in partitioning an architecture is the desirability of mapping each set of features required to provide a single service, to the same component. Partitioned architectures that achieve this goal are hereinafter referred to as architectures that are partitioned along service-lines.
Another factor to consider in partitioning an architecture, is the desire that the resulting components be decoupled from one another. Conventional telecommunication switch designs are constituted by components that are coupled to one another. Generally, the coupling of one component to another occurs when the designs of the components are highly interdependent on each other, such that one component cannot be changed without also changing the other. Coupling is generally undesirable as it prevents components from being developed independently of each other. Coupled components are decoupled from one another by implementing well-defined and simple interfaces between them, that do not have to change as the implementation of either of the components changes.
SUMMARY OF THE INVENTION
It is an object of this invention to obviate and/or mitigate one or more of the above-identified disadvantages.
According to a first broad aspect, the invention provides a packet scheduler for use in a packet switch having a cell memory, the packet scheduler comprising a queue manager hardware block (QM) for maintaining a queue of packet identifiers for each of a plurality of internal connection numbers, each packet identifier corresponding to a packet that is buffered at a respective buffer address of the cell memory within the switch, and for determining the time at which each buffered packet is to be transmitted from the switch, the QM having a switch interface for communicating internal connection numbers and buffer addresses to and from the packet switch; and the QM having a rate shaper interface for sending and receiving internal connection numbers and TDQ (traffic descriptor queue) identifiers.
According to a second broad aspect, the invention provides a packet scheduler for use in a packet switch having a cell memory, the packet scheduler comprising: a queue manager hardware block (QM) for maintaining a queue of packet identifiers for each of a plurality of internal connection numbers, each packet identifier corresponding to a packet that is buffered at a respective buffer address of the cell memory within the switch, and for determining the time at which each buffered packet is to be transmitted from the switch, the QM having a switch interface for communicating internal connection numbers and buffer addresses to and from the packet switch; and the QM having a virtual port scheduler interface for sending and receiving TDQ identifiers.
According to a third broad aspect, the invention provides A method of scheduling packets comprising the steps of: (a) maintaining a credit-count for each of a plurality of internal connection numbers (ICN); (b) upon receipt of a buffer address and a particular ICN enqueueing a packet identifier that is associated with the buffer address in a per-connection queue (PCQ) that is associated with the particular ICN and enqueueing the ICN in an associated traffic descriptor queue (TDQ) only when another copy of the given ICN is not already enqueued on the TDQ, and when the ICN's credit-count is exceeding a predetermined threshold; and (c) dequeueing the given ICN from the TDQ by reading a packet identifier from the ICN's PCQ, looking up the BADR, and outputting the ICN and the BADR.
REFERENCES:
patent: 5633859 (1997-05-01), Jain et al.
patent: 6141323 (2000-10-01), Rusu
patent: 6151321 (2000-11-01), Benson et al.
patent: 6195331 (2001-02-01), Tani
patent: 6212165 (2001-04-01), Mann et al.
patent: 6219352 (2001-04-01), Bonomi et al.
patent: 6262986 (2001-07-01), Oba et al.
patent: WO9639759 (1996-12-01), None
patent: WO9720415 (1997-05-01), None
Chin Wellington
Nortel Networks Limited
Pham Brenda
LandOfFree
Modular scalable packet scheduler with rate based shaping... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modular scalable packet scheduler with rate based shaping..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular scalable packet scheduler with rate based shaping... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2832916