Video streaming services over vehicular ad-hoc networks (VANETs) are in high demand for numerous applications associated with the connected vehicle (infotainment, driver assistance, accident support, etc.). However, streaming high-quality video through a VANET is not a trivial task, as the wireless channel is highly unreliable and suffers from bandwidth constraints. As a consequence, many packets may be lost, making it very difficult for the receiver to reconstruct a video with the minimum quality required. Our proposed scheme will combine several aspects of the overall video streaming architecture by following a cross-layer approach that includes: (a) the video packet stream content characteristics, (b) an adaptive forward error correction coding scheme, and (c) the use of QoS services. An adaptive RaptorQ coding scheme is proposed to protect the video packet stream without wasting the available network bandwidth. At the same time, we will use the QoS differentiated services of IEEE 802.11p to prioritise critical video packets, in order to avoid degradation of video quality during streaming. Finally, we will provide a mechanism to reduce the impact of synchronisation effects on the IEEE 1609.4 multiplexed service channel, which will reduce the packet collisions at the beginning of the service channel slot. All of these techniques, when properly combined, will enable high-quality video streaming services in urban VANET scenarios, thus providing a pleasant video quality experience to users even under different network conditions, with moderate to high packet error rates. In order to test the performance of our proposal, we will use a highly detailed simulation framework under different network conditions. The results of this work are expected to provide a feasible solution for high-quality video streaming services in urban VANETs.

Abstract This paper introduces a dual hybrid neural network model combining convolutional neural networks (CNNs) and artificial neural networks (ANNs) to optimize the quantization parameter (QP) for both $$64\times 64$$ 64 × 64 and $$32\times 32$$ 32 × 32 blocks in the versatile video coding (VVC) standard, enhancing video quality and compression efficiency. The model employs CNNs for spatial feature extraction and ANNs for structured data handling, addressing the limitations of current heuristic and just noticeable distortion (JND)-based methods. A dataset of luminance channel image blocks, encoded with various QP values, is generated and preprocessed, and the dual hybrid network structure is designed with convolutional and dense layers. The QP optimization is applied at two levels: the $$64\times 64$$ 64 × 64 model provides a global QP offset, while the $$32\times 32$$ 32 × 32 model refines the QP for further partitioned blocks. Performance evaluations using model error metrics like mean squared error (MSE), root mean squared error (RMSE), mean absolute error (MAE), as well as perceptual metrics like weighted PSNR (WPSNR), MS-SSIM, PSNR-HVS-M, and VMAF, demonstrate the model’s effectiveness. While our approach performs competitively with state-of-the-art algorithms, it significantly outperforms in VMAF, the most advanced and widely adopted perceptual quality metric. Furthermore, the dual-model approach yields better results at lower resolutions, whereas the single-model approach is more effective at higher resolutions. These results highlight the adaptability of the proposed models, offering improvements in both compression efficiency and perceptual quality, making them highly suitable for practical applications in modern video coding.

Abstract It is well-known that each new video coding standard significantly increases in computational complexity with respect to previous standards, and this is particularly true for the HEVC and VVC video coding standards. The development of techniques for reducing the required complexity without affecting the rate/distortion (R/D) performance is therefore always a topic of intense research interest. In this paper, we propose a combination of two powerful techniques, deep learning and parallel computing, to significantly reduce the complexity of the HEVC encoding engine. Our experimental results show that a combination of deep learning to reduce the CTU partitioning complexity with parallel strategies based on frame partitioning is able to achieve speedups of up to 26 $$\times$$ × when 16 threads are used. The R/D penalty in terms of the BD-BR metric depends on the video content, the compression rate and the number of OpenMP threads, and was consistently between 0.35 and 10% for the video sequence test set used in our experiments

