计算机网络考前复习
计算机网络概述
- 网络协议(Network protocol)简称协议。协议规定了通信实体之间所交换的消息的格式、意义、顺序以及针对收到信息或发生的事件所采取的行动。
- 协议的三要素：语法、语义、时序
- 计算机网络结构：网络边缘、接入网络/物理介质、网络核心(核心网络)
- 网络核心的关键功能：路由(确定分组从源到目的的传输路径)+转发(将分组从路由器的输入端口交换至正确的输出端口)
- 端系统通过接入ISP连接到Internet
- 多路复用：频分多路复用(FDM)、时分多路复用(TDM)、波分多路复用(WDM)、码分多路复用(CDM，相同频率载波、不同的码片序列)
- 数据交换的类型：电路交换(独占资源)、报文交换、分组交换
- 电路交换：建立连接(呼叫/电路建立)、通信、释放连接(拆除电路)
- 报文交换：发送信息整体
- 分组交换：报文拆出一系列相对较小的数据包，产生额外开销
- 速率/数据率/数据传输速率/比特率 单位：b/s(或bps) 通常指额定速率或标称速率
- 带宽：数字信道所能传达的最高数据率 单位：b/s(或bps)
- 四种分组延迟：节点处理延迟(差错检测、确定输出链路)、排队延迟(等待输出链路可用)、传输延迟(分组大小/传输速率)、传播延迟(物理链路长度/信号传播速度)
- 时延带宽积：传播时延*带宽($d_{prop}\times R (bits)$)
- OSI参考模型(从上到下：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层)
- 物理层：接口特性(机械、电气、功能、规程)、比特编码、数据率、比特同步、传输模式(单工、半双工、全双工)
- 数据链路层：组帧、物理寻址、流量控制、差错控制、访问控制
- 网络层：逻辑寻址(IP地址)、路由、分组转发
- 传输层：端到端进程间的完整报文传输
- 会话层：对话控制(建立、维护)、同步
- 表示层：数据表示转化、加密/解密、压缩/解压缩
- 应用层：支持用户通过用户代理(浏览器)或网络接口使用网络(服务，FTP/SMTP/HTTP)
- TCP/IP参考模型从上到下：应用层(HTTP、SMTP、DNS、RTP)、运输层(TCP、UDP)、网际层(IP)、网络接口层
- 五层参考模型：综合OSI和TCP/IP的优点(从上到下：应用层、传输层、网络层、链路层、物理层)
网络应用
网络应用基本原理
- 网络应用的体系结构：客户机/服务器结构(C/S)、点对点结构(P2P)、混合结构(Napster)
- 进程间通信：套接字Socket
- 寻址方式：IP地址+端口号
- Internet提供的传输服务：TCP服务(面向连接、可靠传输、流量控制、拥塞控制)、UDP服务(无连接、不可靠的数据传输)
Web应用
- HTTP连接的两种类型：非持久性连接(HTTP 1.0版本，每个TCP连接最多传输一个对象)、持久性连接(HTTP 1.1版本，每个TCP连接允许传输多个对象)
- HTTP协议有两类消息：请求消息(request)、响应消息(response)
- 上传输入的方法：POST、GET
- HTTP/1.0：GET、POST、HEAD
- HTTP/1.1：GET、POST、HEAD、DELETE
- HTTP响应状态代码：200 OK、301 Moved Permanently、400 Bad request、404 Not Found、505 HTTP Version Not Surported
- Cookie的组件：HTTP响应/请求消息的头部行、保存在客户端主机上的Cookie文件、Web服务器端的后台数据库
- Web缓存/代理服务器技术
Email应用
- 构成组件：邮件客户端、邮件服务器、SMTP协议
- SMTP协议通过TCP进行email信息的可靠传输
- 传输过程的三个阶段：握手、信息的传输、关闭
- 多媒体扩展MIME：通过邮件头部增加额外的行以声明内容类型
- 邮件访问协议：POP3、IMAP、HTTP
DNS应用
- DNS服务：域名指向IP地址的翻译
- 递归查询
P2P应用
- 索引：IP地址+端口号
- 集中式索引：节点加入时通知中央服务器地址和内容。问题：单点失效问题、性能瓶颈、版权问题
- 泛洪查询：完全分布式的架构
- 层次式覆盖网络：超级节点+子节点
Socket编程
- 应用编程接口API：位于应用层和传输层中间。
- WSAStartup：使用socket的应用程序在使用socket前必须首先调用WSAStartup。
- WSACleanup：完成对socket的应用后调用，释放资源。
- socket(protofamily,type,proto)：创建套接字。参数一：协议族。参数二:套接字类型。参数三：协议号。
- closesocket(SOCKET sd)：关闭套接字。
- bind(sd,localaddr,adrrlen)：绑定套接字的本地端点地址(IP地址+端口号)。
- listen(sd,queuesize):套接字置为监听状态(仅服务器调用)。
- connect(sd,saddr,saddrlen)：客户程序使客户套接字sd与服务器特定端口的套接字sadrr进行连接。
- accept(sd,caddr,caddrlen)：服务器从处于监听状态的套接字sd请求队列中取出一个客户请求。(仅服务器调用)
- send/sendto：TCP或调用了connect函数的UDP/UDP与没调用connect的UDP。
- recv/recvfrom：TCP或调用了connect函数的UDP/UDP与没调用connect的UDP。
- getsockopt/setsockopt：设置/获取套接字参数。
- TCP客户端软件流程：确定服务器IP地址与端口号、创建套接字、分配本地端点地址(IP地址+端口号)、连接服务器(套接字)、遵循应用层协议进行通信、关闭/释放连接。
- UDP客户端软件流程：确定服务器IP地址与端口号、创建套接字、分配本地端点地址(IP地址+端口号)、指定服务器端点地址，构造UDP数据报、遵循应用层协议进行通信、关闭/释放连接。
- 4种类型基本服务器：循环无连接服务器、循环面向连接服务器、并发无连接服务器、并发面向连接服务器。
传输层
传输层服务
- 多路复用/分用、可靠数据传输机制、流量控制机制、拥塞控制机制
- 提供进程之间的逻辑通信机制(TCP/UDP)
复用和分用
- 接收端多路分用
- 发送端多路复用
- 无连接分用：利用端口号创建socket，收到UDP段后检查其目的端口号，将UDP段导向绑在该端口号的socket。
- 面向连接的分用：接收端根据源IP+端口号和目的IP+端口号选择合适的Socket。
无连接传输协议
- UDP Checksum校验和
可靠数据传输
- Rdt 2.0：利用校验和检测位错误，正确则告诉发送方分组已正确接收(ACK)，错误则告诉发送方有错误(NAK)，发送方收到NAK后重传分组。
- Rdt 2.1：对ACK和NAK添加checksum，为每个分组增加序列号避免重复分组。
- Rdt 2.2：只使用ACK，接收方通过ACK告知最后一个被成功接收的分组。
- Rdt 3.0：添加定时器，解决分组丢失的问题。
滑动窗口协议
- 发送方在收到ack之前连续发送多个分组
- Go-Back-N(GBN)协议，窗口尺寸为N，最多允许N个分组未确认。为空中的分组设置定时器。ACK(n)：n及以前的分组被正确接收。超时则重传大于等于n的还未收到ACK的分组。
- Select-Repeat(SR)协议，设置缓存机制，缓存乱序到达的分组。为每个分组设置定时器。
网络层
网络层服务
- 从发送主机向接受主机传送数据段
- 核心功能：转发+路由
- 网络服务模型：无连接服务、连接服务
虚电路网络与数据报网络
- 数据报网络提供网络层无连接服务
- 虚电路网络提供网络层连接服务
- 类似于传输层的TCP/UDP，但是网络层服务是主机到主机的服务，由网络核心实现。
- 虚电路：一条从源主机到目的主机，类似于电路的逻辑连接。(分组交换，使用链路全部带宽)
- 虚电路通信过程：呼叫建立、数据传输、拆除呼叫。
- 数据报网络：网络层无连接、每个分组携带目标地址、路由器根据分组的目标地址转发分组。
IPv4协议
- 网络链路存在最大传输单元(MTU)
- 大IP分组向较小MTU链路转发时，可以被分片，IP分片到达目的主机后进行重组。
- IP地址：32比特(IPv4)
- 网络号(NetID)：高位比特
- 主机号(HostID)：低位比特
- IP子网：IP地址具有相同网络号的设备接口，不跨越路由器可以彼此物理连通的借口。
- A类地址：0.0.0.0~127.255.255.255
- B类地址：128.0.0.0~191.255.255.255
- C类地址：192.0.0.0~223.255.255.255
- D类地址：224.0.0.0~239.255.255.255
- E类地址：240.0.0.0~255.255.255.255
- 特殊IP地址：
| NetID | HostID | 作为IP分组源地址 | 作为IP分组目的地址 | 用途 |
|---|---|---|---|---|
| 全0 | 全0 | 可以 | 不可以 | 在本网中表示本机，路由 表中表示默认路由 |
| 全0 | 特定值 | 不可以 | 可以 | 本网内某个特定主机 |
| 全1 | 全1 | 不可以 | 可以 | 本网广播地址 |
| 特定值 | 全0 | 不可以 | 不可以 | 网络地址，表示一个网络 |
| 特定值 | 全1 | 不可以 | 可以 | 对特定网络所有主机广播 |
| 127 | 非全0或 非全1的 任何数 |
可以 | 可以 | 环回地址 |
- 私有IP地址：
| Class | NetIDs | Blocks |
|---|---|---|
| A | 10 | 1 |
| B | 172.16 to 172.31 | 16 |
| C | 192.168.0 to 192.168.255 | 256 |
- 子网划分：将原网络的主机号的部分比特设为子网号。
- 子网掩码：NetID、SubID全取1，HostID全取0。
- A类子网掩码：255.0.0.0
- B类子网掩码：255.255.0.0
- C类子网掩码：255.255.255.0
- 借用3比特划分子网的B网的子网掩码：255.255.224.0
无类域间路由聚合(CIDR)
- 无类域间路由聚合：a.b.c.d/x，x为前缀长度。
- 路由聚合：最长前缀匹配优先
DHCP协议
- 主机广播-发现报文
- DHCP服务器-提供报文
- 主机请求IP地址-请求报文
- DHCP服务器分配IP地址-确认报文
网络地址转换(NAT)
- 所有离开本地网络去往Internet的数据报的源IP地址需替换为相同的NAT IP地址以及不同的端口号。
- 违背端到端通信原则，开发者必须考虑NAT的存在,e.g. P2P。
ICMP协议
- 互联网控制报文协议ICMP支持主机和路由器：差错报告、网络探寻
- 两类ICMP报文：差错报告报文(目的不可达、源抑制、超时/超期、参数问题、重定向)、网络探寻报文(回声请求与应答报文、时间戳请求与应答报文)
IPv6
- IPv6数据报格式：固定长度的40字节基本首部，不允许分片。
- 移除checksum，加快每跳时间。
路由算法
- 链路状态路由算法：Dijkstra算法，所有节点掌握网络拓扑和链路费用，计算从一个节点到其他所有节点的最短路径。
- 距离向量路由算法：Bellman-Ford算法，计算到邻居的费用与邻居到目标费用的最小值。存在无穷技术问题。
- 层次路由：聚合路由器为一个区域-自治系统AS。同一AS内的路由器运行相同的算法。
- 网关路由器位于AS边缘，通过链路连接其他AS的网关路由器。
- 热土豆路由：将分组转发给最近的网关路由器
Internet路由
- Internet采用层次路由
- 常见的AS内部路由协议：路由信息协议(RIP)、开放最短路径优先(OSRP)、内部网关路由协议(IGRP)
- RIP：距离度量,存在最大跳步数(e.g. 15)，每条链路1个跳步。
- RIP：每隔30s，邻居交换一次DV(距离向量)，成为通告。180s没有收到通告则该链路失效。
- RIP：每次通告最多25个目的的子网。
- OSPF：采用链路状态路由算法，利用Dijkstra计算路由。
- OSPF：允许使用多条相同费用的路径。
- BGP：eBGP(从邻居AS获取子网可达信息)、IBGP(向所有AS内部路由器传播子网可达信息)
数据链路层
数据链路层服务
- 数据链路层负责通过一条链路，从一个节点向另一个物理链路直接相连的相邻节点传送数据报。
- 组帧、链路接入、相邻节点间可靠交付、流量控制、差错检测、差错纠正、全双工和半双工通信控制。
差错编码
- 检错码、纠错码
- 对于检错码，如果编码集的汉明距离$d_s=r+1$，则该检错码可以检测$r$位的差错。
- 对于纠错码，如果编码集的汉明距离$d_s=2r+1$，则该纠错码可以纠正$r$位的差错。
- 奇偶校验码：1比特校验位(检测奇数位差错)、二维奇偶校验(检测奇数位差错、部分偶数位差错，纠正同一行/列的奇数位错)
- checksum
- 循环冗余校验码CRC
多路访问控制(MAC)协议
- 采用分布式算法决定节点如何共享信道，即决策节点何时可以传输数据。
- 信道划分MAC协议(多路复用技术，TDMA、FDMA、CDMA、WDMA)、随机访问MAC协议(冲突恢复机制)、轮转MAC机制(节点轮流使用信道)
随机访问MAC协议
- 两个或多个结点同时传输，检测冲突并从冲突中恢复。
- 典型的随机访问MAC协议：时隙ALOHA、ALOHA、CSMA、CSMA/CD、CSMA/CA
- 时隙ALOHA：假定所有帧大小相同，时间被划分为等长的时隙，结点只能在时隙开始时刻发送帧，结点间时钟同步，如果两个或两个以上结点发送帧则结点检测到冲突。
- 时隙ALOHA：无冲突——在下一时隙继续发送新的帧，冲突——下一时隙以概率p重传该帧，直至成功。
- ALOHA：有新的帧生成时立即发送，冲突可能性增大，效率比时隙ALOHA更差！
- 载波监听多路访问协议CSMA：发送帧之前监听信道，信道空闲发送完整帧，信道忙则推迟发送。问题：继续发送冲突帧，浪费信道资源。
- CSMA/CD：检测到冲突后传输终止，减少信道浪费。“边发边听，不发不听。”
轮转访问MAC协议
- 主节点轮流邀请从属节点发送数据
局域网
ARP协议
- 48位MAC地址：固化在网卡的ROM中，有时也可以软件设置。作用于局域网内标识一个帧从哪个接口发出，到达哪个物理相连的其他接口。
- ARP表：LAN中的每个IP结点(主机、路由器)维护一个表，存储某些LAN节点的IP/MAC地址映射关系。
以太网
- 物理拓扑：总线、星型
- 以太网的MAC协议：采用二进制指数退避算法的CSMA/CD
- 以太网交换机：储存-转发以太网帧，检验到达帧的目的MAC地址，选择性向一个或多个输出链路转发帧。主机感知不到交换机的存在。即插即用。自学习。
- 虚拟局域网VLAN：支持VLAN划分的交换机，可以在一个物理LAN架构上配置、定义多个VLAN。
PPP协议
- 常见的点对点数据链路控制协议：HDLC、PPP
- PPP设计需求：组帧、比特透明传输、差错检测、连接活性检测、网络层地址协商。
802.11无线局域网
- 无线信道很难实现边发送边检测冲突。
- 发送端首先利用CSMA向BS发送一个很短的RTS帧，BS广播一个CTS帧。通过很小的预约帧避免数据帧冲突。