TCP was conceived to ensure reliable node-to-node communication in moderate-bandwidth, moderate-latency, WANs. As it is now a mature Internet standard, it is the default connection-oriented protocol in networks built from commodity components, including Internet data centers. Data centers, however, rely on high-bandwidth, low-latency networks for communication. Moreover, their communication patterns, especially those generated by distributed applications such as MapReduce, often take the form of synchronous multi-node to node bursts. Under the right conditions, the network switch buffer overflow losses induced by these bursts confuse TCP's feedback mechanisms to the point that TCP throughput collapses. This collapse, termed TCP Incast, results in gross underutilization of link capacities, significantly degrading application performance. Conventional approaches to mitigating Incast have focused on single-path solutions, for instance, adjusting TCP's receive windows and timers, modifying the protocol itself, or adopting explicit congestion notifications. This thesis explores complementary multi-path approaches to avoiding Incast's onset. The principal idea is to use the regularity and high connectivity of typical data center networks, such as the increasingly popular fat-tree topology, to better distribute multi-node to node bursts across the available paths, thereby avoiding the switch buffer overflows that induce TCP Incast. The thesis's main contributions are: (1) development of new oblivious, multi-path, routing schemes for fat-tree networks, (2) derivation of relations between the schemes and Incast's onset, and (3) investigation of a novel "front-back" approach to minimizing the packet reordering introduced by multipath routing. Formal analyses are focused on relating schemes' worst-case loading of certain network resources - expressed as oblivious performance ratios (OPRs) - to Incast's onset. Potential benefits are assessed through ns-3 simulations on fat-trees under a variety of communication patterns. Results indicate that over a variety of experimental conditions, the proposed schemes reduce the incidence of TCP Incast compared to standard routing schemes.

In today’s scenario, energy efficiency has become one of the most crucial issues for Data Center Networks (DCN). This paper analyses the energy saving capability of a Data center network using Segment Routing (SR) based model within a Software Defined Network (SDN) architecture. Energy efficiency is measured in terms of number of links turned off and for how long the links remain in sleep mode. Apart from saving the energy by turning off links, our work further efficiently manages the traffic within the available links by using Per-packet based load balancing approach. Aiming to avoid congestion within DCN’s and increase the sleeping time of inactive links. An algorithm for deciding the particular set of links to be turned off within a network is presented. With the introduction of per-packet approach within SR/SDN model, we have successfully saved 21 % of energy within DCN topology. Results show that the proposed Per-packet SR model using Random Packet Spraying (RPS) saves more energy and provides better performance as compared to Per-flow based SR model, which uses Equal Cost Multiple Path (ECMP) for load balancing. But, certain problems also come into picture using per-packet approach, like out of order packets and longer end to end delay. To further solidify the effect of SR in saving energy within DCN and avoid previously introduced problems, we have used per-flow based Flow Reservation approach along with a proposed Flow Scheduling Algorithm. Flow rate of all incoming flows can be deduced using Flow reservation approach, which is further used by Flow Scheduling Algorithm to increase Bandwidth utilization Ratio of links. Ultimately, managing the traffic more efficiently and increasing the sleeping time of links, leading to more energy savings. Results show that, the energy savings are almost similar in per-packet based approach and per-flow based approach with bandwidth reservation. Except, the average sleeping time of links in per-flow based approach with bandwidth reservation decreases less severely as compared to per-packet based approach, as overall traffic load increases.

