计算机网络（自顶向下的方法）

子网掩码：前n位全1，后（32-n）位全0
网络号：IP地址与子网掩码做与运算的结果
广播地址：网络位不变，主机位全置1
主机号：保留网络位，主机位为IP地址
主机号范围：网络地址+1~广播地址-1
三类网络：
- A：0.0.0.0~127.255.255.255（00~01）8网络，24主机
- B：128.0.0.0~191.255.255.255（100~101） 16网络，16主机
- C：192.0.0.0~223.255.255.255（1100~1101） 24网络，8主机
- 127.0.0.1:本地回环地址(Loopback Address)，不属于任何一个有类别地址类。它代表设备的本地虚拟接口，所以默认被看作是永远不会宕掉的接口。在Windows操作系统中也有相似的定义，所以通常在安装网卡前就可以ping通这个本地回环地址。一般都会用来检查本地网络协议、基本数据接口等是否正常。

3、动态主机配置协议（DHCP,Dynamic Host Configuration Protocol）

即插即用协议，允许主机自动获取一个IP地址（为主机分配一个临时的IP地址）
当主机加入或离开时，DHCP更新IP地址表。DHCP服务器会动态的从地址池中抽取地址和放回地址。
DHCP为新到来的主机分配IP地址：
1. DHCP发现（客户在UDP分组中广播DHCP发现报文）
2. DHCP提供（一个或多个DHCP服务器广播DHCP提供报文作出响应）
3. DHCP请求（客户从所有服务器中选择一个，提供DHCP请求报文）
4. DHCP ACK （DHCP服务器用DHCP ACK报文响应请求）
缺点：因为每到一个地方DHCP就会分配一个新的IP，故当结点在子网间移动时，其不能维持该结点与远程应用之间的TCP连接

4、网络地址转换（NAT,Network Address Translation）

解决问题：子网变大（新的设备加入）后的地址分配问题
私有IP、端口号与公有IP、端口号之间的转化（由路由器改写）

缺点：
1. 不同主机上的不同进程被NAT变为了同一个IP+端口号（破坏进程编址）；
2. 越级处理，路由器处理了传输层的分组；
3. 违反了端到端原则（结点介入了主机间的通信），妨碍了部分P2P应用（文件共享、语音应用）
4. 应该使用IPv6来解决IP不够的问题，而非用NAT
优点：
1. 解决了IP不够用的问题
2. 能够用一个IP代表所有内网的资源使用
UPnP：解决了NAT在P2P应用中NAT穿越的问题

4.3 ICMP(Internet Control Message Protocol,因特网控制报文协议)

用于差错报告，报告在某个位置IP路由器不能找到一条路径

4.4 IPv6

1、IPv4与IPv6

	IPv4	IPv6
地址容量	32bit（点分十进制）	128bit（冒号十六进制，8组）
首部大小	20B~60B	40B（没有首部检验和，选项）
分片	支持分片（根据路由MTU）	不支持分片，长度超出则丢弃，并发送“分组太大”
数据传播	单播，广播	单播，广播，任播（可以使数据报交付给一组主机中的任意一个）

2、从IPv4到IPv6

1.双栈（dual-stack）

使用双栈的结点能够使用IPv4与IPv6，能够接收与发送IPv4、IPv6

2.建隧道（tunnrling）

将IPv6打包为IPv4进行传输

隧道：两个IPv6中间的IPv4路由器的集合

4.5 路由选择算法

1、全局式路由选择算法

用完整的、全局的网络计算最短路径
链路状态算法（Link Stack）
Dijkstra算法
- D（v）：源节点到目的结点v的最低费用；
- p（v）：最短路径的前一结点（v的邻居）；
- N‘：已确认结点集

2、分散式路由选择算法

迭代的、分布式的计算方式计算最短路径
距离向量算法 DV（distance vector）
- 迭代的：算法持续到邻居间无更多的信息交换为止
- 分布式的：每个结点需要从一个或多个邻居处获得信息
- 异步的：不要求所有结点步伐一致的操作
- 每次更新到邻居结点的最短距离表
- 路由选择环路，坏消息（链路状态改变）传播慢

LS	DV
在网络上的所有结点广播信息	只和邻居结点广播信息
信息包括到邻居结点的距离D（v）	信息包括所有结点最短的距离min{dv}
收敛速度快O（ $N^{2}$ ）	收敛速度慢（路由选择环路，无穷计数）
能够广播不正确路径
健壮的，不正确链路仅在小范围传播	不正确链路会扩散到整个网络

4.6 因特网中的路由选择

自治系统（AS）用以解决路由器规模过大时路由算法计算量过于复杂，以及公司有管理自治需求的问题，提出在一个AS中运行在自治系统内部的路由选择算法（RIP、OSPF）与网关路由器

1、RIP（Routing Information Protocol,路由选择信息协议）

基于DV算法实现的一种距离向量协议，使用术语跳，指示从源路由器到目的子网的最短路径所经过的子网数量（算上自己，最大15跳）
邻居间每30s使用RIP响应报文更新信息，每台路由器需要维护一张路由选择表
RIP是基于UDP运行的应用层协议，但其功能服务于网络层

2、OSPF（Open Shortest Path First,最短路径优先路由协议）

基于LS算法的AS路由选择协议
优点：1.安全，可以鉴别OSPF报文的真实性；2.允许从多条费用相同的路径中选择一条使用；3.对单播和多播路由选择的综合支持；4.支持在单个路由选择域内的层次结构

3、BGP（Border Gateway Protocol,边界网关协议）

BGP为每个AS提供的功能：
1. 从邻居AS获取子网的可达性信息
2. 向本AS内部的所有路由器通告它（子网）的可达信息
3. 基于可达性信息与策略，确定到达某个子网的最佳路由。
内部和外部BGP
- 跨越两个AS的BGP连接称为外部BGP（External Border Gateway Protocol，eBGP）
- 在相同AS中的两台路由器之间的会话称为内部BGP（Internal Border Gateway Protocol，iBGP）
BGP基于TCP实现，功能服务于网络层
BGP路由选择（热土豆路由选择）：将分组以最低开销送出其AS

4.7 广播和多播

广播：从一个源结点到网络中所有其他结点交付分组的服务

多播：从一个源结点向其他网络中一个结点子集交付分组

1、广播方法

N次单播
无控制洪泛
- 洪泛（flooding）：结点向它的所有邻居结点都发送分组副本。
- 广播风暴（broadcast storm）：网络中存在环时，结点无休止的广播分组。
受控洪泛

五、数据链路层

5.1 链路层提供的服务

成帧（framing）：将网络层数据报用链路层帧封装起来。
链路接入：媒体访问控制MAC（Medium Access Control）规定了帧在链路上的传播规则
可靠交付（reliable data transfer）：保证无差错地传递网络层数据报，特别对于误码率较高的无线链路。许多有线的链路层不提供可靠交付服务。
差错检测和纠正

5.2 差错检测和纠正

奇偶校验（parity checking）

如果要发送包含d个比特的数据，发送方加上一个额外的校验比特。如果采用偶校验，则使这（d+1）个比特中1的总数为偶数。
接收方接收（d+1）个比特，如果采用偶校验，但是1的总数为奇数，则检查出错误。但是没有差错纠正能力。

检验和（checksum）

对于数据D，发送方计算所有数据16比特字的和，如果溢出则回卷（指加到最后一位）。
求这个和的反码（就是将结果的0换成1，1换成0）。
将数据与检验和发送给接收方。
接收方将数据和检验和的所有16比特字加到一起，如果结果全为1，则正确，反之出错。

循环冗余检测（Cyclic Redundancy Check，CRC）

接收方和发送方提前规定一个生成多项式G，包含（r+1）个比特。
发送方要发送一个包含 d 比特的数据D。
接收方计算：D末尾添r个0，除以 G ，如果余数R为0，则正确，反之有错误。
CRC=G+R，可以检测到连续的 r 比特或者更少的误差。

5.3 多路链路访问链路和协议

1、多路访问（Multiple Access）问题

多路访问协议：协调多个发送和接收结点对在一条共享广播信道上的传输行为
碰撞（collide）：多个结点同时传输帧，所有结点同时接收到多个帧。传输的帧在所有接收方发生碰撞

2、多路访问解决办法

信道划分协议（Channel Partitioning Protocols）
- 时分多路复用（time division multiple access，TDMA）
- 频分多路复用（frequency division multiple access，FDMA）
- 码分多址（Code Division Multiple Access，CDMA）
随机接入协议（Random Access Protocols）
- 时隙ALOHA（slotted ALOHA):把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片开始时刻再发送.
- ALOHA:
- 载波监听多路访问（Carrier Sense Multiple Access，CSMA）
- 具有碰撞检测的载波监听多路访问（Carrier Sense Multiple Access with Collision Detection，CSMA/CD）
- 具有碰撞避免的载波监听多路访问（Carrier Sense Multiple Access with Collision Avoidance，CSMA/CA）
轮流协议（taking-turns protocols）
- 轮询协议（polling protocol）。主节点以循环的方式轮询（poll）每个节点。
- 令牌传递协议（token-passing protocol）。传递令牌，有令牌才发送帧。