The increasing number of sophisticated malware poses a significant cybersecurity threat. Portable executable (PE) files are a common vector for such malware. We review and evaluate machine learning-based PE malware detection techniques in this work. Using a large benchmark dataset, we evaluate features of PE files using the most common machine- learning techniques to detect malware.

The Dempster-Shafer (DS) belief theory constitutes a powerful framework for modeling and reasoning with a wide variety of uncertainties due to its greater expressiveness and flexibility. As in the Bayesian probability theory, the DS theoretic (DST) conditional plays a pivotal role in DST strategies for evidence updating and fusion. However, a major limitation in employing the DST framework in practical implementations is the absence of an efficient and feasible computational framework to overcome the prohibitive computational burden DST operations entail. The work in this article addresses the pressing need for efficient DST conditional computation via the novel computational model DS-Conditional-All. It requires significantly less time and space complexity for computing the Dempster's conditional and the Fagin-Halpern conditional, the two most widely utilized DST conditional strategies. It also provides deeper insight into the DST conditional itself, and thus acts as a valuable tool for visualizing and analyzing the conditional computation. We provide a thorough analysis and experimental validation of the utility, efficiency, and implementation of the proposed data structure and algorithms. A new computational library, which we refer to as DS-Conditional-One and DS-Conditional-All (DS-COCA), is developed and harnessed in the simulations.

This work introduces a new technique for lossless compression of color images. The technique is composed of first transforming an RGB image into luminance and chrominance domain (Y CuCv). Then, the luminance channel Y is compressed with a context-based, adaptive, lossless image coding technique (CALIC). After processing the chrominance channels with a hierarchical prediction technique that was introduced by Kim and Cho, Burrows-Wheeler Inversion Coder (BWIC) or JPEG 2000 is used to compress of the chrominance channels Cu and Cv. It is demonstrated that, on a wide variety of images, particularly on medical images, the technique achieves substantial compression gains over other well-known compression schemes such as CALIC, JPEG 2000, LOCO-I, BPG(HEVC), and the previously proposed hierarchical prediction and context adaptive coding technique LCIC.

The Internet of Things (IoT) is an emerging paradigm, where the ubiquitous devices can form the networks and connect to Internet. Security and management of devices remain open challenges for the IoT. We adopt the management framework of industry consortium THREAD, where a group of devices cooperating to accomplish the same task (called policy) are administrated by a designated device called commissioner and together they form a policy group. All these policy groups are further managed by a centralized server. In this hierarchical network structure, the secure distribution of the policy information, access control, and group key from the centralized server to commissioner and its peers become challenging given the pervasive, complex and heterogeneous properties of devices. To solve this, we propose protocols/mechanisms along with a variant of Broadcast Encryption called Secure Identity-Based Broadcast Encryption (SIBBE) and demonstrate the feasibility for secure distribution of information to the IoT devices from centralized server. Most of the related work is based on the Attribute-based Encryption (ABE) for IoT devices, which has scalability issues with the number of attributes. Our experimental and simulation evaluations show that our scheme outperforms the existing schemes in terms of scalability, latency, and communication overhead.

Botnet threats include a plethora of possible attacks ranging from distributed denial of service (DDoS), to drive-by-download malware distribution and spam. While for over two decades, techniques have been proposed for either improving accuracy or speeding up the detection of attacks, much of the damage is done by the time attacks are contained. In this work we take a new direction which aims to predict forthcoming attacks (i.e. before they occur), providing early warnings to network administrators who can then prepare to contain them as soon as they manifest or simply quarantine hosts. Our approach is based on modelling the Botnet infection sequence as a Markov chain with the objective of identifying behaviour that is likely to lead to attacks. We present the results of applying a Markov model to real world Botnets' data, and show that with this approach we are successfully able to predict more than 98% of attacks from a variety of Botnet families with a very low false alarm rate.

