Techniques for selecting available subnets for delegation among dynamic host configuration servers

• US 7,302,484 B1
• Filed: 08/13/2002
• Issued: 11/27/2007
• Est. Priority Date: 10/24/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kinnear, Kenneth Jr., Stapp, Mark
• Primary Examiner(s): Vaughn; William
• Assistant Examiner(s): SHAW, PELING ANDY
• Application Number:
  US10/218,555
• Time in Patent Office: 1,932 Days
• Field of Search: 709220-222, 709/223, 709/226, 709/245, 714/702, 345/543
• US Class Current: 709/226
• CPC Class Codes: H04L 61/5053 Lease time; Renewal aspects
• CPC Class Codes: H04L 61/5061 Pools of addresses

Abstract

A method and apparatus for providing network addresses for hosts on a network includes generating and storing network configuration information in a subnet management process, where a subnet is a set of contiguous network addresses. The network configuration information indicates network addresses to be distributed among a plurality of network devices. Policy information is also generated and stored. The policy information indicates a policy set of one or more policy processes. Each policy process selects an available subnet from available network addresses. A request for a subnet is received from a subnet requesting process. A particular subnet is determined based on the network configuration information, the request, and the policy set. A response indicating the particular subnet is sent to the subnet requesting process. These techniques allow an administrator to choose a policy for selecting subnets that better utilizes network resources for a wide range of network architectures.

Claims

1. A method of providing network addresses for hosts on a network, the method comprising the computer-implemented steps of:

generating and storing, as part of a subnet management process, network configuration information indicating a plurality of network addresses to be distributed among a plurality of network devices, wherein a subnet is a set of contiguous network addresses;

generating and storing policy information indicating a policy set of one or more policy processes, each policy process for selecting an available subnet from a plurality of available network addresses of the plurality of network addresses;

wherein each policy process manages a plurality of available network addresses of the plurality of network addresses;

receiving, from a subnet requesting process, a request for a subnet to be used by a particular network device;

invoking a particular policy process to determine a particular subnet based on the network configuration information, the request, and the policy set, wherein the particular policy process manages a particular plurality of available network addresses of the plurality of network addresses and determines the particular subnet by performing;

determining, based on the request, the particular network device to use the particular subnet;

determining whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

selecting from the particular plurality of available network addresses a candidate subnet as the particular subnet, wherein selection of the candidate subnet depends on whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

sending a response indicating the particular subnet to the subnet requesting process.

2. A method as recited in claim 1, wherein the subnet requesting process is another subnet management process.

3. A method as recited in claim 1, wherein the subnet requesting process is a routing process on a router connected to a local network.

4. A method as recited in claim 1, wherein:

said step of determining a particular subnet includes the step of determining a particular size for the particular subnet based on the request; and

the particular policy process of the policy set includes the steps of;

managing a set of available subnets of the particular plurality of available network addresses of the plurality of network addresses; and

matching the particular size to a size of a candidate subnet of the set of available subnets; and

selecting the candidate subnet as the particular subnet.

5. A method as recited in claim 4, said step of managing the set of available subnets further comprising the steps of:

adding a released subnet to the set of available subnets when the released subnet is made available in the particular policy process;

determining whether the released subnet is adjacent to a second subnet of the set of available subnets; and

if it is determined that the released subnet is adjacent, then replacing the released subnet and the second subnet in the set of available subnets with a combined subnet spanning the released subnet and the second subnet.

6. A method as recited in claim 4, said step of matching the particular size to the size of the candidate subnet further comprising the steps of:

determining whether no subnet of the available subnets has the particular size; and

if it is determined that no subnet of the available subnets has the particular size, then

determining a second subnet of the available subnets, which second subnet is bigger than the particular size; and

splitting the second subnet into the candidate subnet having the particular size and a third subnet.

7. A method as recited in claim 6, wherein the second subnet is a smallest subnet of the available subnets bigger than the particular size.

8. A method as recited in claim 6, wherein the second subnet is a first sequentially encountered subnet of the available subnets bigger than the particular size.

9. A method as recited in claim 1, wherein

the particular policy process of the policy set includes the step of, if it is determined that the particular leased subnet is allocated to the particular device, then selecting from the available network addresses a candidate subnet adjacent to the particular leased subnet.

10. A method as recited in claim 9, wherein the particular policy process includes the step of, if it is determined that no leased subnet of the set of leased subnets is allocated to the particular device, then selecting from the available network addresses a candidate subnet not adjacent to any leased subnet of the set of leased subnets.

11. A method as recited in claim 1, wherein said step of generating and storing policy information further comprises storing instructions to implement a particular policy process.

