Host-based intrusion detection system (HIDS) is a necessary component for network security, especially when more and more data are encrypted which makes network-based intrusion detection system lose its functionality of packet content inspection. After many years of research, it is widely acknowledged that system calls are the preferred data source for HIDS. In a recent paper, a novel semantic analysis approach was proposed and shown to achieve the best performance, as compared with various previous syntactic analysis schemes. The performance difference is profound for modern attacks. However, the semantic analysis approach requires considerable computational complexity. In this paper, we present a deep learning architecture which requires no data pre-processing and is easy to train. Experimental results show that our design has a better performance than the semantic analysis approach.

Sensing-based semi-persistent scheduling algorithm was developed by 3GPP as the standard for distributed resource selection in V2X sidelink communications. Sensing before resource selection largely reduces collision probability. However, we found that considerable collisions can happen if user equipments use different resource reservation intervals. An enhancement is proposed in this paper to prevent collisions. The proposed enhancement requires only simple computation and does not need additional information to be transmitted in sidelink control information. Simulations are conducted and results show that the improvement is significant. For our simulation scenario, the collision probability can be reduced by more than 77% under perfect channel condition. When channel condition is taken into consideration, the packet reception ratio can be improved by more than 6.41%.

Live streaming applications over wireless mobile networks have increased dramatically in recent years. In most current systems, the media center is capable of providing multiple streams of different qualities and each individual viewer selects its own stream based on channel condition and/or other considerations. This may result in inefficient use of radio resource. In this paper, we propose to let evolved node B, which has the channel conditions of all viewers, decide which streams should be delivered so that the total throughput is maximized, subject to the constraints that every viewer can successfully decode at least one stream and the radio resource consumed is under a pre-determined threshold. For a system that has many possible modulation and coding schemes, it requires huge computational complexity to obtain the optimum solution. We present a greedy algorithm which tends to find a solution that allows more viewers to decode higher quality streams. Simulation results show that the total throughputs achieved by the greedy algorithm for various scenarios are close to those of the optimum solutions.

Bufferbloat is a phenomenon caused by excessive buffering of packets that results in high latency, large jitter, as well as throughput degradation. It happens when a loss-based Transmission Control Protocol (TCP), such as New Reno or Cubic, is used for data transfer. A dynamic receive window adjustment (DRWA) scheme has recently been proposed to solve the bufferbloat problem. It was reported that, with the DRWA scheme, the bufferbloat problem can be effectively solved. However, we found that when there are multiple TCP connections sharing some bottleneck link, the ones with DRWA tend to lose their bandwidth share to those without DRWA. Moreover, when a user equipment establishes multiple TCP connections all implemented with DRWA and all connections pass through the same bottleneck link, the connection which is established last will dominate the bandwidth. In this paper, we present a simple scheme, called I-D (increasing-decreasing) two-state dynamic receive window adjustment, which according to simulation results can effectively solve the bufferbloat problem without the unfair bandwidth-dominating issues.

Traffic in wireless networks has become more diverse due to various applications running on smartphones. Moreover, traffic generated by background processes which has small amount of data and widely dispersed in time takes up a large portion of diverse data applications. To reduce signaling overhead due to frequent state transitions of radio resource control (RRC), the evolved nodeB (eNB) tends to keep User equipment (UE) in RRC connected state all the time. However, this approach leads to high UE power consumption and inefficient resource utilization at eNB, especially when UE has only background traffic. To cope with this problem, we propose three shaping schemes which transmit together accumulated background data to reduce both signaling overhead and power consumption at the same time. In addition, we analyze the performance of the proposed shaping schemes. The analytical results are verified with simulations.

Energy saving and quality of service (QoS) support are two important issues of Long-Term Evolution Advanced (LTE-A) wireless networks. Unfortunately, achieving high energy saving efficiency often implies degradation of QoS support. In this paper, we address the issue of QoS support under Discontinuous Reception (DRX), the power saving mechanism of LTE-A. Different from previous studies which analyzed average packet delay under DRX mechanism, we adopt packet loss ratio due to violation of delay bound as QoS requirements of real-time applications. The problem of QoS support under DRX mechanism is defined as an optimization problem to maximize average power saving under the constraint that the packet loss ratio is no greater than a pre-determined threshold. We derive packet loss ratio and energy saving efficiency given DRX parameter values and propose an approach to select appropriate DRX parameter values. Simulations are conducted to verify our analysis. We found that the analytical results match well with simulations. Moreover, the energy saving efficiency achieved by the selected DRX parameter values is very close to that of the optimum solution.

