Yoann Desmouceaux

Juan Antonio

Cordero Fuertes

Thomas Heide Clausen

Reliable BIER with Peer Caching

Keywords: Multicast, Reliable multicast, Bit-Indexed Explicit Replication (BIER), Segment Routing (SR), Policies, Performance evaluation

BIER (Bit-Indexed Explicit Replication) alleviates the operational complexities of multicast protocols (associated to the multicast tree and the incurred state in intermediate routers), by allowing for source-driven, per-packet destination selection, efficient encoding thereof in packet headers, and stateless forwarding along shortest-path multicast trees. BIER perpacket destination selection enables efficient reliable multicast delivery: packets not received by a subset of intended destinations can be efficiently BIER-retransmitted to only that subset. While BIER-based reliable multicast exhibits attractive performance attributes, relying on source retransmissions for packet recovery may be costly -even unnecessary, if topologically close peers are able to provide a copy of the packet.

Thus, this paper extends the use of reliable BIER multicast to allow recovery also from peers, using Segment Routing (SR) to steer retransmission requests through a set of potential (local) candidates, before requesting retransmissions from the source as a last resort only. A general framework is introduced, which can accommodate different policies for the selection of candidate peers for retransmissions. Simple (both static and adaptive) policies are introduced and analyzed, both (i) theoretically and (ii) by way of simulations in data-center-like and real-world topologies. Results indicate that local peer recovery is able to substantially reduce the overall retransmission traffic, and that this can be achieved through simple policies, where no signalling is required to build a set of candidate peers.

I. INTRODUCTION

As the size and complexity of Data-Center Networks (DCNs) [START_REF] Bilal | Quantitative comparisons of the state-of-the-art data center architectures[END_REF] and Content Distribution Networks (CDNs) [START_REF] Pathan | A taxonomy of cdns[END_REF] grow, efficient multicast distribution of content becomes increasingly desirable [START_REF] Kim | Efficient multicast schemes using in-network caching for optimal content delivery[END_REF], [START_REF] Ni | Large-scale cooperative caching and applicationlevel multicast in multimedia content delivery networks[END_REF], [START_REF] Li | Reliable multicast in data center networks[END_REF]. Multicast protocols were never widely deployed in the Internet, due to their intrinsic complexity and their requiring state in intermediate routers [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF]. Protocols such as PIM (Protocol Independent Multicast) [START_REF] Nicholas | Protocol Independent Multicast -Dense Mode (PIM-DM): Protocol Specification (Revised)[END_REF], which operate by clients "subscribing" to multicast traffic flows by sending join messages, offer a best-effort data delivery service. Several protocols have been proposed, which offer different data delivery services -notably, reliability. NORM (Negative-acknowledgement-Oriented Reliable Multicast) [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF], among others, uses sequence numbers in data packets to detect packet losses, and negative acknowledgements (NACKs) which trigger a multicast transmission of the missing packet to the multicast group. Other protocols [START_REF] Li | Reliable multicast in data center networks[END_REF], [START_REF] Paul | Reliable multicast transport protocol (rmtp)[END_REF] use unicast retransmissions to those destinations having missed a packet.

Bit-Indexed Explicit Replication (BIER) [START_REF] Wijnands | Multicast Using Bit Index Explicit Replication (BIER)[END_REF] is a multicast protocol that removes the need for flow-state in intermediate

The authors are with École Polytechnique, 91128 Palaiseau, France, emails: {yoann.desmouceaux, juan-antonio.cordero-fuertes, thomas.clausen}@polytechnique.edu. Y. Desmouceaux is also with Cisco Systems Paris Innovation and Research Laboratory (PIRL), 92782 Issy-les-Moulineaux, France, email: ydesmouc@cisco.com. routers. Intermediate routers replicate and forward packets over the interfaces providing shortest paths (according to unicast routes) to the specified destinations, as illustrated in figure 1. BIER-based reliable multicast [START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF] enables the source to detect and efficiently retransmit (with BIER), missing packets to their requesting destinations.

"Local recovery" may, if available, be preferable to retransmissions from the source, and numerous reliable multicast protocols have proposed such an approach [START_REF] Li | Reliable multicast in data center networks[END_REF], [START_REF] Yavatkar | A reliable dissemination protocol for interactive collaborative applications[END_REF], [START_REF] Levine | Improving internet multicast with routing labels[END_REF]. This has benefits in terms of Quality-of-Experience (e.g., when the source and the destination having lost a packet experience a substantial round-trip delay), or when there are links towards the source whose usage should be limited (e.g., so as to not overload the source, or for traffic engineering or economic reasons). Several usage scenarios can be listed, in which it is interesting to provide local recovery rather than source-based retransmissions:

• live [START_REF] Rückert | Software-defined multicast for over-the-top and overlay-based live streaming in isp networks[END_REF], [START_REF] Rückert | Flexible, efficient, and scalable software-defined over-the-top multicast for isp environments with dynsdm[END_REF] or linear [START_REF] Choi | A survey of user behavior in vod service and bandwidth-saving multicast streaming schemes[END_REF] multicast video delivery, for which it is crucial to provide low-latency services to the end users, and where retransmissions from sources behind costly (for instance, transcontinental) links can be detrimental to the packet reception delay;

• multicast pre-placement of content in CDNs [START_REF] Kim | Efficient multicast schemes using in-network caching for optimal content delivery[END_REF], [START_REF] Ni | Large-scale cooperative caching and applicationlevel multicast in multimedia content delivery networks[END_REF], [START_REF] Seyyedi | Hybrid cdn-p2p architectures for live video streaming: Comparative study of connected and unconnected meshes[END_REF], for which it can be costly (in terms of link usage, and in terms of global transmission speed) to rely on remotely-located sources to perform retransmissions;

• pushing of software updates to multiple machines in datacenter networks [START_REF] James | Fast content distribution on datacenter networks[END_REF] (or more generally, of arbitrary files to distributed storage systems relying on replication [START_REF] Weil | Ceph: A scalable, high-performance distributed file system[END_REF]) from exterior sources, for the same reasons as above -and especially because data centers feature sub-millisecond machineto-machine latencies, making them interesting candidates for local retransmissions.

Therefore, a desirable reliable multicast protocol would be able to minimize the amount of state in the routers and retransmission traffic, while allowing for locally-emitted retransmissions. With "standard" multicast retransmissions [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF], the source re-floods the whole tree as a result (a). With BIER retransmissions [START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF], the source re-floods only the subset of failing destinations (b). With peer-based BIER retransmissions introduced in this paper, the NACKs are sent to a peer that had cached the packet, which then floods the failing destinations, spanning a smaller tree (c).

A. Statement of Purpose

The purpose of this paper is to extend reliable BIER [START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF] to allow a destination, having lost a multicast packet, to request local retransmission thereof from local peers (i.e., which are topologically close, and part of the destination set for the multicast flow) which may have successfully received a copy thereof -before requesting a retransmission from the source. This is achieved by (i) each destination caching successfully received packets for a small amount of time, and (ii) destinations detecting a packet loss sending a NACK through an ordered set of peers (that might offer a retransmission) followed by the source, by way of Segment Routing (SR) [START_REF] Filsfils | The segment routing architecture[END_REF].

The advantages of this approach are threefold: (i) the use of peer-based recovery reduces the number of retransmissions from the source, (ii) the use of SR allows a destination to generate a single NACK for a lost packet, which ultimately and automatically will be forwarded to the source if no local retransmissions are possible, and (iii) BIER-based retransmissions (from the source or from any peer) reduce the overall traffic by avoiding both unnecessary duplicate unicast retransmissions across a link close to the source, and multicast floods across the entire multicast tree.

B. Related Work

Different approaches to reliable multicast exist, most of which are not based on BIER, and will be reviewed in section I-B1. The proposal in this paper is built on edgecaching and cooperative content management -which has some notions in common with Information Centric Networking (ICN), discussed in section I-B2. BIER, and reliable BIER, as well as Segment Routing, will be explored in further details in section I-B3 and in section I-B4.

