Computer Network Review

计算机网络

课程概述

参考教材

课程考核

nju2019autumn@163.com

课程内容

第一章

服务质量：

Network Protocols

Internet standards

Magnitude of Different Delay：

Queuing Delay：

Different Types of Malware

Denial of Service (DOS)

How to handle Masquerade

交换机通常位于接入网中，而路由器通常用于网络核心中。

一个分组所经历的一系列通信链路和分组交换机称为通过该网络的路径(route或path).

因特网工程任务组(Internet Engineering Task Force, IETF)

请求评论(Request For Comment, RFC)

接入网：是指将端系统物理连接到其边缘路由器(edge router)的网络。边缘路由器是端系统到任何其他远程端系统的路径上的第一台路由器。

存储转发传输(store-and-forward transmission):是指在交换机能够开始向输出链路传输该分组的第一个比特之前，必须接收到整个分组。

接入ISP-区域ISP(regional ISP)- 第一层ISP(tier-1 ISP)

第二章：应用层

两种主流体系结构：

Web和HTTP

HTTP是一个无状态协议(stateless protocol)

非持续连接(non-persistent connection): 每个请求/响应是经一个单独的TCP连接发送

持续连接(persistent connection): 所有的请求及其响应经相同的TCP连接发送

HTTP报文格式

HTTP请求报文的第一行叫做请求行(request line), 其后继的行叫做首部行(header line)，后面还可能有实体体(entity body).

请求行有三个字段：方法字段、URL字段和HTTP版本字段

HTTP响应报文包括三个部分：状态行、首部行、实体体

第三章：运输层

3.1 概述和运输层服务

运输层协议只工作在端系统

运输层协议能够提供的服务常常受制于底层网络层协议的服务模型。然而，即使底层网络协议不能在网络层提供相应的服务，运输层协议也能提供某些服务。

端口号是一个16比特的数，其大小在0~65535之间。0~1023范围的端口号称为周知端口号(well-known port).

端口扫描：可以用nmap

3.3 无连接运输：UDP

UDP特点：

|源端口号(2byte)|目的端口号(2byte)|
| 长度(2byte)   |检验和(2byte)  |
| 应用数据(报文) |

UDP校验和：即因特网校验和。2字节相加，溢出回卷，最后取反码。

端到端原则(end-end principle),该原则表述为因为某种功能必须基于端到端实现：“与在较高级别提供这些功能(比如这里的差错检测)的代价相比，在较低级别上设置的功能可能是冗余的或几乎没有价值的。”

虽然UDP提供差错检测，但它对差错恢复无能无力。UDP的某种实现只是丢弃受损的报文段，其他实现是将受损的报文段交给应用程序并给出警告。

3.4 可靠数据传输原理

可靠数据传输为上层实体提供的服务抽象是：数据可以通过一条可靠的信道进行传输。借助于可靠信道，传输数据比特就不会受到损坏或丢弃，而且所有数据都是按照其发送顺序进行交付。

GoBackN协议：

SR协议：

3.5 面向连接的运输：TCP

最大报文段长度(Maximum Segement Size,MSS): MSS通常根据最初确定的由本地发送主机发送的最大链路层帧长度(即所谓的最大传输单元(Maximum Transimission Unit, MTU))来设置。如以太网和PPP链路层协议都具有1500字节的MTU，因此MSS的典型值为1460字节。MSS不包括首部。

TCP协议没有规定收到失序的报文段应该怎么办，这一问题可以给实现TCP的编程人员去处理。他们可以丢弃或者缓存，现实中通常采用缓存。

TCP的首部：

TCP提供累积确认(cumulative acknowledgment)

3.5.3 往返时间的估计与超时

  1. 估计往返时间
    • 做SampleRTT的测量：在任意时刻，仅为一个已发送的但目前尚未被确认的报文段测量一个SampleRTT。TCP绝不为已被重传的报文段计算SampleRTT。
    • 更新公式：EstimatedRTT = $(1-\alpha)$ EstimatedRTT + $\alpha$ SampleRTT
    • $\alpha$的推荐值是$\alpha=0.125$
    • 指数加权移动平均(Exponential Weighted Moving Average, EWMA)
    • RTT偏差DevRTT,用于估算SampleRTT一般会偏离EstimatedRTT的程度：
      • DevRTT = $(1- \beta)$ DevRTT + $\beta$ |SampleRTT - EstimatedRTT|
      • $\beta$的推荐值为0.25
  2. 设置和管理重传超时间隔
    • TimeoutInterval=EstimatedRTT+4DevRTT
    • 推荐初始TimeoutInterval值为1秒。出现超时后，TimeoutInterval值将加倍。然而，只要收到报文段并更新EstimatedRTT，就使用上述公式再次计算TimeoutInterval.

3.5.4 可靠数据传输

定时器太多会带了很多开销，所以使用单一定时器

  1. 一些有趣的情况：关于超时和重传
  2. 超时间隔加倍
  3. 快速重传：一旦收到3个冗余ACK，TCP就执行快速重传(fast retransmit)
  4. 是回退N步还是选择重传：
    • TCP只会重传一个分组
    • TCP的差错恢复机制更像是GBN协议和SR协议的混合体。

3.5.5 流量控制(flow control)

3.5.6 TCP连接管理

建立连接(三次握手，three-way handshake)：

  1. 客户端-> [SYN=1,seq=client_isn] -> 服务器端
  2. 客户端 <- [SYN=1, seq=server_isn, ack=client_isn+1] <- 服务器端
  3. 客户端-> [SYN=0,seq=client_isn+1,ack=server_isn+1] ->服务器端

