Unlike the traditional networking infrastructure, the software defined network (SDN) separates the network control function from the data transmission function. SDN of a large geographical area requires multiple controllers rather than a single centralized one, and controller provisioning has a significant impact on the network performance. In this paper we propose a novel load balancing scheme with switch migration to effectively solve the dynamic controller provisioning problem (DCPP) for SDN. The proposed scheme employs a meta-heuristic approach based on harmony search and K-means clustering of the switches. The proposed scheme is evaluated by computer simulation in terms of load balancing accuracy, and it turns out to be superior to the existing harmony search algorithm.

Differential Evolution (DE) algorithm is one of the popular evolutionary algorithms that is designed to find a global optimum on multi-dimensional continuous problems. In this paper, we propose a new variant of DE algorithm by combining a self-adaptive DE algorithm called dynNP-DE with Elite Opposi tion-Based Learning (EOBL) scheme. Since dynNP-DE algorithm uses a small number of population size in the later of the search process, the population diversity becomes low, and therefore premature convergence may occur. We have therefore extended an OBL scheme to dynNP-DE algorithm to overcome this shortcoming and improve the optimization performance. By combining EOBL scheme to dynNP-DE algorithm, the population diversity can be supplemented because not only the information of individuals but also their opposition information can be utilized. We measured the optimization performance of the proposed algorithm on CEC 2005 benchmark problems and breast cancer detection, which is a research field that has recently attracted a lot of attention. It was verified that the proposed algorithm could find better solutions than five state-of-the-art DE algorithms.

Software‐defined networking (SDN) decouples the control plane and data forwarding plane to overcome the limitations of traditional networking infrastructure. Among several communication protocols employed for SDN, OpenFlow is most widely used for the communication between the controller and switch. In this paper two packet scheduling schemes, FCFS‐Pushout (FCFS‐PO) and FCFS‐Pushout‐Priority (FCFS‐PO‐P), are proposed to effectively handle the overload issue of multiple‐switch SDN targeting the edge computing environment. Analytical models on their operations are developed, and extensive experiment based on a testbed is carried out to evaluate the schemes. They reveal that both of them are better than the typical FCFS‐Block (FCFS‐BL) scheduling algorithm in terms of packet wait time. Furthermore, FCFS‐PO‐P is found to be more effective than FCFS‐PO in the edge computing environment.

Constrained Application Protocol (CoAP) was developed to support the communication between resource constrained nodes via low-power links. As an Internet protocol, CoAP needs congestion control primarily to stabilize the networking operation. In this paper we propose a new round trip time based adaptive congestion control scheme, which improves CoAP by utilizing the retransmission count information in estimating the retransmission timeout. An experiment is conducted based on Californium CoAP framework and real devices. It shows that the proposed scheme significantly improves CoAP in terms of throughput and rate of successful transaction.

Heterogeneous network (HetNet) deploying a number of small cells in a macro cell improves network capacity as well as data rate at hot spots and cell edges. The mobility management with HetNet is challenging due to its complexity. In this paper an efficient handover scheme is proposed considering the asymmetric characteristics of macro and pico cells in HetNet. The proposed scheme ranks the candidate cells for handover using a multi-criteria decision making (MCDM) algorithm and the information on the movement of user equipment (UE). When the received power is too low, if the UE can detect a suitable target eNB of good quality, handover is triggered promptly even before the time-to-trigger window expires to avoid radio link failure. Even though the received signal from the serving cell is high enough for communication, handover is also triggered for the UE when the downlink SINR is below a threshold. The performance of the proposed scheme is evaluated by computer simulation and compared with two well-known handover algorithms with respect to the number of handovers per second, goodput per UE, and packet loss rate. The simulation with LTE-Sim reveals that the proposed scheme significantly enhances the goodput while reducing packet loss and unnecessary handover.

Wireless sensor networks (WSN) is widely used for gathering data in the distributed fashion. In WSN, each node has limited energy resource, and thus the lifetime of the network is one of the most critical issues. In this paper we propose an energy efficient and optimal randomized clustering protocol for self-organizing WSNs. The proposed scheme decides optimal number of clusters by employing a new approach for setting threshold value, including the probability of optimum number of cluster-heads and residual energy of the nodes. We also introduce a new approach maximize the network lifetime by tree construction in each cluster. Computer simulation shows that the proposed scheme effectively reduces and balances the energy consumption among the nodes, and thus significantly extends the network lifetime compared to the existing schemes.

Data exist in various persistent-storage formats, and Hadoop distributed file system (HDFS) has been recognized to be effective for distributed storage and processing. Recently, the research of Hybrid NAND flash-based solid state drives (SSD) is rapidly expanding into the storage areas including Hybrid ReRAM/MLC NAND SSD. Most existing researches of Hybrid SSD are based on a single storage, while the management of multiple nodes like HDFS is still immature. In this paper a new efficient cold data eviction scheme is proposed which is based on the state of node congestion of Hybrid SSD for HDFS. It computer simulation reveals that the proposed scheme significantly reduces average recovery and execution time in comparison to the existing replication schemes.

The Solid State Drive (SSD) is now becoming a main stream in storage systems. It is widely deployed as cache for hard disk drive (HDD) to speed up the execution of data intensive applications. In this paper we propose a novel block replacement algorithm for flash-based disk cache, named Block Replacement based on Popularity(BRP). Using the frequency and recency of block access, it calculates the block popularity to select the block which will be evicted from SSD. This avoids cache pollution and keeps popular blocks in SSD cache, leading to high hit ratio. Meanwhile, the proposed scheme reduces block replacements, and thus incurs less write operations to SSD. As a result, BRP enhances the performance of storage and the lifetime of SSD. Computer simulation demonstrates that the proposed scheme consistently outperforms five existing cache replacement algorithms with two different kinds of traces.

With IPTV, channel zapping time is one of the significant problems. It occurs when the user wants to change the channel but needs to wait until the target channel is available. Various schemes reducing the time have been suggested, which download the candidate channels of the future use in advance. In this paper we propose a new method which further reduces the channel zapping time by pre-downloading the candidate channels during the time latency between two successive push operations of the buttons of remote controller made by the user. Computer simulation verifies its effectiveness in various operational conditions. More importantly, it can be employed together with other scheme of reducing channel zapping time without any additional overhead.

Wireless sensor networks are widely used for gathering data in the distributed fashion. Since the network consists of low-cost nodes of limited battery power, it is a challenging task to design an energy efficient routing scheme. In this paper we propose a novel clustering algorithm based on spanning tree of bounded degree in each cluster for energy efficient WSNs. The proposed scheme selects the cluster-head considering the residual energy of each node, and partitions each cluster for constructing efficient routing paths to the base station. Computer simulation shows that the proposed scheme effectively reduces and balances the energy consumption among the nodes, and thus significantly extends the network lifetime compared to the existing schemes such as LEACH, PEGASIS, and TREEPSI.

Nowadays, wireless sensor networks (WSNs) are widely used, and various routing schemes have been developed for them. Its lifetime is limited as each node of WSN is battery-powered, and unnecessary data transmissions of the nodes shorten the lifetime of entire network. Gossiping protocol has been recognized as one of the most effective routing schemes employed for WSN. In this paper we propose a new scheme called energy efficient gossiping (E-Gossip) protocol to maximize the lifetime of WSN by properly adjusting the gossip probability and controlling the operation of each sensor node based on the remaining energy. Redundant data transmission is also reduced. The proposed scheme is simulated with NS-2, and the simulation results show that it substantially reduces and balances the energy consumption compared to AODV and the existing gossiping protocol. As a result, the proposed scheme is able to effectively prolong the lifetime of WSN.

Health monitoring system is one of most important and practical applications of wireless sensor network (WSN). Even though various health monitoring devices based on WSN are used, they are still quite limited in the sense of mobility and accuracy. In this paper a new wearable health monitoring system is proposed, which consists of bio-shirt and vital sensor node. Here the accuracy of the measurement of electrocardiogram signal is enhanced, and the sensor node is optimized for the use in WSN. Also, a multi-hop routing protocol is employed to effectively deal with rapid changes in the link between a fast moving target node and static relay nodes. The experiments for various types of movements of an individual wearing the proposed bio-shirt reveal that the proposed system significantly improves the performance of health monitoring based on WSN compared to the existing device.

Recently, various applications have emerged which utilize wireless sensor network (WSN) consisting of low cost and low power sensors in smart spaces. Here a great deal of research has been carried out on transmitting video over WSN. WSN has limited resources in terms of bandwidth and data processing capability, while video requires bulk data to be transmitted. In this paper we propose a two-stage Quality of Service (QoS) guaranteeing scheme for video transmission over WSN, called the Multi-Channel Multi-Path (MCMP) scheme. It selects the best paths from the source camera to the gateway based on hop-count, aggregated path energy, BER, and end-to-end delay. A failure recovery scheme is also provided to cope with link failure. Computer simulation reveals that the proposed scheme significantly outperforms the existing scheme in terms of channel utilization and delay.

A context-aware system handling time-critical applications must satisfy explicit end-to-end time constraints which are highly dependent on the correlation between the dynamically changing contexts. To effectively deal with the timing constraints of context-aware systems, a methodology must be developed specifying the causal relationship between the contexts and timing aspect. To date, this issue has not yet been adequately addressed. In this paper, we propose a new modeling methodology which effectively represents the timing variation of contexts by extending interval timed colored Petri net. We also propose a technique determining if a service is able to satisfy the timing requirement. The effectiveness of the proposed approach is demonstrated using a collision avoidance service provided to moving vehicles.

Context-awareness service is one of the key features in ubiquitous computing system. In heterogeneous pervasive computing environment, effective context modeling and reasoning are important to enable the collaboration and distributed reasoning among the agents. The effectiveness of the previous approaches for distributed reasoning significantly degrades when a large number of agents are involved. In order to solve this problem we propose a layered context model efficiently facilitating distributed reasoning. We also propose similarity-based context reasoning which takes the correlation of context models into account. The performance of the proposed scheme is verified by computer simulation, which shows that the trust of reasoning outcome is greatly enhanced.

Multithreading is an efficient technique commonly used to maximize the performance of CPU. One of the most important challenges in multithreading is thread pool management. It needs to retain a proper number of threads in the pool, which minimizes the response time and maximizes the resource utilization. To achieve this goal, this paper proposes a novel trendy exponential moving average (TEMA) scheme for predicting the number of threads. Also, a prediction-based thread pool management scheme is proposed which adjusts the idle timeout period and thread pool size to effectively adapt the system to the changing environment. The experiment results show the effectiveness of the proposed approach in terms of response time and CPU usage, compared with the existing prediction-based scheme and Sun watermark.

