Method and apparatus for operating a computer network

• US 7,610,333 B2
• Filed: 12/11/2003
• Issued: 10/27/2009
• Est. Priority Date: 12/31/2002
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Robertson, Derrick D, McKee, Paul F
• Primary Examiner(s): Anderson; Matthew D
• Assistant Examiner(s): YOUSSEF, ADEL Y
• Application Number:
  US10/539,413
• Publication Number:
  US 20060149836A1
• Time in Patent Office: 2,147 Days
• Field of Search: 709/202, 709/203
• US Class Current: 709/203
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/1824 implemented using Network-attached Storage [NAS] architecture distributed or networked storage systems G06F3/067; protocols for distributed storage of data in a network H04L67/1097
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers
• CPC Class Codes: H04L 67/107 with limitation or expansion of the discovery scope
• CPC Class Codes: H04L 67/1089 Hierarchical topologies
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

Messages are generated by a first device which messages together have the purpose of identifying a predetermined number of devices which satisfy a test condition included in each message. These messages are sent respectively to on-line devices neighboring the first device. To ensure that no more devices than necessary are identified by the messages, each message includes a variable which is referred to as a token bucket which indicates the number of devices to be discovered by the message. Additionally, each message includes a unique identifier. When one device receives a discovery message sent from another device, it determines if it satisfies the test condition and if so it sends an acceptance message to the originating device, decrements the token bucket in the message and forwards on any remaining tokens to another neighbor. The process stops once all tokens have been disposed of in this way. If a message reaches the end of a path without disposing of all of the tokens, the message is returned back up the path to try different paths until eventually all paths have been tried or a restriction criterion e.g., maximum permitted number of hops) is met whereupon the message is returned back as a failed message to the originating device.

Claims

1. A method of identifying a predetermined number of computers within a computer network which satisfy one or more specified conditions, the method comprising:

communicating a request from an originating computer to one or more of the computers in the network a request message which includes said one or more specified conditions and a token value which is indicative of a number of computer devices to be located by the message;

receiving said request message at subsequent computers and at each subsequent computer which receives a request message processing the message, performing the following;

determining if it is able to satisfy the one or more conditions specified in the request message and if so, decrementing the token value within the received request message and identifying itself to the request originating computer, and then

determining if the, possibly decremented, token value in the received request message indicates that at least one further computer device is required to be located and if so, forwarding one or more daughter messages on to a subsequent computer or computers within the computer network unless a restriction criterion has been met,

wherein each daughter message includes said one or more specified conditions and a token value such that the token value if only one daughter message is forwarded, or the sum of the token values of the daughter messages if more than one daughter message is forwarded, equals the, possibly decremented, token value of the received request message.

2. A method as claimed in claim 1 wherein each message includes a number of further hops permissible as a restriction criterion and each time the message is newly received by a device it decrements the number of further hops permissible until it reaches zero whereupon the restriction criterion is deemed to have been met.

3. A method as claimed in claim 1, wherein each computer maintains a register of neighboring devices for the purpose of communicating request messages thereto together with a probability associated with each registered neighboring device and wherein these probabilities are used to determine to which neighboring device or devices a request message or messages is or are to be sent.

4. A method as claimed in claim 3 wherein a computer from time to time requests certain of its neighbors to re-register with other computers in dependence upon the probabilities associated with its registered neighboring computers.

5. A method of storing a data file in a computer network, the method comprising:

identifying a predetermined number of computers within a computer network using the method according to claim 1

generating a first plurality, corresponding to the identified predetermined number of computers, of erasure coded fragments from the data file such that any subset of the fragments which contains at least a smaller predetermined number of the first plurality of fragments can be used to recreate the data file; and

transmitting each of the erasure coded fragments to a respective one of the identified computers for storage thereon;

wherein at least one of the one or more specified conditions is that the computer has sufficient storage space available for storing one of said fragments.

6. A method as claimed in claim 5 wherein each fragment is encoded before transmission to a respective identified computer.

7. A method as claimed in claim 5 wherein each fragment is transmitted together with the public key of a public/private key combination belonging to a user attempting to store the data file.

8. A method as claimed in claim 5 wherein the data file is first transmitted from a remote client device to a gateway computer which is on the other side of a firewall between the remote client device and the gateway server, the computer network within which the computers are to be identified also being located on the other side of the firewall to the remote client device.

9. A computer network comprising a plurality of computers having data connections such that each computer within the network can communicate with any other computer within the network provided both computers are running and correctly connected into the network, each computer within the network comprising:

a request generator for generating request messages each of which includes a token value indicative of the number of other computers within the network to be identified by the message and one or more specified conditions which each identified computer is to satisfy; and

a request processor for processing received request messages by;

determining if it is able to satisfy the one or more conditions specified in the request message and if so, decrementing the token value within the message and identifying itself to the originator of the corresponding received request message, and then,

determining if the, possibly decremented, token value in the request message indicates that at least one further computer is required to be located by the message and if so, forwarding the one or more daughter messages on to a subsequent computer or computers within the computer network, unless a restriction criterion has been met,

wherein each daughter message includes said one or more specified conditions and a token value such that the token value if only one daughter message is forwarded, or the sum of the token values of the daughter messages if more than one daughter message is forwarded, equals the, possibly decremented, token value of the received request message.

10. A computer for forming part of a computer network comprising a plurality of computers having data connections such that each computer within the network can communicate with any other computer within the network provided both computers are running and correctly connected into the network, the computer comprising:

a request generator for generating request messages each of which includes a token value indicative of the number of other computers within the network to be identified by the message and one or more specified conditions which each identified computer is to satisfy; and

a request processor for processing received request messages by;

determining if it is able to satisfy the one or more conditions specified in the received request message and if so, decrementing the token value within the message and identifying itself to the originator of the received request message, and then,

determining if the, possibly decremented, token value in the received request message indicates that at least one further computer is required to be located by the message and if so, forwarding one or more daughter messages on to a subsequent computer or computers within the computer network, unless a restriction criterion has been

wherein each daughter message includes said one or more specified conditions and a token value such that the token value if only one daughter message is forwarded, or the sum of the token values of the daughter messages if more than one daughter message is forwarded, equals the, possibly decremented, token value of the received request message.