Reference no: EM131485578
(A) Program read input graph from a text file ( containing information about graph like edge, node, number of requested pair node), set of middlebox location, set of request node pair(node pair is like connection between 2 node who connect for communication).
NOTE: middlebox :- is like any firewall, proxy, network function which will be placed between two node pair and program is to assign the middleboxes between them using the algorithm and generate output as text file with number of assigned middleboxes.
(B): Apply approximation algorithm on the graph read from text file.
In algo: in step 5 we need to apply augmenting path method. Algorithm is regarding deploying middlebox in graph by applying augmenting path method( based on Ford-Fulkerson Algorithm - Find BFS and then DFS -- used for maximum matching). When there is no more augmenting exist in graph, then graph is max matching graph.
Details how algo work here::: ml is potential middlebox location. M is empty set, U is set of all nodes and A(M) is partial assignment on given empty set. Initially partial assignment is empty. Algorithm starts with empty assignment and route through each possible middlebox location ml ? U \ M ( U is union here). The function ? calculates matchings on bipartite graph by using augmenting path methods (tmp<- ?(M U {ml}) U is union here ) and after calculating submodular function, if matching is more than initial optimal matching (opt <- 0) then it updates opt and deploy middlebox result along with already deployed middlebox in graph. The algorithm performs |M*| iterations on given graph where |M*| is amount of middleboxes. For each ml ? U \ M, ?(M U {ml}) is calculated by using augmenting path method and middlebox location ml with highest value as added to set M.
(C): Produce graph as output and/or produce log file with details of assigned middlebox after applying algorithm, number of nodes.
