Saturday, March 27, 2010

Simplified IP Addressing

Basics
The first question concerns what constitutes a Class A, or a Class B, etc. network. Novices have trouble remembering where each class begins and ends. Table 3 shows a schema to help with this. First, let's discuss some basics of binary numbers.
A byte is a grouping of eight binary bits. Since a binary bit is either a 0 or a 1, a byte consists of eight 0s and/or 1s. No mystery here. So 10010101 is one byte and 11100000 is another. How do we convert these to decimal numbers? It turns out that the right-most bit has a weight of 1 (2<+>0<+>). The next bit to its left has a weight of 2 (2<+>1<+>), the next has a weight of 4 (2<+>2<+>), i.e., two raised to the second power and so on:
2
or equivalently:
128  64  32  16  8  4  2  1     : decimal weights
Thus, the binary number 10101001 has a decimal equivalent of
1x1 + 1x8 + 1x32 + 1x128 = 169
If you assign contiguous 1s starting from the right, the above diagram can be used as a kind of calculator. Let's say you have 00001111 binary bits. To get the decimal equivalent, you could do the calculations the hard way, that is:
1x1 + 1x2 + 1x4 + 1x8 = 15
or you could note the following (taking our number):
128  64  32  16  8  4  2  1     :decimal weights
  0  0  0  0  1  1  1  1 :binary number
If you have all ones starting at the right side, you can simply take the weight of the first 0 bit (16 in this case), subtract 1, and you have 15—the decimal equivalent—without having to use a calculator. Thus, if all the bits on the right are 1s, you can determine the decimal value by using the above diagram as a kind of calculator. Note that the bits go up in powers of 2, so the ninth bit has a decimal weight of 256. So if you have a byte with all ones, i.e., 11111111, then it has a decimal value of 255 (256 -1). 255 appears many times in IP addressing.

Table 1. Decimal Equivalents for Netmasking

128 64 32 16 8 4 2 1 decimal
1 0 0 0 0 0 0 0 128
1 1 0 0 0 0 0 0 192
1 1 1 0 0 0 0 0 224
1 1 1 1 0 0 0 0 240
1 1 1 1 1 0 0 0 248
1 1 1 1 1 1 0 0 252
1 1 1 1 1 1 1 0 254
1 1 1 1 1 1 1 1 255
Now we need to construct another calculator for handy reference (see Table 1). There is a thing called netmasking, which I will discuss later on. Standard procedure says to start the masking from the left and work down. So, if you make the eighth, or high-order bit, 1 and the rest equal to 0, the decimal equivalent is 128; if you made the first three bits 1 and the rest 0, the decimal equivalent is 224, etc.

Table 2. Shortened Netmask Table

128 64 32 16 8 4 2 1 Binary
128 192 224 240 248 252 254 255 Decimal

This table works fine, but is a bit unwieldy. Table 2 shows a short version. It says that if your byte is 11100000, then the decimal equivalent value is 224. If this bothers you, just use Table 1.
IP Addresses
We have set the groundwork for IP addressing, and I will now discuss the standard IPv4 addresses. The IP addresses are sometimes called “dotted quad” numbers. There are five classes of IP addresses, i.e., A, B, C, D and E. Classes D and E are reserved so you can work with classes A, B and C. However, I will show all five here. The class is determined from the first byte. Thus, an IP address of 205.140.187.31 is a class C address, since the first byte is 205. How do I know that? Well, let's look at Table 3.

Table 3. Classes of IP Addresses


High-Ordered Byte
Class Binary Decimal Decimal

Starting Starting Ending

Point Point Point
A 0 0 126



127 (loop-back)
B 10 128 191
C 110 192 223
D 1110 224 239
E 11110 240 247

How did I get Table 3? I had to remember only a couple of pieces of information, then I constructed the rest. I know there are five classes of IP addresses, and the first byte of the IP address tells you to which class it belongs. I also know the schema for the binary starting value of the first byte, i.e., 0, 10, 110, etc. Because of the way it follows a schema, the second column is easy to construct. Now, using Table 2, it was easy to construct the third column.
Next, note that the fourth column (ending point) follows naturally by simply subtracting one from the beginning of the next class. A class C begins at 192, while a class D begins at 224. Hence, a class C must end at 223. Now you have no excuses about forgetting the beginning and ending points of each class; merely remember the binary schema, and take a minute to construct the table. On a side note, you don't have to worry about Classes D and E, except that the beginning of Class D tells you where Class C ends by subtracting 1.
Bitwise AND
We need to discuss netmasking, but first, let's digress for a moment. A Boolean AND is just like an “and” in English. You tell Johnny you will buy him an ice cream cone if he puts out the trash “and” makes his bed. If he does neither or only one of them, he doesn't get an ice cream cone. If he does both, he gets the cone.

Table 4. Bit-Wise Logical AND Truth Table

First Second Result
Bit Bit
0 0 0
0 1 0
1 0 0
1 1 1

