基于互联网的计算答案.docx

基于互联网的计算-刘晓芳1 (1) 什么是SOA？SOA有什么特点? 请例举几种 SOA的实例； (2) 什么是Web Service？简要说明Web Services中Service 的含义。答：（1）SOA的定义:SOA(service-oriented architecture)被设计为提供这样的灵活性：将业务过程以及下层的IT基础设施作为一个安全的、标准化的组件（即服务）,这些组件可以通过被重用的方式来适应不断变化的业务优先级。 SOA的特点有：服务是自包含和模块化的服务支持互操作服务是松耦合的服务是位置透明的服务是由构件组成的合成模块SOA的实例：CORBA（Common Object Request Broker Architecture,公共对象请求代理体系结构）DCOM（Distributed Component Object Model分布式组件对象模型）J2EEWWW （2）Web Service是一种用URI标识的软件应用，它的接口和绑定可以通过XML文档定义、描述和发现。Web Service支持通过基于Internet的协议、并利用基于XML的信息与其他软件进行直接的交互。Service的含义：应用程序或者业务的不同功能单元，这些功能单元作为一个独立的实例存在，并且通过松耦合、基于消息的通信模式和其他应用程序或者服务进行交互。2. (1) 请给出Web Services 的体系结构图（包含角色和行为的三角图），并简述各角色和行为的含义。 (2) 下图是Web Services 的协议栈，将其补充完整；并简述栈中每一层的作用。 （1）角色：（自己翻译的）服务需求者（service requester）：一个应用程序、软件模块或者需要服务的另一个服务。服务提供者（service provider）：接受和执行服务使用者的请求的可寻址的网络实体。服务中介（service broker）：包含一个可用服务库并且为感兴趣的服务使用者提供服务提供者接口的查找。行为：Publish发布:一个服务的描述只有被发布，该服务才可以被服务请求者发现和调用。使用的协议是WSDL。Find/Search查找:服务请求者通过向服务注册中心查询来定位符合自己要求的服务。使用的协议是UDDI。Bind&Invoke绑定和调用:服务请求者根据服务注册中心提供的服务描述信息来调用服务。使用的协议是SOAP。（2） Web Service协议栈中各层的作用： Discovery：服务发现层:服务请求者查询可以调用的服务。 Composition：服务组合层:组合Web服务，从而可以形成新的Web服务。 Service Description：服务描述层:为调用服务提供了具体的方法。包含服务的接口和实现细节。 XML Messaging：XML信息层:用于调用服务时传送信息。 Network：网络传输层:采用广泛使用的协议传输消息，并且能够顺利通过代理防火墙。3. (1)什么是WSDL？WSDL定义了service 的哪些个方面？分别对应于WSDL中的哪些元素？WSDL文档被分为哪两种类型？ (2)请说明binding元素与portType 之间的关系，为什么说“Binding element is generic ”? （1）WSDL一种用来定义网络服务的XML格式，该XML格式将网络服务定义为一组在信息的层次上操作的终端节点，这些信息包含基于文档的信息和基于过程的信息。WSDL定义了Service的以下三个方面：a. 服务是什么（服务接口）。对应着portType与message和type元素。 b. 访问规格（怎样使用服务）。对应着binding元素。 c. 服务的位置（服务在哪里）。对应着port及service元素。WDSL文档分为以下两种类型： a. 服务接口 b. 服务实现（2）一个binding元素为一个portType描述了一个特定的的通信协议。每个binding与一个portType对应，binding元素描述了portType中每个操作里面每个消息的具体通信协议。Binding element is generic（Binding元素是泛化的）因为它只是简单地定义了描述绑定细节的框架。实际的绑定细节通过使用扩展元素的方式提供。这种架构允许WSDL随着时间的推移逐步演化，因为元素可以在预定义的slot中使用。4 下面给出的代码段是一个功能块的 JAVA语言描述，请给出该描述的 WSDL描述，包括消息定义和portType定义（消息格式使用 RPC模式）. 5 （1）什么是SOAP？特点？SOAP消息调用有哪几种模式？SOAP提供了基于XML的通信框架，这个框架有什么特点？ （2）画出SOAP消息的结构，并简要解释各部分的作用；(1)SOAP（Simple Object Access Protocol）简单对象访问协议（SOAP）是一种轻量的、简单的、基于 XML 的协议，它被设计成在 WEB 上交换结构化的和固化的信息。 SOAP特点：可扩展性 可在多种底层网络协议上使用 独立于编程模型 SOAP消息调用的模式：理论上好像是四种组合吧document/literaldocument/encodedrpc/encodedrpc/literal (2)SOAP 消息的结构： a. SOAP 消息的头部是可选的，它包含了关于 SOAP 消息的特定应用程序信息（例如身份认证、付款等）。 b. SOAP 消息体是必须的，它包含了实际的 SOAP 消息，该消息是向最终的终端节点发送的。 6. (1)在将SOAP与WSDL绑定时，SOAP定义了两种消息格式：Document和RPC ，请简要说明这两种方式的不同之处，并分别指出下面两个SOAP消息属于哪种式？SOAP Message 1SOAP Message 2（2）（开放式问题）谈谈你对SOAP协议的理解并说明为什么将SOAP作为Web Services的基本传输协议，而不采用HTTP和RPC ？ (1)将SOAP与WSDL绑定时，SOAP定义的两种消息格式:a. 文档方式：表明消息体简单的包含了一个 XML 文档，该文档的格式需要是 发送者和接受者事先商定的。 b. RPC方式：表明消息体包含了对于一个方法调用的 XML描述。Message 1 是 RPC 方式， Message 2 是文档方式。(2)SOAP 有助于实现大量异构程序和平台之间的互操作性 , SOAP是把成熟的基于 HTTP 的WEB技术与XML的灵活性和可扩展性组合在了一起。在Web中简单比效率和纯技术重要。HTTP 的优势在于它可以非常容易的创建HTTP-GET和HTTP-POST消息，并且响应它不需要复杂的 XML 处理，因此是不使用 SOAP 时的最好选择,但是 HTTP 不能够利用 HTML 调用XML 以复杂 数据类型为参数的 Web 服务。而这正是SOAP的优点所在，同时 SOAP 向 HTTP提供了显式绑定，因此可以将 SOAP在HTTP之上使用。RPC 的优点是通过直接远程访问过程,避免烦琐的打包和解包的过程,并且不依赖于某种特定的协议但RPC一般用于应用程序之间的通信，而且采用的是同步通信方式，因此对于比较小型的简单应用还是比较适合的，因为这些应用通常不要求异步通信方式。但是对于一些大型的应用，这种方式就不是很适合了，因为此时程序员需要考虑网络或者系统故障，处理并发操作、缓冲、流量控制以及进程同步等一系列复杂问题，所以需要使用 SOAP. 7(1)给出UDDI数据模型的主要元素，并给出他们直接的关系； (2)UDDI定义了一套怎样的机制使得我们能够与其交互？ (3)tModel 结构有何描述能力？它在UDDI中的两种主要应用是什么？(1) UDDI 数据模型的主要元素:a. 业务实体。通过描述其信息（例如名字、描述和联系）和它提供的服务，表示一个 物理业务。b. 业务服务。表示一个业务提供的服务。 c. 绑定模版。指出如何调用一个服务。 d. 技术模型 (tModel) 。表示唯一的概念或者构件。直接关系: (2) 我们与 UDDI 交互的机制, 通过 UDDI API 的方式。a. UDDI 提供了一种程序设计模型和架构，定义了与服务注册中心通信的规则。b. 通过已经指定好的 SOAP 接口集合与 UDDI 进行交互。 c. 在 UDDI 的规范中，所有的 API 都利用 XML 进行定义，打包成一个SOAP 消息，然后利用 HTTP 协议发送。 (3) tModel 结构的描述能力:tModel 结构用于提供一种描述能力，这种能力描述了与某个规范、概念甚至一个共享设计的相符程度。 在UDDI中的两种主要应用： 定义技术指纹可以在UDDI注册中心建立唯一的技术标识，这个标示是预先确定的规范，它就是tModel定义抽象命名空间引用有的结构是用于定义组织标示和分类信息的，在这些结构中引用的tModel视为是抽象命名空间引用。8 (1) BPEL中与流程交互的服务被定义为partner ，按照交互类型的不同partner有不同的类型，简要说明这三种类型，并在下图中指明每个 partner 所属类型； (2) 简要说明BPEL中的顺序、分支、重复、并发等结构化活动； (3) 什么是BPEL 抽象流程？它与具体流程相比有什么特点？你认为它适合应用在什么场景？BPEL 中 partner 的三种类型:Parter 是与一个流程交互的服务。 a. 被调用 partner :在流程的算法中作为一个完整的部分被调用的服务。 b. 客户机 partner :调用流程的服务。 c. 第三类 partner : 既可以由流程调用, 也可以调用流程的服务。图中partner A是第三类partner；partner B是被调用partner。BPEL中的结构化活动: 定义步骤的有序序列 用现在常见的“case-statement”方法产生分支 定义循环 执行可选路径中的一条 指定一些步骤应该并行执行抽象流程是部分被指定的流程，通常不是用来执行的。它具有以下特点：a. 可以通过抽象屏蔽操作细节b.当描述业务协议的公共部分时，可以使用BPEL的概念来反应抽象程度的不同。c.只处理协议相关的数据d. 采用非确定数值来隐藏行为的私有部分应用场景：它具有良好的形式和完整的表达能力，因此可以用来规定操作细节上程度不一的流程。9(1)Semantic Web 的核心概念是什么？它给Web Services带来什么启示？ (2)RDF 定义了独立于域的表达处理元数据的基础，RDFS提供了描述特定域的机制，简述二者之间的关系，并说明为什么有了RDF 和RDFS还定义OWL？ (3)按照表达能力有强到弱的顺序给出OWL的三个子语言。(1) 核心概念：语义网络是对现有网络的扩充，在语义网络中，信息具有良好定义的语义，可以告诉机器可以对数据进行的操作，从而更好的支持计算机和人的协同操作。启示：提供了一种带语义支持的基于元数据的处理机制，使我们可以用一种机器可以处理的模式来描述和处理网络资源，进而实现web服务的自动化查找，组合和调用。 (2) 二者关系：RDF是描述web资源及其关系的数据模型，采用“资源-属性-属性值”的主谓宾结构。RDFS是RDF的词汇描述语言，定义了在RDF数据模型中用到的词汇表。可以认为RDFS是对RDF的补充，增强了RDF对资源的描述能力。为什么需要：RDF局限于二元谓词，而RDFS局限于子类和属性层次划分，属性的定义域和值域的约束。鉴于RDF和RDFS的表达能力有限，语义Web需要更强大的本体描述语言。OWL在语义和意义表达方面比RDF和RDFS有更多的方法，因此对于Web上机器可处理内容的描述能力也更强。 (3)三种OWL的子语言，即 OWL Full、OWL DL 和 OWL Lite，而且各子语言的表达能力由强到弱(OWL Lite 是表达能力最弱的子语言。它是 OWL DL 的一个子集，但是通过降低 OWL DL 中的公理约束，保证了迅速高效的推理。它支持基数约束，但基数值只能为 0 或 l 。因为 OWL Lite表达能力较弱，为其开发支持工具要比其他两个子语言容易一些。 OWL Lite 用于提供给那些仅需要一个分类层次和简单约束的用户 OWL DL（Description Logic，描述逻辑）将可判定推理能力和较强表达能力作为首要目标， 而忽略了对 RDFS 的兼容性。 OWL DL 包括了 OWL 语言的所有语言成分，但使用时必须符合一定的约束，受到一定的限制。 OWL DL 提供了描述逻辑的推理功能，描述逻辑是OWL 的形式化基础。 OWL Full 包含 OWL 的全部语言成分并取消了 OWL DL 中的限制，它将RDFS扩展为一个 完备的本体语言，支持那些不需要可计算性保证（no computational guarantees）但需要最强 表达能力和完全自由的 RDFS 用户6。在OWL Full中，一个类可以看成是个体的集合，也可 以看成是一个个体。由于OWL Full取消了基数限制中对可传递性质的约束，因此不能保证可 判定推理 )应该不用记这么多.10(1) 下图给出了OWL-S 中描述service 的上层本体，请将图补充完整； (2) 简要说明OWL-S 在建模service 时定义了哪几类流程。 (3) OWL-S 利用WSDL 在ServiceGrounding中将service 的抽象信息与传输协议、消息格式等具体细节绑定，下图给出了绑定细节，将其补充完整。 (4) WSDL 和OWL-S 都能够描述Web 服务。说明二者的区别与联系。 (1) (2) OWL-S 在建模 services 时定义的几类流程:原子流程：可以直接被调用，没有子流程，在一个单独的步骤里执行。合成流程： 由其他（合成或者非合成）的流程组成，组合流程需要有一个composedOf属性。ControlConstruct类通过该属性指示合成的控制结构。简单流程：简单流程是一个抽象概念，用来提供某些原子流程的视图或者是某些合成流程的简单描述。 (3) (4) WSDL是一种描述Web服务的工业标准，它为服务的描述定义了XML格式的可行框架,用于描述服务的接口、绑定和访问点.OWL-S是一种上层本体建模语言，它以无二义性计算机可以理解的语言来表达Web服务的属性和能力。它支持使用者自动化定位、选择、使用、合成和管理Web服务。OWL-S在实施初始基础技术时利用了WSDL。OWL-S的grounding的概念与WSDL绑定的概念大体上是一致的。一个OWL-S或者是WSDL grounding使用 OWL类作为在WSDL声明的消息的抽象类型，并依靠WSDL绑定构造来规范消息的格式。11(1) 简要介绍flood 算法； (2) 在flood 算法中，TTL 和hop 代表什么含义？ (3) flood 有什么优点和缺点？简要介绍至少两种flood 的改进算法。 (1) Flood算法是在纯粹分布式结构中采用的方法,不需要向索引服务器报告共享的信息, 而是将请求泛洪到直接相连的邻居,再进一步洪泛到所有的邻居，直到收到响应,或者达到了最大的泛洪步数。 (2) TTL与hop:TTL和hops 用来控制请求的直径或者范围。 在特殊情况下作为一个标志使用，向前移动的时候，减少TTL并且增加 Hops 。 TTL （ Time-to-live ）是洪泛消息的生存周期Hops （Hops to Live）是洪泛消息生存的跳数 当某个Peer要查询数据时，会定义查询消息的生存期和跳数。然后首先把查询消息发送给它的直接邻居，再由直接邻居将查询消息发送到它们的邻居，每前进一步消息的生存期-1，跳数+1。 如果消息的生存周期不为 0 或者每收到相应信息则继续洪泛。随着消息生存期的增加，可达的主机增多，也会产生许多的消息。 （3）flood 的缺点:flood 算法容易造成控制信息的泛滥，消耗大量的带宽，从而可能很快造成网络拥 塞甚至网络的不稳定，同时，局部性能较差的结点可能会导致网络被分片，从而导致 整个网络的可用性较差，另外这类系统更容易受到垃圾信息，甚至是病毒的恶意攻击。flood的优点:（不确定） 此算法不要求维护网络的拓扑结构和相关的路由计算，仅要求接收到信息的节点以广播方式转发数据包。稳定性较高。 Flood改进（选两个记）：Gossip：在典型的 gossip 算法中，一个节点将新产生的信息发送给一组随机选择的结点。这些节点在下一轮也做类似的事，其他结点也如此，直到该消息已经发送到所有的结点或者TTL小于0。 如何确定随机选择的数量： a. 由开发者的经验决定，根据网络结点的扩展进行适应。 b. 使用 SCAMP （可扩展性的成员协议），每一个结点只是维护 log(n) 个成员 结点 FloodTrail ：首先，一个结点将它的查询用 Flood 标记后通过 P2P 网络洪泛出去，并且将它的每一个与邻居的链接标记为trail link。然后，对于同一个查询，当它的一个邻居获取到与并不是第一次获取的消息时，返回一条简短的“ trail link validation ”消息。 如何在动态覆盖中工作： a. 每个 peer 中都设置了一个定时器，该定时在在每次构造了 flooding trail 后立刻重置。 b. 一个 peer 的 trail 只在该 peer 的定时器到时之前对查询广播有效。ICN( 基于兴趣的集群网络 ) ： 在 ICN 中，结点以集群的方式组织，集群的策略基于人的兴趣。 ICN 是自组织、完全分布式、可伸缩并且是逻辑上分层的。 ICN 有两到三个逻辑层次，这些层次位于一个动态环境中，也就是说结 点可以随时加入或者离开这个环境。 在三层的 ICN 中，有三种获取数据的方式： a. 从同一个集群中获取 b. 从同一个类的不同集群中获取 c. 从不同的类中获取 12 (1) 请简述Hybrid P2P，Unstructured P2P和Structured P2P（DHT）的查找机制； (2)从查询效率、负载平衡、稳定性和可扩展性等方面比较三者的优缺点，最后写出这三种拓扑的查询时间复杂度和存储空间复杂度。 (3)分别针对Hybrid P2P，Unstructured P2P 和Structured P2P 给出的实际的应用例子。 （1）Hybrid P2P(混合化P2P)：包含索引服务器的P2P网络，网络中的数据存放在Peer上，数据的索引放在索引服务器上，Peer之间通过服务器相互通信。当某个Peer查找数据时，它会想服务器发送查询请求然后由服务器完成查询，并根据服务返回的结果与存放所需数据的Peer进行通信获得相应的数据。Unstructured P2P(非结构化P2P)：不包含中央服务器的纯P2P网络，网络中的数据存放在Peer上通过漫水法查找数据。即Peer在查找数据时，不是向中心服务器查询而是将查询请求洪泛到自己的直接领居。如果未收到响应，则继续向邻居的直接邻居洪泛直到收到响应，或者达到最大的洪泛步数。Structured P2P（结构化P2P）：使用纯分布式数据传送技术和基于关键字查找的纯P2P网络。结构化P2P在查找时采用基于关键字和DHT（分布式哈希表）的查找方法。将整个网络中数据和结点信息构为一张哈希表，然后用哈希算法将表中的各项分布到网络上。当某个结点查找数据时，采用类似折半查找的方法利用DHT在整个网络中按关键字查找数据。（2）Hybrid P2P(混合化P2P)的优点是易于管理，查询效率较高，缺点是健壮性、可扩展性和自组织能力差，没有克服C/S模式的缺点，一旦索引服务器出现问题整个网络就会瘫痪。Unstructured P2P(非结构化P2P)的优点是网络比较简单易于使用和实现，稳定性较高，Peer的加入或者退出对网络造成的影响不是很大，缺点是洪泛查询易造成网络广播风暴，且查询效率过低可扩展性差。Structured P2P（结构化P2P）的优点是：可扩展性好、查询速度较快、自组织能力好、网络平衡度高，缺点是网络的稳定性较差，Peer的上下限会对网络造成影响，同时查找数据时虽然速度较快但必须是精确匹配。Structured P2PUnstructured P2P复杂度： （3）Hybrid P2P：主要有Napster，Maze，Thunder，BitTorrent（可能不需简要说明，只是列举即可）Napster用户启动Napster，然后连接Napster服务器。Napster从用户私人的MP3歌曲库中建立动态目录。其中一个用户beastieboy输入搜索内容。Napster将用户beastieboy输入的内容在动态目录中查找，然后找出并显示成功匹配的项。用户beastieboy选择正确且速度较快的用户进行连接，然后进行文件传输。Unstructured P2P：Gnutella它是针对于分布式搜索的一个协议。每个节点既是客户端，又是服务器，被称为servent。当用户提出查询或是浏览搜索结果时，它提供客户端接口，同时，它也可以接收其他servent发送来的查询。Structured P2P：Chord没有集中的服务器（纯粹的P2P）。使用DHT来查找数据（更有效但更复杂）。13下图是一个基于Flooding 的Gnutella结构：其中Peer1,Peer2,Peer3 等节点组成了一个非结构化P2P 网络，每个节点都维护着不同数量的邻居节点信息，并拥有一定的资源，TTL 设为3。Peer4 维护的节点列表Peer1，Peer6，Peer9 和Peer10 信息；外部的Peer8 找到Peer4 请求加入网络，请简述加入的过程；Peer8 加入网络后哪些节点维护的节点列表变化？给出Peer4和Peer8的节点列表，从Peer8出发能否找到Peer3上的资源？ Peer8找到Peer4后，向Peer4发送一条加入网络的请求消息，Pee4收到请求之后将Peer8加入自己维护的节点列表，然后给Peer8发送一条确认信息，表示已经把Peer8加入到网络中。Peer8收到确认信息之后把Peer4加入自己的节点列表。Peer8加入网络后，Peer4节点列表增加一项Peer8，Peer8自身有增加一项Peer4,其它节点的节点列表不发生变化。Peer4的节点列表： Peer6Peer9Peer8Peer10Peer1 Peer4Peer8的节点列表：Peer8要找到Peer3，要通过4跳，而这个网络的TTL=3，所以不能找到。14(1)什么是DHT？DHT存储真实的数据吗？为什么？ (2) DHT 在P2P 网络中的主要作用是什么？我们通过什么方式来建立起结点与数据的关联？ (3) DHT支持模糊查询吗？为什么？（1）DHT是指分布式哈希表（Distributed Hash Table），DHT是一种分布式存储方法。在不需要服务器的情况下，每个客户端负责一个小范 围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。 DHT表本身不存储资源数据。原因有：首先，DHT表是一个用来实现结点、资源查找功能的列表， 没有必要存储真实的资源数据。第二，DHT表是利用哈希算法对实际的值散列后存 储的，散列算法是不可逆的，故DHT表也没有办法存储真实的数据。 （2）作用：DHT的引入解决了信息是分布存储的，那么如何将信息分布存储在重叠网络结点上的问题，它的查找时间为O(log(N) ，具有良好的可扩展性，并在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个P2P应用同时使用。 建立关联方式：DHT使用分布式哈希算法来建立结点与数据的关联。分布式哈希算法的核心思想是通过将存储对象的特征(关键字)经过哈希运算，得到键值(Hash Key)，对象的分布存储依据键值来进行。对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映射到了一个具体的数值范围中。（3）DHT不支持模糊查询，它要求查询数据与哈希键值要精确匹配，才能找到15 (1) 请对下图中基于DHT的P2P 中度数和直径的折中关系图简要说明。 (2) 为什么基于DHT的P2P 会存在这种折中关系？（1）在包含N个结点P2P网络中，当度数为O(N)时，搜索算法的直径为O(1)（如Hybrid P2P）；当每个结点仅维护一个邻居时（即度是O(1)时），搜索算法的直径为O(N)（比如Flooding）。这是度数和直径关系的两种极端情况。同时，研究分析了O(d)的度和O(d)的直径的算法是不可能的。而Chord网络结构正好介于两种极端情况之间，从而能够获得O(log(N)的搜索直径。从渐进曲线关系可以看出，如果想获得较短的搜索直径，必然导致度数的增加；而网络实际连接状态的变化造成大度数邻居关系的维护复杂程度增加。另外，研究者证明O(logN)甚至O(logN/loglogN)的平均路径长度也不能满足状态变化剧烈的网络应用的需求。新的搜索算法受到这种折衷关系制约的根本原因在于DHT对网络拓扑结构的确定性认识。（2）新的搜索算法受到这种折衷关系制约的根本原因在于DHT对网络拓扑结构的确定性认识。（不确定）16(1)介绍一下Chord 协议网络架构； (2) Chord 的两种查找方式是什么？ (3) 给出几种Chord 改进算法，不少于两种； (4) 你还知道其它哪些结构化网络协议？ （1）Chord协议网络架构：chord属于pure P2P里的structured（结构化）p2p，在chord环上的所有节点构造了一个虚拟的环空间，每个节点有一个唯一的ID，每个资源也对应自己唯一的ID，两个ID公用一个命名空间。每个节点都有前驱（predecessor）和后继（successor），节点加入chord环时，通过哈希产生该节点的ID，找到该节点的前驱和后继后把该节点加入环中；每个节点都有自己的Finger Table表，在查找时，通过Finger Table表进行计算查找。 （2）Chord提供了两种查找方式： a. 基本查找：Chord环中每个结点维护他们的前驱和后继的IP，基本查找就是沿 着Chord环的线性查找。 b. 基于指纹表的查找：Chord环中的每个结点维护一个指纹表，该指纹表可以利 用一种类似二分查找的方式加速查找过程。 （3）Chord改进算法:（选两种） 1)增加稳定性的算法：当有节点出现问题时，会导致不能实现正确查找，所以可以考虑使用list为每个节点保存若干个后继，这样能够提高网络的稳定性。 2)P-chord: 将Chord环进行分组,实现组内节点的自治，组间的路由和查询操作则通过组代表帮助完成。将节点的路由表进行改造, 可以消除冗余信息, 增加有效信息，在保持Chord 其他性能的前提下, 减少平均查找跳数, 提高查找效率。 3）SPJoin ：SPJoin是对Chord加入算法的改进，它通过使用加入节点的后继和后继的前驱中的信息来减少加入节点在构建finger table时需要的查询跳数，从而减少总的加入开销 （4）其它结构化网络协议有：CAN，Pastry,Tapestry17有一个命名空间为015的Chord环，假设其中在线的结点为0，2，4，7，10，12，15。 (1)请给出其中结点0，4，12的Finger Table表； (2)假如结点9加入了网络，请分析网络中哪些结点的Finger Table表要做改动？请写出改动后的Finger Table表； (3)数据项ID为3要存放到网络上，它应该存放在那个结点上？ (4)请给出从结点7 出发查找到数据项3 的查找路由。 (5) Chord 对结点失效采用了维护后继结点列表的机制，请简述其原理。其中后继列表的长度为多少合适？为什么？ 1）N0：KSTARTINTERVALNODE111,2）2222，4）2344，8）4488，0）10N4：KSTARTINTERVALNODE155，6）7266，8）7388，12）1041212，4）12N12：KSTARTINTERVALNODE11313,14）1521414，0）15300，4）0444，12）42）结点9加入之后，在线的结点为0，2，4，7，9，10，12，15。网络中的结点0、4、7的Finger Table表需做改动。KSTARTINTERVALNODE111,2）2222，4）2344，8）4488，0）9N4KSTARTINTERVALNODE155，6）7266，8）7388，12）941212，4）12N7KSTARTINTERVALNODE188，9）9299，11）931111，15）1241515，7）153）数据项ID为3应该放在结点4上。基于Finger Table表查询算法为：Chord环上的一个结点在数据项ID后面，则将这个数据项发送到这个结点上。4）N7-N15-N45)当结点n失效时，所有Finger Table表中包括结点n的项都必须把它替换成n的后继节点。为了保证节点n的失效不影响系统中正在进行的查询过程，每个Chord节点都维护一张包括r个直接的后继结点列表。如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正常节点替换失效节点。后继列表的长度为2log(N) 最合适。假设一个结点维护的后继列表长度为r，结点的失效率为1/2，网络内的结点个数为N，假定结点失效互不影响，则一个结点后继全部失效的概率为(1/2)r，则所有结点后继都不失效的概率为P=(1 (1/2)r)N，要使P达到尽可能的大并且r也不能太大，选取一个折中r=2log(N)，而此时P=1 1/N，当结点个数N很大时，整个网络结点后继失效率已经很低了。18下图为一个基于半分布式拓扑的 Kazaa 网络，其相当于一个混合层次化 P2P结构。其中下层由超级结点（SN）和一般结点（ON）组成中心化网络，上层由超级结点组成基于洪泛方法的非结构化网络。(1) 请描述在这种网络结构中资源的查找机制。 (2) 比较这种网络结构与纯基于洪泛的非结构化网络（例如 Gnutella）的优缺点。（1）在这种网络中，超级节点要维护两个列表：本中心化网络的一般节点列表、部分其他中心化网络的超级节点列表，这个超级节点列表类似于纯flood网络中的邻居节点列表。当一般节点A需要查找某资源RS时，A首先将该查询请求发送给A所在中心化网络的超级节点SNA，SNA将此查询请求洪泛转发给超级节点列表中的节点，其他中心化网络中的超级节点在收到该查询请求后，将此查询请求转发给本中心化网络的一般节点，并将其洪泛转发给超积极节点列表中的节点。这样，查询消息就首先通过上层洪泛网络到达所有的超级节点，再由超级节点转发给本地中心化网络中的一般节点。（2）优点:与纯洪泛网络相比，此网络能够限制洪泛产生的消息数量，降低网络负载。 缺点:一个中心化网络的超级节点的掉线意味着这个中心化网络的所有一般节点都掉线，所以此网络的稳定性没有纯洪泛网络高。19. (1)什么是NAT？NAT 有哪几种类型？ (2)为什么在P2P中要实现对N AT 进行穿透？ (3)为什么说对称型NAT难以穿透？ （1）NAT：网络地址转换（Network Address Translator）NAT把一个私有的IP地址转化为一个能被其他公共主机访问的公有的IP 地址，来解决IPv4地址不足的问题。NAT有如下二类：l 基本的NAT-Basic NAT网络地址/端口转化-NAPT (Network Address/Port Translator)圆锥NAT-Cone NAT aa. 完全锥形NAT(即 一对一（one-to-one） NAT) bb. 受限锥形NAT cc. 端口受限锥形NAT 对称NAT-Symmetric NAT （2）在P2P网络中的主机应该与其它主机共享资源，但是在NAT内部的主机不能被NAT外部的主机访问，也就是说，NAT减少了P2P网络中有效的连接和资源共享，因此，需要支持穿透NAT的通信（3）因为对称NAT需要端口预测，而端口预测的成功率比较低。 20. 简要描述一下NAT 穿透中UDP打洞方法的流程。 第一步：一台在私网上的主机1想要连接另一台在私网上的主机2，由于主机2所在私有网的SESSION表没有关于主机1的记录，所有暂时无法建立连接，但在主机1所在私有网的SESSION表中添加上一条主机1连接主机2的记录。第二步：主机1先连接在公网上的服务器，通过公网上的服务器连接主机2，由于主机2所在私有网的SESSION表中有主机2连接公网服务器的记录，所以此连接能建立起来。第三步：当主机2尝试连接主机1时，由于主机1所在私有网的SESSION表中已经有记录，所以主机2也能成功连接主机1，而不需要通过公网上的服务器，此时在主机2的私有网SESSION表添加记录表明，主机2连接过主机1。此时，穿透NAT的UDP打洞就完成了，主机1与主机2能直接连接了，而不需要通过公网的服务器。21、云计算中有哪三类服务模型？分别对这些模型进行简要概括。 软件作为服务(SAAS /Software as a Service) 以服务的方式将应用程序提供给互联网最终用户，不需要用户将软件产品安装在自己的电脑上，而是按照某种服务水平协议(SLA)直接通过网络，从提供商获取自己所需要的、带有相应软件功能的服务。平台作为服务(PAAS/ Platform as a Service) 以服务的方式提供应用程序开发和部署平台。就是指将一个完整的计算机平台，包括应用设计、应用开发、应用测试等，都作为一种服务提供给客户。在这种服务模式中，客户不需要购买硬件和软件，只需要利用PAAS平台，就能够创建、测试、部署应用和服务。基础设施作为服务(IAAS/ Infrastructure as a Service) 以服务的形式提供服务器、存储和网络硬件以及相关软件。它是三层架构的最底层。是指企业或个人可以使用云计算来远程访问计算资源，这包括计算、存储以及应用虚拟化技术所提供的相关功能。22、什么是MapReduce？描述MapReduce的执行过程。 MapReduce是由Google引入的一种软件架构，它最初被Google 用来创建和更新索引，现在普遍用来支持计算机集群上大规模数据集（大于1TB）的分布式计算。MapReduce的执行过程是让用户通过设定Map功能将一组key/value对转换为一组中间key/value对。然后Reduce功能将具有相同中间key值的中间value值进行整合，从而得到计算结果。23、什么是物联网？简述物联网的技术架构。 物联网是指通过装置在物体上的各种信息传感设备，如DFID装置、红外感应器、全球定位系统、激光扫描器等，赋予物体智能，并通过接口与互联网相连而形成的一个物品与物品相连的巨大的分布式协同网络。 从技术架构上来看，物联网可分为三层：感知层、网络层和应用层。 感知层由各种传感器以及传感器网关构成，包括二氧化碳浓度传感器、温度传感器、湿度传感器、二维码标签、RFID标签和读写器、摄像头、GPS等感知终端。感知层的作用相当于人的眼耳鼻喉和皮肤等神经末梢，它是物联网获识别物体，采集信息的来源，其主要功能是识别物体，采集信息。网络层由各种私有网络、互联网、有线和无线通信网、网络管理系统和云计算平台等组成，相当于人的神经中枢和大脑，负责传递和处理感知层获取的信息。应用层是物联网和用户（包括人、组织和其他系统）的接口，它与行业需求结合，实现物联网的智能应用。24. 简要描述结构化数据，非结构化数据以及半结构化数据，并分别举例说明。 结构化数据通常是指在传统数据库中保存，可以用二维表结构来逻辑表达实现的数据。比如企业ERP、财务系统；医疗HIS数据库；教育一卡通；政府行政审批；其他核心数据库等。非结构化数据：不方便用数据库二维逻辑表来表现的数据即称为非结构化数据，这类信息的特点是通常无法直接知道他的内容，对以后检索非常麻烦。包括所有格式的办公文档、文本、图片、XML、HTML、各类报表、图像和音频/视频信息等等。半结构化数据，这些数据有一定的内部结构但是结构变化很大，所以难以用二维表结构来表达实现。因为我们要了解数据的细节所以不能将数据简单的组织成一个文件按照非结构化数据处理，由于结构变化很大也不能够简单的建立一个表和他对应。包括邮件、HTML、报表、资源库等等，典型场景如邮件系统、WEB集群、教学资源库、数据挖掘系统、档案系统等等。25. (1) 大数据有哪四个特点，并简要说明。 (2)简述大数据和云计算的关系。 （1）一是数据体量巨大(Volume)从TB级别跃升到PB级别。同时在分析数据过程中需要巨大的运算量。集中存储/集中计算已经无法处理如此巨大的数据量。 二是数据类型繁多(Variety) 大数据种类繁多，在编码方式、数据格式、应用特征等多个方面存在差异性，比如网络日志、视频、图片、网页等等。三是价值密度低(Value) 大数据的价值密度很低，即单条数据并无太大价值，但是庞大的数据量蕴含巨大财富。四是处理速度快(Velocity) 速度包括总体数据量增长速度快同时需要快速的分析以及处理海量数据 （2）参考： 毕 业 论 文论文题目学 院专 业年 级姓 名指导教师职 称（200 年 月）教务处制毕业设计说明书与毕业论文撰写的规范化要求一篇完整的毕业设计说明书或毕业论文有题目、摘要及关键词、目录、引言（前言）、正文、结论、谢辞、参考文献、附录等几部分构成。要求理工科专业不少于4000字，文科专业不少于6000字。一、毕业设计说明书撰写的主要内容与基本要求一份完整的毕业设计说明书应包括如下主要内容：1题目设计课题名称，要求简洁、确切、鲜明。2中外文摘要及关键词应扼要叙述本设计的主要内容、特点，文字要简练。中文摘要约300字左右；外文摘要约250个实词左右。关键词35个。3目录主要内容的目录。4前言应说明本设计的目的、意义、范围及应达到的技术要求；简述本课题在国内（外）的发展概况及存在的问题；本设计的指导思想；阐述本设计应解决的主要问题。 5正文（1）设计方案论证：应说明设计原理并进行方案选择。应说明为什么要选择这个方案（包括各种方案的分析、比较）；还应阐述所采用方案的特点（如采用了何种新技术、新措施、提高了什么性能等）。（2）设计及计算部分：这是设计说明书的重要组成部分，应详细写明设计结果及计算结果。（3）样机或试件的各种实验及测试情况：包括实验方法、线路及数据处理等。（4）方案的校验：说明所设计的系统是否满足各项性能指标的要求，能否达到预期效果。校验的方法可以是理论分析（即反推算），包括