Research in Communications
Research in the area of Communications, networks and systems includes fundamental work on data networks, information theory and communication theory. Systems research includes satellite communications, wireless communication, optical communications and networks.
Data Communication Networks
The major objective of this work is to develop the scientific base needed to design data communication networks that are efficient, robust, and architecturally clean. Wide area and local area networks, high-speed and low-speed networks, and point-to-point and broadcast communication channels are of concern. Some specific topics of current interest are power control, the capacity of wireless channels with parallel relays, splitting and successive decoding for wireless networks, media access control protocols, routing in wireless and satellite networks, quality of service control, diverse traffic mixes, failure recovery, topological design, and the use of pricing as a mechanism for efficient resource allocation. Professors Dimitri P. Bertsekas, Vincent Chan, Robert G. Gallager, Muriel Medard, Eytan Modiano, and John Tsitsiklis, Doctors John Chapin, Steven G. Finn, Charles Rohr, and Peter Young, and their students are conducting this research.
Optical Networks
Professors Chan, Gallager, and Modiano continue to work on the next-generation internet program funded by DARPA. The focus of the program is to design and prototype the next-generation local and metropolitan area access network (MAN) with an increase in data rate of up to four orders of magnitude, but at the same time to decrease the cost of delivery per bit by approximately the same amount.
The network will use multiple wavelengths (colors) to increase capacity and optical devices for routing and switching. New results on the use of mesh topology for MANs indicate that the cost structure of MANs is heavily dependent on the optical cross-connect technology at the switching nodes. Efficient topologies that nearly achieve fundamental bounds on performance are found, and these architectures are very different from previously used and accepted architectures. One interesting architectural feature of the network will be an option for the user of the network to set up direct, end-to-end optical flows for future applications with very large transactions (gigabytes and beyond). A new program sponsored by DARPA on all-optical, local and metro area networks with ultra-high reliability and performance has been initiated by Professors Chan and Modiano. The objective of this research is to use optical network technology to build a highly reliable network that services high-end applications, such as aircraft control and coherent collaborative sensing. It is the expectation of the sponsor that MIT will provide architecture lead and guidance for industry contractors. This program emphasizes cross-layer network optimization and nontraditional networks that provide a faster response than current networks, along with arbitrarily high delivery reliability.
Prof. Medard, in collaboration with her students, is working on issues of reliability and robustness of backbone and access networks. Her first project is in the area of probabilistic analysis of optical network robustness as part of an AFOSR University Research Initiative (URI) with Stanford University, University of Illinois, and Caltech. The work in this area considers robustness and security of all large network systems, such as backbone communication networks and power grids. Recent results in this area include results for robustness for both regular and non-regular random graphs. By extending to non-regular graphs results previously available only for regular graphs, the results allow significant expansion of the types of large networks that may be considered. Other MIT researchers on this URI project are Professors George Verghese and Bernard Lesieutre.
Prof. Medard and her students are also working on reliability of access networks. She is the MIT member of a recent NSF Information Technology Research (ITR) project with the University of Illinois in the area of robust optical local and metropolitan area networks. This project, conducted in collaboration with Prof. Chan, considers the use of coarse unit of measure (UOM) and limited signal-to-noise ratios (SNRs) in architecting robust networks. Results in this area concern the optimal design of local area networks with a limited number of nodes. The results have extended the understanding of circulant graphs for low probability of failure. Moreover, they have shown that, under extreme stress conditions, for which failure probability rises, the characteristics of graphs required to ensure robustness are very different than in the low-failure probability mode. The results have also provided analytical results for networks with correlated failures.
Satellite Communications and Networking
The overall goal of this research addresses architecture designs for efficient data communications over low-Earth orbiting satellites (LEOs) and other more generalized satellite systems, especially when they are interconnected with terrestrial fiber and wireless systems to form a heterogeneous global internet. There are three main components to this research:
1. Adaptive power and rate control techniques for satellite communication systems over time-varying satellite channels to achieve greatly improved (an order of magnitude or more) data throughputs
2. Efficient routing algorithms over a time-varying integrated and heterogeneous global network for maximum resource utilization, especially the space segments
3. Efficient congestion control algorithms at the transport and network layers for an integrated satellite/terrestrial network
Professors Chan, Modiano, and Tsitsiklis, Doctors Finn and Rohr, and their students are conducting this research.
This year, Prof. Modiano and his students developed a power allocation scheme, for a satellite data relay to a ground sink problem with multiple downlink beams, that maximizes the satellite's data throughput. Power is allocated to each beam according to the number of packets in the corresponding buffer and the channel conditions corresponding to that beam. The work is significant because it shows that the optimal physical layer power allocation takes into account network layer buffer occupancy. This contrasts with the traditional layered view of network protocols, where functions at the different layers are de-coupled. Moreover, it shows that the capacity of a satellite system can be greatly increased through the use of the optimal power allocation algorithm. Such increase in system capacity is critical to the success of future satellite systems aimed at data delivery. Prof. Modiano's group also developed energy-efficient transmission scheduling schemes that take into account channel conditions in deciding when to transmit data. These schemes can be used to significantly reduce the amount of energy needed for data transmission.
During the past year, Prof. Chan and his students have researched the power and beam allocation method based on traffic demands and channel conditions over satellite downlinks. As the satellite system uses narrower beams to support many small users within its coverage area at high data rates over high frequency bands, it becomes more attractive to implement an agile antenna power pattern and dynamic beam scheduling method. The study indicates that the use of a parallel multibeam scheme with optimized power allocation provides a substantial power gain and fairness advantage amongst different demands. By coupling power allocation with multibeam scheduling when the number of active beams is smaller than the number of cells, Prof. Chan's group shows that a modest number of active parallel beams are sufficient to cover many cells efficiently, even with the steady-state delay constraints. The delay analysis is coupled with flow/congestion control by controlling incoming traffic according to channel conditions and delay requirements. The team considers very slow channel fading due to rain attenuation, compared to the packet length and its deadline requirement. This enables the team to explore a quasi-static channel condition with fixed capacity during the interval of consideration.
On congestion control for hybrid networks, Prof. Modiano and his students have explored the interaction between protocols at different layers. They developed models for analyzing the interaction between TCP and lower-layer protocols. In particular, they developed a model for the interaction between TCP and the Aloha multiple-access protocol and showed that channel "collisions" due to the Aloha protocol result in TCP window closures that significantly degrade end-to-end network performance. In order to alleviate the problem, they are exploring alternative access schemes that result in much-improved end-to-end throughput.
In the study on satellite system design, and specifically on capacity dimensioning and routing for hybrid satellite and terrestrial networks, the group has formulated satellite-link dimensioning and routing as a two-stage stochastic programming problem and has solved for the optimal link capacity. This will minimize the sum of satellite network investment cost for different link-cost to user-entry-rejection-cost ratios.
In addition, Prof. Modiano has initiated a research program with NASA exploring interactions in space networks between protocols at different layers of the protocol stack. A particular focus of this project will be an examination of the overall network architecture across multiple layers of the network hierarchy, seeking opportunities for cross-layer optimization. Such an approach is of particular importance for NASA's space Internet because of its heterogeneous nature. It is a goal of this project to obtain an understanding of the interactions between network layers so that overall, end-to-end performance can be significantly improved.
Space Relay Networks
In the last six months, Prof. Modiano and his students initiated a study on the preferred constellation topology of the space backbone. Based on providing coverage for spaceborne users alone, the minimum number of satellites in the backbone constellation can be as small as 12 for low-Earth orbiting satellites (LEOs), six for medium-Earth orbiting satellites (MEOs) and the usual three for geostationary-Earth orbiting satellites (GEOs).
The ability to reconfigure inter-satellite crosslinks via pointing, thereby establishing new links between satellites, allows a new paradigm in the architecture of the physical network topology. The researchers believe reconfiguration of connection topologies permits much more efficient use of crosslinked assets, especially in situations with a few data sinks. Additionally, flexible networking architectures with resource sharing may lead to significant cost savings for individual space mission systems.
The team also completed a mini-study to reach a baseline understanding of current traditional space-qualified processors and commercial processors. The study confirms the common belief that radiation-hardened processors are at least one order of magnitude slower (approximately 7 to 10 years slower) than commercial processors. This suggests that the team's vision of using commercial processors as replenishable, networked space-borne processors may lead to significant improvement of computation power in space. Subsequently, Prof. Modiano's group has begun to analyze the architecture of a networked processing system in space and the associated problem of task scheduling.
The researchers continue to look at resource management, scheduling, and routing for a satellite constellation network with optical crosslinks and RF downlinks. They developed a basic "separation" result that allows for separate control of crosslinks and downlinks while maintaining throughput optimality and ensuring robustness to link failures and changing channel conditions. Scheduling algorithms for both the satellite crosslinks and downlinks have been developed. Moreover, a fundamental tradeoff between the complexity of the scheduling algorithm and the resulting packet transmission delay has been established.
Multiple-Access Wireless Channels
Prof. Medard is working in the area of capacity and stability of coded packetized multiple-access channels with students at MIT and with Prof. Sean Meyn of the University of Illinois, Urbana Champaign and Prof. Andrea Goldsmith of Stanford University. This research establishes the capacity of such channels and examines trade-offs between energy and delay. It allows the uncoordinated access in satellite networks of multiple users without requiring total performance in the event of a packet collision. Prof. Medard is also developing with students an emulator using an IS-95 code division multiple-access (CDMA) standard. This emulator provides a practical implementation of theoretical coded multiple-access results.
Along with Prof. Medard, Professors Chan, Gallager, Modiano, and Moe Win, Doctors Chapin, Finn, Rohrs, and Young, and their students are conducting this research.
Communication Under Channel Uncertainty
Prof. Medard has been investigating several issues in the area of wireless communications over uncertain channels. In collaboration with Prof. R. Srikant at the University of Illinois, she has investigated the effect of unequal channel knowledge at the sender and receiver. In particular, the team has developed bounds to assess the effectiveness of applying techniques designed for certain idealized channel models to more channels with more detailed models.
In collaboration with Prof. Goldsmith of Stanford University, Prof. Medard has investigated the capacity of time-varying channels with sender- and receiver-side information, in particular channels with perfect-side information but significant inter-symbol interference, for which no capacity formulas existed. In collaboration with Dr. Ibrahim Abou-Faycal of MIT and Prof. Madhow of University of California at Santa Barbara, she is working on the use of an adaptive modulator without feedback in which the sender adapts to the quality of the receiving channel measurement as well as the channel strength. This technique increases capacity by up to 30 percent without expressly supplemented energy and without requiring real-time computation.
Professors Medard and Zheng, with their students, have established a new, practical way of transmission over ultra-wideband channels. Their work has discovered a significant family of signals that can achieve capacity under infinite bandwidth limits, whereas only a single such scheme was heretofore known. Their work has also shown that a simple application of a simplified version of these schemes can achieve rates that approach capacity limits in the regime where energy is the main capacity limitation and in the regime where bandwidth is the main limitation. This work establishes for the first time a relation between infinite bandwidth capacity-achieving schemes and practical schemes for finite bandwidth and limited peak energy.
Prof. Medard, Dr. Abou-Faycal, and their students have established new results relating bandwidth and error probability for ultra-wideband fading channels. Their results show that error probability decreases very slowly with bandwidth and therefore, unlike non-fading channels, infinite-bandwidth performance cannot be achieved in the finite bandwidth regime. These results in effect achieve a strong coding theorem, which relates capacity, energy, bandwidth, and delay fundamentally with error probability.
Prof. Win and his graduate students are working on the application of mathematical and statistical theories to communication, detection, and estimation problems with application to measurement and modeling of time-varying channels, design and analysis of multiple antenna systems, ultra-wide bandwidth (UWB) communications systems, optical communications systems, and space communications systems. Their accomplishments include:
1. Receiver design, analysis and simulations for UWB communications. The group developed theoretical/experimental analysis techniques that enabled the efficient design and accurate performance prediction of UWB transmission. They proposed reduced-complexity Rake receivers based on partial combining (PRake) and selective combining (SRake), and evaluated the receivers' link performance in a realistic UWB channel.
2. Reduced-complexity Rake receivers. Prof. Win and his students quantified the effects of spreading bandwidth on spread-spectrum systems in dense multipath environments in terms of receiver performance, receiver complexity, and channel parameters. They created a novel analytical framework that provides 1) fundamental insights on how wideband reduced-complexity selective Rake receivers can best take advantage of multipath environments, and 2) theoretical basis for deciding how many fingers should be included in the receiver architecture for wideband systems in general and for third-generation wireless systems in particular.
3. Inverse symbol error probability (SEP) for diversity reception: The researchers derived tight upper and lower bounds on the inverse SEP for multichannel reception with MRC in fading. The new bounds enable the derivation of the symbol error outage (SEO) in a shadowing environment and are useful for the design of digital radio systems with diversity reception.
4. Efficient evaluation of error rate for hybrid diversity systems: The group derived simple explicit bounds for assessing the error rate of hybrid diversity systems. The bounds are tight and valid for all values of signal-to-noise ratios (SNR), thus alleviating the need for complicated analysis and multiple numerical integrals. Contrary to a previous conjecture, the penalty of a hybrid diversity system relative to MRC diversity was shown not to be a constant; it is not independent of the SNR and the target symbol error probability.
Wireless Ad Hoc Networks
Prof. Modiano continues to work with Draper Laboratory on management and control of mobile ad hoc networks. Such networks are of critical importance for future combat systems, sensor networks, and autonomous systems involving mobile ground and air vehicles. These systems heavily depend on cooperative control between mobile vehicles and consequently on the availability of a communication capability between the vehicles. In a dynamic, mobile environment, one cannot assume that such communication capabilities are always present. In this effort, Prof. Modiano and his students are developing architectures and protocols for providing reliable communication in this environment.
Over the past year, the team developed algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Major results include a novel polynomial time algorithm that optimally solves the minimum energy link-disjoint paths problem, as well as an optimal algorithm for the minimum energy node disjoint paths problem. The team also developed a joint routing and power allocation algorithm for a wireless network. They show that the algorithm maximizes the throughput of a wireless network in the sense that it can stabilize the network whenever the arrival rates into the network are within the network's stability region.
In addition, Professors Modiano, Eric Feron, and Nancy Lynch, along with Dr. Jinane Abounadi, are collaborating on a MURI with Stanford University and the University of Illinois on Cooperative Networked Control of Dynamical Peer-to-Peer Vehicle Systems. A major focus of the project is the interplay between communication and control in an environment of networked vehicles.
Coding and Statistical Physics
Prof. David Forney continued to investigate connections between coding and statistical physics in collaboration with A. Barg (Lucent Bell Laboratories), M. Chiang (Stanford University), A. Montanari (of Paris, visiting Prof. Sanjoy Mitter at MIT), and J. Yedidia (Mitsubishi Research Labs, Cambridge). A paper with Barg on minimum distances and error exponents of codes for the binary symmetric channel using a large-deviation-theoretic approach has been accepted for the IEEE Transactions on Information Theory. With Montanari, this approach has been extended to general discrete memoryless channels.
Sensor Web, Interference, Coding, and Statistical Mechanics
Recent research on turbo coding, decoding of low-density parity check codes, and statistical mechanisms of disordered systems has shown that there are deep connections between those subjects. Prof. Sanjoy Mitter, in collaboration with Dr. Nigel Newton, has recently given an Information Theoretic view of Maximum Likelihood Decoding and Nonlinear Estimation of Diffusion Processes. In the recently completed thesis of Maurice Chu, a unified view of Distributed Estimation with application to the Sensor Web has been presented. In the soon-to-be-completed thesis of Louay Bazzi, various aspects of coding and complexity have been investigated. Finally, Prof. Mitter, with Dr. Reuben Rabi, is developing a theory of interconnections, which has applications in distributed control, coding, and inference on graphs.
Codes on Graphs and Iterative Decoding
Prof. Forney continued his research on codes on graphs and iterative decoding algorithms. He gave several plenary talks and published a review article in this area. He also wrote several new research papers.
In joint work with A. Barg and A. Montanari, Prof. Forney redeveloped Gallager's error exponent bounds for discrete memoryless channels from the point of view of large-deviation theory, and showed that random codes typically have poorer minimum distance than random linear codes.
Quantum Information Theory
Yonina Eldar (Digital Signal Processing Group), working with Prof. Forney, has shown that the "square-root" measurement of quantum detection theory is actually a "least-squares" measurement, from which many of its properties follow. She has also shown that there is an intimate correspondence between such measurements and the "tight frames" of wavelet and signal representation theory, which allows various quantum mechanical results to be transported to frame theory. Recent results relate to geometrically uniform measurements and frames.
Network Codes
Prof. Medard, in collaboration with her students and Prof. Ralf Koetter of the University of Illinois, Urbana-Champaign, is working on an algebraic description of codes on graphs for data transmission over networks. All routing over a network can be described as a code over that network. Moreover, network capacity in error-free networking can be significantly enhanced through the use of codes over these networks. The research by Professors Koetter and Medard has developed a powerful new construct which, when extended, not only provides all the results previously obtained by graph theoretic methods, but also gives necessary and sufficient conditions for any set of connections to be feasible over a graph where we code. This research is being extended to ensure robustness when links or nodes are permanently removed. Thus, it provides results on the fundamental network management requirements for recovery from non-intermittent failures. This is the first research to establish theoretical bounds for the network management needs of networks in order to be able to recover from failures.
Prof. Medard, in collaboration with her students and with Prof. David Karger of LCS, Prof. Koetter of the University of Illinois, Urbana-Champaign, Professors Michelle Effros and Babak Hassibi of Caltech, and Dr. Abounadi of MIT, is working on using linear network codes as a unified framework for source, channel, and network coding. The researchers examine the issue of separation and code design for network data transmission environments. They have demonstrated that source-channel (or source-network) separation holds for several canonical network examples when the whole network operates over a common finite field. Their approach uses linear codes.
The researchers' simple, unifying framework for these codes not only allows them to re-establish with economy the optimality of linear codes for single transmitter channels and for Slepian-Wolf source coding; it also enables them to establish the optimality of linear codes for multiple-access and for erasure-broadcast channels. Moreover, the team has shown that source-channel separation holds for these networks. The linearity of both source and network coding thus blurs the delineation between source and network codes. The team has shown that this robustness of separation is strongly predicated on the fact that noise and inputs are independent. The researchers have illustrated the fact that design for individual network modules may yield poor results when such modules are concatenated, making end-to-end coding necessary. Thus, they argue, it is the lack of decomposability into canonical network modules, rather than the lack of separation between source and channel coding, that presents major challenges for network coding.
Free-Space Optical Communications
Under DARPA sponsorship, Professors Chan and Shapiro and Dr. Franco Wong have undertaken an ambitious new development of high-rate and high-performance free-space optical communication systems and networks. This research, a joint venture between LIDS and the Research Laboratory of Electronics (RLE), explores diversity transmitter and receiver techniques to mitigate power fading due to atmospheric turbulence. This year, the researchers extended their theoretical efforts on techniques to mitigate the effects of atmospheric turbulence, in particular scintillation, on line-of-sight optical communications. They have also begun to perform diversity reception experiments in the experimental testbed. Collaboration with Tellabs and Draper Laboratory
LIDS and Draper Laboratory are developing a novel approach to collaborative research. In this approach, the two laboratories integrate industrial research interests within MIT's research and educational environment. The key difference between this new model of collaboration and traditional approaches is the focus on human resources as the primary enabler. Toward this end, LIDS provides Draper Laboratory with access to faculty, students, visitors, facilities, and infrastructure support, while Draper Laboratory mirrors the research at LIDS in its own programs, assuming responsibility both for co-advising student research and for technology transfer as an internal corporate process. LIDS benefits from the persistent presence of industrial researchers, and our partners benefit from the leveraging of LIDS' staff.
