深度学习笔记

1 概论

网络接入方式

网络边缘

处在因特网边缘的部分就是连接在因特网上的所有的主机。这些主机又称为端系统(End System)。

端系统中运行的程序之间的通信方式通常可划分为两大类：

客户/服务器(Client/Server, C/S)方式 ：通信由客户 A发起， 向服务器 B 请求服务， 而服务器 B 向客户 A 提供服务。

对等(Peer-to-Peer , P2P)方式：Peer既是客户，又是服务器

网络核心

因特网中最复杂的部分。

功能：向网络边缘中的大量主机提供连通性， 使边缘部分中的任何一个主机都能够和其他主机 通信(即发送或接收数据)

核心设备：路由器(Router)

路由器是实现分组交换(Packet Switching)的关键 构件，其任务是转发收到的分组，这是网络核心 部分最重要的功能

电路交换和分组交换

“交换”(switching)的含义就是转接——把一条电话线转接到另一条电话线，使它们连通起来。

从通信资源的分配角度来看， “交换”就是按照某种方式动态地分配传输线路的资源。

电话系统（电路交换）

笨终端，聪明的网络

确保每个网络部件都是可靠的

​ 系统可靠性＝部件可靠性

​ 通过局部冗余实现部件的高可靠性

​ 期望每个部件都能正常工作，部件失败的可能性 很低

需要人工配置的，高度控制的网络

主要特点

电路交换分为三个阶段： 建立连接、通信、释放连接

分组交换系统

建立在简单的、不可靠部件上的可靠系统

自适应的系统

聪明的终端，可以修正传输错误

分组交换网络抵御故障的能力较强，重新传输 的是出问题的数据包、而不是全部信息；如果数据包遇到计算机发生故障或者线路中断，会 另找其他的传输路径。

主要特点

在发送端，先把较长的报文划分成较短的、固定长度的数据段（分组）;

每一个数据段前面添加上首部构成分组;

依次把各分组发送到接收端;

接收端收到分组后剥去首部还原成报文

数据先分成分组后再传输

每个分组单独选路

路由器的处理过程

在路由器中的输入和输出端口之间没有直接连线（即没有建立物理连接）。

路由器处理分组的过程是：

​ ①把收到的分组先放入缓存(暂时存储);

​ ②查找转发表，找出到某个目的地址应从哪个 端口转发;

​ ③把分组送到适当的端口转发出去

==存储转发==

主机和路由器的作用不同

​ 主机是为用户进行信息处理的，并向网络发送分组，从网络接收分组

​ 路由器对分组进行存储转发，最后把 分组交付目的主机

分组交换的优点

高效 动态分配传输带宽，对通信链路是逐段占用

灵活 以分组为传送单位和查找路由

迅速 不必先建立连接就能向其他主机 发送分组

可靠 保证可靠性的网络协议；分布式的 路由选择协议使网络有很好的生存性

分组交换带来的问题

分组在各结点存储转发时需要排队， 并要检查分组首部决定向何处转发， 这就会㐀成一定的时延

分组必须携带的首部(里面有必不可少 的控制信息)也㐀成了一定的开销

分组交换和电路交换的时延特性

电路交换时延与数据长度有关

分组交换时延：转发时延（路由器）+传输时延

计算机网络的类型

WAN（Wide Area Network）,也称为远程网

通信子网主要使用分组交换技术

城域网（Metropolitan Area Network, MAN)

局域网(Local Area Network，LAN)

不存在路由选择问题

关系

局域网和广域网（WAN和LAN）

局域网和广域网的侧重点不同：
LAN：共享信道，冲突算法
解决网络中随时可能产生的冲突，减少冲突，
减少错误
WAN：网状拓扑，路由算法
找出一条最佳的路径，从而加快转发㏿度，
减少错误

ISP和骨干网

ISP：网络服务提供商 Internet Service Provider

