Fat trees are considered suitable structures for data center interconnection networking. Such structures are rigid, and hard to scale up and scale out. A good data center network structure should have high scalability, efficient switch utilization, and high reliability. In this paper we present a class of data center network structures based on hypergraph theory and combinatorial block design theory. We show that our data center network structures are more flexible and scalable than fat trees. Using switches of the same size, our data center network structures can connect more nodes than fat trees, and it is possible to construct different structures with tradeoffs among inter-cluster communication capacity, reliability, the number of switches used, and the number of connected nodes.

Fat trees are considered suitable structures for data center interconnection networking. Such structures are rigid, and hard to scale up and scale out. A good data center network structure should have high scalability, efficient switch utilization, and high reliability. In this paper we present a class of data center network structures based on hypergraph theory and combinatorial block design theory. We show that our data center network structures are more flexible and scalable than fat trees. Using switches of the same size, our data center network structures can connect more nodes than fat trees, and it is possible to construct different structures with trade-offs among inter-cluster communication capacity, reliability, the number of switches used, and the number of connected nodes.

In the previous papers, we presented a new mesh of trees based switch architecture, denoted as MOTS (N) switch, along with its variations IMOTS (N) and IMOTS-CT (N) switches. The analysis and simulation results were presented that all of them achieve 100% throughput and the mean cell delay of IMOTS-CT (N) is comparable to that of OQ switch with FIFO queues (FIFO-OQ). Especially, IMOTS-CT (N) was proposed for a way to reduce mean cell delay of IMOTS (N). In this paper, we propose advanced IMOTS (N), denoted as AIMOTS (N), with token based scheduling algorithm of it. It shows a way to reduce hardware complexity of IMOTS (N) and IMOTS-CT (N). Quantitative simulation results are presented to compare AMOTS (N) switch with others.

Resource allocation and job scheduling are the core functions of grid computing. These functions are based on adequate information of available resources. Timely acquiring resource status information is of great importance in ensuring overall performance of grid computing. This work aims at building a distributed system for grid resource monitoring and prediction. In this paper, we present the design and evaluation of a system architecture for grid resource monitoring and prediction. We discuss the key issues for system implementation, including machine learning-based methodologies for modeling and optimization of resource prediction models. Evaluations are performed on a prototype system. Our experimental results indicate that the efficiency and accuracy of our system meet the demand of online system for grid resource monitoring and prediction.

We recently proposed an innovative agile crossbar switch architecture called contention-tolerant crossbar (CTC(N)) and its generalization multi-layer CTC(N) (MCTC(N)) switch. In this paper, we propose several generalizations of CTC(N), including SCTC(N, n) (sparse CTC), SMCTC(N, n) (sparse multi-layer CTC) and MSCTC(N, n) (multi-layer sparse CTC). Through analysis and simulations, we show that these generalizations maintain the same performance of their counterparts CTC(N) and MCTC(N), while reducing the cost from O(N2) to O(N log N).

We recently proposed an innovative agile crossbar switch architecture called contention-tolerant crossbar (CTC(N)) switch, which can tolerate output contentions by a pipelining mechanism, with pipeline stages implemented as buffers in the input ports. These buffers are used to decouple the scheduling task into N independent parts in such a way that N schedulers are located in the N input ports, and they operate independently and in parallel without using any arbiter. In this paper, we present a simple fully distributed scheduling algorithm scheme and show its effectiveness by simulations.

We propose an innovative agile crossbar switch architecture called contention-tolerant crossbar, denoted by CTC(N). Unlike the conventional crossbar and the crossbar with crosspoint buffers, which require complex hardware resolvers to grant one out of multiple output requests, CTC(N) can tolerate output contentions by a pipelining mechanism, with pipeline stages implemented as buffers in input ports. These buffers are used to decouple the scheduling task into N independent parts in such a way that $N$ schedulers are located in N input ports, and they operate independently and in parallel. Without using arbiters and/or crosspoint buffers that require additional chip area, the CTC(N) switch is more scalable than existing crossbars. We analyze the throughput of CTC(N) switch without and with internal speedup by building a queuing model. We show that, under Bernoulli i.i.d. uniform traffic, CTC(N) without internal speedup has worst-case throughput of 63%, and CTC(N) achieves 100% throughput with internal speedup 2. Our simulation results validate our theoretical analysis.

Distributors, also known as multicast switching networks, support one-to-many communications. Known wide-sense nonblocking distributors are either having high costs or not efficiently routable. We present a wide-sense nonblocking distributor of O(N\log N) cost, O(\log N) diameter, O(N\log N) control cost, and O(\log N) routing time. This is the first wide-sense nonblocking distributor that is optimal in all four aspects.

In communication networks, multiple disjoint communication paths are desirable for many applications. Such paths, however, may not exist in a network. In such a situation, paths with minimum link and/or node sharing may be considered. This paper addresses the following two related fundamental questions. First, in case of no solution of disjoint multiple paths for a given application instance, what are the criteria for finding the best solution in which paths share nodes and/or links? Second, if we know the criteria, how do we find the best solution? We propose a general framework for the answers to these two questions. This framework can be configured in a way that is suitable for a given application instance. We introduce the notion of link shareability and node shareability and consider the problem of finding minimum-cost multiple paths subject to minimum shareabilities (MCMPMS problem). We identify 65 different link/node shareability constraints, each leading to a specific version of the MCMPMS problem. In a previously published technical report, we prove that all the 65 versions are mutually inequivalent. In this paper, we show that all these versions can be solved using a unified algorithmic approach that consists of two algorithm schemes, each of which can be used to generate polynomial-time algorithms for a set of versions of MCMPMS. We also discuss some extensions where our modeling framework and algorithm schemes are applicable.

In recent years, many researchers have investigated optical interconnections as parallel computing. Optical interconnections are attractive due to their high bandwidth and concurrent access to the bus in a pipelined fashion. The Linear Array with Reconfigurable Pipelined Bus System (LARPBS) model is a powerful optical bus system that combines both the advantages of optical buses and reconfiguration. To increase the scalability of the LARPBS model, we propose a two-dimensional extension: a simplified two-dimensional Array with Reconfigurable Pipelined Bus System (2D ARPBS). While achieving better scalability, we show the effectiveness of this newly proposed model by designing two novel optimal sorting algorithms on this model. The first sorting algorithm is an extension of Leighton's seven-phase columnsort algorithm that eliminates the restriction of sorting only an r \times s array, where r \ge s^2 , and sorts an n \times n array in O(\log n) time. The second one is an optimal multiway mergesort algorithm that uses a novel processor efficient two-way mergesort algorithm and a novel multiway merge scheme to sort n^2 items in O(\log n) time. Using an optimal sorting algorithm Pipelined Mergesort designed for the LARPBS model as a building block, we extend our research on parallel sorting on the LARPBS to a more scalable 2D ARPBS model and achieve optimality in both sorting algorithms.

Light-trail is proposed as a candidate to carry IP traffic over wavelength division multiplexing (WDM) optical networks given its capability of accommodating multi-granularity traffic by time-division multiplexing (TDM). Light-trail's unidirectional shared-media multicast nature makes it hard to implement distributed access control and restricts that at most one packet transmission can take place at any time. Recently, opportunistic optical hyperchannel was proposed to improve light-trail by permitting easy distributed access control. In this paper, we propose a set of distributed access control protocols, namely, 1-persistent protocols, for opportunistic optical hyperchannels to maximize the throughput and provide fair service among contending nodes by taking their inherent advantage of adaptive space-division multiplexing (SDM). We also point out a possible generalization of opportunistic optical hyperchannels by removing the restriction of linear structure, and demonstrate possible applications of such a generalization.

Light-trail is proposed as a candidate to carry IP traffic over wavelength-division multiplexing optical networks given its capability of enabling high-speed provisioning and accommodating multigranularity traffic. In a light-trail, the optical shutters at the start node and the end node are configured to be in OFF state and the optical shutters at the intermediate nodes are configured to be in ON state. Thus, an optical bus is formed, allowing traffic multiplexing without the state change of any optical shutter. This, however, limits the system throughput and also makes it impossible to implement a fully distributed medium access control (MAC) protocol to assure quality of service (QoS) in a light-trail. With the recent development on ultrafast optical shutter, we propose an improved light-trail architecture, called opportunistic hyperchannel in this paper. In an opportunistic hyperchannel, an intermediate node can dynamically control its optical shutter which makes it possible to design a fully distributed QoS assuring MAC protocol. We then present a QoS assuring distributed dynamic scheduling protocol, namely, minimum source round robin (minSrcRR) protocol, for opportunistic hyperchannels. Theoretical analysis on the effectiveness of the proposed QoS assuring protocol and the worst-case delay bound are also derived in this paper. The simulation results quantitatively demonstrate the advantage of opportunistic hyperchannels and the effectiveness of minSrcRR protocol.

Opportunistic hyperchannel was proposed as an improvement of light-trail to carry IP traffic over wavelength division multiplexing (WDM) optical networks given its capability of enabling high speed provisioning and accommodating multi- granularity traffic. In an opportunistic hyperchannel, the optical shutters at the start node and the end node are configured to be in OFF state and the optical shutters at the intermediate nodes can be self-adjusted to be in ON/OFF according to actual traffic. With this ability, an opportunistic hyperchannel can be dynamically divided into multiple segments, and each segment can independently accommodate a request. Thus, an opportunistic hyperchannel can amplify the system throughput. In this paper, we present a centralized dynamic scheduling protocol named prioritized maximum independent set (PMIS), and introduce a data structure called 2-dimensional priority search tree (2D-PST) that supports PMIS. With 2D-PST, one round of PMIS can be carried out in O(k . log n . log m) time to maximize the system throughput under the constraint of assuring quality of service (QoS) for opportunistic hyperchannels. The simulation results quantitatively demonstrate the effectiveness of PMIS protocol.

