Tie Liao
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Tie.Liao@inria.fr
This paper addresses the problems related to multipoint distribution of Web documents over Internet. We present a multicast Web application which allows the sharing of Web resources among a group of people by using the MBONE technology. We describe a general-purpose light weight reliable multicast transport protocol (LRMP) which is an important building block of the application. We will also discuss other technical issues related to the design of such applications, such as caching, Web-browser interface, and embedded objects.
Keywords: WWW, Real Time, Conferencing, Multicast, Reliable Multicast.
The multicast conference techniques have been widely exploited on the MBONE (Multicast Backbone) [1]. The MBONE is a virtual multicast network built on the Internet which allows that data packets for multiple destinations are delivered in such a way that no duplicated data travel across the network. There are already a rich set of conference tools available on the MBONE including audio/video, image, whiteboard, and shared text editor. The multicast techniques provide a way to go beyond the client/server model of the Web. But at present it lacks powerful tools for broadcast of Web documents.
This paper presents a new application for broadcast of Web documents, called WebCanal. This application is designed for exchange of Web documents, basically of the text/html MIME type, on the Internet, in multicast mode among a group of users, or in unicast mode between two users. It is intended to be used for:
The distribution of Web documents on the MBONE is very different from real time audio and video conferencing applications. Since multicast packets are sent as datagrams using connectionless protocols such as UDP, they may be lost due to network congestion and delivered not in order. While audio and video conferencing applications can tolerate some packet loss, the distribution of Web documents should definitively implement a mechanism to repair the lost data blocks. Some multicast Web tools use a gross grained scheme - the repeated transmission scheme, which is costly and introduces a large latency, thus not suitable for real time applications. Packet loss repair should be handled in a fine grained fashion, i.e., at the packet level using a reliable transport protocol, much like TCP in the case of unicast connection. Indeed, packet loss repair is performed at the cost of additional transmission delay which is admissible for the distribution of Web documents, but generally not for real time audio/video applications.
Our application is based on the Light-Weight Reliable Multicast Protocol and the Real Time Transport Protocol (LRMP/RTP). The LRMP is derived from the Scalable Reliable Multicast protocol (SRM) [4] but introduces some simplifications and improvements. It offers end-to-end reliable and ordered data delivery service to applications. Preliminary tests showed that this protocol meets well the requirements of file distribution over the MBONE.
We intend WebCanal to be a real time application. Typically a user of WebCanal receives what is sent on a multicast session and displays the most recently received document. No attempt is made to get passed events, whereas users are provided with capabilities to review passed events that have been received previously. We believe this scheme is appropriate for applications we claimed above.
Statistics show that the size of most HTML documents is relatively small and has an average between 6 and 7k bytes [12]. This results in that the WebCanal application can work at very low network bandwidth, e.g. at 8 kbits/sec for well-designed Web pages. This gives an important advantage over other media types which usually requires much higher bit rate.
The remainder of this paper presents in detail the design and the implementation of this application. In the next section we present related work and discuss the existing problems. After we describe the architecture and protocols used in the WebCanal application. Then we address the issues related to reliable multicast transport protocols by presenting LRMP. Next, we discuss the technical problems for designing a multicast Web tool. Finally we give the current status of this work and outline future work.
MCM (Multicast Mosaic) [8], developed by Jean-Christophe Touvet, is a tool specially for multicast of HTML slides. While initially used with the NCSA Mosaic browser, support for other browsers (e.g. Netscape) was added in a newer version. MCM uses a master-slave model. A multicast daemon (master) packs all slides into a single package and repeatedly multicast this package in hope that at least one error-free copy can get to remote sites. When the master loads a Web page, only the URL of this page is multicast. Upon receipt of the URL, those users who have already received the package can visualize the corresponding document. The main problem with MCM is its repeated transmission scheme which is not suitable for real-time applications.
Ed Burns developed Webcast [9] in 1995 for sharing Web documents on the MBONE. It was designed especially to work with the X-Mosaic browser through its CCI interface. Multicast can be carried out either on HTML documents or only on URLs. It was built on Reliable Multicast Protocol (RMP) [5] to cope with the network transmission error, whereas RMP is now considered unsuitable for wide area network-based applications due to its token ring control scheme.
mMosaic [10] is another effort to make Mosaic a multicast tool. Implemented by Gilles Dauphin, mMosaic can multicast Web documents together with inlined images to remote Mosaic users. It uses repeated transmission scheme but can cache data segments received from previous cycles. At each retransmission, remote users only need to repair missing segments.
mWeb [11] is an ongoing project for the distribution of HTML documents over the MBONE. It adopted a much similar approach as ours, SRM/RTP as the transport protocol to offer real time reliable services to applications, this will be explained later in the following sections of this paper. mWeb is an effort to offer a multicast Web tool through multiple browsers and seems to be a good step towards the right direction to providing reliable multicast tools.
A recently emerged technology, the Push technology [13] is aimed at bringing to mass consumers the information of interest rather than they having to fetch it themselves. This technology, characterized by narrowcast or pointcast, basically makes use of unicast data transmission to distribute information to potentially a large number of users. While this technology is very promising, it could aggravate the network congestion problem for several reasons. First data traffic is duplicated in the network. Second, the traffic generated by automatic transfer (push) could be considerably greater than what is loaded via HTTP (pull) because some of the automatically transferred information may be not useful to the user. It is expected that this technology would be combined with the multicast technology in near future.
In conclusion, up to now there is no available tool good enough for multicast of Web documents on the MBONE while the requirements for such a tool are continuously growing.
Our application was designed with the goals of flexibility, scalability and portability. To provide flexibility, we wanted that multiple users can distribute Web documents in a session at any given time, either interactively using a browser or automatically by providing a URL list. While we wanted to use existing Web browsers to visualize the received documents, our application should not depend on a specific Web browser.
By scalability, we wanted that our application can be used for large group of users (typically one thousand or more). To achieve this goal, the transport protocol should minimize control message flow to avoid the proportional growth of this flow with the number of participants. In addition, we wanted that a simple receiver should be light-weight, thus can be run on low-end machines. Since receivers are geometrically dispersed over the world, the quality of their network connections could be very heterogeneous. This problem should be definitively taken into account to ensure the normal behavior of a multicast session.
By portability, we wanted our application to run on multi-platform. This is achieved by using Java language. The WebCanal application was entirely implemented in Java, thus hopefully it should run on UNIX and PC platforms where the Java Development Kit is available.
The building blocks of the WebCanal application is shown in Figure 1. This application runs as an HTTP proxy server to Web browsers. A Web browser uses the HTTP proxy interface to load Web documents by sending an HTTP GET request. Upon receipt of this request, WebCanal loads the document via the HTTP protocol using a unicast connection to the Web server. This document is then sent to the Web browser and also sent to the multicast session. Along with the document, some meta information is also required for interpretation of document data at the receiver, such as content type, location, etc. To do so, an HTTP header is appended at the beginning of each document sent to the multicast session. In particular, the status, content type, content length and location fields should be present in the HTTP header. In this way, any applications that understand the HTTP protocol is able to play with this data stream.
The bulk data of Web documents are sent to the multicast session through the Light-weight Reliable Multicast Protocol which is an extended version of RTP (Real Time Transport Protocol). Since LRMP/RTP offers reliable and ordered packet delivery services, applications can "trust" input data received from the session. Each Web document is treated as an RTP frame, so RTP frame boundary marker can easily tell us the end of a document without necessarily parsing the data stream.
When a document is completely received, the application will send a request to the browser through one of the browser interfaces for display of the document. Unfortunately there is no way at this time to provide a unique interface to all browsers, but a simple solution is to run a Java applet in the browser which is responsible for communication between the browser and the application. In this way, all java-enabled browsers can be interoperable with our application. The CCI interface can be used for Mosaic browser instead.
Figure 1. Architecture of the WebCanal application.
RTP has a companion, the Real Time Transport Control Protocol (RTCP) whose purpose is to provide functions to encapsulate information about the participants in a session and to monitor the quality of service for the data conveyed by RTP. RTP/RTCP are now widely used in real time audio and video conferencing applications on the MBONE.
The data traffic of RTP and that of RTCP are sent in a best-effort way, so that it is not guaranteed that they will all arrive at the receivers. For continuous media applications, the most important is to guarantee the end-to-end transmission delay while some packet loss is tolerable. RTP is suitable for these applications for its low-overhead, best-effort characteristics.
Multicast Web applications have basically loose real-time constraints compared with continuous media applications. Users can tolerate some delay for receiving HTML documents. The tolerable delay ranges typically from 0 - 10 seconds. This particularity makes possible to use error recovery mechanism which is extremely important for our application.
Since the 1980s, a number of reliable multicast transport protocols have emerged. Each of them has its own emphasis and application scope. To avoid to reinvent the wheel, we intend to make use of the already available protocols and take the maximum benefits from the experience from various projects in this domain. Our choice is based on the following criteria:
At present, SRM [4] seems to the best suitable for our criteria while some aspects of this protocol are not fully satisfactory. SRM provides a framework to do packet loss report and repair for applications that need reliable data delivery service. It has been implemented in an application wb, a network whiteboard, and widely tested.
In SRM, receivers send NACK (negative acknowledgement) packets to report packet loss. NACK and repair packets are both sent to the multicast group. To prevent NACK implosion at the sender, before sending a NACK packet, a receiver should first schedule a random timer. When the timer expires, if a similar NACK has been received, the receiver does not send its NACK but waits for the repair. Otherwise it sends a NACK packet.
All participants in a group take part in the repair process. Upon receipt of a NACK, similarly, before sending the repair, a participant schedules a random timer. Repair packet will be sent only if no repair is heard at the timeout.
The timer values used in the above algorithm are based on the round trip time between two participants. SRM depends largely on the ability to measure the round trip time from one participant to all other participants. Besides SRM does not address well the problems related to generic and heterogeneity of receivers.
We decided to use a modified version of SRM, the light-weight reliable multicast protocol. This protocol improves SRM in some aspects which will be described further in the next section.
LRMP was designed as a general-purposed reliable transport protocol based on unreliable underlying network transport protocols such as UDP. It offers three important features: loss repair, ordered packet delivery, and adapted rate-based flow control. It is a complement to RTP. Initially we intended to implement LRMP on top of RTP, as we realized that there would be much redundant information carried in LRMP packets and RTP packets, it is wiser to implement LRMP as an extension to RTP/RTCP.
Five control packet types are specified in LRMP: ECHO and ECHO_ACK packets are used to measure the round-trip time between two users; NACK packets are used to report packet loss; SYNC packets inform the receivers the outgoing sequence number reached; SYNC_ERR packets report an unrecoverable sequence error at a receiver. All these packets are implemented as RTCP control packets. Like RTCP, several LRMP packets can be multiplexed into one out-going packet.
In LRMP, application data are just sent as standard RTP data packets. It is the application's responsibility to use a specific payload format to encapsulate media data and fill the timestamp field.
LRMP packets, RTCP packets together with sequence number carried in RTP packets provides a set of information enough to make a reliable transport protocol. LRMP was carefully designed to work against possible loss of control packets.
In this section, instead of going into the technical details of the protocol, we will emphasize the differences between LRMP and SRM. Readers are invited to refer to [4] for more information about SRM.
In SRM, when packet loss occurs, all participants are involved in the repair process in hope that the closest site to the loss reporter could send the repair. We argue that this scheme is contradictory to the scalability. First for this scheme to work, each participant needs to know the round trip time to all other participants in the session. Consider the case that there are already one thousand participants and a new comer just joins the session. With optimization, this new participant requires at minimum one query packet and one thousand responses to determine the round trip time without counting retransmission. If still new comers arrive, the generated control traffic will be considerable.
Second the round-trip time between two sites is generally time-variant since network congestion varies from time to time, in particular over wide area networks. So measurements need to be performed periodically. As control traffic is generally limited to a low percentage of data traffic, (e.g. 5% in RTP), it is hard to do it.
Finally it is likely that duplicated repair packets will be sent to the whole group, just like duplicated NACKs. The former could be avoided and the latter can not be all eliminated.
Our point of view is that all involved repair scheme is appropriate only if local recovery can be used. In the local recovery scheme, close users (e.g. in a region) are grouped together as subgroups, repair packets are sent in the subgroup when possible by adjusting TTL (time to live) in multicast packets. This is very attractive and is an area for future work [6].
To simplify the problem, in LRMP, only sender is allowed to send repair packets. So we need only to know the round-trip time from the sender to receivers. An additional advantage of this scheme is that receivers do not need to cache received packets if they are in order, and thus require less system resources.
A NACK packet in LRMP includes information about the first sequence number lost (16 bits), a bitmask (16 bits) for succeeding lost packets. A LRMP receiver uses the random timer value proposed in SRM for sending NACKs and keeps track of NACKs sent by other receivers to avoid NACK implosion.
Upon receipt of a NACK packet, repairs are sent immediately by the original sender if the request is considered not duplicated. LRMP treats resend requests of the same packet as duplicated if they are received within 0.5 second. The sender gives higher priority to sending repair packets than sending normal packets.
The reception cache has a limited size, but should be enough large for loss repair. However if there are many out-of-order packets and repairs do not arrive, the reception cache may become full. In this case, there are two choices, either to drop new packets or to clear old packets to keep synchronized with the sending process. Note that the flow control in LRMP is not adapted for a particular user. We adopted the later since LRMP is designed for transmission of continuous data streams, older data are considered less important than new ones. When packets are dropped from the cache, a reception exception event will be generated, both the application and the sender will be notified of such an event.
Unlike TCP which uses a window based flow control, LRMP uses a rate based flow control mechanism. That is, LRMP sends data packets, including repair packets, at a rate specified by an application. This rate is adapted dynamically to better suit available network bandwidth.
In order to avoid to aggravate network congestion, a simple and intuitive way is to keep transmission rate to the effective data rate, i.e., the rate with loss excluded. However this would not work in practice, because other applications using a best effort algorithm or with no adapted flow control will fill the bandwidth. The algorithm currently used in LRMP is based on loss statistics collected through RTCP RR's (receiver reports). Only "bad" receivers affect the flow control. Transmission rate is decreased when there are many receivers with a significant loss rate, and it is increased when there are a few.
The purpose of this algorithm is to keep an acceptable speed for the majority of receivers, and to try to satisfy a few worst receivers when possible. More sophisticated flow control mechanisms are subjects under study. This algorithm may cause reception failure at the worst receivers a situation which will be discussed in the section that follows.
While 100% reliability is attractive, it is difficult to achieve it in practice. To ensure 100% reliability, we have either to use a flow control mechanism like in TCP which is adapted to the worst receiver, or in absence of this adaptation to keep very old data for any possible retransmission. The first solution is excluded in LRMP. For the second one, there are two ways to do it, either old data are kept in the cache of the protocol entity or by the application. In case of continuous data stream, keeping all data by the protocol requires in theory a cache with infinite capacity. Whereas the second depends on applications, this is an application semantics.
In LRMP, we want neither to use very large cache nor to be application dependent. So it is possible that LRMP is unable to resend very old data packets. Consequently unrecoverable reception error may occur at receivers. Note that data rate is adapted to the packet loss at most of receivers, so this will only happen at the worst receivers. LRMP provides mechanism for recovery from a reception exception.
If due to network partition or a receiver with a terrible link, reception failure occurs, i.e., a receiver finds a too large difference between the currently received sequence number and that of the first lost packet, it will send a SYNC_ERR packet (upon timeout) to report a serious synchronization error. It also cleans its cache and tries to synchronize with the current sequence number.
At the sender side, upon reception of a SYNC_ERR packet, LRMP will notify the application such an event together with the interval of lost sequence numbers. It is the application to decide to take any remedy actions. For example it may ignore the event for continuous data stream, or resend this part of data according to the level of importance.
This mechanism allows application to control the level of quality of service and thus prevents the disturb caused by a particular receiver with a very bad network connection. We think that this is especially suitable for WAN based applications.
This section describes our approaches to other high-level technical issues related to the design and implementation of multicast Web applications. Our application is intended to be interoperable with multiple Web browsers. In lack of a standard client interface to Web browsers, there is no a simple and convenient way to get our application to work with whatever user's preferable browser. The requirement is that a multicast application needs to catch user's open operations and to send received documents back to the browser for visualization. We want to offer multiple browser interfaces at some future time.
If the documents to be sent are found on a Web server, they are fetched by a built-in HTTP module in our application. This makes our application independent of Web servers, so no any operations need to be performed on the server side. Note that our application can be configured to further use an HTTP proxy instead of fetching the documents directly from a Web server. This is useful for people who are behind a fire wall.
To be able to send, a user should first create or join a session. When a session is created (e.g. using sdr), it is like a broadcast channel. Users are free to go in or out a channel. No special control is provided at this time on joining a session and becoming a sender. This functionality needs further study.
Finally, send control over content types and size is also important. In a session where there are users with a bad network link, we may just send HTML contents. Otherwise we could send both HTML contents and inlined images. Therefore users are allowed to restrict the document transfer to be carried out only on certain content types.
In this case, documents to be sent are specified in a file. A user just fills in that file a list of URLs. For conveniency, no need to include embedded objects in the list. A HTML parser allows to get them and add to the final list.
After start-up, our application reads first this list file, and fetches the corresponding documents if they are not local files. Then it starts to sequentially send out the documents. When it sees no attendee in the multicast session, it stops automatically the document transfer. At some later time, if it sees that some attendees joined the session, it will restart the transmission. Other session participants, except the sender, generally work in receive-only mode.
Additional settings may be required for the user, for example, to adjust the bandwidth to use, and the interval between two document sendings. These settings are particularly useful for multicast of frequently updated information, such as daily news, weather forecast, etc.
For broadcast of HTML slides or discussion among a group of users, often we need interactivity. This is naturally done with a Web browser. Our application has a built-in HTTP proxy server for this purpose.
This proxy server should be configured as the HTTP proxy in the browser. In this way the user's open operations are directed to our application. The later is charged of fetching the requested documents and sending them to the multicast session. Problems come with user's backward and forward operations. A browser may not load the documents from the server for these operations. In this case, setting both the disk cache size and memory cache size to zero would force the browser to load them from the proxy server. Thus the proxy server, i.e., the multicast application, is able to send these requests to remote participants.
Other user's operations, like mouse motion and scrollbar motion events, are hard to catch as none of the available browsers can report such events to external modules. Thus they are not multicast by our application.
Whereas the proxy scheme allows to catch user's open operations, it is somewhat dangerous since all user's open operations will be multicast, even not intended. Yet other possibilities should be provided. We use a special form of URL, the pipelined URL to allow a user to multicast a document without reconfiguring the HTTP proxy of the browser. It is of the following form:
http://WebCanal.host:port/|http://www.w3.org/
which means the first HTTP server in that line to fetch the URL that follows. Thus URLs in the standard form will not be directed to our application. This method works when the HREF links in the document are relative path names.
Multiple-session participants can send documents at any given time. If they are sending a same document (e.g. http://www.w3.org/) at the same time, currently only the one who started the first takes effect, others are just ignored. A validation check mechanism has to be implemented and is one of our future tasks.
After a user has joined a multicast session, all documents being sent by other participants can be received. But no efforts are made to get documents sent before the current user joined the session.
When documents are received, users are provided with three possibilities for display in a browser: the most recently received document, a list of the documents received in the current session or a list of all received documents. The first could be used for multicast of slides while the others are more suitable when there are multiple senders in a session. The list of received documents is generated in the HTML format on the fly and is automatically updated when new documents arrive. This list is classified according to the sender name and includes the document title. By a simple click on this list, a user can easily visit the document of interest.
To display received documents, our application currently uses a Java applet which is run in the browser. When a new document is received, our application sends a command to the applet. On reception of this command, the applet will request the browser either to show the document, or to show the list of documents depending on the user's configuration.
While multicast, WebCanal sends first the HTML file and sequentially sends embedded objects in the list. At reception, each time an embedded object is received, the displayed HTML document will be refreshed. In our tests, Java objects generally still work with no problem after multicast.
A big problem is with proprietary tags. We are not sure we are aware of all of them. If an unknown proprietary tag introduces a new embedded object, we will have trouble in multicasting it.
The cache mechanism allows some optimization to make a multicast application more network-friendly. Since documents can be cached at receivers, document content will not be sent if it is already sent once in the current session. In this case, only the URL is sent to the session. Upon reception of this URL, those who have one copy in the cache can do faster visualization. Those who joined later the session and thus missed the document content will send a request to the sender to ask the retransmission. This scheme can considerably reduce the data traffic in the case there are documents which have many icons in common. In interactive sending, a user can change this default behavior using the reload command in the browser.
Though we could introduce some good cache management techniques from existing cache servers, we have not done that due to time constraints. Currently there is no really cache management in our application. What we do is automatic and implicit update. That is, when a document arrives, it replaces automatically what is already saved in the cache. In addition, cached documents remain in the disk cache until a user deletes them explicitly using a menu provided by the user interface of our application.
Another mechanism deployed in our cache management is the backup technique. This is to deal with the vulnerability of network links and multicast groups. In a multicast session, participants are potentially dispersed world wide. Due to congested network links or a bad manipulation, a sender may often be lost. So the currently received document should be dropped even a complete copy exists in the cache. The backup technique is used to do recovery on this error. When a document is received, the already cached file (if it exists) is saved as a backup. During the reception, the user can still visit this file. Only after the whole document content is correctly received, the backup file is removed from the cache. Therefore in the case of error transmission, users can at least keep an old version, which is better than nothing.
A main advantage with the cache is that when a user quit the session for some reason and rejoins at a later time, the user keeps a partial state of the session and will gets synchronized faster with the current sending. In addition, the user has the possibility to view the received documents at some future time.
Special efforts have been made to provide an easy tool for end-users, such as a friendly user interface, start-up from sdr, automatic start-up of a reception window in the browser.
Figure 2 shows the user interface of our application. On the left side, a list of participants is displayed. That allows them to know who is currently in the session. If the user clicks on a participant, the related information will be displayed on the right side, such as the name, email and statistic-data as carried in LRMP/RTP control packets. The bottom bar shows the status messages, e.g., the current activity or error message.
Figure 2. WebCanal user interface.
A multicast talk facility is also provided that allows discussion among session participants, like the UNIX talk command. This is particularly useful for getting feedback from receivers in case of problems. The talk window can be activated through the View menu. The multicast talk is implemented on top of LRMP and can be considered as a proof-of-concept application of LRMP.
The options menu allows to configure a number of options, such as enable send and how to display received documents, as described above. The cache menu allows to remove cached elments. Users could display all cached documents in a browser window before performing this operation.
An example of reception window is shown in Figure 3 where the most recently received document is displayed. This window is composed of two frames, the top frame displays the sender name and the document URL. It is also in this frame that the Java applet is running. The bottom frame is used to display the document content or list of documents according to the configuration.
Figure 3. A reception window.
A static and temporary web payload type is used by our application for data encapsulation within RTP. But hopefully a more standard payload type will be used later instead.
LRMP was implemented with configurability in mind. LRMP mainly allows an application to configure three important options:
In some preliminary tests, we artificially introduced up to 50% loss rate at receivers. Statistics are collected via RTCP SR (sender report) and RR (receiver report), as well as LRMP control packets. LRMP worked well under very bad loss rate. Even with large audio and video files, data transfer time and delay are reasonable regarding to the used bandwidth.
While keeping improving the WebCanal application, our future work will be mainly carried out on the following three subjects: