Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Elguapo's Guide to Routing

By el_guapo in Internet
Thu Nov 07, 2002 at 05:06:16 AM EST
Tags: Internet (all tags)
Internet

Part 1 - An introduction

Chapter 2 will be the Routing Information Protocol(RIP). Chapter 3 will be the Border Gateway Protocol (BGP - you used BGP to get to this page). Chapter 4 will be Open Shortest Path First Protocol (OSPF). Chapter 5 will be the Interior Gateway Routing Protocol (IGRP). Chapter 6 will be the Enhanced Interior Gateway Routing Protocol (EIGRP). Chapter 7 will be the Intermediate System to Intermediate System protocol (IS-IS - I know this but have never done it, if someone would like to help on this one please advise.


I am going to assume that either A)you understand basic IP addressing things (such as your address, subnet mask and default gateway) or B)you'll go here to find that information out.

So, what exactly is "routing"? Routing is simply a source host attempting to find a destination host. Basically, your source IP address asks your default gateway: A)how the heck does it get to its requested destination? and B)would you please take me there?

Routing takes 2 basic forms, "Static" and "Dynamic". Static routes are just that, some schlep like me went in and manually programmed the route. On Cisco devices these are programmed in the format "ip route a.b.c.d e.f.g.h i.j.k.l" where a.b.c.d is the destination route, e.f.g.h is the subnet mask for that destination (this makes it possible to route either entire subnets or an individual host) and i.j.k.l is the next hop.

I think this is the best time to bring up a routing concept called "admin distance". Since it's entirely possible - and on the internet it's actually very probable - that a router might have more than one route to a destination, it has to have a way of deciding which route to use. (A router can even have more than 1 static route to a destination, if you were wondering) Thus the concept of admin distance. Admin distance is merely a way of numerically weighting routes, with lower being the more preferred route. Incidentally, static routes have an admin distance of 1 - they assume a network admin that programs a static route is pretty damn sure he wants that route followed. Go here for a listing of the other admin distances. And yes, you can change admin distances for routes from their defaults. For a static route you change its default admin distance in the form of "ip route dest.ipaddy dest.mask next.hop admindist". Asking yourself if there is a route with a default admin distance of "0"? Why yes there is, and that brings us to our next section.

"Connected" Routes. A connected route is a route that the device sort of learned automatically. It did this because it had an interface in the destination subnet. If I have an interface with the IP address of 192.168.0.1 masked with 255.255.255.0, then I automatically know to send anything destined for that class C subnet out that interface. There is no "better" route than a connected, but a static is a darn close second place.

Routing protocols exist so that schleps like myself don't have to continually manage static routes. They DON'T do this to make my life easier, they do it so that the network can A)be much more manageble (our network has well over 150,000 nodes - managing the static routes it would need would require about 150,000 people in my team). B)Be "self healing" in case of outages. When a network "self heals", that is called convergence. Convergence happens (hopefully!) when you first turn on the network, and whenever something happens that makes the network have to work around it, like an outage. Fast convergence is a very desireable trait for a routing protocol to have. Being an engineered thing, though, they suffer the same thing any engineering project suffers from: "you want it fast, cheap or robust? Pick two".

Routing protocols are generally grouped into two groups:

  1. Distance Vector and
  2. Link state.
