计算机网络

什么是Internet

• 运行应用程序

• 如Web、email

• 客户端向服务器请求、接收服务

• 没有专门的服务器

网络核心：电路交换

• 该呼叫采用了上面链路的第2 个线路，右边链路的第1个线路（piece）

• 独享资源：不同享
每个呼叫一旦建立起来就能够 保证性能
如果呼叫没有数据发送，被分配 的资源就会被浪费 (no sharing)
通常被传统电话网络采用k

• 链路带宽、交换能力

• 专用资源：不共享

• 保证性能

• 要求建立呼叫连

• 连接建立时间长

• 计算机之间的通信有突发性，如果使用线路交 换，则浪费的片较多
• 即使这个呼叫没有数据传递，其所占据的片也不能 够被别的呼叫使用

网络核心：分组交换

• 以分组为单位储存
• 网络带宽资源不再分分为一个个片，传输时使用全部带宽
• 主机之间传输的数据被分为一 个个分组

• 资源共享，按需使用
• 存储-转发：分组每次移 动一跳
• 在转发之前，节点必须收到 整个分组
• 延迟比线路交换要大
• 排队时间

• 适合于对突发式数据传输
• 资源共享
• 简单，不必建立呼叫

• 过度使用会造成网络拥塞：分组延时和丢失
• 对可靠地数据传输需要协议来约束：拥塞控制

• 分组交换: 分组的存储转发一段一段从源端传到目标端 ，按照有无网络层的连接，分为
1. 数据报网络
• 分组的目标地址决定下一跳
• 在不同的阶段，路由可以改变
2. 虚电路网络：
• 每个分组都带标签（虚电路标识 VC ID），标签决定下一跳
• 在呼叫建立时决定路径，在整个呼叫中路径保持不变
• 路由器维持每个呼叫的状态信息

数据报的工作原理

• 在通信之前,无须建立起一个连接,有数据就传输

• 每一个分组都独立路由(路径不一样,可能会失序)

• 路由器根据分组的目标地址进行路由

• 住宅接入：modem

• 接入网: digital subscriber line (DSL)

• 物理媒体：同轴电缆、光纤

网络结构和ISP

• ISPs (Internet Service Providers)：因特网服务提供商

• 中心：第一层ISP（如UUNet, BBN/Genuity, Sprint, AT&T）国家/国际覆盖，速率极高
• 直接与其他第一层ISP相吃连
• 与大量的第二层ISP和其他客户网络相连

• 第二层ISP: 更小些的 (通常是区域性的) ISP
• 与一个或多个第一层ISPs，也可能与其他第二层ISP

• 第三层ISP与其他本地ISP
• 接入网 (与端系统最近)

• ISP之间的连接
• POP：高层ISP面向客户网络的接入点，涉及费用结算
• 如一个低层ISP接入多个高层ISP，多宿（multi home）
• 对等接入：2个ISP对等互接，不涉及费用结算
• IXP：多个对等ISP互联互通之处，通常不涉及费用结算
• ICP：自己部署专用网络，同时和各级ISP连接

分组延时

• 通常是微秒数量级或更

• 取决于拥塞程度

• = L/R, 对低速率的链路而言很大（如拨号），通常为微秒级 到毫秒级

• 几微秒到几百毫秒

• 链路的队列缓冲区容量有限

• 当分组到达一个满的队列时，该分组将会丢失

• 丢失的分组可能会被前一个节点或源端系统重传，或根本不重传

• 瞬间吞吐量: 在一个时间点的速率

• 平均吞吐量: 在一个长时间内平均

• 瓶颈链路：端到端路径上，限制端到端吞吐的链路

协议层次

• 服务：低层实体向上层实体提供它们之间的通信的能力

• 原语（API）：上层使用下层服务的形式，高层使用低层提供的服务，以及低层向高层提供服务都是通过服务访问原语来进行交互的—形式

• 服务访问点 SAP (Services Access Point) ：上层使用下层提供的服务通过层间的接口—地点 Ps : 传输层端口SAP

• 服务(Service)：低层实体向上层实体提供它们之间的通信的能力，是通过原语(primitive)来操作的，垂直

• 协议(protocol) ：对等层实体(peer entity)之间在相互通信的过程中，需要遵循的规则的集合，水平

• 本层协议的实现要靠下层提供的服务来实现

• 本层实体通过协议为上层提供更高级

• 应用层: 网络应用
• 为人类用户或者其他应用进程提供网络应用服务
• FTP, SMTP, HTTP,DNS

• 传输层: 主机之间的数据传输
• 在网络层提供的端到端通信基础上，细分为进程到进程，将不可靠的通信变成可靠地通信
• TCP, UDP

• 网络层: 为数据报从源到目的选择路由
• 主机主机之间的通信，端到端通信，不可靠
• IP, 路由协议

• 链路层: 相邻网络节点间的数据传输
• 2个相邻2点的通信，点到点通信，可靠或不可靠
• 点对对协议PPP, 802.11(Wi-Fi), Ethernet

• 物理层: 在线路上传送bit

• 表示层: 允许应用解释传输的 数据 eg. 加密，压缩，机 器相关的表示转换

• 会话层: 数据交换的同步，检查点，恢复

• 应用层：报文(message)

• 传输层：报文段(segment)：TCP段，UDP数据报

• 网络层：分组packet（如果无连接方式：数据报 datagram）

• 数据链路层：帧(frame)

• 物理层：位(bit)

Internet历史

• 早期（1960年以前的）网络
• 线路交换网络
• 线路交换的特性使得其不适合计算机之间的通信
• 线路建立时间过长
• 独享方式占用通信资源，不适合突发性很强的计算机之间的通信
• 可靠性不高：非常不适合军事通信
• 三个小组独立地开展分组交换的研究

• 1961-1972: 早期的分组交换概念

• 1972-1980: 专用网络和网络互联

• 1980-1990: 体系结构变化, 网络数量激增，应用丰富

• 1990, 2000’s: 商业化, Web, 新的应用

• 2005-现在

小结

• 边缘：端系统（包括应用）+接入网

• 核心：网络交换设备+通信链路

• 协议：对等层实体通信过程中遵守的规则的集合
• 语法，语义，时序

• 应用

应用层

• 传输层的服务模型

• 客户-服务器模式

• 对等模式(peer-to-peer)

• 内容分发网络

应用架构

• 客户-服务器模式（C/S:client/server）

• 对等模式(P2P:Peer To Peer)

• 混合体：客户-服务器和对等体系

• 服务器: 一直运行 固定的IP地址和周知的端口号（约定） 扩展性：服务器场
• 数据中心进行扩展
• 扩展性差

• 客户端: 主动与服务器通信 与互联网有间歇性的连接 可能是动态IP 地址 不直接与其它客户

• （几乎）没有一直运行的服务器

• 任意端系统之间可以进行通信

• 每一个节点既是客户端又是服务器
• 自扩展性-新peer节点带来新的服务能力，当然也带来新的服务请求

• 参与的主机间歇性连接且可以改变IP 地址
• 难以管理
• 例子: Gnutella，迅雷

进程标示和寻址问题（服务用户）

• 对进程进行编址（addressing）

• 进程为了接收报文，必须有一个标识 即：SAP（发送也需要标示）
• 主机：唯一的 32位IP地址
• 仅仅有IP地址不能够唯一标示一个进程；在一台端系统上有很多应用进程在运行
• 所采用的传输层协议：TCP or UDP
• 端口号（Port Numbers）

• 一些知名端口号的例子：
• HTTP: TCP 80 Mail: TCP25 ftp:TCP 2

• 一个进程：用IP+port标示 端节点

• 本质上，一对主机进程之间的通信由2个端节点构成

传输层提供的服务-需要穿过层间的信息

传输层提供的服务-层间信息的代表

传输层提供的服务-层间信息代码

• 进程向套接字发送报文或从套接字接收报文

• 套接字 <-> 门户
• 发送进程将报文推出门户，发送进程依赖于传输层设施在另外一侧的门将报文交付给接受进程
• 接收进程从另外一端的门户收到报文（依赖于传输层设施)

如何使用传输层提供的服务实现应用

• 定义应用层协议：报文格式，解释，时序等

• 编制程序，通过API调用网络基础设施提供通信服务传报文，解析报文，实现应用时序等

应用层协议

• 定义了：运行在不同端系统上的应用进程如何相互交换报文
• 交换的报文类型：请求和应答报文
• 各种报文类型的语法：报文中的各个字段及其描述
• 字段的语义：即字段取值的含义
• 进程何时、如何发送报文及对报文进行响应的规则

• 应用协议仅仅是应用的一个组成部分
• Web应用：HTTP协议，web客户端，web服务器，HTML

• 如HTTP, SMTP

• 如：Skype

UDP存在的必要性

• 能够区分不同的进程，而IP服务不能
• 在IP提供的主机到主机端到端功能的基础上，区分了主机的应用进程

• 无需建立连接，省去了建立连接时间，适合事务性的应用

• 不做可靠性的工作，例如检错重发，适合那些对实时性要求比较高而对正确性要求不高的应用
• 因为为了实现可靠性（准确性、保序等），必须付出时间代 价（检错重发）

• 没有拥塞控制和流量控制，应用能够按照设定的速度发送数据
• 而在TCP上面的应用，应用发送数据的速度和主机向网络发送的实际速度是不一致的，因为有流量控制和拥塞控制

Web 与 HTTP

• 购物车

• 推荐

• 用户状态 (Web e-mail)

• Cookies允许站点知道许多关于用户的信息

• 可能将它知道的东西卖给第三方

• 使用重定向和cookie的搜索引擎还能知道用户更多的信息

• 如通过某个用户在大量站点上的行为，了解其个人浏览方式的大致模式

• 广告公司从站点获得信息

• 协议端节点：在多个事务上，发送端和接收端维持状态

• cookies: http报文携带状态信息

• 用户设置浏览器： 通过缓存访问Web

• 浏览器将所有的HTTP请求发给缓存
• 在缓存中的对象：缓存直接返回对象
• 如对象不在缓存，缓存请求原始服务器，然后再将对象返回给客户端

• 缓存既是客户端又是服务器

• 通常缓存是由ISP安装 (大学、公司、居民区ISP)

为什么要使用Web缓存

• 降低客户端的请求响应时间

• 可以大大减少一个机构内部网络与Internet接入链路上的流量

• 互联网大量采用了缓存： 可以使较弱的ICP也能够有效提供内容

Ps. 百分之八十的人访问了百分之二十的互联网内容，提高运输层带宽的成本远远高于部署Web本地缓存服务器

FTP与Email

• 向远程主机上传输文件或从远程主机接收文件

• 客户/服务器模式
• 客户端：发起传输的一方
• 服务器：远程主机

• ftp: RFC 959

• ftp服务器：端口号为21

• FTP客户端与FTP服务器通过端口21联系，并使用TCP为传输协议

