Transparent and efficient multi-destination TCP communications based on bit indexed explicit replication

Systems, methods, and computer-readable storage media for multi-destination TCP communications using bit indexed explicit replication (BIER). In some examples, a system can generate a TCP packet associated with a TCP session involving a set of destination devices, and encode an array of bits into the TCP packet to yield a TCP multicast packet. The array of bits can define the destination devices as destinations for the multicast packet. The system can transmit the TCP multicast packet towards the destination devices through a BIER domain. The system can receive acknowledgements from a first subset of the destination devices. Based on the acknowledgements, the system can determine that the first subset of the destination devices received the multicast packet and a second subset of the destination devices did not receive the multicast packet. The system can then retransmit the multicast packet to the second subset of the destination devices.

TECHNICAL FIELD

The present technology pertains to multicast communications, and more specifically, the present technology involves multicast transmissions based on bit indexed explicit replication and transport protocols.

BACKGROUND

A large portion of today's internet traffic goes through content delivery networks which provide a limited set of data to a large number of destinations. These technologies generally rely on caching and replication. Replication allows content delivery networks to provide the same data to multiple destinations. Typically, content delivery networks perform replication through IP multicast communications or overlay networks. IP multicast enables replication by allowing the data to be sent to all end-hosts. Unfortunately, IP multicast retransmissions can be significantly inefficient, as IP multicast lacks a mechanism for limiting the data transmitted during a retransmission to an arbitrary set of end-hosts. By contrast, overlay networks can greatly simplify replication. However, overlay networks require a significant amount of state to be maintained by intermediate nodes, which can become onerous

More recently, a new multicast paradigm called bit indexed explicit replication (BIER) has emerged. Contrary to native IP multicast, BIER allows for data to be transmitted to an arbitrary set of end-hosts, which can be defined by a group of bits representing a selected set of end-hosts. However, BIER has limited efficiency and reliability, and lacks end-to-end flow control as well as backwards compatibility with connection-oriented transport layer protocols and communications.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

The approaches set forth herein can provide efficient and reliable delivery of data from a source to multiple destinations specifically selected to receive the data. Moreover, the approaches herein provide backwards compatibility to transport layer stacks and protocols, such as transport control protocol (TCP) stacks. For example, BIER can be used to provide transparent and efficient multi-destination TCP.

Disclosed are systems, methods, and computer-readable storage media for transparent and efficient multi-destination transport layer communications using BIER. In some embodiments, an example system can generate a multicast BIER-encoded packet having an array of bits and a transport protocol segment. The array of bits can correspond to a set of destination devices for the packet. Moreover, the array of bits can be used by network devices in a BIER domain to route the packet to the corresponding destination devices.

For example, each bit in the array can represent a particular destination device. The bits can thus allow any intermediate nodes in the BIER domain that receive the multicast packet to determine where to forward the packet. The intermediate nodes can refer to a mapping table to identify which destination device is associated with a particular bit in the array of bits.

The multicast packet can allow the system to transmit data to multiple destination devices without sending the data separately or individually to all destination devices. For example, the multicast packet can allow the system to select a particular set of destination devices and transmit the data to the particular set in one multicast communication that is tailored only to the destination devices in the particular set. If retransmission is later necessary, the system can also modify the array of bits to modify the destinations of the multicast packet to a different set of destination devices, to limit the retransmission to only those destination devices in the different set. This can allow the system to avoid having to send the packet and data to any destination devices that do not need to receive the packet.

The system can transmit the multicast BIER-encapsulated packet to the set of destination devices through a BIER domain. As previously noted, any intermediate nodes in the BIER domain can refer to the array of bits to determine which destination nodes should receive the multicast BIER-encapsulated packet, in order to understand where to forward the multicast BIER-encapsulated packet.

The system can transmit the multicast BIER-encapsulated packet, including the TCP segment in the BIER-encapsulated packet, over the BIER domain to the set of destination devices. The multicast BIER-encapsulated packet can be configured to allow backwards compatibility with the transport layer stacks (e.g., TCP stacks) at the destination devices. Moreover, the transmission from the system to the destination devices can take into account transport layer state, such as acknowledgments sent or received, buffers and windows (e.g., TCP windows), etc.

The multicast BIER-encapsulated can be forwarded to the set of destination devices by one or more destination helper devices in the BIER domain. In some cases, the destination helper devices can decode the transport protocol segment from the multicast BIER-encapsulated and forward the transport protocol segment to the set of destination devices.

The system can receive acknowledgements from those destination devices that received the multicast BIER-encapsulated packet and/or the transport protocol segment. The acknowledgments can be responsive to the transport protocol segment in the multicast BIER-encapsulated packet. The acknowledgments can acknowledge the last transmission(s) received by the destination devices associated with the transport protocol session involving the set of destination devices. Further, the acknowledgments can include, without limitation, an acknowledgment number, a sequence number, one or more other acknowledgment flags or data, and so forth.

Based on the acknowledgements, the system can determine which destination devices received the multicast BIER-encapsulated packet and which destination devices did not. If one or more destination devices did not receive the multicast BIER-encapsulated packet, the system can retransmit the multicast BIER-encapsulated packet, including any associated data, to those one or more destination devices that did not receive the multicast BIER-encapsulated packet.

The system can limit the destinations of the retransmitted multicast BIER-encapsulated packet to those one or more destination devices that did not receive the multicast BIER-encapsulated packet, without also retransmitting the packet to those destination devices that did receive the packet. To retransmit the multicast BIER-encapsulated packet to those destination devices that did not receive the multicast BIER-encapsulated packet, the system can modify the multicast BIER-encapsulated packet or generate a new multicast BIER-encapsulated packet based on a modified array of bits. The modified array of bits can include bits corresponding to the destination devices for the retransmission, and exclude bits corresponding to those destination devices that did receive the multicast BIER-encapsulated packet previously transmitted.

Description

The disclosed technology addresses the need in the art for efficient and reliable multicast. The present technology involves system, methods, and computer-readable media for efficient and reliable multicast using BIER multicast and transport-layer protocols. A description of architectures and network environments for efficient and reliable multicast using BIER and transport-layer protocols, as illustrated inFIGS. 1A and 1B, is first disclosed herein. A discussion of multicast using BIER multicast and transport-layer protocols, as illustrated inFIGS. 2-4, will then follow. The discussion then concludes with a brief description of example computing devices, as illustrated inFIGS. 5 and 6A-B. These variations shall be described herein as the various embodiments are set forth. The disclosure now turns toFIG. 1A.

FIG. 1Aillustrates a schematic diagram of an example architecture100for multi-destination transport control protocol (TCP) communications using BIER. Data source104can provide data to multi-destination relay106that needs to be transmitted to destinations110A-D (collectively “110” hereinafter). In some cases, the data source104can provide the data to multi-destination relay106as a unicast message or stream. To illustrate, the data source104can provide the data to the multi-destination relay106in a TCP stream, as an inter-process communication (IPC) or through system calls to a BIER-aware socket interface, for example.

Multi-destination relay106can obtain the data and provide the data to all destinations110in a reliable multicast transmission. For example, multi-destination relay106can establish a TCP session with destinations110. In some cases, multi-destination relay106can establish individual TCP sessions with the destinations110and combine the individual sessions into a single TCP session with the destinations110.

Multi-destination relay106can generate a multicast packet using BIER, to be transmitted to the destinations110through the BIER domain102. BIER is a multicast forwarding technique requiring each packet to transport a bitmask field for which each bit set to 1 represents a destination the packet should reach. Each bit is therefore associated with a given destination for which the router knows the next-hop. The BIER domain102can include routers that are capable of supporting BIER, such as Bit-Forwarding Routers. Moreover, the BIER domain102can implement BIER control plane protocols which allow routers within the BIER domain102to exchange the information needed for them to forward packets to each other using BIER. A further description of BIER, including the BIER architecture, is provided in Wijnands, et al. (Jul. 18, 2016), “MULTICAST USING BIT INDEX EXPLICIT REPLICATION”, IETF, draft-ietf-bier-architecture-04, which is incorporated herein by reference in its entirety.