12. A method as recited in claim 1, wherein:

said step of generating and storing policy information further comprises registering a separate policy process into the policy set; and

said step of determining the particular subnet comprises;

sending a message to the separate policy process; and

receiving guidance information affecting a choice of the particular subnet.

13. A method as recited in claim 12, wherein the separate policy process reports subnet usage information to an outside application.

14. A method as recited in claim 12, wherein:

the message includes the particular subnet selected by a second policy process of the policy set; and

the guidance information includes data indicating acceptance of the particular subnet by the separate policy process.

15. A method as recited in claim 12, wherein:

the message includes a second subnet selected by a second policy process of the policy set; and

the guidance information includes data indicating rejection of the second subnet by the separate policy process.

16. A method as recited in claim 12, wherein:

the guidance information includes data indicating a particular policy process of the policy set; and

the method further comprises determining the subnet based on the particular policy process in response to the guidance information.

17. A method as recited in claim 12, wherein the guidance information includes data indicating the particular subnet.

18. A method as recited in claim 1, wherein the policy set includes two or more policy processes.

19. A method as recited in claim 18, wherein the policy information indicates a particular policy process of the policy set to invoke first.

20. A computer-readable storage medium carrying one or more sequences of instructions for providing network addresses for hosts on a network, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

generating and storing, as part of a subnet management process, network configuration information indicating a plurality of network addresses to be distributed among a plurality of network devices, wherein a subnet is a set of contiguous network addresses;

generating and storing policy information indicating a policy set of one or more policy processes, each policy process for selecting an available subnet from a plurality of available network addresses of the plurality of network addresses;

wherein each policy process manages a plurality of available network addresses of the plurality of network addresses;

receiving, from a subnet requesting process, a request for a subnet to be used by a particular network device;

invoking a particular policy process to determine a particular subnet based on the network configuration information, the request, and the policy set, wherein the particular policy process manages a particular plurality of available network addresses of the plurality of network addresses and determines the particular subnet by performing;

determining, based on the request, the particular network device to use the particular subnet;

determining whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

selecting from the particular plurality of available network addresses a candidate subnet as the particular subnet wherein selection of the candidate subnet depends on whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

sending a response indicating the particular subnet to the subnet requesting process.

21. An apparatus for providing network addresses for hosts on a network, comprising:

means for generating and storing, as part of a subnet management process, network configuration information indicating a plurality of network addresses to be distributed among a plurality of network devices, wherein a subnet is a set of contiguous network addresses;

means for generating and storing policy information indicating a policy set of one or more policy processes, each policy process for selecting an available subnet from a plurality of available network addresses of the plurality of network addresses;

wherein each policy process manages a plurality of available network addresses of the plurality of network addresses;

means for receiving, from a subnet requesting process, a request for a subnet to be used by a particular network device;

means for invoking a particular policy process to determine a particular subnet based on the network configuration information, the request, and the policy set, wherein the particular policy process manages a particular plurality of available network addresses of the plurality of network addresses and determines the particular subnet by performing;

determining, based on the request, the particular network device to use the particular subnet;

determining whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

selecting from the particular plurality of available network addresses a candidate subnet as the particular subnet, wherein selection of the candidate subnet depends on whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

means for sending a response indicating the particular subnet to the subnet requesting process.

23. An apparatus as recited in claim 21, wherein:

said means for determining a particular subnet includes means for determining a particular size for the particular subnet based on the request; and

the particular policy process of the policy set includes means for;

managing a set of available subnets of the particular plurality of available network addresses of the plurality of network addresses; and

matching the particular size to a size of a candidate subnet of the set of available subnets; and

selecting the candidate subnet as the particular subnet.

24. An apparatus as recited in claim 23, said means for managing the set of available subnets further comprising:

means for adding a released subnet to the set of available subnets when the released subnet is made available in the particular policy process;

means for determining whether the released subnet is adjacent to a second subnet of the set of available subnets; and

if it is determined that the released subnet is adjacent, then replacing the released subnet and the second subnet in the set of available subnets with a combined subnet spanning the released subnet and the second subnet.

25. An apparatus as recited in claim 23, said means for matching the particular size to the size of the candidate subnet further comprising:

means for determining whether no subnet of the available subnets has the particular size; and

if it is determined that no subnet of the available subnets has the particular size, then

determining a second subnet of the available subnets, which second subnet is bigger than the particular size; and

means for splitting the second subnet into the candidate subnet having the particular size and a third subnet.

26. An apparatus as recited in claim 25, wherein the second subnet is a smallest subnet of the available subnets bigger than the particular size.

