Icke-triviala billigaste väg-ruttningskonflikter - klassificering och sökmetoder
OSPFSPR-con?ictsSPRDISPRClassi?cationSearch methodsOSPFBVR-kon?ikterDesign av BVRInversa billigaste väg- problemKlassi?ceringSökmetoder.
Within telecommunication and routing of tra?c in IP-networks a protocol named?Open Shortest Path First? (OSPF) is widely used. This means that a server dealswith the routing over a network with given weights by calculating shortest paths touse for routing. If we assume that a desired tra?c pattern is given the problem isto ?nd out if it is possible to set the weights so that the desired tra?c pattern is apart of a shortest path graph. In this thesis we assume that it is a unique shortestpath. To search for weights that solve the problem leads to a complex LP-model. Analternative is to search in the LP-dual under certain restrictions. These solutions tothe LP-dual are called con?icts and a con?ict means that there exists no weights sothat the desired tra?c pattern is obtained. The goal of this thesis is to study, classifyand search for con?icts. An algorithm has been developed that ?nds some kind ofcon?icts in polynomial time with respect to the size of the graph.