Telecommunications and Wireless

Cooperative Source and Channel Coding
Cooperative Regions and Partner Choice in Coded Cooperative Systems
Power Efficient Multimedia Wireless Communications
Peer-to-Peer Video Streaming System
Sensor Management
Unlocking Capacity for Wireless Access Networks through Robust Cooperative Cross-Layer Design
Cooperative Networks: Implementation of Cooperative MAC Protocols for Wireless LANs
Designing Medium Access Control for Cooperative Networks
High-Speed Network Intrusion Detection and Prevention
Lightwall: A Light-Weight Distributed Enforcement Architecture for Centralized Network Control Policy
Data Center Networks

Cooperative Source and Channel Coding

Participating Faculty: Elza Erkip, Yao Wang
Web Site: http://eeweb.poly.edu/~elza/, http://eeweb.poly.edu/~yao/
Funding Sources: NSF, Philips Research, CATT, WICAT

Current and next generations of wireless devices and services are substantially different than the original cellular phones which could only carry voice signals. Third/fourth generation cellular and wireless local area networks are designed to support data services, image and video communications as well as voice. Multimedia signals require higher data rates and larger bandwidths than their voice counterparts. This necessitates a more efficient use of already scarce radio resources. Furthermore, guaranteeing a desired level of signal quality for image and video is especially difficult given that the wireless channel is unreliable and compressed audio and video streams are very  sensitive to transmission errors.

In order to provide robust wireless multimedia communications, this research uses cooperative communication techniques along with jointly optimized source compression and channel coding strategies. Cooperation of wireless terminals is achieved by overhearing other terminal's signals and retransmitting towards the desired destination. This provides signal diversity and enables robust source-to-destination routes which can adapt to changes in the wireless environment.  In order to establish the theory and practice of cooperative source and channel coding, the research plan consists of three interrelated components: Information theory of source channel cooperation; design of cooperative source and channel coding techniques with numerical/simulation studies to jointly optimize the parameters; and application of these techniques to wireless video transmission. Our initial results illustrate the benefits of layered cooperation both for idealized and practical channel codes. Layered cooperation improves the overall source distortion by providing higher reliability for important source bits via cooperation [1], [2], [3].

[1] D. Gunduz and E. Erkip. Joint source-channel cooperation: Diversity versus spectral efficiency.  In Proceedings of 2004 International Symposium on Information Theory, Chicago, June 2004.

[2] X. Xu, Y. Wang and E. Erkip. Layered cooperation for wireless multimedia communications. To appear, Proceedings of 2004 Picture Coding Symposium, San Francisco, December 2004.

[3] X. Xu, D. Gunduz, E. Erkip and Y. Wang. Layered cooperative source and channel coding. Submitted, 2005 ICC Multimedia Communication and Home Networking Symposium, Seoul, Korea, May 2005.

Cooperative Regions and Partner Choice in Coded Cooperative Systems

Participating Faculty: Elza Erkip, Andrej Stefanov (stefanov@poly.edu)
Web Site: http://eeweb.poly.edu/~elza/, http://eeweb1.poly.edu/stefanov/
Funding Sources: NSF, Philips Research, CATT, WICAT

Cooperation of mobiles provides signal diversity in wireless networks. See project “Cooperative Wireless Communications: Fundamental Principles” for a detailed description of the cooperation principle. Most work in the literature of cooperative systems assumes that a cooperating partner is already chosen and investigates the details of how cooperation should be carried out. However, it is also important to be able to choose a partner among available candidates to maximize cooperation benefits for the user or the whole system. Therefore, for a given cooperative protocol, it is desirable to know exact conditions under which cooperation is useful, how much benefits can be brought by cooperation and how the channel qualities of user-to-user and user-to-destination links affect these benefits of cooperation.

In this project we consider a coded cooperative system as described in the project “Cooperative Coding for Wireless Networks” and investigate the choice of partners to minimize the error rates. We study the partner choice problem both in an asymptotic regime when  the received signal to noise ratios are high, and as a function of the locations of users [1], [2]. Our results provide simple analytical tools that identify locations of partner terminals, which we call “cooperative region,” such that if a source terminal cooperates with someone in the cooperative region, it will observe a reduction in the frame error rate with respect to no cooperation. Formulation of the cooperative region enables us to limit the  search region of good partners. We also develop  analytical tools that indicate the best partner from a set of available nodes that are all inside the cooperative region. Using these results, cooperation decisions can be made online without need of simulations or large look-up tables.

[1] Z. Lin, E. Erkip and A. Stefanov, An asymptotic analysis on the performance of coded cooperation systems. In Proceedings of 2004 Fall Vehicular Technology Conference, Los Angeles, September 2004.

[2] Z. Lin, E. Erkip and A. Stefanov, Cooperative regions for coded cooperative systems. To appear, Proceedings of 2004 GLOBECOM Communication Theory Symposium, Dallas, December 2004.

Power Efficient Multimedia Wireless Communications

Participating Faculty: Elza Erkip, David Goodman (goodman@duke.poly.edu) and Yao Wang
Funding Sources: NSF and WICAT
Web Site: http://eeweb.poly.edu/dream-it/

