https://www.youtube.com/playlist?list=PL6RdenZrxrw9inR-IJv-erlOKRHjymxMN
本单元将介绍计算机网络的基本原理。你将了解互联网是如何设计和运作的,了解它的优势和缺点。
互联网采用四层模型架构。从下到上分别为:物理层、数据链路层、网络层和传输层。每个层级都有不同的功能。
大多数应用层使用传输控制协议(TCP)来传输数据。TCP可确保数据包的有序和错误检查传输。
互联网通过将数据分成小包来进行传输。每个数据包都有个别的打包、传输和重组。这种方法提高了网络的鲁棒性。
网络层负责数据包的路由和转发工作。IP协议是网络层的基础,它指定了互联网地址和数据包转发规则。
IP地址标识互联网上的每一台主机。IP地址分配工作由网络管理员完成。
可以使用网络分析软件查看计算机如何使用互联网连接和传输数据包,从而检验本单元学习的知识。
网络最有趣的是运用它们的应用程序。大型网络专家戴维·克拉克提出,目前网络的指数式增长表明,连接本身就是一种回报,比任何单一应用程序如电子邮件或万维网更有价值。
连接的概念是两个位于世界不同地方的计算机可以连接到对方,并交换数据。如果您将计算机连接到互联网,您就能与所有连接到互联网的其他计算机交流。
网络应用程序的基本模型是:每个计算机运行着本地程序,这些本地程序通过网络进行通信。如今最常见的通信模式是双向可靠字节流。
例如,程序A运行在计算机A上,可以将数据写入连接,这些数据通过网络发送到计算机B,在计算机B上运行的程序B可以读取这些数据。同样,程序B也可以向程序A写入数据。
万维网使用了超文字传输协议(HTTP)。客户端打开与服务器的连接,并向服务器发送GET命令请求页面。
HTTP旨在建立一个以文档为中心的方式,使程序之间进行通信。例如,在浏览器中输入学校网址,浏览器就会打开与学校Web服务器的连接,并发送GET请求以获取首页。
服务器接收请求后检查请求是否合法,如果通过检查就发送响应。响应带有状态码,如200表示请求被接受,响应内容包含请求文档数据。
BitTorrent允许人们共享和交换大文件。不同于Web,客户端从多个其他客户端而不是单个服务器请求文件片段。
BitTorrent将文件分割为小块的数据称为piece。客户端从其他客户端下载完整piece后,就可以告诉其他客户端它具有该piece,让他人也能下载。
与Web和Skype一样,BitTorrent也是使用双向流的通信模式,但是它以更复杂的方式使用,例如通过Tracker跟踪客户端 peering信息。
Skype允许语音聊天和视频通话。当客户端A想呼叫B时,它打开一个连接到B,如果B接受就开始交换数据。
但是,由于NAT存在,外部节点很难打开连接到内部节点。Skype使用中继服务器解决这个问题。例如,如果AB都在NAT后,它们就通过中继服务器通信。
网络工程师将互联网所有的功能分为不同的层次,以提高互联网模型的可理解性和可维护性。
互联网最常用的模型是四层模型,从下到上分别为:
负责在单个链路上交换数据包,例如以太网和WiFi。
负责端到端交换数据包,并且使用IP协议。IP提供最佳努力交付,没有交付保证。
提供两种服务:TCP提供可靠交付服务,确保数据以正确顺序和完整性交付;UDP为不需要可靠交付的应用提供服务。
成千上万的应用程式,例如HTTP、BitTorrent等,均建立在传输层服务基础上运行。
各层通过向下层提供服务和向上层开放API来实现功能隔离:
这样每一层都可以独立设计和优化,互不影响。
IP是一种数据报服务。当我们要求IP发送一些数据时,它会创建一个数据报,然后将我们的数据放入其中。数据报是独立路由通过网络的一个报文,根据其报头中的信息进行路由。换句话说,数据报是自包含的。
数据报报头包含目的地IP地址(IPDA)和源IP地址(IPSA)。每个路由器根据IPDA进行转发决定。数据报将hop对hop通过网络,从源IP地址来到目的IP地址。
IP不承诺数据包一定能送达目的地。它们可能会延迟送达,误序或者永远不送达。但IP不会随意丢弃数据包,只会在必要时丢弃,例如路由器缓冲队列满时。IP不会重传丢失的数据,也不会通知源这些数据包被丢弃了。
IP不为一条通信保持任何状态信息。即使一个SKYPE通话包含许多IP数据包,IP层也不了解这个通话,只会单独路由每个数据包。
IP还提供其他服务:
尽量防止数据包无限循环。它使用TTL字段来删除可能陷入循环的数据包。
如果数据包过长,IP将进行分片。
IP支持任何链路层。它几乎不要求链路层能力。
IP为每份数据分配唯一的标识,防止数据包重复。
IP支持数据包优先级。
以上归纳了视频中的主要内容。
网络遵循四层模型,从应用层开始将数据流分割成段。传输层负责可靠地将数据段传送到另一台计算机中的应用层。数据段作为网络层数据包发送,网络层负责将数据包传送到目的计算机。
大部分网络传输使用TCP协议。TCP建立连接需要三次握手:客户端发送SYN包,服务器返回SYN-ACK包,客户端回复ACK包。然后双方就可以开始数据传输。
网络层使用IP地址将数据包传递给计算机。但对应用层而言,还需要端口号指明数据分发给哪个应用。TCP/IP网络中的网页服务器默认使用端口80。
交换机根据路由表将数据包转发到下一跳。路由表将IP地址模式匹配到输出端口。默认路由匹配所有包。
数据包从源主机出发,经过多个路由器转发,最终传送到目的地。路由器根据当前流量和网络拓扑选择输出端口。Traceroute工具可以显示数据包从源到目的的每个中继点。
使用Wireshark监视浏览器与网站服务器的数据包交换过程,看到TCP三次握手建立连接,然后HTTP请求和响应包传输网页数据。Traceroute显示数据包从本地到目的网站的传输路径。这展示了网络层视角下数据包如何在Internet上传输。
封包交换是互联网最初的设计理念,即将数据分割成独立的封包,每个封包中包含目的地址信息,路由器可以独立地将每个封包传输到目标。
每个封包包含源地址、目的地址以及数据内容,足以让网络将其传输到目标终端。封包交换网络中的交换机可以基于每个封包的目的地址独立进行转发。
早期封包可能包含完整的路由信息表明经过哪些交换机,每个交换机只需查看封包头而不需保持状态。但这会带来安全问题,现今网络采用简化模式,交换机本地存储目的地址与下一跳的映射表。
交换机对每个封包进行独立转发,不需要跟踪不同会话中的封包组,这使得交换机设计简单高效。若要为每个会话设置状态,会造成管理和性能问题。
封包交换让网络资源如链路能在 unterschied流量间进行统计多重化分享,如两个用户同时访问,链路带宽可以动态分配。这大大提高了网络利用率。
尽管当时有争议,但封包交换理念已经成为构建网络的基石。它使网络设计简单,且让网络资源能高效共享利用。
层次结构原则是将系统划分为多个功能层次或组件,各层次之间通过标准接口进行交互。
可扩展性强,每个层次独立开发。
减少层与层之间的复杂依赖关系,提高各层独立性。
分离关注点,每个层次只关注自己的功能。
上层层次重用下层服务,提高利用率。
允许各层独立升级和改进。
计算机编程、电子邮件、Web浏览器和TCP/IP协议栈都是典型的层次结构设计。
计算机编程编译过程也采用层次结构,如词法分析、语法分析等层次独立运行。
极少情况下,如操作系统内核可能需要使用汇编语言打破层次结构,这将丧失独立性和可移植性。应尽量避免这种情况。
网络通信也采用层次结构设计,各层通过标准接口实现对等交互,如TCP协议中的三次握手通信过程。
这种设计使网络系统具有良好的隔离性、可扩展性和兼容性。
封装原则指通过在数据包中组织协议层信息的方式,既可以保持层次结构,也可以让各层共享数据包内容。
通过将数据划分为离散单元(数据包),在每个数据包中嵌套不同协议层的信息头和数据载荷,实现了层次结构和分组交换的结合。
每个协议层在数据包中包含头、载荷和尾。较高层协议作为较低层协议的数据载荷进行传输,实现不同协议层信息的封装。
举例说明如何将HTTP获取请求封装到TCP段中,再封装到IP数据包和无线网卡帧中进行传输。Wireshark可以观测到各层协议在数据包内的位置。
实现了系统各层的隔离性和独立演进能力。例如操作系统内核和Transport层的变更都不会影响应用层。封装也可以递归应用,实现更复杂的网络架构。
VPN通过TLS封装IP数据包,实现内部网络与外部网络的安全隔离。
计算机内存以字节为单位进行存储,多个字节表示一个值时需要确定字节顺序。
主要有小端字节顺序和大端字节顺序两种。小端字节顺序是将低位字节存储在低地址,高位字节存储在高地址。大端字节顺序正好相反。
如果要存储1024(十六进制0x0400),需要2个字节。小端字节顺序下,低地址字节存储0x00,高地址字节存储0x04。
当前主流计算机采用小端字节顺序,因为它在计算上性能更好。但人类阅读文本时习惯从高位数字开始,这与大端字节顺序一致。
由于不同架构计算机存在字节顺序差异,网络通信数据需要统一字节顺序,否则在不同平台上无法正常解析收发数据。
没有提供题目内容,需要答题时判断每个数字的十六进制表示在小端字节顺序还是大端字节顺序。不使用计算器或者其他工具辅助。
53 为小端字节顺序,因为其十六进制表示为0x35,最低有效位在最低地址。
4116 为大端字节顺序,等价于4096+20,最高有效位在最低地址。
5 为大端字节顺序,最高有效位在最低地址。
83,886 为小端字节顺序。
80 为小端字节顺序。
305,414,945 为小端字节顺序,通过判断奇偶性分析Least Significant Bit位置。
不同处理器采用不同的字节顺序存取多字节数据,为了实现通信需要统一字节顺序。
网络协议一般采用大端字节顺序(大字节在低地址)。如IPv4使用大端存放数据长度字段。
处理器与网络可能采用不同顺序,需要函数如ntohs()进行转换。读取网络数据须先转换为主机顺序,写入网络数据须先转换为网络顺序。
Wireshark可以查看TLS报文中的IP报头长度字段字节顺序,验证其为规定的大端格式。
需要明确处理器与网络顺序的转换点,严格按规定进行转换,免得重复或遗漏导致问题。常用库提供转换函数供调用。
IPv4地址长度为32位,通常用点分四段格式表示,如192.168.0.1。
IPv4地址唯一标识网络中的设备,IP层根据地址向对应设备传送数据包。
子网掩码用于区分内网和外网地址,将连续1开始的位数与地址进行与运算,相同则在同一子网。
255.255.255.0表示前24位为1,相同的24位则在同一子网内可以直接传送数据包。
使用ifconfig命令可以查看本机IPv4地址和子网掩码,根据两个地址与子网掩码的与运算判断是否在同一子网内。
以下条件下判断目的地址是否与源地址在同一子网内:
源地址:192.168.1.33 目的地址:192.168.1.64 子网掩码:255.255.255.0
匹配,在同一子网内
源地址:192.168.1.33 目的地址:192.168.2.64 子网掩码:255.255.255.0
不匹配,不同子网
源地址:192.168.1.33 目的地址:192.168.1.64 子网掩码:255.255.0.0
匹配,在同一子网内
源地址:192.168.1.33 目的地址:192.168.2.64 子网掩码:255.255.0.0
不匹配,不同子网
通过与源地址进行与运算与子网掩码判断目的地址是否在同一子网内。
将源地址和目的地址分别与子网掩码进行与运算,查看结果地址是否相同。
若相同,则在同一子网内;若不同,则不在同一子网内。
源地址:10.0.1.32 目的地址:10.0.2.16 子网掩码:255.255.255.0
与运算结果: 源地址:10.0.1.0 目的地址:10.0.2.0
不相同,不在同一子网内。
IPv4地址最初分为A、B、C三类,将地址分为网络号和主机号。
A类:128个网络,每个网络216个主机 B类:216个网络,每个网络216个主机 C类:224个网络,每个网络28个主机
分配不够灵活,如大学获得的A类地址过多未充分利用。
允许网络前缀长度为任意位,定义门限值2的N次幂大小的地址块。
如/16表示网络前缀长度为16位,定义216个地址;/20定义2^12个地址。
IANA->RIR->ISP,RIR负责各大洲,ARIN负责北美,APNIC负责西太平洋地区。
IANA划分最后5个/8块给每个RIR后,地址分配管理权利转给各RIR。
路由器通过路由表决定将数据包转发到哪个链路。
包含目标网络号和下一跳的链路接口,网络号使用CIDR表示法。
将数据包的目的地址与路由表对比,选择匹配度最高的可用路由转发数据包。
路由表包含默认路由和171.33.0.0/16两项项目。
接收171.33.5.245的数据包,匹配171.33.0.0/16项目转发。
一个地址可能匹配多个项目,选择前缀长度最长的项目转发。
前缀长度为0,匹配任意地址的数据包。优先级最低。
根据目标地址与路由表进行LPM匹配,选择下一跳接口转发数据包。
包含默认路由和171.33.0.0/16,171.168.0.0/16两项项目。
171.33.5.245
根据最长前缀匹配规则,匹配171.33.0.0/16项目,通过链路5转发。
171.168.5.1
根据最长前缀匹配规则,匹配171.168.0.0/16项目,通过链路3转发。
200.1.1.1
根据最长前缀匹配规则,匹配默认路由0.0.0.0/0项目,通过链路1转发。
将数据包的目的IP地址与路由表项目进行比较,选择匹配程度最高的项目决定通过哪个链路转发。
匹配默认路由和63.19.5.0/30,/30前缀长度30比默认路由长,通过链路3传送。
匹配默认路由、171.0.0.0/8和171.0.0.0/10,/10前缀长度10比其他两者长,通过链路4传送。
匹配默认路由,但不匹配63.19.5.0/30,通过链路1传送。
只匹配默认路由,通过链路1传送。
匹配默认路由和171.0.0.0/8,但不匹配171.0.0.0/10,/8前缀长度比默认路由长,通过链路2传送。
将地址与路由表项目进行前缀长度匹配,选择匹配度最高的项目决定通过哪个链路传送数据包。
网络层使用IP地址标识主机,链路层使用MAC地址标识网络接口卡。两种地址不同但在实际应用中会对应mapping。
地址解析协议(Address Resolution Protocol, ARP)负责进行IP地址和MAC地址之间的动态对应。节点发送ARP请求后,拥有请求IP的节点回应其MAC地址。
ARP报文有硬件类型、协议类型、硬件地址长度、协议地址长度、操作码(请求/回应)以及源/目标地址等字段。
ARP表项默认20分钟过期。节点也可广播ARP请求同时刷新其它节点的ARP表。
大多数应用通过可靠的双工字节流来进行通信。知识点包括:
网络采用四层模型:物理层、数据链路层、网络层、运输层。网络层使用IP地址标识主机,IP被视为网络的“细腰”。
IP负责地址寻路、包的封装与传递。IP版本包括IPv4和IPv6。IP地址标识网络主机,路由器根据地址进行转发。
基础原理包括:分组交换、分层设计、封装。分组交换使数据以包的形式在网络中传输;分层设计降低复杂度;封装实现各层独立运作。
该课程首先介绍应用如何使用网络;然后系统地介绍四层网络模型、IP协议及其工作原理;最后总结基本网络设计原理。这些基础知识构成现今网络的基石。
1990年代中期,尽管已经有一些试验性技术可以实现计算机之间的语音通讯,但没有商业产品可以实现计算机到固定电话网络的语音通话。1996-1997年,计算机硬件性能和网络带宽都有了较大提升,这为Voice over IP奠定了基础。
traditional电话交换机当时采用单片机设计,代价高且操作维护成本高。捷时公司研究将电话交换系统控制模块运行在常规服务器上,以软件方式控制硬件资源进行语音交换,这就是软交换技术。这 revolutionized 电话交换领域。
为实现计算机到固定电话的连接,需要协议支持两端进行呼叫设置。Jon Peterson参与开发了Session Initiation Protocol (SIP),它可以在IP网络上进行呼叫控制并建立多媒体会话。SIP成为Voice over IP成功的基础。
SIP标准中为保证通信安全做出了许多补救,但为了可实现性也做出一定妥协。随着信令和媒体流可由中间节点获取的问题被广泛关注,ITF现已将重点放在解决PRISM计划等事件带来的隐私保护问题上。
SIP广泛应用在Skype、VoIP设备、3G电话等场景的信令传输。网络运萢商也采用类似SIP的信令机制构建语音架构。但SIP依赖中间节点也带来一定风险。理想状态下,SIP应端对端驱动,不依赖中间功能节点。
传输层提供应用层数据的通信服务。UDP提供简单且不可靠的数据报传输。TCP提供可靠的二进制字节流传输。
TCP连接的建立需要信息交互。TCP分段中包含有效载荷和头部字段。TCP需要检测数据错误并进行纠错,以实现可靠传输。探讨TCP如何设计和实现可靠传输。
检查和检测数据错误的三种算法:校验和、循环冗余校验和消息鉴别码。这些算法能识别分组是否被篡改。
分析网络协议设计的基本工具有限状态机。介绍TCP如何使用限状态机进行会话管理和连接控制。
介绍用户数据报协议UDP和Internet控制消息协议ICMP在传输层的应用。UDP提供不可靠数据报服务。ICMP传输控制信息,如报告错误。
深入介绍传输层各个重要原理,包括可靠传输机制、信息交换过程、错误检测算法以及TCP工作状态机设计,以实现可靠高效的数据传输。
TCP作为运输层协议,主要为应用层提供以下服务:
可靠的数据传输服务。TCP可以检测和纠正数据传输中的错误,还可以检测和请求缺失的数据段。这些机制可以确保应用层收到完整和正确的数据。
序列化的数据传输服务。TCP将应用层的数据以流的形式传输,并按顺序交付。收到的数据的顺序与发送的数据顺序一致。
支持流量控制。TCP可以防止快速发送方过快发送数据而超过接收方的处理能力,从而避免受到拥堵。
面向连接的服务。TCP建立连接后,两端形成全双工通道来传输数据。
TCP通过下列四种机制实现可靠的数据传输:
数据确认。接收方在正确接收数据后,将发送确认消息告知发送方。
校验和。TCP段内附带校验和用于检测传输过程中的错误。
序列号。每段数据都附带序列号,用于检测丢失的数据段。
流量控制。接收方告知发送方自己缓冲区空间大小,防止接收方缓冲区溢出。
TCP报文头较长且复杂,主要字段包括:
TCP通过这些字段实现可靠数据传输服务。
UDP(用户数据报协议)是运输层下的一个报文层通信协议。它比TCP简单得多,没有建立连接和可靠传输等机制。
UDP报文只包含四个主要字段:
UDP提供的是无连接、不可靠的报文服务:
因此,如果应用需要可靠传输,需要自行实现重传机制。
DNS、DHCP等简单查询-响应协议常使用UDP,因为:
部分实时音视频服务历史也使用UDP,但今天多采用基于TCP的HTTP传输。
相比TCP,UDP提供了更简单直接的报文层服务,用于不需建连接和可靠传输的场景。
ICMP(互联网控制消息协议)用于报告网络层错误和诊断问题。
ICMP运行在网络层之上,严格来说是传输层协议。当主机或路由器需要报告错误时,会将错误信息封装在ICMP负载中,交给IP传输。
ICMP报告消息采用不可靠传输模式。它仅发送简单数据报,不尝试重发,也不维护已发送消息的状态。它只是简单地反馈错误指示,而不是完整报告。
常用的ICMP消息类型包括:
Ping命令使用ICMP回显请求(类型8代码0)和回显应答(类型0代码0),测试目标主机是否可达以检查连接。
Traceroute通过设置IP数据报的TTL字段来识别网络路径上的路由器。它发送UDP数据报,TTL设置为1,首跳路由器回送TTL耗尽报告。Traceroute重复增加TTL,逐步识别路径上的全部路由器。
末端到末端原则在互联网设计中占有非常重要的地位。它包含两个原则:
如果不遵循这个原则,网络系统很可能会出现错误并传输数据错误。
强末端到末端原则规定,网络的职责是尽可能高效灵活地传输数据报,其他一切功能应由网络边缘完成。
这两个原则最早由萨尔扎、克拉克和里德在1984年的论文中提出。
末端到末端原则认为,功能的实现必须由应用层站在末端进行,才能确保正确性。网络可以提供帮助但无法负责正确性。
例如在文件传输中,要确保文件完整无误需要源端加入检验信息,目的端整合后检验。只有这样才能确保传输正确。
TCP提供可靠字节流服务,但不完美,有可能传输错误数据。因此也需要应用层进行末端到末端检验。
无线链路层提供性能优化,提高低可靠性链路的可靠性,但不负责正确性,这与末端到末端原则一致。
强末端到末端原则强调网络只负责高效灵活地传输数据报,其他功能由边缘完成,为网络设计带来更大灵活性。
网络和其主机都可能会出现错误。为了网络能正常运作,就需要能够检测这些错误。
常见的错误检测算法有:
简单实施,但是检测能力较弱。主要是TCP/IP使用。原理是把数据包中的各字节相加,如果和为0xffff,则校验通过。
计算成本较高,但是检测能力更强。可以检测单个错误位,以及错位长度小于CRC位数的错位块。以太网等链路层通常使用。
使用密钥,可以检测数据是否被篡改。但是对错误检测效果不如CRC。TLS等传输层安全使用。
以上三种错误检测算法各有优劣,选择应视情况而定。链路层主要使用CRC,而TCP/IP层校验和就足够了,因为链路层已经完成了重要的错误检测工作。
了解这些错误检测算法的不同特点,能助益网络通信协议的设计。
有限状态机(Finite State Machine,FSM)是网络协议和系统设计常用的一种形式。
FSM由有限数量的状态组成。每个状态表示系统的一个配置。
状态间通过事件和动作进行转换。事件会触发状态转换,动作表明状态转换后的行为。
FSM通过边缘中的标签来描述状态之间的转换关系。标签包含事件和可选的动作。
同一状态下,对同一事件只能有一个唯一的转移。转移必须明确定义,否则FSM的行为会不明确。
FSM示例:描述基本HTTP请求的三种状态——就绪状态、请求页面状态和请求待进行状态,以及各状态下的事件和动作。
可以 partially 规范化 FSM,只明确常用场景,其他情形留若干空隙或用文字进行补充。这可以平衡简明和完整之间。
假设FSM从关闭状态开始。然后:
该情况下,插座将处于的状态是: 关闭状态
假设FSM从关闭状态开始。然后:
该情况下,插座将处于的状态是:关闭状态
所以问题一中的答案是FIN_WAIT_1状态。
TCP连接处于建立状态后,开始进行数据传输。
当一端主动关闭连接时,称为active closer。它会发送FIN包,状态转移到FIN_WAIT_1状态。
另一端收到FIN后,状态转移到CLOSE_WAIT状态。这端称为passive closer。
passive closer可以继续发送数据,active closer会进行ACK。
passive closer也可以主动关闭,发送FIN并状态转移到LAST_ACK状态。
两端也可能同时主动关闭,交叉发送FIN包。此时都进入FIN_WAIT_1状态。
FIN_WAIT_1状态后,可能结果包括:
passive closer ACK但不发送FIN,状态转入FIN_WAIT_2
passive closer也发送FIN,状态转入TIME_WAIT
两端同时主动关闭,状态转入CLOSING然后TIME_WAIT
TCP从SYN建立连接到FIN断开连接,过程对称且精确定义,可以规避实现上的歧义。
流控制解决发送速度快于接收速度的问题,避免数据包丢失。
Stop and wait协议保证任何时刻只有一个数据包在网络中。
发送方发送一个数据包后进入等待ACK状态,接收ACK后再发送下一个数据包。未收到ACK会在超时后重传该包。
接收方收到新数据后发送ACK。
如果ACK丢失,发送方会超时重传数据包。如果数据成功但ACK丢失,也会产生同样情况。
发送方有两个状态:等待数据和等待ACK。接收方只有一个等待状态。
可能出现 ACK被延迟导致超时重传并产生重复发送的数据包情况。
使用单bit计数器可以区分ACK是否应答原始数据包还是重传数据包。
该计数器有两个假设:1网络不会重复发送数据包 2数据包不会被延迟超过多个超时期。
本视频主要介绍了窗口滑动控制算法,这是目前大多数高性能协议使用的流控制算法。
首先回顾简单的停止等待流控制算法。该算法一次只允许一个数据包在途,发送方发送一个数据包后,等待接收方回传确认包。如果没有收到确认包,则断定超时并重传。该算法简单实用。
但是,停止等待算法有一个主要问题。假设通信链路的瓶颈速度是10Mbit/s,但由于时延等原因,一次只能传输一个数据包,则实际传输速度只有2%的链路速度,效率很低。
为解决这个问题,引入了窗口滑动流控制算法。其基本思想是:允许最大N个数据包同时在途,不必等待前一个包确认后再发送下一个包。
具体来说,发送方和接收方都维护三个变量:窗口大小、最后确认的包序列号和最后发送/接收的包序列号。发送方要保证未确认包序列号与窗口大小之差不超过窗口大小,接收方同样。
接收方采用累计确认机制,即确认收到的连续数据段的最后一个包,代表已经接收该段内所有包。
如果设置好窗口大小,使得每次时延内可以发送的包数充满链路速度,就可以实现最大传输效率。
本视频主要对可靠通信中常用的重传策略进行解释。
滑动窗口可靠传输协议采用累计确认机制,接收方只会确认收到的最后一个包序列号。如果未确认的包超时未收到确认,则需要重传该包。
常见的两种重传策略是:
回退n strategry(Go Back N)。若发生包丢失,将从丢失包处开始重传之后未确认的全部包。这种策略保守,认为如果一个包丢失,则后续包也很可能丢失。
选择重传(Selective Repeat)。仅重传未收到确认的单个包。这种策略相对乐观,认为单个包丢失不代表后续包也会丢失。
选择重传效率较高,但如果丢失包连续,恢复速度可能较慢。回退n策略恢复速度快,但效率较低,可能重传无须重传的包。
实现可靠传输时,需要维护每个包的超时定时器。超时则启动重传。同时要注意发送端窗口大小,不发送超出窗口大小的额外包。
实现协议时,可以选择回退n或选择重传两种策略,视具体网络环境和效率要求而定。接收窗口大小也影响选择何种策略。
TCP报文头共20个字节,由以下几个字段组成:
源端口和目的端口:每个16位,标识报文来源端口和目的端口。
序列号:32位,标识段内首个数据字节在数据流中的序列号。
确认号:32位,确认已收到的数据序列号加1。
校验和:16位,用于 检查报文是否出错。计算的范围包括TCP报头、数据和伪首部(部分IP头)。
窗口大小:16位,表示接收缓冲区可用大小,用于流量控制。
控制位:包括SYN、FIN、RST、PSH、ACK和URG等,标识报文类型。
急需指针:16位,如果紧急位被设置,指明紧急数据在报文中的位置。
选项偏移量:4位,如果报文带有选项字段,指明数据起始位置。
此外,TCP还可以通过添加选项字段扩充功能,如MSS(最大报文长度)等。TCP报头加上选项共计20~60字节不等。它为可靠数据传输提供了序列号、确认号、校验和、流量控制等机制。
TCP连接建立使用三次握手。
主动打开方(Active Opener)发送带SYN标记的报文,表示同步序列号。主动打开方的序列号标记为Sa。
被动打开方(Passive Opener)收到报文后,回复一个带SYN-ACK标记的报文,同时设置ACK标记。被动打开方序列号标记为Sp,并ACK主动打开方序列号Sa加1。
主动打开方收到后回复一个只带ACK标记的报文,ACK被动打开方序列号Sp加1。此时双方建立连接,并开始数据传输。
如果双方主动打开连接,两者同时各自发送带SYN标记的报文。随后各自回复,带SYN-ACK标记和ACK标记。交替应答建立连接,此过程需要4个报文,而不是标准三次握手的3个报文。
使用Wireshark可以实际监测TCP三次握手建立连接的报文。例如使用telnet建立端口80连接,可以观察到先后发送和接收的三个报文,其中第一个报文带SYN标记,第二个报文带SYN-ACK标记,第三个报文只带ACK标记。
建立连接后,主机开始通过TCP报文传输实际的数据内容。报文带有序列号和ACK标记标识报文位置。数据传输的报文还带有实际数据长度字段。
TCP连接双向传输,需要双方都不再发送数据时才能真正断开连接。
一方发送带FIN标记的报文,表示无更多数据发送。另一方回复ACK报文确认。之后再由另一方发送FIN报文,再经确认,连接才真正终止。整个过程需要4个报文。
TCP通过序列号和确认号簿管理连接状态,保证数据可靠传输。它使用三次握手建立连接,传输数据时通过报文编号实现流控,双向关闭需要四次交互完成断开操作。这套机制是Internet可靠通信的基石。
TCP:提供可靠的双向字节流传输服务,用于95%以上的Internet应用。
UDP:提供无连接的报文传输服务,用于无需可靠传输的应用,如DNS、DHCP等询答协议。
ICMP:主要用于传送网络故障报告,帮助诊断网络连接问题。
TCP通过序列号和确认号实现流量控制,检测丢包和错误,通过重传机制保证可靠传输。
建立连接需要三次握手,采用滑动窗口和选择重传策略传输数据。连接由有限状态机管理。
UDP将应用数据封装成报文,直接传送而不提供追踪和确认。适用于少量应用如DNS查询。
当路由器无法转发IP数据报时,会使用ICMP错误报文通知源主机。帮助诊断网络连接问题。
网络设计应遵循正确实现功能在网络终端的原则。网络层应保持简单,功能越多越容易出错。
了解了三大运输层协议TCP、UDP和ICMP在Internet上的主要作用,tcp的可靠传输实现机制,以及网络设计的重要原则——结束至端原则。
主要研究3D打印、传感器网络及其所带来的政策挑战,比如网传生物打印的监管难题。
视频介绍网络层数据包交换原理,并解释其三个组成延迟及实时应用解决方式。可以回答网络延迟计算及路由器转发机制等问题。
公元前2000年,人类使用简单的火光信号传递预设的信息。
1600年代开始,人们发明用字母码表示整个字母表来传输任意信息。
1700年代早期,常用词和短语采用数字码,进行简化编码。
1700年代,人们为控制信号发明了代码,例如开始和结束发送,减慢发送速度等,这就形成了第一个协议的雏形。
1793年,法国的克劳德·夏普发明并建立了第一套光学电报网路。
1793年,法国政府在190公里里建立了15个站点。1804年,网络已经达到370公里。
光学电报系统发展出代码、流量控制、同步等现今网络必备的概念。
1876年,亚历山大·格拉汉姆·贝尔在美国成功进行了首次电话通话。
电话的发明极大提升了通信效率。到1915年,第一条跨洲电话线路建成。
1962年,美国麻省理工学院的韦纳·博克开始提出“星际网络”概念。
1969年,美国国防部高等研究计划局建立了第一版因特网——ARPANET,连接了4个节点。
1983年,TCP/IP正式在因特网范围内使用。1990年,WWW问世。
帧中继是早期电话网络中的传输方式。每个通话都需要建立专用电路,保证通话质量。但是它存在一些缺点:
带宽利用率低。通话间歇期电路闲置而无法被其他通话使用。
应用需求差异大。不同应用需要不同传输速率,固定速率电路难以适应。
状态管理复杂。每条通话都需要在每个路由器维护对应状态,随网路规模增大管理难度也增大。
而包交换网络采用分组的形式实现传输。每个数据块Header加地址后作为一个数据包发送。包交换会维持每个路由表,按照目标地址选取下一跳路由器,实现跳跃式传输。
其优点是:
带宽利用率高,包可以并行传输而不需要专用电路。
流量响应灵活,可以根据应用需求实时调整传输速率。
状态管理简单,每条传输无需维护全程状态。
因此,包交换机制成为当今互联网的主流传输方式。它可以高效利用网络资源,适应各种网络应用的需求。
传播延迟是从一个节点到另一个节点间单位信息传播的时间。它取决于链路长度l和信息在链路中的传播速度c,用公式表示为:
传播延迟t=l/c
其中c一般取2×108m/s,等于光速的99%。
封包化延迟是从一个节点开始发送封包的第一个比特,到发送完最后一个比特的时间间隔。它取决于封包大小p和链路带宽r,用公式表示为:
封包化延迟t=p/r
端到端延迟是从源节点开始发送第一个比特,到目的节点接收最后一个比特的时间间隔。它等于在整个传输路径上每个链路的传播延迟与封包化延迟的总和。
端到端延迟t=Σ(传播延迟+封包化延迟)
由于封包在链路上会与其他封包争用资源,当封包数量超过链路处理能力时,多余的封包需要在路由器队列缓存等待发送,引入了额外的队列延迟。队列延迟会使端到端延迟变得不可预测。
路由器采用先入先出方式处理队列中的封包。队列大小决定丢包概率。
包交换式传输将数据分割为多个固定长度的分组,每个分组通过网络传输,各个分组可能采取不同的传输路径。
交换机是网络节点,负责将分组从一个端口发送到另一端口。交换机分析分组头部信息(如目的地地址),以确定分组应被发送到哪个端口。
端到端延迟是指数据从源节点到目标节点耗费的总时间。它包含了如下几个部分:
分组化延迟:将数据分割为分组的时间
传播延迟:分组通过网线和交换机传播的时间
队列延迟:分组在交换机等待其他分组传输的时间
队列延迟会导致端到端延迟变得不确定,这对一些应用如实时视频通信来说是个问题。
实时应用如视频 streaming 会采用播放缓冲区来解决队列延迟不确定性问题。
客户端会主动获取更多的数据包,形成播放缓冲区。即使后续分组延迟,也可以从缓冲区中获取数据进行播放,使得播放不会中断。
缓冲区越大,就可以容忍更大的延迟波动。但缓冲区也不能无限大,需要在实用性和流畅性之间找到平衡。
可以通过目标-时间图来分析播放缓冲动态:
从图中可以明确播放点、缓冲区大小、数据消耗速率等参数,帮助设计和诊断播放器。
本视频将讨论不同的队列模型。
首先是最简单的确定性队列模型。它可以帮助我们理解许多简单队列系统的动态。这通常是理解网络中的情况的一个很好的开始。
确定性队列模型将路由器和其队列绘制成标准形式。假设包以某个接口进入队列,然后通过输出链接离开。
任何时间点t,都可以知道队列的占用量q(t)。即在t时刻队列中包的数量或字节数。
同样,可以知道累积到达量a(t)和累积离开量d(t),即分别到t时刻累计到达和离开的包或字节数。
假设输出链接速率为r,则可以画出a(t)和d(t)随时间的变化曲线。此时,q(t)的值就是a(t)和d(t)曲线之间的垂直距离。
对于在t时间到达的一个字节,其排队等待时间d(t)就是其a(t)和d(t)曲线之间的水平距离。
通过此模型可以直接得到q(t)和d(t)的值,理解队列和延迟的动态变化情况。
分析一个示例:每1秒有一个100比特的包以1000比特/秒的速率到达队列。输出链路速率为500比特/秒。
可绘制a(t)和d(t)曲线。根据两曲线之间的距离,每1秒循环中的平均q(t)值为25比特。整个循环平均q(t)为5比特。
如果消息采用一个大包传递,端到端延迟由各路由器间链路传输延迟和每个路由器内包处理延迟之和组成。
如果将消息划分为小包,每个小包在每个路由器内的处理延迟会更小。因而端到端延迟也会更小。
小包化可以使消息以较快速度通过队列,从而减少整体延迟。这就是要将消息分裂成小包的原因。
本节介绍队列的一些重要参数,这些参数在分析队列延迟时很有用:
使用图示了队列的到达和离开事件。到达表示为向下箭头,离开表示为向上箭头。然后绘制了队列容量Q(t)随时间的变化曲线。
有时会出现“虚拟离开”,即容量为零时仍有离开事件发生。这会导致“漏送”,系统无法从良好行为中获得奖励。
分别给出了周期到达和突发到达两种情况下队列容量Q(t)的变化曲线。突发到达会使平均容量和方差都增加,从而增加延迟。
随机到达的平均等待时间会长于周期到达。确定性越高,延迟越小。
在研究队列时,常用泊松过程来模拟随机到达过程。泊松过程具有“无记忆”特性,这对于建模队列很重要。
本节主要介绍了队列的一些基本概念和属性,为后续理论知识提供了直观的理解基础。
包交换器有三个主要阶段:
地址查找:检查转发包的目的地址,通过查找转发表来确定下一个节点。
头部更新:如需要,更新包头,例如IP路由器需要减1时延字段TTL。
缓冲队列:可能出现拥堵,使用缓冲内存暂时保存等待输出的包。
一般包交换器有多个输入和输出端口。每个输入包通过查找表后,会转发到相应输出队列。若输出队列已满,则包会储存在缓冲内存中等待。
以太网交换机完成以下4个操作:
检查每一帧报头的目的以太网地址。
如果地址在转发表中找到,则转发到相应输出端口。
如果地址未找到,则广播给所有端口。
通过学习源地址表来更新转发表。
以太网交换机使用哈希表存储MAC地址,通过精确匹配查询表获取输出端口。
IP路由器完成7个操作:
检查以太网报文以太网目的地址是否为路由器本身。
检查IP版本号是否为IPv4。
减1TTL字段,更新IP头校验和。
4.通过最长前缀匹配查找IP目的地址,获取下一个路由器接口地址。
IP路由器使用最长前缀匹配查询表,获取路由下一跳目的地址,而非精确匹配。
以太网交换机使用哈希表高效存储和精确匹配MAC地址。
IP路由器使用最长前缀匹配表,匹配IP地址前缀查找下一跳接口地址。前缀表示IP地址部分最高有效位相同的地址集合。
帧中继交换机主要有两个工作步骤:
根据帧头中的目的地址在转发表中查询目的端口。
根据查询结果将帧转发到正确的输出端口,这样帧才能通过正确的输出链路送到目的地。
输出队列交换机将输出队列设置在交换机的输出端口上。这样做最大限度地提高了吞吐量,并最小化了平均延迟。
但是,输出队列交换机存在以下问题:
当多个流全都需要发送到同一个输出端口时,输出队列的写入速率可以达到N倍的输入线速率,其中N是输入端口数。
输出队列需要运行的速度变为N+1倍输入线速率,随着N的增加,这对输出队列的要求就越高。
长期来看,输出队列的写入速率不能持续达到N倍线速,否则系统无法维持。只能通过拥塞控制将平均写入速率控制在1倍线速内。
输入队列交换机将队列设置在交换机的输入端口上。这样可以解决输出队列交换机的问题:
输入队列只需要一次接收一个帧,一次发送一个帧,运行速度可以降低到2倍输入线速率。
相比输出队列,输入队列适合实现更大规模的交换机。
但是,输入队列交换机也存在头阻塞问题:当多个输入流头部帧均需要发送到同一个输出端口时,会使其它流的帧被阻塞,导致吞吐量下降。
虚拟输出队列是一种解决输入队列头阻塞问题的方法。每个输入端口为每个实际输出端口维护一个单独的队列。这样帧会根据目的端口分类到不同的队列,队列内帧均去向同一端口,避免了头阻塞问题。
虚拟输出队列能够将输入队列交换机的吞吐量提升至最优水平。它已广泛应用到高速交换机设计中。
首先来介绍先入先出(FIFO)队列的一些问题。如果有许多数据包通过这个队列,发送速率最高的流将获得最大的带宽,占用更多的输出链路。这就会发生“拥堵”,大流量流可以挤压低流量流。
FIFO队列鼓励了不良行为,比如一个流会尽量快速发送数据包来挤走其他流。这样会给网络带来负担。
如果有些流量比如控制流量更重要,FIFO队列无法根据优先级处理数据包。它只根据数据包到达顺序来发送,对优先级没有考虑。
为解决这些问题,可以采用严格优先级机制,用两个队列分别处理高优先级流量和低优先级流量。高优先级队列永远先于低优先级队列被服务,这样可以完全隔离低优先级流量的影响。
但如果高优先级流量过多,可能会完全 starvation低优先级流量。此方法最好只用于高优先级流量数量适中的情况。
加权优先级相比严格优先级,可以给不同流量定义不同的权重,实现更灵活的优先级控制。
比如高优先级流量定义权重为2,低优先级流量定义权重为1。则高优先级流量占用输出链路带宽的2/3,低优先级流占1/3。
但与实际情况不符的是,此方法假设数据包大小相同,实际上数据包长度差异很大。如果直接按包处理,将破坏优先级设置。
为解决数据包长度不均匀的问题,可以使用“模拟时间”来实现加权优先级。
仍然采用轮询各个队列的方法,但每个轮询周期,向各队列中发送的不是包,而是位(bit)。每个队列的发送位数等于它的权重值。
这样就实现了按权重分配传输资源,而不受数据包实际大小的影响。通过这种思考实验,为后续的实际算法奠定了理论基础。
本节讨论了分组交换网络中的延迟保证。
端到端延迟的公式包含三个部分:分组化延迟、传播延迟和队列延迟。第一两个部分是固定的,由网络控制;队列延迟一般不受控制,很难保证延迟。
如果使用加权公平队列,可以保证每个流的服务速率。 knowing 队列的Buffer大小和每个流的服务速率,可以计算该队列的最大延迟上限。
如果知道每个Router中每个队列的最大延迟,就可以计算端到端的延迟上限。
但如果到达速率过高,可能导致Buffer泄漏。 为了防止此情况,可以使用σ-ρ流量控制:
如果满足σ-ρ流量控制,并且服务速率大于ρ,就可以保证Buffer不会溢出,也就可以提供延迟保证。
具体实现时,可以将流分组后插入对应的队列中,各队列使用加权公平队列算法服务,从而保证每个队列的最小服务速率。这可以实现端到端的延迟保证。
本例分析了两个主机通过三个路由器连接时, packets 传输延迟是否满足要求的实例。
分析步骤:
队列延迟为总延迟减去固定延迟,为10ms - 5.48ms = 4.52ms
问题要求队列延迟平均分配到3个路由器,则每个路由器的队列延迟最大为4.52ms/3 = 1.507ms
所以每个路由器的最大延迟为1.507ms,满足主机要求的端到端延迟10ms限制。
在这单元中,你学习了许多关于分组交换的知识:
分组交换是网络通信的基础,它简单高效,且可以更好恢复网络故障。每个数据包包含了达到目的地所需的信息。
理解分组交换带来的后果是理解网络延迟的关键。延迟包含分组化延迟、传播延迟和排队延迟三个部分。
使用几何模型可以视觉化路由器队列的变化,进而理解延迟产生的原因。
实时应用通过播放缓冲区平滑网络延迟不确定性,确保流畅播放。但无法完全避免暂停。
通过队列服务率控制,网络能提供流量速率和延迟保证。
交换机和网络路由器通过寻找转发表来转发分组,并在输出端口忙时缓存分组。它们工作原理类似。
学习这些知识可以帮助你解释网络延迟成分,设计播放缓冲,说明分组交换机制,以及分析网络流量寻求延迟和速率保证等。这对理解网络体系结构和操作很重要。
塞斯科的汤姆·埃德塞介绍了以太网交换机和路由器的发展历史。
最早成功的以太网交换机是塞斯科公司设计的Catalyst 5000,它采用定制芯片实现固定端口桥接功能。集线卡上装有12个这种应用特定集成电路(ASIC)芯片,每个芯片对一个端口进行桥接处理。多个集线卡通过后面板总线连接组成整机。
后来塞斯科试图在硬件上实现路由功能。当时塞斯科的主流路由器依靠MIPS处理器运行软件,效率较低。通过不断研究,他们最终证明可以在硬件上实现路由。第一个这样的产品可以将首包导向集线卡上的软件路由器处理,同时在硬件上缓存流信息。返回后与缓存对比,记录层二报头重写信息,从而实现后续包的快速转发。
软件和硬件之间实现了独立运行。硬件实质上缓存了层三路由,节省了软件处理开销。缓存技术到今天仍在使用,实现方案取决于具体问题。
以太网交换机和路由器功能不断丰富,例如安全检查、服务质量、监控等。体积也不断增大,架构从单片式发展到逐步分布式。这需要利用新技术克服性能瓶颈,例如采用交叉总线或分布式式结构。技术的不断进步让产品性能提升了几个数量级。
拥塞控制是防止发送者过量发送数据包而导致网络拥塞的一种机制。它必须满足两个条件:1) 防止网络拥塞发生;2) 将拥塞控制影响均匀分配给各流。
拥塞控制应该进行在哪里是一个问题。按照端到端原则,智能应置于网络边缘,网络内部只负责转发数据包。TCP就是一种边缘拥塞控制协议。
TCP使用的拥塞控制算法是加法增加型减法减小型(Additive Increase Multiplicative Decrease, AIMD)。这个算法能很好地控制拥塞,并公平地分配带宽。它被认为是网络技术最重要的发明之一。
本课程将学习拥塞控制原理、TCP的AIMD算法实现细节,以及不同场景下其工作机制。还将学习TCP未来可能的发展方向。帮助学生厘清TCP拥塞控制在互联网中发挥的重要作用。
拥塞可以发生在多种时间尺度上:
毫秒级:两个数据包同时到达路由器输出端口时可能会发生碰撞。
轮回时间级:一个TCP流长时间发送时,其发送速率的变化可能导致某路由器缓冲区积压。
小时级:高峰期网络访问用户过多时可能导致某链路拥塞。
拥塞的主要原因是:
源节点发送速率超过输出链路带宽时,路由器缓冲区将堆积数据包;
多个源节点发送给同一目的地时,如果其总速率超过输出链路带宽,也将发生拥塞;
流量的临时波动也可能引起短期拥塞。
拥塞如果长期存在,将导致:
数据包丢失率增加;
重复传输增加网络负载;
应用层传输延迟增加。
所以,需要拥塞控制来避免网络性能下降。
网络需要有公平且高效的策略来分配每条链路有限的带宽。根据每个节点所要求的带宽来给予相应的带宽分配,避免任何节点单方面占用过多链路资源。
拥塞控制的目的是让网络在拥塞状态下也能正常运行。它通过控制发送速率来限制链路利用率,避免数据包损失率过高。实现公平且高效的网络资源分配是拥塞控制的最终目标。
网络拥堵控制可以在网络中完成,也可以在终端主机中完成。
网络级别拥堵控制需要网络支持,比如路由器能够向源主机发送拥堵信号。送回拥堵信号可以直接控制源主机的行为,易于实现,分布式。不过需要改变网络结构。
终端级拥堵控制由主机自行观察网络情况并调整发送速率实现。具有良好的可扩展性,无需更改网络结构。但响应速度可能较慢。
TCP就是一种终端级拥堵控制算法。它通过包丢失或接收端应答判断网络拥堵情况,进而调整滑动窗口大小控制可输出包数量,实现拥堵控制。
当输出队列长度超过阈值或链路利用率下降时,路由器可以将拥堵信号标记在经过的数据包头中,然后由接收端将信号传回发送端,实现网络级拥堵控制。
终端级拥堵控制相比,更易实现、更易扩展,无需改变网络结构,因此性能更好。但响应时间可能较长。两种控制方式均可实现最大最小公平分配。
加减增减(AIMD)机制可以通过调整TCP滑动窗口大小来调节网络中尚未确认的数据包数量,从而控制网络拥塞程度。
AIMD工作原理:
每收到一个包后,滑动窗口增加1/W。当收到整个窗口的数据包后,窗口大小增加1。
每次丢包后,窗口大小减半。
在网络中的数据包可以分为三类位置:
源-目的间的瓶颈链路上。
路由器缓冲区中。
反方向ACK包。
当增加滑动窗口大小时,新增的数据包只能放入路由器缓冲区。缓冲区压力随窗体大小增加而增加。
单流AIMD特点:
窗体和RTT一致波动,但发送速率保持常数,保持链路利用率100%。
AIMD调整窗体来探测“网络容量囊”的大小,而不是直接调整发送速率。
路由器缓冲区大小应大于窗体波动幅度,以保证系统稳定运行。
爱丽斯通过10Mbps链路播放视频,源服务器在旧金山,最小RTT为5ms。
最小AIMD窗口为6250字节,最大为12500字节。
路由器缓冲区大小为50000比特。
窗口减半后重新达到最大值需要187.5ms。
如果源服务器在澳大利亚,最小RTT为250ms,缓冲区应为298KB。
在澳大利亚情况下,窗口减半后重新达到最大值需要468.75s,近8分钟。
单流AIMD下,窗口从减半 recovering 需要很长时间,这在实际应用中是个问题,需要寻找更快的TCP拥塞控制算法。
在之前的视频中,我们了解了单流网络中的AIMD算法。在现实网络中,路由器上的缓冲区会同时包含来自不同流的许多数据包。
一个路由器通常可以容纳成百上千的数据包。每一条流通常只占据缓冲区很小的一部分。如果有1万条流共享1万个数据包的缓冲区,那么每条流平均只占据一个数据包的位置。
当一个流的数据包到达时,缓冲区很可能已经满了。如果数据包不幸到达的时机正好是缓冲区满的时机,这个流的这个数据包就会被丢弃。随着流数量的增加,缓冲区占用率会越来越平稳。每个流都可能随机遭遇丢包。
尽管如此,每个流仍然独立地按照AIMD算法运行。当它的数据包被丢弃时,流会减半其窗口大小;其他流不受影响,继续增加其窗口大小,直到自己的数据包被丢弃。
由于流数量巨大,RTT可以看作基本不变。通过put等于窗口大小除以RTT,可以得出每个流的吞吐量反比于RTT。流间公平性不够好是一个AIMD的缺点。
通过几何推导,可以得出AIMD算法下每个流的吞吐量与丢包概率成反比根号关系。零丢包率下,窗口大小将无限增长,通过丢包就是AIMD控制流量的核心机制。
流量控制机制只控制端点的数据接收能力,但网络实际传输能力可能低于此。如果源节点根据流量控制窗口尽可能快速发送数据,将可能导致链路拥塞,大量数据丢包需要重传。
早期TCP根据流量控制窗口一次性发送所有数据段。如果窗口大小超过网络实际承载能力,将导致链路饱和后数据重复丢包。TCP发送效率很低,数据增量极小。
使用拥塞窗口来估计网络实际传输能力。Sender窗口采用这两个窗口中的较小值。
将TCP发送状态分为慢启动和拥塞避免两个阶段。
慢启动阶段每收到ACK就增加一个MSS的数据发送数量。第一RTT只发送一个段,第二RTT发送2个段等,这样逐渐探测网络容量。
拥塞避免阶段操作近于网络容量,不再快速增长也不再快速减少 sending rate。
这些改进大幅提高了TCP传输效率。
TCP通过三种机制来控制拥塞:
拥塞窗口:用于限制同时在网络中的数据包数量。
慢启动和拥塞避免:控制拥塞窗口的增长。
准确估计RTT对TCP很重要,因为它用于:
若RTT估计值过短,可能导致多余重传;若过长,可能等待时间过长无法及时重传。
TCP Tahoe对RTT估计算法做出了以下改进:
使用加权移动平均算法不断修正RTT估计值。
同时估算RTT的方差。如方差大,则增加超时阈值,以免等待过长;方差小,则降低阈值,避免等待过长。
根据确认报文的时间间隔来发送新数据,实现”自时钟”功能。避免突发发送大量报文造成拥塞。
TCP Tahoe通过优化RTT估计算法和引入”自时钟”机制,使得TCP更好地感知网络状况,据此调整发送速率,更好地控制和缓解网络拥塞。
TCP Tahoe解决了网络拥堵控制问题,使得TCP能在Internet上正常运行。但是,其性能还不如理想,因为对网络资源利用有一定保守。
TCP Reno在TCP Tahoe的基础上进行了改进。对三次重复ACK,TCP Reno采用快速恢复机制,将拥塞窗口设置为原来的一半,而不是设置为1。这可以避免进入慢启动状态,提高性能。
TCP Reno还增加了更快传输机制。在收到三次重复ACK时,直接重新传输丢失片段,而不需要等待超时。这可以缩短响应时间,进一步提高吞吐量。
TCP New Reno相比TCP Reno在快速恢复状态进一步改进:
每收到一个重复ACK,就将拥塞窗口增加一个MTU(最大传输单元)大小。
当最后一个未确认 segment被ACK时,将拥塞窗口设置回快速恢复进入时的值。
这使得TCP New Reno在快速恢复期间,能够继续发送新的段包,从而缩短空闲时间,进一步提高网络利用率。
TCP采用拥塞窗口控制发送数据速度。当网络拥堵时,通过减小拥塞窗口来控制发送速度。处于慢启动阶段时,窗口以指数函数增长;进入拥护避免阶段后,窗口以线性增长。遇到丢包时,采取不同措施减小窗口大小,以避免重复发送造成网络拥堵。
网络拥堵控制存在两个冲突要求:
服务提供商要最大化链路利用率,不想有闲置带宽。
用户希望公平地获取网络带宽资源。
拥堵控制算法应该使链路利用率保持高,同时所有用户在相同条件下能平分网络带宽。还要避免网络拥堵崩溃。
拥塞窗口大小最佳值为带宽倍时延积。比如带宽10M字节/s,时延100ms,则拥塞窗口应为1M字节。
AIMD(加法增加乘法减少)可以满足上述要求:
加法增加可以使链路利用率保持高。
乘法减少可以使各用户获得平等带宽,使网络状态接近公平占有线。
通过图示可以看出,AIMD可以使数据流Repeatedly probe for more bandwidth, eventually settling on an equal share of the link capacity for all flows while keeping the link highly utilized.
结论是,AIMD是一种高效的拥堵控制算法,能使网络资源在各流之间得到公平分配,同时保持高链路利用率。
RFC是Internet工程任务组(IETF)的标准化文件,描述和指定了Internet的协议和标准。
RFC按类型分为:
RFC起初是个人草案,输入IETF工作组讨论。经版本迭代后,可能成为工作组文件。通过社区评审与IESG审核后,方可成为正式RFC。
RFC2119中专门定义了在RFC中使用的关键词:必须(MUST)、应该(SHOULD)、可以(MAY)。它们指示RFC的强制性程度。
RFC内容包括提要、版权说明、定义、安全考虑、IANA考虑等部分。例如TCP拥塞控制RFC阐述了拥塞窗口初值、慢启动阈值等参数的设置规则。
流控制限制源主机不发送超过目的主机接收能力的数据。拥塞控制限制源主机不向网络发送过多数据,填满中继器队列。
TCP使用拥塞窗口来限制未确认报文数量。发送端根据拥塞控制算法调整拥塞窗口大小,防止网络拥塞。
TCP使用的加加减减算法(AIMD):当未发生丢包时,每RTT增加一个包大小;发生丢包时,将拥塞窗口减半。
网络应该是公平的。最大公平性定义:网络流量分配如果无法增加某流速率而不降低其他流速率,即为最大公平。
在丢包率p的情况下,TCP流的理论吞吐量为:平方根(3/2)×(1/RTT)×平方根(p)
Tahoe、Reno、New Reno三个TCP版本,历次优化加快收敛速度、减少丢包带来的影响。
本单元将介绍三大网络应用:域名系统(DNS)、万维网(HTTP)和比特托伦特(BitTorrent)。同时讨论网关地址转换(NAT)对网络应用的影响。
域名系统使用UDP作为传输层协议。它实现了名称与信息查询功能,使客户端能通过域名获取资源信息。
超文本传输协议HTTP基于TCP,实现客户端与服务器交互请求与响应模式。最近HTTP标准不断发展,提高了网络传输性能。
比特托伦特是P2P文件分享应用,使用TCP作为传输层。它利用“种子-下载”机制,实现分布式文件传输效率。
NAT设备可以实现一个网络下多个主机使用一个公网IP连接外网。但也限制了主动连接行为,给网络应用带来一定挑战。许多解决方案应对NAT局限。
网络地址转换器(NAT)是一种设备,位于内部网络和互联网之间。它有两个接口:内部接口和外部接口。
NAT向内部网络中的主机分配私有IP地址(如10.0.0.x),但它自己的外部接口使用公有IP地址(如111.222.333.444)与互联网通信。
当内部主机向外发起连接请求时,NAT将源IP和端口进行映射,例如将源IP 10.0.0.101和端口5000映射为外部IP 111.222.333.444和端口7000。这样就可以将多个内部主机用一个公网IP访问互联网。
返回数据包经NAT识别外部IP和端口后,会将其转换回内部主机的私有IP和端口进行转发。此过程建立和维护每个会话的转换表,支持动态端口映射。
NAT同时实现了一定程度的网络地址和端口资源的互相隔离与共享,为内部网络提供了隐私保护。现今大多数家用路由器和网络也都使用NAT技术。
NAT并不事先为每个主机预留地址映射,只会在内部主机向外发起第一个会话请求时,为其建立一次性的动态端口映射。
比如主机A请求与服务器S的SSH连接,NAT此时根据TCP三次握手报文,为A的源IP地址10.0.0.101和源端口5000,分配外部IP 111.222.333.444和目标端口7000进行一次映射。
随后数据包经NAT地址转换之后,经互联网正常建立会话。服务器回应也会由NAT检索映射,还原后转发给内部主机A。这种映射模式可以有效利用有限的公网IP资源。
NAT通过地址及端口转换,实现了内外网络地址与资源的隔离共享。它为内部主机提供了一定程度的匿名性,也实现了有效利用有限的公网IP地址。NAT技术目前广泛应用于家用路由器和企业网络、云计算基础设施等场景。
举例介绍了对称NAT如何影响分布式多人在线游戏:当游戏角色从一区换到另一区时,由于端口映射不同导致连接断开。说明NAT添加的行为很难考虑到。
后文还提到了RFC对NAT行为的标准规范,优化了网络应用开发。
NAT可以为主机提供IP地址共享服务,但是也带来一些影响:
接收连接问题。NAT后主机无法直接接收来自外部的TCP连接,因为NAT没有对应的映射表条目。
连接重定向。客户端可以通过运行中的中介服务器进行连接重定向,此时客户端主动建立与中介服务器和对方主机的连接。
中继通信。当两客户端都在NAT后时,它们可以通过中继主机进行通信,中继主机负责转发两客户端之间的数据包。
NAT分派。客户端可以通过与服务器通信得知对方的外部IP和端口,然后同时向对方发送数据包来让NAT建立映射。这适用于锁定端口NAT和限制锁定NAT。
对新 transport 协议的影响。NAT工作依赖于了解传输层报文格式,无法支持新的传输协议。
对应用的限制。由于无法直接接收外部连接,部分服务如语音会议就很难下部署。开发者需要采取额外措施解决NAT问题。
NAT分派会失败,因为客户端从服务器获取的外部IP和端口信息仅在当前会话期间有效,无法用于建立新连接。这就是对称NAT在Internet上的不推荐原因之一。
NAT会将内部IP地址和端口对映射到外部IP地址和端口对上。当有数据包从内部传到外部时,NAT就根据这个映射将源IP和端口转换为外部值。否则数据包无法正常传输。
对于UDP,NAT会在看到从内部出发的第一个数据包时创建映射。对于TCP,NAT可以在看到SYN数据包或任何TCP数据包时创建映射,以支持更多情况下的通信。
UDP映射由于没有连接控制会在一段时间后自动删除,以回收端口资源。TCP映射会在看到FIN-ACK报文时更快删除,但也需考虑一些边缘情况。
NAT需遵循将内外端口都映射到相应范围(0-1023和1024-65535)的规则,避免对原有应用产生影响。
为满足各种应用需求,RFC给出了几种NAT类型的定义规范,例如防火墙必须具备的完全沙锅NAT属性。同时也给出了NAT的标准操作规范,包含了大量对原有协议的兼容考量。
NAT需支持两个内部主机通过NAT对对方同时发起连接的情况,这对点对点通信尤为重要。
HTTP是互联网上最重要的应用层协议之一,它定义了如何在万维网(World Wide Web)上请求和传输超文本文档。
超文本(Hypertext)是一种允许在文档中包含格式和内容信息的文档格式。
HTTP采用请求/响应模型,客户端向服务器端发送请求,服务器端返回响应:
GET请求不包含消息主体,POST请求可以包含表单数据等内容。
请求和响应都可以包含多个头信息字段,例如:
超文本文档可以通过标签内嵌其他文件,如图片、样式表等。浏览器在解析HTML时会自动发起这些子资源的请求。
浏览器开发工具可以查看HTTP请求和响应详细信息,还可用telnet连接指定端口进行简单测试。
以上就是HTTP的基本工作原理。
图中蓝线代表客户端到服务器的数据包,红线代表服务器到客户端的数据包。
SYN和SYN-ACK握手需要100毫秒。
第一个HTTP请求需要60毫秒到达服务器。
160毫秒时,服务器开始发送响应,包含2个数据包。
第一个响应数据包传输时,服务器收到第二个HTTP请求。
服务器将第二个请求的2个响应数据包加入队列。
响应数据包总共需要90毫秒发送完毕。
总计需要480毫秒:
所以预测两个图片下载总计需要150毫秒,总时间为250毫秒。
本题考察HTTP页面加载时延估算能力:
根据以上参数,需要计算各案例HTTP页面完全加载需要的时间。
多请求传输会由于延迟排队带来一定额外时延,但相对单个请求,延迟增量很小。重叠传输能有效缩短总下载时间。
Connection请求头和响应头Keep-alive机制消除连接重建开销,提升HTTP并发性能。HTTP1.1/2.0规范优化常见请求模式,带来显著 shortened 加载时间。
BitTorrent会将文件拆分成多个固定大小的块(Piece),默认每个块256KB或更大。
客户端通过下载Torrent文件加入连接,Torrent文件包含文件信息及其他节点信息。节点离开后,其持有的块会由其他节点补全。
早期通过 tracker 节点获取其他客户端列表,现已采用DHT分布式哈希表进行节点查找。
客户端从多个节点同时下载块的不同部分(SubPiece),降低延迟。每个块带有SHA-1哈希值用于检查完整性。
客户端定期和其他节点交换块信息,优先下载较为稀有的块。上传给其他节点时采用“你给我我给你”的Tit-for-tat算法,每30s随机解禁1个节点。
rarest-first策略和多节点并行下载使下载效率最大化。BitTyrant提出了自私策略可提升性能,但全面采用后效果不佳。
域名系统(Domain Name System,DNS)是互联网的核心服务之一,它使人类可读的域名可以对应到互联网协议地址。
早期通过host.text文件存储主机与IP地址的对应关系,随着规模增大不可行。DNS使用域名层次结构和分布式管理解决问题。
DNS查询和响应消息指定在RFC1035中。
消息由下列部分组成:
头:描述整个消息,包括消息ID、操作码等。长度为12字节。
询问部分:包含查询名称。
答复部分:包含查询名称对应的资源记录。
授权部分:包含域名服务器授权资源记录。
附加部分:包含额外的资源记录。
每个部分都由一个或多个资源记录(RR)组成。
每个RR包含:
名称:域名,可以采用压缩编码。
类型:A记录代表IPv4地址,AAAA记录代表IPv6地址,CNAME记录代表别名,NS记录代表名称服务器等。
类:记录应用的协议集,通常为1代表Internet。
生存周期(TTL):记录的有效时间。
数据长度和数据:具体的应用数据,如IPv4地址值。
域名采用分层结构并使用ASCII编码每个层级。每个层级由长度字段和文本值组成。
长度大于192时,后14位表示偏移字节,指向重复域名的位置,实现了重复域名的压缩存储。
使用dig命令可以查询域名,查看DNS响应包中的各个部分和RR结构细节。
DNS系统中主要记录种类包括:
域名解析的基本查询过程为:
要正确配置名称服务器,需考虑以下几点:
在实际查询中,会出现以下细节:
DHCP(动态主机配置协议)可以自动为计算机分配IP地址、子网掩码和网关地址等网络配置信息。
计算机连接网络时,会广播发送DHCP发现消息。监听到该消息的DHCP服务器会回应报价,提供可供选择的IP地址等配置。计算机会选择一个报价,向DHCP服务器发送请求消息。DHCP服务器确认后,即可将配置信息分配给计算机,此时计算机便可以正常使用IP通信了。
DHCP租约配置可以设定有效期限。到期前计算机会向DHCP服务器发送重新请求,刷新租约延长有效期。释放租约可以主动告知服务器可释放配置。
计算机发送DHCP发现广播请求,携带标识码
听到请求的DHCP服务器回报可选配置报价,携带相同标识码
计算机选择一报价,向对应的DHCP服务器发送具体请求
DHCP服务器确认分配该配置,带有租约期限
到期前计算机重新请求刷新租约,得以继续使用该配置
可选择性发送释放消息,通知服务器不再使用当前配置
由于还没有IP配置信息,DHCP消息使用UDP广播传输:
这样就能在没有IP地址的情况下实现DHCP协议配置信息的自动分配。
本课介绍了三种主要的网络应用:
动态主机配置协议(DHCP)可以为计算机自动分配IP地址、子网掩码、网关地址等网络设置。
域名系统(DNS)可以将域名映射为IP地址,使得网址更加友好。
超文本传输协议(HTTP)是浏览器与Web服务器之间通信的标准协议。
网络地址转换器(NAT)允许多个内部设备共享一个公网IP地址。它通过修改报文头来重写地址信息。
NAT根据报文的传输端口来区分不同设备的数据流,实现对内外包裹的转换。但默认只允许内部主机发起外部连接,外部主机无法直接连接内部主机。
DHCP和DNS使用UDP协议。HTTP使用TCP协议,1.1版本支持长连接技术。
BitTorrent采用P2P架构,由TCP连接组成的超大规模“群”来协同下载文件。它使用稀缺度优先和“我们的主义”策略来实现高效分发。
NAT给应用带来一定困难,但也有工作方法,例如孔明打洞法和同时打开来初始化连接。总体来说,简单的NAT映射更有利于模拟端到端连接。
本课将详细介绍路由这个网络基础概念。路由决定如何将数据包从源发送到目的地。
源路由:数据包自行带有完整路由表前往目的地,效率低且存在安全隐患。
转发表路由:每个路由设备保留一张转发表,根据目的地址选择下一跳。这是Internet采用的方案。
转发表由分布式算法动态生成。路由设备将生成一张生成目的地为根的横跨整个网络的生成树,确保任何源都可以通过这颗树到达目的地。
主流算法有贝尔曼-福特算法(distance vector)和迪杰斯特拉算法(link state)。它们通过信息交换来构建生成树。
Internet由许多自治系统构成,每个自治系统内部运行独立的网段和路由管理。内部使用RIP或OSPF进行路由,不同自治系统间使用BGP协议。
Internet采用层次结构,每个级别的路由设备负责向下一级传输路由信息。这种分层设计简化了路由管理与路径选择。
本视频将介绍距离矢量路由协议,特别是使用Bellman-Ford算法的距离矢量协议。
距离矢量路由协议是一种每个路由器都会记录自己到其他所有路由器的距离向量的路由协议。路由器定期将自己的距离向量发送给邻居,然后通过迭代计算最终可以找到最小花费的跨越树。
Bellman-Ford算法是距离矢量路由协议最常用的算法。它假设每个路由器都知道到临近路由器的链路成本。每个路由器会维护一个向量,记录到其他每个路由器的当前最低成本。
算法开始时,所有成本都设为无限大。每隔一定时间,每个路由器会将自己的成本向量发送给邻居。如果在任何时候学习到一条成本更低的路径,就更新自己的成本向量。如此反复,算法最终会收敛到最小成本跨越树。
视频给出了一个简单网络拓扑图,并以此作为例子详细说明Bellman-Ford算法的每一步计算过程。
算法开始时,每个路由器对自己到其他所有路由器的成本向量都设为无限大。随后,每个轮次信息将沿着网络扩散,路由器通过收到的新信息不断更新成本向量,算法将最终收敛。
视频还提到,算法的最大运行时间就是网络中最长无环路的跳数。同时,只要链路成本不下降,算法一定会收敛。如果链路成本发生变化,算法也能很好适应并重新收敛。
视频提到,当链路发生故障导致某些目的地不可达时,Bellman-Ford算法会出现问题,“坏消息传播得慢”。随后给出一个简单示例,证明这一问题。
链路状态算法是一种路由选择算法。在这种算法中,每个路由器都会定期向所有其他路由器广播自己连接的边和边的状态(是否正常工作等)。所以每台路由器都会知道整个网络拓扑结构。
迪杰斯特拉算法是链路状态算法的一种。它能够找到源点到其余每个路由器的最短路径生成最小生成树。
每个路由器先向其他路由器广播自己连接的边的状态,以获知整个网络拓扑结构。
然后每个路由器独立运行迪杰斯特拉算法,生成从自己出发到其它每个路由器的最短路径最小生成树。
迪杰斯特拉算法将源点加入生成树集合,其他节点加入候选集合。
选择候选集合中到源点路径成本最小的节点加入生成树集合,同时从候选集合中删除。
重复第4步,直到候选集合为空,算法结束。这时生成树集合即为源点到其他每个点的最短路径生成树。
只要链路状态(是否正常工作)改变,路由器会重新广播状态。之后每个路由器都会重新运行迪杰斯特拉算法计算新的最短路径生成树。
迪杰斯特拉算法是OSPF路由协议的基础,OSPF广泛用于互联网路由。
可以将路由器看成竖着的球,用连接它们的线来代表边。线的长度代表成本。通过拉动线实现迪杰斯特拉算法,最终形成一颗全紧的最小生成树,其中线代表最短路径。
互联网由数以百万计的路由器组成,直接连接着10多亿终端用户。简单直接使用链路状态或距离向量算法进行路由计算难以满足这个巨大网络的规模需求。因此需要将网络划分为较小的子集进行管理,这就是层次化路由的理念。
网络被划分为自治系统(Autonomous System,AS),每个AS内部都有自己的边界门路由器。AS内部使用内部路由协议自行决定内部路由,外部使用BGP进行路由信息交换。
单出口AS(Single Exit AS)只有一个对外连接点。多出口AS(Multiple Exit AS)有多个对外连接点。
RIP:距离向量算法,每30秒更新一次,180秒失效判断。无认证,安全性较差。原因是BSD里实现简单。
OSPF:链路状态算法。实时更新链路信息,定期定时更新路由表,收敛速度快。运行Dijkstra算法计算最短路径。支持认证,安全性较高。分区实现(Area)。广泛使用。
单出口AS直接默认路由,所有未知目的地报文转发到默认路由器。
多出口AS需要根据目标网络选择出口,使用BGP进行路由信息交换。
BGP为不同AS之间安全可信赖的路由信息交换提供了标准机制,是互联网施行分层管理的基石。
BGP是Border Gateway Protocol的缩写,是连接自治系统之间的外部网关协议。
BGP是一种路径向量协议,BGP路由器只会向其他BGP路由器传播完整的路径信息。路径信息包含该目的地可以通过的多个自治系统序列。
网络由多个自治系统构成,每个自治系统由一组路由器和链路组成。自治系统之间通过BGP进行连接。
自治系统之间存在客户-供应商关系。供应商向客户提供互联服务,客户向供应商支付费用。这样就形成了自治系统层级结构。
BGP定义了四种主要消息类型:
UPDATE消息是最重要的,它传播新路由和撤销旧路由。
路径属性包含在UPDATE消息中,用于选择优先路由。主要路径属性包括:
收到多个相同目的地的路由后,BGP根据以下顺序选择最优路由:
例如,对于目的地AS1内网段的路由,Frank通过AS2和AS4获得了两条路径。根据本地偏好设置,AS2路径的本地偏好为100,AS4为80。则Frank会选择通过AS2的路径,因为它的本地偏好设置更高。
以上就是BGP的基本概念、消息类型、路径属性和路由选择算法。它充分体现了不同AS之间的关系、策略和BGP为此提供的机制。
多播路由指向多个目的地复制数据包的能力。为了有效地传输数据给多个主机,需要考虑网络是否可以或应该帮助我们来复制数据包,而不是一个个地发送给每个目标。
简单地重复传播数据包是一种实现多播的方式。每一个路由器在收到数据包后,都会把它发送到除了入口端口外的其他所有端口,这样数据包就会循环传播下去。但这种方法会造成数据包永远循环,无法到达目的地。
利用了单播路由时已建立的最短路径生成树。广播数据包带有源地址,路由器判断接收端口是否在向源地址的最短路径上,如果是就接受并发送到其他端口,否则丢弃该数据包。这可以实现无环传输,但所有路由器 inicial 都会接收数据包。
没有关联主机的路由器会向源发送”修剪”消息,从而从广播树中去除自己。最终形成的树只覆盖有兴趣的数据包的终端主机,更高效。但初始化还是涉及所有路由器。
理想情况下,每个源应建立自己的最短路径生成树,这样数据包就能沿着到每个目的地的最短成本路径传输。但如果群组主机较少,也可以设立汇合点,每个源先把数据包发送到汇合点,汇合点再建立向全体成员的单个最短路径树传输数据包。
IPv4设立了多播地址类,地址范围为224.0.0.0-239.255.255.255。多播地址指代一个群组,群内所有接收者都使用该地址。路由器根据地址和源地址元组进行路由。
本课继续介绍路由概念。以太网交换机也需要决定如何转发数据包到正确的目的地,这里介绍了跨树协议来防止循环。
跨树协议会选择一个跨树根节点,并根据根节点到其他交换机的距离来建立一个单独的跨树拓扑结构。这样一来就可以避免多个循环产生。
交换机转发数据包的过程是:检查数据包头部的以太网目的地地址,如果在转发表中找到就转发,否则广播发送。转发表条目是通过学习源地址来确定的。
但是这可能产生循环问题。例如,如果A想向B发送数据包,中间有多个交换机,第一个交换机不知道路径就广播发送,那么数据包可能一直在环路中循环。
为了解决这个问题,跨树协议会构建整个网络的单个跨树,而不是为每个目的地建立单独的跨树。
具体实现为:
所有交换机广播特殊的BPDU包,包含发送者ID、当前认为的跨树根节点ID、发送者到根的距离估计值
起初,每个交换机都认为自己是跨树根
接收到更好的BPDU后(根ID小或距离短),会采纳新的跨树根和距离值,同时增加1重新广播
通过多轮交换,会定出一个根节点,从根向外确定每一层的跨树拓扑结构
其他未包含在跨树中的链路将被禁用,避免产生环路
整个网络就形成了一个唯一的跨树,且无环,实现了安全的路径转发。
IPv6地址采用128比特,可以提供比IPv4地址更大的可用地址空间。
大卫谈起他如何接触网络领域。大学时期,他在明尼苏达大学从事并行计算与网络方面的研究工作。他们构建了第一个基于ATM技术的实时网络,连接各大超级计算机并进行计算能力的竞争试验。后来,由于需要连接不同超级计算机间的通讯协议兼容性问题,他们研发了第一个可在ATM网络上运行的超级计算机通信协议转换器。
大卫后来加入一家 focuses on high-performance networking 的初创公司。但发现超级计算机的数量少,成本也高,难以实现规模化。这时互联网刚开始商用,于是他们将技术应用于路由器设计,成功开发出首个分布式转发式路由器。这家公司后被Ascend Communications收购。大卫又转投其他初创公司,最终于1999年加盟思科。
在思科期间,大卫参与设计并负责多款产品,如IOS XR操作系统、CRS系列核心路由器、ASR系列路由接入器等。此外他还参与了许多网络协议标准的制定,如BGP、OSPF、MPLS等,这些协议构成了互联网今日的基础架构。
大卫表示,他早期研究并行计算与网络的工作,为他积累了深厚的操作系统及模块化设计经验。这帮助他后来在思科成功设计各种产品。他目前仍在思科从事新一代网络技术的研发,如SDN、NFV等领域。
BGP作为互联网的纽带,随着互联网的发展而逐步成长。早期阿潘娜网络(ARPANET)时,网络结构简单,不需要复杂的路由协议。NSFNet建立后,网络间连接方式更加灵活,出现环路,BGP就被设计用于支持此类拓扑结构的路由。随着互联网规模增长,BGP不断改进来应对地址空间不足、路由表规模大、域间业务关系变化等问题。
BGP采用基于路径的路由信息传播机制。每个节点向链路存取表中添加自身域,然后选择其中一条路径告知其它节点。其他节点再重复此过程传播路由。尽管原理简单,但配置的复杂度很高,经常因为操作错误引发故障。
BGP可以很好地协调不同服务提供商之间的冲突目标,确保互联网连接。它具有很好的可扩展性和适应能力。但同时,BGP难以扩展,配置过程复杂容易出错,一个小失误可能导致全球影响。由于依赖路径向量,可能无法获得最佳路由。
通过BGP对等会话来非法宣告路由是真实威胁。但是,恶意行为者通常不希望互联网中断,更偏好具体目标攻击。实际操作中,利用BGP攻击应还不如其他攻击方式严重。然而,BGP故障可能造成更广泛影响。
总体上,BGP解决了很难的任务,在不同机构间协调路径选择。它具有很强的适应能力。但是,配置复杂易出错,路径选择限制也才能满足需求。安全问题存在,但相对其他网络攻击,利用BGP直接攻击的风险较低。继续优化和改进BGP仍将是重要任务。
本单元将介绍链路层的基本工作原理,包括通信的基本原理如信号和噪声、客户端如何通过错误纠正编码恢复错误比特等。
主要介绍两种类型的物理链路:
有线链路,以以太网为主。介绍早期以太网使用的CSMA/CD共享介质访问控制机制。现在主要使用交换机。
无线链路。与有线不同,无线链路的信道质量会随时间变化,存在不同类型的干扰。由于广播性,会带来隐藏终端问题。
不同链路支持的数据包最大传输单元(MTU)大小不一样,如以太网为1500字节。需要IP分片功能在链路间调整包大小。
发送方和接收方使用的时钟存在误差,需要编码信息传达时钟参数,让接收方正确解码数据。
任何通道都有理论上的传输率极限,称为香农极限。该极限取决于带宽和信噪比。
带宽(B)指通道使用的频率范围。信噪比(SNR)指信号强度与噪声强度的比值。通道容量(C)描述每秒可以传输的比特数,计算公式为:
\[C=B\\log_2(1+SNR)\]数字信号通过调制把比特映射到模拟信号上进行传输。
使用不同振幅来表示0和1。适用于线缆通道。
使用不同频率来表示0和1。
使用信号相位的差别来表示0和1。适用于无线通道。常见的有二相位调制(BPSK)。
实际通道不会使用单一频率,而是一段频带。例如802.11b协议每个20MHz宽的信道可以传输数据。
调制信号通常为模拟信号,其主要属性包括振幅、波长、频率和相位。
人: 好的,你总结得很好。是否能增加一点内容,详细介绍一下调制信号的几种主流方式,比如 recipients 中的 BPSK,QAM 等,加深读者的理解。
在这个视频中,讲述了物理层中数据传输的错误来源以及错误编码的方法。
信道容量由带宽和信道信噪比决定,信噪比越高,传输速率可以越快。然而,真正可用的传输速率会因噪声的存在而受限。
噪声会导致接收信号与理论信号有差异。若采用更为稠密的调制集,噪声可能会使接收点错认为另一个点,从而产生误码。误码率随信噪比的增高而降低。
为减少误码,可在物理层加入一定冗余。比如添加一定位数的校验码。这样即便少量位错误,也能通过校验码进行错误检测和纠正,从而恢复原始数据。
802.15.4标准采用四比特符号,每个符号映射16个调制符号,实现1/8的编码增益。802.11n标准支持不同调制方式和编码增益率,实现各种传输速率。
编码能在一定程度上提高传输层吞吐量,弥补信道数据传输的不确定性,使系统整体性能优于直接将数据分组映射到信道的效率。是物理层常用的一种错误控制方法。
当我们将数据通过链路发送时,比如以以太网链路,我们通常假定有一个数据速率,如10Mbps或1Gbps。当我们发送10Mbps时,我们假设每个比特持续100纳秒,或者每秒有1000万个比特。当我们发送1Gbps时,我们假设每个比特持续1纳秒。因此,在发送端和接收端必须有时钟概念。
发送端使用时钟将比特发送出去。理想情况下,接收端也可以使用这个时钟恢复比特。但是,发送端和接收端的时钟是由不同的振荡器生成的,所以它们的频率并不完全相同。这可能导致接收端无法准确解码比特。
时钟的差异通常表示为每百万个脉冲(PPM)。如果两钟的偏差在100ppm范围内,那么长时间内它们的差异可能达到一个完整的比特宽度。但实际上,它们保持一个相对稳定的频率偏差。
接收端需要从信号本身推断发送端的时钟,以确定比特起始和结束位置,正确解码数据。如果接收端的时钟运行得比发送端快,它可能会重复采样比特;如果比发送端慢,它可能会跳过比特。
目前主流的同步通信中,发送端会将时钟信息同数据一起编码传输, facilitating接收端从中恢复时钟。一种方法是插入同步字节序列来同步发送端和接收端时钟。
此外,采用异步通信方式也可以实现很短的通信,不需要明确时钟。只要发送端和接收端时钟频率大致相同,接收端就可以利用检测到的起始和停止位准确采样比特信息。
通过主动地添加一些冗余数据来提供错误修正能力。FEC在物理层和链路层都可应用。
所罗门码是一种广泛使用的FEC编码方式。它用原始数据作为一个多项式的系数,计算多项式上的点,将这些点作为编码后的数据传输。
例如255,223 coding:将223字节数据编码为255字节数据。可以纠正32个asures错误或16个一般错误。
王道的里德-所罗门编码在现实应用中会更复杂,但基本原理是:数据作为多项式的系数,计算点传输,接收端通过点重建多项式解码原始数据。它通过增加冗余数据增强了容错能力。
CSMACD(Carrier Sense Multiple Access with Collision Detection)是一种介质访问控制协议。具体包括:
载波监测(Carrier Sense):在发送数据前,需要监测介质是否繁忙。
多点访问(Multiple Access):多个发送方可以共享同一传输介质。
冲突检测(Collision Detection):如果两个或两个以上发送方同时访问介质会导致冲突,需要检测冲突并重新发送。
最早期以太网的物理形式为:
使用粗大的黄色电缆,非常不灵活。
电缆布置在天花板、墙壁或地下。
在电缆上的接头可以实现物理接触,将电缆连接到具体的网络接口。
接口再连接计算机。
以太网帧格式包括:同步前缀、帧起始标记、目标地址、源地址、类型字段、数据字段、帧校验序列等部分。
原始以太网速率为10Mbps。随后提高到100Mbps(快以太网)和1000Mbps(吉比特以太网)。遇到速率提高后,需要保证CSMACD条件成立,采取减小分组长度L的方法。
原始以太网采用总线拓扑。随后采用星状拓扑,将访问点集中在交换机中管理,并采用什么线拓扑部署 Category3/5 电话线,大幅提高可管理性。
随着速率和主机数量的增长,冲突越来越严重。来采用交换机进行网络划分,降低冲突域,提高网络利用率。同时,交换集中管理也更方便。这导致以太网交换技术的兴起。
无线网络与有线网络最大的区别在于,无线网络使用的传输介质是空间,而不是像有线网络那样使用标准化的导线。这会给无线网络带来以下几点影响:
无线信号强度随距离的增长而衰减速度大于等于r平方。即距离发射器两倍时,信号强度至少会减弱75%。
无线信号会发生反射。意味着可以通过多路径收到同一个信号,但到达时间不同。
无线环境中的障碍物(如人体、金属板等)会削弱信号强度。
无线信号受环境影响很大,如温度、湿度变化会影响传输。
无线频率资源非专属,需要与他人共享频段,容易受到干扰。
无线网络节点的位置和天线方向会影响信号收发效果,位置变动会导致连接不稳定。
由于上述多种因素的结合作用,无线网络连通性随时间而动态变化很大。
相比有线网络,无线网络的管理和优化工作很复杂。
美国将无线电频谱细分为多个带宽,分别用于不同应用。WiFi使用的频段主要在2.4GHz和5GHz范围内的部分频带。这些频段资源需要与多个领域共享,很容易受到其它设备的干扰。
所以得出结论:与有线网络不同,无线网络具有不可预测和动态变化的特点,增加了网络优化的难度。
网线网络通常使用的载波检测多址接入碰撞检测(CSMA/CD)Media Access Control(MAC)协议。
CSMA/CD协议的工作原理是:
检测网络中是否有其他节点在传输数据
如果空闲,则立即开始传输
如果忙,等待数据传输结束后再传输
在传输过程中,如果检测到信号不同于自己传输的数据,那么发生了碰撞
发生碰撞后,发送Jam信号通知所有节点,然后进行退避算法重新传输
但是,此种协议在无线网络中无法工作,因为:
发送节点无法感知接收节点是否出现碰撞情况
发送节点无法区分是自己的数据还是其他节点的数据
远程节点的数据干扰可能被本地大功率信号淹没
因此,无线网络需要使用新的MAC协议来检测和处理碰撞情况,以实现高通道利用率。
CSMA/CA是无线网络常用的媒体访问控制(MAC)协议。
它采用链路层确认机制解决无线网络中难以检测碰撞的问题。具体做法是:
发送节点发出数据包后,接收节点回复确认消息。
若接收节点未收到数据包,将不回复确认。发送节点此时需要重传。
发送节点在重传前采用指数退避算法,选择随机等待时间,以避免重复碰撞。
802.11标准定义了CSMA/CA机制,它主要包括:
选择初试等待时间T,监听信道是否为空。
若空闲,每次监听成功将T减1。当T减至0时进行发送。
接收到确认后,进入下次传输;否则进行指数退避,重新选择更长T值后重试。
此机制可以有效避免重传导致的重复碰撞,提高通道利用率。但是也会涉及隐藏终端和暴露终端等问题。
此外,CSMA/CA难以区分丢包原因是碰撞还是信道质量差。这会影响重传策略选择。但总体而言,在信道利用率低的情况下,CSMA/CA效果很好。
RTS/CTS机制是一种MAC协议,使用短程控制报文进行地址分配。
具体步骤:
发报节点A首先发送请求发送报文(RTS)给接收节点B。
B接收到RTS后,如果可以接收,则回复清除发送报文(CTS)给A。
邻近但无法直接通信的节点C,也可以接收到CTS,知悉B忙于接收,避免干扰。
收到CTS后的A,向B发送数据报文。B确认后,A完成发送。
RTS/CTS可以有效防止隐藏终端问题,但无法完全解决,且增加控制开销。它将冲突率下推到控制报文层面。
RTS/CTS对暴露终端问题无助,但可以减少总体冲突,有助区分丢包原因。
Wi-Fi主流使用CSMA,因为RTS/CTS的控制报文开销与数据率成正比,会降低 throughput 达25%。只在丢包严重时选择RTS/CTS。
802.11物理层帧格式包含同步字节、启动分帧字节(SFD)和物理层头等字段。
同步字节用来检测信号,SFD标识同步结束,定义物理层帧的边界。
物理层头包含48位参数,描述服务字段、长度字段、CRC校验等信息。整个物理层采用前向错误 correction 编码方式进行信号编码。
链接层帧包含控制字段、持续时间字段、地址字段、序列号字段、网络数据字段和CRC校验码等字段。
持续时间字段告诉其他节点该帧交互的时间长度,用于虚拟媒介接收。
地址字段支持源地址、目的地址以及通过接入点将有线网与无线网连接的桥接模式。
802.11n支持多种调制编码方案,接收机根据信号质量自动选择最优速率,通过修改MCS Index实现链接速率的调整。实际数据速率从6.5Mbps至150Mbps不等。
但是,由于控制字段必须兼容所有接收机,发送速度受限。随着数据速率增长,控制开销占比越来越高,实际吞吐量难以提升。
802.11标准设计了向下兼容的机制,但控制字段必需以最低速率传输。这会成为提高效率的限制因素。
例如当前600Mbps环境下,控制字段占用空中时间达92%,仅剩8%用于数据传输。实际吞吐率远低于理论值。
计算机网络中,高层协议的数据单元大小可能大于低层协议支持的数据单元大小。这时就需要把高层数据单元分割为多个低层可以支持的更小的片段,这过程称为分片。而收件端需要将分片重新组装成原始数据,这过程称为组装。
分片和组装常见于网络的不同层级:
传输层,如TCP将数据流分割为 segments 再发送,接收端将segments 重新组装成数据流。
网络层,如IP包在网络传输过程中可能会在中继节点被分割为多个IP分片,接收端将IP分片重新组装成原始IP包。
链接层,如无线连接802.15.4的帧大小很小,需要将IPv6数据包分割为多个片段传输后再组装。
IP分片是整个IP数据包在网络传输过程中由于MTU问题被中继节点分割为多个IP报文的一种机制。
IP报文包括标识符字段(Ident)和偏移量字段(Offset),这两个字段允许接收端识别出分片属于同一原始IP包,并正确将它们重新组装。
分片过程中,除最后一个片段外,其它所有片段的More Fragment位均设置为1。每一个分片的Offset字段表示其数据在原始包中的位置。
IP分片减轻了源节点调整报文大小的工作量,但也增加了包丢失的概率,因此OS和协议栈通常都会尽量避免IP分片。TCP传输可以通过探测路径MTU选择恰当的段尺寸来避免IP分片。
物理层定义了各种物理连接标准,如以太网、WiFi、DSL等。以太网支持10M、100M、1G等不同速率,WiFi会受环境影响而速率波动。
链路层需考虑如何在物理层上共享链路,比如以太网不需要介质访问控制,而WiFi需要CSMA/CA机制。链路层还要处理错误控制。
IP是最基础的网络层协议,可以运行在不同的物理层上。IP会进行分片以适应MTU不同的链路。分片由源节点进行,目的地重组原始报文。
TCP可提供可靠数据传输服务。它通过序列号和确认号来检测和纠正错误,实现流控和拥塞控制。
熵理论给出了信道最大传输率上限,即香农极限。掌握信息论知识对理解数字通信的本质很重要。
还学习了串行通信基本原理,比特误差correction,无线网络的隐蔽站问题等知识。这些理论知识给网络沉淀了深厚的基础。
路网项目是MIT的无线网研究项目。项目将天线安装在学生的房顶,建立来网路连接实现宽带互联网接入。
路网项目实现了以下目标:
构建无线网作为研究原型,为剑桥市内的MIT和哈佛大学学生提供宽带接入。
采用无网状拓扑连接各个节点,由少量校内资源节点为学生提供带宽。
实地部署带来许多与模拟不同的无线连接行为,比如链接质量波动大等问题。
需要研发能在实际运行环境下工作的路由协议。
连接了真实用户带来的真实流量问题。
路网项目实践发现以下无线网络特点:
链接质量并非全零全一,同一链接可能会丢30%或70%的数据包。
链接质量随时间波动,受调制方式、干扰影响会突变。
用户应用对网络影响很大,如一个BT下载可能影响其他100个用户。
层层问题综合,给研究带来很多收获。
Meraki之初产品采用了路网项目的无网状拓扑思想。但随着客户需求不同,产品主要发展方向是:
提供易于部署和管理的云端解决方案。
Meraki设备直接与云端管理系统通信,实现软件定义的边缘 compute 更新。
Meraki产品至今仍支持无网状拓扑模式。
云管理带来以下优点:
实现不同场地的一致配置和监控。
中心化的软件和政策升级管理。
提供更好的用户体验,如响应新设备需要。
对IT运维更友好,提高运营效率。
用户关注Meraki云管理下的网络设备数据安全问题。Meraki解决方案如下:
明确数据中心运营模式和数据隐私政策。
设备与云端联络采用IPSec隧道加密传输。
öffent对系统结构和安全机制透明公开。
保证用户数据安全且不外泄的同时,提供优质的云服务。
窃听协议:监听广播网络或强制网络公开信息进行窃听。
假冒其它节点:伪装为基础设施节点, forged响应欺骗客户端传输数据。
中间人攻击:窃取并转发数据流或阻断通信。
主机劫持:假冒被攻击主机完全终止通信。
阻断服务攻击:过载攻击对象瘫痪其通信能力。
保密性:隐私通信不被他人窃听。
完整性:通信内容不被篡改。
认证:确定对话实体的身份真实性。
摘要函数:检验数据完整性。
密文:实现隐私通信。
公开密钥证书:验证实体身份认证。
数字签名:检验通信内容和发送者真实性。
理解这些攻击手法和安全原则,可以设计出更安全的网络体系。
保密性:使用加密技术防止消息被窃听。
完整性:使用MAC算法检测消息是否被篡改。
认证:使用数字签名和证书验证对方身份。
可用性:防止拒绝服务攻击影响正常通信。
2.中间人攻击:截取并篡改 Alice 和Amazon之间的通信。
重新定向攻击:欺骗路由器将流量导向攻击者。
TCP会话劫持:破坏TCP连接实现数据盗取。
拒绝服务攻击:过载网络资源实施阻断。
使用HTTPS/SSL/TLS加密通信防止窥探。
数字签名验证对方身份确保通信完整性。
升级软硬件减少漏洞,加强网络安全监控防御攻击。
理解网络安全威胁和防御手段对设计可靠系统至关重要。
无线网络或者使用同一物理媒体的早期以太网中,数据包会广播给所有节点, facilitates 窃听攻击。
交换机学习主机的MAC地址后将数据包转发到对应端口,若表项过多会被覆盖,导致数据包广播。
恶意DHCP服务器可以快速响应配置主机IP、网关和DNS服务器等信息。
恶意ARP服务器可以欺骗主机获取错误目的MAC地址,欺骗网络流量。
改变网卡为混杂模式收取所有数据包。
利用交换机转发表空间覆盖强制数据包广播。
部署恶意DHCP服务器配置错误网络参数劫持会话。
部署恶意ARP服务器回复错误MAC地址实现中间人攻击。
使用物理隔离网络或加密传输防止窃听。
正确配置DHCP/ARP服务器,定期维护交换机表项。
使用端到端认证防止会话被篡改。
提升网络安全监控能力及时发现异状。
理解这些接入层攻击原理对网络安全防护至关重要。
攻击者以伊芙为例,对交换机进行MAC地址重载攻击。
伊芙 continuosly 发送一个新的MAC地址包,迫使交换机学习表覆盖现有地址。
表项失效后,爱丽丝到鲍勃的数据包将广播,伊芙可以窃听。
使用Mininet网络模拟平台,搭建三主机Topo拓扑。
爱丽丝正常向鲍勃ping通,伊芙无法窃听。
伊芙启动MAC地址重载攻击,交换机表溢出,爱丽丝数据包广播。
伊芙可以使用Wireshark捕获爱丽丝的数据流量。
攻击停止,交换机恢复学习,恢复隐私通信。
使用模拟隔离局域网和加密传输防止窃听。
定期清理交换机学体表,增加新地址学习阈值。
加强入侵检测,监测不法MAC数据包行为。
理解MAC重载攻击原理,对设防至关重要。
攻击者伊芙启动恶意DHCP服务器、DNS服务器和WEB服务器。
伊芙可快速回应DHCP请求,迫使爱丽丝使用恶意DNS服务器。
恶意DNS服务器将域名解析到伊芙的WEB服务器上实施劫持。
Mininet模拟三主机Topo,网络正常运行。
爱丽丝可以访问互联网,DNS查询正确。
伊芙启动DHCP恶意攻击程序。
爱丽丝会使用恶意DHCP、DNS服务器。
爱丽丝访问网站会被导向伊芙的服务器篡改。
窃听会话内容,架设钓鱼网站获取敏感数据。
拦截网站,审查管理网络流量。
利用DNS缓存效应长期绑定用户端游离网络。
理解DHCP攻击在接入层的危害,做好预防对策非常重要。
攻击者伊芙进行ARP欺骗,使交换机学习伊芙拥有爱丽丝和鲍勃的MAC地址。
爱丽丝和鲍勃会使用伊芙的MAC地址通信,数据会转发到伊芙。
伊芙可以中间人攻击,解码计票内容进行窥探。
Mininet模拟三主机Topo网络。
爱丽丝ping鲍勃,伊芙无法看到数据。
伊芙启动ARP欺骗程序。
爱丽丝SSH登录鲍勃,流量被定向到伊芙。
伊芙使用Edicat解码捕获用户名密码等敏感信息。
使用加密协议防止中间人攻击。
访问控制列表限制未授权主机访问内网。
使用ARP巡检检测地址欺骗,及时修复配置表。
理解中间人攻击原理,重视网络访问控制与资产保护工作。
通过ICMP请求重定向路由,导致攻击者成为中间人。
攻击者可以滥发ICMP请求重定向,改变某一主机的路由表,重定向流量。
BGP元数据欺骗,如非法宣告某IP段,劫持其流量。
伪造BGP会话,注入虚假路由表,重定向流量。
使用更具体的IP前缀部分劫持流量。
直接控制BGP路由器,注入虚假路由表更难被发现。
2008年巴基斯坦电信误破坏Youtube流量。
2004年马来西亚大数据1ISP攻击雅虎网站。
2003年黑客劫持北美网络地址后发钓鱼邮件。
理解 layer 3 attack原理,重视网络安全管理与监控工作。
拒绝服务攻击目的在于阻止某项服务的可用性。最简单的拒绝服务攻击方式是过载目标服务器或网络,使其无法正常运行。
拒绝服务攻击主要包括以下几种方式:
洪水攻击:大量发送无端口请求或回声请求等流量,阻塞网络带宽或资源。
散兵攻击:利用分布式计算机网络资源,从不同地址同时发送请求过载目标。攻击难以过滤单一来源。
动态反射攻击:利用DNS、SNMP等协议反射获取大量放大流量攻击目标。单个请求产生数倍流量对目标。
TCP挥霍攻击:发送大量 forged SYN包占满目标服务器半打开连接队列,导致 legitimate 连接被拒绝。
IP分段攻击:发送大量 forged 分段包占满目标存储空间,使其无法重新组包。
声明服务攻击:发送大量请求强行调用echo服务产生更多流量对目标。
Smurf攻击:利用广播回应产生放大流量攻击目标。
2000年2月,黑客使用Smurf攻击瘫疲雅虎系统。
MS Blaster蠕虫使用TCP挥霍攻击windowsupdate.com导致客户无法更新。微软使用CDN Akamai缓解攻击。
Spammer通过拒绝服务攻击关闭反垃圾邮件公司Blue Security作报复。
攻击者入侵大量主机构建僵尸网络,随时启动大规模分布式拒绝服务攻击目标网站。
攻击者利用拒绝服务阻断网站后,要求支付赎金以停止攻击,这就是勒索攻击手法。
拒绝服务攻击手法繁多,随技术发展不断更新。分布式 attacks 和 动态反射攻击尤为难防。切断入侵源头,协调ISP配合过滤,使用CDN分流还是缓解攻击的主要方法。
网络安全保证通信的保密性、完整性和可用性。保密性通过加密实现,让通信内容只有参与方才能查看。完整性通过数字签名和消息验证码实现,确保通信内容未被篡改。可用性通过系统设计可扩展性解决拒绝服务攻击问题。
加密算法通过密钥实现保密通信。一时密码是理想的保密算法,但难以实践。现实中使用对称加密和非对称加密,以较小密钥保护大量数据安全。
数字签名和消息验证码(MAC)实现完整性检查。数字签名只有持有密钥的参与方才能生成,MAC需共享密钥验证。哈希函数计算数据指纹, MAC功能类似但加入密钥。
数字证书实现身份验证。由可信第三方签发的数字证书,可以建立参与方的身份链。消息中加入数字签名证明发送方身份。
通过数据中心和负载均衡实现系统可扩展,分散压力;通过防火墙和IDS过滤入侵流量,阻止拒绝服务攻击成功。
对称加密需要双方共享同一个密钥。加密时使用加密函数E将明文M和密钥K作为输入,产生密文C。解密时使用解密函数D将密文C和密钥K作为输入,还原明文M。
一时密码使用一次性且随机生成的比特串作为密钥。加密时将明文与密钥使用异或操作,解密时亦同。密钥的长度需长于明文,实现完美保密但实际应用难。
常见对称加密算法有AES、blowfish、3DES和RC4等。选择密钥长度足以防止暴力破解,如128位或256位。
AES是美国标准,用于军用和银行应用;blowfish速度快但不再更新;3DES是DES的延伸算法,安全性受限;RC4适用于流式网络数据加密。
我们希望使用较小的密钥实现对大数据量的加密,同时具有足够的安全强度防止破解。这是对称加密在实际应用中的一个重要目标。
如果使用同一个随机密钥K,对两个消息M1和M2进行异或操作加密,产生密文C1和C2。其中:
C1=K xor M1
C2=K xor M2
那么解密C2是否会泄露M1和M2的信息?
答案是不会泄漏信息的。由于密钥K是一个随机串,对任何消息M进行异或都无法得到M的任何信息。所以从C2中无法推导M1和M2的任何内容。
一时密码算法保证了使用同一个随机密钥加密的多个消息之间是绝对无关的,不会产生任何关联性。这就是它实现极高保密性的原因。
如果使用同一个随机密钥K,对两个消息M1和M2进行异或操作加密,产生密文C1和C2。那么被动攻击者Eve得到C1和C2后,是否能够获得M1和M2的信息?
答案是可以的。
因为:
C1 = K xor M1 C2 = K xor M2
那么C1 xor C2就等价于M1 xor M2。
如果M1和M2都为ASCII文本,由于异或操作后会保留部分明文片段,Eve就可以获得M1和M2的部分信息。
更极端的情况下,如果M1=M2,那么C1和C2将是相同的,Eve就可以直接推断M1=M2。
所以一时密码中,严格来说每个密钥K只能用于加密唯一的一个消息,否则将无法提供完美的保密性。这也是它名为“一时”密码的原因。
一时密码难以实现,我们需要能够使用小密钥(128-256位)加密大量数据的加密体系。
流加密通过伪随机数生成密文流进行异或运算加密。块加密针对固定大小(64/128位)的数据块进行加密映射。
流加密存在重复使用密钥序列导致的安全隐患。无线网络原始加密协议WEP即因此被破解。
AES是美国推荐的对称加密标准,已广泛应用于网络通信安全。
Blowfish通过Feistel网络结构对64位数据块进行加密,采用18个子密钥对数据进行16轮迭代加密映射,实现快速加密。
如果对Blowfish算法进行以下修改:
只进行1轮迭代;
第一个明文块全为0,产生密文块C1;
第二个明文块产生密文块C2;
那么第二个明文块的左半部分l0的值就等于C2。
原因是:
只有1轮迭代,相当于对2个明文块进行异或,得到密文块。
第一个明文块全为0,所以C2等于第二个明文块左半部分l0异或0。
异或0不改变值,所以l0的值就等于C2。
通过这次攻击,攻击者可以确定第二个明文块的左半部分具体值为C2,从而获得部分明文信息。这再次说明修改算法可能会带来新安全问题。
如果对Blowfish算法仅进行以下修改:
仅1轮迭代;
第一个明文块全为0;
第一个明文密文为C1;
第二个明文密文为C2;
那么可以推断出第二个明文块左半部分l0的值:
根据第一个明文块为0,可以推断出p1的值为r2,即C1的值0x7b77dca2
知道p1值,可以通过异或运算推断出第二个明文块左半部分l0的值:
l0 = C2 异或 p1
= 0x0dcdc85 异或 0x7b77dca2
= 0xebe0027
所以答案是0xebe0027。
该攻击源于简化Blowfish算法的缺陷,从而破解出部分明文,说明不应改写原始算法设计。
ECB模式对每个明文块单独加密,如果明文重复,密文也重复,无法保证安全性。
CBC模式每个密文块与下一个明文块进行异或,解决了ECB模式的重复明文问题。
要使用CBC模式将信息加密:
选择初始化向量IV;
明文块M1与IV进行异或,加密结果作为密文块C1;
密文块C1与下一个明文块M2进行异或,再加密为C2;
重复步骤3,直到所有明文块加密完毕;
IV不能重复使用,否则可能导致信息泄露。
还有CTR模式、CFB模式等,工作原理不同,适用于不同场景。在选择加密模式时,需要考虑消息特点和性能要求。
如果采用安全的对称密码算法和CBC模式,且正确处理IV,在网络上传输的加密消息在理论上是安全的。但需要防止其他原因导致密钥泄露。
使用对称加密算法进行加密,例如采用CBC模式加密后在网络上传输消息,这只能实现保密性,但无法检测消息是否被篡改。
具体来说:
加密只保证了未授权方无法获取消息内容,实现了保密功能;
但是加密后的数据依然可以被攻击者篡改,检测不到有无改动;
所以仅使用对称加密无法证明消息传输过程中没有被篡改。
所以,对称加密可以提供保密性,但无法保证消息的完整性。需要使用数字签名等技术来达到数据不可抵赖的完整性保护。
除了保密性外,完整性也是系统安全的一个重要属性。
加密只能保证消息内容不被未授权读取,但无法检测消息是否被篡改;
完整性算法可以确保消息来源于持有密钥的主体,从而 detection 消息是否被篡改;
例如文件系统、拍卖、路由等都需要完整性,以防止中间人攻击。
两类来源鉴别机制实现完整性:
加密散列函数:可以检测数据是否被修改,但任何人都可以生成和验证,缺乏鉴别性;
消息认证码:基于密钥,可以确保只有拥有密钥的主体才能生成消息认证码,同时也具备检测数据修改的功能。
通用哈希链路机制HMAC可以实现消息认证码,它采用双层哈希的方式隐藏中间状态;
应使用SHA-256或SHA-512等安全哈希算法;
对消息进行认证时,应计算认证码后再进行加密,而不是加密后再计算认证码。
公钥密码体系使用一对密钥进行加密与解密,包含公开密钥和私密密钥。
公开密钥可以自由传播,任何人使用该密钥对数据进行加密;
只有持有相应私密密钥的接收方才能对使用公开密钥加密的数据进行解密;
公钥密码体系主要算法包括RSA、ElGamal等。
使用系列算法生成一对密钥,公开密钥和对应的私密密钥;
加密使用公开密钥,解密使用私密密钥;
私密密钥无法从公开密钥中推导得出,安全性基于数论难题;
需要加入随机数防止同PLAINTEXT产生相同密文。
公钥密钥可以用来数字签名,提供数据完整性验证功能:
生成数字签名需要私密密钥,验证签名需要公开密钥;
签名防止对方否认已发送的消息,但不提供消息密送功能。
RSA、ElGamal等公钥算法采用大素数运算,计算复杂度大大高于对称加密,通常采用杂交加密方案。
数字证书用于确保公钥的真实性,通过第三方数字签名来核实持有人与公钥的对应关系。
证书包含目标名称、公钥和签发机构数字签名;
签发机构可以是可信根CA机构或其他中间CA;
浏览器预装可信CA公钥,用来验证证书签名;
证书错误可能导致通信不安全,显示安全警告。
数字证书由可信第三方CA签发,建立公钥与主体实体名称之间的对应关系。
根CA公钥直接预装在操作系统和软件中;
中间CA可以为其他网站签发子证书;
证书链关系显示签发权限的传递过程。
使用预装CA公钥核对证书是否由对应CA签名,从而验证公钥持有者身份。实现 SSL/TLS 加密通信和网站身份验证。
TLS是Transport Layer Security的缩写,提供了传输层的安全通信。它位于TCP层之上,为应用层提供可靠且安全的字节流传输服务。
TLS采用五步握手建立安全通道:1客户端发送支持密码列表 2服务器选择密码并返回公钥证书 3客户端用服务器公钥加密预先密钥 4客户端和服务器使用随机数、预先密钥计算对称密钥 5双方发送加密握手消息确认
客户端随机数、服务器随机数和预先密钥通过伪随机函数生成主密钥,再根据主密钥和随机数生成对称密钥、初始向量等会话密钥。密钥长度由所选密码决定。
TLS将应用层数据分成记录,每个记录包含长度和MAC值。记录再经密码加密后通过TCP传输。一条记录可能分成多个TCP报文段传输。TLS也支持数据压缩。
TLS最新版本为1.2,前身是SSL。TLS通过不断升级提高安全性,修复漏洞和增强功能。HTTPS即基于TLS1.2或更高版本提供安全HTTP通信。
TLS客户端随机数和服务器随机数均为32字节,其中4字节为时间戳,28字节为随机数。
预先密钥为48字节,前2字节为协议版本,后46字节为随机数。
假设TLS会话使用上述随机值生成1024字节对称密钥。若攻击者可以正确计算伪随机函数但不知道预先密钥,采取穷举攻击,最多可尝试2的46次。
预先密钥长度为46字节,每个字节有256种可能值,共有2的46种组合;
攻击者尝试每个预先密钥组合并计算出密钥,最多需要2的46次尝试。
攻击者最多需要2的46次尝试来破解TLS session的对称密钥。
客户端和服务器随机数均公开发送,攻击者可知晓;
仅预先密钥为46比特的随机密钥未公开,攻击者需尝试所有可能组合;
一次尝试中,攻击者依次尝试每个预先密钥组合,并通过伪随机函数重计算得到主密钥和对称密钥;
考虑预先密钥组合有2的46种情况,最多需要2的46次尝试来枚举所有可能。
2的46次远大于实际计算能力,证明TLS协议能很好抵御对称密钥的穷举攻击。
虚拟主机技术可以使单个服务器托管多个网站,但会给TLS带来问题:
TLS握手需要将证书中的名字与请求关联,但此时还未获取到应用层域名信息;
服务器无法判断请求对应的域名,选择提供哪个网站的证书;
如果添加新的主机名,TLS会验证失败;
TLS作为会话层protocol需要知道客户端请求的主机名;
但主机名信息只存在于应用层HTTP头部Host字段;
当TLS握手发生时,还未获取到应用层数据;
层次结构导致TLS无法及时获取所需的主机名信息。
层次架构的封装性带来了TLS无法正常运行的问题,说明层次结构并不意味着自动解决所有问题,有时也会限制功能。
网络存在严重安全威胁:窃听、篡改、截取等。我们假设网络被敌对方控制。
保密性:实现隐秘通讯;
完整性:检测消息是否被篡改;
真实性:验证对方持有某个密钥。
对称加密、块密码、ECB模式、CBC模式。杂凑函数的单向性。数字签名实现真实性。
TLS/SSL、HTTPS等。公钥加密及数字证书实现密钥交换。
不要自行实现,应使用经过复杂验证的开源加密库。严格遵循安全最佳实践。
网络安全极为复杂,一个小错可以产生重大危害。应专注安全原则而非算法细节,并使用已验证的安全解决方案。
联邦通信委员会(FCC)是一个独立的监管机构,负责调节美国通信部门。FCC下设5位委员,其中一位为主席。
FCC具有以下职责:
管理无线电频谱发放许可。
监管通信公司,确保公平竞争。
监督有线电视和卫星电视服务。
促进通信技术发展。
处理用户投诉。
为残疾人提供轮椅接入等无障碍通信服务。
不同于其他国家,FCC是一个独立机构,不受行政机关控制。它从国会获得授权后独立监管。其决定只能由法院审查是否违法或违宪。
1990年代,互联网和移动通信技术快速发展。FCC在执法和政策上扮演重要角色,加快了美国通信行业的改革。它允许公司更自由地使用无线电频谱,推进固网与无线网融合。这帮助美国公司成功实现固网到移动的转变。
安德鲁·格洛夫曾警告FCC,数据分组交换技术将摧毁基于电路交换的旧体制。FCC协助新技术赢得竞争,旧公司无法适应改变而失败,例如AT&T。
互联网架构和通信网络的垂直整合产业格局曾阻碍创新。现在正试图通过开放接口等手段,提高软件参与度,加快网络基础设施创新速度。
政府监管在一定程度上可以促进通信网络治理和发展,但也不宜过分干预企业活动。FCC需要根据变化找到平衡点。
Dan Boneh 9岁时,他父亲毫无原因地把RSA算法教给他,他被这些大数和神奇的加密方式深深吸引住了。
大学时期,他继续学习密码学,意识到这是一个同时使用深厚数学和有实际应用的绝佳领域。
他主要研究两方面:密码学及更广泛的计算机安全研究。密码学只是计算机安全一个很小的部分。
软件安全等问题比密码学更大和复杂。
许多家电如照相机、打印机等都采用WEB界面进行配置,但其本身资源很小,无法运行完整的WEB应用程序组成。
所以厂商自己开发轻量级WEB应用,但容易出现各种安全漏洞。Dan Boneh小组购买多种这样的设备测试,发现共有各种漏洞。
如果没有妥善保护,这些设备成为进一步攻击其它网络的跳板。
-例如支持多种算法、易于在发现问题后快速更换算法等设计原则。
本节内容主要介绍互联网最初设计时的八大目标。
互联网最初就是作为一个“网络间互连”的概念,目的是建立一个有效地利用现有互连的网络的技术。早期设计者认为,想要改变每个网络都是不现实的,所以采取了网络间互连的方式。这导致了网络层ing和封装等概念的产生。
互联网通信能力应当在单个或多个网络(网关)失效时继续保持。
互联网应支持各种通信服务类型,不仅限于某一类型。
考虑到数据通信量大,而实时性需求相对较低,无连接的方式更适合数据通信。
互联网不同部分的操作应当相对独立,互联网实体间应该支持端到端通信。
互联网不应该有一个中心控制点,其操作应分散进行。
互联网架构应允许私人网络以广播方式连接,并且不需获得许可。
互联网许以封装的方式,利用现存网络资源进行中继,这对分层架构的支持成为其核心设计原则之一。
以上目标旨在设计一个灵活、弹性强、开放的互联网架构。
互联网由许多小型地区网络或公司构成全球网络。这些小型网络将通过签约大型互联网服务提供商实现全球连通。
主要的互联网服务提供商包括:斯普林特、ATT、英国电信、法国电讯等。这些互联网骨干服务提供商负责不同国家或地区的网络连接,通过对等连接互相传输数据。
每个服务提供商通过自治系统号来标识其负责的网络范围。服务提供商采用边界网关协议BGP来传递网络拓扑信息并建立数据传输路径。
近年来,内容提供商(如谷歌、Facebook)也开始建设自己的网络基础设施,直接与现有网络互联互通。
总体来说,互联网实际上是一个由许多网络构成的网络体系。
主要的测量分类包括:
常用的测量工具包括网络探测器、流量分析仪以及软件定义网络技术等。
将探针设在骨干网络或边缘网络位置可以获取不同视角下的网络数据。
IPv4地址空间即将枯竭, IPv6迁移面临诸多困难。网络结构包含硬件层(光缆管道)、路由智能(路由器)、运营商合作运作(下发地址)、互联网工程任务组(IETF)制定标准(IP协议)。IP地址可以认为是互联网的粘合剂,它将不同的物理网络连接到一起,实现任何两个IPv4/IPv6主机之间的数据发送。
早期,网络规模小,互联网工程师约翰·波斯特负责手动分配IPv4地址。随着网络规模扩张,成立了互联网架构委员会(IAB)分专门负责地址分配。80年代开始大量使用IPv4地址,但主机数量少,32位地址空间似乎极其富余。如斯坦福大学仅有1.4万学生但被分配了1670万个地址。地址分配采取“谁要就给谁”的方式,产生后继问题。
IPv6体系建设完备,但 largescale部署迟迟不进,给技术标准组织和网络运营商带来重大挑战。通讯设备和应用软件厂商也迟迟不进行IPv6兼容改造。几大影响因素:1. 兴趣相关企业利益不同调;2. 更新成本烦琐;3. 网际互操作性较差。当前只能通过旧系统兼容新系统来实现过渡,但效率低下。
相比80年代,现今互联网治理架构更为分散和复杂,各界利益不统一,难以高效协调。IPv6标准制定完毕,但实质应用推广困难重重。关键是 mobilize各方共识,降低升级成本,促进应用体系升级兼容,以加速网络全面迁移新架构。
讲者第一次知道互联网是在1995年大学一年级时。
互联网发展迅速,现在已经成为我们生活中不可或缺的一部分。
电话网络是由网络来管理和提供智能服务,终端设备简单。
电话网络最后一次主要创新是移动电话。
互联网采用了端到端原则,由终端设备进行智能处理,网络层只提供简单转发。
只有终端设备看到以外层信息,网络层只看IP头。
给互联网带来普遍性,网络不区分数据内容,只负责传输。
只有终端设备维护连接状态,平滑处理网络故障。
讲者使用tcpdump分别在本地和远端主机抓包,观察源地址和目标地址。
演示源IP地址和目标端口一致,验证网络连接是正常的。
演示端到端原则下,不同地点的源地址和目标地址。
移动网络上浏览网页的速度相比于WiFi或有线网络来说会变慢。主要原因有以下几点:
DNS查询需要更长时间。手机首先需要查询域名系统(DNS)把域名转换成IP地址,这需要一轮网络往返。
TCP三次握手也需要更长时间。建立TCP连接也需要1.5轮网络往返。
每个网页资源(HTML、图片、CSS、JS等)都需要单独请求,而这些请求可能来自不同的域名,所以每个请求都需要经过DNS查询和TCP连接建立过程。
手机网络带宽和延迟较大。网络往返时间直接影响DNS查询和TCP建立时间。即使数据量小,等待时间也很长。
网页资源越多,请求次数越多,总体加载时间就越长。一般网站包含的资源种类繁多,数量也很大。
移动网络运营商的DNS和网页服务器距离手机更远,这也延长了网络往返时间。
为了提升移动网页加载速度,关键是减少网络请求次数,优化TCP连接建立,利用浏览器本地缓存等技术。Google Chrome通过预取预渲染等技术做了很多优化。
随后演示者详细介绍了网页加载的各个阶段,包括DNS查询、TCP三次握手、HTTP请求获取HTML、浏览器解析HTML发现其他资源需要单独获取、为每个资源重复上述过程。
还使用了瀑布图详细展示了每个资源的DNS、TCP建立、等待响应、接收响应各阶段的耗时,让大家直观了解移动网络每个步骤的耗时来源。
有同学问到为什么DNS查询时间比TCP建立时间长?
回答是DNS系统结构和部署位置原因。DNS服务通常部署在运萟商网络,而网页服务器可能在更远的地方,所以往返时间会长一些。
还有同学问TCP建立时间也很长的原因。回答是对,TCP三次握手在移动网络下也很耗时,这正是移动网页速度慢的一个重要原因。
美国先进研究计划局(ARPA)成立于1958年,目的是防止苏联在科技上带来的威胁,以及保证美国在太空领域的领先地位。1960年代,ARPA开始资助计算机科学研究项目,但各研究机构的计算机资源不能互通。
1969年,ARPA决定建设一个计算机网络,将其资助的计算机科学研究机构连接起来,形成共享资源的网络。这就是阿帕网的开端。第一台路由器安装在加州大学洛杉矶分校。1970年首次完成两台计算机之间的数据传输。
20世纪70年代中后期,芬塞尔夫与鲍伯·卡恩在斯坦福大学设计了TCP/IP协议族,确立了互联网架构的基础。1983年1月1日,ARPANET正式采用TCP/IP协议,标志着互联网正式形成。
芬塞尔夫此后长期担任美国计算机协会主席和谷歌首席互联网传道师,致力推广开放的网络环境。他参与建立了域名解析机构ICANN,并在各国议会倡导网络中立等原则。
尽管互联网基础设施与协议设计已经存在40年,但系统的发展与演变还有很大潜力。新型网络层技术如OpenFlow可以为这一过程提供支持。同时,社会的需要也在驱动着互联网服务的不断完善。今后的研究与创新将推动互联网进入新的阶段。
从网络视角来看,移动性指的是主机点对网络的连接点随时间的改变。移动性不等于物理移动。例如使用WiFi在室内切换是具有移动性的,但阅读线上课程视频时就没办法移动。
移动性分为:
微观移动性:一天内主机点经常改变,如早上在宿舍上网,然后上课在教室使用WiFi。
中度移动性:一天内主机点会多次改变,如上下课时连接不同WiFi。
makro移动性:在车内或飞机上长时间保持网络连接的场景。
确保通信中断。
主机IP地址随连接点变更,需要动态分配IP。
需要运营商基础设施支持流量转发。
对方是否需要知道IP地址变更是可选的,考虑到隐私保护,对方无需了解位置也可以。
随着主机连接方式由有线向无线主导,需要适应:
主机连接点更易变,需要支持流量中继。
IP协议层设计初衷为固定连接,并不方便支持移动主机。
需要在IP层以下增加移动支持机制。
以上内容整理自斯坦福CS144课程中Jim Ku教授关于移动通信的课堂讲义。