To ensure that the multicast packet gets transmitted over the BIER domain102to the correct destinations110, the multi-destination relay106can set a bit in the multicast packet for each of the destinations110. The bit can be set in a bitmask field encoded in the multicast packet for BIER forwarding. Each bit can represent a respective destination from the destinations110. The bits can thus allow routers or devices in the BIER domain102to forward the packet to the appropriate destinations110.

The BIER domain102can include destination helpers108A-C (collectively “108” hereinafter), which are configured to support BIER. Destination helpers108can perform forwarding of BIER packets based on the bits in the bitmask field encoded in the multicast packets.

The destination helpers108can perform lightweight TCP stream tracking and packet modification. For example, the destination helpers108can keep track of each TCP connection in order to remember the last sequence number explicitly acknowledged by the data source104or the multi-destination relay106(e.g., when the acknowledgment bit is set by 1).

The destination helpers108can extract TCP segments from BIER packets and send them to the destinations110as IP packets. This can allow the destinations110to receive and process the packets from the BIER domain102without having to implement or support BIER. When forwarding a TCP segment to a destination110, if the acknowledgment flag is not set on it, the destination helper108can set the acknowledgment bit to 1, fill the acknowledgment sequence number with a cached value associated with the same stream (e.g., a value cached when the connection was established), and correct the TCP checksum. If the acknowledgment flag is set, the acknowledgment sequence number can be cached by the destination helper108.

The destinations110can receive the packet with the TCP segment from the destination helpers108. The destinations110may perceive the received packet as a unicast packet, as the BIER multicast process can be transparent to the destinations110.

The destinations110can have an unmodified TCP stack. Moreover, the destinations110can receive the TCP segments, and send data and/or messages back to the data source104and/or multi-destination relay106as a unicast.

The destinations110can receive the TCP segment and data from the destination helpers108, and transmit an acknowledgment towards to the data source104. The acknowledgment can include the acknowledgment sequence number for the data received by the destinations110. The destination helpers108can receive the acknowledgments from the destinations110and forward the acknowledgements to the multi-destination relay106. The destination helpers108can also cache the acknowledgment number in the acknowledgment packet. Thus, next time the destination helpers108receive a packet for the destinations110, the destination helpers108will be able to set the acknowledgment number and also set the acknowledgment bit to 1.

The multi-destination relay106can then receive acknowledgments forwarded by the destination helpers108from the destinations110. The multi-destination relay106can track the acknowledgments received from the destinations110to determine if the multi-destination relay106has not received an acknowledgment from any particular destination. Moreover, the multi-destination relay106may cache the transmitted data chunks until all destinations110have explicitly acknowledged receipt.

If the multi-destination relay106determines that one or more destinations110have not acknowledged the data, it can retransmit the data to those destinations, without also retransmitting the data to those destinations that did receive the data. For example, the multi-destination relay106can adjust the bits in the bitfield mask encoded in the multicast packet to remove the bits for those destinations that did acknowledge receiving the data and only include the bits for which the multi-destination relay106did not receive an acknowledgement. The multi-destination relay106can then retransmit the multicast packet with the modified bits to the destination helpers108over the BIER domain102. The destination helpers108can then transmit the TCP segments to the appropriate destinations as previously described.

The multi-destination relay106can keep the individual TCP state (e.g., windows, acknowledgment sequence numbers, etc.) for each flow. The multi-destination relay106can use the state to ensure that packets sent to the destinations110are compliant with the TCP retransmits and congestion mechanisms of the destinations110. For example, the multi-destination relay106can keep track of the sending window or buffer. The multi-destination relay106can hold off sending more data to the destinations110until the multi-destination relay106has received acknowledgments for the data that is in the sending window or buffer.

Referring toFIG. 1B, the multi-destination relay106can split or divide the destinations110into sets152and154, to break up subsequent multicast transmissions. For example, the multi-destination relay106can modify the BIER bits in the multicast packet to exclude the bits which correspond to destinations110A and110B, to ensure that the multicast packet is not transmitted to destinations110A and110B. Thus, after the bits are modified, the destinations configured on the multicast packet will be limited to destinations110C and110D from set154.

The multi-destination relay106can then create a multicast packet having BIER bits that specify the destinations110A and110B in set152as the destinations. This multicast packet will then be transmitted to the destinations110A and110B in the set152.