An important lesson of cellular telephone communications is that effective management of radio resources, including transmitter power and channel bandwidth, is essential to the quality and efficiency of a network and to the utility of subscriber equipment. The theory and algorithms for radio resource management were first confined to telephone communications. Later work showed that efficient power control algorithms for cellular data transmission differ from those devised for telephony. The radio resource management problem becomes even more complex when we anticipate networks that simultaneously carry a variety of information types. Our research focuses on managing radio resources in multimedia wireless networks with an emphasis on power efficiency.

As video transmission is integrated into wireless communication systems, the theory of power control should be expanded to consider both signal processing power and transmission power when designing new algorithms, since video coding can be a significant drain on the battery of a portable wireless terminal.

This project examines the interaction of signal processing and radio transmission in the design of algorithms for managing power and bandwidth utilization in multimedia wireless networks. Initial research focused on a single portable terminal transmitting video signals to a cellular base station. The research combines theory of source coding and radio transmission, models of distortion due to source coding and channel errors in H.263 video coders, and measurements of power dissipation in equipment performing video coding. Initial results show that the optimum amount of video compression depends on the distance between the terminal and the base station. To avoid using excessive transmitter power, terminals far from a base station should employ more video compression (at the expense of additional signal processing power consumption) than terminals near a base station.

Subsequent work expands the studies of a single terminal to consider the mutual interference of several terminals, all transmitting video signals to the same CDMA base station. Work in progress considers a network in which some terminals are transmitting video signals and others are transmitting data to the base station.

[1] Xiaoan Lu, Yao Wang, Elza Erkip and David Goodman, Minimize the Total Power Consumption for Multiuser Video Transmission over CDMA Wireless Network: a Two-step Approach, to be presented at 2005 International Conference on Acoustics Speech and Signal Processing (ICASSP2005).

[2] Xiaoan Lu, David Goodman, Yao Wang and Elza Erkip, Complexity-bounded Power Control in Video Transmission over a CDMA Wireless Network, To be presented at IEEE Globecom 2004 Conference.

[3] Xiaoan Lu, Yao Wang, Elza Erkip and David Goodman, Power Optimization of Source Encoding and Radio Transmission in Multiuser CDMA Systems, in Proceedings of 2004 International Conference on Communications (ICC), Vol. 5, pp. 3106-3110, June, 2004.

[4] Xiaoan Lu, Thierry Fernaine, Yao Wang, Modelling Power Consumption for H.263 Video Coding, in Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS), Vol. 2, pp. 77-80, 2004.

[5] Xiaoan Lu, Elza Erkip, Yao Wang and David Goodman, Power efficient multimedia communication over wireless channels, IEEE Journal on Selected Areas on Communications, Special Issue on Recent Advances in Wireless Multimedia, Vol. 21, No. 10, pp. 1738-1751, Dec., 2003.

[6] Xiaoan Lu, Yao Wang and Elza Erkip, Power efficient H.263 video transmission over wireless channels, in Proceedings of 2002 International Conference on Image Processing (ICIP), Vol. 1, pp. 533-536, September 2002.

[7] Elza Erkip, Xiaoan Lu, Yao Wang, David Goodman, Total power optimization for wireless multimedia communication, in System Level Power Optimization for Wireless Multimedia Communication: Power Aware Computing, edited by R. Karri and D. Goodman, Chapter 1, Kluwer Academic Publishers, 2002.

[8] Elza Erkip, Yao Wang, David Goodman, Yuantao Wu and Xiaoan Lu, Energy efficient coding and transmission, in Proceedings of IEEE Vehicular Technology Conference (VTC), Vol. 2, pp. 1444-1448, Spring 2001, May 2001.

Peer-to-Peer Video Streaming System

Participating Faculty: Yong Liu, Shivendra Panwar, Keith W Ross, CSE Dept., Yao Wang
Funding Sources: Thomson, Princeton, NJ; Verizon, Waltham, MA; Huawei, Nanjing, China.

With the widespread adoption of broadband residential access, live video streaming may be the next disruptive IP communication technology. Peer-to-Peer video streaming systems have recently emerged to provide real-time video streaming service over the Internet. Although many architectures are possible for IPTV video distribution, several mesh-pull P2P architectures have been successfully deployed in the Internet.

Measurement. In order to gain insights into P2P IPTV systems and the traffic loads they place on ISPs, we have undertaken an in-depth measurement study of one of the most popular P2P IPTV systems. The measurement results obtained through passive and active measurement bring important insights into the traffic characteristics of unstructured overlay networks formed by P2P IPTV systems. Our study provides an important input to further investigation of the impact of emerging unstructured overlay networks on traffic engineering of underlay networks. Our measurement work was published in prestigious journals, such as IEEE Transactions on Multimedia [1] and IEEE Journal on Selected Areas in Communications [2], which was awarded the Best Paper in Multimedia Communications of IEEE Communications Society (ComSoc) in 2008.

