Implicit Withdrawal - BGP Update Message

Hi Ado,

It will also depend on whether your update messages are immediately
preceded by a BGP session state change for a given peer IP
(transitioning to state 6 (established)).

If the session has just reset, then the first message you see for a
{peer,prefix} is an announce, and subsequent announces (for the same
{peer,prefix} but a different path) are implicit withdrawals.

But if you just analyze a batch of RIS update files for a given time
window, it is not correct to assume that the first message for a
{peer,prefix} is a new announce. You'd need to load the RIB dump (bview)
from just before your time window, to establish if the prefix was
already in the RIB, to determine if the first announce you see is a new
announce or also an implicit withdrawal.

You'll also need to take into account, the session resets that occur
during your time window. If a state change occurs, that will also
effectively withdraw all the prefixes already received from that peer.

Cheers,
Colin

On 11/10/15 14:03, Maurizio Patrignani wrote:
> Dear Ado,
> 
>    the term "implicit withdrawal" applies to a BGP update U_2 that comes
> to a BGP speaker from the same peer P that sent a previous update U_1.
> When the peer P sends the second update U_2, the meaning is that the
> previous update U_1 is implicitly withdrawn by P and replaced with U_2.
> In other words, the sequence U_1, U_2 has the same effect of U_1,
> Withdrawal, U_2.    
>    The four BGP announcements that you list in your email do not come
> all from the same peer of router 192.65.185.40. However, the third
> announcement (FROM: 192.65.185.144, AS_PATH: 6893 3561 209 297) is an
> implicit withdrawal of the first (FROM: 192.65.185.144, AS_PATH: 6893
> 8938 1 297). There is only one implicit withdrawal in the sequence.
>    After all four announcements are received by router 192.65.185.40,
> router 192.65.185.40 has to choose its best route to prefix
> 192.152.102.0/24. The choice is among the 2nd, 3rd and 4th route, since
> the 1st announcement is implicitly withdrawn by the 3rd.
> 
> Best,
> Maurizio
> 
> On 10/11/2015 12:26 PM, Ado Maja wrote:
>> Dear all,
>> I am trying to account for all implicit withdrawal messages within a
>> certain period of time looking at BGP update messages collected at
>> rrc, Ripe. 
>> Implicit Withdrawal Definition: If the sender announces a route to a
>> currently reachable address and the new route is identical to the
>> current route, this is a duplicate announcement. Otherwise, the sender
>> is replacing the current route with a new route and this is an
>> implicit withdrawal. (Wang et al. in the "Observation and Analysis of
>> BGP iBehavior under Stress")
>>  
>> What I am trying to understand is how do I count implicit withdrawals?
>> If for example, I have 4 BGP messages shown below that have same IP
>> address and different AS-PATH attribute, how many implicit withdrawals
>> do I have? Is it 3? If I look at consecutive messages that have same
>> IP address and different AS-PATH attribute the result would be 3 (I
>> compare first to the second, second to the third and third to the
>> fourth – assuming they have same IP address and different AS-PATH I
>> increment implicit withdrawals). But I have come across a solution
>> that takes a first message and compares it to the rest of the
>> messages. Than second message compares to the rest of the messages.
>> And lastly compares the third to the fourth. In this case number of
>> implicit withdrawals is 6. Please advise.
>> Thanks for your help.
>> TIME: 2001-9-16 00:00:06
>> TYPE: BGP4MP/BGP4MP_MESSAGE AFI_IP
>> FROM: 192.65.185.144
>> TO: 192.65.185.40
>> BGP PACKET TYPE: UPDATE
>> ORIGIN: IGP
>> AS_PATH: 6893 8938 1 297
>> NEXT_HOP: 192.65.185.144
>> ANNOUNCED: 192.152.102.0/24
>>  
>> TIME: 2001-9-16 00:00:18
>> TYPE: BGP4MP/BGP4MP_MESSAGE AFI_IP
>> FROM: 192.65.184.3
>> TO: 192.65.185.40
>> BGP PACKET TYPE: UPDATE
>> ORIGIN: IGP
>> AS_PATH: 513 10764 6509 297
>> NEXT_HOP: 192.65.185.9
>> ANNOUNCED: 192.152.102.0/24
>>  
>> TIME: 2001-9-16 00:00:36
>> TYPE: BGP4MP/BGP4MP_MESSAGE AFI_IP
>> FROM: 192.65.185.144
>> TO: 192.65.185.40
>> BGP PACKET TYPE: UPDATE
>> ORIGIN: IGP
>> AS_PATH: 6893 3561 209 297
>> NEXT_HOP: 192.65.185.144
>> ANNOUNCED: 192.152.102.0/24
>>  
>> TIME: 2001-9-16 00:00:44
>> TYPE: BGP4MP/BGP4MP_MESSAGE AFI_IP
>> FROM: 192.65.185.130
>> TO: 192.65.185.40
>> BGP PACKET TYPE: UPDATE
>> ORIGIN: IGP
>> AS_PATH: 559 8933 6509 297
>> NEXT_HOP: 192.65.185.130
>> ANNOUNCED: 192.152.102.0/24
> 
> 
> -- 
> Maurizio "Titto" Patrignani
> Dipartimento di Ingegneria, Universita' Roma Tre
> Tel +39.06.57333233, Fax +39.06.57333612
> http://www.dia.uniroma3.it/~patrigna
> 

-- 
Colin Petrie
Systems Engineer
RIPE NCC