1) Reliable Multicast: Reliable multicast protocols assume the existence of a multicast tree (e.g., built using PIM, or similar), to which are added (i) detection, (ii) reporting, and (iii) loss recovery via packet retransmission. Depending on the notion of reliability, the mechanisms differ on the intended set of receivers, on transmission requirements, and on available trade-offs for each purpose [START_REF] Atwood | A classification of reliable multicast protocols[END_REF]. Since strict reliability is hard to achieve and does not scale, a weaker notion of semireliability, associated to time-limited efforts (retransmissions, NACKs) before dropping a packet, is sometimes used in multicast systems with large number of destinations.

Loss estimation and recovery can be handled exclusively at the source, as in XTP [START_REF] Strayer | XTP: the Xpress Transfer Protocol[END_REF], or through receiver detection and source retransmission, as in RMP [START_REF] Whetten | A high performance totally ordered multicast protocol[END_REF], SRM [START_REF] Floyd | A reliable multicast framework for light-weight sessions and application level framing[END_REF] or NORM [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF], [START_REF] Bormann | NACK-Oriented Reliable Multicast (NORM) Transport Protocol[END_REF]. Local recovery has been explored by several approaches, either from designated intermediate devices, as in PGM [START_REF] Gemmell | The pgm reliable multicast protocol[END_REF], from designated receives, as in RMTP [START_REF] Paul | Reliable multicast transport protocol (rmtp)[END_REF], or from a backup overlay of destinations, as in RDCM [START_REF] Li | Reliable multicast in data center networks[END_REF].

2) Information-Centric Networking (ICN): ICN [START_REF] Jacobson | Networking named content[END_REF] is a paradigm where content is stored as named data packets, and where users send interest packets requesting named data packets. As data packets are only identified by names, caching by intermediate routers is possible, and a packet needs only be delivered once per interface, corresponding to a previouslyemitted interest. ICN thus shares properties with reliable multicast protocols, by enabling recovery of data from nearby routers.

What is proposed in this paper differs from ICN in that it (i) assumes push-based multicast applications and (ii) does not rely on routers performing caching, by offloading this task exclusively to the set of destinations -i.e., requires no extensive modifications to routers nor to applications.

3) Bit-Indexed Explicit Replication (BIER): BIER [START_REF] Wijnands | Multicast Using Bit Index Explicit Replication (BIER)[END_REF] is a multicast protocol allowing for delivery of a packet to a group, with each destination explicitly indicated by the source. Each possible destination is assigned an index; a bitstring, where the i-th bit is set if and only if the i-th possible destination is intended to receive the packet, is included in each packed header.

On receiving a packet, a BIER router maps intended destinations to IP addresses, consults its routing table to identify over which interfaces the packet should be forwarded to reach the destinations indicated in the bitstring, and makes one replica of the packet for each of these interfaces. Finally, just before transmitting the (replica of the) packet over an interface, the included bitstring is updated, leaving only those bits corresponding to destinations reachable via this interface, set (figure 1). No per-source or per-flow state is required in any router -only a (standard unicast) routing table and the static mapping between bit index numbers and IP addresses must be present.

BIER can be used to provide reliable BIER, a reliable multicast service with per-packet (rather than per-flow) granularity [START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF]. Schematically, when a destination detects a packet to be lost, it sends a NACK towards the source -which collects NACKs for this packet for a small amount of time, recording the destinations requesting retransmission. When that time expires, it uses BIER to send the retransmission to exactly the set of destinations which sent a NACK (figure 2c). This both avoids flooding the whole original multicast tree (figure 2a), and prevents duplicate retransmissions over the same link (as would be the case, for unicast retransmissions to each destination, figure 2b).

4) Segment Routing (SR): SR [START_REF] Filsfils | The segment routing architecture[END_REF] is an architecture allowing packets to traverse a source-specified, explicit, ordered set of interconnections (called "segments"), before reaching their final destination. A segment can be associated with different functions, from the simple (forwarding a packet to the next segment) to arbitrarily complex (e.g., handing over a packet to a Virtual Network Function for processing). In IPv6 Segment Routing [START_REF] Filsfils | SRv6 Network Programming[END_REF], segments are identified by IPv6 addresses, and carried in an IPv6 Extension Header [START_REF] Previdi | IPv6 Segment Routing Header (SRH)[END_REF]. After a segment is processed, the processing router will replace the current IP destination address of the packet with the available next segment -and forward it using regular unicast IP forwarding. This enables transparent delivery of segment routed packets across non-SR-capable routers.

C. Paper Outline

The remainder of this paper is organized as follows. Section II gives a birds-eye view of the proposed extension to reliable BIER, and section III a detailed specification of how BIER is used to construct a reliable multicast framework which can accommodate diverse policies for selecting peers for local retransmissions. Section IV introduces basic taxonomy and example peer selection policies. Section V provides a theoretical analysis and discussion of performance and cost trade-offs for each of these policies, which are experimentally evaluated by way of network simulations in sections VI-VIII: section VI introduces the characteristics of the simulation environment, and sections VII and VIII describe and discuss the main performance results over both a data center topology and a real ISP topology. Finally, section IX concludes this paper.

II. OVERVIEW: RELIABLE BIER WITH PEER CACHING

In this paper, the reliable BIER mechanism introduced in [START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF] is extended to support recovery from peers. Rather than sending a NACK directly to the source to request retransmission of a lost packet, this paper proposes that a NACK be first sent through an ordered set of peer(s), each of which might be able to provide a retransmission if they have a cached copy of the lost packet (figure 2d). Retransmission from the source is solicited as a "last resort". As with reliable BIER, peers can, of course, aggregate NACKs, before performing a BIER-based retransmission. This locality in retransmissions is expected to reduce delays, as well as to reduce the load on the source, and on its egress links [START_REF] Levine | Improving internet multicast with routing labels[END_REF], [START_REF] Atwood | A classification of reliable multicast protocols[END_REF].

A. Segment Routing Recovery

Requesting retransmission from an ordered list of peers, followed by the source, is done by sending a NACK using Segment Routing (an "SR-NACK"). Each segment will trigger an action which is: (i) if the peer is unable to perform the retransmission, forward the packet to the next segment; (ii) if the peer is able to perform the retransmission, stop forwarding the segment and perform a BIER retransmission (figure 2d). This is illustrated in figure 3: in (a) an SR-NACK is received by a peer, which is able to satisfy the retransmission; in (b) an SR-NACK is received by a peer, which is not able to satisfy the retransmission request, and where the next segment is another peer -which, then, is able to satisfy the retransmission request; in (c) neither of the two peers receiving the SR-NACK is able to satisfy the retransmission request, and the SR-NACK is therefore forwarded to the source of the multicast packet.

The combined approach thus consists of the source performing an initial BIER transmission of a multicast packet. Destinations receiving the packet may (in addition to processing it) cache it for a short amount of time for possible peerretransmission. A destination detecting a packet loss (e.g., by receiving a subsequent packet belonging to the same multicast flow) will construct an SR-NACK, containing a number of peers followed by the source. A peer receiving an SR-NACK for which it is able to offer a retransmission will behave as if it was the source in reliable BIER: collect NACKs for this packet for a small amount of time, record the destinations requesting retransmission, and use BIER for retransmitting the packet to exactly the set of destinations from which an SR-NACK was received, when the timer expires.

B. Peer Caching with Peerstrings

This recovery mechanism is, of course, agnostic to the manner in which the set of candidate peers is chosen. If the network operator has instrumented the network in such a way that some peers are "better" candidates for retransmissions (e.g., they are more likely to have cached packets, they are behind less costly or less lossy links, etc.), destinations can be administratively configured to send NACKs to those -with the drawback of requiring instrumentation and configuration. Thus, this paper introduces a modification to the BIER forwarding plane, allowing destinations to learn about candidate peers.

To this end, an additional bitstring is introduced in BIER headers, henceforth denoted a peerstring. This peerstring is set so as to allow a destination, detecting a packet loss, to identify potential peers from which a retransmission can be requested. A-minima, the peerstring is empty, which defaults to requesting retransmission from the source, as in reliable BIER. A-maxima, the peerstring contains all destinations (i.e., is a copy of the bitstring as inserted by the source) -and any peerstring in between these two extremes is valid.

