ARP表项配置

29 Aug 2024 in Algorithm Pageviews

solve actually problem!

某网络设备向目的IP发送报文时，需要在ARP表中根据已经配置的表项(ip与mac地址的映射关系)，找到对应的mac的地址，补全报文的二层信息后进行转发，如果没找到就需要将报文缓存起来，等到后续配置了对应的表项后，再次进行补发。

请实现下面接口:

1. ArpSystem(int arpCap, int cachePktCap, int ipCap)初始化

   • 表项最大数量为 arpCap
   • 缓存能力：设备最多可缓存cachePktCap个报文，且同一个IP最多缓存ipCap报文

2. Update(int ip, string macAddr) 配置一条ARP表项

   • 如果已经存在该ip的映射关系，则覆盖ip对应的macAddr，返回空列表[]

   • 如果不存在，当表项未满时，直接添加一条表项；当表项已满时，将最久未调用的表项替换(如查询、添加和覆盖配置)

     添加或替换表项后，将该ip缓存的报文升序返回(以备补发)，然后清空对应ip的缓存报文

3. Forward(int ip, int pktId) 在ARP表中查询此IP对应的macAddr 进行模拟转发

   • 若找到对应的macAddr，则返回该macAddr表示成功转发；否则，尝试将报文pktId进行缓存，返回空的字符串""
   • 若超出cachePktCap或者ipCap中的任意一个，就缓存失败，否则缓存成功

输入

每行有一个函数调用，初始话只在首行会调用一次。mac地址为十六进制形式，用-间隔开来。如：CC-DD-EE-FF-AA-09

输出

按顺序输出每个函数的执行结果

样例：

输入：

ArpSystem(3, 3, 2)

Update(123, “AB-AB-AB-AB-AB-AB”)

Forward(456, 23)

Forward(456, 0)

Forward(456, 8)

Update(456, “BA-BA-BA-BA-BA-BA”)

Update(123, “CD-EF-AB-AA-AB-AB”)

Forward(123, 5)

输出：

null

[]

””

””

””

[0, 23]

[]

“CD-EF-AB-AA-AB-AB”

实现

#include <bits/stdc++>

using namespace std;

class ArpSystem {
public:
    ArpSystem(int arpCap, int cachePktCap, int ipCap)
        : m_arpCap(arpCap), m_cachePktCap(cachePktCap), m_ipCap(ipCap) {}

    vector<int> Update(int ip, const string &macAddr)
    {
        auto iter = std:find(arpIp.begin(), arpIp.end(), ip);
        if (iter == arpIp.end()) {
            if (arpIp.size() == m_arpCap) {
                arpId.erase(arpIp.begin());
            }

            arpIp.emplace_back(ip);
            ipMac[ip] = macAddr;
            vector<int> res(pktIdHash[ip].begin(), pktIdHash[ip].end());
            m_curNum -= res.size();
            pktIdHash[ip].clear();
            return res;
        }
        
        arpIp.erase(iter);
        arpIp.emplace_back(ip);
        ipMac[ip] = macAddr;
        return {};
    }
    
    string Forward(int ip, int pktId)
    {
		auto iter = std::find(arpIp.begin(), arpIp.end(), ip);
        if (iter == arpIp.end()) {
            if ((curNum < m_cachePktCap) && (pktIdHash[ip].size() < m_ipCap)) {
                pktIdHash[ip].insert(pktId);
                curNum++;
            }
            return "";
        }
        
        arpIp.erase(iter);
        arpIp.emplace_back(ip);
        return ipMac[ip];
    }

private:
    int m_arpCap{};
    int m_cachePktCap{};
    int m_ipCap{};
    int m_curNum{};
    vector<int> arpIp;
    map<int, string> ipMac;
    map<int, set<int>> pktIdHash;
};