Power saving is an important issue when integrating the wireless LAN technology into mobile devices. Besides Quality of Service (QoS) guarantee, the IEEE 802.11e introduces an architecture called Scheduled Automatic Power-Save Delivery (S-APSD) aiming at delivering buffered frames to power save stations. In S-APSD, the Access Point (AP) schedules the Service Period (SP) of stations. To increase power efficiency, SPs should be scheduled to minimize the chance of overlapping. In a recent paper, an algorithm named Overlapping Aware S-APSD (OAS-APSD) was proposed to find the wake-up time schedule for a new Traffic Stream (TS) to minimize the chance of SP overlapping. The combination of OAS-APSD and HCF Controlled Channel Access (HCCA) was proved to outperform 802.11 Power Save Mode (PSM) with Enhanced Distributed Channel Access (EDCA) in power saving efficiency and QoS support. However, the OAS-APSD algorithm requires high online computational complexity which could make it infeasible for real systems. Without harming the optimality, this paper presents an efficient algorithm with much less complexity by exploiting the periodicity of service schedule. Because of largely reduced online computational complexity, the proposed algorithm is much more feasible than OAS-APSD.

Pattern-matching techniques have recently been applied to network security applications such as intrusion detection, virus protection, and spam filters. The widely used Aho-Corasick (AC) algorithm can simultaneously match multiple patterns while providing a worst-case performance guarantee. However, as transmission technologies improve, the AC algorithm cannot keep up with transmission speeds in high-speed networks. Moreover, it may require a huge amount of space to store a two-dimensional state transition table when the total length of patterns is large. In this paper, we present a pattern-matching architecture consisting of a stateful pre-filter and an AC-based verification engine. The stateful pre-filter is optimal in the sense that it is equivalent to utilizing all previous query results. In addition, the filter can be easily realized with bitmaps and simple bitwise-AND and shift operations. The size of the two-dimensional state transition table in our proposed architecture is proportional to the number of patterns, as opposed to the total length of patterns in previous designs. Our proposed architecture achieves a significant improvement in both throughput performance and memory usage.

The IEEE 802.16e standard known as Mobile WiMAX has recently been introduced. It is considered as one of the most promising wireless access technologies supporting high data throughput with low cost of deployment. Mobile WiMAX makes use of Orthogonal Frequency-Division Multiple Access (OFDMA) digital modulation scheme as the transmission method. With the constraint requires that all requests have to be mapped as a rectangle, it is shown that finding an optimum mapping solution is an NP-complete problem. Many burst mapping algorithms have been proposed, but none considered the case with prioritized requests. This paper presents an efficient packing algorithm for two-level requests with two targets: (1) map high (MUST part) priority data as much as possible; and (2) achieve high efficiency, reduces the number of unused slots, and minimizes the mapping information overhead. Simulation results show that the proposed algorithm achieves high efficiency.

In this paper, we present a resource allocation algorithm for OFDMA-based systems which handles both real-time and non-real-time traffic. For real-time traffic, the QoS requirements are specified with delay bound and loss probability. The resource allocation problem is formulated as one which maximizes system throughput subject to the constraint that the bandwidth allocated to a flow is no less than its minimum requested bandwidth, a value computed based on loss probability requirement and running loss probability. A user-level proportional-loss scheduler is adopted to determine the resource share for flows attached to the same subscriber station (SS). In case the available resource is not sufficient to provide every flow its minimum requested bandwidth, we maximize the amount of real-time traffic transmitted subject to the constraint that the bandwidth allocated to an SS is no greater than the sum of minimum requested bandwidths of all flows attached to it. Moreover, a pre-processor is added to maximize the number of real-time flows attached to each SS that meet their QoS requirements. We show that, in any frame, the proposed proportional-loss scheduler guarantees QoS if there is any scheduler which guarantees QoS. Simulation results reveal that our proposed algorithm performs better than previous works.

Hybrid coordination function (HCF) is proposed in IEEE 802.11e standard to support quality of service (QoS). HCF defines two channel access mechanisms; one of them is HCF controlled channel access (HCCA) designed for contention free transmission. In HCCA, each QoS-enhanced station (QSTA) obtains polled transmission opportunity (TXOP) from the hybrid coordinator (HC), which is in charge of scheduling the channel access and responding the poll messages to each QSTA. However, forwarding polling messages causes a significant overhead and degrades the channel utilization of data transmission. The goal of this work is to develop an efficient multipolling scheme that can reduce the overhead of polling messages. The simulation results show that the proposed algorithm can reduce the control overhead and, thus, improve the channel utilization significantly.

Power saving is an important issue when integrating the wireless LAN technology into mobile devices. The IEEE 802.11e introduced an architecture named as Scheduled Automatic Power Save Delivery (S-APSD) aiming at delivering buffered traffic to PS stations while meeting QoS requirement. In S-APSD, the access point (AP) of wireless LAN schedules the service periods (SP) of stations periodically. It is clear that the overlapping of SPs should be avoided to increase the power saving performance. An algorithm named Overlapping-Aware S-APSD (OAS-APSD) was proposed to find the service start time (SST) for a new traffic stream to minimize the chance of SP overlapping. However, it takes high on-line computational complexity and thus could be infeasible for real system. Reserving the optimality of finding the suitable SST, this paper presents an efficient scheduling algorithm to utilize the periodic nature of the service schedules. Therefore, with much less complexity, the AP can respond to the joining of new traffic streams in a much feasible fashion when implementing the S-APSD.

Piggyback is an effective way to reduce the MAC protocol overhead of wireless networks. This paper considers the physical data rate and transmission bit error to derive the criterion of piggyback. Numerical results show that the improvement of piggyback can reach 40% for some cases. For given the bit error rate and the data rate, we also provide the criterion for every combination in a table.

The advanced MIMO (multiple-input multiple-output) system can provide higher capacity gain or higher diversity gain in modern wireless networks. The capacity gain is achieved by interference cancellation technique to fully utilize the spatial degree of freedom. In a multiuser wireless system, the increased degrees of freedom provide the chance to select multiple wireless stations (STAs) to maximize the throughput. In this paper, we consider a scenario where the access point (AP) equipped with two antennas to simultaneously communicate with two STAs, each with single antenna. After obtaining the statuses of the size of buffered traffic and the achievable transmission rate, the AP should pair compatible STAs to minimize the loss of spatial degree of freedom. Therefore, three pairing algorithms are proposed and are evaluated through computer simulations. The algorithms have much less implementation complexity than the brute force pairing algorithm and achieve satisfactory performance of throughput.

This paper presents a bitmap-based hardware architecture for the Glushkov nondeterministic finite automaton (G-NFA), which recognizes a given regular expression. We show that the inductions of the functions needed to construct the G-NFA can be generalized to include other special symbols commonly used in extended regular expressions such as the POSIX 1003.2 format. Our proposed implementation can detect the ending positions of all substrings of an input string T, which start at arbitrary positions of T and belong to the language defined by the given regular expression. To achieve high performance, the implementation is generalized to the NFA, which processes K symbols in each operation cycle. We provide an efficient solution for the boundary condition when the length of the input string is not an integral multiple of K. Compared with previous designs, our proposed architecture is more flexible and programmable because the pattern matching engine uses memory rather than logic.

Home and office network gateways often employ a cost-effective embedded network processor to handle their network services. Such network gateways have received strong demand for applications dealing with intrusion detection, keyword blocking, antivirus and antispam. Accordingly, we were motivated to propose an appropriate fast scalable automaton-matching (FSAM) hardware to accelerate the embedded network processors. Although automaton matching algorithms are robust with deterministic matching time, there is still plenty of room for improving their average-case performance. FSAM employs novel prehash and root-index techniques to accelerate the matching for the nonroot states and the root state, respectively, in automation based hardware. The prehash approach uses some hashing functions to pretest the input substring for the nonroot states while the root-index approach handles multiple bytes in one single matching for the root state. Also, FSAM is applied in a prevalent automaton algorithm, Aho-Corasick (AC), which is often used in many content-filtering applications. When implemented in FPGA, FSAM can perform at the rate of 11.1Gbps with the pattern set of 32,634 bytes, demonstrating that our proposed approach can use a small logic circuit to achieve a competitive performance, although a larger memory is used. Furthermore, the amount of patterns in FSAM is not limited by the amount of internal circuits and memories. If the high-speed external memories are employed, FSAM can support up to 21,302 patterns while maintaining similar high performance.