Analysis. The fundamental design philosophy of P2P systems is to efficiently utilize resources available on peers to collaboratively improve application performance at low server infrastructure cost. Video applications are extremely sensitive to streaming rate and delay. We analytically investigated various performance bounds of P2P IPTV systems. Specifically, we studied two major efficiency design issues for P2P IPTV to achieve high streaming rate and low delay. We answered the following questions: What is the maximum supportable streaming rate and peer population in a P2P IPTV system [3]? What is the minimum delay that can be achieved in P2P streaming [4]? What is the performance bound of P2P video systems offering multiple channels [5]? For each question, we derived the performance bounds, and then proposed design solutions to achieve the derived bounds. Our results have been published in highly selective conferences, such as IEEE Conference on Computer and Communications (INFOCOM) 2007 (acceptance ratio 18%) [3], and ACM Multimedia 2007 (acceptance ratio 19%) [4], INFOCOM 2009 (acceptance ratio 19%) [5]

Design. Through measurement and analysis, we obtained valuable insights on the operation of P2P streaming systems. In a project funded by Thomson corporate research lab at Princeton, we designed a Hierarchically Clustered P2P Streaming System (HCPS) to achieve a close to 100% peer uploading bandwidth utilization with dynamic peer arrivals and departures [5]. Adaptive queue based chunk scheduling algorithm is developed to make our P2P streaming system robust against network bandwidth variations [6]. In addition, we have built up a prototype system, whose performance has been validated in an Internet scale network testbed, the PlanetLab. Our experimental results were published in the Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS 2008) (acceptance ratio 15%) [7] and IEEE Transactions on Multimedia [8]. In [9], we developed VUD, a radically new P2P streaming design for systems simultaneously offering multiple channels. By decoupling the video upload and download of peers, VUD effectively solved two fundamental performance problems of the traditional P2P streaming design: excessive long channel switching delays and poor quality for unpopular channels. For Video-on-demand, we developed a new incentive mechanism that motivates peers to contribute more upload bandwidth to obtain better video playback experience [10].   

[1] Xiaojun Hei, Chao Liang, Jian Liang, Yong Liu, and Keith W. Ross, “A Measurement Study of a Large-Scale P2P IPTV System,” IEEE Transactions on Multimedia, December 2007.

[2] Xiaojun Hei, Yong Liu, and Keith Ross, “Inferring Network-Wide Quality in P2P Live Streaming Systems,” IEEE Journal on Selected Areas in Communications, the special issue on advances in P2P streaming, December 2007.

[3] Rakesh Kumar, Yong Liu, and Keith Ross, “Stochastic Fluid Theory for P2P Streaming Systems,” in Proceedings of IEEE INFOCOM, 2007.

[4] Yong Liu, “On the Minimum Delay Peer-to-Peer Video Streaming: how realtime can it be?,” in Proceedings of ACM Multimedia, 2007.

[5] Di Wu, Yong Liu and Keith Ross, "Queuing Network Models for Multi-Channel P2P Live Streaming Systems", in the Proceedings of IEEE Conference on Computer and Communications (INFOCOM) 2009

[5] Chao Liang, Yang Guo, and Yong Liu, “Hierarchically Clustered P2P Streaming System,” in Proceedings of GLOBECOM, 2007.

[6] Yang Guo, Chao Liang, and Yong Liu, “Adaptive Queue-based Chunk Scheduling for P2P Live Streaming,” in Proceedings of IFIP Networking, May 2008.

[7] Chao Liang, Yang Guo, and Yong Liu, “Is Random Scheduling Sufficient in P2P Video Streaming?,” in Proceedings of International Conference on Distributed Computing Systems, June 2008.

[8] Chao Liang, Yang Guo, and Yong Liu, “Investigating the Scheduling Sensitivity of P2P Video Streaming: an experimental study,” accepted by IEEE Transactions on Multimedia.

[9] Di Wu, Chao Liang Yong Liu and Keith Ross, "View-Upload Decoupling: A Redesign of Multi-Channel P2P Video Systems", in the Proceedings of IEEE Conference on Computer and Communications (INFOCOM) Mini-Conference, 2009.

[10] Chao Liang, Zhenghua Fu, Yong Liu, and Chai Wah Wu, "iPASS: Incentivized Peer-assisted System for Asynchronous Streaming", in the Proceedings of IEEE Conference on Computer and Communications (INFOCOM) Mini-Conference, 2009

Sensor Management

Participating Faculty: I-Tai Lu

The project is to develop phenomenology and models for determining the effects of electromagnetic interference and electromagnetic compatibility (EMI/EMC) on, and as a result of adjunct ISR (intelligence, surveillance and reconnaissance) sensors for expanded US Navy’s E2-C, EA-6B and EA-18G missions. The introduction of such adjunct ISR sensors may interfere with existing and future systems (such as radar, jamming, signal processing, and communications) as well as be incompatible with existing and future EMI/EMC environments. This project will determine a range of possible interference effects and potential design methods to mitigate these effects for current and future E2-C, EA-6B, and EA-18G applications. So far, we have

• created a mathematical model to simulate the effects of electromagnetic radiation on the E-2C aircraft. The model is used to identify and propose cost effective solutions to potential electromagnetic radiation problems on the E-2C aircraft that could result from increased sensor power levels. 
• performed analysis to quantitatively describe the currents induced over the scattering surfaces for EA-6B and EA-18G aircrafts.
• developed approaches to predict the width of the Fresnel zone for various surface wave scattering paths and estimate the magnitude of the magnetic field intensity as a function of incident RF power level.
• participated in Mockup EA-6B wing testing.

