The problem of finding a minimum-cast multicast tree (Steiner tree) is known as NP complete. Heuristic based algorithms for this problem to achieve good performance are usually time-consuming. In this paper, we propose a new strategy called tree-caching for efficient multicast connection setup in connection-oriented networks. In this scheme, the tree topologies that have been computed are cached in a database of the source nodes. This can reduce the connection establishment time for subsequent connection requests which have some common multicast members, by an efficient reuse of cached trees without having to re-run a multicast routing algorithm for the whole group. This method can provide an efficient way to eliminate, when ever possible, the expensive tree computation algorithm that has to be performed in setting up a multicast connection. We first formulate the problem of tree-caching and then propose a tree-caching algorithm to reduce the complexity of the tree computations when a new connection is to be established. Through simulations, we find that the proposed tree-caching strategy performs very well and can significantly reduce the computation complexity for setting up multicast connections.

The development of efficient quality of service (QoS) routing algorithms in a high-speed network environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently heuristic algorithms based on Lagrange relaxation techniques have been proposed to resolve the contradiction between the time complexity and the quality of solution. In this paper, we investigate the performance of two heuristic algorithms, LR_DCLC and NR_DCLC, for the delay-constrained least-cost (DCLC) routing problem. Algorithm LR_DCLC is based on linear relaxation, while algorithm NR_DCLC, which is proposed in this paper, is based on nonlinear relaxation. A large number of simulations demonstrate that even though both algorithms have very good performance, NR_DCLC can obtain much better solutions than LR_DCLC by running Dijkstra's algorithm on average a few more times, especially in the case when the optimal solutions are hard to find.

The modern network service of finding the optimal path subject to multiple constraints on performance metrics such as delay, jitter, loss probability, etc. gives rise to the multi-constrained optimal-path (MCOP) QoS routing problem, which is NP-complete. In this paper, this problem is solved through both exact and heuristic algorithms. We propose an exact algorithm E_MCOP, which first constructs an aggregate weight and then uses a K-shortest-path algorithm to find the optimal solution. By means of E_MCOP, the performance of the heuristic algorithm H_MCOP proposed by Korkmaz et al. in a recent work is evaluated. H_MCOP only runs Dijkstra's algorithm (with slight modifications) twice, but it can find feasible paths with a success ratio very close to that of the exact algorithm. However, we notice that in certain cases its feasible solution has an unsatisfactorily high average cost deviation from the corresponding optimal solution. For this reason, we propose some modified algorithms based on H_MCOP that can significantly improve the performance by running Dijkstra's algorithm a few more times. The performance of the exact algorithm and heuristics is investigated through computer simulations on networks of various sizes.

Active Reliable Multicast (ARM) is a novel loss recovery scheme for large-scale reliable multicast that employs active routers to protect the sender and network bandwidth from unnecessary feedback and repair traffic. Active routers perform NACKs suppression, cache multicast data for local loss recovery, and use scoped retransmission to avoid exposure. Limited active resources at routers need to be optimized to achieve low loss recovery latency and/or high network throughput. In this paper, we study the cache placement strategies and caching policies for ARM. Several heuristics, namely uniform allocation, proportional allocation, max-min fair share and weighted allocation for cache allocation methods are proposed. To further improve the loss recovery performance, caching policies can be employed in conjunction with the cache allocation strategies. Several caching policies, namely complete caching, random caching and deterministic caching, are proposed. Extensive simulation experiments are conducted to evaluate and compare the performance of the proposed strategies and policies. Numerical results reveal that significant performance gains can be achieved when a proper cache placement strategy and a caching policy are used for a given available cache resource. Another interesting finding is that the contributions of the cache placement scheme and caching policy to the recovery latency performance are roughly independent. The obtained insights in this study will provide some design guidelines for optimal active resource allocation and caching polices for reliable multicast communications.

In the future asynchronous transfer mode (ATM) networks, an efficient virtual path (VP) control strategy must be applied to guarantee the network has high throughput with tolerable node processing load. The multistage VP control may be the best candidate since the tasks in this method are shared by the central node and local nodes, and it allows us to track the traffic changes while maintain a good state of the VP topology by reconfiguring it at regular or need based intervals. In this paper, we focus on the VP topology optimization problem in the multistage VP control. We first present the problem formulation in which the tradeoff between the network throughput and processing costs is considered, and then employ an algorithm based on a route-neuron Hopfield neural network (HNN) model to solve this problem. The numerical results demonstrate the HNN can converge to optimal solutions with high probability and stability while in other cases to near optimal solutions if the values of the system parameters in the route-neuron model are chosen according to some empirical formulas provided in this paper.

In this paper, a discrete-time convergence theorem for continuous-state Hopfield networks with self-interaction neurons is proposed. This theorem differs from the previous work by Wang in that the original updating rule is maintained while the network is still guaranteed to monotonically decrease to a stable state. The relationship between the parameters in a typical class of energy functions is also investigated, and consequently a "guided trial-and-error" technique is proposed to determine the parameter values. The third problem discussed in this paper is the post-processing of outputs, which turns out to be rather important even though it never attracts enough attention. The effectiveness of all the theorems and post-processing methods proposed in this paper is demonstrated by a large number of computer simulations on the assignment problem and the N-queen problem of different sizes.

In this paper, we present a new network design problem that is applicable for designing virtual paths (VP's) in an asynchronous transfer mode (ATM) network to efficiently support multicast applications, especially real-time multimedia applications. We first address several alternatives for the solution and compare their properties. Then we focus on a new solution which sets up a semi-permanent VP layout (VPL) and constructs VC trees for different multicast traffic demand patterns based on the constructed VPL. A three-phase heuristic solution is proposed for designing a good virtual-path layout for a given set of multicast traffic demand patterns. By varying the design parameters, we can obtain different VPLs which possess different tradeoffs among some important criteria, namely, the network overhead for a connection setup, routing table resources and control and management cost. Simulations are performed on randomly generated networks to demonstrate the performance and scalability of our solution. To the best of our knowledge, there is no prior known work which takes the multicast connection traffic into account for the VP layout design.

Functional and formal verification are important methodologies for complex mixed-signal design validation. However the industry is still verifying such systems by pure simulation. This process lacks on error localization and formal verifications methods. This is the existing verification gap between the analog and digital blocks within a mixed-signal system. Our approach improves the verification process by creating temporal properties named mixed-signal assertions which are described by a combination of digital assertions and analog properties. The proposed method is a new assertion-based verification flow for designing mixed-signal circuits. The effectiveness of the approach is demonstrated on a Σ/Δ-converter.

The problem of finding a path with two additive constraints, in particular finding a path that satisfies both the cost and the delay constraints, is called multi-constrained path (MCP) problem in the literature. In this paper, we explore the MCP problem based on the idea of single mixed weight --a mixed weight for each link is first obtained by combining its delay and cost, and then Dijkstra's algorithm is used to find the corresponding shortest path. Given two infeasible paths, it can be theoretically proved that a better path can possibly be found if we choose an appropriate parameter to construct the mixed weight. An approximate algorithm is thus proposed to solve the MCP problem. Theoretical analysis demonstrates that this algorithm can make a correct judgment whether there is a feasible path or not with a very high probability even in the strict case where the delay bound is between the delays of the least delay path and the least cost path, while the cost bound is between the costs of the two paths. On the other hand, the time complexity of this algorithm is very small since it only needs to execute Dijkstra's algorithm a limited number of times. The excellent performance of the proposed algorithm is verified by a large number of experiments on networks of different sizes.

In maritime networks, the communication links are characterized as high dynamics due to ship mobility and fluctuation of the sea surface. The performance of traditional transmission protocols is poor in maritime networks. Thus, some researchers have considered using Delay Tolerant Network (DTN) to improve the performance of data transmission in maritime environment. Most existing work on maritime DTNs uses simulation to evaluate the transmission performance in maritime DTNs. In this paper, we develop a theoretical model to analyze the performance of data transmission in maritime DTNs. We first construct a model to describe the ship encounter probability. Then, we use this model to analyze the data delivery ratio from ships in the seaway to the base station (BS) on the coast. Based on the data of tracing the ships navigating in a realistic seaway, we develop a simulator and validate the theoretical models. In addition, by comparing the performance of DTN transmission protocol and traditional end-to-end transmission protocol, we confirm that DTN protocol can effectively improve the performance of data transmission in maritime networks.

Multipath routing employs multiple parallel paths between the source and destination for a connection request to improve resource utilization of a network. In this paper, we present an integrated design of multipath routing with delay constraints and failure survivability in MPLS networks. By combining the failure survivability schemes into the multipath routing algorithms, path protection or restoration policies will enable the network to accommodate link failures and at the same time achieve significant improvement on network resource utilization. We propose a number of multipath routing algorithms, working-backup path selection and bandwidth allocation schemes. We evaluate the performance of the proposed schemes in terms of call blocking probability, network resource utilization and load balancing factor. Extensive simulation results validate the effectiveness of the proposed schemes. In particular, we compare these multipath schemes to the existing failure recovery schemes that mostly focus on single path routing. The results demonstrate that the proposed integrated design framework can provide effective network failure survivability, and also achieve better load balancing and/or higher network resource utilization.

A new low-voltage, all-in-one ESD (electrostatic discharging) protection circuit was designed. One such ESD protection unit is enough to protect each I/O pad against ESD stresses of all modes, i.e., from I/O to power supply and ground positively and negatively. This novel ESD circuit features adjustable trigger-voltage, i.e., 5 V to 60 V, with low turn-on threshold down to 5 V, symmetric active discharging channels in all directions, fast response time of 0.1 to 0.3 ns, and high ESD performance/area ratio of greater than 80 V per micrometer width. It was implemented in commercial BiCMOS technologies and achieved 14 kV human body model (HBM) and 15 kV air-gap IEC ESD protection levels. This compact ESD structure can not only provide adequate ESD protection, but also minimize the ESD-induced parasitic effects, which makes it a suitable ESD protection solution for mixed-signal and RF ICs in very deep sub-micron regime.