With the goal of encouraging locality in retransmissions, one simple policy is that, for a given destination, the peerstring contains the set of destinations that share the same parent as itself. This is illustrated in figure 4: when destination 0 receives a packet, the peerstring has a bit set for all destinations, which have the same parent as itself (i.e., destination 2). When a router forwards a reliable BIER packet over an interface i, it must, in addition to updating the bitstring for that interface, update the peerstring -essentially setting the peerstring to the union of the bitstrings for all other outgoing interfaces.

An extension to this principle is to include two peerstrings in a data packet received by a destination d: one peerstring indicating destinations with the same parent as d, and a second peerstring indicating destinations with the same grandparent (but, not the same parent) as d -as illustrated in figure 5. Thus, this affords more flexibility, but at the expense of more per-packet overhead. This mode of operation will be referred to as the two-peerstrings mode.

III. SPECIFICATION

In the proposed BIER extension, the BIER header defined in [START_REF] Wijnands | Encapsulation for Bit Index Explicit Replication (BIER) in MPLS and Non-MPLS Networks[END_REF] is extended to include an additional bitstring, the peerstring, denoted P S1 and described in section II-B. When BIER operates in two-peerstrings mode, the header will also include a second peerstring, P S2. This header is included in all multicast data packets, and is processed by each intermediate router. Each multicast data packet also includes a reliable BIER header, defined in [START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF], which conveys flow identifiers and sequence numbers, and which allows detecting lost packets in a flow. This header only carries end-to-end semantics, and is not processed by intermediate BIER routers.

A. Source Operation

Packet transmission: The source adds a reliable BIER header to each multicast data packet, containing a flow identifier and a sequence number, as well as a standard BIER header [START_REF] Wijnands | Encapsulation for Bit Index Explicit Replication (BIER) in MPLS and Non-MPLS Networks[END_REF] extended with peerstrings, as described above. The bitstring BS in the BIER header contains the set of destinations receiving packets from within the flow. Also, the peerstring P S1 is set to BS and, if included, P S2 is also set to BS, as illustrated in figures 4 and 5. The multicast source also caches a copy of each sent packet during a time interval ∆t s cache .

Packet retransmission: When receiving an SR-NACK for a given packet, a source starts a timer ∆t s agg , during which it collects (potential) further SR-NACKs for the same packet from other destinations. Upon expiration of this timer, a retransmission of the packet is performed, with the set of destinations that have sent a NACK as the BIER bitstring.

B. Intermediate Router Operation

BIER bitstring processing: BIER packets are processed according to the BIER specification [START_REF] Wijnands | Multicast Using Bit Index Explicit Replication (BIER)[END_REF]. Only bits corresponding to destinations for which the shortest-path is via interface i are preserved in the bitstring contained in multicast data packets transmitted over that interface i.

Peerstring processing: Upon receipt of a reliable BIER packet with a bitstring BS in , and before forwarding it over interface i (with outgoing bitstring BS out i ), a router must update P S1 and, if included, also P S2. In two-peerstrings mode, first P S2 out i is set to P S1 in . Then, the peerstring P S1 out is set to the OR of the bitstrings sent over all other interfaces (formally, P S1 out i ← ∪ j =i BS out j ) 1 . This way, the P S1 sent over each interface contains the set of those other destinations, to which this router has sent a copy of the packet. Note that the use of bitwise operators to compute peerstrings makes it a simple operation to be implemented in hardware.

C. Destination Operation

Packet reception: Upon receipt of a packet by a destination, the packet can be cached for a duration of ∆t p cache (for potential retransmission to a peer). The peerstring(s) of the packet are inspected. The included P S1 is used for updating

1 P S1 out i ← BS in \ BS out i is an equivalent way of proceeding, as ∪ j =i BS out j = BS in \ BS out i holds as an invariant.
the set P 1 of "local" peers. If included, P S2 is used for updating the set P 2 , of second-most local peers.

Packet loss: Upon detection of loss of a packet in a given flow (e.g., by receiving a packet in the same flow, whose reliable BIER header indicates a higher sequence number), a destination builds an SR-NACK packet. The SR-NACK contains a reliable BIER header with the flow identifier and the sequence number of the requested packet, and its SR header segment list is set to (p 1 , . . . , p n , s), where the p i 's are peers selected from P 1 and P 2 , and where s is the source. Different policies can be used for deciding which peers to include from P 1 and P 2 , and in which order, as described in section IV.

While sending the SR-NACK, the destination starts a ∆t d retry timer. When this timer expires, if the no retransmission is received, the same SR-NACK is retransmitteduntil either the missing packet is received, or a retransmission request limit R lim is reached -after which recovery is aborted. (If semi-reliability is unacceptable, R d lim must be set to ∞.) Packet retransmission: Upon receipt of an SR-NACK, a peer inspects the reliable BIER header of the SR-NACK and extracts the flow identifier and sequence number. If a cached copy of the requested packet is available, it is scheduled for retransmission; otherwise, the SR-NACK is forwarded to the next entry in the segment list (i.e., to the next peer or, ultimately, to the source).

Retransmissions from peers use the same mechanism as those from the source: a timer ∆t p agg is used to collect other NACKs before sending the copy to the set of destinations which have NACKed the packet.

IV. PEER SELECTION POLICIES

As introduced in section III-C, upon missing a packet, a destination will build an SR-NACK with peer(s) extracted from P 1 and P 2 . The framework introduced in this paper is agnostic to the policy used for selecting those peers. To illustrate this, the remainder of this section suggests examples of simple policies for selection of peers to be included in SR-NACKs: random selection of peers, clustered selection of peers, and a simple adaptive (statistically-driven) policy.

A. Random Peer Selection

This policy builds an SR segment list (p, s) where s is the source, and p is a peer randomly selected from P 1 . Randomly selecting peers from P 1 may increase locality of retransmissions, but rarely allows aggregation of multiple retransmissions into a single BIER packet. As an example, if ten destinations d 1 , . . . , d 10 have the same parent (thus, for each d i , P 1 = {d 1 , . . . , d 10 } \ {d i }), and d 1 , d 2 both detect loss of the same packet, the probability that d 1 and d 2 send an SR-NACK for this packet to the same peer in {d 3 , . . . , d 10 } is 1/8.

B. Deterministically Clustered Peer Selection

This policy builds an SR segment list (p, s) such that all destinations with the same parent router (i.e., all destinations with the same P 1 ) select the same p. As a convenient convention, for this paper, all d will select as p the element in P 1 \ {d} with the highest index.

This policy generalises for two-peerstring mode by building a SR segment list (p 1 , p 2 , s). All d will select as p 1 the element in P 1 \ {d} with the highest index, and as p 2 the element in P 2 \ {d} with the highest index.

While this policy favours aggregation of local retransmissions into a single BIER packet, it does not guard against selecting an unsuitable peer, e.g., a peer located behind a particularly lossy link.

C. Adaptive Statistically-driven Peer Selection

As long as the constraint that the last segment in the SR segment list for a SR-NACK must be the source is satisfied, any adaptive policy -allowing a destination to observe and "learn" which peers are good candidates from whom to request retransmissions -can be be used for selecting additional peers for inclusion.

Formally, this is an instance of the Multi-Armed Bandit problem: an agent (a destination needing a retransmission) repeatedly activates one of several casino arms (in this case: sends an SR-NACK to a peer) and collects a reward (obtains, or not, a retransmission). The goal is a policy for maximizing the expected reward [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], [START_REF] Kuleshov | Algorithms for the multi-armed bandit problem[END_REF], [START_REF] Velmorel | Multi-armed bandit algorithms and empirical evaluation[END_REF].

As an illustration, a simple -greedy peer selection policy is employed: with probability ( 1), a destination detecting a packet loss sends an SR-NACK to a random peer among the set of available peers. With probability (1 -), it sends an SR-NACK to the peer from which it so far has received the highest number of successful retransmissions. The value of reflects the trade-off between exploration (contacting random peers and gathering statistics) and exploitation (requesting retransmission from the best known candidate) -between reactivity to changes and performance after convergence.

V. POLICY ANALYSIS

The impact of using peer caching and peer retransmissions, and of each of the policies introduced in section IV, can be quantified analytically. Section V-A provides a basic analysis of the benefits of local retransmissions, and section V-B derives an analytical model for the random and clustered policies. Section V-C then explores the benefits from a simple, adaptive policy. For tractability, as well as for ease of interpretation of the results, the models formulated in this section focus on a single multicast group, in a regular tree. Formulating and solving a model to derive policies applicable in the case of arbitrary topologies and multicast groups would be an interesting extension that is out of the scope of this paper. Proofs of the theoretical results presented in this section are available in the appendix.

A. Recovery Locality

The assumption in this paper is, that sending local recovery requests to a local peer is likely to be both "cheaper" than sending the request to the multicast source, and successful -i.e., a "close" neighbour is likely to have successfully cached the requested packet. This section explores the latter of these two assumptions, by quantifying the probability distribution of the distance from a destination having not received a given packet, to the closest peer that has (and, therefore, is able to perform retransmission).

A regular tree topology is assumed, wherein inner nodes are intermediate BIER routers, and leaves are destinations. Nodes at a given depth are assumed to have the same number of children, and links at a given depth have the same loss probability. As corresponds to the operation of BIER, the root node of the tree is assumed to be the multicast source.

The tree is of height h, with node ranks indexed by their depth in the tree, from 0 (the source) to h. Similarly, links ranks are indexed from 0 (links from source to first descendants) to h-1. Each node at rank i ∈ {0, . . . , h} has c i children (with c h = 0) and α i is the loss probability of links at rank i ∈ {0, . . . , h -1}. Multicast transmission of a single packet to all leaves is considered.

Lemma 1 gives the probability that no nodes in the subtree, rooted at a given node, do not receive the multicast transmission.

Lemma 1

The probability b i that a multicast transmission from a node at rank i ∈ {0, . . . , h} does not reach any destination (within its subtree), is:

b i = [α i + (1 -α i )b i+1 ] ci (1)
Proposition 1 The distribution of D, i.e., the shortest distance from an arbitrary destination to a destination having successfully received the multicast transmission can for k ∈ {1, . . . , h} be derived from (1):

f D (2k) = h-k-1 i=0 (1 -α i ) (α h-k + (1 -α h-k )b h-k+1 )× ×[1 -[(1 -α h-k )b h-k+1 + α h-k ] c h-k -1 ] (2)
with:

f D (0) = h-1 i=0 (1 -α i ) f D (∞) = b 0
In proposition 1, f D (0) corresponds to the probability that a destination has successfully received the multicast transmission.

D denotes the random variable of distance towards closest successful destination for destinations having not received the packet. The probability distribution of D can be computed as the conditional distribution of D (see proposition 1) given that the packet is not received (which has probability 1 -f D (0)), as shown in corollary 1.

Corollary 1 The distribution of D, the minimum distance from a destination that missed a packet and to a destination which successfully received the packet is, for k ∈ {1, . . . , h}:

1-2-2-2-32 exp 1-2-2-2-32 lin 1-2-2-2-2-2-8 exp 1-2-2-2-2-2-8 lin
f D (2k) = f D (2k) 1 -f D (0) = = h-k-1 i=0 (1 -α i ) 1 - h-1 i=0 (1 -α i ) (α h-k + (1 -α h-k )b h-k+1 )× × [1 -[(1 -α h-k )b h-k+1 + α h-k ] c h-k -1 ] (3)
with:

f D (0) = 0 f D (∞) = b0 1-f D (0) = b0 1-h-1 i=0 (1-αi)
The probabilities α i of loss at each link appear in equations ( 2) and ( 3), allowing to reflect different topology assumptions. In some topologies, loss probabilities may, e.g., be assumed negligible for links close to the source, and more significant for links close to destinations (i.e., α i < α j if i < j). Two models for rank-dependent link loss probabilities are considered:

• Linear increase (lin):

α i = α max i h-1 . • Exponential increase (exp): α i = α max e i -1 e h-1 -1 .
Figure 6 depicts the distribution of the minimum distance from a destination that missed a multicast transmission, and to a destination successfully receiving a multicast transmission, f D (2k). Two tree topologies with 256 destinations are considered: (i) h = 5, (c 0 , . . . , c 5 ) = (1, 2, 2, 2, 32); and (ii) h = 7, (c 0 , . . . , c 7 ) = (1, 2, 2, 2, 2, 2, 8).

It can be observed that the expected shortest distance between a failing destination and a successful peer is lower for the exponential loss model (in which the loss probability for top links is lower) than for the linear loss model. In other words, as expected, if top links are less lossy, it is more likely for a failing destination to be able to recover from a close destination.

This confirms the intuition that in networks with this type of loss distribution (such as can be envisioned in data-centres, or in networks where the "last hop" is, e.g., a wireless link, or a consumer grade residential xDSL), selection of local recovery peers (e.g., peers that are in the same subtree or in the immediately upper subtree) should be preferred to selection of peers farther away.

B. Clustered and Random Policies

The properties and performance of the two simplest, static, and (to some degree) most "extreme" peer policies of section IV -random and clustered peer selection -is studied by way of two metrics: the number of recovery successes (performance) and the number of incurred recovery retransmissions (cost). A recovery is successful if a destination detecting the loss of a packet sends an SR-NACK to a peer that previously has received and cached a copy thereof. The number of recovery retransmissions incurring is the number of unique peers, which are selected for retransmission by the set of destinations which have lost that packet. This is because each selected peer will send only one BIER transmission as a response to receiving a set of SR-NACKs for the same multicast packet.

For the remainder of this section, a subtree with n destinations is considered, and recovery of one packet within this subtree is examined.

The following variables are introduced (where X denotes a particular selection policy):

• K, the number of destinations which did not receive the packet by way of the original multicast transmission from the source; • S X , the number of recovery successes, i.e., destinations which did not received the packet by way of the original multicast transmission from the source, but which successfully received a retransmission from a peer, in response to an SR-NACK. • T X , the number of recovery retransmissions, i.e., of unique peers which received an SR-NACK for a given multicast packet. Figure 7 shows an example with n = 10 destinations, K = 4 destinations missing a packet, S X = 3 successful requests (out of 4) and T X = 2 retransmissions.

Lemmas 2 and 3 describe the probability density function (PDF) for the number of recovery successes (S R , S D ) and for the number of retransmissions (T R , T D ), for the random and clustered policies, respectively. For the number of retransmissions with the clustered policy, it is assumed that a peer, from receiving the first SR-NACK and until retransmission of the packet, waits a sufficiently large amount time so as to maximise the ability of aggregating retransmissions into a single BIER-transmission.

Lemma 2 (Random selection policy) Given K = k destinations (0 ≤ k ≤ n) that did not receive the multicast transmission from the source, the probability that, from among these k destinations, s (0 ≤ s ≤ k) will choose a peer which did receive the multicast transmission from the source, Given s recovery successes, the probability of t retransmissions (0

P r[S R = s|K = k] ≡ f S R ,k (s), is: f S R ,k (s) = k s k -1 n -1 k-s n -k n -1 s (4)
≤ t ≤ s), P r[T R = t|S R = s, K = k] ≡ f T R ,k,s (t), is: f T R ,k,s (t) = n -k t t i=0 (-1) t-i t i i n -k s (5)
Lemma 3 (Clustered selection policy) Similar to Lemma 2, the probability that s destinations (out of k ≥ 2 destinations that did not receive the multicast transmission from the source) will choose a peer which did receive the multicast transmission from the source, P r[

S D = s|K = k] ≡ f S D ,k (s), is: f S D ,k (s) =            n-k n if s = k k n 1 -k-1 n-1 if s = 1 k n k-1 n-1 if s = 0 0 otherwise (6)
The probability of having t retransmissions, P r[

T D = t|K = k] ≡ f T D ,k (t), is: f T D ,k (t) =      1 -k n k-1 n-1 if t = 1 k n k-1 n-1 if t = 0 0 otherwise (7)
As edge cases, when k = 1, there is one recovery/retransmission: S D = T D = 1; and when k = 0, there are no recoveries/retransmissions:

S D = T D = 0.
From lemmas 2 and 3 follow two key results, describing the average number of recovery successes (proposition 2) and the average number of retransmissions (proposition 3 and corollary 2). Proposition 2 Assuming K = k destinations that did not receive the multicast transmission from the source, the expected number of recovery successes for the random and clustered approaches is the same, and has the value:

E[S R |K = k] = E[S D |K = k] = k(n -k) n -1 (8)
Proposition 3 Assuming K = k destinations that did not receive the multicast transmission from the source, the expected number of retransmissions for random (S R ) and clustered (S D ) policies have the following expressions:

E[T R |K = k] = (n -k) -(n -k) n -2 n -1 k (9) E[T D |K = k] = 1 -k(k-1) n(n-1) if k ≥ 1 0 if k = 0 (10)
The following corollary compares the behavior of both policies when considering that each destination has, independently, the same probability of having not received the multicast transmission from the source.

Corollary 2 Assuming that each destination has (independently of the others) a probability β ∈ [0, 1] of not having received the multicast transmission from the source (i.e., the probability of having k destinations, that did not receive the multicast transmission from the source, is binomial with parameter β, and thus P r

[K = k] = n k β k (1 -β) n-k
), then the expected number of retransmissions with the random policy grows linearly with the number of destinations, whereas the expected number of transmissions with the clustered policy is bounded:

E[T R ] ∼ n→∞ n(1 -β)(1 -e -β ) = Θ(n) E[T D ] ∼ n→∞ 1 -β 2 = Θ(1) (11)
From proposition 2, both policies yield the same performance on average, i.e., the expectation of the number of recovery successes is the same for both policies. The clustered policy achieves the same reliability as the random policy by concentrating recovery requests on a single peer, which allows aggregation of retransmissions into a single BIER retransmission. Since aggregation occurs less often in the random policy, in terms of retransmission cost, the random policy is more expensive (linear in the number of destinations vs constant), as shown in corollary 2.

This difference is only possible because random and clustered policies achieve their (equal) average performance through different probability density distributions, as shown in figure 8. In this example, it is assumed that k = 35 destinations out of n = 100 have not received the initial multicast transmission. While with the random policy there is negligible chance that no less than 15 and no more than 30 destinations are able to obtain a retransmission from a peer, the clustered policy operates on an all-or-nothing fashion: all 35 destinations will obtain a retransmission from a peer with high probability -but recovery may be mostly unsuccessful with non-negligible probability (∼ 12% for 0 successes, 23% for only one success over 35).

For the purpose of illustrating the relative performance of random and clustered policies, it is possible to consider a Service Level Agreement (SLA) commitment specifying a minimum fraction of destinations (1 -δ) (with δ 1) being served without the need for source retransmission. Source retransmissions are unneeded when destinations receive the packet in the first BIER transmission from the source, and when the first peer recovery request is successful. Since source retransmission may lead to a substantial increase in packet latency, the previously described SLA can be reformulated in terms of reduced latency experienced by a higher fraction of destinations. The probability that a fraction (1 -δ) of destinations is served without resorting to source retransmissions, under policy X, g n,β,X (δ), is:

g n,β,X (δ) = P r[S X > K -nδ] = = n k=0 P r[S X > K -nδ|K = k]P r[K = k] (12)
where P r[S X > x|K = k] can be computed from equations ( 4) and ( 6). Figure 9 illustrates the value of g n,β,X as a function of δ, when n = 100, β = 0.2, and for the random and clustered policies 2 . Figure 9 can be used to help an operator decide which policy to choose. For strict SLAs where a large fractions of the destinations must be served without source retransmissions (δ ≈ 0), there is a higher probability that systems are compliant when using the clustered policy (δ < 0.05 in figure 9). Conversely, with looser SLAs, there is a higher probability that systems are compliant when the random policy is used (δ > 0.05 in figure 9), and both policies behave identically for highly-loose SLAs (δ > 0.25 in figure 9). To conclude, when source retransmissions are significantly less preferable than peer retransmissions (e.g., due to a substantially higher delay incurred), the clustered policy might be preferable with respect to the random policy.

C. Going Adaptive: the -Greedy Policy

For the purpose of this analysis, a binary (c = 2) multicast BIER transmission tree, with height h = 7, to illustrate the ability of the simple -greedy adaptive policy and to learn and adapt to changes in networking conditions, under two different scenarios:

• A (static) scenario (figures 10(a) and 11(a)), where all links are lossy (α = 0.1), except for links between the source and destination 0 -i.e., with a static "best" (ideal) peer from which to request retransmission. Number of destinations that did not receive the multicast transmission from the source, and which are selecting peers 0 and 32 under the -greedy policy, in (a) static and (b) dynamic scenarios.

• A (dynamic) scenario (figures 10(b) and 11(b)) which reflects a situation with failure of a "good" peer. Specifically destination 0 is, as in the static scenario and for the same reasons, the "best" (ideal) destination (α = 0 for links from destination 0 and to the source) up until multicast packet # 8000, after which it becomes a bad destination behind very lossy (α = 0.4) links. Concurrently, destination 32 is a relatively good, though not perfect, destination (α = 0.01) during the entire duration of the flow. It is worth to observe that, in these simulations, recoveries are idealized: retransmissions from contacted peers are always successful if the contacted peer holds a copy of the requested BIER packet. Unsurprisingly, = 0 (i.e., choosing deterministically the destination with highest success record) achieves more steady performance than does = 0.2 (i.e., choosing random destinations for recovery 20% of the time) in static conditions (figure 10(a)). Using = 0.2 policy, however, performance is less impacted by the failure of destination 0, and the system adapts faster to the new conditions (figure 10(b)): as shown in figure 11(b), failing destinations when using = 0.2 switch to destination 32 quicker, after the failure of (former ideal) destination 0.

VI. SIMULATION ENVIRONMENT

The reliable multicast mechanism, described in this paper, has been implemented in NS-3 [START_REF] Riley | The ns-3 network simulator[END_REF] as four components: (i) a BIER forwarding plane (as described in section III-B), (ii) a Segment Routing forwarding plane, (iii) a reliable BIER layer for a source (section III-A), and (iv) a reliable BIER layer for destinations (section III-C).

The reliable BIER layer at the source interfaces with the UDP socket API, to transform UDP multicast packets into BIER packets, while also caching a copy of sent packets so as to be able to retransmit them on receipt of SR-NACKs. The reliable BIER layer at a destination also interfaces with the UDP socket API, collecting received BIER packets before handing them (in-order) over to the UDP socket. This layer also caches a copy of received packets, so as to be able to retransmit them on receipt of a SR-NACK from a peer, and generate SR-NACKs when a packet loss is detected.

The parameters as defined in section III are: ∆t s agg = ∆t p agg = 7 ms, ∆t p cache = 50 ms, ∆t s cache = 100 ms, ∆t d retry = 15 ms, R d lim = 3. Notably, the value of the SR-NACK retry delay is set significantly greater than the NACK aggregation delay, ∆t d retry ∆t agg , so that a second NACK is only sent if the source (or peer) has had the chance to send a retransmission and has failed.

A. Links and Link Loss Model

All links are point-to-point, with 1 Gbps throughput and 1 µs propagation delay, have an MTU of 1500 bytes, and are attached to interfaces with drop-tail queues of size 512 packets.

The link loss model used for all links in the simulations is a clock-based Gilbert-Elliott model [START_REF] Gilbert | Capacity of a burst-noise channel[END_REF], [START_REF] Elliott | Estimates of error rates for codes on burst-noise channels[END_REF], where the probability of a successful transmission is k = 1 in good state and h = 0.5 in bad state. Transitions from bad to good, and from good to bad, are triggered with exponential clocks, of mean 1/r = 2.5 ms and 1/p = (h-α) αr = (0.5-α) α × 2.5 ms, respectively, where α ∈ [0, 1] is a parameter representing "packet loss probability".

