Network coding is a novel technique to improve the throughput of networks to transfer messages from sources to sinks. Before the birth of network coding, intermediate nodes can only forward the received messages. In a network coding scheme, the intermediate nodes are allowed to mix the received messages from different incoming links. Network coding has found a wide range of applications, such as peer-to-peer networks, distributed storage and content distribution. The theory of network encoding complexity aims to deal with the question what the minimum number of encoding nodes needed in networks is. In order to tackle this question, we convert it into a combinatorial optimization problem. For directed networks, I examine the number of “mergings”, a special type of graph structure. Consider an acyclic directed network G with l source-sink pairs. Let ci denote the minimum size of edge-cut between i-th source-sink pair for 1 ≤ i ≤ l. Then, by Menger’s theorem, there exists a group of ci edge-disjoint paths (Menger’s paths) between i-th source-sink pair. Although within the same group these paths are edge-disjoint, the paths from different groups may have to merge with each other. It is known that by choosing Menger’s paths appropriately, the number of mergings among different groups of Menger’s paths is always bounded by a constant, which is independent of the size of G. The tightest such constant for the all the above-mentioned networks is denoted byM(c1, c2, . . . , cl) when all sources are distinct, and by M∗(c1, c2, . . . , cl) when all sources are identical. It turns out that M and M∗ are closely related to the network encoding complexity for a variety of networks, such as multicast networks, two-way networks and networks with multiple sessions of unicast. Computation of these two important functions, however, appears to be rather difficult; so far there are no explicit formulas for M and M∗ for a generic parameter c1, c2, . . . , cl. In this thesis, I derive exact values of and tighter bounds on M and M∗ for some parameters, and establish the inequality relationships between M and M∗. For undirected networks, I examine the number of “hubs”, the vertices of degree at least three. Compared to directed networks, study on network en-coding complexity in undirected networks has seen little progress. Consider an undirected network G with l source-sink pairs. For i = 1, 2, . . . , l, let ci de-note the minimum size of vertex-cut between i-th source-sink pair. I study H (c1, c2, . . . , cl), the minimum number of hubs needed in an undirected network with min-cut constraints. The function H is closely related to network en-coding complexity for undirected networks. I prove that under some constraints, regardless of the size of the undirected networks, such minimum number is always bounded above and I derive tight upper bounds for some special parameters. In particular, for two pairs of sources and sinks, I present a novel path-searching algorithm, the analysis of which is instrumental for the derivations of the tight upper bounds. / published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

It has been envisioned that in the near future, wireless ad hoc networks would populate various application fields, ranging from disaster relief, environmental monitoring, surveillance, to medical applications, the observation of chemical and biological processes and community mesh networks. The decentralized and self-organizing nature of wireless ad hoc networks makes distributed algorithms fit very well in these networks, which however pose great challenges to the algorithm designers as they try to achieve optimal efficiency in communications. In this thesis, I develop a set of distributed algorithms addressing these challenges and solving some fundamental communication problems in wireless ad hoc networks. Communications in wireless ad hoc networks happen on a shared medium, and consequently are subject to interference. The first part of the thesis focuses on disseminating information on multiple-access channels while avoiding collisions. For both single-channel and multi-channel networks, the complexity of information dissemination is investigated, and nearly optimal distributed algorithms are proposed. The second part of the thesis focuses on designing efficient distributed algorithms for some fundamental problems under the physical Signal-to-Interference-plus-Noise-Ratio (SINR) interference model. The SINR model defines global fading interference with which the success of a signal reception depends on all simultaneous transmissions. Compared with graph based models, the SINR model reflects the fading and cumulative nature of radio signals. Hence, the SINR model represents the physical reality more precisely. However, the global nature of the SINR model makes the analysis of distributed algorithms much more challenging. Two types of fundamental problems are addressed in this part. The first type is closely related to communication coordination, including the wireless link scheduling problem and the node coloring problem. The second type of problems are about basic communication primitives, including the local broadcasting problem and the multiple-message broadcast problem. I investigate the complexity of these fundamental problems under the SINR interference model, and present efficient or optimal distributed algorithms. In the third part of the thesis, I propose a general interference model that can include commonly adopted interference models as special cases, and study whether efficient distributed algorithms can still be designed and analyzed in such a general model. Specifically, the affectance model is proposed in this part, which depicts the relative interference (affectance) on communication links caused by transmitting nodes. Both graph based models and the SINR model can be transformed into the affectance model. Under this general model, distributed algorithms with worst-case guarantees for the local broadcasting problem are presented. I also show how to make use of the developed techniques to get nearly optimal algorithms under the graph based model and the SINR model. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

