现在的位置: 首页 > 综合 > 正文

华为:IP地址匹配 在路由器中,一般来说转发模块采用最大前缀匹配原则进行目的端口查找,具体如下:

2013年11月28日 ⁄ 综合 ⁄ 共 4004字 ⁄ 字号 评论关闭
/**************************************************************************************
IP地址匹配
问题描述:
在路由器中,一般来说转发模块采用最大前缀匹配原则进行目的端口查找,具体如下:
IP地址和子网地址匹配:
IP地址和子网地址所带掩码做AND运算后,得到的值与子网地址相同,则该IP地址与该子网匹配。
比如:
IP地址:192.168.1.100
子网:192.168.1.0/255.255.255.0,其中192.168.1.0是子网地址,255.255.255.0是子网掩码。
192.168.1.100&255.255.255.0 = 192.168.1.0,则该IP和子网192.168.1.0匹配
IP地址:192.168.1.100
子网:192.168.1.128/255.255.255.192
192.168.1.100&255.255.255.192 = 192.168.1.64,则该IP和子网192.168.1.128不匹配
最大前缀匹配:
任何一个IPv4地址都可以看作一个32bit的二进制数,比如192.168.1.100可以表示为:
11000000.10101000.00000001.01100100,
192.168.1.0可以表示为11000000.10101000.00000001.00000000
最大前缀匹配要求IP地址同子网地址匹配的基础上,二进制位从左到右完全匹配的位数尽量多
(从左到右子网地址最长)。
比如:
IP地址192.168.1.100,同时匹配子网192.168.1.0/255.255.255.0和子网192.168.1.64/255.255.255.192,
但对于子网192.168.1.64/255.255.255.192,匹配位数达到26位,多于子网192.168.1.0/255.255.255.0的24位,
因此192.168.1.100最大前缀匹配子网是192.168.1.64/255.255.255.192。
请编程实现上述最大前缀匹配算法。
要求实现函数:
void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n)
【输入】ip_addr:IP地址字符串,严格保证是合法IPv4地址形式的字符串
net_addr_array:子网地址列表,每一个字符串代表一个子网,包括子网地址和掩码,
表现形式如上述,子网地址和子网掩码用’/’分开,严格保证是
合法形式的字符串;如果读到空字符串,表示子网地址列表结束
【输出】n:最大前缀匹配子网在*net_addr_array[]数组中对应的下标值。如果没有匹配返回-1
示例
输入:
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",
""
}
输出:n=2  因为匹配且掩码更长,最大前缀匹配

关于sscanf函数用法总结的两篇文章:

C语言sscanf函数用法总结(一) 正则表达式  

http://blog.csdn.net/shihui512/article/details/8847454

C语言sscanf函数用法总结(二) 正则表达式 

http://blog.csdn.net/shihui512/article/details/8850274

********************************************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int GetBitOne(int num)
{
    int res=0;
    while(num!=0)
    {
        num&=(num-1);
        res++;
    }
    return res;
}
/*从匹配的IP地址中寻找最大前缀匹配,即寻找子网掩码中1的个数最多的*/
void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n)
{
	int ip,subnet_ip,subnet_mask;
	int ip_array[4],subnet_ip_array[4],subnet_mask_array[4];
	int index;
	int i,result,cnt=0;
	int maxi=0;
	sscanf(ip_addr,"%d.%d.%d.%d",&ip_array[0],&ip_array[1],&ip_array[2],&ip_array[3]);
	ip = (ip_array[0]<<24)+(ip_array[1]<<16)+(ip_array[2]<<8)+(ip_array[3]);
	*n =-1;
	for(index = 0;net_addr_array[index][0] != '\0';index++)  //只有空字符串的第一个字符就是'\0'
	{
		sscanf(net_addr_array[index],"%d.%d.%d.%d/%d.%d.%d.%d",
            &subnet_ip_array[0],&subnet_ip_array[1],&subnet_ip_array[2],&subnet_ip_array[3],
            &subnet_mask_array[0],&subnet_mask_array[1],&subnet_mask_array[2],&subnet_mask_array[3]);

		subnet_ip = (subnet_ip_array[0]<<24)+(subnet_ip_array[1]<<16)+(subnet_ip_array[2]<<8)+(subnet_ip_array[3]);
		subnet_mask = (subnet_mask_array[0]<<24)+(subnet_mask_array[1]<<16)+(subnet_mask_array[2]<<8)+(subnet_mask_array[3]);
		if((ip & subnet_mask) == subnet_ip)
		{
			/************统计子网掩码中1的个数***********
			for(i=0;i<sizeof(subnet_mask)*8;i++)
			{
				result = subnet_mask & 1;
				subnet_mask=subnet_mask>>1;
				cnt+=result;
			}
			************统计子网掩码中1的个数***********/
			cnt=GetBitOne(subnet_mask);
			if(cnt>maxi)
			{
				maxi = cnt;
				*n = index;
			}
		}
	}
}
/*******************************************
255 ==1111 1111
192 ==1100 0000  128+64
64  ==0100 0000
128 ==1000 0000
100 ==0110 0100 64+32+4
********************************************/
void  test1()
{
	cout<<"test1 ==========================="<<endl;
	int n;
	const char ip_addr[50] = "192.168.1.100";
	const char *net_addr_array[256]=
	{
		"192.168.1.128/255.255.255.192", //192&100=64!=128 不匹配
		"192.168.1.0/255.255.255.0", // 匹配
		"192.168.1.64/255.255.255.192",  //匹配  掩码更长,最大前缀匹配
		"0.0.0.0/0.0.0.0",
		""
	};
	max_prefix_match(ip_addr,net_addr_array,&n);
	cout<<"n= "<<n<<endl;

}
void  test2()
{
	cout<<"test2 ==========================="<<endl;
	int n;
	const char ip_addr[50] = "192.168.1.100";
	const char *net_addr_array[256]=
	{
		"192.168.1.100/255.255.255.255", //255&100=100 掩码更长,最大前缀匹配
		"192.168.1.0/255.255.255.0", // 匹配
		"192.168.1.64/255.255.255.192",  //匹配  
		"0.0.0.0/0.0.0.0",
		""
	};
	max_prefix_match(ip_addr,net_addr_array,&n);
	cout<<"n= "<<n<<endl;

}
int main()
{
    test1();
    test2();
	return 0;
}
/************************************
test1 ===========================
n= 2
test2 ===========================
n= 0

Process returned 0 (0x0)   execution time : 0.845 s
Press any key to continue.

*************************************/

【上篇】
【下篇】

抱歉!评论已关闭.