# Iptrie
[![Test](https://github.com/hertogp/iptrie/actions/workflows/elixir.yml/badge.svg)](https://github.com/hertogp/iptrie/actions/workflows/elixir.yml)
[![Module Version](https://img.shields.io/hexpm/v/iptrie.svg)](https://hex.pm/packages/iptrie)
[![Hex Docs](https://img.shields.io/badge/hex-docs-lightgreen.svg)](https://hexdocs.pm/iptrie/)
[![License](https://img.shields.io/hexpm/l/iptrie.svg)](https://github.com/hertogp/iptrie/blob/master/LICENSE)
[![Last Updated](https://img.shields.io/github/last-commit/hertogp/iptrie.svg)](https://github.com/hertogp/iptrie/commits/master)
[![Total Download](https://img.shields.io/hexpm/dt/iptrie.svg)](https://hex.pm/packages/iptrie)
<!-- @MODULEDOC -->
IP lookup, with longest prefix match, for IPv4, IPv6 prefixes (and others).
`Iptrie` manages multiple `Radix` trees, one for each type of prefix used as
determined by their `maxlen` property after encoding it as a `t:Pfx.t/0`
struct. That way, IPv4 prefixes (`maxlen: 32`) use a different radix tree as
opposed to IPv6 (`maxlen: 128`) or other types.
Iptrie has a bias towards IPv4, IPv6, EUI-48 and EUI-64, since it uses `Pfx` to
convert arguments to a `t:Pfx.t/0` struct. Other types of prefixes will
require the actual `t:Pfx.t/0` structs as arguments for the various Iptrie
functions.
Like `Pfx`, Iptrie tries to mirror the representation of results to the
arguments given, if possible.
## IPv4/IPv6
iex> ipt = new()
...> |> put("1.2.3.0/24", "v4")
...> |> put("128.0.0.0/8", "v4-128")
...> |> put("acdc:1975::/32", "T.N.T")
...> |> put("acdc:1978::/32", "Powerage")
...> |> put("0.0.0.0/0", "v4 default")
...> |> put("::/0", "no dynamite")
iex>
iex> # 3 longest prefix matches that find the same prefix
iex> lookup(ipt, "1.2.3.128")
{"1.2.3.0/24", "v4"}
iex> lookup(ipt, {{1, 2, 3, 128}, 32})
{{{1, 2, 3, 0}, 24}, "v4"}
iex>
iex> lookup(ipt, %Pfx{bits: <<1, 2, 3, 128>>, maxlen: 32})
{%Pfx{bits: <<1, 2, 3>>, maxlen: 32}, "v4"}
iex>
iex> lookup(ipt, "acdc:1975::")
{"acdc:1975:0:0:0:0:0:0/32", "T.N.T"}
iex>
iex> # separate trees, separate default "routes"
iex> lookup(ipt, "10.11.12.13")
{"0.0.0.0/0", "v4 default"}
iex> lookup(ipt, "abba::")
{"0:0:0:0:0:0:0:0/0", "no dynamite"}
iex>
iex> # visualize the IPv4 & IPv6 radix trees
iex> kv32 = fn {k, v} -> "#{Pfx.new(k, 32)}<br/>#{v}" end
iex> radix(ipt, 32)
...> |> Radix.dot(label: "IPv4", kv_tostr: kv32)
...> |> (&File.write("assets/ipv4.dot", &1)).()
iex> kv128 = fn {k, v} -> "#{Pfx.new(k, 128)}<br/>#{v}" end
iex> radix(ipt, 128)
...> |> Radix.dot(label: "IPv6", kv_tostr: kv128)
...> |> (&File.write("assets/ipv6.dot", &1)).()
The radix trees in the example above look like this:
![ipv4](assets/ipv4.dot.png) ![ipv6](assets/ipv6.dot.png)
## Others
Iptrie can also be used to do longest prefix match lookup for other types of
prefixes, like e.g. MAC addresses:
iex> ipt = new()
...> |> put("00-22-72-00-00-00/24", "American Micro-Fuel Device")
...> |> put("00-d0-ef-00-00-00/24", "IGT")
...> |> put("08-61-95-00-00-00/24", "Rockwell Automation")
iex>
iex> lookup(ipt, "00-d0-ef-aa-bb-cc")
{"00-D0-EF-00-00-00/24", "IGT"}
iex>
iex> # longest match for partial prefix
iex> lookup(ipt, "08-61-95-11-22-00/40") |> elem(1)
"Rockwell Automation"
iex>
iex> kv48 = fn {k, v} -> "#{Pfx.new(k, 48)}<br/>#{v}" end
iex> radix(ipt, 48)
...> |> Radix.dot(label: "MAC OUI", kv_tostr: kv48)
...> |> (&File.write("assets/mac.dot", &1)).()
![mac](assets/mac.dot.png)
`Iptrie` recognizes EUI-48 and EUI-64 prefixes. Note that EUI-64 using ':' as
punctuation might come out as an IPv6, in which case `Pfx.from_mac/1` should be
used to create a prefix before putting it in the trie.
Since prefixes are stored in specific radix trees based on the `maxlen` of
given prefix, you could also mix IPv4, IPv6, EUI-48, EUI-64 prefixes and
possibly others, in a single Iptrie.
## Examples
Summarize an Iptrie containing a list of full length prefixes within a /24,
with 1 missing address:
iex> new(for x <- 0..255, do: {"1.1.1.#{x}", x})
...> |> delete("1.1.1.128")
...> |> prune(fn _ -> {:ok, 0} end, recurse: true)
...> |> to_list()
...> |> Enum.map(fn {pfx, _v} -> {"#{pfx}", "Range #{Pfx.first(pfx)} - #{Pfx.last(pfx)}"} end)
[
{"1.1.1.0/25", "Range 1.1.1.0 - 1.1.1.127"},
{"1.1.1.129", "Range 1.1.1.129 - 1.1.1.129"},
{"1.1.1.130/31", "Range 1.1.1.130 - 1.1.1.131"},
{"1.1.1.132/30", "Range 1.1.1.132 - 1.1.1.135"},
{"1.1.1.136/29", "Range 1.1.1.136 - 1.1.1.143"},
{"1.1.1.144/28", "Range 1.1.1.144 - 1.1.1.159"},
{"1.1.1.160/27", "Range 1.1.1.160 - 1.1.1.191"},
{"1.1.1.192/26", "Range 1.1.1.192 - 1.1.1.255"}
]
Find the more specific entries in an Iptrie for a given search prefix
iex> new()
...> |> put("acdc:1975::/32", "TNT")
...> |> put("acdc:1977::/32", "LTBR")
...> |> put("abba:1975::/32", "RING")
...> |> more("acdc::/16")
...> |> Enum.map(fn {p, v} -> {"#{p}", v} end)
[
{"acdc:1977:0:0:0:0:0:0/32", "LTBR"},
{"acdc:1975:0:0:0:0:0:0/32", "TNT"}
]
Find the less specific entries in an Iptrie for a given search prefix
iex> new()
...> |> put("1.1.1.0/24", 0)
...> |> put("1.1.1.0/25", 1)
...> |> put("1.1.1.0/26", 2)
...> |> put("1.1.1.0/30", 3)
...> |> put("1.1.1.128/25", 4)
...> |> less("1.1.1.3")
...> |> Enum.map(fn {pfx, v} -> {"#{pfx}", v} end)
[
{"1.1.1.0/30", 3},
{"1.1.1.0/26", 2},
{"1.1.1.0/25", 1},
{"1.1.1.0/24", 0}
]
<!-- @MODULEDOC -->
## Installation
[Iptrie](https://hexdocs.pm/iptrie) can be installed by adding `:iptrie` to your
list of dependencies in `mix.exs`:
```elixir
def deps do
[
{:iptrie, "~> 0.6.0"}
]
end
```
## Copyright and License
Copyright (c) 2021 hertogp
The source code is licensed under the [MIT License](./LICENSE.md).