计算机网络

主机/端系统

几十亿台连接因特网的设备

通信链路(links)

包括fiber, copper(铜线), radio, satellite等,其传播速度即为带宽(bandwidth),单位为bit/s或bps

分组(packet)

端系统间发送数据,发送端把数据分段加上首部字节,由此形成的信息包为packet

路由器(routers)

在不同端系统之间转发分组(forward packets)

因特网服务提供商(ISP)

自身即为多台分组交换机和多段通信链路组成的网络,ISP端系统提供不同类型的网络接入

协议(protocol)

定义了两个或多个通信实体之间交换报文(message)的格式和顺序,以及报文传输和其他事件所采取的动作

• 协议的作用:定义格式,定义顺序,定义行为

构成

端系统和应用程序

模式

CS, P2P

形式

描述

Dial-up Modem

拨号调制解调器

使用电话线,Modem把数字数据转换为高频音,通过电话线给中心局;模拟信号再通过Modem转回数字数据,问题在于不能"always on",通话时就无法上网

信号转换: digital  <-> analogue signal

速度: 最高56Kbps

线路: dedicated(家庭直接由电话线连接CO)

Digital Subscriber Line
数字用户线

原理同上,但对不同信号(高速下行/中速上行/双向通话)使用不同频率编码,在接入时使用分配器过滤不同频率的信号,实现always on

信号转换: digital  <-> analogue signal

速度: 上行: 1Mbps 下行: 8Mbps

线路: dedicated

cable 电缆接入

一种住宅接入(residental access)方式,使用有线电视线缆,系统中:
光缆连接电缆头端->地区枢纽->同轴电缆连接到各家,因此称为混合光纤同轴系统(hybrid fiber coax, HFC),是不对等网络(asymmetric)

信号转换: digital  <-> analogue signal

速度: 上行: 2Mbps 下行: 30Mbps

线路: shared(无论光缆和电缆)

光纤到户

使用光纤连接中心局和家庭,速度快,同时可携带电话,电视信号,分为主/被动两类

• 典型的PON👇

信号转换: light <-> electrical

速度: 有KMbps的潜力

线路: shared

ethernet 以太网

通常在企业,大学中使用,端系统用双绞铜线连接以太网交换机,再连接更大的因特网

速度: 10Mbps,100Mbps,1Gbps,10Gbps...

wireless access

无线接入

无线用户从/到一个access point发送/接收packet,接入点即基站,其与企业网相连,再与更大因特网连接

bit

在传送者/接收者间传播

bit rate

比特速率,每秒传输的bit数,单位bps

physical link

连接传送者/接收者

guided media

在固体媒介中传播(铜缆,光纤)

unguided media

自由传播(广播)

Coaxial cable 同轴电缆

• 同心铜导体
• 常用于有线电视电缆接入

Optical fiber 光纤

• 可引导光脉冲,一个脉冲为1bit
• 支持比特速率极高,不受电磁干扰,100Km的衰减也很小

radio 广播

常见类型

• terrestrial microwave 地表微波
• LAN (wifi)
• wide-area (cellular)
• satelite

twisted pair 双绞线

• 普遍使用于局域网
• 绞合减少了临近双绞线的电器干扰
• 现代双绞线可达到10Gbps的速率和100m长,是高速LAN的主要解决

构成

大量连接的路由器

数据传播方式

• 分组交换
• 电路交换

参考链接:

Difference between Circuit Switching and Packet Switching

网络在host间创建专用的端到端连接(e2e),路径中的routers都为连接维持状态,连接期间也预留了恒定的传输速率(带宽,bandwidth),如传统电话网络

特点总结: 

• 建立并维持实际连接
• 连接专用(dedicated)
• 预留固定带宽
• 速率恒定

频分复用
(Frequency-Division Multiplexing, FDM)

时分复用
(Time-Division Division Multiplexing, TDM)

链路为不同连接分配特定频段,该频段的宽度即为带宽

时间划分为固定间隔的帧,帧又分为固定数量的时隙(slot),不同时隙对应不同连接专用

右图每一帧左旋90度,即为左图,本质TDM也是使用了1/4的带宽

❓例题: 传输一个64000bits的文件,假设使用24slots的TDM电路交换,(带宽)比特速率1.536Mbps,且需500ms创建端到端电路,则发送文件的时间为?

解: 1.536Mbps/24 = 64Kbps (不理解就看FDM与TDM图,实际等效)

 64000bits/64Kbps = 10s

10 + 0.5 = 10.5 s

每个端对端数据流被分为组(packet),不同用户的组共享网络资源,每个组可占有全部带宽;总资源需求可以超过可用量,但在分组队列中会发生阻塞,分组每次只能移动一跳(hop)

特点总结: 

• 不同端连接的分组共享链路
• 分组可占有最大带宽

如图链路,源发送一个大小L的packet,链路传输速率Rbps,则传输到目的地的时延为多少?

解:由于S&F机制,开始源需要L/R才能将packet完整传输到router,此时router才能开始forward此packet,又需要L/R才能完整到达目的地,共需2L/R的时间

结论:对于N条速率R的链路组成的路径(N-1个router),源发送一个packet抵达目的地的e2e时延为:

如图,35个用户共享链路进行分组交换,带宽1Mbps,每个用户活跃时只能使用100kbps带宽,且活跃时间占其传输时间的1/10,求分组交换,电路交换下最多用户数?

• 电路交换: 最多支持1Mbps/100kbps=10个用户
• 分组交换: 

在给定区域,有一个较大的ISP(第一层ISP),为小规模ISP或区域ISP提供网络接入,下级ISP类似;当两个ISP对等(peer)时,互相之间不结算(收费);且任何非第一层ISP都可以多宿

