Method and apparatus for distributing dynamic auto-summarization of internet protocol reachable addresses

• US 7,782,882 B2
• Filed: 09/17/2007
• Issued: 08/24/2010
• Est. Priority Date: 09/17/2007
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Qureshi, Muhammad Akber, Lofquist, David Brian
• Primary Examiner(s): Pezzlo; John
• Application Number:
  US11/856,334
• Publication Number:
  US 20090073994A1
• Time in Patent Office: 1,072 Days
• Field of Search: 370/252, 370/254, 370/315, 370/389, 370/400, 370/401
• US Class Current: 370/401
• CPC Class Codes: H04L 2101/60 Types of network addresses
• CPC Class Codes: H04L 2101/695 using masks or ranges of addresses
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

A computer implemented method, apparatus, and computer usable program code for managing addresses in a network. In one advantageous embodiment, a computer implemented method is used to managing addresses for a plurality of destinations in a network. Addresses assigned to a plurality of gateways are summarized to form summarized addresses containing prefixes and addresses for the plurality of gateways in which each gateway in the plurality of gateways is associated with a portion of the prefixes and addresses for destinations handled by the each gateway in the plurality of gateways. A gateway in the plurality of gateways having a largest portion of the summarized addresses is assigned a prefix for all addresses assigned to the network to form a selected gateway. An associated portion of the summarized addresses for the selected gateway is replaced with the prefix.

Claims

1. A computer implemented method for managing addresses for a plurality of destinations in a network, the computer implemented method comprising:

summarizing addresses assigned to a plurality of gateways to form summarized addresses containing prefixes and addresses for the plurality of gateways in which each gateway in the plurality of gateways is associated with a portion of the prefixes and addresses for destinations handled by the each gateway in the plurality of gateways;

assigning a gateway in the plurality of gateways having a largest portion of the summarized addresses, a prefix for all addresses assigned to the network to form a selected gateway; and

replacing an associated portion of the summarized addresses for the selected gateway with the prefix.

2. The computer implemented method of claim 1 further comprising:

assigning a particular gateway with a largest number of addresses covered by a selected prefix for a prefix size within a range of prefix sizes;

removing addresses assigned to the particular gateway that are covered by the selected prefix; and

adding particular addresses assigned to other gateways in the plurality of gateways that are covered by the selected prefix, wherein the particular addresses are selected addresses removed from a previous summarization by another prefix having a different prefix size.

3. The computer implemented method of claim 2 further comprising:

repeating the steps of assigning the particular gateway with the largest number of addresses covered by the selected prefix for the prefix size within the range of prefix sizes;

removing addresses assigned to the particular gateway that are covered by the selected prefix;

and adding particular addresses assigned to other gateways in the plurality of gateways that are covered by the selected prefix, wherein the particular addresses are selected addresses removed from the previous summarization by another prefix having the different prefix size.

4. A computer implemented method for managing addresses, the computer implemented method comprising:

vertically summarizing the addresses dynamically for a plurality of gateways in a network while the network is active to form a set of prefixes and addresses;

horizontally summarizing the set of prefixes and addresses to form a summarized set of addresses; and

sending the summarized set of addresses to another network, wherein the summarized set of addresses are used to select a gateway for use in directing traffic to a selected destination.

5. The computer implemented method of claim 4 further comprising:

selecting a gateway from the plurality of gateways using the summarized set of addresses to send traffic to a destination in a plurality of destinations.

6. The computer implemented method of claim 4, wherein the network is a tactical network and the another network is a satellite network and wherein the sending step comprises:

sending the summarized set of addresses from the tactical network to the satellite network for use in directing traffic to a plurality of destinations associated with the summarized set of addresses.

7. The computer implemented method of claim 4, wherein the network is a first sub-network within a larger network, and the another network is a second sub-network within the larger network providing access to the first sub-network to reach destinations in other sub- networks in the larger network and wherein the sending step comprises:

sending the summarized set of addresses from the first sub-network to the second sub- network for use in directing traffic to a plurality of destinations associated with the summarized set of addresses.

8. The computer implemented method of claim 4, wherein the sending step comprises:

sending a portion of the summarized set of addresses assigned to each gateway by the each gateway to the another network to send the summarized set of addresses to the another network.

9. The computer implemented method of claim 4, wherein the vertical summarizing step comprises:

successively summarizing Internet Protocol addresses of one network assigned to each gateway within the plurality of gateways dynamically for distribution into another network to create prefixes for a set of bits within a plurality of bits using the Internet Protocol addresses assigned to the each gateway.

10. The computer implemented method of claim 4, wherein the horizontal summarizing step comprises:

successively summarizing prefixes of one network assigned to a plurality of gateways dynamically to create prefixes with different prefix sizes for a set of bits within a plurality of bits using the prefixes and Internet Protocol addresses assigned to the plurality of gateways.

