查询IP地址的ISP

给定一个IP地址，如何查询其所属的ISP，如：中国移动（ChinaMobile），中国电信（ChinaTelecom），中国铁通（ChinaTietong)？

• 现在网上有ISP的IP地址区段可供下载，比如中国移动的IP地址段

  103.20.112.0/22
  103.21.176.0/22
  111.0.0.0/10
  112.0.0.0/10
  117.128.0.0/10
  120.192.0.0/10
  183.192.0.0/10
  211.103.0.0/17
  211.136.0.0/14
  211.140.0.0/15
  211.142.0.0/17
  211.142.128.0/17
  211.143.0.0/16
  218.200.0.0/14
  218.204.0.0/15
  218.206.0.0/15
  221.130.0.0/15
  221.176.0.0/13
  223.112.0.0/14
  223.116.0.0/15
  223.120.0.0/13
  223.64.0.0/11
  223.96.0.0/12
  36.128.0.0/10
  39.128.0.0/10

  上述网络地址是CIDR记法：IP地址/网络id位数，其中IP地址分为两部分

  • 网络id
  • 主机id
  @H_404_43@

  比如，192.168.23.35/21，其子网掩码为11111111 11111111 11111000 00000000即255.255.248.0，网络ID：192.168.00010111

  • ip地址103.20.112.168，发现与103.20.112.0/22前22位相匹配，则此IP地址属于中国移动

  @H_404_43@

  ---

  Trie树实现查询

  Trie树使用公共前缀，降低查询时间，减小了存储空间。为了构建Trie树，将IP地址二进制化，这样Trie树变成了一棵二叉树，左孩子节点为0，右孩子节点为1。叶子节点存储IP地址所对应的ISP。

  Trie树的Java实现

  /* * Trie树，用于存储、检索ip地址 * 叶子节点标记为ip地址对应的ISP */
  public class TrieTree {
       private Node root = null;   //根节点
  
      /*二叉树的节点*/
      private static Node {
          String element;  //非叶子节点为空 叶子节点标记为ISP
          Node[] children; //左孩子节点为0 右孩子节点为1
  
          public Node() {
              element = "";
              children = new Node[2];
              for (int i = 0; i < children.length; i++) {
                  children[i] = null;
              }
          }
      }
  
      TrieTree() {
          root = new Node();
      }   
  
      /*插入ip地址*/
      public void insert(Node root,String ipAddress,String isp) {
          if(ipAddress.length() > 32) {
              System.out.println("ip地址处理错误");
          } else {
              Node crawl = root;
              for(int i=0; i<ipAddress.length(); i++) {
                  int index = (int) ipAddress.charAt(i) - '0';
                  if(crawl.children[index] == null) {
                      crawl.children[index] = new Node();
                  }
                  crawl = crawl.children[index];              
              }
              crawl.element = isp;
          }
      }
  
      insert(String ipAddress,String isp) {
          insert(root,ipAddress,isp);
      }
  
      /* * 检索ip地址，返回其所对应的ISP * 若不在Trie树中，则返回null * */
      public String search(String binaryIP) {
          Node crawl = root;
          0; crawl.element.length() == 0; i++) {
              int) binaryIP.charAt(i) - '0';
              null) {
                  return null;
              }
              crawl = crawl.children[index];
          }
          return crawl.element;
      }
  }

  ---

  IP地址格式化

  下面的class给出两个方法，实现

  • 将IP地址转变成二进制
  • 从CIDR记法的IP地址中得到网络ID部分
  @H_404_43@

  /* * IP地址CIDR记法：network.host/size * 比如：103.20.112.0/22 * 功能：将IP地址转换成其network地址 */
  
  IPFormat {
      /*将ip地址转换成32位的二进制*/
      static String toBinaryNumber(String ipAddress) {
          String[] octetArray = ipAddress.split("\\.");
          String binaryNumber = "";
          for(String str: octetArray) {
              int octet = Integer.parseInt(str,10);
              String binaryOctet = Integer.toBinaryString(octet);
              int bolength = binaryOctet.length();
              if(bolength < 8) {
                  0; i < 8 - bolength; i++) {
                      binaryOctet = '0' + binaryOctet;            //补前导0
                  }
              }
              binaryNumber += (binaryOctet);
          }
          return binaryNumber;
      }
  
      /*获取network地址部分*/
      getNetworkAddress(String cidrAddress) {
          String[] cidrArray = cidrAddress.split("/");
          String binaryNumber = toBinaryNumber(cidrArray[0]);
          int size = Integer.parseInt(cidrArray[1]);
          return binaryNumber.substring(0,size);
      }
  
      /*main方法用于测试*/
      static main(String[] args) {
          String ip = "103.20.112.0/20";
          String bn = getNetworkAddress(ip);
          System.out.println(bn);
      }
  }