Distance vector is so named because routing decisions are decided upon by which way is the destination (vector), and how far away is said destination (distance)? For example, "a.b.c.d is 3 hops away and in the direction of next-hop e.f.g.h". Since each router depends on it's neighbors for routing information, who in turn learned from THEIR neighbors, distance vector is nicknamed "routing by rumor". RIP, IGRP, EIGRP (this is commonly called "a distance vector that acts like a link state". This isn't really the chapter to go into why), BGP, Appletalk's Routing Table Maintenance Protocol (RTMP), DEC's DNA Phase IV, Novell's IPX RIP and Xerox's XNS RIP are all distance vector routing protocols. (If you're a network weenie, yes, I did just cheat on those last few by looking in a book) Since no router knows the state of the network beyond it's directly connected links, Distance Vector protocols can make bad routing decisions.

Distance Vector protocols share some common traits.

  1. Neighbors - these are two routers that share a common connection. A router sends it's routing updates to it's directly connected neighbors and depends on them to send it on down the line.
  2. Broadcast updates - when a router is fiirst turned on, how does it find out who it's neighbors are? The simplest way is to send out a broadcast to 255.255.255.255, the univeral IP broadcast address. Neighboring routers running the same protocol will hear this and do what is appropriate.
  3. Full route table updates - most distance vector protocols take the simplistic approach of sending their entire route table and letting the neighbor discard what it doesn't need. Needless to say this seriously hampers scalability, since big networks could very conceivably suck up all their bandwidth simply exchanging routes.
  4. Periodic Updates - at the end of a certain time period, an update will be sent. The downside here is that updates are sent (and remember an update is the entire route table) whether something has changed or not.
Link state protocols, unlike distance vector protocols, keep an entire map of the network that they learned from their neighbors. A neighbor is all the routers speaking the same protocol and configured to to share information on the same network. The goal of link state protocols is for each peer to have an identical picture of the state of the entire network. Each router originates information about itself and the links it has and their state (thus the name). If distance vector is the equivilant of using road signs to find your way around, then link state is the equivalent of having a road map. Protocols that use link state are: Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), DEC's DNA Phase V, and Novell's Netware Link Services Protocol (NLSP). (Cheated again!)

Some common characteristics of Link State protocols are:

  1. Each router establishes what is called an "adjacency" with each of it's neighbors.
  2. Each router then sends Link State Advertisements (LSA)to each neighbor, one LSA per link. The LSA identifies the link, the state of the link, the metric cost for using the link and any neighbors that may be connected to the link. Each neighbor receiving the LSA then forwards it on, in a process called "Link State Flooding", to all of it's downstream neighbors.
  3. Each router then stores a copy of these LSA's in a database. When the network is converged all databases should be identical.
  4. This "Link State Database" then has the "Dijkstra algorith" ran against it to calculate the shortest path to each network and this information is then placed in the routing table.
  5. Link State Sequence numbers - sequence numbers help a router keep track of LSA's. In a big network it is possible to get conflicting information about the network due to latency. A link could go down and come right back up, and a router could get the LSA saying the link was back up before it got the LSA saying it was down. Thus sequence numbers, if I get LSA#168 saying it's up, follwed immediatly by LSA#167 saying it's down, I know which order to consider them. Without the sequence number it would have ignored the first LSA ("I already knew it was up!"), and then registered that interface as down when it got the second LSA out of order.
  6. Link State Aging - this lets the router determine how old an LSA is. A router might receive multiple LSA's with identical sequence numbers. If the time difference of those ages is less than MaxAgeDiff, then it assumes this is because of natural latency, and it keeps the copy it already has in it's database and doesn't flood. If it exceeds that setting then it assumes there was an anomoly and places the new LSA in it's database and floods it. There is also a MaxAge setting - if an LSA gets to MaxAge it is flooded and removed from the database. There is a LSrefreshtime wherein a router floods it's LSA's to all of it's neighbors, and they reset the current age to zero. LSrefreshtime is usually set to 1/2 of MaxAge so you get two shots at resetting the timer before everybody dumps that LSA.

Next up, the Routing Information Protocol!

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o here
o here [2]
o Also by el_guapo