Many network security applications rely on string matching to detect intrusions, viruses, spam, and so on. Since software implementation may not keep pace with the high-speed demand, turning to hardware-based solutions becomes promising. This work presents an innovative architecture to realize string matching in sub-linear time based on algorithmic heuristics, which come from parallel queries to a set of space-efficient Bloom filters. The algorithm allows skipping characters not in a match in the text, and in turn simultaneously inspect multiple characters in effect. The techniques to reduce the impact of certain bad situations on performance are also proposed: thebad-blockheuristic, a linear worst-case time method and a non-blocking interface to hand over the verification job to a verification module. This architecture is simulated with both behavior simulation in C and timing simulation in HDL for antivirus applications. The simulation shows that the throughput of scanning Windows executable files for more than 10000 virus signatures can achieve 5.64 Gb/s, while the worst-case performance is 1.2 Gb/s if the signatures are properly specified.

In the past few years, IEEE 802.11 wireless LANs (WLANs) has rapidly gained large popularity for broadband wireless access. With the growing of various applications, users are demanding features such as higher throughput while keeping respectable operation time for their devices. To provide higher system bandwidth utilization, multi-polling mechanisms are often employed to reduce protocol overhead. However, they require wireless stations (STAs) to spend much time in overhearing which tends to waste energy and reduce battery lifetime. In this paper, we propose an energy-efficient multi-polling mechanism which combines power management strategy with a low overhead Medium Access Control (MAC) protocol. The main idea is to put STAs into the Doze state and determine a suitable wake-up time schedule to statistically achieve desirable guarantee of bandwidth utilization. From both analysis and simulation results, we found that, compared with the original ordered-contention multi-polling scheme, our proposed mechanism saves up to 80% of energy for a network consisting of 20 polled STAs with 5% loss of system bandwidth utilization as tradeoff. The significant saving of energy is a consequence of alleviating the overhearing problem with well scheduled wake-up times for STAs.

Because of its accuracy, pattern matching technique has recently been applied to Internet security applications such as intrusion detection/prevention, anti-virus, and anti-malware. Among various famous pattern matching algorithms, the Aho-Corasick (AC) can match multiple pattern strings simultaneously with worst-case performance guarantee and is adopted in both Clam antivirus (ClamAV) and Snort intrusion detection open sources. The AC algorithm is based on finite automaton which can be implemented straightforwardly with a two-dimensional state transition table. However, the memory requirement prohibits such an implementation when the total length of the pattern strings is large. The ClamAV implementation limits the depth of the finite automaton and combines with linked lists to reduce memory requirement. The banded-row format is adopted to compress the state transition table and used as an alternative pattern matching machine in Snort. In this paper we present a novel implementation which requires small memory space and achieves high throughput performance. Compared with the banded-row format, our proposed scheme achieves 39.7% reduction in memory requirement for 5,000 patterns randomly selected from ClamAV signatures. Besides, the processing time of our proposed scheme is, on the average, 83.9% of that of the banded-row format for scanning various types of files. Compared with the ClamAV implementation with the same 5,000 patterns and files, our proposed scheme requires slightly more memory space but achieves 80.6% reduction in processing time on the average.

Various multi-polling schemes have been proposed to reduce the overhead resides in legacy IEEE 802.11 WLAN protocols. In particular, the two-step multi-polling (TSMP) scheme utilizes the acquired buffer status and channel condition to derive exact required time of each wireless station. Consequently, it seems to be easy to incorporate an energy saving schedule to prolong the operating time of the portable devices. However, even though it adopted the concept of rate adaptation, the TSMP scheme did not take into account frame retransmissions caused by transmission errors due to, say, fading of the wireless channel. The uncertain time spent on retransmission of former stations in the schedule may introduce energy-consuming overhearing for later ones. In this paper, we propose wake-up time schedules and an adaptive updating algorithm to save more energy for the later stations under the error-prone wireless environment. The proposed scheme is simple and thus quite feasible. Besides, from extensive simulation results, we found that the proposed solution is effective.

Abstract Compressed pattern matching (CPM) is an emerging research field addressing the problem: given a compressed sequence and a pattern, process the sequence with minimal (or no) decompression to find the pattern occurrence(s) in the uncompressed sequence. It can be applied to detect malwares and confidential information leakage in compressed files directly. In this paper, we report our work of CPM in Lempel–Ziv–Welch (LZW) compressed sequences. We propose an efficient bitmap‐based realization of the Amir–Benson–Farach algorithm. We also generalize the algorithm to find all pattern occurrences and report their absolute positions in the uncompressed sequence. Experiments are conducted to test the space requirements of our proposed generalization and two related CPM schemes which can also be realized with bitmaps. Results show that our proposed generalization requires the least amount of storage for moderate and long patterns. We also conduct experiments to compare the throughput performance of our proposed generalization with these two related CPM schemes and the decompress‐then‐search scheme. Results show that our proposed generalization outperforms the decompress‐then‐search scheme significantly. When scanning a file with pattern occurrences, our proposed generalization performs slightly better than the two related CPM schemes. The difference is significant when scanning a file with no pattern occurrence. Copyright © 2008 John Wiley & Sons, Ltd.

Because of its accuracy, signature matching is considered an important technique in anti-virus/worm applications. Among some famous pattern matching algorithms, the Aho-Corasick (AC) algorithm can match multiple patterns simultaneously and guarantee deterministic performance under all circumstances and thus is widely adopted in various systems, especially when worst-case performance such as wire speed requirement is a design factor. However, the AC algorithm was developed only for strings while virus/worm signatures could be specified by simple regular expressions. In this paper, we generalize the AC algorithm to systematically construct a finite state pattern matching machine which can indicate the ending position in a finite input string for the first occurrence of virus/worm signatures that are specified by strings or simple regular expressions. The regular expressions studied in this paper may contain the following operators: * (match any number of symbols), ? (match any symbol), and {min,max} (match minimum ofmin, maximum ofmaxsymbols), which are defined in ClamAV, a popular open source anti-virus/worm software module, for signature specification.

As the wireless LAN (WLAN) becomes prevalent, users are demanding more and more features such as high throughput and low power consumption. To provide higher channel efficiency, contention-based multipolling mechanism was proposed to improve the single polling and contention-free multipolling mechanisms. However, when this medium access control (MAC) protocol is used, wireless stations would need to spend much time in overhearing which tends to waste energy and reduce battery lifetime. We propose a power efficient multipolling mechanism to arrange wireless stations into groups and put them into sleep mode when other stations are transmitting. From the simulation results, we find the proposed mechanism can address the issue of overhearing while also keeping the flexibility and high channel efficiency properties.

For QoS requirements of real-time traffic, IEEE 802.11 working group introduces a QoS-aware channel access mechanism, called hybrid coordination function (HCF), which consists of contention-based enhanced distributed channel access (EDCA) and contention-free HCF controlled channel access (HCCA). The TXOP allocation and the admission control units of the HCCA reference scheduler are only appropriate for constant bit rate (CBR) flows. It may result in serious packet loss for variable bit rate (VBR) flows. In this paper, we propose a simple admission control algorithm which adopts Gaussian distribution to approximate VBR traffic. Numerical results obtained from computer simulations show that our proposed algorithm can effectively and efficiently allocate transmission opportunity (TXOP) durations to QoS-enhanced stations (QSTAs) to guarantee a predefined packet loss probability. Moreover, our proposed scheme can easily handle multiple VBR flows of the same QSTA to get the advantage of multiplexing gain.

Deterministic packet marking (DPM) has recently been proposed as an alternative approach for IP traceback to identify the ingress router interfaces that receive and forward attack packets. Scalable, simple to implement, and no extra bandwidth required are the major advantages of DPM. Besides, it allows incremental deployment and service providers can implement it without revealing their internal network topology. Several DPM schemes have recently been proposed. Unfortunately, these schemes suffer from either a high false positive rate when there are multiple simultaneous attackers or a high false negative rate when packet loss happens because of congestion. In this paper, we propose and evaluate the false positive and false negative rates of a novel DPM scheme that is much scalable than the previous schemes. In the proposed DPM scheme, we use multiple hash functions to reduce the probability of address digest collision. Our analysis and computer simulations show that the proposed DPM scheme results in much smaller false positive rate than previous schemes. Moreover, by modifying the reconstruction procedure, one can control the false negative rate to combat packet loss with slight increase of false positive rate. With eight different kinds of marks, the expected number of packets required to reconstruct an interface address is only 22.

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 bitmap 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.

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 is 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.