把城市之间连接起来的网就叫骨干网
直接和国外连接（即有国际出口）
其他有接入功能的ISP通过骨干网连到国外
“骨干网”通常是用于描述大型网络结构时经常使用的词语，描述网络结构，而非具体使用的传输方式或协议
骨干网一般都是广域网:作用范围几十到几千
公里

衡量网络性能的指标

带宽

速率

比特(bit，位)是计算机中数据量的单位，也是信息论中使用的信息量的单位。

速率即数据率(data rate)或比特率(bit rate)是连接在计算机网络上的主机在数字信道上传输数据的速率，是一个最重要的性能指标。速率的单位是 bps，kbps，Mbps，Gbps 等

速率往往是指额定速率或标称速率

带宽与位宽度

数字信号流随时间的变化：在时间轴上信 号的宽度随带宽的增大而变窄（位时间）

时延

发送时延

发送数据时，数据块从节点进入到传输媒体所需要的时间。

从发送数据块的第一个比特算起，到该数据块的最后一个比特发送完毕所需的时间。

传播时延

电磁波在信道中需要传播一定的距离而花费的时间。

信号传输速率（即发送速率）和信号在信道上的传播速率是完全不同的概念

处理时延

交换结点为存储转发而进行一些 必要的处理所花费的时间

排队时延

结点缓存队列中分组排队所经历的时延

排队时延的长短往往取决于网络中当时的通信量

数据经历的总时延

时延的产生

从结点 A 向结点 B 发送数据，四种时延所产生 的位置

吞吐量

吞吐量：每秒能够成功传输的数据量(瞬时、 平均)

吞吐量与带宽的区分：两者的单位都是bps.

英文：吞吐量:throughput 带宽: bandwidth

通信链路的带宽一般是指链路上每秒所能传送 的比特数，以太网的带宽是10Mbps

区分链路上的可用带宽与实际链路中每秒所能 传送的比特数（吞吐量），用“吞吐量”来表示 一个系统的测试性能

因为实现受各种低效率因素的影响，由一段带 宽为10Mbps的链路连接的一对节点可能只达到 2Mbps的吞吐量。

这样就意味着，一个主机上的应用能够以 2Mbps的速度向另外的一个主机发送数据。

每个连接的端到端吞吐量： min(Rc, Rs, R/10)

实际上 Rc 或 Rs 也可 能是瓶颈

因特网钟主机的通信过程

协议和层次体系结构

协议

协议是通信实体（如网络应用程序）之 间通信所必须遵守的规则

协议定义了在两个或多个通信实体之间 交换的报文格式和次序，以及在报文 传输和/或接收或其他事件方面所采取的 动作

协议的组成

语法：数据与控制信息的结构或格式

语义：需要发出何种控制信息，完成何种动作以及做出何种响应

同步：事件实现顺序的详细说明

分层体系结构

基本概念

实体、协议、服务和服务访问点
实体(Entity) 表示任何可发送或接收信息的硬件或软件进程。
协议是控制两个对等实体（Peer Entity）进行通信的规则的集合。
在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务。
要实现本层协议，还需要使用下层所提供的服务。

协议和服务

本层服务的实体只能看见服务而无法看见下 面的协议。

下面的协议对上面的服务用户是透明的。

协议是“水平的” ，即协议是控制对等实体之 间通信的规则。

服务是“垂直的” ，即服务是由下层向上层通 过层间接口提供的。

同一系统相邻两层的实体进行交互的地方， 称为服务访问点 SAP (Service Access Point)。

TCP/IP协议栈

封装

示例： 我要访问北邮的主页，通信过程是怎样的？

分层体系结构的要点

1. 网络体系结构分几层？每层的功能是什么？ 有哪些协议？
2. 不同系统的对等层实体遵守协议进行通信
3. 协议的实现需要下层的服务
4. 只有最底层是实际通信，其他各层都是虚拟通信，数据流向：U型
5. 除最底层之外，每层对于上层的数据进行封装（打包：增加包头/尾，包头/尾的格式和内容由协议规定）

2 应用层

网络应用概述

提供网络应用

编写应用程序

