为 java 实现 IPv4 最长前缀查找

Question

我正在实施的项目的想法是编写一个函数/方法，当给定一个 IPv4 地址时，通过将最长前缀匹配规则应用于给定的转发表来找到正确的传出接口。我想到了一个线性搜索：对于每个要路由的地址，它检查转发表中的每个条目是否匹配，并跟踪哪个匹配条目具有最长的前缀。但我不知道如何将其实现到我的代码中。

package lpm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class LongestPrefixMatcher {
    
    public Map<Integer, Byte> prefixmap = new HashMap<>();
    public Map<Integer, Integer> portmap = new HashMap<>();

    public LongestPrefixMatcher() {

    }

    /**
     * Looks up an IP address in the routing tables
     *
     * @param ip The IP address to be looked up in integer representation
     * @return The port number this IP maps to
     */
    public int lookup(int ip) {
        byte maxprefix = 0;
        int maxport = -1;
        for (int address : prefixmap.keySet()) {
            //the first prefix number of bits in address matches with the first pref bits in ip
            if (prefixmap.containsKey(ip)) {
                if ((address >>> (prefixmap.get(ip))) == (ip >>> (prefixmap.get(ip)))) {
                    if (prefixmap.get(ip) > maxprefix) {
                        maxprefix = prefixmap.get(ip);
                        maxport = portmap.get(ip);
                    }
                }
            }
        }
        return maxport;
    }

    /**
     * Adds a route to the routing tables
     *
     * @param ip           The IP the block starts at in integer representation
     * @param prefixLength The number of bits indicating the network part
     *                     of the address range (notation ip/prefixLength)
     * @param portNumber   The port number the IP block should route to
     */
    public void addRoute(int ip, byte prefixLength, int portNumber) {
        prefixmap.put(ip, prefixLength);
        portmap.put(ip, portNumber);
    }

    

    /**
     * Converts an integer representation IP to the human readable form
     *
     * @param ip The IP address to convert
     * @return The String representation for the IP (as xxx.xxx.xxx.xxx)
     */
    private String ipToHuman(int ip) {
        return Integer.toString(ip >> 24 & 0xff) + "." +
                Integer.toString(ip >> 16 & 0xff) + "." +
                Integer.toString(ip >> 8 & 0xff) + "." +
                Integer.toString(ip & 0xff);
    }

    /**
     * Parses an IP
     *
     * @param ipString The IP address to convert
     * @return The integer representation for the IP
     */
    private int parseIP(String ipString) {
        String[] ipParts = ipString.split("\\.");

        int ip = 0;
        for (int i = 0; i < 4; i++) {
            ip |= Integer.parseInt(ipParts[i]) << (24 - (8 * i));
        }

        return ip;
    }}

我试过了，但没用。包含 ip、header 和 port（按此顺序）的路由在另一个文件中给出

 1.0.0.0/24  1 1.0.4.0/22  2 1.0.16.0/23 3 1.0.18.0/23 4 1.0.20.0/23 5 1.0.22.0/23 6 1.0.24.0/23 7 1.0.26.0/23 8 1.0.28.0/22 9 1.0.64.0/18 10 1.0.128.0/17    11 1.0.128.0/18    12 1.0.129.0/24    13 1.0.192.0/18    14 1.1.1.0/24  15 1.1.64.0/19 16 1.1.127.0/24    17 1.1.128.0/17    18 1.1.128.0/19    19

如果我的工作中有任何指导或错误点，那就太好了。我得到的错误是该行的 NullPointerException。

if ((address >>> (prefixmap.get(ip))) == (ip >>> (prefixmap.get(ip))))