Re: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04

tony.li@tony.li Sat, 09 May 2020 17:18 UTC

Return-Path: <tony1athome@gmail.com>
X-Original-To: lsr@ietfa.amsl.com
Delivered-To: lsr@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id EC8163A0CF8 for <lsr@ietfa.amsl.com>; Sat, 9 May 2020 10:18:43 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.499
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 3OrrhDaS5kuP for <lsr@ietfa.amsl.com>; Sat, 9 May 2020 10:18:37 -0700 (PDT)
Received: from mail-pf1-x434.google.com (mail-pf1-x434.google.com [IPv6:2607:f8b0:4864:20::434]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E62DE3A0C7F for <lsr@ietf.org>; Sat, 9 May 2020 10:18:31 -0700 (PDT)
Received: by mail-pf1-x434.google.com with SMTP id 145so2598162pfw.13 for <lsr@ietf.org>; Sat, 09 May 2020 10:18:31 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=6SKK+lJ870gqkApQ2xKx/LqWcr03+zEUVdWSke5i8tE=; b=GOruR+saiAAtrPuwaJoLF+er08PUbxuUdRvXWHleB3zXXv9khnPw+/z0Id83LEL6af lGRWyCkxKud+pXbaDKmOtxvC5sfAlzqaHAh8bEN9MHeB6fpjRfcW3IFeoxcnaS2XpKd/ 6JV3yud+wyeUK+Alri5LX8Ts/vgq/VjMvCYu+nJeQ1KhSCH0sh3Fa+NXgiNti4Zf7L5V 6fMJ2QqwONMAoMhVPUdQnb1g+mtwQgvMtaQPdqeUTex0npqI6Yy0PnZOG5hWhnDOms1a xRJ8ITQDMdQ+SRBg58UvRs1Y2/hr3N6U79TjQXsdL/gqLoJzKTSbZ81fcNBLGkXithyl moKg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=6SKK+lJ870gqkApQ2xKx/LqWcr03+zEUVdWSke5i8tE=; b=uMYS97eM6Qh/o/gzv9pEgyKHy0vqCLsxw5Xg5uK8m7o6Hb/QVewy65a+14A9i2Qhri u2JGQ9PEB2emQpilamW71gNsPI2mMfYOvI9sHCQ3XIA4NIZdzXxy3SLMTe6AjBdAle/Y UWrqd6NykXioCRCj5KgvG+O5w07c+eVkWevV1dR6QijK248h1OQ3RIkYAaaP9MqTRPRV XVzsl9zZtsa8ZFpVnvDwPEXm2v45DEsH/bxQZ6fk0yEoHkW9VtA/slQNtf/6JdFxBwvE 6qz2I9t/76h8CASkgYp/GbDxiTYHRs4Lx9RX2zLJbqSnoGGp0Qd+w340tESmyeg6ajCb wUOA==
X-Gm-Message-State: AGi0PubT56qDtG0KJtfzWeXaigErmxxjG/lwezQoJ5nvCSaITleqClfk 3hpH6AvTkR/3DnygdiYcg/M=
X-Google-Smtp-Source: APiQypKGhPPcJoFf3LJMpX8u5LuJ5ZZV0ColNdotxZH/3lFOu4GbEStlufqsf4wRJ+HE3+7Nz1sQ7w==
X-Received: by 2002:a63:1e22:: with SMTP id e34mr7646041pge.427.1589044711119; Sat, 09 May 2020 10:18:31 -0700 (PDT)
Received: from [10.95.85.165] ([162.210.129.5]) by smtp.gmail.com with ESMTPSA id kr1sm2134840pjb.26.2020.05.09.10.18.29 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Sat, 09 May 2020 10:18:30 -0700 (PDT)
Sender: Tony Li <tony1athome@gmail.com>
From: tony.li@tony.li
Message-Id: <15BFEDE9-5FCB-4FF2-A373-96231AECE607@tony.li>
Content-Type: multipart/alternative; boundary="Apple-Mail=_DDED3C64-31DE-4448-A9AF-607BE84B70C3"
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.80.23.2.2\))
Date: Sat, 9 May 2020 10:18:28 -0700
In-Reply-To: <28604621f41f45a5a6b870413c4318e0@huawei.com>
Cc: "sarahchen@arista.com" <sarahchen@arista.com>, "lsr@ietf.org" <lsr@ietf.org>
To: "Gengxuesong (Geng Xuesong)" <gengxuesong@huawei.com>
References: <28604621f41f45a5a6b870413c4318e0@huawei.com>
X-Mailer: Apple Mail (2.3608.80.23.2.2)
Archived-At: <https://mailarchive.ietf.org/arch/msg/lsr/-LzHjxZMp1JepZHDRKCQoIxPT-Y>
Subject: Re: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04
X-BeenThere: lsr@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Link State Routing Working Group <lsr.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/lsr>, <mailto:lsr-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/lsr/>
List-Post: <mailto:lsr@ietf.org>
List-Help: <mailto:lsr-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/lsr>, <mailto:lsr-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 09 May 2020 17:18:46 -0000

