Method and system for improved routing
First Claim
Patent Images
1. A method for use in updating a routing table of a router of a plurality of routers, the routing table comprising at least one route to be used for at least one destination, wherein update messages with routing information are sent between the plurality of routers wherein at the router the method comprises:
- receiving an update message including path information indicating a new path or a withdrawal of a path for a destination;
determining if the received path information is associated with a path exploration event, the path exploration event is associated with a number of non-optimal transient paths, the determining including using a generative stochastic signal model, the generative stochastic signal model including a Hidden Markov Model (HMM);
identifying a longest contiguous path sequence from the transient paths of the path exploration event;
updating the routing table in accordance with results of the determination and an identified sequence for determining whether the path information contained in the received update message is used; and
generating routing information to be included in update messages to be sent to the other routers of the plurality of routers, in accordance with the result of the determination, wherein the HMM includes,a number N of hidden states Si with 1≦
i≦
N, the 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, the observation symbols corresponding to the path sequences received in the update messages,a state transition probability distribution aij=P(qi,t+1|qi,t) with 1≦
i, j≦
N,wherein P(qi,t+1|qi,t) is the probability that an actual state at time t+1 is equal to Si, and that a preceding actual state at timet was Si at time t,an observation probability distribution in state j, bj(O)=P(Ot|qi,t) with 1≦
j≦
N, P(Ot|qi,t) being a probability of emitting an observation O at time t in an actual state qj at time t, andan initial state distribution π
i=P(qi,1) with 1≦
i≦
N, P(qi,1) being a probability of having an initial state Si.
11 Assignments
0 Petitions
Accused Products
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.
11 Citations
10 Claims
-
1. A method for use in updating a routing table of a router of a plurality of routers, the routing table comprising at least one route to be used for at least one destination, wherein update messages with routing information are sent between the plurality of routers wherein at the router the method comprises:
-
receiving an update message including path information indicating a new path or a withdrawal of a path for a destination; determining if the received path information is associated with a path exploration event, the path exploration event is associated with a number of non-optimal transient paths, the determining including using a generative stochastic signal model, the generative stochastic signal model including a Hidden Markov Model (HMM); identifying a longest contiguous path sequence from the transient paths of the path exploration event; updating the routing table in accordance with results of the determination and an identified sequence for determining whether the path information contained in the received update message is used; and generating routing information to be included in update messages to be sent to the other routers of the plurality of routers, in accordance with the result of the determination, wherein the HMM includes, a number N of hidden states Si with 1≦
i≦
N, the 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, the observation symbols corresponding to the path sequences received in the update messages, a state transition probability distribution aij=P(qi,t+1|qi,t) with 1≦
i, j≦
N,wherein P(qi,t+1|qi,t) is the probability that an actual state at time t+1 is equal to Si, and that a preceding actual state at timet was Si at time t, an observation probability distribution in state j, bj(O)=P(Ot|qi,t) with 1≦
j≦
N, P(Ot|qi,t) being a probability of emitting an observation O at time t in an actual state qj at time t, andan initial state distribution π
i=P(qi,1) with 1≦
i≦
N, P(qi,1) being a probability of having an initial state Si. - View Dependent Claims (2, 3, 4, 5, 6, 7, 9, 10)
-
-
8. A 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:
-
at least one processor, the at least one processor configured to, receive an update message containing path information indicating a new path or a withdrawal of a path for a destination; determine if the received path information is associated with a path exploration event, the path exploration event is associated with a number of non-optimal transient paths, the determination including using a generative stochastic signal model, the generative stochastic signal model including a Hidden Markov Model (HMM); identify a longest contiguous path sequence from the transient paths of the path exploration event; update the routing table in accordance with results of the determination and an identified sequence for determining whether the path information contained in the received update message is used; and a routing information base (RIB) including, a Loc-RIB routing table, an Adj-RIB_In configured to store the received path information, and an Adj-RIB-Out;
whereinthe at least one processor is further configured to not store the received path information in the Loc-RIB routing table and in the Adj-RIB-Out if the received path information is associated with the path exploration event, and the HMM includes, a number N of hidden states Si with 1≦
i≦
N, the 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, the observation symbols corresponding to the path sequences received in the update messages, a state transition probability distribution aij=P(qi,t+1|qi,t) with 1≦
i, j≦
N,wherein P(qi,t+1|qi,t) is a probability that an actual state at time t+1 is equal to Si, and that a preceding actual state at time t was Si at time t, an observation probability distribution in state j, bj(O)=P(Ot|qj,t) with 1≦
j≦
N, P(Ot|qi,t) being a probability of emitting an observation O at time t in an actual state qi at time t, andan initial state distribution π
i=P(qi,1) with 1≦
i≦
N, P(qi,1) being a probability of having an initial state Si.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeRPX Corporation
-
Original AssigneeAlcatel-Lucent SA (Nokia Corporation)
-
InventorsPapadimitriou, Dimitri
-
Primary Examiner(s)Chea, Philip
-
Assistant Examiner(s)Ma, Wing
-
Application NumberUS13/515,455Publication NumberTime in Patent Office2,493 DaysField of Search709242US Class CurrentCPC Class CodesH04L 45/02 Topology update or discoveryH04L 45/033 by updating distance vector...H04L 45/14 Routing performance; Theore...
