Packet routing on grids of processors

The problem of routing packets onn ₁×...×n _r mesh-connected arrays or grids of processors is studied. The focus of this paper is on permutation routing where each processor contains exactly one packet initially and finally. A slight modification of permutation routing called balanced routing is also discussed. For two-dimensional grids a determinisitc routing algorithm is given forn×n meshes where each processor has a buffer of size f(n) < n. It needs 2n + O(n/f(n)) steps on grids without wrap-arounds. Hence, it is asymptoticaliy nearly optimal, and as good as randomized algorithms routing data only with high probability. Furthermore, it is demonstrated that onr-dimensional cubes of processors permutation routing can be performed asymptotically by (2r–2)n steps, which is faster than the running times of so-far known randomized algorithms and of deterministic algorithms.Partially supported by Siemens AG, München.     

Worst-case identification in ℓ2: linear and nonlinear algorithms

We consider worst-case identification in the ℓ₂ norm. Given an unknown system h ε ℓ₁ one wishes to choose bounded inputs u ε ℓ∞ such that given finitely many corrupted output measurements {y(k): 0 ≤ k}of Y = h*u + η, where η is noise, assumed small, one can construct an approximation g with g - h₂ → 0 as η∞ → 0 and n → ∞. It is shown that inputs can be chosen such that to identify a sequence of length n with an ℓ₂ error of O(η∞) one requires only O(n) measurements. A numerical example is inclu     

Nonlinear eigenvalue problems for quasilinear systems

