45794294
Embedding K-ary Complete Trees into Hypercubes
Abstract In this paper, dilated embedding and precise embedding of K-ary complete trees into hypercubes are studied. For dilated embedding, a nearly optimal algorithm is proposed which embeds a K-ary complete tree of height h, TK(h), into an (h − 1)[log K] + [log (K + 2)]-dimensional hypercube with dilation Max{2, φ(K), φ(K + 2)}. φ(x) = min{λ: Σλi=0Cid ≥ x and d = [log x]}. It is clear that [([log x] + 1)/2] ≤ φ(x) ≤ [log x], for x ≥ 3.) For precise embedding, we show a (K − 1)h + 1-dimensional hypercube is large enough to contain TK(h) as its subgraph, K ≥ 3.
33412339
Conservative Algorithms for Parallel and Sequential Integer Sorting
We present a conservative CRCW parallel algorithm for integer sorting. This algorithm sorts n integers from {0, 1, ..., m−1} in time O(n log log min(m,n)/p + log n) using p processors. The simulation of our parallel algorithm on the sequential machine yields a sequential algorithm for integer sorting which sorts n integers from {0, 1, ..., m−1} in time O(n min(log log n, log log m/log n)).
45976743
Improved lightpath (wavelength) routing in large WDM networks
We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. We first present fast, efficient algorithms both for the general problem and for a natural restricted version. The new algorithms outperform earlier work, providing time improvements amounting to an almost linear time factor in most cases. Also, all our algorithms can be implemented on the network in a distributed way.
34776029
Embedding between 2-D meshes of the same size
It is shown how to embed an x/sub 1/ /spl times/ 1/sub 1/ mesh M/sub 1/ into an s/sub 2/ /spl times/ t/sub 2/ mesh M/sub 2/, where s/sub 1/ /spl times/ t/sub 2/, s/sub 1/ < t/sub i/ (i = 1,2) such that the dilation is minimized. It is assumed that load = 1 and expansion = 1. For each case there is shown a lower bound on the dilation and a corresponding embedding method. The dilations by these embedding algorithms either match a lower bound or are very close to a lower bound.<<ETX>>
9442074
Generalized Latin squares II
Abstract This paper is a continuation of a study on a new class of combinatorial structures called generalized Latin squares or 〈k,l〉-Latin squares. Here, we study the existence question of perfect 〈k,l〉-Latin squares. The main result is an existence theorem for the case M = 2, where M is the multiplicity of the generalized Latin squares. Specifically, we show that for given positive integers N, k = ip, l = iq, where i = gcd(k,l), there exists a perfect 〈k,l〉-Latin square of order N with M = 2 if and only if (i) N = 4k, (ii) pq(p + q)| N, and (iii) q|2.
44324303
Equivalent permutation capabilities between time division optical omega network and non-optical extra stage omega network
Since optical networks must support crosstalk-free (CF) connections, regular N/spl times/N multistage interconnection networks (MINs) cannot be directly used to provide connections between N inputs and N outputs. A solution is to use a 2N/spl times/2N Cube-Type MIN to provide the N/spl times/N connections. C. Qiao (1993) proposed a time domain approach that divides the N optical inputs into several groups such that CF connections can be provided by an N/spl times/N regular MIN in several time slots, one for each group. The set of N-permutations realizable in two slots is defined as class /spl theta/. Qiao proved that the size of /spl theta/ is larger than the size of class /spl Omega/, where /spl Omega/ consists of all N-permutations passible through a regular N/spl times/N Omega network. The paper first presents an optimal O(NlgN) time algorithm for identifying whether a given permutation belongs to class /spl theta/ or not. From this algorithm, the paper proves an interesting fact that the class /spl theta/ is identical to the class /spl Omega/+1 which represents the set of N-permutations admissible by a non-optical N/spl times/N one-extra stage Omega network.
33166016
Indirect RSVP for Virtual Cluster Cellular Mobile IP Networks
Mobile IP (MIP) could be deployed in a wireless cellular network so that the integrated Cellular Mobile IP (CMIP) network can be used to support datagram delivery to mobile users. In order to provide QoS for realtime traffic in IP network, Resource reSerVation Protocol (RSVP) is needed to reserve network resources along the route which the datagrams follow. However, current RSVP fails to operate through the MIP tunnel. Moreover, the high registration rate in a CMIP network greatly degrades RSVP performance. In this paper, an Indirect RSVP (IRSVP) over Virtual Cluster Cellular Mobile IP (VCCMIP) is proposed in which an assistant RSVP connection is introduced to assist the end-to-end major RSVP operation over the MIP tunnel. IRSVP signaling costs and packet loss rates are evaluated. Simulation results show that the proposed scheme can greatly increase RSVP performance in terms of packet loss and RSVP connection active percentage.
768133
Performance analysis of TCP-friendly AIMD algorithms for multimedia applications
In this paper, the performance of TCP-friendly generic AIMD (Additive Increase and Multiplicative Decrease) algorithms for Web-based playback and multirate multimedia applications is investigated. The necessary and sufficient TCP-friendly condition is derived, and the effectiveness and responsiveness of AIMD are studied. Due to practical implications, a Dynamic TCP-friendly AIMD (DTAIMD) algorithm is proposed. Extensive simulation results are given to verify the derived necessary and sufficient condition, and to demonstrate the performance of the proposed DTAIMD algorithm.
39945401
End-to-end TCP Performance with Local Retransmissions
12254119
Wireless network security
410513
Active Feedback - UIUC TREC-2003 HARD Experiments
In this paper, we report our experiments on the HARD (High Accuracy Retrieval from Documents) Track in TREC 2003. We focus on active feedback, i.e., how to intelligently propose questions for relevance feedback in order to maximize accuracy improvement in the second run. We proposed and empirically evaluated three different methods, i.e., top-k, gapped top-k, and k-cluster centroid, to extract a fixed number of text units (e.g. passage or document) for feedback. The results show that presenting the top k documents for user feedback is often not as beneficial for learning as presenting more diversified documents.