Protein annotation has long been a challenging task in computational biology. Gene Ontology (GO) has become one of the most popular frameworks to describe protein functions and their relationships. Prediction of a protein annotation with proper GO terms demands high-quality GO term representation learning, which aims to learn a low-dimensional dense vector representation with accompanying semantic meaning for each functional label, also known as embedding. However, existing GO term embedding methods, which mainly take into account ancestral co-occurrence information, have yet to capture the full topological information in the GO-directed acyclic graph (DAG). In this study, we propose a novel GO term representation learning method, PO2Vec, to utilize the partial order relationships to improve the GO term representations. Extensive evaluations show that PO2Vec achieves better outcomes than existing embedding methods in a variety of downstream biological tasks. Based on PO2Vec, we further developed a new protein function prediction method PO2GO, which demonstrates superior performance measured in multiple metrics and annotation specificity as well as few-shot prediction capability in the benchmarks. These results suggest that the high-quality representation of GO structure is critical for diverse biological tasks including computational protein annotation.

The performance of anomaly detection algorithms is usually measured using the total residual error. This error metric is calculated by comparing the labels assigned by the detection algorithm against a reference ground truth. Obtaining a highly expressive ground truth is by itself a challenging task, if not infeasible. Often, a dataset is manually labeled by domain experts. However, manual labeling is error prone. In real-world sensor network deployments, it becomes even more difficult to label a sensor dataset due to the large amount of samples, the complexity of visualizing the data, and the uncertainty in the existence of anomalies. This paper proposes an automated technique which uses highly representative anomaly models for labeling. We demonstrate the effectiveness of this technique through evaluating a classification algorithm using our designed anomaly models as ground truth. We show that the classification accuracy is similar to that when using manually labeled real-world data points.

We study the problem of maximizing path availability in mesh networks against simultaneous failures of multiple links without using protection schemes. The links belong to shared risk link groups (SRLGs) that have arbitrary failure probabilities. This problem is NP-hard, so we propose heuristic algorithms for networks with large numbers of SRLGs, as well as optimal solutions for networks with smaller numbers of SRLGs. The solutions are evaluated through simulations.

Abstract In this paper, we present a software‐defined radio (SDR) based cognitive radio (CR) implementation and demonstration over the frequency modulation (FM) band. Using GNU Radio as the software platform and USRP (Universal Software Radio Peripheral) SDR boards as the hardware solution, we implement and demonstrate a CR that autonomously senses the entire FM band, detects all the active FM stations (occupied bands) as well as the spectrum holes (non‐occupied bands), exploits the available spectrum holes to transmit secondary users' data without interference with the existing FM transmission. Moreover, we demonstrate that when a primary user's transmission returns to its allocated spectrum band after a period of absence, the CR automatically adapts its transmission and hands off to a different spectrum hole that is available to avoid interference with the returning primary user. Moreover, we have proposed, implemented, and demonstrated a frequency hopping scheme over multiple spectrum holes to support multiple secondary users while attaining the minimum interference among the users. Copyright © 2009 John Wiley & Sons, Ltd.

This paper proposes a novel multi-carrier CDMA scheme, namely FD-CI/MC-CDMA (frequency division carrier interferometry multi-carrier code division multiple access), to combine the benefits of previously developed FD-MC-CDMA with CI/MC-CDMA together to provide higher BER performance in multipath fading channels. FD-MC-CDMA is capable of exploiting the available frequency diversity benefits in multipath fading channels while reducing MAI. Specifically, instead of transmitting all users' information bits over all carriers, FD-MC-CDMA employs a subset of non-contiguous carriers to support a subset of users (while maintaining the same overall system capacity and throughput as in MC-CDMA). However, since the length of Hadamard-Walsh codes only exists for certain integers, FD-MC-CDMA lacks the flexibility to accurately divide all subcarriers into subsets according to the channel condition. On the other hand, CI/MC-CDMA offers good BER performance while providing any length of orthogonal spreading codes. By combining these two systems together, the proposed FD-CI/MC-CDMA system significantly outperforms FD-MC-CDMA (as well as MC-CDMA) in multipath fading channel at similar complexity.

MC-CDMA (multiple carrier code division multiple access) has been considered a strong candidate for cognitive radio and dynamic spectrum access network, due to its high spectral efficiency, easy implementation and the capability of operating over non-contiguous frequency bands. However, like other multi-carrier transmission technologies such as OFDM (orthogonal frequency division multiplexing), the orthogonality among subcarriers in MC-CDMA system is lost in a mobile environment, leading to inter-carrier interference (ICI) and performance degradation. In this paper, we apply the ICI self-cancellation scheme previously proposed for OFDM system to orthogonal MC-CDMA system with Hadamard-Walsh codes to diminish ICI and improve BER performance. We show that the ICI self-cancellation scheme for MC-CDMA is equivalent to employing a subset of the Hadamard code matrix. As a direct result, the proposed ICI self cancellation method does not increase the complexity at both transmitter and receiver. To compensate for the network capacity (in terms of the number of users) loss in the proposed ICI self-cancellation method, a second set of orthogonal Hadamard-Walsh codes on the quadrature subcarriers are introduced. The proposed system offers significant BER performance gain than original MC-CDMA with the presence of ICI and same network capacity when BPSK modulation is employed. Simulation results over multi-path fading channel confirm the effectiveness of the proposed scheme, without increasing any complexity.

Channel allocation is an important area of research in open spectrum networks which asserts a significant impact on the spectrum utilization and the fairness among users. This paper studies the optimization of channel allocation, considering multiple objectives. For each objective, a binary programming model is described. Then a new optimization objective called fairness constrained maximum throughput is proposed. To achieve this optimization objective, a unified binary linear programming (UBLP) model is constructed which is then solved by the simplex method and branch-and-bound search. The solution to this model satisfies a bandwidth requirement for each user, e.g., the bandwidth for each user is equal to or larger than a per-user bandwidth minimum, and the solution also maximizes the network throughput. We prove that given different per-user bandwidth minimum, the optimal solution to the UBLP model achieves specific optimization objectives, such as the maximum network throughput and the max-min fairness. For the proportional fairness objective, the solution to the UBLP model proves to be within a bound of the optimal solution.

Sums of lognormal random variables occur in many important problems in wireless communications. However, the lognormal sum distribution is known to have no close-form and is difficult to compute numerically. Several approximation methods have already been proposed to approximate the lognormal sum distribution. However, these approximation methods all have their drawbacks: some widely used approximation methods are not very accurate at the lower region, some other approximation methods require the CDF curve from Monte Carlo simulation first. In this paper, we propose a novel approximation method, namely the Log Skew Normal (LSN) approximation, to model and approximate the sum of M lognormal distributed random variables. The proposed LSN approximation method has very high accuracy in most of the region, especially in the lower region. Furthermore, this approximation method does not require the CDF curve from Monte Carlo simulation first. The closed-form probability density function (PDF) of the resulting LSN random variable is presented and its parameters are derived from those of the M individual lognormal random variables by using an moment matching technique. Simulation results on the cumulative distribution function (CDF) of sum of M lognormal random variables in different conditions are used as reference curves to compare various approximation techniques. LSN approximation is found to provide better accuracy over a wide CDF range over other approximation methods.

Survivable service provisioning design has been an important issue in communication networks. In this work, we study survivable service provisioning using shared path based protection under a scheduled traffic model in wavelength convertible WDM optical mesh networks with Shared Risk Link Groups (SRLGs). In the scheduled traffic model, a set of demands is given, and the setup time and teardown time of a demand are known in advance. The objective is to minimize the total network resources (e.g., the number of wavelength-links) used by working paths and protection paths of the given set of demands while 100% restorability is guaranteed against any single SRLG failure. This problem is known to be NP-hard. We therefore study a time efficient approach to approximating the optimal solution to the problem. Our proposed approach is based on an iterative survivable routing scheme that utilizes a capacity provision matrix and processes demands sequentially. Our simulation results indicate that the proposed ISR-SRLG algorithm achieves excellent performance in terms of the total network resources used.