A GPS system selects routes between two points with minimum physical distance or minimum driving time. Here we address a different type of route selection problem. Given a road map with driving distance and wireless connectivity for each road segment, find a driving route that maximizes total wireless connectivity while its length is bounded by a predetermined value. In this paper, we present three heuristic-algorithms. Initially they compute maximum connection-capacity shortest path for determining a bound for route length. The first algorithm (i) augments the road map by replacing each road segment with ratio of the distance of the road segment and its wireless communication capacity, and (ii) selects a route on the augmented map that satisfies route-length bound. The second algorithm assigns a penalty value to intersections based on their distance from a shortest path -- closer the intersection, higher the penalty. The algorithm selects among unexplored intersections one that has the minimum penalty value. The final algorithm utilize the first algorithm twice for selecting a route -- once to find distance and communication capacity of each intersection from the origin and then to find the same from the destination. Through extensive simulation of grid road networks it was found that on an average all three algorithms select routes that have higher communication capacity than any shortest paths. The most interesting observation is that the communication capacity gain is higher than the route length increase. For instance, when distance increase was bounded by 20%, on an average path selected by one algorithm was 11.4% longer than the length of the shortest path but connection capacity was about 32.5% higher than that of all shortest paths.

In general, automobiles travel from the origin to the destination using a shortest route. However, the shortest route may not be a highest wireless connection-capacity route, because of availability of wireless services (base station and access points etc.) along the route. To the best of our knowledge, currently no algorithm exists for selecting a route that maximizes wireless connection-capacity, while keeping route length shortest and close to shortest. In this paper, we propose two modified version of Dijkstra route selection algorithms: one for selecting a maximum connection capacity shortest route, and the other is for discovering higher wireless connection-capacity routes; the length of the route could be larger than a shortest route, but no larger than predetermined bound. The second proposed algorithm exploits the state change of the intersection to broaden the search range of possible routes. Results from our extensive simulation for a Manhattan-street type grid network with the heterogeneous IEEE 802.11a wireless access, show that for a 50% increase in route length and 15 Access Points (APs), the proposed algorithm can increases wireless connection-capacity by 35.67% and 31.27% compared to the shortest and random route selection algorithms, respectively.

In this paper, we propose a new transport protocol, theConcurrentMulti-PathReal-timeTransmissionControlProtocol(cmpRTCP), that has been designed to handle real-time streams (like video and audio) over IP-networks. cmpRTCP has been designed with a congestion controller and a real-time scheduler embedded in its core to intelligently exploit the availability of multiple paths between multi-homed hosts for concurrent transmission of unicast real-time streams. Experimental results show that this is a best effort protocol that tries to maximize the amount of data that is successfully delivered to the destination in a timely manner under varying drop and delay conditions of the network.

This paper describes a novel approach to represent the rate-distortion characteristics of an encoded media. This work is distinguished by three key contributions. The first is the introduction of the concept of data-rate PSNR information table (DRPIT), which facilitates for very fast packet scheduling during video streaming. Rate-distortion characteristic of the compressed video is extracted during preprocessing and is stored as DRPIT. The second contribution is an efficient algorithm to compute DRPIT during preprocessing, which decreases the computation time drastically. The algorithm exploits the acyclic dependency of the independently decodable units of the compressed packetized media. The third contribution consists of the application of DRPIT in variable rate video streaming systems. Two different types of systems are explained using two specific implementations which are also used for performance validation of the proposed approach. Experimental results demonstrate that the systems using DRPIT provide 6-10 dB gain, relative to the systems that do not distinguish between individual packets and treat them equally.

