0

所以我试图从路由条目中返回一个最佳匹配接口。但是，它并不完全按照我想要的方式工作。我以应有的方式返回了 6 个值中的 5 个，但我很确定路由表中有一百万个条目，我的算法将不起作用。我正在使用二进制搜索来解决这个问题。但是，例如，我要返回的接口的 ipaddress 小于我作为参数传递的 ipaddress，则二进制搜索算法不起作用。结构如下所示：

struct routeEntry_t
{
    uint32_t ipAddr;
    uint32_t netMask;
    int interface;
};
routeEntry_t routing_table[100000];

假设路由表如下所示：

{ 0x00000000, 0x00000000, 1 }, // [0]

{ 0x0A000000, 0xFF000000, 2 }, // [1]

{ 0x0A010000, 0xFFFF0000, 10 }, // [2]

{ 0x0D010100, 0xFFFFFF00, 4 }, // [3]

{ 0x0B100000, 0xFFFF0000, 3 }, // [4]

{ 0x0A010101, 0xFFFFFFFF, 5 }, // [5]

示例输入/输出：

  1. 常规搜索

输入：0x0D010101 输出：4（条目 [3]）

输入：0x0B100505 输出：3（条目 [4]）

  1. 要查找任意地址，它应该转到默认界面。

输入：0x0F0F0F0F 输出：1（条目 [0]）

  1. 要查找与多个条目匹配的地址，请选择最佳匹配。

输入：0x0A010200 输出：10（条目 [2]）

输入：0x0A050001 输出：2（条目 [1]）

输入：0x0A010101 输出：5（条目 [5]）

但我的输出看起来像 2、3、1、10、1、5。我不明白我在哪里搞砸了。你能解释一下我在哪里做错了吗？任何帮助都会很棒。提前致谢。然而，这就是我的算法的样子（假设条目已排序）：

int interface(uint32_t ipAddr)

{ int 开始 = 0;

int end = SIZE-1;

int mid = 0;

vector<int> matched_entries;

vector<int>::iterator it;

matched_entries.reserve(SIZE);

it = matched_entries.begin();


if (start > end)
    return -1;

while (start <= end)
{
    mid = start + ((end-start)/2);

    if (routing_table[mid].ipAddr == ipAddr)
        return routing_table[mid].interface;
    else if (routing_table[mid].ipAddr > ipAddr)
    {
        uint32_t result = routing_table[mid].netMask & ipAddr;
        if (result == routing_table[mid].ipAddr)
        {
            matched_entries.push_back(mid);
        }
        end = mid-1;
    }
    else
    {
        uint32_t result = routing_table[mid].netMask & ipAddr;
        if (result == routing_table[mid].ipAddr)
        {
            matched_entries.insert(it,mid);
        }
        start = mid+1;
    }
}


int matched_ip = matched_entries.back();
if (routing_table[matched_ip].netMask & ipAddr)
    return routing_table[matched_ip].interface;
else
    return routing_table[0].interface;

}

4

2 回答 2

1

“正确”接口是具有最具体网络掩码的条目，其 IP 地址与您的输入在同一子网上。

让我们更详细地看看网络掩码是什么，以及它们是如何工作的。

符号

尽管网络掩码通常以点分十进制或十六进制表示法编写，但 IPv4 网络掩码的二进制表示始终是 32 位；也就是说，它与 IP 地址的长度完全相同。网络掩码总是从零位或多个1位开始，并用位填充0以完成其 32 位长度。当网络掩码应用于 IP 地址时，它们会一点一点地“排列”。1IP 地址中与网络掩码中的位相对应的位确定 IP 地址的网络号；0与网络掩码中的位相对应的那些决定了设备号。

目的

网络掩码用于将地址空间划分为更小的子网。同一子网上的设备可以直接使用 TCP/IP 协议栈相互通信。不同子网上的设备必须使用一个或多个路由器在它们之间转发数据。因为它们将子网相互隔离，所以网络掩码是创建设备逻辑分组的自然方式。例如，公司内的每个位置或部门可能有自己的子网，或者每种类型的设备（打印机、PC等）可能有自己的子网。

示例网络掩码：

255.255.255.128→ FF FF FF 10→1111 1111 1111 1111 1111 1111 1000 0000
此网络掩码指定 IP 地址的前 25 位确定网络号；最后 7 位确定设备编号。这意味着可以有 2 25 个不同的子网，每个子网有 2 7 = 128 个设备。*

