Abstract

This thesis focuses on problems related to Inference of Congestion in the Internet and Multicast Traffic Engineering in Overlay Networks. In the first part of the thesis, we propose methods which help to improve the quality of the congestion inference on both end-to-end paths and internal network links in the Internet. "br /"Today, transport protocols which transfer data in the Internet classify all packet losses as congestion. However, the development of various wireless access networks had led to the growth of wireless links in the Internet. Therefore, the packet losses observed by a transport protocol may have resulted either due to congestion or due to the presence of wireless links on the end-to-end path. In order to make best use of available network bandwidth, a transport protocol must reduce its sending rate only in response to congestion losses and not in response to wireless losses. In the second chapter of this dissertation, we consider the problem of differentiating congestion and wireless losses for unreliable transport protocols which transfer multimedia flows. Previously proposed end-to-end loss differentiation schemes chapter of this dissertation, we show efficient ways of encoding multicast trees within data packets. These encodings are almost optimal in terms of space and can be read and processed efficiently. They can be used to represent multicast trees within data packets to route multicast traffic on explicit trees in a stateless manner. We show the correspondence of multicast trees to theoretical tree data structures and obtain lower bounds on the number of bits needed to represent multicast trees.significantly misclassify wireless and congestion losses. We propose an explicit loss differentiation scheme which uses agents at the boundaries of wireless links and results in an accurate inference of congestion on the end-to-end path. We show how the agents can intelligently record the cause of packet losses within packets which are not lost, with low overhead. Inferring the level of congestion on internal network links or paths is useful for the purposes of monitoring and management of networks. The level of congestion on a link can be inferred by measuring the loss rate on that link. Installing or upgrading network elements to monitor internal links is an expensive process and hence the characteristics of internal links are often inferred from end-to-end measurements. "br /"The process of inferring characteristics of internal links from end-to-end measurements has come to be known as Network Tomography. One of the earliest proposed methods of performing network tomography is MINC (Multicast-based Inference of Network Characteristics), which infers loss rates (congestion) on internal network links using end-to-end multicast measurements. In MINC, per-link loss rates are inferred by analyzing binary feedbacks which are reported by multicast receivers in response to measurement probes sent from the source. However, due to the presence of buggy or malicious multicast receivers, feedbacks collected may be incorrect leading to a faulty inference of link loss rates. "br /"In the third chapter of this dissertation, we present a statistical verification procedure which can identify if the binary feedback data collected from receivers of a multicast tree contains incorrect feedbacks. The procedure does not require the knowledge of multicast tree topology and is able to identify incorrect data even in the presence of colluding receivers. "br /"In order to infer link characteristics from end-to-end multicast measurements, dedicated infrastructures to perform these measurements need to be deployed. For large scale multicast measurements, the task of deployment is complex and expensive. To avoid this, it was proposed to couple the process of reporting binary feedbacks for MINC loss inference with RTCP (Real-Time Control Protocol). "br /"In this passive measurement architecture, existing multicast sessions which use RTP (Real-Time Transport Protocol) to transfer their data can use their data packets as probes and report binary feedbacks needed for loss inference by piggy-backing them on RTCP packets. For loss inference, MINC requires receivers to report per probe binary feedbacks and this poses constraints since RTCP feedback bandwidth must not exceed 5% of data bandwidth. In the fourth chapter of this dissertation, we develop an extended MINC loss estimator which can perform loss inference using aggregate receiver feedbacks. Aggregate feedbacks require less feedback bandwidth and the estimator is able to perform loss inference using aggregate feedbacks without significant loss of accuracy. We also compare this estimator to the approach where MINC loss inference is performed using a reduced set of binary feedbacks. "br /"In the second part of the thesis, we propose a method which helps to perform multicast traffic engineering in overlay networks. In overlay networks, the network nodes which are generally servers can perform intelligent and adaptive networking functions which normally routers do not support. By studying the state of overlay paths, nodes can route traffic dynamically and perform load balancing or routing based on certain constraints. One of the tasks which overlay networks support is multicast routing. To make best use of the traffic conditions in the network, overlay nodes can route multicast traffic adaptively and achieve goals of traffic engineering. To be able to do so, they need mechanisms to choose specific or explicit multicast trees in the overlay. One way of routing traffic on explicit trees is to perform source routing, that is, to specify the tree within multicast data packets. In the fifth; Résumé non disponible en françai