Techniques for assigning internet protocol version six network blocks in unknown networks

• US 9,112,764 B2
• Filed: 09/20/2011
• Issued: 08/18/2015
• Est. Priority Date: 06/09/2011
• Status: Active Grant

• Current Assignee: Time Warner Cable Enterprises LLC (Charter Communications Incorporated)
• Original Assignee: Time Warner Cable Enterprises LLC (Charter Communications Incorporated)
• Inventors: Howard, Lee
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): PEREZ, JOSE L
• Application Number:
  US13/237,901
• Publication Number:
  US 20120314705A1
• Time in Patent Office: 1,428 Days
• Field of Search: 370/254, 370/255, 370/351, 370/389, 370/392, 370/401, 370/428, 709/220, 709/221, 709/222, 709/238, 709/239, 709/242, 709/245
• US Class Current: 1/1
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing

Abstract

A gateway router apparatus sends a first multicast SOLICIT message with a prefix length hint based on a number of network segments associated with the apparatus. The apparatus receives a second multicast SOLICIT message with a prefix length hint, from a downstream router in a premises network. At the apparatus, the following are recorded: (i) an estimated prefix length associated with the second multicast SOLICIT message; and (ii) an interface associated with the second multicast SOLICIT message. At the apparatus, a first ADVERTISE message is received, and a REQUEST message is sent, both over the internet. The REQUEST message specifies a prefix length based on the number of network segments associated with the apparatus and the recorded estimated prefix length associated with the second multicast SOLICIT message. The apparatus sends a second ADVERTISE message advertising ability of the apparatus to delegate prefixes in accordance with the REQUEST message.

Claims

1. A method comprising the steps of:

sending, from a gateway router apparatus, interposed between a premises network and an internet, a first multicast SOLICIT message with a prefix length hint based on a number of network segments associated with said gateway router apparatus;

receiving, at said gateway router apparatus, a plurality of second multicast SOLICIT messages, from a plurality of routers in said premises network;

recording, at said gateway router apparatus;

a prefix length hint associated with each of said plurality of second multicast SOLICIT messages; and

an interface associated with each of said plurality of second multicast SOLICIT messages;

receiving, at said gateway router apparatus, a first ADVERTISE message, over said internet;

subtracting a prefix length hint from said prefix length hints recorded at said gateway router apparatus in said recording step, wherein said prefix length hint subtracted from said prefix length hints recorded at said gateway router apparatus was received on an interface where said first ADVERTISE was received;

sending, from said gateway router apparatus, a REQUEST message, over said internet, said REQUEST message specifying a prefix length based on said number of network segments associated with said gateway router apparatus and said prefix length hints associated with said plurality of second multicast SOLICIT messages recorded at said gateway router apparatus after said subtracting step; and

sending, from said gateway router apparatus, a second ADVERTISE message advertising ability of said gateway router apparatus to delegate prefixes in accordance with said REQUEST message.

2. The method of claim 1, further comprising:

receiving, at said gateway router apparatus, a REPLY message, over said internet, in accordance with said REQUEST message, said REPLY message having a prefix assignment;

dividing said prefix assigned in said REPLY message;

assigning each local interface of said gateway router a prefix of default length; and

sending a REPLY message from said gateway router apparatus to a downstream router with a prefix assignment in accordance with said prefix length hint associated with said downstream router.

3. The method of claim 1, further comprising:

calculating said prefix length hint of said first multicast SOLICIT message by;

determining a total number of interfaces of said gateway router apparatus;

subtracting one from said total number of interfaces of said gateway router apparatus to obtain a first result; and

setting said prefix length hint of said first multicast SOLICIT message as a number of /64 prefixes in accordance with said first result; and

calculating said prefix length specified in said REQUEST message by;

adding to said first result said prefix length hints of said plurality of second multicast SOLICIT messages to obtain a second result; and

setting said prefix length specified in said REQUEST message as a number of /64 prefixes in accordance with said second result.

4. The method of claim 3, further comprising said gateway router apparatus waiting a predetermined time period prior to sending said REQUEST message, in order to allow sufficient time to receive at said gateway router apparatus pertinent communications from downstream thereof.

5. The method of claim 3, wherein, in said step of determining said total number of interfaces of said gateway router apparatus, at least one of said interfaces comprises multiple interfaces treated as a single interface.

6. The method of claim 3, wherein said REQUEST message comprises a first REQUEST message, further comprising:

sending, from a downstream router of said plurality of routers in said premises network, said second multicast SOLICIT message thereof, said prefix length hint thereof being based on a number of network segments associated with said downstream router;

receiving, at said downstream router;

said first multicast SOLICIT message; and

a third multicast SOLICIT message of said plurality of second multicast SOLICIT messages with a prefix length hint, from a still further downstream router in said premises network;

recording, at said downstream router;

said prefix length hint of said first multicast SOLICIT message;

an interface associated with said first multicast SOLICIT message;

said prefix length hint of said third multicast SOLICIT message;

an interface associated with said third multicast SOLICIT message; and

said second ADVERTISE message;

receiving, at said downstream router, said second ADVERTISE message, over said premises network;

sending, from said downstream router, a second REQUEST message, over said premises network, said second REQUEST message specifying a prefix length based on said number of network segments associated with said downstream router and on said recorded prefix length hint of said third multicast SOLICIT message; and

sending, from said downstream router, a third ADVERTISE message advertising ability of said downstream router to delegate prefixes in accordance with said second REQUEST message.

7. The method of claim 6, further comprising:

calculating said prefix length hint of said second multicast SOLICIT message associated with said downstream router by;

determining a total number of interfaces of said downstream router;

subtracting one from said total number of interfaces of said downstream router to obtain a third result; and

setting said prefix length hint of said second multicast SOLICIT message as a number of /64 prefixes in accordance with said third result; and

calculating said prefix length specified in said second REQUEST message by;

adding to said third result said third multicast SOLICIT message prefix length hint for each of said plurality of second multicast SOLICIT messages associated with a downstream router to obtain a fourth result; and

setting said prefix length specified in said second REQUEST message as a number of /64 prefixes in accordance with said fourth result.

8. The method of claim 1, wherein at least one of said plurality of second multicast SOLICIT messages does not have a second multicast SOLICIT message prefix length hint, and wherein said prefix length hint is an estimated prefix length associated with said at least one of said plurality of second multicast SOLICIT messages comprises a default value.

9. The method of claim 8 wherein said default value comprises a value of /64.

10. The method of claim 1, further comprising providing a system, wherein the system comprises distinct software modules, each of the distinct software modules being embodied in a non-transitory manner on a tangible, computer-readable, recordable storage medium, and wherein the distinct software modules comprise a dynamic host control management process module, a dynamic host control client process module, and a dynamic host control server process module;

wherein;

said step of sending said first multicast SOLICIT message is carried out by said dynamic host control client process module executing on at least one hardware processor of said gateway router apparatus;

said step of receiving said plurality of second multicast SOLICIT messages is carried out by said dynamic host control server process module executing on said at least one hardware processor of said gateway router apparatus;

said step of recording is carried out by said dynamic host control management process module executing on said at least one hardware processor of said gateway router apparatus;

said step of receiving said first ADVERTISE message is carried out by said dynamic host control client process module executing on said at least one hardware processor of said gateway router apparatus;

said step of sending said REQUEST message is carried out by said dynamic host control client process module executing on said at least one hardware processor of said gateway router apparatus; and

said step of sending said second ADVERTISE message is carried out by said dynamic host control server process module executing on said at least one hardware processor of said gateway router apparatus.

11. A method comprising the steps of:

sending, from a block-assigning router apparatus, a first multicast SOLICIT message with a prefix length hint based on a number of network segments associated with said block-assigning router apparatus;

receiving, at said block-assigning router apparatus;

a second multicast SOLICIT message from an upstream router apparatus; and

a third multicast SOLICIT message with a prefix length hint, from a downstream device;

recording, at said block-assigning router apparatus;

a prefix length hint of said second multicast SOLICIT message;

an interface associated with said second multicast SOLICIT message;

said prefix length hint of said third multicast SOLICIT message;

an interface associated with said third multicast SOLICIT message; and

a first ADVERTISE message received from said upstream router apparatus;

sending, from said block-assigning router apparatus, a REQUEST message, over said premises network, said REQUEST message specifying a prefix length based on said number of network segments associated with said block-assigning router apparatus and on said recorded prefix length hint of said third multicast SOLICIT message, but not on said recorded prefix length hint of said second multicast SOLICIT message; and

sending, from said block-assigning router apparatus, a second ADVERTISE message advertising ability of said block-assigning router apparatus to delegate prefixes in accordance with said REQUEST message.