Search engine is a critical component in several stages of a pipeline flow in high-performance IP routers. To achieve high performance, it has been proposed to use TCAMs to implement search engines in hardware. In this paper, the state- of-art TCAM-based MSMB-LPT scheme is used as an example to show how to introduce pipelining into TCAM-based search by presenting pipelined scheme P-MSMB-LPT. It is shown that P-MSMB-LPT eliminates the unnecessary hazard that exists in the MSMB-LPT scheme, and achieves near-optimal speedup with almost no additional hardware overhead.

In communication networks, multiple communication paths sharing minimum number of links or/and nodes may be desirable for improved performance, resource utilization and reliability. We introduce the notion of link sharability and node sharability, and consider the problems of finding minimum-cost k paths subject to minimum link/node sharability constraints. We identify 65 different link/node sharability constraints, and consider the fundamental problem of finding minimum-cost k paths between a pair of nodes under these constraints. We present a unified polynomial-time algorithm scheme for solving this problem subject to 25 of these different sharability constraints.

Fast and accurate recognition of motion data streams from gesture sensing and motion capture devices has many applications and is the focus of this article. Based on the analysis of the geometric structures revealed by singular value decompositions (SVD) of motion data, a similarity measure is proposed for simultaneously segmenting and recognizing motion streams. A direction identification approach is explored to further differentiate motions with similar data geometric structures. Experiments show that the proposed similarity measure can segment and recognize motion streams of variable lengths with high accuracy, without knowing beforehand the number of motions in a stream.

Abstract — Clos networks are an important class of switching networks due to their modular structure and much lower cost compared with crossbars. For routing I/O permutations of Clos networks, sequential routing algorithms are too slow, and all known parallel algorithms are not practical. We present the algorithm-hardware codesign of a unified fast parallel routing architecture called distributed pipelining routing (DPR) architecture for rearrangeable nonblocking and strictly nonblocking Clos networks. The DPR architecture uses a linear interconnection structure and processing elements that performs only shift and logic AND operations. We show that a DPR architecture can route any permutation in rearrangeable nonblocking and strictly nonblocking Clos networks in ¦¨§� © �� � steps. The same architecture can be used to carry out control of any group of connection/disconnection requests for strictly nonblocking Clos networks in ¦¨ § © ��� steps. Several speeding-up techniques are also presented. This architecture is applicable to packet and circuit switches of practical sizes. Index Terms: Clos network, permutation routing, circuit switching, packet switching, rearrangeable nonblocking,

A new scalable optical network infrastructure SMART is proposed based on light-trails and hypernetwork architecture. The underlying physical network of SMART is a reconfigurable WDM network with reconfigurability distributed over network nodes. The reconfigurable node architecture is capable of dynamically setting up, modifying, and tearing down connections that consist of multi-access hyperchannels, which are an extension of light-trails. Like light-trails, hyperchannels are used to efficiently utilize bandwidth in subwavelength granularity. Hyperchannels and hyperpaths (hybrid connection paths) make SMART scalable. Equipped with a menu of switching techniques and connection types, SMART is able to manage optimized connections, and enforce individual service qualities and overall network performance. SMART network combines the best features of optics and electronics, making the network highly intelligent. Various virtual networks can be easily constructed over SMART. SMART encompasses the best features of existing mature electrical and optical network technologies, making these technologies as special cases. SMART is evolvable with backward compatibility. SMART is customizable for constructing LANs, MANs and WANs, and for access and transport. SMART provides an excellent alternative for the next generation Internet.

A new rearrangeable nonblocking photonic multi- log2N network DM(N) is introduced. It is shown that DM(N) network simultaneously possesses many good properties, including those of existing rearrangeable nonblocking multi-log2N networks and new ones such as O (log N) -time fast parallel self-routing and nonblocking multiple-multicast.

Trains as a mass transport system are a strong application case for coarsely granular bandwidth-on-demand networking. Multiple trains time-sharing the same track, traveling at a significant speed and containing a large number of bandwidth savvy users represents a premier motivation for the merger of optical and wireless communications. Wireless delivery methods alone cannot suffice the need for such a large moving mass of bandwidth intensive users. We propose a method to efficiently integrate a wireless network over a flexible optical backbone. The proposed method is built upon the light-trails optical platform and involves a unique control layer that adapts to an overlaid wireless network. Here, we propose a cross-layer protocol that enables seamless communication for these "light-trains". We also show benefits in terms of throughput, end-to-end delay, bandwidth efficiency and scalability of such a scheme through a simulation study.

In this paper, we propose a scalable multicast protection scheme based on a dual-homing architecture where each destination host is connected to two edge routers. Under such an architecture, there are two paths from the source of a multicast session to each destination host, which provides a certain level of protection for the data traffic from the source to the destination host. The protection level varies from 0 percent to 100 percent against a single link failure, depending on the number of shared links between these two paths. The major advantage of the proposed scheme lies in its scalability due to the fact that the protection is provided by constructing a dual-homing architecture at the access network while keeping the routing protocols in the core network unchanged. The selection of dual edge routers plays an important role in enhancing the protection level. Two problems arise for the proposed dual-homing partial multicast protection scheme. One is to calculate the survivability from the source to any pair of edge routers. The other is to assign a pair of edge routers for each destination host such that the total survivability is maximized for the multicast session subject to the port number constraint of each edge router. We propose an optimal algorithm to solve the first problem. We prove the decision version of the second problem is NP-complete and propose two heuristic algorithms to solve it. Simulation results show that the proposed heuristic algorithms achieve performance close to the calculated lower bound