关闭连接：

  1. 客户端 ->[FIN]->服务器端
  2. 客户端 <- [ACK] <- 服务器端
  3. 客户端 <- [FIN] <- 服务器端
  4. 客户端 -> [ACK] ->服务器端

P169 状态图

SYN洪泛攻击

当服务器端不在某端口接收TCP连接，会发送RST。

当服务器端不在某端口接收UDP连接，会发送一个特殊的ICMP的数据报。

nmap工作原理：向目标主机的特定TCP端口发送一个特殊的TCP SYN报文段：

  1. 源主机收到一个TCP SYNACK报文段：意味着目标主机上一个程序该端口接收TCP连接，所以结果是“打开”。
  2. 源主机收到一个TCP RST报文段：该端口没有运行接收TCP连接的程序，但至少没有被防火墙阻拦。
  3. 什么也收不到：被防火墙阻拦。

3.6 拥塞控制原理

我们可以根据网络层是否为运输层拥塞控制提供了显式帮助，来区分拥塞控制方法。

TCP拥塞控制

TCP使用端到端拥塞控制

TCP采用的方法是让每一个发送方根据所感知到的网络拥塞程度来限制其能向连接发送流量的速率。

三个问题：

  1. 一个TCP发送方如何限制它向连接发送流量的速率
    • 发送方跟踪一个额外的变量：拥塞窗口(congestion window),表示为cwnd
    • 我们维护：LastByteSent - LastByteAcked $\le $ min{cwnd, rwnd}
  2. 一个TCP发送方如何感知从它到目的地之间的路径上存在拥塞呢？
    • 超时或收到三个冗余的ACK。
  3. 当发送方感知到端到端的拥塞时，采用何种算法来改变其发送速率呢？
    • 基本原则：
      • 一个丢失的报文段意味着拥塞，因此当丢失报文段时应当降低TCP发送方的速率。
      • 一个确认报文段指示该网络正在向接收方交付发送方的报文段，因此，当对先前未确认报文段的确认到达时，能够增加发送方的速率。
      • 带宽探测。

TCP拥塞控制算法

主要包括三个部分：慢启动、拥塞避免、快速恢复

  1. 慢启动
    • cwnd初始值较小，但每个RTT时刻翻倍直到下列三种情况
      • 存在一个由超时指示的丢包事件
        • 把cwnd设置为1并重新开始慢启动过程。并且将ssthresh(慢启动阈值)设置为cwnd/2
      • 达到或超过ssthresh的值，结束慢启动并且TCP转移到拥塞避免模式
      • 检测到3个冗余ACK，TCP执行一种快速重传并进入快速恢复状态
  2. 拥塞避免
    • 线性增长：每RTT 1MSS
    • 当拥塞时，ssthresh设置为cwnd的一半。
      • 如果是超时， cwnd设置为1
      • 如果是3个冗余ACK，cwnd减半
  3. 快速恢复

详细待了解！！！

TCP拥塞控制常常被称为加性增、乘性减(Additive-Increase, Multiplicative-Decrease, AIMD)拥塞控制方式。

第四章：网络层(数据平面)

因特网的网络层提供了单一的服务，称为尽力而为服务(best-effort service).

4.2 路由器工作原理

路由器的结构：

输入端口、输出端口和交换结构几乎总是用硬件实现的。控制平面的功能通常用软件实现并在路由选择处理器上执行。

4.2.1 输入端口处理和基于目的地转发

结构：$\rightarrow$ 线路端接 $\rightarrow$ 数据链路处理(协议，拆封) $\rightarrow$ 查找、转发、排队 $\rightarrow$ 交换结构

使用在每个输入端口的影子副本，转发决策能在每个输入端口本地做出，无须基于每个分组调用集中式路由选择处理器，因此避免了集中式处理的瓶颈。

转发表保存前缀，进行匹配，最长前缀匹配规则。

输入端口除了做查找，还要进行下列：

  1. 必须出现物理层和链路层处理
  2. 必须检查分组的版本号、校验和以及寿命字段，并且重写后两个字段
  3. 必须更新用于网络管理的计数器。

4.2.2 交换

4.2.3 输出端口处理

结构：交换结构 $\rightarrow$ 排队(缓存管理) $\rightarrow$ 数据链路处理(协议，封装) $\rightarrow$ 线路端接 $\rightarrow$

4.2.4 何处出现排队

  1. 输入排队
    • 线路前部(Head-Of-the-Line,HOL)阻塞
  2. 输出排队
    • 丢弃到达的分组:弃尾(drop)
    • 在缓存填满之前便丢弃一个分组：主动队列管理(Active Queue Management, AQM)算法。

用于缓存长度的经验方法：缓存数量($B$)应当等于平均往返时延(RTT)乘以链路的容量($C$) . 最近的研究： $B = RTT * C / \sqrt{N}$. $N$为TCP流的条数。

4.2.5 分组调度

  1. 先进先出(FIFO)
  2. 优先权排队(priority queuing)
    • 有非抢占式优先权排队(non-preemptive priority queuing)
  3. 循环和加权公平排队
    • 循环排队规则(round robin queuing discipline)
    • 加权公平排队(Weighted Fair Queuing, WFQ)规则

4.3 网际协议：IPv4、寻址、IPv6及其他

4.3.1 IPv4数据报格式

4.3.2 IPv4数据报分片

