<p>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.</p>
<p>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</p>
<p>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.)</p>
<p>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).</p>
<p><a href="https://i.sstatic.net/xpJgR.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xpJgR.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2021-12-13T22:12:52.053Z
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.)
Neal Young
CC BY-SA 4.0
2021-12-21T22:54:20.000Z
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.
JimN
CC BY-SA 4.0
2021-12-22T19:18:29.767Z
@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](https://d2vlcm61l7u1fs.cloudfront.net/media%2F47e%2F47eb291e-7bbb-452c-bb88-3530f07f8f6d%2FphpfCFvXz.png)
Ramon
CC BY-SA 4.0
2021-12-22T19:19:25.263Z
@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.
Ramon
CC BY-SA 4.0
2021-12-22T19:20:57.053Z
@JimN: You are right. I addressed the issue raised by you in the comment responding to Neal.
Ramon
CC BY-SA 4.0
2021-12-23T17:23:47.697Z
For the notion of an "optimal" link structure to be well defined, you need to define a single objective that you want the link structure to optimize.  From reading between the lines, it seems that you want to minimize the aggregate distance traveled by packets, assuming that for each pair (p, q) of nodes the number of packets sent from p to q is specified by the entry $M_{pq}$ of some "traffic matrix", and each packet from p to q travels on the clockwise path on the circle from p to q, except that when it is possible to jump ahead using a chord, the packet does that.  Is that correct?
Neal Young
CC BY-SA 4.0
2021-12-29T10:28:55.853Z
@NealYoung: It is correct.
Ramon
CC BY-SA 4.0
2021-12-29T14:27:24.197Z
Looks like you already know about [Chord](https://en.wikipedia.org/wiki/Chord_(peer-to-peer))?
Neal Young
<ds.algorithms><graph-theory><graph-algorithms><optimization>
optimization on graph edges selection
Ramon
# optimization on graph edges selection

(Asked by: username_0 on 2021-12-13)

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](https://i.sstatic.net/xpJgR.png)](https://i.sstatic.net/xpJgR.png)

**Tags:** ds.algorithms, graph-theory, graph-algorithms, optimization

> **Comments:**
> **username_1**: 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.)  
> **username_2**: 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.  
> **username_0**: @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](https://d2vlcm61l7u1fs.cloudfront.net/media%2F47e%2F47eb291e-7bbb-452c-bb88-3530f07f8f6d%2FphpfCFvXz.png)  
> **username_0**: @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.  
> **username_0**: @username_2: You are right. I addressed the issue raised by you in the comment responding to Neal.  
> **username_1**: For the notion of an "optimal" link structure to be well defined, you need to define a single objective that you want the link structure to optimize.  From reading between the lines, it seems that you want to minimize the aggregate distance traveled by packets, assuming that for each pair (p, q) of nodes the number of packets sent from p to q is specified by the entry $M_{pq}$ of some "traffic matrix", and each packet from p to q travels on the clockwise path on the circle from p to q, except that when it is possible to jump ahead using a chord, the packet does that.  Is that correct?  
> **username_0**: @NealYoung: It is correct.  
> **username_1**: Looks like you already know about [Chord](https://en.wikipedia.org/wiki/Chord_(peer-to-peer))?  

---

## 0 answers

