Finding widespread events in a distributed network is crucial when detecting cyber-attacks or network malfunctions. We propose a new detection scheme for widespread events based on bitmaps that can succinctly record and deliver event information between monitoring agents and a central coordinator. Our proposed scheme reduces communication overhead as well as total number of rounds, and achieves even higher accuracy, compared with the current state of the art.

Internet routers need to classify incoming packets quickly into flows in order to support features such as Internet security, virtual private networks and Quality of Service (QoS). Packet classification uses information contained in the packet header, and a predefined rule table in the routers. Packet classification of multiple fields is generally a difficult problem. Hence, researchers have proposed various algorithms. This study proposes a multi-dimensional encoding method in which parameters such as the source IP address, destination IP address, source port, destination port and protocol type are placed in a multi-dimensional space. Similar to the previously best known algorithm, i.e., bitmap intersection, multi-dimensional encoding is based on the multi-dimensional range lookup approach, in which rules are divided into several multi-dimensional collision-free rule sets. These sets are then used to form the new coding vector to replace the bit vector of the bitmap intersection algorithm. The average memory storage of this encoding is θ (LNlog N) for each dimension, where L denotes the number of collision-free rule sets, and N represents the number of rules. The multi-dimensional encoding practically requires much less memory than bitmap intersection algorithm. Additionally, the computation needed for this encoding is as simple as bitmap intersection algorithm. The low memory requirement of the proposed scheme means that it not only decreases the cost of packet classification engine, but also increases the classification performance, since memory represents the performance bottleneck in the packet classification engine implementation using a network processor.

In this paper, we show a method to locate a single stuck-at fault of a random access memory (RAM). From the fail-bitmaps of the RAM, we obtain their Walsh spectrum. For a single stuck-at fault, we show that the fault can be identified and located by using only the 0-th and 1-st coefficients of the spectrum. We also show a circuit to compute these coefficients. The computation time is O(2n), where n is the number of bits in the address of the RAM. The computation time is much shorter than one that uses a logic minimization method.

Tree-based approach has been proven to be most scalable for one-to-many reliable multicast. It efficiently combines distributed recovery with local recovery over a logical tree of the sender and receivers. It has also been known that the performance of the tree-based protocols heavily depends upon the quality of the logical tree. In this paper, we propose an end-to-end scheme to further enhance the scalability of the tree-based approach. By exchanging packet loss information observed at the end hosts, the scheme constructs and maintains a logical tree congruent with the underlying multicast routing tree even in the presence of session membership and multicast route changes. The scheme also groups the tree nodes and assigns separate multicast addresses to them in order to enable efficient multicast retransmission for reducing both delay and exposure. We compare the proposed scheme with Tree-based Multicast Transport Protocol (TMTP), a static tree-based protocol. Extensive simulations up to 300 node sessions reveal that the proposed scheme reduces implosion and exposure more than 20% and 50%, respectively. The results also indicate that the scheme is highly scalable such that the improvement gets more significant as the size of the session increases.

In this paper, we propose fast bitmap search algorithms to reduce the computational complexity of transform-based vector quantization (VQ) techniques, which achieve better quality in reconstructed images than the ordinary VQ. By removing the unlikely codewords in each step, the bitmap search method, which starts from the most significant bitmap then the successive significant ones, can save more than 90% computation of the ordinary transformed VQ. By applying to the singular value decomposition (SVD) VQ as an example, theoretical analyses and simulation results show that the proposed bitmap search methods dramatically reduce the computation and achieve invisible distortion in the reconstructed images.

In general, multimedia files are much larger than ordinary text files because they consist of multiple monomedia. In order to process large multimedia files in real time, the file system must be able to store and access files efficiently. In th UNIX s5 file system, a multimedia file may be scattered into many disk blocks over the entire disk space, and accessing a multimedia file requires a considerable amount of time for random disk head movement. This paper proposes the internal structure of a multimedia file and its inode which is modified from UNIX s5 file system's. Also, we propose a mechanism for allocating and deallocating contiguous disk blocks for large multimedia files using the bitmap tree and compares its performance with that of the UNIX s5 file system. Our results show that the proposed mechanism reduces considerably the number of disk I/Os required to allocate and deallocate contiguous disk blocks. It also reduces the total access time for large multimedia files by approximately 95% due to the contiguous allocation of disk spaces.