在不同的端系统上运行
通过网络和其他端系统通信
遵守特定的协议
示例：webserver软件和浏览器软件通信

无需修改网络核心软件

网络核心设备不运行网络应用程序
方便实现快速的应用开发和部署

应用层协议的内容

消息类型
例如：请求、应答
语法（Syntax）
消息中包含哪些字段，每个字段的长度
语义 (Semantics)
每个字段信息的含义
时序：消息的顺序

应用层协议的特点

面向用户，支持特定的网络应用

​ 没有通用的协议，每个应用有专门的协议！
​ 相比其他层，协议数量最多、最复杂

网络应用的体系结构

C/S 体系结构

服务器:
提供服务，同时处理多个客户请求
一直在线
地址(域名)公开，一般不变
可能有多个服务器(server farms)
一般需要高性能硬件支持

客户:
与服务器通信，使用服务
临时连接到网络
IP地址可能是动态的
客户之间不直接通信

P2P体系结构

Peer -to-Peer
没有严格的服务器 - 客户机之分 ，Peer
没 有 一 直 在 线 的 服 务 器 ， Peer 在 必 要 时 充 当 服 务 器
Peer 之 间 直 接 通 信
Peer 临 时 连 接 到 网 络 ， 且IP 地 址 可 能 动 态 变 化 可扩 展 、 成本低 ， 但难 于 管 理 、 有 安 全 隐 患

P2P文件下载：Peer之间互相传输文件

P2P: 如何查找资源

集中式：从索引服务器(Index Server)中查找资源，eg. Napster
分布式：洪泛查询(Query Flooding)，eg. Gnutella
分层叠加网，超级节点提供索引服务，
eg.KaZaA, freenet,chord

集中式查找：混合P2P

洪泛式（Flooding）查找

分层叠加网（Overlay Network）查找

C/S和P2P混合结构

进程通信

C/S模式的主机间进程通信

不同主机间通信的接口：Sockets

套接字
应用进程使用socket来发送/接收消息
应用编程接口（API）
位于应用层和传输层 之间
帮助应用访问系统内核（TCP/IP协议软件）
设置相关参数（如最大报文段长度MSS等）

Internet 上的每台主机都 有一个唯一的IP地址
Q: IP地址能唯一标识进程吗? A: 当然不行，一台主机中可能有多个进程在运行

通信关系与端口号

IP地址与端口号示例

网络应用对传输服务的要求：衡量指标

可靠性：数据丢失率

o 可容忍差错，如话音
o 不能容忍差错，如Email

实时性

o 端到端的时延

吞吐量 (Throughput)

o 端到端的带宽
o 音频数据: 5kbps-1Mbps
o 视频数据:10kbps-5Mbps

安全性

o 是否加密、是否验证用户身份、能否保证数据一致性

因特网的传输层服务

DNS

基本功能

IP地址的优点和缺点
IP地址更适合计算机处理，包含足够的路由信息。
IP地址不适合人们记忆
无法通过IP地址猜测主机的用途
如一个主机到底是www服务器还是FTP服务器？
如何取长补短——域名系统
优点：
使用方便，易于记忆。
一致性好，不会随IP地址的改变而改变。
采用分层结构的分布式数据库，ᨀ供主机名和IP地址映射的目录服务
允许主机查询分布式DNS数据库的应用层协议

DNS协议要点

采用C/S模型，Client请求，Server响应
客户端程序：resolver(解析器)
传输层采用UDP
DNS服务器的访问端口号是53
DNS是其他应用层协议的支撑协议

层次化的名字空间

主机域名的构成

主机名是由一系列由“.”分开的标签组成：

标签由英文字母和数字组成；
每个标签不能超过63个字符；
全部的标签不能超过255个字符；
书写顺序是从主机开始直到域名树的根域为止。例如：scss.bupt.edu.cn

域名是一个组织在域名空间中的名字

例如，北京邮电大学的域名为bupt.edu.cn。
该组织中已注册的主机都以组织的域名为后缀。

区域

是域名空间中的一部分（子树），从域名管理的角度来划分的，即DNS服务器的管辖范围是“区”
每一个区设置相应的权威服务器，用来保存该区中所有主机的域名到ip地址的映射

DNS服务器

根据DNS服务器的作用，可分为四类：

根域名服务器（Root Name Server）

o 为下级域名服务器提供域名解析服务；
它需要知道全部顶级域名服务器的地址。
o 数量很少，由于历史原因，主要分布在北美地区。

全球共有13个(a-m)
o 当用户无法在本地完成名字解析时，即访问根名字服务器
o 根名字服务器知道所有顶级名字服务器的IP地址
n 每个名字服务器均知道其下级名字服务器的地址
n 最终能访问到权威名字服务器，完成名字解析

顶级域名服务器（Top level Name Server）

o 负责管理该顶级域名服务器注册的所有二级域名。

权威域名服务器（Authoritative Name Server）

o 每台因特网中的主机都应该在所在域的域名服务器中注册，提供注册的域名服务器就是该主机的认证域名服务器。

企业网/校园网的DNS 服务器，提供主机名(如Web 服务器、Email 服务器的域名)与IP地址的权威映射
由企业网/校园网自己维护或ISP维护

本地域名服务器（Local Name Server）

o 当一个主机发出 DNS 查询请求时，这个查询请求报文就发送给本地域名服务器。

如果本地DNS 服务器找不到对应的映射关系，则将代理resolver去请求其他的名字服务器
本地DNS 服务器可能是企业网/校园网的DNS 服务器或ISP 的DNS 服务器

DNS解析

迭代查询

迭代查询过程
在无法完成域名解析时，本地DNS服务器询问根DNS 服务器
根DNS 服务器返回.edu域DNS 服务器的地址
本地DNS 服务器询问.edu域DNS 服务器
以此类推，最终请求权威DNS 服务器

递归查询

由被请求的名字服务器代理进行DNS查询
因特网中可选采用

DNS性能改进措施

主、备用服务器
定期把数据复制到备用服务器中，主服务器发生故障时，备用服务器代替工作

当DNS服务器收到一个新的DNS响应，会将域名和地址的映射关系缓存在本地
提高后续查找效率
缓存的映射数据在一段时间后过期
本地DNS服务器通常可以直接访问TLD 服务器，而不必访问根名字服务器

映射数据更新/通知机制

DNS资源记录

RR 格式: (name, TTL, class, type, value)

DNS协议消息

DNS协议包含**请求(query)和应答(reply)**两个消息， 其消息格式相同

消息头(12字节)

标识（ID）: 16位，一对请 求和应答消息使用同样的标识

标志（Flag）:
消息是请求或应答
是否使用递归查询
递归查询是否可行
应答是否是权威的

DNS的安全性问题

名字服务器易受攻击，名字数据库被非法主机
修改
n DNS伪冒(spoofing)
n DNS缓存毒化(Cache poisoning)
n DOS、缓存溢出(Buffer overrun)、重放(Replay)攻击…

o 改进策略：DNSSEC
n RFC 3090
n 数字签名、公共密钥
o 对DNS请求/应答消息进行身份认证

WWW应用和HTTP

❒万维网，WWW, World Wide Web
❒ 不是一个网络，而是基于因特网的信息服务系统
❒ 分布式超媒体系统(Hyper-media)
超媒体包括文本、图形、图像、音频、视频等多种媒体
❒ 以C/S模式工作
客户程序向服务器程序ᨀ出请求
服务器程序向客户程序返回客户需要的万维网文档，即页

WWW应用的客户端：浏览器

o WWW应用的用户接口
o 功能
n 向Web服务器发送请求消息
n 接收Web服务器的应答消息
n 解释网页文档的源代码，将网页呈现给用户
n 通用的客户端，支持Email、文件传输、BBS、电子商务等应用
o 不同的浏览器对于同一网页文件的呈现结果不同

WWW应用的服务器端：Web服务器

