ECE 50863: Computer Network Systems

Class Overview

This graduate class focused on understanding, designing, and testing computer networks and network protocols. It consisted of discussion of current network architectures and protocols as well as three labs were I designed parts of networks myself. Given the simulated nature of these labs, and the goal being mostly conceptual, they where all implemented in Python. I also read several research papers on the topics we were covering.

Course Content

Network Stack and Routing SSL/TLS TCP UDP IPv4 Ethernet Hubs, Switches, and Routers Spanning Tree Algorithm Distance-Vector Routing Link-State Routing Inter Domain Routing BGP	Transport Layer Accumulative Acknowledgment Selective Acknowledgment Negative Acknowledgment Flow Control RTT Approximation TCP Tahoe and Reno Cubic TCP TCP BBR Explicit Congestion Notification Weighted Fair Queueing
Video Streaming Adaptive Bitrate Algorithms Buffer-Based ABR Algorithms Model Predictive Control ABR Algorithms Variable Bitrate Encoding	Software Defined Networks Management, Control, and Forwarding Planes OpenFlow Programmable Switches Software-Driven Wide Area Network

Papers

• End-To-End Arguments in System Design (J. H. SALTZER, D. P. REED, and D. D. CLARK)
• A Buffer-Based Approach to Rate Adaptation: Evidence from a Large Video Streaming Service (Te-Yuan Huang, Ramesh Johari, Nick McKeown, Matthew Trunnell, Mark Watson)
• A Control-Theoretic Approach for Dynamic Adaptive Video Streaming over HTTP (Xiaoqi Yin, Abhishek Jindal, Vyas Sekar, Bruno Sinopoli)
• Achieving High Utilization with Software-Driven WAN (Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Vijay Gill, Mohan Nanduri)

Labs

Lab 1: Software Defined Network

In the first lab, I built a simple control layer for a software defined network. This lab was meant to help students transition from undergraduate to graduate labs, so it was more simplistic than future labs. The controller simply used Dijkstra's algorithm on latencies to find the quickest path between switches. Each switch would send keep alive packets to both the controller and its neighbors. These packets would also inform the controller what neighbors it could reach. Upon a timeout, the network would assume a topology change, and the controller would update the paths accordingly. If a switch came back online, the controller would again update the paths accordingly.

Lab 2: Transport Layer Protocol

This lab had me build a transport layer protocol and optimize its performance for "goodput" (throughput minus any overhead) and overhead. It was tested over a simulated network which randomly (uniform) dropped or swapped packets. The rate of dropping could be controlled for different tests. We initially build a stop and go protocol (send packet, wait for ACK, then send next packet), then optimized from there.

Features I Implemented

• Cumulative ACK scheme. Retransmission only on timeout. ACK sent on any packet received, or if no packet received after timeout. More data sent on receiving an ACK. Multiple ACKs may be received before window is updated, particularly if the last window or retransmissions are still being sent.
• Round trip time (RTT) estimator similar to RFC 6298.
  
  • Uses exponential smoothing to calculate an approximate RTT and RTTVAR (variance) from previous packets, then uses both to create output RTT.
• Window Size using RTT and Bandwidth (Bandwidth from configuration)
• A selective ACK scheme in addition to Cumulative ACK Scheme. Up to 4 ranges, prevents unnecessary retransmission and allows window to grow to 1.2x. Window size is capped to keep total buffer size finite.
• Packet recovery through parity packets.
  • After every 10 full sized packets, one parity packet is sent. These 10 packets ond the parity packet form a parity group
  • One packet can be dropped from a parity group without slowing down transmission.
  • The data, sequence number, and EOF bit of the parity packet are the XOR sum of all corresponding bits of the packets in the group. The parity group also includes the number of packets in the parity group.
  • Each packet in the group carries the group number. Group 0 is reserved for no parity group.
  • Parity groups expire after all packets in the group are received or 1 second of inactivity.

Sensitivity Table

Bandwidth = 200,000 bytes/s, One Way Propagation = 0.100s, mean[standard deviation]

	5% loss and 5% reordering	2% loss and 2% reordering	No loss and no reordering
Goodput (bytes/s)	107,087[10,101]	142,528[8,616]	156,707[764]
Overhead (% of bytes sent)	13.5[1.15]	11.4[0.895]	10.1[0.0000]

Ablation Table

Bandwidth = 200,000 bytes/s, One Way Propagation = 0.100s, Loss and Reordering = 2%, mean[standard deviation]

Design Alternative	Goodput (bytes/s)	Overhead (bytes)
Default	142,528[8,616]	11.4[0.895]
Disable parity	113,037[6,802]	36,587[8,925]
Parity for every 40 packets	116,104[10,505]	50,697[8,873]
Parity for every 20 packets	132,257[18,356]	59,903[10,307]
Disable Selective ACK	131,872[10,695]	125,427[36,979]
Disable Selective ACK window growth	138,645[9,146]	71,880[3,899]
Allow Selective ACK window growth up to 1.3x.	133,117[10,295]	80,566[8,812]
Enable variable window size (RTT)	126,750[5,722]	78,604[9,394]
Disable variable timeout (RTT)	150,269[6,208]	65,556[822]

Results Discussion

• The cumulative ACK and window scheme provided the largest performance improvement over stop and go.
• The parity reconstructor provided the largest performance improvement over the cumulative ACK scheme.
  • In this system, packets are lost at random with equal probability. This allows a parity scheme to replace most of the lost packets without the need for retransmission. This reduces the number of slow timeouts and resent data. This would likely be less effective if the packets dropped were grouped together.
  • This feature negatively impacts performance on a perfectly reliable connection. Given that this is redundancy, it is sacrificing overhead for goodput. Using larger parity groups decreases overhead and goodput. With my base setup, parity adds an overhead of around 10%.
  • This adds redundancy on the packet, not data level. This could affect performance in several interesting ways.
    • A positive of this is that it assumes most but not all packets are of the same size. For a data level implementation, one must assume all packets are the same size, or send 2 parity packets each time to account for the offset of a lost packet relative to the data.
    • A negative of this is that the data needed to decode a parity packet may be received, but this system has no way to know that is the packet needed to decode the parity and get the correct output, making this potentially less effective.
  • This feature allows a packet to be “received” later than it should be based on network conditions. This could affect RTT estimations and cause fast retransmit to transmit when it is not needed.
  • Earlier I had some other issues that made the parity scheme less effective, mainly window size based on estimated RTT.
• Next most important was the selective ACK scheme.
  • Although this had a minor effect on goodput, it had a much larger effect on overhead. This is likely because it prevented the retransmission of already received packets.
• The next improvement is the selective ACK growing the window by a small amount.
  • This provided a small improvement to goodput. This allows the time following a retransmission to be more effectively used. To large of an additional window size often led to buffer overflows, so the performance improvement was minimal.
• Finally, a fix I made to my timeout system was also important to most of the improvements (Appendix A). It fixed some flaws in things such as the selective ACK scheme.
• In my final implementation, the RTT estimator hurt performance.
  • In earlier implementations, which had more variable RTT’s (Appendix A), it did positively affect the speed.
  • I decided to leave it in my final design to give a somewhat more realistic perspective on the goodput.
• Using the RTT estimator for window sizes also hurt performance.
  • This is likely because the RTT estimator may estimate too high at some points, causing the window to grow too large, and causing packets to be dropped because of a full buffer.
  • A potential solution to this would be to use the RTTVAR to decrease the window size. This would prevent a sudden jump in RTT from increasing the window size too much.
• Other Potential Features
  • A dynamic window size would be an interesting feature. It would make this more realistic, but simply using the RTT was not effective.
  • A reliability measurement of the network to control the number of packets in a parity group could also improve performance on diverse networks.
  • Some form of fast retransmit could also be implemented, but it would have to take into account parity groups. This would add significant complexity. I attempted to implement this, but upon realizing its interaction with the parity groups, I decided against perusing it.

Discussion of RTT and Timeout in this Simulation

