Connecting millions of networks around the world and being able to communicate with each other is a very complex task that requires solving many problems, such as different addressing schemes, different network access mechanisms, different error handling methods, different routing mechanisms, etc. Users’ needs are diverse, and no single network can meet all users’ needs. One of the tasks of the network layer is to interconnect these heterogeneous networks. The interconnection of the so-called network refers to two or more computer networks, through certain methods, with one or more communication processing equipment (intermediate equipment) mutual connection, in order to form a larger network system.

In the hierarchical structure of a computer network, different layers have different relay devices:

Therefore, “The network layer uses routers for interconnection” means “The relay device at the network layer is a router”.

What is a router? As long as the home installed wifi must be familiar with the router, it is:

Yeah, but we’re just using a home router, which is different from routing on a computer network, but it runs the same protocol, the same computer theory. A router is also essentially a computer for routing over the Internet. Note that the router is a very important device. The entire network layer uses the router as a node to exchange data and information.

A router performs two main functions: route selection (determining which path to take) and packet forwarding (the action taken when a packet arrives). The former constructs routing table according to the specific routing protocol and constantly updates and maintains routing table by exchanging routing information with neighboring routers regularly or regularly. The latter process the data flow through the router, and the key operations are forwarding table query, forwarding and related queue management and task scheduling. 1) Routing selection: according to the complex distributed algorithm, the selected routes are dynamically changed according to the changes of the entire network topology obtained from each neighboring router; 2) Packet forwarding: the router forwards the user’s IP datagram from the appropriate port according to the forwarding table. The routing table is derived from the routing algorithm, and the forwarding table is derived from the routing table. The structure of the forwarding table should optimize the lookup process, and the routing table should optimize the calculation of network topology changes. When discussing the principle of routing, the term routing table is generally used instead of distinguishing between forwarding table and routing table.

In communication subnet, caused by excessive group and network performance degradation is called congestion, consider a situation where a router link bandwidth for R B/s (note: R is unknown the alphabet, B/s is a unit of bandwidth, bytes per second), if IP packet from its only one port, its rate is R B/s. When r= r, it may seem like a “good thing” because the link bandwidth is fully utilized.

However, as the rate of packets arriving at the router approaches R, the average time tingle increases dramatically, and a large number of packets are discarded (the buffer on the router port is limited), the throughput of the entire network plummets, and the average latency between the source and destination becomes nearly infinite. The method to judge whether the network is in the state of congestion is to observe the relationship between network throughput and network load: 1) If the network throughput is significantly less than the normal throughput with the increase of network load, the network may enter the state of “mild congestion”; 2) If the network throughput decreases with the increase of network load, the network may enter the state of congestion; 3) If the network load continues to increase and the network throughput drops to zero, the network may enter a deadlock state.

1) Open-loop control: in the design of the network, factors related to congestion will be considered in advance, and strive to avoid congestion in the work of the network. It is a static approach to prevention. Once the whole system is up and running, no modifications are needed halfway through. Open-loop control means can include determining when to receive new traffic, when to discard groups and which groups to discard, and determining what scheduling decisions to make, etc. The common feature of all these means is that they do not consider the current network state when making decisions. 2) Closed-loop control: regardless of various factors related to congestion in advance, the monitoring network system is used to monitor and timely detect where congestion occurs, and then the congestion information is transmitted to the appropriate place to adjust the operation of the network system and solve problems. Closed-loop control is based on the concept of feedback loop, which is a dynamic approach.

Router forward packets are forwarded by routers, which are obtained by various algorithms. We divide routing algorithms into two types: static routing algorithm and dynamic routing algorithm according to whether they can be adjusted adaptively with the traffic or topology of the network.

Static routing algorithm: Also called non-adaptive routing algorithm, the network administrator manually configures routing information. When the network topology or link state changes, the network administrator need to manually modify the router in the static routing information, but the static routing algorithm applies only to a small, simple, high security of military and commercial network system (large civil network of complex structure, the change is big, the network administrator can not hold!).

Dynamic routing algorithm, called adaptive routing algorithm on a router’s routing table entry is through the mutual connection between the router compared to exchange information, then according to certain algorithm optimization, and the routing information is continuously updated in a certain time interval, to adapt to the changing network, to obtain the optimal path finding at any time.

Two routing algorithms that look more convenient with tables:

Such as the table above shows that for large network system, the structure is complex and changing situation, impossible by the network administrator to set up the deployment of static routing algorithm (i.e., cannot use), can only be set algorithm, automatically ADAPTS to network algorithm, and here we commonly used dynamic routing algorithm can be divided into two categories — – “distance vector routing algorithm” “link-state routing algorithm.

The link-state routing algorithm requires that each node participating in the algorithm has complete network topology information. They perform the following two tasks: first, actively test the status of all adjacent nodes. Two nodes that share a link are neighbors that are connected to the same link or to the same broadcast physical network. Second, the link state is periodically propagated to all other nodes (that is, all other routing nodes). The typical link state algorithm is the OSPF algorithm (described in Part iv – Routing Agreement).

In a link-state routing, a node checks the status of all direct links and sends the resulting status information to all other nodes on the network, not just those directly connected. In this way, each node receives routing information containing direct link status from all other nodes on the network.

Whenever link-state packets arrived, routing nodes will use these status information to update their own network topology and the state of “visual field”, once the link-state changed, node to update the network diagram using Dijsktra shortest path algorithm to calculate the routing, starting from the source of a single calculation reaches the purpose of all nodes of the shortest path. The link-state routing algorithm mainly has three characteristics: 1) Send information to all routers in the AS Autonomous system, in this case by flooding, That is, a router sends a message to all neighboring routers through all ports, and each neighboring router sends the message to all its neighbors (but not to the router that just sent the message). 2) The information sent is the link state of all routers adjacent to the router (the “link state” here indicates which routers are adjacent to the router and the “metric” of the link), but this is only part of the information known to the router. For the OSPF algorithm, the metrics of link status are mainly used to represent costs, distances, delays, and bandwidths. 3) The router sends this message to all routers only when the link status changes. Because the link state of a router only involves the connectivity state of neighboring routers, there is no direct relationship between the link state routing algorithm and the scale of the entire Internet. Therefore, the link state routing algorithm can be used in the large Internet environment or the aggregation of routing information changes.

The main advantage of the link-state routing algorithm is that each routing node uses the same original state data to calculate the path independently, and does not depend on the calculation of the intermediate node. Link-state packets are transmitted unchanged, so the algorithm is easy to find faults. Nodes from all the other when a received message, it can be in the local immediately calculate the correct path, guarantee the step convergence, finally because link-state packets carrying only from a single node information about direct link, its size has nothing to do with in the network routing node number, therefore, link-state algorithm than distance vector algorithm has better scale to stretching.

Comparison between distance vector routing algorithm and road state routing algorithm: In distance vector routing algorithm, each node is only with it Direct neighbors, it offers its neighbors from himself to all other nodes in the network of the lowest cost estimate, in link-state routing algorithm, each node through radio talking to all other nodes, but it only tell them directly connected with its link cost, by contrast, distance vector routing algorithm is possible to meet the problem such as routing loops.

Route selection within an AS is called intra-zone route selection, and route selection between aS is called interzone route selection. There are two main types of routing protocols on the Internet. 1. Interior Gateway Protocol (IGP) : A routing Protocol used within an AUTONOMOUS system, independent of the routing Protocol used by other autonomous systems on the Internet. At present, these routing protocols, such as RIP and OSPF, are most commonly used. 2. External Gateway Protocol (EGP) : If the source and destination are in different autonomous systems, a protocol is required to pass routing information to the other AUTONOMOUS system when the datagram passes to the boundary of one autonomous system (the two autonomous systems may use different GP). Such a protocol is the external gateway protocol EGP. The most commonly used external gateway protocol is BGP-4. A diagram of two autonomous systems interconnected:

In the figure above, Each autonomous system to decide which run within the autonomous system internal routing protocol (for example, can be a RIP, can also be a OSPF), but each autonomous system has one or more routers (figure of router R1 and R2) in addition to running the system’s internal routing protocol, routing protocol will run between autonomous systems (for example, B GP – 4).

1) Each router in the network maintains a record of the distance from itself to each other destination network (thus, this is a set of distances, called a “distance vector”). 2) Distance, also known as Hop Count, sets the distance (Hop Count) from a router to the directly connected network as 1. Each time you pass through a router, the distance (hop count) increases by 1. 3)RIP considers a good route to be a route with a small number of routers, that is, a route with a small hop count is preferentially selected. 4)RIP allows a path to contain a maximum of 15 routers (that is, a maximum of 15 hops). Therefore, if the distance is 16, it indicates that the network is unreachable. Therefore, RIP applies only to small Internet. Loop problems may occur in distance vector routing. The purpose of specifying the maximum hop count on the path is to prevent datagrams from constantly circulating on the loop and reduce the possibility of network congestion. 5) By default, RIP broadcasts RIP route updates every 30 seconds between any two RIP routers to automatically establish and maintain a routing table (dynamic maintenance). 6) RIP does not support the broadcast of subnet masks, so the subnet masks of each network in RIP must be identical. However, in the new RIP2, variable length subnet masks and CIDR are supported.

