ReadMe

笔记是用飞书做的，下面的内容为直接复制粘贴，也可以直接用飞书链接查看

大部分都做的特别认真，只有第七章4G5G部分有点划水

可供复习参考

今年期末考的点很细~~（很怪，我怎么记得谁发明了TCP/WIFI/Ethernet…）~~，需要将大黑书的部分仔细阅读并牢记后才有可能打高分（好吧，可能是因为我菜，且记忆力已经不太好了

平时可以不去听课，但是有小测~~（小测说是闭卷，其实大多数同学都会Ctrl F PPT，并且只要不被老师发现可以直接抄同学的/对答案）~~，小测题目在后期就不可见了，建议做完一次小测就将题目和答案保存下来，期末可能会涉及到（今年期末貌似第一道选择题就是小测的原题）

除了期末闭卷题目奇怪要背诵外，平时的任务量接近于零，四次作业（似乎只要做了就是100分？反正我自己是这样的），每章结束后会有雨课堂小测，全是单选题。

1 Computer Networks and the Internet

1.1 What is the Internet?

描述方式一：通过硬件和软件组件

接入互联网的设备为主机host(端系统end system)，end system通过通信链路comunication link和分组交换机packet switch连接到一起
Packet switch类型有路由route和链路层交换机link-layer switch，它们都要向最终目的地发送分组。link-layer switch通常用于接入网中，而route通常用于网络核心中
ISP：Internet Service Provider，端系统通过ISP接入因特网，每个ISP自身就是一个由多台分组交换机和多段通信链路组成的网络。ISP互联，较低层的ISP通过国家国际的较高层ISP互联，较高层ISP彼此直接互联。
协议protocols控制信息的发送与接收
Internet standards: 由因特网工程任务组IETF(Internet Engineering Task Force)研发，IETF的标准文档称为请求评论RFC(Request For Comment)，RFC文档定义了TCP/IP/HTTP/SMTP等协议

描述方式二：根据基础设施向分布式应用提供的服务

Infrastructure provides service to applications
Provides programming interface to distributed applications

协议protocol

协议定义了在两个或多个通信实体之间交换的报文的格式和顺序format and order，以及报文的发送/接收或其他事件所采取的操作action

1.2 Network edge网络边缘

Internet structure:

Network edge: host(host可进一步划分为客户client和服务器server，服务器server通常属于大型数据中心data center)
Access networks, physical media(接入网，将端系统物理连接到其边缘路由器的网络): communication links
Network core: routers, network of networks (ISPs)

How to connect end systems to edge router?

Residential access nets(家庭接入：DSL\电缆、FTTH和5G固定式无线)
Institutional access networks(企业接入school, company)
Mobile access networks(广域无线接入WIFI, 4G/5G)

Residential access nets家庭接入

数字用户线(DSL，Digital Subscriber Line)和电缆网络(cable Internrt access)

数字用户线DSL：use existing telephone line to central office DSLAM（data over DSL phone line goes to Internet，voice over DSL phone line goes to telephone net）

电缆网络：由于系统中既应用了光纤也应用了同轴电缆，故常被称为混合光纤同轴(Hybrid Fiber Coax, HFC)；共享广播媒体（多用户同时下载时接收速率远低于电缆总计的下行速率，且由于上行信道也是共享的，需要一个分布式多路访问协议来协调传输和避免碰撞）

光纤到户(Fiber To The Home, FTTH)

Institutional access networks企业接入

mix of wired, wireless link technologies, connecting a mix of switches and routers

Ethernet: wired access at 100Mbps, 1Gbps, 10Gbps

WiFi: wireless access points at 11, 54, 450 Mbps

Links物理媒介

1.3 Network core网络核心

packet-switching分组交换: hosts break application-layer messages into packets

存储转发传输Store-and-forward transmission：交换机必须确保接收到整个分组后才能开始向输出链路传输该分组的第一个比特，所以就会存在时延，总时延是2L/R（若没有这个机制，则总时延是L/R）。一般情况，通过由N条速率均为R的链路组成的路径，从源到目的地发送一个分组，此时端到端时延为NL/R

排队时延和分组丢失queuing and loss：①queuing：分组到达的速率大于被处理的速率，分组要承受输出缓存的排队时延queuing delay；②loss：由于缓存空间有限，当一个到达的分组发现缓存被其他等待传输的分组完全充满的时候，到达的分组或已经排队的分组之一将被丢弃

转发表和路由选择协议：当源主机要向目的端系统发送一个分组时，源在该分组的首部中包含了目的地的IP地址。每台路由器都具有一个转发表（forwarding table）

Circuit switching电路交换

会预留资源（缓存、链路传输速率），每个端到端电路交换会均分传输速率

通过频分复用(Frequency-Division Multiplexing, FDM)或时分复用(Time-Division Multiplexing, TDM)来实现的

Packet switching vs Circuit switching

Packet switching is great for bursty data(激增的数据)，会有时延和包丢失

Circuit switching 会保留资源，但是某种程度上也会造成资源的浪费，且每条电路的传输速率会降低

趋势是朝着分组交换方向发展

Internet structure：

1.4 Performance: loss丢包, delay时延, throughput吞吐量

四种时延

节点处理时延nodal processing delay
- 检查分组首部
- 决定将该分组导向何处determine output link
- 检查比特级别的差错check bit errors
排队时延queuing delay
- time waiting at output link for transmission
- 取决于路由的拥塞情况(congestion level)
传输时延transmission delay
- 仅当所有已经到达的分组被传输后，才能传输刚到达的分组
- 若L为分组长度，R为链路传输速率，则传输时延为L/R。这是将一个比特推向链路所需要的时间（类比发射
传播时延propagation delay
- 一旦一个比特被推向链路，该比特需要向路由器B传播，从该链路的起点到路由器B传播所需要的时间就是传播时延
- 若d是路由器A和B之间的距离，S，是该链路的传播速率，则传播时延为d/s

排队时延与丢包

流量强度traffic intensity：La/R

考虑所有的时延（除排队时延外，因为其可以不计），端到端时延等于N(d_proc + d_trans + d_prop)，其中d_trans = L/R

吞吐量（以bps计）
1. 瞬间吞吐量instantaneous throughput：主机B接收到该文件的速率
2. 平均吞吐量average throughput：若主机接收到所有F bit用了T s，则平均吞吐量为F/T bps
3. 瓶颈链路：
4. 服务器–(Rs)–路由器–(Rc)–客户，则吞吐量取Rs和Rc之间的更小者，故从服务器向客户传输一个F bit的大文件所需要的时间是F/min{Rs, Rc}

1.5 Protocol layers, service models协议层次及其服务模型

Layered Internet protocol stack：

1.6 Security

经因特网将有害程序放入计算机
- 恶意软件malware，且会自我复制self-replicating（从被感染的主机寻求进入因特网上的其他主机）
DoS（拒绝服务攻击，Denial-of-Service attack）：
嗅探分组packet sniffing：在无线传输设备的附近放置一台被动的接收机，该接收机能得到传输的每个分组的副本，包含各种敏感信息
IP哄骗 IP spoofing：injection注入 of packet with false source address

防御方式：

2 The Application Layer

2.1 Principles of network applications

When creating a network app：需要编写将在多个端系统上运行的软件，不需要写在网络核心设备如路由器和链路层交换机上运行的软件。网络核心设备不作用于应用层而是作用于较低的层次，特别是在网络层及其以下，这种基本的设计就是让应用软件与终端系统隔离。
应用体系结构application architecture

Client-server architecture
P2P architecture

Processes communicating进程通信
1. ①客户与服务器进程
2. 当多个进程运行在相同的端系统上时，它们使用进程间通信机制相互通信
3. 在两个不同端系统上的进程，通过跨越计算机网络交换报文（message）
4. client客户：发起通信（即在该会话开始时发起与其他进程的联系）的进程
5. server服务器：在会话开始后等待被联系的进程
6. 在P2P文件共享的某些应用中，一个进程能够既是客户又是服务器，但是仍然按照上述划分要求划分

②进程与计算机网络之间的接口：Sockets

网络应用程序由成对的进程组成，这些进程通过网络相互发送报文

socket是同一台主机内应用层与运输层之间的接口

进程可类比于房子，socket类比于它的门

③Addressing processes进程寻址

利用IP地址标识主机

标识符包括与主机上的进程关联的IP地址和端口号port number。有了这两个数据就可以给服务器进程发送报文了

The transport service an app need

可从四个方面对应用程序服务要求进行分类：