In this paper we propose cmpTCP-Westwood (cmpTCPW), which is an extension of a variant of TCP-Westwood and SCTP. The proposed cmpTCPW has been implemented by altering and extending library-based open-source implementation of SCTP. The proposed cmpTCPW manages transmission control parameters of all paths simultaneously; a scheduler concurrently dispatches packets over all the paths from a common transmission queue. However, one virtual retransmission queue is maintained for each path, and the receiver sends acknowledgment for a packet on the same path on which the packet is received. In this paper we describe the proposed architecture and implementation; also, we report empirical evaluations of cmpTCPW. In our network emulation laboratory, two host computers were connected through two independent network emulators. Each network emulator runs on a separate computer, and the network parameters are adjusted independently. Our extensive evaluation shows that cmpTCPW delivers higher throughput than cmpTCP.

Concurrent Multipath Transport (CMT) has been of increasing interest recently for aggregating bandwidth, balancing load, and increasing reliability. In this paper we propose a concurrent multipath Transport Control Protocol (cmpTCP), which is an extension of TCP New Reno and Steam Control Transmission Protocol (SCTP). The proposed cmpTCP has been implemented by altering and extending library-based open-source for SCTP. The proposed cmpTCP manages transport control parameters of all paths simultaneously; a scheduler concurrently dispatches packets over all the paths from a common transmission queue. However, one virtual retransmission queue is maintained for each path, and the receiver sends acknowledgment for a packet on the same path on which the packet is received. A Markov model for estimation of expected window size of each path has been proposed. Next, the proposed model has been utilized to derive an expression for computing average data transmission rate when the proposed cmpTCP is used. To validate performance of the proposed model, two host computers were connected through two independent network emulators. Each network emulator runs on a separate computer, and the network parameters are adjusted independently. We used our cmpTCP for transferring files from one host to the other. Comparison of experimental results with model predicted results shows excellent agreement.

Many recent studies have been dedicated to the estimation of channel utilization of networks deploying IEEE 802.11 MAC protocols. A common finding in these studies is that as the number of wireless nodes increases in a carrier sensing zone, the channel utilization decreases. In this paper we identify a cause for channel utilization drop and propose a novel backoff-state assignment algorithm to alleviate the problem. Also, we develop an analytical model for a node using the proposed backoff-state assignment algorithm. Using the model we show that the proposed MAC can provide higher channel utilization than the original MAC for both basic and RTS/CTS modes of operation.

MPEG-4 spatial scalable encoding scheme (SSES) provides different resolutions and wide range of VBR, (variate bit rate) video to satisfy requirements of end users with variant screen resolutions and network bandwidth. In a SSES, one base layer traffic and one (or more) enhancement layer(s) traffic are generated. Although many traffic models have been developed for single layer video traffic, none exists for VBR, SSES video traffic. Our extensive studies suggest that MMG (Markov-modulated gamma) model can capture base layer traffic quite well. However, it cannot be used for modeling enhancement layer traffic for two reasons: (1) enhancement layers have no I-frames, (2) enhancement layer traffic and base layer traffic are not independent and have a strong correlation. In this paper, we propose two models for enhancement layer traffic and aggregate traffic. To maintain the correlation between base layer and enhancement layers, we augment the base-layer state transition model. The augmentation uses state transition relation between base layer and enhancement layer traffic or between base layer and aggregate traffic. The models have been validated by QQ plots and leaky-bucket simulations. The model generated traffic streams quite accurately mimic original traffic streams.

Network throughput and end-to-end delay time are two important parameters in the design and the evaluation of routing protocols for wireless ad hoc networks. Network throughput and routing protocols have been studied for some time. To be able to estimate the end-to-end delay time, the process induced by the random position of every node has to be known, that is, a mobility model for the nodes has to be specified. It has been proved that if a mobility model for the nodes is based on a Brownian motion on a flat 2-torus the expected end-to-end delay time has logarithmic growth. In this paper we propose a different, although related, mobility model for the nodes based on a discrete-time Markov chain on a flat 2-torus: a standard symmetric random walk. We prove that under this mobility model the end-to-end delay time of a wireless ad hoc network with k user is /spl otimes/(klogk).