Hi Xuesong,


> Thank you for your work about Flooding Reduction mechanism. I think it is very useful for IGP scalability.


Thank you, we very much appreciate that.


> When Sarah giving presentation for draft-chen-lsr-dynamic-flooding-algorithm-00 in LSR interim meeting, I raised a question about how to handle multipoint failure in the flooding topology. I remembered that draft-ietf-lsr-dynamic-flooding-04 was mentioned. I have read this draft, especially section 6.8.11 and temporary flooding relevant content. I think it is a valid method logically. (We have tried to raise some examples to challenge this method, but in all these cases, this method works) Considering that reliability of IGP is crucial for deployment, we are still wondering whether some mathematical proof is necessary (or possible) to guarantee that, in all the possible scenarios, proper convergence could be achieved when using flooding reduction algorithm, just as traditional IGP mechanism. The proof may be case by case depending on the flooding reduction algorithm, but we think even some example or clue about how to do this will be very helpful.


A proof? Ok, I can try to be rigorous, but it’s been a very long time. I apologize in advance to Kireeti, Mr. Myers, Mr. Douglas, and Prof. Greever for what follows.


Definition: Let G=(V, E) be a finite graph. F=(V, E’) is a ‘flooding topology’ on G if E’ is a subset of E and F is connected.


We normally have other properties for flooding topologies, such as being bi-connected, relatively sparse, minimal diameter, and minimal degree, but those properties are not relevant for this proof.


Definition: Let C=(V*, E*), V* a subset of V, E* a subset of E, be the ‘cut’ of G. This represents the failures in the topology. Let G’ = G - C, the topology after failure, and let F’ = F - C, be the flooding topology after failure. 


Definition: Let R = E - E* - E’. This is the set of 'recovery edges': edges that have not failed and are not part of the flooding topology.


Corollary: R is finite. 

Proof: G is finite, by definition. Therefore E is finite, E* must be finite, and E’ is finite.


Lemma 1: If G’ is connected, then F’ + R is connected.

Proof: 

G’ = G - C = (V, E) - (V*, E*) = (V - V*, E - E*).  

F’ + R = (F - C) + (E - E* - E’) = (V, E’) - (V*, E*) + (E - E* - E’) = ( V - V*, E’ - E* ) + ( E - E* - E’) = ( V - V*, E’ - E* + E - E* - E’ ) = ( V - V*, E - E* - E* ) = ( V - V*, E - E* ) = G’.

Q.E.D.


Lemma 2: If G’ is connected, then incrementally adding edges from R to F’ will yield a connected flooding topology.

Proof: By induction. Let R’ be a subset of R. Induction property: Either F' + R’ is connected, or R’ is a proper subset of R.

Base case: R’ is the empty set. If F’ is connected, then F’ + R’ is connected and the property is satisfied. If F’ + R’ is not connected, R’ is empty, which is a proper subset of R.

Induction case: Let r be a recovery edge in R - R’ (i.e., a new edge to add).  If F’ + R’ is connected, then the property is satisfied already. If F’ + R’ + r is connected, the property is satisfied. If R’ + r = R, then by Lemma 1, the property is satisfied. Otherwise, R’ + r != R, and the property is satisfied. By our corollary, the induction must terminate.

Q.E.D.



Bugs, questions, and comments are welcome.

Regards,
Tony