1. What is routing
Routing is the act of passing information from the source through the network to the destination. On the road, it encounters at least one intermediate node. Routers are usually compared to bridges, and to the careless people, they seem to accomplish the same thing. Their main difference is that bridging occurs at the second layer (link layer) of the OSI reference protocol, while routing occurs at the third layer (network layer). This difference causes the two to use different information in the process of passing information, thereby completing their tasks in different ways.
The topic of routing has long appeared in the computer world, but it was not until the mid-1980s that commercial success was achieved. The main reason for this delay was that the network in the 1970s was very simple, and large networks were later more common.
2. The composition of the route
Routing involves two basic actions: determining the best path and transmitting information over the network. In the process of routing, the latter is also called (data) exchange. Exchange is relatively simple, while selection paths are complicated.
1. Path selection
metric is a metric criterion used by routing algorithms to determine the optimal path to a destination, such as path length. To help select routes, the routing algorithm initializes and maintains a routing table containing path information, which varies according to the routing algorithm used.
The routing algorithm fills the routing table based on a lot of information. Purpose/Next Hop Address The best way to inform the router to reach this goal is to send the packet to the router representing the "next hop". When the router receives a packet, it checks its destination address and tries to associate this address with its "next hop".
The routing table may also include other information. The routing table compares metrics to determine the best paths, which vary according to the routing algorithm used, and the common metrics will be described below. Routers communicate with each other and maintain their routing tables by exchanging routing information. The routing update information usually contains all or part of the routing tables. By analyzing routing update information from other routers, the router can establish a network topology diagram. Another example of information sent between routers is link status broadcast information, which notifies other router senders of the link status. The link information is used to establish a complete topology map so that the router can determine the optimal path.
2. Exchange
The switching algorithm is relatively simple and is the same for most routing protocols. In most cases, a host decides to send data to another host. After obtaining the address of the router through certain methods, the source host sends a packet pointing to the physical (MAC) address of the router, and its protocol address points to the destination host.
After the router checks the destination protocol address of the packet, it determines whether it knows how to forward the packet. If the router does not know how to forward it, it usually discards it. If the router knows how to forward, it turns the destination physical address into the next hop physical address and sends it to it. The next hop may be the ultimate destination host, if not, usually another router, which will perform the same steps. When a packet flows in the network, its physical address is changing, but its protocol address remains unchanged.
The exchange between the source system and the destination system is described above, and the ISO defines the terminology used to describe the hierarchy of this process. In this term, network devices that do not have the ability to forward packets are called end systems (ES--end systems), and those that have this ability are called intermediary systems (IS--intermediate systems). IS is further divided into intradomain IS (intradomain IS) that can communicate within the routing domain and interdomain IS (interdomain IS) that can communicate within the routing domain. Routing domains are usually considered to be part of the network under unified management and comply with a specific set of management rules, also known as the autonomous system utonomous system). In some protocols, the routing domain can be divided into routing intervals, but the intra-domain routing protocol can still be used to exchange data within and between intervals.
3. Routing algorithm
Routing algorithms can be distinguished based on multiple characteristics. First, the specific goals of the algorithm designer affect the operation of the routing protocol; second, there are multiple routing algorithms, each of which has different impacts on network and router resources; finally, the routing algorithm uses multiple metrics to affect the calculation of the optimal path. The following chapter analyzes the characteristics of these routing algorithms.
1. Design objectives
Routing algorithms usually have one or more of the following design goals: Optimization Simple, low-consumption Robust, stable Fast aggregation Flexibility
Optimization refers to the ability of the routing algorithm to select the best path and calculates it based on the value and weight of the metric. For example, there is a routing algorithm that may use hop counts and delays, but the weights of the delays may be larger. Of course, the routing protocol must strictly define the algorithm for calculating metrics.
The routing algorithm can also be designed as simple as possible. In other words, routing protocols must provide their functionality efficiently, minimizing overhead for software and applications. Efficiency is especially important when software that implements routing algorithms must run on computers with limited physical resources.
The routing algorithm must be robust, i.e. it must still be handled normally in the event of abnormal or unforeseen events, such as hardware failures, high loads, and incorrect implementations. Because routers are located at the connection points of the network, they can cause major problems when they fail. The best routing algorithms are usually those that have been tested by time and proved to be stable under various network conditions.
In addition, routing algorithms must be able to aggregate quickly, aggregation is the process by which all routers agree on the optimal path. When a network event causes the path to be broken or unavailable, the router distributes the route update information through the network, prompting the recalculation of the optimal path, and ultimately all routers agree. Routing algorithms with very slow aggregation may cause routing loops or network interrupts.
Routing algorithms should also be flexible, that is, they should adapt quickly and accurately to various network environments. For example, if a network segment is broken, when you know the problem, many routing algorithms will quickly select the next best path for the path that usually uses the network segment. The routing algorithm can be designed to adapt to network bandwidth, router queue size, and network latency.
2. Algorithm type
The differences between each routing algorithm include:
- Static and dynamic
- Single and multipath
- Flat and layered
- Host Intelligence and Router Intelligence
- Intra-domain and inter-domain
- Link state and distance vector
(1) Static and dynamic
Static routing algorithms are hard to be considered as algorithms, but they are just table mappings established by the network management before starting routing. These mappings themselves do not change unless the network administrator changes. Algorithms using static routing are easier to design and work well in predictable network communications and simple networks.
Since static routing systems cannot reflect network changes, they are usually considered unsuitable for today's large, variable networks. The main routing algorithms in the 1990s were dynamic routing algorithms, which adapted to changes in the network environment by analyzing the received routing update information. If the information indicates that a network has changed, the routing software recalculates the route and issues new route update information. This information penetrates the network, prompting the router to recalculate and make corresponding changes to the routing table.
Dynamic routing algorithms can be supplemented by static routing where appropriate. For example, the last router (router of last resort) is the way to all non-routable packets, ensuring that all data has at least a method to process.
(2) Single path and multipath
Some complex routing protocols support multiple paths to the same purpose. Unlike single-path algorithms, these multipath algorithms allow data to be multiplexed on multiple lines. The advantages of multipath algorithms are obvious: they provide better throughput and reliability.
(3) Flat and layered
Some routing protocols operate in flat spaces, while others have routing levels. In a flat routing system, each router is peer to all other routers; in a hierarchical routing system, some routers form the routing backbone, and data flows from the non-backbone router to the backbone router, and then transmitted on the backbone until they reach the target area, where they reach the end point from the last backbone router through one or more non-backbone routers.
Routing systems are usually designed with logical node groups, called domains, autonomous systems, or intervals. In a hierarchical system, some routers can communicate with routers in other domains, while others can only communicate with routers in the domain. In large networks, there may be other levels, and the most advanced routers form the routing backbone.
The main advantage of hierarchical routing is that it simulates the structure of most companies, so it can support their communications well. Most network communication occurs in groups (domain). Because routers in the domain only need to know other routers in the domain, their routing algorithms can be simplified, and according to the routing algorithm used, the traffic of route updates can be reduced accordingly.
(4) Host intelligence and router intelligence
Some routing algorithms assume that the source node determines the entire path, which is often called source routing. In the source routing system, the router acts as a storage forwarding device, unconsciously sending packets to the next hop. Other routing algorithms assume that the host knows nothing about the path, in which the router decides the path through the network based on its own calculations. In the former system, the host has the intelligence to determine routing, while the latter has this capability for the router.
The tradeoff between host intelligence and router intelligence is actually the balance between optimal routing and extra overhead. Host intelligent systems can usually choose better paths because they explore all possible paths before sending data, and then choose the best path based on the definition of "optimization" for a particular system. However, determining the behavior of all paths usually takes a lot of exploration traffic and a long time.
(5) Intra-Domain and Inter-Domain
Some routing algorithms work only within the domain, while others work both within and between domains. The essence of these two algorithms is different. The reason it follows is that the optimized intra-domain routing algorithm is not necessary and also becomes an optimized inter-domain routing algorithm.
(6) Link status and distance vector
The link state algorithm (also called the short path priority algorithm) distributes routing information to every node of the network, but each router only sends the part of the routing table that describes its own link state. Each router in the distance vector algorithm (also called the Bellman-Ford algorithm) sends all or part of the routing table, but only sends it to its neighbors. That is, the link state algorithm sends less update information everywhere, while the distance vector algorithm sends more update information to adjacent routers.
Because link state algorithms are aggregated faster, they tend to generate routing loops relative to distance algorithms. On the other hand, the link state algorithm requires more CPU and memory resources, so the implementation and support of the link state algorithm are more expensive. Although there are differences, both algorithm types work well in most environments.
3. Routed metric
The routing table contains information used by the exchange software to select the best path. But how is the routing table established? What is the essence of information they contain? How does a routing algorithm decide which path is better based on this information?
The routing algorithm uses many different metrics to determine the optimal path. Complex routing algorithms can select routes based on multiple metrics and combine them into a composite metric. Commonly used metrics are as follows:
- Path length
- Reliability
- Delay
- Bandwidth
- Load
- Communication cost
Path length is the most commonly used route metric. Some routing protocols allow network management to manually assign substitution value to each network link. In this case, the routing length is the sum of the costs of the various links passed through. Other routing protocols define the number of hops, that is, the number of network products that packets must pass through on the way from source to destination, such as the number of routers.
Reliability, in routing algorithms, refers to the dependency of network links (usually described as bit error rate). Some network links may fail more than others. After the network fails, some network links may be easier or faster to repair than others. Any reliability factor can be calculated when assigning a value to the reliability rate, and usually the network administrator assigns a metric value to the network link.
Routing delay refers to the time it takes for a packet to arrive at a destination from the source through the network. Many factors affect latency, including the bandwidth of the intermediate network link, the port queues passing through each router, the congestion level of all intermediate network links, and the physical distance. Because delay is a mixture of multiple important variables, it is a relatively common and effective metric.
Bandwidth refers to the available circulation capacity of the link. When all other conditions are equal, a 10Mbps Ethernet link is preferable to a 64kbps dedicated line. Although bandwidth is the maximum throughput available for a link, routing through a link with a larger bandwidth is not necessarily better than routing through slower links. For example, if a fast link is busy, it may take longer to reach the destination for a group.
Load refers to the busyness of network resources, such as the router. The load can be calculated in many ways, including CPU usage and processing of packets per second. Continuous monitoring of these parameters is also very resource-intensive.
Communication costs are another important metric, especially when some companies may have more operating costs than performance. Even if the line delay may be long, they would rather send data through their own lines than use expensive public lines.
IV. Network protocol
The routing protocol is transmitted by the routing protocol, also known as the network protocol.
These network protocols perform various functions required to communicate between user applications of source and destination devices, and these functions may vary widely across protocols. The network protocol occurs at the upper four layers of the OSI reference model: the transport layer, the session layer, the presentation layer, and the application layer.
The terms routed protocol (a protocol that can be routed) and routing protocol (a routing protocol) are often confused. The routed protocol is routed in the network, such as IP, DECnet, AppleTalk, Novell NetWare, OSI, Banyan VINES, and Xerox Network System(XNS). The routing protocol is a protocol that implements routing algorithms. Simply put, it guides the network protocol. Routing protocols such as: IGRP, EIGRP, OSPF, EGP, BGP, IS-IS and RIP, etc.
The above is all the content of this article. I hope it will be helpful to everyone's study and I hope everyone will support me more.