In a near future, video transmission capabilities in intelligent vehicular networks will be essential for deploying high-demanded multimedia services for drivers and passengers. Applications and services like video on demand, iTV, context-aware video commercials, touristic information, driving assistance, multimedia e-call, etc., will be part of the common multimedia service-set of future transportation systems. However, wireless vehicular networks introduce several constraints that may seriously impact on the final quality of the video content delivery process. Factors like the shared-medium communication model, the limited bandwidth, the unconstrained delays, the signal propagation issues, and the node mobility, will be the ones that will degrade video delivery performance, so it will be a hard task to guarantee the minimum quality of service required by video applications. In this work, we will study how these factors impact on the received video quality by using a detailed simulation model of a urban vehicular network scenario. We will apply different techniques to reduce the video quality degradation produced by the transmission impairments like (a) Intra-refresh video coding modes, (b) frame partitioning (tiles/slices), and (c) quality of service at the Medium Access Control (MAC) level. So, we will learn how these techniques are able to fight against the network impairments produced by the hostile environment typically found in vehicular network scenarios. The experiments were carried out with a simulation environment based on the OMNeT++, Veins and SUMO simulators. Results show that the combination of the proposed techniques significantly improves the robustness of video transmission in vehicular networks, paving the way, with a wise collaboration with other techniques, to achieve a robust video delivery system that supports multimedia applications in future intelligent transportation systems.

Vehicular Ad-hoc Networks contribute to the Intelligent Transportation Systems by providing a set of services related to traffic, mobility, safe driving, and infotainment applications. One of the most challenging applications is video delivery, since it has to deal with several hurdles typically found in wireless communications, like high node mobility, bandwidth limitations and high loss rates. In this work, we propose an integrated simulation framework that will provide a multilayer view of a particular video delivery session with a bunch of simulation results at physical (i.e., collisions), MAC (i.e., packet delay), application (i.e., % of lost frames), and user levels (i.e., perceptual video quality). With this tool, we can analyze the performance of video streaming over vehicular networks with a high level of detail, giving us the keys to better understand and, as a consequence, improve video delivery services.

Uniform quantization schemas with dead zone are commonly used in image and video codecs. The design of these quantizers affects to the final R/D performance, being two of the quantizer parameters, the responsible for that variations: (a) the dead zone size and (b) the reconstruction point location inside each quantization step. We analyze how variations of these parameters, by means of a variable dead zone quantizer, affect to the R/D performance of wavelet-based image encoders, using three different quality metrics. We tune the quantizer for each image to obtain the optimum parameters that provide the best R/D behavior for each of the metrics for different rate ranges, without altering the rest of the encoder stages. We provide a general parameter set for each metric and rate range, to be used with other images to obtain important rate savings and better quality values for each metric.

Depth Image Base Rendering (DIBR) is an effective approach for 3D-TV, however quality and time consistence of the depth map is a problem in this field. Our intermediate solution between Intra and Inter encoders is able to cope with the quality and time consistency of the captured depth map info. Our encoder achieves the same visual quality than H264/AVC and x264 in Intra mode reducing coding delays.

This paper presents a perceptually enhanced intra-mode video encoder based on the Contrast Sensitivity Function (CSF) with a gracefully quality degradation as compression rate increases. The proposed encoder is highly competitive especially for high definition video formats at high video quality applications with constrained real-time and power processing demands.

Wavelet transforms have proved to be very powerful tools for image compression, since many state-of-the-art image codecs employ DWT into their algorithms. One advantage of this transform is the provision of both frequency and spatial localization of image energy compacted into a small fraction of the transform coefficients, equally likely to be positive or negative. Previous studies have verified that there is a strong correlation between the sign of a wavelet coefficient and the signs of their neighbors. This correlation opens the possibility of using a sign predictor in order to improve the image compression process. In this work we evaluate two algorithms, one based on Genetic programming and other based on Simulated Annealing process in order to obtain a good wavelet sign predictor.

