3. Buffering Strategies

3. Buffering Strategies

Buffer management is a crucial part in the NetMedia system. There are two main components: server and client buffers.

3.1 Server Flow Control Buffer

A straightforward server buffer is designed for each stream to perform fast delivery of the stream from the disk to the network. Figure 33.3 shows the structure of a server buffer for a stream. A server stream buffer is a circular list of items. Each item may contain one packet. Each server stream buffer has the following characteristics:

• One producer and one consumer: the producer writes packets to the buffer and the consumer reads from the buffer.

• First in first out: packets which are written in first will be read out first.

Figure 33.3: Server flow control buffer design.

Specifically, each server stream buffer has two pointers: read pointer (readp) and write pointer(writep). Items from readp to writep are readable; spaces from writep to readp are writable.

Since a server buffer is designed for flow control of the data from the disk to the network, the size of a server buffer can be relatively small. In the implementation of NetMedia, the size of the video buffer is 100 video packets, where each video packet is 1024 bytes, and the size of the audio buffer is 20 audio packets, where each audio packet is 631 bytes.

3.2 Client Packet Buffer

Client buffer management is a central part of the NetMedia framework. In contrast to the server buffer that must support fast delivery of the stream from the disk to the network, the purpose of a client buffer is to take care of network delays and out of order arriving packets, and to efficiently support user interactions.

The novelty of the client buffer management is the support of interactivity requests like backward-playback or seek. The difficulties experienced with interactive support in video streams is the video encoding used by most advanced compression techniques [28]. Several works propose methods for implementing forward but do not adequately deal with backward playback. To solve the decoding problem, an approach [48] is proposed to use a separate file for each video stream, preprocessed for backward playback. The advantage is that it does not need special client buffer management. The disadvantage is that a separate file must be created for all video streams, increasing the storage used in the system, and hence the cost.

Our approach is to let the client support interactive requests rather than the server. As frames of video are processed at the client, rather than discard the displayed frames, the client saves the most recent frames to a temporary buffer. The motivation is to reduce the bandwidth requirements of a network in exchange of memory at the client site, because we expect an increase in network load in the next years in comparison to falling memory prices.

The client buffer design for interactivity functions is the use of a circular buffer. The model proposed here allows all interactive functions to occur at any time with an immediate response time. If the buffer is large enough the interactive request for backward playback can be fed directly out of the buffer instead of requesting a retransmission from the server.

The interactive buffer for a stream has two levels: packet and index buffers. The first level is the packet buffer. It is a set of fixed-size packets. Each packet has one pointer, which can be used to point to another packet, so we can easily link any set of packets by pointer manipulation (For example, all packets for a particular frame.) A list of free packet slots is maintained.

The second level for audio buffer is the index buffer of a circular list in which each entry records the playback order of the packet. Each packet in an audio stream has a unique number-PacketNo, which indicates the order of the packets in the whole stream. For the video buffer, each index in index buffer points to one frame (which is a list of ordered packets within the frame). We define the point with the minimal packet/frame number as MinIndex and the point where we read data for playback as CurrentIndex. Both indices traverse the circumference in a clock-wise manner, as shown in Figure 33.4 (Note that in this figure, since the buffer is for a video stream, the two pointers are named as MinFrameIndex and CurrentFrameIndex.)

Figure 33.4: Client video buffer.

The distance between MinIndex and CurrentIndex is defined as history area. A packet is not removed immediately after it's displayed. It's removed only when some new packet needs space. So valid indices from MinIndex (inclusive) to CurrentIndex (not inclusive) point to the packets/frames which have been displayed and haven't been released yet. (The data may be used to support backward later.) To keep track of the forward playback capabilities, we introduce the packet/frame with the maximum number as MaxIndex. Note that MaxIndex is always between CurrentIndex and MinIndex. The distance between CurrentIndex and MaxIndex is defined as future area. Using the history and future areas the user has full interaction capabilities in the two different areas.

When a new packet arrives at the client site, the system checks its packet/frame number (denoted seqno) and decides if the packet can be stored. The valid range of the packet/frame numbers is defined as follows:

(33.1)

If the packet has a packet/frame number outside the above range, then it is considered as packet loss and discarded. Otherwise, the packet is stored in a packet slot either taken from the free packet slot list or obtained from releasing some history data. Note that once some history data is released, the MinIndex will be updated.

To increase the decoding speed of compressed motion predicted frames we introduce the use of a decode buffer. The MPEG compression scheme [28] introduces interframe dependencies among I, P and B type frames. To decode a certain frame, previous or future frames might be needed. For example, given the following frame sequence:

frame-type:	I	B	B	P	B	B	P	B	B	I
frame#:	1	2	3	4	5	6	7	8	9	10

Frames 1,4 and 7 must be decoded before frame 9 can be decoded. To speed up the decoding process for the backward playback, we cache the decoded frames within an I to I frame sequence. In case of dependencies we might be able to feed the needed frames out of the decode buffer instead of calling the decoding routine multiple times.

To implement the above buffer design and allow interactive requests to be fed from their local buffer we need to set a reasonable buffer size for the index and packet buffers. We introduce two consideration factors: MAX_INTERACTIVE_SUPPORT and REASONABLE_DELAY. MAX_INTERACTIVE_SUPPORT defines the longest playback time we expect to be buffered in the client for interactive support, thus defining the size of the index buffer. REASONABLE_DELAY defines the delay within which most packets will pass over the network, thus defining the size of the packet buffer. In the implementation of NetMedia, REASONABLE_DELAY is defined to be 2 seconds. The size of MAX_INTERACTIVE_SUPPORT depends on the amount of forward/backward play support (can vary from 10 sec to 5 minutes or more, depending on the memory at the client).

At the server site, video frames are normally represented in encoding order to make it easier for the decoder to decode in the forward playback. This complicates the decoding of frames for backward playback. Our streams are transmitted in display order to achieve the minimal distance among the dependent frames for both forward and backward playback decoding. The advantage is that our scheme at the client site has uniform design and the same performance for both forward and backward playback. With the use of the decoding buffer and our network control algorithms, we can control the amount of data in the future or backward area in our buffer. This allows the user to specify the amount of interactivity support that he wants for backward or forward playback without immediate request to the server.

Using the above buffer design we can utilize the history and future areas to feed interactive requests directly from the local buffer. If the request does not exceed the cache, the server will not be notified. This will highly reduce the scalability problems faced by the server in case of multiple interactivity requests. Access outside the history or future area must be handled by redirect streaming from the server, but the probability of this case can be drastically reduced by the amount of the buffer size given at the client.