计算机网络自顶向下方法::计算机网络中的安全

什么是网络中的安全 机密性 (confidentiality)。仅有发送方和希望的接收方能够理解传输报文的内容因为窃听者可以截获报文,这必须要求报文在一定程度上进行加密(encrypted),使截取的报文无法被截获者所理解。机密性的这个方面大概就是通常意义上对于术语安全通信的理解。 报文完整性 (message integrity)。Alice 和 Bob 希望确保其通信的内容在传输过程中未被改变——或者恶意篡改或者意外改动。我们在可靠传输和数据链路协议中遇到的检验和技术在扩展后能够用于提供这种报文完整性。 端点鉴别(end-point authentication)。发送方和接收方都应该能证实通信过程所涉及的另一方,以确信通信的另一方确实具有其所声称的身份。人类的面对面通信可以通过视觉识别轻易地解决这个问题。当通信实体在不能看到对方的媒体上交换报文时,鉴别就不是那么简单了。当某用户要访问一个邮箱时,邮件服务器如何证实该用户就是他所声称的那个人呢。 运行安全性(operational security)。几乎所有的机构(公司、大学等)今天都有了与公共因特网相连接的网络。这些网络都因此潜在地能够被危及安全。攻击者能够试图在网络主机中安放蠕虫,获取公司秘密,勘察内部网络配置并发起 DoS 攻击。我们将看到诸如防火墙和入侵检测系统等运行设备正被用于反制对机构网络的攻击。防火墙位于机构网络和公共网络之间,控制接入和来自网络的分组。入侵检测系统执行“深度分组检查“任务,向网络管理员发出有关可疑活动的警告。 密码学的原则 对称密钥密码体制 历史上的单密码 凯撒密码 单密码替换 多码代替密码 块密码 该密码用在多种因特网协议的加密中,包括 PGP (用于安全电子邮件)、SSL(用于使 TCP 连接更安全)和 IPsec(用于使网络层传输更安全)。 在块密码中,要加密的报文被处理为 K 比特的块。每块被独立加密。为了加密一个块,该密码采用了一对一映射,将 K 比特块的明文映射为 K 比特块的密文。 目前有一些流行的块密码,包括 DES (Data Encryption Standard, 数据加密标准)3DES 和 AES (Advanced Encryption Standard, 高级加密标准)。 密码块链接 在计算机网络应用中,通常需要加密长报文(或长数据流)。如果使用前面描述的块密码,通过直接将报文切割成 K 比特块并独立地加密每块,将出现一个微妙而重要的问题。为了理解这个问题,注意到两个或更多个明文块可能是相同的。例如,两个或更多块中的明文可能是 HHTTP/1.1 。对于这些相同的块,块密码当然将产生相同的密文。当攻击者看到相同的密文块时,它可能潜在地猜出其明文,并且通过识别相同的密文块和利用支撑协议结构的知识,甚至能够解密整个报文。为了解决这个问题,可以在密文中混合某些随机性,使得相同的明文块产生不同的密文块。 公开密钥加密 公开密钥密码学(英语:Public-key cryptography)也称非对称式密码学(英语:Asymmetric cryptography)是密码学的一种算法,它需要两个密钥,一个是公开密钥,另一个是私有密钥;公钥用作加密,私钥则用作解密。使用公钥把明文加密后所得的密文,只能用相对应的私钥才能解密并得到原本的明文,最初用来加密的公钥不能用作解密。由于加密和解密需要两个不同的密钥,故被称为非对称加密;不同于加密和解密都使用同一个密钥的对称加密。公钥可以公开,可任意向外发布;私钥不可以公开,必须由用户自行严格秘密保管,绝不透过任何途径向任何人提供,也不会透露给被信任的要通信的另一方。 RSA 报文完整性和数字签名 密码散列函数 MD5,SHA-1,SHA-256 报文鉴别码 发送发送方使用一个密钥和特定算法对明文产生一个短小的定长数据分组,即 MAC(报文鉴别码),并将它附加在报文中。在接收方,使用相同密钥的和算法对明文计算 MAC,如果新的 MAC 与报文中的 MAC 匹配,那么接受者确信报文未被修改过,接受者确信报文来自所期望的发送方。 数字签名 在数字领域,人们通常需要指出一个文件的所有者或创作者,或者表明某人认可一个文件内容。数字签名(digital signature) 就是一种在数字领域实现这些目标的密码技术。 Bob 让他的初始长报文通过一个散列函数。然后他用自己的私钥对得到的散列进行数字签名。明文形式的初始报文连同已经数字签名的报文摘要(从此以后可称为数字签名)一道被发送给 Alice。 Alice 先把发送方的公钥应用于报文获得一个散列结果。然后她再把该散列函数应用于明文报文以得到第二个散列结果。如果这两个散列匹配,则 Alice 可以确信报文的完整性及其发送方 。 公钥认证 数字签名的一个重要应用是公钥认证 (public key certification),即证实一个公钥属于某个特定的实体。公钥认证用在许多流行的安全网络协议中,包括 IPsec 和 SSL。 CA 证实一个实体( 一个人 、一台路由器等)的真实身份。如何进行认证并没有强制的过程。当与一个 CA 打交道时,一方必须信任这个 CA 能够执行适当的严格身份验证。 一旦 CA 验证了某个实体的身份,这个 CA 会生成一个将其身份和实体的公钥绑定起来的证书(certificate)。这个证书包含这个公钥和公钥所有者全局唯一的身份标识信息(例如,一个人的名字或一个 IP 地址)。由 CA 对这个证书进行数字签名。 端点鉴别 当经网络进行鉴别时,通信各方不能依靠生物信息比如外表、声波纹等进行身份鉴别。的确,我们会在后面的实例研究中看到,诸如路由器、客户/服务器进程等网络元素通常必须相互鉴别。此处,鉴别应当在报文和数据交换的基础上,作为某鉴别协议 (authentication protocol)的一部分独立完成。鉴别协议通常在两个通信实体运行其他协议(例如,可靠数据传输协议、路由选择信息交换协议或电子邮件协议)之前运行。鉴别协议首先建立相互满意的各方的标识;仅当鉴别完成之后,各方才继续下面的工作。 不重数和对称密钥密码体制 Alice 向 Bob 发送报文“我是 Alice" 。 Bob 选择一个不重数 R , 然后把这个值发送给 Alice 。 Alice 使用她与 Bob 共享的对称秘密密钥 \(K_{A-B}\) 来加密这个不重数,然后把加密的不 重数 \(K_{A-B}(R)\) 发回给 Bob。与在协议 ap3.1 中一样,由于 Alice 知道 \(K_{A-B}\) 并用它加密一个值,就使得 Bob 知道收到的报文是由 Alice 产生的。这个不重数用于确定 Alice 是活跃的 。 Bob 解密接收到的报文。如果解密得到的不重数等于他发送给 Alice 的那个不重数,则可鉴别 Alice 的身份 。 安全电子邮件 Alice 发送邮件时 Alice 对她要发送的报文 m 应用一个散列函数 H(例如 MD5), 从而得到一个报文摘要; 用她的私钥 SK 对散列函数的结果进行签名,从而得到一个数字签名; 把初始报文(未加密)和该数字签名级联起来生成一个包; 向 Bob 的电子邮件地址发送这个包。 当 Bob 接收到这个包时 他将 Alice 的公钥 PBK 应用到被签名的报文摘要上; 将该操作的结果与他自己对该报的散列 H 进行比较 PGP 安装 PGP 时,软件为用户产生一个公开密钥对。该公钥能被张贴到用户的网站上或放置在某台公钥服务器上。 私钥使用用户口令保护。 PGP 允许用户选择是否对报文加密,数字签名,并对数字签名加密。 PGP 也提供了一种公钥认证机制,但是这种机制与更为传统的 CA 差异很大。PGP 公钥由一个可信 Web 验证。当 Alice 相信 一个密钥/用户名对确实匹配时,她自己就可以验证这一密钥/用户名对。 使 TCP 连接安全:SSL TCP 的这种强化版本通常被称为安全套接字层(Secure Socket Layer, 修改的版本被称为运输层安全性(Transport Layer Secu1ily, SSL)。SSL 版本 3 的一个稍加修改的版本被称为运输层安全性(Transport Layer Securily,TLS), 已经由 IETF 标准化。 握手 Bob 与 Alice 创建一条 TCP 连接 验证 Alice 是真实的 Alice 发送给 Alice 一个主密钥,Bob 和 Alice 待用该主密钥生成 SSL 会话所需的所有对称密钥 一旦创建了 TCP 连接, Bob 就向 Alice 发送一个 hello 报文 。Alice 则用她的证书进行响应,证书中包含了她的公钥。因为该证书已被某 CA 证实过,Bob 明白无误地知道该公钥属于 Alice。 Bob 产生一个主密钥 (MS)(该 MS 将仅用于这个 SSL 会话),用 Alice 的公钥加密该 MS 以生成加密的主密钥 (EMS),并将该 EMS 发送给 Alice Alice 用她的私钥解密该 EMS 从而得到该 MS SSL 握手 客户发送它支持的密码算法的列表,连同一个客户的不重数。 从该列表中,服务器选择一种对称算法(例如 AES)、一 种公钥算法(例如具有特定密钥长度的 RSA)和一种 MAC 算法。它把它的选择以及证书和一个服务器不重数返回给客户。 客户验证该证书,提取服务器的公钥,生成一个前主密钥(Pre-Master Secret,PMS),用服务器的公钥加密该 PMS, 并将加密的 PMS 发送给服务器 。 使用相同的密钥导出函数(就像 SSL 标准定义的那样),客户和服务器独立地从 PMS 和不重数中计算出主密钥(Master Secret,MS)。然后该 MS 被切片以生成两个密码和两个 MAC 密钥。此外,当选择的对称密码应用于 CBC(例如 3DES 或 AES),则两个初始化向量(Initialization Vector,IV)也从该 MS 获得,这两个 IV 分别用于该连接的两端。自此以后,客户和服务器之间发送的所有报文均被加密和鉴别(使用 MAC)。 客户发送所有握手报文的一个 MAC 。 服务器发送所有握手报文的一个 MAC 。 关闭连接 在某个时刻,Bob 或者 Alice 将要终止 SSL 会话。一个方法是让 Bob 通过直接终止底层的 TCP 连接来结束该 SSL 会话,这就是说,通过让 Bob 向 Alice 发送一个 TCP FIN 报文段。但是这种幼稚设计为截断攻击(truncation attack)创造了条件,Trudy 再一次介入一个进行中的 SSL 会话中,并用 TCP FIN 过早地结束了该会话。如果 Trudy 这样做的话,Alice 将会认为她收到了 Bob 的所有数据,而实际上她仅收到了其中的一部分。对这个问题的解决方法是,在类型字段中指出该记录是否是用于终止该 SSL 会话的。(尽管 SSL 类型是以明文形式发送的,但在接收方使用了记录的 MAC 对它进行了鉴别。)通过包括这样一个字段,如果 Alice 在收到一个关闭 SSL 记录之前突然收到了一个 TCP FIN,她可能知道正在进行着某些耍花招的事情。 网络层安全性:IPsec 和虚拟安全网 IP 安全(IP Security)协议更常被称为 IPsec,它为网络层提供了安全性。IPsec 为任意两个网络层实体(包括主机和路由器)之间的 IP 数据报提供了安全。如我们很快要描述的那样,许多机构(公司、政府部门、非营利组织等等)使用 IPsec 创建了运行在公共因特网之上的虚拟专用网 (Vir1ual Private, Network, VPN) 。 除了机密性,网络层安全协议潜在地能够提供其他安全性服务。例如,它能提供源鉴别,使得接收实体能够验证安全数据报的源。网络层安全协议能够提供数据完整性,使得接收实体能够核对在数据报传输过程中可能出现的任何篡改。网络层安全服务也能提供防止重放攻击功能,这意味着 Bob 能够检测任何攻击者可能插入的任何冗余数据报。我们将很快看到 IPsec 的确提供了用于些安全服务的机制,即机密性、源鉴别、数据完整性和重放攻击防护。 IPsec 和虚拟专用网 当总部中的一台主机向某旅馆中的某销售员发送一个 IP 数据报时,总部中的网关路由器将经典的 IPv4 转换成为 IPsec 数据报,然后将该 IPsec 数据报转发进因特网。该 IPsec 数据报实际上具有传统的 IPv4 首部,因此在公共因特网中的路由器处理该数据报,仿佛它对路由器而言是一个普通的 IPv4 数据报。IPsec 数据报的载荷包括了一个 IPsec 首部,该首部被用于 IPsec 处理;此外,IPsec 数据报的载荷是被加密的。当该 IPsec 数据报到达销售员的便携机时,便携机的操作系统解密载荷并提供其他安全服务,如验证数据完整性,并将解密的载荷传递给上层协议(例如,给 TCP 或 UDP)。 运行安全性:防火墙和入侵检测系统 防火墙(firewall)是一个硬件和软件的结合体,它将一个机构的内部网络与整个因特网隔离开,允许一些数据分组通过而阻止另一些分组通过。防火墙允许网络管理员控制外部和被管理网络内部资源之间的访问,这种控制是通过管理流人和流出这些资源的流量实现的。 从外部到内部和从内部到外部的所有流量都通过防火墙。 仅被授权的流量(由本地安全策略定义)允许通过。 防火墙自身免于渗透。 防火墙分类 传统分组过滤器 (traditional packet filter) 一个机构通常都有一个将其内部网络与其 ISP(并因此与更大的公共因特网相连)相连的网关路由器。所有离开和进入内部网络的流量都要经过这个路由器,而这个路由器正是分组过滤(packet filtering)出现的地方。分组过滤器独立地检查每个数据报,然后基于管理员特定的规则决定该数据报应当允许通过还是应当丢弃。 状态过滤器 (slateful filter) 传统的防火墙无法管理连接,大量的连接仍然能使内部网络崩溃。状态过滤器通过用一张连接表来跟踪所有进行中的 TCP 连接来解决这个问题。防火墙能够通过观察三次握手(SYN、SYN ACK 和 ACK)来观察一条新连接的开始;而且当它看到该连接的一个 FIN 分组时,它能够观察该连接的结束,当防火墙经过比如说 60 秒还没有看到该连接的任何活动性,它也能够(保守地)假设该连接结束了。 应用程序网关 为了得到更高水平的安全性,防火墙必须把分组过滤器和应用程序网关结合起来。应 用程序网关除了看 IP/TCP/UDP 首部外,还基于应用数据来做策略决定。一个应用程序网关 (application gateway )是一个应用程序特定的服务器,所有应用程序数据(入和出的)都必须通过它。多个应用程序网关可以在同一主机上运行,但是每一个网关都是有自己的进程的单独服务器 。 入侵检测程序 为了检测多种攻击类型,我们需要执行深度分组检查(deep packet inspection),即查看首部字段以外部分,深入查看分组携带的实际应用数据。应用程序网关经常做深度分组检查。而一个应用程序网关仅对一种特定的应用程序执行这种检查。 入侵检测设备仅能够检查所有通过它传递的分组的首部(类似于分组过滤器 ),而且能执行深度分组检查(与分组过滤器不同)的设备。当这样的设备观察到一个可疑的分组时,或一系列可疑的分组时,它能够防止这些分组进入该机构网络。或者仅仅是因为觉得该活动可疑,该设备虽说能够让这些分组通过,但要向网络管理员发出告警,网络管理员然后密切关注该流量并采取适当的行动。 当观察到潜在恶意流量时能产生告警的设备称为入侵检测系统 (Intrusion Detection System,IDS)。滤除可疑流量的设备称为入侵防止系统(Intrusion Prevention System , IPS) 。

2021 Jun 19 · 3 min

计算机网络自顶向下方法::链路层与局域网

链路层概述 在本章中为方便讨论,将运行链路层协议协议的任何设备均称为节点。节点包括主机、路由器、交换机和 WiFi 接入点 。我们也把沿着通信路径连接相邻节点的通信信道称为链路。为了将一个数据报从源主机传输到目的主机,数据报必须通过沿端到端路径上的各段链路传输。 链路层提供的服务 成帧(framing).在每个网络层数据报经链路传送之前,几乎所有的链路层协议都要将其用链路层帧封装起来。一个帧由一个数据字段和若干首部字段组成,其中网络层数据报就插在数据字段中。帧的结构由链路层协议规定。 链路接入。媒体访问控制(Medium Access Control, MAC)协议规定了帧在链路上传输的规则。 可靠交付。当链路层协议提供可靠交付服务时。它保证无差错地经链路层移动每个网络层数据报 差错检测和纠正。当帧中的一个比特作为 1 传输时,接收方节点中的链路层硬件可能不正确地将其判断为 0,反之亦然。这种比特差错是由信号衰减和电磁噪声导致的。因为没有必要转发一个有差错的数据报,所以许多链路层协议提供一种机制来检测这样的比特差错。通过让发送节点在帧中包括差错检测比特,让接收节点进行差错检查,以此来完成这项工作。 链路层在何处实现 链路层的主体部分是在网络适配器(network adapter)中实现的,网络适配器有时也称为网络接口卡(Nehvork Interface Card, NIC)。位于网络适配器核心的是链路层控制器,该控制器通常是一个实现了许多链路层服务(成帧、链路接入、差错检测等)的专用片。因此,链路层控制器的许多功能是用硬件实现的。 在发送端,控制器取得了由协议栈较高层生成并存储在主机内存中的数据报,在链路层帧中封装该数据报(填写该帧的各个字段),然后遵循链路接入协议将该帧传进通信链路中。在接收端,控制器接收了整个帧,抽取出网络层数据报。如果链路层执行差错检 测,则需要发送控制器在该帧的首部设置差错检测比特,由接收控制器执行差错检测。 链路层的软件组件实现了高层链路层功能,如组装链路层寻址信息和激活控制器硬件。在接收端,链路层软件响应控制器中断,处理差错条件和将数据报向上传递给网络层。所以,链路层是硬件和软件的结合体。 差错检测和纠正技术 奇偶位校验 假设要发送的信息 D 有 d 比特。在偶校验方案中,发送方只需包含一个附加的比特,选择它的值,使得这 d+1 比特中 1 的总数是偶数。对于奇校验方案,选择校验比特值使得有奇数个 1。单个校验比特被存放在一个单独的字段中。 采用单个奇偶校验位方式。接收方的操作也很简单。接收方只需要数一数接收的 d + 1 比特中 1 的数目即可。如果在采用偶校验方案中发现了奇数个值为 1 的比特,接收方知道至少出现了一个比特差错。更精确的说法是,出现了奇数个比特差错。 二维奇偶校验 单比特奇偶校验方案的二维一般化方案。这里 D 中的 d 个比特被划分为 i 行 j 列。对每行和每列计算奇偶值。产生的 i+j+1 奇偶比特构成了链路层帧的差错检测比特。现在假设在初始 d 比特信息中出现了列单个比特差错。使用这种二维奇偶校验方案,包含比特值改变的列和行的校验值都将会出现差错。因此接收方不仅可以检测到出现了单个比特差错的事实,而且还可以利用存在奇偶校验差错的列和行的索引来实际识别发生差错的比特并纠正它! 接收方检测和纠正差错的能力被称为前向纠错,FEC 技术很有价值,因为它们可以减少所需的发送方重发的次数。也许更为重要的是,它们允许在接收方立即纠正差错。FEC 避免了不得不等待的往返时延,而这些时延是发送方收到 NAK 分组并向接收方重传分组所需要的,这对于实时网络应用或者具有长传播时延的链路(如深空间链路)可能是一种非常重要的优点。 检验和方法 因特网检验和(Internet checksum)就基于这种方法,即数据的字节作为 16 比特的整数对待并求和。这个和的反码形成了携带在报文段首部的因特网检验和。接收方通过对接收的数据(包括检验和)的和取反码,并且检测其结果是否为全 1 比特来检测检验和。如果这些比特中有任何比特是 0, 就可以指示出差错。检验和方法需要相对小的分组开销。例如,TCP 和 UDP 中的检验和只用了 16 比特。然而,与常用于链路层的 CRC 相比,它们提供相对弱的差错保护。 循环冗余检测 现今的计算机网络中广泛应用的差错检测技术基于循环冗余检测编码 CRC 编码也称为多项式编码,因为该编码能够将要发送的比特串看作为系数是 0 和 1 一个多项式,对比特串的操作被解释为多项式算术。 多路访问链路和协议 有两种类型的网络链路:点对点链路和广播链路。 点对点链路(point-to-point link)由链路一端的单个发送方和链路另一端的单个接收方组成。许多链路层协议都是为点对点链路设计的,如点对点协议 (point-to-point protocol, PPP)和高级数据链路控制(high-level data link control HDLC)就是两种这样的协议。 广播链路(broadcast link),它能够让多个发送和接收节点都连接到相同的、单一的、共享的广播信道上。广播信道通常用于局域网中,局域网是一个地理上集中在一座建筑物中的网络。 多路访问协议 信道划分协议 时分多路复用(TDM)和频分多路复用(FDM)是两种能够用于在所有共享信道节点之间划分广播信道带宽的技术。假设一个支持 N 个节点的信道且信道的传输速率为 Rbps。TDM 将时间划分为时间帧(time frame),并进一步划分每个时间帧为 N 个时隙(slot)。然后把每个时隙分配给 N 个节点中的一个。无论何时某个节点在有分组要发送的时候,它在循环的 TDM 帧中指派给它的时隙内传输分组比特。通常,选择的时隙长度应使一个时隙内能够传输单个分组。TDM 是有吸引力的,因为它消除了碰撞而且非常公平:每个节点在每个帧时间内得到了专用的传输速率 R/N bps。然而它有两个主要缺陷。首先,节点被限制于 R/N bps 的平均速率,即使当它是唯一有分组要发送的节点时。其次,节点必须总是等待它在传输序列中的轮次,即我们再次看到,即使它是唯一一个有帧要发送的节点。 FDM 将 R bps 信道划分为不同的频段(每个频段具有 R/N 带宽),并把每个频率分配给 N 个节点中的一个。因此 FDM 在单个较大的 R bps 信道中创建了 N 个较小的 R/N bps 信道。FDM 也有 TDM 同样的优点和缺点。它避免了碰撞.在 N 个节点之间公平地划分了带宽,然而,FDM 也有 TDM 所具有的主要缺点,也就是限制一个节点只能使用 R/N 的带宽,即使当它是唯一一个有分组要发送的节点时。 CDMA 对每个节点分配一种不同的编码。然后每个节点用它唯一的编码来对它发送的数据进行编码。如果精心选择这些编码,CDMA 网络具有一种奇妙的特性,即不同的节点能够同时传输,并且它们各自相应的接收方仍能正确接收发送方编码的数据比特,而不在乎其他节点的干扰传输 CDMA 已经在军用系统中使用了一段时间,目前已经广泛地用于民用,尤其是蜂窝电话中。 随机接入协议 在随机接入协议中,一个传输节点总是以信道的全部速率(即 R bps ) 进行发送,当有碰撞时,涉及碰撞的每个节点反复地重发它的帧(也就是分组),到该帧无碰撞地通过为止。但是当一个节点经历一次碰撞时,它不必立刻重发该帧。相反,它在重发该帧之前等待一个随机时延。涉及碰撞的每个节点独立地选择随机时延。因为该随机时延是独立地选择的,所以下述现象是有可能的:这些节点之一所选择的时延充分小于其他碰撞节点的时延,并因此能够无碰撞地将它的帧在信道中发出。 时隙 ALOHA 所有帧由 L 比特组成 时间被划分成长度为 L/R 秒的时隙。 节点只在时隙起点开始传输帧。 节点是同步的。每个节点都知道时隙何时开始。 如果在一个时隙中有两个或者更多个帧碰撞。则所有节点在该时隙结束之前检测到该碰撞事件。令 p 是一个概率,即一个在 0 和 1 之间的数。在每个节点中,时隙 ALOHA 的操作是简单的。 当节点有一个新帧要发送时,它等到下一个时隙开始并在该时隙传输整个帧。 如果没有碰撞,该节点成功地传输它的帧,从而不需要考虑重传该帧。 如果有碰撞,该节点在时隙结束之前检测到这次碰撞。每个时隙中重传它的帧,直到该帧被无碰撞地传输出去 时隙多路访问协议的效率定义为:当有大量的活跃节点且每个节点总有大量的帧要发送时,长期运行中成功时隙的份额。注意到如果不使用某种形式的访问控制,而且每个节点都在每次碰撞之后立即重传,这个效率将为零。时隙 ALOHA 显然增加了它的效率,使之大于零 载波侦听多路访问 (CSMA) 说话之前先听。如果其他人正在说话,等到他们说完话为止。在网络领域中,这被称为载波侦听(carrier sensing) 即一个节点在传输前先听信道。如果来自另一个节点的帧正向信道上发送,节点则等待直到检测到一小段时间没有传输,然后开始传输 。 如果与他人同时开始说话,停止说话。在网络领域中,这被称为碰撞检测(colliion detection),即当一个传输节点在传输时一直在侦听此信道户。如果它检测到另一个节点正在传输干扰帧,它就停止传输,在重复"侦听-当空闲时传输"循环之前等待一段随机时间。 这两个规则包含在载波侦听多路访问(Carrier Sense Multiple Access, CSMA) 和具有碰撞检测的 CSMA。 具有碰撞检测的载波侦听多路访问 (CSMA/CD) 适配器从网络层一条获得数据报,准备链路层帧,并将其放入帧适配器缓存中。 如果适配器侦听到信道空闲(即无信号能量从信道进入适配器),它开始传输帧。在另一方面,如果适配器侦听到信道正在忙,它将等待,直到侦听到没有信号能批时才开始传输帧。 在传输过程中,适配器监视来自其他使用该广播信道的适配器的信号能量的存在。 如果适配器传输整个帧而未检测到来自其他适配器的信号能量,该适配器就完成了该帧。在另一方面,如果适配器在传输时检测到来自其他适配器的信号能量,它中止传输(即它停止了传输帧)。 中止传输后,适配器等待一个随机时间量、然后返回步骤 2 轮流协议 轮询协议 轮询协议要求这些节点之一要被指定为主节点。主节点以循环的方式轮询(poll)每个节点。特别是,主节点首先向节点 1 发送一个报文,告诉它(节点 1)能够传输的帧的最多数量。在节点 1 传输了某些帧后,主节点告诉节点 2 它(节点 2)能够传输的帧的最多数量。上述过程以这种方式继续进行,主节点以循环的方式轮询了每个节点。轮询协议消除了困扰随机接入协议的碰撞和空时隙,这使得轮询取得高得多的效率。但是它也有一些缺点。第一个缺点是该协议引入了轮询时延,即通知一个节点”它可以传输”所需的时间。例如,如果只有一个节点是活跃的,那么这个节点将以小于 R bps 的速率传输,因为每次活跃节点发送了它最多数量的帧时,主节点必须依次轮询每一个非活跃的节点。第二个缺点可能更为严重,就是如果主节点有故障,整个信道都变得不可操作。 令牌传递协议 在这种协议中没有主节点。一个称为令牌(token)的小的特殊帧在节点之间以某种固定的次序进行交换。例如,节点 1 可能总是把令牌发送给节点 2,节点 2 可能总是把令牌发送给节点 3,而节点 N 可能总是把令牌发送给节点 1。当一个节点收到令牌时,仅当它有一些帧要发送时,它才持有这个令牌;否则,它立即向下一个节点转发该令牌。当一个节点收到令牌时,如果它确实有帧要传输,它发送最大数目的帧数,然后把令牌转发给下一个节点。令牌传递是分散的,并有很高的效率。但是它也有自己的一些问题。例如,一个节点的故障可能会使整个信道崩溃。或者如果一个节点偶然忘记了释放令牌,则必须调用某些恢复步骤使令牌返回到循环中来。 DOCSIS: 用于电缆因特网接入的链路层协议 一个电缆接入网通常在电缆网头端将几千个住宅电缆调制解调器与一个电缆调制解调器端接系统 CMTS 连接。CMTS 规范定义了电缆数据网络体系结构及其协议。DOCSIS 使用 FDM 将下行和上行(调制解调器到 CMTS) 网络段划分为多个频率信道。CMTS 在下行信道中传输的帧被所有在信道上做接收的电缆调制解调器接收到;然而因为仅有单一的 CMTS 在下行信道上传输,不存在多路访问问题。但在上行方向,存在着多个有趣的技术挑战,因为多个电缆调制解调器共享到 CMTS 的相同上行信道(频率),因此能够潜在地出现碰撞)。电缆调制解调器既不能侦听上行信道是否忙,也不能检测碰撞。相反,该电缆调制解调器如果没有在下一个下行控制报文中收到对请求分配的响应的话,就推断出它的微时隙请求帧经历了一次碰撞。当推断出一次碰撞,电缆调制解调器使用二进制指数回退将其微时隙请求帧延缓到以后的时隙重新发送。当在上行信道上有很少的流量,电缆调制解调器可能在名义上分配给微时隙请求帧的时隙内实际传输数据帧(因此避免不得不等待微时隙分配)。 交换局域网 链路层寻址和 ARP (ARP)该协议提供了将 IP 地址转换为链路层地址的机制。 MAC 地址 并不是主机或路由器具有链路层地址,而是它们的适配器(即网络接口)具有链路层地址。 链路层地址有各种不同的称呼:LAN 地址(LAN address)、物理地址(physical address)或 MAC 地址(MAC address)。因为 MAC 地址似乎是最为流行的术语,所以我们此后就将链路层地址称为 MAC 地址。 MAC 地址的一个有趣性质是没有两块适配器具有相同的地址。IEEE 在管理着该 MAC 地址空间。特别是,当一个公司要生产适配器时,它支付象征性的费用购买组成 2^24 个地址的一块地址空间。IEEE 分配这块 2^24 个地址的方式是:固定一个 MAC 地址的前 24 比特,让公司自已为每个适配器生成后 24 比特的唯一组合。 当某适配器要向某些目的适配器发送一个帧时、发送适配器将目的适配器的 MAC 地址插入到该帧中,并将该帧发送到局域网 上。 地址解析协议 因为存在网络层地址(例如,因特网的 IP 地址)和链路层地址(即 MAC 地址),所以需要在它们之间进行转换。对于因特网而言、这是地址解析协议(Address Resolution Protocol,ARP)的任务。 为了发送数据报,该源必须要向它的适配器不仅提供 IP 数据报,而且要提供目的主机 222.222.222.222 的 MAC 地址。然后发送适配器将构造一个包含目的地的 MAC 地址的链路层帧,并把该帧发送进局域网。 通过在发送主机中的 ARP 模块将取在相同局域网上的任何 IP 地址作为输入,然后返回相应的 MAC 地址获得 MAC 地址。 每台主机或路由器在其内存中具有一个 ARP 表(ARP table),这张表包含 IP 地址到 MAC 地址的映射关系该 ARP 表也包含一个寿命(TTL)值,它指示了从表中删除每个映射的时间。注意到这张表不必为该子网上的每台主机和路由器都包含一个表项;某些可能从来没有进入到该表中,某些可能已经过期。从一个表项放置到某 ARP 表中开始,一个表项通常的过期时间是 20 分钟。 当 ARP 表项不在时,发送方构造一个 ARP 分组,广播到连接在适配器上的所有设备。对应 MAC 地址的机器用标准帧回复。 最好把 ARP 看成是跨越链路层和网络层边界两边的协议 发送数据报到子网以外 子网内部通过 ARP 寻址发送数据包到路由器,子网之间的路由器也通过 ARP 协议获取 MAC 地址。 以太网 以太网因为布局早,价格,传输效率等原因已经占领绝大多数市场。 以太网帧结构 数据字段(46~1500 字节)。这个字段承载了 IP 数据报。以太网的最大传输单元(MTU)是 1500 字节。 目的地址(6 字节)。这个字段包含目的适配器的 MAC 地址,即 BB-BB-BB-BB-BB-BB。当适配器 B 收到一个以太网帧,帧的目的地址无论是 BB-BB-BB-BB-BB­-BB.还是 MAC 广播地址,它都将该帧的数据字段的内容传递给网络层;如果它收到了具有任何其他地址的帧,则丢弃之。 源地址(6 字节)。这个字段包含了传输该帧到局域网上的适配器的 MAC 地址 类型宇段(2 字节)。类型字段允许以太网复用多种网络层协议。 CRC 前同步码(8 字节)。以太网帧以一个 8 字节的前同步码(Preamble)字段开始。该前同步码的前 7 字节的值都是 10101010;最后一个字节是 10101011。前同步码字段的前 7 字节用于“唤醒“接收适配器,并且将它们的时钟和发送方的时钟同步。 以太网技术都向网络层提供不可靠服务。特别是,当适配器 B 收到一个来自适配器 A 的帧,它对该帧执行 CRC 校验,但是当该帧通过 CRC 校验时它既不发送确认帧;而当该帧没有通过 CRC 校验时它也不发送否定确认帧。当某帧没有通过 CRC 校验,适配器 B 只是丢弃该帧。 以太网技术 使用标准以太网帧格式, 并且后向兼容 1OBASE-T 与 1OOBASE-T 技术。这使得吉比特以太网和现已安装的以太网设备基础很容易集成。 允许点对点链路以及共享的广播信道。如前所述,点对点链路使用交换机,而广播信道使用集线器。在吉比特以太网术语中,集线器被称为"带缓存的分配器” 。 使用 CSMA/CD 来共享广播信道。为了得到可接受的效率,节点之间的最大距离必须严格限制。 对于点对点信道,允许在两个方向上都以 40 Gbps 全双工操作 。 通过所有这些改变,的确还有一个历经 30 年保持未变的持久不变量,即以太网帧格式。也许这才是以太网标准的一个真正重要的特征。 链路层交换机 交换机的任务是接收入链路层帧并将它们转发到出链路,交换机自身对子网中的主机和路由器是透明的,这就是说,某主机/路由器向另一个主机/路由器寻址一个帧,顺利地将该帧发送进局域网,并不知道某交换机将会接收该帧并将它转发到另一个节点。这些帧到达该交换机的任何输出接口之一的速率可能暂时会超过该接口的链路容量。为了解决这个问题,交换机输出接口设有缓存,这非常类似于路由器接口为数据报设有缓存。 交换机转发和过滤 过滤(filtering)是决定一个帧应该转发到某个接口还是应当将其丢弃的交换机功能。 转发(forwarcling)是决定一 个帧应该被导向哪个接口,并把该帧移动到那些接口的交换机功能。交换机的过滤和转发借助于交换机表(switch table)完成。该交换机表包含某局域网上某些主机和路由器的但不必是全部的表项。 假定目的地址为 DD-DD-DD-DD-DD-DD 的帧从交换机接口 x 到达。交换机用 MAC 地址 DD-DD-DD-DD-DD-DD 索引它的表。有 3 种可能的情况: 表中没有对于 DD-DD-DD-DD-DD-DD 的表项。在这种情况下,交换机向除接口 x 外的所有接口前面的输出缓存转发该帧的副本。换言之,如果没有对于目的地址的表项,交换机广播该帧。 表中有一个表项将 DD-DD-DD-DD-DD-DD 与接口 x 联系起来。在这种情况下,该帧从包括适配器 DD-DD-DD-DD-DD- DD 的局域网网段到来。无须将该帧转发到任何其他接口,交换机通过丢弃该帧执行过滤功能即可。 表中有一个表项将 DD-DD-DD-DD-DD-DD 与接口 y!=x 联系起来。在这种情况下,该帧需要被转发到与接口 y 相连的局域网网段。交换机通过将该帧放到接口 y 前面的输出缓存完成转发功能。 自学习 交换机表初始为空。 对于在每个接口接收到的每个入帧,该交换机在其表中存储:1.在该帧源地址字段中的 MAC 地址;2 该帧到达的接口;3 当前时间。交换机以这种方式在它的表中记录了发送节点所在的局域网网段。如果在局域网上的每个主机最终都发送了一个帧,则每个主机最终将在这张表中留有记录。 如果在一段时间(称为老化期(aging time))后,交换机没有接收到以该地址作为源地址的帧,就在表中删除这个地址。以这种方式,如果一台 PC 被另一台 PC (具有不同的适配器)代替,原来 PC 的 MAC 地址将最终从该交换机表中被清除掉。 交换机是即插即用设备(plug-and-play device),因为它们不需要网络管理员或用户的干预。要安装交换机的网络管理员除了将局域网网段与交换机的接口相连外,不需要做其他任何事。管理员在安装交换机或者当某主机从局域网网段之一被去除时,他没有必要配置交换机表。交换机也是双工的,这意味着任何交换机接口能够同时发送和接收。 链路层交换机的性质 消除碰撞。在使用交换机(不使用集线器)构建的局域网中,没有因碰撞而浪费的带宽!交换机缓存帧并且决不会在网段上同时传输多于一个帧。就像使用路由器一样,交换机的最大聚合带宽是该交换机所有接口速率之和。因此,交换机提供了比使用广播链路的局域网高得多的性能改善。 异质的链路。交换机将链路彼此隔离,因此局域网中的不同链路能够以不同的速率运行并且能够在不同的媒体上运行。 管理。除了提供强化的安全性交换机也易于进行网络管理。检测流量,检测问题发生。 交换机和路由器比较 交换机是第二层的分组交换机,而路由器是第三层的分组交换机 交换机是即插即用的,这是世界上所有超负荷工作的网络管理员都喜爱的特性。交换机还能够具有相对高的分组过滤和转发速率,交换机必须处理高至第二层的帧,而路由器必须处理高至第三层的数据报。在另一方面,为了防止广播帧的循环,交换网络的活跃拓扑限制为一棵生成树。另外,一个大型交换网络将要求在主机和路由器中有大的 ARP 表,这将生成可观的 ARP 流量和处理量。而且,交换机对于广播风暴并不提供任何保护措施,即如果某主机出了故障并传输出没完没了的以太网广播帧流,该交换机将转发所有这些帧使得整个以太网的崩溃。 因为网络寻址通常是分层次的(不像 MAC 寻址那样是扁平的),即使当网络中存在冗余路径时,分组通常也不会通过路由器循环。(然而,当路由器表被误配置时,分组可能循环;IP 用一个特殊的报文首部字段来限制循环。)所以,分组就不会被限制到一棵生成树上,并可以使用源和目的地之间的最佳路径。因为路由器没有生成树限制,所以它们允许以丰富的拓扑结构构建因特网,例如包括欧洲和北美之间的多条活跃链路。路由器的另一个特色是它们对第二层的广播风暴提供了防火墙保护。尽管也许路由器最重要的缺点就是它们不是即插即用的,即路由器和连接到它们的主机都需要人为地配置 IP 地址 C 而且路由器对每个分组的处理时间通常比交换机更长,因为它们必须处理高达第三层的字段。 通常,由几百台主机组成的小网络通常有几个局域网网段。对于这些小网络、交换机就足够了,因为它们不要求 IP 地址的任何配置就能使流量局部化并增加总计吞吐量。但是在由几千台主机组成的更大网络中,通常在网络中(除了交换机之外)还包括路由器。路由器提供了更健壮的流量隔离方式和对广播风暴的控制,并在网络的主机之间使用更智能的路由。 虚拟局域网 支持 VLAN 的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网。在一个 VLAN 内的主机彼此通信,仿佛它们与交换机连接。在一个基于端口的 VLAN 中,交换机的端口(接口)由网络管理员划分为组。每个组构成一个 VLAN,在每个 VLAN 中的端口形成一个广播域。 链路虚拟化:网络化作链路层 多协议标签交换 与电路交换的电话网不同、MPLS 客观上讲是一种分组交换的虚电路网络。它们有自己的分组格式和转发行为。因此,从教学法 的观点看,有关 MPLS 的讨论既适合放在网络层的学习中、也适合放在链路层的学习中。然而,从因特网的观点看,我们能够认为 MPLS 像电话网和交换以太网一样,作为为 IP 设备提供互联服务的链路层技术。 数据中心网络 每个数据中心都容纳了数万至数十万台主机,并且同时支持着很多不同的云应用。数据中心都有自己的数据中心网络这些数据中心网络将其内部主机彼此互联并与因特网中的数据中心互联。 数据中心网络支持两种类型的流量:在外部客户与内部主机之间流动的流量,以及内部主机之间流动的流量。为了处理外部客户与内部主机之间流动的流量,数据中心网络包括了一台或者多台边界路由器(border router), 它们将数据中心网络与公共因特网相连 数据中心网络因此需要将所有机架彼此互联,并将机架与边界路巾器连接。 负载均衡 一个大型的数据中心通常会有几台负载均衡器,每台服务于一组特定的云应用。由于负载均衡器基于分组的目的端口号(第四层)以及目的 IP 地址做决策,因此它们常被称为“第四层交换机”。 等级体系结构 对于仅有数于台主机的小型数据中心,一个简单的网络也许就足够了。这种简单网络由一台边界路由器、一台负载均衡器和几十个机架组成,这些机架由单一以太网交换机进行互联。但是当主机规模扩展到几万至几十万的时候,数据中心通常应用路由器和交换机等级结构。 在该等级结构的顶端,边界路由器与接入路由器相连。在每台接入路由器下面,有 3 层交换机。每台接入路由器与一台第一层交换机相连,每台第一层交换机与多台第二层交换机以及一台负载均衡器相连。每台第二层交换机又通过机架的 TOR 交换机(第三层交换机)与多个机架相连。所有链路通常使用以太网作为链路层和物理层协议,并混合使用铜缆和光缆。通过这种等级式设计,可以将数据中心扩展到几十万台主机的规模。 数据中心网络的发展趋势 全连接拓扑 模块化数据中心 回顾:Web 页面请求的历程 一名学生 Bob 将他的便携机与学校的以太网交换机相连,下载一个 Web 页面(比如说 www.google.com主页)。 Bob 便携机上的操作系统生成一个 DHCP 请求报文,并将这个报文放入具有目的端口 67(DHCP 服务器)和源端口 68(DHCP 客户)的 UDP 报文段,该 UDP 报文段则被放置在一个具有广播 IP 目的地址(255.255.255.255)和源 IP 地址 0.0.0.0 的 IP 数据报中(4.3.I 节),因为 Bob 的便携机还没有一个 IP 地址。 包含 DHCP 请求报文的 IP 数据报则被放置在以太网帧中。该以太网帧具有目的 MAC 地址 FF:FF:FF:FF:FF:FF,使该帧将广播到与交换机连接的所有设备;该帧的源 MAC 地址是 Bob 便携机的 MAC 地址 00:I6:D3:23:68:8A。 包含 DHCP 请求的广播以太网帧是第一个由 Bob 便携机发送到以太网交换机的帧。该交换机在所有的出端口广播入帧,包括连接到路由器的端口。 路由器在它的具有 MAC 地址 00:22:6B:45:1F 的接口接收到该广播以太网帧,该帧中包含 DHCP 请求、并且从该以太网帧中抽取出 IP 数据报。该数据报的广播 IP 目的地址指示了这个 IP 数据报应当由在该节点的高层协议处理,因此该数据报的载荷(一个 UDP 报文段)被分解向上到达 UDP,DHCP 请求报文从此 UDP 报文段中抽取出来。此时 DHCP 服务器有了 DHCP 请求报文。 我们假设运行在路由器中的 DHCP 服务器能够以 CIDR 块 68.85.2.0/24 分配 IP 地址)所以本例中,在学校内使用的所有 IP 地址都在 Comcast 的地址块中。我们假设 DHCP 服务器分配地址 68.85.2.101 给 Bob 的便携机。DHCP 服务器生成包含这个 IP 地址以及 DNS 服务器的 IP 地址(68.87.71.226)、默认网关路由器的 IP 地址(68.85.2.l)。和子网块(68.85.2.0/24)(等价为“网络掩码")的一个 DHCP ACK 报文该 DHCP 报文被放入一个 UDP 报文段中,UDP 报文段被放人一个 IP 数据报中,IP 数据报再被放入一个以太网帧中。这个以太网帧的源 MAC 地址是路由器连到归属网络时接口的 MAC 地址址(00:22:6B:45:1F:1B),目的 MAC 地址是 Bob 便携机的 MAC 地址 包含 DHCP ACK 的以太网帧由路由器发送给交换机。因为交换机是自学习的、并且先前从 Bob 便携机收到(包含 DHCP 请求的)以太网帧,所以该交换机知道寻址到 00:16:03:23:68:8A 的帧仅从通向 Bob 便携机的输出端口转发。 Bob 便携机接收到包含 DHCPACK 的以太网帧,从该以太网帧中抽取 IP 数据报,从 IP 数据报中抽取 UDP 报文段,从 UDP 报文段抽取 DHCPACK 报文。Bob 的 DHCP 客户则记录下它的 IP 地址和它的 DNS 服务器的 IP 地址。它还在其 IP 转发表中安装默认网关的地址。Bob 便携机将向该默认网关发送目的地址为其子网 68.85.2.0/24 以外的所有数据报。此时,Bob 便携机已经初始化好它的网络组件,并准备开始处理 Web 网页获取。 Bob 便携机上的操作系统因此生成一个 DNS 查询报文,将字符串 www.google.com 放入 DNS 报文的问题段中。该 DNS 报文则放置在一个具有 53 号(DNS 服务器)目的端口的 UDP 报文段中。该 UDP 报文段则被放入具有 IP 目的地址 68.87.71.226 和源 IP 地址 68.85.2.101 的 IP 数据报中。 Bob 便携机则将包含 DNS 请求报文的数据报放入一个以太网帧中.该帧将发送(在链路层寻址)到 Bob 学校网络中的网关路由器。然而,即使 Bob 便携机经过上述第 5 步中的 DHCPACK 报文知道了学校网关路由器的 IP 地址(68.85.2.1),但仍不知道该网关路由器的 MAC 地址。为了获得该网关路由器的 MAC 地址,Bob 便携机将需要使用 ARP 协议。 Bob 便携机生成一个具有目的 lP 地址 68.85.2.1(默认网关)的 ARP 查询报文,将该 ARP 报文放置在一个具有广播目的地址(FF:FF:FF:FF:FF:FF)的以太网帧中,并向交换机发送该以太网帧,交换机将该帧交付给所有连接的设备,包括网关路由器。 网关路由器在通往学校网络的接口上接收到包含该 ARP 查询报文的帧,发现在 ARP 报文中目标 IP 地址 68.85.2.1 匹配其接口的 IP 地址。网关路由器因此准备一个 ARP 回答,指示它的 MAC 地址 00:22:6B:45:1F:1B 对应 IP 地址 68.85.2.1~它将 ARP 回答放在一个以太网帧中,其目的地址为 00:16:D3:23:68:8A(Bob 便携机),并向交换机发送该帧,再由交换机将帧交付给 Bob 便携机。 Bob 便携机接收包含 ARP 回答报文的帧并从 ARP 回答报文中抽取网关路由器的 MAC 地址(00:22:6B:45:1F:1B) Bob 便携机现在(最终!)能够使包含 DNS 查询的以太网帧寻址到网关路由器的 MAC 地址。注意到在该帧中的 IP 数据报具有 IP 目的地址 68.87.71.226(DNS 服务器),而该帧具有目的地址 00:22:68:45:1F:1B(网关路由器)。Bob 便携机向交换机发送该帧,交换机将该帧交付给网关路由器。 网关路由器接收该帧并抽取包含 DNS 查询的 IP 数据报。路由器查找该数据报的目的地址(68.87.71.226),并根据其转发表决定该数据报应当发送到 Comcast 网络中最左边的路由器 IP 数据报放置在链路层帧中,该链路适合将学校路由器连接到最左边 Comcast 路由器,并且该帧经这条链路发送。 在 Comcast 网络中最左边的路由器接收到该帧,抽取 IP 数据报,检查该数据报的目的地址(68.87.71.226),并根据其转发表确定出接口,经过该接口朝着 DNS 服务器转发数据报,而转发表己根据 Comcast 的域内协议(如 RIP、OSPF 或 IS-IS)以及因特网的域间协议 BGP 所填写。 最终包含 DNS 查询的 IP 数据报到达了 DNS 服务器。DNS 服务器抽取出 DNS 查询报文,在它的 DNS 数据库中查找名字www.google.com,找到包含对应www.google.com的IP地址(64.233.169.105)的DNS源记录,前面讲过这种缓存数据源于google.com的权威DNS服务器。该DNS服务器形成了一个包含这种主机名到IP地址映射的DNS回答报文,将该DNS回答报文放入UDP报文段中,该报文段放入寻址到Bob便携机(68.85.2.101)的IP数据报中。该数据报将通过Comcast网络反向转发到学校的路由器,并从这里经过以太网交换机到Bob便携机。 Bob 便携机从 DNS 报文抽取出服务器www.google.com的IP地址。最终,在大量工作后,Bob便携机此时准备接触www.google.com服务器! 既然 Bob 便携机有了www.google.com的IP地址,它能够生成TCP套接字(2.7节),该套接字将用于向吓叩.google.com发送HTTPGET报文(2.2.3节)。当Bob生成TCP套接字时,在Bob便携机中的TCP必须首先与www.google.com中的TCP执行三次握手。Bob 便携机因此首先生成一个具有目的端口 80(针对 HTTP 的)的 TCP SYN 报文段,将该 TCP 报文段放置在具有目的 1P 地址 64.233.169.105(www.google.com)的IP数据报中,将该数据报放置在MAC地址为00:22:68:45:1F:1B(网关路由器)的帧中,并向交换机发送该帧. 在学校网络、Comcast 网络和谷歌网络中的路由器朝着 www.google.com 转发包含 TCP SYN 的数据报,使用每台路由器中的转发表,如前面步骤 14~16 那样。前面讲过支配分组经 Comcast 和谷歌网络之间域间链路转发的路由器转发表项,是由 BGP 协议决定的 最终,包含 TCPSYN 的数据报到达www.googole.com0从数据报抽取出TCPSYN报文并分解到与端口80相联系的欢迎套接字。对于谷歌HTTP服务器和Bob便携机之间的TCP连接生成一个连接套接字。产生一个TCP SYN ACK 报文段,将其放入向 Bob 便携机寻址的一个数据报中,最后放入链路层帧中,该链路适合将www.google.com连接到其第一跳路由器。 包含 TCP SYN ACK 报文段的数据报通过谷歌、Comcast 和学校网络,最终到达 Bob 便携机的以太网卡,数据报在操作系统中分解到步骤 18 生成的 TCP 套接字,从而进入连接状态。 借助于 Bob 便携机上的套接字,现在(终于!)准备向www.googJe.com发送字节HTTP GET 报文则写入套接字,其中 GET 报文成为一个 TCP 报文段的载荷。该 TCP 报文段放置进一个数据报中,并交付到www.google.com,如前面步骤18-20所述。 在www.google.com的HTTP服务器从TCP套接字读取HTTP GET 报文,生成一个 HTTP 响应报文,将请求的 Web 页内容放入 HTTP 响应体中,并将报文发送了,Bob 的浏览器生成包含要获取的 URL 的 HTTPGET 报文进 TCP 套接字中。 包含 HTTP 回答报文的数据报通过谷歌、Comcast 和学校网络转发,到达 Bob 便携机。Bob 的 Web 浏览器程序从套接字读取 HTTP 响应,从 HTTP 响应体中抽取 Web 网页的 html, 并最终(终于!)显示了 Web 网页。

2021 Jun 18 · 5 min

计算机网络自顶向下方法::网络层::控制平面

概述 转发表和流表计算、维护和安装的两种方法 每路由器控制。每台路由器中都包含转发和路由选择功能。每台路由器有一个路由选择组件,用于与其他路由器中的路由选择组件通信,以计算其转发表的值。这种每路由器控制的方法在因特网中已经使用了几十年。OSPF 和 BGP 协议都是基于这种每路由器的方法进行控制的。 逻辑集中式控制。通用的"匹配加动作“抽象允许执行传统的 IP 转发以及其他功能(负载共享、防火墙功能和 NAT) 的丰富集合,而这些功能先前是在单独的中间盒中实现的。该控制器经一种定义良好的协议与每台路由器中的一个控制代理(CA) 进行交互,以配置和管理该路由器的转发表。CA 一般具有最少的功能,其任务是与控制器通信并且按控制器命令行事。这些 CA 既不能直接相互交互,也不能主动参与计算转发表。这是每路由器控制和逻辑集中式控制之间的关键差异。 “逻辑集中式"控制意味着就像路由选择控制服务位于单一的集中服务点那样获取它们,即使该服务出于容错和性能扩展性的原因,很可能经由多个服务器实现。 SDN 采用了逻辑集中式控制器的概念,而这种方法在生产部署中得到了越来越多的应用。 路由选择算法 其目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径(等价于路由)。通常,一条好路径指具有最低开销的路径。 第一种分类方式:根据该算法是集中式还是分散式来划分 集中式路由选择算法 用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径。具有全局状态信息的算法常被称作链路状态(Link State,LS) 算法,因为该算法必须知道网络中每条链路的开销。 分散式路由选择算法 路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息。相反,每个节点仅有与其直接相连链路的开销知识即可开始工作。然后,通过迭代计算过程以及与相邻节点的信息交换,一个节点逐渐计算出到达某目的节点或一组目的节点的最低开销路径。 第二种分类方式:根据算法是静态的还是动态的进行分类 静态路由选择算法 路由随时间的变化非常缓慢,通常是人工进行调整如人为手工编辑一条链路开销) 动态路由选择算法 随着网络流量负载或拓扑发生变化而改变路由选择路径。一个动态算法可周期性地运行或直接响应拓扑或链路开销的变化而运行。虽然动态算法易于对网络的变化做出反应,但也更容易受诸如路由选择循环、路由振荡之类问题的影响。 第三种分类方式:根据它是负载敏感的还是负载迟钝的进行划分 负载敏感算法 链路开销会动态地变化以反映出底层链路的当前拥塞水平。如果当前拥塞的一条链路与高开销相联系,则路由选择算法趋向于绕开该拥塞链路来选择路由。 负载迟钝 当今的因特网路由选择算法(如 RIP、OSPF 和 BGP)都是负载迟钝的(load-insensitive),因为某条链路的开销不明确地反映其当前或最近的拥塞水平。 链路状态路由选择算法 在链路状态算法中,网络拓扑和所有的链路开销都是已知的。实践中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的,其中每个链路状态分组包含它所连接的链路的标识和开销。在实践中,这经常由链路状态广播算法来完成。节点广播的结果是所有节点都具有该网络的统一、完整的视图。于是每个节点都能够像其他节点一样,运行 LS 算法并计算出相同的最低开销路径集合。 距离向量路由选择算法 距离向量(Distance-Vector,DV) 算法是一种迭代的、异步的和分布式的算法。说它是分布式的,是因为每个节点都要从一个或多个直接相连邻居接收某些信息,执行计算,然后将其计算结果分发给邻居。说它是迭代的,是因为此过程一直要持续到邻居之间无更多信息要交换为止。说它是异步的,是因为它不要求所有节点相互之间步伐一致地操作。 链路开销改变与链路故障 当一个运行 DV 算法的节点检测到从它自己到邻居的链路开销发生变化时,它就更新其距离向量,并且如果最低开销路径的开销发生了变化,向邻居通知其新的距离向量。 LS 与 DV 路由选择算法的比较 报文复杂性。我们已经看到 LS 算法要求每个节点都知道网络中每条链路的开销。这就要求要发送 O(|N||E|)个报文 。而且无论何时一条链路的开销改变时,必须向所有节点发送新的链路开销。DV 算法要求在每次迭代时,在两个直接相连邻居之间交换报文。我们已经看到,算法收敛所需时间依赖于许多因素。当链路开销改变时,DV 算法仅当在新的链路开销导致与该链路相连节点的最低开销路径发生改变时,才传播已改变的链路开销。 收敛速度。我们已经看到 LS 算法的实现是一个要求 O(|N||E|)个报文的 O(|N|^2)算法。DV 算法收敛较慢,且在收敛时会遇到路由选择环路。DV 算法还会遭遇无穷计数的问题。 健壮性。对于 LS 算法,路由器能够向其连接的链路广播不正确的开销。作为 LS 广播的一部分,一个节点也可损坏或丢弃它收到的任何区广播分组。但是一个 LS 节点仅计算自己的转发表;其他节点也自行执行类似的计算。这就意味着在 LS 算法下,路由计算在某种程度上是分离的,提供了一定程度的健壮性。在 DV 算法下,一个节点可向任意或所有目的节点通告其不正确的最低开销路径。更一般地,我们会注意到每次迭代时,在 DV 算法中一个节点的计算会传递给它的邻居,然后在下次迭代时再间接地传递给邻居的邻居。在此情况下,DV 算法中一个不正确的节点计算值会扩散到整个网络 。 因特网中自治系统内部的路由选择:OSPF 规模。随着路由器数目变得很大,涉及路由选择信息的通信、计算和存储的开销将高得不可实现。当今的因特网由数亿台主机组成。在这些主机中存储的路由选择信息显然需要巨大容量的内存。在所有路由器之间广播连通性和链路开销更新所要求的负担将是 巨大的!在如此大量的路由器中迭代的距离向量算法将肯定永远无法收敛!显然,必须采取一些措施以减少像因特网这种大型网络中的路由计算的复杂性 。 管理自治。因特网是 ISP 的网络,其中每个 ISP 都有它自己的路由器网络。ISP 通常希望按自己的意愿运行路由器,或对外部隐藏其网络的内部组织面貌。在理想情况下,一个组织应当能够按自己的愿望运行和管理其网络,还要能将其网络与其他外部网络连接起来。 在相同 AS 中的路由器都运行相同的路由选择算法并且有彼此的信息。在一个自治系统内运行的路由选择算法叫作自治系统内部路由选择协议。 开放最短路优先 (OSPF) OSPF 路由选择及其关系密切的协议 IS-IS 都被广泛用千因特网的 AS 内部路由选择。 OSPF 是一种链路状态协议,它使用洪泛链路状态信息和 Dijkstra 最低开销路径算法。使用 OSPF, 一台路由器构建了一 幅关于整个自治系统的完整拓扑图(即一幅图)。于是,每台路由器在本地运行 Dijkstra 的最短路径算法,以确定一个以自身为根节点到所有子网的最短路径树。各条链路开销是由网络管理员配置的管理员也许会选择将所有链路开销设为 1, 因而实现了最少跳数路由选择,或者可能会选择将链路权值按与链路容量成反比来设置,从而不鼓励流量使用低带宽链路。OSPF 不强制使用设置链路权值的策略(那是网络管理员的任务),而是提供了一种机制(协议),为给定链路权值集合确定最低开销路径的路由选择。 使用 OSPF 时,路由器向自治系统内所有其他路由器广播路由选择信息,而不仅仅是向其相邻路由器广播。每当一条链路的状态发生变化时(如开销的变化或连接/中断状态的变化),路由器就会广播链路状态信息。即使链路状态未发生变化,它也要周期性地(至少每隔 30 min 一次)广播链路状态。OSPF 协议还要检查链路正在运行(通过向相连的邻居发送 HELLO 报文 ),并允许 OSPF 路由器获得相邻路由器的网络范围链路状态的数据库 。 优点 安全。能够鉴别 OSPF 路由器之间的交换(如链路状态更新)。 多条相同开销的路径。当到达某目的地的多条路径具有相同的开销时,OSPF 允许使用多条路径。 对单播与多播路由选择的综合支持。 支持在单个 AS 中的层次结构。一个 OSPF 自治系统能够层次化地配置多个区域每个区域都运行自己的 OSPF 链路状态路由选择算法,区域内的每台路由器都向该区域内的所有其他路由器广播其链路状态。 ISP 之间的路由选择:BGP 在因特网中,所有的 AS 运行相同的 AS 间路由选择协议,称为边界网关协议(Broder Gateway Protocol, BGP)。正是这个协议将因特网中数以千计的 ISP 黏合起来。 BGP 的作用 从邻居 AS 荻得前缀的可达性信息。特别是,BGP 允许每个子网向因特网的其余部分通告它的存在。一个子网高声宣布“我存在,我在这里”,而 BGP 确保在因特网中的所有 AS 知道该子网。如果没有 BGP 的话,每个子网将是隔离的孤岛,即它们孤独地存在,不为因特网其余部分所知和所达。 确定到该前缀的“最好的“路由。一台路由器可能知道两条或更多条到特定前缀的不同路由。为了确定最好的路由,该路由器将本地运行一个 BGP 路由选择过程(使用它经过相邻的路由器获得的前缀可达性信息)。该最好的路由将基于策略以及可达性信息来确定 。 通告 BGP 路由信息 对于每个 AS, 每台路由器要么是一台网关路由器(gateway router)要么是一台内部路由器(internal router)。网关路由器是一台位于 AS 边缘的路由器,它直接连接到在其他 AS 中的一台或多台路由器。内部路由器仅连接在它自己 AS 中的主机和路由器 。 在 BGP 中,每对路由器通过使用 179 端口的半永久 TCP 连接交换路由选择信息。每条直接连接以及所有通过该连接发送的 BGP 报文,称为 BGP 连接 (BGP connection)。此外,跨越两个 AS 的 BGP 连接称为外部 BGP (eBGP) 连接,而在相同 AS 中的两台路由器之间的 BGP 会话称为内部 BGP (iBGP) 连接 。在真实的网络中,从某个给定的路由器到某个给定的目的地可能有多条不同的路径,每条通过了不同的 AS 序列 。 确定最好的路由 当路由器通过 BGP 连接通告前缀时,它在前缀中包括一些 BGP 属性 (BGP attribute)。用 BGP 术语来说,前缀及其属性称为路由 ( route)。两个较为重要的属性是 AS-PATH 和 NEXT-HOP。AS-PATH 属性包含了通告已经通过的 AS 的列表,如我们在前面的例子中所见。为了生成 AS-PATH 的值,当一个前缀通过某 AS 时,该 AS 将其 ASN 加入 AS-PATH 中的现有列表。 IP 任播 BGP 还常被用于实现 IP 任播(anycast) 服务,该服务通常用于 DNS 中。 动机 在许多分散的不同地理位置,替换不同服务器上的相同内容 让每个用户从最靠近的服务器访问内容。 CDN 使用 IP 任波的方式 在 IP 任播配置阶段,CDN 公司为它的多台服务器指派相同的 IP 地址,并且使用标准的 BGP 从这些服务器的每台来通告该 IP 地址。当某台 BGP 路由器收到对于该 IP 地址的多个路由通告,它将这些通告处理为对相同的物理位置提供不同的路径当配置其路由选择表时,每台路由器将本地化地使用 BGP 路由选择算法来挑选到该 IP 地址的最好的路由。 路由选择策略 在路由选择算法中,实际上首先根据本地偏好属性选择路由,本地偏好值由本地 AS 的策略所确定。 为什么会有不同的 AS 间和 AS 内部路由选择协议? 策略。在 AS 之间,策略问题起主导作用。一个给定 AS 产生的流量不能穿过另一个特定的 AS, 这可能非常重要。类似地,一个给定 AS 也许想很好地控制它承栽的其他 AS 之间穿越的流量。我们已看到,BGP 承栽了路径属性,并提供路由选择信息的受控分布,以便能做出这种基于策略的路由选择决策。在一个 AS 内部,一切都是在相同的管理控制名义下进行的,因此策略问题在 AS 内部选择路由中起着微不足道的作用。 规模。扩展一个路由选择算法及其数据结构以处理到大量网络或大量网络之间的路由选择的这种能力,是 AS 间路由选择的一个关键问题。在一个 AS 内,可扩展性不是关注的焦点。首先,如果单个 ISP 变得太大时,总是能将其分成两个 AS, 并在这两个新的 AS 之间执行 AS 间路由选择。 性能。由于 AS 间路由选择是面向策略的,因此所用路由的质量通常是次要关心的问题。 我们的确看到了在 AS 之间,甚至没有与路由相关的开销概念。然而在一个 AS 内部,这种对策略的关心就不重要了,可以使路由选择更多地关注一条路由实现的性能级别。 SDN 控制平面 SDN 体系结构具有 4 个关键特征 基于流的转发:SDN 控制的交换机的分组转发工作,能够基于运输层、 网络层或链路层首部中任意数量的首部字段值进行。 数据平面与控制平面分离:数据平面由网络交换机组成,交换机是相对简单(但快速)的设备,该设备在它们的流表中执行“匹配加动作”的规则。控制平面由服务器以及决定和管理交换机流表的软件组成。 网络控制功能:位于数据平面交换机外部。然而,与传统的路由器不同,这个软件在服务器上执行,该服务器与网络交换机截然分开且与之远离。控制平面自身由两个组件组成: 一个 SDN 控制器, 以及若干网络控制应用程序。控制器维护准确的网络状态信息机和主机的状态;为运行在控制平面中的网络控制应用程序提供这些信息;提供方法,这些应用程序通过这些方法能够监视、 编程和控制下面的网络设备。 可编程的网络。通过运行在控制平面中的网络控制应用程序、该网络是可编程的。这些应用程序代表了控制平面的“智力”,使用了由 SDN 控制器提供的 API 来定义和控制网络设备中的数据平面。 SDN 控制平面:SDN 控制器和 SDN 网络控制应用程序 通信层:SDN 控制器和受控网络设备之间的通信。显然,如果 SDN 控制器要控制远程 SDN 使能的交换机、主机或其他设备的运行,需要一个协议来传送控制器与这些设备之间的信息。 网络范围状态管理层。由 SDN 控制平面所做出的最终控制决定换机的流表以取得所希望的端到端转发,实现负载均衡,或实现一种特定的防火墙能力,将要求控制器具有有关网络的主机、链路、交换机和其他 SDN 控制设备的最新状态信息。 对于网络控制应用程序层的接口。控制器通过它的“北向“接口与网络控制应用程序交互。该 API 允许网络控制应用程序在状态管理层之间读/写网络状态和流表。当状态改变事件出现时,应用程序能够注册进行通告。可以提供不同类型的 API, 我们将看到两种流行 SDN 控制器使用 REST 请求响应接口与它们的应用程序进行通信。 OpenFlow 协议 OpenFlow 协议运行在 SDN 控制器和 SDN 控制的交换机或其他实现 OpenFlow API 的设备之间。OpenFlow 协议运行在 TCP 之上,使用 6653 的默认端口号。从控制器到受控交换机流动的重要报文有下列这些: 配置。该报文允许控制器查询并设置交换机的配置参数 。 修改状态。该报文由控制器所使用,以增加/删除或修改交换机流表中的表项,且设置交换机端口特性。 读状态。该报文被控制器用于从交换机的流表和端口收集统计数据和计数器值。 发送分组。该报文被控制器用于在受控交换机从特定的端口发送出 一个特定的报文。 流删除。该报文通知控制器已删除一个流表项,例如由于超时,或作为收到“修改状态"报文的结果。 端口状态。交换机用该报文向控制器通知端口状态的变化。 分组入。一个分组到达交换机端口,并且不能与任何流表项匹配,那么这个分组将被发送给控制器进行额外处理。匹配的分组也被发送给控制器,作为匹配时所采取的一个动作。“分组入“报文被用于将分组发送给控制器。 ICMP: 因特网控制报文协议 ICMP 被主机和路由器用来彼此沟通网络层的信息。ICMP 最典型的用途是差错报告。 在某个位置,IP 路由器不能找到一条通往 HTTP 请求中所指定的主机的路径、该路由器就会向你的主机生成并发出一个 ICMP 报文以指示该错误。 另一个有趣的 ICMP 报文是源抑制报文。这种报文在实践中很少使用 。其最初目的是执行拥塞控制,即使得拥塞的路由器向一台主机发送一个 ICMP 源抑制报文,以强制该主机减小其发送速率。 网络管理和 SNMP 网络管理框架 管理服务器(managing server)是一个应用程序,通常有人的参与,并运行在网络运营中心 (NOC) 的集中式网络管理工作站上。管理服务器是执行网络管理活动的地方,它控制网络管理信息的收集、处理、分析和/或显示。 被管设备 (managed deyjce) 是网络装备的一部分(包括它的软件),位于被管理的网络中。在一个被管设备中,有几个所谓被管对象 (managed object) 。这些被管对象是被管设备中硬件的实际部分(例如,一块网络接口卡只是一台主机或路由器的一个组件)和用于这些硬件及软件组件的配置参数(例如,像 OSPF 这样的 AS 内部路由选择协议)。 一个被管设备中的每个被管对象的关联信息收集在管理信息库(Management Information Base, MIB) 中,我们将看到这些信息的值可供管理服务器所用 在每个被管设备中还驻留有网络管理代理 (network management agent) ,它是运行在被管设备中的一个进程,该进程与管理服务器通信,在管理服务器的命令和控制下在被管设备中采取本地动作。 网络管理框架的最后组件是网络管理协议 (network management protocol ) 。该协议运行在管理服务器和被管设备之间,允许管理服务器查询被管设备的状态,并经过其代理间接地在这些设备上采取行动。代理能够使用网络管理协议向管理服务器通知异常事件(如组件故障或超过了性能阙值)。重要的是注意到网络管理协议自己不能管理网络。恰恰相反,它为网络管理员提供了一种能力,使他们能够管理网络。 简单网络管理协议 SNMP 是一个应用层协议,用于在管理服务器和代表管理服务器执行的代理之间传递网络管理控制和信息报文。SNMP 最常使用的是请求响应模式,其中 SNMP 管理服务器向 SNMP 代理发送一个请求,代理接收到该请求后,执行某些动作,然后对该请求发送一个回答。请求通常用于查询(检索)或修改(设置)与某被管设备关联的 MIB 对象值。 SNMP 第二个常被使用的是代理向管理服务器发送的一种非请求报文,该报文称为陷阱报文(trap message) 。陷阱报文用于通知管理服务器,一个异常情况(例如一个链路接口启动或关闭)已经导致了 MIB 对象值的改变。

2021 Jun 17 · 3 min

计算机网络自顶向下方法::网络层::数据平面

网络层概述 路由器的数据平面的主要作用是从其输入链路向其输出链路转发数据报;控制平面的主要作用是协调这些本地的每路由器转发动作,使得数据报沿着源和目的地主机之间的路由器路径最终进行端到端传送。 转发和路由选择:数据平面和控制平面 转发:当一个分组到达某路由器的一条输入链路时,该路由器必须将该分组移动到适当的输出链路 路由选择:当分组从发送方流向接收方时,网络层必须决定这些分组所采用的路由或路径。计算这些路径的算法被称为路由选择算法 每台网络路由器中有一个关键元素是它的转发表(forwarding table) 。路由器检查到达分组首部的一个或多个字段值,进而使用这些首部值在其转发表中索引,通过这种方法来转发分组。这些值对应存储在转发表项中的值,指出了该分组将被转发的路由器的输出链路接口。 控制平面:传统的方法 路由选择算法运行在每台路由器中,并且在每台路由器中都包含转发和路由选择两种功能。在一台路由器中的路由选择算法与在其他路由器中的路由选择算法通信,以计算出它的转发表的值。 控制平面:SDN 方法 SDN 方法显示了从路由器物理上分离的另一种方法,远程控制器计算和分发转发表以供每台路由器所使用,路由选择设备仅执行转发。远程控制器可能实现在具有高可靠性和冗余的远程数据中心中,并可能由 ISP 或某些第三方管理。路由器和远程控制器通过交换包含转发表和其他路由选择信息的报文实现通信。 网络服务模型 网络层能提供的某些可能的服务 确保交付。该服务确保分组将最终到达目的地。 具有时延上界的确保交付。该服务不仅确保分组的交付,而且在特定的主机到主机时延上界内(例如在 1OOms 内)交付 。 有序分组交付。该服务确保分组以它们发送的顺序到达目的地。 确保最小带宽。这种网络层服务模仿在发送和接收主机之间一条特定比特率(例如 1Mbps) 的传输链路的行为。只要发送主机以低于特定比特率的速率传输比特(作为分组的组成部分),则所有分组最终会交付到目的主机。 安全性。网络层能够在源加密所有数据报并在目的地解密这些分组,从而对所有运输层报文段提供机密性。 因特网的网络层提供了单一的服务,称为尽力而为服务,使用尽力而为服务,传送的分组既不能保证以它们发送的顺序被接收,也不能保证它们最终交付;既不能保证端到端时延,也不能保证有最小的带宽。尽力而为服务看起来是根本无服务的一种委婉说法,即一个没有向目的地交付分组的网络也符合尽力而为交付服务的定义 路由器工作原理 通用路由器结构 输入端口 它在路由器中执行终结入物理链路的物理层功能 与位于入链路远端的数据链路层交互来执行数据链路层功能 执行查找功能,通过查询转发表决定路由器的输出端口,到达的分组通过路由器的交换结构转发到输出端口 交换结构 交换结构将路由器的输入端口连接到它的输出端口 输出端口 输出端口存储从交换结构接收的分组,并通过执行必要的链路层和物理层功能在输出链路上传输这些分组 路由选择处理器 路由选择处理器执行控制平面功能 在传统的路由器中,它执行路由选择协议,维护路由选择表与关联链路状态信息,并为该路由器计算转发表 在 SDN 路由器中,路由选择处理器负责与远程控制器通信,目的是接收由远程控制器计算的转发表项,并在该路由器的输入端口安装这些表项 输入端口处理和基于目的地转发 输入端口的线路端接功能与链路层处理实现了用于各个输入链路的物理层和链路层。在输入端口中执行的查找对于路由器运行是至关重要的。正是在这个地方,路由器使用转发表来查找输出端口,使得到达的分组能经过交换结构转发到该输出端口。 转发表是由路由选择处理器计算和更新的,或者转发表接收来自远程 SDN 控制器的内容 最长前缀匹配规则 路由器用分组目的地址的前缀(prefix) 与该表中的表项进行匹配;如果存在一个匹配项,则路由器向与该匹配项相关联的链路转发分组,当有多个匹配时,在该表中寻找最长的匹配项,并向与最长前缀匹配相关联的链路接口转发分组。 执行转发表匹配不仅必须要用硬件执行查找,而且需要对大型转发表使用超出简单线性搜索的技术 一旦通过查找确定了某分组的输出端口,则该分组就能够发送进入交换结构。在某些设计中,如果来自其他输入端口的分组当前正在使用该交换结构,一个分组可能会在进入交换结构时被暂时阻塞。因此,一个被阻塞的分组必须要在输入端口处排队,并等待稍后被及时调度以通过交换结构。 其他需要执行的动作 必须出现物理层和链路层处理 必须检查分组的版本号、检验和以及寿命字段,并且重写后两个字段 必须更新用于网络管理的计数器 可选防火墙过滤分组 可选 NAT 重写端口号 交换 交换结构位于一台路由器的核心部位,因为正是通过这种交换结构,分组才能实际地从一个输入端口交换(即转发)到一个输出端口中。交换可以用许多方式完成。 经内存交换。最简单、最早的路由器是传统的计算机,在输入端口与输出端口之间的交换是在 CPU ( 路由选择处理器)的直接控制下完成的。输入与输出端口的功能就像在传统操作系统中的 I/O 设备一样。一个分组到达一个输入端口时。该端口会先通过中断方式向路由选择处理器发出信号。于是,该分组从输入端口处被复制到处理器内存中。路由选择处理器则从其首部中提取目的地址,在转发表中找出适当的输出端口,并将该分组复制到输出端口的缓存中。 经总线交换。在这种方法中、输入端口经一根共享总线将分组直接传送到输出端口。不需要路由选择处理器的干预。 经互联网络交换。克服单一、共享式总线带宽限制的一种方法是,使用一个更复杂的互联网络,例如过去在多处理器计算机体系结构中用来互联多个处理器的网络。纵横交换机是非阻塞的。更为复杂的互联网络使用多级交换元素,以使来自不同输入端口的分组通过交换结构同时朝着相同的输出端口前行。 输出端口处理 输出端口处理取出已经存放在输出端口内存中的分组并将其发送到输出链路上。这包括选择和取出排队的分组进行传输,执行所需的链路层和物理层传输功能。 何时出现排队 输入排队 如果交换结构不能快得(相对于输入线路速度而言)使所有到达分组无时延地通过它传送,在这种情况下,在输入端口也将出现分组排队,因为到达的分组必须加入输入端口队列中,以等待通过交换结构传送到输出端口。 队头阻塞 一个输入队列中的排队分组必须等待通过交换结构发送,因为它被位于线路前部的另一个分组所阻塞,即使这个分组所前往的端口是空闲的。 输出排队 端口的发送速率小于交换机交换分组的速率,排队的分组耗尽了端口的可用内存,将会采取一定策略丢弃排队的分组 弃尾策略,丢弃刚到达排队的分组 删除一个或多个巳排队的分组为新来的分组腾出空间 分组调度 先进先出 调度规则按照分组到达输出链路队列的相同次序来选择分组在链路上传输,如果没有足够的缓存空间来容纳到达的分组,队列的分组丢弃策略则确定该分组是否将被队列中去除其他分组以便为到达的分组腾出空间, 优先权排队 到达输出链路的分组被分类放人输出队列中的优先权类,实践中,网络操作员可以配置一个队列,这样携带网络管理信息的分组获得超过用户流量的优先权,非抢占式优先权排队规则下,一旦分组开始传输,就不能打断。 循环和加权公平排队 其中,到达的分组被分类并在合适的每个类的等待区域排队。于是用循环调度一样,WFQ 调度器也以循环的方式为各个类提供服务,即首先服务第一类,然后第二类,接着第三类,然后重复这种服务模式。 网际协议:IPv4、寻址、 IPv6 及其他 IPv4 数据报格式 版本(号)。这 4 比特规定了数据报的 IP 协议版本。通过查看版本号,路由器能够确定如何解释 IP 数据报的剩余部分 。不同的 IP 版本使用不同的数据报格式。 首部长度。因为一个 IPv4 数据报可包含一些可变数量的选项,故需要用这 4 比特来确定 IP 数据报中载荷实际开始的地方。大多数 IP 数据报不包含选项,所以一般的 IP 数据报具有 20 字节的首部。 服务类型。服务类型(TOS)比特包含在 IPv4 首部中,以便使不同类型的 IP 数据报能相互区别开来 数据报长度。这是 IP 数据报的总长度(首部加上数据),以字节计。因为该字段长为 16 比特,所以 IP 数据报的理论最大长度为 65535 字节。 标识、标志、片偏移。这个字段与所谓 IP 分片有关。 寿命。寿命字段用来确保数据报不会永远(如由于长时间的路由选择环路)在网络中循环。每当一台路由器处理数据报时,该字段 的值减 1。若 TTL 字段减为 0, 则该数据报必须丢弃。 协议。该字段通常仅当一个 IP 数据报到达其最终目的地时才会有用。该字段值指示了 IP 数据报的数据部分应交给哪个特定的运输层协议。 首部检验和,首部检验和用于帮助路由器检测收到的 IP 数据报中的比特错误 源和目的 IP 地址。当某源生成一个数据报时,它在源 IP 字段中插入它的 IP 地址,在目的 IP 地址字段中插入其最终目的地的地址。 选项。选项字段允许 IP 首部被扩展。 数据(有效栽荷)。IP 数据报中的数据字段包含要交付给目的地的运输层报文段 ( TCP 或 UDP)。然而,该数据字段也可承载其他类型的数据,如 ICMP 报文。 IPv4 数据报分片 一个链路层帧能承载的最大数据量叫作最大传送单元(Maximum Transmission Unit, MTU),不同的链路有不同的 MTU 片在其到达目的地运输层以前需要重新组装。 当生成一个数据报时,发送主机在为该数据报设置源和目的地址的同时贴上标识号。发送主机通常将它发送的每个数据报的标识号加 1。当某路由器需要对一个数据报分片时,形成的每个数据报(即片)具有初始数据报的源地址、目的地址与标识号。当目的地从同一发送主机收到一系列数据报时,它能够检查数据报的标识号以确定哪些数据报实际上是同一较大数据报的片。为了让目的主机绝对地相信它已收到了初始数据报的最后一个片,最后一个片的标志比特被设为 0、而所有其他片的标志比特被设为 1。为了让目的主机确定是否丢失了一个片(且能按正础的顺序重新组装片),使用偏移字段指定该片应放在初始 IP 数据报的哪个位置。 IPv4 编址 一台主机通常只有一条链路连接到网络;当主机中的 IP 想发送一个数据报时,它就在该链路上发送。主机与物理链路之间的边界叫作接口(interface)。 因为路由器的任务是从链路上接收数据报并从某些其他链路转发出去,路由器必须拥有两条或更多条链路与它连接。路由器与它的任意一条链路之间的边界也叫作接口。一台路由器因此有多个接口.每个接口有其链路。因为每台主机与路由器都能发送和接收 IP 数据报,IP 要求每台主机和路由器接口拥有自己的 IP 地址。因此、从技术上讲,一个 IP 地址与一个接口相关联,而不是与包括该接口的主机或路由器相关联。 每个 IP 地址长度为 32 比特(等价为 4 字节),因此总共有 2^32 大约 40 亿个可能的 IP 地址 。 在全球因特网中的每台主机和路由器上的每个接口,都必须有一个全球唯一的 IP 地址,这些地址不能随意地自由选择。一个接口的 IP 地址的一部分需要由其连接的子网来决定。 IP 编址为这个子网分配一个地址 223.1.1.0/24, 其中的 /24 记法,有时称为子网掩码。指示 32 比特中的最左侧 24 比特定义了子网地址。任何其他要连到 223.1.1.0/24 网络的主机都要求其地址具有 223.1.1.xxx 的形式。 因特网的地址分配策略被称为无类别域间路由选择(Classless Interdon1ain Routing,CIDR),在这种情况下,该组织内部的设备的 IP 地址将共享共同的前缀。因特网的 BGP 路由选择协议时。将看到该组织网络外部的路由器仅考虑前面的前缀比特 x。这就是说,当该组织外部的一台路由器转发一个数据报,且该数据报的目的地址位于该组织的内部时,仅需要考虑该地址的前面 x 比特,这相当大地减少了在这些路由器中转发表的长度,因为形式为 a.b.c.d/x 的单一表项足以将数据报转发到该组织内的任何目的地。这种使用单个网络前缀通告多个网络的能力通常称为地址聚合(address aggregation), 也称为路由聚合(route-aggregation) 或路由摘要(route summarization)。 在 CIDR 被采用之前,IP 地址的网络部分被限制为长度为 8、16 或 24 比特,这是一种称为分类编址 (classful addressing) 的编址方案,这是因为具有 8、16 和 24 比特子网地址的子网分别被称为 A、B 和 C 类网络。 获取一块地址 为了获取一块 IP 地址用于一个组织的子网内,某网络管理员也许首先会与他的 ISP 联系,该 ISP 可能会从已分给它的更大地址块中提供一些地址。例如,该 ISP 也许自己已被分配了地址块 200.23.16.0/20。该 ISP 可以依次将该地址块分成 8 个长度相等的连续地址块,为本 ISP 支持的最多达 8 个组织中的一个分配这些地址块中的一块。 ISP 的地址来源于 ICANN 组织,它还负责 管理 DNS 根服务器。 获取主机地址:动态主机配置协议 主机地址也能手动配置,但是这项任务目前更多的是使用动态主机配置协议。DHCP 允许主机自动获取(被分配)一个 IP 地址。网络管理员能够配置 DHCP, 以使某给定主机每次与网络连接时能得到一个相同的 IP 地址,或者某主机将被分配一个临时的 IP 地址(temporary IP address), 每次与网络连接时该地址也许是不同的。除了主机 IP 地址分配外,DHCP 还允许一台主机得知其他信息,例如它的子网掩码、它的第一跳路由器地址(常称为默认网关)与它的本地 DNS 服务器的地址。由于 DHCP 具有将主机连接进一个网络的网络相关方面的自动能力,故它又常被称为即插即用协议(plug-and-play protocol) 或零配置(zeroconf)协议。 DHCP 是一个客户-服务器协议 主机加入子网的过程 DHCP 服务器发现:一台新到达的主机的首要任务是发现一个要与其交互的 DHCP 服务器这可通过使用 DHCP 发现报文 ( DHCP discover tnessage) 来完成,DHCP 客户生成包含 DHCP 发现报文的 IP 数据报,其中使用广播目的地址 255.255.255.255 并且使用“本主机”源 IP 地址 0.0.0.0,DHCP 客户将该 IP 数据报传递给链路层,链路层然后将该帧广播到所有与该子网连接的节点。 DHCP 服务器提供:DHCP 服务楛收到 一个 DHCP 发现报文时,用 DHCP 提供报文 (DHCP offer message) 向客户做出响应,该报文向该子网的所有节点广播,仍然使用 IP 广播地址 255.255.255.255。因为在子网中可能存在几个 DHCP 服务器,该客户也许会发现它处于能在几个提供者之间进行选择的优越位置。每台服务器提供的报文包含有收到的发现报文的事务 ID 、向客户推荐的 IP 地址、网络掩码以及 IP 地址租用期, 即 IP 地址有效的时间量。服务器租用期通常设置为几小时或几天。 DHCP 请求。新到达的客户从一个或多个服务器提供中选择一个,并向选中的服务器提供用 DHCP 请求报文 (DHCP request message) 进行响应,回显配置的参数。 DHCP ACK。服务器用 DHCP ACK 报文进行响应,证实所要求的参数。 从移动性角度看,DHCP 确实有非常严重的缺陷。因为每当节点连到一个新子网,要从 DHCP 得到一个新的 IP 地址,当 一个移动节点在子网之间移动时,就不能维持与远程应用之间的 TCP 连接 网络地址转换 NAT 使能路由器对于外部世界来说甚至不像一台路由器。相反 NAT 路由器对外界的行为就如同一个具有单一 IP 地址的单一设备。 通过使用 NAT 路由器上的一张 NAT 转换表(NAT translation table)、并且在表项中包含了端口号及其 IP 地址,该路由器怎样知道它应将某个分组转发给哪个内部主机 当生成一个新的源端口号时,NAT 路由器可选择任意一个当前未在 NAT 转换表中的源端口号。 IPv6 IPv6 数据报格式 扩大的地址容量。IPv6 将 IP 地址 长度从 32 比特增加到 128 比特。这就确保全世界将不会用尽 IP 地址。 简化高效的 40 宇节首部。40 字节定长首部允许路由器更快地处理 IP 数据报 3 一种新的选项编码允许进行更灵活的选项处理。 流标签。这些特殊流是发送方要求进行特殊处理的流,如一种非默认服务质量或需要实时服务的流。 版本。该 4 比特字段用于标识 IP 版本号。毫不奇怪,IPv6 将该字段值设为 6。 流量类型。该 8 比特字段与我们在 IPv4 中看到的 TOS 字段的含义相似。 有效载荷度该 16 比特值作为一个无符号整数,给出了 IPv6 数据报中跟在定长的 40 字节数据报首部后面的字节数量。 下一个首部。该字段标识数据报中的内容(数据字段)需要交付给哪个协议(如 TCP 或 UDP)。该字段使用与 IPv4 首部中协议字段相同的值。 跳限制。转发数据报的每台路由楛将对该字段的内容减 1。如果跳限制计数达到 0, 则该数据报将被丢弃。 源地址和目的地址 。IPv6 128 比特地址的各种格式在 RFC 4291 中进行了描述。 数据。这是 IPv6 数据报的有效载荷部分当数据报到达目的地时,该有效载荷就从 IP 数据报中移出,井交给在下一个首部字段中指定的协议处理。 从 IPv4 到 IPv6 的迁移 在实践中已经得到广泛采用的 IPv4 到 IPv6 迁移的方法包括建隧道。建隧道依据的基本思想如下:假定两个 IPv6 节点,使用 IPv6 数据报进行交互,但它们是经由中间 IPv4 路由器互联的。我们将两台 IPv6 路巾器之间的中间 IPv4 路由器的集合称为一个隧道 (tunnel) 通用转发和 SDN 在通用转发中,一张匹配加动作表将基于目的地的转发表一般化了。因为能够使用网络层和/或链路层源和目的地址做出转发决定,所以显示转发设备更为准确地描述为“分组交换机”而不是第三层“路由器”或第二层“交换机”。 匹配加动作转发表在 OpenFlow 中称为流表 (flow table), 它的每个表项包括: 首部宇段值的集合,入分组将与之匹配 。 与基于目的地转发的情况一样,基于硬件 匹配在 TCAM 内存中执行得最为迅速。匹配不上流表项的分组将被丢弃或发送到远程控制器做更多处 理 。 在实践中,为了性能或成本原因, 一 个流表可以由多个流表实现,但我们这里只关注单一流表的抽象 计数器集合(当分组与流表项匹配时更新计数器)。这些计数器可以包括已经与该表项匹配的分组数量,以及自从该表项上次更新以来的时间 当分组匹配流表项时所采取的动作集合。这些动作可能将分组转发到给定的输出端口,丢弃该分组、复制该分组和将它们发送到多个输出端口,和/或重写所选的首部字段。 匹配 OpenFlow 的匹配抽象允许对来自三个层次的协议首部所选择的字段进行匹配 流表项也可以有通配符 最后,并非一个 IP 首部中的所有字段都能被匹配 动作 转发。一个入分组可以转发到一个特定的物理输出端口,广播到所有端口,或通过所选的端口集合进行多播。该分组可能被封装并发送到用于该设备的远程控制器。该控制器则可能对该分组采取某些动作,包括安装新的流表项,以及可能将该分组返回给该设备以在更新的流表规则集合下进行转发 。 丢弃。没有动作的流表项表明某个匹配的分组应当被丢弃。 修改字段。在分组被转发到所选的输出端口之前,分组首部 10 个字段中的值可以重写 。 匹配加动作操作的 openFlow 例子 简单转发 负载均衡 充当防防火墙

2021 Jun 17 · 3 min

计算机网络自顶向下方法::运输层

概述和运输层服务 运输层协议为运行在不同主机上的应用进程之间提供了逻辑通信。应用进程使用运输层提供的逻辑通信功能彼此发送报文,而无须考虑承载这些报文的物理基础设施的细节。 运输层协议是在端系统中而不是在路由器中实现的。在发送端,运输层将从发送应用程序进程接收到的报文转换成运输层分组,用因特网术语来讲该分组称为运输层报文段(segment)。在接收端,网络层从数据报中提取运输层报文段,并将该报文段向上交给运输层 。运输层则处理接收到的报文段,使该报文段中的数据为接收应用进程使用。 网络应用程序可以使用多种的运输层协议。例如,因特网有两种协议,即 TCP 和 UDP。每种协议都能为调用的应用程序提供一组不同的运输层服务。 运输层和网络层的关系 在协议栈中,运输层刚好位于网络层之上。网络层提供了主机之间的逻辑通信,而运输层为运行在不同主机上的进程之间提供了逻辑通信 计算机网络中可以安排多种运输层协议,每种协议为应用程序提供不同的服务模型。 运输协议能够提供的服务常常受制于底层网络层协议的服务模型。如果网络层协议无法为主机之间发送的运输层报文段提供时延或带宽保证的话,运输层协议也就无法为进程之间发送的应用程序报文提供时延或带宽保证。 即使底层网络协议不能在网络层提供相应的服务,运输层协议也能提供某些服务。例如可靠运输。 因特网运输层概述 UDP:它为调用它的应用程序提供了一种不可靠、无连接的服务 TCP:它为调用它的应用程序提供了一种可靠的、面向连接的服务 当设计一个网络应用程序时,该应用程序的开发人员必须指定使用这两种运输协议中的一种 因特网网络层协议有一个名字叫 IP, 即网际协议。IP 为主机之间提供了逻辑通信。IP 的服务模型是尽力而为交付服务,是不可靠的 我们总结一下 UDP 和 TCP 所提供的服务模型。UDP 和 TCP 最基本的责任是,将两个端系统间 IP 的交付服务扩展为运行在端系统上的两个进程之间的交付服务。将主机间交付扩展到进程间交付被称为运输层的多路复用 ( transport-layer multiplexing) 与 多路分解 (demultiplexing) 进程到进程的数据交付和差错检查是两种最低限度的运输层服务,也就是 UDP 所提供的服务 TCP 额外供了可靠数据运输和拥塞控制 多路复用和多路分解 一个进程有一个或多个套接字,它相当于从网络向进程传递数据和从进程向网络传递数据的门户。在接收主机中的运输层实际上并没有直接将数据交付给进程,而是将数据交给了一个中间的套接字。由于在任一时刻,在接收主机上可能有不止一个套接字,所以每个套接字都有唯一的标识符。标识符的格式取决于它是 UDP 还是 TCP 套接字。 主机为了将一个到达的运输层报文段定向到适当的套接字,每个运输层报文段中具有几个字段。在接收端,运输层检查这些字段,标识出接收套接字,进而将报文段定向到该套接字。将运输层报文段中的数据交付到正确的套接字的工作称为多路分解( demulti plexing) 。在源主机从不同套接字中收集数据块,并为每个数据块封装上首部信息(这将在以后用于分解)从而生成报文段,然后将报文段传递到网络层,所有这些工作称为多路复用( multiplexing) 运输层多路复用要求 套接字有唯一标识 每个报文段有特殊字段来指示该报文段所要交付到的套接字 这些特殊字段是源端口号字段和目的端口号字段 在主机上的每个套接字能够分配一个端口号,当报文段到达主机时,运输层检查报文段中的目的端口号,并将其定向到相应的套接字。然后报文段中的数据通过套接字进入其所连接的进程 无连接的多路复用与多路分解 一个 UDP 套接字是由一个二元组全面标识的,该二元组包含一个目的 IP 地址和一个目的端口号。因此,如果两个 UDP 报文段有不同的源 IP 地址和/或源端口号,但具有相同的目的 IP 地址和目的端口号,那么这两个报文段将通过相同的目的套接字被定向到相同的目的进程。 面向连接的多路复用与多路分解 TCP 套接字是由一个四元组(源 IP 地址,源端口号,目的 IP 地址,目的端口号)来标识的 两个具有不同源 IP 地址或源端口号的到达 TCP 报文段将被定向到两个不同的套接字 Web 服务器与 TCP 如果客户与服务器使用持续 HTTP,则在整条连接持续期间 ,客户与服务器之间经由同一个服务器套接字交换 HTTP 报文 。然而,如果客户与服务器使用非持续 HTTP, 则对每一对请求/响应都创建一个新的 TCP 连接并在随后关闭、因此对每一对请求/响应创建一个新的套接字并在随后关闭。这种套接字的频繁创建和关闭会严重地影响一个繁忙的 Web 服务器的性能 无连接运输:UDP UDP 只是做了运输协议能够做的最少工作。除了复用/分解功能及少量的差错检测外,它几乎没有对 IP 增加别的东西。 使用 UDP 时,在发送报文段之前,发送方和接收方的运输层实体之间没有握手 使用 UDP 的理由 关于发送什么数据以及何时发送的应用层控制更为精细 无须连接建立 无连接状态 分组首部开销小 UDP 中缺乏拥塞控制能够导致 UDP 发送方和接收方之间的高丢包率,并挤垮了 TCP 会话,这是一个潜在的严重问题。很多研究人员已经提出了一些新的机制,使得 UDP 执行自适应的拥塞控制 使用 UDP 的应用是可能实现可靠数据传输的。这可通过在应用程序自身中建立可靠性机制来完成。例如 Google 的 QUIC。 UDP 报文段结构 源端口,发送方的端口号 目的端口,接收方的端口号 报文长度,即整个 UDP 报文的长度,包括头部和数据,单位为字节 检验和。 应用数据,也就是报文 UDP 检验和 检验和用千确定当 UDP 报文段从源到达目的地移动时,其中的比特是否发生了改变 发送方的 UDP 对报文段中的所有 16 比特字的和进行反码运算,求和时遇到的任何溢出都被回卷。 得到的结果被放在 UDP 报文段中的检验和字段,在接收方,全部的 4 个 16 比特字(包括检验和)没有引入差错 ,则显然在接收方处该和将是 1111111111111111 UDP 提供差错检测是因为不能保证源和目的之间的所有链路都提供差错检测;这就是说,也许这些链路中的一条可能使用没有差错检测的协议 可靠数据传输原理 构造可靠数据传输协议 经完全可靠信道的可靠数据传输: rdt1.0 首先,我们考虑最简单的情况,即底层信道是完全可靠的。我们称该协议为 rdt1.0,该协议本身是简单的。在这个简单的协议中,一个单元数据与一个分组没差别。而且,所有分组是从发送方流向接收方;有了完全可靠的信道,接收端就不需要提供任何反馈信息给发送方,因为不必担心出现差错!注意到我们也已经假定了接收方接收数据的速率能够与发送方发送数据的速率一样快。因此,接收方没有必要请求发送方慢一点! 经具有比特差错信道的可靠数据传输:rdt2.0 底层信道更为实际的模型是分组中的比特可能受损的模型。在分组的传输、传播或缓存的过程中,这种比特差错通常会出现在网络的物理部件中,我们眼下还将继续假定所有发送的分组(虽然有些比特可能受损)将按其发送的顺序被接收。 控制报文使得接收方可以让发送方知道哪些内容被正确接收,哪些内容接收有误并因此需要重复。在计算机网络环境中,基于这样重传机制的可靠数据传输协议称为自动重传请求( Automatic Repeat Request,ARQ)协议。 差错检测:首先,需要一种机制以使接收方检测到何时出现了比特差错 接收方反馈:rdt2.0 协议将从接收方向发送方反馈是否接受的分组。 重传:接收方收到有差错的分组时,发送方将重传该分组文 当发送方处于等待 ACK 或 NAK 的状态时,它不能从上层获得更多的数据,仅当接收到 ACK 并离开该状态时才能发生这样的事件,因此,发送方将不会发送一块新数据,除非发送方确信接收方已正确接收当前分组。由于这种行为,rdt2.0 这样的协议被称为停等(stop-and-wait)协议。 考虑受损 ACK 和 NAK 的 3 种可能性 增加确认机制,会陷入无尽的确认,不可行 增加足够的检验和比特,使发送方不仅可以检测差错,还可恢复差错 当发送方收到含糊不清的 ACK 或 NAK 分组时,只需重传当前数据分组即可。然而,这种方法在发送方到接收方的信道中引入了冗余分组 (duplicate packet) 。冗余分组的根本困难在于接收方不知道它上次所发送的 ACK 或 NAK 是否被发送方正确地收到。因此它无法事先知道接收到的分组是新的还是一次重传! 解决这个新问题的一个简单方法是在数据分组中添加一新字段,让发送方对其数据分组编号,即将发送数据分组的序号放在该字段。于是,接收方只需要检查序号即可确定收到的分组是否一次重传。对于停等协议这种简单情况,1 比特序号就足够了,因为它可让接收方知道发送方是否正在重传前一个发送分组,或是一个新分组。 协议 rdt2.1 使用了从接收方到发送方的肯定确认和否定确认。当接收到失序的分组时,接收方对所接收的分组发送一个肯定确认。如果收到受损的分组,则接收方将发送一个否定确认。如果不发送 NAK, 而是对上次正确接收的分组发送一个 ACK, 我们也能实现与 NAK 一样的效果。发送方接收到对同一个分组的两个 ACK,就知道接收方没有正确接收到跟在被确认两次的分组后面的分组,rdt2.2 是在有比特差错信道上实现的一个无 NAK 的可靠数据传输协议 经具有比特差错的丢包信道的可靠数据传输:rdt3.0 协议现在必须处理另外两个关注的问题:怎样检测丢包以及发生丢包后该做些什么 发送方负责检测和恢复丢包工作 判断丢失:发送方传输一个数据分组,该分组或者接收方对该分组的 ACK 发生了丢失。在这两种情况下,发送方都收不到应当到来的接收方的响应。如果发送方愿意等待足够长的时间以便确定分组已丢失,则它只需重传该数据分组即可。 决定等待时长:即发送方与接收方之间的一个往返时延(可能会包括在中间路由器的缓冲时延)加上接收方处理一个分组所需的时间。为了实现基于时间的重传机制,需要一个倒计数定时器,在一个给定的时间掀过期后,可中断发送方。因此,发送方需要能做到:每次发送一个分组(包括第一次分组和重传分组)时,便启动一个定时器;响应定时器中断;终止定时器 现在我们归纳一下数据传输协议的要点。在检验和、序号、定时器、肯定和否定确认分组这些技术中,每种机制都在协议的运行中起到了必不可少的作用。至此,我们得到了一个可靠数据传输协议! 流水线可靠数据传输协议 rtd3.0 有个停等协议影响性能,存在信道利用率低的问题。 这种特殊的性能问题的一个简单解决方法是:不以停等方式运行,允许发送方发送多个分组而无须等待确认,因为许多从发送方向接收方输送,的分组可以被看成是填充到一条流水线中,故这种技术被称为流水线 流水线协议对可靠数据传输协议带来的影响 增加序列号范围 发送方和接收方需要缓存多个分组 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。解决流水线的差错恢复有两种基本方法是:回退 N 步 (Go-Back-N, GBN) 和选择重传 (Selective Repeat, SR) 。 回退 N 步 那些已被发送但还未被确认的分组的许可序号范围可以被看成是一个在序号范围内长度为 N 的窗口,随着协议的运行,该窗口在序号空间向前滑动。因此,N 常被称为窗口长度 (window size),GBN 协议也常被称为滑动窗口协议 (sliding-window protocol)。 GNB 发送方需要响应三种类型的事件 上层的调用:当上层调用发送函数时,如果队列满了就不发送。 收到一个 ACK:对收到的序号 n 和 n 以前的分组全部确认 超时事件:如果出现超时,发送方重传所有已发送但还未被确认过的分组 接收方如果一个需要为 n 的分组被正确按序接受,则接收方为分组 n 发送一个 ACK, 并将该分组中的数据部分交付到上层。在所有其他情况下,接收方丢弃该分组,并为最近按序接收的分组重新发送 ACK。因为接收方需要按序交付分组给上层。 选择重传 选择重传 (SR) 协议通过让发送方仅重传那些它怀疑在接收方出错(即丢失或受损)的分组而避免了不必要的重传。这种个别的、按需的重传要求接收方逐个地确认正确接收的分组。再次用窗口长度 N 来限制流水线中未完成 、未被确认的分组数。然 而,与 GBN 不同的是,发送方已经收到了对窗口中某些分组的 ACK。 SR 接收方将确认一个正确接收的分组而不管其是否按序。失序的分组将被缓存直到所有丢失分组(即序号更小的分组 )皆被收到为止,这时才可以将一批分组按序交付给上层 。 发送方的事件 从上层收到数据。当从上层接收到数据后,SR 发送方检查下一个可用于该分组的序号。如果序号位于发送方的窗口内,则将数据打包并发送;否则就像在 GBN 中一样,要么将数据缓存,要么将其返回给上层以便以后传输。 超时。定时器再次被用来防止丢失分组。然而 ,现在每个分组必须拥有其自己的逻辑定时器,因为超时发生后只能发送一个分组。可以使用单个硬件定时楛模拟多个逻辑定时器的操作。 收到 ACK。如果收到 ACK, 倘若该分组序号在窗口内,则 SR 发送方将那个被确认的分组标记为已接收。如果该分组的序号等于 send_base, 则窗口基序号向前移动到具有最小序号的未确认分组处。如果窗口移动了并且有序号落在窗口内的未发送分组,则发送这些分组。 接收方的事件 序号在[rev_base,rcv_base + N - 1]内的分组被正确接收。在此情况下,收到的分组落在接收方的窗口内,一个选择 ACK 被回送给发送方。如果该分组以前没收到过,则缓存该分组。如果该分组的序号等于接收窗口的基序号,则该分组以及以前缓存的序号连续的分组交付给上层。然后,接收窗口按向前移动分组的编号向上交付这些分组。 序号在 [ rcv_base - N, rcv_base - 1] 内的分组被正确收到。在此情况下,必须产生一个 ACK, 是接收方以前已确认过的分组 。 其他情况。忽略该分组 。 对于哪些分组已经被正确接收,哪些没有,发送方和接收方并不总是能看到相同的结果。对 SR 协议而言,这就意味着发送方和接收方的窗口并不总是一致。 可靠数据传输机制及其用途的总结 检验和;用于检测在一个传输分组中的比特错误 定时器:用于超时/重传一个分组,可能因为该分组〈或其 ACK) 在信道中丢失了。由于当一个分组延时但未丢失〈过早超时) ,或当一个分组已被接收方收到但从接收方到发送方的 ACK 丢失时,可能产生超时事件,所以接收方可能会收到一个分组的多个冗余副本 序号:用于为从发送方流向接收方的数据分组按顺序编号。所接收分组的序号间的空隙可使接收方检测出丢失的分组。具有相同序号的分组可使接收方检测出一个分组的冗余副本 确认:接收方用于告诉发送方一个分组或一组分组已被正确地接收到了。确认报文通常携带着被确认的分组或多个分组的序号。确认可以是逐个的或累积的,这取决于协议 否定确认:接收方用于告诉发送方某个分组未被正确地接收。否定确认报文通常据带着未被正确接收的分组的序号 窗口、流水线:发送方也许被限制仅发送那些序号落在一个指定范围内的分组。通过允许一次发送多个分组但未被确认,发送方的利用率可在停等操作模式的基础上得到增加。我们很快将会看到,窗口长度可根据接收方接收和缓存报文的能力、网络中的拥塞程度或两者情况来进行设置 ...

2021 Jun 16 · 6 min

计算机网络自顶向下方法::应用层

应用层协议原理 应用层协议原理 研发网络应用程序的核心是写出能够运行在不同的端系统和通过网络彼此通信的程序 当研发新应用程序时,你需要编写将在多台端系统上运行的软件 网络应用体系结构 从应用程序研发者的角度看,网络体系结构是固定的,并为应用程序提供了特定的服务集合 应用程序体系结构 (application architecture) 由应用程序研发者设计,规定了如何在各种端系统上组织该应用程序。 客户-服务器体系结构 有一个总是打开的主机称为服务器,它服务于来自许多其他称为客户的主机的请求 客户-服务器体系结构,客户相互之间不直接通信 服务器具有固定的、周知的地址,该地址称为 IP 地址 具有客户-服务器体系结构的非常著名的应用程序包括 Web、FTP、Telnet 和电子邮件 一个流行的社交网络站点如果仅有一台服务器来处理所有请求,将很快变得不堪重负。为此,配备大量主机的数据中心(data center)常被用于创建强大的虚拟服务器。 P2P 体系结构 对数据中心服务器有最小的依赖 应用程序在间断连接的主机对之间使用直接通信,这些主机对被称为对等方 具有自扩展性,成本效率高,不需要庞大的基础设施 具有 P2P 体系结构的应用包括 BitTorrent、因特网电话和视频会议(例如 Skype) 进程通信 客户与服务器通信 网络应用程序由成对的进程组成,这些进程通过网络相互发送报文 对每对通信进程,我们通常将这两个进程之一标识为客户(client) , 而另一个进程标识为服务器 在 P2P 文件共享的某些应用中,一个进程能够既是客户又是服务器 我们定义客户和服务器进程如下: 在一对进程之间的通信会话场景中,发起通信(即在该会话开始时发起与其他进程的联系) 的进程被标识为客户,在会话开始时等待联系的进程是服务器 进程与计算机网络之问的接口 进程通过一个称为套接字(socket)的软件接口向网络发送报文和从网络接收报文 套接字是同一台主机内应用层与运输层之间的接口。由于该套接字是建立网络应用程序的可编程接口,因此套接字也称为应用程序和网络之间的应用程序编程接口 进程寻址 为了标识该接收进程,需要定义两种信息 主机的地址 目的主机中指定接受进程的标识符 在因特网中,主机由其 IP 地址 (IP adress) 标识 目的地端口号 (port number) 用于指定运行在接收主机上的接收进程(更具体地说,接收套接字) 可供应用程序使用的运输服务 可靠数据传输 确保由应用程序的一端发送的数据正确、完全地交付给该应用程序的另一端 吞吐量 运输层协议能够以某种特定的速率提供确保的可用吞吐量 带宽敏感的应用具有特定的吞吐量要求,而弹性应用 (elastic application) 能够根据当时可用的带宽或多或少地利用可供使用的吞吐量 定时 运输层协议也能提供定时保证,能够以多种形式实现。这种服务将对交互式实时应用程序有吸引力。 安全性 在发送和接收进程之间提供机密性,以防该数据以某种方式在这两个进程之间被观察到。运输协议还能提供除了机密性以外的其他安全性服务,包括数据完整性和端点鉴别 因特网的提供的运输服务 TCP 服务 面向连接服务和可靠数据传输服务 在应用层数据报文开始流动之前,TCP 让客户端和服务器互相交换运输层控制信息。在握手后,一个全双工 TCP 连接就在两者之间建立了。当应用程序结束报文发送时,必须拆除该连接。 通信进程能够依靠 TCP, 无差错、按适当顺序交付所有发送的数据。当应用程序的一端将字节流传进套接字时,它能够依靠 TCP 将相同的字节流交付给接收方的套接字,而没有字节的丢失和冗余。 TCP 也提供拥塞控制机制,当发送方和接收方之间的网络出现拥塞时,TCP 的拥塞控制机制会抑制发送进程,TCP 拥塞控制也试图限制每个 TCP 连接,使它们达到公平共享网络带宽的目的。 UDP 服务 UDP 是一种不提供不必要服务的轻量级运输协议,它仅提供最小服务。UDP 是无连接的,因此在两个进程通信前没有握手过程。 UDP 协议提供一种不可靠数据传送服务,不保证报文能到达接受进程,也不保证顺序。 UDP 没有拥塞控制机制,可以以任意速率向下层注入数据。 运输协议不提供的服务 吞吐量和定时保证 应用层协议 交换的报文类型,例如请求报文和响应报文。 各种报文类型的语法,如报文中的各个字段及这些字段是如何描述的。 字段的语义,即这些字段中的信息的含义。 确定一个进程何时以及如何发送报文,对报文进行响应的规则。 Web 和 HTTP HTTP 概况 ...

