The rapid growth of online shopping stores, such as Amazon, has led to services reaching billions of people worldwide. With global retail sales exceeding $6 trillion in 2024, customer expectations for personalized and seamless shopping experiences have heightened. Traditional online shopping experiences, such as search and navigation systems, often fall short in addressing complex shopping journeys. Conversational shopping (such as Amazon Rufus) offers a transformative approach by enabling dynamic, multi-turn dialogues that closely resemble human interactions. This allows customers to explore product options, seek clarifications, and receive personalized recommendations, thereby enhancing product discovery and informed decision-making. In this paper, we share our year-long journey of using language models for conversational shopping at Amazon and introduce how we use LLM fine-tuning techniques to enhance LLMs for a conversational shopping experience like Amazon Rufus. We also introduce innovative strategies for training data collection and demonstrate real-world applications, including product recommendations, clarification mechanisms, and internationalization for global customers.

International audience

During the planning of communication networks, the routing decision process (distributed and online) often remains decoupled from the network design process, that is, resource installation and allocation‐planning process (centralized and offline). To reconcile both processes and take into account demand variability, we generalize the capacitated multicommodity fixed charge network design class of problems by including different types of fixed costs (installation and maintenance costs) and variable costs (routing costs) but also variable traffic demands over multiple periods. However, conventional integer programming methods can typically solve only small to medium size instances of this problem. Two major difficulties are encountered when using commercial solvers to solve the associated mixed integer programs: (i) problems are large scale and even solving the linear relaxation of the problem can be challenging; and (ii) the solver hardly find good feasible solutions for medium to large scale instances. As an alternative, we propose a Lagrangian approach for computing a lower bound by relaxing the flow conservation constraints such that the Lagrangian subproblem itself decomposes by node. Though this approach yields one subproblem per network node, solving the Lagrangian dual by means of the bundle method remains a complex computational tasks. However, it always provides a lower bound on the optimal solution. Moreover, based on this relaxation, we propose a Lagrangian heuristic that makes the approach more robust than a black‐box usage of a Mixed Integer Programming (MIP) solver. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 110–123 2017

Resource abstraction aims at enabling flexible allocation of capacity to serve demands by aggregating physical resources taken out of distributed resource pools accessible via dedicated gateways. This paradigm sits at the heart of many networking models including resource virtualization and other cloud computing. In this paper, we show this generic problem can be modeled by combining and extending the Hub Location with the Location Routing Problem, referred to as the Hub-Location Routing Problem (HLRP). A mixed- integer program for the HLRP is proposed and evaluated using representative settings. We compare the results with those obtained when modeling the initial problem as an Location Routing Problem only; hence, obtain a quantitative assessment of the performance tradeoffs between resource abstraction, (al)location and routing.

This document provides a detailed description of the tutorial lecture on Challenges in Network Optimization provided at the 2016 IEEE 17th International Conference on High Performance Switching and Routing (HPSR). This lecture is motivated by the recent evolutions of communication networks which have induced new challenges in mixed-integer network optimization ranging from problem formulation to computational methods. Indeed, paradigms such as information-oriented networks, resource abstraction (at the heart of virtualization and other cloudification), and programmability of network functions lead to combine well-established optimization problems with network optimization problems (network design, resource placement/allocation and other multi-commodity flow problems). Beyond dimensioning, provisioning/configuring and scheduling/ planning, the combination of conventional network optimization problems with the facility-location or the hub-location problem for instance, provides guidelines for the design of unified processes that address these evolutions. In this tutorial, we exploit mixed-integer programming as a tool for driving early design decisions (thus, not only for the traditional application of network optimization) together with associated requirements such as congestion awareness but also reliability by extending the combined problems to their reliable variant. We compare how the selection of the appropriate routing strategies may also be determined by means of this approach. Finally, in order to cope with demand uncertainty, we extend these formulations to their set-induced robust counterpart. Indeed, robust optimization enables to accommodate spatio-temporal variations in demands and associated traffic for instance without compromising on the solution quality. We conclude this lecture by outlining some of the main research challenges in network optimization at both modeling and computational level.

