思维之海

——在云端，寻找我的星匙。

高等计算机网络

In

高等计算机网络。深入学习计算机网络体系结构、协议和算法，了解掌握计算机网络的最新研究成果，学习计算机网络的基本研究方法并能够初步开展计算机网络领域的相关研究。

References

课程：《高等计算机网络》，徐恪

Introduction

徐恪：计算机网络体系结构与高性能路由器、网络空间安全、赛博智能经济与区块链。

课程目标

  • 深入学习计算网络体系结构、协议和算法
  • 了解掌握计算机网络的最新研究成果（论文讨论）
  • 学习计算机网络的基本研究方法
  • 初步开展计算机网络领域的相关研究（课程项目）

相关课程

《计算机网络体系结构》——内容相当（最初的课，人数太多，为了开新课才有了“高等计算机网络”）

《计算机网络前沿研究》——注重SDN，数据中心网络，网络与AI等

《下一代互联网》——网研院的课，IPv6为核心的下一代互联网技术

主要教学内容

  • 介绍网络基础知识
  • 互联网发展历史
  • 网络体系结构详细介绍（强调基本算法和基本协议）
  • 课堂讨论、分组调研及课堂报告

注重系统性和整体性，形成网络大局观。

教材和参考书

《高级计算机网络》——徐恪、徐明伟

正在出新版，旧版已经脱销了。没有太大的必要看。

《计算机网络体系结构——设计、建模、分析与优化》

《Computer Networks》

考核方式

  • 论文阅读（30%）
    • 6篇500字+的阅读报告
      • 多交可以酌情加分（开始卷了）
  • 技术专题讨论（30%）
    • 45分钟专题报告
  • 课程项目（40%）
    • 选定研究/开发型项目，并完成课程报告

网络研究的基本问题

网络体系结构 Architecture

体系结构的准确描述是很难的。 网络的基本原则和机制?

  • 状态：状态的维护、更新和存储
  • 实名：实体如何命名。比如IP地址、域名
  • 名字、寻址、路由：这些功能函数的设计
  • 协议分层：Modularity of the protocol stack
  • 资源分配：公平性和（congestion control）
  • 安全性：网络安全
  • 管理：互联网的管理
  • 服务质量（QoS）：如何获得和请求服务质量

网络可以分为两大技术主题：

  • 网络基础理论：容量与可扩展性；最优化设计；控制理论；博弈论与机制设计；流量模型和网络行为学
  • 网络体系结构：网络分层与跨层设计；软件定义网络、主动网络、可编程网络、应用层网络、无线与移动网络、网络虚拟化；对组播和服务质量的支持；IPv6与下一代互联网

网络也可以分为三大应用主题：

  • 资源管理和分配：QoS，拥塞控制、流量工程
  • 网络管理：失效管理、配置管理、计费管理、性能管理、安全管理
  • 网络安全：完整性、机密性、可用性

网络与分布式系统

网络与分布式系统的界限日益模糊：

  • 网络本质上就是分布式系统
  • 互联网服务已经成为信息服务的基本模式

数据中心网络的资源管理和调度：

  • 数据中心分布式系统资源管理与网络流控和拥塞控制深度融合
  • 计算广告、推荐算法等也与网络资源使用密切相关

比特币与区块链：

  • 比特币就是运行在网络之上的P2P系统
  • 区块链是P2P网络、分布式共识、密码算法等多种技术融合的产物

网络与分布式系统的基础科学问题

网络领域科学问题：

  • 安全性
  • 开放性（扩展性）
  • 实时性

相互制约，相互平衡。

分布式系统领域科学问题：

  • 易用性和可编程性问题
  • 安全性问题
  • 一致性问题（共识问题）
  • 可靠性和可用性问题
  • 性能提升问题

通用人工智能：朱松纯老师正在准备搞这个方向，用小样本、小数据集来进行推理等操作。

网络研究的基本方法

文献阅读

  • 了解新领域，应该从综述论文入手
    • ACM Computing Surveys, IEEE Communications Surveys and Tutorials
    • Proceedings of the IEEE
    • Communications of the ACM, IEEE Computer
    • IEEE Personal Communications, IEEE Communications Magazine, IEEE Network
  • 通过顶级国际会议了解最新的研究成果
    • SIGCOMM，INFOCOM，MOBICOM，MOBIHOC，SIGMETRICS，GLOBECOM，ICNP
  • 充分利用网络资源
    • 图书馆电子资源（IEEE，ACM全文库）
    • google.com
    • scholar.google.com
  • 文献阅读
    • 【精致的笔记】
    • 关注作者和研究小组

网络模型与实验

模型：

  • 性能模型：排队论，Petri网（任丰原老师的课程）
  • 形式化模型：自动机，SDL（尹霞老师的课程）
  • 数学模型：优化理论（数学系相关课程），控制理论（自动化系相关课程），博弈论（网络科学与策略机制），图论，网络微积分

实验：

  • 测量、模拟、仿真和实现
  • 算法研究中，模拟最方便：ns-2, OPNET, MATLAB
  • 研究实际网络的行为，需要进行实际测量和观察
  • 协议研究需要仿真和实现：PlanetLab

Top-10 tips for writing a paper

  1. Every paper tells a story
  2. Write top down
  3. Introduction: crucial, formulaic
  4. Master the basics of organized writing
  5. Put yourself in place of the reader
  6. No one (not even your mother) is as interested in this topic as you
  7. State the results carefully
  8. Don’t overstate/understate your results
  9. Study the art of writing
  10. Good writing takes times

The Internet

根据排队论，分组交换的效率较高。

互联网组织

Internet Society (ISOC)

https://www.internetsociety.org/

Internet Hall of Fame

Pioneers: design and development of the Internet with exceptional achievements

Innovators: made outstanding technological, commercial, regulatory or policy advances and helped to expand the Internet’s positive impact on the lives of others

Global Connectors: who have made major contributions to the growth, connectivity, and use of the Internet

Internet Engineering Task Force (IETF)

The IETF is the protocol engineering and development arm of the Internet

Subdivided into many working groups, which specify Request For Comments or RFCs

The Internet Engineering Steering Group (IESG)

The IESG is responsible for technical management of IETF activities and the Internet standards process

Composed of the Area Directors of the IETF working groups

看起来很民主很透明，但IETF实际上仍然是一个中心化组织，其中最重要的部门就是IESG。下面的这些主席对标准化工作有几乎绝对的话语权。

Futurewei 跟华为关系比较密切，常常道华为开会来跟进新技术的标准化工作。

Internet Research Task Force (IRTF)

做一些标准化的工作。

The Internet Research Task Force is composed of a number of focused, long-term and small Research Groups

Internet Architecture Board (IAB)

互联网一个元老院QAQ荣誉很高。

The IAB is responsible for defining the overall architecture of the Internet, providing guidance and broad direction to the IETF

目前有做一些funding。

Internet Corporation for Assigned Names and Numbers (ICANN)

协调地址、域名等等。

  • To reach another person on the Internet you have to type an address into your computer — a name or a number
  • That address must be unique so computers know where to find each other
  • ICANN coordinates these unique identifiers across the world. Without that coordination, we wouldn’t have one global Internet

边缘论

“核心简单，边缘复杂”。

边缘论的解释：

  • One interpretation:
    • A function can only be completely and correctly implemented with the knowledge and help of the applications standing at the communication endpoints
  • Another: (more precise…)
    • a system (or subsystem level) should consider only functions that can be completely and correctly implemented within it
  • Alternative interpretation: (also correct …)
    • Think twice before implementing a functionality that you believe that is useful to an application at a lower layer
    • If the application can implement a functionality correctly, implement it a lower layer only as a performance enhancement

层次化选择

拥塞控制究竟应该放在哪一层?

  • 应用层
    • 交给软件来做，那么有的人可能根本不会去管拥塞控制，每个人写的也不一样
  • 链路层
    • 交给交换机/路由器，很可能不是所有人都用得到，那么对底层硬件资源的消耗是不太理想的（需要维护大量额外的参数和控制信号）。比如，一些传输流媒体的用户可能不太care拥塞控制

Internet 传输层

UDP

早期UDP在以太网上是广播，所以很占带宽，也就是说，只要有一些视频媒体的流量，其他人可能就做不了什么事情了。

TCP

分组交换没法解决拥塞问题。

——提出TCP的自适应的想法。

