System and method for optimizing the topology of a virtual ring based upon a TCP/IP network

• US 20070081461A1
• Filed: 10/03/2006
• Published: 04/12/2007
• Est. Priority Date: 10/06/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Denecheau, Lionel, Dispensa, Jean-Claude, Esteve, Denis
• Granted Patent: US 7,715,330 B2
• Time in Patent Office: Days
• US Class Current: 370/231
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

In a network having nodes, N nodes are members of a virtual communications ring for multicast communication among the N nodes, each of the N nodes being associated with only an upstream and a downstream one of the other N nodes. One of the N nodes manages changes in ring membership, including requesting the others of the N nodes to participate in measuring distances to a N+1th, node responsive to receiving an insertion request message. The manager node inserts the N+1th node in the communications ring responsive to receiving replies, which includes inserting the N+1th node in a selected location between two selected ones of the N nodes, such that the N nodes and the N+1th node are enabled to multicast messages around the ring. Due to the selected location of the N+1th node, communication distances for muticasted messages tend to be shorter than such distances that would otherwise occur.

Claims

1. A method in a network having nodes and a transport layer protocol providing end to end data transfer, wherein N of the nodes are members of a virtual communications ring for multicast communication among the N nodes, each of the N member nodes being logically associated with only a logically upstream one of the N nodes and a logically downstream one of the N nodes, and wherein for the communications ring one of the N nodes functions as a manager node for managing changes in ring membership, the method comprising:

a) requesting, by the manager node, the others of the N member nodes to participate in measuring respective communication distances to a N+1th, non-member node responsive to the manager node receiving an insertion request message from the non-member node; and

b) inserting, by the manager node, the N+1th node as a new member node in the communications ring responsive to receiving replies to the requesting, wherein the inserting includes inserting the N+1th node in a selected location between two selected ones of the N nodes, such that the N nodes and the N+1th node are enabled to multicast messages around the communication ring and communications distances for the muticasted messages tend to be shorter due to the selected location of the N+1th node than would communications distances that would arise for other possible locations of the N+1th node.

2. The method of claim 1, wherein a) includes:

sending, by the manager node to the manager node'"'"'s downstream node, a compute distance message including an address of the N+1th node, wherein the compute distance message is for each receiving one of the N node'"'"'s to send to its respective downstream node in the communications ring, so that the compute distance message is multicasted throughout the communications ring; and

wherein the method includes;

receiving, by the manager node from the manager node'"'"'s upstream node, a plurality of distance computed messages in response to the multicasted compute distance message.

3. The method of claim 1, wherein b) includes:

selecting, as a first one of the two selected ones of the N nodes, one of the N nodes having a shortest communications distance to the N+1th node; and

selecting, as a second one of the two selected ones of the N nodes, the one of the upstream and downstream nodes of the first selected node having a shortest communications distance to the N+1th node.

4. The method of claim 1, wherein the communications distance measurements are based on node response times.

5. The method of claim 1, wherein the communications distance measurements are based on numbers of routers between nodes.

6. The method of claim 1, wherein b) includes:

sending a change neighbour message by the manager node, wherein the change neighbour message communicates respective upstream and downstream node designations for the two selected ones of the N nodes relative to the N+1th node; and

receiving neighbour changed confirmation messages by the manager node from the two selected ones of the N member nodes.

7. An apparatus comprising:

a network having nodes and a transport layer protocol providing end to end data transfer;

wherein N selected ones of the nodes are members of a virtual communications ring for multicast communication among the N nodes, each of the N member nodes being logically associated with only a logically upstream one of the N nodes and a logically downstream one of the N nodes;

wherein one of the N nodes of the communications ring is operable to provide a manager node function for managing changes in ring membership, the manager node having a processor;

wherein the network includes a tangible, computer readable memory having program code for execution by the manager node processor, including;

first program code for requesting the others of the N member nodes to participate in measuring respective communication distances to a N+1th, non-member node responsive to the manager node receiving an insertion request message from the non-member node; and

second program code for inserting the N+1th node as a new member node in the communications ring responsive to receiving replies to the requesting, wherein the inserting includes inserting the N+1th node in a selected location between two selected ones of the N nodes, such that the N nodes and the N+1th node are enabled to multicast messages around the communication ring and communications distances for the muticasted messages tend to be shorter due to the selected location of the N+1th node than would be communications distances that would arise for other possible locations of the N+1th node.

8. The apparatus of claim 7, wherein the first program code includes:

program code for sending a compute distance message to the manager node'"'"'s downstream node, the message including an address of the N+1th node, wherein the message is for each receiving one of the N node'"'"'s to send to its respective downstream node in the communications ring, so that the compute distance message is multicasted throughout the communications ring; and

wherein the program code for execution by the manager node processor includes;

program code for receiving a plurality of distance computed messages from the manager node'"'"'s upstream node in response to the multicasted compute distance message.

9. The apparatus of claim 7, wherein the second program code includes:

program code for selecting, as a first one of the two selected ones of the N nodes, one of the N nodes having a shortest communications distance to the N+1th node; and

program code for selecting, as a second one of the two selected ones of the N nodes, the one of the upstream and downstream nodes of the first selected node having a shortest communications distance to the N+1th node.

10. The apparatus of claim 7, wherein the program code for execution by the manager node processor includes:

program code for measuring communications distances based on node response times.

11. The apparatus of claim 7, wherein the program code for execution by the manager node processor includes:

program code for measuring communications distances based on numbers of routers between nodes.

12. The apparatus of claim 7, wherein the second program code includes:

program code for sending a change neighbour message by the manager node, wherein the change neighbour message communicates respective upstream and downstream node designations for the two selected ones of the N nodes relative to the N+1th node; and

program code for receiving neighbour changed confirmation messages by the manager node from the two selected ones of the N member nodes.

13. A computer program product for use in a network having nodes and a transport layer protocol providing end to end data transfer, wherein N of the nodes are members of a virtual communications ring for multicast communication among the N nodes, each of the N member nodes being logically associated with only a logically upstream one of the N nodes and a logically downstream one of the N nodes, and wherein for the communications ring one of the N nodes functions as a manager node for managing changes in ring membership, the computer program product including a tangible, computer usable medium including computer usable program code for execution by the manager node, the program code including:

first program code for requesting the others of the N member nodes to participate in measuring respective communication distances to a N+1th, non-member node responsive to the manager node receiving an insertion request message from the non-member node; and

second program code for inserting the N+1th node as a new member node in the communications ring responsive to receiving replies to the requesting, wherein the inserting includes inserting the N+1th node in a selected location between two selected ones of the N nodes, such that the N nodes and the N+1th node are enabled to multicast messages around the communication ring and communications distances for the muticasted messages tend to be shorter due to the selected location of the N+1th node than would be communications distances that would arise for other possible locations of the N+1th node.

14. The computer program product of claim 13, wherein the first program code includes:

program code for sending a compute distance message to the manager node'"'"'s downstream node, the message including an address of the N+1th node, wherein the message is for each receiving one of the N node'"'"'s to send to its respective downstream node in the communications ring, so that the compute distance message is multicasted throughout the communications ring; and

wherein the program code for execution by the manager node processor includes;

program code for receiving a plurality of distance computed messages from the manager node'"'"'s upstream node in response to the multicasted compute distance message.

15. The computer program product of claim 13, wherein the second program code includes:

program code for selecting, as a first one of the two selected ones of the N nodes, one of the N nodes having a shortest communications distance to the N+1th node; and

program code for selecting, as a second one of the two selected ones of the N nodes, the one of the upstream and downstream nodes of the first selected node having a shortest communications distance to the N+1th node.

16. The computer program product of claim 13, wherein the program code for execution by the manager node processor includes:

program code for measuring communications distances based on node response times.

17. The computer program product of claim 13, wherein the program code for execution by the manager node processor includes:

program code for measuring communications distances based on numbers of routers between nodes.

18. The computer program product of claim 13, wherein the second program code includes:

program code for sending a change neighbour message by the manager node, wherein the change neighbour message communicates respective upstream and downstream node designations for the two selected ones of the N nodes relative to the N+1th node; and

program code for receiving neighbour changed confirmation messages by the manager node from the two selected ones of the N member nodes.

19. In a network having nodes, a method of providing a service to manage nodes, wherein the network includes a transport layer protocol providing end to end data transfer and N of the nodes are members of a virtual communications ring for multicast communication among the N nodes, each of the N member nodes being logically associated with only a logically upstream one of the N nodes and a logically downstream one of the N nodes, and wherein for the communications ring one of the N nodes functions as a manager node for managing changes in ring membership, the service comprising:

a) requesting, by the manager node, the others of the N member nodes to participate in measuring respective communication distances to a N+1th, non- member node responsive to the manager node receiving an insertion request message from the non-member node, wherein a) further includes;

sending, by the manager node to the manager node'"'"'s downstream node, a compute distance message, wherein the compute distance message is for each receiving one of the N node'"'"'s to send to its respective downstream node in the communications ring, so that the compute distance message is multicasted throughout the communications ring; and

b) inserting, by the manager node, the N+1th node as a new member node in the communications ring responsive to receiving replies to the requesting, wherein the inserting includes inserting the N+1th node in a selected location between two selected ones of the N nodes, such that the N nodes and the N+1th node are enabled to multicast messages around the communication ring and communications distances for the muticasted messages tend to be shorter due to the selected location of the N+1th node than would be communications distances that would arise for other possible locations of the N+1th node, wherein b) further includes;

inserting, by the manager node, the N+1th node as a new member node in the communications ring responsive to receiving replies to the requesting, wherein the inserting includes inserting the N+1th node in a selected location between two selected ones of the N nodes, such that the N nodes and the N+1th node are enabled to multicast messages around the communication ring and communications distances for the muticasted messages tend to be shorter due to the selected location of the N+1th node than would be communications distances that would arise for other possible locations of the N+1th node.

20. The method of providing a service of claim 19, comprising:

sending a change neighbour message by the manager node, wherein the change neighbour message communicates respective upstream and downstream node designations for the two selected ones of the N nodes relative to the N+1th node; and

receiving neighbour changed confirmation messages by the manager node from the two selected ones of the N member nodes.