一种IP命中交叉网段的查找算法

tammypi tammypi
2019-05-22 09:31
202
0

1.问题描述

假设有一堆网段,如下所示:

192.168.1.100-192.168.1.120,AAA,id1

192.168.1.50-192.168.1.150,BBB,id2

10.67.1.1/24,CCC,id3

10.67.1.1,DDD,id4

10.67.1.0,EEE,id5

 

第一列是单IP或者网段,第二列是设备hash,第三列是这个IP或者网段的唯一标志。IP与网段、网段与网段之间是可以有交叉的,比如192.16.1.100-192.168.1.120和192.168.1.50-192.168.1.150就是存在一部分交叉的。

 

要求,当一个日志过来过来时,需要得到它里面的IP的唯一ID,比如10.67.1.125过来,我们就知道它是属于10.67.1.1/24网段,那么就是用id3来标志它;比如10.67.1.1过来时,我们发现既可以命中10.67.1.1(id4)也可以命中10.67.1.1/24(id3),那么就提取日志里记录的hash值,比如hash是CCC,那么我们就知道它的唯一ID应该是id3。

 

2.解题思路

1.首先将网段拆开为多个不交叉的段,并且记录每个段对应的相关信息

2.在一个日志过来时,提取其IP在网段里进行二分查找,当查找到的相关信息唯一时,直接返回;当查找到的相关信息不唯一时,使用hash值进行比对,从而拿到命中值

2.1网段拆分为不交叉段

对于一组数据,如下所示:

s1,e1,id1

s2,e2,id2

s3,e3,id3

s和e分别代表起始数值,id为唯一标志。它们的范围如下图所示:

我们可以按数值的大小进行排序,注意,如果两个值相等的情况下,起始值排在结束值之前,排序之后如下所示:

s1,s2,s3,e1,e2,e3

分析的过程如下图所示:

step1,得到的结果应该是:[s1,s2-1]  id1

在step2,得到的结果应该是:[s2,s3-1]  id1,id2

在step3,得到的结果应该是:[s3,e1]   id1,id2,id3

在step4,得到的结果应该是:[e1+1,e2]   id2,id3

在step5,得到的结果应该是:[e2+1,e3]  id3

那么总结的处理过程如下:

从排序后的数值list里拿到两个元素n1,n2,用一个全局的S记录id值

  • 如果n1是s类型,则a=n1,且将n1对应的id加入S中;如果n1是e类型,则a=n1+1,则将n1对应的id从S中移除
  • 如果n2是s类型,则b=n2-1;如果n2是e类型,则b=n2
  • 如果a<=b且S不为空,则对于[a,b]以及S进行输出

以此循环,直至对于list处理结束。

核心代码如下所示:

public List<OutputNode> init(List<IpRangeAsset> list){
		List<GapRangeNode> gapRangeNodeList = new ArrayList<>();
		for(int i=0;i<list.size();i++){
			gapRangeNodeList.add(new GapRangeNode(list.get(i).getStartIpInt(),i,false));
			gapRangeNodeList.add(new GapRangeNode(list.get(i).getEndIpInt(),i,true));
		}

		Collections.sort(gapRangeNodeList, new Comparator<GapRangeNode>() {
			@Override
			public int compare(GapRangeNode o1, GapRangeNode o2) {
				return o1.getNumber()-o2.getNumber()<0||(o1.getNumber()==o2.getNumber()&&o2.isEnd())?-1:1;
			}
		});

		OutputNode outputNode = new OutputNode(-1,-1);
		List<OutputNode> resultList = new ArrayList<OutputNode>();
		for(int i=0;i<gapRangeNodeList.size()-1;i++){
			GapRangeNode n1 = gapRangeNodeList.get(i);
			GapRangeNode n2 = gapRangeNodeList.get(i+1);
			long n = -1;
			long m = -1;
			if(n1.isEnd()){
				n = n1.getNumber()+1;
				outputNode.removeAssetIndex(list.get(n1.getIndex()));
			}else{
				n = n1.getNumber();
				outputNode.addAssetIndex(list.get(n1.getIndex()));
			}
			if(n2.isEnd()){
				m = n2.getNumber();
			}else{
				m = n2.getNumber() - 1;
			}
			if(n <= m && outputNode.getAssetIndexSet().size() > 0){
				OutputNode copyNode = new OutputNode(n,m);
				Iterator<IpRangeAsset> iterator = outputNode.getAssetIndexSet().iterator();
				while(iterator.hasNext()){
					copyNode.addAssetIndex(iterator.next());
				}
				resultList.add(copyNode);
			}
		}
		return resultList;
	}

