In this paper, a theory of lexicographic optimization for convex and compact feasible sets is presented. Existence, globality, unimodality, and uniqueness of the solution to the problem are proved. Also, necessary and sufficient conditions are derived that establish the relationship between the lexicographic problem and the maxmin problem. This framework is shown to be useful in the problem of designing flow control protocols. Towards this objective, a theory of bottleneck ordering is introduced, which unveils the convergence properties of the flow control problem.

Maxmin is a flow control mechanism based on fairness criteria. In this paper we consider the problem of routing and maxmin rate allocation over a communication network. We present two contributions in this paper. The first contribution is to provide a new relative maxmin definition and to extend the concepts of advertised rate from single-path to multi-path networks. The second contribution is to propose a novel multi- path maxmin routing scheme based on new advertised rate algorithm. We prove that this new scheme will converge to relative maxmin solution.

In the current Internet, congestion control is performed jointly by the end systems running the TCP protocol and by routers running active queue management (AQM) algorithms. Due to the TCP protocol's AIMD congestion control algorithm and its round trip time delay to react to packet losses, it is very hard to maintain high TCP throughput with a low packet loss rate in routers. In addition, unresponsive traffic, such as short HTTP sessions, do not react to AQM packet loss/marks. Hence, these unresponsive traffic may cause high packet loss in the AQM queues due to its high bursts. In this paper, we provide a solution to identify unresponsive traffic in AQM queues that does not need packet header examination. In our solution, periodic features of TCP traffic due to its AIMD behavior is first estimated in the mixed incoming traffic. We then design a wavelet de-noising filter to separate the high bursts in unresponsive traffic from the TCP traffic and allow those bursts to bypass the AQM queue. By allowing bursts of unresponsive traffic to bypass AQM queues, we not only avoid the impact of unresponsive traffic to AQM queues, but also avoid dropping extra packets in those unresponsive flows. Our proposed de-noising scheme is suitable for high speed networks, where per packet header examination is expensive. Our simulations show that the proposed de-noising scheme is effective on heavily congested links. An analysis of the computational complexity of the proposed scheme is also provided.

The well-known edge server bottleneck is shown in this paper to be the result of a mismatch between the general-purpose architecture and the special-purpose data functions it was not intended to perform exclusively. Six overheads are identified that contribute significantly to the bottleneck. To solve this bottleneck problem, a solution is to apply the principle of separation between control and data functions. While the idea is not new, the application of this principle to the edge server architecture is novel in the convergence of three technologies: network, server, and storage. Notable performance has been obtained with this approach using ASIC implementation for TCP or UDP streaming applications.

The problem of time-optimal network queue control is solved: what are the input data rates that make network queue sizes converge to their ideal size in the least possible time after a disturbance while still maintaining maximum link utilization at all times, even in the transient? The problem is nontrivial especially because of the vast possible heterogeneity in packet propagation delays in the network. In this paper, we derive the time-optimal queue control for a single congested network node with a single finite queue shared by flows with arbitrary network delays. We neatly separate the derivation of the optimal arrival rate sequence from that of the feedback control protocol to achieve it. The time-optimal control is robust to bandwidth and queue size estimation errors. Its complexity is only a function of the size of the network delays and no per-flow computation is needed. The time-optimality and robustness properties are proven to hold under all queue operating regimes with no need for linearizing approximations.

Current efforts on ad hoc wireless network research are focused more on routing and multicasting protocols. However, there is an increasing need to understand what sort of media could be transported over wireless ad hoc networks other than data. Existing research on multimedia wireless communications often addresses broadband wireless networks with a connection-oriented backbone. In this paper, we address the possibility of transporting audio traffic over wireless ad hoc networks. We examine the impact of wireless multi-hop links on audio data relay and how the audio quality at the receiver is affected. In particular, we examine communication parameters such as latency, jitter, packet loss, and their impact on perceived audio quality.