In a mobile cellular system quality of service (QoS) to mobile terminals (MTs) is measured by the probability of forced termination P/sub ft/ and/or probability of new call blocking (P/sub b/). Since, both cannot be reduced simultaneously, usually keeping the P/sub ft/ below a designated level DP/sub ft/ is considered as QoS guarantee to the users of the system. However, P/sub ft/ is related to system parameters namely, maximum capacity of the cell C, the average new call arrival rate /spl lambda/, the average call holding time 1//spl mu/, and the average cell dwell time 1//spl eta/ by complex nonlinear equations. Therefore, call admission control (CAC) for maintaining P/sub ft/ at DP/sub ft/ is a very challenging task. A fuzzy controller is proposed to dynamically maintain P/sub ft/ at DP/sub ft/ with changes in system parameters. Also, current cellular networks are employing CDMA as the multiple access technique since it provides much more capacity than other techniques. Interference received at the base station (BS) of a cell is considered in the decision making process of whether to admit a call or not. We describe the CAC criteria used in CDMA cellular networks in this paper. Also, through simulation we show that fuzzy controller can be integrated with other CAC schemes to guarantee QoS to the users.

Abstract It has been shown that in a mobile ad hoc wireless network per node throughput remains constant as the number of nodes approaches infinity, when the nodes lie in a disk of unit area. However, this requires that some packets are delivered indirectly by a relay node. In this paper, we prove, in the same setup, that D(k) ∈ Θ(log k), where D(k) is the expected delay time of a mobile ad hoc wireless network with k nodes. As consequence, we have concluded that mobile ad hoc wireless networks are not scalable for real‐time applications. Copyright © 2004 John Wiley & Sons, Ltd.

A video on demand (VoD) system is expected to transmit many movies over a single channel as demanded by the end users. When several videos are transmitted simultaneously over a link the effective bandwidth required per video is usually much lower than that needed by a single video because of multiplexing gain. Fast and accurate estimation of multiplexing gain is necessary for developing call admission control (CAC) algorithms. Known models which estimate queue size and effective bandwidth of multiplexed video system cannot capture frame size variations in different segments of a video, and are not very useful particularly when the number of videos is not too large. The multinomial model proposed in this paper is built on a Markov-modulated gamma (MMG)-based traffic model of a single video. It takes into consideration average frame size variations in different segments of a video and can predict multiplexing gain for any number of multiplexed videos. The model has been validated using MPEG traces of commercial movies.

In a mobile cellular system quality of service to mobile terminals (MTs) is measured by the probability of new call blocking P/sub b/, and the probability of forced termination, P/sub ft/. Since the available bandwidth in a cell is very limited, both P/sub b/ and P/sub ft/ cannot be reduced or avoided simultaneously. Usually keeping the P/sub ft/ below a designated level is accepted as the measure of quality of service. Admission of new calls is controlled to reduce P/sub ft/. However, there are at least three parameters (new call arrival rate, mean duration of calls, and mobility of users) that can and change dynamically. Moreover, these parameters are related with P/sub ft/ via complicated nonlinear equations. Therefore, call admission control (CAC) for maintaining a desired value of P/sub ft/ is a very challenging task. No CAC algorithm has been reported in the past that can function well with dynamic changes to all these three parameters. We proposed an algorithm that addresses this issue. The new algorithm uses a fuzzy controller to adjust the call preblocking load value with the changing traffic parameters. The fuzzy controller makes use of fuzzy associative memory (FAM) to maintain the required QoS. The use of new system in dynamic traffic conditions is illustrated. Providing the required level of QoS, the algorithm also increases the channel utilization. The proposed CAC with FAM is compared and contrasted with previous CACs.

All traffic models for MPEG-like encoded variable bit rate (VBR) video can be broadly categorized into (1) data-rate models (DRMs) and (2) frame-size models (FSMs). Almost all proposed VBR traffic models are DRMs. DRMs generate only data arrival rate, and are good for estimating average packet-loss and ATM buffer overflowing probabilities, but fail to identify such details as percentage of frames affected. FSMs generate sizes of individual MPEG frames, and are good for studying frame loss rate in addition to data loss rate. Among three previously proposed FSMs: (1) one generates frame sizes for full-length movies without preserving group-of-pictures (GOP) periodicity; (2) one generates VBR video traffic for news videos from scene content description provided to it; and (3) one generates frame sizes for full-length movies without preserving size-based video-segment transitions. We propose two FSMs that generate frame sizes for full-length VBR videos preserving both GOP periodicity and size-based video-segment transitions. First, two-pass algorithms for analysis of full-length VBR videos are presented. After two-pass analysis, these algorithms identify size-based classes of video shots into which the GOPs are partitioned. Frames in each class produce three data sets, one each for I-, B-, and P-type frames. Each of these data sets is modeled with an axis-shifted gamma distribution. Markov renewal processes model (size-based) video segment transitions. We have used quartile-quartile (QQ) plots to show visual similarity of model-generated VBR video data sets with original data set. Leaky-bucket simulation study has been used to show similarity of data and frame loss rates between model-generated VBR videos and original video. Our study of frame-based VBR video revealed that even a low data-loss rate could affect a large fraction of I frames, causing a significant degradation of the quality of transmitted video.

MPEG-encoded variable bit rate (VBR) video traffic is expected to incur cell losses during its transmission over a broadband network. These cell losses introduce distortion into the received video. Frame drop rate and root mean square error (RMSE) can be used to objectively measure this distortion. These two metrics are useful in identifying the threshold cell loss rate (CLR) beyond which the quality of received video is unacceptable to viewers. Thus, they are useful in identifying CLRs to be used in evaluating VBR video traffic models. A novel analytical model is developed for predicting both frame drop rate and RMSE as a function of (i) uniform cell loss rate and (ii) MPEG encoding parameters. The model is validated by an empirical study using an actual MPEG video.

Video traffic is expected to be the major source for broadband integrated services digital networks (B-ISDN). In this paper we propose two FSM that generate frame sizes for full-length VBR videos preserving both GOP-periodicity and size-based video-segment transitions. First, two-pass algorithms for analysis of full-length VBR videos are presented. After two-pass analysis these algorithms identify and partition (size-based) classes of video segments. Frames in each segment class produce three datasets one each for I-, B-, and P-type frame. Each of these data-sets is modeled with an axis shifted gamma distribution Markov renewal processes model (size-based) video segment transitions. We have used QQ plots to show visual similarity of model-generated VBR video data-sets with original dataset. A leaky-bucket simulation study is used to show similarity of data and frame loss rates between model-generated VBR videos and original video. Our study of frame-based VBR video revealed even a low data loss rate could affect a large fraction of I frames causing a significant degradation of the quality of transmitted video.

A new, fault-tolerant, scalable, and modular virtual topology for lightwave networks employing wavelength division multiplexing is proposed. The proposed architecture is based on a hypercube connected ring structure that enjoys the rich topological properties of a hypercube , but it also overcomes one of its drawbacks. In a hypercube, the nodal degree increases with the number of nodes. Hence, the per-node cost of the network increases as the network size grows. However, in a hypercube connected ring network (HCRNet) the nodal degree is small and it remains constant, independent of the network population. A HCRNet, like a hypercube, is perfectly symmetric in the sense that the average internodal distance in an N -node HCRNet is the same from any source node. Its average internodal distance is in the order of log N and it is comparable to other regular structures such as the Trous and ShuffleNet. The HCRNet is based on the Cube Connected Cycle (CCC) interconnection pattern proposed for multiprocessor architectures. However, the HCRNet improves on CCC by rearranging its hypercube links, which results in a significantly lower average internodal distance. In this paper we present the structural properties of HCRNet, and address the issues of scalability, and fast routing in complete as well as incomplete HCRNet.

