Nonblocking k-fold multicast networks

Multicast communication involves transmitting information from a single source to multiple destinations and is a requirement in high-performance networks. Current trends in networking applications indicate an increasing demand in future networks for multicast capability. Many multicast applications require not only multicast capability, but also predictable communication performance such as guaranteed multicast latency and bandwidth. In this paper, we present a design for a nonblocking k-fold multicast network, in which any destination node can be involved in up to k simultaneous multicast connections in a nonblocking manner. We also develop an efficient routing algorithm for the network. As can be seen, a k-fold multicast network has significantly lower network cost than that of k copies of ordinary 1-fold multicast networks and is a cost effective choice for supporting arbitrary multicast communication.     

Cost-effective designs of WDM optical interconnects

Optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has become a promising networking choice to meet ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/communication applications, such as data browsing in the World Wide Web, multimedia conferencing, e-commerce, and video-on-demand services. As optics becomes a major networking media in all communications needs, optical interconnects will inevitably play an important role in interconnecting processors in parallel and distributed computing systems. We consider a cost-effective design of WDM optical interconnects for current and future generation parallel and distributed computing and communication systems. We first categorize WDM optical interconnects into two different connection models based on their target applications: the wavelength-based model and the fiber-link-based model. Most of existing WDM optical interconnects belong to the first category. We then present a minimum cost design for WDM optical interconnects under wavelength-based model by using sparse crossbar switches instead of full crossbar switches in combination with wavelength converters. For applications that use the fiber-link-based model, we show that network cost can be significantly reduced, and present such a minimum cost design for WDM optical interconnects under this model. Finally, we generalize the idea used in the design for the fiber-link-based model to WDM optical interconnects under the wavelength-based model, and obtain another new design that can trade off switch cost with wavelength converter cost in this type of WDM optical interconnect. The results in this paper are applicable to any emerging optical switching technologies, such as SOA-based and MEMS-based technologies.     

Low-cost,delay-bounded point-to-multipoint communication to support multicasting over WDM networks

The confluence of technical advances and multimedia service needs is intensifying the need for high throughput and low latency. Future communication networks will face an increase in traffic driven by multimedia requirements with stringent delay and jitter requirements. Wavelength division multiplexing (WDM) optical networks have the potential for meeting these goals by offering unprecedented high bandwidth and low latency. One very important aspect of the emerging Internet services is the need to support multicasting. This is crucial if WDM networks were to play an efficient role in the next generation Internet.Multicasting in WDM networks supporting multimedia applications can be viewed as the process of taking a group communication request and selecting a multicast tree that satisfies the quality of service requirements, in terms of bandwidth and end-to-end delay, of the underlying application. In this paper, we present a new class of low-cost, bounded-delay multicast heuristics for WDM networks. The heuristics use various techniques to establish a tree of semi-lightpaths between a source and a group of destination nodes. The unique feature of these heuristics is that they decouple the cost of establishing the multicast tree from the delay incurred by data transmission due to light-wave conversion and processing at intermediate nodes along the transmission path. A simulation study shows the performance of the proposed heuristics.     

Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks

Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.     

Comparison of recovery schemes to maximize restorable throughput in multicast networks

Multicast networks have many applications especially in real-time content delivery systems. For high-quality services, users do not expect to witness any interruption; thus, network link failure has to be handled gracefully. In unicast networks there are many approaches for dealing with link failures using backup paths. Recently, Cohen and Nakibly categorized these methods, provided linear programming formulations for optimizing network throughput under the assumption that the paths are splitable, and compared them experimentally. In this work, we take their approach and apply to the multicast failure recovery problem. We propose backup bandwidth allocation algorithms based on linear programs to maximize the throughput, and perform an experimental study on the performance of recovery schemes. We study many recovery schemes in multicast networks and propose a new recovery scheme that performs better than all other recovery scheme except the one that recomputed the whole multicast tree from scratch for each link failure.     

Efficient fault-tolerant routing in multihop optical WDM networks

This paper addresses the problem of efficient routing in unreliable multihop optical networks supported by Wavelength Division Multiplexing (WDM). We first define a new cost model for routing in (optical) WDM networks that is more general than the existing models. Our model takes into consideration not only the cost of wavelength access and conversion but also the delay for queuing signals arriving at different input channels that share the same output channel at the same node. We then propose a set of efficient algorithms in a reliable WDM network on the new cost model for each of the three most important communication patterns-multiple point-to-point routing, multicast, and multiple multicast. Finally, we show how to obtain a set of efficient algorithms in an unreliable WDM network with up to f faulty optical channels and wavelength conversion gates. Our strategy is to first enhance the physical paths constructed by the algorithms for reliable networks to ensure success of fault-tolerant routing, and then to route among the enhanced paths to establish a set of fault-free physical routes to complete the corresponding routing request for each of the communication patterns     