The IEEE 802.11g standard has been proposed to enhance the data rate of wireless LAN connections up to 54 Mbps, while ensuring backward compatibility with legacy 802.11b devices at the same time. However, in a hybrid 802.11b/g network, the throughput of 802.11g devices is compromised because of not only the overhead to interoperate with 802.11b devices, but also the unbalanced medium contentions between devices with different versions of the standard. We propose a hybrid Markov-chain based model to quantify this throughput reduction effect in 802.11b/g mixed scenarios. The analytical model is further verified with simulations and field measurements under different station numbers, data rates, and data packet sizes. In addition, a simple frame-bursting technique is shown to balance the throughput between 802.11b and 802.11g stations.

Identifying the sources of an attack is an important task in the Internet security area. An attack could consist of a large number of packet streams generated by many compromised slaves that consume resources associated with various network elements to deny normal services or a few offending packets to disable a system. Several techniques based on probabilistic samples of transit packets have been developed, to determine the sources of large packet flows. It seems that logging of packet digests is necessary for traceback of an individual packet. A clever technique based on Bloom filters has recently been proposed to generate the audit trails for each individual packet within the network. The scheme is effective. However, the storage requirement is approximately 0.5% of the link capacity, which becomes a problem as link capacity increases. In this paper, we propose packet digesting schemes for flows and sets of packets sharing the same source and destination addresses. Compared with the individual packet digesting scheme, these schemes can achieve similar goals and are much more scalable. Simulations with real Internet traffic show that the storage requirements of our proposed schemes are one to two orders of magnitude lower.

Packet classification is an important component of new Internet routers to support various services such as quality of service guarantee and virtual 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 nested binary tuple space search algorithm presented [V.Srinivasan, 2001] was designed for two-field conflict free filter sets. The time complexity of the nested binary search algorithm is ([log(W + 1)])/sup 2/, where W is the length of the fields. In this paper, we investigate the impact of built-in markers and associated pre-computation mechanisms on such an algorithm employs unified markers and associated pre-computation mechanisms on such an algorithm. We found that, if the nested binary search algorithm employs unified markers and identical pre-computation manner for them, the search process may result in a "no match" while there exist matching filters. The incorrect decision is caused by conflicts between some markers and filters. We present in this paper a necessary and sufficient condition to determine whether or not markers generated by a filter conflict with another filter. Besides, we further propose a novel search algorithm which can find the best matching filter in 2[log(W + 1)] probes. Although more resolution filters are added, empirical results for random filter sets show that our scheme requires less memory than the nested binary search algorithm because no primary markers (and the secondary markers of primary markers) are needed.

In order to exploit the nonlinear time-varying property of network traffic, the traffic flow from controlled sources is described by a fuzzy autoregressive moving-average model with auxiliary input (fuzzy ARMAX process), with the traffic flow from uncontrolled sources (i.e., cross traffic) being described as external disturbances. In order to overcome the difficulty of the transmission delay in the design of congestion control, the fuzzy traffic model is translated to an equivalent fuzzy predictive traffic model. A fuzzy adaptive flow control scheme is proposed to avoid congestion at high utilization while maintaining good quality of service. By use of fuzzy adaptive prediction technique, the difficulties in congestion control design due to nonlinearity, time-varying characteristics, and large propagation delay can be overcome by the proposed adaptive traffic control method. A comparative evaluation is also given to show the superiority of the proposed method.

Packet classification is an important component of new Internet routers to support various services such as quality of service guarantee and virtual 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 nested binary tuple space search algorithm was designed for two-field conflict free filter sets. The time complexity of the nested binary search algorithm is ([log(W + 1)])/sup 2/, where W is the length of the fields. To ensure that the filter set is conflict free, the authors assumed that conflicts are resolved by adding resolution filters. In this paper, we propose a novel search algorithm which can find the best matching filter in 2[log(W + 1)] probes. Although more resolution filters are added, empirical results for random filter sets show that our scheme requires less memory than the nested binary search algorithm because no primary markers (and the secondary markers of primary markers) are needed.

