B I E R Yoann Desmouceaux

Thomas Heide Clausen

Juan Antonio

Cordero Fuertes

W Mark Townsley

Reliable Multicast with

Keywords: multicast, reliable multicast, Bit Indexed Explicit Replication (BIER), scalability, performance evaluation

Inter-network multicast protocols, which build and maintain multicast trees, incur both explicit protocol signalling, and maintenance of state in intermediate routers in the network. B.I.E.R. (Bit-Indexed Explicit Replication) is a technique which can provide a multicast service yet removes such complexities: intermediate routers are unencumbered by group management, and no per-group state is to be maintained.

This paper explores the use of B.I.E.R. as a basis for developing an efficient and reliable multicast mechanism, where redundant traffic is avoided, essential traffic is forwarded along shortest paths, and no per-flow state is required in intermediate routers. Evaluated by way of both an analytical model and network simulation both in generic and in real network topologies with varying background traffic loads, the proposed B.I.E.R.-based reliable multicast mechanism exhibits attractive performance attributes: it attains delivery success rates as high as any other reliable multicast service, but with significantly better link utilisation and no per-flow or per-group state in intermediate routers of the network.

I. INTRODUCTION

Developed alongside their unicast counterparts, multicast protocols were never offered as universally available network services in the Internet [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] -in part, as the operational complexity of multicast was perceived as exceeding the potential benefits from efficient one-to-many distribution of content. "Native" multicast was therefore, when available, confined to within single networks (or even, to within single links) -and multicast between sites ("inter-network multicast") was established by way of overlays (e.g., MBONE [START_REF] Eriksson | Mbone: The multicast backbone[END_REF]). The complexity of multicast protocols is, in part, due to their group-based nature: schematically, when a client wishes to receive messages sent to a multicast group, it will explicitly and periodically send join messages to its "local multicast router" (using IGMP). This router will forward these join message upwards in the multicast tree (using e.g., PIM [START_REF] Nicholas | Protocol Independent Multicast -Dense Mode (PIM-DM): Protocol Specification (Revised)[END_REF]), until reaching the multicast source. Intermediate routers are expected to build, and maintain, flow state (a minima, a multicast tree) for as long as join messages are regularly received, in order to provide connectivity to all members of the multicast group.

Bit-Indexed Explicit Replication (B.I.E.R.) [START_REF] Wijnands | Multicast using Bit Index Explicit Replication[END_REF] was designed to eliminate this complexity, and to enable lightweight internetwork multicast -with the ambition being that intermediate routers maintain no flow state, other than that of an existing unicast routing table, and that intermediate routers are not involved

The authors are with École Polytechnique, 91128 Palaiseau, France, emails: {Yoann.Desmouceaux, Thomas.Clausen, Juan-Antonio.Cordero-Fuertes, Mark.Townsley}@polytechnique.edu.

Y. Desmouceaux and W. M. Townsley are also with Cisco Systems Paris Innovation and Research Laboratory (PIRL), 92782 Issy-les-Moulineaux, France, emails: {ydesmouc,townsley}@cisco.com. in group management. The key idea in B.I.E.R., which is detailed in the below, is that the source of a multicast data packet encodes the set of destinations (i.e., the members of the group) as a bit-string, and includes this bit-string in the header of each multicast data packet. Intermediate routers only need to be able to interpret that bit-string -leaving group management (if any) a matter for only the clients and the source. A proposal to increase the resiliency of multicast distribution with B.I.E.R. or B.I.E.R.-TE 1 with fast re-route mechanisms is introduced in [START_REF] Braun | Performance comparison of resilience mechanisms for stateless multicast using bier[END_REF].

A. Bit-Indexed Explicit Replication (B.I.E.R.) B.I.E.R. [START_REF] Wijnands | Multicast using Bit Index Explicit Replication[END_REF] is a multicast mechanism wherein the source of a multicast data packet explicitly identifies and indicates the set of destinations by way of inserting a destination bit-string into each multicast data packet. Each bit in the destination-bit-string corresponds to a destination in the network towards which -if the bit is set -the multicast data packet will be forwarded. Upon receipt of a multicast data packet, a B.I.E.R. router consults its unicast routing table in order to identify those interfaces over which copies of the received multicast data packet are to be sent, so as to follow the shortest path to each destination. When sending the multicast data packet over an interface, the B.I.E.R. router will clear all bits in the destination bit-string, except for those destinations for which the shortest path is via this interface. B.I.E.R. thus offers multicast as a network service, by way of using (but, not constructing) a shortest-path source-tree, rooted in the source of each multicast data packet. A B.I.E.R. router requires neither per-group nor per-flow multicast forwarding state, thus there is also no multicast group maintenance signalling: every group exists a priori, by way of the destination bit-string and the unicast routing table. The only requirements for a router participating in B.I.E.R. multicast that it runs an (any) unicast routing protocol, and is able to perform the bit#→IP mapping.

The destination bit-string is a substitution (or, dictionary) coder: the position of a set bit maps to a destination IP address. The precise way in which the dictionary is constructed is of no algorithmic significance, although it is interesting to note that if coupled with destination address assignment, it is possible to make this a simple mapping function: a simple example is to use the bit number as the value of a well defined octet in an IPv6 address <head-bits>:bit#:<rest-of-address>.

The way in which the destination bit-string is carried in each multicast data packet is also without algorithmic significance, though several options exist. If address assignment and number of destinations permit, the destination bitstring can be encoded as part of the destination IPv6 address, e.g., <head-bits>:bit-string:<rest-of-address>in which case the destination bit-string incurs no extra over-thewire overhead. Alternatively, the destination bit-string can be carried as an IPv6 extension header -which does incur extra octets in each multicast data packet, but at the same time allows an unlimited number of destinations, and is independent from any address assignment constraints or policies.

B. Statement of Purpose

The original B.I.E.R. specification [START_REF] Wijnands | Multicast using Bit Index Explicit Replication[END_REF] emphasises the flexibility provided by B.I.E.R. at the flow level, allowing for adding to and removing from the set of destinations of a flow without the need of building multicast trees and maintaining flow state in the routers. It is possible to take this one step further, to modifying the set of destinations on a per-packet basis, and to do so entirely without incurring any additional overhead.

This flexibility can be used to develop efficient reliable multicast: if the source of a multicast data packet is informed as to the set of destinations, to which a retransmission is required, it can use B.I.E.R. for minimising the traffic footprint of this retransmission: set the bit-string so as to contain only the destinations affected by a multicast data packet loss, thus the retransmission will be forwarded only along the shortest path tree covering the source and these destinations.

This paper studies this use of B.I.E.R. for reliable multicastand, compares this "reliable B.I.E.R." to two reliable multicast references: (i) the mechanisms known from e.g., NORM [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF], in which the source -when informed about a destination in the multicast group being affected by a multicast data packet losswill retransmit the multicast data packet to all destinations, and (ii) retransmission by way of unicast(s) to those destinations affected by a multicast data packet loss: this is for instance the case in RMTP [START_REF] Paul | Reliable multicast protocol (rmtp)[END_REF], if the number of affected destinations is below a given threshold.

