It’s a complete copy. It’s very well written. This article to CSDN blogger “where that accompany a carp” original articles, follow BY CC 4.0 – SA the copyright agreement, the original links: blog.csdn.net/s2603898260…

Some common network devices (such as switches and routers) maintain some entries to implement route addressing and fast forwarding. The important entries are as follows:

  • The routing table
  • Turn published
  • The Mac table
  • ARP table

This article gives a detailed introduction to the four key entries in the network.

directory

  • Routing Table Forwarding Table

  • Media Access Control Table

    • Address learning thread
    • Packet forwarding thread

  • Address Resolution Table

  • summary

Routing Table Forwarding Table

In the computer network, the main work of the router is to find an optimal transmission path for each packet passing through the router and effectively transmit the data to the destination site. In order to select the best transmission path from many paths, the router saves the topology information of the surrounding network and various path parameters, which is called the routing table. A routing table, or RIB, is a spreadsheet (file) or class database stored in a router or networked computer. A routing table stores a path to a particular network address (and in some cases, a routing metric for that path). The main goal of routing table establishment is to realize routing protocol and static route selection.

In each router device, two similar tables are usually maintained, respectively:

Routing Information Base, abbreviated as RIB table, Forwarding Information Base, abbreviated as FIB table, RIB table is used to make Routing decisions. A forwarding table is used to forward packets.

Because the core job of a router is to find the best path for each packet that passes through the router. What is best? Of course, in many paths to choose the fastest, the best quality, the shortest path,… And the routes corresponding to the optimal routes to different networks are formed into a new table, that is, FIB table (forwarding table).

In my Ubantu system, RIB tables and FIB tables can be queried by route and route-f respectively.

As a host device, the routing table is simple and there are no multiple outbound interfaces. Therefore, the FIB table and RIB table are the same.

It needs to be noted that there are many names for these two tables, but as long as you know the role of the two tables, then see other names are no longer strange. Usually, the routing table we refer to in network forwarding is the general name of the two tables, or does not distinguish which table is used at all. Different network devices may also use different tables for routing, addressing, and forwarding.

Routing entry content:

In the routing table, each entry contains the following contents:

Destination network address (Destination) + Subnet mask (Genmask) : The network address and the network mask determine the Destination network range that can be reached by the local host. Generally, the Destination network range includes the following: (1) Host address: indicates the network address of a specific host. (2) Subnet address: the network address of a specific subnet; (3) Default route: All network addresses not specified in the routing table are matched with 0.0.0.0, which is used to configure the default gateway (default route is displayed in the Ubantu VM).

Gateway/Next Hop: When common terminals (such as PCS and mobile phones) access the network, they do not need to configure any routing information. Instead, they use the DHCP protocol of routers to assign IP addresses. When receiving IP addresses, the terminal sets the Gateway of the device as a directly connected router. In the process of Internet access, all packets are directly sent to the gateway device for subsequent forwarding because there is no other route when they are queried.

The network device updates the routing table by configuring dynamic routing protocols, and also sets the default gateway. If a routing entry exists in the received packet, the packet is sent to the next-hop network device through the outgoing interface of the routing entry. If no routing entry is matched, the packet needs to be sent to the default gateway for subsequent forwarding.

Interface (Iface) : An interface defines the egress that a router uses to forward packets to a specific network destination address. It is used to determine from which network port the packet is sent to the next-hop device.

Metric: Indicates the cost of a route. Generally, it indicates the total number of routers required to reach the destination address. A Metric indicates the number of routers that pass through a router. Fewer hops usually means lower cost of the route, while more hops means higher cost. When there are multiple routing options for the same network, the routing algorithm selects the route with fewer hops.

Flags: Common Flag flags in the routing table are as follows:

  1. U: Routes are dynamic.
  2. H: The target is a host;
  3. G: The route points to the gateway.
  4. R: restores entries generated by dynamic routes.
  5. D: dynamic installation by routing background program;
  6. M: modified by the routing background program;
  7. ! : Denies routes.

In my previous work, I often checked the Routing table of Cisco devices. Its marker bits were more detailed and clearly marked the dynamic routing type of routing entries.

Refs: unused in the Linux kernel, usually 0.

Search count (Use) : indicates the number of times that the route item is searched by the routing software.

There are three types of routes in the routing table:

  • Direct routes (routes discovered by link layer protocols)
  • Static routes (routes manually configured by the administrator)
  • Dynamic routing (routes discovered by dynamic routing protocols)

Static routing table features: Static routes are fixed routes manually configured by the administrator on a router and maintained by the administrator. Static routes do not age out due to timeout and do not change with network topology changes. Static routes need to be maintained by administrators, so they cannot detect and adjust the network topology in real time. Therefore, static routes are only used in small-scale networks with simple topology.

