@article{LaoutarisSmaragdakisBestavrosEtAl:ton10, author={Nikolaos Laoutaris and Georgios Smaragdakis and Konstantinos Oikonomou and Ioannis Stavrakakis and Azer Bestavros}, title={{Distributed Server Migration for Scalable Internet Service Deployment}}, journal={IEEE/ACM Transactions on Networking}, volume = {(To Appear)}, number = {}, pages = {}, month = {}, year = 2010, abstract={} } @article{HarfoushBestavrosByers:ton08, author={Khaled Harfoush and Azer Bestavros and John Byers}, title={{Measuring Bottleneck Bandwidth of Targeted Path Segments}}, url={http://www.cs.bu.edu/fac/best/res/papers/ton09-cartouche.pdf}, keywords={Network, Internet Measurement, MassServer}, journal={IEEE/ACM Transactions on Networking}, volume = {17}, number = {1}, pages = {80-92}, month = {February}, year = 2009, abstract={Accurate measurement of network bandwidth is important for network management applications as well as flexible Internet applications and protocols which actively manage and dynamically adapt to changing utilization of network resources. Extensive work has focused on two approaches to measuring bandwidth: measuring it hop-by-hop, and measuring it end-to-end along a path. Unfortunately, best-practice techniques for the former are inefficient and techniques for the latter are only able to observe bottlenecks visible at end-to-end scope. In this paper, we develop end-to-end probing methods which can measure bottleneck capacity bandwidth along arbitrary, targeted subpaths of a path in the network, including subpaths shared by a set of flows. We evaluate our technique through ns simulations, then provide a comparative Internet performance evaluation against hop-by-hop and end-to-end techniques. We also describe a number of applications which we foresee as standing to benefit from solutions to this problem, ranging from network troubleshooting and capacity provisioning to optimizing the layout of application-level overlay networks, to optimized replica placement.} } @article{LaoutarisSmaragdakisBestavrosEtAl:tpds07, author={Georgios Smaragdakis and Nikolaos Laoutaris and Azer Bestavros and Ibrahim Matta and Ioannis Stavrakakis}, title={{Distributed Selfish Caching}}, url={http://www.cs.bu.edu/fac/best/res/papers/tpds07-dsc.pdf}, journal = "{IEEE Transactions on Parallel and Distributed Systems}", month = {October}, year = 2007, number = {10}, volume = {18}, pages = {1361-1375}, publisher = {{IEEE}}, 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 online caching algorithms, where the exposed resource is the storage at each node. Motivated by content networking applicationsincluding Web caching, content delivery networks (CDNs), and peer-to-peer (P2P)this paper extends our previous work on the offline 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, and simulation experiments, we show that online 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, that is, 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 -Y´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. } } @article{SmaragdakisLaoutarisBestavrosEtAl:comnet07, author={Georgios Smaragdakis and Nikolaos Laoutaris and Azer Bestavros and Ibrahim Matta and Ioannis Stavrakakis}, title={{Mistreatment-Resilient Distributed Caching}}, url={http://www.cs.bu.edu/fac/best/res/papers/comnet07-dsc.pdf}, journal = "{The Computer Networks Journal (COMNET): The International Journal of Computer and Telecommunications Networking}", month = {August}, year = 2007, number = {11}, volume = {51}, publisher = {{Elsevier}}, 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. } } @article{GuirguisBestavrosMattaZhang:jpdc07, author={Mina Guirguis and Azer Bestavros and Ibrahim Matta and Yuting Zhang}, title={{Adversarial Exploits of End-Systems Adaptation Dynamics}}, keywords={Internet Systems, Security, Real-Time Dynamics, Control Theory}, journal = "{Journal of Parallel and Distributed Computing}", year = 2007, number = {3}, pages = {318-328}, volume = {67}, publisher = {{Elsevier}}, url={http://www.cs.bu.edu/fac/best/res/papers/jpdc07-roq.pdf}, abstract = {Internet end-systems employ various adaptation mechanisms that enable them to respond adequately to legitimate requests in overload situations. Today, these mechanisms are incorporated in most scalable end-systems through the use of one or more component subsystems such as admission controllers, traffic shapers, content transcoders, QoS Controllers, and load balancers. While the design of these components has been heavily investigated and significantly fine-tuned for efficiency and scalability purposes, the security implication of the adaptation mechanisms used in these components has not been on the radar to system designers. To that end, this paper exposes adversarial exploits of the dynamics that result from the adaptive nature of these components. We show that a well orchestrated Reduction of Quality (RoQ) attack could induce significant inefficiencies or reduce the service quality of end-systems, without resorting to brute-force Denial-of-Service (DoS) exploits that target the limited steady-state capacity of these end-systems. We present a general analytical framework that captures the effect of RoQ exploits on the underlying optimization process of the adaptation mechanisms. Using detailed models, we instantiate this general framework for some of the aforementioned end-system adaptation mechanisms, focusing on admission controllers and load balancers. Our exposition is supported with numerical solutions of analytical models, which are validated using results from detailed simulations, and measurements from real Internet experiments performed in our lab. } } @article{SmaragdakisLaoutarisMattaBestavros:lncs06, author={Georgios Smaragdakis and Nikolaos Laoutaris and Ibrahim Matta and Azer Bestavros and Ioannis Stavrakakis}, title={{A Feedback Control Approach to Mitigating Mistreatment in Distributed Caching Groups}}, journal={Lecture Notes in Computer Science 3976 - 0331}, year=2006, url={http://www.cs.bu.edu/fac/best/res/papers/lncs06.pdf} } @article{VelosoAlmeidaMeiraBestavrosJin:ton06, author={Eveline Veloso and Virgilio Almeida and Wagner Meira and Azer Bestavros and Shudong Jin}, title={{A Hierarchical Characterization of a Live Streaming Media Workload}}, journal={IEEE/ACM Transactions on Networking}, volume = {14}, number = {1}, pages = {}, month = {February}, year = 2006, keywords={Streaming Media Characterization, Live Content Workloads, Internet Measurement, Networking, Web, Real-Time}, abstract={We present what we believe to be the first thorough characterization of {\em live} streaming media content delivered over the Internet. Our characterization of over 3.5 million requests spanning a 28-day period is done at three increasingly granular levels, corresponding to clients, sessions, and transfers. Our findings support two important conclusions. First, we show that the nature of interactions between users and objects is fundamentally different for live versus stored objects. Access to stored objects is {\em user driven}, whereas access to live objects is {\em object driven}. This reversal of active/passive roles of users and objects leads to interesting dualities. For instance, our analysis underscores a Zipf-like profile for user interest in a given object, which is in contrast to the classic Zipf-like popularity of objects for a given user. Also, our analysis reveals that transfer lengths are highly variable and that this variability is due to the stickiness of clients to a particular live object, as opposed to structural (size) properties of objects. Second, by contrasting two live streaming workloads from two radically different applications, we conjecture that some characteristics of live media access workloads are likely to be highly dependent on the nature of the live content being accessed. In our study, this dependence is clear from the strong temporal correlations observed in the traces, which we attribute to the synchronizing impact of live content on access characteristics. Based on our analyses, we present a model for live media workload generation that incorporates many of our findings, and which we implement in \sc{Gismo} \cite{JinBestavros:per01}.} } @article{JinBestavros:comnet06, author={Shudong Jin and Azer Bestavros}, title={{Small-world Characteristics of Internet Topologies and Multicast Scaling}}, keywords={Internet Characterization, Internet Topology, Multicast}, url={http://www.cs.bu.edu/fac/best/res/papers/comnet06-smallworld.pdf}, journal = "{The Computer Networks Journal (COMNET): The International Journal of Computer and Telecommunications Networking}", month = {April}, year = 2006, number = {5}, volume = {50}, publisher = {{Elsevier}}, abstract={ Recent work has shown that the physical connectivity of the Internet exhibits small-world behavior. Characterizing such behavior is important not only for generating realistic Internet topology, but also for the proper evaluation of large-scale content delivery techniques. Along this line, this paper tries to explain how the small-world behavior arises in the Internet topologies and how it impacts the performance of multicast techniques. First, we attribute the small-world behavior to two possible causes—namely the variability of vertex degree and the preference for local connections for vertices. We have found that both factors contribute with different relative degrees to the small-world behavior of the autonomous system (AS) level and router level Internet topologies. For the AS level topology, we observe that the high variability of vertex degree is sufficient to cause the small-world behavior, but for the router level topology, the preference for local connectivity plays a more important role. Second, we propose better models to generate small-world Internet topologies. Our models incorporate both causes of small-world behavior, and generate graphs closely resemble real Internet graphs. Third, using simulation we demonstrate the importance of our work by studying the scaling behavior of multicast techniques. We show that multicast tree size largely depends on the network topology. If topology generators capture only the variability of vertex degree, they are likely to underestimate the benefit of multicast techniques. } } @article{GuirguisBestavrosMatta:comnet06, author={Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title={{Exogenous-Loss Aware Traffic Management in Overlay Networks: Toward Global Fairness}}, keywords={Internet Traffic Management, Overlay Networking, Real-Time Buffer Management}, url={http://www.cs.bu.edu/fac/best/res/papers/comnet05-xqm.pdf}, journal = "{The Computer Networks Journal (COMNET): The International Journal of Computer and Telecommunications Networking}", volume = {50}, number = {13}, year = {2006}, issn = {1389-1286}, pages = {2331--2348}, publisher = {{Elsevier}}, 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. } } @article{BestavrosByersHarfoush:tpds05, author = {Azer Bestavros and John Byers and Khaled Harfoush}, title = {{Inference and Labeling of Metric-Induced Network Topologies}}, journal = {{IEEE Transactions on Parallel and Distributed Systems}}, publisher = {{IEEE Press}}, number = {10}, volume = {16}, month = {October}, year = {2005}, url = {http://www.cs.bu.edu/fac/best/res/papers/tpds05.pdf}, keywords={MassServer, Internet Measurement, Distributed Systems, Network Characterization}, abstract = { The development and deployment of distributed network-aware applications and services require the ability to compile and maintain a model of the underlying network resources with respect to one or more characteristic properties of interest. To be manageable, such models must be compact; and to be general-purpose, should enable a representation of properties along temporal, spatial, and measurement resolution dimensions. In this paper, we propose MINT -- a general framework for the construction of such metric-induced models using end-to-end measurements. We present the basic theoretical underpinnings of MINT for a broad class of performance metrics, and describe PERISCOPE, a Linux embodiment of MINT constructions. We instantiate MINT and PERISCOPE for a specific metric of interest -- namely, packet loss rates -- and present results of simulations and Internet measurements that confirm the effectiveness and robustness of our constructions over a wide range of network conditions. } } @article{BestavrosBradleyKfouryMatta:ccr04, author = {Azer Bestavros and Adam Bradley and Assaf Kfoury and Ibrahim Matta}, title = {{Safe Compositional Specification of Networking Systems}}, journal = {{ACM SIGCOMM Computer Communication Review (CCR)}}, publisher = {{ACM Press}}, number = 3, volume = 34, month = {{July}}, year = {2004}, url = {http://www.cs.bu.edu/fac/best/res/papers/ccr04.pdf}, abstract = { The Science of Network Service Composition has clearly emerged as one of the grand themes driving many of our research questions in the networking field today [NeXtworking 2003]. This driving force stems from the rise of sophisticated applications and new networking paradigms. 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 would govern such composition is what will constitute that new science of composition. The combined heterogeneity and dynamic open nature of network systems makes 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 (e.g., control theory, game theory, network calculus, percolation theory, economics, queuing 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 management architecture, and we use control theory and QoS theory as example theories from which we lift up compositional specifications.} } @article{JinBestavrosIyengar:mmsj03, author={Shudong Jin and Azer Bestavros and Arun Iyengar}, title={{Network-Aware Partial Caching For Internet Streaming Media}}, journal={ACM Multimedia Systems Journal}, volume = "", number = "", pages = "", month = "", year=2003, url={}, keywords={Internet, Streaming Media, Caching, Web, Real-Rime, MassServer-Pub}, } @article{JinBestavros:per01, author={Shudong Jin and Azer Bestavros}, title={{GISMO: Generator of Streaming Media Objects and Workloads}}, journal={{Performance Evaluation Review}}, keywords={Internet Modeling, Benchmarking, Simulation, Multimedia, Streaming Media Delivery}, year=2001, url = {http://www.cs.bu.edu/faculty/best/res/papers/per01.pdf}, pubisher={ACM Sigmetrics}, number={3}, volume={29}, abstract={This paper presents a tool called GISMO (Generator of Internet Streaming Media Objects and workloads). GISMO enables the specification of a number of streaming media access characteristics, including object popularity, temporal correlation of request, seasonal access patterns, user session durations, user inter-activity times, and variable bit-rate (VBR) self-similarity and marginal distributions. The embodiment of these characteristics in GISMO enables the generation of realistic and scalable request streams for use in the benchmarking and comparative evaluation of Internet streaming media delivery techniques. To demonstrate the usefulness of GISMO, we present a case study that shows the importance of various workload characteristics in determining the effectiveness of proxy caching and server patching techniques in reducing bandwidth requirements.} } @article{JinBestavros:jcc01, author={Shudong Jin and Azer Bestavros}, title={{GreedyDual* Web Caching Algorithm: Exploiting the Two Sources of Temporal Locality in Web Request Streams}}, keywords={Network caching, Web Proxy Caching Algorithms, Web locality of reference}, journal={International Journal on Computer Communications}, year=2001, volume=24, number=2, pages={174-183}, month={February}, pubisher={Elsevier} } @article{BarfordBestavrosBradleyCrovella:wwwj99, author={Paul Barford and Azer Bestavros and Adam Bradley and Mark Crovella}, title={{Changes in Web Client Access Patterns: Characteristics and Caching Implications}}, journal={{World Wide Web Journal, Special Issue on Characterization and Performance Evaluation}}, volume={2}, number={1999}, pages={15-28}, month={August}, note={Baltzer Science Publishers}, year=1999, abstract={Understanding the nature of the workloads and system demands created by users of the World Wide Web is crucial to properly designing and provisioning Web services. Previous measurements of Web client workloads have been shown to exhibit a number of characteristic features; however, it is not clear how those features may be changing with time. In this study we compare two measurements of Web client workloads separated in time by three years, both captured from the same computing facility at Boston University. The older dataset, obtained in 1995, is well-known in the research literature and has been the basis for a wide variety of studies. The newer dataset was captured in 1998 and is comparable in size to the older dataset. The new dataset has the drawback that the collection of users measured may no longer be representative of general Web users; however using it has the advantage that many comparisons can be drawn more clearly than would be possible using a new, different source of measurement. Our results fall into two categories. First we compare the statistical and distributional properties of Web requests across the two datasets. This serves to reinforce and deepen our understanding of the characteristic statistical properties of Web client requests. We find that the kinds of distributions that best describe document sizes have not changed between 1995 and 1998, although specific values of the distributional parameters are different. Second, we explore the question of how the observed differences in the properties of Web client requests, particularly the popularity and temporal locality properties, affect the potential for Web file caching in the network. We find that for the computing facility represented by our traces between 1995 and 1998, (1) the benefits of using size-based caching policies have diminished; and (2) the potential for caching requested files in the network has declined.} } @article{Bestavros:jicae97, author={Azer Bestavros}, title={{Engineering Real-Time Robotics Software Systems Using Cleopatra}}, journal={Integrated Computer-Aided Engineering}, volume={5}, number={4}, pages={349-367}, note={IOS Press}, month={October}, year=1998, abstract={In this paper we overview our work on Cleopatra, an object-oriented specification and programming language, and show how Cleopatra was instrumental in the design and testing of a sensory-motor robotics application using a generalization of Brooks' subsumption architecture. The specification of a real-time software control system is often the result of a process, whereby a conceptual control system is fleshed out as a computer program. To be accurate, this process must abide by operational (e.g., timing or synchronization) constraints, which necessitate that knowledge about the available computation resources be utilized. Cleopatra is unique in that, unlike most traditional programming languages for non-real-time systems, it does not abstract away the details of the underlying machinery (e.g., hardware and operating system). By subjecting programmers to (at least some) limitations of the underlying machinery, the likelihood of timing failures is greatly reduced because programmers must write programs that are cognizant of these limitations. Unrealistic systems---possessing properties such as infinite capacities or perfect timing---cannot be specified. We argue that this ``ounce of prevention'' at the specification level is likely to spare a lot of time and energy in the development cycle---not to mention the elimination of potential hazards that would have gone unnoticed.} } @article{Bestavros:jis97, author="Azer Bestavros", title={{Load Profiling in Distributed Real-Time Systems}}, journal={Journal of Information Sciences}, note={North-Holland}, volume={101}, number={1/2}, pages={1-27}, year=1997, month={June}, abstract={ Load balancing is often used to ensure that nodes in a distributed systems are equally loaded. In this paper, we show that for real-time systems, load balancing is not desirable. In particular, we propose a new load-profiling strategy that allows the nodes of a distributed system to be unequally loaded. Using load profiling, the system attempts to distribute the load amongst its nodes so as to maximize the chances of finding a node that would satisfy the computational needs of incoming real-time tasks. To that end, we describe and evaluate a distributed load-profiling protocol for dynamically scheduling time-constrained tasks in a loosely-coupled distributed environment. When a task is submitted to a node, the scheduling software tries to schedule the task locally so as to meet its deadline. If that is not feasible, it tries to locate another node where this could be done with a high probability of success, while attempting to maintain an overall load profile for the system. Nodes in the system inform each other about their state using a combination of multicasting and gossiping. The performance of the proposed protocol is evaluated via simulation, and is contrasted to other dynamic scheduling protocols for real-time distributed systems. Based on our findings, we argue that keeping a diverse availability profile and using passive bidding (through gossiping) are both advantageous to distributed scheduling for real-time systems.} } @article{bestavros:97e, author="Azer Bestavros", title={{World Wide Web Traffic Reduction and Load Balancing Through Server-Based Caching}}, journal={IEEE Concurreny: Special Issue on Parallel and Distributed Technology}, note={IEEE Press}, pages={56-67}, volume=5, number=1, month={Jan-Mar}, year=1997, abstract={ Research on replication techniques to reduce traffic and minimize the latency of information retrieval in a distributed system has concentrated on client-based caching, whereby recently/frequently accessed information is cached at a client (or at a proxy thereof) in anticipation of future accesses. We believe that such myopic solutions---focussing exclusively on a particular client or set of clients---are likely to have a limited impact. Instead, we offer a solution that allows the replication of information to be done on a global supply/demand basis. We propose a data dissemination mechanism that allows information to propagate from its producers to servers that are closer to its consumers. This dissemination reduces network traffic and balances load amongst servers by exploiting geographic and temporal locality of reference properties exhibited in client access patterns. The level of dissemination depends on the relative popularity of documents, and on the expected reduction in traffic that results from such dissemination. We used extensive HTTP logs to motivate an analytical model of server popularity and file access profiles. Using that model we show that by disseminating the most popular documents on servers closer to clients, network traffic could be reduced considerably, while servers are load-balanced. We present results of trace-driven simulations that quantify the performance gains achievable through the use of such a protocol. } } @article{bestavros:97c, author="Azer Bestavros", title={{Speculative Service in Large-scale Distributed Information Systems}}, journal={International Journal on Computer Applications}, note={ISCA Press}, pages={1-9}, volume=4, number=1, month={April}, year=1997 } @article{bestavros:96p, author={Azer Bestavros and Carlos Cunha}, title={{Server-initiated Document Dissemination for the WWW}}, journal={IEEE Data Engineering Bulletin}, volume=19, issue=3, pages={3-11}, month={September}, year=1996, url={http://www.cs.bu.edu/fac/best/res/papers/debull96.ps} } @inproceedings{BassemBestavros:wasa09, author = {Christine Bassem and Azer Bestavros}, title = {{CSR: Constrained Selfish Routing in Ad-Hoc Networks}}, booktitle = {Proceedings of WASA'09: International Conference on Wireless Algorithms, Systems, and Applications}, address={Boston, MA}, month = {{August}}, year = {2009}, url = {http://www.cs.bu.edu/fac/best/res/papers/wasa09.pdf}, abstract = { } } @inproceedings{LondonoBestavrosTeng:hotcloud09, author = {Jorge Londono and Azer Bestavros and Shanghua Teng}, title = {{Colocation Games And Their Application to Distributed Resource Management}}, booktitle = {Proceedings of USENIX HotCloud'09: Workshop on Hot Topics in Cloud Computing}, address={San Diego, CA}, month = {{June}}, year = {2009}, url = {http://www.cs.bu.edu/fac/best/res/papers/hotcloud09.pdf}, abstract = { } } @inproceedings{OceanKfouryBestavros:mompes09, author = {Michael Ocean and Assaf Kfoury and Azer Bestavros}, title = {{A Formal Type-Centric Framework for Verification and Resource Allocation in Pervasive Sense-and-Respond Systems}}, booktitle = {Proceedings of MOMPES'09: The 6th ICSE Workshop on Model-based Methodologies for Pervasive and Embedded Software}, address={Vancouver, Canada}, month = {{May}}, year = {2009}, url = {http://www.cs.bu.edu/fac/best/res/papers/mompes09.pdf}, abstract = { } } @inproceedings{GuirguisBestavrosMatta:icn09, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title = {{Assessment of Vulnerability of Content Adaptation Mechanisms to RoQ Attacks}}, booktitle = {{Proceedings of ICN'09: IARIA International Conference on Networks}}, address={Guadeloupe, France}, month = {{March}}, year = {2009}, url = {http://www.cs.bu.edu/fac/best/res/papers/icn09.pdf}, abstract = { } } @inproceedings{LondonoBestavros:mmcn09, author = {Jorge Londono and Azer Bestavros}, title = {{A Two-Tiered On-Line Server-Side Bandwidth Reservation Framework for the Real-Time Delivery of Multiple Video Streams}}, booktitle = {Proceedings of MMCN'09: The SPIE and IS\&T Conference on Multimedia Computing and Networking}, address={San Jose, CA}, month = {{January}}, year = {2009}, url = {http://www.cs.bu.edu/fac/best/res/papers/mmcn09.pdf}, abstract = { } } @inproceedings{MorcosBestavrosMatta:secon08, author = {Hany Morcos and Azer Bestavros and Abraham Matta}, title = {{Amorphous Placement and Informed Diffusion for Timely Field Monitoring by Autonomous, Resource-Constrained, Mobile Sensors}}, booktitle = {Proceedings of SECON'08: The IEEE Conference on Sensor, Mesh and Ad Hoc Communications and Networks}, address={San Francisco, CA}, month = {{June}}, year = {2008}, url = {http://www.cs.bu.edu/fac/best/res/papers/secon08.pdf}, abstract = { } } @inproceedings{SmaragdakisLekakisLaoutarisBestavros+:conext08, author = {Georgios Smaragdakis and Vassilis Lekakis and Nikolaos Laoutaris and Azer Bestavros and John W. Byers and Mema Roussopoulos}, title = {{EGOIST: Overlay Routing using Selfish Neighbor Selection}}, booktitle = {{Proceedings of ACM CoNEXT 2008}}, address={Madrid, Spain}, month = {{November}}, year = {2008}, url = {http://www.cs.bu.edu/fac/best/res/papers/conext08.pdf}, abstract = { A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of connectivity management, i.e., folding new arrivals into an existing overlay, and re-wiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for specific applications designed to work well in real deployments, and providing abstractions for the underlying problem that are analytically tractable, especially via game-theoretic analysis. In this paper, we unify these two thrusts by using insights gleaned from novel, realistic theoretic models in the design of Egoist a distributed overlay routing system that we implemented, deployed, and evaluated on PlanetLab. Using extensive measurements of paths between nodes, we demonstrate that Egoist˘s neighbor selection primitives significantly outperform existing heuristics on a variety of performance metrics, including delay, available bandwidth, and node utilization. Moreover, we demonstrate that Egoist is competitive with an optimal, but unscalable full-mesh approach, remains highly effective under significant churn, is robust to cheating, and incurs minimal overhead. Finally, we use a multiplayer peer-to-peer game to demonstrate the value of Egoist to end-user applications.} } @inproceedings{MorcosAtiaBestavrosMatta:dcoss08, author = {Hany Morcos and George Atia and Azer Bestavros and Abraham Matta}, title = {{An Information Theoretic Framework for Field Monitoring Using Autonomously Mobile Sensors}}, booktitle = {Proceedings of DCOSS'08: The 4th IEEE/ACM International Conference on Distributed Computing in Sensor Systems}, address={Santorini, Greece}, month = {{June}}, year = {2008}, url = {http://www.cs.bu.edu/fac/best/res/papers/dcoss08.pdf}, note={(Best Paper Award)}, abstract = { } } @inproceedings{SmaragdakisLaoutarisMichiardiBestavros+:infocom08, author = {Georgios Smaragdakis and Nikolaos Laoutaris and Pietro Michiardi and Azer Bestavros and John Byers and Mema Roussopoulos}, title = {{Swarming on optimized graphs for n-way broadcast}}, booktitle = {Proceedings of Infocom'08: The IEEE International Conference on Computer Communication}, address={Phoenix, Arizona}, month = {{April}}, year = {2008}, url = {http://www.cs.bu.edu/fac/best/res/papers/infocom08.pdf}, abstract = { } } @inproceedings{LondonoBestavros:hpgc08, author={Jorge Londono and Azer Bestavros}, title={{netEmbed: A Network Resource Mapping Service for Distributed Applications}}, booktitle = {Proceedings of the IEEE/ACM IPDPS High-Performance Grid Computing Workshop}, address={Miami, Florida}, month = {{April}}, year = {2008}, url = {http://www.cs.bu.edu/fac/best/res/papers/hpgc08.pdf}, abstract = { } } @inproceedings{ManjanathaBestavrosGaynor:hcmdss07, author={Sowmya Manjanatha and Azer Bestavros and Mark Gaynor}, title={Rule-Based Decision Support for Sensor Networks using snBench}, booktitle = {Proceedings of the Workshop on High Confidence Medical Device Software and Systems (HCMDSS'07)}, address={Cambridge, Massachusetts}, month = {{June}}, year = {2007}, url = {http://www.cs.bu.edu/fac/best/res/papers/hcmdss07.pdf}, abstract = { } } @inproceedings{OceanBestavros:wisec08, author = {Michael Ocean and Azer Bestavros}, title = {{Wireless and physical security via embedded sensor networks}}, booktitle = {Proceedings of WiSec'08: The ACM Conference on Wireless Network Security}, address={Alexandria, Virginia}, month = {{March}}, year = {2008}, url = {http://www.cs.bu.edu/fac/best/res/papers/wisec08.pdf}, note={(Best Paper Award)}, abstract = { } } @inproceedings{LondonoBestavros:middleware07, author={Jorge Londono and Azer Bestavros}, title={{netEmbed: A Service for Embedding Distributed Applications (Extended Abstract and Demo)}}, booktitle = {Proceedings of the ACM/IFIP/Usenix Middleware Conference}, address={Newport Beach, California}, month = {{November}}, year = {2007}, url = {http://www.cs.bu.edu/fac/best/res/papers/middleware07.pdf}, abstract = { } } @inproceedings{LaoutarisSmaragdakisBestavrosByers:infocom07, author = {Nikolaos Laoutaris and Georgios Smaragdakis and Azer Bestavros and John Byers}, title = {{Implications of Selfish Neighbor Selection in Overlay Networks}}, booktitle = {Proceedings of Infocom'07: The IEEE International Conference on Computer Communication}, address={Anchorage, Alaska}, month = {{May}}, year = {2007}, url = {http://www.cs.bu.edu/fac/best/res/papers/infocom07-sns.pdf}, abstract = { In a typical overlay network for routing or content sharing, each node must select a fixed number of immediate overlay neighbors for routing traffic or content queries. A selfish node entering such a network would select neighbors so as to minimize the weighted sum of expected access costs to all its destinations. Previous work on selfish neighbor selection has built intuition with simple models where edges are undirected, access costs are modeled by hop-counts, and nodes have potentially unbounded degrees. However, in practice, important constraints not captured by these models lead to richer games with substantively and fundamentally different outcomes. Our work models neighbor selection as a game involving directed links, constraints on the number of allowed neighbors, and costs reflecting both network latency and node preference. We express a node's "best response" wiring strategy as a k-median problem on asymmetric distance, and use this formulation to obtain pure Nash equilibria. We experimentally examine the properties of such stable wirings on synthetic topologies, as well as on real topologies and maps constructed from PlanetLab and AS-level Internet measurements. Our results indicate that selfish nodes can reap substantial performance benefits when connecting to overlay networks constructed by naive nodes. On the other hand, in overlays that are dominated by selfish nodes, the resulting stable wirings are optimized to such great extent that even uninformed newcomers can extract near-optimal performance through naive wiring strategies. } } @inproceedings{LaoutarisSmaragdakisBestavros:infocom07, author = {Nikolaos Laoutaris and Georgios Smaragdakis and Konstantinos Oikonomou and Ioannis Stavrakakis and Azer Bestavros}, title = {{Distributed Placement of Service Facilities in Large-Scale Networks}}, booktitle = {Proceedings of Infocom'07: The IEEE International Conference on Computer Communication}, address={Anchorage, Alaska}, month = {{May}}, year = {2007}, url = {http://www.cs.bu.edu/fac/best/res/papers/infocom07-dfl.pdf}, abstract = {} } @inproceedings{LaoutarisZervasBestavrosKollios:infocom07, author = {Nikolaos Laoutaris and Georgios Zervas and Azer Bestavros and George Kollios}, title = {{The Cache Inference Problem and its Application to Content and Request Routing}}, booktitle = {Proceedings of Infocom'07: The IEEE International Conference on Computer Communication}, address={Anchorage, Alaska}, month = {{May}}, year = {2007}, url = {http://www.cs.bu.edu/fac/best/res/papers/infocom07-cip.pdf}, abstract = {} } @inproceedings{GuirguisBestavrosMatta:infocom07, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title = {{Reduction of Quality (RoQ) Attacks on Dynamic Load Balancers: Vulnerability Assessment and Design Tradeoffs}}, booktitle = {Proceedings of Infocom'07: The IEEE International Conference on Computer Communication}, address={Anchorage, Alaska}, month = {{May}}, year = {2007}, url = {http://www.cs.bu.edu/fac/best/res/papers/infocom07-roq.pdf}, 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. } } @inproceedings{DuarteMattosBestavrosAlmeida:icwsm07, author = {Fernando Duarte and Bernardo Mattos and Azer Bestavros and Virgilio Almeida and Jussara Almeida}, title = {{Traffic Characteristics and Communication Patterns in Blogosphere}}, booktitle = {Proceedings of ICWSM'07: International Conference on Weblogs and Social Media}, address={Boulder, Colorado}, month = {{March}}, year = {2007}, url = {http://www.cs.bu.edu/fac/best/res/papers/icwsm07.pdf}, abstract = {} } @inproceedings{OceanBestavrosKfoury:vee06, author = {Michael Ocean and Azer Bestavros and Assaf Kfoury}, title = {{snBench}: Programming and Virtualization Framework for Distributed Multitasking Sensor Networks}, booktitle = {Proceedings of VEE'06: The 2nd ACM/Usenix International Conference on Virtual Execution Environments}, month = {June}, year = {2006}, isbn = {1-59593-332-6}, pages = {89 - 99}, location = {Ottawa, Ontario, Canada}, url={http://www.cs.bu.edu/fac/best/res/papers/vee06.pdf}, publisher = {ACM Press}, address = {New York, NY, USA}, abstract={} } @inproceedings{GuirguisBestavrosMatta:icc06, author={Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title={{On the Impact of Low-Rate Attacks}}, keywords={Real-Time, Web, Internet, Network, Security}, url={http://www.cs.bu.edu/fac/best/res/papers/icc06.pdf}, booktitle={{Proceedings of ICC'2006: The IEEE International Conference on Communications}}, year=2006, month={June}, address={Istanbul, Turkey}, abstract={} } @inproceedings{LaoutarisSmaragdakisBestavrosStavrakakis:infocom06, author = {{Nikolaos Laoutaris and Georgios Smaragdakis and Azer Bestavros and Ioannis Stavrakakis}}, title = {{Mistreatment in Distributed Caching Groups: Causes and Implications}}, booktitle = {Proceedings of Infocom'06: The IEEE International Conference on Computer Communication}, address={Barcelona, Spain}, month={April}, year = {2006}, url = "http://www.cs.bu.edu/fac/best/res/papers/infocom06.pdf", keywords={Web Caching, Web, Internet, Network, Security, Distributed Systems, Game Theory}, 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 of 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 limited to object replication and was conducted under a game-theoretic framework. 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 replacement/redirection/admission 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. When this becomes possible, 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 the 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. } } @inproceedings{LiChangKolliosBestavros:icde06, author = {Feifei Li and Ching Chang and George Kollios and Azer Bestavros}, title={{Characterizing and Exploiting Reference Locality in Data Stream Applications}}, booktitle = {Proceedings of IEEE ICDE'06: The International Conference on Data Engineering}, address = {Atlanta, Georgia}, month={April}, year=2006, url={http://www.cs.bu.edu/fac/best/res/papers/icde06.pdf}, abstract={ In this paper, we investigate a new approach to process queries in data stream applications. We show that reference locality characteristics of data streams could be exploited in the design of superior and flexible data stream query processing techniques. We identify two different causes of reference locality: popularity over long time scales and temporal correlations over shorter time scales. An elegant mathematical model is shown to precisely quantify the degree of those sources of locality. Furthermore, we analyze the impact of locality-awareness on achievable performance gains over traditional algorithms on applications such as MAX-subset approximate sliding window join and approximate count estimation. In a comprehensive experimental study, we compare several existing algorithms against our locality-aware algorithms over a number of real datasets. The results validate the usefulness and efficiency of our approach. } } @inproceedings{BestavrosBradleyKfouryMatta:icnp05, author={Azer Bestavros and Adam Bradley and Assaf Kfoury and Ibrahim Matta}, title= {{Typed Abstraction of Complex Network Compositions}}, Booktitle={{Proceedings of ICNP'05: The 13th IEEE International Conference on Network Protocols}}, address={Boston, MA}, month={November}, year=2005, url = "http://www.cs.bu.edu/fac/best/res/papers/icnp05.pdf", keywords={iBench, Protocol Verification, Internet and Web Protocol Composition, Security}, 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. } } @inproceedings{BestavrosBradleyKfouryOcean:basenets05, author = {Azer Bestavros and Adam Bradley and Assaf Kfoury and Michael Ocean}, title = {{SNBENCH: A Development and Run-Time Platform for Rapid Deployment of Sensor Network Applications}}, booktitle = {Proceedings of the IEEE International Workshop on Broadband Advanced Sensor Networks (Basenets 2005)}, address={Boston, MA}, month={October}, year = {2005}, url = "http://www.cs.bu.edu/fac/best/res/papers/basenets05.pdf", keywords={Real-Time, Sensor Network, Distributed Systems}, abstract = { We envision the emergence of general-purpose, well-provisioned sensor networks---which we call ``Sensoria''---that are embedded in (or overlayed atop) physical spaces, and whose use is shared amongst autonomous users of that space for independent and possibly conflicting missions. Our conception of a Sensorium stands in sharp contrast to the commonly adopted view of an embedded sensor network as a special-purpose infrastructure that serves a well-defined, fixed mission. The usefulness of a Sensorium will not be measured by how highly optimized its various protocols are, or by how efficiently its limited resources are being used, but rather by how flexible and extensible it is in supporting a wide range of applications. To that end, in this paper, we overview and present a first-generation implementation of snBench: a programming environment and associated run-time system that support the entire life-cycle of programming sensing-oriented applications. The components of snBench are analogous to those commonly found in traditional, stand-alone general-purpose computing environments. SNAFU (SensorNet Applications as Functional Units) is a high-level strongly-typed functional language that supports stateful, temporal, and persistent computation. SNAFU is compiled into an intermediate, abstract representation of the processing graph, called a STEP (Sensorium Task Execution Plan). The STEP graph is then linked to available Sensorium eXecution Environments (SXEs). A Sensorium Service Dispatcher (SSD) decomposes the STEP graph into a linked execution plan, loading STEP sub-graphs to appropriate individual SXEs and binding those loaded sub-graphs together with appropriate network protocols. The SSD may load many such programs onto a Sensorium simultaneously, taking advantage of programs' shared computation and dependencies to make more efficient use of sensing, computation, network, and storage resources. } } @inproceedings{ZhangBestavrosGuirguisMattaWest:vee05, author = {Yuting Zhang and Azer Bestavros and Mina Guirguis and Ibrahim Matta and Richard West}, title = {{Friendly Virtual Machines: Leveraging a Feedback-Control Model for Application Adaptation}}, booktitle = {Proceedings of the 2005 ACM/USENIX Conference on Virtual Execution Environments}, address={Chicago, Illinois}, month={June}, year = {2005}, url = "http://www.cs.bu.edu/fac/best/res/papers/vee05.pdf", 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.} } @inproceedings{GuirguisBestavrosMattaZhang:infocom05, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta and Yuting Zhang}, title = {{Reduction of Quality (RoQ) Attacks on Internet End-Systems}}, booktitle = {Proceedings of Infocom'05: The IEEE International Conference on Computer Communication}, address={Miami, Florida}, month={March}, year = {2005}, url = "http://www.cs.bu.edu/fac/best/res/papers/infocom05-roq.pdf", 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. } } @inproceedings{SharmaBestavrosMatta:infocom05, author = {Abhishek Sharma and Azer Bestavros and Ibrahim Matta}, title = {{dPAM: A Distributed Prefetching Protocol for Scalable Asynchronous Multicast in P2P Systems}}, month={March}, year = {2005}, booktitle = {Proceedings of Infocom'05: The IEEE International Conference on Computer Communication}, address={Miami, Florida}, url = "http://www.cs.bu.edu/fac/best/res/papers/infocom05-dpam.pdf", abstract = { We leverage the buffering capabilities of endsystems 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. } } @inproceedings{GuirguisBestavrosMatta:icenco04, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title = {{Routing Tradeoffs inside a d-dimensional Torus with applicability to CAN}}, booktitle = {Proceedings of the 1st International Computer Engineering Conference New Technologies for the Information Society (ICENCO'04)}, address={Cairo, Egypt}, url = "http://www.cs.bu.edu/fac/best/res/papers/icenco04.pdf", month={December}, year={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. } } @inproceedings{GuirguisBestavrosMatta:ccn04, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title = {{Bandwidth Stealing via Link-targeted RoQ Attacks}}, booktitle = {Proceedings of CCN'04: IASTED International Conference on Communication and Computer Networks}, month={November}, year = {2004}, address={MIT, Cambridge, MA}, url = "http://www.cs.bu.edu/fac/best/res/papers/ccn04.pdf", abstract = { We present a scheme that enables a set of flows to acquire an unfair share of bandwidth by mounting an adversarial distributed Reduction of Quality (RoQ) attack on flows competing for that bandwidth. This adversarial behavior stands in sharp contrast to other network exploits, e.g., Denial-of- Service (DoS) attacks, whose aim is to simply take down a resource, or severely limit access to a service. The extent to which the scheme we expose is successful in slowing down competing flows determines the amount of "stolen bandwidth." We present two schemes for the construction of a RoQ attack stream that would evade detection, and thus would challenge counter-DoS techniques. Our results show the vulnerability of the Internet to the distributed nature of RoQ attacks, which could be mounted through a relatively small number of zombie clients, motivating the need for the development of counter measures. We validate our findings through simple analysis, simulations and real Internet experiments.} } @inproceedings{GuirguisBestavrosMattaRigaDiamantZhang:iscc04, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta and Niky Riga and Gali Diamant and Yuting Zhang}, title = {{Providing Soft Bandwidth Guarantees Using Elastic TCP-based Tunnels}}, booktitle = {Proceedings of ISCC'04: IEEE Symposium on Computer and Communications}, year = {2004}, address={Alexandria, Egypt}, url = "http://www.cs.bu.edu/fac/best/res/papers/iscc04.pdf", 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 controltheoretic 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. } } @inproceedings{GuirguisBestavrosMatta:icnp04, author={Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title= {{Exploiting the Transients of Adaptation for RoQ Attacks on Internet Resources}}, booktitle={{Proceedings of ICNP'04: The 12th IEEE International Conference on Network Protocols}}, address={Berlin, Germany}, keywords={Protocol Verification, Internet and Web Protocol Composition}, month={October}, year=2004, url = "http://www.cs.bu.edu/fac/best/res/papers/icnp04-roq.pdf", abstract={ 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.} } @inproceedings{BradleyBestavrosKfoury:icnp04, author={Adam Bradley and Azer Bestavros and Assaf Kfoury}, title= {{A Typed Model for Encoding-Based Protocol Interoperability}}, booktitle={{Proceedings of ICNP'04: The 12th IEEE International Conference on Network Protocols}}, address={Berlin, Germany}, keywords={Protocol Verification, Internet and Web Protocol Composition}, month={October}, year=2004, url = "http://www.cs.bu.edu/fac/best/res/papers/icnp04-model.pdf", abstract={ Documentation of the HTTP protocol includes precise descriptions of the syntax of the protocol, but lacks similarly precise specification of the semantics of messages and message bodies. Semantics are stated in English prose; while this makes the document more intuitively accessible, it makes any sort of formal claims of correctness or interoperability difficult to derive from the specification itself. We propose "layered types", a formal description of the interpretive semantics of HTTP message bodies based upon the stacked type syntax. This model allows us to formally declare semantics for content-related HTTP headers and offers a precise way of characterizing interoperability between current and future protocol revisions and extensions. } } @inproceedings{SharmaBestavrosMatta:wcw04, author={Abhishek Sharma and Azer Bestavros and Ibrahim Matta}, title= {{Performance Evaluation of Distributed Prefetching for Asynchronous Multicast in P2P Networks}}, booktitle={{Proceedings of WCW'04: The 9th International Workshop on Web Caching And Content Distribution}}, address={Beijing, China}, keywords={P2P Networks, Caching, Prefetching, real-Time, Streaming Media Delivery}, month={October}, year=2004, url = "http://www.cs.bu.edu/fac/best/res/papers/wcw04.pdf", 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 eval- uate through extensive simulations the performance of the distributed prefetching protocol, dPAM, 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 signifi- cantly, compared to the previously proposed cache-and-relay strategy, even when the group of clients downloading a stream changes quite fre- quently due to client departures.} } @inproceedings{GuirguisBestavrosMatta:sigcomm04, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title = {{Adaptation = Vulnerability: Under RoQ Attacks}}, booktitle = {ACM SIGCOMM 2004 (Poster Session)}, address={Portland, Oregon}, month={August}, year = {2004}, url = {http://www.cs.bu.edu/fac/best/res/papers/sigcomm04-poster.pdf}, abstract = { } } @inproceedings{BradleyBestavrosKfoury:icnp03, author={Adam Bradley and Azer Bestavros and Assaf Kfoury}, title= {{Systematic Verification of Safety Properties of Arbitrary Network Protocol Compositions Using CHAIN}}, booktitle={{Proceedings of ICNP'03: The 11th IEEE International Conference on Network Protocols}}, address={Atlanta, GA}, keywords={Protocol Verification, Internet and Web Protocol Composition}, month={November}, year=2003, url = "http://www.cs.bu.edu/fac/best/res/papers/icnp03.pdf", abstract={} } @inproceedings{GuirguisBestavrosMatta:icnp03, author = {Mina Guirguis and Azer Bestavros and Ibrahim Matta}, title = {{XQM: eXogenous-loss aware Queue Management}}, booktitle = {IEEE ICNP 2003 (Poster Session)}, address={Atlanta, Georgia}, month={November}, year = {2003}, url = {http://www.cs.bu.edu/fac/best/res/papers/icnp03-poster.pdf}, abstract = { } } @inproceedings{GuptaBestavrosMatta:rtas04, author = {Kanishka Gupta and Azer Bestavros and Ibrahim Matta}, title = {{Context-aware Real-time Scheduling}}, booktitle = {RTAS 2004: IEEE Real-Time and Embedded Technology and Applications Symposium (WIP Session)}, address={Toronto, Canada}, month={May}, year = {2004}, url = {http://www.cs.bu.edu/fac/best/res/papers/rtas04-wip.pdf}, abstract = { } } @inproceedings{JinBestavros:mascots03, author={Shudong Jin and Azer Bestavros}, title={{Small-world Characteristics of Internet Topologies and Multicast Scaling}}, keywords={Internet Characterization, Internet Topology, Multicast}, url={http://www.cs.bu.edu/fac/best/res/papers/mascots03.pdf}, booktitle={{Proceedings of Mascots'2003: The IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems}}, year=2003, month={October}, address={Orlando, FL}, abstract={} } @inproceedings{BestavrosJin:icdcs03, author={Azer Bestavros and Shudong Jin}, title={{OSMOSIS: Scalable Delivery of Real-Time Streaming Media in Ad-Hoc Overlay Networks}}, booktitle = {Proceedings of IEEE ICDCS'03 Workshop on Data Distribution in Real-Time Systems}, address={Providence, RI}, month={May}, year=2003, url={http://www.cs.bu.edu/fac/best/res/papers/icdcs03.pdf}, abstract={Ad-hoc overlay networks are increasingly used for sharing static bulk content but their promise for scaling the delivery of on-demand, real-time content is yet to be tapped. In this paper, we show that overlay networks could be used efficiently to distribute popular real-time streaming media on-demand to a large number of clients. We propose and evaluate OSMOSIS a cache-and-relay end-system multicast approach, whereby a client joining a multicast session caches the stream, and if needed, relays that stream to neighboring clients which may join the multicast session at some later time. OSMOSIS is fully distributed, scalable, and efficient in terms of network link costs. We present analytical and empirical results of our evaluation of OSMOSIS. Our analysis establishes OSMOSIS scalability characteristics under a variety of assumptions. Our simulations are over large, synthetic random networks, power-law degree networks, and small-world networks (all of which could well be representative of ad-hoc overlay topologies, as well as over large real router-level Internet maps.} } @inproceedings{HarfoushBestavrosByers:infocom03, author={Khaled Harfoush and Azer Bestavros and John Byers}, title={{Measuring Bottleneck Bandwidth of Targeted Path Segments}}, keywords={Beacon, Internet Measurement}, booktitle = {Proceedings of Infocom'03: The IEEE International Conference on Computer Communication}, address={San Fransisco, CA}, month={May}, year=2003, url={http://www.cs.bu.edu/fac/best/res/papers/infocom03.pdf}, abstract={} } @inproceedings{BradleyBestavros:gi02, author={Adam Bradley and Azer Bestavros}, title={{Basis Token Consistency: Supporting Strong Web Cache Consistency}}, month={November}, year=2002, booktitle={Proceedings of the 2002 Globecom Global Internet Symposium}, address={Taipei, Taiwan}, url={http://www.cs.bu.edu/fac/best/res/papers/gi02.pdf}, keywords={Internet, Web Caching, Consistency}, abstract={}, } @inproceedings{VelosoAlmeidaMeiraBestavrosJin:imw02, author={Eveline Veloso and Virgilio Almeida and Wagner Meira and Azer Bestavros and Shudong Jin}, title={{A Hierarchical Characterization of a Live Streaming Media Workload}}, keywords={Web Characterization, Internet Measurement, Networking}, month={November}, year=2002, address={Marseille, France}, url = {http://www.cs.bu.edu/faculty/best/res/papers/imw02.pdf}, booktitle={Proceedings of the ACM/Usenix Internet Measurment Workshop (IMW'02)}, abstract={We present what we believe to be the first thorough characterization of {\em live} streaming media content delivered over the Internet. Our characterization of over 3.5 million requests spanning a 28-day period is done at three increasingly granular levels, corresponding to clients, sessions, and transfers. Our findings support two important conclusions. First, we show that the nature of interactions between users and objects is fundamentally different for live versus stored objects. Access to stored objects is {\em user driven}, whereas access to live objects is {\em object driven}. This reversal of active/passive roles of users and objects leads to interesting dualities. For instance, our analysis underscores a Zipf-like profile for user interest in a given object, which is in contrast to the classic Zipf-like popularity of objects for a given user. Also, our analysis reveals that transfer lengths are highly variable and that this variability is due to the stickiness of clients to a particular live object, as opposed to structural (size) properties of objects. Second, by contrasting two live streaming workloads from two radically different applications, we conjecture that some characteristics of live media access workloads are likely to be highly dependent on the nature of the live content being accessed. In our study, this dependence is clear from the strong temporal correlations observed in the traces, which we attribute to the synchronizing impact of live content on access characteristics. Based on our analyses, we present a model for live media workload generation that incorporates many of our findings, and which we implement in \sc{Gismo} \cite{JinBestavros:per01}.} } @inproceedings{JinBestavros:ngc02, author={Shudong Jin and Azer Bestavros}, title={{Cache and Relay Streaming Media Delivery for Asynchronous Clients}}, booktitle={{Proceedings of the 4th International Workshop on Networked Group Communication}}, year=2002, month={October}, address={Boston, MA}, url = {http://www.cs.bu.edu/faculty/best/res/papers/ngc02.pdf}, keywords={Web Caching, Internet Protocols, End-system Multicast, Scalable Content Distribution}, abstract={We consider the problem of efficient delivery of popular streaming media to a large number of asynchronous clients. We propose a buffer-and-relay end system multicast approach, whereby a client joining a multicast session buffers the stream (either partially or entirely) and, if needed, relays that stream to neighboring clients which may join the multicast session at some later time. This buffer-and-relay approach is fully distributed, scalable, and efficient in terms of network link cost. In this paper we evaluate this approach under assumptions of (1) limited client bandwidth, and (2) limited client buffering capacity. When client bandwidth is limited, we show that while finding an optimal solution is NP-hard, a simple greedy algorithm performs surprisingly well in that it incurs network link costs that are very close to a theoretically-derived lower bound. When client buffering capacity is limited, we show that our greedy algorithm significantly reduces network link costs. We have evaluated our buffer-and-relay approach using simulation over large, synthetic random networks, power-law degree networks, and small-world networks, as well as over large real router-level Internet maps.} } @inproceedings{BradleyBestavrosKfoury:wcw02, author={Adam Bradley and Azer Bestavros and Assaf Kfoury}, title={{Safe Composition of Web Communication Protocols for Extensible Edge Services}}, booktitle={{Proceedings of the 7th International Web Caching and Content Delivery Workshop}}, month={August}, year=2002, address={Boulder, CO}, url = {http://www.cs.bu.edu/faculty/best/res/papers/wcw02.pdf}, keywords={Web Caching, Internet Protocols, Formal verification, HTTP, Interoperability, Model checking, Protocol composition}, abstract={As new multi-party edge services are deployed on the Internet, application-layer protocols with complex communication models and event dependencies are increasingly being specified and adopted. To ensure that such protocols (and compositions thereof with existing protocols) do not result in undesirable behaviors (e.g., livelocks) there needs to be a methodology for the automated checking of the ``safety'' of these protocols. In this paper, we present ingredients of such a methodology. Specifically, we show how SPIN, a tool from the formal systems verification community, can be used to quickly identify problematic behaviors of application-layer protocols with non-trivial communication models---such as HTTP with the addition of the ``100 Continue'' mechanism. As a case study, we examine several versions of the specification for the Continue mechanism; our experiments mechanically uncovered multi-version interoperability problems, including some which motivated revisions of HTTP/1.1 and some which persist even with the current version of the protocol. One such problem resembles a classic degradation-of-service attack, but can arise between well-meaning peers. We also discuss how the methods we employ can be used to make explicit the requirements for hardening a protocol's implementation against potentially malicious peers, and for verifying an implementation's interoperability with the full range of allowable peer behaviors.} } @inproceedings{BradleyBestavros:wc302, author={Adam Bradley and Azer Bestavros}, title={{Basis Token Consistency: Extending and Evaluating a Novel Web Consistency Algorithm}}, booktitle = {{Proceedings of WC3: The International Workshop on Caching, Coherence, and Consistency}}, year=2002, url={http://www.cs.bu.edu/fac/best/res/papers/wc302.pdf}, keywords={Internet, Web Caching, Consistency}, abstract={}, month={June}, address={New York} } @inproceedings{JinBestavros:sigmetrics02, author={Shudong Jin and Azer Bestavros}, title={{Scalability of Multicast Delivery for Non-sequential Streaming Access}}, booktitle = {{Proceedings of Sigmetrics'2002: The ACM International Conference on Measurement and Modeling of Computer Systems}}, year=2002, url={http://www.cs.bu.edu/fac/best/res/papers/sigmetrics02.pdf}, keywords={Internet, Characterization, Streaming Media, Multicast, Web, Real-Rime, Networking}, abstract={Multicast is considered a panacea for scalable streaming media delivery over the Internet. To enable asynchronous service over a multicast infrastructure, two categories of techniques have been proposed: stream merging and periodic broadcasting. The scalability of these techniques stems from the fact that for sequential streaming access, the required server bandwidth grows {\em logarithmically} with request arrival rates for stream merging techniques, and {\em logarithmically} with the inverse of start-up delay for periodic multicasting techniques. Recent studies raise doubts as to the appropriateness of the sequential access model (in which access to a stream proceeds uninterrupted from beginning to end). A non-sequential access model (allowing access to start at random points in the stream) is more accurate as it allows the modeling of partial access and client inter-activity. In this paper, we analytically and experimentally (re-)evaluate the scalability of multicast delivery under a non-sequential access model. We show that under such a realistic model, the required server bandwidth for any protocol providing immediate service grows at least as fast as the {\em square root} of the request arrival rate, and that the required server bandwidth for any protocol providing delayed service grows {\em linearly} with the inverse of the start-up delay. We also investigate the impact of limited client bandwidth on scalability. We present practical protocols, which provide immediate service to non-sequential requests (subject to limited client bandwidth), and which are near-optimal in that the required server bandwidth is very close to its lower bound.} } @inproceedings{JinBestavrosIyengar:icdcs02, author={Shudong Jin and Azer Bestavros and Arun Iyengar}, title={{Accelerating Internet Streaming Media Delivery using Network-Aware Partial Caching}}, booktitle = {Proceedings of ICDCS'2002: The IEEE International Conference on Distributed Computing Systems}, year=2002, url={http://www.cs.bu.edu/fac/best/res/papers/icdcs02.pdf}, keywords={Internet, Characterization, Streaming Media, Multicast, Web,Real-Rime}, abstract={Internet streaming applications are adversly affected by network conditions such as high packet loss rates and long delays. This paper aims at mitigating such effects by leveraging the availability of client-side caching proxies. We present a novel caching architecture (and associated cache management algorithms) that turn edge caches into accelerators of streaming media delivery. A salient feature of our caching algorithms is that they allow partial caching of streaming media objects and joint delivery of content from caches and origin servers. The caching algorithms we propose are both network-aware and stream-aware; they take into account the popularity of streaming media objects, their bit-rate requirements, and the available bandwidth between clients and servers. Using realistic models of Internet bandwidth (derived from proxy cache logs and measured over real Internet paths), we have conducted extensive simulations to evaluate the performance of various caching management alternatives. Our experiments demonstrate that network-aware caching algorithms can significantly reduce service delay and improve overall stream quality. Also, our experiments show that partial caching is particularly effective when bandwidth variability is not very high.} } @inproceedings{HarfoushBestavrosByers:pam02, author={Khaled Harfoush and Azer Bestavros and John Byers}, title={{PeriScope: An Active Measurement API}}, keywords={Beacon, Internet Measurement}, booktitle = {Proceedings of PAM'2002: The IEEE Passive and Active Measurement Workshop}, month={March}, year=2002, url={http://www.cs.bu.edu/fac/best/res/papers/pam02.pdf}, abstract={} } @inproceedings{BestavrosByersHarfoush:infocom02, author={Azer Bestavros and John Byers and Khaled Harfoush}, title={{Inference and Labeling of Metric-Induced Network Topologies}}, keywords={Beacon, Internet Measurement}, booktitle = {Proceedings of Infocom'02: The IEEE International Conference on Computer Communication}, month={June}, address={New York, NY}, year=2002, url={http://www.cs.bu.edu/fac/best/res/papers/infocom02.pdf}, abstract={} } @inproceedings{BestavrosMehrotra:wwc01, author={Azer Bestavros and Sumit Mehrotra}, title= {{DNS-based Internet Client Clustering and Characterization}}, booktitle={{Proceedings of WWC'01: The 4th IEEE Workshop on Workload Characterization}}, address={Austin, TX}, keywords={Internet, Characterization, Web}, month={December}, year=2001, url = "http://www.cs.bu.edu/fac/best/res/papers/wwc01.pdf", abstract={This paper proposes a novel protocol which uses the Internet Domain Name System (DNS) to partition Web clients into disjoint sets, each of which is associated with a single DNS server. We define an L-DNS cluster to be a grouping of Web Clients that use the same Local DNS server to resolve Internet host names. We identify such clusters in real-time using data obtained from a Web Server in conjunction with that server's Authoritative DNS---both instrumented with an implementation of our clustering algorithm. Using these clusters, we perform measurements from four distinct Internet locations. Our results show that L-DNS clustering enables a better estimation of proximity of a Web Client to a Web Server than previously proposed techniques. Thus, in a Content Distribution Network, a DNS-based scheme that redirects a request from a web client to one of many servers based on the client's name server coordinates (e.g., hops/latency/loss-rates between the client and servers) would perform better with our algorithm.} } @inproceedings{BarfordBestavrosByesCrovella:imw01, author={Paul Barford and Azer Bestavros and John Byers and Mark Crovella}, title={On the Marginal Utility of Network Topology Measurements}, booktitle={{Proceedings of the 2001 Sigcomm Internet Measurement Workshop}}, month={{October}}, year={2001}, url={http://www.cs.bu.edu/faculty/best/res/papers/imw01.pdf}, abstract={ The cost and complexity of deploying measurement infrastructure in the Internet for the purpose of analyzing its structure and behavior is considerable. Basic questions about the {\em utility} of increasing the number of measurements and measurement sites have not yet been addressed which has led to a ``more is better'' approach to wide-area measurement studies. In this paper, we step toward a more quantifiable understanding of the marginal utility of performing wide-area measurements in the context of Internet topology discovery. We characterize the observable topology in terms of nodes, links, node degree distribution, and distribution of end-to-end flows using statistical and information-theoretic techniques. We classify nodes discovered on the routes between a set of 8 sources and 1277 destinations to differentiate nodes which make up the so called ``backbone'' from those which border the backbone and those on links between the border nodes and destination nodes. This process includes reducing nodes that advertise multiple interfaces to single IP addresses. We show that the utility of adding sources beyond the second source quickly diminishes from the perspective of interface, node, link and node degree discovery. We also show that the utility of adding destinations is constant for interfaces, nodes, links and node degree indicating that it is more important to add destinations than sources.} } @inproceedings{HarfoushBestavrosByers:icnp00, author={Khaled Harfoush and Azer Bestavros and John Byers}, title={{Robust Identification of Shared Losses Using End-to-End Unicast Probes}}, booktitle={{Proceedings of ICNP'00: The 6th IEEE International Conference on Network Protocols}}, address={Osaka, Japan}, keywords={Beacon, Internet Measurement}, month={October}, year=2000, url={http://www.cs.bu.edu/fac/best/res/papers/icnp00.ps}, abstract={ Current Internet transport protocols make end-to-end measurements and maintain per-connection state to regulate the use of shared network resources. When two or more such connections share a common endpoint, there is an opportunity to correlate the end-to-end measurements made by these protocols to better diagnose and control the use of shared resources. We develop packet probing techniques to determine whether a pair of connections experience shared congestion. Correct, efficient diagnoses could enable new techniques for aggregate congestion control, QoS admission control, connection scheduling and mirror site selection. Our extensive simulation results demonstrate that the conditional (Bayesian) probing approach we employ provides superior accuracy, converges faster, and tolerates a wider range of network conditions than recently proposed memoryless (Markovian) probing approaches for addressing this opportunity.} } @inproceedings{JinBestavros:mascots00, author={Shudong Jin and Azer Bestavros}, title={{Sources and Characteristics of Web Temporal Locality}}, keywords={Internet Characterization, Web locality of reference}, url={http://www.cs.bu.edu/fac/best/res/papers/mascots00.ps}, booktitle={{Proceedings of Mascots'2000: The IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems}}, year=2000, month={August}, address={San Fransisco, CA}, abstract={Temporal locality of reference in Web request streams emerges from two distinct phenomena: the {\em long-term popularity} of Web documents and the {\em short-term temporal correlations} of references. In this paper we show that the commonly-used distribution of inter-request times is predominantly determined by the power law governing the long-term popularity of documents. This inherent relationship tends to disguise the existence of short-term temporal correlations. We propose a new and robust metric that enables accurate characterization of that aspect of temporal locality. Using this metric, we characterize the locality of reference in a number of representative proxy cache traces. Our findings show that there are measurable differences between the degrees (and sources) of temporal locality across these traces.} } @inproceedings{JinBestavros:sigmetrics00, author={Shudong Jin and Azer Bestavros}, title={{Temporal Locality in Web Request Streams: Sources, Characteristics, and Caching Implications (Extended Abstract)}}, keywords={Internet Characterization, Web locality of reference}, url={http://www.cs.bu.edu/fac/best/res/papers/sigmetrics00.ps}, booktitle={{Proceedings of Sigmetrics'2000: The ACM International Conference on Measurement and Modeling of Computer Systems}}, year=2000, month={June}, address={Santa Clara, CA}, abstract={} } @inproceedings{JinBestavros:wcw00, author={Shudong Jin and Azer Bestavros}, title={{GreedyDual* Web Caching Algorithm: Exploiting the Two Sources of Temporal Locality in Web Request Streams}}, keywords={Network caching, Web Proxy Caching Algorithms, Web locality of reference}, url={http://www.cs.bu.edu/fac/best/res/papers/wcw00.ps}, booktitle={{Proceedings of the 5th International Web Caching and Content Delivery Workshop}}, year=2000, month={May}, address={Lisbon, Portugal}, abstract={The relative importance of long-term popularity and short-term temporal correlation of references for Web cache replacement policies has not been studied thoroughly. This is partially due to the lack of accurate characterization of temporal locality that enables the identification of the relative strengths of these two sources of temporal locality in a reference stream. In [JB99], we have proposed such a metric and have shown that Web reference streams differ significantly in the the prevelance of these two sources of temporal locality. These findings underscore the importance of a Web caching strategy that can adapt in a dynamic fashion to the prevelance of these two sources of temporal locality. In this paper, we propose a novel cache replacement algorithm, GreedyDual*, which is a generalization of GreedyDual-Size. GreedyDual* uses the metrics proposed in [JB99] to adjust the relative worth of long-term popularity versus short-term temporal correlation of references. Our trace-driven simulation experiments show the superior performance of GreedyDual* when compared to other Web cache replacement policies proposed in the literature.} } @inproceedings{YoonBestavrosMatta:icc00, author={Jaehee Yoon and Azer Bestavros and Ibrahim Matta}, title={{Adaptive Reliable Multicast}}, keywords={Network protocols, Reliable Multicast, Internet}, url={http://www.cs.bu.edu/fac/best/res/papers/icc00.ps}, booktitle={{Proceedings of ICC'2000: The IEEE International Conference on Communications}}, year=2000, month={June}, address={New Orleans}, abstract={We present a new reliable multicast protocol, called ARM (for Adaptive Reliable Multicast). Our protocol integrates ARQ and FEC techniques. The objectives of ARM are (1) reduce the message overhead due to NACK requests, (2) reduce the amount of data transmission, and (3) reduce the time it takes for all receivers to receive the data intact (without loss). During data transmission, the sender periodically informs the receivers of the number of packets that are yet to be transmitted. Based on this information, each receiver predicts whether this amount is enough to recover its losses. Only if it is not enough, that the receiver requests the sender to encode additional redundant packets. Using ns simulations, we show the superiority of our hybrid ARQ-FEC protocol over the well-known Scalable Reliable Multicast (SRM) protocol.} } @inproceedings{YoonBestavrosMatta:rtas00, author={Jaehee Yoon and Azer Bestavros and Ibrahim Matta}, title={{SomeCast: A Paradigm for Real-Time Adaptive Reliable Multicast}}, keywords={Network protocols, Real-Time QoS on the Internet}, url={http://www.cs.bu.edu/fac/best/res/papers/rtas00.ps}, booktitle={{Proceedings of RTAS'2000: The IEEE Real-Time Technology and Applications Symposium}}, year=2000, month={May}, address={Washington, DC}, abstract={SomeCast is a novel paradigm for the reliable multicast of real-time data to a large set of receivers. SomeCast is receiver-initiated and thus scalable in the number of receivers, the diverse characteristics of paths between senders and receivers, and the dynamic conditions of such paths. SomeCast enables receivers to dynamically adjust the rate at which they receive multicast information to enable the satisfaction of their QoS constraints. This is done by enabling a receiver to join SOME number of concurrent multiCAST sessions, whereby each session delivers a portion of an encoding of the real-time data. By adjusting the number of such sessions dynamically, client-specific QoS constraints are met independently. The SomeCast paradigm can be thought of as a generalization of the AnyCast and ManyCast paradigms, which have been proposed in the literature to address issues of scalability of UniCast and MultiCast environments, respectively. In this paper we overview the SomeCast paradigm, describe an instance of a SomeCast protocol, and present simulation results that quantify the significant advantages gained from adopting such a protocol.} } @inproceedings{JinBestavros:icdcs00, author={Shudong Jin and Azer Bestavros}, title={{Popularity-Aware GreedyDual-Size Web Proxy Caching Algorithms}}, url={http://www.cs.bu.edu/fac/best/res/papers/icdcs00.ps}, booktitle={{Proceedings of ICDCS'2000: The IEEE International Conference on Distributed Computing Systems}}, keywords={Internet, Web, Network caching}, year=2000, month={May}, address={Taiwan}, abstract={Web caching aims at reducing network traffic, server load, and user-perceived retrieval delays by replicating popular content on proxy caches that are strategically placed within the network. While key to effective cache utilization, popularity information (e.g. relative access frequencies of objects requested through a proxy) is seldom incorporated directly in cache replacement algorithms. Rather, other properties of the request stream (e.g. temporal locality and content size), which are easier to capture in an on-line fashion, are used to indirectly infer popularity information, and hence drive cache replacement policies. Recent studies suggest that the correlation between these secondary properties and popularity is weakening due in part to the prevalence of efficient client and proxy caches. This trend points to the need for proxy cache replacement algorithms that directly capture popularity information. In this paper, we (1) present an on-line algorithm that effectively captures and maintains an accurate popularity profile of Web objects requested through a caching proxy, (2) propose a novel cache replacement policy that uses such information to generalize the well-known GreedyDual-Size algorithm, and (3) show the superiority of our proposed algorithm by comparing it to a host of recently-proposed and widely-used algorithms using extensive trace-driven simulations and a variety of performance metrics.} } @inproceedings{AversaBestavros:ipccc00, author={Luis Aversa and Azer Bestavros}, title={{Load Balancing a Cluster of Web Servers Using Distributed Packet Rewriting}}, url={http://www.cs.bu.edu/fac/best/res/papers/ipccc00.pdf}, booktitle={{Proceedings of IPCCC'2000: The IEEE International Performance, Computing, and Communication Conference}}, year=2000, month={February}, address={Phoenix, AZ}, abstract={We present and evaluate an implementation of a prototype scalable web server consisting of a load-balanced cluster of hosts that collectively accept and service TCP connections. The host IP addresses are advertised using Round Robin DNS (RR-DNS) technique, allowing any host to receive requests from any client. Once a client attempts to establish a TCP connection with one of the hosts, a decision is made as to whether or not the connection should be redirected to a different host---namely, the host with the lowest number of established connections. We use the low-overhead Distributed Packet Rewriting (DPR) technique [1] to redirect TCP connections. In our prototype, each host keeps information about the remaining hosts in the system. Load information is maintained using periodic multicast amongst the cluster hosts. Performance measurements suggest that our prototype outperforms both pure RR-DNS and the stateless DPR solutions. } } @inproceedings{AtlasBestavros:rtss99, author={Alia Atlas and Azer Bestavros}, title={{Design and Implementation of Statistical Rate Monotonic Scheduling in KURT Linux}}, url={http://www.cs.bu.edu/fac/best/res/papers/rtss99.ps}, booktitle={{Proceedings of RTSS'99: The 19th IEEE Real-Time Systems Symposium}}, year=1999, month={December}, address={Phoenix, AZ}, abstract={We present the design and implementation of Statistical Rate Monotonic Scheduling (SRMS) on the KURT Linux Operating System. We overview the technical issues we had to address to integrate SRMS into KURT Linux and present the API we have developed for scheduling periodic real-time tasks using SRMS. } } @inproceedings{AtlasBestavros:ic3n99, author={Alia Atlas and Azer Bestavros}, title={{Multiplexing VBR Traffic Flows with Guaranteed Application-level QoS Using Statistical Rate Monotonic Scheduling}}, url={http://www.cs.bu.edu/fac/best/res/papers/ic3n99-a.ps}, booktitle={{Proceedings of IC3N'99: The 8th IEEE International Conference on Computer Communications and Networks}}, year=1999, month={October}, address={Boston, MA}, abstract={The data units transmitted by an application may vary in size while being constant in rate, which results in a variable bit rate (VBR) data flow. That data flow requires QoS guarantees. Statistical multiplexing is inadequate, because no guarantees can be made and no firewall property exists between different data flows. In this paper, we present a novel resource management paradigm for the maintenance of application-level QoS for VBR flows. Our paradigm is based on Statistical Rate Monotonic Scheduling (SRMS), in which (1) each application generates its variable-size data units at a fixed rate, (2) the partial delivery of data units is of no value to the application, and (3) the QoS guarantee extended to the application is the probability that an arbitrary data unit will be successfully transmitted through the network to/from the application.} } @inproceedings{BasuNarayananKeLittleBestavros:ic3n99, author={P. Basu and A. Narayanan and W. Ke and T.D.C. Little and A. Bestavros}, title={{Optimal Scheduling of Secondary Content for Aggregation in Video-on-Demand Systems}}, url={http://www.cs.bu.edu/fac/best/res/papers/ic3n99-b.ps}, booktitle={{Proceedings of IC3N'99: The 8th IEEE International Conference on Computer Communications and Networks}}, year=1999, month={October}, address={Boston, MA}, abstract={Dynamic service aggregation techniques can exploit skewed access popularity patterns to reduce the costs of building interactive VoD systems. These schemes seek to cluster and merge users into single streams by bridging the temporal skew between them, thus improving server and network utilization. Rate adaptation and secondary content insertion are two such schemes. In this paper, we present and evaluate an optimal scheduling algorithm for inserting secondary content in this scenario. The algorithm runs in polynomial time, and is optimal with respect to the total bandwidth usage over the merging interval. We present constraints on content insertion which make the overall QoS of the delivered stream acceptable, and show how our algorithm can satisfy these constraints. We report simulation results which quantify the excellent gains due to content insertion. We discuss dynamic scenarios with user arrivals and interactions, and show that content insertion reduces the channel bandwidth requirement to almost half. We also discuss differentiated service techniques, such as N-VoD and premium no-advertisement service, and show how our algorithm can support these as well.} } @inproceedings{BestavrosKim:spie99, author={Azer Bestavros and Gitae Kim}, title={{Preserving Bandwidth Using A Lazy Packet Discard Policy in ATM Networks}}, url={http://www.cs.bu.edu/fac/best/res/papers/spie99.ps}, booktitle={{Proceedings of SPIE'99 Performance and Control of Network Systems III}}, year=1999, month={September}, address={Boston, MA}, abstract={A number of recent studies have pointed out that TCP's performance over ATM networks tends to suffer, especially under congestion and switch buffer limitations. Switch-level enhancements and link-level flow control have been proposed to improve TCP's performance in ATM networks. Selective Cell Discard (SCD) and Early Packet Discard (EPD) ensure that partial packets are discarded from the network ``as early as possible'', thus reducing wasted bandwidth. While such techniques improve the achievable throughput, their effectiveness tends to degrade in multi-hop networks. In this paper, we introduce Lazy Packet Discard (LPD), an AAL-level enhancement that improves effective throughput, reduces response time, and minimizes wasted bandwidth for TCP/IP over ATM. In contrast to the SCD and EPD policies, LPD delays as much as possible the removal from the network of cells belonging to a partially communicated packet. LPD preserves network bandwidth by keeping such cells alive and by ensuring that additional cells, obtained through Reed-Solomon block coding at the sender's AAL, are eventually transmitted to salvage the packet in question. We outline the implementation of LPD and show the performance advantage of TCP/LPD, compared to plain TCP and TCP/EPD through analysis and simulations.} } @inproceedings{AtlasBestavros:rtss98, author={Alia Atlas and Azer Bestavros}, title={{Statistical Rate Monotonic Scheduling}}, booktitle={{Proceedings of RTSS'98: The 18th IEEE Real-Time Systems Symposium}}, address={Madrid, Spain}, month={December}, year=1998, url={http://www.cs.bu.edu/fac/best/res/papers/rtss98.ps}, abstract={Statistical Rate Monotonic Scheduling (SRMS) is a generalization of the classical RMS results of Liu and Layland \cite{ll:sched} for periodic tasks with highly variable execution times and statistical QoS requirements. The main tenet of SRMS is that the variability in task resource requirements could be smoothed through aggregation to yield guaranteed QoS. This aggregation is done over time for a given task and across multiple tasks for a given period of time. Similar to RMS, SRMS has two components: a feasibility test and a scheduling algorithm. SRMS feasibility test ensures that it is possible for a given periodic task set to share a given resource without violating any of the statistical QoS constraints imposed on each task in the set. The SRMS scheduling algorithm consists of two parts: a job admission controller and a scheduler. The SRMS scheduler is a simple, preemptive, fixed-priority scheduler. The SRMS job admission controller manages the QoS delivered to the various tasks through admit/reject and priority assignment decisions. In particular, it ensures the important property of task isolation, whereby tasks do not infringe on each other.} } @inproceedings{BestavrosCrovellaLiuMartin:icnp98, author={Azer Bestavros and Mark Crovella and Jun Liu and David Martin}, title={{Packet Rewriting and its Application to Scalable Web Server Architectures}}, booktitle={{Proceedings of ICNP'98: The 6th IEEE International Conference on Network Protocols}}, address={Austin, TX}, pages={}, month={October}, year=1998, url={http://www.cs.bu.edu/fac/best/res/papers/icnp98.ps}, abstract={To construct high performance Web servers, system builders are increasingly turning to distributed designs. An important challenge that arises in such designs is the need to direct incoming connections to individual hosts. Previous methods for connection routing (Layer 4 Switching) have employed a centralized node to handle all incoming requests. In contrast, we propose a distributed approach, called Distributed Packet Rewriting (DPR), in which all hosts of the distributed system participate in connection routing. DPR promises better scalability and fault-tolerance than the currrent practice of using centralized, special-purpose connection routers. In this paper, we describe our implementation of four variants of DPR and compare their performance. We show that DPR provides performance comparable to centralized alternatives, measured in terms of throughput and delay. Also, we show that DPR enhances the scalability of Web server clusters by eliminating the performance bottleneck exhibited when centralized connection routing techniques are utilized.} } @inproceedings{BestavrosMatta:infocom98, author={Azer Bestavros and Ibrahim Matta}, title={{A Load Profiling Approach to Routing Guaranteed Bandwidth Flows}}, booktitle = {Proceedings of Infocom'98: The IEEE International Conference on Computer Communication}, month={April}, address={San Fransisco, CA}, year=1998, url={http://www.cs.bu.edu/fac/best/res/papers/infocom98.ps}, abstract={To support the stringent Quality of Service (QoS) requirements of real-time ({\em e.g.} audio/video) applications in integrated services networks, several routing algorithms that allow for the reservation of the needed bandwidth over a Virtual Circuit (VC) established on one of several candidate routes have been proposed. Traditionally, such routing is done using the least-loaded concept, and thus results in balancing the load across the set of candidate routes. In a recent study, we have established the inadequacy of this load balancing practice and proposed the use of {\em load profiling} as an alternative. Load profiling techniques allow the distribution of ``available'' bandwidth across a set of candidate routes to match the characteristics of incoming VC QoS requests. In this paper we thoroughly characterize the performance of VC routing using load profiling and contrast it to routing using load balancing and load packing. We do so both analytically and via extensive simulations of multi-class traffic routing in Virtual Path (VP) based networks. Our findings confirm that for routing guaranteed bandwidth flows in VP networks, load balancing is not desirable as it results in VP bandwidth fragmentation, which adversely affects the likelihood of accepting new VC requests. This fragmentation is more pronounced when the granularity of VC requests is large. Typically, this occurs when a common VC is established to carry the {\em aggregate} traffic flow of many high-bandwidth real-time sources. For VP-based networks, our simulation results show that our load-profiling VC routing scheme performs better or as well as the traditional load-balancing VC routing in terms of revenue under both skewed and uniform workloads. Furthermore, load-profiling routing improves routing fairness by proactively increasing the chances of admitting high-bandwidth connections.} } @inproceedings{DasBestavrosCaglayanGonsalves:padd98, author={Subrata Das and Azer Bestavros and Alper Caglayan and Paul Gonsalves}, title={{Increasing agent autonomy by learning from events}}, booktitle = {Proceedings of the Second International Conference on The Practical Applications of Knowledge Discovery and Data Mining}, month={March}, pages={241-260}, address={London, UK}, year=1998, } @inproceedings{BestavrosMatta:icnp97, author={Azer Bestavros and Ibrahim Matta}, title={{Load Profiling for Efficient Route Selection in Multi-Class Networks}}, booktitle = {Proceedings of IEEE ICNP'97: The International Conference on Network Protocols}, month={October}, address={Atlanta, GA}, year=1997, url={http://www.cs.bu.edu/fac/best/res/papers/icnp97.ps}, abstract={High-speed networks, such as ATM networks, are expected to support real-time Quality of Service (QoS) guarantees required by many applications such as those that involve voice and video communication. To support such services, routing algorithms that allow for the reservation of the needed bandwidth over a Virtual Circuit (VC) have been proposed. Commonly, these algorithms assign VCs to routes using the least-loaded concept, and thus result in balancing the load over the set of all candidate routes. In this paper, we show that for such reservation-based VC routing algorithms---which allow for the exclusive use of a preset fraction of a resource's bandwidth for an extended period of time---load balancing is not desirable as it results in resource fragmentation, which adversely affects the likelihood of accepting new VC requests. We present an on-line VC routing scheme that is based on the concept of ``load profiling'', which allows a distribution of ``available'' bandwidth across a set of candidate routes to match the characteristics of incoming VC QoS requests. We show the effectiveness of our load-profiling approach when compared to traditional load-balancing and load-packing VC routing schemes.} } @inproceedings{bestavros:97n, author={Azer Bestavros and Gitae Kim}, title={{Exploiting Redundancy For Timeliness in TCP Boston}}, booktitle = {Proceedings of RTAS'97: The IEEE Real-time Technology and Applications Symposium}, address = {Montreal, Canada}, month={June}, year=1997, url={http://www.cs.bu.edu/fac/best/res/papers/rtas97a.ps} } @inproceedings{bestavros:97i, author={Azer Bestavros and Gitae Kim}, title={{Implementation and Performance Evaluation of TCP Boston}}, booktitle = {Proceedings of ICC'97: The IEEE International Conference on Communications}, address = {Montreal, Canada}, month={June}, year=1997, url={http://www.cs.bu.edu/fac/best/res/papers/icc97.ps} } @inproceedings{bestavros:97h, author={Azer Bestavros}, title={{Load Profiling: A Methodology for Scheduling Real-Time Tasks in a Distributed System}}, booktitle = {Proceedings of ICDCS'97: The IEEE International Conference on Distributed Computing Systems}, address = {Baltimore, Maryland}, month={May}, year=1997, url={http://www.cs.bu.edu/fac/best/res/papers/icdcs97.ps}, abstract={ Traditionally, the goal of load management protocols for distributed systems has been to ensure that nodes are equally loaded. In this paper, we show that for real-time systems, load balancing is not desirable since it results in the available bandwidth being distributed equally amongst all nodes---in effect making all nodes in the system capable of offering almost the same bandwidth (in cycles per second) to incoming tasks. We show that this ``one size fits all'' practice leads to a higher rate of missed deadlines as incoming tasks may be denied service because they require bandwidth that cannot be granted at any single node---while plenty of fragmented bandwidth is collectively available in the system. We propose a new load-profiling strategy that allows the nodes of a distributed system to be unequally loaded so as to maximize the chances of finding a node that would satisfy the computational needs of incoming real-time tasks. The performance of the proposed protocol is evaluated via simulation, and is contrasted to other dynamic scheduling protocols for real-time distributed systems. } } @inproceedings{bestavros:97f, author={Azer Bestavros and Gitae Kim}, title={{TCP Boston: A Fragmentation-tolerant TCP Protocol for ATM Networks}}, booktitle = {Proceedings of Infocom'97: The IEEE International Conference on Computer Communication}, address = {Kobe, Japan}, month={April}, year=1997, url={http://www.cs.bu.edu/fac/best/res/papers/infocom97.ps}, abstract={ The popularity of TCP/IP coupled with the premise of high speed communication using Asynchronous Transfer Mode (ATM) technology have prompted the network research community to propose a number of techniques to adapt TCP/IP to ATM network environments. ATM offers Available Bit Rate (ABR) and Unspecified Bit Rate (UBR) services for best-effort traffic, such as conventional file transfer. However, recent studies have shown that TCP/IP, when implemented using ABR or UBR, leads to serious performance degradations, especially when the utilization of network resources (such as switch buffers) is high. Proposed techniques---switch-level enhancements, for example---that attempt to patch up TCP/IP over ATMs have had limited success in alleviating this problem. The major reason for TCP/IP's poor performance over ATMs has been consistently attributed to packet fragmentation, which is the result of ATM's 53-byte cell-oriented switching architecture. In this paper, we present a new transport protocol, TCP Boston, that turns ATM's 53-byte cell-oriented switching architecture into an advantage for TCP/IP. At the core of TCP Boston is the Adaptive Information Dispersal Algorithm (AIDA), an efficient encoding technique that allows for dynamic redundancy control. AIDA makes TCP/IP's performance less sensitive to cell losses, thus ensuring a graceful degradation of TCP/IP's performance when faced with congested resources. In this paper, we introduce AIDA and overview the main features of TCP Boston. We present detailed simulation results that show the superiority of our protocol when compared to other adaptations of TCP/IP over ATMs. In particular, we show that TCP Boston improves TCP/IP's performance over ATMs for both network-centric metrics (e.g., effective throughput) and application-centric metrics (e.g., response time). } } @inproceedings{almeida:96a, author={Virgilio Almeida and Azer Bestavros and Mark Crovella and Adriana de Oliveira}, title={{Characterizing Reference Locality in the Web}}, booktitle = {Proceedings of PDIS'96: The IEEE Conference on Parallel and Distributed Information Systems}, address = {Miami Beach, Florida}, month={December}, year=1996, pages={92-107}, url={http://www.cs.bu.edu/fac/best/res/papers/pdis96.ps}, abstract={ In this paper we propose models for both temporal and spatial locality of reference in streams of requests arriving at Web servers. We show that simple models based on document popularity alone are insufficient for capturing either temporal or spatial locality. Instead, we rely on an equivalent, but numerical, representation of a reference stream: a stack distance trace. We show that temporal locality can be characterized by the marginal distribution of the stack distance trace, and we propose models for typical distributions and compare their cache performance to our traces. We also show that spatial locality in a reference stream can be characterized using the notion of self-similarity. Self-similarity describes long-range correlations in the dataset, which is a property that previous researchers have found hard to incorporate into synthetic reference strings. We show that stack distance strings appear to be stongly self-similar, and we provide measurements of the degree of self-similarity in our traces. Finally, we discuss methods for generating synthetic Web traces that exhibit the properties of temporal and spatial locality that we measured in our data. } } @inproceedings{bestavros:96u, author={Sanjoy Baruah and Azer Bestavros}, title={{Timely and Fault-Tolerant Data Access from Broadcast Disks: A Pinwheel-Based Approach}}, booktitle = {Proceedings of DART'96: ACM CIKM Workshop on Databases: Active \& Real-Time}, address = {Rockville, Maryland}, month={November}, year=1996, url={http://www.cs.bu.edu/fac/best/res/papers/dart96.ps} } @inproceedings{bestavros:96m, author = {Azer Bestavros and Sue Nagy}, title = {{An Admission Control Paradigm for Value-cognizant Real-Time Databases}}, booktitle = {Proceedings of AAAI'96: The Fall Symposium on Flexible Computation in Intelligent Systems}, address = {MIT, Cambridge, MA}, month={November}, year=1996, url={http://www.cs.bu.edu/fac/best/res/papers/aaai96.ps} } @inproceedings{bestavros:96h, author = {Azer Bestavros}, title = {{Middleware Support for Data Mining and Knowledge Discovery in Large-scale Distributed Information Systems}}, booktitle = {SIGMOD'96 Data Mining Workshop}, address = {Montreal, Canada}, month={June}, pages={}, year=1996, url={http://www.cs.bu.edu/fac/best/res/papers/sigmod96.ps} } @inproceedings{bestavros:96g, author = {Azer Bestavros}, title = {{AIDA}-based Real-Time Fault-Tolerant Broadcast Disks}, booktitle = {Proceedings of RTAS'96: The 1996 IEEE Real-Time Technology and Applications Symposium}, address = {Boston, Massachusetts}, month={May}, pages={}, year=1996, url={http://www.cs.bu.edu/fac/best/res/papers/rtas96.ps} } @inproceedings{bestavros:96a, author={Azer Bestavros}, booktitle={Proceedings of ICDE'96: The 1996 International Conference on Data Engineering}, title={{Speculative Data Dissemination and Service to Reduce Server Load, Network Traffic and Service Time for Distributed Information Systems}}, address={New Orleans, Louisiana}, month={March}, year=1996, url={http://www.cs.bu.edu/fac/best/res/papers/icde96.ps}, pages={180-189}, abstract={ We present two server-initiated protocols to improve the performance of distributed information systems (e.g. WWW). Our first protocol is a hierarchical data dissemination mechanism that allows information to propagate from its producers to servers that are closer to its consumers. This dissemination reduces network traffic and balances load amongst servers by exploiting geographic and temporal locality of reference properties exhibited in client access patterns. Our second protocol relies on ``speculative service'', whereby a request for a document is serviced by sending, in addition to the document requested, a number of other documents that the server speculates will be requested in the near future. This speculation reduces service time by exploiting the spatial locality of reference property. We present results of trace-driven simulations that quantify the attainable performance gains for both protocols. } } @inproceedings{bestavros:95q, author={Azer Bestavros}, booktitle={Proceedings of CIKM'95: The 4th ACM International Conference on Information and Knowledge Management}, title={{Using Speculation to Reduce Server Load and Service Time on the World Wide Web}}, address={Baltimore, Maryland}, month="November", year=1995, url={http://www.cs.bu.edu/fac/best/res/papers/cikm95.ps} } @inproceedings{bestavros:95p, author={Azer Bestavros}, booktitle={Proceedings of SPDP'95: The 7th IEEE Symposium on Parallel and Distributed Processing}, title={{Demand-based document dissemination to reduce traffic and balance load in distributed information systems}}, address={San Anotonio, Texas}, month="October", year=1995, pages={338-345}, url={http://www.cs.bu.edu/fac/best/res/papers/spdp95.ps}, abstract={ Research on replication techniques to reduce traffic and minimize the latency of information retrieval in a distributed system has concentrated on client-based caching, whereby recently/frequently accessed information is cached at a client (or at a proxy thereof) in anticipation of future accesses. We believe that such myopic solutions---focussing exclusively on a particular client or set of clients---are likely to have a limited impact. Instead, we offer a solution that allows the replication of information to be done on a global supply/demand basis. We propose a hierarchical demand-based replication strategy that optimally disseminates information from its producer to servers that are closer to its consumers. The level of dissemination depends on the relative popularity of documents, and on the expected reduction in traffic that results from such dissemination. We used extensive HTTP logs to validate an analytical model of server popularity and file access profiles. Using that model we show that by disseminating the most popular documents on servers closer to clients, network traffic could be reduced considerably, while servers are load-balanced. We argue that this process could be generalized to provide for an automated server-based information dissemination protocol that will be more effective in reducing both network bandwidth and document retrieval times than client-based caching protocols. } } @inproceedings{bestavros:95o, author={Azer Bestavros}, booktitle={Proceedings of the ACM/IASTED/ISMM International Conference on Distributed Multimedia Systems and Applications}, title={{Demand-based data-dissemination in Distributed Multimedia Systems}}, address={Stanford, CA}, month="August", year=1995, url={http://www.cs.bu.edu/fac/best/res/papers/ismm95.ps} } @inproceedings{bestavros:95f, author={Azer Bestavros and Robert Carter and Mark Crovella and Carlos Cunha and Abdelsalam Heddaya and Sulaiman Mirdad}, booktitle={IEEE SDNE'96: The Second International Workshop on Services in Distributed and Networked Environments}, title={{Application Level Document Caching in the Internet}}, address={Whistler, British Columbia}, month="June", year=1995, url={http://www.cs.bu.edu/fac/best/res/papers/sdne95.ps} } @inproceedings{bestavros:93d, author="Azer Bestavros", title="{AIDA-based Communication for Distributed Real-Time Applications}", booktitle="Proceedings of the Second IEEE Network Management and Control Workshop", address="Tarrytown, NY", month="September", year=1993, url={http://www.cs.bu.edu/fac/best/res/papers/nmc93.ps} } @inproceedings{bestavros:93f, author="Azer Bestavros and Dimitrios Spartiotis", title="{Probabilistic Job Scheduling for Distributed Real-time Applications}", booktitle="Proceedings of the First IEEE Workshop on Real-Time Applications", address="New York, NY", month="May", year=1993, pages={97-102}, url={http://www.cs.bu.edu/fac/best/res/papers/rtaw93.ps} } @inproceedings{bestavros:93c, author="Azer Bestavros", title="{AIDA: A Bandwidth Allocation Strategy for Distributed Time-Critical Systems}", booktitle="Proceedings of the First IEEE IPPS Workshop on Parallel and Distributed Real-Time Systems", address="Newport Beach, CA", month="April", year=1993, url={http://www.cs.bu.edu/fac/best/res/papers/wpdrts93.ps} } @inproceedings{bestavros:90i, author="Azer Bestavros", title="{SETH: A {VLSI} chip for the real-time information dispersal and retrieval for security and fault-tolerance}", booktitle="Proceedings of ICPP'90, The 1990 International Conference on Parallel Processing", address="Chicago, Illinois", month="August", year=1990, pages={457-464}, url={http://www.cs.bu.edu/fac/best/res/papers/icpp90.ps} } @article{ConsidineEtal:tods09, author = "J. Considine and M. Hadjieleftheriou and F. Li and J. W. Byers and G. Kollios", title = "Robust Approximate Aggregation in Sensor Data Management Systems", journal = "{ACM Transactions on Database Systems}", month = "April", year = "2009", pages = "1--35", volume = "34(1)" } @inproceedings{WangByers:sigmetrics07, author = "C. Wang and J. Byers", title = "{Generating Representative ISP Topologies From First-Principles}", booktitle = "{Proc. of ACM SIGMETRICS '07}", month = "June", year = "2007", note = "Poster session paper", address = "San Diego, CA", pages = "365--366" } @inproceedings{DuerigEtal:sigcomm05, author = "J. Duerig and R. Ricci and J. W. Byers and J. Lepreau", title = "{Optimizing IP Address Assignment and Static Routing at Large Scale}", booktitle = "{Proc. of ACM SIGCOMM '05 Poster Session}", month = "August", year = "2007" } @inproceedings{SharmaByers:pam05, author = "M. Sharma and J. Byers", title = "{Scalable Coordination Techniques for Distributed Network Monitoring}", booktitle = "{Proc. of the Passive and Active Measurement Workshop (PAM 2005) poster session}", month = "April", year = "2005" } @inproceedings{BashByersConsidine:dmsn04, author = "Boulat A. Bash and John W. Byers and Jeffrey Considine", title = "{Approximately Uniform Random Sampling in Sensor Networks}", booktitle = "{Proc. of the 1st Workshop on Data Management in Sensor Networks (DMSN '04)}", month = "August", year = "2004", address = "Toronto, Canada" } @inproceedings(ConsidineLiKolliosByers:icde04, author = "J. Considine and F. Li and G. Kollios and J. W. Byers", title = "Approximate Aggregation Techniques for Sensor Databases", booktitle = "{Proc. of the 20th IEEE Int'l Conference on Data Engineering (ICDE '04)}", month = "April", year = "2004", address = "Boston", pages = "449--460", url = "http://www.cs.bu.edu/fac/byers/pubs/gg.ps" ) @article{ByersConsidineMitzenmacherRost:ton04, author = {John W. Byers and Jeffrey Considine and Michael Mitzenmacher and Stanislav Rost}, keywords = "ShapeShifter-Pub", title = "{Informed Content Delivery Across Adaptive Overlay Networks}", journal = "{IEEE/ACM Transactions on Networking}", month = "October", year = "2004", volume = "12(5)", pages = "767--780", abstract = {}, } @inproceedings{ByersRaz:allerton05, author = "J. W. Byers and D. Raz", title = "{Flow Allocation Games: Pricing, Equilibria and Fast Convergence}", booktitle ="{Proceedings of the 43rd Annual Allerton Conference on Communication, Control, and Computing}", address = "Monticello, IL", month = "September", year = "2005" } @article{ByersKwonLubyMitzenmacher:ton05, author = {John W. Byers and G.-I. Kwon and Michael Luby and Michael Mitzenmacher}, keywords = "ShapeShifter-Pub", title = "{Fine-Grained Layered Multicast with STAIR}", journal = "{IEEE/ACM Transactions on Networking}", year = "2006", month = "March", volume = "14(1)", pages = "81--93" } @article{BartalByersRaz:sicomp04, author = {Yair Bartal and John Byers and Danny Raz}, title = "{Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control}", journal = "{SIAM Journal on Computing}", volume = "33(6)", pages = "1261--1279", month = "August", year = "2004" } @article{KwonByers:jsac04, author = "G.-I. Kwon and J. W. Byers", keywords = "ShapeShifter-Pub", title = "Leveraging Single Rate Schemes in Multiple Rate Multicast Congestion Control Design", journal = "{IEEE Journal on Selected Areas in Communication (J-SAC)---Special Issue on Design, Implementation and Analysis of Communication Protocols}", month = "December", year = "2004", volume = "22(10)", pages = "1975--1986", url = {http://www.cs.bu.edu/fac/byers/pubs/leverage.pdf} } @inproceedings(KwonByers:infocom04, author = "G.-I. Kwon and J. W. Byers", keywords = "ShapeShifter-Pub", title = "ROMA: Reliable Overlay Multicast with Loosely Coupled TCP Connections", booktitle = "Proc. of IEEE INFOCOM", month = "March", year = "2004", address = "Hong Kong", url = {http://www.cs.bu.edu/fac/byers/pubs/roma.ps} ) @inproceedings(ByersConsidineMitzenmacher:spaa04, author = "J. W. Byers and J. Considine and M. Mitzenmacher", keywords = "ShapeShifter-Pub", title = "Geometric Generalizations of the Power of Two Choices", booktitle = "Proc. of the 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA)", month = "June", year = "2004", address = "Barcelona", pages = "31--35", url = "http://www.cs.bu.edu/fac/byers/pubs/gg.ps" ) @inproceedings(ConsidineByersMayer-Patel:hotnets03, author = "J. Considine and J. W. Byers and K. Mayer-Patel", keywords = "MassServer-Pub", title = "A Constraint Satisfaction Approach to Testbed Embedding Services", booktitle = "Proc. of HotNets-II", month = "November", year = "2003", address = "Cambridge, MA", url = "http://www.cs.bu.edu/fac/byers/pubs/hotnets2.ps" ) @article{LakhinaByersCrovellaMatta:jsac03, author = "A. Lakhina and J. Byers and M. Crovella and I. Matta", title = {{On the Geographic Location of Internet Resources}}, journal = "{IEEE Journal on Selected Areas in Communication (J-SAC)---Special Issue on Internet and WWW Measurement, Mapping, and Modeling }", year = 2003, volume = "21(6)", pages = "934--948", month = "August", keywords = "MassServer-Pub", comment = "Guest Editors: S. Jamin, D. Raz, Y. Shavitt, and D. Towsley", url = "http://www.cs.bu.edu/faculty/matta/Papers/jsac03.ps" } @article{FayedKrapivskyByersCrovellaFinkelRedner:ccr03, author = "M. Fayed and P. Krapivsky and J. Byers and M. Crovella and D. Finkel and S. Redner", title = "On the Emergence of Highly Variable Distributions in the Autonomous System Topology", keywords = "MassServer-Pub", journal = "{ACM Computer Communication Review}", year = 2003, volume = "33(2)", pages = "41--50", month = "April", url = "http://www.cs.bu.edu/fac/byers/pubs/CCR03.ps" } @article{ByersChengConsidineItkisYeung:comcom03, author = "J. Byers and J. Considine and G. Itkis and M. Cheng and A. Yeung", title = "Securing Bulk Content Almost for Free", keywords = "ShapeShifter-Pub", journal = "{Computer Communications (Elsevier)}", year = 2006, month = "February", pages = "280--290" } @inproceedings(LakhinaByersCrovellaXie:infocom03, author = "A. Lakhina and J. W. Byers and M. Crovella and P. Xie", keywords = "MassServer-Pub", title = "{Sampling Biases in IP Topology Measurements}", booktitle = "Proc. of IEEE INFOCOM", month = "April", year = "2003", address = "San Francisco, CA", url = {http://www.cs.bu.edu/fac/byers/pubs/samplingbias.pdf} ) @inproceedings(KwonByers:infocom03, author = "G.-I. Kwon and J. W. Byers", keywords = "ShapeShifter-Pub", title = "Smooth Multirate Multicast Congestion Control", booktitle = "Proc. of IEEE INFOCOM", month = "April", year = "2003", address = "San Francisco, CA", url = {http://www.cs.bu.edu/fac/byers/pubs/SMCC.pdf} ) @inproceedings(ByersConsidineMitzenmacher:iptps03, author = "J. W. Byers and J. Considine and M. Mitzenmacher", keywords = "ShapeShifter-Pub", title = "Simple Load Balancing for Distributed Hash Tables", booktitle = "Proc. of 2nd Int'l Workshop on Peer-to-Peer Systems (IPTPS)", month = "February", year = "2003", address = "Berkeley, CA", pages = "31--35", url = "http://www.cs.bu.edu/fac/byers/pubs/iptps03_loadbalance.ps" ) @inproceedings{LakhinaByersCrovellaMatta:imw02, author = "Anukool Lakhina and John Byers and Mark Crovella and Ibrahim Matta", title = {{On the Geographic Location of Internet Resources}}, keywords = "MassServer-Pub", booktitle = "{Proceedings of the Internet Measurement Workshop}", year = 2002, month = "November", address = "Marseille, France", note = "Short Abstract", url = "http://www.cs.bu.edu/faculty/matta/Papers/imw02.ps" } @inproceedings{SharmaByers:gi02, author = "Manish Sharma and John W. Byers", title = "{How Well Does File Size Predict Wide-Area Transfer Time?}", booktitle={Proceedings of the 2002 Globecom Global Internet Symposium}, address={Taipei, Taiwan}, month = "October", year = "2002", url={http://www.cs.bu.edu/fac/byers/pubs/filesize.ps}, keywords={MassServer-Pub} } @inproceedings{ByersConsidineMitzenmacherRost:sigcomm02, author = {John W. Byers and Jeffrey Considine and Michael Mitzenmacher and Stanislav Rost}, keywords = "ShapeShifter-Pub", title = "{Informed Content Delivery Across Adaptive Overlay Networks}", booktitle = {Proceedings of ACM SIGCOMM '02}, month = "August", year = "2002", address = "Pittsburgh, PA", pages = "47-60", url = {http://www.cs.bu.edu/fac/byers/pubs/SIGCOMM02.ps}, abstract = {}, } @article{ByersHornLubyMitzenmacherShaver:jsac02, author = "J.W. Byers and G. Horn and M. Luby and M. Mitzenmacher and W. Shaver", keywords = "ShapeShifter-Pub", title = "{FLID-DL: Congestion Control for Layered Multicast}", journal = "IEEE Journal on Selected Areas in Communications", volume = "20(8)", pages = "1558--1570", month = "October", year = "2002", url = {http://www.cs.bu.edu/fac/byers/pubs/JSAC-FLID.ps} } @article{ByersLubyMitzenmacher:jsac02, author = "J.W. Byers and M. Luby and M. Mitzenmacher", keywords = "ShapeShifter-Pub", title = "A Digital Fountain Approach to Asynchronous Reliable Multicast", journal = "IEEE Journal on Selected Areas in Communications", volume = "20(8)", pages = "1528--1540", month = "October", year = "2002", url = {http://www.cs.bu.edu/fac/byers/pubs/JSAC-DF.ps}, } @article{RostByersBestavros:jcc02, author={Stanislav Rost and John Byers and Azer Bestavros}, title={{The Cyclone Server Architecture: Streamlining Delivery of Popular Content}}, journal={{International Journal on Computer Communications}}, keywords={Content Delivery, Tornado Codes, Scalable Server Architectures, ShapeShifter-Pub, MassServer-Pub}, volume = {25(4)}, year=2002, url = {http://www.cs.bu.edu/faculty/best/res/papers/wcw01.pdf}, pubisher={Elsevier}, abstract={ We propose a new technique for efficiently delivering popular content from information repositories with bounded file caches. Our strategy relies on the use of fast erasure codes (a.k.a. forward error correcting codes) to generate encodings of popular files, of which only a small sliding window is cached at any time instant, even to satisfy an unbounded number of asynchronous requests for the file. Our approach capitalizes on concurrency to maximize sharing of state across different request threads while minimizing cache memory utilization. Additional reduction in resource requirements arises from providing for a lightweight version of the network stack. In this paper, we describe the design and implementation of our Cyclone server as a Linux kernel subsystem.} } @inproceedings(ByersKwon:ngc01, author = "John Byers and Gu-In Kwon", keywords = "ShapeShifter-Pub", title = {{STAIR: Practical AIMD Multirate Multicast Congestion Control}}, booktitle = "Third Int'l Workshop on Networked Group Communication (NGC 2001)", url = "http://www.cs.bu.edu/fac/byers/pubs/STAIR.ps", month = "November", year = "2001" ) @inproceedings(Byers:spie01, author = "John Byers", keywords = "ShapeShifter-Pub, MassServer-Pub", title = {{Flexible Transport Services for Emerging Opportunities in Internet Content Delivery}}, booktitle = "Proceedings of SPIE ITCom 2001, Conference on Scalability and Traffic Control in IP Networks", url = "http://www.cs.bu.edu/fac/byers/pubs/SPIE01.ps", month = "August", year = "2001" ) @inproceedings{RostByersBestavros:wcw01, author={Stanislav Rost and John Byers and Azer Bestavros}, title={{The Cyclone Server Architecture: Streamlining Delivery of Popular Content}}, booktitle={{Proceedings of the 6th International Web Caching and Content Delivery Workshop}}, keywords={Content Delivery, Tornado Codes, Scalable Server Architectures, ShapeShifter-Pub, MassServer-Pub}, month={June}, year=2001, address={Boston, MA}, url = {http://www.cs.bu.edu/faculty/best/res/papers/wcw01.pdf}, abstract={ We propose a new technique for efficiently delivering popular content from information repositories with bounded file caches. Our strategy relies on the use of fast erasure codes (a.k.a. forward error correcting codes) to generate encodings of popular files, of which only a small sliding window is cached at any time instant, even to satisfy an unbounded number of asynchronous requests for the file. Our approach capitalizes on concurrency to maximize sharing of state across different request threads while minimizing cache memory utilization. Additional reduction in resource requirements arises from providing for a lightweight version of the network stack. In this paper, we describe the design and implementation of our Cyclone server as a Linux kernel subsystem.} } @inproceedings (ByersLubyMitzenmacher:infocom01, author = "J. W. Byers and M. Luby and M. Mitzenmacher", title = "Fine-Grained Layered Multicast", booktitle = "Proceedings of IEEE INFOCOM '01", month = "April", address = "Anchorage, AK", url = "http://www.cs.bu.edu/fac/byers/pubs/finegrained.ps", year = "2001" ) @inproceedings(ByersFruminHornLubyMitzenmacherRoetterShaver:ngc00, author = "John Byers and Michael Frumin and Gavin Horn and Michael Luby and Michael Mitzenmacher and Alex Roetter and William Shaver", title = {{FLID-DL: Congestion Control for Layered Multicast}}, booktitle = "Second Int'l Workshop on Networked Group Communication (NGC 2000)", url = "http://www.cs.bu.edu/fac/byers/pubs/FLID-DL.ps.gz", month = "November", year = "2000" ) @inproceedings{ByersNasser:mobihoc00, author = "J. Byers and G. Nasser", title = "Utility-Based Decision-Making in Wireless Sensor Networks (extended abstract)", booktitle = "Proceedings of IEEE MobiHOC 2000", address = "Boston, MA", month = "August", url = "http://www.cs.bu.edu/fac/byers/pubs/sensor_utility.ps", year = "2000" } @inproceedings (ByersLubyMitzenmacher:infocom99, author = "J. W. Byers and M. Luby and M. Mitzenmacher", title = "Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads", booktitle = "Proceedings of IEEE INFOCOM '99", pages = "275--83", month = "March", address = "New York, NY", url = "http://www.cs.bu.edu/fac/byers/pubs/mirrors.ps", year = "1999" ) @inproceedings(ByersLubyMitzenmacherRege:sigcomm98, author = "J. W. Byers and M. Luby and M. Mitzenmacher and A. Rege", title = "A Digital Fountain Approach to Reliable Distribution of Bulk Data", booktitle = "Proceedings of ACM SIGCOMM '98", month = "September", year = "1998", address = "Vancouver", url = "http://www.cs.bu.edu/fac/byers/pubs/digfoun.ps", pages = "56-67" ) @inproceedings(BartalByersRaz:focs97, author = "Y. Bartal and J. Byers and D. Raz", title = "Global Optimization Using Local Information with Applications to Flow Control", booktitle = "Proceedings of the 38th IEEE Symposium on Mathematical Foundations of Computer Science (FOCS)", address = "Miami Beach, FL", month = "October", year = "1997", url = "http://www.cs.bu.edu/fac/byers/pubs/flowcontrol.ps", pages = "303-312" ) @inproceedings(AdlerBartalByersLubyRaz:istcs97, author = "M. Adler and Y. Bartal and J. Byers and M. Luby and D. Raz", title = "A Modular Analysis of Network Transport Protocols", booktitle = "Proc. of the 5th Israeli Symposium on Theory of Computing and Systems", month = "June", url = "http://www.cs.bu.edu/fac/byers/pubs/modanal.ps", year = "1997" ) @inproceedings(BartalByersLubyRaz:iscc98, author = "Y. Bartal and J. Byers and M. Luby and D. Raz", title = "Feedback-Free Multicast Prefix Protocols", booktitle = "Proc. of the IEEE Symposium on Computers and Communications", month = "June", url = "http://www.cs.bu.edu/fac/byers/pubs/mprefix.ps", year = "1998" ) @inproceedings{SommersBarfordCrovella:Presto09, author = "Joel Sommers and Paul Barford and Mark Crovella", title = "Router Primitives for Programmable Active Measurement", booktitle = "The Second ACM SIGCOMM Workshop on Programmable Routers for Extensible Services of Tomorrow (Presto '09)", month = "Aug", year = 2009, catID1 = "IM", catID2 = "methods", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/presto09-active-msmt.pdf", abstract = "Active probe-based measurements are the foundation for understanding important network path properties such as SLA compliance and available bandwidth. Well known challenges in active probe-based measurement include the logistics of deploying and managing host-based measurement infrastructures, the load that probe packets place on network resources, the inaccuracy of resultant measurements, and the relatively limited set of features that can be measured. In this paper, we argue that these challenges can be addressed through programmable, router-based support for active measurement. While commercial routers today have some basic capabilities for emitting probe packets, these mechanisms are minimal and do not allow the necessary flexibility in the kinds of probing that can be done. We describe a set of functional primitives that enable a wide range of router-based active measurements and would improve and simplify the ability to assess and understand network structure and dynamic network state. We discuss the associated resource requirements and implications of our approach related to configuration, security and privacy. Finally, we support and illustrate the powerful potential of our approach through a series of measurement scenarios and describe our ongoing efforts toward a Click-based implementation of our framework." } @inproceedings{CvetkovskiCrovella:Infocom09, author = "Andrej Cvetkovski and Mark Crovella", title = "Hyperbolic Embedding and Routing for Dynamic Graphs", booktitle = "Proceedings of Infocom 2009", location = "Rio de Janeiro, Brazil", month = "Apr", year = 2009, catID1 = "IM", catID2 = "management", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom09-hyperbolic.pdf", abstract = "We propose a scheme for routing in arbitrary network connectivity graphs, based on greedy routing and utilizing virtual node coordinates. In dynamic multihop packet-switching communication networks, routing elements can join or leave during network operation or exhibit intermittent failures. We present an algorithm for online greedy graph embedding in the hyperbolic plane that enables incremental embedding of network nodes as they join the network, without disturbing the global embedding. Even a single link or node removal may invalidate the greedy routing success guarantees in network embeddings based on an embedded spanning tree subgraph. As an alternative to frequent reembedding of temporally dynamic network graphs in order to retain the greedy embedding property, we propose a simple but robust generalization of greedy distance routing called Gravity--Pressure (GP) routing. Our routing method always succeeds in finding a route to the destination provided that a path exists, even if a significant fraction of links or nodes is removed subsequent to the embedding. GP routing does not require precomputation or maintenance of special spanning subgraphs and, as demonstrated by our numerical evaluation, is particularly suitable for operation in tandem with our proposed algorithm for online graph embedding." } @inproceedings{ErramilliCrovella:Chants08, author = "Vijay Erramilli and Mark Crovella", title = "Forwarding in Opportunistic Networks with Resource Constraints", booktitle = "Proceedings of the Fourth ACM Workshop on Challenged Networks (CHANTS 08)", location = "San Francisco, CA", month = "September", year = 2008, catID1 = "IM", catID2 = "wireless", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/chants08-resource-constrained.pdf", abstract = "Effective forwarding in mobile opportunistic networks is a challenge, given the unpredictable mobility of nodes, short contact durations between nodes, wireless interference and limited buffer sizes. Most forwarding algorithms aim at decreasing costs (relative to flooding the network) by forwarding only to nodes which are likely to be good relays. While it is non-trivial to decide if an encountered node is a good relay or not at the moment of encounter, it is harder still to prioritize which messages to transmit under the presence of short contact durations and which messages to drop when buffers become full. The main objective of this paper is to study different message prioritization schemes using real measurements. Such schemes can be broadly divided into two categories - schemes which do not use any network information, and schemes which do. Examples of the former set of schemes include FIFO/LIFO etc. For the latter set of schemes, there is a key design choice: On one hand, we have the following scheme: when a forwarding opportunity presents itself, assign high priorities to messages which are relatively close to their intended destination. On the other hand, we can assign high priorities to messages which are farther away from their destination than closer messages. In order to decide if messages are close to their destination or not, we have to rely on a forwarding algorithm. For this, we use delegation forwarding schemes which have been shown to be efficient in terms of cost incurred in the network. We develop a new set of prioritization schemes based on delegation schemes. We consider these schemes in our empirical study." } @inproceedings{FonsecaCrovellaSalamatian:Hotmetrics08, author = "Nahur Fonseca and Mark Crovella and Kav{\'e} Salamatian", title = "Long Range Mutual Information", booktitle = "Proceedings of the First Workshop on Hot Topics in Measurement and Modeling of Computer Systems (Hotmetrics '08)", location = "Annapolis, MD", month = "June", year = 2008, catID1 = "IM", catID2 = "anomalies", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/hotmetrics08-lrmi.pdf", abstract = "Network traffic modeling generally views traffic as a superposition of flows that creates a timeseries of volume counts (e.g. of bytes or packets). What is omitted from this view of traffic is the contents of packets. Packet contents (e.g. header fields) contain considerable information that can be useful in many applications such as change and anomaly detection, and router performance evaluation. The goal of this paper is to draw attention to the problem of modeling traffic with respect to the contents of packets. In this regard, we identify a new phenomenon: long range mutual information (LRMI), which means that the dependence of the contents of a pair of packets decays as a power of the lag between them. We demonstrate that although LRMI is hard to measure, and hard to model using the mathematical tools at hand, its effects are easy to identify in real traffic, and it may have a considerable impact on a number of applications. We believe that work in modeling this phenomenon will open doors to new kinds of traffic models, and new advances in a number of applications." } @inproceedings{ErramilliEtAl:Mobihoc08, author = "Vijay Erramilli and Augustin Chaintreau and Mark Crovella and Christophe Diot", title = "Delegation Forwarding", booktitle = "Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHoc)", location = "Hong Kong SAR, China", month = "May", year = 2008, pages = "251-259", catID1 = "IM", catID2 = "wireless", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/mhoc08-delegation-forwarding.pdf", abstract = "Mobile opportunistic networks are characterized by unpredictable mobility, heterogeneity of contact rates and lack of global information. Successful delivery of messages at low costs and delays in such networks is thus challenging. Most forwarding algorithms avoid the cost associated with flooding the network by forwarding only to nodes that are likely to be good relays, using a quality metric associated with nodes. However it is non-trivial to decide whether an encountered node is a good relay at the moment of encounter. Thus the problem is in part one of online inference of the quality distribution of nodes from sequential samples, and has connections to optimal stopping theory. Based on these observations we develop a new strategy for forwarding, which we refer to as delegation forwarding. We analyse two variants of delegation forwarding and show that while naive forwarding to high contact rate nodes has cost linear in the population size, the cost of delegation forwarding is proportional to the square root of population size. We then study delegation forwarding with different metrics using real mobility traces and show that delegation forwarding performs as well as previously proposed algorithms at much lower cost. In particular we show that the delegation scheme based on destination contact rate does particularly well." } @inproceedings{ChhabraEtAl:Infocom08, author = "Parminder Chhabra and Clayton Scott and Eric D. Kolaczyk and Mark Crovella", title = "Distributed Spatial Anomaly Detection", booktitle = "Proceedings of Infocom 2008", location = "Phoenix, AZ", month = "Apr", year = 2008, catID1 = "IM", catID2 = "anomalies", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom08-distributed-ad.pdf", abstract = "Detection of traffic anomalies is an important problem that has been the focus of considerable research. Recent work has shown the utility of spatial detection of anomalies via cross-link traffic comparisons. In this paper we identify three advances that are needed to make such methods more useful and practical for network operators. First, anomaly detection methods should avoid global communication and centralized decision making. Second, nonparametric anomaly detection methods are needed to augment current parametric approaches. And finally, such methods should not just identify possible anomalies, but should also annotate each detection with some probabilistic qualifier of its importance. We propose a framework that simultaneously advances the current state of the art on all three fronts. We show that routers can effectively identify volume anomalies through cross-link comparison of traffic observed only on the router's own links. Second, we show that generalized quantile estimators are an effective way to identify high-dimensional sets of local traffic patterns that are potentially anomalous; such methods can be either parametric or nonparametric, and we evaluate both. Third, through the use of false discovery rate as a detection metric, we show that candidate anomalous patterns can be equipped with an estimate of a probability that they truly are anomalous. Overall, our framework provides network operators with an anomaly detection methodology that is distributed, effective, and easily interpretable. Part of the underlying statistical framework, which merges aspects of nonparametric set estimation and multiple hypothesis testing, is novel in itself, although the derivation of that framework is necessarily given elsewhere." } @inproceedings{ErramilliEtAl:imc2007, author = "Vijay Erramilli and Augustin Chaintreau and Mark Crovella and Christophe Diot", title = "Diversity of Forwarding Paths in Pocket Switched Networks", booktitle = "Proceedings of the ACM/SIGCOMM Internet Measurement Conference", pages = "161--174", month = "October", year = "2007", catID1 = "IM", catID2 = "wireless", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imc07-path-diversity.pdf", abstract = "Forwarding in DTNs is a challenging problem. We focus on the specific issue of forwarding in an environment where mobile devices are carried by peoplye in a restricted physical space (a conference) and contact patterns are not predictable. We show for the first time a path explosion phenomenon between most pairs of nodes. This means that, once the first path reaches the destination, the number of subsequent paths grows rapidly with time, so there usually exist many near-optimal paths. We study the path explosion phenomenon both analytically and empirically. Our results highlight the importance of unequal contact rates across nodes for understanding the performance of forwarding algorithms. We also find that a variety of well-known forwarding algorithms show surprisingly similar performance in our setting and we interpret this fact in light of the path explosion phenomenon." } @inproceedings{ErikssonEtAl:imc2007, author = "Brian Eriksson and Paul Barford and Robert Nowak and Mark Crovella", title = "Learning Network Structure from Passive Measurements", booktitle = "Proceedings of the ACM/SIGCOMM Internet Measurement Conference", pages = "209--214", month = "October", year = "2007", catID1 = "IM", catID2 = "methods", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imc07-passive-discovery.pdf", abstract = "The ability to discover network organization, whether in the form of explicit topology reconstruction or as embeddings that approximate topological distance, is a valuable tool. To date, network discovery has been based on active measurements. However, it is feasible to envision passive discovery of network topology and distance, simply by monitoring packet traffic. Unfortunately, the lack of explicit control over the choices of which endpoints are measured means that passive network discovery must deal with the problem of missing information. We consider one such example, namely reconstructing embeddings and some topological information from unwanted network traffic captured at a set of honeypots. We develop a number of algorithms for reconstruction of missing measurements. Our algorithms use insights derived from the known topology of the Internet as well as local interpolation techniques from approximation theory. We characterize the degree to which missing information can be reconstructed and show that a limited but useful amount of reconstruction is possible, allowing the recovery of network embeddings and some topological relationships from passively collected data." } @article{ChuaKolaczykCrovella:jsac06, author = "David B. Chua and Eric D. Kolaczyk and Mark Crovella", title = "Network Kriging", journal = "IEEE Journal on Selected Areas in Communications, Special Issue on Sampling the Internet", month = "December", year = "2006", volume = 24, number = 12, pages = "2263--2272", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/Network_Kriging.pdf", catID1 = "IM", catID2 = "graphestim", abstract = "Network service providers and customers are often concerned with aggregate performance measures that span multiple network paths. Unfortunately, forming such network-wide measures can be difficult, due to the issues of scale involved. In particular, the number of paths grows too rapidly with the number of endpoints to make exhaustive measurement practical. As a result, it is of interest to explore the feasibility of methods that dramatically reduce the number of paths measured in such situations while maintaining acceptable accuracy. We cast the problem as one of statistical prediction---in the spirit of the so-called `kriging' problem in spatial statistics---and show that end-to-end network properties may be accurately predicted in many cases using a surprisingly small set of carefully chosen paths. More precisely, we formulate a general framework for the prediction problem, propose a class of linear predictors for standard quantities of interest (e.g., averages, totals, differences) and show that linear algebraic methods of subset selection may be used to effectively choose which paths to measure. We characterize the performance of the resulting methods, both analytically and numerically. The success of our methods derives from the low effective rank of routing matrices as encountered in practice, which appears to be a new observation in its own right with potentially broad implications on network measurement generally." } @article{DonnetRaoultFriedmanCrovella:jsac06, author = "Benoit Donnet and Philippe Raoult and Timur Friedman and Mark Crovella", title = "Deployment of an Algorithm for Large-Scale Topology Discovery", journal = "IEEE Journal on Selected Areas in Communications, Special Issue on Sampling the Internet", month = "December", year = "2006", volume = 24, number = 12, pages = "2210--2220", catID1 = "IM", catID2 = "trathome", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/Doubletree.pdf", abstract = "Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. This paper describes several contributions towards that end. These were first presented in the proceedings of ACM Sigmetrics 2005. We show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We propose two metrics focusing on redundancy in probing and show that both are important. We also propose and evaluate Doubletree, an algorithm that strongly reduces redundancy while maintaining nearly the same level of node and link coverage. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Following the Sigmetrics work, we implemented Doubletree, and deployed it in a real network environment. This paper describes that implementation, as well as preliminary favorable results." } @article{ClaffyEtAl:CCR06, author = "{kc Claffy} and Mark Crovella and Timur Friedman and Colleen Shannon and Neil Spring", title = "Community-oriented network measurement infrastructure (CONMI) workshop report", journal = "Computer Communication Review", volume = 36, number = 2, pages = "41--48", month = "April", year = 2006, url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/conmi-workshop2005.pdf" } @inproceedings{LiEtAl:imc2006, author = "Xin Li and Fang Bian and Mark Crovella and Christophe Diot and Ramesh Govindan and Gianluca Iannaccone", title = "Detection and Identification of Network Anomalies Using Sketch Subspaces", booktitle = "Proceedings of the ACM/SIGCOMM Internet Measurement Conference", pages = "147--152", month = "October", year = "2006", catID1 = "IM", catID2 = "anomalies", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imc06-sketch-subspaces.pdf", abstract = "Network anomaly detection using dimensionality reduction techniques has received much recent attention in the literature. For example, previous work has aggregated netflow records into origin-destination (OD) flows, yielding a much smaller set of dimensions which can then be mined to uncover anomalies. However, this approach can only identify which OD flow is anomalous, not the particular IP flow(s) responsible for the anomaly. In this paper we show how one can use random aggregations of IP flows (i.e., sketches) to enable more precise identification of the underlying causes of anomalies. We show how to combine traffic sketches with a subspace method to (1) detect anomalies with high accuracy and (2) identify the IP flows(s) that are responsible for the anomaly. Our method has detection rates comparable to previous methods and detects many more anomalies than prior work, taking us a step closer towards a robust on-line system for anomaly detection and identification." } @inproceedings{ErramilliCrovellaTaft:imc2006, author = "Vijay Erramilli and Mark Crovella and Nina Taft", title = "An Independent-Connection Model for Traffic Matrices", booktitle = "Proceedings of the ACM/SIGCOMM Internet Measurement Conference", month = "October", year = "2006", catID1 = "IM", catID2 = "management", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imc06-icmodel.pdf", extra1 = "Full Version", extra1url = "http://www.cs.bu.edu/faculty/crovella/TBD", abstract = "A common assumption made in traffic matrix (TM) modeling and estimation is independence of a packet's network ingress and egress. We argue that in real IP networks, this assumption should not and does not hold. The fact that most traffic consists of two-way exchanges of packets means that traffic streams flowing in opposite directions at any point in the network are not independent. In this paper we propose a model for traffic matrices based on independence of connections rather than packets. We argue that the independent-connection (IC) model is more intuitive, and has a more direct connection to underlying network phenomena than the gravity model. To validate the IC model, we show that it fits real data better than the gravity model and that it works well as a prior in the TM estimation problem. We study the model's parameters empirically and identify useful stability properties. This justifies the use of the simpler versions of the model for TM applications. To illustrate the utility of the model we focus on two such applications: synthetic TM generation and TM estimation. To the best of our knowledge this is the first traffic matrix model that incorporates properties of bidirectional traffic." } @book{CrovellaKrishnamurthy:book06, author = "Mark Crovella and Balachander Krishnamurthy", title = "{Internet} Measurement: Infrastructure, Traffic and Applications", publisher = "John Wiley and Sons, Inc", year = 2006, pages = 512, catID1 = "IM", url = "http://www.amazon.com/gp/product/047001461X/", extra1 = "Wiley Press page with book excerpts.", extra1url = "http://www.wiley.com/WileyCDA/WileyTitle/productCd-047001461X.html" } @article{GueyeZivianiCrovellaFdida:ton2006, author = "Bamba Gueye and Artur Ziviani and Mark Crovella and Serge Fdida", title = "Constraint-Based Geolocation of {Internet} Hosts", journal = "IEEE/ACM Transactions on Networking", month = "December", year = "2006", volume = 14, number = 6, pages = "1219--1232", catID1 = "IM", catID2 = "location" } @inproceedings{LakhinaCrovellaDiot:flocon05, author = "Anukool Lakhina and Mark Crovella and Christophe Diot", title = "Detecting Distributed Attacks using Network-Wide Flow Traffic", booktitle = "Proceedings of FloCon 2005 Analysis Workshop", month = "September", year = "2005", location = "New Orleans, LA", catID1 = "IM", catID2 = "anomalies", abstract = "In this work, we present our methods to detect distributed attacks in backbone networks using sampled flow traffic data. Distributed attacks are traditionally viewed to be fundamentally more difficult to detect than single-source attacks. In contrast, we demonstrate that the more distributed an attack is, the better our methods are at detecting it. This is because our methods analyze correlations across all network-wide traffic simultaneously, instead of inspecting traffic on individual links in isolation. In addition, our methods are highly sensitive to the attack intensity; we show that attacks rates of less than 1\% of the underlying traffic can be detected successfully by our methods.", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/flocon05.pdf" } @misc{BasaniEtAl:patent06, author = "Vijay Basani and Krishna Mangipudi and Lynne Murach and Leroy Karge and Vitaly Revsin and Azer Bestavros and Mark Crovella and Domenic LaRosa", title = {Method and Apparatus for Election of Group Leaders in a Distributed Network}, url = "http://patft.uspto.gov/netacgi/nph-Parser?patentnumber=6993587", year = 2006, catID1 = "Systems", catID2 = "servers", howpublished = {US Patent Number 6,993,587, issued January 31, 2006} } @inproceedings{LakhinaCrovellaDiot:sigcomm05, author = "Anukool Lakhina and Mark Crovella and Christophe Diot", title = "Mining Anomalies Using Traffic Feature Distributions", booktitle = "Proceedings of ACM SIGCOMM 2005", month = "August", year = "2005", location = "Philadelphia, PA", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigc05-mining-anomalies.pdf", pages = "217--228", catID1 = "IM", catID2 = "anomalies", extra1 = "Earlier (Full) Version, published as BUCS Technical Report BUCS-TR-2005-002", extra1url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/mining-anomalies-TR.pdf", abstract = "The increasing practicality of large-scale flow capture makes it possible to conceive of traffic analysis methods that detect and identify a large and diverse set of anomalies. However the challenge of effectively analyzing this massive data source for anomaly diagnosis is as yet unmet. We argue that the distributions of packet features (IP addresses and ports) observed in flow traces reveals both the presence and the structure of a wide range of anomalies. Using entropy as a summarization tool, we show that the analysis of feature distributions leads to significant advances on two fronts: (1) it enables highly sensitive detection of a wide range of anomalies, augmenting detections by volume-based methods, and (2) it enables automatic classification of anomalies via unsupervised learning. We show that using feature distributions, anomalies naturally fall into distinct and meaningful clusters. These clusters can be used to automatically classify anomalies and to uncover new anomaly types. We validate our claims on data from two backbone networks (Abilene and Geant) and conclude that feature distributions show promise as a key element of a fairly general network anomaly diagnosis framework." } @inproceedings{ChuaKolaczykCrovella:sigmetrics05, author = "David B. Chua and Eric D. Kolaczyk and Mark Crovella", title = "A Statistical Framework for Efficient Monitoring of End-to-End Network Properties", booktitle = "Proceedings of ACM SIGMETRICS (Poster Paper)", month = "June", year = 2005, location = "Banff, Canada", catID1 = "IM", catID2 = "graphestim", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigm05-end2end.pdf", extra1 = "Earlier (Full) Version, published as Technical Report at arXiv:cs.NI/0412037", extra1url = "http://arxiv.org/abs/cs.NI/0412037", abstract = "Network service providers and customers are often concerned with aggregate performance measures that span multiple network paths. Unfortunately, forming such network-wide measures can be difficult, due to the issues of scale involved. In particular, the number of paths grows too rapidly with the number of endpoints to make exhaustive measurement practical. As a result, it is of interest to explore the feasibility of methods that dramatically reduce the number of paths measured in such situations while maintaining acceptable accuracy. In previous work we have proposed a statistical framework for efficiently addressing this problem, in the context of additive metrics such as delay and loss rate, for which the per-path metric is a sum of per-link measures (possibly under appropriate transformation). The key to our method lies in the observation and exploitation of the fact that network paths show significant redundancy (sharing of common links). In this paper we make three contributions: (1) we generalize the framework to make it more immediately applicable to network measurements encountered in practice; (2) we demonstrate that the observed path redundancy upon which our method is based is robust to variation in key network conditions and characteristics, including the presence of link failures; and (3) we show how the framework may be applied to address three practical problems of interest to network providers and customers, using data from an operating network. In particular, we show how appropriate selection of small sets of path measurements can be used to accurately estimate network-wide averages of path delays, to reliably detect network anomalies, and to effectively make a choice between alternative sub-networks, as a customer choosing between two providers or two ingress points into a provider network." } @inproceedings{DonnetEtAl:sigmetrics05, author = "Benoit Donnet and Philippe Raoult and Timur Friedman and Mark Crovella", title = "Efficient Algorithms for Large-Scale Topology Discovery", booktitle = "Proceedings of ACM SIGMETRICS", year = 2005, location = "Banff, Canada", month="June", catID1="IM", catID2="trathome", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigm05-trathome.pdf", extra1 = "Earlier Version, published as Technical Report at arXiv:cs.NI/0411013", extra1url="http://arxiv.org/abs/cs.NI/0411013", abstract="There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. In this paper we make two contributions toward that end. First, we show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We measure two kinds of redundancy in probing (intra- and inter-monitor) and show that both kinds are important. We show that straightforward approaches to addressing these two kinds of redundancy must take opposite tacks, and are thus fundamentally in conflict. Our second contribution is to propose and evaluate Doubletree, an algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Our results show that Doubletree can reduce both types of measurement load on the network dramatically, while permitting discovery of nearly the same set of nodes and links. We then show how to enable efficient communication between monitors through the use of Bloom filters." } @inproceedings{SouleEtAl:sigmetrics05, author = "Augustin Soule and Anukool Lakhina and Nina Taft and Konstantina Papagiannaki and Kave Salamatian and Antonio Nucci and Mark Crovella and Christophe Diot", title = "Traffic Matrices: Balancing Measurements, Inference and Modeling", booktitle = "Proceedings of ACM SIGMETRICS", month = "June", year = 2005, location = "Banff, Canada", pages = "362--373", catID1 = "IM", catID2 = "graphestim", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigm05-trafficmatrices.pdf", abstract = "Traffic matrix estimation is well-studied, but in general has been treated as simply a statistical inference problem. In practice, however, network operators seeking traffic matrix information have a range of options available to them. Operators can measure traffic flows directly; they can perform partial flow measurement, and infer missing data using models; or they can perform no flow measurement and infer traffic matrices directly from link counts. The advent of practical flow measurement makes the study of these tradeoffs more important. In particular, an important question is whether judicious modeling, combined with partial flow measurement, can provide traffic matrix estimates that are signficantly better than previous methods at relatively low cost. In this paper we make a number of contributions toward answering this question. First, we provide a taxonomy of the kinds of models that may make use of partial flow measurement, based on the nature of the measurements used and the spatial, temporal, or spatio-temporal correlation exploited. We then evaluate estimation methods which use each kind of model. In the process we propose and evaluate new methods, and extensions to methods previously proposed. We show that, using such methods, small amounts of traffic flow measurements can have significant impacts on the accuracy of traffic matrix estimation, yielding results much better than previous approaches. We also show that different methods differ in their bias and variance properties, suggesting that different methods may be suited to different applications." } @inproceedings{DonnetEtAl:PAM05, author = "Benoit Donnet and Timur Friedman and Mark Crovella", title = "Improved Algorithms for Network Topology Discovery", booktitle = "Lecture Notes in Computer Science, Proceedings of Passive and Active Measurement Workshop (PAM2005)", month="Mar", year=2005, catID1="IM", catID2="trathome", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/pam05-tr-at-home.pdf", abstract="Topology discovery systems are starting to be introduced in the form of screen saver software that have the potential to be widely deployed. However, little consideration has been given as to how to perform large-scale topology discovery efficiently and in a network-friendly manner. In previous work, we have described how large numbers of traceroute monitors can coordinate their efforts to obtain a map of the network while reducing their impact on routers and end-systems. The key is for them to share information regarding the interfaces that they have discovered. However, such sharing introduces considerable communication overhead. In this paper, we show how we can improve the communication scaling properties through the use of Bloom filters for lossy compression of the interface list. Also, any system in which every monitor traces routes towards every destination has inherent scaling problems. We propose to divide up the monitors into clusters, each cluster focusing on a different destination list." } @inproceedings{ChuaKolaczykCrovella:Infocom05, author = "David B. Chua and Eric D. Kolaczyk and Mark Crovella", title = "Efficient Monitoring of End-to-End Network Properties", booktitle = "Proceedings of Infocom 2005", location = "Miami, FL", month = "Mar", year = 2005, catID1 = "IM", catID2 = "graphestim", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom05-efficient-monitoring.pdf", abstract = "It is often desirable to monitor end-to-end properties, such as loss rates or packet delays, across an entire network. However, active end-to-end measurement in such settings does not scale well, and so complete network-wide measurement quickly becomes infeasible. More efficient measurement strategies are therefore needed. Previous work, examining this problem from a linear algebraic perspective, has shown that for exact recovery of complete end-to-end network properties, the number of paths that need to be monitored can be reduced to approximately the number of links in the network. In this paper we ask whether measurement strategies of even greater efficiency are possible. We recast the problem as one of statistical prediction and show that end-to-end network properties may be accurately predicted in many cases using a significantly smaller set of carefully chosen paths than needed for exact recovery. We formulate a general framework for the prediction problem, propose a simple class of predictors for standard quantities of interest (e.g., averages, totals, differences), and show that linear algebraic methods of subset selection may be used to make effective choice of which paths to measure. We explore the accuracy of the resulting methods both analytically and numerically, in the context of real network topologies of varying size. The feasibility of our methods derives from the low effective rank of routing matrices as encountered in practice, which appears to be a new observation of interest in its own right. The resulting framework, which is quite general, appears to hold promise for studying and improving the efficiency of monitoring of end-to-end-network properties." } @inproceedings{FonsecaCrovella:Infocom05, author = "Nahur Fonseca and Mark Crovella", title = "Bayesian Packet Loss Detection for {TCP}", booktitle = "Proceedings of Infocom 2005", location = "Miami, FL", month = "Mar", year = 2005, catID1 = "IM", catID2 = "methods", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom05-tcpbayes.pdf", abstract = "One of TCP's critical tasks is to determine which packets are lost in the network, as a basis for control actions (flow control and packet retransmission). Modern TCP implementations use two mechanisms: timeout, and fast retransmit. Detection via timeout is necessarily a time-consuming operation; fast retransmit, while much quicker, is only effective for a small fraction of packet losses. In this paper we consider the problem of packet loss detection in TCP more generally. We concentrate on the fact that TCP's control actions are necessarily triggered by inference of packet loss, rather than conclusive knowledge. This suggests that one might analyze TCP's packet loss detection in a standard inferencing framework based on probability of detection and probability of false alarm. This paper makes two contributions to that end: First, we study an example of more general packet loss inference, namely optimal Bayesian packet loss detection based on round trip time. We show that for long-lived flows, it is frequently possible to achieve high detection probability and low false alarm probability based on measured round trip time. Second, we construct an analytic performance model that incorporates general packet loss inference into TCP. We show that for realistic detection and false alarm probabilities (as are achievable via our Bayesian detector) and for moderate packet loss rates, the use of more general packet loss inference in TCP can improve throughput by as much as 25%." } @article{FonsecaAlmeidaCrovella:cacm05, author = "Rodrigo Fonseca and Virg\'{\i}lio Almeida and Mark Crovella", title = "Locality in a Web of Streams", journal = "Communications of the ACM", volume = 48, number = 1, month = "Jan", year = 2005, pages = "82--88", catID1 = "IM", catID2 = "web", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/cacm-web-streams.pdf" } @inproceedings{GueyeZivianiCrovellaFdida:imc2004, author = "Bamba Gueye and Artur Ziviani and Mark Crovella and Serge Fdida", title = "Constraint-Based Geolocation of {Internet} Hosts", booktitle = "Proceedings of the ACM/SIGCOMM Internet Measurement Conference 2004", month = "October", year = "2004", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imc04-constraint-based-geolocation.pdf" } @inproceedings{LakhinaCrovellaDiot:imc2004, author = "Anukool Lakhina and Mark Crovella and Christophe Diot", title = "Characterization of Network-Wide Anomalies in Traffic Flows", booktitle = "Proceedings of the ACM/SIGCOMM Internet Measurement Conference 2004", month = "October", year = "2004", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imc04-characterizing-network-wide.pdf" } @inproceedings{LakhinaCrovellaDiot:sigcomm2004, author = "Anukool Lakhina and Mark Crovella and Christophe Diot", title = "Diagnosing Network-Wide Traffic Anomalies", booktitle = "Proceedings of ACM SIGCOMM 2004", month = "August", year = "2004", location = "Portland, OR", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigc04-network-wide-anomalies.pdf" } @inproceedings{LakhinaEtAl:sigmetrics2004, author = "Anukool Lakhina and Konstantina Papagiannaki and Mark Crovella and Christophe Diot and Eric D. Kolaczyk and Nina Taft", title = "Structural Analysis of Network Traffic Flows", booktitle = "Proceedings of ACM SIGMETRICS / Performance 2004", month = "June", year = "2004", location = "New York, New York", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigm04-structural-flows.pdf" } @inproceedings{TangCrovella:pam2004, author = "Liying Tang and Mark Crovella", title = "Geometric Exploration of the Landmark Selection Problem", booktitle = "Lecture Notes in Computer Science 3015, Proceedings of Passive and Active Measurement Workshop (PAM2004)", month = "April", year = "2004", pages = "63--72", location = "Juan-les-Pins, France", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/pam04-geom-coords.pdf" } @inproceedings{TangCrovella03:imc2003, author = "Liying Tang and Mark Crovella", title = "Virtual Landmarks for the {Internet}", booktitle = "Proceedings of the ACM/SIGCOMM Internet Measurement Conference 2003", month = "October", year = "2003", location = "Miami Beach, Florida", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imc03-coords.pdf" } @article{FonsecaAlmeidaCrovella:cacm03, author = "Rodrigo Fonseca and Virg\'{\i}lio Almeida and Mark Crovella", title = "Locality in a Web of Streams", journal = "Communications of the ACM", month = "to appear", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/cacm-web-streams.pdf", year = 2003 } @inproceedings{FonsecaAlmeidaCrovellaAbrahao:infocom03, author = "Rodrigo Fonseca and Virg\'{\i}lio Almeida and Mark Crovella and Bruno Abrah\~{a}o", title = "On the Intrinsic Locality Properties of Web Reference Streams", booktitle = "Proceedings of IEEE Infocom", year = "2003", month = "April", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom03-weblocality.pdf", abstract = "There has been considerable work done in the study of Web reference streams: sequences of requests for Web objects. In particular, many studies have looked at the locality properties of such streams, because of the impact of locality on the design and performance of caching and prefetching systems. However, a general framework for understanding why reference streams exhibit given locality properties has not yet emerged. In this work we take a first step in this direction, based on viewing the Web as a set of reference streams that are transformed by Web components (clients, servers, and intermediaries). We propose a graph-based framework for describing this collection of streams and components. We identify three basic stream transformations that occur at nodes of the graph: aggregation, disaggregation and filtering, and we show how these transformations can be used to abstract the effects of different Web components on their associated reference streams. This view allows a structured approach to the analysis of why reference streams show given properties at different points in the Web. Applying this approach to the study of locality requires good metrics for locality. These metrics must meet three criteria: 1) they must accurately capture temporal locality; 2) they must be independent of trace artifacts such as trace length; and 3) they must not involve manual procedures or model-based assumptions. We describe two metrics meeting these criteria that each capture a different kind of temporal locality in reference streams. The popularity component of temporal locality is captured by entropy, while the correlation component is captured by interreference coefficient of variation. We argue that these metrics are more natural and more useful than previously proposed metrics for temporal locality. We use this framework to analyze a diverse set of Web reference traces. We find that this framework can shed light on how and why locality properties vary across different locations in the Web topology. For example, we find that filtering and aggregation have opposing effects onthe popularity component of the temporal locality, which helps to explain why multilevel caching can be effective in the Web. Furthermore, we find that all transformations tend to diminish the correlation component of temporal locality, which has implications for the utility of different cache replacement policies at different points in the Web." } @inproceedings{CrovellaKolaczyk:infocom03, author = "Mark Crovella and Eric Kolaczyk", title = "Graph Wavelets for Spatial Traffic Analysis", booktitle = "Proceedings of IEEE Infocom", year = "2003", month = "April", location = "San Francisco, CA", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom03-graph-wavelets.pdf", abstract = "A number of problems in network operations and engineering call for new methods of traffic analysis. While most existing traffic analysis methods are fundamentally temporal, there is a clear need for the analysis of traffic across multiple network links --- that is, for spatial traffic analysis. In this paper we give examples of problems that can be addressed via spatial traffic analysis. We then propose a formal approach to spatial traffic analysis based on the wavelet transform. Our approach (graph wavelets) generalizes the traditional wavelet transform so that it can be applied to data elements connected via an arbitrary graph topology. We explore the necessary and desirable properties of this approach and consider some of its possible realizations. We then apply graph wavelets to measurements from an operating network. Our results show that graph wavelets are very useful for our motivating problems; for example, they can be used to form highly summarized views of an entire network's traffic load, to gain insight into a network's global traffic response to a link failure, and to localize the extent of a failure event within the network." } @inproceedings{GuoCrovellaMatta:mascots01, author = "Liang Guo and Mark Crovella and Ibrahim Matta", title = {{How does TCP Generate Pseudo-Self-Similarity?}}, booktitle = "Proceedings of the International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunications Systems~-~{MASCOTS~'01}", address = "Cincinnati, Ohio", month = "August", year = 2001, keywords = {Congestion Control, Long-Range Dependence, Self-Similarity}, url = "http://www.cs.bu.edu/faculty/matta/Papers/mascots01-tcp-pss.ps", abstract ={Long-range dependence has been observed in many recent Internet traffic measurements. In addition, some recent studies have shown that under certain network conditions, TCP itself can produce traffic that exhibits dependence over limited timescales, even in the absence of higher-level variability. In this paper, we use a simple Markovian model to argue that when the loss rate is relatively high, TCP's adaptive congestion control mechanism indeed generates traffic with OFF periods exhibiting power-law shape over several timescales and thus introduces pseudo-long-range dependence into the overall traffic. Moreover, we observe that more variable initial retransmission timeout values for different packets introduces more variable packet inter-arrival times, which increases the burstiness of the overall traffic. We can thus explain why a single TCP connection can produce a time-series that can be misidentified as self-similar using standard tests.} } @inproceedings(LiuCrovella:imw01, author = "Jun Liu and Mark E. Crovella", title = "Using Loss Pairs to Discover Network Properties", booktitle = "Proceedings of the ACM SIGCOMM Internet Measurement Workshop 2001", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/imw-losspairs.pdf", month = "Nov", year = "2001" ) @article(BarfordCrovella:ton01, author = "Paul Barford and Mark E. Crovella", title = "Critical Path Analysis of {TCP} Connections", journal = "IEEE/ACM Transactions on Networking", year = "2001", VOLUME = "9", number = "3", pages = "238--238", month = "June" ) @inproceedings(Crovella:LNCS00, author = "Mark E. Crovella", title = "Performance Evaluation with Heavy Tailed Distributions", booktitle = "Lecture Notes in Computer Science 1786", pages = "1--9", month = "March", year = "2000" ) @inproceedings(BarfordCrovella:sigcomm00, author = "Paul Barford and Mark E. Crovella", title = "Critical Path Analysis of {TCP} Connections", booktitle = "Proceedings of the 2000 ACM SIGCOMM Conference", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigcomm00.ps", pages = "127--138", year = "2000", annote = "Also appeared by invitation as ``An\'{a}lisis de secuencia cr\'{\i}tica de transacciones TCP'' in {\em Proceedings of SIGCOMM Latin America,\/} San Antonio de Bel\'{e}n, Costa Rica, April 2001." ) @inproceedings(CrovellaFrangiosoHarcholBalter:usenix99, author = "Mark E. Crovella and Robert Frangioso and Mor Harchol-Balter", title = "Connection Scheduling in {W}eb Servers", booktitle = "1999 USENIX Symposium on Internet Technologies and Systems (USITS '99)", URL = "http://www.cs.bu.edu/techreports/99-003-connection-scheduling-in-web-servers.ps.Z", year = "1999" ) @article(BarfordCrovella:per99, author = "Paul Barford and Mark E. Crovella", title = "Measuring {W}eb Performance in the Wide Area", journal = "Performance Evaluation Review", volume = "Special Issue on Network Traffic Measurement and Workload Characterization", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/wawm-per.ps", month = "August", year = 1999 ) @article(CarterCrovella:cn99, author = "Robert L. Carter and Mark E. Crovella", title = "On the Network Impact of Dynamic Server Selection", journal = "Computer Networks", volume = 31, number = "(23-24)", year = 1999, pages = "2529--2558", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/dss-journal.ps" ) @article(HarcholBalterCrovellaMurta:jpdc99, author = "Mor Harchol-Balter and Mark E. Crovella and Cristina D. Murta", title = "On Choosing a Task Assignment Policy for a Distributed Server System", journal = "Journal of Parallel and Distributed Computing", volume = "Special Issue on Software Support for Distributed Computing", month = "September", year = 1999, url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/tools98.ps" ) @incollection(Crovella:whitebook99, author = "Mark E. Crovella", title = "Performance Characteristics of the {W}orld {W}ide {W}eb", booktitle = "Whitebook on Performance Evaluation", editor = {G\"{u}nter Haring and Martin Reiser and Christophe Lindemann}, publisher = "Springer-Verlag", year = "1999" ) @incollection(CrovellaLipsky:ssbook99, author = "Mark E. Crovella and Lester Lipsky", title = "Simulations with Heavy-Tailed Workloads", booktitle = "Self-Similar Network Traffic and Performance Evaluation", editor = "Kihong Park and Walter Willinger", publisher = "Wiley / Wiley Interscience", address = "New York", year = "1999" ) @incollection(ParkKimCrovella:ssbook99, author = "Kihong Park and Gi Tae Kim and Mark E. Crovella", title = "The Protocol Stack and its Modulation Effect on Self-Similar Traffic", booktitle = "Self-Similar Network Traffic and Performance Evaluation", publisher = "Wiley / Wiley Interscience", editor = "Kihong Park and Walter Willinger", address = "New York", year = "1999" ) @inproceedings(BarfordCrovella:sigmetrics99, author = "Paul Barford and Mark E. Crovella", title = "A Performance Evaluation of Hyper Text Transfer Protocols", booktitle = "Proceedings of ACM SIGMETRICS '99", year = "1999", month = "May", pages = "188--197", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/sigm99.ps" ) @article(HarcholBalterCrovellaMurta:ptools98, author = "Mor Harchol-Balter and Mark E. Crovella and Cristina D. Murta", title = "On Choosing a Task Assignment Policy for a Distributed Server System", journal = "Proceedings of Performance Tools '98. Lecture Notes in Computer Science", volume = "1469", pages = "231--242", year = "1998", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/tools98.ps" ) @article(CrovellaTaqqu:mcap99, author = "Mark E. Crovella and Murad S. Taqqu", title = "Estimating the Heavy Tail Index from Scaling Properties", journal = "Methodology and Computing in Applied Probability", volume = 1, number = 1, month = "July", year = "1999", pages = "55--79", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/aest.ps" ) @inproceedings(CrovellaHarcholBalterMurta:sigmetrics98, author = "Mark E. Crovella and Mor Harchol-Balter and Cristina Duarte Murta", title = "Task Assignment in a Distributed System: Improving Performance by Unbalancing Load", booktitle = "Proceedings of SIGMETRICS '98 (poster paper)", year = "1998", month = "July" ) @inproceedings(BarfordCrovella:sigmetrics98, author = "Paul Barford and Mark E. Crovella", title = "Generating Representative {W}eb Workloads for Network and Server Performance Evaluation", booktitle = "Proceedings of Performance '98/SIGMETRICS '98", pages = "151--160", year = "1998", month = "July", url = "http://cs-www.bu.edu/faculty/crovella/paper-archive/sigm98-surge.ps" ) @inproceedings(CrovellaBarford:infocom98, author = "Mark E. Crovella and Paul Barford", title = "The Network Effects of Prefetching", booktitle = "Proceedings of Infocom '98", pages = "1232--1240", month = "April", year = "1998" ) @article(CrovellaBestavros:ton97, author = "Mark E. Crovella and Azer Bestavros", title = "Self-Similarity in {W}orld {W}ide {W}eb Traffic: Evidence and Possible Causes", journal = "IEEE/ACM Transactions on Networking", year = "1997", VOLUME = "5", number = "6", pages = "835--846", month = "December" ) @inproceedings(CrovellaLipsky:wsc97, author = "Mark E. Crovella and Lester Lipsky", title = "Long-Lasting Transient Conditions in Simulations with Heavy-Tailed Workloads", booktitle = "Proceedings of the 1997 Winter Simulation Conference", year = "1997", pages = "1005--1012", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/wsc97.ps" ) @inproceedings(FioriniLipskyCrovella:pdcs97, author = "Pierre Fiorini and Lester Lipsky and Mark Crovella", title = "Consequences of Ignoring Self-Similar Data Traffic In Communications Modeling", booktitle = "Proceedings of Tenth International Conference on Parallel and Distributed Computing Systems (PDCS-97)", year = "1997", month = "October", pages = "322--327", url = "http://www.cs.bu.edu/faculty/crovella/paper-archive/pt-fiorini-lipsky.ps" ) @inproceedings(ParkKimCrovella:spie97, author = "Kihong Park and Gitae Kim and Mark E. Crovella", title = "On the Effect of Traffic Self-Similarity on Network Performance", booktitle = "Proceedings of SPIE International Conference on Performance and Control of Network Systems", year = "1997", month = "November", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/TR-park-kim.ps" ) @incollection(CrovellaTaqquBestavros:book98, author = "Mark E. Crovella and Murad S. Taqqu and Azer Bestavros", title = "Heavy-Tailed Probability Distributions in the {W}orld {W}ide {W}eb", booktitle = "A Practical Guide To Heavy Tails", publisher = "Chapman \& Hall", address = "New York", year = "1998", chapter = 1, editor = "Robert J. Adler and Raisa E. Feldman and Murad S. Taqqu", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/web-tails.ps", pages = "3--26" ) @inproceedings(CarterCrovella97:infocom97, author = "Robert L. Carter and Mark E. Crovella", title = "Server Selection Using Dynamic Path Characterization in Wide Area Networks", booktitle = "Proceedings of Infocom '97, the Sixteenth Annual Joint Conference of the IEEE Computer and Communication Societies", month = "April", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom97.ps", year = "1997" ) @article(CarterCrovella:pe98, author = "Robert L. Carter and Mark E. Crovella", title = "Measuring Bottleneck Link Speed in Packet Switched Networks", journal = "Performance Evaluation", year = "1996", VOLUME = "27\&28", pages = "297--318", URL = "http://cs-www.bu.edu/techreports/96-006-measuring-bottleneck-link.ps.Z" ) @inproceedings(CarterCrovella:peformance96, author = "Robert L. Carter and Mark E. Crovella", title = "Measuring Bottleneck Link Speed in Packet Switched Networks", booktitle = "PERFORMANCE '96, the International Conference on Performance Theory, Measurement and Evaluation of Computer and Communication Systems", month = "October", URL = "http://cs-www.bu.edu/techreports/96-006-measuring-bottleneck-link.ps.Z", year = "1996" ) @inproceedings(ParkKimCrovella:icnp96, author = "Kihong Park and Gi Tae Kim and Mark E. Crovella", title = "On the Relationship Between File Sizes, Transport Protocols, and Self-Similar Network Traffic", booktitle = "Proceedings of the Fourth International Conference on Network Protocols (ICNP'96)", month = "October", pages = "171--180", URL = "http://cs-www.bu.edu/faculty/crovella/paper-archive/icnp96.ps", year = "1996" ) @inproceedings(CrovellaBestavros:sigmetrics96, author = "Mark E. Crovella and Azer Bestavros", title = "Self-Similarity in {W}orld {W}ide {W}eb Traffic: Evidence and Possible Causes", booktitle = "Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems", pages = "160--169", year = "1996", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/self-sim/sigmetrics-version.ps", month = "May" ) @inproceedings(CrovellaCarter:hpcs95, author = "Mark E. Crovella and Robert L. Carter", title = "Dynamic Server Selection in the {I}nternet", booktitle = "Proceedings of the Third IEEE Workshop on the Architecture and Implementation of High Performance Communication Subsystems (HPCS'95)", year = "1995", URL = "http://www.cs.bu.edu/faculty/crovella/paper-archive/hpcs95/paper-final.ps", month = "August" ) @INPROCEEDINGS{EspteinMattarMatta:ICNP09, AUTHOR = {Sam Epstein and Karim Mattar and Ibrahim Matta}, TITLE = {{Principles of Safe Policy Routing Dynamics}}, BOOKTITLE = {{Proceedings of the 17th IEEE International Conference on Network Protocols (ICNP'09)}}, YEAR = {2009}, address = "Princeton, NJ", month = "October" } @INPROCEEDINGS{MattarMattaX:NetDB09, AUTHOR = {Karim Mattar and Ibrahim Matta and John Day and Vatche Ishakian and Gonca Gursun}, TITLE = {{Declarative Transport: A Customizable Transport Service for the Future Internet}}, BOOKTITLE = {{Proceedings of the $5^{th}$ International Workshop on Networking Meets Databases (NetDB 2009), co-located with SOSP 2009}}, YEAR = {2009}, address = {Big Sky, MT}, month = {October} } @INPROCEEDINGS{EspositoMatta:GC09, AUTHOR = "Flavio Esposito and Ibrahim Matta", TITLE = {{PreDA: Predicate Routing for DTN Architectures over MANET}}, BOOKTITLE = {{Proceedings of the IEEE Globecom 2009 Next-Generation Networking and Internet Symposium (GC'09 NGNI)}}, YEAR = "2009", address = "Honolulu, Hawaii", month = "December" } @INPROCEEDINGS{EspositoMattaX:NCA09, AUTHOR = "Flavio Esposito and Ibrahim Matta and Pietro Michiardi and Nobuyuki Mitsutake and Damiano Carra", TITLE = {{Seed Scheduling for Peer-to-Peer Networks}}, BOOKTITLE = {{Proceedings of the Eighth IEEE International Symposium on Network Computing and Applications (IEEE NCA09)}}, YEAR = "2009", address = "Cambridge, MA", month = "July" } @INPROCEEDINGS{DayMattaMattar:rearch08, AUTHOR = "John Day and Ibrahim Matta and Karim Mattar", TITLE = {{``Networking is {IPC}": {A} Guiding Principle to a Better Internet}}, BOOKTITLE = {{Proceedings of ReArch'08 - Re-Architecting the Internet}}, YEAR = "2008", address = "Madrid, SPAIN", month = "December", organization = {{Co-located with ACM CoNEXT 2008}}, url = "http://www.cs.bu.edu/fac/matta/Papers/ipc-rearch08.pdf", abstract = "This position paper outlines a new network architecture that is based on the fundamental principle that \emph{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 \emph{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)." } @inproceedings{AggradiEspositoMatta:chants08, author = "Gabriele Ferrari Aggradi and Flavio Esposito and Ibrahim Matta", title = {{Supporting Predicate Routing in DTN over MANET}}, booktitle={{Proceedings of ACM MobiCom Workshop on Challenged Networks (CHANTS 2008)}}, address={San Francisco, CA}, keywords={}, note = {{\bf Demo}}, month={September}, year= 2008, url = "http://www.cs.bu.edu/fac/matta/Papers/chants2de-matta.pdf", 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. " } @inproceedings{RigaMattaX:conext07, author = "Niky Riga and Ibrahim Matta and Alberto Medina and Craig Partridge and Jason Redi", title = {{{JTP}: An Energy-conscious Transport Protocol for Multi-hop Wireless Networks}}, booktitle={{Proceedings of CoNEXT Conference}}, address={New York, NY}, keywords={}, month={December}, year= 2007, url = "http://www.cs.bu.edu/fac/matta/Papers/jtp-final-camera-conext07.pdf", 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." } @inproceedings{RigaMattaBestavros:globecom-asns07, author = "Niky Riga and Ibrahim Matta and Azer Bestavros", title = {{A Geometric Approach to Slot Alignment in Wireless Sensor Networks}}, booktitle={{Proceedings of the IEEE Global Telecommunications Conference (Globecom'07) Ad-hoc and Sensor Networking Symposium }}, address={Washington, DC}, keywords={}, month={November}, year=2007, url = "http://www.cs.bu.edu/faculty/matta/Papers/asns-globecom07.pdf", 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. "} @inproceedings{YilmazMatta:net07, author = {Selma Yilmaz and Ibrahim Matta}, title = {{An Adaptive Management Approach to Resolving Policy Conflicts}}, booktitle = {Proceedings of IFIP Networking 2007}, address = {Atlanta, Georgia}, month = {{May}}, year = {2007}, url = "http://www.cs.bu.edu/faculty/matta/Papers/net07.pdf", 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. "} @inproceedings{MattarSridharanZangMattaBestavros:pam2007, author = {Karim Mattar and Ashwin Sridharan and Hui Zang and Ibrahim Matta and Azer Bestavros}, title = {{{TCP} over CDMA2000 Networks: {A} Cross-Layer Measurement Study}}, booktitle = {Proceedings of the $8^{th}$ Passive and Active Measurement Conference (PAM)}, address = {{Louvain-la-neuve, Belgium}}, year = {2007}, url = "http://www.cs.bu.edu/faculty/matta/Papers/pam07.pdf", 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 {\em RF} and {\em 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." } @inproceedings{Smaragdakis:networking2006, author = {Georgios Smaragdakis and Nikolaos Laoutaris and Ibrahim Matta and Azer Bestavros and Ioannis Stavrakakis}, title = {{A Feedback Control Approach to Mitigating Mistreatment in Distributed Caching Groups}}, booktitle = {Proceedings of IFIP Networking 2006}, year = {2006}, month = {May}, address = {Coimbra, Portugal}, url = "http://www.cs.bu.edu/faculty/matta/Papers/Networking06.pdf", 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 stre ams 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. " } @inproceedings{RigaMedinaMattaX:sigcomm05, author = {Niky Riga and Alberto Medina and Ibrahim Matta and Craig Partridge and Jason Redi and Isidro Castineyra}, title = {{Transport Services for Energy Constrained Environments}}, booktitle={{Proceedings of ACM SIGCOMM'05}}, address={Philadelphia, PA}, keywords={}, month={August}, year=2005, note ="Work-in-progress Session", url = "http://www.cs.bu.edu/faculty/matta/Papers/sigcomm05.pdf", 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 ef- ficiency 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. " } @Article{GolmieMatta:compcomm05-Editorial, author = "Nada Golmie and Ibrahim Matta", title = {{Guest Editorial}}, journal = {{Elsevier Computer Communications Journal---Special Issue on Applications and Services in Wireless Networks}}, month = "September", volume = "28", number = "14", year = 2005, url = "http://www.cs.bu.edu/faculty/matta/Papers/editorial-cc05.pdf" } @article{MorcosMattaBestavros:sigbed05, author = "Hany Morcos and Ibrahim Matta and Azer Bestavros", title = {{M2RC: Multiplicative-increase/additive-decrease Multipath Routing Control for Wireless Sensor Networks}}, journal={{SIGBED Review---Special Issue on the Best of SenSys 2004 Work-in-Progress}}, volume=2, number=1, month={January}, year=2005, url = "http://www.cs.virginia.edu/sigbed/", 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 M$^2$RC. M$^2$RC has two phases: mesh establishment phase and data forwarding phase. In the first phase, M$^2$RC establishes the routing state to enable multipath data forwarding. In the second phase, M$^2$RC forwards data packets from the source to the sink. Targeting hop-by-hop reliability, an M$^2$RC forwarding node waits for an acknowledgement (ACK) that its packets were correctly received at the next neighbor. Based on this feedback, an M$^2$RC node applies multiplicative-increase/additive-decrease (MIAD) to control the number of neighbors targeted by its packet broadcast. We simulated M$^2$RC in the ns-2 simulator [4] and compared it to GRAB [1], Max-power, and Min-power routing schemes. Our simulations show that M$^2$RC 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." } @misc{StavrakakisMattaSmirnov:NeXtworking2003-Editorial, author = "Ioannis Stavrakakis and Ibrahim Matta and Michael Smirnov (editors)", title = {{Report on the First COST (EU)-NSF (USA) Workshop on Exchanges and Trends in Networking}}, howpublished = {{July 2004}} } @inproceedings{MorcosMattaBestavros:icenco04, author = "Hany Morcos and Ibrahim Matta and Azer Bestavros", title = {{BiPAR: A Bimodal Power-Aware Routing Protocol for Wireless Sensor Networks}}, booktitle={{Proceedings of the First International Computer Engineering Conference (ICENCO 2004)}}, address={Cairo, Egypt}, keywords={}, month={December}, year=2004, url = "http://www.cs.bu.edu/faculty/matta/Papers/bipar-icenco04.pdf", abstract="" } @inproceedings{YilmazMatta:ccn04, author = "Selma Yilmaz and Ibrahim Matta", title = {{A Randomized Solution to BGP Divergence}}, booktitle={{Proceedings of the 2nd IASTED International Conference on Communication and Computer Networks (CCN'04)}}, address={Cambridge, Massachusetts}, keywords={}, month={November}, year=2004, url = "http://www.cs.bu.edu/faculty/matta/Papers/", abstract="" } @inproceedings{BarmanSmaragdakisMatta:globecom-gi04, author = "Dhiman Barman and Georgios Smaragdakis and Ibrahim Matta", title = {{The Effect of Router Buffer Size on HighSpeed TCP Performance}}, booktitle={{Proceedings of Global Internet and Next Generation Networks Symposium, IEEE Global Telecommunications Conference (Globecom'04) }}, address={Dallas, TX}, keywords={}, month={December}, year=2004, url = "http://www.cs.bu.edu/faculty/matta/Papers/", abstract="" } @inproceedings{BarmanMatta:wiopt04, author = "Dhiman Barman and Ibrahim Matta", title = {{Model-based Loss Inference by TCP over Heterogeneous Networks}}, booktitle={{Proceedings of WiOpt'04: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks}}, address={University of Cambridge, UK}, keywords={}, month={March}, year=2004, url = "http://www.cs.bu.edu/faculty/matta/Papers/wiopt04.pdf", 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 {\em 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 {\em 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. }} @inproceedings{DiamantVeytserMattaX:camad04, author = "Gali Diamant and Leonid Veytser and Ibrahim Matta and Azer Bestavros and Mina Guirguis and Liang Guo and Yuting Zhang and Sean Chen", title = {{itmBench: Generalized API for Internet Traffic Managers}}, booktitle = "{Proceedings of the 10th IEEE Workshop on Computer-Aided Modeling, Analysis and Design of Communication Links and Networks (CAMAD '04)}", month = "December", address = "Dallas, TX (in conjunction with Globecom 2004)", year = 2004, url = "", abstract = " Internet Traffic Managers (ITMs) are special machines placed at strategic places in the Internet. {\em 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 {\em 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 {\em 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 {\em itmBench} Linux-based prototype is free software and can be obtained from {\tt http://www.cs.bu.edu/groups/itm/}. " } @inproceedings{SmaragdakisMattaBestavros:sanpa04, author = "Georgios Smaragdakis and Ibrahim Matta and Azer Bestavros", title = {{SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks}}, booktitle = "{Proceedings of the Second International Workshop on Sensor and Actuator Network Protocols and Applications (SANPA '04)}", month = "August", address = "Boston, MA (in conjunction with Mobiquitous 2004)", year = 2004, url = "http://www.cs.bu.edu/faculty/matta/Papers/sep-sanpa04.pdf", 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 {\em 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. "} @inproceedings{RigaMattaBestavros:sanpa04, author = "Niky Riga and Ibrahim Matta and Azer Bestavros", title = {{DIP: Density Inference Protocol for wireless sensor networks and its application to density-unbiased statistics}}, booktitle = "{Proceedings of the Second International Workshop on Sensor and Actuator Network Protocols and Applications (SANPA '04)}", month = "August", address = "Boston, MA (in conjunction with Mobiquitous 2004)", year = 2004, url = "http://www.cs.bu.edu/faculty/matta/Papers/dip-sanpa04.pdf", 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 {\em 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. " } @inproceedings{ErramilliMattaBestavros:secon04, author = "Vijay Erramilli and Ibrahim Matta and Azer Bestavros", title = {{On the Interaction between Data Aggregation and Topology Control in Wireless Sensor Networks}}, booktitle = "{Proceedings of the First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (IEEE SECON 2004)}", month = "October", address = "Santa Clara, CA", year = 2004, url = "http://www.cs.bu.edu/faculty/matta/Papers/", 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. " } @inproceedings{MorcosMattaBestavros:sensys04, author = "Hany Morcos and Ibrahim Matta and Azer Bestavros", title = {{M2RC: Multiplicative-increase/additive-decrease Multipath Routing Control for Wireless Sensor Networks}}, booktitle = "{Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (ACM SenSys '04)}", month = "November", address = "Baltimore, Maryland", year = 2004, note = "Poster", url = "http://www.cs.bu.edu/faculty/matta/Papers/m2rc-sensys04.pdf", abstract = "" } @inproceedings{BarmanMattaAltmanAzouzi:WWIC04, author = "Dhiman Barman and Ibrahim Matta and Eitan Altman and Rachid El Azouzi", title = {{TCP Optimization through FEC, ARQ and Transmission Power Tradeoffs}}, booktitle = {Proceedings of WWIC 2004: The 2nd International Conference on Wired/Wireless Internet Communications}, year = 2004, month = "February", address = "Frankfurt (Oder), Germany", url = "http://www.cs.bu.edu/faculty/matta/Papers/wwic04.pdf", 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." } %} @article{HassanKrunzMatta:ToWC02, author={Mohamed Hassan and Marwan Krunz and Ibrahim Matta}, title= {{Markov-based Channel Characterization for Tractable Performance Analysis in Wireless Packet Networks}}, journal = "{IEEE Transactions on Wireless Communications}", comment = "Accepted November 2002. Under minor revision", year = 2003, note = "To appear", url = "http://www.cs.bu.edu/faculty/matta/Papers/towc03.ps", abstract={} } @article{JinGuoMattaBestavros:ton02, author={Shudong Jin and Liang Guo and Ibrahim Matta and Azer Bestavros}, title= {{A Spectrum of TCP-friendly Window-based Congestion Control Algorithms}}, journal={{IEEE/ACM Transactions on Networking}}, address={}, keywords={Congestion Control, TCP-friendliness, TCP-compatibility, Fairness, Transient Behavior}, volume = "11", number = "3", month = "June", year= "2003", comment = "Accepted May 2002 by Vern Paxon", url = "http://www.cs.bu.edu/faculty/matta/Papers/ton02.ps", abstract={} } @article{RatnamMatta:IJCS02, author={Karu Ratnam and Ibrahim Matta}, title= {{WTCP: An Efficient Mechanism for Improving Wireless Access to TCP Services}}, journal = "{International Journal of Communication Systems --- Special Issue on Wireless Access to the Global Internet: Mobile Radio Networks and Satellite Systems}", volume = "16", pages = "47--62", year = "2003", comment = "Accepted September 2002.", url = "http://www.cs.bu.edu/faculty/matta/Papers/ijcs02.ps", abstract={} } @article{GuoMatta:CN02, author={Liang Guo and Ibrahim Matta}, title= {{Search Space Reduction in {QoS} Routing}}, journal = "{Computer Networks}", volume = "41", number = "1", month = "January", year = "2003", comment = "Accepted May 2002. To appear", url = "http://www.cs.bu.edu/faculty/matta/Papers/comnet02b.ps", abstract={} } %} @inproceedings{LiuMattaCrovella:WiOpt03, author = "Jun Liu and Ibrahim Matta and Mark Crovella", title = {{End-to-end Inference of Loss Nature in Hybrid Wired/Wireless Environment}}, booktitle={{Proceedings of WiOpt'03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks}}, address={INRIA Sophia-Antipolis, France}, keywords={}, month={March}, year=2003, url = "http://www.cs.bu.edu/faculty/matta/Papers/wiopt03.ps", abstract={} } @Article{KrunzMatta:comnet02, author = "Marwan Krunz and Ibrahim Matta", title = {{Analytical Investigation of the Bias Effect in Variance-Type Estimators for Inference of Long-Range Dependence}}, journal = "Computer Networks -- Special Issue on Advances in Modeling and Engineering of Long-Range Dependent Traffic", month = "October", volume = "40", number = "3", pages = "445-458", year = "2002", comment = "Accepted March 2002. Guest Editors: M. Devetsikiotis and N.L.S. da Fonseca", keywords= {Long-Range Dependence}, url = "http://www.cs.bu.edu/faculty/matta/Papers/comnet02.ps" } @inproceedings{BarmanMatta:icnp02, author = "Dhiman Barman and Ibrahim Matta", title = {{Effectiveness of Loss Labeling in Improving TCP Performance in Wired/Wireless Networks}}, booktitle={{Proceedings of ICNP'2002: The 10th IEEE International Conference on Network Protocols}}, address={Paris, France}, keywords={}, month={November}, year=2002, url = "http://www.cs.bu.edu/faculty/matta/Papers/icnp02.ps", abstract={} } %} %} @Article{KrunzMatta:ieeecomm02-Editorial, author = "Marwan Krunz and Ibrahim Matta", title = {{Guest Editorial}}, journal = {{IEEE Communications Magazine---Feature Topic on Internet Quality of Service Routing}}, month = "June", volume = "40", number = "6", year = 2002, url = "http://www.cs.bu.edu/faculty/matta/Papers/editorial-ieeecomm02.pdf" } @inproceedings{GuoMatta:spie02, author={Liang Guo and Ibrahim Matta}, title= {{Differentiated Control of Web Traffic: A Numerical Analysis}}, booktitle={{Proceedings of SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks}}, address={Boston, MA}, keywords={Heavy-tailed Distributions, TCP Congestion Control, Traffic Engineering}, month={August}, year=2002, url = "http://www.cs.bu.edu/faculty/matta/Papers/spie02-web.ps", abstract={} } @inproceedings{YilmazMatta:spie02, author={Selma Yilmaz and Ibrahim Matta}, title= {{On the Scalability-Performance Tradeoffs in MPLS and IP Routing}}, booktitle={{Proceedings of SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks}}, address={Boston, MA}, keywords={Multi-Protocol Label Switching, IP Routing, Constraint-Based Routing, Multicommodity Flow Algorithms, Simulation}, month={August}, year=2002, url = "http://www.cs.bu.edu/faculty/matta/Papers/spie02-routing.ps", abstract={} } @inproceedings{GuoMatta:sigmetrics02, author={Liang Guo and Ibrahim Matta}, title= {{Scheduling Flows with Unknown Sizes: An Approximate Analysis}}, booktitle={{Proceedings of ACM SIGMETRICS~'2002}}, address={Marina Del Rey, CA}, keywords={Traffic Engineering, Congestion Control, TCP Performance, Fairness}, month={June}, year=2002, note = "Poster", url = "http://www.cs.bu.edu/faculty/matta/Papers/sigmetrics02.ps", abstract={} } @Article{TsaoussidisMatta:jwcmc01-Editorial, author = "Vassilis Tsaoussidis and Ibrahim Matta", title = {{Guest Editorial}}, journal = "Journal of Wireless Communications and Mobile Computing -- Special Issue on Reliable Transport Protocols for Mobile Computing", month = "February", volume = "2", number = "1", year = 2002, keywords= {TCP, congestion control, wireless links, mobile computing, energy efficiency}, url = "http://www.cs.bu.edu/faculty/matta/Papers/editorial-jwcmc02.html" } @Article{TsaoussidisMatta:jwcmc01, author = "Vassilis Tsaoussidis and Ibrahim Matta", title = {{Open Issues on TCP for Mobile Computing}}, journal = "Journal of Wireless Communications and Mobile Computing -- Special Issue on Reliable Transport Protocols for Mobile Computing", month = "February", volume = "2", number = "1", year = 2002, keywords= {TCP, congestion control, wireless links, mobile computing, energy efficiency}, url = "http://www.cs.bu.edu/faculty/matta/Papers/jwcmc01.ps" } @inproceedings{GuoMatta:icnp01, author={Liang Guo and Ibrahim Matta}, title= {{The War between Mice and Elephants}}, booktitle={{Proceedings of ICNP'2001: The 9th IEEE International Conference on Network Protocols}}, address={Riverside, CA}, keywords={Traffic Engineering, Congestion Control, TCP Performance, Fairness}, month={November}, year=2001, url = "http://www.cs.bu.edu/faculty/matta/Papers/icnp01-war.ps", abstract={} } @inproceedings{JinGuoMattaBestavros:icnp01, author={Shudong Jin and Liang Guo and Ibrahim Matta and Azer Bestavros}, title= {{TCP friendly SIMD Congestion Control and Its Convergence Behavior}}, booktitle={{Proceedings of ICNP'2001: The 9th IEEE International Conference on Network Protocols}}, address={Riverside, CA}, keywords={Congestion Control, TCP-friendliness, Fairness, Convergence}, month={November}, year=2001, url = "http://www.cs.bu.edu/faculty/matta/Papers/icnp01-simd.ps", abstract={} } %has been observed in many recent Internet traffic measurements. %In addition, some recent studies have shown that under certain %network conditions, TCP itself can produce traffic %that exhibits dependence over %limited timescales, even in the absence of higher-level %variability. %In this paper, we use a simple Markovian model to argue that %when the loss rate %is relatively high, %TCP's adaptive congestion control mechanism indeed generates %traffic with OFF periods exhibiting power-law shape over %several timescales and thus %introduces pseudo-long-range dependence into the overall traffic. %Moreover, %we observe that more variable initial retransmission timeout values %for different packets introduces %more variable packet inter-arrival times, %which increases the burstiness of the %overall traffic. %We can thus explain why a single TCP connection can produce %a time-series that can be misidentified %as self-similar using standard tests.} %} @inproceedings{MedinaLakhinaMattaByers:mascots2001, author = "Alberto Medina and Anukool Lakhina and Ibrahim Matta and John Byers", title = {{BRITE: An Approach to Universal Topology Generation}}, booktitle = "Proceedings of {MASCOTS~'01}: The International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems", address = "Cincinnati, Ohio", month = "August", year = 2001, keywords = {Topology generation, graph models, network topology, growth models, annotated topologies, simulation environments.}, url = "http://www.cs.bu.edu/faculty/matta/Papers/mascots01-brite-user.ps", abstract ={ Effective engineering of the Internet is predicated upon a detailed understanding of issues such as the large-scale structure of its underlying physical topology, the manner in which it evolves over time, and the way in which its constituent components contribute to its overall function. Unfortunately, developing a deep understanding of these issues has proven to be a challenging task, since it in turn involves solving difficult problems such as mapping the actual topology, characterizing it, and developing models that capture its emergent behavior. Consequently, even though there are a number of topology models, it is an open question as to how {\em representative} the generated topologies they generate are of the actual Internet. Our goal is to produce a topology generation framework which improves the state of the art and is based on the design principles of representativeness, inclusiveness, and interoperability. {\em Representativeness} leads to synthetic topologies that accurately reflect many aspects of the actual Internet topology (e.g. hierarchical structure, node degree distribution, etc.). {\em Inclusiveness} combines the strengths of as many generation models as possible in a single generation tool. {\em Interoperability} provides interfaces to widely-used simulation applications such as {\em ns} and {\em SSF} and visualization tools like {\em otter}. We call such a tool a {\em universal topology generator}.} } @inproceedings{YilmazMatta:mascots2001, author = "Selma Yilmaz and Ibrahim Matta", title = {{On Class-Based Isolation of UDP, Short-Lived and Long-Lived TCP Flows }}, booktitle = "Proceedings of {MASCOTS~'01}: The International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems", address = "Cincinnati, Ohio", month = "August", year = 2001, keywords = {Class-based isolation vs. sharing, packet dropping (RED, Tail-drop), fairness, queuing analysis }, url = "http://www.cs.bu.edu/faculty/matta/Papers/mascots01-cbi.ps", abstract ={ The congestion control mechanisms of TCP make it vulnerable in an environment where flows with different congestion-sensitivity compete for scarce resources. With the increasing amount of unresponsive UDP traffic in today's Internet, new mechanisms are needed to enforce fairness in the core of the network. We propose a scalable Diffserv-like architecture, where flows with different characteristics are classified into separate service queues at the routers. Such class-based isolation provides protection so that flows with different characteristics do not negatively impact one another. In this study, we examine different aspects of UDP and TCP interaction and possible gains from segregating UDP and TCP into different classes. We also investigate the utility of further segregating TCP flows into two classes, which are class of short and class of long flows. Results are obtained analytically for both Tail-drop and Random Early Drop (RED) routers. Class-based isolation have the following salient features: (1) better fairness, (2) improved predictability for all kinds of flows, (3) lower transmission delay for delay-sensitive flows, and (4) better control over Quality of Service (QoS) of a particular traffic type.} } @Article{RatnamMattaRangarajan:JOIN01, author = "Karunaharan Ratnam and Ibrahim Matta and Sampath Rangarajan", title = {{A Fully Distributed Location Management Scheme for Large PCS Networks}}, journal = "Journal of Interconnection Networks - Special Issue on Performance Analyis and Evaluation of Wireless and Mobile Networks", month = "March", volume = "2", number = "1", pages = "85--102", year = 2001, keywords= {Location Management; PCS Networks; Centralized versus Distributed; Performance Analysis}, url = "http://www.cs.bu.edu/faculty/matta/Papers/join01.ps" } @inproceedings{MattaBestavros:NSFwIT00, author={Ibrahim Matta and Azer Bestavros}, title= {{QoS Controllers for the Internet}}, booktitle={{Proceedings of the NSF Workshop on Information Technology}}, address={Cairo, Egypt}, month={March}, year=2000, keywords = {QoS Controllers, Internet}, url = "http://www.cs.bu.edu/faculty/matta/Papers/NSFwIT00.ps", abstract={In this position paper, we review basic control strategies that machines acting as {\em traffic controllers} could deploy in order to improve the management of Internet services. Such traffic controllers are likely to spur the widespread emergence of advanced applications, which have (so far) been hindered by the inability of the networking infrastructure to deliver on the promise of Quality-of-Service (QoS).} } @Article{MattaGuo:JCN00, author = "Ibrahim Matta and Liang Guo", title = {{QDMR: An Efficient QoS Dependent Multicast Routing Algorithm}}, journal = "Journal of Communications and Networks - Special Issue on QoS in IP Networks", month = "June", volume = 2, number = 2, pages = "168--176", year = 2000, comment = "Guest Editors: H. Schulzrinne, H. Miyahara, and L. Fratta", keywords= {Quality-of-Service networks; real-time multicast routing, constrained path optimization; simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/jcn00.ps", abstract = {Many distributed real-time applications, such as audio- and video-conferencing and collaborative systems, require multicast support from the underlying network. Multicasting involves the delivery of messages over a tree rooted at the sender and whose paths lead to the various receivers. A major objective of the routing protocol is to build a tree with minimum cost. Finding such a tree is known to be computationally expensive, and many heuristics have been proposed to efficiently find near-optimal trees. Moreover, some heuristics exist to efficiently find multicast trees that are of low cost {\em and} satisfy Quality-of-Service (QoS) (e.g.\ delay) delivery constraints required by real-time applications. However, these heuristics are not fast enough for large-scale networks. In this paper, we present a fast algorithm, called QDMR, for generating delay-constrained low-cost multicast routing trees. A salient feature of QDMR is that it {\em dynamically} adjusts its low-cost tree construction policy based on how far the current on-tree node is from violating the QoS delay bound. This QoS dependent (adaptive) tree construction, together with the capability to merge least-delay paths into the low-cost tree in case of stringent delay requirements, lead to the following properties: (1)~QDMR guarantees that a feasible multicast tree (that satisfies the requested delay) will be found if such tree exists; (2)~this delay-bounded multicast tree is very rapidly generated; and (3)~the tree has low cost. Through analysis and extensive simulations, we confirm the premise of QDMR by comparing it to many existing multicast algorithms. } } @inproceedings{RatnamMattaRangarajan:ISCC00, author = "Karu Ratnam and Ibrahim Matta and Sampath Rangarajan", title = {{A Fully Distributed Location Management Scheme for Large PCS}}, booktitle = "{Proceedings of ISCC~'2000: The Fifth IEEE Symposium on Computers and Communications}", month = "July", address = "Antibes-Juan les Pins, France", year = 2000, keywords = {Personal Communication Networks, Location Management, Performance Analysis}, url = "http://www.cs.bu.edu/faculty/matta/Papers/iscc00.ps", abstract = {In \cite{RRD,RATNAM}, we presented the design, specification and proof of correctness of a fully distributed location management scheme for PCS networks and argued that fully replicating location information is both appropriate and efficient for small PCS networks. In this paper, we extend our previous work by first analyzing the performance of our scheme. Then, we extend the scheme in a hierarchical environment so as to reduce overhead and scale to {\em large} PCS networks. Through extensive numerical results, we show the superiority of our scheme compared to the current IS-41 standard.} } @Article{MedinaMattaByers:ccr00, author = "Alberto Medina and Ibrahim Matta and John Byers", title = {{On the Origin of Power Laws in Internet Topologies}}, journal = "ACM Computer Communication Review", year = 2000, volume = "30", number = "2", month = "April", keywords = {Topology Generation, Power Laws}, url = "http://www.cs.bu.edu/faculty/matta/Papers/ccr00.ps", abstract = {Recent empirical studies \cite{FFF99} have shown that Internet topologies exhibit power laws of the form $y = x^\alpha$ for the following relationships: (P1)~outdegree of node (domain or router) versus rank; (P2)~number of nodes versus outdegree; (P3)~number of node pairs within a neighborhood versus neighborhood size (in hops); and (P4)~eigenvalues of the adjacency matrix versus rank. However, causes for the appearance of such power laws have not been convincingly given. In this paper, we examine four factors in the formation of Internet topologies. These factors are (F1)~preferential connectivity of a new node to existing nodes; (F2)~incremental growth of the network; (F3)~distribution of nodes in space; and (F4)~locality of edge connections. In synthetically generated network topologies, we study the relevance of each factor in causing the aforementioned power laws as well as other properties, namely diameter, average path length and clustering coefficient. Different kinds of network topologies are generated: (T1)~topologies generated using our parametrized generator, we call {\sc BRITE}; (T2)~random topologies generated using the well-known Waxman model \cite{Waxman88}; (T3)~Transit-Stub topologies generated using GT-ITM tool \cite{CDZ97}; and (T4)~regular grid topologies. We observe that some generated topologies may not obey power laws P1 and P2. Thus, the existence of these power laws can be used to validate the accuracy of a given tool in generating representative Internet topologies. Power laws P3 and P4 were observed in nearly all considered topologies, {\em but} different topologies showed different values of the power exponent $\alpha$. Thus, while the presence of power laws P3 and P4 do not give strong evidence for the representativeness of a generated topology, the value of $\alpha$ in P3 and P4 can be used as a litmus test for the representativeness of a generated topology. We also find that factors F1 and F2 are the key contributors in our study which provide the resemblance of our generated topologies to that of the Internet. } } @inproceedings{MattaGuo:icnp00, author={Ibrahim Matta and Liang Guo}, title= {{Differentiated Predictive Fair Service for TCP Flows}}, booktitle={{Proceedings of ICNP'2000: The 8th IEEE International Conference on Network Protocols}}, address={Osaka, Japan}, keywords={Differentiated service; TCP congestion control; class-based isolation versus sharing; packet dropping (tail-drop, RED); fairness; control theory; simulation}, month={October}, year=2000, url = "http://www.cs.bu.edu/faculty/matta/Papers/icnp00.ps", abstract={} } %} @article{MattaBestavrosKrunz:ETT99, author = "Ibrahim Matta and Azer Bestavros and Marwan Krunz", title = {{Load Profiling Based Routing for Guaranteed Bandwidth Flows}}, journal = "European Transactions on Telecommunications - Special Issue on Architectures, Protocols and Quality of Service for the Internet of the Future", volume = 10, number = 2, pages = "165--181", month = "March/April", year = 1999, comment = "Guest Editors: M. D'Ambrosio and M. Atiquzzaman", keywords = {Integrated services networks; QoS routing; virtual path based networks; admission control and routing of multi-class guaranteed flows; load balancing, packing, and profiling; real-time/on-line resource allocation; performance evaluation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/ett99.ps", abstract = {To support the stringent Quality of Service (QoS) requirements of real-time ({\em e.g.} audio/video) applications in integrated services networks, several routing algorithms that allow for the reservation of the needed bandwidth over a Virtual Circuit (VC), established on one of several candidate routes, have been proposed. Traditionally, such routing is done using the least-loaded concept, and thus results in balancing the load across the set of candidate routes. In this paper, we propose the use of {\em load profiling} as an attractive alternative to load balancing for routing guaranteed bandwidth VCs (flows). Load profiling techniques allow the distribution of ``available'' bandwidth across a set of candidate routes to match the characteristics of incoming VC QoS requests. We thoroughly characterize the performance of VC routing using load profiling and contrast it to routing using load balancing and load packing. We do so both analytically and via extensive simulations of multi-class traffic routing in Virtual Path (VP) based networks. Our findings show that for routing guaranteed bandwidth flows in VP networks, load profiling is desirable as it reduces VP bandwidth fragmentation, which increases the likelihood of accepting new VC requests. This fragmentation could be particularly harmful when the granularity of VC requests is large. Typically, this occurs when a common VC is established to carry the {\em aggregate} traffic flow of many high-bandwidth real-time sources. For VP-based networks, our simulation results show that our load-profiling VC routing scheme performs better or as well as the traditional load-balancing VC routing in terms of revenue under both skewed and uniform workloads. Furthermore, load-profiling routing improves routing fairness by proactively increasing the chances of admitting high-bandwidth flows.} } @inProceedings{GuoMatta:RTAS99, author = "Liang Guo and Ibrahim Matta", title = {{QDMR: An Efficient QoS Dependent Multicast Routing Algorithm}}, booktitle = "{Proceedings of RTAS~'99: The Fifth IEEE Real-Time Technology and Applications Symposium}", month = "June", address = "Vancouver, British Columbia, Canada", year = 1999, keywords= {Quality-of-Service networks; real-time multicast routing, constrained path optimization; simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/rtas99.ps", abstract = {Many real-time applications, such as video conferencing, require the transmission of messages from a sender to multiple receivers subject to Quality-of-Service (QoS) delivery constraints (e.g.\ bounded delay). This requires the underlying multicast protocol to find a QoS-constrained minimum-cost communication path (tree). However, finding such a tree is known to be computationally expensive. In this paper, we present a fast heuristic, called QDMR, for generating delay-constrained low-cost multicast routing trees. A salient feature of QDMR is that it dynamically adjusts its low-cost tree construction policy based on how far the current on-tree node is from violating the QoS delay bound. This QoS dependent (adaptive) tree construction, together with the capability to merge least-delay paths into the low-cost tree in case of stringent delay requirements, lead to the following properties: (1)~QDMR guarantees to find a feasible multicast tree if such tree exists; (2)~this delay-bounded multicast tree is very rapidly generated; and (3)~the tree has low cost. Through analysis and extensive simulations, we confirm the premise of QDMR by comparing it to many existing multicast algorithms.} } @inproceedings{GuoMatta:ICDCS99, author = {Liang Guo and Ibrahim Matta}, title = {{Search Space Reduction in {QoS} Routing}}, booktitle = {Proceedings of ICDCS~'99: The 19th International Conference on Distributed Computing Systems}, year = 1999, month = "June", address = {Austin, Texas}, keywords = {Quality-of-Service (QoS) Routing; Constrained Path Optimization; Simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/icdcs99.ps", abstract = {To provide real-time service, integrated networks require the underlying routing algorithm to be able to find low-cost paths that satisfy given Quality of Service (QoS) constraints. 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 {\it 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 the method proposed by Blokh and Gutin \cite{BG95} 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.} } @inproceedings{MattaGuo:ISCC99, author = "Ibrahim Matta and Liang Guo", title = {{On Routing Real-Time Multicast Connections}}, booktitle = "{Proceedings of ISCC~'99: The Fourth IEEE Symposium on Computers and Communications}", month = "June", address = "Red Sea, Egypt", year = 1999, keywords = {Quality-of-Service networks; real-time multicast routing; load distribution; simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/iscc99.ps", abstract = {Many distributed real-time applications, such as audio- and video-conferencing, require the network to construct a multicast path (tree) from a sender to multiple receivers. Furthermore, real-time applications have Quality-of-Service (QoS) requirements ({\it e.g.}\ bandwidth). The objective of the routing protocol is to build a tree that is both feasible ({\it i.e.} satisfies the requested QoS) {\it and} least costly. The cost of a tree depends on the costs of its links. The cost of a link should reflect the effect of allocating resources to the new connection on existing and future connections. Many studies have proposed multicast algorithms to construct low-cost QoS-constrained trees. However, these studies assume that {\it some} cost is given for each link, and they do not examine the effect of the link cost function. In this paper, we examine the effect of various link cost functions on the performance of two classes of multicast routing algorithms under both uniform and skewed real-time workload. We also investigate the impact of inaccurate network state information. Our simulation results show that when network state information is accurate (most up-to-date) at each router, the choice of the link cost function only has a negligible effect, if any, on the routing performance. More interestingly, we find that, a link cost function that is more sensitive to load performs better when link state information is relatively accurate, while when link state information is more stale, a link cost function that is less sensitive to load performs better. This is more pronounced under higher load and when multicast groups are more dense.} } @inproceedings{RatnamMattaRangarajan:ICNP99, author = "Karu Ratnam and Ibrahim Matta and Sampath Rangarajan", title = {{Analysis of Caching-based Location Management in Personal Communication Networks}}, booktitle = "{Proceedings of ICNP~'99: The 7th International Conference on Network Protocols}", address = "Toronto, Canada", month = "November", year = 1999, keywords = {Personal Communication Networks; Location Management; Caching; Performance Analysis}, url = "http://www.cs.bu.edu/faculty/matta/Papers/icnp99.ps", abstract = {Personal communication networks support the delivery of communication services as the user moves from one region to another. When a mobile user/terminal receives a call, the network has to quickly determine its current location. The existing approach suffers from high delay in locating the mobile as it requires maintaining the current location in a stable storage that has to be always consulted to reach the mobile. To reduce this delay, many proposed schemes rely on caching the locations of mobiles, especially those which do not move too frequently. To measure mobility, the node that originates the call usually measures {\em only} those movements that it sees between successive calls to that mobile. In this paper, we present a caching scheme based on fully disseminating the location updates of mobiles to {\em every} node so as to increase the chance that the cache entry points to the correct location of the mobile user. We analyze our full dissemination based scheme and compare it to other caching and non-caching based schemes.} } @inproceedings{Matta:essen99, author={Ibrahim Matta}, title= {{On Network Resource Management for End-to-End QoS}}, booktitle={{Workshop on Wide Area Networks and High Performance Computing}}, address={Essen, Germany}, pages = "199-218", series = {Lecture Notes in Control and Information Sciences}, publisher = {Springer Verlag}, volume= 249, year=1999, isbn = {1-85233-642-0}, keywords = {QoS architectures}, url = "http://www.cs.bu.edu/faculty/matta/Papers/essen99.ps", abstract= {This article examines issues and challenges in building distributed Quality-of-Service (QoS) architectures. We consider architectures that facilitate cooperation between the applications and the network so as to achieve the following tasks. Applications are allowed to express in their own language their QoS (performance and cost) requirements. These application-specific requirements are communicated to the network in a language the network understands. Resources are appropriately allocated within the network so as to satisfy these requirements in an efficient, scalable, and reliable manner. Furthermore, the applications and the network have to cooperate ``actively'' (or continually) to be able to achieve these tasks under time-varying conditions.} } @misc{MattaGuo:NUEXPO1998, author = "Ibrahim Matta and Liang Guo", title = {{Z-iteration: Rapid Evaluation of System Performance}}, howpublished = "{Northeastern University TECH EXPO}", year = 1998 } @article{KrunzMattaZhao:JTelecomm98, author = "Marwan Krunz and Wei Zhao and Ibrahim Matta", title = {{Scheduling and Bandwidth Allocation for the Distribution of Archived Video in VOD Systems}}, journal = "Journal of Telecommunication Systems - Special Issue on Multimedia", volume = 9, number = "3-4", pages = "335--355", month = "September", year = 1998, keywords = {Bandwidth Allocation; MPEG; Video Scheduling; Video-On-Demand; Traffic Envelope}, url = "http://www.cs.bu.edu/faculty/matta/Papers/telecomm98.ps", abstract = {} } @article{MattaShankar:ISDN98, author = "Ibrahim Matta and A.~Udaya Shankar", title = {{Fast Time-Dependent Evaluation of Integrated Services Networks}}, journal = "Computer Networks and ISDN Systems - Special Issue on Modeling of Wired and Wireless ATM", year = 1998, volume = 29, number = "17-18", month = "February", pages = "1999-2020", keywords = {Multi-Service Networks, Transient Performance, Dynamic Flow Models, Queueing Models, Resource Allocation Algorithms, Routing}, url = "http://www.cs.bu.edu/faculty/matta/Papers/isdn98.ps", abstract = {We present a numerical-analytical method to evaluate multi-service networks with adaptive routing, scheduling and admission controls. We apply our method to connection-oriented networks supporting different types of real-time connections. The network dynamics is described by difference equations which can be solved for both transient and steady-state performances. Results indicate that our method is computationally much cheaper than discrete-event simulation, and yields accurate performance measures. Connection routing algorithms are usually evaluated individually in terms of steady-state performance measures. In this paper, we also use our time-dependent evaluation method to compare several connection routing schemes in terms of {\it instantaneous} measures. Our results show that a routing scheme which defines the cost of a path as the sum of measured link utilizations yields more stable behavior and lower connection blocking probability over a wide range of workload parameters and network configurations than other traditional schemes.} } @inProceedings{MattaBestavros:INFOCOM98, author = "Ibrahim Matta and Azer Bestavros", title = {{A Load Profiling Approach to Routing Guaranteed Bandwidth Flows}}, booktitle = "{Proceedings of IEEE INFOCOM~'98: The Conference on Computer Communications}", month = "March", year = 1998, keywords = {Integrated services networks; virtual path based networks; admission control and routing of multi-class guaranteed flows; load balancing, packing, and profiling; real-time/on-line resource allocation; performance evaluation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/infocom98.ps", abstract = {We study a new approach to routing multi-class traffic flows with guaranteed bandwidth requirements. The approach is based on our recently proposed concept of {\em load profiling} \cite{Matta:ICNP97}. We thoroughly characterize routing performance using load profiling and contrast it to routing using load balancing and load packing. We do so both analytically and via extensive simulations on Virtual Path (VP) based networks. Our findings confirm that load balancing is not desirable as it results in VP bandwidth fragmentation, which adversely affects the likelihood of accepting new flow requests. This fragmentation is more pronounced when the granularity of the requests is large. Our simulation results also show that our load-profiling routing scheme performs better or as well as the traditional load-balancing routing in terms of revenue under both skewed and uniform workloads. Furthermore, load-profiling routing improves routing fairness by proactively increasing the chances of admitting high-bandwidth flows.} } @inProceedings{Matta:ATM98, author = "Liang Guo and Ibrahim Matta", title = {{On State Aggregation for Scalable QoS Routing}}, booktitle = "Proceedings of the IEEE ATM '98 Workshop", address = "Fairfax, VA", month = "May", year = 1998, keywords = {Multi-service networks; topology aggregation; hierarchical routing; PNNI; Quality of Service (QoS)}, url = "http://www.cs.bu.edu/faculty/matta/Papers/ATM98.ps", abstract = {State (topology) aggregation is the notion of reducing nodal as well as link information to achieve scaling in a large network. In this paper, we compare the performance of three different aggregation schemes, namely, the Simple-Node scheme, the Full-Mesh scheme, and the Star scheme, which represent a given group of nodes by a single logical node, a complete graph between border nodes, and a star-like graph connecting all of the border nodes, respectively. We obtain transient performance measures for multi-service networks using our recently developed Z-iteration method \cite{Z-iter:web}. We restrict the set of candidate paths to short length paths as this has been shown to be an effective way to enhance network performance. Our simulation results indicate that under a uniformly distributed workload, the scheme that has more detailed topology information performs much better, as common sense suggests. More interestingly, however, we found that as the workload becomes skewed, i.e., as it concentrates around few ``hot-spot'' nodes, the Simple-Node scheme, which is considered to be the most inaccurate aggregation scheme, appears to perform at least as well as the Full-Mesh scheme, which on the contrary provides the most detailed information. We attribute this result to the conflicting goals of network utilization efficiency and network load balancing, a conflict that arises when restricting the set of candidate paths.} } @inproceedings{RatnamMatta:ISCC98, author = "Karu Ratnam and Ibrahim Matta", title = {{WTCP: An Efficient Mechanism for Improving TCP Performance over Wireless Links}}, booktitle = "Proceedings of ISCC '98: The Third IEEE Symposium on Computer and Communications", month = "June", address = "Athens, Greece", year = 1998, keywords = {Wireless access, flow control, congestion control, error recovery, Internet, TCP/IP, transport protocols, performance evaluation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/iscc98.ps", abstract = {The Transmission Control Protocol (TCP) used in the Internet has been mainly designed assuming a relatively reliable wireline network. TCP assumes that {\em any} loss is due to congestion and consequently invokes congestion control measures. This has been shown to yield poor performance in the presence of wireless links as a large number of segment losses will occur more often because of wireless channel errors or host mobility. We present an efficient transmission control scheme (WTCP) that requires the base station to buffer data packets destined for the mobile host and retransmit lost packets. Through simulations, we show that our scheme yields better throughput than other existing proposals {\em while} maintaining TCP's end-to-end semantics. One salient feature of WTCP is that it effectively hides the time spent by the base station to locally recover so that the TCP's round trip time estimation at the source is not affected. This is critical since otherwise the ability of the source to effectively detect congestion in the wireline network will be hindered.} } @inproceedings{RatnamMatta:SS98, author = "Karu Ratnam and Ibrahim Matta", title = {{Effect of Local Retransmission at Wireless Access Points on the Round Trip Time Estimation of TCP}}, booktitle = "Proceedings of IEEE 31st Annual Simulation Symposium", month = "April", year = 1998, keywords = {Wireless access, flow control, congestion control, error recovery, Internet, TCP/IP, transport protocols, performance evaluation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/ss98.ps", 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 {\em 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 use extensive simulations to evaluate TCP performance in the presence of congestion and wireless losses when the base station employs one of two proposals, namely Snoop \cite{BALA:COM} and WTCP \cite{KARU:TR}. 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.} } @inproceedings{MattaEltoweissyLieberherr:ICC98, author = "Ibrahim Matta and MMohamed Eltoweissy and Karl Lieberherr", title = {{From CSCW Applications to Multicast Routing: An Integrated QoS Architecture}}, booktitle = "{Proceedings of ICC'98: The IEEE International Conference on Communications}", month = "June", address = "Atlanta, Georgia", year = 1998, keywords = {Computer Supported Cooperative Work, multicast routing, quality-of-service, protocol architecture, aspect-oriented programming}, url = "http://www.cs.bu.edu/faculty/matta/Papers/icc98.ps", abstract = {Computer Supported Cooperative Work (CSCW) has the potential of providing the environment needed for groups of diverse users to cooperate to achieve their common goals. This potential has been under-utilized. One major obstacle is the lack of cooperation between CSCW systems and the underlying network services to accommodate the dynamic behavior of CSCW groups. Multicast routing presents a strong case where current network services are inadequate for the traffic generated in CSCW environments. In this paper, we demonstrate the need for CSCW-specific multicast routing and present an integrated QoS architecture where a router QoS manager, on behalf of a multicast routing manager, negotiates with host and CSCW-specific QoS managers for efficient resource utilization and guaranteed QoS delivery. The multicast routing manager switches between routing trees or algorithms as warranted by the changes in the characteristics and requirements of the CSCW systems running at the hosts. We discuss an aspect-oriented programming approach to the efficient description and flexible implementation of adaptive application and network protocol behavior.} } @inproceedings{MattaEltoweissy:RTAS98, author = "Ibrahim Matta and Mohamed Eltoweissy", title = {{A Scalable QoS Routing Architecture for Real-Time CSCW Applications}}, booktitle = "{Proceedings of RTAS'98: The Fourth IEEE Real-Time Technology and Applications Symposium}", month = "June", address = "Denver, Colorado", year = 1998, keywords = {Computer Supported Cooperative Work, multicast routing, quality-of-service, protocol architecture, aspect-oriented programming}, url = "http://www.cs.bu.edu/faculty/matta/Papers/rtas98.ps", abstract = {Computer Supported Cooperative Work (CSCW) has the potential of providing the environment needed for groups of diverse users to cooperate in real-time to achieve their common goals. This potential has been under-utilized due to the lack of cooperation between CSCW systems and the underlying network services to accommodate the dynamic behavior and varying Quality-of-Service (QoS) requirements of CSCW groups and the applications they use. To satisfy such requirements, QoS multicast routing should be employed. Unfortunately, current multicast services are inadequate for the traffic generated in CSCW environments. In this paper, we present a CSCW-specific routing architecture that supports QoS requirements and is both scalable and robust. Scalability is needed to accommodate large number of multicast groups and highly dynamic group membership and behavior, while robustness provides reliability and stable performance for each group during adaptation and in presence of the other existing groups. In our architecture, a router QoS manager, on behalf of a multicast routing manager, negotiates with host and CSCW-specific QoS managers for efficient resource utilization and guaranteed QoS delivery. The multicast routing manager switches between routing trees and algorithms as warranted by the changes in the characteristics and requirements of the CSCW systems running at the hosts. We present a class-based and a partial view-based method to scalability. We also present a centralized and a distributed method to establishing a group's QoS multicast path while providing robustness. In addition to prototyping our architecture and defining appropriate protocols and mappings between the various QoS and router managers, we are investigating the use of the Internet standard SNMP for information gathering. This necessitates extending its management information bases (MIBs) to include group objects.} } @inproceedings{EltoweissyMatta:ICTE98, author = {Mohamed Eltoweissy and Ibrahim Matta}, title = {{Computer Supported Generative Learning}}, booktitle = {Proceedings of ICTE~'98: The International Conference on Technology and Education}, year = 1998, month = "March", address = {Santa Fe, New Mexico}, url = "http://www.cs.bu.edu/faculty/matta/Papers/icte98.ps", abstract = {The rapid changes in technology, the explosive growth in global competition, and the restructuring and flattening of organizations are dramatically changing the career requirements of computer scientists and engineers. It has become crucial to engage in a life-long learning process, where knowledge and skills are continually updated to maintain professional vitality. We term this learning process {\it generative learning}. Our work uses modern computing and communication technologies to provide a generative learning environment in which professionals will enjoy maximum support for their learning activities. In this paper, we present a computer supported generative learning (CSGL) model where the learner goes through cycles of learning-application-assessment over different time scales. Key components of our model are multi-grained assessment and cooperative learning. We describe a knowledge-based framework to support these activities. Our proposed CSGL environment will enlevin and enrich life-long learning by providing the instructional and organizational resources needed to plan, execute, manage, and regularly assess the progress of the integrated career and education processes.} } @inProceedings{MattaKrunz:ICC97, author = "Ibrahim Matta and Marwan Krunz", title = {{Packing and Least-Loaded Based Routing in Multi-Rate Loss Networks}}, booktitle = "{Proceedings of ICC~'97: The IEEE International Conference on Communications}", pages = "827-831", month = "June", address = "Montreal, Quebec, Canada", year = 1997, keywords = {Routing, admission control, resource allocation algorithms, multi-rate loss networks, simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/icc97.ps", abstract = {We examine various schemes for dynamically routing virtual circuits (VCs) in a multi-class network. A VC setup request may be rejected by admission control because resources are either unavailable or being reserved for future incoming VCs. We examine least-loaded based schemes, which attempt to balance the load among available routes. In addition, we examine packing based schemes, which attempt to reduce bandwidth fragmentation possibly at the expense of load balancing. Our simulation results show that under skewed workload, our packing based scheme outperforms a traditional least-loaded based scheme in terms of revenue (or equivalently, network utilization). Under uniform workload, both schemes provide similar revenue. } } @inproceedings{EltoweissyMatta:ESCCC97, author = {Mohamed Eltoweissy and Ibrahim Matta}, title = {{A Framework for Computer Supported Generative Learning}}, booktitle = {Proceedings of ESCCC~'97: The 13th Eastern Small College Computing Conference}, year = 1997, address = "Stockton, NJ", month = "October", pages = "197-206" } @inproceedings{MattaShankar:ICNP96, author = "Ibrahim Matta and A.~Udaya Shankar", title = {{Dynamic Routing of Real-Time Virtual Circuits}}, booktitle = {Proceedings of ICNP~'96: The IEEE International Conference on Network Protocols}, year = 1996, month = "October", address = "Columbus, Ohio", url = "http://www.cs.bu.edu/faculty/matta/Papers/icnp96.ps", abstract = {Future integrated services networks, such as ATM networks, will support diverse services, including guaranteed real-time service required by many applications such as voice and video. To support such service, virtual circuit (VC) routing algorithms are often proposed. Typically, the source maintains a view of the network, and uses this view to select a path to the destination. A request is then made to setup a real-time VC over this path through resource reservations. The request is blocked if the requested resources are not available. These VC routing algorithms are usually evaluated individually in terms of steady-state performance measures. In this paper, we compare several VC routing schemes in terms of {\rm instantaneous} measures using a recently developed time-dependent evaluation method. Our results show that a routing scheme which defines the cost of a path as the sum of measured link utilizations yields more stable behavior and lower VC blocking probability over a wide range of workload parameters and network configurations than other traditional schemes.} } @inproceedings{MattaRyan:IC3N96, author = "Ibrahim Matta and Daniel Ryan", title = {{Optimal Transmission of Data Over Multi-Hop Networks}}, booktitle = {Proceedings of ICCCN '96: The 5th International Conference on Computer Communications and Networks}, year = 1996, month = "October", address = "Rockville, MD", note = "Poster", url = "http://www.cs.bu.edu/faculty/matta/Papers/icccn96.ps", abstract = {We study the end-to-end delay performance when transmitting data traffic over multi-hop networks. Data is normally carried in transmission units (e.g.,\ packet, frame, cell). The performance is strongly affected by several factors, including header and payload sizes of the transmission units, and the effect of pipelining these units over the multiple links. We determine the optimal payload size as a function of the data size, the header size and the number of links. We show the performance penalty incurred because of some transmission standards.} } @Article{MaRS:JINet95, author = "A.~Udaya Shankar and Cengiz Alaettino\u{g}lu and Klaudia Dussa-Zieger and Ibrahim Matta", title = {{Transient and Steady-State Performance of Routing Protocols: Distance-Vector versus Link-State}}, journal = "Journal of Internetworking: Research and Experience", year = 1995, volume = 6, pages = "59-87", keywords = {Computer networks, routing protocols, performance evaluation, modeling, discrete-event simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/jinet95.ps", abstract = {We examine two approaches to adaptive routing protocols for wide-area store-and-forward networks, namely, distance-vector and link-state. Distance-vector algorithms have less storage requirements than link-state algorithms. The ARPANET started with a distance-vector algorithm (Distributed Bellman-Ford), but because of long-lived loops, changed to a link-state algorithm (SPF). We evaluate, using a recently developed network simulator, MaRS, the transient and steady-state performance of SPF and two newly proposed distance-vector algorithms (ExBF and MS). Overall, SPF and ExBF have comparable performance and MS is worse.} } @article{MattaShankar:jsac95, author = "Ibrahim Matta and A.~Udaya Shankar", title = {{Type-of-Service Routing in Datagram Delivery Systems}}, journal = "{IEEE Journal on Selected Areas in Communications~--~Special Issue on the Internet}", volume = 13, number = 8, pages = "1411--1425", month = "October", year = 1995, comment = "Guest Editors: J. Crowcroft, D. Estrin, H. Schulzrinne, and M. Schwartz", url = "http://www.cs.bu.edu/faculty/matta/Papers/jsac95.ps", abstract = {The Internet is expected to support various services, including best-effort services and guaranteed services. For best-effort services, we propose a new approach to achieving type-of-service (TOS) classes with adaptive next-hop routing. We consider two TOS classes, namely, delay-sensitive and throughput-sensitive. As in routing protocols such as OSPF and integrated IS-IS, each node has a different next-hop for each destination and TOS class. Traditionally, a node has a single FCFS queue for each outgoing link, and the next-hops are computed using link measurements. In our approach, we attempt to isolate the two traffic classes by using for each outgoing link a separate FCFS queue for each TOS class; the link is shared cyclicly between its TOS queues. The next-hops for the delay-sensitive traffic adapts to link delays of that traffic. The next-hops for the throughput-sensitive traffic adapts to overall link utilizations. We compare our approach with the traditional approach using discrete-event simulation and Liapunov analysis (for stability of routes). Our approach offers lower end-to-end delay to the delay-sensitive traffic. A related property is that the routes for the delay-sensitive traffic are more stable, i.e.\ less oscillations. An unexpected property is that the overall end-to-end delay is lower, because the throughput-sensitive traffic moves away to under-utilized routes.} } @inproceedings{MattaShankar:sigmetrics95, author = "Ibrahim Matta and A.~Udaya Shankar", title = {{{\it Z}-Iteration: A Simple Method for Throughput Estimation in Time-Dependent Multi-Class Systems}}, booktitle = "Proceedings of ACM SIGMETRICS / PERFORMANCE~'95", address = "Ottawa, Canada", pages = "126-135", month = "May", year = 1995, keywords = {Multi-class systems, transient performance, dynamic flow models, queueing models, simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/sigmetrics95.ps", abstract = {Multiple-class multiple-resource (MCMR) systems, where each class of customers requires a particular set of resources, are common. These systems are often analyzed under steady-state conditions. We describe a simple method, referred to as {\mbox {\it Z-iteration}}, to estimate both transient and steady-state performances of such systems. The method makes use of results and techniques available from queueing theory, network analysis, dynamic flow theory, and numerical analysis. We show the generality of the {\it Z}-iteration by applying it to an ATM network, a parallel disk system, and a distributed batch system. Validations against discrete-event simulations show the accuracy and computational advantages of the {\mbox {\it Z-}iteration}.} } @inproceedings{AlaettinogluMattaShankar:icccn95, author = "Cengiz Alaettinoglu and Ibrahim Matta and A.~Udaya Shankar", title = {{A Scalable Virtual Circuit Routing Scheme for {ATM} Networks}}, booktitle = {Proceedings of ICCCN~'95: The International Conference on Computer Communications and Networks}, pages = "630-637", year = 1995, month = "September", address = {Las Vegas, Nevada}, keywords = {Virtual circuit routing, admission control, resource allocation, real-time service, simulation}, url = "http://www.cs.bu.edu/faculty/matta/Papers/icccn95.ps", abstract = {We present a scalable VC routing protocol based on the recently proposed viewserver hierarchy. Each viewserver maintains a partial view of the network. By querying these viewservers, a source obtains a merged view that contains a path to the destination. The source then sends a setup request packet over this path to reserve resources. We use simulation to compare our protocol to a simple approach that maintains a full view of the network. In addition to the savings in storage, our protocol performs as well or better in terms of VC carried load and blocking probability over a wide range of real-time workload. } }