How to manage serial numbers

Paul Rubin <no.email@nospam.invalid> wrote:
> Theo Markettos <theom+news@chiark.greenend.org.uk> writes:
> > for (each request)
> >   printf("ID = %x\n", rand());
> > ... pay close attention to your system's rand() implementation to
> > check it's 32 bits long and has a 2^32 bit sequence length.
> 
> If you generate perfectly random 32-bit numbers you should expect
> to see duplicates after around 64k, due to the birthday paradox.

Interesting, never thought of the birthday paradox in this context.

He could use a linear feedback shift register, which can be set up
to have specific sequence lengths:

http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

-- 
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

Nils M Holm <news2009@t3x.org> writes:
> He could use a linear feedback shift register, which can be set up
> to have specific sequence lengths:

That's no different for his purposes from using a sequential counter:
you have to carefully maintain state across multiple runs, etc., which
is what randomness aimed to avoid.

Paul Rubin <no.email@nospam.invalid> wrote:
> Nils M Holm <news2009@t3x.org> writes:
> > He could use a linear feedback shift register, which can be set up
> > to have specific sequence lengths:
> 
> That's no different for his purposes from using a sequential counter:
> you have to carefully maintain state across multiple runs, etc., which
> is what randomness aimed to avoid.

True. But then the same applies to any other PRNG, doesn't it? Either
you use a specific cycle length (2^32 in this case) then you have to
maintain state. Or you use a much longer cycle length with different
seeds across sites, but in this case you you will very probably generate
duplicates, because you have to use modulo to get 32-bit output.

-- 
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

Nils M Holm <news2009@t3x.org> writes:
> True. But then the same applies to any other PRNG, doesn't it?

The idea is to use a real RNG, not a PRNG.  Typically those are made by
digitizing electrical noise and then running the output through a hash
function.  You come pretty close to this by using such randomness to
seed a PRNG with sufficiently wide internal state.  There is an
extensive literature about this, mostly in cryptography but some in
other areas.

On 04/11/2014 21:18, Paul Rubin wrote:
>
> If you generate perfectly random 32-bit numbers you should expect
> to see duplicates after around 64k, due to the birthday paradox.

Easy to handle: when you have generated a new random number, simply 
check it against the database, and generate a new one if it exists.

-- 
Torfinn Ingolfsen,
Norway

On 10/04/14 21:25, Paul Rubin wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> That was my first thought.  If you think it is hard to generate a
>> sequence of unique serial numbers, you really are in the wrong
>> business.
> 
> Depending on the requirements, it can be harder than it sounds.
> Client/server is one approach, but do you really want to have to stop
> your manufacturing line just because an internet connection went down?
> Even if the internet stays up, does its very presence mean you have to
> deal with a bunch of resulting potential security issues?  Do you really
> want to sign up to keep administering that database across the entire
> production life of the product, that might be decades, just for the sake
> of keeping the serial numbers sequential?  Etc. etc.
> 

Why do you want to bring "the internet" into this?  He wants a server
that can track the numbers and other information, and client PC's to do
the programming.  The only practical way to keep track of this
information is in a database, and any database server will have a way to
provide guaranteed different unique serial numbers to client programs.
PostgreSQL, as recommended by Andrew (it would be my recommendation too)
is free but has a feature list that makes most top-tier commercial
databases envious.

So you have a server with PostgreSQL, and as many client PC's as you
want connected to it.  If you want extra safety, PostgreSQL will do
clustering.  And if you want to do things in parallel at separate sites,
and feel that the internet is unreliable in your part of the world, then
just set up a duplicate server and start it with a different base
number. (10,000 per month for 20 years gives 2.4M devices - start server
2 at 100M to have some leeway).  And if you want to do things cheaply,
remember that you can happily run your PostgreSQL server on the client
machine instead of a dedicated server.

On 12/04/14 00:23, George Neuner wrote:
> On Fri, 11 Apr 2014 12:56:21 -0500, "antedeluvian"
> <63015@embeddedrelated> wrote:
> 
>>>
>>> Any ideas?
>>>
>> If you are using some form of Ethernet, how about a system using or based
>> on the MAC address?	   
> 
> Manufacturer assigned MAC addresses are *not* guaranteed to be unique
> ... they really only are a best effort.  
> 
> Moreover, many (most?) chips allow the MAC address to be changed by
> software.  Multiport NICs frequently ship with all the ports set
> identically and the software _must_ change them or network fabric will
> be driven crazy.  Becomes interesting when you have many such NICs in
> the same network.
> 
> George
> 

MAC addresses don't have to be unique.  They simply have to be unique
when they are on the same physical network (and same VLAN).  If you have
a multiport NIC then it is highly unlikely that two ports will be
connected to the same network (channel bundling is handled separately,
and has no problem with non-unique MAC addresse as long as the shared
addresses are at the same end of the link).

I have set up a production/programming line where the network cards are
programmed with the OUID part of the MAC address in the first stage, and
then are connected together in a network for second stage programming
and unique MAC assignment.  So at that point, there can be a dozen cards
with the same MAC address connected to the same switch - but each port
on the switch is given a different VLAN number and everyone is happy.

Paul Rubin <no.email@nospam.invalid> wrote:
> Theo Markettos <theom+news@chiark.greenend.org.uk> writes:
> > for (each request)
> >   printf("ID = %x\n", rand());
> > ... pay close attention to your system's rand() implementation to
> > check it's 32 bits long and has a 2^32 bit sequence length.
> 
> If you generate perfectly random 32-bit numbers you should expect
> to see duplicates after around 64k, due to the birthday paradox.

This is a pseudorandom generator, not true randomness that you'd get from
/dev/random.  You need to pick a PRNG it has a known sequence length and is
guaranteed not to repeat in this length.  Relying on the system rand() is
probably a bad plan for repeatability reasons, but such PRNGs exist 
(LFSRs are but one example).

Theo

Theo Markettos <theom+news@chiark.greenend.org.uk> writes:
> This is a pseudorandom generator, not true randomness that you'd get
> from /dev/random.  You need to pick a PRNG it has a known sequence
> length and is guaranteed not to repeat in this length.

You mean before a single output repeats, as opposed to the internal
state (and therefore the entire sequence) repeating?  Well ok, but in
that case it's no different from a counter.

> Relying on the system rand() is probably a bad plan for repeatability
> reasons, but such PRNGs exist (LFSRs are but one example).

There is no point to using this type of PRNG for the application at
hand, since it requires maintaining exact state across production runs.
The reason for suggesting randomness in the first place was to avoid
that requirement.

Paul Rubin <no.email@nospam.invalid> wrote:
> Theo Markettos <theom+news@chiark.greenend.org.uk> writes:
> > Relying on the system rand() is probably a bad plan for repeatability
> > reasons, but such PRNGs exist (LFSRs are but one example).
> 
> There is no point to using this type of PRNG for the application at
> hand, since it requires maintaining exact state across production runs.
> The reason for suggesting randomness in the first place was to avoid
> that requirement.

But even if you use true randomness, you are still left with the
same dilemma, because a true random distribution will contain the
same value multiple times, and even if you could make sure that this
probably will not happen (by giving the RNG a very large range),
scaling the output of the RNG down to 32 bits will still generate
duplicates way before exhausting the 32-bit range.

The only way to avoid this is an LFSR (or an equivalent function),
but this is basically a counter, as you already pointed out, and
that will introduce state.

The only stateless solution I see is to use a (P)RNG with different
seeds and a longer serial number.

-- 
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org