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

Meet the Team



Students Graduated

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-COM2 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-COM2 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-COM2 compiler to incorporate measurement components and dynamic linking and adaptation of runtime adaptation of codes compiled under the P-COM2 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 S4W 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 S4W 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 S4W 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 S4W software and improved it by adding difraction and improved ray tracing capabilties. The S4W 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 S4W 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 S4W 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 S4W 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 S4W 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

Meeting Minutes

PhD Dissertation

MS Thesis

Undergraduate Honors Thesis






Links to Source Code or Manual of Montage Projects


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.

©2002-2012 The Wireless Internet Center for Advanced Technologies (WICAT and NYU Wireless) All rights reserved. Please read our Copyright, Trademark and Disclaimer Notices. Contact Webmaster