可靠数据传输reliable data transfer
吞吐量throughput
- 带宽敏感的应用bandwidth-sensitive application：具有吞吐量要求的应用程序
- 弹性应用elastic application：能根据当时可用的带宽利用可供使用的吞吐量
定时timing
- 用于实时交互式应用
安全性security

因特网提供的运输服务：

TCP具有拥塞控制机制而UDP不具备；TCP能无差错、按适当顺序交付所有发送的数据，而UDP不保证该报文将到达接收进程，且到达的报文可能是乱序到达的

TCP安全：无论是TCP还是UDP都没有提供任何加密机制——>使用一种加强版本的TCP，TLS（运输层安全Transport Layer Security）。当一个应用使用TLS时，发送进程向TLS socket传递铭文数据，发送主机中的TLS则加密该数据，并将加密的数据传递给TCP socket，加密的数据经因特网传送到接收进程中的TCP socket，该socket将加密数据传递给TLS，由其进行解密。

应用层协议an application-layer protocol

一个应用层协议定义了应用的进程是怎么在不同的终端系统运行并彼此发送报文的，特别的，应用层协议定义了：

Types of messages exchanged交换的报文的类型，举例，请求报文和响应报文
Message syntax不同的报文类型的语法，比如报文中的各个字段及这些字段是如何描述的
Message semantics报文中各个字段的语义，就是这些字段中信息的含义
Rules确定一个进程何时以及如何发送报文，对报文进行响应的规则

Open protocols：有些应用层协议是由RFC文档定义的，因此它们位于公共域中，everyone has access to protocol definition。如HTTP, SMTP

Proprietary protocols：如Skype, Zoom

2.2 Web and HTTP

HTTP（超文本传输协议HyperText Transfer Protocol）
1. ①概述：
2. HTTP是Web的应用层协议，由两个程序实现，一个client程序和一个server程序
3. HTTP使用TCP
4. HTTP is stateless（无状态协议）：因为HTTP服务器不会保留clients的任何信息，所以如果我们连续请求两次同一个对象，它就会回复两次

②HTTP两种类型的连接方式：(HTTP默认使用持续连接)

非持续连接non-persistent connection：为每对client-server建立单独的TCP连接
- 一个web页面上可能有多个object，而多个object的下载需要多个连接（因为一个html文件上的object实际上是引用，所以要额外下载）
- 每个TCP连接只传输一个请求报文和一个响应报文，每个TCP连接在服务器发送一个对象后关闭，即该连接并不为其他的对象而持续下来
- RTT(往返时间，Round-Trip Time)：一个数据包从client到server然后再返回的时间，RTT包括了中间路由和交换机处的传输延迟和排队延迟，还有处理延迟
  - HTTP response time(per object)：每个object都将会有两个RTT的延迟——一个建立TCP连接，一个请求和回复
  - 故Non-persistent HTTP response time = 2RTT+ file transmission time
持续连接persistent connection：使用同一个TCP连接
- client sends requests as soon as it encounters a referenced object（而不必等待对未决请求的回答）
- as little as one RTT for all the referenced objects (cutting response time in half)

③HTTP报文格式

请求报文
- 请求行request line：方法字段、URL字段和HTTP版本字段
- 首部行header line：
  - Host
  - Connection: close
  - User-agent
  - Accept-language
响应报文
- 初始状态行status line：协议版本字段、状态码和相应状态信息
- 首部行header line
- 实体体entity body

Cookie：用户与服务器的交互

四个组件：

cookie header line of HTTP response message
cookie header line in next HTTP request message
cookie file kept on user ’ s host, managed by user ’ s browser
back-end database at Web site
Web caches缓存（也叫代理服务器proxy server）

Web caches既是server又是client，server for original requesting client；client to origin server

好处：

reduce response time for client request
reduce traffic on an institution’s access link
Internet is dense with caches，enables “poor” content providers to more effectively deliver content

Conditional GET：允许缓存器证实它的对象是最新的

方法：在请求报文中包含一个“If-modified-since: ”首部行，首部行的值等于之前服务器发送的响应报文中的“Last-Modified: ”
作为条件GET方法的响应，该Web服务器仍会发送一个响应报文，但并没有在该响应报文中包含所请求的对象，为了避免浪费带宽

HTTP/2
1. 主要目标是减小感知时延

队首阻塞Head Of Line(HOL) blocking：经单一TCP连接发送一个Web页面中的所有对象存在队首阻塞问题

HTTP/2解决HOL阻塞的方案是将每个报文分成小帧，并且在相同TCP连接上交错发送请求和响应报文

——>HTTP/2的重要改进：

将一个HTTP报文分成独立的帧、交错发送它们并在接收端将其装配起来
允许服务器为一个客户请求而发送多个响应。即除了对初始请求的响应外，服务器能够向该客户推额外的对象，而无需客户再进行任何请求

HTTP/3: adds security, per object error- and congestion-control (more pipelining) over UDP

2.3 E-mail, SMTP, IMAP

E-mail：三个主要组成部分
1. User agents用户代理
2. Mail servers邮件服务器
3. SMTP简单邮件传输协议

一个简单的邮件发送过程：从发送方的用户代理开始，传输到发送方的邮件服务器，再传输到接收方的邮件服务器，然后在这里被分发到接收方的邮箱中

SMTP：
1. SMTP是 Internet email最重要的应用程协议，它使用的是TCP协议在mail server间进行传输
2. client side运行于发送方mail server，server side运行于接收方mail server，也就是每个mail server都会同时运行client side和server side的SMTP
3. Three phases of transfer:
  - SMTP handshaking(greeting)
  - SMTP transfer of messages
  - SMTP closure
4. 发送方和接收方直接是直接传递，无论距离，都是直接连接两个服务器
5. SMTP和HTTP的比较：
  - 使用SMTP传送邮件前要将二进制多媒体数据编码为ASCII码，传输后还要解码。而用HTTP传输前不需要将多媒体数据编码为ASCII码
邮件报文格式

