Re: [Lsr] New draft on Flex-Algorithm Bandwidth Constraints

Tony Przygienda <> Mon, 01 March 2021 16:59 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BDAFB3A1F9D for <>; Mon, 1 Mar 2021 08:59:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.965
X-Spam-Status: No, score=-1.965 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, URI_DOTEDU=0.132] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id uA_PKopgFet9 for <>; Mon, 1 Mar 2021 08:59:05 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::d33]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id AE2EE3A1F9E for <>; Mon, 1 Mar 2021 08:59:05 -0800 (PST)
Received: by with SMTP id n132so6661224iod.0 for <>; Mon, 01 Mar 2021 08:59:05 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=J5VCwD2Fi51JdRSkBpVL8TzLuWe/qEUR8Bv0pnsiRac=; b=gkTu1v7x/4O2/JHHY+NYxIOefw7pgVrWZVGIDTdJwRxxj1uDL5+7zxh3yWIw5+Z7tT 9wRIVjfXJBpU78eeJlu3+HLZNCkeAZt3NmHSvuqZzARyx012MWUxd+u2oUkOflCh0DBu 8AlzPJN3xvVlWFeru4gchKDIc9gRa/jVksWXRl5de3RoBruOVZ5hpMKb06T4RUSDPdM+ Qymea69gWBiqdXotiQ/73A8J48cYlRomcxACHLVjO2amVliimY6c2XuhfWVjmjzOJW3r +5l/U2bzwf4ZRi4VWhUqzSR9sF6Wh5jeQ+kSKymjpboUkhn9m/b72fri7assxMGAFrxb BZgg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=J5VCwD2Fi51JdRSkBpVL8TzLuWe/qEUR8Bv0pnsiRac=; b=OC7jwNBarNSVHjdHlmZkUxZ5U3aF5ex8AERX4/48TZ32MTEvnORtyof9NSMUveJ+ak dxttn/Yyh6Or976MPJFr8pY911n9wSoTNAIgoXohagAeGJm2IXg/gAY8gi+mSvD3FsCg B8Q29G1FfH0YGmYxDPI4NOXn4G7f7GsJsng1Rb4dgkY32WDZYLiWatXY3OSX9v0Bknrn rhiHYFhSrY5QT6X+xAuV5uYNEEwF+vCSKfKAf8vkXCNF9rspLUxhtT80pdhUpN30+eYh garCU9wdtte3naQA5VjWrl1qy7C5aTUxJj/N/0sH4bzvRBWjTTmXefFnr7lKrDDg3gIf t+ww==
X-Gm-Message-State: AOAM5317EGfqowdHmDljp4R0J+75n7lz6pUlG1W7DvpZiXoEJ8CnmgbX GBkzXHrgR4xA1jd9OL35x+FyLCzf3JYZnAyGWUY=
X-Google-Smtp-Source: ABdhPJyG2YI/g0v24eyJ+3EDKPvbs/hf4/4yaKYCvj4YWDOkurtWxLBiuv2Iv/3/Vtg8zd1iXBjiz8DvQ3KTUpDtINY=
X-Received: by 2002:a05:6638:2bb:: with SMTP id d27mr16678519jaq.98.1614617943603; Mon, 01 Mar 2021 08:59:03 -0800 (PST)
MIME-Version: 1.0
References: <> <> <>
In-Reply-To: <>
From: Tony Przygienda <>
Date: Mon, 1 Mar 2021 17:58:27 +0100
Message-ID: <>
To: Tony Li <>
Cc: William Britto A J <>, "" <>, "DECRAENE Bruno IMT/OLN" <>, Shraddha Hegde <>, Rajesh M <>
Content-Type: multipart/alternative; boundary="000000000000fa0bf005bc7c884d"
Archived-At: <>
Subject: Re: [Lsr] New draft on Flex-Algorithm Bandwidth Constraints
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, 01 Mar 2021 16:59:08 -0000

On Sat, Feb 27, 2021 at 2:56 AM Tony Li <> wrote:

> Hi William & co-authors,
> Thank you for your contribution. It’s definitely interesting. As bandwidth
> management is one area where FlexAlgo lags legacy traffic engineering, this
> is definitely one small step in the right direction.
> But I have many comments…
> 1) I’ll start with the title: there is MUCH more here than bandwidth
> constraints. Perhaps this should be generalized somehow? Sorry, I don’t
> have a constructive suggestion.

there is good general, theoretical body of work here that shows what is
possible to compute (NP completeness, algorighms, heuristics). short search
yields e.g.

JSAC '96 Crowcroft is a starting point on additive/multiplicative, other
papers even eqarlier called that stuff max/additive, convex/concave (that
has to do with linear programming space properties) etc. I'm aware of work
going as far back as '92-'93 here.

Generally, one max/min & one additive is doable (you need additive to make
sure you don't start hamiltonian walks based on a constraint ;-)  Mixing up
addvitive & mix/min is a fairly poor idea unless one is happy with
heurestics that kind of "almost always work" and customer is not looking
for hard guarantees but "wishes that maybe granted".

> 2) Section 2: I concur that bandwidth is an important consideration in
> path computation. At a first reading, it is not at all clear to me that it
> is optimal to somehow transmogrify things into a metric. Why not simply
> deal with the bandwidth directly?  I did (eventually) realize that you did
> this because you want SPF to somehow select the path with the minimum
> product of (# links) * bandwidth.  I think you need to be explicit about
> this motivation and also mention that traditional SPF is not set up to deal
> with a floating point metric. Note that a bandwidth metric is STILL
> somewhat counter-intuitive to me, as I would expect that you’d mostly want
> to route things along the highest bandwidth paths, not the lowest ones.
> More motivation behind the bandwidth metric would be most welcome.

yeah, BW can be made a metric and work, IEEE encoding is simply a funky
number and different max/min/additive/multiplicative/any increasing
function (whether it has to be stricly monotonic is a more complex
discussion).  old but very solid stuff for that space

based on even earlier

   [BP95]   J.-Y. Le Boudec and T. Przygienda.  A Route Pre-Computation
            Algorithm for Integrated Services Networks.  Journal of
            Network and Systems Management, 3(4), 1995.
   [GOW97]  R. Guerin, A. Orda, and D. Williams.  QoS Routing Mechanisms
            and OSPF Extensions.  In Proceedings of the 2nd IEEE Global
            Internet Mini-Conference, pages 1903-1908, Phoenix, AZ,
            November 1997.

expired draft-ietf-qosr-framework-04.txt

 but given graph theory doesn't change things roughly still the same ;-)

There is also good body of work on something that quickly interacts with
that work, namely k-disjointness. e'thing looking for "fattest pipe" or
"shortest-widest" pretty quickly crams all traffic on the same links ;-)
unless somehting like RSVP-TE reserves & changes metric.

All those things have been implemented and worked in products so we know
they work, maybe flex stuff is just a framework now to unify it all a bit.

my only small nit on the draft is that the stepping is in practical terms
almost always exponewntial so you don't have to encode full value
necessarily. the rounding has to adjust to link size as well or is better
served as % value.

-- tony