This document provides a detailed description and motivation together with the structure of the tutorial lecture on Advances in Dynamic Routing Models and Algorithms for Large-Scale Graphs provided at the 2015 IEEE 16th International Conference on High Performance Switching and Routing (HPSR). After motivating the importance of this multi-disciplinary research topic blending algorithm graph theory, distributed computing as well as performance analysis and modeling, this paper provides a detailed structure of the tutorial lecture. We conclude this paper by the challenges resulting from new application domains in routing, in particular, for so-called information-centric networks and position the new paradigms presented in the second part of this lecture, namely, the overlay model (content-distribution networks) and named-based routing model.

In communication networks, the routing decision process (distributed and online) remains decoupled from the network design process, i.e., resource installation and allocation planning process (centralized and offline). To reconcile both processes, we ambition to design a distributed optimization technique aware of distributed nature of the routing process by decomposing the optimization problem along same dimensions as (distributed) routing decision process. For this purpose, we generalize the capacitated multi-commodity capacitated fixed charge network design (MCND) class of problems by including different types of fixed costs (installation and maintenance costs) and variable costs (routing costs) but also variable traffic demands over multiple periods. However, conventional integer programming methods can typically solve only small to medium size instances. As an alternative, we propose a Lagrangian approach for computing a lower bound by relaxing the flow conservation constraints such that the Lagrangian subproblem itself decomposes by node. Though this approach yields one subproblem per network node, solving the Lagrangian dual by means of the bundle method remains a complex computational tasks. However, the approach is more robust than any LP solvers and it always returns some solutions. Instead, we proved that CPLEX, which uses the Dual Simplex algorithm, is not able to provide a solution for large instances.

The capacitated fixed‐charge network design (FCND) problem considers the simultaneous optimization of capacity installation and routing of traffic where a fixed cost is paid for opening a link and a linear routing cost is paid for sending traffic flow(s) on that link. The routing decisions must be performed such that the traffic flows remain bounded by the installed link capacities. The FCND problem appears as a particular case of the combined multiperiod network design and traffic flow routing problem with time‐dependent demands formulated in this article as a mixed integer linear program (MILP). A compact formulation based on the aggregation of traffic flows per destination and an extended formulation, where flows are decomposed by origin‐destination pairs while keeping the requirement of destination‐based routing, have been proposed in D. Papadimitriou and B. Fortz, IEEE International Conference on Communications (2014), pp.1124–1130 and IEEE Global Communications Conference (2014), pp.1303–1309, respectively. In this article, we propose to resolve this computationally challenging problem by means of the rolling horizon heuristic with the objective to decrease the computational time while degrading as less as possible the quality of the solution. The resulting improvements enable to progressively overcome the computational limits encountered when solving such problem, in particular, when the network size and number of periods increase. The improvements provided by the rolling horizon heuristic can be further exploited by extending the proposed model to account for different patterns of failures that may affect installed arcs over time. For this purpose, our generalized MILP formulation comprises a time‐variable link maintenance cost function. We further analyze the quality of the results for the proposed formulation with different link maintenance cost functions with the objective to derive the best arc replacement strategy. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 364–379 2015

The combined network design and (distributed) traffic routing problem can be formulated as a large-scale multi-period mixed integer optimization problem. This problem combines network design decisions and routing decisions, with time-dependent traffic demands. In this paper, we consider different branch-and-cut strategies for solving the problem with the base and extended formulations proposed in our prior work.

The combined network design and (distributed) traffic routing problem can be formulated as a large-scale multi-period mixed integer optimization problem. This problem combines network design decisions and routing decisions, with time-dependent demands. In [1], we proposed a compact formulation based on the aggregation of flows by destination. We observed that its resolution on realistic instances becomes intractable and unscalable with state-of-the-art solvers due to the weak linear programming bound that this formulation provides. In this paper, we consider an extended formulation where flows are decomposed by origin-destination pairs, while keeping the requirement of destination-based routing. The quality of the extended formulation and the computational time needed to solve it are evaluated on a representative set of network topologies and traffic demands, and compared to results obtained with the base formulation of [1]. The extended formulation can then be considered for more efficient resolution methods involving decomposition and cutting planes approaches.