In this work, we study the problem of efficient service provisioning in light-trail WDM optical networks under a scheduled traffic model. In this model, a set of demands is given, and the setup time, teardown time, and the requested bandwidth of a demand are known in advance. When constructing light-trails to accommodate scheduled demands, we consider two cases: static light-trail case and dynamic light-trail case. In the static light-trail case, a light-trail will not be torn down once it is set up. In the dynamic light-trail case, a light-trail can be torn down when it is not used by any scheduled demand, so that the resources for that light-trail can be re-allocated for other light-trails. We present Integer Linear Programming (ILP) formulations for this problem while considering the instantiation of static light-trails as well as dynamic light-trails to provision scheduled services. The optimization objective is to minimize the resources used in terms of the total wavelength-links used to accommodate a set of demands. Time efficient heuristic algorithms are then proposed for both cases. The solutions to the ILP formulations and the extensive simulation of the heuristic algorithms show that the use of dynamic light-trails significantly reduces the required resources to accommodate the same demand set. The resource reduction becomes more significant as the size of demand sets increases and the time correlation among demands becomes weaker. The heuristic algorithms for both cases are also shown to be very time efficient.

Existing optical burst switching (OBS) architecture has assumed the separated transfer of burst header packets and data bursts. To deal with burst contention and blocking, various approaches have been proposed such as using deflection routing, fiber delay line buffering, wavelength conversion, and burst segmentation. In this paper, we investigate a shared channel architecture that allows the transfer of both burst header packets and data bursts on the same wavelength channel with some modifications on the current OBS architecture. The new shared channel based OBS architecture is expected to have better flexibility in resource utilization and improved burst blocking performance. Based on the reduced load fixed point approximation, we provide an analytic model for burst blocking probability analysis under the proposed architecture which employs the just-enough-time signaling and fixed routing. The accuracy of the analytic model is validated via extensive simulation. Overall, our analysis and simulation show that the proposed architecture achieves a significantly lower burst blocking probability than the conventional architecture.

Burst grooming in OBS networks is to coalesce two or more sub-bursts to form a larger burst that will be switched as one unit in order to reduce resource waste and switching penalty. In this paper, we study the burst grooming problem where bursts originating from the same source and destined to different destinations may be groomed together. Assuming burst grooming can only be realized at edge nodes, we explore the light splitting capability of core nodes and mainly deal with the case when bursts in the network is too small to satisfy the minimum burst length requirement. We propose two effective burst grooming algorithms, (1) no over-routing waste approach (NoORW); and (2) minimum relative total resource ratio approach (MinRTRR). Our initial simulation results have shown that the proposed algorithms are effective in improving system performance in terms of burst blocking probability and average burst end- to-end delay.

Survivable service provisioning design has emerged as one of the most important issues in communication networks in recent years. In this work, we study survivable service provisioning with shared protection under a scheduled traffic model in wavelength convertible WDM optical mesh networks. In this model, a set of demands is given, and the setup time and teardown time of a demand are known in advance. Based on different protection schemes used, this problem has been formulated as integer linear programs with different optimization objectives and constraints in our previous work [8, 9]. The problem is shown to be NP- hard. We therefore study time efficient approaches to approximating the optimal solution to the problem. Our proposed approach is based on an iterative survivable routing (ISR) scheme that utilizes a capacity provision matrix and processes demands sequentially using different demand scheduling policies. The objective is to minimize the total network resources (e.g., number of wavelength-links) used by working paths and protection paths of a given set of demands while 100% restorability is guaranteed against any single failure. The proposed algorithm is evaluated against solutions obtained by integer linear programming. Our simulation results indicate that the proposed ISR algorithm is extremely time efficient while achieving excellent performance in terms of total network resources used. The impact of demand scheduling policies on the ISR algorithm is also studied.

In this work, we study a multi-constrained routing problem in networks with SRLGs where a path between a source and a destination is determined such that both the path cost and the weight of SRLGs to which the links of the path belong are bounded. The path cost is measured as the sum of cost of links on the path while the weight of SRLGs is calculated as the sum of the weight of individual SRLGs along the path. The solution to this problem can be used to find risk bounded and cost bounded path for a connection, or to design algorithms that find a pair of low cost SRLG-diverse paths between a source and a destination for survivable service provisioning. The multi-constrained routing problem is solved in two steps. First, an algorithm is devised that tries to find a least cost path in the network where the path cost is defined to be the combined cost of links and SRLG weights along the path. Second, an intelligent search algorithm that integrates the algorithm of the first step is designed to solve the multi-constrained routing problem to effectively find a path with the least total link cost while the total weight of the SRLGs along the path is bounded. The performances of the proposed algorithms are evaluated via extensive simulation and are compared with the solutions obtained by integer linear programming. Our simulation studies show that the proposed algorithms produce excellent results.

In this paper, we propose a general scheduled traffic model, sliding scheduled traffic model. In this model, the setup time t/sub s/ of a demand whose holding time is T time units is not known in advance. Rather t/sub s/ is allowed to begin in a pre-specified time window [l,T] subject to the constraint that l/spl les/t/sub s//spl les/r-T. We then consider two problems: (1) how to properly place a demand within its associated time window to reduce overlapping in time among a set of demands; and (2) route and assign wavelengths (RWA) to a set of demands under the proposed sliding scheduled traffic model in mesh reconfigurable WDM optical networks without wavelength conversion. In addition, we consider how to rearrange a demand by negotiating a new setup time that minimizes the demand schedule change in case that the demand is blocked. To maximize temporal resource reuse, we propose a demand time conflict reduction algorithm to solve the first problem. Two algorithms, window based RWA algorithm and traffic matrix based RWA algorithm, are then proposed for the second problem. We compare the proposed RWA algorithms against a customized tabu search scheme. Simulation results show that the proposed demand time conflict reduction algorithm can resolve well over 50% of time conflicts and the space-time RWA algorithms are effective in satisfying demand requirements and minimizing total network resources used, d.

We study survivable service provisioning under a scheduled traffic model in wavelength convertible WDM optical mesh networks. In this model, a set of demands is given, and the setup time and teardown time of each demand are known in advance. We formulate the problem as integer linear programs that maximally exploit network resource reuse in both space and time. The objective is to minimize the total number of wavelength-links used by working paths and protection paths of all traffic demands while 100% restorability is guaranteed against any single failures. Our simulation results indicate that joint optimization of resource sharing in space and time enabled by our connection holding-time aware protection schemes can achieve significantly better resource utilization than schemes that are holding-time unaware

With the huge capacity, wavelength division multiplexing (WDM) optical networks are predominantly used as the transport infrastructure to carry inter-domain traffic for client networks. Traffic grooming refers to the aggregation of low-speed client traffic flows onto high-capacity optical connections, to achieve cost-effective traffic transport. In this paper, we propose a route segment technique to efficiently compute the client traffic blocking probability in dynamic traffic grooming, where client traffic randomly arrives/departs. In our experiments, the blocking probabilities computed by this technique closely match the results obtained by simulations.

Traffic grooming in wavelength division multiplexing (WDM) optical networks controls how to consolidate client calls with sub-wavelength data rates onto lightpaths. It can be classified into static or dynamic traffic grooming depending on whether the client traffic is static or dynamic. The principal problem in traffic grooming is to construct a logical topology to route client traffic over a given physical topology. For dynamic traffic grooming, the logical topology may be dynamically configured, or designed a priori given the stationary traffic demands between client nodes (and reconfigured on relatively large time scale, e.g., on the order of hours, to adapt to traffic demands changes). Both approaches have their pros and cons. This paper studies the latter case and develops a heuristic algorithm to design logical topology, constrained by client traffic blocking probability requirement and the maximum by-pass traffic amount allowed at each client node. We have compared logical topologies designed the heuristic and an ILP model. The heuristic performance is impressive.

Sensor networks have emerged as a promising technology for large-scale, real-time monitoring in complex environments. This paper develops in-network algorithms for the detection and tracking of region-based targets and events. We deal with such issues as network topology, event boundary detection, region merging, and region simplification and smoothing. Simulation experiments confirmed that our algorithms are efficient and accurate.

For video communications over wireless ad-hoc networks, there are fundamentally two different kinds of packet losses: packet losses due to channel over-pumping, where the operating transmission rate is higher than the prevailing channel capacity, and packet losses due to transmission errors. To eliminate the first kind of packet losses, rate-control is necessary in order to adapt to the time-varying channel capacity. For the second kind of packet losses, error-resilient coding techniques should be used. In this paper, we propose a cross-layer rate-control scheme based on an analytical study of how the effective video transmission rate is affected by the prevailing operating parameters. Furthermore, in order to provide error-resilient real-time video delivery over such wireless ad-hoc networks, a cross-layer delay-constrained joint source-channel coding (JSCC) approach, to be used in conjunction with rate-control, is proposed and investigated. Simulation results demonstrate the effectiveness of this combination of cross-layer rate-control and delay-constrained JSCC for supporting error-resilient video delivery over wireless ad-hoc networks operating under a delay constraint.

Adaptive multimedia services are very attractive since resources in wireless/mobile networks are relatively scarce and widely variable, and more importantly the resource fluctuation caused by mobility and channel fading can be mitigated using adaptive services. Therefore, there are extensive research activities on Quality of Service (QoS), call admission control, as well as bandwidth degradation and adaptation for adaptive multimedia services in wireless/mobile networks in recent years. However, fairness of bandwidth degradation has largely been ignored in previous work and remains an important issue in adaptive multimedia service provisioning. In this paper, we propose and study proportional degradation service provisioning in wireless/mobile networks that offer multiple classes of adaptive multimedia services. The proposed proportional degradation fairness model guarantees the proportional bandwidth degradation among different classes of services. Two proportional degradation scenarios are studied in this paper. In the first scenario, we study the proportional degradation provisioning with two QoS parameters for adaptive multimedia: the degradation ratio (DR) and the degradation degree (DD). In the second scenario, we study the proportional degradation provisioning with a new QoS parameter for adaptive multimedia: the degradation area (DA). For each scenario, based on the QoS parameters, proportional degradation adaptation algorithms are proposed to approximate the proportional degradation model, to fairly adapt calls' degradations, to utilize the system resource efficiently, as well as to optimize QoS parameters. Performance studies show that in the first scenario, proportional DR has been achieved very well, whereas proportional DD has not been well achieved. In other words, DR outperforms DD in terms of proportional degradation. In the second scenario, proportional DA has been well achieved. Furthermore, bandwidth resources have been efficiently utilized and DA has been minimized. Copyright © 2004 John Wiley & Sons, Ltd.

In this paper, we study the optimal configuration of p-cycles in survivable WDM optical mesh networks with sparse wavelength conversion while 100% restorability is guaranteed against any single failures. We formulate the problem as an integer linear program. In our optimization model, working paths are known before protection configuration is done. p-cycles and wavelength converters are then optimally determined subject to the constraint that only a given number of nodes have wavelength conversion capability. The objective is to minimize the cost of link capacity used by all p-cycles to accommodate a set of traffic demands. In the proposed p-cycle configuration architecture, we take into account converter sharing: (a) when converters are used for accessing p-cycles and for wavelength conversion between two adjacent on-cycle spans; (b) when converters are used among disjoint straddling spans incident to the same node for accessing p-cycles. Converter sharing enables the network to require as few converters as possible to attain a satisfactory level of performance. Our simulation results indicate that the proposed approach significantly outperforms the approach for WP networks in terms of protection cost and can obtain the optimal performance as achieved by the approach for VWP networks, but requires fewer wavelength conversion sites and fewer wavelength converters.