一个链路层帧能承载的最大数据量叫做最大传送单元(Maximum Transimission Unit, MTU). 对IP数据报长度具有严格限制并不是主要问题。问题在于在发送方与目的地路径上的每段链路可能使用不同的链路层协议，且每种协议可能具有不同的MTU。

IPv4的设计者感到在路由器中重新组装数据报会给协议带来相当大的复杂性并且影响路由器的性能。为坚持网络内核保持简单的原则，IPv4的设计者决定将数据报的重新组装工作放到端系统中，而不是放到网络路由器中。

所以分片可以发生在端系统和路由器上。重组只会发生在端系统上。

16比特标识唯一标识了一个数据报(发送主机通常将它发送的每个数据报的标识号加1)。13比特片偏移记录了该分片在原数据报中的偏移(以8字节为单位，所以13对应16)。最后一个片的标志比特被设为0，而所有其他片的标志比特被设为1.

4.3.3 IPv4编址

子网(subbet), 子网掩码(network mask)

因特网的地址分配策略被称为无类别域间路由选择(Classless Interdomain Routing, CIDR).

使用单个网络前缀通告多个网络的能力通常被称为地址聚合(address aggregation), 也称为路由聚合(route aggregation) 或路由摘要(route summarization)

a.b.c.d/x

一个地址的剩余32-x比特可认为是用于区分该组织内部设备的，其中的所有设备具有相同的网络前缀。

具有8、16和24比特子网地址的子网分别被称为A、B和C类网络。

255.255.255.255 广播地址

组织内的地址：动态主机配置协议(Dynamic Host Configuration, DHCP).DHCP除了分配IP地址，还会告诉主机它的子网掩码，它的第一跳路由器地址(常被称为默认网关)与它的本地DNS服务器的地址。 DHCP又常被称为即插即用协议(plug-and-play protocol) 或零配置(zeroconf)协议。

通常情况下，每个子网需要一个DHCP服务器，但也可以用一个DHCP中继代理(通常是一台路由器)，这个代理知道用于该网络的DHCP服务器的地址。

DHCP协议是一个4个步骤的过程：

  1. DHCP服务器发现
    • 发送DHCP发现报文(DHCP discover message), 使用UDP， 端口67。使用广播地址为目的IP，使用0.0.0.0为本机IP
  2. DHCP服务器提供
    • DHCP服务器收到一个DHCP发现报文时，用DHCP提供报文(DHCP offer message)向客户做出响应，使用广播地址为目的IP，使用本机IP为源IP。 这个报文里包含有收到的发现报文的事物ID、向客户推荐的IP地址。网络掩码以及IP地址租用期(address lease time). 服务器租用期通常设置为几小时或几天。
  3. DHCP请求
    • 从一个或多个服务器提供中选择一个，并向选中的服务器提供用DHCP请求报文(DHCP request message)进行响应，回显配置的参数。这一步中仍用广播地址为目的IP，使用0.0.0.0位源IP
  4. DHCP ACK
    • 服务器用DHCP ACK报文(DHCP ACK message) 对DHCP请求报文进行响应。 仍然是广播消息。

DHCP协议的所有消息都是广播消息。

从移动性角度看，DHCP确实有非常严重的缺陷。因为每到一个新的子网，就会获取一个新的IP地址。

4.3.4 网络地址转换(Network Address Translation, NAT)

NAT转换表(NAT translation table)

4.3.5 IPv6

IPv6有已下特性

IPv6的一些字段：

在IPv4数据报中没有的部分：

在实践中已经得到广泛采用的IPv4到IPv6迁移的方法包括建隧道(tunneling)

4.4 通用转发和SDN

通用转发：每台分组交换机包含一张匹配加动作表，该表示由远程控制器计算和分发的

第五章：网络层：控制平面

5.1 概述

完成转发表和流表的计算和维护有两种方法：

  1. 每路由器控制：每台路由器内运行这一种路由选择算法
  2. 逻辑集中式控制：由逻辑集中式路由选择控制器计算并分发转发表给每台路由器。路由器主要负责和其通信即可，获取转发表。

5.2 路由选择算法

其目的是从发送方到接收方的过程中确定一条通过路由器网络好的路径。这里的好可能是具有最低开销的，也有策略上的考量(比如某ISP不转发另一ISP的流量)

我们对路由选择算法有三种分类方式：

  1. 根据该算法是集中式还是分散式：
    • 集中式路由选择算法(centralized routing algorithm): 指需要关于网络的完整的、全局性的知识。具有全局状态信息的算法常被称作链路状态(Link State, LS)算法。
    • 分散式路由选择算法(decentralized routing algorithm): 没有节点拥有关于所有网络链路开销的完整信息。
  2. 根据算法是静态的还是动态的：
    • 静态路由选择算法(static route algorithm): 路由随时间变化缓慢，通常可以人工进行调整。
    • 动态路由选择算法(dynamic routing algorithm): 可周期性地运行或直接响应拓扑或链路开销的变化而运行。但也容易受路由选择循环、路由震荡之类问题的影响。
  3. 根据它是负载敏感的还是负载迟钝的：
    • 负载敏感算法(load-sensitive algorithm): 链路开销会动态地变化以反映出底层链路的当前拥塞水平。
    • 负载迟钝的(load-insensitive): 当今的因特网路由选择算法都是负载迟钝的。

5.2.1 链路状态路由选择算法

可以用Dijkstra算法。

5.2.2 距离向量路由算法

距离向量(Distance-Vector, DV)算法是一种迭代的、异步的和分布式的算法。

一旦更新，向邻居发送更新后的。

