Route selection

I have a very basic question but a full answer has been somewhat hard to find. My question is:

"how does routing work?"


(Please no lmgtfy.com/?q=how+does+routing+work )

1. (google result: www.howstuffworks.com/router1.htm )
2. (result within this site: www.firewall.cx/ip_routing.php )
I realize thats a incredibly basic question which normally gets blasted away by the people who assume that I'm looking for the easy answer without looking at all.

My main issue is I know the internet is big....




I mean not even big but incredibly big. Just the fact that IPv4 requires NAT proves that. My issue is I don't understand how I get a ping result from a random IP address in 11 hops when there are SOOOOOO many paths a packet can take and far to many end nodes for every router to have a table entry in it.

I understand how Dijkstra's Algorithm works


I understand that Routers have tables & Default routes that push a packet along the path of least resistance but what I don't understand is:

"How routing works?"

with a more particular depth of

"How does routing work when the internet is so huge a router couldn't hope to hold all the entries of end nodes in a table how is the needle in the hey stack found?"


(Simplified question: The internet is to big for a router to hold all paths in memory so how does it find the needle in the haystack?)


*note: Before anyone flames me for asking too basic of a question keep in mind that I've REALLY looked hard for a satisfying answer and so far have found none. I didn't spend 5 minutes looking for an answer I've spent weeks and it's really depressing that every explanation I find of how a router works tells me exactly what a router is meant to do but not how it manages to find the destination address. I would absolutely love to see an example with the logic each router along a path used to make it's selection. (assuming more than 10 hops)


Thank you for your time.

I think the basic answer is it works through a combination of sensible design, the gateway-of-last-resort and the fact that IP addresses are hierachical. Let me try to explain:
If you live in say the USA and ping an address in Outer Mongolia, your local router does not know, or indeed need to know, all the details of all the possible paths to that destination. All it does is to ask 'is this packet for one of the networks I know about?' It will know about it's locally connected networks and also some remote networks that have been advertised to it by whatever routing protocol it is running. Being Outer Mongolia the destination network is unlikely to feature in that short list, so it just shrugs its shoulders and forwards the packet to its default route, or gateway of last resort. The sensible design comes in because whoever configured that router would have defined the gateway of last resort to be a higher-level router that interconnects branches of the internet rather than mere subscribers or endpoints. Maybe that router in turn doesn't know the destination network. No matter; it just does the same and passes the problem higher up the tree until after maybe ten hops we've arrived at one of the routers handling traffic between say the USA and Europe. That router doesn't know the destination network but does know that the first part of that address range is in Europe somewhere, so across the pond it goes. At the other side the router there knows a little boit more and recognises this is destined for Mongolia. Then the Mongolian border router (if there is such a thing) recognises the traffic is for Outer Mongolia, passes it to an internal router in that country which passes it to a router providing a gateway into that ISP which does know the destination. That's a total of perhaps thirty hops.
Did that help?

There are concepts you need to revisit very well like

route summarisation
DNS referal system

In the explanation the most loyal Bishop gave you, those routers are highly summarised and also work with DNS. every PC most be connected to some ISP who maintains a DNS record and could query the DNS servers of other ISPs.

I am crowded for time now, I will make subsequent contribution is future

:shock:


So your saying that IP ranges are actually grouped into country codes?

That router doesn't know the destination network but does know that the first part of that address range is in Europe somewhere, so across the pond it goes.

This makes a lot of sense. Thank you. I honestly did not know IP ranges were sorted by physical location at all. But given the many sites that can locate things by IP.... I should have guessed:

www.find-ip-address.org/ip-country/
( www.countryipblocks.net/country-blocks/select-formats/ )

Thank you Bishop & Sose!


I'll read more into route summarization and DNS referal system and get back to this topic soon.

Edit/update:

After looking up "route summarization" your correct Sose I could see how that would save processing time and memory on a router making it possible to route smaller and faster.

Router summarization:



I'm still not sure what I'm missing from DNS referral system but then I haven't found a really good example of it.

Glad we're helping. The key concept is the hierachical nature of the IP addressing system. For me to say that every address is simply prefixed with a country code would be a bit of an oversimplification; there are often a number of addressing 'blocks' per country and they might not be contiguous. The point is though that at the international level the router will know which address ranges it can reach via which interfaces. In practice the traffic might pass through several 'international' routers along the internet backbone before it reaches the correct place to jump off. A useful mental model is international travel - If you wanted to travel from say littletown in some state in the US to a village in the UK, you'd go from littletown via local roads then onto a big highway to bigtown airport then fly maybe to London then take a motorway to the nearest UK town then off onto local roads and finally down a country lane to reach the quiet village. What travel decisions would you be making at each step? You wouldn't expect the destination board at bigtown airport to list the name of every village in the UK; you'd just just get on a plane to London

I get a ping result from a random IP address in 11 hops when there are SOOOOOO many paths a packet can take and far to many end nodes for every router to have a table entry in it.

Even I don't understand that when we ping an IP, the max hop count to the destination is always 16???
Please let me know if anyone have the answer.
Thanks