网段拆分的效果如下:

 

2.2二分查找

由于已经将网段拆分成了不相交的网段,所以可以直接将网段按照从小到大进行排序,得到一个有序的数组。然后使用二分查找来找寻IP所属的网段,如果命中的网段对应着多个结果,那么使用hash找到对应的结果。在IP范围数目为100万的情况下,如果使用二分查找,最坏的比对次数为math.log(1000000,2)约等于20次,而直接顺序查找最坏的比对次数为1000000次。

二分查找的核心代码如下:

public IpRangeAsset search(long ipint,String devHash,List assetList){
		int low = 0;
		int high = assetList.size()-1;
		IpRangeAsset ipRangeAsset = null;
		while(low <= high){
			int index = (low+high)/2;
			if(ipint > assetList.get(index).getEnd()){
				low = index + 1;
			}else if(ipint < assetList.get(index).getStart()){
				high = index - 1;
			}else{
				if(assetList.get(index).getAssetIndexSet().size() == 1){
					ipRangeAsset = assetList.get(index).getAssetIndexSet().iterator().next();
				}else{
					Iterator iterator = assetList.get(index).getAssetIndexSet().iterator();
					while(iterator.hasNext()){
						IpRangeAsset entry = (IpRangeAsset) iterator.next();
						if(entry.getDevHash().equals(devHash)){
							ipRangeAsset = entry;
							break;
						}
					}
				}
				break;
			}
		}
		return ipRangeAsset;
	}

3.性能对比

对于IP、IP范围数目为100万的情况下,对于50000个IP进行查找的耗时进行了比对,比对结果如下所示:

二分查找耗时为27ms,而普通查找为35974ms,耗时大概相差3个数量级,差距还是比较明显的。

 

下面附上完整代码:

IpRangeAsset.java
package com.formatengine.asset.v4;
import com.alibaba.fastjson.JSONObject;
import net.ripe.commons.ip.Ipv4;
import net.ripe.commons.ip.Ipv4Range;
import java.io.Serializable;
import java.util.HashMap;
import java.util.Map;

/**
 * Created by dell on 2019/5/17.
 * 主机型资产和网段型资产对应的类
 */
public class IpRangeAsset implements Serializable{
	private String startIp;
	private String endIp;
	private String devHash;
	private Long startIpInt;
	private Long endIpInt;
	//地理位置、资产id等增强信息存储之处
	private Map additional = new HashMap();

	public IpRangeAsset(String ip,String devHash,Map additional){
		if(ip.contains("/")){
			String[] tempIps = ip.split("/");
			this.startIp = Ipv4.of(tempIps[0]).lowerBoundForPrefix(Integer.valueOf(tempIps[1])).toString();
			Ipv4Range ipv4Range = Ipv4Range.parse(startIp+"/"+tempIps[1]);
			this.endIp = ipv4Range.end().toString();
			this.startIpInt = ipv4Range.start().asBigInteger().longValue();
			this.endIpInt = ipv4Range.end().asBigInteger().longValue();
		}else if(ip.contains("-")){
			Ipv4Range ipv4Range = Ipv4Range.parse(ip);
			this.startIp = ipv4Range.start().toString();
			this.startIpInt = ipv4Range.start().asBigInteger().longValue();
			this.endIp = ipv4Range.end().toString();
			this.endIpInt = ipv4Range.end().asBigInteger().longValue();
		}else{
			this.startIp = ip;
			this.endIp = ip;
			this.devHash = devHash;
			this.additional = additional;
			startIpInt = Ipv4.of(ip).asBigInteger().longValue();
			endIpInt = Ipv4.of(ip).asBigInteger().longValue();
		}
		this.devHash = devHash;
		this.additional = additional;
	}