毒性逆转(poisoned reverse)：如果$z$通过$y$路由选择到目的地$x$，则$z$将通告$y$,它$z$到$x$的距离是无穷大。涉及3个或更多节点(而不只是两个直接相连的邻居节点)的环路将无法用毒性逆转技术检测到。

LS和DV路由选择算法的比较：

5.3 因特网中自治系统内部的路由选择：OSPF

自治的原因：规模和管理自治

一个自治系统由其全局唯一的AS号(ASN)所标识，就像IP地址那样，AS号由ICANN区域注册机构所分配。

在相同AS中的路由器都运行着相同的路由选择算法并且有彼此的信息。在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议(intra-autonomous system routing protocol).

开放最短路优先(OSPF): OSPF路由选择及其关系密切的协议IS-IS都被广泛用于因特网的AS内部路由选择。

OSPF是一种链路状态协议，它是用洪泛链路状态信息和Dijkstra最低开销路径算法。

使用OSPF，一台路由器构建了一幅关于整个自治系统的完整拓扑图。于是，每台路由器在本地运行Dijkstra的最短路径算法，以确定一个以自身为根节点到所有子网的最短路径树。

当链路状态发生变化时，路由器就会广播链路状态信息，即使为发生变换，也会周期性地广播链路状态。链路状态通告的这种周期性更新增加了链路状态算法的健壮性。

OSPF的通告包含在OSPF报文中，由IP承载，对OSPF其上层协议的值是89。

OSPF的优点：

5.4 ISP之间的路由选择：BGP

自治系统间路由选择协议(inter-autonomous system routing protocol). 边界网关协议(Broder Gateway Protocol, BGP)

正是这个协议将因特网中数以千计的ISP黏合起来。

BGP是一种分布式和异步的协议

5.4.1 BGP的作用

  1. 从邻居AS获得前缀的可达性信息。BGP允许每个子网向因特网的其余部分通告它的存在。BGP确保在因特网中的所有AS知道该子网。
  2. 确定到该前缀的"最好的"路由

5.4.2 通告BGP路由信息

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

在BGP中，每对路由器通过使用179端口的半永久TCP连接交换路由选择信息。每条直连连接以及所有通过该连接发送的BGP报文，称为BGP连接(BGP connection). 跨越两个AS的BGP连接称为外部BGP(eBGP)连接，而在相同AS中的两台路由器之间的BGP会话称为内部BGP(iBGP)连接。

5.4.3 确定最好的路由

一些术语：当路由器通过BGP连接通告前缀时，它在前缀中包括一些BGP属性(BGP attribute). 用BGP路由来说，前缀及其属性称为路由(route). 两个较为重要的属性是AS-PATH和NEXT-HOP。 AS-PATH属性包含了通告已经通过的AS列表。如果一台路由器在路径列表中看到包含了它自己的AS，它将拒绝该通告。NEXT-HOP是AS-PATH起始的路由器接口的IP地址

热土豆路由选择

在路由器转发表中增加AS外部目的地的步骤：

  1. 从AS间协议学到经多个网关可达子网x
  2. 使用来自AS内部协议的路由选择信息，以决定到达每个网关的最低开销路径的开销
  3. 热土豆路由选择：选择具有最小最低开销的网关
  4. 从转发表确定通往最低开销网关的接口$I$。在转发表中加入表项$(x,I)$

热土豆路由选择依据的思想是：对于路由器1b，尽可能快地将分组送出其AS(更明确地说，用可能的最低开销)，而不担心其AS外部到目的地的余下部分的开销。

路由选择算法

在实践中，BGP使用了一种比热土豆路由选择更为复杂但却结合了其特点的算法。对于任何给定的目的地前缀，进入BGP的路由选择算法的输入是到某前缀的所有路由的集合，该前缀是已被路由器学习和接收的。如果仅有一条这样的路由，BGP显然选择该路由。如果到相同的前缀有两条或多条路由，则顺序地调用下列消除规则直到余下一条路由：

  1. 路由被指派一个本地偏好值作为其属性之一(除了AS-PATH和NEXT-HOP以外)。一条路由的本地偏好可能由该路由器设置或可能由在相同AS中的另一台路由器学习到。本地偏好属性的值是一种策略决定，它完全取决于该AS的网络管理员。具有最高本地偏好值的路由将被选择。
  2. 从余下的路由中(所有具有相同的最高本地偏好值)，将选择具有最短AS-PATH的路由。如果该规则是路由选择的唯一规则，则BGP将使用距离向量算法决定路径，其中距离测度使用AS跳的跳数而不是路由器跳的跳数。
  3. 从余下的路由中(所有都具有相同的最高本地偏好值和相同的AS-PATH长度)，使用热土豆路由选择，即选择具有最靠近NEXT-HOP路由器的路由。
  4. 如果仍留下多条路由，该路由器使用BGP标识符来选择路由。

5.4.4 IP任播

多台服务器使用相同的IP地址，由BGP路由来选择某一服务器。CDN一般不使用IP任播，而DNS一般使用IP任播。

5.4.5 路由选择策略

任何穿越某ISP主干网的流量必须是其源或目的位于该ISP的某个客户网络中。

5.5 SDN控制平面

5.6 ICMP:因特网控制报文协议

ICMP最典型的用途是差错报告。

ping和traceroute就是用ICMP实现的

5.7 网络管理和SNMP

第六章：链路层和局域网

6.1 链路层概述

6.1.1 链路层提供的服务

任一链路层的基本服务都是将数据报通过单一通信链路从一个节点移动到相邻节点。