Header lines
- To: (必含）
- From: （必含）
- Subject: （可能含）
Blank line
Body

邮件访问协议mail access protocol

接收邮件方的用户代理不能使用SMTP得到报文，因为取报文是一个拉操作，而SMTP是一个推协议。此时有两种方式，若接收方使用的是基于Web的电子邮件或智能手机上的客户端（如Gamil），则用户代理通过HTTP来取邮件；另一种方式是使用IMAP（因特网邮件访问协议）

2.4 The Domain Name System DNS

DNS：域名系统，实现主机名到IP地址转换的目录服务
1. DNS是：
2. 一个由分层的DNS服务器实现的分布式数据库distributed database
3. 一个使得主机能够查询分布式数据库的应用层协议

DNS协议运行在UDP之上，使用53号端口

DNS通常是由其他应用层协议所使用的，包括HTTP和SMTP，将用户提供的主机名转换为其背后的IP地址

DNS也是通过client-server模式

DNS服务：
1. Hostname-to-IP-address translation主机名到IP地址的转换
2. Host aliasing主机别名：区别规范主机名canonical hostname
3. Mail server aliasing邮件服务器别名
4. Load distribution负载分配：因为某个站点可能分布在多台服务器上，具有不同的IP地址，当client对映射到某地址集合的名字发出一个DNS请求时，该服务器用IP地址的整个集合进行响应，但在每个回答中循环这些地址次序
DNS工作机理
1. ①Why not centralize DNS?
2. 单点故障sigle point of failure
3. 通信容量traffic volume
4. 远距离的集中式数据库distant centralized database
5. 维护maintenance

——>分布式、层次数据库a distributed, hierarchical database

②三种DNS服务器以及结构：

③本地DNS服务器local DNS server：

④DNS name resolution名称解析：从请求主机到本地DNS服务器的查询是递归的，其余的查询是迭代的

Iterated query
Recursive query

⑤DNS缓存：

cache entries timeout (disappear) after some time (TTL)
cached entries may be out-of-date
除少数DNS查询以外，根服务器被绕过了

DNS记录和报文

①共同实现DNS分布式数据库的所有DNS服务器储存了资源记录（Resource Record, RR），RR提供了主机名到IP地址的映射

②DNS query and reply messages both have the same format

TODO

DNS Security

DDoS attack：由于根服务器可以绕过，所以针对TLD服务器的DDoS攻击更有效
Spoofing attack欺骗伪造：intercept DNS queries, returning bogus replies

2.5 P2P applications

文件分发时间：
1. client-server：（分发时间呈线性增长）
  - 服务器必须向N个对等方的每个传输该文件的一个副本 NF/u_s
  - 每个client必须下载文件副本 F/d_min
2. P2P：（分发时间有上界）
  - 每个对等方都能够帮服务器分发该文件。当一个对等方接收到某些文件数据，它能够使用自己的上载能力重新将数据分发给其他对等方
  - 在分发的开始，只有服务器具有文件 F/u_s
  - 具有最低下载速率的对等方不能以小于F/d_min的分发时间获得所有F bit F/d_min
  - 系统整体的总上载能力等于服务器的上载速率加上每个单独的对等方的上载速率 NF/(u_s + u1+ … + u_N)
BitTorrent：一种用于文件分发的流行P2P协议
1. torrent：参与一个特定文件分发的所有对等方的集合
2. chunk：在一个torrent中的对等方彼此下载等长度的文件块
3. tracker追踪器：当一个对等方加入某torrent时，它向追踪器注册自己，并周期性地通知追踪器它仍在该torrent中
4. Requesting chunks：最稀缺优先rarest first
5. Sending chunks：tit-for-tat一报还一报
  - 每过30秒A将随机地选择一名新的对换伴侣并开始与那位伴侣进行对换。如果这两名对等方都满足此对换，它们将对方放入其前4位列表中并继续与对方进行对换，直到该对等方之一发现了一个更好的伴侣为止

2.6 video streaming and content distribution networks

HTTP流和DASH
1. HTTP流：
  - 视频只是储存在HTTP服务器中作为一个普通的文件，每个文件有个特定的URL，当用户要看该视频时，客户与服务器创建一个TCP连接并发送对该URL的HTTP GET请求
  - 缺陷：对不同客户，或者对相同客户的不同时间而言，客户可用的带宽大小有很大不同
2. DASH（经HTTP的动态适应性流， Dynamic Adaptive Streaming over HTTP）
Content distribution networks(CDN)内容分发网

to stream content (selected from millions of videos) to hundreds of thousands of simultaneous users

CDN通常采用两种不同的服务器安置原则：

深入enter deep：在遍及全球的接入ISP中部署服务器集群来深入到ISP的接入网中，目标是靠近端用户
邀请做客bring home：通过在少量的关键位置建造大集群来邀请到ISP做客。不是将集群放在接入ISP中，这些CDN通常将它们的集群放置在因特网交换点IXP

大多数CDN利用DNS来截获和重定向请求

任何CDN部署，其核心是集群选择策略cluster selection strategy，即动态地将客户定向到CDN中的某个服务器集群或数据中心的机制

3 The Transport Layer

3.1 Transport-layer services

运输层协议是在端系统中而不是在路由器中实现的，即端系统中有应用层、运输层、网络层、链路层和物理层，而路由器中只有网络层、链路层和物理层
Transport protocols actions in end systems:
1. Sender: breaks application messages into segments, passes to network layer
2. Receiver: reassembles segments into messages, passes to application layer
运输层 vs 网络层
1. 运输层： communication between processes
2. 网络层：communication between hosts
3. 运输协议能提供的服务常常受限于底层网络层协议的服务模型
4. 然而，即时底层网络协议不能在网络层提供相应的服务，运输层协议也能提供某些服务
两种运输层协议：TCP&UDP

3.2 Multiplexing and demultiplexing多路复用与多路分解

一个进程可能有一个或多个套接字，接收主机怎样将一个到达的运输层报文段定向到适当的套接字

Multiplexing as sender：handle data from multiple sockets, add transport header(later used for demultiplexing)
Demultiplexing as receiver：use header info to deliver received segments to correct socket

多路分解怎样work的

Host receives IP datagrams. 每个IP数据报中有源IP地址和目的地IP地址，每个数据报还带有传输层报文，这个报文里面有源和目的地的端口号

Host uses IP addresses & port numbers to direct segment to appropriate socket

无连接的多路复用与多路分解connectionless demultiplexing

当创建一个UDP socket时，运输层自动地为该socket分配一个端口号，UDP套接字由一个二元组全面标识的，中有目的地IP地址和目的地端口号

when receiving host receives UDP segment: checks destination port # in segment and directs UDP segment to socket with that port #，所以具有相同目的地端口号的报文段将通过相同的目的socket被定向到相同的目的进程

面向连接的多路复用与多路分解connection-oriented demultiplexing

TCP套接字是由一个四元组标识的，中有源IP地址、源端口号、目的地IP地址、目的地端口号，这四个值全部都会被用上，所以具有不同源IP地址或源端口号的TCP报文段将被定向到两个不同的套接字（区别于UDP报文段）
服务器主机可以支持很多并行的TCP套接字，每个套接字与一个进程联系，并由其四元组来标识每个套接字

总结

UDP：多路分解只使用destination port number
TCP：多路分解使用四元组

Multiplexing/demultiplexing happen at all layers

3.3 Connectionless transport: UDP

为什么选用UDP

关于发送什么数据以及何时发送的应用层控制更为精细。TCP的拥具有拥塞控制机制，它保证报文的可靠交付，却不管可靠交付需要多少时间。实时应用通常要求最小的发送速率，不希望过分的延迟报文段的传送，且能容忍一些数据丢失。
无需连接建立。UDP不需要任何准备即可进行数据传输。
无连接状态。TCP需要在端系统中维护连接状态，包括接收和发送缓存、拥塞控制参数以及序号与确认号的参数。UDP不维护连接状态，也不追踪这些参数
分组首部开销小。每个TCP报文段都有20字节的首部开销，而UDP仅有8字节的开销

UDP常用于

流式多媒体streaming multimedia apps
DNS
SNMP网络管理数据
HTTP/3（也可以通过在应用程序自身中建立可靠性机制来实现可靠数据传输）

UDP报文段结构
UDP检验和：为了确定当UDP报文段从源到达目的地移动时，其中的比特是否发送了改变

怎样计算检验和：

将所有16比特的字相加，如果最后结果有溢出，则将溢出的那个数加到最后一个数上，得到的结果再取反码（所有的0换成1，所有的1换成0）

在接收方，将原有的16比特的字连带检验和相加，和应该全是1，若某一比特为零，则出了差错

3.4 Principles of reliable data transfer

数据可以通过一条可靠的信道进行传输。借助于可靠信道，传输数据比特就不会收到损坏或丢失，而且所有数据都是按照其发送顺序进行交付
讨论基于可靠数据传输协议的下层协议也许是不可靠的，如TCP是在不可靠（IP）端到端网络层之上实现的可靠数据传输协议
可靠传输协议的流程图

可靠数据传输协议

①rdt1.0: reliable transfer over a reliable channel经完全可靠信道的可靠数据传输

rdt的发送端只通过rdt_send(data)事件接受来自较高层的数据，产生一个包含该数据的分组，并将分组发送到信道中。rdt_send(data)事件是由较高层应用的过程调用产生的
在接收端，rdt通过rdt_rcv(packet)事件从底层信道接收一个分组，从分组中取出数据，并将数据上传给较高层。rdt_rcv(packet)事件是由较低层协议的过程调用产生的

②rdt2.0: channel with bit errors经具有比特差错信道的可靠数据传输

几个概念：
- ACKs(acknowledgements)：receiver explicitly tells sender that pkt received OK
- NCKs(negative acknowledgements)：receiver explicitly tells sender that pkt had errors
- ARQ(Automatic Repeat reQuest)协议：sender retransmits pkt on receipt of NAK自动重传请求
- Stop and wait：sender sends one packet, then waits for receiver response（发送方不会发送一块新数据，除非发送方确定接收方已正确接收当前分组）
状态图

rdt2.0有一个致命错误：如果ACK/NAK受损会怎样？
- 如果一个ACK或NAK分组受损，发送方无法知道接收方是否正确接收了上一块发送的数据。此时不能直接重传retransmit，可能会造成重复duplicate

③rdt2.1：对于上述rdt2.0致命错误的处理

发送方和接收方的状态数都是以前的两倍，因为协议状态此时必须反映出目前正发送的分组或希望接收的分组的序号是0还是1

④rdt2.2：在有比特差错信道上实现的一个无NAK的可靠数据传输协议

和rdt2.1相比只是不用NAK而已

instead of NAK, receiver sends ACK for last pkt received OK
duplicate ACK at sender results in same action as NAK: retransmit current pkt
TCP uses this approach to be NAK-free

⑤rdt3.0: channels with errors and loss经具有比特差错的丢包信道的可靠数据传输

由于分组序号在0和1之间交替，rdt3.0也被称为比特交替协议

相当于在发送方处设置了一个倒计时：

发送方会在合理的时间内等待ACK

如果在此期间没有收到ACK，就会重新发送。

如果数据包（或ACK）仅被延迟（而不是丢失），则重传将是重复的

但是序列号已经处理了这个问题。接收方必须指定要ACK的数据包的序列号，这需要倒计时计时器。

流水线可靠数据传输协议pipelining

rdt3.0性能问题的核心在于它是一个停等协议。定义发送方（或信道）的利用率utilization为发送方实际忙于将发送比特送进信道的那部分时间与发送时间之比，即U_sender = (L/R) / (RTT + L/R)

解决这种性能问题的简单方法是：不以停等方式运行，允许发送方发送多个分组而无须等待确认

pipelining对于可靠数据传输协议的影响：

必须增加序号范围
需要在发送方和接收方进行缓存，保证数据包的顺序

pipelining的差错修复有两种基本方法：

回退N步 Go-Back-N, GBN
选择重传 Selective Repeat, SR

GBN/sliding-window protocol

发送方可以一次发送多个数据包，最多有N个未收到确认的数据包

接收方会回复一个累积确认，即只确认最后一个连续的数据包

如果接收方发现中间有一个数据包丢失了，它不会确认已经接收到的数据包，直到丢失的数据包被接收到为止

发送方会设置一个定时器来检测最早未收到确认的数据包

如果定时器超时，就会重新发送从这个未确认数据包开始的所有数据包

action：当某个包丢失时，滑动窗口会停在丢失的那个处，因为它没有返回ack，下次sender发送pkt时，不会滑动到期望的地方，而是从丢失的这个处再发送包括它在内的前一次发送的后面的数字，如下图

选择重传：通过让发送方仅重传那些它怀疑在接收方出错的分组而避免不必要的重传

发送方可以同时发送多达N个未确认的数据包，接收方会对每个已经接收到的数据包单独发送确认消息

发送方会为每个未确认的数据包分别维护一个定时器

当定时器超时时，只会重新发送该数据包，而不是之前未确认的所有数据包。

action：发送方只要收到了接收方传来的ACK滑动窗口就会往前移动一位；接收方如果收到的分组是当前滑动窗口的第一位，则交付分组、发送ACK并且往前移动一位，否则缓存分组，直到收到第一位的分组，则一次性交付缓存的连续分组，并移动窗口，即下面的两个方框所总结的：

举例：

3.5 Connection-oriented transport: TCP

Segment structure

与UDP一样：
- 首部包括源端口号和目的端口号以及检验和字段
首部还包括：
- 32比特的序号字段（seq, sequence number field）和32比特的确认号字段（ACK, acknowledgment number field）
  - 一个报文段的序号就算该报文段数据字段首字节的序号
  - 确认号是主机正在等待的数据的下一个字节序号
- 16比特的接收窗口字段receive window field
- 4比特的首部长度字段header length field
- 可选与变长的选项字段options field
- 6比特的标志字段flag field
往返时间RTT与重传超时间隔TimeoutInterval
- SampleRTT：从某报文段被发出到对该报文段的确认被收到之间的时间量。TCP仅为传输一次的报文段测量SampleRTT，绝不为已被重传的报文段计算
- EstimatedRTT：由于SampleRTT值会随着路由器的拥塞和端系统负载的变化而波动，所有采取对其取平均的方式。一旦获得一个新的SampleRTT，TCP就会根据下列公式来更新EstimatedRTT：EstimatedRTT = (1-alpha)*EstimatedRTT + alpha * SampleRTT，常取alpha为0.125（这种平均被称为指数加权移动平均EWMA）
- DevRTT：用于估算SampleRTT偏离EstimatedRTT的程度，DevRTT = (1-beta)DevRTT + beta|SampleRTT - EstimatedRTT|，SampleRTT波动越大，DevRTT值越大，常取beta为0.25
- TimeoutInterval = EstimatedRTT + 4*DevRTT （EstimatedRTT加上一定余量，当SampleRTT值波动较大时，这个余量应大一点）

Reliable data transfer

简化版：

TCP sender：三个事件

event: data received from application
event: timeout
event: ACK received

TCP receiver：ACK generation

TCP快速重传fast retransmit：一旦收到3个冗余ACK，TCP就执行快速重传，即在该报文段定时器过期之前就重传丢失的报文段

Flow control流量控制

TCP通过让发送方维护一个接收窗口（receive window）的变量来提供流量控制。而由于TCP是bidirectory，所以在连接两端的发送方都各自维护一个接收窗口。

rwnd = RcvBuffer - [LastByteRcvd - LastByteRead]

发送方的主机A在该连接的整个生命周期须保证LastByteRead - LastByteAcked <= rwnd

TCP receiver “advertises” free buffer space in rwnd field in TCP header

Connection management

在发送包括数据的报文段之前client和server需要3次握手（three-way handshake）来创建连接

为什么两次握手不行？
- 为了实现可靠数据传输， TCP 协议的通信双方，都必须维护一个序列号，以标识发送出去的数据包中，哪些是已经被对方收到的。三次握手的过程即是通信双方相互告知序列号起始值，并确认对方已经收到了序列号起始值的必经步骤
- 如果只是两次握手，至多只有连接发起方的起始序列号能被确认，另一方选择的序列号则得不到确认
建立连接/三次握手过程：
- 第一步：client端的TCP向server端的TCP发送一个SYN报文段，其中SYN比特被置为1，具有初始序号client_isn
- 第二步：server会从收到的数据报中提取TCP SYN报文段，为该TCP连接分配TCP缓存和变量，并向client发送允许连接的报文段SYNACK报文段，其中SYN被置为1，且包含server_isn
- 第三步：当client收到SYNACK报文段后，也要给该连接分配缓存和变量，并向server发送另一个报文段，此报文段对server允许连接的报文段进行确认（client通过将server_isn+1放置到TCP报文段首部的确认字段来完成该工作）。由于此时连接已经建立，所以该SYN被置为0
- 即client— SYN = 1, seq = client_isn —> server
- server— SYN = 1, seq = server_isn, ack = client_isn+1 —> client
- client— SYN = 0, seq = client_isn + 1, ack = server_isn+1 —> server
关闭一个TCP连接：
- client关闭— FIN=1 —> server
- server— ACK —> client
- server关闭— FIN=1 —> client
- client—ACK—>server

3.6 Principles of congestion control

informally: “too many sources sending too much data too fast for network to handle”

三种情况（复杂度逐渐升高）：

两个发送方和一台具有无穷大缓存的路由器

两台主机（A和B）都有一条连接，且这两条连接共享源与目的地之间的单跳路由

吞吐量只能拿到R/2.这个吞吐量是由于两条连接之间共享链路容量造成的。无论主机A和主机B的发送速率设置为多高，都不可能超过R/2的吞吐量
当分组的到达速率接近链路容量时，分组会有巨大的排队时延

两个发送方和一台具有有限缓存的路由器

两个结果：当分组到达一个已满的缓存时会被丢弃；由于每条连接都是可靠的，所以被丢弃的分组会被发送方重传

三种情况：

理想情况：sender sends only when router buffers available
情况二：发送方仅当在确定了一个分组已经丢失时才重传
- 网络拥塞的代价：发送方必须执行重传以补偿因为缓存溢出而丢弃/丢失的分组
情况三：发送方提前发生超时并重传在队列中已被推迟但还未丢失的分组
- 网络拥塞的代价：发送方在遇到大时延时所进行的不必要重传会引起路由器利用其链路带宽来转发不必要的分组副本

4个发送方和具有有限缓存的多台路由器及多跳路径

不同的流量会在同一路由器处为有限缓存空间而竞争

网络拥塞的代价：当一个分组沿一条路径被丢弃时，每个上游路由器用于转发该分组到丢弃该分组而使用的传输容量最终被浪费掉了

总结网络拥塞的代价

拥塞控制方法

端到端拥塞控制End-end congestion control
- no explicit feedback from network
- congestion inferred from observed loss, delay
- approach taken by TCP
网络辅助的拥塞控制Network-assisted congestion control
- routers provide direct feedback to sending/receiving hosts with flows passing through congested router
- 或者，路由器标记或更新从发送方流向接收方的分组中的某个字段来指示拥塞的产生，一旦收到一个标记的分组后，接收方会向发送方通知该网络拥塞指示（需要经过一个完整的往返时间）

3.7 TCP congestion control

TCP拥塞控制方法：AIMD（让每一个发送方根据所感知到的网络拥塞程度来限制其能向连接发送流量的速率）

AIMD具体细节

TCP发送方如何限制向其连接发送流量的
- 运行在发送方的TCP拥塞控制机制跟踪一个额外的变量，即拥塞窗口cwnd。在一个发送方中未被确认的数据量不会超过cwnd与rwnd中的最小值，不过有时候忽略接收窗口的限制，则发送方的发送速率≈cwnd/RTT 字节/秒
TCP拥塞控制算法：
- 慢启动
- 拥塞避免
- 快速恢复（非必需）

慢启动slow start

在慢启动状态，cwnd的值以1个MSS开始并且每当传输的报文段首次被确认就增加1个MSS（对每个报文段增加）。所以TCP发送速率起始慢，但在慢启动阶段以指数增长。

cwnd = initcwnd * 2^n

何时结束？
- 法一：若存在一个由超时指示的丢包事件（即拥塞），TCP发送方将cwnd设置为1并重新开始慢启动过程，还将第二个状态变量的值ssthresh(慢启动阈值)设置为cwnd/2（此过程用于记录下ssthresh的值，便于向下一过程转换）。当cwnd的值等于ssthresh时结束慢启动并且TCP转移到拥塞避免模式
- 法二：如果检测到3个冗余ACK，这时TCP执行一种快速重传并进入快速恢复状态

拥塞避免

一旦进入拥塞避免状态，cwnd的值大约是上次遇到拥塞时的值的一半（即拥塞并不遥远！）

此时每过一个RTT只将cwnd的值增加一个MSS，无论多少个报文段。即当cwnd<ssthresh时，拥塞窗口使用慢启动算法，按指数级增长。当cwnd>ssthresh时，拥塞窗口使用拥塞避免算法，按线性增长

何时结束？

若由超时引起的丢包：TCP的拥塞避免算法行为与慢启动的情况一样，cwnd的值被设置为1个MSS，ssthresh的值被更新为cwnd值的一半
若由收到三个冗余的ACK引起的丢包：TCP将cwnd的值减半，当收到3个冗余的ACK时，将ssthresh的值记录为cwnd的值的一半，接下来进入快速恢复状态

快速恢复

对于引起TCP进入快速恢复状态的缺失报文段，每当收到冗余的ACK，cwnd的值增加一个MSS。最终，当最后一个ACK到达时，TCP在降低cwnd后进入拥塞避免状态

如果出现超时事件，快速恢复在执行如同在慢启动和拥塞避免中相同的操作后，迁移到慢启动状态

当丢包事件出现时，cwnd的值被设置为1个MSS且ssthresh的值被设置为cwnd值的一半

上述三个过程总结

快速恢复不是必需的构件，三个状态没有先后顺序，可以相互转换

TCP拥塞控制：AIMD（加性增，乘性减）

即每个RTT内cwnd线性增加1MSS，然后出现3个冗余ACK事件时cwnd减半

TCP CUBIC

与TCP Reno有些许不同，仅当收到ACK时增加拥塞窗口，同时保持慢启动和快速恢复，仅改变拥塞避免阶段

W_max: sending rate at which congestion loss was detected

K: point in time when TCP window size will reach W_max

CUBIC以当前事件t和K之间距离的立方为函数来增加拥塞窗口，所以会更快地接近W_max，同时尽可能长时间地维持流仅低于拥塞门限

网络辅助明确拥塞通告和基于时延的拥塞控制

明确拥塞通告ECN
- two bits in IP header (ToS field) marked by network router to indicate congestion
- congestion indication carried to destination
- destination sets ECE bit on ACK segment to notify sender of congestion
- involves both IP (IP header ECN bit marking) and TCP (TCP header C,E bit marking)
基于时延的拥塞控制Delay-based TCP congestion control
- Keeping sender-to-receiver pipe “just full enough, but no fuller”: keep bottleneck link busy transmitting, but avoid high delays/buffering

TCP fairness公平性

TCP是公平的，在理想情况下：

Same RTT
fixed number of sessions only in congestion avoidance

3.8 Evolution of transport-layer functionality运输层功能的演化

主要介绍了QUIC（Quick UDP Internet Connections）：

4 The Network Layer: the Data Plane

4.1 Network layer: overview

网络层的作用概述：将分组从一台发送主机移动到另一台接收主机

转发forwarding：move packets from a router’s input link to appropriate router output link（在网络层的数据平面）。
- 在router内部，从router input port到router output port
路由选择routing：determine route taken by packets from source to destination（在网络层的控制平面）
- 在router之间，有两种方法：
  - 传统方法：运行在每台router中，每台router都包含转发和路由选择两种功能
  - SDN方法：物理上分离，远程控制器计算和分发转发表以供每台router使用。即路由选择设备仅执行转发，而远程控制器计算并分发转发表

网络服务模型Network Service Model

定义了分组在发送与接收主机之间的端到端传输特性

因特网尽力而为服务best-effort service：传送的分组既不能保证以它们发送的顺序接收，也不能保证它们最终交付，既不能保证端到端时延，也不能保证有最小的带宽

4.2 What’s inside a router

路由器结构

输入端口inpurt port
交换结构switching fabrics
输出端口output port
路由选择处理器routing processor

输入端口input port

最长前缀匹配规则longest prefix matching rule：在表中寻找最长的匹配项，并向最长前缀匹配相关联的链路接口转发分组

交换switching fabrics

transfer packet from input link to appropriate output link

三种交换方式：

经内存交换memory
- 在CPU（路由选择处理器）的直接控制下完成
- 分组先后被复制到路由选择处理器内存和输出端口的缓存中
- 不能同时转发两个分组，因为经过共享系统总线一次仅能执行一个内存读/写
经总线交换bus
- 输入端口经一根共享总线将分组直接传送到输出端口，不需要路由选择处理器的干预
- 该分组能被所有的输出端口收到，但只有与该标签匹配的端口才能保存该分组
- 一次只有一个分组能够跨越总线，故路由器的交换带宽受总线速率的限制
经互联网络交换interconnection network
- NxN
- 能并行转发多个分组，但是如果来自两个不同输入端口的两个分组目的地为同一输出端口时，一个分组必须在输入端等待

排队queuing

输入排队input port queuing
- Head-of-the-Line(HOL) blocking队列首部阻塞：在一个输入队列中排队的分组必须等待通过交换结构发送（即使输出端口是空闲的），因为它被位于队列首部的另一个分组所阻塞
输出排队output port queuing
- 当没有足够的内存来缓存一个入分组时，要么丢弃到达的分组（弃尾drop-tail），要么删除一个或多个已排队的分组为新来的分组腾出空间
- 在某些情况下，在缓存填满之前便丢弃一个分组/或在其首部加上标记，这可以向发送方提供一个拥塞信号。称为主动队列管理AQM算法
多少缓存才“够用”
- B = RTT * C / sqrt(N)，RTT为往返时延，C为链路容量，N为流的数量

分组调度packet scheduling：排队的分组如何经输出链路传输

先进先出FIFO/FCFS
- packets transmitted in order of arrival to output port
优先权排队priority queuing
- 到达输出链路的分组被分类放入输出队列中的优先权类（高优先权类和低优先权类）
循环排队round robin（RR）
- 分组被分类，但是类之间不存在严格的服务优先权。循环调度器在这些类之间轮流提供服务
加权公平排队weighted fair queuing, WFQ
- 与RR不同之处在于，每个类i被分配一个权w_i，类i将确保接收到的服务部分等于w_i/(sigma w_j)，这也是类i得到的最小带宽

4.3 IP: the Internet Protocol

IPv4数据报格式
IP地址

IP地址：4个字节（32比特），每个字节用它的十进制形式书写，各字节间以句点隔开（点分十进制记法）

每台主机和路由器接口都有自己的IP地址

子网subnets

IP地址为子网分配一个地址（子网掩码network mask）：223.1.1.0/24

一个子网的IP定义并不局限于连接多台主机到一个路由器接口的以太网段，如路由器与路由器通过点对点链路连接，这个链路也是一个子网

因特网的地址分配策略：无类别域间路由选择 CIDR：

当使用子网寻址时，32比特的IP地址被划分为两部分：a.b.c.d/x，x为地址第一部分subnet part的比特数
（网络）前缀：a.b.c.d/x地址的x最高比特
路由聚合：使用单个网络前缀通告多个网络

IP地址：如何获取一块地址

为了获取一块IP地址用于一个组织的子网内，网络管理员也许会与他的ISP联系，该ISP可能会从已分给它的更大地址块中提供一些地址。

获取主机host地址：动态主机配置协议DHCP（也叫即插即用协议plug-and-play）

某组织一旦获得了一块地址，它就可为本组织内的主机与路由器接口逐个分配IP地址。以前常手工配置，现在更多采取DHCP来完成。

给定主机每次与网络连接时能得到一个相同的IP地址或者被分配一个临时的IP地址
允许一台主机得知其他信息，如network mask、address of first-hop router for client、name and IP address of DNS sever

DHCP是一个client-server协议，客户通常是新到达的主机，需要获得包括自身使用的IP地址在内的网络配置信息

每个子网具有一台DHCP服务器或DHCP中继代理（通常是一台路由器）

网络地址转换 network address translation, NAT

用于在本地网络中使用私有地址，在连接互联网时转而使用全局IP地址的技术（改变了packet的source IP address和source port number）

为了解决IPv4地址短缺而开发的技术

IPv6

由于32比特的IPv4地址空间即将用尽

A. 数据报格式：

和IPv4相比：

no checksum (to speed processing at routers)
no fragmentation/reassembly
no options (available as upper-layer, next-header protocol at router)
扩大的地址容量，IPv6将IP地址长度从32比特增加到128比特
流标签。用于给特殊流的分组加上标签，这些特殊流是发送方要求进行特殊处理的流

B. 从IPv4到IPv6的迁移

建隧道tunneling

假定两个IPv6节点要使用IPv6数据报进行交互，这时将两台IPv6路由器之间的中间IPv4路由器的集合称为一个隧道。借助于隧道，可将IPv6数据报放到一个IPv4数据报的数据字段中

4.4Generalized Forwarding泛化转发, SDN

匹配加操作match plus action：查找目的IP地址，然后将分组发送到有特定输出端口的交换结构

匹配加操作转发表称为流表flow table，本质是个api：

Match plus action统一了不同的设备：

4.5 Middleboxes（防火墙

中间盒定义：在源主机和目标主机之间的数据路径上执行除IP路由器的正常标准功能之外的任何中间框

中间盒提供的三种服务：

NAT转换
安全服务
性能增强

NFV网络功能虚拟化

使用商用硬件（网络、计算和存储），并试图在通用软件堆栈之上构建专门的软件来实现这些服务

互联网架构原则

IP沙漏

端到端原则

5 The Network Layer: the Control Plane

5.1 introduction

转发表和流表是如何计算、维护和安装的

每路由器控制per-router control(traditional)：
- 每台路由器都运行一种路由选择算法
- 每台路由器中都包含转发和路由选择功能
- 每台路由器都有一个路由选择组件，用于与其他路由器中的路由选择组件通信
- Eg. OSPF, BGP协议
逻辑集中式控制logically centralized control(software defined networking)
- 逻辑集中式控制器计算并分发转发表以供每台路由器使用的情况
- 控制器经一种良好的协议与每台路由器中的一个控制代理CA进行交互，这些CA既不能直接相互交互，也不能主动参与计算转发表

5.2 routing protocols

路由选择算法目的：从发送方到接收方的过程中确定一条通过路由器网络的好的路径（等价于路由）

“good”: least “cost”, “fastest”, “least congested”

算法的分类：

Link state链路状态路由选择算法 LS

集中式路由选择，具有全局状态信息

即Dijkstra算法，计算从某节点（源节点，我们称之为u）到网络中所有其他节点的最低开销路径

当LS算法终止时，对于每个节点，我们都得到从源节点沿着它的最低开销路径的前一节点

复杂度分析：

算法复杂度O(n^2)或O(nlogn)
Message complexity：O(n^2)

振荡：when link costs depend on traffic volume, route oscillations possible

如何防止振荡：a. 强制链路开销不依赖于所承载的流量（不可接受）；b. 确保并非所有的路由器都同时运行LS算法

Distance vector距离向量路由选择算法 DV

分散式路由选择

是一种迭代的、异步的、自我终止的和分布式的算法

min_v是对于x的所有邻居v来说的，所以必须通过遍历邻居v开始

D_x(y)即遍历x的每个邻居，再加上邻居到y的距离向量，然后更新

直到无更新报文发送为止

Key idea：

from time-to-time, each node sends its own distance vector estimate to neighbors
when x receives new DV estimate from any neighbor, it updates its own DV using B-F equation:
under minor, natural conditions, the estimate D_x(y) converge to the actual least cost d_x(y)

DV算法：链路开销改变与链路故障

路由选择环路routing loop->无穷计数问题count-to-infinity

即good news travels fast while bad news travels slow

解决方法：毒性逆转poisoned reverse

如果z通过y路由选择到目的地x，则z将通告y，它（即z）到x的距离是无穷大。只要z经y路由选择到x，z就持续地向y讲述这个善意的小谎言

LS与DV路由选择算法的比较

robustness方面，由于一个LS节点仅计算字节的转发表，所以路由技术在某种程度上是分离的，提供了一定程度的健壮性

而DV算法中一个不正确的节点计算值会扩散到整个网络

5.3 intra-ISP routing: OSPF

AS：Autonomous System，自洽系统

每个AS由一组通常处在相同管理控制下的路由器组成，通常一个ISP中的路由器以及互联它们的链路构成一个AS

在相同AS中的路由器都运行相同的路由选择算法并且有彼此的信息，在不同AS中的路由器可以运行不同的域内路由协议

在一个自洽系统内运行的路由选择算法叫做自洽系统内部路由选择协议intra-autonomous system routing protocol

intra-AS: routing among routers within same AS (“network”)
inter-AS: routing among AS’es

Intra-AS routing: routing within an AS

RIP: Routing Information Protocol
- classic DV: DVs exchanged every 30 secs
- no longer widely used
EIGRP: Enhanced Interior Gateway Routing Protocol
- DV based
- formerly Cisco-proprietary for decades (became open in 2013 [RFC 7868])
OSPF: Open Shortest Path First
- link-state routing
- IS-IS protocol (ISO standard, not RFC standard) essentially same as OSPF

OSPF 开放最短路优先

Open: 公众可用的

OSPF是一种链路状态协议

each router floods OSPF link-state advertisements (directly over IP rather than using TCP/UDP) to all other routers in entire AS

OSPF的结构

5.4 routing among ISPs: BGP

Internet inter-AS routing: BGP（Border Gateway Protocol）

在因特网中，所有的AS运行相同的AS间路由选择协议，称为边界网关协议BGP

BGP为每个AS一种手段来完成下列的任务：

obtain destination network reachability info from neighboring ASes（eBGP）
determine routes to other networks based on reachability information and policy
propagate reachability information to all AS-internal routers (iBGP)
advertise (to neighboring networks) destination reachability info

eBGP, iBGP connections

对于每个AS，每台路由器要么是一台网关路由器gateway router，要么是一台内部路由器internal router。

BGP session: two BGP routers (“peers”) exchange BGP messages over semi-permanent TCP connection:
1. advertising paths to different destination network prefixes (BGP is a “path vector” protocol)
BGP advertised route: prefix + attributes
1. prefix: destination being advertised
2. two important attributes:
  - AS-PATH: list of ASes through which prefix advertisement has passed通告已经通过的AS的列表
  - NEXT-HOP: indicates specific internal-AS router to next-hop AS
BGP路由选择算法

热土豆路由选择hot potato routing
- 从所有可能的路由中选择的路由到开始该路由的NEXT-HOP路由器具有最小开销（选择具有最小最低开销的网关）
在实践中，BGP顺序地调用下列消除规则直到余下一条路由：
- local preference value attribute: policy decision
- shortest AS-PATH
- closest NEXT-HOP router: hot potato routing
- additional criteria

路由选择策略

ISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs

5.5 SDN control plane

SDN体系结构的四个关键特征

SDN体系结构组件

SDN控制的交换机 Data-plane switches
- protocol for communicating with controller (e.g., OpenFlow)
SDN控制器 SDN controller (network OS)
- maintain network state information
- 通过northbound api与网络控制应用程序交互，通过southbound api与交换机交互
- implemented as distributed system
网络控制应用程序 network-control apps

OpenFlow协议

operates between controller, switch
TCP used to exchange messages
Key controller-to-switch messages：
- features读状态: controller queries switch features, switch replies
- configure配置: controller queries/sets switch configuration parameters
- modify-state修改状态: add, delete, modify flow entries in the OpenFlow tables
- packet-out发送分组: controller can send this packet out of specific switch port
Communication between SDN controller and controlled switches
Key switch-to-controller messages：
- packet-in分组入: transfer packet (and its control) to controller. See packet-out message from controller
- flow-removed流删除: flow table entry deleted at switch
- port status端口状态: inform controller of a change on a port.

Control plane and data plane interaction
SDN控制器几个例子

A. ORION: Google’s SDN control plane (NSDI’21): control plane for Google’s datacenter (Jupiter) and wide area (B4) networks

B. OpenDaylight (ODL) controller：

SAL（Service Abstraction Layer，服务抽象层）

C. ONOS controller

独有特征：意图框架intent framework：允许应用程序请求高层服务，而不必知道该服务的执行细节

5.6 Internet Control Message Protocol

ICMP：因特网控制报文协议，被主机和路由器用来彼此沟通网络层的信息

典型用途：差错报告。例如，如果IP路由器不能找到一条通往HTTP请求中所指定的主机的路径，该路由器就会向你的主机生成并发出一个ICMP报文以指示该错误

error reporting: unreachable host, network, port, protocol
echo request/reply (used by ping)

network-layer “above” IP: ICMP messages carried in IP datagrams（ICMP通常被认为是IP的一部分，但是从体系结构上讲它位于IP之上）

ICMP message: type, code plus first 8 bytes of IP datagram causing error

Traceroute and ICMP

6 The Link Layer

6.1 introduction

专有名词

运行链路层协议的任何设备均称为节点，包括主机、路由器、交换机和WIFI接入点

沿着通信路径连接相邻节点的通信信道称为链路link

链路层提供的服务

Framing成帧，link access
reliable delivery between adjacent相邻的 nodes
flow control
error detection
error correction
half-duplex and full-duplex

链路层的实现与交互

大多数情况下，链路层是在称为网络适配器的芯片上实现的，有时也称为网络接口控制器（NIC）

attaches into host’s system buses

链路层控制器的大部分功能是在硬件中实现的

6.2 error detection, correction

EDC: error detection and correction bits

差错检测不是100%有效

larger EDC field yields better detection and correction

三种方法：

奇偶校验 parity checking

A. 单比特奇偶校验single bit parity

要发送的信息D有d比特，在偶校验方案中，发送方只需要包含一个附加的比特，选择它的值，使得这d+1比特中1的总数是偶数（奇校验同理）

接收方只需数一数接收的d+1比特中1的数量即可

单比特奇偶校验若检测到error，则一定有error；若没有检测到error，则不一定没有error

B. 二维奇偶校验two-dimensional parity

包含行和列

可以通过行和列的索引来识别并纠正发送差错的比特

能检测但不能纠正一个分组中两个比特差错的任何组合

避免了重传——>前向纠错FEC：接收方检测和纠正差错的能力，可以减少所需的发送方重发的次数，允许在接收方立即纠正差错，而不是让发送方重传一份正确的。从而避免了不得不等待的往返时延

因特网检验和 Internet checksum

见3.3节

循环冗余检测 CRC

D：被发送的数据比特，d比特
R：附加比特，默认为0，r比特
G：生成多项式，r+1比特

用G去除接收到的d+r比特，如果余数为非零，则接收方知道出现了差错，否则认为数据正确而被接收

这里的“除”是取异或的意思

R = remainder(D*2^r/G)

6.3 multiple access protocols多路访问链路和协议

两种网络链路：

点对点链路point-to-point link
- 由链路一端的单个发送方和链路另一端的单个接收方组成
- point-to-point link between Ethernet switch, host
- PPP for dial-up access
广播链路broadcast link（shared wire or medium）
- 能让多个发送和接收节点都连接到相同的、单一的、共享的广播信道上
- old-school Ethernet
- upstream HFC in cable-based access network
- 802.11 wireless LAN, 4G/4G. satellite

多路访问协议multiple access protocol

一个理想的多路访问协议：

多路访问协议的三种类型：

信道划分协议channel partition protocol
- 将channel分成小的部分，如time slots, frequency, code
- 将片段划分给节点，以供独家使用
- 4G, 5G
随机接入协议random access protocol
- channel not divided, allow collisions
- “recover” from collisions
- Erthernet, WiFi
轮流协议taking-turns protocol
- nodes take turns, but nodes with more to send can take longer turns

信道划分协议

时分多路复用TDMA
- 将时间划分为时间帧time frame，并进一步划分每个时间帧为N个时隙slot，然后把每个时隙分配给N个节点中的一个
- 选择的时隙长度应使一个时隙内能够传输单个分组
- 没有被使用的时隙处于空闲状态idle
- 优缺点：
  - 优点：避免了碰撞，十分公平，每个节点在每个帧时间内得到了专用的传输速率R/N bps
  - 缺点：节点被限制于R/N bps的平均速率，哪怕它是唯一有分组要发送的节点
频分多路复用FDMA
- 将R bps信道划分为不同的频段，每个频道都有R/N带宽，并把每个频率分配给N个节点中的一个
- 优缺点与TDMA类似
码分多址CDMA
- TDMA和FDMA分别为节点分配时隙和频率，CDMA为每个节点分配一种不同的编码，然后节点用它唯一的编码对它发送的数据进行编码
- 不同的节点可以同时传输（利用编码），不会互相干扰

随机接入协议

A. 概念

一个传输节点总是以信道的全部速率（即R bps）进行发送，当有碰撞时，涉及碰撞的每个节点反复地重发它们的分组，到该分组无碰撞地通过为止
遇到碰撞后独立地选择随机时延，重发分组

B. 随机接入协议的例子：

ALOHA, slotted ALOHA
CSMA, CSMA/CD, CSMA/CA

C. Slotted ALOHA:

时间被划分成长度为L/R秒的时隙（即传输一帧的时间）
节点只在时隙开始的时候传输帧，以全速R传输
如果大于等于2个节点在同一个时隙里传帧，则发生碰撞
发生碰撞后节点会以概率p在后续的每个时隙中重传它的帧，直到传出去为止

时隙多路访问协议的效率efficiency：当有大量的活跃节点且每个节点总有大量的帧要发送时，长期运行中成功时隙的份额
- Max efficiency: 1/e ≈ 37%（相似的分析，37%时隙是空闲的，26%时隙有碰撞）

D. Pure ALOHA

与时隙ALOHA相比，纯ALOHA每个节点的运输不是同步的，这带来了更大可能性的碰撞
Max efficiency: 1/2e ≈ 18%

E. 载波侦听多路访问CSMA

载波侦听carrier sensing：easy in wire, hard in wireless

CSMA：listen before transmit
- 由于有端到端信道传播时延(channel propagation delay)，所以尽管所有的节点都在进行载波侦听，也会有碰撞。且传播时延越长，载波侦听节点不能侦听到网络中另一个节点已经开始传输的机会越大
CSMA/CD：CSMA with collision detection
- 减少了在碰撞上浪费的时间
- transmission aborted on collision detection（只能检测碰撞冲突，无法避免；CSMA/CA不能检测冲突，只能尽量避免）

Erthernet CSMA/CD algorithm：

CSMA/CD efficiency：

轮流协议

channel partitioning MAC protocols在high load下高效，random access MAC protocols在low load下高效，而take turns尝试拥有both

轮询协议polling
- 要求节点之一被指定为主节点，主节点以循环的方式轮询每个节点。即主节点首先向节点1发送一个报文，告诉节点1能够传输帧的最多数量，在节点1传输了某些帧后，主节点再转向节点2……
- 蓝牙Bluetooth使用的就是轮询协议
- 优点：避免了碰撞和空时隙
- 缺点：
  - 引入了轮询延迟
  - 主节点可能出现故障
令牌传递协议token passing
- 没有主节点，一个被称为令牌的小的特殊帧在节点之间以某种固定的次序进行交换
- transmit while holding token
- 优点：令牌是分散的，效率高
- 缺点：一个节点的故障可能导致整个信道崩溃

Cable access network有线接入网: FDM, TDM and random access

6.4 LANs

6.4.1 addressing, ARP

主机和路由器（的适配器/网络接口）都有链路层地址，而ARP（地址解析协议）就是提供了将IP地址转换为链路层地址的机制

MAC地址

具有多个网络接口的主机将具有与之相关联的多个链路层地址

MAC地址长度为6字节，通常用十六进制表示法

没有两块适配器具有相同的地址

MAC地址具有扁平结构（区别于IP地址分为网络部分和主机部分），can move interface from one LAN to another

地址解析协议ARP

ARP将一个IP地址映射为一个MAC地址，且只为同一个子网上的主机和路由器接口解析IP地址

每台主机或路由器在其内存中具有一个ARP table，格式<IP address, MACaddress, TTL>,TTL（Time to Live）为从表中删除这个映射的时间

ARP协议具体做法：

如果发送方的ARP表具有该目的节点的表项，则done
如果没有，则需要构造ARP packet（包含IP src, IP dst, MAC src, MAC dst），使用MAC广播地址来发送这个分组

发送数据报到子网外

MAC的src和dest是根据当前的发送方和接收方决定的，在传递过程中会被更改。而IP的src和dest是根据整体的源和目的地决定的，在传递过程保持不变

6.4.2 Erthernet

first widely used LAN technology

从bus改为switched：

帧结构frame structure

Ethernet: unreliable, connectionless

Unreliable：receiving NIC doesn’t send ACKs or NAKs to sending NIC
Connectionless：no handshaking between sending and receiving NICs
Ethernet’s MAC protocol: unslotted CSMA/CD with binary backoff

6.4.3 switches

transparent: hosts unaware of presence of switches

plug-and-play, self-learning：switches do not need to be configured

switch可以同时进行多个传输，由于Ethernet protocol used on each incoming link，所以有着不同目的地的传输是无碰撞且为双全工（full-duplex）

有着相同目的地的传输会发生碰撞！

Switch forwarding table

Filtering and forwarding is completed by switch table

each switch has a switch table, each entry:

(MAC address of host, interface to reach host, time stamp)
looks like a routing table!

假设目的地址为DD-DD-DD-DD-DD-DD的帧从交换机接口x到达，交换机用MAC地址索引它的表，可能有3种可能的情况：

表中没有对应MAC地址的表项：交换机广播该帧
表中有MAC地址与接口x关联的表项：丢弃该帧执行过滤功能
表中有MAC地址与接口y≠x关联的表项：通过将该帧放到接口y前面的输出缓存完成转发功能

Self-learning

switch learns which hosts can be reached through which interfaces

交换机存储在每个接口接收到的入帧的信息，且在一段时间（老化期aging time）后，如果交换机没有接收到以该地址作为源地址的帧，就在表中删除这个地址

6.4.4 VLANs

虚拟局域网virtual LANs：VLANs

为了解决被配置为等级结构的局域网的一些问题，如隐私、效率等

port-based VLAN: switch ports grouped (by switch management software) so that single physical switch operates as multiple virtual switches）

跨多个switches的VLANs

VLAN干线连接VLAN trunking：每台交换机上的一个特殊端口被配置为干线端口，发送到任何VLAN的帧经过干线链路转发到其他交换机

802.1Q：一种扩展的以太网帧格式，用于解决到达干线端口的帧属于哪个特定的VLAN问题

6.5 link virtualization: MPLS

多协议标签交换Multiprotocol Label Switching, MPLS

goal：改善IP路由器的转发速度

faster lookup using fixed length identifier

MPLS capable routers，被称为label-switched router

forward packets to outgoing interface based only on label value (don’t inspect IP address)

MPLS forwarding table distinct from IP forwarding tables

flexibility: MPLS forwarding decisions can differ from those of IP：
- use destination and source addresses to route flows to same destination differently (IP routing: path to destination determined by destination address alone)
- re-route flows quickly if link fails: pre-computed backup paths

6.6 data center networking

7 Wireless and Networks

7.1 introduction

无线网络中的要素

Wireless hosts
- 主机本身可能可以移动，也可能不移动（wireless does not always mean mobility!）
Base station基站
- typically connected to wired network
- relay中继 - responsible for sending packets between wired network and wireless host(s) in its “area”
- e.g., cell towers, 802.11 access points
wireless link
- 两种主要特性：链路速率和覆盖区域
infrastructure mode基础设施模式
- 与基站关联的主机通常被称为以基础设施模式运行，因为所有传统的网络服务都由网络向通过基站相连的主机提供
ad hoc mode自组织
- no base stations
- nodes can only transmit to other nodes within link coverage
- nodes organize themselves into a network: route among themselves

无线网络的分类

7.2 Wireless links and network characteristics

无线链路的特点：

fading (attenuation)递减的信号强度
- Wireless radio signal attenuates (loses power) as it propagates (free space “path loss”)
- Free space path loss ~ (fd)^2
multipath多路径传播
- multipath propagation多径传播: radio signal reflects off objects ground, built environment, arriving at destination at slightly different times
noise来自其他源的干扰
- 在同一个频段发送信号的电波源将互相干扰
- SNR: signal-to-noise ratio 信噪比，单位是dB
  - 较大的SNR使接收方更容易从背景噪声中提取传输的信号
  - BER：比特差错率，是在接收方收到的有错传输比特的概率
  - given physical layer: increase power -> increase SNR->decrease BER
  - SNR may change with mobility: dynamically adapt physical layer (modulation technique, rate)
hidden terminals隐藏终端问题

CDMA 码分多址

encoding: inner product: (original data) X (chipping sequence)

decoding: summed inner-product: (encoded data) X (chipping sequence)

7.3 WiFi: 802.11 wireless LANs

7.3.1 802.11无线局域网体系结构

IEEE 802.11 Wireless LAN

all use CSMA/CA for multiple access, and have base-station and ad-hoc network versions

802.11 LAN architecture：

802.11体系结构的基本构件模块是基本服务集BSS（Basic Service Set），BSS包含一个或多个无线站点以及一个被称为接入点AP的中央基站

802.11: Channels

spectrum divided into channels at different frequencies

AP admin chooses frequency for AP

可能有干扰

802.11: Association

arriving host: must associate with an AP

scans channels, listening for beacon frames containing AP’s name (SSID) and MAC address
selects AP to associate with
then may perform authentication [Chapter 8]
then typically run DHCP to get IP address in AP’s subnet

802.11: passive/active scanning

选择AP的方式，一个是接收AP的信标帧，一个是向所有的AP广播探测帧

7.3.2 802.11MAC协议

IEEE 802.11 MAC Protocol: CSMA/CA

802.11使用碰撞避免技术而非碰撞检测；使用链路层确认/重传（ARQ）方案

处理隐藏终端：RTS和CTS

RTS：Request to Send，短请求发送
CTS：Clear to Send，允许发送

过程：

sender first transmits small RTS packet to BS using CSMA
- RTSs may still collide with each other (but they’re short)
BS broadcasts CTS in response to RTS
CTS heard by all nodes
- sender transmits data frame
- other stations defer transmissions

7.3.3 802.11 frame: addressing

802.11 WiFi frame:

address1: AP, address2: H1, address3: R1(router)

802.3 Ethernet frame:

dest, src

7.3.4 802.11: mobility within same subnet

7.3.5 802.11: advanced capabilities

速率适应Rate adaptation

SNR decreases, BER increase as node moves away from base station

When BER becomes too high, switch to lower transmission rate but with lower BER

功率管理power management

node-to-AP: “I am going to sleep until next beacon frame”
- AP knows not to transmit frames to this node
- node wakes up before next beacon frame
beacon frame: contains list of mobiles with AP-to-mobile frames waiting to be sent
- node will stay awake if AP-to-mobile frames to be sent; otherwise sleep again until next beacon frame

7.3.6 Bluetooth

Personal area networks: Bluetooth

7.4 Cellular networks: 4G and 5G

7.4.1 Elements of 4G LTE architecture

移动设备Mobile device
基站Base station
归属用户服务器Home Subscriber Service（HSS）
- 控制平面部件，是一个数据库，储存关于移动设备的信息
- works with MME in device authentication
服务网关S-GW（Serving Gateway）、PDN网关P-GW（PDN Gateway）等其他网络路由器
- 是位于移动设备与因特网之间的数据路径上的两台路由器
- P-GW provides NAT services
移动性管理实体MME（Mobility Management Entity）
- MME也是一个控制平面组件
- device authentication (device-to-network, network- to-device) coordinated with mobile home network HSS
- path (tunneling) setup from mobile device to P-GW
- device handover between cells
- tracking/paging device location

7.4.2 LTE: data plane control plane separation

LTE data plane protocol stack

LTE将移动设备的链路层分为三个子层，从IP向下：

分组数据汇聚Packet Data Convergence: header compression, encryption
无线链路控制Radio Link Control (RLC) Protocol: fragmentation/reassembly, reliable data transfer
介质访问控制（MAC）Medium Access:requesting, use of radio transmission slots (OFDM)

7.4.3 Radio Access Network: 4G radio无线电接入网

LTE在下行信道上使用频分复用和时分复用的组合，称为正交频分复用OFDM（Orthogonal Frequency Division Multiplexing）

7.4.4 LTE附加功能：网络连接和功率管理

网络连接

见p377

功率管理

as in WiFi, Bluetooth: LTE mobile may put radio to “sleep” to conserve battery:

light sleep: after 100’s msec of inactivity
- wake up periodically (100’s msec) to check for downstream transmissions
deep sleep: after 5-10 secs of inactivity
- mobile may change cells while deep sleeping – need to re-establish association