Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-09-28
2004-10-19
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S463000, C711S111000
Reexamination Certificate
active
06807187
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to communications and computer systems; more particularly, the invention relates to determining a next round robin element using a cascaded approach.
BACKGROUND OF THE INVENTION
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system designs, and resulting the in the development of faster and more powerful communications devices.
A network device, such as a router or packet switching system, is used in many networks to send traffic from multiple inputs to one or more outputs. The number of elements connected to a network device requesting service is greatly increasing because of enhanced customer demand as well as faster technology which allows the servicing of significantly more elements by a single device. For example, an edge router or packet switch may now wish to service thousands of connected elements having traffic to send.
However, in many cases, only a single element may be serviced at a time by a network element or one of its components, such as a line card. When elements are of a same priority, a round robin technique is commonly used to service these elements in a fair way. If all elements are to be serviced each time, a simple wrap-around counter increased after an element is serviced can be used to identify which element to service at a give time. However, if some elements do not need servicing, such a counter technique can waste a transmission cycle for each element not needing servicing, which may cause poor performance. The exact performance would depend on the occupancy rate of the elements. The counter round robin technique could be adapted to increase the counter if an element does not require servicing, however, such a technique typically cannot guarantee finding the next element to service within a transmission period or clock time, especially with a high number of inputs and/or fast transmission rate.
Another implementation of the round robin technique to accommodate a subset of the elements needing servicing includes a circuit which identifies the current element to service. Such conventional circuits are reasonable to implement when there are a relatively few number of inputs to choose between, such as on the order on tens of elements. However, as the number of elements to service becomes large, the circuitry becomes overwhelming large and has a very slow critical time path, which may exceed a transmission cycle or clock time.
Needed are new methods and apparatus for determining which element to service using a round robin technique, especially when a subset of the elements may not need servicing at any given time.
SUMMARY OF THE INVENTION
A cascaded circuit is used to identify a next element in a round robin sequence. Multiple first stage elements receive an indication of a last selected element and one or more indication signals of elements requesting selection. These elements requesting selection are a subset of the elements which may request selection. Each of the first stage elements includes an identification circuit to identify one of the requesting elements to a second stage element. The second stage element, coupled to the multiple first stage elements, receives an indication of either the last selected element or the first stage element coupled to the last selected element. The second stage element includes a selection circuit to select the next element from among the elements requesting selection identified by the first stage elements.
REFERENCES:
patent: 5155854 (1992-10-01), Flynn et al.
patent: 5546548 (1996-08-01), Chen et al.
patent: 5666488 (1997-09-01), Joh
patent: 5729702 (1998-03-01), Creedon et al.
patent: 5832278 (1998-11-01), Pham
patent: 5881313 (1999-03-01), Ramakrishnan et al.
Cisco Technology Inc.
Kizou Hassan
Lee Timothy
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for determining a next round robin... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining a next round robin..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining a next round robin... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3330351