Dynamic allocation of context identifiers for header compression

• US 8,553,688 B2
• Filed: 07/28/2011
• Issued: 10/08/2013
• Est. Priority Date: 07/28/2011
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Primary Examiner(s): Pezzlo, John
• Application Number:
  US13/192,750
• Publication Number:
  US 20130028095A1
• Time in Patent Office: 803 Days
• Field of Search: 370/252, 370/254, 370/389, 370/401
• US Class Current: 370/389
• CPC Class Codes: H04L 2101/659 Internet protocol version 6 [IPv6] addresses
• CPC Class Codes: H04L 2101/672 Short addresses
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 61/106 across networks, e.g. mapping telephone numbers to data network addresses

Abstract

In one embodiment, routable traffic through one or more border routers between a local computer network and a global computer network is monitored in order to characterize use of one or more global prefixes of the traffic. A particular set of the global prefixes, up to a maximum number, that are most frequently used may be mapped into a set of context identifiers (IDs) having a shorter bit-length than the global prefixes. The context IDs may then be distributed into the local computer network, and the one or more border routers convert between the context IDs and the global prefixes, accordingly.

Claims

1. A method, comprising:

monitoring routable traffic through a border router between a local computer network and a global computer network;

characterizing use of one or more global prefixes of the traffic;

determining a number of global prefixes that can be mapped into context identifiers (IDs) having a shorter bit-length than the global prefixes;

determining, up to the number, a particular set of the global prefixes that are most frequently used;

mapping the context IDs to the particular set of global prefixes;

distributing the context IDs into the local computer network; and

converting between the context IDs and the global prefixes at the border router.

2. The method as in claim 1, wherein there are a plurality of border routers between the local and global computer networks;

the method further comprising;

characterizing use of one or more global prefixes of the traffic based on monitoring the traffic through the plurality of border routers.

3. The method as in claim 2, further comprising:

determining, by a primary border router of the plurality of border routers, the particular set of the global prefixes that are most frequently used based on the traffic through the plurality of border routers;

mapping, by the primary border router, the context IDs to the particular set of global prefixes;

distributing the context IDs from the primary border router into the local computer network; and

converting between the context IDs and the global prefixes at the plurality of border routers.

4. The method as in claim 2, further comprising:

determining, by each border router of the plurality of borders via a deterministic function shared by the plurality of border routers, the particular set of the global prefixes that are most frequently used based on the traffic through the plurality of border routers;

mapping the context IDs to the particular set of global prefixes using the deterministic function;

distributing the context IDs from the plurality of border routers into the local computer network; and

converting between the context IDs and the global prefixes at the plurality of border routers.

5. The method as in claim 1, wherein there are a plurality of border routers between the local and global computer networks;

the method further comprising;

determining, by each border router of the plurality of border routers, a respective set of the global prefixes that are most frequently used through the corresponding border router;

mapping, by each border router, respective context IDs to the respective set of global prefixes;

distributing the respective context IDs from each border router into the local computer network; and

resolving any conflicts between the respective context IDs from each border router.

6. The method as in claim 5, wherein resolving a particular conflict comprises:

relinquishing a mapped context ID having a lowest frequency of use among the plurality of border routers.

7. The method as in claim 1, further comprising:

disabling use of a particular context ID in the local computer network in response to a cost of the particular context ID exceeding its benefit.

8. The method as in claim 1, further comprising:

remapping the context IDs after a length of time.

9. The method as in claim 1, wherein global prefixes comprise Internet Protocol version 6 (IPv6) addresses.

10. The method as in claim 9, wherein context IDs comprise IPv6 over Low power Wireless Personal Area Networks (6LoWPAN) context IDs.

11. The method as in claim 1, wherein characterizing the use of the one or more global prefixes of the traffic and determining the particular set of the global prefixes that are most frequently used comprises an algorithm selected from a group consisting of a frequency-counting algorithm and a Huffman coding algorithm.

12. The method as in claim 1, wherein distributing the context IDs into the local computer network comprises:

piggybacking the context IDs within network topology discovery messages distributed within the local computer network.

13. The method as in claim 1, wherein distributing the context IDs into the local computer network comprises:

relaying the context IDs within dynamic host configuration protocol (DHCP) messages within the local computer network.

14. The method as in claim 1, further comprising:

adjusting the number of global prefixes that can be mapped into context IDs.

15. An apparatus, comprising:

one or more network interfaces to communicate as a border router between a local computer network and a global computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a border router process executable by the processor, the process when executed operable to;

monitor routable traffic through the border router between the local computer and the global computer network;

characterize use of one or more global prefixes of the traffic;

determine a number of global prefixes that can be mapped into context identifiers (IDs) having a shorter bit-length than the global prefixes;

determine, up to the number, a particular set of the global prefixes that are most frequently used;

map the context IDs to the particular set of global prefixes;

distribute the context IDs into the local computer network; and

convert between the context IDs and the global prefixes at the border router.

16. The apparatus as in claim 15, wherein there are a plurality of border routers between the local and global computer networks, and wherein the process when executed is further operable to:

characterize use of one or more global prefixes of the traffic based on shared knowledge of the traffic through the plurality of border routers.

17. The apparatus as in claim 16, wherein the process when executed is further operable to:

determine, as a primary border router of the plurality of border routers, the particular set of the global prefixes that are most frequently used based on the traffic through the plurality of border routers;

map, by the primary border router, the context IDs to the particular set of global prefixes; and

distribute the context IDs from the primary border router into the local computer network, wherein the plurality of border routers are configured to convert between the context IDs and the global prefixes.

18. The apparatus as in claim 16, wherein the process when executed is further operable to:

determine, via a deterministic function shared by the plurality of border routers, the particular set of the global prefixes that are most frequently used based on the traffic through the plurality of border routers; and

map the context IDs to the particular set of global prefixes using the deterministic function.

19. The apparatus as in claim 15, wherein there are a plurality of border routers between the local and global computer networks, and wherein the process when executed is further operable to:

resolve any conflicts between the mapped context IDs and other mapped context IDs from other border routers of the plurality of border routers.

20. The apparatus as in claim 19, wherein the process when executed to resolve a particular conflict is further operable to:

relinquish a mapped context ID having a lowest frequency of use among the plurality of border routers.

21. The apparatus as in claim 15, wherein the process when executed is further operable to:

remap the context IDs after a length of time.

22. The apparatus as in claim 15, wherein the process when executed to distribute the context IDs into the local computer network is further operable to one of either:

piggyback the context IDs within network topology discovery messages distributed within the local computer network; and

relaying the context IDs within dynamic host configuration protocol (DHCP) messages within the local computer network.

23. The apparatus as in claim 15, wherein the process when executed is further operable to:

adjust the number of global prefixes that can be mapped into context IDs.

24. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

monitor routable traffic through a border router between a local computer network and a global computer network;

characterize use of one or more global prefixes of the traffic;

determine a number of global prefixes that can be mapped into context identifiers (IDs) having a shorter bit-length than the global prefixes;

determine, up to the number, a particular set of the global prefixes that are most frequently used;

map the context IDs to the particular set of global prefixes;

distribute the context IDs into the local computer network; and

convert between the context IDs and the global prefixes.