Routing Protocol

After having the IP Address and the design of the routing table, we must continue to consider how to obtain routing information, that is, how to exchange information between routers, such as how to express their reachability to other routers, after obtaining routing information, we still need to find a way to construct the routing table.

Internet control message network packet protocol ICMP

In order to efficiently forward IP data packets and improve the chances of successful delivery, the Internet control message network packet protocol is used at the Internet layer, but ICMP is not a higher layer protocol (it appears to be a higher layer protocol because ICMP is enclosed in IP datagrams as part of the data), and its format is as follows:

ICMP message network packet is divided into two types, ** ICMP error report message network packet ** and ** ICMP query message network packet **, the format of the first four bytes of the ICMP message network packet is unified, a total of three fields, respectively, the type, code, and test, the content of the next 4 bytes related to the ICMP type, and finally the data field, the length depends on the type of ICMP.

Common ICMP message network packet types are:

ICMP message network packet type	Value of type	Type of ICMP message network packet
Error report message network packet	3	destination unreachable
	11	Time exceeds
	12	Parameter problem
	5	Change the route
Inquiry message network packet	8 or 0	Request or answer
	13 or 14	timestamp request or answer

ICMP message network packet code field is to further distinguish a certain type of several different cases, and the test field is used to test the entire ICMP message network packet, because the IP datagram header test and does not test the content of the IP data packet.

Error message network packet

There are four types of error message network packets in the above table:

• End unreachable: When a router or host cannot deliver a datagram, it sends an end unreachable message network packet to the source.
• Time Out: When the router receives a datagram with a time-to-live of 0, it discards the datagram and sends a message network packet to the far point for longer than the time. At the same time, when the midpoint cannot receive all the datagrams of a datagram at a predetermined time, it discards all the received datagrams and sends a message network packet to the source for longer than the time.
• Parameter problem: When the host or router receives a datagram with incorrect fields in the header, it will discard the datagram and send the parameter problem message network packet to the source.
• Retargeting: The router sends a message network packet that changes the route to the host, letting the host know that the defective datagram is sent to another router.

When the host first starts working, it usually sets the IP Address of a default router in the routing table. Regardless of the destination address to which the datagram is to be sent, the datagram will be sent to the default router first. If the default router finds that the best route for a datagram sent by the host to a destination address should go through another router on the current network, it tells the host about this by changing the route message network packet.

The data fields in all ICMP error report packets have the same style. The header and the first 8 bytes of the data field of the received IP data packet that need to be error reported are extracted. The data fields of the datagram, together with the first 8 bytes of the ICMP error report message network packet, constitute the ICMP error report message network packet. The first 8 fields of the IP datagram that need to be error reported are extracted in order to obtain Port Number of the transport layer

The following situations should not send ICMP error report message network packets:

• For ICMP error report message network packets, no longer send ICMP error report message network packets.
• For all subsequent datagram sheets of the first sharding datagram sheet, no ICMP error report message network packet is sent.
  For data packets with multicast addresses, error message network packets are not sent.
  For special addresses (such as 127.0.0.1), no error message network packets are sent.

Interrogation message network packet

There are two commonly used query message network packets:

• Echo Request and Answer: ICMP Echo Request message network packet is an inquiry sent by the host or router to a specific destination host. The host that receives this message network packet must send an ICMP Echo Answer message network packet to the source host or router. This inquiry message network packet is used to test whether the destination station is reachable and its related status.
• Timestamp Request and Answer: Request a host to answer its current date and time.

Application examples

PING

The PING command actually uses ICMP to send back request and answer message network packets.

Traceroute

Traceroute is actually a series of IP datagrams sent by the source host to the destination host. The datagrams encapsulate UDP datagrams that cannot be delivered. The TTL of the first datagram P1 is set to 1. When P1 arrives on the path When the first router R1, R1 subtracts it, and then subtracts the TTL by 1. Since the TTL is equal to 0, R1 discards P1 and sends a ** ICMP time exceeds the ** error message network packet to the source host.

Next, the nth datagram Pn is sent, the TTL is set to n, and finally a datagram reaches the destination host. Since it is an undeliverable UDP datagram, the destination host sends the ** ICMP endpoint unreachable error message network to the source host packet **.

Routing protocol

Ideal routing algorithm

The core of the routing protocol is the routing algorithm, that is, what algorithm is needed to obtain each item in the routing table.

An ideal routing algorithm should have:

• The algorithm must be ** correct and complete **. Here “correct” means that through the path indicated by each routing table, the packet must eventually reach the destination network and destination host.
• The algorithm must be computationally simple. It must not add too much overhead to network communication.
• The algorithm should be able to adapt to changes in traffic and network topology, that is, to have the ability to self-adapt.
  The algorithm should be stable. When the network traffic and network topology are relatively stable, the algorithm should converge to an acceptable solution.
• The algorithm should be ** fair **. The routing algorithm should be equal for all portals.
• The algorithm should be the best. The so-called best is just a reasonable choice relative to a specific requirement.

Hierarchical routing protocol

If the routing algorithm can be adjusted with the network traffic or topology Self-Adaptation to divide, can be divided into two categories, respectively, static routing policy and dynamic routing policy.

Static routing strategy, also known as non-Self-Adaptation routing, is characterized by simplicity and small overhead, but it cannot adapt to changes in network state in time. For very simple small networks, we can use static routing.

The routing protocols used by the Internet are mainly dynamic and distributed.

• The Internet is so large that if all routers knew how all networks should arrive, the routing table would be very large and the routing processing time would be very long.
• Many units do not want the outside world to know the layout details of their own unit network and the routing protocols used by the department.

To this end, we can divide the Internet into many small autonomous systems (AS) **, AS refers to a group of routers under the management of a single technology **, one AS to another AS shows a single and consistent routing policy.

