Classifying PSTN Switching Stations: A National Security Agency Application

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 networks switching stations must be known. This thesis develops an integer linear programming model for accomplishing this classification. In this model, a PSTN is represented 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 networks topology and employ various heuristics to reduce the size of the problem are evaluated. The model is implemented in GAMS Development Corporations Generic Algebraic Modeling System and sample PSTNs are solved using IBMs 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.