Bitwise ANDs work bit by bit. So, if you AND a 1 with a 1, you get a 1. If you AND two 0s, a 1 and a 0, or a 0 and a 1, however, you get a 0. Table 4 illustrates this operation.
Now let's take a whole byte and do a Logical AND with another byte. Suppose the first byte is 10110010 and the second byte is 01100111. Working from the right, note that the first byte has a decimal value of
0*1 + 1*2 + 0*4 + 0*8 + 1*16 + 1*32 + 0*64 + 1*128 = 178
while the second byte has a decimal value of
1*1 + 1*2 + 1*4 + 0*8 + 0*16 + 1*32 + 1*64 + 0*128 = 103.
Now, AND the two bytes:
1 0 1 1 0 0 1 0         178 decimal, ANDed with
0 1 1 0 0 1 1 1         103 decimal
---------------             gives
0 0 1 0 0 0 1 0         34 decimal
As a second example, let's AND 178 with 255.
1 0 1 1 0 0 1 0         178 decimal, ANDed with
1 1 1 1 1 1 1 1         255 decimal
---------------             gives
1 0 1 1 0 0 1 0         178 decimal
We know, then, that when you bit-wise AND any byte (number) with 255, you get the number dropping through, i.e., the result is merely the number again.
Netmasking
The default netmasks for the various classes are shown in Table 5 with some sample host IP addresses. Simply put, a host is anything that has an IP address. This includes servers, workstations, routers, etc.

Table 5. Default Netmasks, etc.

Class Default Meaning of Sample Sample

Net-Mask IP (Host) Host Network


Address Address Address
A 255.0.0.0 N.H.H.H 10.0.1.23 10.0.0.0
B 255.255.0.0 N.N.H.H 146.87.12.250 146.87.0.0
C 255.255.255.0 N.N.N.H 200.150.189.31 200.150.189.0