	public String getStartIp() {
		return startIp;
	}

	public void setStartIp(String startIp) {
		this.startIp = startIp;
	}

	public String getDevHash() {
		return devHash;
	}

	public void setDevHash(String devHash) {
		this.devHash = devHash;
	}

	public String getEndIp() {
		return endIp;
	}

	public void setEndIp(String endIp) {
		this.endIp = endIp;
	}

	public Long getStartIpInt() {
		return startIpInt;
	}

	public void setStartIpInt(Long startIpInt) {
		this.startIpInt = startIpInt;
	}

	public Long getEndIpInt() {
		return endIpInt;
	}

	public void setEndIpInt(Long endIpInt) {
		this.endIpInt = endIpInt;
	}

	public Map getAdditional() {
		return additional;
	}

	public void setAdditional(Map additional) {
		this.additional = additional;
	}

	public String toString(){
		return JSONObject.toJSONString(this);
	}
}
OutputNode.java
package com.formatengine.asset.v4;
import com.alibaba.fastjson.JSONObject;
import net.ripe.commons.ip.Ipv4;

import java.io.Serializable;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by dell on 2019/5/20.
 * 用于进行资产范围切分输出的model
 */
public class OutputNode implements Serializable{
	private long start;
	private long end;
	private String startIp;
	private String endIp;
	private Set indexAssetSet = null;

	public OutputNode(long start, long end) {
		this.start = start;
		this.end = end;
		this.indexAssetSet = new HashSet();
		if(this.start != -1){
			this.startIp = Ipv4.of(start).toString();
		}
		if(this.end != -1){
			this.endIp = Ipv4.of(end).toString();
		}
	}

	public long getStart() {
		return start;
	}

	public void setStart(long start) {
		this.start = start;
		this.startIp = Ipv4.of(start).toString();
	}

	public long getEnd() {
		return end;
	}

	public void setEnd(long end) {
		this.end = end;
		this.endIp = Ipv4.of(end).toString();
	}

	public Set getAssetIndexSet() {
		return indexAssetSet;
	}

	public void setAssetIndexSet(Set indexSet) {
		this.indexAssetSet = indexSet;
	}

	public void removeAssetIndex(IpRangeAsset val){
		this.indexAssetSet.remove(val);
	}

	public void addAssetIndex(IpRangeAsset val){
		this.indexAssetSet.add(val);
	}

	public String getStartIp() {
		return startIp;
	}

	public String getEndIp() {
		return endIp;
	}

	public String toString(){
		return JSONObject.toJSONString(this);
	}
}
GapRangeNode.java
package com.formatengine.asset.v4;

import java.io.Serializable;

/**
 * Created by dell on 2019/5/20.
 * 用于进行资产范围拆分的model
 */
public class GapRangeNode implements Serializable{
	private long number;
	private int index;
	private boolean end;

	public GapRangeNode(long number, int index, boolean end) {
		this.number = number;
		this.index = index;
		this.end = end;
	}

	public long getNumber() {
		return number;
	}

	public void setNumber(long number) {
		this.number = number;
	}

	public int getIndex() {
		return index;
	}

	public void setIndex(int index) {
		this.index = index;
	}

	public boolean isEnd() {
		return end;
	}

	public void setEnd(boolean end) {
		this.end = end;
	}
}
BinarySearch.java
package com.formatengine.asset.v4;
import net.ripe.commons.ip.Ipv4;

import java.io.Serializable;
import java.util.*;
/**
 * Created by dell on 2019/5/17.
 * 二分查找类
 */