Today, mobile IPTV provides various multimedia services. Therefore, extensive researches on providing service continuity in the mobile IPTV environment are being conducted. Here reducing the user waiting time under the restriction of limited bandwidth is an important design issue in the video on-demand multicast service. In this paper we propose a scheme reducing the waiting time of a user wanting to start to view the video not from the beginning but from any point. The proposed scheme allows significantly reduced waiting time compared to the existing scheme for varying request rates and number of channels, as verified by computer simulation.

Multi-agent system in the ubiquitous computing environment can provide customized services to the users by effectively utilizing the distributed resources. The existing dynamic load balancing approach invokes the migration of agents even for temporal imbalance of the loads. In this paper we propose a prediction-based dynamic load balancing scheme which can effectively avoid unnecessary agent migration. An experiment reveals that the proposed approach significantly reduces the service response time compared with the existing scheme. It enables the agent system to quickly adapt to the environment change through effective load balancing.

Recently, WiBro has been developed to efficiently support broadcasting via wireless network. MBS (multicast broadcast service) based on WiBro has numerous applications including DMB. Since the current MBS implementation uses only common channel which is managed by scheduling, it cannot effectively support many users requesting the service at the same time. This paper proposes a new counting scheme with which the channel mode can be properly switched between common channel and dedicated channel by considering the number of users and their mobility. It thus allows efficient use of limited radio resource in WiBro supporting the MBS. The simulation results with NS-2 show that it is significantly more efficient than the existing scheme when many users request the same broadcasting service channel.

The demand on IPTV services has been greatly increasing in the area of wireless communication. For supporting a large number of users with limited resources, the development of effective transmission technology is inevitable. In this paper we propose an efficient batching scheme enhancing the performance of VoD system over wireless IPTV. The proposed approach capitalizes the notion of segment interval time to maximize the channel utilization. Computer simulation shows that the proposed approach allows seamless service with a small number of channels as one or two for practical operational conditions, while the existing batching scheme requires a much larger number of channels. Moreover, the start-up latency is reduced.

Today, VoD is an important technology for many applications, and a number of periodic broadcasting schemes have been proposed to support a large number of receivers. However, these schemes are not suitable to the environment where wired and wireless devices coexist. With the existing schemes dealing with heterogeneous receivers, the service latency of low-end clients is reduced by sacrificing that of high-end clients. In this paper we propose a novel scheme reducing the service latency of high-end clients as well by partitioning the first segment and transmitting them through sub-channels added according to the network condition. Computer simulation shows that the service latency is significantly decreased compared to the existing scheme.

Energy efficiency is a critical issue for sensor network. In this paper we propose an energy efficient context adaptive MAC protocol for wireless sensor networks. The existing approaches improve energy efficiency by controlling the duty cycle of transmission period. The proposed protocol achieves that by letting each node stay in the sleep mode if the number of packets in the buffer is smaller than the threshold, while the threshold value is decided according to the distance of the node to the sink node. The variable threshold for each switch node, however, may cause increased latency. This problem is solved by immediately transmitting the packets of high priority context data. Computer simulation using OMNeT++ reveals that the proposed protocol significantly reduces the energy consumption compared with the existing S-MAC and T-MAC protocol.

RFID Tag detection/recognition is one of the most critical issues for successful deployment of RFID systems in diverse applications. The main factors influencing tag detection by RFID reader antenna include tag position, relative position of reader, read field length, etc. In this paper, we analyze the characteristics of tag detection for a carton box object on a wooden pallet by an experimental approach based on tag signal strength, and we propose a method for predicting detection related directly to the strength of tag signal using an intelligent machine learning technique called support vector machine (SVM). The use of the proposed method is able to save time and cost by quick prediction of tag detection. Extensive experiments showed that the proposed approach can predict tag recognition for a carton box object with an accuracy at 95% for various reader heights and read field lengths. The proposed approach is effective for determining the best tag detection influencing factor conditioned on the target object with the help of detectability prediction.

The demand on high speed Internet access has been rapidly growing due to various multimedia applications requiring high speed data transmission. WiMAX based on IEEE 802.16 standard is one of the most effective technologies among the existing solutions. With the current multicasting technique, the base station receives duplicated multicast IP datagrams via GRE Tunnel, which significantly degrades the network performance. In this paper we propose a new L2 layer multicasting approach which can avoid the duplicated packet problem by utilizing the message exchanged between the base station and subscriber station. Computer simulation with NS-2 reveals that the proposed approach allows much higher throughput and lower packet delay compared to the existing approach.

Programming and composing deterministic distributed real-time systems is becoming increasingly important, yet remains difficult and error-prone. An innovative approach to such systems is the general-form timeliness-guaranteed design paradigm, which is the basis for the time-triggered message-triggered object (TMO) programming and system specification scheme. This approach was originally developed for Windows programming environments and operating systems. This paper describes the techniques needed to make TMO support the Linux operating system and reports the resulting performance characteristics.

A number of different kinds of applications in large and complex ubiquitous computing systems need fault tolerance. Here failure detection is one of the key elements for efficient fault management. There exist various fault monitoring and detection algorithms employing a timeout-based mechanism. However, they are occasionally inaccurate in unstable or overloaded system. The goal of the proposed scheme is to enhance the accuracy of fault detection by properly handling the monitoring interval. This is achieved by dynamically adjusting the window of the past elapsed times included in the prediction of the monitoring interval. Computer simulation reveals that the proposed algorithm allows much more elastic and accurate prediction of monitoring interval than the existing algorithms regardless of load condition of the system.

Agent based development is a new technology that has been recently used in many domains. However, the development of an agent-based system can be difficult and time-consuming for inexperienced developers. To address this problem, in this paper, we propose a pattern based agent development and support tool. This approach facilitates rapid agent development and addresses common design problem. The agent patterns are classified according to function. We apply this approach for agent development, based on a travel assistant scenario.

Replicating data is a promising way of improving the dependability of large distributed systems. The hybrid data replication protocol combines concepts of the tree quorum protocol and grid protocol. We present an analytical evaluation of read/write availability for the generalized hybrid data replication protocol, which extends the arrangement of nodes into a more general form to improve write availability. The average number of nodes accessed for read/write operations is also analyzed under the assumption that nodes might fail. Equations are derived based on node availability p, and numerical examples are shown. We use computer simulations to estimate the throughput for read/write operations.

Abstract Even though tree‐based reliable multicast protocols are known to be most scalable for one‐to‐many sessions, there is still an open question as to whether these protocols are also scalable for many‐to‐many sessions. In this paper, we analyze and compare two promising multicast protocols—the receiver‐initiated protocol with NACK suppression and the tree‐based protocol—using a new spatial loss model. The proposed model considers the correlation of packet loss events for more realistic analysis unlike the previous work. The analysis results show that the tree‐based protocol achieves much higher throughput than the receiver‐initiated protocol for a many‐to‐many session as the number of participants in the session becomes larger. Copyright © 2004 John Wiley & Sons, Ltd.

Congestion control is a key task in reliable multicast along with error control. However, existing tree-based congestion control schemes such as MTCP[11] and TRAMCC[3] are designed for one-to-many reliable multicast and have some drawbacks when they are used for many-to-many reliable multicast. We propose an efficient congestion control mechanism, TMRCC, for tree-based many-to-many reliable multicast protocols. The proposed scheme is based on the congestion windowing mechanism and a rate controller is used in addition. The feedback for error recovery is exploited for congestion control as well to minimize the overhead at the receivers. The ACK timer and the NACK timers are set dynamically reflecting the network condition changes. The rate regulation algorithm in the proposed scheme is designed to help the flows sharing the same link to achieve the fair share quickly. The performance of the proposed scheme is evaluated using ns-2 [2]. The simulation results show that the proposed scheme outperforms TRAMCC in terms of intra-session fairness and shows good level of responsiveness, TCP-friendliness, and scalability.

Due to its topological generality and flexibility, the k-ary n-cube architecture has been actively researched for various applications. However, the processor allocation problem has not been adequately addressed for the k-ary n-cube architecture, even though it has been studied extensively for hypercubes and meshes. The earlier k-ary n-cube allocation schemes based on conventional slice partitioning suffer from internal fragmentation of processors. In contrast, algorithms based on job-based partitioning alleviate the fragmentation problem but require higher time complexity. This paper proposes a new allocation scheme based on isomorphic partitioning, where the processor space is partitioned into higher dimensional isomorphic subcubes. The proposed scheme minimizes the fragmentation problem and is general in the sense that any size request can be supported and the host architecture need not be isomorphic. Extensive simulation study reveals that the proposed scheme significantly outperforms earlier schemes in terms of mean response time for practical size k-ary and n-cube architectures. The simulation results also show that reduction of external fragmentation is more substantial than internal fragmentation with the proposed scheme.

Group communication is a useful mechanism guaranteeing consistency among replicated objects. The existing approaches do not allow transparent plug-in of group communication protocols into CORBA. They either require modification of CORBA or OS, or provide no room for incorporating group communication transport protocols into CORBA. We thus propose a generic group communication framework that allows transparent plug-in of various group communication protocols with no modification of existing CORBA. We extend the open communications interface (OCI) to support interoperability, reusability of existing group communication, and independency on ORB and OS. We also define the group communication inter-ORB protocol (GCIOP) as a group communication instantiation of the general inter-ORB protocol (GIOP) that encapsulates underlying group communication protocols. The proposed scheme can be exploited for fault-tolerant CORBA (FT CORBA).

Abstract Although establishing correct and efficient routes is an important design issue in mobile ad hoc networks (MANETs), a more challenging goal is to provide energy efficient routes because mobile nodes' operation time is the most critical limiting factor. This article surveys and classifies the energy‐aware routing protocols proposed for MANETs. They minimize either theactive communication energyrequired to transmit or receive packets or theinactive energyconsumed when a mobile node stays idle but listens to the wireless medium for any possible communication requests from other nodes.Transmission power control approachandload distribution approachbelong to the former category, andsleep/power‐down mode approachbelongs to the latter category. While it is not clear whether any particular algorithm or a class of algorithms is the best for all scenarios, each protocol has definite advantages/disadvantages and is well suited for certain situations. The purpose of this paper is to facilitate the research efforts in combining the existing solutions to offer a more energy efficient routing mechanism. Copyright © 2003 John Wiley & Sons, Ltd.

Tree-based reliable multicast protocols are known to be most scalable for one-to-many sessions. However, there is still an open question whether these protocols are also scalable for many-to-many sessions. We categorize existing tree-based protocols into four classes according to the feedback/retransmission policies employed, and analyze and compare them on the basis of a proposed spatial loss model. This model considers the correlation of packet loss events for more realistic analysis, unlike previous work. The analysis reveals that, in many-to-many cases, a tree-based protocol with unicast NACK, unicast retransmission and periodic polling is most scalable with respect to throughput for practical session sizes. The protocol is also simple to implement.

We present the design, implementation, and performance analysis of group-aided multicast (GAM), a scalable many-to-many reliable multicast transport protocol. GAM achieves high quality ACK trees while keeping the tree maintenance overhead reasonably low in the presence of dynamic group membership and route changes. It is supported by a group configuration mechanism organizing the members in a multicast session into multiple small groups and a tree configuration mechanism maintaining logical trees according to the underlying multicast routing trees. With the two mechanisms, GAM builds a two-layer hierarchy of multi-level logical trees from which high-quality per-source ACK trees are generated. Simulation results show that the GAM protocol is more scalable than a NACK suppression protocol in terms of processing time for request/repair messages and recovery latency.

This paper reevaluates the multicast protocols for MANETs in terms of energy efficiency and proposes a new robust multicast protocol, called two-tree multicast (TTM). Multicast protocols can be broadly categorized into two types, tree-based multicast and mesh-based multicast, based on the network structure along which multicast packets are delivered to multiple receivers. Mesh-based protocols are more robust to mobility and result in high packet delivery ratio. On the other hand, multicast trees are more energy efficient than multicast meshes. This is because mesh-based protocols depend on broadcast flooding within the mesh and therefore, mobile nodes in the mesh must receive all multicast packets during the multicast communication. The proposed TTM uses two trees, a primary and an alternative backup tree, to improve energy efficiency compared to the mesh-based protocols and to offer a better energy balance and packet delivery ratio than the free-based protocols. Performance evaluation study shows that the proposed TTM saves energy consumption by a factor of 1.9/spl sim/4.0 compared to the mesh-based multicast. In terms of combined performance metric, energy per delivered packet, TTM shows up to 80% and 40% improved performance than the mesh-based multicast and the conventional shared tree multicast, respectively.

Mapping virtual process topology to physical processor topology is one of the most important issues in parallel computing. The mapping problem for switch-based cluster systems of irregular topology is very complicated due to the connection irregularity and routing complexity. This paper proposes two mapping schemes for irregular cluster systems, which try to map the nearest neighbors in the process topology to physically adjacent processors. In addition, an application-oriented performance metric, weighted cardinality, is introduced to represent the quality of mapping. A simulation study shows that, for a virtual topology of a 16/spl times/16 mesh, the proposed mapping schemes result in better mapping quality and about 15/spl sim/20% shorter communication latency compared to random mapping. The proposed algorithms should also be beneficial when they are applied to metacomputing and cluster of cluster systems, where the communication costs are an order of magnitude different depending on the relative position of the processor nodes.

In mobile wireless network efficient location management for tracking and finding mobile users is a critical issue. The traffic for location update can be excessive, especially at the base stations that are near to the location area (LA) boundaries. In this paper we propose a new location update scheme which can significantly reduce the signaling traffic for location update. It is based on the virtual layer approach employing SubMSCs. The virtual layer is laid upon the original layer of LA's such that the mobile terminals moving around the boundary cells of adjacent LA's become to move within a virtual LA. As a result, the location update traffic is substantially reduced compared to overlapping scheme which is the most recent and efficient location update scheme.

Object replication is a technique to enhance fault tolerance and high availability. Group communication is a useful mechanism guaranteeing the consistency among replicated objects. We propose a generic group communication framework that allows transparent plug-in of various group communication protocols with no modification of existing CORBA. For this, we extend the Open Communications Interface (OCI) to support interoperability, reusability of existing group communication, and independency on ORB and OS. The proposed scheme is composed of group membership, group IOR, and group multicast. Experimental results show that group object invocation using the proposed scheme performs substantially better than group object invocations using IIOP as the number of members in a group increases.

While various checkpointing schemes have been widely used to reduce the recovery time when a fault occurs, the problem of evaluating the optimal checkpoint interval that maximizes the availability of the system has been a critical research issue for decades. The evaluation can be done by developing analytical models with restrict assumptions. However, the analytical model has reached its limitations as the checkpointing schemes become complicated. This paper proposes to use stochastic Petri net model for the evaluation and shows the effectiveness of the approach using case studies. The paper develops stochastic Petri net models and shows how to obtain the optimal checkpoint intervals for systems employing two widely used checkpointing schemes: Checkpoint with Rollback Recovery scheme for uniprocessor systems and Primary Site Approach for multiprocessor systems.

This paper proposes a Barrier Tree for Meshes (BTM) to minimize the barrier synchronization latency for two-dimensional (2D) meshes. The proposed BTM scheme has two distinguishing features. First, the synchronization tree is 4-ary. The synchronization latency of the BTM scheme is asymptotically /spl theta/(log/sub 4/ n), while that of the fastest scheme reported in the literature is bounded between /spl Omega/(log/sub 3/ n) and /spl theta/(n/sup 1/2/), where n is the number of member nodes. Second, nonmember nodes are neither involved in the construction of a BTM nor actively participate in the synchronization operations, which avoids interference among different process groups during synchronization. This not only results in low setup overhead, but also reduces the synchronization latency. The low setup overhead is particularly effective for the dynamic process model provided in MPI-2. Extensive simulation study shows that, for up to 64/spl times/64 meshes, the BTM scheme results in about 40/spl sim/70 percent shorter synchronization latency and is more scalable than conventional schemes.

VLSI-based processor arrays have been widely used for computation intensive applications such as matrix and graph algorithms. Algorithm-based fault tolerance designs employing various encoding/decoding schemes have been proposed for such systems to effectively tolerate operation time fault. In this paper, we propose an efficient algorithm-based fault tolerance design using the weighted data-check relationship, where the checks are obtained from the weighted data. The relationship is systematically defined as a new (n, k, N/sub w/) Hamming checksum code, where n is the size of the code word, k is the number of information elements in the code word, and N/sub w/ is the number of weights employed, respectively. The proposed design with various weights is evaluated in terms of time and hardware overhead as well as overflow probability and round-off error. Two different schemes employing the (n, k, 2) and (n, k, 3) Hamming checksum code are illustrated using important matrix computations. Comparison with other schemes reveals that the (n, k, 3) Hamming checksum scheme is very efficient, while the hardware overhead is small.

A method for testing multi-protocol implementation under test (IUT) with a single test suite has been proposed in the literature. It tests a multi-protocol IUT in an integrated way compared to the conventional method, where a single-layer test method and a single-layer embedded test method are applied, respectively, to the upper layer protocol and to lower layer protocols. However, it did not consider how to generate the test cases automatically but proposed only an approach for the test method. This paper proposes an algorithm called multi-protocol test method (MPTM) for automatic test case generation based on that approach. With the MPTM, a multi-protocol IUT consisting of two protocol layers is modeled as two finite state machines (FSMs), and the relationships between the their transitions are defined as a set of transition relationships, pre-execution and carried-by. The proposed algorithm is implemented and applied to a simplified TCP/IP and B-ISDN signaling/SSCOP (service specific connection-oriented protocol). The MPTM is able to test the multi-protocol IUT even though the interfaces between the protocol layers are not exposed. It also allows the same test coverage as conventional test methods, but with a much smaller number of test cases and operations.

In multicasting multimedia data, effectively adapting to heterogeneous receivers is very difficult. In this paper, we propose a new scheme called the "active traffic control mechanism for layered multimedia multicasting" (ATLM) in an active network environment. The proposed scheme controls traffic at each router using the traffic condition of immediate children nodes. Also, the traffic adjustment is much finer than existing multicast protocols of single-layer granularity. Computer simulation reveals that the proposed scheme significantly improves the amount of delivered traffic and the end-to-end delay by as much as 10%, as compared to layer-wise adjustment. Moreover, it does not require one to maintain multiple sessions for transferring multi-layer data but only one session, and thus reduces the overheads on session management and network bandwidth.

Group Communication System (GCS) is an important building block for reliable, fault-tolerant distributed applications. Due to highly variable and unpredictable latency in WANs, GCS needs to cope with frequent membership changes. It results in diminishing the scalability of GCS. In this paper we propose a new scheme that improves the scalability of group membership service for WANs by exploiting dedicated membership servers configured into multiple layers and reaching global agreement on the view through layered servers. It improves the scalability of a process group of N member processes from O(N/sup 2/) to O(N/sup 3/) with three layers, where N is the number of processes in the group. Computer simulation verifies that the proposed scheme requires much smaller number of message exchanges for reaching an agreement on a next view and does that much quicker. In addition, the proposed scheme prevents applications from being blocked until reaching the final view agreement if the applications permit temporary inconsistency.

Multicomputer systems achieve high performance by utilizing a number of computing nodes. Recently, by achieving significant reductions in communication delay, the three-dimensional (3D) torus has emerged as a new candidate interconnection topology for message-passing multicomputer systems. In this paper, we propose an efficient processor allocation scheme-scan search scheme-for the 3D torus based on a first-fit approach. The scan search scheme minimizes the average allocation time for an incoming task by effectively manipulating the 3D information on a torus as 2D information using a data structure called the CST (Coverage Status Table). Comprehensive computer simulation reveals that the allocation time of the scan search scheme is always smaller than that of the earlier scheme based on a best-fit approach. The difference gets larger as the input load increases, and it is as much a factor of 3 for high load. To investigate the performance of the proposed scheme in different scheduling environments, we also consider a non-FCFS scheduling policy along with the typical FCFS policy. The allocation time complexity of the scan search scheme is O(LW/sup 2/H/sup 2/). This is significantly smaller than that of the existing scheme which is O(L/sup 4/W/sup 4/H/sup 4/). Here, L, W, and H represent the length, width, and height of 3D torus, respectively.

ATM is an important technology for implementing the B-ISDN, while TCP has become a core for computer networking. In this paper we study the performances of typical TCP traffic control schemes assuming the parallel ATOM switch, which is an efficient time division ATM switch. Computer simulation shows that early packet discard (EPD) scheme outperforms tail dropping and partial packet discard (PPD) scheme in terms of throughput and delay, regardless of the size of the buffer and packet.

Among the various systems developed for parallel and distributed computing, networks of workstations (NOWs) based on the Message Passing Interface (MPI) have been recognized as an efficient platform. In this paper, we implement and compare two important message logging protocols, pessimistic and optimistic, for a NOW employing MPI. An experiment reveals that the total execution time is not significantly affected by the number of failures, while the performance of the optimistic protocol is more influenced by the number of failures than the pessimistic protocol is. Also, the former is more efficient than the latter for a reasonable number of failure points.

Multistage interconnection networks (MINs) have been widely used for parallel computer systems, and also recognized as an efficient switching fabric for digital communication. In this paper, we propose a new switching mechanism for MINs called unit step buffering (USB) which significantly improves the network performance. Here each cell is allowed to move only one buffer entry position using short network cycle. The proposed USB scheme is compared to the traditional scheme by analytical modeling and computer simulation. They reveal that throughput and delay are improved about 60%-80% for practical size MINs with reasonable traffic in the asynchronous transfer mode (ATM) switching environment. Improvement on parallel computer systems with larger size packets is more significant at about 100%. More importantly, the scheme does not require any additional hardware or operational overhead.

The task scheduling policy and the processor allocation scheme affect the system performance significantly. In this paper, we propose an efficient processor allocation scheme for 3D mesh interconnection network with a simple FIFO scheduling policy. Complexity analysis shows that the allocation and deallocation of the scheme are O(LWH/sup 2/) and O(LH), respectively, which are better than earlier schemes. Comprehensive computer simulation shows that the average allocation time of the proposed scheme is improved up to about 85% compared to the best earlier 3D approach.

Efficient allocation of processors to incoming tasks in parallel computer systems is very important for achieving the desired high performance. It requires recognizing the free available processors with minimum overhead. In this paper, we present an efficient task allocation scheme for 2D mesh architectures. By employing a new approach for searching the mesh, our scheme can find the available submesh without scanning the entire mesh, unlike earlier designs. Comprehensive computer simulation reveals that the average allocation time and waiting delay are much smaller than earlier schemes of comparable performances, irrespective of the size of meshes and distribution of the shape of the incoming tasks.

Dictionary machine is an important VLSI system performing high speed data archival operations. In this paper, we present a design which can efficiently implement dictionary machines in VLSI processor arrays. In order to effectively process the operations of dictionary machine, hexagonal mesh is selected as the host topology in which two different networks for update and query operation are embedded. The proposed design is simple to implement as well as allows high throughput.

Efficient allocation of proper size submeshes to incoming tasks in two-dimensional (2D) mesh-connected processors is very important for achieving the desired high performance. It also needs to guarantee the recognition of the free submeshes with minimum overhead. In this paper we present an efficient task allocation scheme for 2D meshes. By employing a new approach for searching the array, our scheme can find the available submesh without the scanning of the entire 2D array unlike earlier designs. As a result, our scheme can significantly reduce the task allocation time. Comprehensive computer simulation reveals that the average allocation time and waiting delay are much smaller than earlier schemes irrespective of the size of meshes. The hardware overhead is comparable to other schemes.

Distributed self-diagnosis approach proposed for multiprocessor systems is also effective for integrated circuit wafers containing a number of identical circuits. Here the testing of each node is based on the majority voting on the test results from itself and neighboring nodes. In this paper, we identify that the unanimous voting (UV) approach always outperforms the individual voting (IV) approach, irrespective of the number of voting cells and fault rate. Based on the UV approach, the optimal number of tests is obtained. We also introduce an adaptive voting scheme by which the test overhead of the traditional voting schemes can be significantly reduced.>

In this brief contribution a new algorithm-based concurrent error detection scheme employing the checksum approach is proposed for FFT networks. Our design allows high error coverage with low false alarm rate by applying the linear weight factors to the checksums. Due to the simplicity, the hardware overhead is relatively small and errors can be quickly detected. The design is also shown to be easily expanded for multidimensional FFT networks.>

In packet switching using multistage interconnection networks (MIN's), it is generally assumed that the packet movements successively propagate from the last stage to the first stage in one network cycle. Ding and Bhuyan (1994), however, have shown that the network performance can be significantly improved if the packet movements are confined within each pair of adjacent stages using small clock cycles. In this short note, we present a model for estimating the performance of multibuffered MIN's employing the approach. Using the model, the relative effectiveness of the approach is identified compared to the traditional design.>

Currently large digital systems consist of a control unit and many processing units. Much work has been done in partitioning large processing units (PUs) into multiple PUs. However, there is still a large control unit that must control each of these PUs. This results in long lines from the control unit to the PUs and hence a long clock period. We present a method to break the control unit into many smaller control units (local CUs) so that each of these local CUs can sit on the same chip as the PU that it controls. These local CUs are partitioned in such a fashion that there is a pipelined sequence of execution between them.>

A scheme is proposed by which nonlinear graph problems can be efficiently solved using processor arrays even in the presence of multiple faults. The fault tolerance capability is achieved using the majority voting approach, and virtually no extra hardware overhead is necessary by maximizing the utilization of the processing elements (PEs). In addition to this, the proposed scheme also allows a significant reduction in the size of the array such that a [3N/5]/spl times/N processor array is enough for processing an N/spl times/N input data for shortest path problem (SPP). Computation time of the proposed design is bound to 9N-2 for SPP, while it is 5N-4 for non-fault tolerant designs.>

Interleaved memory schemes have been used to increase the memory bandwidth. In this paper, we propose a new interleaved memory scheme called PSIM (Periodically Shifted Interleaved Memory), which allows high memory bandwidths at the sacrifice of very small memory space. It is a stride dependent scheme where the processor utilization is 100% for most strides using a power-of-two number of memory modules. We show, analytically and then by simulation, that the efficiency of PSIM is consistently higher than not only earlier stride dependent schemes but also stride independent schemes for both short and long vector accesses

Multistage interconnection networks (MIN's) have a number of applications in the areas of computer and communication. While several analytical models have been proposed for the performance evaluation of MIN's, they are either not very accurate or too complex to be generalized. The authors propose a new model for evaluating multibuffered MIN's with 2/spl times/2 switching elements. It effectively and realistically models the correlation of packet movements between two adjacent stages as well as subsequent network cycles. As a result, the proposed model is very accurate for any size and traffic conditions of MIN's. It is also simple and can be easily generalized.>

Call packing has been recognized as a routing scheme that significantly reduces the blocking probability of connection requests in a circuit-switched Clos multistage interconnection network. In this paper, for the first time, we develop general analytical models for the point-to-point blocking probability of the call-packing scheme applied to Clos networks. By introducing a new parameter called the degree of call packing, the models can correctly estimate the blocking probability of both call-packing and random routing schemes. The models are verified by computer simulation for various size networks and traffic conditions.>

Fault tolerance has been one of the major issues for the VLSI based FFT networks. In this paper, two efficient approaches for concurrent error location and correction of FFT networks are proposed. Using our approach, a faulty component can be located at an additional try followed by log/sub 2/m comparisons of m corrupted outputs. An error can also be corrected, once it is detected, at a small modification of basic module with an additional try. Moreover, our approaches are general in the sense that they can be implemented with any concurrent error detection scheme employing a checksum approach for FFT networks.>

A methodology for the register allocation problem in high-level synthesis based on the scanline sweep algorithm is introduced. The algorithm is computationally efficient and easy to understand and to implement, and it guarantees an optimal number of registers for nonpipelined designs. In this method, a set of registers is available from which the best one can be chosen by the allocator for variable binding. The method has proved to be useful in constructive allocation strategies in which the operators and variables are simultaneously considered for binding for interconnect cost optimization. The allocation program is written in C and it is integrated into the DAGAR high-level synthesis system.>

A comprehensive model for evaluating crossbar networks in which the memory bandwidth and processor acceptance probability are primary measures considered is presented. This analytical model includes all important network control policies, such as the bus arbitration and rejected request handling policies, as well as the home memory concept. Computer simulation validates the correctness of the model. It is confirmed that the home memory and dynamic bus arbitration policy improve the network performance.>

The authors present a model which can accurately evaluate the performance of single-buffered and multibuffered MINs (multistage interconnection networks) with 2*2 switching elements (SESs). Earlier models were inaccurate because of the simplicity, or hard to expand for larger SEs or buffer sizes due to their complexity. The proposed model for single-buffered MINs has only three states, including the blocked state, while it is very accurate by realistically modeling the transactions between buffers in adjacent stages and network cycles. The model was expanded for multibuffered MIN, and it was found to be still very accurate. Comparisons with simulation and the YLL model (see H.Y. Yoon et al., 1990) revealed that the proposed models are consistently much more accurate irrespective of the size of the network, buffer, and traffic condition. The proposed model can be easily expanded for any other structures and operation conditions of MINs.>

Among a number of techniques for efficiently testing VLSI circuits, the BIST using compression technique is recognized as reliable and cost effective. While compact testing using signature analysis allows an efficient test, some faulty responses cannot be detected due to aliasing. This paper shows how the aliasing probability can be significantly reduced by a factor of 2/sup (k+1)/ when k intermediate signatures are checked. The proposed scheme can also quickly detect the fault using fewer hardware resources.>

The authors present a novel modular fault-tolerant binary tree architecture which is shown to be more effective in overcoming both operational faults and fabrication defects than earlier approaches. Furthermore, for practical size trees of up to eight levels, it is shown how the proposed design can be efficiently load out in VLSI with very short interconnections. Thus, the design is suitable for monolithic implementation of a large binary tree architectures. For board level multichip designs, a hybrid scheme, combining the new design with the SOFT approach, is presented. It shows better reliability than either design alone. >

A novel reconfiguration scheme is proposed to achieve a highly successful reconfiguration rate for two-dimensional processor arrays with fixed interconnection resources. The authors use a flexible spare allocation scheme and thereby achieve a spare allocation pattern which maximizes the utilization of the given interconnection resources. However, some spare allocations may not result in the successful reconfiguration of a logic array due to the lack of necessary resources. The rationale behind this approach is that the probability of the occurrence of allocation patterns causing such resource conflicts is pretty low. Furthermore, the rare resource conflicts may be resolved by the proposed resolution techniques. By utilizing the given interconnection resources much more efficiently, the proposed scheme achieves a higher reconfiguration rate than a previous design of similar approach. The complexity of the reconfiguration algorithm is O(N/sup 2/).>

Although a number of defect-tolerance schemes for two-dimensional VLSI/WSI (wafer scale integration) processor arrays have been proposed in the literature, none is efficient enough always to guarantee a restructured array that utilizes all the good processors on the wafer while using only a limited number of interconnection channels. The authors present a restructuring scheme that can achieve this (no matter how severely clustered the faults) with a maximum channel width of three, provided the total number of faults in the array are within some stated limits. For practical size arrays, this limit is large enough so as not be be restrictive in practice. Moreover, the scheme also works extremely well, in a probabilistic sense, for a larger number of faults, when the failed processors are severely clustered.>

The authors present an efficient scheme for the layout of large binary-tree architectures by embedding the complete binary tree in a two-dimensional array of processing elements. Their scheme utilizes virtually 100% of the processing elements in the array as computing elements; it also shows substantial improvements in propagation delay and maximum edge length over H-tree layouts. They shown that their layouts readily lend themselves to fault-tolerant designs for overcoming fabrication defects in large-area and wafer-scale implementations of binary-tree architectures.>

An efficient scheme is presented for embedding a complete binary tree architecture in a two-dimensional array of processing elements. The scheme utilizes almost 100% of the processing elements in the array as actual computing elements, with small and asymptotically optimal propagation delay. The maximum edge length is optimal for trees with up to six levels. The scheme is compared with other designs proposed in the literature and shown to be significantly better.>