The multi-destination relay106can divide the destinations110into sets152and154based on various reasons, as further explained below. For example, the multi-destination relay106can divide the destinations110into sets152and154based on performance. To illustrate, if the destinations110A and110B are slower in responding (e.g., sending ACK messages) to communications from the multi-destination relay106, then those destinations110A and110B can be divided into a different set152to prevent those destinations110A and110B from slowing down the communications with the other destinations110C and110D. The multi-destination relay106can then generate a different multicast packet for destinations110A and110B in set152, as previously explained, which it can use to communicate with those destinations110A and110B at the slower pace of the destinations110A and110B.

Similarly, by removing destinations110A and110B from the set of destinations110in the original multicast packet, the multi-destination layer110can from set154with only destinations110C and110D, and continue communicating with those destinations at the faster pace.

As another example, the multi-destination relay106can divide the destinations110into sets152and154in order to send different data to different destinations. To illustrate, in a TCP flow, some chunks of data might be the same for every destination, while other chunks may differ depending on the destination set. Accordingly, the different sets152,154may be used to send the different data chunks.

The multi-destination relay106can also add destinations to a set of destinations configured on a multicast packet. For example, the multi-destination relay106can add destination110E to destination set154by adding a corresponding BIER bit to the multicast packet. The destination110E can be added for various reasons. For example, if data source104needs to also send the data to destination110E, it can add destination110E to the destination set154to ensure that destination110E also receives the data when transmitted to the destination set154. As another example, if destination110E is split from another set, the multi-destination relay106can add the destination110E to the destination set154if the multi-destination relay106determines that the destination110E needs to receive the same data and may have the same or similar parameters (e.g., speed or pace of communications, TCP parameters, etc.).

While the data source104and multi-destination relay106are illustrated inFIGS. 1A and 1Bas separate systems, it should be noted that in some cases, the data source104and multi-destination relay106can reside within the same system. Similarly, in some cases, the destination helpers108can reside on the destinations110.

Having described an example architecture, the disclosure now turns to an overview of multi-destination TCP communications using BIER. The TCP communications can involve TCP end-to-end with a BIER aware stack at the data source or relay. The data source can reliably provide the data to the multi-destination relay in various ways. For example, the source can provide the data via a TCP stream, as an inter-process communication (IPC), or through system calls to a BIER-aware socket interface.

The multi-destination relay can receive the data flow and cache the data chunks transmitted to the destinations, until all destinations have explicitly acknowledged receipt of the data flow/chunks. The multi-destination relay can include a BIER stack which allows the multi-destination relay to send TCP packets to an arbitrary set of destinations. For a given flow, the multi-destination relay can keep a TCP state (e.g., TCP windows, acknowledgments, acknowledgment sequence numbers, etc.) for each destination. This state can be used in order to ensure the packets sent to the destinations are compliant with the TCP retransmit and congestion mechanisms of all the destinations.

In some cases, the expectation can be that the destinations consume the data at approximately the same speed, which can be controlled to the slowest denominator by the source in order to maintain the outstanding amount of data below a certain threshold. Destinations that appear to be too slow or unresponsive can be separated from the faster destinations, by dynamically and transparently creating two or more destination sets with different rates.

The destination helper can perform lightweight TCP stream tracking and packet modifications. In some cases, the amount of packet modifications may depend on the way BIER is implemented. The destination helper can keep track of each TCP connection in order to remember the last sequence number explicitly acknowledged by the source or multi-destination relay (e.g., when the acknowledgment bit is set by 1). The destination helper can extract TCP segments from BIER packets and send them to the destinations as IP packets. Since the destinations receive the packets as IP packets, the destinations do not have to implement BIER.

When forwarding a TCP segment to a destination, if the acknowledgment flag is not set, the destination helper can set the acknowledgment bit to 1, fills the acknowledgment sequence number with the cached value associated with the same stream, and correct the TCP checksum. If the acknowledgment flag is set, the acknowledgment sequence number can be cached by the destination helper.

The destinations can implement an unmodified destination TCP stack. The destinations can receive regular TCP segments, and can send data back to the source as unicast packets. Backward unicast segments can be acknowledged by the source as unicast.

