I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there.

I am working on computer networking optimization. In the simplest scenario, we model the network as a graph with a circular node topology which each edge has a cost known as weight, similar to the attached photo. Each node(vertex) can have a maximum number of X

active links (edge) to other nodes at any given time. Then it can open, maintain, or close links (each operation has a cost associated with it). If there isn't a direct edge, traffic(some data traversing from a source node to destination node) must be routed through neighboring nodes. What is the best link structure(optimal set of edges in the graph connecting nodes) in the underlying graph given the predicted traffic intensity matrix between the nodes? (The set containing the links possible to choose can be a complete graph that is represented in the figure by grey edges.)

Note: the optimal link structure should be recalculated on a regular basis to account for history (for example, it is worthwhile to keep a connection between two nodes open even though there is no traffic at the current time because it was generally a busy link in the past and the chance of using this link is high in future).

enter image description here

  • 3
    $\begingroup$ Please add details. (When you say "optimal link structure", what objective are you trying to optimize? Is it, say, the average number of links that a data packet has to travel (assuming it follows the shortest path from source to destination, and assuming that, say, each "grey" edge represents desired traffic)? Do the gray edges form a uniformly weighted complete graph? Will you settle for an answer to the static question, given that just properly formalizing a dynamic variant may be difficult? What about a rooted X-ary tree? Then each packet travels at most $2\log_X n$ links.) $\endgroup$
    – Neal Young
    Dec 13, 2021 at 22:12
  • $\begingroup$ you write "The set containing the links possible to choose can be a complete graph that is represented in the figure by grey edges." but the grey edges are not a complete graph in the picture - many pairs are missing. Can this be clarified? Also, the problem structure seems to ignore the node positions/topology of the layout - can you clarify what your circular topology has to do with the problem. $\endgroup$
    – JimN
    Dec 21, 2021 at 22:54
  • $\begingroup$ @NealYoung Comment - Part 1 Thank you for comment. By optimal structure, I mean the minimum cost between source and destination. Let me clarify: in the circular network topology, each packet should be sent to the right-hand side neighbor (e.g., In the photo, if node 7 wants to send data to node 12: the route is 7,8,9,10,11,12). Moreover, in the circular topology, some direct links(edges) between nodes that are not neighbors can be added, and we denote this link as the chord. link $\endgroup$
    – Ramon
    Dec 22, 2021 at 19:18
  • $\begingroup$ @NealYoung For instance, there exists a chord between nodes 1 and 12 in the figure). By using a chord, the routing between pairs can be done with a fewer number of traversed hops and hence less cost. Thus, this optimization problem should decide the chord link between the most beneficial nodes in the network, considering the traffic matrix in adaptive strategy. The grey links depicted in the question photo only represent the case that possible chord selection can be from a potential complete graph. Hence, the optimization algorithm will decide which edge to select (active) for the chord. $\endgroup$
    – Ramon
    Dec 22, 2021 at 19:19
  • $\begingroup$ @JimN: You are right. I addressed the issue raised by you in the comment responding to Neal. $\endgroup$
    – Ramon
    Dec 22, 2021 at 19:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.