This paper proposes an integrated solution to handoffs in wireless ATM networks. The proposed method has the following features: 1) combining soft handoff and hard handoff into one, 2) solving the crossed path problem due to both ends of a connection making handoffs at the same time, 3) minimizing overheads due to move back, and 4) minimizing QoS adaptation by load balancing. Previous studies cover at most one aspect of the proposed protocol. The crossed path problem arises when the crossover switch found by one end does not lie on the new path determined by the other end of the same connection. The proposed protocol minimizes handoff delay and cell delay. Simulation results show excellent scalability, adaptability, stability, and flexibility of the protocol. Performance analysis of the protocol is also provided.

This paper presents the first distributed multi-rate maxmin rate allocation protocol for multicast traffic. The protocol supports minimum rate guarantee for each receiver as a QoS parameter. The protocol is practical and it maintains a good performance-scalability trade-off. While the network is required to participate, the complexity added by the protocol is minimal.

This paper proposes a solution to the problem of crossed path, which may occur when both ends of the connection are mobile hosts (MHs) for wireless ATM networks. Previous studies cover the case when only one MH makes a handoff. To minimize circuit setup cost, most of these studies propose the crossover switch (CX) solution so that parts of the original path can be retained in the new path. This study deals with the case when both MHs make handoffs. In such a case, CX found by one end may not lie on the new path determined by the other end, and a crossed path situation occurs. This paper proposes a protocol to resolve the crossed path problem so that a new path can satisfy the QoS requirement of the virtual connection (VC) when a QoS guaranteed path exists. In addition, this paper solves the "moveback" problem that also exists in a single handoff. The proposed protocol has the best performance with CDMA because of its soft handoff feature. Simulation results reveal the scalability, flexibility and robustness of the protocol. Performance analysis of the protocol is also provided.

This paper proposes a QoS adaptation scheme for both wireline and wireless networks. Multiplexed adaptive queuing (MAQ) requires only three queues per output port in any switch router; thus minimizing the complexity associated with queue management. MAQ provides a multitude of features that enable networks to adapt QoS mechanisms. The scheme is a scalable closed-loop control protocol based on dynamic priority labeling of packets at edge nodes and bandwidth assignment at both edge and core nodes using the rate-based feedback from the network. The connections with a wide spectrum of end-to-end QoS requirements are statistically multiplexed to the extent that their requirements can be satisfied while still maintaining simplicity and scalability of scheduling and buffer management inside the network. Therefore, individual flows are mapped to fine-grain QoS classes at the edge nodes, while at the core nodes, coarse-grain QoS is provided by aggregating flows into limited number of priority queues. Analysis and simulation studies demonstrate the effectiveness of the proposed scheme.

The problem of allocating maxmin rates with minimum rate constraints for connection-oriented networks is considered. This paper proves that the convergence of maxmin rate allocation satisfies a partial ordering in the bottleneck links. This partial ordering leads to a tighter lower bound for the convergence time for any maxmin protocol. An optimally fast maxmin rate allocation protocol called the distributed constraint precedence graph (CPG) protocol is designed based on this ordering theory. The new protocol employs bi-directional minimization and does not induce transient oscillations. The distributed CPG protocol is compared against ERICA, showing far superior performance.

This paper considers STMM, a spatio-temporal max-min fair rate allocation for virtual circuits (VCs) in networks with time-varying link capacities. This is a direct generalization of conventional steady-state max-min fair rate allocation. In an STMM allocation, all links are fully utilized while maintaining feasibility and fairness among VCs at all times. It is shown that if and only if the propagation delay differences between VCs as seen at different switches is consistent, the STMM problem gets decoupled into a time-sequence of independent steady-state max-min fair allocation problems. A generic protocol to achieve STMM allocation in such networks is presented. Practical temporal flow control protocols which take link delays into account, can be then designed as approximations of this ideal protocol.

This paper proves a tight lower and upper bound for the convergence of max-min rate allocation protocols for connection-oriented networks. The theory is based on the concept of a constraint precedence graph. The analysis and simulation results show that the previously known convergence time estimates are too pessimistic.

The discrete multitone (DMT) modulation is the transmission scheme of choice in ADSL. DMT works on the condition that the standardized length-32 cyclic prefix guard band is longer than the channel for the purpose of orthogonalizing the sub-bands. Time-domain equalizers (TEQ) have been designed for the DMT receiver to shorten the physical channel response. This paper expands on a proposed TEQ scheme by reformulating its optimization problem to avoid matrix decompositions or inversions, and by devising a numerically sound solution using the inverse power method. Simulation results show the reformulated solution to be near-optimal.

This paper introduces a scalable maxmin flow control protocol which guarantees the minimum rate for each connection-oriented flow without requiring per-flow information. The protocol is called MR-ASAP (minimum rate guaranteeing adaptive source-link accounting protocol). MR-ASAP is an extension of ASAP, the first exact maxmin flow control protocol for best-effort connection-oriented traffic in integrated service networks, without requiring per-flow accounting at the intermediate network node. In the classical maxmin computation, only the maximum rate constraints are considered; in this paper the minimum rate requirements are treated similarly as the maximum rate constraints. Existing protocols that achieve exact maxmin optimality with minimum rate guarantee require per-flow information and complex computation such as sorting of the minimum rates at the switch. By generalizing the concept of constraint, the complex sorting and per-flow accounting required in the existing protocols are avoided. Simulation demonstrates fast convergence to optimality.

This paper re-examines maxmin protocols for ABR traffic in ATM networks in four aspects: convergence, complexity, variations, and performance. First, the concept of "pseudo-saturation" is introduced. Most, if not all, protocols do not properly handle pseudo-saturated links, and as a result, there is no guarantee for convergence to true maxmin solutions. Second, the concept of "constraint precedence graph (CPG)" is introduced and is used to define the best possible time complexity of any maxmin protocol. The existing complexity estimates are overly conservative because they do not consider possible concurrent operations. In contrast, the CPG analysis explicitly accounts for parallelization. Third, the concept of "constraint" is generalized and this generalization is used to derive an optimality condition for the maxmin problem with nonzero minimum cell rate (MCR) requirements. This optimality condition can be used in conjunction with any maxmin protocol to handle the nonzero MCR requirements without adding excessive complexity. Finally, simulations suggest that the complexity analysis is inadequate to gauge protocol performance. A new analysis based on protocol dynamics is called for to understand the performance.

In this paper, we derive a time-complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of Goldstein-Levitin-Poljak type formulated by Bertsekas (1982), Bertsekas and Gallager (1987) and Bertsekas et al. (1984) converges to within /spl epsi/ in relative accuracy in O(/spl epsi//sup -2/h/sub min/N/sub max/) number of iterations, where N/sub max/ is the number of paths sharing the maximally shared link, and h/sub min/ is the diameter of the network. Based on this complexity result, we also show that the one-source-at-a-time update policy has a complexity bound which is O(n) times smaller than that of the all-at-a-time update policy, where n is the number of nodes in the network. The result of this paper argues for constructing networks with low diameter for the purpose of reducing complexity of the network control algorithms. The result also implies that parallelizing the optimal routing algorithm over the network nodes is beneficial.

The EPRCA (enhanced proportional rate control algorithm) is a leading congestion control protocol for available bit rate (ABR) service in ATM networks. Even though EPRCA has been adopted by the ATM Forum as the standard for ABR congestion control, we show that this protocol is only marginally stable. The stability analysis presented in this paper does not consider interactions among network components and should be considered as a bottle-neck stability result. We show that, if a queue is the bottleneck of a congested path, then its queue size will eventually decrease. However, if a queue is not congested, its queue size can actually increase and the congestion can be self-induced.

Derives a time complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of the Goldstein-Levitin-Poljak type formulated by Bertsekas (1982) converges to within /spl epsiv/ in relative accuracy in O(/spl epsiv//sup 2/h/sub min/N/sub max//sup L/) iterations, where N/sub max//sup L/ is the number of paths sharing the maximally shared link, and h/sub min/ is the diameter of the network. Based on this complexity result, the authors also show that the one-source-at-a-time update policy has a complexity bound which is O(n) times smaller than that of the all-at-a-time update policy [Bertsekas, 1982], where n is the number of nodes in the network. The result of the paper argues for constructing networks with low diameter for the purpose of reducing the complexity of the network control algorithms. The result also implies that parallelizing the optimal rotating algorithm over the network nodes is beneficial.

In this paper, we develop a logic synthesis approach which relies on accurate design evaluation program to estimate the final design attributes such as layout speed. Given a candidate design implementation, an evaluation program is called upon to provide quick and accurate estimates of the critical path delay. This information is then used as a feedback to the logic optimization system. Based on this feedback, the system will "re-orient" itself toward a new direction for optimization. Such a scheme represents a more realistic way of generating optimal layout implementations.>

An accelerated learning algorithm (ABP-adaptive back propagation) is proposed for the supervised training of multilayer perceptron networks. The learning algorithm is inspired from the principle of "forced dynamics" for the total error functional. The algorithm updates the weights in the direction of steepest descent, but with a learning rate a specific function of the error and of the error gradient norm. This specific form of this function is chosen such as to accelerate convergence. Furthermore, ABP introduces no additional "tuning" parameters found in variants of the backpropagation algorithm. Simulation results indicate a superior convergence speed for analog problems only, as compared to other competing methods, as well as reduced sensitivity to algorithm step size parameter variations.

An efficient algorithm for a logic synthesis system based on global dynamic extraction and flexible cost (GDEF) is described. The GDEF is designed to find the best common subexpression and to update the value of the other common subexpressions dynamically. The GDEF feedbacks approximate layout area obtained through an area-estimation program to guide the logic synthesis process. In this approach, the cost function is dependent on both literal count and estimated area.>

The gradient-projection (GP) technique is used to solve the optimal routing problem (ORP) for high-speed asynchronous transfer mode (ATM) networks. The ORP minimizing network average packet loss probability is complicated due to packet losses at intermediate switching nodes, and the problem is nonconvex. The nonconvex ORP is transformed into a convex ORP called the reduced-ORP (R-ORP), and the GP algorithm is used to obtain a routing solution. The solution obtained for the R-ORP is shown to be a good approximation of the globally optimal solution for the ORP for realistic network operating conditions. A theoretical upper bound of the difference between the R-ORP solution and the ORP solution is derived.>

The implementation of a combined flow control and optimal routing algorithm in packet switched networks is discussed. An analysis is made of the influence of various objective functions on maximum link utilization, average packet delay and fairness. How the parameters in the proposed objective function affect network performance measures like the flow in the entire network, amount of rejected traffic, maximum link utilization, average packet delay, and unfairness among users is studied. These measures are evaluated for various networks and traffic configurations, and, on the basis of these studies and results, suggestions are made for obtaining the best network performance and utilization.>

A distributed algorithm is presented that can be used to solve the single-destination shortest path (SDSP) problem or the all-pairs shortest path (APSP) problem for a class of clustered data networks. The network graph is assumed to be characterized with a balanced hierarchically clustered (BHC) topology. The BHC topology is introduced in this paper and is shown to be a realistic characterization for a large class of interconnected data networks. For certain types of BHC topologies, the SDSP problem can be solved with computation and communication time complexities of O(log n), assuming one processor is available at each of the n number of nodes. Assuming p processors are available at each node, computation and communication time complexities of O((n/p) log n) and O(n log n) are achievable, respectively, for solving the APSP problem. It is also shown that the algorithm converges in an asynchronous environment.>

A cluster management scheme for dynamic networks, the purpose of which is to maintain the cluster structure of the hierarchical network as a balanced-tree topology is presented. The theoretical time complexity bounds of the cluster management scheme for node birth and death are derived. The effects of the cluster management on gate-connected fixed-node networks under heavy intercluster traffic situations are discussed. In order to show that the scheme can handle realistic communication networks, routing tables and OD pair shortest path routing are used. The settle-down time, throughput, and end-to-end link delays of a network that uses cluster management and a network of the same topology that only uses flooding are compared.>

A recurrent multilayer perceptron (MLP) network topology is used in the identification of nonlinear dynamic systems from only the input/output measurements. This effort is part of a research program devoted to developing real-time diagnostics and predictive control techniques for large-scale complex nonlinear dynamic systems. The identification is performed in the discrete-time domain, with the learning algorithm being a modified form of the back-propagation (BP) rule. The recurrent dynamic network (RDN) developed is used for the identification of a simple power plant boiler with known nonlinear behavior. Results indicate that the RDN can reproduce the nonlinear response of the boiler while keeping the number of nodes roughly equal to the relative order of the system. A number of issues are identified regarding the behavior of the RDN which are unresolved and require further research. Use of the recurrent MLP structure with a variety of different learning algorithms may prove useful in utilizing artificial neural networks for recognition, classification, and prediction of dynamic patterns

A novel artificial neural network model based on P. Kanerva's (MIT Press, 1988) sparse distributed memory (SDM) is presented. The model possesses many major advantages over the original SDM. It is adaptive in the sense that the memory cells are called into service or released from service by a global mechanism. Since memory cells are utilized depending on the load on the memory, the actual number of memory cells needed to implement the ASDN (adaptive SDM) is significantly smaller than what is required for the original SDM. The storing and retrieval procedures are much simpler, and analysis of the best match problem can be carried out in a deterministic setting. All the advantages of the original SDM are retained while the main drawback of the original SDM, namely, the huge number of physical memory locations, is removed. The concept of time-varying intensity of memory is introduced, and customized metrics for determining distance between two data objects are allowed

A distributed algorithm is presented which finds the shortest path from every node in the network to a given destination node. The network topology is assumed to be organizable into a generalized balanced-tree hierarchy (BH). The BH topology is introduced and characterized, and it is shown that most large interconnected data networks are of this type. It is also shown that the algorithm converges in an asynchronous environment. Therefore, some of the difficulties associated with synchronizing the order of events can be avoided in the actual implementation of the proposed algorithm.>

Fairness in multiple-path optimal routing algorithms in virtual circuit data networks is investigated. Fairness measures are developed to evaluate optimal routings. Several objective functions are considered to be possible replacements of the average packet delay objective function that is widely used in optimal routing algorithms, and evaluated for various network and traffic configurations. A numerical study using the fairness measures developed shows that the objective function which is in the integral form of the average packet delay achieves perfect fairness while sacrificing only a nominal increase in the average packet delay. The numerical study also confirms the conjecture by D.P. Bertsekas and R.G. Gallager (1987) that the form of objective function does not affect the average packet delay in any significant way.>

An adaptive hierarchical routing protocol based on the extension of the new Arpanet scheme is proposed and its simulated performance is presented. The protocol can adapt to rapidly changing environments and works for arbitrarily large networks. A number of existing schemes as well as the proposed scheme are simulated under many different environments and clustering structures. The proposed protocol is found to be superior to the other protocols tested in many different types of network traffic and topological configurations. The results indicate that intercluster links must be reliable, because (1) the failure of these links can significantly degrade the routing performance, even though the protocol does not degrade as badly as the existing scheme and (2) hierarchical routing protocols usually prefer small clusters, which means that there will be many intercluster links. The tradeoff between two conflicting performance criteria, response speed and communication overhead, is shown.>