Topology synthesis of communication networks

This dissertation addresses three topics in the field of topology synthesis of communication networks.; In the first chapter of this dissertation we investigate a suggested enhancement to Multiprotocol Label Switching (MPLS) that increases the scalability of MPLS networks through the use of a new forwarding paradigm called Intermediate Destination Removal. This new paradigm allows packets on a label switched path (LSP) in an MPLS network to be terminated before reaching the designated end-node of the LSP. Utilizing Intermediate Destination Removal results in a significant reduction in the number of labels each node has to manage, thus reduces the size of the switching tables, speeds up the forwarding process in core label-switch routers (LSRs) and increases the overall scalability of MPLS. We investigate the characteristics of this enhancement and suggest a heuristic algorithm for synthesizing paths that make effective use of the newly introduced paradigm.; In the second chapter we introduce the Connected Disc Covering problem. This problem is an extension to the classical Disc Covering problem, in which a minimal covering of a set of points in the plane is sought, using congruent unit radius discs. In our extension, the resulted covering is required to also be connected in a graph theoretical sense. The main application of this problem is the synthesis of a backbone network for roaming terminals in a mobile ad hoc network. We propose two heuristic algorithms to approximate solutions of this problem, corresponding to approximations of the Minimal Connected Dominating Set problem.; The third chapter studies possible flawed syntheses in non-homogeneous best-effort networks. We assume a strict priority scheduling policy and consider the non-homogeneous case, in which each flow may be assigned a different local priority at different nodes. We show that certain priority assignments may result in oscillatory behavior of the network. We identify and prove necessary and sufficient conditions for such oscillations to occur.