11. The computer implemented method of claim 4, wherein the horizontally summarizing step comprises:

assigning a gateway in the plurality of gateways a prefix for particular addresses assigned to the network.

12. The computer implemented method of claim 4 further comprising:

initiating the computer implemented method in response to an event.

13. The computer implemented method of claim 9, wherein the initiating step comprises:

initiating the computer implemented method in response to a change in a topology of the network.

14. The computer implemented method of claim 4 further comprising:

performing the step of vertically summarizing the addresses dynamically for the plurality of gateways in the network while the network is active to form the set of prefixes and the step of horizontally summarizing the set of prefixes and addresses to form the summarized set of addresses using link state information for the plurality of gateways.

15. The computer implemented method of claim 4, wherein an association of gateways in the plurality of gateways with the set of summarized addresses is present in the set of summarized addresses.

16. A computer program product for managing addresses for a plurality of destinations in a network, the computer program product comprising:

a non-transitory computer readable storage medium;

program code stored on the non-transitory computer readable storage medium for summarizing addresses assigned to a plurality of gateways to form summarized addresses containing prefixes and addresses for the plurality of gateways in which each gateway in the plurality of gateways is associated with a portion of the prefixes and addresses for destinations handled by the each gateway in the plurality of gateways;

program code stored on the non-transitory computer readable storage medium for assigning a gateway in the plurality of gateways having a largest portion of the summarized addresses, a prefix for all addresses assigned to the network to form a selected gateway; and

program code stored on the non-transitory computer readable storage medium for replacing an associated portion of the summarized addresses for the selected gateway with the prefix.

17. The computer program products of claim 16 further comprising:

program code stored on the non-transitory computer readable storage medium for assigning a particular gateway with a largest number of addresses covered by a selected prefix for a prefix size within a range of prefix sizes;

program code stored on the non-transitory computer readable storage medium for removing addresses assigned to the particular gateway that are covered by the selected prefix;

and program code stored on the non-transitory computer readable storage medium for adding particular addresses assigned to other gateways in the plurality of gateways that are covered by the selected prefix, wherein the particular addresses are selected addresses removed from a previous summarization by another prefix having a different prefix size.

18. A computer program product for managing addresses, the computer program product comprising:

non-transitory computer readable storage medium ;

program code stored on the non-transitory computer readable storage medium for vertically summarizing the addresses dynamically for a plurality of gateways in a network while the network is active to form a set of prefixes and addresses;

program code stored on the non-transitory computer readable storage medium for horizontally summarizing the set of prefixes and addresses to form a summarized set of addresses; and

program code stored on the non-transitory computer readable storage medium for sending the summarized set of addresses to another network, wherein the summarized set of addresses are used to select a gateway for use in directing traffic to a selected destination.

19. The computer program product of claim 18 further comprising:

program code stored on the non-transitory computer readable storage medium for selecting a gateway from the plurality of gateways using the summarized set of addresses to send traffic to a destination in a plurality of destinations.

20. The computer program product claim 18, wherein the network is a tactical network and the another network is a satellite network and wherein the program code stored on the non-transitory computer readable storage medium for sending the summarized set of addresses to another network, wherein the set of summarized addresses are used to select a gateway for use in directing traffic to the a selected destination, comprises:

program code stored on the non-transitory computer readable storage medium for sending the summarized set of addresses from the tactical network to the satellite network for use in directing traffic to a plurality of destinations associated with the summarized set of addresses.

21. The computer program product of claim 18, wherein the network is a first sub-network within a larger network, and the another network is a second sub- network within the larger network providing access to the first sub-network to reach destinations in other sub-networks in the larger network and wherein the program code stored on the non- transitory computer readable storage medium for sending the summarized set of addresses to another network, wherein the summarized set of addresses are used to select the gateway for use in directing traffic to the selected destination comprises:

program code stored on the non-transitory computer readable storage medium for sending the summarized set of addresses from the first sub-network to the second sub-network for use in directing traffic to a plurality of destinations associated with the summarized set of addresses.

22. A network data processing system comprising:

a plurality of destinations; and

a plurality of gateways, wherein the plurality of gateways vertically summarize addresses for the plurality of destinations dynamically for the plurality of gateways in a network within the network data processing system while the network is active to form a set of prefixes and addresses;

horizontally summarize the set of prefixes and addresses to form a summarized set of addresses; and

sending the summarized set of addresses to another network within the network data processing system, wherein the set of summarized addresses are used to select a gateway for use in directing traffic to the a selected destination.

23. The network data processing system of claim 22, wherein the network is a tactical network and wherein the another network is a satellite network.

24. The network data processing system of claim 22, wherein the plurality of gateways vertically summarize the addresses, horizontally summarize the set of prefixes and addresses, and send the summarized set of addresses to the another network in response to a change in a topology of the network.

25. The network data processing system of claim 22, wherein the plurality of destinations are a plurality of mobile nodes.