Resource allocation and reclamation for on-demand address pools

• US 7,788,345 B1
• Filed: 09/13/2001
• Issued: 08/31/2010
• Est. Priority Date: 06/04/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Salama, Hussein F., Sukiman, Indrajanti, Cramer, Thomas E. Jr., Sheth, Purnam Anil
• Primary Examiner(s): Divecha; Kamal B
• Application Number:
  US09/952,259
• Time in Patent Office: 3,274 Days
• Field of Search: 709219-224, 709/226, 709/227, 709/229, 709/245, 709/228, 709/249, 710/4, 710/9
• US Class Current: 709/220
• CPC Class Codes: H04L 2101/668 Internet protocol [IP] address subnets
• CPC Class Codes: H04L 61/5014 using dynamic host configuration protocol [DHCP] or bootstrap protocol [BOOTP]
• CPC Class Codes: H04L 61/5061 Pools of addresses

Abstract

A method for on-demand management of Internet Protocol (IP) address pools includes allocating an unused IP address from a local IP address pool designated for a remote domain if a request to connect to the remote domain is received and deallocating an IP address if the IP address is released. The local IP address pool includes at least one subnet dynamically assigned from a global IP address pool. Each of the subnets specifies a contiguous set of one or more IP addresses. IP addresses are allocated using a first-assigned-subnet-first policy, wherein an IP address is allocated from a least recently assigned subnet having at least one unallocated IP address. According to one aspect, subnets are deassigned using a last-assigned-subnet-first policy, wherein the deassigned subnet is the most recently assigned subnet having no allocated IP addresses.

Claims

1. A method for on-demand management of Internet Protocol (IP) address pools, the method comprising:

receiving a first dynamically assigned subnet from a global IP address pool, wherein the global IP address pool maintains a pool of IP addresses for one or more remote domains, the first dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to one of the one or more remote domains;

storing the first dynamically assigned subnet in a local IP address pool;

receiving a second dynamically assigned subnet, the second dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to the one of the one or more remote domains;

storing the second dynamically assigned subnet in the local IP address pool;

allocating an IP address from the local IP address pool, wherein the local IP address pool comprises the first and the second dynamically assigned subnets, when a request to connect to the one of the one or more remote domains is received, wherein the allocating is based on a first-assigned subnet policy, in which the IP address is allocated from a least recently assigned subnet in the local IP address pool corresponding to the one of the one or more remote domains and having at least one unallocated IP address, monitoring the local IP address pool utilization, and requesting one or more additional subnets specifying a contiguous set of IP addresses corresponding to the one of the one or more remote domains from the global IP address pool if utilization of the local IP address pool exceeds a first high threshold and releasing one or more subnets from the local IP address pool to the global IP address pool if utilization of the local IP address pool falls below a second low threshold, wherein the requesting one or more additional subnets comprises requesting a subnet having a first predetermined number of IP addresses, wherein the first high and second low thresholds are preconfigured before the one or more additional subnets are requested; and

deallocating the IP address if the IP address is released, wherein the one of the one or more remote domains comprises a virtual private network;

wherein the releasing one or more subnets is based on a last-assigned subnet first policy, in which the one or more subnet that was most recently assigned and stored in the local IP address pool is released first,

wherein the last-assigned subnet first policy further comprises;

releasing the one or more subnets from the local IP address pool by selecting the one or more subnets to be released from subnets having no allocated IP addresses, releasing the one or more subnets based upon a subnet assignment time and releasing the one or more subnets in decreasing order of subnet assignment times;

wherein the releasing one or more subnets further comprises releasing a subnet having a second predetermined number of IP addresses.

2. The method of claim 1 wherein the releasing one or more subnets further comprises deassigning subnets having the smallest number of allocated IP addresses.

3. The method of claim 1, further comprising polling the local IP address pool at predetermined intervals to obtain local IP address pool utilization information.

4. The method of claim 1 wherein the requesting one or more subnets further comprises requesting a subnet having a size that is relative to a current subnet size.

5. The method of claim 4 wherein the deallocating an IP address further comprises deassigning a subnet having a size that is relative to the current subnet size.

6. The method of claim 1 wherein the requesting one or more subnets further comprises requesting a subnet having a size that is relative to an initial subnet size.

7. The method of claim 6 wherein the deallocating an IP address further comprises deassigning a subnet having a size that is relative to the initial subnet size.

8. The method of claim 1 wherein the requesting one or more subnets further comprises requesting a subnet having a size that is relative to a current subnet size.

9. The method of claim 1 wherein the deallocating an IP address further comprises deassigning a subnet having a size that is relative to the current subnet size.

10. The method of claim 1 wherein the releasing one or more subnets further comprises removing the summarized route for the one or more subnets from a routing table associated with the local IP address pool.

11. The method of claim 1 wherein the method further comprises inserting a route summary for the requested one or more subnets if the requested one or more subnets is received.

12. A non-transitory computer readable storage medium storing a program embodying instructions executable by a computer to perform a method for on-demand management of Internet Protocol (IP) address pools, the method comprising:

receiving a first dynamically assigned subnet from a global IP address pool, wherein the global IP address pool maintains a pool of IP addresses for one or more remote domains, the first dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to if one of the one or more remote domains;

storing the first dynamically assigned subnet in a local IP address pool;

receiving a second dynamically assigned subnet, the second dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to the one of the one or more remote domains;

storing the second dynamically assigned subnet in the local IP address pool;

allocating an IP address from the local IP address pool, wherein the local IP address pool comprises the first and the second dynamically assigned subnets, when a request to connect to the one of the one or more remote domains is received, wherein the allocating is based on a first-assigned subnet policy, in which the IP address is allocated from a least recently assigned subnet in the local IP address pool corresponding to the one of the one or more remote domains and having at least one unallocated IP address, monitoring the local IP address pool utilization, and requesting one or more additional subnets specifying a contiguous set of IP addresses corresponding to the one of the one or more remote domains from the global IP address pool if utilization of the local IP address pool exceeds a first high threshold and releasing one or more subnets from the local IP address pool to the global IP address pool if utilization of the local IP address pool falls below a second low threshold, wherein the requesting one or more additional subnets comprises requesting a subnet having a first predetermined number of IP addresses, the first high and second low thresholds are preconfigured before the one or more additional subnets are requested; and

deallocating the IP address if the IP address is released, wherein the one of the one or more remote domains comprises a virtual private network;

wherein the releasing one or more subnets is based on a last-assigned subnet first policy, in which the one or more subnets that was most recently assigned and stored in the local IP address pool is released first,

wherein the last-assigned subnet first policy further comprises;

releasing the one or more subnets from the local IP address pool by selecting the one or more subnets to be released from subnets having no allocated IP addresses, releasing the one or more subnets based upon a subnet assignment time and releasing the one or more subnets in decreasing order of subnet assignment times;

wherein the releasing one or more subnets further comprises releasing a subnet having a second predetermined number of IP addresses.

13. The non-transitory computer readable storage medium of claim 12 wherein the releasing one or more subnets further comprises deassigning subnets having the smallest number of allocated IP addresses.

14. The non-transitory computer readable storage medium of claim 12 wherein the method further comprises polling the local IP address pool at predetermined intervals to obtain local IP address pool utilization information.

15. The non-transitory computer readable storage medium of claim 12 wherein the requesting one or more subnets further comprises requesting a subnet having a size that is relative to a current subnet size.

16. The non-transitory computer readable storage medium of claim 15 wherein the deallocating an IP address further comprises deassigning a subnet having a size that is relative to the current subnet size.

17. The non-transitory computer readable storage medium of claim 12 wherein the requesting one or more subnets further comprises requesting a subnet having a size that is relative to an initial subnet size.

18. The non-transitory computer readable storage medium of claim 17 wherein the deallocating an IP address further comprises deassigning a subnet having a size that is relative to the initial subnet size.

19. The non-transitory computer readable storage medium of claim 12 wherein the requesting one or more subnets further comprises requesting a subnet having a size that is relative to a current subnet size.

20. The non-transitory computer readable storage medium of claim 12 wherein the deallocating an IP addresses further comprises deassigning a subnet having a size that is relative to the current subnet size.

21. The non-transitory computer readable storage medium of claim 12 wherein the releasing one or more subnets further comprises removing the summarized route for the one or more subnet from a routing table associated with the local IP address pool.

22. The non-transitory computer readable storage medium of claim 12 wherein the method further comprises inserting a route summary for the requested one or more subnets if the requested one or more subnets is received.

23. A system for on-demand management of Internet Protocol (IP) address pools, the system comprising:

a memory; and

a computer processor operably coupled to the memory element for managing IP address pools, including;

means for receiving a first dynamically assigned subnet from a global IP address pool, wherein the global IP address pool maintains a pool of IP addresses for one or more remote domains, the first dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to one of the one or more remote domains;

means for storing the first dynamically assigned subnet in a local IP address pool;

means for receiving a second dynamically assigned subnet, the second dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to the one of the one or more remote domains;

means for storing the second dynamically assigned subnet in the local IP address pool;

means for allocating an IP address from the local IP address pool, wherein the local IP address pool comprises the first and the second dynamically assigned subnets, when a request to connect to the one of the one or more remote domains is received, wherein the allocating is based on a first-assigned subnet policy, in which the IP address is allocated from a least recently assigned of any subnets in the local IP address pool having at least one unallocated IP address corresponding to the one of the one or more remote domains, monitoring the local IP address pool utilization, and requesting one or more additional subnets specifying a contiguous set of IP addresses corresponding to the one of the one or more remote domains from the global IP address pool if utilization of the local IP address pool exceeds a first high threshold and releasing one or more subnets from the local IP address pool to the global IP address pool if utilization of the local IP address pool falls below a second low threshold, wherein the requesting one or more additional subnets comprises requesting a subnet having a first predetermined number of IP addresses, wherein the first high and second low thresholds are preconfigured before the one or more additional subnets are requested; and

means for deallocating the IP address if the IP address is released, wherein the one of the one or more remote domains comprises a virtual private network;

wherein the releasing one or more subnets is based on a last-assigned subnet first policy, in which the one or more subnet that was most recently assigned and stored in the local IP address pool is released first,

wherein the last-assigned subnet first policy further comprises;

releasing the one or more subnets from the local IP address pool by selecting the one or more subnets to be released from subnets having no allocated IP addresses, releasing the one or more subnets based upon a subnet assignment time and releasing the one or more subnets in decreasing order of subnet assignment times;

wherein the releasing one or more subnets further comprises releasing a subnet having a second predetermined number of IP addresses.

24. The system of claim 23 wherein the means for releasing one or more subnets further comprises means for deassigning subnets having the smallest number of allocated IP addresses.

25. The system of claim 23 wherein the system further comprises means for polling the local IP address pool at predetermined intervals to obtain local IP address pool utilization information.

26. The system of claim 23 wherein the means for requesting one or more subnets further comprises means for requesting a subnet having a size that is relative to a current subnet size.

27. The system of claim 26 wherein the means for deallocating an IP address further comprises means for deassigning a subnet having a size that is relative to the current subnet size.

28. The system of claim 23 wherein the means for requesting one or more subnets further comprises means for requesting a subnet having a size that is relative to an initial subnet size.

29. The system of claim 28 wherein the means for deallocating an IP address further comprises means for deassigning a subnet having a size that is relative to the initial subnet size.

30. The system of claim 23 wherein the means for requesting one or more subnets further comprises means for requesting a subnet having a size that is relative to a current subnet size.

31. The system of claim 23 wherein the means for deallocating an IP address further comprises means for deassigning a subnet having a size that is relative to the current subnet size.

32. The system of claim 23 wherein the means for releasing one or more subnets further comprises means for removing the summarized route for the one or more subnets from a routing table associated with the local IP address pool.

33. The system of claim 23, further comprising means for inserting a route summary for the requested one or more subnets if the requested one or more subnets is received.

34. An apparatus for on-demand management of Internet Protocol (IP) address pools, the apparatus comprising:

a memory; and

a computer processor operably coupled to the memory element and operable to execute instructions associated with a local IP address pools manager,

