Method and apparatus for electing a leader node in a computer network

• US 7,421,578 B1
• Filed: 07/22/2003
• Issued: 09/02/2008
• Est. Priority Date: 07/22/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Weis, Brian, Huang, Geoffrey
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): LEMMA, SAMSON B
• Application Number:
  US10/625,445
• Time in Patent Office: 1,869 Days
• Field of Search: 713/163
• US Class Current: 713/163
• CPC Class Codes: H04L 63/065 for group communications cryptographic mechanisms or cryptographic arrangements for key management involving conference or group key H04L9/0833
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity

Abstract

A method performed by a first computer node for selecting a leader node to provide service to a plurality of other nodes in a multicast group, wherein each of the nodes communicates using multicast messages, comprises issuing a first election call message; receiving candidacy announcement messages from one or more leader candidate nodes in a specified time period; selecting a victor from among all leader candidate nodes from which candidacy announcement messages are received; receiving one or more victor announcement messages from one or more leader victor nodes for a second specified time period; resolving zero or more collisions among the victor announcement messages to result in selecting the leader node. One embodiment provides a dynamic secure protocol for electing a key server, such as a key server that is suited for use with a group key exchange protocol such as the Group Domain of Interpretation (GDOI). Public key signatures may be used to secure message exchanges and to provide for authentication of network nodes in a multicast group.

Claims

1. A method performed by a first computer node for selecting a leader node to provide service to a plurality of other nodes in a multicast group, wherein each of the nodes communicates using multicast, broadcast or anycast messages, the method comprising the computer-implemented steps of:

issuing a first election call message;

receiving candidacy announcement messages from one or more leader candidate nodes in a specified time period;

selecting a victor from among all leader candidate nodes from which candidacy announcement messages are received;

receiving one or more victor announcement messages from one or more leader victor nodes for a second specified time period;

resolving zero or more collisions among the victor announcement messages to result in selecting the leader node;

receiving, in the first election call message, first identity information specifying a second node that sent the first election call message;

pushing the identity information onto a stack;

receiving a second election call message that includes second identity information specifying a third node that sent the second election call message; and

ignoring the second election call message when the second identity information is found in the stack.

2. A method as recited in claim 1, wherein the leader node is a key server that provides keys for use in encrypting multicast group messages.

3. A method as recited in claim 1, wherein the leader node is a GDOI key server that provides keys to nodes according to Group Domain of Interpretation.

4. A method as recited in claim 1, further comprising:

performing a coin toss operation that results in either a first result or a second result; and

sending a candidacy announcement message in response to the first result occurring, or awaiting the candidacy announcement messages from the one or more leader candidate nodes in response to the second result occurring.

5. A method as recited in claim 1, wherein the step of selecting a victor further comprises the steps of:

determining whether the first computer node is the winner; and

sending a victor announcement message in response to determining that the first computer node is the winner.

6. A method as recited in claim 1, further comprising the step of ignoring any election call messages while awaiting receipt of the one or more candidacy announcement messages.

7. A method ad recited in claim 1, wherein selecting a victor comprises selecting one of the leader candidate nodes having a highest network address.

8. A method as recited in claim 1, wherein resolving any collisions comprises:

determining that two or more announcement messages have been received; and

issuing a second election call message.

9. A method as recited in claim 1, wherein the election call message, candidacy announcement messages, and victor announcement messages are multicast, broadcast or anycast messages.

10. A method as recited in claim 1, wherein each of the messages comprises a packet type value, sender sequence number value, sender identity value, and a digital signature of a node that sent the message.

11. A method as recited in claim 1, further comprising digitally signing each of the messages.

12. A method as recited in claim 1, further comprising the steps of:

creating a sequence number for each message that is sent;

digitally signing each message before sending the message; and

incrementing the sequence number.

13. A method as recited in claim 1, wherein the step of issuing the first election call message is performed only after failing to receive a reply to a key server discovery message that is sent by the first node upon newly joining a multicast group.

14. A method as recited in claim 1, wherein the first node is a member of an ad hoc multicast group.

23. A method as recited in claim 1, further comprising the steps of:

creating a sequence number for each message that is sent;

digitally signing each message before sending the message; and

incrementing the sequence number.

24. A method as recited in claim 1, wherein the first node is a member of an ad hoc multicast group.

15. A method performed by a first computer node for selecting a Group Domain of Interpretation (GDOI) key server to provide key service to a plurality of client nodes in a multicast group, the method comprising the computer-implemented steps of:

issuing a first election call message;

receiving candidacy announcement messages from one or more leader candidates in a specified time period;

selecting a winner from among all leader candidates from which candidacy announcement messages are received;

receiving one or more victor announcement messages from one or more leader victor nodes for a second specified time period;

resolving zero or more collisions among the victor announcement messages to result in selecting the leader node;

receiving, in the first election call message, first identity information, specifying a second node that sent the first election call message;

pushing the identity information onto a stack;

receiving a second election call message that includes second identity information specifying a third node that sent the second election call message; and

ignoring the second election call message when the second identity information is found in the stack;

wherein the election call message, candidacy announcement messages, and victor announcement messages are multicast, broadcast or anycast messages.