A Novel Multistage Network Architecture with Multicast and Broadcast Capability

In this paper, a new class of optical multistage interconnection network (MIN) architecture is presented, which is constructed utilizing a modularization approach rather than the traditional recursive or fixed exchange pattern methods. The modified architecture consists of an input module, an output module, two point-to-point (PTP) modules, and one modified multicast/broadcast (M/B) module(s). We also implement the multicast/broadcast module with WDM technique, which reduces the hardware cost required for multicast and the re-computation cost for a new connection. We show that it has the best application flexibility and provides multicast function without imposing significant negative impacts on the whole network. A new multicast connection pattern is also proposed in this paper, which makes it practical and economical to apply amplification in space-division networks. Compared with existing multicast architectures, this new architecture with Dilated Benes PTP modules has better performance in terms of system SNR, the number of switch elements, and system attenuation in point-to-point connections. Moreover, the multicast/broadcast module adopts wavelength division multiplexing (WDM) technique to increase its multicast/broadcast assignment. As a result, given m available distinguished wavelengths, one M/B module can support at most m M/B requests at the same time. The new proposed M/B module with WDM is more practical and economical to apply amplification in space-division networks.     

WDM optical interconnects with recirculating buffering and limited range wavelength conversion

All-optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has been proposed as a promising candidate to meet the ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. However, with current technology, the cost of optical communication, especially the cost of optical buffering and wavelength conversion, remains a major concern for such applications. In this paper, we study WDM optical interconnects that utilize low cost recirculating buffering and limited range wavelength conversion. We first consider the packet scheduling problem in this type of interconnect, and formalize the problem of maximizing throughput and minimizing packet delay as a matching problem in a bipartite graph. We give an optimal parallel algorithm for this problem that runs in O(Bk/sup 2/) time, compared to O((N+B)/sup 3/k/sup 3/) time if directly applied to existing matching algorithms for general bipartite graphs, where N is the number of input/output fibers of the interconnect, B is the number of fiber delay lines, and k is the number of wavelengths. We also consider efficient switching fabric designs for this type of interconnect. We distinguish between the switching fabric connecting the input fibers to the output fibers and the switching fabric connecting the input fibers to the delay lines and show that by adopting the idea of concentration, the cost of the latter can be reduced significantly in terms of the number of crosspoints.     

A sleep-mode interleaving algorithm for layered-video multicast services in IEEE 802.16e networks

In this paper we investigate efficient mechanisms to support layered-video multicast services in IEEE 802.16e (Mobile WiMAX) networks.¹ Given the bandwidth eager and energy hungry nature of layered-video multicast services, network systems should employ efficient bandwidth allocation and energy saving mechanisms. We first investigate how the WiMAX energy saving mechanisms significantly degrade the performance of multicast bandwidth allocation mechanisms for layered-video multicast services. Then, we present a theoretical model for illustrating this interaction problem. To the best of our knowledge, this paper offers the first investigation into and the first theoretical model of the interaction problem between multicast bandwidth allocation and WiMAX energy saving mechanisms. To solve the interaction problem, we propose a novel sleep-mode interleaving algorithm beyond the existing mechanisms. The proposed algorithm has full compatibility with the existing multicast bandwidth allocation mechanisms and with IEEE 802.16e standards. By appropriately adjusting one sleep mode parameter defined in the standard, the proposed sleep-mode interleaving algorithm effectively guarantees the bandwidth efficiency of the video multicast mechanisms while mobile users can execute the standard sleep mode operations. Simulation results demonstrate the effectiveness of the proposed algorithm in terms of packet delivery ratio, user satisfaction, energy efficiency and computational complexity.     

Seamless handover between unicast and multicast multimedia streams

With the deployment of heterogeneous networks, mobile users are expecting ubiquitous connectivity when using applications. For bandwidth-intensive applications such as Interact Protocol Television （IPTV）, multimedia contents are typical- ly transmitted using a multicast delivery method due to its bandwidth efficiency. However, not all networks support multicasting. Multicasting alone could lead to service disruption when the users move from a multicast-capable network to a non-multicast network. In this paper, we propose a handover scheme called application layer seamless switching （ALSS） to provide smooth real-time multimedia delivery across unicast and multicast networks. ALSS adopts a soft handover to achieve seamless playback during the handover period. A real-time streaming testbed is implemented to investigate the overall handover performance, espe- cially the overlapping period where both network interfaces are receiving audio and video packets. Both the quality of service （QoS） and objective-mapped quality of experience （QoE） metrics are measured. Experimental results show that the overlapping period takes a minimum of 56 and 4 ms for multicast-to-unicast （M2U） and unicast-to-multicast （U2M） handover, respectively. The measured peak signal-to-noise ratio （PSNR） confirms that the frame-by-frame quality of the streamed video during the handover is at least 33 dB, which is categorized as good based on ITU-T recommendations. The estimated mean opinion score （MOS） in terms of video playback smoothness is also at a satisfactory level.     