Each routing table item has three key data :< destination network N, distance D, next-hop router X>. Perform the following steps for each RIP packet sent by an adjacent router: 1) Modify all the items in the RIP packet sent from a neighboring router X: Change the address in the Next Hop field to X, and add the value of all distance fields to 1. 2) Perform the following steps for each item in the modified RIP packet: (1) If the destination network N does not exist in the original routing table, the item is added to the routing table. (2) If the destination network N exists in the original routing table and the next-hop router address is X, the item in the original routing table is replaced with the received item ③ If the destination network N exists in the original routing table and the next-hop router address is not X, if the distance D in the received item is smaller than that in the routing table, the received item replaces the item in the original routing table: otherwise, nothing is done 3) If the router does not receive the updated routing table from the neighboring router within 180 seconds (the default RIP timeout period is 180 seconds), the neighboring router is regarded as unreachable. That is, the distance between the neighboring router and the router is set to 16(16 indicates unreachable). 4) Return

To better learn OSPF, compare RIP with OSPF:

Because of the frequent exchange of link state information among routers, all routers can eventually establish a link state database. This database is essentially a topology map of the entire network, which is consistent across the entire network (this is called link-state database synchronization). Each router then according to the entire network topology structure, Dijkstra shortest path algorithm is used to calculate the optimal path from yourself to the purpose of the network, to construct their own routing table, after that, when the link state changes, each router to calculate to the optimal path of each objective network construct new routing table.

Note: Although the complete optimal path can be calculated using Dijkstra, the routing table does not store the complete path and stores the next hop (only after the next hop router can know how to go).

To enable OSPF to apply to large-scale networks,OSPF divides an AS into several smaller areas, called areas. The advantage of partitioning is that the exchange of link-state information by flooding is limited to each region rather than the entire autonomous system, which reduces the traffic over the entire network. A router in an area only knows the complete network topology of the area, but does not know the network topology of other areas. These areas also have layers. The domains at the top are called backbone regions and are responsible for connecting to other regions at the bottom, as well as to other autonomous regions.

The Border Gateway Protocol (BGP) is a Protocol used to exchange routing information between routers of different ass. It is an external gateway protocol. The Border Gateway protocol is often used between gateways on the Internet. The routing table contains a list of known routers, the addresses the routers can reach, and the number of hops on the path to each router. The internal gateway protocol is primarily an attempt to make datagrams AS efficient AS possible from source to destination in an AS. There is no need to consider other aspects of strategy within an AS. However, BGP is used in a different environment, mainly because 1) The large scale of the Internet makes it very difficult to select routes between autonomous systems. 2) It is impractical to find the best route between autonomous systems. 3) Routing policies must be considered for routing between autonomous systems

The boundary gateway protocol BGP is only trying to find a better route to reach the destination network (without going around in circles) rather than to find the best route. BGP uses path-vector routing protocol, which is very different from distance vector protocol and link-state protocol. BGP is an application layer protocol based on TCP.

BGP works as follows: The administrator of each AS selects at least one router as the BGP spokesperson of the AS. A BGP spokesperson exchanges routing messages with other BGP spokesmen of the AS BGP packets are transmitted through TCP, that is, BGP packets are the data part of TCP packets. BGP packets are exchanged on this connection to establish BGP sessions. BGP sessions are used to exchange routing information After all BGP spokesmen exchange network reachability information with each other, each BGP spokesman can find a better route to each AS.

Each BGP spokesperson must run both BGP and the internal gateway protocol used by the AS, such AS OSPF or RIP. The network reachability information exchanged by BGP is a series of ass that must pass to reach a certain network (represented by network prefix).

BGP has the following features: 1) The number of nodes that BGP exchanges routing information is the same as that of autonomous systems, which is much smaller than the number of networks in these autonomous systems. 2) The number of BGP spokesmen (or border routers) in each AUTONOMOUS system is small, which makes routing between autonomous systems less complicated. 3)BGP supports CIDR, so the ROUTING table of BGP should include the destination network prefix, the next-hop router, and the sequence of autonomous systems to reach the destination network. 4) When BGP is just running,BGP neighbors exchange the entire BGP routing table, but in the future, they only need to update the changed part when changes occur. This will save network bandwidth and reduce the processing overhead of the router.

