Routing messages in a computer network using deterministic and probabilistic source routes

• US 9,112,805 B2
• Filed: 09/28/2012
• Issued: 08/18/2015
• Est. Priority Date: 09/28/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Hong, Wei, Vasseur, Jean-Philippe
• Primary Examiner(s): Zhou, Yong
• Application Number:
  US13/631,064
• Publication Number:
  US 20140092905A1
• Time in Patent Office: 1,054 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 2101/659 Internet protocol version 6 [IPv6] addresses
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

In one embodiment, a data packet message is provided which includes a routing header configured to accommodate both a deterministic source route and a probabilistic source route for encoding a nodal source route. The nodal source route is selectively encoded with one or both of a deterministic source route and a probabilistic source route based upon one or more predetermined criteria.

Claims

1. A method, comprising:

providing a message having a routing header configured to accommodate both a deterministic source route and a probabilistic source route for encoding a nodal source route for the message in a computer network; and

selectively encoding the nodal source route with one or both of a deterministic source route and a probabilistic source route based upon one or more predetermined criteria, wherein the nodal source route is encoded with a deterministic source route when it is determined an estimated cost of false positives attributable to a Bloom filter is above a certain threshold.

2. The method of claim 1 wherein the deterministic source route includes an IPv6 address.

3. The method of claim 1 wherein the routing header includes one or more of the following fields:

(a) a path length field indicative of the number of entries of the source route;

(b) a current position field which is incremented by each router of a nodal path;

(c) a Bloom filter integer K indicative of the number of hash functions to use for the Bloom filter; and

(d) a Bloom filter bit-vector field for encoding a Bloom filter.

4. The method of claim 1 wherein the probabilistic source route includes a bloom filter.

5. The method of claim 1 wherein the selectively encoding step includes encoding the nodal source route with a Bloom filter when it is determined an estimated cost of false positives attributable to a Bloom filter is below a certain threshold.

6. The method of claim 1 wherein the message having the router header is a proactive routing protocol advertisement message.

7. A method, comprising:

receiving a message in a computer network having a routing header configured to accommodate both a deterministic source route and a probabilistic source route for encoding a nodal source route for the message;

determining whether the message has a deterministic source route in the route header;

in response to the message not having a deterministic source route, interpolating a probabilistic source route and forwarding the message based on the interpolation, wherein the probabilistic source route includes a Bloom filter; and

in response to the message having a deterministic source route for all nodal devices along a nodal path, eliminating the Bloom filter from the routing header and forwarding the message according to the deterministic source route.

8. The method of claim 7 further comprising the step of forwarding the message according to the probabilistic source route in response to instructions to eliminate deterministic explicit identifiers from a deterministic source route in the routing header to reduce signal overhead.

9. The method of claim 7 further comprising the step of forwarding the message according to the probabilistic source route when the message is near an end portion of a nodal path in the computer network.

10. The method of claim 7 further comprising the step of forwarding the message according to the probabilistic source route when a number of neighboring nodal devices is below a threshold.

11. The method of claim 7 further comprising the step of forwarding the message according to the probabilistic source route conditional upon feedback regarding the occurrence of false positives attributable to a Bloom filter provided in the probabilistic source route.

12. The method of claim 7 further comprising the step of including an explicit identifier in the deterministic source route in the routing header every Nth nodal hop of the message along a signal nodal path where N is an integer.

13. The method of claim 7 further comprising the step of determining if a deterministic source route includes an explicit identifier for a next message route hop, and if yes, use the determined explicit identifier for forwarding message along the next message route hop.

14. The method of claim 7 further comprising the step of querying a Bloom filter present in probabilistic source route for each neighbor node along the nodal path for forwarding the message along the nodal path if it is determined the deterministic source route does not include an explicit identifier for a next signal route hop along the nodal path.

15. The method of claim 7 wherein the message having the router header is a proactive routing protocol advertisement message.

16. An apparatus, comprising:

one or more network interfaces to communicate with a computer network;

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

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

provide a message having a routing header configured to accommodate both a deterministic source route and a probabilistic source route for encoding a nodal source route for the message in the computer network; and

selectively encode the nodal source route with one or both of a deterministic source route and a probabilistic source route based upon one or more predetermined criteria;

wherein the processor is operative to encode the nodal source route with a deterministic source route when it is determined an estimated cost of false positives attributable to a Bloom filter is above a certain threshold.

17. The apparatus as in claim 16, wherein the deterministic source route includes an IPv6 address and the probabilistic source route includes a Bloom filter.

18. The apparatus as in claim 16, wherein the processor is operative to encode the nodal source route with a Bloom filter when it is determined an estimated cost of false positives attributable to a Bloom filter is below a certain threshold.

19. An apparatus, comprising:

one or more network interfaces to communicate with a computer network;

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

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

receive a message in the computer network having a routing header configured to accommodate both a deterministic source route and a probabilistic source route for encoding a nodal source route for the message;

determine whether the message has a deterministic source route in the routing header; and

in response to the received message not having a deterministic source route, interpolate a probabilistic source route and forwarding the message based on the interpolation,

wherein in response to the received message having a deterministic source route for all nodal devices along a nodal path, the processor is configured to eliminate the Bloom filter from the routing header and forward the message according to the deterministic source route.