The paper deals with the existence of positive solutions for the quasilinear system (Φ(u'))' + λh(t)f(u) = 0,0 < t < 1 with the boundary condition u(0) = u(1) = 0. The vector-valued function Φ is defined by Φ(u) = (q(t)(p(t)u₁), …, q(t)(p(t)u_n)), where u = (u₁, …, u_n), andcovers the two important cases (u) = u and (u) = up > 1, h(t) = diag[h₁(t), …, h_n(t)] and f(u) = (f¹(u), …, fⁿ (u)). Assume that fⁱ and h_i are nonnegative continuous. For u = (u₁, …, u_n), let

, f₀ = maxf¹₀, …, fⁿ₀ and f_∞ = maxf¹_∞, …, fⁿ_∞. We prove that the boundary value problem has a positive solution, for certain finite intervals of λ, if one of f₀ and f_∞ is large enough and the other one is small enough. Our methods employ fixed-point theorem in a cone.     

Minimal Adaptive Routing on the Mesh with Bounded Queue Size

An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptive routing algorithms, we present an Ω(n²/k²) bound on the worst case time to route a static permutation of packets on ann×nmesh or torus with nodes that can hold up tok≥ 1 packets each. This is the first nontrivial lower bound on adaptive routing algorithms. The argument extends to more general routing problems, such as theh–hrouting problem. It also extends to a large class of dimension order routing algorithms, yielding an Ω(n²/k) time bound. To complement these lower bounds, we present two upper bounds. One is anO(n²/k+n) time dimension order routing algorithm that matches the lower bound. The other is the first instance of a minimal adaptive routing algorithm that achievesO(n) time with constant sized queues per node. We point out why the latter algorithm is outside the model of our lower bounds.     

Oscillation criteria of certain nonlinear partial difference equations

This paper is concerned with the nonlinear partial difference equation with continuous variables

,where a, σ_i, τ_i are positive numbers, h_i(x, y, u) ε C(R⁺ × R⁺ × R, R), uh_i(x, y, u) > 0 for u ≠ 0, h_i is nondecreasing in u, i = 1, …, m. Some oscillation criteria of this equation are obtained.     

Maximum flow and critical cutset as descriptors of multi-state systems with randomly capacitated components

Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b₁(τ), …, B_n(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation.     

Tight Bounds on Parallel List Marking

The list marking problem involves marking the nodes of an ℓ-node linked list stored in the memory of a (p, n)-PRAM, when only the position of the head of the list is initially known, while the remaining list nodes are stored in arbitrary memory locations. Under the assumption that cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish anΩ(min{ℓ, n/p}) randomized lower bound for ℓ-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. Such a result implies that randomization cannot be exploited in any significant way in this setting. For the case where list cells are tagged in a way that differentiates them from other cells, the above lower bound still applies to deterministic algorithms, while we establish a tight

Full-size image

bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values.     

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nⁿ nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.     

Avoidance of churn rate through temporal centralization in Chord

In this paper we have introduced a concept called temporal centralization to handle high churn rate without disturbing the original decentralized architecture of Peer-to-Peer overlay system. The frequent joining/leaving of nodes in a P2P system costs high. We know that the well-known structured system like Chord handles query in O(logn), but node joining/leaving is O(logn)², where n is the number of nodes available in the system. Therefore, with high churn rate, it is hard to maintain the cost of routing table. In our approach, updation of all routing tables are not done immediately after a node joining the system. We introduce the concept of temporal centralization to Chord protocol that reduces the churn rate retaining the same number of steps for query processing. The simulation results show the improvement of performance of P2P network reducing transient node population.     

Some new paranormed sequence spaces

Maddox defined the sequence spaces ℓ_∞(p), c(p) and c₀(p) in [Proc. Camb. Philos. Soc. 64 (1968) 335, Quart. J. Math. Oxford (2) 18 (1967) 345]. In the present paper, the sequence spaces a₀^r(u,p) and a_c^r(u,p) of non-absolute type have been introduced and proved that the spaces a₀^r(u,p) and a_c^r(u,p) are linearly isomorphic to the spaces c₀(p) and c(p), respectively. Besides this, the α-, β- and γ-duals of the spaces a₀^r(u,p) and a_c^r(u,p) have been computed and their basis have been constructed. Finally, a basic theorem has been given and later some matrix mappings from a₀^r(u,p) to the some sequence spaces of Maddox and to some new sequence spaces have been characterized.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

Randomized multipacket routing and sorting on meshes

We consider the problem of routing and sorting ond-dimensionaln×...× mesh connected computers. Each of the processing units initially holdsk packets. We present randomized algorithms that solve these problems with (1+o(1))·max{2·d·n,k·n/2} communication steps. On a torus these problems are solved twice as fast. Thus we match the bisection bound up to lower-order terms, for allk≥4·d. Earlier algorithms required some additional Θ(n) steps or more, and were more complicated. With 2·d·n extra steps our algorithm can also route in the cut-through routing model.     

The fastcube: a variation on hypercube topology with lower diameter

This paper presents a class of n-dimensional interconnection topologies with N=2ⁿ nodes which we refer to as n-fastcubes. The node degree of the n-fastcube is n and its diameter is ⌈(n+1)/2⌉, which is substantially smaller than that of the same size hypercube. Topological properties as well as several routing algorithms for fastcubes are developed. In addition, a new methodology for the design and analysis of fastcubes is employed. This methodology is based on modeling interconnection networks as finite state automata. The inputs to these particular automata are routing sequences. The routing and embedding algorithms developed in this paper produce routing sequences. The main characteristic of routing sequences is their node independence. A node independent routing sequence, p(H), produces a path between any pair of nodes with the Hamming distance of H. Thus, these sequences can be used, without modification, at any node to establish paths in a fastcube.     

Generalized dilations and the stabilization of uncertain systems via measurement feedback

We study the problem of semiglobally stabilizing uncertain nonlinear system

Full-size image

, with (A,B) in Brunowski form. We prove that if p₁(z,u,t)u and p₂(z,u,t)u are of order greater than 1 and 0, respectively, with “generalized” dilation δ_l(z,u)=(l¹⁻ⁿz₁,…,l⁻¹z_n−1,z_n,lu) and uniformly with respect to t, where z_i is the ith component of z, then we can achieve semiglobal stabilization via arbitrarily bounded linear measurement feedback.     

Two-Pass Rearrangeability in Faulty Benes Networks

Existing fault-tolerant routing schemes for Benes networks either consider only the control line stuck-at faults, or handle the switch faults by some graceful degradation routing schemes that reconfigure the network into a smaller system with minimal loss. Now, even in the presence of a single switch fault in anN×NBenes networkB(n), (n= log₂N), noN×Npermutation can be realized in a single pass. In this paper, we attempt to characterize the switch fault sets inB(n), in the presence of which the network is always capable of realizing any arbitraryN×NpermutationPin two passes, such that any source–destination path is set up in a single pass, no recirculation is needed, but the whole set ofNsource–destination paths ofPis partitioned in two subsets and are realized in two successive passes. We propose an algorithm that will detect if the switch fault set present in aB(n), belongs to this class; if it is yes, we present another algorithm that computes the fault-tolerant routing to realize any arbitrary permutationPin two passes. This scheme enables us to makeB(n) fault-tolerant in the presence of a restricted class of multiple switch faults, without any recirculation through intermediate nodes, or any reconfiguration of the system.     

A Simple Optimal Parallel Algorithm for a Core of a Tree

A core of a tree T = (V, E) is a path in T which minimizes ∑_vVd(v, P), where d(v, P), the distance from a vertex v to path P, is defined as min_uPd(v, u). We present an optimal parallel algorithm to find a core of T in O(log n) time using O(n/log n) processors on an EREW PRAM machine, where n is the number of vertices of tree T.     

A generalization of concavity for finite differences

The concept of concavity is generalized to discrete functions, u, satisfying the n^th-order difference inequality, (−1)^n−kΔⁿu(m) ≥ 0, M = 0, 1,..., N and the homogeneous boundary conditions, u(0) = … = u(k−1) = 0, u(N + k + 1) = … = u(N + n) = 0 for some k “1, …, n − 1”. A piecewise polynomial is constructed which bounds u below. The piecewise polynomial is employed to obtain a positive lower bound on u(m) for m = k, …, N + k, where the lower bound is proportional to the supremum of u. An analogous bound is obtained for a related Green's function.     

Selection, Routing, and Sorting on the Star Graph

We consider the problems of selection, routing, and sorting on ann-star graph (withn! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a “(k, 1,k) chain network”) of the star graph which enables us to design efficient algorithms for the above mentioned problems. We present an algorithm that performs a sequence ofnprefix computations inO(n²) time. This algorithm is used as a subroutine in our other algorithms. We also show that sorting can be performed on then-star graph in timeO(n³) and that selection of a set of uniformly distributednkeys can be performed inO(n²) time with high probability. Finally, we also present a deterministic (nonoblivious) routing algorithm that realizes any permutation inO(n³) steps on then-star graph. There exists an algorithm in the literature that can perform a single prefix computation inO(nlgn) time. The best-known previous algorithm for sorting has a run time ofO(n³lgn) and is deterministic. To our knowledge, the problem of selection has not been considered before on the star graph.     

Routing on Meshes with Buses

We consider the problem of routing packets on an MIMD mesh-connected array of processors augmented with row and column buses. We give lower bounds and randomized algorithms for the problem of routing k-permutations (where each processor is the source and destination of exactly k packets) on a d-dimensional mesh with buses, which we call the (k,d)-routing problem. We give a general class of ``hard' permutations which we use to prove lower bounds for the (k,d)-routing problem, for all k,d≥ 1. For the (1,1)- and (1,2)-routing problems the worst-case permutations from this class are identical to ones published by other authors, as are the resulting lower bounds. However, we further show that the (1,d)-routing problem requires 0.72 ... n steps for d=3, 0.76 ... n steps for d=4, and slightly more than steps for all d≥ 5. We also obtain new lower bounds for the (k,d)-routing problem for k,d > 1, which improve on the bisection lower bound in some cases. These lower bounds hold for off-line routing as well. We develop efficient algorithms for the (k,1)-routing problem and for the problem of routing k-randomizations (where each processor has k packets initially and each packet is routed to a random destination) on the one-dimensional mesh and use them in a general (k,d)-routing algorithm which improves considerably on previous results. In particular, the routing time for the (1,d)-routing problem is bounded by steps with high probability (whp), whenever for some constant ε > 0, and the routing time for the (k,d)-routing problem is steps whp whenever for some constant ε > 0 and k≥ 3.6 ... d, matching the bisection lower bound. We then present a simple algorithm for the (2,2)-routing problem running in 1.39 ... n+o(n) steps whp. Finally, for the important special case of routing permutations on two-dimensional meshes with buses, the (1,2)-routing problem, we give a more sophisticated algorithm that runs in 0.78 ... n+o(n) steps whp. Received May 18, 1994; revised June 23, 1995.     

Universal stabilization of a class of nonlinear systems with homogeneous vector fields

Under relative-degree-one and minimum-phase assumptions, it is well known that the class of finite-dimensional, linear, single-input (u), single-output (y) systems (A,b,c) is universally stabilized by the feedback strategy u = Λ(λ)y, λ = y², where Λ is a function of Nussbaum type (the terminology “universal stabilization” being used in the sense of rendering /s(0/s) a global attractor for each member of the underlying class whilst assuring boundedness of the function λ(·)). A natural generalization of this result to a class ^k of nonlinear control systems (a,b,c), with positively homogeneous (of degree k 1) drift vector field a, is described. Specifically, under the relative-degree-one (cb ≠ 0) and minimum-phase hypotheses (the latter being interpreted as that of asymptotic stability of the equilibrium of the “zero dynamics”), it is shown that the strategy u = Λ(λ)/vby/vb^k−1y, assures ^k-universal stabilization. More generally, the strategy u = Λ(λ)exp(/vby/vb)y, assures -universal stabilization, where = _{k 1} ^k.