The 3D-DWT is a mathematical tool of increasing importance in those applications that require an efficient processing of volumetric info. Other applications like professional video editing, IPTV video surveillance applications, live event IPTV broadcast, multi-spectral satellite imaging, HQ video delivery, etc, would rather use 3D-DWT encoders to reconstruct a frame as fast as possible. However, the huge memory requirement of the algorithms that compute the 3D-DWT is one of the main drawbacks in practical implementations. In this paper, we introduce a fast frame-based 3D-DWT video encoder with low memory usage. In addition, there is no need to divide the input video sequence into group of pictures (GOP), and it can be applied in a continuous manner, so that no boundary effects between GOPs appear.

Traditional embedded coding systems involve high complexity algorithms, requiring fast and expensive processors. In the last years, several authors have developed very fast and simple non-embedded wavelet encoders that are able to get reasonable good performance with reduced computing requirements. These encoders have lost the SNR scalability and precise rate control capabilities. In this paper, we propose a new non-embedded LTW codec version (E-LTW) with precise rate control method and good R/D performance due to the use of intra band neighboring context modeling for sign coding.

Providing quality-of-service (QoS) in wirelessadhocnetworks is an intrinsically complex task due to node mobility, distributed channel access, and fading radio signal effects. This goal can be successfully accomplished only through the cooperation of the different protocol layers involved. In this paper we propose a novel QoS architecture that is able to support applications with the bandwidth, delay, and jitter requirements in MANET environments. The proposed architecture is modular, allowing the plugging in of different protocols, which offers great flexibility. Despite its modularity, we propose optimizations based on interactions between the media access control (MAC), routing, and admission control layers which offer important performance improvements. We validate our proposal in scenarios where different network loads, node mobility degrees, and routing algorithms are tested in order to quantify the benefits offered by our QoS proposal. In particular, we have also used real H.264/AVC video traces to simulate video sources in order to measure the quality in terms of peak signal to noise ratio of the received video, so that the benefits of applying our QoS scheme to video sources can be assessed in terms of user satisfaction (from the applications perspective).

In this paper, a new algorithm to efficiently compute the two-dimensional wavelet transform is presented. This algorithm aims at low memory consumption and reduced complexity, meeting these requirements by means of line-by-line processing. In this proposal, we use recursion to automatically place the order in which the wavelet transform is computed. This way, we solve some synchronization problems that have not been tackled by previous proposals. Furthermore, unlike other similar proposals, our proposal can be straightforwardly implemented from the algorithm description. To this end, a general algorithm is given which is further detailed to allow its implementation with a simple filter bank or using the more efficient lifting scheme. We also include a new fast run-length encoder to be used along with the proposed wavelet transform for fast image compression and reduced memory consumption. When a 5-megapixel image is transformed, experimental results show that the proposed wavelet transform requires 200 times less memory and is five times faster than the regular one. If we consider the whole coding system, numerical results show that it achieves state-of-the-art performance with very low memory requirements and fast execution, becoming an interesting solution for resource-constrained devices such as mobile phones, digital cameras, and PDAs.

The 3D-DWT is a mathematical tool of increasing importance. However, the huge memory requirement of the algorithms that compute it is one of the main drawbacks in practical implementations. In this paper, we introduce a frame-by-frame algorithm to calculate the 3D-DWT with low memory usage. This algorithm is general, in the sense that it can be employed with any wavelet transform and, contrary to other proposals, it gets the same results as the regular wavelet transform. In addition, there is no need to divide the input video sequence into group of frames, and it can be applied in a continuous manner, so that coding efficiency is increased and no blocking artifacts appear.

Recently, there has been an increasing interest in the design of very fast wavelet image encoders focused on applications (interactive real-time image&video applications, GIS systems, etc) and devices (digital cameras, mobile phones, PDAs, etc) where coding delay and/or available computing resources (working memory and power processing) are critical for proper operation. Most of these fast wavelet image encoders are non-embedded in order to reduce complexity, so no rate control tools are available for scalable coding applications. In this work, we analyze the impact of simple rate control tools for these encoders in order to determine if the inclusion of rate control functionality is worth enough with respect to popular embedded encoders like SPIHT and JPEG2000. We perform the study by adding rate control to the nonembedded LTW encoder, showing that the increase in complexity still maintains LTW competitive with respect SPIHT and JPEG2000 in terms of R/D performance, coding delay and memory consumption.

