Montage: An Integrated End-to-End Design and Development Framework for Wireless Networks

Meet the Team

Faculty

James C. Browne, The University of Texas at Austin
Narendran Ramakrishnan, Virginia Tech University
Ted S. Rappaport, The University of Texas at Austin
Sanjay Shakkottai, The University of Texas at Austin
Srinidhi Varadarajan, Virginia Tech University

Students

Craig Bergstrom, Virginia Tech
Jeremy K. Chen, The University of Texas at Austin
Mathew Crocker, The University of Texas at Austin
Ved Vyas Duggirala, Virginia Tech
Joy Mukherjee, Virginia Tech
Hyun Park, The University of Texas at Austin
Jung Ryu, The University of Texas at Austin
Sundar Subramanian, The University of Texas at Austin
Madhulika Yalamanchi, The University of Texas at Austin
Chang Woo Yang, The University of Texas at Austin
Yung Yi, The University of Texas at Austin

Students Graduated

Chen Na, graduated Ph.D., "IEEE 802.11 Wireless LAN Traffic Analysis: A Cross-layer Approach," The University of Texas at Austin, May 2005, advised by Prof. Ted Rappaport
Huihui Wang, graduated Ph.D., "Modeling and Wideband Characterization of Radio Wave Propagation in Microcells," The University of Texas at Austin, May 2005, advised by Prof. Ted Rappaport
Michael Heffner. graduated M.S. " A Runtime Framework for Adaptive Compositional Modeling," Virginia Tech, summer 2005, 42 pages. Jointly advised by Prof. Naren Ramakrishnan and Prof. Srinidhi Varadarajan.
Jeremy K. Chen, graduated M.S.,"Throughput Measurements and Models of Public IEEE 802.11b Wireless Local Area Networks," The University of Texas at Austin, May 2004, advised by Prof. Ted Rappaport
Samit Jain, graduated B.S., The University of Texas at Austin, (Currently enrolled in the Ph.D program in CS at Columbia), advised by Prof. James C. Browne
Will Rodenbush, undergraduate honors researcher, "Computer aided rendering of floor plans," The University of Texas at Austin, December 2004, advised by Prof. Ted Rappaport

Project Summary

As today’s wireless networks transition from circuit-switched voice to internet protocol (IP) based traffic, there is a critical need to accurately and rapidly model the performance of emerging end-to-end user applications. Surprisingly, today’s wireless systems treat all the higher layer protocols of the network stack as invisible and irrelevant in the development of wireless standards (e.g., WCDMA, EDGE, and IEEE 802.11a). Future wireless networks must abandon this archaic viewpoint of separation, and must use cross-layer knowledge to enable the next generations of ubiquitous wireless applications. In fact, one of the major stumbling blocks to designing and deploying the new generation of wireless network services is the lack of sophisticated computational tools for end-to-end systems modeling and simulation. Next generation simulation environments must address both the fidelity of modeling needed for the channel and physical levels of the protocol hierarchy and, at the same time, interactively exploit these features in software protocols employed at the higher layers. When such an approach is used, it becomes possible to create a powerful, accurate, end-to-end modeling environment for the development of the next generation of wireless data networks.

This proposal will develop the first academic end-to-end multi-layer simulator and emulator for wireless networks. Montage —an integrated protocol development environment —will support the evolutionary design, development, and test of wireless network protocols. It will enable wireless and ad-hoc mobile network researchers and system operators across the country to design, develop, and analyze wireless hardware, network protocols, middleware algorithms, and network applications in a single integrated public-domain environment. Key research issues addressed in this proposal include a unified multi-modeling methodology (simulation + emulation + direct code execution), algorithms for smart scheduling, building a dynamic compositional environment, and incorporating sophisticated performance models of various network protocol layers. Montage thus addresses both the TPES (Technology for Performance Engineered Systems) and the CADDS (Complex Application Design and Support Systems) goals of the NSF Next Generation Software (NGS) program.

Development of Montage drives development of new methods and techniques for integration of complex systems. It is simply not possible to create an integrated system from several existing and semantically complex systems on an ad hoc basis. The research tasks of this project derive from interfacing and integration of systems, which have quite different semantic bases, varied execution models, and span multiple levels of abstraction. One task is to design interface specification languages that will enable representation of the translations across the multiple semantics, execution models and levels of abstraction. Applying the interface language to interface and integrate the software systems, which together implement the Montage methodology, will be a major component of this research. As application case studies, this project will address key validation and design problems for large-scale ad-hoc wireless networks, as well as large commercial cellular networks that are transitioning from 2.5G to 3G. Today, these computational capabilities do not exist.

