Detecting and breaking cycles in a computer network

• US 7,327,741 B1
• Filed: 12/20/2002
• Issued: 02/05/2008
• Est. Priority Date: 12/20/2002
• Status: Expired due to Fees

• Current Assignee: NortonLifeLock Inc.
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Slaughter, Gregory L., Saulpaugh, Thomas
• Primary Examiner(s): Kizou; Massan
• Assistant Examiner(s): ZHU, BO HUI ALVIN
• Application Number:
  US10/324,872
• Time in Patent Office: 1,873 Days
• Field of Search: 370/254, 370/255, 370/389, 370/390, 370/396, 370/432
• US Class Current: 370/396
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways

Abstract

Various embodiments of a system and method related to a computer network capable of detecting and breaking cycles are disclosed. First routing information usable to send messages to a first address may be created. The first address may be associated with multiple nodes in the network. When sending a message from a first node to the first address according to the first routing information, a cycle may be detected. The first routing information may be changed to break the cycle.

Claims

1. A method comprising:

storing routing information on each of a plurality of nodes, wherein the routing information on each node specifies one or more links over which to send messages addressed to a first address, wherein two or more of the nodes each host an instance of the first address;

sending a message addressed to the first address from a first node of the plurality of nodes;

a second node of the plurality of nodes receiving the message from more than one of the plurality of nodes, wherein the second node receiving the message from more than one of the plurality of nodes comprises the second node receiving the message from a third node, wherein the third node forwards the message to the second node in response to receiving the message from a fourth node; and

the second node initiating an operation to change the routing information stored on one or more of the plurality of nodes in response to receiving the message from more than one of the plurality of nodes, wherein changing the routing information stored on one or more of the plurality of nodes comprises changing the routing information stored on the third node to specify that messages addressed to the first address should be sent over a first link to the fourth node in response to determining that the third node received the message from the fourth node via the first link.

2. The method of claim 1,

wherein said changing the routing information stored on one or more of the nodes comprises changing the routing information stored on one or more of the nodes such that upon sending an additional message addressed to the first address from the first node, the second node does not receive the additional message from more than one of the plurality of nodes.

3. The method of claim 1,

wherein the second node receiving the message from more than one of the plurality of nodes comprises the second node receiving the message from the third node in response to the third node routing the message toward a first instance of the first address and receiving the message from a fifth node in response to the fifth node routing the message toward a second instance of the first address.

4. The method of claim 1,

wherein before the routing information stored on the third node is changed, the routing information stored on the third node specifies that messages addressed to the first address should be sent over a second link;

wherein said changing the routing information stored on the third node comprises changing the routing information stored on the third node such that after said changing, the routing information stored on the third node specifies that messages addressed to the first address should be sent over the first link and does not specify that messages addressed to the first address should be sent over the second link.

5. The method of claim 1,

wherein the second node is coupled by a second link to the third node and is coupled by a third link to a fifth node;

wherein before the routing information on the third node is changed, the routing information on the third node specifies that messages addressed to the first address should be sent over the second link to the second node;

wherein the routing information on the fifth node specifies that messages addressed to the first address should be sent over the third link to the second node;

wherein the second node receiving the message from more then one of the plurality of nodes comprises the second node receiving the message from the third node via the second link and receiving the message from the fifth node via the third link.

6. The method of claim 1,

wherein the fourth node forwards the message to the third node in response to receiving the message from a fifth node;

wherein said changing the routing information stored on one or more of the plurality of nodes further comprises changing the routing information stored on the fourth node to specify that messages addressed to the first address should be sent over a second link to the fifth node in response to determining that the fourth node received the message from the fifth node via the second link.

7. A computer-readable memory medium storing program instructions executable to implement a method comprising:

storing routing information on each of a plurality of nodes, wherein the routing information on each node specifies one or more links over which to send messages addressed to a first address, wherein two or more of the nodes each host an instance of the first address;

sending a message addressed to the first address from a first node of the plurality of nodes;

a second node of the plurality of nodes receiving the message from more than one of the plurality of nodes, wherein the second node receiving the message from more than one of the plurality of nodes comprises the second node receiving the message from a third node, wherein the third node forwards the message to the second node in response to receiving the message from a fourth node; and

