计算机网络
2023-08-30 22:23:55 0 举报AI智能生成
计算机网络全书思维导图
作者其他创作
大纲/内容
分支主题
分支主题
分支主题
分支主题
第一章 概论
1.1什么是Internet
网络
节点和边之间的关联关系
计算机网络
联网的计算机所构成的系统
通信链路
将各种节点连在一起
接入网链路
主机连接到互联网的链路（和方的有关的链路）
主干链路
路由器间的链路（圆的接在一起）
性能指标：带宽（bps）=传输速度
节点
主机节点（方形）（端系统=主机）（end system\host）
电脑，手机，web服务器，联网的冰箱等等
是源，也是目标
数据交换节点（圆形）
路由器（圆的）
工作在网络层
协议
对等层实体在通信过程中应该遵守的规则的集合，包括语义、语法和时序
控制发送、接受信息
TCP、IP、HTTP、FTP、PPP
协议定义了在两个或者多个通信实体之间交换的报文格式（语法、语义）和次序，以及在报文传输和/或接受或者其他事件方面所采取的动作
交换机（方的）
工作在链路层
中继器
既不是源也不是目标，是数据的中转节点
互联网
以TCP协议和IP协议为主的一簇协议来支撑工作的网络（是计算机网络的一种）
网络的网络，一堆网络通过网络互联设备连在一起的网络
公共网Internet vs 专用intranet
从服务的角度：互联网是分布式应用以及为分布式应用提供通讯的基础设施（基础设施为应用进程提供服务的形式是API，分布式应用是网络存在的理由，应用层以下都是基础设施）
使用通信设施进行通信的分布式应用
Web、VoIP、email、分布式游戏、电子商务、社交网络
通信基础设施为apps提供编程接口（通信服务）
将发送和接受数据的apps与互联网连接起来
为app应用提供服务选择，类似于邮政服务
无连接不可靠服务（UTP）
面向连接的可靠服务（TCP ip）
Internet·标准
RFC：request for comments
REC文档在IEFT上发布
协议通过RFC格式发布，一个协议可能涉及很多RFC文档
IETF: internet engineering task force（互联网工程任务组）
网络结构
网络边缘（edge）
主机
（主机上的）应用程序（客户端和服务器）（边缘系统的网络应用是网络存在的理由）
网络核心（core）
把所有的边缘节点接在一起，让任意两个端系统可以相互通信（数据交换）
网络的网络
互联着的路由器
接入网、物理媒体（access）
把边缘接入到网络核心
有线或者无线通信链路
结构图
1.2 网络边缘
端系统（主机）
运行应用程序，如Web、email
在“网络的边缘”
模式
客户/服务器（C/S）模式
客户端向服务器请求、接收服务
如Web浏览器/服务器：email客户端/服务器
服务端为主，有所有资源的客户端为从，它请求的资源都来自服务端（比如发送电子邮件，我的电子邮件的应用是客户端，是这种应用的客户端，电子邮件的服务器是服务端）（客户端是主动的，服务器是被动的，服务器必须对客户端有所反应）（客户端后运行，服务端先运行）
存在可扩展性问题和可靠性问题
对等（peer-peer）模式（P2P）
很少（甚至没有）专门的服务器
如Gnutella、kaZaA、EMule
每个节点既是客户端又是服务器
可扩展性强，分布式通信
服务
采用网络设施的面向连接服务
目标
在端系统之间传输数据，中间的路由器不用维护主机间的通信关系
握手
在数据传输之前做好准备
TCP-传输控制协议（Transmission Control Protocol）
Internet上面面向连接的服务
TCP服务（RFC 793）
特性
可靠地、按顺序地传送数据
确认和重传
可靠：不重复、不丢失、不出错、不失序
流量控制
发送方不会淹没接收方
拥塞控制
当网络拥塞时，发送方降低发送速率
握手
应用
HTTP（Web)、FTP(文件传送）、TeInet（远程登录）、SMTP（email）
采用基础设施的无连接服务
目标
在端系统之间传输数据
UDP-用户数据报协议（User Datagram Protocol）
无连接服务
特性
无连接
不握手，直接发送
不可靠数据传输
无流量控制
无拥塞控制
应用
实时多媒体/流媒体、远程会议、DNS、Internet电话、查询
1.3网络核心
路由器的网状网络
基本问题：数据怎样通过网络进行传输
电路交换
为每个呼叫预留一条专有电路：如电话网
端到端的资源被分配给从源端到到目标端的呼叫叫“call”
独享资源：不共享
每次呼叫一旦建立起来就能够保证性能
如果呼叫没有数据发送，被分配的资源就会被浪费
为呼叫分配片
如果某次呼叫没有数据，则其资源片处于空闲状态
网络资源（如带宽）被分成片
频分复用（Frequency-division-multiplexing）
时分复用（Time-division-multiplexing）
波分复用（Wave-division-multiplexing）
电路交换不适合计算机之间的通信
原因
连接建立时间长
计算机之间的通信有突发性，如果使用电路交换，则浪费的片较多
即使这个呼叫没有数据传递，所占据的片也不能被别的呼叫使用
分组交换
分组：将要传送的数据分成一个个单位
将分组从一个路由器传到相邻路由器（hop），一段段最终从源端传到目标端
每段：采用链路的最大传输能力（带宽）
网络带宽资源不再分位一个个片，传输时使用全部带宽
资源共享，按需使用
存储-转发：分组每次移动一跳（hop）
在转发之前，节点必须收到整个分组
在传输到下一个链路之前，整个分组必须到达路由：存储-转发
延迟比电路交换（线路交换）要大
排队时间
如果到达速率>链路的输出速率：
分组就会排队，等待传输
如果路由器的缓冲用完了，分组就会被抛弃
统计多路复用（特殊的时分）
随机划分时间片，没有固定模式（电路交换的TDM时间划分是固定的）
允许更多的用户使用网络
分组方式（按照有无网络层的连接）
数据报网络
不要维护主机之间的通讯关系
无连接（在通信之前无需建立起一个连接，有数据就会传输）
分组的目标地址决定下一跳
路由器根据分组的目标地址进行路由
在不同阶段，路由可以改变
每一次分组都单独路由（路径不一样，可能失序）
类似：问路
虚电路网络
要维护主机之间的通讯关系
有连接，网络层的连接（在呼叫建立时决定路径，在整个呼叫中路径保持不变）
每次分组都带有标签（虚电路标识 VCID），标签决定下一跳
路由器维持每一个呼叫的状态信息
分组交换 vs 电路交换
分组交换是“突发数据的胜利者”
适合对突发式数据传输
资源共享
简单，不用建立呼叫
分组交换过度使用会造成网络堵塞：分组延时和丢失
对可靠地数据传输需要协议来约束：堵塞控制
电路交换服务
保证音频/视频应用需要的带宽
预约服务（线路交换）vs 按需服务（分组交换）
核心功能
路由（全局）routing
决定分组采用的源到目标的路径
路由算法
转发（局部）forwarding
将分组从路由器的输入链转到输出链路
查路由表决定怎么走
网络的分类
电路交换网络
FDM（好像跑道）
TDM（好像跳大绳，一人一过）
WDM
分组交换网络
虚电路网络
数据报网络
1.4 接入网和物理媒介
接入网
怎样将端系统和边缘路由连接（从历史角度分类）
住宅接入网络
modem
拨号调制解调器（modulate-demodulate）
56Kbps的速率直接接入路由器（通常更低）
不能同时上网和打电话；不能总是在线
将上网数据调制加载音频信号上，在电话线上传输，在局端将其中的数据解调出来；反之亦然
调频
调幅
调相位
综合调剂
线缆网络（电视）
越往上越是光纤，越往下越是同轴电缆
有线电视信号线缆双向改造
FDM：在不同的频段传输不同信道的数据
数字电视和上网数据（上下行）
混合光纤同轴电缆 HFC（hybrid fiber coax）
非对称：最高30Mbps的下行传输速率，2Mbps上行传输速率
线缆和光纤网络将各个家庭用户接入到 ISP（因特网服务提供商）路由器
各用户共享到线缆头端的接入网络
与DSL不同，DSL每个用户一个专用线路到CO（central office）（中心局，电话总局）
电缆模式（电视）
越往上越是光纤，越往下越是同轴电缆
FTTH
光纤到户
DSL(digital subscriber line)用户数字电路，电话服务
采用现存的交换局DSLAM的电话线
DSL线路上的数据被传到互联网
DSL线路上的语音被穿到电话网
2.5 Mbps上行传输速率（typically < 1 Mbps）
24 Mbps下行传输速率（typically < 10 Mbps）
家庭网络
单位接入网络（学校，公司）
Ethernet（以太网）
经常被企业或者大学等机构采用
10 Mbps，100Mbps，1Gbps，10Gbps传输率
现在，端系统经常直接接到以太网交换机上
无线接入网络
各无线端系统共享无线接入网络（端系统到无线路由器）-------通过基站或者叫接入点
无线局域（WLAN）
802.11b/g（WiFi）：11，54 Mbps传输速率
无线广域
（由电信运营商提供）cellular：蜂窝网
以基站位中心（base station）
通信距离：10-20km
1-10 Mbps
3G，4G，LTE
物理媒体
分类
导引型媒体（guided media）
看得见摸得着
传送得更远
信号沿着固体媒介被导引
同轴电缆、光纤、双绞线
双绞线（twisted pair）TP
两根绝缘铜导线拧合
5类：100Mbps以太网，Gbps千兆以太网
6类：10Gbps万兆以太网
分类
屏蔽双绞线
非屏蔽双绞线
同轴电缆（coaxial cable）
两根同心的铜导线
双向
共享的媒介
基带电缆
电缆上一个单个通道
Ethernet
宽带电缆
电缆上有多个通信信号
HFC
光缆（fiber optic cable）
光脉冲，每个脉冲表示一个bit，在玻璃纤维中传输
高速（带宽极宽）
点到点的高速传输（如10 Gbps-100Gbps传输速率）
低误码率
在两个中继器之间有很长的距离，不受电磁噪声干扰
安全
非导引型媒体（unguided media）
特性
开放的空间传输电磁波或者光信号，在电磁波或者光信号中承载数字数据
传播环境效应（传输过程受干扰）
反射
吸收
干扰
双向
无需物理”线缆“
类型
地面微波
WLAN（无线局域网）
WiFi
wide-area
蜂窝（cellular）
卫星
kbps-45Mbps每个通道（或者多个聚集通道）
270msec 端到端延迟
同步静止卫星和低轨卫星
定义
连接每个发送-接收对之间的物理媒体
1.5 Internet结构和ISP
互联网的结构：网络的网络
端系统通过接入ISPs（Internet Service Providers）连接到网络
住宅、公司、学校的ISPs
接入ISPs相应的必须是互联的
因此任何两个端系统可互相发送分组到对方
导致的”网络的网络“非常复杂
发展和演化是通过经济的和国家的政策来驱动的
让我们采用渐进方法来描述当前互联网的结构
给定数百万接入ISPs，如何将它们互联到一起
在网络的最中心，一些为数不多的充分连接的大范围网络（分布广、节点有限、但是很多之间有着多重连接）
”tier-“commercial ISPs（商业ISPs）
例如：Level 3、Sprint、AT&T、NTT
国家或者国际的覆盖
content provider network（内容提供商网络）
例如：Google
将它们的数据中心接入ISP，方便周边用户访问；通常私有网络之间用专网绕过第一层ISP和区域ISPs
发展过程
1.全连接
将每两个ISPs直接相连
不可扩展（Scalability）
需要n平方复杂度的连接
2.将每个接入ISP都连接到全局ISP（global ISP）（全局范围内覆盖）
客户ISPs和提供者ISPs有经济合约
3.合作&竞争
竞争：但是，如果全局ISP是可行的业务，就会有竞争者（有利可图就有竞争者）
合作：通过ISP之间的合作可以完成业务的扩展，会有互联，对等互联的结算关系
access net：接入网--------peering link：互联-----------Internet exchange point：互联网交换点
4.细分：业务会有细分（全球接入和区域接入），区域网络将出现，用于将接入ISPs连接到全局ISPs
regional net：区域网
5. 内容提供商网络（Internet Content Provider）ICP
例如：Google、Microsoft、Akamai
会构建它们自己的网络，将它们的服务、内容更加靠近用户端，向用户提供更好的服务，减少自己的运营支出
也要接入ISP
总结
结构：松散的层次结构
中心：第一层ISP（如UUNet，BBN/Genuity,Sprint,AT&T)国家/国际覆盖，速率极高
直接与其他第一层ISP相连
通过peer或者IXP相连接
与大量的第二层ISP和其他客户网络相连
第二层ISP：更小一些的（通常是区域性的）ISP
与一个或者多个第一层ISPs，也可能与其他第二层ISP相连
第三层ISP与其它本地ISP
接入网（access net）（与端系统最近）或者本地ISP（local ISP）
最后接入终端
一个分组要经过许多网络
ICP
很多内容提供商（如：Google、Akamai）可能会部署自己的网络，连接自己的在DC（数据中心），走自己的数据
连接若干local ISP和各级（包括一层）ISP，更加靠近用户
经济考虑：少付费----------用户体验考虑：更快
ISP之间的连接
POP
高一层ISP面向客户网络的接入点，涉及费用结算
例如：一个低层ISP接入多个高层ISP，多宿（multi home）
对等接入
两个ISP对等互接，不涉及费用结算
IXP
多个对等ISP互联互通之处，通常不涉及费用结算
对等接入
ICP自己部署专用网络，同时和各级ISP连接
1.6 分组延时、丢失和吞吐量
分组丢失和延时是怎样发生的
在路由器缓冲区的分组列队的时候
分组到达链路的速率超过了链路输出的能力
延迟：分组等待排到队头，然后再传输
延迟：传输也有时间
丢失：可用的缓冲区有限---------分组到达时，如果没有可用的缓冲区，则该分组被丢掉
延时
四种分组延时
节点处理 延时
检查bit级错误
检查分组首部和决定将分组导向何处
排队 延时
在输出链路上等待输出的时间
依赖于路由器的拥塞程度
R=链路宽度（bps）
L=分组长度（bits）
a=分组到达队列的平均速率（单位时间内到达的分组数）
流量强度=La/R
La/R~0
平均排队延时很小（到的速度小，出的速度大）
La/R->1
延时变得很大
La/R>1
比特到达队列的速率超过了从该队列输出的速率，平局排队延时趋向无穷大
设计系统时，流量强度不能大于1！
传输 延迟
R=链路带宽（bps）
L=分组长度（bits）
将分组发送到链路上的时间=L/R
存储转发延时
传播延时
d=物理链路的长度
s=在媒体上的传播速度（~2x10^8 m/sec）
传播延时=d/s
上述延时可用车队类比
WAN
LAN
每一跳延时时间
处理时延影响吞吐量
Traceroute诊断程序
提供从源端，经过路由器，到目的地的延时测量
例如：traceroute：gaia.cs.umass.edu to www.eurecom.fr
丢失
链路的队列缓冲区容量有限
当一个分组到达一个满的队列时，给分组将会丢失
丢失的分组可能会被前一个节点或源端系统重传，或根本不重传
以太网不提供上一节点重传服务（主要看链路认为自己是否可靠，以太网认为自己的底层很可靠，所以没有重传机制；wifi、无线链路认为自己的底层不可靠，所以提供重传机制）
通过UDP放出去的分组，源端系统也不会重传（TCP会重传）
只有应用层会发起重传，网络层和链路层没有重传机制
吞吐量（性能指标之一）
定义
在源端和目标端之间传输的速率（数据量/单位时间）
瞬间吞吐量
在一个时间点的速率
平均吞吐量
在一个长时间内的平均值
指A到B，单位时间内传输出去，对方能够收到的有效输出量
取决于Rs---------取决于RC（吞吐量）
瓶颈链路
端到端路径上，限制端到端吞吐的链路
多链路
1.7 协议层次服务模型
网络是一个非常复杂的系统
网络功能繁杂：数字信号的物理承载、点到点、路由、rbt、进程分区、应用等
现实来看，网络的许多构成元素和设备
主机
路由器
各种媒体的链路
应用
协议
硬件、软件
问题是：如何组织和实现这个功能复杂的网络功能
层次化方式实现复杂网络功能
将网络复杂的功能，分为功能明确的层次，每一层实现了其中一个或一组的功能，功能中有其上层可以使用的功能：服务（服务是功能的一部分）
协议及协议的功能：本层协议实体互相交互，执行本层的协议动作，目的是实现本层功能，通过接口为上层提供更好的服务
协议的实现方式：在实现本层协议的时候，直接利用了下层所提供的服务
协议是对等的水平关系，服务是垂直的关系
本层服务
借助下层服务实现本层协议实体之间交互带来的新功能（上层可以利用）+更下层所提供的服务
服务和访问点
服务（Service）
低层实体向上层实体提供它们之间的通信能力
服务提供者（Service provider）
服务用户（Service user）
原语（primitive）
下层使用下层服务的形式，高层使用低层提供的服务，以及下层向高层提供服务都是通过服务访问原语来进行交互的-----形式
就是提供服务的形式（到底需要什么服务）
服务访问点SAP（Service Access Point）
上层使用下层提供的服务通过层间的接口-------地点
例子：邮箱
地址（address）
下层的一个实体支撑着上层的多个实体，SAP有标志不同上层实体的作用
用于下层的服务提供者，区分不同的上层用户，传递信息
例子：传输层的SAP：端口（port）
服务的类型（服务的形式）
面向连接的服务（Connection-oriented Service）
连接（Connection）
两个通信实体为进行通信而建立的一种结合
过程
建立连接、通信、拆除连接
例子
网络层的连接被成为虚电路
TCP
适用范围
适合大的数据块的传输，不适合小的零星报文
特点
保守
服务类型
可靠的数据流
传送页面（可靠的获得，通过接收方的确认）
可靠的字节流
远程登录
不可靠的连接
数字化声音
无连接的服务（Connectionless Service）
两个对等层实体在通信前不需要建立一个连接，不预留资源；不需要通信双方都是活跃的（例：寄信）
特点
不可靠
可能重复
可能失序
IP分组，数据包
UPD
适用范围
适合传输零星数据
服务类型
不可靠的数据报
电子方式的函件
有确认的数据报
挂号信
请求回答
信息查询
服务和协议的区别
服务（Service）：低层实体向上层实体提供它们之间的通信的能力，是在SAP上通过原语（primitive）来操作（SAP告诉向哪个上层提供服务，原语告诉提供什么服务），垂直
协议（protocol）：对等层实体（peer entity）之间互相通信的过程，需要遵循的规则的集合，水平
服务和协议的联系
本层协议的实现要靠下层提供的服务来实现
本层实体通过协议为上层提供更高级的服务
数据单元（DU ）
上层要传的数据对于本层来说是SDU（服务数据单元），本层的SDU加上头部信息就是PDU（协议数据单元），头部信息有一部分是ICI转换过去的，有一部分是本层附加上去的
1对多的关系：上层发送的SDU太大了，在下层拆解成几个小的SDU
多对1的关系：上层发送了很多非常小的SDU，下层将它们组合
1对1的关系：理想，非常好的状态
分层处理和实现复杂系统的好处
概念化
结构清晰，便于标识网络组件，以及描述其互相关系
分层参考模型
结构化（化繁为简）
模块化更易于维护和系统升级
改变某一层次服务的实现不影响系统中的其他层次
对于其他层次而言是透明的（指不可见）
如改变登记程序并不影响系统的其他部分
改变两个秘书使用的通信方式不影响2个翻译的工作
改变两个翻译使用的语言也不影响上下2个层次的工作
分层思想被认为有害的地方
效率比较低
Internet协议栈（从下而上理解）
应用层：网络应用（报文message）
为人类用户或其他应用进程提供网络应用服务
FTP、SMTP、HTTP、DNS
应用层可以在传输层所提供的服务的基础上，完成应用报文和应用报文之间的交互，完成以后想干嘛干嘛
传输层：主机之间的数据传输（报文段segment）
在网络层提供的端到端通信的基础上，细分为进程到进程，将不可靠的通信变成可靠的通信
TCP、UDP
传输层在网络层之上，在网络层主机到主机的服务的基础之上，完成进程到进程的区分，并把网络层所提供的不可靠的通信服务变成可靠的通信服务
可靠：不出错，不重复、不丢失、不失序
网络层：为数据报从源到目的地选择路由（分组packet/datagram数据报）
主机主机之间的通信，端到端通信不可靠
IP（做转发）、路由协议（做路由）
重要的两个功能：转发（局部）和路由（全局）
在链路层所提供的，在相邻两点间数据传输的基础之上，传输以分组为单位的端到端的数据传输（源主机到目标主机）E2E（end system to end system）
链路层：相邻网络节点间的数据传输（帧frame）
点对对协议PPP、802.11（WiFi）、Ethernet
在物理层所提供的服务的基础上，在相邻的两点之间传输以帧为单位的数据（P2P point to point）
物理层：在线路上传送bit
把数字数据转换成物理信号，承载在媒体之上，从一点传到相邻的另外一点，对方的物理层再将接收到的物理信号反转回数字信号
完成相邻两点之间bit的传输
ISO/OSI参考模型(ISO国际标准化组织----提出-----OSI开放系统互联
表示层
允许应用解释传输的数据
例如：加密、压缩、机器相关的表示转换
会话层
数据交换的同步，检查点，恢复
互联网协议栈没有上述两层
这些服务，如果需要的话，必须被应用层实现
在源端做一个大的封装，到交换机的时候两层解封装再封装，到路由器的时候三层解封装再封装，到目标主机完成一个大的解封装
各层次的协议数据单元PDU
应用层
报文（message）
传输层
报文段（segment）：TCP段、UDP段
网络层
分组（packet）（如果无线连接：数据报datagram）
链路层
帧（frame）
物理层
位（bit）
小结
Internet
什么是协议
网络边缘、核心、接入网络
分组交换vs电路交换
Internet/ISP结构
性能：丢失、延时、吞吐量、速率带宽
层次模型和服务模型
小结1
从组成角度看 什么是互联网
边缘
端系统（包括应用）+接入网
核心：网络交换设备+通信链路
协议：对等层的实体通信过程中遵守的规则的集合
格式，次序、动作；语义、语法、时序
为了实现复杂的网络功能，采用分层方式设计、实现和调试
应用层、传输层、网络层、数据链路层、物理层
协议数据单元：报文（message）、报文段（segment）、分组（packet）、帧（frame）、位（bit）
从服务的角度 看互联网
通信服务基础设施
提供的通信服务：面向连接、无连接
应用
应用之间的交互
C/S模式
P2P模式
小结2
数据交换
分组交换
电路交换
比较 线路交换和分组交换
分组交换的2种方式
虚电路
数据报
接入网和物理媒介
接入网技术
住宅
ADSL、拨号、cable modem
单位
以太网
无线接入方式
物理媒介
光纤、同轴电缆、以太网、双绞线
ISP层次模型
小结3
分组交换网络延迟和丢失是如何发生的
延迟的组成：处理、排队、传输、传播
网络的分层体系结构
分层体系结构
服务
协议数据单元
封装与解封转
第二章 应用层
2.1 应用层协议原理
创建一个新的网络应用
编程
在不同的端系统上运行
通过网络基础设施提供的服务，应用进程彼此通信
如Web
Web服务器软件与浏览器软件通信
网络核心中没有应用层软件
网络核心没有应用层功能
网络应用只在端系统上存在，快速网络应用开发和部署
网络应用的体系结构（按照应用进程和应用进程的沟通方式来看）
客户-服务器模式（C/S:client/server）
服务器
一直运行
固定的IP地址和周知的端口号（约定）
扩展性：服务器场
数据中心进行扩展
扩展性差
客户端
主动与服务器通信
与互联网有间歇性的连接
可能是动态的IP地址
不直接与其他客户端通信
可扩展性比较差
随着访问用户的增加，性能达到一定阈值之后，会急剧性的下降
可靠性比较差
对等模式（P2P：Peer To Peer）
（几乎）没有一直运行的服务器
任意端系统之间可以进行通信
每一个节点既是客户端又是服务器
自扩展性
新peer节点带来新的服务能力，当然也带来新的服务请求
参与的主机间歇性连接且可以改变IP地址
难管理
例如：GnutElla、迅雷
混合体：客户-服务器和对等体系结构
Napster
文件搜索：集中
主机在中心服务器上注册其资源
主机向中心服务器查询资源位置
文件传输：P2P
任意peer节点之间
即时通信
在线检测：集中
当用户上线时，向中心服务器注册其IP地址
用户与中心服务器联系，以找到其在线好友的位置
两个用户之间的聊天：P2P
进程通信
进程
在主机上运行的应用程序
分类
客户端进程
发起通信的进程
服务器进程
等待连接的进程
在同一个主机内，使用进程间通信机制通信（操作系统定义）
不同主机，通过交换报文（Message）来通行
使用OS提供的通信服务
按照通信协议交换报文
借助传输层提供的服务
注意：P2P架构的应用也有客户端进程和服务器进程之分
分布式进程通信需要解决的问题
问题一：进程标示和寻址问题（服务客户）
解决方法
进程为了接收报文，必须有一个标示，即SAP（发送也需要标示）
主机：唯一的32位IP地址
仅仅有IP地址不能够唯一的标示一个进程，在一台端系统上有很多应用进程在运行
所采用的传输层协议：TCP or UDP
端口号（Port Numbers）（16个bit）
一些知名端口号的例子
HTTP：TCP 80 Mail：TCP25 ftp：TCP 2
一个进程：用IP+port标示 端节点
本质上，一些主机进程之间的通信由2个端节点构成
IP地址+TCP/UDP端口号
问题二：传输层-应用层提供服务是如何（服务）
位置：层间界面的SAP（TCP/IP：socket）
形式：应用进程接口API（TCP/IP：socket API）
问题三：如何使用传输层提供的服务，实现应用进程之间的报文交换，实现应用（用户使用服务）
定义应用层协议：报文格式、解释、时序等
编制程序，使用OS（操作系统）提供的API（应用程序接口），调用网络基础设施提供的通信服务报文，实现应用时序等
应用层协议
定义了：运行在不同端系统上的应用进程如何互相交换报文
交换的报文类型：请求和应答报文
各种报文类型的语法：报文中的各个字段及其描述
字段的语义：即字段取值的含义
进程何时、如何发送报文及对报文进行相应的规则
应用协议仅仅是应用的一个组成部分
Web应用：HTTP协议、web客户端、web服务器、HTML
公开协议
由RFC（request for comments）文档定义
允许互相操作
如HTTP、SMTP
专用（私有）协议
协议不公开
如：Skype（通过互联网打电话）
衡量指标：应用层需要传输层提供什么样的服务
数据丢失率
有些应用则要求100%的可靠数据传输（如文件）
有些应用（如音频）能容忍一定比例以下的数据丢失
延迟
一些应用出于有效性考虑，对数据传输有严格的时间限制
Internet电话、交互式游戏
延迟、延迟差
吞吐
一些应用（如多媒体）必须需要最小限度的吞吐，从而使得应用能够有效运转
一些应用能充分利用可供使用的吞吐（弹性应用）
安全性
机密性
完整性
可认证性（鉴别）
常见应用对传输服务的要求
Internet传输层提供的服务
TCP服务
可靠的传输服务
流量控制：发送方不会淹没接收方
拥塞控制：当网络出现拥塞时，能抑制发送方
不能提供的服务：时间保证、最小吞吐保证和安全
面向连接：要求在客户端进程和服务器进程之间建立连接
UDP服务
不可靠数据传输
不提供的服务：可靠，流量控制，拥塞控制，时间、宽带保证、建立连接
为什么要有UDP
UDP存在的必要性
能够区分不同的进程，而IP服务不能
在IP提供的主机到主机、端到端功能的基础上，区分了主机的应用进程
无需建立连接，省去了建立连接的时间，适合事务性的应用
不做可靠性的工作，例如检错重发，适合那些对实时性要求比较高而对正确性要求不高的应用
因为为了实现可靠性（准确性、保序等），必须付出时间的代价（检错重发）
没有拥塞控制和流量控制，应用能够按照设定的速度发送数据
而在TCP上面的应用，应用发送数据的速度和主机向网络发送的实际速度不一致的，因为有流量控制和拥塞控制
Internet应用及其应用协议和传输协议
安全TCP
TCP&UDP
都没有加密
明文通过互联网传输，甚至密码
SSL
在TCP上面实现，提供加密的TCP连接
私密性
数据完整性
端到端的鉴别
HTTPS
SSL在应用层
应用采用SSL库，SSL库使用TCP通信
SSL socket API
应用通过API将明文交给socket，SSL将其加密在互联网上传输
2.2 Web and HTTP
一些术语
Web页：由一些对象组成
对象可以是HTML文件，JPEG图像、Java小程序、声音剪辑文件等
Web页含有一个基本的HTML文件，该HTML文件又包含若干对象的引用（链接）
通过URL（通用资源定位符）对每个对象进行引用
访问协议、用户名、口令号、端口等
URL格式
http默认80号端口，ftp默认21号端口
HTTP概述
HTTP:超文本传输协议
Web的应用层协议
客户端/服务器模式
客户：请求、接收和显示Web对象的浏览器
服务器：对请求进行响应，发送对象的Web服务器
HTTP 1.0：RFC 1945
HTTP1.1：RFC 2068
使用TCP
客户端发起一个与服务器的TCP连接（建立套接字），端口号为80
服务器接受客户的TCP连接
在浏览器（HTTP客户端）与Web服务器（HTTP服务器）交换HTTP报文（应用层协议报文）
TCP连接关闭
HTTP是无状态的
维护状态的协议很复杂
必须维护历史信息（状态）
如果服务器/客户端死机，它们的状态信息必须是一致
无状态的服务器能够支持更多的客户端
服务器并不维护关于客户的任何信息
HTTP连接
非持久HTTP
最多只有一个对象在TCP上发送
下载多个对象需要多个TCP连接
HTTP/1.0使用非持久连接
缺点
每个对象要2个RTT
操作系统必须为每个TCP连接分配资源
但浏览器通常打开并行TCP连接，以获取引用对象
持久HTTP
多个对象可以在一个（在客户端和服务器之间的）TCP上连接
HTTP/1.1默认使用持久连接
服务器在发送响应后，仍保持TCP连接状态
在相同客户端和服务器之间的后续请求和响应报文通过相同进行传送
客户端在遇到一个引用的时候，就可以尽快发送该对象的请求
分类
流水（pipeline）方式的持久HTTP
HTTP/1.1的默认模式
客户端遇到一个引用对象就立即产生一个请求
所有引用（小）对象只花费一个RTT是可能的
非流水方式的持久HTTP
客户端只能在收到前一个响应后才能发出新的请求
每个引用对象花费一个RTT
HTTP请求报文
两种类型的HTTP报文：请求、响应
HTTP请求报文
ASCII（人能阅读）
通用格式
子主题
报文格式
子主题
三部分
请求行
首部行
结束行
实体体
提交表单输入
Post方式
网页通常包括表单输入
包含在实体主体（entify body）中的输入被提交到服务器
客户端向服务器提供相应的信息
URL方式
方法：GET
输入通过请求行的URL字段上载
方法类型
HTTP1.0常用的命令
GET
获取，客户端向服务器请求
POST
客户端向服务器提交
HEAD
要求服务器在响应报文中不包含请求对象->故障跟踪
客户端仍然向服务器请求，但请求的是HTML的头部（HTML对象包括头部和body）
维护或者建立索引的时候用
HTTP1.1
GET、POST、HEAD
PUT
将实体主体的文件上载到URL字段规定的路径
像服务器提交相应的对象
通常做网页内容的维护
DELETE
删除URL字段规定的文件
删除相关的对象
put一般是修改，get是查询，post是增加，delete是删除
HTTP响应报文
HTTP响应状态码
位于服务器->客户端响应报文中的首行
例子
200 OK
请求成功，请求对象包含在响应报文的后续部分
301 Moved Permanently
请求的对象已经被永久转移了：新的URL在响应报文的Location：首部行中指定
客户端软件自动用更新的URL去获取对象
400 Bad Request
一个通用的差错代码，表示该请求不能被服务器解读
404 Not Found
请求的文档在该服务器上没有找到
505 HTTP Version Not Supported
改进HTTP的无状态-----用户-服务器状态：cookies
大多数主要的门户网站使用cookies
4个组成部分
1）在HTTP响应报文中有一个cookie的首部行
2）在HTTP请求报文中有一个cookie的首部行
3）在用户端系统中保留有一个cookie文件，由用户的浏览器管理
4）在Web站点有一个后端数据库
例子
Susan总是用同一个PC使用Internet Explore上网
她第一次访问了一个使用了Cookie的电子商务网站
当最初的HTTP请求到达服务器时，该Web站点产生一个唯一的ID，并以此作为索引在它的后端数据库中产生一个项
Cookies能够带来什么
用户验证
购物车
推荐
用户状态（Web e-mail)
如何维护状态
协议端节点：在多个事务上，发送端和接收端维持状态
cookies：http报文携带状态信息
Cookies与隐私
Cookies允许站点知道许多关于用户的信息
可能将它知道的东西卖给第三方
使用重定向和cookie的搜索引擎还能知道用户更多的信息
如果通过某个用户在大量站点上的行为，了解其个人浏览方式的大致模式
广告公司从站点获取信息
Web缓存（代理服务器）
目标
不访问原始服务器，就满足客户的请求
用户设置浏览器：通过缓存访问Web
浏览器将所有的HTTP请求发给缓存
在缓存中的对象，缓存直接返回对象
如果对象不在缓存，缓存请求原始服务器，然后再将对象返回给客户端
缓存既是客户端又是服务器
通常缓存是由ISP安装（大学、公司、居民区ISP）
为什么要使用web缓存？
降低客户端的请求响应时间
可以大大减少一个机构内部网络与Internet接入链路上的流量
（服务器负载降低）互联网大量采用了缓存：可以使较弱的ICP也能够有效提供服务
缓存示例
解决方法1---------贵
解决方法2------缓存
对缓存的改进：条件GET方法
目标：
如果缓存器中的对象拷贝是最新的，就不要发送对象
2.3 FTP
文件传输协议FTP
向远程主机上传输文件或从远程主机接收文件
客户/服务器模式
客户端：发起传输的一方
服务器：远程主机
ftp：RFC 959
ftp服务器：端口号为21
控制连接与数据连接分开
FTP客户端与FTP服务器通过端口21联系，并使用TCP为传输协议
客户端通过控制连接获得身份确认
客户端通过控制连接发送命令浏览远程目录
收到一个文件传输命令时，服务器打开一个到客户端的数据连接
一个文件传输完成后，服务器关闭连接
服务器打开第二个TCP数据连接用来传输另一个文件
控制连接：带外（out of band）传送
FTP服务器维护用户的信息状态：当前路径、用户账号与控制连接对应
FTP命令、响应
2.4 Email
3个主要组成部分
用户代理（客户端软件）
又名“邮件阅读器
撰写、编辑和阅读邮件
如Outlook、Foxmail
输出和输入邮件保存在服务器上
邮件服务器
邮箱中管理和维护发送给用户的邮件
输出报文列队保持待发送邮件报文
邮件服务器之间的SMTP协议：发送email报文
客户：发送方邮件服务器
服务器：接收方邮件服务器
简单邮件传输协议：SMTP【RFC 2821】
使用TCP在客户端和服务器之间的传送报文，端口号为25
直接传输：从发送方服务器到接收方服务器
传输的3个阶段
握手
传输报文
关闭
命令/响应交互
命令：ASCII文本
响应：状态码和状态信息
报文必须是7为ASCII码
举例：Alice给Bob发送报文
1）Alice使用用户代理撰写邮件并发送给bob@someschool.edu
2)Alice的用户代理将邮件发送到她的邮件服务器：邮件放在报文列队中
3）SMTP的客户端打开到Bob邮件服务器的TCP连接
4）SMTP客户端通过TCP连接发送Alice的邮件
5）Bob的邮件服务器将邮件放到Bob的邮箱
Bob调用他的用户代理阅读邮件
邮件报文格式
SMTP：交换email报文的协议
RFC 822：文本报文的标准
报文格式：多媒体扩展
MIME：多媒体邮件扩展（multimedia mail extension）
RFC 2045、2056
在报文首部用额外的行申请MIME内容形式
将不在ACSCII码字符范围内字符，编码为长一点的ASCII码，来隐性代表原字符
邮件访问协议
SMTP：传送到接收方的邮件服务器
邮件访问协议：从服务器访问邮件
POP：邮局访问协议（Post Office Protocol）【RFC 1939】
用户身份确认（代理<->服务器）并下载
端口号110
无状态
上述例子使用”下载并删除”模式
如果改变客户机，Bob不能阅读文件
下载并保留：不同客户机上为报文的拷贝
IMAP：Internet邮件访问协议（Internet Mail Access Protocol）【RFC 1730】
更多特性（更复杂）
在服务器上处理存储的报文
有状态
POP3 vs IMAP
POP3在会话中是无状态的
POP3是本地文件管理文件夹
IMAP服务器将每个报文与一个文件夹联系起来
IMAP允许用户用目录来组织报文
IMAP允许用户读取报文组件
IMAP在会话过程中保留用户的状态
目录名、报文ID与目录名之间的映射
IMAP是远程管理文件夹
HTTP:Hotmail、Yahoo！Mail等
方便
总结
SMTP使用持久连接
SMTP要求报文（首部和主体）为7位ASCII编码
SMTP服务器使用 CRLF.CRLF决定报文尾部
SMTP vs HTTP
HTTP：拉（pull）
SMTP：推（push）
二者都是ASCII形式的命令/相应交互、状态码
HTTP：每个对象封装在各自的响应报文中
SMTP：多个对象包含在一个报文中
子主题
2.5 DNS（Domain Name System）域名系统
DNS的必要性
IP地址标识主机、路由器
但IP地址不好记忆，不便于人类使用（没有意义）
人类一般倾向于使用一些有意义的字符串来标识Internet上的设备
存在着“字符串"-IP地址转换的必要性
人类用户提供要访问机器的”字符串“名称
有DNS负责转换成为二进制的网络地址
DNS需要解决的问题
问题1：如何命名设备
用有意义的字符串：好记、便于人类使用
解决一个平面命名的重名问题：层次化命名
问题2：如何完成名字到IP地址的转换
分布式的数据库维护和响应名字查询
问题3：如何维护：增加或者删除一个域，需要在域名系统中做哪些工作
DNS的历史
ARPANET的名字解决方案
主机名：没有层次的一格字符串（一个平面）
存在着一个（集中）维护站:维护着一张主机名-IP地址的映射文件：Hosts.txt
每台主机定时从维护站取文件
ARPANET解决方案的问题
当网络中主机数量很大时
没有层次的主机名很难分派
文件的管理、发布、查询都很麻烦
DNS总体思想和目标
DNS的主要思路
分层的、基于域的命名机制
若干分布式的数据库完成名字到IP地址的转换
运行在UDP之上的端口号为53的应用服务
不要握手，直接查询
核心的Internet功能，但以应用层协议实现
在网络边缘处理复杂性
DNS主要目的
实现主机名-IP地址的转换（name/IP translate）
其他目的
主机别名到规范名字的转换：host aliasing
邮件服务器别名到邮件服务器正规名字的转换：Mail server aliasing
负载均衡：Load Distribution
问题1：DNS名字空间（The DNS Name Space）
DNS域名结构
一个层面命名设备会有很多重名
采用层次树状结构的命名方式
Internet根被划分为几百个顶级域（top lever domains）
通用的（generic）
.com--.edu--.gov--.int--.mil--.net--.org--.firm--.hsop--.web--.arts--.rec
国家的（countries）
.cn--.us--.nl--.jp
每个（子）域下面可划分为若干子域（subdomains）
树叶是主机
根名字服务器：共有13个根名字服务器（中国没有，日本有）
域名
从本域往上，直到树根
中间使用”.“间隔不同的级别
例如：
snnu.edu.cn
jwxt.snnu.edu.cn
域名的域名：可以用于表示一个域
主机的域名：一个域上的一个主机
域名的管理
一个域管理其下的子域
.jp划分为 ac.jp co.jp
.cn划分为edu.cn com.cn
创建一个新域，必须征得它所属域的同意
域与物理网络无关
域遵从组织界限，而不是物理网络
一个域的主机可以不在一个网络
一个网络的主机不一定在一个域
域的划分是逻辑的，而不是物理的
问题2：解析问题-名字服务器（Name Server）
一个名字服务器的问题
可靠性问题：单点故障
扩展性问题：通信容量
维护问题：远距离的集中式数据库
区域（zone）
区域的划分由区域管理者自己决定
将DNS名字空间划分为互不交互的区域，每个区域都是树的一部分
名字服务器
每个区域都有一个名字服务器，维护者所管辖区域的权威信息（authoritative record）
名字服务器允许被放置在区域之外，以保障可靠性
名字空间划分为若干区域：Zone
权威DNS服务器：组织机构的DNS服务器，提供组织机构服务器（如Web和mail）可访问的主机和IP之间的映射
组织机构可以选择实现自己维护或由某个服务提供商来维护
TLD服务器
顶级域（TLD）服务器：负责顶级域名（如com、org、net）和所有国家级的顶级域名（如cn、jp、uk）
Network solutions公司维护com TLD服务器
Educause公司维护 edu TLD服务器
区域名字服务器维护资源记录
资源记录（recourse records）
作用：维护 域名-IP地址（其他）的映射关系
位置：Name Server的分布式数据库中
RR格式：（domain_name，ttl，type，class，Value）
domain_name：域名
ttl：time to live：生存空间（权威（时间很长很长的无限大），缓冲记录（时间有限）
class类别：对于Internet，值为IN
Value值：可能是数字，域名或ASCII串
Type类别：资源记录的类型
DNS大致工作过程
应用调用 解析器（resolver）
解析器为客户 向Name Server发出查询报文（封装在UDP段中）
Name Server返回响应报文（name/ip)
本地名字服务器（Local Name Server）
并不严格属于层次结构
每个ISP（居民区的ISP、公司、大学）都有一个本地DNS服务器
也称”默认名字服务器“
当一个主机发起一个DNS查询时，查询被送到器本地DNS服务器
起着代理作用，将查询转发到层次结构中
名字解析过程
目标名字在Local Name Server中
情况1：查询的名字在该区域内部
情况2：缓存（cashing）
当本地名字服务器不能解析名字时，联系根名字服务器顺着根-TLD一直找到权威名字服务器
递归查询
名字解析负担都放在当前联络的名字服务器上
问题：根服务器的负担太重
解决：迭代查询（iterated queries）
DNS协议、报文
DNS协议：查询和响应报文的报文格式相同
提高性能：缓存
一旦一个服务器学到了一个映射，就将该映射缓存起来
根服务器通常都在本地服务器中缓存着
使得根服务器不经常被访问
目的：提高效率
可能存在的问题：如果情况变化，缓存结果和权威资源记录不一致
解决方案：TTL（默认2天）
问题3：维护问题：新增一个域ICANN
在上级域的名字服务器中增加两条记录，指向这个新增的子域的域名 和 域名服务器的地址
在新增子域的 名字服务器上，运行名字服务器，负责本域的名字解析：名字->IP地址
例子：在com域中建立一个”Network Utopia“
到注册登记机构注册域名networkutopia.com
需要向该机构提供权威DNS服务器（基本的、和辅助的）的名字和IP地址
登记机构在com TLD服务器中插入两条RR记录
在networkotopia.com的权威服务器中确保有
服务器的www.networkutopia.com的类型为A的记录
用于邮件服务器mail.networkutopia.com的类型为MX的记录
攻击DNS
2.6 P2P应用
纯P2P架构
没有或（极少）一直运行的服务器
任意端系统都可以直接通信
利用peer的服务能力
peer节点间歇上网，每次IP地址都有可能变化
P2P文件共享
两大问题：
如何定位所需资源
如何处理对等方的加入与离开
可能的方案（非结构化P2P）
集中
P2P：集中式目录
最初的“Napster”设计
文件传输是分散的，而定位内容是高度集中的
1）当对等方连接时，它告知中心服务器（下线也要告诉服务器）
IP地址
内容
2）Alice查询“双节棍.MP3”
3)Alice从Bob处请求文件
分散
完全分布式：查询洪泛：GnutElla
全分布式
没有中心服务器
开放文件共享协议
许多GnutElla客户端实现了GnutElla协议
类似于HTTP有许多的浏览器
覆盖网络：图
如果X和Y之间有一个TCP连接，则两者之间存在一条边
所有活动的对等方和边就是覆盖网络
边不是物理链路
给定一个对等方，通常所连接的节点少于10个
GnutElla：协议
在已有的TCP连接上发送查询报文（向所有的邻居发出查询）
对等方转发查询报文（对方也向所有的邻居发出查询）
以反方向返回查询命令
可扩展性：限制范围的洪泛查询
GnutElla：对等方加入
1.对等方X必须首先发现，某些已经在覆盖网络中的其他对等方：使用可用对等方列表
自己维护一张对等方列表（经常开机的对等方IP）
联系维护列表的GnutElla站点
2.X试图与该列表上的对等方建立TCP连接，直到与某个对等方Y建立连接
X向Y发送一个Ping（加入请求）报文，Y转发该Ping报文
4.所有收到Ping报文的对等方以Pong报文响应IP地址，共享文件的数量及总字节数
5.X收到许多Pong报文，然后它能建立其他TCP连接
半分散
混合体：利用不匀称性：KaZaA
每个对等方要么是一个组长，要么隶属于一个组长
对等方与其组长之间有TCP连接
组长对之间有TCP连接
组长跟踪其所有的孩子的内容
组长与其他组长联系
转发查询到其他组长%
获得其他组长的数据拷贝
KaZaA：查询
每个文件有一个（Hash）散列标识码和一个描述符
组长用匹配进行响应
对每个匹配：元数据、散列标识码和IP地址
Torrent（洪流）:节点的组，节点之间交换文件块
如果组长将查询转发给其他组长，其他组长也以匹配进行响应
客户端选择要下载的文件
向拥有文件的对等方发送一个带散列标识码的HTTP请求
非结构化的P2P：混合体：BitTorrent：P2P文件分发
一个文件被分为一个个块246KB
tracker：跟踪torrent中的参与节点
网络中的这些peers发送和接受文件块，互相服务
peer加入torrent
一开始没有块，但是将会通过其他节点，积累文件块
向跟踪服务器注册，获得peer节点列表，与部分peer节点构成邻居关系（“连接”）
当peer下载时，该peer可以同时向其他节点提供上载服务
peer可能会变换用于交换块的peer节点
扰动churn：peer节点可能会上线或者下线
一旦一个peer拥有整个文件，它会（自私的）离开或者保留（利他主义）在torrent中
客户端向其组长发送关键字查询
请求、发送文件块
请求块
在任何给定时间，不同peer节点拥有一个文件块的子集
周期性的，Alice节点向邻居询问他们的拥有哪些文件块的信息
Alice向peer节点请求它希望的文件块，稀缺的文件块
发送块：一报还一报tit-for-tat
Alice向4个peer发送块，这些块向它提供自己最大的带宽服务
其他peer被Alice阻塞（将不会从Alice出获得服务）
每10秒重新评估一次：前4位
每个30秒：随机选择其他peer节点，向这个节点发送块
“优化疏通”这个节点
新选择的节点可以加入这个top4
tit-for-tat
（1）Alice“优化疏通”Bob
（2）Alice变成了Bob的前四位提供者；Bob答谢Alice
（3）Bob变成了Alice的前四位提供者
例子
稀缺资源优先，最高传输速率优先
结构化的P2P：DHT（Distributed Hash Table）
哈希表
DHT方案
环形DHT 以及覆盖网络
Peer波动
例子
文件分发（BitTorrent）
C/S vs P2P
问题：从一台服务器分发文件（大小F）到N个peer需要多少时间
peer节点上下载能力是有限的资源
C/S模式
数量非常少的客户端在请求服务器服务的时候，客户端的下载能力是瓶颈；随着用户数量的增加，服务器的上载带宽是瓶颈
P2P模式
流媒体（KanKan）
VoIP（Skype）
2.7 CDN（Content Distribution Networks）内容分发网络
视频流化服务和CDN：上下文
视频流量：占据着互联网大部分的宽带
Netflix，YouTube，16%的ISP下行流量
~1B YouTube用户，~75M Netflix用户
挑战：规模性---如何服务~1B 用户
单个超级服务器无法提供服务（为什么）
子主题
不同的用户拥有不同的能力(例如：有线接入和移动用户；带宽丰富和受限用户）
解决方案：分布式的，应用层面的基础设施
多媒体：视频
视频：固定速度显示的图像序列
24 images/sec
网络视频特点
高码率：>10x于音频，高的网络带宽需求
可以被压缩
90%以上的网络流量是视频
数字化图像：像素的阵列
每个像素被若干bits表示
编码：使用图像内和图像间的冗余来降低编码的比特数
空间冗余（图像内）
时间冗余（相邻的图像间）
存储视频的流化服务
多媒体流化服务：DASH
DASH：Dynamic Adaptive Streaming over HTTP（在HTTP上的动态自适应流化）
服务器：
将视频文件分割成多个块
每个块独立存储，编码于不同码率（8-10种）
告示文件（manifest file）：提供不同块的URL
客户端：
先获取告示文件
周期性地测量服务器到客户端的带宽
查询告示文件，在一个时刻请求一个块，HTTP头部指定字节范围
如果带宽足够，选择最大码率的视频块
会话中的不同时刻，可以切换请求不同的编码快（取决于当时的可用带宽）
“智能”客户端：客户端自适应决定
什么时候去请求块（不至于缓存挨饿或者溢出）
请求什么编码速率的视频块（当带宽够用时，请求高质量的视频块）
哪里去请求快（可以向离自己近的服务器发送URL，或者向高可用带宽的服务请求）
挑战：服务器如何通过网络向上百万用户同时流化视频内容（上百万视频内容）
选择1：单个的、大的超级服务中心“mega-server”
服务器到客户端路径上跳数较多，瓶颈链路带宽小导致停顿
“二八规律”决定了网络同时充斥着同一个视频的多个拷贝，效率低（付费高、带宽浪费、效果差）
单点故障、性能瓶颈
周边网络的拥塞
评述：相当简单，但是这个方法不可扩展
选择2：通过CDN，全网部署缓存节点，存储服务内容，就近为用户提供服务，提高用户体验
enter deep：将CDN服务深入到许多接入网
更接近用户，数量少，离用户近，管理困难
Akamai，1700个位置
bring home：部署在少数（10个左右）关键位置，如将服务器安装于POP附近
采用租用线路将服务器簇连接起来
Limelight
在CDN节点中存储内容的多个拷贝
用户从CDN中请求内容
重定向到最近的拷贝，请求内容
如果网络路径堵塞，可能选择不同的的拷贝
让内容靠近用户，内容加速
互联网络主机-主机之间的通信作为一种服务向用户提供（CDN在网络边缘，应用层）
OTT挑战：在拥塞的互联网上复制内容
从哪个CDN节点中获取内容
用户在网络拥塞时的行为
在哪些CDN节点中存储内容
2.8 TCP套接字（Socket）编程
2.9 UDP套接字编程
第三章 传输层
3.1 概述和传输层服务
传输服务和协议
为运行在不同主机上的应用进程提供逻辑通信
传输协议运行在端系统
发送方：将应用层的报文分成报文段，然后传递给网络层
接收方：将报文段重组成报文，然后传递给应用处
有多个传输层协议可供选择
Internet： TCP和UDP
传输层vs网络层
网络层服务：主机之间的逻辑通信
传输层服务：进程之间的逻辑通信
依赖于网络层的服务
延时、带宽
并对网络层的服务进行增强
数据丢失、顺序混乱、加密
类比：东西2个家庭的通信
Ann家的12个小孩给Bill家的12个小孩发信
主机=家庭
进程=小孩
应用层报文=信封中的信件
传输协议=Ann和Bill
为家庭小孩提供复用解复用服务
网络层协议=邮政服务
家庭=家庭的邮包传输服务
有些服务是可以加强的：不可靠->可靠：安全 但有些服务是不可以被加强的：带宽，延迟
Internet传输层协议
可靠的、保序的传输：TCP
多路复用、解复用
拥塞控制
流量控制
建立连接
不可靠、不保序的传输：UDP
多路复用、解复用
没有为尽力而为的IP服务添加更多的其他额外服务
都不提供的服务
延时保证
带宽保证
3.2 多路复用和解复用
在发送方主机多路复用
从多个套接字接收来自多个进程的报文，根据套接字对应的IP地址和端口号等信息对报文段用头部加以封装（该头部信息用于以后的解复用）
在接收方主机多路解复用
根据报文段的头部信息中的IP地址和端口号将接收到的报文段发给正确的套接字（和对应的应用进程）
多路解复用工作原理
解复用作用：TCP或者UDP实体采用哪些信息，将报文段的数据部分交给正确的socket，从而交给正确的进程
主机收到IP数据报
每个数据报有源IP地址和目标IP地址
每个数据报承载一个传输层报文段
每个报文段有一个源端口号和目标端口号
主机联合使用IP地址和端口号将报文段发送给合适的套接字
无连接（UDP）多路解复用
创建套接字
服务器端创建本地套接字，客户端创建本地套接字
在接收端，UDP套接字用二元组标识（目标IP地址，目标端口号）
当主机接收到UDP报文段
检查报文段的目标端口号
用该端口号将报文段定位给套接字
如果两个不同源IP地址/源端口号的数据报，但是有相同的目标IP/目标端口号，则被定位到相同的套接字
回顾：
创建拥有本地端口号的套接字
当创建UDP段采用端口号，可以指定
目标IP地址
目标端口号
当主机接收到UDP段时
检查UDP段中的目标端口号
将UDP段交给具备那个端口号的套接字
面向连接（TCP）的多路复用
TCP套接字：四元组本地标示
源IP地址
源端口号
目标IP地址
目标端口号
解复用：接收主机用这四个值来将数据报定位到合适的套接字
服务器能够在一个TCP端口同时多个TCP套接字
每个套接字由其四元组标识（有不同的源IP和源PORT）
web服务器对每个连接客户端有不同的套接字
非持久对每个请求有不同的套接字
多线程web server
一个进程下面可能有多个线程：由多个线程分别为客户提供服务
在这个场景下，还是根据4元组决定将报文段内容同一个进程下的不同线程
解复用到不同线程
3.3 无连接传输UDP
UDP（User Datagram Protocol用户数据报协议）
“no frills”，“bare bones”Internet传输协议
“尽力而为”的服务，报文段可能
丢失
送到应用进程的报文乱序
无连接
UDP发送端和接收端之间没有握手
每个UDP报文段都被独立的处理
UDP被用于
流媒体（丢失不敏感，速率敏感，应用可控制传输速率）
DNS
SNMP（简单网络管理协议）
在UDP上实现可靠传输
在应用层增加可靠性
应用特定的差错恢复
UDP报文格式：
为什么要有UDP
不建立连接（会增加延时）
简单：在发送端和接收端没有连接状态
报文段的头部很小（开销小）
无拥塞控制和流量控制
UDP可以尽可能快的发送报文段
应用->传输速率=主机->网络速率
UDP校验和
目标：检测在被传输报文段中的差错（比如特反转）
加反加判，溢出回卷
发送方：
将报文段的内容视为16bit的整数
校验和：报文段加法和（1的补运算）
发送方将校验和放在UDP的校验和字段
接收方
计算接收到的报文段的校验和
检查计算出校验和与校验和字段的内容是否相等
不相等：检测到差错
相等：没有检测到差错（但也许还是有差错---残存错误）
3.4 可靠数据传输的原理
rdt在应用层、传输层和数据链路层都很重要
是网络top 10问题之一
信道的不可靠特点决定了可靠数据传输协议（rdt）的复杂性
问题描述
我们将
渐增式地开发可靠数据传输协议（rdt）的发送方和接收方
只考虑单向数据传输
但控制信息是双向流动的
双向的数据传输问题实际上是2个单向数据传输问题的综合
使用有限状态机（FSM）来描述发送方和接收方
状态
在该状态时，下一个状态只由下一个事件唯一确定
引起状态变迁的事件/状态变迁时（协议）采取的动作
Rdt1.0：在可靠信道上的可靠数据传输
下层的信道是完全可靠的
没有比特出错
没有分组丢失
接收方和发送方的FSM
发送方将数据发送到下层信道
接收方从下层信道接收数据
Rdt2.0：具有比特差错的信道
下层信道可能会出错：将分组中的比特翻转
用 校验和 来检验 比特差错
问题：怎样从差错中恢复
确认（ACK）：接收方显式地告诉发送方分组已被正确接收
否定确认（NAK）：接收方显式地告诉发送方分组发生了差错
发送方接收到NAK后，发送方重传分组
Rdt2.0中的新机制：采用 差错控制编码 进行差错检测
发送方 差错控制编码、缓存
接收方使用编码检错
接收方的反馈：控制报文（ACK、NAK）：接收方->发送方
接收方收到反馈相应的动作
数据、校验和
rdt2.0：没有出错的操作
1.
2.
3.
4.
5.
Rdt2.1
发送方处理出错的ACK/NAK（4个状态）
分组的序号，数据，校验和
接收方处理出错的ACK/NAK(2个状态，一个状态可能有3种事件 ）
讨论
发送方
在分组中加入序列号
两个序列号（0,1）就足够了
一次只发送一个未经确认的分组
必须检错ACK/NAK是否出错（需要EDC）
状态数变成两倍
必须记住当前分组的序列号为0还是1
接收方
必须检错接收到的分组是否是重复的
状态会指示希望接收到的分组的序号为0还是1
注意：接收方并不知道发送方是否正确收到了ACK/NAK
发送方不对收到ack/nak给确认，没有所谓的确认的确认
接收方发送ack，如果后面接收方收到的是
老分组P0，则ack错误
下一个分组P1，ack正确
Rdt2.2：无NAK的协议
功能同Rdt2.1，但只是用ACK（ack要编号）
接收方对最后确认接收的分组发ACK，以替代NAK
接收方必须显式地包含被正确接收分组的序号
但收到重复的ACK（如：再次收到ACK0）时，发送方与收到NAK采取相同的动作：重传当前分组
为后面的一次发送多个数据单元做一个准备
一次能够发送多个
每一个应答都有：ACK、NAK：麻烦
使用对前一个数据单元的ACK，替代本数据单元的NAK
确认信息减少一半，协议处理简单
Rdt3.0：具有比特差错和分组丢失的信道
新的假设：下层信道可能会丢失分组（数据或ACK）
会死锁
机制还不够处理这种状况
检验和
序列号
ACK
重传
方法：发送方等待ACK一段合理的时间
发送端超时重传：如果到时没有收到ACK->重传
问题：如果分组（或ACK）只是被延迟了
重传可能会导致数据重复，但利用序列号已经可以处理这个问题
接收方必须指明被正确接收的序列号
需要一个倒计时定时器
链路层的timeou时间是确定的，传输层timeout时间是适应的
发送方
过早超时（延迟的ACK）也能正常工作，但是效率较低，一半的分组和确认是重复的；设置一个合理的超时时间比较重要
rdt3.0的性能
rdt3.0可以工作，但链路容量比较大的情况下，性能较差
链路容量比较大，一次发一个PDU的不能够充分利用链路的传输能力
例如：
rdt3.0 停-等操作
流水线协议
流水线：提高链路利用率
瓶颈转移了->链路带宽
流水线：允许发送方在未得到对方确认的情况下一次发送多个分组
必须增加序号的范围：用多个bit表示分组的序号
在发送方/接收方要有缓冲区
发送方缓冲：未得到确认：可能需要重传
接收方缓冲：上层用户取用数据的速率 不等于 接收到的数据速率：接收到的数据可能乱序，排序交付（可靠）
两种通用的流水线协议:回退N步（GBN）和选择重传（SR）
通用：滑动窗口（slide window）协议
发送缓冲区
形式：内存中的一个区域，落入缓冲区的分组可以发送
功能：用于存放已发送，但是没有得到确认的分组
必要性：需要重发时可用
发送缓冲区的大小：一次最多可以发送多个未经确认的分组
停止等待协议=1
流水线协议>1，合理的值，不能很大，链路利用率不能够超过100%
发送缓冲区中的分组
未发送的：落入缓冲区的分组，可以连续发送出去
已经发送出去的、等待对方确认的分组：发送缓冲区的分组只有得到确认才能删除
SW（发送窗口）RW（接收窗口）S-W（停止等待协议）
发送窗口滑动过程-相对表示方法
可采用相对移动方式表示，分组不动
可缓冲范围移动，代表一段可以发送的权利
发送窗口：发送缓冲区内容的一个范围
那些以及发送但是未经确认分组的序号构成的空间
发送窗口的最大值<=发送缓冲区的值
一开始：没有发送任何一个分组
后沿=前沿
之间为发送窗口的尺寸=0
每发送一个分组，前沿前移一个单位
发送窗口的移动->前沿移动
发送窗口前沿移动的极限：不能够超过发送缓冲区
发送窗口的移动->后沿移动
条件：收到老分组的确认
结果：发送缓冲区罩住新的分组，来了分组可以发送
移动的极限：不能够超过前沿
全部过程
接收窗口
接收窗口（receiving window）=接收缓冲区
接收窗口用于控制哪些分组可以接收
只有收到的分组序号落入到接收窗口内才允许接收
若序号在接收窗口内，则丢弃
GBN：接收窗口尺寸Wr=1，则只能顺序接收
SR：接收窗口尺寸Wr>1，则可以乱序接收
但提交给上层的分组，要按序
例子
Wr=1，在0的位置；只有0号分组可以接收
向前滑动一个，罩在1的位置，如果来了第2号分组，则丢弃
接收窗口的滑动和发送确认
滑动：
低序号分组到来，接收窗口移动
高序号分组乱序到，缓存但不交付（因为要实现rdt，不允许乱序），不滑动
发送确认：
接收窗口尺寸=1：发送连续收到的最大的分组确认（累计确认）
接收窗口尺寸>1：收到分组，发送那个分组的确认（非累计确认）
正常情况下的2个窗口互动
发送窗口
有新的分组落入到发送缓冲区范围，发送->前沿移动
来了老的低序号分组的确认->后沿向前滑动->新的分组可以落入发送缓冲区的范围
接收窗口
收到分组，落入到接收窗口范围内，接收
是低序号，发送确认给对方
发送端上面来了分组
发送窗口滑动
接收窗口滑动
发确认
异常情况下GBN的2窗口互动
发送窗口
新分组落入到发送缓冲区范围，发送->前沿滑动
超时重传机制让发送端将发送窗口中的所有分组发送出去
来了老分组的重复确认->后沿不向前滑动->新的分组无法落入发送缓冲区的范围（此后如果发送缓冲区有新的分组可以发送）
接收窗口
收到乱序分组，没有落入到接收窗口范围内，抛弃
（重复）发送老分组的确认，累计确认
异常情况下SR的2窗口互动
发送窗口
新分组落入发送缓冲区，发送->前沿移动
超时重传机制让发送端将超时的分组重新发送
来了乱序分组的确认->后沿不向前滑动->新的分组无法落入发送缓冲区的范围（此时如果发送缓冲区有新的分组可以发送）
接收窗口
收到乱序分组，落入到接收窗口范围内，接收
发送该分组的确认，单独确认
GBN协议和SR协议的异同
相同之处
发送窗口>1
一次能够发送多个未经确认的分组
不同之处
GBN
接收窗口尺寸=1
接收端：只能顺序接收
发送端：从表现来看，一旦一个分组没有成功，如：0,1,2,3,4，假如1未成功，2,3,4都发送出去了，要返回1再发送；GB1
优点：
简单，所需资源少（接收方一个缓存单元）
缺点
一旦出错，回退N步代价大
适用范围
出错率低：比较适合GBN，出错非常罕见，没有必要用复杂的SR，为罕见的事件做日常的准备和复杂处理
SR
接收窗口尺寸>1
接收端：可以乱序接收
发送端：发送0,1,2,3,4，一旦1未成功发送，2,3,4已发送，无需重发，选择性发送1
优点：出错时，重传一个代价小
缺点：复杂，所需资源多（接收方多个缓存单元）
适用范围
链路容量大（延迟大，带宽大）：比较适合SR而不是GBN，一点出错代价太大
总结
Go-Back-N:
发送端最多在流水线中有N个未确认的分组
接收端只是发送累计型确认cumulative ack
接收方如果发现gap，不确认新到来的分组
发送端拥有对最老的未经确认分组的定时器
只需设置一个定时器
当定时器到时的时候，重传所有未确认的分组
base-下沿 nextseqnum-上沿
Selective Repeat：
发送端最多在流水线中有N个未经确认的分组
接收方对每个到来的分组单独确认individu ack（非累计确认）
发送方为每个未确认的分组保持一个定时器
当超时定时器到时，只是重发到时的未确认分组
发送窗口的最大值
3.5 面向连接的传输：TCP
概述
点对点：
一个发送方，一个接收方
可靠的，按顺序的字节流
没有报文边界
管道化（流水线）
TCP拥塞控制和流量控制设置窗口大小
发送和接收缓存
全双工数据
在同一连接中数据双向流动
MSS：最大报文段大小
面向连接
在数据交换之前，通过握手（交换控制报文）初始化发送方、接收方的状态变量
有流量控制
发送方不会淹没接收方
TCP报文段结构
TCP序号，确认号
序号
报文段首字节在字节流的编号
确认号
期望从另一方收到下一个字节的序号
累计确认
TCP往返延时（RTT）和超时
怎样设置TCP超时
比RTT要长
但RTT是变化的
太短
太早超时
不必要的重传
太长
对报文段的丢失反应慢，消极
怎样估计RTT
SampleRTT
测量从 报文段发出到收 到 确认接收 的时间
SampleRTT会变化，因此估计的RTT应该比较平滑
对几个最近的测量值求平均，而不是仅用当前的SampleRTT
TCP：可靠数据传输
TCP在IP不可靠服务的基础上建立了Rdt
管道化的报文
GBN or SR
累计确认（像GBN）
单个重传定时器（像GBN）
是否可以接收乱序的，没有规范
通过以下事件触发重传
超时（只重发那个最早的未确认段：SR）
重复的确认
例子：收到了ACK50，之后来又收到3个ACK50
序号最小的报文没有被收到，后面的几个先收到了，接收方三次收到比期望序号大的数据都会发送一次期望序号的（最老）ACK
首先考虑简化TCP发送方
忽略重复的确认
忽略流量控制和拥塞控制
TCP发送方事件
从应用层接受数据
用nextseq创建报文段
用序号nextseq为报文段首字节的字节流编号
如果还没有运行，启动定时器
定时器与最早未确认的报文段关联
时间间隔：TimeOutInterval
超时：
重传后沿最老的报文段
重新启动定时器
收到确认
如果是对尚未确认的报文段确认
更新已被确认的报文序号
如果当前有未确认的报文段，重新启动定时器
TCP：重传
产生TCP ACK的建议
接收方的事件
所期望序号的报文段按序到达。所有在期望序号之前的数据都已经被确认
有期望序号的报文段到达。另一个按序报文段等待发送ACK
比期望序号大的报文段乱序到达。检测出数据流中的间隔
能部分或完全填充接收数据间隔的报文段到达
快速重传
超时周期往往太长：
在重传丢失报文段之前的延时太长
通过重复的ACK来检测报文段丢失
发送方通常连续发送大量报文段
如果报文段丢失，通常会引发多个重复的ACK
如果发送方收到同一数据的3个冗余ACK，重传最小序号的段
快速重传：在定时器过时之前重发报文段
它假设跟在被确认的数据后面的数据丢失了
第一个ACK是正常的
收到第二个该段的ACK，表示接收方收到该段后的乱序段
收到第3,4个该段的ACK，表示接收方收到该段之后的2个、3个乱序段，可能性非常大，段丢失了
TCP 流量控制
接收方控制发送方，不让发送方发送太多、太快以至于让接收方缓冲区溢出
接收方在其向发送方的TCP段头部的rwnd字段“通告”其空闲buffer大小
RcvBuffer大小通过socket选项设置（典型默认大小为4096字节）
很多操作系统自动调整RcvBuffer
发送方限制未确认字节的个数<=接收方发送过来的rwnd值
保证接收方不会被淹没
连接管理
连接建立
在正式交换数据之前，发送方和接收方握手建立通信关系：
同意建立连接（每一方都知道对方愿意建立连接）
同意连接参数
同意建立连接 2次握手
在网络中，2次握手建立连接总是可行吗
变化的延时（连接请求的段没有丢，但可能超时）
由于丢失造成的重传
报文乱序
互相看不到对方
3次握手
关闭连接
客户端，服务器分别关闭它自己这一侧的连接
发送端FIN bit=1的TCP段
一旦收到FIN，用ACK回应
接到FIN段，ACK可以和它自己发出的FIN段一起发出
可以处理同时的FIN交换
3.6 拥塞控制原理
拥塞
非正式的定义：“太多的数据需要网络传输，超过了网络的处理能力”
与流量控制不同
拥塞的表现：
分组丢失（路由器缓冲区溢出）
分组经历比较长的延迟（在路由器的列队中排队）
网络中前10位的问题
拥塞的原因/代价
场景1
场景2
输出比输入小的原因：
重传的丢失分组
没有必要重传的重传分组
场景3
拥塞控制方法
两种常用的拥塞控制方法
端到端拥塞控制：
没有来自网络的显示反馈
端系统根据延迟和丢失事件推断是否有拥塞
TCP采用的方法
网路辅助器的拥塞控制：
路由器提供给端系统以反馈信息
单个bit置位，显示有拥塞（SNA，DECbit，TCP/IP ECN，ATM）
显示提供发送端可以采用的速率
案例学习：ATM ABR 拥塞控制
ABR：available bit rate
“弹性服务”
如果发送端的路径“轻载”，发送方使用可用的带宽
如果发送方的路径拥塞了，发送方限制其发送的速度到一个最小保障速率上
RM（资源管理）信元
由发送端发送，在数据信元中间隔插入
RM信元中的bit被交换机设置（“网络辅助”）
NI bit：no increase in rate（轻微拥塞）速率不要增加了
CI bit：congestion indication 拥塞指示
发送端发送的RM信元被接收端返回，接收端不做任何改变
在RM信元中的2个字节ER（explicit rate）字段
拥塞的交换机可能会降低信元中ER值
发送端发送速度会因此是最低的可支持速率
数据信元中的EFCI bit：被拥塞的交换机设计成了1
如果在资源管理信元RM前面的数据信元EFCI被设置成了1，接收端在返回的RM信元中设置CI bit
3.7 TCP拥塞
机制
端到端的拥塞控制机制
路由器不向主机提供有关拥塞的发聩信息
路由器的负载比较轻
符合网络核心简单的TCP/IP架构原则
端系统根据自身得到的信息，判断是否发生拥塞，从而采取动作
拥塞控制的几个问题
如何检测拥塞
轻微拥塞
拥塞
控制策略
在拥塞发生时如何动作，降低速率
轻微拥塞，如何降低
拥塞时，如何降低
在拥塞缓解时，如何动作，增加速率
TCP拥塞控制：拥塞感知
发送端如何探测到拥塞
某个段超时了（丢失事件）：拥塞
超时时间到，某个段的确认没有来
原因一：网络拥塞（某个路由器缓冲区没空间了，被丢失）概率大
原因二：出错被丢失了（各级错误，没有通过校验，被丢弃）概率小
一旦超时，就认为拥塞了，有一定误判，但是总体控制方向是对的
有关某个段的3次重复ACK：轻微拥塞
段的第一个ack，正常，确认绿段，期待红段
段的第二个重复ack，意味着红段的后一段收到了，蓝段乱序到达
段的第2,3,4个ack重复，意味着红段的后2,3,4个段收到了，橙段乱序到达，同时红段丢失的可能性很大（后面3个段都收到了，红段都没到）
网络这时还能够进行一定程度的传输，拥塞但情况比第一种好
TCP拥塞控制：速率控制方法
如何控制发送端发送的速率
维持一个拥塞窗口的值：CongWin
发送端限制已发送但未确认的数据量（的上限）
从而粗略地控制发送方往网络中注入的速率
CongWin是动态的，是感知到网络拥塞程度的函数
超时或者3个重复ACK，CongWin下降
超时时：CongWin降为1MSS（最大报文段长度），进入ss阶段然后再倍增到CongWin/2（每个RTT），从而进入CA阶段
3个重复ACK：CongWin降为CongWin/2，CA阶段
否则（正常收到ACK，没有发生以上情况）：CongWin跃跃欲试
ss（慢启动）阶段：加倍增加（每个RTT）
CA（拥塞避免）阶段：线性增加（每个RTT）
TCP拥塞控制和流量控制的联合动作
联合控制的方法
发送端控制 发送但未确认的字节数量 同时也不能超过接收窗口，满足流量控制要求
sendWin=min（CongWin，RecvWin）
同时满足 拥塞控制和流量控制要求
TCP拥塞控制：策略概述
拥塞控制策略
慢启动
AIMD：线性增加、乘性减少
超时事件后的保守策略
总结
TCP吞吐量
TCP公平性
公平性目标：
如果K个TCP会话分享一个链路为R的瓶颈，每个会话的有效带宽为R/K
第四章 网络层：数据平面
4.1 导论
网络层服务
在发送主机和接收主机之间传送报文段（segment）
在发送端将报文段封装到数据报（datagram）中
在接收端，将报文段上交给传输层实体
网络层协议存在于每一个主机和路由器
路由器检查每一个经过它的IP数据报的头部
网络层的关键功能
网络层的功能
转发（数据平面）：
将分组从路由器的输入接口转发到合适的输出输出接口
路由（控制平面）：
使用路由算法来决定分组从发送主机到目标接收主机的路径
路由选择算法
路由选择协议
旅行类比
转发：通过单个路口的过程
路由：从源到目的地的路由规划过程
网络层：数据平面、控制平面
数据平面
本地，每个路由器功能
决定从路由器输入端口到达的分组如何转发到输出端口
转发功能
传统方式
基于目标地址+转发表
SDN方式
基于多个字段+流表
控制平面
网络范围内的逻辑
决定数据报如何在路由器之间路由，决定数据报从源到目标主机之间端到端的路径
控制平面的方法
传统的路由算法：
在路由器中被实现
software-defined networking（SDN）软件定义网络：在远程的服务器中实现
传统方式
在每一个路由器中的单独路由器算法元件，在控制平面进行交互
每个路由器既可以转发也可以路由
控制平面和数据平面在一个设备上实现（控制平面和数据平面紧耦合）
分布式路由
控制平面：路由算法决定端到端的路径
数据平面：IP协议根据转发表决定了IP数据报在此路由器上的局部转发
僵化，不灵活，不可编程
SDN方式：逻辑集中的控制平面
一个不同的（通常是远程的）控制器与本地控制代理（CAs）交互
集中式路由
网络服务模型
从发送方主机到接收端主机传输数据报的“通道”，网络提供怎样的服务模型
对于单个数据报的服务
可靠传送
延迟保证：如：少于40ms的延迟
对于数据报流的服务
保序数据报传送
保证流的最小带宽
分组之间的延迟差
连接建立
在某些网络架构中是第三重要的功能
ATM、fram、relay、X.25
在分组传输之前，在两个主机之间，在通过一些路由器所构成的路径上建立一个网络层连接
涉及路由器
网络层和传输层连接服务的区别
网络层
在两个主机之间，涉及到路径上的一些路由器
传输层
在2个进程之间，很可能只体现在端系统上（TCP连接 ）
4.2 路由器组成
路由器结构概述
高层面（非常简化的）通用路由器体系架构
路由：
运行路由选择算法/协议（RIP、OSPF，BGP）---生成路由表
转发：
从输入到输出链路交换数据报---根据路由表进行分组的转发
输入端口功能
根据数据报头部的信息如：目的地址，在输入端口内存中的转发表中查找适合的输出端口（匹配+行动）
基于目标的转发：仅仅依赖于IP数据报的目标IP地址（传统方法）
通用转发：基于头部字段的任意集合进行转发
输入端口缓存
当交换机构的速率小于输入端口的汇聚速率时--->在输入端口可能要排队
排队延迟以及由于输入缓存溢出造成丢失
Head Of Line（HOL）blocking（头端阻塞）：排在队头的数据报阻止了队列中其他数据报向前移动
交换结构
将分组从输入缓存区传输到合适的输出端口号
交换速率：分组可以按照该速率从输入传输到输出
运行速度经常是输入/输出链路速率的若干倍
N个输入端口：交换机构的交换速度是输入线路速度的N倍比较理想，才不会成为瓶颈
通过内存交换
第一代路由器
在CPU直接控制下的交换，采用传统的计算机
分组被拷贝到系统内存，CPU从分组的头部提取出目标IP地址，查找转发表，找到对应的输出端口，拷贝到输出端口
转发速率被内存的带宽限制（数据报通过BUS两遍）
一次只能转发一个分组
通过总线交换
第二代路由器
数据报通过共享总线，从输入端转发到输出端口
总线竞争：交换速度受限于总线带宽
1次处理一个分组
32Gbps，Cisco5600：对于接入企业或企业级路由器，速度足够（但不适合区域或骨干网络）
通过互联网络（crossbar等）的交换
同时并发转发多个分组，克服总线带宽限制
Banyan（榕树）网络，crossbar（纵横）和其他的互联网被开发，将多个处理器连接成多处理器
当分组从端口A到达，转给端口Y；控制器短路相应的两个总线
高级设计：将数据报分片为固定长度的信元，通过交换网络交换
Cisco12000：以60Gbps的交换速率通过互联网
输出端口
当数据报从交换机构的到达速率比传输速率快就需要输出端口缓存
由调度规则选择排队的数据报进行传输
调度机制
调度：选择下一个要通过链路传输的分组
FIFO（fist in fist out）scheduling：按照分组到来的次序发送
丢弃策略：如果分组到达一个满的队列，哪个分组将会被抛弃
tail pop：丢弃刚到达的分组
priority pop：根据优先权丢弃/移除分组
random：随机的丢弃/移除
调度策略：优先权
优先权丢度：发送最高优先权的分组
多类，不同类别有不同的优先权
类别可能依赖于标记或者其他的头部字段，例：IP source/dest,port number,ds,etc.
先传高优先级的队列中的分组，除非没有
高（低）优先权中的分组传输次序：FIFO
调度策略：其他的
Round Robin（RR）scheduling
多类
循环扫描不同类型的队列，发送完一类的一个分组，再发送下一个类的一个分组，循环所有类
Weight Fair Queuing（WFQ）
一般化的Round Robin
在一段时间内，每个队列得到的服务时间是：Wi/（XIGMA（Wi））*t，和权重成正比
每一个类在每一个循环中获得不同权重的服务量
数据报（分组）可能会被丢弃，由于拥塞，缓冲区没有空间
4.3 IP：Internet Protocol
IP数据报格式
IP分组和重组（Fragmentation&&Reassembly）
网络链路层有MTU（最大传输单元）--链路层帧所携带的最大数据长度
不同的链路类型
不同的MTU
大的IP数据报在网络中被分片（fragmented）
一个数据报被分割成若干个小的数据报（八个字节的整数切割）
相同的ID
不同的偏移量
最后一个分片标记为0
”重组“只在最终的目标主机进行
IP头部的信息被用于标识，排序相关的分组
例子
IP编址
引论
IP地址：32位标示，对主机或者路由器的接口编址
接口：主机/路由器和物理链路的连接处
路由器通常有多个接口
主机也有可能有多个接口
IP地址和每个接口关联
一个IP地址和一个接口相关联
这些接口是如何连接的
子网（Subnets）
IP地址
子网部分（高位bit）
主机部分（地位bit）
什么是子网（subnet）
一个子网内的节点（主机或者路由器）它们的IP地址的高位部分相同，这些节点构成的网络的一部分叫做子网
无需路由器接入，子网内各个主机可以在物理上互相直接到达（一跳可达，可以借助交换机）
判断方法
要判断一个子网，将每一个接口从主机或者路由器上分开，构成了一个个网络的孤岛
每一个孤岛（网络）都是一个都可以被称为subnet
6个
IP地址分类
特殊的IP地址
一些约定
子网部分：全为0-------本网络
主机部分：全为0-------本主机
主机部分：全为1-------广播地址，这个网络的所有主机
网络部分：全为1-------回路地址
内网（专网）IP地址
专用地址：
地址空间的一部分供专用地址使用
永远不会被当做公共地址来分配，不会与公共地址重复
只在局部网络中有意义，区分不同的设备
路由器不对目标地址是专用地址的分组进行转发
专用地址范围
CIDR（Classless InterDomain Routing）无类域间路由
子网部分可以在任意位置
地址格式：a.b.c.d/x，其中x是地址中子网号的长度
子网掩码中1代表网络号，0代表主机号（ip地址与子网掩码做与运算，只保留子网部分）
转发表和转发算法
路由表只有四个表项（目标子网号--子网掩码--下一跳--端口）
获得IP数据报的目标地址
对于转发表（路由表）的每一个表项
如（IP Des addr）&（mask）==destination，则按照表项对应的接口转发该数据报
如果没有找到，则使用默认表项转发该分组
如何获得一个IP地址
主机如何获得一个IP地址
DHCP：动态主机配置协议---自动获取IP、子网掩码、网关（自己家的网关是路由器的IP地址，或者猫的IP地址）、本地DNS
DHCP
目标：允许主机在加入网络的时候，动态地从服务器哪里获得IP地址
可以更新对主机在用IP地址的租用期--租期快到了
重新启动时，允许重新使用以前用过的IP地址
支持移动用户加入该网络（短期在网）
DHCP工作概述（UDP上的一个服务）
主机广播“DHCP discover”报文【可选】
类似于有没有活着的DHCP服务器啊
DHCP服务器用“DHCP offer”提供报文响应【可选】
服务器回应“我活着”
主机请求IP地址：发送“DHCP request”报文
DHCP服务器发送地址：“DHCP ack”报文
client没有IP地址，IP地址先取0.0.0.0
Client用32位全1的广播地址来问所有DHCP服务器
DHCP实例
如何获得一个网络的子网部分
从ISP获得地址块中分配一个小地址块
一个ISP如何获得一块地址
层次编址：路由聚集（route aggregation）
层次编址允许路由信息的有效广播
层次编址：特殊路由信息（more special route）
最长前缀匹配
NAT（Network Address Translation）
网络地址转换---出去的时候把源（内网）地址转换为ISP统一的IP地址；回来的时候把机构对应的IP地址转回内网地址
动机：本地网络只有一个有效IP地址
不需要从ISP分配一块地址，可用一个IP地址用于所有的（局域网）设备---省钱
可以在局域网 改变设备地址 的情况下而 无需通知外界
可以改变ISP（地址变化）而不需要改变内部设备地址
局域网内部的设备没有明确的地址，对外是不可见的----安全
实现：NAT路由器必须
外出数据包：替代源地址和端口号为NAT IP地址和新的端口号，目标IP和目标端口号不变
远端的C/S将会用NAT IP地址，新端口号作为目标地址
记住每一个转换替换对（在NAT转换表中）
源IP、端口 vs NAT IP、新端口
进入数据报：替换目标IP地址和端口号，采用存储在NAT转换表的mapping表项，用（源IP、端口）
16-bit端口字段
6万多个同时连接，一个局域网
对NAT是有争议的：
路由器只应该对第三层做信息处理，而这里对端口号（四层）作了处理
违反了end-to-end原则
端到端原则：复杂性放到网络边缘
无需借助中转和变换，就可以直接传送到目标主机
NAT可能被一些应用设计者考虑，例如：P2P application
外网的机器无法主动连接到内网的机器上
地址短缺问题可以被IPv6解决
NAT穿越：如果客户端需要连接在NAT后面的服务器，如何操作
1.静态配置NAT（把NAT表静态的写死）
2.UPnP协议（也叫IGD协议），允许内网的设备查询/增加/删除NAT的表项
3.中继
IPv6
动机
初始动机：32-bit地址空间将会被很快用完
另外的动机：
头部格式改变帮助加速处理和转发
TTL-1
头部checksum
分片
头部格式改变帮助QoS
IPv6数据报格式
固定的40字节头部
数据报传输过程中，不允许分片
太大了IPv6协议会发送错误报告给源主机，让它自己把分组弄小一点
头部（Cont）
Priority：标示流中数据报的优先级
Flow Label：标示数据报在一个“flow”（“flow”的概念没有被严格的定义）
Next header：标示上层协议
hop limit相当于IPv4里面的time to live（每过一个路由器-1）
和IPv4的其他变化
Checksum：被移除掉，降低在每一段中处理的速度
Options：允许，但是在头部之外，被“Next header”字段标示
ICMPv6：ICMP的新版本
附加了报文类型 例如：Packet Too Big
多播组管理功能
从IPv4到IPv6的平移
不是所有的路由器都能够同时升级的
没有一个标记日“flag days”
在IPv4和IPv6路由器混合时，网络如何运转
隧道：在IPv4路由器之间传输的IPv4数据报中携带IPv6数据报
4.4 通用转发和SDN
每个路由器（Per Route）的控制平面
每个路由器上都有实现路由算法的元件（它们之间相互交互）---形成传统IP实现方式的控制平面
算出路由表之后交给IP实体，由IP实体实现转发
每台设备上既实现控制功能，又实现数据平面
控制功能分布式实现
路由表--粘连（控制平面和数据平面粘连在一起）
缺陷
数量众多、功能各异的中间盒
路由器的网络层功能
IP转发：对于到来的分组按照路由表决定如何转发，数据平面
路由：决定路径，计算路由表；处于控制平面
还有其他种类繁多的网络设备（中间盒）
交换机；防火墙；NAT；IDS；负载均衡设备
未来：不断增加的需求和相应的网络设备
需要不同的设备去实现不同的网络功能
每台设备集成了控制平面和数据平面的功能
控制平面分布式地实现了各种控制平面功能
升级和部署网络设备非常困难
网络设备控制平面的实现方式特点
互联网网络设备：传统方式都是通过分布式，每台设备的方法来实现数据平面和控制平面功能
垂直集成：每台路由器或者其他网络设备，包括：
硬件、在私有的操作系统
互联网标准协议（IP、RIP、IS-IS、OSPF、BGP）的私有实现
从上到下都由一个厂商提供（代价大、被设备“绑架”）
每个设备都实现了数据平面和控制平面的事情
控制平面的功能是分布式实现的
设备基本上只能（分布式升级困难）按照固定方式工作，控制逻辑固化。不同的网络功能需要不同的“middleboxes”：防火墙、负载均衡器、NATboxes，····
（数据+控制平面）集成--->（控制逻辑）分布--->固化
代价大；升级困难；管理困难
问题
SDN：逻辑上集中的控制平面
一个不同的（通常是远程的）控制器与CA（控制代理）交互，控制器决定分组转发的逻辑（可编程），CA所在设备执行逻辑
SDN的主要思路
网络设备数据平面和控制平面分离
数据平面--分组交换机
将路由器、交换机和目前大多数网络设备的功能进一步抽象成：按照流表（有控制平面设置的控制逻辑）进行PDU（帧或分组）动作（包括转发、丢失、拷贝、泛洪、阻塞）
统一化设备功能：SDN交换机（分组交换机），执行控制逻辑
控制平面--控制器+网络应用
集中、分离
计算和下发控制逻辑：流表
SDN数据平面和控制平面分离的优势
水平集成控制平面的开放实现（而非私有实现），创造出好的产品产业，促进发展
分组交换机、控制器和各种控制逻辑网络应用app可由不同产商生产，专业化，引入竞争形成良好的生态
集中实现控制逻辑，网络管理容易
集中控制器了解网络状况，编程简单，传统方式困难
避免路由器的误配置
基于流表的匹配+行动的工作方式允许“可编程的”分组交换机
实现流量工作等高级特征
在此框架下实现各种新型（未来）的网络设备
流量工程：传统路由比较困难
SDN特点
1.通用“flow-based”基于流的匹配+行动
2.控制平面和数据平面分离
3.控制平面功能在数据交换设备之外实现
4.可编程控制应用
在控制器之上以网络应用形式实现各种网络功能
SDN架构
数据平面交换机（分组交换机）
快速、简单，商业化交换设备采用硬件实现通用转发功能
流表被控制器计算和安装
基于南向API（例如OpenFlow），SDN控制器访问基于流的交换机
定义了哪些可以被控制哪些不能
也定义了和控制器的协议（例如：OpenFlow）
SDN控制器
网络OS
维护网络状态信息
通过上面的北向API和网络控制应用应用交互
通过下面的南向API和网络交换机交互
逻辑上集中，但是在实现上通常由于性能、可扩展性、容错性以及鲁棒性采用分布式方法
控制应用
网络控制应用
控制的大脑：采用下层提供的服务（SDN控制器提供的API）实现网络功能
路由器 交换机
接入控制 防火墙
负载均衡
其他功能
非绑定：可以被第三方提供，控制器厂商通常不同，与分组交换机厂商也可以不同
每一个路由器包含一个流表（被逻辑上集中的控制器计算和分发）
Open Flow 数据平面抽象
流：由分组（帧）头部字段所定义
通用转发：简单的分组处理规则
模式：将分组头部字段和流表进行匹配
行动：对于匹配上的分组，可以是丢弃、转发、修改、将匹配的分组发送给控制器
优先权Priority：几个模式匹配了，优先采用哪个，消除歧义
计数器Counters：#bytes以及#packets
路由器中的路由表定义了路由器的匹配+行动规则（流表由控制器计算并下发）
表项结构
OpenFlow协议
控制器和SDN交换机交互的协议
采用TCP来交换报文
加密可选
3种OpenFlow报文类型
控制器>交换机
异步（交换机>控制器））
对称
控制器-交换机报文
第五章 网络层控制平面
5.1 路由选择算法
路由协议的目标：确定从发送主机到接收主机之间，通过路由器的网络“较好”的路径（等价于路由器的序列）
路径：路由器的序列，分组将会沿着该序列从源主机到达最后的目标主机
“较好”：最小“代价”，“最快的”，“最不拥塞”
路由：一个“top 10”网络挑战
路由（route）的概念
路由：按照某种指标（传输延迟，所经过的站点数目）等找到一条从源节点到目标节点的较好路径
较好路径：按照某种指标较小的路径
指标：站数，延迟，费用，队列长度等，或者是一些单纯指标的加权平均
采用什么样的指标，表示网络使用者希望网路在什么方面表现突出，什么指标网络使用者比较重视
路由器---路由器之间的最优路径=主机对之间的最优路径
路由器连接子网，子网到路由器之间的跳数就一跳，必须要走
路由器到下一跳路由器（节点到节点）之间的最优路径找到了
也就找到了从源子网向目标子网所有主机对之间的最优路径
大大降低了路由计算的规模
在路由计算中按照子网到子网的路径计算为目标，而不是主机到主机
路由选择算法（routing algorithm）：网络层软件的一部分，完成路由功能
网络的图抽象
原则
最优化原则（optimality principle）
路由选择算法的原则
正确性（correctness）
算法必须是正确的和完整的，使分组一站一站接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项；没有处理不了的目标站地址
简单性（simplicity）
算法在计算机上应简单：最优但复杂的算法，时间上延迟很大，不实用，不应为了获取路由信息增加很多的通信量
健壮性（robustness）
算法应能适应通信量和网络拓扑的变化：通信量变化，网络拓扑的变化算法能很快适应；不向很拥塞的链路发数据，不向断了的链路发送数据
稳定性（stability）
产生的路由不应该摇摆
公平性（fairness）
对每一个站点都公平
最优性（optimality）
某个指标的最优，时间上、费用上等指标，或者综合指标；实际上，获取最优的结果代价比较高，可以是次优的
路由算法的分类
全局或者局部路由信息
全局
所有的路由器拥有完整的拓扑和边的代价
“link state”算法
分布式
路由器只知道与它有物理连接关系的邻居路由器，和到相应邻居路由器的代价值
迭代地与邻居交换路由信息、计算路由信息
“distance vector”算法
动态或者静态
静态
路由随时间变化缓慢
非自适应算法（non-adaptive algorithm）：不能适应网络拓扑和通信量的变化，路由表是事先计算好的
动态
路由变化很快
周期性更新
根据链路代价的变化而变化
自适应路由算法（adaptive algorithm）
能适应网络拓扑和通信量的变化
link state（链路状态）
Dijkstra算法的讨论
distance vector（距离矢量）
无穷计算问题
LS和DV算法的比较
消息复杂度（DV胜出）
LS：有n个节点，E条链路，发送报文O（nE）个
局部的路由信息，全局传播
DV：只和邻居交换信息
全局的路由信息，局部传播
收敛时间（LS胜出）
LS：O（n^2）算法，有可能震荡
DV：收敛较慢，可能存在路由环路、count-to-infinity问题
健壮性：路由器故障会发生什么（LS胜出）
LS：
节点会通告不正确的链路代价
每个节点只计算自己的路由表
错误信息影响较小，局部，路由较健壮
DV
DV节点可能会通告对全网所有节点的不正确路径代价
每一个节点的路由表可能被其他节点使用
错误可能扩散全网
两种路由选择算法都有其优点，而且在互联网上都有应用
5.2 自治系统内部的路由选择
RIP（Routing Information Protocol）
DV算法
距离矢量：每条链路cost=1，# hops（max=15 hops）跳数
DV每隔30s和邻居交换DV，通告
每个通告包括，最多25个目标子网
RIP通告（advertisements）
DV：在邻居之间每隔30s交换通告报文
定期，而且在改变路由的时候发送通告报文
在对方的请求下可以发送通告报文
每一个通告：至多AS内部的25个目标网络的DV
目标网络+跳数
一个公告最多25个子网，最大跳数为16
例子
链路失效和恢复
如果180s没有收到通告信息---->邻居或者链路失效
发现经过这个邻居的路由失效
新的通告报文会传递给邻居
邻居因此发出新的通告（如果路由变化的话）
链路失效快速（？）地在整网中传输
使用毒性逆转（poison reverse）阻止ping-pong回路（不可达的距离：跳数无限=16段）
RIP进程处理
RIP以应用进程的方式实现：route-d（daemon）
通告报文通过UDP报文传送，周期性重复
网络层的协议使用了传输层的服务，以应用层实体的方式实现
OSPF（Open Shortest Path First）
“open”：标准可公开获得
使用LS算法
LS分组在网络中（一个AS内部）分发
全局网络拓扑、代价在每一个节点中都保持
路由算法采用Dijkstra算法
OSPF通告信息中携带：每一个邻居路由器一个表项
通告信息会传遍AS全部（通过泛洪）
在IP数据报上直接传送OSPF报文（而不是通过UDP和TCP）
IS-IS路由协议：几乎和OSPF一样
OSPF“高级”特性（在RIP中没有的）
安全：所有的OSPF报文都是经过认证的（防止恶意的攻击）
允许有多个代价相同的路径存在（在RIP协议中只有一个）
对于每一个链路，对于不同的TOS有多重代价矩阵
例如：卫星链路代价对于尽力而为的服务代价设置比较低，对实时服务代价设置的比较高
支持按照不同的代价计算最优路径，如：按照时间和延迟分别计算最优路径
对单播和多播的集成支持
在大型网络中支持层次性OSPF
5.3 ISP之间的路由选择：BGP
层次路由
一个平面的路由
一个网络中的所有路由器的地位一样
通过LS，DV，或者其他路由算法，所有路由器都要知道其他所有路由器（子网）如何走
所有路由器在一个平面
平面路由的问题
规模巨大的网络中，路由信息的存储、传输和计算机代价巨大
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如何走的问题
扩展性强：规模增大，性能不会减的太多
解决了管理问题
各个AS内部可以运行不同的内部网关协议
可以使自己网络的细节不向外透露
互联网AS间路由：BGP
BGP（Border Gateway Protocol）：自治区域间路由协议“事实上的”标准
将互联网各个AS粘在一起的胶水
BGP提供给每个AS以下方法
eBGP：从相邻的ASes那里获得子网可达信息
iBGP：将获得的子网可达信息传输到AS内部的所有路由器
根据子网可达信息和策略来决定到达子网的“好”路径
允许子网向互联网其他网络通告“我在这里”
基于距离矢量算法（路径矢量）
不仅仅是距离矢量，还包括到达各个目标网络的详细路径（AS序号的列表）能够避免简单DV算法的路由环路问题
BGP基础
BGP会话：2个BGP路由器（“peers”）在一个半永久的TCP连接上交换BGP报文
通告向不同目标子网前缀的“路径”（BGP是一个“路径矢量”协议）
路径属性&路由
当通告一个子网前缀时，通告包括BGP属性
prefix+attributes=”route"
两个重要的属性：
AS-PATH：前缀的通告所经过的AS列表
检测路由环路：多路径选择
在向其他AS转发时，需要将自己的AS号加在路径上
NEXT-HOP：从当前AS到下一跳AS有多个链路，在NEXT-HOP属性中，告诉对方通过哪个I转发
其他属性：路由偏好指标，如何被插入的属性
基于策略的路由
当一个网关路由器接收到一个路由通告，使用输入策略来接受或过滤（accept or decline）
过滤原因1：不想经过某个AS，转发某些前缀的分组
过滤原因2：已经有了一条前往某前缀的偏好路径
策略也决定了是否向它别的邻居通告收到的这个路由信息
BGP路径通告
BGP通告
使用TCP协议交换BGP报文
BGP报文：
OPEN：打开TCP连接，认证发送方
UPDATE：通告新的路径（或者撤销原路径）
KEEPALIVE：在没有更新时保持连接，也用于对OPEN请求确认
NOTTIFICATION：报告以前消息的错误，也用来关闭连接
BGP，OSPF，转发表表项
路由表表项由：AS内和AS间的路由共同决定
BGP路径选择
路由器可能获得一个网络前缀的多个路径，路由器必须进行路径选择，路由器选择可以基于
1.本地偏好值属性：偏好策略决定
2.最短AS-PATH：As的跳数
3.最近的NEXT-HOP路由器：热土豆路由
4.附加的判据：使用BGP标示
一个前缀对应这多种路径，采用消除规则直到留下一条路径
为什么内部网关协议和外部网关协议如此不同
策略：
Inter-AS：管理员需要控制通信路径，谁在使用它的网络进行数据传输
Intra-AS：一个管理者，所以无需策略
AS内部的各子网的主机尽可能地利用资源进行快速路由
规模
AS间路由必须考虑规模问题，以便支持全网的数据转发
AS内部路由规模不是一个大的问题
如果AS太大，可将此AS分成小的AS：规模可控
或者AS内部路由支持层次性，层次性路由节约了空间，降低了更新数据流量
性能
Intra-AS（AS内）关注性能
Inter-AS（AS间）：策略可能比性能更重要
第六章 链路层和局域网
6.1 引论
网络节点的连接方式
点到点连接
多点连接
共享性介质
通过网络交换机
连接实例
WAN（广域网）：网络形式采用点到点链路
带宽大、距离远（延迟大）
如果采用多点连接方式
竞争方式：一旦冲突代价大
令牌协调方式：在其中协调节点的发送代价大
点到点链路的链路层服务实现非常简单，封装和解封装
LAN（局域网）：一般采用多点连接方式
连接节点非常方便
接到共享型介质上（或网络交换机），就可以连接所有其他节点
多点连接方式网络的链路层功能实现相当复杂
多点接入：协调各节点对共享性介质的访问和使用
竞争方式：冲突之后的协调
令牌方式：令牌产生，占有和释放等
一些术语
主机和路由器是节点（网桥和交换机也是）：nodes
沿着通信路径，连接各个相邻节点通信信道的链路：links
有线链路
无线链路
局域网，共享性链路
第二层协议数据单元帧frame，封装数据报
数据链路层负责从一个节点通过链路将（帧中的）数据报发送给物理相邻节点
链路层
数据报（分组）在不同的链路以不同的链路协议传送
第一跳链路：以太网
中间链路：帧中继链路
最后一跳802.11（无线局域网）
不同的链路协议提供不同的服务
例如：在链路层上提供（或没有）可靠数据传输
传输类比
从Princeton到Lausanne
轿车：princeton to JFK
飞机： JFK to Geneva
火车：Geneva to Lausanne
旅行者=数据报datagram
交通段=通信链路 communication link
交通模式=链路层协议：数据报链路层和局域网
票务代理=路由算法 routing algorithm
服务
成帧，链路接入：
将数据报封装在帧中，加上帧头、帧尾部
如果采用的是共享性介质，信道接入获得信道访问权
在帧头部使用“MAC”（物理）地址来标示源和目标
不同于IP地址
在相邻两个节点完成可靠数据传递
在低出错率的链路上（光纤和双绞线电缆）很少使用
出错率低，没有必要在每一个帧中做差错控制工作，协议复杂
发送端对每一帧进行差错控制编码，根据反馈做出响应动作
接收端进行控制解码，反馈给发送端（ACK，NAK）
在本层放弃可靠控制工作，在网络层或者传输层做可靠控制的工作，或者根本不做可靠控制工作
在无线链路上经常使用：出错率较高
在传输层还要进行可靠数据传输
原因：出错率高，如果在链路层不做差错控制工作，漏去的错误比较高
到了上层如果需要可靠控制的数据传输代价很大
流量控制：
使得相邻的发送和接受节点速度匹配
差错检测
差错由信号衰减和噪声引起
接收方检测出的错误
通知发送端进行重传或丢弃帧
差错纠正
接收端检查和纠正bit错误，不通过重传来纠正错误
半双工和全双工
半双工：链路可以双向传输，但一次只有一个方向
实现
在每一个主机上
也在每一个路由器上
交换机的每一个端口上
在网卡（适配器）（NIC）实现
链路层功能在“适配器”上实现（aka network interface card/NIC）或者一个芯片组上
以太网，802.11网卡；以太网芯片组
实现链路层和响应物理层功能
接收到主机的系统总线上
硬件、软件和固件的综合体
适配器（网卡）通信
发送方
在帧中封装数据报
加上差错控制编码，实现RDT和流量控制功能等
接收方
检查有无出错，执行rdt和流量控制功能等
解封装数据报，将其交给上层
6.2 差错检测和纠正
错误检验
EDC=差错检测和纠正位（冗余位）
检错不是100%可靠
协议会检漏一些错误，但是很少
更长的EDC字段可以得到更好的检测和纠正效果
D=数据由差错检测保护，可以包含头部字段
奇偶校验
单bit奇偶校验
检测单个bit级错误
二维奇偶校验
检测和纠正单个bit错误
检验和：CRC（循环冗余校验）
强大的差错检验码
将数据比特D，看成是二进制的数据
生成多项式G：双方协商r+1位模式（r次方）
生成和检验所使用的位模式
目标：选择r位CRC附加位R，使得
<D，R>正好被G整除
接收方知道G，将<D，R>除以G，如果非0余数：检查出错误
能检查所有少于r+1位的突发错误
实际中广泛使用（以太网、802.11 WIFI、ATM）
例子
性能分析
突发错误和突发长度
CRC检错性能描述
能够检查出所有的1bit错误
能够检查出所有的双bit错误
能够检查出所有长度=r或者<r位的错误
6.3 多点访问协议
引入
两种类型的链路（一个子网内部链路连接形式）
点对点
拨号访问的PPP
以太网交换机和主机之间的点对点链路
广播（共享线路和媒体）
传统以太网
HFC上行链路
802.11无线局域网
单个共享的广播型链路
2个或更多站点同时传送：冲突（collision）
多个节点在同一时刻发送，则会收到2个或多个信号叠加
多路访问协议（介质访问控制协议：MAC）
分布式算法--决定节点如何使用共享信道，即：决定节点什么时候发送
关于共享控制的通信必须用借助信道本身传输
没有带外的信道，各节点使用其协调信道使用
用于传输控制信息
理想的多路访问协议
给定：Rbps的广播信道
必要条件
1.当一个节点要发送时，可以R速率发送
2.当M个节点要发送时，每个可以以R/M的平均速率发送
完全分布的
没有特殊节点协调发送
没有时钟和时隙的同步
简单
MAC（媒体访问控制）协议：分类
信道划分
把信道划分成小片（时间、频率、编码）
分配片给每个节点专用
随机访问
信道不划分，允许冲突
冲突后恢复
线缆接入网络（信道划分和随机访问的综合）
多个40Mbps下行（广播）信道，FDM
下行：通过FDM分成若干信道，互联网、数字电视等
互联网信道：只有1个CMTS在其上面传输
多个30Mbps上行信道，FDM
多路访问：所有用户使用；接着TDM分成微时隙
部分时隙：分配；部分时隙：竞争
DOCSIS：TDM上行信道
采用TDM的方式将上行信道分成若干微时隙：MAP指定
站点采用分配给它的微时隙上行数据传输：分配
在特殊的上行微时隙中，个站点请求上行微时隙：竞争
各站点对于该时隙的使用是随机的
一旦碰撞（请求不成功，结果是：在下行的MAP中没有为它分配，则二进制退避）选择时隙上传
上行信道预约时隙，下行信道分配时隙
依次轮流
节点依次轮流
但是有很多数据传输的节点可以获得较长的信道使用权
总结
多点接入问题：对于一个共享型介质，各个节点如何协调对它的访问和使用
信道划分：按时间、频率或者编码
TDMA、FDMA、CDMA
随机访问（动态）
ALOHA，S-ALOHA、CSMA、CSMA/CD、CSMA/CA
子主题
载波侦听：在有些介质上很容易（有线介质），但有些介质比较困难（无线）
CSMA/CD:802.3 Ethernet中使用
CSMA/CA：802.11WLAN中使用
依次轮流协议
集中：由一个中心节点轮询；分布：通过令牌控制
蓝牙、FDDI、令牌环
6.4 LANs
MAC地址和ARP
32位IP地址
网络层地址
用于使数据报到达目标IP子网：前n-1跳
从而到达子网中的目标节点：最后一跳
LAN（MAC/物理/以太网）地址
用于使帧从一个网卡传递到其物理连接的另一个网卡（在同一物理网络中）
48bitMAC地址固化在适配器的ROM，有时也可以通过软件设定
理论上全球任何2个网卡的MAC地址都不相同
例如：1A-2F-BB-76-09-AD（16进制表示，一位4bit）
网络地址和MAC地址分离
IP地址和MAC地址的作用不同
IP地址是分层的
一个子网所有站点网络号一致，路由聚集，减少路由表项
需要一个网络中的站点地址网络号一致，如果捆绑需要定制网卡非常麻烦
希望网络层地址是配置的：IP地址完成网络到网络的交付
MAC地址是一个平面
网卡在生产时不知道被用于哪个网络，因此给网卡一个唯一的标示，用于区分一个网络内部不同的网卡即可
可以完成一个物理网络内部的节点到节点的数据交付
分离的好处
网卡坏了，ip不变，可以捆绑到另一个网卡的MAC上
物理网络还可以除IP以外支持其他网络层协议，链路协议为任意上层网络协议服务，如IPX等
捆绑的问题
如果仅仅使用IP地址，不用MAC地址，那么它仅支持IP协议
每次上电都要重新写入网卡IP地址
另外一个选择就是不使用任何地址：不用MAC地址，则每到来一个帧都要上传到IP层次，由它判断是不是需要接收，干扰一次
LAN地址和ARP
局域网上每个适配器都有一个唯一的LAN地址
MAC地址由IEEE管理和分配
制造商购入MAC地址空间（保证唯一性）
类比：
MAC地址：身份证号
IP地址：通讯地址
MAC平面地址--》支持移动
可以将网卡接到其他网络中
IP地址有层次--》不能移动
依赖于节点连接的IP子网，与子网的网络号相同（有与其相连的子网相同的网络前缀）
ARP（Address Resolution Protocol）
已知B的IP地址，如何确定B的MAC
在LAN上的每个IP节点都有一个ARP表
ARP表：包括一些LAN节点IP/MAC地址的映射
<IP address ; MAC address ; TTL >（TTL是指地址映射失效的时间）典型是20min
ARP协议：在同一LAN
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的表项
无需网络管理员的干预
例子
walkthrough：发送数据报：由A通过R到B，假设A知道B的IP地址
在R上有两个ARP表，分别对应两个LAN
在源主机的路由表中，发现到目标主机的下一跳时111.111.111.110
在源主机的ARP表中，发现其MAC地址是E6-E9-00-17-BB-4B
A创建数据报，源IP地址:A；目标IP地址:B
帧从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
现在一般是交换机在中心
每个节点以及相连的交换机端口使用（独立的）以太网协议（不会和其他节点的发送产生碰撞）
以太帧结构
发送方适配器在以太网帧中封装IP数据报，或者其他网络层协议数据单元
前导码+目标地址+源地址+类型（如IP，IPX）+ 数据报+循环冗余校验
地址：6字节源MAC地址，目标MAC地址
如：帧目标地址=本站MAC地址，或是广播地址；接收、递交帧中的数据到网络层
否则，适配器忽略该帧
类型：指出高层协议（大多数是IP，但也支持其他网络层协议Novell IPX 和 Apple Talk）
CRC：在接收方校验
如果没有通过校验，丢弃错误帧
前导码：
7B 10101010+1B 10101011
用来同步接收方和发送方的时钟频率
使得接收方将自己的时钟调到发送端的时钟
从而可以按照发送端的时钟来接收发送的帧
无连接、不可靠的服务
无连接：帧传输前，发送方和接收方之间没有握手
不可靠：接收方适配器不发送ACKs或者NAKs给发送方
递交给网络层的数据报流可能有gap（间隔，有些数据丢了）
如上层使用像传输层TCP协议这样有rdt，gap会被补上（源主机，TCP实体）
否则，应用层就会看到gap
以太网的MAC协议：采用二进制退避的CSMA/CD介质访问形式
子主题
802.3以太网标准：链路和物理层
很多不同的以太网标准
相同的MAC协议（介质访问控制）和帧结构
不同的速率：2Mbps、10Mbps、100Mbps、1Gbps、10Gbps
不同的物理层标准
不同的物理层媒介：光纤，同轴电缆和双绞线
使用CSMA/CD
没有时隙
NIC如果侦听到其他NIC在发送就不发送：载波侦听（carrier sense）
发送时，适配器当侦听到其他适配器在发送就放弃对当前帧的发送，冲突检测（CD）
冲突后尝试重传，重传前适配器等待一个随机时间，随机访问（random access）
100BaseT and 10BaseT
100 mbps速率也被称为“fast Ethernet”
T代表双绞线
节点连接到HUB上：“star topology”物理上星型
逻辑上是总线型，盒中总线
节点和HUB间的最大距离是100m
HUB
hubs本质上是物理层的中继器
从一个端口收，转发到所有其他端口
速率一致
没有帧的缓存
在hub端口上 有CSMA/CD机制：适配器检测冲突
提供网络管理功能
Manchester编码
在10BaseT中使用
每一个bit的位时中间有一个信号跳变
允许在接收方和发送方节点之间进行时钟同步
节点间不需要集中和全局的时钟
10Mbps，使用20M带宽，效率50%
千兆以太网
采用标准的以太帧格式
自由主题
0 条评论
下一页
