Title: Reliable Multicasting Using IP Protocol

Reliable IP Multicast

Man-Yeob Lim (mylim@sunam.kreonet.re.kr)

Dae Young Kim (dykim@ccl.chungnam.ac.kr)

Chungnam National University, Korea

　

Abstract

　

In multicast communication, many reliable multicast schemes were studied in order to overcome packet losses in the network. However the fact that packets are lost in the underlying networks but the solutions are sought in the end hosts makes the search for solutions difficult. As the network technologies improve, almost all the packet losses are due to congestion in the network. If routers can identify packets before dropped from congestion, the routers can initiate recovery process much sooner than end hosts. A reliable multicast scheme initiated and coordinated by routers is proposed. This scheme is much faster than by sender-initiated or receiver-initiated recovery and latency is smaller. Moreover, latency jitter is substantially smaller so that this scheme can improve recovery performance of real time packets.

Keywords: Reliable Multicast Protocol, Reliable IP Multicast, Congestion, Retransmission, Buffer Router, Cache Router, Packet Recovery

Table of Contents

Introduction

Related Works

Recovery Operation

Delay before Retransmission

Recovering Burst Losses

Packet Format

Simulation

Scalability

Discussion

Conclusion

References

Introduction

　

Since the IP multicast was proposed [1], there have been many research works on reliable multicast protocols. However the fact that the multicast routing is performed on IP packets and IP packet losses occur in the underlying networks but the solutions are sought in the end hosts makes the search for solutions difficult. The transport protocol sits on end hosts of group members, which are spread over a large geographical area, and so if packets are lost, it not only takes long to detect losses in the transport layer but also makes group coordination very complicated. Even though many schemes were proposed to overcome the multicast communication losses [2-6], it is hard to devise a complete and general solution without network involvement in the task.

Packet loss due to uncorrectable bit errors is common in wireless links, where loss rate of as high as 40% has been measured in the field. In wired links, link errors are rare, and the dominant cause of errors is a temporary overload in switch and multiplexor buffers [7]. Current high-speed networks which use fiber-optic transmission links can achieve as low as 10e-14 error rates that makes it negligible compared to loss due to congestion.[8] This figure is lower error rate than one bit error per all day long in a gigabit network. This fact gives us a clue that we can solve the multicast problem in the network level without end hosts’ involvement. Because packets are lost due to congestion, i.e. temporary overload in router or switch buffers, we can devise a process to identify a packet before dropping and then to retransmit by network element.

In high speed networks, end-to-end congestion control is not appropriate, so that hop-by-hop congestion control was suggested [9][10]. In addition to the congestion control, if packet recovery is added, this solution is provided by the network layer and complete reliable multicast and unlimited scalability can be acquired.

In real time multicast service, latency jitter is critical for replay. The existing protocols suffer from relatively wide latency jitter because loss is detected at the source or receiver while packets are lost at various part of the network. In order to minimize the jitter the packets should be recovered as soon as possible and recovery at routers has possibility.

In this work we present a recovery scheme, Reliable IP Multicast (RIM), which recovers multicast packets dropped at routers. If a packet is dropped at a router the router issues a drop message to the router which holds the duplicate packet. The packet is retransmitted by unicast to the router which sent the drop message and multicast is resumed. There is no flooding and implosion because the drop message and the repair packet are sent by unicast.

　

Related Works

Depending on who initiates recovery process, reliable multicast schemes are divided into sender-initiated and receiver-initiated schemes [11]. In sender-initiated schemes the source host detects packet losses based on missing ACKs. Because positive acknowledge is used, ACKs become overhead in normal operation. In receiver-initiated schemes, receiving hosts detect missing packets and report NAKs to the source. In error-free situation, no extra packets are transmitted thus giving network no overhead. But if packet loss occurs, every receiver who does not receive the packet issues NAK toward the source. This causes NAK implosion. There are several schemes to reduce NAK implosion. In SRM [12], random backoff delay is used before sending NAKs, so that other receivers can suppress NAKs. This backoff delay can suppress NAK implosion but it enlarges recovery latency.

Back in 1992, RM [13] proposed to give window based reliability to every connections from the source to the destination in the multicast tree. Every host and intermediate gateways are equipped with recovery caches and point to point reliable communications are guaranteed. This scheme could provide a reliable multicast in the network level but it requires heavy routers and does not have compatibility with the Internet and will suffer extreme performance degradation.

