The robustness of human social networks against epidemic propagation relies on the propensity for physical contact adaptation. During the early phase of infection, asymptomatic carriers exhibit the same activity level as susceptible individuals, which presents challenges for incorporating control measures in epidemic projection models. This article focuses on modeling and cost-efficient activity control of susceptible and carrier individuals in the context of the susceptible-carrier-infected-removed (SCIR) epidemic model over a two-layer contact network. In this model, individuals switch from a static contact layer to create new links in a temporal layer based on state-dependent activation rates. We derive conditions for the infection to die out or persist in a homogeneous network. Considering the significant costs associated with reducing the activity of susceptible and carrier individuals, we formulate an optimization problem to minimize the disease decay rate while constrained by a limited budget. We propose the use of successive geometric programming (SGP) approximation for this optimization task. Through simulation experiments on Poisson random graphs, we assess the impact of different parameters on disease prevalence. The results demonstrate that our SGP framework achieves a cost reduction of nearly 33% compared to conventional methods based on degree and closeness centrality.

Accurate and comprehensive data acquisition is critical for modern data-driven environmental applications. Mobile Crowdsensing (MCS) offers an effective approach by leveraging user participation to collect environmental data through task assignment. To minimize costs, MCS platforms often partition the environment into subareas and utilize inference algorithms to extrapolate data for entire subareas based on partial sensing in a limited subset. However, determining the optimal set of users for sensing tasks remains challenging due to constraints such as user availability and the complexity of data inference models. This paper introduces Sensify, a task assignment strategy that optimizes data acquisition by accounting for data correlations and budget constraints. Sensify efficiently selects subareas and recruits cost-effective users for sensing tasks, incorporating user-specific contexts such as location and device power availability during task assignment. To adaptively manage the platform budget, the strategy considers a dynamic set of users with varying costs over time. A deep recurrent reinforcement learning-based network is employed to select optimal subareas for sensing, while user recruitment is dynamically optimized using a reinforcement learning approach. Specifically, a modified Contextual Combinatorial Multi-Armed Bandit (CC-MAB) framework is utilized to handle the volatility and variability in user costs. Experiments conducted on two real-world datasets demonstrate that Sensify can improve data acquisition by up to 7% compared to existing approaches.

Software-defined networks (SDNs) provide customizable traffic control by storing numerous rules in on-chip memories with minimal access latency. However, the current on-chip memory capacity falls short of meeting the growing demands of SDN control applications. While rule eviction and aggregation strategies address this challenge at the switch level, programmable data planes enable a more flexible approach through cooperative rule caching. However, current solutions rely on computationally intensive off-the-shelf solvers to perform rule placement across the network. In this paper, we present an efficient solution for the cooperative rule caching problem. We first present the design of a resource-efficient switch capable of caching rules for its neighbors alongside a lightweight protocol for retrieving cached rules. Then, we introduce RaSe, an approximation algorithm for minimizing rule lookup latency across the network through optimized cooperation-aware rule placement. We conduct a theoretical analysis of RaSe, followed by a P4-based proof-of-concept assessment in Mininet and a large-scale numerical evaluation using real-world network topology. In comparison with existing solver-based solutions, the proposed method obtains the solution 160 times faster and improves the average rule lookup latency by about 21% compared to several algorithmic baselines.

The temporal nature of data in Internet of Things (IoT) networks necessitates periodic updates of cached content at edge devices, while multicasting dynamic content can enhance network efficiency. This paper addresses the challenge of joint cache updating and multicast scheduling in a cache-enabled, queue-equipped small base station (SBS) with limited cache capacity, which accesses a macro base station (MBS) to download (update) uncached (cached) content and serves requests through multicasting. We formulate a two-stage optimization problem to minimize the average age of information (AAoI) per request, subject to constrained average queueing delay and access rate. The first stage employs the Lyapunov drift-plus-penalty method at the SBS to schedule multicasting and downloading (updating) uncached (cached) content. The second stage, implemented at the MBS, leverages deep reinforcement learning (DRL) to determine the content replacement policy. Simulation results show that the DRL-based cache replacement policy yields up to 50%, 59%, and 60% improvements in AAoI compared to the maximum age, least-recently-used, and least-frequently-used baseline policies, respectively.

Edge computing (EC) has emerged as a paradigm aimed at reducing data transmission latency by bringing computing resources closer to users. However, the limited scale and constrained processing power of EC pose challenges in matching the resource availability of larger cloud networks. Load balancing (LB) algorithms play a crucial role in distributing workload among edge servers and minimizing user latency. This paper presents a novel set of distributed LB algorithms that leverage machine learning techniques to overcome the three limitations of our previous LB algorithm, EVBLB : (i) its reliance on static time intervals for execution, (ii) the need for comprehensive information about all server resources and queued requests for neighbor selection, and (iii) the use of a central coordinator to dispatch incoming user requests over edge servers. To offer increased control, custom configuration, and scalability for LB on edge servers, we propose three efficient algorithms: Q-learning (QL), multi-armed bandit (MAB), and gradient bandit (GB) algorithms. The QL algorithm predicts the subsequent execution time of the EVBLB algorithm by incorporating rewards obtained from previous executions, thereby improving performance across various metrics. The MAB and GB algorithms prioritize near-optimal neighbor node servers while considering dynamic changes in request rate, request size, and edge server resources. Through simulations, we evaluate and compare the algorithms in terms of network throughput, average user response time , and a novel LB metric for workload distribution across edge servers.

Information aging has gained prominence in characterizing communication protocols for timely remote estimation and control applications. This work proposes an Age of Information (AoI)-aware threshold-based dynamic frame slotted ALOHA (T-DFSA) for contention resolution in random access machine-type communication networks. Unlike conventional DFSA that maximizes the throughput in each frame, the frame length and age-gain threshold in T-DFSA are determined to minimize the normalized average AoI reduction of the network in each frame. At the start of each frame in the proposed protocol, the common Access Point (AP) stores an estimate of the age-gain distribution of a typical node. Depending on the observedstatus of the slots, age-gains of successful nodes, and maximum available AoI, the AP adjusts its estimation in each frame. The maximum available AoI is exploited to derive the maximum possible age-gain at each frame and thus, to avoid overestimating the age-gain threshold, which may render T-DFSA unstable. Numerical results validate our theoretical analysis and demonstrate the effectiveness of the proposed T-DFSA compared to the existing optimal frame slotted ALOHA, threshold-ALOHA, and age-based thinning protocols in a considerable range of update generation rates.

The emerging serverless computing paradigm has recently attracted huge attention from both academia and industry. It brings benefits, such as less operational complexity, high scalability and availability, and lower costs. Serverless applications are usually partitioned into several chains of functions. The serverless provider should schedule functions for execution per customers' requests considering their chained nature. Also, the existing scheduling mechanisms for serverless platforms pay little attention to the reduction of energy consumption during functions' execution. To fill this gap, we present an energy-aware execution scheduler for serverless service providers named EneX. To do so, we formulate the minimization of energy consumption for executing the incoming chains of functions with specified computational loads and deadlines. Due to the intractability of the problem, we introduce a linear programming reformulation based on which, we propose an online scheduler. Finally, our experiments demonstrate the significant improvement of EneX in terms of energy efficiency.

Power management in multi-server data centers especially at scale is a vital issue of increasing importance in cloud computing paradigm. Existing studies mostly consider thresholds on the number of idle servers to switch the servers on or off and suffer from scalability issues. As a natural approach in view of the Markovian assumption, we present a multi-level continuous-time Markov decision process (CTMDP) model based on state aggregation of multi-server data centers with setup times that interestingly overcomes the inherent intractability of traditional MDP approaches due to their colossal state-action space. The beauty of the presented model is that, while it keeps loyalty to the Markovian behavior, it approximates the calculation of the transition probabilities in a way that keeps the accuracy of the results at a desirable level. Moreover, near-optimal performance is attained at the expense of the increased state-space dimensionality by tuning the number of levels in the multi-level approach. The simulation results were promising and confirm that in many scenarios of interest, the proposed approach attains noticeable improvements, namely a near 50% reduction in the size of CTMDP while yielding better rewards as compared to existing fixed threshold-based policies and aggregation methods.

