Subject: [GROW] Implicit Withdrawal - BGP Update Message

From: Ado Maja <[email-masked]>
Date: Sun, 11 Oct 2015 10:12:32 +0000 (UTC)

Dear all,

I am trying to account for all implicitwithdrawal messages within a certain period of time looking at BGP updatemessages collected at rrc, Ripe. 

Implicit Withdrawal Definition:If the sender announces a route to a currently reachable address and the newroute is identical to the current route, this is a duplicate announcement.Otherwise, the sender is replacing the current route with a new route and thisis an implicit withdrawal. (Wanget al. in the "Observation and Analysis of BGP iBehavior underStress")

 What I am trying to understand is how do Icount implicit withdrawals? If for example, I have 4 BGP messages shown belowthat have same IP address and different AS-PATH attribute, how many implicitwithdrawals do I have? Is it 3? If I look at consecutive messages that havesame IP address and different AS-PATH attribute the result would be 3 (Icompare 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 implicitwithdrawals). But I have come across a solution that takes a first message andcompares it to the rest of the messages. Than second message compares to therest of the messages. And lastly compares the third to the fourth. In this casenumber of implicit withdrawals is 6. Please advise. 

Thanks for your help.

TIME: 2001-9-16 00:00:06

TYPE: BGP4MP/BGP4MP_MESSAGEAFI_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_MESSAGEAFI_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_MESSAGEAFI_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_MESSAGEAFI_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

---

From: Jeffrey Haas <[email-masked]>
Date: Mon, 12 Oct 2015 12:21:48 -0400

Ado,

On Sun, Oct 11, 2015 at 10:12:32AM +0000, Ado Maja wrote:
>  What I am trying to understand is how do Icount implicit withdrawals? If
> for example, I have 4 BGP messages shown belowthat have same IP address
> and different AS-PATH attribute, how many implicitwithdrawals do I have?
> Is it 3? If I look at consecutive messages that havesame IP address and
> different AS-PATH attribute the result would be 3 (Icompare 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 implicitwithdrawals).
> But I have come across a solution that takes a first message andcompares
> it to the rest of the messages. Than second message compares to therest of
> the messages. And lastly compares the third to the fourth. In this
> casenumber of implicit withdrawals is 6. Please advise. 

Remember that the implicit withdrawal is from the perspective of a given
peer; i.e. for a given Adj-Rib-In.  Thus, don't count things from different
peers as implicit withdrawals.

My bigger comment is that implicit withdrawals have the context that you
know when the *first* update containing that prefix has been done.  You're
not going to get this 100% cleanly from the MRT data without a heuristic of
"this is my time 0" for comparison.  My recommendation is to not trying to
categorize the updates as "implicit withdrawals"; instead simply count them
as updates against the same prefix.  You don't have enough information to
determine why the upstream router sent the update (policy, path selection,
an actual withdraw further upstream).

-- Jeff