IP Layer forwarding packet flow
Let's learn this article together IP Layer forwarding packet flow .
First, a simple example is given to illustrate how the router forwards packets , As shown in the figure below ：
Yes 4 individual A Class networks are connected by three routers , There may be thousands of hosts on every network . If the routing table indicates how each host should forward , Then the routing table will be too large （ Suppose there are 10000 hosts in each network , Four networks have 4 Ten thousand hosts , So every routing table has 4 Line ten thousand ）, But if the routing table indicates how to forward to a certain network , Then the routing table in each router only contains 4 That's ok , One line corresponds to one network . With routers R2 For example, the routing table of , because R2 Connect to the network at the same time 2 And the Internet 3 On , So as long as the destination host is on the network 2 Or network 3 On , All through the interface 0 or 1 By the router R2 Direct delivery （ And use ARP Protocol found host hardware address ）. If the destination host is on the network 1 in , Then the next hop router should be R1, Its IP The address is 184.108.40.206. Router R2 and R1 Because of being connected to the network at the same time 2 On , So the router R2 Forward the packet to the router R1 It's easy . Empathy , If the destination host is on the network 4 in , Then router R2 The packet should be forwarded to IP The address is 220.127.116.11 The router R3（ Be careful ： Every router has 2 Different IP Address ）.
The whole network topology can be simplified as shown in the figure below ：
The network becomes a link , But every router says it's IP Address . Using a simplified diagram like this , So that we do not have to care about the specific topology of a network and how many hosts are connected to the network , This diagram emphasizes that when forwarding packets over the Internet , It's forwarding from one router to the next .
In the routing table , The most important information of each route is the following two ：
- Destination network address
- Next hop address
Determine the next hop router according to the destination network address , By doing so, we can get the following results ：
- IP The datagram will eventually find the router on the network where the destination host is located
- Only when you get to the last router , Just trying to deliver directly to the destination host
stay IP In the first part of the datagram , There is no place to indicate “ Next hop router IP Address ”, stay IP The first part of the datagram says IP The address is the source IP Address and purpose IP Address , Without a router in the middle IP Address . since IP There is no next hop router in the datagram IP Address , So how can the datagram to be forwarded find the next hop router ？ When the router receives a datagram to be forwarded , Get the next hop router from the routing table IP After the address , It's not filling in this address IP The datagram , It's the network interface software delivered to the data link layer . Network interface software is responsible for the next hop router IP Address to hardware address （ Use ARP agreement ）, And put this hardware address in the link layer MAC The first part of the frame , Then find the next hop router based on this hardware address . thus it can be seen , When sending a series of datagrams , The above lookup routing table 、 use ARP Get the hardware address 、 Write the hardware address to MAC The first part of the frame and so on , It's going to be repeated .
The following summarizes the packet forwarding algorithm ：
- Extract the destination host's... From the header of the datagram IP Address D, The destination network address is N
- if N Is a network address directly connected to this router , Direct delivery , That is, there is no need to go through other routers , Deliver the datagram directly to the destination host （ Put the destination host address D Convert to hardware address , Encapsulate datagrams as MAC frame , Send this frame again ）; Otherwise, it will be delivered indirectly , Perform the next step
- If the destination address in the routing table is D Specific host routing for , Then the datagram is sent to the next hop router specified in the routing table , otherwise , Perform the next step
- If there is an arrival network in the routing table N The routing , Then the datagram is sent to the next hop router specified in the routing table , otherwise , Perform the next step
- If there is a default route in the routing table , The datagram is sent to the default router specified in the routing table , otherwise , Perform the next step
- Report forwarding packet error
The routing table does not indicate the complete path of the packet to a certain network , Which router to go through first , And then through which router and so on . The routing table indicates , To a network, you should go to a router first , After reaching the next hop router , Continue to look up the routing table , Know which router to go to next . So step by step to find it , Until we finally reach the destination network . It's like we go to a destination , But there's no map , You can only ask for directions at every fork in the road , Passers by only pointed out how to go the next section of the road , At the next fork , We keep asking for directions , So back and forth . Even without a map , But in the end it will be there .
Before we go further into routing , We'll also introduce two very important concepts, subnet division and Supernet construction .
Level three IP Address
Today to see , stay ARPANET Early stage ,IP The design of the address is not reasonable ：
IP The utilization of address space is sometimes very low
every last A Class address network can connect more than 1000 ten thousand , And every one B Class address network can be connected to more than the number of hosts 6 ten thousand . Some units have applied for a B Class address network , But the number of hosts connected is not much , I'm not willing to apply for one that's enough to use C Class address .IP Waste of address , And make IP Address space resources are used up too early .
Assigning a network number to each physical network will make the routing table too large and make the network performance worse
Every router should be able to find out how to get to the next hop router of other networks from the routing table , When there are more networks in the Internet , The more items in the router's routing table . such , Even if we have enough IP The address resource can assign a network number to each physical network , It can also cause too many entries in the router's routing table . This not only increases the cost of routers （ More storage space ）, And finding a route takes more time , At the same time, it also makes the routing information exchanged between routers increase sharply , Therefore, the performance of router and Internet will decline .
Level two IP The address is not flexible enough
Sometimes it's urgent , A unit needs to open a new network immediately in a new place . But in applying for a new IP Before the address , It's impossible for the newly added network to work on the Internet .
To solve the above problems , from 1985 From the year onwards ,IP Added one to the address “ Subnet number field ”, Make two levels IP The address becomes level three IP Address . This is called subnetting , Its basic idea is as follows ：
（1） A unit with many physical networks , The physical network can be divided into several subnets （subnet）. The division of subnets is purely a matter within an organization , The network outside our unit can't see how many subnets this network is composed of , Because this unit is still a network .
（2） The method of subnet division is to borrow several bits from the host number of the network as the subnet number （subnet-id）, Of course, the host number will be reduced by the same number of digits .
（3） All from other network send to this unit a host IP The datagram , It's still based on IP The destination network number of the datagram finds the router connected to the network of the unit . But this router is receiving IP After the data report , Then find the destination subnet according to the destination network number and subnet number , hold IP Datagram delivery to destination host .
Let's use an example to illustrate the concept of subnet division ：
A unit has a B class IP Address , The Internet address is 18.104.22.168（ The network number is 145.13）. Where the destination address is 145.13.x.x All the datagrams are sent to the router on this network R1.
Now divide the network shown in the figure above into three subnets , Suppose the subnet number is occupied 8 position , Then the host number is just 8 position . The three subnets are 22.214.171.124、126.96.36.199、188.8.131.52. After subnetting , The whole network is still a network to the outside , Its network address is 184.108.40.206, But the Internet 220.127.116.11 Router on R1 After receiving data from outside , And then according to the destination address of the datagram, forward it to the corresponding subnet .
Suppose a datagram has reached the router R1（18.104.22.168）, So how does this router forward it to the subnet 22.214.171.124 Well ？
from IP The header of the datagram can't see whether the network connected by the source host or destination host is divided into subnets . because IP Neither the address itself nor the header of the datagram contains any information about subnet division , Something else has to be done , This is the subnet mask . As shown in the figure below ：
To make the router R1 It's very convenient to extract the purpose from the datagram IP The network address of the subnet to be found is extracted from the address , Router R1 We're going to use level three IP The subnet mask for the address . The purpose of the datagram IP Address and subnet mask “ And ” operation , You can get the network address of the subnet . From the outside of the Internet , This is a common B Class network , But after entering this network （ Enter the router R1）, You can see that there are still many networks （ subnet ）.
Now the Internet standard says ： All networks must use a subnet mask , At the same time, there must be a subnet mask column in the router's routing table . If a network is not divided into subnets , Then the subnet mask of the network uses the default subnet mask , as follows ：
- A Class address default subnet mask ：255.0.0.0
- B Class address default subnet mask ：255.255.0.0
- C Class address default subnet mask ：255.255.255.0
Subnet mask is an important property of a network or a subnet , When routers exchange routing information with neighboring routers , You have to put your network （ Or subnets ） The subnet mask tells the adjacent router . Every item in the router's routing table , Besides giving the destination network address , The subnet mask of the network must also be given . If a router is connected to two subnets , You have two network addresses and two subnet masks .
Subnetting adds flexibility , But it reduces the number of hosts that can connect to the network .
Forwarding packets when using subnets
After subnetting , The packet forwarding algorithm must be changed accordingly .
After using subnet partition , The routing table must contain the following three items ： Destination network address 、 Subnet mask 、 Next hop address , At this time, the forwarding packet algorithm is as follows ：
- Extract the destination from the header of the received datagram IP Address D
- Judge whether to deliver directly , Check the network directly connected to the router one by one ： Use the subnet mask of each network and D Conduct “ And ” operation , See if the result matches the network address . If the match , Direct delivery to the group （ hold D Convert to physical address , Encapsulate datagram into frame and send it out ）, Otherwise indirect delivery , Perform the next step
- If the destination address of the routing table is D Specific host routing for , Then the datagram is sent to the next hop router specified in the routing table , Otherwise go to the next step
- For each row in the routing table , Use the subnet mask and D Conduct “ And ” operation , The result is N. if N Matches the destination network address of the line , Then the datagram is sent to the next hop router indicated by the line , Otherwise go to the next step
- If there is a default route in the routing table , Then the datagram is sent to the default router indicated in the routing table , Otherwise go to the next step
- Report forwarding group error
No classified address CIDR（ Construct hypernets ）
To a certain extent, the division of subnets eases the difficulties encountered in the development of the Internet , However, in 1992 year , The Internet still faces three problems that must be solved as soon as possible , This is it. ：
（1）B Class address in 1992 Half of the year has been allocated , It will be all distributed soon
（2） The number of items in the routing table on the Internet backbone has increased dramatically （ From thousands to tens of thousands ）
（3） Whole IPv4 The final address will run out of space （2011 year 2 month 3 Japan ,IANA announce IPv4 Address exhaustion ）
IETF To solve the first two problems, we have developed a method of address coding without classification , Its official name is classless inter domain routing CIDR（Classless Inter-Domain Routing）, There are two main characteristics ：
（1） It eliminates the traditional A class 、B class 、C The concept of class address and subnets . It is the 32 Bit IP The address is divided into two parts , The front part is the network prefix , Used to indicate the network , The back part is for the mainframe . therefore ,CIDR send IP The address goes from three-level addressing to two-level addressing , It uses the slash notation , stay IP Slash after address “/”, Write in the number of digits occupied by the network prefix .
（2）CIDR Make the network prefixes the same continuous IP Address in one “CIDR Address block ”, As long as you know CIDR Any address in the address block , You can know the starting address of this address block （ Minimum address ）, Maximum address , And the number of addresses in the address block .
Of course , The host number is full 0 And all 1 The address of , Generally not used . To facilitate routing ,CIDR Use 32 Bit address mask , It consists of a string of 1 And a bunch of 0 form ,1 The number of prefixes is the length of the network prefix . although CIDR No subnet , However, some networks still use subnet partition and subnet mask , therefore CIDR The address mask used can also continue to be called a subnet mask .CIDR What you mean by not using subnets is ：CIDR Not in 32 The bit address indicates several bits as subnet fields , But assigned to a CIDR The unit of the address block , We can still divide some subnets according to our needs . These subnets also have only one network prefix and host number field , But the network prefix of subnet is longer than that of the whole unit . for example , A unit is assigned to an address block /20, We can continue to divide it into 8 Subnet （ Borrow from host number 3 Bit to divide the subnet ）. At this time, the network prefix of each subnet becomes 23 position .
Due to a CIDR The address block has many addresses , So use... In the routing table CIDR Address block to find the destination network . This aggregation of addresses is often called routing aggregation , It enables an entry in the routing table to represent many routes of the original traditional classification address , Reduce the exchange of routing information between routers , Improved the performance of the Internet . Routing aggregation is also known as forming a hypernetwork .
Longest path match
In the use of CIDR when , Each line in the router is made up of “ network prefix ” and “ Next hop address ” form . however , When looking up the routing table, you may get more than one match , This brings up a problem ： Which route should be selected from the matching results ？ The answer is ： Select the route with the longest network prefix , This is called longest prefix matching , Because the longer the network prefix , The smaller the address block is , The more specific the route is .
Using binary clues to find routing tables
Because to find the route with the longest prefix , So it makes the search process of routing table more complicated . When the number of items in the routing table is large , How to reduce the lookup time of routing table becomes a very important problem , Routing table must use good data structure and advanced fast search algorithm .
The simplest lookup algorithm for routing tables without class addressing is ： Loop through all possible prefixes . for example ： Given a destination address D, For each possible network prefix length M, Router from D To extract from M Network prefix of one bit , Look up the network prefix in the routing table , The longest match found corresponds to the route to be found . The obvious disadvantage of this algorithm is that the number of searches is too much . For a more efficient search , Generally, routing tables without classification and addressing are stored in a hierarchical data structure , And then search from top to bottom by hierarchy , The most common one is binary cues . Here is an example to illustrate the structure of binary cues .
To simplify the structure of binary cues , You can start by finding out which one corresponds to each IP The unique prefix of the address . The only prefix is ： All of the... In the table IP In the address , The prefix is unique . When searching , As long as it matches the unique prefix . The depth from top to bottom of the root node of the binary clue is at most 32 layer , Each layer corresponds to IP One of the addresses . One IP The rules for storing binary clues in addresses are very simple , First check IP First on the left of the address , If 0, The node of the first layer is just below the left of the root node , If 1, On the bottom right , Check the second digit of the address , Construct the nodes of the second layer , By analogy , Until the last bit of the unique prefix .