Future broadband integrated services networks based on asynchronous transfer mode (ATM) technology are expected to support multiple types of multimedia information with diverse statistical characteristics and quality of service (QoS) requirements. To meet these requirements, efficient scheduling methods are important for traffic control in ATM networks. Among general scheduling schemes, the rate monotonic algorithm is simple enough to be used in high-speed networks, but does not attain the high system utilization of the deadline driven algorithm. However, the deadline driven scheme is computationally complex and hard to implement in hardware. The mixed scheduling algorithm is a combination of the rate monotonic algorithm and the deadline driven algorithm; thus it can provide most of the benefits of these two algorithms. In this paper, we use the mixed scheduling algorithm to achieve high system utilization under the hardware constraint. Because there is no analytic method for schedulability testing of mixed scheduling, we propose a genetic algorithm-based neural fuzzy decision tree (GANFDT) to realize it in a real-time environment. The GANFDT combines a GA and a neural fuzzy network into a binary classification tree. This approach also exploits the power of the classification tree. Simulation results show that the GANFDT provides an efficient way of carrying out mixed scheduling in ATM networks.

The rate monotonic algorithm has been proposed to be used along with traffic shapers to provide quality of service guarantee in ATM networks. Admission criterion and a fast admission control procedure were developed assuming that cell arrivals are periodic. For bursty traffic, this assumption is conservative and may significantly reduce the efficiency of bandwidth utilization. We present an efficient admission criterion for bursty sources. We assume that the traffic generated by each source is regulated with a leaky bucket regulator. Our admission criterion takes into consideration the traffic characteristics. Since the arrival pattern changes in every hop, every network node is required to know how many hops a connection has traversed. We derive the admission criterion for a network (such as the Internet) which allows different users to transmit packets of different lengths. Numerical results show that, compared with the conservative criterion which assumes periodic traffic sources, system utilization could be largely improved.

The paper proves some topological properties of bitonic sorters, which have found applications in constructing, along with banyan networks, internally nonblocking switching fabrics in future broadband networks. The states of all the sorting elements of an N/spl times/N bitonic sorter are studied for four different input sequences {a/sub i/}/sub i=l//sup N/, {b/sub i/}/sub i=l//sup N/, {c/sub i/}/sub i=l//sup N/, and {d/sub i/}/sub i=l//sup N/ where a/sub i/=i-1, b/sub i/=N-i, and the binary representations of c/sub i/ and d/sub i/ are the bit reverse of those of a/sub i/ and b/sub i/, respectively. An application of these topological properties is to help design efficient fault diagnosis procedures. We present an example for detecting and locating a single faulty sorting element under a simple fault model where all sorting elements are always in the straight state or the cross state.

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.

We present a definition of burstiness for delay sensitive traffic streams in terms of a function, i.e., the cell loss probability of a bufferless multiplexer at all non-negative link capacities. Some properties of the definition are proved. One property implies any definition of burstiness in terms of a real number may not be appropriate. The other property implies the commonly used moment matching method in approximating traffic sources may not be appropriate either. We also present a quantization algorithm for networks which provide only finitely many bit rates for describing traffic characteristics. Our proposed quantization algorithm guarantees the quantized version is always burstier than the original source and thus can be used to design call admission control scheme for an ATM network.

Several distributed power control algorithms that can achieve carrier-to-interference ratio (CIR) balancing with probability one have been proposed previously for cellular mobile systems. 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 Grandhi et al. [1994]. The excellent performance and the fully distributed property make our proposed algorithm a good choice for cellular mobile systems.

In this paper, we present a real-time computation algorithm based on the bufferless fluid flow model [Jabbari and Yegenolu, 1992] 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 [Murase et al., 1991], 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 [Elwalid and Mitra, 1993].