In this paper, a very fast variation of the lower-tree wavelet (LTW) image encoder is presented. LTW is a fast non-embedded encoder with state-of-the-art compression efficiency, which employs a tree structure as a fast method of coding coefficients, being faster than other encoders like SPIHT or JPEG 2000. The alternative Huffman-based encoder presented in this paper serves to largely reduce the execution time, at the expense of loss in coding efficiency. Experimental results show that this encoder is more efficient than other very fast wavelet encoders, like the recently proposed PROGRESS (which is surpassed in up to 0.5 dB), and faster than them (from 4 to 9 times in coding). Compared with the JPEG 2000 reference software, the encoder is from 18 to 38 times faster, while PSNR is similar at low bit-rates, and about 0.5 lower at high bit-rates

Multipath routing protocols have proved to be able to enhance the performance of MANET in terms of reliability, load balancing, multimedia streaming, security, etc. However, deploying a QoS framework on top of such routing protocols is a complex task, requiring an appropriate QoS strategy to be developed and deployed. In this paper we propose such a strategy, validating it through simulation. The results achieved show that the proposed QoS framework can perfectly coexist with multipath routing protocols, achieving significant improvements on the overall network performance, especially from the point of view of demanding applications.

When comparing the performance of different video coding approaches, improvements or new codec designs, one of the most important performance metrics is the rate/distortion (R/D), where distortion use to be measured in terms of PSNR (peak signal-to-noise ratio) values. However, it is well known that this metric not always capture the distortion perceived by the human being. So, a lot efforts were performed to define an objective video quality metric that is able to measure video quality distortion close to the one perceived for the destination user. In this work, we perform a study of different available objective quality metrics in order to evaluate their behaviour, taking as reference the classical PSNR metric. Our purpose is to find, if any, a video quality metric that is able to substitute PSNR for video quality assessment and determine a more accurate R/D performance metric when designing and evaluating video codec proposals

In this paper, a new image compression algorithm is proposed based on the efficient construction of wavelet coefficient lower trees. The main contribution of the proposed lower-tree wavelet (LTW) encoder is the utilization of coefficient trees, not only as an efficient method of grouping coefficients, but also as a fast way of coding them. Thus, it presents state-of-the-art compression performance, whereas its complexity is lower than the one presented in other wavelet coders, like SPIHT and JPEG 2000. Fast execution is achieved by means of a simple two-pass coding and one-pass decoding algorithm. Moreover, its computation does not require additional lists or complex data structures, so there is no memory overhead. A formal description of the algorithm is provided, while reference software is also given. Numerical results show that our codec works faster than SPIHT and JPEG 2000 (up to three times faster than SPIHT and fifteen times faster than JPEG 2000), with similar coding efficiency

In this paper, a new algorithm to efficiently implement the two-dimensional lifting scheme is presented. The 1D lifting-scheme performs in-place processing of the input samples, and hence it provides reduction in memory requirements. However, for image processing (2D), in-place computation is not enough, resulting in a memory-intensive algorithm, since it has to keep the whole image in memory. We propose the use of line-by-line processing algorithm for the lifting scheme, and we address some issues on how to perform synchronization among different buffer levels, so that an implementation can be easily written. Experimental results show that, for a 5-megapixel image, our algorithm requires 200 times less memory and it is more than 3 times faster than the usual one.

QoS support in MANETs is a hard and challenging task due to the intrinsic complexities of these networks. In this work we present a solution called DACME to support real-time services in MANETs based on distributed admission control. Using the IEEE 802.1 Ie MAC technology as our basis for traffic differentiation, we develop a technique based on probes to assess available bandwidth in an end-to-end path, as well as the end-to-end delay and jitter. Results show that our technique is quite promising due to the degree of accuracy achieved estimating the different network parameters, while maintaining acceptable levels of traffic overhead and admission delay. Also, since no demands are imposed on intermediate stations, it can be easily deployed.