Among several models of neurons and their interconnections, feedforward artificial neural networks (FFANNs) are most popular, because of their simplicity and effectiveness. Difficulties such as long learning time and local minima may not affect FFANNs as much as the question of generalization ability, because a network needs only one training, and then it may be used for a long time. This paper reports our observations about randomness in generalization ability of FFANNs. A novel method for measuring generalization ability is defined. This method can be used to identify degree of randomness in generalization ability of learning systems. If an FFANN architecture shows randomness in generalization ability for a given problem, multiple networks can be used to improve it. We have developed a model, called voting model, for predicting generalization ability of multiple networks. It has been shown that if correct classification probability of a single network is greater than half, then as the number of networks in a voting network is increased so does its generalization ability. Further analysis has shown that VC-dimension of the voting network model may increase monotonically as the number of networks in the voting networks is increased.

A new, fault-tolerant, scalable, and modular virtual topology for lightwave networks employing wavelength division multiplexing is proposed. The proposed architecture is based on a hypercube connected ring structure that enjoys the rich topological properties of a hypercube, but it also overcomes one of its drawbacks. In a hypercube, the nodal degree increases with the number of nodes. Hence, the per-node cost of the network increase as the network size grows. However, in a hypercube connected ring network (HCRNet) the nodal degree is small and it remains constant, independent of the network population. The HCRNet, like the hypercube, is perfectly symmetric in the sense that average internodal distance in an N-node HCRNet is the same from any source node. Its average internodal distance is in the order of logN and it is comparable to other regular structures such as Trous and ShuffleNet. The authors present the structural properties of the HCRNet and the network routing.>

Assume that n stations, each with a buffer to hold only one packet at a time, are connected as a ring and that data packets are transmitted counterclockwise. A station will attempt to transmit a packet to the next station only if (i) it has a packet to send and (ii) the next station’s buffer is empty. The communication cannels connecting the stations are noisy, and there is a fixed probability $p(0 < p < 1)$ of error-free transmission of a packet from one station to the next in one attempt. An exact expression for the long-run average time for a packet to go around the ring is derived. (A special case of this answers a question raised by Berman and Simon in [Proc. 20th ACM Symp. on Theory of Computing, ACM Press, 1988, pp. 66–77].) For fixed n and p, the throughput of the system is maximum when the number of packets is an integer closest to ${n / 2}$.

The authors exploit the capabilities of lightwave technology in order to construct photonic implementations of "adaptive" and "optimized" distributed queue dual bus (DQDB) structures. These (virtual) structures are linear and multihop in nature, and they can be constructed on any physical topology by exploiting the broadcast-and-select property of WDM lightwave networks. The present study is important since it will allow DQDB (IEEE 802.6) networks to scale up by taking advantage of the various attractive properties of lightwave technology when they become available. The specific problem is on topological design, and it can be stated as follows: given that the network nodes must be connected linearly and that the node positions in the network can be adjusted by properly tuning their (optical) transmitters and receivers, what is the best pattern for interconnecting them? Two sets of heuristic optimization algorithms are formulated. The first set is concerned with minimizing the maximum flow in any link. The second set of heuristics requires the knowledge of not only the traffic matrix but also the distance matrix, and these heuristics are aimed at minimizing the network-wide mean packet delay. A dynamic node migration heuristic is also formulated under which neighbouring nodes swap their positions based on local information in order to preserve the optimality criterion in effect when the offered traffic changes. The performance of these heuristics are compared, some of their properties are analyzed, while their other attractive properties are highlighted via numerical examples.>

This paper presents parallel algorithms for fuzzy arithmetic operations on systolic arrays. A large part of the arithmetic on fuzzy numbers is referred to as fuzzy convolutions, which take O(n2) time steps when implemented sequentially. In this paper, we present two parallel algorithms. The first algorithm runs on a linear array machine in O(n) time, using O(n) processors, and thus, achieving optimal time and cost. The second algorithm runs on a mesh-of-trees type of computer architecture in L(log n) time steps, using O(n2) processors. The latter, although not optimal achieved high speedup. Both can be adapted to handle larger linear fuzzy numbers of fuzzy numbers with higher dimension.