The peak power consumption has become an important concern in the hardware design process of some of today’s applications, such as energy harvesting (EH) and bio-implantable (BI) electronic devices. The limited peak harvested power in EH devices and heating concerns in BI devices are the main reasons for power control’s importance in these devices. This article proposes a generalized design approach for ultralow-power arithmetic circuits. The proposed circuits are based on residue number system (RNS) combined with deterministic bit-streams. The resulting circuits can be used in systems with a restricted power budget. We suggest several approaches to design generic hardware-efficient adders, multipliers, multiply-accumulate (MAC) unit, forward converters (FCs), and reverse converters (RCs). Using the proposed approach, designing these components for any moduli of the RNS can be performed through simple bit-width adjustments in the circuits. The synthesis results show that the proposed adder achieves, on average, 69% and 2% lower area compared to the bit-serial and a state-of-the-art RNS adder, respectively. Furthermore, the proposed multiplier outperforms the bit-serial, interleaved, and a state-of-the-art design for multiplying RNS numbers by, on average, 57%, 60%, and 77% in terms of power consumption, respectively. The efficiency of our approach is shown via two essential applications, digital signal processing, and machine learning. We implement an FFT engine using the proposed method. Compared to prior RNS implementations, our design achieves 47% lower power consumption. We also implement a CNN accelerator’s processing element (PE) with the proposed computation elements. Our design provides considerable speedup and lower power consumption compared to a state-of-the-art ultralower-power design.

Prediction and control of spreading processes in social networks (SNs) are closely tied to the underlying connectivity patterns. Contrary to most existing efforts that exclusively focus on positive social user interactions, the impact of contagion processes on the temporal evolution of signed SNs (SSNs) with distinctive friendly (positive) and hostile (negative) relationships yet, remains largely unexplored. In this paper, we study the interplay between social link polarity and propagation of viral phenomena coupled with user alertness. In particular, we propose a novel energy model built on Heider's balance theory that relates the stochastic susceptible-alert-infected-susceptible epidemic dynamical model with the structural balance of SSNs to substantiate the trade-off between social tension and epidemic spread. Moreover, the role of hostile social links in the formation of disjoint friendly clusters of alerted and infected users is analyzed. Using three real-world SSN datasets, we further present a time-efficient algorithm to expedite the energy computation in our Monte-Carlo simulation method and show compelling insights on the effectiveness and rationality of user awareness and initial network settings in reaching structurally balanced local and global network energy states.

Edge computing provides computational resources in the vicinity of end-users to reduce delay compared to traditional remote clouds. However, the capacity of edge resources usually is not sufficient for the required computational demands. Therefore, it is necessary to design methods for employing these resources in an efficient manner. On the other hand, network function virtualization (NFV) is a promising solution to use the network resources in a more flexible way than traditional schemes. Although more focus has been on realization of NFV systems via virtual machines so far, recent studies show that container-based solutions can improve efficiency thanks to lightweight implementation and layered structure of containers. Nonetheless, to the best of our knowledge, there is no comprehensive study on the problem of orchestrating services composed of a chain of containerized network functions in edge networks. In this paper, we consider this scenario when service requests are submitted to the system and address important aspects of this problem such as downloading and sharing container layers and steering traffic among network functions. We present the formulation of the problem as an integer linear program (ILP) and prove its NP-hardness. Then, to handle this problem, we propose RCCO, a polynomial-time algorithm based on ideas from deterministic and randomized rounding framework. Our results from extensive evaluations show that the bandwidth consumption of the proposed algorithm compared to the optimal algorithm is higher by only about 4% while it can outperform baselines from literature by more than 37%.

Content caching is perceived as a promising approach to offload traffic from shared medium networks by pre-fetching and placing contents in caches during off-peak hours, and taking advantage of multicasting in the delivery times. While most existing efforts on caching are directed towards reducing the traffic rate over the shared medium, little attention is given to user preferences. Though placement based on the heterogeneity of content popularity improves the caching performance, it is understood to be a non-trivial combinatorial optimization problem. In this paper, we investigate the content caching problem under non-uniform and user-dependent demands and propose several heuristic methods by leveraging hybrid coded-uncoded caching, clustering, and the trade-off between local and global popularity of contents. Simulation results validate our analysis and show the out-performance of the proposed schemes with respect to existing methods.

In serverless architectures, the scheduler component in the controller acts as a load-balancing entity and distributes the arriving tasks based on the availability of free resources on the machines. We argue that offering a multi-step decision-making process makes it feasible to allocate tasks to machines prudently, thus reducing the average response time to users. Aiming to achieve this, we propose to equip the controller with a limited cache for diverse purposes, including preserving the hash of task outcomes and storing the history of task deployment, in this paper. The response time is then further optimized by employing a batch-based technique and grouping the tasks. Evaluation results reveal that the proposed cache-aided serverless architecture can increase the average response time speed by nearly 21 %, on average, in the decision-making process.

Finite Impulse Response (FIR) filters are commonly used due to lower sensitivity to noise than their recursive counterparts. Computations of FIR filters require numerous multiply-and-accumulate (MAC) operations. Therefore, hard-ware implementation of high-order adaptive FIR filters results in a considerable area and power consumption. This paper proposes a hardware-efficient FIR engine based on the integration of deterministic approaches to Stochastic Computing (SC) with Residue Number Systems (RNS). The design inherits the intrinsic simplicity and low hardware requirements of SC circuits. As a contribution of our work, in contrast to other SC-based methods that impose errors on computations, our proposed method offers exact results like the binary implementations of FIR filters. Furthermore, the design decreases the required clock cycles, which can be translated to higher throughput in comparison with its SC predecessor (for example, 4× for 8-bit computations) at the cost of acceptable hardware overhead.

As the scale and speed of modern networks continue to increase, traffic sampling has become an indispensable tool in network management. While there exist a plethora of sampling solutions, they either provide limited flow visibility or have poor scalability in large networks. This paper presents the design and evaluation of FlowShark, a high-visibility per-flow sampling system for Software-Defined Networks (SDNs). The key idea in FlowShark is to separate sampling decisions on short and long flows, whereby sampling short flows is managed locally on edge switches, while a central controller optimizes sampling decisions on long flows. To this end, we formulate flow sampling as an optimization problem and design an online algorithm with a bounded competitive ratio to solve the problem efficiently. To show the feasibility of our design, we have implemented FlowShark in a small OpenFlow network using Mininet. We present experimental results of our Mininet implementation as well as performance benchmarks obtained from packet-level simulations in larger networks. Our experiments with a machine learning based Traffic Classifier application show up to 27% and 19% higher classification recall and precision, respectively, with FlowShark compared to existing sampling approaches.

Aggressive scaling in integrated circuits creates new challenges such as an increase in power density, temperature, and especially process variation in designing Multiprocessor Systems-on-Chip (MPSoC). While most of the previous works attempt to mitigate the process variation effects at the system level, the eventual design still suffers from the variability of frequency and leakage power. In this paper, we propose a method calledStereothat combinesstochastic and decomposition to solve task assignment and scheduling under process variation in MPSoCs. In our previous work, we formulated a Mixed Integer Linear Programming (MILP) problem for variation-aware task assignment and scheduling to optimize energy consumption while meeting the real-time constraints. To capture the stochastic behavior of process variation, we employed a chance-constrained programming technique to turn the problem into a corresponding stochastic optimization that can be solved by typical ILP solvers. However, it had a scalability problem. To address this issue, in this work, we leverage a Logic-based Benders Decomposition (LBD) approach to improve the running time for finding an optimal solution of assignments and schedulings under process variation phenomenon). We carried out extensive experiments using Embedded System Synthesis Benchmarks Suite (E3S). The experimental results of the Stereo method evince considerable improvements compared to the baseline method in terms of performance-yield and run-time. The Stereo-based MILP method ameliorates performance-yield up to 2× and run-time by 532×. Moreover, for manifold applications, the Stereo-based LBD method archives 3.47×-91.49× run-time improvement compared to the Stereo-based MILP approach and is capable of assigning and scheduling of more than 50 tasks on 9 processors.

Efficient and consistent update of the network routing rules is a challenging task that significantly affects the performance, correctness, and security of Software-Defined Networks (SDN). In this work, we consider the problem of minimizing the makespan of updating the routing rules in SDNs, while guaranteeing three crucial consistency requirements: (1) WayPoint Enforcement, (2) Loop Freedom, and (3) Conflict Freedom. This problem is known to be NP-hard, and thus we focus on designing approximate algorithms that run in polynomial time without incurring TCAM storage overhead. To compute consistent rule-update schedules, we propose two algorithms, calledTimeXandRMS.TimeXemploys the solution of a linear program (LP) to address the makespan minimization goal systematically.RMSis an LP-independent heuristic that provides higher scalability. We demonstrate and utilize a property of rule-updates, called reversibility, to reduce the makespan in RMS. Extensive simulations show that our algorithms reduce the makespan by 2% to 18% and attain a 4.9$\times$speedup compared to previous studies. Moreover, Mininet experiments reveal that the proposed algorithms can mitigate the transient congestion caused by conflicting flows.