A large ISP is a large autonomous system, and the Internet divides routing protocols into two categories:

• ** Internal Gateway Protocol IGP **, the routing protocol used within an autonomous system, which has nothing to do with what routing protocol other autonomous systems choose on the Internet.
• ** External Gateway Protocol EGP **, when the source host and destination host are not in the same autonomous system, if a datagram is transmitted to the autonomous system boundary, a protocol is required to transmit routing information to another autonomous system in the system.

Internal Gateway Protocol RIP

RIP is a distributed distance vector-based routing protocol, the standard protocol of the Internet, which requires each router in the network to maintain a distance record from itself to every other destination network.

RIP defines ** “distance” ** as follows:

The distance from a router to a directly connected network is defined as 1, and the distance from a router to a non-directly connected network is defined as the number of routers that have not passed plus 1.

The distance of the RIP protocol also became the “number of hops”, because every time it passed through a router, the number of hops was increased by one. RIP believed that the best Lu You was that it passed through a small number of routers, which meant that the distance was short. RIP allowed a path to contain up to 15 routers, so when the distance was equal to 16, it was equivalent to unreachable. It can be seen that RIP is only suitable for small networks.

RIP can no longer use multiple routes between two networks at the same time. ** RIP chooses a route with the fewest routers, even if there is a route with high speed and low latency but more routers **

The ** characteristics ** of the RIP protocol are as follows:

• Only exchange information with neighboring routers.
  The information exchanged by the router is all the information that the current router knows, that is, its current routing table.
• Exchange routing information at a fixed time.

When a router starts working, its routing table is empty, and then the router can only find that the distance between itself and several neighboring networks is 1. Each router can only exchange and update routing information with a limited number of neighboring routers, but after several exchanges, all routers will eventually know the shortest distance to any network in the autonomous system and the address of the next hop router. This process is called “convergence”.

The most important information in the routing table of the RIP protocol is the distance to a network and the next hop address.

Distance vector algorithm:

1. For RIP message network packets sent by neighboring routers with address X, first modify all items in this message, change the addresses in the next hop address field to X, and add 1 to all distance fields. Each item has three key data: to the destination network N, the distance is d, and the next hop routing address is X.
2. For each item in the modified RIP message, perform the following steps:
   • If there is no destination network N in the original routing table, add the item to the routing table.
   • If there is destination network N in the routing table, check the next hop routing address. If the next hop routing address is X, replace the received item with the original item. If the next hop address is not X, check whether the d in the received item is less than the distance in the routing table. If it is small, update it, otherwise do nothing.
     If the updated routing table of the neighboring router is not received within three minutes, mark the neighboring router as unreachable.

Internal Gateway Protocol OSPF

** Development of shortest route first OSPF (Open Shortest Path First) ** is to overcome the shortcomings of RIP and open out. “Open” indicates that the OSPF protocol is not controlled by a single manufacturer, “shortest path first” is because of the use of the shortest path algorithm SPF proposed by Dijkstra.

The most important feature of the OSPF protocol is the use of a distributed ** link state protocol (link state protocol) **, rather than RIP distance vector, compared with RIP, OSPF ** three characteristics ** and RIP are not the same:

• Send information to all routers of the autonomous system. The method used here is the flooding method, that is, the router sends information to all output ports to all neighboring routers, and each neighboring router sends this information to all its neighboring routers (no longer to the router that just sent the information).
• The ** information sent is the link state ** of this router and all neighboring routers, but this is part of the information that only the router knows. The so-called “link state” is to indicate which routers this router is adjacent to, and the “measure” of the link. OSPF uses this metric to represent cost, distance, delay, bandwidth, etc., as determined by network administrators.
  Only when the link state changes, the router wants all routers to send information using flooding method.

Due to the frequent exchange of information between routers, all routers will eventually establish a link state database, which is actually a topology diagram of the entire network.

OSPF divides an autonomous system into several smaller areas, called areas, each with a 32-bit area identifier.

The advantage of zoning is that the range of link state information exchanged by flooding is limited to each area rather than the entire autonomous system. OSPF uses hierarchical zoning. The upper-level area is called the backbone area. The identifier of the backbone area is 0.0.0.0 by default. The role of the backbone area is to communicate with other lower-level areas. Information from other areas is summarized by the area boundary router.

External Gateway Protocol BGP

First of all, it is necessary to clarify why the internal gateway protocol discussed earlier cannot be used between different autonomous systems. There are two main reasons for this:

• The Internet is too large, and it is very difficult to route between autonomous system ASs. A router connected to the Internet backbone must find a matching destination network in the routing table for any valid IP Address. At present, on the Internet backbone router, a routing table item has long found the network prefix of 5w., it takes too long to calculate the path using OSPF. And because of the different internal protocols of each AS, it is unlikely to calculate a meaningful path cost when a path passes through multiple AS.
• Routing between AS must take into account relevant strategies, including political and economic factors, such as our domestic sites can not go in circles abroad when transmitting datagrams to each other.

BGP can only strive to find a better route to the destination network, ** not to find an optimal route **. BGP adopts the path vector routing protocol. When configuring BGP, the administrator of each autonomous system must select at least one router as the ** “BGP spokesperson” ** of the autonomous system. The BGP spokesperson is often the boundary router of BGP.

When a BGP spokesperson exchanges information with other AS BGP speakers, it is necessary to establish a TCP connection (port: 179), and then establish a BGP session on this connection…

Each BGP spokesperson must run the internal gateway protocol of the AS in addition to the BGP.

The network reachability information exchanged by BGP is a series of autonomous systems that must be passed through to reach a certain network. After the BGP spokesperson exchanges the network reachability, each BGP spokesperson finds a better route to each AS from the received routing information according to the adopted strategy.