12. A gateway router apparatus interposed between a premises network and an internet, said gateway router apparatus comprising:

a memory;

at least one processor coupled to said memory; and

a persistent storage device, tangibly embodying in a non-transitory manner instructions which when loaded into said memory cause said at least one processor to;

send, from said gateway router apparatus, a first multicast SOLICIT message with a prefix length hint based on a number of network segments associated with said gateway router apparatus;

receive, at said gateway router apparatus, a plurality of second multicast SOLICIT messages, from a plurality of routers in the premises network;

record, at said gateway router apparatus;

a prefix length hint associated with each of said plurality of second multicast SOLICIT messages; and

an interface associated with each of said plurality of second multicast SOLICIT messages;

receive, at said gateway router apparatus, a first ADVERTISE message, over the internet;

subtract a prefix length hint from said prefix length hints recorded at said gateway router apparatus, wherein said prefix length hint subtracted from said prefix length hints recorded at said gateway router apparatus was received on an interface where said first ADVERTISE was received;

send, from said gateway router apparatus, a REQUEST message, over said internet, said REQUEST message specifying a prefix length based on said number of network segments associated with said gateway router apparatus and said prefix length hints associated with said plurality of second multicast SOLICIT messages recorded at said gateway router apparatus after subtracting said prefix length hint received on said interface where said first ADVERTISE was received; and

send, from said gateway router apparatus, a second ADVERTISE message advertising ability of said gateway router apparatus to delegate prefixes in accordance with said REQUEST message.

13. The gateway router apparatus of claim 12, wherein said persistent storage device further tangibly embodies in said non-transitory manner additional instructions which when loaded into said memory cause said at least one processor to:

receive, at said gateway router apparatus, a REPLY message, over said internet, in accordance with said REQUEST message, said REPLY message having a prefix assignment;

divide said prefix assigned in said REPLY message;

assign each local interface of said gateway router a prefix of default length; and

send a REPLY message from said gateway router apparatus to a downstream router with a prefix assignment in accordance with said prefix length hint associated with said downstream router.

14. The gateway router apparatus of claim 12, wherein said persistent storage device further tangibly embodies in said non-transitory manner additional instructions which when loaded into said memory cause said at least one processor to:

calculate said prefix length hint of said first multicast SOLICIT message by;

determining a total number of interfaces of said gateway router apparatus;

subtracting one from said total number of interfaces of said gateway router apparatus to obtain a first result; and

setting said prefix length hint of said first multicast SOLICIT message as a number of /64 prefixes in accordance with said first result; and

calculate said prefix length specified in said REQUEST message by;

adding to said first result said prefix length hints of said plurality of second multicast SOLICIT messages to obtain a second result; and

setting said prefix length specified in said REQUEST message as a number of /64 prefixes in accordance with said second result.

15. The gateway router apparatus of claim 14, wherein said persistent storage device further tangibly embodies in said non-transitory manner additional instructions which when loaded into said memory cause said at least one processor to cause said gateway router apparatus to wait a predetermined time period prior to sending said REQUEST message, in order to allow sufficient time to receive at said gateway router apparatus pertinent communications from downstream thereof.

16. The gateway router apparatus of claim 14, wherein said instructions, when loaded into said memory, cause said at least one processor to determine said total number of interfaces of said gateway router apparatus by treating, as a single one of said interfaces, multiple interfaces.

17. The gateway router apparatus of claim 12, wherein at least one of said plurality of second multicast SOLICIT messages does not have a second multicast SOLICIT message prefix length hint, and wherein said prefix length hint is an estimated prefix length associated with said at least one of said plurality of second multicast SOLICIT messages comprises a default value.

18. The gateway router apparatus of claim 17 wherein said default value comprises a value of /64.

19. The gateway router apparatus of claim 12, wherein said instructions are organized as a plurality of distinct software modules, and wherein the distinct software modules comprise a dynamic host control management process module, a dynamic host control client process module, and a dynamic host control server process module;

wherein said at least one processor;

sends said first multicast SOLICIT by executing said dynamic host control client process module;

receives said plurality of second multicast SOLICIT messages by executing said dynamic host control server process module;

records said estimated prefix length and said interface by executing said dynamic host control management process module;

receives said first ADVERTISE message by executing said dynamic host control client process module;

sends said REQUEST message by executing said dynamic host control client process module; and

sends said second ADVERTISE message by executing said dynamic host control server process module.

