计算机网络期末复习

发表于 更新于 分类于

期末复习。

Chapter 1 概述

网络边缘

  • host
  • server

接入方式

  • DSL：网络、电话线共用一条线，各用户独立用各自的线
  • 电缆：各用户分享同一根线

传输

  • transmission delay：数据包长度（比特）/传输速率，输入速率>发送速率时数据包排队
  • propagation delay：传输距离（物理）/介质中传输速率

连接方式

主要在路由器之间体现：

  • 电路交换：路由器彼此之间有多条预留专线，不共享
  • 包交换（packet-switching）：路由器共享信道带宽

ISP 网络服务提供者

  • 端系统（网络边缘/子网）需要接入ISP才能接入互联网。
  • ISP互联：所有ISP通过中间一些路由器进行互联，起到降低连接复杂度的目的，避免每个ISP与其他所有都需要直接连接

延时

（收到包后立刻）处理延时、在发送队列中等待延时、传输延时、传播延时。

$$
d = d_{proc} + d_{queue} + d_{trans} + d_{prop}
$$

队列等候延时随流量强度指数增长。

互联网协议栈

五层结构，只学习四层（无物理层）。

层 处理数据类型
应用层 message
传输层 segment
网络层 datagram
传输层 frame

逐层向下封装更多报头，数据变长。

Chapter 2 应用层

Socket

属于应用层，面向传输层的接口，将应用层message转换为传输层segment，用于网络位置不同的进程间通信。

应用层应用的标识：IP地址+端口号，IP地址表示网络位置，端口号表示进程。

客户端-服务器架构

HTTP

  • 使用client-server架构
  • 传输层使用TCP连接，端口80

HTTP 请求：

  • 类型：GET，POST，…
  • header

HTTP 响应：

  • 状态行：HTTP协议号、连接状态
  • header
  • 请求的数据

Cookies：
保存状态，client首次向某服务器发送HTTP请求的时候，服务器创建cookie信息并随着HTTP响应返回给client，client本地保存cookie信息，下次请求同一个服务器的时候将携带cookie信息

Web cache、代理服务器：
避免client与server进行直接通信。cache存储在代理服务器上，client请求origin server的时候，先请求cache所在代理服务器，若有缓存则直接返回数据；否则，代理服务器请求origin server，然后响应再返回给client。

SMTP

用于电子邮件发送。

组成：

  • user agent：用户设备，向mail server发请求
  • mail server：存储邮件，使用SMTP协议发送邮件

先建立TCP连接，再发送信息，可靠传输。

user agent和自己的mail server之间可以用HTTP或SMTP协议，mail server彼此间只能用SMTP协议。

DNS

域名解析，实现域名到IP地址的转换。分布式、层次化结构。

  • 顶级域名解析服务器（TLD）：解析.com, .org, .net, .uk, .jp, …等顶级域名的服务器
  • 权威DNS服务器：特定组织提供其特定域名的IP解析
  • 本地DNS服务器：存储了域名-IP地址翻译对（可能过期），加速解析过程，一般优先访问

问询方式：

  • iterated：优先问询local DNS，然后依次问询root DNS，TLD DNS，权威DNS，每一步都返回结果到local DNS
  • recursive：优先问询local DNS，然后问询root DNS，再由root DNS问询TLD DNS，…每次向下一级DNS服务器问询，直到最后得到IP地址再递归返回

DNS记录（RR）：

  • name：域名
  • value：对应IP
  • type：解析类型，指定value的值
  • ttl：记录缓存时间
type种类 对应value类型
A IP地址
CNAME 正式域名
NS 权威DNS解析服务器域名
MX 域名对应的邮件服务器域名

P2P架构

BT

将文件分成多个chunks，参加BT下载的各用户之间互相传输chunks。

组成：

  • tracker：追踪torrent中每个用户的行为，管理新加入的用户
  • torrent：记录了参加chunks传输的用户组

传输机制：
请求：

  • rarest-first：每个用户优先请求自己缺少的，其他人拥有最少的chunk

