There is strong interest in leveraging reinforcement learning (RL) for information retrieval (IR) applications including search, recommendation, and advertising. Just in 2020, the term "reinforcement learning" was mentioned in more than 60 different papers published by ACM SIGIR. It has also been reported that Internet companies like Google and Alibaba have started to gain competitive advantages from their RL-based search and recommendation engines. This full-day tutorial gives IR researchers and practitioners who have no or little experience with RL the opportunity to learn about the fundamentals of modern RL in a practical hands-on setting. Furthermore, some representative applications of RL in IR systems will be introduced and discussed. By attending this tutorial, the participants will acquire a good knowledge of modern RL concepts and standard algorithms such as REINFORCE and DQN. This knowledge will help them better understand some of the latest IR publications involving RL, as well as prepare them to tackle their own practical IR problems using RL techniques and tools. Please refer to the tutorial website (https://rl-starterpack.github.io/) for more information.

Pipelined ASIC architectures are increasingly being used in forwarding engines for high-speed IP routers. We explore optimization issues in the design of memory-efficient data structures that support fast incremental updates in such forwarding engines. Our solution aims to balance the memory utilization across the multiple pipeline stages. We also propose a series of optimizations that minimize the disruption to the forwarding process caused by route updates. These optimizations reduce the update overheads by over a factor of two for a variety of different core routing tables and update traces.

We present two centralized algorithms that dynamically deform the topology of a multi-hop wireless network in response to changing traffic conditions, so as to reduce the end-to-end packet delay. These algorithms operate by reducing an easily calculable traffic-and-topology-dependent metric that has strong positive correlation to the mean end-to-end network delay. This makes it possible to change the network topology in real time. The first algorithm involves moving existing nodes to create new links, while the second involves adding a new node to the existing network. The new links are added judiciously between nodes with the most traffic fluctuations, in a way that often decreases the total number of network links. Multiple simulations on the original and the deformed networks using the \ns simulator demonstrate that the reductions in end-to-end delay are significantly higher than with the alternative approach of increasing the capacities of the most congested links.

Pipelined ASIC architectures are increasingly being used in forwarding engines for high speed IP routers. We explore optimization issues in the design of memory-efficient data structures that support fast incremental updates in such forwarding engines. Our solution aims to balance the memory utilization across the multiple pipeline stages. We also propose a series of optimizations that minimize the disruption to the forwarding process caused by route updates. These optimizations reduce the update overheads by a factor of 2-5 for a variety of different core routing tables and update traces.

Ternary content-addressable memories (TCAMs) are becoming very popular for designing high-throughput forwarding engines on routers: they are fast, cost-effective and simple to manage. However, a major drawback of TCAMs is their high power consumption. This paper presents architectures and algorithms for making TCAM-based routing tables more power efficient. The proposed architectures and algorithms are simple to implement, use commodity TCAMs, and provide worst-case power consumption guarantees (independent of routing table contents).

We present a routing paradigm called PBR that utilizes steepest gradient search methods to route data packets. More specifically, the PBR paradigm assigns scalar potentials to network elements and forwards packets in the direction of maximum positive force. We show that the family of PBR schemes are loop free and that the standard shortest path routing algorithms are a special case of the PBR paradigm. We then show how to design a potential function that accounts for traffic conditions at a node. The resulting routing algorithm routes around congested areas while preserving the key desirable properties of IP routing mechanisms including hop-by-hop routing, local route computations and statistical multiplexing. Our simulations using the ns simulator indicate that the traffic aware routing algorithm shows significant improvements in end-to-end delay and jitter when compared to standard shortest path routing algorithms. The simulations also indicate that our algorithm does not incur too much control overheads and is fairly stable even when traffic conditions are dynamic.

We study the route oscillation problem [16, 19] in the Internal Border Gateway Protocol (I-BGP)[18] when route reflection is used. We propose a formal model of I-BGP and use it to show that even deciding whether an I-BGP configuration with route reflection can converge is an NP-Complete problem. We then propose a modification to I-BGP and show that route reflection cannot cause the modified protocol to diverge. Moreover, we show that the modified protocol converges to the same stable routing configuration regardless of the order in which messages are sent or received.

We study the stability of the OSPF protocol under steady state and perturbed conditions. We look at three indicators of stability, namely, (a) network convergence times, (b) routing load on processors, and (c) the number of route flaps. We study these statistics under three different scenarios: (a) on networks that deploy OSPF with TE extensions, (b) on networks that use subsecond HELLO timers, and (c) on networks that use alternative strategies for refreshing link-state information. Our results are based on a very detailed simulation of a real ISP network with 292 nodes and 765 links.

For the last decade, QoS support for the Internet has focused on real-time applications such as audio and video. However, today's Internet is dominated by elastic traffic flows (such as Web traffic) that are more tolerant of delay and jitter. Such traffic flows tend to be short-lived and the end-to-end reservation approach for resource allocation does not work well for them. Some form of flow aggregation is required to do resource allocation in a scalable manner. In this paper, we present user-share differentiation (USD), an architecture for providing long-term, scalable, resource allocation for elastic traffic. The USD scheme has the advantages of per-customer traffic isolation, flexible service models, and scalability. We also summarize simulation results (presented in Basu et al. (1998), in detail) that show the effectiveness of the USD scheme.

The challenge is to develop an easily usable protocol development framework that combines the flexibility of layered implementations, the efficiency of tightly-coupled monolithic implementations and the correctness achievable using high-level protocol validation languages. This challenge is addressed by a language-based framework that introduces a new protocol specification language called Promela++. The framework consists of a protocol verification tool and an optimizing compiler that generates efficient protocol code from Promela++ specifications. Promela++ is based on the Promela protocol validation language and has been designed with a rich set of domain-specific constructs. These constructs facilitate the task of protocol specification as well as enable the Promela++ compiler to perform domain-specific optimizations. The Promela++ compiler can also automatically transform protocol specifications in Promela++ to protocol models in Promela. The article presents a new language that unites the twin goals of checking protocol correctness using model checkers, and efficient protocol construction using optimizing compilers, under a single framework; exploits language design to provide mechanisms that simultaneously ease programming and enable generation of efficient protocol code; and demonstrates the effectiveness of this approach by doing a complete evaluation of multiple protocol implementations in Promela++.

Fast Ethernet and ATM are two attractive network technologies for interconnecting workstation clusters for parallel and distributed computing. This paper compares network interfaces with and without programmable co-processors for the two types of networks using the U-Net communication architecture to provide low-latency and high-bandwidth communication. U-Net provides protected, user-level access to the network interface and offers application-level round-trip latencies as low as 60 /spl mu/sec over Fast Ethernet and 90 /spl mu/sec over ATM. The design of the network interface and the underlying network fabric have a large bearing on the U-Net design and performance. Network interfaces with programmable co-processors can transfer data directly to and from user space while others require aid from the operating system kernel. The paper provides detailed performance analysis of U-Net for Fast Ethernet and ATM, including application-level performance on a set of Split-C parallel benchmarks. These results show that high-performance computing is possible on a network of PCs connected via Fast Ethernet.

The U-Net communication architecture provides processes with a virtual view of a network interface to enable userlevel access to high-speed communication devices. The architecture, implemented on standard workstations using offthe-shelf ATM communication hardware, removes the kernel from the communication path, while still providing full protection. The model presented by U-Net allows for the construction of protocols at user level whose performance is only limited by the capabilities of network. The architecture is extremely flexible in the sense that traditional protocols like TCP and UDP, as well as novel abstractions like Active Messages can be implemented efficiently. A U-Net prototype on an 8node ATM cluster of standard workstations offers 65 microseconds round-trip latency and 15 Mbytes/sec bandwidth. It achieves TCP performance at maximum network bandwidth and demonstrates performance equivalent to Meiko CS-2 and TMC CM-5 supercomputers on a set of Split-C benchmarks.