One bit network masks
Én bit netværksmasker
The number of IP addresses is:
Antallet af IP adresser er:
4.2949e9 IPv4 addresses
3.4028e38 IPv6 addresses
4.2949e9 IPv4 adresser
3.4028e38 IPv6 adresser
The addresses are simply bitstrings of length 32 and 128 respectively. So the numbers are just 232 and 2128.
Adresserne er simpelthen bitstrenge af henholdsvis længde 32 og 128. Så antallene er bare 232 og 2128.
But how many networks are there?
Men hvor mange netværk er der?
Networks
Netværk
In the following I will only use IPv4, as it is simpler. But our findings will also apply to IPv6.
I det følgende bruger jeg kun IPv4, fordi det er simplere. Men vores resultater vil osse gælde IPv6.
Networks have two parts, a network address and a network mask. At first glance it looks like two IP addresses, because it is two bitstrings of length 32.
Netværk har to dele, en netværksadresse og en netværksmaske. Det ligner umiddelbart to IP adresser, fordi det er to bitstrenge af længde 32.
The second bitstring, the network mask, always starts with a run of 1s, after which it is all 0s. Written with bits, the example looks like this:
Den anden bitstreng, netværksmasken, starter altid med en række 1er, hvorefter resten er 0er. Skrevet med bits ser eksemplet sådan ud:
As the mask always has this pattern, many just writes networks by using the number of 1s in the mask, like this:
Da masken altid har dette mønster, skriver mange bare netværket med det antal 1er der er i masken, sådan her:
This is called CIDR notation.
Det kaldes CIDR notation.
Now, let us just for the fun of it imagine that we want to save some memory.
Lad os nu for sjov forestille os at vi gerne vil spare noget memory.
Notice that the mask only has 32 bits, so it can only take 33 different values. We clearly dont need 32 bits to write those values. It can be done with 6 bits. So our example network could be written this way:
Læg mærke til at masken kun består af 32 bits, så den kan kun tage 33 forskellige værdier. Vi behøver helt sikkert ikke 32 bits for at skrive de værdier. 6 bits kan gøre det. Så vores eksempel kunne se sådan ud:
But it can be done even better than that. Notice that the network address ends in 0s the same way that the 32 bit mask does. So we should be able to save something here. There are some complications though, because the number of 0s depend on the mask, so it is variable. Also the network address can be valid for more than one mask. At least all smaller masks. So what to do?
Men det kan gøres bedre endnu. Læg mærke til at netværksadressen slutter med 0er på samme måde som 32 bit masken gør det. Så vi må kunne spare noget her. Det er dog ikke så ligetil, for antallet af 0er afhænger af masken, så det er variabelt. Desuden kan netværksadressen være gyldig for mere end én maske. I det mindste for alle mindre masker. Så hvad gør vi?
Well, as you guessed it from the headline, we can effectively reduce the mask down to one bit. This is how to do it:
Jo, som du har gættet fra overskriften, så kan masken effektivt set reduceres til én bit. Det gøres sådan her:
Take only the part of the network address where the 32 bit mask is 1. Note what the last bit in it is. Then append the opposite bit until the length is n+1.
Tag kun den del af netværksadressen hvor 32 bit masken er 1. Notér hvad sidste bit er i den. Vedhæft så den modsatte bit indtil længden er n+1.
For our example, the result will look like this:
I vores eksempel vil resultatet se sådan ud:
Can we save more memory than this? No. All /32 networks are the same as all IP addresses, and as we know they take 32 bits to represent. So using only 32 bits will not leave any space to represent networks larger than /32.
Kan vi spare mere memory end det? Nej. Alle /32 netværk svarer til alle IP adresser, og det tager som bekendt 32 bits at repræsentere dem. Så har vi kun 32 bits, er der ikke plads til netværk større end /32.
0.0.0.0/0
When the 32 bit mask only contains 0s, that is when the network is 0.0.0.0/0, our method for finding the one bit network mask breaks down. There are no bits in the network address we can start with. We dont know whether to fill the 33 bits with 0s or 1s.
Når 32 bit masken kun består af 0er, altså når netværket er 0.0.0.0/0, så bryder vores én bit netværksmaske metode sammen. Der er ikke nogen bits i netværksadressen, som vi kan starte med. Vi ved ikke om vi skal fylde de 33 bits med 0er eller 1er.
I have chosen to say that we should use 0s.
Jeg har valgt at sige der skal bruges 0er.
If you start doing arithmetic with bitstrings, you find out that the bitstring that has only 1s in it, behaves in weird ways. So it is indeed called "weird". That is the reason I chose that it also should be the one that is weird when we are working with one bit network masks.
Hvis man begynder at lave aritmetik med bitstrenge finder man ud af at bitstrengen der kun har 1er i sig, opfører sig mærkeligt. Derfor bliver den ofte kaldt for "weird". Det er grunden til at jeg har valgt det osse er den der skal være weird når det gælder én bit netværksmaskerne.
But how many?
Men hvor mange?
It is simple to reverse the "compression" I just showed you. All you have to do is to reverse the steps.
Det er nemt at vende "komprimeringen", som jeg lige viste dig, om. Det eneste man skal gøre er at tage skridtene baglæns.
Now, note two interesting facts. 1: No matter what bitstring of length 33 that we receive, it can be "decrompessed" into a network. 2: Two different non-weird strings will always "decompress" into two different networks...
Bemærk nu to interessante egenskaber. 1: Uanset hvilken bitstreng af længde 33 vi får, kan den "dekomprimeres" til et netværk. 2: To forskellige ikke-weird strenge vil altid "dekomprimere" til to forskellige netværk...
What we have is better than compression and decompression. We have a one-to-one correspondence between networks and non-weird bitstrings of length 33.
Det vi har er bedre end komprimering og dekomprimering. Vi har en en-til-en korrespondance mellem netværk og ikke-weird bitstrenge af længde 33.
That makes it easy to answer the question from the beginning of the article... How many networks are there?
Det gør det nemt at svare på spørgsmålet fra starten af artiklen... Hvor mange netværk er der?
8.5899e9 IPv4 networks
6.8056e38 IPv6 networks*
8.5899e9 IPv4 netværk
6.8056e38 IPv6 netværk*
Which is 233-1 and 2129-1 respectively.
Som er henholdsvis 233-1 og 2129-1.
*) This is a theoretical number. In IPv6 all subnets should be /64, giving us instead a number of 265-1 ≈ 3.6893e19 IPv6 networks. But this number also comes with a caveat, as networks smaller than /64 are being regularly used in a number of cases.
*) Dette er et teoretisk tal. I IPv6 bør alle subnets være /64, hvilket giver os et antal på 265-1 ≈ 3.6893e19 IPv6 netværk. Men det tal kommer med sine egne forbehold, da netværk mindre end /64 bruges regelmæssigt i en række tilfælde.
In practice
I praksis
The reason IPv4 networks are represented by network addresses and masks, is that they are incredibly efficient to compute with. With that representation most computations can be done with bitwise logic operations, which are part of the instruction set of any decent processor. You dont get much faster computation than that.
Grunden til at IPv4 netværk repræsenteres med netværksadresse og maske, er at de er utroligt effektive at beregne på. Med den repræsentation kan de fleste beregninger klares med bitvis logiske oparationer, som er i enhver hæderlig processors instruktionssæt. Beregninger bliver ikke meget hurtigere end det.
You may also have noticed that processors are the reason behind the size of the bitstrings, as 32 bits was the word size of the powerful processors, back when IPv4 was designed.
Det kan være du osse har lagt mærke til at processorerne er grunden til størrelsen af bitstrengene, da 32 bits var word size for de stærke processorer dengang IPv4 blev designet.
The algorithms for, and storage of IPv6 networks are more complicated. But their representation is also heavily influenced by processors and performance.
Algoritmerne for, og lagringen af IPv6 netværk er mere komplicerede. Men deres repræsentation er osse stærkt påvirket af processorer og performance.
Indeed, hardware aligned formats permeates all of networking. Network formats are possibly the closest to assembler that you will get for data formats.
Faktisk gennemsyrer hardwareorienterede formater alle dele af netværk. Netværksformater er nok det tætteste som dataformater kommer på assembler.
In general
Generelt
If we forget networking for a moment, what we are really dealing with when we have a "network", is a bitstring of length less than or equal to 32. Let us also forget the number 32, then what we have is a bitstring of length less than or equal to n. So our correspondance applies in general between those bitstrings, and non-weird bitstrings of fixed length n+1.
Hvis vi glemmer netværk et øjeblik, så er det vi i virkeligheden har når vi har et "netværk", en bitstreng med længde mindre end eller lig med 32. Lad os osse glemme tallet 32, så er det vi har en bitstreng med længde mindre end eller lig med n. Vores korrespondance gælder helt generelt mellem disse bitstrenge og ikke-weird bitstrenge af fast længde n+1.
The functions are very simple. One is the inverse of the other, and vice versa. Here they are in pseudo code:
Funktionerne er meget simple. En er den andens invers, og omvendt. Her er de i pseudokode:
function to_fixed( b , n )
// b: Bitstring of length ≤ n.
// n: Positive integer.
// Map b into a bitstring of length n+1.
if b is empty
set lastbit to 1
else
set lastbit to the last bit of b
append (not lastbit) to b as long as its length is ≤ n
return b
function to_fixed( b , n )
// b: Bitstreng af længde ≤ n.
// n: Positivt heltal.
// Afbild b til en bitstreng af længde n+1.
hvis b er tom
sæt lastbit til 1
ellers
sæt lastbit lig med den sidste bit i b
vedhæft (not lastbit) til b sålænge dens længde er ≤ n
returnér b
function from_fixed( b )
// b: Non-weird bitstring of length n+1.
// Map b into a bitstring of length ≤ n.
set lastbit to the last bit of b
remove the last bit of b as long as it is equal to lastbit
return b
function from_fixed( b )
// b: Ikke-weird bitstreng af længde n+1.
// Afbild b til en bitstreng af længde ≤ n.
sæt lastbit lig med den sidste bit i b
fjern den sidste bit i b sålænge den er lig med lastbit
returnér b
These functions can also gain from low-level instructions. But because they contain loops, they can never be as efficient as the address+mask functions.
Disse funktioner kan osse udnytte lav-niveau instruktioner. Men da de indeholder løkker, kan de aldrig blive lige så effektive som adresse+maske funktionerne.