16. A method as recited in claim 15, wherein the step of issuing the first election call message is performed only after failing to receive a reply to a key server discovery message that is sent by the first node upon newly joining a multicast group.

17. A method as recited in claim 15, further comprising:

performing a coin toss operation that results in either a first result or a second result; and

sending a candidacy announcement message in response to the first results occurring, or awaiting the candidacy announcement messages from the one or more leader candidates in response to the second result occurring.

18. A method as recited in claim 15, wherein the step of selecting a winner further comprises the steps of:

determining whether the first computer node is the winner; and

sending a victor announcement message in response to determining that the first computer node is the winner.

19. A method as recited in claim 15, further comprising the step of ignoring any election call messages while awaiting receipt of the one or more candidacy announcement messages.

20. A method as recited in claim 15, wherein selecting a winner comprises selecting one of the leader candidates having a highest network address.

21. A method as recited in claim 15, wherein resolving any collisions comprises:

determining that two or more announcement messages have been received; and

issuing a second election call message.

22. A method as recited in claim 15, wherein each of the messages comprises a packet type value, sender sequence number value, sender identity value, and a digital signature of a node that sent the message.

25. A computer-readable storage device or disk medium carrying one or more sequences of instructions for a first computer node for selecting a leader node to provide service to a plurality of other nodes in a multicast group, wherein each of the nodes communicates using multicast, broadcast or anycast messages, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

issuing a first election call message;

receiving candidacy announcement messages from one or more leader candidate nodes in a specified time period;

selecting a victor from among all leader candidate nodes from which candidacy announcement messages are received;

receiving one or more victor announcement messages from one or more leader victor nodes for a second specified time period;

resolving zero or more collisions among the victor announcement messages to result in selecting the leader node;

receiving, in the first election call message, first identity information specifying a second node that sent the first election call message;

pushing the identity information onto a stack;

receiving a second election call message that includes second identity information specifying a third node that sent the second election call message; and

ignoring the second election call message when the second identity information is found in the stack.

26. A computer-readable storage device or disk medium as recited in claim 25, wherein the leader node is a key server that provides keys for use in encrypting multicast group messages.

27. A computer-readable storage device or disk medium as recited in claim 25, wherein the leader node is a GDOI key server that provides keys to nodes according to Group Domain of Interpretation.

28. A computer-readable storage device or disk medium as recited in claim 25, further comprising instructions for:

performing a coin toss operation that results in either a first result or a second result; and

sending a candidacy announcement message in response to the first results occurring, or awaiting the candidacy announcement messages from the one or more leader candidate nodes in response to the second result occurring.

29. A computer-readable storage device or disk medium as recited in claim 25, wherein the instructions for the step of selecting a victor further comprise instructions for the steps of:

determining whether the first computer node is the winner; and

sending a victor announcement message in response to determining that the first computer node is the winner.

30. A computer-readable storage device or disk medium as recited in claim 25, further comprising instructions for the step of ignoring any election call messages while awaiting receipt of the one or more candidacy announcement messages.

31. A computer-readable storage device or disk medium as recited in claim 25, wherein selecting a victor comprises selecting one of the leader candidate nodes having a highest network address.

32. A computer-readable storage device or disk medium as recited in claim 25, wherein resolving any collisions comprises:

determining that two or more announcement messages have been received; and

issuing a second election call message.

33. A computer-readable storage device or disk medium as recited in claim 25, wherein the election call message, candidacy announcement messages, and victor announcement messages are multicast, broadcast or anycast messages.

34. A computer-readable storage device or disk medium as recited in claim 25, wherein each of the messages comprise a packet type value, sender sequence number value, sender identity value, and a digital signature of a node that sent the message.

35. A computer-readable storage device or disk medium as recited in claim 25, further comprising digitally signing each of the messages.

36. A computer-readable storage device or disk medium as recited in claim 25, further comprising instructions for the steps of:

creating a sequence number for each message that is sent;

digitally signing each message before sending the message; and

incrementing the sequence number.

37. A computer-readable storage device or disk medium as recited in claim 25, wherein the step of issuing the first election call message is performed only after failing to receive a reply to a key server discovery message that is sent by the first node upon newly joining a multicast group.

38. A computer-readable storage device or disk medium as recited in claim 25, wherein the first node is a member of an ad hoc multicast group.

39. An apparatus for a first computer node for selecting a leader node to provide service to a plurality of other nodes in a multicast group, wherein each of the nodes communicates using multicast, broadcast or anycast messages, comprising:

one or more processors;

means for issuing a first election call message;

means for receiving candidacy announcement messages from one or more leader candidate nodes in a specified time period;

means for selecting a victor from among all leader candidate nodes from which candidacy announcement messages are received;

means for receiving one or more victor announcement messages from one or more leader victor nodes for a second specified time period;

means for resolving zero or more collisions among the victor announcement messages to result in selecting the leader node;

means for receiving, in the first election call message, first identity information specifying a second node that sent the first election call message;

means for pushing the identity information onto a stack;

means for receiving a second election call message that includes second identity information specifying a third node that sent the second election call message; and

