The EDD connection admission control scheme has been proposed for supporting real-time communication in packet-switched networks. In the scheme, when a connection establishment request occurs, the worst-case link delay in each link along the connection is calculated to determine whether the request can be accepted or not. In order to calculate the worst-case link delay, we must perform a check called the point schedulability check for each of some discrete time instants (checkpoints). Therefore when there are many checkpoints, the worst-case link delay calculation is time-consuming. We have proposed a high-speed calculation method. The method finds some checkpoints for which the point schedulability check need not be performed and removes such unnecessary checkpoints in advance before a connection establishment request occurs, and the check is performed for each of the remaining checkpoints after the request occurs. However, the method is not so effective under the situation that the maximum packet length in networks is large, because the method can find few unnecessary checkpoints under the situation. This paper proposes a new high-speed calculation method. We relax the condition which determines whether or not the point schedulability check need not be performed for each checkpoint in our previous method and derive a new condition for finding unnecessary checkpoints. Using the proposed method based on the new condition, we can increase the number of unnecessary checkpoints compared to our previous method. Numerical examples which are obtained by extensive simulation show that the proposed method can attain as much as about 50 times speedup.

In order to improve TCP performance, the use of a PEP (Performance Enhancing Proxy) has been proposed. The PEP operates on a router along a TCP connection. When a data packet arrives at the PEP, it forwards the packet to the destination host, transmits the corresponding ACK (premature ACK) to the source host on behalf of the destination host, and stores a copy of the packet in a local buffer (PEP buffer) in case the packet needs to be retransmitted. In this paper, in accordance with a strategy that keeps the number of prematurely acknowledged packets in the PEP buffer below a fixed threshold (watermark) value, we investigate the relation between the watermark value and the average throughput. Extensive simulations show that the results can be roughly classified into two cases. In the first case, the average throughput becomes larger for larger watermark values and becomes a constant value when the watermark value is over a certain value. In the second case, although the average throughput becomes larger for lager watermark value in the same way, it decreases when the watermark value is over a certain value. We also show that the latter (former) case can occur more easily as the propagation delay in the input side network of the PEP becomes smaller (larger) and the propagation delay in the output side network of the PEP becomes larger (smaller), and also show that the latter (former) case can occur more easily as the transmission speed in the input side network becomes larger (smaller) and the transmission speed in the output side network becomes smaller (larger) while the PEP buffer capacity becomes smaller (larger).

Light trail architecture is attracting attention as a new optical wavelength-division multiplexing network architecture that can be built with currently available devices and can achieve bandwidth allocation with granularity finer than a wavelength. Because a light trail is a shared medium, we need a medium access control (MAC) protocol to prevent collisions. Although MAC protocols using token passing can prevent collisions, the bandwidths of links that are located upstream of the token holding node are kept idle. We first propose a dynamic light trail splitting method for increasing throughput of a light trail by using such idle bandwidths. Our method splits a trail into upstream and downstream trails at the token holding node, and independent data transmission on the two trails are permitted. As a result, we expect that the split trail architecture will achieve higher throughput than the original non-split trail architecture. The degree of performance improvement with the split trail architecture depends on how appropriately we determine the upstream and downstream token holding times of every transmission node. Thus, we formulate a problem in which we optimize the token holding times to accommodate requested traffic volume as a linear programming problem. We then derive the throughput of the split trail architecture by solving the problem using the NUOPT solver and investigate the degree of improvement over the original architecture. In addition, we evaluate the end-to-end delay of the split trail architecture by simulation. According to numerical examples, the split trail architecture achieves 1) almost the same throughput as the original one for the worst-case traffic pattern where every transmission node sends data to the terminating node of the trail only, 2) about 1.6 times higher throughput for a uniform traffic pattern where every node pair requests the same traffic volume and an extremely unbalanced traffic pattern where only a few node pairs request huge traffic volume, 3) about 1.9 time higher throughput for the split trail architecture's good-case traffic pattern where every transmission node sends data to its adjacent downstream node only, and 4) the end-to-end delay enough to satisfy any application's QoS requirement according to ITU-T Recommendation Y.1541.

The locally exhaustive testing of multiple output combinational circuits is the test which provides exhaustive test patterns for each set of inputs on which each output depends. First, this paper presents a sufficient condition under which a minimum test set (MLTS) for the locally exhaustive testing has 2w test patterns, where w is the maximum number of inputs on which any output depends. Next, we clarify that any CUT with up to four outputs satisfies the condition, independently of w and n, where n is the number of inputs of the CUT. Finally, we clarify that any CUT with five outputs also satisfies the condition for 1w2 or n2wn.

Any minimum test set (MLTS) for locally exhaustive testing of multiple output combinational circuits (CUTs) has at least 2w test patterns, where w is the maximum number of inputs on which any output depends. In the previous researches, it is clarified that every CUT with up to four outputs has an MLTS with 2w elements. On the other hand, it can be easily shown that every CUT with more than five outputs does not have such an MLTS. It has not been however known whether every CUT with five outputs has such an MLTS or not. In this paper, it is clarified that every CUT with five outputs has such an MLTS. First, some terminologies are introduced as preliminaries. Second, features of 5(w1) dependence matrices of CUTs with five outputs and (w1) inputs are discussed. Third, an equivalence relation between dependence matrices of two CUTs is introduced. The relation means that if it holds and one of the CUTs has an MLTS with 2w elements, then the other CUT also has such an MLTS. Based on the features described above, a theorem is established that there exists a 5w dependence matrix which is equivalent to each of the above 5(w1) matrices. Finally, it is proved by the use of the theorem that every CUT with five outputs has an MLTS with 2 w elements.

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

This paper proposes a new supply current test method for detecting floating gate defects in CMOS ICs. In the method, unusual increase of the supply current caused by defects is promoted by superposing an AC component on the DC power supply. Feasibility of the test is examined by some experiments on four DUTs with an intentionally caused defect. The results showed that our method could detect clearly all the defects, one of which may be detected by neither any functional logic test nor any conventional supply current test.

The shuffle-like network (SL-Net) is known as a logical topology for WDM-based multihop packet-switched networks. Even if we fix the logical topology to an SL-Net, we can still reposition nodes in the SL-Net by re-tuning wavelengths of transmitters and/or receivers. In conventional node placement algorithms, routes between nodes are assumed to be given. In this paper, we propose two heuristic node placement algorithms for the SL-Net to decrease the average end-to-end packet transmission delay under a given traffic matrix in the case that routes are design variables. The principal idea is to prevent too many traffic flows from overlapping on any link. To attain the idea, in one of the algorithms, a node is selected one by one in a decreasing order of the sums of sending and receiving traffic requirements in nodes, and its placement and routes between the node and all the nodes already placed are simultaneously decided so that the maximum of the amounts of traffic on links at the moment is minimum. In the other algorithm, a node is selected in the same way, and first it is placed so that the average distance between the node and all the nodes already placed is as large as possible, and then routes between the node and all the nodes already placed are decided so that the maximum of the amounts of traffic on links at the moment is minimum. Numerical results for four typical traffic matrices show that either of the proposed algorithms has better performance than conventional algorithms for each matrix, and show that the proposed algorithms, which are based on a jointed optimization approach of node placement and routing, are superior to algorithms which execute node placement and routing as two isolated phases.

A method to detect open node defects that cannot be detected by the conventional IDDQ test method has previously been proposed employing a sinusoidal wave superposed on the DC supply voltage. The present paper proposes a strategy to improve the detectability of the test method by means of frequency analysis of the supply current. In this strategy, defects are detected by determining whether secondary harmonics of the sinusoidal wave exist in the supply current. The effectiveness of the method is confirmed by experiments on two CMOS NAND gate packages (SSIs).

To improve TCP throughput even if the maximum receiving window size is small, a TCP performance enhancing proxy (PEP) using a UDP-like packet sending policy with error control has been proposed. The PEP operates on a router along a TCP connection. When the PEP receives a data packet from the source host, it transmits the packet to the destination host, copies the packet into the local buffer (PEP buffer) in case the packets need to be transmitted and sends a premature ACK acknowledging receipt of the packet to the source host. In the PEP, the number of prematurely acknowledged packets in the PEP buffer is limited to a fixed threshold (watermark) value to avoid network congestion. Although the watermark value should be adjusted to changes in the network conditions, watermark adjusting algorithms have not been investigated. In this paper, we propose a watermark adjusting algorithm the goal of which is to maximize the throughput of each connection as much as possible without excessively suppressing the throughputs of the other connections. In our proposed algorithm, a newly established connection uses the initial watermark value of zero to avoid drastic network congestion and increases the value as long as its throughput increases. In addition, when a new connection is established, every already-established connection halves its watermark value to allow the newly established connection to use some portion of the bandwidth and increases again as long as its throughput increases. We compare the proposed algorithm (CW method) with other methods: the FW method that uses a fixed large watermark value and the NP method that does not use the PEP. Numerical results with respect to throughput and fairness showed that the CW method is generally superior to the other two methods.

The programming circuit of SRAM-based FPGAs consists of two shift registers, a control circuit and a configuration memory (SRAM) cell array. Because the configuration memory cell array can be easily tested by conventional test methods for RAMs, we focus on testing for the shift registers. We first derive test procedures for the shift registers, which can be done by using only the faculties of the programming circuit, without using additional hardware. Next, we show the validness of the test procedures. Finally, we show an application of the test procedures to test Xilinx XC4025.

This paper considers a test set for a multibit shifter which can execute arbitrary bit length shifting/rotating operations. The multibit shifter consists of several stages of sub-shifters, each of which can shift/rotate its inputs by an arbitrary number of bits less than or equal to a predetermined constant. Outputs of one sub-shifter are shifted/rotated in the next sub-shifted. All of the sub-shifters have the same structure, and are constructed with multiplexers. Every sub-shirter is separately tested. All of the multiplexers in each sub-shifter are tested in parallel and exhaustively. A minimum test set for every sub-shifter can be obtained by the use of an algorithm which generates a Boolean 2pq matrix M such that any 2pp submatrix of M includes all bit patterns of length p, where p and q (pq) are the numbers of input lines in a multiplexer and those in a sub-shifter, respectively. A complete test set for the multibit shifter can be easily obtained as the union of minimum test sets for all sub-shifters.