On Bandwidth-Efficient Overlay Multicast

In this paper, we propose a new multicast delivery mechanism for bandwidth-demanding applications in IP networks. Our mechanism, referred to as multiple-destination overlay multicast (MOM), combines the advantages of IP multicast and overlay multicast. We formulate the MOM routing problem as an optimization problem. We then design an algorithm based on Lagrangian relaxation on our formulation and propose a distributed protocol based on the algorithm. For network operators, MOM consumes less network bandwidth than both IP multicast and overlay multicast. For users, MOM uses less interface bandwidth than overlay multicast.     

Computational intelligence in photonics technology and optical networks: A survey and future perspectives

The continuous growth of broadband communications, multimedia services and Internet is absolutely related to the deployment and operation of optical networks. Despite optical fibers’ enormous physical bandwidth the development of optical networks for today’s advanced, reliable and guaranteed-type services, require an efficient management of the bandwidth together with an orthological and careful use of optical components given their high manufacturing cost. These requirements have lead to the need for sophisticated photonic devices and to optical networks’ implementations of increased functionality and associated thus complexity. For the efficient consideration of those problems different design and optimization techniques have been applied to date. However, as the complexity increases, the use of computational intelligence (CI) in those problems is becoming a unique tool of imperative value. In this paper we review in a unified approach the applications of CI starting from the physical layer and ending to services layer, given that here there is a strong relation and unique interplay between components’ technology and network issues, being sharing the common target of physical bandwidth’s efficient utilization. The applicability of different CI classes (genetic algorithms and evolution strategies, fuzzy systems, and artificial neural networks) in optical wavelength division multiplexing (WDM) networks is identified and evaluated. Furthermore specific optical networks’ optimization problems are categorized. Being a rapidly growing area, new trends, such as evolutionary game theory, in understanding and design of large scale Optical Network are also identified and discussed. The paper seeks to review the aforementioned areas, identify new problems and trends, triggering this way new research efforts for interdisciplinary cooperation between researchers.     

A taxonomy of multicast protocols for Internet applications

The continuous growth in applications that require communications among a group of hosts or simultaneous dissemination of data to multiple sites on the Internet has led to considerable interest in multicast communication. These applications have different quality of service requirements such as deadlines to response time and tolerance to data loss. Internet multicast protocols provide a spectrum of services to cater for the needs of a wide array of multicast applications. The design alternatives of a multicast protocol for a particular application may lead to different performance characteristics, for example higher utilization of network bandwidth vs lower protocol processing requirements. Therefore a framework is required to various design choices available to design multicast protocols and evaluate the performance tradeoffs associated with these alternatives. Motivated by such a need and by the evolution of multicast applications over the Internet, this article presents a taxonomy of multicast protocols and a common framework to evaluate their performance.     

无线Mesh网络中基于业务价值的组播带宽分配方案

高延迟及低效益是无线Mesh网络中开展流媒体业务面临的主要问题。为解决该问题,首先赋予组播业务价值,该值反映了业务的网络优先级及效益优先级,并提出一个基于组播价值优先级的组播带宽分配方案。该方案第一阶段实施基于价值优先级的不区分业务类型的静态分配,通过对高价值业务的优先调度,实现了组播价值最大化及带宽效益最大化。在拥塞时,实施第二阶段的基于业务带宽需求调整及抢占的动态分配,保证了低时延约束业务的服务质量。仿真与常见算法的比较表明,所提出的方案在保证业务网络服务质量的同时,能实现带宽效益最大化。     

Bandwidth guaranteed multicast scheduling for virtual output queued packet switches

Multicast enables efficient data transmission from one source to multiple destinations, and has been playing an important role in Internet multimedia applications. Although several multicast scheduling schemes for packet switches have been proposed in the literature, they usually aim to achieve only short multicast latency and high throughput without considering bandwidth guarantees. However, fair bandwidth allocation is critical for the quality of service (QoS) of the network, and is necessary to support multicast applications requiring guaranteed performance services, such as online audio and video streaming. This paper addresses the issue of bandwidth guaranteed multicast scheduling on virtual output queued (VOQ) switches. We propose the Credit based Multicast Fair scheduling (CMF) algorithm, which aims at achieving not only short multicast latency but also fair bandwidth allocation. CMF uses a credit based strategy to guarantee the reserved bandwidth of an input port on each output port of the switch. It keeps track of the difference between the reserved bandwidth and actually received bandwidth, and minimizes the difference to ensure fairness. Moreover, in order to fully utilize the multicast capability provided by the switch, CMF lets a multicast packet simultaneously send transmission requests to multiple output ports. In this way, a multicast packet has more chances to be delivered to multiple destination output ports in the same time slot and thus to achieve short multicast latency. Extensive simulations are conducted to evaluate the performance of CMF, and the results demonstrate that CMF achieves the two design goals: fair bandwidth allocation and short multicast latency.     

