Systems and methods for predictive routing

• US 6,850,524 B1
• Filed: 07/31/2000
• Issued: 02/01/2005
• Est. Priority Date: 07/31/2000
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications Incorporated (Lumen Technologies, Inc.)
• Inventors: Troxel, Gregory Donald, Wiggins, David Paul
• Primary Examiner(s): Vanderpuye, Kenneth
• Assistant Examiner(s): NGUYEN, VAN KIM T
• Application Number:
  US09/630,304
• Time in Patent Office: 1,646 Days
• Field of Search: 370230-231, 370/338, 370351-355, 3703952-39532, 370400-402
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458

Abstract

A system provides predictive routing of packets in a network with multiple nodes. The system receives messages from the nodes (740). The messages contain predictions regarding future events that may happen to entities associated with the nodes. The system extracts the predictions from the received messages (750), determines active states of the entities based on the predictions (750), and generates a routing table using the active states of the entities (760). The system uses the routing table to route packets through the network.

Claims

1. A method for predictive routing of packets by a node in a network having a plurality of nodes, comprising:

receiving messages from advertising nodes in the network, at least one of the messages containing a prediction regarding a future event that may happen to an entity associated with a corresponding advertising node;

extracting the prediction from the received message;

determining an active state of the entity based on the prediction;

generating a routing table using the active state of the entity; and

routing packets through the network using the routing table.

2. The method of claim 1, wherein the receiving includes:

receiving at least two messages containing predictions from one of the advertising nodes, and

merging the at least two messages.

3. The method of claim 1, wherein the entity includes one of the advertising node, an interface associated with the advertising node, or a relationship existing between the advertising node and another one of the nodes in the network;

and

wherein the receiving includes;

receiving, from the advertising node, a message that includes predictions regarding a plurality of different entities.

4. The method of claim 1, wherein the receiving includes:

receiving at least one message that includes a plurality of predictions relating to a plurality of entities.

5. The method of claim 4, wherein the extracting includes:

decoding the at least one message to obtain a prediction corresponding to each of the entities.

6. The method of claim 1, wherein the extracting includes:

decoding the received message to obtain a prediction function corresponding to the entity.

7. The method of claim 6, wherein the determining includes:

applying a time value, corresponding to a future time, to the prediction function to determine the active state of the entity at the future time.

8. The method of claim 7, wherein the generating includes:

recomputing the routing table for each of a plurality of time values.

9. The method of claim 6, wherein the determining includes:

applying a plurality of time values, corresponding to a time interval, to the prediction function to determine cost values associated with the entity for the time interval, and

using the cost values to identify the active state of the entity for the time interval.

10. The method of claim 9, wherein the using includes:

identifying a worst cost value from the determined cost values, and using the worst cost value as the active state of the entity for the time interval.

11. The method of claim 9, wherein the generating includes:

recomputing the routing table, and

installing the recomputed routing table at the end of each of a plurality of time intervals.

12. The method of claim 1, wherein the generating includes:

recomputing the routing table upon changes to the active state of the entity.

13. A system for generating a routing table for predictive routing of packets in a network having a plurality of nodes, comprising:

means for obtaining messages from nodes in the network, the messages containing predictions regarding future events that may happen to entities associated with corresponding ones of the nodes;

means for extracting the predictions from the messages;

means for determining active states of the entities based on the predictions; and

means for generating a routing table, using the active states of the entities, for routing packets through the network.

14. A node in a network having a plurality of nodes, comprising:

a memory configured to store a routing table; and

a processor configured to receive messages from other nodes in the network, the messages containing predictions regarding future events that may happen to entities associated with corresponding ones of the other nodes, extract the predictions from the received messages, determine active states of the entities based on the predictions, recompute the routing table in the memory using the active states of the entities, and send packets through the network using the routing table.

15. The node of claim 14, wherein the processor is configured to obtain at least two messages containing predictions from a same one of the other nodes and merge the at least two messages.

16. The node of claim 14, wherein each of the entities includes one of the corresponding other node, an interface associated with the corresponding other node, and a relationship existing between the corresponding other node or one of the other nodes in the network.

17. The node of claim 16, wherein the processor is configured to obtain, from a same one of the other nodes, a message that includes predictions regarding a plurality of different entities.

18. The node of claim 14, wherein the processor is configured to receive at least one message that includes a plurality of predictions relating to a plurality of entities and decode the at least one message to obtain a prediction corresponding to each of the entities.

19. The node of claim 14, wherein the processor is configured to decode the received messages to obtain prediction functions corresponding to the entities.

20. The node of claim 19, wherein the processor is configured to apply a time value, corresponding to a future time, to each of the prediction functions to determine the active state of the corresponding entity at the future time.

21. The node of claim 20, wherein the processor is configured to recompute the routing table for each of a plurality of time values.

22. The node of claim 19, wherein the processor is configured to apply a plurality of time values, corresponding to a time interval, to each of the prediction functions to determine cost values associated with the corresponding entity for the time interval, and use the cost values to identify the active state of the corresponding entity for the time interval.

23. The node of claim 22, wherein the processor is configured to identify a worst cost value from the determined cost values and use the worst cost value as the active state of the corresponding entity for the time interval.