[1] I-Tai Lu, “EMI and EMC Studies for Northrop Grumman’s Airplanes,” Northrop Grumman report.

[2] I-Tai Lu, “Supplementary Results to the Joint Service Center Reports,” Northrop Grumman report.

Unlocking Capacity for Wireless Access Networks through Robust Cooperative Cross-Layer Design

Participating Faculty: Shivendra Panwar, Elza Erkip, Pei Liu
Web Site: http://witestlab.poly.edu/

Cooperative wireless communication refers to active users in the network assisting each other in information delivery, with the objective of gaining greater reliability and efficiency than they could obtain individually. The wireless medium allows nodes to “overhear” other transmissions. While traditional wireless networks ignore this overheard information and treat it as harmful interference, cooperative networking exploits the broadcast nature of the wireless channel by finding effective ways of pooling the overheard information.

In a distributed wireless network, it is possible to employ several relays and mimic a multiple antenna transmission system. In our research we propose a MAC layer solution that allows multiple relays to send information to the receiver at unison, using a randomized distributed space time code. The randomized space-time coding can recruit relays on the fly, thus significantly reducing signaling overhead. The cross-layer design between physical layer and MAC layer involves relay discovery and rate adaptation, and results in improvements in throughput and delay performance. The design is dynamic and can be adapted to changing network conditions. The proposed MAC scheme can be integrated into various wireless technologies such as distributed contention based networks (e.g., IEEE 802.11 BSS and ad hoc mode) as well as centralized multiple access networks (e.g., IEEE 802.16).

[1] C. Nie, P. Liu, T. Korakis, E. Erkip, S. Panwar, "CoopMAX: A Cooperative MAC with Randomized Distributed Space-Time Coding for an IEEE 802.16Network", to appear, IEEE ICC 2009.

[2] P. Liu and S. Panwar, “Randomized spatial multiplexing for distributed cooperative communications”, to appear, IEEE WCNC 2009.

[3] T. Korakis, M. Knox, E. Erkip, S. Panwar, "Cooperative Network Implementation Using Open Source Platforms", to appear in IEEE Communications Magazine, special issue on Cooperative and Relay Communications, February 2009.

[4] P. Liu, Y. Liu, T. Korakis, A. Scaglione, E. Erkip and S. Panwar, “Cooperative MAC for Rate Adaptive Randomized Distributed Space-time Coding”, in Proceedings of the IEEE Globecom 2008.

[5] P. Liu, C. Nie, T. Korakis and S. Panwar, “A Cooperative MAC for Distributed Space-Time Coding in an IEEE 802.16 Network”, in Proceedings of the second International Workshop on Cooperative Wireless Communications and Networking (Conet 2008), invited paper.

[6] F. Verde, T. Korakis, E. Erkip, A. Scaglione, "On avoiding collisions and promoting cooperation: catching two birds with one stone", in Proceedings of the IEEE SPAWC 2008, Recife, Brazil, July 2008.

[7] K. Sinkar, A. Jagirdar, T. Korakis, H. Liu, S. Mathur, S. Panwar, "Data Recovery in Heterogeneous Networks Using Peer’s Cooperative Networking", in Proceedings of the IEEE Secon 2008, San Francisco, CA, USA, June 2008.

[8] Z. Tao, T. Korakis, F. Liu, S. Panwar, J. Zhang, L. Tassiulas, Cooperation and Directionality: Friends or Foes?, in Proceedings of the IEEE ICC 2008, Beijing, China, May 2008.

[9] F. Liu, T. Korakis, Z. Tao, S. Panwar, A MAC-PHY Cross-Layer Protocol for Wireless Ad-Hoc Networks,  IEEE WCNC 2008, Las Vegas, NV, March 2008.

Cooperative Networks: Implementation of Cooperative MAC Protocols for Wireless LANs

Participating Faculty: Shivendra Panwar, Pei Liu
Web Site: http://witestlab.poly.edu/

Cooperative communications, which refer to the collaborative processing and retransmission of overheard information at stations surrounding a source, has recently gained momentum in the research community. The notion of cooperation takes full advantage of the broadcast nature of the wireless channel and creates spatial diversity, thereby achieving improvement in system robustness, capacity, delay, coverage range, and interference reduction. The innovation of cooperative communications is not confined only to the physical layer. It is available in various forms at higher protocol layers. To enable access to physical layer information and facilitate quick adaptability to mobility, it is natural to introduce the notion of cooperation into the layer directly above the PHY, namely the medium access control (MAC) layer. Thus, we have proposed several MAC layer protocols that leverage the notion of Cooperation in the MAC layer of wireless networks.

While the simulations have the ability incorporate more general models, we are still limited by the complexity of the simulation software and our limited knowledge of the wireless environment. Some specific limitations of the simulation approach in depicting a real wireless network include inaccurate representation of the wireless medium, simplification of synchronization issues that occur in wireless terminals, ignorance of several aspects such as the computational overhead.