Topology Design of Network-Coding-Based Multicast Networks

It is anticipated that a large amount of multicast traffic needs to be supported in future communication networks. The network coding technique proposed recently is promising for establishing multicast connections with a significantly lower bandwidth requirement than that of traditional Steiner-tree-based multicast connections. How to design multicast network topologies with the consideration of efficiently supporting multicast by the network coding technique becomes an important issue now. It is notable, however, that the conventional algorithms for network topology design are mainly unicast-oriented, and they cannot be adopted directly for the efficient topology design of network-coding-based multicast networks by simply treating each multicast as multiple unicasts. In this paper, we consider for the first time the novel topology design problem of network-coding-based multicast networks. Based on the characteristics of multicast and network coding, we first formulate this problem as a mixed-integer nonlinear programming problem, which is NP-hard, and then propose two heuristic algorithms for it. The effectiveness of our heuristics is verified through simulation and comparison with the exhaustive search method. We demonstrate in this paper that, in the topology design of multicast networks, adopting the network coding technique to support multicast transmissions can significantly reduce the overall topology cost as compared to conventional unicast-oriented design and the Steiner-tree-based design.     

QoS based multicast routing algorithms for real time applications

In recent years, there has been a lot of interest in providing real-time multimedia services like digital audio and video over packet-switched networks such as Internet and ATM. These services require certain quality of service (QoS) from the network. The routing algorithm should take QoS factor for an application into account while selecting the most suitable route for the application. In this paper, we introduce a new routing metric and use it with two different heuristics to compute the multicast tree for guaranteed QoS applications that need firm end-to-end delay bound. We then compare the performance of our algorithms with the other proposed QoS-based routing algorithms. Simulations were run over a number of random networks to measure the performance of different algorithms. We studied routing algorithms along with resource reservation and admission control to measure the call throughput over a number of random networks. Simulation results show that our algorithms give a much better performance in terms of call throughput over other proposed schemes.     

GMAC: An overlay multicast network for mobile agent platforms

The lack of proper support for multicast services in the Internet has hindered the widespread use of applications that rely on group communication services such as mobile software agents. Although they do not require high bandwidth or heavy traffic, these types of applications need to cooperate in a scalable, fair and decentralized way. This paper presents GMAC, an overlay network that implements all multicast related functionality–including membership management and packet forwarding–in the end systems. GMAC introduces a new approach for providing multicast services for mobile agent platforms in a decentralized way, where group members cooperate in a fair way, minimize the protocol overhead, thus achieving great scalability. Simulations comparing GMAC with other approaches, in aspects such as end-to-end group propagation delay, group latency, group bandwidth, protocol overhead, resource utilization and failure recovery, show that GMAC is a scalable and robust solution to provide multicast services in a decentralized way to mobile software agent platforms with requirements similar to MoviLog.     

基于区域的无线传感器网络分簇组播路由算法

在资源受限的无线传感器网络中,组播由于能够有效的利用网络带宽并降低服务器的负担因而受到广泛的关注。提出了一种基于区域的组播路由算法,该算法中采用了分簇的结构,并能够根据传感器网络的能量和带宽都有限的特点和组播成员的分布动态的调整组播树的形状,从而能够在低开销的情况下为无线传感器网络提供良好的性能。     

基于网络编码的分布式无线光网络在线优化

最近, 一种集成骨干光传输网络、无源光网络和无线接入网的混合宽带无线光网络被提出。这种网络具有大带宽、低费用和无处不在的信息接入等特点。考虑在这种网络中的基于网络编码的多播会话的设计问题, 使得网络效用最大化, 而布网的费用最小化。这个问题被转换为一个混合的整数非线性规划问题, 精确求解极其困难。为了使得问题简化, 采用了一种两步优化方法进行求解, 交替地为多播会话选择光网络单元和网关。在每一次迭代过程中需要解决两个问题：光网络的网络编码设计问题和无线网络的用户和带宽分配问题。前者通过基于拉格朗日对偶分解的分布式方法实现; 后者通过广义Benders分解实现。通过仿真验证了所采用的方法的有效性。