IDENTIFYING NODES IN A RING NETWORK

• US 20060265519A1
• Filed: 07/29/2006
• Published: 11/23/2006
• Est. Priority Date: 06/28/2001
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: Fortinet Inc.
• Inventors: Millet, Tim
• Granted Patent: US 7,890,663 B2
• Time in Patent Office: Days
• US Class Current: 709/251
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 12/433 with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 47/286 Time to live

Abstract

A master node in a packet ring network periodically sends packet containing a discovery marker into the packet ring network. As each node in turn receives the packet, each adds its own discovery marker, which contains its topology information, to the packer, saves the topology information of others, and resends the packet to the next node in the ring. Eventually, the master node receives the packer containing a chain of discovery markers for all active nodes terminated by the master'"'"'s own discovery marker, so the master node then removes its own discovery marker and resends the packer in to the ring network. Each node in turn then removes its own discovery marker. In this way, all nodes in the ring see topology information for every other active node.

Claims

1. A method of arbitrating among a plurality of nodes participating in a ring network, the method comprising:

if a first node of the plurality of nodes has not received an arbitration token during a predetermined period of time, then the first node originating and transmitting a new arbitration token onto the ring network; and

if the first node receives the arbitration token during the predetermined period of time, then when a node identifier associated with the arbitration token is at a lower priority than a node identifier associated with the first node, the first node modifying the arbitration token by replacing the node identifier associated with the arbitration token with the node identifier associated with the first node and retransmitting the modified arbitration token onto the ring network.

2. The method of claim 1, further comprising the first node retransmitting the arbitration token onto the ring network without the replacing the node identifier associated with the arbitration token when the node identifier associated with the arbitration token is at a higher priority than the node identifier associated with the first node.

3. The method of claim 1, further comprising the first node converting the arbitration token to a normal packet and transmitting the normal packet on the ring network when the node identifier associated with the arbitration token is at an equal priority to the node identifier associated with the first node.

4. The method of claim 2, further comprising the first node incrementing a time-to-live field in the arbitration token when the node identifier associated with the arbitration token is at the higher priority than the node identifier associated with the first node.

5. The method of claim 4, further comprising the first node converting the arbitration token to a normal packet and transmitting the normal packet on the ring network when the time-to-live field for the arbitration token is exceeded.

6. A node in a ring network, comprising:

a ring controller to;

transmit an arbitration token on the ring network when a period of time has expired without receipt of the arbitration token,

receive the arbitration token, and

when a node identifier associated with the arbitration token is at a lower priority than a node identifier associated with the first node, replace the node identifier associated with the arbitration token with the node identifier associated with the first node and transmit the arbitration token on the ring network.

7. The node of claim 6, wherein the ring controller is further configured to transmit the arbitration token on the ring network when the node identifier associated with the arbitration token is at a higher priority than the node identifier associated with the first node.

8. The node of claim 6, wherein the ring controller is further configured to convert the arbitration token to a normal packet and transmit the normal packet on the ring network when the node identifier associated with the arbitration token is at an equal priority to the node identifier associated with the first node.

9. The node of claim 7, wherein the ring controller is further configured to increment a time-to-live filed in the arbitration token when the node identifier associated with the arbitration token is at the higher priority than the node identifier associated with the first node.

10. The node of claim 9, wherein the ring controller is further configured to convert the arbitration token to a normal packet and transmit the normal packet on the ring network when the time-to-live field for the received arbitration token is exceeded.

11. A method of determining a master node on a ring network, the method comprising:

a first node of a plurality of nodes on the ring network initiating circulation of a new arbitration token among the plurality of nodes on the ring network by (i) generating the new arbitration token responsive to determining an arbitration token timeout period has elapsed without the first node detecting an arbitration token on the ring network and (ii) transmitting the new arbitration token to a neighboring node of the plurality of nodes on the ring network;

upon receipt of the new arbitration token by a node of the plurality of nodes, the node determining its relative priority to that of the first node by comparing a local ID of the node to an ID field of the arbitration token, which is initialized by the first node to the ID of the first node prior to transmission of the new arbitration token onto the ring network;

if the node is determined to the higher priority than the first node, then the node overwriting the ID field with the local ID and retransmitting the new arbitration token onto the ring network;

if the node is determined to be lower priority than the first node, then the node retransmitting the new arbitration token onto the ring network without overwriting the ID field; and

if the node is determined to be of equal priority and the node is the first node, then the first node assuming the master node role, whereby once the new arbitration token is passed all the way around the ring network and back to the first node unmodified by any higher priority nodes of the plurality of nodes, the first node becomes the master node.

12. A ring network node comprising:

a communication means for participating in a ring network having a plurality of nodes;

a token origination means for initiating circulation of a new arbitration token among the plurality of nodes by (i) generating the new arbitration token responsive to determining an arbitration token timeout period has elapsed without the ring network node detecting an arbitration token on the ring network and (ii) transmitting the new arbitration token to a neighboring node of the plurality of nodes;

a priority evaluation means for receiving an arbitration token and determining the ring network node'"'"'s relative priority to that of a node of the plurality of nodes currently identified by an ID field of the arbitration token; and

a means responsive to the priority evaluation means for (i) overwriting the ID field with a local ID of the ring network node if the ring network node is determined to be higher priority than the node currently identified by the ID field of the arbitration token, (ii) retransmitting the arbitration token onto the ring network without overwriting the ID field if the ring network node is determined to be lower priority than the node currently identified by the ID field of the arbitration token, and (iii) assuming a role of master ring network ring if the arbitration token has been passed all the way around the ring network and the ID field of the arbitration token identifies the ring network node.

13. A data structure stored on computer-readable media, the data structure comprising:

a packet-ring master field to indicate whether an originating blade is a current packet-ring master;

a control-blade master field to indicate whether the originating blade is a control-blade master;

a blade characteristics field to specify per-blade characteristics;

a connection state field to indicate a blade'"'"'s current connection state;

a blade identification field to specify the originating blade;

a marker field to indicate that the data structure is a blade discovery marker.

14. The data structure of claim 13, wherein the connection state field further indicates current connection state associated with a primary neighbor and a protect-ring neighbor of the originating blade.

15. A computer-readable medium having stored thereon instructions, which when executed by a processor of a first node of a ring network cause the first node to:

initiate circulation of a new arbitration token among a plurality of nodes on the ring network by (i) generating the new arbitration token responsive to determining an arbitration token timeout period has elapsed without the first node detecting an arbitration token on the ring network, (ii) setting an ID field of the arbitration token to a local ID of the first node, and (ii) transmitting the new arbitration token to a neighboring node of the plurality of nodes on the ring network;

upon receipt of an arbitration token, determine the first node'"'"'s relative priority to that of a node currently identified by an ID field of the arbitration token by comparing a local ID of the first node to the ID field of the arbitration token, which identifies the current highest priority node of the plurality of nodes through which the arbitration token has been circulated;

overwrite the ID field with the local ID and retransmit the arbitration token on the ring network if the first node is determined to be higher priority than the current highest priority node;

retransmit the arbitration token onto the ring network without overwriting the ID field if the first node is determined to be lower priority than the current highest priority node; and

assume a role as master node of the ring network, if the arbitration token has been passed all the way around the ring network and the current highest priority node is the first node.