Search

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]

Gaussian networks are degree four symmetric networks and these are designed based on the concept of Gaussian integers. The Gaussian network can be described in terms of a generator $\alpha =a+bi$ , where a$ and b$ are integers and . When $\gcd (a,b)=1$ , how to find edge disjoint Hamiltonian cycles has been shown before. In this paper for any generator $\alpha =a+bi,$ even when $\gcd (a, b)=d > 1$ , how to obtain two edge disjoint Hamiltonian cycles in these networks is described. [ABSTRACT FROM AUTHOR]

Cloud computing not only requires high-capacity data center networks to accelerate bandwidth-hungry computations, but also causes considerable power expenses to cloud providers. In recent years many advanced data center network architectures have been proposed to increase the network throughput, such as Fat-Tree [1] and BCube [2] , but little attention has been paid to the power efficiency of these network architectures. This paper makes the first comprehensive comparison study for typical data center networks with regard to their Network Power Effectiveness(NPE), which indicates the end-to-end bps per watt in data transmission and reflects the tradeoff between power consumption and network throughput. We take switches, server NICs and server CPU cores into account when evaluating the network power consumption. We measure NPE under both regular routing and power-aware routing, and investigate the impacts of topology size, traffic load, throughput threshold in power-aware routing, network power parameter as well as traffic pattern. The results show that in most cases Flattened Butterfly possesses the highest NPE among the architectures under study, and server-centric architectures usually have higher NPEs than Fat-Tree and VL2 architectures. In addition, the sleep-on-idle technique and power-aware routing can significantly improve the NPEs for all the data center architectures, especially when the traffic load is low. We believe that the results are useful for cloud providers, when they design/upgrade data center networks or employ network power management. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel analysis method for divisible load scheduling in mesh, torus and Gaussian network, a new type of interconnection network that has the same node degree as the mesh and torus, but shorter network diameter and shorter average hop distances under equal network size. The divisible scheduling in these three networks are uniformly formulated as the Maximum Finish Time Minimization (MFTM) problem. It involves minimizing the makespan of the load distribution and processing. The MTFM problem, a relaxed MFTM problem, a linear programming problem version and a heuristic algorithm are described and solved. The first three of these problems have identical solutions. The heuristic algorithm is close in performance to the optimal solution, significantly outperforms the previously described dimensional algorithm, and has much wider application range than the previously proposed phase algorithm. [ABSTRACT FROM PUBLISHER]

With the development of multiprocessor system on chips (MPSoCs), it is expected that hundreds of computing cores will be operating on a single chip in the near future. This will require high-performance on-chip networks with very low latency to provide a communication substrate for the increasing number of cores. In this paper, we consider Gaussian on-chip networks that are of significant topological advantages over traditional mesh and torus networks in terms of diameter and average hop distance. Many applications on MPSoCs need global data movement and global control to exchange data and synchronize the execution among cores, which require all-to-all broadcast communication. In this paper, we propose an all-to-all broadcast algorithm suitable for on-chip implementation on the Gaussian network topology. The algorithm utilizes controlled message flooding based on a broadcast pattern, which can be described in a formal, generic way for each node in terms of a few simple operations and can be easily built into router hardware. Furthermore, the generic broadcast pattern also ensures a balanced traffic load in all dimensions in the network so that minimum total latency for all-to-all broadcast can be achieved. The algorithm overlaps message switching time with transmission time in a pipelined fashion to further reduce the total communication latency of all-to-all broadcast. Comparison results demonstrate the topological merits of Gaussian networks and ultralow latency of the proposed all-to-all broadcast algorithm. [ABSTRACT FROM AUTHOR]

A complete family of Cayley graphs of degree four, denoted as L-networks, is considered in this paper. L-networks are 2D mesh-based topologies with wrap-around connections. L-networks constitute a graph-based model which englobe many previously proposed 2D interconnection networks. Some of them have been extensively used in the industry as the underlying topology for parallel and distributed computers of different scales. Tori, twisted and doubly twisted tori, toroidal diagonal meshes, chordal rings, and circulant graphs are, among others, members of the L-network family. Therefore, many results obtained in previous studies on these networks can be deduced from the general framework presented in this work. In addition, the network model presented in this work allows for new results on the domain of low-degree interconnection networks. Particularly, closed expressions for the graph distance properties have been derived and an optimal routing algorithm of constant complexity is provided. Since symmetry has a big impact on network performance, we have also identified which L-networks are symmetric by studying their group of automorphisms. Finally, a very simple model that predicts the performance of L-networks is also presented. Such model has been contrasted with empirical evaluation. [ABSTRACT FROM AUTHOR]

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]

Clos networks and their variations such as folded-Clos networks (fat-trees) have been widely adopted as network topologies in data center networks. Since multicast is an essential communication pattern in many cloud services, nonblocking multicast communication can ensure the high performance of such services. However, nonblocking multicast Clos networks are costly due to the large number of middle stage switches required. On the other hand, server redundancy is ubiquitous in today’s data centers to provide high availability of services. In this paper, we explore such server redundancy in data centers to reduce the cost of nonblocking multicast Clos data center networks (DCNs). To facilitate our analysis, we first consider an ideal fault-free data center with no server failure. We give an algorithm to assign active servers evenly among input stage switches in a multicast Clos DCN where each server has one or more redundant backups depending on the availability requirements of services they provide. We show that the sufficient nonblocking condition on the number of middle stage switches for a multicast Clos DCN can be significantly reduced by exploring server redundancy. Then, to complete our analysis, we consider a practical faulty data center, where one or more active servers may fail at any time. We give a strategy to re-balance the active servers among input stage switches after server failures so that the same nonblocking condition still holds. Finally, we provide a multicast routing algorithm with linear time complexity to configure multicast connections in Clos DCNs. [ABSTRACT FROM AUTHOR]

A fundamental goal of data center networking is to efficiently interconnect a large number of servers with the low equipment cost. Several server-centric network structures for data centers have been proposed. They, however, are not truly expandable and suffer a low degree of regularity and symmetry. Inspired by the commodity servers in today's data centers that come with dual port, we consider how to build expandable and cost-effective structures without expensive high-end switches and additional hardware on servers except the two NIC ports. In this paper, two such network structures, called HCN and BCN, are designed, both of which are of server degree 2. We also develop the low overhead and robust routing mechanisms for HCN and BCN. Although the server degree is only 2, HCN can be expanded very easily to encompass hundreds of thousands servers with the low diameter and high bisection width. Additionally, HCN offers a high degree of regularity, scalability, and symmetry, which conform to the modular designs of data centers. BCN is the largest known network structure for data centers with the server degree 2 and network diameter 7. Furthermore, BCN has many attractive features, including the low diameter, high bisection width, large number of node-disjoint paths for the one-to-one traffic, and good fault-tolerant ability. Mathematical analysis and comprehensive simulations show that HCN and BCN possess excellent topological properties and are viable network structures for data centers. [ABSTRACT FROM PUBLISHER]

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]

As the number of cores on a chip increases, Networks-on-Chip (NoCs) that connect many cores would face long links to reduce hop counts. The long links become bottlenecks in terms of both energy and RC delays as technology advances. To alleviate the negative impact of long links, we propose decentralized routers for NoCs. A decentralized router consists of multiple submodules that are positioned on a link, and hence the long links are segmented. Furthermore, we illustrate the design of an entire network that uses decentralized routers to obtain a good tradeoff between hop counts and wire delays per hop. Decentralized routers are effective especially in high-radix topologies, such as the flattened butterfly, and energy-delay product is reduced by greater than 60 percent. As NoCs become larger and more complex, the benefit of the decentralized routers will become more significant. [ABSTRACT FROM PUBLISHER]

A graph G=(V,E) is said to be \emph{conditional k-edge-fault pancyclic} if, after removing $k$ faulty edges from $G$ and provided that each node is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to $|V|$ inclusive. In this paper, we sketch the common properties of a class of networks called Matching Composition Networks (MCNs), such that the conditional edge-fault pancyclicity of MCNs can be determined from the derived properties. We then apply our technical theorem to show that an $m$-dimensional hyper-Petersen network is conditional $(2m-5)$-edge-fault pancyclic. \\ \noindent{\bf Keywords}: Conditional edge faults, fault-tolerant cycle embedding, matching composition networks, pancyclicity, multiprocessor systems. [ABSTRACT FROM PUBLISHER]

To improve the reliability of on-chip network based systems, we design a deadlock-free routing technique that is more resilient to component failures and guarantees a higher degree of node connectivity. The routing methodology consists of three key steps. First, we determine the maximal connected subgraph of the faulty network by checking whether the defective components happen to be the cut vertices and bridges of the network topology. A precise fault diagnosis mechanism is used to identify partial defective routers. Second, we construct an acyclic channel dependency graph that breaks all cycles and preserves connectivity of the maximal connected subgraph. This is done through the cycle-breaking and connectivity guaranteed (CBCG) algorithm. Finally, we introduce a fault-tolerant adaptive routing scheme that can be used with or without virtual channels for network congestion avoidance and high-throughput routing. The simulation results show both the effectiveness and robustness of the proposed approach. For an $8 \times 8$ 2D-Mesh with 40 percent of link damage, full connectivity and deadlock freedom are still archived without disabling any faultless router in 98.18 percent of the simulations. In a 2D-Torus, the simulation percentage is even higher (99.93 percent). The hardware overhead for supporting the introduced features is minimal. An on-line implementation of cbcg using TSMC 65nm library has only 0.966 and 1.139 percent area overhead for the $8\times8$ and $16 \times 16$ 2D-Meshes. [ABSTRACT FROM AUTHOR]