This project intends to implement Cooperative MAC protocols and study them in a large scale programmable wireless testbed. Moving one step further than analysis/simulation and implementing cooperative protocols in a real wireless platform, would provide deep insights about the behavior of cooperative wireless networks. Through implementations and experiments, we should be able to design, improve and in some cases redesign these protocols as well as incorporate more relevant models into our theory and simulations. We will also be able to test how proposed wireless schemes scale with the size of the network.

We implement the cooperative MAC layer protocols in a Linux based platform. We use open source wireless drivers based on the 802.11 protocol and commercial wireless cards, and we modify these drivers in order to implement our algorithms. Different Linux open source drivers (HostAP, MADWiFi, Intel) are studied and tested in order to figure out their abilities and their limitations. We implement cooperative MAC layer algorithms, using in parallel more than one combination of driver-chipset. We compare different implementations by studying advantages and disadvantages of each implementation. We also study and implement cross-layer algorithms between MAC and PHY layer as well as MAC algorithms for multicast or broadcast services (e.g. video multicasting).

[1] S. Singh, E. Siddiqui, T. Korakis, P. Liu, S. Panwar, "A Demonstration of Cooperative coding schemes using WARP", research demo, WiNTECH 2008 MobiCom Workshop, San Francisco, CA, USA, September 2008. Third place award, WinTECH 2008 demo Contest.

[2] S. Singh, E. Siddiqui, T. Korakis, P. Liu, S. Panwar, "A Demonstration of Video over a Cooperative PHY layer Protocol", research demo, ACM MobiCom 2008, San Francisco, CA, USA, September 2008.

[3] S.Singh, T.Korakis, P.Liu, S.Panwar, “A demonstration of cooperative communications using software defined radio”, research demo, TridentCom 2009, Washington D.C. USA, April 2009

[4] Jian Lin, Thanasis Korakis, Xiao Wang, Shunyuan Ye, Shivendra S. Panwar, “A demonstration of a cross-layer cooperative routing-MAC scheme in multi-hop ad-hocnetworks”, research demo, TridentCom 2009, Washington D.C. USA, April 2009

[5] Ankit Sharma, Vikas Gelara, Shashi Singh, Thanasis Korakis, Pei Liu, Shivendra Panwar, "Implementation of a Cooperative MAC protocol using a Software Defined Radio Platform",  IEEE LANMAN 2008, Cluj-Napoca, Romania, September 2008.

[6] T. Korakis, Z. Tao, S. Singh, P. Liu, S. Panwar, "Implementation of a Cooperative MAC Protocol: Performance and challenges in real environment", EURASIP Journal on Wireless Communications and Networking, under review.

Designing Medium Access Control for Cooperative Networks

Participating Faculty: Shivendra Panwar
Web Site: http://eeweb.poly.edu/coopmac/

The wireless medium is a broadcast one by nature. Many nodes may overhear the transmission. In the legacy IEEE 802.11 medium access control (MAC) protocols, transmissions received by mobile stations other than the intended receiver are discarded. The broadcast nature of the wireless channels is not fully utilized. Additionally, in legacy IEEE 802.11, transmission rates of different station can vary over a wide range (e.g., from 1 to 11 Mbps in IEEE 802.11b), the high rate stations have the same channel access probability as the low rate stations, but in fact they obtain lower share of channel time than the low rate stations. This not only degrades the throughput, but also causes serious fairness problems because low data rate stations uses most of the channel time.

To exploit the broadcast nature of wireless channels, recent work on cooperative coding has shown that additional “cooperative” nodes, which overhear the transmission from sender and then participate in additional transmissions, can provide space diversity for the system. We adopt these ideas to increase the throughput of a wireless network and designed a new MAC protocol. In our proposed cooperative MAC protocol, instead of reducing the transmission rate for the nodes near the edge, we facilitate low rate stations to transmit the data packet first to an intermediate station and then to the destination, if this two-hop transmission approach is faster than direct transmission.

In our protocol, each station in the network needs to overhear the ongoing transmission by other stations, from which they can discover their neighbors. When a station has data to transmit, it will choose one station from the neighbor list, so that if a packet was sent to the selected station first and then relayed to the destination, this two hop transmission spends the least transmission time. We also introduced a new handshake message - HR (helper-ready) in additional to the RTS (request-to-send), CTS (clear-to-send) and ACK (acknowledgement) already in 802.11. An illustration of the exchange of control and data packet is shown in Figure 1.

We validated our protocol using both analytical modeling and simulation. The results show that cooperative MAC protocol can substantially enhance the network performance, in terms of the achievable throughput and average delay experienced by the data packets. Besides, the cooperative MAC improves the system fairness in the sense that it reduces the channel time occupied by low rate stations. Last, but not the least, the protocol is designed such that only minor software modification to the legacy MAC implementation is needed and backward compatibility with the legacy IEEE 802.11 system is maintained.

[1] Pei Liu, Zhifeng Tao, Sathya Narayanan, Thanasis Korakis and Shivendra S. Panwar, "CoopMAC: A Cooperative MAC for Wireless LANs", IEEE Journal on Selected Areas in Communications, Special Issue on Cooperative Communications, to appear, Feburary 2007