As the Internet develops and technology evolves, multimedia traffic dominates the Internet. Traditional client-server based video streaming solutions are expensive and suffering from the scalability issue. Inspired by the immense success and efficiency of BitTorrent in distributing file contents to large groups of users, the peer-to-peer (P2P) paradigm has been adopted to provide streaming services including both P2P video-on-demand (VoD) and P2P live streaming. Among the design challenges, one open yet fundamental question is, how to identify the most suitable neighbor for a peer to make a piece request. We refer this problem as the request peer selection problem. Properly allocating the piece request to potential providers is essential to the system and would help to balance the load at each peer. A well designed request peer selection algorithm increases the requestor’s probability to download the desired piece timely which leads to enhanced video quality and improved playback continuity. This thesis aims to enhance the overall system performance by proposing optimized request peer selection algorithms for both P2P VoD and P2P live streaming systems. In P2P VoD, participating peers start playback from the very beginning of a stored video. The playback-points of peers, as well as the amount of video contents/pieces the peers cached, depend on when they join the video session, or their viewing ages. The content buffered by younger peers is a subset of older peers, thus collaborative piece exchange among peers is undermined due to the unbalanced supply and demand. To address this issue, a playback-point based request peer selection algorithm: closest playback-point first (CPF) is proposed. Specifically, when a peer requests a particular video piece, among the set of potential providers, a request is sent to the peer that has the smallest playback-point difference with itself. With CPF, peers with similar content availability are loosely grouped into clusters to maximize the utilization of individual peer’s upload capacity. Extensive packet level simulations show that with CPF, the video playback quality is enhanced and the VoD server load is significantly reduced. Unlike P2P VoD, P2P live streaming systems have to meet real-time playback constraints, which makes it even more challenging. To better regulate the network traffic and to balance the load among peers, a service response time (SRT) based request peer selection algorithm is proposed. In particular, a peer in the network estimates the service response time (SRT) between itself and each neighboring peer. SRT is measured from when a data piece request is sent until the requested piece arrives. When a peer makes a piece request, the neighbor with smaller SRT and fewer data pieces would be favored. The rationale is: smaller SRT implies excess serving capacity and fewer data pieces suggests fewer potential piece requests received. Extensive packet level simulations show that the traffic load in the network is better balanced, the streaming server load is reduced, and the overall quality of service, measured by playback continuity, startup delay etc., is improved. / published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

Not available / text

Not available / text

Not available / text

Not available / text

Not available / text

This dissertation starts by realizing that network management is a very complex and error-prone task. The major causes are identified through interviews and systematic analysis of network config- uration data on two large campus networks. This dissertation finds that network events and dynamic reactions to them should be programmatically encoded in the network control program by opera- tors, and some events should be automatically handled for them if the desired reaction is general. This dissertation presents two new solutions for managing and configuring networks using Software- Defined Networking (SDN) paradigm: Kinetic and Coronet. Kinetic is a programming language and central control platform that allows operators to implement traffic control application that reacts to various kinds of network events in a concise, intuitive way. The event-reaction logic is checked for correction before deployment to prevent misconfigurations. Coronet is a data-plane failure recovery service for arbitrary SDN control applications. Coronet pre-plans primary and backup routing paths for any given topology. Such pre-planning guarantees that Coronet can perform fast recovery when there is failure. Multiple techniques are used to ensure that the solution scales to large networks with more than 100 switches. Performance and usability evaluations show that both solutions are feasible and are great alternative solutions to current mechanisms to reduce misconfigurations.

Thesis (DTech. degree in Computer Science and Data Processing: Software Development.)--Tshwane University of Technology, 2012. / Based on the fundamental assumption that individuals view their privacy differently, this study attempts to find a solution on how to protect the personal information of an individual stored in a relational database system against privacy violations. Secondly, to determine how the Hippocratic principles can be effectively applied to give individuals better control over their personal information, while at the same time allowing the organisation to process its transactions on the same personalised information. In answering these problems, the study established a set of extended principles to which the collection and the use of personal data should strictly hold.