Figure 1 illustrates the intuition that when faced with a multicast data packet loss (figure 1a), a NORM-style retransmission from the source and to the entire multicast group (naturally) will impose a load on all links in the multicast tree, regardless of if they lead to destinations affected by a multicast data packet loss (figure 1b). Unicast retransmissions (figure 1c), while traversing only the shortest-path tree between the source and the destinations affected by a multicast data packet loss, may cause the same multicast data packet to be retransmitted across the same link multiple times -whereas B.I.E.R. utilises only the shortest path tree between the source and the destinations affected by a multicast data packet loss, with each packet only retransmitted across the same link once (figure 1d). This paper formalises a simple, reliable, multicast mechanism using B.I.E.R., and examines if the suggested intuition holds -and in which conditions.

To that purpose, network simulations are conducted, and an analytical model is developed.

C. (Semi-)Reliable Multicast

While the term "reliable" is used throughout this paper, and is generally used in literature, it is perhaps more realistic to describe the attained multicast network services as semi-reliable. For example, maintaining a retransmission buffer (regardless if centralised at the source or distributed / peer-based) indefinitely is hardly feasible -nor will excessive retransmissions necessarily increase the overall success rate across heavily congested paths. Therefore, this paper will not consider mechanisms whereby a source adapts its sending rate to the worst destination; rather, it will assume that the source sends a stream at a fixed rate (e.g., a live broadcast media stream), and that destination applications might decide to give up on certain packets -if they are behind heavily congested links, and/or if they no longer would need the packet after retransmission.

D. Related Work

While never widely deployed as an inter-networking service, several reliable multicast protocols have been developed [START_REF] Popescu | A survey of reliable multicast communication[END_REF]. "Log-Based Receiver-reliable Multicast" (LBRM) [START_REF] Holbrook | Log based receiver reliable multicast for distributed interactive simulation[END_REF] uses a log server for caching packets sent by the source, and which also reacts to requests for retransmissions. A hierarchical architecture is suggested: a destination that has not received a packet will first solicit retransmission from a local log server -and, only if that fails, solicit a primary log server. In the "Reliable Multicast Transport Protocol" (RMTP), [START_REF] Paul | Reliable multicast protocol (rmtp)[END_REF] proposes a hierarchical architecture, wherein intermediate routers in the multicast tree, will contribute retransmissions in case of isolated losses, but with global recovery handled by the source. [START_REF] Floyd | A reliable multicast framework for light-weight sessions and application level framing[END_REF] introduces "Scalable Reliable Multicast" (SRM), which uses receiver-based reliability (receivers detect losses and request retransmissions) combined with low-rate multicast by every member to report the highest sequence number received. The "Tree-based Multicast Transport Protocol" (TMTP) [START_REF] Yavatkar | A reliable dissemination protocol for interactive collaborative applications[END_REF] is another instance of a reliable multicast protocol, wherein destinations are grouped in a tree of different domains, within which local recovery can be performed.

The IETF2 standardised "Negative-acknowledgment Oriented Reliable Multicast" (NORM) [START_REF] Bormann | NACK-Oriented Reliable Multicast (NORM) Transport Protocol[END_REF], using NACKs and source-based retransmissions to attain reliability. NORM also proposes redundancy and recovery by way of Forward Error Coding (FEC) -either proactively, or in response to negative acknowledgements. A TCP-friendly congestion-control mechanism has been proposed in [START_REF] Macker | A tcp friendly, rate-based mechanism for nack-oriented reliable multicast congestion control[END_REF]. The IETF has also examined the "Pragmatic General Multicast" (PGM) protocol [START_REF] Gemmell | The pgm reliable multicast protocol[END_REF], which uses negative acknowledgements and local repairs.

In the context of data-centers, [START_REF] Li | Reliable multicast in data center networks[END_REF] proposes the end-host based protocol "Reliable Data Center Multicast" (RDCM): through a central controller, RDCM explicitly builds a multicast tree, and a multicast-tree-aware backup overlay, for data dissemination. Retransmissions are performed on a peer-to-peer (unicast) basis: every receiver is responsible for providing, if needed, retransmissions for up to two of its peers.

The performance of (reliable, and otherwise) multicast protocols has been studied both analytically and through network simulations. For example, [START_REF] Bhagwat | Effect of topology in performance of reliable multicast communication[END_REF] develops an analytical model and carries simulations to study the performance of a generic reliable block-based multicast protocol using stop-and-wait, positive acknowledgements, and selective retransmissions. This model quantifies the number of transmission attempts until full reception, assuming independent losses in different links. [START_REF] Nonnenmacher | Reliable multicast: Where to use fec[END_REF] investigates the optimal placement of FEC in reliable multicast trees, by way of studying generic models of such trees (i.e., a single path common to all receivers, a set of completely separate paths to each receiver) and a refinement of the model developed in [START_REF] Bhagwat | Effect of topology in performance of reliable multicast communication[END_REF]. The number of successful receptions for different types of trees is studied by way of analysis and simulation in [START_REF]Performance modelling of reliable multicast transmission[END_REF], which also derives a generic approximation for the expected number of transmissions for reliable delivery.

Finally, models relying on TCP overlays for multicast have also been developed: [START_REF] Baccelli | The one-to-manv tcp overlay: A scalable and reliable multicast architecture[END_REF] introduces the One-to-Many TCP Overlay for reliable multicast services, as an application-level multicast alternative to IP reliable multicast; [START_REF] Basin | Source of instability in data center multicast[END_REF] studies the performance of TCP-based reliable multicast trees, built as a set of reliable point-to-point links, in data-centers.

E. Paper Outline

The remainder of this paper is organised as follows: section II details the use of B.I.E.R. for light-weight, reliable multicast. Section III and section IV evaluate the performance of this reliable multicast mechanism (denoted reliable B.I.E.R.) in different topologies and with different losses, by way of network simulations -and compare the performance with other reliable multicast mechanisms. Generalising the observations from the network simulations, section V provides an analytical study of reliable B.I.E.R. performance. Section VI concludes this paper.

II. RELIABLE B.I.E.R. -SPECIFICATION

To provide reliable multicast as a network service, transparent to applications, reliable B.I.E.R. is designed to operate as a shim-layer above the network layer, as depicted in figure 2. This reliable B.I.E.R. shim layer is, of course, upper-layer agnostic, and as such supports both transport layers (e.g., UDP) as well as IP-in-IP.

The reliable B.I.E.R. shim layer assumes a unique flow ID from the upper layer, and maintains for each flow ID a sequence number, monotonically increased for each new packet being handed by the upper layer. The tuple (flow ID, sequence number) allows uniquely identifying each original multicast data packet in the network, identifying when a multicast data packet is received out of order, etc. For many transport layers, the flow ID would be a hash of the tuple (protocol number, source IP address, source port), whereas for more specific transport layers a transport-layer-specific identifier could be used (e.g., the session ID for QUIC [START_REF] Hamilton | QUIC: A UDP-Based Secure and Reliable Transport for HTTP/2[END_REF]).

For each outgoing multicast data packet, the reliable B.I.E.R. shim layer takes a destination set, rather than a single destination IP address, from the upper layer -and compresses this into the destination-bit-string. The destination-bit-string and the sequence number comprise the reliable B.I.E.R. header, to be included in each multicast data packet. The precise form of the reliable B.I.E.R. header has no algorithmic significance -but in an IPv6 context can, for instance, take the form of a destination options extension header.

