cs144学习记录

Posted on Edited on In

cs144

斯坦福 或许博士的时候有机会遇见你吧

现在我还是乖乖找个跳板 末流211的痛，，，

video: https://www.youtube.com/watch?v=r2WZNaFyrbQ&list=PL6RdenZrxrw9inR-IJv-erlOKRHjymxMN

platform: Ed — Digital Learning Platform (edstem.org)

homework: https://cs144.github.io/

Week 1

lesson1

BitTorrent协议

BitTorrent(简称BT)是一个文件分发协议，每个下载者在下载的同时不断向其他下载者上传已下载的数据。而在FTP，HTTP协议中，每个下载者在下载自己所需文件的同时，各个下载者之间没有交互。当非常多的用户同时访问和下载服务器上的文件时，由于FTP服务器处理能力和带宽的限制，下载速度会急剧下降，有的用户可能访问不了服务器。BT协议与FTP协议不同，特点是下载的人越多，下载速度越快，原因在于每个下载者将已下载的数据提供给其他下载者下载，充分利用了用户的上载带宽。通过一定的策略保证上传速度越快，下载速度也越快。在很短时间内，BitTorrent协议成为一种新的变革技术。

skype协议

Skype协议（英语：Skype protocol），由Skype公司发展的专有通信协议，以点对点网络（peer-to-peer）方式创建电话网络。这个协议的内容并没有被公开发布，采用这个协议的软件，也是专有软件。

在没有获得Skype公司适当授权的前提下，Skype网络，与其他绝大多数VoIP网络间，不具互操作性。研究者以逆向工程来揭露Skype协议的内容，并根据这些已知的内容，以一些非正式的软件完成连线，来使用Skype公司提供的服务。如

Project

环境安装

直接用他给的虚拟机

1
cs144:12345678

IDE Clion? 用它连一下虚拟机

还是用我自己的ubuntu，，，

搞了1h 没搞好真无语

相关包的要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
clang-tidy 静态代码分析框架
g++ version 8.x 我用了9.x 没问题吧，，，
clang-tidy version 6 or 7
clang-format version 6 or 7
cmake version 3 or later
libpcap development headers (libpcap-dev on Debian-like distributions)
git
iptables                  iptables 是 Linux 防火墙系统的重要组成部分，iptables 的主要功能是实现对网络数据包进出设备及转发的控制
mininet 2.2.0 or later     mininet在SDN网络实验中可以用来快速、方便的创建网络拓扑
tcpdump
telnet    
wireshark 
socat   Socat 是 Linux 下的一个多功能的网络工具，名字来由是 「Socket CAT」。其功能与有瑞士军刀之称的 Netcat 类似，可以看做是 Netcat 的加强版。 Socat 的主要特点就是在两个数据流之间建立通道，且支持众多协议和链接方式。
netcat-openbsd  Netcat OpenBSD 版本是对原始 netcat 的重写，包括对 IPv6、代理和 unix 套接字的支持。除了这些增强功能之外，它还被编译以删除一个被认为是应用程序巨大安全漏洞的功能。
GNU coreutils   软件包包括一整套基本的 shell 工具
bash 
doxygen   将程序中的特定批注转换成为说明文件
graphviz  一个图可视化工具

lab0

先按要求读 documentation

看代码怎么有种当年初看吴恩达作业的感觉了，，，眼花缭乱 不知所云

wrting webget

实现 webget？ 我最初写出来的是这么个玩意 但是没返回 两个可能的原因

  • 没port （ 不知道为什么这里没加
  • close 后面再加东西 （ 确实要加 \r\n\r\n

sock.eof() 后来查才会用

EOF是end of file的缩写，表示”文字流”（stream）的结尾。这里的”文字流”，可以是文件（file），也可以是标准输入（stdin）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void get_URL(const string &host, const string &path) {
    // Your code here.

    // why dont have port number
    TCPSocket sock;
    sock.connect(Address(host,"http"));


    std::string request = "GET " + path + " HTTP/1.1\r\n" +
                          "Host: " + host + "\r\n" +
                          "Connection: close\r\n\r\n";

    sock.write(request);
    while(!sock.eof()){
        auto recvd = sock.read();
        std::cout << recvd;
    }

    sock.close();

    cerr << "Function called: get_URL(" << host << ", " << path << ").\n";
    cerr << "Warning: get_URL() has not been implemented yet.\n";
}

最后的writeup 如上

image-20221019135306026

好像要么指定 service 在这里是http? 要么是 port

image-20221019135636710

An in-memory reliable byte stream

先来看一下 writer 感觉只有一个 FileDescriptor Class 类可以用？

可能是压根没写过c++ 看了半天还不知道如何下手，，，

要求再解读。。。太困难了，，，

  • 写一个传 字节的 类似于socket 但是在内存中实现

要再内存中实现 所以我们要搞个什么数据结构来存呢？ 看样子应该是 first in first out?