So, what does this mean and what do we do with it? Let's work through Table 5. If we take the sample Class A address, 10.0.1.23 and bit-wise AND it with its default netmask, we obtain 10.0.0.0. What is 10.0.0.0? It's the network address—look at the last column.
Notice that the first byte gives the network address when ANDing a Class A network with its default netmask, while the first two bytes give the network address when ANDing a Class B IP address with the default Class B netmask. Hence, we say that the first byte of a Class A IP address gives the network address, and the three remaining bytes give the host addresses, i.e., a Class A address has the form N.H.H.H where N stands for Network and H stands for Host. Likewise, the first two bytes of a Class B IP address pertain to the network, and the last two bytes pertain to the host address, i.e., N.N.H.H. Finally, the first three bytes of a Class C IP address pertain to the network, while the last byte pertains to the host, i.e., N.N.N.H.
Subnetting
Let's illustrate this with a Class B IP address such as 142.168.25.100. From Table 5, we know that the default netmask for a Class B network is 255.255.0.0. Hence, ANDing the default mask with the IP address yields the address of the network that particular host is on, i.e., 142.168.0.0. So, a host with an IP address of 142.168.25.100 finds itself on a network with an IP address of 142.168.0.0 if a default Class B net-mask is used.
If you are granted a full Class B suite of addresses with a network address of 142.168.0.0, what do you do with them? Remember, a Class B network has the form of N.N.H.H, i.e., the last two bytes can be used for assigning host IP addresses. This yields a network with 2<+>16<+> - 2 host addresses. The -2 comes from the fact that 142.168.0.0 is the network address, so it can't be assigned to a host; the last address on the network, 142.168.255.255, is used for broadcasts, so it also can't be assigned to a host.
This would be a very big network (65,534 host addresses), far too big to be practical. A very simple approach is to “borrow” one byte's worth of host addresses and assign them as network addresses. That would yield 2<+>8<+> = 256 networks with 254 hosts on each. Even here, these are large networks. This process of borrowing host addresses and using them for networks is called subnetting. We accomplish this by using a sub-netmask (SNM). In this case, we would use a sub-netmask of 255.255.255.0, which is the default Class C netmask. Hence, we have taken one Class B network and turned it into 256 Class C networks.
If we AND 142.168.25.100 with 255.255.255.0, we get a network address of 142.168.25.0 with the first available host address of 142.168.25.1 and the last of 142.168.25.254, since 142.168.25.255 is reserved for broadcasts. Another way of doing this is to start with the network address (142.168.25.0 in this case), turn all host bits into 1s, and obtain the broadcast address. Here, the last byte is used for host addresses, so turning them to ones gives 142.168.25.255. This type of broadcast is called a directed broadcast, meaning that it jumps routers while a local broadcast (which doesn't jump routers) has the form 255.255.255.255 no matter which class of network is involved.
If you're not too stunned at this point, you may wonder if you can subnet only on byte boundaries or if you can subnet a Class C network. The answers are “no” and “yes”, respectively; i.e., you can work in the middle of a byte.
Subnetting on Non-Byte Boundaries
Let's say you are granted a full Class C suite of addresses, e.g., 210.168.94.0 as your network address. You are allowed to assign the host addresses (the last byte) as you please. If you use the default Class C netmask of 255.255.255.0 (see Table 5), you can assign host addresses of 210.168.94.1 through 210.168.94.254 on a single network. That's feasible of course, but you may want to break this up into multiple networks of perhaps 25 hosts each.
Let's do some mathematics. If we have 4 bits for hosts, will it be enough? 2<+>4<+>-2 = 14 and is not enough. So, let's use 5 bits for hosts: 2<+>5<+>-2 = 30 which will work. However, we have 8 bits in the last byte for hosts, so let's borrow three bits for subnetworks; then we still have the requisite 5 bits for hosts. Great, but how many subnets do we have? How about 2<+>3<+> = 8? We have, then, eight subnetworks with 30 host addresses on each. If you are doing the math, you are probably saying, “but 8x30 is only 240 addresses; what happened to the others?” Valid question! Oops, don't get sore, but it's time to construct another table. Note that each address will have the form of 210.168.94.last byte, and the SNM (sub-netmask) will have the form 255.255.255.last byte. Let's just work with the last byte.

Table 6. Subnetworks for Class C Network (shows the last byte)

Binary Decimal
Number Equivalent
00000000 0
00100000 32
01000000 64
01100000 96
10000000 128
10100000 160
11000000 192
11100000 224

From Table 2 (or Table 1), we see the SNM will be 255.255.255.224. The 224 comes from the last byte being 11100000. So what are the subnets? Table 6 shows them (last byte only).
Let's detail a few. First, take the smallest. The full subnetwork address of the smallest is 210.168.94.0. The next one up is 210.168.94.32, and so on. Remember that with three bits to work with, we get 2<+>3<+> = 8 subnets, and looking at Table 6, you see them.

Table 7. Analysis of 256 Values of Last Byte

Last Byte What Why
Addresses Happens  
  to Them  
0 invalid first subnet address
1-30 valid hosts on first subnet
31 invalid broadcast address of first subnet
32 invalid second subnet address
33-62 valid hosts for second subnet
63 invalid broadcast address of second subnet
64 invalid third subnet address
65-94 valid hosts for third subnet
95 invalid broadcast address of third subnet
96 invalid fourth subnet address
97-126 valid hosts for fourth subnet
127 invalid broadcast address of fourth subnet
128 invalid fifth subnet address
129-158 valid hosts for fifth subnet
159 invalid broadcast address of fifth subnet
160 invalid sixth subnet address
161-190 valid hosts for sixth subnet
191 invalid broadcast address of sixth subnet
192 invalid seventh subnet address
193-222 valid hosts for seventh subnet
223 invalid broadcast address of seventh subnet
224 invalid eighth subnet address
225-254 valid hosts for eighth subnet
255 invalid broadcast for eighth subnet

Back to the question of why we get only 240 host addresses. “(Gasp)—another table!” Looking at the last byte, we get Table 7.
Now let's answer the question of what happened to the other addresses. To do this, tally all the “invalid addresses”, i.e., those that can't be used for host addresses.
First, we have eight subnets, each with a subnetwork address and a broadcast address. So we lose 8*2 = 16 addresses here. Now if we subtract these 16 from 256, we get 240 available host addresses.
Doing it the other way is much easier. We have eight subnetworks, each with 30 valid IP addresses; this gives us 8*30=240 valid IP addresses total, the magic number.
For fun, let's do one more thing: analyze the sixth subnetwork in a little more detail. The last byte is 10100000 binary or 160 decimal. The full subnet address is 210.168.94.160 decimal, and we use an SNM of 255.255.255.224. Remember, I said to take the subnet address, set all the host bits to 1s and add them to get the broadcast address. If we do this correctly, it should give the same result as Table 7.
We use five bits for host addresses, so the decimal value of the sixth bit is 32. Subtracting 1 gives 31. Thus, setting the five host bits to 1s, i.e., 00011111, gives a value of 31 decimal. Adding this to the last byte of the subnet address (160) gives 191 for the broadcast address, agreeing with Table 7. Here is the “whole Megillah”:
210.168.94.160 The Sub-Network address210.168.94.161-190 Valid host addresses210.168.94.191 Directed Broadcast address
One final point. Some authors use the term “sub-netmask” even when referring to the default netmasks—they are being just a tad loose with their terms. Happy IP addressing, and remember, Linux is inevitable.

Thursday, March 4, 2010

Some cardinals

  • A binary tree with n nodes has exactly n+1 null nodes
  • If there are n nodes, there exist 2^n-n different trees.
  • No. of nodes in a full binary tree is of the form 2^k - 1
  • Bucket size is 1, when the overlapping and collision occur at same time
Because If there is only one entry possible in the bucket, when the collision occurs,
there is no way to accommodate the colliding value. This results in the overlapping of values.