Re: [bmwg] Call for views: draft-vpolak-mkonstan-bmwg-mlrsearch-03

"Vratko Polak -X (vrpolak - PANTHEON TECH SRO at Cisco)" <vrpolak@cisco.com> Thu, 19 November 2020 18:35 UTC

Return-Path: <vrpolak@cisco.com>
X-Original-To: bmwg@ietfa.amsl.com
Delivered-To: bmwg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 26B993A0FB1 for <bmwg@ietfa.amsl.com>; Thu, 19 Nov 2020 10:35:17 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.6
X-Spam-Level:
X-Spam-Status: No, score=-9.6 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, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_DKIM_WL=-7.5, WEIRD_PORT=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com header.b=LPs69UW9; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=OQLKbGOd
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 mRgWmZ7uEtOW for <bmwg@ietfa.amsl.com>; Thu, 19 Nov 2020 10:34:40 -0800 (PST)
Received: from alln-iport-6.cisco.com (alln-iport-6.cisco.com [173.37.142.93]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DDF093A0944 for <bmwg@ietf.org>; Thu, 19 Nov 2020 10:34:38 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=9180; q=dns/txt; s=iport; t=1605810878; x=1607020478; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=Q+TY+ZaW5bv6Cq9cTMUSYaBJhsa1bqqHPsKQXLE4RyI=; b=LPs69UW92vIBnp0jVDPmdoc3CE6VBd4NetB4rQU21oAQa9CK81TZuj8Z LoVffYJRBi/CY4oaaQibP5Af0Ml8ELIzEDDckGta+nDXIt00IufO/FDSb z37IYYWxSWDyY0JMyQi6xbTnPdDQEORp36iM9INcCCyAmxDON2SY8IQjy M=;
X-IPAS-Result: =?us-ascii?q?A0D5CABtubZffZxdJa1igQmDIVF7WS8uCoQzg0kDjVyBB?= =?us-ascii?q?Zd+gUKBEQNUCwEBAQ0BARgPBgIEAQGDMkVTAheCEgIlOBMCAwEBAQMCAwEBA?= =?us-ascii?q?QEFAQEBAgEGBBQBAYY8DIVyAQEBAQIBAQEQCwYRDAEBLAsBBAcEAgEIEQQBA?= =?us-ascii?q?QECAiYCAgIlCxUICAIEDgUIGoMFglUDDiABAwukNQKBPIhodoEygwQBAQWBM?= =?us-ascii?q?wEDAgIMQYMJGIIQAwaBDiqCc4N2hlcbggCBEUOBUUk1PoI7IgEBAgEWgQwgH?= =?us-ascii?q?BWDADOCLJNsh0WHV4QRkR8KIIJNiRKSKoMaiheUS5VViQCVWAIEAgQFAg4BA?= =?us-ascii?q?QWBayGBWXAVO4JpUBcCDY4rF4NOgmSCMIVEdDcCBgEJAQEDCXyMOwGBEAEB?=
IronPort-PHdr: =?us-ascii?q?9a23=3Ax2jPcBcissuqrfXUEvt+b+eLlGMj4e+mNxMJ6p?= =?us-ascii?q?chl7NFe7ii+JKnJkHE+PFxlwaQA9fb6u4Cge/b9aD9CiQM4peE5XYFdpEEFx?= =?us-ascii?q?oIkt4fkAFoBsmZQVb6I/jnY21ffoxCWVZp8mv9PR1TH8DzNF3Tvju46DNUGg?= =?us-ascii?q?isfQZwL/7+T4jVicn/3uuu+prVNgNPgjf1Yb57IBis6wvLscxDiop5IaF3wR?= =?us-ascii?q?zM8XY=3D?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-AV: E=Sophos;i="5.78,354,1599523200"; d="scan'208";a="631387231"
Received: from rcdn-core-5.cisco.com ([173.37.93.156]) by alln-iport-6.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 19 Nov 2020 18:30:21 +0000
Received: from XCH-RCD-001.cisco.com (xch-rcd-001.cisco.com [173.37.102.11]) by rcdn-core-5.cisco.com (8.15.2/8.15.2) with ESMTPS id 0AJIUFbs021091 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Thu, 19 Nov 2020 18:30:20 GMT
Received: from xhs-aln-003.cisco.com (173.37.135.120) by XCH-RCD-001.cisco.com (173.37.102.11) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Thu, 19 Nov 2020 12:29:44 -0600
Received: from xhs-rtp-001.cisco.com (64.101.210.228) by xhs-aln-003.cisco.com (173.37.135.120) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Thu, 19 Nov 2020 12:29:43 -0600
Received: from NAM02-BL2-obe.outbound.protection.outlook.com (64.101.32.56) by xhs-rtp-001.cisco.com (64.101.210.228) with Microsoft SMTP Server (TLS) id 15.0.1497.2 via Frontend Transport; Thu, 19 Nov 2020 13:29:43 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=KxNErFDBNeMlBNJLwQYc9rgSKFvjAk7QsFd+TMX0uSc2oPwW8P63VvZITAvRZBq6trHFUn3uDquDAKj7D3ERQUcqlc58BOBtt80Evjk5NCu42iwQdrmROyDt0ILNJLn1yZQHfMG7T7Wi6EpacoKN4BhKxcrRLI2/SEOafUOe0N/mfc3mTbkXsbSN58WBOQsaaYBY/m2U986PL93DcYFw4lAQZc/tqssTvUuqPFMhG/HeGwJHd0NJBNVo4tYGPRfrr324+NxQq23ZgIYUuxns1R3OvK+PCQsIzZPyy5Vx/G/QPayBgbBm8WH4ibKdCvDFXpYW+J3finBXaWq4a4TGxg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Q+TY+ZaW5bv6Cq9cTMUSYaBJhsa1bqqHPsKQXLE4RyI=; b=P3Ierf+LK/HZt9XUWpjjSk/gpd0/sm5Oj89F4NWwRNRznBuOmJtDYPs2fBQEl8Fpw+0+TxCNUK2phHHRVjHDhvFfFJQuqqOcMVVcXRlmR8OiSDypP/DWIKWKZGUsCQffQtGse8Vg5ZiAdDoXZgSZfdD46B5jMsn4ivjuVeJYGDibqHEH0yOrPqw0cKl6P1Zne1mSjFAVzubh7vLAY35tMywkIxtv+UcZg//EjrxYjMDFhk1e56VsY5wf6AEdDTV4oAwr44rAo1RmsRe0rVM0cx1KzK2NoJlipY2/5XnAdKzOKWkQPYhuvj/6ax8eArrXFI+GzEd/6tdSPwNdETXEHA==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=cisco.com; dmarc=pass action=none header.from=cisco.com; dkim=pass header.d=cisco.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cisco.onmicrosoft.com; s=selector2-cisco-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Q+TY+ZaW5bv6Cq9cTMUSYaBJhsa1bqqHPsKQXLE4RyI=; b=OQLKbGOdZFI+gthBVDOo9uzQjF6miQjBe6LzIedjWH7182eBUvbPGo+Drj1v7L5rh/3pdESOj56WB6QscRgcpFhYrw7S4NPmC3tmZa3S5t3XQz1H+XBXcroNyDpVPE4D9s6Wcyf1HnwXNSjZSzJYHjbs3wDZEUjhyrGz0d8Scmc=
Received: from BY5PR11MB4038.namprd11.prod.outlook.com (2603:10b6:a03:18c::33) by BYAPR11MB2663.namprd11.prod.outlook.com (2603:10b6:a02:ca::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3564.28; Thu, 19 Nov 2020 18:29:42 +0000
Received: from BY5PR11MB4038.namprd11.prod.outlook.com ([fe80::555f:32d3:7019:8c0a]) by BY5PR11MB4038.namprd11.prod.outlook.com ([fe80::555f:32d3:7019:8c0a%3]) with mapi id 15.20.3541.025; Thu, 19 Nov 2020 18:29:41 +0000
From: "Vratko Polak -X (vrpolak - PANTHEON TECH SRO at Cisco)" <vrpolak@cisco.com>
To: Gabor LENCSE <lencse@hit.bme.hu>
CC: "bmwg@ietf.org" <bmwg@ietf.org>
Thread-Topic: [bmwg] Call for views: draft-vpolak-mkonstan-bmwg-mlrsearch-03
Thread-Index: AQHWveRyhjiB8wvwwkup7JWBCi6ZDKnPB6QAgACQfKA=
Date: Thu, 19 Nov 2020 18:29:40 +0000
Message-ID: <BY5PR11MB4038D6E164D9FB1F7453C1D5BDE00@BY5PR11MB4038.namprd11.prod.outlook.com>
References: <F9E3D2FE-3A28-4EAB-ACFA-6F7916188804@cisco.com> <c38133b8-1be7-d77a-0e40-8bcbe47ac405@hit.bme.hu>
In-Reply-To: <c38133b8-1be7-d77a-0e40-8bcbe47ac405@hit.bme.hu>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: hit.bme.hu; dkim=none (message not signed) header.d=none;hit.bme.hu; dmarc=none action=none header.from=cisco.com;
x-originating-ip: [46.229.239.158]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: b59481bc-327b-4be6-0c72-08d88cb914d2
x-ms-traffictypediagnostic: BYAPR11MB2663:
x-microsoft-antispam-prvs: <BYAPR11MB2663C8FB585E46D16B399012BDE00@BYAPR11MB2663.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: kUJ5uP+JwMA1fCq55l2CAOclbUK4TN9410+14mUnDstURJMn95ZhpIutD61fYx/fr0O45jZ273zceOL62LXteYeQOyLySe8eGn1QTS4+bdarZekqP8urRjRnM5lpQsGgHvimE15PX3OLb4XTtzJIcNs8Rk+NQ2MZjUgG1f1slfdcD7Ivj8I4dwl+49/795HQHrG0Stt/sgcO9677lkTFiG6DrCR+kzEbEMCg6lsV6GrrXV4ELuJ/7Rydn2/PWbm3d+EvJy7vGqZM85BzSbYNOaitayQXOtGgWHbDT0TbEHqY5dIg49UFctC5BJnbTJIrqMFe8BQBIr7bc5MJ2VNCsrHasMMosMIhig5vSJghizTOK/UpgqQF/eXXq6eu6LxWJIFspG+mmr9GfHyk7RdRLQ==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BY5PR11MB4038.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFS:(376002)(396003)(346002)(366004)(136003)(39860400002)(4326008)(5660300002)(7696005)(66574015)(186003)(26005)(83380400001)(6506007)(478600001)(966005)(52536014)(55016002)(316002)(6916009)(53546011)(66946007)(66556008)(66476007)(8676002)(8936002)(86362001)(66446008)(76116006)(64756008)(71200400001)(33656002)(9686003)(2906002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: OG7+H8VLgSA8W834A8XrGqOuB4gHC/R3Va2fu1zlCegMCiaIzNVd5WC1XZFo+1Vd/9qxHwSK6DgbHz91eXRzeZNef/jEmojBdkNRBUhcEHaNI52sCbIralSL1BbzNOyZWF/1hzRhmOiKIqpLFusMsXLx0/zGgsbHUfPpiu62bcaYKnMIRxPYWUtfPjw5a04A4RljZTJtpXQ6Bkd/SZB+0ZyocYrO2pcd9QGscofICjkIv3IZBWmaB8/L5SBIQnmyp05qEbhOti5UJcGj4fIabRF8ouK9QGFNbgvfvh7E6kVo5lmGKFKLBf2u/1qF2FysSI0eGgU4IIlolw1RF6Y+vt1v10fC+yIPuQUK+ZoFwL+xjvhOl+IiQW6O3xHLf9qavHZUkqfP9lBhft7vLvpsgVvBFrdtD/RQamv265z0RaDKJK0x9yUf16qqLOcIG7wlWuspuGXFI1cWtUkX5kR5QYkGAyBtaLEDABVJtVij4nFNRAri9eUWfU9cU+TzbsKr2eyXCbiQb97KSVnmCx9sgV3eTnEbZBA8nRSXBS2li3njfoXclOa6W62mX4LDsZvsfT797cI20IlHIznMpcNGQ2HQLZ2w+HZRkGhMDTjOhRALOZVrHCqN1+JOTazooCcNiCEmFKfW9zfamVfejRV3NA==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: BY5PR11MB4038.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: b59481bc-327b-4be6-0c72-08d88cb914d2
X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Nov 2020 18:29:41.5335 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 5ae1af62-9505-4097-a69a-c1553ef7840e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: KyhDgq6dPbaLsOEj68M75nwvSZBRfFLvLlatvJVUw2xe3diKm9BrDEkF43a4CB2kjBsAOdv+wf+MqAmg7IJLPA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BYAPR11MB2663
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.37.102.11, xch-rcd-001.cisco.com
X-Outbound-Node: rcdn-core-5.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/bmwg/v5doMeu7o9Gc_y8adtzsV1Oy0rU>
Subject: Re: [bmwg] Call for views: draft-vpolak-mkonstan-bmwg-mlrsearch-03
X-BeenThere: bmwg@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Benchmarking Methodology Working Group <bmwg.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/bmwg>, <mailto:bmwg-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/bmwg/>
List-Post: <mailto:bmwg@ietf.org>
List-Help: <mailto:bmwg-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/bmwg>, <mailto:bmwg-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 19 Nov 2020 18:35:19 -0000

> Have you done a case study, in which you compared
> the efficiency of MLR search with that of the traditional binary search? 

We did few things.

We compared search duration when we first employed MLRsearch.
Previously, we used binary search (two separate tests, for NDR and for PDR)
with trial duration 10 seconds.
MLRsearch implementation (single test searching for both values)
was using 30 second trial in the last phase
(and accuracy goal was more strict),
and it was still faster.
How much faster, that depends mainly on how stable the DUT behavior is.
When writing the draft, we chose the conservative
"it greatly reduces (>50%) the overall duration".

Before that, during development, I used a small simulator
(to verify MLRsearch works and how well it works).
I never got time to make it really usable,
but anyone can take a look [1] and try to make it work.

> How much faster is your algorithm than traditional binary search?

I think the best case is MLRsearch being 7 times faster.
In worst case MLRsearch is slower than binary search,
but that needs really adversarial DUT behavior (or very bad luck).
Mere "unstable" DUT behavior is usually not enough.

> Could we state something like
> "MLR produces better quality results than binary search" ?

In practice yes. In theory no.

Strictly speaking, the result comes from (the internal search part of)
the last phase of MLR search, which is equivalent to bisection.
Everything that happens before affects only total duration,
not the final result.

Obviously, improved speed allows users to use more narrow target width,
and longer trial duration, improving quality of the result.

Less obviously, earlier phases of MLRsearch are affecting
the position of the final bisection interval.
For deterministic systems it should not matter,
but for less deterministic systems it does.
In my experience there are two effects.
Firstly, having multiple intermediate phases
means more extreme results are less probable.
Secondly, the initial phase (with mrr and mrr2)
is likely to start the search in higher values.
Overall, MLRsearch tends to give results
with higher average, but smaller standard deviation.
But in practice the differences are quite small,
trial duration alone usually has larger effect.

> Please send me a pointer, if you have published such results!

Have you seen the graphs in our presentations?
They come from real tests, but it is not many data points,
and they were selected to show a situation when "something notable" happens.

We are publishing results from our official testing, but only the values
(NDR and PDR, lower bound for each, from 10 runs per test),
duration is not visible.
As we have many tests, we had never run the full set for both searches.

Here [2] is last "release" using bisection,
and here [3] is the first with MLRsearch.
But the DUT tested (VPP) is also a different release,
so it is not an apples-to-apples comparison.
The links are showing "vhost" tests,
which are the least stable from the set.

> I wonder if you are willing to do an update

Yes, updates are on my TODO list.

On implementation front I plan to support configurable number
of loss ratios (not just NDR and PDR).

On documentation front I plan to discuss more deeply
some trade-offs and decisions in the implementation.

On combined front, improvements can be added
(use valid bound from neighboring loss ratio target
when a bound becomes invalid on re-measurement)
and removed (currently I think the "wider interval in earlier phase" idea
is too risky in bad case and not speedy enough in good case).

> in the near future (i.e. within a few weeks)

Hard to tell. I give it a 40% chance
that an update will arrive that soon.

Vratko.

[1] https://gerrit.fd.io/r/c/csit/+/11897
[2] https://docs.fd.io/csit/rls1804/report/vpp_performance_tests/packet_throughput_graphs/vm_vhost.html#ndr-throughput
[3] https://docs.fd.io/csit/rls1807/report/vpp_performance_tests/packet_throughput_graphs/vm_vhost.html#n-hsw-x520

-----Original Message-----
From: bmwg <bmwg-bounces@ietf.org> On Behalf Of Gabor LENCSE
Sent: Thursday, 2020-November-19 08:01
To: bmwg@ietf.org
Subject: Re: [bmwg] Call for views: draft-vpolak-mkonstan-bmwg-mlrsearch-03

Dear Authors,

I am interested in your draft. I promised (right now at the BMWG 
meeting) to review it. I wonder if you are willing to do an update in 
the near future (i.e. within a few weeks), as then I would review the 
updated version.

I also have questions. Have you done a case study, in which you compared 
the efficiency of MLR search with that of the traditional binary search? 
I would be interested in RFC 2544 compliant (zero loss rate) throughput 
measurements. How much faster is your algorithm than traditional binary 
search? Could we state something like "MLR produces better quality 
results than binary search" ?

Please send me a pointer, if you have published such results!

Cheers,

Gábor

On 11/18/2020 8:53 PM, Maciek Konstantynowicz (mkonstan) wrote:
> Dear BMWG Contributors,
>
> We would like to ask your view regarding draft-vpolak-mkonstan-bmwg-mlrsearch-03:
>
> 1. During the interim BMWG meeting post IETF-107 [1] there was quite some interests in working on this draft in BMWG:
>     a. Our (authors) understanding is that BMWG agreed to adopt this work as a BMWG draft and collaborate on making it into RFC.
>     b. But in the absence of the last statement being present in the meeting notes [1], we would like to re-confirm this.
>     c. If it is re-confirmed, we will re-post the draft with its name updated to draft-bmwg-mlrsearch.
>
> 2. If point 1. is cleared, we would like to then invite folks to collaborate closer with us and progress this draft to RFC:
>     a. Welcome all comments identifying areas that require clarification and/or gaps that need to be addressed.
>     b. Substantial additions and co-authors are welcome.
>
> We do have a discussion slot regarding above in the IETF-109 BMWG meeting, slides are available at [2].
>
> Cheers,
> Maciek and Vratko (authors)
>
> [1] notes-ietf-107-bmwg, https://etherpad.ietf.org:9009/p/notes-ietf-107-bmwg?useMonospaceFont=true
> [2] slides for draft-vpolak-mkonstan-bmwg-mlrsearch-03, https://datatracker.ietf.org/meeting/109/materials/slides-109-bmwg-multiple-loss-ratio-search-00
> _______________________________________________
> bmwg mailing list
> bmwg@ietf.org
> https://www.ietf.org/mailman/listinfo/bmwg

_______________________________________________
bmwg mailing list
bmwg@ietf.org
https://www.ietf.org/mailman/listinfo/bmwg