For each incoming multicast data packet, the reliable B.I.E.R. shim layer at each destination will inspect the sequence number to detect losses, and signal losses by way of sending negativeacknowledgements (NACKs) from destinations towards the source. Having this signalling only involve the end-points (source and destinations) serves, in part to run the protocol over any "standard" set of B.I.E.R. routers doing best-effort forwarding 3 , and in part to facilitate deployment (only the end-points need to agree on parameters, for example). As in other reliable multicast protocols, e.g., [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF], [START_REF] Gemmell | The pgm reliable multicast protocol[END_REF], NACKs are used in order to avoid an "ACK storm". Of course, for very large error rates or errors affecting a wide range of destinations, this may lead to a "NACK storm". Such a storm of control traffic could be avoided e.g., by allowing intermediate routers to aggregate NACKs before forwarding them upwards, without changing the end-to-end behaviour specified in this paper.

For the purpose of this paper, a slightly modified socket API is used -specifically, allowing the sender to provide the set of destinations (rather than a single multicast group address) to which a multicast data packet is to be forwarded.

A. Source Operation

A reliable B.I.E.R. source operates as detailed in algorithm 1. On sending a packet through a socket, the reliable B.I.E.R. shim layer caches a copy of the packet, with which it associates a

p C[S] ← p, R[S] ← 0, T [S] ← ∞ delete C[S -w], R[S -w], T [S -w] garbage collection S ← S + 1 for s ∈ C with T [s] ≤ Tnow do perform retransmits p ← C[s] retrieve cached packet insert reliable B.I.E.R. header with flow F , seq s insert B.I.E.R. header with bistring R[s] transmit p R[s] ← 0, T [s] ← ∞ end for end for for each received NACK packet with flow F , seq s, bit b do if s ∈ C then R[s] = R[s] OR 2 b add b to the retransmit bitstring T [s] ← min{T [s], Tnow + ∆tagg}
schedule retransmit end if end for B.I.E.R. retransmit bit-string with all bits cleared, and a timer of duration ∆t agg , where ∆t agg represents a window of time between the first NACK is received and a retransmission is made. Within this window, for each NACK received, the corresponding bit in the B.I.E.R. retransmit bit-string is set; at the end of this window, the cached multicast data packet is retransmitted with the destination-bit-string set to the associated B.I.E.R. retransmit bit-string. This permits aggregation of retransmissions to multiple destinations in a single B.I.E.R. packet, thus potentially reducing the number of transmissions of this packet. If after retransmission, a subsequent NACK for the same packet is received, a new ∆t agg window is opened and the aggregation mechanism is restarted.

B. Destination Operation

A reliable B.I.E.R. destination operates as described in algorithm 2. In short, a destination will send a NACK to the source when it detects that a packet was lost -a packet being deemed lost when one of its successors is received 4 . If necessary, NACKs for a lost packet are then retransmitted regularly by means of a timer, until a retransmission is received.

More precisely, for each incoming multicast data packet, the reliable B.I.E.R. shim layer parses the reliable B.I.E.R. header and either hands it off to the upper layer, or (if received out-oforder) records it in a buffer, C. For each multicast data packet that (1) is received out-of-order, and (2) creates a "hole" (i.e., a set of missing packets between two consecutively received packets) in C, the reliable B.I.E.R. shim layer adds the element(s) corresponding to this "hole" in the list of lost packets, L. Each element in L is identified by the sequence number, s, of the corresponding lost packet, and is associated with a timer,

[S] ← p L ← L \ {S}, delete T [S], N [S] end if
schedule NACK for packets between n and S for seq from n to S with seq /

∈ L ∪ C do L ← L ∪ {seq}, T [seq] ← Tnow, N [seq] ← 0 end for end if send appropriate NACKs for seq ∈ L with T [seq] ≤ Tnow do if N [seq] < l then send NACK with flow F , seq seq T [seq] ← Tnow + ∆tretry, N [seq] ← N [seq] + 1 else abort trying to recover this packet L ← L \ {seq}, delete T [seq], N [seq] C[seq] ← {}
put a dummy packet in the cache end if end for send pending recovered packets to application

while n ∈ C do p ← C[n], delete C[n] transmit p to application n ← n + 1 end while end for a NACK count, N [s].
For each element of L, a NACK is sent towards the source. The NACK contains a reliable B.I.E.R. header wherein the included bit-string indicates the bit of the client sending the NACK 5 , and the sequence number corresponding to the lost packet. Then, the NACK count is incremented, and a new timer for this packet is set to expire after ∆t retry (a configurable retry delay). Upon timer expiration, if no retransmission has been received, and if the NACK count is below a configurable limit l, another NACK is sent and the process is restarted. When the retransmission count reaches l, it is assumed that the source is not able to offer timely retransmission (for instance, due to congestion on the path), and the destination gives up trying to request. This achieves a "poor-man's congestion control", by limiting the number of possible retransmission of a multicast data packet.

C. Parameter Discussion

The value of ∆t agg directly influences the global behaviour of reliable B.I.E.R.:

• when ∆t agg = 0, no aggregation is performed, and the protocol degenerates to individual, unicast-based, retransmissions;

• when ∆t agg > 0, aggregation is enabled: the greater ∆t agg , the greater the probability of aggregating retransmissions, but at 5 One reason for including a bit-string is, that this allows the originator to create the and B.I.E.R. retransmit bit-string by a simple OR operation of received NACKs. • when ∆t agg = RT T max -RT T min , maximum aggregation is enabled; higher values of ∆t agg will not provide further benefit.

Determination of the value of ∆t agg thus requires taking into account RTT variations and error probability along the different paths, as well as the sensitivity of the application to delay: it thus corresponds to a policy decision. Furthermore, to make sure that each destination sends at most one NACK for each multicast data packet (re)transmission failure, ∆t retry should be greater than ∆t agg + RT T max .

III. DATA-CENTER SIMULATIONS

Regardless of the underlying network topology, content delivery with B.I.E.R. from a given source will follow (but not construct) a shortest-path tree. Thus for this first set of simulations, reliable B.I.E.R. is tested on a simple tree-topology, modelling a data-center, depicted in figure 4: a core router, connected to two aggregation routers -each of which is connected to two Top-of-Rack switches (ToR), and with each rack hosting 10 machines.

The purpose of the set of tests in this section is to examine if the intuition, introduced in section I-B and depicted in figure 1, holds: that using B.I.E.R. (rather than multicast or unicast) for retransmissions can yield a measurable and significant diminution of the traffic footprint.

To this end, three different scenarios are constructed around the same physical topology depicted in figure 4. These scenarios serve to explore how reliable B.I.E.R. performs both when losses are spatially located and when they are not, specifically: Uncorrelated localised losses, where background traffic is present inside the leftmost rack, i.e., where both the source and destination of the background traffic are members of the leftmost rack, saturating individual links between the ToR switch and the machines in the rack, and thus affecting these machines individually -but with the rest of the data-center unaffected. This scenario is studied in section III-B. Correlated localised losses, where background traffic is present inside the two leftmost racks, i.e., where source and destination are members of the two leftmost racks. This saturates the incoming links to the two leftmost ToR switches, and thus will affect destinations on all machines within a rack, together -again, with the rest of the data-center unaffected. This scenario is studied in section III-C. Bursty, non-localised losses, where losses are not related to localised background traffic, but are produced by a loss model in each individual link. This scenario is studied in section III-D.

A. Simulation Parameters and Setup

