Search

The military tactical logistics planning problem addresses the issue of distributing heterogeneous commodities (e.g., food, medical supplies, construction material, ammunition, etc.) to forward operating bases in a theatre of operations using a combination of heterogeneous transportation assets such as logistics trucks and tactical helicopters. Minimizing the logistics operating cost while satisfying the operational demands under time and security constraints is of high importance for the Canadian Armed Forces. In this study, a logistics planning model is developed to explore the trade-offs between the effectiveness and efficiency in military tactical logistics distribution. A mathematical optimization algorithm based on Column-and-Cut generation techniques is developed to find the fleet mix and size of transportation assets to meet different Quality-of-Support (QoS) parameters. This paper presents details of a new column generation decomposition approach and a solution algorithm along with an application example to demonstrate the methodology. Extensive computational results are presented in order to measure the degree of efficiency and scalability of the proposed approach, and to analyze the trade-offs between: (1) delivery time and operating cost; (2) security and operating cost.

Ethernet Ring Protection (ERP) has recently emerged to provide protection switching for Ethernet ring topologies with sub-50 ms failover capabilities. In addition to Ethernet's cost-effectiveness and simplicity, ERP's promise to also provide protection in mesh packet transport networks positions Ethernet as a prominent competitor to conventional SONET/SDH and the technology of choice for carrier networks. Higher service availability, however, in ERP mesh networks has been challenged by the issue of network partitioning and the contention for protection resources which may be caused by concurrent failures. In this paper, we show that in a mesh network designed to withstand only single failure situations, network services usually suffer from two outage categories subject to concurrent dual-link failures. We address the problem of minimal capacity network design to provide high service availability against concurrent dual-link failures. We cast this combinatorially complex design problem as an optimization one and show that higher service availability can be achieved by proper RPL (Ring Protection Link) placement and ring hierarchy selection. The objective is to maximize the network flow under any dual-link failure scenario. Our design achieves minimal capacity allocation that minimizes the number of service outages (up to 37%) therefore achieving higher service availability. Numerical evaluation and comparative study show that the joint desgin approach of the ILP model provisions 8% less capacity than the sequential two-step approach to achieve similar service availability.

Ethernet Ring Protection (ERP) has recently emerged to provide protection switching for Ethernet ring topologies with sub-50 ms failover capabilities. ERP's promise to provide protection in mesh packet transport networks positions Ethernet as a prominent competitor to conventional SONET/SDH and as the technology of choice for carrier networks. Higher service availability, however, in ERP has been challenged by the issue of network partitioning and contention for shared capacity caused by concurrent failures. In this paper, we show that in a network designed to withstand single-link failure, the service availability, in the presence of double link failures, depends on the designed ERP scheme, i.e., the RPL placement as well as the selection of ring hierarchy. Therefore, we present a study for characterizing service outages and propose a design method which strikes a balance between capacity requirement and service availability (i.e., the number of service outages resulting from concurrent failures). We observe that through effective design, remarkable reduction in service outages is obtained at a modest increase in capacity deployment.

Network survivability is a key design issue for optical transport mesh networks. Various survivability schemes have been introduced among which p-cycle has (and continues) attracted quite a lot of attention because of its fast and efficient protection capabilities. The concept of p-cycle has been generalized to pre-cross-connected trails, or p-trails, by exploiting the fact that providing pre-cross-connected protection paths and obtaining fast restoration do not necessarily require a cyclic structure as in p-cycles. In this paper, we investigate the benefits and sharing capabilities of p-trails and observe that non-simple p-trails and p-cycles can be built from merging simple trails. We derive two ILP models for survivable network design using p-trails. Our first design model is a simple ILP whose optimal solution relies on the exhaustive enumeration of all simple trails in the network. We observe that the size of our ILP model, and therefore the computation time, become prohibitively large making the model unpractical for larger network instances. Therefore, to overcome this scalability issue, we develop an enhanced model for this complex optimization problem using the column generation (CG) decomposition technique. Our developed design approach is shown to be very scalable, as opposed to other prior p-trail design methods; further, we show that p-trails are more efficient than p-cycles in terms of protection resource redundancy in the network.

While many have advocated for the use of Virtual Local Area Networks (VLANs) as a way to provide scalable traffic management, finding the optimal traffic split (mapping) among VLANs to achieve load balancing has turned out to be a very challenging and combinatorially complex problem to solve. This paper considers the traffic engineering problem in data center networks by studying the joint problem of finding spanning trees for VLANs and optimally selecting the most promising spanning trees to map the traffic flows onto. We mathematically model this problem using Integer Linear Program (ILP) techniques and follow a primal-dual decomposition approach, using column generation, to solve exactly a relaxed mapping version of the problem, as well we present approximate solutions to the original problem. We show through numerical evaluations an outstanding scalability of the decomposed version of the problem and we use our results to study the performance of traffic engineering protocols developed in recent literature for data center networks. NPRP 5-137-2-045 grant from the Qatar National Research Fund (a member of the Qatar Foundation). Scopus

International audience; This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages. We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose a design of 100\% single segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100\% single segment protection. For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost.