Method and apparatus for assigning IP addresses
View Patent ↗The invention includes a method and apparatus for assigning an IP address to a mobile node (MN) from an IP address space represented using an address aggregation tree. A method includes receiving a request for an IP address for the MN, identifying each of a plurality of sub-tree gaps in the address aggregation tree, selecting one of the identified sub-tree gaps, and assigning an available IP address from the selected sub-tree gap to the MN. The sub-tree gaps of the address aggregation tree are identified using a recursive algorithm that traverses the address aggregation tree. The selected one of the sub-tree gaps is selected based on respective sizes of the identified sub-tree gaps. The assigned IP address is communicated to the MN for use by the MN in accessing various services.
1. A method for assigning an IP address to a mobile node (MN) from an IP address space represented using an address aggregation tree, comprising:
receiving a request for an IP address for the MN;
identifying each of a plurality of sub-tree gaps in the address aggregation tree, each of the sub-tree gaps comprising at least one IP address available for assignment to the MN;
selecting one of the identified sub-tree gaps, wherein the selected one of the sub-tree gaps is selected according to respective sub-tree gap sizes of the identified sub-tree gaps, wherein the selected sub-tree gap comprises one of the sub-tree gaps having a smallest sub-tree gap size, wherein, when at least two of the plurality of sub-tree gaps have the same smallest sub-tree gap size, the selected sub-tree gap comprises one of the at least two sub-tree gaps having a smallest address space gap size; and
assigning one of the at least one available IP address of the selected sub-tree gap to the MN.
2. A method for assigning an IP address to a mobile node (MN) from an IP address space represented using an address aggregation tree, comprising:
receiving a request for an IP address for the MN;
identifying each of a plurality of sub-tree gaps in the address aggregation tree, each of the sub-tree gaps comprising at least one IP address available for assignment to the MN;
selecting one of the identified sub-tree gaps;
assigning one of the at least one available IP address of the selected sub-tree gap to the MN; and
in response to a determination that assignment of the available IP address fills a sub-tree in which the selected one of the sub-tree gaps is located, removing the sub-tree from the address aggregation tree.
3. The method of claim 2 , wherein identifying the plurality of sub-tree gaps in the address aggregation tree comprises:
traversing the address aggregation tree using an algorithm to identify each of the plurality of sub-tree gaps.
4. The method of claim 2 , wherein each sub-tree gap comprises a gap in the IP address space that is located within a single sub-tree of the address aggregation tree.
5. The method of claim 2 , wherein the selected sub-tree gap is selected in a manner tending to fill a largest sub-tree of the address aggregation tree first.
6. The method of claim 2 , further comprising:
propagating the assigned IP address toward the MN.
7. The method of claim 2 , wherein the plurality of sub-tree gaps in the address aggregation tree are identified using a sub-tree gap list generated using the address aggregation tree.
8. The method of claim 7 , wherein, for each of the sub-tree gaps, the sub-tree gap list comprises:
an indication of the at least one IP address of the sub-tree gap; and
a sub-tree gap size of the sub-tree gap.
9. An apparatus for assigning an IP address to a mobile node (MN) from an IP address space represented using an address aggregation tree, comprising:
means for receiving a request for an IP address for the MN;
means for identifying each of a plurality of sub-tree gaps in the address aggregation tree, each of the sub-tree gaps comprising at least one IP address available for assignment to the MN;
means for selecting one of the identified sub-tree gaps, wherein the selected one of the sub-tree gaps is selected according to respective sub-tree gap sizes of the identified sub-tree gaps, wherein the selected sub-tree gap comprises one of the sub-tree gaps having a smallest sub-tree gap size, wherein, when at least two of the plurality of sub-tree gaps have the same smallest sub-tree gap size, the selected sub-tree gap comprises one of the at least two sub-tree gaps having a smallest address space gap size; and
means for assigning one of the at least one available IP address of the selected sub-tree gap to the MN.
10. An apparatus for assigning an IP address to a mobile node (MN) from an IP address space represented using an address aggregation tree, comprising:
means for receiving a request for an IP address for the MN;
means for identifying each of a plurality of sub-tree gaps in the address aggregation tree, each of the sub-tree gaps comprising at least one IP address available for assignment to the MN;
means for selecting one of the identified sub-tree gaps;
means for assigning one of the at least one available IP address of the selected sub-tree gap to the MN; and
means for removing, from the address aggregation tree, a sub-tree in which the selected one of the sub-tree gaps is located, wherein the sub-tree is removed in response to a determination that assignment of the available IP address fills the sub-tree in which the selected one of the sub-tree gaps is located.
11. The apparatus of claim 10 , wherein the means for identifying the plurality of sub-tree gaps in the address aggregation tree comprises:
means for traversing the address aggregation tree using an algorithm to identify each of the plurality of sub-tree gaps.
12. The apparatus of claim 10 , wherein each sub-tree gap comprises a gap in the IP address space that is located within a single sub-tree of the address aggregation tree.
13. The apparatus of claim 10 , wherein the selected sub-tree gap is selected in a manner tending to fill a largest sub-tree of the address aggregation tree first.
14. The apparatus of claim 10 , further comprising:
means for propagating the assigned IP address toward the MN.
15. A non-transitory computer-readable storage medium storing a software program, that, when executed by a computer, causes the computer to perform a method for assigning an IP address to a mobile node (MN) from an IP address space represented using an address aggregation tree, the method comprising:
receiving a request for an IP address for the MN;
identifying each of a plurality of sub-tree gaps in the address aggregation tree, each of the sub-tree gaps comprising at least one IP address available for assignment to the MN;
selecting one of the identified sub-tree gaps;
assigning one of the at least one available IP address of the selected sub-tree gap to the MN; and
in response to a determination that assignment of the available IP address fills a sub-tree in which the selected one of the sub-tree gaps is located, removing the sub-tree from the address aggregation tree.