public class BinarySearch implements Serializable{
	public List init(List list){
		List gapRangeNodeList = new ArrayList<>();
		for(int i=0;i() {
			@Override
			public int compare(GapRangeNode o1, GapRangeNode o2) {
				return o1.getNumber()-o2.getNumber()<0||(o1.getNumber()==o2.getNumber()&&o2.isEnd())?-1:1;
			}
		});

		OutputNode outputNode = new OutputNode(-1,-1);
		List resultList = new ArrayList();
		for(int i=0;i 0){
				OutputNode copyNode = new OutputNode(n,m);
				Iterator iterator = outputNode.getAssetIndexSet().iterator();
				while(iterator.hasNext()){
					copyNode.addAssetIndex(iterator.next());
				}
				resultList.add(copyNode);
			}
		}
		return resultList;
	}


	public IpRangeAsset search(long ipint,String devHash,List assetList){
		int low = 0;
		int high = assetList.size()-1;
		IpRangeAsset ipRangeAsset = null;
		while(low <= high){
			int index = (low+high)/2;
			if(ipint > assetList.get(index).getEnd()){
				low = index + 1;
			}else if(ipint < assetList.get(index).getStart()){
				high = index - 1;
			}else{
				if(assetList.get(index).getAssetIndexSet().size() == 1){
					ipRangeAsset = assetList.get(index).getAssetIndexSet().iterator().next();
				}else{
					Iterator iterator = assetList.get(index).getAssetIndexSet().iterator();
					while(iterator.hasNext()){
						IpRangeAsset entry = (IpRangeAsset) iterator.next();
						if(entry.getDevHash().equals(devHash)){
							ipRangeAsset = entry;
							break;
						}
					}
				}
				break;
			}
		}
		return ipRangeAsset;
	}

	public IpRangeAsset normalSearch(long ipint,String devHash,List assetList){
		IpRangeAsset ipRangeAsset = null;
		for(int index=0;index= ipint && assetList.get(index).getEnd() <= ipint){
				if(assetList.get(index).getAssetIndexSet().size() == 1){
					ipRangeAsset = assetList.get(index).getAssetIndexSet().iterator().next();
				}else{
					Iterator iterator = assetList.get(index).getAssetIndexSet().iterator();
					while(iterator.hasNext()){
						IpRangeAsset entry = (IpRangeAsset) iterator.next();
						if(entry.getDevHash().equals(devHash)){
							ipRangeAsset = entry;
							break;
						}
					}
				}
				break;
			}
		}
		return ipRangeAsset;
	}

	public static void main(String[] args){
		List list = new ArrayList();
		list.add(new IpRangeAsset("192.168.1.100-192.168.1.120","AAA",null));
		list.add(new IpRangeAsset("192.168.1.50-192.168.1.150","BBB",null));
		list.add(new IpRangeAsset("10.67.1.1/24","CCC",null));
		list.add(new IpRangeAsset("10.67.1.1","DDD",null));
		list.add(new IpRangeAsset("10.67.1.255","EEE",null));
		list.add(new IpRangeAsset("10.67.1.254-10.67.1.255","FFF",null));
		list.add(new IpRangeAsset("10.67.1.0","HHH",null));
		Random random = new Random();
		//100万个资产
		for(int i=0;i<1000000;i++){
			String ipStart = String.valueOf(random.nextInt(255));
			String ipEnd = String.valueOf(random.nextInt(255));
			String randomStart = ipStart + "." + ipEnd + ".1.100";
			String randomEnd = ipStart + "." + ipEnd + ".1.255";
			list.add(new IpRangeAsset(randomStart + "-" + randomEnd, "", null));
		}

		BinarySearch binarySearch = new BinarySearch();
		List assetList = binarySearch.init(list);

		long startTime = System.currentTimeMillis();
		for(int i=0;i<50000;i++){
			String ip = "10.67.1.0";
			binarySearch.search(Ipv4.of(ip).asBigInteger().longValue(),"DDD",assetList);
		}

		long endTime = System.currentTimeMillis();
		System.out.println("binary search waste:"+(endTime-startTime)+"ms");

		long startTime1 = System.currentTimeMillis();
		for(int i=0;i<50000;i++){
			String ip = "10.67.1.0";
			binarySearch.normalSearch(Ipv4.of(ip).asBigInteger().longValue(), "DDD", assetList);
		}
		long endTime1 = System.currentTimeMillis();

		System.out.println("normal search waste:"+(endTime1-startTime1)+"ms");
	}
}

IP和大整型转换的依赖:

  net.ripe.commons
  commons-ip-math
  1.23

发表评论

验证码: