In this paper, the problem of Redundant Duplicated RREQ Network-wide Flooding (RDRNF), induced by multiple sensor nodes during route discovery in event-driven wireless sensor networks, is described. In order to reduce the number of signaling messages during the route discovery phase, a novel extension, named the Localized Route Discovery Extension (LRDE), to the on-demand ad hoc routing protocol, is proposed. The LRDE reduces energy consumption during route discovery. The heuristically and temporarily selected Path Set-up Coordinator (PSC) plays the role of a route request broker that alleviates redundant route request flooding. The LRDE also sets a route path be aggregation-compatible. The PSC can effectively perform data aggregation through the routing path constructed by the LRDE. The simulation results reveal that significant energy is conserved by reducing signaling overhead and performing data aggregation when LRDE is applied to on-demand routing protocols.

In this paper, we propose a multicast protocol, called BAM (Branch Aggregation Multicast), for wireless sensor networks. The main contribution of BAM is a reduction in the radio communication load, which is a key determinant of sensor energy consumption. BAM does not use any control packets such as join/leave messages and does not manage multicast groups. BAM is highly compatible with existing wireless sensor protocols, such as routing protocols, MAC protocols, and other kinds of energy efficient protocols. BAM implementation is quite simple and BAM works on various networks even if some sensors are not BAM-capable. BAM is composed of two aggregation techniques. One is single hop aggregation (S-BAM) and the other is multiple paths aggregation (M-BAM). S-BAM aggregates radio transmission within a single hop and enables single transmission to multiple intended receivers. M-BAM aggregates multiple paths into fewer ones and limits the range of radio transmission. S-BAM is designed to reduce redundant communication at every branch while M-BAM is designed to reduce the number of branches. SM-BAM, the combination of S-BAM and M-BAM, can reduce the radio communication load thus enabling energy efficient multicast communication. We evaluate BAM in three ways, qualitative evaluation by theoretical analysis, quantitative evaluation through computer simulations, and experiments using CrossBow's MICA2. Our results show that BAM is a very energy efficient multicast protocol that well supports wireless sensor networks.

Incorporating sensor nodes with data aggregation capability to transmit less data flow in wireless sensor networks could reduce the total energy consumption. This calls for the efficient and effective data-centric routing algorithm to facilitate this advantage. In the first part of this paper, we model the data-centric routing problem by rigorous mixed integer and linear mathematical formulation, where the objective function is to minimize the total transmission cost subject to multicast tree constraints. With the advancement of sensor network technology, sensor nodes with configurable transmission radius capability could further reduce energy consumption. The second part of this paper considers the transmission radius assignment of each sensor node and the data-centric routing assignment jointly. The objective function is to minimize the total power consumption together with consideration of construction of a data aggregation tree and sensor node transmission radius assignment. The solution approach is based on Lagrangean relaxation in conjunction with the novel optimization-based heuristics. From the computational experiments, it is shown that the proposed algorithms calculate better solution than other existing heuristics with improvement ratio up to 169% and 59% with respect to fixed transmission radius and configurable transmission radius for network with 300 random generated nodes.

A fully Internet-connected business environment is subject to frequent changes. To ordinary customers, online shopping under such a dynamic environment can be frustrating. We propose a new E-commerce service called the CIGMA to assist online customers under such an environment. The CIGMA provides catalog comparison and purchase mediation services over multiple shopping sites for ordinary online customers. The service is based on up-to-date information by reflecting the frequent changes in catalog information instantaneously. It also matches the desire of online customers for fast response. This paper describes the CIGMA along with its architecture and the implementation of a working prototype.

The problem of aggregating different stochastic process into a unique one that must be characterized based on the statistical knowledge of its components is a key point in the modeling of many complex phenomena such as the merging of traffic flows at network nodes. Depending on the physical intuition on the interaction between the processes, many different aggregation policies can be devised, from averaging to taking the maximum in each time slot. We here address flows averaging and maximum since they are very common modeling options. Then we give a set of axioms defining a general aggregation operator and, based on some advanced results of functional analysis, we investigate how the decay of correlation of the original processes affect the decay of correlation (and thus the self-similar features) of the aggregated process.

The demand for intra- and interdomain routing for multilayered networks such as those using generalized multiprotocol label switching (GMPLS) is strong. One of the features that is peculiar to GMPLS networks is that because several different domains, such as those of IP, ATM, and optical fiber, are combined with each other hierarchically, various routing policies, which are sometimes independent from underlying domains and sometimes taking the underlying domains' policies into consideration, are required. For example GMPLS's lower layer LSPs like lambda LSP are expected to be established independently before the upper-layer LSPs, like IP and MPLS LSPs, are established in the underlying domains. Another requirement for the GMPLS interdomain routing is lightening the burden for selecting the interdomain route, because there are a lot of demands to interconnect many GMPLS domains. In order to satisfy these demands, we propose a path computation server (PCS) that is special for the intra/interdomain routing of GMPLS networks. As a counterpart of the proposed interdomain routing, it is now becoming popular to apply OSPF to the GMPLS interdomain routing. Therefore, we compared the proposed interdomain routing with OSPF, and show the applicability of the routing to GMPLS networks.

Packet classification is important in fulfilling the requirements of differentiated services in next generation networks. One of interesting hardware solutions proposed to solve the packet classification problem is bit vector algorithm. Different from other hardware solutions such as ternary CAM, it efficiently utilizes the memories to achieve an excellent performance in medium size policy database; however, it exhibits poor worst-case performance with a potentially large number of policies. In this paper, we proposed an improved bit-vector algorithm named Condensate Bit Vector which can be adapted to large policy databases in the backbone network. Experiments showed that our proposed algorithm drastically improves in the storage requirements and search speed as compared to the original algorithm.

Materialized views, which are derived from base relations and stored in the database, offer opportunities for significant performance gain in query evaluation by providing quick access to the pre-computed data. A materialized view can be utilized in evaluating a query if it has pre-computed result of some part of the query plan. Although many approaches to utilizing materialized views in evaluating a query have been proposed, there exist several restrictions in selecting such views. This paper proposes new ways of utilizing materialized views in answering an aggregate query. Views including relations that are not referred to in the given query are utilized. Attributes missing from a view can be recovered under certain conditions. We identify the conditions where a view may be used in evaluating a query and present the algorithm to search for the most efficient query among the equivalent ones. We also report on a simulation based on the TPC-H and GRID databases. Simulation results show that our approach provides impressive performance improvements to the data warehousing environment where aggregate views are often pre-computed and materialized.

This paper presents a scalable and efficient quota-based admission control scheme for the 3rd generation (3G) operator's IP backbone network, where quota denotes a chunk of bandwidth. This research is motivated by the 3G operator's need for guaranteeing end-to-end IP QoS of mobile-to-mobile and mobile-to-server multimedia sessions. In the proposed scheme, the quota size of a path implies the proper amount of allocated and released resources on the path condition. Employing the quota size makes the job of allocating or releasing resources at nodes in a path simple so that it becomes scalable. Moreover, with this simple scheme, an edge node can be allowed not only to initiate the allocation/release request but also to perform admission control function. To maximize the efficiency, the path quota size varies depending on the bottleneck link condition in the path. In high offered load, the proposed scheme decreases the path quota size and retains higher utilization while it requires lower signaling cost than the fixed scheme using a fixed size aggregation. As the load lessens, it increases the path quota size and reduces the signaling cost significantly.

One drawback of Integrated service architecture is the scaling problem. Therefore, flow aggregation is an important solution for supporting quality of service in large-scale network. In advance reservation, priori information of advance-reserved requests can be used for flow aggregation before their initiation time. However, an impolitic aggregation can lead to violate admission control. In this paper, we propose an effective algorithm to aggregate advance-reserved requests with guaranteed delay. The proposed algorithm not only can reduce the amount of state in core network but also minimize the bandwidth consumption. The simulation result indicates that the state in the core network can be reduced as low as 17.3% even in the worst case.

A rapid growth of the Internet and proliferation of new multimedia applications lead to demands of high speed and broadband network technologies. Routers are also necessary to follow up the growth of link bandwidths. From this reason, there have been many researches on high speed routers having switching capabilities. To have an expected effect, however, a control parameters set based on traffic characteristics are necessary. In this paper, we analyze the network traffic using the network traffic monitor and investigate the Internet traffic characteristics through a statistical analysis. We next show the application of our analytical results to parameter settings of high speed switching routers. Simulation results show that our approach makes highly utilized VC space and high performance in packet processing delay. We also show the effect of flow aggregation on MPLS. From our results, the flow aggregation has a great impact on the performance of MPLS.

