Browsing by Author "Yuang, MC"

Now showing 1 - 20 of 56

A collision resolution paradigm for Random Access Channel control in multi-access wireless networks
(2002)
Yuang, MC
;
Lo, BC
;
Chen, JY
;
資訊工程學系
;
Department of Computer Science
The Random Access Channel (RACH) incurs a collision if more than one user make signaling requests over the same time slot, spreading code, or antenna element, in TDMA, CDMA, or SDMA wireless networks, respectively. In this paper, we propose a Hexanary-Feedback Collision Resolution Paradigm (HFCRP), capable of leveraging access efficiency of the RACH for all above wireless networks. HFCRP performs incremental contention resolution, managing a small subset of users at a time via a two-phase process. In the first phase, a group of users is probabilistically admitted, with a negligible probability of the group size greater than five. In the second phase, all users in the group are efficiently resolved. The two-phase process is augmented with hexanary feedback control facilitated by an nvelope-pdf-based Multi-user stimator ( M R) implemented at the physical layer. significantly, the M R measures the exact number of transmitting users (zero to five) in a contention slot by matching the envelope pdf s histograms of received signals to a library of pre-constructed pdf s. These six outcomes comprise the hexanary feedback being broadcast to users during the real-time operation of the two-phase process. Analytic and simulation results delineate that, performing in con unction with the M R, HFCRP achieves high performance with respect to maximum stable throughput, saturated throughput, access delay, and blocking probability.
A Contention Access Protocol with Dynamic Bandwidth Allocation for wireless ATM networks
(2000)
Yuang, MC
;
Tien, PL
;
Chen, CS
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a new Contention Access Protocol (CAP) augmented with a Dynamic Bandwidth Allocator (DBA) for wireless ATM networks supporting ABR and Signaling Control (SCR) traffic. CAP incorporates a dynamic tree-splitting collision resolution algorithm parameterized by an optimal Splitting Depth (SD). DBA performs estimation and on-line prediction of ABR self-similar traffic characteristics. It in turn determines the optimal SD per every frame, satisfying ABR throughput and SCR blocking probability requirements while retaining maximal aggregate throughput. Simulation results postulate the optimal SD's under various ABR and SCR traffic conditions. These results are then off-line trained and constructed by a Back Propagation Neural Network (BPNN), which is used on-line for optimal bandwidth allocation.
A cut-based method for terminal-pair reliability
(1996-09-01)
Chen, YG
;
Yuang, MC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Summ. & Conclusions - This paper assesses two categories of partition techniques for computing terminal-pair reliability (path-based and cut-based algorithms) by experimenting on published benchmarks; the criteria are the number of subproblems and the computation time. The cut-based algorithm is superior to the path-based algorithm with respect to the computation time for most benchmarks. A refinement of the cut-based algorithm (using network reduction) profoundly outperforms the path-based algorithm (with reduction) for all benchmarks.
A cut-based method for terminal-pair reliability
(1995)
Chen, YG
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
A delay and loss versatile scheduling discipline in ATM switches
(1998-01-01)
Hah, JM
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a versatile scheduling discipline, called Precedence with Partial Push-out (PPP), in Asynchronous Transfer Mode (ATM) switches supporting two delay and two loss priorities. By employing a threshold L, PPP provides delay guarantee by allowing a newly-arriving high-delay-priority cell to precede a maximum of L low-delay-priority cells. Through the use of another threshold R, the discipline offers loss guarantee by permitting a newly-arriving high-loss-priority cell to push out the last low-loss-priority cell located beyond the Rth location in a full queue. By setting L and R properly, PPP versatilely performs as any one of the four widely-accepted disciplines, namely the FCFS, head-of-line, push-out, or head-of-line with push-out disciplines. To determine L and R retaining demanded Quality of Services (QoSs), we provide an in-depth queueing analysis for the Cell Delay (CD) and Cell Loss Ratio (CLR) of high-delay-priority, low-loss-priority cells. We further propose a simple, algebra-based analysis for the CD and CLR for low-delay-priority, high-loss-priority cells. On the basis of these analyses, L and R can be dynamically and effectively adjusted to provide adequate delay and loss guarantees for high-priority cells while incurring only minimal performance degradation for other classes of cells. Finally, the paper presents simulation results confirming the accuracy of the analyses.
A delay and loss versatile scheduling discipline in ATM switches
(1998-03-01)
Hah, JM
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a versatile scheduling discipline, called Precedence with Partial Push-out (PPP), in Asynchronous Transfer Mode (ATM) switches supporting two delay sand two loss priorities. By employing a threshold L, the PPP discipline provides delay guarantee by allowing a newly-arriving high-delay-priority cell to precede a maximum of L, few-delay-priority cells. Through the use of another threshold R, the discipline offers loss guarantee by permitting a newly-arriving high-loss-priority cell to push out the last low-loss-priority cell located beyond the R-th location in a full queue. By setting L and R properly, PPP versatilely performs as any one of the four widely-accepted disciplines, namely, the FCFS, head-of-line, push-out, or head-of-line with push-out disciplines. For precisely determining L and R retaining demanded Quality of Services (QoSs), we provide an in-depth queueing analysis for the Cell Delay (CD) and Cell Loss Ratio (CLR) of high-delay-priority, low-loss-priority cells. We further propose a simple, algebra-based analysis for the CD and CLR of low-delay-priority, high-loss-priority cells. On the basis of these analyses, L and R can be dynamically and effectively adjusted to provide adequate delay and loss guarantees for high-priority cells while incurring only minimal performance degradation for other classes of cells. Finally, the paper presents simulation results confirming the accuracy of the analyses.
A high-performance input access scheme for ATM multicast switching
(1996-01-01)
Haung, YR
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose an input access scheme for input-queued ATM multicast switches, achieving high system throughput, low packet delay and packet loss probability. Multicast and unicast packets of each input port are separately queued. Multicast queues take priority over the unicast queues, and both types of queues are fairly served in a cyclic-priority access discipline. In particular, each unicast queue is handled on a window-service basis, and each multicast packet is switched in a one-shot scheduling manner. To evaluate the performance of the access scheme, we propose an approximate analysis based on a simplified cyclic-priority model for an N x N finite-buffer multicast switch possessing Bernoulli multicast and unicast arrivals, with window-service (for unicasting) and one-shot scheduling (for multicasting) both taken into account. Finally, we show simulation results to demonstrate the accuracy of the approximate analysis and the superiority of the scheme over existing schemes with respect to normalized system throughput, mean packet delay, and packet loss probability.
A high-performance input access scheme for ATM multicast switching
(1996)
Haung, YR
;
Yuang, MC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
In this paper, we propose an input access scheme for input-queued ATM multicast switches, achieving high system throughput, low packet delay and packet loss probability. Multicast and unicast packets of each input port are separately queued. Multicast queues take priority over the unicast queues, and both types of queues are fairly served in a cyclic-priority access discipline. In particular, each unicast queue is handled on a window-service basis, and each multicast packet is switched in a one-shot scheduling manner. To evaluate the performance of the access scheme, we propose an approximate analysis based on a simplified cyclic-priority model for an N x N finite-buffer multicast switch possessing Bernoulli multicast and unicast arrivals, with window-service (for unicasting) and one-shot scheduling (for multicasting) both taken into account. Finally, we show simulation results to demonstrate the accuracy of the approximate analysis and the superiority of the scheme over existing schemes with respect to normalized system throughput, mean packet delay, and packet loss probability.
A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks
(2004-11-01)
Lee, SSW
;
Yuang, MC
;
Tien, PL
;
Lin, SH
;
資訊工程學系
Optical wavelength-division multiplexed (WDM) networks often include optical cross-connects with multigranularity switching capability such as switching on a single lambda, a waveband, or an entire fiber basis. In addition, it has been shown that routing and wavelength assignment (RWA) in an arbitrary mesh WDM network is an NP-complete problem. In this paper, we propose an efficient approximation approach, called Lagrangean relaxation with heuristics (LRH), aimed to resolve RWA in multigranularity WDM networks particularly with lambda and fiber switches. The task is first formulated as a combinatorial optimization problem in which the bottleneck link utilization is to be minimized. The LRH approach performs constraint relaxation and derives a lower-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LRH approach employs a new heuristic algorithm to arrive at a near-optimal upper-bound solution. With lower and upper bounds, we conduct a performance study on LRH with respect to accuracy and convergence speed under different parameter settings. We further draw comparisons between LRH and an existing practical approach via experiments over randomly generated and several well-known large sized networks. Numerical results demonstrate that LRH outperforms the existing approach in both accuracy and computational time complexity, particularly for larger sized networks.
A MAC protocol for real-time manufacturing traffic in client-server-based high speed broadcast networks
(1996)
Liu, JC
;
Yuang, MC
;
Wu, CHJ
;
交大名義發表
;
資訊工程學系
Advances in network technology and the emergence of applications for manufacturing demanding stringent Quality of Service (QoS) requirements have made the design of high-speed broadcast networks feasible and indispensable. Unlike traditional broadcast networks, such as Ethernet, high-speed broadcast networks exhibit high bandwidth-delay product. Moreover, forthcoming networks are required to support diverse virtual manufacturing devices demanding different amounts of bandwidth. Examples are networks with client-server configurations. These facts render traditional Medium Access Control (MAC) protocols unviable. The paper proposes a new MAC protocol, called Prioritized Adaptive Cycle Cell Insertion (PACCI), especially advantageous to client-server-based high-speed broadcast networks. PACCI achieves bounded delay and high utilization regardless of the network size and load. In addition to providing fair access for clients through c_cycles, PACCI offers prioritized access to servers through s_cycles. The bandwidth allocation of the c_cycles and s_cycles is then based on an analytic model in an effort to provide QoS guarantees in terms of throughput under diverse traffic loads. The paper also presents simulation results that demonstrate the accuracy of the analysis and the superior performance of PACCI.
A network reduction axiom for efficient computation of terminal-pair reliability
(2000-07-01)
Hsu, SJ
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
Terminal-pair reliability (TR) in network management determines the probabilistic reliability between two nodes (the source and sink) of a network, given failure probabilities of all links. It has been shown that TR can be effectively computed by means of the network reduction technique. Existing reduction axioms, unfortunately, are limited to trivial rules such as valueless link removal and series-parallel link reduction. In this paper, we propose a novel reduction axiom, referred to as triangle reduction. The triangle reduction axiom transforms a graph containing a triangle subgraph to that excluding the base of the triangle. The computational complexity of the transformation is as low as O(1). With triangle reduction, the number of subproblems generated by partition-based TR algorithms, for simplified grid networks, can be reduced to O(((1 + root 5)/2)(n)). The paper further provides an assessment of the effectiveness of triangle reduction on partition-based TR algorithms with respect to the number of subproblems and computation time through experimenting on published benchmarks and random networks. Experimental results demonstrate that, incorporating triangle reduction, the path-based (cut-based) partition TR algorithm yields a substantially reduced number of subproblems and computation time for all (most of the) benchmarks and random networks. (C) 2000 Elsevier Science Ltd. All rights reserved.
A novel intra-media synchronization mechanism for multimedia communications
(1996)
Yuang, MC
;
Tien, PL
;
資訊工程學系
;
Department of Computer Science
A perfectly stable contention access scheme for wireless access networks
(2001)
Yuang, MC
;
Lo, BC
;
Chen, JY
;
資訊工程學系
;
Department of Computer Science
Existing TDM-based contention access schemes exhibit the unstable or load-susceptible problem in which throughput exponentially deteriorates as the traffic offered load increases or fluctuates. In this paper, we propose a persistently stable, efficient Hexanary-Feedback-based Contention Access (HFCA) scheme, aiming to provide QoS guarantee while retaining stable and maximal network throughput. Unlike existing schemes that consider all contending mobile terminals as a whole, HFCA incrementally resolves a small group of terminals each time via a two-phase selection/resolution process. The incremental resolution repeats until the minimum non-blocking probability (QoS for signaling traffic) is satisfied. To accelerate resolution within the process, the number of simultaneously transmitting terminals is estimated based on an Envelope-pdf-based Estimator (EPER), by matching the corresponding normalized envelope histogram of the receiving signal with the priori envelope-pdf library. Facilitated with incremental resolution and the EPER, HFCA achieves the highest maximum throughput (0.574) and saturated throughput (0.52) reported to date irrespective of traffic increase and variation.
A QoS packet/burst scheduler for broadband networks
(2002)
Yuang, MC
;
Shih, J
;
Tien, PL
;
資訊工程學系
;
Department of Computer Science
Prevailing weight-based scheduling algorithms advocate static or coarse-grained simplification of timestamp computation, resulting in performance bottleneck and unnecessary downgrade under heavy and normal computation loads, respectively. Our goal is to design a scheduler that enables quantitative trade-off balance between performance and complexity. In this paper, we propose a Stepwise QoS Scheduler (SQS), enabling packet to burst scheduling under normal to heavy computation loads, based on a new notion of window. Window sizes of unity and greater than one correspond to packet and burst scheduling, respectively. SQS exerts simple FIFO service within the window and guarantees stepwise weight-proportional service at the window boundary. As a result, quantitative trade-off balance can be facilitated via the adjustment of the window size. We further formally specify the SQS service guarantee for a flow by a stepwise service curve, which is a function of W and theta(min) - the least-upper-bound delay incurred by the first packet of the busy period of the flow. Finally, we demonstrate through experimental results that, by applying a small window (W less than or equal to 10), SQS outperforms Weighted Fair Queueing (WFQ) and performs as superior as Worst-case Fair Weighted Fair Queueing (WF(2)Q) with respect to throughput fairness, mean delay, and worst-case delay fairness.
A QoS-guaranteed MAC protocol using variable frame granularity for wireless access networks
(2001)
Yuang, MC
;
Lo, BC
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a MAC protocol, called QMAC+, which adopts variable frame granularity, aiming to provide bandwidth-on-demand and QoS guarantees while retaining maximal network throughput QMAC+ supports three traffic types- CBR, VBR, and Reservation Request (RVR) for making CBR/VBR connection reservation. Essentially, QMAC+ governs weight-based reservation access (for VBR/CBR) and premier contention access (for RVR) over dynamically allocated reservation and premier contention bandwidths, respectively. In particular, the premier contention access performs incremental contention resolution by means of feedback control using an envelope-pdf-based estimator for the estimation of the number of concurrently transmitting users. As a result, the frame granularity is dynamically changed adapting to traffic fluctuation. Simulation results demonstrate that QMAC+ achieves superior performance with respect to throughput, delay, and blocking probability.
A synchronization paradigm with QoS guarantees for multimedia communications
(1999)
Yuang, MC
;
Lo, BC
;
Chen, YG
;
Tien, PL
;
資訊工程學系
In this paper, we propose a synchronization paradigm, called SYNC*, offering two Quality of Service (QoS) requirements, skew and throughput, for multimedia communications. SYNC* is composed of three components: Intelligent Video Smoother (IVS), Synchronizer, and Multi-thread Priority Manager (MPM). While IVS and Synchronizer achieves intramedia and Intermedia synchronization, respectively, MPM ensures satisfactory throughput before playout. The main goal of the paper is to present in detail the design and performance analysis of the second component, Synchronizer. Synchronizer is aimed to achieve bounded skew between different media through periodic marking of correlated frames. The minimum marking interval yielding a given skew is analytically determined based on a Markov Batch Bernoulli Process (MBBP)/D/K/1 queueing model. We demonstrate the profound agreement between analytic and simulation results. The results also indicate that, the playout quality with respect to skew is highly relevant to the traffic burstiness and decoder buffer size. On the basis of a fixed marking interval, the greater the burstiness and buffer size, the poorer the playout quality.
Bandwidth assignment paradigms for broadband integrated voice/data networks
(1998-03-25)
Yuang, MC
;
Huang, YR
;
資訊工程學系
;
Department of Computer Science
Broadband Integrated Services Digital Networks (BISDNS)/Asynchronous Transfer Mode (ATM) are expected to support diverse applications demanding different bandwidth and Quality of Services (QoSs). Particularly for integrated voice and data networks, voice traffic results in call losses and data traffic suffers from longer delays should networks have insufficient bandwidth. The main goal of the paper is to analytically determine optimal bandwidth allocated to voice and data by means of a queueing model with heterogeneous arrivals and multiple designated channels. The accuracy of analytical results is confirmed by simulation results. On the basis of the analysis, the paper proposes a bandwidth assignment paradigm for the assignment of network bandwidth to voice and data in an effort to guarantee minimal data delay and voice call blocking probability. The run time complexity of the bandwidth assignment computation and paradigm construction is shown to be polynomial bounded. Consequently, the resulting bandwidth assignment assures QoSs in terms of data delay and voice call blocking probability under various network loads. (C) 1998 Elsevier Science B.V.
Departure process analysis for earliest-due-date scheduling discipline in ATM switches
(1996-11-01)
Liang, ST
;
Yuang, MC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Asynchronous Transfer Mode (ATM) networks are expected to support to diverse mix of traffic sources demanding different Quality Of Service (QOS) guarantees. Regarding the Earliest-Due-Date (EDD) as one of the most promising scheduling disciplines offering delay guarantees in ATM switches, we provided in our previous work a decent queueing analysis for determining the urgency number (D-i) for each service class in an effort to offer 99% delay guarantees for higher delay priority calls under various traffic loads. To further evaluate the end-to-end delay distribution for an observed call, in this paper we present the departure process analysis for the EDD discipline with two urgency numbers D-0 = 0 and D-1 = D associated with two delay-based service classes (class 0 and class 1), respectively. The EDD-based ATM switch is modelled by a discrete-time, single-server queueing system with renewal and non-renewal arrivals. Based on the queueing model, we derive the interdeparture time distribution for the observed traffic stream being multiplexed with other traffic streams. The accuracy of the analysis is confirmed by simulation results. Numerical results demonstrate the characteristic reform of the periodic traffic stream after multiplexing through an EDD-based ATM switch. Since the derived departure process becomes the arrival process of the subsequent ATM switch along the pre-established virtual route, the analysis offers the realization of end-to-end delay computation for ATM networks.
DMTS: A distributed multimedia teleworking system
(1998-11-01)
Yuang, MC
;
Liu, JG
;
Chen, YG
;
Liu, JC
;
資訊工程學系
Multimedia systems combine a variety of information sources, such as voice, graphics, animation, images, and full-motion video, into a wide range of applications. The paper initially categorizes existing multimedia applications into three classes: noninteractive-oriented, interactive-oriented client-server-based, and interactive-oriented peer-party-based. In particular, the paper examines interactive-oriented applications and provides an in-depth survey of the media synchronization problem for the design of these applications. The paper then presents our prototyping system, called the Distributed Multimedia Teleworking System (DMTS), which allows two or more remote systems in collaboration to access and modify multimedia data through a network in a fully synchronous fashion. The system has been developed over TCP/IP and an FDDI network, using an XVideo D/A card. The media supported by DMTS include text, graphics, voice, and video. DMTS employs a master-slave collaboration model to maintain the coherence of the text and graphics data being simultaneously modified. Moreover, DMTS also adopts effective mechanisms to reduce skew (asynchrony) and jitter delays between video and voice streams. Finally, the paper demonstrates that DMTS achieves a maximum throughput of 13 frames per second, and reveals that the throughput bottleneck resides in the hardware capture and D/A processing of video frames.
DMTS: A distributed multimedia teleworking system
(1998-11-01)
Yuang, MC
;
Liu, JG
;
Chen, YG
;
Liu, JC
;
資訊工程學系
Multimedia systems combine a variety of information sources, such as voice, graphics, animation, images, and full-motion video, into a wide range of applications. The paper initially categorizes existing multimedia applications into three classes: noninteractive-oriented, interactive-oriented client-server-based, and interactive-oriented peer-party-based. In particular, the paper examines interactive-oriented applications and provides an in-depth survey of the media synchronization problem for the design of these applications. The paper then presents our prototyping system, called the Distributed Multimedia Teleworking System (DMTS), which allows two or more remote systems in collaboration to access and modify multimedia data through a network in a fully synchronous fashion. The system has been developed over TCP/IP and an FDDI network, using an XVideo D/A card. The media supported by DMTS include text, graphics, voice, and video. DMTS employs a master-slave collaboration model to maintain the coherence of the text and graphics data being simultaneously modified. Moreover, DMTS also adopts effective mechanisms to reduce skew (asynchrony) and jitter delays between video and voice streams. Finally, the paper demonstrates that DMTS achieves a maximum throughput of 13 frames per second, and reveals that the throughput bottleneck resides in the hardware capture and D/A processing of video frames.