Network topology of hierarchical ring with recursive shortcuts

Patent metadata

Field	Value
Publication number	US-9825844-B2
Application number	US-201615365460-A
Country	US
Kind code	B2
Filing date	Nov 30, 2016
Priority date	Oct 30, 2013
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

An interconnection system comprising a plurality of nodes, each comprising at least two ports, and a plurality of links configured to interconnect ports among the nodes to form a hierarchical multi-level ring topology, wherein the ring topology comprises a plurality of levels of rings including a base ring and at least two hierarchical shortcut rings, and wherein each node connected to a higher-level shortcut ring is also connected to all lower-level rings including the base ring.

First claim

What is claimed is:

1. A node in a recursive ring network topology comprising a plurality of nodes, comprising:
a first port for coupling to an adjacent first node via a base link in a base ring, wherein the first port is configured to receive a first message from the first node over the base link;
a second port for coupling to a non-adjacent second node via a first shortcut link in a first level shortcut ring, wherein the second port is configured to receive a second message from the second node over the first shortcut link;
a third port for coupling to a non-adjacent third node via a second shortcut link in a second level shortcut ring, wherein the third port is configured to receive a third message from the third node over the second shortcut link; and
a processor coupled to the first, second, and third ports, wherein the processor is configured to determine a shortest path for each of the first, second, and third messages, and
wherein a number of intermediate nodes positioned between the third node and the node along the base ring is at least double a number of intermediate nodes between the second node and the node along the base ring,
wherein all nodes connected to the second level shortcut ring are also connected to the first level shortcut ring, and
wherein at least one node connected to the first level shortcut ring is not connected to the second level shortcut ring.

2. The node of claim 1 , wherein N is a positive integer representing a total number of the plurality of nodes, wherein the second level shortcut ring is a level k ring, wherein k is an integer that satisfies relationship 2<=k<=(Log h (N)−1), wherein h is an integer that satisfies 2<=h<=N, and wherein the third node and the node are separated by (h k −1) intermediate nodes along the base ring.

3. The node of claim 1 , wherein the plurality of nodes are arranged such that the nodes are represented using consecutive integer addresses ranging from 0 to N−1 in a single direction on the ring network topology, wherein N is a positive integer representing a total number of the plurality of nodes, wherein the links are configured such that node addresses (h k )*I are employed for a level k ring, and wherein h, k, and I are integers that satisfy relationships

2
<=
h
<=
N

,

0
<=
k
<=

(

Log
h

⁡

(
N
)

-
1

)

,

and
⁢

⁢
0

<=
I
<=

(

N

h
k

-
1

)

.

4. The node of claim 1 , further comprising at least one receiver coupled to the first, second, and third ports, wherein the receiver is configured to:
receive the first message from the first node over the base link;
receive the second message from the second node over the first shortcut link; and
receive the third message from the third node over the second shortcut link.

5. The node of claim 1 , wherein the processor is configured to determine a first shortest path to a first destination for the first message, a second shortest path to a second destination for the second message, and a third shortest path to a third destination for the third message.

6. The node of claim 5 , further comprising a transmitter coupled to the processor and configured to:
transmit the first message over the first shortest path to the first destination;
transmit the second message over the second shortest path to the second destination; and
transmit the third message over the third shortest path to the third destination.

7. The node of claim 6 , further comprising at least one memory coupled to the processor and configured to:
store the first message in a first queue for storing messages from the base ring;
store the second message in a second queue for storing messages from the first level shortcut ring; and
store the third message in a third queue for storing messages from the second level shortcut ring.

8. The node of claim 7 , wherein the at least one memory is further configured to store a shortest path routing table, and wherein determining the first, second, and third shortest paths comprises looking up entries in the shortest path routing table.

9. The node of claim 1 , wherein the node employs at least two virtual channels (VCs) for transferring messages, and wherein a routing direction of the messages is changed by switching between virtual channels.

10. A first node configured to route messages in a recursive hierarchical ring network topology, comprising:
a receiver configured to receive a message from a second node over a shortcut link in a level k shortcut ring, wherein the first and second nodes are separated by (h k −1) intermediate nodes along a base ring, wherein k is an integer that satisfies relationship 1<=k<=(Log h (N)−1), wherein N is a positive integer representing a total number of a plurality of nodes available in the recursive hierarchical ring network topology, and wherein h is an integer that satisfies 2<=h<=N;
a processor operably coupled to the receiver and configured to determine a shortest path to a third node that is along a route of the message to an intended destination node, wherein the shortest path is selected from a group of paths that traverse the recursive hierarchical ring network topology in a clockwise direction or a counter clockwise direction, but not both; and
a transmitter operably coupled to the processor and configured to transmit the message to the third node over the determined shortest path.

11. The first node of claim 10 , wherein the plurality of nodes are represented by consecutive integer addresses ranging from 0 to N−1 in a single direction on the recursive hierarchical ring network topology.

12. The first node of claim 10 , wherein the shortest path is determined by predicting available shortcuts to the third node by presuming that all shortcut links are configured such that node addresses (h k )*I are used for a level k ring, wherein I is an integer that satisfies relationship

0
<=
I
<=

(

N

h
k

-

Assignees

• Futurewei Technologies Inc

Inventors

• Lih Iulin
• Lynch William

Classifications

• Y02B60/1225

  Cross-Sectional Technologies · mapped topic

• H04L45/64

  using an overlay routing layer · CPC title

• G06F15/17362

  hierarchical topologies · CPC title

• H04L2012/421

  Interconnected ring systems · CPC title

• Y02B60/1207

  Cross-Sectional Technologies · mapped topic