• 客户端通过控制连接获得身份确认

• 客户端通过控制连接发送命令浏览远程目录

• 收到一个文件传输命令时，服务器打开一个到客户端的数据连接

• 一个文件传输完成后，服务器关闭连接

• 服务器打开第二个TCP数据连接用来传输另一个文件

• 控制连接： 带外（ “out of band” ）传送

• FTP服务器维护用户的状态信息：当前路径、用户帐户与控制连接对应

• 使用TCP在客户端和服务器之间传送报文，端口号为25

• 直接传输：从发送方服务器到接收方服务器

• 传输的3个阶段
• 握手
• 传输报文
• 关闭

• 命令/响应交互
• 命令：ASCII文本
• 响应：状态码和状态信息

• 报文必须为7位ASCII

特点

• SMTP使用持久连接

• SMTP要求报文（首部和主体）为7位ASCII编码

• SMTP服务器使用CRLF.CRLF决定报文的尾部

• MIME：多媒体邮件扩展（multimedia mail extension）, RFC 2045, 2056

• 在报文首部用额外的行申明MIME内容类

DNS

DNS系统需要解决的问题

• 问题1：如何命名设备
• 用有意义的字符串：好记，便于人类用使用
• 解决一个平面命名的重名问题：层次化命名

• 问题2：如何完成名字到IP地址的转换
• 分布式的数据库维护和响应名字查询

• 问题3：如何维护：增加或者删除一个域，需要在域名系统中做哪些工作

• ARPANET的名字解析解决方案
• 主机名：没有层次的一个字符串（一个平面）
• 存在着一个（集中）维护站：维护着一张 主机名-IP地址的映射文件：Hosts.txt
• 每台主机定时从维护站取文件

• ARPANET解决方案的问题

• 当网络中主机数量很大时

• 没有层次的主机名称很难分配

• 文件的管理、发布、查找都很麻烦

• DNS的主要思路
• 分层的、基于域的命名机制
• 若干分布式的数据库完成名字到IP地址的转换
• 运行在UDP之上端口号为53的应用服务
• 核心的Internet功能，但以应用层协议实现  在网络边缘处理复杂性

• DNS主要目的：
• 实现主机名-IP地址的转换(name/IP translate)
• 其它目的
• 主机别名到规范名字的转换：Host aliasing
• 邮件服务器别名到邮件服务器的正规名字的转换：Mail server aliasing
• 负载均衡：Load Distribution

• 域名的管理
• 一个域管理其下的子域 .jp 被划分为 ac.jp co.jp
.cn 被划分为 edu.cn com.cn
• 创建一个新的域，必须征得它所属域的同意

• 域与物理网络无关
• 域遵从组织界限，而不是物理网络
• 一个域的主机可以不在一个网络
• 一个网络的主机不一定在一个域
• 域的划分是逻辑的，而不是物理

• 一个名字服务器的问题
• 可靠性问题：单点故障
• 扩展性问题：通信容量
• 维护问题：远距离的集中式数据库

• 区域(zone)
• 区域的划分有区域管理者自己决定
• 将DNS名字空间划分为互不相交的区域，每个区域都是树的一部分
• 名字服务器：
• 每个区域都有一个名字服务器：维护着它所管辖区域的权威信息(authoritative record)
• 名字服务器允许被放置在区域之外，以保障可靠

• 顶级域(TLD)服务器：负责顶级域名（如com, org, net, edu和gov）和所有国家级的顶级域名（如cn, uk, fr, ca, jp ）
• Network solutions 公司维护com TLD服务器
• Educause公司维护edu TLD服务器

• 资源记录(resource records)
• 作用：维护 域名-IP地址(其它)的映射关系
• 位置：Name Server的分布式数据库中

• RR格式: (domain_name, ttl, type,class,Value)
• Domain_name: 域名
• Ttl: time to live : 生存时间(权威，缓冲记录)
• Class 类别 ：对于Internet，值为IN
• Value 值：可以是数字，域名或ASCII串
• Type 类别：资源记录的类型—见下页

• 并不严格属于层次结构

