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:
-- Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
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
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.
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
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.
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.
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
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.
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
Yes, you can't use the RNG approach with 32 bit device ID's if there are more than a few devices. That's why I suggested 128 bit ID's. Those would be ok in some applications where usually only computers have to distinguish or copy the ID's, but ID's that large are a bit inconvenient for humans to enter into keyboards etc. If 32 bits is a requirement, which apparently it is, then a stateful approach is the only way I can see.
Can you use the MAC address of the Ethernet port being used to connect to the server? You may have to put it in band since a switch can replace the MAC address.
So you'd need a cross reference from MAC addresses to serial numbers on the server.
If your MAC addresses are not in OTP ROM on the client nodes, you have another problem- although having a default MAC address may actually work out. You'd need to issue a new MAC address for new nodes.
What won't work (reliably) is having two nodes with the same MAC address at the same time. The same IP address must also be avoided.
If the server can 1) have instrumentation to pull the DHCP tables for the network and 2) use that to identify nodes, then that might help.
-- Les Cargill
They simply *HAVE* to be globally unique unless you can prove you'll never have a collision... and IMO, you never can unless you have significant configuration controls in deployment.
The only way you can assure uniqueness of MAC addresses is by local enforcement - one company used a tape of OTP parts. In this fellow's case, assignment of MAC addresses could be part of his server, but you have to plan for how the deployment can handle non-unique MAC addresses unless it's tightly controlled.
Simply RMAing "collided" nodes might be a good solution. But probably not.
Right - dual NICs on the same node can use the same MAC, generally.
I still wouldn't. Some people's bridge implementations on switches may or may not work right.
This is fine if you can assure that VLAN configuration can be part of the deal. Sometimes you have Randomly Purchased Switches and you cannot do that.
-- Les Cargill
You *HAVE* to have local controls to never allow duplicate MAC addresses into the wild. I suppose you can train people to recognize duplicate address misbehavior but that sounds more expensive.
*Shudder*-- Les Cargill
If you can RFID them, you can print off serial numbers on barcode stickers. Much more manageable.
You *HAVE TO DESIGN THIS PROCESS*. You cannot just throw boxes at it.
Much.
But the map between the barcode and serial number must then be maintained. If they're identical, that cannot break...
-- Les Cargill
Well considering for last 2 years some PCB manufacturers have been doing this by embedding the RFID inside the PCB for example
PCB redeisgin may not even be necessary.
As to the Process side I reckon it will be less than what is currently being discussed for the whole process.
of
--
Paul Carpenter | paul@pcserviceselectronics.co.uk
PC Services
Raspberry Pi Add-ons
Timing Diagram Font
For those web sites you hate
That's what we do - the database that generates the parts list and the stock levels also generates the serial numbers for the batch. I print them off in A4 sheets. (Still can't find any small enough for the very small boards, without going to those roll printer things which I find a PITA).
So I am thinking of going to simple batch / date code tracking and dropping the serial numbers - will be a shame since we have the serial numbers going back to our first board, serial number 1.
[...]-- John Devereux
I'd worry about them falling off. Laser etching might or might not be a practical alternative.
You are overstating the case.
It is /expected/ that MAC addresses will be globally unique - but there is no authority or rules to enforce that. This is unlike things like Bluetooth or USB ids and serial numbers - if you want to be able to use the trademarked logos for these interfaces, then you have to follow the rules about unique ids. And while there /is/ an authority that registers and administers the 24-bit OUID part of MAC addresses, you are not obliged to use one.
If you sell networked equipment to a customer without giving specific requirements about the networking, then the customer can expect the MAC address to be globally unique, and can reasonably claim against you if there is a conflict. But that's just general trade rules - if you sell something, people expect it to work in a particular way.
There are lots of circumstances in which people can and do make networked equipment without globally unique MACs. For some of these, you have enough control to be sure there is no conflict (such as in the case I mentioned, where cards temporarily have identical MAC addresses at one stage of production programming). Maybe you are building systems that each customer will only have one of, or you have other limitations in the network.
But it is also not unreasonable to "cheat", and it is very common during development and testing. If you are making larger quantities of a system, then an official OUID is not that expensive and looks more professional. But for earlier work, it is common to pick an OUID of another company, or an unallocated OUID, or a "locally administered" OUID, and then a random 24-bit number. So you pick Ford's OUID and a random number - what are the chances of that causing a collision during your development? Or just pick a full 48-bit random number - what are your chances of collision then? Another common trick for development is to copy the MAC address from old and unused equipment.
Of course it is best to have a proper OUID and proper control over the MAC addresses you allocate from it. But don't be fooled into thinking that MAC addresses really are globally unique, or really have to be globally unique.
You have to be extraordinarily incompetent to end up with collided nodes in practice, so RMA'ing them should be fine.
Of course I can be sure that the VLAN configuration is correct - it is part of the production and programming line. Why would there be a "randomly purchased switch" in a production facility - especially one where the setup of the switch is an important component in the programming line?
I have been bit by it. Wasn't my doing, but I still had to untangle it.
People expect things to work. Two identical MAC addresses on the same collision domain or VLAN or what have you doesn't work.
That, I don't particularly have a problem with but it's a matter of production control.
Still...
True.
You'll usually inherit one from an acquisition. There's always been an acquisition...
SFAIK, best practices still are to have them be as unique as possible as early as possible. It's worth putting some thought into this.
Because somebody may or may not know the procedure for replacing a switch.
This ignores IPV6 altogether - that can be a disaster on the hoof when it comes your way.
-- Les Cargill
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.