Browsing by Author "Lee, TH"

Now showing 1 - 20 of 36

A deterministic packet marking scheme for tracing multiple Internet attackers
(2005)
Lee, TH
;
Huang, TYW
;
Lin, I
;
電信工程研究所
;
Institute of Communications Engineering
Deterministic packet marking (DPM) has recently been proposed as an alternative approach for IP traceback. It requires no extra bandwidth and is backward compatible with Internet equipments that do not implement it. Moreover, service providers can implement it without revealing their internal network topology. Unfortunately, the false positive rate could be very high if multiple hosts use the same source address to attack the victim simultaneously. Even worse, no source will be identified if attackers change their source addresses for every packet they send. These two problems can be solved with a modified DPM scheme which we called DPM with address digest (DPM-AD). We found that the false positive rate of the DPM-AD scheme could be much higher than it was claimed when the number of ingress router interfaces is larger than the number of attackers. In this paper, we propose and evaluate the false positive rate of a novel DPM scheme that is much more scalable than the DPM-AD scheme. Our analysis and simulation results show that the proposed DPM scheme can trace 1K simultaneous attackers at a false positive rate less than 0.5% with acceptable reconstruction complexity.
A fast computation algorithm for connection admission control of delay sensitive traffic with multiple quality of service requirements
(1996-08-01)
Lee, TH
;
Lai, KC
;
交大名義發表
;
電子工程學系及電子研究所
;
National Chiao Tung University
This paper presents a fast computation algorithm for connection admission control for heterogeneous delay sensitive traffic in ATM networks. Cell loss probability is adopted as the measure of quality of service. In our study, cells of each connection are allowed to have two different loss priorities and the aggregate traffic can have more than two. To cope with multiple quality of service requirements, the link capacity is divided into several bands. For simplicity, each traffic source is assumed to alternate between active and idle periods. However, the results can be extended to traffic sources having more than two states. Upper bounds of actual cell loss probabilities are derived based on the bufferless fluid flow model. Numerical results show that the upper bounds are close to the actual cell loss probabilities.
A fault tolerant shared memory ATM switch
(1997)
Lee, TH
;
Liu, SJ
;
電信工程研究所
;
Institute of Communications Engineering
In this paper, we present a fault tolerant ATM switch based on the shared memory architecture [6]. We study first the effect of a single fault to an ATM switch. Basically, a single fault in an ATM switch results in cell mis-delivery, out-of-sequence, corruption, and/or loss. We propose to add output port address, sequence number, and CRC checking to each cell for on-line fault detection. Some single faults which cause cell loss cannot be detected without wing multiple switch copies. Therefore, we propose to we a duplex system for detecting these faults and also for fault tolerant. We then design a fault tolerant switch based on the shared memory architecture [6]. Our proposed implementation can tolerate a single fault without losing cells in most cases.
A fully distributed power control algorithm for cellular mobile systems
(1996-05-01)
Lee, TH
;
Lin, JC
;
電信工程研究所
;
Institute of Communications Engineering
Several distributed power control algorithms that can achieve carrier-to-interference ratio (CIR) balancing with probability one have been proposed recently for cellular mobile systems [5]-[8], In these algorithms, only local information is used to adjust transmitting power, However, a normalization procedure is required in each iteration to determine transmitting power and, thus, these algorithms are not fully distributed, In this paper, we present a distributed power control algorithm which does not need the normalization procedure, We show that the proposed algorithm can achieve CIR balancing with probability one, Moreover, numerical results reveal our proposed scheme performs better than the algorithm presented in [7], which has the best performance among the distributed power control algorithms studied in [5]-[8], The excellent performance and the fully distributed property make our proposed algorithm a good choice for cellular mobile systems.
A minimum output burstiness traffic scheduling algorithm
(1999-11-01)
Kuo, YE
;
Lee, TH
;
傳播研究所
;
電信工程研究所
;
Institute of Communication Studies
In this paper, we present a traffic scheduling algorithm, called the Delay-Bound Monotonic with Average Rate Reservation (DM/ARR), which generates minimum output burstiness streams. We assume that connection i is policed by the leaky bucket algorithm with parameters (sigma(i), sigma(i)) where sigma(i) is the bucket size (or burstiness) and p(i) is the leaky rate. Compared with the totally isolated scheme where connection i is allocated a bandwidth r(i) = max{sigma(i)/d(i),rho(i)} (d(i) is the delay bound requirement of connection i), the DM/ARR algorithm has a better performance in the sense that it has a larger admission region. We prove that. among all possible scheduling algorithms that satisfy the delay bound requirements of established connections, DM/ARR results in the minimum output burstiness. This is important because a smaller burstiness implies a smoother traffic and thus the receiver (or next switch node in a multihop network) can handle it more easily. Numerical results show that the admission region of the DM/ARR algorithm is close to that of the earliest deadline first [1] algorithm. A packetized version is studied for ATM networks.
A parallel automaton string matching with pre-hashing and root-indexing techniques for content filtering coprocessor
(2005)
Tseng, KK
;
Lin, YD
;
Lee, TH
;
Lai, YC
;
交大名義發表
We propose a new Parallel Automaton string matching approach and its hardware architecture for content filtering coprocessor. This new approach can improve the average matching time of the Parallel Automaton with Pre-Hashing and Root-Indexing techniques. The Pre-Hashing technique uses a hashing function to verify quickly the text against the partial patterns in the Automaton, and the Root-Indexing technique matches multiple bytes for the root state in one single matching. A popular Automaton algorithm, Aho-Corasick (AC) is chosen to be implemented by adding the two techniques; we employ these two techniques in a memory efficient version of AC namely Bilmap AC For the average-case time, our approach improves Bitmap AC by 494% and 224% speedup for URL and Virus patterns, respectively. Since Pre-Hashing and Root-Indexing techniques can be concurrently executed with Bitmap AC in the hardware, our proposed approach has the same worst-case time as Bitmap AC.
A study on the distributed power control for cellular mobile systems
(1996)
Lee, TH
;
Lin, JC
;
傳播研究所
;
Institute of Communication Studies
Adaptive line search algorithm for packet classification
(2002)
Ting, PC
;
Hsu, YS
;
Lee, TH
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Packet classification has become an important component of routers to support various services such as quality of service guarantee and virtual 2 private network. Basically, packet classification can be considered as a-process looking for the best matching filter in a filter set for several fields selected from packet header. Various data structures and search algorithms have been proposed for such multi-field packet classification. In particular, the Line Search algorithm presented in [9] was designed for two-dimensional tuple space based packet classification. Since every column has to be examined, the time complexity of the Line Search algorithm is close to that in the worst case, i.e., (W+1)[log(W+1)], where W denotes the length of the fields. In this paper, we present two pruning criteria to improve the average performance. Empirical results for random filter sets show that the Line Search scheme incorporating these two pruning criteria reduces the average search time by nearly 90%. Besides, in order to improve the lookup time in the worst case, we further propose a new search algorithm, called Adaptive Line Search which can find the best matching filter in k[log(W+1)] probes, where k is a tunable parameter with 2 ! k: W+1 Achieving better lookup time in the worst case, i.e. smaller k, requires adding more filters to the original filter set. We perform a thorough experimental study of tradeoffs between memory requirement and lookup performance for various k and the results show that for k = 2 our Adaptive Line Search scheme requires about two times of memory space consumed by the Line Search scheme, but reduces significantly the maximum number of hash probes by nearly 94%.
Admission control for ATM networks using rate monotonic traffic scheduling algorithm
(1997)
Lee, TH
;
Chang, AB
;
交大名義發表
;
傳播研究所
;
National Chiao Tung University
Rate monotonic scheduling algorithm had been shown [1] to be the optimum static priority assignment scheme for an environment where packets are of variable length and a higher priority packet can preempt a lower priority one without causing any loss. It is optimum in the sense that if a set of m constant bit rate connections are schedulable (i.e., every packet is served before its succeeding packet arrives) with any static priority assignment scheme, then they are schedulable with rate monotonic scheduling algorithm. In this paper, we study the schedulability issue of rate monotonic scheduling algorithm for ATM networks where all packets are of the same length. We prove a necessary and sufficient condition for a set of m constant bit rate connections to be rate monotonic schedulable. Based on the necessary and sufficient condition, we design a simple admission control algorithm. We also present a sufficient condition which can be used for fast admission control if there are only a few possible periods for the connections.
Admission control for variable spreading gain CDMA wireless packet networks
(2000-03-01)
Lee, TH
;
Wang, JT
;
電信工程研究所
;
Institute of Communications Engineering
A technique for variable spreading gain code-division multiple access (VSG-CDMA) with transmit power control has recently been proposed [4], [5] to provide integrated services in a wireless packet network. System capacities of VSG-CDMA networks with and without considering user activity factors were derived. The analysis gives a lower bound of system capacity because a user's transmitted power is considered part of the interference to its own signal. In this paper, we present an optimistic upper bound assuming that there is no multipath fading or the energy of a signal in all multipath components can be fully resolved. An optimum power vector assignment and a simple criterion for all users to simultaneously achieve their quality of service (QoS) requirements tin terms of bit energy-to-interference density ratios) are derived. We found from numerical examples that, compared with the lower bound given in [4] and [5], significant improvement can be obtained if multipath fading can be satisfactorily handled. Several access control schemes are also studied to guarantee delay bound requirements. Simulation results reveal that more connections can be further accommodated with access control.
Admission control for VSG-CDMA systems supporting integrated services
(1998)
Lee, TH
;
Wang, JT
;
電信工程研究所
;
Institute of Communications Engineering
Variable spreading gain CDMA (VSG-CDMA) technique with transmitting power control has recently been proposed [4] to provide integrated services in a wireless packet network System capacities of VSG-CDMA systems with and without considering user activity factors were derived based on some intuitive arguments. The analysis is imprecise because a user's transmitted power is considered part of the interference to its own signal. In this paper, we present a more precise analysis. An optimal power vector assignment and a simple criterion for all users to achieve simultaneously their quality of service. requirements (in terms of bit energy-to-interference density ratios) are derived. We found from numerical examples that, compared with the rough analysis given in [4], significant improvement can be obtained. An access control scheme is also studied to guarantee delay bound requirements. Simulation results reveal that more connections can be further accommodated with access control.
Admission control for VSG-TDMA/SS multimedia cellular networks
(1998)
Wang, JT
;
Lee, TH
;
電信工程研究所
;
Institute of Communications Engineering
In this paper, we address the admission control issue for the TDMA/SS (Time division multiple access with spread spectrum) system for multimedia services. In the TDMA/SS system, time is divided into frames and each frame is further divided into slots. Only one user is allowed to transmit in a slot and thus spread spectrum technique is adopted to combat inter-cell interference. A packet can occupy more than one slot, depending on the user's data rate and quality of service requirement. We derive a necessary and sufficient condition for a group of users to be admissible for the TDMA/SS system and prove that its admission region contains that of the TDMA/CDMA system. In the TDMA/CDMA system, time is also divided into frames and each frame consists of several slots. The difference is that every packet occupies exactly one slot and multiple users can transmit their packets in the same slot. Numerical results show that the admission region of the TDMA/SS system can be significantly larger than that of the TDMA/CDMA system. To further increase bandwidth utilization and guarantee delay bound requirements, several access control schemes are proposed. Simulation results are obtained for these access control schemes.
Background noise cancellation for hands-free communication system of car cabin using adaptive feedforward algorithms
(2003)
Wu, JD
;
Lee, TH
;
Bai, MSR
;
機械工程學系
;
Department of Mechanical Engineering
This paper describes the background noise attenuation for hands-free communication systems of car cabins using adaptive feedforward noise control algorithm. For hands-free telephone system, the quality of communication usually is effect by background noise such as engine noise and aerodynamic noise. In the present study, an active noise control (ANC) design for reducing car cabin periodic background noise from engine and broadband random noise using adaptive feedforward control are investigated. The control algorithm is based on the well-known filtered-x least mean square (FXLMS) with multi-sine synthesized reference signal and frequency counting technology is implemented on a digital signal processor (DSP) platform. Experimental results indicated that the proposed design was effective suppressing 15 dB in periodic engine noise and 2-3 dB in broadband random background noise.
Characterization of delay-sensitive traffic
(1998-08-01)
Lee, TH
;
Lai, KC
;
電信工程研究所
;
電信研究中心
;
Institute of Communications Engineering
Resource allocation is necessary for a network which guarantees quality of service (QoS), In this paper we first present a definition for a traffic stream to be burstier than another traffic stream. The definition is based on the loss probability of a bufferless multiplexer and thus is appropriate for delay-sensitive traffic which cannot tolerate queueing delay caused by buffering. An optimum quantization algorithm is then derived for source characterization. The optimally quantized version achieves minimum loss rate for all possible allocated bandwidths under the condition that it is burstier than the real traffic. The quantized source is called a pseudosource and can be used by the network for resource allocation. Some numerical examples are studied. Results show that, for a bufferless multiplexer, the allocated bandwidth based on optimally quantized pseudosources is only slightly greater than the minimum bandwidth required to meet the requested QoS.
Correlated token bucket shapers for multiple traffic classes
(2004)
Lee, TH
;
電信工程研究所
;
Institute of Communications Engineering
Traffic shaping is an important technique for quality of service guarantee in a network that provides integrated services. It Is often used in an access node to regulate user traffic submitted to the network. Since the leaky bucket algorithm has been selected by international standard organizations as the traffic policing algorithm, an ideal shaper should change the temporal characteristics of user traffic to conform to the criterion. It is well known that token bucket is equivalent to leaky bucket and is often used to name shapers that shape traffic in accordance with the leaky bucket criterion. However, in standard documents, the leaky bucket algorithm was described for a single traffic class. There is no discussion for multiple traffic classes. One possible way is to use multiple independent shapers such that each traffic class is regulated by one shaper independent of other traffic classes. This approach is simple but may not be reasonable. In this paper, we propose to use multiple correlated token buckets to shape user traffic with multiple classes. In our proposed architecture, cheaper traffic classes can utilize the unused bandwidth subscribed for more expensive traffic classes. Besides, each traffic class Is guaranteed a minimum bandwidth specified by its leaky bucket parameters.
Design and performance evaluation of a distributed knockout switch with input and output buffers
(1996-06-01)
Cheng, YJ
;
Lee, TH
;
Shen, WZ
;
電子工程學系及電子研究所
;
電信工程研究所
A nonblocking ATM switch with input and output buffers is proposed and its performance is evaluated. The proposed switch is a modified version of an existing distributed-knockout-switch. In the proposed switch architecture, an input port with a nonempty queue always sends a cell to the switch at the beginning of each time slot. The cell sent out from an input port reaches either its destination output port (if it wins the contention) or a different input port (if it loses). A priority scheme is adopted to preserve service-cell sequencing. A cell is discarded if it loses a predetermined number of consecutive contentions. A modified architecture which can provide multicast service is also presented. Simulations are performed to evaluate the proposed switch architecture under both uniform- and hot-spot nonuniform-traffic models.
Design and performance evaluation of a distributed knockout switch with input and output buffers
(1996-06-01)
Cheng, YJ
;
Lee, TH
;
Shen, WZ
;
電子工程學系及電子研究所
;
電信工程研究所
A nonblocking ATM switch with input and output buffers is proposed and its performance is evaluated. The proposed switch is a modified version of an existing distributed-knockout-switch. In the proposed switch architecture, an input port with a nonempty queue always sends a cell to the switch at the beginning of each time slot. The cell sent out from an input port reaches either its destination output port (if it wins the contention) or a different input port (if it loses). A priority scheme is adopted to preserve service-cell sequencing. A cell is discarded if it loses a predetermined number of consecutive contentions. A modified architecture which can provide multicast service is also presented. Simulations are performed to evaluate the proposed switch architecture under both uniform- and hot-spot nonuniform-traffic models.
Design of a real-time call admission controller for ATM networks
(1996-10-01)
Lee, TH
;
Lai, KC
;
Duann, ST
;
電子工程學系及電子研究所
;
電信工程研究所
In this paper, we present a real-time computation algorithm based on the bufferless fluid flow model [6] for call admission control (CAC) on one link of an asynchronous transfer mode (ATM) network with heterogeneous bursty traffic, Cell loss probability is adopted as the measure of quality-of-service (QoS), Our computation algorithm requires a constant memory size and needs only two multiplications and one division to determine whether a connection request can be accepted or not. It is known [7], that due to the interference between different types of traffic the individual cell loss probability may not meet the requirement even though the global one does, In this paper, we provide a close upper-bound for individual cell loss probability which can easily be obtained with our computation algorithm, Numerical examples using typical traffic parameters are studied to corroborate the upper-bound, We also compare the performance of the investigated CAC scheme with that of the effective bandwidth technique [9].
Estimates of loss probabilities for delay-sensitive traffic in ATM networks
(1996-06-20)
Lai, KC
;
Lee, TH
;
傳播研究所
;
電控工程研究所
;
Institute of Communication Studies
Simple estimates of loss probabilities for heterogeneous delay-sensitive traffic in ATM networks are presented. Cells of different connections can have different loss priorities. Numerical results show that the estimates, which are derived from the bufferless fluid flow model, are close to the actual cell loss probabilities.
Fast admission control for rate monotonic schedulers
(1999-01-01)
Lee, TH
;
Chang, AB
;
交大名義發表
;
傳播研究所
;
National Chiao Tung University
Rate monotonic traffic scheduling algorithm had been shown [1] to be the optimal static priority assignment scheme. The system model studied in [1] can be considered (although not realistic) as a preemptive multiplexer which accepts constant bit rate connections that generate packets periodically. The multiplexer adopts a service discipline such that a lower priority packet can be preempted at any stage by a higher priority one without any loss. The constraint is that every packet has to complete its service before the arrival of its succeeding packet generated by the same connection. In this paper, we study the schedulability problem of rate monotonic schedulers for a fixed-length packet switched network such as the ATM network. A necessary and sufficient condition for a set of m constant bit rate connections to be rate monotonic schedulable is first derived and then utilized to design fast admission control algorithms. One of our algorithms computes in advance the minimum period of a connection which can be accepted given a set of existing connections.