Network balancing procedure that includes redistributing flows on arcs incident on a batch of vertices

摘要

A representation of a flow network having vertices connected by arcs is provided. The vertices include a first set of vertices that provide flow to a second set of vertices over arcs connecting the first set and second set of vertices. A balancing procedure in the network is performed that includes redistributing flows on arcs incident on the second set of vertices. The balancing procedure includes selecting a batch of the vertices in the second set, and redistributing flows on arcs incident on the selected batch of vertices. The selecting and redistributing are repeated for other batches of vertices in the second set.

主权项

1. A method comprising:
providing a representation of a flow network comprising a first set of vertices that provide flow to a second set of vertices over arcs connecting the first set and second set of vertices; performing, by a computer system, a balancing procedure in the flow network that includes redistributing flows on arcs incident on the second set of vertices, wherein the balancing procedure comprises:
selecting a batch of the vertices in the second set;redistributing flows on arcs incident on the selected batch of vertices, wherein the redistributing comprises:
reading flows incident on at least a portion of the first set of vertices;using the flows incident on the at least the portion of the first set of vertices to update the flows on the arcs incident on the selected batch of vertices; andupdating at least some of the flows incident on the at least the portion of the first set of vertices in response to the updated flows on the arcs incident on the selected batch of vertices,wherein the reading, using, and updating are performed by plural threads executing in the computer system;repeating the selecting and redistributing for other batches of vertices in the second set; andestablishing synchronization to prevent the updating of the at least some of the flows incident on the at least the portion of the first set of vertices from being performed by any of the plural threads until each of the threads has completed the reading.