发送：

  • tit-for-tat：每10s，对接收速率排序，选择最快的4个用户发送chunk
  • randomly-select：每30s，随机选一个用户发送chunk

CDN 内容分布网络

提供了流媒体存储、服务的解决方案。

流媒体被切分成小块，以不同码率编码存储，复制存储于多台物理位置不同的CDN服务器上。用户请求流媒体URL，由DNS直接解析到CDN的IP地址，请求CDN服务器，返回流媒体。流媒体传输中时刻检测网络状况，实时选择当前网络状况下最好质量编码的流媒体块进行传输（DASH）。

Chapter 3 传输层

实现两个进程之间逻辑通信，将应用层message封装成segment。
Internet两种传输层协议：

  • TCP：可靠传输
  • UDP：不可靠传输

复用&解复用

复用从多个socket得到多个message，封装成多个segment然后发送；解复用将收到的多个segment根据header内容解封装后分配到对应的socket（根据IP地址和端口号，端口号对应进程，IP地址对应host）。

UDP解复用只通过源端口号和目的端口号确定segment被送到的socket。
TCP解复用通过源IP，目的IP，源端口号，目的端口号确定segment被送到的socket，允许一个端口同时接收多个来源的segment。

UDP

segment结构：

  • 32 bits每行
  • 源端口号，目标端口号
  • UDP包长度，checksum
  • 应用层message

checksum
发送方将segment每16bit分为一组二进制数，所有组相加（尾部进位）后取反填入checksum（初始checksum视为0），接收方同样方法计算（包括checksum的值）但相加后不取反，如果求和每位都是1说明没有出错。

可靠性传输

重要思想：使用ACK、序号、计时器进行接收状态确认。

pipelined protocols：允许多个数据包串行进行可靠传输，提高信道利用率。
两种基本pipelined protocols：

  • GBN：go-back-n
  • SR：selective repeat

GBN：

  • 发送方有窗口
  • cumulative计时器
  • GBN每次因超时重新发送的都是整个窗口内的包，接收方回复当前已收到的最大有序包序号
  • 发送方接收到一个有序ACK，窗口移动一下，计时器重新为当前最老的包计时
  • GBN的窗口是逐个数据包位移动的

SR：

  • 收发都有窗口
  • 只重传没有接收到ACK的数据包
  • 接收方缓存失序的包
  • 每个包有自己的计时器
  • 收到什么包就回复什么包的ACK
  • 接收方向上层传递所有接收到的有序包，并移动接收窗口

TCP：

  • 双工，同时传seq num和ACK
  • timeout时间确定：大于RTT，RTT需要估计
  • 结合GBN和SR
    • 用一个计时器记录最老的包，timeout重发整个发送窗口内所有的包（GBN性质）
    • 接收方缓存收到乱序的包
  • ACK为接收方需要的下一个seq num
  • 快重传：连续收到3个相同ACK之后，第4次接收到同样的ACK时立刻发送该包（timeout前就完成了重传，更快）

流控

接收方有buffer，其中free buffer的大小成为rwnd，接收方回复ACK时带有rwnd信息，从而发送方可确定发送窗口大小以至于不会使接收方overflow。

三次握手

建立：

  1. client发送SYN=1的请求
  2. server回复SYN=1的ACK
  3. client回复ACK，此时可携带数据，连接建立

断开：

  1. client发送FIN=1请求
  2. server回复ACK，此时还能携带数据
  3. server发送FIN=1，断开连接，此时不再携带数据

拥塞控制

根据超时、重复ACK情况自动控制发送窗口的大小。

  • 原则：加性增长，乘性衰减。
  • 发送方：接收到连续ACK就将cwnd（发送窗口）size+1，检测到丢包就减半。
  • MSS：一个数据包在cwnd中占位。

slow start：

  • 每次收到一个有序ACK，cwnd size+1，一个RTT下来翻倍
  • 若timeout，阈值减半，size设为1，开始新的slow start至阈值后线性增长
  • 若3次重复ACK，阈值减半，size减半然后线性增长
  • 阈值初始值为初始cwnd size一半

阈值为指数增长和线性增长的分界点。