Broader Impacts: Montage will be made available as a public domain web portal with customized design scenario interfaces for network researchers, educators, and commercial carriers. Montage shall also serve as a national archive for measured network performance and as a repository of designs selected by the user community. Montage will enable researchers to setup virtual testbeds, validate their modeling, and design and test middleware algorithms for wireless networks of the future. The principal investigators have an excellent track record for creating valuable research products and learning materials for education and training purposes. Furthermore, the investigators have proven records for fostering economic growth by creating high-tech spinout companies. Montage already has the support of key industrial constituencies (see supporting letters), and will emerge as a valuable resource for researchers and educators.

Project Progress During 2004 - 2005

Prof. James C. Browne

The goal for this year was to establish the necessary extensions to the P-COM² compiler and runtime system to enable completion of the end-to-end coupling of the physical modeling codes of Rappaport and Shakkottai with the Weaves simulator of Varadarajan with the P-COM² application development and modeling system..

This goal required several extensions to each of the compiler, the runtime system and the interface definition language. We have extended the ability of the runtime system to couple parallel execution with distributed/parallel discrete event simulation. [Mahmood 2005b] This extension is essential to being able to couple with the Weaves execution engine.

We have extended the runtime system of the P-COM² compiler to incorporate measurement components and dynamic linking and adaptation of runtime adaptation of codes compiled under the P-COM² component composition system. [Mahmood 2005a] This too is a necessary capability for effectively integrating with Weaves.

We will have a project meeting in Austin on May 16-17 to begin the actual code level integration of the three systems.

Prof. Naren Ramakrishnan and Prof. Srinidhi Varadarajan

During 2004-2005, we have successfully developed a runtime framework for composing object models of scientific codes. The framework allows us to compose collections of arbitrary codes and permits direct code execution without source-level modifications. In addition, the framework supports the instrumentation of object codes to realize runtime adaptivity scenarios. For instance, an application can explore numerous algorithmic possibilities, learn the results of these decisions, and reward the most efficient possibilities. Finally, the framework is resilient to failure when exploring solution spaces, allowing us to "restart" the application from an arbitrary point when we detect failure.

This framework is currently being used in the Montage context to compose adaptive configurations of S⁴W models, to realize targeted higher-level Montage performance goals. One instantiation of this framework involves studying the end-to-end performance of an FTP session over a simulated wireless network situated in the 3rd floor of Durham hall, Virginia Tech. Depending on the fidelity of the desired session, we dynamically substitute a less accurate S⁴W model (but a cheaper one) in the composed application. We have developed a high level markup language (HACL) that allows us to specify the forms of adaptivity we want. A compiler uses the tags in this language to instrument the object codes without manual user intervention.

In the forthcoming year, we plan to identify opportunities for adaptive composition of models at multiple levels of the Montage hierarchy of simulations. We intend to adopt a "graphs of models" approach where relationships between models are encoded via multiple partial order constraints; a recommender system then attempts to identify a satisficing sequence of models (e.g., a channel model integrated with a surrogate model for bit error rate estimation followed by a third model for assessing network throughput) within the given constraints. Such powerful capabilities will ensure that Montage can serve as an integrated PSE for wireless network modeling and simulation.

Finally, we intend to integrate the distributed memory prototype of the relativistic time model within the ONE framework. The current prototype implements the ONE framework and the relativistic time model on a shared memory system. Since the relativistic time model was intended for distributed memory systems where the temporal model provides a parallel representation of a "naturally" flowing clock, the main performance advantages will be realized on large-scale distributed memory parallel supercomputers. The current performance results were obtained from an 8 processor shared-memory Opteron system funded under this grant. Over the next year, this system will be scaled first to a 16 processor distributed memory cluster and then to a 400 processor cluster.

Prof. Naren Ramakrishnan was on academic sabbatical during the last year and was not directly supervising graduate students at Virginia Tech. To ensure continuity of the Montage project, graduate student Craig Bergstrom has been working with Prof. Srinidhi Varadarajan on integrating the lower-level channel models of S⁴W with the higher level protocol layers of Varadarajan's ONE emulator.

Prof. Srinidhi Varadarajan worked on the integration of Weaves and the Relativistic Time temporal model within the Open Network Emulator environment. This work made significant progress over the past year and has achieved prototype capability. The prototypes are being delivered to the University of Texas, Austin in May 2005. In addition, we have implemented a preliminary prototype of the distributed memory parallel implementation of the relativistic time model and integrated it within the ONE framework. The current system prototype models wireless and wired networks within a direct code execution framework, where complete applications intended for deployment can be executed within the ONE simulator. The ONE simulator currently includes a direct code execution engine, the relativistic time temporal model, a complete TCP/IP stack (including TCP, UDP, IP, ICMP, IGMP, BGP and NAT/Firewalling subsystems) and S4W models of a wireless network.

Prof. Ted Rappaport

During 2004-2005, we successfully implemented the S⁴W software and improved it by adding difraction and improved ray tracing capabilties. The S⁴W software was implemented on a parallel computer cluster in WICAT and NYU Wireless, and was used to validate microcell measurements in San Francisco, thus expanding the applicability of S⁴W and validating its usefulness in both indoor and outdoor environments. We also made progress in mapping SNR and SIR predictions to end-user bit error rates and throughput rates, and validated the capability of using S⁴W or measurements to blindly predict end-user throughput. This work involved all of Prof. Rappaport’s students, and was published in several peer reviewed journals.

Also during the year, the Montage research results were presented at the IEEE 802.11 Plenary Session, as the site-specific approach has promise for the control of future wireless networks. The work was well received, and was invited for presentation at IEEE 802.1, the futuristic committee of the IEEE International standards body. Two PhD students graduated with Montage funding, laying the foundation for UT’s 2nd generation of S⁴W students who are already off to a fast start.

In the coming year, we plan to more tightly integrate the propagation and end-user performance modeling capabilities of S⁴W with the Virginia Tech research team, to ensure that new implementations and more complicated throughput models may be achieved.

Prof. Sanjay Shakkottai (Algorithms for Wireless Networks)

1. Wireless Scheduling: We have recently studied the Multi-user EXP rule (MEXP) for multiple-queue multiple-server scheduling motivated by a model for transmission to multiple users over a wireless broadcast channel. The MEXP algorithm is shown to be throughput optimal, and pathwise optimal (i.e. minimizes the maximum queue length) in the heavy traffic limit.

2. Routing over Wireless Networks: Geographic routing with greedy relaying strategies have been widely studied as a routing scheme over wireless sensor networks. These schemes assume that the nodes have perfect information about the location of the destination. When the distance between the source and destination is normalized to unity, the asymptotic routing delays in these schemes are of order 1/M(n) is the maximum distance traveled in a single hop (transmission range of a radio).

Three scenarios are considered: (i) where nodes have location errors (imprecise GPS), (ii) where only coarse geographic information about the destination is available, such as the quadrant or half-plane in which the destination is located, and (iii) where only a small fraction of the nodes have routing information. In this paper, it is shown that even with such imprecise or limited destination-location information, the routing delays are of order 1/M(n). Further, routing delays of this magnitude can be obtained even if only a small fraction of the nodes have any location information, and other nodes simply forward the packet to a randomly chosen neighbor.

Finally, the throughput-capacity is derived for networks with progressive routing strategies that take packets closer to the destination in every step, but not necessarily along a straight-line. Such a routing strategy could potentially lead to spatial "hot spots" in the network where many data flows intersect at a spatial region (a node or group of nodes), due to "sub-optimal" routes with increased path-lengths. In this paper, it is shown that the effect of hot spots due to progressive routing does not reduce the network throughput-capacity in an order sense. In other words, the throughput-capacity with progressive routing is order-wise the same as the maximum achievable throughput-capacity.

3. Simulation of Large-scale Networks: Motivated by the scale and complexity of simulating large-scale networks, recent research has focused hybrid fluid/packet simulators, where fluid models are combined with packet models in order to reduce simulation complexity. However, these simulators still need to track the queuing dynamics of network routers, which generate considerable simulation time-complexity in a large-scale network model.

