Network Coding is a critical technique when designing next-generation network systems, since the use of network coding can significantly improve the throughput and performance (delay/reliability) of the system. In the traditional design paradigm without network coding, different information flows are transported in a similar way like commodity flows such that the flows are kept separated while being forwarded in the network. However, network coding allows nodes in the network to not only forward the packet but also process the incoming information messages with the goal of either improving the throughput, reducing delay, or increasing the reliability. Specifically, network coding is a critical tool when designing absolute Shannon-capacity-achieving schemes for various broadcasting and multi-casting applications. In this thesis, we study the optimal network schemes for some applications with less restrictive network models. A common component of the models/approaches is how to use network coding to take advantage of a broadcast communication channel.<div><br></div><div>In the first part of the thesis, we consider the system of one server transmitting K information flows, one for each of K users (destinations), through a broadcast packet erasure channels with ACK/NACK. The capacity region of 1-to-K broadcast packet erasure channels with ACK/NACK is known for some scenarios, e.g., K<=3, etc. However, existing achievability schemes with network coding either require knowing the target rate in advance, and/or have a complicated description of the achievable rate region that is difficult to prove whether it matches the capacity or not. In this part, we propose a new network coding protocol with the following features: (i) Its achievable rate region is identical to the capacity region for all the scenarios in which the capacity is known; (ii) Its achievable rate region is much more tractable and has been used to derive new capacity rate vectors; (iii) It employs sequential encoding that naturally handles dynamic packet arrivals; (iv) It automatically adapts to unknown packet arrival rates; (v) It is based on GF(q) with q>=K. Numerically, for K=4, it admits an average control overhead 1.1% (assuming each packet has 1000 bytes), average encoding memory usage 48.5 packets, and average per-packet delay 513.6 time slots, when operating at 95% of the capacity.</div><div><br></div><div>In the second part, we focus on the coded caching system of one server and K users, each user k has cache memory size M<sub>k</sub> and demand a file among the N files currently stored at server. The coded caching system consists of two phases: Phase 1, the placement phase: Each user accesses the N files and fills its cache memory during off-peak hours; and Phase 2, the delivery phase: During the peak hours, each user submits his/her own file request and the server broadcasts a set of packet simultaneously to K users with the goal of successfully delivering the desired packets to each user. Due to the high complexity of coded caching problem with heterogeneous file size and heterogeneous cache memory size for arbitrary N and K, prior works focus on solving the optimal worst-case rate with homogeneous file size and mostly focus on designing order-optimal coded caching schemes with user-homogeneous file popularity that attain the lower bound within a constant factor. In this part, we derive the average rate capacity for microscopic 2-user/2-file (N=K=2) coded caching problem with heterogeneous files size, cache memory size, and user-dependent heterogeneous file popularity. The study will shed some further insights on the complexity and optimal scheme design of general coded caching problem with full heterogeneity.<br></div><div><br></div><div>In the third part, we further study the coded caching system of one server, K= 2 users, and N>=2 files and focus on the user-dependent file popularity of the two users. In order to approach the exactly optimal uniform average rate of the system, we simplify the file demand popularity to binary outputs, i.e., each user either has no interest (with probability 0) or positive uniform interest (with a constant probability) to each of the N file. Under this model, the file popularity of each user is characterized by his/her file demand set of positive interest in the N files. Specifically, we analyze the case of two user (K=2). We show the exact capacity results of one overlapped file of the two file demand sets for arbitrary N and two overlapped files of the two file demand sets for N = 3. To investigate the performance of large overlapped files we also present the average rate capacity under the constraint of selfish and uncoded prefetching with explicit prefetching schemes that achieve those capacities. All the results allow for arbitrary (and not necessarily identical) users' cache capacities and number of files in each file demand set.<br></div>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/14161811 |
| Date | 12 March 2021 |
| Creators | Chih-Hua Chang (10214267) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/thesis/Optimal_Network_Coding_Under_Some_Less-Restrictive_Network_Models/14161811 |
Page generated in 0.0022 seconds