Routing protocols (RIP, OSPF and BGP). Online networks and communication systems

Border Gateway Protocol (BGP) version 4 is the primary protocol for exchanging routing information between autonomous systems on the Internet today. BGP replaces EGP1, which was used in the early days when the Internet had a single backbone. This highway was a central autonomous system, to which all other autonomous systems were connected in accordance with a tree topology. Since loops between autonomous systems were eliminated with this structure, EGP did not take any measures to eliminate route loops.

Let's explain the basic principles of BGP using an example (Fig. 1).

Rice. 1 Finding a route between autonomous systems using BGP

Each of the three autonomous systems (AS 1021, AS 363 and AS 520) has several routers that act as external gateways. Each of them runs the BGP protocol, with which they communicate with each other.

A router communicates with other routers using BGP only if the administrator explicitly specifies during configuration that these routers are its neighbors. For example, router EG1 in this example will communicate via BGP with router EG2 not because these routers are connected by a point-to-point link, but because when router EG1 was configured as a neighbor, router EG2 (with the address 194.200.30.2) was specified to it. Similarly, when configuring router EG2, router EG1 (with the address 194.200.30.1) was assigned as its neighbor.

This method of interaction is convenient in a situation where the routers exchanging routing information belong to different service providers (ISPs). The ISP administrator can decide which autonomous systems it will exchange traffic with and which it will not by defining a list of neighbors for its external gateways. The RIP and QSPF protocols, designed for use within an autonomous system, exchange routing information with all routers within their immediate reach (via a local network or a point-to-point link). This means that information about all networks appears in each router's routing table, so that every network is reachable by everyone. This is a normal situation in a corporate network, but not in ISP networks, which is why the BGP protocol plays a special role here.

BGP routers use TCP (port 179) to establish a session with specified neighbors. When establishing a BGP session, a variety of router authentication methods can be used to increase the security of autonomous systems.

The basic message of BGP is the UPDATE message, which is used by a router to inform a neighboring autonomous system router that networks belonging to its own autonomous system are reachable. The very name of this message suggests that it is a trigger announcement that is sent to a neighbor only when something changes dramatically in the autonomous system: new networks or new paths to networks appear, or, on the contrary, existing networks or paths disappear.

A single UPDATE message can announce one new route or invalidate multiple routes that no longer exist. In BGP, a route is a sequence of autonomous systems that must be passed on the way to the network specified in the address. More formally, information about the route (BGP Route) to the network (Network/Maskjength) looks like this:
BGP Route = AS_Path; NextHop; Network/Maskjength;
Here AS_Palh is a set of autonomous system numbers, NextHop is the IP address of the router through which packets need to be transmitted to the Network/Maskjength network. For example, if router EG1 wants to announce to router EG2 that a new network 202.100.5.0/24 has appeared in AS 1021, then it generates the following message:

AS 1021; 194.200.30.1; 202.100.5.0/24,
after which it passes it to router EG2 of AS 363 (with which it, of course, must have a BGP session established).

Router EG2, having received the UPDATE message, stores information about the 202.100.5.0/24 network in its routing table along with the address of the next router 194.200.30.1 and a note that this information was received via the BGP protocol. Router EG2 exchanges routing information with the internal gateways of the AS 363 system using some IGP protocol, such as OSPF. If EG2 is set to redistribute BGP routes to OSPF routes, then all internal AS 363 gateways will know the existence of the 202.100.5.0/24 network through an OSPF advertisement that will be external. Router EG2 will now start advertising the address of its own internal interface as the next router address, for example 192.17.100.2.

However, OSPF cannot be used to propagate the 202.100.5.0/24 network message to other autonomous systems, such as AS 520. Router EG3 associated with router EG4 of autonomous system 520 must use BGP, generating an UPDATE message in the required format. To solve this problem, it cannot use information about the 202.100.5.0/24 network received from the OSPF protocol through one of its internal interfaces, since it has a different format and does not contain, for example, information about the number of the autonomous system in which this network is located. net.
The problem is solved by having routers EG2 and EG3 also establish a BGP session with each other, even though they belong to the same autonomous system. This implementation of the BGP protocol is called internal (Interior BGP, iBGP), in contrast to the main, external one (Exterior BGP, eBGP). As a result, router EG3 receives the necessary information from router EG2 and transmits it to its external neighbor, router EG4. When generating a new UPDATE message, router EG3 transforms the message received from router EG2, adding its own autonomous system AS 520 to the list of autonomous systems, and replaces the received address of the next router with the address of its own interface:

AS 363, AS 1021; 132.15.64.3; 202.100.5.0/24.