The B.I.E.R. shim layer, described in section II, has been implemented in NS-3 [START_REF] Riley | The ns-3 network simulator[END_REF], with the bit#→IP-address mapping assumed a priori available in all routers, as discussed in section I-A. UDP is used as transport protocol, and B.I.E.R. and reliable B.I.E.R. headers are implemented as IPv6 extension headers. The reliable B.I.E.R. parameters from section II are chosen as follows: ∆t agg = 7ms (NACK aggregation delay), ∆t retry = 15ms (NACK retransmission timer), and l = 3 (retransmission limit). All links are homogeneous, point-to-point, with 1 Gbps capacity, with an MTU of 1500 octets and a prop- agation delay of 1 µs. Network interfaces all have tail-drop queues of size 512 packets. The links themselves are lossless -except for the simulations in section III-D, which considers link-losses according to a Gilbert-Elliot loss model [START_REF] Elliott | Estimates of error rates for codes on burst-noise channels[END_REF]. For these simulations, the multicast data packet source is attached to the core router, which generates a constant bit-rate reliable B.I.E.R. flow of 500 Mbps. All 40 machines are destinations for this flow. This scenario can be considered to represent e.g., broadcasting of a live media, where a constant transmission bitrate has to be sustained, and where a retransmitted multicast data packet is of no value if received "too late". Thus, some packets may not be received by all destinations, and the ratio of packets successfully received after retransmissions (the delivery ratio) will be a metric of interest -as will the network load of the different links in the network, as well as the sum of traffic over all links in the network (the traffic footprint).

When unicast background traffic is introduced in the network (for the simulations in section III-B and III-C), it takes the form of 19 UDP flows of a constant bit-rate of 500 Mbps. Each flow has a randomly selected source and destination. These flows are injected into the network in a staggered fashion, starting every 200 ms, and each lasting until the end of the simulation. The simulations in section III-B and III-C differ in the domain from which the (source, destination) pairs are randomly chosen.

As a reference, reliable B.I.E.R. (i.e., using B.I.E.R. for retransmissions, as per this paper) is compared with multicast (as in e.g., [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF]) and unicast (as in e.g., [START_REF] Paul | Reliable multicast protocol (rmtp)[END_REF]) retransmissions of NACKed multicast data packets.

B. Uncorrelated, Localised Losses

For this set of simulations, UDP background flows are introduced with sources and destinations both within the leftmost rack (figure 4) as described in section III-A. This will saturate some of the links between the ToR router and the individual machines, leading to packet losses in the "downwards" interfaces of the leftmost ToR router. B.I.E.R. aggregation will thus only happen when, by chance, two or more clients detect a packet loss (and thus generates NACKs) at the same time.

Figure 3 depicts the results of a 4-second simulation run, specifically the usage of the two core links, the delivery ratio, and the distribution of the number of clients in B.I.E.R. retransmissions. A first observation from figure 3b is that, with multicast retransmissions, the rightmost aggregation link carries unnecessary traffic, unlike unicast and B.I.E.R. retransmissions. It can also be observed that multicast retransmissions saturate the core links faster than the two other mechanisms: this is because excess retransmissions produce additional congestion, leading to additional losses of original transmissions, in turn leading to additional retransmissions.

Comparing with unicast retransmissions, the use of B.I.E.R. retransmissions further minimises the traffic footprint: even with uncorrelated losses, when using B.I.E.R., retransmissions are aggregated when several clients do not receive the same packet. This is illustrated in figure 3d, which depicts the Cumulative Distribution Function (CDF) of the number of simultaneous clients to which a B.I.E.R. retransmission is performed: ∼ 10% of B.I.E.R. retransmissions are destined for multiple (≥ 2) destinations, and thus benefit from aggregation. This allows a further reduction of link usage, as depicted in figure 3b.

A conclusion to draw from these simulations is that, in case of localised losses, B.I.E.R. and unicast retransmissions are preferable to multicast retransmissions -due to the latter incurring unnecessary traffic on links in paths unaffected by losses. Another conclusion is, that when multiple destinations do not receive a given multicast data packet, B.I.E.R. retransmissions allow aggregation -an advantage over unicast retransmissions.

C. Correlated, Localised Losses

For this set of simulations, UDP background flows are introduced with sources and destinations within the two leftmost racks (figure 4) as described in section III-A. This will, again, saturate some of the links -this time, in addition to between the individual machines and the ToR routers, also between the ToR routers and aggregation routers. A loss on one of these links will affect all the destinations within a rack.

Figure 5 depicts the results of a 4-second simulation. For the same reasons as in section III-B, multicast retransmissions cause unnecessary traffic on the right "half" of the data-center (see figure 4) -and causes earlier saturation on the left core link.

A single lost multicast data packet will, in this scenario, typically fail to be received by several destinations, therefore unicast retransmissions will generate a larger traffic footprint as compared to B.I.E.R. retransmissions. With a link capacity of 1 Gbps and a multicast flow of 0.5 Gbps, the link between the source and the core router can sustain the unicast retransmission load only when each multicast data packet is, on average, retransmitted no more than once. Beyond that, the link becomes saturated with retransmissions, thus preventing "legitimate" original transmissions to succeed. This explains why uni-cast recovery incurs a lower delivery ratio, as depicted in figure 5c. This is also why the link usage on the first core link is lower for unicast retransmissions than for B.I.E.R. retransmissions, as depicted in figure 5a.

The distribution of the number of simultaneous clients to which a multicast data packet is retransmitted is depicted in figure 5d: ∼ 46% of B.I.E.R. retransmissions are destined for multiple destinations, and thus benefit from aggregation.

D. Unlocalised, Bursty Losses

The simulations on sections III-B and III-C illustrate the benefits of B.I.E.R. retransmissions when losses are spatially localised. Instead of creating background UDP flows, this section assumes uncontrolled, exogenous congestion in the data centermodelled by a Gilbert-Elliott loss model [START_REF] Elliott | Estimates of error rates for codes on burst-noise channels[END_REF] on all links. This model is used to model bursty transmissions, and [START_REF] Hasslinger | The gilbert-elliott model for packet loss in real time services on the internet[END_REF] shows that it accurately describes packet losses in the Internet. In sum, the Gilbert-Elliott loss model prescribes that a link can be in either a good or bad state. In good state, the link is ideal (no losses), whereas in bad state, the probability of a transmission to be successful (i.e., to not be lost) is h. For each packet to be transmitted over a link, the state of the link may change: from bad to good with a probability of r, and from good to bad with a probability p.

For the purpose of the simulations in this section, the success probability in the bad state is set to h = 0.5, and the transition probability from bad to good to r = 0.01 (i.e., the expected loss burst duration is 100 packets). The transition probability from good to bad, p, is set so that the average packet loss ratio is α, according to equation (4) in [START_REF] Hasslinger | The gilbert-elliott model for packet loss in real time services on the internet[END_REF]: p = rα 1-h-α = 0.01α 0.5-α . In order to quantify the sensitivity of the system to different congestion levels, 19 simulations are run, for α ∈ {0.001, 0.002, . . . , 0.01, 0.02, . . . , 0.1}.

Figure 6 depicts the simulation results. A stability limit (α = 6% for B.I.E.R. and multicast, α = 0.9% for unicast) can be observed in figure 6a. Above this limit, retransmissions compete with original transmissions over the link between the source and the core router, causing some of these original transmissions to be lost, requiring additional retransmissions. This, then, causes the delivery ratio to deteriorate, as depicted in figure 6c. Thus, for this stability metric, reliable B.I.E.R. shows superior results as compared to unicast retransmissions, while behaving similarly as compared to multicast retransmissions. A conclusion to draw from these simulations is that, when losses are unlocalised and bursty, B.I.E.R. retransmissions are vastly preferable to multicast retransmissions, in terms of global traffic footprint and also vastly preferable to unicast retransmissions, in terms of avoiding saturation of individual links.

