A Universal Stabilization Algorithm for Multicast Flows with Network Coding

doi:10.1109/TCOMM.2012.102512.120046

Return

A Universal Stabilization Algorithm for Multicast Flows with Network Coding

2013-02-01

PRE

Cheng‐Shang Chang

Duan‐Shin Lee

DOI：10.1109/TCOMM.2012.102512.120046

Original

Original request for help

Save

Abstract

En 中文

In this paper, we consider a network that supports multiple multicast flows with network coding. It is well-known that network coding can be used to increase the throughput of a delay-free network. However, as there are multiple multicast flows in the network, packets might be delayed due to contention. As packets from the same flow have to be synchronized for network coding, additional buffers, known as synchronization buffers in the literature, are required. In certain networks, such as multistage interconnection networks in switch fabrics [17], the size of internal buffers could be quite limited. One of the key contributions of the paper is to propose a packet scheduling algorithm so that synchronization buffers can be bounded by a finite constant that only depends on the maximum hop count of the flows. We also show that our scheduling algorithm does not cause any throughput degradation as it can stabilize the network for any admissible traffic. Moreover, our algorithm is universal and it does not require to know the rates of the flows in the network. The main idea of our algorithm is to introduce fictitious packets in the dynamic frame sizing algorithm recently proposed in [4], [19] for stabilizing switches and wired networks (without network coding). By so doing, packets that might be stalled in synchronization buffers can be flushed out. We show that the number of fictitious packets in each frame is also bounded by a finite constant that only depends on the maximum hop count.

Keywords:

Scheduling

stability

networks

network coding

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.