According to [START_REF] Hasslinger | The gilbert-elliott model for packet loss in real time services on the internet[END_REF], the probability π B of being in bad state is

π B = p p+r = 1 1+(h-α)/α = α 0.5 , yielding an expected link loss rate of π B (1 -h) + (1 -π B )(1 -k) = 0.5π B = α.
This justifies using α as a parameter to tune the average packet loss probability. This loss model is only applied to multicast data packets -SR-NACKs are not subject to losses, as the path from destinations to the source is supposedly less lossy 3 .

VII. DATA-CENTER SIMULATIONS

For the purpose of evaluating the mechanism introduced in this paper, a data-center-like topology is first used.

A. Network Topology

The topology used in this set of simulations is as follows, illustrated in figure 12: • a source, "outside" the data-center -reachable across a capacity constrained connection (e.g., a connection incurring higher delays, which has limited throughput, or subject to a higher, congestion-induced, loss probability) is attached to a core router; • the core router is attached to 2 aggregation routers;

• each aggregation router is attached to 2 Top-of-Rack (ToR) routers; • each ToR router is attached to 10 servers in a rack (destinations).

In other words, the topology is a regular tree, in which successive arities are (1, 2, 2, 10). This topology has been chosen for the simulations for two reasons. First, it can be used to reason about actual data-centerspecific scenarios (as introduced in section I) -e.g., distributed storage, distribution of software upgrades, or pre-placement of content. Second, as BIER packets in any arbitrary topology will effectively be spread along a shortest-path tree, reasoning about a regular tree is a first step towards understanding the properties of the proposed mechanism (simulations on nonregular trees are deferred to section VIII).

It is to be noted that such a topology does not allow for evaluating what happens in multi-path-enabled data-center topologies, such as BCube [START_REF] Guo | BCube: a high performance, server-centric network architecture for modular data centers[END_REF] or DCell [START_REF] Guo | DCell: a scalable and fault-tolerant network structure for data centers[END_REF]. However, such topologies rely on source-routing to effectively transmit packets, and would thus require modifications to the BIER forwarding plane so as to properly encode the multicast tree, which is outside of the scope of this paper. Furthermore, interpreting evaluations based on these topologies would make it difficult to highlight how the mechanism introduced in this paper reacts to congestion on a link, since these topologies would tend to naturally spread congestion across all links.

B. Evaluation Objectives

The objective of using SR-NACKs for requesting retransmissions from peers, rather than directly from the source, is specifically not to minimize the number of transmissions, globally -but, rather, to maximize the number of retransmissions that can be satisfied locally, i.e., within the data-center. Consequently, one key metric is the number of retransmissions performed by the source -corresponding to the load of the link between the source and the core router (bold link in figure 12).

C. Static Peer Policy -One-Peerstring Mode

To baseline the benefits of locality, the two static peer selection policies introduced in section IV-A (random) and in section IV-B (clustered) are tested in one-peerstring mode: a destination, which detects that a packet has been lost, sends an SR-NACK towards first a "local" peer4 according to the policy, then to the source. These two static peer selection policies are compared with classic reliable BIER without peer recovery (i.e., wherein NACKs are sent directly to the source).

Figure 13 depicts the results of 19 four-second-long simulations using a 500 Mbps multicast flow (i.e., 166673 BIERpackets generated by the source), for different values of α (see section VI) applying uniformly to all links. Figure 13a shows the link usage of the ingress link to the core router (see figure 12), averaged over the duration of the simulation. Using classic reliable BIER, the source performs all retransmissions, and the ingress link to the core router saturates for α ≥ 7%. With peer-based retransmissions, even with α = 10%, this link remains well below saturation, with a link usage below 680 Mbps. This is detailed in figure 13a, and explained through figure 13b, which depicts the number of times a retransmission has been performed by the source.

On receiving an SR-NACK, a peer waits for ∆t p agg , to allow receiving SR-NACKs from other peers, before a single aggregate BIER retransmission is made. Thus, the number of destinations in the bitstring is an indicator of the ability to reduce the number of retransmissions. This is depicted in figures 13c and 13d, for retransmissions made by the source or by a peer, respectively, and for random and clustered peer selection policies. Retransmissions by the source are required when both the originator of an SR-NACK, and the selected peer, have not received a given packet -e.g., when the packet was lost over the link between an aggregation router and a ToR router (see figure 12), in which case all destinations below that ToR router would need to receive a retransmission. This explains why most source retransmissions are destined to 2 to 10 destinations (figure 13c). Similarly, but to a lesser extent, a consequent number of source retransmissions are destined to between 11 and 20 destinations, which can be explained in most cases by a loss over the link between an aggregation router and the core router. Figure 13d also shows that random peer selection (expectedly) does not facilitate aggregation in peer-issued retransmissions, whereas clustered peer selection allows for some aggregation -which occurs when a packet is lost several time in the same subtree.

D. Static Peer Policy -Two-Peerstrings Mode

A variation of the clustered peer policy (section IV-B) is possible when using two peerstrings. A destination, detecting that a packet has not been received, sends an SR-NACK towards first the leftmost "local" peer, then to the leftmost second-most local 5 peer, and finally to the source. The objective is, again, to reduce the number of retransmissions needed from the source, at the cost of potentially more total (but, local) traffic. The baseline for this approach is the clustered peer selection policy of section VII-C, as well as standard reliable BIER, thus the same topology, traffic patterns, and link loss model, are used. The simulation results for different values of α are depicted in figure 14, where figure 14a shows that the two-peerstring approach yields a further reduction in the link usage on the ingress link to the core router, due to fewer retransmissions being required by the source. In figure 14b, this reduction appears to be from 2.2× less (when α = 0.05) to 3.3× less (when α = 0.02), when comparing to the onepeerstring approach.

To understand the ability of the proposed mechanism to reduce retransmission traffic, figure 14c depicts the number of destinations in the retransmission bitstrings. Using the twopeerstring mode, retransmissions by the source are required only when neither the originator of an SR-NACK, nor its selected local peer, nor its selected second-most local peer, have received a given packet -most usually when the packet was lost over the link between an aggregation router and the core router. This explains why the majority of retransmissions are sent to between 11 and 20 destinations, and confirms a greater degree of aggregation (among 20 destinations, rather than 10) of source retransmissions, as compared to the onepeerstring mode. Furthermore, due to their ability to collect SR-NACKs from an adjacent subtree, designated peers will sometimes perform retransmissions to a whole rack (when a link from an aggregation router to a ToR router has failed), thereby also increasing aggregation as compared to the onepeerstring mode.

Finally, to understand the impact of the proposed mechanism in terms of incurred signaling traffic, table I reports the signaling overhead caused by SR-NACKs emitted during the simulations, for both the one-peerstring and two-peerstring mode, as well as for standard reliable BIER. Signaling overhead is computed in terms of packet-links, i.e., SR-NACKs per traversed links (in the tree). An SR-NACK traversing n links in the tree counts as n packet-links 6 . For each mechanism and each value of α, table I displays the average signaling overhead per multicast data packet, i.e., the number of (SR-NACK) packet-links needed, in average, before all destinations have received a new multicast dat packet from the source. Results show that signaling overhead incurred by the twopeerstring policy is approximately 1.4× the overhead related to the one-peerstring policy, but this extra signaling overhead is what allows for greatly reducing the number of source-induced retransmissions (as depicted in figure 14a), thus providing better quality of service for the clients.

E. Adaptive Peer Policy

To simulate the existence of some local peers being "more suitable" than others, the link loss model is modified such that each ToR router has exactly one destination with a non-lossy ToR-to-destination link. An adaptive policy should enable all other destinations connected to that ToR router to "learn" that this peer is the "most suitable" peer for retransmissions, and therefore, when detecting that a packet has not been received, send an SR-NACK towards first this "most suitable" peer, and only then to the source. To exemplify this, and to examine the intuitions from section V-C, the -greedy policy has been implemented and tested against the random peer selection policy 7 (section VII-C) and standard reliable BIER. In order to allow for sufficient exploration, = 0.2 is used.