Finally, the CDF of the number of simultaneous clients to which a multicast data packet is retransmitted is depicted in fig- ure 6d, which shows that when α ≥ 6%, more than 50% of B.I.E.R. retransmissions are destined for multiple destinations, and thus benefit from aggregation. Fig. 9. Network topology (picture from [START_REF]Internet Topology Zoo[END_REF]).

E. Influence of the Aggregation Timer

As described in section II-C, increasing the aggregation timer ∆t agg (i.e., the amount of time during which the source collects NACKs for a given packet before retransmitting) directly reduces the induced network traffic (since aggregating more NACKs means that the corresponding retransmission is sent to more clients), at the cost of packets being delivered later to the application. In order to quantify this phenomenon, an experiment using the scenario of section III-D is conducted. For two target loss probabilities α = 1% and α = 0.8% (slightly above and below the stability limit observed in figure 6a, respectively), different values for the parameter ∆t agg are used, ranging from 25 µs to 10 ms.

Figure 7a depicts the usage of the link between the source and the core router, averaged above the duration of the simulation, with α = 1%. It is interesting to observe that enabling NACK aggregation (i.e., making ∆t agg = 0) causes a substantial improvement in performance. In particular, the use of any non-zero NACK aggregation delay leads to a significant benefit in terms of link usage: the smallest non-zero explored value (∆t agg = 25 µs) makes the link usage drop from 1 Gbps (with ∆t agg = 0) to 645 Mbps. Further increases of the aggregation delay lead to minor reductions of link usage (e.g., from 645 Mbps for ∆t agg = 25 µs, to 615 Mbps for ∆t agg = 10 ms), at the cost of linearly increasing the delay of retransmitted packets by ∆t agg . Figure 7b depicts the results for α = 0.8%: a similar pattern can be observed, with a lower amount of traffic for unicast retransmissions -due to α being below the stability limit.

IV. ISP TOPOLOGY SIMULATIONS

Sections III-B, III-C, and III-D illustrated the benefits of reliable B.I.E.R. for reducing the traffic footprint in strict tree topologies such as those from data centers -begging the question of if these benefits are dependent on these topologies. In order to answer that question, this section presents simulations of a real (not just realistic) topology, specifically that of BT Eu-rope (Aug. 2010) from [START_REF]Internet Topology Zoo[END_REF] (see figure 9). Note that while the topology used comes from a real deployment, this simulation does not claim to reproduce realistic Internet traffic: the goal is to explore the behaviour of reliable B.I.E.R.. This topology consists of 24 routers, connected by 1 Gbps links. It is assumed that the unicast routing protocol has converged and each router has perfect shortest paths to all other routers. For the purpose of this simulation study, the source node is attached to router 17 (in London), and a destination is attached to each of the other 23 routers. The simulation parameters and multicast traffic flow parameters are as per section III-A. Background traffic flows are also as per section III-A, noting that router 17 is never chosen as source or destination for a background flow.

Figure 8a depicts the link usage between the source and router 17 -revealing that unicast retransmissions rapidly saturate the link, and that multicast retransmissions saturate the link faster than B.I.E.R. retransmissions. Figure 8b depicts the link usage of the link between router 17 (to which the source is attached) and router 5 (one of its directly adjacent peer routers), noting that it is up to twice as high for multicast retransmissions, as it is for both B.I.E.R. retransmissions and for unicast retransmissions. The link load for unicast retransmissions on this link is lower than for reliable B.I.E.R.. The reason for this is, that as unicast retransmissions already saturated the link between the source and router 17 (figure 8a), fewer unicast retransmissions make it onto the link between router 17 and router 5 (figure 8b), causing an overall lower data delivery ratio when using unicast retransmissions. This is depicted in figure 8c, which also indicates a higher data delivery ratio for B.I.E.R. retransmissions than for multicast retransmissions.

The distribution of the number of simultaneous clients to which a multicast data packet is retransmitted is depicted in figure 8d: ∼ 71% of B.I.E.R. retransmissions are destined for multiple destinations, and thus benefit from aggregation.

The conclusion to draw from these simulations is, that the results obtained with a data-center topology (section III) also can be valid for other topologies.

V. RELIABLE B.I.E.R. PERFORMANCE ANALYSIS

The simulations in sections III and IV illustrate the performance benefits of B.I.E.R.-retransmissions for reliable multicast, both when faced with (i) rare, isolated losses, and with (ii) correlated, frequent losses in traffic-intensive environments. Specifically, reliable B.I.E.R. was observed to result in a substantially lower traffic footprint in the simulated scenarios, with equivalent or better multicast data packet delivery ratios than when using multicast and unicast retransmissions.

This section aims at generalising these observations, by way of formulating an analytical model of arbitrary tree topologies -and using this model to, analytically, quantify the number of successful and failed transmissions 6 necessary for a reliable multicast operation to succeed (i.e., for all destinations to have received a copy of a multicast data packet). Section V-B derives an exact expression of this as M B

[i] , for reliable B.I.E.R. -and for comparison, M m

[i] and M u [i] for when using multicast and unicast 6 Colloquially speaking, to count the blue arrows in figure 1.

retransmissions, respectively. These exact expressions, however, become mathematically intractable for large trees, thus section V-C develops a first-order approximation of the average traffic footprints of reliable multicast using B.I.E.R., multicast, and unicast retransmissions, respectively.

A. Model, Assumptions and Definitions

Network links have an associated packet loss probability 7α ∈ [0, 1]. As illustrated in section 1, multicast transmissions and retransmissions (regardless of if B.I.E.R., multicast, or unicast retransmissions) span a tree, rooted in the source. For describing these trees, the following notation is introduced: routers and destinations are indiscriminately termed node, and each node is uniquely labeled, with the path from the root of the tree to it8 ; [[i], j] denotes the j-th child of node [i], and the term "the subtree [i]" refers to the subtree, which is rooted in node

[i]. Finally, the set of children of [i] is denoted c([i]): c([i]) = {[[i], 1], [[i], 2], . . . }
This analysis assumes retransmissions by the source until all destinations have received a copy of the multicast data packet, and that the source collects all generated NACKs before retransmitting a packet (i.e., l = ∞, no NACKs are lost, ∆t agg ≥ RT T max -RT T min , ∆t retry ≥ ∆t agg + RT T max ). It quantifies, under these assumptions, (1) the number of retransmissions of a multicast data packet that are made by the source, and (2) the total number of transmissions in the network, until all clients have received (at least) one copy of the multicast data packet.

Definitions: Given a node [i] and its child [[i], j], and with reference to figure 11: • T [[i],j] : is the number of attempts from node [[i], j], i.e., number of times that [[i], j] must transmit copies of a multicast data packet to its children, to ensure that all destinations in its subtree receive the multicast data packet. If

[[i], j] is a leaf, then by convention T [[i],j] = 1. • X [i]→j : is the number of transmissions made by [i] over the link ([i], [[i], j]), needed to ensure that node [[i], j] receives the T [[i]
,j] copies of the multicast data packet.

• M [i] : Number of packets transmitted inside a subtree [i] to ensure that all destinations receive a copy, where indicates the considered variant (B for B.I.E.R., m for multicast, u for unicast). If [i] is a leaf, then by convention

M [i] = 0.
The number of attempts by [i] is the worst of the number of transmissions on all links ([i], [[i], j]):