2021 Jun 16 · 7 min

计算机网络自顶向下方法::计算机网络和因特网

计算机网络和因特网 什么是因特网 具体构成描述 因特网是一个世界范围的计算机网络,即它是一个互联了遍及全世界数十亿计算设备的网络。 传统 PC、Linux 工作站、服务器、智能手机、平板电脑、电视机、游戏机、家用电器、手表正在与互联网相连,这些设备称为主机或者端系统。 端系统通过通信链路 (communication link) 和分组交换机 (packet switch) 连接到一起 不同的链路能够以不同的速率传输数据,链路的传输速率 (transmission rate) 以比特/秒 (bills, 或 bps) 度量 。 当一台端系统要向另一台端系统发送数据时,发送端系统将数据分段,并为每段加上首部字节。由此形成的信息包用计算机网络的术语来说称为分组( packet)。这些分组通过网络发送到目的端系统,在那里被装配成初始数据。 分组交换器 从它的一条入通信链路接收到达的分组,并从它的一条出通信链路转发该分组 在当今的因特网中,两种最著名的类型是路由器(router)和链路层交换机(link-layer switch) 链路层交换机通常用于接入网中,而路由器通常用于网络核心中。 从发送端系统到接收端系统,一个分组所经历的一系列通信链路和分组交换机称为通过该网络的路径(route 或 path) ISP 端系统通过因特网服务提供商 (Internet Service Provider, ISP) 接入因特网 每个 ISP 自身就是一个由多台分组交换机和多段通信链路组成的网络。 协议 端系统、分组交换机和其他因特网部件都要运行一系列协议 (protocol), 这些协议控制因特网中信息的接收和发送。 TCP、IP、HTTP、SMTP 协议标准由因特网工程任务组研发,IETF 的标准文档称为请求评论(Request For Comment, RFC) 服务描述 为应用程序提供服务的基础设施 因特网相连的端系统提供了一个套接字接口(socket interface), 该接口规定了运行在一个端系统上的程序请求因特网基础设施向运行在另一个端系统上的特定目的地程序交付数据的方式。 什么是协议 定义了在两个或多个通信实体之间交换的报文的格式和顺序,以及报文发送和/或接收一条报文或其他事件所采取的动作。 因特网中协议无处不在快,不同的协议用于完成不同的通信任务。 网络边缘 与因特网相连的计算机和其他设备称为端系统,它们位于因特网的边缘,因特网的端系统包括了桌面计算机、服务器和移动计算机和非传统联网设备。 端系统被称为主机 运行应用程序,提供服务 主机有时又被进一步划分为两类 :客户(client)和服务器(server) 接入网 将端系统物理连接到其边缘路由器(edge router)的网络。边缘路由器是端系统到任何其他远程端系统的路径上的第一台路由器。 家庭接入: DSL、电缆、 FTTH、拨号和卫星 企业(和家庭)接人: 以太网和 WiFi 广域无线接入: 3/4/5G 和 LTE 物理媒介 双绞铜线 同轴电缆 光线 陆地无线电信道 卫星无线电信号 网络核心 分组交换 在各种网络应用中, 端系统彼此交换报文(message), 报文能够包含协议设计者需要的任何东西,报文可以执行一种控制功能,也可以包含数据, 为了从源端系统向目的端系统发送一个报文, 源将长报文划分为较小的数据块,称之为分组(packet)。 在源和目的地之间,每个分组都通过通信链路和分组交换机(packet switch)传送。 如果某源端系统或分组交换机经过一条链路发送一个 L 比特的分组,链路的传输速率为 R 比特/秒,则传输该分组的时间为 L/R 秒 。 存储转发传输 存储转发传输是指在交换机能够开始向输出链路传输该分组的第一个比特之前,必须接收到整个分组。 排队时延和分组丢失 如果到达的分组需要传输到某条链路,但发现该链路正忙于传输其他分组,该到达分组必须在输出缓存中等待。因此,除了存储转发时延以外,分组还要承受输出缓存的排队时延。 因为缓存空间的大小是有限的,一个到达的分组可能发现该缓存巳被其他等待传输的分组完全充满了。在此情况下,将出现分组丢失( 丢包)(packet loss), 到达的分组或已经排队的分组之一将被丢弃 。 转发表和路由选择协议 每台路由器具有一个转发表(forwarding table),用于将目的地址(或目的地址的一部分) 映射成为输出链路。当某分组到达一台路由器时,路由器检查该地址,并用这个目的地址搜索其转发表,以发现适当的出链路。路由器则将分组导向该出链路 。 因特网具有一些特殊的路由选择协议,(routing protocol) ,用于自动地设置这些转发表。 电路交换 在电路交换网络中,在端系统间通信会话期间,预留了端系统间沿路径通信所需要的资源(缓存,链路传输速率) 在分组交换网络中.这些资源则不是预留的;会话的报文按需使用这些资源,其后果可能是不得不等待(即排队)接入通信线路 。 传统的电话网络是电路交换的例子。 电路交换网络中的复用 频分复用,链路的频谱由跨越链路创建的所有连接共享,不够经济。 时分复用,时间被划分为固定期间的帧,并且每个帧又被划分为固定数量的时隙。当网络跨越一条链路创建一条连接时,网络在每个帧中为该连接指定一个时隙,这些时隙专门由该连接单独使用,一个时隙( 在每个帧内)可用于传输该连接的数据。 分组交换于电路交换的对比 电路交换不考虑需求,而预先分配了传输链路的使用,这使得巳分配而并不需要的链路时间未被利用,另一方面,分组交换按需分配链路使用。链路传输能力将在所有需要在链路上传输分组的用户之间逐分组地被共享。 网络的网络 今天的因特网是一个网络的网络,其结构复杂,由十多个第一层 ISP 和数十万个较低层 ISP 组成。ISP 覆盖的区域多种多样,有些跨越多个大洲和大洋,有些限于狭窄的地理区域。较低层的 ISP 与较高层的 ISP 相连,较高层 ISP 彼此互联。用户和内容提供商是较低层 ISP 的客户,较低层 ISP 是较高层 ISP 的客户。近年来,主要的内容提供商也已经创建自己的网络,直接在可能的地方与较低层 ISP 互联。 分组交换网中的时延、丢包和吞吐量 分组交换网中的时延概述 时延的类型 处理时延:检查分组首部,决定分组路由,检查比特级别差错,微秒或更低的数量级别。 排队时延:一个特定分组的排队时延长度将取决于先期到达的正在排队等待向链路传输的分组数量,实际的排队时延可以是毫秒到微秒量级。 传输时延:将所有分组的比特推向链路(即传输,或者说发射)所需要的时间。实际的传输时延通常在毫秒到微秒量级。 传播时延:从该链路的起点到路由器传播所需要的时间是传播时延,在广域网中,传播时延为毫秒级别。 排队时延和丢包 排队时延对不同的分组可能是不同的。 传输的第一个分组没有排队时延,而传输的最后一个分组将经受相对大的排队时延 当表征排队时延时,人们通常使用统计量来度量,如平均排队时延排队时延的方差和排队时延超过某些特定值的概率 如果分组以突发形式到达而不是周期性到达,则可能会有很大的平均排队时延 。 随着流量强度接近于 1,平均排队时延迅速增加。该强度的少量增加将导致时延大比例增加 。 当分组到达路由器,路由器没有地方存储这个分组,就会丢弃 (drop) 该分组,即该分组将会丢失 (lost) 。丢失的分组可能基于端到端的原则重传,以确保所有的数据最终从源传送到了目的地。 端到端时延 端到端的时延是之间每一跳的时延总和 Traceout 可用来跟踪中间每一跳的时延 端系统、应用程序和其他时延:协议有意的时延,VoIP 分组时延。 计算机网络中的吞吐量 在任何时间瞬间的瞬时吞吐量(instantaneous throughput) 是主机接收到该文件的速率 如果该文件由 F 比特组成,主机 B 接收到所有 F 比特用去 T 秒,则文件传送的平均吞吐量 (average throughput) 是 F/Tbps 当没有其他干扰流最时,其吞吐量能够近似为沿着源和目的地之间路径的最小传输速率 。 协议层次及其服务模型 分层的体系结构 一个协议层能够用软件、硬件或两者的结合来实现 各层的所有协议被称为协议栈。因特网的协议栈由 5 个层次组成:物理层、链路层 、网络层、运输层和应用层。 应用层:应用层是网络应用程序及它们的应用层协议存留的地方,包括了 HTTP,SMTP 和 FTP。应用层协议分布在多个端系统上,而一个端系统中的应用程序使用协议与另一个端系统中的应用程序交换信息分组。我们把这种位于应用层的信息分组称为报文 ( message)。 传输层:因特网的运输层在应用程序端点之间传送应用层报文。 在因特网中,有两种运输协议,即 TCP 和 UDP, 利用其中的任一个都能运输应用层报文 。 TCP 向它的应用程序提供了面向连接的服务。这种服务包括了应用层报文向目的地的确保传递和流量控制。 UDP 协议向它的应用程序提供无连接服务。这是一种不提供不必要服务的服务,没有可靠性,没有流量控制,也没有拥塞控制。 网络层:因特网的网络层负责将称为数据报 (datagram) 的网络层分组从一台主机移动到另一台主机。 链路层:因特网的网络层通过源和目的地之间的一系列路由器路由数据报。网络层将数据报下传给链路层,链路层沿着路径将数据报传递给下一个节点。在该下一个节点,链路层将数据报上传给网络层。我们把链路层分组称为帧。 物理层:物理层的任务是将帧中的一个个比特从一个节点移动到下一个节点。 OSI 模型 应用层、表示层、会话层、运输层、网络层、数据链路层和物理层。 表示层的作用是使通信的应用程序能够解释交换数据的含义。这些服务包括数据压缩和数据加密(它们是自解释的) 以及数据描述(这使得应用程序不必担心在各台计算机中表示/存储的内部格式不同的问题)。 会话层提供了数据交换的定界和同步功能,包括了建立检查点和恢复方案的方法 。 封装 在发送主机端,一个应用层报文 (application-layer message) 被传送给运输层。 运输层收取到报文并附上附加信息(所谓运输层首部信息) 该首部将被接收端的运输层使用。应用层报文和运输层首部信息一道构成了运输层报文段(transport­ layer segment) 。运输层报文段因此封装了应用层报文。附加的信息也许包括了下列信息: 允许接收端运输层向上向适当的应用程序交付报文的信息;差错检测位信息,该信息让接收方能够判断报文中的比特是否在途中已被改变。 运输层则向网络层传递该报文段,网络层增加了如源和目的端系统地址等网络层首部信息,生成了网络层数据报 ( network-layer datagram) 。 该数据报接下来被传递给链路层,链路层增加它自己的链路层首部信息并生成链路层帧(link-layer frame) 。 面对网络攻击 恶意软件,僵尸网络,自我复制,病毒,蠕虫 DoS 攻击 弱点攻击。这涉及向一台目标主机上运行的易受攻击的应用程序或操作系统发送制作精细的报文。 带宽洪泛。攻击者向目标主机发送大量的分组,分组数量之多使得目标的接入链路变得拥塞,使得合法的分组无法到达服务器 。 连接洪泛。攻击者在目标主机中创建大量的半开或全开 TCP 连接。该主机因这些伪造的连接而陷入困境,并停止接受合法的连接 。 嗅探分组 在无线传输设备的附近放置一台被动的接收机,该接收机就能得到传输的每个分组的副本! 这些分组包含了各种敏感信息,包括口令、社会保险号、商业秘密和隐秘的个人信息。记录每个流经的分组副本的被动接收机被称为分组嗅探器。 嗅探器也能够部署在有线环境中。 IP 哄骗 将具有虚假源地址的分组注入因特网的。生成具有任意源地址、分组内容和目的地址的分组,然后将这个人工制作的分组传输 到因特网中,因特网将忠实地将该分组转发到目的地。 计算机网络和因特网的历史 分组交换的发展: 1961 ~ 1972 专用网络和网络互联: 1972 ~ 1980 网络的激增: 1980 ~ 1990 因特网爆炸: 20 世纪 90 年代到现在

2021 Jun 15 · 2 min

深入理解Java虚拟机::线程安全和锁优化

线程安全和锁优化 线程安全 当多个线程同时访问一个对象时,如果不用考虑这些线程在运行时环境下 的调度和交替执行,也不需要进行额外的同步,或者在调用方进行任何其他的协调操作,调用这个对象的行为都可以获得正确的结果,那就称这个对象是线程安全的。 代码本身封装了所有必要的正确性保障手段(如互斥同步等),令调用者无须关心多线程下的调用问题,更无须自己实现任何措施来保证多线程环境下的正确调用 Java 语言中的线程安全 不可变 不可变(Immutable)的对象一定是线程安全的,无论是对象的方法实现还是方法的调用者,都不需要再进行任何线程安全保障措施。 最简单的一种就是把对象里面带有状态的变量都声明为 final 常见不可变类型 String 枚举类 java.lang.Number 的部分子类 Long Double BigInteger BigDecimal 绝对线程安全 不管运行时环境如何,调用者都不需要任何额外的同步措施 相对线程安全 需要保证对这个对象单次的操作是线程安全的,我们在调用的时候不需要进行额外的保障措施,但是对于一些特定顺序的连续调用,就可能需要在调用端使用额外的同步手段来保证调用的正确性。 线程兼容 线程兼容是指对象本身并不是线程安全的,但是可以通过在调用端正确地使用同步手段来保证对象在并发环境中可以安全地使用 线程对立 线程对立是指不管调用端是否采取了同步措施,都无法在多线程环境中并发使用代码 线程安全的实现方法 互斥同步 同步是指在多个线程并发访问共享数据时,保证共享数据在同一个时刻只被一条(或者是一些,当使用信号量的时候)线程使用。 互斥是实现同步的一种手段,临界区(Critical Section)、互斥量 (Mutex)和号量(Semaphore)都是常见的互斥实现方式 synchronized synchronized 关键字经过 Javac 编译之后,会在同步块的前后分别形成 monitorenter 和 monitorexit 这两个字节码指令 。 这两个字节码指令都需要一个 reference 类型的参数来指明要锁定和解锁的对象 被 synchronized 修饰的同步块对同一条线程来说是可重入的。这意味着同一线程反复进入同步块也不会出现自己把自己锁死的情况。 被 synchronized 修饰的同步块在持有锁的线程执行完毕并释放锁之前,会无条件地阻塞后面其他线程的进入。这意味着无法像处理某些数据库中的锁那样,强制已获取锁的线程释放锁;也无法强制正在等待锁的线程中断等待或超时退出。 持有锁是一个重量级 ReentrantLock 等待可中断:是指当持有锁的线程长期不释放锁的时候,正在等待的线程可以选择放弃等待,改为处理其他事情。可中断特性对处理执行时间非常长的同步块很有帮助。 公平锁:是指多个线程在等待同一个锁时,必须按照申请锁的时间顺序来依次获得锁;而非公平锁则不保证这一点,在锁被释放时,任何一个等待锁的线程都有机会获得锁。synchronized 中的锁是非公平的,ReentrantLock 在默认情况下也是非公平的,但可以通过带布尔值的构造函数要求使用公平锁。不过一旦使用了公平锁,将会导致 ReentrantLock 的性能急剧下降,会明显影响吞吐量。 锁绑定多个条件:是指一个 ReentrantLock 对象可以同时绑定多个 Condition 对象。在 synchronized 中,锁对象的 wait()跟它的 notify()或者 notifyAll()方法配合可以实现一个隐含的条件,如果要和多于一个的条件关联的时候,就不得不额外添加一个锁;而 ReentrantLock 则无须这样做,多次调用 newCondition()方法即可。 比较 性能接近 只需要基础的同步功能时,更推荐 synchronized。 Lock 应该确保在 finally 块中释放锁,否则一旦受同步保护的代码块中抛出异常,则有可能永远不 会释放持有的锁。这一点必须由程序员自己来保证,而使用 synchronized 的话则可以由 Java 虚拟机来确保即使出现异常,锁也能被自动释放。 非同步阻塞 基于冲突检测的乐观并发策略 如果共享的数据的确被争用,产生了冲突,那再进行其他的补偿措施,最常用的补偿措施是不断地重试,直到出现没有竞争的共享数据为止。这种乐观并发策略的实现不再需要把线程阻塞挂起,因此这种同步操作被称为非阻塞同步(Non-Blocking Synchronization),使用这种措施的代码也常被称为无锁(Lock-Free) 编程。 硬件指令保证原子性 测试并设置(Test-and-Set) ; 获取并增加(Fetch-and-Increment) ; 交换(Swap); 比较并交换(Compare-and-Swap,下文称 CAS); 加载链接/条件储存(Load-Linked/Store-Conditional,下文称 LL/SC)。 无同步方案 可重入代码 可以在代码执行的任何时刻中断它,转而去执行另外一段代码(包括递归调用它本身),而在控制权返回后,原来的程序不会出现任何错误,也不会对结果有所影响。 不依赖全局变量、存储在堆上的数据和公用的系统资源,用到的状态量都由参数中传入,不调用非可重入的方法等。 线程本地存储(Thread Local Storage):如果一段代码中所需要的数据必须与其他代码共享,那就看看这些共享数据的代码是否能保证在同一个线程中执行。如果能保证,我们就可以把共享数据的可见范围限制在同一个线程之内,这样,无须同步也能保证线程之间不出现数据争用的问题。 锁优化 自旋锁与自适应自旋 自适应意味着自旋的时间不再是固定的了,而是由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定的。 锁消除 锁消除是指虚拟机即时编译器在运行时,对一些代码要求同步,但是对被检测到不可能存在共享数据竞争的锁进行消除。 锁粗化 如果虚拟机探测到有这样一串零碎的操作都对同一个对象加锁,将会把加锁同步的范围扩展(粗化)到整个操作序列的外部 轻量级锁 在代码即将进入同步块的时候,如果此同步对象没有被锁定(锁标志位为“01”状态),虚拟机首先将在当前线程的栈帧中建立一个名为锁记录(Lock Record)的空间,用于存储锁对象目前的 Mark Word 的拷贝,然后,虚拟机将使用 CAS 操作尝试把对象的 Mark Word 更新为指向 Lock Record 的指针。如果这个更新动作成功了,即代表该线程拥有了这个对象的锁,并且对象 Mark Word 的锁标志位(Mark Word 的最后两个比特)将转变为“ 00”,表示此对象处于轻量级锁定状态. 偏向锁 它的目的是消除数据在无竞争情况下的同步原语,进一步提高程序的运行性能。如果说轻量级锁是在无竞争的情况下使用 CAS 操作去消除同步使用的互斥量,那偏向锁就是在无竞争的情况下把整个同步都消除掉,连 CAS 操作都不去做了