Speedup and efficiency, two measures for performance of pipelined computers, are now used to evaluate performance of parallel algorithms for multiprocessor systems. However, these measures consider only the computation time and number of processors used and do not include the number of the communication links in the system. The author defines two new measures, cost effectiveness and time-cost effectiveness, for evaluating performance of a parallel algorithm for a multiprocessor system. From these two measures two characterization factors for multiprocessor systems are defined and used to analyze some well-known multiprocessor systems. It is found that for a given penalty function, every multiprocessor architecture has an optimal number of processors that produces maximum profit. If too many processors are used, the higher cost of the system reduces the profit obtained from the faster solution. On the other hand, if too few processors are used, the penalty paid for taking a longer time to obtain the solution reduces the profit.>

The goal of the study described is to exploit the capabilities of emerging lightwave technology and the fact that the IEEE 802.6 MAN is a linear network, to construct near optimal linear multihop lightwave networks. Heuristic algorithms are proposed for constructing photonic implementations of near optimal distributed queue dual bus (DQDB) structures. Two sets of heuristic optimization algorithms are formulated. The first set is concerned with minimizing the maximum flow in any link in the network, while the second set of heuristics is aimed at minimizing the network-wide mean packet delay. Important properties of these algorithms are analyzed and their performance is demonstrated with several representative numerical examples.>

New optimal systolic algorithms for the transitive closure problem on ring and linear arrays of processors is presented. The data dependency of the Warshal-Floyd algorithm is exploited to obtain highly pipelined parallel algorithms. One of the algorithms is asymptotically seven times more cost-effective than previous algorithms for computing transitive closure problems. The authors introduce a new expository device, called the RCT diagram, that depicts simultaneously the flow of data and computation of parallel algorithms.>

The star graph has been show to be an attractive alternative to the widely used n-cube. Like the n-cube, the star graph possesses rich structure and symmetry as well as fault tolerant capabilities, but has a smaller diameter and degree. However, very few algorithms exists to show its potential as a multiprocessor interconnection network. Many fast and efficient parallel algorithms require broadcasting as a basic step. An optimal algorithm for one-to-all broadcasting in the star graph is proposed. The algorithm can broadcast a message to N processors in O(log/sub 2/ N) time. The algorithm exploits the rich structure of the star graph and works by recursively partitioning the original star graph into smaller star graphs. In addition, an optimal all-to-all broadcasting algorithm is developed.>

A method for estimating the speedup for asynchronous bottom-up parallel parsing is presented. Two models for bottom-up parallel parsing are proposed, and the speedup for each of the two models is estimated. The speedup obtained for model A is a very close to the simulation result already available in literature; however, the model is restrictive because it can only communicate with its immediate left and right neighbors. This increases the processor coordination and interprocessor communication times. Model B, while showing a greater speedup time, is expensive to construct when the number of processors is large.>

Although incidence matrix representation has been used to analyze the Petri net based models of a system, it has the limitation that it does not preserve reflexive properties (i.e., the presence of self-loops) of Petri nets. But in many practical applications self-loops play very important roles. This paper proposes a new representation scheme for general Petri nets. This scheme defines a matrix called "reflexive incidence matrix (RIM) Cr," which is a combination of two matrices, a "base matrix Cb," and a "power matrix Cp." This scheme preserves the reflexive and other properties of the Petri nets. Through a detailed analysis it is shown that the proposed scheme requires less memory space and less processing time for answering commonly encountered net queries compared to other schemes. Algorithms to generate the RIM from the given net description and to decompose RIM into input and output function matrices are also given. The proposed Petri net representation scheme is very useful to model and analyze the systems having shared resources, chemical processes, network protocols, etc., and to evaluate the performance of asynchronous concurrent systems.