In this work, we propose a hybrid simulator -- FluNet - where queueing dynamics are not tracked. The FluNet simulator is predicated on a fast-queueing regime at bottleneck routers, where the queue length fluctuates on a time-scale that is much faster than the time-scale of end systems. FluNet does not track queue lengths at routers, but instead, uses an equivalent rate based model the router queue; and queue-based AQM schemes (such as RED) are replaced by equivalent rate-based models. This allows us to simulate large-scale systems, where the simulation "time-step-size" is governed only by the time-scale of the end-systems, and not the intermediate routers; whereas a fluid model based simulator that tracks queue-length would require decreasingly smaller step-sizes as the size of system increases. We validate our model using a Linux based implementation, and with real traffic. Our results indicate a good match between packet systems and the associated FluNet system.

Montage Team Accomplishments

Project Report

Sept. 2003 - August 2004 Project Report

Meeting Minutes

PhD Dissertation

Chen Na, IEEE 802.11 Wireless LAN Traffic Analysis: A Cross-layer Approach, The University of Texas at Austin, May 2005, advised by Prof. Ted Rappaport
Huihui Wang, " Modeling and Wideband Characterization of Radio Wave Propagation in Microcells," The University of Texas at Austin, May 2005, advised by Prof. Ted Rappaport

MS Thesis

Michael Heffner. graduated M.S. " A Runtime Framework for Adaptive Compositional Modeling," Virginia Tech, summer 2005, 42 pages. Jointly advised by Prof. Naren Ramakrishnan and Prof. Srinidhi Varadarajan
Jeremy K. Chen, "Throughput Measurements and Models of Public IEEE 802.11b Wireless Local Area Networks," The University of Texas at Austin, May 2004, advised by Prof. Ted Rappaport

Undergraduate Honors Thesis

Will Rodenbush, "Computer aided rendering of floor plans," The University of Texas at Austin, December 2004, advised by Prof. Ted Rappaport

Publications

