[Textbook]: Computer Networking: A Top-Down Approach(7th Edition) by James F. Kurose, Keith W. Ross
搜索”#解题”查看所有计算题解题方法

Chapter 1: Introduction of Networking

[Textbook] 1.x, 2.7

What’s the Internet

Connected Devices
- Hosts = End systems
- Run network applications
Communication links
- Optical fiber, Copper, Radio, Satellite
- Build physical networks
Routers
- Forward packets between physical networks

Com.Dev. —>Com.Lnk.Phys.NtWk—>RouterInternet

Building Internet

Communication Infrastructure
- Enables distributed applications
- e.g: Web, VoIP, email, online games, e-commerce, file sharing
Communication Services Provided
- IP: Unreliable, data delivery
- TCP: Reliable data delivery
- QoS: Guaranteed delay and throughput
  
  Delay: 延迟; Throughput: 吞吐量/网速
Network Protocols
- Control sending, receiving of messages
- e.g: HTTP, Skype; TCP, IP; PPP, Ethernet
Internet Standards
- IETF: Internet Engineering Task Force
- RFC: Request for comments
Internet: “network of networks”
- Public Internet versus private Intranet
- Loosely hierarchical
  
  Intranet: 内部网

Internet History

1961-1972: Early packet-switching principles
1972-1980: Internetworking, new and proprietary nets
1980-1990: new protocols, a proliferation of networks
1990’s, 2000’s: commercialization, the Web, new apps
2007~Now:
- P2P applications
- Iot: Internet of things
- SON: Self-Organizing Network
- SDN: Software Defined Network
- CDN: Content Distribution Network
- ICN: Information-Centric Network

Access Internet

Network Edge

End systems (hosts)
- Run application programs
- e.g. Web, Email
Client/Server model(P2S)
- Client host requests, receives service from always-on server
- e.g. Web browser/server; Email client/server
Peer-to-peer model(P2P)
- Minimal (or no) use of dedicated servers
- e.g. Skype, BitTorrent

Access Networks

Physical media(Wired and wireless com.lnk.)
Connect end systems to edge router
- Residential access networks (Home)
  - Dialup via modem:
    - Up to 56Kbps
    - direct access to router
  - DSL: Digital Subscriber line
    - Deployment: Telephone company
    - Upstream: 1~3Mbps, Downstream: 8~24Mbps
    - Dedicated physical line to telephone central office
- HFC: hybrid fiber coax
  - Asymmetric: up to 30Mbps downstream, 2 Mbps upstream
  - Homes share access to ISP router
  - Deployment: cable TV companies
- Institutional networks (school, company)
  - LAN connects end systems to router
  - Ethernet:
    - 10Mbps, 100Mbps, 1Gbps, 10Gbps
    - Modern configuration: Ethernet switch backbone connect end systems
- Mobile access networks
  - End systems <-------->Shared wireless mediaRouter
  - Wireless LANs (WLAN)
    - 802.11b/g(WiFi): 11 or 54Mbps
  - Wider-area wireless access
    - Provided by telecommunication operator
    - 10Mbps over cell network
    - LTE(4G) and WiMAX
    - 20Gbps(5G?)
  - Modern family
    - ———=to/from cable headend Modem =—-= Router/Firewall =—-= Wireless AP - - - - Wireless Device
    - ———=to/from cable headend Modem =—-= Router/Firewall =—-=Ethernet Device
Performance
- Bandwidth (bps)
- Shared or dedicated
  
  Dedicated: 专用的

Network Core

Interconnected routers(Network of networks)
Circuit Switching
- Performance: Link bandwidth, switch capacity
- Dedicated circuit per call, e.g: telephone
- Circuit-like (guaranteed) performance
- Require call setup/teardown
Packet Switching
- Each end-to-end data stream divided into packets
- Application A, B packets share network resources
- Store and forward: packets move one hop at a time, stored (queued) at switches
- Each packet uses full link bandwidth
- Resource contention: aggregate (burst-up) resource demand can exceed amount available
- Congestion: packets queue and wait for link use
Statistical Multiplexing
- Link bandwidth dedicated or shared
- Sequence of packets have or have not fixed pattern
- Source that has higher bit rate occupies more time intervals
Virtual Circuit
- Circuit Swithching + Packet Switching
- Fixed router and main cross roads
- Shared resource, requird congestion control
- Resource can be preserved, leadingto different performance
- Require connection setup/teardown
Internet Structure – Network of Networks
- Roughly hierarchical
- At center: “Tier-1” (National) ISPs
- “Tier-2” ISPs: smaller (often regional) ISPs
- “Tier-3” ISPs and local/edge ISPs, connect access networks