20. A block-assigning router apparatus, within a premises network, interposed between an upstream router apparatus and a downstream router apparatus, said block-assigning router apparatus comprising:

a memory;

at least one processor coupled to said memory; and

a persistent storage device, tangibly embodying in a non-transitory manner instructions which when loaded into said memory cause said at least one processor to;

send, from said block-assigning apparatus, a first multicast SOLICIT message with a prefix length hint based on a number of network segments associated with said block-assigning router apparatus;

receive, at said block-assigning router apparatus;

a second multicast SOLICIT message from said upstream router; and

a third multicast SOLICIT message with a prefix length hint, from said downstream router;

record, at said block-assigning router apparatus;

said prefix length hint of said second multicast SOLICIT message;

an interface associated with said second multicast SOLICIT message;

said prefix length hint of said third multicast SOLICIT message;

an interface associated with said third multicast SOLICIT message; and

an first ADVERTISE message received from said upstream router apparatus;

send, from said block-assigning router, a REQUEST message, over said premises network, said REQUEST message specifying a prefix length based on said number of network segments associated with said block-assigning router and on said recorded prefix length hint of said third multicast SOLICIT message, but not on said recorded prefix length hint of said second multicast SOLICIT message; and

send, from said block-assigning router apparatus, a second ADVERTISE message advertising ability of said block-assigning router apparatus to delegate prefixes in accordance with said REQUEST message.

21. An article of manufacture comprising a computer program product, said computer program product comprising:

a tangible computer-readable recordable storage medium, storing in a non-transitory manner computer readable program code for execution by at least one processor of a gateway router apparatus interposed between a premises network and an internet, the computer readable program code comprising;

computer readable program code configured to send, from said gateway router apparatus, a first multicast SOLICIT message with a prefix length hint based on a number of network segments associated with said gateway router apparatus;

computer readable program code configured to receive, at said gateway router apparatus, a plurality of second multicast SOLICIT messages, from a plurality of routers in the premises network;

computer readable program code configured to record, at said gateway router apparatus;

a prefix length hint associated with each of said plurality of second multicast SOLICIT messages; and

an interface associated with each of said plurality of second multicast SOLICIT messages;

computer readable program code configured to receive, at said gateway router apparatus, a first ADVERTISE message, over the internet;

computer readable program code configured to subtract a prefix length hint from said prefix length hints recorded at said gateway router apparatus, wherein said prefix length hint subtracted from said prefix length hints recorded at said gateway router apparatus was received on an interface where said first ADVERTISE was received;

computer readable program code configured to send, from said gateway router apparatus, a REQUEST message, over said internet, said REQUEST message specifying a prefix length based on said number of network segments associated with said gateway router apparatus and said prefix length hints associated with said plurality of second multicast SOLICIT messages recorded at said gateway router apparatus after subtracting said prefix length hint received on said interface where said first ADVERTISE was received; and

computer readable program code configured to send, from said gateway router apparatus, a second ADVERTISE message advertising ability of said gateway router apparatus to delegate prefixes in accordance with said REQUEST message.

22. A gateway router apparatus interposed between a premises network and an internet, said gateway router apparatus comprising:

means for sending, from said gateway router apparatus, a first multicast SOLICIT message with a prefix length hint based on a number of network segments associated with said gateway router apparatus;

means for receiving, at said gateway router apparatus, a plurality of second multicast SOLICIT messages, from a plurality of routers in the premises network;

means for recording, at said gateway router apparatus;

a prefix length hint associated with each of said plurality of second multicast SOLICIT messages; and

an interface associated with each of said plurality of second multicast SOLICIT messages;

means for receiving, at said gateway router apparatus, a first ADVERTISE message, over the internet;

means for subtracting a prefix length hint from said prefix length hints recorded at said gateway router apparatus, wherein said prefix length hint subtracted from said prefix length hints recorded at said gateway router apparatus was received on an interface where said first ADVERTISE was received;

means for sending, from said gateway router apparatus, a REQUEST message, over said internet, said REQUEST message specifying a prefix length based on said number of network segments associated with said gateway router apparatus and said prefix length hints associated with said plurality of second multicast SOLICIT messages recorded at said gateway router apparatus after subtracting said prefix length hint received on said interface where said first ADVERTISE was received; and

means for sending, from said gateway router apparatus, a second ADVERTISE message advertising ability of said gateway router apparatus to delegate prefixes in accordance with said REQUEST message.