Efficient cross-layer routing and congestion control architectures for distributed systems

Kassa, Debessay

Permalink

https://hdl.handle.net/2142/45430 Copy

Description

Title

Efficient cross-layer routing and congestion control architectures for distributed systems

Author(s)

Kassa, Debessay

Issue Date

2013-08-22T16:39:56Z

Director of Research (if dissertation) or Advisor (if thesis)

Nahrstedt, Klara

Doctoral Committee Chair(s)

Nahrstedt, Klara

Committee Member(s)

• Godfrey, Philip B.
• Lumetta, Steven S.
• Fahmy, Sonia

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Cross-layer routing and congestion control
• Adaptive rate allocation
• Server selection
• Load balancing
• Generalized efficient sharing (GES)
• Fractional (partial) flows
• Network level max-min fairness
• Network level service level agreement
• Network level quality of service
• Hybrid peer to peer networks
• Per packet prices
• Efficient peer incentives
• Meta-data management
• Active/passive content
• Content index management
• Secure content exchange
• Power-efficient datacenter
• Efficient Openflow
• Software defined networking
• Surrogate servers
• Low content transfer times
• High throughput architectures

Abstract

Major distributed systems such as the Internet, datacenter and hybrid P2P networks share a common known challenge of finding an optimal path to transfer content from a source to a destination and the optimal rate at which content is transmitted. In general networks such as the Internet, per user, there is usually one possible content source/destination such as a web server. There can be multiple possible paths to/from the destination/source (server). In datacenter networks which usually have a tree structure and in hybrid Peer-to-Peer (P2P) networks, there can be multiple possible servers at which content can be stored and from which content can be re- trieved. Multiple possible servers (sources/destinations) translates into multiple possible paths to/from a content destination/source. Finding an optimal path to/from a destination/source requires efficient conges- tion control and routing schemes. The transmission control protocol (TCP) is the major congestion control protocol in the Internet. TCP and its variants have the drawback of not accurately knowing rate share of flows at bottleneck links. Some protocols proposed to address these drawbacks are not fair to short flows, which are the majority of the Internet traffic. Other protocols result in high queue length and packet drops which translate into a high average flow completion time (AFCT). The currently major deployed intra-domain routing algorithm is the Open Shortest Path First (OSPF) [1]. OSPF uses a simple heuristic routing metric (link weight). The routing metric used doesn’t properly take into account the latest status of the network. Other traffic engineering schemes such as the TeXCP proposed to address the routing issues of existing schemes also fail to find a globally (domain level) optimal route. Besides, they incur additional probing and path reservation packet overheads. Recently deployed datacenter network architectures rely on random server and hence path selection in the attempt to ease congestion. However such random selection of paths can result in serious congestion and content transfer delay. This can for instance be caused by large content transfers (elephant flows) which take a long time to finish. In this case a random path selection can add to the congestion caused by elephant flows. Existing cloud datacenter architectures such as the Google File System (GFS) and the Hadoop File ii System (HDFS) rely on a single name node server (NNS) to manage metadata information of which content is stored in which server. A single NNS can be a potential bottleneck and a single point of failure. Hybrid P2P content sharing can result in significant scalability gains in addition to assisting content distribution networks (CDNs). However, currently proposed CDN and P2P hybrid schemes do not provide accurate, fair and efficient incentives to attract and maintain more peers. Besides, they do not use efficient prioritized congestion control and content source selection mechanisms to reduce content transfer times. In this thesis, we present the design and analysis of cross-layer congestion control and routing protocols to address the above challenges of major distributed systems. Our schemes derive an efficient rate metric which sources use to set their sending rates and which routers/switches use as a link weight to compute an optimal path. Among other contributions our rate and path computation schemes achieve network level max-min fairness where available resources are quickly utilized as long as there is demand for them. Our schemes have prioritized rate allocation mechanisms to satisfy different network level service level agreements (SLA)s on throughput and delays. For cloud datacenter networks, our scheme uses a light weight front end server (FES) to allow the use of multiple NNS and there by mitigate the shortcomings of existing architectures. For hybrid P2P networks our schemes ensure high and accurate incentives to participating peers. Such fair incentives attract more peers which securely download and distribute contents. The thesis also presents efficient content index management schemes for the hybrid P2P networks with robust incentive implementation mechanisms. We have implemented our protocols for general networks (the Internet), for cloud datacenter and hybrid P2P networks in the well known NS2 simulator. We have conducted detailed packet level and trace-based experiments. Simulation results show that our protocol for general networks can result in the reduction of the average file completion time (AFCT) by upto 30% when compared with well known existing schemes. Our cross-layer design for cloud datacenter networks can achieve a content transfer time which is about 50% lower than the existing schemes and a throughput which is higher than existing approaches by upto than 60%. Our detailed trace-based experiments also shows that our hybrid P2P protocol outperforms existing schemes in terms of file download time and throughput by up to 30% on average. The results also demonstrate that our hybrid P2P scheme obtains fair uplink prices for the uploaders and fair cost for the downloaders maintaining an overall system fairness. Besides, the results show the efficient enforcements of the prioritized allocations. Our implementation of the hybrid P2P protocol using an Apache SQL Server with PHP in Linux virtual machines demonstrates that content index management mechanisms of our protocol are scalable.

Graduation Semester

2013-08

Permalink

http://hdl.handle.net/2142/45430

Copyright and License Information

Copyright 2013 Debessay Kassa

Owning Collections