The sets of destinations involved in a TCP communication can be dynamically adjusted for various reasons, such as performance and efficiency. For example, in some cases, to reduce the amount of used networking resources, the multi-destination relay106can send data to all of the destinations which have not yet acknowledged the data. However, this may result in the rate to all destinations being capped by the slowest of the destinations. Accordingly, the multi-destination relay106can observe when some destinations are slower than others and send data specifically to destinations that are ahead, while waiting for the slower destinations. The multi-destination relay106can identify that some destinations are slower than others in various ways. For example, the destination can monitor how much of the TCP sending window is unused due to limitations of the slowest destination.

If the slower destinations continue to run slower or cause delays, the multi-destination relay106can a split the set of destinations between slow and fast destinations. Sets of destinations can be divided further or merged again, as necessary.

In some cases, it is also possible to throttle down some destinations in order to allow the slowest destinations to catch up. For example, the multi-destination relay may throttle communications to the fastest destinations until the slower destinations catch up. If the problem persists, the multi-destination can continue to throttle communications, split the set of destinations into faster and slower sets, or both.

To avoid a significant trade-off between transmission delay and network resources consumption, the multi-destination relay can dynamically adjust parameters for splitting a set of destinations or adding/removing destinations to a set, in order to optimize the transmission delay while making sure that networking resources are not exhausted.

Destinations can also be added and removed from a multi-destination flow as necessary. For example, destinations can be added or removed by sending unicast SYN and FIN/RESET packets and changing the sending state accordingly. When adding a new destination, the first sent byte can be arbitrarily chosen. New destinations can be added or removed for various reasons, such as performance, service changes, requests, etc. For example, destinations can be added or removed from the multi-destination flow in live-content streaming contexts which generally involve a destinations set that dynamically changes.

In some examples, the multi-destination relay can terminate the TCP connection from the data source. A reliable multicast operation can be performed between the multi-destination relay and the multiple destination helpers, whereby the relay interprets the BIER-based address and route. In this example, a hierarchy of relays may be deployed that perform a BIER multicast operation at each level. The destination helpers can turn the reliable multicast operation into unicast TCP and transform the BIER addresses into unicast addresses.

Moreover, in some examples, a shim layer, such as HIP (Host Identity Protocol), can be used to transform a classical address as seen by the upper stack into a BIER-based address. The BIER-based address can also change as additional listeners join, unbeknownst of the application. Listeners can be added by forging a SYN, SYN-ACK, ACK exchange from the relay, as discussed above.

As illustrated above, the multi-destination relay can dynamically manage the set of destinations, allowing for splits and merges depending on the current efficiency/delay desired tradeoff, as well as any service requirements. The multi-destination relay can allow new destinations to be added dynamically to an on-going stream.

In some cases, the multi-destination relay can allow sets of destinations to receive partial data from the streams depending on authorization and policies.

The approaches herein can also mitigate acknowledgment storms using BIER and acknowledgement aggregation. TCP generally requires that acknowledgements be sent by all destinations directly to the source. In some cases, this can create an enormous amount of communications on the network, commonly referred to as an “acknowledgement storm”.

However, acknowledgment storms can be mitigated herein by aggregating acknowledgments from destinations to the multi-destination relay such that, as acknowledgements travel back towards the source, a bitstring encoding the set of destinations actually acknowledging the same data is constructed within the packet. Therefore, the multi-destination relay receives a limited number of acknowledgements including a bitstring that can be used to acknowledge data from multiple destinations instead of just one. This process can include a reversed BIER bitstring building process.

As noted above, BIER can allow for sending a given packet to a selected set of destinations based on the transport layer state (e.g., received acknowledgments, TCP windows, etc.) of a flow or session. Since destinations randomly pick their sequence number during a TCP handshake, in some cases, TCP data packet can be transmitted towards destinations with the acknowledgment flag not set, such that the acknowledgment flag can be set by the destination helper. This can enable backward traffic to be sent as unicast from destinations to sources.

The multi-destination relay can keep track of the TCP state of all the destinations, and use the TCP state when sending back data to multiple destinations such that the transmission is compliant with the TCP specifications of all those destinations.

