Managing network traffic using hashing functions

• US 7,203,768 B2
• Filed: 12/22/2000
• Issued: 04/10/2007
• Est. Priority Date: 12/22/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Olsen, Gregory P.
• Primary Examiner(s): NGUYEN, THU HA T
• Application Number:
  US09/746,677
• Publication Number:
  US 20020129133A1
• Time in Patent Office: 2,300 Days
• Field of Search: 709/217, 709/223, 709/224, 709/238, 709/218, 709/220, 709245-246, 709/249, 370/253, 370/254, 370/238, 370/256, 370/310, 370/402, 370400-401, 370/392, 707/10
• US Class Current: 709/249
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18

Abstract

Network traffic that is used to communicate multicast and broadcast messages are separated into subgroups with respect to the multicast and broadcast messages. In one embodiment a hashing function is used to separate target devices into subgroups. For example, a device identifier can be used by a hash function to determine which subgroup the device belongs to. Messages can be sent to the different subgroups at different times to manage network traffic, or the devices can reply to messages based on their respective subgroupings to manage network traffic.

Claims

1. A method comprising:

broadcasting a discovery request to network devices;

estimating a number of network devices from responses received from the network devices;

dividing target devices into subsets of target devices, wherein a subset to which a particular device belongs is determined based on a subset index value corresponding to results of a hash function performed with an identifier of the device and a number of subsets to which the target devices are divided;

sending a second request;

limiting subsets of target devices responsive to the second request, in part based on the second request including the number of subsets to which the target devices are divided and the subset index value, wherein the subset index value indicates a specific subset of the number of subsets to which the second message is targeted; and

varying a timing with which the second request is communicated to the subsets of target devices to result in the second request being sent to the multiple subsets at varying times.

2. The method of claim 1 wherein determining the subset of target devices comprises:

broadcasting over a network;

receiving one or more responses to the network broadcast from target devices coupled to the network;

estimating a number of devices coupled to the network; and

determining a number of subgroups based, at least in part, on the estimated number of devices coupled to the network.

3. The method of claim 1 wherein determining the subset of target devices comprises:

multicasting to a subset of a network;

receiving one or more responses from target devices of the subnet;

estimating a number of devices in the subnet; and

determining a number of subgroups based, at least in part, on the estimated number of devices in the subnet.

4. A physical article comprising a tangible machine-accessible medium to provide machine-readable instructions that, when executed, cause one or more electronic system to:

broadcast a discovery request to network devices;

estimate a number of network devices from responses received from the network devices;

divide target devices into subsets of target devices, wherein a subset to which a particular device belongs is determined based on a subset index value corresponding to results of a hash function performed with an identifier of the device and a number of subsets to which the target devices are divided;

send a second request;

limit subsets of target devices responsive to the second request, in part based on the second request including the number of subsets to which the target devices are divided and the subset index value, wherein the subset index value indicates a specific subset of the number of subsets to which the second message is targeted; and

vary a timing with which the second request is communicated to the subsets of target devices to result in the second request being sent to the multiple subsets at varying times.

5. The physical article of claim 4 wherein the instructions that cause the one or more electronic systems to determine the subset of target devices further comprises sequences of instructions that, when executed, cause the one or more electronic systems to:

broadcast over a network;

receive one or more responses from target devices coupled to the network;

estimate a number of devices coupled to the network; and

determine a number of subgroups based, at least in part, on the estimated number of devices coupled to the network.

6. The physical article of claim 4 wherein the instructions that cause the one or more electronic systems to determine the subset of target devices further comprises sequences of instructions that, when executed, cause the one or more electronic systems to:

multicast to a subset of a network;

receive one or more responses from target devices of the subnet;

estimate a number of devices in the subnet; and

determine a number of subgroups based, at least in part, on the estimated number of devices in the subnet.

7. A method comprising:

broadcasting a discovery request to network devices;

estimating a number of network devices from responses received from the network devices;

dividing a set of target devices into multiple subsets of target devices, wherein the subset to which a particular device belongs is determined based on an identifier of the device;

sending a second request;

limiting subsets of target devices responsive to the second request, in part based on the second request including the number of subsets to which the target devices are divided and a subset index value, wherein the subset index value indicates a specific subset of the number of subsets to which the second message is targeted;

performing a hash function with a unique identifier and the number of subsets to generate a hash result; and

responding to the second message if the hash result equals the hash the subset index value.

8. The method of claim 7 wherein determining the subset of target devices comprises:

broadcasting over a network;

receiving one or more responses from target devices coupled to the network;

estimating a number of devices coupled to the network; and

determining a number of subgroups based, at least in part, on the estimated number of devices coupled to the network.

9. The method of claim 7 wherein determining the subset of target devices comprises:

multicasting to a subset of a network;

receiving one or more responses from target devices of the subnet;

estimating a number of devices in the subnet; and

determining a number of subgroups based, at least in part, on the estimated number of devices in the subnet.

10. A physical article comprising a tangible machine-accessible medium to provide machine-readable instructions that, when executed, cause one or more electronic system to:

broadcast a discovery request to network devices;

estimate a number of network devices from responses received from the network devices;

divide a set of target devices into multiple subsets of target devices, wherein the subset to which a particular device belongs is determined based on an identifier of the device;

send a second request;

limit subsets of target devices responsive to the second request, in part based on the second request including the number of subsets to which the target devices are divided and a subset index value, wherein the subset index value indicates a specific subset of the number of subsets to which the second message is targeted;

perform a hash function with a unique identifier and the number of subsets to generate a hash result; and

respond to the second message if the hash result equals the hash the subset index value.

11. The physical article of claim 10 wherein the instructions that cause the one or more electronic systems to determine the subset of target devices further comprises sequences of instructions that, when executed, cause the one or more electronic systems to:

broadcast over a network;

receive one or more responses from target devices coupled to the network;

estimate a number of devices coupled to the network; and

determine a number of subgroups based, at least in part, on the estimated number of devices coupled to the network.

12. The physical article of claim 10 wherein the instructions that cause the one or more electronic systems to determine the subset of target devices further comprises sequences of instructions that, when executed, cause the one or more electronic systems to:

multicast to a subset of a network;

receive one or more responses from target devices of the subnet;

estimate a number of devices in the subnet; and

determine a number of subgroups based, at least in part, on the estimated number of devices in the subnet.

13. A tangible machine-accessible medium having electronic data signals stored therein, the medium to be shared among a plurality of network devices, wherein the electronic data signals comprise sequences of instructions that, when executed, cause one or more electronic systems to:

broadcast a discovery request to network devices;

estimate a number of network devices from responses received from the network devices;

divide a set of target devices into multiple subsets of target devices, wherein the subset to which a particular device belongs is determined based on an identifier of the device;

send a second request;

limit subsets of target devices responsive to the second request, in part based on the second request including the number of subsets to which the target devices are divided and a subset index value, wherein the subset index value indicates a specific subset of the number of subsets to which the second message is targeted;

perform a hash function with a unique identifier and the number of subsets to generate a hash result; and

respond to the second message if the hash result equals the hash the subset index value.

14. The tangible machine-accessible medium of claim 13 wherein the sequences of instructions that cause the one or more electronic systems to determine the subset of target devices further comprises sequences of instructions that, when executed, cause the one or more electronic systems to:

broadcast over a network;

receive one or more responses from target devices coupled to the network;

estimate a number of devices coupled to the network; and

determine a number of subgroups based, at least in part, on the estimated number of devices coupled to the network.

15. The tangible machine-accessible medium of claim 13 wherein the sequences of instructions that cause the one or more electronic systems to determine the subset of target devices further comprises sequences of instructions that, when executed, cause the one or more electronic systems to:

multicast to a subset of a network;

receive one or more responses to from target devices of the subnet;

estimate a number of devices in the subnet; and

determine a number of subgroups based, at least in part, on the estimated number of devices in the subnet.