Routing problems derived from silicon-interposer and etc. are often formulated as a set-pair routing problem where the combination of pin-pairs to be connected is flexible. In this routing problem, a length matching routing pattern is often required due to the requirement of the signal propagation delays be the same. We propose a fast length matching routing method for the set-pair routing problem. The existing algorithm generates a good length matching routing pattern in practical time. However, due to the limited searching range, there are length matching routing patterns that cannot find due to the limited searching range of the algorithm. Also, it needs heavy iterative steps to improve a solution, and the computation time is practical but not fast. In the set-pair routing, although pin-pairs to be connected is flexible, it is expected that combinations of pin-pairs which realize length matching are restricted. In our method, such a combination of pin-pairs is selected in advance, then routing is performed to realize the connection of the selected pin-pairs. Heavy iterative steps are not used for both the selection and the routing, then a routing pattern is generated in a short time. In the experiments, we confirm that the quality of routing patterns generated by our method is almost equivalent to the existing algorithm. Furthermore, our method finds length matching routing patterns that the existing algorithm cannot find. The computation time is about 360 times faster than the existing algorithm.

Connecting a large number of servers with high bandwidth links is one of the most crucial and challenging tasks that the Data Center Network (DCN) must fulfill. DCN faces a lot of difficulties like the effective exploitation of DC components that, if highlighted, can aid in constructing high performance, scalable, reliable, and cost-effective DCN. In this paper, we investigate the server-centric structure. We observe that current DCs use servers that mostly come with dual ports. Effective exploitation of the ports of interest for building the topology structure can help in realizing the potentialities of reducing expensive topology. Our new network topology, named “Parallel Cubes” (PCube), is a duplicate defined structure that utilizes the ports in the servers and mini-switches to form a highly effective, scalable, and efficient network structure. P-Cube provides high performance in network latency and throughput and fault tolerance. Additionally, P-Cube is highly scalable to encompass hundreds of thousands of servers with a low stable diameter and high bisection width. We design a routing algorithm for P-Cube network that utilizes the P-Cube structure to strike a balance among the numerous links in the network. Finally, numerical results are provided to show that our proposed topology is a promising structure as it outperforms other topologies and it is superior to Fat-tree, BCube and DCell by approximately 24%, 16%, 8% respectively in terms of network throughput and latency. Moreover, P-Cube extremely outperforms Fat-tree, and BCube structures in terms of total cost, complexity of cabling and power consumption.

Skip Graph is a promising distributed data structure for large scale systems and known for its capability of range queries. Although several methods of routing range queries in Skip Graph have been proposed, they have inefficiencies such as a long path length or a large number of messages. In this paper, we propose a novel routing method for range queries named Split-Forward Broadcasting (SFB). SFB introduces a divide-and-conquer approach, enabling nodes to make full use of their routing tables to forward a range query. It brings about a shorter average path length than existing methods, as well as a smaller number of messages by avoiding duplicate transmission. We clarify the characteristics and effectiveness of SFB through both analytical and experimental comparisons. The results show that SFB can reduce the average path length roughly 30% or more compared with a state-of-the-art method.

Recently proposed irregular networks can reduce the latency for both on-chip and off-chip systems with a large number of computing nodes and thus can improve the performance of parallel applications. However, these networks usually suffer from deadlocks in routing packets when using a naive minimal path routing algorithm. To solve this problem, we focus attention on a lately proposed theory that generalizes the turn model to maintain the network performance with deadlock-freedom. The theorems remain a challenge of applying themselves to arbitrary topologies including fully irregular networks. In this paper, we advance the theorems to completely general ones. Moreover, we provide a feasible implementation of a deadlock-free routing method based on our advanced theorem. Experimental results show that the routing method based on our proposed theorem can improve the network throughput by up to 138 % compared to a conventional deterministic minimal routing method. Moreover, when utilized as the escape path in Duato's protocol, it can improve the throughput by up to 26.3 % compared with the conventional up*/down* routing.

We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.