Efficient recognition of haptic data such as 3D motion capture data and sign language sensory data can have wide applications in the interactive computer animation and sign language automatic translation areas. For this purpose, we propose a similarity measure for multi-attribute haptic data, a new form of multimedia signal. The proposed similarity measure, based on singular value decomposition, captures the most important features of the signal data, allows for different signal generating rates and reasonable variations in similar signals. Experiments with real life and synthetic data demonstrate that the proposed similarity measure can capture the similarities of motions with different speeds and different lengths and can have up to 100% recognition rates.

Switching networks are widely used as core components in network switches and routers, and communication subsyetems in parallel computing systems. Most switching networks are multistage interconnection networks built with small-size switching elements. Nonblocking switching networks have been favored because of their capability of setting up any one-to-one I/O connections. There are three types of nonblocking networks: strictly nonblocking (SNB), wide-sense nonblocking(WSNB) and rearrangeable nonblocking (RNB). In both SNB and WSNB networks, a connection can be established from any idle input to any idle output without disturbing existing connections. In SNB networks any of available conflict-free paths for a connection can be chosen and inWSNB networks, however, a rulemust be followed to choose one. The high degree of connection capability in SNB and WSNB networks is at a high hardware cost. RNB networks, usually constructed with lower hardware cost, can establish a conflict-free path for the connection from any idle input to any idle output if the rearrangement of existing connections is allowed. Large-scale SNB and WSNB switching networks, which are suitable for circuit switching, are usually infeasible in practice due to their high cost. In contrast, rearrangeable networks are more scalable because of their much lower cost. However, rearrangeable networks are not suitable for circuit switching. Over the years, a rich theory of nonblocking switching networks has been developed. Unfortunately, no explicitly constructable optimal-cost SNB and WSNB network has been discovered. Known powerful nonblocking networks are either costly and unscalable, or very inefficient in routing connections. In this talk, we introduce the the notion of virtual nonblockingness and almost nonblockingness, and the concepts of virtual nonblocking (VNB) networks and almost nonblocking (ANB) networks.

Web caching is an important technology for improving the scalability of Web services. One of the key problems in coordinated enroute Web caching is to compute the locations for storing copies of an object among the enroute caches so that some specified objectives are achieved. In this article, we address this problem for tree networks, and formulate it as a maximization problem. We consider this problem for both unconstrained and constrained cases. The constrained case includes constraints on the cost gain per node and on the number of object copies to be placed. We present dynamic programming-based solutions to this problem for different cases and theoretically show that the solutions are either optimal or convergent to optimal solutions. We derive efficient algorithms that produce these solutions. Based on our mathematical model, we also present a solution to coordinated enroute Web caching for autonomous systems as a natural extension of the solution for tree networks. We implement our algorithms and evaluate our model on different performance metrics through extensive simulation experiments. The implementation results show that our methods outperform the existing algorithms of either coordinated enroute Web caching for linear topology or object placement (replacement) at individual nodes only.

We study the connection capacity of a class of rearrangeable nonblocking (RNB) and strictly nonblocking (SNB) networks with/without crosstalk-free constraint, model their routing problems as weak or strong edge-colorings of bipartite graphs, and propose efficient routing algorithms for these networks using parallel processing techniques. This class of networks includes networks constructed from banyan networks by horizontal concatenation of extra stages and/or vertical stacking of multiple planes. We present a parallel algorithm that runs in O(lg/sup 2/ N) time for the RNB networks of complexities ranging from O(N lg N) to O(N/sup 1.5/ lg N) crosspoints and parallel algorithms that run in O(min{d* lg N, /spl radic/N}) time for the SNB networks of O(N/sup 1.5/ lg N) crosspoints, using a completely connected multiprocessor system of N processing elements. Our algorithms can be translated into algorithms with an O(lg N lg lg N) slowdown factor for the class of N-processor hypercubic networks, whose structures are no more complex than a single plane in the RNB and SNB networks considered.

Nonblocking interconnection networks are always favored to be used as switching networks whenever possible. The crosstalk-free requirement in photonic networks adds a new dimension of constraints for nonblockingness. Routing algorithms play a fundamental role in nonblocking networks, and any algorithm that requires more than linear time would be considered too slow for real-time applications. One remedy is to use multiple processors to route connections in parallel and the other is to construct cost effective self-routing nonblocking networks. We propose a new class of self-routing strictly nonblocking networks by studying the connection capacity of banyan-type networks. Compared with existing strictly nonblocking self-routing networks, the presented new networks have lower hardware cost, shorter connection diameter, and much smaller number of required wavelengths. Consequently, they are more feasible for implementation with reduced optical signal attenuation and crosstalk.