• 多宿(multi-home): 选择多个ISP连接
• IXP:Internet Exchange Point: 第三方创建的多个对等ISP的汇合点

处理

pkt从到达节点到进入输出队列的间隔,包括检查packet首部决定去向,检查bit级别错误

排队

当link在传输别的packet,则当前packet等待

传输(transmission)

即L/R,将完整packet传输(推出)的时间

传播(propagation)

受限于Link的物理媒介传播速度,d为router间距,s为物理速率,则时延为d/s

区别传输&传播时延

• 传输时延:router推出完整packet的时间,与距离无关
• 传播时延:packet在link上传输的时间,与距离有关

运算

解释

常用单位

a

packet达到队列的平均速率

pkt/s

R

link的推出bit的速率

bps

L

视所有packet大小都是L比特

b

La

每秒到达Link的比特数

bps

La/R

流量强度,link的压力

因

特

网

协

议

栈

应用层

支持网络程序,是网络程序及其应用层协议存留处

• PDU: message
• FTP, SMTP, HTTP

运输层

在程序端点间传输应用层message

• PDU:  segment
• TCP, UDP

网络层

将称为数据报(datagram)的网络层分组从一台主机移动到另一台

• PDU: datagram
• IP

链路层

在相邻网络节点间转递数据,其上的分组为帧(frame)

• PDU: frame
• Ethernet, 802.111, PPP

物理层

负责将frame中的bit运输到相邻网络元素

• PDU: bits

I
S

O

表示层

使通信的app可解释交换数据的含义

会话层

提供数据交换和定界与同步功能,包括建立check point和恢复

server

• 主机持续在线
• 永久IP
• 用于拓展(scale)的服务器场(server farms)

clients

• 间歇连接
• 可变IP
• Client之间不会直接交流

pure p2p

• 服务器非持续在线
• 任意(arbitrary)端系统直接通信
• 节点间歇连接,IP可变

特点

• 高可扩展(highly scalable),难以管理
• 对等方IP动态化,如何发现

• PID特定于系统,当host系统不一,PID对应进程也不同,无法统一
• 一个进程可建立多个连接,此时一个PID不足以区分多个连接

关于port

port分为三类

• 0-1023: well-known ports/system ports,其中很多端口固定分配给系统某种服务使用
• 1024-49151: registered ports,分配给用户或应用程序进程
• 49152-65535:dynamic ports,一般不固定分配某种服务

TCP 服务

UDP 服务

意义

由于分组交换中没有建立连接,packet传到哪里完全由网络核心的routers们决定,可能出现问题:
1. packet走不同的link到达
2. 由于link不同,packet可能乱序或丢包 因此,端系统上的传输层必须进行控制=>TCP传输控制协议

用户数据报协议,实现简单,发送速度快

支持

• connection-oriented:面向连接
• reliable transport:可靠传输
• flow control: 流控,为了避免receiver的buffer满导致丢包,需要进行流控
• congestion control:拥塞控制

• unreliable transport

不支持

• timing
• minimum throughtput guarantee
• security

• connection setup
• reliability
• flow control
• congestion control
• timing
• minimum throughtput guarantee
• security

应用

邮件,远程连接,web

流媒体,DNS,网管协议

对比

UDP实现简单速度快;TCP为了可靠性需要大量约束
企业为了并取优点,大都自己设计应用层协议实现原有传输层TCP中的可靠性保证,在传输层采用UDP协议,这样又能保证速度

名称

超文本传输协议 hypertext transfer protocol

位置

应用层

架构

CS

特点

• 基于TCP协议,需建立TCP连接再传递HTTP request/response(三次握手),传输结束需要关闭TCP连接(四次挥手)
• 无状态, stateless:S无法保存过往的C任何requests

典型的HTTP传输场景

关于RTT(round-trip time, 往返时间)

建立TCP连接 ->传递HTTP请求/响应 ->TCP连接关闭

RTT是一个packet在CS之间往返的时间

三次握手+HTTP RR传输=2RTT

**问:一个TCP可以携带几个不同的HTTP请求:

通过三次握手说明,只有持久连接时才能携带一个以上的不同HTTP请求

nonpersistent

每个R/R对经过一个单独的TCP连接发送

np + cocurrent TCP

虽然每个R/R使用单独TCP,但TCP可同时创建

persistent

所有的R/R对可通过一个TCP连接发送,由此可知,只有在persistent连接中,一个TCP才能携带多个HTTP请求,依次处理

(默认)p + pipeline

(无等待HTTP)

无需等待之前的response返回,可一次性发出所有request,近似为同一时间全部发出(pipeline看似想同时处理HTTP请求,但实践困难,虽然服务器端默认开启,但现代浏览器默认关闭)

1. 用户请求一个web页面,它由一些文本和3幅图像构成,忽略transmit时间,求分别采用上述四种传输方式后的response time

• np:2RTT+3*2RTT=6RTT
• np+cTCP:2RTT+2RTT=4RTT
• p: 2RTT+3*RTT=5RTT
• p+p: 2RTT + RTT=3RTT

清楚流程:
1. 先请求页面=>2RTT(3次握手+HTTP RR)

2. 对html中的三幅图片:

当为np时,每个图片也需要2RTT=>3*2RTT;

当为cTCP时,相当于只有一幅图片=>2RTT;

当为p时,无需重建TCP,每个图片需要RTT=>3*RTT

当为PP时,相当于一幅图片且无需重建TCP=>RTT

(设传播时延为ds)

1. 非持续并行

深入分析以上非持续并行的2RTT构成

2. 持续非流水线

深入分析以上非持续非流水线的2RTT+10RTT'构成

3. 扩展:当是持续且带流水线

2RTT+RTT'+9*100k/R