Typical Network Applications

Client/Server Applications
P2P Applications
Client-Server Architecture

Server
- Always-on host
- Permanent IP address
- Server farms for scaling
Clients
- Communicate with server
- May be intermittently connected
- May have dynamic IP addresses
- Do not communicate directly with each other
Web and HTTP
- Request: Clients use browser to send URL(URI)s via HTTP to servers requesting a Web page
- Construct: Web pages constructed using HTML (or other markup language), inter-connected by URL
- Respond: Servers (or caches) respond with requested Web page
- Display: Client’s browser displays Web page returned by server
FTP
- Transfer file to/from remote host
- Control connection: Login/logout, file trans command/reply
- Data connection: File contents, client side initiates file transfer
E-Mail
- MIME: Multi-purpose Internet Mail
  
  Non-text data
- SMTP: Simple Mail Transfer Protocol
  
  Simple text mail
- POP: Post Office Protocol
  
  Mail retrieval from server, including authorization and download
- IMAP: Internet Mail Access Protocol
  
  Manipulation of stored mails on server

P2P Application

BitTorrent
- File divided into chunks
- Peer join torrent
  - Register to tracker to get list of peers
  - Connect to some peers
  - Issue requests for missing chunks
- Upload chunks
  - send
- Peers may come and go
Skype
- P2P VoIP: PC/Phone
- Proprietary application layer protocol
  
  Proprietary: 专有的
- Make a call
  - Register: SC(skype client) register with SN(super node)
  - Authenticate: SC authenticate(log in)
  - Call: SC contact SN with caller ID
  - SN contacts other SNs to find callee address
  - SC directly contacts callee over UDP/TCP
- Login server: authentication; Super node: exchange address
- Protocol Layers and Service Model

OSI

Physical
- bits across link
- Physical interface
- Physical aspects: Mechanical, Electrical/Optical, Functional/Procedural
Data Link
- frames
- activation, maintenance, deactivation of connection
- medium access control for muiltiple access
- error detection and retransmission: error-free transmission
- flow control
Network
- packet across mulltiple links/networks
- addressing and routing
- Forwarding transfers packet across a node
- Congestion control to deal with traffic surges
- Connection setup, maintenance, and teardown
Transport
- data between end systems
- Reliable stream transfer or quick-and-simple single-block transfer
- Connection setup, maintenance, and release
-Session- into App.
-Presentation- into App.
Application
- Means for applications to access OSI environment

Service Primitives and Parameters

      ServiceUserA                  ServiceUserB
          +  |                            +  |
Confirm   |  |   Request     Indication   |  |  Response
          |  +                            |  +
             (N-1) Layer Service Provider

TCP/IP Protocol Architecture

Used by global Internet

Application: supporting network applications

FTP, SMTP, HTTP
Transport: process-process data transfer

TCP, UDP
Internetwork: routing of datagrams across net of nets

IP, routing protocols
Link: data transfer between neighboring routers / hosts

PPP, Ethernet
Physical: bits “on the wire”
Protocol Data Units(PDU)
Control info is added to user data at each layer
Segment and Header: Transport layer segments application data, a transport header added
- Destination SAP, Sequence number, Error detection code
  The IP Layer in Detail
Sender encapsulates segments into datagrams
Receiver delivers segments to transport layer
Router examines header fields in all IP datagrams

Network Programming

Socket programming
- Build client/server application that communicate using sockets
- A socket is a pair of [IP addresses, port]
Socket API
- Introduced in BSD4.1 UNIX, 1981
- Explicitly created, used, and released by applications
- Implementing client/server paradigm
2 types of transport service via socket API
- Unreliable datagram, i.e. UDP
- Reliable, byte stream-oriented, i.e. TCP

Socket Programming with TCP

Client: Create socket->Specify [IP_s, Port_s]->Recieve reply, connection [IP_c, Port_c; IP_s,Port_s]
Server: Create listening Socket->Accept contact, create new socket->connection [IP_c, Port_c; IP_s, Port_s]
Server distinguish clients using [IP_c, Port_c]

Interaction:

    SERVER                                        CLIENT 
    create listening socket  
      |                         TCP con. setup
+-> wait for connection      <---------------->  create socket
|     |                                             |
|   read request             <-----------------  send request
|     |                                             |
|   write reply              ----------------->  read reply
|     |                                             |
+-- close                                         close

Socket Programming with UDP

No connection
Sender attaches IP address, port of destination to each packet
Receiver extract IP address, port of sender from received packet
Transmitted data may be received out of order, or lost