Simulations are run for different values of α, with results depicted in figure 15. As -greedy allows directing an SR-NACK towards peers that have a greater chance of being able to retransmit a packet, these are less often forwarded to the source, reducing the number of source retransmissions (figure 15b) and the link usage of the ingress link to the core router (figure 15a). Finally, when a SR-NACK is received by a "more suitable" peer, its retransmissions are more often successful (as it is connected to its ToR router over a non-lossy link), reducing further retransmissions of that packet.

VIII. ISP SIMULATIONS

To validate the genericness of the proposed approach with respect to the network topology, another set of simulations has been conducted, this time in a real ISP topology. As compared to section VII, the resulting spanning tree is non-regular. Use cases for reliable multicast in such topologies include video streaming of live events.

A. Network Topology

The topology used for the purpose of this set of simulations is the BT Europe, August 2010 topology, extracted from the Internet Topology Zoo [START_REF]Internet Topology Zoo[END_REF]. The topology is depicted in figure 16a, and consists of 24 nodes. All nodes are located in Europe, except for nodes 11 (New York) and 12 (Washington DC), which are not visible on the figure, and have each a link to node 17 (London). As this topology features remote (transatlantic) nodes, it is suited to evaluate scenarios wherein it is costly to traverse certain links. As such, the scenario studied in this section will be the transmission of a multicast stream from node 11 (New York) to all other nodes.

Another point of interest of using such a non-regular topology is, that it provides a more natural framework to test adaptive peer selection policies. Indeed, some destination(s) will automatically be both close to the source (thus, more prone to have received packets because there are less links in the path to the source) and close to an important number of other peers. As an illustration, figure 16b shows the closeness centrality of each node in the graph, defined as the inverse of the mean distance to the other nodes. It can be observed that nodes 17 (London), 21 (Amsterdam) and 5 (Frankfurt) exhibit the highest centrality, meaning that they are 'local' to a large part of destinations, and would therefore be natural candidates to act as retransmitting peers.

B. Peer Selection Policies Evaluation

For the purpose of the simulations, a client is attached to each of the nodes, except for node 11 (NYC), to which a source is attached; the Dijkstra algorithm is first run offline to construct routing tables. As in section VII, links have 1 Gbps capacity, and the same simulation parameters are used. A multicast flow of 500 Mbps is sent from the source to each of the clients during four seconds, in [START_REF] Weil | Ceph: A scalable, high-performance distributed file system[END_REF] for different values of the average link loss probability α.

The random selection policy with one peerstring is used to evaluate the core properties of the mechanism introduced in this paper. Additionally, the -greedy policy is evaluated, as a way to examine the convergence of destinations under adaptive policies towards highly-central nodes as retransmitters. Finally, as a baseline, reliable BIER as in [START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF] is used. Results are reported in figure 17. Figure 17a depicts the average usage of the link between the source and the router to which it is attached. Whereas with standard reliable BIER the link is saturated for high values of α (α ≥ 6%), usage of this link is reduced with peer-based BIER retransmissions (the worst case being 720 Mbps for α = 10%), showing that the proposed mechanism allows protecting the source from having to retransmit too many packets. This can be also observed on figure 17b, depicting the number of individual packet retransmissions performed by the source: the number of source retransmissions falls by a factor of at least 2.2× when using peer-based retransmissions.

With respect to the comparison between static and adaptive policies, figure 17b shows that the number of source-based retransmissions is further reduced when using the adaptive policy. This can be explained by observing, for each peer, the number of packets successfully recovered through this peer, for the static policy and the adaptive policy (figure 17c) -the figures display the distribution for the lossiest tested scenario (corresponding to α = 0.1), so as to better visualize the differences. Whereas with the static policy the distribution of retransmitters is relatively uniform, with the adaptive policy it can be clearly observed that peers 17 and 5 (and, to a lesser extend, peer 21) contributes to most of the recoveries. This confirms that retransmissions are handled by peers with high centrality (see figure 16b).

IX. CONCLUSION

This paper extends the reliable multicast service based on BIER. The proposed extension uses BIER for ensuring that data traffic is forwarded over minimal shortest path trees, and SR-based NACKs for reporting losses and requesting retransmissions. SR-NACKs allow failing destinations to contact, in order, peers for (local) recovery before requesting retransmission from the source. All retransmissions are performed through BIER-enabled shortest paths.

The proposed protocol is compatible with standard BIER operation (RFC 8279 [START_REF] Wijnands | Multicast Using Bit Index Explicit Replication (BIER)[END_REF]): no caching is made by intermediate routers, retransmissions are regular BIER packets, and the retransmission logic is handled exclusively by sources and destinations. In addition, a lightweight extension to the BIER forwarding plane is proposed (the processing of a peerstring in the BIER header), allowing destinations to automatically learn about potential candidates from which to ask retransmissions. In absence of this extension, peer-based recoveries can still be requested if destinations are manually configured to do so. By allowing for local repair of multicast failures, the proposed mechanism limits the amount of source retransmissions, and thus their impact in terms of network traffic and delay.

The proposed framework is generic enough to accommodate a broad spectrum of policies for selection of recovery peers, including static, adaptive, and operator-defined. Example of such policies are introduced and analyzed, both analytically and by way of network simulations. Evaluation suggests that substantial benefits in terms of increasing locality of recoveries and reducing usage of costly links can be achieved with relatively simple policies.

s recoveries corresponds to the number of unique elements sampled when drawing with replacement s elements from a set of (n -k) elements. From [START_REF] Mendelson | What is the distribution of the number of unique original items in a bootstrap sample?[END_REF], this is:

1 (n -k) s × (n -k)! (n -k -t)! × s t
where s t (Stirling number of second kind) represents the number of ways to partition s elements into t non-empty subsets, and can be expressed as:

s t = 1 t! t i=0
(-1) t-i t i i s

Combining these two expressions yields equation ( 5), which concludes the proof.

B. Proof of lemma 3

Proof: Consider the clustered policy, whereby a failing destination sends a NACK to a designated peer p, and p itself if failing sends NACKs to another designated peer p * . Consider the transmission of a multicast packet to a cluster of n destinations, from among which k do not receive the packet. Each of the k non-successful destinations then sends a recovery request (NACK) to p (or p * if the non-successful destination is p itself). If the designated peer p is not amongst the k failing destinations (which happens with probability n-k n ), all the recoveries are successful, and S D = k. If the designated peer p is among the failing destinations, but not its retransmitter p * (which happens with probability k n 1 -k-1 n-1 ), then only one recovery request is successful (the one from the designated peer p), and S D = 1. Finally, if both the designated peer p and its retransmitter p * are among the k failing destinations (which happens with probability k n k-1 n-1 ), no retransmission request is successful, and S D = 0. Combining these three cases yields equation [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF].

To derive equation [START_REF] Nicholas | Protocol Independent Multicast -Dense Mode (PIM-DM): Protocol Specification (Revised)[END_REF], it suffices to note that both cases by definition, which proves equation [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF] for the random policy.

From equation ( 6), the expected value of S D can be computed as:

E[S D |K = k] = k × n -k n + 1 × k n 1 - k -1 n -1 = k n -1 (n -k) which proves that E[S R |K = k] = E[S D |K = k].
D. Proof of Proposition 3 Proof: Assuming that k destinations have missed the multicast packet, and that s recoveries are successful, the expected number of incurred recovery retransmissions for the random policy is computed by averaging equation ( 5):

E[T R |S R = s, K = k] = s t=0 t × P r[T R = t|S R = s, K = k] = (n -k) 1 - n -k -1 n -k s
Then, the average number of retransmissions with no assumption on s can be obtained by combining this result with equation ( 4), yielding (with p = k-1 n-1 to ease notation):

E[TR|K = k] = k s=0 E[TR|SR = s, K = k] × P r[SR = s, K = k] = (n -k) -(n -k) k s=0 k s p k-s (1 -p) s n -k -1 n -k s = (n -k) -(n -k) n -2 n -1 k
For the clustered policy, deriving the expected number of retransmissions is done by averaging equation [START_REF] Nicholas | Protocol Independent Multicast -Dense Mode (PIM-DM): Protocol Specification (Revised)[END_REF], and by noting that since the number of retransmissions is either 0 or 1, the expected value is simply the probability that there is one retransmission:

E. Proof of Corollary 2

Proof: Assuming that each destination has missed the multicast packet independently with probability β, the number K of failing destinations follows a binomial distribution:

P r[K = k] = n k β k (1 -β) n-k (13)
For the random policy, it is possible to deduce the expected number of retransmissions (averaged over the failing destinations k) by combining equations ( 9) and ( 13):

E[T R ] = n k=0 E[T R |K = k] × P r[K = k] = (n -nβ) - n k=0 n k β k (1 -β) n-k (n -k) n -2 n -1 k = n(1 -β) 1 -1 - β n -1 n
which is, if n → ∞ and β = 0, β = 1, using Taylor's 1st-term approximation of 1 -β n-1 n :

E[T R ] = n(1 -β)(1 -e -β ) + O(1) (14)
The same reasoning can be used for the clustered policy. The expected number of retransmissions becomes, by using [START_REF] Wijnands | Multicast Using Bit Index Explicit Replication (BIER)[END_REF] and ( 13):

E[T D ] = n k=0 E[T D |K = k] × P r[K = k] = n k=1 n k β k (1 -β) n-k 1 - k n k -1 n -1 = 1 -(1 -β) n -β 2
which is, if n → ∞ and β = 0:

E[T D ] = 1 -β 2 + o(1) (15)
concluding the proof.

Figure 1 .

 1 Figure 1. Example of BIER packet forwarding

Source

Figure 2 .

 2 Figure 2. Comparison of different reliability mechanisms. In this example, red clients are assumed to have missed reception of a packet and sent a NACK.With "standard" multicast retransmissions[START_REF] Adamson | Reliable messaging for tactical group communication[END_REF], the source re-floods the whole tree as a result (a). With BIER retransmissions[START_REF] Desmouceaux | Reliable Multicast with B.I.E.R[END_REF], the source re-floods only the subset of failing destinations (b). With peer-based BIER retransmissions introduced in this paper, the NACKs are sent to a peer that had cached the packet, which then floods the failing destinations, spanning a smaller tree (c).

  (A, B, S) Has copy -> don't forward SR-NACK (a) SR-NACK to peer+source, peer retransmission.

  (A, B, C, S) Has copy -> don't forward SR-NACK (b) SR-NACK to two peers+source, second peer retransmission. (A, B, C, S) No copy -> forward SR-NACK SR-NACK (A, B, C, S) (c) SR-NACK to two peers+source, source retransmission.

Figure 3 .

 3 Figure 3. SR-based recovery scenarios: SR-NACK sent by A. A red destination indicates that it is not able to satisfy the retransmission request, whereas a green destination indicates that it is.

Figure 5 .

 5 Figure 4. Example of peerstring operation

Figure 6 .

 6 Figure 6. PDF of the recovery at 2k hops (conditioning to a loss).

Figure 7 .

 7 Figure 7. Example with a policy X over n = 10 destinations, with K = 4 destinations (2, 5, 6 and 7) having lost a packet. Arrows indicate recovery requests (SR-NACKs): destination 2 requests recovery from peer 1; destination 5 from peer 2; and destinations 6 and 7 from peer 10; S X = 3 recovery requests are successful (i.e., those from 2, 6 and 7), as peers 1 and 10 have correctly received the original packet; T X = 2 retransmissions are performed (from 1 and 10).

Figure 8 .

 8 Figure 8. Number of destinations able to obtain a retransmission of a packet from a peer, when k = 35 out of n = 100 have not received the initial multicast transmission.

Figure 9 .

 9 Figure 9. Probability that a fraction of (1 -δ) of destinations successfully receive the packet (1) directly from the source in the first transmission, or (2) from a contacted peer -i.e., excluding source retransmissions, with n = 100, β = 0.2.

Figure 10 .

 10 Figure 10. Success ratio (after 1st recovery) for -greedy policy, for (a) static and (b) dynamic scenarios.

Figure 11 .

 11 Figure 11.Number of destinations that did not receive the multicast transmission from the source, and which are selecting peers 0 and 32 under the -greedy policy, in (a) static and (b) dynamic scenarios.

Figure 12 .

 12 Figure 12. Datacenter topology for simulations of section VII

Figure 13 .

 13 Figure 13. Clustered vs random peer selection within same subtree, and for different values of the Gilbert-Elliott link loss probability α.

Figure 14 .

 14 Figure 14. Data-center topology: clustered peer selection in two subtrees vs in one subtree, for different values of the Gilbert-Elliott link loss probability α.

  Figure 15. Data-center topology with one ideal peer per rack: -greedy peer selection in subtree vs random, for different values of the Gilbert-Elliott link loss probability α.

  (a) Network topology (picture from[START_REF]Internet Topology Zoo[END_REF]).

Figure 16 .

 16 Figure 16. ISP topology for simulations of section VIII

  Histogram of peer contributions to recoveries (α = 0.10), for random and -greedy strategies. Node 11 (NYC) is the source.

Figure 17 .

 17 Figure 17. ISP topology: -greedy vs. random peer selection in subtree, for different values of the Gilbert-Elliott link loss probability α.

  S D = k and S D = 1 yield one retransmission, and that S D = 0 yields zero retransmissions. Thus P r[T D = 1|K = k] = P r[S D = k|K = k] + P r[S D = 1|K = k] and P r[T D = 0|K = k] = P r[S D = 0|K = k], yielding equation (7). C. Proof of Proposition 2 Proof: Assuming that k destinations have missed the multicast packet, S R has a binomial distribution with k samples and with success probability n-k n-1 . Thus, E[S R |K = k] = k × n-k n-1

E

  [T D |K = k] = P r[T D = 1|K = k]

  different simulations,

		1.2x10	9
	Average link usage (b/s)	0 2x10 8 4x10 8 6x10 8 8x10 8 1x10 9			BIER-PEER ε-greedy, source to core link BIER-PEER random, source to core link BIER, source to core link
			0	0.01 0.02	0.03	0.04	0.05	0.06	0.07	0.08	0.09	0.1
					Average loss probability (α)
		(a) Link usage between node 11 (New York) and its router
	Source retransmissions	0 50000 100000 150000 200000 250000	0.01 BIER-PEER ε-greedy 0.02 0.03 BIER-PEER random BIER	0.04	0.05	0.06	0.07	0.08	0.09	0.10
					Average loss probability (⍺)

While the gap amplitude is dependent on the value of β (i.e., lower loss probabilities at destination lead to shorter gaps, as it can be expected), the trend shown in figure9is invariant for values of n and β.

Whereas traffic from the source to the destination is bursty, and therefore likely to cause interface buffers to run full, and drop packets, traffic from destinations to the source is expected to be sparse (essentially, SR-NACKs).

A peer is considered "local" if it has the same parent -in which case, it is indicated in the received P S1 in .

A peer is considered "second-most local" if it has the same grandparent, but not the same parent -in which case, it is indicated in the received P S in 2 .

Given figure12, an SR-NACK will have traversed two links if reaching the most local peer, six links if then reaching the second-most local, and ten links if then reaching the source.

The comparison is made to the random peer selection policy, rather than to any of the clustered peer selection policies. Selecting the destination with the non-lossy link for any of the clustering policies would amount to biasing in favour of that policy -selecting any other, would amount to biasing in its disadvantage.

ACKNOWLEDGEMENTS

This work was supported in part by the Cisco-Polytechnique Chaire "Internet of Everything" (http://www. internet-of-everything.fr).

APPENDIX

A. Proof of lemma 2

Proof: Consider the transmission of a multicast packet to a cluster of n destinations, from among which k do not receive the packet. Each of the k non-successful destinations then selects a peer at random among (n -1) peers (all peers but itself), and there are (n -k) successful peers, thus this selection is successful with probability n-k n-1 . Therefore, the probability that s of the k non-successful destinations sends a NACK to a successful peer follows a binomial law with parameter n-k n-1 , yielding equation (4).

To derive equation ( 5), assume that there are s successful recoveries. The number of retransmissions t incurred by these