Checkpoint 4 Writeup

报文头格式

IPV4头

/*
*  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*  |Version|  IHL  |Type of Service|          Total Length         |
*  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*  |         Identification        |Flags|      Fragment Offset    |
*  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*  |  Time to Live |    Protocol   |         Header Checksum       |
*  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*  |                       Source Address                          |
*  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*  |                    Destination Address                        |
*  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*  |                    Options                    |    Padding    |
*  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*/
  static constexpr size_t LENGTH = 20;        // IPv4 header length, not including options, at least 20 bytes
  static constexpr uint8_t DEFAULT_TTL = 128; // A reasonable default TTL value
  static constexpr uint8_t PROTO_TCP = 6;     // Protocol number for TCP
  // IPv4 Header fields
  uint8_t ver = 4;           // IP version
  uint8_t hlen = LENGTH / 4; // header length (multiples of 32 bits, that is 4 bytes)
  uint8_t tos = 0;           // type of service
  uint16_t len = 0;          // total length of packet
  uint16_t id = 0;           // identification number
  bool df = true;            // don't fragment flag
  bool mf = false;           // more fragments flag
  uint16_t offset = 0;       // fragment offset field
  uint8_t ttl = DEFAULT_TTL; // time to live field
  uint8_t proto = PROTO_TCP; // protocol field
  uint16_t cksum = 0;        // checksum field
  uint32_t src = 0;          // src address
  uint32_t dst = 0;          // dst address

ARP头包含

uint16_t hardware_type = TYPE_ETHERNET;             // Type of the link-layer protocol (generally Ethernet/Wi-Fi)
uint16_t protocol_type = EthernetHeader::TYPE_IPv4; // Type of the Internet-layer protocol (generally IPv4)
uint16_t opcode {}; // Request or reply

EthernetAddress sender_ethernet_address {};
uint32_t sender_ip_address {};

EthernetAddress target_ethernet_address {};
uint32_t target_ip_address {};

发送时要加上以太网头

以太网头包含

EthernetAddress dst;
EthernetAddress src;
uint16_t type; //Frame type：TYPE_IPv4 or TYPE_ARP

主要函数实现

void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )

查看本地map是否缓存了目标ip对应的mac地址

是，构建以太网帧(填写头部，并用InternetDatagram构造payload)，放入sending_queue
否，构建以太网帧，放入waiting_queue，如果最近无对目标ip的ARP请求，构建请求报文并放入sending_queue

optional NetworkInterface::recv_frame( const EthernetFrame& frame )

只接受广播帧和mac地址是本地mac地址的帧

如果是TYPE_IPv4，说明是发送给自己的，去除头部将InternetDatagram交给上层
如果是TYPE_ARP，使用parse解析出ARP报文，并在本地map中添加报文发送方的ip和mac的映射，继续判断ARP类型，如果是OPCODE_REQUEST，就和本地ip比较，相同就发送ARP REPLY；至于为什么mac是广播地址是不用广播，暂时不知道，貌似除了发送ARP时设置外没用过。完成ARP处理后还要把waiting_queue里发送到最近更新的ip的帧添加到sending_queue

void NetworkInterface::tick( const size_t ms_since_last_tick )

每次被调用时清除超时映射和超时ARP_REQUEST记录即可

optional NetworkInterface::maybe_send()

取出sending_queue最早的帧发送

最后附上代码

#include "network_interface.hh"

#include "arp_message.hh"
#include "ethernet_frame.hh"

using namespace std;

// ethernet_address: Ethernet (what ARP calls "hardware") address of the interface
// ip_address: IP (what ARP calls "protocol") address of the interface
NetworkInterface::NetworkInterface( const EthernetAddress& ethernet_address, const Address& ip_address )
  : ethernet_address_( ethernet_address ), ip_address_( ip_address )
{
  cerr << "DEBUG: Network interface has Ethernet address " << to_string( ethernet_address_ ) << " and IP address "
       << ip_address.ip() << "\n";
}