Diversity is a widely existing and much desired property in many networking systems. This dissertation studies diversity problems in Internet, which is the largest computer networking system in the world. The motivations of diversifying the Internet are two-fold. First, diversifying the Internet improves the Internet routing robustness and reliability. Most problems we have encountered in our daily use of Internet, such as service interruptions and service quality degradation, are rooted in the inter-domain routing system of Internet. Inter-domain routing is policy-based routing, where policies are often based on commercial agreements between ASes. Although people know how to safely accommodate a few commercial agreements in inter-domain routing, for a large set of diverse commercial agreements, it is not clear yet what policy guidelines can accommodate them and guarantee convergence. Accommodating diverse commercial agreements not only is needed for ASes in Internet to achieve their business goals, it also provides more path diversity in inter-domain routing, which potentially benefits the inter-domain routing system. However, more reliable and robust routing cannot be achieve unless the routing system exploits the path diversity well. However, that is not the case for the current inter-domain routing system. There exist many paths in the underlying network, but the routing system cannot find those paths promptly. Although many schemes have been proposed to address the routing reliability problem, they often add significant more complexity into the system. The need for a more reliable inter-domain routing system without adding too much complexity calls for designing practical schemes to better exploit Internet path diversity and provide more reliable routing service. The increasing demands of providing value-added services in Internet also motivates the research work in this dissertation. Recently, network virtualization substrates and data centers are becoming important infrastructures. Network virtualization provides the ability to run multiple concurrent virtual networks in the same shared substrate. To better facilitate building application-specific networks so as to test and deploy network innovations for future Internet, a network virtualization platform must provide both high-degree of flexibility and high-speed packet forwarding in virtual networks. However, flexibility and forwarding performance are often tightly coupled issues in system design. Usually we have to sacrifice one in order to improve the other one. The lack of a platform that has both flexibility and good forwarding performance motivates the research in this dissertation to design network virtualization platforms to better support virtual networks with diverse functionalities in future Internet. The popularity of data centers in Internet also motivates this dissertation to studying scalable and cost-efficient data center networks. Data centers with a cluster of servers are already common places in Internet to host large scale networking applications, which require huge amount of computation and storage resources. To keep up with the performance requirements of those applications, a data center has to accommodate a large number of servers. As Internet evolves and more diverse applications emerge, the computation and storage requirements for data centers grow quickly. However, using the conventional interconnection structure is hard to scale the number of servers in data centers. Hence, it is of importance to design new interconnection structures for future data centers in Internet. Four interesting topics are explored in this dissertation: (i) accommodating diverse commercial agreements in inter-domain routing, (ii) exploiting the Internet AS-level path diversity, (iii) supporting diverse network data planes, and (iv) diverse interconnection networks for data centers. The first part of this dissertation explores accommodating diverse commercial agreements in inter-domain routing while guaranteeing global routing convergence, so as to provide more path diversity in Internet. The second part of this dissertation studies exploiting the path diversity in Internet by running multiple routing processes in parallel, which compute multiple paths and those paths can complement each other in case one path has problems when dynamics present in the routing system. The third part of this dissertation studies supporting concurrent networks with heterogeneous data plane functions via network virtualization. Two virtual network platforms are presented, which achieve both high-speed packet forwarding in each virtual network and high degree of flexibility for each virtual network to customize its data plane functions. The last part of this dissertation presents a new scalable interconnection structure for data center networks. The salient feature of this new interconnection structure is that it expands to any number of servers without requiring to physically upgrading the existing servers.

No description available.

Software-defined Networking (SDN) enables flexible network management, but as networks evolve to a large number of end-points with diverse network policies, higher speed, and higher utilization, abstraction of networks by SDN makes monitoring and debugging network problems increasingly harder and challenging. While some problems impact packet processing in the data plane (e.g., congestion), some cause policy deployment failures (e.g., hardware bugs); both create inconsistency between operator intent and actual network behavior. Existing debugging tools are not sufficient to accurately detect, localize, and understand the root cause of problems observed in a large-scale networks; either they lack in-network resources (compute, memory, or/and network bandwidth) or take long time for debugging network problems. This thesis presents three debugging tools: PathDump, SwitchPointer, and Scout, and a technique for tracing packet trajectories called CherryPick. We call for a different approach to network monitoring and debugging: in contrast to implementing debugging functionality entirely in-network, we should carefully partition the debugging tasks between end-hosts and network elements. Towards this direction, we present CherryPick, PathDump, and SwitchPointer. The core of CherryPick is to cherry-pick the links that are key to representing an end-to-end path of a packet, and to embed picked linkIDs into its header on its way to destination. PathDump is an end-host based network debugger based on tracing packet trajectories, and exploits resources at the end-hosts to implement various monitoring and debugging functionalities. PathDump currently runs over a real network comprising only of commodity hardware, and yet, can support surprisingly a large class of network debugging problems with minimal in-network functionality. The key contributions of SwitchPointer is to efficiently provide network visibility to end-host based network debuggers like PathDump by using switch memory as a "directory service" - each switch, rather than storing telemetry data necessary for debugging functionalities, stores pointers to end hosts where relevant telemetry data is stored. The key design choice of thinking about memory as a directory service allows to solve performance problems that were hard or infeasible with existing designs. Finally, we present and solve a network policy fault localization problem that arises in operating policy management frameworks for a production network. We develop Scout, a fully-automated system that localizes faults in a large scale policy deployment and further pin-points the physical-level failures which are most likely cause for observed faults.