o 保存Web网页文档
o 接收客户端的请求消息
o 返回响应消息：状态信息和网页数据
o 可选功能
n 保存访问用户信息
n 对于访问用户进行身份认证
n 对于网页数据进行权限管理
n ……

WWW应用的编址：URL

统一资源定位符，唯一标识一个资源，对资源进行定位和访问

协议名 :// 主机: 端口号 /文件路径及文件名
例如：http://www.abc.com:8080/example/example.html

和网页上的链接相关联
缺省值：
n 协议名：http
n 端口号：80
n 文件名：index.html

网页类型

o静态网页（Static web page）
n 以文件形式保存
n 不同的用户、不同时间访问，返回结果均一样

o动态网页（Dynamic web page）
n 收到浏览器请求后，服务器端动态生成网页
n 示例：CGI脚本

o活跃网页（Active web page）
n 收到服务器响应后，客户端动态生成网页
n 示例：Java Applet

HTTP概述

o WWW的应用层协议
o 采用C/S模型
n 客户端浏览器： 发出HTTP请求，接收HTTP响应，向用户呈现网页
n Web服务器: 接收HTTP请求，返回HTTP响应（包含请求的网页数据）
o 传输层采用TCP
o 无状态（Stateless）协议
n 服务器端不保存以前的访问记录，对于每个请求都是单独处理

HTTP 的操作过程

(1) 浏览器分析超链接, 如 http://www.abc.com/example.html
(2) 浏览器使用通过DNS获得服务器(www.abc.com)的IP地址
(3) 浏览器建立到服务器的TCP连接
(4) 浏览器发送HTTP 请求： GET /example.html HTTP/1.0
(5) 服务器发送HTTP响应
(6) 释放TCP连接
(7) 浏览器显示网页example.html

非持久连接

RTT: Round Trip Time, 往返时间，time for a small packet to travel from client to server and back.(不包含发送时延)

响应时间:
1 ×RTT：建立TCP连接
1 ×RTT： 发送HTTP请求、返回HTTP响应
网页对象文件传输时间
响应时间 = 2 ×RTT+文件传输时间

持久连接

流水线

Client可以连续发出多个请求，而不必等待前一个请求的响应完成

HTTP消息的格式

HTTP有两类消息：请求（request）,响应（ response ）
❒ 消息格式：ASCII ，（易读）

请求消息

响应消息

Cookie

Web服务器对于访问用户的标识信息，可用于识别用户、记录用户信息和访问情况

Cookie涉及下列内容：

1. 在HTTP响应中包含一行set-cookie头信息
2. 在HTTP请求中包含一行cookie头信息
3. Client主机中保存一个cookie文件，由浏览器管理
4. Server端的后台数据库

示例： o 小王访问淘宝网站 o服务器收到初次访问请 求时，将增加小王的相关信息
唯一的ID 数据库的记录

Cookie: 用于保持访问状态

Cookie的特性

Cookie的应用：
o 身份认证
o 购物车
o 个性化的推荐信息
o 用户会话状态(Web e-mail)

代理服务器（Proxy Server）

目的：减轻Web服务器的负担，加快访问速度

在浏览器程序中设置 通过代理访问
浏览器将所有HTTP 请求均发送给代理
如果在代理中找到请求的 对象，则由代理返回响应
否则代理将请求转发给 要访问的Web Server， 由该Server 响应
代理缓存来自Web Server的网页对象

浏览器Caching： 浏览器缓存访问过的网页，进一步减少网络负载

缓存的更新：条件GET

3 网络层

网络层概述

实现了端到端（主机-主机）的数据传输

网络层的主要功能

路由选择
根据数据携带的目的主机地址为数据包选择一条的路径，以到达目的主机
主机/路由器编址
每个网络接口有一个唯一的IP地址
网络互联
在不同的网络之间转发数据，向传输层提供统一的数据传输
分段/重装
当数据包长度超过输出接口所连接的网络的限制时，应拆分成多个数据包

网络互联