Autonomous system numbers eliminate looping of UPDATE messages. For example, when router EG5 sends a message about network 202.100.5.0/24 to router EG6, the latter will not use it, since it will look like:
AS 520, AS 363, AS 1021; 201.14.110.3; 202.100.5.0/24.

Since the list of autonomous systems already contains the number of its own autonomous system, it is obvious that the message is in a loop.

The BGP protocol is used today not only to exchange routing information between autonomous systems, but also within them.

Today's article will focus on the main dynamic routing protocol - BGP (Border Gateway Protocol). Why the main one? – Because it is with the help of BGP that the topology of the entire Internet is organized.

So, in this article we will look at the following points:

Basic BGP Terms
How BGP works
BGP Message Types

Terminology

When it comes to BGP, the first thing to consider is the concept of an autonomous system. AS(Autonomus System). An autonomous system is a collection of routing points and connections between them, united by a common communication policy that allows this system to exchange data with nodes located outside its boundaries.

An AS is characterized by a (more recently 32-bit) ASN number (Autonomus System Number) and a pool of IP addresses. The IANA (Internet Assigned Numbers Authority) organization is responsible for issuing both, delegating control over the distribution of ASN and other Internet resources to regional registrars.

The connectivity of autonomous systems is achieved thanks to static or dynamic routing.

With static routing everything is simple. You log into the device and manually specify a route to its nearest neighbor. In practice, connecting even 10 routers with each other seems to be quite a difficult task.

Therefore, for large networks, they came up with dynamic routing, in which devices automatically share information with each other about the routes they have and, moreover, adapt to changes in the topology.

As you know, dynamic routing protocols are classified according to two main criteria:

Type of protocol operation relative to AS

IGP (Interior Gateway Protocol) – work within an autonomous system. These include: RIP, OSPF, EIGRP, IS-IS
EGP (Exterior Gateway Protocol) - work outside of autonomous systems and ensure their connectivity. This includes BGP

Protocol operation algorithm

Distance-Vector - knows routes only to its nearest neighbors and exchanges the routing table with them. (RIP, EIGRP)
Link State – knows the entire network topology and exchanges the topology table with its neighbors (OSPF, IS-IS)

Obviously BGP cannot be a Link State protocol. Just imagine how many autonomous systems there are on the Internet; any router will simply fail if it receives so much information.

So, BGP is an external routing protocol used to connect two ASes. The diagram looks something like this:

Since BGP has the great task of connecting autonomous systems throughout the Internet, it must be very reliable. For these purposes, at the very beginning of its operation, the BGP router initiates the establishment of a TCP session on port 179 to its neighbor, and standard SYN and ACK exchanges occur.

BGP connections must be absolutely negotiated by the autonomous system administrators wishing to establish the connection. If, say, the AS402 administrator launched a BGP process on the BR2 router (Border Router), specifying BR1 and its ASN as a neighbor, and the AS401 administrator did not take any action, then the TCP session will not rise and the systems will remain disconnected. In addition, the following conditions must be met:

Port 179 is not blocked by ACL (Access Control List)
Routers ping each other
When starting a BGP process, the ASN of the remote side was specified correctly
RouterIDs do not match

If the TCP session is established successfully, then the BGP routers begin exchanging

OPEN messages, in which they report their ASN, RouterID and Hold timer. Hold timer is the time during which the TCP session will be maintained. If the conditions listed earlier are not met, for example, the information about the AS number does not match, then the message NOTIFICATION a router that receives an incorrect ASN will notify its neighbor and reset the TCP session.

If all conditions are met, then the routers, at a certain interval, begin to send messages to each other KEEPALIVE, meaning confirmation of the parameters adopted in OPEN and the “I’m still alive” notification.

Finally, routers can begin exchanging routing information via message UPDATE. The structure of this message is divided into two parts:

Path Attributes. This indicates which AS the route came from, its origin and the Next Hop for this path.
NRLI (Network Layer Reachability Information). This indicates information directly about the networks to be added to the routing table, i.e. the IP address of the network and its mask.

The UPDATE message will be sent every time one of the routers receives information about new networks, and the KEEPALIVE message will be sent throughout the entire TCP session.

This is exactly how routing works throughout the Internet. History knows many incidents when the incorrect operation of the BGP protocol led to failures of large parts of the global network, so its importance cannot be underestimated.

Was this article useful to you?

Please tell me why?