链路层协议能够提供的可能服务包括：

6.1.2 链路层在何处实现

链路层的主体部分是在网络适配器(network adapter)中实现。位于网络适配器核心的是链路层控制器。尽管大部分链路层是在硬件中实现的，但部分链路层是在运行于主机CPU上的软件中实现的。链路层的软件组件实现了高层链路层功能，如组装链路层寻址信息和激活控制器硬件。

6.2 差错检测和纠正技术

三种技术：奇偶校验、检验和方法 和 循环冗余检测。

6.2.1 奇偶校验

二维奇偶校验

接收方检测和纠正差错的能力被称为前向纠错。

6.2.2 检验和方法

运输层使用检验和，链路层使用CRC。why?

因为运输层差错检测用软件实现，采用简单而快速如检验和这样的差错检测方案是重要的。在另一方面，链路层的差错检测在适配器中用专门的硬件实现，它能够快速执行更复杂的CRC操作。

6.2.3 循环冗余检测

现今的计算机网络中广泛应用的差错检测技术基于循环冗余检测(Cyclic Redundancy Check, CRC)编码。CRC编码也称为多项式编码(polynomial code).

每个CRC标准都能检测小于$r+1$比特的突发差错。(这意味着所有连续的$r$比特或者更少的差错都可以检测到。)此外，在适当的假设下，长度大于$r+1$比特的突发差错以概率$1-0.5^r$被检测到。每个CRC标准也都能检测任何奇数个比特差错。

6.3 多路访问链路和协议

有两种类型的网络链路：

一个对链路层很重要的问题：如何协调多个发送和接收节点对一个共享广播信道的访问，这就是多路访问问题(multiple access problem).

多路访问协议(multiple access protocol).我们能够将任何多路访问协议分为3种类型之一：

我们希望多路访问协议应该具有下列所希望的特性：

  1. 当仅有一个节点发送数据时，该节点具有$R$ bps的吞吐量
  2. 当有$M$个节点发送数据时，每个节点吞吐量为$R/M $ bps. 这不必要求$M$个节点中的每一个节点总是有$R/M$的瞬间速率，而是每个节点在一些适当定义的时间间隔内应该有$R/M$的平均传输速率。
  3. 协议是分散的；这就是说不会因某主节点故障而使整个系统崩溃
  4. 协议是简单的，使实现不昂贵

6.3.1 信道划分协议

FDM,TDM,CDMA

6.3.2 随机接入协议

  1. 时隙ALOHA
    • 同步的，有一系列的时隙，只在时隙开始时传送，且在某一时隙发生碰撞，在该时隙结束前能检测到
    • 当一个节点有新的帧发送，它将在下一个时隙的开始进行传输
    • 如果没有检测到碰撞，则成功
    • 如果有碰撞，该节点以概率$p$在后续的每个时隙中重传它的帧，直到该帧被无碰撞地传输出去。
    • 成功的概率： $Np(1-p)^{N-1}$, 最大效率为$\frac{1}{e}$, 即0.37
  2. ALOHA
    • 不需要同步
    • 成功的概率：$Np(1-p)^{2(N-1)}$, 最大效率为$\frac{1}{2e}$
  3. 载波侦听多路访问(CSMA)
    • 两个重要规则：
      • 说话之前先听： 载波侦听(carrier sensing)
      • 如果与他人同时开始说话，停止说话：碰撞检测(collision detection)
    • 既然侦听了，又怎么会碰撞呢？：因为有广播信道端到端信道传播时延(channel propagation delay). 该传播时延越大，载波侦听节点不能侦听到网络中另一个节点已经开始传输的机会就越大。
    • CSMA不包含碰撞检测
  4. 具有碰撞检测的载波侦听多路访问(CSMA/CD)
    • 协议步骤：
      1. 适配器从网络层一条获得数据报，准备链路层帧，并将其放入帧适配器缓存中。
      2. 如果适配器侦听到信道空闲(即无信号能量从信道进入适配器)，它开始传输帧。在另一方面，如果适配器侦听到信道正在忙，它将等待，直到侦听到没有信号能量时才开始传输帧。
      3. 在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在。
      4. 如果适配器传输整个帧而未检测到来自其他适配器的信号能量，该适配器就完成了该帧。在另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，它中止传输(即它停止了传输帧)。帧长得有下限， 不然在碰撞可能在传输结束后发送。
      5. 中止传输后，适配器等待一个随机时间量，然后返回步骤2
    • 随机等待的时间量不能一样的，不然一直碰撞。我们采用二进制指数后退算法(binary exponential backoff)。
      • 当传输一个给定帧时，在该帧经历了一连串的$n$次碰撞后，节点随机地从${ 0,1,2,…,2^n-1 }$ 中选择一个$K$值。因此一个帧经历的碰撞越多，$K$选择的间隔越大。对于以太网，一个节点等待的实际时间量是$K \cdot 512$ 比特时间(即发送512比特进入以太网所需时间量的$K$倍)， $n$能够取的最大值在$10$以内。
  5. CSMA/CD 效率
    • $d_{prop}$ 表示信号能量在任意两个适配器之间传播所需的最大时间
    • $d_{trans}$ 表示传输一个最大长度的以太网帧的时间
    • 效率 =$\frac{1}{1+ 5 d_{prop}/d_{trans} }$
    • 当$d_{prop}$ 接近$0$时，效率接近1
    • 当$d_{trans}$变得很大时，效率也接近于1

6.3.3 轮流协议(taking-turns protocol)