27. An apparatus as recited in claim 25, wherein the second subnet is a first sequentially encountered subnet of the available subnets bigger than the particular size.

28. An apparatus as recited in claim 21, wherein:

the particular policy process of the policy set includes means for, if it is determined that the particular leased subnet is allocated to the particular device, then selecting from the available network addresses a candidate subnet adjacent to the particular leased subnet.

29. An apparatus as recited in claim 28, wherein the particular policy process includes means for selecting from the available network addresses a candidate subnet not adjacent to any leased subnet of the set of leased subnets, if it is determined that no leased subnet of the set of leased subnets is allocated to the particular device.

30. An apparatus as recited in claim 21, wherein:

said means for generating and storing policy information further comprises registering a separate policy process into the policy set; and

said means for determining the particular subnet comprises;

means for sending a message to the separate policy process; and

means for receiving guidance information affecting a choice of the particular subnet.

31. An apparatus as recited in claim 30, wherein:

the guidance information includes data indicating a particular policy process of the policy set; and

the apparatus further comprises means for determining the subnet based on the particular policy process in response to the guidance information.

22. An apparatus for providing network addresses for hosts on a network, comprising:

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

a processor;

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

generating and storing, as part of a subnet management process, network configuration information indicating a plurality of network addresses to be distributed among a plurality of network devices, wherein a subnet is a set of contiguous network addresses;

generating and storing policy information indicating a policy set of one or more policy processes, each policy process for selecting an available subnet from a plurality of available network addresses of the plurality of network addresses;

wherein each policy process manages a plurality of available network addresses of the plurality of network addresses;

receiving, from a subnet requesting process, a request for a subnet to be used by a particular network device;

invoking a particular policy process to determine a particular subnet based on the network configuration information, the request, and the policy set, wherein the particular policy process manages a particular plurality of available network addresses of the plurality of network addresses and determines the particular subnet by performing;

determining, based on the request, the particular network device to use the particular subnet;

determining whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

selecting from the particular plurality of available network addresses a candidate subnet as the particular subnet, wherein selection of the candidate subnet depends on whether a leased subnet of the plurality of network addresses has already been allocated to the particular network device; and

sending a response indicating the particular subnet to the subnet requesting process.

32. An apparatus as recited in claim 22, wherein:

said step of determining a particular subnet includes the step of determining a particular size for the particular subnet based on the request; and

the particular policy process of the policy set includes the steps of;

managing a set of available subnets of the particular plurality of available network addresses of the plurality of network addresses; and

matching the particular size to a size of a candidate subnet of the set of available subnets; and

selecting the candidate subnet as the particular subnet.

33. An apparatus as recited in claim 32, said step of managing the set of available subnets further comprising the steps of:

adding a released subnet to the set of available subnets when the released subnet is made available in the particular policy process;

determining whether the released subnet is adjacent to a second subnet of the set of available subnets; and

if it is determined that the released subnet is adjacent, then replacing the released subnet and the second subnet in the set of available subnets with a combined subnet spanning the released subnet and the second subnet.

34. An apparatus as recited in claim 32, said step of matching the particular size to the size of the candidate subnet further comprising the steps of:

determining whether no subnet of the available subnets has the particular size; and

if it is determined that no subnet of the available subnets has the particular size, then

determining a second subnet of the available subnets, which second subnet is bigger than the particular size; and

splitting the second subnet into the candidate subnet having the particular size and a third subnet.

35. An apparatus as recited in claim 34, wherein the second subnet is a smallest subnet of the available subnets bigger than the particular size.

36. An apparatus as recited in claim 34, wherein the second subnet is a first sequentially encountered subnet of the available subnets bigger than the particular size.

37. An apparatus as recited in claim 22, wherein

the particular policy process of the policy set includes the steps of, if it is determined that the particular leased subnet is allocated to the particular device, then selecting from the available network addresses a candidate subnet adjacent to the particular leased subnet.

38. An apparatus as recited in claim 37, wherein the particular policy process includes the steps of, if it is determined that no leased subnet of the set of leased subnets is allocated to the particular device, then selecting from the available network addresses a candidate subnet not adjacent to any leased subnet of the set of leased subnets.

39. An apparatus as recited in claim 22, wherein:

said step of generating and storing policy information further comprises registering a separate policy process into the policy set; and

said step of determining the particular subnet comprises;

sending a message to the separate policy process; and

receiving guidance information affecting a choice of the particular subnet.

40. An apparatus as recited in claim 39, wherein:

the guidance information includes data indicating a particular policy process of the policy set; and

further comprising the step of determining the subnet based on the particular policy process in response to the guidance information.