As network virtualization becomes ubiquitous, legacy hardware-based traffic monitoring systems are no longer viable for dynamic traffic inspection at arbitrary locations in virtual networks. In this paper, we present the design and evaluation of Open Virtual Tap (OVT), a software-defined solution to replace hardware taps for traffic monitoring in OpenFlow virtual networks by utilizing mirroring capabilities of OpenFlow switches. The key idea behind OVT is the joint configuration of all switches in the substrate physical network in order to efficiently mirror flows from all virtual networks. We show that such a design avoids inefficiencies that result from existing software-based traffic mirroring solutions in which each virtual network configures its own switches independently of other virtual networks. We evaluate OVT using model-driven simulations as well as Mininet experiments with realistic applications for intrusion detection and video telephony analysis. Specifically, in our experiments, we observe that OVT can achieve up to 20% improvement in flow coverage compared to existing traffic mirroring approaches.

Prior research in hardware accelerators has largely focused on spatial convolutions (CONV). However, state-of-the-art DNNs employ low-rank convolutions (LR-CONV). LR-CONVs such as depthwise and pointwise convolutions exhibit lower arithmetic intensity and lower data re-use. LR-CONV s result in low hardware utilization and high latency. However, they provide opportunities for inter-layer data reuse. We propose X-Layer, which systematically explores the design space of cross-layer dataflows. We develop novel fine-grain cross-layer dataflows for LR-CONVs that support partial loop dimension completion. X-Layer decouples the nested loops in a pipeline and combines them to create a common outer dataflow and several inner dataflows. X-layer discovers additional opportunities for optimizing LR-CONVs: i) it overlaps adjacent layers at fine-granularity with partially completed channels and filters. This minimizes the intermediate storage required. ii) it enables each pipelined layer to independently choose optimal outer and inner dataflows by supporting streaming activation transformations. We explore a large design space of cross-layer dataflows and evaluate them for depth-separable, inverted residual, and CONV layers across six different DNNs. We also find that coarse-grain dataflows are sensitive to on-chip memory (≥ 1.5 MB) and performance drops steeply if enough on-chip SRAM is not provided. X-Layer dataflows find optimal performance across a wide range of on-chip memory (≥ 32KB). Compared to the existing coarse-grain and medium-grain dataflows, X-Layer improves the performance by 7.8× and 16.6×, while requiring 8.3× and 2× less SRAM.

Edge computing (EC)is a promising solution to enable the next-generation delay-critical network services which are not conceivable in the traditional cloud-based architecture. EC takes the computing and storage resources closer to the end-users at the edge of the networks to eliminate the propagation delays caused by geographical distances. However, due to the lack of facilities such as cooling systems, the capacity of available resources in the edge is far less than that in the remote clouds. So, efficient utilization of the edge resources has a profound impact on the effectiveness of the edge computing paradigm. Load balancing is a key factor in achieving resource efficiency and high utilization. In this paper, we present the design of EVBLB, an efficient load balancing algorithm based on Voronoi tessellation (VT) that assigns the users' service requests to the edge servers while considering the density of edge resources in the area and the distance of the users from the assigned servers. Building on the notion of VT not only allows us to achieve these goals, but is also computable in linear time, which significantly improves the scalability and responsiveness of our proposed method as compared to existing studies. Our simulation results show that EVBLB outperforms two conventional baselines in terms of throughput, response time, task completion time, and request blocking rate.

Generalized Sparse Matrix-Matrix Multiplication (Sparse GEMM) is widely used across multiple domains, but the computation’s regularity is dependent on the input sparsity pattern. The majority of sparse GEMM accelerators are based on the inner product method and propose new storage formats [5], [28], [31] to regularize computation. We find that these storage formats are more suited for denser matrices. Accelerators [26], [34] adopting the outer product algorithm are more suitable for highly sparse inputs $(\lt 1$% density), since they support CSC/CSR storage formats. The current state-of-the-art, SpArch [34], condenses inputs to improve output reuse, but then spoils input reuse. The condensing effectiveness varies across inputs leading to high variance in DRAM utilization and speedup across inputs. SpArch also requires a complex memory hierarchy (e.g., prefetch caches) to re-capture input reuse.We propose Spaghetti, an open-source Chisel generator for creating FPGA-optimized outer product accelerators. The key novelty in Spaghetti is a new pattern-aware software scheduler that analyzes the sparsity pattern and schedules row-col pairs of the inputs onto the fixed microarchitecture. Spaghetti takes advantage of our observation that the rows in the input matrix lead to mutually independent rows in the final output. Thus the scheduler can partition the input into tiles that maximize reuse and eliminate re-fetching the partial matrices from the DRAM. The microarchitecture template we create has the following key benefits: i) we can statically schedule the inputs in a streaming fashion and maximize DRAM utilization, ii) we can parallelize the merge phase and generate multiple rows of the output in parallel maximally using the output DRAM bandwidth, iii) we can adapt to the varying logic resources and bandwidth across various FPGA devices and attain maximal roofline performance (only limited by memory bandwidth). We auto-generate sparse GEMM accelerators on Amazon AWS FPGAs and demonstrate that we can achieve performance improvement over CPUs and GPUs between 1.1 – 34.5 x. Compared to SpArch [34], our design improves performance by an average of $2.6 \times$, and reduces DRAM accesses by an average of $4 \times$.

With widespread deployment of virtualization technologies in datacenter networks, traditional tools used for network monitoring, such as hardware taps, become unfit. This is due to the inability of hardware solutions for dynamic deployment and virtual network monitoring. This paper presents the design and evaluation of SoftTap, a scalable alternative to hardware taps which is capable of operating over both physical and virtual switches. SoftTap is based on port and flow mirroring capabilities of commodity OpenFlow switches and is not limited to a specific network architecture or topology. A key design challenge in SoftTap is the fast computation of switch mirroring configurations in large-scale deployments. Our design is based on novel polynomial time approximation algorithms that are shown to achieve bounded approximation ratios compared to optimal solutions. We evaluate SoftTap using model-driven simulations as well as realistic Mininet experiments. Specifically, our simulations consider large networks to show the scalability of SoftTap. Mininet experiments, on the other hand, consider its real-world utility by implementing an intrusion detection system (IDS) and a VoIP metering application on top of SoftTap. In our experiments, under SoftTap, IDS achieves up to 25% higher detection recall, while VoIP metering achieves up to 23% less packet loss compared to existing mirroring-based traffic monitoring approaches.

Nowadays, static power consumption in chip multiprocessor (CMP) is the most crucial concern of chip designers. Power-gating is an effective approach to mitigate static power consumption particularly in low utilization. Network-on-Chip (NoC) as the backbone of multi- and many-core chips has no exception. Previous state-of-the-art techniques in power-gating desire to decrease static power consumption alongside the lack of diminution in performance of NoC. However, maintaining the performance and utilization of the power-gating approach has not yet been addressed very well. In this article, we propose TAMA (Turn-Aware Mapping & Architecture) as an effective method to boost the performance of the TooT method that was only powering on a router during turning pass or packet injection. In other words, in the TooT method, straight and eject packets pass the router via a bypass route without powering on the router. By employing meta-heuristic approaches (Genetic and Ant Colony algorithms), we develop a specific application mapping that attempts to decrease the number of turns through interconnection networks. Accordingly, the average latency of packet transmission decreases due to fewer turns. Also, by powering on turn routers in advance with lightweight hardware, the latency of sending packets diminishes. The experimental results demonstrate that our proposed approach, i.e., TAMA achieves more than 13% reduction in packet latency of NoC in comparison with TooT. Besides the packet latency, the power consumption of TAMA is reduced by about 87% compared to the traditional approach.

Virtual Network Embedding (VNE) is an essential component of network virtualization technology. Prior works on VNE mainly focused on resource efficiency and did not address the scalability as a first-grade objective. Consequently, the ever-increasing demand and size render them less-practical. The few existing designs for mitigating this problem either do not extend to multi-resource settings or do not consider the physical servers and network simultaneously. In this work, we develop GraphViNE, a parallelizable VNE solution based on spatial Graph Neural Networks (GNN) that clusters the servers to guide the embedding process towards an improved runtime and performance. Our experiments using simulations show that the parallelism of GraphViNE reduces its runtime by a factor of 8. Also, GraphViNE improves the revenue-to-cost ratio by about 18%, compared to other simulated algorithms.

Emerging intelligent embedded devices rely on Deep Neural Networks (DNNs) to be able to interact with the real-world environment. This interaction comes with the ability to retrain DNNs, since environmental conditions change continuously in time. Stochastic Gradient Descent (SGD) is a widely used algorithm to train DNNs by optimizing the parameters over the training data iteratively. In this work, first we present a novel approach to add the training ability to a baseline DNN accelerator (inference only) by splitting the SGD algorithm into simple computational elements. Then, based on this heuristic approach we propose TaxoNN, a light-weight accelerator for DNN training. TaxoNN can easily tune the DNN weights by reusing the hardware resources used in the inference process using a time-multiplexing approach and low-bitwidth units. Our experimental results show that TaxoNN delivers, on average, 0.97% higher misclassification rate compared to a full-precision implementation. Moreover, TaxoNN provides 2.1× power saving and 1.65× area reduction over the state-of-the-art DNN training accelerator.

Deep Neural Networks (DNNs) are inherently computation-intensive and also power-hungry. Hardware accelerators such as Field Programmable Gate Arrays (FPGAs) are a promising solution that can satisfy these requirements for both embedded and High-Performance Computing (HPC) systems. In FPGAs, as well as CPUs and GPUs, aggressive voltage scaling below the nominal level is an effective technique for power dissipation minimization. Unfortunately, bit-flip faults start to appear as the voltage is scaled down closer to the transistor threshold due to timing issues, thus creating a resilience issue.This paper experimentally evaluates the resilience of the training phase of DNNs in the presence of voltage underscaling related faults of FPGAs, especially in on-chip memories. Toward this goal, we have experimentally evaluated the resilience of LeNet-5 and also a specially designed network for CIFAR-10 dataset with different activation functions of Rectified Linear Unit (Relu) and Hyperbolic Tangent (Tanh). We have found that modern FPGAs are robust enough in extremely low-voltage levels and that low-voltage related faults can be automatically masked within the training iterations, so there is no need for costly software-or hardware-oriented fault mitigation techniques like ECC. Approximately 10% more training iterations are needed to fill the gap in the accuracy. This observation is the result of the relatively low rate of undervolting faults, i.e., <0.1%, measured on real FPGA fabrics. We have also increased the fault rate significantly for the LeNet-5 network by randomly generated fault injection campaigns and observed that the training accuracy starts to degrade. When the fault rate increases, the network with Tanh activation function outperforms the one with Relu in terms of accuracy, e.g., when the fault rate is 30% the accuracy difference is 4.92%.

Content caching is a technique aimed to reduce the network load imposed by data transmission during peak time while ensuring users' quality of experience. Studies have shown that content delivery via coded caching can significantly improve beyond the performance limits of conventional caching schemes when caches and the server share a common link. Finding the optimal cache content placement however, becomes challenging under arbitrary distributions of content popularity. While existing works show that partitioning contents into three popularity levels performs better when multiple requests are received at each time slot, they neither delve into the problem analysis nor derive closed-form expressions for the optimum partitioning problem. In this paper, we analyze the coded caching scheme for a system with arbitrary content popularity, where we derive explicit closed-forms for the server load in the delivery phase and formulate the near-optimum partitioning problem. Simulation results are presented to corroborate our mathematical analysis.

Location fingerprinting is a technique employed when Global Positioning System (GPS) positioning breaks down within indoor environments. Since Location Service Providers (LSPs) would implicitly have access to such information, preserving user privacy has become a challenging issue in location estimation systems. This paper proposes a low-complexity k-anonymity approach for preserving the privacy of user location and trajectory, in which real location/trajectory data is hidden within k fake locations/trajectories held by the LSP, without degrading overall localization accuracy. To this end, three novel location privacy preserving methods and a trajectory privacy preserving algorithm are outlined. The fake trajectories are generated so as to exhibit characteristics of the user’s real trajectory. In the proposed method, no initial knowledge of the environment or location of the Access Points (APs) is required in order for the user to generate the fake location/trajectory. Moreover, the LSP is able to preserve privacy of the fingerprinting database from the users. The proposed approaches are evaluated in both simulation and experimental testing, with the proposed methods outperforming other well-known k-anonymity methods. The method further exhibits a lower implementation complexity and higher movement similarity (of up to 88%) between the real and fake trajectories.

Inaccuracy of computations is an important challenge with Stochastic Computing (SC). Deterministic approaches are proposed to produce completely accurate results with SC circuits. Current deterministic methods need a large number of clock cycles to produce exact result. This directly translates to a very high energy consumption. We propose a method based on the Residue Number Systems (RNS) to mitigate the high processing time of the deterministic methods. Compared to the state-of-the-art deterministic methods of SC, our approach delivers 760x and 170x improvement in terms of processing time and energy consumption.

Employing convolutional neural networks (CNNs) in embedded devices seeks novel low-cost and energy efficient CNN accelerators. Stochastic computing (SC) is a promising low-cost alternative to conventional binary implementations of CNNs. Despite the low-cost advantage, SC-based arithmetic units suffer from prohibitive execution time due to processing long bit-streams. In particular, multiplication as the main operation in convolution computation, is an extremely time-consuming operation which hampers employing SC methods in designing embedded CNNs.

Network operators are more than ever overwhelmed by increased capital investments and operational costs incurred due to the explosive mobile data traffic growth. An efficient strategy in managing operational expenditure within limits without sacrificing end-user satisfaction is to offload the traffic of content dissemination from the network backbone to local road-side units (RSUs). Allocating suitable subsets of contents to each RSU cache so as to maximize the hit ratio of requests made by vehicular entities is an optimization problem of paramount value. In this paper, we address the issue of content dissemination in a socially-aware hybrid environment with mobile end-users, wherein an overlay network comprising of a social network over a cellular vehicular network is considered. In this setting, vehicles represent the mobile nodes that obtain requested contents either from base station or from local RSUs, if available. By employing a mobile RSU that accounts for the social characteristics of the underlying network, we introduce a novel approach for content distribution in an urban environment. Results from simulation experiments reveal an average improvement of 6% in network throughput for the proposed method as compared to conventional content dissemination counterparts.

In content distribution networks, a key objective is the efficient utilization of the network that interconnects geographically distributed datacenters. This is a challenging problem due to vastly different characteristics and requirements of bulk and realtime transfers that share the interconnection network. Bulk transfers aim at delivering a copy of a usually large file to multiple datacenters before a deadline, while realtime transfers are absolutely delay-intolerant with unsteady and dynamic demands. In this paper, we consider the problem of multicasting deadline-critical bulk transfers in an inter-datacenter network in the presence of unknown and fluctuating demand by realtime transfers. Specifically, we develop a joint admission control and routing algorithm called PMDx, which anticipates future realtime demands and proactively reserves just the right amount of network resources in order to serve future realtime transfers without adversely affecting network utilization or bulk transfer deadlines. We show that the PMDx algorithm is a 2/δ-approximation with probability 1 - ϵ, and runs in polynomial time proportional to ln(1/ϵ)/(1 - δ)2, for 0 < δ,ϵ < 1. We also provide extensive model-driven simulation results to study the behaviour of our algorithms in real world network topologies. Our results confirm that PMDx is very close to the optimal, and improves the utilization of the network by 14% compared to a recently proposed algorithm.

Content caching has emerged as a promising technique to reduce the backhaul multimedia traffic rising due to the proliferation of mobile devices. To address the bottleneck issue arising as a result of sparse wireless resources, the current literature is mainly focused on designing centralized or decentralized coded caching schemes. In this paper, we present a hybrid coded caching approach in a cellular network considering mobile users, where both downlink transmission from the base-station (BS) and device-to-device (D2D) communications are permitted. The proposed method comprises of two phases in content delivery. In the first phase, coded packets are delivered using decentralized coded caching which provides concurrent transmissions through spatial reuse. The BS broadcasts the remaining files using the centralized coded caching paradigm in the second phase in order to compensate for the diminishing returns in D2D communications as time progresses. We analytically derive and analyze the optimal switching point for which the network performance improves in terms of throughput and response time delay under two random user mobility models. Validated by simulation results, our hybrid strategy significantly reduces the finishing time as compared to existing schemes.

Nowadays, aggressive scaling in integrated circuits brings out new challenges such as increase in power density, temperature, and process variation in designing Multiprocessor Systems-on-Chip (MPSoC) employed in embedded systems. While most of the previous works attempt to mitigate the process variation effects in system design level, the eventual design still is inefficient and suffers from the variability of frequency and leakage power of processors in a MPSoC. In this paper, we formulate a MILP problem for variation-aware task assignment and scheduling to optimize power consumption while meeting the real-time constraints. To capture stochastic behavior of process variation, we employ chance-constrained programming technique to turn the problem into a corresponding stochastic optimization one that can be solved by typical solvers. Extensive experiments using E3S benchmarks have been carried out and the obtained results of the proposed method evince improvements compared to the baseline method in terms of performance-yield and run-time.

