Re: Pseudorandom Flow Labels

Fernando Gont <fernando@gont.com.ar> Wed, 06 April 2011 17:59 UTC

Return-Path: <fernando.gont.netbook.win@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 429453A696D for <ipv6@core3.amsl.com>; Wed, 6 Apr 2011 10:59:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.599
X-Spam-Level:
X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1]
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 I-GBojOE9z+V for <ipv6@core3.amsl.com>; Wed, 6 Apr 2011 10:59:34 -0700 (PDT)
Received: from mail-yw0-f44.google.com (mail-yw0-f44.google.com [209.85.213.44]) by core3.amsl.com (Postfix) with ESMTP id 0F2043A696C for <ipv6@ietf.org>; Wed, 6 Apr 2011 10:59:33 -0700 (PDT)
Received: by ywi6 with SMTP id 6so799109ywi.31 for <ipv6@ietf.org>; Wed, 06 Apr 2011 11:01:17 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:sender:message-id:date:from:user-agent :mime-version:to:cc:subject:references:in-reply-to :x-enigmail-version:openpgp:content-type:content-transfer-encoding; bh=8/tGWN75FcGtYhU5LWZvWjmqNYXV8pnBeHLX5a6i/kY=; b=lI2LK0IbqnPHEiEygLZgf58WrhN1dmFd58/D48GqSAcrgkBYGcB2OUu4DqhbbhCPen LETTEQhXB8w3lG74ep0VTo+PhtAZoT+jnTr/lbi17dcqI0/7eUCtPEo/px09b0aDeAo0 VB0ayh+UTEdDwzITIafmlHBSGnt3W8Ze1eDjc=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:x-enigmail-version:openpgp:content-type :content-transfer-encoding; b=uMp3QTDZYymLRiabAuNc6Adq4LFQoDpmOZx8TcItXAL/MVkHB7LV7Tyo/tqxf6Fr4V WeGKRD1ZsVgVvt1rEEdMIstA1uKc9owJMVco0zItBCIUGzvY981mNNbDtREP9oLysPbW 54n+y+sbrI3knQ6HMM1Mx42kAYeUFcz9s9OVw=
Received: by 10.236.78.33 with SMTP id f21mr1511835yhe.123.1302112877563; Wed, 06 Apr 2011 11:01:17 -0700 (PDT)
Received: from [192.168.123.101] ([190.48.201.131]) by mx.google.com with ESMTPS id l73sm270559yhn.77.2011.04.06.11.01.13 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 06 Apr 2011 11:01:16 -0700 (PDT)
Sender: Fernando Gont <fernando.gont.netbook.win@gmail.com>
Message-ID: <4D9CAA66.9090402@gont.com.ar>
Date: Wed, 06 Apr 2011 15:01:10 -0300
From: Fernando Gont <fernando@gont.com.ar>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.2.8) Gecko/20100802 Thunderbird/3.1.2
MIME-Version: 1.0
To: Thomas Narten <narten@us.ibm.com>
Subject: Re: Pseudorandom Flow Labels
References: <BD901061-96AC-4915-B7CE-2BC1F70861A5@castlepoint.net> <201104051958.p35JwaJP019044@cichlid.raleigh.ibm.com>
In-Reply-To: <201104051958.p35JwaJP019044@cichlid.raleigh.ibm.com>
X-Enigmail-Version: 1.1.1
OpenPGP: id=D076FFF1
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Cc: 6man List <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 17:59:35 -0000

On 05/04/2011 04:58 p.m., Thomas Narten wrote:
> At the core, my concern with "pseudo random" is that I (as an
> implementor) do not know what I have to do do satisfy that requirement
> and I think in some cases that cost is higher than justified by the
> benefit. The current documents do not provide enough concrete
> guidance, IMO. If we want folk to actually set the Flow Label to a
> good value, tell them what to do. Don't make them think too
> hard. Provide them with a suggested algorithm. Don't just say "make it
> psuedo random".

draft-gont-6man-flowlabel-security aims at addressing this issue.



> More to the point, if this could be done in a "stateless" manner,
> e.g., by the routine that sends IP datagrams, that would be
> nice. I.e., if the IP "send" routine could easily set the Flow Label
> whenever it was zero, in a "stateless" manner, that would almost
> guarantee we'd get wide spread implementation.

FWIW, all of the algorithms in the port randomization RFC (including the
hash-based ones) are stateless.



> I take it as a given that doing ECMP on the src/dst address gets you
> 80% of what you need today. Adding in the Flow Label (if set) will
> take you much further. I am not convinced you need real "pseudo
> randomness" in the Flow Label to get the benefits being called for.

I think that for this sort of ting, "pseudo-random numbers" are your
friend. There have been a variety of cases in recent history in which
predictable values have been used (TCP ISNs, IP IDs, TCP port numbers,
etc.), and only later we realized that there were implications to that.
-- which then lead to patches such that pseudo-random values were used,
instead.


>> 2) If we expect that if a intermediate router or switch is using
>> *just* the 3-tuple of {src_ip, dst_ip + flow_label} as input-keys to
>> compute a load-balancing hash algorithm, then the more random the
>> flow-label, the better load-distribution of /all/ traffic will be
>> across the LAG and/or ECMP paths.
> 
> Understood. But what you need for this is not (necessarily) pseudo
> randomness. Just sufficient variability (when combined with the
> src/dst) to get good distribution on the output side of the hash.

Agreed. For instance, the hash-based algorithm recommended in
draft-gont-6man-flowlabel-security results in a linear function for each
(src IP, dst IP) (that has a random offset...)




>> a) As a network operator I have no control over the number of IP
>>      addresses used by content farms or residential networks.
>>      Furthermore, it's not clear that as more & more machines (and,
>>      smartphones!) ship that support multiple CPU's and/or multiple
>>      cores that each of those discrete computing units will (or,
>>      should?) receive their own IP address.  With IPv6 that's at
>>      least a possibly, but perhaps due to "ease of development",
>>      that won't happen often, or at all.  If we strongly recommend a
>>      pseudo-random flow-label and a device is only capable of
>>      load-balancing using a 3-tuple, then I've at least got a
>>      [relatively] unique flow-label in the packet header to provide
>>      load distribution.
> 
> I think we can assume that if we use both the src/dst, we will get a
> good degree of distribution in the values. Adding the Flow Label gives
> more. I am just not convinced that to get good distribution we need to
> *require* (or strongly suggest) psuedo randomness in the Flow
> Lable. We know that by simply incrementing the Flow Label by 1 for
> each flow, we get sufficient distribution. That is *way* easier to
> implement than something else.

What we want is unpredictable flow numbers, with a low frequency of FL
reuse. A typical call to random() would be just *one*¨way to do it. But,
as noted, there are others.

For hash-based algorithms, you only compute the hash once for each flow.
Then you simply increment the FL for each packet you send for that flow.




> Now. What about TEPs? They have no way of knowing whether the port
> numbers being used provide proper randomness. That implies if they are
> going to generate pseudo-random Flow Labels, they have a *lot* more
> work to do. And to be sure that all packets from a given "flow" are
> given the same Flow Label, they may have to maintain state. i.e., so
> that subsequent packets from the same flow get assigned the same Flow
> Label value. 

Not necessarily: hash functions are your friend (whether you might or
might not want to implement this (e.g., for performance reasons) is a
different issue)

Thanks,
-- 
Fernando Gont
e-mail: fernando@gont.com.ar || fgont@acm.org
PGP Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1