从网络体系结构的层次观点来考察，网络互联
可在四个层次上实现：
n 物理层
n 数据链路层
n 网络层
n 网络层以上

物理层：中继器/集线器

在电缆段之间复制比特流
没有地址概念，本质上不是网络互连

数据链路层：网桥/交换机

LAN互联：在网段(segment)之间转发数据帧
根据数据帧中的信息（MAC地址）进行转发

网络层：路由器

网络层互联：在网络之间转发分组/包
根据分组中的逻辑地址（IP地址）进行转发

更高层：网关

连接不同体系结构或协议的网络
传输网络、应用网关

网络互联：小结

o 物理层：使用中继器或集线器在不同的电缆段之间复制位信号，无寻址功能；
o 数据链路层：使用网桥或交换机在局域网之间存储转发数据帧，用MAC地址寻址；
o 网络层：使用路由器在不同的网络之间存储转发分组，用IP地址寻址；
o 传输层及应用层：使用网关提供更高层次的互连，用端口号或其他特定标识寻址。

源主机网络层的主要工作

将上层数据封装成IP包
查路由表选择路由

路由器网络层的主要工作

查路由表选择路由
IP包转发

目的主机网络层的主要工作

检查目的地址，确认是自己
处理IP包头，将数据交给上层

网络层提供的服务

屏蔽底层网络的差异，向传输层提供一致的服务

虚电路网络

虚电路网络提供面向连接的服务
n 借鉴了电路交换的优点
n 发送数据之前，源主机和目的主机之间首先要建立一条虚连接（逻辑连接）
n 数据无丢失、重复和失序
n 示例：分组交换网X.25、ATM

面向连接

数据传输过程分为三阶段：建立虚连接、传输数据、拆除虚连接
虚电路表
输入接口、输入VCI（虚电路标识，局部有效）
输出接口、输出VCI（虚电路标识，局部有效）

输入接口和输入VCI唯一标识一条虚电路，后续的数据报只需携带VCI，无需携带完整的目的地址

A 发送给 B 的所有分组都沿着同一条虚电路传送

数据报网络

无连接
路由器对于每个输入的数据包单独进行处理
路由表包含了目的地址和输出接口的对应关系
每个数据包必须包含完整的目的地址
来自相同源节点和目的节点的两个数据报可能被转发到不同的接口，不保证顺序
对网络状况和目的主机状况一无所知，可能出现丢失

数据报网络的好处

由于传输网络不提供端到端的可靠传输服务，这就使网络中的路由器可以做得比较简单，而且价格低廉（与电信网的交换机相比较）。
如果主机（即端系统）中的进程之间的通信需要是可靠的，那么就由网络的主机中的传输层负责（包括差错处理、流量控制等）。
采用这种设计思路的好处是：网络的造价大大降低，运行方式灵活，能够适应多种应用。

H1 发送给 H2 的分组可能沿着不同路径传送

路由表示例

数据报 vs 虚电路

特点	数据报	虚电路
是否需要预先建立连接	不需要	需要
数据包中携带的地址	完整地址	较短的VCI
资源分配方式	动态分配	预先分配
路由选择	每个数据包都需要	只是在建立虚电路时
数据传输的可靠性	不可靠，数据包可能丢失、重复或失序	可靠
一对主机之间的数据流的传输路径	每个数据包的传输路径可能不同	一个虚连接上的所有数据包沿着同一路径传输
路由器或链路故障的影响	只影响正在处理的数据包	经过该路由器或链路的所有连接都需要重建
服务质量（QoS）保障	很难实现	通过在建立VC时申请足够资源，容易实现
拥塞控制	很难实现	容易实现

路由选择算法

根据数据包中携带的目的地址，为数据包在网络中选择一条路径，以到达目的主机

路由器查找路由表，完成选路

选路到下一跳（Next Hop，或输出接口），而不是完整路由

路由选择与转发
转发：将数据从路由器的输入接口转移到相应的输出接口
路由选择：根据路由表确定应转发到哪个输出接口的过程