While the above examples provided herein refer to TCP as the transport layer protocol, the examples herein can also be implemented using other transport layer protocols. For example, in some cases, SCTP (Stream Control Transmission Protocol) can be used instead of TCP. SCTP can allow for dynamic mapping of streams and listeners, so that not all listeners receive all SCTP streams. Registration or policies may be employed to decide which listener gets which stream. SCTP may also be used only between the relays and the helpers, in order to mix TCP and UDP flows in a single federated reliable multicast transport.

The disclosure now turns toFIG. 2, which illustrates an example transport-layer stream200between multi-destination relay106and destination110A. The multi-destination relay106can send a SYN message202to the destination110A. The destination helper108A can receive the SYN message202and forward it to the destination110A. The destination110A can receive the SYN message202and send a SYN/ACK message204to multi-destination relay106. The SYN/ACK message204can include, without limitation, an acknowledgment sequence number and an acknowledgment number.

The destination helper108A can receive the SYN/ACK message204and forward it to the multi-destination relay106. The destination helper108A can also cache information in the SYN/ACK message204, such as the acknowledgment number, the acknowledgment sequence number, etc.

The multi-destination relay106can receive the SYN/ACK message204and send an ACK message206to the destination110A. After the handshake has been established, the multi-destination relay106can send subsequent data packets to the destination110A. The destination helper108A can cache information from the ACK message206. For example, the destination helper108A can cache the acknowledgment numbers and/or acknowledgment sequence numbers sent from the multi-destination relay106to destination110A.

The multi-destination relay106can send a message208to the destination110A. The message208can include, for example, an acknowledgment and data for the destination110A. The destination helper108A can receive the message208and forward the message210to the destination110A. The message210can be the same as message208. However, in some cases, the message210can include modifications to message208. For example, if message208does not have an acknowledgment flag, acknowledgment sequence number, or acknowledgment number set, the destination helper108A can set any of that information in the message210.

The destination110A can receive the message210, and subsequently send an ACK212to the multi-destination relay106. The destination helper108A can receive the ACK212and forward it to the multi-destination relay106. The destination helper108A can also cache information from the ACK212, such as acknowledgment number, acknowledgment sequence number, etc.

The multi-destination relay106can receive the ACK212and determine that the destination110A received the message208. The multi-destination relay106can also respond with an ACK214to the destination110A.

Having disclosed some basic system components and concepts, the disclosure now turns to the example method shown inFIG. 3. For the sake of clarity, the methods are described in terms of the network100shown inFIGS. 1A and 1B. The steps outlined herein are exemplary and can be implemented in any combination thereof, including combinations that exclude, add, or modify certain steps.

At step300, the multi-destination relay106can generate a first multicast BIER-encapsulated packet having a first array of bits (e.g., BIER bits) and a transport protocol segment (e.g., TCP segment). The bits in the first array of bits can respectively define a set of destination devices110as respective destinations for the first multicast BIER-encapsulated packet.

At step302, the multi-destination relay106can transmit the first multicast BIER-encapsulated packet through a BIER domain102and towards the set of destination devices110. The first multicast BIER-encapsulated packet can be routed through the BIER domain102based on the array of bits which identifies the destinations110of the packet.

At step304, the destination helpers108can receive the first multicast BIER-encapsulated packet. If the first multicast BIER-encapsulated packet does not include an acknowledgment sequence number, the destination helpers108can encode a cached acknowledgement sequence number into the packet. The cached acknowledgment sequence number can be based on a previous SYN/ACK message transmitted by the destinations110when establishing the transport protocol connection or session.

At step306, the destination helpers108can extract or extract the transport protocol segment from the first multicast BIER-encapsulated packet and forward the transport protocol segment to the destinations110. As previously noted, the destination helpers108can identify the destinations110for the transport protocol segment based on the array of bits in the first multicast BIER-encapsulated packet.

At step308, one or more of the destinations110can receive the transport protocol segment and transmit an ACK message to the multi-destination relay106.

At step310, the destination helpers108can receive one or more ACK messages from the destinations110, and forward the ACK messages to the multi-destination relay106.

