Scheme for avoiding deadlock in multi-ring interconnect, with additional application to congestion control

Abstract

A method and system to avoid multi-ring deadlock. The method includes removing a message on a multi-ring interconnect either with a ring connector associated with the target of the message or by the message's source station such that the message travels no more than one time around the slotted ring interconnect before its removal. The method may also be applied to single ring networks for congestion control.

1 - 31 . (canceled) 
     
     
         32 . A network comprising:
 at least one source station;   at least one target station;   at least one source slotted ring interconnect comprising a plurality of slots, the source station operably connected to the source slotted ring interconnect;   at least one target slotted ring interconnect comprising a plurality of slots, the target station operably connected to the target slotted ring interconnect, wherein the target slotted ring interconnect and the source slotted ring interconnect are different; and   at least one ring connector connecting the source slotted ring interconnect and the target slotted ring interconnect,   wherein the source station is configured to transmit a message to one of the plurality of slots of the source slotted ring interconnect such that the message travels around the source slotted ring interconnect,   wherein, if the ring connector or the target station is able to receive the message, the ring connector or the target station is configured to remove the message from the source slotted ring interconnect, otherwise the ring connector or the target station is configured to mark the message with a negative flag, and the source station is configured to remove the message marked with the negative flag from the source slotted ring interconnect, such that the message travels no more than one time around the source slotted ring interconnect before removal.   
     
     
         33 . The network of  claim 32 , wherein the target is the ring connector or another ring connector associated with a target station operably connected to the target slotted ring interconnect. 
     
     
         34 . The network of  claim 32 , wherein the source slotted ring interconnect is arranged to operate as a circular shift register. 
     
     
         35 . The network of  claim 32 , wherein the message carries an identification of a target station or a ring connector. 
     
     
         36 . The network of  claim 32 , wherein the source station, the target station, or both monitors the slot to which the source station, the target station, or both are attached for messages targeting the source station, the target station, or both. 
     
     
         37 . The network of  claim 32 , wherein the target station removes the message from a slot if the target station has sufficient resource to receive the message. 
     
     
         38 . The network of  claim 32 , wherein the ring connector is a bridge. 
     
     
         39 . The network of  claim 32 , wherein the ring connector includes a buffer capable of holding the message. 
     
     
         40 . The network of  claim 32 , wherein the source station keeps a copy of the message until the source station gets either a negative or a positive acknowledgement. 
     
     
         41 . A method to avoid multi-ring deadlock comprising:
 putting a message from a source station in a slot of a source slotted ring interconnect directed to a target station on a target slotted ring interconnect, wherein the source slotted ring interconnect and the target slotted ring interconnect are not the same;   allowing the message to travel around the source slotted ring interconnect; and   
       if the target station is able to receive the message, removing the message from the source slotted ring interconnect either with a ring connector connecting the source slotted ring interconnect and the target slotted ring interconnect or by the target station, and
 if the target station is not able to receive the message, marking the message with a negative flag and removing, by the source, the message marked with the negative flag from the source slotted ring interconnect, such that the message travels no more than one time around the source slotted ring interconnect before removal. 
 
     
     
         42 . The method of  claim 41 , wherein the ring connector includes a buffer capable of holding the message. 
     
     
         43 . The method of  claim 41 , further comprising keeping a copy of the message on the source station until the source station gets either a negative or a positive acknowledgement. 
     
     
         44 . The method of  claim 41 , wherein the message comprises a valid bit V, a negative acknowledgement bit N, and one destination bit D[k] per station or ring connector k on the ring, wherein k represents a station on the slotted ring interconnect. 
     
     
         45 . The method of  claim 44 , wherein the message includes a plurality of destination bits D, each of the plurality of destination bits D corresponding to a station operably attached to the source slotted ring interconnect. 
     
     
         46 . The method of  claim 44 , wherein a precondition for the message to be sent is V=0 and N=0 for the slot, wherein the valid bit V=0 represents that the slot is not occupied by a valid message, and the valid bit V=1 represents that the slot is occupied by a valid message. 
     
     
         47 . The method of  claim 46 , further comprising setting V:=1, D[s]:=1, and D[t]:=1 when a message is sent, where D[s] is a destination bit of the source station and D[t] is the destination bit of the target station. 
     
     
         48 . The method of  claim 44 , wherein the target receives a message if V=1 and N=0 and D[t]=1, where D[t] is the destination bit of the target station. 
     
     
         49 . The method of  claim 48 , further comprising setting V:=0, D[s]:=0, and D[t]:=0 when a message is received. 
     
     
         50 . The method of  claim 44 , further comprising setting a negative acknowledgement by setting V:=0 and N:=1 and D[s]:=1 if the target cannot receive the message. 
     
     
         51 . The method of  claim 44 , further comprising the source station counting time and performing checks in the clock when either positive or negative acknowledgement is scheduled to arrive. 
     
     
         52 . The method of  claim 51 , further comprising removing the message from the ring by setting N:=0 and D[s]:=0 if the message arrives with V=0 and N=1 and D[s]=1. 
     
     
         53 . The method of  claim 52 , wherein the source station recognizes that D[s]=1 indicates a negative acknowledgement and that the message needs to be re-sent at a later time. 
     
     
         54 . The method of  claim 52 , further comprising allowing the source station to send a different message if the source station has another message to send. 
     
     
         55 . The method of  claim 51 , further comprising discarding the message if the message arrives with D[s]=0. 
     
     
         56 . The method of  claim 55 , wherein the source station recognizes that D[s]=0 indicates a positive acknowledgement and that the original message has been successfully delivered. 
     
     
         57 . The method of  claim 51 , wherein if D[s]=1 and V=1 and N=0 and the source station can receive a new message, setting V:=0, D[s]:=0, and D[u]:=0 when the new message is received, wherein D[u] is the destination bit of a target station u. 
     
     
         58 . The method of  claim 51 , wherein if D[s]=1 and V=1 and N=0 and the source station cannot receive a new message, setting a negative acknowledgement by setting V:=0 and N:=1 and D[s]:=0. 
     
     
         59 . A method comprising:
 controlling congestion on a network with a single slotted ring interconnect comprising limiting the slot occupancy of a message from a source station to a target station to at most one cycle around the slotted ring marking the message with a negative flag, if the target station is not able to receive the message, and removing, by the source station, the message marked with the negative flag; and   determining a wait time by a the source station to be used by the source station for resending the message based on an occupancy rate of one or more slots of the slotted ring interconnect.   
     
     
         60 . The method of  claim 59 , further comprising monitoring the occupancy rate of the one or more slots by the source station in the network comprising the slotted ring interconnect as the slots rotate past the source station and use that information to control how soon the message that had been previously not received by the target station should be resent by the source station. 
     
     
         61 . The method of  claim 60 , comprising increasing a wait time before resending the message that had been previously not received by the target. 
     
     
         62 . The method of  claim 61 , wherein increasing the wait time reduces the congestion on the slotted ring interconnect.