T [i] = max [[i],j]∈c([i]) X [i]→j (1)
B. Computation of T [i] , X [i]→j , and

M [i]
Each node [[i], j] needs to receive T [[i],j] copies of the multicast data packet from its parent, [i]. For each of these, the number of transmissions over the link ([i], [[i], j]) until the copy is [i]

[[i], k] [[i], j]
transmission attempts

X [i] j T [i] X [i] k M [i] [[i], k] M [[i], j] M Parent of [i] successful transmissions
P r(X [i]→j = x|T [[i],j] = k) = x -1 k -1 α x-k (1 -α) k (2)
and the number of attempts from node [i], T [i] is:

P r(T [i] = k) = [[i],j]∈c([i]) P r(X [i]→j ≤ k) - [[i],j]∈c([i]) P r(X [i]→j ≤ k -1) (3)
Equations ( 2) and (3) allow computing the probability density function (PDF) for X [i]→j and T [i] recursively, from the leaves towards the root, using the convention that for a leaf,

T [i] = 1.
M B [i] = [[i],j]∈c([i]) (X [i]→j + M B [[i],j] ) (4)
U [i]→[[i],j] = T [i] -X [i]→j f =1 (1 + Y f [i]→j F f [[i],j] ) (5)
where the mean number of packets sent in a multicast flood from [i], E(F [j] ), can be recursively computed as follows (with E(F [j] ) = 0 for every leaf [j]):

E(F [i] ) = [[i],j]∈c([i]) (1 + (1 -α)E(F [[i],j] )) (6)
U [i]→[[i],j] ) is M m [1] = 16.
From this, the total number of packets sent in a subtree [i] until all of its destinations receive a copy, M m

[i] , can be computed recursively. It corresponds, for each child [[i], j], to the number of transmissions over the link

[i] → [[i], j] required by [[i], j],
plus the number of packets sent inside [[i], j] so as to cover all destinations, plus the unnecessary multicast packets originating from [i]:

M m [i] = [[i],j]∈c([i]) X [i]→j + M m [[i],j] + U [i]→[[i],j] (7)
Proposition 2 indicates a simple way to compute the average traffic footprint for multicast retransmissions, using

T [i] and F [i] .
Proposition 2 Let [i] be a node in the tree. With multicast retransmissions, the mean number of packets sent until all destinations in [i] obtain a copy can be computed as such:

E(M m [i] ) = E(T [i] )E(F [i] ) (8)
Proof: See appendix -A.

2 Figure 12 provides a detailed example of multicast reliable transmission, with corresponding values for T

[i] , X [i]→j , U [i]→[[i],j] , and M m [i] variables. B.3 Unicast retransmissions: M u [i]
With unicast retransmissions, losses experienced by each destination are treated individually by the source. Given the loss of a multicast data packet (sent by the source [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF]) at a destination [c], connected to the source in d([c]) hops, the number of retransmissions from the source before successful delivery of the packet to [c] is a random variable, R [1]→[c] , whose mean is described in proposition 3.

Proposition 3 The mean value of R

[1]→[c] is: E(R [1]→[c] ) = 1 -(1 -α) d([c]) α(1 -α) d([c]) (9)
Proof: See appendix -B. 2

The previous proposition allows to compute the total number of multicast data packets sent from the source with the unicast reliability mechanism, M u [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] . This variable corresponds to the multicast data packets sent in the first multicast flood, plus, for each destination that did not receive a copy of the multicast data packet, the number of unicast retransmissions needed until the copy is successfully received. Proposition 4 expresses M u

[1] and provides a closed expression for its mean, E(M u [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] ). Proposition 4 Let C be the set of destinations, and let F [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] be the (random) set of destinations that have successfully received a copy after the first multicast flood by [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF]. Then, the number of multicast data packets sent from the source, under unicast retransmissions, until each destination has received a copy is:

M u [1] = F [1] + [c]∈C 1 {[c] / ∈F [1] } R [1]→[c] (10)
and its mean is:

E(M u [1] ) = E(F [1] ) + [c]∈C (1 -(1 -α) d([c]) ) 2 α(1 -α) d([c]) (11)
Proof: From the definition of F [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] , equation [START_REF] Floyd | A reliable multicast framework for light-weight sessions and application level framing[END_REF] holds. The mean number of multicast data packets sent in the network is therefore:

E(M u [1] ) = E(F [1] ) + [c]∈C P r([c] / ∈ F [1] )E(R [1]→[c] )
And since P r(

[c] / ∈ F [1] ) = 1 -(1 -α) d([c]
) , the result in ( 11) is obtained by using equation [START_REF] Holbrook | Log based receiver reliable multicast for distributed interactive simulation[END_REF]. 2

B.4 Computational Example

For trees of small height, it is possible to recursively derive the average number of transmissions needed in the network in order to deliver a multicast data packet to all destinations, in an exact manner, for B.I.E.R. reliability (proposition 1 and equation (4)), multicast reliability (proposition 2) or unicast reliability (proposition 4). As an example, figure 13 reports the results of this computation, for a binary tree of height 2 (as in figure 1): as expected, reliable B.I.E.R. incurs the lowest overhead.

C. Total Traffic Approximation

Directly computing the traffic footprint is intractable when the depth of the tree is important. Therefore, this section provides a first-order approximation of the number of packets transmitted in the network before all destinations receive a copy, under the assumption that losses are rare (i.e., α → 0, as in [START_REF]Performance modelling of reliable multicast transmission[END_REF]), for arbitrary trees and for each retransmission mechanism (reliable B.I.E.R., unicast retransmissions, multicast retransmissions).

For a link l of the tree, d(l) is the depth of l (d(l) = 1 for a link rooted at the source); L is the total number of links in the tree, and D is the average depth of a links in the tree:

D = 1 L l d(l).
C is the number of destinations, and ∆ is the average squared depth of a destination: ∆ = 1 C c d(c) 2 . Given these parameters, Theorem 1 describes first-order (for α) approximations of the number of transmissions in the network: Theorem 1 The average number of multicast data packets that need to be sent in the tree until all destinations have received a copy are, for reliable B.I.E.R. (M B [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] ), for multicast retransmissions (M m [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] ) and for unicast retransmissions (M u [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] ), given by the following approximation when α → 0:

     E(M B [1] ) = L + LDα + O(α 2 ) E(M m [1] ) = L + [L 2 -L(D -1)]α + O(α 2 ) E(M u [1] ) = L + [C∆ -L(D -1)]α + O(α 2 ) (12)
Proof: See appendix -C. 2 When there are no losses (α = 0), the transmission of one multicast data packet yields L packets in the tree (one per link), whichever retransmission mechanism (B.I.E.R., multicast or unicast) is used. In addition to these L packets, with B.I.E.R. retransmissions, the traffic is approximately LDα packets, as compared to approximately L 2 α packets for multicast retransmissions and approximately C∆α for unicast retransmissions (Theorem 1). The traffic due to unicast or multicast retransmissions can thus be orders of magnitudes bigger than the corresponding B.I.E.R. traffic, if the number of links and/or the depth of destinations is important.

D. Discussion

The accuracy and relevance of approximations from theorem 1 can be assessed against simulations in realistic tree topologies. Two examples are examined in this section: (1) reliable multicast over a datacenter-like topology as depicted in figure 4, and (2) multicast flows over fat-tree-like topologies [START_REF] Al-Fares | A scalable, commodity data center network architecture[END_REF].