<p dir="ltr">Ensuring a high quality of experience for Internet applications is challenging owing to the significant variability (e.g., of traffic patterns) inherent to both cloud data-center networks and wide area networks. This thesis focuses on optimizing application performance by both conducting measurements to characterize traffic variability, and designing applications that can perform well in the face of variability. On the data center side, a key aspect that impacts performance is traffic burstiness at fine granular time scales. Yet, little is know about traffic burstiness and how it impacts application loss. On the wide area side, we focus on video applications as a major traffic driver. While optimizing traditional videos traffic remains a challenge, new forms of video such as 360◦ introduce additional challenges such as respon- siveness in addition to the bandwidth uncertainty challenge. In this thesis, we make three contributions.</p><p dir="ltr"><b>First</b>, for data center networks, we present Millisampler, a lightweight network traffic char- acterization tool for continual monitoring which operates at fine configurable time scales, and deployed across all servers in a large real-world data center networks. Millisampler takes a host-centric perspective to characterize traffic across all servers within a data center rack at the same time. Next, we present data-center-scale joint analysis of burstiness, contention, and loss. Our results show (i) bursts are likely to encounter contention; (ii) contention varies significantly over short timescales; and (iii) higher contention need not lead to more loss, and the interplay with workload and burst properties matters.</p><p dir="ltr"><b>Second</b>, we consider challenges with traditional video in wide area networks. We take a step towards understanding the interplay between Content-Delivery-Networks (CDNs), and video performance through end-to-end measurements. Our results show that (i) video traffic in a session can be sourced from multiple CDN layers, and (ii) throughput can vary signifi- cantly based on the traffic source. Next we evaluate the potential benefits of exposing CDN information to the client Adaptive-Bit-Rate (ABR) algorithm. Emulation experiments show the approach has the potential to reduce prediction inaccuracies, and enhance video quality of experience (QoE).</p><p dir="ltr"><b>Third</b>, for 360◦ videos, we argue for a new streaming model which is explicitly designed for continuous, rather than stalling, playback to preserve interactivity. Next, we propose Dragonfly, a new 360° system that leverages the additional degrees of freedom provided by this design point. Dragonfly proactively skips tiles (i.e., spatial segment of the video) using a model that defines an overall utility function that captures factors relevant to user experience. We conduct a user study which shows that majority of interactivity feedback indicating Dragonfly being highly reactive, while the majority of state-of-the-art’s feedback indicates the systems are slow to react. Further, extensive emulations show Dragonfly improves the image quality significantly without stalling playback.</p>

With the growing business impact of distributed big data analytics jobs, it has become crucial to optimize their execution and resource consumption. In most cases, such jobs consist of multiple sub-entities called tasks and are executed online in a large shared distributed computing system. The ability to accurately estimate runtime properties and coordinate execution of sub-entities of a job allows a scheduler to efficiently schedule jobs for optimal scheduling. This thesis presents the first study that highlights spatial dimension, an inherent property of distributed jobs, and underscores its importance in efficient cluster job scheduling. We develop two new classes of spatial dimension based algorithms to<br>address the two primary challenges of cluster scheduling. First, we propose, validate, and design two complete systems that employ learning algorithms exploiting spatial dimension. We demonstrate high similarity in runtime properties between sub-entities of the same job by detailed trace analysis on four different industrial cluster traces. We identify design challenges and propose principles for a sampling based learning system for two examples, first for a coflow scheduler, and second for a cluster job scheduler.<br>We also propose, design, and demonstrate the effectiveness of new multi-task scheduling algorithms based on effective synchronization across the spatial dimension. We underline and validate by experimental analysis the importance of synchronization between sub-entities (flows, tasks) of a distributed entity (coflow, data analytics jobs) for its efficient execution. We also highlight that by not considering sibling sub-entities when scheduling something it may also lead to sub-optimal overall cluster performance. We propose, design, and implement a full coflow scheduler based on these assertions.