Bgp-4 uses four types of packets: 1) The Open message is used to establish a relationship with another neighboring BGP spokesperson. 2) the Upte message is used to send information about a route and list multiple routes to be kepted. 3) The Keepalive message is used to confirm the Open message and periodically confirm the neighbor relationship 4) Notification messages are used to send detected errors

The following table compares RIP,OSPF, and BGP

Summary: Presents the relationship diagram of routing protocol and routing algorithm

The practical requirement for using multicast is for applications to send a packet to multiple destination hosts. If IP multicast is not used (that is, done in unicast mode), the source host (the audio and video server in the image below) needs to unicast each destination host (in this case the client) once, sending a separate IP packet. If IP multicast is used, the source host sends a single IP packet to a multicast address. (Both IPv4 and IPv6 have reserved multicast addresses, and multicast addresses are used to identify a group of addresses.) The network sends a copy of this IP packet to each host in the multicast group, thus completing the packet sending to multiple destination hosts.

The illustration is as follows: IP multicast is not used

Use IP multicast

Note: In IP multicast, a host can choose to join or leave a group, so that a host can belong to multiple groups.

IP multicast uses the class D address format. The first four bits of a Class D address are 1110. So the range of class D addresses is 224.0.0.0 239.255.255.255. Each class D P address identifies a multicast group.

Multicast datagrams differ from ordinary IP datagrams in that they use class D IP addresses only as destination addresses, and the protocol field value in the header is 2, indicating the use of IGMP. Note to the committee: 1) Multicast datagrams are also “best efforts delivered” and do not provide reliable delivery; 2) Multicast addresses can only be used for destination addresses, not source addresses; 3) No ICMP error message is generated for multicast datagrams. Therefore, if the multicast address is entered after the PING command, no response will be received. 4) Not all class D addresses can be used as multicast addresses.

IP multicast can be divided into two types: network multicast on the Internet and hardware multicast on the LAN. The relationship between the two types of multicast is: the final stage of multicast over the Internet, or the delivery of multicast datagrams to all members of the multicast group using hardware multicast over the LAN.

Network multicast example: an audio and video server serves 90 hosts, as shown in the above figure (the previous figure is for comparing network multicast with hardware multicast).

Hardware multicast example: IANA has Ethernet multicast addresses ranging from 01-00-5E-00-00-00 to 01-00-5E-7f-ff-ff. It is easy to see that only 23 bits of each address can be used for multicast. Only 23 bits of a Class D IP address can be allocated. The first five bits of a Class D IP address cannot be used as an Ethernet hardware address. For example,IP multicast address 224.128.64.32(e0-80-40-20) and another IP multicast address 224.0.64.32(e0-00-40-20) are both translated into Ethernet hardware multicast addresses 01-00-5E-00-40-20. The mapping between the multicast IP address and the Ethernet hardware address is not unique. Therefore, the host that receives the multicast packet must use software to filter the packet at the IP layer and discard the packet that is not to be received by the host. As shown in figure:

What it means: The Internet architecture and protocols that support mobility are collectively known as mobile IP. It is designed to allow mobile nodes (computers, servers, network segments, etc.) to maintain their connectivity while moving. To be more precise, mobile IP technology is to move nodes to fixed network IP addresses to realize roaming across different network segments, and ensure that the network permissions based on network IP will not change in the roaming process. Goal/Role/Purpose: The goal of mobile IP is to automatically delegate packets to mobile nodes. A mobile node is a host that changes its connection point from one network or subnet to another. With mobile IP, a mobile node can change its resident location without changing its IP address.

Composition/composition: ipv4-based mobile IP defines three functional entities: mobile nodes, home agents (also known as local agents) and out-of-port agents (also known as external agents). 1) Mobile node: mobile node with permanent IP address 2) Local agent: in a network environment, the permanent “residence” of a mobile node is called the home network. In the home network, the entity that performs the mobile management function on behalf of the mobile node is called the home agent (local agent). According to the transfer address of the mobile user, it transfers the data packets of the mobile node using tunnel technology 3) External agent: the entity that helps the mobile node to complete the mobile management function in the external network is called external agent

