Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-11-09
2003-02-04
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S416000, C370S432000, C709S240000
Reexamination Certificate
active
06515991
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 use an input-queued, nonblocking switch. These switches have the 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 (1) 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, and giving precedence to one such highest priority request using an output precedence pointer, either an individual output precedence pointer. The output precedence pointer is 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. Each input chooses the 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: 5802052 (1998-09-01), Venkataraman
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Hsu Alpus H.
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-3135976