Forward progress mechanisms for a communications network having multiple nodes

Patent metadata

Field	Value
Publication number	US-11483209-B2
Application number	US-201916688814-A
Country	US
Kind code	B2
Filing date	Nov 19, 2019
Priority date	Nov 19, 2019
Publication date	Oct 25, 2022
Grant date	Oct 25, 2022

Abstract

A communication network includes: a plurality of nodes in a topology, with each node having an upstream and a downstream neighboring node in the topology; a separate unidirectional communication link coupled between each node and that node's downstream neighboring node; and a separate unidirectional control link coupled between each node and that node's upstream neighboring node. A controller in each node keeps a count of packets sent by that node via the corresponding unidirectional communication link. The controller uses the count of packets sent to determine whether a given packet is allowed to be sent from that node to the downstream neighboring node and, if so, whether a full rate or a throttled rate is to be used for sending the given packet. Based at least in part on the determining, the controller selectively sends the given packet to the downstream neighboring node.

First claim

What is claimed is:

1. A communication network, comprising:
a plurality of nodes configured in a topology, each node having an upstream neighboring node and a downstream neighboring node in the topology;
a separate unidirectional communication link coupled between each node and that node's downstream neighboring node, wherein packets sent from nodes in the topology are forwarded from node to node via corresponding unidirectional communication links until reaching destination nodes; and
a controller in each node, wherein the controller in each node is configured to:
keep a count of packets sent by that node;
use the count of packets sent to determine whether a given packet is to be sent from that node to the downstream neighboring node by determining that: packets are not allowed to be sent when the count of packets sent is equal to a maximum threshold, packets are to be sent at the throttled rate when the count of packets sent is equal to or greater than a minimum threshold but less than the maximum threshold, and packets are to be sent at the full rate when the count of packets sent is less than the minimum threshold; and
based at least in part on the determining, selectively send the given packet to the downstream neighboring node.

2. The communication network of claim 1 , wherein:
sending packets at the full rate includes sending a packet in each cycle of a controlling clock when a packet is available to be sent; and
sending packets at the throttled rate includes sending a packet in fewer than each cycle of a controlling clock when a packet is available to be sent.

3. The communication network of claim 2 , wherein sending a packet in fewer than each cycle of the controlling clock includes:
sending packets at variable rates in terms of clock cycles per packet based at least in part on a value of the count of packets sent between the minimum threshold and the maximum threshold, wherein:
higher rates are used when the value of the count of packets sent is closer to the minimum threshold; and
lower rates are used when the value of the count of packets sent is closer to the maximum threshold.

4. The communication network of claim 1 , wherein the controller in each node or another entity is configured to dynamically set at least one of the respective minimum threshold and the maximum threshold based on one or more operating criteria.

5. The communication network of claim 1 , further comprising:
a separate unidirectional control link coupled between each node and that node's upstream neighboring node, wherein a control token is passed from node to node in the topology via the unidirectional control links;
wherein, for keeping a count of packets sent by each node, the controller in that node is configured to:
increment a respective count of packets sent upon sending each packet; and
set the respective count of packets sent to zero upon passing the control token to the upstream neighboring node.

6. The communication network of claim 1 , wherein the controller in each node is configured to:
receive packets destined for an other node from that node's upstream neighboring node via the unidirectional communication link between the upstream neighboring node and that node; and
forward the packets to that node's downstream neighboring node via the unidirectional communication link between that node and the downstream neighboring node;
wherein, while forwarding packets received from the upstream neighboring node, that node is unable to send that node's own packets to the downstream neighboring node.

7. The communication network of claim 1 , further comprising:
a separate unidirectional control link coupled between each node and that node's upstream neighboring node, wherein a control token is passed from node to node in the topology via the unidirectional control links;
wherein each controller is configured to, upon being passed the control token from the downstream neighboring node:
determine a respective count of packets sent;
determine whether that node has packets to be sent;
when the respective count of packets sent is equal to or greater than a minimum threshold or the node has no packets to send, that controller is configured to:
zero the respective count of packets sent; and
pass the control token to the upstream neighboring node; and

when the respective count of packets sent is less than a minimum threshold and the node has packets to send, that controller is configured to:
hold the control token; and
send packets to the downstream neighboring node via the unidirectional communication link between that node and the downstream neighboring node in cycles of a controlling clock in which that node is not forwarding packets received from the upstream neighboring node.

8. The communication network of claim 7 , wherein:
upon sending each packet to a given node that is holding the control token, a particular upstream neighboring node is configured to increment a respective count of packets sent; and
when the particular upstream neighboring node has sent sufficient packets to increment the respective count of packets sent to be equal to a maximum threshold value, the particular upstream neighboring node is configured to halt sending packets, thereby avoiding sending packets to the given node that block the given node from sending the given node's own packets and freeing the given node to make forward progress in sending the given node's own packets.

9. The communication network of claim 1 , further comprising:
a separate unidirectional control link coupled between each node and that node's upstream neighboring node, wherein a control token is passed from node to node in the topology via the unidirectional control links;
wherein the control token is passed from node to node in the topology in a first direction on the unidirectional control links, the first direction being opposite to a second direction in which packets are sent and forwarded between nodes in the topology on the unidirectional communication links.

10. The communication network of claim 1 , wherein the topology is or is included in a ring, a mesh, or a star topology.

11. A communication network, comprising:
a plurality of first topology nodes configured in a first topology, each first topology node having: an upstream neighboring first topology node and a downstream neighboring first topology node in the first topology, a separate unidirectional communication link coupled between that first topology node and that first topology node's downstream neighboring first topology node, and a separate unidirectional control link coupled between that first topology node and that first topology node's upstream neighboring first topology node, wherein packets sent from first topology nodes are forwarded from first topology node to first topology node in the first topology via corresponding unidirectional communication links until reaching destination first topology nodes;
a plurality of second topology nodes configured in a second topology, each second topology node having: an upstream neighboring second topology node and a downstream neighboring second topology node in the second topology, a separate unidirectional communication link coupled between that second topology node and that second topology node's downstream neighboring second topology node, and a separate unidirectional control link coupled between that second topology node and that second topology node's upstream neighboring second topology node, wherein packets sent from second topology nodes are forwarded from second topology node to second topology node in the second topology via corresponding unidirectional communication links until reaching dest

Assignees

• Advanced Micro Devices Inc

Inventors

• Kelley John
• Shenoy Kartik

Classifications

• H04L43/0894

  Packet rate · CPC title

• H04L43/16

  Threshold monitoring · CPC title

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title

• H04L41/0894

  Policy-based network configuration management · CPC title