In this paper, we propose an IEEE 802.15.10-based layer 2 routing (L2R) method with a load balancing algorithm; the proposal considers fairness in terms of the cumulative number of sending packets at each terminal to resolve the packet concentration problem for the IEEE 802.15.4-based low-power consumption wireless smart utility network (Wi-SUN) systems. The proposal uses the accumulated sending times of each terminal as a weight in calculating each path quality metric (PQM) to decide multi-hopping routes with load balancing in the network. Computer simulation of the mesh network with 256 terminals shows that the proposed routing method can improve the maximum sending ratio (MSR), defined as the ratio of the maximum sending times to the average number of sending times in the network, by 56% with no degradation of the end-to-end communication success ratio (E2E-SR). The proposed algorithm is also experimentally evaluated by using actual Wi-SUN modules. The proposed routing method also improves the MSR by 84% with 70 terminals. Computer simulations and experiments prove the effectiveness of the proposed method in terms of load balancing.

Cooperative caching is a key technique to reduce rapid growing video-on-demand's traffic by aggregating multiple cache storages. Existing strategies periodically calculate a sub-optimal allocation of the content caches in the network. Although such technique could reduce the generated traffic between servers, it comes with the cost of a large computational overhead. This overhead will be the cause of preventing these caches from following the rapid change in the access pattern. In this paper, we propose a light-weight scheme for cooperative caching by grouping contents and servers with color tags. In our proposal, we associate servers and caches through a color tag, with the aim to increase the effective cache capacity by storing different contents among servers. In addition to the color tags, we propose a novel hybrid caching scheme that divides its storage area into colored LFU (Least Frequently Used) and no-color LRU (Least Recently Used) areas. The colored LFU area stores color-matching contents to increase cache hit rate and no-color LRU area follows rapid changes in access patterns by storing popular contents regardless of their tags. On the top of the proposed architecture, we also present a new routing algorithm that takes benefit of the color tags information to reduce the traffic by fetching cached contents from the nearest server. Evaluation results, using a backbone network topology, showed that our color-tag based caching scheme could achieve a performance close to the sub-optimal one obtained with a genetic algorithm calculation, with only a few seconds of computational overhead. Furthermore, the proposed hybrid caching could limit the degradation of hit rate from 13.9% in conventional non-colored LFU, to only 2.3%, which proves the capability of our scheme to follow rapid insertions of new popular contents. Finally, the color-based routing scheme could reduce the traffic by up to 31.9% when compared with the shortest-path routing.

Recent Network on Chip (NoC) design must take the thermal issue into consideration due to its great impact on the network performance and reliability, especially for 3D NoC. In this work, we design a virtual channel based fully adaptive routing algorithm for the runtime 3D NoC thermal-aware management. To improve the network throughput and latency, we use two virtual channels for each horizontal direction and design a routing function which can not only avoid deadlock and livelock, but also ensure high adaptivity and routability in the throttled network. For path selection, we design a strategy that takes priority to the distance, but also considers path diversity and traffic state. For throttling information collection, instead of transmitting the topology information of the whole network, we use a 12 bits register to reserve the router state for one hop away, which saves the hardware cost largely and decreases the network latency. In the experiments, we test our proposed routing algorithm in different states with different sizes, and the proposed algorithm shows better network latency and throughput with low power compared with traditional algorithms.

Self-Aligned Quadruple Patterning (SAQP) is an important manufacturing technique for sub 14nm technology node. Although various routing algorithms for SAQP have been proposed, it is not easy to find a dense SAQP compliant routing pattern efficiently. Even though a grid for SAQP compliant routing pattern was proposed, it is not easy to find a valid routing pattern on the grid. The routing pattern of SAQP on the grid consists of three types of routing. Among them, third type has turn prohibition constraint on the grid. Typical routing algorithms often fail to find a valid routing for third type. In this paper, a simple directed grid-graph for third type is proposed. Valid SAQP compliant two dimensional routing patterns are found effectively by utilizing the proposed directed grid-graph. Experiments show that SAQP compliant routing patterns are found efficiently by our proposed method.

The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).

In the routing design of interposer and etc., the combination of a pin pair to be connected by wire is often flexible, and the reductions of the total wire length and the length difference are pursued to keep the circuit performance. Even though the total wire length can be minimized by finding a minimum cost maximum flow in set pair routing problems, the length difference is often large, and the reduction of it is not easy. In this paper, an algorithm that reduces the length difference while keeping the total wire length small is proposed. In the proposed algorithm, an initial routing first obtained by a minimum cost maximum flow. Then it is modified to reduce the maximum length while keeping the minimum total wire length, and a connection of the minimum length is detoured to reduce the length difference. The effectiveness of the proposed algorithm is confirmed by experiments.

