title: What is the most efficient way to match the IP addresses to huge route entries?
body: <p>Imagining there is a firewall, and the system administrator blocked many subnets, perhaps all subnets of a specific country.</p>
  
  <p>For example:</p>
  
  <pre><code>192.168.2.0 / 255.255.255.0
  223.201.0.0 / 255.255.0.0
  223.202.0.0 / 255.254.0.0
  223.208.0.0 / 255.252.0.0
  ....
  </code></pre>
  
  <p>To determine whether a IP address have been blocked, the firewall may use the algorithm below.</p>
  
  <pre><code>func blocked(ip)
      foreach subnet in blocked_subnets
          if in_subnet(subnet, ip)
              return true
      return false
  </code></pre>
  
  <p>But, the algorithm needs too much time to run, the time complexity is O(n). If the route table contains too many entries, the network will become almost unavailable.</p>
  
  <p>Is there a more efficient way to match the IP addresses to huge route entries? It is based on some kinds of trees/graphs (Trie?) I guess. I have read something about Longest prefix match and Trie but didn't get the point.</p>