Source: http://www.google.com/patents/US6449283?dq=patent:5992892
Timestamp: 2017-08-18 18:39:59
Document Index: 547786466

Matched Legal Cases: ['§119', '§112', '§4', '§4', '§4', '§4', '§4', '§4', '§4', '§4', '§4', '§4']

Patent US6449283 - Methods and apparatus for providing a fast ring reservation arbitration - Google Patents
In a switch having input ports and output ports, a fast ring reservation arbitration is provided by grouping crosspoint units associated with an output port. If any of the crosspoint units of a group request the output port, a received token will be passed to crosspoint units within the group. If, on...http://www.google.com/patents/US6449283?utm_source=gb-gplus-sharePatent US6449283 - Methods and apparatus for providing a fast ring reservation arbitration
Publication number US6449283 B1
Application number US 09/312,321
Publication number 09312321, 312321, US 6449283 B1, US 6449283B1, US-B1-6449283, US6449283 B1, US6449283B1
Inventors Hung-Hsiang Jonathan Chao, Alper Altinordu
Patent Citations (3), Referenced by (127), Classifications (19), Legal Events (6)
Methods and apparatus for providing a fast ring reservation arbitration
US 6449283 B1
1. In a switch having input ports, output ports, and a switching fabric for selectively connecting an input port to an output port, the switching fabric including a matrix of crosspoints having rows associated with the input ports and columns associated with the output ports, a method for arbitrating among cells contending for a particular one of the output ports, the method comprising steps of:
a) for each column of crosspoints, passing a token in a ring defined by the crosspoints;
b) for each column of crosspoints, defining groups of crosspoints;
c) for each column of crosspoints and for each of the groups of crosspoints, logically ORing requests for the output port associated with the column to generate a group request;
d) for each column of crosspoints and for each of the groups of crosspoints, if the group request is LOW, and the token is received, passing received token to a next group of crosspoints in the ring; and
e) for each column of crosspoints and for each of the groups of crosspoints, if the group request is HIGH and the token is received, passing the received token to successive crosspoints of the group of crosspoints,
wherein, when a crosspoint having a request receives the token, the cell associated with that crosspoint wins the arbitration.
2. The method of claim 1 wherein the step of, for each column of crosspoints and for each of the groups of crosspoints, logically ORing requests for the output port associated with the column to generate the group request includes sub-steps of:
i) defining at least two sub-groups of crosspoints within the group of crosspoints;
ii) for each of the at least two sub-groups of crosspoints, logically ORing requests for the associated output port to generate at least two intermediate OR results;
iii) logically ORing the at least two intermediate OR results to generate a further OR result.
3. The method of claim 2 wherein the further OR result is the group request.
i) defining at least four sub-groups of crosspoints within the group of crosspoints;
ii) for each of the four sub-groups of crosspoints, logically ORing requests for the associated output port to generate four intermediate OR results;
iii) logically ORing the four intermediate OR results to generate a further OR result.
5. The method of claim 4 wherein the further OR result is the group request.
the first crosspoint of each group having a token input coupled with a first output of a switch and a token output coupled with a token input of a next crosspoint,
the last crosspoint of each group having a token input coupled with a token output of a preceding crosspoint and a token output coupled with a first input of an OR gate,
each of the second through next to last crosspoints of each group having a token input coupled with a token output of a preceding crosspoint and a token output coupled with a token input of a next crosspoint,
a second input of the OR gate coupled with a second output of the switch, and
an output of the OR gate coupled with the input of a switch of a next group of crosspoint units,
a method for arbitrating among cells contending for a particular one of the output ports, the method comprising steps of:
a) for each column of crosspoints and for each of the groups of crosspoints, logically ORing requests for the associated output port to generate a group request; and
b) for each column of crosspoints and for each of the groups of crosspoints, applying the group request as a control signal to the switch,
wherein, if the group request is LOW, the input of the switch is passed to the second output of the switch, and
wherein, if the group request is HIGH, the input of the switch is passed to the first output of the switch.
7. The method of claim 6 further comprising a step of, within each column of crosspoints:
c) passing an output of the OR gate of the last group of crosspoints to the input of the switch of the first group of crosspoints.
8. In a system having input ports, output ports, and a switching fabric for selectively connecting an input port to an output port, the switching fabric including a matrix of crosspoints having rows associated with the input ports and columns associated with the output ports, a device comprising:
a) means, associated with a first group of crosspoints in a column of crosspoints, for accepting a token, for forwarding the token to a next group of forwarding the token to a first crosspoint of the first group in response to a second condition; and
b) means, associated with a second group of crosspoints in a column of crosspoints, for accepting a token from the first group of crosspoints, for forwarding the token to a next group of crosspoints in response to another first condition and for forwarding the token to a first crosspoint of the second group in response to another second condition.
9. The device of claim 8 wherein the first condition occurs if none of the crosspoints of first group receives a request for the output port associated with the crosspoint of the first group, and
wherein the second condition occurs if at least one of the crosspoints of the first group receives a request for the output port associated with the crosspoints of the first group.
10. The device of claim 8 wherein the other first condition occurs if none of the crosspoints of the second group receives a request for the output port associated with the crosspoints of the second group, and
wherein the other second condition occurs if at least one of the crosspoints of the second group receives a request for the output port associated with the crosspoints of the second group.
11. In a system having input ports, output ports, and a switching fabric for selectively connecting an input port to an output port, the switching fabric having a column associated with an output ports, the column comprising:
a) a first crosspoint group including
i) a switch having an input for accepting a token, a control input, a first output and a second output,
ii) an OR gate having a first input coupled with the first output of the switch, a second input, and an output for providing a token,
iii) a first crosspoint unit having a token input coupled with the second output of the switch and a token output coupled with a next crosspoint unit of the first crosspoint group,
iv) a last crosspoint unit having a token input coupled with the token output of a preceding crosspoint unit of the first crosspoint group and a token output coupled with the second input of the OR gate, and
v) switch control logic having an output for providing a control signal to the control input of the switch.
12. The switching fabric column of claim 11 wherein the switch control logic generates the control signal based on requests received by each of the crosspoint units of the first crosspoint group.
b) a second crosspoint group including
ii) an OR gate having a first input coupled with the first output of the switch of the second crosspoint group, a second input, and an output for providing a token,
iii) a first crosspoint unit having a token input coupled with the second output of the switch of the second crosspoint group and a token output coupled with a next crosspoint unit of the second crosspoint group,
iv) a last crosspoint unit having a token input coupled with the token output of a preceding crosspoint unit of the second crosspoint group and a token output coupled with the second input of the OR gate of the second crosspoint group, and
v) switch control logic having an output for providing a control signal to the control input of the switch of the second crosspoint group.
16. The switching fabric of claim 15 wherein the output of the OR gate of the first crosspoint group is coupled with the input of the switch of the second crosspoint group.
Benefit is claimed, under 35 U.S.C. §119(e)(1), to the filing date of provisional patent application serial number 60/085,672, entitled “MULTICAST CROSSPOINT SWITCHING ARCHITECTURE WITH TUNNELING RING RESERVATION”, filed on May 15, 1998 and listing Alper Altinordu and Hung-Hsiang J. Chao as the inventors, for any inventions enclosed in the manner provided by U.S.C. §112, ¶ 1. This provisional application is expressly incorporated herein by reference.
An input-output queued switch will result by an input queued switch using a speedup of greater than one (c>1). A recent study shows that it is possible to achieve 100% switch throughput with a moderate speedup of c=2. (See, e.g., the technical publication, R. Guerin, et al., “Delay and Throughput Performance of Speed-Up Input-Queuing Packet Switches”, IBM Research Report RC 20892, (June 1997).) Since each output port can receive up to c cells in a time slot (each input port can send up to c cells during the same time), the requirement on the number input-output matching found in each arbitration cycle (c cycles in a time slot) may possibly be relaxed, enabling simpler arbitration schemes. On the other hand, the arbitration time is reduced c times, making the time constraint for arbitration more stringent.
The present invention may meet stringent arbitration time constraints to resolve output port contention by using a novel token tunneling arbitration scheme for output port contention resolution. This scheme is a variation of the ring reservation method proposed in the article, B. Bingham et al, “Reservation-Based Contention Resolution Mechanism for Batcher-Banyan Packet Switches”, Electronic Letters, Vol. 24, No. 13, pp. 772-3 (June 1988) and is fair. The arbitration time of the ring reservation method is proportional to the number of switch ports. With token tunneling arbitration, it is possible to reduce the arbitration time to the order of the square root of the number of ports. The ring reservation method proposed in the Bingham article is implemented using sequential logic. On the other hand, the token tunneling arbitration scheme of the present invention is implemented with combinational logic that makes it even faster. Thus, the present invention has a comparable delay in the basic arbitration unit as the bi-directional arbiter described in the article, K. Genda et al, “A 160 Gb/s ATM Switching System Using an Internal Speed-Up Crossbar Switch”, Proc. GLOBECOM'94, pp. 123-33 (November 1994). However, the overall arbitration delay is much smaller with the present invention because of the token tunneling method. Furthermore, the present invention may be implemented with only two pins per output port, compared to six in the switch discussed in the Genda article. Crossbar chips are generally pad-limited and therefore the number of pins required per port determines the number of ports that can be accommodated in a single chip.
Having described an environment in which various aspects of the present invention may operate, processes, methods and apparatus which may be used are now described in §4.3 below.
Functions which may be performed by the input port controllers 910 are described in §4.3.2.1.1 below. Then, an exemplary structure for implementing the input port controllers 910 is described in §4.3.2.1.2 below. Finally, an operation of the exemplary structure is described in §4.3.2.1.3 below.
Note that since N of the virtual output queues 912 (VOQs) may correspond to unicast cells, a multicast pattern is generated for these virtual output queues 912. The generated multicast pattern has one HIGH (‘1’) bit corresponding to the requested output port with the remaining N-1 bits set to LOW (‘0’). In these virtual output queues 1262, the multicast pattern queue 1320 is not needed since the multicast pattern will always be the same. Since the (N+1)th virtual output queue 912 is reserved for multicast cells, it stores actual multicast patterns.
Having described an exemplary structure for implementing at least some aspects of the input port controller 910′, its operation and its interaction with a row of crosspoint units 926′ is now described in §4.3.2.1.3 below.
More specifically, in FIG. 14e, notice that the cell C3 advances into the buffer 1350, the cells C1 and C2 advance within the buffer 1350, (the appropriate bit of) the multicast pattern MP(C1) advances to the flip-flop 1382, (the appropriate bit of) the multicast pattern MP(C2) advances to the flip-flop 1384, and the multicast pattern MP(C3) advances into the buffer 1370. This time, since the OR result of all of the bits of the multicast pattern in the flip-flop 1382 (or distributed in the flip-flops 1382 of a row of crosspoint units 926′) will not be zero (‘0’) until the cell C1 has been forwarded to each of the requested output ports, the contents of the buffers will remain the same until the cell C1 has been forwarded to each of the requested output ports. FIG. 14e shows the contents of the exemplary input port controller 1250′/1260′ and the row of crosspoint units 9261 after initialization.
Recall that each bit of a multicast pattern associated with a cell corresponds to whether or not that cell is to be provided to an associated output port. Thus, if there are N output ports 930, the multicast pattern will have N bits and the switching fabric 920 will have rows of N crosspoint units 926″. Thus, a input load process 1640 associated with a row of crosspoint units 926″ may function to (i) accept a multicast pattern from a selected virtual output queue 912 of an associated input port 910, (ii) forward, to each of the crosspoint units 926″ of the row, an associated bit of the multicast pattern, (iii) to receive updates to the bits of the multicast pattern from the crosspoint units 926″ of the row, and (iv) to request a multicast pattern of a head of line cell from a next selected virtual output queue 912 of the input port controller 910 when all bits of the multicast pattern of the present cell are zero (‘0’). An exemplary method for effecting the load input process 1640 is described in §4.3.2.3.2.1 below. First, however, functions which may be performed by the token tunneling process 1630 are introduced in §4.3.2.3.1.2 below
Recall from step 1030 of FIG. 10, that in the dual round robin arbitration scheme of the present invention, that for each output port 930, a winner from among requesting input ports is chosen. Since each output port 930 is associated with a column of crosspoint units 926″, as will be described in more detail in §4.3.2.3.2.2 below, this second round robin arbitration may be effected by passing a token around the crosspoint units 926″ defining a column in the switching fabric 920. Basically, a crosspoint unit with a HIGH (‘1’) multicast pattern bit and a token will switch a cell at a vertical data (vd) input through to a horizontal data (hd) output. In the next arbitration round, the token will start at the next crosspoint unit. If the crosspoint unit 926″ has a LOW (‘0’) multicast pattern bit when it receives the token, it simply passes the token to the next crosspoint unit 926″ in the column.
FIG. 18 is illustrates a simple circuit for determining a request signal based on updated multicast pattern bits from a row 1810 of crosspoint units 926. In this case, the crosspoint units 926 are grouped to define a first group 1812 a of crosspoint units 926 and a second group 1812 b of crosspoint units 926. This grouping of crosspoint 926 units may correspond to a row of crosspoint units 926 across a number of crosspoint chips 924. In any event, the modified bits of the multicast pattern from each group are applied to an OR gate 1822 a or 1822 b. The results of the OR gate are then applied to a higher level OR gate 1820 which generates the request signal (hk). The updating of the bits of the multicast pattern, as well as the loading of the bits of the multicast pattern, will be described in more detail in the description of the crosspoint units in §4.3.2.3.3.1 below.
As can be appreciated from the foregoing, arbitration time becomes proportional to the number of ports of an crosspoint chip 924 (or of another grouping), rather than the number of ports of the entire switch fabric. More specifically, the worst case time complexity of the basic token tunneling method is 4n+2(N/n−2) gate delays. This worst case occurs when there is only one multicast pattern bit with a value of ‘1’in a column of crosspoint units 926 and it is at the farthest position from the round robin pointer. For example, the worst case delay occurs if the one HIGH (‘1’) multicast pattern bit is at the bottommost crosspoint unit 926, while the round robin pointer points to (i.e., the token is at) the topmost crosspoint unit 926. As will be described in §4.3.2.3.3.1 below, each crosspoint unit 926 contributes two (2) gate delays for output arbitration. In the worst case scenario, the token ripples through all the crosspoint units 926 in the crosspoint chip 924 (or other grouping) where the token is generated and all the crosspoint units 926 in the crosspoint chip 924 (or other grouping) in which the crosspoint unit with the HIGH (‘1’) multicast pattern bit is the last crosspoint unit 926. This contributes the 4n gates delay. Since there are a total N/n crosspoint circuits 924 (or other groupings) in each column, and at most (N/n−2) crosspoint circuits 924 (or other groupings) will be tunneled through, another 2(N/n−2) gate delays occurs in the worst case.
FIG. 20b is an alternative structure in which switches 2022, 2024, OR gates 2032, 2034, and the tunneling logic are arranged in a hierarchy to further reduce round robin arbitration delays. By tunneling through smaller groups of crosspoint units 926 (groups of size g) and arranging these groups in hierarchy as shown in FIG. 20b, it is possible to further reduce the worst case arbitration delay to 4g+5d+2(N/n−2) gate delays, where ┌d=log2(n/g)┐. The hierarchical arrangement basically decreases the time spent in the crosspoint chip 924 (or other grouping) where the token is generated and in the crosspoint chip 924 (or other grouping) in which the crosspoint unit with the HIGH (‘1’) multicast pattern bit is the last crosspoint unit 926. For example, if N=256, n=16, and g=2, the basic token tunneling structure of FIG. 20a has a worst case arbitration of 92 gate delays, whereas the hierarchical token tunneling structure of FIG. 20b has a worst case arbitration of only 51 gate delays.
The input value controller 2620 determines the value to be loaded into the flip-flop 2410′/1382 in the next arbitration cycle. If the output Q(N) of the flip-flop 2630/1384 is LOW (‘0’), the value stored in the flip-flop 2630/1384 will be loaded into the flip-flop 2410′/1382 under control of the handshake (hk) signal. More specifically, the value will be loaded into the flip-flop 2410′/1382 only after all of the multicast pattern bits in the row are LOW (‘0’). If, on the other hand, the output Q(N) of the flip-flop 2630/1382 is HIGH (‘1’), the operation of the input value controller 2620 will depend on the grant (en) signal. If the grant (en) signal is LOW (‘0’), the value stored in the flip-flop 2410′/1382 is preserved since the crosspoint unit 926″″ will not be switching through a cell in the current arbitration cycle. If, on the other hand, the grant (en) signal is HIGH (‘1’), the value stored in the flip-flop 2630/1384 will be loaded into the flip-flop 2410′/1382 under control of the handshake (hk) signal. Table 1 presented below is a truth table for the put value controller 2620.
0 0 0 1 X hk=0 and QH=1
0 0 1 1 X hk=0 and QH=1
1 0 0 0 X en=1 and QH=0
1 0 1 0 X en=1 and QH=0
The bypass disable (bp) output of the crosspoint unit 926″″ may be used by a token tunneling device to determine whether the crosspoint unit 926″″ can be bypassed. (Recall FIGS. 21a and 21 b.) The bypass disable (bp) signal is the logical OR (Note OR gate 2650.) of the multicast pattern bit from the flip-flop 2410′/1382 and the token generation point (tgp) signal output by the token generation controller 2610. If the mulitcast pattern bit is HIGH (‘1’) or if the crosspoint unit 926″″ is the token generation point, then the crosspoint unit 926″″ should not be bypassed by the token. It is clear that the crosspoint unit 926″″ should not be bypassed if its multicast pattern bit is HIGH (‘1’). Even if its multicast pattern bit is LOW (‘0’), the crosspoint unit 926″″ should not be bypassed because if all of the other multicast pattern bits in the column are LOW (‘0’), then it should be able to receive the token that it generated.
For a 256×256 switch with the incoming aggregated bandwidth of 5 Gb/s and internal speedup (c) of two (2), the line bandwidth of the switch fabric is 10 Gb/s. The total switch capacity is 5 Gb/s×256, or 1.28 Tb/s. The cell length can be chosen to be 64 bytes to accommodate the smallest internet protocol packet size (40 bytes). The switch fabric has four (4) switch planes 922. Assuming that each crosspoint chip 924 can accommodate 16 ports, the switch plane 922 has (256/16)2, or 256 crosspoint chips 924. In other words, the entire switch fabric with four (4) switch planes needs 1,024 crosspoint units 926. If more ports (e.g., 32) can be accommodated by a crosspoint chip 924, then the total number of crosspoint chips 924 in each plane 922 can be reduced (e.g., to 64). However, the pin count of each of the crosspoint chips 924 will be proportionally increased, which may be prohibited due to high packaging cost and power consumption.
(d) if, after modification, all bits of the multicast pattern in a row are LOW (‘0’), then a handshake signal (HSK) may be applied to the input port 910 associated with the row during the cycle (i+1) (A handshake signal is determined to be LOW (‘0’) or HIGH (‘1’) in any event.). Although these steps were shown as operating in a serial sequence, it is possible to have some operations take place concurrently. Further, in some cycles, not all of these operations will be performed. For example, the bits of a multicast pattern are loaded into a row of crosspoint units 926 only if the handshake signal was asserted in the previous cycle.
An exemplary architecture, which employs the foregoing method 3330 and which can handle P=four (4) priority levels, is now described. Cells, as well as multicast patterns of the cells at each input are stored in priority queues in the corresponding input ports 910. The head of line and next to head of line multicast pattern bits of all of the four (4) priority queues are stored in the corresponding crosspoint units 926 of a row. More than one priority level's head of line multicast pattern bits stored in a crosspoint unit 926 can be HIGH (‘1’) simultaneously. This means that more than one head of line cell in the input virtual priority queues request to the switched through that crosspoint unit 926. A crosspoint unit 926 will always try to serve the highest priority request. In this exemplary structure, a crosspoint unit 926 will always try to serve the highest priority request. Thus, in such cases, the crosspoint unit 926 will enter the contention in its column using the highest priority request made to it. FIG. 34 illustrates the storage of bits of multicast patterns for four (4) priority levels stored in a row of four (4) crosspoint units. As shown, within each of the input port controllers, the multicast patterns for head of line and next to head of line cells for each of the four (4) priority levels are stored in multicast pattern queues 1320 a′ through 1320 d′. Within each of the crosspoint units, a flip-flop 1382 a′ stores a bit of the head of line multicast pattern of a first priority level cell associated with the output port of the column, a flip-flop 1382 b′ stores a bit of the head of line multicast pattern of a second priority level cell associated with the output port of the column, a flip-flop 1382 c′ stores a bit of the head of line multicast pattern of a third priority level cell associated with the output port of the column, and a flip-flop 1382 d′ stores a bit of the head of line multicast pattern of a fourth priority level cell associated with the output port of the column. Flip-flops 1384 a′ through 1384 d′ may also be provided to similarly store bits of the next to head of line multicast pattern of first through fourth priority level cells.
US6909710 * Dec 30, 2002 Jun 21, 2005 International Business Machines Corporation Method of operating a buffered crossbar switch
US7224671 * Aug 15, 2001 May 29, 2007 Force10 Networks, Inc. Method and apparatus for load balancing in network processing device
US7349388 * Dec 30, 2002 Mar 25, 2008 International Business Machines Corporation Buffered crossbar switch and its method of operation
US7486683 * Jul 20, 2004 Feb 3, 2009 International Business Machines Corporation Algorithm and system for selecting acknowledgments from an array of collapsed VOQ's
US7826434 Dec 5, 2007 Nov 2, 2010 International Business Machines Corporation Buffered crossbar switch
US8325715 * Feb 9, 2007 Dec 4, 2012 Futurewei Technologies, Inc. Internet switch router
US8804709 * Mar 9, 2012 Aug 12, 2014 Juniper Networks, Inc. Switching device
US8930582 * Oct 31, 2003 Jan 6, 2015 Oracle America, Inc. Method and apparatus for regulating communications between multiple transmitters and receivers
US9135201 May 25, 2011 Sep 15, 2015 International Business Machines Corporation Switching device for routing data, computer interconnection network and routing method using such device
US9160685 Mar 9, 2012 Oct 13, 2015 Cisco Technology, Inc. Large interconnect fabrics
US20050053078 * Jul 20, 2004 Mar 10, 2005 International Business Machines Corporation Algorithm and system for selecting acknowledgments from an array of collapsed VOQ's
US20050122907 * Oct 31, 2003 Jun 9, 2005 Ebergen Josephus C. Method and apparatus for regulating communications between multiple transmitters and receivers
US20080089352 * Dec 5, 2007 Apr 17, 2008 International Business Machines Corporation Buffered crossbar switch
US20080215786 * Mar 2, 2006 Sep 4, 2008 Koninklijke Philips Electronics, N.V. Electronic Device And A Method For Arbitrating Shared Resources
US20120163375 * Mar 9, 2012 Jun 28, 2012 Juniper Networks, Inc. Switching device
CN102906729A * May 25, 2011 Jan 30, 2013 国际商业机器公司 Switching device for routing data, computer interconnection network and routing method using such device
CN102906729B * May 25, 2011 Aug 24, 2016 国际商业机器公司 用于路由数据的交换装置、使用此装置的计算机互连网络与路由方法
CN103416033A * Mar 9, 2012 Nov 27, 2013 思科技术公司 Large interconnect fabrics
CN103416033B * Mar 9, 2012 Apr 5, 2017 思科技术公司 大型互联架构
WO2012122538A1 * Mar 9, 2012 Sep 13, 2012 Cisco Technology, Inc. Large interconnect fabrics
U.S. Classification 370/461, 370/447, 370/445, 370/462, 370/450
Cooperative Classification H04L49/25, H04L2012/5679, H04L49/3045, H04L49/50, H04L49/1523, H04L49/101, H04L49/30, H04L49/3081, H04L2012/5651
European Classification H04L49/25, H04L49/30E, H04L49/30J, H04L49/50
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CHAO, HUNG-HSIANG JONATHAN;ALTINORDU, ALPER;REEL/FRAME:010284/0832;SIGNING DATES FROM 19990818 TO 19990826