[rbridge] a stronger RPF check for TRILL

Santosh Rajagopalan <sunny.rajagopalan@us.ibm.com> Thu, 08 March 2012 17:56 UTC

Return-Path: <rbridge-bounces@postel.org>
X-Original-To: ietfarch-trill-archive-Osh9cae4@ietfa.amsl.com
Delivered-To: ietfarch-trill-archive-Osh9cae4@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 5779D21F86B1 for <ietfarch-trill-archive-Osh9cae4@ietfa.amsl.com>; Thu, 8 Mar 2012 09:56:26 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.854
X-Spam-Status: No, score=-5.854 tagged_above=-999 required=5 tests=[AWL=-0.744, BAYES_05=-1.11, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-4]
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id rSnazDDdv5Lw for <ietfarch-trill-archive-Osh9cae4@ietfa.amsl.com>; Thu, 8 Mar 2012 09:56:25 -0800 (PST)
Received: from boreas.isi.edu (boreas.isi.edu []) by ietfa.amsl.com (Postfix) with ESMTP id 5D7A221F8682 for <trill-archive-Osh9cae4@lists.ietf.org>; Thu, 8 Mar 2012 09:56:25 -0800 (PST)
Received: from boreas.isi.edu (localhost []) by boreas.isi.edu (8.13.8/8.13.8) with ESMTP id q28Hhke4025611; Thu, 8 Mar 2012 09:43:47 -0800 (PST)
Received: from e34.co.us.ibm.com (e34.co.us.ibm.com []) by boreas.isi.edu (8.13.8/8.13.8) with ESMTP id q28HhO33025220 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <rbridge@postel.org>; Thu, 8 Mar 2012 09:43:33 -0800 (PST)
Received: from /spool/local by e34.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for <rbridge@postel.org> from <sunny.rajagopalan@us.ibm.com>; Thu, 8 Mar 2012 10:43:23 -0700
Received: from d03dlp01.boulder.ibm.com ( by e34.co.us.ibm.com ( with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Thu, 8 Mar 2012 10:43:20 -0700
Received: from d03relay02.boulder.ibm.com (d03relay02.boulder.ibm.com []) by d03dlp01.boulder.ibm.com (Postfix) with ESMTP id A5E5BC40007 for <rbridge@postel.org>; Thu, 8 Mar 2012 10:43:18 -0700 (MST)
Received: from d03av05.boulder.ibm.com (d03av05.boulder.ibm.com []) by d03relay02.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id q28HhAlt141414 for <rbridge@postel.org>; Thu, 8 Mar 2012 10:43:13 -0700
Received: from d03av05.boulder.ibm.com (loopback []) by d03av05.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id q28Hh9xm029062 for <rbridge@postel.org>; Thu, 8 Mar 2012 10:43:10 -0700
Received: from d03nm127.boulder.ibm.com (d03nm127.boulder.ibm.com []) by d03av05.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with ESMTP id q28Hh0cf028499 for <rbridge@postel.org>; Thu, 8 Mar 2012 10:43:00 -0700
X-KeepSent: 717BEAAE:B04DF3B2-872579BB:00608789; type=4; name=$KeepSent
To: rbridge@postel.org
X-Mailer: Lotus Notes Release 8.5.1FP5 SHF29 November 12, 2010
Message-ID: <OF717BEAAE.B04DF3B2-ON872579BB.00608789-882579BB.00615D1A@us.ibm.com>
From: Santosh Rajagopalan <sunny.rajagopalan@us.ibm.com>
Date: Thu, 08 Mar 2012 09:43:00 -0800
X-MIMETrack: Serialize by Router on D03NM127/03/M/IBM(Release 8.5.1FP2|March 17, 2010) at 03/08/2012 10:42:59
MIME-Version: 1.0
X-Content-Scanned: Fidelis XPS MAILER
x-cbid: 12030817-1780-0000-0000-000003D17D4D
X-IBM-ISS-DetailInfo: BY=3.00000256; HX=3.00000185; KW=3.00000007; PH=3.00000001; SC=3.00000001; SDB=6.00120280; UDB=6.00029083; UTC=2012-03-08 17:43:21
X-ISI-4-43-8-MailScanner: Found to be clean
X-MailScanner-From: sunny.rajagopalan@us.ibm.com
Subject: [rbridge] a stronger RPF check for TRILL
X-BeenThere: rbridge@postel.org
X-Mailman-Version: 2.1.6
Precedence: list
List-Id: "Developing a hybrid router/bridge." <rbridge.postel.org>
List-Unsubscribe: <http://mailman.postel.org/mailman/listinfo/rbridge>, <mailto:rbridge-request@postel.org?subject=unsubscribe>
List-Archive: <http://mailman.postel.org/pipermail/rbridge>
List-Post: <mailto:rbridge@postel.org>
List-Help: <mailto:rbridge-request@postel.org?subject=help>
List-Subscribe: <http://mailman.postel.org/mailman/listinfo/rbridge>, <mailto:rbridge-request@postel.org?subject=subscribe>
Content-Type: multipart/mixed; boundary="===============0861243034=="
Sender: rbridge-bounces@postel.org
Errors-To: rbridge-bounces@postel.org

It appears the the multidestination frame checks present in TRILL may not
be strong enough to cover some cases of packet duplicates during network
transition scenarios. In this email, I'm going to suggest a modification of
the TRILL RPF check to cover these cases.

The root problem is that there's a notion of directionality built into the
RPF concept ("accept packets from X along this vector"). In a p2p link,
specifying the port alone uniquely qualifies that vector. However, in a
multiaccess link, there are many "links/adjacencies" overlaid on the
physical link. To identify one of them, you need to specify both the
outer_smac *and* the port. So the RPF check should actually be "accept
packets from X along (outer_smac, port)".

Consider this network:

All the links except the link between C and D are p2p links. C and D are
connected over a classical ethernet network (represented by the pseudonode
"o"). Let's say D gets picked as the root for a multidestination tree (the
choice of root is unimportant here).
The resulting tree looks like:


Now lets say that a link comes up from A to the same classical ethernet
network. So the network looks like this:
     |                 |

Let's say the resulting tree in steady state includes all links except the
B-C link. After the network has converged, a packet that starts out from F
will go F->A, where A will send one copy to the A-B link and another copy
into the CE network, from where it will be received by C and D.

However, lets consider a transition stage where A and D have acted on their
LSPs and programmed their forwarding plane, while B and C have not yet done
This means that B and C both consider the link between them to still be
part of the tree.

So a packet that starts out from F and reaches A will be copied by A into
the A-B link and the A-o link. D's RPF check says to accept packets on this
tree coming from F over its link to the CE network, so it gets accepted. D
is also adjacent to A on the tree, so the tree adjacency check also passes.

However, the packet that gets to B gets sent out by B to C. C's RPF check
still has the old state, and it thinks the packet is ok. C sends the packet
along the old tree, which is towards the CE network. D receives one more
packet, but the tree adjacency check passes because C is adjacent to D in
the new tree as well. The RPF check also passes because D's link to the CE
network is ok for receiving packets from A.

So now D gets duplicates of every packet until B and C act on their LSPs
and program their hardware tables. The AF state is (I believe) irrelevant
here because we're talking about TRILL encapsulated packets, not native CE

In the example above, the adjacency check alone doesn't help, because the
rbridge D has adjacencies to both A & C on the tree. A check on (port,
smac) will pass for packets from both A and C.

The only check which can stop this from happening, I believe, is if you
replace the current RPF check which looks like this:
{tree_id, source_rbridge}->{allowed_port}

with a modified check which looks like this:

{tree_id, rbridge}->{allowed_port, allowed_outer_smac}

This will make sure that packets will be accepted by D only if they were
sent by A. This combined check can be a replacement for the currently
separate adjacency and RPF checks.

Sunny Rajagopalan
rbridge mailing list