Due to its simplicity and scalability, the differentiated services (DiffServ) model is expected to be widely deployed across the Internet. For each DiffServ compliant router, the scheduling algorithm is critical in implementing per hop behaviors (PHBs), according to which packets are forwarded. We propose a hierarchical DiffServ scheduling (HDS) algorithm to support DiffServ classes on input-queued switches. The proposed HDS algorithm features in a hierarchical scheduling scheme that consists of two levels of schedulers. One level is the central scheduler which is designed to maximize the switch throughput by computing a maximal size matching between input ports and output ports. The other level is formed by input port schedulers which provide differentiated services by serving cells belonging to different classes dynamically. Using such a hierarchical scheme, the implementation complexity and the amount of information needed to be transmitted between input ports and the central scheduler are dramatically reduced compared with existing maximal weight matching based DiffServ scheduling algorithms. The tradeoff of its slightly worse delay performance is acceptable.

A new class of interconnection networks called group connectors are introduced. A group connector G (N,n) is a switching network that consists of N inputs and N outputs such that (1) its N outputs are divided into N/n groups with n outputs in each group, and (2) it can provide any simultaneous one-to-one connections from the N inputs to the N outputs, possibly without the ability of distinguishing the permutation of the outputs within each group. Note that a group connector is able to distinguish among groups of outputs. Group connectors has applications in the switching matrices in dense wavelength-division multiplexing (DWDM) networks. Clearly, an N /spl times/ N permutation network can be used as an N /spl times/ N group connector. We show that a group connector can be built at a lower hardware cost than that of a permutation network of the same size.

Multistage interconnection networks (MINs) are among the most efficient switching architectures in terms of the number of switching elements (SEs) used. For optical MINs (OMINs), two I/O connections with neighboring wavelengths cannot share a common SE due to crosstalk. In this paper, we focus on the wavelength dilation approach, in which the I/O connections sharing a common SE will be assigned different wavelengths with enough wavelength spacing. We first study the permutation capacity of OMINs, then propose fast parallel routing and wavelength assignment algorithms for OMINs. By applying our permutation decomposition and graph coloring techniques, the proposed algorithms can route any permutation without crosstalk in wavelength-rearrangeable space-strict-sense Banyan networks and wavelength-rearrangeable space-rearrangeable Benes networks in polylogarithmic time using a linear number of processors.

Summary form only given. Nonblocking multistage interconnection networks are favored to be used as switching networks whenever possible. Crosstalk-free requirement in photonic networks adds a new dimension of constraints for nonblockingness. Routing algorithms play a fundamental role in nonblocking networks, and any algorithm that requires more than linear time would be considered too slow for real-time applications. One remedy is to use multiple processors to route connections in parallel. In this paper, we study the connection capacity of a class of rearrangeable nonblocking and strictly nonblocking networks with/without crosstalk-free constraint, model their routing problems as weak or strong edge colorings of bipartite graphs, and propose efficient routing algorithms for these networks using parallel processing techniques.

In this work, we focus on fast and efficient recognition of motions in multi-attribute continuous motion sequences. 3D motion capture data, animation motion data, and sensor data from gesture sensing devices are examples of multi-attribute continuous motion sequences. These sequences have multiple attributes rather than only one attribute as time series data has. Motions can have different rates and durations, and the resulting data can thus have different lengths. Also, motion data can have noises due to transitions between successive motions. Hence, traditional distance measuring approaches used for time series data (such as Euclidean distances or dynamic time-warped distances) are not suitable for recognition in multi-attribute motion sequences. Hence, we have defined a similarity measure based on the analysis of singular value decomposition (SVD) properties of similar multi-attribute motions. A five-phase algorithm has then been proposed that gives good pruning power by exploiting the proximity of continuous motion data. We experimented this algorithm with data from different sources: 3D motion capture devices, animation motions, and CyberGlove gesture sensing device. These experiments show that our algorithm can segment and recognize long motion streams with high accuracy and in real time without knowing beforehand the number of motions in a stream.

The classification problem transforms a set of N numbers in such a way that none of the first N/2 numbers exceeds any of the last N/2 numbers. A comparator network that solves the classification problem on a set of r numbers is commonly called an r-classifier. We show how the well-known Leighton's Columnsort algorithm can be modified to solve the classification problem of N=rs numbers, with 1 /spl les/ s /spl les/ r, using an r-classifier instead of an r-sorting network. Overall, the r-classifier is used O(s) times, namely, the same number of times that Columnsort applies an r-sorter. A hardware implementation is proposed that runs in optimal O(s+logr) time and uses an O(rlogr(s + logr)) work. The implementation shows that, when N= rlogr, there is a classifier network solving the classification problem on N numbers in the same O(logr) time and using the same O(rlogr) comparators as an r-classifier, thus saying a logr factor in the number of comparators over an (rlogr)-classifier.