At step312, the multi-destination relay106can receive the one or more ACK messages and determine if the multi-destination relay106did not receive an ACK message from any of the destinations110.

At step314, the multi-destination relay106can determine if it has received ACK messages from all of the destinations110. If the multi-destination relay106determines that it received ACK messages from all the destinations110, at step316, the multi-destination relay106can determine that the transport protocol segment was received by all of the destinations110. If necessary, the multi-destination relay106can proceed to send any additional data to the destinations110.

If the multi-destination relay106determines that it did not receive ACK messages from one or more of the destinations110, at step318, the multi-destination relay106can determine that one or more destinations110did not receive the transport protocol segment. The destinations that are assumed to not have received the transport protocol segment can be those destinations for which the multi-destination relay106did not receive an ACK message. Thus, the multi-destination relay106can infer that a destination did not receive the transport protocol segment when the multi-destination relay106does not receive an ACK message from that destination.

The ACK messages can be responsive to the transport protocol segment in the first multicast BIER-encapsulated packet transmitted by the multi-destination relay. Moreover, the ACK messages can be associated with a transport protocol session or connection associated with the transport protocol segment.

At step320, the multi-destination relay106can retransmit a second multicast BIER-encapsulated packet to those destinations that did not receive the transport protocol segment from the first multicast BIER-encapsulated packet. The second multicast BIER-encapsulated packet can include the transport protocol segment and a second array of bits. The second array of bits can include bits corresponding to the destinations that did not receive the transport protocol segment from the first multicast BIER-encapsulated packet, which are the intended destinations of this second multicast BIER-encapsulated packet. The array of bits can thus define those destinations that did not receive the transport protocol segment from the first multicast BIER-encapsulated packet, as the respective destinations of the second multicast BIER-encapsulated packet.

The multi-destination relay106can maintain the state (e.g., send window or buffer, acknowledgment numbers, connection information, etc.) of the transport protocol session or connection, to ensure that any transmissions (e.g., first and second multicast BIER-encapsulated packets) to the destinations110comport with the state and the transport protocol parameters at the destinations110.

If the multi-destination relay106determines that one or more new destinations need to receive data being transmitted to the destinations110via the multicast BIER-encapsulated packets, the multi-destination relay106can add the destination to the set of destinations for the multicast BIER-encapsulated packets to ensure that destination also receives the data.

Similarly, if the multi-destination relay106determines that one or more of the destinations110should be removed from the set of destinations defined for the multicast BIER-encapsulated packets, the multi-destination relay106can modify the array of bits in the multicast BIER-encapsulated packets to remove any bits corresponding to the one or more destinations to be excluded. Destinations can be removed from the set of destinations and/or the set of destinations can be divided into subsets for various reasons, such as performance, flow control, preferences, etc. For example, the multi-destination relay106may divide a set of destinations into subsets in order to separate the faster destinations from the slower destinations, to allow the transmissions to continue without unnecessary delays. Subsets of destinations can also be further divided as necessary, and other destinations can also be added to specific subsets. The set(s) of destinations can be dynamically and continuously monitored and adapted based on the communications and circumstances.

The transport protocol associated with the transport protocol segment and the transport protocol session or connection can be any transport layer protocol, such as TCP and SCTP. Moreover, to transmit multicast BIER-encapsulated packets to the destinations110, the multi-destination relay106can first establish a transport protocol connection (e.g., TCP connection or session), which it can then use to communicate the multicast BIER-encapsulated packets and content data. In some cases, the multi-destination relay106can form transport protocol connections with each of the destinations110, and combine the individual transport protocol connections into a single transport protocol connection. The multi-destination relay106can use the acknowledgments obtained from the destinations110through the transport protocol connection to determine retransmissions and packet destinations.

The disclosure now turns toFIGS. 4 and 5A-B, which illustrate example devices.

FIG. 4illustrates an example network device400suitable for performing switching, port identification, and/or port verification operations. Network device400includes a master central processing unit (CPU)404, interfaces402, and a bus410(e.g., a PCI bus). When acting under the control of appropriate software or firmware, the CPU404is responsible for executing packet management, error detection, and/or routing functions. The CPU404preferably accomplishes all these functions under the control of software including an operating system and any appropriate applications software. CPU404may include one or more processors408such as a processor from the Motorola family of microprocessors or the MIPS family of microprocessors. In an alternative embodiment, processor408is specially designed hardware for controlling the operations of network device400. In a specific embodiment, a memory406(such as non-volatile RAM, a TCAM, and/or ROM) also forms part of CPU404. However, there are many different ways in which memory could be coupled to the system.

FIG. 5AandFIG. 5Billustrate example system embodiments. The more appropriate embodiment will be apparent to those of ordinary skill in the art when practicing the present technology. Persons of ordinary skill in the art will also readily appreciate that other system embodiments are possible.

FIG. 5Aillustrates a system bus computing system architecture500wherein the components of the system are in electrical communication with each other using a bus505. Exemplary system500includes a processing unit (CPU or processor)510and a system bus505that couples various system components including the system memory515, such as read only memory (ROM)570and random access memory (RAM)575, to the processor510. The system500can include a cache of high-speed memory connected directly with, in close proximity to, or integrated as part of the processor510. The system500can copy data from the memory515and/or the storage device530to the cache517for quick access by the processor510. In this way, the cache can provide a performance boost that avoids processor510delays while waiting for data. These and other modules can control or be configured to control the processor510to perform various actions. Other system memory515may be available for use as well. The memory515can include multiple different types of memory with different performance characteristics. The processor510can include any general purpose processor and a hardware module or software module, such as module1532, module2534, and module3536stored in storage device530, configured to control the processor510as well as a special-purpose processor where software instructions are incorporated into the actual processor design. The processor510may essentially be a completely self-contained computing system, containing multiple cores or processors, a bus, memory controller, cache, etc. A multi-core processor may be symmetric or asymmetric.

To enable user interaction with the computing device500, an input device545can represent any number of input mechanisms, such as a microphone for speech, a touch-sensitive screen for gesture or graphical input, keyboard, mouse, motion input, speech and so forth. An output device535can also be one or more of a number of output mechanisms known to those of skill in the art. In some instances, multimodal systems can enable a user to provide multiple types of input to communicate with the computing device500. The communications interface540can generally govern and manage the user input and system output. There is no restriction on operating on any particular hardware arrangement and therefore the basic features here may easily be substituted for improved hardware or firmware arrangements as they are developed.

The storage device530can include software modules532,534,536for controlling the processor510. Other hardware or software modules are contemplated. The storage device530can be connected to the system bus505. In one aspect, a hardware module that performs a particular function can include the software component stored in a computer-readable medium in connection with the necessary hardware components, such as the processor510, bus505, display535, and so forth, to carry out the function.

FIG. 5Billustrates an example computer system550having a chipset architecture that can be used in executing the described method and generating and displaying a graphical user interface (GUI). Computer system550is an example of computer hardware, software, and firmware that can be used to implement the disclosed technology. System550can include a processor555, representative of any number of physically and/or logically distinct resources capable of executing software, firmware, and hardware configured to perform identified computations. Processor555can communicate with a chipset560that can control input to and output from processor555. In this example, chipset560outputs information to output565, such as a display, and can read and write information to storage device570, which can include magnetic media, and solid state media, for example. Chipset560can also read data from and write data to RAM575. A bridge580for interfacing with a variety of user interface components585can be provided for interfacing with chipset560. Such user interface components585can include a keyboard, a microphone, touch detection and processing circuitry, a pointing device, such as a mouse, and so on. In general, inputs to system550can come from any of a variety of sources, machine generated and/or human generated.

Chipset560can also interface with one or more communication interfaces560that can have different physical interfaces. Such communication interfaces can include interfaces for wired and wireless local area networks, for broadband wireless networks, as well as personal area networks. Some applications of the methods for generating, displaying, and using the GUI disclosed herein can include receiving ordered datasets over the physical interface or be generated by the machine itself by processor555analyzing data stored in storage570or575. Further, the machine can receive inputs from a user via user interface components585and execute appropriate functions, such as browsing functions by interpreting these inputs using processor555.

It can be appreciated that example systems500and550can have more than one processor510or be part of a group or cluster of computing devices networked together to provide greater processing capability.