This paper compares the performances of optimal routing as yielded by the pipe, hose, and intermediate models. The pipe model, which is specified by the exact traffic matrix, provides the best routing performance, but the traffic matrix is difficult to measure and predict accurately. On the other hand, the hose model is specified by just the total outgoing/incoming traffic from/to each node, but it has a problem in that its routing performance is degraded compared to the pipe model, due to insufficient traffic information. The intermediate model, where the upper and lower bounds of traffic demands for source-destination pairs are added as constraints, is a construction that lies between the pipe and hose models. The intermediate model, which lightens the difficulty of the pipe model, but narrows the range of traffic conditions specified by the hose model, offers better routing performance than the hose model. An optimal-routing formulation extended from the pipe model to the intermediate model can not be solved as a regular linear programming (LP) problem. Our solution, the introduction of a duality theorem, turns our problem into an LP formulation that can be easily solved. Numerical results show that the network congestion ratio for the pipe model is much lower than that of hose model. The differences in network congestion ratios between the pipe and hose models lie in the range from 27% to 45% for the various network topologies examined. The intermediate model offers better routing performance than the hose model. The intermediate model reduces the network congestion ratio by 34% compared to the hose model in an experimental network, when the upper-bound and lower-bound margins are set to 25% and 20%, respectively.

We present a congestion control algorithm for the Internet and assess its stability. The algorithm has low operation complexity and exercises control over sources without keeping per-flow information. Given the lack of support for explicit-rate feedback in the Internet, we discuss an implementation where feedback is based on explicit binary indications. We assess the stability through a discrete-time model and present simulation results showing the efficacy of the algorithm. The obtained results indicate that when the algorithm is used to control sources that support explicit binary feedback, its stability is not affected and its performance is close to that obtained with sources that support explicit-rate feedback.

This letter proposes a dynamic bandwidth allocation algorithm for access networks based PON (Passive Optical Network). It considers the mixture of transport layer protocols when responding to traffic congestion at the SNI (Service Node Interface). Simulations on a mixture of TCP (Transmission Control Protocol), and UDP (User Datagram Protocol) traffic flows show that the algorithm increases the throughput of TCP, improves the fairness between the two protocols, and solves the congestion problem at the SNI.

In network tomography, most work to date is based on exploiting probe packet level correlations to infer the link loss rates and delay distributions. Some other work focuses on identifying the congested links using uncorrelated end-to-end measurements and link prior probability of being congested. In their work, the prior probabilities are identified by the matrix inversion with a number of measurement snapshots, and the algorithm to find the congested links is heuristic and not optimal. In this letter, we present a new estimator for the prior probabilities that is computationally simple, being an explicit function of the measurement snapshots. With these prior probabilities, the identification of the congested link set is equivalent to finding the solution for a probability maximization problem. We propose a fast bottom-up approach named FBA to find the solution for this problem. The FBA optimizes the solution step by step from the bottom up. We prove that the solution by the FBA is optimal.

We consider a single-link multi-source network with FAST TCP sources. We adopt a continuous-time dynamic model for FAST TCP sources, and propose a static model to adequately describe the queuing delay dynamics at the link. The proposed model turns out to have a structure that reveals the time-varying network feedback delay, which allows us to analyze FAST TCP with due consideration of the time-varying network feedback delay. Based on the proposed model, we establish sufficient conditions for the boundedness of congestion window of each source and for the global asymptotic stability. The asymptotic stability condition shows that the stability property of each source is affected by all other sources sharing the link. Simulation results illustrate the validity of the sufficient condition for the global asymptotic stability.

In this paper, we obtain some refinement of representation theorems for context-free languages by using Dyck languages, insertion systems, strictly locally testable languages, and morphisms. For instance, we improved the Chomsky-Schützenberger representation theorem and show that each context-free language L can be represented in the form L=h(D ∪ R), where D is a Dyck language, R is a strictly 3-testable language, and h is a morphism. A similar representation for context-free languages can be obtained, using insertion systems of weight (3,0) and strictly 4-testable languages.

This paper proposes an improved method of reversible data hiding with increased capacity. The conventional method determines whether to embed a data bit in an image block according to the statistics of pixels in that block. Some images have pixel statistics that are inadequate for data hiding, and seldom or never have data embedded in them. The proposed method modulates the statistics invertibility to overcome such disadvantages, and is also able to improve the quality of the image containing the hidden data using block-adaptive modulation. Simulationresults show the effectiveness of the proposed method.

Tree structured data often appear in bioinformatics. For example, glycans, RNA secondary structures and phylogenetic trees usually have tree structures. Comparison of trees is one of fundamental tasks in analysis of these data. Various distance measures have been proposed and utilized for comparison of trees, among which extensive studies have been done on tree edit distance. In this paper, we review key results and our recent results on the tree edit distance problem and related problems. In particular, we review polynomial time exact algorithms and more efficient approximation algorithms for the edit distance problem for ordered trees, and approximation algorithms for the largest common sub-tree problem for unordered trees. We also review applications of tree edit distance and its variants to bioinformatics with focusing on comparison of glycan structures.

In this paper, we address the following problems: Given a sequence A of n real numbers, and four parameters I,J,X and Y with I≤ J and X≤ Y, find the longest (or shortest) subsequence of A such that its length is between I and J and its sum is between X and Y. We present an online and an offline algorithm for the problems, both run in O(nlog n) time, which are optimal.

In this paper, an effective congestion control algorithm is proposed to increase the end-to-end delivery success ratio of upstream traffic by reduction of buffer drop probabilities and their deviation in wireless sensor networks. According to the queue length of parent and child nodes, each child node chooses one of the parents as the next hop to the sink and controls the delay before transmission begins. It balances traffics among parents and mitigates congestion based on congestion level of a node. Simulation results show that the proposed algorithm reduces buffer drop probabilities and their deviation and increases the end-to-end delivery success ratio in wireless sensor networks.

Traditional TCP has a good congestion control strategy that adapts its sending rate in accordance with network congestion. In addition, a fast recovery algorithm can help TCP achieve better throughput by responding to temporary network congestion well. However, if multiple packet losses occur, the time to enter congestion avoidance phase would be delayed due to the long recovery time. Moreover, during the recovery phase, TCP freezes congestion window size until all lost packets are recovered, and this can make recovery time much longer resulting in performance degradation. To mitigate such recovery overhead, we propose Momentary recovery algorithm that recovers packet loss without an extra recovery phase. As other TCP and variants, our algorithm also halves the congestion window size when packet drop is detected, but it performs congestion avoidance phase immediately as if loss recovery is completed. For lost packets, TCP sender transmits them along with normal packets as long as congestion window permits rather than performs fast retransmission. In this manner, we can eliminate recovery overhead efficiently and reach steady state momentarily after network congestion. Finally, we provide a simulation based study on TCP recovery behaviors and confirm that our Momentary recovery algorithm always shows better performance compared with NewReno, SACK, and FACK.

In general, the spleen accompanied by abnormal abdomen is hypertrophied. However, if the spleen size is originally small, it is hard to detect the splenic enlargement due to abnormal abdomen by simply measure the size. On the contrary, the spleen size of a person having a normal abdomen may be large by nature. Therefore, measuring the size of spleen is not a reliable diagnostic measure of its enlargement or the abdomen abnormality. This paper proposes an automatic method to diagnose the splenic enlargement due to abnormality, by examining the boundary pattern of spleen in abdominal CT images.

In Low Earth Orbit (LEO) satellite networks, the user distributions are unbalanced due to the geography and the population dispersion. As a result, some satellites have few traffic loads, while others have heavy traffic loads which often lead to congestion events. In this paper, we propose a novel load balancing method based on congestion prediction. In the proposed method, each satellite detects areas where congestion often occurs and conveys their positions to its adjacent satellites. In those areas, the concerned satellites perform load balancing algorithms to prevent congestion. The performance of the proposed method is evaluated through a number of simulations. The simulation results demonstrate that the proposed scheme improves packet drop rate, end-to-end delay, and throughput.

In this paper, we present a new dependency parsing method for languages which have very small annotated corpus and for which methods of segmentation and morphological analysis producing a unique (automatically disambiguated) result are very unreliable. Our method works on a morphosyntactic lattice factorizing all possible segmentation and part-of-speech tagging results. The quality of the input to syntactic analysis is hence much better than that of an unreliable unique sequence of lemmatized and tagged words. We propose an adaptation of Eisner's algorithm for finding the k-best dependency trees in a morphosyntactic lattice structure encoding multiple results of morphosyntactic analysis. Moreover, we present how to use Dependency Insertion Grammar in order to adjust the scores and filter out invalid trees, the use of language model to rescore the parse trees and the k-best extension of our parsing model. The highest parsing accuracy reported in this paper is 74.32% which represents a 6.31% improvement compared to the model taking the input from the unreliable morphosyntactic analysis tools.

This letter presents the optimal routing by the intermediate model; a construction that lies between the pipe and hose models. We show that it is a practical way of realizing optimal routing. A formulation extended from the pipe model to the intermediate model can not be solved as a regular linear programming (LP) problem. Our solution, the introduction of a duality theorem, successfully turns our problem into an LP formulation that can be easily solved. Numerical results show that the intermediate model has better routing performance than the hose model.

Time-Triggered Controller Area Network is widely accepted as a viable solution for real-time communication systems such as in-vehicle communications. However, although TTCAN has been designed to support both periodic and sporadic real-time messages, previous studies mostly focused on providing deterministic real-time guarantees for periodic messages while barely addressing the performance issue of sporadic messages. In this paper, we present an O(n2) scheduling algorithm that can minimize the maximum duration of exclusive windows occupied by periodic messages, thereby minimizing the worst-case scheduling delays experienced by sporadic messages.

In addition to high bit error rates, large and sudden variations in delay often occur in wireless cellular networks. The delay can be several times the typical round-trip time, which can cause the spurious timeout. In this letter, we propose a new window control algorithm to improve TCP performance in wireless cellular networks with large delay variation and high bit error rates. Simulation results illustrate that our proposal improves the performance of TCP in terms of fairness and link utilization.

Several scheduling algorithms have been proposed for the downlink of a Code Division Multiple Access (CDMA) system with High Data Rate (HDR). Modified Largest Weighted Delay First (M-LWDF) scheduling algorithm selects a user according to the user current channel condition, user head-of-line packet delay and user Quality of Service (QoS) requirement. Proportional Fair (PF) scheduling algorithm has also been proposed for CDMA/HDR system and it selects a user according to the ratio of the user current channel rate and the user average channel rate, which provides good performance in terms of fairness. However, when variable bit rate (VBR) traffic is considered under different channel conditions for each user, both schedulers' performance decrease. M-LWDF scheduler can not guarantee the QoS requirement to be achieved and PF scheduler can not achieve a good fairness among the users. In this work, we propose a new scheduling algorithm to enhance M-LWDF and PF schedulers performance. Proposed scheduler selects a user according to the user input traffic characteristic, user current channel condition and user QoS requirement, which consists of a delay value with a maximum violation probability. We consider the well-known effective bandwidth expression, which takes into account the user QoS requirement and the user input traffic characteristics, to select a user to be scheduled. Properties of the proposed scheduling algorithm are investigated through simulations with constant bit rate (CBR) and VBR flows and performance comparisons with M-LWDF and PF schedulers. The results show a better performance of the proposed scheduler compared with M-LWDF and PF schedulers.

In this paper, we propose a three-phase text error correction model consisting of a word spacing error correction phase, a syllable-based spelling error correction phase, and a word-based spelling error correction phase. In order to reduce the text error correction complexity, the proposed model corrects text errors step by step. With the aim of correcting word spacing errors, spelling errors, and mixed errors in SMS messages, the proposed model tries to separately manage the word spacing error correction phase and the spelling error correction phase. For the purpose of utilizing both the syllable-based approach covering various errors and the word-based approach correcting some specific errors accurately, the proposed model subdivides the spelling error correction phase into the syllable-based phase and the word-based phase. Experimental results show that the proposed model can improve the performance by solving the text error correction problem based on the divide-and-conquer strategy.

The Processing of high-dynamic-range (HDR) images is embodied by a lot of algorithms. This paper takes notice of one of these algorithms which is presented using the iCAM06. iCAM06 is capable of making color appearance predictions of HDR images based on CIECAM02 color predictions and incorporating spatial process models in the human visual system (HVS) for contrast enhancement. The effect of user controllable factors of iCAM06 was investigated and the best factor which corresponds with Breneman's corresponding color data sets was found. A suggested model improves color matching predictions for the corresponding color data set in Breneman's experiment.