In today's communication networks, distributed control functions such as routing inherit their design driven by processing capacity and memory consumption. Henceforth, the routing protocol decision process (distributed and online) remains still decoupled from the routing optimization process (centralized and offline). Distributed optimization does not take into account the distributed nature of the online routing decision making process because distributed optimization is not decomposed along the same dimensions as the routing decision making process. The challenge becomes thus how to modify the routing decision process to include optimization objectives and how to make the optimization problem aware of the distributed nature of the online routing decision process under dynamic conditions. As a first evolution in that direction, we propose a new combined optimization model that integrates network design decisions and routing decisions, with time-dependent demands. As part of our main contribution, the proposed model keeps in sight the need for a distributed routing function, through the use of scalable routing tables. We also put our work in the perspective of a fully distributed, decomposed optimization setting.

Information-centric networking has been proposed to achieve efficient and reliable distribution of content. We propose a model to assign content locators to content names. Information routing decision is made based on geometric routing using the assigned locators. We consider a geometric routing scheme known as geodesic geometric routing. We demonstrate on the iLab.t virtual wall the successful operation of the proposed scheme and the gain of using content locators on capacity utilization by means of caching.

Compact routing schemes address the fundamental tradeoff between the memory space required to store the routing table entries and the length of the routing paths that these schemes produce. This paper introduces the first known nameindependent, leaf-initiated dynamic compact routing scheme that allows the distribution of traffic from any source to any set of leaf nodes along a multicast routing path that defines a distribution tree. By means of the proposed scheme, a multicast distribution tree dynamically evolves according to the arrival of leaf-initiated join/leave requests. To evaluate the performance we consider the following metrics: the stretch of the produced routing paths, the size and the number of routing table entries, and the communication cost. The results obtained by simulation on synthetic power law graphs (modeling the Internet topology) show that our scheme can successfully handle leaf-initiated dynamic setup of multicast distribution trees. Two reference multicast routing schemes (the Shortest Path Tree and the Steiner Tree algorithm) are used to compare the performance of the proposed scheme. While increasing the communication cost compared to the Shortest Path Tree, the proposed scheme achieves considerable reduction of the routing table size compared to both reference schemes. Moreover, the stretch of the resulting multicast routing paths show limited deterioration compared to the minimum value obtained with Steiner Trees.

We demonstrate machine learning augmented Open Shortest Path First (OSPF) routing which infers Shared Risk Groups (SRG) from link failure history. For an initial link failure matching an SRG, it predicts subsequent link state advertisements corresponding with that SRG, improving convergence and recovery times during multiple network failures.

A large number of intelligent components for managing the Future Internet have been proposed recently or are currently being investigated. However, before these network components can be deployed in real-life networks, they need to be thoroughly validated through realistic and large scale experiments. Testbed facilities provide a means to set up large scale network topologies but offer only a limited functionality in managing the deployment of the experiment itself. In this paper, we propose a management framework which automates the configuration and management of network experiments. The framework focuses on the emulation of user behaviour, to obtain realistic network conditions, and features several mechanisms that allow to reduce the experiments' size both temporally (in shorter simulation time) as spatially (with fewer physical nodes).

This paper investigates routing algorithms that compute paths along which combined unicast and multicast traffic can be forwarded altogether, i.e., over the same path. For this purpose, the concept of AnyTraffic group is introduced that defines a set of nodes capable to process both unicast and multicast traffic received from the same (AnyTraffic) tree. The resulting scheme is referred to as AnyTraffic routing. This paper defines a heuristic algorithm to accommodate the AnyTraffic group and to find the proper set of branch nodes of the tree. The algorithm supports dynamic changes of the leaf node set during multicast session lifetime by adapting the corresponding tree upon deterioration threshold detection. Studies are performed for both static and dynamic traffic scenarios to i) determine the dependencies of the algorithm (node degree, clustering coefficient and group size); and ii) evaluate its performance under dynamic conditions. Initial results show that the AnyTraffic algorithm can successfully handle dynamic requests while achieving considerable reduction of forwarding state consumption with small increase in bandwidth utilization compared to the Steiner Tree algorithm.

In this paper, we use machine learning technique at the routers to study the link state protocol data to predict the existence of shared risk link groups (SRLG) in the network. In particular, we use the correlation between different link state updates (LSUs) issued by different network nodes (routers) upon failure. The concerned network router then runs a novel Bayesian network based statistical learning process to learn about the possible existence of SRLGs. The decision of this online learning is transferred to the routing information base (RIB) so that it can accordingly modify the routing table for the entire SRLG upon failure detection of one of the candidate node of that particular SRLG and hence reduce the protection switching time.

The high capacity provided by packet-switched networks is supporting the proliferation of bandwidth intensive multimedia applications which require multicasting capability. As a consequence on today's networks, unicast and multicast traffic compete for shared resources where a router must maintain both unicast and multicast forwarding states. Pursuing a forwarding state reduction, in this paper we introduce the novel concept of Any Traffic data group which consists of a group of nodes receiving both unicast and multicast traffic over the same single minimum-cost network entity. A novel heuristic algorithm is specifically defined to accommodate such data group and has been compared with the standard shortest path (SP) algorithm - the optimal case for unicast routing - and a classical Sterner tree (ST) heuristic algorithm - the optimal case for multicast routing. Exhaustive experiments have been performed to validate the proposed algorithm.

Ethernet is becoming the dominant aggregation technology for carrier transport networks; however, as it is a LAN technology, native bridged ethernet does not fulfill all the carrier requirements. One of the schemes proposed by the research community to make ethernet fulfill carrier requirements is ethernet VLAN-label switching (ELS). ELS allows the creation of label switched data paths using a 12-bit label encoded in the VLAN TAG control information field. Previous label switching technologies such as MPLS use more bits for encoding the label. Hence, they do not suffer from label sparsity issues as ELS might. This paper studies the sparsity issues resulting from the reduced ELS VLAN-label space and proposes the use of the label merging technique to improve label space usage. Experimental results show that label merging considerably improves label space usage.

Generalized Multi-Protocol Label Switching (GMPLS) has become the protocol suite of choice for unified control plane implementation. However, its adoption is facing major challenges in terms of feasibility, performance, and gain when migrating from legacy packet over optical multi-layer networks driven by overlaid control planes. The ITEA TBONES project aims at tackling both objectives through the development of a platform including all the elements constituting such networks: network dimensioning, management plane and GMPLS control plane. This paper details the control plane architecture of the TBONES software platform, including its realization and applicability for multi-area networks, as well as the Testbed. Several experiments are described, both for validation and for demonstration of its capabilities and future usage.

In future multilayer packet circuit networks, the traffic engineering (TE) apparatus is foreseen as a fundamental (logically independent) toolset, which carries out TE tasks, taking into account the operators operational considerations and fulfilling their TE constraints. The TE toolset relies on the generalized multi-protocol label switching (GMPLS) suite of protocols; its description is provided in terms of its functional scope and properties. Next a new TE element (TeE) is proposed that complements the existing TE toolset and its delivered features. Finally, this paper analyzes and compares the architectural and implementation options for the TeE logical entity

Automatically switched circuit establishment is a big step for the operators towards the automation of transport services. The aim is to reduce OPEX while improving service capabilities through a distributed generalized multi-protocol label switching (GMPLS) control plane. Nevertheless, the control plane may not operate on its own and, hence, network operators need a holistic service production platform where intensified traffic engineering (TE) capabilities exist when operating the control plane. The aim of this paper is to point out and discuss issues to be addressed and to provide guiding principles as well as a policy-based management (PBM) solution pertaining to enhanced TE related to the GMPLS control plane protocols and the corresponding network management issues.