Display: Sort:
Elguapo's Guide to Routing | 52 comments (18 topical, 34 editorial, 0 hidden)
Question (5.00 / 1) (#28)
by cameldrv on Thu Nov 07, 2002 at 12:24:33 AM EST

Well, all the router geeks should be here, so I will ask the burning question I have had for a while.

From time to time, we hear people complaining that the routing table for the core routers is getting too big, and this is hurting the performance of multihomed routers.  Why don't they just use a big lookup table for the routes?  You can make a table with one byte for every /24 in only 16 megabytes, so what difference does it make how many routes are in memory?

Routing Table Size (none / 0) (#34)
by supine on Thu Nov 07, 2002 at 07:19:07 AM EST

The problem with routing table size is the complexity it adds to the system as it grows. There is a lot of information that is associated with each route. The router also accepts multiple routes to the same destination but picks one to put in the lookup table.

Therefore it is not the static memory usage that is the problem but the resource intensive computation required when something changes and preferred routes have to be recalculated.

As an illustration, when a link between two providers goes down for some reason this causes the routing across that link to be dropped. When the link comes back up the routes are restored. This is referred to as a "flap". Flapping creates enough of a problem with other's routers that flap dampening was introduced. Each time a link flaps it is assigned penalty points. When it reaches a threshold the routers start ignoring routing information from that link. As time passes penalty points are struck off and once below the threshold the link is re-established.

In summary, it isn't the storage of the routes in memory as much as the computation required when there is a routing change.

marty


--
"No GUI for you! Use lynx!!!, Come back, One year!" -- /avant
[ Parent ]

what supine said (none / 0) (#40)
by el_guapo on Thu Nov 07, 2002 at 02:23:15 PM EST

also, most routers (at least the ones i know) have comparatively little memory. for instance, my internet BGP peer boxen, despite having over 100,000 routes, have a grand total of 256MB of RAM, which is incidentally the maximum they can have. that RAM has to not only hold all of those routes, it has to run the OS, run BGP, run OSPF, run a shitload of ACLs, support telnet yada yada yada when i do BGP i'll show some examples from a full internet tier 1 connected BGP peer
mas cerveza, por favor mirrors, manifestos, etc.
[ Parent ]
+1 FP (none / 0) (#30)
by S1ack3rThanThou on Thu Nov 07, 2002 at 03:54:15 AM EST

I've always been interested in the black art that is routing and networks, I'm glad someone is finally going to explain it to me!

"Remember what the dormouse said, feed your head..."
link better (4.00 / 1) (#31)
by nex on Thu Nov 07, 2002 at 04:26:05 AM EST

As I came too late and the article is already past edit mode, I'm not going to point out little language problems that are still present in the new version.

But I'd like to slap your fingers with a ruler because of one particularly important point. Plase take no offense, it's really meant as a suggestion for improvement: Never, never, never ever call a link "here". This is not what hypertext is about. Links point to a place where more information about a certain topic can be obtained, and this topic hardly ever can be called "here". Links stand out, as they are emphasized, e.g. underlined and in a different colour, like here on K5. Consequently, they are often skimmed by people who don't read the rest of the article. Take me, for example. I didn't read the whole text, because I know the basics of routing already, but I had a look at the "related links" column to the right. When I read "here" there, I have no idea what the link is about, and what's worse, you've got two of those, but the system can't tell them apart and only gives me one in the "related links" column. Incidentially, the one that I'm not interested in. You should have called the Link "route selection in Cisco routers" or something. It would be even better to point directly the paragraph you're referring to (http://www.ieng.com/warp/public/105/21.html#2) and call the link something like default administratice distances.

Much nicer, huh?

a quibble: (none / 0) (#38)
by ethereal on Thu Nov 07, 2002 at 01:40:55 PM EST

Links aren't underlined if you turn that off in your browser.

As a corollary: web sites that set their visited link color to be the ordinary text color, or even worse set their unvisited link color to the ordinary text color, should be burned to the ground with all hands. The same goes for sites that force links to be underlined even though I turned that off in my browser.

Couldn't agree more about descriptive link names, though. My problem is always in deciding whether I should include "click here" as part of the link or not. I always wonder whether my readers are smart enough to click everything they see, or whether I have to tell them to click it.

--

Stand up for your right to not believe: Americans United for Separation of Church and State
[ Parent ]

bad web design or really stupid readers (none / 0) (#46)
by nex on Fri Nov 08, 2002 at 11:50:44 AM EST

links are generally marked in a way that makes them stand out. you have to be able to tell them apart from ordinary text, after all. of course different browsers handle this differently, you don't have to tell me that lynx doesn't underline links. but they stand out after all.

if a user changes his or her settings to make links virtually invisible, it's in his or her own responsibility. trying to rely on phrases like "click here" because you stopped liking colours is stupid, stupid, stupid.

links serve the single purpose of pointing to another document. in most user agents, going to that other document is achieved by clicking on the link. in this case, every link is there for the user to click it if s/he wants to see the other document. marking a link with "click here" is nonsense, because it is self-evident that it may be clicked and there are no links marked with "don't click here!". in other user agents, you don't click on a link, but input or say its number. in this case, "click here" makes even less sense. if you have to wonder wheter your readers are smart enough to figure out on their own where to click, you are either a very, very bad web designer or writing for very, very stupid people. if you showed me the web pages you're referring to, i'd very likely be able to point out to you why it's inelegant and bad style to use "click here"-phrases and how it could be done better.

[ Parent ]

links (none / 0) (#53)
by ethereal on Mon Nov 11, 2002 at 10:35:27 AM EST

My point is that link formatting should be left up to the user agent, not decided by the web page developer. When a developer makes a choice that doesn't work well with a particular user agent setting, they've caused pain for those users for no good reason as well as harming their site. I as a user should decide what formatting to give links in order to make them stand out to my eye. That can be underlining, or color, or BLINK, or whatever. The developer shouldn't code the page so as to force one of these ways, since the user may have chosen differently. Especially if the developer is forcing things to look like what is normally the default in most browsers anyway.

The thing with "click here" is really a question of: are links information resources, or are they imperatives to the user? That is, does a user view your page as a list of references (in the literary sense) that they can follow at their leisure, or do they view it as a sort of actions menu, where you have to tell them that clicking this will make the page do something. That is the question that I ask myself when I think about "click here", and I think it's the (incorrectly answered) question that leads to the proliferation of "click here". It's the confusion between hypertext as reference system (the original aim) and web page as application that's to blame.

Personally, I do steer away from "click here", but often I have to think about it for a minute before I can figure out a way to word the link that makes the imperative clear, or whether in fact the link should be an action versus a reference. I don't write any "click heres", but it's a little tougher to avoid than you would think it should be. Though perhaps I just need to do it more.

--

Stand up for your right to not believe: Americans United for Separation of Church and State
[ Parent ]

not convinced (none / 0) (#42)
by svillee on Thu Nov 07, 2002 at 07:34:34 PM EST

While I usually try to use descriptive text for hyperlinks, there are times when it's more trouble than it's worth.

Here's a challenge for you: Take either of the sentences where the author used "here" in a hyperlink. Then show how to rewrite the entire sentence to fix the problem, without changing the meaning, and without making the sentence more awkward.

Here is a hypothetical example where it would be rather tough:

Mr. Jones has written numerous articles emphasizing deflation as a growing threat to the economy. Examples may be found here, here and here.

Now, in this case the author could replace each "here" with the full name of the corresponding article. But this would make the sentence much longer. The author may feel that many readers are not even interested in the examples. He may just want to provide a short list of pointers as a courtesy for those few who may be interested.

The bottom line is that the problem you describe is only really a problem for those who skip the article and just look at the "related links". So my sympathy is pretty limited. The sentences with "here" in hyperlinks make perfect sense to those who actually read the article.

[ Parent ]

maybe this convinces you: (5.00 / 1) (#47)
by nex on Fri Nov 08, 2002 at 12:24:40 PM EST

> Take either of the sentences where the author used "here" in
> a hyperlink. Then show how to rewrite the entire sentence to fix the
> problem, without changing the meaning, and without making the sentence
> more awkward.

I'll even try both. First example, before:
>> I am going to assume that either A)you understand basic IP
>> addressing things (such as your address, subnet mask and default
>> gateway) or B)you'll go here to find that information out.
This becomes:
I am going to assume that you either (A) understand the basics of IP addressing (such as your own IP address, subnet mask and default gateway) or (B) you will find out how IP addressing works before reading on.
Well, I did change the literal meaning a little, but this was necessary because the author requires the reader to "go here". I think offering further information without being that authoritarian about what sources the reader should use is better anyway, and my link title is descriptive and can stand on its own.

Second example, before:
>> Admin distance is merely a way of numerically weighting routes ...
>> Go here for a listing of the other admin distances.
This becomes:
Admin distance is merely a way of numerically weighting routes ...

Your example:
> Examples may be found here, here and here.
This becomes:
Examples may be found at various sources [1] [2] [3].

________
[1] www.textism.com
[2] err.antville.org
[3] ped.antville.org

My sentence is not longer at all and readers who aren't interested can just skip over the footnotes. And you see where the link points to before you click it. One could link the numbers of the footnotes directly to the destinations or to the corresponding footnotes at the bottom of the article. I like to put link in footnotes very much in these situations, because often I want teh reader to read the whole text before following the links. For example, when explaining how to use a web site and pointing to the log-in prompt. If you put a link in the text, users often log in right away and then instantly get lost or even do some damage because they didn't read important information that was after the link.

> He may just want to provide a short list of pointers as a courtesy
> for those few who may be interested.
Mine was shorter, and I think it looks more elegant than "here, here and here". And my links have distinct names (even when linking from the numbers themselves), which is important in many situations, e.g. here on K5.

On sites like slashdot where it's understood that readers are "web savvy", you can also find this form:
Mr. Jones has written numerous articles emphasizing deflation as a growing threat to the economy.
This is still much more elegant and descriptive than "here". Furthermore, your argument that the usage of "here" is only a problem for those who skip the article and just look at the "related links" is flawed in several points: There's nothing wrong with only looking at the related links (e.g. because the article only covers the basics that you already know, but points to firther reading you might be interested in), readers who do so shouldn't be punished for skipping the article, it also affects readers who skim the article for interesting parts and read all the URLs automatically because they are emphasized and stand out, and it also annoys people who do read the whole article.

[ Parent ]

aesthetics (none / 0) (#48)
by svillee on Fri Nov 08, 2002 at 06:36:51 PM EST

I will concede that you have improved the original two sentences. Regarding the rest, let's just say that we evidently have different aesthetic tastes.

My sentence is not longer at all.

I hate to nitpick, but it is longer.

strlen("Examples may be found here, here and here.") == 42

strlen("Examples may be found at various sources [1] [2] [3].") == 53

[ Parent ]

my mistake (none / 0) (#50)
by nex on Sat Nov 09, 2002 at 07:13:11 AM EST

What I was actually referring to was your statement that inserting the complete title of every referenced document would make the sentence "much longer", to which I provided an alternative method, which is in fact much shorter.

But I was thinking of something and wrote something else---my mistake.

By the way, if you don't count the references to the footnotes (the numbers in brackets), my sentece has the same number of letters, less words and less syllables ;-).

[ Parent ]

The problem is (none / 0) (#51)
by Spendocrat on Sat Nov 09, 2002 at 08:00:21 PM EST

Your sentence makes having hypertext much less useful. If you're moving the links out from the sentence itself, why use hypertext at all?

[ Parent ]
no problem (4.50 / 2) (#52)
by nex on Sun Nov 10, 2002 at 12:26:49 PM EST

footnotes are a bad solution in most cases. i suggested them for a very specific use case someone else constructed. of course, while they make sense in a few specific situations, using "here, here and here" also makes sense in a few specific situations. however, as constructs like that are mostly used in really unappropriate contexts, i react more sensitive to them. and i try to avoid them wherever possible, because every occurence of a hyperlinked "here" reeks like "unexperienced newbie". it's something like an on-line equivalent to 'orphans' and 'widows' in typography.

the usefulness of hypertext is also degraded by nondescript links.

[ Parent ]

Much improved, more understandable (none / 0) (#32)
by daragh on Thu Nov 07, 2002 at 05:03:23 AM EST

I look forward to the next installments and hope you take as much care with them.

No work.

Thanks (none / 0) (#35)
by mreardon on Thu Nov 07, 2002 at 08:05:57 AM EST

I look forward to the rest of the series.

Very interesting.... (none / 0) (#37)
by lithmonkey on Thu Nov 07, 2002 at 12:31:32 PM EST

...but I don't think that will help me configure my laptop to find my network printer.
;)

Nitpicking, or outright flaw? (4.00 / 1) (#41)
by mindstrm on Thu Nov 07, 2002 at 06:16:53 PM EST

"So, what exactly is "routing"? Routing is simply a source host attempting to find a destination host. Basically, your source IP address asks your default gateway: A)how the heck does it get to its requested destination? and B)would you please take me there? "

This is not correct; routing management protocols like RIP and OSPF are NOT "routing". Routing is the act of looking at a packet and deciding where it goes.

Routing is not your source IP address asking your gateway how to get a packet to a destination; routing is the packet being compared to a routing table on the local host and then sent to the next hop, repeated until the destination is reached, no further hops can be found, or the ttl expires.

I might be nitpicking... but the title of the article would lead me to expect an explanation of how ip routing works, but instead it goes into how route management works.


Elguapo's Guide to Routing | 52 comments (18 topical, 34 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!