Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-05-17
2003-10-07
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S467000
Reexamination Certificate
active
06631131
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to techniques for arbitrating access to a shared resource. One particular example is a device having multiple inputs and outputs for routing message traffic in a communications network. More particularly, the invention relates to a method, and apparatus for implementing that method, to bias the arbitration between two or more inputs of the device that are contending for data communication access to the same output of the device.
As multiprocessing environments grow, the ability to provide data communication between the individual system elements (i.e., processors and peripheral equipment) of the system requires careful thought so as not to inadvertently give a system element unfair access to a communications path or some other shared resource (e.g., a multiple-user bus system) while, at the same time, limiting such access to other system elements.
Many of today's data communication networking configurations will use various devices (typically, “routers”) to direct or otherwise route message traffic from one communications link to one of a number of other communications links. However, message traffic can be received at two or more inputs of the device at substantially the same time bound for the same output, raising the issue of which of the two will be allowed to proceed before the other, i.e., who goes first. Access to the output requires some form of arbitration between the two contending inputs. Smaller systems (i.e., those with a small number of system elements needing to communicate with one another) may use such classic arbitration techniques as assigning fixed priorities to the inputs or “round-robin” processing. In the former, each port input is provided a predetermined priority to form a hierarchical arbitration scheme. Inputs with higher priority will be given access to an output over inputs with lower pre-assigned priorities seeking access to that same output. The round-robin technique involves assigning priorities according to a predetermined order among the inputs. As message traffic is received, the priorities change so that the last input granted access to a particular output is then given the lowest priority, and the next input in order now has the highest priority; the remaining inputs will have their priorities similarly changed according to the predetermined order.
Similar techniques may be used in other shared resource environments such as, for example, multiple-user bus systems, to allocate access to the bus between connected controllers.
As computing systems become more complex, so that the number of elements (processors and peripheral units) increase, it would not be unusual for an input of a routing device to be required to route message traffic from several elements. Further, routing devices are sometimes cascaded to form, for example, tree-like network configurations, increasing the number of system elements that may need to route message traffic through an input of a routing device. Using pre-assigned priorities, round-robin processing, or other similar techniques can unfairly allocate the services of a routing device's input to some of the system's elements at the expense of other elements that use another input of that routing device. For example, a routing device may receive at one input message traffic from only one system element, while another input of that same routing device is required to service several elements. Using any of the above techniques will operate to give more of the routing device's attention to the one element, and less attention to each of the several elements using the second input. Thus, prior arbitration techniques can unfairly allocate more of the routing device's services to the input having the lesser number of system elements using that routing device.
One solution to assuring fair allocation of services to device inputs is to use biased arbitration techniques. With biased arbitration, each input has a bias value that determines the percentage of time it will win arbitration.
Biased arbitration can be used either to assure fair access to all nodes, or to purposely give some paths higher priority than other paths. Biased arbitration can be used to help support quality of services (QOS) guarantees for real-time or constant bit rate traffic.
One biased arbitration system is described in U.S. Pat. No. 5,694,121, assigned to the assignee of the present application, which discloses an ALU arbitration technique. Each port has a bias value provided and has an associated accumulator. The port with the highest value in its accumulator wins arbitration. The winner then decrements its accumulator by the sum of the bias values of all the losers, and each loser increments its accumulator by its own bias value. Another biased arbitration system is described in U.S. Pat. No. 5,710,549, which is also assigned to the assignee of the present application.
This ALU biasing scheme works well for routers with small numbers of ports. However, it does not scale well to larger routers because large adders and logic for pairwise comparisons of all accumulators are required to determine a current arbitration winner.
Accordingly, research continues to develop effective biased arbitration techniques of utility on complex systems.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, requestors are assigned bias values which are encoded as binary bias vectors. The bias vectors are stored as columns in a matrix, with each column corresponding to a particular requester. During an arbitration the rows of the matrix are fetched; thus, the matrix is designated a transpose matrix. The rows are fetched in a way that gives the correct biasing and also gives the lowest possible latency.
According to another aspect of the invention, the rows are fetched by a mapped counter output. The counter output is mapped so that rows having more significant bit positions of the binary bias vectors are fetched more frequently than less significant bit positions.
According to another aspect of the invention, rows having all zeros are skipped because those rows indicate that no access will be granted. A skip-row signal is asserted for rows having all zeros and to be accessed after the row having all zeros is substituted.
According to another aspect of the invention, an unbiased cycle is generated where all ports requesting access are serviced regardless of their bias values.
According to another aspect of the invention, bias vectors for requestors not having a request pending are masked during an arbitration.
According to another aspect of the invention, most significant rows having no active request are masked to avoid fetching the rows.
Other features and advantages will be apparent in view of the following detailed description and appended drawings.
REFERENCES:
patent: 4389642 (1983-06-01), Kahn
patent: 4852083 (1989-07-01), Niehaus et al.
patent: 5694121 (1997-12-01), Krause et al.
patent: 5710549 (1998-01-01), Horst et al.
patent: 6081527 (2000-06-01), Chappel et al.
Horst Robert W.
Mizell Robert B.
Sonnier David P.
Watson William J.
Do Nhat
Hewlett--Packard Development Company, L.P.
Nguyen Chau
Oppenheimer Wolff & Donnelly
Sherry Leah
LandOfFree
Transpose table biased arbitration scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Transpose table biased arbitration scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transpose table biased arbitration scheme will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3139067