# US 2012/0254465 A1 · Method and system for improved routing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254465 A1
- Document ID: US20120254465A1
- Status: Published application
- Kind: A1
- Application number: 13/515,455
- Filed: 2010-12-20
- Published: 2012-10-04
- Earliest claimed: 2010-01-04
- Assignees: Alcatel Lucent
- Inventors: Dimitri Papadimitriou
- Web page: https://patentgrep.com/patent/US20120254465A1

## CPC

- H04L 45/14: {Routing performance; Theoretical aspects}
- H04L 45/033: by updating distance vector protocols
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 5, 6)

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

### Claim 8 (depends on 2)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 3)

Method of claim 3, wherein the HMM uses:
a number N of preferably at least 4 hidden states Si 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 aij=P(qj, t+1|qi, t) with 1≦i, j≦N;
wherein P(qj, t+1|qi, t) is the probability that the actual state at time t+1 is equal to Sj, and that the 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|qj, t) being the probability of emitting the observation O at time t in the actual state qj at time t.
an initial state distribution πi=P(qi, 1) with 1≦i≦N, P(qi, 1) being the probability of having an initial state Si.

### Claim 11 (depends on 10)

Method of claim 10, wherein the number of states comprise:
a first state S1 indicating that there is no change in the path;
a second state S2 indicating a re-initialization;
a third state S3 indicating an increase of the path length;
a fourth state S4 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.

### Claim 12 (depends on 10)

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 A0 of a destination with a different path of the same length;
a withdrawal W(A) of a path A for a given destination.

### Claim 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.

### Claim 14 (depends on 10, 11, 12, 13)

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.

### Claim 15 (depends on 14)

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.
