Lab5 NetworkInterface

Overview

在前面的lab0-4中，我们实现了TCP协议。而在本次实验，以及接下来的实验6中，我们会将目光从顶层转移到底层——我们将着眼于运输层以下的协议。在本次实验中，我们将实现ETH协议，实现对IP数据报的封装以及对物理地址的查询转发；在下一次实验中，我们将实现网络层的路由转发算法。

承上启下

协议栈架构

我们在前面的实验已经实现了TCP协议，那么，TCP报文究竟是如何进行封装，最终到达peer那边的？我们的协议栈架构究竟是怎么样的？对于这个过程的实现协议栈，我们可以有如下三种选择。

TCP-UDP-IP

在此架构中，TCP不由操作系统的内核实现，而是运行在用户态。【事实上这三种选择TCP都是运行在用户态的，正如我们实现的这样】

用户态会将上层app传来的数据封装在TCP报文段中，用户态只需向操作系统提供的一个接口传入TCP报文段以及目的地址进入该接口就行。在此接口中，操作系统会给用户传进来的数据报文增加UDP、IP、ETH等等协议头，添加端口号等等等。

所以说，其实操作系统默认只支持UDP-IP-ETH呀！新加的一层TCP反倒是靠用户实现的！

如果只需UDP协议，用户只需传入上层app的数据就行；如果还想要TCP，那就得由用户自己实现TCP协议，把上层app的数据封装成TCP报文，然后再发送给系统调用做进一步的封装。

其实不仅是TCP，HTTP应该也是用户自己实现的。对于web开发来说，大概应该是这样：top app data→ HTTP request/response → TCP segment → 操作系统接口 → UDP → IP → ETH frame

这个“TCP是用户态实现的”的观点让我非常震撼，在计网理论学的东西现在我们居然已经亲手实现出来了，有种网友面基的震撼。

TCP/IP协议栈到底是内核态好还是用户态好？这篇文章好像写得很好，但是我没怎么看懂就先放在这【经典】不过里面对于NAK和ACK机制的对比学习写得挺有意思的，看了感觉很有收获。

TCP-IP

TCP当然也可以越过UDP协议，直接与IP层相连。但这由于不用了操作系统提供的那一层UDP，我们要做的事情就会变多变复杂。这也是我们经常听到的所谓“TCP/IP协议”的意义。

Linux provides an interface, called a TUN device, that lets application supply an entire Internet datagram, and the kernel takes care of the rest (writing the Ethernet header, and actually sending via the physical Ethernet card, etc.). But now the application has to construct the full IP header itself, not just the payload.【要做的事变多了】

不过这里的这个填IP header的事情，在学校已经做过了，只是这个点的话确实没什么好说的

听起来有没有很耳熟？是的，这个TCP-IP架构，我们在lab0-4已经实现了！其TCP部分是由我们自己写的，而IP部分则是由官方给的代码写的。

You’ve done this already.

In Lab 4, we gave:

  1. an object that represents an Internet datagram and knows how to parse and serialize itself (tcp_helpers/ipv4_datagram.{hh,cc}) 表示了Internet datagram的数据结构，它可以自己序列化。
  2. the logic to encapsulate(封装) TCP segments in IP (now found in tcp_helpers/tcp_over_ip.cc).

The CS144TCPSocket uses these tools to connect your TCPConnection to a TUN device.

【我关于这些代码的研究放在了其他的对实验未涉及的思考模块中了】

所以说，

发送数据时，数据流向：上层app→（通过CS144TCPSocket）TCPConnection→（通过write方法）ByteStream→TCPSender→（通过从_sender.segments_out读）TCPConnection→（通过CS144TCPSocket绑定的事件从segments_out传输）TUN

接收数据时，数据流向：TUN→（通过CS144TCPSocket绑定的事件调用segment_received）TCPConnection→TCPReceiver→（中间经过StreamAssembler）BYteStream→（通过CS144TCPSocket读）上层app

TUN以内隐藏的复杂逻辑，都由操作系统来帮我们实现。除去我们本次实验要做的ETH协议之外，剩下的其实好像就是我们在6.S081中做的networking driver了！再接下去就是数据链路层和物理层的工作了，这些就是硬件实现的范畴了。

感觉写到这，心情非常地澎湃。我们居然真的真的，亲手将计算机网络全部实现了出来，心中真是无限感→动↑啊！

TCP-IP-ETH

而在整个sponge实现中，我们不拘泥于仅实现TCP/IP。我们还要实现属于我们自己的ETH协议。

就跟TCP/IP的实现中，将IP数据包发送给操作系统需要通过TUN接口一样，我们需要把包装的ETH数据报发送给TAN接口。

总结

因而，通过以上表述，我们知道了本次实验的目的是实现数据链路层，以及为什么要实现数据链路层。下面将详细介绍数据链路层的具体功能以及实现。

数据链路层的实现

要明白数据链路层怎么实现，首先要知道其功能。

数据链路层的功能

可大概分为两点：

  1. 通过ETH协议，封装/拆封数据包

    这个没什么好说的。

    “交付给上层协议栈”的这个“交付”动作是怎么用代码实现的呢？在成员变量里保留对上层协议栈的成员的引用？或者是像TCP那样，维护一个_out和一个received方法，其它具体连接由socket的事件驱动？

    答案应该是像TCP这样。

    但其实也不完全像TCP。TCP与其上层，也即app的交互是通过socket；但interface没有这个机制，它只能在frame_received的时候直接return它收到的数据报。啊不过，也许从eth得到数据报然后交给ip也是socket的任务？

    我记得在本校的计网实验中，似乎是归结到了一个函数内实现，其接收一个void*类型的指针，好像还有代表报文格式的枚举类。

  2. 通过ARP协议，将IP地址转化为物理地址

    我们学过，在数据链路层（还是说是物理层？）endpoint的交互是通过物理地址的，但在网络层以上，endpoint的交互是通过IP地址（域名也会被解析为IP地址）的。因而，在ETH层，我们首先需要将IP地址转化为其对应的物理地址。

    在这里可以梳理一下计算机网络中所谓“地址”的转化路径：

    我们通过约定俗成的域名访问某个主机，该域名会被DNS解析为IP地址，该IP地址会在网络层，也就是IP协议这边经过路由转发【如果是用户host的话会发给自己的default路由器】，然后在ETH层会根据这个要去的地方的IP地址通过ARP协议查表，得到下一站应该要去的物理地址。

    与此同时我们也可以归纳出lab6的内容。我们的lab6就是要做这个“转发”功能。根据所学可知，实质上只有路由器才算起着真实的路由转发功能【host的路由转发只是转发给自己的海关路由器】。而路由器不需要什么TCP协议，所以lab6只基于lab5，跟lab0-4没有半毛钱关系。

ARP协议

image-20230307193836409

H1知道R1的IP地址是因为设置了默认网关，而路由器之间知道彼此的IP地址是通过路由协议相互通信。

为什么H1知道要发给H2就需要经过R1，以及为什么H1知道R1的IP地址，R1知道R2的IP地址，这都是网络层的路由协议在起作用。

而H1怎么知道的R1的MAC地址，这就是ARP协议研究的内容了。是ARP将已知的IP地址翻译为MAC。

ARP协议的具体内容看视频就好，在此不赘述。具体有ARP请求报文（广播）、ARP响应报文（单播）

如果发现不知道MAC地址就发ARP request，收到ARP request的host如果发现是自己的，就需要做两件事，一个是记下来者，另一个是发送ARP响应报文。

image-20230307194650945

network interface

介绍完上面的种种，终于来到了本次实验要实现的正题：network interface。

正如同在网络层，各个主机通过IP协议，凭借自己的IP地址相互打交道一样，在数据链路层，各个network interface通过ARP协议和ETH协议，凭借MAC地址相互打交道。

可以看出，数据链路层的“network interface”与网络层的“主机”是相近的。它们的区别是什么呢？

答案是，一个主机可以有多个网卡，因而可以有多个network interface。

image-20230307193102495

不过这里的这个对应还是很有意思的，它反映出了计算机网络的抽象：一次网络传输可以看作是单层之间的相互交流，可以忽略其他层。不得不感慨，设计出网络层级模型的人真是天才。

因而，在我们的数据链路层，也即我们的network interface中，我们需要实现ARP协议和ETH协议，完成数据包的收发。

心得

感想

这次实验内容其实有一说一挺复杂的，既要管理各种超时，又要写收发管理。它其实跟TCPSender有点像，只不过本次实验的难点在数据结构的管理，TCPSender的难点在各种状态机的细枝末节。由于有TCPSender的基础，本次实验完成难度大大减小，我甚至写完代码后不出二十分钟就pass掉了测试用例（骄傲←）不过，它的编码过程及数据结构确实还是有点复杂的。

思路

初见思路

整理一下我们的interface可能收到/发送的报文，思路就很简单了

收：

  1. 来自外部的数据

    比较MAC地址跟自己一不一样

    需要去掉其ETH头，交付给上层

  2. ARP请求

    比对请求的IP地址跟自己的一不一样。

    如果一样，就把该报文的src MAC记录进ARP，并且发送一个ARP响应进入frame_out

  3. ARP响应

    记录MAC地址；将放入等待暂存队列的数据包取出重新发送

发：

  1. 来自上层的数据报

    查询ARP表，如果MAC地址已知就发，未知的话放入等待队列，并且发送ARP请求

  2. ARP请求

  3. ARP响应

所以我们需要写以下几个函数：

  1. frame_received

  2. send_arp_response

    创建一个新的frame，填上自己的MAC地址和srcMAC

  3. send_arp_request

    创建一个新的frame，填上自己的MAC地址、IP地址和目的IP地址

  4. frame_send

    发送从上层来的报文

  5. ARP操作 ARP表是一个map映射

以及如下成员变量：

  1. ARP映射的数据结构

    map<IP地址，{MAC地址，ticks}>

  2. 等待队列

    map<IP地址，{未填写dst的frame们，latest_ticks}>

  3. ticks 代表当前经过的时间

正确思路

可以看到，官方提供给我们的接口定义，以及在指导书中对函数实现的详细拆分，确实跟初见思路所想的差不多完全一样【但我更推荐看指导书的版本，它枚列得更加清晰】，可以说思路还是很直观的。所以就不多bb了直接看代码吧。

小细节

  1. 等待在同一个IP地址的帧可能不止一个，所以在数据结构中需要以vector集合形式管理

  2. 在接收以太帧时，应该首先检查最外层的ETH协议的MAC地址，作用是判断这个帧是不是发给自己的。

    如果帧内封装的是IP数据包，这样做就很OK了，因为能确保此时自己一定可以收这个包；

    但是如果帧内封装的是ARP数据包，这样做是不OK的。因为依照ARP协议，若是此为ARP REQUEST，则其ETH header是广播地址，而它真正想要届到的对象的信息是在ARP header中的target IP。因而，对于ARP协议，我们还得判断header中的target IP和本机IP是否相等。

代码

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NetworkInterface {
  private:
    // ...
    
    // arp映射的元素定义
    struct arp_node {
        EthernetAddress mac;// ip地址key对应的mac地址
        size_t ticks;// 该条记录被记录时的时间
    };
    // ARP映射，<IP地址，元素结点>
    std::map<uint32_t, arp_node> arp_mappings{};
    
    struct waiting_node {
        std::vector<EthernetFrame> frames{};// 等待在该IP地址的以太帧们
        size_t latest_ticks = 0;  // 等候中的frame们最晚放入者的时间
    };
    // 等待队列，<IP地址，元素结点>
    std::map<uint32_t, waiting_node> waiting_frames{};

    size_t ticks = 0;// 出生到现在经过的时钟滴答
    // 自定义方法，用于发送一个arp报文【请求/响应】
    void send_arp(uint32_t target_ip, EthernetAddress eth_add, uint16_t opcode);

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include "network_interface.hh"
#include "arp_message.hh"
#include "ethernet_frame.hh"
#include <iostream>

template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {}

using namespace std;


NetworkInterface::NetworkInterface(const EthernetAddress &ethernet_address, const Address &ip_address)
    : _ethernet_address(ethernet_address), _ip_address(ip_address) { }

// param: target ip address , target ethernet address , and the arp opcode
// if is the request, pass BROADCAST as the param;
// if is the response, pass arprequest.eth_add as the param.
void NetworkInterface::send_arp(uint32_t target_ip, EthernetAddress eth_add, uint16_t opcode) {
    // create the eth frame
    EthernetFrame frame;
    /* create the payload */
    // create the arp message
    ARPMessage arp_mes;
    arp_mes.sender_ethernet_address = _ethernet_address;
    arp_mes.sender_ip_address = _ip_address.ipv4_numeric();
    arp_mes.opcode = opcode;
    arp_mes.target_ip_address = target_ip;
    if (opcode == ARPMessage::OPCODE_REPLY)
        arp_mes.target_ethernet_address = eth_add;
    else // if is the REQUEST, arp target mac is unknown and should be set to zero
        arp_mes.target_ethernet_address = {0, 0, 0, 0, 0, 0};
    // serialize and put it into the payload
    frame.payload() = BufferList(arp_mes.serialize());
    /* fill in the header */
    EthernetHeader header;
    header.src = _ethernet_address;
    header.dst = eth_add;
    header.type = EthernetHeader::TYPE_ARP;
    frame.header() = header;

    // send it
    _frames_out.push(frame);
}

//! \param[in] dgram the IPv4 datagram to be sent
//! \param[in] next_hop the IP address of the interface to send it to (typically a router or default gateway, but may also be another host if directly connected to the same network as the destination)
//! (Note: the Address type can be converted to a uint32_t (raw 32-bit IP address) with the Address::ipv4_numeric() method.)
// 处理从上层协议接收到的信息
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();
    // create the eth frame
    EthernetFrame frame;
    // fill in the payload
    frame.payload() = dgram.serialize();
    // fill in the header
    EthernetHeader header;
    // dst is reserved
    header.src = _ethernet_address;
    header.type = EthernetHeader::TYPE_IPv4;

    auto tmp_arp = arp_mappings.find(next_hop_ip);// find the mac from the arp mappings
    if (tmp_arp == arp_mappings.end()) {  // not exist
        frame.header() = header;          // remember that the dst field is reserved
        auto tmp_wait = waiting_frames.find(next_hop_ip);// is there a waiting queue?
        // the arp request hasn't been sent if there is not a waiting queue, 
        if (tmp_wait == waiting_frames.end()) {
            // create the waiting queue
            vector<EthernetFrame> frames;
            frames.push_back(frame);
            waiting_node node;
            node.frames = frames;
            node.latest_ticks = ticks;
            waiting_frames.insert(make_pair(next_hop_ip, node));
            // send arp request
            send_arp(next_hop_ip, ETHERNET_BROADCAST, ARPMessage::OPCODE_REQUEST);
        } else { // the arp request has been sended
            if (ticks - tmp_wait->second.latest_ticks > 5*1000) {// send before 5 seconds
                // resend arp request
                send_arp(next_hop_ip, ETHERNET_BROADCAST, ARPMessage::OPCODE_REQUEST);
                // update the time only when the arp request was sent
                tmp_wait->second.latest_ticks = ticks;  
            }
            tmp_wait->second.frames.push_back(frame);// add the frame to the waiting list
        }
        return;
    }
    // recall that the dst field is reserved
    header.dst = tmp_arp->second.mac;
    frame.header() = header;

    // send it right away
    _frames_out.push(frame);
}