24. The node of claim 22, wherein the processor is configured to recompute the routing table and install the recomputed routing table at the end of each of a plurality of time intervals.

25. The node of claim 14, wherein the processor is configured to recompute the routing table upon changes to the active states of the entities.

26. The node of claim 14, wherein the processor is further configured to generate messages that include predictions regarding at least one entity.

27. The node of claim 26, wherein at least one of the generated messages includes at least one of an event piece, a peer prediction piece, an interface prediction piece, or a node prediction piece.

28. The node of claim 27, wherein the event piece includes:

an event type that indicates a predicted event for the entity, and

an event time that indicates a time at which the predicted event may occur.

29. The node of claim 27, wherein the peer prediction piece includes:

a peer address that indicates an address of one of the other nodes, and

at least one event piece that indicates predicted events for the other node.

30. The node of claim 27, wherein the interface prediction piece includes:

an interface address that indicates an address of an interface associated with the node, and

at least one event piece that indicates predicted events for the interface.

31. The node of claim 27, wherein the node prediction piece includes:

at least one node event piece that indicates predicted events for the node.

32. The node of claim 26, wherein the processor is further configured to transmit the generated messages on the network.

33. A computer-readable medium storing instructions for causing at least one processor to perform a method for generating a routing table for predictive routing of packets in a network having a plurality of routers, the method comprising:

extracting predictions from messages received from routers in the network, the predictions identifying future events that may happen to entities associated with corresponding ones of the routers;

determining active states of the entities based on the predictions; and

generating a routing table, using the active states of the entities, for routing packets in the network.

34. A method for generating prediction messages for predictive routing of packets in a network having a plurality of nodes, the method, performed by at least one of the nodes, comprising:

generating predictions relating to at least one entity associated with the node, wherein the generating predictions includes;

creating a prediction that specifies a future event that may occur to at least one of the node, an interface associated with the node, or a relationship between the node and at least one other node;

encoding the predictions into one or more prediction messages; and

flooding the prediction messages on the network.

35. The method of claim 34, wherein the generating includes:

identifying an the future event that may occur to the at least one of the node, an interface associated with the node, or a relationship between the node and at least one other node,

identifying a time at which the future event may occur, and

creating a prediction iron the identified future event and time.

36. The method of claim 34, wherein the encoding includes:

converting each of the predictions into at least one of a node prediction piece, an interface prediction piece, or a peer prediction piece, the node prediction piece specifying one or more future events that may occur to the node, the interface prediction piece specifying one or more future events that may occur to an interface associated with the node, and the peer prediction piece specifying one or more future events that may occur to a relationship between the node and at least one other node, and creating each of the prediction messages from one or more of the node prediction piece, the interface prediction piece, or and the peer prediction piece.

37. The method of claim 34, wherein the flooding includes:

transmitting the prediction messages to all of the nodes in the network.

38. A computer-readable medium containing instructions for causing at least one processor to perform a method for generating prediction messages for predictive routing of packets in a network having a plurality of nodes, the method comprising:

creating predictions relating to at least one entity associated with the processor, wherein the creating predictions includes;

creating a prediction that specifies a future event that may occur to at least one of the entity, an interface associated with the entity, or a relationship between the entity and at least one other entity;

encoding the predictions into one or more prediction messages; and

transmitting the prediction messages on the network.

39. A router in a network having a plurality of routers, comprising:

a memory configured to store instructions; and

a processor configured to execute the instructions in the memory to generate predictions relating to at least one entity associated with the router, encode the predictions into one or more prediction messages, and flood the prediction messages on the network, wherein the processor is configured to create a prediction that specifies a future event that may occur to at least one of the router, an interface associated with the router, or a relationship between the router and at least one other router.

40. The router of claim 39, wherein the processor is configured to identify the future event that may occur to the at least one of the router, an interface associated with the router, or a relationship between the router or at least one other router, identify a time at which the future event may occur, and create a prediction from the identified future event and time.

41. The router of claim 39, wherein the processor is configured to convert each of the predictions into at least one of a router prediction piece, an interface prediction piece, or a peer prediction piece, the router prediction piece specifying one or more future events that may occur to the router, the interface prediction piece specifying one or more future events that may occur to an interface associated with the router, and the peer prediction piece specifying one or more future events that may occur to a relationship between the router and at least one other router, and create each of the prediction messages from one or more of the router prediction piece, the interface prediction piece, or and the peer prediction piece.

42. The router of claim 39, wherein the processor is configured to transmit the prediction messages to all of the routers in the network.

43. The router of claim 39, wherein the processor is further configured to receive messages from other ones of the routers in the network, the messages containing predictions regarding future events that may happen to one or more entities associated with corresponding ones of the routers, extract the predictions from the received messages, and generate a routing table from the extracted predictions.

44. A memory device that stores a prediction data structure, comprising:

a peer prediction piece including a peer event component that indicates a predicted event for a relationship between first and second nodes in a network and an event time component that indicates a time at which the predicted event may occur;

an interface prediction piece including an interface event component that indicates a predicted event for an interface associated with the first node and an event time component that indicates a time at which the predicted event may occur; and

a node prediction piece including a node event component that indicates a predicted event for the first node and an event time component that indicates a time at which the predicted event may occur.