Dynamic voltage and frequency scaling (DVFS) is a technique used to meet the power budget limitations in multi-core embedded systems. DVFS is applied to Networks-on-Chip (NoC) as a major contributor of the dissipated power on-chip. We propose an analytic model to accurately calculate the performance bounds on the best effort NoC with multiple voltage-frequency islands. The model supports dual-port buffer or handshaking mechanisms. We also suggest a method to set the frequencies of the islands to decrease the dissipated power. We examine our method and models and show their effectiveness.

Large-scale neural network accelerators are often implemented as a many-core chip and rely on a network-on-chip to manage the huge amount of inter-neuron traffic. The baseline and different variations of the well-known mesh and tree topologies are the most popular topologies in prior many-core implementations of neural networks. However, the grid-like mesh and hierarchical tree topologies suffer from high diameter and low bisection bandwidth, respectively. In this paper, we present ClosNN, a customized Clos topology for Neural Networks. The inherent capability of Clos to support multicast and broadcast traffic in a simple and efficient way, as well as its adaptable bisection bandwidth, is the major motivation behind proposing a customized version of this topology as the communication infrastructure of large-scale neural network implementations. We compare ClosNN with some state-of-the-art NoC topologies adopted in recent neural network hardware accelerators and show that it offers lower average message hop count and higher throughput, which directly translates to faster neural information processing.

Multiparty cloud video conferencing architecture has been recently advocated to exploit rich computing and bandwidth resources in the cloud to effectively improve video conferencing performance. As a typical design in this architecture, multiple agents, i.e., virtual machines, are deployed in different cloud sites, and users are assigned to the agents. Then, the users communicate through the agents, and the agents might transcode the recorded videos given the heterogeneities among devices in terms of hardware specification and connectivity. In this architecture, two critical and nontrivial challenges are: 1) assigning users to agents to reduce the operational cost and the user-to-user conferencing delay and 2) identifying best agents to perform transcoding tasks, taking into account the heterogeneous bandwidth and processing availabilities. To address these challenges, we cast a joint problem of user-to-agent assignment and transcoding-agent selection. The ultimate objective is to simultaneously minimize the cost of the service provider and the conferencing delay. The problem is combinatorial in nature, which belongs to the NP-hard node assignment problems. We leverage the Markov approximation framework and devise an adaptive parallel algorithm that finds a close-to-optimal solution to our problem with a bounded performance guarantee. To evaluate the performance of our solution, we implement a prototype video conferencing system and carry out trace-driven experiments. In a set of largescale experiments using PlanetLab traces, our solution decreases the operational cost by 77% and simultaneously yields lower conferencing delay compared with an existing alternative.

The demand for multimedia services in modern networks has experienced exponential growth in recent years and it is expected to dominate the mobile traffic in near future. On the other hand, the link capacity of mobile networks is limited due to the scarce wireless resources. Caching is a popular technique that uses available storage capability of the mobile devices to relieve this traffic tension in high peak hours of network operation. In this paper, we investigate the effect of mobility on a wireless device-to-device (D2D) coded caching architecture. Coded caching is a technique in which library files are split into sub-files and any combination of sub-files can be cached at devices and exchanged between them later. We consider two mobility models for our network architecture and study the effect of mobility on the throughput of the network. We show that, in contrast to the static scenario, by exploiting the mobility in a D2D coded caching network, the coded multi-casting gain and the spatial reuse gain can be attained simultaneously, in terms of the throughput scaling law.

Recent studies reveal that an adversary might trace the apparently insignificant traffic rate of source nodes over the net and turn such data to invaluable information so as to breach the privacy of the victim sources. Inhibiting the adversary of being able to extract information from the traffic rate of source nodes is a complicated task unless taking into consideration the flow conservation law effect of the transmitter queue. A reliable method of preserving the rate privacy that copes with the flow conservation law is to transmit original packets augmented with probabilistically dummy ones so as to change the observable aggregated traffic rate. Augmenting dummy packets, however, bears redundancy, and hence, requires extra resources in terms of bandwidth and buffer requirements, and more importantly suggests higher transmitting energy consumption. Grounded on the queueing and information theories, in this paper, we present an efficient method that minimally augments dummy packets to preserve the source rate privacy at a given degree while preserving the delay distribution of the original packets intact, and thus does not affect the quality of service parameters of the transmitted data in terms of delay and jitter. The presented method models the original packets and dummy ones with a preemptive resume 2-priority queueing system and then using information theory attempts to maximize the Fano lower bound of the best estimation of the adversary's speculation. All of the theoretically obtained results have been validated by conducting simulation experiments.

The cloud computing paradigm has been advocated in recent video conferencing system design, which exploits the rich on-demand resources spanning multiple geographic regions of a distributed cloud, for better conferencing experience. A typical architectural design in cloud environment is to create video conferencing agents, i.e., Virtual machines, in each cloud site, assign users to the agents, and enable inter-user communication through the agents. Given the diversity of devices and network connectivities of the users, the agents may also transcode the conferencing streams to the best formats and bitrates. In this architecture, two key issues exist on how to effectively assign users to agents and how to identify the best agent to perform a Transco ding task, which are nontrivial due to the following: (1) the existing proximity-based assignment may not be optimal in terms of inter-user delay, which fails to consider the whereabouts of the other users in a conferencing session, (2) the agents may have heterogeneous bandwidth and processing availability, such that the best Transco ding agents should be carefully identified, for cost minimization while best serving all the users requiring the transcoded streams. To address these challenges, we formulate the user-to-agent assignment and Transco ding-agent selection problems, which targets at minimizing the operational cost of the conferencing provider while keeping the conferencing delay low. The optimization problem is combinatorial in nature and difficult to solve. Using Markov approximation framework, we design a decentralized algorithm that provably converges to a bounded neighborhood of the optimal solution. An agent ranking scheme is also proposed to properly initialize our algorithm so as to improve its convergence. The results from a prototype system implementation show that our design in a set of Internet-scale scenarios reduces the operational cost by 77% as compared to a commonly-adopted alternative, while simultaneously yielding lower conferencing delays.

In deadline-constrained data aggregation in wireless sensor networks (WSNs), the imposed sink deadline in an interference-limited network hinders participation of all sensor nodes in data aggregation. Thus, a subset of nodes can contribute in aggregation and quality of aggregation (QoA) increases with the growth of the number of participating nodes. Scheduling the nodes' transmissions is a central problem, which aims to maximize the QoA, while satisfying the sink deadline, i.e., on-time delivery of the sensed data to the sink node. Although the previous studies have proposed optimal scheduling algorithms to this problem given a particular aggregation tree, there is no work on constructing optimal tree in this context. The underlying aggregation tree can make a big difference on QoA since we demonstrate that the ratio between the maximum achievable QoAs of different trees could be as large as O(2D), where D is the sink deadline. In this paper, we cast an optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. The problem is combinatorial in nature and difficult to solve as we prove its NP-hardness. We employ Markov approximation framework and devise two distributed algorithms with different computation overheads to find bounded close-to-optimal solutions. Simulation experiments in a set of representative randomly-generated scenarios show that the proposed algorithms significantly improve QoA by 101% and 93% on average compared to the best, to our knowledge, existing alternative methods.

SIMT accelerators are equipped with thousands of computational resources. Conventional accelerators, however, fail to fully utilize available resources due to branch and memory divergences. This underutilization is manifested in two underlying inefficiencies: pipeline width underutilization and pipeline depth underutilization. Width underutilization occurs when SIMD execution units are not entirely utilized due to branch divergences. This affects lane activity and results in SIMD inefficiency. Depth underutilization takes place when the pipeline runs out of active threads and is forced to leave pipeline stages idle. This work addresses both inefficiencies by harnessing inactive threads available to the pipeline. We introduce Harnessing inActive thReads in many-core Processors (or simply HARP) to improve width and depth utilization in accelerators. We show how using inactive yet ready threads can enhance performance. Moreover, we investigate implementation details and study microarchitectural changes needed to build a HARP-enhanced accelerator. Furthermore, we evaluate HARP under a variety of microarchitectural design points. We measure the area overhead associated with HARP and compare to conventional alternatives. Under Fermi-like GPUs, we show that HARP provides 10% speedup on average (maximum of 1.6X) at the cost of 3.5% area overhead. Our analysis shows that HARP performs better under narrower SIMD and shorter pipelines.

Recent advancements in wireless protocols and technologies such as IEEE 802.11n enhances communication systems in terms of offering high physical rates that are well-suited for multimedia and bandwidth-hungry applications. Since efficiency at the medium access control (MAC) layer decreases with increasing the physical rate, few researches have used aggregation, as a compensatory method, to improve efficiency. They have, however, underscored scalability in terms of parameters such as physical rate or number of users. Thus, providing a more scalable MAC protocol has become as issue of paramount concern. In this paper, we propose the Dual-channel Token-based MAC (DT-MAC) protocol that can provide scalability and improve efficiency especially for a large number of users and high physical rates. Then, DT-MAC is analytically evaluated in saturated conditions, and a predictable and optimal bandwidth allocation scheme to sub-channels is proposed. Simulation results for various parameters show that DT-MAC can approximately improve throughput 68% and decrease transmission delay and jitter nearly 90% compared with IEEE 802.11n for a dense high-data-rate single-hop network and operates well under low load.

In recent years, there has been an increasing demand for ubiquitous streaming like applications in data networks. In this paper, we concentrate on NUM-based rate allocation for streaming applications with the so-called S-curve utility functions. Due to non-concavity of such utility functions, the underlying NUM problem would be non-convex for which dual methods might become quite useless. To tackle the non-convex problem, using elementary techniques we make the utility of the network concave, however this results in reverse-convex constraints which make the problem non-convex. To deal with such a transformed NUM, we leverage Sequential Convex Programming (SCP) approach to approximate the non-convex problem by a series of convex ones. Based on this approach, we propose a distributed rate allocation algorithm which under mild conditions converges to a locally optimal solution of the original NUM. Numerical results validate the effectiveness, in terms of tractable convergence of the proposed rate allocation algorithm.

Modern GPUs synchronize threads grouped in warps. The number of threads included in each warp (or warp size) affects divergence, synchronization overhead, and the efficiency of memory access coalescing. Small warps reduce the performance penalty associated with branch and memory divergence at the expense of a reduction in memory coalescing. Large warps enhance memory coalescing significantly but also increase branch and memory divergence. Dynamic workload behavior, including branch/memory divergence and coalescing, is an important factor in determining the warp size returning best performance. Based on this observation, we propose Dynamic Warp Resizing (DWR). DWR outperforms static warp size decisions, up to 2.28X.

The rapid emergence of peer-to-peer streaming has attracted many interests during last years. Video streaming continuity perceived by the user and meeting rigorous constraints on delay are the two challenging issues of main concern. In this paper, we aim to explore the trade-off between these two competing goals through a biobjective problem formulation that maximizes some notions of playback continuity while minimizing some notions of delay. Our formulation uses explicit approximations of delay and playback continuity that is beneficial for modeling trade-off between the aforementioned competing performance metrics. We then study the Pareto-optimal points of the biobjective formulation through scalarization technique. Our numerical results endorse that the proposed biobjective formulation provides a good way of performance trade-off characterization for such systems.

Privacy preservation in wireless sensor networks has drawn considerable attention from research community during last few years. Emergence of single-owner, multi-user commercial sensor networks along with hostile and uncontrollable environment of such networks, makes the security issue in such networks of a great importance. This paper concentrates on token-based privacy preservation schemes. A possible attack on such schemes has been introduced. Two different approaches has been utilized to mitigate the attack. We present mathematical models for it's effects and overheads. The results have been verified using extensive simulations.

Grid-based networks (or grids for short), such as meshes and tori, have been the underlying topology for many multicomputers, and have been extensively studied in the past as a graph topology. In this paper, we investigate some topological properties of grids without boundary wrap-around (meshes) and with boundary wrap-around (tori). In particular, we study the problem of finding the number of nodes located at/within a given distance from a given node (surface area/volume) in the network and derive some expressions for computing such a number. Furthermore, we provide similar expressions that improve on previous results already reported in the literature for some special cases of grids, notably hypercubes and k-ary n-cubes. We also show some applications of the derived expressions in analytical performance modelling of some grid-based networks under uniform and hotspot traffic loads.

Motivated by applications like sensor, peer to peer networks there has been growing interest in monitoring large scale distributed systems. In these applications, source location anonymity is an attractive and critical security property. Most of prior works assumed a weak adversary model where the adversary sees only local network traffic, but here we consider source anonymity against a global eavesdropper. Attaining location unobservability under global attacker is very difficult and expensive to achieve, because sensor networks are very limited in resources. In this work we propose a distributed algorithm to mix real event traffic with carefully chosen dummy traffic to hide the real event traffic pattern. We assume that we have fixed amount of resources to send dummy traffic and we try to share it among sensors so as to maximize the degree of anonymity of the system. Through simulation, we illustrate that the proposed technique is efficient in protecting location information from the eavesdropper.

The research community has recently witnessed the emergence of densely deployed wireless sensor networks (WSNs) consisting of a large number of battery-operated sensor nodes. As a candidate for monitoring remote faulty regions, WSNs may suffer from hardware and software faults which may cause misbehavior of a portion of network. Geographic routing algorithms aims at traversing data packets in such environments with admissible communication complexity. In this paper, we propose a novel region routing algorithm that addresses message loss tolerability in harsh and hostile environments by assigning higher weights to higher harsh regions. Finally, we present extensive simulation experiments to validate the accuracy of the proposed algorithm.

Motivated by applications like sensor, peer to peer, ad hoc networks there has been growing interest in monitoring large scale distributed systems. In these applications typically we wish to monitor a global system condition which is defined as a function of local network elements parameters. In this paper, we study Aggregate Threshold Queries in sensor networks, which are used to detect when an aggregate value of all sensor measurements crosses a predetermined threshold. The major constraint in designing monitoring applications is reducing the amount of communication burden which is the dominant factor of energy drain in wireless sensor networks. In this study, we address the aggregate threshold monitoring problem by proposing a distributed algorithm to set local thresholds on each sensor node so that only those sensors whose measurements crosses their local thresholds commence communication. We adopt the FPTAS optimization formulation of the problem [1] and propose a distributed algorithm as the solution to the problem. Simulation results demonstrate the validity of the proposed distributed algorithm in attaining very close performance as the centralized scheme.

Wireless sensor networks (WSNs) are usually missioned to gather critical information in hostile and adversarial environments, which make them susceptible to compromise and revelation. Therefore, establishing secure communication in such networks is of great importance necessitating utilization of efficient key distribution schemes. In order to address such methods, several works using probabilistic, deterministic and hybrid approaches have been introduced in past few years. In this paper, we study the connectivity of key-distribution mechanisms in secured topologies of wireless sensor networks. We explore the effect of the radio range on the connectivity of the network and provide a lower bound on the radio range under which the cover time of the underlying topology decreases significantly. We also deduce that any broadcasting algorithm in such a network is performing only by a factor O(nß), where ß ¿ (0,1), worse than broadcasting algorithms in unsecured topologies. Our numerical results and simulation experiments validates the correctness and efficiency of our analysis.

Wired and wireless data networks have witnessed an explosive growth of inelastic traffics such as real-time or media streaming applications. Recently, applications relying on layered encoding schemes appeared in the context of live-streaming and video and audio delivery applications. This paper addresses the Network Utility Maximization (NUM) for scalable multimedia transmission which is relying on layered encoding schemes. Nonconvexity of the NUM problem for such applications makes dual-based approaches incompetent, whereby achieving optimality proves quite challenging. We adopt the staircase utility function and formulate the underlying optimization problem. To tackle the non-convexity of the problem, we use a smooth approximation of the staircase utility function and propose a dual-based distributed algorithm for rate allocation and bandwidth sharing in such scenarios. Numerical results show that the proposed algorithm achieves suboptimal yet efficient solution.

We consider two flow control schemes for best effort traffic in on-chip architectures, which can be deemed as the solutions to the boundary extremes of a class of utility maximization problem. At one extreme, we consider the so-called rate-sum flow control scheme, which aims at improving the performance of the underlying system by roughly maximizing throughput while satisfying capacity constraints. At the other extreme, we deem the max-min flow control, whose concern is to maintain max-min fairness in rate allocation by fairly sacrificing the throughput. We then elaborate our argument through a weighting mechanism in order to achieve a balance between the orthogonal goals of performance and fairness. Moreover, we investigate the implementation facets of the presented flow control schemes in on-chip architectures. Finally, we validate the proposed flow control schemes and the subsequent arguments through extensive simulation experiments.

The development of peer to peer overlay networks applications has attracted an immense interest from the research community in recent years. Several challenging issues have to be resolved in order to provide accessible, efficient and scalable inter-peer communication. Achieving resilience so as to reduce the disconnection probability, is among the most demanding issues to provide a robust and omnipresent service to peer to peer applications. This paper attempts to address this issue, by proposing a graph-theoretic model using the well-known star interconnection network with sub-logarithmic degree characteristics, which not only facilitate scalability problem, but also achieves maximum connectivity compared to the other existing graph-based methods. The simulation results confirm that the proposed solution attains a higher degree of resiliency compared to other existing topologies.

