Shulou(Shulou.com)06/01 Report--

Continue to make up half of what I wrote at the weekend and achieve a perfect day.

One of the facts we know is that there are so many IP addresses that it is impossible to manage them uniformly, both in the data plane and in the control / management plane. Therefore, the IP protocol is designed to be extensible. For IP routing, the routing calculation is hop-by-hop, of course, it also supports the "source routing" option. Source routing means that the data has already planned the route before departure, and hop-by-hop routing is the standard form of IP routing, that is to say, IP packets plan the route immediately on the road.

I prefer IP routing because this is also the way I travel. I like to travel, but I don't like booking hotels in advance, planning routes in advance, navigation, etc., my way is to look at road signs on the road, to a temporary stop after the backpack to find accommodation, and then go wherever you go, this is a kind of wandering with no destination. Of course, IP packets have a destination.

Hop-by-hop global optimization

IP routing is hop-by-hop routing on each router, so there is a problem, such a large Internet, how to believe that so many hop-by-hop routes stitching together a complete path is really optimal? The answer is obviously yes, and the question is how to prove it.

Routing algorithm

According to the book, routing algorithms are basically divided into distance vector algorithms and link-state algorithms, and their respective protocol masterpieces are RIP and OSPF (I found the first job with these two). This is true, but from the process of proving the correctness of these algorithms, you will find that "hop-by-hop optimal routing is really global optimal routing." In this paper, I only give the proof of the Dijkstra algorithm based on the link-state routing protocol, because the link-state database of every device in the network is the same, so it is easy to understand.

Proof of correctness of Dijkstra algorithm

First of all, it is necessary to prove the correctness of the Dijkstra algorithm before the follow-up. After all, the Dijkstra algorithm itself only guides the operation steps of step by step, and does not prove that every path in the shortest path tree is indeed the shortest. This fact is needed to prove the principle of hop-by-hop global optimization.

The following diagram gives a simple proof of the correctness of the Dijkstra algorithm. Detailed and complete mathematical proof can refer to this idea:

The problem of global optimization of hop by hop

The following diagram points to the problem of hop-by-hop global optimization:

Proof of hop-by-hop global optimization

The following diagram gives a simple proof of hop-by-hop global optimization in a variety of ways, and I give only one of them here:

Attached: the greedy model of Dijkstra algorithm

If we pour a glass of water on the ground and observe the traces of the water spreading, we will understand the Dijkstra algorithm, which is indeed self-evident. Nature is lazy and always acts in the most labor-saving way. Water molecules start at that point of landing and reach a series of points along a certain path on the rugged ground due to gravity (not considering other molecular forces for the time being). These paths must be the shortest paths. We can regard the rugged degree of the ground as the weight of the path, which is exactly the same as the Dijkstra algorithm model.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.