Lab 5: building an IP router

准备工作

下载代码以及跑通流程

git checkout -b lab5-startercode
git fetch
git merge origin/lab5-startercode
cd build
make -j4 && make check_lab5

说明

维护ip到(EthernetAddress, time)的映射表arp_map，其中time表示添加映射的时间；
对于每次发送的dgram和next_hop，一共分为三种情况：
1. 映射表里表里有的next_hop对应的ip，则直接发送；
2. 映射表里表里一开始没有next_hop对应的ip，后来得到映射，然后发送；
3. 映射表里表里一开始没有next_hop对应的ip，目前也没得到映射，缓存dgram和next_hop；
对于每次收到的以太网帧，判断是IPv4还是ARP；
- 如果是IPv4，则解析并返回ip数据包；
- 如果是ARP，则更新映射，并发送可以发送的第3类数据，如果是ARP请求，则发送ARP回复；
如果映射超过30秒，则删除；如果发送5秒后还未回复，则再次发送；

代码

network_interface.hh

class NetworkInterface {
  private:
    //! Ethernet (known as hardware, network-access-layer, or link-layer) address of the interface
    EthernetAddress _ethernet_address;

    //! IP (known as internet-layer or network-layer) address of the interface
    Address _ip_address;

    //! outbound queue of Ethernet frames that the NetworkInterface wants sent
    std::queue<EthernetFrame> _frames_out{};

    // add
    // 映射表
    // ip -> (EthernetAddress, time)
    std::unordered_map<uint32_t, std::pair<EthernetAddress, size_t>> _arp_map{};
    // 已发送, 未回应的部分
    // ip -> time
    std::unordered_map<uint32_t, size_t> waiting_msg{};
    // 未发送部分, 没有对应以太网地址的部分
    std::list<std::pair<Address, InternetDatagram>> cache{};
    // 时间
    size_t _time = 0;

  public:
    //! \brief Construct a network interface with given Ethernet (network-access-layer) and IP (internet-layer) addresses
    NetworkInterface(const EthernetAddress &ethernet_address, const Address &ip_address);

    //! \brief Access queue of Ethernet frames awaiting transmission
    std::queue<EthernetFrame> &frames_out() { return _frames_out; }

    //! \brief Sends an IPv4 datagram, encapsulated in an Ethernet frame (if it knows the Ethernet destination address).

    //! Will need to use [ARP](\ref rfc::rfc826) to look up the Ethernet destination address for the next hop
    //! ("Sending" is accomplished by pushing the frame onto the frames_out queue.)
    void send_datagram(const InternetDatagram &dgram, const Address &next_hop);

    //! \brief Receives an Ethernet frame and responds appropriately.

    //! If type is IPv4, returns the datagram.
    //! If type is ARP request, learn a mapping from the "sender" fields, and send an ARP reply.
    //! If type is ARP reply, learn a mapping from the "target" fields.
    std::optional<InternetDatagram> recv_frame(const EthernetFrame &frame);

    //! \brief Called periodically when time elapses
    void tick(const size_t ms_since_last_tick);

    // add
    bool equal(const EthernetAddress &d1, const EthernetAddress &d2);
    // 发送广播
    EthernetFrame broadcast_frame(uint32_t ip);
};

equal

判断两个以太网地址是否相等：

bool NetworkInterface::equal(const EthernetAddress &d1, const EthernetAddress &d2) {
    for (int i = 0; i < 6; i++) {
        if (d1[i] != d2[i]) {
            return false;
        }
    }

    return true;
}

broadcast_frame

广播：

EthernetFrame NetworkInterface::broadcast_frame(uint32_t ip) {
    ARPMessage arp_msg;
    arp_msg.opcode = ARPMessage::OPCODE_REQUEST;
    arp_msg.sender_ethernet_address = _ethernet_address;
    arp_msg.sender_ip_address = _ip_address.ipv4_numeric();
    arp_msg.target_ethernet_address = {};
    arp_msg.target_ip_address = ip;

    EthernetHeader header;
    header.src = _ethernet_address;
    header.dst = ETHERNET_BROADCAST;
    header.type = header.TYPE_ARP;

    EthernetFrame frame;
    frame.header() = header;
    frame.payload() = arp_msg.serialize();

    return frame;
}

send_datagram

void NetworkInterface::send_datagram(const InternetDatagram &dgram, const Address &next_hop) {
    // convert IP address of next hop to raw 32-bit representation (used in ARP header)
    const uint32_t next_hop_ip = next_hop.ipv4_numeric();
    // 判断是否存在
    auto it = _arp_map.find(next_hop_ip);
    if (it == _arp_map.end()) {
        // 不在arp表中, 缓存, 等待回复后发送
        cache.push_back({next_hop, dgram});
        // 不在已发送未回复则广播, 不要重复广播
        if (waiting_msg.find(next_hop_ip) == waiting_msg.end()) {
            EthernetFrame frame = broadcast_frame(next_hop_ip);
            // 发送
            _frames_out.push(frame);
            // 更新表
            waiting_msg[next_hop_ip] = _time;
        }
    } else {
        // 在arp表中, 则直接发送
        EthernetHeader header;
        header.src = _ethernet_address;
        header.dst = (it->second).first;
        header.type = EthernetHeader::TYPE_IPv4;
        EthernetFrame frame;
        frame.header() = header;
        frame.payload() = dgram.serialize();
        _frames_out.push(frame);
    }
}

recv_frame

optional<InternetDatagram> NetworkInterface::recv_frame(const EthernetFrame &frame) {
    EthernetHeader header = frame.header();
    // 只接受以太网目的地是广播地址或存储在以太网地址成员变量`_ethernet_address`中的以太网地址
    if (!equal(header.dst, ETHERNET_BROADCAST) && !equal(header.dst, _ethernet_address)) {
        return {};
    }

    if (header.type == header.TYPE_IPv4) {
        // 如果入站帧是IPv4，将有效载荷解析为`InternetDatagram`，如果成功（意味着`parse()`方法返回`ParseResult::NoError`），则将生成的`InternetDatagram`返回给调用者。
        InternetDatagram ip_datagram;
        ParseResult res = ip_datagram.parse(frame.payload());
        if (res == ParseResult::NoError) {
            return ip_datagram;
        } else {
            return {};
        }
    } else {
        // 如果入站帧是ARP，将有效载荷解析为ARP消息，如果成功，记住发送方的IP地址和以太网地址之间的映射，持续30秒。（从请求和回复中学习映射。）
        ARPMessage arp_msg;
        ParseResult res = arp_msg.parse(frame.payload());
        if (res == ParseResult::NoError) {
            // 发送方以太网地址和ip地址
            EthernetAddress eth_addr = arp_msg.sender_ethernet_address;
            uint32_t ip_addr = arp_msg.sender_ip_address;
            // 此外，如果是ARP请求请求我们的IP地址，请发送适当的ARP回复。
            if ((arp_msg.opcode == ARPMessage::OPCODE_REQUEST) && (arp_msg.target_ip_address == _ip_address.ipv4_numeric())) {
                EthernetHeader header_send;
                header_send.type = header_send.TYPE_ARP;
                header_send.dst = arp_msg.sender_ethernet_address;
                header_send.src = _ethernet_address;

                ARPMessage arp_msg_send;
                arp_msg_send.opcode = arp_msg_send.OPCODE_REPLY;
                arp_msg_send.sender_ethernet_address = _ethernet_address;
                arp_msg_send.sender_ip_address = _ip_address.ipv4_numeric();
                arp_msg_send.target_ethernet_address = arp_msg.sender_ethernet_address;
                arp_msg_send.target_ip_address = arp_msg.sender_ip_address;

                // 发送
                EthernetFrame frame_send;
                frame_send.header() = header_send;
                frame_send.payload() = arp_msg_send.serialize();

                _frames_out.push(frame_send);
            }
            // 更新映射
            _arp_map[ip_addr] = {eth_addr, _time};
            // 发送
            for (auto it = cache.begin(); it != cache.end();) {
                Address addr_cache = it->first;
                InternetDatagram dgram_cache = it->second;
                // 如果ip是更新的ip, 则发送
                if (addr_cache.ipv4_numeric() == ip_addr) {
                    send_datagram(dgram_cache, addr_cache);
                    // 删除
                    cache.erase(it++);
                } else {
                    it++;
                }
            }
            // 删除已发送未回应的部分
            waiting_msg.erase(ip_addr);
        }
        return {};
    }
}

tick

void NetworkInterface::tick(const size_t ms_since_last_tick) { 
    _time += ms_since_last_tick;
    // 更新映射表
    for (auto it = _arp_map.begin(); it != _arp_map.end();) {
        // 超过30秒则删除
        if (_time - (it->second).second >= 30 * 1000) {
            _arp_map.erase(it++);
        } else {
            it++;
        }
    }
    // 更新已发送, 未回应的部分
    for (auto it = waiting_msg.begin(); it != waiting_msg.end(); it++) {
        // 超过5秒则重发
        if (_time - it->second >= 5 * 1000) {
            // 不在arp表中, 广播
            EthernetFrame frame = broadcast_frame(it->first);
            // 发送
            _frames_out.push(frame);
            // 更新发送时间
            it->second = _time;
        }
    }
}

测试

由于lab4实现的有问题，这里的webget测试也无法成功，这里只测试arp：

make -j8 && ctest -R arp

Test project /home/cs144/sponge/build
    Start 29: arp_network_interface
1/1 Test #29: arp_network_interface ............   Passed    0.00 sec

100% tests passed, 0 tests failed out of 1