• 每个ISP (居民区的ISP、公司、大学）都有一个本地DNS服务器
• 也称为“默认名字服务器”

• 当一个主机发起一个DNS查询时，查询被送到其本地DNS服务器
• 起着代理的作用，将查询转发到层次结构中

• 名字解析过程
• 目标名字在Local Name Server中
• 情况1：查询的名字在该区域内部
• 情况2：缓存(cashing)

• 名字解析负担都放在当前联络的名字服务器上

• 问题：根服务器的负担太重

• 解决： 迭代查询(iterated queries)

• 主机cis.poly.edu 想知道主机 gaia.cs.umass.edu的IP地址
• 根（及各级域名）服务器返回的不是查询结果，而是下一个NS的地址
• 后由权威名字服务器给出解析结果
• 当前联络的服务器给出可以联系的服务器的名字
“我不知道这个名字，但可以向这个服务器请求”

• 一旦名字服务器学到了一个映射，就将该映射缓存起来

• 根服务器通常都在本地服务器中缓存着
• 根服务器不用经常被访问

• 目的：提高效率

• 可能存在的问题：如果情况变化，缓存结果和权威资源记录不一致

• 解决方案：TTL（默认2天）

• 在上级域的名字服务器中增加两条记录，指向这个新增的子域的域名和域名服务器的地址

• 在新增子域 的名字服务器上运行名字服务器，负责本域的名字解析： 名字->IP地址 例子：在com域中建立一个“Network Utopia”

• 到注册登记机构注册域名networkutopia.com
• 需要向该机构提供权威DNS服务器（基本的、和辅助的）的名字和IP地址
• 登记机构在com TLD服务器中插入两条RR记录: (networkutopia.com,dns1.networkutopia.com, NS) (dns1.networkutopia.com, 212.212.212.1, A)

• 在networkutopia.com的权威服务器中确保有
• 用于Web服务器的 www.networkuptopia.com 的类型为A的记录
• 用于邮件服务器mail.networkutopia.com的类型为MX的记

P2P应用

• 没有（或极少）一直运行的服务器

• 任意端系统都可以直接通信

• 利用peer的服务能力

• Peer节点间歇上网，每次IP地址都有可能变化

从一台服务器分发文件（大小F）到N个peer需要多少时间？

• 发送一个copy: F/Us

• 发送N个copy： NF/Us

• 客户端: 每个客户端必须下载一个文件拷贝

• d(min) = 客户端最小的下载速率

• 下载带宽最小的客户端下载的时间：F/d(min)

• 服务器传输：最少需要上载一份拷贝
• 发送一个拷贝的时间：F/us

• 客户端: 每个客户端必须下载一个拷贝
• 最小下载带宽客户单耗时：: F/dmin

• 客户端: 所有客户端总体下载量NF
• 最大上载带宽是：us+Sui
• 除了服务器可以上载，其他所有的peer节点都可以上载

• 文件被分为一个个块256KB

• 网络中的这些peers发送接收文件块，相互服务

• Peer加入torrent:
• 一开始没有块，但是将会通过其他节点处累积文件块
• 向跟踪服务器注册，获得peer节点列表，和部分peer节点构成邻居关系 (“连接”)

• 当peer下载时，该peer可以同时向其他节点提供上载服务

• Peer可能会变换用于交换块的peer节点

• 扰动churn: peer节点可能会上线或者下线

• 一旦一个peer拥有整个文件，它会（自私的）离开或者保留（利他主义）在torrent中

BitTorrent: tit-for-tat

1. Alice “优化疏通” Bob

2. Alice 变成了Bob的前4位提供者; Bob答谢Alice

3. Bob 变成了Alice的前4提供者

两大问题：

• 如何定位所需资源

• 如何处理对等方的加入与离开

可能的方案

• 集中

• 分散

• 半分散

存在的问题：文件传输是分散的，而定位内容则是高度集中的

• 单点故障

• 性能瓶颈

• 侵犯版权

• 全分布式
• 没有中心服务器

• 开放文件共享协议

• 许多Gnutella客户端实现了Gnutella协议
• 类似HTTP有许多的浏览器

1. X接着试图与该列表上的对等方建立TCP连接，直到与某个对等方Y建立连接

2. X向Y发送一个Ping报文，Y转发该Ping报文

3. 所有收到Ping报文的对等方以Pong报文响应IP地址、共享文件的数量及总字节数

4. X收到许多Pong报文，然后它能建立其他TCP连接

• 每个对等方要么是一个组长，要么隶属于一个组长
• 对等方与其组长之间有TCP连接
• 组长对之间有TCP连接

• 组长跟踪其所有的孩子的内容

• 组长与其他组长联系
• 转发查询到其他组长
• 获得其他组长的数据拷贝

• 每个文件有一个散列标识码和一个描述符

• 客户端向其组长发送关键字查询

• 组长用匹配进行响应：
• 对每个匹配：元数据、散列标识码和IP地址

• 如果组长将查询转发给其他组长，其他组长也可以匹配进行响应

• 客户端选择要下载的文件
• 向拥有文件的对等方发送一个带散列标识码的HTTP请求

• 请求排队
• 限制并行上载的数量
• 确保每个被传输的文件从上载节点接收一定量的带宽

• 激励优先权
• 鼓励用户上载文件
• 加强系统的扩展性

• 并行下载
• 从多个对等方下载同一个文件的不同部分
• HTTP的字节范围首部
• 更快地检索

Distributed Hash Table (DHT)

• 哈希表

• DHT方案

• 环形DHT以及覆盖网络

• Peer波

CDN

• DASH: Dynamic, Adaptive Streaming over HTTP

• 服务器:
• 将视频文件分割成多个块
• 每个块独立存储，编码于不同码率（8-10种）
• 告示文件（manifest file）: 提供不同块的URL

• 客户端:
• 先获取告示文件
• 周期性地测量服务器到客户端的带宽
• 查询告示文件,在一个时刻请求一个块，HTTP头部指定字节范围
• 如果带宽足够，选择最大码率的视频块
• 会话中的不同时刻，可以切换请求不同的编码块 (取决于当时的可用带宽)

• “智能”客户端: 客户端自适应决定
• 什么时候去请求块 (不至于缓存挨饿，或者溢出)
• 请求什么编码速率的视频块 (当带宽够用时，请求高质量的视频块)
• 哪里去请求块 (可以向离自己近的服务器发送URL，或者向高可用带宽的服务器请求)

服务器如何通过网络向上百万用户同时流化视频内容?

• CDN: 在CDN节点中存储内容的多个拷贝 • e.g. Netflix stores copies of MadMen

• 用户从CDN中请求内容 • 重定向到最近的拷贝，请求内容 • 如果网络路径拥塞，可能选择不同的拷贝

• 从哪个CDN节点中获取内容？–最近的

• 用户在网络拥塞时的行为？

• 在哪些CDN节点中存储什么内容？

套接字编程

TCP套接字

UDP套接字

• 没有握手 • 发送端在每一个报文中明确地指定目标的IP地址和端口号 • 服务器必须从收到的分组中提取出发送端的IP地址和端口号

传输层

传输服务和协议

• 为运行在不同主机上的应用进程提供逻辑通信

• 传输协议运行在端系统
• 发送方：将应用层的报文分成报文段，然后传递给网络层
• 接收方：将报文段重组成报文，然后传递给应用层

• 有多个传输层协议可供应用选择
• Internet: TCP和UDP

• 网络层服务：主机之间的逻辑通信

• 传输层服务：进程间的逻辑通信

• 依赖于网络层的服务
• 延时、带宽

• 并对网络层的服务进行增强
• 数据丢失、顺序混乱、加密

• 可靠的、保序的传输： TCP
• 多路复用、解复用
• 拥塞控制
• 流量控制
• 建立连接

• 不可靠、不保序的传输：UDP
• 多路复用、解复用
• 没有为尽力而为的IP服务添加更多的其它额外服务

• 都不提供的服务：
• 延时保证
• 带宽保证

多路复用/解复用

• 解复用作用：TCP或者UDP实体采用哪些信息，将报文段的数据部分交给正确的socket，而交给正确的进程

• 主机收到IP数据报
• 每个数据报有源IP地址和目标地址
• 每个数据报承载一个传输层报文段
• 每个报文段有一个源端口号和目标端口号(特定应用有著名的端口号)

• 主机联合使用IP地址和端口号将报文段发送给合适的套接字

• 创建套接字： 服务器端： serverSocket=socket(PF_INET, SOCK_DGRAM,0); bind(serverSocket, &sad, sizeof(sad)); serverSocket和Sad指定的端口号捆绑
客户端： ClientSocket=socket(PF_INET, SOCK_DGRAM,0); 没有Bind,ClientSocket和OS为之分配的某个端口号捆绑（客户端使用什么端口号无所谓，客户端主动找服务器）

• 在接收端，UDP套接字用二元组标识 (目标IP地址、目标端口号)

• 当主机收到UDP报文段：
• 检查报文段的目标端口号
• 用该端口号将报文段定位给套接字

• 如果两个不同源IP地址/源端口号的数据报，但是有相同的目标IP地址和端口号，则被定位到相同的套接字

• 当主机接收到UDP段时：
• 检查UDP段中的目标端口号
• 将UDP段交给具备那个端口号的套接字

• TCP套接字:四元组本地标识：
• 源IP地址
• 源端口号
• 目的IP地址
• 目的端口号

• 解复用：接收主机用这四个值来将数据报定位到合适的套接字

• 服务器能够在一个TCP端口上同时支持多个TCP套接字：
• 每个套接字由其四元组标识（有不同的源IP和源PORT）

• Web服务器对每个连接客户端有不同的套接字
• 非持久对每个请求有不同的套接字

• 一个进程下面可能有多个线程：由多个线程分别为客户提供服务

• 在这个场景下，还是根据4元组决定将报文段内容同一个进程下的不同线程

• 解复用到不同线

无连接传输：UDP

• “no frills,” “bare bones”Internet传输协议

• “尽力而为”的服务，报文段可能
• 丢失
• 送到应用进程的报文段乱序

• 无连接：
• UDP发送端和接收端之间没有握手
• 每个UDP报文段都被独立地处理

• UDP 被用于:
• 流媒体（丢失不敏感，速率敏感、应用可控制传输速率
• DNS
• SNMP

• 在UDP上可行可靠传输:
• 在应用层增加可靠性
• 应用特定的差错恢复

• 目标端：校验范围+校验和=1111111111111111 通过校验
• 否则没有通过校验 注：求和时，必须将进位回卷到结果上

可靠数据传输（rdt）的原理

• rdt在应用层、传输层和数据链路层都很重要

• 是网络Top 10问题之一

• 信道的不可靠特点决定了可靠数据传输协议（ rdt ）的复杂性

• 下层的信道是完全可靠的
• 没有比特出错
• 没有分组丢失

• 发送方和接收方的FSM
• 发送方将数据发送到下层信道
• 接收方从下层信道接收数据

发送方发送一个分组，然后等待接收方的应答

• 功能同rdt2.1，但只使用ACK(ack 要编号）

• 接收方对最后正确接收的分组发ACK，以替代NAK
• 接收方必须显式地包含被正确接收分组的序号

• 当收到重复的ACK（如：再次收到ack0）时，发送方与收到NAK采取相同的动作：重传当前分组

• 为后面的一次发送多个数据单位做一个准备
• 一次能够发送多个
• 每一个的应答都有：ACK，NACK；麻烦
• 使用对前一个数据单位的ACK，代替本数据单位的nak
• 确认信息减少一半，协议处理简单

• 过早超时（延迟的ACK）也能够正常工作；但是效率较低，一半的分组和确认是重复的；

• 设置一个合理的超时时间也是比较重要的

• rdt3.0可以工作，但链路容量比较大的情况下，性能很差
• 链路容量比较大，一次发一个PDU 的不能够充分利用链路的传输能力

• 例：1 Gbps的链路，15 ms端-端传播延时，分组大小为1kB

• U sender：利用率 – 忙于发送的时间比例

• 每30ms发送1KB的分组 -> 270kbps=33.75kB/s 的吞吐量（在1 Gbps 链路上）

• 瓶颈在于：网络协议限制了物理资源

• 增加n,能提高链路利用率

• 但当达到某个n,其u=100%时,无法再通过增加n，提高利用率

• 瓶颈转移了->链路带宽

• 两种通用的流水线协议：回退

• 发送缓冲区
• 形式：内存中的一个区域，落入缓冲区的分组可以发送
• 功能：用于存放已发送，但是没有得到确认的分组
• 必要性：需要重发时可用

• 发送缓冲区的大小：一次最多可以发送多少个未经确认的分组
• 停止等待协议=1
• 流水线协议>1，合理的值，不能很大，链路利用率不能够超100%

• 发送缓冲区中的分组
• 未发送的：落入发送缓冲区的分组，可以连续发送出去;
• 已经发送出去的、等待对方确认的分组：发送缓冲区的分组只有得到确认才能删除

• 发送窗口：发送缓冲区内容的一个范围
• 那些已发送但是未经确认分组的序号构成的空间

• 发送窗口的最大值<=发送缓冲区的值

• 一开始：没有发送任何一个分组
• 后沿=前沿
• 之间为发送窗口的尺寸=0

• 每发送一个分组，前沿前移一个单位

• 发送窗口前沿移动的极限：不能够超过发送缓冲区

• 发送窗口前沿移动的极限：不能够超过发送缓冲区

• 发送窗口后沿移动
• 条件：收到老分组的确认
• 结果：发送缓冲区罩住新的分组，来了分组可以发送
• 移动的极限：不能够超过前沿

• 发送窗口后沿移动
• 条件：收到老分组(后沿)的确认
• 结果：发送缓冲区罩住新的分组，来了分组可以发送
• 移动的极限：不能超过前沿

• 滑动窗口技术
• 发送窗口 (sending window)

• 接收窗口 (receiving window)=接收缓冲区

• 接收窗口用于控制哪些分组可以接收；
• 只有收到的分组序号落入接收窗口内才允许接收
• 若序号在接收窗口之外，则丢弃；

• 接收窗口尺寸Wr=1，则只能顺序接收；

• 接收窗口尺寸Wr>1 ，则可以乱序接收
• 但提交给上层的分组，要按序

• 例子：Wr＝1，在0的位置；只有0号分组可以接收；向前滑动一个，罩在1的位置，如果来了第2号分组，则丢弃

• 接收窗口的滑动和发送确认
• 滑动：
• 低序号的分组到来，接收窗口移动
• 高序号分组乱序到，缓存但不交付（因为要实现rdt，不允许失序），不滑动
• 发送确认：
• 接收窗口尺寸=1：发送连续收到的最大的分组确认（累计确认）
• 接收窗口尺寸>1：到分组，发送那个分组的确认（非累计确认）

• 相同之处
• 发送窗口>1
• 一次能够可发送多个未经确认的分组

• 不同之处
• GBN :接收窗口尺寸=1
• 接收端：只能顺序接收
• 发送端：从表现来看，一旦一个分组没有发成功，如：0,1,2,3,4,1未成功，234都发送出去了，要返回1再发送；GB1

• SR: 接收窗口尺寸>1
• 接收端：可以乱序接收
• 发送端：发送0,1,2,3,4，一旦1未成功，2,3,4,已发送，无需重发，选择性发送1

• 接收方对每个正确接收的分组，分别发送ACKn（非累积确认）
• 接收窗口>1
• 可以缓存乱序的分组
• 终将分组按顺序交付给上层

• 发送方只对那些没有收到ACK的分组进行重发-选择性重发
• 发送方为每个未确认的分组设定一个定时器

• 发送窗口的最大值（发送缓冲区）限制发送未确认分组的个数

面向连接的传输： TCP

• 点对点：
• 一个发送方，一个接收方

• 可靠的、按顺序的字节流：
• 没有报文边界

• 管道化（流水线）：
• TCP拥塞控制和流量控制设置窗口大小

• 发送和接收缓存

• 全双工数据：
• 在同一连接中数据流双向流动
• MSS：最大报文段大小

• 面向连接：
• 在数据交换之前，通过握手（交换控制报文） 初始化发送方、接收方的状态变量

• 有流量控制：
• 发送方不会淹没接收方

• 期望从另一方收到的下一个字节的序号

• 累积确认

• 指数加权移动平均

• 过去样本的影响呈指数衰减

• 推荐值：α = 0.125

• TCP在IP不可靠服务的基础上建立了rdt
• 管道化的报文段
• GBN or SR
• 累积确认（像GBN）
• 单个重传定时器（像GBN）
• 是否可以接受乱序的，没有规范

• 通过以下事件触发重传
• 超时（只重发那个最早的未确认段：SR）
• 重复的确认
• 例子：收到了ACK50,之后又收到3个ACK50

• 首先考虑简化的TCP发送方：
• 忽略重复的确认
• 忽略流量控制和拥塞控制

• 超时周期往往太长：
• 在重传丢失报文段之前的延时太长

• 通过重复的ACK来检测报文段丢失
• 发送方通常连续发送大量报文段
• 如果报文段丢失，通常会引起多个重复的ACK

• 如果发送方收到同一数据的3个冗余ACK，重传最小序号的段：
• 快速重传：在定时器过时之前重发报文段
• 它假设跟在被确认的数据后面的数据丢失了
• 第一个ACK是正常的
• 收到第二个该段的ACK，表示接收方收到一个该段后的乱序段 收到第3，4个该段的ack，表示接收方收到该段之后的2个，3个乱序段，可能性非常大段丢失了

• 接收方在其向发送方的TCP段头部的rwnd字段“通告”其空闲buffer大小
• RcvBuffer大小通过socket选项设置 (典型默认大小为4096 字节)
• 很多操作系统自动调整RcvBuffer

• 发送方限制未确认(“in-flight”)字节的个数≤接收方发送过来的 rwnd 值

• 保证接收方不会被淹没

• 客户端，服务器分别关闭它自己这一侧的连接
• 发送FIN bit = 1的TCP段

• 一旦接收到FIN，用ACK回应
• 接到FIN段，ACK可以和它自己发出的FIN段一起发送

• 可以处理同时的FIN交

拥塞控制原理拥塞控制原理

• 非正式的定义: “太多的数据需要网络传输，超过了网络的处理能力”

• 与流量控制不同

• 拥塞的表现:
• 分组丢失 (路由器缓冲区溢出)
• 分组经历比较长的延迟(在路由器的队列中排队)

• 网络中前10位的问题!

• 2个发送端，2个接收端

• 一个路由器，具备无限大的缓冲

• 输出链路带宽：R

• 没有重传

• 一个路由器，有限的缓冲

• 分组丢失时，发送端重传
• 应用层的输入=应用层输出:λlin = λout
• 传输层的输入包括重传: λin>=λin

• 只在缓冲可用时发送

• 不会丢失:λ’in=λin

• 4个发送端

• 多重路径

• 超时/重传

• 当分组丢失时，任何“关于这个分组的上游传输能力” 都被浪费了

• 在RM信元中的2个字节 ER (explicit rate)字段
• 拥塞的交换机可能会降低信元中ER的值
• 发送端发送速度因此是最低的可支持速率

• 数据信元中的EFCI bit: 被拥塞的交换机设置成1
• 如果在管理信元RM前面的数据信元EFC被设置成了1, 接收端在返回的RM信元中设置CI bit

TCP 拥塞控制：机制

• 端到端的拥塞控制机制

• 路由器不向主机有关拥塞的反馈信息
• 路由器的负担较轻
• 符合网络核心简单的TCP/IP架构原则

• 端系统根据自身得到的信息，判断是否发生拥塞，从而采取动作

• 某个段超时了（丢失事件 ）：拥塞
• 超时时间到，某个段的确认没有来
• 原因1：网络拥塞（某个路由器缓冲区没空间了，被丢弃）概率大
• 原因2：出错被丢弃了（各级错误，没有通过校验，被丢弃）概率小
• 一旦超时，就认为拥塞了，有一定误判，但是总体控制方向是对的

• 有关某个段的3次重复ACK：轻微拥塞
• 段的第1个ack，正常，确认绿段，期待红段
• 段的第2个重复ack，意味着红段的后一段收到了，蓝段乱序到达
• 段的第2、3、4个ack重复，意味着红段的后第2、3、4个段收到了，橙段乱序到达，同时红段丢失的可能性很大（后面3个段都到了，红段都没到）
• 网络这时还能够进行一定程度的传输，拥塞但情况要比第一种好

• CongWin是动态的，是感知到的网络拥塞程度的函数
• 超时或者3个重复ack，CongWin↓
• 超时时：CongWin降为1MSS,进入SS阶段然后再倍增到CongWin/2（每个RTT），从而进入CA阶段
• 3个重复ack ：CongWin降为CongWin/2,CA阶段
• 否则（正常收到Ack，没有发送以上情况）：CongWin跃跃欲试↑
• SS阶段：加倍增加(每个RTT)
• CA阶段：线性增加(每个RTT)

• 发送端控制发送但是未确认的量同时也不能够超过接收窗口，满足流量控制要求
• SendWin=min{CongWin, RecvWin}
• 同时满足 拥塞控制和流量控

• 慢启动

• AIMD：线性增、乘性减少

• 超时事件后的保守策略

• 连接刚建立, CongWin = 1 MSS
• 如: MSS = 1460bytes & RTT = 200 msec
• 初始速率 = 58.4kbps

• 可用带宽可能>> MSS/RTT
• 应该尽快加速，到达希望的速率

• 当连接开始时，指数性增加发送速率，直到发生丢失的事件
• 启动初值很低
• 但是速度很快

• 当连接开始时，指数性增加（每个RTT）发送速率直到发生丢失事件
• 每一个RTT， CongWin加倍
• 每收到一个ACK时，CongWin加1（why）
• 慢启动阶段：只要不超时或3个重复ack，一个RTT， CongWin加倍

• 总结: 初始速率很慢，但是加速却是指数性的
• 指数增加，SS时间很短，长期来看可以忽略

• 当收到3个重复的ACKs:
• CongWin 减半
• 窗口（缓冲区大小）之后线性增长

• 当超时事件发生时:

• CongWin被设置成 1 MSS，进入SS阶段

• 之后窗口指数增长

• 增长到一个阈值（上次发生拥塞的窗口的一半）时，再线性增加 思路

• 3个重复的ACK表示网络还有一定的段传输能力

• 超时之前的3个重复的ACK表示“警报”

Q:什么时候应该将指数性增长变成线性？

• 当CongWin＜Threshold, 发送端处于慢启动阶段（slow-start）, 窗口指数性增长.

• 当CongWin〉Threshold, 发送端处于拥塞避免阶段（congestion-avoidance）, 窗口线性增长.

• 当收到三个重复的ACKs (triple duplicate ACK),Threshold设置成 CongWin/2， CongWin=Threshold+3.

• 当超时事件发生时timeout, Threshold=CongWin/2CongWin=1 MSS，进入SS阶段

• TCP的平均吞吐量是多少，使用窗口window尺寸W和RTT来描述?
• 忽略慢启动阶段，假设发送端总有数据传输

• W：发生丢失事件时的窗口尺寸（单位：字节）
• 平均窗口尺寸（#in-flight字节）：3/4W
• 平均吞吐量：RTT时间吞吐3/4

• > L = 2·10-10 （为了达到10Gbps的吞吐，平均50亿段丢失一个） 非常非常小的丢失率！可能远远低于链路的物理丢失率，达不到的

• 网络带宽增加，需要更新的TCP版本!

网络层

数据平面与控制平面

• 在发送主机和接收主机对之间传送段（segment）

• 在发送端将段封装到数据报中

• 在接收端，将段上交给传输层实体

• 网络层协议存在于每一个主机和路由器

• 路由器检查每一个经过它的IP数据报的头部

• 决定从路由器输入端口到达的分组如何转发到输出端口

• 转发功能：
• 传统方式：基于目标地址+转发表
• SDN方式：基于多个字段+流表 控制平面

• 网络范围内的逻辑

• 决定数据报如何在路由器之间路由，决定数据报从源到目标主机之间的端到端路径

• 2个控制平面方法:

路由器组成

• 根据数据报头部的信息如：目的地址，在输入端口内存中的转发表中查找合适的输出端口（匹配+行动）

• 基于目标的转发：仅仅依赖于IP数据报的目标IP地址（传统方法）

• 通用转发：基于头部字段的任意集合进行转发

Q: 但是如果地址范围如果没有划分的特别规整，会发生什么？

• 最长前缀匹配：在路由器中经常采用TCAMs( ternary content addressable memories)硬件来完成
• 内容可寻址：将地址交给TCAM，它可以在一个时钟周期内检索出地址，不管表空间有多大
• Cisco Catalyst系列路由器: 在TCAM中可以存储多达约为1百万条路由表项

• 将分组从输入缓冲区传输到合适的输出端口

• 交换速率：分组可以按照该速率从输入传输到输出
• 运行速度经常是输入/输出链路速率的若干倍
• N个输入端口：交换机构的交换速度是输入线路速度的N倍比较理想，才不会成为瓶颈

• 3种典型的交换机构

• 当数据报从交换机构的到达速度比传输速率快就需要输出端口缓存

• 由调度规则选择排队的数据报进行传输

• 假设交换速率Rswitch是Rline的N倍（N：输入端口的数量）

• 当多个输入端口同时向输出端口发送时，缓冲该分组（当通过交换网络到达的速率超过输出速率则缓存）

• 排队带来延迟，由于输出端口缓存溢出则丢弃数据报

• FIFO (first in first out) scheduling: 按照 分组到来的次序发送
• 现实例子?
• 丢弃策略: 如果分组到达一个满的队列，哪个分组将会被抛弃?
• tail drop: 丢弃刚到达的分组
• priority: 根据优先权丢失/移除分组
• random: 随机地丢弃/移除

• 多类

• 循环扫描不同类型的队列, 发送完一类的一个分组，再发送下一个类的一个分组，循环所有类

• 一般化的Round Robin

• 在一段时间内，每个队列得到的服务时间是： Wi/(XIGMA(Wi)) *t，和权重成正比

• 每个类在每一个循环中获得不同权重的服务量

IP:Internet Protocol

• 网络链路有MTU (最大传输单元) –链路层帧所携带的最大数据长度
• 不同的链路类型
• 不同的MTU

• 大的IP数据报在网络上被分片(“fragmented”)
• 一个数据报被分割成若干个小的数据报
• 相同的ID
• 不同的偏移量
• 最后一个分片标记为0
• “重组”只在最终的目标主机进行
• IP头部的信息被用于标识，排序相关分片

• IP 地址: 32位标示，对主机或者路由器的接口编址

• 接口: 主机/路由器和物理链路的连接处
• 路由器通常拥有多个接口
• 主机也有可能有多个接口
• IP地址和每一个接口关联

• 一个IP地址和一个接口相关联

• IP地址:
• 子网部分(高位bits)
• 主机部分(地位bits)

• 什么是子网(subnet) ?
• 一个子网内的节点（主机或者路由器）它们的IP地址的高位部分相同，这些节点构成的网络的一部分叫做子网
• 无需路由器介入，子网内各主机可以在物理上相互直接到达

• Class A：126 networks ，16 million hosts

• Class B：16382networks ，64 K hosts

• Class C：2 million networks ，254 host

• Class D：multicast

• Class E：reserved for future

• 专用地址：地址空间的一部份供专用地址使用

• 永远不会被当做公用地址来分配, 不会与公用地址重复
• 只在局部网络中有意义区分不同的设备

• 路由器不对目标地址是专用地址的分组进行转发

• 专用地址范围
• Class A 10.0.0.0-10.255.255.255 MASK 255.0.0.0
• Class B 172.16.0.0-172.31.255.255 MASK 255.255.0.0
• Class C 192.168.0.0-192.168.255.255 MASK 255.255.255. 0

• 32bits , 0 or 1 in each bit
• 1: bit位置表示子网部分
• 0:bit位置表示主机部分

• 原始的A、B、C类网络的子网掩码分别是
• A：255.0.0.0 ：11111111 00000000 0000000 00000000
• B：255.255.0.0：11111111 11111111 0000000 00000000
• C：255.255.255.0：11111111 11111111 11111111 00000000

• CIDR下的子网掩码例子：
• 11111111 11111111 11111100 00000000

• 另外的一种表示子网掩码的表达方式
• /#
• 例：/22：表示前面22个bit为子网部分

• 获得IP数据报的目标地址

• 对于转发表中的每一个表项 √ 如 (IP Des addr) & (mask)== destination, 则按照表项对应的接口转发该数据报 √ 如果都没有找到,则使用默认表项转发数据报

Q: 如何获得一个网络的子网部分?

Q: 一个ISP如何获得一个地址块?

• 动机: 本地网络只有一个有效IP地址:
• 不需要从ISP分配一块地址，可用一个IP地址用于所有的（局域网）设备–省钱
• 可以在局域网改变设备的地址情况下而无须通知外界
• 可以改变ISP（地址变化）而不需要改变内部的设备地址
• 局域网内部的设备没有明确的地址，对外是不可见的–安全

• 16-bit端口字段:
• 6万多个同时连接，一个局域网!

• 对NAT是有争议的:
• 路由器只应该对第3层做信息处理，而这里对端口号（4层）作了处理
• 违反了end-to-end 原则
• 端到端原则：复杂性放到网络边缘
• 无需借助中转和变换，就可以直接传送到目标主机
• NAT可能要被一些应用设计者考虑, eg, P2P applications
• 外网的机器无法主动连接到内网的机器上
• 地址短缺问题可以被IPv6解决
• NAT穿越：如果客户端需要连接在NAT后面的服务器，如何操作

• 客户端需要连接地址为10.0.0.1的服务器
• 服务器地址10.0.0.1 LAN本地地址 (客户端不能够使用其作为目标地址)
• 整网只有一个外部可见地址: 138.76.29.7

• 方案1: 静态配置NAT：转发进来的对服务器特定端口连接请求
• e.g., (123.76.29.7, port 2500) 总是转发到10.0.0.1 port 25000

• 方案2: Universal Plug and Play (UPnP) Internet Gateway Device (IGD) 协议. 允许NATted主机可以:
• 获知网络的公共 IP地址(138.76.29.7)
• 列举存在的端口映射
• 增/删端口映射 (在租用时间内) i.e., 自动化静态NAT端口映射配置

• 方案 3: 中继 (used in Skype)
• NAT后面的服务器建立和中继的连接
• 外部的客户端链接到中继
• 中继在2个连接之间桥接

• 初始动机: 32-bit地址空间将会被很快用完

• 另外的动机:

• 头部格式改变帮助加速处理和转发
• TTL-1
• 头部checksum
• 分片

• 头部格式改变帮助QoS

• Checksum: 被移除掉，降低在每一段中的处理速度

• Options: 允许，但是在头部之外, 被 “Next Header” 字段标示

• ICMPv6: ICMP的新版本
• 附加了报文类型, e.g. “Packet Too Big”
• 多播组管理功能

路由选择算法

• c(x,x’) = 链路的代价 (x,x’) - e.g., c(w,z) = 5

• 代价可能总为1

• 或是链路带宽的倒数

• 或是拥塞情况的倒数

• 汇集树(sink tree)
• 此节点到所有其它节点的最优路径形成的树
• 路由选择算法就是为所有路由器找到并使用汇集树

• 路由选择算法的原则
• 正确性(correctness):算法必须是正确的和完整的,使分组一站一站接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项；没有处理不了的目标站地址；
• 简单性(simplicity):算法在计算机上应简单：最优但复杂的算法，时间上延迟很大，不实用，不应为了获取路由信息增加很多的通信量；
• 健壮性(robustness):算法应能适应通信量和网络拓扑的变化：通信量变化，网络拓扑的变化算法能很快适应；不向很拥挤的链路发数据，不向断了的链路发送数据；
• 稳定性(stability)：产生的路由不应该摇摆
• 公平性(fairness)：对每一个站点都公平
• 最优性(optimality)：某一个指标的最优，时间上，费用上，等指标，或综合指标；实际上，获取最优的结果代价较高，可以是次优的

• 非自适应算法(non-adaptive algorithm):不能适应网络拓扑和通信量的变化,路由表是事先计算好的

• 自适应路由选择(adaptive algorithm):能适应网络拓扑和通信量的变化

1. 发现相邻节点,获知对方网络地址

• 一个路由器上电之后,向所有线路发送HELLO分组

• 其它路由器收到HELLO分组,回送应答,在应答分组中,告知自己的名字(全局唯一)

• 在LAN中,通过广播HELLO分组,获得其它路由器的信息,可以认为引入一个人工节点

1. 测量到相邻节点的代价(延迟,开销)

• 实测法,发送一个分组要求对方立即响应

• 回送一个ECHO分组

• 通过测量时间可以估算出延迟情况

1. 组装一个分组,描述相邻节点的情况

• 发送者名称

• 序号,年龄

• 列表: 给出它相邻节点,和它到相邻节点的延迟

1. 将分组通过扩散的方法发到所有其它路由器

• 顺序号:用于控制无穷的扩散,每个路由器都记录(源路由器,顺序号),发现重复的或老的就不扩散
• 具体问题1: 循环使用问题
• 具体问题2: 路由器崩溃之后序号从0开始
• 具体问题3:序号出现错误

• 解决问题的办法:年龄字段(age)
• 生成一个分组时,年龄字段不为0
• 每个一个时间段,AGE字段减1
• AGE字段为0的分组将被抛弃

1. 通过Dijkstra算法找出最短路径

• 路由器获得各站点LS分组和整个网络的拓扑

• 通过Dijkstra算法计算出到其它各路由器的最短路径(汇集树)

• 将计算结果安装到路由表中

• LS的应用情况
• OSPF协议是一种LS协议,被用于Internet上
• IS-IS(intermediate system- intermediate system): 被用于Internet主干中, Netware

• 符号标记: c(i,j): 从节点i 到j链路代价(初始状态下非相邻节点之间的链路代价为∞) D(v): 从源节点到节点V的当前路径代价(节点的代价) p(v): 从源到节点V的路径前序节点 N’: 当前已经知道最优路径的的节点集合(永久节点的集合)

• LS路由选择算法的工作原理
• 节点标记: 每一个节点使用(D(v),p(v)) 如：(3,B)标记
• D(v)从源节点由已知最优路径到达本节点的距离
• P(v)前序节点来标注
• 2类节点
• 临时节点(tentative node) :还没有找到从源节点到此节点的最优路径的节点
• 永久节点(permanent node) N’:已经找到了从源节点到此节点的最优路径的节点

• 初始化
• 除了源节点外,所有节点都为临时节点
• 节点代价除了与源节点代价相邻的节点外,都为∞

• 从所有临时节点中找到一个节点代价最小的临时节点,将之变成永久节点(当前节点)W

• 对此节点的所有在临时节点集合中的邻节点(V)
• 如 D(v)>D(w) + c(w,v), 则重新标注此点, (D(W)+C(W,V), W)
• 否则，不重新标注

• 开始一个新的循环

• 代价及相邻节点间代价的获得
• 跳数(hops), 延迟(delay),队列长度
• 相邻节点间代价的获得：通过实测

• 路由信息的更新
• 根据实测 得到本节点A到相邻站点的代价（如:延迟）
• 根据各相邻站点声称它们到目标站点B的代价
• 计算出本站点A经过各相邻站点到目标站点B的代价
• 找到一个最小的代价，和相应的下一个节点Z，到达节点B经过此节点Z，并且代价为A-Z-B的代价
• 其它所有的目标节点一个计算

• 以当前节点J为例,相邻节点A,I,H,K

• J测得到A,I,H,K的延迟为8ms,10ms,12ms,6ms

• 通过交换DV, 从A,I,H,K获得到它们到G的延迟为18ms,31ms,6ms,31ms

• 因此从J经过A,I,H,K到G的延迟为26ms,41ms,18ms,37ms

• 将到G的路由表项更新为18ms, 下一跳为：H

• 其它目标一样，除了本节点

• Dx(y) = 节点x到y代价最小值的估计
• x 节点维护距离矢量Dx = [Dx(y): y є N ]

• 节点x:
• 知道到所有邻居v的代价: c(x,v)
• 收到并维护一个它邻居的距离矢量集
• 对于每个邻居, x 维护Dv = [Dv(y): y є N ]

• Dx(y)估计值最终收敛于实际的最小代价值dx(y)
• 分布式、迭代算法

• DV的无穷计算问题
• DV的特点
• 好消息传的快 坏消息传的慢
• 好消息的传播以每一个交换周期前进一个路由器的速度进行
• 好消息:某个路由器接入或有更短的路径

• 坏消息的传播速度非常慢(无穷计算问题)

• 例子:
• 第一次交换之后, B从C处获得信息,C可以到达A(C-A,要经过B本身),但是路径是2,因此B变成3,从C处走
• 第二次交换,C从B处获得消息, B可以到达A,路径为3, 因此,C到A从B走,代价为3
• 无限此之后, 到A的距离变成INF,不可达

• 水平分裂的问题:在某些拓扑形式下会失败（存在环路）

• 例子:
• A,B到D的距离为2, C到D的距离为1、
• 如果C-D路径失败，C获知到D为INF,从A,B获知到D的距离为INF,因此C认为D不可达
• A从C获知D的距离为INF,但从B处获知它到D的距离为2,因此A到B的距离为3,从B走
• B也有类似的问题
• 经过无限次之后,A和B都知道到D的距离为INF

• 节点会通告不正确的链路代价

• 每个节点只计算自己的路由表

• 错误信息影响较小，局部，路由较健壮 DV:

• DV节点可能通告对全网所有节点的不正确路径代价
• 距离矢量

• 每一个节点的路由表可能被其它节点使用
• 错误可以扩散到全网

自治系统内部的路由选择

• DV: 在邻居之间每30秒交换通告报文
• 定期，而且在改变路由的时候发送通告报文
• 在对方的请求下可以发送通告报文

• 每一个通告: 至多AS内部的25个目标网络的DV
• 目标网络+跳数（一次公告最多25个子网，最大跳数为16）

• RIP 以应用进程的方式实现：route-d (daemon)

• 通告报文通过UDP报文传送，周期性重复

• 网络层的协议使用了传输层的服务，以应用层实体的方式实现

• “open”: 标准可公开获得

• 使用LS算法
• LS 分组在网络中（一个AS内部）分发
• 全局网络拓扑、代价在每一个节点中都保持
• 路由计算采用Dijkstra算法

• OSPF通告信息中携带：每一个邻居路由器一个表项

• 通告信息会传遍AS全部（通过泛洪）
• 在IP数据报上直接传送OSPF报文 (而不是通过UDP和TCP)

• IS-IS路由协议：几乎和OSPF一样

• 2个级别的层次性: 本地, 骨干
• 链路状态通告仅仅在本地区域Area范围内进行
• 每一个节点拥有本地区域的拓扑信息；
• 关于其他区域，知道去它的方向，通过区域边界路由器（最短路径）

• 区域边界路由器: “汇总（聚集）”到自己区域内网络的距离, 向其它区域边界路由器通告.

• 骨干路由器: 仅仅在骨干区域内，运行OSPF路由

• 边界路由器: 连接其它的AS’s.

ISP之间的路由选择: BGP

• 平面路由的问题
• 规模巨大的网络中，路由信息的存储、传输和计算代价巨大
• DV: 距离矢量很大，且不能够收敛
• LS：几百万个节点的LS分组的泛洪传输，存储以及最短路径算法的计算
• 管理问题：
• 不同的网络所有者希望按照自己的方式管理网络
• 希望对外隐藏自己网络的细节
• 当然，还希望和其它网络互联

• 层次路由：将互联网分成一个个AS(路由器区域)
• 某个区域内的路由器集合，自治系统“autonomous systems” (AS)
• 一个AS用AS Number（ASN)唯一标示
• 一个ISP可能包括1个或者多个AS

• 路由变成了: 2个层次路由
• AS内部路由：在同一个AS内路由器运行相同的路由协议
• “intra-AS” routing protocol：内部网关协议
• 不同的AS可能运行着不同的内部网关协议
• 能够解决规模和管理问题
• 如：RIP,OSPF,IGRP
• 网关路由器：AS边缘路由器，可以连接到其他AS
• AS间运行AS间路由协议
• “inter-AS” routing protocol：外部网关协议
• 解决AS之间的路由问题，完成AS之间的互联互通

• 解决了规模问题
• 内部网关协议解决：AS内部数量有限的路由器相互到达的问题, AS内部规模可控
• 如AS节点太多，可分割AS，使得AS内部的节点数量有限
• AS之间的路由的规模问题
• 增加一个AS，对于AS之间的路由从总体上来说，只是增加了一个节点=子网（每个AS可以用一个点来表示）
• 对于其他AS来说只是增加了一个表项，就是这个新增的AS如何走的问题
• 扩展性强：规模增大，性能不会减得太多

• BGP 会话: 2个BGP路由器(“peers”)在一个半永久的TCP连接上交换BGP报文:
• 通告向不同目标子网前缀的“路径”（BGP是一个“路径矢量”协议）

• 当AS3网关路由器3a向AS2的网关路由器2c通告路径： AS3,X
• 3a参与AS内由运算，知道本AS所有子网X信息
• 语义上：AS3向AS2承诺，它可以向子网X转数据报
• 3a是2c关于X的下一跳（next hop）

• 当通告一个子网前缀时，通告包括 BGP 属性
• prefix + attributes = “route”

• 2个重要的属性:
• AS-PATH: 前缀的通告所经过的AS列表: AS 67 AS 17
• 检测环路；多路径选择
• 在向其它AS转发时，需要将自己的AS号加在路径上
• NEXT-HOP: 从当前AS到下一跳AS有多个链路，在NETX-HOP属性中，告诉对方通过那个 I 转发.
• 其它属性：路由偏好指标，如何被插入的属性

• 基于策略的路由：
• 当一个网关路由器接收到了一个路由通告, 使用输入策略来接受或过滤（accept/decline.）
• 过滤原因例1：不想经过某个AS，转发某些前缀的分组
• 过滤原因例2：已经有了一条往某前缀的偏好路径
• 策略也决定了是向它别的邻居通告收到的这个路

• 路由器AS2.2c从AS3.3a接收到的AS3,X路由通告 (通过 eBGP)

• 基于AS2的输入策略，AS2.2c决定接收AS3,X的通告，而且通过iBGP）向AS2的所有路由器进行通告

• 基于AS2的策略，AS2路由器2a通过eBGP向AS1.1c路由器通告AS2,AS3,X 路由信息
• 路径上加上了 AS2自己作为AS序列的一跳

• AS1 网关路由器1c从2a学习到路径：AS2,AS3,X

• AS1网关路由器1c从3a处学习到路径AS3,X

• 基于策略，AS1路由器1c选择了路径：AS3,X，而且通过iBGP告诉所有AS1内部的路由器

• 使用TCP协议交换BGP报文.

• BGP 报文:
• OPEN: 打开TCP连接，认证发送方
• UPDATE: 通告新路径 (或者撤销原路径)
• KEEPALIVE：在没有更新时保持连接，也用于对OPEN 请求确认
• NOTIFICATION: 报告以前消息的错误，也用来关闭连接

Q:路由器是如何设置到这些远程子网前缀的转发表表项的？

Q:路由器是如何设置到这些远程子网前缀的转发表表项的？

• 路由器可能获得一个网络前缀的多个路径，路由器必须进行路径的选择，路由选择可以基于：

1. 本地偏好值属性: 偏好策略决定

2. 最短AS-PATH ：AS的跳数

3. 最近的NEXT-HOP路由器:热土豆路由

4. 附加的判据：使用BGP标示

• 一个前缀对应着多种路径，采用消除规则直到留下一条路径

• 2d通过iBGP获知，它可以通过2a或者2c到达X

• 热土豆策略：选择具备最小内部区域代价的网关作为往X的出口（如：2d选择2a，即使往X可能有比较多的AS跳数）：不要操心域间的代价！

• A向B和C通告路径Aw

• B选择不向C通告BAw：
• B从CBAw的路由上无法获得收益，因为C,A,w都不是B的客户
• C从而无法获知 CBAw路径的存在：每个ISP感知到的网络和真实不一致

• C可能会通过 CAw (而不是使用B)最终路由到w

• A,B,C 是 提供商网络：

• X,W,Y 是桩网络（stub networks）或者叫端网络

• X 是双重接入的，多宿桩网络，接入了2个网络

• 策略强制让X:
• X不想路由从B通过X到C的分组
• 因而X就不通告给B，它实际上可以路由到C

为什么内部网关协议和外部网关协议如此不同?

SDN控制平面

Q: 网管如果需要u到z的流量走uvwz,x到z的流量走xwyz，怎么办？

Q: 如果网管需要将u到z的流量分成2路：uvwz 和uxyz (负载均衡)，怎么办?（ IP路由面向目标）

Q:如果需要w对蓝色的和红色的流量采用不同的路由，怎么办？

• 快速，简单，商业化交换设备采用硬件实现通用转发功能

• 流表被控制器计算和安装

• 基于南向API（例如OpenFlow），SDN控制器访问基于流的交换机
• 定义了哪些可以被控制哪些不能

• 也定义了和控制器的协议(eg.OpenFlow)

• 控制器和SDN交换机交互的协议

• 采用TCP来交换报文
• 加密可选

• 3种OpenFlow报文类型
• 控制器>交换机
• 异步（交换机>控制器）
• 对称 (misc)

• 分组进入: 将分组（和它的控制）传给控制器，见来自控制器的packet-out报文

• 流移除: 在交换机上删除流表项

• 端口状态: 通告控制器端口的变化

• ODL Lithium 控制器

• 网络应用可以在SDN 控制 内 或者 外面

• 服务抽象层SAL：和内部以及外部的应用以及服务进行交互

• 控制应用和控制器分离（应用app在控制器外部）

• 意图框架：服务的高级规范：描述什么而不是如何

• 相当多的重点聚焦在分布式核心上，以提高服务的可靠性，性能的可扩展性

链路层和局域网

• 点到点连接

• 多点连接：
• 共享型介质
• 通过网络交换机

• WAN:网络形式采用点到点链路
• 带宽大、距离远（延迟大） >带宽延迟积大
• 如果采用多点连接方式
• 竞争方式：一旦冲突代价大
• 令牌等协调方式：在其中协调节点的发送代价大

• 点到点链路的链路层服务实现非常简单，封装和解封装

• LAN一般采用多点连接方式
• 连接节点非常方便
• 接到共享型介质上（或网络交换机），就可以连接所有其他节点

• 多点连接方式网络的链路层功能实现相当复杂
• 多点接入：协调各节点对共享性介质的访问和使用
• 竞争方式：冲突之后的协调
• 令牌方式：令牌产生，占有和释放等

• 在相邻节点间（一个子网内）进行可靠的转发
• 在低差错链路上很少使用 (光纤,一些双绞线)
• 出错率低，没有必要在每一个帧中做差错控制的工作，协议复杂
• 发送端对每一帧进行差错控制编码，根据反馈做相应的动作
• 接收端进行差错控制解码，反馈给发送端（ACK，NAK）
• 在本层放弃可靠控制的工作，在网络层或者是传输层做可靠控制的工作，或者根本就不做可靠控制的工作
• 在高差错链路上需要进行可靠的数据传送
• 高差错链路：无线链路：

Q：为什么要在采用无线链路的网络上，链路层做可靠数据传输工作；还要在传输层做端到端的可靠性工作？

• 流量控制：
• 使得相邻的发送和接收方节点的速度匹配

• 错误检测：
• 差错由信号衰减和噪声引起
• 接收方检测出的错误:
• 通知发送端进行重传或丢弃帧

• 差错纠正:
• 接收端检查和纠正bit错误，不通过重传来纠正错误

• 半双工和全双工:
• 半双工：链路可以双向传输，但一次只有一个方向

• 发送方:
• 在帧中封装数据报
• 加上差错控制编码，实现RDT和流量控制功能等

• 接收方：
• 检查有无出错，执行rdt和流量控制功能等
• 解封装数据报，将至交给上层

差错检测和纠正

• 协议会漏检一些错误，但是很少

• 更长的EDC字段可以得到更好的检测和纠正效果

• 突发错误和突发长度

• CRC检错性能描述

多路访问协议

• 没有特殊节点协调发送

• 没有时钟和时隙的同步

• 信道划分
• 把信道划分成小片（时间、频率、编码）
• 分配片给每个节点专用

• 随机访问
• 信道不划分，允许冲突
• 冲突后恢复

• 依次轮流
• 节点依次轮流
• 但是有很多数据传输的节点可以获得较长的信道使用权

• 轮流使用信道，信道的时间分为周期

• 每个站点使用每周期中固定的时隙(长度=帧传输时间)传输帧

• 如果站点无帧传输，时隙空闲->浪费

• 如：6站LAN，1、3、4有数据报，时隙2、5、6空闲

• CDMA (code division multiple access) :
• 所有站点在整个频段上同时进行传输,采用编码原理加以区分
• 完全无冲突
• 假定:信号同步很好,线性叠加

• 比方
• TDM：不同的人在不同的时刻讲话
• FDM：不同的组在不同的小房间里通信
• CDMA：不同的人使用不同的语言讲话

• 当节点有帧要发送时
• 以信道带宽的全部 R bps发送
• 没有节点间的预先协调

• 两个或更多节点同时传输，会发生➜冲突“collision”

• 随机存取协议规定:
• 如何检测冲突
• 如何从冲突中恢复（如：通过稍后的重传）

• 随机MAC协议:
• 时隙ALOHA
• ALOHA
• CSMA, CSMA/CD, CSMA/CA

• N个节点的最大效率：求出使f(P)=Np(1-p)N-1最大的p*

• 代入P得到最大f(p)=Np(1-p)N-1

• N为无穷大时的极限为1/e=0.37

1. 适配器获取数据报，创建帧

2. 发送前：侦听信道CS 1)闲：开始传送帧 2)忙：一直等到闲再发送 3.发送过程中，冲突检测CD 1)没有冲突:成功 2)检测到冲突:放弃,之后尝试重发