两种：

6.4 交换局域网

6.4.1 链路层寻址和ARP:

6.4.2 以太网：

6.4.3 链路层交换机

  1. 交换机转发和过滤
    • 过滤是决定一个帧应该转发到某个接口还是应当将其丢弃的交换机功能。
    • 转发是决定一个帧应该被导向哪个接口，并把该帧移动到那些接口的交换机功能。
    • 交换机的过滤和转发借助于交换机表(switch table), 表项中包含：MAC地址，通过该MAC地址的交换机接口
    • 表项放置在表中的时间
    • 当有一个帧从接口$x$进来，目的地址为$A$
      • 如果表中没有$A$的表项，向除了接口$x$的接口转发该帧
      • 如果表中$A$对应接口$x$, 丢弃该帧
      • 如果表中$A$对应接口$y \not= x$, 转发该帧到接口$y$
  2. 自学习
    • 步骤如下：
      1. 交换表初始为空
      2. 对于在每个接口接收到的每个入帧，该交换机在其表中存储：源MAC地址，到达的接口，当前时间
      3. 如果在一段时间(称为老化期(aging time))后，交换机没有接受到以该地址作为源地址的帧，就在表中删除这个地址。
    • 交换机是即插即用设备(plug-and-play device)
  3. 链路层交换机的性质
    • 消除碰撞
    • 异质的链路
    • 管理
    • 延伸知识：交换机毒化(switch poisoning). 它向交换机发送大量的具有不同伪造源MAC地址的分组，因为用伪造表项填满了交换机表，没有为合法主机留下空间。这使该交换机广播大多数帧，这些帧能够由嗅探器俘获到。由于这种攻击只有技艺高超的攻击者才能做到，因此交换机比起集线器和无线局域网来更难受到嗅探
  4. 交换机和路由器比较

交换和路由的区别

交换功能 $\begin{cases} \text{主机为单位} \ \text{网段为单位} \end{cases}$

交换：交换表。

不选最短路——支撑树算法

  1. 帧转发——目的MAC
  2. 地址学习——源MAC
  3. 环路检测——

链路层交换机

6.4.4 虚拟局域网

等级交换结构的缺点：

我们可以通过支持虚拟局域网(Virtual Local Network, VLAN)的交换机来处理。支持VLAN的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网。在一个基于端口的VLAN中，交换机的端口(接口)由网络管理员划分为组。每个组构成一个VLAN，在每个VLAN中的端口形成一个广播域。

6.5 链路虚拟化：网络作为链路层

6.6 数据中心网络

6.7 Web页面请求的历程

第七章：无线网络和移动网络

7.1 概述

无线网络分类：

7.2 无线链路和网络特征

无线链路与有线链路的区别：

无线链路协议不仅采用有效的CRC错误检测码，还采用了链路层ARQ协议来重传受损的帧。

信噪比(Signal-to-Noise Ratio, SNR), 比特差错率(BER)

$SNR = 10 \log_{10} (\frac{P_{signal}}{P_{noise}})$

隐藏终端问题(hidden terminal problem)： 即使A和C的传输确实是在目的地B发生干扰，环境的物理阻挡(例如，一座大山或者一座建筑)也可能会妨碍A和C互相听到对方的传输。

衰减可能也会导致无法检测碰撞。

CDMA

7.3 WiFi: 802.11 无线LAN

802.11有好几个标准，它们都使用了相同的媒体访问协议CSMA/CA. 它们的链路层帧也都使用相同的帧结构

802.11设备工作在两个不同的频段上：2.4~2.485GHz(2.4GHz频段)和5.1~5.8GHz(称之为5GHz频段)。

802.11体系结构

基本服务集(Basic Service Set, BSS)：一个BSS包含一个或多个无线站点和一个被称为接入点(Access Point, AP)的中央基站(base station).

配置AP的无线LAN经常被称作基础设施无线LAN(infrastructure wireless LAN). 其中基础设置是指AP连同互联AP和一台路由器的有线以太网。

信道与关联

7.3.2 802.11 MAC协议

802.11的设计者为802.11无线LAN选择了一种随机访问协议：带碰撞避免的CSMA(CSMA with collision avoidance),或简称为CSMA/CA

以太网和802.11虽然都使用载波侦听随机接入，但他们有区别：

  1. 802.11使用碰撞避免而非碰撞检测
  2. 802.11使用链路层确认/重传(ARQ)方案

802.11MAC协议使用碰撞避免而非碰撞检测。主要有两个原因

一旦一个站点开始发送一个帧，它就完全地发送该帧。

链路层确认方案(link-layer acknowledgment):目的站点收到一个通过CRC检验的帧后，它等待一个被称作短帧间间隔(Short Inter-Frame Spacing, SIFS)的一小段时间，然后发回一个确认帧。如果发送站点在给定的时间内未收到确认帧，它假定出现了错误并重传该帧，使用CSMA/CA协议访问该信道。如果在若干固定次重传后仍未收到确认，发送站点将放弃发送并丢弃该帧。

CSMA/CA协议：

  1. 如果某站点最初监听到信道空闲，它将在一个被称作分布式帧间间隔(Distributed Inter-Frame Space, DIFS)的短时间段后发送该帧。
  2. 否则，该站点选取一个随机回退值并且在侦听信道空闲时递减该值。当侦听到信道忙时，计数值保持不变。
  3. 当计数值减为0时，该站点发送整个数据帧并等待确认。
  4. 如果收到确认，发送站点知道它的帧已被目的站正确接受了。如果该站点要发送另一帧，它将从第二步开始CSMA/CA协议。如果未收到确认，发送站点将重新进入第二步中的回退阶段，并从一个更大范围内选取随机值。

