Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-05-20
2003-05-13
Olms, Douglas (Department: 2732)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S382000, C370S395410, C370S461000, C370S462000, C370S401000, C711S151000, C711S158000, C379S229000
Reexamination Certificate
active
06563818
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to data communication networking devices, more particularly, to an arbitration logic architecture used in storing data frames in memory.
2. Background Art
In computer networks, a plurality of network stations are interconnected via a communications medium. For example, Ethernet is a commonly used local area network scheme in which multiple stations are connected to a single shared serial data path. These stations often communicate with a switch located between the shared data path and the stations connected to that path Typically, the switch controls the communication of data packets on the network.
When all of the stations connected to the network are simultaneously operating, packet traffic on the shared serial path can be heavy. In order for the data to be properly transmitted, the switch must manage the storage of these data packets within memory. Typically, a free buffer queue stores free address pointers; these free pointers point to available address space in memory where data can be stored. In a complex system such as a multiport switch, the free buffer queue provides a mechanism to orderly manage the requests for free pointers by various logic within the switch. An arbitration logic utilizes a round robin algorithm to honor the requests that are of identical priority. One approach to providing this type of arbitration scheme is discussed below with respect to Tables 1 and 2.
For the purposes of explanation, it is assumed that a multiport switch has six ports for the receipt and transmission of data frames. These six ports have equal priority. Each port has queuing logic tat executes requests to the free buffer queue for a free pointer upon receipt of a data frame. As indicated previously, a free pointer points to available space within memory for storage of the received data frame. The data frame is stored in the memory until the switch makes the appropriate switching decisions for that data frame, and is thereafter transmitted. To monitor and track which port should be granted the request, the arbitration logic, typically, has to maintain the following information (shown below):
TABLE 1
Counter
Value
REQ 1
REQ 2
REQ 3
REQ 4
REQ 5
REQ 6
01
1
X
X
X
X
X
02
1
0
0
0
0
0
03
1
X
0
0
0
0
04
1
X
X
0
0
0
05
1
X
X
X
0
0
06
1
X
X
X
X
0
The first column, labeled Counter Value, represents the values of a counter that is maintained by the arbitration logic. This counter value is also referred to as the slot number. The counter in this case is a 3-bit counter, which is incremented whenever an acknowledgement is sent by the arbitration logic to the respective port. As an illustration, Table 1 represents the conditions in which the arbitration logic may grant an acknowledgement to request
1
(REQ_
1
) from port
1
. If the counter value is 1, for example, REQ_
1
is
1
and the request bits that correspond to the remaining ports
2
-
6
are in a “DON'T CARE” state (denoted by “X”). The second condition, in which REQ_
1
is honored, is when the counter value is 2 and all the other requests are 0. If the counter value equals 3, REQ_
1
is 1 while REQ_
2
is in a “DON'T CARE” state and the remaining requests bits are 0. REQ_
2
is in a “DON'T CARE” state because the arbitration logic checks the request sequentially and then loops back; thus, the acknowledgement would be sent out based upon REQ_
1
being set to 1, which precedes REQ_
2
. The other conditions (i.e., when the counter equals 4, 5, and 6) follow the same rationale.
This scheme provides port
1
the absolute right to be granted an acknowledgement when the counter value is 1, assuming port
1
has a request. However, port
1
will only be granted an acknowledgement when the counter value is 2 if each of the other ports does not have a request. When the counter value is 3, port
1
will be granted and acknowledgement if it has a request and ports
3
-
6
do not. In this case, port
1
has priority over port
2
so that a request by port
2
does not matter in making the decision to grant an acknowledgement to port
1
. It is apparent that for the arbitration logic to issue an acknowledgement, all the conditions of Table 1 have to be captured for only a single acknowledgement. Table 2 illustrates the conditions that must be satisfied to instruct the arbitration logic to issue an acknowledgement to REQ_
2
from port
2
. The conditions for granting the remaining requests (i.e., REQ_
3
, REQ_
4
, REQ_
5
, and REQ_
6
) exhibit a similar scheme.
TABLE 2
Counter
Value
REQ 1
REQ 2
REQ 3
REQ 4
REQ 5
REQ 6
01
0
1
X
X
X
X
02
X
1
X
X
X
X
03
0
1
0
0
0
0
04
0
1
X
0
0
0
05
0
1
X
X
0
0
06
0
1
X
X
X
0
Because of the numerous permutations that must be processed with respect to each acknowledgement, the conventional arbitration logic is complex. That is, the number of gates (or gate counts) increases with logic complexity, resulting in suboptimal performance and increased die size.
SUMMARY OF THE INVENTION
There exists a need for a implementing a more efficient round-robin arbitration architecture. There is also a need for reducing complexity of the arbitration logic. There is yet another need to minimize the die size of the device.
These and other needs are met by the present invention, where an arbitration logic grants acknowledgements to a requesting port in a round robin scheme. The architecture of the arbitration logic comprises multiple cells that are cascaded. The cascaded cells output an acknowledgement signal in response to an inhibit signal and a request signal. A counter maintains the order of the round robin scheme and is incremented only when the arbitration logic grants an acknowledgement
According to one aspect of the invention, a multiport switch is configured for controlling communication of data frames. The multiport switch comprises a buffer queue, which stores free buffer pointers. The free buffer pointers point to addresses of available memory space within the memory. A plurality of ports receive and transmit the data frames. Each of the ports is configured to output a request signal to request one of the free buffer pointers from the buffer queue. An arbitration logic receives and arbitrates the request signals from the plurality of ports according to a round robin scheme. The arbitration logic comprises a plurality of cells that correspond to the plurality of ports. These cells are cascaded in a prescribed sequence. The cell with the highest priority is able to send an acknowledgement signal to a corresponding requesting port, assuming the cell has received a request signal from that port. This highest priority cell concurrently sends an inhibit signal to the other lower priority cells to prevent each of these cells from sending another acknowledgement signal. The priorities of the cells are based in part on the relative positions of the cells within the prescribed sequence. This arrangement reduces complexity of the arbitration logic.
Another aspect of the present invention provides a method for storing data frames in memory. The method includes outputting a plurality of request signals to request a free buffer pointer. A free buffer pointer indicates an address of available space within the memory. The plurality of request signals are synchronized. The method also includes arbitrating the request signals in a round robin scheme by utilizing a plurality of cells cascaded in a prescribed sequence. The step of arbitrating comprises selecting a cell based upon a counter value, and outputting an inhibit signal from the selected cell in response to a corresponding request signal. The inhibit signal inhibits the other cells in the prescribed sequence from asserting their respective acknowledgement signals. The step of arbitrating further includes selectively asserting by the selected cell a corresponding acknowledgement signal based upon the corresponding request signal and a received inhibit signal, incrementing the counter value in response to the asserted acknowledgement signal, and obtaining the free buffer pointer in response to th
Sang Jinqlih
Yang Edward
Advanced Micro Devices , Inc.
Nguyen Van Kim T.
Olms Douglas
LandOfFree
Weighted round robin cell architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Weighted round robin cell architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weighted round robin cell architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3003247