Observing the current situation in the infocummunication industry, it is clear that meeting the network demands of users is proving challenging for service providers. The part metrics like delay and jitter play in customer satisfaction is ever increasing. Furthermore, new network applications and services have stringent reliability and quality requirements. Therefore contrary to previous trends, these days the primary concern is no longer bandwidth; rather, the most important aspect of the network is its quality of service. Due to the spread of optical technologies (such as passive optical networks) modern access networks can provide sufficiently high speeds without difficulty. However, providers are struggling to ensure the reliability of their networks, and as a result of the unique (tree) topology of said networks, the delay of inter-network traffic can be high.
My task was to design, implement, and test algorithms that improve the quality of service attributes of the network. In my thesis, I have chosen to investigate two methods in detail. First I considered extending the existing network topology with new connections as a method of improvement. On the one hand, these new links offer alternative routes for user traffic, and improve the reliability of the network, because they offer a chance to bypass failed segments. One the other hand, latency may be reduced if they are used not only as a protection method, but also during normal operation. To select the new connections that have to be inserted into the network for best results, I have designed and implemented an integer linear program, based on solving the famous travelling salesman problem in an auxiliary graph generated from the original input.
The other method presented in my thesis selects a number of existing nodes and upgrades them into optical mirrors; therefore since this solution does not alter the tree topology, the network’s reliability remains unchanged. The mirrors greatly reduce latency by offering shorter and more direct communication paths between nodes in the network; they also eliminate a significant amount of unnecessary traffic because the new, shorter paths are not required to visit the root, thus reducing the overall network load. I have established a metric that can measure the value of a mirror placement based on the traffic patterns and the topology of the network. I have proposed an integer linear program to choose which nodes to turn into mirrors. Moreover, I have implemented an alternative method, that is local and greedy; this second algorithm sacrifices optimality to ensure that it can scale well with the network’s size.
Simulations have proven the efficiency of both the integer linear program responsible for inserting new connections and the greedy mirror insertion method.