Re: [Lsr] On flooding, diameter, and degree

tony.li@tony.li Mon, 19 November 2018 22:12 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 94CBD130DE5 for <lsr@ietfa.amsl.com>; Mon, 19 Nov 2018 14:12:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.4
X-Spam-Level:
X-Spam-Status: No, score=-1.4 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 rZxIv5mcbwmG for <lsr@ietfa.amsl.com>; Mon, 19 Nov 2018 14:12:54 -0800 (PST)
Received: from mail-pg1-x536.google.com (mail-pg1-x536.google.com [IPv6:2607:f8b0:4864:20::536]) (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 ED2AB1252B7 for <lsr@ietf.org>; Mon, 19 Nov 2018 14:12:53 -0800 (PST)
Received: by mail-pg1-x536.google.com with SMTP id s198so1272652pgs.2 for <lsr@ietf.org>; Mon, 19 Nov 2018 14:12:53 -0800 (PST)
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=FSyLd8zP2imyx8GbcTAcSfpKrscG4pq0myhmW+K0a9o=; b=BNWxwMG8HwZFThzeJNcn7M+xDKMKUotdmraRI27cEnJ1bzOqeeVf16BFSEqtu2NNCd KvFQQeubbr0d2gjpzVIPk5oE7+boeYZKBtjP4VJfhtcfynEn5b4bqDYgQ8DXWW1O3ueR CrkEp9S9MADWo9OfzhyTXsuLkT8aQVcaf1erR2g0AON4f4jXwOwArq92rVOjoYdSod58 ZW3SHjn8NBxFtQrVAVtEjH+lJxWUQ+VTbOBPhvHeeyYw4TDGgdczhTDJq0wWZRxno5Xw Brefc4cE8dmy5AL96Jm1/PFetlneBLoruJuFI8lqlpl1qnEWa5ZiRB0Kb2hRthuB/xGQ IINA==
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=FSyLd8zP2imyx8GbcTAcSfpKrscG4pq0myhmW+K0a9o=; b=YdMU8+5JBmyggwhI8N3CrcmExs97ap2AmNVdyVXf/cHN13lyVLvzXflKoyG561Ysc0 cHZ/d5U8DZa4zbKe8jYg42apzn6o4276WdG2YoDhTSBZ1re6eoFBf5obpkkJv6r0bggN y/yMB4uH9n/2nGMo00Bt7rNLiQrVA3NsDLOH+abW8Bizc1RNPeWfrWHL7nW0qZcMBwTI d+vUZZfJWWSjwUkud8we4o+f507hZz/kVJcejVMVQgDn4Qs35osAvfBFdjhsS2cjXdl2 LYSg8R1Qg7Vugq06ORYzZkpBcwwSvPsJGH+Ihhr91+Xr1grVUiYFTs5CLgd97CCM03QM WVQQ==
X-Gm-Message-State: AGRZ1gL58SxDWRjE0ijotsFD7IrM7+OWaTGyAAaNqkEXekWfTS2MN2nh wMVY1PTP1BLp2wuJNA/tuBM=
X-Google-Smtp-Source: AJdET5ew033I1quHzfKhvuJWaNTYcewMYxKNWF8LPd+lq858HSxCBBrPY7Au3W6Q0Rlt/ypT6XaQJg==
X-Received: by 2002:a63:1258:: with SMTP id 24mr21488363pgs.114.1542665573354; Mon, 19 Nov 2018 14:12:53 -0800 (PST)
Received: from [172.22.228.216] ([162.210.130.3]) by smtp.gmail.com with ESMTPSA id z8sm65934773pgz.53.2018.11.19.14.12.52 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 19 Nov 2018 14:12:52 -0800 (PST)
Sender: Tony Li <tony1athome@gmail.com>
From: tony.li@tony.li
Message-Id: <90FD275F-695D-4213-86F1-C369C5CE17F3@tony.li>
Content-Type: multipart/alternative; boundary="Apple-Mail=_2CFDBCA6-0CC4-4316-9F66-BF57D3C1A784"
Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\))
Date: Mon, 19 Nov 2018 14:12:51 -0800
In-Reply-To: <CO1PR15MB1095CB6927D20C7CD7EDFAD8D0D80@CO1PR15MB1095.namprd15.prod.outlook.com>
Cc: "lsr@ietf.org" <lsr@ietf.org>
To: David Allan I <david.i.allan@ericsson.com>
References: <EDB53B05-0AFD-4C94-A9D7-80EE22BEF6C7@tony.li> <CO1PR15MB1095CB6927D20C7CD7EDFAD8D0D80@CO1PR15MB1095.namprd15.prod.outlook.com>
X-Mailer: Apple Mail (2.3445.9.1)
Archived-At: <https://mailarchive.ietf.org/arch/msg/lsr/Fy45cxjrE3FiepGgiAzUPauT2zc>
Subject: Re: [Lsr] On flooding, diameter, and degree
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: Mon, 19 Nov 2018 22:12:56 -0000

Dave,

Thanks very much for commenting.  I’m a bit confused about your column “Receipt Degree” and perhaps how flooding works in your proposal.

Let’s use the example from your section 4.2, where ‘a’ and ‘z’ are the roots and there are only two tiers.

Suppose that ‘a’ has an update.  It replicates to all lower nodes, except that the link from ‘a’ to ’3’ has failed.

Per section 4.4, it seems like this is an update received from an upstream member adjacency. Since this is only a two-tier system, the lower nodes have no downstream nodes, so they do not replicate back to the upstream.  How do nodes ‘b’ .. ‘z’ ever get the update? How does ‘3’?

If I’m misunderstanding 4.4, and all of ‘i’, …, ‘x’, and ‘1’, …, ’n’ replicate back to ‘z’, then doesn’t it have a receipt degree higher than 2?

Or are ‘i’ and ’n’ special cases that do upstream replication, resulting in paths a - i - z - 3 and a - n - z - 3?

Very confused,
Tony






> On Nov 19, 2018, at 1:44 PM, David Allan I <david.i.allan@ericsson.com> wrote:
> 
> HI Tony:
>  
> Re: draft-allan-lsr-flooding-algorithm…. 
>  
> My draft falls under the “bushy” class of solutions,  to borrow your terminology. 
>  
> So mapping to your datapoints and translating what I presented in Bangkok to actual numbers:
>  
> Graph      Fault free      Single Fault    Replication     Receipt   
> Diameter        Worst case       Degree          Degree
> Diameter                              
> K4,17      2               3               17              2
> K4,40      2               3               40              2
> K8,80      2               3               80              2
> K8,200     2               3               200             2
> K16,200    2               3               200             2
> K20,400    2               3               400             2
> K40,800    2               3               800             2
>  
> Worst case occurs when an inter node link fails, as the LSA from one end of the link needs to loop back via the other root to the node at the other end of the failed link.
>  
> Rgds
> Dave
>  
> From: Lsr <lsr-bounces@ietf.org> On Behalf Of tony.li@tony.li
> Sent: Monday, November 19, 2018 10:29 AM
> To: lsr@ietf.org
> Subject: [Lsr] On flooding, diameter, and degree
>  
>  
> Hi all,
>  
> I’d like to expound a bit more on a point that I made at the mike in Bangkok.
>  
> The figures of merit for a flooding algorithm are the resulting diameter of the flooding topology and the maximum degree of the nodes in the topology.
>  
> The diameter is important because it says how many hops an link state update will have to traverse before it covers the topology. This dictates what the convergence time of the network will be.
>  
> The degree is important because it is the measure of the amount of replication that a node will have to do during flooding, and, more importantly, it is also a bound on the number of times that a node can receive replicas of the same update.  If the degree is too high, then the node can be overwhelmed by an influx of flooding, resulting in instability.
>  
> For a flooding algorithm to be seriously considered, it is important to characterize these results and understand how they grow under scale.  In particular, I’m concerned about tree based algorithms because they typically have a large diameter because the tree is tall and spindly, or they end up with a large degree, because the tree is quite bushy.
>  
> I would very much like to see candidate algorithms present how they perform.
>  
> Here’s a few data points from our algorithm simulations, just for comparison:
>  
> Graph      Diameter        Degree                       
> K4,17      4               10
> K4,40      4               23
> K8,80      4               22
> K8,200     4               53
> K16,200    6               28
> K20,400    5               45
> K40,800    6               43
>  
> Thanks,
> Tony