What is the route?
The so-called route refers to the activity of moving information from the source location to the target location by interconnecting networks. In general, during the routing process, the information will pass at least one or more intermediate nodes. Typically, people will compare routing and exchanges, mainly because the functions implemented in ordinary users are exactly the same. In fact, the main difference between routing and exchange is to exchange the second layer (data link layer) that occurs in the OSI reference model, while the route occurs in the third layer, ie the network layer. This difference determines that the route and exchange in the process of mobile information requires different control information, so the approach to each function is different.
As early as 40 years, the discussion of routing technology has emerged, but it has gradually entered commercial use in the 1980s. The reason why routing technology is not widely used in the early adventive. It is because the network structure before the 1980s is very simple, and the routing technology has no use of martial arts. Until for more than a decade, a large-scale Internet network gradually became popular, providing a good foundation and platform for the development of routing technology.
Composition of routing technology
The routing technology we usually said is actually composed of two most basic activities, namely the optimal path and transmission information unit (also known as a packet). Among them, the transmission and exchange of packets is relatively simple and straightforward, while the determination of the route is more complex.
Determine the route
Metric (Metric), such as path length, etc., is a criteria for calculating and determining the optimal path to destination. To help determine the path of data transmission, the routing algorithm can establish and maintain the routing table. Various route information is included in the routing table. Routing information is different depending on the route algorithm used.
The routing algorithm writes a variety of different information in the routing table, and the router selects the optimal path according to the destination to be reached by the data package to send the packet to the next router that can reach the destination. When the next router receives the packet, its destination address is also viewed, and the router is transferred to the rear router using the appropriate path. Up to the packet until the packet reaches the final destination.
In addition to the two information we see in the above figure, the routing table also contains other information about routing and select value. The router determines the optimal path by comparing the measured value of different paths, and the specific metrics must be determined by the route algorithm used. We will introduce some of the more common metrics in the article.
Mutual communication can be performed between the routers, and the respective routing tables can be maintained by transmitting different types of information. Routing update information is such information, which is generally consisting of partial or all routing tables. The router can master the topology of the entire network by analyzing routing information issued by other routers. Link Status Broadcasting is another information transmitted between the router, which can be notified to other routers in a timely notification of the link state of the information sender.
Packet exchange
The switching algorithm relative to the routing algorithm is more simple, and most of the routing protocols can use the same exchange technology. When the sender of the data packet acquires the address of the router through a certain manner, the packet is transmitted in the physical address (MAC address) of the router, and the final destination of the network layer address identifies the data packet.
When the router receives the packet, the protocol address indicating its destination will be viewed and the packet is declared to forward the packet to the next router. If the router does not know how to forward the packet to its destination, the packet is usually discarded. If the router knows the forwarding path of the packet, it will change the physical address to the next router, and then send it out. Up to this class until the packet reaches the final destination. During the whole process, the physical address of the packet changes with the different routers passing through the movement process, but the protocol address representative of the destination remains unchanged.
Routing algorithm
The routing algorithm is mainly determined by several key factors. First, the design intent of the algorithm has a great impact on the actual operation of the routing protocol. Second, there are currently many different types of routing algorithms, each algorithm has different requirements and impact on networks and router resources. Finally, the routing algorithm uses different metrics, thereby making the calculation results of the optimal path. plan for design
Typically, a routing algorithm can reflect the following designs:
Optimality
Simple, low overhead
Stunning, stable
Quick gather
Strong applicability
The optimality is the ability to select the optimal path of the routing algorithm, depending on the metrics used in calculating the best path. For example, a routing algorithm can simultaneously use a data packet through the number of hops and time delays as metrics, while it is delayed as the main criteria. Each routing protocol must strictly define the calculation method of the measurement.
The design of the route protocol should be as simple as possible. In other words, the routing algorithm must be able to exert its function in the most effective way, minimize software and use overhead. Especially when implementing the software of the routing algorithm can only be more important when running on a limited robot, the validity is more important.
The routing algorithm must have good robustness, which can operate normally when an abnormality or an emergency (such as hardware damage, too high and performing error, etc.). Because routers are often a network connection node, if there is a problem, it will bring very serious consequences. Therefore, the best routing algorithm should be able to withstand the test, and the stable operating state can be maintained under different network conditions.
The routing algorithm should also be able to get rapidly. The so-called aggregation means that all routers reach an agreement on the optimal path. When a problem occurs properly because some reason, the router will issue routing update information to all networks, recalculate the optimal path, and eventually make all routers agree on new paths. The routing algorithm that is slow in gathering speed may cause the routing loop.
In the routing loop shown below, a packet arrives at router 1 at time t1. Since the information in the router 1 has been updated, the router knows the optimal path to the destination to the packet destination should pass through the router 2. Therefore, the router 1 forwards the packet to the router 2. However, the information in the router 2 is not updated, so it is still considered that the optimal path should pass through the router 1, and thus forward the packet to the router 1. In this way, the data packet can only be passed back and forth between two routers until the router 2 receives routing update information or the packet beyond the maximum survival time.
The routing algorithm should also have very good adaptability to quickly and accurately adapt to different network environments. For example, assuming a problem with a network segment, many routing protocols can quickly select the new best path to replace the original path that has not been used. The routing algorithm should be able to change the variables of parameter variables such as network bandwidth, network delay.
Algorithm type
The routing algorithm can be divided into many different types. The main classification criteria are as follows:
Static VS Dynamics
Single path VS multipath
Single layer structure VS hierarchical structure
Host intelligent VS router smart
Domain VS domain
Link status VS distance vector
Static VS Dynamics
The static routing algorithm is not a truly routing algorithm, but is just a routing mapping table that is pre-established by the network administrator before starting the network routing function. Unless the administrator is modified, the content of the mapping table does not change any changes. The algorithm using static routes is very simple in design, mainly suitable for use in environmentally predictable, network structure relatively simple environments.
Since the static routing system cannot respond to network changes, it is not applicable to today's large, dynamic networks. Most mainstream routing algorithms currently used are dynamic routing algorithms, which can be adjusted accordingly by analyzing the received routing update information. If the network changes, routing software will recalculate new routes and send new route updates information. Update information can be spread throughout the network, all of which re-executes their respective routing algorithms, and make corresponding modifications to the routing table. Static routing and dynamic routes are not fully aligned. In the appropriate environment, both can organically combine together and complement each other. For example, we can create a static route, specify a special router as the last resort router to receive all packets that cannot be properly routed, so we can guarantee that all information can be processed in some way. .
Single path VS multipath
Some complex routing protocols can support multiple paths to the same destination. Unlike single path algorithms, multi-path algorithms can realize multiple multiplexing of data traffic between multiple paths. The advantages of multi-path routing algorithms are very obvious, providing greater data throughput while enhancing the reliability of the network.
Single layer structure VS hierarchical structure
In a single-level routing system, all routers are all right; in the hierarchical routing system, it is a routing of a part of the router. Any host transmitted packet first passes the non-mainstry router to the main router, and then passes along the routing trunk. When arriving at the network area of the destination, transfer from the main router into the non-mainstry router and eventually arrived at the target recipient.
Typically, we call the local node group in the routing system as a domain, autonomous system, or zone. In a hierarchical routing system, some routers in one domain can communicate with routers located in other domains, while others can only communicate with routers in the domain. In larger networks, there may be more routing levels, while routing is generally consisting of routers located at the highest level.
The biggest advantage of the layered routing is that its composition structure is consistent with the management and organizational structure we used in real companies, so it can support the company's internal data traffic and mode. For example, in the enterprise network, most of the network communication occurs in a small group or domain, so the domain router only needs to know how to communicate with other routers in the domain, do not care about other domains. Router. In this way, the routing algorithm can be simplified, and the route update traffic is reduced accordingly.
Host intelligent VS router smart
The so-called host intelligence algorithm is that the sender of the packet determines the complete route in the entire transmission process, and is generally referred to as a source route. In the source routing system, the role of the router is just simple storage and forwarding.
The basis of the router intelligence algorithm is that the sender of the packet is assumed that the route does not have any decisive capabilities, completely by the router based on the respective calculation methods to select and determine the transmission path of the data.
Domain VS domain
Some routing algorithms can only be used in separate domains, while others can be used in the domain in the domain. The nature of these two algorithms is different, and therefore, a good domain is often not necessarily used in a domain environment.
Link status VS distance vector
Link status algorithm (also known as the shortest path priority algorithm) can pass routing information to all nodes on the network. However, each router only sends the small part of the routing information that describes its link state to the outside world. The distance vector algorithm (also known as a Bellman-Ford algorithm) requires every router to send all or most of the routing table information, but this information can only be sent to the approaching router. Thus, the difference between the two is that the link state algorithm can send a small amount of updated information to the entire network range, and the distance vector algorithm is only a large amount of update information that can only send a large amount of update to the adjacent router.
Because the gathering speed of the link state algorithm is relatively fast, it is more effective than the distance vector algorithm to avoid the occurrence of routing circuits. However, from another aspect, the link state algorithm needs to take up more CPU processing time and system memory, so the implementation and support costs of the distance vector algorithm are higher. In addition to the differences mentioned here, both routing algorithms can be used in most network environments. Routing metrics
The routing algorithm uses many different metrics to determine the best path. Some complex routing algorithms can be integrated with several independent metrics, making more comprehensive and accurate routing decisions. The following is the most common route metrics:
Path length
reliability
Delay
bandwidth
load
Communication cost
The path length is the most common route metric. Some routing protocols allow network managers to specify routing costs for each network connection. In this case, the path length is the sum of all routes related to the connection. Other routing protocols can also define the number of hops, ie the data packets from the source address to the network interconnect device (such as routers, etc.) that must pass through the destination.
In the scope of the routing algorithm, reliability mainly refers to the usability of each network connection (usually using bit error rate representation). Some network connections may be more prone to problems than other connections. After network failure fix, some network connections may be faster or more convenient than other connections. Network managers can take care of any reliability factors and specify a corresponding reliable value for each network connection.
Routing delay refers to the sum of time to move the packet from the source address to the destination over the network. There are many factors that can cause routing delays, including the bandwidth of the network connection, each passage, network congestion, and physical distance needed by the data package. Because routing delay is a comprehensive reflection of multiple important variables, it is generally adopted.
Bandwidth refers to the traffic throughput that can be provided by a network connection. Obviously, the bandwidth of 10-Mbps Ethernet is greatly higher than the bandwidth of the 64-Kbps line. Although bandwidth reflects the maximum rate capable of providing a network connection, it is sometimes the use of broadband connections and is not necessarily the optimal path. For example, if a high speed connection is very busy, the time actually waiting for the delivery of a packet may be longer.
The load refers to the busyness of network resources and devices such as routers. We can calculate the load, such as the usage rate of the CPU, and the number of packets that can be processed per second. Long-term continuous monitoring for routing loads can be more efficient to manage and configure network resources.
Communication cost is another very important routing metric, especially for companies that focus on operating costs relative to network performance, their importance is more obvious. For example, sometimes the enterprise will use the cost of the use of public lines to switch to a larger private line, which is the specific embodiment of communication costs.
