|Selected Publications (post 2002)|
|Publications from WING bibliography (includes pre 2002 papers)|
|Citations to my work from Google Scholar|
Hany Morcos, George Atia, Azer Bestavros, and Ibrahim Matta. An Information Theoretic Framework for Field Monitoring Using Autonomously Mobile Sensors. Ad Hoc Networks: Special Issue on Distributed Computing in Sensor Systems, 9(6):1049–1058, August 2011.
Abstract: We consider a mobile sensor network monitoring a spatio-temporal field. Given limited caches at the sensor nodes, the goal is to develop a distributed cache management algorithm to efficiently answer queries with a known probability distribution over the spatial dimension. First, we propose a novel distributed information theoretic approach assuming knowledge of the distribution of the monitored phenomenon. Under this scheme, nodes minimize an entropic utility function that captures the average amount of uncertainty in queries given the probability distribution of query locations. Second, we propose a correlation-based technique, which only requires knowledge of the second-order statistics, relaxing the stringent constraint of a priori knowledge of the query distribution, while significantly reducing the computational overhead. We show that the proposed approaches considerably improve the average field estimation error. Further, we show that the correlation-based technique is robust to model mismatch in case of imperfect knowledge of the underlying generative correlation structure.
Hany Morcos, Azer Bestavros, and Ibrahim Matta. Preferential Field Coverage Through Detour-Based Mobility Coordination. In Proceedings of the 9th IFIP Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net), Juan-les-pins, France, June 2010. (Best Paper Award)
Abstract: Controlling the mobility of mobile nodes (e.g., robots) to monitor a given field is a well-studied problem in sensor networks. In this setup, absolute control over the nodes' mobility is assumed. In this paper, we address a more general setting in which mobility of each node is externally constrained by a schedule consisting of a list of locations that the node must visit at particular times. Typically, such schedules exhibit some level of slack, which could be leveraged to achieve a specific coverage distribution of a field. Such a distribution defines the relative importance of different field locations. We define the Constrained Mobility Coordination problem for Preferential Coverage (CMC-PC) as follows: given a field with a desired monitoring distribution, and a number of nodes n, each with its own schedule, we need to coordinate the mobility of the nodes in order to achieve the following two goals: 1) satisfy the schedules of all nodes, and 2) attain the required coverage of the given field. We show that the CMC-PC problem is NP-complete (by reduction from the Hamiltonian Cycle problem). Then we propose TFM, a distributed heuristic to achieve field coverage that is as close as possible to the required coverage distribution. We verify the premise of TFM using extensive simulations, as well as taxi logs from a major metropolitan area. We compare TFM to the random mobility strategy ---the latter provides a lower bound on performance. Our results show that TFM is very successful in matching the required field coverage distribution, and that it provides, at least, two-fold query success ratio for queries that follow the target coverage distribution of the field.
Alberto Medina, Gonca Gursun, Prithwish Basu, and Ibrahim Matta. On the Universal Generation of Mobility Models. In Proceedings of the 18th Annual Meeting of the IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), Miami Beach, Florida, August 2010.
Abstract: Mobility models have traditionally been tailored to specific application domains such as human, military, or ad hoc transportation scenarios. This tailored approach often renders a mobility model useless when the application domain changes, and leads to wrong conclusions about the performance of protocols and applications running atop of different domains. In this work we propose and implement a mobility modeling framework (UMMF) based on the observation that the mobility characteristics of most mobility-based applications can be captured in terms of a few fundamental factors: (1) Targets; (2) Obstacles; (3) Dynamic events; (4) Navigation; (5) Steering behaviors; and (6) Dynamic behaviors. We demonstrate the mapping of application-domain-specifics to UMMF elements, showing the power and flexibility of our approach.
Flavio Esposito and Ibrahim Matta. PreDA: Predicate Routing for DTN Architectures over MANET. In Proceedings of the IEEE Globecom 2009 Next-Generation Networking and Internet Symposium (GC'09 NGNI), Honolulu, Hawaii, December 2009.
Abstract: We consider a Delay Tolerant Network (DTN) whose users (nodes) are connected by an underlying Mobile Ad hoc Network (MANET) substrate. Users can declaratively express high-level policy constraints on how content should be routed. For example, content can be directed through an intermediary DTN node for the purposes of preprocessing, authentication, etc., or content from a malicious MANET node can be dropped. To support such content routing at the DTN level, we implement Predicate Routing where high-level constraints of DTN nodes are mapped into low-level routing predicates within the MANET nodes. Our testbed uses a Linux system architecture with User Mode Linux to emulate every DTN node with a DTN Reference Implementation code. In our initial architecture prototype, we use the On Demand Distance Vector (AODV) routing protocol at the MANET level. We use the network simulator ns-2 (ns-emulation version) to simulate the wireless connectivity of both DTN and MANET nodes. Preliminary results show the efficient and correct operation of propagating routing predicates. For the application of content re-routing through an intermediary, as a side effect, results demonstrate the performance benefit of content re-routing that dynamically (on-demand) breaks the underlying end-to-end TCP connections into shorter-length TCP connections.
Hany Morcos, Azer Bestavros, and Ibrahim Matta. Amorphous Placement and Informed Diffusion for Timely Field Monitoring by Autonomous, Resource-Constrained, Mobile Sensors. In Proceedings of IEEE SECON Conference, San Francisco, CA, June 2008.
Abstract: Personal communication devices are increasingly equipped with sensors for passive monitoring of encounters and surroundings. We envision the emergence of services that enable a community of mobile users carrying such resource-limited devices to query such information at remote locations in the eld in which they collectively roam. One approach to implement such a service is directed placement and retrieval (DPR), whereby readings/queries about a specic location are routed to a node responsible for that location. In a mobile, potentially sparse setting, where end-to-end paths are unavailable, DPR is not an attractive solution as it would require the use of delay-tolerant (ooding-based store-carry-forward) routing of both readings and queries, which is inappropriate for applications with data freshness constraints, and which is incompatible with stringent device power/memory constraints. Alternatively, we propose the use of amorphous placement and retrieval (APR), in which routing and eld monitoring are integrated through the use of a cache management scheme coupled with an informed exchange of cached samples to diffuse sensory data throughout the network, in such a way that a query answer is likely to be found close to the query origin. We argue that knowledge of the distribution of query targets could be used effectively by an informed cache management policy to maximize the utility of collective storage of all devices. Using a simple analytical model, we show that the use of informed cache management is particularly important when the mobility model results in a non-uniform distribution of users over the eld. We present results from extensive simulations which show that in sparsely-connected networks, APR is more cost-effective than DPR, that it provides extra resilience to node failure and packet losses, and that its use of informed cache management yields superior performance.
Hany Morcos, George Atia, Azer Bestavros, and Ibrahim Matta. An Information Theoretic Framework for Field Monitoring Using Autonomously Mobile Sensors. In Proceedings of International Conference on Distributed Computing in Sensor Systems (DCOSS), Santorini Island, Greece, June 2008. (Best Paper Award, Applications Track)
Abstract: We consider a mobile sensor network monitoring a spatio-temporal field. Given limited caches at the sensor nodes, the goal is to develop a distributed cache management algorithm to efficiently answer queries with a known probability distribution over the spatial dimension. First, we propose a novel distributed information theoretic approach assuming knowledge of the distribution of the monitored phenomenon. Under this scheme, nodes minimize an entropic utility function that captures the average amount of uncertainty in queries given the probability distribution of query locations. Second, we propose a correlation-based technique, which only requires knowledge of the second-order statistics, relaxing the stringent constraint of a priori knowledge of the query distribution, while signicantly reducing the computational overhead. We show that the proposed approaches considerably improve the average field estimation error. Further, we show that the correlation-based technique is robust to model mismatch in case of imperfect knowledge of the underlying generative correlation structure.
Gabriele Ferrari Aggradi, Flavio Esposito, and Ibrahim Matta. Supporting Predicate Routing in DTN over MANET. In Proceedings of ACM MobiCom Workshop on Challenged Networks (CHANTS 2008), San Francisco, CA, September 2008. (Demo)
Abstract: We consider a Delay Tolerant Network (DTN) whose users (nodes) are connected by an underlying Mobile Ad hoc Network (MANET) substrate. Users can declaratively express high-level policy constraints on how content should be routed. For example, content may be diverted through an intermediary DTN node for the purposes of preprocessing, authentication, etc. To support such capability, we implement Predicate Routing where high-level constraints of DTN nodes are mapped into low-level routing predicates at the MANET level. Our testbed uses a Linux system architecture and leverages User Mode Linux to emulate every node running a DTN Reference Implementation code. In our initial prototype, we use the On Demand Distance Vector (AODV) MANET routing protocol. We use the network simulator ns-2 (ns-emulation version) to simulate the mobility and wireless connectivity of both DTN and MANET nodes. We show preliminary throughput results showing the efficient and correct operation of propagating routing predicates, and as a side effect, the performance benefit of content re-routing that dynamically (on-demand) breaks the underlying end-to-end TCP connection into shorter-length TCP connections.
Niky Riga, Ibrahim Matta, Alberto Medina, Craig Partridge, and Jason Redi. JTP: An Energy-conscious Transport Protocol for Multi-hop Wireless Networks. In Proceedings of CoNEXT Conference, New York, NY, December 2007.
Abstract: We present a transport protocol whose goal is to reduce power consumption without compromising delivery requirements of applications. To meet its goal of energy efficiency, our transport protocol (1) contains mechanisms to balance endto- end vs. local retransmissions; (2) minimizes acknowledgment traffic using receiver regulated rate-based flow control combined with selected acknowledgements and in-network caching of packets; and (3) aggressively seeks to avoid any congestion-based packet loss. Within a recently developed ultra low-power multi-hop wireless network system, extensive simulations and experimental results demonstrate that our transport protocol meets its goal of preserving the energy efficiency of the underlying network.
Niky Riga, Ibrahim Matta, and Azer Bestavros. A Geometric Approach to Slot Alignment in Wireless Sensor Networks. In Proceedings of the IEEE Global Telecommunications Conference (Globecom'07) Ad-hoc and Sensor Networking Symposium, Washington, DC, November 2007.
Abstract: Traditionally, slotted communication protocols have employed guard times to delineate and align slots. These guard times may expand the slot duration significantly, especially when clocks are allowed to drift for longer time to reduce clock synchronization overhead. Recently, a new class of lightweight protocols for statistical estimation in wireless sensor networks have been proposed. This new class requires very short transmission durations (jam signals), thus the traditional approach of using guard times would impose significant overhead. We propose a new, more efficient algorithm to align slots. Based on geometrical properties of space, we prove that our approach bounds the slot duration by only a constant factor of what is needed. Furthermore, we show by simulation that this bound is loose and an even smaller slot duration is required, making our approach even more efficient.
Niky Riga, Alberto Medina, Ibrahim Matta, Craig Partridge, Jason Redi, and Isidro Castineyra. Transport Services for Energy Constrained Environments. In Proceedings of ACM SIGCOMM'05, Philadelphia, PA, August 2005. Work-in-progress Session.
Abstract: JAVeLEN (Joint Architecture Vision for Low Energy Networking) is a network architecture whose design targets the reduction of the energy-per-bit used for data delivery in tactical wireless mobile ad-hoc networks (MANETs). It comprises the physical, MAC, routing, and transport layers of the communication stack. In this extended abstract we briefly summarize our work in progress on the design of JTP, the JAVeLEN Transport Protocol. The central question of our JTP research is, given a network-wide energy efficiency objective, how should a transport protocol be designed so that such objective is achieved while taking into account application semantics. JTP achieves that goal by exploiting reliability semantics weaker than those offered by TCP when applications tolerate it. JTP incorporates as well additional QoS provisions for applications.
Hany Morcos, Ibrahim Matta, and Azer Bestavros. M2RC: Multiplicative-increase/additive-decrease Multipath Routing Control for Wireless Sensor Networks. SIGBED Review---Special Issue on the Best of SenSys 2004 Work-in-Progress, 2(1), January 2005.
Abstract: Routing protocols in wireless sensor networks (WSN) face two main challenges: first, the challenging environments in which WSN's are deployed negatively affect the quality of the routing process. Therefore, routing protocols for WSN's should recognize and react to node failures and packet losses. Second, sensor nodes are battery-powered, which makes power a scarce resource. Routing protocols should optimize power consumption to prolong the lifetime of the WSN. In this paper, we present a new adaptive routing protocol for WSN's, we call it M2RC. M2RC has two phases: mesh establishment phase and data forwarding phase. In the first phase, M2RC establishes the routing state to enable multipath data forwarding. In the second phase, M2RC forwards data packets from the source to the sink. Targeting hop-by-hop reliability, an M2RC forwarding node waits for an acknowledgement (ACK) that its packets were correctly received at the next neighbor. Based on this feedback, an M2RC node applies multiplicative-increase/additive-decrease (MIAD) to control the number of neighbors targeted by its packet broadcast. We simulated M2RC in the ns-2 simulator  and compared it to GRAB , Max-power, and Min-power routing schemes. Our simulations show that M2RC achieves the highest throughput with at least 10-30% less consumed power per delivered report in scenarios where a certain number of nodes unexpectedly fail.
Hany Morcos, Ibrahim Matta, and Azer Bestavros. BiPAR: A Bimodal Power-Aware Routing Protocol for Wireless Sensor Networks. In Proceedings of the First International Computer Engineering Conference (ICENCO 2004), Cairo, Egypt, December 2004.
Abstract: Wireless Sensor Networks (WSN) have the potential to change the way we perform many tasks today. Examples include military applications, agriculture applications and medical applications. Routing protocols in WSN have to operate in challenged environments. In these environments, packet losses and node failures are common. One other challenge is the limited power supply of sensors since they are battery-powered, which makes power saving a crucial feature of any WSN protocol in order to increase the lifetime of the whole network. In this paper, we present, BiPAR, a new routing protocol that counteracts the effects of the environment on sensors and, at the same time, tries to minimize its power consumption. The design of BiPAR is very intuitive. It is a semi-reliable protocol that tries to use the least amount of power to deliver data packets, i.e., it routes packets on the least-power path to the sink. If successful, this behavior saves as much battery power as possible. On the other hand, if the first transmission on the least-power path is not successful, BiPAR switches to the max-power path to the sink. This behavior consumes more energy than the first transmission, but maximizes the probability of successful communication. We simulated BiPAR in ns-2  and evaluated it under different node failure models. We compared it against GRAB , min-power routing scheme, and max-power routing scheme. Our simulations show that BiPAR delivers at least 30% more reports than GRAB, when node failures are spread all over the routing field. BiPAR delivers as much as 50% more reports than min-power routing under the same conditions.
Hany Morcos, Ibrahim Matta, and Azer Bestavros. M2RC: Multiplicative-increase/additive-decrease Multipath Routing Control for Wireless Sensor Networks. In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (ACM SenSys '04), Baltimore, Maryland, November 2004. Poster.
Vijay Erramilli, Ibrahim Matta, and Azer Bestavros. On the Interaction between Data Aggregation and Topology Control in Wireless Sensor Networks. In Proceedings of the First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (IEEE SECON 2004), Santa Clara, CA, October 2004.
Abstract: Wireless sensor networks are characterized by limited energy resources. To conserve energy, application-specific aggregation (fusion) of data reports from multiple sensors can be beneficial in reducing the amount of data flowing over the network. Furthermore, controlling the topology by scheduling the activity of nodes between active and sleep modes has often been used to uniformly distribute the energy consumption among all nodes by de-synchronizing their activities. We present an integrated analytical model to study the joint performance of in-network aggregation and topology control. We define performance metrics that capture the tradeoffs among delay, energy, and fidelity of the aggregation. Our results indicate that to achieve high fidelity levels under medium to high event reporting load, shorter and fatter aggregation/routing trees (toward the sink) offer the best delay-energy tradeoff as long as topology control is well coordinated with routing.
Georgios Smaragdakis, Ibrahim Matta, and Azer Bestavros. SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks. In Proceedings of the Second International Workshop on Sensor and Actuator Network Protocols and Applications (SANPA '04), Boston, MA (in conjunction with Mobiquitous 2004), August 2004.
Abstract: We study the impact of heterogeneity of nodes, in terms of their energy, in wireless sensor networks that are hierarchically clustered. In these networks some of the nodes become cluster heads, aggregate the data of their cluster members and transmit it to the sink. We assume that a percentage of the population of sensor nodes is equipped with additional energy resources---this is a source of heterogeneity which may result from the initial setting or as the operation of the network evolves. We also assume that the sensors are randomly (uniformly) distributed and are not mobile, the coordinates of the sink and the dimensions of the sensor field are known. We show that the behavior of such sensor networks becomes very unstable once the first node dies, especially in the presence of node heterogeneity. Classical clustering protocols assume that all the nodes are equipped with the same amount of energy and as a result, they can not take full advantage of the presence of node heterogeneity. We propose SEP, a heterogeneous-aware protocol to prolong the time interval before the death of the first node (we refer to as stability period), which is crucial for many applications where the feedback from the sensor network must be reliable. SEP is based on weighted election probabilities of each node to become cluster head according to the remaining energy in each node. We show by simulation that SEP always prolongs the stability period compared to (and that the average throughput is greater than) the one obtained using current clustering protocols. We conclude by studying the sensitivity of our SEP protocol to heterogeneity parameters capturing energy imbalance in the network. We found that SEP yields longer stability region for higher values of extra energy brought by more powerful nodes.
Niky Riga, Ibrahim Matta, and Azer Bestavros. DIP: Density Inference Protocol for wireless sensor networks and its application to density-unbiased statistics. In Proceedings of the Second International Workshop on Sensor and Actuator Network Protocols and Applications (SANPA '04), Boston, MA (in conjunction with Mobiquitous 2004), August 2004.
Abstract: Wireless sensor networks have recently emerged as enablers of important applications such as environmental, chemical and nuclear sensing systems. Such applications have sophisticated spatial-temporal semantics that set them aside from traditional wireless networks. For example, the computation of temperature averaged over the sensor field must take into account local densities. This is crucial since otherwise the estimated average temperature can be biased by over-sampling areas where a lot more sensors exist. Thus, we envision that a fundamental service that a wireless sensor network should provide is that of estimating local densities. In this paper, we propose a lightweight probabilistic density inference protocol, we call DIP, which allows each sensor node to implicitly estimate its neighborhood size without the explicit exchange of node identifiers as in existing density discovery schemes. The theoretical basis of DIP is a probabilistic analysis which yields the relationship between the number of sensor nodes contending in the neighborhood of a node and the level of contention measured by that node. Extensive simulations confirm the premise of DIP: it can provide statistically reliable and accurate estimates of local density at a very low energy cost and constant running time. We demonstrate how applications could be built on top of our DIP-based service by computing density-unbiased statistics from estimated local densities.
Eleni Trouva, Eduard Grasa, John Day, Ibrahim Matta, Lou Chitkushev, Steve Bunch, Miguel Ponce de Leon, Patrick Phelan, and Xavier Hesselbach-Serra. Transport over Heterogeneous Networks Using the RINA Architecture. In Proceedings of the 9th International Conference on Wired/Wireless Internet Communications (WWIC), Barcelona, Spain, June 2011.
Abstract: The evolution of various wireless technologies has greatly increased the interest in heterogeneous networks, in which the mobile users can enjoy services while roaming between different networks. The current Internet architecture does not seem to cope with the modern networking trends and the growing application demands for performance, stability and efficiency, as the integration of different technologies faces many problems. In this paper, we focus on the issues raised when attempting to provide seamless mobility over a hybrid environment. We highlight the shortcomings of the current architecture, discuss some of the proposed solutions and try to identify the key choices that lead to failure. Finally, we introduce RINA (Recursive Inter-Network Architecture), a newly-proposed network architecture that seeks to integrate networks of different characteristics inherently and show a simple example that demonstrates this feature.
Flavio Esposito, Anna-Maria Vegni, Ibrahim Matta, and Alessandro Neri. On Modeling Speed-based Vertical Handovers in Vehicular Networks. In Proceedings of the IEEE GLOBECOM 2010 Workshop on Seamless Wireless Mobility, Miami, Florida, December 2010.
Abstract: Although vehicular ad hoc networks are emerging as a novel paradigm for safety services, supporting real-time applications (e.g., video-streaming, Internet browsing, online gaming, etc.) while maintaining ubiquitous connectivity remains a challenge due to both high vehicle speed, and non-homogeneous nature of the network access infrastructure. To guarantee acceptable Quality-of-Service and to support seamless connectivity, vertical handovers across different access networks are performed. In this work we prove the counterintuitive result that in vehicular environments, even if a candidate network has significantly higher bandwidth, it is not always beneficial to abandon the serving network. To this end, we introduce an analytical model for a vertical handover algorithm based on vehicle speed. We argue that the proposed approach may help providers incentivize safety by forcing vehicular speed reduction to guarantee acceptable Quality-of-Service for real-time applications.
Karim Mattar, Ashwin Sridharan, Hui Zang, Ibrahim Matta, and Azer Bestavros. TCP over CDMA2000 Networks: A Cross-Layer Measurement Study. In Proceedings of the 8th Passive and Active Measurement Conference (PAM), Louvain-la-neuve, Belgium, 2007.
Abstract: Modern cellular channels in 3G networks incorporate sophisticated power control and dynamic rate adaptation which can have a significant impact on adaptive transport layer protocols, such as TCP. Though there exists studies that have evaluated the performance of TCP over such networks, they are based solely on observations at the transport layer and hence have no visibility into the impact of lower layer dynamics, which are a key characteristic of these networks. In this work, we present a detailed characterization of TCP behavior based on cross-layer measurement of transport, as well as RF and MAC layer parameters. In particular, through a series of active TCP/UDP experiments and measurement of the relevant variables at all three layers, we characterize both, the wireless scheduler in a commercial CDMA2000 network and its impact on TCP dynamics. Somewhat surprisingly, our findings indicate that the wireless scheduler is mostly insensitive to channel quality and sector load over short timescales and is mainly affected by the transport layer data rate. Furthermore, we empirically demonstrate the impact of the wireless scheduler on various TCP parameters such as the round trip time, throughput and packet loss rate.
Mohamed Hassan, Marwan Krunz, and Ibrahim Matta. Markov-based Channel Characterization for Tractable Performance Analysis in Wireless Packet Networks. IEEE Transactions on Wireless Communications, 3(3):821--831, May 2004.
Abstract: Finite-state Markov Chain (FSMC) models have often been used to characterize the wireless channel. The fitting is typically performed by partitioning the range of the received signal-to-noise ratio (SNR) into a set of intervals (states). Different partitioning criteria have been proposed in the literature, but none of them was targeted to facilitating the analysis of the packet delay and loss performance over the wireless link. In this paper, we propose a new partitioning approach that results in an FSMC model with tractable queueing performance. Our approach utilizes Jake's level-crossing analysis, the distribution of the received SNR, and the elegant analytical structure of Mitra's producer-consumer fluid queueing model. An algorithm is provided for computing the various parameters of the model, which are then used in deriving closed-form expressions for the effective bandwidth (EB) subject to packet loss and delay constraints. Resource allocation based on the EB is key to improving the perceived capacity of the wireless medium. Numerical investigations are carried out to study the interactions among various key parameters, verify the adequacy of the analysis, and study the impact of error control parameters on the allocated bandwidth for guaranteed packet loss and delay performance.
Dhiman Barman and Ibrahim Matta. Model-based Loss Inference by TCP over Heterogeneous Networks. In Proceedings of WiOpt'04: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, University of Cambridge, UK, March 2004.
Abstract: The Transmission Control Protocol (TCP) has been the protocol of choice for many Internet applications requiring reliable connections. The design of TCP has been challenged by the extension of connections over wireless links. In this paper, we investigate a Bayesian approach to infer at the source host the reason of a packet loss, whether congestion or wireless transmission error. Our approach is ``mostly'' end-to-end since it requires only one long-term average quantity (namely, long-term average packet loss probability over the wireless segment) that may be best obtained with help from the network (e.g. wireless access agent). Specifically, we use Maximum Likelihood Ratio tests to evaluate TCP as a classifier of the type of packet loss. We study the effectiveness of short-term classification of packet errors (congestion vs. wireless), given stationary prior error probabilities and distributions of packet delays conditioned on the type of packet loss (measured over a longer time scale). Using our Bayesian-based approach and extensive simulations, we demonstrate that an efficient online error classifier can be built as long as congestion-induced losses and losses due to wireless transmission errors produce sufficiently different statistics. We introduce a simple queueing model to underline the conditional delay distributions arising from different kinds of packet losses over a heterogeneous wired/wireless path. To infer conditional delay distributions, we consider Hidden Markov Model (HMM) which explicitly considers discretized delay values observed by TCP as part of its state definition, in addition to an HMM which does not as in [LiuMattaCrovella:WiOpt03]. We demonstrate how estimation accuracy is influenced by different proportions of congestion versus wireless losses and penalties on incorrect classification.
Dhiman Barman, Ibrahim Matta, Eitan Altman, and Rachid El Azouzi. TCP Optimization through FEC, ARQ and Transmission Power Tradeoffs. In Proceedings of WWIC 2004: The 2nd International Conference on Wired/Wireless Internet Communications, Frankfurt (Oder), Germany, February 2004.
Abstract: TCP performance degrades when end-to-end connections extend over wireless connections --- links which are characterized by high bit error rate and intermittent connectivity. Such link characteristics can significantly degrade TCP performance as the TCP sender assumes wireless losses to be congestion losses resulting in unnecessary congestion control actions. Link errors can be reduced by increasing transmission power, code redundancy (FEC) or number of retransmissions (ARQ). But increasing power costs resources, increasing code redundancy reduces available channel bandwidth and increasing persistency increases end-to-end delay. The paper proposes a TCP optimization through proper tuning of power management, FEC and ARQ in wireless environments (WLAN and WWAN). In particular, we conduct analytical and numerical analysis taking into account the three aforementioned factors, and evaluate TCP (and ``wireless-aware'' TCP) performance under different settings. Our results show that increasing power, redundancy and/or retransmission levels always improves TCP performance by reducing link-layer losses. However, such improvements are often associated with cost and arbitrary improvement cannot be realized without paying a lot in return. It is therefore important to consider some kind of net utility function that should be optimized, thus maximizing throughput at the least possible cost.
Karu Ratnam and Ibrahim Matta. WTCP: An Efficient Mechanism for Improving Wireless Access to TCP Services. International Journal of Communication Systems --- Special Issue on Wireless Access to the Global Internet: Mobile Radio Networks and Satellite Systems, 16:47--62, 2003.
Abstract: The Transmission Control Protocol (TCP) has been mainly designed assuming a relatively reliable wireline network. It is known to perform poorly in the presence of wireless links because of its basic assumption that any loss of a data segment is due to congestion and consequently it invokes congestion control measures. However, on wireless access links, a large number of segment losses will occur more often because of wireless link errors or host mobility. For this reason, many proposals have recently appeared to improve TCP performance in such environment. They usually rely on the wireless access points (base stations) to locally retransmit the data in order to hide wireless losses from TCP. In this paper, we present WTCP (Wireless-TCP), a new mechanism for improving wireless access to TCP services. We use extensive simulations to evaluate TCP performance in the presence of congestion and wireless losses when the base station employs WTCP, and the well-known Snoop proposal. Our results show that WTCP significantly improves the throughput of TCP connections due to its unique feature of hiding the time spent by the base station to locally recover from wireless link errors so that TCP's round trip time estimation at the source is not affected. This proved to be critical since otherwise the ability of the source to effectively detect congestion in the fixed wireline network is hindered.
Jun Liu, Ibrahim Matta, and Mark Crovella. End-to-end Inference of Loss Nature in Hybrid Wired/Wireless Environment. In Proceedings of WiOpt'03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, INRIA Sophia-Antipolis, France, March 2003.
Abstract: In a hybrid wired/wireless environment, an effective classification technique that identifies the type of a packet loss, i.e., a loss due to wireless link errors or a loss due to congestion, is needed to help a TCP connection take congestion control actions only on congestion-induced losses. Our classification technique is developed based on the loss pairs measurement technique and Hidden Markov Models (HMMs). The intuition is that the delay distribution around wireless losses is different from the one around congestion losses. An HMM can be trained to capture the delays observed around each type of loss by different state(s) in the derived HMM. We develop an automated way to associate a loss type with a state based on the delay features it captures. Thus, classification of a loss can be determined by the loss type associated with the state in which the HMM is at that loss. Simulations confirm the effectiveness of our technique under most network conditions, and its superiority over the Vegas predictor. We identify conditions under which our technique does not perform well.
Dhiman Barman and Ibrahim Matta. Effectiveness of Loss Labeling in Improving TCP Performance in Wired/Wireless Networks. In Proceedings of ICNP'2002: The 10th IEEE International Conference on Network Protocols, Paris, France, November 2002.
Abstract: The current congestion-oriented design of TCP hinders its ability to perform well in hybrid wireless/wired networks. We propose a new improvement on TCP NewReno (NewReno-FF) using a new loss labeling technique to discriminate wireless from congestion losses. The proposed technique is based on the estimation of average and variance of the round trip time using a filter, called Flip Flop filter, that is augmented with history information. We show the comparative performance of TCP NewReno, NewReno-FF, and TCP Westwood through extensive simulations. We study the fundamental gains and limits using TCP NewReno with varying Loss Labeling accuracy (NewReno-LL) as a benchmark. Lastly our investigation opens up important research directions. First, there is a need for a finer grained classification of losses (even within congestion and wireless losses) for TCP in heterogeneous networks. Second, it is essential to develop an appropriate control strategy for recovery after the correct classification of a packet loss.
Vassilis Tsaoussidis and Ibrahim Matta. Open Issues on TCP for Mobile Computing. Journal of Wireless Communications and Mobile Computing -- Special Issue on Reliable Transport Protocols for Mobile Computing, 2(1), February 2002.
Abstract: We discuss the design principles of TCP within the context of heterogeneous wired/wireless networks and mobile networking. We identify three shortcomings in TCP's behavior: (i) the protocol's error detection mechanism, which does not distinguish different types of errors and thus does not suffice for heterogeneous wired/wireless environments, (ii) the error recovery, which is not responsive to the distinctive characteristics of wireless networks such as transient or burst errors due to handoffs and fading channels, and (iii) the protocol strategy, which does not control the tradeoff between performance measures such as goodput and energy consumption, and often entails a wasteful effort of retransmission and energy expenditure. We discuss a solution-framework based on selected research proposals and the associated evaluation criteria for the suggested modifications. We highlight an important angle that did not attract the required attention so far: the need for new performance metrics, appropriate for evaluating the impact of protocol strategies on battery-powered devices.
Eleni Trouva, Eduard Grasa, John Day, Ibrahim Matta, Lou Chitkushev, Patrick Pheland, Miguel Ponce de Leon, and Steve Bunch. Is the Internet an unfinished demo? Meet RINA! In Proceedings of the TERENA Networking Conference (TNC), Prague, Czech Republic, May 2011.
Abstract: The aim of this paper is to look at the deficiencies of the current Internet architecture, consider a deeper understanding of why the current architecture is failing to provide solutions and contrast the traditional beliefs on networking with new ones, coming from a network architecture based on the fundamentals. First, we briefly introduce the early history of packet-switched networking to provide the reader with background for the discussion that follows. We highlight the main issues that the current Internet faces and expose the architectural decisions that lead to these problems. Next, we present RINA (Recursive InterNetwork Architecture), a network architecture based on fundamentals among which is that networking is interprocess communication and only IPC. We show the fundamental principles from which RINA is derived, the core elements of the architecture and give a simple example of communication. The adoption of RINA as the architecture for the future networks would enable enhanced security, inherent support for quality of service, mobility, multi-homing, offer new market opportunities and decrease the complexity of the current technology by an order of magnitude.
Luca Chiaraviglio and Ibrahim Matta. An Energy-Aware Distributed Approach for Content and Network Management. In Proceedings of the IEEE INFOCOM 2011 Green Communications and Networking Workshop, Shanghai, China, April 2011.
Abstract: We propose a distributed approach in which an Internet Service Provider (ISP) and a Content Provider (CP) cooperate to minimize total power consumption. Our solution is distributed between the ISP and the CP to limit shared information, such as network topology and servers' load. In particular, we adopt a dual decomposition technique. We investigate the performance of the proposed solution on realistic case-studies. We compare our algorithms with a centralized model, whose aim is to minimize total power consumption. We consider different power models for devices. Results show that the distributed algorithm is close to the optimal solution, with a power efficiency loss less than 17%.
Gonca Gursun, Mark Crovella, and Ibrahim Matta. Describing and Forecasting Video Access Patterns. In Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM) - Mini Conference, Shanghai, China, April 2011.
Abstract: Computer systems are increasingly driven by workloads that reflect large-scale social behavior, such as rapid changes in the popularity of media items like videos. Capacity planners and system designers must plan for rapid, massive changes in workloads when such social behavior is a factor. In this paper we make two contributions intended to assist in the design and provisioning of such systems. We analyze an extensive dataset consisting of the daily access counts of hundreds of thousands of YouTube videos. In this dataset, we find that there are two types of videos: those that show rapid changes in popularity, and those that are consistently popular over long time periods. We call these two types rarely-accessed and frequently-accessed videos, respectively. We observe that most of the videos in our data set clearly fall in one of these two types. For each type of video we ask two questions: first, are there relatively simple models that can describe its daily access patterns? And second, can we use these simple models to predict the number of accesses that a video will have in the near future, as a tool for capacity planning? To answer these questions we develop two different frameworks for characterization and forecasting of access patterns. We show that for frequently-accessed videos, daily access patterns can be extracted via principal component analysis, and used efficiently for forecasting. For rarely-accessed videos, we demonstrate a clustering method that allows one to classify bursts of popularity and use those classifications for forecasting.
J. Touch, I. Baldine, R. Dutta, G. Finn, B. Ford, S. Jordan, D. Massey, I. Matta, C. Papadopoulos, P. Reiher, and G. Rouskas. A Dynamic Recursive Unified Internet Design (DRUID). Computer Networks – Special Issue on Architectures and Protocols for the Future Internet, 55(4):919–935, March 2011.
Abstract: The Dynamic Recursive Unified Internet Design (DRUID) is a future Internet design that unifies overlay networks with conventional layered network architectures. DRUID is based on the fundamental concept of recursion, enabling a simple and direct network architecture that unifies the data, control, management, and security aspects of the current Internet, leading to a more trustworthy network. DRUID's architecture is based on a single recursive block that can adapt to support a variety of communication functions, including parameterized mechanisms for hard/soft state, flow and congestion control, sequence control, fragmentation and reassembly, compression, encryption, and error recovery. This recursion is guided by the structure of a graph of translation tables that help compartmentalize the scope of various functions and identifier spaces, while relating these spaces for resource discovery, resolution, and routing. The graph also organizes persistent state that coordinates behavior between individual data events (e.g., coordinating packets as a connection), among different associations (e.g., between connections), as well as helping optimize the recursive discovery process through caching, and supporting prefetching and distributed pre-coordination. This paper describes the DRUID architecture composed of these three parts (recursive block, translation tables, persistent state), and highlights its goals and benefits, including unifying the data, control, management, and security planes currently considered orthogonal aspects of network architecture.
Vatche Ishakian, Ibrahim Matta, and Joseph Akinwumi. On the Cost of Supporting Mobility and Multihoming. In Proceedings of the IEEE GLOBECOM 2010 Workshop on Network of the Future, Miami, Florida, December 2010.
Abstract: As the Internet has evolved and grown, an increasing number of nodes (hosts or autonomous systems) have become multihomed, i.e., a node is connected to more than one network. Multihoming can be viewed as a special case of mobility---as a node moves, it unsubscribes from one network and subscribes to another, which is akin to one interface becoming inactive and another active. The current Internet architecture has been facing significant challenges in effectively dealing with mobility (and consequently multihoming). The Recursive InterNetwork Architecture (RINA) was recently proposed as a clean-slate solution to the current problems of the Internet. In this paper, we perform an average-case cost analysis to compare the mobility / multihoming support of RINA, against that of other approaches such as LISP and Mobile-IP. We also validate our analysis using simulation.
Gonca Gursun, Ibrahim Matta, and Karim Mattar. Revisiting A Soft-State Approach to Managing Reliable Transport Connections. In Proceedings of the 8th International Workshop on Protocols for Future, Large-Scale and Diverse Network Transports (PFLDNeT), Lancester, PA, November 2010.
Abstract: We revisit the problem of connection management for reliable transport as part of our clean-slate Recursive InterNet Architecture (RINA). At one extreme, a pure soft-state (SS) approach (as in Delta-t) safely removes the state of a connection at the sender and receiver once the state timers expire without the need for explicit removal messages. And new connections are established without an explicit handshaking phase. On the other hand, a hybrid hard-state/soft-state (HS+SS) approach (as in TCP) uses both explicit handshaking as well as more limited timer-based management of the connection's state. In this paper, we consider the worst-case scenario of reliable single-message communication. Using simulation, we evaluate various approaches in terms of correctness (with respect to data loss and duplication) and robustness to bad network conditions (high message loss rate and variable channel delays). Our results show that the SS approach is more robust, and has lower message overhead and higher goodput. Thus, SS presents the best choice for reliable applications, especially those operating over bandwidth-constrained, error-prone networks. This result also suggests that within a clean-slate transport architecture, explicit connection messages for data reliability are not needed, and so a simple common packet interface based on Delta-t---rather than TCP vs. T/TCP vs. UDP, etc.--- can be provided to support both transactional and bulk, reliable and unreliable (unacknowledged) applications.
Luca Chiaraviglio and Ibrahim Matta. GreenCoop: Cooperative Green Routing with Energy-efficient Servers. In Proceedings of the First International Conference on Energy-Efficient Computing and Networking, University of Passau, Germany, April 2010.
Abstract: Energy-efficient communication has recently become a key challenge for both researchers and industries. In this paper, we propose a new model in which a Content Provider and an Internet Service Provider cooperate to reduce the total power consumption. We solve the problem optimally and compare it with a classic formulation, whose aim is to minimize user delay. Results, although preliminary, show that power savings can be huge: up to 71% on real ISP topologies. We also show how the degree of cooperation impacts overall power consumption. Finally, we consider the impact of the Content Provider location on the total power savings.
Sam Epstein, Karim Mattar, and Ibrahim Matta. Principles of Safe Policy Routing Dynamics. In Proceedings of the 17th IEEE International Conference on Network Protocols (ICNP'09), Princeton, NJ, October 2009.
Abstract: We introduce the Dynamic Policy Routing (DPR) model that captures the propagation of route updates under arbitrary changes in topology or path preferences. DPR introduces the notion of causation chains where the route flap at one node causes a flap at the next node along the chain. Using DPR, we model the Gao-Rexford (economic) guidelines that guarantee the safety (i.e., convergence) of policy routing. We establish three principles of safe policy routing dynamics. The non-interference principle provides insight into which ASes can directly induce route changes in one another. The single cycle principle and the multi-tiered cycle principle provide insight into how cycles of routing updates can manifest in any network. We develop InterferenceBeat, a distributed algorithm that propagates a small token along causation chains to check adherence to these principles. To enhance the diagnosis power of InterferenceBeat, we model four violations of the Gao-Rexford guidelines (e.g., transiting between peers) and characterize the resulting dynamics.
Karim Mattar, Ibrahim Matta, John Day, Vatche Ishakian, and Gonca Gursun. Declarative Transport: A Customizable Transport Service for the Future Internet. In Proceedings of the 5th International Workshop on Networking Meets Databases (NetDB 2009), co-located with SOSP 2009, Big Sky, MT, October 2009.
Abstract: We argue that in a clean-slate architecture, transport state is an integral part of the network state, which includes information for routing, monitoring, resource allocation, etc. Given the myriad of transport policies needed to support advanced functions such as in-network caching, in-network fair allocation, and proxying, these policies should be made programmable. We outline how flexible and generic transport policies can be specified in a declarative language to realize a transport service where distributed transport state is shared and manipulated using recursive queries.
Mina Guirguis, Joshua Tharp, Azer Bestavros, and Ibrahim Matta. Assessment of Vulnerability of Content Adaptation Mechanisms to RoQ Attacks. In Proceedings of the Eighth International Conference on Networks, Gosier, Guadeloupe/France, March 2009.
Abstract: Current computing systems employ different mechanisms to deal with overload conditions. Of those widely deployed are content adaptation mechanisms whereby the quality level of the content is adapted dynamically to mitigate overload conditions. Serving degraded content reduces strain on resources and enables them to cater for a larger set of clients. To that end, this paper studies adversarial exploits of dynamic content adaptation mechanisms to a new instantiation of Reduction of Quality (RoQ) attacks. The RoQ attack pattern is orchestrated to cause different forms of damage such as longer response time for legitimate clients, degraded content being served and underutilization of resources. We assess the impact of RoQ attacks via the potency metric which reflects the tradeoffs between the damage inflicted and the cost in mounting the attack. We validate our results through numerical analysis as well as real Internet experiments.
John Day, Ibrahim Matta, and Karim Mattar. ``Networking is IPC": A Guiding Principle to a Better Internet. In Proceedings of ReArch'08 - Re-Architecting the Internet, Madrid, SPAIN, December 2008. Co-located with ACM CoNEXT 2008.
Abstract: This position paper outlines a new network architecture that is based on the fundamental principle that networking is inter-process communication (IPC). In this model, application processes (APes) communicate via an IPC facility. The IPC processes that make up this facility provide a protocol that implements an IPC mechanism, and a protocol for managing distributed IPC (routing, security and other management tasks). Our architecture is recursive in that the IPC processes can themselves be APes requesting services from lower IPC facilities. We present the repeating patterns and structures in our architecture, and show how the proposed model would cope with the challenges faced by today's Internet (and that of the future).
Mina Guirguis, Azer Bestavros, Ibrahim Matta, and Yuting Zhang. Reduction of Quality (RoQ) Attacks on Dynamic Load Balancers: Vulnerability Assessment and Design Tradeoffs. In Proceedings of IEEE Infocom, Anchorage, Alaska, May 2007.
Abstract: One key adaptation mechanism often deployed in networking and computing systems is dynamic load balancing. The goal from employing dynamic load balancers is to ensure that the offered load would be judiciously distributed across resources to optimize the overall performance. To that end, this paper discovers and studies new instances of Reduction of Quality (RoQ) attacks that target the dynamic operation of load balancers. Our exposition is focused on a number of load balancing policies that are either employed in current commercial products or have been proposed in literature for future deployment. Through queuing theory analysis, numerical solutions, simulations and Internet experiments, we are able to assess the impact of RoQ attacks through the potency metric. We identify the key factors, such as feedback delay and averaging parameters, that expose the trade-offs between resilience and susceptibility to RoQ attacks. These factors could be used to harden load balancers against RoQ attacks. To the best of our knowledge, this work is the first to study adversarial exploits on the dynamic operation of load balancers.
Selma Yilmaz and Ibrahim Matta. An Adaptive Management Approach to Resolving Policy Conflicts. In Proceedings of IFIP Networking 2007, Atlanta, Georgia, May 2007.
Abstract: The Border Gateway Protocol (BGP) is the current inter-domain routing protocol used to exchange reachability information among Autonomous Systems (ASes) in the Internet. BGP supports policy-based routing which allows each AS to independently define a set of local policies regarding which routes to accept and advertise from/to other networks, as well as which route the AS prefers when more than one route becomes available. However, independently chosen local policies may cause global conflicts, which result in protocol divergence. We propose a new algorithm, called Adaptive Policy Management (APM), to resolve policy conflicts in a distributed manner. Akin to distributed feedback control systems, each AS independently classifies the state of the network as either conflict-free or potentially conflicting by observing its local history only (namely, route flaps). Based on the degree of measured conflicts, each AS dynamically adjusts its own path preferences---increasing its preference for observably stable paths over flapping paths. The convergence analysis of APM derives from the sub-stability property of chosen paths. APM and other competing solutions are simulated in SSFNet for different performance metrics.
Mina Guirguis, Azer Bestavros, Ibrahim Matta, and Yuting Zhang. Adversarial Exploits of End-Systems Adaptation Dynamics. Journal of Parallel and Distributed Computing (Elsevier), 67(3):318--335, March 2007.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. On the Impact of Low-Rate Attacks. In Proceedings of the 41st IEEE International Conference on Communications (ICC'06), Istanbul, Turkey, June 2006.
Abstract: Recent research have exposed new breeds of attacks that are capable of denying service or inflicting significant damage for TCP flows, without sustaining the attack traffic. Such attacks are often referred to as low-rate attacks and they stand in sharp contrast against traditional Denial of Service (DoS) attacks that can completely shut off TCP flows by flooding an Internet link. In this paper, we study the impact of these new breeds of attacks and the extent to which defense mechanisms are capable of mitigating the attack's impact. Through adopting a simple discrete-time model with a single TCP flow and a non-oblivious adversary, we were able to expose new variants of these low-rate attacks that could potentially have high attack potency per attack burst. Our analysis is focused towards worst-case scenarios, thus our results should be regarded as upper bounds on the impact of low-rate attacks rather than a real assessment under a specific attack scenario.
Azer Bestavros, Adam Bradley, Assaf Kfoury, and Ibrahim Matta. Typed Abstraction of Complex Network Compositions. In Proceedings of the 13th IEEE International Conference on Network Protocols (ICNP'05), Boston, MA, November 2005.
Abstract: The heterogeneity and open nature of network systems make analysis of compositions of components quite challenging, making the design and implementation of robust network services largely inaccessible to the average programmer. We propose the development of a novel type system and practical type spaces which reflect simplified representations of the results and conclusions which can be derived from complex compositional theories in more accessible ways, essentially allowing the system architect or programmer to be exposed only to the inputs and output of compositional analysis without having to be familiar with the ins and outs of its internals. Toward this end we present the TRAFFIC (Typed Representation and Analysis of Flows For Interoperability Checks) framework, a simple flow-composition and typing language with corresponding type system. We then discuss and demonstrate the expressive power of a type space for TRAFFIC derived from the network calculus, allowing us to reason about and infer such properties as data arrival, transit, and loss rates in large composite network applications.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. Exogeneous-Loss Aware Traffic Management in Overlay Networks: Toward Global Fairness. Computer Networks Journal (Elsevier COMNET), Volume 50 Issue 13, September 2006. (Accepted September 2005)
Abstract: For a given TCP flow, exogenous losses are those occurring on links other than the flow's bottleneck link. Exogenous losses are typically viewed as introducing undesirable ``noise'' into TCP's feedback control loop, leading to inefficient network utilization and potentially severe global unfairness. This has prompted much research on mechanisms for hiding such losses from end-points. In this paper, we show that low levels of exogenous losses are surprisingly beneficial in that they improve stability and convergence, without sacrificing efficiency. Based on this, we argue that exogenous-loss awareness should be taken into account in overlay traffic management techniques that aim to achieve global fairness. To that end, we propose an eXogenous-loss aware Queue Management (XQM) approach that actively accounts for and leverages exogenous losses on overlay paths. We envision the incorporation of XQM functionality in Overlay Traffic Managers (OTMs). We use an equation based approach to derive the quiescent loss rate for a connection based on the connection's profile and its global fair share. In contrast to other techniques, XQM ensures that a connection sees its quiescent loss rate, not only by complementing already existing exogenous losses, but also by actively hiding exogenous losses, if necessary, to achieve global fairness. We establish the advantages of exogenous-loss-aware OTMs using extensive simulations in which we contrast the performance of XQM to that of a host of traditional exogenous-loss unaware techniques.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. Reduction of Quality (RoQ) Attacks on Internet End-Systems. In Proceedings of IEEE Infocom, Miami, Florida, March 2005.
Abstract: Current computing systems depend on adaptation mechanisms to ensure that they remain in quiescent operating regions. These regions are often defined using efficiency, fairness, and stability properties. To that end, traditional research works in scalable server architectures and protocols have focused on promoting these properties by proposing even more sophisticated adaptation mechanisms, without the proper attention to security implications. In this paper, we exemplify such security implications by exposing the vulnerabilities of admission control mechanisms that are widely deployed in Internet end systems to Reduction of Quality (RoQ) attacks. RoQ attacks target the transients of a system's adaptive behavior as opposed to its limited steady-state capacity. We show that a well orchestrated RoQ attack on an end-system admission control policy could introduce significant inefficiencies that could potentially deprive an Internet end-system from much of its capacity, or significantly reduce its service quality, while evading detection by consuming an unsuspicious, small fraction of that system's hijacked capacity. We develop a control theoretic model for assessing the impact of RoQ attacks on an end-system's admission controller. We quantify the damage inflicted by an attacker through deriving appropriate metrics. We validate our findings through real Internet experiments performed in our lab.
Dhiman Barman, Georgios Smaragdakis, and Ibrahim Matta. The Effect of Router Buffer Size on HighSpeed TCP Performance. In Proceedings of Global Internet and Next Generation Networks Symposium, IEEE Global Telecommunications Conference (Globecom'04) , Dallas, TX, December 2004.
Abstract: We study the effect of the IP router buffer size on the throughput of HighSpeed TCP (HSTCP). We are motivated by the fact that in high speed routers, the buffer size is important as such a large buffer size might be a constraint. We first derive an analytical model for HighSpeed TCP and we show that for small buffer size equal to 10% of the bandwidth-delay product, HighSpeed TCP can achieve more than 90% of the bottleneck capacity. We also show that setting the buffer size equal to 20% can increase the utilization of HighSpeed TCP up to 98%. On the contrary, setting the buffer size to less than 10% of the bandwidth-delay product can decrease HighSpeed TCP's throughput significantly. We also study the performance effects under both DropTail and RED AQM. Analytical results obtained using a fixed-point approach are compared to those obtained by simulation.
Gali Diamant, Leonid Veytser, Ibrahim Matta, Azer Bestavros, Mina Guirguis, Liang Guo, Yuting Zhang, and Sean Chen. itmBench: Generalized API for Internet Traffic Managers. In Proceedings of the 10th IEEE Workshop on Computer-Aided Modeling, Analysis and Design of Communication Links and Networks (CAMAD '04), Dallas, TX (in conjunction with Globecom 2004), December 2004.
Abstract: Internet Traffic Managers (ITMs) are special machines placed at strategic places in the Internet. itmBench is an interface that allows users (e.g. network managers, service providers, or experimental researchers) to register different traffic control functionalities to run on one ITM or an overlay of ITMs. Thus itmBench offers a tool that is extensible and powerful yet easy to maintain. ITM traffic control applications could be developed either using a kernel API so they run in kernel space, or using a user-space API so they run in user space. We demonstrate the flexibility of itmBench by showing the implementation of both a kernel module that provides a differentiated network service, and a user-space module that provides an overlay routing service. Our itmBench Linux-based prototype is free software and can be obtained from http://www.cs.bu.edu/groups/itm/.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. Routing Tradeoffs inside a d-dimensional Torus with applicability to CAN. In Proceedings of the First International Computer Engineering Conference (ICENCO 2004), Cairo, Egypt, December 2004.
Abstract: Overlay networks have evolved as powerful systems enabling the development of new applications ranging from simple file sharing applications to more complex applications for managing Internet traffic. Content Addressable Network (CAN)  is one such network where nodes (peers) are organized in a d-dimensional torus. Nodes maintain state for their immediate neighbors and a request is routed inside the network through the neighbor that is closest to the destination. This process is repeated until the request reaches its destination. In this paper, we consider routing tradeoffs between space and time; Space in terms of state maintained at each node and time in terms of the average path length experienced as requests get routed inside the network. Our findings motivate the importance for nodes to maintain state, not just for their immediate neighbors, but also for a few Long Range Nodes (LRNs). These LRNs will allow longer jumps inside the space, reducing the average path length. We evaluate the effect of having these long jumps through comparing different setups that store the same amount of state. Based on this, we propose a new dynamical scheme where nodes update their LRNs in order to adapt to the nature of requests. This has significant implication when some nodes become popular in hot-spot zones. We validate our findings through simulations.
Selma Yilmaz and Ibrahim Matta. A Randomized Solution to BGP Divergence. In Proceedings of the 2nd IASTED International Conference on Communication and Computer Networks (CCN'04), Cambridge, Massachusetts, November 2004.
Abstract: The Border Gateway Protocol (BGP) is an interdomain routing protocol that allows each Autonomous System (AS) to define its own routing policies independently and use them to select the best routes. By means of policies, ASes are able to prevent some traffic from accessing their resources, or direct their traffic to a preferred route. However, this flexibility comes at the expense of a possibility of divergence behavior because of mutually conflicting policies. Since BGP is not guaranteed to converge even in the absence of network topology changes, it is not safe. In this paper, we propose a randomized approach to providing safety in BGP. The proposed algorithm dynamically detects policy conflicts, and tries to eliminate the conflict by changing the local preference of the paths involved. Both the detection and elimination of policy conflicts are performed locally, i.e. by using only local information. Randomization is introduced to prevent synchronous updates of the local preferences of the paths involved in the same conflict.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. Bandwidth Stealing via Link Targeted RoQ Attacks. In Proceedings of the 2nd IASTED International Conference on Communication and Computer Networks (CCN'04), Cambridge, Massachusetts, November 2004.
Abstract: We expose an adversarial attack scheme that aims to steal bandwidth for the benefit of a particular set of flows through lunching a distributed interference attack streams on competing flows. The extent to which the interference attack streams were successful in reducing or denying bandwidth from competing flows determines the amount of bandwidth stolen. Given such a goal, our exposed scheme stands in sharp contrast to sustained high-rate Denial-of-Service (DoS) attacks targeted directly at a specific resource or a set of flows. We demonstrate two schemes for the construction of an interference attack stream that would evade detection, and thus challenging counter-DoS techniques. Our results show the vulnerability of the current Internet to those new forms of attacks that could be easily mounted with a few number of zombie clients. We validate our findings through simple analysis, simulations and real Internet experiments.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. Exploiting the Transients of Adaptation for RoQ Attacks on Internet Resources. In Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP'04), Berlin, Germany, October 2004.
Abstract: In this paper, we expose an unorthodox adversarial attack that exploits the transients of a system's adaptive behavior, as opposed to its limited steady-state capacity. We show that a well orchestrated attack could introduce significant inefficiencies that could potentially deprive a network element from much of its capacity, or significantly reduce its service quality, while evading detection by consuming an unsuspicious, small fraction of that element's hijacked capacity. This type of attack stands in sharp contrast to traditional brute-force, sustained high-rate DoS attacks, as well as recently proposed attacks that exploit specific protocol settings such as TCP timeouts. We exemplify what we term as Reduction of Quality (RoQ) attacks by exposing the vulnerabilities of common adaptation mechanisms. We develop control-theoretic models and associated metrics to quantify these vulnerabilities. We present numerical and simulation results, which we validate with observations from real Internet experiments. Our findings motivate the need for the development of adaptation mechanisms that are resilient to these new forms of attacks.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. Adaptation=Vulnerability: Under RoQ Attacks. In Proceedings of the ACM SIGCOMM 2004, Portland, Oregon, September 2004. Poster.
Azer Bestavros, Adam Bradley, Assaf Kfoury, and Ibrahim Matta. Safe Compositional Specification of Networking Systems. ACM SIGCOMM Computer Communication Review, 34(3):21--33, July 2004.
Abstract: The science of network service composition has emerged as one of the grand themes of networking research as a direct result of the complexity and sophistication of emerging networked systems and applications. By service composition we mean that the performance and correctness properties local to the various constituent components of a service can be readily composed into global (end-to-end) properties without re-analyzing any of the constituent components in isolation, or as part of the whole composite service. The set of laws that govern such composition is what will constitute that new science of composition. The heterogeneity and open nature of network systems make composition quite challenging, and thus programming network services has been largely inaccessible to the average user. We identify (and outline) a research agenda in which we aim to develop a specification language that is expressive enough to describe different components of a network service, and that will include type hierarchies inspired by type systems in general programming languages that enable the safe composition of software components. We envision this new science of composition to be built upon several theories, possibly including control theory, network calculus, scheduling theory, and game theory. In essence, different theories may provide different languages by which certain properties of system components can be expressed and composed into larger systems. We then seek to lift these lower-level specifications to a higher level by abstracting away details that are irrelevant for safe composition at the higher level, thus making theories scalable and useful to the average user. In this paper we focus on services built upon an overlay traffic management architecture, and we use control theory and QoS theory as example theories from which we lift up compositional specifications.
Mina Guirguis, Azer Bestavros, Ibrahim Matta, Niky Riga, Gali Diamant, and Yuting Zhang. Providing Soft Bandwidth Guarantees Using Elastic TCP-based Tunnels. In Proceedings of ISCC '2004: The Ninth IEEE Symposium on Computers and Communications, Alexandria, Egypt, June 2004.
Abstract: The best-effort nature of the Internet poses a significant obstacle to the deployment of many applications that require guaranteed bandwidth. In this paper, we present a novel approach that enables two edge/border routers---which we call Internet Traffic Managers (ITM)---to use an adaptive number of TCP connections to set up a tunnel of desirable bandwidth between them. The number of TCP connections that comprise this tunnel is elastic in the sense that it increases/decreases in tandem with competing cross traffic to maintain a target bandwidth. An origin ITM would then schedule incoming packets from an application requiring guaranteed bandwidth over that elastic tunnel. Unlike many proposed solutions that aim to deliver soft QoS guarantees, our elastic-tunnel approach does not require any support from core routers (as with IntServ and DiffServ); it is scalable in the sense that core routers do not have to maintain per-flow state (as with IntServ); and it is readily deployable within a single ISP or across multiple ISPs. To evaluate our approach, we develop a flow-level control-theoretic model to study the transient behavior of established elastic TCP-based tunnels. The model captures the effect of cross-traffic connections on our bandwidth allocation policies. Through extensive simulations, we confirm the effectiveness of our approach in providing soft bandwidth guarantees.
Alberto Medina, Kave Salamatian, Nina Taft, Ibrahim Matta, Yolanda Tsang, and Christophe Diot. A Two-step Statistical Approach for Inferring Network Traffic Demands. Technical Report BU-CS-2004-011, Boston University, Computer Science Department, Boston, MA 02215, March 2004. Revises Technical Report BUCS-2003-003.
Abstract: Accurate knowledge of traffic demands in a communication network enables or enhances a variety of traffic engineering and network management tasks of paramount importance for operational networks. Directly measuring a complete set of these demands is prohibitively expensive because of the huge amounts of data that must be collected and the performance impact that such measurements would impose on the regular behavior of the network. As a consequence, we must rely on statistical techniques to produce estimates of actual traffic demands from partial information. The performance of such techniques is however limited due to their reliance on limited information and the high amount of computations they incur, which limits their convergence behavior. In this paper we study a two-step approach for inferring network traffic demands. First we elaborate and evaluate a modeling approach for generating good starting points to be fed to iterative statistical inference techniques. We call these starting points informed priors since they are obtained using actual network information such as packet traces and SNMP link counts. Second we provide a very fast variant of the EM algorithm which extends its computation range, increasing its accuracy and decreasing its dependence on the quality of the starting point. Finally, we evaluate and compare alternative mechanisms for generating starting points and the convergence characteristics of our EM algorithm against a recently proposed Weighted Least Squares approach.
Mina Guirguis, Azer Bestavros, and Ibrahim Matta. XQM: eXogenous-loss aware Queue Management. In Proceedings of ICNP 2003: The 11th IEEE International Conference on Network Protocols, Atlanta, Georgia, November 2003. Poster.
Abstract: We postulate that exogenous losses--which are typically regarded as introducing undesirable ``noise'' that needs to be filtered out or hidden from end points--can be surprisingly beneficial. In this paper we evaluate the effects of exogenous losses on transmission control loops, focusing primarily on efficiency and convergence to fairness properties. By analytically capturing the effects of exogenous losses, we are able to characterize the transient behavior of TCP. Our numerical results suggest that ``noise'' resulting from exogenous losses should not be filtered out blindly, and that a careful examination of the parameter space leads to better strategies regarding the treatment of exogenous losses inside the network. Specifically, we show that while low levels of exogenous losses do help connections converge to their fair share, higher levels of losses lead to inefficient network utilization. We draw the line between these two cases by determining whether or not it is advantageous to hide, or more interestingly introduce, exogenous losses. Our proposed approach is based on classifying the effects of exogenous losses into long-term and short-term effects. Such classification informs the extent to which we control exogenous losses, so as to operate in an efficient and fair region. We validate our results through simulations.
Anukool Lakhina, John Byers, Mark Crovella, and Ibrahim Matta. On the Geographic Location of Internet Resources. IEEE Journal on Selected Areas in Communication (J-SAC)---Special Issue on Internet and WWW Measurement, Mapping, and Modeling, 21(6), August 2003.
Abstract: One relatively unexplored question about the Internet's physical structure concerns the geographical location of its components: routers, links and autonomous systems (ASes). We study this question using two large inventories of Internet routers and links, collected by different methods and about two years apart. We first map each router to its geographical location using two different state-of-the-art tools. We then study the relationship between router location and population density; between geographic distance and link density; and between the size and geographic extent of ASes. Our findings are consistent across the two datasets and both mapping methods. First, as expected, router density per person varies widely over different economic regions; however, in economically homogeneous regions, router density shows a strong superlinear relationship to population density. Second, the probability that two routers are directly connected is strongly dependent on distance; our data is consistent with a model in which a majority (up to 75-95%) of link formation is based on geographical distance (as in the Waxman topology generation method). Finally, we find that ASes show high variability in geographic size, which is correlated with other measures of AS size (degree and number of interfaces). Among small to medium ASes, ASes show wide variability in their geographic dispersal; however, all ASes exceeding a certain threshold in size are maximally dispersed geographically. These findings have many implications for the next generation of topology generators, which we envisage as producing router-level graphs annotated with attributes such as link latencies, AS identifiers and geographical locations.
Shudong Jin, Liang Guo, Ibrahim Matta, and Azer Bestavros. A Spectrum of TCP-friendly Window-based Congestion Control Algorithms. IEEE/ACM Transactions on Networking, 11(3), June 2003.
Abstract: The increased diversity of Internet application requirements has spurred recent interests in transport protocols with flexible transmission controls. In window-based congestion control schemes, increase rules determine how to probe available bandwidth, whereas decrease rules determine how to back off when losses due to congestion are detected. The parameterization of these control rules is done so as to ensure that the resulting protocol is TCP-friendly in terms of the relationship between throughput and loss rate. In this paper, we define a new spectrum of window-based congestion control algorithms that are TCP-friendly as well as TCP-compatible under RED. Contrary to previous memory-less controls, our algorithms utilize history information in their control rules. Our proposed algorithms have two salient features: (1) They enable a wider region of TCP-friendliness, and thus more flexibility in trading off among smoothness, aggressiveness, and responsiveness; and (2) they ensure a faster convergence to fairness under a wide range of system conditions. SIMD is one instance of this spectrum of algorithms, in which the congestion window is increased super-linearly with time since the detection of the last loss. Compared to recently proposed TCP-friendly AIMD and binomial algorithms, we demonstrate the superiority of SIMD in: (1) adapting to sudden increases in available bandwidth, while maintaining competitive smoothness and responsiveness; and (2) rapidly converging to fairness and efficiency.
Marwan Krunz and Ibrahim Matta. Analytical Investigation of the Bias Effect in Variance-Type Estimators for Inference of Long-Range Dependence. Computer Networks -- Special Issue on Advances in Modeling and Engineering of Long-Range Dependent Traffic, 40(3):445--458, October 2002.
Abstract: Since the publication of the Bellcore measurements in the early nineties, long-range dependence (LRD) has been in the center of a continuous debate within the teletraffic community. While researchers largely acknowledge the significance of the LRD phenomenon, they still disagree on two issues: (1) the utility of LRD models in buffer dimensioning and bandwidth allocation, and (2) the ability of commonly used statistical tools to differentiate between true LRD and other potential interpretations of it (e.g., non-stationarity). This paper is related to the second issue. More specifically, our objective is to analytically demonstrate the limitations of variance-type indicators of LRD. Our work is not meant to advocate a particular modeling philosophy (be it LRD or SRD), but rather to emphasize the potential misidentification caused by the inherent bias in variance-type estimators. Such misidentification could lead one to wrongly conclude the presence of an LRD structure in a sequence that is known to be SRD. Our approach is based on deriving simple analytical expressions for the slope of the aggregated variance in three autocorrelated traffic models: a class of SRD (but non-Markovian) M/G/1 processes, the discrete autoregressive of order one model (SRD Markovian), and the fractional ARIMA process (LRD). Our main result is that a variance-type estimator often indicates, falsely, the existence of an LRD structure (i.e., H > 0.5) in synthetically generated traces from the two SRD models. The bias in this estimator, however, diminishes monotonically with the length of the trace. We provide some guidelines on selecting the minimum trace length so that the bias is negligible. We also contrast the VT estimator with three other estimation techniques.
Liang Guo and Ibrahim Matta. Differentiated Control of Web Traffic: A Numerical Analysis. In Proceedings of SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks, Boston, MA, August 2002.
Abstract: Internet measurements show that the size distribution of Web-based transactions is usually very skewed; a few large requests constitute most of the total traffic. Motivated by the advantages of scheduling algorithms which favor short jobs, we propose to perform differentiated control over Web-based transactions to give preferential service to short web requests. The control is realized through service semantics provided by Internet Traffic Managers, a Diffserv-like architecture. To evaluate the performance of such a control system, it is necessary to have a fast but accurate analytical method. To this end, we model the Internet as a time-shared system and propose a numerical approach which utilizes Kleinrock's conservation law to solve the model. The numerical results are shown to match well those obtained by packet-level simulation, which runs orders of magnitude slower than our numerical method.
Liang Guo and Ibrahim Matta. Scheduling Flows with Unknown Sizes: An Approximate Analysis. In Proceedings of ACM SIGMETRICS'02, Marina Del Rey, CA, June 2002. Poster.
Abstract: Previous studies have shown that giving preferential treatment to short jobs helps reduce the average system response time, especially when the job size distribution possesses the heavy-tailed property. Since it has been shown that the TCP flow length distribution also has the same property, it is natural to let short TCP flows enjoy better service inside the network. Analyzing such discriminatory system requires modification to traditional job scheduling models since usually network traffic managers do not have detailed knowledge about individual flows such as their lengths. The Multi-Level (ML) queue, proposed by Kleinrock, can be used to characterize such system. In an ML queueing system, the priority of a flow is reduced as the flow stays longer. We present an approximate analysis of the ML queueing system to obtain a closed-form solution of the average system response time function. We show that the response time of short flows can be significantly reduced without penalizing long flows.
Flavio Esposito, Ibrahim Matta, Debajyoti Bera, and Pietro Michiardi. On the Impact of Seed Scheduling in Peer-to-peer Networks. Computer Networks, July 2011. In Press.
Abstract: In a content distribution (file sharing) scenario, the initial phase is delicate due to the lack of global knowledge and the dynamics of the overlay. An unwise piece dissemination in this phase can cause delays in reaching steady state, thus increasing file download times. After showing that finding the scheduling strategy for optimal dissemination is computationally hard, even when the offline knowledge of the overlay is given, we devise a new class of scheduling algorithms at the seed (source peer with full content), based on a proportional fair approach, and we implement them on a real file sharing client. In addition to simulation results, we validated on our own file sharing client (BUTorrent) that our solution improves up to 25% the average downloading time of a standard file sharing protocol. Moreover, we give theoretical upper bounds on the improvements that our scheduling strategies may achieve.
Flavio Esposito, Ibrahim Matta, Pietro Michiardi, Nobuyuki Mitsutake, and Damiano Carra. Seed Scheduling for Peer-to-Peer Networks. In Proceedings of the Eighth IEEE International Symposium on Network Computing and Applications (IEEE NCA09), Cambridge, MA, July 2009.
Abstract: The initial phase in a content distribution (file sharing) scenario is delicate due to the lack of global knowledge and the dynamics of the overlay. An unwise distribution of the pieces in this phase can cause delays in reaching steady state, thus increasing file download times. We devise a scheduling algorithm at the seed (source peer with full content), based on a proportional fair approach, and we implement it on a real file sharing client. In dynamic overlays, our solution improves by up to 25% the average downloading time of a standard protocol ala BitTorrent.
Nikolaos Laoutaris, Georgios Smaragdakis, Azer Bestavros, Ibrahim Matta, and Ioannis Stavrakakis. Distributed Selfish Caching. IEEE Transactions on Parallel and Distributed Systems, 18(10), October 2007.
Abstract: Although cooperation generally increases the amount of resources available to a community of nodes, thus improving individual and collective performance, it also allows for the appearance of potential mistreatment problems through the exposition of one node's resources to others. We study such concerns by considering a group of independent, rational, self-aware nodes that cooperate using on-line caching algorithms, where the exposed resource is the storage at each node. Motivated by content networking applications -- including web caching, CDNs, and P2P -- this paper extends our previous work on the off-line version of the problem, which was conducted under a game-theoretic framework, and limited to object replication. We identify and investigate two causes of mistreatment: (1) cache state interactions (due to the cooperative servicing of requests) and (2) the adoption of a common scheme for cache management policies. Using analytic models, numerical solutions of these models, as well as simulation experiments, we show that on-line cooperation schemes using caching are fairly robust to mistreatment caused by state interactions. To appear in a substantial manner, the interaction through the exchange of miss-streams has to be very intense, making it feasible for the mistreated nodes to detect and react to exploitation. This robustness ceases to exist when nodes fetch and store objects in response to remote requests, i.e., when they operate as Level-2 caches (or proxies) for other nodes. Regarding mistreatment due to a common scheme, we show that this can easily take place when the ``outlier'' characteristics of some of the nodes get overlooked. This finding underscores the importance of allowing cooperative caching nodes the flexibility of choosing from a diverse set of schemes to fit the peculiarities of individual nodes. To that end, we outline an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes.
Georgios Smaragdakis, Nikolaos Laoutaris, Azer Bestavros, Ibrahim Matta, and Ioannis Stavrakakis. Mistreatment-Resilient Distributed Caching. Computer Networks Journal (Elsevier COMNET), 51(11), August 2007.
Abstract: The distributed partitioning of autonomous, self-aware nodes into cooperative groups, within which scarce resources could be effectively shared for the benefit of the group, is increasingly emerging as a hallmark of many newly-proposed overlay and peer-to-peer applications. Distributed caching protocols in which group members cooperate to satisfy local requests for objects is a canonical example of such applications. In recent work of ours we identified mistreatment as a potentially serious problem for nodes participating in such cooperative caching arrangements. Mistreatment materializes when a node's access cost for fetching objects worsens as a result of cooperation. To that end, we outlined an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes. Under this framework, a node opts to participate in the group only if its individual access cost is less than the one achieved while in isolation. In this paper, we argue against the use of such static all-or-nothing approaches which force an individual node to either join or not join a cooperative group. Instead, we advocate the use of a smoother approach, whereby the level of cooperation is tied to the benefit that a node begets from joining a group. To that end, we propose a distributed and easily deployable feedback-control scheme which mitigates mistreatment. Under our proposed adaptive scheme, a node independently emulates its performance as if it were acting in a greedy local manner and then adapts its caching policy in the direction of reducing its measured access cost below its emulated greedy local cost. Using control-theoretic analysis, we show that our proposed scheme converges to the minimal access cost, and indeed outperforms any static scheme. We also show that our scheme results in insignificant degradation to the performance of the caching group under typical operating scenaria.
Georgios Smaragdakis, Nikolaos Laoutaris, Ibrahim Matta, Azer Bestavros, and Ioannis Stavrakakis. A Feedback Control Approach to Mitigating Mistreatment in Distributed Caching Groups. In Proceedings of IFIP Networking 2006, Coimbra, Portugal, May 2006.
Abstract: We consider distributed collaborative caching groups where individual members are autonomous and self-aware. Such groups have been emerging in many new overlay and peer-to-peer applications. In a recent work of ours, we considered distributed caching protocols where group members (nodes) cooperate to satisfy requests for information objects either locally or remotely from the group, or otherwise from the origin server. In such setting, we identified the problem of a node being mistreated, i.e., its access cost for fetching information objects becoming worse with cooperation than without. We identified two causes of mistreatment: (1) the use of a common caching scheme which controls whether a node should not rely on other nodes in the group by keeping its own local copy of the object once retrieved from the group; and (2) the state interaction that can take place when the miss-request streams from other nodes in the group are allowed to affect the state of the local replacement algorithm. We also showed that both these issues ca n be addressed by introducing two simple additional parameters that affect the caching behavior (the reliance and the interaction parameters). In this paper, we argue against a static rule-of-thumb policy of setting these parameters since the performance, in terms of average object access cost, depends on a multitude of system parameters (namely, group size, cache sizes, demand skewness, and distances). We then propose a feedback control approach to mitigating mistreatment in distributed caching groups. In our approach, a node independently emulates its performance as if it were acting selfishly and then adapts its reliance and interaction parameters in the direction of reducing its measured access cost below its emulated selfish cost. To ensure good convergence and stability properties, we use a (Proportional-Integral-Differential) PID-style controller. Our simulation results show that our controller adapts to the minimal access cost and outperforms static-parameter schemes.
Yuting Zhang, Azer Bestavros, Mina Guirguis, Ibrahim Matta, and Richard West. Friendly Virtual Machines: Leveraging a Feedback-Control Model for Application Adaptation. In Proceedings of the 2005 ACM/USENIX Conference on Virtual Execution Environments, Chicago, Illinois, June 2005.
Abstract: With the increased use of ``Virtual Machines'' (VMs) as vehicles that isolate applications running on the same host, it is necessary to devise techniques that enable multiple VMs to share underlying resources both fairly and efficiently. To that end, one common approach is to deploy complex resource management techniques in the hosting infrastructure. Alternately, in this paper, we advocate the use of self-adaptation in the VMs themselves based on feedback about resource usage and availability. Consequently, we define a ``Friendly'' VM (FVM) to be a virtual machine that adjusts its demand for system resources, so that they are both efficiently and fairly allocated to competing FVMs. Such properties are ensured using one of many provably convergent control rules, such as AIMD. By adopting this distributed application-based approach to resource management, it is not necessary to make assumptions about the underlying resources nor about the requirements of FVMs competing for these resources. To demonstrate the elegance and simplicity of our approach, we present a prototype implementation of our FVM framework in User-Mode Linux (UML)---an implementation that consists of less than 500 lines of code changes to UML. We present an analytic, control-theoretic model of FVM adaptation, which establishes convergence and fairness properties. These properties are also backed up with experimental results using our prototype FVM implementation.
Abhishek Sharma, Azer Bestavros, and Ibrahim Matta. dPAM: A Distributed Prefetching Protocol for Scalable Asynchronous Multicast in P2P Systems. In Proceedings of IEEE Infocom, Miami, Florida, March 2005.
Abstract: We leverage the buffering capabilities of end-systems to achieve scalable, asynchronous delivery of streams in a peer-to-peer environment. Unlike existing cache-and-relay schemes, we propose a distributed prefetching protocol where peers prefetch and store portions of the streaming media ahead of their playout time, thus not only turning themselves to possible sources for other peers but their prefetched data can allow them to overcome the departure of their source-peer. This stands in sharp contrast to existing cache-and-relay schemes where the departure of the source-peer forces its peer children to go the original server, thus disrupting their service and increasing server and network load. Through mathematical analysis and simulations, we show the effectiveness of maintaining such asynchronous multicasts from several source-peers to other children peers, and the efficacy of prefetching in the face of peer departures. We confirm the scalability of our dPAM protocol as it is shown to significantly reduce server load.
Abhishek Sharma, Azer Bestavros, and Ibrahim Matta. Performance Evaluation of Distributed Prefetching for Asynchronous Multicast in P2P Networks. In Proceedings of the Ninth International Workshop on Web Content Caching and Distribution, Bejing, China, October 2004.
Abstract: We consider the problem of delivering real-time, near real-time and stored streaming media to a large number of asynchronous clients. This problem has been studied in the context of asynchronous multicast and peer-to-peer content distribution. In this paper we evaluate through extensive simulations the performance of the distributed prefetching protocol, dPAM [TR-BU-CS-2004-026], proposed for scalable, asynchronous multicast in P2P systems. We show that the prefetch-and-relay strategy of dPAM can reduce the server bandwidth requirement quite significantly, compared to the previously proposed cache-and-relay strategy, even when the group of clients downloading a stream changes quite frequently due to client departures.
Kanishka Gupta, Azer Bestavros, and Ibrahim Matta. Context-aware Real-time Scheduling. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2004), Toronto, Canada, May 2004. Work-in-progress Session.
Liang Guo and Ibrahim Matta. Search Space Reduction in QoS Routing. Computer Networks, 41(1), January 2003.
Abstract: To provide real-time service or engineer constrained-based paths, networks require the underlying routing algorithm to be able to find low-cost paths that satisfy given Quality-of-Service (QoS) constraints. However, the problem of constrained shortest (least-cost) path routing is known to be NP-hard, and some heuristics have been proposed to find a near-optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. In this paper, we focus on solving the delay-constrained minimum-cost path problem, and present a fast algorithm to find a near-optimal solution. This algorithm, called DCCR (for Delay-Cost-Constrained Routing), is a variant of the k-shortest path algorithm. DCCR uses a new adaptive path weight function together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near-optimal solution in a very short time. Furthermore, we use a variant of the Lagrangian relaxation method proposed by Handler and Zang to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm SSR+DCCR (for Search Space Reduction+DCCR). Through extensive simulations, we confirm that SSR+DCCR performs very well compared to the optimal but very expensive solution.
Selma Yilmaz and Ibrahim Matta. On the Scalability-Performance Tradeoffs in MPLS and IP Routing. In Proceedings of SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks, Boston, MA, August 2002.
Abstract: MPLS (Multi-Protocol Label Switching) has recently emerged to facilitate the engineering of network traffic. This can be achieved by directing packet flows over paths that satisfy multiple requirements. MPLS has been regarded as an enhancement to traditional IP routing, which has the following problems: (1) all packets with the same IP destination address have to follow the same path through the network; and (2) paths have often been computed based on static and single link metrics. These problems may cause traffic concentration, and thus degradation in quality of service. In this paper, we investigate by simulations a range of routing solutions and examine the tradeoff between scalability and performance. At one extreme, IP packet routing using dynamic link metrics provides a stateless solution but may lead to routing oscillations. At the other extreme, we consider a recently proposed Profile-based Routing (PBR), which uses knowledge of potential ingress-egress pairs as well as the traffic profile among them. Minimum Interference Routing (MIRA) is another recently proposed MPLS-based scheme, which only exploits knowledge of potential ingress-egress pairs but not their traffic profile. MIRA and the more conventional widest-shortest path (WSP) routing represent alternative MPLS-based approaches on the spectrum of routing solutions. We compare these solutions in terms of utility, bandwidth acceptance ratio as well as their scalability (routing state and computational overhead) and load balancing capability. While the simplest of the per-flow algorithms we consider, the performance of WSP is close to dynamic per-packet routing, without the potential instabilities of dynamic routing.