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

I. routing table

In a computer network, a routing table or routing domain information base (RIB) is a spreadsheet (file) or class database stored in a router or networked computer. The routing table stores a path to a specific network address (and in some cases, a routing metric for the path). The routing table contains topology information around the network. The main goal of establishing routing table is to realize routing protocol and static route selection.

In the construction of modern routers, the routing table is not directly involved in packet transmission, but is used to generate a small direction table that contains only the packet transmission priority path selected by the routing algorithm. this table is usually compressed or pre-compiled to optimize hardware storage and lookup.

2. Brief introduction of routing algorithm

Routing algorithm is an algorithm that improves the function of routing protocol and reduces the overhead caused by routing as much as possible. Efficiency is especially important when the software that implements the routing algorithm must run on computers with limited physical resources. Routing algorithms must be robust, that is, they must still be able to handle abnormal or unforeseen events, such as hardware failures, high loads, and incorrect implementations. Because routers are located at the connection point of the network, they can cause major problems when they fail. The best routing algorithms are usually those that have stood the test of time and proved to be stable under various network conditions.

In addition, routing algorithms must be able to aggregate quickly, which is the process by which all routers agree on the best path. When a network event makes the path broken or unavailable, the router distributes routing updates through the network, which promotes the recalculation of the best path and finally makes all routers agree. Routing algorithms with slow aggregation may cause routing rings or network outages.

Third, the target characteristics of routing algorithm

Routing algorithms usually have one or more of the following target characteristics: optimization, simplicity, low consumption, robustness, stability, fast aggregation, flexibility.

(1) Optimization: the ability of a routing algorithm to choose the best path. It is calculated according to the value and weight of metric.

(2) simplicity: algorithm design must be concise. Routing protocols must provide their functions efficiently in the network and minimize the overhead of software and applications. This is especially important when the software that implements the routing algorithm must run on computers with limited physical resources.

(3) robustness: routing algorithms can run correctly when they are in abnormal or unpredictable environments, such as hardware failures, overloads, or operational errors. Because routers are distributed on network connection points, there will be serious consequences when they fail. The best router algorithms usually stand the test of time and have been proved to be reliable in a variety of network environments.

(4) Fast convergence: convergence is a process in which all routers are consistent in judging the best path. When a network event causes a route to be available or unavailable, the router sends out an update message. Routing updates spread throughout the network, causing the best path to be recalculated and finally reaching the best path recognized by all routers. Routing algorithms with slow convergence can cause path loops or network outages.

(5) flexibility: routing algorithms are required to adapt to various network environments quickly and accurately. For example, if a network segment fails, the routing algorithm should be able to quickly detect the failure and choose another best path for all routes using that segment.

IV. Classification of routing algorithms

Routers use routing algorithms to find the best route to their destination. When saying "best route", parameters such as the number of hops (the number of hops (the journey of a packet packet from one router or intermediate node to another node in the network), delay, and packet transmission communication time are considered.

Static routing algorithm can not adjust its routing table according to the changes of network traffic and topology, so it can not find the best route. Dynamic routing algorithm is that the routing of nodes depends on the current state information of the network. This strategy can better adapt to the changes of network traffic and topology, and help to improve the performance of the network. However, because the algorithm is complex, it will increase the burden of the network. The three practical routing strategies are:

(1) distributed routing. Each router has only information about the router to which it is directly connected-- not for each router in the network. These algorithms are also known as DV (distance vector) algorithms.

(2) centralized routing. Each router has all the information about all other routers in the network and the traffic status of the network. These algorithms are also known as LS (link-state) algorithms.

(3) Hybrid dynamic routing. Mix distributed routing with centralized routing and other routing methods.

Distance vector algorithm

Each node periodically sends routing refresh messages to all neighboring nodes. The message consists of a set of ordered data pairs (VMagazine D). V represents the node that the node can reach, and D represents the distance (hop count) to the node. The node that receives the route refresh message recalculates and modifies its routing table.

Distance vector routing algorithm has the advantages of simple and easy to implement. However, it is not suitable for large-scale network environments with drastic routing changes. Because the routing change of a node propagates from the neighboring nodes like waves, the process is very slow, which is called "slow convergence". Therefore, the problem of routing inconsistency may occur during the route refresh process of the distance vector routing algorithm. Another disadvantage of distance vector routing algorithm is that it requires a lot of information exchange, but many of them may have nothing to do with the current route refresh.

VI. Link-state algorithm

⑴ each node must find out all its neighbors

When a node starts, it tells it who it is by sending a special HELLO message on each point-to-point link and sending a reply message through the node at the other end of the link.

⑵ each node measures the delay or other parameters of each of its neighbors

The link-state routing algorithm requires each node to know the delay of each of its neighbors. The most direct way to measure this delay is to send a special ECHO response message on the link between them and ask the other party to send it back as soon as it is received. A more reasonable estimate can be obtained by dividing the measured round-trip time by 2. In order to get more accurate results, you can repeat the test many times and take the average.

⑶ establish Link-status message

After collecting the information for exchange, the next step is to create a message containing all the data for each node. The message begins with the sender's identifier, followed by a sequence number and a list of all its neighbors. For each neighbor, the delay to this neighbor is given.

Setting up link-state messages is easy, but the difficulty is deciding when to build them. One feasible way is to build them periodically at regular intervals. Another feasible method is to establish some important events when the node detects them. For example, when a link or a neighbor crashes or recovers, establish them.

⑷ Distribution Link-status message

The basic distribution algorithm is flooding using sequence numbers. This distribution algorithm may cause different nodes to use different versions of the topology due to the recycling of sequence numbers, the collapse of a node, or the misuse of a sequence number. This will lead to instability, loops, inability to reach the destination machine, and other problems. In order to prevent such errors, it is necessary to include an age field in each message, the age minus 1 per second, and when the age is reduced to 0, the message is discarded.

⑸ calculates new routes

Once a node collects all the link-state messages from other nodes, it can construct a complete network topology based on this, and then use the Dijkstra algorithm to locally construct the shortest path to all possible destinations.

Link-state routing algorithm has the advantages of calculating the shortest path independently, adapting to network changes quickly and exchanging less routing information, but compared with distance vector routing algorithm, it is more complex and difficult to implement.

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.