Classifying PSTN switching stations: a national security agency application

Abstract

The U.S. National Security Agency wishes to predict the routing of messages over various communications networks. Before routing predictions can be made in a public switch telephone network (PSTN), the hierarchical level of the network's switching stations must be known. This thesis develops an integer linear programming model foraccomplishing this classification. In this model, a PSTN isrepresented as a graph in which switching stations are nodes and the logical connections between the switching stations are arcs. Algebraic constraints represent the engineering standards common to PSTNs. The model also incorporates probabilistic inferences about the class of switching stations to improve classification accuracy for networks not following typical PSTN structural practices. Preprocessing routines that analyze the network's topology and employ various heuristics to reduce the size of the problem are evaluated. The model is implemented in GAMS Development Corporation's Generic Algebraic Modeling System and sample PSTNs are solved using IBM's Optimization Subroutine Library solver on a 166 MHz desktop personal computer. Accurate classification solutions are obtained in under 2 seconds for actual PSTNs, while extremely large notional networks of over 300 nodes and 900 arcs are solved in under 2 minutes