Programming hints and tips

For your reading pleasure

The long list of rules which used to be posted here has been accumulated and moved into a book called Robert's Rules Of Coding on my bookshelf. If you want to read the rules, or if you are interested in other writings about programming and other topics, please drop by.

As always, write to me if you have anything interesting to say about programming.

Not been here for a while? Interested in past soapboxes? I've posted them all in the archives.

For Discussion (2000-07-25): Routing on the Internet

This is the beginning of a short course I plan to give on the Internet and IP. I'm starting it here on my soapbox to see how it is received.

Common uses of the Internet include the World Wide Web, email, and newsgroups. Since you are probably using the World Wide Web to read this right now, this course will use the web as an example to discuss how the Internet works. If you have any questions which are not covered here, feel free to write me. If I got anything wrong, definitely write me.

When you ask for a web page (say, the home page at www.esmerel.com), your browser has to do a few things to get you the page. First, it must translate the name that you entered into an IP address, and then it must send a request to that IP address to have the page returned.

Translating the name (DNS Lookup)

To send a request to another computer (node) on the Internet, your browser needs to know the IP address of that node. IP stands for "Internet Protocol" and is the way that computers talk to each other across the Internet. Each computer has a unique identifier, called an IP address. This is that weird set of 4 numbers (like 64.23.8.193) that you sometimes see instead of a name for a web site.

However, you generally know the sites on the Internet by their names (which are called domain names), such as www.esmerel.com. To translate the domain name into an IP address, your browser uses something called a domain name server (DNS).

Your browser (and your email software as well) has already been set up, when you or someone else configured it to access the Internet, to know the IP address of a domain name server. When it wants to find the IP address of a domain, it sends a request to the domain name server, which returns the IP address corresponding to that domain.