C. Na, J. K. Chen, T. S. Rappaport, "Measured Traffic Statistics and Throughput of IEEE 802.11b Public WLAN Hotspots with Three Different Applications," to appear in IEEE Transactions on Wireless Communications
N. Mahmood, Y. Feng and J.C. Browne, "A Case Study in Application Family Development by Automated Component Composition: HP-Adaptive Finite Element Codes," to appear in the Proceedings of ICCS 2005 (Atlanta, GA, May 2005). [Mahmood 2005a]
N. Mahmood, Y. Feng and J.C. Browne, "Evolutionary Performance-Oriented Development of Parallel Programs by Composition of Components," to appear in the Proceedings of the Workshop on Software Performance Evaluation 2005 (Palma de Mallorca, Spain, July 2005). [Mahmood 2005b]
K. Kane and J.C. Browne, "A Taxonomy of Access Control," to appear in the Proceedings of the Symposium on Reliable Distributed Systems (October 2005, Orlando, FL).
S. Jain, M. Crocker, N. Mahmood and J.C. Browne, "Productivity and Performance Through Components: The ASCI/Sweep3D Application," to appear in the Proceedings of COMPFRAME 2005
S. Shakkottai, "Asymptotics of Query Strategies over a Sensor Network," To appear in IEEE Transactions on Automatic Control, June 2005
S. Deb, S. Shakkottai and R. Srikant, "Asymptotic Behavior of Internet Congestion Controllers in a Many-Flows Regime," To appear in Mathematics of Operations Research, 2005
S. Shakkottai, R. Srikant and A. Stolyar, "Pathwise Optimality of the Exponential Scheduling Rule for Wireless Channels," Advances in Applied ProbabilityVol. 36, No. 4, pp. 1021 -- 1045, December, 2004.
S. Subramanian and S. Shakkottai, "Geographic Routing with Limited Information in Sensor Networks," Proceedings of The Fourth International Conference on Information Processing in Sensor Networks, Los Angeles, CA, April, 2005
Y. Yi and S. Shakkottai, "On the Elasticity of Marking Functions: Scheduling, Stability, and Quality-of-Service in the Internet," Proceedings of the 39th Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, March, 2005
C. W. Yang and S. Shakkottai, "Delay Asymptotics of the SRPT Scheduler," Proceedings of the IEEE Conference on Decision and Control (CDC), December 2004
S. Bhadra, S. Shakkottai, and S. Vishwanath, "Covert Communication over Slotted ALOHA Systems," Proceedings of the 42nd Allerton Conference on Communication, Control, and Computing, Urbana, IL, October, 2004.
S. Varadarajan and N. Ramakrishnan, "Novel Runtime Systems Support for Adaptive Compositional Modeling in PSEs,"Future Generation Computer Systems (Special Issue on Complex PSEs for Grid Computing'), Vol. 21, No. 6, 20 pages, June 2005, to appear.
C. Na, J. K. Chen, T. S. Rappaport, "Traffic Statistics and Throughput Models for Several Applications,"Proceedings of IEEE Global Telecommunications Conference (Globecom) 2004, Nov 29 - Dec 3.
J. He, A. Verstak, L. T. Watson, C. A. Stinson, N. Ramakrishnan, C. A. Shaffer, T. S. Rappaport, C. R. Anderson, K. Bae, J. Jiang, and W. H. Tranter, "S⁴W: Globally Optimal Transmitter Placement for Indoor Wireless Communication Systems,"IEEE Transactions on Wireless Communications Vol. 3, No. 6, pages 1906--1911, Nov 2004.
M. Heffner, N. Ramakrishnan, and S. Varadarajan, "Abstracting Adaptivity in Scientific Computations via Runtime Recommender Systems and the Weaves Framework, Session on Adaptivity in Parallel and Distributed Computing through Interoperating Systems and Applications" (A. Stathopoulos and D. Nikolopulos, organizers), Abstracsts of the SIAM Conference on Parallel Processing for Scientific Computing, San Francisco, CA, 2004.
J. Mukherjee and S. Varadarajan, "Weaves: A Framework for Reconfigurable Programming," International Journal of Parallel Processing, to appear.
C. Na and T. S. Rappaport, "Measured Wireless LAN Public Hotspot Traffic Statistics," IEE Electronic Letters, Vol. 40, No. 19, pp. 1202-1203, September 2004.
H. Wang and T. S. Rappaport, "A Parametric Formulation of the UTD Diffraction Coefficients for a Dielectric Wedge,"Proceedings of 2004 IEEE Antennas and Propagation Society International Symposium and URSI National Radio Science Meeting, Monterey, CA, June 20-26, 2004
W. Wu, A. Arapostathis, and S. Shakkottai, "Optimal Power Allocation for a Wireless Channel under Heavy Traffic Approximation," Proceedings of the 38th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, March 2004.
Y. Yi and S. Shakkottai, "Hop-by-hop Congestion Control over a Wireless Multi-hop Network,"Proceedings of IEEE Infocom, Hong Kong, March 2004.
S. Shakkottai, "Asymptotics of Query Strategies over a Sensor Network,"Proceedings of IEEE Infocom, Hong Kong, March, 2004.
Y. Yi, S. Deb, and S. Shakkottai, "Short Queue Behavior and Rate Based Marking," Proceedings of the 38th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, March 2004.
M. Airy, B. Mondal, R. Heath, and S. Shakkottai, "Iterative, Rate-Constrained Capacity of MIMO Broadcast Channels,"Proceedings of the 38th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, March 2004.
Y. Yi, S. Deb, and S. Shakkottai, "Time-scale Decomposition and Equivalent Rate Based Marking,"IMA Worshop: Measurme, IEE Electronic Letters, Vol. 40, No. 19, pp. 1202-1203, September 2004.ent, Modeling and Analysis of the Internet, University of Minesota, MN, January 2004.
B. Rengarajan, J. K. Chen, S. Shakkottai, T. S. Rappaport, “Connectivity of Sensor Networks with Power Control”, IEEE Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, November 9-12, 2003.
S. Shakkottai, T. S. Rappaport, P. C. Karlsson, “Cross-Layer Design for Wireless Networks”, IEEE Communications Magazine, Volume 41, No. 10, October 2003, pp. 74-80.

Presentations

T. S. Rappaport, C. Na, J. K. Chen, “Convergence of Cellular and Wireless LAN: Hotspot Traffic Statistics and User Trends,” invited talk, CTIA show, March 22, 2004.

Links to Source Code or Manual of Montage Projects

Site Specific System Simulator for Wireless Communications (S⁴W)
PCOM² and CODE² Framework Download , Example Download

Acknowledgement and Notes

This material is based upon work supported by the National Science Foundation under Grant No. 0305644. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.