A gentle routing tutorial by Girish Venkatachalam
Girish Venkatachalam is a UNIX hacker with more than a decade of
networking and crypto programming experience.
His hobbies include yoga,cycling, cooking and he runs his own
business. Details here:
The Internet is held together by the layer III of the TCP/IP protocol suite. Layer III is commonly known as the routing layer or the IP layer. I mean IPv4 throughout this article as IPv6 is not something I have woken up to yet. I have not had to worry about it in programming yet. With that as a starting point let me try to take you through this interesting topic gently and with care.
You don't have to know much about programming or technology to follow this article. We are talking only high level stuff. It is thoroughly fascinating to understand how the Internet works. We will leave all the details and focus only on the big picture. In so doing I am going to focus on the most critical aspect of Internet. Internet is nothing but a network of heterogeneous networks. And I am going to explain how one network understands the language spoken by another. That is all.
You do not have to worry too much about jargon like BGP, OSPF, RIP and MPLS that hackers use. You are welcome to learn them at your convenience and as and when time permits and interest prevails. For now suffice it to say that BGP, OSPF and RIP are routing protocols and that MPLS is a sophisticated enhancement to traditional IP routing. Let us leave MPLS aside now. It is more of a telecom thing strictly speaking.
The Internet is first of all divided into multiple ASes. AS expands to Autonomous System. Each AS is managed by a real world ISP or some governing entity with a defined routing policy. It is hard to define AS but a vaguely useful definition would be homogeneous network.
As I said before Internet is about tying together various heterogeneous networks. Network A is different from network B which is different from network C. Internet makes a computer from network A speak to a computer in network C. AS can be thought of as network A or B or C. Within A, a single routing practice or protocol is in vogue and all nodes in A behave homogeneously. A is different from B and hence A and B are heterogeneous. IP routing makes it possible to marry them together.
The difference in networks also stem from the difference in the OS that runs on each of the nodes and the physical links and even the nodes themselves. We could connect to the Internet from a Blackberry phone over Wi Fi or a home phoneline using PPP or ADSL. Evidently what makes the Internet tick is the ability to speak one common language.
Each Autonomous System manages itself. The routing changes within itself are managed by itself. If a router goes down or if a new network or router gets added,the changes are propagated throughout the network. This is the responsibility of the AS. This is similar to the divide and conquer rule that the British used when ruling India.
Break down the problem into simpler pieces. First we break down the Internet into multiple ASes with each AS managing its own routing. BGP is the protocol that makes one AS speak to another AS. This is what makes the Internet work at the highest level. BGP version 4 is the core routing protocol of the Internet. If BGP goes down, then there is no Internet. It is without a doubt, the most basic and underlying substratum of the Internet machine.
It is also known as an exterior gateway protocol. One more detail is necessary. BGP does what is known as "prefix based routing". And the route lookups are done with the "longest prefix match algorithm". These are incredibly simple concepts to master. Every network is identified by the network prefix and these prefixes are aggregated by BGP. Let me give you an interesting example. A router that knows how to route 61.23.4/24 packets will be referred by a router that knows only the 61/8 prefix. By this approach of route aggregation, BGP routing tables are kept to manageable sizes.
Another aspect is longest prefix match. Every BGP router sends the packets to the router/interface that matches the longest prefix. Assuming that there are two choices 61.4/16 and 61.4.2/24 for a packet bound to 18.104.22.168, the latter router is preferred since the route is more specific. This is common sense. Nothing fancy.
Enough blurb about BGP which I said is the core routing protocol of the Internet. It is also an EGP or an exterior gateway protocol. BGP is not just a routing protocol alone. It can be used for very interesting applications like link level load balancing, policy based routing between ASes, failover routing, link multiplexing, link aggregation, propagating ancillary information quickly and so on.
BGP is a very interesting protocol. The routing protocol that does not interest me much is OSPF. It is an IGP or Interior Gateway Protocol. It routes inside an AS. In fact there is not even a concept of AS in OSPF. OSPF is an incredibly complex protocol that is highly noisy and er unstable. I could be wrong but oftentimes I have felt that OSPF is more like Windoze networking. OSPF is designed to tackle a different kind of problem but the details have driven me mad many times.
RIP is another IGP. It is a very simple protocol and an old one too. It is not going away from the face of the Internet. So it certainly deserves a mention. So OSPF and RIP in conjunction with BGP make the Internet work. This is what makes your mail from Blackberry reach your sweetheart. You watch youtube videos because these protocols do their job.
I hope we did not have to think a lot till now. Good. Now let us look at one more interesting twist involved in routing. Routing protocols work over UDP, IP or TCP. OSPF works over IP. BGP over TCP. And RIP over UDP. Very interesting. Which means that we have a chicken and egg problem now. How can routes be discovered and how do you say that routing protocols work in layer III when they work over TCP or UDP?
It is explained by the fact that the key function of networking layer is forwarding, not routing. Building routing tables and keeping them up-to-date is the job of these protocols/daemons. The actual job is done by IP forwarding. This always happens in layer III. Packet forwarding is similar to packet switching we find in LAN. It is more complex and done in software. MPLS sits somewhere in between switching and routing and it speeds up intelligent routing in a big way.
I will wrap up this gentle overview with a key data structure involved in routing protocols. Patricia tree is the data structure used to build and maintain routing tables. It is easy to see why this data structure is preferred and used compared to a generic linked list or tree. Patricia tree understands the IP addressing structure and it helps very fast lookups based on prefixes. Anyway we are not getting into details.
Internet routing after all isn't all that hard. Is it?
Got something to add? Send me email.
(OLDER) <- More Stuff -> (NEWER) (NEWEST)
Printer Friendly Version
Increase ad revenue 50-250% with Ezoic
More Articles by Girish Venkatachalam © 2009-11-07 Girish Venkatachalam