Re: Pseudorandom Flow Labels

Brian E Carpenter <brian.e.carpenter@gmail.com> Wed, 06 April 2011 07:17 UTC

Return-Path: <brian.e.carpenter@gmail.com>
X-Original-To: ipv6@core3.amsl.com
Delivered-To: ipv6@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 357ED3A68C7 for <ipv6@core3.amsl.com>; Wed, 6 Apr 2011 00:17:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -103.599
X-Spam-Level:
X-Spam-Status: No, score=-103.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 60KIMjxb-JMT for <ipv6@core3.amsl.com>; Wed, 6 Apr 2011 00:17:08 -0700 (PDT)
Received: from mail-wy0-f172.google.com (mail-wy0-f172.google.com [74.125.82.172]) by core3.amsl.com (Postfix) with ESMTP id 181963A68BB for <ipv6@ietf.org>; Wed, 6 Apr 2011 00:17:07 -0700 (PDT)
Received: by wyb29 with SMTP id 29so1107331wyb.31 for <ipv6@ietf.org>; Wed, 06 Apr 2011 00:18:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:message-id:date:from:organization:user-agent :mime-version:to:cc:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=mjf8j48GEttt1dBKkFer/5W6/LudbcgYvfuq2npBZoo=; b=oCC6MFVEmkdYTbG4zedJYqUDKY7n7Hwzn5ucyvYLytQ5b0PAuBnfKHalM883c+UUsL U70LaNwn8mBXt7uxmTK+AZv6fiGc0Si592QWGuH6Y5rBy7iovrIPTa2MfblzbhmXfxv0 QhAqyaj3cMKbb0zc9C6B3JCj2L388XkKMtcvw=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:organization:user-agent:mime-version:to:cc :subject:references:in-reply-to:content-type :content-transfer-encoding; b=ZX1C/yEnYsD9ZF/svu2sCBRr9u+SPNociLo42NVVSjS6hbwQgyaRUpS0cOz1MvTh1z IJgrt1AH+FACz2y+UFTrpbxdrcaUI8VDaJXYUlAsloy9rTSOw+aeTSj9sVlZgrYPjyU7 xrB8deW3N+eNywa4rkpODXLBp7jYfUbKWMkFA=
Received: by 10.216.171.133 with SMTP id r5mr6069219wel.91.1302074330634; Wed, 06 Apr 2011 00:18:50 -0700 (PDT)
Received: from [192.168.1.65] (host86-162-222-107.range86-162.btcentralplus.com [86.162.222.107]) by mx.google.com with ESMTPS id bs4sm155115wbb.52.2011.04.06.00.18.48 (version=SSLv3 cipher=OTHER); Wed, 06 Apr 2011 00:18:49 -0700 (PDT)
Message-ID: <4D9C13D5.1030800@gmail.com>
Date: Wed, 06 Apr 2011 19:18:45 +1200
From: Brian E Carpenter <brian.e.carpenter@gmail.com>
Organization: University of Auckland
User-Agent: Thunderbird 2.0.0.6 (Windows/20070728)
MIME-Version: 1.0
To: "Hemant Singh (shemant)" <shemant@cisco.com>
Subject: Re: Pseudorandom Flow Labels
References: <BD901061-96AC-4915-B7CE-2BC1F70861A5@castlepoint.net><201104052036.p35KaoHV019253@cichlid.raleigh.ibm.com><19204E85-5B6E-409C-B450-7E3AC5EF47FA@apple.com><201104052148.p35LmM9g019765@cichlid.raleigh.ibm.com><9ED6022F-6863-4267-A268-C73240098539@apple.com> <201104060008.p3608OlC022133@cichlid.raleigh.ibm.com> <5B6B2B64C9FE2A489045EEEADDAFF2C301391466@XMB-RCD-109.cisco.com>
In-Reply-To: <5B6B2B64C9FE2A489045EEEADDAFF2C301391466@XMB-RCD-109.cisco.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Cc: Thomas Narten <narten@us.ibm.com>, 6MAN Working Group <ipv6@ietf.org>
X-BeenThere: ipv6@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: "IPv6 Maintenance Working Group \(6man\)" <ipv6.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/ipv6>, <mailto:ipv6-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/ipv6>
List-Post: <mailto:ipv6@ietf.org>
List-Help: <mailto:ipv6-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ipv6>, <mailto:ipv6-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 06 Apr 2011 07:17:09 -0000

I have a quite strongly held belief that trying to be mathematically
precise (not to say pedantic) has never worked well in IETF protocols.
(OK, there is one possible exception, namely NTP.) Our implementors
are not going to understand subtleties such as 'low discrepancy'.
IMHO, arguing about the correct mathematical formulation is not quite the
point.

We do seem to agree that the important point is that the final output
of the hash function used to select between alternate routes is
uniformly distributed. Asking for flow label values that are reasonably
well distributed as input to that hash function is enough. Any stateless
method that provides this will do. Frankly I don't care whether we all
it pseudo-random, quasi-random, or mashed potato. (Counting from 1 will
not do, because it's stateful.)

Regards
   Brian Carpenter

On 2011-04-06 13:34, Hemant Singh (shemant) wrote:
> -----Original Message-----
> From: ipv6-bounces@ietf.org [mailto:ipv6-bounces@ietf.org] On Behalf Of
> Thomas Narten
> Sent: Tuesday, April 05, 2011 8:08 PM
> To: james woodyatt
> Cc: 6MAN Working Group
> Subject: Re: Pseudorandom Flow Labels
> 
> 
>> What is *required* is that the hash function (or whatever function
>> that is used) on the router maps the tuples in a *uniform* way across
>> the range of possible outputs.
> 
>> If you have 10 links, and all your Flow Labels are clustered around
>> low ten values, but in an approximately uniform way, a simple modulo
>> hash will get you the kind of distribution you need.
> 
>> The range of values of the flow label itself does not need to be
>> uniformly distributed.
> 
>> That is why incrementing a counter for each new flow provides adequate
>> properties. I remain unconvinced that we need to require that they
>> exhibit pseudo randomness, or even be uniform.
> 
>> If that is a requirement, I'd like to see the justification, not just
>> hand waiving.
> 
> How about something like the text below:
> 
> A property of the flow label is that when the flow label is used a key
> to a hash function the function produces a uniform distribution of hash
> values.  Thus, incrementing a counter for each new flow is one means to
> achieve the property described in the previous sentence. 
> 
> Hemant 
> --------------------------------------------------------------------
> IETF IPv6 working group mailing list
> ipv6@ietf.org
> Administrative Requests: https://www.ietf.org/mailman/listinfo/ipv6
> --------------------------------------------------------------------
>