• 冲突: 2+ 站点（AP或者站点）在同一个时刻发送

• 802.11: CSMA – 发送前侦听信道
• 不会和其它节点正在进行的传输发生冲突

• 802.11: 没有冲突检测!
• 无法检测冲突：自身信号远远大于其他节点信号
• 即使能CD：冲突!=成功
• 目标: avoid collisions: CSMA/C(ollision)A(voidance)
• 无法CD，一旦发送一脑全部发送完毕，不CD
• 为了避免无CD带来的信道利用率低的问题，事前进行冲突避免

• 如果帧正确，则在SIFS后发送ACK

• 在count down时，侦听到了信道空闲为什么不发送，而要等到0时在发送
• 2个站点有数据帧需要发送，第三个节点正在发送
• LAN CD：让2者听完第三个节点发完，立即发送
• 冲突：放弃当前的发送，避免了信道的浪费于无用冲突帧的发送
• 代价不昂贵

• WLAN : CA
• 无法CD，一旦发送就必须发完，如冲突信道浪费严重，代价高昂
• 思想：尽量事先避免冲突，而不是在发生冲突时放弃然后重发
• 听到发送的站点，分别选择随机值，回退到0发送
• 不同的随机值，一个站点会胜利
• 失败站点会冻结计数器，当胜利节点发完再发

• 无法完全避免冲突
• 两个站点相互隐藏： • A,B 相互隐藏，C在传输 • A,B选择了随机回退值 • 一个节点如A胜利了，发送 • 而B节点收不到，顺利count down到0 发送 • A,B的发送在C附近形成了干扰
• 选择了非常靠近的随机回退值： • A,B选择的值非常近 • A到0后发送 • 但是这个信号还没达到B时 • B也到0了，发送冲突

• 发送方首先使用CSMA向BS发送一个小的RTS分组
• RTS可能会冲突（但是由于比较短，浪费信道较少）

• BS广播 clear-to-send CTS，作为RTS的响应

• CTS能够被所有涉及到的节点听到
• 发送方发送数据帧
• 其它节点抑制发 > 采用小的预约分组，可以完全避免数据帧的冲突

• 主节点邀请从节点依次传送

• 从节点一般比较“dumb”

• 缺点:
• 轮询开销：轮询本身消耗信道带宽
• 等待时间：每个节点需等到主节点轮询后开始传输，即使只有一个节点，也需要等到轮询一周后才能够发送
• 单点故障：主节点失效时造成整个系统无法工作

• 多点接入问题：对于一个共享型介质，各个节点如何协调对它的访问和使用?
• 信道划分：按时间、频率或者编码
• TDMA、FDMA、CDMA