255.255.255.0     → FF FF FF 00→1111 1111 1111 1111 1111 1111 0000 0000
此网络掩码指定一个具有 2 24 个子网的地址空间，每个子网有 2 8 = 256 个单独的地址。这是一种非常常见的配置——如此普遍以至于它被简单地称为“C 类”网络。

255.255.192.0     → FF FF FC 00→1111 1111 1111 1111 1111 1100 0000 0000
此网络掩码指定 2 22 个子网，每个子网有 2 10 = 1024 个地址。它可能在大型公司内部使用，每个部门都有数百台设备，这些设备应该在逻辑上组合在一起。

无效的网络掩码（注意内部零）：
255.128.255.0     → FF 80 FF 00→1111 1111 1000 0000 1111 1111 0000 0000

计算

以下是一些示例，说明网络掩码如何确定 IP 地址的网络号和设备号。

  IP 地址： 192.168.0.1→网络C0 A8 00 01
  掩码：255.255.255.0→FF FF FF 00
此设备位于子网 192.168.0.0。它可以直接与其他 IP 地址为 192.168.0 的设备通信。X

  IP 地址： 192.168.0.1     → C0 A8 00 01
  IP 地址： 192.168.0.130→网络C0 A8 00 82
  掩码：255.255.255.128→FF FF FF 80
这两个设备位于不同的子网上，没有路由器就无法相互通信。

  IP 地址： 10.10.195.27→网络0A 0A C3 1B
  掩码：255.255.0.0→FF FF 00 00
这是“B 类”网络上的地址，可以与10.10.0.0 网络上的 2 16 个地址进行通信。

您可以看到1网络掩码开头的位越多，它就越具体。也就是说，更多1位会创建一个由更少设备组成的“更小”子网。

把它们放在一起

像您的路由表一样，包含网络掩码、IP 地址和接口的三元组。（它还可能包含一个“成本”指标，如果它们都能够将数据路由到特定目的地，则它指示几个接口中的哪一个是“最便宜的”使用。例如，一个可能使用昂贵的专线。）

为了路由数据包，路由器会找到与数据包目的地最具体匹配的接口。如果，则具有地址addr和网络掩码的条目与mask目标 IP 地址匹配，其中表示按位运算。在英语中，我们想要两个地址共有的最小子网。dest(addr & netmask) == (dest & netmask)&AND

为什么？假设您和一位同事在一家同时拥有公司有线网络和无线网络的大型连锁酒店中。您还连接到公司的 VPN。您的路由表可能如下所示：

目标网络掩码接口说明
 ------------ -------- --------- -----
 公司电子邮件 FFFFFF00 VPN 通过 VPN 路由所有公司流量
 有线网络 FFFF0000 到全球其他酒店地址的有线流量
 默认 00000000 无线 所有其他流量

最具体的规则将通过 VPN 安全地路由您的公司电子邮件，即使地址恰好也与有线网络匹配。到连锁酒店内其他地址的所有流量都将通过有线网络进行路由。其他一切都将通过无线网络发送。



*实际上，在每个子网中，保留 2 个地址（最高和最低）。全1地址是广播地址：该地址将数据发送到子网上的每个设备。当设备还没有自己的 IP 地址时，设备使用全零地址来引用自身。为了简单起见，我忽略了这些。

所以算法会是这样的：

initialize:
  Sort routing table by netmask from most-specific to least specific.
  Within each netmask, sort by IP address.

search:
  foreach netmask {
    Search IP addresses for (input & netmask) == (IP address & netmask)
    Return corresponding interface if found
  }
  Return default interface
于 2012-04-01T17:58:53.290 回答
0

好的，这就是我的结构和算法现在的样子。它可以工作并给我想要的结果，但是我仍然不知道如何在网络掩码中对 IP 地址进行排序。我使用 STL 排序对网络掩码进行排序。

struct routeEntry_t

{
uint32_t ipAddr;
uint32_t netMask;
int interface;

bool operator<(const routeEntry_t& lhs) const
{
    return lhs.netMask < netMask;
}
};

const int SIZE = 6;

routeEntry_t routing_table[SIZE];

void sorting()
{
//using STL sort from lib: algorithm
sort(routing_table, routing_table+SIZE);
}

int interface(uint32_t ipAddr)
{
for (int i = 0; i < SIZE; ++i)
{
    if ((routing_table[i].ipAddr & routing_table[i].netMask) == (ipAddr &   routing_table[i].netMask))
        return routing_table[i].interface;
}
return routing_table[SIZE-1].interface;
}
于 2012-04-02T07:20:09.090 回答