Applications of stable matching in switch scheduling have been proposed. However, the classical GS (Gale and Shapley) stable matching algorithm is infeasible for high-speed implementation due to its high complexity. Instead, acyclic stable matching algorithms have been shown useful in implementing scheduling for high-speed switches/routers. We model the acyclic stable matching problem as the dominating set problem for a rooted dependency graph, and propose a parallel algorithm for finding the dominating set in O(n log n) time. We design and implement a scheduler based on the proposed algorithm in hardware. Simulation results show that the number of 2-input NAND gates and the timing of our design are proportional to n/sup 2/ and n respectively, making it feasible to implement the scheduler at high speed with current CMOS technologies.

Multistage interconnection networks (MINs) can be used to construct electro-optic switches. To implement crosstalk-free switching in such a switch, two I/O connecting paths cannot share a common switching element (SE). Thus, a permutation must be decomposed into partial permutations, each being routed through the switch without crosstalk. It was shown that any permutation can be decomposed into two semipermutations, and each is a maximum partial permutation realizable in one pass in an optical Benes network. However, the time complexity of existing decomposition algorithms for realizing connection requests is proportional to permutation size. In this paper, we reexamine the permutation capacity of MINs, present a simpler proof for semipermutation decomposability, and propose a parallel decomposition algorithm of logarithmic time. This algorithm is shown useful for optimally routing crosstalk-free paths in optical Benes networks in high-speed.

The diverse service requirements of emerging Internet applications faster the need for flexible and scalable IP quality-of-service (QoS) schemes. Due to its simplicity and scalability, DiffServ is expected to be widely deployed across the Internet. Though DiffServ supporting scheduling algorithms for output-queueing (OQ) switches have been widely studied, there are few DiffServ scheduling algorithms for input-queueing (IQ) switches. In this paper, we propose the dynamic DiffServ scheduling (DDS) algorithm for IQ switches to provide dynamic bandwidth allocation for DiffServ classes. The basic idea of DDS is to schedule EF and AF traffic according to their minimum service rates with the reserved bandwidth and schedule AF and BE traffic fairly with the excess bandwidth. We evaluate the performance of DDS under bursty traffic arrivals and compare it with PQWRR, an existing scheduling algorithm suitable for supporting DiffServ for OQ switches. Simulations results show that DDS provides minimum bandwidth guarantees for EF and AF traffic and fair bandwidth allocation for BE traffic. DDS also achieves the delay and jitter performance for EF traffic close to that of PQWRR and the delay performance for AF traffic better than that of PQWRR at high loads. Using comparator-tree based arbitration components, it is feasible to implement DDS in hardware at high speed.

Recently, CIOQ switches have attracted interest from both academic and industrial communities due to their ability of achieving 100% throughput and perfectly emulating OQ switch performance with a small speedup factor S. To achieve a speedup factor S, a conventional CIOQ switch requires the switch matrix and the memory to operate S times faster than the line rate. In this paper, we propose to use a CIOQ switch with space-division multiplexing expansion and grouped inputs/outputs (SDMG CIOQ switch for short) to achieve speedup while only requiring the switch matrix and the memory to operate at the line rate. The cell scheduling problem for the SDMG CIOQ switch is abstracted as a maximum bipartite k-matching problem. Using fluid model, we prove that any maximal size k-matching algorithm on an SDMG CIOQ switch with an expansion factor 2 can achieve 100% throughput assuming input arrivals satisfy the strong law of large numbers and no inputs/outputs are oversubscribed. We further propose an efficient and starvation-free maximal size k-matching scheduling algorithm, kFRR, for the SDMG CIOQ switch. Simulation results show that kFRR achieves 100% throughput with an expansion factor 2 under two SLLN traffic models, uniform traffic and polarized traffic, confirming our analysis.

In this paper, we propose new pipelined request-grant-accept (RGA) and request-grant (RG) maximal size matching (MSM) algorithms to achieve speedup in combined input and output queueing (CIOQ) switches. To achieve a speedup factor S, in the proposed pipelined RGA/RG MSM algorithms, we pipeline operations of finding S matching in S scheduling cycles based on the observation that all matched inputs/outputs will not be used in later iterations in the same scheduling cycle. We show that our pipelined RGA/RG MSM algorithms reduce the scheduling time constraint by SI/(I+S-1), where I is the number of iterations allowed in each scheduling cycle. Taking the example of pipelined PIM, we evaluate the performance of the proposed algorithms by simulation. Simulation results have shown that pipelined PIM for CIOQ switches with speedup of 2 under both Bernoulli and bursty arrivals.

DSP processors have gained more importance and popularity in implementing communication systems. Efficient implementation of logarithm and arctangent functions on DSP processors is necessary for applications such as digital receiver used in modern radar systems and digital communication systems. This paper presents a general scheduling and mapping optimization method based on grain packing to implement the two functions on TI TMS320C67X architecture with multiple parallel function units. Experimental results of our optimized implementation on TMS320C67x have achieved up to 79.5% performance improvement over TI C67x library functions. Our optimization method and techniques can also be applied to other DSP processors with parallel execution units.