In local recovery approaches, receivers in a local group coordinate each other and recover lost packets among them, thus confine the propagation of NAKs inside of the local group. Because there is no NAK implosion, the receivers can send NAKs as soon as packet loss is detected, thus eliminating backoff delay. In a server-based local recovery scheme [14], repair servers do a major role in recovering lost packets. Repair servers are connected to the routers or could be included inside the routers. They take part in group communication and store packets in the internal cache. Recovery is receiver-oriented, i.e. the receivers have responsibility to detect missing packets and request retransmission. Upper layer protocol detects lost packet and sends NAK to a local group including a repair server. The repair server retransmits the repair packet if it succeeds to find the lost packet. If it fails the repair server multicasts a NAK to other repai! r servers and the source host. The local recovery has better latency performance over the SRM [12], because in SRM random backoff delay is added before requesting retransmission in order to suppress NAK implosion. In SRM retransmission is made by any receiver who detects packet loss, but in the local recovery NAK transmission is limited to a local group.

Recently, suggestions are made to equip routers with cache to store packets for recovery. Motivated by the Active Network technology[15], more functions are added to routers to fulfil future network requirements. In ARM [16], active routers perform the following actions: data caching for local retransmission, NACK fusion/suppression, partial multicasting for scoped retransmission. ARM selects routers which are located at strategic points in the network, called active routers. Active routers have internal cache to store packets for recovery. As a receiver-initiated scheme, receivers detecting packet loss sends NAK. NAKs are forwarded to upstream toward the source. When an active router receives a NAK, it retransmits repair packet if it holds the same packet in the cache, or forwards the NAK to upstream. In addition to retransmitting the repair packet, the active router combines the same NAKs coming from different receivers into one NAK and! implosion is avoided. (Fig 1. ARM Operation)

ARM outperforms SRM in recovery latency, where SRM has 2.5 RTT in non-adaptive mode, 1.4 RTT in adaptive mode while ARM has 1 RTT without caching, 0.2 RTT in 100% caching. Here the recovery latency is defined as time from loss is detected at receivers until the loss is recovered. When a packet is lost in the intermediate router, the time for a packet to travel from the lost point to the receivers should be added to the delay latency. In the receiver-initiated reliable protocols there is no way to figure out the time for the packet loss, so that the delay latency is defined in the view of the receivers.

Recovery Operation

When a router receives more data than it can handle, congestion occurs. Once a congestion occurs the router receives no more data until the congestion is removed. Because the input queue is full, the incoming packets are not accepted in the queue but just ignored. In RIM, small size of extra queue is allocated to store header of dropped packets. The IP header is 20 bytes long and this information is enough to search the same packet from duplicate packet storage. The header includes source address, destination group address, identity and offset fields. The identity field identifies packets out of a packet stream which is going from one source to one destination. This field was defined for packet segmentation and reassembly. When a packet is travelling through a network the packet is segmented into pieces if the underlying network does not support long packet size. The segmented packets are reassembled in the destination host based on the i! dentity and the offset field. If copies of the dropped packets are stored in a place it is possible to identify the same packet with the identity and the offset field. In order to retransmit the dropped packet, the congested router requests retransmission by sending a request packet which includes header of the dropped packet.

Multicast routers at selected locations are given internal cache to hold duplicate copies of the multicast packets as long as the packets can reach the next multicast routers. The multicast routers are not all equipped with buffer, but routers in every several hops in the routing tree or routers which are located at strategic locations like congestive area, are selected. As a packet travels along the routing tree, it passes through cache routers. If congestion occurs and the packet is lost, the packet is repaired by the cache router through which the packet passed most recently. For this purpose an option field is added to the IP data packet to store the last cache router's IP address. The address field is updated by every multicast router when the packet passes through the router. (Fig. 2. RIM Operation)

If a buffer router receives repair request, the router searches the duplicate packet in the cache and encapsulates the packet into a unicast one. The unicast packet is transferred to the requesting router. Then the requesting router restores into multicast packet and resume multicasting.

Delay before Retransmission

　

When congestion occurs there arises a question that how soon the router will be recovered from congestion and become ready to receive packets. If the congestion extends for a long period of time fast retransmission is useless or makes problem even worse. In reliable unicast protocol, congestion control is provision of TCP, which seems working acceptably because there are enough delay before the congestion is detected by the end host even though the response is not optimally fast. In multicast, congestion makes reliable transport protocol harder and getting an optimum congestion control even worse. The optimum scenario against congestion is to detect a congestion as soon as possible and to wait until the congestion is removed before any retransmission is attempted. Hop-by-hop congestion controls were proposed in the high speed networks. If congestion is detected the congested router notifies its congestion to the upstream routers to re! duce [9] transmission. We propose to make repair request after the congestion is removed. Because the header size is only 20 bytes long there is no big impact to the memory usage even though thousand headers are saved before requesting requests. This recovery scheme can be working fine with proposed congestion control.

　

Recovering Burst Losses

　

