UC Santa Cruz

Wireless networks are a fixture of present day computing. We are seeing a simultaneous increase in network density and throughput demand as the clients of these networks grow accustomed to more data hungry applications. Contention-based channel access methods take bigger performance hits and waste more energy as network density and load increases. It is therefore clear that the future of wireless networking will need to exploit some form of schedule based channel access in order to simultaneously solve the problems of energy consumption and maximization of channel utilization.

The focus of this work is on leveraging implicit properties of network traffic to benefit the performance of schedule based medium access mechanisms. We focus on one of these properties: the packet arrival behavior of the traffic. We chose to start our work by trying to answer the following question: "If we use predictions of the behaviors of flows in the network, can we decrease the delay in schedule-based medium access control?" The main idea is to use traffic forecasting to anticipate transmission schedules instead of establishing them reactively, i.e., as traffic arrives at the MAC layer. Although not all applications generate forecastable traffic, we contend that many applications do. Examples of predictable network traffic include Voice-over-IP (VoIP) applications such as Skype, iChat, and Google talk. Video streaming applications have lower QoS demands but also contain many predictable patterns. All of these applications are becoming increasingly commonplace in the home networks of today.

An experimental method was used to evaluate the benefit that accurate traffic prediction could have on the performance of a schedule based MAC protocol (DYNAMMA). Comparing the performance of DYNAMMA to our modified version of it (DYNAMMA-PRED) in simulations showed that prediction does improve delay performance of the schedule based protocol significantly, particularly at lower network loads.

The next step was to address the topic of extracting patterns out of packet arrival times of each flow with more mathematical rigor. We did this by measuring the entropy of packet arrivals in a network flow. Given that entropy is defined as the "measure of information", its value in this context signifies the amount of pattern in the packet arrival times of a flow - the less information each arrival holds, the more pattern there is overall.

During our investigation of the entropy of the packet arrival times, our research produced the concept of an "entropy fingerprint" - a plot of the entropy of the packet arrival times of a flow over a range of time scales. Each entropy fingerprint has numerous characteristics that are related to the packet arrival behavior of the flow that generated it. These fingerprints can be used in many ways, such as identifying what application generated the flow or whether the flow's packet arrivals are likely to be regular or irregular at a given time scale. In addition to the entropy fingerprints, the entropy estimator that we developed turned out to be usable as forecaster as well, able to predict the chances of a packet arrival in the next slot.

Analyzing the entropy fingerprints of various types of traffic confirmed that there was useful information in the packet arrival times of network flows that could be leveraged in a schedule based MAC protocol. Furthermore, the work presented us with a traffic forecaster that we could use to extract this information for use in such a MAC protocol.

Following this work, we designed a medium access control protocol to embody the fusion of traffic forecasting with a schedule based access control mechanism. We called the protocol TRANSFORMA, which stands for TRAffic FORecasting Medium Access. TRANSFORMA was designed using the principle that the MAC layer should detect the properties of each flow transparently and adapt its level of service accordingly. TRANSFORMA attempts to do that by observing an application flow, learning its pattern, and forecasting the flows future behavior based on the observed one. In its current implementation, TRANSFORMAs forecaster examines the packet arrival process of each application flow and determines the corresponding per-flow inter-packet arrival times. It then uses this information to establish the flows medium access schedule. TRANSFORMA operates under the assumption that applications that place more stringent requirements, e.g., higher data rates and delay sensitivity have forecastable network usage patterns. The simulation results show that TRANSFORMA significantly improves on the delay performance of its predecessor, DYNAMMA.

The final contribution of this work is a real-system implementation of TRANSFORMA. This fully functional network link enables experimentation with real application traffic, serves to validate our simulation results and demonstrates that the concepts embodied in TRANSFORMA are practical.