In the mobile IP protocol, each mobile node has a unique local address, and its local address is unchanged when the mobile node moves. In the local network link, each local node must also have a local agent to maintain the current location information for it, which needs to introduce the forward address. When a mobile node is connected to a foreign network link, the forward address is used to identify the current location of the mobile node for routing purposes. The union of the local address of the move node with the current forward address is called the move binding or simply binding. When the mobile node gets a new forwarding address, it registers with the local agent by binding so that the local agent knows the current location of the mobile node in real time.

The basic communication flow of mobile IP technology is as follows: 1) When the mobile node is in the local network, it communicates in the traditional TCP/IP way (the inherent address in the local network). 2) roaming mobile nodes to a local network, are still using a fixed IP address to communicate, in order to be able to receive communications of IP packet, it issued to the mobile node needs to be registered address the current position with the local agent, the location address is passed to the address (it can be an external agent address or dynamic configuration of an address) 3) After receiving the registration from the forward address, the local proxy will construct a tunnel to the forward address and send the intercepted IP packets destined for mobile nodes to the forward address through the tunnel 4) Unpack the tunnel at the forwarding address, recover the original IP packet, and finally send it to the mobile node, so that the mobile node can receive the IP packet sent to it on the extranet. 5) The extranet of the mobile node sends IP packet to the communication peer through the router or the extranet agent 7) When the mobile node returns to the local network, the mobile node cancels the forwarding address to the local agent. At this time, the mobile node will use the traditional TCP/IP mode to communicate

Mobile IP Sets two IP addresses for the mobile host, namely the primary address and the secondary address (the forward address). When the mobile host is on the local network, it uses the primary address. When moving to another network, you need to obtain a temporary secondary address, but the primary address remains the same. When moving from the extranet back to the local network, the secondary address changes or is discarded, while the primary address remains the same.

In terms of structure, router consists of route selection and packet forwarding. From the perspective of the model, the router is a device at the network layer, which implements the next three layers of the network model, namely the physical layer, the data link layer and the network layer. The router architecture is as follows:

Note that if a store-and-forward device implements a level of functionality, it can interconnect two network segments (networks) that use different protocols at that level. For example, the bridge realizes the physical layer and the data link layer, so the bridge can connect two different network segments of the physical layer and the data link layer. However, the repeater realizes the physical layer, but cannot interconnect two different network segments of the physical layer. This is because the repeater is not a store-and-forward device, but a straight-through device.

The routing part is also called the control part, and its core component is the routing processor. The task of the routing processor is to construct routing table according to the selected routing protocol, and update and maintain the routing table constantly by exchanging routing information with other neighboring routers regularly or regularly. Packet forwarding consists of three parts: switching structure, a set of input ports and a set of output ports. Input ports from the physical layer can be derived from the received bit stream link layer frames, then data frames from network layer, an output port is to perform the opposite operation, exchange structure are key components in the router, turn it according to the published to deal with group, will enter an input port grouping out from a suitable output port forwarding. There are three common switching methods: switching by memory, switching by bus, and switching by Internet. The switching structure itself is a network.

The forwarding table is derived from the routing table, and its entries directly correspond to routing entries. However, the format of the forwarding table is different from that of the routing table, which should be structured to optimize the lookup process (while the routing table needs to optimize the calculation of network topology changes). Turn published contains a packet will be sent to the destination address, and the grouping of the next-hop (namely the destination address, the next step the receiver for the actual MAC address) to reduce the number of turns published repeat project, you can use a default route instead of all with the same “the next-hop project, and set the default route is lower than the other project priority. Routing tables are always implemented in software; Forwarding tables can be implemented with software or even special hardware. No default route is configured:

The default route is configured:

The two forwarding tables are described as follows: 1. The forwarding table records the next-hop router that the router reaches on a network. 2. The router has a default route with the lowest priority. If all other items fail to match, the router uses the default route to the next-hop router.

Note 1: When discussing the principle of routing, it is not necessary to distinguish between a routing table and a routing table. However, it is important to note that a routing table is not equal to a forwarding table. The actual forwarding of the packet is to look up the forwarding table directly, not the routing table directly. Note 2: The difference between forwarding and routing: “forwarding” refers to the router forwarding the received IP datagram from the appropriate port according to the forwarding table. It involves only one router, while “routing” involves many routers. The routing table is the result of the cooperation of many routers. These routers construct the entire routing table by dynamically changing the selected routes based on the changes in network topology obtained from the neighboring routers based on complex routing algorithms.