0

我正在寻找一个好的算法（或代码，如果你说得比英语好）来执行以下操作：

对于给定的 IP 范围（例如 1.1.1.1 - 1.1.2.247），找到包含指定范围内所有 IP 的子网/地址的最小组合。忽略广播、子网 0 限制和网络类。

例子：

  • 对于 1.1.1.1 - 1.1.2.1 你会得到 {1.1.1.1/24, 1.1.2.1} 比 {1.1.1.1, 1.1.1.2, ..., 1.1.1.255, 1.1.2.1} 更好/更小
  • 对于 1.1.1.12 - 1.1.1.31，您会得到 {1.1.1.12/30, 1.1.1.16/28}，它比 {1.1.1.12, 1.1.1.13, 1.1.1.14, 1.1.1.15, 1.1 更好/更小。 1.16/28}

出于好奇，用例是使用 Openflow 协议将任意范围的源/目标 IP 上的网络流量与最少的流量匹配。这种优化的需求源于硬件交换机/路由器对这些流配置的空间有限，并且需要相对较长的时间来编程/修改。

4

1 回答 1

0

如果您将 IP 地址视为 32 位数字，那么这就是找​​到一组区间的问题，该区间的并集是您需要填充的 IP 地址范围。查看您的第一个示例，我将假设当您说 0.1 时，您允许间隔包含 .0，因为 1.1.1.1/24 是 1.1.1.0/24 的地址集。

将 IP 地址视为数字，我将从最小的数字开始，并从该数字开始寻找最大的子网，该数字不超过最终 IP 地址。将其作为您的第一个子网并计算出刚刚覆盖的范围末尾的 IP 地址。然后重新开始寻找从该 IP 地址开始的最大子网，并且不会走得太远 - 依此类推。

这是最优的，因为可用的子网都以 2 的幂排列。要使用覆盖 2^n 个地址的大型子网，您必须移动到低 n 位已清除的起始地址。如果您的清除位少于 n 位，那么执行此操作的方法是在每个阶段选择可能的最大步长，并且每个步长都会清除当前地址中的最低设置位。

于 2014-06-11T04:33:07.077 回答