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.
