IP version [4 bits] Header length (in longs) [4] Type of service (there's some internal structure to this field, which we'll pass over for the moment) [8 Total length (in bytes) [16] Packet id (for handling packet fragmentation in transit)[16] Fragmentation flags (again internally structured) [3] Fragmentation offset (in eight-byte blocks) [13] Time to live (packet lifetime, in router hops) [8] Protocol (what kind of data are we carrying, anyway?) [8] Header checksum [16] Source address [32] Destination address [32] [Options]
- IP addresses are globally unique 32-bit identifiers. Each network interface
of every IP-enabled device has such an identifier (IP, additionally, like Ethernet,
has broadcast and multicast addressing modes, but I defer comment on these).
For human consumption, IP addresses are conventionally
represented in 'dotted decimal' notation. Procedure: split the binary value
along byte boundaries; decimalize the chunks; glue them together with periods.
E.g.:
Raw binary: 11001100000001001100000000000010 Direct decimal translation: 3422863362 Binary by bytes: 11001100 00000100 11000000 00000010 Dotted decimal: 204.4.192.2
- IP addresses are structured entities.
They encode a network identifier (where each physical
network has a distinct identifier, and where the addresses of all the devices
on a given network share a common identifier) and a host identifier (where each
device on a given network has a host identifier that's unique on that network).
This structure allows for efficient packet forwarding, it means that
we can proceed by extracting network
ids from destination addresses and making forwarding decisions on that
information alone--we don't need to keep routing info for each individual device.
The leftmost bits in an IP address encode the
network id, the rightmost the host id. The boundary between these
components has been defined in two
different ways over the course of Internet history. We'll get to the current
scheme momentarily. In the original model, referred to as "classful addressing",
the network/host boundary inhered
in (or could be inferred directly from) the addresses
themselves. This model worked roughly as follows:
on the assumption that
there are three kinds of networks in the world--large, medium, and small--let
there be three 'address classes'--A, B, and C--that have respectively one-,
two-, and three-byte network prefixes. Let there be some central authority that
assigns network identifiers. For each physical network that an interested
organization wants to connect to the Internet, let the central authority
allocate an identifier of a class appropriate to the size of that network. Let
the organization to which the network id is assigned dispose of the host bits
as it chooses. Let the prefixes of the different classes be distinguishable by
a pattern of leading bits, as follows
Class Net-bits Host-bits Leading-bits Decimalized first byte A 8 24 0 0-126 B 16 16 10 128-191 C 24 8 110 192-223
- There's an efficient operation for extracting the network component
of an IP address--"bit-wise logical and".
Even high-level programming languages typically allow
some direct bit-level manipulation of data; operations including bit shifting
and various logical operations; 'bit-wise logical and' compares bits at
corresponding positions in two quantities, and returns 1 if and only if both
input bits are 1. So to extract a network prefix from an address, we create what's called
a "mask", a 32-bit quantity with 1s at the positions corresponding to the network
component of the address and 0s elsewhere, and then do bit-wise logical and on the
address and mask. The
result of applying
the mask is to preserve the original values at the positions corresponding to
the 1s and to zero out everything else. For example, let's say we're interesting
in pulling the network chunk from the IP address
209.209.209.209 (= 11010001110100011101000111010001).
1. Inspect the leading bits of the address 2. Ah, '110', that'll be a class C address 3. Let's see, class C has a three bytes of network prefix, so we'll need a mask with 24 leading 1s address: 11010001110100011101000111010001 mask: 11111111111111111111111100000000 --------------------------------------------- net prefix: 11010001110100011101000100000000
[Notes expanded from original from this point on]
- IP packets flow from origin to destination across one or more physical networks. Everybody gets involved in the packet-forwarding act, both hosts and routers.
- Take 1. Forwarding under "classful addressing": host perspective. The host
will be configured with an IP address and with the IP address of a router
on its own network, through which it can send to off-network destinations. By inspection of its
own IP address, the host can compute the network id of the network it lives on (per
the discussion of masking above).
For each packet to be forwarded, the host
- Applies to the destination address the mask appropriate to that address
- If the result is the same as the host's network id, the destination is on the same network as the host, and the host will deliver the packet directly (we'll get shortly to what it means to "deliver directly").
- If the result differs from the host's network id, the destination is on some other network and the host sends the packet to the router for further handling. The host has now passed the buck!
- Examples:
A host H is configured with an IP of 192.192.192.25, and is told that its router R is at 192.192.192.254. H sees that the leading bits of the first byte of its address are 110, infers that it has a class C addrress, and applies a 24-bit mask to the address to derive the network prefix for its network, obtaining the result 192.192.192.0. 11000000 11000000 11000000 00001101 # H's IP address (192.192.192.25) 11111111 11111111 11111111 00000000 # mask appropriate for that address ----------------------------------- 11000000 11000000 11000000 00000000 # H's network prefix (192.192.192.0) Now assume that H wants to send to H2 at 192.192.192.221. H inspects the destination address, sees that the leading bits of the first byte are 110, infers that it is a class C address, applies a 24-bit mask to it, obtaining 192.192.192.0 as the network prefix. H then compares that result to the network prefix for its own network, observes that they are identical, concludes that the destination is on its own network, and sends direct to the destination 11000000 11000000 11000000 11011101 # H2's IP address (192.192.192.221) 11111111 11111111 11111111 00000000 # mask appropriate for that address ----------------------------------- 11000000 11000000 11000000 00000000 # H2's network prefix (192.192.192.0) By comparison, assume next that H wants to send to H3 at 192.192.193.64. H inspects the destination address, sees that the leading bits of the first byte are 110, infers that this too is a class C address, therefore again applies a 24-bit mask to it, and this yields 192.192.193.0. 11000000 11000000 11000001 01000000 # H3's IP address 11111111 11111111 11111111 00000000 # mask appropriate for that address ----------------------------------- 11000000 11000000 11000001 00000000 # H3's network prefix (192.192.193.0) H compares this result to its own network identifier, observes that they differ, concludes that the destination is on some other network, and bails--sends to its router for further processing
- Forwarding under "classful addressing": router perspective. A router is
connected to multiple physical networks. An IP address is associated with each
of the router's interfaces. From each address the router infers a corresponding
network prefix. The router also mains a "routing table", i.e., information about
networks other than the ones to which it's directly connected. Entries in the
table consist of (at least) a network identifier and the IP address of a
next-hop
router--a router on a directly connected network that's one step closer to the
destination network than the first router. For each packet that the
router sees,
- If the destination address is the router itself, process the packet.
- If the destination address, when masked, results in a network prefix identical to one associated with one of the router's interfaces, deliver direct out that interface (as a host would).
- Else, compare the masked destination to the routing table entries; on a match, send to the IP address of the next-hop entry for the router. The router's now passed the buck!
- Examples:
Consider a router R that has three network interfaces, bearing the IP addresses 192.192.192.254, 208.208.208.208, and 10.10.10.10. The router also has routing tables entries for networks 11.0.0.0 and 128.128.0.0, as follows: Network prefix Address of next-hop router -------------- -------------------------- 11.0.0.0 10.10.10.253 128.128.0.0 208.208.208.253 From the IP addresses of its interfaces the router derives by masking the identities of its attached networks, namely 192.192.192.0, 208.208.208.0, and 10.0.0.0. A packet arrives at R stamped with the destination address 208.208.208.13. R masks that address, and determines that the destination resides on the 208.208.208.0 network: 11010000 11010000 11010000 000001101 # destination = 208.208.208.13 11111111 11111111 11111111 000000000 # mask for class C ------------------------------------ 11010000 11010000 11010000 000000000 # destination network = 208.208.208.0 R compares the network prefix it computes to the network prefixes associated with its own network interfaces, sees a match, and "sends direct" to the destination out its interface bearing the address 208.208.208.208. A second packet now arrives at R stamped with the destination address 128.128.128.1. R notices that the leading bits of the first byte of the address are 10, knows this means the address is a class B one, applies a 16-bit mask, and determines that the recipient lives on the 128.128.0.0 network. 10000000 10000000 10000000 00000001 # destination = 128.128.128.1 11111111 11111111 00000000 00000000 # class B mask ----------------------------------- 10000000 10000000 00000000 00000000 # destination network = 128.128.0.0 R compares the network prefix it computes to the network prefixes associated with its own network interfaces, but fails to find a match. It then compares the computed prefix against the network prefixes in its routing table, sees that the second entry matches, and forwards the packet to 208.208.208.253 for further handling.
- Take 2: IP forwarding with "subnet masks".
"Classful addressing" and forwarding based on it, as above, is simple,
but also inflexible and wasteful. If the IP addresses of all the devices on a
physical network need to share a network prefix, and if the only source of network
prefixes is what you get from the classful interpretation of addresses, then
each physical network consumes a classful identifier. Now consider what happens
when the rate at which networks attach to the Internet increases dramatically.
First, since we're using net ids to manage packet-forwarding, the amount of
information that has to be tracked grows. Further, the supply of identifiers of
each class is fixed, so if there turns out to be high demand for identifiers of
a particular class, there's a risk of exhausting the address space. And in fact
there've been over Internet history recurrent episodes of mass hysteria about
class B exhaustion.
In the mid-'80s an important scheme was developed to circumvent these problems--'subnetting'. The idea is that when some device is trying to figure out how to forward a packet, it extracts the network id not by using a mask derived from the address itself, but by using... another mask, a piece of information stored locally. This mask serves the same function as the one we talked about being directly derivable from the address--we use it to extract network prefixes--only now we're not paying any attention to those leading bits: we define the boundary wherever we think is convenient. This scheme allows organizations to develop complex internal network topologies without having to go back to their ISPs to beg for more IP address blocks. Furthermore, the rest of the world doesn't need to know anything about these internal divisions.
- Forwarding with subnetting: host perspective. The
host will be configured with an IP address and mask and will know the IP address of
a local router, through which it can send to remote destinations.
By inspection of its own IP address and mask, the host
computes the network id of the network it lives on. For each packet to
be forwarded, the host
- Applies its mask to the destination address
- If the result is the same as the host's network id, the destination is on the same network as the host, and the host will deliver the packet directly
- If the result differs from the host's network id, the destination is on some other network and the host sends the packet to the router for further handling. The host has now passed the buck!
- Examples:
To start off with a simple case in which the subnet mask falls on a byte boundary, I'll re-use the "host under classful addressing" scenario above, and we'll say that the network designer just happens to use subnet masks that correspond to the classful interpretation of the addresses involved. A host H is configured with an IP of 192.192.192.25, a mask of 255.255.255.0, and is told that its router R is at 192.192.192.254. H applies the mask to its address to derive the network prefix for its network, obtaining the result 192.192.192.0. 11000000 11000000 11000000 00001101 # H's IP address (192.192.192.25) 11111111 11111111 11111111 00000000 # Locally configured subnet mask ----------------------------------- 11000000 11000000 11000000 00000000 # H's network prefix (192.192.192.0) Now assume that H wants to send to H2 at 192.192.192.221. H applies its mask to that address to see whether the resulting network prefix matches the network prefix of H's own network. Notice in particular that H no longer inspects the destination address to determine what mask to apply to it. Nor does it need to know what mask is defined on H2's network. For each device making packet forwarding decisions, all that matters are locally-defined masks. 11000000 11000000 11000000 11011101 # H2's IP address (192.192.192.221) 11111111 11111111 11111111 00000000 # H's mask ----------------------------------- 11000000 11000000 11000000 00000000 # computed network prefix (192.192.192.0) In this case the computed network prefix matches H's own, so H thinks the destination is local--on H's own network--and sends direct to H2. By comparison, assume next that H wants to send to H3 at 192.192.193.64. H again applies its own mask to that address, and the resulting network prefix is 192.192.193.0. 11000000 11000000 11000001 01000000 # H3's IP address 11111111 11111111 11111111 00000000 # H's mask ----------------------------------- 11000000 11000000 11000001 00000000 # computed network prefix (192.192.193.0) This time H sees that the computed prefix differs from its own, infers that the destination lives on a remote network, and accordingly sends the packet to its router for further handling.
Now here's a second example, in which the subnet boundary doesn't correspond to a byte boundary in the IP address. Exactly the same principles are involved as before, but it's harder to see what's going on just by looking at the dotted-decimal representation of the addresses involved. Let's say that we have H at 10.19.16.16, configured with a mask of 255.240.0.0 and with a router at 10.30.32.64. H computes its network prefix from its mask as follows: 00001010 00010011 00010000 00010000 # H's IP address (10.19.16.16) 11111111 11110000 00000000 00000000 # H's mask (255.255.240.0) ----------------------------------- 00001010 00010000 00000000 00000000 # H's network prefix (10.16.0.0) Now let's say that H wants to send a packet to 10.24.48.48. Once again H's first question is "does 10.24.48.48 live on my network or not?", and once again H resolves this by masking the destination again H's own network mask and comparing the result to H's network prefix: 00001010 00011000 00110000 00110000 # destination IP address (10.24.48.48) 11111111 11110000 00000000 00000000 # H's mask (255.255.240.0) ----------------------------------- 00001010 00010000 00000000 00000000 # computed network prefix (10.16.0.0) In this case the two prefixes are identical, H infers the destination is local, and "sends direct". Finally let's try it with H trying to send to 10.33.2.2. Apply the local mask to the destination to compute network prefix: 00001010 00100001 00000010 00000010 # destination IP address (10.33.2.2) 11111111 11110000 00000000 00000000 # H's mask (255.255.240.0) ----------------------------------- 00001010 00100000 00000000 00000000 # computed network prefix (10.32.0.0) Does 10.32.0.0 equal H's own prefix of 10.16.0.0. Not exactly, so H forwards the packet to the router.
- Router perspective:
A router is connected to multiple physical
networks. An IP address and mask is associated with each of the router's
interfaces. From each address and mask the router infers a network prefix.
The router also maintains a "routing table",
i.e., information about networks other than the ones to which it's directly
connected. Entries in the table consist of (at least) a network identifier,
associated mask,
and the IP address of a next-hop router--a router one step closer to the
destination.
For each packet that the router sees,
- If the destination address is the router itself, process the packet.
- If the destination address, when masked against the mask associated with any of the router's interfaces or routing table entries, results in a network prefix identical to the interface's or table entry's own prefix, deliver direct out that interface or to the next-hop router indicated in that table entry. The set of interfaces and table entries is examined in decreasing order of mask length (i.e., the mask with the greatest number of consecutive left-most 1s is tried first). One way of phrasing this is to say that the router tries to find the most specific route possible to the destination.
- Example:
Consider a router R that has three network interfaces, bearing the IP addresses and masks 200.201.202.1/255.255.255.0, 208.208.208.209/255.255.255.252, and 129.0.2.1/255.255.255.0. The router also has routing tables entries for networks 0.0.0.0/0.0.0.0 and 200.201.202.64/255.255.255.192, as follows: Network prefix Mask Address of next-hop router -------------- ---- -------------------------- 200.201.202.64 255.255.255.192 129.0.2.2 0.0.0.0 0.0.0.0 208.208.208.210 From the IP addresses and masks of its interfaces the router derives the identities of its attached networks, namely 200.201.202.0, 208.208.208.208, and 129.0.2.0. A packet arrives at R stamped with the destination address 129.0.2.12. R goes down its list of interfaces and table entries, applying the mask associated with each interface to the address, looking to see if the result matches the network prefix for that interface. When it gets to the 129.0.2.1 interface there is such a match: 10000001 00000000 00000010 000001100 # destination = 129.0.2.12 11111111 11111111 11111111 000000000 # R's mask for its 129.0.2.1 interface ------------------------------------ 10000001 00000000 00000010 000000000 # computed prefix = 129.0.2.0 But 129.0.2.0 is the prefix R has already computed from its own IP and mask as the network prefix associated with this interface. Therefore R sends direct out this interface. A second packet now arrives at R stamped with the destination address 200.201.202.66. As it happens, this address will match against both R's 200.201.202 interface and its 202.201.202.64 routing table entry, but the latter is applied first because its mask contains more 1s bits. 11001000 11001001 11001010 01000010 # destination = 200.201.202.66 11111111 11111111 11111111 11000000 # mask for first routing table entry ----------------------------------- 11001000 11001001 11001010 01000000 # destination network = 200.201.202.64 R sees that the result matches the prefix for the table entry, and forwards the packet to the indicated next-hop router. Last packet. A packet arrives at R destined for 4.4.4.4. The routing table entry with the mask of 0.0.0.0 is the last one that would ever be applied (assuming a match hadn't previously been found)--a mask of 0.0.0.0 has no 1s bits at all, and is therefore the "shortest", lowest precedence mask. In this case, the tests against all the other interfaces and routing table entries fail, so we actually reach this point. Masking 4.4.4.4 against 0.0.0.0 results in 0.0.0.0--but that's the prefix we're looking for, so the packet is forwarded to 208.208.208.210. Notice that anything masked against 0.0.0.0 always results in 0.0.0.0, so if there's an entry like this in a routing table, the forwarding action associated with it is guaranteed to be applied to any packet for which no more specific rule can be found. An entry like this is traditionally called the "default route". In the case, for example, in which a given router is an organization's only connection point to the Internet, a default route may be the only explicit entry in the router's routing table.