Multihoming has been broadly employed by large enterprises, and stub networks to augment the availability and reliability of their Internet access. In this technique, the edge network is connected to the Internet through multiple upstream Internet Service Providers (ISPs) rather than one. Thus far, different aspects of multihomed networks have received intensive attention in the research community. However, there have been quite a few works on the selection methodologies of upstream ISPs for a multihomed network which is definitely a primary prerequisite for other challenges in this area. In this paper, we try to address the ISP selection problem for provisioning of survivable end-to-end connections in multihomed networks. We first argue about different design decisions that the network operator has to make for support of resiliency against single-link network failures. Then, the minimum ISP selection problem is defined in which the goal is to pick the minimum number of upstream ISPs such that by multihoming to them, the major connections of the network would achieve a satisfactory level of resiliency against link failures. Then, we propose a brute-force method to optimally unravel this problem. Despite the NP-hardness of our problem, we show that the proposed method can be used in practice to solve the problem in tolerable manner.

Wired and wireless data networks have witnessed a rapid proliferation of multimedia applications such as live-streaming applications, video conferencing, etc. A desirable key feature for multimedia transmission over multiuser environments with heterogeneous users is the ability of adapting rate and quality of video stream to different QoS conditions. The most efficient approach to address the scalability of multimedia applications is to encode video stream in compliance with Scalable Video Coding (SVC) standard, which is proposed as an extension to H.264/AVC standard. This paper addresses the utility-proportional optimization for multimedia applications that are relying on SVC-encoded video signals. We use the staircase utility function to analytically model the SVC-encoded multimedia applications and formulate the underlying optimization problem. Non-convexity of the optimization problem for such applications makes dual-based approaches incompetent, whereby achieving optimality proves quite challenging. We use a smooth approximation of the utility function to come up with a convex formulation and propose a dual-based distributed algorithm for rate allocation and bandwidth sharing in such scenarios. Numerical results are proposed as the support to the proposed rate control algorithm.

Motivated by applications of sensor networks, there has been growing interest in monitoring large scale distributed systems. In these applications, we usually wish to monitor a global system condition defined as a function of local network elements parameters. In this paper, we study Reactive Monitoring in sensor networks, which has the benefit of operating in a decentralized manner. Our primary concern in adopting such a monitoring paradigm is reducing the communication cost which is the dominant factor of energy drain in wireless sensor networks. In this study, we address the reactive aggregate monitoring problem by casting the underlying threshold assignment as an optimization problem. This allow us to propose a distributed algorithm to set local thresholds on each sensor node to be adapted to the statistics of the events measured by spatially scattered sensor nodes. Through simulation, we illustrate that the proposed threshold assignment technique can significantly reduce the communication overhead of the monitoring mechanism in sensor networks.

Fault-tolerance and network routing have been among the most widely studied topics in the research of parallel processing and computer networking. A fault- tolerant routing algorithm should guarantee the delivery of messages in the presence of faulty components. In this paper, we present a comparative performance study of nine prominent fault-tolerant routings in 2D wormhole-switched tori. These networks carry the software-based routing scheme which has been suggested as an instance of a fault-tolerant method widely used in the literature to achieve high adaptivity and support inter-processor communications in parallel computer networks due to its ability to preserve both communication performance and fault-tolerant demands in such systems. The performance measures studied are the throughput, average message latency, power, and average usage of virtual channels per node. Results obtained through simulation suggest two classes of presented routing schemes as high performance candidates in most faulty networks.

Sensor nodes are usually deployed in adversarial environments in which they are subject to compromise and revelation of critical information rendering the entire network useless. Therefore, secure communication of wireless sensor networks (WSNs) necessitates utilization of efficient key distribution schemes. Over the past few years, several works using probabilistic, deterministic and hybrid methods have been conducted to address key distribution among sensor nodes. In this paper we propose a novel method to deterministically distribute key-chains throughout a WSN utilizing expander graphs based on the Zig-Zag graph product. Given a set of constraints such as network size, amount of storage, radio range and key-chain length, we are able to efficiently construct a resilient yet scalable key distribution graph. The main advantage of the obtained method is providing a more user-adjustable and predictable framework compared to the previously proposed approaches. Simulation results demonstrate the efficiency of our proposed scheme and its general applicability to different network paradigms with diverse requirements.

Designing appropriate buffer sizes for routers within Network-on-Chip (NoC) so as to minimize the power while preserving the required performance in the presence of self-similar traffic has been considered a challenging problem in the literature. A few analytical studies carried out in NoC modeling have been adopted assumptions such as exponentially-distributed packet inter-arrivals, and conclusions reached under such assumptions may be inappropriate in the presence of self-similar traffic. Through mathematical analysis this paper predicts the optimal buffer size under self-similar traffic using Discrete Poisson Pareto Burst Process (DPPBP). The validity of the mathematical expressions is demonstrated through simulation experiments.

Wireless sensor networks (WSNs) consist of large number of sensor nodes with limited sensing, processing and communication capabilities that cooperatively fulfill environmental sensing and monitoring tasks. WSNs are meant to be deployed in large numbers in various environments, including remote and more importantly harsh environments ensuing potential hardware or software faults which consequently may cause temporal unavailability of some sensor nodes. Geographic routing algorithms owing to low overhead of message passing and state preserving are very promising candidate for such environments. In this paper, we propose greedy weighted region routing (GWRR) algorithm that addresses message loss tolerability in harsh and hostile environments by assigning higher weights to harsher regions and then we present a nearly-optimal routing in dense WSNs. Moreover, we demonstrate that GWRR has low computational overhead. Simulation experiments confirm the validity of proposed algorithm with high degree of accuracy.

Peer-to-peer file sharing applications are major proportion of traffic in Internet. Among P2P file sharing applications, BitTorrent is known to be the most popular system, in which peers can download pieces of file proportional with upload bandwidth shared with others. Therefore, for such a system, bandwidth adjustment is very significant for peers. In this paper we aim at modeling this as a solution to an optimization problem which maximizes the portion of download bandwidth constrained by the average download time of peers. To solve this, we propose an iterative algorithm which can be implemented in a distributed manner with low computation and communication overhead.

Recent studies in modern telecommunication networks have convincingly revealed that IP traffic exhibits a perceptible self-similar behavior over a wide range of time scales. Adapting the traditional Poisson model can therefore lead to erroneous conclusions regarding network performance dynamics. On the other hand, with growing demand for greater bandwidth, several optical paradigms have been proposed as substitutes for the next-generation Internet backbone. Among all these approaches, optical burst switching (OBS) has been widely recognized as a suitable alternative to optical packet switching (OPS) due to its support for bursty traffic and high bandwidth granularity. Thus, devising suitable buffers so as to accurately capture the fractal behavior of multimedia traffic in such optical core switches has become a major scientific endeavor. For the first time, in this paper, we propose an analytical model with quality of service (QoS) provision at a complete OBS network level. We then study the performance of the presented model in terms of blocking probability. Using this model, we also study the impact of burst aggregation time on the total loss probability and validate its correctness through simulation results.

The research community has recently witnessed the emergence of multi-processor system on chip (MPSoC) platforms consisting of a large set of embedded processors. Particularly, Interconnect networks methodology based on Network-on-Chip (NoC) in MP-SoC design is imminent to achieve high performance potential. More importantly, many well established schemes of networking and distributed systems inspire NoC design methodologies. Employing end-to-end congestion control is becoming more imminent in the design process of NoCs. This paper presents a centralized congestion scheme in the presence of both elastic and streaming flow traffic mixture. In this paper, we model the desired Best Effort (BE) source rates as the solution to a utility maximization problem which is constrained with link capacities while preserving Guaranteed Service (GS) traffics services requirements at the desired level. We proposed an iterative algorithm as the solution to the maximization problem which has the benefit of low complexity and fast convergence. The proposed algorithm may be implemented by a centralized controller with low computation and communication overhead.

Top-k monitoring is a noteworthy query that recently has been put into practice in wireless sensor networks (WSN). In top-k monitoring (i.e., an instance of continuous distributed monitoring), base station or coordinator continuously monitors k sensors with the highest (or lowest) values. Since the goal in such applications is to perform monitoring task while incurring minimum communication (data traffic) overhead, local constraints should be set at remote sites to filter unnecessary updates. Thereby, the novelty of this paper lies on the investigation of a method called MOTE where model-based optimization technique is utilized to set filters at remote sensors. In the proposed technique, the problem of optimal filter setting for maintaining top-k set is formulated as a variant of set cover which is an np-hard problem with well studied approximation methods. Simulation results demonstrate the validity of the proposed MOTE algorithm in improving the performance compared to other filter setting methods.

