Patent US2185322A successfully refreshed from Google Patents.
US6848017B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for determining connections in a crossbar switch
Assignee: EMC Corp
•
Filing: 2001-10-24
•
Granted: 2005-01-25
•
Expires: 2021-10-24
Abstract
Abstract 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.
Inventors
- 👤 Stuart P. MacEachern
- 👤 Jacob Y. Bast
- 👤 Raju C. Bopardikar
- 👤 Jack J. Stiffler
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 15:12
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17375; H; H04; H04Q; H04Q3/00; H04Q3/42; H04Q3/52; H04Q2213/00; H04Q2213/1302; H04Q2213/13034; H04Q2213/1304; H04Q2213/13054; H04Q2213/13056; H04Q2213/13076; H04Q2213/13097; H04Q2213/13141; H04Q2213/13213; H04Q2213/1332; H04Q2213/1334
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
110 words
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.
Claim 2
Independent Claim
110 words
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.
Claim 3
Dependent Claim
29 words
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.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
29 words
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.
Claim 6
Dependent Claim
28 words
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.
Claim 7
Dependent Claim
65 words
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).
Claim 8
Dependent Claim
63 words
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).
Claim 9
Dependent Claim
43 words
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.
Claim 10
Dependent Claim
35 words
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.
Claim 11
Dependent Claim
21 words
The method of claim 8 wherein the metric second value comprises the number of different destinations requested by the each source.
Claim 12
Dependent Claim
21 words
The method of claim 8 wherein the metric second value comprises the number of unconnected requests generated by the each source.
Claim 13
Dependent Claim
35 words
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.
Claim 14
Dependent Claim
120 words
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.
Claim 15
Dependent Claim
120 words
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.
Claim 16
Dependent Claim
51 words
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.
Claim 17
Dependent Claim
41 words
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.
Claim 18
Dependent Claim
36 words
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.
Claim 19
Dependent Claim
41 words
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.
Claim 20
Dependent Claim
75 words
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.
Claim 21
Dependent Claim
70 words
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.
Claim 22
Dependent Claim
53 words
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.
Claim 23
Dependent Claim
35 words
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.
Claim 24
Dependent Claim
21 words
The apparatus of claim 20 wherein the metric second value comprises the number of different destinations requested by the each source.
Claim 25
Dependent Claim
21 words
The apparatus of claim 20 wherein the metric second value comprises the number of unconnected requests generated by the each source.
Claim 26
Dependent Claim
35 words
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.
Claim 27
Dependent Claim
131 words
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.
Claim 28
Dependent Claim
131 words
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.
Claim 29
Dependent Claim
41 words
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.
Claim 30
Dependent Claim
40 words
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.
Claim 31
Dependent Claim
41 words
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.
Claim 32
Dependent Claim
40 words
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.
Claim 33
Dependent Claim
78 words
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.
Claim 34
Dependent Claim
76 words
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.
Claim 35
Dependent Claim
47 words
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.
Claim 36
Dependent Claim
37 words
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.
Claim 37
Dependent Claim
23 words
The computer program product of claim 32 wherein the metric second value comprises the number of different destinations requested by the each source.
Claim 38
Dependent Claim
23 words
The computer program product of claim 32 wherein the metric second value comprises the number of unconnected requests generated by the each source.
Claim 39
Dependent Claim
37 words
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.
Claim 40
Dependent Claim
125 words
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.
Claim 41
Dependent Claim
125 words
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.
Claim 42
Dependent Claim
113 words
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.
Claim 43
Dependent Claim
113 words
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.
References Cited (Backward Citations)
US5371495A
Cited
JPH0690242A
Cited
US5299190A
Cited
US5377182A
Cited
US5537400A
Cited
US5923868A
Cited
US5848066A
Cited
US5754120A
Cited
US5862128A
Cited
US5734649A
Cited
US5781546A
Cited
US5754543A
Cited
US5923644A
Cited
US5923656A
Cited
US6317598B1
Cited
US6195335B1
Cited
US6087958A
Cited
US20010050916A1
Cited
WO1999040754A1
Cited
US6212612B1
Cited
US6574669B1
Cited
US6243664B1
Cited
US6182185B1
Cited
US6618379B1
Cited
US6747971B1
Cited
US6717945B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-01-25 | 2008-07-26 | 2009-01-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-01-25 | 2012-07-26 | 2013-01-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-01-25 | 2016-07-26 | 2017-01-25 | $7700.00 | Window Closed / Lapsed |