Efficient and scalable provisioning of always-on multicast streaming services

There is a growing need for large-scale distribution of realtime multicast data such as Internet TV channels and scientific and financial data. Internet Service Providers (ISPs) face an urgent challenge in supporting these services; they need to design multicast routing paths that are reliable, cost-effective, and scalable. To meet the realtime constraint, the routing paths need to be robust against a single IP router or link failure, as well as multiple such failures due to sharing fiber spans (SRLGs). Several algorithms have been proposed to solve this problem in the past. However, they are not suitable for today’s large networks, because either they do not find a feasible solution at all or if they do, they take a significant amount of time to arrive at high-quality solutions.In this paper, we present a new Integer Linear Programming (ILP) model for designing a cost-effective and robust multicast infrastructure. Our ILP model is extremely efficient and can be extended to produce quality-guaranteed network paths. We develop two heuristic algorithms for solving the ILP. Our algorithms can guarantee to find high-quality, feasible solutions even for very large networks. We evaluate the proposed algorithms using topologies of four operational backbones and demonstrate their scalability. We also compare the capital expenditure of the resulting multicast designs with existing approaches. The evaluation not only confirms the efficacy of our algorithms, but also shows that they outperform existing schemes significantly.     

A scalable framework for mobile real-time group communication services

A scalable framework for mobile real-time group communication services is developed in this paper. Examples for possible applications of this framework are mobile social networks, mobile conference calls, mobile instant messaging services, and mobile multi-player on-line games. A key requirement for enabling a real-time group communication service is the tight constraint imposed on the call delivery delay. Since establishing such communication service for a group of independent mobile users under a tight delay constraint is NP-hard, a two-tier architecture is proposed, that can meet the delay constraint imposed by the real-time service requirement for many independent mobile clients in a scalable manner. This goal is achieved by two dimensional partition of the space, first by organization and then geographically. Both the time and memory complexity associated with the location management of N mobile users are O(N) for the location management provided by the proposed framework, while a distributed scheme requires O(N²) for both time and memory complexity.     

可伸缩多播通信的延时方法

使用ARQ与FEC混合技术有利于提高多播通信的可靠性和可伸缩性,但随着多播通信规模的扩大,仍将引发NACK爆炸的问题,接收者延时发送NACK,可以避免NACK爆炸,文中提出了基于指数分布,均匀分段延时的方法,并对其性能进行了分析。可知该方法抑制NACK的能力达到10^10。     

Declarative Web services composition using proofs

Over the last decade, Web services composition has become a thriving area of research and development endeavors for application integration and interoperability. Although Web services composition has been heavily investigated, several issues still need to be addressed. In this paper, we mainly discuss two major bottlenecks in the current process of modeling compositions. The first bottleneck is related to the level of expertise required to achieve a composition process. Typical procedural style of modeling, inspired by workflow/business process paradigm, do not provide the required abstractions. Therefore, they fail to support dynamic and self-managed compositions able to adapt to unpredictable changes. The second bottleneck in current service compositions concerns their life cycle and their management, also called their governance. In this context, we propose a declarative proof-based approach to Web service composition. Based on the three stages of pre-composition, abstraction, and composition, our solution provides an easy way to specify functional and non-functional requirements of composite services in a precise and declarative manner. It guides the user through the composition process while allowing detection and recovery of violations at both design and run-time using proofs and planning. Experiment results clearly show the added value of the proof-based solution as a viable strategy to improve the composition process.     

SoMR: A scalable distributed QoS multicast routing protocol

Many Internet multicast applications such as teleconferencing and remote diagnosis have Quality-of-Service (QoS) requirements. The requirements can be additive (end-to-end delay), multiplicative (loss rate), or of a bottleneck nature (bandwidth). Given such diverse requirements, it is a challenging task to build QoS-constrained multicast trees in a large network where no global network state is available. This paper proposes a scalable QoS multicast routing protocol (SoMR) that supports all three QoS requirement types. SoMR is scalable due to small communication overhead. It achieves favorable tradeoff between routing performance and routing overhead by carefully selecting the network sub-graph in which it searches for a path that can support the QoS requirements. The scope of search is automatically tuned based on the current network conditions. An early-warning mechanism helps detect and route around the long-delay paths in the network. The operations of SoMR are completely decentralized. They rely only on the local state stored at each router.     

Secure multicast in IPTV services

Technological evolution is leading telecommunications to all-IP networks where multiple services are transported as IP packets. Among these are the group communications services with confidentiality requirements. Secure IP multicast may be used to secure the broadcast of video channels. However, in scenarios such as cable TV where the concept of video channel and bundle are present, groups are very large, and users switch very rapidly between channels (zapping), a sort of problems still need to be addressed.The solution proposed in this paper addresses these problems. For that purpose, a centralized form of secure group communications is proposed also used to transmit, not data, but group cryptographic material. Threes types of cryptographic keys are used. End systems use this material to decrypt the data sent by the content providers.     