IEEE 802.11协议允许站点使用一个短请求发送(Request to Send, RTS)控制帧和一个短允许发送(Clear to Send, CTS)控制帧来预约对信道的访问。尽管RTS/CTS交换有助于降低碰撞，但它同样引入了时延以及消耗了信道资源。因此RTS/CTS交换仅仅用于为长数据预约信道。在实际中，每个无线站点可以设置一个RTS门限值，仅当帧长超过门限值时，才使用RTS/CTS序列。对许多无线站点而言，默认的RTS门限值大于最大帧长值，因此对所有发送的DATA帧，RTS/CTS序列都被跳过。

可以使用802.11 作为一个点对点链路。

7.3.3 IEEE 802.11帧

  1. 有效载荷与CRC字段
    • 有限载荷允许的最大长度为2312字节，但它通常小于1500字节
  2. 地址字段
    • 802.11帧中有4个地址字段，每个都可以包括一个6字节的MAC地址
      • 地址2是传输该帧站点的MAC地址。相当于源地址
      • 地址1是要接受该帧的无线站点的MAC地址，相当于目标地址
      • 地址3包含这个路由器接口的MAC地址。地址3在BSS和有限局域网互联中起着关键作用。
      • 当AP在自组织模式中互相转发时使用第四个地址。
  3. 序号、持续期和帧控制字段
    • 使用序号可以使接收方区分新传输的帧和以前帧的重传。
    • 802.11协议允许传输节点预约信道一段时间，包括传输其数据帧的时间和传输确认的时间。这个持续期值被包括在该帧的持续期字段中(在数据帧和RTS和CTS帧中均存在)。
    • 帧控制字段包含很多子字段
      • 类型和子类型字段用于区分关联、RTS、CTS、ACK和数据帧
      • WEP字段指示了是否使用加密
      • To和From字段用于定义不同地址字段的含义。

7.3.4 在相同的IP子网中的移动性

保持自己的IP地址和所有正在进行的TCP连接

保持IP地址不变，两个AP有着相同的SSID，那交换机如何知道设备已经更换了AP(更换了交换机的端口)呢，可以通过新的AP，发送一个广播帧，那么就能更新交换机的表项。

802.11中的高级特色

  1. 802.11速率自适应：类似于TCP的拥塞控制
  2. 功率管理：节点睡眠。AP先缓存目标帧

6.3.6 个人域网络：蓝牙和ZigBee

  1. 蓝牙
    • 802.15.1 也被称为无线个人域网络(Wireless Personal Area Network, WPAN)
    • 以TDM方式工作于无须许可证的2.4GHz无线电波段，每个时隙长度为625 $\mu s$
    • 在每个时隙内，发送方利用79个信道中的一个进行传输，同时从时隙到时隙以一个已知的伪随机方式变更信道。这种被称作跳频扩展频谱(frequency-Hopping Spread Spectrum, FHSS).
    • 802.15.1网络是自组织网络
    • 802.15.1设备首先组织成一个多达8个活动设备的皮可网(piconet). 这些设备之一被指定为主设备，其余充当从设备。
    • 主节点真正控制皮可网，它的时钟确定了皮可网中的时间，它可以在每个奇数时隙中发送，而从设备仅当主设备在前一时隙与其通信后才可以发送，并且只能发送给主设备。除了从设备，网络中还可以有多达255个的寄放(parked)设备.这些设备仅其状态被主节点从寄放转换为活动之后才可以进行通信。
  2. ZigBee
    • IEEE标准化的第二个个人域网络是802.14.5
    • ZigBee较之蓝牙其服务目标是低功率、低数据率、低周期的应用。

第八章：计算机网络中的安全

8.1 什么是网络安全

安全通信具有下列所需要的特性：

8.2 密码学原则

8.2.1 对称密钥密码体制

攻击分三种：

8.2.2 公开密钥加密

  1. RSA
    1. 选择两个大素数$p$和$q$
    2. 计算$n=pq$ 和 $z=(p-1)(q-1)$
    3. 选择一个小于$n$的数$e$, 且使$e$ 和$z$ 没有(非1的)公因数
    4. 求一个数$d$ 使得$ed-1$ 可以被$z$整除
    5. 公钥是$(n,e)$ , 私钥是$(n,d)$
  2. 会话密钥
    • 用RSA加密会话密钥，使用对称的会话密钥进行通信。

8.3 报文完整性和数字签名

8.3.1 密码散列函数

密码散列函数要具有下列性质：找到任意两个不同的报文$x$和$y$使得$H(x)=H(y)$，在计算上是不可能的。

8.3.2 报文鉴别码

Alice和Bob共享秘密$s$,被称为鉴别密钥(authentication key).

  1. Alice生成报文$m$, 加上$s$, 得到$m+s$, 然后计算散列$H(m+s)$(例如使用SHA-1). $H(m+s)$ 被称为报文鉴别码(Message Authentication Code, MAC).
  2. 然后Alice发送$(m,H(m+s))$
  3. Bob根据$m$ 和$s$ 计算$H(m+s)$ 来判断是否正常。

8.3.3 数字签名

用公钥加密

公钥认证：

将公钥与特定实体绑定通常是认证中心(Certification Authority, CA)完成的，CA的职责就是使识别和发行证书合法化。

8.4 端点鉴别(end-point authentication)

