Not really relevant to networking, but I firmly believe hash tables (and hashing) had a concrete starting point within recorded history, which appears to be January 1953.
Fascinating! I delved into Knuth's "TAOCP Volume 3", specifically the Hashing section, and indeed:
> The idea of hashing appears to have been originated by H. P. Luhn, who wrote an internal IBM memorandum in January 1953 that suggested the use of chaining; in fact, his suggestion was one of the first applications of linked linear lists.
Unfortunately, I couldn't locate the memo. It seems they never made it public. However, I stumbled upon a nice paper from 1953 in which he discusses enhancing search engines by refining sets - http://jonathanstray.com/papers/Luhn-SearchEngine-1953.pdf
Knuth also references Arnold I. Dumey, who appears to be the first to describe hash tables in open literature. I was able to retrieve his paper: https://archive.org/details/sim_computers-and-people_1956-12.... Dumey initiates with an O(log n) solution using the "twenty questions" game, subsequently explaining how we'd be better off if we could do computation before we access the memory. I found his introduction to the hash function rather intriguing:
> A certain manufacturing company had a parts and assemblies list of many thousands of items. A mixed digital and alphabetic system of numbering items was used, of six positions in all. Eight complex machines or assemblies were sold to the public. These had item numbers taken from the general system. In setting up a punch card control system on these eight items it was first proposed to record the entire six digit number for each item. However, examination of the eight assembly numbers disclosed that no two were alike on the fourth digit. It was therefore sufficient, for sorting purposes, merely to record the fourth digit, thereby releasing five badly needed information spaces for other purposes.
> This rather extreme case indicates that an examination of the item description may disclose a built-in redunancy which can be used to cut the field down to practical size.
He further discusses handling duplicates and introduces chaining:
> Adjust the addressing scheme, according to a method which will be described later, to reduce the number of direct addresses, and use the excess locations to store overflows. Put the overflow address at the tail end of stored item information. What the best reduction is varies from case to case. Note that the expectation of the number of accesses to be made goes up when these methods are used. At each access we check by using the complete item description, usually.
And discusses how a somewhat efficient hash address can be constructed by diving a prime number and using the remainder:
> Consider the item description as though it were a number in the scale of 37 or whatever. Or write it as a binary number by using the appropriate punched tape coding. Divide this number by a number slightly less than the number of addressable locations (the writer prefers the nearest prime). Throw away the quotient. Use the remainder as the address, adjusting to base 10, as the case may be.
When people turn up at the IETF and want to repeat a bad idea, that's the kind of thing they say. They say "the reasons why foo was bad don't necessarily apply to bar" while waving their hands. They try try to make it sound as if the reasons actually don't apply, usually without having much idea about what the reasons were.
Because often they DIDN'T fail the first time. It's just that when the next batch of devs decided they needed something, they didn't bother learning from the previous generation, and instead re-did every mistake of the past 30 years, to finally "invent" the already-working approach that had been there for decades.
One example that springs to mind is GUI code. We've gone through 3 cycles of that so far (including the original).
We went from sending our code to run at mainframe owned by big corporation and leased monthy for a price to sending our code to big corporation to run at not-mainframe for a monthly price
There's a lot of wheel reinvention going on in our industry.
Take Protocol Buffers. It exists because "ASN.1 sucks", but it's got all the problems that DER had, so it's really just a bad reinvention of ASN.1. In just the context of serialization formats you'll find a mind boggling amount of wheel reinvention. From S-expressions to all the 1980s RPCs (Apollo Domain, ONC, DCE, ...) to COM to all the ASN.1 encoding rules, to XML and FastInfoSet, to JSON and all the binary JSONs out there, to Protocol Buffers and Flat Buffers and... It's nuts. It goes on an on. And there's one or several RPCs for every one of these.
I am not sure whether they (IETF) have managed to retain their humor, but some great "truths", such as:
" With sufficient thrust, pigs fly just fine. However, this is not necessarily a good idea. It is hard to be sure where they are going to land, and it could be dangerous sitting under them as they fly overhead."
"It is always something."
"It is more complicated than you think."
Then:
"This RFC raises no security issues. However, security protocols are subject to the fundamental networking truths."
and
"The references have been deleted in order to protect the guilty and avoid enriching the lawyers."
> With sufficient thrust, pigs fly just fine. However, this is not necessarily a good idea. It is hard to be sure where they are going to land, and it could be dangerous sitting under them as they fly overhead.
Not sure I understand how this applies to networking?
I saw some forcepoint contraption forcing a MITM proxy to all http traffic by injecting a DLL in each process.
With sufficient manpower and infosec mandate, it got implemented just fine. But its incomplete buggy win32 API emulation landed on random applications, crashing them, and automatic updates and https got disabled left and right because the MITM flying over the heads of applications validating their certs
Applying significant force or effort to achieve a narrow definition of success will have unhappy consequences. Understand the entire system before rushing toward a solution.
Windows AD is the worst culprit here. Most times when something breaks that can not possibly be linked to DNS, the AD is bridging the failure in some way.
That said, yeah, I'd bet the large majority of bind installations are broken too. It's just that DNS really resists failure, and the GP isn't exactly about when it fails.
I have run TCP/IP networks of thousands of machines before all the automated tooling that's around these days to make this not cause you to loose your sanity. I've seen many of the possible cascading failure modes there are to see at this point[1]. I stand by my claim that DNS is one of the most unreliable parts of the jenga tower though.
[1] eg the first time I had root on a unix box I accidentally advertised it as a gateway over bgp and had all the "outbound" tcp traffic for the business park our office was in and a small ISP coming into my box and timing out. Yeah bgp and routing protocols are also common causes of failure, but DNS is worse.
If I haven’t posted this RFC to a new group I am working with, the collaboration is still new and we haven’t fully bonded. This RFC will be true and useful long after TCP is a historical relic.
Next time I see a terrible comedian I will wonder if they could have been inventing the internet instead. It's strange to read humour from an age when jokes didn't have to be pro level mind blowing to be funny though. Simpler times.
38 comments
[ 3.1 ms ] story [ 91.0 ms ] thread> The idea of hashing appears to have been originated by H. P. Luhn, who wrote an internal IBM memorandum in January 1953 that suggested the use of chaining; in fact, his suggestion was one of the first applications of linked linear lists.
Unfortunately, I couldn't locate the memo. It seems they never made it public. However, I stumbled upon a nice paper from 1953 in which he discusses enhancing search engines by refining sets - http://jonathanstray.com/papers/Luhn-SearchEngine-1953.pdf
Knuth also references Arnold I. Dumey, who appears to be the first to describe hash tables in open literature. I was able to retrieve his paper: https://archive.org/details/sim_computers-and-people_1956-12.... Dumey initiates with an O(log n) solution using the "twenty questions" game, subsequently explaining how we'd be better off if we could do computation before we access the memory. I found his introduction to the hash function rather intriguing:
> A certain manufacturing company had a parts and assemblies list of many thousands of items. A mixed digital and alphabetic system of numbering items was used, of six positions in all. Eight complex machines or assemblies were sold to the public. These had item numbers taken from the general system. In setting up a punch card control system on these eight items it was first proposed to record the entire six digit number for each item. However, examination of the eight assembly numbers disclosed that no two were alike on the fourth digit. It was therefore sufficient, for sorting purposes, merely to record the fourth digit, thereby releasing five badly needed information spaces for other purposes.
> This rather extreme case indicates that an examination of the item description may disclose a built-in redunancy which can be used to cut the field down to practical size.
He further discusses handling duplicates and introduces chaining:
> Adjust the addressing scheme, according to a method which will be described later, to reduce the number of direct addresses, and use the excess locations to store overflows. Put the overflow address at the tail end of stored item information. What the best reduction is varies from case to case. Note that the expectation of the number of accesses to be made goes up when these methods are used. At each access we check by using the complete item description, usually.
And discusses how a somewhat efficient hash address can be constructed by diving a prime number and using the remainder:
> Consider the item description as though it were a number in the scale of 37 or whatever. Or write it as a binary number by using the appropriate punched tape coding. Divide this number by a number slightly less than the number of addressable locations (the writer prefers the nearest prime). Throw away the quotient. Use the remainder as the address, adjusting to base 10, as the case may be.
When people turn up at the IETF and want to repeat a bad idea, that's the kind of thing they say. They say "the reasons why foo was bad don't necessarily apply to bar" while waving their hands. They try try to make it sound as if the reasons actually don't apply, usually without having much idea about what the reasons were.
One example that springs to mind is GUI code. We've gone through 3 cycles of that so far (including the original).
Another is programming languages.
We went from sending our code to run at mainframe owned by big corporation and leased monthy for a price to sending our code to big corporation to run at not-mainframe for a monthly price
Take Protocol Buffers. It exists because "ASN.1 sucks", but it's got all the problems that DER had, so it's really just a bad reinvention of ASN.1. In just the context of serialization formats you'll find a mind boggling amount of wheel reinvention. From S-expressions to all the 1980s RPCs (Apollo Domain, ONC, DCE, ...) to COM to all the ASN.1 encoding rules, to XML and FastInfoSet, to JSON and all the binary JSONs out there, to Protocol Buffers and Flat Buffers and... It's nuts. It goes on an on. And there's one or several RPCs for every one of these.
" With sufficient thrust, pigs fly just fine. However, this is not necessarily a good idea. It is hard to be sure where they are going to land, and it could be dangerous sitting under them as they fly overhead."
"It is always something."
"It is more complicated than you think."
Then:
"This RFC raises no security issues. However, security protocols are subject to the fundamental networking truths."
and
"The references have been deleted in order to protect the guilty and avoid enriching the lawyers."
Not sure I understand how this applies to networking?
With sufficient manpower and infosec mandate, it got implemented just fine. But its incomplete buggy win32 API emulation landed on random applications, crashing them, and automatic updates and https got disabled left and right because the MITM flying over the heads of applications validating their certs
To paraphrase, you can force a square peg into a round hole if you push hard enough, but it will probably lead to instability in unpredictable places.
E.g. you could probably tunnel all your corporate traffic through DNS if you try hard enough, but it's probably a bad idea.
* https://www.craftcomputing.store/product/hip-flask-in-case-o...
Maybe it's because I don't use bind.
Windows AD is the worst culprit here. Most times when something breaks that can not possibly be linked to DNS, the AD is bridging the failure in some way.
That said, yeah, I'd bet the large majority of bind installations are broken too. It's just that DNS really resists failure, and the GP isn't exactly about when it fails.
[1] eg the first time I had root on a unix box I accidentally advertised it as a gateway over bgp and had all the "outbound" tcp traffic for the business park our office was in and a small ISP coming into my box and timing out. Yeah bgp and routing protocols are also common causes of failure, but DNS is worse.
https://twitter.com/jdub/status/739110670562557952
Also (of course) there is a Wikipedia list of funny RFCs, many with a similar publish date: https://en.wikipedia.org/wiki/April_Fools%27_Day_Request_for...
Chef’s kiss