Patent ID: 6215771
Filing Date: 2001-04-10
Classification: H04J,H04L,H04Q

Abstract:
A method of configuring a telecommunications network so as to optimise traffic routing within the network and to select optimised traffic routes, said network comprising a plurality of nodes interconnected by communications links, each said link having a predetermined bandwidth capacity and incorporating one or more communications channels, the method comprising the steps of determining for every pair of nodes in the network a set of n possible shortest paths comprising a sequence of links between those nodes where n is a power of 2, assigning to each said shortest path a respective n bit binary code, forming groups of said shortest paths, each said group containing shortest paths one selected from each set and each group being represented as a unique bit string comprising a sequence of the binary codes of its component paths, assigning a cost value to each said shortest path and determining for each said group a cost term comprising the sum of the cost values of its component paths, for each said group of paths, constructing a utilisation table identifying a traffic demand imposed on every network link use by the paths of that group and determining a congestion factor comprising the number of links whose bandwidth capability would be exceeded by a predetermined level of usage, determining for each said group a bandwidth factor comprising the number of communications channels that will be required to support the traffic demand, determining for each said group of paths a fitness function comprising a weighted sum of the cost factor, the congestion factor and the bandwidth factor for that group of paths, assembling a population pool of groups of paths selected according to their respective fitness functions, selecting from the population pool a gene pool of groups of paths of preferred fitness function, generating an offspring pool from said gene pool and population pool via a genetic operator, and repeating said selection and offspring pool generation to determine a network routing solution achieving a predetermined fitness function value, wherein pairs of members of the gene pool are selected at random and, with a first predetermined probability, identically positioned portions of their bit sequences are interchanged, wherein mutations are introduced into the gene pool by introducing random changes in individual bit values with a second predetermined probability, wherein said first and second probabilities are adjusted in value during the route selection process, and wherein said weighting values are adjusted for particular routes so as to render those route less favourable for selection, thereby preserving those routes for availability to priority customers.