In this work, we propose a QoS architecture for MANETs based on a probe-based distributed admission control mechanism and the IEEE 802.11e technology. Our aim is to improve peer-to-peer communication in wireless mobile ad hoc networks by supporting real-time multimedia streaming. This technology can adapt to applications with bandwidth, delay and jitter constraints, and yet we keep to a minimum the requirements imposed on intermediate stations. Simulation results show that we successfully achieve our goal of supporting QoS-constrained applications in MANETs with a low overhead, confirming the adequateness of using probe-based admission control in these environments.

Mobile ad-hoc networks (MANETs) present quite large packet loss bursts due to mobility. In this work we propose two models based on hidden Markov models for estimating packet arrivals and packet loss patterns in MANETs. These models help the evaluation and tuning of multimedia streaming applications in terms of simulation time and required resources. In particular, we show how these models can be applied in the design of error concealment algorithms to increase the video coding resilience. The obtained results show that we get comparable results without the need for several long simulation runs. Finally, we also propose a set of new metrics for packet loss patterns analysis that can be of interest for the evaluation of audio/video streaming applications.

A new image compression algorithm is proposed based on the efficient construction of wavelet coefficient lower trees. This lower-tree wavelet (LTW) encoder presents state-of-the-art compression performance, while its temporal complexity is lower than the one presented in other wavelet coders, like SPIHT and JPEG2000. This fast execution is achieved by means of a simple two-pass coding and one-pass decoding algorithm. On the other hand, its computation does not need additional lists or complex data structures so there is no memory head. A formal description of the algorithm is provided, so that an implementation can be performed straightforwardly. The results show that the codec works faster than SPIHT and JPEG2000 with better performance in terms of rate-distortion metric.

In this paper, we analyze in depth the effect of using ITB in the network, showing that they not only serve for guaranteeing minimal routing, but also that they are a powerful mechanism able to balance network traffic and reduce network contention. To demonstrate these capabilities, we apply the ITB mechanism to improved routing schemes, such as DFS and smart-routing. These routing algorithms (without ITB) are able to improve the performance of up*/down* by 30 percent and 90 percent, respectively, for a 32-switch network. The evaluation results show that, when ITB are used together with these improved routing algorithms, network throughput achieved by DFS and smart-routing can still be improved by 56 percent and 23 percent, respectively. However, smart-routing requires a time to compute the routing tables that rapidly grows with network size, it being impossible in practice to build networks with more than 32 switches. This high computational cost is mainly motivated by the need of obtaining deadlock-free routing tables. However, when ITB are used, one can decouple the stages of computing routing tables and breaking cycles. Moreover, as stated above, ITB can be used to reduce network contention. In this way, in this paper, we also propose a completely new routing algorithm that tries to balance network traffic by using a simple and low time consuming strategy. The proposed algorithm guarantees deadlock freedom and reduces network contention with the use of ITB. The evaluation results show that our algorithm obtains unprecedented throughputs in 32-switch networks, tripling the original up*/down* and almost doubling smart-routing.

