Distributed Processing and Networking
Our focus in this area is in the application of distributed search
methods to resolve collisions and to identify bottlenecks in distributed
systems and computer networks, and the design of efficient protocols for
- Real-Time Multimedia Loss Concealment.
The research aims to design protocols and coding methods for the concealment of errors
that occur during real-time transmission of audio and video data over unreliable IP networks,
such as the Internet and wireless networks. Since video and audio transmissions may tolerate
some degree of loss, it is necessary to study schemes that involve trade-offs in their
real-time requirements and tolerance to loss. The schemes studied will involve proper
coding of transmitted data, protocols to schedule transmissions and feedbacks, and
reconstruction schemes to recover lost data. Results of this research will lead to
more robust transmissions of real-time video and audio data over unreliable networks.
- Multiaccess problem: the search for a single responding station.
The multiaccess problem, or the identification of a single station
to use a shared channel, is an important problem in local-area
and mobile networks. Although the number of contention slots
needed to resolve contention in the original binary backoff algorithm
grows linearly with respect to the number of contending stations,
the variance of inter-channel access delays grows very quickly
with increasing number of contending stations. Consequently, the
number of contending stations in such networks must be kept
We have developed an efficient collision-resolution algorithm for
multiaccess networks with a geometrically distributed inter-channel
access delay and an average delay that is constant, independent of
the number of contending stations.
In this protocol, each station chooses a random number in a common
range, and stations inside a common window can contend for the
channel in the next contention slot. By reducing the common window
successively using dynamic programming, a single station will eventually
be isolated. The speed of the protocol can be improved by storing
the optimal window in each step ahead of time in lookup tables.
A U.S. patent on this invention was awarded in 1986.
The protocol has also been extended to use in mobile networks.
The window-based scheme for contention resolution was extended to
work in multiprocessor bus networks and networks with multiple
contention busses. A variation of this algorithm was implemented
in the Sequent Balance 8000 multiprocessor.
Load balancing problem: the search for stations with the minimum and the maximum load.
By implementing the window protocol in software, load balancing
can be carried out effectively in software in local-area networks.
The window protocol implemented in software can find stations
with the maximum and the minimum workload in constant time on the
average, independent of the number of contending stations.
Load balancing strategies: learning and generalization.
Using evolutionary learning, new load balancing strategies
were created, verified on a real system, and generalized
to systems not tested in learning. The key issue involves
the development of an
experimental system that allows load balancing strategies with
different parameters to be tested under identical workload
Load balancing: applications.
The mapping of neural-network learning on distributed-memory
multiprocessors has been studied.
Protocols for real time transmissions.
In this area we study efficient protocols and related performance
issues to transmit real-time data over computer networks. We study
related issues in quality of service, protocols for efficient
audio, image, and data coding and reconstruction, and the implementation
and testing of these protocols on prototypes.
Resource sharing interconnection networks: the distributed search
for free resources of a specific type.
The problem involves the design of architectural supports
in a multistage interconnection network to search for free
resources of a specific type to satisfy incoming requests.
The problem has been transformed into a maximum-flow problem
that can be solved in polynomial time. Hardware implementations
of the distributed maximum-flow problem have also been studied.
The main applications studied are the file-placement
problem and the use of a broadcast bus to aid distributed
query processing and concurrency control in distributed
Other protocols and applications.
Miscellaneous and protocols and applications have been studied, specifically,
distributed search on the Internet.