We are sorry that the article was not useful for you: (Please, if it is not difficult, indicate why? We will be very grateful for a detailed answer. Thank you for helping us become better!

A router is usually assigned to multiple networks. When he receives a packet, he must solve two problems:

to which network it should transfer it;
which way?

The last decision is based on choosing the optimal path. Which available path is the optimal path? This is usually determined by a metric. Metrics is the conditional cost of transmission over the network. The total measurement of a particular route is equal to the sum of the metrics of the networks that include the route. The router chooses the route with the lowest metric. The metric is assigned to a network interface depending on the protocol type. Some simple protocols, like the Routing Information Protocol (RIP), treat all networks as the same. Then the cost of passing through each network is the same, and sections are counted to determine the metric. So, if a packet passes through 10 networks to reach its final destination, the total cost is 10 hops.

Other protocols, such as Open Shortest Path First (OSPF), allow the administrator to assign a cost to the network based on the type of service required. A route through a network can have a different cost (metric). For example, if a service type requires maximum performance, the satellite channel has a smaller metric than the optical line. On the other hand, if minimal latency is desired by the server type, the optical link has a lower metric than the satellite link. OSPF allows each router to have a table of route sequences based on the type of service required.

Other protocols define the metric differently. In the Border Gateway Protocol (BGP), a criterion is a policy that can be set by an administrator. Policy is the principle by which the path is determined.

In any metric, a router must have routing tables to consult when forwarding a packet. The routing table specifies the optimal path for a packet. A table can be either static or dynamic. Static table- one of those that often does not change. Dynamic table- one of those that updates automatically when there are changes anywhere on the Internet. Today the Internet needs dynamic tables. Tables need to be updated as changes occur on the Internet. For example, they need to be updated when a route fails, or they need to be updated whenever a better route is created.

Routing protocols are designed to map the requirements of tables dynamic routing. Routing protocol- a combination of rules and procedures that allow routers on the Internet to inform each other about changes. Routing protocols also include procedures for combining information received from other routers.

In this lecture we will talk about unidirectional routing protocols. We will discuss multidirectional routing protocols in the next lecture.

Internal and external routing

Today the Internet is a huge network, so one routing protocol cannot handle the task of updating all router tables. For this reason, the Internet is divided into autonomous systems. Autonomous System (AS)- a group of networks and routers under the control of one administrator. Routing within an autonomous system is classified as internal routing. Routing between autonomous systems is classified as external routing. Each autonomous system can choose an internal routing protocol in order to handle routing within the autonomous system. However, only one is selected to handle routing between autonomous systems. routing protocol.

Several internal and external protocols have been developed. In this lecture we will touch only on the most popular of them - the internal protocols RIP and OSPF and one external protocol BGP. RIP and OSPF are used to update routing tables within an autonomous system. BGP is used to update routing tables for routers that connect autonomous systems together.

Routing Information Protocol (RIP)

Routing Information Protocol (RIP – Routing Information Protocol) - internal routing protocol, used within an autonomous system. This is a very simple protocol based on the use of a distance routing vector. In this section, we will first look at the principle of distance vector routing as it applies to RIP, and then discuss the RIP protocol itself.

Routing distance vector

Using routing distance vector,Each router periodically shares its Internet login ,information with its neighbors. Below are three basic principles of this process to help you understand how the algorithm works.

Distribution of autonomous system login information. Each router distributes entry information to neighboring autonomous systems. This information may not be detailed at first. However, the volume and quality of information do not matter. The router sends, in any case, everything it has.
Distribution to neighbors only. Each router sends its information only to its neighbors. It sends the information it receives through all interfaces.
Distribution at regular intervals. Each router sends its information to its neighboring autonomous system at fixed intervals, such as every 30 seconds.

BGP is an external gateway routing protocol used to conduct routing between routing domains (or autonomous systems). BGP is used by all Internet service providers, as well as at the core of very large networks.

BGP is a very stable and highly scalable routing protocol. BGP exhibits exceptional stability in inter-autonomous system (AS) routing (even with large routing tables) and provides network administrators with greater latitude and flexibility in creating routing rules.

The operating principle of the distance vector routing protocol:

The BGP protocol is a route vector protocol i.e. applies vector (direction) and path information to the destination.

An example of how a distance vector routing protocol works

Suppose that Router A generated a route to network 10.1.10/2A and advertised it to Router B. In the information about how to reach the destination network 10.1.10/2A, Router A indicates that it is the first router in the path. Router B, having received this route, adds itself to the path and sends it to Router C, which in turn adds itself to the path to network 10.1.10/2A and sends the route to Router D. When Router D receives the route to destination 10.1. 10/2A, it discovers that the path to it passes through routers C, B, and A. Router D adds itself to the path and sends the resulting route back to Router A. Having received the route advertisement, Router A rejects it because it finds it in corresponding to the path of oneself.

This is how BGP works, except that the information is added to the path to the destination network not by individual routers, but by autonomous systems. Any router that has received a route can determine the presence of a routing loop by checking for the presence of its own autonomous system along the path to a given network.

The BGP protocol does not impose any requirements on the network topology.

The BGP protocol, based on information received from various routers, builds a graph of autonomous systems with all connections between nodes. Each AS has a unique number. A connection between two ASs forms a path, and information about the collection of paths from one node in an AS to a node in another AS constitutes a route. BGP actively uses information about routes to a given destination, which avoids routing loops between domains.

Choosing a path.BGP does not use metrics to detect loops in a path; it needs them to manage network rules.

The BGP protocol advertises only one optimal route to all its neighbors. Below is a list of metrics, ordered by increasing importance:

· Administrative weight;

· Local preference;

· Locally created routes;

· Shortest AS path;

· Lowest source;

· Metric MED (Multiple Exit Discriminator);

· Preferred external paths;

· Path through the nearest neighbor, if synchronization is enabled;

· Path through the neighbor with the lowest router ID;

The route with the shortest AS path is selected when all the more significant factors coincide.

The BGP protocol is designed to exchange information about the reachability of subnets between autonomous systems (AS), that is, groups of routers under a single technical control that use the intra-domain routing protocol to determine routes within themselves and the inter-domain routing protocol to determine routes for delivering packets to other ASs. The transmitted information includes a list of speakers that can be accessed through this system. The best routes are selected based on the rules adopted in the network.

BGP supports classless addressing and uses route summarization to reduce routing tables. The fourth version of the protocol has been in effect since this year; all previous versions are outdated.

BGP, along with DNS, is one of the main mechanisms that ensure the functioning of the Internet.

BGP is an application layer protocol and operates on top of the transport layer protocol TCP (port 179). Once the connection is established, information about all routes intended for export is transmitted. In the future, only information about changes in routing tables is transmitted. When a connection is closed, all routes about which information was transmitted by the opposite side are deleted.

Message Format

A BGP message begins with a header, which may be followed by data, depending on the type of message. The maximum message length is 4096 octets, the minimum is 19 octets. The message header contains the following fields:

Marker (16 octets) - used for compatibility, must be filled with ones;
Length (2 octets) - message length in octets, including header;
Type (1 octet):
- 1 - Opening;
- 2 - Information update;
- 3 - Alert;
- 4 - Saving the connection.

Opening

The first message after establishing a connection should be “Opening”. If the message is successfully processed, a “Connection Save” will be sent in response. In addition to the BGP header, the Open message contains the following fields:

Version (1 octet) - protocol version, current value 4;
My system (2 octets) - autonomous system number;
Time interval (2 octets) - the maximum time interval in seconds between receiving “Update information” or “Save connection” messages;
Sender ID (4 octets) - set equal to the IP address;
Length of additional parameters (1 octet);
Extra options:
- Parameter type (1 octet);
- Parameter length (1 octet);
- Parameter value.

Update information

The “Information Update” message is intended to transmit information about routes between speakers. The message can indicate new routes and remove broken ones. Message structure:

Length of deleted routes (2 octets);
Routes to be deleted:
- Length (1 octet) - length in bits of the IP address prefix;
- An IP address prefix, padded with a minimum number of bits to a complete octet;
Path attribute length (2 octets);
Path attributes:
- Attribute type:
  - Attribute flag;
  - Attribute code;
- Attribute length (1 or 2 octets, depending on the flag);
- Attribute data;
Reachability information - list of IP address prefixes:
- Length (1 octet) - length in bits of the IP address prefix (zero length - matches all IP addresses);
- An IP address prefix, padded with a minimum number of bits to form a complete octet.

All path attributes match all entries in the Reachability Information field.

Saving the connection

A connection save message must be sent at least once every one-third of the maximum time interval between messages, but not more than once per second. If the time interval is set to zero, then the message should not be sent periodically. The message does not use any additional fields.

Alert

An alert is sent if an error is detected and the connection is closed. The message contains the following fields:

Error code (1 octet);
Subcode (1 octet);
Data.

Selection process

The selection process starts after the information is updated and serves to select routes for use locally and for transmission to other routers using BGP. The process uses the attributes of the received routes to obtain the degree of preference for a route, or information that a route is not suitable for entry into the route database and should be excluded from the selection process. The process is divided into three phases:

Calculation of the degree of preference for each received route;
Selecting the best route for each destination and entering it into the route database;
Transferring routes to other routers, and summarizing routes can be performed.

Literature

Installing and configuring BGP using Quagga routing software on Gentoo Linux
Setting up BGP on Linux (Quagga Zebra) with automatic load balancing across three channels and redundancy
William R. Parkhurst Reference to commands and configuration of the BGP-4 protocol for Cisco routers = Cisco BGP-4 Command and Configuration. - M.: “Williams”, 2002. - P. 384. - ISBN 1-58705-017-X
BGP protocol (translation into Russian) = CISCO UNIVER CD.