Three dimensional integration using Through-Silicon Vias (TSVs) offers short inter-layer interconnects and higher packing density. In order to take advantage of these attributes, a novel hybrid 3D NoC-Bus architecture is proposed in the paper. For vertical link, a Fake Token Bus architecture is elaborated, which utilizes the bandwidth efficiently by updating token synchronously. Based on this bus architecture, a methodology of hybrid 3D NoC-Bus design is introduced. The network hybridizes with the bus in vertical link and distributes long links of the full connected network into different layers, which achieves a network with a diameter of only 3 hops and limited radix. In addition, a congestion-aware routing algorithm applied to the hybrid network is proposed. The algorithm routes packets in horizontal firstly when the bus is busy, which balances the communication and reduces the possibility of congestion. Experimental results show that our network can achieve a 34.4% reduction in latency and a 43% reduction in power consumption under uniform random traffic and a 36.9% reduction in latency and a 48% reduction in power consumption under hotspot traffic over regular 3D mesh implementations on average.

One of the most important constraints in wireless sensor networks (WSN) is that their nodes, in most of the cases, are powered by batteries, which cannot be replaced or recharged easily. In these types of networks, data transmission is one of the processes that consume a lot of energy, and therefore the embedded routing algorithm should consider this issue by establishing optimal routes in order to avoid premature death and eventually having partitioned nodes network. This paper proposes a new routing algorithm for WSN called Micro-Economic Routing Algorithm (MERA), which is based on the microeconomic model of supply-demand. In such algorithm each node comprising the network fixes a cost for relay messages according to their residual battery energy; and before sending information to the base station, the node searches for the most economical route. In order to test the performance of MERA, we varied the initial conditions of the system such as the network size and the number of defined thresholds. This was done in order to measure the time span for which the first node dies and the number of information messages received by the base station. Using the NS-2 simulator, we compared the performance of MERA against the Conditional Minimum Drain Rate (CMDR) algorithm reported in the literature. An optimal threshold value for the residual battery is estimated to be close to 20%.

As process technology is scaled down, a typical system on a chip (SoC) becomes denser. In scaled process technology, process variation becomes greater and increasingly affects the SoC circuits. Moreover, the process variation strongly affects network-on-chips (NoCs) that have a synchronous network across the chip. Therefore, its network frequency is degraded. We propose a process-variation-adaptive NoC with a variation-adaptive variable-cycle router (VAVCR). The proposed VAVCR can configure its cycle latency adaptively on a processor core basis, corresponding to the process variation. It can increase the network frequency, which is limited by the process variation in a conventional router. Furthermore, we propose a variable-cycle pipeline adaptive routing (VCPAR) method with VAVCR; the proposed VCPAR can reduce packet latency and has tolerance to network congestion. The total execution time reduction of the proposed VAVCR with VCPAR is 15.7%, on average, for five task graphs.

The wireless robotic sensor network (WRSN) is a combination of a mobile robot and wireless sensor networks. In WRSN, robots perform high-level missions such as human rescue, exploration in dangerous areas, and maintenance and repair of unmanned networks in cooperation with surrounding sensor nodes. In such a network, robots should move to the accident site as soon as possible. This paper proposes a distance-aware robot routing (DAR) algorithm, which focuses on how to pick the shortest path for the mobile robot by considering characteristics different from packet routing. Simulations are performed to demonstrate the benefits of using the proposed algorithm.

Routing is still a challenging issue for wireless sensor networks (WSNs), in particular for WSNs with a non-uniform deployment of nodes. This paper introduces a Node Aggregation Degree-aware Random Routing (NADRR) algorithm for non-uniform WSNs with the help of two new concepts, namely the Local Vertical Aggregation Degree (LVAD) and Local Horizontal Aggregation Degree (LHAD). Our basic idea is to first apply the LVAD and LHAD to determine one size-proper forwarding region (rather than a fixed-size one as in uniform node deployment case) for each node participating in routing, then select the next hop node from the size-proper forwarding region in a probabilistic way, considering both the residual energy and distribution of nodes. In this way, a good adaptability to the non-uniform deployment of nodes can be guaranteed by the new routing algorithm. Extensive simulation results show that in comparison with other classical geographic position based routing algorithms, such as GPSR, TPGF and CR, the proposed NADRR algorithm can result in lower node energy consumption, better balance of node energy consumption, higher routing success rate and longer network lifetime.