Computing a distance map (distance transform) is an operation that converts a 2D image consisting of black and white pixels to an image where each pixel has a value or a pair of coordinates that represents the distance to or location of the nearest black pixel. It is a basic operation in image processing and computer vision fields, and is used for expanding, shrinking, thinning, segmentation, clustering, computing shape, object reconstruction, etc. This paper examines the possibility of implementing the problem of finding a distance map for an image efficiently using an optical bus. The computational model considered is the linear array with a reconfigurable pipelined bus system (LARPBS), which has been introduced recently based on current electronic and optical technologies. It is shown that the problem for an n /spl times/ n image can be implemented in O(log n log log n) bus cycles deterministically or in O(log n) bus cycles with high probability on an LARPBS with n/sup 2/ processors. We also show that the problem can be solved in O(log log n) bus cycles deterministically or in O(l) bus cycles with high probability on an LARPBS with n/sup 3/ processors. Scalability of the algorithms is also discussed briefly. The algorithm compares favorably to the best known parallel algorithms for the same problem in the literature.

The ubiquity of IP has led to IP-over-WDM as the core architecture for the next-generation optical Internet. Optical burst switching (OBS) has been proposed to be a competitive switching technology for DWDM networks. The data channel scheduling algorithm is one of the major challenges in OBS. The same-service-to-all model of the current Internet is inadequate for the diverse quality of service expectations of Internet applications and users. Differentiated service (DiffServ) was proposed to provide a scalable and manageable architecture for service differentiation in IP networks. This paper proposes a scheduling algorithm based on an existing LAUC-VF algorithm to support DiffServ and takes advantage of MPLS. Simulation results demonstrate that this algorithm has better QoS performance than the existing LAUC-VF algorithm.

Mesh-connected computers (MCCs) are a class of important parallel architectures due to their simple and regular interconnections. However, their performances are restricted by their large diameters. Various augmenting mechanisms have been proposed to enhance the communication efficiency of MCCs. One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). We propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). We compare IMMBs with MMBs and a class of previously proposed generalized MMBs (GMMBs). We show the power of IMMBs by considering semigroup and prefix computations. Specifically, as our main result we show that for any constant 0½×N½square IMMB using which semigroup and prefix computations on N operands can be carried out in O(Nε) time, while maintaining O(1) broadcasting time. Compared with the previous best complexities O(N⅛) and O(N1/16) achieved on a rectangular MMB and GMMB, respectively, for the same computations, our results show that IMMBs are more powerful than MMBs and GMMBs.

Various augmenting mechanisms have been proposed to enhance the communication efficiency of mesh-connected computers (MCCs). One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). In this paper, we propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). Each processor in an IMMB is connected to exactly two buses. We show the power of IMMBs by considering semigroup and prefix computations. Specifically, we show that semigroup and prefix computations on N operands, and data broadcasting all take O(log N) time on IMMBs. This is the first O(log N) time algorithm for these problems on arrays with fixed broadcasting buses.

We present a hardware-algorithm for sorting N elements using either a p-sorter or a sorting network of fixed I/O size p while strictly enforcing conflict-free memory accesses. To the best of our knowledge, this is the first realistic design that achieves optimal time performance, running in /spl Theta/(NlogN/plogp) time for all ranges of N. Our result completely resolves the problem of designing an implementable, time-optimal algorithm for sorting N elements using a p-sorter. More importantly, however, our result shows that, in order to achieve optimal time performance, all that is needed is a sorting network of depth O(log/sup 2/p) such as, for example, Batcher's classic bitonic sorting network.

(a, b)-trees are an important class of search trees. They include 2-3 trees, 2-3-4 trees, and B-trees as subclasses. We show that a space-minimum (a, b)-tree is also height-minimum and present an optimal algorithm for constructing (a, b)-trees that are height-minimum and space-minimum. Given n keys, our algorithm constructs an (a, b)-tree with minimum height and lowest possible nodes. Our algorithm takes /spl Theta/(n) time if the keys in S are sorted and /spl Theta/(n log n) time if the keys are not sorted. We also discuss possible applications of our algorithm.

Sorting networks of fixed I/O size p have been used, thus far, for sorting a set of p elements. Somewhat surprisingly, the important problem of using such a sorting network for sorting arbitrarily large datasets has not been addressed in the literature. Our main contribution is to propose a simple sorting architecture whose main feature is the pipelined use of a sorting network of fixed I/O size p to sort an arbitrarily large data set of N elements. A noteworthy feature of our design is that no extra data memory space is required, other than what is used for storing the input. As it turns out, our architecture is feasible for VLSI implementation and its time performance is virtually independent of the cost and depth of the underlying sorting network. Specifically, we show that by using our design N elements can be sorted in /spl Theta/(N/p log N/p) time without memory access conflicts. Finally, we show how to use an AT/sup 2/-optimal sorting network of fixed I/O size p to construct a similar architecture that sorts N elements in /spl Theta/(N/p log N/p log p) time.

