![[INET 2000]](/web/20160103041004im_/http://www.isoc.org/inet2000/cdproceedings/inet00sm.gif)
![[ Up ]](/web/20160103041004im_/http://www.isoc.org/inet2000/cdproceedings/up.gif)
![[Prev]](/web/20160103041004im_/http://www.isoc.org/inet2000/cdproceedings/prev.gif)
![[Next]](/web/20160103041004im_/http://www.isoc.org/inet2000/cdproceedings/next.gif)
Layered encoding is suitable to adapt the quantity of data according to the capacity of each sub-network in Internet Protocol (IP) multicasting. However, packets sent without any artifice on the order are not appropriately treated even if their priority levels are given. We ascertain this phenomenon by simulation and propose a method to control the packet order to properly transmit the data according to the tagged priority levels.
We implemented an MPEG (Moving Picture Experts Group) stream playback system, which has the mechanisms of layered encoding and packet order control.
We also propose and implement a mechanism that a router selects packets according to priority levels. We further study a mechanism in the case that Quality of Service (QoS) control is available.
These mechanisms enable a receiver to receive a proper quality of information according to the bandwidth of a network, by means of layered encoding, controlling packet order and layered transmission in IP multicasting.
The Internet will be further utilized to transport multimedia data. It will be possible to broadcast multimedia data over the Internet, when a high-speed network is available.
The difference in network bandwidth of links causes packet loss when multimedia data is transmitted by IP (Internet Protocol)-multicasting on the Internet. It causes serious influences such as pauses of audio and disorder of video. We adopt layered encoding and layered transmission to solve this problem. Each packet is prioritized according to the layer it belongs to using this method. However, when the packets are in the same layer burst, packets are sometimes not transmitted in accordance with their priority.
We propose a method of controlling the packet transmission order in order to avoid bursting. This allows the router to selectively transmit packets with a higher priority when the sending host sends them using this method.
In multimedia broadcasting, multiple users can receive data simultaneously and play it back on their own player with a display and a speaker. Though it is similar to TV broadcasting, in multimedia broadcasting we can receive not only motion pictures and audio sound but also character data, information of TV programs, some application programs and so on. TV programs will become more interactive when the broadcasting station and audiences can communicate with each other. Anyone can also easily broadcast his own multimedia data because he does not have to set up a large antenna.
We adopt IP multicasting as a transmission method instead of IP unicasting because of its scalability, that is the ability to function normally when the number of receivers increases greatly. Here all a sender has to do is to send data once to an IP-multicast address, and the data is transmitted to all receivers by being copied onto appropriate routers on the path.
A problem occurs in IP multicasting in that not all receivers can necessarily obtain the complete data, because each of them has different capability for data reception. Packet loss occurs when packets are transmitted on a link with narrow bandwidth. This causes serious influences such as pause of sound and disorder of pictures. Packet loss occurs at the points on the route where the bandwidth is narrow. This is unavoidable even if the bandwidth is reserved using Quality of Service (QoS) guarantee.
We utilize a layered encoding mechanism which can reduce the amount of data dynamically in accordance with the bandwidth of a link to alleviate the packet loss. Layered encoded data consists of information of lowest quality and the difference data which allows the information to be upgraded to a higher quality. Some receiving hosts that have enough bandwidth receive all the layers, and they decode information with the highest quality. Others decode lower quality information using some of the layers when it cannot get all the difference data. This controlling method is called "layered transmission" which adjusts the amount of data transmission according to the bandwidth.
Data encoded in the MPEG (Moving Picture Experts Group) format is layered-transmitted in our system. We explain a method of layering encoded MPEG data in this section. Note that the higher the priority, the smaller the priority number.
An encoding method for multimedia data such as MPEG handles one or more media, e.g., audio and video. Generally, the audio layer should be highly prioritized, if both audio and video data are transmitted simultaneously. For this purpose, data is encoded so that multiple media are separated into individual layers each with an independent priority.
It is possible to assign priorities so that "a low quality audio has the highest priority, while a low quality video has a higher priority than a high quality audio" occurs, if each medium is divided into multiple layers.
Control of the following qualities is considered for layered-encoding video streams: the number of frames per second and the quality of each frame.
Consider a layered-encoding method based on the number of frames per second. The MPEG data consist of three types of pictures: I, P and B. One whole image can be decoded by just an I-picture, since an I-picture is independent of the other two types of pictures. A P-picture depends on an I-picture because it contains difference data obtained from the I-picture. A B-picture depends on both of the P- and I-pictures. Thus, the MPEG data can be easily separated into three layers. The three layers corresponding to I-, P- and B-pictures are assigned with priority 0, 1 and 2, respectively.
This method has the advantage of layering already-encoded data in the MPEG format. However, the defects are that it strongly depends on the MPEG format, and the data cannot be divided into more than three layers when using only this method. When four or more layers are required, additional methods such as the layered encoding depending on the quality of pictures are needed. This method is explained in the next section.
During MPEG data compression, data provided by means of Discreet Cosine Transform (DCT) are arranged in the order of their spectrum frequencies. The higher the frequency of an element, the more detailed information of an image is included. An image data is divided into multiple layers according to its frequency bands by utilizing this feature. A higher priority layer contains lower frequency elements, while a lower priority layer contains higher frequency elements. Receivers can decode high-quality video if they can receive data from lower priority layers, but they can decode only low-quality video if they receive data only from higher priority layers.
In this section, we propose a method of controlling the packet transmission order for layered-encoded data.
An instantaneous rise of the transmitting rate occurs when packets of the same layer are sent in a row. Some packets may be discarded at a router even when the average rate is suitable for a long period, if the bandwidth is momentarily overloaded. Thus, we should control the order of packet transmission in order to keep the packet sending rate regular even during a short period.
We verified that the packet loss ratio varied with the control of the packet transmission order through simulations. First, we simulated under the following conditions:
Note that packets sent by other hosts were not mixed in this simulation.
Table 1 shows the packet loss ratio at each layer with two types of transmission orders (A and B). There are five priorities indicated by the number.
Table 1: Packet loss ratio at each layer
| Transmission Order (Type) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 000111222333444 (A) | 0% | 33% | 33% | 33% | 100% |
| 012340123401234 (B) | 0% | 0% | 0% | 100% | 100% |
It is shown that there is a big difference in the packet loss ratio between type (A) and type (B). As the ratio between the receiving rate and the transmitting rate is 5 to 3, a router is expected to transmit data with the three highest priorities theoretically.
The router discarded a packet with the first or second priority in the case of type (A), while it could transmit all packets with priorities from the lowest to the second in the case of type (B).
The receiver cannot utilize data from lower priority layers unless it already obtains data from the higher priority layers. Therefore, type (B) is superior to type (A).
The results of the simulation show that a router cannot help transmitting data useless for video decoding, if the packet transmission order is inappropriate. The results also show that a router transmits packets according to the priority order if the transmission order is controlled, and thus the network resource can be utilized effectively.
Such phenomenon does not occur if the queue length is long enough. The necessary length of the queue is eight or more in the case of type (A) and three or more in the case of type (B), according to the results of other simulations. Generally, it costs much more to implement large queues at a router. Thus, the packet transmission order should be controlled to reduce the queue length.
We call a set of data in which the packet transmission order is reshuffled a "group." The packet transmission order is not reshuffled between groups. It is easy to determine the transmission order in a group, if the number of packets at all the layers are the same. These numbers are, however, different from each other, because the amounts of the data are different at each layer.
We propose a method of determining the packet transmission order, under this kind of condition. The following three suggestions are presented in this article:
The purpose of the first suggestion is that transmission of packets with high priorities should be ensured even if the bandwidth of the network is narrow. This is because they include important information.
The second suggestion deals with the problem that a router cannot appropriately forward packets if the packets of the same layer are fed into it continuously. The reason is as explained before.
We still have to consider the third suggestion. Some packets are discarded and the remaining packets are transmitted, when congestion occurs at a router. These remaining packets are to be transmitted at even intervals. Figure 1 (A) and (B) shows examples of these. Packets were transmitted more orderly in (B) than (A) after packets of the second layer were discarded. Such transmission order can be determined by considering the order of the packets at the adjacent layers. We show an algorithm that determines the order of all packets by taking our three suggestions into consideration.
Figure 1 (A): An example packet transmission order (A)
Figure 1 (B): An example packet transmission order (B)
N is the number of layers and Pn is the number of packets at the n-th layer. Buffer B0 whose size is b0 is prepared in the initial state, where bn indicates (SIGMAni=0 Pi). The values of all elements in the buffer are set to priority 0. The following procedure is repeated, as n = 0 in the initial state:
Detailed processing of (2.) is that the value of the j-th element in Bn is set to the (FLOOR( bn+1/bn))-th element in Bn+1, where 0 <= j <= (Bn - 1). Packets with one priority lower are added in process (3), and in process (2) of the next round they are ordered at constant intervals. The order is determined using this procedure, and the transmission is well-ordered not only at one layer but also between adjacent layers.
Figure 2 shows the determining process of a transmission order under the condition that the three layers, which have the highest, medium and the lowest priorities, consist of two, three and five packets, respectively. The sending host sends packets at a constant rate in accordance with the determined order.
Figure 2: Process of determining transmission order
The method proposed in the previous section is effective only for routers that handle packets with priorities. However, this kind of router is not generally installed. We discuss the following two types of implementations for this kind of router in this section:
A router generally has queues for each output interface. Received packets from input interfaces are transferred to the output queues. The router then outputs the packet at the head of the queue. The queue overflows when the router has received more packets than it can send for the moment. This condition is called congestion.
Packets with the lowest priority must be discarded when congestion occurs. The oldest one in the queue should be discarded if there is more than one packet with the lowest priority. Reshuffling of the transmitted packets should be avoided, because the order has already been properly determined by the sender.
Assume routers with QoS support have individual queues for every QoS reserved route. Although this is different from routers without QoS support, the process of the queues is the same for routers with QoS support when congestion occurs.
The following two types of reserving methods are possible:
The layered transmission can be more easily performed using the former, because the quality of the information can be controlled just by changing the number of routes. The former, however, consumes more network resources than the latter, since a router must manage all layers by means of reserving routes, policing and shaping packets, and so on.
A router can transmit packets appropriately when the packet transmission order is controlled according to the proposed method, even in the latter case. In addition, the required queue size can be decreased when the order is controlled as described in section 4.1. Thus, a router can utilize the network resources by controlling the packet transmission order.
We implemented a system that transmits layered data in the MPEG format on FreeBSD (See Figure 3 where implemented modules by us are shown in gray hatch) [MEDIA1997].
Figure 3: Implemented system
The sending host encodes data in MPEG at first. It then controls the packet transmission order, and sends these packets after shaping them. The system handles only video data and encodes them into three layers according to their picture types. The algorithm shown in Section 4 is used for the control of the packet transmission order.
The data packets are IP multicasted using the following protocols over the IP layer.
The priority of each packet is contained in a Type Of Service (TOS) field of the IP header. The MPEG data are packed into (2) and (3). Some newly created fields are used in (3) to contain the layer information.
We implemented a layered-transmission router with ALTernate Queuing (ALTQ)[ALTQ1998]. Usage of ALTQ enables the length of queues or the bandwidth of the network to be varied freely.
The receiving host reorders received packets into the original packet order and decodes them using the general MPEG decoder. If there are packets missing in the frame, the frame is discarded and skipped. Other frames may also be discarded and skipped if they depend on another discarded frame. This means that some B-pictures are not displayed when the related P-picture is discarded, even if all packets of the B-pictures are obtained. Similarly, no pictures in a Group Of Pictures (GOP) are displayed if the I-picture in the GOP is discarded.
Our system is evaluated using the packet transmission order control.
Figure 4 shows the environment of our experiments. The sending host sent the layered MPEG data with IP multicasting. The bandwidth from the router to the receivers was limited arbitrarily, while the bandwidth from the sender to the router was assumed wide enough. The router discards packets with the lowest priority when congestion occurs.
Figure 4: Experiment environment
The encoded MPEG data of 1.2Mbps are layered-encoded and transmitted. The video rate is 30 frames per second, and one GOP has 15 frames consisting of one I-picture, four P-pictures and ten B-pictures. Table 2 shows the amount of the data at each layer.
Table 2: Ratio of the amount of data in each layer
| Priority (MPEG Picture Type) | |||
|---|---|---|---|
| 0 (I) | 1 (P) | 2 (B) | |
| Ratio of the amount of data | 16% | 46% | 38% |
| Number of packets | 533 | 1660 | 1550 |
| Ratio of the number of packets | 14% | 44% | 41% |
Data at all layers require a bandwidth of 1.3Mbps for transmission, including IP, UDP and RTP headers. Data are sent in 30 seconds and 3,743 packets are sent in this period.
A bandwidth of 0.8Mbps is required for transmitting all packets of I- and P-pictures in this environment. Thus, we limited the bandwidth of the route to 0.8Mbps and changed the queue length from one to ten. Figure 5 (A) and (B) shows the results.
Figure 5(A): Ratio of transmitted packets in each layer (packet transmission
order controlled)
Figure 5(B): Ratio of transmitted packets in each layer (packet transmission
order uncontrolled)
Packets with higher priorities are transmission guaranteed by controlling the packet transmission order. Almost all packets with the lowest priority are discarded and packets with higher priorities are transmitted when the queue length is five or more.
On the other hand, packets with higher priorities are also discarded when the transmission order is uncontrolled. If the queue length is increased to over 30, the result of using uncontrolled order can be improved. (See Figure 6.)
Figure 6: Ratio of transmitted packets in each layer (packet transmission
order uncontrolled)
These results show that a router can process packets efficiently by controlling the packet transmission order when congestion occurs.
Other results for the cases where the bandwidth is changed into values other than 0.8Mbps also show that packets can be transmitted appropriately with a small queue size when the packet transmission order is controlled.
We evaluated the number of frames that the receiving host was able to decode. The experiment environment and the transmitted data are the same as those in the previous section. The receiver does not play back frames whose data are not completed. Neither does it display frames that depend on other frames that are not played back.
The number of frames is 900 (30-second motion pictures with 30-frames-per-second data). We counted the number of displayable frames by controlling the packet transmission order and changing the following two parameters:
Figure 7 (A) and (B) shows the results for the cases where the packet transmission order was controlled and uncontrolled, respectively. The number of displayable frames is 900, if the bandwidth of the network is 1.3Mbps or more. The receiver can play back more pictures when the transmission order is controlled, even if the bandwidth is limited. On the other hand, the number of displayable frames decreases rapidly when the transmission order is uncontrolled, even if the bandwidth becomes just a little bit insufficient. This is because either or both of more important I- and/or P-pictures are not transmitted.
Figure 7(A): Number of displayed frames (packet transmission order
controlled)
Figure 7(B): Number of displayed frames (packet transmission order
uncontrolled)
These results show that the network can be more efficiently utilized by controlling the packet transmission order.
We showed that the layered encoded data can be properly transmitted by controlling the packet transmission order, and proposed an algorithm to control the transmission order. We also implemented a system for transmitting, receiving and displaying MPEG video data, based on our proposal. We verified through experiments that the quality of the MPEG video can be improved by controlling the packet transmission order.
Our future subjects are implementation of a system that also handles the quality of frames and audio streams, and further study on delay and buffer management at a receiver.