In the past ten years, with the continuous expansion of the scale of computer networks and the rapid development of large-scale Internet networks (such as the Internet), routing protocol technology has gradually become a key part of network technology, and routers have also become the most important network equipment. The needs of users drive the development of routing protocol technology and the popularization of routers. People are no longer satisfied with sharing information only on the local network, but want to maximize the use of various types of network resources in various regions of the world. In the current situation, any computer network with a certain scale (such as enterprise network, campus network, intelligent building, etc.), no matter whether it adopts fast network technology, FDDI technology, or ATM technology, it is inseparable from routers , otherwise it cannot function and manage properly.
1. Routing Protocol
There are two typical routing methods: static routing and dynamic routing.
A static route is a fixed routing table set in a router. Static routes do not change unless network administrators intervene. Since static routes cannot reflect changes in the network, they are generally used in networks with small network scale and fixed topology. The advantages of static routing are simplicity, efficiency, and reliability. Among all routes, static routes have the highest priority. When a dynamic route conflicts with a static route, the static route prevails.
Dynamic routing is a process in which routers in the network communicate with each other, transmit routing information, and update the router table with the received routing information. It can adapt to changes in network structure in real time. If the routing update information indicates that the network has changed, the routing software will recalculate the route and issue a new routing update information. The information passes through each network, causing each router to restart its routing algorithm and update its routing table to dynamically reflect changes in network topology. Dynamic routing is suitable for large-scale networks and complex network topologies. Of course, various dynamic routing protocols occupy network bandwidth and CPU resources to varying degrees.
Static routing and dynamic routing have their own characteristics and scope of application, so dynamic routing is usually used as a supplement to static routing in the network. When a packet is routed in a router, the router first searches for a static route, and if found, forwards the packet according to the corresponding static route; otherwise, searches for a dynamic route.
According to whether it is used in an autonomous domain, dynamic routing protocols are divided into interior gateway protocol (IGP) and exterior gateway protocol (EGP). The autonomous domain here refers to a network with a unified management organization and a unified routing policy. The routing protocol used in the autonomous domain is called the interior gateway protocol, and the commonly used ones are RIP and OSPF; the external gateway protocol is mainly used for routing between multiple autonomous domains, and the commonly used ones are BGP and BGP-4. A brief introduction is given below.
1.1 RIP Routing Protocol
The RIP protocol was originally designed for the Xerox parc general protocol of the Xerox network system, and is a commonly used routing protocol in the Internet. RIP uses the distance vector algorithm, that is, the router selects the route according to the distance, so it is also called the distance vector protocol. A router collects all the different paths that can reach a destination and keeps path information about the minimum number of stations to each destination, discarding any information other than the best path to the destination. At the same time, the router also informs other neighboring routers of the collected routing information using the RIP protocol. In this way, the correct routing information is gradually spread to the entire network.
RIP is widely used, it is simple, reliable, and easy to configure. But RIP is only suitable for small, homogeneous networks because it allows a maximum number of sites of 15, and any destination beyond 15 is marked as unreachable. Moreover, the broadcast of routing information every 30s by RIP is also one of the important reasons for the broadcast storm of the network.
1.2 OSPF Routing Protocol
In the mid-1980s, RIP could no longer adapt to the interconnection of large-scale heterogeneous networks, and OSPF came into being. It is a routing protocol developed for IP networks by the Interior Gateway Protocol Working Group of the Internet Engineering Task Force (1ETF).
0SPF is a link-state-based routing protocol that requires each router to send link-state broadcast information to all other routers in its same administrative domain. All interface information, all metrics and some other variables are included in the link state broadcast of OSPF. A router using OSPF must first collect relevant link state information and calculate the shortest path to each node according to a certain algorithm. The distance vector-based routing protocol only sends information about routing updates to its neighboring routers.
Different from RIP, OSPF subdivides an autonomous domain into areas, and accordingly, there are two types of routing methods: when the source and destination are in the same area, intra-area routing is used; when the source and destination are in different areas , the interval routing is used. This greatly reduces network overhead and increases network stability. When a router in one area fails, it does not affect the normal operation of routers in other areas in the autonomous area, which also brings convenience to network management and maintenance.
1.3 BGP and BGP-4 Routing Protocols
BGP is an exterior gateway protocol designed for the TCP/IP Internet and used between multiple autonomous domains. It is neither based on a pure link state algorithm nor a pure distance vector algorithm. Its main function is to exchange network reachability information with BGP in other autonomous domains. Each autonomous domain can run different interior gateway protocols. The BGP update information includes pairing information of network number/autonomous domain path. The autonomous domain path includes the autonomous domain string that must pass through to reach a specific network, and these update information are sent out through TCP to ensure the reliability of transmission.
In order to meet the ever-expanding needs of the Internet, BGP continues to develop. In the latest BGp4, it is also possible to combine similar routes into one route.
1.4 Priority of Routing Table Entries
In a router, static routes and one or more dynamic routes can be configured at the same time. The routing tables maintained by each of them are provided to the forwarder, but the entries of these routing tables may conflict. This conflict can be resolved by configuring the priority of each routing table. Usually, the static route has the highest priority by default. When other routing table entries contradict it, the static route is forwarded.
2. Routing principle
When a host in an IP subnet sends an IP packet to another host in the same IP subnet, it will directly send the IP packet to the network, and the other party can receive it. When it wants to send a host with a different IP on the network, it needs to select a router that can reach the destination subnet, send the IP packet to the router, and the router is responsible for sending the IP packet to the destination. If no such router is found, the host sends the IP packet to a router called the "default gateway". The "default gateway" is a configuration parameter on each host, which is the IP address of a router port connected to the same network.
When a router forwards an IP packet, it only selects an appropriate port according to the network number part of the destination IP address of the IP packet and sends the IP packet out. Like the host, the router also needs to determine whether the port is connected to the destination subnet. If it is, it directly sends the packet to the network through the port. Otherwise, it also selects the next router to transmit the packet. A router also has its default gateway for forwarding IP packets it doesn't know where to send it. In this way, the IP packets that know how to be transmitted are correctly forwarded through the router, and the IP packets that are not known are sent to the "default gateway" router. In this way, the IP packets will eventually be sent to the destination, but cannot be sent to the destination. IP packets are discarded by the network.
At present, TCP/IP networks are all interconnected through routers, and the Internet is an international network in which thousands of IP subnets are interconnected through routers. This kind of network is called a router based network, which forms an "internet" with routers as nodes. In the "internet", the router is not only responsible for forwarding IP packets, but also responsible for communicating with other routers to jointly determine the routing of the "internet" and maintain the routing table.
Routing actions include two basic elements: routing and forwarding. Routing is to determine the best path to reach the destination, which is realized by routing algorithm. Since it involves different routing protocols and routing algorithms, it is relatively complicated. In order to determine the best path, the routing algorithm must start and maintain a routing table containing routing information, which varies depending on the routing algorithm used. The routing algorithm fills the different information collected into the routing table, and according to the routing table, the relationship between the destination network and the next hop (nexthop) can be told to the router. The routers exchange information for routing update, update and maintain the routing table to correctly reflect the topology changes of the network, and the routers determine the best path according to the metrics. This is the routing protocol (rouTIng protocol), such as Routing Information Protocol (RIP), Open Shortest Path First (OSPF) and Border Gateway Protocol (BGP) and so on.
Forwarding is the transmission of information packets along the best route that has been routed. The router first looks in the routing table to determine whether it knows how to send the packet to the next site (router or host). If the router does not know how to send the packet, it usually discards the packet; otherwise, the packet is discarded according to the corresponding entry in the routing table. Send to the next site, if the destination network is directly connected to the router, the router will send the packet directly to the corresponding port. This is the routed protocol (routed protocol).
Routing forwarding protocol and routing protocol are mutually cooperative and independent concepts. The former uses the routing table maintained by the latter, while the latter uses the functions provided by the former to publish routing protocol data packets. The routing protocols mentioned below, unless otherwise specified, refer to routing protocols, which is also a common practice.
3. Routing algorithm
The routing algorithm plays a crucial role in the routing protocol. The algorithm used often determines the final routing result. Therefore, the routing algorithm must be selected carefully. Generally, the following design goals need to be comprehensively considered:
3.1 Optimization: refers to the ability of the routing algorithm to select the best path.
3.2 Simplicity: Algorithms are designed concisely to provide the most efficient functions with the least software and overhead.
3.3 Robustness: The routing algorithm operates correctly under abnormal or unpredictable circumstances, such as hardware failure, high load, or operational errors. Because routers are distributed across network junctions, there are serious consequences when they fail. The best router algorithms usually stand the test of time and are proven reliable in a variety of network environments.
3.4 Fast Convergence: Convergence is the process in which all routers reach agreement on the judgment of the best path. When a network event causes a route to be available or unavailable, the router sends out an update. The routing update information spreads throughout the entire network, triggering recalculation of the best path, and finally reaching the best path that is agreed upon by all routers. Routing algorithms with slow convergence can cause path loops or network interruptions.
3.5 Flexibility: The routing algorithm can quickly and accurately adapt to various network environments. For example, if a network segment fails, the routing algorithm needs to quickly detect the failure and choose another optimal path for all routes using that network segment.
Routing algorithms can be classified into the following categories according to their types: static and dynamic, single-path and multi-path, equal and hierarchical, source routing and transparent routing, intra-domain and inter-domain, link state and distance vector. The features of the first few are basically the same as the literal meaning. The following focuses on the link state and distance vector algorithm.
Link-state algorithms (also called shortest-path algorithms) send routing information to all nodes on the Internet, however, for each router, only the portion of its routing table that describes its own link state is sent. The distance vector algorithm (also known as the Bellman-Ford algorithm) requires each router to send all or part of its routing table information, but only to neighboring nodes. Essentially, link-state algorithms send small amounts of updates throughout the network, while distance-vector algorithms send large amounts of updates to neighboring routers.
Since the link-state algorithm converges faster, it is somewhat less prone to routing loops than the distance-vector algorithm. But on the other hand, the link state algorithm requires more CPU power and more memory space than the distance vector algorithm, so the link state algorithm will be more expensive to implement. Apart from these differences, both algorithms work well in most environments.
Finally, it should be pointed out that routing algorithms use many different metrics to determine the best path. A complex routing algorithm may use a variety of metrics to select routes, combine them into a single composite metric through a certain weighted operation, and then fill it into the routing table as a path-finding standard. The commonly used metrics are: path length, reliability, delay, bandwidth, load, communication cost, etc.