[2] Pei Liu, Zhifeng Tao, Zinan Lin, Elza Erkip and Shivendra Panwar, "Cooperative Wireless Communications: A Cross-Layer Approach", IEEE Wireless Communications, vol.13, no.4, pp.84-92, August 2006

[3] P. Liu, Z. Tao, and S. S. Panwar, "A Cooperative MAC Protocol for Wireless Local Area Networks," in Proceedings of the IEEE International Conference on Communications (ICC), Seoul, Korea, May 2005

[4] S. Narayanan, P. Liu, S. S. Panwar, "On the advantages of multi-hop extensions to IEEE 802.11 infrastructure mode," in Proceedings of the  IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, LA, 2005

[5] S. Narayanan, P. Liu, S. S. Panwar, "On the advantages of multi-hop extensions to IEEE 802.11 infrastructure mode," NYMAN 2004, New York, NY, Sep. 2004

High-Speed Network Intrusion Detection and Prevention

Participating Faculty: Jonathan Chao, N. Sertac Artan
Web Site: http://eeweb.poly.edu/labs/hsnl/

Network Intrusion Detection and Prevention Systems (NIDPSs) are vital in the fight against network intrusions. NIDPSs search for certain malicious content in network traffic (i.e., signatures) using a method called Deep Packet Inspection (DPI), where incoming packet payloads are compared against known attack signatures. Processing every single byte in the incoming packet payload has a very stringent time constraint, e.g., 200 ps for a 40-Gbps line. Traditional DPI systems either need a large memory space or use special memory, such as Ternary Content Addressable Memory (TCAM), limiting parallelism or yielding high-cost/power consumption.

The main goal of our group is to develop low-cost, high-speed, and scalable DPI methods. To achieve this goal, we have developed two novel hardware architectures named TriBiCa (Trie Bitmap Content Analyzer) (Artan and Chao, 2007) and LaFA (Lookahead Finite Automata) (Bando et al., 2009). TriBiCa provides minimal perfect hashing functionality for detecting malicious signatures with extremely small memory requirements. LaFA is a scalable data structure for detecting Regular Expressions (RegExes) signatures, which are the de facto way to represent NIDPS signatures today. In addition to TriBiCa and LaFA, we have also proposed an Aggregated Bloom Filter (Artan et al. 2007) to increase the scalability and throughput of Bloom Filters.  In our earlier work, we worked on multi-packet signature detection, where signatures are fragmented into multiple packets (Artan and Chao, 2005).

Lookahead Finite Automata (LaFA)

RegExes have been widely used to represent complex string patterns in DPI due to their flexibility and conciseness. However, it has been very challenging to implement a high-speed RegEx Detection system with a large number of RegEx rules. 
Our proposed Lookahead Finite Automata (LaFA) is a scalable RegEx detection system that can achieve very high-speed operation and accommodate a large number of rules. It can also support flexible updates.

LaFA uses three observations to achieve great scalability and high-speed operation.

1. RegExes consist of a variety of different components such as character classes or repetitions. Due to this variety, it is hard to identify a method that is efficient for concurrently detecting all of these different components of a RegEx. However, in most cases today, these heterogeneous components are detected by a state machine that consists of homogeneous states. This leads to inefficiency and, as a result, the scalability of such systems is poor.
2. The order of components in a RegEx is preserved in the state machine detecting this RegEx. However, it may be beneficial to change the order of the detection of components in a RegEx. For instance, it is easy to detect simple strings as they are expected to appear less frequently, whereas others are harder to detect (for instance, character classes) and may appear more frequently. By reordering the detection of the components, the trade-off between detection complexity and appearance frequency can be exploited for better scalability. 
3. Most RegExes share similar components. In the traditional FA approaches, a small state machine is used to detect a component in a RegEx. This state machine is duplicated since the similar component may appear multiple times in different RegExes. Furthermore, most of the time, these RegExes sharing this component cannot appear at the same time in the input. As a result, the repetition of the same state machine for different RegExes introduces redundancy and limits the scalability of the RegEx detection system.

LaFA addresses these three issues with three novel methods as summarized in the example in Figure 1.

We have prototyped LaFA on a Virtex 4 Field-Programmable Gate Array (FPGA) based on the hardware architecture shown in Figure 2. LaFA requires an order of magnitude less memory compared to today’s state-of-the-art RegEx detection systems. A single commodity FPGA chip can accommodate up to 25,000 RegExes. Based on the throughput of our LaFA prototype, we expect that a 34-Gbps throughput can be achieved by using a state-of-the-art FPGA. 

Figure 1: An example illustrating the transformation from a RegEx set R into the corresponding LaFA: (a) The RegEx set R, (b) the NFA corresponding to R, (c) separation of simple strings, (d) reordering the detection sequence, and (e) the final step, the sharing of complex detection modules, which leads to the LaFA corresponding to R.

Figure 2: LaFA Architecture

Trie Bitmap Content Analyzer (TriBiCa)

TriBiCa uses a trie structure with a hash function performed at each layer. Branching is determined by the hashing results with an objective to evenly partition attack signatures into multiple groups at each layer. During a query, as an input traverses the trie, an address to a table in the memory that stores all attack signatures is formed and is used to access the signature for an exact match. Due to the small space required, multiple copies of TriBiCa can be implemented on a single chip to perform pipelining and parallelism simultaneously, thus achieving high throughput.

We have designed the TriBiCa on a modest FPGA chip, Xilinx Virtex 2, achieving 10-Gbps throughput without using any external memory. A proof-of-concept design is implemented and tested with 1-Gbps packet streams. By using today’s state-of-the-art FPGAs, a throughput of 40 Gbps is believed to be achievable.

Figure 3: TriBiCa data structure for 8 signatures and a sample query on the TriBiCa data structure.

Aggregated Bloom Filters

As part of the low-cost, high-speed, and scalable DPI goal, our research also involves optimizing current state-of-the-art building blocks for DPI. One such popular building block is the Bloom Filter (BF). To increase throughput by reducing off-chip access, BFs are used as on-chip filters. We show that BFs have shortcomings when implemented on hardware. Hence, we propose Aggregated Bloom Filters (ABFs) to increase the throughput and scalability of hardware BFs. ABF leverages the query mechanism for hardware BFs by removing redundant hash calculations and redundant on-chip memory accesses for higher throughput. ABF also improves scalability by aggregating small distributed BFs to a single BF for better on-chip memory utilization. ABF shows seven-fold improvement in the average query throughput and four times less memory usage compared to previous hardware BFs for NIDPS.

Figure 4: TriBiCa test setup.

Prefix Bloom Filters

Precision is also crucial for NIDPS, which can easily be evaded by fragmentation of attack packets. The straightforward defragmentation method is not applicable at high-speeds due to high-memory requirement. In our earlier work, this multi-packet signature detection problem is addressed using a defragmentation-free, space-efficient solution. A new data structure, the Prefix Bloom Filter (PBF), is proposed to significantly reduce the storage requirement of the problem.

[1] M. Bando, N. S. Artan, and H. J. Chao, “LaFA: Lookahead Finite Automata for Scalable Regular Expression Detection,” in ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2009), Princeton, NJ, Oct. 2009.
[2] N. S. Artan, H. Yuan, and H. J. Chao, “A Dynamic Load-Balanced Hashing Scheme for Networking Applications,” in IEEE Global Communications Conference (GLOBECOM 2008), New Orleans, LA, Nov-Dec 2008.
[3] M. Bando, N. S. Artan, and H. J. Chao, “Highly Memory-Efficient LogLog Hash for Deep Packet Inspection,” in IEEE Global Communications Conference (GLOBECOM 2008), New Orleans, LA, Nov-Dec 2008.
[4] N. S. Artan, M. Bando, and H. J. Chao, “Boundary Hash for Memory-Efficient Deep Packet Inspection,” in IEEE International Conference on Communications (ICC 2008), Beijing, China, May 2008.
[5] N. S. Artan and H. J. Chao, “Design and Analysis of a Multi-packet Signature Detection System,” Int. J. Security and Networks, vol. 2, no.1/2, pp. 122–136, Mar. 2007.
[6] N. S. Artan, R. Ghosh, Y. Guo, and H. J. Chao, “A 10-Gbps High-Speed Single-Chip Network Intrusion Detection and Prevention System,” in 50th Annual IEEE Global Communications Conference (GLOBECOM 2007), Washington, DC, Nov. 2007.
[7] N. S. Artan, K. Sinkar, J. Patel, and H. J. Chao, “Aggregated Bloom Filters For Intrusion Detection And Prevention Hardware,” in 50th Annual IEEE Global Communications Conference (GLOBECOM 2007), Washington, DC, Nov. 2007.
[8] N. S. Artan and H. J. Chao, “TriBiCa: Trie Bitmap Content Analyzer for High-Speed Network Intrusion Detection,” in 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007), 2007, pp.125–133.
[9] N. S. Artan and H. J. Chao, “Multi-packet Signature Detection using Prefix Bloom Filters,” in 48th  Annual IEEE Global Communications Conference (GLOBECOM 2005), St Louis, MO, Nov-Dec 2005.

Lightwall: A Light-Weight Distributed Enforcement Architecture for Centralized Network Control Policy

Participating Faculty: Jonathan Chao
Web Site: http://eeweb.poly.edu/labs/hsnl/

As more applications and services are delivered through the network, the security and reliability of the network are attracting increasing attention. To minimize disruptions, network operators want to maintain more control over the network traffic and behavior. Areas of concern are access and admission control, traffic engineering, detection and mitigation of network anomalies, and attack isolation to name a few.

As more of these devices are deployed across the network, often incrementally, policy  management of all these devices becomes a problem. For these devices to provide effective traffic policing, up-to-date and coherent configurations are required. Also, problems arise with detecting conflicts among distributed rulesets, troubleshooting network anomalies, and verifying  conformity of network security requirements when multiple administrators are involved in manually managing policing devices distributed across the network. The tasks are not only tedious and contribute to a significant portion of operating costs, but are also error-prone, which can cause network downtime.

The requirements, and even the definition of a network control system, are not universally applicable. Some networks may require simple access control while financial institutions are required by law to have strict controls on information flows between their systems. We believe facilitating innovations at the network control and management layer promotes more effective and useful network controls.

