Granted Patent B2

US 8,964,565 · App. 13/698,511 · Granted Feb 24, 2015

Abstract

Claims (43)

1. A method comprising:

creating an update message at a first node of a network, the update message including first routing information for updating a routing information base of a peer of the first node, said first routing information including,

at least one path to a first destination node of a number of destination nodes, said at least one path including a next hop node that is adjacent to the first node, and

at least one routing topology variable derived from the at least one path to said first destination node, said at least one routing topology variable indicating a risk of bottlenecks in the at least one path, the risk of bottleneck being based on a failure of transmission by one or more nodes on the at least one path; and

sending the update message to the peer of the first node, the peer of the first node determining a path for communication with another node based on at least the update message received from the first node.

2. The method of claim 1 , wherein the at least one routing topology variable is derived from the at least one path to said first destination.

3. The method of claim 1 , wherein said at least one routing topology variable comprises at least one of,

a diversity variable related to the at least one path in the first routing information base for said first destination node; and

a concentration variable related to the at least one path in the first routing information base having the same next-hop node as the selected path for the first destination node.

4. The method of claim 3 , wherein

said peer of the first node has a routing information base, and

said peer of the first node updates the routing information base of said peer based on the at least one topology variable received from the first node.

5. The method of claim 1 , wherein,

the first node and the peer are Border Gateway Protocol (BGP) routers,

the routing information base of the first node and it's the peer each includes,

a first part (Adj-RIBS-In) configured to store routing information from inbound update messages;

a second part (Loc-RIB) configured to store selected local routing information, and

a third part (Adj-RIBs-Out) configured to store the routing information to be included in outbound update message,

the selected path contained in the update message sent by the first node is stored in the first part, and

the second part and the third part are updated based on the at least one topology variable contained in the update message.

6. The method of claim 3 , wherein the diversity variable is related to the at least one path in a first part of the first routing information base for said first destination node, the first part (Adj-RIBs-In) configured to store routing information from inbound update messages.

7. The method of claim 6 , wherein a concentration variable is related to the number of paths stored in the second part of the first routing information base having the same next-hop node as the selected path for the destination node.

8. The method of claim 3 , wherein,

the update message is a Border Gateway Protocol (BGP) update message comprising an AS_Path attribute with the selected path, and

the diversity and concentration variable are encoded as a vector matching the AS_Path attribute.

9. The method of claim 1 , wherein,

each node of the network sends update messages as defined in claim 1 , and

the update message sent by each node also includes the at least one topology variable received from a corresponding peer if said peer is present in the selected path for said first destination.

10. The method of claim 9 , wherein the update message sent by each node also includes the at least one topology variable from each node present in the selected path as received through a corresponding peer present in the selected path.

11. A router comprising:

a routing information base including, for each destination node of a number of destination nodes of a network, at least one path, the router being configured to,

create an update message, the update message including first routing information for updating a routing information base of a peer of the router, the first routing information including,

at least one path to a first destination node of a number of destination nodes, said at least one path including a next hop node that is adjacent to the router, and

at least one routing topology variable derived from the at least one path to said first destination node, said at least one routing topology variable indicating a risk of bottlenecks in the at least one path, the risk of bottleneck being based on a failure of transmission by one or more nodes on the at least one path, and

send the update message to the peer of the router, the peer of the router determining a path for communication with another node based on at least the update message received from the router.

12. The router of claim 11 , wherein the at least one routing topology variable comprises at least one of,

a diversity variable related to the at least one path in the first routing information base for the first destination node; and

a concentration variable related to the at least one path in the first routing information base having the same next hop as the selected path for the first destination node.

13. The router of claim 11 , wherein the router further comprises:

a processor configured to process information in the router information base, and update the routing information base based on the at least routing topology variable.

14. The router of claim 11 , wherein,

the router is a Border Gateway Protocol (BGP) router; and

the routing information base comprises a Loc-RIB part, an Adj-RIB-In part and an Adj-RIB-Out part.

Assignments (10)