Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions

A variant of the High Multiplicity Multiprocessor Scheduling Problem with C job lengths is considered, in which jobs can be processed only by machines not greater than a given index. When C=2, polynomial algorithms are proposed, for the feasibility version of the problem and for maximizing the number of scheduled jobs.     

Optimal radio resources and transmission formats assignment in OFDMA systems

The problem of assigning radio resources and transmission formats to users in the downlink of an OFDMA network is addressed. In particular, a single cell environment with a realistic interference model and a margin adaptive approach is considered, i.e., the aim is of minimizing the total transmission power while maintaining a certain given rate for each user. The computational complexity issues of the problem are discussed, and an approximation analysis is presented. Heuristic approaches, based on rounding techniques and graph models, are also proposed. Computational experiences show that, in a comparison with a commercial state-of-the-art optimization solver and with alternatives from the literature, the proposed algorithms are effective in terms of solution quality and CPU times.     

Amplification effects of the send rate of TCP connection through an optical burst switching network

This paper investigates support for TCP RENO flows in an Optical Burst Switching (OBS) network. In particular we evaluate the TCP send-rate, i.e., the amount of data sent per time unit taking into account the burst assembly mechanism at the edge nodes of the OBS network and burst loss events inside the network. The analysis demonstrates an interesting phenomenon, that we call correlation benefit. This phenomenon is introduced by the aggregation mechanism and can give rise, in some conditions, to a significant increase in the TCP send-rate. These results are obtained by means of an analytical model, based on a Markovian approach, and have been validated via an intensive simulation campaign.     

Supporting the Web with an information centric network that routes by name

Information Centric Networking (ICN) is a new paradigm in which the network layer provides users with content, instead of providing communication channels between hosts, and is aware of the name (or identifiers) of the contents. A fundamental ICN operation is the routing of content requests towards a node that is able to provide the requested content. To meet this goal, different routing architectures have been proposed so far.     

Performance evaluation of a new technique for IP support in a WDMoptical network: optical composite burst switching (OCBS)

The optical composite burst switching (OCBS) technique is proposed to be implemented in an all-optical backbone network to support Internet protocol (LP) traffic. The OCBS is based on two main features. First, several IP packets are assembled in a single macropacket, called burst. Second, the burst contention in an optical switch is handled by means of two techniques, the wavelength dimension and the burst-dropping (BD) technique. Different from traditional optical burst switching, where an entire burst is discarded when all of the output wavelengths are engaged at the arrival instant of the burst, a switch adopting the BD technique discards only the initial part of a burst finding all of the engaged output wavelengths while forwarding the final part of the burst, beginning at the instant in which one wavelength becomes free. The OCBS allows an increase in the switch throughput in terms of number of accepted IP packets because a burst contains a given number of IP packets. We introduce the analytical model that allows us to evaluate the effectiveness of the technique and, in particular, the obtained saving; furthermore, a sensitivity analysis of the saving, with respect to both the optical burst switch parameters and the traffic load, is carried out     

Minimizing and balancing setups in a serial production system

This paper addresses a problem arising in the coordination between two consecutive manufacturing departments of a production system, in which parts are processed in batches, and each batch is characterized by two distinct attributes. Due to limited interstage buffering between the two stages, the two departments have to follow the same batch sequence. In the first department, a setup occurs every time the first attribute of the new batch is different from the previous one. In the downstream department, there is a setup when the second attribute of the new batch changes. The problem consists of finding a common batch sequence optimizing some global utility index. Here we propose a metaheuristic approach to a bi-criteria version of the problem considering two indices, namely the total number of setups paid for by the two departments and the maximum number of setups paid for by either department.     

Overlay,Borůvka‐based,Ad‐hoc multicast Protocol: description and performance analysis

This paper presents a novel Mobile Ad‐hoc NETworks (MANET) multicast protocol, named Overlay Borůvka‐based Ad‐hoc Multicast Protocol (OBAMP), and evaluates its performance. OBAMP is an overlay protocol: it runs only in the end‐systems belonging to the multicast group. OBAMP has three distinctive features, which give to the protocol a good performance in terms of distribution efficiency: (i) its distribution tree closely resembles the minimum spanning tree; (ii) it exploits broadcast communications; (iii) its design limits not only overlay signaling but also network‐layer signaling. In addition, OBAMP can cope with node failures in a very short time. As a consequence, OBAMP has a low latency and a high delivery ratio, even when the group size increases. To prove these statements, we analyze the performance of OBAMP with ns‐2 and compare it with three state‐of‐the‐art protocols, namely ODMRP (a network‐layer protocol), ALMA, and AMRoute (two overlay protocols). The overlay protocols are assumed to use AODV as underlying routing protocol. Also, we stress that we have implemented OBAMP, in Java, and we have tested it on the field, to prove its feasibility; to allow fellow researchers to reproduce and test our work we published all simulation and implementation codes. Copyright © 2007 John Wiley & Sons, Ltd.     

Optimal packet scheduling in UTRA-TDD

In UTRA-TDD, packets with different formats and quality-of-service (QoS) requirements are sent across the air interface organized into radio frames. We propose a frame-by-frame exact downlink scheduling algorithm based on dynamic programming, considering different traffic classes with their QoS levels.     

Sequencing unreliable jobs on parallel machines

This paper addresses an allocation and sequencing problem motivated by an application in unsupervised automated manufacturing. There are n independent jobs to be processed by one of m machines or units during a finite unsupervised duration or shift. Each job is characterized by a certain success probability p _i , and a reward r _i which is obtained if the job is successfully carried out. When a job fails during processing, the processing unit is blocked, and the jobs subsequently scheduled on that machine are blocked until the end of the unsupervised period. The problem is to assign and sequence the jobs on the machines so that the expected total reward is maximized. This paper presents the following results for this problem and some extensions: (i) a polyhedral characterization for the single machine case, (ii) the proof that the problem is NP-hard even with 2 machines, (iii) approximation results for a round-robin heuristic, (iv) an effective upper bound. Extensive computational results show the effectiveness of the heuristic and the bound on a large sample of instances.