拥塞控制和拥塞避免。

  • 避免：尽量别出事
    • 93年TCP Vegas

BIC：快速找最合适的窗口大小。

TCP Header

Flags：RESET可以用来断开连接，所以常常用来干扰某个TCP连接。

可靠数据传输

可靠数据传输：IP层是不可靠的，需要在TCP中加入检查和确认等机制。

两种冗余方式：

  • 空间冗余：在编码上的冗余
  • 时间冗余：确认+超时重传机制

可靠性机制

Mechanisms:

  • Checksum: detects corruption in pkts & acks
  • ACK: “packet correctly received”
  • Duplicate ACK: “packet incorrectly received”
  • Sequence number
  • Timeout only at sender

Provides reliable transmission over:

  • A forward & reverse channel with bit-errors
  • Detects duplicates of packets/acks
  • NAKs eliminated
  • A forward & reverse channel with packet-errors (loss)

三次握手

3-way-handshake

TCP窗口流控

MSS：最大段长，默认536字节。

越大效率越高，但同时如果丢包损失也越高。

可以和MTU最大传输单元进行适配。避免中途重新分配的时延。

TCP流控：发送的包不要超过接收窗口。

TCP拥塞控制

网络中堵塞之后，出现丢包问题，丢包又触发了重传……丢包、重传、丢包、重传……这便是TCP拥塞的特征。

Van Jacobson: save the Internet.

拥塞控制和拥塞避免

让传输速率保持在knee附近是比较明智的选择。

动态的自适应方案

基于网络的模型：预先分配每个节点的网络流量限制。比如，ATM、故宫。

拥塞控制的目标：

  • 稳定
    • 一个动态系统的均衡点
  • 有效
  • 公平
    • 公平的问题比较复杂。。
    • 提前定义规则，按照可预测的方式去分配资源

Max-min fairness：

  • 没有拥塞时：$f = max(x_i)$
  • 否则：$\sum_j \text{min}(x_i,f)=c$

ACK自时钟控制分组收发：每收到一个包，发送一个ACK。保持进出均衡。

保持在knee点附近波动。实现自适应。

TCK：慢加快减。收敛到平衡点。

TCK Reno：快重传，快恢复。（跳过了慢启动）

TCK Vegas：平滑的发送窗口。不会丢包。（前提时buffer足够大）

算法主要看延迟，即RTT时间梯度。

BIC：对RTT最优窗口值进行二分查找。但RTT更小的人更容易拿到窗口，不公平。

CUBIC：试图解决BIC的公平性问题，找到一种RTT无关的最优窗口查找算法。

————————————————

BBR

找到带宽最大和延迟最小的点。但它们之间是相关的，所以研究人员一开始觉得是不可能的。

BBR：分别估计，并计算时延带宽积。按照这个值去优化。

主动测量。测量短时间（10s内）的最小RTT。

BBR的问题：

  • 公平性问题
  • ACK压缩问题（一个ACK应答多个报文，如200个）
  • 应用重启时如何快速恢复带宽
  • 不匹配的接收窗口

BBR对于数据中心网络的应用还存在一些问题。

RED等主动队列管理算法

提前在队列还没有满的时候，提供一些预警信号。

随着队列变长，预警强度也随之增加。

——关键是早一点有效沟通队列的信息。

  • 不是全体通知
    • 引入概率，抽签通知，保证公平性

FRED：加入对flow rate的自适应。

优化问题，求解全局用户效用之和的最大化。

凸优化——对偶问题。变成一个机器学习的问题。

TCP & AQM。拥塞控制变成一个在互联网上求解最优化的问题。

拥塞控制是Internet最重要的问题之一。

Internet 服务质量

网络研究中主要关注网络保证性能的能力。

和性能相关的主要的QoS参数：

  • 带宽
  • 延迟
  • 丢包率

交叉流量是不可预测的。

集成服务，对资源进行分发预留。

课程项目

项目调研

DDoS

协作学习。然而协作学习其实就是无中心化的分布式学习。

NetFPGA

https://netfpga.org/

NetFPGA可以非常方便的使得研究人员或者高校学生搭建一个高速，硬件加速的网络系统。目前NetFPGA已经融入了斯坦福大学的课程中，教授学生如何设计硬件传送、传发数据的GigE的交换机与路由器。