In this paper, we propose optimization approaches for the parameter determination of the PNNI complex node model. Two optimal objectives are discussed: Least Square Approximation and Maximum Deviation Minimization. For each objective, we propose two practical criteria for setting up bypasses: Maximum Difference Removal and Largest Deviation Removal. Generalized inverse of matrix and linear programming techniques are used to find the solutions. The numerical results show that the least square approximation with the largest deviation removal criteria has the best performance as the number of bypasses increases.

A shared buffer ATM switch loaded with bursty input traffic is modeled by a discrete-time queueing system. Also, the unbalanced and correlated routing traffic patterns are considered. An approximation method to analyze the queueing system under consideration is developed. To overcome the problem regarding the size of state space to be dealt with, the entire switching system is decomposed into several subsystems, and then each subsystem is analyzed in isolation. We first propose an efficient algorithm for superposing all the individual bursty cell arrival processes to the switch. And then, the maximum entropy method is applied to obtain the steady-state probability distribution of the queueing system. From the obtained steady-state probabilities, we can derive some performance measures such as cell loss probability and average delay. Numerical examples of the proposed approximation method are given, which are compared with simulation results.

This paper investigates the lossless video aggregation and transport, a concept of transmitting a group of video sessions as a bundle over a communication network. We focus on the design of optimal transmission plan with minimum receiver buffer requirement for stored variable bit-rate (VBR) videos over a constant bit-rate (CBR) channel without incurring buffer underflow and overflow. For a single video, an efficient algorithm is proposed to calculate the optimal transmission plan in only O(N) time, a significant improvement of the previous result with time complexity of O(N2log N). For multiple video sessions, we propose an aggregation scheme to calculate the changes of optimal transmission plans at the joints or separations, where a session bundled in the aggregated video stream begins or stops. The experimental results show that our algorithms stand out in terms of simplicity and efficiency.

In this paper, we propose flow aggregation algorithms for multicast video transport. Because of heterogeneities of network/client environments and users' preference on the perceived video quality, various QoS requirements must be simultaneously guaranteed even for the single video source in the multicast connection. It is easy but ineffective to provide many video streams according to each user's request. Our flow aggregation algorithm arranges similar QoS requirements of clients into a single QoS requirement, by which the required number of video streams that the video server prepares can be decreased. Then the total amount of the required bandwidth can be reduced by sharing the same video stream among a number of clients. Our flow aggregation algorithm has two variants, which are suitable to sender-initiated and receiver-initiated multicast connections, respectively. Proposed algorithms are evaluated and compared through simulation. Then we show that the server-initiated flow aggregation (an ideal case in our approach) is most effective, but the receiver-initiated flow aggregation can also offer a reasonably effective mechanism.

Scientific database systems for the analysis of genes and proteins are becoming very important these days. We have developed a deductive database system PACADE for analyzing the three dimensional and secondary structures of proteins. In this paper, we describe the statistical data classification component of PACADE. We implemented the component for cluster analysis and discrimination analysis. In addition, we enhanced the aggregation function in order to calculate the characteristic values which are useful for data classification. By using the cluster analysis function, the proteins are thereby classified into different types of structural characteristics. The results of these structural analysis experiments are also described in this paper.

A new indexing technique for rapid evaluation of nested query on composite object is propoced, reducing the overall cost for retrieval and update. An extended B+ tree is introduced in which object identifier (OID) to be searched and path information usud for update of index record are stored in leaf node and subleaf node, respectively. In this method, the retrieval oeration is applied only for OIDs in the leaf node. The index records of both leaf and subleaf nodes are updated in such a way that the path information in the subleaf node and OIDs in the leaf node are reorganized by deleting and inserting the OIDs. The techniaue presented offers advantages over currently related indexing techniques in data reorganization and index allocation. In the proposed index record, the OIDs to be reorganized are always consecutively provided, and thus only the record directory is updated when an entire page should be removed. In addition, the proposed index can be allocate to a path with the length greater than 3 without splitting the path. Comparisons under a variety of conditions are given with current indexing techniques, showing improved performance in cost, i.e., the total number of pages accessed for retrieval and update.