We consider a backbone network with $n$ nodes, and $n(n − 1)$ ingress-egress (IE)pairs. We index nodes as $i = 1,\ldots,n$, and IE pairs as $(k, l)$, which refers to ingress (source) $l$ and egress (destination) $k$, i.e., from node $l$ to node $k$. The traffic from node $l$ to node $k$ is denoted $T_{kl} \geq 0$. Note that the traffic exiting at node $k$ is given by $E_k = \sum_l T_{kl}$. We refer to the matrix $T$ as a traffic pattern.
The network has m directed edges, with adjacency matrix $A$, where $$ A_{ij} = \begin{cases} +1 \textrm{ if edge }j \textrm{ enters node }$i$ \\ −1 \textrm{ if edge }j\textrm{ leaves node }i\\ 0\textrm{ otherwise}. \end{cases} $$ We allow the splitting of traffic corresponding to one IE pair, which means we can aggregate all flows in the network that share the same destination or egress node. We let $F_{kj} \geq 0$ denote the flow on edge $j$ that is destined for destination $k$.
Conservation of flow and capacity constraints are given by the convex constraints $$ \begin{array}{cc} T + AF^T = 0, \\ F^T1 \leq c,\; 0 \leq F \end{array} $$
The optimization problem is to maximize the utility $U(T) = \sum_{k\neq l}\psi(T_{kl})$ of the traffic flows, subject to conservation of flow and edge capacity constraints: $$ \begin{array}{cc} \textrm{minimize} & \sum_{k\neq l}\psi(T_{kl}) \\ subject to & T + AF^T = 0, \\ & F^T1 \leq c, \\ & 0 \leq F \end{array} $$
In [1]:
import numpy as np
import cvxpy as cvx
import matplotlib.pyplot as plt
# import networkx as nx
%matplotlib inline
In [22]:
np.random.seed(1)
n = 5
edges = [(0,1), (3, 4), (1,2), (2,3), (4,2), (4, 0)]
m = len(edges)
A = np.zeros((n, m))
for idx, edge in enumerate(edges):
A[edge[0], idx] = -1
A[edge[1], idx] = +1
F = cvx.Variable((n, m))
T = cvx.Variable((n, n))
# Masks out diagonals.
M = (np.ones((n, n)) - np.eye(n)).astype(bool)
c = np.ones(m)
T_min = np.zeros((n, n))
obj = cvx.Maximize(cvx.sum(cvx.sqrt(T[M])))
prob = cvx.Problem(obj,
[A*F.T == T,
F >= 0,
cvx.sum(F, 0) <= c,
(T - T_min)[M] >= 0])
# Define problem data.
prob.solve(solver=cvx.ECOS, verbose=True)
Out[22]:
In [26]:
# Plot results.
import networkx as nx
G=nx.Graph()
G.add_nodes_from(range(n))
G.add_edges_from(edges)
print("Nodes of graph: ")
print(G.nodes())
print("Edges of graph: ")
print(G.edges())
# Plot the result.
plt.figure(figsize=(12,10))
pos=nx.spring_layout(G)
node_colors = cvx.diag(T).value.tolist()
nodes = nx.draw_networkx_nodes(G,pos,node_color=node_colors, with_labels=False,
node_size=100, node_cmap=plt.cm.Reds)
edge_colors = cvx.sum(F, 0).value.tolist()
edges = nx.draw_networkx_edges(G,pos,edge_color=edge_colors,width=4,
edge_cmap=plt.cm.Blues, arrows=True)
plt.colorbar(edges, label='Edge flow')
plt.colorbar(nodes, label='Node traffic')
plt.axis('off')
plt.show()
In [3]:
grid_dim = 7
p = grid_dim*grid_dim
k = 6
n = 2*(grid_dim-1)*grid_dim
U = np.random.uniform(20, 50, size=k)
L = -np.random.uniform(0, 5, size=p)
c = np.random.uniform(5, 10, size=n)
# Create a networkx graph.
# G.nodes() is a list of node keys.
# G.edges() is a list of edge keys of the form (node key, node key).
G = nx.grid_2d_graph(grid_dim, grid_dim)
# Map node key to the index in nodes.
node_key_to_idx = {key:i for i, key in enumerate(G.nodes())}
# Connect nodes via edges.
for i, key in enumerate(G.edges()):
idx1 = node_key_to_idx[key[0]]
idx2 = node_key_to_idx[key[1]]
#edges[i].connect(nodes[idx1], nodes[idx2])
# Plot the result.
plt.figure(figsize=(12,10))
pos = dict(zip(G,G)) # dictionary of node names->positions
node_colors = [1 for node in nodes]
nodes = nx.draw_networkx_nodes(G,pos,node_color=node_colors, with_labels=False,
node_size=100, node_cmap=plt.cm.Reds)
edge_colors = [1 for edge in edges]
edges = nx.draw_networkx_edges(G,pos,edge_color=edge_colors,width=4,
edge_cmap=plt.cm.Blues, arrows=True)
plt.colorbar(edges, label='Edge flow')
plt.colorbar(nodes, label='Node source')
plt.axis('off')
plt.show()