When a burst loss occurs and thousand of packets are lost, thousand repair requests should be sent. In order to reduce the number of repair requests we can combine the requests into one or more repair requests. When a burst losses happen, the congested router can analyze the headers and combine as many headers in series into one, having same source and destination addresses. The repair request look like to transmit packets from source S to destination D with identity between M and N. Even though there is one or several holes in the burst, the retransmission can include them only to be ignored in the destination host. Using this expression the requesting router can reduce the memory holding headers of the lost burst packets.

　

Packet Format

　

An option field is attached to the IP datagram in order to specify cache router where duplicate packet is stored. The option field has code, length and buffer/cache IP address.

Drop message is an ICMP packet to inform cache router that a packet or burst of packets are dropped. The message includes type, code, checksum, no_of_identity and internet header of the dropped packet which has smallest identity number in the burst. When drop report of multiple packets are sent, series of packets from the same source to the same destination are represented by one drop message.

Repair packet is transmitted as a unicast packet with an option field. The option field has code, length and multicast address. Receiving the unicast packet the router converts to a multicast packet and resumes multicast.

Simulation

We simulated RIM in order to compare delay latency and jitter performance to ARM. As a simulation model a pair of a source and a destination in the routing tree was selected. (Figure 3. Simulation Model) Because packets are recovered by the intermediate routers without involvement of the receivers the delay latency is redefined as time from loss occurred until the loss is recovered. In ARM if a packet is lost at router Rn, the time to detect the loss is n hop delay plus inter-gap delay between packets. Inter-gap delay varies upon packet rate. Also if the last packet in the data stream was lost it takes longer until any heartbeat message is arrived. Once packet loss is detected the receiver issues NAK and it takes n + 1 hop delay for the NAK to reach the first active router which holds the duplicate packet. One more hop delay is added for repair, thus making t! otal of (2n + 2) hop delay + inter-gap delay. In RIM if a packet is lost the NAK is immediately issued to higher routers and repair is made immediately, thus making 2 hop delay. Th delay latency based upon the location where loss occurs is shown in Figure 4. If routers of one out of three routers are selected as active router then the delay latency could be like dotted lines in the figure.

In ARM (Figure 5), as loss point is closer to source, recovery latency becomes longer. As latency becomes longer, the size of cache in the active router becomes large. In RIM (Figure 6), recovery latency is constant no matter where the loss point is, so that the cache size in the active router can be constant. Simulation result shows that RIM outperforms ARM in recovery latency and latency jitter: ARM has recovery latency of 0.5 - 1.0 RTT while RIM has 0.1 - 0.5 RTT based upon caching ratio. ARM has latency jitter of 0.8 RTT independent from caching ratio while RIM has 0 - 0.8 RTT. Caching ratio is the percentage of the number of active routers out of the total routers in the network. In RIM the minimum recovery latency is 0.1 RTT and moreover, the jitter is 0, ideally. The figur! e 0 means that there is no jitter existing in terms of hop count. In real networks, the actual hop delay is different in each hop. The variance of the hop delay and processing time of each router will generate non zero jitter. Note the minimum recovery latency of ARM was 0.2 RTT with old definition while it is 0.5 RTT with new definition. This is because in new definition the propagation delay from the loss point to the destination is added to the recovery latency.

Scalability

As the number of group members increases in a multicast network, the complexity increases enormously when packets are lost. It is because the usual reliable multicast protocols are implemented at the end-hosts. In order to cope with the packet loss, the reliable transport protocol must first figure out who are group members, where they are, and how they should be grouped to minimize retransmission. But if retransmission is made in the network layer as proposed, the retransmission is done by routers independently from group members’ participation. This means that each loss is recovered where and when it was dropped far before the effect is propagated to many group members.

Discussion

It may be interesting to evaluate the proposed RIM protocol based upon the metrics normally used to compare multicast protocols. The metrics are request implosion, duplicate replies, recovery latency, recovery isolation, and adaptability to dynamic membership changes [6].

i. Request implosion: the problem that occurs when a loss of a packet triggers simultaneous requests from a large number of receivers, overwhelming the sender and/or other receivers.

All the end-to-end recovery produces enormous number of simultaneous requests because a congestion at a mid-point in network affects all the receiving member hosts in the subtree. In RIM congestion at one point is readily recovered at that exact point before the impact affects the receiving hosts. Therefore one drop generates just one retransmission request accordingly.

ii. Duplicate replies: the problem that occurs when many end points multicast the same reply in response to a request.

Similar to the above metric, one packet drop at a mid-point in network generates many retransmission requests from group members and thus duplicate replies as many as the number of requests are also generated. In RIM, recovery is committed to the router where congestion occurs, so that the number of reply is reduced to one instead of as many as otherwise affected hosts in the subtree.

