Message scheduling or call request scheduling is the process offinding optimal routing for a set of circuit connection requests througha communications network. Each request has a single source with one ormore destinations. Furthermore, different requests may have differentsource and different destination nodes. Finding optimal routing for aset of requests is called the point to multipoint routing problem(PMRP). The current practice in solving the PMRP is to consider eachpoint to multipoint request as a collection of point to point requests,and then solve each paint to point request. This is very costly andgenerally produces poor results. The paper presents an algorithm for thepoint to multipoint routing problem that uses a genetic algorithm and aheuristic Steiner tree algorithm. The genetic algorithm allows thescheduler to find an optimal or near-optimal path through the networkfor each request. In the algorithm each request is treated as a wholeand not as a collection of point to point requests. Furthermore, given aset of point to multipoint routing requests, the algorithm considersvarious subsets sizes of the original set of requests and produces anoptimal or near-optimal ordering of the requests for the specifiedsubset size. They run the PMRP algorithm on several test cases withexcellent results
展开▼