A datacenter hosts hundreds of thousands of servers and a huge amount of bandwidth is required to accommodate communication between thousands of servers. Several packet switched based datacenter architectures are proposed to cater the high bandwidth requirement using multilayer network topologies, however at the cost of increased network complexity and high power consumption. In recent years, the focus has shifted from packet switching to optical circuit switching to build the data center networks as it can support on demand connectivity and high bit rates with low power consumption. On the other hand, with the advent of Software Defined Networking (SDN) and Network Function Virtualization (NFV), the role of datacenters has become more crucial. It has increased the need of dynamicity and flexibility within a datacenter adding more complexity to datacenter networking. With NFV, service chaining can be achieved in a datacenter where virtualized network functions (VNFs) running on commodity servers in a datacenter are instantiated/terminated dynamically. A datacenter also needs to cater large capacity requirement as service chaining involves steering of large aggregated flows. Use of optical circuit switching in data center networks is quite promising to meet such dynamic and high capacity traffic requirements. In this thesis work, a novel and modular optical data center network (DCN) architecture that uses multi-directional wavelength switches (MD-WSS) is introduced. VNF service chaining use case is considered for evaluation of this DCN and the end-to-end service chaining problem is formulated as three inter-connected sub-problems: multiplexing of VNF service chains, VNFs placement in the datacenter and routing and wavelength assignment. This thesis presents integer linear programming (ILP) formulation and heuristics for solving these problems, and numerically evaluate them. / Ett datacenter inrymmer hundratusentals servrar och en stor mängd bandbredd krävs för att skicka data mellan tusentals servrar. Flera datacenter baserade på paketförmedlande arkitekturer föreslås för att tillgodose kravet på hög bandbredd med hjälp av flerskiktsnätverkstopologier, men på bekostnad av ökad komplexitet i nätverken och hög energiförbrukning. Under de senaste åren har fokus skiftat från paketförmedling till optisk kretsomkoppling for att bygga datacenternätverk som kan stödja på-begäran-anslutningar och höga bithastigheter med låg strömförbrukning. Å andra sidan, med tillkomsten av Software Defined Networking (SDN) och nätverksfunktionen Virtualisering (NFV), har betydelsen av datacenter blivit mer avgörande. Det har ökat behovet av dynamik och flexibilitet inom ett datacenter, vilket leder till storre komplexitet i datacenternätverken. Med NFV kan tjänstekedjor åstadkommas i ett datacenter, där virtualiserade nätverksfunktioner (VNFs) som körs på servrar i ett datacenter kan instansieras och avslutas dynamiskt. Ett datacenter måste också tillgodose kravet på stor kapacitet eftersom tjänstekedjan innebär styrning av stora aggregerade flöden. Användningen av optisk kretsomkoppling i datacenternätverk ser ganska lovande ut for att uppfylla sådana trafikkrav dynamik och hög kapacitet. I detta examensarbete, har en ny och modulär optisk datacenternätverksarkitektur (DCN) som använder flerriktningvåglängdsswitchar (MD-WSS) införs. Ett användningsfall av VNF-tjänstekedjor noga övervägd för utvärdering av denna DCN och end-to-end-servicekedjans problem formuleras som tre sammankopplade delproblem: multiplexering av VNF-servicekedjor, VNF placering i datacentret och routing och våglängd uppdrag. Denna avhandling presenterar heltalsprogrammering (ILP) formulering och heuristik för att lösa dessa problem och numeriskt utvärdera dem.