计算机网络
第一章 计算机网络和因特网
* 基本概念
* 类似人类协议：由某些设备的硬件或软件执行。
* 因特网中的所有活动，都受协议制约。例如，网卡中 的协议、端系统中的拥塞控制协议等等。
* 因特网的运行离不开协议
* 三要素
* 语法：即数据与控制信息的结构或格式。
* 语义：即需要发出何种控制信息，完成何种动作以及做出何种响应。
* 时序（同步），即事件实现顺序的详细说明。
网络接入方式
家庭（企业）接入
- 数字用户线技术DSL：电话线，拨号上网，使用频分复用技术FDM
- 混合光纤同轴电缆HFC：电视线，使用频分复用技术FDM
- 光纤到户技术FTTH
- 卫星链路接入
- WIFI：802.11协议
广域接入
- 3G
- 4G
- LTE
分组交换
分组交换：主机将应用层 消息(messages)分割为若干分组(packets）
- 排队(queuing)和丢包(loss): 如果在一段时间内，分组到达链路速率超过了链路的传输速率：分组将排队，在输出链路上等待传输； 如果缓存溢出，则会出现丢包。
- 每个分组以链路的最大传输速率传输
报文交换：电报知道伐
- 数据交换结点需要经历存储、转发这个过程，所以会引起转发时延。
电路交换：预留端系统之间通信路径上所需要 的资源 (缓存，链路带宽)，建立连接。
- 发送方以恒定速率向接收方传送数据。如，电话网络。
- TDM时分多路复用
- FDM频分多路复用
- CDM码分多路复用
- 效率较低 ，静默期（无数据传输）专用电路空闲，网络资源被浪费
- 创建端到端电路及预留端到端带宽的过程复杂
四种时延
节点处理时延dproc
- 检测比特错误
- 确定输出链路
- 通常时延小于毫秒级别
排队时延dqueue
- 在输出端口等待传输的时间
- 依赖于路由器的拥塞等级
传输时延dtrans
- 路由器到线路信号转换的延时，题目给的那个mb/s那个，带宽。
传播时延dprop
- 线路传输延时，和距离有关。
协议模型
- 每层可以使用相邻下一层提供的服务
第N层只能调用第N-1层提供的数据发送服务，而不 能调用N-2层提供的服务，第N-1层不能调用第N层提供的服务 。
* OSI七层模型
| 层 | 功能 | 协议 |
|---|---|---|
| 应用层 | 文件传输，电子邮件，文件服务，虚拟终端 | TFTP，HTTP，SNMP，FTP，SMTP，DNS，Telnet |
| 表示层 | 数据格式化，代码转换，数据加密 | 没有协议 |
| 会话层 | 解除或建立与别的接点的联系 | 没有协议 |
| 传输层 | 提供端对端的接口 | TCP，UDP |
| 网络层 | 为数据包选择路由 | IP，ICMP，RIP，OSPF，BGP，IGMP |
| 数据链路层 | 传输有地址的帧以及错误检测功能 | SLIP，CSLIP，PPP，ARP，RARP，MTU |
| 物理层 | 以二进制数据形式在物理媒体上传输数据 | ISO2110，IEEE802，IEEE802.2 |
<table>
- 恶意代码
- 间谍软件
- DOS/DDOS
- 分组嗅探
- IP哄骗
第二章 应用层
2.1 应用层协议原理
两种体系结构
client-server(C/S, B/S)
peer-to-peer (P2P)
TCP
发送和接收过程之间的可靠传输
流量控制:发送方不会淹没接收方
拥塞控制:节流阀发送时，网络超载
不提供:定时、最低吞吐量保证、安全性
面向连接:客户机和服务器进程之间需要设置
http、smtp、ftp
UDP
发送和接收过程之间不可靠的数据传输
不提供:可靠性、流量控制、拥塞控制、时间、吞吐量保证、安全性或连接设置
dns
应用层协议
消息语法 ：消息中字段的划分，以及有哪些字段
消息语义：每个字段信息的含义
规则：规定进程在什么时候以及如何发送&响应消息
2.2 Web和HTTP
HTTP：超文本传输协议
80端口
C/S架构
TCP协议
持续/非持续
流水线/非流水线方式（持续）
流水节约RTT时延
- 一次TCP就要2个RTT，非持续几个文件就几个*2
RTT (definition): time for a small packet to travel from client to server and back- HTTP报文格式
cookie
用户识别
状态跟踪
商品推荐
安全/隐私问题
WEB缓存
工作原理：浏览器发送所有的HTTP请求给cache(缓存服务器)
如果请求对象存在于缓存服务器：缓存服务器直接返回对象给客户
如果请求对象不在缓存服务器中，则缓存服务器向原始服务器请求，然后返回对象给客户
条件get
发送包含上次更新的时间
如果没有发生修改，则返回一个空数据的响应报文 (304)
如果发生了修改，则返回一个最新的数据
2.3 因特网中的电子邮件
SMTP, POP3, IMAP
C/S
TCP
2.4 DNS：因特网的目录服务
分布式数据库
53端口
UDP协议
DNS的作用
- 主机名到IP地址的转换
- 主机别名查询 (host aliasing)
- 规范名, 别名
- 邮件服务器的别名
- 负载均衡
层次结构
- 根服务器（ROOT）：主要维护的是顶级域名服务器的IP地址
- 顶级域服务器（TLD）：维护顶级域名的IP地址，顶级域名：com、org、net、edu、gov、jp、ca、cn
- 权威DNS服务器：由组织机构维护的自己提供的服务器的域名到IP地址映射的DNS服务器。例如我们学校的 Web服务器和电子邮件服务器的域名和IP地址的映射由我们学校自己的权威DNS服务器维护。
- 本地DNS服务器（默认DNS服务器 ）：本地域名服务器如果无法解析，会向根域名服务器发起请求 ，并不严格属于层次化结构 。
DNS查询
- 迭代
- 递归
2.5 P2P文件分发
P2P文件分享的特点
- 直接在对等方间传输：所有内容不经过第三方服务器
- 高度的可扩展能力：利用众多对等方集合中的资源去分发内容
- 使用客户机/服务器模式：请求的对等方是客户机，被选中的对等方是服务器
- 服务器对等方使用文件传输协议向客户机对等方传送。
- 通过传送“HTTP请求”和“HTTP响应”报文进行。
- 所有的对等方必须既能运行文件传输协议的客户机端程序，又能运行服务器端程序。
- 对等方既是一个客户机，又是一个瞬时Web服务器。
资源定位
集中式目录
查询洪泛：“查询报文”在网络中产生很大的流量。
利用不均匀：设立组长，组员，综合使用洪范和集中式目录的思想。
2.6 套接字编程：生成网络应用
UDP套接字编程的示例
UDPClient
from socket import *
serverName = ‘localhost’
serverPort = 12000
clientSocket = socket(AF_INET, SOCK_DGRAM)
message = raw_input(’Input lowercase sentence:’)
clientSocket.sendto(message,(serverName, serverPort))
modifiedMessage, serverAddress = clientSocket.recvfrom(2048)
print modifiedMessage
clientSocket.close()
UDPServer
from socket import *
serverPort = 12000
serverSocket = socket(AF_INET, SOCK_DGRAM)
serverSocket.bind(('', serverPort))
print “The server is ready to receive”
while 1:
message, clientAddress = serverSocket.recvfrom(2048)
modifiedMessage = message.upper()
serverSocket.sendto(modifiedMessage, clientAddress)
TCP套接字编程的示例
TCPClient
from socket import *
serverName = ’servername’
serverPort = 12000
clientSocket = socket(AF_INET, SOCK_STREAM)
clientSocket.connect((serverName,serverPort))
sentence = raw_input(‘Input lowercase sentence:’)
clientSocket.send(sentence)
modifiedSentence = clientSocket.recv(1024)
print ‘From Server:’,modifiedSentence
clientSocket.close() Python
TCPServer
from socket import *
serverPort = 12000
serverSocket = socket(AF_INET,SOCK_STREAM)
serverSocket.bind((‘’,serverPort))
serverSocket.listen(1)
print ‘The server is ready to receive’
while 1:
connectionSocket, addr = serverSocket.accept()
sentence = connectionSocket.recv(1024)
capitalizedSentence = sentence.upper()
connectionSocket.send(capitalizedSentence)
connectionSocket.close()
第三章 运输层
3.1 运输层服务
可靠的、按序的交付 (TCP)
- 拥塞控制
- 流量控制
- 连接建立
不可靠、不按序交付: UDP
- “尽力而为”
- 不提供不必要服务的扩展
不可用的服务:
时延保证
带宽保证
3.2 多路复用与多路分解
UDP：目的ip和端口号
TCP：源ip和端口号、目的ip和端口号
3.3 无连接传输: UDP
UDP段可能：丢包，对应用程序交付失序
UDP报文段结构
- 源端口号和目的端口号（32bit）
- UDP长度：UDP报文的字节长度（包括首部和数据）。（16bit）
- UDP校验和: 检验UDP首部和数据部分的正确性。（16bit）
- 数据内容
校验和计算
1.按位相加
2.进位回卷
3.取反
3.4 可靠数据传输原理
rdt1
无比特差错
无分组丢失
rdt2
有比特差错
无分组丢失
rdt2.0
怎么检测到比特错误：检验和机制(checksum)
检测到错误后的处理方法：由接收方通知发送方重传
ACK：显式的告诉发送人成功收到了分组
NAK：接收人显式告诉发送人分组出错
当收到NAK报文 时，发送人重传出错的分组
缺陷
如果ACK/NAK受损，将会出现何种情况？
不能只是重传：可能导致冗余(接收方不知道是否重复)
rdt2.1
处理冗余:
发送方对每个分组增加序列号
如果ACK/NAK受损，发送方重传当前的分组
接收方丢弃(不再向上交付)冗余分组
rdt2.2
与rdt2.1一样的功能，仅使用ACK
代替NAK，接收方对最后正确接收的分组发送ACK
接收方必须明确地包括被确认分组的序号
在发送方冗余的ACK导致如同NAK相同的动作：重传当前分组
rdt3
有比特差错
有分组丢失
倒计时定时器
流水线协议
GBN：Go-Back-N
选择性重传： S-R
GBN改善了信道效率，但仍然有不必要重传问 题，为此进一步提出了SR机制
SR接收方分别确认所有正确接收的报文段
- 需要缓存分组，以便最后按序交付给给上层
SR发送方只需要重传没有收到ACK的分组
- 发送方定时器对每个没有确认的分组计时
SR发送窗口
- N个连续的序号
- 也需要限制已发送但尚未应答分组的序号
3.5 面向连接的传输: TCP
流量控制
连接管理
- 三次握手
1.客户机向服务器发送 TCP SYN报文段2.服务器收到SYN报文段, 用SYNACK报文段回复3.客户机接收到 SYNACK, 用ACK报文段回复,可能包含数据
* 关闭连接
1.客户机向服务器发送TCP FIN控制报文段2.服务器收到FIN，用ACK回答。关闭连接，发送FIN3.客户机收到FIN, 用ACK回答
4.服务器接收ACK，连接关闭
3.6 TCP拥塞控制
慢启动
TCP连接开始时，cwnd的值通常初始置为一个MSS的较小值，这就使得初始发送速率大约为 MSS/RTT；之后，每收到一个报文段的首次被确认cwnd就增加一个MSS。这样，第一个RTT中，cwnd为1 MSS， 第二个RTT中，cwnd为2 MSS， 第三个RTT中，cwnd为4 MSS， 即每个RTT之后，cwnd就翻倍，cwnd呈指数增长。当发生丢包时，设置一个变量 ssthresh（慢启动阈值） = cwnd / 2, 然后cwnd重新设为1。
拥塞避免当出现丢包时，如果（可能会直接进入快速恢复）进入慢启动阶段，ssthresh设为 cwnd/2, cwnd值置为1，然后每个RTT cwnd翻倍，当cwnd值到达 ssthresh之后，进入拥塞避免阶段。此时，每个RTT，cwnd值只增加1个MSS，即每收到一个报文的ACK，cwnd = cwnd + MSS/cwnd.直到再次出现丢包后。当出现超时类型的丢包时，进入慢启动阶段（ssthresh = cwnd/2, cwnd=1）；当出现三次冗余ACK类型的丢包时，进入快速恢复阶段（ssthresh = cwnd/2, cwnd = ssthreash + 3MSS)
快速恢复当出现三次冗余ACK类型的丢包时，进入快速恢复阶段。此时 ssthresh = cwnd/2, cwnd = ssthreash + 3MSS，之后每个RTT内，cwnd增加1个MSS，直到出现丢包。
第四章 网络层：数据平面
4.1 网络层概述
网络层功能
转发(forwarding)：将分组 (packet)从路由器的输入端口转移到输出端口
路由(routing)：确定分组从发送方到接收方的路由(route)
4.2 路由器工作原理
路由器的两个核心功能
- 运行路由算法/协议(RIP, OSPF, BGP)
- 将分组从路由器的输入链路传送到正确的输出链路
最长前缀匹配规则
4.3 IP
ipv4报文格式
IP分片
IP地址
子网划分
IP地址所在网段的首位和末尾分别是网段地址和广播地址，不能使用。
IPV4寻址
DHCP
NAT
第五章 网络层：控制平面
路由算法
LS算法
确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后，它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息，其中包含它自身的IP地址。
测量相邻路由器的延时（或者其他重要的网络参数，比如平均流量）。为做到这一点，路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2，路由器便可以计算出延时。（路程往返时间是网络当前延迟的量度，通过一个分组数据包从远程主机返回的时间来测量。）该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。
向网络中的其他路由器广播自己的信息，同时也接收其他路由器的信息。 在这一步中，所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样，每一个路由器都能够知道网络的结构以及状态。
使用一个合适的算法，确定网络中两个节点之间的最佳路由。 在这一步中，路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点，如Dijkstra最短路径算法。在这个算法中，一个路由器通过收集到的其他路由器的信息，建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注，称为权值或成本。这个数字是延时和平均流量的函数，有时它仅仅表示节点间的跃点数。例如，如果一个节点与目的地之间有两条链路，路由器将选择权值最低的链路。
DV算法
- 路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i, j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。
- 路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：前序字段——表示当前节点之前的节点。长度字段——表示从源节点到当前节点的权值之和。标号字段——表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。
- 路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。
- 路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。
- 路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。
- 路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。
- 如果这个节点不是V2（目的节点），路由器则返回到步骤5。
- 如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。
路由协议
- OSPF
OSPF的简单说就是两个相邻的路由器通过发报文的形式成为邻居关系，邻居再相互发送链路状态信息形成邻接关系，之后各自根据最短路径算法算出路由，放在OSPF路由表，OSPF路由与其他路由比较后优的加入全局路由表。
第六章 链路层和局域网
6.1 链路层概述
链路层提供的服务
- 封装成帧，链路接入(framing, link access):
- 封装数据报为数据帧，增加头部，尾部信息
- 如果是共享链路，接入链路
- 在数据帧头部中，用MAC地址来标识源目的MAC地址
- 在相邻节点之间可靠传输数据帧
- 在比特错误率很低的链路(光纤、双绞线)很少使用
- 无线链路：高比特错误率
- 流量控制(flow control)
- 差错检查(error detection)
- 错误纠正(error correction)
- 接收方标识和纠正比特错误，而不需要请求重传
- 半双工和全双工(half-duplex and full-duplex)
- 在半双工模式，链路的两个节点都可以发送数据，但 是不能同时发送
以太网提供的服务
6.2 差错检测和纠正技术
循环冗余检测CRC
即多项式编码，把要发送的比特串看作为系数是0或1的一个多项式，对比特串的操作看作为多项式运算。
奇偶检验（1的个数）
checksum
6.3多路访问控制协议
广播链路，如wifi，集线器
点到点链路：不存在冲突
信道划分：TDMA、FDMA、CDMA
随机访问：ALOHA、CSMA 、CSMA/CD、CSMA/CA
轮流：轮询、令牌传递
6.4 链路层寻址
MAC地址（LAN地址、物理地址）
- 节点“网卡”本身所带的地址（唯一）。
- MAC地址长度通常为6字节(48比特)，共248个。
- 4字节地址用16进制表示，每个字节表示为一对16进制数
- 网卡的MAC地址是永久的（生产时固化在其ROM里）
ARP: 地址解析协议
交换机工作原理
VLAN
- 按照端口号划分
- 按照MAC地址划分
- 按照网络层地址划分(IPv4)