确定/更新路由表的算法

理想的路由算法
算法必须是正确的和完整的。
算法在计算上应简单。
算法应能适应通信量和网络拓扑的变化，要有自适应性。
算法应具有稳定性。
算法应是公平的。
算法应是最佳的。

不存在一种绝对的最佳路由算法。

基于图论
节点：路由器
边：链路
权值：链路开销
路径长度
HOP数（跳数）
延迟时间

最短路由
总开销最小的路径

路由选择算法的分类

静态选路算法（非自适应选路算法）
路由表预先设定（不考虑网络当前状况）
路由表基本不变
一般不能保证是最佳路由

动态选路算法（自适应选路算法）
根据当前网络的拓扑结构和负载，（周期性）动态更新路由表

静态选路算法

o 固定路由表选路法
根据事先设置的静态路由表，查表选路

o 洪泛法（Flooding）
向除输入接口之外的所有接口转发

o 随机走动选路法
按概率随机选路

固定路由表选路法

静态路由表的生成：Dijakstra算法——Dijakstra的最短路径算法

o 求源节点到其他节点的最短路径和最小开销，即以源节点
为根的最短路径树(Shortest Path Tree, SPF)

o 算法原理
1）定义一个集合N，包含所有最短路径已确定的节点，在初始时，该集合中只包含一个源节点（设为S）
2）如果S和某个节点之间有一条边相连，距离就是该边上的权值；否则，距离值设为无穷大（∞）
3）从集合N外的节点中选择一个和S距离最小的节点（设为T）加入集合
4）重新计算S到其他集合N外的节点的距离，如果经过T的路径更短，则更新距离值
5）重复3-4步，直到所有节点都加入集合N

参考：https://www.bilibili.com/video/BV1H4411N7oD?p=93&vd_source=c75b11f1c6d9b809759edcc17586cf0d

静态选路算法：洪泛法

不计算路径，有路就走
路由器收到数据包后，向除了输入接口之外的所有接口转发

特点：

o 一个数据包将产生大量的副本（copy）
n 给网络增加大量负载

o 至少有一个副本将到达目的主机
n 健壮性强

o 至少有一个副本选择的是最优路由

o 所有的路由器都会收到副本
n 可用于传播路由信息

缺点：重复数据包多，浪费带宽
优点：可靠性高，路径最短，常用于军事

随机走动选路法

o 路由表中，一个表项有多条候选路由，路由器收到一个数据包时，按照预定的概率随机地选择其中一条路由
o 应用：无线网络

动态选路算法

自适应算法是动态的、分布式的算法
实现分布式算法的三要素： n 测量路由 n 更新路由信息的协议 n 计算路由开销

DVR：距离矢量选路算法 Distance Vector Routing

o 距离：两个节点间传输数据的开销
o 前提：每个路由器都知道自己到邻居节点的距离
o 动态选路：路由器通过周期性地与邻居节点交换路由信息
n 与谁交换：邻居节点
n 交换什么：路由表中的距离项（目的地、距离）
n 何时交换：周期性交换
o 各节点根据路由信息更新路由表

无穷计算问题

好消息传播得快，坏消息传播得慢

缺点

o 交换的路径信息量大
o 路径信息不一致
o 收敛速度慢（坏消息）
o 不适合大型网络

LSR：链路状态选路算法 Link State Routing

链路状态：链路连通/中断、链路开销
o 又称最短路径优先（SPF）选路
使用Dijkstra算法来计算最短路径
o 路由器发现自己和邻居节点的链路状态及开销
o 路由器之间通过交换路由信息，构造出全网的拓扑结构，并计算出到其他节点的最短路径
与谁交换：网络中的所有节点
交换什么：一个节点到各邻居节点的链路开销
何时交换：网络初启或链路状态变化时

链路状态算法（ L-S ）

基本思想：
o 发现它的邻接节点，并得到其网络地址
o 测量它到各邻接节点的延迟或开销
o 组装一个分组以告知它刚知道的所有信息
o 将这个分组发给所有其他路由器
o 计算到每个其他路由器的最短路径