• 流水线可以认为host只有一个RTT',但无法忽略server发送时的queuing delay

request

response

GET/POST/HEAD区别

• GET在page传参数是将参数直接放在地址最后
• POST将参数放在request body,不明文表示
• HEAD类似GET但常用于开发测试,不返回请求对象

Connection控制是否为持久连接

构成

流程

构成

web cache既是client也是server:在本地存储副本传输给客户;又向原始server发出request

作用

• web cache大大减少client的response time,尤其是当客户和原始server间有bottleneck link时
• web cache可以减少机构的接入链路到internet的通信量

• FTP协议是一种不安全的文件传输协议,明文保存数据
• FTP使用一种"(控制信息)带外传输"技术(out of band):使用双TCP连接,control con建立在21端口用于控制连接,浏览目录等;当需要传递数据,在20端口建立data con

HTTP

FTP

面向对象

超文本传输,面向网页

文件传输协议,面向文件

端口

默认80

默认20,21

传输

单TCP连接,控制信息带内传输

双TCP连接,控制信息带外传输

状态

无状态

会话期间保留用户state

持久性

默认持久且带流水线,可转换

控制连接persistent,数据non-persistent

一个典型的电子邮件系统如右图,主要由三部分构成:

• user agents:用户代理,负责向服务器中上传/收取信息,负责编辑阅读消息,比如outlook,iPhone mail
• mail servers:存放用户接收到的消息
• SMTP:在mail servers之间发送/接收邮件信息的协议(接收不包括user agent从server中接收信息,这一过程由别的协议负责)

构成

使用TCP进行可靠传输,占用端口25,有状态

过程

• direct transfer:

• 从sending server -> receiving server

• 三个阶段(类比HTTP传输)

• handshaking
• transfer of messages
• close

举例

①②③A打开Outlook写信->Outlook发送给A.server (SMTP)

④---->A.server和B.server建立TCP连接----> (SMTP)

⑤⑥B.server中信息被Gmail读取->B在Gmail上查看邮件 (POP3/IMAP...)

SMTP

HTTP

共同点

• SMTP是一个push(推)的协
• SMTP使用persistent连接
• 每个对象被封转在自己的response msg中

• HTTP是一个pull(拉)的协
• HTTP的连接方式分p/nonp
• 大量的对象被封装在一个multipart msg中

都有基于ASCII的command/response交互,状态码

定义

①一个由分层(hierarchy)的DNS服务器实现的分布式数据库

②使得host能够查询分布式数据库的应用层协议.

位置

DNS服务器:通常是运行Berkeley Internet Name Domain软件的UNIX机器.

DNS协议:运行在运输层的UDP之上,使用53端口

功能

• 进行host name到IP的转换

用户host上的浏览器/邮件阅读器需要把host name转换为IP地址时:

1. 首先调用DNS客户端,指明被转换的主机名;
2. DNS收到主机名,向网络发送msg

(所有请求和回答msgs都使用传输层UDP数据报通过53端口发送);

1. 经过时延后,host上的DNS接收到回答msg,再传递给调用的应用程序.

• 主机别名 host aliasing: 比如baidu.com实际上为一个别名
• 邮件服务器别名
• 负载均衡 load distribution

热门站点的Web服务器被冗余的分布在多台服务器,每台服务器所在端系统有不同IP,但所有IP的集合对应着一个规范host name,为了防止客户只对排在最前面的IP访问导致服务器负载不均,DNS会循环地址的次序,分配负载

• single point of failure:单个DNS server崩溃internet瘫痪
• traffic volume:通信容量,单个server会处理所有查询
• distant centralized database:单个server无法邻近查询所有客户
• maintenance:单个server为所有host维护记录不切实际,数据库庞大且会频繁更新

Root name servers

世界上400多个根域名服务器遍布世界,由13个组织管理.根域名服务器提供TLD服务器的IP地址

TLD, Top-level domain servers

顶级域名服务器.对于如com,org,net,edu,gov等顶级域和国家域都有TLD服务器,提供authoritative servers的IP地址

Authoritative DNS servers

权威DNS服务器,在Internet上有公共可访问主机的组织机构需提供公众可访问的DNS记录,用以映射IP地址.组织机构需实现自己的权威DNS服务器来实现保存记录

local DNS serves

本地DNS服务器.并不严格属于分层结构.每个ISP有一台local server,当用户host发出DNS query时,query被发送到本地server(更像是代理,实现请求的转发)

前提:纽约大学计算机系主机cis.poly.edu想知道主机gaia.cs.umass.edu的IP地址,且已知NYU计算机系的本地DNS服务器dns.poly.edu

过程

①cis.poly.edu首先向本地dns.poly.edu发送一个查询msg,其中包含被转换的主机名gaia.cs.umass.edu

②本地DNS服务器发送至root server

③root server发现edu前缀并把负责edu的TLD的IP地址列表返回给本地server

④本地server再次向TLD发送msg

⑤TLD注意到umass.edu前缀,返回负责的权威server IP地址给本地

⑥本地server直接向dns.cs.umass.edu发送msg

⑦对应server用gaia.cs.umass.edu对应的IP地址响应

⑧本地server返回IP地址给host

全程发送了4次msg,接收4次msg

对比:现在普遍采用迭代查询,因为DNS缓存技术的存在,更节约资源

过程

①用户host向本地server发送查询msg,其中包含要转换的主机名

②本地server向root server发送msg

③root server根据edu前缀发送至负责edu的TLD

④TLD根据umass.edu前缀发送msg至负责的权威server

⑤权威server将msg中主机名对应的IP地址发送回TLD

⑥TLD返沪给root

⑦root返回给本地server

⑧本地server返回转换结果给host

定义

caching技术能把任何映射缓存在本地

比如dns.poly.edu从root/TLD/authoritative得到的映射结果都会被保存

应用

• 一台host查询不同dns:采用iterated query,第一次要转换a.edu完成后;第二次查询b.edu的IP地址,负责edu的TLD IP地址结果已经在本地,可直接从中查询下级权威server IP
• 两台host查询相同dns:内网第一台host查询a.edu后本地server缓存其IP,第二台host查询a.edu,可直接返回结果

资源记录

resource record:实现分布式DB的所有DNSserver存储的即为rr,提供了主机名到IP地址的映射,其中ttl为记录生存时间

Type--A

• name:主机名;
• value:IP地址
• 类型为A的RR提供了标准主机名到IP地址的映射: 如(relay1.bar.foo.com,145.37.93.126,A)

Type--NS

• name:个域(xxx.com);
• value:可解析域名IP的权威server主机名
• 该RR用于沿着查询链路由DNS查询

如(foo.com, dns.foo.com, NS)

Type--CNAME

• name:规范名(canonical name)对应的别名(alias name);
• value:规范名
• 该记录可向查询的host提供一个主机名对应的规范名

比如www.ibm.com是servereast.backup2.ibm.com的别名

Type--MX

• name:个别名(邮箱后缀)
• value:个别名为name的mailserver的规范名
• MX记录允许邮件服务器主机名有简单别名

• 例题:域名注册

1. 一个NS记录,一个A记录

{www.startwar.com.cn, dns1.startwar.com.cn, NS}

{dns1.starwar.com.cn, 128.119.12.40, A}}

2. 两个web server的A记录,一个mailserver的A记录,一个邮件地址的MX记录

{www.starwar.com.cn, 128.119.12.55, A}

{www.starwar.com.cn, 128.119.12.56, A}

{starwar.com.cn, galaxy.starwar.com.cn, MX}

{galaxy.starwar.com.cn, 128.119.12.60, A}

3. (com,cn都属于TLD域名)

特点

• 非always-on服务器
• 任意端系统直接通信
• 节点间歇连接且IP可更改

对比CS--1台服务器分发文件到N台客户机场景:已知文件大小F,上传速度u,下载速度d

C/S

• 服务器需要上传N份拷贝,耗
• 客户机i下载耗时
• 则文件分发总耗时
• 结论:CS架构下,文件分发耗时和N成线性关系(假设下载速度稳定)

P2P

P2P具有特点:当一个peer接收到文件数据,可以使用上传能力重新把数据发给对等方,因此服务器只需上传一份文件,即可分发给所有设备

• 服务器上载耗时:
• 客户机i下载耗时
• 总共有NFbits必须被下载,而系统整体总上载能力等于服务器加上每个peer的上载速率,不可能超过
• 则分发文件总耗时最小为

名词

• torrent: 洪流,参与文件分发的所有peers
• tacker: 追踪器,每个torrent对应的一台server,当一个peer加入torrent,会向tacker注册,告知自己的地址,资源等
• chunk: 块,torrent中peers彼此下载等长的文件块

定义

一个peer加入torrent,开始没有块,在其向tracket注册后,连接邻近peers获取块,在下载的同时也在上传;peers可以在任意时候离开并再次加入:拥有完整文件时依然可以大公无私留在洪流中上传文件,也可以在只有文件子集时立刻离开后续再返回

拉块

pulling chunks,peer A主动向洪流中的peer B请求,B会优先发送给其网络中最稀缺的资源--rarest first

防吸血

tit-for-tat(一报还一报),peer A把chunk以最高速发送给4个peers,每10s评估,但为了避免形成小圈子导致没有新数据/垄断数据,每30s随机选择peer主动传输数据.这样peer A有可能变成该peer的top4之一,从而打破小团体,而且避免了某些peer只下载不上传,保证公平性

场景

centralized directory(集中式目录),P2P网络中文件传输可以非集中,但很多时候定位资源是高度集中的,peer需要先向目录服务器请求资源的地址,才能直接点对点传输.这带了的问题:

• 单点故障:目录服务器崩溃,P2P应用崩溃
• 性能瓶颈:大型P2P系统中,集中式服务器要维护庞大数据库,每秒可能处理大量查询
• 版权问题:法律系统更容易关闭目录服务器

洪泛

P2P网络中,一台peer的查询msg通过已有的TCP连接传播,每个peer收到后先检索自己,有资源则和查询peer直接建立连接,没有则继续转发msg,peer在其中担任了:server/client/router,洪泛避免了设置目录server,采用广泛的转发来查询可用资源

缺陷

1. P2P洪泛网络中peer隐藏自己;
2. flooding范围无法确定,当查询到后其余msg还在传播,浪费资源

解决:层次化overlay(覆盖),一些peer选出一个leader,类似于目录server,leader可动态调换,当group内peer查询,先由leader在组内定位,如果组内没有,在leader直接进行洪泛查询

概述

DHT是一个分布式的P2P数据库

• 数据库存放(key,value)键值对
• key是内容类型,value是IP地址
• peer使用key查询DB,DB返回对应value
• peer也能插入键值对

DHT标识符

给定一个nbits标识符,可以分配给[]个peers,key需要和标识符相对应,这需要hash函数,即DHT来历,由于hash函数可以处理冲突,因此DHT可以映射的资源数目可以超

分配keys

P2P网络中peers不一定在线可用,因此分配key时,key对应的id也许不存在,此时采用"immediate successor"(近邻后继)

捷径

在典型的循环DHT中,可能遇到命中率低的问题,查询被不断传递,此时使用cut可以提高效率

搅动

peer churn:peer可随时离开,但DHT中的peer需要随时知道上任/继任者的IP,因此需要定时ping,查看是否alive

• 区块链实际上为分布式账本
• 任何改动被按时间次序的记录下来
• consensus共识:如何证明peer的好坏,需要达成共识,有以下几种方式

• POW: proof of work,付出足够的工作证明自己

比特币即为POW,挖矿本质是耗费算力解题,证明自己后才能留下记录,即产生币

• POS: proof of stake,有足够的利益证明自己

• smart contact

场景

类似skype的软件进行P2P通信时,面临问题:内网IP相同的机器在全世界同时可能在线非常多,因此不能直接通过内网IP进行通信

解决

NAT运行在router上,内网IP发送的数据被NAT替换IP后发送到外网,返回时同样"拆马甲"

定位

NAT作为可变临时地址,当两个peer中一个在外网时,可由内网peer去找固定公网IP的peer,但如果两个都是内网peer,此时需要第三方在公网中的机器作为中介进行处理

服务

• 供运行在不同host上的程序进程逻辑通信
• 端系统中的传输层协议:

• 发送方:app层msg-->分割为segments-->传递给network层
• 接收方:把segment重组为msgs

协议

见: Ch2 因特网传输协议服务(TCP/UDP是传输层协议)⭐

multiplexing

demultiplexing

定义

源host从不同socket中收集数据块,为它们封装head(用于以后分解),从而生成segments,再把segments投递到network层

接收端主机,运输层检查字段,标识出对应的接收socket,将把segments定向到对应socket
多路复用/分解原理解释了为什么多个socket可使用一个port通信

原理

• 主机接收IP数据报

• 每个数据报有S_IP,D_IP
• 每个数据报携带一个报文段
• 每个报文段有一个S_Port number,D_Port number

• 主机使用IP&Port numbers就能直接找到对应的socket
• 参考: 关于port

数据报报文段

特征

• 创建指定端口的socket
• 一个UDP socket是由一个二元组<dest IP,dest port number>全面标识的
• 接收UDP数据报时:

• 检查报文段中dest port number
• 通过port number直接引导到对应socket

• 当s IP不同时,只要d IP和port一样,报文段就会引导至一样的socket

SP的作用

segment中的dest port可供引导segment;

而SP是在当接收方需要回发报文时,会从中取值,加上发送方IP作为地址

特征

• CP socket由四元组标识<sIP,sP,dIP,dP >,接收方使用四个值直接引导报文段到指定socket
• server host可支持同时多个TCP sockets,下图
• 因为四元组的区分,web服务器对一个client可以有不同的socket(不同端口),见下图

个人理解

所谓多路复用就是一条路可以同时传输多个来自不同links的segs,要做到这点,就需要区分segs,因此UDP中使用二元组,TCP中使用四元组,解复用自然而然就是"各回各家,各找各妈"

特征

• 无连接

• 没有s/r之间的握手;
• 每个UDP上的seg都独立于其他segs被处理

• 尽力而为的传输

• 丢包,乱序

• 简单
• seg的header更小
• 无拥塞控制

UDP seg中length指明了seg的字节长度(data+header)

用于

适合loss tolerant以及rate sensative的程序,如:流媒体,DNS

改进

目的

检测segs中的错误

流程

sender:

• 把seg内容视为16bits序列
• 对所有16bits字求和,并回卷溢出,结果取反码作为checksum
• 把checksum放在UDP seg中

receiver:

• 根据收到seg内容计算checksum
• 对比计算结果和checksum域中的值

• 相等:no error
• 不相等: error

举例

服务抽象

理想情况:数据可以通过可靠的信道传输,从而bits不会损坏或丢失,而且所有数据都按照发送顺序交付.如TCP连接

实现协议

可靠数据传输协议 reliable data transfer protocol.如TCP就是传输层上的可靠传输协议

问题

可靠协议的下层协议也许不可靠.如TCP在网络层上不可靠的IP协议上传输

讨论目标

开发一个协议,能够考虑到底层带来的bits损坏或丢失升至丢包,注意的是可靠数据传输原理不针对某一层,在各层中都有体现

约定

• rdt/udt: 可靠/不可靠数据
• rdt_send():上层调用(如app),传输可靠数据
• udt_send():由rdt调用,通过不可靠信道传输数据给receiver
• deliver_data():rdt调用,传递数据给上层
• rdt_rcv():当packets抵达信道的rcv端时调用
  目前只考虑单向(unidirectional)数据传输,以下过程设计到FSM,有限状态机

• sender

接收高层数据,打包后通过信道传输

• receiver

从底层接收packet,从中取数数据后传给较高层

这种理想情况下,receiver无需提供任何信息给sender,因为无需担心出错

FSM

分析FSM

• sender

接收上层调用后把数据和checksum打包通过信道发送-->进入wait state:如果收到NAK,则重发packet继续当前state;如果收到ACK-->进入等待命令的下一状态

注意:当sender等待ACK/NAK时,无法接收上层调用,这种机制叫做"停等"(stop-and-wait)

• receiver

收到packet后,如果pkt中有bit错误,返回NAK;如果没有错误,提取数据,传递数据,返回ACK

理解

此时需要考虑到确认信息的需求--自动重传请求协议(Automatic Repeat reQuest, ARQ),协议中有三种应对bit差错的地方:

• 差错检测
• 接收方反馈:

• ACK, acknowledge:肯定确认,理论上只要一个bit:1
• NAK, negative ~:否定确定,同样一个bit:0

rdt2.0缺陷

可能的解决和新的问题

实际方案

ACK/NAK本身出现错误

给Receiver返回的ACK/NAK也设置checksum.当Sender收到含糊的ACK/NAK分组,则重传pkt

困难在于receiver不知道上一次ACK/NAK是否被sender正确接收,从而无法区分自己正在接收的pkt是上次重传还是新的

在pkt中添加编号,即把当前pkt的序号放在字段中,结合停等机制,server会重发不确定的pkt,而receiver通过序号就知道接受的是重发pkt还是全新pkt

S

等待调用0状态-->打包发送pkt0-->

停等0状态:

①当收到NAK或发现ACK/NAK出错(corrupt),则重新发送pkt(ACK/NAK本身无需携带序号,由于停等机制,sender知道这次ACK/NAK出错发生在最近的pkt0),继续停等0状态

②当收到ACK且反馈本身无误(notcorrupt)-->进入等待调用1状态

Sender端的corrupt表示ACK/NAK混淆
receiver端的corrupt表示pkt有误

R

等待传入0状态:

①如果发现传递出错(corrupt),则打包返回NAK,继续等待传入0状态;(错误分组)

②如果接收到pkt1,传递无误,则返回ACK,继续等待传入0状态(失序分组)

③如果发现pkt0,传递无误-->提取数据,传递数据,返回ACK(正常分组)-->进入等待传入1状态

FSM

分析FSM

• Sender

等待调用0状态-->打包发送pkt0-->

停等0状态:

①当收到ACK1或ACK/NAK混淆时,重发pkt0,继续停等0状态

②当收到ACK0且反馈本身无误(notcorrupt)-->进入等待调用1状态

• Receiver

等待传入0状态:
①收到pkt1或传递出错,发送ACK1

②收到pkt0且传递无误-->提取数据,传递数据,返回ACK0-->进入等待传入1

理解

冗余ACK体现在:

进入①前,Sender必定收到了ACK1,再次进入①收到ACK1,说明Receiver没有正确接收pkt0

问题

需要做什么

想法:时限+重传+冗余pkt

• bit受损/丢失
• 丢包

• bit检测/应对
• 丢包检测/应对

让sender负责检测和恢复丢包,无论pkt或者receiver的ACK丢失,sender都无法收到合适的响应,设定一个时限,当超过后,就认为发生丢包,进行重传.由于时延的不确定,需要考虑到延迟过大导致误以为丢包后重复传输pkt产生的冗余pkt,为实现基于时间的重传,需要timer

①每次发送一个pkt(新pkt或重传pkt)时启动
②可以响应特定动作从而中断
③终止

FSM

分析FSM

• Sender

基本类似rdt2.2版本,等待调用0状态->打包发送pkt0,开始计时-->
停等0状态:

①收到ACK1或ACK/NAK混淆,触发计数器进入②(计时一直进行)

②时间到,重发pkt0,重新计时

③收到ACK0且反馈本身无误,停止计时-->进入等待调用1状态

• Receiver

等待传入0状态:
①收到pkt1或传递出错,返回ACK1,保持等待0

②收到pkt0且传递无误,返回ACK0-->进入等待传入1状态

rdt3.0只是功能上正确的协议,性能孱弱,左图说明了其在传输文件时低下的利用率(utilization),问题在于它的停等机制,让sender必须在接收到ACK后才能发出下一个pkt

改进思路:流水线

• 必须增加序号:流水线使得同时在link上的未确定pkt有多个,不能只是用0,1
• sender/receiver都必须缓存多个pkt,因此sender必须缓冲那些已经发送但是没有确认的pkt

模式

• base:标识已发送但还未ack的pkt
• nextseq:标识待发送的pkt
• N:窗口尺寸,即缓冲大小,

seq<base+N,窗口未满,可继续打包

base=seq,无待发送pkt

可靠性

sender

1. 初始base=(next)seq=1,此后只要seq<base+N即buffer未满,就可接收数据打包发送,然后seq++;
2. 如果收到正确返回,base++.当base==seq说明buffer里没有pkt等待确认,停止计时,否则重启计时;
3. 收到任何ACK重置timer
4. 当时间到,重发当前窗口从[base]~[seq-1]的所有pkt

receiver

1. 初始化(expect)seq=1;
2. 接收到正确且合序的pkt,提取数据,返回对应pkt,seq++;
3. 其余默认情况下返回当前最大正确顺序seq的pkt;

特征

1. 顺序性:对于sender,必须收到base的ack才能窗口右移,否则do nothing;对于receiver,必须接收expectseq的pkt才能返回pkt并seq++
2. 按窗口重发:当timeout时,无论处于sender的[base]~[seq-1]的pkt是否能正确到达,重发所有(回退)
3. 积累确认,对序号为n的分组确认时,表明接收方对n和n之前所有的pkt都正确接收

示意

模式

SR下receiver也设置了buffer,从而使得双方可以乱序发送/接收

可靠性

• sender

只有收到窗口中最小pkt的ack后base++;当timeout后,重发当前最小未确认的pkt,重启计时器

• receiver

对于在窗口中的pkt,正确接收后返回ack,不用考虑顺序;对于冗余/错误pkt,do nothing由sender的timer处理,时间到后对面自然会重发

模式

解:这道题先分析b更合适,注意在GBN下:

b).接收方expseq=k,说明从pkt[k-N]~pkt[k-1]都已经确认接收返回ACK,则取值范围[k-N,k-1]

a).由b),接收方返回了N个ACK,但不能保证都正确抵达:

• 最坏:N个ACK都出问题,sender的base还是k-N,则seq取值范围[k-N,k-1]
• 最好:N个ACK都正确接收,窗口已经移动N位,base=k,此时seq的变化范围[k,k+N-1]

SR接收方窗口大小问题--分组序号有限:0,1,2,3且receiver窗口大小为3.
a)receiver的三个ACK全部丢失,因此sender需要重传第一次的seq为012的pkt012

b)sender发送pkt3丢失,产生不同步,sender发送pkt4(seq0).receiver需要确认seq3和第二次出现的seq0==>对于receiver来说,无法辨别这时的seq0是新pkt或者重传

解:结合上一题,依旧设此时expseq=k,窗口大小N

考虑极端情况下,s和r"最不同步"的情况即receiver接受了N个pkt,返回的N个ACK全部丢失.此时receiver窗口最右端为k+N-1;sender的seq最坏为k-N,此时最大不同步距离为

包含2N个不同序列号,则为了避免发生序号重叠,应该保证序号空间范围k≥2N

组成

• 一台host上的(发送)buffer,变量和进程socket
• 另一台host上的(接收)buffer,变量,进程socket
  注意:两台host之间的网络元素(routers,switchers)都没有为连接分配cache和变量

特点

• 面向连接的:两个进程在数据传输之前,必须相互"握手"--相互发送预备报文段以确保数据传输的参数
• 一一对应:一个sender,一个receiver
• 可靠的有序字节流
• send/receive buffer
• full duplex data(全双工数据):在一条链接中的双向数据流;

• MSS:maxmium segment size最大报文段长度,TCP可从buffer中提取放入segment中数据数量的最大限制

• 流控

流程

三次握手

连接建立

数据封装传递

对比UDP

• TCP提供:可靠有序传输,流控,拥塞控制,
• UDP仅提供:process2process投递, 数据校验(checking)

• seq:字节流,指示seg中第一个byte的数据
• ACK:期待从对方接收的下一个byte数据

右图👉

A:发出C,C的第一个byte为42,A期待收到79

B:发出C,C的第一个byte为79,B期待收到43

RTT

sampleRTT是直接采样得出

timeout

ACK丢失

早熟(timeout过早)

积累ACK

只要sender收到的ACK正确无误,则说明receiver对之前的PKT都正确接收,则sender可以放心的一次性确认,不用在乎中间ACK丢失

如果完全依靠timeout触发重传,效率不够高,比如窗口第一个pkt丢失,可能发出多个pkt后才能timeout.GBN因此引入快速重传,当sender收到多个冗余ACK后,判断该pkt丢失,不管timeout,立即重传

背景

由于TCP在sender/receiver都具有buffer,为了避免处理速度不一致导致receiver端buffer溢出数据丢失,需要进行流控,使得两端速度相一致,流控算法即GBN/SR

实现

TCP让sender维护一个接收窗口(receiver window),用于提示receiver还有多少buffer可用,且全双工通信使得两端发送方各自维护一个窗口

场景

A发送文件给B:B为连接分配RcvBuffer,B上进程定期从中读取数据,定义变量:

• LastByteRead:B从buffer中读出的data flow最后一个byte编号
• LastByteRcvd:从网络到达且放入B接收缓存中数据流的最后一个Byte编号

为了不溢出,必须保证(rwnd标识接收窗口)

LastByteRcvd-LastByteRead≤RcvBuffer

rwnd = RcvBuffer-[LastByteRcvd-LastByteRead

• 第一步: client发送一个特殊的TCP报文段,其中不含app层数据,但header中包含一个标志位SYN,被设为1

SYN=1,seq=client_isn

• 第二步: server收到特殊seg,从中提取SYN,为TCP连接分配buffer和变量,向client发送允许连接报文段SYNACK,不含数据

SYN=1,seq=server_isn,ACK=client_isn+1

• 第三步: client收到SYNACK,也为连接分配buffer和变量,同时发送另一个seg给server,对server的seg进行确认,此时连接已经建立,SYN置为0,可以携带数据

SYN=0,seq=client_isn+1,ACK=server_isn+1

• 之后: 此后可以互相发送seg,在每个seg中SYN都被置为0

WireShark抓包:

• 阶段一:Seq=0,ACK=0,SYN=1
• 阶段二:Seq=0,ACK=1,SYN=1
• 阶段三:Seq=1,ACK=1,SYN=0

client应用进程关闭socket

• 第一步

TCP向server端进程发送一个特殊seg,header中包含标志位FIN,设为1

• 第二步

server收到FIN,回复ACK然后

• 第三步

server发送自己的终止seg,FIN设为1

• 第四步

client收到FIN,回复ACK

server收到ACK,连接关闭

client

server

2发送方,1无限缓存路由 (路径带宽R,λ_in单位byte/s)

实际拥塞情况:左--troughout与发送速率关系;右--delay与发送速率关系

分析:
a)两条路径同时发送,每条路径带宽最大R/2,因此左图在小于R/2时吞吐量与速率成线性关系,当到达R/2后,无法超出带宽,保持R/2

b)当λ_in接近R/2时流量强度接近并超过,不可避免的开始排队并发展成无限期排队(参考:Ch1:流量强度)

2发送方,1有限缓存路由

由于缓存有限,会发生丢包,该情况下引入"重传"机制:

• λ_in表示sender应用层->传输层传递初始msg速率
• λ_in'表示sender传输层->网络层传输初始seg或重传seg速率,也叫网络的供给载荷(offered load)
• λ_out表示receiver把报文段从传输层->应用层速率

分析

a)假设hostA只在buffer空闲时发送分组,此时λ_in=λ_in'

b)假设hostA在确认一个packet丢失后才重发,当时(初始数据+重发数据)等价于网络中每发送0.5R数据,其中有0.333Rbyte/s是初始数据,0.166Rbytes/s是重发数据

c)假设hostA的timer设置较短,会提前重传,此时效率更为低下

4发送方,N有限缓存路由&多跳路径

考虑A->C,经过R1,R2,此时R2被共享,区分:此时可以看到每个路径的带宽R可被一个host完全占有

• 当λ_in'较小时,对吞吐量的影响类似上一情况
• 当λ_in'较大时：

• 理论通过R2的A-C流量最多为R(R1到R2)
• 但此时如果B-D的供给载荷增大,二者会竞争,甚至死锁，A-C的吞吐量可能趋于0，即如图所示情况
• 此外,当分组仅丢失在第二跳时,第一条的传输也完全无意义

e2e控制⭐

• 网络层未给运输层拥塞控制提供显式支持
• 端系统通过观察网络行为(丢包,时延)推断
• TCP拥塞控制采用此方法

network-assisted

• router向sender提供显式的反馈,比如一个bit来只是链路的拥塞情况

理解:此约束通过限制sender未确认的数据量间接限制了sender的发送速度:对于一个丢包和发送delay均可不计算的连接,在每个往返时间RTT的起始点,最多可以发送cwnd字节数据,该RTT结束时sender接收确认报文.因此sender发送速率大概为cwnd/RTT字节/s,通过调整cwnd可以调节发送速率

慢启动

• 初始:给cwnd起始设置为1MSS(最大报文段长度)的较小值,使得初始速率为MSS/RTT
• 传输:之后每次sender确认一个seg后,把cwnd增加一个MSS

（第二次,sender发出两个seg,因此会有两个ACK,sender对cwnd加两个MSS,下次同时发出四个seg...依次类推达到cwnd每次翻倍的效果）

• 结束:发生拥塞后,有三种结束慢启动增长cwnd的方式

1. 当发生timeout标识的拥塞sender把cwnd重置为1-->重启慢启动过程;同时设置ssthresh为cwnd/2
2. 当cwnd==ssthresh(慢启动阈值)时结束慢启动且sstresh=cwnd/2-->拥塞避免
3. 如果发生快速重传(Fast retransmit)-->快速恢复

拥塞避免

• 传输:如果进入拥塞避免,此时如果cwnd继续翻倍,很容易又进入拥塞,因此采用每次cwnd增长一个MSS,通用实现一般是接收到ACK后对cwnd增加MSS*(MSS/cwnd)

(当MSS=1000,cwnd=8000:假设一个RTT发送8个segs,当一个seg的ACK传达到sender,cwnd增加1000(1000/8000)=125,当RTT结束,cwnd共增加1000)

• 结束:丢包事件发生

1. 当由超时引发(说明拥塞):同上cwnd=1,sstresh=cwnd/2-->慢启动
2. 当被3冗余ACK触发(说明只是出错,不一定拥塞),反应不应剧烈-->快速恢复:cwnd减半,每个冗余ACK使cwnd++,最终产生的效果为cwnd=1/2cwnd+3,sstresh=1/2cwnd-->拥塞避免

快速恢复

• 进入快速恢复后,立刻重传丢失的seg,重传完毕-->cwnd减半,每个冗余ACK使cwnd++,最终产生的效果为cwnd=1/2cwnd+3,sstresh=1/2cwnd-->拥塞避免
• 如果重传未抵达就发生timeout,则cwnd=1,sstresh=cwnd/2-->慢启动

小结

TCP拥塞控制称为"additive increase,multiplicative decrease"(加性增,乘性减,AIMD),因此期cwnd变化情况如右图所示

公平性

如果K个TCP连接共享带宽为R的瓶颈链路,每条链接应该达到R/K的平均速率

TCP

红线:实际吞吐量

蓝线:平均值

• A->B:起始,此时连接1,2共同进入慢启动,带宽和<R,因此cwnd同步增加,吞吐量同理
• B->C:到达B,二者吞吐量之和大于R,发生减半,骤降到C
• C->D:与A->B类似

因此TCP实现了公平性

并行TCP

• 因为无法阻止TCP应用创建多个并行连接,公平性无法解决
• 一个app可以创建多个TCP连接传输一个对象,从而抢占大部分带宽

UDP

实时多媒体(Internet电话,视频会议)不愿意在TCP运行,因为不想被传输速率遏制.使用UDP时:即便网络拥塞,数据也要以恒定速率发送,即便丢包,不愿意把速率降至"公平",以保证不丢包

a) Identify the intervals of time when TCP slow start is operating.

b) Identify the intervals of time when TCP congestion avoidance is operating.

c) After the 5th transmission round, is segment loss detected by a triple duplicate ACK or by a timeout

d) After the 11th transmission round, is segment loss detected by a triple duplicate ACK or by a timeout

e) What is the value of threshold at the 14th transmission round

f) What is the value of threshold at the 18th transmission round

g) During what transmission round is the 70th segment sent?

Assuming a pkt loss is detected after the 27th round by the receipt of a triple duplicate ACK, what will be the values of the congestion window size and of threshold?

时间

cwnd

th

备注

时间

cwnd

th

备注

1

1

14

2

12

2

2

15

4

12

3

4

16

8

12

timeout

threshold=1/2cwnd

4

8

17

1

4

5

16

18

2

4

6

32

3dup
threshhold=1/2cwnd

19

4

4

cwnd==threshold
慢启动->避免

7

19

16

20

5

2

8

20

16

21

6

2

9

21

16

22

7

2

10

22

16

23

8

2

timeout

threshhold=1/2cwnd

11

23

16

24

1

4

12

24

16

timeout

threshhold=1/2cwnd

25

2

4

13

1

12

26

4

4

cwnd==threshold
慢启动->避免

1. [1,6],[13,16],[17,19],[24,26]
2. [7,12],[19,23]
3. 3dup
4. timeout
5. 12
6. 4
7. 1+2+4+8+16+32+19=82,在第7个round中

结果

分析

Time

SEND

RECV

Time

SEND

RECV

time

base
(N=3)

nextseq

timer

0

1

220

5

1

1

10

2

230

(8 丢失) 

0

1

2

start

20

3

240

9

10

1

3

30

250

10

20

1

4

40

4