Peer discovery

• US 20050117525A1
• Filed: 11/12/2004
• Published: 06/02/2005
• Est. Priority Date: 11/12/2003
• Status: Active Grant

• Current Assignee: Avaya Canada Corp. (Avaya Incorporated)
• Original Assignee: Avaya Canada Corp. (Avaya Incorporated)
• Inventors: Poustchi, Behrouz, Gagnon, Natalie Ann, Stelzig, James Andrew
• Granted Patent: US 7,577,150 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 61/5046 Resolving address allocation conflicts; Testing of addresses testing when self-assigning an address H04L61/5092
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04L 65/1069 Session establishment or de-establishment
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04M 7/0063 where the network is a peer-to-peer network

Abstract

Upon initial connection of a peer to a peer-to-peer network, the peer notifies other peers of its connection to the network. The peer receives existence notifications from other peers and may use them to create a list of the peers on the network, which may be sorted by the unique identifiers of each peer. A prospective network address is selected, e.g. based on the ordinal position of the peer within the sorted list. Conflict checking resolves conflicts between the prospective network address and the network address of other peers. Each peer may periodically notify the other peers of its network address, e.g. to prevent new peers from claiming the address. When a peer becomes inactive, another peer detecting this may begin periodically notifying the remaining peers that the address of the disconnected peer is already claimed. Peers may be Voice-over-IP telephone sets and network addresses may be directory numbers.

Claims

1. At one network device of a plurality of network devices, a method comprising:

sending an-existence notification;

receiving one or more existence notifications from one or more other network devices; and

based on the received existence notifications, selecting a prospective network address for said one network device.

2. The method of claim 1 wherein each existence notification includes a unique network device identifier.

3. The method of claim 2 wherein said unique network device identifier is a hardware address.

4. The method of claim 2 wherein said selecting is based on each said unique network device identifier.

5. The method of claim 4 wherein said selecting comprises:

sorting each said unique network device identifier of said other network devices along with a unique identifier of said one network device, said sorting resulting in a sorted list of said plurality of network devices;

determining an ordinal position of said one network device within the sorted list; and

from said ordinal position, creating said prospective network address.

6. The method of claim 5 wherein said creating a prospective network address comprises adding an offset associated with said ordinal position to a base address.

7. The method of claim 1 wherein said sending an existence notification comprises sending a network connection message.

8. The method of claim 7 wherein said sending a network connection message comprises sending two or more instances of said message at either of a fixed time interval or a random time interval.

9. The method of claim 1 wherein said sending comprises multicasting.

10. The method of claim 1 further comprising:

determining whether a conflict exists between said prospective network address and a network address claimed by any of said other network devices; and

if a conflict exists, resolving said conflict so that said prospective network address is claimed by only one of said plurality of network devices.

11. The method of claim 10 wherein said received existence notifications include an indication of network addresses claimed by said other network devices.

12. The method of claim 11 wherein said indication of network addresses claimed by said other network devices include an indication of network addresses claimed by network devices previously connected to said network but not currently connected to said network.

13. The method of claim 11 wherein said determining whether a conflict exists comprises establishing whether said network addresses claimed by said other network devices include said prospective network address.

14. The method of claim 13 wherein, if said establishing establishes that said network addresses of said other network devices include said prospective network address, said resolving comprises selecting a new prospective network address for said one network device and repeating said determining whether a conflict exists for said new prospective network address.

15. The method of claim 13 wherein said determining whether a conflict exists further comprises, if said establishing establishes that said network addresses of said other network devices do not include said prospective network address, notifying each of said other network devices of said prospective network address and awaiting receipt of any objections from any of said other network devices to the claiming by said one network device of said prospective network address.

16. The method of claim 15 further comprising, if said one network device fails to receive an objection from any of said other network devices to the claiming by said one network device of said prospective network address, claiming said prospective network address as the network address of said one network device.

17. The method of claim 15 wherein, if said one network device receives an objection from any of said other network devices to the claiming by said one network device of said prospective network address, said resolving comprises selecting a new prospective network address for said one network device and repeating said determining whether a conflict exists for said new prospective network address.

