Identifying nodes in a ring network

• US 7,890,663 B2
• Filed: 07/29/2006
• Issued: 02/15/2011
• Est. Priority Date: 06/28/2001
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: Fortinet Inc.
• Inventors: Millet, Tim
• Primary Examiner(s): Lee; Philip C
• Application Number:
  US11/460,977
• Publication Number:
  US 20060265519A1
• Time in Patent Office: 1,662 Days
• Field of Search: 709/251, 370/222, 370/254, 370/258, 370/455, 710/107, 710/111
• 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

Methods are provided for determining a master node on a ring network. According to one embodiment, a first node on the ring network initiates circulation of an arbitration token by (i) determining an arbitration token timeout period has elapsed and (ii) transmitting the arbitration token to a neighboring node. Upon receipt of the arbitration token by a node, it determines its relative priority by comparing its ID to an ID field of the arbitration token, initialized by the first node. If the node is determined to be higher priority, then it overwrites the ID field and retransmits the arbitration token onto the ring network. If the node is determined to be lower priority, then the node retransmits the arbitration token without overwriting the ID field. If the node is determined to be of equal priority and the node is the first node, then it assumes the master node role.

Claims

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

when 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, wherein arbitration tokens are used to identify a token master of the plurality of nodes that is responsible for generating a packet transmission token onto the ring network and wherein the packet transmission token authorizes a transmitting node of the plurality of nodes that has most recently received the packet transmission token to transmit locally generated packets onto the ring network;

when 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; and

wherein the predetermined period of time is calculated by N*(D+L)*C, where N is a number of the plurality of nodes, D is a maximum packet delay, L is a ring latency input/output measure and C is a clock period.

2. The method of claim 1, further comprising the first node retransmitting the arbitration token onto the ring network without 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 the packet transmission token and transmitting the packet transmission token 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 discarding the arbitration token when the time-to-live field for the arbitration token is exceeded.

6. A node in a ring network, comprising:

a hardware ring controller to;

transmit an arbitration token on the ring network when a predetermined period of time has expired without receipt of the arbitration token, wherein arbitration tokens are used to identify a token master of a plurality of nodes in the ring network that is responsible for generating a packet transmission token onto the ring network and wherein the packet transmission token authorizes a transmitting node of the plurality of nodes that has most recently received the packet transmission token to transmit locally generated packets onto the ring network,

receive the arbitration token,

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, and

wherein the predetermined period of time is equal to N*(D+L)*C, where N is a number of the plurality of nodes, D is a maximum packet delay, L is a ring latency input/output measure and C is a clock period.

7. The node of claim 6, wherein the hardware 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 hardware ring controller is further configured to convert the arbitration token to the packet transmission token and transmit the packet transmission token 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 hardware ring controller is further configured to increment 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.

10. The node of claim 9, wherein the hardware ring controller is further configured to discard the arbitration token when the time-to-live field for the received arbitration token is exceeded.

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

defining at least two different types of tokens recognized by a plurality of nodes on the ring network, including an arbitration token and a packet transmission token, wherein the arbitration token is used to identify the token master of the plurality of nodes, which is responsible for generating the packet transmission token onto the ring network, and wherein the packet transmission token authorizes a transmitting node of the plurality of nodes that has most recently received the packet transmission token to transmit locally generated packets onto the ring network;

a first node of the plurality of nodes 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 first node detecting the arbitration token on the ring network and (ii) transmitting the new arbitration token to a neighboring node of the plurality of nodes;

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 an ID of the first node prior to transmission of the new arbitration token onto the ring network;

if the node is determined to be 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;

if the node is determined to be of equal priority and the node is the first node, then the first node assuming a token master role and transmitting the packet transmission token onto the ring network, 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 token master; and

wherein the arbitration token timeout period is equal to N*(D+L)*C, where N is a number of the plurality of nodes, D is a maximum packet delay, L is a ring latency input/output measure and C is a clock period.