Overview:

With the fast growth of high-speed communication networks, the spectrum of network applications has been enlarged to include new and diverse applications with different QoS requirements. As these applications vary in their bandwidth and delay requirements, it becomes important for the network itself to become aware of the applications' requirements and treat them differently to increase its utilization on one hand, and to minimize the impact of network congestion on the end user perceived quality. Since the network process a large number of network flows (or applications), scalability becomes a key factor in the network performance. Therefore, we propose two new scalable application-aware router mechanisms to enhance the application's perceived QoS. First, we propose a new efficient buffer management scheme called MPFD that is application-aware and achieves the performance of more complex schemes. Although it is generic to any prioritize traffic, we choose MPEG-2 traffic as a demonstration example. Second, we propose a scalable utility-based rate allocation architecture that performs rate allocation according the utility functions provided by the users.

(1) MPFD

There are several buffering management approaches proposed in literature to efficiently support prioritized traffic like video streams. Some approaches are based on introducing a threshold in the buffer such as Partial Buffer Sharing (PBS) and Triggered Buffer Sharing (TBS). These schemes are simple to implement and can provide buffer protection for high priority frames, but the overall performance is low because the buffer is not fully utilized due to the fixed partial buffer space that is allocated to low priority packets. Another priority buffer management scheme is the Push Out Buffer (POB). While this scheme is efficient and fully utilizes the buffer space, it is complex to implement because it requires searching the buffer for low priority packets to discard. The simplicity of threshold-based schemes makes them deployable in intermediate network nodes at the expense of their relatively low efficiency. On the contrary, the complexity of POB scheme makes it inappropriate to be deployed in network nodes despite its efficiency and higher performance.

In this project, we explore a new dropping scheme that combines the properties of both threshold-based schemes, like PBS, and POB. Multi-Priority Frame Discard (MPFD) has features that exists in both POB and PBS schemes. We present this scheme in the context of MPEG-2 video traffic as an example of QoS-sensitive application. MPFD has the simplicity of the PBS scheme in dropping incoming packets upon arrival and has the efficiency of POB in minimizing the number of lost frames (in this example) while keeping the video quality optimal. It also accommodates video traffic characteristics to produce better performance than other dropping schemes. MPFD is based on constructing a virtual buffer that represents the future buffer occupancy using information about future video frames. The virtual buffer occupancy is used to decide whether accepting the currently arriving video frame will cause dropping a future video frame of a higher priority or not.

(2) Utilite

Utility-based rate allocation performs rate allocation with respect to the flow utility, where utility is define as the application-level QoS. This has the advantage of allocating network resources with respect to a metric that is directly perceived by the end users.

Rate allocation mechanisms inherently reside in the core network routers to provide network flows with a share of its resources according to a rate fairness criterion. Basing rate allocation on a fairness criterion that is utility-based is advantageous especially when applications with diverse QoS requirements are sharing the network. we consider simplicity and scalability of the router significant to its performance and need to be considered in rate allocation mechanisms. We, therefore, focus on scalable rate allocation mechanisms in the context of utility fairness.

In this project, we propose Utilite, a scalable utility-based fair rate allocation architecture that can approximate the utility max-min fairness, a fairness approach that is widely used in computer networks. The proposed architecture uses utility information from the sources and allocates rates for flows such that utility fairness is approximated. The architecture is scalable since it does not maintain per-flow state in the network routers. Instead, it leverages the concept of dynamic packet state to realize scalability.

Results / Status:

(1) MPFD

The performance of the algorithms is measured using the goodput metric. Goodput is defined as the ratio of the cells belonging to correctly displayable frames that are transmitted by the node's output link to the total number of cells.

While MPFD is designed to consider dependency between frames, however, PBS and TBS were not. Since we are measuring the goodput (or the usability of transmitted video frames), it will not be fair to compare MPFD with the PBS and POB as they are because their goodput performance will be low. Therefore, we implemented modified PBS, TBS, and TD schemes that are able to perform dependency dropping. We call the modified PBS, TBS, and TD as PBS-D, TBS-D, and TD-D, respectively. Clearly, the goodput performance of PBS-D and TBS-D is better than the original PBS and TBS schemes.

We compared the results of MPFD with four dropping schemes: TD-D, POB, PBS-D and TBS-D algorithms. In Figures 1 and 2, we plotted cell loss probability for all dropping schemes versus normalized output rate with a confidence of 90%. The normalized output rate is the ratio between the output rate and the input rate. It can be looked at as a measure of link congestion. In addition to the results for MPFD with lookahead=10 anchor frames, we plotted results for simple MPFD with lookahead = 1 anchor frame to show the lower performance bound of MPFD. It will be shown below that MPFD with 10 lookahead steps is sufficient to achieve better performance than all threshold-based dropping schemes.