//! \param[in] frame the incoming Ethernet frame
optional<InternetDatagram> NetworkInterface::recv_frame(const EthernetFrame &frame) {
    if (frame.header().dst != _ethernet_address && frame.header().dst != ETHERNET_BROADCAST)
        return {};  // should not accept
    if (frame.header().type == EthernetHeader::TYPE_IPv4) {
        InternetDatagram ip_data;
        ParseResult res = ip_data.parse(frame.payload());
        if (res == ParseResult::NoError) {
            return ip_data; // return to send it to the upper protocal
        } else
            return {};
    }
    if (frame.header().type != EthernetHeader::TYPE_ARP)
        return {};
    
    ARPMessage arp_mes;
    ParseResult res = arp_mes.parse(frame.payload());
    if (res != ParseResult::NoError)
        return {};
    // I'm not the arp target
    if (arp_mes.target_ip_address != _ip_address.ipv4_numeric())
        return {};
    
    auto tmp_arp = arp_mappings.find(arp_mes.sender_ip_address);
    if (tmp_arp == arp_mappings.end()) {  // arp mapping not exist, create one
        arp_node node;
        node.ticks = ticks;
        node.mac = arp_mes.sender_ethernet_address;
        arp_mappings.insert(make_pair(arp_mes.sender_ip_address, node));
    } else {
        tmp_arp->second.ticks = ticks;  // update the record ticks
    }
    if (arp_mes.opcode == ARPMessage::OPCODE_REQUEST) {
        send_arp(arp_mes.sender_ip_address, arp_mes.sender_ethernet_address, ARPMessage::OPCODE_REPLY);
        // shouldn't return now, maybe we are also waiting for the sender's mac address
        // return {};
    }
    // send all frames in the waiting queue
    auto tmp_wait = waiting_frames.find(arp_mes.sender_ip_address);
    // have no frames waiting for the address
    if (tmp_wait == waiting_frames.end())
        return {};
    while (!tmp_wait->second.frames.empty()) {
        EthernetFrame f = tmp_wait->second.frames.back();
        // recall that the dst field is reserved
        f.header().dst = arp_mes.sender_ethernet_address;  
        _frames_out.push(f);
        tmp_wait->second.frames.pop_back();
    }
    // erase all the waiting frames
    waiting_frames.erase(tmp_wait);
    return {};
}

//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void NetworkInterface::tick(const size_t ms_since_last_tick) {
    ticks += ms_since_last_tick;
    // walk the arp mappings to check whether a mapping is out-of-date
    for (auto it = arp_mappings.begin(); it != arp_mappings.end();) {
        if (ticks - it->second.ticks > 30 * 1000) {
            it = arp_mappings.erase(it);
        } else
            it++;
    }
}