• 随机访问 (动态) • ALOHA, S-ALOHA, CSMA, CSMA/CD • 载波侦听: 在有些介质上很容易 (wire：有线介质), 但在有些介质上比较困难 (wireless：无线) • CSMA/CD ：802.3 Ethernet网中使用 • CSMA/CA ：802.11WLAN中使用

• 依次轮流协议
• 集中：由一个中心节点轮询；分布：通过令牌控制
• 蓝牙、FDDI、令牌环

LANs

• 32bitIP地址:
• 网络层地址
• 前n-1跳：用于使数据报到达目的IP子网
• 最后一跳：到达子网中的目标节点

• LAN（MAC/物理/以太网）地址:
• 用于使帧从一个网卡传递到与其物理连接的另一个网卡(在同一个物理网络中)
• 48bit MAC地址固化在适配器的ROM，有时也可以通过软件设定
• 理论上全球任何2个网卡的MAC地址都不相同

1. 分离好处

2. 网卡坏了，ip不变，可以捆绑到另外一个网卡的mac上

3. 物理网络还可以除IP之外支持其他网络层协议，链路协议为任意 上层网络协议， 如IPX等

4. 捆绑的问题

5. 如果仅仅使用IP地址，不用mac地址，那么它仅支持IP协议

6. 每次上电都要重新写入网卡 IP地址；