// dgram: the IPv4 datagram to be sent
// 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) by using the
// Address::ipv4_numeric() method.
void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )
{
  uint32_t next_hop_ip = next_hop.ipv4_numeric();
  if(arp_table.count(next_hop_ip)){
    EthernetFrame frame;
    frame.header.dst=arp_table[next_hop_ip].first;
    frame.header.src=ethernet_address_;
    frame.header.type=EthernetHeader::TYPE_IPv4;
    frame.payload=serialize(dgram);
    sending_queue.push(frame);
  }else{
      EthernetFrame frame;
      frame.header.src=ethernet_address_;
      frame.header.type=EthernetHeader::TYPE_IPv4;
      frame.payload=serialize(dgram);
      waiting_queue[next_hop_ip].push_back(frame);
      if(!arp_request_table.count(next_hop_ip)){
        ARPMessage arp;
        arp.opcode=ARPMessage::OPCODE_REQUEST;
        arp.sender_ethernet_address=ethernet_address_;
        arp.sender_ip_address=ip_address_.ipv4_numeric();
        arp.target_ip_address=next_hop_ip;
        arp_request_table[next_hop_ip]=0;
        frame.header.dst=ETHERNET_BROADCAST;
        frame.header.src=ethernet_address_;
        frame.header.type=EthernetHeader::TYPE_ARP;
        frame.payload=serialize(arp);
        sending_queue.push(frame);
      }
  }
}

// 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 {};
  }
  if(frame.header.type==EthernetHeader::TYPE_IPv4){
    InternetDatagram dgram;
    if(parse(dgram,frame.payload)){
      return dgram;
    }
  }else if(frame.header.type==EthernetHeader::TYPE_ARP){
    ARPMessage arp;
    if(parse(arp,frame.payload)){
      arp_table[arp.sender_ip_address]={arp.sender_ethernet_address,0};
      if(arp.opcode==ARPMessage::OPCODE_REQUEST){
        if(arp.target_ip_address==ip_address_.ipv4_numeric()){
          ARPMessage reply;
          reply.opcode=ARPMessage::OPCODE_REPLY;
          reply.sender_ethernet_address=ethernet_address_;
          reply.sender_ip_address=ip_address_.ipv4_numeric();
          reply.target_ethernet_address=arp.sender_ethernet_address;
          reply.target_ip_address=arp.sender_ip_address;
          EthernetFrame newframe;
          newframe.header.dst=arp.sender_ethernet_address;
          newframe.header.src=ethernet_address_;
          newframe.header.type=EthernetHeader::TYPE_ARP;
          newframe.payload=serialize(reply);
          sending_queue.push(newframe);
        }
        // else if(frame.header.dst == ETHERNET_BROADCAST){
        //   sending_queue.push(frame);
        // }
      }
      auto datagrams=waiting_queue[arp.sender_ip_address];
      for(auto& i:datagrams){
        i.header.dst=arp.sender_ethernet_address;
        sending_queue.push(i);
      }
      waiting_queue.erase(arp.sender_ip_address);
    }
  }
  return {};
}

// 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 )
{
  for(auto it=arp_table.begin();it!=arp_table.end();){
    it->second.second+=ms_since_last_tick;
    if(it->second.second>map_lmt){
      it=arp_table.erase(it);
    }else{
      it++;
    }
  }
  for(auto it=arp_request_table.begin();it!=arp_request_table.end();){
    it->second+=ms_since_last_tick;
    if(it->second>arp_request_lmt){
      it=arp_request_table.erase(it);
    }else{
      it++;
    }
  }
}

optional<EthernetFrame> NetworkInterface::maybe_send()
{
  if(sending_queue.empty()){
    return {};
  }
  EthernetFrame frame=sending_queue.front();
  sending_queue.pop();
  return frame;
}