Figure 1

Figure 1 shows the B-frame loss probability for all dropping schemes. The B-frame loss of complete frames in both MPFD and simple MPFD appears to be the smallest of all threshold-based schemes while it achieves a comparable performance of POB scheme. This indicates that the MPFD scheme results in better bandwidth utilization and better video quality than TD-D, PBS-D and TBS-D.

Figure 2

Figure 2 shows the cell loss probability in anchor frames. The simple MPFD results show a loss reduction in anchor frames and better performance than TD-D, but not as good as other threshold-based dropping schemes. In MPFD, however, the anchor frames encountered a loss of 3.5 * 10^-6 only, which is the lowest loss among all dropping schemes including POB.

(2) Utilite

Different scenarios are used to test the proposed architecture. These scenarios are intended to demonstrate the behavior of Utilite under several network situations. Scenarios are generated by changing some simulation parameters such as the number flows in the link, utility function types used, number of congested links, etc. We present two scenarios:

Heterogeneous Flows:

In this case, we have ten flows traversing a link. Each flow uses one of two different utility functions. This scenario shows how Utilite provides same utility for all flows. It also shows that flows with different utility functions are allocated different rates.

Figure 3

Figure 4

Figure 3 shows the link fair utility versus time for the ten flows traversing it. Utilite quickly converges to the max-min fair utility of the link. In Figure 4, it is shown that flow rates are separated into two bands because these flows have one of two utility functions.

Dynamic Flows Entering and Leaving a Link:

In this case, we consider several heterogeneous flows joining and leaving the network link and evaluate the efficiency of Utilite. We show how flows sharing the link will dynamically increase or decrease their rate according the number of flows and the available bandwidth at the link.

Figure 5

Figure 6

Figure 7

We consider a dynamic network condition where the number of flows in the link dynamically changes as shown in Figure 5. Figures 6 and 7 show the aggregate and individual accepted rate and the fair utility for the link, respectively. We notice that the fair utility changes dynamically to adjust the flows rate in order to utilize the link bandwidth. Three different utility functions are used in this case. It is noticed here again the individual rate separation into three bands, most clearly shown between 10 and 25 sec.

Publications & Presentations:

• A. Awad, R. Sivakumar, and M. W. McKinnon,
  ``MPFD: A Lookahead Based Buffer Management Scheme for MPEG-2 Video Traffic.''
  To appear in Proceedings of IEEE International Symposium on Computers and Communications (ISCC), Kemer-Antalya, Turkey, June 2003.

Software Downloads:

People:

• Ashraf Awad (Alumnus)
• Raghupathy Sivakumar (Professor)
• Martin William McKinnon (Professor)

References & Related Work:

(1) MPFD

• edro Cuenca, Antonio Garrido, Francisco Quiles, and Luis Orozco-Barbosa, "Performance Evaluation of Cell Discarding Mechanisms for the Distribution of VBR MPEG-2 Video Over ATM Networks," IEEE Transactions on Broadcasting, 44(2), June 1998.
• C. G. Kang and H. H. Tan, "Queueing Analysis of Explicit Priority Assignment Partial Buffer Sharing Schemes for ATM Networks," Proceedings of IEEE INFOCOM, 2:810--819, April 1993.
• Tao Tian, A. H. Li, Jiangtao Wen, and J.D. Villasenor, "Priority dropping in network transmission of scalable video," Proceedings of International Conference on Image Processing, 3:400--403, Sept. 2000.
• M. Krunz, R. Sass, and H. Hughes, "Statistical Characteristics and Multiplexing of MPEG Streams," Proceedings of IEEE INFOCOM, 2:455--462, April 1995.
• J. R. Li, X. Gao, L. Qian, and V. Bharghavan, "Goodput Control for Heterogeneous Data Streams," Proceedings of NOSSDAV, June 2000.

(2) Utilite

• Z. Cao and E. Zegura, "Utility Max-Min: An Application Oriented Bandwidth Allocation Scheme," INFOCOM, 2:793-801, March 1999.
• I. Stoica, S. Shenker, and H. Zhang, "Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks," SIGCOMM, 28(4):118-30, October 1998.
• Scott Shenker, "Fundamental Design Issues for the Future Internet," JSAC, 13(7):1176-88, September 1995.