–> 队列！（怎么上上学期才学的 毛线都不记得了 这就是CN undegraduate education吗？

我怎么这么容易忘，，，那么问题变为 CC+中 队列怎么用

14w+ 赞的 先贴这儿了

看来要先在模版里引入

(206条消息) C++ 类模板（template）详解_霸道小明的博客-CSDN博客_c++ template

一点一点来解决吧 首先 下面这个怎么写 DUMMY_CODE 伪代码的意思

即： ByteStream 如何实现

1
ByteStream::ByteStream(const size_t capacity) { DUMMY_CODE(capacity); }

先要定义一个 capacity？

(206条消息) c++中冒号（:）的用法_限量发行x的博客-CSDN博客_c++ 冒号

这里应该是要继承接口？

1
2
3
ByteStream::ByteStream(const size_t capacity) :
        buffer(),
        capacity_size(capacity),

目前先是这样 来看看 write 即往队列中插值？

1
2
3
// Write a string of bytes into the stream. Write as many
// as will fit, and return the number of bytes written.
size_t write(const std::string &data);

data 是 string 类型 要怎么操作 一个一个写进去？

大致想法：判断是否为空 不为空则一个一个（从前往后）插入buffer中

要不停调用 wirte? 按他的意思就判断有多长 然后写进去？bytes 是不是长度还要再乘一下

(206条消息) C++中的string类用法简介_liitdar的博客-CSDN博客_c++ string

c++ | size_t - 山竹小果 - 博客园 (cnblogs.com) 用 size_t 保命 大概是这个意思 防over

1
2
3
4
5
6
ByteStream::write(const string &data) {
    for (size_t i = 0; i < data.length(); i++) {
        buffer.push(data[i]);
    }
    return data.length();
}

但是貌似没考虑溢出？ 等下再说 等会看下read咋回事再说

1
2
// Returns the number of additional bytes that the stream has space for
size_t remaining_capacity() const;

这个要看队列里有多少个值 拿capacity_size 去减 queue.size()

1
size_t ByteStream::remaining_capacity() const { return capacity_size - buffer.size(); }

接下来看

1
2
// Signal that the byte stream has reached its ending
void end_input();

emmm 这样不知道刑不刑 但上面write就要加上一句判断了 

1
2
3
void ByteStream::end_input() {
    return capacity_size == buffer.size();
}

这个貌似要定义一个 _error 人家给好了 那没事了

1
2
// Indicate that the stream suffered an error
void set_error();

—–>

okk 到目前为止 write 差不多了 改 read 了 这peek 是干什么的o.o

看半天才明白 查看steam的下多少个字节

1
2
// Peek at next "len" bytes of the stream
std::string peek_output(const size_t len) const;

咋 peek 出列？应该是 写！这里string可以直接加吗

很烦 到这里 没搜到遍历 queue 的方法 。。。再开一个吗？会不会比较占空间？ o.o

似乎 用什么deque 可以遍历 哎 上面要重写了 好好好

1
2
3
string ByteStream::peek_output(const size_t len) const {
    return string(buffer.begin(), buffer.begin() + len);
}

easy

1
2
3
4
5
void ByteStream::pop_output(const size_t len) {
    for (size_t i = 0; i < len; i++) {
        buffer.pop_front();
    }
}

read的话 直接从 buffer 中peek peek完就 pop

1
2
// Read (i.e., copy and then pop) the next "len" bytes of the stream
std::string read(const size_t len);
1
2
3
4
5
std::string ByteStream::read(const size_t len) {
    string str = this->peek_output(len);
    this->pop_output(len);
    return str;
}

快胜利了o.o

——————————————————>

1
2
3
4
5
6
7
8
9
10
11
12
bool input_ended() const; // `true` if the stream input has ended


bool eof() const; // `true` if the output has reached the ending
bool error() const; // `true` if the stream has suffered an error
size_t buffer_size() const; // the maximum amount that can currently be peeked/read
bool buffer_empty() const; // `true` if the buffer is empty


// 还要专门搞两个值来记录一下
size_t bytes_written() const; // Total number of bytes written
size_t bytes_read() const; // Total number of bytes popped

怎么判断 input 结束了？ 是个问题，，，

eof 怎么实现？

end_input 是记录写完？ 是对于每一次来说

input_ended 是记录输入结束了 是对于整体来说

要设两个变量分别记录一下 written and read

随便写了一下 接下来就是处理一堆爆红了

终于 改了很多地方 这里就不放wp了

image-20221103111515314

记录下出错的地方

1
2
3
4
5
6
7
8
9
10
11
12
size_t ByteStream::write(const string &data) {
    if (_end_input) {
        return 0;
    }

    _written_size += data.length();

    for (size_t i = 0; i < data.length(); i++) {
        _buffer.push_back(data[i]);
    }
    return data.length();
}

这里不该直接加 data.length() 而要判断下data是否能写进去

1
min(data.size(), _capacity_size - _buffer.size());

lab1

从原理的角度来看：

Your push substring method will ignore any portion of the string that would cause the StreamReassembler to exceed its “capacity”`

现在来分析一下这句话讲的是什么意思

这似乎是可靠数据传输原理里的一种需求

实验目的 把stream 的一些(可能为乱序)的片段重新组装

但是？我怎么判断他们的数据 有个标志？

确实是这样 有个 index 这个lab要实现的功能并不多

要求：

TCP sender 将其字节流分成短段（每个子串不超过约1460字节），以便它们都适合数据报。但是网络可能会重新排序这些数据报，或者丢弃它们，或者不止一次地传递它们。接收器必须将这些段重新组合成它们开始时的连续字节流。

所以我们要做的：

  • 判断是否重复？
  • 是否有缺失？
  • 重新排序

考虑一下需要增加的变量 ：

需要搞一个来记录一下是否出现过？或者说判断deque中相对应的 index 是否为空？

但我们只有两种插入的方法 头插和尾插

最好的方法感觉就是先给他排好序再插到 _buffer 里面

然后再来一个write 直接就写进去了

所以 https://blog.csdn.net/liitdar/article/details/80498634

找到了 insert 方法

如果是空格就给他替换掉？不是空格就跳过？

~~看来不能直接全部replace 还是先 insert 再说~~~~

真实地情况

image-20221103160844647

可以看到的是 他的 capacity 包括了两个部分 第一部分是 已经存到 ByteStream 的 _bufffer 中的

第二部分是 已经收到的但暂时存起来的

问题来了 什么时候放到 auxiliary storage 中？

如果 待 push 的 index 不等于 绿色中最后一个 segment 的 index +1 就需要放进 auxiliary storage 中等待

map 能用吗？学一下 c++的map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Construct a `StreamReassembler` that will store up to `capacity` bytes.
StreamReassembler(const size_t capacity);


// Receive a substring and write any newly contiguous bytes into the stream,
// while staying within the memory limits of the `capacity`. Bytes that would
// exceed the capacity are silently discarded.
//
// `data`: the substring
// `index` indicates the index (place in sequence) of the first byte in `data`
// `eof`: the last byte of this substring will be the last byte in the entire stream
void push_substring(const string &data, const uint64_t index, const bool eof);


// Access the reassembled ByteStream (your code from Lab 0)
ByteStream &stream_out();


// The number of bytes in the substrings stored but not yet reassembled
size_t unassembled_bytes() const;


// Is the internal state empty (other than the output stream)?
bool empty() const;

首先 搞明白一个东西 拿什么东西 去存组成的stream

之前的 ByteStream 

1
2
3
4
5
6
7
ByteStream::ByteStream(const size_t capacity)
        : _buffer()
        , _capacity_size(capacity)
        , _written_size(0)
        , _read_size(0)
        , _end_input(false)
        , _error(false) {}

这个函数的实现是重点

1
2
3
4
5
6
7
8
9
10
11
    //! \brief Receive a substring and write any newly contiguous bytes into the stream.
    //!
    //! The StreamReassembler will stay within the memory limits of the `capacity`.
    //! Bytes that would exceed the capacity are silently discarded.
    //!
    //! \param data the substring
    //! \param index indicates the index (place in sequence) of the first byte in `data`
    //! \param eof the last byte of `data` will be the last byte in the entire stream
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    DUMMY_CODE(data, index, eof);
}

超出了 throw eof

没有超出 把 &data 加到 _buffer 里面？ 需要先好好理解一下他这个 index

param index indicates the index (place in sequence) of the first byte in data

那我们用什么办法给他插入 deque 里面呢？

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
#include "stream_reassembler.hh"

// Dummy implementation of a stream reassembler.

// For Lab 1, please replace with a real implementation that passes the
// automated checks run by `make check_lab1`.

// You will need to add private members to the class declaration in `stream_reassembler.hh`

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

using namespace std;

StreamReassembler::StreamReassembler(const size_t capacity) :
    _output(capacity), // 我们的 _output 是 ByteStream  
					 // 即我们可以对他使用所有的 ByteStream 中的方法
    _capacity(capacity) {}

//! \details This function accepts a substring (aka a segment) of bytes,
//! possibly out-of-order, from the logical stream, and assembles any newly
//! contiguous substrings and writes them into the output stream in order.
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    // put segment into StreamReassembler

}

size_t StreamReassembler::unassembled_bytes() const { return {}; }

bool StreamReassembler::empty() const { return {}; }H

乱写了一点 过了 63% 明天再接着写 写的头晕了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    // put segment into StreamReassembler
    if (eof){
        
    }


    if (index == _location){
        _output.write(data);
        _location += data.size(); // 更新了之后应该再检查一遍是否有可以塞进去的？

        while (_substring_map.count(_location)){
            _output.write(_substring_map[_location]);
            _location += _substring_map[_location].size();
        }

    }else if(!_substring_map.count(index)){
        _substring_map.insert(std::map<int,std::string>::value_type(index,data));
    }
}