Our proposed architecture embraces the ideas from the 4D project, which used centralized components for control and management. We employ simple (or dumb) forwarding devices, called Enforcement Agents (EAs), on the data-plane to handle network traffic. A set of servers, called Supervisors, acts as the centralized component that governs the network control decisions and dynamically disseminates them in a just-in-time manner. The decision engines correspond to the network control and management layer. The resulting system consists of mainly light-weight forwarding devices sharing a few heavy-weight decision engines through a small number of Supervisors. Lightwall is an overall light-weight architecture compared to the traditional architecture, which deploys many heavy-weight devices throughout the network.

Supervisors focus on determining and maintaining up-to-date network control decisions, and making those decisions available across the network in a robust, consistent, and scalable manner.  EAs focus on packet forwarding while inquiring and enforcing network control decisions in a just-in-time manner. Through the set of Supervisors, decision engines are presented with packets and information that originated from the data-plane.  Decision engines do not need to worry about disseminating actions and keeping them up-to-date. Similarly, EAs do not need to know how the actions are determined nor the specification of the underlying control policies.

This separation of duties offers several benefits:

Open platform

The network operator can now choose its set of network control features, policy representation, and management platform independent of the enforcement mechanism deployed in the network. In fact, there can be multiple platforms potentially provided by different vendors. Similarly, this architecture allows the co-existence of traditional policing devices and EAs, potentially from multiple vendors with different sets of features. This not only offers flexibility to administrators on choosing networking equipment, but also opens up opportunities for innovations in the equipment vendor industry.

Manageability

Network control policies can be updated anytime. Instead of manually identifying the relevant policing devices on which to install or update policies, changes can now be made at their respective decision engines with the knowledge that the Supervisors will automatically and consistently enforce the latest policies in the distributed EAs.

With centralized decision engines, conflicts or potential policy induced anomalies can be more readily discovered and resolved with existing algorithms before deployment. By maintaining a version control on the policy and a global view on a central repository of flow-initiation statistics, network anomalies and troubleshooting will be more manageable.

Deployments of  EAs can be done incrementally and involve only minimal configuration. Once connected to the network, a new EA is ready to forward traffic and enforce network control decisions provided by Supervisor.

We set up a physical network testbed consisting of Linux software routers, a Cisco hardware router, and Linux-based servers and traffic generators. We use a modified pktgen Linux kernel traffic generator for our testbed experiments. EAs are implemented with kernel modules using the Linux Netfilter framework and deployed in Linux-based software routers. A Supervisor is implemented as three multi-thread, C++ user-level applications running on an Intel Core 2 Duo 1.86GHz Linux server. A stateless firewall decision engine is implemented using the Netfilter framework. Also, a simple C++ program that emulates a constant packet classification time of 700us per packet is used as an additional decision engine. EA implementations, such as hardware add-ons and firmware updates to existing switches and routers, are currently in progress.

Data Center Networks

Participating Faculty: Jonathan Chao, Kang Xi
Web Site: http://eeweb.poly.edu/labs/hsnl/

A data center is a facility that houses computer systems and associated components, such as storage, switches, routers, firewalls, and Heating, Ventilating, and Air Conditioning (HVAC). From the networking viewpoint, a data center includes a large number of computers that are interconnected by a data center network (DCN). Yet, a DCN is more than a simple collection of computers. The computers are controlled by sophisticated software to work in a highly interactive and coordinated way such that they become a high-performance computing system. Data centers have evolved to be one of the most critical facilities in the Internet. In particular, the fast growth of cloud computing is supported by large-scale and cost-effective data centers. Currently, a data center may contain from dozens to hundreds of thousands of servers.

The rapid growth of data centers has posed great challenges on the design of the interconnection networks. On one hand, it is essential to study the most cost-effective method to build large-scale DCNs. A recent trend is to use commodity devices to scale out the network to support tens to hundreds of servers. While some work has been done to investigate network architecture, routing, and address management (e.g., DCell, Portland, VL2, check Sigcomm 2008 & 2009 for the papers), more research needs to be conducted in the aspect of throughput/delay optimization, network stability control, dynamic routing, and network resilience.  

[1] Kang Xi and H. J. Chao, “IP Fast Rerouting for Shared Risk Link Group Failure Recovery,” submitted, 2009.
[2] Adrian Tam, Kang Xi, and H. J. Chao, “Leveraging Performance of Data Center Networks by Reactive Reroute,” submitted, 2009.
[3] Adrian Tam, Kang Xi, and H. J. Chao, “A Fast Reroute Scheme for IP Multicast,” IEEE Globecom, Nov. 2009.
[4] Kang Xi and H. J. Chao, “IP Fast Rerouting for Double-Link Failure Recovery,” Technical Report, Nov. 2009.
[5] Kang Xi and H. J. Chao, “IP Fast Rerouting for Single-Link/Node Failure Recovery,” IEEE BroadNets, Nov. 2007.
[6] Kang Xi and H. J. Chao, “"ESCAP: Efficient SCan for Alternate Paths to Achieve {IP} Fast Rerouting,” IEEE Globecom, Nov. 2007.