Recently, the importance of data sharing structures in autonomous distributed networks has been increasing. A wireless sensor network is used for managing distributed data. This type of distributed network requires effective information exchanging methods for data sharing. To reduce the traffic of broadcasted messages, reduction of the amount of redundant information is indispensable. In order to reduce packet loss in mobile ad-hoc networks, QoS-sensitive routing algorithm have been frequently discussed. The topology of a wireless network is likely to change frequently according to the movement of mobile nodes, radio disturbance, or fading due to the continuous changes in the environment. Therefore, a packet routing algorithm should guarantee QoS by using some quality indicators of the wireless network. In this paper, a novel information exchanging algorithm developed using a hash function and a Boolean operation is proposed. This algorithm achieves efficient information exchanges by reducing the overhead of broadcasting messages, and it can guarantee QoS in a wireless network environment. It can be applied to a routing algorithm in a mobile ad-hoc network. In the proposed routing algorithm, a routing table is constructed by using the received signal strength indicator (RSSI), and the neighborhood information is periodically broadcasted depending on this table. The proposed hash-based routing entry management by using an extended MAC address can eliminate the overhead of message flooding. An analysis of the collision of hash values contributes to the determination of the length of the hash values, which is minimally required. Based on the verification of a mathematical theory, an optimum hash function for determining the length of hash values can be given. Simulations are carried out to evaluate the effectiveness of the proposed algorithm and to validate the theory in a general wireless network routing algorithm.

In order to find paths guaranteed by Quality of Service (QoS), the link state database (LSDB), containing QoS constraint information, and residing in routers, needs to be well managed. However, there is a trade-off between the exact reflection of the current link status and the update cost to calculate and maintain this data. In order to perfectly reflect the current link state, each router immediately notifies its neighbors whenever link state information changes. However, this may degrade the performance of the router. On the other hand, if current link state information is not updated routinely, route setup requests may be rejected because of the discrepancy between the current link state information and the previously updated link state information in the LSDB. Therefore, we need link state update (LSU) algorithms making it possible to appropriately update the LSDB. In addition, to facilitate implementation, they also should have low-complexity and must be adaptive under the variation of network conditions. In this paper, we propose an enhanced simple-adaptive (ESA) LSU algorithm, to reduce the generation of LSU messages while maintaining simplicity and adaptivity. The performance of this algorithm is compared with five existing algorithms by rigorous simulations. The comparision shows that the ESU algorithm can adapt to changes in network conditions and its performance is superior to existing LSU algorithms.

With the rapid adoption of mobile devices and location based services (LBS), applications provide with nearby information like recommending sightseeing resort are becoming more and more popular. In the mean time, traffic congestion in cities led to the development of mobile public transportation systems. In such applications, mobile devices need to communicate with servers via wireless communications and servers should process queries from tons of devices. However, because users can not neglect the payment for the wireless communications and server capacities are limited, decreasing the communications made between central servers and devices and reducing the burden on servers are quite demanding. Therefore, in this paper, we propose a cost-effective intelligent public transportation system, ACE-INPUTS, which utilizes a mobile device to retrieve the bus routes to reach a destination from the current location at the lowest wireless communication cost. To accomplish this task, ACE-INPUTS maintains a small amount of information on bus stops and bus routes in a mobile device and runs a heuristic routing algorithm based on such information. Only when a user asks more accurate route information or calls for a "leave later query", ACE-INPUTS entrusts the task to a server into which real-time traffic and bus location information is being collected. By separating the roles into mobile devices and servers, ACE-INPUTS is able to provide bus routes at the lowest wireless communication cost and reduces burden on servers. Experimental results have revealed that ACE-INPUTS is effective and scalable in most experimental settings.

One approach to accommodating IP traffic on a wavelength division multiplexing (WDM) network is to construct a logical topology, establishing a set of lightpaths between nodes. The lightpaths carry IP traffic but do not require any electronic packet processing at intermediate nodes, thereby reducing the load on those nodes. When the IP and WDM networks have independent routing functions, however, the lightpaths in the WDM network may not be fully utilized by the IP router. It is therefore necessary to integrate the two routing mechanisms in order to utilize resources efficiently and adapt to changes in traffic. In this paper, we propose an integrated routing mechanism for IP over WDM networks. The key idea is to first prepare a set of virtual-links representing the lightpaths that can be established by the WDM network, then calculate the minimum cost route on an IP network including those links. Our simulation results show that when traffic patterns do not change, the throughput of our method is almost the same as that of a logical topology optimally designed for a given traffic demand. When traffic patterns change, the throughput of our method is about 50% higher than that of the logical topology.