7. 另外一个选择就是不使用任何地址；不用MAC地址，则每到来一个帧都要上传到IP层次，由它判断是不是需要接受，干扰一次

• MAC地址由IEEE管理和分配

• 制造商购入MAC地址空间（保证唯一性）

• 类比: (a)MAC地址：社会安全号 (b)IP地址：通讯地址

• MAC平面地址 ➜ 支持移动
• 可以将网卡到接到其它网络

• IP地址有层次-不能移动
• 依赖于节点连接的IP子网，与子网的网络号相同（有与其相连的子网相同的网络前缀）

问题:已知B的IP地址，如何确定B的MAC地址?

• 在LAN上的每个IP节点都有一个ARP表

• ARP表：包括一些LAN节点IP/MAC地址的映射

• A要发送帧给B(B的IP地址已知)， 但B的MAC地址不在A的ARP表中

• A广播包含B的IP地址的ARP查询包
• Dest MAC address = FF-FF-FF-FF-FF-FF
• LAN上的所有节点都会收到该查询包

• B接收到ARP包，回复A自己的MAC地址
• 帧发送给A
• 用A的MAC地址（单播）

• A在自己的ARP表中，缓存IP-to-MAC地址映射关系，直到信息超时
• 软状态: 靠定期刷新维持的系统状态
• 定期刷新周期之间维护的状态信息可能和原有系统不一致

• ARP是即插即用的
• 节点自己创建ARP的表项
• 无需网络管理员的干预

• A创建数据报，源IP地址：A；目标IP地址：B

• A创建一个链路层的帧，目标MAC地址是R，该帧包含A到B的IP数据报

• 帧从A发送到R

• 帧被R接收到，从中提取出IP分组，交给上层IP协议实体

• R转发数据报，数据报源IP地址为A，目标IP地址为B

• R创建一个链路层的帧，目标MAC地址为B，帧中包含A到B的IP数据报

• 目前最主流的LAN技术：98%占有率

• 廉价：30元RMB 100Mbps！

• 最早广泛应用的LAN技术

• 比令牌网和ATM网络简单、廉价

• 带宽不断提升：10M, 100M, 1G, 10G

• 总线：在上个世纪90年代中期很流行
• 所有节点在一个碰撞域内，一次只允许一个节点发送
• 可靠性差，如果介质破损，截面形成信号的反射，发送节点误认为是冲突，总是冲突

• 星型：目前最主流

• 连接选择: hub 或者 switch

• 现在一般是交换机在中心

• 每个节点以及相连的交换机端口使用（独立的）以太网协议（不会和其他节点的发送产生碰撞）

• 无连接：帧传输前，发送方和接收方之间没有握手

• 不可靠：接收方适配器不发送ACKs或NAKs给发送方
• 递交给网络层的数据报流可能有gap
• 如上层使用像传输层TCP协议这样的rdt，gap会被补上(源主机，TCP实体)
• 否则，应用层就会看到gap

• 以太网的MAC协议：采用二进制退避的CSMA/CD介质访问控制形式

• 在 10BaseT中使用

• 每一个bit的位时中间有一个信号跳变

• 允许在接收方和发送方节点之间进行时钟同步
• 节点间不需要集中的和全局的时钟

• 10Mbps，使用20M带宽，效率50%

• Hey, this is physical-layer stuff!

• 采用标准的以太帧格式

• 允许点对点链路和共享广播信道

• 物理编码：8b10b编码

• 在共享模式，继续使用CSMA/CD MAC技术，节点间需要较短距离以提高利用率

• 交换模式：全双工千兆可用于点对点链路
• 站点使用专用信道，基本不会冲突，效率高
• 除非发往同一个目标

• 802.11b
• 使用无需许可的2.4-5 GHz 频谱
• 无绳电话和微波炉
• 最高11 Mbps
• 在物理层采用直接序列扩频 direct sequence spread spectrum (DSSS) +所有的主机采用同样的序列码 不同：速率，物理层 相同：MAC, 帧格式

• 802.11a
• 更高频率5-6 GHz
• 最高54 Mbps
• 距离相对短，受多路径影响大

• 802.11g
• 频率2.4-5 GHz
• 最大54 Mbps
• 与802.11b向后兼容

• 802.11n: 多天线MIMO
• 频率2.4-5 GHz
• 最高200 Mbps

• 所有的802.11标准都是用CSMA/CA进行多路访问

• 所有的802.11标准都有基站模式和自组织网络模式

• 802.11b: 2.4GHz-2.485GHz 频谱被分为11个相互不同的但是部分重叠的频段
• AP管理员为AP选择一个频率
• 可能的干扰: 邻居AP可能选择同样一个信道!

• 主机: 必须在通信之前和AP建立associate
• 扫描所有的信道，侦听包含AP SSID和MAC地址的信标帧
• 主动扫描：主机发送探测，接受AP的响应
• 被动扫描
• 选择希望关联的AP
• 可能需要执行鉴别（认证）[Chapter 8]
• 基于MAC、用户名口令
• 通过AP的中继，使用RADIUS鉴别服务器进行身份鉴别
• 将会执行DHCP获得IP地址和AP所在子网前缀

• 网段(LAN segments) ：可以允许一个站点发送的网络范围
• 在一个碰撞域，同时只允许一个站点在发送
• 如果有2个节点同时发送，则会碰撞
• 通常拥有相同的前缀，比IP子网更详细的前缀

• 所有以hub连到一起的站点处在一个网段，处在一个碰撞域
• 骨干hub将所有网段连到了一起

• 通过hub可扩展节点之间的最大距离

• 通过HUB,不能将10BaseT和100BaseT的网络连

Q: 交换机如何知道通过接口1到达A，通过接口5到达 B’?

• A: 每个交换机都有一个交6换表 switch table, 每个表项:
• (主机的MAC地址,到达该MAC经过的接口，时戳)
• 比较像路由表! > Q: 每个表项是如何创建的？如何维护的?

• 交换机可被级联到一起

• 流量隔离: 从/到1-8端口的流量只会涉及到1-8
• 也可以基于MAC地址进行VLAN定义

• 动态成员: 成员可以在VLANs之间动态分配router

• 在VLANs间转发:通过路由器进行转发 (就像他们通过各自的交换机相联一样)
• 实际操作中，设备生产商可以提供：交换机和路由器的单一设备

• 如果有多个交换机，希望它们相连并且共享VLANs信息

• 方法1：各交换机每个VLAN一个端口和另外交换机相应VLAN端口相连->扩展性问题