The datacenter-like topology of figure 4 α → 0, retransmissions will incur a footprint of 177α packets for B.I.E.R., 510α packets for unicast, and 2079α packets for multicast. In order to quantify the quality of the approximation for this example, the means for M B [1] , M m [1] and M u [1] have been computed over 10 6 random samples, for different values of α with 0 ≤ α ≤ 1%. Figure 14 depicts the results of these simulations, as well as the linear approximation from theorem 1. For B.I.E.R. and unicast retransmissions, the approximation accurately fits the computed mean. For multicast retransmissions, the approximation is within a 6% error margin of the computed value.

For reliable multicast flows over fat-tree-like topologies, the root has k children, each having k/2 children, each also having k/2 children. For these trees, the parameters become: L = k + k 2 2 + k 3 4 , L × D = k + k 2 + 3k 3 4 , C = k 3 4 , ∆ = 9, allowing calculating the approximation of theorem 1. Table 1 depicts the approximate retransmission footprint for B.I.E.R., multicast and unicast retransmissions. It can be observed that unicast retransmissions exhibit a footprint approximately twice as high as B.I.E.R. retransmissions. The footprint for multicast retransmissions is at least one order of magnitude higher, and clearly does not scale with the number of clients.

VI. CONCLUSION

This paper has proposed a scalable network service offering efficient and reliable multicast. NACK-based, this network service uses B.I.E.R. (Bit-Indexed Explicit Replication) for ensuring that traffic (original transmissions and retransmissions, both) are forwarded over a minimal shortest path tree, requiring maintenance of neither per-flow nor per-group state by intermediate routers: the source will encode, for each (re)transmission of a multicast data packet, the precise destination set -be that every member of a given group, or those members having issued a NACK to request retransmission.

The performance of this network service is compared with "classic" reliable multicast mechanisms, where retransmissions are either unicast (to all destinations having sent a NACK, only) or multicast to all destinations in a given group (when a NACK for a multicast data packet was received from any destination).

Simulation studies in both data-center-like and in Internetlike topologies, and when faced with different loss models, show that the proposed B.I.E.R.-based reliable multicast network service is able to achieve reliability, while overcoming the two main shortcomings of these reference mechanisms: (i) contrary to multicast reliability, links not concerned by losses are not affected by retransmissions and (ii) contrary to unicast reliability, links concerned by losses do not unnecessarily carry multiple copies of the same packets.

Generalising from the simulation studies, an analytical model is presented, which quantifies the retransmission footprint incurred by the three mechanisms in any topology -and which shows that the B.I.E.R.-based reliable multicast network service incurs a consistently lower overhead.

Proof: by induction over the structure of the tree. If [i] is a leaf, then T [i] = 1 and the result holds with C [i] = 1, D [i] = 1. Otherwise, assume that [i] is not a leaf, and that the result holds for all children of [i]. Let [[i], j] be an arbitrary child of [i], and x ≥ 1. Using the induction hypothesis, and the fact that α ≤ 1:

P r(X [i]→j = x) = x k=1 P r(T [[i],j] = k) x -1 k -1 α x-k (1 -α) k ≤ x k=1 C [[i],j] (D [[i],j] α) k-1 x -1 k -1 α x-k (1 -α) k = C [[i],j] α x-1 x k=1 (D [[i],j] ) k-1 x -1 k -1 (1 -α) k

Fig. 1 .

 1 Fig. 1. Comparison of different reliable multicast mechanisms. In this example, two clients do not receive a packet and send a NACK to the source (a). Multicast retransmissions (b) will vainly incur traffic towards the clients that had successfully received the packet. With unicast retransmissions (c), identical packets will be transmitted on the same link. B.I.E.R. retransmissions (d) ensure that the traffic footprint is minimal.

Fig. 2 .

 2 Fig. 2. B.I.E.R. shim layer

Fig. 3 .Fig. 4 .

 34 Fig. 3. Uncorrelated localised losses experiment. B.I.E.R. retransmits vs unicast and multicast retransmits.

Fig. 5 .

 5 Fig. 5. Correlated localised losses experiment. B.I.E.R. retransmits vs unicast and multicast retransmits.

Fig. 7 .

 7 Fig. 7. Influence of ∆tagg: link usage between the source and the core router.

  source to router 17 link Unicast retransmissions, source to router 17 link Multicast retransmissions, source to router 17 link (a) Link usage, between the source and router 17 (London).

  example 1st hop link Unicast retransmissions, example 1st hop link Multicast retransmissions, example 1st hop link (b) Link usage, between router 17 (London) and router 5.

Fig. 8 .

 8 Fig. 8. ISP topology experiment. B.I.E.R. retransmits vs unicast and multicast retransmits.

  Figure 6bshows the aggregate traffic (the sum of traffic induced by transmissions and retransmissions over all links) for each of the values of α. While unicast retransmissions (in the stability zone) behave slightly worse than B.I.E.R. retransmissions, multicast retransmissions incur a substantial traffic footprint (of approximately 1.7× that of B.I.E.R. retransmissions, for α = 6%).

Fig. 10 .

 10 Fig. 10. Reliable B.I.E.R. examplified -solid blue arrows represent successful transmissions, dashed blue arrows represent unsuccessful transmissions, and dashed black arrows represent NACKs. A NACK is sent by two nodes (a) upon receipt of a subsequent packet in the stream. After retransmission (b), the last node still has not received a copy of the packet, and sends a second NACK upon timeout of ∆tretry (Algorithm 2). Figure (d) shows the total number of attempts T [i] at each node [i], and total transmissions X [i]→j at each link [i] → [[i], j]. The total number of packets sent in the tree (the sum of all X [i]→j ) is M B [i] = 11.

Fig. 11 .Proposition 1

 111 Fig. 11. Notation.

B. 1

 1 B.I.E.R. retransmissions: M B [i] When using B.I.E.R. retransmissions, M B [i] is the sum of the transmissions on each link ([i], [[i], j]) and the packets transmitted in each subtree [[i], j], i.e., :

Figure 10 B. 2

 102 Figure 10 provides a detailed example of a B.I.E.R. reliable transmission, with the corresponding values for T [i] , X [i]→j and M B [i] displayed in Fig. 10d. B.2 Multicast retransmissions: M m [i] The number of multicast data packets sent over a network with multicast retransmissions can be obtained by adapting the previously presented model (section V-B.1). Consider the transmission from a node [i] to a node [[i], j]: transmitted packets can be classified into two categories: (i) packets sent until the subtree [[i], j] is covered, and (ii) packets flooded by [i] inside the subtree [[i], j] after it has been covered. The latter packets come from retransmissions from the source [i] that are due to other subtrees [[i], k] having not yet been covered. Let U [i]→[[i],j] be the number of packets that fall into the second category. The number of floods is T [i] -X [i]→j (i.e., the number of times [i] transmits after [[i], j] has already received enough packets): index these floods with f ∈ [1, T [i] -X [i]→j ]. For each of these floods, let Y f [i]→j be a Bernoulli variable of parameter (1 -α) representing the success of transmission on the link [i] → [[i], j], and F f [[i],j] be a variable representing the number of packets flooded in the subtree [[i], j]. The number of unnecessary packets is then, for each of these floods, one packet (from [i] to [[i], j]) plus, if the transmission succeeded (i.e., if Y f [i]→j = 1), the number of packets F f [[i],j] resulting from a multicast flood sourced at [[i], j]:

Fig. 12 .

 12 Fig. 12. Example of multicast reliable transmission. In addition to the conventions of figure 10, green arrows represent unnecessary retransmissions. In the second attempt (b), node [[1], 1] floods one unnecessary packet. In the third attempt (c), the root floods three unnecessary packets, and node [[1], 2] floods one unnecessary packet. Figure (d) shows the total number of attempts T [i] at each node [i], total transmissions X [i]→j at each link [i] → [[i], j], and the total number of unnecessary packets U [i]→[[i],j] flooded by each node [i] in the subtree [[i], j]. The total number of packets sent in the tree (the sum of all X [i]→j and U [i]→[[i],j] ) is M m [1] = 16.

Fig. 13 .

 13 Fig. 13. Number of packets M B [1] (B.I.E.R. retransmissions), M m [1] (multicast retransmissions) and M u [1] (unicast retransmissions) transmitted in the binary tree of figure 1 until all destinations receive a copy.

Fig. 14 .

 14 Fig. 14. Number of packets M B [1] (B.I.E.R. retransmissions), M m [1] (multicast retransmissions) and M u [1] (unicast retransmissions) transmitted in the tree of figure 4 until all destinations receive a copy. Solid lines represent exact values (obtained by simulation), dotted lines represent the low-loss approximation given in theorem 1.

  Algorithm 1 Reliable B.I.E.R. Source Operation

	∆tagg ← NACK aggregation delay
	w ← packet cache window size
	F ← unique flow identifier
	B ← destination bitstring
	S ← 0	sequence number
	C ← {}	packet cache
	R ← {}	retransmit bitstrings
	T ← {}	retransmit timers
	for each outgoing packet p do
	insert reliable B.

I.E.R. header with flow F , seq S insert B.I.E.R. header with bitstring B transmit

  Reliable B.I.E.R. Destination Operation

	∆tretry ← NACK retransmission delay
	l ← NACK retransmission limit
	F ← unique flow identifier
	L ← {}	seqnum of lost packets
	T ← {}	NACK transmit timers for lost packets
	N ← {}	number of times a NACK has been sent
	C ← {}	recovered packets pending for app
	n ← 0	next expected seqnum
	for each incoming packet p with flow F , seq S do
	if S = n then	received in-order packet
	transmit p to application
	n ← n + 1
	else if S > n then	received out-of-order packet
	if S / ∈ C then	cache packet and un-schedule NACK
		C

T [s], and Algorithm 2

Table 1 .

 1 Average number of retransmissions per multicast data packet for (k, k/2, k/2) tree topologies (approximation as per theorem 1)

	E.R. unicast	multicast

http://www.ietf.org/

It is to be noted, however, that if intermediate routers provides caching capabilities[START_REF] Zhang | Named data networking[END_REF], they could be extended to intercept NACKs and perform retransmissions in place of the source. This would not change the end-to-end behaviour as specified in this paper.

The successor of the last data packet is a special end-of-connection packet. To ease readability, Algorithms 1 and 2 assume an infinite stream.

For lossless links, operating below capacity and with finite buffers, packet losses are due to buffer overflow -thus while a link may be lossless, an interface may still experience packet losses.

The root is labelled[START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF]; the first child of the root is labelled[[1], 1], its second child [[1], 2]; the first child of [[1], 1] is [[[1], 1], 1]; etc.

ACKNOWLEDGEMENTS

The authors are grateful towards Mohammed Hawari for reviewing this paper, towards Pierre Pfister for insightful discussions and comments, and towards the reviewers whose comments greatly helped improve the quality of this manuscript.

Appendix

A. Comparison with Multicast Retransmissions

Proof: [Proof of proposition 2] by induction. If [i] is a leaf, M m

[i] = 0 and F [i] = 0, hence the result holds. Otherwise, let [i] be a node that is not a leaf, and assume that the result holds for all children of [i]. Then, using equation [START_REF] Paul | Reliable multicast protocol (rmtp)[END_REF], and Wald's equation to expand E(U [i]→[[i],j] ) from equation [START_REF] Braun | Performance comparison of resilience mechanisms for stateless multicast using bier[END_REF], it follows that:

where the equality E(X

and equation ( 6

represent the number of trials before (and not counting) the unicast success.

For each of these first

unicast packets will be sent through the chain of links from [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF]

The last (successful) unicast attempt will generate d packets (one per link). Hence, the total number of unicast packets sent until the destination [c] receives a copy, R [1]→[c] , is:

This appendix provides a proof of theorem 1; for this, three lemmas will be needed. Lemma 1 first gives an approximation at order 1 in α of the probabilities of having one or two transmissions. Then, lemma 2 gives a bound on the corresponding probability distributions, which will be used in lemma 3 to show that terms corresponding to three or more transmissions do not contribute to the terms of order 1 in α.

For an arbitrary node [i] in the tree, let l([i]) be the number of links in the subtree rooted at

The following approximations hold when α → 0:

Proof: by induction over the structure of the tree. If [i] is a leaf, then T [i] = 1 by definition (a client needs one copy of the packet). Otherwise, let [i] be a node that is not a leaf, and assume that the result holds for all children of

Then, the definition of T [i] gives:

The following lemma provides a geometric bound on the distribution of X [i]→j and T [i] variables, and will be useful to then bound their expectations. Lemma 2 Let [i] be a node in the tree, and (if

The result for

The result for T [i] remains to be proven. For t ≥ 1:

-

When developing the first product, a term [[i],j]∈c([i]) P r(X [i]→j < k) appears, which cancels out with the second product. Remaining terms in the first product are indexed with σ. These terms contain one or more factors of the form P r(X

and other factors of the form P r(X [[i],j ] < k). Let j(σ) be one of the j such that P r(X [[i],j(σ)] = k) appears in the term. An upper-bound for the other factors is 1, effectively keeping only the contribution of P r(X

The result for

Lemma 3 provides an approximation of the expectations of X [i]→j and T [i] variables, at order 1 in α, using lemmas 1 and 2.

Lemma 3 Let [i] be a node in the tree, and (if

The following approximations hold when α → 0:

Proof: First, it will be shown that

. By summing the inequalities in lemma 2, and provided that α is small enough (α

Then, using lemma 1, E(X [i]→j ) can be approximated as:

which concludes the proof for E(X [i]→j ). The proof for E(T

In the last sum, the first term corresponds to the link from [i] to a child [[i], j], and the second term corresponds to the sum of depths of all links in the subtree rooted at [[i], j] incremented by 1, i.e., the depth as counted from the root [i].

2

A proof of theorem 1 for multicast reliability can now be expressed. Theorem (Traffic footprint for multicast) The following approximation holds when α → 0:

Proof: Let d(l) be the depth of a link l as seen by the root (a link between the root and one of its children having depth 1). Using equation [START_REF] Adamson | Reliable messaging for tactical group communication[END_REF], it is possible to write:

Combining proposition 2 and lemma 3 yields:

which concludes the proof. 2

Finally, the following proves theorem 1 for unicast reliability.

Theorem (Traffic footprint for unicast) The following approximation holds when α → 0:

Proof: As in the proof for multicast reliability, the first term in equation [START_REF] Yavatkar | A reliable dissemination protocol for interactive collaborative applications[END_REF] can be approximated as: E(F [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] ) = L -L(D -1)α + O(α 2 ). Hence, the whole expectation can be approximated as:

= E(F [START_REF] Diot | Deployment issues for the ip multicast service and architecture[END_REF] ) +