18. The method of claim 17 further comprising applying a network address conflict resolution scheme upon receiving said objection and wherein said selecting a new prospective address is conditional upon a determination by said network address resolution scheme that said one network device should not claim said network address.

19. The method of claim 18 wherein said network address conflict resolution scheme is a comparison of the unique identifier of said one network device and the unique identifier of another network device on behalf of which said objection was sent.

20. The method of claim 1 wherein said network address is a directory number.

21. The method of claim 20 wherein said directory number is a telephone extension and wherein said network device is a telephone set.

22. In a network including a first network device, a second network device, and at least one other network device, a method of maintaining a network address of the first network device, comprising:

at said second network device;

maintaining said network address of said first network device; and

upon determining that said first network device is inactive, notifying said at least one other network device that said network address of said first network device has been claimed.

23. The method of claim 22 wherein said notifying comprises periodically notifying.

24. The method of claim 23 wherein said periodic notifying comprises periodically multicasting a message.

25. The method of claim 22 wherein said at least one other network device includes a third device and further comprising:

at said third network device;

upon receiving said notification that said network address of said first network device has been claimed, comparing a network address of said first network device with a prospective network address for said third network device; and

if said comparing indicates a match between said network address of said first network device and said prospective network address for said third network device, selecting another prospective network address for said third network device.

26. The method of claim 22 wherein said notifying is conditional upon establishing that said second network device is the network device that should perform said notifying.

27. The method of claim 26 wherein said establishing identifies only one network device that should perform said notifying for said inactive first network device.

28. The method of claim 27 wherein said establishing comprises sorting a plurality of network devices that either currently have a presence on said network or previously had a presence on said network by their unique identifiers so as to create a sorted list of network devices and ascertaining that said inactive first network device follows said second network device within the sorted list with no active network device interceding in the list between said first and second network devices.

29. The method of claim 28 wherein said establishing alternatively comprises ascertaining that said inactive first network device precedes the first active network device within said sorted list and said second network device is the last active network device within said sorted list.

30. The method of claim 22 wherein, upon receipt of an indication at said second network device that a further network device is desirous of claiming said network address, communicating an objection to said claiming to said further network device.

31. A method for use at a network device comprising maintaining a state machine including a first state and a second state, said first state indicating that said network device has selected a prospective network address, said second state indicating that said network device has claimed said prospective network address as its network address.

32. A network device for use with one or more other network devices, said network device and said other network devices cumulatively forming a plurality of network devices, said network device adapted to:

send an existence notification;

receive one or more existence notifications from said other network devices; and

based on the received existence notifications, select a prospective network address for said network device.

33. The network device of claim 32 wherein each existence notification includes a unique network device identifier.

34. The network device of claim 33 wherein said unique network device identifier is a hardware address.

35. The network device of claim 33 wherein said selecting is based on each said unique network device identifier.

36. The network device of claim 35 wherein said selecting comprises:

sorting each said unique network device identifier of said other network devices along with a unique identifier of said network device, said sorting resulting in a sorted list of said plurality of network devices;

determining an ordinal position of said network device within the sorted list; and

from said ordinal position, creating said prospective network address.

37. The network device of claim 36 wherein said creating a prospective network address comprises adding an offset associated with said ordinal position to a base address.

38. The network device of claim 32 wherein said sending an existence notification comprises sending a network connection message.

39. The network device of claim 38 wherein said sending a network connection message comprises sending two or more instances of said message at either of a fixed time interval or a random time interval.

40. The network device of claim 32 wherein said sending comprises multicasting.

41. The network device of claim 32 further adapted to:

determine whether a conflict exists between said prospective network address and a network address claimed by any of said other network devices; and

if a conflict exists, resolve said conflict so that said prospective network address is claimed by only one of said plurality of network devices.

42. The network device of claim 41 wherein said received existence notifications include an indication of network addresses claimed by said other network devices.

43. The network device of claim 42 wherein said indication of network addresses claimed by said other network devices include an indication of network addresses claimed by network devices previously connected to said network but not currently connected to said network.

