Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1996-06-27
2001-04-03
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S416000, C370S432000, C709S240000
Reexamination Certificate
active
06212182
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to combined unicast and multicast scheduling.
2. Description of Related Art
In communication networks in which fast switching is desired, one switching technique which has become common is to property that each possible input may be coupled to each possible output, and that data cells to be switched are queued at the input to the switch without effect on operation of the switch.
It often occurs in such switches that several inputs will simultaneously contend for the same output, and moreover that one input will simultaneously have data cells available for more than one output. Several techniques are known for selecting which input to couple to which output at each particular switching time, so as to achieve the greatest possible data cell flow through the switch, while ensuring that every input is communicated to its desired output within a reasonable time.
U.S. Pat. No. 5,267,235, titled “Method and Apparatus for Resource Arbitration”, issued in the name of Charles P. Thacker and assigned to Digital Equipment Corporation, describes one switching technique, herein called “Parallel Iterative Matching” or PIM. In the PIM technique, unmatched inputs and outputs are scheduled by a three-part process, in which (!) each unmatched input sends a request to every output for which it has a queued data cell; (2) each unmatched output which receives at least one request selects among them randomly and grants the selected request; and (3) each input which receives at least one grant selects among them and accepts the selected grant.
Nicolas McKeown's Ph.D. Thesis at the University of California (Berkeley), titled “Scheduling Cells in an Input Queued Switch”, submitted May 1995, describes another switching technique, herein called “Rotating Priority Iterative Matching” or RPIM. The RPIM technique improves on the PIM technique by introducing a grant precedence pointer at each output which rotates among the unmatched inputs, and requiring each output to grant to the input nearest the grant precedence pointer in preference to all other inputs.
One problem which has arisen in the art is that the input cells are often an intermixed stream of unicast cells (destined for a single output) and multicast cells (destined for more than one output). Both the PIM technique and the RPIM technique suffer from the drawback that they are not well suited for switching multicast data cells.
Another problem which has arisen in the art is that it is often desired to assign priorities to data cells, so that, for example, data cells carrying certain classes of data are more likely to arrive at their destination without excess switching delays. Both the PIM technique and the RPIM technique suffer from the drawback that they are complicated by attempts to simultaneously switch multiple priorities of data cells.
When the input stream of data cells intermixes both unicast and multicast data cells, each data cell being prioritized with one of multiple priorities, the PIM technique and the RPIM technique do not achieve satisfactory results.
Accordingly, it would be advantageous to provide a technique for combined unicast and multicast scheduling, and further to provide a technique for combined unicast and multicast scheduling which operates well with prioritized data cells.
SUMMARY OF THE INVENTION
The invention provides a method and system for combined unicast and multicast scheduling. Data cells are assigned at each input, to one unicast input queue for each output, or to a single multicast input queue. Each input makes two requests for scheduling to each output for which it has a queued data cell, one unicast request and one multicast request. Each output grants up to one request, choosing highest priority requests first, giving precedence to one such highest priority request using an output precedence pointer, either an individual output precedence pointer which is specific to that output for unicast data cells, or a group output precedence pointer which is generic to all outputs for multicast data cells. Each input accepts up to one grant for unicast data cells, or as many grants as possible for multicast data cells, choosing highest priority grants first, giving precedence to one such highest priority grant using an input precedence pointer.
In a preferred embodiment, the individual output precedence pointers each implement a round-robin precedence technique, in which the most recent input to transmit a data cell has the lowest precedence; the pointer is incremented to point to a next input each time a data cell is transmitted from the pointed-to input. The input precedence pointers each preferably implement an identical precedence technique. However, the group output precedence pointer is not incremented until all outputs from the multicast data cell for the pointed-to input have been transmitted.
REFERENCES:
patent: Re. 33900 (1992-04-01), Howson
patent: 4131767 (1978-12-01), Weinstein
patent: 4161719 (1979-07-01), Parikh et al.
patent: 4316284 (1982-02-01), Howson
patent: 4397020 (1983-08-01), Howson
patent: 4419728 (1983-12-01), Larson
patent: 4424565 (1984-01-01), Larson
patent: 4437087 (1984-03-01), Petr
patent: 4438511 (1984-03-01), Baran
patent: 4439763 (1984-03-01), Limb
patent: 4445213 (1984-04-01), Baugh et al.
patent: 4446555 (1984-05-01), Devault et al.
patent: 4456957 (1984-06-01), Schieltz
patent: 4464658 (1984-08-01), Thelen
patent: 4499576 (1985-02-01), Fraser
patent: 4506358 (1985-03-01), Montgomery
patent: 4507760 (1985-03-01), Fraser
patent: 4532626 (1985-07-01), Flores et al.
patent: 4644532 (1987-02-01), George et al.
patent: 4646287 (1987-02-01), Larson et al.
patent: 4677423 (1987-06-01), Benvenuto et al.
patent: 4679189 (1987-07-01), Olson et al.
patent: 4679227 (1987-07-01), Hughes-Hartogs
patent: 4723267 (1988-02-01), Jones et al.
patent: 4731816 (1988-03-01), Hughes-Hartogs
patent: 4750136 (1988-06-01), Arpin et al.
patent: 4757495 (1988-07-01), Decker et al.
patent: 4763191 (1988-08-01), Gordon et al.
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 4769811 (1988-09-01), Eckberg, Jr. et al.
patent: 4771425 (1988-09-01), Baran et al.
patent: 4819228 (1989-04-01), Baran et al.
patent: 4827411 (1989-05-01), Arrowood et al.
patent: 4833706 (1989-05-01), Hughes-Hartogs
patent: 4835737 (1989-05-01), Herrig et al.
patent: 4879551 (1989-11-01), Georgiou et al.
patent: 4893306 (1990-01-01), Chao et al.
patent: 4903261 (1990-02-01), Baran et al.
patent: 4922486 (1990-05-01), Lidinsky et al.
patent: 4933937 (1990-06-01), Konishi
patent: 4960310 (1990-10-01), Cushing
patent: 4962497 (1990-10-01), Ferenc et al.
patent: 4962532 (1990-10-01), Kasiraj et al.
patent: 4965767 (1990-10-01), Kinoshita et al.
patent: 4965772 (1990-10-01), Daniel et al.
patent: 4970678 (1990-11-01), Sladowski et al.
patent: 4979118 (1990-12-01), Kheradpir
patent: 4980897 (1990-12-01), Decker et al.
patent: 4991169 (1991-02-01), Davis et al.
patent: 5003595 (1991-03-01), Collins et al.
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5020058 (1991-05-01), Holden et al.
patent: 5033076 (1991-07-01), Jones et al.
patent: 5034919 (1991-07-01), Sassai et al.
patent: 5054034 (1991-10-01), Hughes-Hartogs
patent: 5059925 (1991-10-01), Weisbloom
patent: 5072449 (1991-12-01), Enns et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5095480 (1992-03-01), Fenner
patent: 5115431 (1992-05-01), Williams et al.
patent: 5128945 (1992-07-01), Enns et al.
patent: 5136580 (1992-08-01), Videlock et al.
patent: 5166930 (1992-11-01), Braff et al.
patent: 5199049 (1993-03-01), Wilson
patent: 5206886 (1993-04-01), Bingham
patent: 5208811 (1993-05-01), Kashio et al.
patent: 5212686 (1993-05-01), Joy et al.
patent: 5224099 (1993-06-01), Corbalis et al.
patent: 5226120 (1993-07-01), Brown et al.
patent: 5228062 (1993-07-01), Bingham
patent: 5229994 (1993-07-01), Balzano et al.
patent: 5237564 (1993-08-01), Lespagnol et al.
patent: 5241682 (1993-08-01), Bryant et al.
patent: 5243342 (1993-09-01), Kattemalalavadi et al.
patent: 5243596 (1993-09-01), Port
Cisco Technology Inc.
Hsu Alpus H.
Lewkowicz, Esq. Paul E.
Skjerven Morrill & MacPherson
LandOfFree
Combined unicast and multicast scheduling does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Combined unicast and multicast scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined unicast and multicast scheduling will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2449699