wherein the local IP address pools manager is configured to receive a first dynamically assigned subnet from a global IP address pool, wherein the global IP address pool maintains a pool of IP addresses for one or more remote domains, the first dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to a one of the one or more remote domains, to store the first dynamically assigned subnet in a local IP address pool, to receive a second dynamically assigned subnet, the second dynamically assigned subnet specifying a contiguous set of IP addresses and corresponding to the one of the one or more remote domains, and to store the second dynamically assigned subnet in the local IP address pool;

wherein the local IP address pools manager contains an IP address allocator configured to allocate an IP address from the local IP address pool, wherein the local IP address pool comprises the first and the second dynamically assigned subnets, when a request to connect to the one of the one or more remote domains is received, wherein the allocating is based on a first-assigned subnet policy, in which the IP address is allocated from a least recently assigned subnet in the local IP address pool corresponding to the one of the one or more remote domains and having at least one unallocated IP address, monitoring the local IP address pool utilization, and requesting one or more additional subnets specifying a contiguous set of IP addresses corresponding to the one of the one or more remote domains from the global IP address pool if utilization of the local IP address pool exceeds a first high threshold and releasing one or more subnets to the global IP address pool if utilization of the local IP address pool falls below a second low threshold, wherein the requesting one or more additional subnets comprises requesting a subnet having a first predetermined number of IP addresses, wherein the first high and second low thresholds are preconfigured before the one or more additional subnets are requested; and

wherein the local IP address pools manager further contains an IP address deallocator configured to deallocate the IP address if the IP address is unused, wherein the one of the one or more remote domains comprises a virtual private network;

wherein the releasing one or more subnets is based on a last-assigned subnet first policy, in which the one or more subnets that was most recently assigned and stored in the local IP address pool is released first,

wherein the last-assigned subnet first policy further comprises;

releasing the one or more subnets from the local IP address pool by selecting the one or more subnets to be released from subnets having no allocated IP addresses, releasing the one or more subnets based upon a subnet assignment time and releasing the one or more subnets in decreasing order of subnet assignment times;

wherein the releasing one or more subnets further comprises releasing a subnet having a second predetermined number of IP addresses.

35. The apparatus of claim 34 wherein the apparatus further comprises:

a utilization assessor to assess local IP address utilization;

a subnet requester to request one or more subnets based upon a first signal from the utilization assessor;

a subnet receiver to receive the one or more subnets requested by the subnet requester; and

a subnet returner to return one or more subnets based upon a second signal from the utilization assessor.

36. The apparatus of claim 34 wherein the subnet returner is further configured to release subnets having the smallest number of allocated IP addresses.

37. The apparatus of claim 34 wherein the subnet requester is further configured to request a subnet having a size that is relative to a current subnet size.

38. The apparatus of claim 37 wherein the subnet returner is further configured to deassign a subnet having a size that is relative to the current subnet size.

39. The apparatus of claim 34 wherein the subnet requester is further configured to request a subnet having a size that is relative to an initial subnet size.

40. The apparatus of claim 37 wherein the subnet returner is further configured to release a subnet having a size that is relative to the initial subnet size.

41. The apparatus of claim 34 wherein the subnet requester is further configured to request a subnet having a size that is relative to a current subnet size.

42. The apparatus of claim 34 wherein the subnet returner is further configured to deassign a subnet having a size that is relative to the current subnet size.

43. The apparatus of claim 34 wherein the apparatus is further configured to remove the summarized route for the one or more subnets from a routing table associated with the local IP address pool if the one or more subnets is deassigned.

44. The apparatus of claim 34 wherein the apparatus is further configured to insert a route summary for the requested one or more subnets if the subnet receiver receives the requested one or more subnets.

45. The apparatus of claim 34 wherein

the global IP address pool comprises an Authentication, Authorization and Accounting (AAA) server coupled to a global IP address interface to communicate with the AAA server using the RADIUS protocol.

46. The apparatus of claim 34 wherein

the global IP address pool comprises a Dynamic Host Configuration Protocol (DHCP) server coupled to a global IP address to communicate with the DHCP server using the DHCP protocol.