Interaction:

    SERVER                                        CLIENT 
    create listening socket  
      |                                             
+-> read request             <-----------------  send request
|     |                                             |
|   write reply              ----------------->  read reply
|     |                                             |
+-- close                                         close

Delay, Loss and Throughput

Delay

Source of delay
- Transmission: $L/R$; microseconds
- Propagation: $d/s$; microseconds
- Nodal processing: Error-check & determine link; microseconds
- Queuing: wait in queue, congestion level; seconds
Queuing Delay
- Traffic intensity: $\rho = L\times\alpha/R$
  $\alpha$: average packet arrival rate
  - $\rho\sim 0$: average queuing delay small
  - $\rho\to 1$: delays become large
  - $\rho\geq 1$: delays infinite
“Real” Internet Delays and Routes
- traceroute
  - Provides delay measurement from source to router along end-to-end Internet path towards destination
  - Each intermediate router will return packets to sender
  - Sender records time interval between transmission and reply

Loss

Buffer of a router has finite capacity
Packet arriving to full queue dropped
Lost packet may be retransmitted, if not, it’s lost

Throughput

Rate (bits/unit per time) at which bits transferred between sender/receiver
Instantaneous or Average
Multiplexing: $\min(R_c, R_s, R/N_l)$

Networks under Attack: Security

Attacks on Internet infrastructure
- Infecting/attacking hosts: malware, spyware, worms, unauthorized access
- Packet sniffing, replay, masquerade
- Denial of service: deny access to resources (servers, link bandwidth)
Internet not originally designed with security in mind
- Original vision: “a group of mutually trusting users attached to a transparent network”
- Internet protocol designers playing “catch-up”
- Security considerations in all layers!

Different Types of Malware

Virus: Infection, Run executables, Self-replicating
Worm: Transmitting over a network
Trojan horses: Disguised as innocuous or desirable, Tempting user to run
Backdoor: Bypassing authentication procedures
Adware: Advertisements
Spyware: Recording activity

Types of Attack

Denial of Service(DoS)
- overwhelming resource with bogus traffic
- Break into hosts -> use compromised hosts to send packets to target
Packet Sniffing
- Broadcast media required
- Promiscuous NIC reads/records all packets passing by
IP Spoofing
- putting any value into IP source address field
- Receiver can’t tell if source is spoofed
Masquerade
- IP spoofing: send packet with false source address
- Record-and-playback: sniff sensitive info (e.g.,password), and use later

Catch-Up

What Trudy Might Do
- Eavesdrop: intercept messages
- Insert messages into connection
- Impersonation: can fake (spoof) source address
- Hijacking: “take over” ongoing connection by removing sender or receiver, inserting himself in place
- Denial of service: prevent service from being used by others
How to Handle This
- Encryption: the message cannot be understood
- MAC: the message cannot be altered
- Sign: the source cannot be forged

Chapter 2. Direct Link Networks

[Textbook] 5.x, 6.x

链路层概述

结点(Node): 主机(Host), 路由器(Router)
链路(Link): 连接相邻节点的通信通道

链路层服务

成帧: 数据组合成帧, 若干首部+数据字段(网络层数据报)
接入: 媒体访问控制(MAC), 协调结点在共享媒体的传输
可靠交付: 保证无差错地传输网络层数据报(有线连接有时不提供这一服务)
检错和纠错: 硬件完成, 比运输层和网络层复杂

链路层实现

网络适配器/网络接口卡(Adapter/NIC)
- 核心是链路层控制器
- 单独的PCI卡或集成到主板

差错检测和纠正技术

差错检测和纠正比特(EDC):
[D]–(发送)–>[D+EDC]–(易出错链路)–>[D’+EDC’]–(接收)–>有错丢弃, 无错则D’=D
未检出比特差错: D’<>D, 但仍然有效, 未检出错误
前向纠错: 接收方检测和纠正错误
奇偶校验
单个奇偶校验位
- |EDC|=1
- 检测奇数个错误比特
二维奇偶校验
- 数据d组成i×j矩阵, 每行每列有校验比特
- 可以检测任意2比特差错, 纠正单比特差错
  检验和方法
因特网校验和
- 数据作为16比特整数进行求和, 取反码作为校验和, |EDC|=16
- D+EDC同样求和, 全1则正确, 有任意0则有错
#解题: 因特网检验和计算方法
- 分段: 16bit一段
- 求和: 挨个加和, 最高位进位到最低位
- 取反: 取反码, 接在数据后面发送
- 检验: 对收到的信息进行以上三步, 全1则无误
  循环冗余检测
循环冗余检测/多项式编码
- r+1比特的多项式, 生成r比特CRC, 不断按位异或
- 检测小于r+1比特的突发(连续)比特差错, 检测任何奇数个比特差错
#解题: CRC计算方法(r+1比特的多项式)
- 补0: 补r个0到需检验的数据后
- 异或: 类似除法, 用异或代替减法, 不断消除最高位的1
- 取余: 最后得到的r位余数就是CRC, 代替那r个0, 接在数据后
- 检验: 对收到的数据做前三步, 余数为0则无误

流量控制

停止等待流量控制

流程
- 源点发送
- 终点收到帧, 回复ACK
- 原点收到ACK, 发送下一帧
- 终点不发ACK终止流
对长帧效果好
滑动窗口流量控制
流程
- 接收端缓存大小 W
- 发送端在没有收到ACK前可以发送W个帧
- 每个帧通过序号来标识, 序号大小受字段长度限制(k bits)帧以 2^k 为模编号($0\to 2^{k}-1$)
- ACK(RRx)包含下一个期望收到的帧编号x
最大窗口大小: $W\leq 2^{k-1}-1$, 防止歧义
差错控制
- Go back N: NAK, 然后出错帧及其后的全部重传
- 选择拒绝: 被拒绝的帧重传, 接收端缓存后面的

多路访问链路和协议

广播链路: 多点, 一个信道
碰撞: 多个结点同时发送
信道划分协议
时分复用TDM
- 时隙slot, 每轮每结点一个时隙
- 速率: R/N, 负载不均衡时浪费, 统计时分复用解决, 有额外开销
频分复用FDM
- 分频率, 一人一频
- 速率: R/N, 负载不均衡时浪费
码分多址CDMA
- 每结点一个编码, 1电平为此编码, 0为编码取反
- 速率: R, 可同时发送(每个结点的编码必须线性不相关), 抗干扰

随机接入协议

时隙ALOHA
- 有ACK
- 前提: 每帧长L, 每时隙L/R, 结点同步, 且在时隙开始时才传输, 碰撞检测够快
- 流程
  - 发送: 结点在一个时隙开始发送帧
    - 成功: 若没检测到碰撞, 则认为成功传输
  - 失败: 检测到碰撞, 在之后的时隙中以概率p不断尝试重传, 直到没有碰撞
- 效率: 取p=1/N时最大化, 当N趋于无穷时, 效率为1/e
ALOHA
- 有ACK
  
  除了不同步, 跟时隙ALOHA一样
- 流程
  - 发送: 结点在一个时隙开始发送帧
    - 成功: 若没检测到碰撞, 则认为成功传输
  - 失败: 检测到碰撞, 立刻以概率p不断尝试重传, 直到没有碰撞
- 效率: 取p=1/N时最大化, 当N趋于无穷时, 效率为1/2e(前后都可能有重叠)
CSMA/CD
- 无ACK
- 不做同步
- 流程
  - 监听: 监听信道是否空闲, 空闲时才开始传输
  - 传输: 传输时也不断监听是否有其他结点的信号能量
    - 成功: 未发现其他能量, 认为发送成功
  - 失败: 发现其他能量, 立刻停止; 发送48bit干扰信号
  - 等待(非持续): 等待一个随机时间, 回到”监听”重传
  - 回退(p持续): 之后的时间当中以概率p重传
  - 回退(1持续, 以太网): 使用二进制指数后退
    - 经历过了k次碰撞, 就从[0,…,2^k-1]中选一个K值, 等待512K个比特时间
    - k最大为10
    - 最多尝试16次发送
- 效率: 近似为
  $$\frac{1}{1+5d_{prop}/d_{trans}}$$
- 最小帧长: 检测冲突的时长不超过端到端传播时延的2倍, 取这一值为最小帧长

轮流协议

轮询协议
- 流程: 每个从结点n
  - 主节点发帧, 告诉从节点n能够发送的最大包数
  - 从节点发送不超过n帧
  - 主节点发现没有信号了, 继续轮询下一个从节点
- 缺点: 轮询时延(第一步耗时); 主节点损坏则信道无用
令牌传递协议
- 流程
  - 收到令牌
  - 如果有帧要发, 则发送不超过最大数目的帧数
  - 传递令牌
- 缺点: 令牌传播时延, 令牌丢失, 单点故障则信道崩溃

用于电缆因特网接入的链路层协议

信道划分
- FDM: 划分为下行和上行, 下行每个6MHz, 上行每个6.4MHz
  - (下行只有一个 CMTS-电缆调制解调器端接系统在发送, 不存在多路)
  - 类似TDM: 划分为序列微时隙
    - 请求帧微时隙: 可能碰撞, 使用随机接入
    - 数据帧微时隙: 收到请求后由CMTS通过下行信道分配给Modem, 不碰撞
      交换局域网
      链路层寻址和ARP
媒体访问控制 MAC地址
- 长度: 6字节
- 与适配器(NIC等)绑定
- 广播地址: 全1, 即12个F
- 每个主机都检查MAC是否与自己相同, 相同则接收
地址解析协议 ARP协议
- 子网内解析
- 每台主机或路由器存有ARP表, 保存了其知晓的MAC-IP对应关系, 每个条目有过期时间
- 流程
  - 若有表项, 直接构造包并发送
  - 若无, 向适配器发送ARP分组(发送和接收的IP地址, 目的MAC是广播地址)
  - 每个主机都收到, 若IP相同, 则响应ARP分组, 用标准链路层帧回复
发送数据报到子网以外
- 路由器每个端口均有MAC和IP
- 路由器将相应ARP, 主机获得的此IP的MAC地址是路由器这一端口的MAC
  以太网
以太网帧结构
- 帧字段
  - 前同步码: 8字节: 前7个字节都是10101010, 同步时钟并唤醒适配器; 最后一个是10101011, “11”警告适配器数据到来
  - 目的MAC地址: 6字节: 与自己的MAC相同才会接收
  - 源MAC地址: 6字节
  - 类型字段: 2字节: 允许以太网复用多种网络层协议
  - 数据: 46-1500: 承载IP数据报, 超长将分片
  - CRC: 4字节: 适配器丢弃校验出错的帧
- 无连接服务: 不事先握手
- 不可靠服务: 成功无ACK, 失败无REJ
以太网技术
- 命名: [速率]BASE[距离或介质], T指铜双绞线, FX/SX/BX指光纤
- 10Mbps: 10BASE[%d], 距离, 使用同轴电缆
- 100Mbps: 100BASE-TX/T4/T2双绞线, -FX/SX/BX光纤
- 1000Mbps: 1000BASE-T等, 又名802.3z, 双绞线, 兼容旧标准, 点对点(交换机)信道全双工, 另有广播(集线器)
- 10Gbps: 10GBASE-T
  链路层交换机
交换机转发和过滤
- 过滤: 决定帧应该发到某个接口还是将其丢弃
- 转发: 决定帧去往哪个接口
  - 流程: 借助交换机表(MAC - 接口 - 时间)
    - 没找到目的MAC, 向源以外的所有端口广播
    - 找到MAC, 与源端口匹配, 则丢弃
    - 找到MAC, 与另一端口匹配, 转发到这一端口(进入端口的缓存)
自学习
- 流程
  - 初始: 交换表为空
  - 学习: 收到帧, 则将[源MAC地址 - 到达的接口 - 当前时间]存入交换表
  - 老化: 一段时间后未收到这一地址作为源的帧, 则此表项移除
- 即插即用设备: 无需进行配置
- 双工: 每个接口可同时发送和接收
链路层交换机的性质
- 消除碰撞: 星型拓扑, 没有因碰撞而浪费的带宽
- 异质链路: 链路彼此隔离, 允许不同速率, 新旧混用
- 管理: 检测异常适配器并断开之, 等
交换机与路由器
- 交换机
  - 优: 即插即用, 分组过滤, 高速率
  - 缺: 拓扑限制为树形, 不提供广播风暴的保护
- 路由器
  - 优: 拓扑灵活, 提供防火墙保护
  - 缺: 需要配置, 处理延迟大
    虚拟局域网
树形交换局域网的缺陷
- 缺乏流量隔离: 单播能够隔离, 但广播不行; 缺乏安全隐私的隔离
- 交换机无效使用: 为了分组造成交换机端口的浪费
- 管理用户: 用户在分组间移动, 则需要改变物理布线, 连接到不同交换机
VLAN: 单一的物理交换机定义多个虚拟局域网, 广播流量仅到达同一分组的端口
- 跨VLAN需要路由器
- VLAN划分: 端口或 MAC
- VLAN干线连接
  - 干线接口: VLAN交换机之间交换帧
  - 帧格式802.1Q: 以太网帧的源地址和类型之间, 加入VLAN标志

Chapter 3. Packet Switching Networks

概述

转发和路由选择

转发: 分组到达输入链路, 路由器将其移动到适当的输出链路
- 转发表: 首部 - 输出链路, 根据第三层首部, 决定输出链路
路由选择: 网络层决定分组所采用的路由或路径
- 路由选择算法: 决定了首部对应的输出链路的值; 集中式/分布式; 人工配置/路由选择协议
- 路由器: 除链路层交换机以外的分组交换机
连接建立: 分组流动之前建立状态
网络服务模型
网络服务
- 确保交付: 确保到达目的地
- 有时延上界的确保交付: 在规定时间内到达
- 有序分组交付: 发送与接收的顺序相同
- 确保最小带宽
- 确保最大时延抖动: 相邻分组发送时的时间差与相邻分组接收时的时间差相差不超过特定值
- 安全性服务: 密钥加密
因特网: 尽力而为(没任何网络服务)
ATM: CBR(恒定比特率, 无丢包, 有序, 维护定时); ABR(可用比特率, 维护最小速率, 有序, 提供拥塞指示)
虚电路和数据报网络
虚电路网络
虚电路: 在网络层使用连接
组成
- 源和目的的路径
- VC号, 该路径每段链路的号码
- 路由转发表表项, [入接口 - 入VC - 出接口 - 出VC]
连接状态信息: 新连接添加表项, 断开连接删除表项
- 虚电路建立
  - 运输层联络网络层, 指定接收地址(信令报文-信令协议)
  - 网络层决定路径, 分配VC号, 添加表项, 预留资源
- 数据传送
- 虚电路拆除
  - 接收方或发送方通知网络层终止虚电路
  - 网络层通知另一端结束呼叫, 更新表项
    数据报网络
转发表: [前缀 - 链路接口]
- 最长前缀匹配规则
- 转发表的更新: 路由选择算法

路由器工作原理

输入端口
- 线路端接: 物理线路接入
- 数据链路处理: 协议, 拆封
- 查找转发排队: 查找转发表, 存帧排队
交换结构
- 经内存交换
- 经总线交换
- 经互连网络交换(纵横式)
输出端口: 排队, 数据链路处理, 线路端接
何处出现排队

<<< TODO >>>

运输层

多路复用和多路分解

套接字Socket: 应用层-网络层门户
- 具有唯一标识符
- 运输层报文开头的2个字段: 源端口号16bit : 目的端口号16bit
  - 周知端口号: 0~1023
    无连接的多路复用与多路分解
UDP套接字由二元组进行标识: 目的IP : 目的端口号
源端口号: 回复时使用
面向连接的多路复用与多路分解
TCP套接字由四元组进行标识: 源IP : 源端口号 : 目的IP : 目的端口号
不同来源的报文到达同一端口可区分, HTTP服务器
UDP: 无连接运输
仅提供复用分解, 差错检测
无连接: 发送报文段之前, 没有握手
优点: 首部短, 时间灵活, 无连接建立, 无连接状态
无拥塞控制, 可以由应用层构建可靠传输
报文段结构
| 源端口号 | 目的端口号 | 长度(首部+数据) | 检验和 | 应用数据(报文) |
|-|-|-|-|-|
| 16bit | 16bit | 16bit | 16bit | … |
- UDP变长数据段
- 检验和计算: UDP报文段 + IP首部的部分字段()
  UDP检验和
计算方法
- 报文段分为16bit字, 相加求和
- 最高位进位回卷, 加到最低位
- 取反码
检验方法: 接收方做前两步, 得到全1, 则没问题
能检测, 不能纠错, 端到端差错控制
可靠数据传输原理
可靠数据传输协议: (服务抽象)传输的比特不会受损或丢失, 并且按序到达
构造可靠传输协议
<!– + 经完全可靠信道的可靠数据传输: 废话
经具有比特差错的信道的可靠数据传输
- 三个功能: 差错检测, 接收方反馈, 重传
- 发送端: 2个状态
  - 等待上层调用
  - 等待接收方回复ACK/NAK
- 接收端: 1个状态: 等待上层调用, –>

面向连接的运输: TCP

提供差错检测, 重传, 累积确认, 定时器, 序号和确认号的首部字段
全双工
TCP连接
三次握手
- 客户发送
- 服务端发送
- 客户发送
MSS最大报文段长度(其实是应用层数据的最大长度): 根据 MTU(链路层)最大传输单元确定, 典型值1460字节

TCP报文段结构
| 源端口号 | 目的端口号 | 序号 | 确认号 | (第一堆) | 接收窗口 | 因特网校验和-紧急数据指针 | 选项 | 数据 |
|-|-|-|-|-|-|-|-|-|
| 16bit | 16bit | 32bit | 32bit | 16bit | 16bit | 16bit+16bit | 0bit+ | … |
第一堆里面有: 首部长度4bit(以字为单位, 1=4字节) + 保留未用6bit + (URG ACK PSHRST SYN FIN)标志字段6bit
SYN FIN RST 用于连接建立和拆除, PSH代表必须立即将数据交给上层, URG与紧急数据指表示指向位置是紧急数据的最后一个字节, 需要通知上层
序号和确认号
- 序号: 是该报文段的首字节的字节流编号
  
  单纯的ACK不包含数据字节, 因此不引发编号增加
- 确认号: 表示这一序号之前的字节均被正确接收, 它和其后的未接收
  
  一个报文可以同时有确认号和序号, 是捎带ACK
  
  往返时间的估计与超时
估计往返时间
- SampleRTT: 某一报文被发出(交给IP)到其确认被接收的时间量(一个来回)
  
  重传的报文不进行测量
- EstimatedRTT: 初始为第一个测得的SampleRTT, 之后根据下式更新
  $$\textrm{EstimatedRTT} = (1-\alpha)\cdot\textrm{EstimatedRTT} + \alpha \cdot \textrm{SampleRTT}$$
  
  指数移动加权平均
- DevRTT: RTT的偏差, 是Sample和Estimated的差的绝对值, 也用指数移动加权平均
  $$\textrm{DevRTT} = (1-\beta)\cdot\textrm{DevRTT} + \beta \cdot |\textrm{SampleRTT}-\textrm{EstimatedRTT}|$$
设置和管理重传超时间隔
- 重传间隔
  - 默认初始值为1s
  - 超时后, 设为先前值的2倍
  - 若有新的EstimatedRTT, 立刻据下式更新
    $$\textrm{TimeInterval} = \textrm{EstimatedRTT} + 4\cdot \textrm{DevRTT}$$

可靠数据传输

累积ACK
- ACK中的数字, 表示其之前的字节均被接收
重传
- 规则: 一个报文到达重传间隔, 仍未收到ACK(ACK>SEQ+LEN), 则重传
- 超时间隔加倍: 重传过后, 下一次的定时将会加倍;
- 推算超时间隔: 若收到ACK或得到上层应用数据, 则又改为使用$\textrm{TimeInterval}$计算
快速重传
- ACK生成策略
  - 延迟ACK: 某一报文到达, 等待500ms, 若下一个按序报文没到, 发这一报文ACK
  - 立刻发送累积ACK: 一个按序报文到了, 前一个在等待发ACK, 发累积ACK, ACK后一个报文
  - 冗余ACK: 到达一个报文, 其序号大于期望的序号, 立刻发送冗余ACK, 其序号为期望序号
  - 收到的报文填补空缺, 且起始于空缺的低端, 则立刻发ACK
- 收到3个冗余ACK, 则进行快速重传, 假定被ACK的报文后的报文全部丢失
回退N步还是选择重传
- 第n个报文重传, 若之后的报文被缓存, 且其ACK及时到达, 那么后续可以不用重传
  
  这意味着TCP不是单纯的GBN, 而含有一部分SN
  
  流量控制
接收窗口
- 接收方跟踪
  - 应用读取的最后一个字节的编号: LastByteRead
  - 接收到的最后一个字节的编号: LastByteRcvd
  - 接收缓存大小: RcvBuffer
  - 接收窗口大小: rwnd = RcvBuffer-(LastByteRcvd-LastByteRead)
    
    也就是缓存余量
  - 接收方将rwnd放入发给发送方的报文中
- 发送方跟踪
  - 发送的最后一个字节的编号: LastByteSent
  - 被确认的最后一个字节的编号: LastByteAcked
  - 从接收到的报文中得到的rwnd
  - 需要始终保证 LastByteSent - LastByteAcked <= rwnd
  - 若出现rwnd=0, 则需要继续发送含有一字节数据的报文
    
    为了防止接收方无数据要发, 引发发送端阻塞. 这个一字节的报文总会被ACK, 有机会获得一个非0的rwnd值
    
    TCP连接管理
建立: 三次握手

| 通信 | SYN | ACK | SEQ | 操作 |
|-|-|-|-|-|
| 客户->服务 | + | | client_isn | 客户端随机选择起始序号 |
| 服务->客户 | | client_isn+1 | server_isn | 服务器分配资源, 随机选择起始序号 |
| 客户->服务 | | server_isn+1 | client_isn+1 | 客户端分配资源 |
终止(以客户终止为例)
- 客户发送FIN(设置首部FIN标志位1)
- 服务器ACK这个FIN
- 服务器发送FIN, 并立刻关闭, 释放资源
- 客户端ACK这个FIN, 定时等待之后关闭, 释放资源
防范SYN洪泛攻击
- 第一步的isn使用散列函数, 用源地址, 目的地址和端口号, 和一个只有服务器知道的散列函数
- 第二步不分配资源
- 第三步根据ACK里面的seq, 可以验证这个ACK是由先前的某个SYN生成的, 于是分配资源建立连接
拒绝通信
- 发送RST(RST标志位1)

拥塞控制原理

一堆废话, 我只关心TCP

TCP拥塞控制

拥塞窗口cwnd
- 对发送进行限制: LastByteSent - LastByteAcked <= min(rwnd, cwnd)
窗口与速率的关系: B = S(发出的包数量)/RTT(往返时间)
TCP拥塞控制算法
- 慢启动
  - 初始: cwnd = 1 (MSS)
  - 加倍: 每一轮, cwnd加倍
  - 结束
    - 超时, 取cwnd = 1, ssthresh = cwnd/2
    - 到达ssthresh, 进入拥塞避免模式
    - 3个冗余ACK, cwnd = cwnd/2+3, 进入快速恢复
- 拥塞避免
  - 线性增加: 每一轮, cwnd+1
  - 结束
    - 超时, 取cwnd = 1, ssthresh = cwnd/2, 相当于慢启动
    - 3个冗余ACK, cwnd = cwnd/2+3, 进入快速恢复
- 快速恢复
  - 接下来收到的冗余ACK, cwnd都加1(之前的3个冗余ACK已经加过3, 至少加3)
  - 结束: 收到期待的ACK, 将cwnd设置为ssthresh, 进入拥塞避免
- TCP拥塞控制: 回顾
  - TCP Tahoe: 没有快速恢复, 3个ACK也进入慢启动
  - TCP Reno: 上文的方案

公平性

TCP AIMD
- 相同的RTT: 公平, 最终会达到平均分配带宽
- RTT不同: RTT小的更快扩大窗口, 将得到更多带宽, 最终似乎与RTT成反比
UDP参与
- UDP没有公平可言, 抢占资源
- UDP将挤压TCP资源
并行TCP
- 一个应用使用多个TCP连接, 就获得了多倍其应得的带宽
  网络辅助拥塞控制
- IP首部设置ECN(2比特, 4状态), 送到接收主机
- 接受主机在TCP ACK中设置ECE, 发到发送主机
- 发送主机减半cwnd, 并在下一个报文头中设置CWD, 发到接收主机

Chapter 4. Internetworking

[Textbook] 4.3, 5.3, 5.4, 5.5, 5.6

Chapter 5. End-to-End Protocols

[Textbook] 3.1, 3.2, 3.3, 3.4, 3.5, 9.x

Chapter 6. Congestion Control and QoS

[Textbook] 3.6, 3.7

Chapter 7. Network Security

[Textbook] 8.x

Chapter 8. Internet Applications

[Textbook] 2.x

CN-ALL

Chapter 1: Introduction of Networking

What’s the Internet

Building Internet

Internet History

Access Internet

Network Edge

Access Networks

Network Core

Typical Network Applications

Client-Server Architecture

P2P Application

Protocol Layers and Service Model

OSI

TCP/IP Protocol Architecture

Network Programming

Socket Programming with TCP

Socket Programming with UDP

Delay, Loss and Throughput

Delay

Loss

Throughput

Networks under Attack: Security

Different Types of Malware

Types of Attack

Catch-Up

Chapter 2. Direct Link Networks

链路层概述

链路层服务

链路层实现

差错检测和纠正技术

奇偶校验

检验和 方法

循环冗余检测

流量控制

停止等待流量控制

滑动窗口流量控制

多路访问链路和协议

信道划分协议

随机接入协议

轮流协议

用于电缆因特网接入的链路层协议

交换局域网

链路层寻址和ARP

以太网

链路层交换机

虚拟局域网

Chapter 3. Packet Switching Networks

概述

转发和路由选择

网络服务模型

虚电路和数据报网络

虚电路网络

数据报网络

路由器工作原理

运输层

多路复用和多路分解

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

面向连接的多路复用与多路分解

UDP: 无连接运输

报文段结构

UDP检验和

可靠数据传输原理

构造可靠传输协议

面向连接的运输: TCP

TCP连接

TCP报文段结构

往返时间的估计与超时

可靠数据传输

流量控制

TCP连接管理

拥塞控制原理

TCP拥塞控制

公平性

网络辅助拥塞控制

Chapter 4. Internetworking

Chapter 5. End-to-End Protocols

Chapter 6. Congestion Control and QoS

Chapter 7. Network Security

Chapter 8. Internet Applications

检验和方法