ECN 显式拥塞提示

发送方发送报文，IP数据包中2 bit ECN位记录网络的拥堵情况，ECN由路由器填写；接收方得到报文后根据ECN位决定返回的ACK中ECE位是否为1，若为1说明有拥堵。

Chapter 4 网络层：数据平面

网络层为路由器之间的通信协议，格式为IP datagram。

网络层功能：

  • 转发：路由器确定输入datagram从哪个口送出
  • 路由：确定从发送地到目的地的路径

路由器架构

  • 输入、输出缓存
  • 交换核心：memory，bus，crossbar
  • 转发表：最长前缀匹配

输入队列在核心处理速度低时暂时缓存输入数据，但是会造成HOL阻塞问题，多个输入队列数据同时传向一个输出端口，导致碰撞。

解决HOL：输出队列。输出队列提供了缓存，发生碰撞的数据包可以缓存在队列中等待输出。

输出队列调度：

  • 优先：根据数据包优先级将数据包缓存到不同的输出队列中，只要高优先级队列不空，优先输出高优先级队列中的包
  • 轮询：循环扫描每个队列，每个队列发送一个包；也可分配权重，循环中重点发送某个队列

IP协议

  • 一行32 bit
  • TCP头20 byte，IP头20 byte

IP包分割：
链路有MTU限制，因此要将整个IP包分割成小包发送，在目的地重组。
分割标准：

  • 只对有效数据进行切割
  • length：包长度，上限为MTU，一般为1500，包括20byte包头，因此有效数据长度为1480
  • offset：相对于原大数据包有效数据起始位的偏移量，为偏移字节数除以8
  • flag：表示当前包是否为切分的小数据包

DHCP

获取IP地址的协议。

流程：

  1. client向广播地址255.255.255.255发送DHCP请求
  2. DHCP服务器接收请求，返回IP地址
  3. client接收IP地址，确认接收IP地址
  4. DHCP服务器回复确认接收IP地址

全程在广播地址上进行通信。

NAT 网络地址转换

子网内部可以自行分配地址，节约了IP地址的使用。

与外网有映射关系：

  • 子网内新IP对应外网相同IP不同端口号
  • 在网关处进行地址转换

IPv6

出现原因：IPv4地址将耗尽、加速处理/转发

特点：

  • 固定40byte包头
  • 不进行包切割
  • 去掉checksum

隧道：IPv6包遇到只能处理IPv4的路由器时外部包装一层IPv4头。

Chapter 5 网络层：控制平面

路由协议

link state：
路由网络拓扑关系已知，全局算法。用Dijkstra。

多轮迭代，第一轮计算起点到所有其他点的距离，以及到这些点前一个点是什么，然后挑出距离最短的点加入队列，接下来反复计算队列内的点距哪个点最近（从起点出发），重复将每一轮最近的点加入队列，直到全部点都加入队列，反向遍历加入点的顺序就是最短路径。

distance vector：
分布式算法，基于Bellman-Ford Equation：

$$
d_x(y) = \min_v{c(x,v)+d_v(y)}
$$

distance vector表示当前点到目标点的最短距离。

每个路由器存储自身转发到每个邻居的cost，以及邻居的distance vector，如果连接状态改变，相邻的路由器彼此发送自己到终点的新距离估计，并用Bellman方程进行distance vector的更新。

自治系统

地址太多，路由表过于庞大，不适合频繁转发交换，因此提出自治系统（AS），整个网络划分为多个AS，每个AS内只控制自己的路由。

两种路由：

  • intra-AS：一个AS内部的路由，协议必须一致
  • inter-AS：不同AS之间的路由

OSPF：一个intra-AS路由协议实例，在一个AS内使用link state路由方式，每个路由器存储整个AS的拓扑表。

BGP：一个inter-AS路由协议实例，有两部分

  • eBGP：从相邻AS收集可达性信息
  • iBGP：将可达性在整个AS内传播

BGP传播两个重要属性：

  • AS-PATH：到目的地经过的每个AS
  • NEXT-HOP：通知AS内路由器下一个AS是哪里