the second node initiating an operation to change the routing information stored on one or more of the plurality of nodes in response to receiving the message from more than one of the plurality of nodes, wherein changing the routing information stored on one or more of the plurality of nodes comprises changing the routing information stored on the third node to specify that messages addressed to the first address should be sent over a first link to the fourth node in response to determining that the third node received the message from the fourth node via the first link.

8. The computer-readable memory medium of claim 7,

wherein said changing the routing information stored on one or more of the nodes comprises changing the routing information stored on one or more of the nodes such that upon sending an additional message addressed to the first address from the first node, the second node does not receive the additional message from more than one of the plurality of nodes.

9. The computer-readable memory medium of claim 7,

wherein the second node receiving the message from more than one of the plurality of nodes comprises the second node receiving the message from the third node in response to the third node routing the message toward a first instance of the first address and receiving the message from a fifth node in response to the fifth node routing the message toward a second instance of the first address.

10. The computer-readable memory medium of claim 7,

wherein before the routing information stored on the third node is changed the routing information stored on the third node specifies that messages addressed to the first address should be sent over a second link;

wherein said changing the routing information stored on the third node comprises changing the routing information stored on the third node such that after said changing, the routing information stored on the third node specifies that messages addressed to the first address should be sent over the first link and does not specify that messages addressed to the first address should be sent over the second link.

11. The computer-readable memory medium of claim 7,

wherein the second node is coupled by a second link to the third node and is coupled by a third link to a fifth node;

wherein before the routing information on the third node is changed, the routing information on the third node specifies that messages addressed to the first address should be sent over the second link to the second node;

wherein the routing information on the fifth node specifies that messages addressed to the first address should be sent over the third link to the second node;

wherein the second node receiving the message from more then one of the plurality of nodes comprises the second node receiving the message from the third node via the second link and receiving the message from the fifth node via the third link.

12. The computer-readable memory medium of claim 7,

wherein the fourth node forwards the message to the third node in response to receiving the message from a fifth node;

wherein said changing the routing information stored on one or more of the plurality of nodes further comprises changing the routing information stored on the fourth node to specify that messages addressed to the first address should be sent over a second link to the fifth node in response to determining that the fourth node received the message from the fifth node via the second link.

13. A system comprising:

a plurality of nodes;

wherein the nodes include memory that stores program instructions executable to implement;

storing routing information on each of the plurality of nodes, wherein the routing information on each node specifies one or more links over which to send messages addressed to a first address, wherein two or more of the nodes each host an instance of the first address;

sending a message addressed to the first address from a first node of the plurality of nodes;

a second node of the plurality of nodes receiving the message from more than one of the plurality of nodes, wherein the second node receiving the message from more than one of the plurality of nodes comprises the second node receiving the message from a third node, wherein the third node forwards the message to the second node in response to receiving the message from a fourth node; and

the second node initiating an operation to change the routing information stored on one or more of the plurality of nodes in response to receiving the message from more than one of the plurality of nodes, wherein changing the routing information stored on one or more of the plurality of nodes comprises changing the routing information stored on the third node to specify that messages addressed to the first address should be sent over a first link to the fourth node in response to determining that the third node received the message from the fourth node via the first link.

14. The system of claim 13,

wherein said changing the routing information stored on one or more of the nodes comprises changing the routing information stored on one or more of the nodes such that upon sending an additional message addressed to the first address from the first node, the second node does not receive the additional message from more than one of the plurality of nodes.

15. The system of claim 13,

wherein the second node receiving the message from more than one of the plurality of nodes comprises the second node receiving the message from the third node in response to the third node routing the message toward a first instance of the first address and receiving the message from a fifth node in response to the fifth node routing the message toward a second instance of the first address.

16. The system of claim 13,

wherein before the routing information stored on the third node is changed, the routing information stored on the third node specifies that messages addressed to the first address should be sent over a second link;

wherein said changing the routing information stored on the third node comprises changing the routing information stored on the third node such that after said changing, the routing information stored on the third node specifies that messages addressed to the first address should be sent over the first link and does not specify that messages addressed to the first address should be sent over the second link.

17. The system of claim 13,

wherein the fourth node is operable to forward the message to the third node in response to receiving the message from a fifth node;

wherein said changing the routing information stored on one or more of the plurality of nodes further comprises changing the routing information stored on the fourth node to specify that messages addressed to the first address should be sent over a second link to the fifth node in response to determining that the fourth node received the message from the fifth node via the second link.