2021 Apr 12 · 1 min

深入理解Java虚拟机::Java 内存模型与线程

Java 内存模型与线程 Amdahl 定律通过系统中并行化与串行化的比重来描述多处理器系统能获得的运算加速能力,摩尔定律则用于描述处理器晶体管数量与运行效率之间的发展关系。这两个定律的更替代表了近年来硬件发展从追求处理器频率到追求多核心并行处理的发展过程。 硬件的效率与一致性 缓存一致性 在多路处理器系统中,每个处理器都有自己的高速缓存,而它们又共享同一主内存 当多个处理器的运算任务都涉及同一块主内存区域时,将可能导致各自的缓存数据不一致 为了解决一致性的问题,需要各个处理器访问缓存时都遵循一些协议,在读写时要根据协议来进行操作,这类协议有 MSI、MESI(Illinois Protocol)、MOSI、 Synapse、Firefly 及 Dragon Protocol 等 内存模型 在特定的操作协议下,对特定的内存或高速缓存进行读写访问的过程抽象 Java 内存模型 主内存与工作内存 Java 内存模型的主要目的是定义程序中各种变量的访问规则,即关注在虚拟机中把变量值存储到内存和从内存中取出变量值这样的底层细节。 变量 包括实例字段、静态字段和构成数组对象的元素 不包括局部变量与方法参数,线程私有的 Java 内存模型规定了所有的变量都存储在主内存(Main Memory)中 每条线程还有自己的工作内存 线程的工作内存中保存了被该线程使用的变量的主内存副本,线程对变量的所有操作(读取、赋值等)都必须在工作内存中进行,而不能直接读写主内存中的数据。 内存之间的交互操作 8 个原子操作 lock(锁定):作用于主内存的变量,它把一个变量标识为一条线程独占的状态。 unlock(解锁):作用于主内存的变量,它把一个处于锁定状态的变量释放出来,释放后的变量才可以被其他线程锁定。 read(读取):作用于主内存的变量,它把一个变量的值从主内存传输到线程的工作内存中,以便随后的 load 动作使用。 load(载入):作用于工作内存的变量,它把 read 操作从主内存中得到的变量值放入工作内存的变量副本中。 use(使用):作用于工作内存的变量,它把工作内存中一个变量的值传递给执行引擎,每当虚拟机遇到一个需要使用变量的值的字节码指令时将会执行这个操作。 assign(赋值):作用于工作内存的变量,它把一个从执行引擎接收的值赋给工作内存的变量,每当虚拟机遇到一个给变量赋值的字节码指令时执行这个操作。 store(存储):作用于工作内存的变量,它把工作内存中一个变量的值传送到主内存中,以便随后的 write 操作使用。 write(写入):作用于主内存的变量,它把 store 操作从工作内存中得到的变量的值放入主内存的变量中。 需要满足的规则 不允许 read 和 load、store 和 write 操作之一单独出现,即不允许一个变量从主内存读取了但工作内存不接受,或者工作内存发起回写了但主内存不接受的情况出现。 不允许一个线程丢弃它最近的 assign 操作,即变量在工作内存中改变了之后必须把该变化同步回主内存。 不允许一个线程无原因地(没有发生过任何 assign 操作)把数据从线程的工作内存同步回主内存中。 一个新的变量只能在主内存中“诞生”,不允许在工作内存中直接使用一个未被初始化(load 或 assign)的变量,换句话说就是对一个变量实施 use、store 操作之前,必须先执行 assign 和 load 操作 。 一个变量在同一个时刻只允许一条线程对其进行 lock 操作,但 lock 操作可以被同一条线程重复执行多次,多次执行 lock 后,只有执行相同次数的 unlock 操作,变量才会被解锁。 如果对一个变量执行 lock 操作,那将会清空工作内存中此变量的值,在执行引擎使用这个变量前,需要重新执行 load 或 assign 操作以初始化变量的值。 如果一个变量事先没有被 lock 操作锁定,那就不允许对它执行 unlock 操作,也不允许去 unlock 一个被其他线程锁定的变量。 对一个变量执行 unlock 操作之前,必须先把此变量同步回主内存中(执行 store、write 操作)。 对于 volatile 型变量的特殊规则 两项特性 第一项是保证此变量对所有线程的可见性,这里的“可见性”是指当一条线程修改了这个变量的值,新值对于其他线程来说是可以立即得知的 保证原子性 运算结果并不依赖变量的当前值,或者能够确保只有单一的线程修改变量的值。 变量不需要与其他的状态变量共同参与不变约束。 禁止指令重排序优化 volatile 变量读操作的性能消耗与普通变量几乎没有什么差别,但是写操作则可能会慢上一些,因为它需要在本地代码中插入许多内存屏障指令来保证处理器不发生乱序执行。 volatile 屏蔽指令重排序的语义在 JDK 5 中才被完全修复,此前的 JDK 中即使将变量声明为 volatile 也仍然不能完全避免重排序所导致的问题(主要是 volatile 变量前后的代码仍然存在重排序问题),这一点也是在 JDK5 之前的 Java 中无法安全地使用 DCL(双锁检测)来实现单例模式的原因。 双重锁定检查是一种在许多语言中都广泛流传的单例构造模式。 针对 long 和 double 型变量的特殊规则 long 和 double 的非原子性协定 在实际开发中,除非该数据有明确可知的线程竞争,否则我们在编写代码时一般不需要因为这个原因刻意把用到的 long 和 double 变量专门声明为 volatile。 原子性、可见性与有序性 原子性(Atomicity) 由 Java 内存模型来直接保证的原子性变量操作包括 read、load、assign、use、store 和 write 这六个 更大范围的原子性保证(经常会遇到),Java 内存模型提供了 lock 和 unlock 字节码指令 monitorenter 和 monitorexit 来隐式地使用这两个操作。这两个字节码指令反映到 Java 代码中就是同步块——synchronized 关键字,因此在 synchronized 块之间的操作也具备原子性。 可见性(Visibility) 可见性就是指当一个线程修改了共享变量的值时,其他线程能够立即得知这个修改 Java 内存模型是通过在变量修改后将新值同步回主内存,在变量读取前从主内存刷新变量值这种依赖主内存作为传递媒介的方式来实现可见性的,无论是普通变量还是 volatile 变量都是如此。普通变量与 volatile 变量的区别是,volat ile 的特殊规则保证了新值能立即同步到主内存,以及每次使用前立即从主内存刷新。 除了 volatile 之外,Java 还有两个关键字能实现可见性,它们是 synchronized 和 final 同步块的可见性是由"对一个变量执行 unlock 操作之前,必须先把此变量同步回主内存中" 而 final 关键字的可见性是指:被 final 修饰的字段在构造器中一旦被初始化完成,并且构造器没有把“this”的引用传递出去,那么在其他线程中就能看见 final 字段的值。 有序性(Ordering) Java 语言提供了 volatile 和 synchronized 两个关键字来保证线程之间操作的有序性,volatile 关键字本 身就包含了禁止指令重排序的语义,而 synchronized 则是由“一个变量在同一个时刻只允许一条线程对其进行 lock 操作”这条规则获得的,这个规则决定了持有同一个锁的两个同步块只能串行地进入。 先行发生原则 先行发生是 Java 内存模型中定义的两项操作之间的偏序关系,比如说操作 A 先行发生于操作 B,其实就是说在发生操作 B 之前,操作 A 产生的影响能被操作 B 观察到,“影响”包括修改了内存中共享变量的值、发送了消息、调用了方法等。 程序次序规则(Program Order Rule):在一个线程内,按照控制流顺序,书写在前面的操作先行发生于书写在后面的操作。注意,这里说的是控制流顺序而不是程序代码顺序,因为要考虑分支、循环等结构。 管程锁定规则(Monitor Lock Rule):一个 unlock 操作先行发生于后面对同一个锁的 lock 操作。这 里必须强调的是“同一个锁”,而“后面”是指时间上的先后。 volatile 变量规则(Volatile Variable Rule):对一个 volatile 变量的写操作先行发生于后面对这个变量的读操作,这里的“后面”同样是指时间上的先后。 线程启动规则(Thread Start Rule):Thread 对象的 start() 方法先行发生于此线程的每一个动作。 线程终止规则(Thread Termination Rule):线程中的所有操作都先行发生于对此线程的终止检测,我们可以通过 Thread::join()方法是否结束、Thread::isAlive()的返回值等手段检测线程是否已经终止执行。 线程中断规则(Thread Interruption Rule):对线程 interrupt()方法的调用先行发生于被中断线程的代码检测到中断事件的发生,可以通过 Thread::interrupted()方法检测到是否有中断发生。 对象终结规则(Finalizer Rule):一个对象的初始化完成(构造函数执行结束)先行发生于它的 finalize()方法的开始。 传递性(Transitivity):如果操作 A 先行发生于操作 B,操作 B 先行发生于操作 C,那就可以得出操作 A 先行发生于操作 C 的结论。 Java 与线程 线程的实现 内核线程实现 内核线程(Kernel-Level Thread,KLT)就是直接由操作系统内核(Kernel,下称内核)支持的线程,这种线程由内核来完成线程切换,内核通过操纵调度器(Scheduler)对线程进行调度,并负责将线程的任务映射到各个处理器上。 用户线程实现 完全建立在用户空间的线程库上,系统内核不能感知到用户线程的存在及如何实现的。用户线程的建立、同步、销毁和调度完全在用户态中完成,不需要内核的帮助。如果程序实现得当,这种线程不需要切换到内核态,因此操作可以是非常快速且低消耗的,也能够支持规模更大的线程数量,部分高性能数据库中的多线程就是由用户线程实现的。 混合实现 这种混合实现下,既存在用户线程,也存在轻量级进程。用户线程还是完全建立在用户空间中,因此用户线程的创建、切换、析构等操作依然廉价,并且可以支持大规模的用户线程并发。而操作系统支持的轻量级进程则作为用户线程和内核线程之间的桥梁,这样可以使用内核提供的线程调度功能及处理器映射,并且用户线程的系统调用要通过轻量级进程来完成,这大大降低了整个进程被完全阻塞的风险。 Java 线程的实现 Java 线程在 早期的 Classic 虚拟机上(JDK 1.2 以前),是基于一种被称为“绿色线程”(Green Threads)的用户线程 实现的,但从 JDK 1.3 起,“主流”平台上的“主流”商用 Java 虚拟机的线程模型普遍都被替换为基于操作系统原生线程模型来实现,即采用 1:1 的线程模型。 Java 线程调度 协同式(Cooperative Threads-Scheduling)线程调度 线程的执行时间由线程本身来控制,线程把自己的工作执行完了之后,要主动通知系统切换到另外一个线程上去。 线程执行时间不可控制,甚至如果一个线程的代码编写有问题,一直不告知系统进行线程切换,那么程序就会一直阻塞在那里。 抢占式(Preemptive Threads-Scheduling)线程调度。 如果使用抢占式调度的多线程系统,那么每个线程将由系统来分配执行时间,线程的切换不由线程本身来决定。 状态转换 新建(New):创建后尚未启动的线程处于这种状态。 运行(Runnable):包括操作系统线程状态中的 Running 和 Ready,也就是处于此状态的线程有可能正在执行,也有可能正在等待着操作系统为它分配执行时间。 无限期等待(Wait ing):处于这种状态的线程不会被分配处理器执行时间,它们要等待被其他线程显式唤醒 限期等待(Timed Waiting):处于这种状态的线程也不会被分配处理器执行时间,不过无须等待被其他线程显式唤醒,在一定时间之后它们会由系统自动唤醒。 阻塞(Blocked):线程被阻塞了,“阻塞状态”与“等待状态”的区别是“阻塞状态”在等待着获取到一个排它锁,这个事件将在另外一个线程放弃这个锁的时候发生;而“等待状态”则是在等待一段时间,或者唤醒动作的发生。在程序等待进入同步区域的时候,线程将进入这种状态。 结束(Terminat ed):已终止线程的线程状态,线程已经结束执行。 Java 与协程 内核线程的局限 切换、调度成本高昂,系统能容纳的线程数量也很有限。 用户线程切换的开销甚至可能会接近用于计算本身的开销,这就会造成严重的浪费 协程的复苏 协程的主要优势是轻量,无论是有栈协程还是无栈协程,都要比传统内核线程要轻量得多 需要在应用层面实现的内容(调用栈、调度器这些)特别多 Java 的解决方案 纤程,一种典型的有栈协程 重新提供对用户线程的支持 一段使用纤程并发的代码会被分为两部分——执行过程(Continuation)和调度器(Scheduler) 执行过程主要用于维护执行现场,保护、恢复上下文状态 而调度器则负责编排所有要执行的代码的顺序

2021 Apr 11 · 2 min

深入理解Java虚拟机::后端编译与优化

后端编译与优化 Java 世界里,虽然提前编译(Ahead Of Time,AOT)早已有所应用,但相对而言,即时编译(Just In Time,JIT)才是占绝对主流的编译形式 解释器与编译器 主流的商用 Java 虚拟机,内部都同时包含解释器与编译器 解释器与编译器两者各有优势 当程序需要迅速启动和执行的时候,解释器可以首先发挥作用,省去编译的时间,立即运行 当程序启动后,随着时间的推移,编译器逐渐发挥作用,把越来越多的代码编译成本地代码,这样可以减少解释器的中间损耗,获得更高的执行效率 解释器还可以作为编译器激进优化时后备的“逃生门”,当激进优化的假设不成立,如加载了新类以后,类型继承结构出现变化、出现“罕见陷阱”(Uncommon Trap)时可以通过逆优化(Deoptimization)退回到解释状态继续执行 内置即时编译器 客户端编译器 服务端编辑器 实验性 Graal 编译器 解释器与编译器搭配使用的方式在虚拟机中被称为“混合模式”(Mixed Mode) 分层编译 第 0 层。程序纯解释执行,并且解释器不开启性能监控功能(Profiling)。 第 1 层。使用客户端编译器将字节码编译为本地代码来运行,进行简单可靠的稳定优化,不开启性能监控功能。 第 2 层。仍然使用客户端编译器执行,仅开启方法及回边次数统计等有限的性能监控功能。 第 3 层。仍然使用客户端编译器执行,开启全部性能监控,除了第 2 层的统计信息外,还会收集如分支跳转、虚方法调用版本等全部的统计信息。 第 4 层。使用服务端编译器将字节码编译为本地代码,相比起客户端编译器,服务端编译器会启用更多编译耗时更长的优化,还会根据性能监控信息进行一些不可靠的激进优化。 热点代码 被多次调用的方法。 被多次执行的循环体。 编译器依然必须以整个方法作为编译对象 热点探测 周期性地检查各个线程的调用栈顶,如果发现某个(或某些)方法经常出现在栈顶,那这个方法就是“热点方法” 基于计数器的热点探测(Counter Based Hot Spot Code Detection)。采用这种方法的虚拟机会为每个方法(甚至是代码块)建立计数器,统计方法的执行次数,如果执行次数超过一定的阈值就认为它是“热点方法”。 回边计数器 统计一个方法中循环体代码执行的次数 当解释器遇到一条回边指令时,会先查找将要执行的代码片段是否有已经编译好的版本,如果有的话,它将会优先执行已编译的代码,否则就把回边计数器的值加一,然后判断方法调用计数器与回边计数器值之和是否超过回边计数器的阈值。当超过阈值的时候,将会提交一个栈上替换编译请求,并且把回边计数器的值稍微降低一些,以便继续在解释器中执行循环,等待编译器输出编译结果 编译过程 在第一个阶段,一个平台独立的前端将字节码构造成一种高级中间代码表 在第二个阶段,一个平台相关的后端从 HIR 中产生低级中间代码表示 最后的阶段是在平台相关的后端使用线性扫描算法在 LIR 上分配寄存器,并在 LIR 上做窥孔优化,然后产生机器代码 经典优化手段 无用代码消除(Dead Code Elimination) 循环展开 (Loop Unrolling) 循环表达式外提(Loop Expression Hoisting) 消除公共子表达式(Common Subexpression Elimination) 常量传播(Constant Propagation) 基本块重排序(Basic Block Reordering) 范围检查消除(Range Check Elimination) 空值检查消除(Null Check Elimination) 如守护内联(Guarded Inlining) 分支频率预测 (Branch Frequency Prediction) 提前编译器 ...

2021 Apr 10 · 1 min