44. The network device of claim 42 wherein said determining whether a conflict exists comprises establishing whether said network addresses claimed by said other network devices include said prospective network address.

45. The network device of claim 44 wherein, if said establishing establishes that said network addresses of said other network devices include said prospective network address, said resolving comprises selecting a new prospective network address for said network device and repeating said determining whether a conflict exists for said new prospective network address.

46. The network device of claim 44 wherein said determining whether a conflict exists further comprises, if said establishing establishes that said network addresses of said other network devices do not include said prospective network address, notifying each of said other network devices of said prospective network address and awaiting receipt of any objections from any of said other network devices to the claiming by said network device of said prospective network address.

47. The network device of claim 46 further adapted to, if said network device fails to receive an objection from any of said other network devices to the claiming by said network device of said prospective network address, claim said prospective network address as the network address of said network device.

48. The network device of claim 46 wherein, if said network device receives an objection from any of said other network devices to the claiming by said network device of said prospective network address, said resolving comprises selecting a new prospective network address for said network device and repeating said determining whether a conflict exists for said new prospective network address.

49. The network device of claim 48 further adapted to apply a network address conflict resolution scheme upon receiving said objection and wherein said selecting a new prospective address is conditional upon a determination by said network address resolution scheme that said network device should not claim said network address.

50. The network device of claim 49 wherein said network address conflict resolution scheme is a comparison of the unique identifier of said network device and the unique identifier of another network device on behalf of which said objection was sent.

51. The network device of claim 32 wherein said network address is a directory number.

52. The network device of claim 51 wherein said directory number is a telephone extension and wherein said network device is a telephone set.

53. A network device for connection to a network including an inactive network device and at least one other network device, adapted to:

maintain said network address of said inactive network device; and

upon determining that said inactive network device is inactive, notify said at least one other network device that said network address of said inactive network device has been claimed.

54. A network device adapted to maintain a state machine including a first state and a second state, said first state indicating that said network device has selected a prospective network address, said second state indicating that said network device has claimed said prospective network address as its network address.

55. The network device of claim 54 further adapted to, while in said first state, notify other network devices of said prospective network address.

56. The network device of claim 55 further adapted to, while in said first state, select another prospective network address upon receipt of an objection to the claim by said network device of said network address from any of said other network devices.

57. The network device of claim 55 further adapted to transition from said first state to said second state upon expiry of a delay period without receipt of an objection to the claim by said network device of said network address from any of said other network devices and wherein, upon said transition, said network device claims said prospective network address as its network address.

58. The network device of claim 57 further adapted to, while in said second state, periodically notify other network devices of its claim to said network address.

59. The network device of claim 58 further adapted to transition from said second state to said first state if, while in said second state, said network device receives an objection to the claim by said network device of said network address from any of said other network devices.

60. The network device of claim 59 wherein said objection to the claim by said network device of said network address comprises an indication that another network device has claimed said network address.

61. The network device of claim 60 further adapted to apply a network address conflict resolution scheme upon receiving said objection to the claim by said network device of said network address and wherein said transition from said second state to said first state is conditional upon a determination by said network address resolution scheme that said network device should not claim said network address.

62. The network device of claim 61 wherein said network address conflict resolution scheme is a comparison of a unique identifier of said network device and a unique identifier of another network device which has already claimed said network address.

63. The network device of claim 62 wherein said unique identifier is a hardware address and wherein said determination that said network device should not claim said network address occurs if the hardware address of said network device is higher than the hardware address of said another network device.

64. The network device of claim 54 wherein said state machine further includes a third, initial state indicating that said network device is connecting to a network.

65. The network device of claim 64 further adapted to, while in said initial state, provide N connection notifications to other network devices of its presence on said network, where N is an integer greater than or equal to one, and receive existence notifications from said other network devices.

66. The network device of claim 65 further adapted to transition from said initial state to said first state upon the elapsing of a time interval.

67. The network device of claim 64 further adapted to transition from said initial state to said first state upon retrieval of a stored, previously claimed network address.

68. A machine-readable medium including machine-executable code for execution at one network device of a plurality of network devices, comprising:

machine-executable code for sending an existence notification;