The maximum throughput of a single-stage non-blocking input-queued switch such as the sort-banyan network is shown to be 0.586 under the uniform traffic model. It can be increased to 0.88 or 0.97 respectively if the switch is speeded up by a factor of 2 or 3. Hui and Lee (1992) showed that, for a large scale three-stage switch built with sort-banyan switch modules, the maximum throughput reduces to 0.458. The analysis was performed based on the assumption that the number of middle-stage switch modules is equal to the number of input/output links of a switch module. In the paper, the authors study the effect of increasing the number of middle-stage switch modules and speeding up the switch. Numerical results are obtained and verified by computer simulations for various combinations. For example, with a speedup factor of 2, the maximum throughput can be improved to 0.85 if the number of middle-stage switch modules is doubled.>

Bitonic sorters have recently been proposed to construct along with banyan networks the switching fabric of future broadband networks. Unfortunately, a single fault in a bitonic sorter may have disastrous consequences for the switching system. Therefore, a bitonic sorter must be proved to be free of faults before it can be used. We study the topological properties of bitonic sorters and present an efficient fault diagnosis procedure to detect, locate, and identify the fault type of single faults. Our diagnosis procedure can detect most single faults in two tests. Faults which cannot be detected in two tests can always be detected in four tests. Several binary search techniques are developed to locate a faulty sorting element (i.e. a 2/spl times/2 sorter).>

The banyan network, and networks topologically equivalent to it, have recently been adopted as interconnection networks in multiprocessor systems. Often, a multiprocessor system is reconfigured when the banyan network becomes faulty. It is possible to avoid a complicated reconfiguration process as long as the faulty banyan network still possesses the dynamic full access (DFA) property. In this paper, we determine a necessary and sufficient condition for a faulty banyan network to possess the DFA property and design a test procedure based on the condition. The test procedure can be used to decompose a faulty banyan network into subsystems possessing the DFA property. We also evaluate the probability that a banyan network loses the DFA property, given the number of faulty switching elements. It is found that as long as faults do not occur in switching elements located in the first and last stages, this probability is very small, even when there are quite a few faulty switching elements.>

In order to utilize multiple-pass routing schemes, a faulty banyan network must possess the dynamic full access (DFA) property. The authors determine a necessary and sufficient condition for a banyan network to possess the DFA property and design a general testing procedure based on the condition. They also enumerate the probability that a banyan network loses the DFA property, given the number of faulty switch elements. It is found that, as long as faults do not occur in switch elements located in the first and last stages, this probability is very small even when there are quite a few faulty switch elements. Therefore, multiple-pass routing schemes can be very useful if the switch elements in the first and last stages are well protected.>

A fair high-speed copy network for multicast packet switching is described. The authors modify the architecture of the copy network proposed by T.T. Lee (1988) to make it fair to all the inlets, and reduce the clock rate requirement of the switching fabric. Fairness is achieved by adding a banyan network to perform cyclic shifts in front of the copy network. A pipelined architecture is proposed to avoid a huge internal speed-up. The clock rate requirement of the proposed copy network is evaluated and compared with that of the original design. It is found that the clock rate requirement can be reduced significantly if the number of inlets is larger than 64.>

A new self-routing network constructed from the sorting and the routing cells is proposed. The complexity of the new network is roughly twice as much as that of a pure banyan network. The new network can be viewed as an implementation of the load-sharing network which requires a very simple management. Its performance under uniform and nonuniform traffic models is analyzed for the unbuffered case. It is found that a higher degree of nonuniformity results in a better performance for certain forms of nonuniform traffic matrices. Simulations are performed to obtain the normalized throughputs and mean packet delays for the single-buffered case. Different from single-buffered pure banyan networks, the mean delay of high-traffic packets is smaller than that of low-traffic packets for a particular form of nonuniform traffic matrices. In addition to performance improvement, the new network is easy to diagnose. Some variations of the proposed network are also studied.>

The limiting throughput efficiency of the classic go-back-N automatic repeat request (ARQ) scheme for burst-error channels described by E. N. Gilbert's (1960) two-state Markov model is evaluated based on regenerative theorems. In Gilbert's model, the channel has two possible states, a quiet state and a noisy state. Let p and q denote respectively the probabilities of transition from the quiet state or the noisy state to itself. Numerical results reveal that the classic go-back-N ARQ scheme performs better under Gilbert's model than an independent error model if and only if p+q>or=1. The technique presented can be applied to evaluate the performance of a wide variety of ARQ schemes for burst-error channels.>