gateway router在收到多条至同一目的地的eBGP消息时会做选择，选最优的一条使用iBGP在AS内传播。

  • 选择最短的AS-PATH
  • 选择最近（hop次数最少）的NEXT-HOP（hot potato routing）

ICMP

用于host与router通信交换网络情况。

Chapter 6 链路层

服务

  • 链路层提供相邻两个网络设备端口之间的通信服务，使用MAC地址导向。
  • 有自己独特的报文头
  • 使用Ethernet协议

实现设备

Adaptor/NIC 网卡。

错误检测

奇偶校验

  • 数据位
  • 校验位
  • 分为奇校验/偶校验，通过改变校验位使所有数据位上共有奇数/偶数个1实现
  • 收发双方1的总数奇偶性改变，则认为出错

CRC校验

循环冗余校验。

三个量：

  • 数据D
  • 生成串G，r比特
  • 冗余串R，r-1比特

收发双方公认一个二进制串G，共r位。发送方将D左移r位，然后模二除G，得到r-1位余数R，追加在D之后发送。

接收方重复模二除法的操作计算余数R，与发送过来的R比较，若不一致，则认为出错。

多接入协议

  • 出现场合：使用广播的链路结构，存在共享的总线
  • 问题：共用总线通信，出现数据传输冲突

解决途径

  • 信道分配
  • 随机访问
  • 轮流访问

信道分配 channel partitionning

将信道资源分给多接入者，共享。

TDMA时分复用
时间上分成多个等长的slot，每个slot内为每个用户分配相等的使用时长，用户在时长内有消息就发送，没有就等待。

FDMA频分复用
在频率域上划分出slot，每个用户使用一个频段进行发送。

随机访问 random access

每次将全部信道资源划分给一个用户使用，随机独享。

slotted ALOHA
将时间分成等长的slot，消息只能在slot开始的时刻开始发送，每个用户在时间上同步，仅在slot开始时才有资格发送消息。

如果多个用户同时发送，则全部发送失败，等待下个slot开始重新发送。直到某个slot仅有一个用户发送，发送成功。

效率低。

pure ALOHA
去掉了slot的划分，每个用户任何时刻都可以发送消息。增大了冲突概率。

效率更低。

CSMA
发送前监听一下目前链路状态，是否空闲可以发送；若空闲则发送，否则延迟发送。监听后如果发送则持续发送，不会中止。

由于监听的消息存在传播延时，导致监听结果虽然为空闲，但在传输回来的途中链路又被占用了，仍导致冲突。

CSMA/CD
加入冲突检测（collision detection）实现监听。检测链路上的信号强度，与发送/接收信号强度比较，确定链路是否空闲。更短时间实现链路状态监听，若发现冲突，立刻停止发送，减少链路资源浪费。

区别于普通CSMA的持续发送，CSMA/CD发送中监测到冲突后立刻停止发送。

Ethernet下CSMA/CD算法流程：

  1. NIC创建Ethernet帧
  2. 监听链路状态，当空闲时开始发送
  3. 如果发送中监测到冲突，立刻中止发送
  4. 发生m次冲突后，NIC从0~2^m^-1中随机选择一个K，等待K×512bit时间之后回到第二步

轮流访问 taking turns

在共享链路和随机访问之间谋取tradeoff。

polling
通过链路中一个master设备进行polling，轮流邀请其他设备进行通信。

token passing
在所有设备间轮流传递token，拥有token的设备允许进行通信。

局域网

MAC地址

用于局域网内链路层通信。是上层所有通信的实现。

  • 48位二进制，记为六组2位16进制数
  • 每个网卡MAC地址唯一

ARP：address resolution protocol

使用IP地址解析MAC地址。局域网内部有ARP表，记录IP地址和MAC地址转换关系。

Q：为什么要用IP解析MAC地址？
A：链路层通信需要目标MAC地址，网络层向下只能传递目标IP地址。

ARP由发出者向广播MAC地址FF-FF-FF-FF-FF-FF问询，全部局域网内设备都能收到；目标设备回复发出者自己的MAC地址，发出者更新ARP转换表。

若出现跨域（不同局域网内的设备）通信，发信者先将报文发送到网关（第一跳路由器），然后由网关转发至其他局域网。局域网内链路层通信，局域网间网络层通信。

Ethernet

连接拓扑：

  • 总线：无交换机
  • 星型：有交换机

Ethernet帧结构：

  • 源MAC地址
  • 目标MAC地址
  • 上层网络层协议
  • 数据负载
  • CRC校验码

交换机

实现链路层帧的转发，类比路由器实现网络层数据包转发。同时多线通信，无冲突，全双工。

类比路由表，交换机有交换表。

交换机获得交换表过程：

  1. 发送帧进入交换机，交换机反向学习得到输入方MAC地址对应的交换机端口，及记录TTL
  2. 查交换表，若发现目的MAC地址对应端口，直接转发至端口；否则向所有端口广播（flood）

反复进行上述过程动态维护交换表。

虚拟LAN

通过交换机端口分配实现虚拟局域网。同时虚拟出了一个路由器隔离两个局域网。同个虚拟LAN内视为通过虚拟交换机互联，不同虚拟LAN之间通过一个虚拟路由器互联。

MPLS

使用IP的普通路由器仅根据目的地址确定转发线路，使用MPLS的路由器同时使用源地址和目的地址确定转发线路。使用label进行标记，根据label选择不同的转发线路。

设备接入场景

  1. 接入网络，DHCP（链路层在广播地址上广播）请求IP地址，DNS服务器地址，网关地址
  2. DNS请求，先运行ARP获取DNS服务器MAC地址，然后发送请求，获得目标IP地址
  3. 建立TCP连接（3次握手）
  4. 发送HTTP请求，接收HTTP回复

Chapter 7 无线网络

CDMA 码分复用

允许多用户同时使用多频段通信，彼此编码方式不同。

  • 编码：发送序列×chipping序列
  • 解码：接受序列×chipping序列

不同用户使用不同chipping序列。

CSMA/CA

  • collision avoidance机制：发送前监听DIFS时间，无其他用户发送时才发送；接收方收到后等待SIFS时间然后回复ACK。ACK用来解决hidden terminal问题。

  • reserve机制：发送方首先发送RTS（request-to-send）通知接收方自己要发送数据，接收方收到后广播CTS（clear-to-send），之后发送方发送数据，其他发送方等待。

使用reserve机制的CSMA/CA：

  1. 发送方等待DIFS，发送RTS
  2. 接收方回复CTS，发送方发送数据，其他方等待
  3. 发送完成，接收方回复ACK

蜂窝网络

构成：

  • 基站
  • MSC

用户设备与基站无线连接，使用CDMA复用。

架构：

  • 2G：仅传输语音信号，基站-BSC-MSC-GatewayMSC-电话网络…
  • 3G：语音+数据（Internet），并行，基站-radio network controller-MSC/SGSN-GatewayMSC/GGSN-电话网络/Internet…
  • 4G-LTE：全部使用Internet，基站-SGW-PGW-Internet…

移动性

如何确定移动设备的网络位置？

定义：

  • home agent：归属代理，表示移动设备的归属，是地址管理设备
  • foreign agent：外部代理，管理移动设备的外部位置
  • correspondent：通信者，希望与移动设备取得联系的设备
  • permanent address：永久地址，即移动设备在归属网络（家）中的地址
  • care-of address：转交地址，移动设备在新网络子网中的地址，一般对应外部代理的地址

registration：移动设备进入新网络，与foreign agent连接，foreign agent向home agent发送信息，home agent知道设备的新网络位置。（向家通知暂住地位置）

间接路由选择：通信者向永久地址发送数据，归属代理将数据转发至外部代理，从而转交给移动设备。

直接路由选择：通信者向永久地址发送数据，归属代理返回移动设备的转交地址，通信者直接向转交地址发送数据。

移动IP

在IP包中增加了新内容：

  • H，F位：表明是home agent还是foreign agent
  • R位：表示是否需要registration