In this paper, we proposed a graph theoretic approach employing an algorithmic method to construct constant-degree graphs possessing not only provably minimum diameter, but also maximum connectivity with respect to other similar graphs.

One of the key issues in the design of multiprocessors system-on-chip (MP-SoCs), multicomputers, and peer-to-peer networks is the development of an efficient communication network to provide high throughput and low latency and its ability to survive beyond the failure of individual components. Generally, the faulty components may be coalesced into fault regions, which are classified into convex and concave shapes. In this paper, we propose a mathematical solution for counting the number of common fault patterns in a 2-D mesh interconnect network including both convex (I-shape, II-shape, square-shape) and concave (L-shape, U- shape, T-shape, +-shape, H-shape) regions. The results presented in this paper which have been validated through simulation experiments can play a key role when studying, particularly, the performance analysis of fault-tolerant routing algorithms and measure of a network fault-tolerance expressed as the probability of a disconnection.

Abstract — Wireless ad hoc networks are so vulnerable to passive attacks and eavesdropping adversaries due to their shared medium which makes network traffic easy to capture and analyze. Therefore, security and privacy protections are of extreme importance for protocols and applications in such networks. In this paper, we introduce a new framework for anonymous routing, named chain-based routing, to improve the privacy. In our framework, nodes on a path are virtually bound to each other like a chain. Each node is only aware of its associated links in a flow and does not require any other information about source, destination, or other parts of the chain. Based on this framework, we propose an on-demand routing protocol, called Chain-based Anonymous Routing (CAR), which uses unicast-based broadcast data transfer to fulfill anonymous communication in wireless ad hoc networks. Through hiding identifiers of nodes inside the chain, CAR realizes sender, receiver, and relationship anonymity in addition to untraceability in the network. Moreover, it is resistant to a wide range of passive attacks while adapting to implement other security mechanisms in the presence of active attacks. Keywords-component; Wireless ad hoc networks, security, anonymity, chain-based routing, unicast-based broadcast. I.

The use of adaptively-routed wormhole switched k-ary n-cubes has been motivated by the high path diversity provided by the rich topology of this family of interconnection networks. Due to its insensitivity to message destination, adaptive wormhole switching has been an attractive design alternative not only in networks suggested for contemporary multicomputers but also in the new Network-on-Chip and System-on-Chip architectures. Although analytical performance models for wormhole switched networks have been widely reported in the literature over the past two decades, the majority of these models have unrealistically assumed negligible buffering capacity at each switching element of the network. This paper proposes the first analytical model to assess the performance of adaptively-routed wormhole-switched k-ary n-cubes with finite size buffers. The new model can also accounts for the use of any number of virtual channels in order to further improve system performance. The model is validated by means of an event-driven simulator and experiments show close agreement between model predictions and simulator results.

One of the fundamental problems in parallel computing is how to efficiently perform routing in a faulty network each component of which fails with some probability. This paper presents a comparative performance study of ten prominent adaptive fault-tolerant routing algorithms in wormhole-switched 2D mesh interconnect networks. These networks carry a routing scheme suggested by Boppana and Chalasani as an instance of a fault-tolerant method. The suggested scheme is widely used in the literature to achieve high adaptivity and support inter-processor communications in parallel computer systems due to its ability to preserve both communication performance and fault-tolerant demands in these networks. The performance measures studied are the throughput, average message latency and average usage of virtual channels per node. Results obtained through simulation suggest two classes of presented routing schemes as high performance candidate in most faulty networks.

Optical technology as a promising infrastructure is imminent in Internet core and metro networks to meet the ever increasing bandwidth demand from a large number of users in scientific, academic, and business communities, as well as in military and other government agencies. Recently, optical burst switching, or OBS, which represents a balance between circuit and packet switching, has opened up some stimulating new challenges in optical networking. Several analytical models of different aspects of optical technology in the Internet core, such as optical interconnections and OBS, have been proposed in the literature. To the best of our knowledge these models, however, have been ignored the impatience of messages traveling through optical switches in the Internet core. Fiber delay lines are employed in an optical switch to obtain enough time in order not to overload a potential congested downstream switch and henceforth avoid contention. This paper describes a novel analytical model to compare the performance of two different forwarding methods in optical burst switches, one which employs wavelength converters in middle switches and one that forces bursts to have the same wavelength throughout their path. One of the main features of the proposed model is the use of results from queuing systems with impatient customers to capture the effects of the impatience of the messages passing through delay lines in a switch. The validity of the model for both forwarding methods is demonstrated by comparing analytical results with those obtained from simulation experiments.

Advances in semiconductor technology, has enabled designers to put complex, massively parallel multiprocessor systems on a single chip. Network on chip (NoC) that supports high degree of reusability and scalablity, is a new paradigm for designing core based System-on-Chip. NoCs provide efficient communication services to IPs: communication services with guarantees on throughput and latency (GS) and communication services with no guarantees on them (BE). However, the run-time management of communication in NoC, especially congestion control mechanism is a challenging task. This paper considers a congestion control scenario which models flow control as a utility-based optimization problem. Since BE traffic is prone to congestion, we assume that GS traffic requirements are being preserved at the desired level and regulate BE source rates with the solution of the optimization problem. We propose an iterative algorithm to solve the optimization problem based on Newton's method. The proposed algorithm can be implemented by a centralized controller with low computation and communication overhead.

Interconnect networks employing wormhole-switching play a critical role in shared memory multiprocessor systems-on-chip (MPSoC) designs, multicomputer systems and system area networks. Virtual channels greatly improve the performance of wormhole-switched networks because they reduce blocking by acting as "bypass" lanes for non-blocked messages. Capturing the effects of virtual channel multiplexing has always been a crucial issue for any analytical model proposed for wormhole-switched networks. Dally has developed a model to investigate the behaviour of this multiplexing which have been widely employed in the subsequent analytical models of most routing algorithms suggested in the literature. It is indispensable to modify Daily's model in order to evaluate the performance of channel multiplexing in more general networks where restrictions such as timing constraints of input arrivals and finite buffer size of queues are common. In this paper we consider timing constraints of input arrivals to investigate the virtual channel multiplexing problem inherent in most current networks. The analysis that we propose is completely general and therefore can be used with any interconnect networks employing virtual channels. The validity of the proposed equations has been verified through simulation experiments under different working conditions

A major issue in modelling the performance merits of interconnection network is dealing with virtual channels. Some analytical models chose not to deal with this issue at all i.e. one virtual channel per physical channel. More sophisticated models, however, relayed on a method proposed by Dally to capture the effect of arranging the physical channel into many virtual channels. In this study, we investigate the accuracy of Dally's method and propose an alternative approach to deal with virtual channels in analytical performance modelling. The new method is validated via simulation experiments and results reveal its accuracy under different traffic conditions

Massively parallel computing systems are being built with hundreds or thousands of components such as nodes, links, memories, and connectors. The failure of a component in such systems will not only reduce the computational power but also alter the network's topology. The software-based fault-tolerant routing algorithm is a popular routing to achieve fault-tolerance capability in networks. This algorithm is initially proposed only for two dimensional networks (Suh et al., 2000). Since, higher dimensional networks have been widely employed in many contemporary massively parallel systems; this paper proposes an approach to extend this routing scheme to these indispensable higher dimensional networks. Deadlock and livelock freedom and the performance of presented algorithm, have been investigated for networks with different dimensionality and various fault regions. Furthermore, performance results have been presented through simulation experiments

Adding virtual channels to wormhole-routed networks greatly improves performance because they reduce blocking by acting as "bypass" lanes for non-blocked messages. Although several analytical models have been proposed in the literature for k-ary n-cubes with deterministic routing, most of them have not included the effects of virtual channel multiplexing on network performance. This paper proposes a new and simple analytical model to compute message latency in k-ary n-cubes with an arbitrary number of virtual channels. Results from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions. The proposed model is then used to investigate the relative performance merits of two different organisations of virtual channels.

Several recent studies have revealed that deadlocks occur very infrequently in the network, especially when enough routing freedom is provided. Routing algorithms based on deadlock avoidance reserve some virtual channels or routing options to specifically deal with deadlocks, and as a result they are not utilized most of the time. Routing algorithms based on deadlock recovery allow messages to use all available virtual channels to cross the network, and efficiently handle infrequently occurred deadlocks. This paper describes a new analytical model of a true fully adaptive routing (TFAR) algorithm with software-based deadlock recovery in k-ary n-cubes. Results obtained through simulation experiments confirm that the model predicts message latency with a good degree of accuracy under different working conditions.