Algorithmic Issues in Communication Networks

本研究关注与高速通信网络的设计、维护和管理有关的算法问题。 高速综合通信网络将成为未来最重要的通信平台，提出了新的技术挑战。许多这些技术问题的本质是某些简单网络问题的交互性，例如路由和分组调度。 本研究的目的是为这些组合问题开发快速而简单的近似算法。 这些算法可以作为成功应对这些挑战的工具。 一些更有前途的方法将在真实的网络数据上进行测试。 设计有效的方法在通信网络上获得信息分组是实现宽带综合业务数字网（BISDN）标准（如ATM（异步传输模式））的主要问题之一。 数据包路由问题就是在通信网络中快速、可靠地将数据包从它们的源移动到它们期望的目的地，并且使用尽可能少的资源。 这个问题的解决方案由两个不同的（虽然决不是独立的）部分组成：为分组选择路径（路由）和分组沿着它们所选择的路径的运动调度（分组交换）。 研究的重点是两个基本的算法问题：路由和分组交换。 许多现实生活中的路由问题的组合本质是不相交路径问题。 路由问题的研究方向包括离线和在线问题的最坏情况下，和竞争分析，分别。

This research is concerned with algorithmic problems relevant to the design, maintenance, and management of high speed communication networks. High-speed integrated communication networks are going to be the most important communication platform of the future, presenting new technological challenges. The essence of many of these technological problems is the interactability of certain simple network problems, such as routing and packet scheduling. The research is concerned with developing fast and simple approximation algorithms for these combinatorial problems. Such algorithms can serve as tools for successfully answering these challenges. Some of the more promising approaches will be tested on real network data. Designing efficient methods to get packets of information across a communication network is one of the main problems in implementing Broadband Integrated Services Digital Network(BISDN) standards, such as ATM (Asynchronous Transfer Mode). The packet routing problem is simply that of moving packets in a communication network from their sources to their desired destinations quickly, reliably, and using as few resources as possible. A solution to this problem consists of two distinct (though by no means independent ) parts: a selection of paths for the packets (routing) and a schedule of the motion of packets along their selected paths (packet switching). The main thrust of the research is on the two basic algorithmic issues: routing and packet switching. The combinatorial essence of many real-life routing problems is the disjoint paths problem. Research directions for the routing problem include both off-line and online problems with worse-case, and competitive analysis, respectively.