Question description:
In the router, generally speaking, the forwarding module adopts the maximum preface matching principle for the destination port search, as follows:
ip address and subnet address matching:
IP address and the sub -network address with the mask for and after the AND operation, the value obtained is the same as that of the subnet address, then the IP address matches the subnet.
, for example:
IP address: 192.168.1.100
8 网: 192.168.1.0/255.255.255.0, of which 192.168.1.0 is the address of the subnet, and 255.255.255.0 is the subnet mask.
192.168.1.100 & 255.255.255.0 = 192.168.1.0, then the IP and Zi.com 192.168.1.0 match
IP address: 192.168.1.100
19 网: 192.168.1.128/255.255.255.192
192.168.1.100 & 255.255.255.192 = 192.168.1.64, then the IP and Ziwang 192.168.1.128 will not match
Maximum prefix matching:
Any IPv4 address can be regarded as a binary number of 32bit. For example, 192.168.1.100 can be expressed as: 11000000.10101000.00000001.01100100.
192.168.1.0 can be expressed as 11000000.10101000.00000001.00000000
The maximum preliminary matching requires the IP address and the matching of the sub -network address, as much as possible from left to right from left to right (the longest is the longest from left to the right network address). for example:
ip address 192.168.1.100, and at the same time, it matches the subnet 192.168.1.0/255.255.255.0 and Ziwang 192.168.1.64/255.255.255.192,,
but for Ziwang 192.168.1.64/255.255.255.192, the matching digit reaches 26 bits, more than the 24 -bit of the sub -net 192.168.1.0/2555.255.0, and 24 bits.
Therefore, 192.168.1.100’s largest precursor network was 192.168.1.64/255.255.255.192.
Please program to implement the above -mentioned maximum preparation algorithm.
Requires the implementation function:
void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n)
[Input] IP_ADDR: IP address string, strict guarantee is a string of legal IPv4 address form
net_addr_array: The sub -network address list, each string represents a subnet, including the subnet address and mask,
The form of expression is as mentioned above.
legal form string; if you read the empty string, it means that the sub -network address list is over
[Output] N: The maximum prefix matching network corresponds to the corresponding lower label value in the*net_addr_array [] array. If no matching return -1
Example
Input:
ip_addr = “192.168.1.100”
net_addr_array[] =
{
“192.168.1.128/255.255.255.192”,
“192.168.1.0/255.255.255.0”,
“192.168.1.64/255.255.255.192”,
“0.0.0.0/0.0.0.0”,
“”
}
Output: n = 2
This question is really troublesome, I have been doing it for a long time ~ The high level is difficult
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n) 5 { 6 int i,j,ip[4],mask[4],l,len,net[4],sum; 7 const char *p; 8 i = 0; 9 l = 0; 10 sum = 0; 11 len = 0; 12 *n = -1; 13 p = ip_addr; 14 while (*p != '\0') 15 { 16 j = 0; 17 while (*p >= '0' && *p <= '9') 18 { 19 int k = *p - '0'; 20 j = j * 10 + k; 21 p++; 22 } 23 if (*p == '\0'){ 24 ip[l++] = j; 25 break; 26 } 27 ip[l++] = j; 28 p++; 29 } 30 l = 0; 31 printf("ip:\n"); 32 for (l=0; l < 4; l++) 33 printf("%d ",ip[l]); 34 printf("\n"); 35 l = 0; 36 while (*net_addr_array[i] != '\0' ) 37 { 38 p = net_addr_array[i]; 39 while (*p != '/') 40 { 41 j = 0; 42 while (*p >= '0' && *p <= '9') 43 { 44 int k = *p - '0'; 45 j = j * 10 + k; 46 p++; 47 } 48 net[l++] = j; 49 if (*p == '/') 50 break; 51 p++; 52 } 53 p++; 54 l = 0; 55 while (*p != '\0') 56 { 57 j = 0; 58 while (*p >= '0' && *p <= '9') 59 { 60 int k = *p - '0'; 61 j = j * 10 + k; 62 p++; 63 } 64 if (*p == '\0'){ 65 mask[l++] = j; 66 break; 67 } 68 mask[l++] = j; 69 p++; 70 } 71 printf("\n"); 72 for (l=0; l < 4; l++) 73 printf("%d ",net[l]); 74 printf("/ "); 75 for (l=0; l < 4; l++) 76 printf("%d ",mask[l]); 77 printf("\ncal ip & mask:\n"); 78 for (l=0; l < 4; l++) 79 { 80 printf(" %d ",ip[l]&mask[l]); 81 if ((ip[l]&mask[l]) != net[l]) 82 break; 83 int temp = mask[l]; 84 while(temp) 85 { 86 87 if (temp & 0x00000001){ 88 sum++; 89 } 90 temp = temp >> 1; 91 } 92 } 93 if (l >= 4) 94 { 95 printf("\ n prefix length:%d",sum); 96 if (len <= sum) 97 { 98 *n = i; 99 len = sum; 100 } 101 } 102 sum = 0; 103 i++; 104 l = 0; 105 printf("\n"); 106 } 107 printf("\n"); 108 } 109 int main() 110 { 111 char ip_addr[20] = "192.168.1.100"; 112 113 //ip_addr[13] = '\0'; 114 115 const char *net_addr_array[100] = 116 117 { 118 "192.168.1.128/255.255.255.192", 119 "192.168.1.0/255.255.255.0", 120 "192.168.1.64/255.255.255.192", 121 "0.0.0.0/0.0.0.0", 122 "" 123 }; 124 int *n; 125 n = (int*)malloc(sizeof(int)); 126 max_prefix_match(ip_addr, net_addr_array, n); 127 printf("n = %d\n",*n); 128 129 }
Reprinted: https://www.cnblogs.com/george-cw/p/3940601.html