machine-executable code for receiving one or more existence notifications from one or more other network devices; and

machine-executable code for selecting a prospective network address for said one network device based on the received existence notifications.

69. The machine-readable medium of claim 68 wherein each existence notification includes a unique network device identifier.

70. The machine-readable medium of claim 69 wherein said unique network device identifier is a hardware address.

71. The machine-readable medium of claim 69 wherein said selecting is based on each said unique network device identifier.

72. The machine-readable medium of claim 71 wherein said selecting comprises:

sorting each said unique network device identifier of said other network devices along with a unique identifier of said one network device, said sorting resulting in a sorted list of said plurality of network devices;

determining an ordinal position of said one network device within the sorted list; and

from said ordinal position, creating said prospective network address.

73. The machine-readable medium of claim 72 wherein said creating a prospective network address comprises adding an offset associated with said ordinal position to a base address.

74. The machine-readable medium of claim 68 wherein said sending an existence notification comprises sending a network connection message.

75. The machine-readable medium of claim 74 wherein said sending a network connection message comprises sending two or more instances of said message at either of a fixed time interval or a random time interval.

76. The machine-readable medium of claim 68 wherein said sending comprises multicasting.

77. The machine-readable medium of claim 68 further comprising:

machine-executable code for determining whether a conflict exists between said prospective network address and a network address claimed by any of said other network devices; and

machine-executable code for, if a conflict exists, resolving said conflict so that said prospective network address is claimed by only one of said plurality of network devices.

78. The machine-readable medium of claim 77 wherein said received existence notifications include an indication of network addresses claimed by said other network devices.

79. The machine-readable medium of claim 78 wherein said indication of network addresses claimed by said other network devices include an indication of network addresses claimed by network devices previously connected to said network but not currently connected to said network.

80. The machine-readable medium of claim 78 wherein said determining whether a conflict exists comprises establishing whether said network addresses claimed by said other network devices include said prospective network address.

81. The machine-readable medium of claim 80 wherein, if said establishing establishes that said network addresses of said other network devices include said prospective network address, said resolving comprises selecting a new prospective network address for said one network device and repeating said determining whether a conflict exists for said new prospective network address.

82. The machine-readable medium of claim 80 wherein said determining whether a conflict exists further comprises, if said establishing establishes that said network addresses of said other network devices do not include said prospective network address, notifying each of said other network devices of said prospective network address and awaiting receipt of any objections from any of said other network devices to the claiming by said one network device of said prospective network address.

83. The machine-readable medium of claim 82 further comprising machine-executable code for, if said one network device fails to receive an objection from any of said other network devices to the claiming by said one network device of said prospective network address, claiming said prospective network address as the network address of said one network device.

84. The machine-readable medium of claim 82 wherein, if said one network device receives an objection from any of said other network devices to the claiming by said one network device of said prospective network address, said resolving comprises selecting a new prospective network address for said one network device and repeating said determining whether a conflict exists for said new prospective network address.

85. The machine-readable medium of claim 84 further comprising machine-executable code for applying a network address conflict resolution scheme upon receiving said objection and wherein said selecting a new prospective address is conditional upon a determination by said network address resolution scheme that said one network device should not claim said network address.

86. The machine-readable medium of claim 85 wherein said network address conflict resolution scheme is a comparison of the unique identifier of said one network device and the unique identifier of another network device on behalf of which said objection was sent.

87. The machine-readable medium of claim 68 wherein said network address is a directory number.

88. The machine-readable medium of claim 87 wherein said directory number is a telephone extension and wherein said network device is a telephone set.

89. A machine-readable medium including machine-executable code for execution at a network device in a network including an inactive network device and at least one other network device, comprising:

machine-executable code for maintaining said network address of said inactive network device; and

machine-executable code for, upon determining that said inactive network device is inactive, notifying said at least one other network device that said network address of said inactive network device has been claimed.

90. A machine-readable medium storing machine-executable code which, when executed by a network device, causes said network device to maintain a state machine including a first state and a second state, said first state indicating that said network device has selected a prospective network address, said second state indicating that said network device has claimed said prospective network address as its network address.