Method and apparatus for determining connections in a crossbar switch
View Patent ↗A procedure is described for determining which source to connect to which destination in a non-blocking crossbar switch through which a plurality of sources may be attempting to gain access to a plurality of destinations. To this end, a metric is dynamically associated with each source and with each destination. Matching of sources to destinations is accomplished by iteratively assigning the destination having the smallest metric of all currently unmatched destinations to the source having the smallest metric of all currently unmatched source.
1. A method for determining connections in a multipath switch between a plurality of sources and a plurality of destinations wherein each source generates one or more requests for connection to one of the plurality of destinations, comprising:
(a) associating a metric having a value dynamically computed from first predetermined criteria with each source;
(b) associating a metric having a value dynamically computed from second predetermined criteria with each destination;
(c) connecting a destination having the smallest metric value of all unconnected destinations to a source requesting that destination having the smallest metric value of all unconnected sources; and
(d) repeating step (c) until all sources are connected to requested destinations.
2. The method of claim 1 wherein step (a) comprises computing the metric value for a source to be equal to the number of different destinations requested by the source.
3. The method of claim 1 wherein step (b) comprises computing the metric value for a destination to be equal to the number of different sources requesting that destination.
4. The method of claim 1 wherein step (a) comprises computing the metric value for a source to be equal to the number of unconnected requests generated by that source.
5. The method of claim 1 wherein step (b) comprises computing the metric value for a destination to be equal to the number of unconnected requests for that destination.
6. The method of claim 1 wherein step (a) comprises:
(a1) computing a value equal to the number of different destinations requested by each source;
(a2) computing a value equal to the number of unconnected requests generated by each source; and
(a3) computing the metric value of each source as the combination of the value computed in step (a1) with the value determined in step (a2).
7. The method of claim 1 wherein step (b) comprises:
(b1) computing a value equal to the number of different sources requesting each destination;
(b2) computing a value equal to the number of unconnected requests for that destination; and
(b3) computing the metric value of each source as the combination of the value computed in step (b1) with the value determined in step (b2).
8. The method of claim 1 further comprising (f) assigning each request a metric having a first value that is dynamically computed from characteristics of the each request and a second value is dynamically computed from characteristics of the source generating the each request.
9. The method of claim 8 wherein the metric first value comprises at least one of the group consisting of a user-assigned priority value and the length of time that the each request has been pending.
10. The method of claim 8 wherein the metric second value comprises the number of different destinations requested by the each source.
11. The method of claim 8 wherein the metric second value comprises the number of unconnected requests generated by the each source.
12. The method of claim 8 wherein the metric second value comprises the combination of the number of different destinations requested by the each source with the number of unconnected requests generated by the each source.
13. Apparatus for determining connections in a multipath switch between a plurality of sources and a plurality of destinations wherein each source generates one or more requests for connection to one of the plurality of destinations, comprising:
a source metric computer that generates source metric information having a value dynamically computed from first predetermined criteria with each source;
a destination metric computer that generates destination metric information having a value dynamically computed from second predetermined criteria with each destination; and
an arbiter that repeatedly connects a destination having the smallest destination metric value of all unconnected destinations to a source requesting that destination having the smallest source metric value of all unconnected sources until all sources are connected to requested destinations.
14. The apparatus of claim 13 wherein the source metric computer comprises a request counter that computes the metric value for each source to be equal to the number of different destinations requested by the each source and a selection mechanism that forwards the source metric information to the destination metric computer.
15. The apparatus of claim 13 wherein the destination metric computer comprises a destination metric accumulator that receives the source metric information and computes the metric value for a destination to be equal to the number of different sources requesting that destination.
16. The apparatus of claim 13 wherein the source metric computer comprises a queue length calculator that computes the metric value for a source to be equal to the number of unconnected requests generated by that source.
17. The apparatus of claim 13 wherein the destination metric computer comprises a destination metric accumulator that receives the source metric information and computes the metric value for a destination to be equal to the number of unconnected requests for that destination.
18. The apparatus of claim 13 wherein the source metric computer comprises:
a request counter that computes a request value equal to the number of different destinations requested by each source;
a queue length calculator that computes a queue length value equal to the number of unconnected requests generated by each source; and
a selector mechanism that generates the metric value of each source as the combination of the request value with the queue length value.
19. The apparatus of claim 13 wherein the destination metric computer comprises:
a destination metric accumulator that computes a request value equal to the number of different sources requesting each destination and computes a queue length value equal to the number of unconnected requests for that destination; and
an accumulator register that generates the metric value of each source as the combination of the request value with the queue length value.
20. The apparatus of claim 13 wherein the source metric computer further comprises a source priority register that assigns each request a metric having a first value that is dynamically computed from characteristics of the each request and means for dynamically computing a second value from characteristics of the source generating the each request.
21. The apparatus of claim 20 wherein the metric first value comprises at least one of the group consisting of a user-assigned priority value and the length of time that the each request has been pending.
22. The apparatus of claim 20 wherein the metric second value comprises the number of different destinations requested by the each source.
23. The apparatus of claim 20 wherein the metric second value comprises the number of unconnected requests generated by the each source.
24. The apparatus of claim 20 wherein the metric second value comprises the combination of the number of different destinations requested by the each source with the number of unconnected requests generated by the each source.
25. A computer program product for determining connections in a multipath switch between a plurality of sources and a plurality of destinations wherein each source generates one or more requests for connection to one of the plurality of destinations, the computer program product comprising a computer usable medium having computer readable program code thereon, including:
program code that associates a source metric having a value dynamically computed from first predetermined criteria with each source;
program code that associates a destination metric having a value dynamically computed from second predetermined criteria with each destination;
program code that repeatedly connects a destination having the smallest metric value of all unconnected destinations to a source requesting that destination having the smallest metric value of all unconnected sources until all sources are connected to requested destinations.
26. The computer program product of claim 25 wherein the program code that generates the source metric value comprises program code that computes the metric value for a source to be equal to the number of different destinations requested by the source.
27. The computer program product of claim 25 wherein the program code that generates the destination metric value comprises program code that computes the metric value for a destination to be equal to the number of different sources requesting that destination.
28. The computer program product of claim 25 wherein the program code that generates the source metric value comprises program code that computes the metric value for a source to be equal to the number of unconnected requests generated by that source.
29. The computer program product of claim 25 wherein the program code that generates the destination metric value comprises program code that computes the metric value for a destination to be equal to the number of unconnected requests for that destination.
30. The computer program product of claim 25 wherein the program code that generates the source metric value comprises:
program code that computes a request value equal to the number of different destinations requested by each source;
program code that computes a request length value equal to the number of unconnected requests generated by each source; and
program code that computes the metric value of each source as the combination of the request value with the queue length value.
31. The computer program product of claim 25 wherein the program code that generates the destination metric value comprises:
program code that computes a request value equal to the number of different sources requesting each destination;
program code that computes a queue length value equal to the number of unconnected requests for that destination; and
program code that computes the metric value of each source as the combination of the request value with the queue length value.
32. The computer program product of claim 25 further comprising program code that assigns each request a metric having a first value that is dynamically computed from characteristics of the each request and a second value is dynamically computed from characteristics of the source generating the each request.
33. The computer program product of claim 32 wherein the metric first value comprises at least one of the group consisting of a user-assigned priority value and the length of time that the each request has been pending.
34. The computer program product of claim 32 wherein the metric second value comprises the number of different destinations requested by the each source.
35. The computer program product of claim 32 wherein the metric second value comprises the number of unconnected requests generated by the each source.
36. The computer program product of claim 32 wherein the metric second value comprises the concatenation of the number of different destinations requested by the each source with the number of unconnected requests generated by the each source.
37. A computer data signal embodied in a carrier wave for determining connections in a multipath switch between a plurality of sources and a plurality of destinations wherein each source generates one or more requests for connection to one of the plurality of destinations, the computer data signal comprising:
program code that associates a source metric having a value dynamically computed from first predetermined criteria with each source;
program code that associates a destination metric having a value dynamically computed from second predetermined criteria with each destination;
program code that repeatedly connects a destination having the smallest metric value of all unconnected destinations to a source requesting that destination having the smallest metric value of all unconnected sources until all sources are connected to requested destinations.
38. Apparatus for determining connections in a multipath switch between a plurality of sources and a plurality of destinations wherein each source generates one or more requests for connection to one of the plurality of destinations, comprising:
means for generating source metric information having a value dynamically computed from first predetermined criteria with each source;
means for generating destination metric information having a value dynamically computed from second predetermined criteria with each destination; and
means for repeatedly connecting a destination having the smallest destination metric value of all unconnected destinations to a source requesting that destination having the smallest source metric value of all unconnected sources until all sources are connected to requested destinations.