Search

In network on chips (NoCs) design, reconfiguration of NoC is a very effective option for minimizing power consumption, and Gaussian networks can provide significant advantage over the mesh networks in terms of network diameter, average hop distance and so on. In this paper, based on the special topology structure and the static connection rules within Gaussian networks, we present the reconfiguration representation for Gaussian networks and the nature of reconfigurable Gaussian networks. Furthermore, reconfigurable rules of Gaussian networks are proposed to design the constraints for automatic reconfiguration of NoC. [ABSTRACT FROM PUBLISHER]

Fairness is an important property of computer networks and systems. In a wide range of these systems such as distributed multi-hop wireless networks, multihomed networks, and cloud computing, each user may be allocated a number of system resources; this resembles a many-to-many relationship between the sets of users and resources, which raises the problem of system-wide fair resource allocation. In this paper, we assume that each user/node can be allocated a number of resources, which could be either in its neighborhood or far from it. As a key difference with previous works and through incorporating the concept of “flow”, we model near/far resources allocated to nodes. To attain fair flow control in such systems, first we model this situation by introducing a new multi-server system called multi-ring, in which a server that represents a resource, can serve only a subset of either neighboring or far nodes in the system. Then, we define a centralized optimization problem to attain weighted proportional fairness among all nodes meaning that the sum of allocated capacities from all servers to each node (while considering its flow) is fair. We evaluate fairness properties of multi-ring networks and provide conditions on system parameters under which a system can have a fair resource allocation. Moreover, we present a distributed method to attain fairness in distributed environments, and its stability/convergence is evaluated by non-linear discrete dynamical systems. We present conditions under which the system is stable, and through numerical analysis, we show how to obtain stable system parameters for large systems. The effectiveness of the presented method is studied through extensive numerical evaluation. Results show the success of our method in attaining fairness for various topologies and system parameters, and confirm our stability analysis. A number of systems with fairness issues are also studied as potential applications of our model. [ABSTRACT FROM AUTHOR]

Efficient exact schedulability tests are required both for online admission of applications to dynamic systems and as an integral part of design tools for complex distributed real-time systems. This paper addresses performance issues with exact response time analysis (RTA) for fixed priority preemptive systems. Initial values are introduced that improve the efficiency of the standard RTA algorithm 1) when exact response times are required and 2) when only exact schedulability need be determined. This paper also explores modifications to the standard RTA algorithm, including the use of a response time upper bound to determine when exact analysis is needed, incremental computation aimed at faster convergence, and checking tasks in reverse priority order to identify unschedulable tasksets early. The various initial values and algorithm implementations are compared by means of experiments on a PC recording the number of iterations required and execution time measurements on a real-time embedded microprocessor. Recommendations are provided for engineers tasked with the problem of implementing exact schedulability tests as part of online acceptance tests and spare capacity allocation algorithms or as part of offline system design tools. [ABSTRACT FROM AUTHOR]

On-chip networks (OCNs) have been proposed to solve the increasing scale and complexity of the designs in nanoscale multicore VLSI designs. The concept of irregular meshes is an important issue because lPs of different sizes may be supported by various vendors. In order to solve routing problems in irregular meshes, modified routing algorithms to detour oversized IPs (OIPs) are needed. However, directly applying fault-tolerant routing algorithms may cause two serious problems: 1) heavy traffic loads around OIPs and 2) unbalanced traffic loads in irregular meshes. In this paper, we propose an OIP Avoidance Prerouting (OAPR) algorithm to solve the aforementioned problems. The proposed OAPR can make traffic loads evenly spread on the networks and shorten the average paths of packets. Therefore, the networks using the OAPR have lower latency and higher throughput than those using faulttolerant routing algorithms. In our experiments, four different cases are simulated to demonstrate that the proposed OAPR improves 13.3 percent to 100 percent sustainable throughputs than two previous fault-tolerant routing algorithms. Moreover, the hardware overhead of the OAPR is less than 1 percent compared to the cost of a whole router. Hence, the proposed OAPR algorithm has good performance and is practical for irregular mesh-based OCNs. [ABSTRACT FROM AUTHOR]

In this paper, we propose a general framework of the iterative local solution (ILS) for computing a connected dominating set (CDS) in ad hoc wireless networks, which include mobile ad hoc networks (MANETS) and wireless sensor networks (WSNs). This approach uses an iterative application of a selected local solution. Each application of the local solution enhances the result obtained from the previous iteration, but each is based on a different node priority scheme. Then, we integrate this iterative process into the process for handling a dynamic network topology and propose two extensions: cyclic iterative local solution (CILS) and seamless iterative local solution (SILS). CILS offers a natural extension of ILS to the dynamic environment but suffers from a broken CDS and nonadaptiveness. With a novel use of a monotonically increasing sequence number for dynamic node priority, SILS offers an extension with the desirable properties of correctness, progressiveness, locality, and seamlessness. Extensive simulations are conducted under ns-2 and a custom simulator to evaluate the effectiveness of the proposed approach in both static and dynamic environments. [ABSTRACT FROM AUTHOR]

