Browsing by Author "Yin, WM"

Now showing 1 - 9 of 9

Allocation and scheduling algorithms for IEEE 802.14 and MCNS in hybrid fiber coaxial networks
(1998-12-01)
Lin, YD
;
Huang, CY
;
Yin, WM
;
資訊工程學系
;
Department of Computer Science
IEEE 802.14 and MCNS are two standards developed for the Hybrid Fiber Coaxial (HFC) CATV networks. Both standards model an upstream channel as a stream of minislots. But their philosophies on resolving collisions in the shared upstream channel are rather different, where IEEE 802.14 adopts the priority+FIFO first-transmission rule and the n-ary tree retransmission rule, and MCNS adopts the binary exponential backoff algorithm with adjustable window sizes. Both provide reservation access, while IEEE 802.14 and MCNS also support isochronous aceess and immediate access, respectively. In this paper, we try to prepare a suggestion list for vendors on how to allocate minislots for reservation aceess and immediate access and how to schedule the reserved bandwidth, which greatly affect the performance of a cable network and are left open by the standards.
Allocation and scheduling algorithms for IEEE 802.14 and MCNS in hybrid fiber coaxial networks
(1998-12-01)
Lin, YD
;
Huang, CY
;
Yin, WM
;
資訊工程學系
;
Department of Computer Science
IEEE 802.14 and MCNS are two standards developed for the Hybrid Fiber Coaxial (HFC) CATV networks. Both standards model an upstream channel as a stream of minislots. But their philosophies on resolving collisions in the shared upstream channel are rather different, where IEEE 802.14 adopts the priority+FIFO first-transmission rule and the n-ary tree retransmission rule, and MCNS adopts the binary exponential backoff algorithm with adjustable window sizes. Both provide reservation access, while IEEE 802.14 and MCNS also support isochronous aceess and immediate access, respectively. In this paper, we try to prepare a suggestion list for vendors on how to allocate minislots for reservation aceess and immediate access and how to schedule the reserved bandwidth, which greatly affect the performance of a cable network and are left open by the standards.
Interleaving collision resolution engines in n-ary tree protocols
(2001-12-01)
Yin, WM
;
Lin, YD
;
資訊工程學系
;
Department of Computer Science
N-ary tree protocols are used for access control on shared channels to resolve collisions among channel users. For exercising a single collision resolution engine (CRE), throughput and latency of such protocols have been comprehensively studied. This study investigates the same protocols with multiple interleaved CREs in slotted networks. Power, defined as the ratio of throughput over latency, is measured as the criteria to launch or terminate CREs. Analysis results indicate that the appropriate number of CREs to trigger depends on the traffic load and the collision resolution protocol. As the load grows to 0.25, 0.35, 0.5, and 0.8, the optimal number of interleaved CREs becomes 2, 3, 5, and 8, respectively. Moreover, the power of n-ary tree protocol with n determined dynamically outperforms the 3-ary tree protocol by 13%.
Optimal ranging algorithms for medium access control in hybrid fiber coax networks
(2002-10-01)
Lin, FYS
;
Yin, WM
;
Lin, YD
;
Lin, CH
;
資訊工程學系
The ranging algorithm allows active stations to measure their distances to the headend for synchronization purpose in Hybrid Fiber Coax (HFC) networks. A practicable mechanism to resolve contention among numerous stations is to randomly delay the transmission of their control messages. Since shorter contention cycle time increases slot throughput, this study develops three mechanisms, fixed random delay, variable random delay, and optimal random delay, to minimize the contention cycle time. Simulation demonstrates that the optimal random delay effectively minimizes the contention cycle time and approaches the theoretical optimum throughput of 0.18 from pure ALOHA. Furthermore, over-estimation reduces the impact on contention cycle time more than under-estimation through sensitivity analysis, and both phenomenon damage slot throughput. Two estimation schemes, maximum likelihood and average likelihood, are thereby presented to estimate the number of active stations for each contention resolution round. Simulation proofs that the proposed estimation schemes are effective even when the estimated number of active stations in initial contention round is inaccurate.
PCUP: Pipelined cyclic upstream protocol over hybrid fiber coax
(1997-01-01)
Lin, YD
;
Wu, CJ
;
Yin, WM
;
交大名義發表
;
資訊工程學系
In order to bring NII (National Information Infrastructure) into the home, the community cable TV networks have to be reengineered to support two-way interactive services. In this work, the authors propose PCUP (Pipelined Cyclic Upstream Protocol) as the upstream MAC (medium access control) protocol for HFC (hybrid fiber coax) community access network. PCUP is designed with the intention of pipelining the upstream channel. This is achieved by proper station positioning, which measures the station propagation offset from the headend, and transmission scheduling, which assigns each station a transmission starting time and duration in a cycle. By taking into account the propagation offsets and transmission times, transmitted cells can appear back-to-back (i.e., pipelined) at the headend. Since only the active stations are scheduled to transmit in a cycle, a membership control mechanism, which runs a contention-based tree walk algorithm, is executed periodically to allow the stations to join or leave. The authors also compare PCUP with various schemes proposed to IEEE 802.14 committee.
PCUP: Pipelined cyclic upstream protocol over hybrid fiber coax
(1997-01-01)
Lin, YD
;
Wu, CJ
;
Yin, WM
;
資訊工程學系
;
Department of Computer Science
In order to bring NII (National Information Infrastructure) into the home, the community cable TV networks have to be reengineered to support two-way interactive services. In this work, the authors propose PCUP (Pipelined Cyclic Upstream Protocol) as the upstream MAC (medium access control) protocol for HFC (hybrid fiber coax) community access network. PCUP is designed with the intention of pipelining the upstream channel. This is achieved by proper station positioning, which measures the station propagation offset from the headend, and transmission scheduling, which assigns each station a transmission starting time and duration in a cycle. By taking into account the propagation offsets and transmission times, transmitted cells can appear back-to-back (i.e., pipelined) at the headend. Since only the active stations are scheduled to transmit in a cycle, a membership control mechanism, which runs a contention-based tree walk algorithm, is executed periodically to allow the stations to join or leave. The authors also compare PCUP with various schemes proposed to IEEE 802.14 committee.
Statistically optimized minislot allocation for initial and collision resolution in hybrid fiber coaxial networks
(2000-09-01)
Yin, WM
;
Lin, YD
;
資訊工程學系
;
Department of Computer Science
In a two-way hybrid fiber coaxial (HFC) network, the headend broadcasts in downstream channels, whereas all stations share the upstream channels. Hence, collision occurs when multiple stations send their bandwidth requests in a minislot, The headend determines how many minislots to allocate to manage collisions. This paper proposes a minislot allocation (SOMA) algorithm to optimize minislot throughput based on statistical estimation. A time proportional scheme is adopted to estimate the number of new requests in the initial resolution process. In addition, the number of retry requests in the collision resolution process is estimated by looking up a predetermined table of the most likely number of requests (MLR). In addition, SOMA is modified to reduce the request access delay by relaxing its allocation policy in a specific situation. We use a self-similar traffic model for simulation and analysis to compare SOMA with the optimal bound and the 3-ary tree algorithm.
Two-phase minislot scheduling algorithm for HFC QoS services provisioning
(2002-03-01)
Yin, WM
;
Wu, CJ
;
Lin, YD
;
資訊工程學系
;
Department of Computer Science
Data-Over-Cable Service Interface Specifications v1.1 (DOCSIS v1.1 ), developed for data transmissions over Hybrid Fiber Coaxial (HFC networks. defines five upstream services for supporting per-flow Quality of Services QoS). The cable modern termination system (CMTS) must periodically grant upstream transmission opportunities to the QoS flows based on their QoS parameters. However, packets may violate QoS requirements when several flows demand the same interval for transmission. This study proposes a two-phase, i.e.. the scheduling sequence determination phase and the minislot assignment phase. minislot scheduling algorithm to reduce the QoS violation rate. In the scheduling sequence determination phase, the flow whose packets are most unlikely to violate QoS is scheduled first. Then. in the minislot assignment phase, the scheduler allocates to a flow the available interval where the likelihood of packet violation is minimum. Simulation results demonstrate that our scheduling algorithm can reduce the QoS violation rate by 80-35% over that of the first-come-first-serve-random-selection algorithm. It increases the utilization by 25% as well, The two-phase minislot scheduling algorithm can work within the DOCSIS v1.1 framework.
Two-phase minislot scheduling algorithm for HFC QoS services provisioning
(2001)
Yin, WM
;
Wu, CJ
;
Lin, YD
;
資訊工程學系
;
Department of Computer Science
Data-Over-Cable Service Interface Specifications v1.1 (DOCSIS v1.1) defines five upstream services for supporting per-flow Quality of Services (QoS). The cable modem termination system (CMTS) must periodically grant upstream transmission opportunities to the QoS flows based on their QoS parameters. This study proposes a two-phase minislot scheduling algorithm to reduce the QoS violation rate. In the scheduling sequence determination phase, the flow whose packets are most unlikely to violate QoS is scheduled first. In the minislot assignment phase, the scheduler allocates to a flow the available interval where the likelihood of packet violation is minimum. Simulation results demonstrate that our scheduling algorithm can reduce the QoS violation rate by 80% similar to 35% over that of the first-come-first-serve-random-selection algorithm and increase the utilization by 25% as well.