Chen, Jingkai (Massachusetts Institute of Technology) | Fang, Cheng (Massachusetts Institute of Technology) | Muise, Christian (Massachusetts Institute of Technology) | Shrobe, Howard (Massachusetts Institute of Technology) | Williams, Brian C. (Massachusetts Institute of Technology) | Yu, Peng (Massachusetts Institute of Technology)
Current network approaches aim to maximize network utilization when routing flows. While such approaches are fast and usually result in acceptable behavior, existing methods are not mission aware. There is no concept of utility maximization, no capability to handle flows with specified deadlines and loss requirements, and no guarantees over the probability of network saturation. In the presence of network degradation due to attacks, there is no guarantee that important flows will be properly transported. In this paper, we present RADMAX, a system for Risk And Deadline Aware Planning for Maximum Utility based on constraint programming, which allows us to handle higher level mission specifications. We show the correctness of RADMAX with respect to loss and delay bounds, provide results for the optimality of RADMAX with respect to the mission utility, and review current results on computational performance.
In planning and scheduling, solving problems with both state and temporal constraints is hard since these constraints may be highly coupled. Judicious orderings of events enable solvers to efficiently make decisions over sequences of actions to satisfy complex hybrid specifications. The ordering problem is thus fundamental to planning. Promising recent works have explored the ordering problem as search, incorporating a special tree structure for efficiency. However, such approaches only reason over partial order specifications. Having observed that an ordering is inconsistent with respect to underlying constraints, prior works do not exploit the tree structure to efficiently generate orderings that resolve the inconsistency. In this paper, we present Conflict-directed Incremental Total Ordering (CDITO), a conflict-directed search method to incrementally and systematically generate event total orders given ordering relations and conflicts returned by sub-solvers. Due to its ability to reason over conflicts, CDITO is much more efficient than Incremental Total Ordering. We demonstrate this by benchmarking on temporal network configuration problems that involve routing network flows and allocating bandwidth resources over time.
By all accounts, today's Internet is not moving data as well as it should. Most of the world's cellular users experience delays of seconds to minutes; public Wi-Fi in airports and conference venues is often worse. Physics and climate researchers need to exchange petabytes of data with global collaborators but find their carefully engineered multi-Gbps infrastructure often delivers at only a few Mbps over intercontinental distances.6 These problems result from a design choice made when TCP congestion control was created in the 1980s--interpreting packet loss as "congestion."13 This equivalence was true at the time but was because of technology limitations, not first principles. As NICs (network interface controllers) evolved from Mbps to Gbps and memory chips from KB to GB, the relationship between packet loss and congestion became more tenuous. Today TCP's loss-based congestion control--even with the current best of breed, CUBIC11--is the primary cause of these problems. When bottleneck buffers are large, loss-based congestion control keeps them full, causing bufferbloat.
Bras, Ronan Le (Cornell University) | Dilkina, Bistra (Cornell University) | Xue, Yexiang (Cornell University) | Gomes, Carla (Cornell University) | McKelvey, Kevin (US Forest Service) | Schwartz, Michael (US Forest Service) | Montgomery, Claire (Oregon State University)
Our work is motivated by an important network design application in computational sustainability concerning wildlife conservation. In the face of human development and climate change, it is important that conservation plans for protecting landscape connectivity exhibit certain level of robustness. While previous work has focused on conservation strategies that result in a connected network of habitat reserves, the robustness of the proposed solutions has not been taken into account. In order to address this important aspect, we formalize the problem as a node-weighted bi-criteria network design problem with connectivity requirements on the number of disjoint paths between pairs of nodes. While in most previous work on survivable network design the objective is to minimize the cost of the selected network, our goal is to optimize the quality of the selected paths within a specified budget, while meeting the connectivity requirements. We characterize the complexity of the problem under different restrictions. We provide a mixed-integer programming encoding that allows for finding solutions with optimality guarantees, as well as a hybrid local search method with better scaling behavior but no guarantees. We evaluate the typical-case performance of our approaches using a synthetic benchmark, and apply them to a large-scale real-world network design problem concerning the conservation of wolverine and lynx populations in the U.S. Rocky Mountains (Montana).