Method and system for improved routing

• US 20120254465A1
• Filed: 12/20/2010
• Published: 10/04/2012
• Est. Priority Date: 01/04/2010
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Papadimitriou, Dimitri
• Granted Patent: US 9,794,166 B2
• Time in Patent Office: Days
• US Class Current: 709/242
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects

Abstract

Method for use in updating a routing table of a router of a plurality of routers, said routing table comprising the route(s) to be used for at least one destination, wherein update messages with routing information are sent between said plurality of routers, typically BGP routers, wherein the following steps are performed at the router: receiving of an update message containing a path or a withdrawal of a path for a destination; determining if the (withdrawn) path is associated with a path exploration event; deciding on the updating of the routing table taking into account the result of the determination.

Claims

1. Method for use in updating a routing table of a router of a plurality of routers, said routing table comprising the route(s) to be used for at least one destination, wherein update messages with routing information are sent between said plurality of routers, typically BGP routers, wherein the following steps are performed at the router:

receiving of an update message containing a path or a withdrawal of a path for a destination;

determining if the (withdrawn) path is associated with a path exploration event;

deciding on the updating of the routing table taking into account the result of the determination.

2. Method of claim 1, wherein the determining uses a generative stochastic signal model.

3. Method of claim 2, wherein the determining uses a Hidden Markov Model (HMM).

4. Method of claim 1, wherein the path exploration event is associated with a number of non-optimal transient paths, and wherein the longest contiguous path sequence of the transient paths, is identified, and wherein the deciding on the updating of the routing table also takes into account said identified sequence for determining whether a path contained in an update message should be selected.

5. Method of claim 1, wherein, if the update message advertises a new path and it is determined that the new path is associated with a path exploration event, the deciding comprises not including the new path in the routing table.

6. Method of claim 1, further comprising the step of:

deciding on routing information to be included in update messages to be sent to other routers, taking into account the result of the determination.

7. Method of claims 5 and 6, wherein, the deciding comprises not including the new path in update messages to be sent to other routers.

8. Method of claim 2, wherein the model uses a plurality of states to model a plurality of communication channels, said plurality of communication channels having outputs being used for selecting the path to be used for the destination;

and wherein the received update messages and information in the routing table are used to provide probabilistic data on the states.

9. Method of claim 1, wherein the router is a BGP router having a number of peers and a Routing Information Base comprising:

an Adj-RIBs-In part storing routing information from inbound update messages;

a Loc-RIB part storing the routing table, i.e. the selected routes, and

an Adj-RIBs-Out part storing the routing information to be included in update messages to be sent to its BGP peers;

wherein the path sequence of the received update message is stored in the Adj-RIBs-In part;

wherein the Loc-RIB part and the Adj-RIBs-Out part are updated taking into account the result of this determination.

10. Method of claim 3, wherein the HMM uses:

a number N of preferably at least 4 hidden states S_i with 1≦

i≦

N, said number of hidden states characterizing routing states of a group of routers upstream of the router, which group is associated with a path exploration event;

a number M of observation symbols O per hidden state, said observation symbols corresponding to the path sequences received in the update messages;

a state transition probability distribution a_ij=P(q_{j, t+1}|q_{i, t}) with 1≦

i, j≦

N;

wherein P(q_{j, t+1}|q_{i, t}) is the probability that the actual state at time t+1 is equal to S_j, and that the preceding actual state at time t was S_i at time t;

an observation probability distribution in state j, b_j (O)=P(O_t|q_{j, t}) with 1≦

j≦

N, P(O_t|q_{j, t}) being the probability of emitting the observation O at time t in the actual state q_j at time t.

an initial state distribution π

_i=P(q_{i, 1}) with 1≦

i≦

N, P(q_{i, 1}) being the probability of having an initial state S_i.

11. Method of claim 10, wherein the number of states comprise:

a first state S₁ indicating that there is no change in the path;

a second state S₂ indicating a re-initialization;

a third state S₃ indicating an increase of the path length;

a fourth state S₄ indicating the presence of a path exploration event;

and optionally a fifth state indicating a withdrawal of a path which is not leading to a path exploration event.

12. Method of claim 10, wherein an update message can comprise an announcement of a path containing a number of path attributes and/or a withdrawal of a path, and wherein the observation symbols comprise:

an announcement A of a destination with no change in path or path attributes;

an announcement A+ of a destination with a path having an increased path length;

an announcement A* of a destination with the same path but different path attributes;

an announcement A⁰ of a destination with a different path of the same length;

a withdrawal W(A) of a path A for a given destination.

14. Router of claim 13, wherein the determining means comprise a stochastic modeling means, preferably a HMM modeling means adapted to function according to the method of any of the claims 10-12.

15. Router of claim 14, wherein the routing table (Loc-RIB) is part of the RIB, the RIB further comprising an Adj-RIB-In for storing the received (withdrawn) path for the destination, and an Adj-RIB-Out;

wherein the decision means are adapted for not storing a new path or a withdrawal of a path in the Loc-RIB and in the Adj-RIB-Out if the new path or the withdrawal is associated with a path exploration event.

13. Router, typically a BGP router, having a routing table comprising the route(s) to be used for at least one destination, wherein the router is adapted to send and receive update messages with routing information, comprising:

receiving means for receiving an update message containing for a destination a path or a withdrawal of a path;

determining means for determining if the (withdrawn) path is associated with a path exploration event;

decision means in communication with the determining means for deciding on the updating of the routing table taking into account the result of the determination.