作者：王雄,任婧,王晟,徐世中,赵阳明
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
智慧协同网络资源分配和业务管理(智慧协同标识网络系列)试读：
前言
互联网在设计之初其目的是为了提供端到端主机间的信息共享服务，因此，互联网络采用了以地址为中心的网络体系架构。互联网以地址为中心的网络架构因其具有开放、简单、易扩展等优点，在过去的30年中，互联网络取得的了巨大的成功。如今，互联网已成为支撑现代社会经济、科技、教育、医疗、文化等方面的最重要信息基础设施，是衡量一个国家科技和经济水平的重要标志之一。
随着宽带无线移动通信、高速光传输和云计算技术的迅速发展，各种高带宽、低时延、高安全和高可靠性要求的互联网络创新应用的不断涌现。然而，面对海量的高要求互联网应用，30多年前发明的以IPv4协议为核心技术的互联网面临着越来越严重的技术挑战，主要包括：内容分发效率低下、地址空间不足、安全性低、可移动性差等。维持现有互联网体系架构不变的前提下，要彻底地解决这些问题是非常困难的。为了解决这些问题，工业界和学术界认为下一代互联网络应该采用Clean State的网络架构。
为了应对现有互联网络的技术挑战，美国、欧洲等发达国家从20世纪90年代中期就先后开始下一代互联网研究。在国家重点基础研究发展“973”计划、国家高技术研究发展“863”计划、自然科学基金的大力支持下，中国从20世纪90年代后期就开始了下一代互联网络体系架构和关键技术的研究。在全球研究人员的共同努力和众多项目的资助下，下一代互联网络体系架构和关键技术的研究取得了很多有价值的研究成果，其中，有代表性的包括信息中心网络、软件定义网络、名址分离网络、标识网络等。
通过对目前提出的下一代互联网络架构分析，我们发现下一代互联网应具有智慧协同的能力。所谓智慧，是指网络应该具有感知传输的内容、及时准确感知网络状态的动态变化和感知不同网络应用特点的能力，并能根据感知到的信息做出优化的决策。而所谓协同，是指网络能够实现异构体系架构间的协同互通，能够协同各种可用手段来优化网络性能，以及支持多种网络优化目标的协同决策。在本书中，我们将具备智慧协同能力的网络称为智慧协同网络。智慧协同网络不是指某一种特定类型的网络，它覆盖的范围较为宽泛，凡是能具备智慧和协同特性的网络，我们都可以视为智慧协同网络。
资源分配和业务管理是智慧协同网络的关键问题之一，该问题关系到网络业务的需求是否能得到有效满足以及网络资源是否能得到有效的利用。本书主要讨论智慧协同网络中的资源管理方法，具体而言主要包括信息中心网络、SDN和数据中心网络中的资源分配和业务管理方法。全书可以分成3个部分，第1部分（第1章）主要介绍智慧协同网络的特点和架构原理。第2部分（第2～4章）分别介绍了信息中心网络中的缓存管理方法、数据中心网络Coflow的调度和路由问题，讨论了SDN中流量矩阵测量问题。第3部分（第5～7章）讨论了多种不同架构信息中心网络协同互通问题，介绍了网络资源管理中不同决策目标的协同优化问题和不同决策手段协同优化的网络资源管理方法。本书不能完全罗列智慧协同网络中的所有资源管理方法，本书各个章节的网络资源管理方法都是作者团队近年来的研究成果，是研究团队集体研究的成果总结。
在此，还特别感谢国家科技部国家重点基础研究发展计划（“973”计划）项目“资源动态适配机制与理论”（2013CB329103）、国家自然科学基金项目“面向ICN的网络级内嵌式缓存架构与配置管理方法研究”（61301153）和“全光网中基于监测迹的链路失效定位技术的研究”（61271165）、长江学者创新团队发展计划和高等学校学科创新引智计划“111引智计划”（B14039）的大力资助。本书的所有成果都是在这些项目的资助下完成的。
此外，由于编著者水平有限，书中难免有错漏，希望读者批评指正。作者2015年12月第1章概述1.1 现有互联网络存在的问题1.2 未来互联网络与智慧协同网络1.3 信息中心网络1.4 软件定义网络1.5 数据中心网络1.1 现有互联网络存在的问题
自20世纪70年代互联网发明以来，互联网已经全方位地融入人类生活的各个方面，极大地改变了人类沟通、工作和生活的方式。在互联网体系结构设计之初，其目的仅是为了在两台计算机之间实现数据传递。因此，诞生于20世纪70年代的互联网络体系架构采用主机到主机（Host-to-Host）的设计原则。在该原则中，每个主机都需要分配一个全网唯一的标识符（IP地址），网络节点根据数据分组中携带的目的IP地址来转发数据分组。由于网络只需要根据目的IP采用“尽力而为”的方式来转发数据分组，因此，如何保证数据传输的可靠性和安全性等复杂功能都由网络终端来完成。互联网络的这种设计思路非常简单，并具有较好的健壮性、开放性和可扩展性，这为互联网络的快速发展奠定了非常坚实的基础。
由于采用主机到主机的设计原则，现有互联网的通信过程主要解决网络中主机“在哪里”的问题，网络中的所有主机（电脑主机、交换设备以及移动终端等）都具有一个IP地址，以表示其位置信息。主机上的一切实体对象（内容、应用程序等）都与该主机地址绑定。当应用程序想要获取某个特定内容对象，必须首先指定拥有该内容对象的某个特定主机作为内容提供者，并给出其地址，然后网络负责将内容对象从指定的源主机地址递送到指定的目的地址。
随着互联网和网络应用的飞速发展，网络中需要递送的内容呈爆炸式增长的态势。根据思科公司的统计，在2013年，全球超过36亿互联网用户每月平均产生51.2 EB的网络流量，包括从网络中获取内[1]容对象或通过网络进行通信。根据中国互联网信息中心（CNNIC）的报告，截至2014年6月，中国互联网用户规模达6.32亿，普及率达[2]46.9%。随着大量新型网络应用的兴起（比如在线视频和在线游戏等），互联网流量将进一步显著增长。根据思科公司的预测，到2018年，将有超过40亿的互联网用户，平均每月将产生132 EB的网络流[1]量，其中79%的流量将由与内容递送相关的业务产生。
巨量的用户需求对互联网架构的性能也提出了新的挑战，比较突出的问题有以下几个方面。（1）无法保证用户自行指定的内容拥有者是最优的内容提供者
网络中往往有多个内容拥有者可以提供同一内容对象，但用户指定的内容拥有者可能并不是最优的提供者。如果用户指定的内容拥有者与其距离较远，用户将经历较大的服务时延，且需要较多的网络链路资源来递送内容；如果用户指定的内容拥有者负载较重，用户的内容请求可能无法获得响应。出现这一问题的根本原因在于，即便有很多主机拥有同一内容对象，用户往往仅能从有限的渠道（比如通过搜索引擎、网站链接等）获得部分主机地址信息。同时，用户也无法获得底层网络拓扑、时延等信息，因此，无法判断所知晓的内容拥有者是否在距离上或时延上是最优的。（2）无法避免在相同链路上多次传输重复的内容对象
当多个用户请求同一内容对象时，在以主机为中心的通信模式下，需要在每个用户和其指定的内容拥有者之间通过独立的端到端通信递送所需内容。而网络设备仅根据主机地址递交分组，因此，在多条端到端通信所经过的相同链路上，可能反复传输相同内容对象。（3）网络的安全性差
由于传统互联网将网络安全作为网络应用交给端系统完成，因此，最常采用的保障内容安全的方法是在端系统进行加/解密。这意味着内容对象的真实性取决于主机的可信度，往往需要一种额外的安全手段来识别、定位和连接此可信主机。网络本身无法保证其递送内容的真实性。此外，由于所有的通信都是基于地址来进行，网络的攻击者可以有针对性地对单个主机/地址来发动DDo S攻击。（4）网络的可控可管性差
为了保证网络的可扩展性，传统互联网通常采用分布式的控制协议，比如OSP、IS-IS、BGP等，然而这些分布式控制协议基本不能实现对流的精细化控制，并且任何细微的网络参数调整都有可能导致网络状态的震荡，引起网络的不稳定性。因此，如何保证业务的Qo S和精细化的网络控制及管理一直都是传统互联网络面临的主要问题之一。虽然为了增强网络的可控可管能力，IETF也提出了一些新的控制，比如MPLS，但是由于网络架构的缺陷，这些协议仍然面临配置和管理复杂的问题。（5）网络不支持节点移动
在传统互联网中，每个通信终端都有一个IP地址，所有的通信都是将数据从一个地址发往另一个地址。为了管理方便，分配给每个机构的IP地址都是固定不变的。因此，当一个终端从一个地方移动到另一个地方时，它的IP地址也必须重新分配，这必然导致了通信的中断。为了解决这一问题，通常的做法是在网络中增加移动代理，通过移动代理来管理用户位置的变化。
综上所述，传统互联网体系架构本身的局限性，导致了一系列很难解决的问题。虽然，目前这些问题都有一些方法可以解决，但这些方法都是通过在现有网络体系架构上打补丁的手段，其带来的问题是网络管理实体越来越复杂，造成网络管理非常困难。为了从根本上解决现有互联网的这些问题，更好的方法是根据现有网络需求，重新设计互联网体系架构。1.2 未来互联网络与智慧协同网络
近年来，世界各国都积极开展了未来互联网体系的研究工作，如美国自然科学基金委于2005年和2006年先后启动了GENI（Global [3]Environment for Networking Innovations，全球网络创新环境）计划[4]和FIND（Future Internet Network Design，未来互联网络设计）。[5]日本于2006年启动了AKARI计划，目标是在2015年之前研究出一个全新的网络架构。欧盟于2008年启动了FIRE（Future Internet [6]Research and Experimentation，未来互联网研究和实验）计划，拟对未来互联网架构和服务机制进行研究，并建立相应的测试平台。在GENI和FIND计划的基础上，美国自然科学基金委于2010年发布了FIA（Future Internet Architecture，未来互联网架构）计划，先后资助[7]了NDN（Named Data Networking，命名数据网络）、Mobility [8][9][10]First、NEBULA、XIA（e Xpressive Internet Architecture）、[11]Choice Net等5个重大项目，分别从不同侧面研究未来互联网的体系架构。2012年6月，美国总统奥巴马签署行政命令并启动US [12]IGNITE计划，进一步加强美国在未来互联网体系与应用方面的基础研究，以巩固美国在信息网络领域的领导地位。
我国也非常重视对未来信息网络体系结构和关键理论及技术的研究。国家“973”计划先后启动了“一体化可信网络与普适服务体系[13]基础研究”“可测可控可管的IP网的基础研究”“新一代互联网体系结构和协议基础研究”“面向服务的未来互联网体系结构与机制研究”和“可重构信息通信基础网络体系研究”等项目。国家“863”计划先后启动了“身份与位置分离的新型路由关键技术与实验系统”“三网融合演进技术与系统研究”等项目。国家自然科学基金委先后启动了“未来互联网体系理论及关键技术研究”“后IP网络体系结构及其机理探索”“未来网络体系结构与关键技术”等重点项目。
在全球研究人员的共同努力和众多项目的资助下，未来互联网体系架构的研究取得了很多耀眼的成果，比如，在GENI的资助下，美国斯坦福大学Nick Mc Keown带领的 Clean Slate 课题组于 2006 年提出了软件定义网络（Software Defined Networking，SDN）的概念[14]。SDN将网络的控制面和数据面进行分离，控制面单独地运行于逻辑上集中的网络控制器上，而数据平面则分布在各个通用的网络转发设备上，这种创新性的设计大大地增加了网络的可控可管性，并降低了网络设备的复杂性。在美国自然基金重点项目的支持下，美国加州大学洛杉矶分校的张丽霞教授带领的研究团队提出了NDN体系架[15]构。NDN直接对传输的内容进行命名，网络用户根据内容的名字来获取内容和服务，而路由器根据内容名来转发内容；在欧盟PSIRP（Publish-Subscribe Internet Routing Paradigm，发布订阅互联网路由范例）项目的支持下，P. Jokela等人提出了PSIRP网络体系架[16]构，与NDN类似，PSIRP也是以信息为中心的网络体系架构。在我国“973”项目的支持下，北京交通大学张宏科教授团队提出了智慧[17]协同标识网络。
除了网络体系架构上的支持外，为了提高网络的数据分发能力，适应快速变化的网络新业务，增强网络的可管控能力，未来互联网还必须具有以下能力。（1）感知传输内容
在传统互联网中，网络节点只关心数据分组中的地址信息，而不关心数据分组中携带的传输内容，从而网络无法缓存传输的内容，导致网络的带宽浪费和内容分发效率低下。为了提高网络对内容的分发效率，网络节点需要辨识经过的内容，并根据内容的特性对内容进行缓存和处理，从而节约网络带宽资源，提高内容的分发效率。（2）及时准确地感知网络状态
要有效地管理和优化网络，网络必须首先实时地感知网络的当前状态，比如网络流量的大小、网络链路的性能指标、网络节点和链路的负载情况等。传统互联网由于缺乏精细化的管理手段，网络状态的感知通常存在很大的误差，从而引起网络决策的失效。（3）感知和区分不同网络应用
网络中不同的应用有不同的特点，不同的应用对网络的需求也可能截然不同。因此，为了给各种网络应用提供最好的服务，网络首先需要感知不同网络应用的特点和需求，以便为网络的决策提供精确的输入。（4）不同网络架构间的协同互通
从前面的论述中可以发现，目前研究界已经提出了若干种未来互联网的体系架构，每种架构都有各自的优点和缺点。因此，未来互联网很可能将是由采用不同体系架构的网络组成。在这种情况下，不同网络架构间的协同互通就变得非常重要。（5）不同网络优化目标协同决策
网络中通常存在若干不同的优化目标，比如负载均衡、网络节能、网络使用代价等。这些优化目标通常还是相互矛盾的，即优化一个目标可能会损害另一个目标，比如，优化网络负载均衡就需要将流尽量均衡地分配到网络的各条链路上，然而这种优化方案却不利于网络的节能（因为网络节能需要尽量多地关掉网络节点和链路）。因此，为了达到一个理想的决策方案，网络的资源管理和调度方案需要考虑不同优化目标间的协同决策。（6）不同决策手段的协同决策
为了提高网络的资源利用和网络的服务性能，通常可以采用多种不同的手段，比如可以改变业务路由、改变网络的物理或逻辑拓扑等。然而，在实际的网络环境中，只通过单一的手段往往很难达到满意的优化效果。因此，为了增强网络的服务性能，网络必须能协同多种手段来进行决策优化。
综上所述，未来互联网需要具有智慧协同的能力。所谓智慧，是指网络应该具有感知传输的内容、及时准确感知网络状态的动态变化和感知不同网络应用特点的能力，并能根据感知到的信息做出优化的决策。所谓协同，是指网络能够实现异构体系架构间的协同互通，能够协同各种可用手段来优化网络性能，以及支持多种网络优化目标的协同决策。在本书中，我们将具备智慧协同能力的未来网络称为智慧协同网络。智慧协同网络不是指某一种特定类型的网络，它覆盖的范围较为宽泛，凡是能具备智慧和协同特性的网络我们都可以视之为智慧协同网络。
目前，研究界普遍认为未来智慧协同网络主要包含3种类型：信息中心网络、软件定义网络和数据中心网络。因此，在接下来的小节中，我们将分别介绍这几种网络的基本架构和原理。1.3 信息中心网络
作为一种重要的未来网络架构，内容中心网络（Content Centric Networking，CCN）可以解决传统互联网以主机为中心的通信模式与快速增长的内容递送需求之间的矛盾。内容中心网络是从网络架构的角度出发，提出将网络中的主机位置和内容对象进行解耦。内容对象具有唯一的标识，不再与主机地址进行绑定。用户直接使用内容名请求所需要的内容对象。网络设备可以识别内容名，并能够根据内容名、用户位置等信息找到适当的内容拥有者作为内容提供者。同时，网络可以利用多播和缓存等技术，避免在网络中重复递送相同的内容对象，也可以利用内容名的唯一性来验证内容对象的真实性。
目前已有大量内容中心网络架构被提出，在这里我们选择最具代表性的3种架构进行简述，即DONA（Data-Oriented Network [18][15][19]Architecture，面向数据的网络架构）、NDN和PURSUIT。（1）DONA[18]
DONA是较早出现的具有典型代表意义的网络架构，如图1-1所示。相对于传统互联网设计对主机的关注，用户实际上更关心内容对象本身，DONA认为新的网络架构需要满足如下要求。
①内容名的永久性：只要内容对象本身是可用的，其对应的内容名也就是一直有效不变的，即内容名不会随内容对象所在位置的变化而变化。
②内容对象的可用性：只要内容对象还存在于网络中，无需依赖特殊的应用层机制，网络可以为用户找到最合适的内容提供者。
③内容对象的真实性：网络需要为用户提供认证内容对象的机制，使其能够直接对内容对象的真实性进行认证，而不依赖于对获取内容对象的方式的认证。
基于以上3点，DONA对网络中内容对象的命名机制和名字解析系统进行了重新设计。在DONA中，内容对象被赋予永久的名字。为了满足永久性和真实性的要求，DONA采用了扁平自认证（Flat Self-Certification）的名字。DONA中的内容名根据主成分（Principal）构造，每个主成分都被赋予一对公私密钥（Public-Private Key）。每个内容对象都和一个主成分关联。内容名的格式为P:L，其中，P为主成分的公钥的加密散列值，用户可利用P验证主成分的身份；L为主成分为此内容对象所选的标签，该标签可为内容对象本身的散列值，因此，用户可以根据内容名校验内容对象本身。图1-1 DONA架构示意图
为了实现内容对象的高可用性，DONA重新构建了名字解析系统。该名字解析系统由多个解析处理器（Resolution Handler，RH）构成。各自治域（Autonomous System， AS）自行决定本自治域内的RH组织结构，逻辑上对外呈现单个RH，这些RH按照AS间拓扑关系进行连接。如图1-1所示，内容拥有者需要向名字解析系统发送注册信息完成注册（图1-1步骤①）。用户向名字解析系统查询能够提供所需内容对象的内容拥有者。名字解析系统根据内容名找到最合适的内容提供者，该内容提供者可能是已注册的内容拥有者或RH上的缓存（图1-1步骤②），内容对象则根据网络地址递送给用户（图1-1步骤③）。（2）NDN[15]
NDN及其前续项目CCN重新设计了网络协议栈，使用内容层取代传统IP层作为网络新的“细腰”，将IP技术作为内容层的一种底层技术。相对于DONA采用的扁平自认证名字，NDN 采用了类似于统一资源定位符（Uniform/Universal Resource Locator，URL）的可汇聚的层次化命名机制。这种层次化的名字更易于人类记忆，且能够反应出内容拥有者的组织结构特点。内容对象本身的安全性则依赖于附带在每个数据分组中的数字签名。需要注意的是，在NDN中，一个完整的内容对象被分成多个内容分片（Chunk）。每个内容分片具有独立的名字，同一内容对象的内容分片具有相同的前缀，用户需要针对每个内容分片发起请求，即内容分片是NDN中的最小操作单元，也是缓存节点的最小缓存单元。NDN架构示意如图1-2所示。图1-2 NDN架构示意图
NDN中有两种基本分组：请求分组（Interest Packet）和数据分组（Data Packet）。NDN重新设计了路由节点模型。路由节点维护3个数据结构：转发信息库（Forwarding Information Base，FIB）、待处理请求表（Pending Interest Table，PIT）和内容存储库（Content Store，CS）。其中，FIB记录请求分组的转发规则。NDN扩展了传统的链路状态协议使其可在域内扩散内容对象的可达性信息（图1-2（a）步骤①）。对于当前节点已转发但未收到回复的请求分组，PIT负责记录其所请求的内容分片名及收到该请求的网络接口，以完成请求汇聚和转发数据分组的功能。CS缓存当前节点已转发过的数据分组，以便为后续请求提供服务。
当收到用户发出的对内容分片的请求分组时，NDN节点首先查询本地CS（图1-2 （b）步骤①），如果CS中存有该内容分片，则将内容分片封装成数据分组递交给用户（图1-2（b）步骤②）；如果CS中没有缓存，则查询PIT（图1-2（b）步骤③）；如果该内容名在PIT中有记录，则说明转发过对同一内容分片的请求，因此，只需向该表项添加接收到当前请求分组的网络接口，然后丢弃该请求分组，这就实现了内容分片请求的汇聚（图1-2（b）步骤④）；如果PIT中没有该内容名对应的表项（图1-2（b）步骤⑤），则根据内容名查询FIB，进行最长前缀匹配，选择合适的网络接口向内容拥有者方向转发请求分组，同时在PIT中记录该请求分组所请求的内容分配名及接收到该请求分组的网络接口（图1-2（b）步骤⑥）。如果FIB中没有该内容名对应的表项，则丢弃该请求分组（图1-2（b）步骤⑦）。
当收到数据分组时，NDN节点首先使用精确匹配方式查询PIT中是否有对应内容分片的表项，如果没有，则直接丢弃该数据分片；如果有，则根据记录向所有接收过对应内容分片请求的网络接口转发该数据分组（图1-2（a）步骤③）。同时，当前节点需要根据缓存策略决定是否在CS中缓存该内容分片。（3）PURSUIT
PURSUIT（Publish Subscribe Internet Technology，发布订阅互[19][16]联网技术）和其前序项目PSIRP将传统应用层的订阅—发布模式引入网络层。PURSUIT中每个内容对象都属于一个或者多个Scope（域）。每个Scope都有自己的标识符，即Scope Identifier（域标识符SID）。为了区分不同的内容对象，在每个Scope内为每个内容对象选择唯一的名字，即Rendezvous Identifier（会面标识符，RID）。因此，在PURSUIT中，内容对象由
PURSUIT构建了一个会面系统（Rendezvous System）来扩散内容可达性信息和处理内容请求，该会面系统包括多个会面节点。内容拥有者向域内的会面点（Rendezvous Point，RP）发布内容对象的元数据信息（内容可达性信息扩散）（图1-3步骤①），用户向RP发送订阅信息（内容请求）（图1-3步骤②），RP负责在本区域内为两者进行匹配，必要时和其他域内RP进行协作（图1-3步骤③）。当匹配成功后，拓扑管理（Topology Management，TM）负责计算出一条从所选内容提供者到用户的转发路径（图1-3步骤④），并生成转发标识符（Forwarding Idenfier，FID）发送给内容提供者（图1-3步骤⑤）。利[20]用Bloom Filter技术，FID中携带有转发路径上所有链路标识的信息。内容提供者利用该FID生成数据分组，发送给用户。PURSUIT路由节点在收到携带FID的数据分组后，判断自己的哪些出链路包含在FID中，然后向这些链路都转发一份数据分组（图1-3步骤⑥）。1.4 软件定义网络
软件定义网络是由美国斯坦福大学Nick Mc Keown教授研究团队[14]提出的一种新型网络架构，它的核心思想是将网络的数据平面与控制平面分离开来，网络的控制平面运行于一个逻辑上的集中控制器上，而数据平面则运行于通用的网络转发设备上。[21]
图1-4所示为SDN架构的逻辑视图。从图1-4可以看出，SDN架构主要包括3个部分：基础设施层、控制层和应用层。图1-4 SDN架构的逻辑视图
基础设施层主要是由数据转发设备（比如SDN交换机）组成的，它是底层数据转发平面，主要负责网络中流表的数据处理、转发和状态收集，实现转发功能。
控制层主要是指SDN的网络控制器，它是SDN架构的核心部分。控制层分别通过南向接口和北向接口，与基础设施层和应用层进行交互。控制层通过北向接口获取不同应用的需求，通过南向接口配置网络转发行为和收集网络状态。
SDN的基础设施层主要由支持Open Flow协议（或其他控制协议）的SDN交换机组成。SDN交换机的逻辑结构如图1-5所示。一个SDN交换机主要包括两个部分：流表和安全通道。SDN交换机完全根据流表记录的转发端口来进行转发，而流表是由网络控制器计算出来的，并通过SDN交换机和控制器间的安全通道下发到SDN交换机上。一个流表项主要包含3个部分：匹配域、行为域和计数器。匹配域记录是用于匹配数据报文头的信息，包含12个匹配字段；行为域制定数据报文匹配后交换机要采取的行为（比如转发、丢弃、洪泛等）；计数器是用于统计与该流表项相匹配的信息数目。安全通道是SDN交换机和控制器间的加密逻辑连接，SDN交换机和控制器间的一切控制消息都通过这个安全通道来传输。图1-5 SDN交换机逻辑结构1.5 数据中心网络
随着信息化与大数据的发展，任务处理仅靠单机的运算已远不能满足用户的要求，于是要求有大量的计算设备来进行联合运算，共同[1~6]完成同一个任务。为此，很多机构便维护大量的计算设备、存储设备等来执行这些任务，或是将这些资源外租为他人完成计算任务。这就催生了数据中心的诞生。
数据中心中维护了大量的计算设备，为了使这些设备能协作地执行同一个任务，需要网络设备将它们连接起来，构成一个网络，这就是数据中心网络。从形式上看，数据中心和传统的机房很相似，但是其形式和内涵又远超传统的机房的范畴。数据中心所存放的大量计算和存储设备可以为用户提供大容量的存储、高速度的计算、多样化的服务。而用户对数据中心所提供的服务需求也越来越高，不仅是要有足够的存储空间和高速的运算，更要求数据中心所提供的服务要有高可靠性和可用性。通常，一个对租户提供服务的数据中心网络的典型结构如图1-6所示。图1-6 数据中心网络基本结构
在数据中心网络中，不同的服务器由接入层交换机连接，然后再通过数据中心网络的核心交换机来实现数据中心网络内部的互连，最后通过路由器和Internet相连。用户通过Interent访问数据中心网络中的资源。数据中心网络在接到用户的资源申请请求后，将用户所需的资源分配给用户，并帮助用户完成特定的任务。在任务完成后，数据中心网络通过Internet将用户任务的执行结果返回给用户。
一些大量的企业可能运营着不只一个数据中心，如亚马逊、IBM、阿里巴巴等，这些企业会把他们的数据中心再互连起来，提供一个功能更为强大的计算存储网络，这就构成了一个云计算系统。在这样一个云计算系统中，当用户在申请资源时，不需要关心所申请到的资源来自于哪个数据中心。这给服务提供商提供了更大的资源优化空间，有助于降低运营成本。尽管如此，数据中心仍然是云计算系统的基石，如何对数据中心网络进行优化，充分提高数据中心资源的利用率，为用户提供更好质量的服务，是数据中心网络研究中的关键问题。
对数据中心的优化，可以分为以下两大类。（1）对计算资源进行优化[22,23]
这类优化主要包括CPU、内存等资源的分配以及任务之间的调度等。这类研究的重点是如何充分利用主机资源，以提高数据中心的处理能力，或是追求任务之间的公平性。（2）对网络资源进行优化
当不同的主机协作完成同一个任务时，不同主机间需要进行通信，传递这一任务执行过程中间的数据。因此，对网络资源的优化，使数据传输更为快速，可以提高数据中心的任务吞吐率和服务质量。对网络资源进行优化主要是要通过对网络中流量的路由和调度进行优化，从而提高网络利用率，进而提高数据中心的利用率，提高任务吞吐率。
当前多数研究工作都关注前一种情况，即对数据中心的计算资源进行优化。但有研究表明，当数据中心执行一个任务时，网络传输时间通常会占到这个任务整个完成时间的33%甚至于50%，因此，网络资源的优化在数据中心的研究中仍然是一个重要的问题。本书的后续章节将针对后一种情况，探讨如何通过对网络中流量的路由、调度，对动态数据中心网络的拓扑进行控制，对光数据中心网络中的波长分配进行优化等方式，提高网络资源的利用率。第2章信息中心网络缓存管理2.1 缓存感知的路由策略2.2 路径上协作缓存管理策略
在传统互联网中，传输的内容/信息是封装在IP报文中，网络节点只能根据IP报文头部的目的地址信息来转发数据分组，而无法感知和识别IP报文中封装的内容。因此，传统互联网不能在路由器节点上缓存经过的内容。另一方面，大量的研究表明，互联网上传输内容的[24]流行度服从Zipf分布，即大量用户请求都集中在少数内容上。在这种情况下，网络将传输大量的重复内容，造成带宽的严重浪费，并且即使是用户请求的重复内容，也必须到内容源去获取，这必然造成数据获取时延的增加。随着网络流量的急剧增加，互联网在内容分发方面非常低效的缺陷也日益凸显。为了解决这一问题，目前广泛使用的方法是在应用层上构建内容分发系统，比如CDN、P2P、Web Cache等。但这些解决方案都是构建在应用层上，很难与网络协同高效地工作。
信息中心网络对内容进行命名，网络用户直接使用内容的名字来获取内容而不是内容所在的地址，网络节点根据内容的名字来转发数据报文。这种设计的是网络节点可以识别经过的内容，并根据内容的特性（如流行度）对内容进行缓存。为后续请求提供服务。用户因此有机会从离自己更近的网络设备获得所需要的内容，而无需向内容拥有者提出请求，从而显著减少用户获取内容对象经历的时延，并节省带宽。因此，信息中心网络的性能改善在很大程度上取决于网络内置缓存的缓存管理机制设计，而网络性能会影响到内容中心网络是否能[25]够被实际部署。2.1节介绍缓存感知的信息中心网络路由策略，2.2[26]节介绍信息中心网络在线缓存管理策略。2.1 缓存感知的路由策略2.1.1 研究动机
缓存感知的路由策略需要解决两个问题：一是如何获得网络中已缓存的内容分片信息（即缓存状态）；二是如何合理选择转发路径以便有效地利用网络中的缓存。
在已知各缓存节点的当前缓存状态后，转发路径的选择将直接影响获取所有内容分片的平均跳数。以图2-1为例，网络中有两个内容1218拥有者（记为pub、pub）和8个路由器（记为R～R）。假定两个内容拥有者都可以提供同一个内容，该内容分为4个内容分片（分别1234记为c、c、c、c）。每个路由器仅能缓存一个内容分片，且同一路径上的缓存节点相互协作以缓存不同的内容分片。网络中的用户都在请求该内容的分片。图2-1所示为在网络运行一段时间后各节点缓存的内容分片情况。图2-1中NC为采用随机线性网络编码时，各节点1缓存的编码分片对应的编码向量。此时用户sub发出请求，图中展示了从两个内容拥有者到此用户的3条可能路径。表2-1给出了在不同路由策略下获得不同分片的跳数和获得全部内容分片的平均跳数。图2-1 缓存感知路由策略示例表2-1 不同路由策略的平均跳数
①当仅采用从用户到所有内容拥有者中跳数最少的最短路径（路径①）时，获取所有分片的平均跳数为2.75。如果采用非最短路径的路径②，因为路径上的缓存节点数目较多，取得所有分片所需的平均跳数较小。这说明合理选择获取内容分片的路径可能减少网络带宽的消耗。
②如果同时采用两条路径（路径①&②或①&③），用户获得所有内容分片的平均跳数减少为2.25。相对于从单一路径获取所有内容分片，同时利用多条路径（即使只是部分分离的路径）上的缓存将进一步减少递送内容所消耗的带宽。
③如前所述，网络内置缓存散布于网络各处，很难协同所有的缓存节点。即使同一路径上的缓存节点相互协作，不同路径的缓存节点也很可能缓存相同的内容分片的副本。按照图中各节点的缓存状态，简单地采用3条路径（路径①&②&③）无法进一步改善性能。
④随机线性网络编码能够以较大概率保证网络各编码分片线性独立，图2-1所示为某次实际实验中随机选择的编码向量。由于用户可以从最近的4个网络内置缓存获取4个线性独立的编码分片，因此，获得所有内容分片的平均跳数减为1.75，显著减少了网络带宽的消耗。
此例说明我们需要设计有效的缓存感知路由策略来减少递送内容所消耗的网络带宽。2.1.2 缓存感知的K-Anycast路由策略
基于之前的讨论，本小节提出了一种缓存感知的K-Anycast路由策略（Cache Aware K-Anycast routing，CAKA）。同时，将采用了网络编码的CAKA策略记为CAKA-NC。
CAKA的基本策略主要包含两个部分。
①已缓存的内容分片信息（即缓存状态）的获取机制。该机制会针对特定内容实时地探测多条路径，收集路径上各缓存节点缓存了该内容对应的哪些内容分片，即收集该内容对应的各内容数据分片的缓存情况（副本的数量及其位置）。其目的是在尽量少增加开销的情况下，探测尽量多的缓存节点。
②缓存感知的K-Anycast路由算法。其目的是在获知所选路径上缓存节点的缓存状态后，选择合理的路径转发请求分组，以便有效地利用网络中的缓存。
CAKA首先针对所请求内容探测各缓存节点的缓存状态，然后根据探测信息，再针对各内容分片发出请求。这是典型的请求—响应[7]模式。在类似NDN这种采用请求—响应模式的内容中心网络中部署CAKA较为容易。探测过程可以在请求第一个内容分片时完成。而[19]PURSUIT采用订阅—发布模式，其原始方案并不支持内容拥有者和用户之间的交互，内容拥有者直接推送整个内容给用户。因此，扩展PURSUIT架构以支持CAKA的困难较大。本节将详细给出如何扩展PURSUIT的双向通信机制以实现CAKA的基本交互。
图2-2所示为在PURSUIT中实现CAKA的基本通信流程。内容管理模块（会面节点RP）判断需要向某一用户递送新发布的内容后，通知路由管理模块（TM）计算路由。TM将调用m-PDP（m Partially Disjointed Paths）算法，该算法负责选择多条探测路径。这些路径将尽量涵盖更多的缓存节点。TM将这些路径的FID下发给对应的内容拥有者（图2-2步骤③）。图2-2 CAKA在PURSUIT中的通信流程
得到FID的内容拥有者将向用户发送一个探测分组（图2-2步骤④）。该探测分组扩展了PURSUIT双向通信协议中的协商分组，记为Prob M（Probe Message，探测消息）。缓存节点在收到探测消息后，会根据所请求的内容名检查自己缓存了该内容的哪些内容分片（当采用CAKA-NC时，将检查自己缓存了多少个线性独立的编码分片），并将此信息附带在探测消息中。
用户收到多条路径上所有缓存节点的缓存状态后，将调用k-PS（k Path Selection）算法。该算法将根据各节点的缓存状态，选择最终发送内容请求的路径。用户利用探测分组中携带的协商信息与所选路径对应的内容拥有者建立双向通信信道（图2-2步骤⑤～步骤⑦）。然后用户沿着所选路径发送内容分片的请求分组，指定具体请求的内容分片编号（CAKA）或者所请求的编码分片数量（CAKA-NC）（图2-2步骤⑧）。缓存节点在收到请求后，如果本地有缓存，则会返回所请求的内容分片（CAKA）或本地缓存的线性独立的编码分片（CAKA-NC）。
2.1.2.1 已缓存内容分片信息的获取机制
CAKA获取已缓存的内容分片信息（缓存状态）的机制涉及两方面：收集已缓存内容分片信息以及选择被探测路径。（1）收集已缓存内容分片信息
为在所选探测路径上收集所请求内容的所有内容分片缓存情况，我们扩展了PURSUIT双向通信协议中的协商分组来携带探测信息。图2-3所示为Prob M的基本结构。其中，PURSUIT头部包括本探测分组的转发标识（TO_SUB_FID），表明本分组是探测分组的类型选项（PUBLISH_PROB）以及内容名信息（SID的数量和所有SID值）。双向通信信息中携带的是用于建立反向信道所需要使用的ID（图2-2中2步骤⑤和⑥所使用的ID）。图2-3 ProbM结构
探测信息用于携带各缓存节点的缓存状态。缓存节点收到ProbM后，根据SID查询本地缓存是否缓存了该内容对应的内容分片。如果有，则在ProbM后添加节点编号和缓存状态。如果采用CAKA，将记录已缓存内容分片的编号，该字段的长度可以根据网络的分片机制进行调整；如果采用CAKA-NC，仅需要记录目前本缓存节点缓存的该内容对应的编码分片数量。（2）探测路径的选择算法（m-PDP）
m-PDP算法的主要目的是找到m条探测路径。所选择的多路径集合需要满足以下要求。
①避免选择过长的探测路径。虽然长路径上的缓存节点数量更多，但当无法从这些缓存节点获得所需内容分片时，请求分组会被递送到距离更远的内容拥有者，从而增加网络时延和带宽消耗。
②能够利用不在最短路径上的缓存。缓存了所需内容分片的节点，3可能不在用户到任何内容拥有者的最短路径上，比如图2-2中的R，但这些节点可能离用户更近。
③尽量让所选路径彼此分离。这是为了可以覆盖更多的缓存节点。
假设网络中一共有n个网络节点和h个内容拥有者。m-PDP算法的主要步骤如下。
① 在原始网络链路权重下，第j=0 次计算所有拥有该内容的内容i拥有者到用户
② 记L为当前最短路径的长度。
③ 设备选路径集合，即min将所有路径长度小于L+Δ的路径加入备选集合，其中，Δ用来约束路径长度。
④ 如果|ψ|≥m ，跳转步骤⑧。
⑤ j=j+1，调整网络链路权重值，增大ψ集合中所有链路的权重，设路径p∈ψ的第k条链路的权重为，其中，j为第j次权重调整增量，有，（0≤α≤1且W是一个很大的值）。
⑥ 基于新设置的权重，第j次计算所有内容拥有者到用户间的最短路径，重新更新ψ。
⑦ 如果|ψ|＜m，跳转到步骤④。
⑧ 输出ψ。2
由于需要计算m条路径，在最坏情况下，算法复杂度为O(nm)，n是网络中所有节点的数量。单纯计算一条最短路径的算法复杂度为2O(n)。由于实际网络中分离路径数m是有限的，实验中只选择了3条，因此，m-PDP算法增加的计算开销是可接受的。
2.1.2.2 缓存感知的K-Anycast路由算法
用户收集到所有探测路径上已缓存的内容分片信息（缓存状态）后，需要决定从每个路径上获取哪些内容分片。k-PS算法的目的是根据收到的缓存状态以及缓存可能被替换的可能性来选择最终获取内容的路径。k-PS算法的主要步骤如下。l
① 为每条路径l∈ψ，设Ω=∅，其中，ψ为m-PDP算法得到的路径l集合，Ω为从路径l上所获取的分片集合。l
② 对每条路径l上的节点集合N，按照节点与用户间的距离按升序排列。v
③ 为内容CO的每个分片i计算从每条路径l∈ψ上的每个节点j∈li,jΝ获取该内容分片的概率p。
④ 计算从每条路径l上获取分片i的代价，其j中，d表示从节点j到用户的距离或者代价。**
⑤ 选择代价最小的路径l获取分片i，并将分片i加入路径l的请求分片集合中。
⑥ 如果还有内容分片没有选择路径，则跳转到步骤③；否则结l束算法，输出所有Ω。lv
在步骤③中，沿着路径l∈ψ，从节点j∈N获取到内容CO分片i的概率表示为i,ji,jl
其中，r是一个(0,1)变量，r=1表示Prob M中记录了节点j∈N缓i,j存有分片i；β则表示分片i在节点j被替换的概率。
算法的步骤②中需要根据节点与用户的距离重新排序，在最坏情况下（网络中所有n个节点都在一条路径上），复杂度为O(nlogn)。步骤③～步骤⑥需要计算从路径上每个节点获取每个分片的概率，在最坏情况下（网络中所有节点都在备选路径上），复杂度为O(hn)，其v中，h为内容CO对应的分片数量。
如果采用CAKA-NC，由于Prob M中仅记录了线性独立编码分片的数量，根据从每条路径上可获得的独立编码分片总量占总分片数量的比例，确定从每个路径上获取编码分片的数量，并不调用k-PS算法。
当用户收到Prob M并由k-PS算法确定了要从每个路径获取的内容分片后，用户将发送内容分片请求信息。对于CAKA，用户将指明从每条路径上获取的内容分片的序号。当收到请求后，缓存节点检查本地缓存，如果有所指定的内容分片，则返回内容分片，同时在请求分组中记录该分片已经发送给用户，从而避免后续节点发送重复的内容分片。对于CAKA-NC，缓存节点将自己缓存的编码分片都发送给用户，并在请求分组中记录本节点已发送了多少编码分片。如果用户没有接收到足够的编码分片，将向最近的内容提供者请求剩余的编码分片。
2.1.2.3 CAKA-NC的编码机制
CAKA-NC采用了随机线性网络编码（Random Linear Network Coding，RLNC）。缓存节点采用RLNC时，不需要知晓网络拓扑，而是独立地选择局部编码向量。利用RLNC，源节点（内容拥有者）和中间节点（网络缓存节点）对属于同一内容的不同内容分片进行编码操作，而目的节点（用户）则进行线性解码操作。（1）内容拥有者的操作v1h
记内容CO的原始分片记为{c,…,c}，内容拥有者从有限域F(q)1h（q是有限域F的大小）中，选择h个线性无关的编码向量{v,…,v}，并利用编码向量和原始内容分片生成h个编码信息，即n,ln
其中，v是向量v的第l个元素。内容拥有者将同时发送编码分nn片c′和其对应的编码向量v。（2）网络缓存节点的操作
每个缓存节点j需要确定本地流行内容的集合，从而确定在本地vk,j可以为内容CO缓存的编码分片数量n。在收到新的编码分片后，缓存节点将判断该编码分片是否与缓存中已有的编码分片线性独立。仅当收到的编码分片与已存编码分片是线性独立的，已存编码分片数量k,j小于n，且还有空余的缓存空间或者该内容的流行度足以替换其他内容时，缓存节点才缓存该编码分片。v
假设在发送编码分片前，缓存节点j缓存了内容CO的t个线性独1t1t立的编码分片{c′,…,c′}，以及其对应的全局编码向量集合{v,…,v}。1t缓存节点将在 (F)q中随机选择局部编码向量a=[a,…,a]，并生成新的编码分片c″和全局编码向量v″。
缓存节点向用户发送[v″|c″]。v
用户的操作：当用户收到同一个内容CO的h个线性独立的编码分片时，可解码并获得h个原始内容分片。
假设用户最终收到h′个线性独立的编码分片，文献[27]证明了收到的编码分片线′性独立的概率可表示为
其中，r为min(h,h′)，q是有限域F的大小。2.1.3 实验设计及结果
为了验证CAKA及CAKA-NC的效果，首先通过仿真实验评估其在大型网络拓扑下的性能。然后在实际系统中实现了CAKA，验证了其可行性。
2.1.3.1 仿真条件
采用离散事件驱动仿真软件OMNe T++实现了3种不同的策略：①原始PURSUIT基于推送的策略，即不利用网络内置缓存，记为Original；②在PURSUIT中利用路径上的缓存，记为On Path；③在PURSUIT上实现CAKA和CAKA-NC策略。因为这里考察的是缓存感知的路由策略，所以假设所有缓存节点都独立地执行缓存操作，采用LCE策略缓存所有转发的每个内容分片，且缓存节点均采用LRU缓存替换策略替换最久未被请求的内容分片。[28]
实验中，采用了两个真实网络拓扑（Abilene和Verio）和一个虚拟网络拓扑（Scale-Free），网络参数见表2-2。表2-2 网络仿真拓扑
为了简化描述，设置所有路由器均具有缓存能力，且每个路由器4都连接一个内容拥有者和多个用户。实验中一共有10个内容，为每个内容随机选择3个内容拥有者。与文献[15]类似，实验中每个内容大小为6 MB，且每个内容被分为6个等长的内容分片。每次实验中，5所有用户一共产生10个请求，满足Zipf分布。
2.1.3.2 仿真结果（1）性能改善（获取每个内容分片的平均跳数）
图2-4所示为不同网络拓扑下，采用不同的缓存策略时，获取所有内容分片所需的平均跳数。图2-4 获取内容分片的平均跳数随节点缓存能力的变化关系图2-4 获取内容分片的平均跳数随节点缓存能力的变化关系（续）
从图2-4中可以看出，使用网络内置缓存可以减少获取每个分片所需的平均跳数。随着节点的缓存能力以及缓存节点数目的增加，网络中可缓存的内容分片总数增加，这使得缓存可以响应大部分请求分组，从而减少获取内容分片的平均跳数。即使仅利用单条最短路径上（On Path）的缓存，在3个拓扑中最多可分别得到27%、40%和39%的性能增益。
随着可使用路径数量的增加，用户可以利用更多的缓存，因此，也可以减少获取内容分片的平均跳数。相对于PURSUIT原始策略，采用两条路径的CAKA策略最多可得到32%、43%和45%的性能增益；而采用3条路径时，则可获得39%、44%和55%的性能增益。
此外，CAKA-NC可进一步改善获取每个内容分片的平均跳数。与采用了3条路径的CAKA策略相比，采用两条路径的CAKA-NC策略在大部分情况下能获得更好的性能。相比于PURSUIT原始策略，在不同拓扑下，采用两条路径的CAKA-NC最多可得到37%、46%和63%的增益；而采用3条路径的CAKA-NC则最多可获得53%、52%和77%的增益。（2）开销
为考察不同策略下获取一个完整内容所需的平均网络开销，我们考虑获得一个内容所涉及的3种类型的开销。
①所有控制消息，包括探测分组、请求分组等。
②所有数据分组的头部，包括协议字段以及CAKA-NC携带的全局编码向量。
③CAKA-NC因为没有收到足够线性独立的编码分片而发出的重传请求和响应。
设集合P表示为获得一个完整内容在网络传输中的所有分组集合。实验结果如图2-5所示。图中所示为不同策略下获取一个完整内容的总加权开销（Total Weighted Over Heads，TWOHs）。ii
其中，O为第i个分组中开销（字节数）；H为此分组所通过的链ii路数；O H反映了为完成内容递送任务所引入的开销，在网络传输中消耗的网络带宽。
从图2-5中可以看到，相比于原始PURSUIT直接推送的策略，利用一条最短路径上缓存的策略，在3个拓扑中最多会增加45%、34%和44%的开销。但随着网络节点的缓存能力增加，分组的平均跳数减少，相应的加权开销可以降到20%、13%和15%。而随着使用的路径数的增多，探测分组和请求分组的数量也相应增加，因此，网络中的总加权开销也相应增加。但随着缓存能力的增加，多路径策略可以使i用户在更近的缓存获得所需内容分片，即递送内容的跳数H减少，因此加权开销也随之减小。图2-5 获取内容的平均加权开销随节点缓存能力的变化关系
为了进一步考察网络开销，定义了总加权净荷（Total Weighted Pay Loads， TWPLs）。ii
其中，U指分组中携带的内容数据净荷，H为分组所有经过的链ii路数，U H表示递送内容净荷时需要消耗的网络带宽。
在实验中，我们考察了不同缓存策略与Original策略相比较，减少的TWPLs和增加的TWHOs。减少的TWPLs表示为PURSUITOriginalCompared Scheme
reduced TWPLs=TWPLs−TWPLs （2-8）PURSUITOriginal
其中，TWPLs 为PURSUIT原始策略的总加权净荷值，Compared Scheme而对比策略的总加权净荷值表示为TWPLs 。减少的TWPLs体现了为了获得同一内容，利用了网络内置缓存、多路径或网络编码所能节省的网络带宽。
同样，增加的TWOHs表示为Compared SchemePURSUITOriginal
increased TWOHs=TWOHs−TWOHs （2-9）Compared Scheme
其中，TWOHs 为所选对比策略的总加权开销，
试读结束[说明：试读内容隐藏了图片]