Re: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04 Mon, 11 May 2020 17:03 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 821063A0B08 for <>; Mon, 11 May 2020 10:03:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.499
X-Spam-Status: No, score=-1.499 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id fRg-zlidka5d for <>; Mon, 11 May 2020 10:03:24 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::432]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 2EB2E3A0A8B for <>; Mon, 11 May 2020 10:03:19 -0700 (PDT)
Received: by with SMTP id 145so4994540pfw.13 for <>; Mon, 11 May 2020 10:03:19 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=sender:from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=CZDGZ6duRIKsx1Yv99ALabJPXmblXJNBrrN0K0V8yAU=; b=qIGHJmwG7EiAWsOQtsff2ZmPG+bc10k7nllVbU75U5lwI8HZafRL+G05S5wLgoSjk7 IvAHLB65EhZBS+W3FlGHI3v4+rZIRR1dN5S/7kU3tvBXOekfed1mblKLitNlSdk3qwuK nSXPeyzYSIZkwnVuCnUicVciO160UvT85Nim9XoM8ub0NAzLW5mvA0Y+ZTACUtyP7Xlr UxhmYRydh6tLzX336T6i7iJ5/eKcMLQsX++DSHHwkZGvV2tRAgL9u6waWht2rtayVHxQ 3jhdhIE/7RWdc3Jv6YS0ZMve6HA9ZwwK3912XZl8JHv1J8L0/qynM4Z6f+9w1bHRDaXQ 6G5w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:sender:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=CZDGZ6duRIKsx1Yv99ALabJPXmblXJNBrrN0K0V8yAU=; b=ZLj9Aw6CtnW1vpLt/2WDz8FuVgL1V4f1TYyLnFQZNX/cqZJpwMsGJw1kU3v4HQuYix k/NJ8lPxh/Ow/Yxqzb6n7/Zi9lf2LoWEHm/deGUQkFwlP1p8GVYDgrQ1bmvXFv9MrCO8 okgBr/SVl6d/o704DXYTEr7SYabBucll+ZLPEATPbfuvJHgBllqWwJa+2SMStZEIn8wm BPugJUqhMxp1OTjKA45MaEVsSzmo/zhyVXC1o1m+1ceweDEl2720sjpIHbKmBBmU0XRV 5Ii8KrgdswWmwvQoKF5k23Syal903c3roEpi+rU3nxtIPANNS0RsVx+KYjmCeHwnSWff WGAw==
X-Gm-Message-State: AGi0Puau/LCll0ehHM4eARCvKfpCRtv3pwuTZvVVbrfdRxI8o4phbS/U KkVmR4tFbV1/2Cngx4WtnNk=
X-Google-Smtp-Source: APiQypIV4y0/pR0iOtQ/AMZBO4KnNPYvkeB7ye1/0u7Fb6a9lvB2WWxiLvpIx9kjLK7x9TtdWBYSHA==
X-Received: by 2002:a62:1d48:: with SMTP id d69mr16841933pfd.102.1589216598381; Mon, 11 May 2020 10:03:18 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id 140sm9816253pfw.96.2020. (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 11 May 2020 10:03:17 -0700 (PDT)
Sender: Tony Li <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_EDBAA4F9-10B8-4492-961C-51270B59C4F5"
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.\))
Date: Mon, 11 May 2020 10:03:15 -0700
In-Reply-To: <>
Cc: "" <>, "" <>
To: "Gengxuesong (Geng Xuesong)" <>
References: <> <> <>
X-Mailer: Apple Mail (2.3608.
Archived-At: <>
Subject: Re: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Link State Routing Working Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 11 May 2020 17:03:32 -0000

Hi Xuesong,

> Thank you for giving detailed proof, and it is very helpful to understand the mechanism.
> As I understand, it is showed in the proof that if there is proper temporary flooding in R = E - E* - E’, same connectivity could be achieved by the flooding topology F’ just as G’. I agree with this.

I’m glad it helped.

> The problem for me now is how to enable the temporary flooding properly.
> Here is an example:
> <image001.png>
> The solid line presents the physical link inside flooding topology, and the dashed line presents the physical link out of flooding topology.
> From the view of me, when multipoint failure happens, node 3 is supposed to enable the temporary flooding between 3 and 4, in order to connect with the nodes inside the red box, while the other dashed line between node 1 and node nobody is not supposed to do temporary flooding although node 1 is connected to the failed link directly.
> It seems a little unclear for me about how the node itself could decide whether a dashed line should do temporary flooding or not in this case.

The problem that you’re asking about is partition detection.

To explain this, I’ve taken the liberty of adding some more labels to your diagram.

To start, each node has its link state database and the flooding topology.  Each node should receive link state updates from nodes in its partition, but will not receive updates from other nodes, thus the link state database is partially inconsistent and must be treated with care.

For example, node 2 will see updates from nodes 1, 6, and 7, informing it of the failure, but it will not receive an update from node 8.

Now, the job of each node is try to compute the partitions of the flooding topology.  In particular, each node needs to understand which nodes are in its partition. A node cannot know all of the partitions that exist, but it turns out that that’s irrelevant.

Once a node understands which nodes are in its partition, then it is a simple matter to see which links should be enabled for temporary flooding.  If a neighbor is in the same partition (e.g., nodes 1 and 5), then adding the link adds no value. If the neighbor is not in the same partition (e.g., nodes 3 and 4), then it becomes a recovery link.

The actual computation of the partitions is straightforward, with one caveat: we always want to perform a two-way check for connectivity.  An implementation should be doing this during SPF already, so this should be familiar. The reason for doing this is quite clear: in node 2’s link state database (LSDB), the LSP for node 8 will show connectivity to node 1 even after the failure. However, node 1’s LSP will clearly show that the adjacency has failed.  We can only infer connectivity when we see both sides of the adjacency are up.

Given this, the specific algorithm that you choose is an implementation detail.  You could do a breadth-first search or a depth-first search. Our implementation chooses to walk the entire flooding topology, building a tree of the partitions that it detects. [IPR note: we have a IPR claim for this approach, with the “don’t sue us, we won’t sue you” terms.]

I hope this helps.