8.5 安全电子邮件

PGP

8.6 使TCP连接安全：SSL

安全套接字层(Secure Socket Layer, SSL)

运输层安全性(Transport Layer Security, TLS)

SSL记录： 类型| 版本 | 长度 | 数据 | MAC

8.6.2 更完整的描述

  1. SSL握手
    1. 客户发送它支持的密码算法的列表，连同一个客户的不重数
    2. 从该列表中，服务器选择一种对称算法(例如AES)、一种公钥算法(例如具有特定密钥长度的RSA)和一种MAC算法。它把它的选择以及证书和一个服务器不重数返回给客户。
    3. 客户验证该证书，提取服务器的公钥，生成一个前主密钥(Pre-Master Secret, PMS), 用服务器的公钥加密该PMS，并将加密的PMS发送给服务器。
    4. 使用相同的密钥导出函数，客户和服务器独立地从PMS和不重数中计算出主密钥(Master Secret, MS). 然后该MS被切片以生成两个密码和两个MAC密钥。此外，当选择的对称密码应用于CBC，则两个初始化向量(Initialization Vector, IV)也从该MS获得，这两个IV分别用于该连接的两段。自此以后，客户和服务器之间发送的所有报文均被加密和鉴别(使用MAC)。
    5. 客户发送所有握手报文的一个MAC
    6. 服务器发送所有握手报文的一个MAC

在SSL中，不重数用于防御"连接重放"，而序号用于防御在一个进行中的会话中重放个别分组。

  1. 连接关闭

8.7 网络层安全性：IPsec和虚拟专用网

IP安全(IP Security)协议更常被称为IPsec，它为网络层提供了安全性。许多机构使用IPsec创建了运行在公共因特网之上的虚拟专用网(Virtual Private Network, VPN).

8.7.1 IPsec和虚拟专用网

当总部中的一台主机向某旅馆中的某销售员发送一个IP数据报时，总部中的网关路由器将经典的IPv4转换成为IPsec数据报，然后将该IPsec数据报转发进因特网。该IPsec数据报实际上具有传统的IPv4首部，因此在公共因特网中的路由器处理该数据报，仿佛它对路由器而言是一个传统的IPv4数据报。但是，IPsec数据报的载荷包括了一个IPsec首部，该首部被用于IPsec处理；此外，IPsec数据报的载荷是被加密的。当该IPsec数据报到达销售员的便携机时，便携机的操作系统解密载荷，并将解密的载荷传递给上层协议。

8.7.2 AH协议和ESP协议

在IPsec协议族中，有两个主要协议：鉴别首部(Authentication Header, AH) 协议 和 封装安全性载荷(Encapsulation Security Payload, ESP)协议。

ESP协议的使用比AH协议要广泛得多。

8.7.3 安全关联

在从源实体向目的实体发送IPsec数据报之前，源和目的实体创建了一个网络层的逻辑连接。这个逻辑连接称为安全关联(Security Association, SA). 一个SA是一个单工逻辑连接；也就是说它是从源到目的地单向的。如果两个实体要互相发送安全数据报，则需创建两个SA，每个方向一个。

8.9 运行安全性：防火墙和入侵检测系统

8.9.1 防火墙

防火墙是一个硬件和软件的结合体，它将一个机构的内部网络与整个因特网隔离开，允许一些数据分组通过而阻止另一些分组通过。

防火墙具有3个目标：

防火墙能够分为3类：

8.9.2 入侵检测系统

为了检测多种攻击类型，我们需要执行深度分组检查(deep packet inspection)

当观察到潜在恶意流量时能产生告警的设备成为入侵检测系统(Instrusion Detection System, IDS).

滤除可疑流量的设备称为入侵防止系统(Intrusion Prevention System, IPS)

一个机构可能在它的机构网络中部署一个或多个IDS传感器。

IDS系统大致可分为两类：

第九章：多媒体网络

9.1 多媒体网络应用

9.1.1 视频的性质

视频最为显著的特点或许是它的高比特率(high bit rate).

视频有两种冗余：空间冗余和时域冗余。他们都可以用来进行视频压缩(video compression)

我们可以使用压缩来生成相同视频的多重版本(multiple version)

9.1.2 音频的性质

9.1.3 多媒体网络应用的类型

  1. 流式存储音频和视频
  2. 会话式IP语音和视频
    • 高度时延敏感(delay-sensitive)
    • 容忍丢包(loss-tolerant)
  3. 流式实况音频和视频

9.2 流式存储视频

流式视频系统可分为三种类型：

绝大多数今天的系统应用了HTTP流和适应性HTTP流

这三种形式的视频流的共同特点是广泛使用了客户端应用缓存，以此来缓解变化的端到端时延和变化的服务器和客户之间可用带宽量的影响。

9.2.1 UDP流

UDP流除了服务器到客户的视频流外，两者间还并行地维护一个单独的控制连接，通过该连接，客户可以发送有关会话状态的命令(如暂停、重新开始、重定位等)。

UDP流有三个重大不足：

9.2.2 HTTP流

客户端应用缓存

9.3 IP语音

9.3.1 尽力而为的服务限制

几乎所有现有的VoIP应用默认运行在UDP上。Skype使用了UDP，除非用户位于阻碍UDP报文段的NAT或防火墙之后。

9.4 实时会话式应用的协议

9.4.1 RTP

RTP通常运行在UDP之上。发送端在RTP分组中封装媒体块，然后在UDP报文段中封装该分组。

9.4.2 SIP

9.5 支持多媒体的网络