On Data-Path Customization In Next-Generation Networks

The Internet is an example of a successful and scalable decentralized system capable of connecting millions of systems and transporting data seamlessly between them. It has been so successful that today, it is impossible to imagine entertainment, education, communication, business and other services without the Internet. In fact, the Internet is widely considered to be just another utility service. Additionally, the diversity of the end-systems ranging from high-end servers to mobile phones and sensors is only adding to the rate of its growth and value. This success is largely the result of careful thought put into the design philosophy of the Internet (globally deployed network layer, isolation of protocol layers). This has resulted in a digital information explosion with recent studies predicting a ten fold increase in the amount of digital content over the next five years. Factors such as information replication, increasingly affordable and heterogeneous end-systems, cheap storage and numerous services are cited to be a few of the reasons for this rapid growth. However, this fixed network layer also poses a barrier to introduction of innovations to support increasingly diverse end-systems and new communication paradigms. Moreover, the inherent issues in security, mobility, performance and reliability cannot be completely resolved by merely changing functionality in the end-systems, and will require addition of functionality in the core of the network as well. Service-centric networking is a new paradigm that seeks to introduce functionality into the network by deploying customized in-network services on-demand. Different compositions of services are used to customize connections to satisfy various user communication requirements. This work addresses four challenges in the context of service-centric networks: (1) automated service composition (2) combined service composition and routing, (3) support for inter-domain data-plane policies in such networks, and (4) end-system support for services through abstractions. Automated service composition deals with the challenge of finding an optimal sequence of services to satisfy communication requirements of a connection. This composed sequence of services is applied to the connection in the data-path. A semantic tree is used to describe communication characteristics and the problem is solved by reducing it to a planning problem. Service composition is typically followed by service routing , where the connection is set up such that the services are applied in order. This is not always optimal as we show through experiments. Combined service composition and routing tries to solve both problems in a single stage by reducing it to a planning problem. We further explore the issues of inter-domain data-plane policies in next-generation networks and discuss a system that uses the semantic tree to specify such policies. The system translates these policies into planning rules and determines the right way to set up the connection such that all policies are met. We also discuss the design and implementation of a novel service socket API that allows end-system applications to access services in a service-centric networking context. Another key aspect of next-generation networking is virtualization of the physical network infrastructure. Network virtualization allows multiple networks with different protocol stacks to share the same physical infrastructure. A key problem for virtual network providers is the need to efficiently allocate their customers\u27 virtual network requests to the underlying network infrastructure. This problem is known to be computationally intractable and heuristic solutions continue to be developed. Most existing heuristics use a two-stage approach in which virtual nodes are first placed on physical nodes and virtual links are subsequently mapped. We present VHub, a novel single-stage approach that formulates this problem as a p-hub median problem. Our results show that VHub outperforms the state of the art algorithms by mapping 23% more virtual networks in lesser time (26% to 96%). Overall, this dissertation discusses techniques through which data-path customization can be achieved in next-generation networks. To solve some of the technical challenges, this work follows a cross-disciplinary approach exploring ideas from computer networking, distributed systems and algorithms to graph theory, mathematical optimization and artificial intelligence. The solutions are also tested through simulations using real and synthetically generated workloads to validate the design