In this work, we propose a new hybrid dynamic burst contention resolution scheme. The proposed scheme is based on the notion of burst segmentation and judiciously uses optical buffering (i.e., FDLs) and partial wavelength conversion, and at the same time dynamically selects contention resolution policies in response to the network traffic load change. We assume that the just-enough-time (JET) signaling protocol is used and that switches only have a limited number of full-range wavelength converters and some switches may not have FDLs or wavelength converters. The proposed hybrid scheme does not pre-reserve FDLs or wavelength converters. Instead, it uses them on an as needed basis to reduce the wavelength converters required. Extensive simulation was performed to evaluate the performance of the proposed scheme and to compare with other schemes. Results show that our hybrid scheme is effective.

We consider the grooming of multicast traffic in WDM optical mesh networks with sparse nodal light splitting capability. Given multicast routing trees for individual multicast sessions, the multicast traffic grooming problem is NP-hard. Moreover, constructing an optimal multicast routing tree in WDM optical mesh networks is also an NP-hard problem. We formulate the problem of multicast traffic grooming in WDM optical mesh networks as an integer linear program. We propose a heuristic algorithm for constructing multicast routing trees and a first-fit algorithm for traffic grooming, assuming wavelength conversion capability in the network nodes. By intelligently grooming several multicast sessions with fractional wavelength bandwidth requirements onto a single wavelength, we demonstrate that our algorithms achieve a significant reduction in the maximum number of wavelengths required in a link as well as in the total number of wavelength links needed.

In this paper, we address the problems of constructing both source-based and core-based many-to-many multicast trees for applications with delay and/or delay jitter constraints. We use the source-destination delay bound and the interdestination delay fitter bound as the QoS requirement and formulate the delay and delay jitter constrained many-to-many multicast tree (D/sup 2/M/sup 3/T) problems. For the source-based, many-to-many multicast paradigm, we extend an existing scheme that builds a one-to-many, QoS-compliant multicast tree and devise a solution scheme that first finds a feasible multicast tree for each source node in the multicast group and then a minimum cover of these multicast trees such that there exists at least one feasible multicast tree in the minimum cover for each source node. For the core-based, many-to-many multicast paradigm, we first derive a necessary and sufficient condition for a core-based multicast tree to be feasible and then devise a solution scheme based on the condition derived. We validate and evaluate both proposed schemes via simulations.

Much work has focused on traffic grooming in WDM ring networks. Previous work has considered many aspects of traffic grooming, including minimizing the number of ADMs, minimizing the number of wavelengths, single hub and multiple hub architectures, switching capabilities, etc. We derive general and tighter bounds on the number of wavelengths in WDM ring networks that may be capable of switching streams across wavelengths. We also study traffic grooming in unswitched UPSRs (unidirectional path-switched rings) and derive a more general lower bound for the number of ADMs required in traffic grooming. This bound reduces to special cases first obtained by E. Modiano and A. Chiu (see IEEE J. of Light-wave Technology, 2000). A cost-effective multi-phase traffic grooming algorithm is proposed and studied for UPSRs. Our numerical results show that this algorithm outperforms existing traffic grooming algorithms, resulting in traffic grooming that uses a lower number of ADMs. Our algorithm in many cases also reaches the general lower bound derived.

In this paper, we present a new online algorithm for dynamically routing bandwidth guaranteed label switched paths (LSPs). LSP set-up requests are represented in terms of a pair of ingress and egress routers as well as its bandwidth requirement, and arrive one by one. There is no a priori knowledge regarding future LSP set-up requests and their characteristics. Our proposed algorithm considers not only the importance of critical links, but also the degree of their importance to routing possible future LSP set-up requests by characterizing their normalized bandwidth contribution to routing future LSP demands. Moreover, link residual bandwidth information, i.e., the link's capability of routing future LSPs, is also incorporated. Simulation results show that our proposed algorithm performs better than the best known bandwidth guaranteed routing algorithm, the minimum interference routing algorithm, in terms of LSP rejection rate under both static and dynamic LSP set-up request arrivals.

This paper extends the concept of multicast to quorumcast, a generalized form of multicast communication. The need of quorumcast communication arises in a number of distributed applications. Little work has been done on routing quorumcast messages. The objective of previous research was to construct a minimum cost tree spanning the source and the quorumcast group members. We further consider the path quality of a constructed spanning tree in terms of delay constraints required by applications that use the tree. As the delay-constrained quorumcast routing problem is NP-complete, we propose an efficient heuristic QoS routing algorithm. We also consider how a loop is detected and removed in the course of tree construction and how to deal with members joining/leaving the quorumcast pool. Our simulation study shows that the proposed algorithm performs well and constructs a quorumcast tree whose cost is close to that of the "optimal" routing tree.

In this paper, we devise a preallocation-based single-hop wavelength division multiple access (WDMA) scheme to support temporal quality of service (QoS) in star-coupled optical networks, We consider a star-coupled broadcast-and-select network architecture in which N stations are connected to a star coupler with W different wavelength channels. Each of the W wavelength channels is slotted and shared by the !V stations by means of time division multiplexing. Depending on the tunability characteristics (tunable or fixed tuned) of the transmitters/receivers, we classify the network architecture as tunable transmitter/fixed tuned receiver (TT-FR), fixed tuned transmitter/tunable receiver (FT-TR), and tunable transmitter/tunable receiver (TT-TR). We first characterize each real-time message stream M/sub i/, with two parameters, the relative message deadline D/sub i/ and the maximum (total) message size C/sub i/ that can arrive within any time interval of length D/sub i/. We then discuss a restricted case in a TT-FR (or FT-TR) system in which the message streams from a source station are assumed to be all destined for the same destination station. Under this assumption, no source destination conflicts may occur. We propose a preallocation-based slot assignment scheme to preallocate slots to a set of isochronous message streams, (M/sub i/=(C/sub i/, D/sub i/)|1/spl les/i/spl les/n) in such a way that, in any time window of size D/sub i/ slots, at least C/sub i/ slots on a wavelength channel are allocated to M/sub i/ for all i. With the solution derived in the restricted case as a basis, we then consider slot assignment in a (general) TT-TR system and propose a binary splitting scheme to assign each message stream sufficient and well-spaced slots to fulfil its temporal requirement, subject to the source/destination conflict constraints. We rigorously prove the invariance properties, and the correctness, of the binary splitting scheme.

We design an effective multicast routing algorithm for distributing layered multicast video to heterogeneous receivers in networks with rate-based link schedulers. The multicast tree constructed by the algorithm fulfils the QoS requirements imposed by heterogeneous receivers both in terms of bandwidth and delay, and at the same time, consumes as little network resource as possible. For the purpose of scalability, the proposed multicast routing algorithm is decentralized and can adapt to network and membership change. To facilitate construction of such a multicast tree in a distributed manner we equip each node with an auxiliary routing table, and propose procedures for updating/maintaining the auxiliary routing table. Simulation results indicate that the multicast tree constructed by the proposed algorithm is more resource efficient than those constructed by other existing algorithms, especially when there exist multiple alternative paths to multicast receivers in the network.

In this paper, we develop efficient admission control tests for member join/leave and its associated state refresh and update procedures for receiver-initiated core-based multicast routing, e.g., core based tree (CBT) protocol, to allow construction of QoS-capable multicast trees, while making the minimum possible impact on the existing infrastructure. Specifically, we (i) derive sufficient conditions for a multicast tree to maintain its QoS; (ii) devise effective admission tests to verify whether or not a group member may join the multicast tree at adequate QoS, while not violating existing QoS guarantees to other on-tree members; and (iii) identify the minimum set of state information required for the admission tests and develop a soft state refresh and update procedure. Finally, we validate the effectiveness of the proposed mechanism by incorporating it into the CBT protocol, and evaluate it via event-driven simulations in terms of the probability of join requests being rejected, message overhead, and scalability.