means for ignoring the second election call message when the second identity information is found in the stack.

40. An apparatus as recited in claim 39, wherein the leader node is a key server that provides keys for use in encrypting multicast group messages.

41. An apparatus as recited in claim 39, wherein the leader node is a GDOI key server that provides keys to nodes according to Group Domain of Interpretation.

42. An apparatus as recited in claim 39, further comprising:

means for performing a coin toss operation that results in either a first result or a second result; and

means for sending a candidacy announcement message in response to the first result occurring, or awaiting the candidacy announcement messages from the one or more leader candidate nodes in response to the second result occurring.

43. An apparatus as recited in claim 39, wherein the means for selecting a victor further comprises:

means for determining whether the first computer node is the winner; and

means for sending a victor announcement message in response to determining that the first computer node is the winner.

44. An apparatus as recited in claim 39, further comprising means for ignoring any election call messages wile awaiting receipt of the one or more candidacy announcement messages.

45. An apparatus as recited in claim 39, wherein the means for selecting a victor comprises means for selecting one of the leader candidate nodes having a highest network address.

46. An apparatus as recited in claim 39, wherein he means for resolving any collisions comprises:

means for determining that two or more announcement messages have been received; and

means for issuing a second election call message.

47. An apparatus as recited in claim 39, wherein the election call message, candidacy announcement messages, and victor announcement messages are multicast, broadcast or anycast messages.

48. An apparatus as recited in claim 39, wherein each of the messages comprises a packet type value, sender sequence number value, sender identity value, and a digital signature of a node that sent the message.

49. An apparatus as recited in claim 39, further comprising means for digitally signing each of the messages.

50. An apparatus as recited in claim 39, further comprising:

means for creating a sequence number for each message that is sent;

means for digitally signing each message before sending the message; and

means for incrementing the sequence number.

51. An apparatus as recited in claim 39, further comprising means for issuing the first election call message only after failing to receive a reply to a key server discovery message that is sent by the first node upon newly joining a multicast group.

52. An apparatus as recited in claim 39, wherein the first node is a member of an ad hoc multicast group.

53. An apparatus for a first computer node for selecting a leader node to provide service to a plurality of other nodes in a multicast group, wherein each of the nodes communicates using multicast, broadcast or anycast messages, comprising:

a network interface that is coupled to the data network for receiving one or more packet flows therefrom;

a processor;

one or more stored sequences of instructions which, when executes by the processor, cause the processor to carry out the steps of;

issuing a first election call message;

receiving candidacy announcement messages from one or more leader candidate nodes in a specified time period;

selecting a victor from among all leader candidate nodes from which candidacy announcement messages are received;

receiving one or more victor announcement messages from one or more leader victor nodes for a second specified time period;

resolving zero or more collisions among the victor announcement messages to result in selecting the leader node;

receiving, in the first elections call message, first identity information specifying a second node that sent the first election call message;

pushing the identity information onto a stack;

receiving a second election call message that includes second identity information specifying a third node that sent the second election call message; and

ignoring the second election call message when the second identity information is found in the stack.

54. An apparatus as recited in claim 53, wherein the leader node is a key server that provides keys for use in encrypting multicast group messages.

55. An apparatus as recited in claim 53, wherein the leader node is a GDOI key server that provides keys to nodes according to Group Domain of Interpretation.

56. An apparatus as recited in claim 53, the sequences of instructions further comprising instructions for:

performing a coin toss operation that results in either a first result or a second result; and

sending a candidacy announcement message in response to the first result occurring, or awaiting the candidacy announcement messages from the one or more leader candidate nodes in response to the second result occurring.

57. An apparatus as recited in claim 53, wherein the step of selecting a victor further comprises the steps of:

determining whether the first computer node is the winner; and

sending a victor announcement message in response to determining that the first computer node is the winner.

58. An apparatus as recited in claim 53, the sequences of instructions further comprising instructions for ignoring any election call messages while awaiting receipt of the one or more candidacy announcement messages.

59. An apparatus as recited in claim 53, wherein selecting a victor comprises selecting one of the leader candidate nodes having a highest network address.

60. An apparatus as recited in claim 53, wherein resolving any collisions comprises:

determining that two or more announcement messages have been received; and

issuing a second election call message.

61. An apparatus as recited in claim 53, wherein the election call message, candidacy announcement messages, and victor announcement messages are multicast, broadcast or anycast messages.

62. An apparatus as recited in claim 53, wherein each of the messages comprises a packet type value, sender sequence number value, sender identity value, and a digital signature of a node that sent the message.

63. An apparatus as recited in claim 53, the sequences of instructions further comprising instructions for digitally signing each of the messages.

64. An apparatus as recited in claim 53, the sequences of instructions further comprising instructions for the steps of:

creating a sequence number for each message that is sent;

digitally signing each message before sending the message; and

incrementing the sequence number.

65. An apparatus as recited in claim 53, wherein the sequences of instructions for issuing the first election call message are performed only after failing to receive a reply to a key server discovery message that is sent by the first node upon newly joining a multicast group.

66. An apparatus as recited in claim 53, wherein the first node is a member of an ad hoc multicast group.