We present efficient parallel matrix multiplication algorithms for linear arrays with reconfigurable pipelined bus systems (LARPBS). Such systems are able to support a large volume of parallel communication of various patterns in constant time. An LARPBS can also be reconfigured into many independent subsystems and, thus, is able to support parallel implementations of divide-and-conquer computations like Strassen's algorithm. The main contributions of the paper are as follows. We develop five matrix multiplication algorithms with varying degrees of parallelism on the LARPBS computing model; namely, MM/sub 1/, MM/sub 2/, MM/sub 3/, and compound algorithms C/sub 1/(/spl epsiv/)and C/sub 2/(/spl delta/). Algorithm C/sub 1/(/spl epsiv/) has adjustable time complexity in sublinear level. Algorithm C/sub 2/(/spl delta/) implies that it is feasible to achieve sublogarithmic time using /spl sigma/(N/sup 3/) processors for matrix multiplication on a realistic system. Algorithms MM/sub 3/, C/sub 1/(/spl epsiv/), and C/sub 2/(/spl delta/) all have o(/spl Nscr//sup 3/) cost and, hence, are very processor efficient. Algorithms MM/sub 1/, MM/sub 3/, and C/sub 1/(/spl epsiv/) are general-purpose matrix multiplication algorithms, where the array elements are in any ring. Algorithms MM/sub 2/ and C/sub 2/(/spl delta/) are applicable to array elements that are integers of bounded magnitude, or floating-point values of bounded precision and magnitude, or Boolean values. Extension of algorithms MM/sub 2/ and C/sub 2/(/spl delta/) to unbounded integers and reals are also discussed.

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G, our algorithm computes a maximum independent set of G in O(n) space and O(n) or O(n log n) time, depending on whether the endpoints of arcs in S are sorted or not. The proofs of the correctness and the complexities of the algorithm are straightforward, and the techniques used can be generalized to solve other problems on circular-arc graphs efficiently. © 1996 John Wiley & Sons, Inc.

We introduce a framework for a class of algorithms solving shortest path related problems, such as the one-to-one shortest path problem, the one-to-many shortest paths problem and the minimum spanning tree problem, in the presence of obstacles. For these algorithms, the search space is restricted to a sparse strong connection graph that is implicitly represented and its searched portion is constructed incrementally on-the-fly during search. The time and space requirements of these algorithms essentially depend on actual search behavior. Therefore, additional techniques or heuristics can be incorporated into search procedure to further improve the performance of the algorithms. These algorithms are suitable for large VLSI design applications with many obstacles.

We consider the problem of simulating linear arrays and rings on the multiply twisted cube. We introduce a new concept, the reflected link label sequence, and use it to define a generalized Gray Code (GGC). We show that GGCs can be easily used to identify Hamiltonian paths and cycles in the multiply twisted cube. We also give a method for embedding a ring of arbitrary number of nodes into the multiply twisted cube.

A modified tree architecture called the compressed tree machine is proposed, and it is shown the compressed tree machine can be an alternative to the conventional tree machine.>

A potential-driven approach to finding a rectilinear Steiner tree for a set of points on a planar grid is proposed. This approach has been implemented on a MasPar parallel processing system, and experimental results show its performance to be comparable with the best experimental results reported in the literature. Moreover, the method can be used for routing in grids with obstacles.>

We propose a class of new multiprocessor structures called bus based trees (BBTs) that are based on multiple buses. We show that a BBT can simulate a tree machine optimally. We also discuss optimal VLSI layouts for the BBT and show that the BBT can be used as a building block to construct new powerful parallel computing structures.

A general approach for the channel routing problem is presented as a framework for a class of heuristic routing algorithms. The algorithm is shown to possess a backtracking capability that increases the chance of completing the routing with a minimum number of tracks. Since the concepts described are general, they can be applied to other channel problems, such as switchbox routing, three-layer routing, and multilayer routing, or even to the overlap model, with only a few modifications. It is shown that track-oriented greedy algorithms can be modified to solve other channel routing problems. As examples, the algorithm is modified to solve the Manhattan switch-box problem and channel routing problems in the overlap and knock-knee models. Preliminary results show that the modified algorithms have good performance and show strong potential to outperform existing algorithms. Applying the algorithm MCRP-ROUT to the benchmark Deutsch's difficult problem and Burstein's difficult problem, routing solutions of 19 tracks and six tracks, respectively, were obtained.>

Let R be a rectangle uniformly partitioned by w-1 vertical line segments and h-1 horizontal line segments. The problem of routing through the rectangle, called the RRP problem (also referred to as the switch-box routing problem), is considered. It is denoted by I=(R, N), and consists of finding a layout under the knock-knee wiring model for the set N of nets inside R. The authors present a set of transformations different from the ones given by K. Mehlhorn et al. (Journal of ACM, vol.33, no.1, p.60-85, 1986) that provide smaller approximation bounds for the unrestricted RRP and the three-terminal-net RRP problems.>

We study the problem of partitioning a rectilinear polygon with interior points into rectangles by introducing a set of line segments. All points must be included in at least one of the line segments introduced and the objective function is to introduce a set of line segments such that the sum of their lengths is minimal. Since this problem is computationally intractable, we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within a fixed constant of the optimal solution value. Even though the constant approximation bound is not so small, we conjecture that in general the solutions our algorithms generate are close to optimal.