Network structure construction and global state maintenance are expensive in large-scale dynamic peer-to-peer (P2P) networks. With inherent topology independence and low state maintenance overhead, random walk is an excellent tool in such network environments. However, the current uses are limited to unguided or heuristic random walks with no guarantee on their converged node visitation probability distribution. Such a convergence guarantee is essential for strong analytical properties and high performance of many P2P applications. In this paper, we investigate an approach for random walks to converge to application- desired node visitation probability distributions while only requiring information about the direct neighbors of each peer. Our approach is guided by the Metropolis-Hastings algorithm for Monte Carlo Markov Chain sampling. Our contributions are threefold. First, we analyze the convergence time of the random walk node visitation probability distribution on common P2P network topologies. Second, we analyze the fault tolerance of our random walks in dynamic networks with potential walker losses. Third, we present the effectiveness of random walks in assisting three realistic network applications: random membership subset management, search, and load balancing. Both search and load balancing desire random walks with biased node visitation distributions to achieve application- specific goals. Our analysis, simulations, and Internet experiment demonstrate the advantage of our random walks compared with alternative topology-independent index-free approaches. [ABSTRACT FROM AUTHOR]

In this paper, we propose load distribution strategies for divisible loads for networked computing environments where computation and communication resource characteristics are unknown and/or vary with time. The principle on which our strategies are formulated is based on using probing loads to estimate the network characteristics and using them to determine the best possible load distribution. This work extends the adaptive strategies proposed in an earlier work to multilevel general networks. These networks, while being more challenging, also offer several opportunities that can be exploited to make the probing phase more efficient. We propose two strategies, one static, which caters to the presence of unknown parameters, and the other dynamic, which caters to both unknown as well as time-varying network parameters. The proposed strategies are robust, resilient, and easily adaptable to network fluctuations. The algorithms are also shown to have a tracking ability, a property that is important in dynamic environments. Examples are presented to illustrate the salient features of these strategies. [ABSTRACT FROM AUTHOR]

Alternating group graphs AGn, studied by Jwo and others, Constitute a class of Cayley graphs that possess certain desirable properties compared with other regular networks considered by researchers in parallel and distributed computing. A different form, ANn, of such graphs, proposed by Youhou and dubbed alternating group networks, has been shown to possess advantages over AGn. For example, ANn has a node degree that is smaller by a factor of about 2 while maintaining a diameter comparable to that of AGn, is maximally fault-tolerant, and shares some of the positive structural attributes of the well-known star graph. In this paper, we characterize the distance between any two nodes in ANn and present an optimal (shortest-path) routing algorithm for this class of networks. [ABSTRACT FROM AUTHOR]

This paper establishes the state of the art in both deterministic and randomized online permutation routing in the POPS network. Indeed, we show that any permutation can be routed online on a POPS(d, g) network either with O(d/g log g) deterministic slots, or, with high probability, with 5c[d/g] + o(d/g) + O(log log g) randomized slots, where constant c = exp(1 + e-1) ≈ 3.927. When d = ϴ(g), which we claim to be the ‘interesting’ case, the randomized algorithm is exponentially faster than any other algorithm in the literature, both deterministic and randomized ones. This is true in practice as well. Indeed, experiments show that it outperforms its rivals even starting from as small a network as a POPS(2, 2) and the gap grows exponentially with the size of the network. We can also show that, under proper hypothesis, no deterministic algorithm can asymptotically match its performance. [ABSTRACT FROM AUTHOR]

(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. This paper proposes a (t, k)-diagnosis algorithm for matching composition networks, which include many well-known interconnection networks such as hypercubes, crossed cubes, twisted cubes, and Möbius cubes. It is shown that matching composition networks of n dimensions are (Ω(...), n), diagnosable, where n > 5. [ABSTRACT FROM AUTHOR]

A Multiple Bus Network (MBN) connects a set of processors via a set of buses. Two important parameters of an MBN are its loading (largest number of connections on a bus) and its degree (largest number of connections to a processor). These parameters determine the cost, speed, and implementability of the MBN. The smallest degree that any useful MBN can have is 2. In this paper, we study the relationship between running time, degree, and loading of degree-2 MBNs running a fundamental class of algorithms called binary tree algorithms. (A binary tree algorithm reduces 2n inputs at the leaves of a balanced binary tree to a single result at the root of the tree.) Specifically, we establish a nontrivial Ω(n/log n) loading lower bound for any degree-2 MBN running a 2n input binary tree algorithm optimally in n steps. We show that this bound does not hold if the restriction on the degree or the running time is relaxed. That is, optimal-time, degree-3, constant loading MBNs and suboptimal-time, degree-2, constant loading MBNs exist for binary tree algorithms. We also derive a lower bound on the additional time (beyond the optimal) needed to run binary tree algorithms on a degree-2, loading-L MBN, for any L⩾ 3. [ABSTRACT FROM AUTHOR]

The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks have been explored. In this paper, we consider the diagnosability of a family of networks, called the Matching Composition Network (MCN); two components are connected by a perfect matching. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the Hypercube Qn, the Crossed cube CQn the Twisted cube TQn and the Möbius cube MQn, can all be-proven to be n, for n ≥4. In particular, we show that the diagnosability of the four- dimensional Hypercube Q4 is 4, which is not previously known. [ABSTRACT FROM AUTHOR]