My initial implementation of timeouts and RTT estimation had a major flaw. When sending more than one packet in a row, it would not consider the time it takes to send the previous packets. This was particularly disruptive on the first window, when all packets are sent at once. Because of this, the RTT of each packet would increase linearly until the end of the first window. For further windows, usually only a few packets would be sent at a time, making this less of an issue. This made the RTT estimator for the timeout improve the goodput by avoiding unnecessary timeouts. This would also imply that on a network were the RTT changed or is not known, the RTT estimator may still be useful. My final implementation mostly fixes this flaw, which helps to improve the goodput. Because of the way the emulator is set up, it would likely be impossible for me to fully fix this flaw. This flaw came originally from the assumption that the Monitor.send method would block until the simulated transmission of the packet was complete. In the real world, this type of issue may also be seen if a fast link is then bottlenecked by a slow link. It may be prudent to consider its effects and better solutions to it outside the confines of this simulation.

Lab 3: Adaptive Bitrate (ABR) Algorithms for Video Streaming

In this lab, I tested several different adaptive bitrate algorithms for video streaming as well as making our own. The general goal was to maximize a "quality of experience" (QoE) metric. We implemented the BBA-2 algorithm from "A Buffer-Based Approach to Rate Adaptation" and the RobustMPC algorithm from "A Control-Theoretic Approach for Dynamic Adaptive Video Streaming over HTTP". Finally I implemented my own algorithm.

My Algorithm

My algorithm would receive the throughput off the last chunk downloaded (Previous Throughput), the bitrates of upcoming chunks (Upcoming Bitrates) (video has variable bitrate), and the buffer level form the simulator.

• Throughput Predictor: The harmonic mean predictor with error adjustment from RobustMPC was used
• Buffer Sizer
  • The target buffer size is the sum of a throughput-based buffer size, a bitrate-based buffer size, and a constant minimum size. It is capped at the maximum buffer size.
  • The minimum size is set to 2 seconds
    • It needs to be at least twice a chunk length to avoid constant rebuffering.
  • The bitrate-based buffer size is calculated similarly to the revisor size in BBA-2. The main difference is that as it sums (towards the future), it takes the maximum sum it reaches, not the final sum.
    • This is clamped above zero.
    • This looks 64 chunks ahead.
  • The throughput-based buffer size is the minimum size needed to never rebuffer over the past chunks assuming that the bitrate is equal to the mean throughput.
    • This is calculated similarly to the bitrate-based version. The difference between the average and the point is summed, with the maximum sum reached being the result.
    • This is clamed above zero.
    • This looks 35 chunks behind.
• Buffer Change: The target buffer size minus the current buffer size. This is then clamped above -1 seconds.
• Bitrate Selector: First calculates the bitrate that will achieve the target buffer size change assuming the predicted bitrate. Then uses the chunk selection algorithm form BBA-2 to select the next chunk.
  • The target bitrate is calculated as C(1-ΔB/T) where C is the predicted throughput, ΔB is the target buffer size change, and 𝑇 is the length of a chunk in seconds.
  • This is a rearrangement of the equation for the change in buffer size given throughput, bitrate, and chunk length. (ΔB=T-RT/C)

Results

• In general, BBA-2 outperforms RobustMPC.
  • RobustMPC is specifically designed to optimize the exact QoE metrics but has issues with rebuffering on some issues. Taking into account buffer size may help elevate this.
• My algorithm was outperformed by BBA-2 but outperformed RobustMPC.
  • My algorithm focuses on avoiding rebuffering, so it has good rebuffer time.
    • BBA-2 beats my algorithm in one case.
  • My algorithm usually has somewhat worse quality than the other algorithms
    • The quality during steady state is based on the throughput prediction, which is currently conservative.
    • With the current setup, it can get locked at a lower bandwidth, even if the buffer is full. While this bandwidth is “safe”, it may not be optimal to switch to a higher rate to empty the buffer.
  • My algorithm does far worse on number of variations.
    • The only optimization for number of variations is the way a chunk is selected from a rate.
    • Given the coarse nature of the bitrates, and the use of a mostly proportional control loop, oscillations are expected during any steady state.