Dynamic routing table features: Dynamic routing tables are created, updated, and maintained by dynamic routing protocols. Common dynamic routing protocols include BGP, RIP, OSPF, ISIS, and EIGRP. Dynamic routing protocols have the following advantages: They can sense network topology changes in real time and adjust routing tables accordingly. Good network scalability, suitable for large and medium-sized networks;

Routing table matching rules:

  • Exact matching algorithm
  • Longest Prefix Matching algorithm (LPM for short)

Typically, network devices implement both of these matching algorithms, but each implementation varies. Routing matching algorithm is very important for network equipment. As a forwarding device, if the number of routing entries reaches a certain number (for example, 100,000 entries, million entries, ten million entries,…), , the performance of matching algorithm needs to be fully considered.

In addition to the retrieval efficiency of the algorithm, we also need to consider whether the search acceleration can be realized by hardware.

Typical algorithms are:

  • The hashing (bucket) algorithm represented by the Linux routing lookup algorithm
  • Lc-trie tree lookup algorithm for Linux
  • Radix Search algorithm of BSD/Cisco
  • BSD/Cisco 256 fork tree search algorithm
  • Piecewise search algorithm used in DPDK (similar to multi-level page table query)

To learn more about the routing table matching principles, read the Routing table Lookup algorithm overview of Internet Routing – Hash/LC-trie tree / 256-way-Mtrie tree

Media Access Control Table

According to the ISO network model, routing tables are located at the network layer and are used for routing and addressing functions. The Mac table maintains the data link layer, which records mappings between Mac addresses -> ports. Speaking of MAC tables, although every network appliance vendor exists, it is more detailed in the switch.

MAC list items:

The MAC address table contains the following contents:

  • The MAC address
  • Physical interface
  • Mac Entry Types (possible)
  • Aging time
  • Vlan-id (possible)

The MAC address table contains dynamic MAC address entries and static MAC address entries. Therefore, the MAC address table contains the aging time and type. Static MAC addresses and static routes are managed and maintained by an administrator. Dynamic Mac address entries are learned. There are generally two important threads in the switch: address learning thread and packet forwarding thread.

Address learning thread:
  • Source MAC address learning: After receiving a packet from the network, the switch learns the source MAC address of the packet and establishes MAC address entries.
  • Port movement mechanism: After receiving a packet, if the port on the switch is found to be inconsistent with the corresponding port in the MAC address table, the switch moves the port and learns the MAC address to a new port.
  • Address aging mechanism: If no packet corresponding to a Mac address entry is received for a long time, the Mac address is deleted. Relearn the packet when it arrives next time.
Packet forwarding thread:
  1. After receiving the packet, the switch queries the Mac address table according to the destination Mac address in the packet. If found, it is emitted from the corresponding port; If it is not found, it is sent to all ports except the incoming port (the legendary flooding);
  2. If the destination Mac address and source Mac address of a packet received by the switch reside on the same port, the switch discards the packet.
  3. If the destination Mac address of a broadcast packet received by a switch is a broadcast packet, the switch forwards the broadcast packet to all ports except the incoming port.

Note: Broadcast and flooding are two different concepts, although sometimes both send messages to all ports.

Address Resolution Table

In the 7-layer OSI model, IP addresses work at layer 3 (the network layer) and Mac addresses work at layer 2 (the data link layer). When forwarding packets, the destination IP address is known, but the destination Mac address is unknown. When encapsulating packets, encapsulate the IP header first and then fill the Layer 2 header. However, because the Mac address is not known, the header of layer 2 cannot be filled. In this case, the ARP protocol is used. It queries the Mac address corresponding to the specified IP address to construct a Mac address entry. Therefore, the Mac address table is essentially a mapping between IP addresses and Mac addresses.

summary

This paper mainly introduces three types of tables (routing table, ARP table, Mac table) that are often encountered in computer networks. The routing table can be subdivided into routing information table (RIB) and forwarding information table (FIB). The RIB table is used to maintain the topology information of the network, while the FIB selects the forwarding information composed of optimal routes from the RIB table. When forwarding (sending) packets:

  1. Query the routing table to determine whether the destination IP address is reachable. If yes, determine the outgoing interface and the next hop
  2. Then query the ARP table to obtain the Mac address corresponding to the destination address and construct a complete Ethernet packet.
  3. Finally, the Mac address table is queried to determine the sending interface of the packet. After determining the outbound interface, the kernel sends the packet to the corresponding NIC driver. The NIC sends the packet to the next-hop device at an appropriate time.