We develop and evaluate a set of member join/leave and state update/refresh procedures for QoS provisioning in core-based multicast routing with explicit member join and soft state refresh procedures. Specifically, in our prior work (Hung-Ying Tyan et al., 1999), we devised eligibility tests to verify whether or not a new member can join a multicast tree at adequate QoS while not violating the existing QoS guarantees to other on-tree members. We extend our prior work, identify the tradeoff between the amount of state kept at each on-tree router and the degree of collaboration among on-tree routers to conduct the tests, and develop two member join/leave procedures that range from using the most comprehensive state update procedure (and hence the least degree of collaboration among on-tree routers) to the other extreme. Also, we evaluate the proposed framework, in terms of the probability of locating feasible multicast trees, message overheads, and scalability.

To complement the prior work of Kung-Ying Tyan, Chao-Ju Hou, Bin Wang and Ching-Chih Han (see Proc. IEEE 17th Real-Time Systems Symposium, Washington DC, 1996), we address the problem of dynamically establishing/terminating real-time message streams in response to call setup/clear requests in single-hop star-coupled WDMA-based optical networks. We consider a network architecture in which N stations are connected to a star coupler with W data channels (W/spl les/N) and one control channel. Each of the W data channels is slotted and shared by the N stations by means of time division multiplexing. The control channel is used for stations to coordinate the call establishment and termination operations. We propose a distributed, dynamic slot allocation scheme to allocate/deallocate, in response to call setup/clear requests, time slots on the W data channels to message streams, with the objective of meeting message deadlines. We formally prove the properties, and the correctness of, the proposed dynamic slot allocation scheme.

Based on the POPSMAC protocol proposed in Chung-Sheng Li et al. (1993), we propose an improved medium access protocol for wavelength division multiple access (WDMA) photonic networks. Using the same set of photonic devices as in POPSMAC, the proposed protocol alleviates the drawbacks of the POPSMAC protocol, e.g., invalid data transmissions following receiver collisions and possible acknowledgement packet collisions with header/data packets, while retaining many advantages of POPSMAC. As a result, the network performance in terms of the throughput and the packet delay is improved. Analytical models based on the timing diagram analysis, the continuous-time Markov chain, and the randomization technique are developed to assess the performance of the proposed protocol. The performance is evaluated in terms of channel utilization, mean packet delay, and packet delay distribution with variations in the number of nodes, the offered traffic, the size of data packets, and the network propagation delay. Numerical results show that the proposed protocol achieves better channel utilization and incurs lower packet delays than POPSMAC.

We devise a preallocation based single hop wavelength division multiple access (WDMA) scheme to support time constrained communication in star coupled optical networks. We consider a star coupled broadcast and select network architecture in which N stations are connected to a star coupler with W different wavelength channels. Each of the W wavelength channels is slotted and shared by the N stations by means of time division multiplexing. Networks with different transceiver configurations, i.e., TT-FR, FT-TR, and TT-TR systems, are investigated. We characterize each real time message stream M, with two parameters, relative message deadline D/sub i/ and maximum (total) message size C/sub i/ that can arrive within any time interval of length D/sub i/. We then discuss a restricted case in a TT-FR system in which the message streams from a source station are assumed to be all going to the same destination station. Under this assumption, no source/destination conflicts may occur. We propose a preallocation based slot assignment scheme to allocate slots to a set of isochronous message streams, {M/sub i/=(C/sub i/, D/sub i/))|1/spl les/i/spl les/n}, so that in any time window of size D/sub i/ slots, at least C/sub i/ slots on a wavelength channel are allocated to M/sub i/ for all i. With the solution derived in the restricted case as a basis, we then consider slot assignment in a (general) TT-TR system, and propose a binary splitting scheme to assign each message stream sufficient and well spaced slots to fulfill its timing requirement, subject to source/destination conflict constraints. We rigorously prove the invariant properties and the correctness of the binary splitting scheme.