Networks of workstations (NOWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. These networks allow the customer to connect processors using irregular topologies, providing the wiring flexibility, scalability and incremental expansion capability required in this environment. Some of these networks use source routing and wormhole switching. In particular, we are interested in Myrinet networks because they are a well-known commercial product and their behavior can be controlled by the software running on the network interfaces (the Myrinet Control Program, MCP). Usually, the Myrinet network uses up*/down* routing for computing the paths for every source-destination pair. In this paper, we propose an in-transit buffer (ITB) mechanism to improve the network performance. We apply the ITB mechanism to NOWs with up*/down* source routing, like the Myrinet, analyzing its behavior on networks with both regular and irregular topologies. The proposed scheme can be implemented on Myrinet networks by simply modifying the MCP, without changing the network hardware. We evaluate by simulation several networks with different traffic patterns using timing parameters taken from the Myrinet network. The results show that the current routing schemes used in Myrinet networks can be strongly improved by applying the ITB mechanism. In general, our proposed scheme is able to double the network throughput on medium and large NOWs. Finally, we present a first implementation of the ITB mechanism on a Myrinet network.

Networks of workstations (NOWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. These networks allow the customer to connect processors using irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. Some of these networks use source routing and wormhole switching. In particular, we are interested in Myrinet networks because it is a well-known commercial product and its behavior can be controlled by the software running in network interfaces (Myrinet Control Program, MCP). Usually, the Myrinet network uses up*/down* routing for computing the paths for every source-destination pair. We propose the In-Transit Buffer (ITB) mechanism to improve network performance. We apply the ITB mechanism to NOWs with up*/down* source routing, like Myrinet, analyzing its behavior on both networks with regular and irregular topologies. The proposed scheme can be implemented on Myrinet networks by only modifying the MCP, without changing the network hardware. We evaluate by simulation several networks with different traffic patterns using timing parameters taken from the Myrinet network. Results show that the current routing schemes used in Myrinet networks can be strongly improved by applying the ITB mechanism. In general, our proposed scheme is able to double the network throughput on medium and large NOWs. Finally, we present a first implementation of the ITB mechanism on a Myrinet network.

During the last decade, a lot of research and development efforts have been made to design competitive still image coders for several kinds of applications. We present a new wavelet still-image coder, called LTW (lower-tree wavelet), based on the construction and codification of coefficient trees, as other proposals are. This algorithm is fast and symmetric (except at extremely low bit rates), which makes it adequate for real-time interactive multimedia applications. We have compared our algorithm with several well-known coders in terms of rate-distortion performance using the standard Lena image. Results show that LTW, with lower temporal complexity, achieves better results than EZW (0.8 dB PSNR) and stack-run (0.13 dB) coders. Also, we have tested the temporal complexity of the LTW algorithm, resulting in it being 3.5 times faster than an optimized EZW (embedded zero-tree wavelet) encoder.

The current standard Ethernet switches are based on the Spanning Tree (ST) protocol. Their most important restriction is that they can not work when the topology has active loops. In fact, the ST protocol selects a tree from the real topology by blocking the links that are not involved in the tree. This restriction produces a network traffic unbalancing behavior saturating those link near the root switch while rest of links will be idle or with a very low utilization. This paper proposes a new transparent switch protocol for Gigabit Ethernet backbones that considerably improves the performance of current ones. The proposed protocol is named ALOR for Active Loops and Optimal Routing. ALOR protocol could be used in the last stage of a fat tree network in order to allow a final backbone with active loops. So, rings, mesh and other regular/irregular active loop topologies can be used to connect the Gigabit switches in order to obtain better performance results.

Clusters of workstations (COWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. In these systems, the interconnection network connects hosts using irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. Myrinet is the most popular network used to build COWs. It uses source routing with the up*/down * routing algorithm. In previous papers we proposed the In-Transit Buffer (ITB) mechanism that improves network performance by allowing minimal routing, balancing network traffic, and reducing network contention. The mechanism is based on ejecting packets at some intermediate hosts and later re-injecting them into the network. Moreover, the ITB mechanism does not require additional hardware as it can be implemented on the software running at Myrinet network adapters. In this paper, we present a first implementation of the ITB mechanism on Myrinet GM software. We show the changes required in packet format and the modifications performed in the Myrinet Control Program (MCP). In addition, both the overhead introduced by the new code and the cost of extracting and re-injecting packets are measured. Results show that, even for this simple implementation, code overhead is only about 125 ns per packet and the message latency increase for messages that use the ITB mechanism is around 1.3 s per ITB. This is the first attempt to implement this mechanism, showing that a real implementation of ITBs is feasible on Myrinet COWs, and the associated overhead does not restrict the potential benefits of this mechanism. 1.

In previous papers, we have proposed the in-transit buffer mechanism (ITB) to improve network performance in COWs with irregular topology and source routing. This mechanism allows the use of minimal paths among all hosts, breaking cyclic dependences between channels by storing and later re-injecting packets at some intermediate hosts. However it also has two additional features that can improve even more network performance. First, the ITB mechanism reduces network contention because some messages are ejected from the network freeing network links. Second the ITB mechanism allows the use of any path between each source-destination pair improving traffic balance. In this paper we present a new routing algorithm that takes advantage of ITB by exploiting both issues: traffic balance and network contention reduction. The evaluation results show that network throughput can be considerably improved. On average, network throughput increases with respect to up*/down* by factors of 2.51 and 3.77 in 32 and 64-switch networks, respectively.

Networks of workstations (NOWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. In these machines, the network connects processors using irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. Also, when performance is the primary concern, these network products are being used to build large commodity clusters with regular topologies. In previous papers, we have proposed the in-transit buffer mechanism to improve network performance, applying it to NOWs with irregular topology and source routing. This mechanism allows the use of minimal paths among all hosts, breaking cyclic dependencies between channels by storing and later re-injecting packers at some intermediate hosts. In this paper we apply the in-transit buffer mechanism to regular networks with source routing in order to improve their performance. Also, two path selection policies are evaluated. The first one will always choose the same minimal path from source to destination, whereas the second one will choose from different alternative minimal paths in a round-robin fashion. The evaluation results show that the overall network throughput can be doubled for large networks.

Networks of workstations (NOWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. Typically, these networks connect processors using irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. In some of these networks, messages are delivered using the up*/down* routing algorithm [9]. However, the up*/down* routing scheme is often non-minimal. Also, some of these networks use source routing [1]. With this technique, the entire path to destination is generated at the source host before the message is sent.

Networks of workstations (NOWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. Typically, these networks connect processors using irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. In some of these networks, packets are delivered using source routing. Due to the irregular topology, the routing scheme is often non-minimal. In this paper we analyze the routing scheme used in Myrinet networks in order to improve its performance. We propose new routing algorithms that balance the utilization of the available routes and always use minimal paths. We show through simulation that the current routing schemes used in Myrinet networks can be improved by modifying only the routing software without increasing the software overhead significantly. The overall throughput can be doubled without modifying the network hardware.

Networks of workstations (NOWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. Typically, these networks connect processors using irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. Similar to the evolution of parallel computers, NOWs are also evolving from distributed memory to shared memory programming model. However, physical distances between processors are longer in NOWs than in tightly-coupled distributed shared-memory multiprocessors (DSMs), leading to higher message latency and lower network bandwidth. Therefore, the network may be a bottleneck when executing some parallel applications in a NOW supporting a shared-memory programming paradigm. In this paper we analyze whether the interconnection network is able to efficiently handle the traffic generated in a NOW with the shared memory model. In particular, we are interested in analyzing the influence of the routing mechanism in the performance of the system. We evaluate the behavior of a NOW with irregular topology by means of an execution-driven simulator using SPLASH-2 applications as the input load. The results show that the routing algorithm can considerably reduce the total execution time of applications. In particular routing adaptivity can reduce the total execution time by 58% in some applications. These results confirm the behavior observed in previous works using synthetic traffic loads.

Networks of workstations (NOWs) are becoming increasingly popular as an alternative to parallel computers. Typically, these networks present irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. Similar to the evolution of parallel computers, NOWs are also evolving from distributed memory to shared memory. However distances between processors are longer in NOWs, leading to higher message latency and lower network bandwidth. Therefore, one can expect the network to be a bottleneck when executing some parallel applications on a NOW supporting a shared-memory programming paradigm. The authors analyze whether the interconnection network in a NOW is able to efficiently handle the traffic generated in a DSM with the same number of processors. They evaluate the behavior of a NOW using application traces captured during the execution of several SPLASH2 applications on a DSM simulator. They show through simulation that the adaptive routing algorithm previously proposed by them almost eliminates network saturation due to its ability to support a higher sustained throughput. Therefore, adaptive routing becomes a key design issue to achieve similar performance in NOWs and tightly-coupled DSMs.