• trunk port干线端口: 多个交换机共享定义的VLAN，在它们之间传输帧
• 帧在不同交换机上的一个VLAN上转发，不能够再使用vanilla 802.1帧 (必须要携带VLAN ID信息)
• 802.1q协议增加/移除附加的头部字段，用于在trun端口上进行帧的转发

链路虚拟化

• 建立基于标签的转发表-信令协议：支持逐跳和显式路由：路由信息传播，路由计算(基于Qos，=基于策略的)，标签分发
• LDP CR-LDP
• RSVP扩展 BGP扩展

• MPLS优点
• 路由弹性：基于Qos，基于策略的
• 充分利用已有的硬件ATM，快速转发
• 支持流连工程，VPN
• 支持带宽等资源的分配

• 初始目的：使用固定长度的标签label进行高速率IP转发 (而不是使用IP address,采用最长前缀匹配)
• 一开始采用固定长度ID进行查表 (而不是采用前缀匹配)
• 借鉴了虚电路的思想 (VC)
• 但是IP数据报仍然保留IP地址!
• 在帧和其封装的分组之间加入一个垫层，标签交换使能的路由器使用垫层信息进行分组转发，不解析分组目标地址

• a.k.a. 标签交换路由器

• 基于标签的值进行分组的转发 (而非检查IP地址)
• MPLS转发表和IP转发表相互独立

• 弹性: MPLS转发决策可以和IP不同
• 采用源地址和目标地址来路由到达同一个目标的流，不同路径（支持流量工程）
• 如果链路失效，能够快速重新路由: 预先计算好的备份链路 (对于VoIP有效)

• IP 路由: 到达目标的路径仅仅取决 目标地址

• IP路由:到达目标的路径仅仅取决于目标地址

• MPLS路由：到达目标的路由，可以基于源和目标地址
• 快速重新路由：在链路失效时，采用预先计算好的路径

• 数万-数十万台主机构成DC网络，密集耦合、距离 临近:
• 电子商务(e.g. Amazon)
• 内容服务器(e.g., YouTube, Akamai, Apple, Microsoft)
• 搜索引擎，数据挖掘 (e.g., Google)

• 挑战:
• 多种应用，每一种都服务海量的客户端
• 管理/负载均衡，避免处理、网络和数据的瓶颈

• 在交换机之间，机器阵列之间有丰富的互连措施:
• 在阵列之间增加吞吐 (多个可能的路由路径)
• 通过冗余度增加可靠

• 笔记本需要一个IP地址，第一跳路由器的IP地址，DNS的地址: 采用DHCP

• DHCP 请求被封装在UDP中，封装在IP, 封装在 802.3 以太网帧中

• 以太网的帧在LAN上广播(dest: FFFFFFFFFFFF), 被运行中的DHCP服务器接收到

• 以太网帧中解封装IP分组，解封装UDP，解封装DHCP

• DHCP 服务器生成DHCP ACK 包括客户端IP地址，第一跳路由器IP地址和DNS名字服务器地址

• 在DHCP服务器封装, 帧通过LAN转发 (交换机学习) 在客户端段解封装

• 客户端接收DHCP ACK应答 客户端段解封装客户端有了IP地址，知道了DNS域名服务器的名字和IP地址第一跳路由器的IP地址

• 在发送HTTP request请求之前, 需要知道 www.google.com 的IP: DNS

• DNS查询被创建，封装在UDP段中，封装在IP数据报中，封装在以太网的帧中. 将帧传递给路由器，但是需要知道路由器的接口： MAC地址：ARP

• ARP查询广播，被路由器接收，路由器用ARP应答，给出其IP地址某个端口的MAC地址

• 客户端现在知道第一跳路由器MAC地址，所以可以发送DNS查询帧了

• 包含了DNS查询的IP数据报通过LAN交换机转发，从客户端到第一跳路由器

• IP 数据报被转发，从校园到达comcast网络，路由（路由表被RIP，OSPF，IS-IS 和/或BGP协议创建）到DNS服务器

• 被DNS服务器解封装

• DNS服务器回复给客户端：www.google.com 的IP地址

网络安全

• 网络安全原理:
• 加密，不仅仅用于机密性
• 认证
• 报文完整性
• 密钥分发

• 安全实践
• 防火墙
• 各个层次的安全性：应用层，传输层，网络层和链路层

• 窃听: 截获报文

• 插入：在连接上插入报文

• 伪装: 可以在分组的源地址写上伪装的地址

• 劫持: 将发送方或者接收方踢出，接管连接

• 拒绝服务: 阻止服务被其他正常用户使用 (e.g.,通过对资源的过载使用)

加密原理

• e.g., 密钥在单码替换加密方法中是替换模式

• Q: 但是Bob和Alice如何就这个密钥达成一致呢

• 初始替换 16 轮一样的函数应用，每一轮使用的不同的48bit密钥最终替换

• 一个循环：一个输入bit影响8个输出bit

• 多重循环: 每个输入比特影响所有的输出bit

• 块密码：DES, 3DES, AE

• 新的对称 密钥NIST标准(Nov. 2001) 用于替换DES

• 数据128bit成组加密

• 128, 192, or 256 bit keys

• 穷尽法解密如果使用1秒钟破解 DES, 需要花149万亿年破解AES

• 加密算法已知，求密钥

• 加密算法和密钥均不知道

• 唯密文攻击

• 已知明文攻击
• 已经知道部分密文和明文的对应关系

• 选择明文攻击
• 攻击者能够选择一段明文，并得到密

认证

报文完整性

• 对m使用散列函数H，获得固定长度的 报文摘要H(m).

密钥分发和证书

• Certification authority (CA): 将每一个注册实体E和他的公钥捆绑.

• E(person, router)到CA那里注册他的公钥
• E 提供给CA，自己身份的证据 “proof of identity”
• CA创建一个证书，捆绑了实体信息和他的公钥
• Certificate包括了E的公钥，而且是被CA签署的（被CA用自己的私钥加了密的）

Q: KDC如何使得 Bob和Alice在和对方通信前，就对称式会话密钥达成一致?

• 当Alice需要拿到Bob公钥
• 获得Bob的证书certificate (从Bob或者其他地方).
• 对Bob的证书，使用CA的公钥

• Alice 需要发送机密的报文m给Bob

• Alice 需要提供机密性，源端可认证性和报文的完整性

• Alice 数字签署文件

• 发送报文（明文）

• 为使用SSL服务的、基于TCP的应用提供传输层次的安全性
• eg. 在WEB的浏览器和服务器之间进行电子商务的交易 (shttp)

• 所提供的安全服务:
• 服务器的可认证性，数据加密，客户端的可认证性

• Alice, Bob采用共享的MS产生4个keys:
• EB: Bob->Alice 数据加密key
• EA: Alice->Bob数据加密key
• MB: Bob->Alice MAC（报文鉴别编码）key
• MA: Alice->Bob MAC key

• 加密和MAC算法在Bob, Alice之间协商

• 为什么要4个keys?
• 更安全

• 网络层次的机密性:
• 发送端主机对IP数据报中的数据进行加密
• 数据：TCP或者UDP的段; ICMP和SNMP 报文.

• 网络层次的可认证性
• 目标主机可以认证源主机的IP地址

• 2个主要协议:
• 认证头部 (AH)协议
• 封装安全载荷encapsulation security payload (ESP) 协议

• 不管AH 还是ESP, 源和目标在通信之前要握手:
• 创建一个网络层次的逻辑通道：安全关联security association (SA)

• 每一个SA 都是单向

• 由以下元组唯一确定:
• 安全协议 (AH or ESP)
• 源 IP地址
• 32-bit连接ID

• 提供机密性，主机的可认证性，数据的完整性

• 数据和ESP尾部部分被加密

• next header字段在ESP尾部

• ESP 认证的头部与AH类似

• 协议号 = 50

• 提供源端的可认证性，数据完整性，但是不提供机密性

• 在IP头部和数据字段之间插入AH的头部

• 协议字段: 51

• 中间的路由器按照常规处理这个数据报

访问控制：防火墙

• 内部网络通过配置防火墙的路由器连接到互联网上

• 路由器对分组逐个过滤，根据以下规则来决定转发 还是丢弃:
• 源IP地址,目标IP地址
• TCP/UDP源和目标端口
• ICMP报文类别
• TCP SYN 和ACK bits

• ACL: 规则的表格，top-bottom应用到输入的分组:(action, condition) 对

• 根据应用数据的内容来过滤进出的数据报，就像根据IP/TCP/UDP字段来过滤一样
• 检查的级别：应用层数据

• Example: 允许内部用户登录到外部服务器，但不是直接登录

1. 需要所有的telnet用户通过网关来telnet

2. 对于认证的用户而言，网关建立和目标主机的telnet connection ，网关在2个连接上进行中继

3. 路由器过滤器对所有不是来自网关的telnet的分组全部过滤掉

• IP spoofing: 路由器不知道数据报是否真的来自于声称的源地址

• 如果有多个应用需要控制，就需要有多个应用程序网关

• 客户端软件需要知道如何连接到这个应用程序
• e.g., 必须在Web browser中配置网络代理的Ip地址

• 过滤器对UDP段所在的报文，或者全过或者全都不过

• 折中: 与外部通信的自由度，安全的级别

• 很多高度保护的站点仍然受到攻击的困扰

• multiple IDSs: 在不同的地点进行不同类型的检查

• 分组过滤:
• 对TCP/IP头部进行检查
• 不检查会话间的相关性

• IDS: intrusion detection system
• 深入分组检查: 检查分组的内容 (e.g., 检查分组中的特征串已知攻击数据库的病毒和攻击串
• 检查分组间的相关性，判断是否是有害的分组
• 端口扫描
• 网络映射
• Dos攻击

• 在攻击之前： “踩点” – 发现在网络上实现了哪些服务

• 使用ping来判断哪些主机在网络上有地址

• 端口扫描：试图顺序地在每一个端口上建立TCP连接 (看看发生了什么)

• 记录进入到网络中的通信流量

• 发现可疑的行为 (IP addresses, 端口被依次扫描)

• 机构中的所有主机都运行能够监测软件，周期性地检查是否有网卡运行于混杂模式

• 每一个主机一个独立的网段 (交换式以太网而不是使用集线器)

• 可以有应用进程直接产生 “raw” IP分组, 而且可以在IP源地址部分直接放置任何地址

• 接收端无法判断源地址是不是具有欺骗性的

• eg. C伪装成B

• 路由器对那些具有非法源地址的分组不进行转发(e.g., 数据报的源地址不是路由器所在的网络地址)

• 很好，但是入口过滤不能够在全网范围内安装

• 在到达主机之前过滤掉这些泛洪的分组 (e.g., SYN) : throw out good with bad

• 回溯到源主机(most likely an innocent, compromised machine)

• 产生的大量分组淹没了接收端

• Distributed DOS (DDOS): 多个相互协作的源站淹没了接收端

• e.g. C以及远程的主机SYN-attack A