# US 2010/0074106 A1 · Scheme for avoiding deadlock in multi-ring interconnect, with additional application to congestion control

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0074106 A1
- Document ID: US20100074106A1
- Status: Published application
- Kind: A1
- Application number: 12/238,194
- Filed: 2008-09-25
- Published: 2010-03-25
- Earliest claimed: 2008-09-25
- Assignees: Intel Corporation
- Inventors: Ching-Tsun Chou; Naveen Cherukuri
- Web page: https://patentgrep.com/patent/US20100074106A1

## CPC

- H04L 47/13: {in a LAN segment, e.g. ring or bus}
- H04L 12/43: with synchronous transmission, e.g. time division multiplex [TDM], slotted rings
- H04L 12/4637: {Interconnected ring systems}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim 1

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 source slotted ring interconnect;
at least one target slotted ring interconnect comprising a plurality of slots, the target station operably connected to the destination slotted ring; and
at least one ring connector connecting the source slotted ring interconnect and the target slotted ring interconnect,
wherein the network is adapted such that a message having a target is put in a slot on the source slotted ring interconnect by the source station, the message adapted to travel around the source slotted ring interconnect,
wherein the network is adapted to remove the message from the source slotted ring interconnect either by a target station, a ring connector, or by the source station such that the message travels no more than one time around the source slotted ring interconnect before removal.

### Claim 2 (depends on 1)

The network of claim 1, wherein the target is ring connector associated with a target station operably connected to the destination slotted ring.

### Claim 3 (depends on 1)

The network of claim 1, wherein the source slotted ring interconnect is adapted to operate as a circular shift register.

### Claim 4 (depends on 1)

The network of claim 1, wherein the message carries an identification of a target station or a ring connector.

### Claim 5 (depends on 1)

The network of claim 1, wherein the source and/or target station monitors the slot to which it is attached for messages targeting it.

### Claim 6 (depends on 1)

The network of claim 1, wherein the target station removes the message from a slot if the station has sufficient resource to receive the message.

### Claim 7 (depends on 1)

The network of claim 1, wherein the ring connector is a bridge.

### Claim 8 (depends on 1)

The network of claim 1, wherein the ring connector includes a buffer capable of holding the message.

### Claim 9 (depends on 1)

The network of claim 1, wherein the source station keeps a copy of the message until the source station gets either a negative or a positive acknowledgement.

### Claim 10

A method to avoid multi-ring deadlock comprising:
putting a message from a source station s in a slot of a source slotted ring interconnect, the message having a target destination t 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
removing the message from the source slotted ring interconnect either with a ring connector associated with the target or by the source station such that the message travels no more than one time around the source slotted ring interconnect before removal.

### Claim 11 (depends on 10)

The method of claim 10, wherein the ring connector includes a buffer capable of holding the message.

### Claim 12 (depends on 10)

The method of claim 10, further comprising keeping a copy of the message on the source station until the source station gets either a negative or a positive acknowledgement.

### Claim 13 (depends on 10)

The method of claim 10, 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.

### Claim 14 (depends on 13)

The method of claim 13, 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.

### Claim 15 (depends on 13)

The method of claim 13, wherein a precondition for the message to be sent is V=0 and N=0 for the source slot.

### Claim 16 (depends on 15)

The method of claim 15, further comprising setting V:=1, D[s]:=1, and D[t]:=1 when a message is sent, where D[s] is the destination bit of the source station and D[t] is the destination bit of the target destination.

### Claim 17 (depends on 13)

The method of claim 13, 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 destination.

### Claim 18 (depends on 17)

The method of claim 17, further comprising setting V:=0, D[s]:=0, and D[t]:=0 when a message is received.

### Claim 19 (depends on 13)

The method of claim 13, further comprising setting a negative acknowledgement by setting V:=0 and N:=1 and D[s]:=1 if the target cannot receive the message.

### Claim 20 (depends on 13)

The method of claim 13, further comprising the source station counting time and performing checks in the clock when either positive or negative acknowledgement is scheduled to arrive.

### Claim 21 (depends on 20)

The method of claim 20, 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.

### Claim 22 (depends on 21)

The method of claim 21, 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.

### Claim 23 (depends on 21)

The method of claim 21, further comprising allowing the source station to send a different message if the source station has another message to send.

### Claim 24 (depends on 20)

The method of claim 20, further comprising discarding the message if the message arrives with D[s]=0.

### Claim 25 (depends on 24)

The method of claim 24, wherein the source station recognizes that D[s]=0 indicates a positive acknowledgement and that the original message has been successfully delivered.

### Claim 26 (depends on 20)

The method of claim 20, wherein if D[s]=1 and V=1 and N=0 and the source slot 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 destination u which may or may not be the same as target destination t.

### Claim 27 (depends on 20)

The method of claim 20, wherein if D[s]=1 and V=1 and N=0 and the source slot cannot receive a new message, setting a negative acknowledgement by setting V:=0 and N:=1 and D[s]:=0.

### Claim 28

A method controlling congestion on a network with a single slotted ring interconnect comprising limiting the slot occupancy of a message to at most one cycle around the slotted ring interconnect.

### Claim 29 (depends on 28)

The method of claim 28, further comprising a source station in the network monitoring an occupancy rate of a plurality of slots comprising the slotted ring interconnect as the slots rotate past it and use that information to control how soon negatively acknowledged messages should be resent.

### Claim 30 (depends on 39)

The method of claim 39, comprising increasing a wait before resending negatively acknowledged messages.

### Claim 31 (depends on 30)

The method of claim 30, wherein increasing the wait time reduces the congestion on the slotted ring interconnect.
