SGER: Online Algorithms for Delay Sensitive Multiparty Session Communication

多方通信是互联网上的一种新兴现象。所设想的应用包括互联网电话会议，远程医疗和外科手术等。一个典型的会话涉及参与者之间的多个交互，并需要任意对参与者之间的数据传输。这些应用通常具有严格的延迟要求，例如，数据传送必须符合个人的最后期限，并且共享数据必须在有限的延迟变化内被参与者接收。如果组很大，组成员在互联网上分散得很远，每个成员需要的数据项也很多，组播到整个组的代价太大;另一方面，如果每个请求都独立回复，而不考虑其他请求，优化一个请求可能会延迟下一个请求的交付。现有的方法，不考虑数据流的相互作用，不能有效地解决延迟的要求。本项目旨在为性能分析建立理论基础，并从时延方面寻求QoS保证的算法解决方案。我们将制定实际的QoS问题到新的在线问题，并试图在多方通信的QoS问题，达到一些明确的结论。本文的研究将在理论上推动网络QoS研究和在线算法设计/分析领域的发展。

Multiparty communication is an emerging phenomenon on the Internet. The envisioned applications include Internet teleconferencing, telemedicine and telesurgery etc. A typical session involves multiple interactions among participants, and requires data transferring between arbitrary pairs of participants. These applications usually have stringent delay requirements, e.g., data delivery must meet individual deadlines, and the shared data must be received by participants within bounded delay variation. If the group is large, group members are scattered far from each other in the Internet, and each member needs a variety of data items, multicasting to the entire group is too costly; On the other hand, if each request is replied independently regardless of other requests, optimizing one request may delay the delivery of the next. Existing approaches that do not consider the interaction of data streams cannot address the delay requirements effectively. This project aims to establish the theoretical basis for performance analysis and seek algorithmic solutions for QoS guarantees on the delay aspect. We will formulate practical QoS problems into new online problems and try to reach some definitive conclusions on QoS issues in multiparty communication. The proposed research will advance the fields of QoS research in networks and online algorithm design/analysis in theory.