It's been a while since I worked on this, but back then over 80% NAT devices used simple +1 port allocation. Some fraction was using other increments and only O

It's been a while since I worked on this, but back then over 80% NAT devices used simple +1 port allocation. Some fraction was using other increments and only OpenBSD used truly random overloading. The main issue with port prediction in general wasn't making it per se, but making it quick enough so that it won't expire. From what I remember ingress TCP filtering was universally very dumb - if there was a SYN out, anything on the same quartet of IP/ports was allowed in. That was on a sample of several thousand devices, though most of these were of consumer grade. It was also few years before the paper you linked to above.