发现邻接节点

当一个路由器启动后，向每个点到点线路发送 HELLO分组（携带自己的网络地址），另一端的路由器发送回来应答，通报其网络地址

测量线路开销

发送一个ECHO分组要求对方立即响应，通过测量RTT，再除以2，发送方就可以得到一个延迟估计值

如果要更精确，可以重复这一过程，取其平均值

构造链路状态包（LSP）

包含：源节点到其所有邻居节点（路由器）的线路开销测量值（即时延）

发布链路状态分组

用洪泛法向所有节点发布LSP，保证每个节点都能收到。
o 存在问题：
n 对于重复的LSP，路由器使用序号判断哪个LSP最新
n 如果序号循环使用，就会发生重复
n 如果一个路由器重启，序号将从0开始重新计数，但这些LSP会被当成过时包
n 如果序号发生错误，则很多LSP将被看成过时包

解决办法：序号+年龄

使用一个32位序号，即使每秒钟发送一个LSP包，137年才会循环一次
在每个LSP包中加一年龄字段（如初值为60），每秒钟将年龄值减1，为0后该包将被丢弃

计算新路由

用Dijkstra算法计算到每个节点的路由

L-S路由算法的优缺点

LSR的优点
n 路由信息的一致性好，坏消息也一样传播得快
n 状态分组的长度较短，仅包含到邻接点的距离、序号和年龄等，与网络规模关系不大，传输所耗用的网络带宽不大，此外，状态分组的扩散，由于年龄参数的设定，不会无限制扩散，所以可适用于大型网络

LSR的缺点
n 每个路由器需要有较大的存储空间，用以存储所收到的每一个节点的链路状态分组
n 计算工作量大，每次都必须计算最短路径

因特网的网络层协议

IP地址

给每个连接在因特网上的主机（或路由器）的 网络接口分配的全世界范围内唯一的 32 位标 识符

每个连接到网络的接口（如网卡）都有一个IP 地址
笔记本电脑的无线网卡和有线网卡各有一个IP地址

IP地址构成

网络号net-id +主机号host-id
n 网络号标识主机/路由器所连接到的网络，
n 主机号标识该主机/路由器
IP 地址 ::= { <网络号>, <主机号>}

地址划分有两类
n 分类编址：
Ø 单播地址分为A、B、C三类
Ø 网络号和主机号所占的比特个数不同
n 无类别编址

分类地址

点分十进制记法

各类网络的地址空间大小

IP 地址的一些重要特点

o IP 地址分网络号和主机号两个等级
n 地址管理机构（全球ICANN、我国CNNIC）在分配IP地址时只分配网络号，而主机号则由得到该网络号的单位自行分配，方便 IP 地址的管理
n 路由器仅根据目的主机的网络号来转发IP包（而不考虑目的主机号），减小了路由表中的表项数，从而减小了路由表所占的存储空间，且加快了查找速度
o IP地址用于标识一个网络接口
n 一台路由器（主机）连接到两个网络时，具有两个不同的IP地址，其网络号不同

特殊的IP地址

划分子网

o 属于一个单位内部的事情，对外仍然是一个网络
o 从主机号借用高若干位作为子网号 subnet-id，主机号
host-id 相应减少了若干位
IP地址 ::= {<网络号>, <子网号>, <主机号>}
o 从外网发给本网某个主机的IP包，仍然根据其目的网络地址，先找到连接本网的路由器；路由器收到 IP包后，再按目的网络地址转发到目的子网。
n 最后交付给目的主机

子网掩码

o 从一个 IP 包的包头无法判断源主机或目的主机所在网络的网络地址
o 使用子网掩码(subnet mask)可以找出 IP 地址中的网络号部分
o 子网掩码：特殊IP地址，网络号（包括子网号）部分为全1，主机号部分为全0
n 功能：获得网络地址
n 方法：将网内的任一个IP地址与子网掩码进行“按位与”操作，即得到该网络的地址