MTCP: scalable TCP-like congestion control for reliable multicast

We present MTCP, a congestion control scheme for large-scale reliable multicast. Congestion control for reliable multicast is important, because of its wide applications in multimedia and collaborative computing, yet non-trivial, because of the potentially large number of receivers involved. Many schemes have been proposed to handle the recovery of lost packets in a scalable manner, but there is little work on the design and implementation of congestion control schemes for reliable multicast. We propose new techniques that can effectively handle instances of congestion occurring simultaneously at various parts of a multicast tree.Our protocol incorporates several novel features: (1) hierarchical congestion status reports that distribute the load of processing feedback from all receivers across the multicast group, (2) the relative time delay concept which overcomes the difficulty of estimating round-trip times in tree-based multicast environments, (3) window-based control that prevents the sender from transmitting faster than packets leave the bottleneck link on the multicast path through which the sender's traffic flows, (4) a retransmission window that regulates the flow of repair packets to prevent local recovery from causing congestion, and (5) a selective acknowledgment scheme that prevents independent (i.e., non-congestion-related) packet loss from reducing the sender's transmission rate. We have implemented MTCP both on UDP in SunOS 5.6 and on the simulator ns, and we have conducted extensive Internet experiments and simulation to test the scalability and inter-fairness properties of the protocol. The encouraging results we have obtained support our confidence that TCP-like congestion control for large-scale reliable multicast is within our grasp.     

An efficient and scalable loss-recovery scheme for video multicast

With the increased popularity of multimedia services on the Internet, efficient video multicast strategies that can scale easily are of critical importance. This paper addresses the issue of video multicast loss recovery and presents an efficient and scalable scheme: Active Injection Recovery (AIR). The proposed scheme has three distinguishing features: active injection of repair packets into loss regions, on-demand construction of loss-recovery structures, and unique rate control over repair traffic. All of these features can save considerable network resources in a large-scale video multicast session. In addition, the proposed scheme simultaneously meets the three well-known requirements for efficiency and scalability in multicast loss recovery: request suppression, local recovery, and retransmission scoping. Another important feature of the proposed scheme is its low recovery latency, which is essential for video multicast. Our results show that the proposed scheme achieves significantly better overall performance as compared to existing multicast loss recovery schemes.     

Interactive information services using World-Wide Web hypertext

Most World-Wide Web information servers provide simple browsing access to collections of static text or hypertext files. This paper describes some interactive World-Wide Web servers that produce information displays and documents dynamically rather than just providing access to static files. The PARC Map Viewer uses a geographic database to create and display maps of any part of the world on demand. The Digital Tradition folk music server provides access to a large database of song lyrics and melodies. These applications take advantage of the multimedia capabilities of World-Wide Web to deliver graphical and audio content as well as formatted text. Hypertext links are used not only for navigation, but also for setting search and presentation parameters. In these applications the HTML format and the HTTP protocol are used like a user interface tool kit to provide not only document retrieval but a complete custom user interface specialized for the application.     

Efficient and adaptive epidemic-style protocols for reliable and scalable multicast

Epidemic-style (gossip-based) techniques have recently emerged as a class of scalable and reliable protocols for peer-to-peer multicast dissemination in large process groups. However, popular implementations of epidemic-style dissemination suffer from two major drawbacks: 1) Network overhead: when deployed on a WAN-wide or VPN-wide scale, they generate a large number of packets that transit across the boundaries of multiple network domains (e.g., LANs, subnets, ASs), causing an overload on core network elements such as bridges, routers, and associated links. 2) Lack of adaptivity: they impose the same load on process group members and the network even under reduced failure rates (viz., packet losses, process failures). In this paper, we describe two protocols to address these problems: 1) a hierarchical gossiping protocol and 2) an adaptive dissemination framework (for multicasts) that allows use of any gossiping primitive within it. These protocols work within a virtual peer-to-peer hierarchy called the leaf box hierarchy. Processes can be allocated in a topologically aware manner to the leaf boxes of this structure, so that protocols 1 and 2 produce low traffic across domain boundaries in the network and induce minimal overhead when there are no failures.     

A new scalable multicast routing algorithm for interactive real-time applications