iii. Recovery latency: the latency experienced by a member from the instant a loss is detected until a reply is received.

In upper layer multicast protocols, the source host or the destination host should wait for the initial time-out period before taking proper recovery action depending on whether the scheme is source-initiated or destination-initiated. This initial waiting time is normally as long as the packet travel time from source to destination or twice the time depending on protocols. In RIM, because the routers decide when to start recovery processing, they do not need to wait.

iv. Recovery isolation (exposure): if a loss affects only a small number of receivers and the sender multicasts the reply to the entire group, then recovery is not isolated to the members experiencing the fault. The repair of a local fault should ideally stay local. Exposure can be quantified by comparing the number of messages used for repair to the size of the area affected by the loss.

When a packet drop occurs in a router this loss affects only the members downstream in the routing tree. If recovery is completed and multicasting is resumed from the very point of packet loss, the recovery is isolated only to the members downstream in the routing tree.

v. Adaptability to dynamic membership changes: a measure of how the efficiency (in terms of loss of service, duplicate messages and added latency) of error recovery is affected by changes in the group topology and membership.

Because the recovery is implemented by routers and routers are irrelevant to the multicast group membership, dynamic change in membership does not affect the recovery scheme. Only if the routers are routing properly after membership changes, the recovery process has nothing to consider further.

Conclusion

　

A reliable multicast scheme by routers is proposed. By incorporating IP/ICMP drop and retransmission messages, the proposed recovery scheme is simple and efficient. This scheme guarantees one retransimission per one packet drop, thus preventing many receivers from requesting retransmission. Because the scheme is implemented purely in the network layer, not only coordination among group members is unnecessary but also it provides unlimited and complete scalability. Because there is no coordination between group members, there is no limitation nor overhead due to the size of multicast group.

References

[1] S. Deering, Host Extensions for IP Multicasting, RFC 1112, Jan. 1989.

[2] S. Kasera, J. Kurose, and D. Towsley, Scaleable reliable multicast using multiple multicast groups, Proc. ACM Sigmetrics Conference, 1997

[3] J. M. Chang and N. F. Maxemchuk, Reliable broadcast protocol, ACM Trans. Computer Systems, 2(3):251-273, August 1984.

[4] S. Armstrong, A. Freier, K. Marzullo, Multicast Transport Protocol, RFC 1301, Feb. 1992.

[5] J. Lin, and S. Paul, RMTP: A Reliable Multicast Transport Protocol, PROC. IEEE INFOCOM’96

[6] C. Papadopoulos, G. Paruklar, G. Varghese, An error control scheme for large-scale multicast applications, Washington University, St. Louis.

[7] S. Keshav, An Engineering Approach to Computer Networking, Addison-Wesley, pp 373-374

[8] Israel Cidon, Asad Khamisy, Moshe Sidi, Analysis of Packet Loss Processes in High-Speed Networks

[9] P.P. Mishra and H.R. Kanakia, A Hop-by-Hop Rate-based Congestion Control Acheme, Proc. ACM SIGCOMM ’92, Aug. 1992

[10] H.T. Kung, R. Morris, Credit-Based Flow Control for ATM Networks, IEEE Network Magazine, March/April 1995, pp 40-48

[11] D. Towsley, J. Kurose, S. Pingali, A Comparison of Sender-Initiated and Receiver-Initiated Reliable Multicast Protocols, IEEE Journal on Selected Areas in Communications, April 1997

[12] Sally Floyd, Van Jacobson, Steven McCanne, Ching-Gung Liu, and Lixia Zhang, A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing. ACM SIGCOMM’95, Oct. 1995

[13] Bala Rajagopalan, Reliability and Scaling Issues in Multicast Communication, Proc. ACM SIGCOMM ’92

[14] Sneka Kasera, Jim Kurose and Don Towsley, A Comparison of Server-Based and Receiver-Based Local Recovery Approaches for Scalable Reliable Multicast, Proc. IEEE INFOCOM’98

[15] David L. Tennenhouse, et al, a Survey of Active Network Research, IEEE Communication Magazine, Jan. 1997

[16] Li-wei H. Lehman, Stephan J. Garland, and David L. Tennenhouse, Active Reliable Multicast, Proc. IEEE INFOCOM’98, 1998

[17] Man-Yeob Lim, Dae Young Kim, Internet Draft, IP Extension for Reliable Multicasting, http://ds.internic.net/internet-drafts/draft-lim-ip-reliable-multicast-01.txt, May 1998

Figures 　

Figure 1. ARM Operation

Figure 2. RIM Operation

Figure 3. Simulation Model

Figure 4. Recovery Latency, ARM vs RIM

Figure 5. ARM Recovery Delay

Figure 6. RIM Recovery Delay