It's called routing. Introduction to IP Routing. Initial and superficial information

First, let's clarify some concepts:

• network node (node) - any network device with TCP/IP protocol;
• host (host) - a network node that does not have packet routing capabilities;
• router - a network node with packet routing capabilities

IP routing is the process of forwarding unicast traffic from a sending node to a receiving node in an IP network with an arbitrary topology.

When one node on an IP network sends a packet to another node, the IP packet header contains the IP address of the sending node and the IP address of the receiving node. The packet is sent as follows:

1. The sending node determines whether the receiving node is on the same IP network as the sender (in local network), or on another IP network (on a remote network). To do this, the sending node performs a bitwise logical multiplication of its IP address by its subnet mask, then a bitwise logical multiplication of the IP address of the recipient node also by its subnet mask. If the results match, then both nodes are on the same subnet. If the results are different, then the nodes are on different subnets.
2. If both network nodes are located on the same IP network, then the sending node first checks the ARP cache to see if the MAC address of the recipient node is in the ARP table. If the required entry is available in the table, then the packets are then sent directly to the recipient node at the link level. If the required entry is not in the ARP table, then the sending node sends an ARP request for the IP address of the recipient node, the response is placed in the ARP table, and after that the packet is also transmitted at the data link level (between network adapters of computers).
3. If the sending node and the receiving node are located on different IP networks, then the sending node sends this packet to the network node, which is specified in the sender's configuration as the "default gateway". The default gateway is always on the same IP network as the sending node, so communication occurs at the data link layer (after an ARP request is made). The default gateway is the router that is responsible for sending packets to other subnets (either directly or through other routers).

Let's consider the example shown in Fig. 4.5.

Rice. 4.5.

IN in this example 2 subnets: 192.168.0.0/24 and 192.168.1.0/24. The subnets are combined into one network by a router. The router interface in the first subnet has an IP address 192.168.0.1, in the second subnet - 192.168.1.1. There are 2 nodes in the first subnet: node A (192.168.0.5) and node B (192.168.0.7). The second subnet has host C with the IP address 192.168.1.10.

If Host A sends a packet to Host B, it will first figure out that Host B is on the same subnet as Host A (ie, the local subnet), then Host A will make an ARP request for IP address 192.168. 0.7. After this, the contents of the IP packet will be transferred to the data link layer, and the information will be transferred from the network adapter of host A to the network adapter of host B. This is an example of direct data delivery (or direct routing, direct delivery).

If host A sends a packet to host C, it will first figure out that host C is on a different subnet (i.e., a remote subnet). Host A will then send the packet to the host that is specified in its configuration as the default gateway (in this case, the router interface with IP address 192.168.0.1). The router on interface 192.168.1.1 will then make a direct delivery to Host C. This is an example of indirect delivery (or indirect delivery) of a packet from Host A to Host C. In this case, the indirect routing process consists of two direct routing operations.

In general, the IP routing process is a series of individual operations that directly or indirectly route packets.

Each network node makes a decision about packet routing based on the routing table, which is stored in random access memory of this node. Routing tables exist not only for routers with multiple interfaces, but also for workstations connected to the network via a network adapter. The routing table in Windows can be viewed using the route print command. Each routing table contains a set of entries. Records can be generated in various ways:

• entries created automatically by the system based on the TCP/IP protocol configuration on each network adapter;
• static entries created by the route add command or in the service console Routing and Remote Access Service ;
• dynamic entries created by different routing protocols (RIP or OSPF).

Let's consider two examples: the routing table of a typical workstation located on a company's local network, and the routing table of a server that has several network interfaces.

Work station.

In this example, there is a workstation with Windows system XP, with one network adapter and the following TCP/IP protocol settings: IP address - 192.168.1.10, subnet mask - 255.255.255.0, default gateway - 192.168.1.1.

Let's enter in command line systems Windows command route print , the result of the command will be the following screen (Fig. 4.6; the text for the English version of the system is given in brackets):

Rice. 4.6.

List of interfaces- a list of network adapters installed on the computer. Interface MS TCP Loopback interface is always present and is intended to refer the node to itself. Interface Realtek RTL8139 Family PCI Fast Ethernet NIC- LAN card.

Network address - the range of IP addresses that are reachable using this route.

Network mask- subnet mask to which the packet is sent using this route.

Gateway address- IP address of the node to which packets corresponding to this route are forwarded.

Interface- network interface designation of this computer, to which packets corresponding to the route are forwarded.

Metrics- conditional cost of the route. If there are several routes for the same network, then the route with the minimum cost is selected. Typically, the metric is the number of routers a packet must go through to get to the desired network.

Let's analyze some rows of the table.

The first row of the table corresponds to the default gateway value in the TCP/IP configuration of this station. The network with address "0.0.0.0" represents "all other networks that do not match other rows in this routing table."

The second line is the route for sending packets from the node to itself.

The third line (network 192.168.1.0 with mask 255.255.255.0) is the route for sending packets to local IP network(i.e. the network in which this workstation is located).

The last line is the broadcast address for all hosts on the local IP network.

The last line in Fig. 4.6 - list of permanent workstation routes. These are static routes that are created with the route add command. In this example there is no such static route.

Now consider a server running Windows 2003 Server, with three network adapters:

• Adapter 1 - located in the company’s internal network (IP address - 192.168.1.10, subnet mask - 255.255.255.0);
• Adapter 2 - located in the external network of the Internet provider ISP-1 (IP address - 213.10.11.2, subnet mask - 255.255.255.248, closest interface in the provider's network - 213.10.11.1);
• Adapter 3 - located in the external network of the Internet provider ISP-2 (IP address - 217.1.1.34, subnet mask - 255.255.255.248, closest interface in the provider's network - 217.1.1.33).

IP networks of providers are conditional, IP addresses are chosen for illustration purposes only (although a coincidence with any existing network is quite possible).

In addition, the Routing Service is installed on the server and remote access For

IN this moment(remember the zero issue) in Moscow we used addresses 172.16.0.0-172.16.6.255. Let’s assume that the network can increase further here, let’s say an office appears on Vorobyovy Gory and we will reserve more subnets up to 172.16.15.0/24 inclusive.
All these addresses: 172.16.0.0-172.16.15.255 - can be described as follows: 172.16.0.0/20. This network (with the /20 prefix) will be the so-called supernet, and the operation of combining subnets into a supernet is called summation subnets (by summarizing routes, to be precise, route summarization)

We apologize for the giant sheets, the video is also getting longer and more unbearable every time. We'll try to be more compact next time.

All interested, but unregistered, are invited to a conversation in LiveJournal.
For preparing the article, many thanks to my co-author thegluck and my wife for the lion’s patience.

For those who are very dissatisfied: this article is not an absolute, it does not fully disclose the theoretical aspects and, therefore, does not pretend to be a full-fledged documentation. From the authors' point of view, this is an aid for beginners, a magical incentive, if you will. On the hub you have the opportunity to put a minus, and not to prove us wrong. I ask you to do just that, because your dissatisfaction will only be met by the above arguments.

Add tags

Routing is the process of determining the route for information in communication networks.

Routes can be specified administratively (static routes) or calculated using routing algorithms based on information about the topology and state of the network obtained using routing protocols (dynamic routes).

Static routes can be:

Routes that do not change over time;

Routes that change according to schedule.

Routing to computer networks typically performed by special software and hardware - routers; in simple configurations can also be performed by general-purpose computers configured accordingly.

In the public sense of the word, routing means the movement of information from a source to a destination through an interconnected network. In this case, as a rule, at least one node is encountered along the way. Routing is often contrasted with the interconnection of networks using a bridge, which, in the popular understanding this method performs exactly the same functions. The main difference between the two is that bridging occurs at Layer 2 of the ISO reference model, while routing occurs at Layer 3. This difference explains why routing and bridging use different information as it moves from source to destination. The result of this is that routing and bridging perform their tasks in different ways; in fact, there are several different types of routing and bridging.

Routing Components

Routing involves two major components: determining optimal routing paths and transporting groups of information (usually called packets) across an internetwork. In this paper, the latter of these two components is called switching. Switching is relatively simple. On the other hand, route determination can be a very complex process.

Defining a route

Route determination can be based on various indicators (values ​​resulting from algorithmic calculations on a single variable - for example, route length) or combinations of indicators. Software implementations of routing algorithms calculate route metrics to determine optimal routes to a destination.

To facilitate the route determination process, routing algorithms initialize and maintain routing tables that contain routing information. Routing information changes depending on the routing algorithm used.

Routing algorithms fill routing tables with a certain amount of information. Destination/Next Hop associations tell the router that a certain destination can be optimally reached by sending a packet to a certain router representing the "next hop" on the way to the final destination. When receiving an incoming packet, the router checks the destination address and tries to associate this address with the next forwarding

Routing tables may also contain other information. "Indicators" provide information about the desirability of a particular channel or path. Routers compare metrics to determine optimal routes. The indicators differ from each other depending on the routing algorithm used. A number of common indicators will be presented and described later in this chapter.

Routers communicate with each other (and maintain their routing tables) by passing various messages. One type of such message is a "routing update" message. Routing updates typically include all or part of the routing table. By analyzing routing update information from all routers, any one of them can build a detailed picture of the network topology. Another example of messages exchanged between routers is a “link-state announcement.” A link-state announcement informs other routers about the status of the sender's links. Link information can also be used to build a complete picture of the network topology. Once the network topology is understood, routers can determine optimal routes to destinations.

Switching

Switching algorithms are relatively simple and are basically the same for most routing protocols. In most cases, the host will determine that the packet needs to be sent to another host. Having received the router's address in a certain way, the source host sends a packet addressed specifically to the physical address of the router (MAC layer), but with the protocol address (network layer) of the destination host.

After checking the packet's destination protocol address, the router determines whether or not it knows how to forward the packet to the next router. In the second case (when the router does not know how to forward the packet), the packet is usually ignored. In the first case, the router forwards the packet to the next router by replacing the destination's physical address with the next router's physical address and then forwarding the packet.

The next transfer may or may not be the final destination's host. If not, then the next hop is usually another router that goes through the same switching decision process. As a packet moves through the Internet, its physical address changes, but its protocol address remains the same. This process is illustrated in the figure.

The above description discusses the switching between the source and the final destination system. The International Organization for Standardization (ISO) has developed a hierarchical terminology that can be useful in describing this process. Using this terminology, network devices that do not have the ability to forward packets between subnets are called end systems (ES), while network devices that do have this ability are called intermediate systems (IS). Intermediate systems are further subdivided into systems that can communicate within "routing domains" ("intra-domain" ISs), and systems that can communicate both within a routing domain and with other routing domains ("inter-domain ISs"). A "routing domain" is generally considered to be part of an integrated network under overall administrative control and governed by a defined set of administrative guidelines. Routing domains are also called "autonomous systems" (AS). For certain protocols, routing domains may be further subdivided into “routing sections,” however, intradomain routing protocols are also used for switching both within and between sections.

Routing Algorithms

Routing algorithms can be differentiated based on several key characteristics. First, the performance of the resulting routing protocol is influenced by the specific problems that the algorithm designer solves. Secondly, there are Various types routing algorithms, and each of them has different effects on the network and routing resources. Finally, routing algorithms use a variety of metrics that influence the calculation of optimal routes. The following sections analyze these attributes of routing algorithms.

Goals of routing algorithm development

Routing algorithms are often designed with one or more of the following goals in mind:

1. Optimality

2. Simplicity and low overhead

3. Vitality and stability

4. Fast convergence

5. Flexibility

Optimality

Optimality is probably the most common design goal. It characterizes the ability of a routing algorithm to select the “best” route. The best route depends on the indicators and the “weight” of these indicators used in the calculation. For example, a routing algorithm might use several hops with a certain delay, but when calculating the "weight" of the delay, it may estimate it to be very significant. Naturally, routing protocols must strictly define their algorithms for calculating indicators.

Simplicity and low overhead

Routing algorithms are designed to be as simple as possible. In other words, the routing algorithm must provide its functionality efficiently, with minimal software overhead and utilization. Efficiency is especially important when the program implementing the routing algorithm must run on a computer with limited physical resources.

Vitality and stability

Routing algorithms must have survivability. In other words, they must function well in the event of unusual or unforeseen circumstances, such as hardware failures, high load conditions, and incorrect implementations. Because Routers are located at network hubs, and their failure can cause significant problems.

Often the best routing algorithms are those that have stood the test of time and proven reliable under a variety of network conditions.

Fast convergence

Routing algorithms must converge quickly. Convergence is the process of agreement among all routers on optimal routes. When some network event causes routes to either be rejected or become available, routers send routing update messages. Routing update messages permeate networks, prompting recomputations of optimal routes and ultimately forcing all routers to agree on those routes. Routing algorithms that converge slowly can lead to routing loops or network failures.

Flexibility

Routing algorithms must also be flexible. In other words, routing algorithms must adapt quickly and accurately to a variety of network circumstances. For example, suppose a network segment is rejected. Many routing algorithms, once aware of this problem, quickly select the next best path for all routes that typically use that segment. Routing algorithms can be programmed to adapt to changes in network bandwidth, router queue sizes, network latency, and other variables.

Types of Algorithms

Routing algorithms can be classified by type. For example, algorithms could be:

1. Static or dynamic

2. Single-route or multi-route

3. Single-level or hierarchical

4. With intelligence in the host or router

5. Intra-domain and inter-domain

6. Algorithms for channel state or distance vector

Static or dynamic algorithms

Static routing algorithms are hardly algorithms at all. The distribution of static routing tables is set by the network administrator before routing begins. It does not change unless the network administrator changes it. Algorithms that use static routes are easy to develop and work well in environments where network traffic is relatively predictable and the network design is relatively simple.

Because Static routing systems cannot respond to changes in the network and are generally considered unsuitable for today's large, constantly changing networks. Most of the dominant routing algorithms of the 1990s. - dynamic.

Dynamic routing algorithms adapt to changing network conditions in real time. They do this by analyzing incoming routing update messages. If the message indicates that a network change has occurred, the routing programs recalculate the routes and send new routing adjustment messages. Such messages permeate the network, prompting routers to re-run their algorithms and change routing tables accordingly. Dynamic routing algorithms can complement static routes where appropriate. For example, you can develop a "last-hit router" (that is, a router to which all packets not sent along a particular route are sent). Such a router acts as a repository for unsent packets, ensuring that all messages will be processed in at least a certain way.

Single-path or multi-path algorithms

Some complex routing protocols provide multiple routes to the same destination. Such multi-route algorithms make it possible to multiplex traffic over multiple lines; single-path algorithms cannot do this. The advantages of multi-path algorithms are obvious - they can provide significantly greater throughput and reliability.

Single-level or hierarchical algorithms

Some routing algorithms operate in flat space, while others use routing hierarchies. In a single-layer routing system, all routers are equal in relation to each other. In a hierarchical routing system, some routers form what constitutes the backbone ( backbone- routing base. Packets from non-core routers travel to and through core routers until they reach the general area of ​​the destination. From this point on, they travel from the last core router through one or more non-core routers to their final destination.

Routing systems often establish logical groups of nodes called domains, or autonomous systems (AS), or areas. In hierarchical systems, some routers in a domain can communicate with routers in other domains, while other routers in that domain can communicate with routers only within their own domain. In very large networks, additional hierarchical levels may exist. Routers at the highest hierarchical level form the routing base.

The main advantage of hierarchical routing is that it mimics the organization of most companies and therefore supports their traffic patterns very well. Most network communication takes place within groups of small companies (domains). Intra-domain routers only need to know about other routers within their domain, so their routing algorithms can be simplified. Routing update traffic may be reduced accordingly, depending on the routing algorithm used.

Algorithms with intelligence in the main computer or router

Some routing algorithms assume that the final source node determines the entire route. This is usually called source routing. In source routing systems, routers simply act as storage and forwarding devices for the packet, forwarding it to the next stop without thinking.

Other algorithms assume that the main computers know nothing about the routes. When using these algorithms, routers determine the route through the interconnected network based on their own calculations. In the first system discussed above, the routing intelligence is located in the main computer. In the system considered in the second case, the routers are endowed with routing intelligence.

The trade-off between routing with intelligence in the host and routing with intelligence in the router is achieved by weighing the optimality of the route against the traffic overhead. Systems with intelligence in the main computer often choose the best routes, because they typically find all possible routes to the destination before the packet is actually sent. They then select the best route based on determining the optimality of that particular system. However, the act of determining all the routes often requires significant search traffic and a large amount of time.

Intra-domain or cross-domain algorithms

Some routing algorithms operate only within domains; others - both within domains and between them. The nature of these two types of algorithms is different. Therefore, it is clear that the optimal intra-domain routing algorithm will not necessarily be the optimal inter-domain routing algorithm.

Channel state or distance vector algorithms

Link state algorithms (also known as shortest path first algorithms) send routing information to all nodes in an interconnected network. However, each router sends only that part of the routing table that describes the state of its own links. Distance vector algorithms (also known as Bellman-Ford algorithms) require each router to send all or part of its routing table, but only to its neighbors. Link-state algorithms actually send small adjustments in all directions, while distance vector algorithms send larger adjustments only to neighboring routers.

With faster convergence, link state algorithms are somewhat less prone to routing loops than distance vector algorithms. On the other hand, link state algorithms have more complex calculations than distance vector algorithms, requiring more processing power and memory than distance vector algorithms. As a result, link state algorithms can be more expensive to implement and maintain. Despite their differences, both types of algorithms perform well under a wide variety of circumstances.

Algorithm indicators (metrics)

Routing tables contain information that switching programs use to select the best route. What characterizes the construction of routing tables? What is the nature of the information they contain? IN this section, dedicated to the performance of algorithms, an attempt is made to answer the question of how an algorithm determines the preference of one route over others.

Routing algorithms use many different metrics. Complex routing algorithms can be based on multiple indicators when selecting a route, combining them in such a way that the result is one separate (hybrid) indicator. The following are the metrics used in routing algorithms:

Route length

Reliability

Delay

Bandwidth

Communication cost

Route length

Route length is the most common routing metric. Some routing protocols allow network administrators to assign arbitrary prices to each network link. In this case, the path length is the sum of the costs associated with each channel that was traversed. Other routing protocols define the "number of hops", i.e. a metric that characterizes the number of passes a packet must make on its way from its source to its destination through networking products (such as routers).

Reliability

Reliability, in the context of routing algorithms, refers to the reliability of each link in the network (usually described in terms of bit-to-error ratio). Some network links may fail more often than others. Failures of some network links can be resolved more easily or quickly than failures of other links. When assigning reliability ratings, any reliability factors can be taken into account. Reliability ratings are typically assigned to network links by network administrators. As a rule, these are arbitrary digital values.

Delay

Routing delay is usually understood as the length of time required for a packet to travel from its source to its destination through an interconnected network. The delay depends on many factors, including the bandwidth of intermediate network channels, queues at the port of each router along the path of the packet, network congestion at all intermediate links of the network and the physical distance over which the packet must be moved.Because there is a conglomeration of several important variables, latency is the most common and useful indicator.

Bandwidth

Bandwidth refers to the available traffic capacity of any link. All other things being equal, a 10 Mbps Ethernet channel is preferable to any leased line with a bandwidth of 64 KB/sec. Although bandwidth is an estimate of the maximum achievable bandwidth channel, routes passing through higher-bandwidth links are not necessarily better than routes passing through slower links.

Mmenu"IP Interface Settings"

Traffic segmentation

Traffic segmentation serves to differentiate domains at layer 2. This feature allows you to configure ports so that they are isolated from each other, but at the same time have access to shared ports used to connect servers and the provider's network backbone. This function can be used when building provider networks.

An example of using the Traffic Segmentation function.

All computers (PC2 - PC24) have access to the uplink port, but do not have access to each other at the link level. This solution can be used:

1.In ETTH projects to isolate end user ports.

2.To provide access to a shared server

Exercise

1. Assemble the network topology shown in the figure

2. Study the sections “Addressing in IP networks”, “IP routing” and the “IP Interfase Settings” menu

3. Create IP subnets. Assign each PC an IP address from its own subnet

4. Study the “Traffic Segmentation” section and the “Traffic Segmentation” menu

5. Organize the “comb” principle on each of the DES-3010G switches - each computer connected to the switch can exchange information only with the outside world, but not with other computers connected to this switch.

6. Confirm that the settings you have made are correct.

Questions for self-control.

1. Types of addresses.

2. IP address levels.

3. Classes of IP addresses. Give examples.

4. Features of the ARP and RARP protocols.

5. DNS service

6. DHCP server functions.

7. Types of routing.

8. Routing Components

9. Route determination

10. Switching

11. Routing algorithms

12. Goals of developing routing algorithms

13. Types of algorithms

14. Algorithm indicators (metrics)

15. What settings can be configured using the “IP Interfase Settings” menu?

16. What is traffic segmentation used for? Let me show you with an example.

16. What settings can be organized using the “Traffic Segmentation” menu?

• Host is the end device that acts as a sender or receiver of data. But the final recipient should not be confused with intermediate devices that also receive data for further transportation.
• Network mask is a sequence of bits indicating the portion of the address that is the network address. The ones in the netmask must be consecutive and start with the most significant bit.
• Metric - route quality. A lower value is better.
• Administrative distance is the degree of trust in the route source. The concept is used by Cisco Systems.
• Internetwork - combining two or more networks with general principles routing The most striking example is the Internet.
• An autonomous system (AS) is a network under the control of a single operator, usually a provider together with its networks or a network of a large company. Each AS has a unique number.

Introduction

To read this article, you must have an understanding of the OSI network model. To do this, it is recommended that you read the article "OSI and TCP/IP Network Models".

Those of you who have been online for several days probably already know the concept of “default gateway”. Or maybe you’ve even heard about routes, which are often referred to in the jargon “routes” (from the English route). And for that matter, the more correct pronunciation of the word is “root” or “raut”. These concepts have become an integral part of our experience on the Internet. But the Internet plays a huge role in the modern world. What is he really like? The Internet is a global network. Its more primitive analogues can be found in any self-respecting large company that creates their own networks with many servers, and they, in turn, provide users with access to a variety of resources. In this way, a huge number of networks have been created.

As you know, a computer can only communicate with hosts from its network. For this, the ARP protocol is used, which converts a network address into a physical one. But what if our desired recipient is on the opposite side of the globe and on a different network? How do we find out his physical address and will our network frame reach him? So the routing process solves this problem.

Initial and superficial information

So what is routing? Routing is the process of choosing the route a packet should take. The device that makes this choice is called a router. Routers operate at Layer 3 of the OSI model. Using only the network address to select a route, discarding the host address. To extract a network address from an IP address, a network mask is used. But you won’t be satisfied with formal formulations alone. Therefore, we will look more deeply.

First, let's look at what a route is. A route is a direction. Although many are accustomed to imagining the entire path traveled by a packet at once, depicting it as a sequence of edges of a graph (representing the network logically), from the point of view of an individual router this is a little different. Each router can tell which interface or which next router to send the packet to, thus specifying the direction of movement. By collecting these directions in sequence, we get the entire route.

Routers decide on a route according to their routing table. This is a table containing the mapping of a network address to a route.

Thus, client machines send data to a recipient on another network through a router. It, in turn, looks at the address of the network in which the recipient is located, compares it with its routing table and decides on choosing a route for each packet or discards the packet. Here again there are moments that it is advisable to chew on.

First, how does the client machine send packets to the router and how does it understand that the packet is intended for routing? To do this, packets are sent with the physical address of the router (more precisely, at the second level they are intended for the router), but the network address of the recipient. Thus, the network frame is destined for the router, so it is received and decapsulated into a packet. But at the network level, the packet is not intended for him. At this stage, routing begins. As mentioned above, it takes place at the network level and does not go beyond it.

The next action that interests us is the process of comparing the network address. So, given the routing table, we need to choose the best route. There are two to three stages for this. First, the network address is compared for the greatest similarity. If there are several such routes, then the routes with the smallest administrative distance are selected. And finally, among the remaining ones, the route with the lowest metric is selected. Administrative distance is the degree of trust in a source. This concept is used by Cisco Systems and we will recall it when considering dynamic routing. Routers that have a single source of dynamic routes or perform only static routing compare only network addresses and metrics. By the way, every computer also has a routing table, and when you want to request a page from the Internet, the computer performs similar actions to select a route.

It may happen that there are several best routes in the routing table. In this case, there are no clear instructions on what to do. Cisco hardware routers perform load balancing among these routes by interleaving packets.

It is quite common to see that the destination network is not in the table, but there is a network covering it (in other words, it is a supernet). But if the network contains the range of addresses of the network we need, then the recipient is also located there. Using this principle, you can replace several subnets with one supernet, but only if they have the same routes. In this case, comparing the network address for the greatest similarity means that the best route will be considered the route whose network address has a greater bit match with the destination network address. How to use this can be seen using an example:

Let us have three routes on the network 10.0.1.0/24, 10.0.2.0/24 and 10.0.3.0/24. Moreover, the routes to the first and third networks are the same. In this case, you can reduce the number of routing table entries, thereby speeding up the process of finding the best route. To do this, we will combine the first and third routes, after which only two routes remain. Moreover, we can unite with any covering network, for example, 10.0.0.0/8. Routing will continue to work correctly, since for network 10.0.2.0/24 the route with the greatest match (more precisely complete) to the network address will be selected, and for the remaining addresses from 10.0.0.0/8 a generalized route will be selected. As you have already noticed, the router starts sending packets to non-existent networks (due to the 10.0.0.0/8 network) and although such packets will be thrown further, this will take up router resources, so it may be a bad approach. Aggregating routes is called prefix aggregation or route summarization.

There are only two types of routing: static and dynamic.

Static routing

With static routing, routes are manually entered by the administrator on each router and do not change during operation. Also sometimes static routing includes routes whose changes can be predicted. For example, changing routes according to schedule or day of the week.

Also worth mentioning are the output interfaces. When raising a network interface and setting up a protocol on it network layer, the route to the network in which this interface is located is automatically entered into the routing table. Such networks in which the router is located are called directly connected. And the routes on them are specified only by the output interface and are the highest priority. After all, why look for workarounds if we are already on this network and can directly send the packet to the recipient?

The remaining routes are specified by the address of the next router. Thus, the packet will pass through routers until it reaches one that has a directly connected destination network.

Dynamic routing

Dynamic routing is accomplished through dynamic routing protocols. With their help, the router builds and updates its routing table.

They say that a network has converged when any router can reach any network. Otherwise, network problems such as packet loss and routing loops may occur. Asymmetric routing is one in which there is a route in only one direction.

Dynamic routing protocols are divided into external and internal. And the internal ones, in turn, are based on distance vector protocols and link state protocols.

Internal protocols are used in networks of various sizes to automate and reliably the routing process. External protocols are used to work between autonomous systems, i.e. in very large networks such as the Internet.

The difference between distance vector protocols and link state protocols is quite significant. Link state protocols appeared later, when class networks became a thing of the past. Their main principle is to store the state of all network channels. They build a kind of network map and independently determine the best routes. Distinctive feature It is also possible to send updates only when the topology changes and only to those routers for which the information will be relevant.

Distance vector protocols require all routers to work correctly and together, as they operate on the direction and metric they receive from neighboring routers. Thus, having received a route, the router increments its metric and sends it to other neighbors. This is where the name of the protocols comes from: distance (metric) and vector (direction). Among the representatives is the EIGRP protocol, which has a number of advantages and some similarities with link state protocols.

Among the external routing protocols, we can note the BGP protocol, on which the Internet rests. It is a path state protocol. This means that it operates on the best paths, which are given by the list of autonomous systems (AS) through which the packet must pass. As a rule, the number of ASes in a path is not large, and the path that contains a smaller number of ASes is considered better. To ensure that some route is a backup route, they use cunning and repeat their AS number several times along the way, thereby increasing the length. When the packet reaches the desired AS, internal routing takes effect.

Multiple routing protocols can run simultaneously on a single router. They can also advertise the same networks. Let's imagine that there is a network in which each router is connected to all the others (this topology is called full mesh). This way we can get into the same network different ways. But let's run different routing protocols on such a network, for example RIP and EIGRP. Let us select for consideration a router on which both of these protocols run. The problem is that the metric in the RIP protocol can take a value from 1 to 15, while in EIGRP it takes on quite impressive values. If you check the metric, then networks advertised by the RIP protocol will be considered higher priority. It turns out that the metrics of different protocols cannot be compared. And as you know, EIGRP builds better routes, so some intermediate step in comparing routes is needed. Cisco uses the concept of administrative distance for this. Each protocol is assigned a unique value that determines the degree of trust, and the lower it is, the more preferable the protocol is. Therefore, before comparing metrics, we select only one protocol for each network. But the value of the administrative distance for the protocol can be changed on Cisco routers, but this change remains valid only within the router.

Conclusion

Routers are a key part of any internetwork network. We can conclude that there are two main tasks that routers solve:

1. Finding the best route
2. Sending a packet along this route

Routing made it possible to combine separate networks into one global network. Where every network member has access to all resources. We can talk about three principles of routing:

1. Each router makes its own decision. It does not specify where the information about the routes was obtained from.
2. If one router has a complete routing table, this does not mean that the others have it too. You can give many reasons and examples when the network does not converge. In some cases this can lead to data loss and in some cases it can lead to routing loops. This is why it is important to correctly and completely configure static routes on routers and/or correctly select and configure a dynamic routing protocol.
3. The existence of a one-way route does not guarantee the existence of a return route. In simple words, the packet may reach the recipient, but there may be no return path for the response packet. This is caused by the incompleteness of the routing table on some router along the way.

-----
Especially for the site
Copying material only with the permission of the author
(c) 2009 year

Or gateway, is a network node with several IP interfaces (containing its own MAC address and IP address) connected to different IP networks, which, based on solving the routing problem, redirects datagrams from one network to another for delivery from the sender to the recipient.

They are either specialized computing machines, or computers with several IP interfaces, the operation of which is controlled by special software.

Routing in IP networks

Routing is used to receive a packet from one device and forward it across the network to another device via other networks. If there are no routers on the network, then routing is not supported. Routers route (forward) traffic to all networks that make up the internetwork.

To route a packet, the router must have the following information:

• Destination address
• A nearby router from which it can learn about remote networks
• Available paths to all remote networks
• The best path to each remote network
• Methods for maintaining and checking routing information

The router learns about remote networks from neighboring routers or from network administrator. The router then builds a routing table that describes how to find remote networks.

If the network is connected directly to the router, it already knows how to route the packet to that network. If the network is not directly connected, the router must learn (learn) access paths to the remote network using static routing (the administrator manually enters the location of all networks into the routing table) or using dynamic routing.

Dynamic routing is a routing protocol process that determines how a device communicates with neighboring routers. The router will update information about each network it learns. If a change occurs in the network, the dynamic routing protocol automatically informs all routers of the change. If static routing is used, the system administrator will have to update the routing tables on all devices.

IP routing is a simple process that is the same on networks of any size. For example, the figure shows the process of step-by-step interaction between host A and host B on another network. In the example, the user of host A requests the IP address of host B by ping. Further operations are not so simple, so let’s look at them in more detail:

• At the command line, the user enters ping 172.16.20.2. On host A, a packet is generated using network layer protocols and ICMP.

• IP calls ARP to find out the destination network for the packet by looking at the IP address and subnet mask of host A. This is a request to the remote host, i.e. the packet is not destined for a host on the local network, so the packet must be forwarded to the router to be forwarded to the desired remote network.
• In order for host A to send a packet to the router, the host must know the hardware address of the router interface connected to the local network. The network layer passes the packet and hardware destination address to the data link layer to be framed and forwarded to the local host. To obtain a hardware address, the host looks up the location of the destination in its own memory, called the ARP cache.
• If the IP address has not yet been reached and is not present in the ARP cache, the host sends an ARP broadcast to look up the hardware address at IP address 172.16.10.1. This is why the first Ping request will usually time out, but the other four requests will succeed. Once an address is cached, there is usually no timeout.
• The router responds and reports the hardware address of the Ethernet interface connected to the local network. Now the host has all the information to forward the packet to the router over the local network. The network layer passes the packet down to generate an ICMP echo request (Ping) at the data link layer, appending the packet with the hardware address to which the host should send the packet. The packet has source and destination IP addresses along with an indication of the packet type (ICMP) in the network layer protocol field.
• The data link layer forms a frame that encapsulates the packet along with the control information necessary for forwarding over the local network. This information includes the source and destination hardware addresses, as well as the value in the type field set by the network layer protocol (this will be the type field since IP uses Ethernet_II frames by default). Figure 3 shows a frame generated at the link layer and forwarded over the local media. Figure 3 shows all the information needed to communicate with the router: source and destination hardware addresses, source and destination IP addresses, data, and check sum Frame CRC, located in the FCS (Frame Check Sequence) field.
• Host A's link layer transmits the frame physical level. There, zeros and ones are encoded into a digital signal and then transmitted over a local physical network.

• The signal reaches the router's Ethernet 0 interface, which is synchronized to the digital signal preamble to retrieve the frame. After constructing the frame, the router interface checks the CRC, and at the end of receiving the frame, compares the received value with the contents of the FCS field. In addition, it checks the transfer process for media fragmentation and conflicts.
• The destination hardware address is checked. Since it matches the router's address, the frame type field is analyzed to determine what to do next with this data packet. The type field specifies the IP protocol, so the router passes the packet to the IP protocol process running on the router. The frame is deleted. The original packet (generated by host A) is placed in the router's buffer.
• The IP protocol looks at the destination IP address in the packet to determine whether the packet is destined for the router itself. Since the destination IP address is 172.16.20.2, the router determines from its routing table that network 172.16.20.0 is directly connected to Ethernet interface 1.
• The router forwards the packet from the buffer to Ethernet interface 1. The router needs to frame it to forward the packet to the destination host. The router first checks its ARP cache to determine whether the hardware address has already been resolved during previous interactions with the given network. If the address is not in the ARP cache, the router sends an ARP broadcast request to Ethernet interface 1 to look up the hardware address for IP address 172.16.20.2.
• Host B responds with the hardware address of its network adapter to an ARP request. The router's Ethernet 1 interface now has everything it needs to forward the packet to its final destination. The figure shows a frame generated by the router and transmitted over the local physical network.

The frame generated by the router's Ethernet 1 interface has a source hardware address from Ethernet interface 1 and a destination hardware address for the host B network adapter. It is important to note that, despite changes in the source and destination hardware addresses, on each router interface that sent the packet, the IP addresses source and destination never change. The package is not modified in any way, but the frames are changed.

• Host B receives the frame and checks the CRC. If the check is successful, the frame is discarded and the packet is transferred to the IP protocol. It analyzes the destination IP address. Since the destination IP address is the same as the address set in Host B, the IP protocol examines the protocol field to determine the destination of the packet.
• Our packet contains an ICMP echo request, so Host B generates a new ICMP echo reply with a source IP address equal to Host B and a destination IP address equal to Host A. The process starts again, but in the opposite direction. However, the hardware addresses of all devices along the packet's path are already known, so all devices will be able to obtain the hardware addresses of the interfaces from their own ARP caches.

In large networks, the process is similar, but the packet will have to travel more hops on the way to the destination host.

Routing tables

In the TCP/IP stack, routers and end nodes make decisions about who to pass a packet to in order to successfully deliver it to the destination node, based on so-called routing tables.

The table is a typical example of a route table using network IP addresses for the network shown in the figure.

Routing table for Router 2

The table shows a multi-route routing table, since it contains two routes to network 116.0.0.0. In the case of constructing a single-route routing table, it is necessary to specify only one path to network 116.0.0.0 based on the lowest metric value.

As you can easily see, several routes with different parameters are defined in the table. You need to read each such entry in the routing table as follows:

To deliver a packet to the network with an address from the Network Address field and a mask from the Network Mask field, you need to send a packet from the interface with the IP address from the Interface field to the IP address from the Gateway Address field, and the “cost” of such delivery will be equal to the number from the field Metrics.

In this table, the "Destination Network Address" column indicates the addresses of all networks to which this router can transmit packets. The TCP/IP stack adopts the so-called one-hop approach to optimizing the packet forwarding route (next-hop routing) - each router and end node takes part in choosing only one packet transmission step. Therefore, each line of the routing table does not indicate the entire route as a sequence of IP addresses of the routers through which the packet must pass, but only one IP address - the address of the next router to which the packet must be transmitted. Along with the packet, responsibility for choosing is transferred to the next router next step routing The one-hop approach to routing means a distributed solution to the route selection problem. This removes the restriction on the maximum number of transit routers along the packet's path.

To forward a packet to the next router, knowledge of its local address is required, but in the TCP/IP stack it is common practice to use only IP addresses in routing tables to store them universal format, independent of the type of networks included in the Internet. To find a local address from a known IP address, you must use the ARP protocol.

One-hop routing has another advantage - it allows you to reduce the size of routing tables in end nodes and routers by using the so-called default route (0.0.0.0) as the destination network number, which usually occupies the routing table last line. If there is such an entry in the routing table, then all packets with network numbers that are not in the routing table are sent to the router specified in the default line. Therefore, routers often store in their tables limited information about internet networks by forwarding packets for other networks to the default port and router. The default router is assumed to forward the packet to the backbone, and routers connected to the backbone have full information about the composition of the Internet.

In addition to the default route, there may be two types of special entries in the routing table - an entry about a host-specific route and an entry about the addresses of networks directly connected to the router ports.

A host-specific route contains a full IP address instead of a network number, that is, an address that has non-zero information not only in the network number field, but also in the host number field. It is assumed that for such an end node the route should be chosen differently from all other nodes in the network to which it belongs. In the case when the table contains different records about the progress of packets for the entire network N and its individual node, which has address N,D, upon arrival of a packet addressed to node N,D, the router will give preference to the entry for N,D.

Entries in the routing table related to networks directly connected to the router contain zeros (“connected”) in the “Metrics” field.

Routing Algorithms

Basic requirements for routing algorithms:

• accuracy;
• simplicity;
• reliability;
• stability;
• justice;
• optimality.

There are various algorithms for constructing tables for one-hop routing. They can be divided into three classes:

• simple routing algorithms;
• fixed routing algorithms;
• adaptive routing algorithms.

Regardless of the algorithm used to build the routing table, the result of their work has a single format. Due to this, in the same network, different nodes can build routing tables according to their own algorithms, and then exchange missing data with each other, since the formats of these tables are fixed. Therefore, a router using an adaptive routing algorithm can provide an end node using a fixed routing algorithm with path information to a network that the end node knows nothing about.

Easy routing

This is a routing method that does not change when the topology and state of the data transmission network (DTN) changes.

Simple routing is provided by various algorithms, typical of which are the following:

• Random routing is the transmission of a message from a node in any randomly selected direction, with the exception of the directions in which the message was received by the node.
• Flooding routing is the transmission of a message from a node in all directions except the direction in which the message arrived at the node. This routing guarantees short packet delivery time, at the expense of throughput degradation.
• Routing based on previous experience - each packet has a counter for the number of nodes passed, in each communication node the counter is analyzed and the route that corresponds to the minimum value of the counter is remembered. This algorithm allows you to adapt to changes in network topology, but the adaptation process is slow and ineffective.

In general, simple routing does not provide directional packet transmission and has low efficiency. Its main advantage is to ensure stable operation of the network in the event of failure of various parts of the network.

Fixed Routing

This algorithm is used in networks with a simple connection topology and is based on the manual compilation of a routing table by the network administrator. The algorithm often works effectively also for backbones of large networks, since the backbone itself can have a simple structure with obvious the best ways The following algorithms distinguish packets in subnets connected to the backbone:

• Single-path fixed routing is when a single path is established between two subscribers. A network with such routing is unstable to failures and overloads.
• Multi-path fixed routing - several possible paths can be established and a path selection rule is introduced. The efficiency of such routing decreases as the load increases. If any communication line fails, it is necessary to change the routing table; for this, several tables are stored in each communication node.

Adaptive Routing

This is the main type of routing algorithms used by routers in modern networks with complex topologies. Adaptive routing is based on the fact that routers periodically exchange special topological information about the networks available on the Internet, as well as about the connections between routers. Usually, not only the topology of links is taken into account, but also their capacity and condition.

Adaptive protocols allow all routers to collect information about the topology of connections in the network, quickly processing all changes in the connection configuration. These protocols are distributed in nature, which is expressed in the fact that there are no dedicated routers in the network that would collect and summarize topological information: this work is distributed among all routers, the following algorithms are distinguished:

• Local adaptive routing - each node contains information about the link state, queue length and routing table.
• Global adaptive routing is based on the use of information received from neighboring nodes. To do this, each node contains a routing table, which indicates the transit time of messages. Based on information received from neighboring nodes, the table value is recalculated taking into account the queue length in the node itself.
• Centralized adaptive routing - there is some central node that collects information about the state of the network. This center generates control packets containing routing tables and sends them to communication nodes.
• Hybrid adaptive routing is based on the use of a table periodically sent by the center and on analyzing the queue length from the node itself.

Algorithm indicators (metrics)

Routing tables contain information that switching programs use to select the best route. What characterizes the construction of routing tables? What is the nature of the information they contain? This section on algorithm metrics attempts to answer the question of how an algorithm determines whether one route is preferable to another.

Routing algorithms use many different metrics. Complex routing algorithms can rely on multiple metrics when selecting a route, combining them in such a way that the result is one hybrid metric. The following are the metrics used in routing algorithms:

• Route length.
• Reliability.
• Delay.
• Bandwidth.

Route length.

Route length is the most common routing metric. Some routing protocols allow network administrators to assign arbitrary prices to each network link. In this case, the path length is the sum of the costs associated with each channel that was traversed. Other routing protocols define a "hop count," a metric that describes the number of trips a packet must make on its way from its source to its destination through network aggregation elements (such as routers).

Reliability.

Reliability, in the context of routing algorithms, refers to the reliability of each link in the network (usually described in terms of bit-to-error ratio). Some network links may fail more often than others. Failures of some network links can be resolved more easily or quickly than failures of other links. When assigning reliability ratings, any reliability factors can be taken into account. Reliability ratings are typically assigned to network channels by administrators. As a rule, these are arbitrary digital values.

Delay.

Routing latency typically refers to the length of time it takes for a packet to travel from its source to its destination across an internetwork. Latency depends on many factors, including the bandwidth of the intermediate links in the network, the queues at the port of each router along the packet's path, network congestion on all intermediate links in the network, and the physical distance over which the packet must travel. Because there is a conglomeration of several important variables, latency is the most common and useful metric.

Bandwidth.

Bandwidth refers to the available traffic capacity of any link. All other things being equal, a 10 Mbps Ethernet channel is preferable to any leased line with a 64 KB/s bandwidth. Although bandwidth is an estimate of the maximum achievable capacity of a link, routes passing through higher-bandwidth links are not necessarily better than routes passing through slower links.