Quality of service (QoS) provisioning generally assumes more than one QoS measure that implies that QoS routing can be categorized as an instance of routing subject to multiple constraints: delay jitter, bandwidth, cost, etc. We study the problem of constructing multicast trees to meet the QoS requirements of real-time interactive applications where it is necessary to provide bounded delays and bounded delay variation among the source and all destinations while keeping overall cost of the multicast tree low. The main contribution of our work is a new strategy for constructing multiconstrained multicast trees. We first derive mathematically a new delay-variation estimation scheme and prove its efficiency. Thereafter, we propose a simple and competitive (in terms of running time) heuristic algorithm, for delay and delay variation constrained routing problem based on the proposed delay-variation estimation scheme and using the Extended Prim-Dijkstra tradeoffs’ algorithm. Our contribution also extends previous works in providing some properties and analyses of delay bounded paths satisfying delay variation constraints. Extensive simulation results show that our algorithm outperforms DVDMR in terms of multicast delay variation with the same time complexity as DVDMR.     

Araneola: A scalable reliable multicast system for dynamic environments

This paper presents Araneola (Araneola means “little spider” in Latin.), a scalable reliable application-level multicast system for highly dynamic wide-area environments. Araneola supports multi-point to multi-point reliable communication in a fully distributed manner, while incurring constant load (in terms of message and space complexity) on each node. For a tunable parameter k≥3, Araneola constructs and dynamically maintains a basic overlay structure in which each node’s degree is either k or k+1, and roughly 90% of the nodes have degree k. Empirical evaluation shows that Araneola’s basic overlay achieves three important mathematical properties of k-regular random graphs (i.e., random graphs in which each node has exactly k neighbors) with N nodes: (i) its diameter grows logarithmically with N; (ii) it is generally k-connected; and (iii) it remains highly connected following random removal of linear-size subsets of edges or nodes. The overlay is constructed and maintained at a low cost: each join, leave, or failure is handled locally, and entails the sending of only about 3k messages in total, independent of N. Moreover, this cost decreases as the churn rate increases.The low degree of Araneola’s basic overlay structure allows for allocating plenty of additional bandwidth for specific application needs. In this paper, we give an example for such a need — communicating with nearby nodes; we enhance the basic overlay with additional links chosen according to geographic proximity and available bandwidth. We show that this approach, i.e., a combination of random and nearby links, reduces the number of physical hops messages traverse without hurting the overlay’s robustness, as compared with completely random Araneola overlays (in which all the links are random) with the same average node degree.Given Araneola’s overlay, we sketch out several message dissemination techniques that can be implemented on top of this overlay. We present a full implementation and evaluation of a gossip-based multicast scheme, with up to 10,000 nodes. We show that compared with a (non-overlay-based) gossip-based multicast protocol, gossiping over Araneola achieves substantial improvements in load, reliability, and latency.     

A scalable Web cache sharing scheme

A new Web cache sharing scheme is presented. Our scheme reduces the duplicated copies of the same objects in global shared Web caches. It also reduces the message overhead of existing schemes significantly. Trace-driven simulations with actual Web cache logs show that the proposed scheme performs better than the two well-known Web cache sharing schemes, the Internet Cache Protocol and the Cache Array Routing Protocol.     

基于Web的用户可扩展兴趣表示模型

首先分析了向量模型度量用户会话的兴趣特征（SI）和聚类的兴趣特征（CI）方法的不足,在此基础上,提出了一种可扩展兴趣表示模型（SIM）,给出了它的数据结构,以及使用SIM表示SI和CI的方法,并分析了这种表示方法的性能优点,最后,通过实验,以实际数据验证了使用SIM表示SI和CI的优越性。     

WebCanal: a multicast Web application

This paper addresses the problems related to multipoint distribution of Web documents over Internet. We present a multicast Web application which allows the sharing of Web resources among a group of people by using the MBONE technology. We describe a general-purposed light-weight reliable multicast transport protocol (LRMP) which is an important building block of the application. We will also discuss other technical issues related to the design of such applications, such as caching, Web browser interface, and embedded objects.     

采用改进的本体相似的Web服务匹配

随着Internet上Web服务的快速增长,客户如何发现想要的Web服务,已经是Web服务技术中的难点和关键问题。鉴于UDDI注册中心的Web服务描述信息非常稀疏的特点,传统的基于关键字的服务匹配机制UDDI缺乏语义支持,搜索效率低;为了在UDDI注册中心提供的用WSDL描述的和未来用语义本体描述的Web服务信息的基础上提高Web服务匹配的查准率和查全率,提出了一种新的本体相似匹配方法,使Web服务匹配在查准率和查全率方面都有所提高。     

Unicast-based multicast communication in wormhole-routed networks

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log ₂ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given     

语义Web服务——Web服务的扩展

语义Web服务是应用语义Web技术对Web服务的扩展.使信息具有语义就是用计算机内的Ontology中的概念作标记符对信息进行标记,对该过程予以支持的就是语义Web技术,即Ontology的构建技术、Ontology的使用技术(语义推理技术)和信息的语义标记技术.语义Web技术对Web服务的扩展可具体化为两项任务:服务提供者、服务请求者和服务注册处三类服务主体均内置Ontology;发布、查找和绑定三种交互信息均采用语义标记.