The domain name servers are usually set up in a hierarchy, and they are periodically (and automatically) updated, so your local domain name server can either directly return the IP address to your computer, or it can look it up in the next level of DNS and then cache it (so it won't have to look it up again next time) and return it to you. Either way, your browser gets a response from the local DNS containing the IP address (or an error response if it failed to find it).

Sending to an IP address

Once your browser has an IP address, it can construct an IP packet (containing the message you want to send, in this case a request for a web page) and send the packet to the destination address. At the simplest level, your computer simply builds the packet and drops it onto the Internet, which takes care (almost magically) of getting it to the right place.

Once you look a little closer, the trick behind the magic becomes clear. Your computer does not need to know much about the destination IP address, only that it is not this computer. It can send the entire IP packet to the nearest router (also known as a gateway, probably the default gateway), and let that router send it to the destination.

Isn't that just dodging the responsibility? Yes, and that's the beauty of the Internet. All your computer has done is pass the packet to a router that it thinks has a better chance of delivering it. So, how does that router deliver the packet?

First, the router checks to see if it can deliver the packet directly. If so, then it does. If not, then it looks at the routers which it can directly reach. From those routers, it picks the one that it thinks is closest to the destination (and which, therefore, has the best chance of being able to deliver the packet), and sends the packet to that one.

This is how routing works on the Internet. Each router either delivers the packet directly to the destination, or forwards it to another router which, in its opinion, is closer to the destination. No router actually needs to know the route that the packet will take.

This flexibility is what allows the Internet to heal itself when a router or a link fails. If the packet cannot get there one way, it will get there another.

How does it get there?

It's possible for you to actually trace the route that the packet took to its destination. The first step is to be sure that the destination exists. IP provides a facility called PING that allows you to do just that. When you send a PING to an IP address, it simply responds with a PING RESPONSE (some call it a PONG). This tells you that the destination exists, can be reached, and is able to respond to at least simple requests.

In the PING packet (in fact, in all IP packets) there is a field known as time-to-live. This field is set to 255 when a packet is sent, and is decremented (reduced by 1) by each router that handles the packet. This field determines the number of "hops" (between servers) that a packet can make. Part of its purpose is to ensure that a packet cannot be routed around the Internet forever. If any router gets a packet and decrements this field to zero, it will not forward the packet any further; it will instead report an error back to the computer that originally sent the packet.

If you want to find out what routers are used to send a packet to a destination, you can use this time-to-live feature to get each router to announce itself to you. Here's how it works.

First, you send a PING to the destination, but you set the time-to-live to one. When the PING reaches the first router, it will decrement the time-to-live to zero, so it will discard the packet and send an error message back to you indicating that the destination is unreachable. This message is known as an ICMP (Internet Control Message Protocol) message. Part of the message is the IP address of the router at which the packet failed.

You record this IP address and then try the PING again, this time with a time-to-live of two. This time it will reach the second router before being discarded, and the error message will give you the IP address of the second router. You continue like this, increasing the time-to-live for each attempt, until you get a PING that actually works. You then have a list of all the routers that handled the packet on the way to the destination.

You cannot set the time-to-live using the ping program itself, but you can use a program called tracert. Tracert will try pinging the destination with increasing time-to-live values, until it determines the route to the destination. If you want to set the time-to-live manually, you can use: tracert -h 1 esmerel.com (then try 2, and so on, until you reach esmerel).

Of course, the next packet may not take the same route. Next time, one of those routers may be down or another one may have come up and be used on the path to the destination.

How does a router know where to send it?

You read earlier that your computer sends the packet to a router, which either delivers it locally (because the destination is directly connected to it), or forwards it to another router that it thinks is closer to the destination.

So, how does the router decide what other router is closer to the destination? It does that by looking it up in a routing table. Each router maintains a routing table, which typically looks something like the one below. Depending on the implementation, there may be other fields in the table, and some of the fields may differ, but this example includes the fields that have to be there.

DestinationSubnet maskGateway
192.168.40.0255.255.255.0local
10.65.1.0255.255.255.0local
192.168.32.0255.255.255.0192.168.40.13
192.168.35.0255.255.255.0192.168.40.14
192.168.0.0255.255.0.0192.168.40.13
10.0.0.0255.0.0.010.65.1.25
0.0.0.00.0.0.010.65.1.1Default

When the router gets a packet, it looks at the destination address and the routing table. It scans the table looking for an entry that matches, and then it sends the packet to the gateway specified in that entry. If no other entry in the table matches, it sends the packet to the destination marked default. In some routers, this is an entry in the table, and in others it is stored separately as the default route, which you may need to configure.

It matches the entries by taking the destination address and masking it with the entry's subnet mask. It compares this against the destination specified in the table. If they match, then this entry can be used. If multiple entries match, then the packet will be routed based on the most specific routing table entry (the one with the most bits set in the subnet mask).

To make this clear, let's look at a few examples.

Local target (192.168.40.17)

First, let's see how the router would send a packet to IP address 192.168.40.17. The router will scan the table. For the first entry, it will mask 192.168.40.17 with 255.255.255.0, which leaves 192.168.40.0. This matches the destination for that entry, so it will use this entry to determine how to send the packet. This entry says that the packet should be sent to local, or to a directly connected computer. The router will send the packet to 192.168.40.17 via the direct connection (probably an Ethernet segment for 192.168.40.xx).

Forwarded packet (192.168.42.17)

Next, let's see how it would router a packet to 192.168.42.17. In this case, it would mask with the first entry's 255.255.255.0, getting 192.168.42.0. This does not match the destination for the first entry, so it will carry on to the second entry. Here it again masks the 192.168.42.17, in this case with the second entry's mask of 255.255.255.0, getting 192.168.42.0 which doesn't match the second entry's destination of 10.65.1.0. So, it will carry on to the third entry, and so on, until it reaches the 5th entry. At the fifth entry, it will mask the 192.168.42.17 with 255.255.0.0 (the fifth entry's mask) getting 192.168.0.0, which matches the destination, so the router knows it can use this entry and forward the packet to 192.168.40.13 (the gateway specified in the fifth entry).

So why didn't it use this entry for the first case? Because one of the rules said to use the most specific entry which matches. This is useful because it means your routing table can specify that a large range of addresses should be routed in one direction, then specify that a smaller subrange of those be routed in a different direction.

Notice that all subnet masks (in binary) consist of a series of ones followed by a series of zeroes. This ensures that the division into networks and subnetworks will always work and will unambiguously provide a most specific matching entry. The most specific entry is simply the one with the most ones in the subnet mask.

The default route

Finally, let's consider how the router would send a packet to 64.23.8.193. It would try matching against the first entry, and fail, and continue through the table. Eventually, it would reach the last entry. This entry is special. Notice that the subnet mask is 0.0.0.0. This means that when you mask it with any IP address the result will be 0.0.0.0, which matches the destination for this entry. This entry is often called a default route. Whenever a packet does not match against any other entry, it will match against the default route, which ensures that the router will always have somewhere it can send the packet. If there is no default route entry, then a packet which does not match any entry must be dropped and an ICMP error message must be sent.
- Read Awk Words.
- Look at my AWK scripts.
- Read Robert's Rules Of Coding.
- Go back to the front gate.
- Read previous programmer's soapboxes
He who is willing to give up freedom for security will get neither.
Page maintained by Rob.