Communication network and a method of regulating the transmission of data packets in a communication network

• US 5,245,609 A
• Filed: 01/30/1991
• Issued: 09/14/1993
• Est. Priority Date: 01/30/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ofek, Yoram, Yung, Marcel M.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US07/647,767
• Time in Patent Office: 958 Days
• Field of Search: 370/93.4, 370/825.02
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

A two-phase fairness algorithm for regulating the transmission of data packets in a communication network having a multitude of nodes connected together to form a spanning tree. In a first or broadcast phase of the fairness algorithm, a first control signal is transmitted over the spanning tree from a root node or a root edge of the tree. This first control signal indicates to each node of the tree a first number of data packets that the node is permitted to transmit in a corresponding time interval. Each intermediate node of the tree transmits the first signal to each of its children nodes only when one or more various conditions relating to the transmission of data packets are satisfied. In a second or merge phase of the fairness algorithm, a second control signal is transmitted from the leaves of the tree to the root node or root edge of the tree. Each intermediate node of the tree transmits the second signal to its parent node only after receiving the second signal from all of its children nodes and after one or more various conditions relating to the transmission of data packets from the intermediate node to its parent node are satisfied. After the root node or root edge of the tree receives the second signal from all of its or their children nodes, the algorithm is repeated.

Claims

1. A method of regulating the transmission of packets in a communications network having a number of nodes, said number of nodes including a root node, a multitude of leaf nodes and a multitude of intermediate nodes, the nodes of the network being connected together to form a tree that is part of a general topology network, the method comprising:

(a) transmitting a first control signal over said spanning tree from the root node to each of the other nodes of the network, the first control signal indicating to each of said other nodes a first number of data packets that said each of said other nodes is permitted to transmit in a corresponding time interval, each intermediate node transmitting the first control signal to another node in the network only when a first corresponding predetermined condition is satisfied;

(b) transmitting a second control signal over the spanning tree from the leaf nodes, to the intermediate nodes and to the root node, each intermediate node transmitting the second control signal to another node in the network only when a second corresponding predetermined condition is satisfied; and

(c) repeating step (a) only when the root node has received the second control signal from each of selected ones of the other nodes.

2. A method according to claim 1, wherein:

the spanning tree forms a multitude of branches extending between the root node and the leaf nodes, each of said branches including at least a plurality of the nodes arranged in sequence along the branch;

on each branch, each node next to another node on the branch in a first direction comprises a parent of said another node, and each node next to another node on the branch in a second, opposite direction comprises a child of said another node; and

the first corresponding predetermined condition is satisfied when each intermediate node transmits to its parent node during the corresponding time interval, either a respective predetermined number of packets, or all packets said each intermediate node has to transmit to the child parent node.

3. A method according to claim 2, wherein the first predetermined condition is also satisfied upon the expiration of a predetermined length of time after said corresponding time interval.

4. A method according to claim 2, wherein the corresponding time interval for each intermediate node is the time between receipt by said each intermediate node of two consecutive first control signals.

5. A method according to claim 2, wherein the second corresponding predetermined condition is satisfied when each intermediate node has received from each of its children nodes either a predetermined number of packets, or all packets said each child node has to transmit to said each intermediate node.

6. A method according to claim 1, wherein each node of the network is capable of being the root nodes.

7. A method according to claim 1, wherein each node of the network initiates step (a) upon the occurrence of predetermined events.

8. A communication network, comprising:

a multitude of nodes for transmitting data packets between the network and a multitude of user stations and for routing the data packets around the network, the multitude of nodes including a root node, a multitude of leaf nodes and a multitude of intermediate nodes located between the root and leaf nodes; and

a multitude of links interconnecting the nodes to transmit data packets and control signals therebetween, each of the links connecting together two of the nodes to transmit data packets and said control signals in first and second opposite directions between said two nodes, each of the nodes being connected to at least one of the links, and the links connecting the nodes together to form a spanning tree structure traversing each of the nodes of the network at least once, the spanning tree forming a multitude of branches extending between the root node and the leaf nodes, each of said branches including at least a plurality of the nodes arranged in sequence along the branch;

wherein on each branch of the spanning tree, each node next to another node on the branch in a first direction comprises a parent of said another node; and

each node next to another node in the branch in a second, opposite direction comprises a child of said another node;

each of the nodes including means to start a two-phase control cycle,

in a first phase of the control cycle, the root node transmits a first control signal over a part of the spanning tree; and

in the first phase of the control cycle, each intermediate node of said part of the tree transmits the first control signal to each child node of said intermediate node after said each intermediate node receives the first control signal and a first corresponding predetermined condition is satisfied.

the first control signal indicating to each of the nodes on said part of the tree a first number of data packets that each of the nodes on said part of the spanning tree is permitted to transmit in a corresponding time interval, and

in a second phase of the control cycle, each of the tree transmits a second control signal to a selected one of the other nodes of the tree to indicate completion of the first phase of the cycle.

9. A communication network according to claim 8, wherein:

in the second phase of the control cycle, each intermediate node of the tree transmits the second control signal to the parent of said each intermediate node when a second corresponding predetermined condition is satisfied.

10. A communication network according to claim 9, wherein:

the first predetermined condition is satisfied when said each intermediate node transmits to each child node thereof during the corresponding time interval either a respective predetermined number of packets, or all packets said each intermediate node has to transmit to said each child node.

11. A communication network according to claim 10, wherein the first predetermined condition is also satisfied upon the expiration of a predetermined length of time after said corresponding time interval.

12. A communication network according to claim 9, wherein the second predetermined conditions is satisfied when said each intermediate node of the tree has transmitted to the parent node thereof either a predetermined number of data packets, or all data packets said each intermediate node has to transmit to said parent node.

13. A communication network according to claim 12, wherein the second predetermined condition is also satisfied upon the expiration of a predetermined length of time after said corresponding time interval.

14. A communication network comprising:

a multitude of nodes for transmitting data packets between the network and a multitude of user stations, and for routing the data packets around the network; and

a multitude of links interconnecting the nodes to transmit data packets and first and second control signals therebetween, each of the links connecting together two of the nodes to transmit data packets and said control signals in first and second opposite directions between said two nodes, the links connecting the nodes together to form a spanning tree structure traversing each of the nodes of the network at least once, each of the nodes being connected to at least one of the links;

each node including

i) means to determine whether the first control signal has been transmitted to the node over a predetermined one of the links within a first corresponding time period; and

(1) if the first control signal has been transmitted to the node over said predetermined one of the links within the first corresponding time period, to transmit the first control signal over each of the other links connected to the node, other than said predetermined one of the links, if the node has transmitted to each of said other links, during a second corresponding time period, either a respective predetermined number of data packets, or all data packets the node has to transmit to said each of said other links, and (2) if the first control signal has not been transmitted to the node over said predetermined one of the links within the first corresponding time period, to transmit the first control signal over all of the links connected to the node, and

ii) means to determine whether the second control signal has been transmitted to the node over all but one of the links connected to the node within a third corresponding time period; and

(1) if the second control signal has been transmitted to the node over all but said one of the links connected to the node during said third corresponding time period, to transmit the second control signal over said one of the links if the node has transmitted to said one of the links, during a fourth corresponding time period, either a predetermined number of data packets, or all data packets the node has to transmit to said one of the links, and (2) if the second control signal has not been transmitted to the node over all but one of the links connected to the node within the third corresponding time period, to transmit the first control signal over all of the links connected to the node.

15. A communication network according to claim 14, wherein the predetermined one of the links is the link over which the node last transmitted the second signal.

16. A communication network according to claim 15, wherein the said one of the links is the link over which the node last received the first signal.