Traffic classification has gained much attention in the past decade, and deep learning proved to exhibit good classification performance. However, the lack of large labeled datasets pushed research to explore few-shots learning approaches, where only a few labeled samples per class are available. Augmentation techniques tailored to the domain of network traffic were proved as a viable solution. In this paper, we demonstrate a new approach to obtain better classification accuracy. Our solution simplifies preprocessing and reduces training time, while effectively utilizing small amounts of training data. Furthermore, it proves to be highly effective in few-shot scenarios, demonstrating robust results when tested on disjoint datasets, specifically the UCDAVIS19 and ISCX datasets. Inspired by the recent breakthroughs in integrating image and text data, particularly the OpenAI CLIP model, we introduce FlowPicClip. This model harnesses the power of contrastive learning with FlowPics and their labels as text sentences. By leveraging Large Language Model (LLM) encoders, FlowPicClip aligns network traffic representations with their textual descriptions. We demonstrate 2.75% and 1.4% improvements over the best published results on the UCDavis19-Human and ISCX datasets for classification tasks, along with$\mathbf{1. 5 \%}$and$\mathbf{6. 2 \%}$improvements in few-shot classification achieved in a disjoint dataset scenario.

Beneš/CLOS architectures are common scalable interconnection networks widely used in backbone routers, data centers, on-chip networks, multi-processor systems, and parallel computers. Recent advances in Silicon Photonic technology, especially MZI technology, have made Beneš networks a very attractive scalable architecture for optical circuit switches.Numerous routing algorithms for Beneš networks were developed starting with linear algorithms having time complexity of O(N log2N) steps. Parallel routing algorithms were developed to satisfy the stringent timing requirements of high-performance switching networks and have time complexity of O((log2N)2).However, their implementation requires O(N2log2N) wires (termed connectivity complexity), and thus are difficult to scale.We present a new routing algorithm for Beneš networks combined with a scalable hardware architecture that supports full and partial input permutations. The processing time of the algorithm is limited to O((log2N)2) steps (iterations) by potentially forfeiting routing of a few input demands; however achieves close to 100% utilization for both full and partial input permutations. The algorithm and architecture allow a reduction of the connectivity complexity to O(N2), a logN improvement over previous solutions.We prove the algorithm correctness, and analyze its performance analytically and with large scale simulations.

Internet traffic classification has been intensively studied over the past decade due to its importance for traffic engineering and cyber security. A promising approach to several traffic classification problems is the FlowPic approach, where histograms of packet sizes in consecutive time slices are transformed into a picture that is fed into a Convolution Neural Network (CNN) model for classification. However, CNNs (and the FlowPic approach included) require a relatively large labeled flow dataset, which is not always easy to obtain. In this paper, we show that we can overcome this obstacle by using Contrastive Representation Learning in order to learn from an unlabeled flow dataset a flow representation that can be embedded in a latent space, enabling clustering of flows belonging to the same class together. We then show that by using just a few labeled flows (a few shots) from each class, we can achieve high accuracy in flow classification. We show that common picture augmentation techniques can help, but accuracy improves further when introducing augmentation techniques that mimic network behavior, such as changes in the RTT (Round-trip time). Finally, we show that we can replace the large FlowPics suggested in the past with much smaller mini-FlowPics and achieve two advantages: improved model performance and easier engineering. Interestingly, this even improves accuracy in some cases.

Internet traffic classification has been intensively studied over the past decade due to its importance for traffic engineering and cyber security. One of the best solutions to several traffic classification problems is the FlowPic approach, where histograms of packet sizes in consecutive time slices are transformed into a picture that is fed into a Convolution Neural Network (CNN) model for classification.

BGP hijack attacks deflect traffic between endpoints through the attacker network, leading to man-in-the-middle attacks. Thus its detection is an important security challenge. In this paper, we introduce a novel approach for BGP hijacking detection that is based on the observation that during a hijack attack, the functional roles of ASNs along the route change. To identify a functional change, we build on previous work that embeds ASNs to vectors based on BGP routing announcements and embed each IP address prefix (AP) to a vector representing its latent characteristics, we call it AP2Vec. Then, we compare the embedding of a new route with the AP embedding that is based on the old routes to identify large differences. We compare our unsupervised approach to several other new and previous approaches and show that it strikes the best balance between a high detection rate of hijack events and a low number of flagged events. In particular, for a two-hour route collection with 10-90,000 route changes, our algorithm typically flags 1-11 suspected events (0.01-0.05% FP). Our algorithm also detected most of the previously published hijack events.

BGP announcements hold latent information about the Internet Autonomous Systems (ASes) and their functional position within the Internet eco-system. This information can aid us in understanding the Internet structure and also in solving many practical problems. In this paper, we present BGP2Vec, a novel approach to revealing the latent characteristics of ASes using neural-network-based embedding. We show that our embedding indeed captures important characteristics of ASes, and then show how the embedding can be used to solve two problems: ASN business-type classification and AS Type of Relationships (ToRs) inference. ToRs inference has been heavily studied in the past two decades and is important for studying Internet routing and identifying IP hijack attacks. We use the BGP2Vec vectors as an input to artificial neural networks and achieve excellent results: an accuracy of 95.8% for ToR classification and an accuracy of 79.2% for AS classification.

IP hijack attacks deflect traffic between endpoints through the attacker network, leading to man-in-the-middle attacks. Current detection solutions are only based on AS-level path analysis, while attacks that include data-plane manipulations may exhibit only geographic anomalies and preserve the AS-level route, or hide the problematic AS in the path. Thus, there is a need to develop data-plane analysis frameworks that examine the actual route packets traverse. We introduce here a deep learning system that examines the geography of traceroute measurements to detect malicious routes. We use multiple geolocation services, with various levels of confidence; each also suffers from location errors. Moreover, identifying a hijacked route is not sufficient since an operator presented with a hijack alert needs an indication of the cause for flagging out the problematic route. Thus, we introduce a novel deep learning layer, called Source-Aware Self-Attention (SASA), which is an extension of the attention mechanism.SASAlearns each data source’s confidence and combines this score with the attention of each router in the route to point out the most problematic one. We validate our IP hijacking classification method using two router data types: coordinates and country location, and show thatSASAoutperforms the regular self-attention layer, using the same neural network architecture, and achieves extremely high accuracy.

Identifying the type of a network flow or a specific application has many advantages, such as, traffic engineering, or to detect and prevent application or application types that violate the organization’s security policy. The use of encryption, such as VPN, makes such identification challenging. Current solutions rely mostly on handcrafted features and then apply supervised learning techniques for the classification. We introduce a novel approach for encrypted Internet traffic classification and application identification by transforming basic flow data into an intuitive picture, aFlowPic, and then using known image classification deep learning techniques, CNNs, to identify the flow category (browsing, chat, video, etc.) and the application in use. We show that our approach can classify traffic with high accuracy, both for a specific application, or a flow category, even for VPN and Tor traffic. Our classifier can even identify with high success new applications that were not part of the training phase for a category, thus, new versions or applications can be categorized without additional training.

Allocating the right amount of resources to each service in any of the datacenters in a cloud environment is a very difficult task. This task becomes much harder due to the dynamic nature of the workload and the fact that while long term statistics about the demand may be known, it is impossible to predict the exact demand in each point in time. As a result, service providers either over allocate resources and hurt the service cost efficiency, or run into situation where the allocated local resources are insufficient to support the current demand. In these cases, the service providers deploy overflow mechanisms such as redirecting traffic to a remote datacenter or temporarily leasing additional resources (at a higher price) from the cloud infrastructure owner. The additional cost is in many cases proportional to the amount of overflow demand. In this paper we study this approach and develop a novel mechanism to assign services to datacenters based on the available resources in each datacenter and the distribution of the demand for each service. We use comprehensive analysis to prove that the overall overflow cost is almost optimal for arbitrary demand distributions, as long as there are no dependencies among the services. We further show, using simulation based on real data that the scheme performs very well on realistic service workloads.

The ToR inference problem had been widely investigated in the last two decades, mostly using heuristic algorithms. In this problem, we attempt to reveal the economic relationships between ASes, data with applications in network routing management and routing security.In this paper, we introduce a novel approach for ToR classification, which is based on embedding the AS numbers (ASN) in high dimensional space using neural networks. Similar to natural language processing (NLP) models, the embedding represents latent characteristics of the ASN and its interactions on the Internet. The embedding coordinates of each AS are represented by a vector; thus, we call our method BGP2VEC. In order to solve the supervised learning problem presented, we use these vectors as an input to an artificial neural network and achieve a state of the art accuracy of 95.2% for ToR classification.

The stochastic knapsack problem is a stochastic version of the well known deterministic knapsack problem, in which some of the input values are random variables. There are several variants of the stochastic problem. In this paper we concentrate on the chance-constrained variant, where item values are deterministic and item sizes are stochastic. The goal is to find a maximum value allocation subject to the constraint that the overflow probability is at most a given value. Previous work showed a PTAS for the problem for various distributions (Poisson, Exponential, Bernoulli and Normal). Some strictly respect the constraint and some relax the constraint by a factor of (1+epsilon). All algorithms use Omega(n^{1/epsilon}) time. A very recent work showed a "almost FPTAS" algorithm for Bernoulli distributions with O(poly(n) * quasipoly(1/epsilon)) time. In this paper we present a FPTAS for normal distributions with a solution that satisfies the chance constraint in a relaxed sense. The normal distribution is particularly important, because by the Berry-Esseen theorem, an algorithm solving the normal distribution also solves, under mild conditions, arbitrary independent distributions. To the best of our knowledge, this is the first (relaxed or non-relaxed) FPTAS for the problem. In fact, our algorithm runs in poly(n/epsilon) time. We achieve the FPTAS by a delicate combination of previous techniques plus a new alternative solution to the non-heavy elements that is based on a non-convex program with a simple structure and an O(n^2 log {n/epsilon}) running time. We believe this part is also interesting on its own right.

Network level surveillance, censorship, and various man-in-the-middle attacks target only specific types of network traffic (e.g., HTTP, HTTPS, VoIP, or Email). Therefore, packets of these types will likely receive “special” treatment by a transit network or a man-in-the-middle attacker. A transit Internet Service Provider (ISP) or an attacker may pass the targeted traffic through special software or equipment to gather data or perform an attack. This creates a measurable difference between the performance of the targeted traffic versus the general case. In networking terms, it violates the principle of “network neutrality,” which states that all traffic should be treated equally. Many techniques were designed to detect network neutrality violations, and some have naturally suggested using them to detect surveillance and censorship. In this article, we show that the existing network neutrality measurement techniques can be easily detected and therefore circumvented. We then briefly propose a new approach to overcome the drawbacks of current measurement techniques.

Many Internet events exhibit periodical patterns. Such events include the availability of end-hosts, usage of internetwork links for balancing load and cost of transit, traffic shaping during peak hours, etc. Internet monitoring systems that collect huge amount of data can leverage periodicity information for improving resource utilization. However, automatic periodicity inference is a non trivial task, especially when facing measurement “noise”. In this paper we present two methods for assessing the periodicity of network events and inferring their periodical patterns. The first method uses Power Spectral Density for inferring a single dominant period that exists in a signal representing the sampling process. This method is highly robust to noise, but is most useful for single-period processes. Thus, we present a novel method for detecting multiple periods that comprise a single process, using iterative relaxation of the time-domain autocorrelation function. We evaluate these methods using extensive simulations, and show their applicability on real Internet measurements of end-host availability and IP address alternations.

The Internet is a complex network, comprised of thousands of interconnected Autonomous Systems. Considerable research is done in order to infer the undisclosed commercial relationships between ASes. These relationships, which have been commonly classified to four distinct Type of Relationships (ToRs), dictate the routing policies between ASes. These policies are a crucial part in understanding the Internet's traffic and behavior patterns. This work leverages Internet Point of Presence (PoP) level maps to improve AS ToR inference. We propose a method which uses PoP level maps to find complex AS relationships and detect anomalies on the AS relationship level. We present experimental results of using the method on ToR reported by CAIDA and report several types of anomalies and errors. The results demonstrate the benefits of using PoP level maps for ToR inference, requiring considerable less resources than other methods theoretically capable of detecting similar phenomena.

Though centrality of vertices in social networks has been extensively studied, all past efforts assume that centrality of a vertex solely depends on the structural properties of graphs. However, with the emergence of online "semantic" social networks where vertices have properties (e.g. gender, age, and other demographic data) and edges are labeled with relationships (e.g. friend, follows) and weights (measuring the strength of a relationship), it is essential that we take semantics into account when measuring centrality. Moreover, the centrality of a vertex should be tied to a diffusive property in the network - a Twitter vertex may have high centrality w.r.t. jazz, but low centrality w.r.t. Republican politics. In this paper, we propose a new notion of diffusion centrality (DC) in which semantic aspects of the graph, as well as a diffusion model of how a diffusive property p is spreading, are used to characterize the centrality of vertices. We present a hyper graph based algorithm to compute DC and report on a prototype implementation and experiments showing how we can compute DCs (using real YouTube data) on social networks in a reasonable amount of time. We compare DC with classical centrality measures like degree, closeness, betweenness, eigenvector and stress centrality and show that in all cases, DC produces higher quality results. DC is also often faster to compute than both betweenness, closeness and stress centrality, but slower than degree and eigenvector centrality.

Low-rank Matrix Factorization (MF) methods provide one of the simplest and most effective approaches to collaborative filtering. This paper is the first to investigate the problem of efficient retrieval of recommendations in a MF framework. We reduce the retrieval in a MF model to an apparently simple task of finding the maximum dot-product for the user vector over the set of item vectors. However, to the best of our knowledge the problem of efficiently finding the maximum dot-product in the general case has never been studied. To this end, we propose two techniques for efficient search -- (i) We index the item vectors in a binary spatial-partitioning metric tree and use a simple branch and-bound algorithm with a novel bounding scheme to efficiently obtain exact solutions. (ii) We use spherical clustering to index the users on the basis of their preferences and pre-compute recommendations only for the representative user of each cluster to obtain extremely efficient approximate solutions. We obtain a theoretical error bound which determines the quality of any approximate result and use it to control the approximation. Both these simple techniques are fairly independent of each other and hence are easily combined to further improve recommendation retrieval efficiency. We evaluate our algorithms on real-world collaborative-filtering datasets, demonstrating more than ×7 speedup (with respect to the naive linear search) for the exact solution and over ×250 speedup for approximate solutions by combining both techniques.

Consider the setting of randomly weighted graphs, namely, graphs whose edge weights are chosen independently according to probability distributions with finite support over the non-negative reals. Under this setting, weighted graph properties such as the diameter, the radius (with respect to a designated vertex), and the weight of a minimum spanning tree become random variables and we are interested in computing their expectation. Unfortunately, this turns out to be #P-hard. In this paper, we define a family of weighted graph properties (that includes the above three) and show that for each property in this family, the problem of computing the kth moment (and in particular, the expectation) of the corresponding random variable admits a fully polynomial-time randomized approximation scheme (FPRAS) for every fixed k.

The topology of the Internet has been extensively studied in recent years, driving a need for increasingly complex measurement infrastructures. These measurements have produced detailed topologies with steadily increasing temporal resolution, but concerns exist about the ability of active measurements to measure the true Internet topology. Difficulties in ensuring the accuracy of every individual measurement when millions of measurements are made daily, and concerns about the bias that might result from measurements along the tree of routes from each vantage point to the wider reaches of the Internet must be addressed. However, early discussions of these concerns were based mostly on synthetic data, oversimplified models or data with limited or biased observer distributions. In this paper, we show the importance that extensive sampling from a broad and well spread set of vantage points has on the resulting topology and bias. The majority of this paper is devoted to a first look at the importance of the distribution quality. We show that diversity in the locations and types of vantage points is required for obtaining an unbiased topology. We analyze the effect that broad distribution has over the convergence of various autonomous systems topology characteristics, and show that although diverse and broad distribution is not required for all inspected properties, it is required for some. Finally, claims against bias in active traceroute sampling are revisited, and we empirically show that diverse and broad distribution can question their conclusions.

The geographical location of Internet IP addresses is important for academic research, commercial and homeland security applications. Thus, both commercial and academic databases and tools are available for mapping IP addresses to geographic locations. Evaluating the accuracy of these mapping services is complex since obtaining diverse large scale ground truth is very hard. In this work we evaluate mapping services using an algorithm that groups IP addresses to PoPs, based on structure and delay. This way we are able to group close to 100,000 IP addresses world wide into groups that are known to share a geo-location with high confidence. We provide insight into the strength and weaknesses of IP geolocation databases, and discuss their accuracy and encountered anomalies.

Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets) is motivated by applications in a variety of areas ranging from biology to the study of the World Wide Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph [Formula: see text]. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter [Formula: see text] and query access to a graph [Formula: see text], outputs an estimate [Formula: see text] such that with high constant probability, [Formula: see text], where [Formula: see text] denotes the number of stars of size [Formula: see text] in the graph. The expected query complexity and running time of the algorithm are [Formula: see text]. We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in [Formula: see text] and the dependence on [Formula: see text]. Our work extends the work of Feige [SIAM J. Comput., 35 (2006), pp. 964–984] and Goldreich and Ron [Random Structures Algorithms, 32 (2008), pp. 473–493] on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-3 paths in sublinear-time.

Peer-to-Peer (p2p) networks are used for sharing content by millions of users. Often, meta-data used for searching is missing or wrong, making it difficult for users to find content. Moreover, searching for new content is almost impossible. Recommender systems are unable to handle p2p data due to inherent difficulties, such as implicit ranking, noise and the extreme dimensions and sparseness of the network.

The usage of peer-to-peer (p2p) networks for music information retrieval (MIR) tasks is gaining momentum. P2P file sharing networks can be used for collecting both search queries and files from shared folders. The first can be utilized to reveal current taste, users interest, and trends, while the latter can be used for enhancing recommender systems. Both provide opportunities for longitudinal analysis, as queries change over time and content often accumulates. Moreover, spatial analysis can expose cultural differences and the way trends propagate. However, tapping into this fountain of information is far from trivial. This paper presents a novel analysis of the shared folders data-set collected from the Gnutella network. We first present the framework for crawling the network and collecting the data. We then present some data-set characteristics, while focusing on music similarities. The paper sheds light on both the opportunities of using p2p data and its complexities.

When forwarding packets in the Internet, Autonomous Systems (ASes) frequently choose the shortest path in their network to the next-hop AS in the BGP path, a strategy known as hot-potato routing. As a result, paths in the Internet are suboptimal from a global perspective. For peering ASes who exchange traffic without payments, path trading - complementary deviations from hot- potato routing - appears to be a desirable solution to deal with these inefficiencies. In recent years, path trading approaches have been suggested as means for interdomain traffic engineering between neighboring ASes, as well as between multiple ASes to achieve global efficiency. Surprisingly, little is known on the computational complexity of finding path trading solutions, or the conditions which guarantee the optimality or even approximability of a path trading protocol. In this paper we explore the computational feasibility of computing path trading solutions between peering ASes. We first show that finding a path trading solution between a pair of ASes is NP- complete, and that path-trading solutions are even NP-hard to approximate. We continue to explore the feasibility of implementing policies between multiple ASes and show that, even if the bilateral path trading problem is tractable for every AS pair in the set of trading ASes, path trading between multiple ASes is NP- hard, and NP-hard to approximate as well. Despite the above negative results, we show a pseudo-polynomial algorithm to compute path trading solutions. Thus, if the range of the instances is bounded, we show one can compute solutions efficiently for peering ASes. We evaluate the path trading algorithm on pairs of ASes using real network topologies. Specifically, we use real PoP-level maps of ASes in the Internet to show that path trading can substantially mitigate the inefficiencies associated with hot-potato routing.

This paper investigates the Direct Connect (DC) file sharing network, which to the best of our knowledge, has never been academically studied before. We developed a participating agent, in order to gather protocol specific information. We quantify network characteristics such as distribution of users in hubs, hubs geography, queries distribution and trends in shared folder size. We also characterize the typical DC user: A heavy downloader with a particularly large shared folder. Most importantly, we discovered a query duplications problem that drains much of the hubs CPU and bandwidth resources. In the DC network, query facilitation is the most demanding task for hubs and the main factor in the protocol's scalability challenges. We show that in some hubs, up to a third of the queries traffic is duplicated and therefore wasteful. Resolving this problem will dramatically improve hubs performances by reducing the amount of relayed queries and thus permitting larger hub communities.

Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph G. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter 0 < ε < 1 and query access to a graph G, outputs an estimate such that with high constant probability, , where vs(G) denotes the number of stars of size s + 1 in the graph. The expected query complexity and running time of the algorithm are . We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in n and the dependence on ε. Our work extends the work of Feige (SIAM Journal on Computing, 2006) and Goldreich and Ron (Random Structures and Algorithms, 2008) on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-3-paths in sublinear time.

The topology of the Internet has been extensively studied in recent years, driving a need for increasingly complex measurement infrastructures. These measurements have produced detailed topologies with steadily increasing temporal resolution, but concerns exist about the ability of active measurement to measure the true Internet topology. Difficulties in ensuring the accuracy of every individual measurement when millions of measurements are made daily, and concerns about the bias that might result from measurement along the tree of routes from each vantage point to the wider reaches of the Internet must be addressed. However, early discussions of these concerns were based mostly on synthetic data, oversimplified models or data with limited or biased observer distributions. In this paper, we show the importance that extensive sampling from a broad distribution of vantage points has on the resulting topology and bias. We present two methods for designing and analyzing the topology coverage by vantage points: one, when system-wide knowledge exists, provides a near-optimal assignment of measurements to vantage points; while the second one is suitable for an oblivious system and is purely probabilistic. The majority of the paper is devoted to a first look at the importance of the distribution's quality. We show that diversity in the locations and types of vantage points is required for obtaining an unbiased topology. We analyze the effect that broad distribution has over the convergence of various autonomous systems topology characteristics. We show that although diverse and broad distribution is not required for all inspected properties, it is required for some. Finally, some recent bias claims that were made against active traceroute sampling are revisited, and we empirically show that diverse and broad distribution can question their conclusions.

Peer to Peer networks are the leading cause for music piracy but also used for music sampling prior to purchase. In this paper we investigate the relations between music file sharing and sales (both physical and digital) using large Peer-to-Peer query database information. We compare file sharing information on songs to their popularity on the Billboard Hot 100 and the Billboard Digital Songs charts, and show that popularity trends of songs on the Billboard have very strong correlation (0.88-0.89) to their popularity on a Peer-to-Peer network. We then show how this correlation can be utilized by common data mining algorithms to predict a song's success in the Billboard in advance, using Peer-to-Peer information.

Peer-to-peer (p2p) content sharing networks are commonly used by millions of users for sharing music files, often performed by artists even before becoming mainstream. In such networks, as well as modern Web 2.0 services, users with similar musical taste often share similar files. This results in songs that have similar properties to be shared together by many users, where the higher the number of song co-occurrences in different users, the stronger is the indication of a tight relationship between these songs. In this work we leverage this feature and propose methods for detecting these "natural" clusters of similar songs. The resulting clusters are shown to be useful in recommender systems, as they almost mitigate the need to use meta-data which is known to be noisy due to its user-generated nature. We present data collected from the Gnutella network and its properties and show two techniques for recommending content to users, one is based on clustering similar-minded users and the other creates song similarity graph and maps users to clusters based on their songs. We show that both techniques result in relatively accurate recommendations, indicating that p2p networks can be leveraged for creating useful recommender systems that can be used for easier content retrieval.

Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone. We explain the problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, node elevation ad-hoc routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic ad-hoc routing solutions.

Point of presence (PoP) level Internet maps are promising for tasks such as reasoning about the Internet evolution in time or Internet delay estimation. We thus suggest an efficient algorithm for generating PoP level Internet maps directly from the traceroute measurement results. The algorithm avoids the noisy process of interface aggregation to routers. The PoP level maps we obtain are annotated with PoP level link delay. Both the map topography and the link delay estimation for tens of ASes were validated with a combination of DNS names and two geo-IP databases, and were found satisfactory.

We consider an abstraction of the problem of managing buffers where traffic is subject to service level agreements (SLA). In our abstraction of SLAs, some packets are marked as ldquocommittedrdquo and the others are marked as ldquoexcess.rdquo The service provider must on one hand deliver all committed packets, and on the other hand can get extra revenue for any excess packet delivered. We study online algorithms managing a buffer with limited space, whose task is to decide which packets should be delivered and which should be dropped. Using competitive analysis, we show how to utilize additional buffer space and link bandwidth so that the number of excess packets delivered is comparable to the best possible by any off-line algorithm, while guaranteeing that no arriving committed packet is ever dropped. Simulations of such traffic (alone and combined with additional best-effort traffic) show that the performance of our algorithm is in fact much better than our analytical guarantees.

Record label companies would like to identify potential artists as early as possible in their careers, before other companies approach the artists with competing contracts. The vast number of candidates makes the process of identifying the ones with high success potential time consuming and laborious. This paper demonstrates how datamining of P2P query strings can be used in order to mechanize most of this detection process. Using a unique intercepting system over the Gnutella network, we were able to capture an unprecedented amount of geographically identified (geo-aware) queries, allowing us to investigate the diffusion of music related queries in time and space. Our solution is based on the observation that emerging artists, especially rappers, have a discernible stronghold of fans in their hometown area, where they are able to perform and market their music. In a file sharing network, this is reflected as a delta function spatial distribution of content queries. Using this observation, we devised a detection algorithm for emerging artists, that looks for performers with sharp increase in popularity in a small geographic region though still unnoticable nation wide. The algorithm can suggest a short list of artists with breakthrough potential, from which we showed that about 30% translate the potential to national success.

Service level agreements (SLAs) are contracts signed between a provider and a customer to govern the amount of traffic that will be serviced. This work pinpoints an important problem faced by the Internet service provider (ISP) which is to be able to differentiate between the services given to aggregates of multiple TCP connections. The metro-Ethernet access network, the differentiated services (DiffServ) architecture and the ATM reference model are three architectural models where edge routers perform traffic metering and coloring of aggregated flows according to the SLA. Finer color marking was suggested to improve differentiation quality. We observe that increasing the number of colors indeed provides a good differentiation between the aggregates according to the committed and the excess rates. We also show that the token bucket coloring policies, which are widely used for this purpose, prefer short packets and mark them with higher priority colors. The differentiation process is more difficult for the short TCP connections that remain in the slow start phase, than for the long connections that are usually in the congestion avoidance phase.

No abstract available.

During the last two decades three important architectural models were designed and standardized: the ATM reference model, the Differentiated Services (DiffServ) architecture and recently the Metro-Ethernet (MEF), the evolving Ethernet-based access network. Although the three architectures provide a substantially different networking model, they all assume inter-AS service level agreements (SLAs), where edge routers perform traffic metering or policing according to the SLA traffic parameters over an aggregate stream (An aggregate is a group of connections, for example all the connections of a small company, and the agreement controls an aggregate) and labels each packet as it arrives according to its conformance. The core routers, using e.g., active queue management mechanisms, identify the packet and react, accordingly. The different packet marking differentiates between service aggregate. All the above standards suggest multiple SLA parameters, using an average committed rate and an average peak rate, each with its own allowed amount of burstiness.

Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone.We explain he problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, Node Elevation Ad-hoc Routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic ad-hoc routing solutions.

We present an anti-pirate revocation scheme for broadcast encryption systems (e.g., pay TV), in which the data is encrypted to ensure payment by users. In the systems we consider, decryption of keys is done on smartcards and key management is done in-band. Our starting point is a scheme of Naor and Pinkas. Their basic scheme uses secret sharing to remove up to t parties, is information-theoretic secure against coalitions of size t , and is capable of creating a new group key. However, with current smartcard technology, this scheme is only feasible for small system parameters, allowing up to about 100 pirates to be revoked before all the smartcards need to be replaced. We first present a novel implementation method of their basic scheme that distributes the work among the smartcard, set-top terminal, and center. Based on this, we construct several improved schemes for many revocation rounds that scale to realistic system sizes. We allow up to about 10,000 pirates to be revoked using current smartcard technology before recarding is needed. The transmission lengths of our constructions are on par with those of the best tree-based schemes. However, our constructions have much lower smartcard CPU complexity: only O (1) smartcard operations per revocation round (a single 10-byte field multiplication and addition), as opposed to the complexity of the best tree-based schemes, which is polylogarithmic in the number of users. We evaluate the system behavior via an exhaustive simulation study coupled with a queueing theory analysis. Our simulations show that with mild assumptions on the piracy discovery rate, our constructions can perform effective pirate revocation for realistic broadcast encryption scenarios.

We identify two typical problems in WLAN hotspots that result in unbounded unfairness between upstream and downstream flows. The first unfairness problem arises due to the uniformity of the MAC layer protocol at the access point (AP) and user nodes that result in equal share to the AP and the user nodes but not to the individual flows. The second unfairness problem arises due to the inability of the physical layer to distinguish frame errors due to hidden terminal based collisions and frame errors due to poor signal strength. We present FairMAC, a deployable solution that addresses these unfairness problems without requiring a change to the 802.11 protocol. Thus, our solution is immediately deployable in the millions of currently operational hotspots. We evaluate the performance of our protocol using simulations and a prototype implementation. We show that FairMAC provides fair access to all the flows regardless whether they are originating at the AP or a host.

In this paper we look at TCP data which was passively collected from an edge ISP, and analyze it to obtain some new results and deeper understanding of TCP loss process. The focus of our study is to identify the 'root cause' links, i.e., the links that are responsible for the majority of the losses or reorders found on the end-to-end TCP connection. We suggest a new root cause criterion and a cost-effective algorithm to identify the root cause links. The algorithm incorporates a new out-of-sequence packet classification technique which is interesting by itself. We test our algorithm on the collected and simulated data and analytically justify its correctness. The simulation results show that the algorithm has a 95% detection rate with 10% false detection rate. We also analyze TCP temporal loss process, and found that the burst loss size is geometrically distributed. We analyze the TCP time-out loss indication under the Bernoulli loss model, which is the simplest model that can cause a geometric distribution, and show that the behavior of the TCP loss process is not different than when tail drop is assumed.

Many Internet multicast applications such as teleconferencing and remote diagnosis have quality-of-service (QoS) requirements. It is a challenging task to build QoS constrained multicast trees with high performance, high success ratio, low overhead, and low system requirements. This paper presents a new scalable QoS multicast routing protocol (SoMR) that has very small communication overhead and requires no state outside the multicast tree. SoMR achieves the favorable tradeoff between routing performance and overhead by carefully selecting the network sub-graph in which it conducts the search for a path that can support the QoS requirement, and by auto-tuning the selection according to the current network conditions. Its early-warning mechanism helps to detect and route around the real bottlenecks in the network, which increases the chance of finding feasible paths for additive QoS requirements. SoMR minimizes the system requirements; it relies only on the local state stored at each router. The routing operations are completely decentralized.

We investigate the problem of finding the minimum delay application-layer multicast trees, such as the trees constructed in overlay networks. It is accepted that shortest path trees are not a good solution for the problem since such trees can have nodes with very large degree, termed high load nodes. The load on these nodes makes them a bottleneck in the distribution tree, due to computation load and access link bandwidth constrains. Many previous solutions limited the maximal degree of the nodes by introducing arbitrary constraints. In this work, we show how to directly map the node load to the delay penalty at the application host, and create a new model that captures the trade offs between the desire to select shortest path trees and the need to constrain the load on the hosts. In this model the problem is shown to be NP-hard. Therefore, we present a logarithmic approximation algorithm and an alternative heuristic solution. Our heuristic algorithm is shown by simulations to be scalable for large group sizes, and produces results that are very close to optimal.

It was noted in recent years that the Internet structure resembles a star with a highly connected core and long stretched tendrils. In this work we present a new quantity, the Internet geometric curvature, that captures the above observation by a single number. We embed the Internet distance metric in a hyperbolic space with an optimal curvature and achieve an accuracy better than achieved before for the Euclidean space. This proves our hypothesis regarding the internet curvature. We demonstrate the strength of our embedding with two applications: selecting the closest server and building an application level multicast tree.

Distance estimation is important to many Internet applications. It can aid a World Wide Web client when selecting among several potential candidate servers or among candidate peer-to-peer servers. It can also aid in building efficient overlay or peer-to-peer networks that react dynamically to changes in the underlying Internet. One of the approaches to distance (i.e., time delay) estimation in the Internet is based on placing tracer stations in key locations and conducting measurements between them. The tracers construct an approximated map of the Internet after processing the information obtained from these measurements. This work presents a novel algorithm, based on algebraic tools, that computes additional distances, which are not explicitly measured. As such, the algorithm extracts more information from the same amount of measurement data. Our algorithm has several practical impacts. First, it can reduce the number of tracers and measurements without sacrificing information. Second, our algorithm is able to compute distance estimates between locations where tracers cannot be placed. To evaluate the algorithm's performance, we tested it both on randomly generated topologies and on real Internet measurements. Our results show that the algorithm computes up to 50%-200% additional distances beyond the basic tracer-to-tracer measurements.

This paper studies the problem of electing a small number of representatives (council) out of a (possible large) group of anonymous candidates. The problem arises in scenarios such as multicast where, to avoid feedback implosion, a small subset of the receivers is chosen to provide feedback on network conditions. We present several algorithms for this problem and analyze the expected number of messages and rounds required for their convergence. In particular, we present an algorithm that almost always converges in one round using a small number of messages (for typical council size) when the number of hosts is known. In the case where the number of hosts is unknown (and too large to be polled), our algorithms converge in a small number of rounds that improves previous results by Bolot et al. (1994).

Embedding of a graph metric in Euclidean space efficiently and accurately is an important problem in general with applications in topology aggregation, closest mirror selection, and application level routing. We propose a new graph embedding scheme called Big-Bang Simulation (BBS), which simulates an explosion of particles under a force field derived from embedding error. BBS is shown to be significantly more accurate compared to all other embedding methods, including GNP. We report an extensive simulation study of BBS compared with several known embedding schemes and show its advantage for distance estimation (as in the IDMaps project), mirror selection, and topology aggregation.

This work presents a thorough investigation of the structure of multicast trees cut from the Internet and power-law topologies. Based on both generated topologies and real Internet data, we characterize the structure of such trees and show that they obey the rank-degree power law; that most high degree tree nodes are concentrated in a low diameter neighborhood; and that the sub-tree size also obeys a power law. Our most surprising empirical finding suggests that there is a linear ratio between the number of high-degree network nodes, namely nodes whose tree degree is higher than some constant, and the number of leaf nodes in the multicast tree (clients). We also derive this ratio analytically. Based on this finding, we develop the fast algorithm, that estimates the number of clients, and show that it converges faster than one round trip delay from the root to a randomly selected client.

As local area wireless networks based on the IEEE 802.11 standard see increasing public deployment, it is important to ensure that access to the network by different users remains fair. While fairness issues in 802.11 networks have been studied before, this paper is the first to focus on TCP fairness in 802.11 networks in the presence of both mobile senders and receivers. In this paper, we evaluate extensively through analysis, simulation, and experimentation the interaction between the 802.11 MAC protocol and TCP. We identify four different regions of TCP unfairness that depend on the buffer availability at the base station, with some regions exhibiting significant unfairness of over 10 in terms of throughput ratio between upstream and downstream TCP flows. We also propose a simple solution that can be implemented at the base station above the MAC layer that ensures that different TCP flows share the 802.11 bandwidth equitably irrespective of the buffer availability at the base station.

Embedding of a graph metric in Euclidean space efficiently and accurately is an important problem in general with applications in topology aggregation, closest mirror selection, and application level routing. We propose a new graph embedding scheme called Big-Bang simulation (BBS), which simulates an explosion of particles under force field derived from embedding error. BBS is shown to be significantly more accurate, compared to all other embedding methods including GNP. We report an extensive simulation study of BBS compared with several known embedding scheme and show its advantage for distance estimation (as in the IDMaps project), mirror selection and topology aggregation.

We present an anti-pirate revocation scheme for broadcast encryption systems (e.g., pay TV), in which the data is encrypted to ensure payment by users. In the systems we consider decryption of keys is done on smart cards and key management is done in-band. Our starting point is a recent scheme of Naor and Pinkas. The basic scheme uses secret sharing to remove up to t parties, is information theoretic secure against coalitions of size t, and is capable of creating a new group key. However with current smart card technology, this scheme is only feasible for small system parameters, allowing up to about 100 pirates to be revoked before all the smart cards need to be replaced. We first present a novel implementation method of their basic scheme that distributes the work in novel ways among the smart card, set-top terminal, and center. Based on this, we construct several improved schemes for many stateful revocation rounds that scale to realistic system sizes. We allow up to about 10000 pirates to be revoked using current smart card technology before re-carding is needed. The transmission lengths of our constructions are on a par with those of the best tree-based schemes. However, our constructions have much lower smartcard CPU complexity: only O(1) smartcard operations per revocation round, as opposed to a poly-logarithmic complexity of the best tree-based schemes. We evaluate the system behavior via an exhaustive simulation study. Our simulations show that with mild assumptions on the piracy discovery rate, our constructions can perform effective pirate revocation for realistic broadcast encryption scenarios.

Various monitoring and performance evaluation tools generate considerable amount of low priority traffic. This information is not always needed in real time, and thus could often be delayed by the network without hurting functionality. This paper proposes a new framework to handle this low priority, but resource consuming traffic in such a way that it will incur a minimal interference with the higher priority traffic, and thus improve the network goodput. The key idea is to allow the network nodes to delay data by locally storing it. This can be done, for example, in the active network paradigm. We show that the active network paradigm can improve the network's goodput dramatically even if a very simple scheduling algorithm is used. To obtain minimal cost schedules we define an optimization problem that we call the travelling miser problem. We study primarily the on-line variant of this problem, which is of greater practical interest. For this problem we develop an enhanced scheduling strategy, study its characteristics in a restricted case, and evaluate its performance through a rigorous simulation study.

The competition on clients attention requires sites to update their content frequently. As a result, a large percentage of Web pages are semi-dynamic, i.e., change quite often and stay static between changes. The cost of maintaining consistency for such pages discourages caching solutions. We suggest here an integrated architecture for the scalable delivery of frequently changing hot pages. Our scheme enables sites to dynamically select whether to cyclically multicast a hot page or to unicast it, and to switch between multicast and unicast mechanisms in a transparent way. Our scheme defines a new protocol, called h.t.t.p.m. In addition, it uses currently deployed protocols, and dynamically directs browsers seeking for a URL to multicast channels, while using existing DNS mechanisms. Thus, we enable sites to deliver content to a growing number of users at less cost and during denial of service attacks, while reducing load on core links. We report simulation results that demonstrate the advantages of the integrated architecture, and its significant impact on server and network load, as well as clients delay.

The simple network management protocol (SNMP) is a widely used standard for management of devices in Internet protocol networks. Part of the protocol great success is due to its simplicity; all the managed information is kept in a management information base (MIB) that can be accessed using SNMP queries to a software agent. We develop a general model that abstract the data retrieval process in SNMP. In particular, we study the amount of queries (communication) and time needed to randomly access an element in this model. It turns out that this question has practical importance. For some network management applications, e.g., MIB browsing, there is a need to traverse portions of a MIB tree, especially tables, in both directions. While the GetNext request defined by the SNMP standard allows an easy and fast access to the next columnar object instance or next scalar object, there is no corresponding operator defined in the SNMP framework for retrieving the previous MIB object instance. This, in effect, allows an efficient MIB traversal only in one direction and makes the search in the reverse direction problematic. This paper presents and analyzes the GetPrev application, a tool that enables the retrieval of the previous instances of a columnar objects or scalar MIB objects. Our GetPrev application uses only standard SNMP GetNext and Get requests to carry on a fast and bandwidth efficient search for the required object instance. For example, as predicted by our analysis and shown by our experiments, retrieving a value of the last columnar object instance in a large forwarding table (ipForwardTable) containing about 3000 entries can take several minutes using a sequence of the GetNext requests (the straightforward approach used, e.g., by widely deployed snmpwalk and snmptable applications). The GetPrev application presented in this paper retrieves this value using no more than 20 GetNext requests (in most cases about seven requests), taking no more than a second (i.e., it is two orders of magnitude faster and two to three orders of magnitude less bandwidth consuming).

Web content providers and content distribution network (CDN) operators often set up mirrors of popular content to improve performance. Due to the scale and decentralized administration of the Internet, companies have a limited number of sites (relative to the size of the Internet) where they can place mirrors. We formalize the mirror placement problem as a case of constrained mirror placement, where mirrors can only be placed on a preselected set of candidates. We study performance improvement in terms of client round-trip time (RTT) and server load when clients are clustered by the autonomous systems (AS) in which they reside. Our results show that, regardless of the mirror placement algorithm used, for only a surprisingly small range of values there is an increase in the number of mirror sites (under the constraint) effective in reducing the client to server RTT and server load. In this range, we show that greedy placement performs the best.

For some important network management applications, e.g., MIB browsing, there is a need to traverse portions of an MIB tree, especially tables, in both directions. While the GetNext request defined by the SNMP standard allows an easy and fast access to the next columnar object instance or the next scalar object, there is no corresponding operator in the SNMP framework for retrieving the previous MIB object instance. This allows an efficient MIB traversal only in one direction and makes the search in the reverse direction problematic. This paper presents SNMP GetPrev a tool that substantially optimizes retrieval of the previous instances of a columnar objects or scalar MIB objects. Our GetPrev application uses only standard SNMP GetNext and Get requests to carry on a fast and bandwidth efficient search for the required object instance. As we show, our application is two orders of magnitude faster and two to three orders of magnitude less bandwidth consuming when compared to the more traditional approaches.

Internet service providers and infrastructural companies often employ mirrors of popular content to decrease client download time and server load. Due to the immense scale of the Internet and decentralized administration of the networks, companies have a limited number of sites (relative to the size of the Internet) where they can place mirrors. Mirrors of popular content are usually replicated on every site to maximize reachability to clients. We study the performance improvements as the number of mirrors increases under different placement algorithms subject to the constraint that mirrors can be placed only at certain locations. Although there are extensive theoretical studies on center placement and, analytical and empirical studies on Web cache placement, we are not aware of any published literature on mirror placement especially in the case of constrained mirror placement. Our results show that increasing the number of mirror sites under the constraint is effective in reducing client download time and reducing server load only for a surprisingly small range of values regardless of the mirror placement algorithm.

Distance estimation is important to many Internet applications, most notably for a WWW client that needs to select a server among several potential candidates. Current approaches to distance (i.e., time delay) estimation in the Internet are based on placing Tracer stations in key locations and conducting measurements between them. The Tracers construct an approximated map of the Internet after processing the information obtained from these measurements. This work presents a novel algorithm, based on algebraic tools, that computes additional distances, which are not explicitly measured. As such, the algorithm extracts more information from the same amount of measurement data. Our algorithm has several practical imparts. First, it can reduce the number of Tracers and measurements without sacrificing information. Second, our algorithm is able to compute distance estimates between locations where Tracers cannot be placed. This is especially important when unidirectional measurements are conducted, since such measurements require specialized equipment which cannot be placed everywhere. To evaluate the algorithm's performance, we tested it both on randomly generated topologies and on real Internet measurements. Our results show that the algorithm computes up to 50-200% additional distances beyond the basic Tracer-to-Tracer measurements.

This paper addresses the problem of aggregating the topology of a sub-network in a compact way with minimum distortion. The problem arises from networks that have a hierarchical structure, where each sub-network must advertise the cost of routing between each pair of its border nodes. The straight-forward solution of advertising the exact cost for each pair has a quadratic cost which is not practical. We look at the realistic scenario of networks where all links are bidirectional, but their cost (or distance) in the opposite directions might differ significantly. The paper presents a solution with distortion that is bounded by the logarithm of the number of border nodes and the square-root of the asymmetry in the cost of a link. This is the first time that a theoretical bound is given to an undirected graph. We show how to apply our solution to PNNI, and suggest some other heuristics that are tested to perform better than the provenly bounded solution.

There is an increasing need to quickly and efficiently learn network distances, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, Internet content providers often place data and server mirrors throughout the Internet to improve access latency for clients, and it is necessary to direct clients to the nearest mirrors based on some distance metric in order to realize the benefit of the mirrors. We suggest a scalable Internet-wide architecture, called IDMaps, which measures and disseminates distance information on the global Internet. Higher level services can collect such distance information to build a virtual distance map of the Internet and estimate the distance between any pair of IP addresses. We present our solutions to the measurement server placement and distance map construction problems in IDMaps. We show that IDMaps can indeed provide useful distance estimations to applications such as nearest mirror selection.

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new Qos-aware multicast routing protocol. QMRP achieves scalability by significantly reducing the communication overhead in constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high-level design of QMRP makes it operable on top of any unicast routing algorithm both intra-domain and inter-domain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees.

The IDMaps project aims to provide a distance map of the Internet from which relative distances between hosts on the Internet can be gauged. Many distributed systems and applications can benefit from such a distance map service, for example, a common method to improve user-perceived performance of the Internet is to place data and server mirrors closer to clients. When a client tries to access a mirrored server, which mirror should it access? With IDMaps, the closest mirror can be determined based on distance estimates between the client and the mirrors. In this paper we investigate both graph theoretic methods and ad hoc heuristics for instrumenting the Internet to obtain distance maps. We evaluate the efficacy of the resulting distance maps by comparing the determinations of the closest replica using known topologies against those obtained using the distance maps.

The future Internet is expected to support applications with quality of service (QoS) requirements. To this end several mechanisms have been suggested in the IETF to support signaling, the most promising among them is DiffServ. An important problem in this framework is how to partition the QoS requirements of an application along a selected path. The problem which is in general NP complete, was solved for continuous convex cost functions by Lorenz and Orda (1999). This work concentrates on discrete cost functions, and presents efficient exact and approximated solutions for various conditions of the problem. We also show that the more complex problem of QoS sensitive routing with discrete cost functions is hard, but has a fully polynomial approximation scheme.

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new QoS-aware multicast routing protocol. QMRP achieves scalability by significantly reducing the communication overhead of constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high level design of QMRP makes it operable on top of any unicast routing algorithm in both intradomain and interdomain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees.

The future Internet is expected to support applications with quality of service (QoS) requirements. To this end, several mechanisms are suggested in the IETF; the most promising among them is DiffServ. An important problem in this framework is how to partition the QoS requirements of an application along a selected path. The problem which is, in general, NP-complete, was solved for continuous convex cost functions by Lorenz and Orda (see IEEE/ACM Trans. Networking. vol.6, p.768-78, 1998 and Proc. IEEE INFOCOM'99, p.246-53, 1999). This paper concentrates on discrete cost functions, which better model the existing and upcoming mechanisms in the Internet. We present efficient exact and approximated solutions for various conditions of the problem. We also show that although the more complex problem of QoS sensitive routing with discrete cost functions is hard, it has a fully polynomial approximation scheme.

The problem we address is how to communicate securely with a set of users (the target set) over an insecure broadcast channel. This problem occurs in two application domains: satellite/cable pay TV and the Internet MBone. In these systems, the parameters of major concern are the number of key transmissions and the number of keys held by each receiver. In the Internet domain, previous schemes suggest building a separate key tree for each multicast program, thus incurring a setup cost of at least k log k per program for target sets of size k. In the pay TV domain, a single key structure is used for all programs, but known theoretical bounds show that either very long transmissions are required, or that each receiver needs to keep prohibitively many keys. Our approach is targeted at both domains. Our schemes maintain a single key structure that requires each receiver to keep only a logarithmic number of establishment keys for its entire lifetime. At the same time our schemes admit low numbers of transmissions. In order to achieve these goals, and to break away from the theoretical bounds, we allow a controlled number of users outside the target set to occasionally receive the multicast. This relaxation is appropriate for many scenarios in which the encryption is used to force consumers to pay for a service, rather than to withhold sensitive information. For this purpose, we introduce f-redundant establishment key allocations, which guarantee that the total number of recipients is no more than f times the number of intended recipients. We measure the performance of such schemes by the number of key transmissions they require, by their redundancy f, and by the probability that a user outside the target set (a free-rider) will be able to decrypt the multicast. We prove a new lower bound, present several new establishment key allocations, and evaluate our schemes' performance by extensive simulation.

This paper studies the problem of where to place network caches. Emphasis is given to caches that are transparent to the clients since they are easier to manage and they require no cooperation from the clients. Our goal is to minimize the overall flow or the average delay by placing a given number of caches in the network. We formulate these location problems both for general caches and for transparent en-route caches (TERCs), and identify that, in general, they are intractable. We give optimal algorithms for line and ring networks, and present closed form formulae for some special cases. We also present a computationally efficient dynamic programming algorithm for the single server case. This last case is of particular practical interest. It models a network that wishes to minimize the average access delay for a single web server. We experimentally study the effects of our algorithm using real web server data. We observe that a small number of TERCs are sufficient to reduce the network traffic significantly. Furthermore, there is a surprising consistency over time in the relative amount of web traffic from the server along a path, lending a stability to our TERC location solution. Our techniques can be used by network providers to reduce traffic load in their network.

In connection-oriented networks, resource reservations must be made before data can be sent along a route. For short or bursty connections, a selected route must have the required resources to ensure appropriate communication with regard to desired quality-of-service (QoS). For example, in ATM networks, the route setup process considers only links with sufficient resources and reserves these resources while it advances toward the destination. The same concern for QoS routing appears in datagram networks such as the Internet, when applications with QoS requirements need to reserve resources along pinned routes. In this paper, we analyze the performance of multi-path routing algorithms and compare them to single-path reservation that might be persistent, i.e., retry after a failure. The analysis assumes that the routing process reserves resources while it advances toward the destination, thus there is a penalty associated with a reservation that cannot be used. Our analysis shows that while multi-path reservation algorithms perform comparably to single-path reservation algorithms, either persistent or not, the connection-establishment time for multi-path reservation is significantly lower. Thus, multi-path reservation becomes an attractive alternative for interactive applications such as World Wide Web browsing.

Networks deploying hierarchical routing are recursively partitioned into sub-networks that do not reveal the full details of their internal structure outside their domains. Instead, an aggregated view of certain parameters that are associated with traversal within such sub-networks between their border nodes is advertised. The ATM PNNI standard and the Internet Nimrod architecture both adopt this approach for routing. This paper studies the effectiveness of ATM hierarchical routing protocols on networks with different hierarchical structures by simulation. Our study shows that in general, the hierarchical source routing performs well compared to the global routing strategy which imposes no hierarchy, while utilizing less storage and communication overhead. For certain networks and topologies, the hierarchical routing performs better than the global routing. Different hierarchies imposed on the same topologies have significantly different performance on the throughput and routing delay. This suggests the necessity of studying the hierarchy design for communication networks using hierarchical routing.

Max-min is a frequently praised criterion for flow control despite its limitations. In practice, the fast rate of changes in the connection layout in modern networks makes it hard for any flow control algorithm to converge to an optimal point. In such an environment, it might be better to trade accuracy with speed. We present algorithms that relax the optimality criterion of the max-min flow fairness but achieve a fast convergence time that is logarithmic in the link bandwidth and not a function of the number of active connections (or sessions). The relaxation we use requires rates to be increased or decreased by a certain factor, 1+/spl epsiv/, or in other words, assigned rates can only be a natural power of some basic bandwidth 1+/spl epsiv/. Under this criterion, the quiescent time of our flow control algorithms is log/sub 1+/spl epsiv//B, where B is the maximum link bandwidth in minimum allocation units. This is a great improvement over the super-linear quiescent time of known algorithms both exact and approximated.

In the future, global networks will consist of a hierarchy of subnetworks called domains. For reasons of both scalability and security, domains will not reveal details of their internal structure to outside nodes. Instead, these domains will advertise only a summary, or aggregated view, of their internal structure, e.g., as proposed by the ATM PNNI standard. This work compares, by simulation, the performance of several different aggregation schemes in terms of network throughput (the fraction of attempted connections that are realized), and network control load (the average number of crankbacks per realized connection.) Our main results are: the minimum spanning tree is a good aggregation scheme; exponential link cost functions perform better than min-hop routing; our suggested logarithmic update scheme that determines when re-aggregation should be computed can significantly reduce the computational overhead due to re-aggregation with a negligible decrease in performance.

This paper addresses the problem of aggregating the topology of a sub-network in a compact way with minimum distortion. The problem arises from networks that have a hierarchical structure, where each sub-network must advertise the cost of routing between each pair of its border nodes. The straightforward solution of advertising the exact cost for each pair has a quadratic cost which is not practical. We look at the realistic scenario of networks where all links are bidirectional, but their cost (or distance) in the opposite directions might differ significantly. The paper presents a solution with distortion that is bounded by the logarithm of the number of border nodes and the square-root of the asymmetry in the cost of a link. This is the first time that a theoretical bound is given to an undirected graph. We show how to apply our solution to the ATM PNNI standard.

In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM networks is an example of an algorithm that does this using a sequential crank-back mechanism. We suggest the implementation of resource reservation along several routes in parallel. We present an analytical model that demonstrates that when there are several routes to the destination it pays to attempt reservation along more than a single route. Following this analytic observation, we present a family of algorithms that route and reserve resources along parallel subroutes. The algorithms of the family represent different trade-offs between the speed and the quality of the established route. The presented algorithms are simulated against several legacy algorithms, including the PNNI crank-back, and exhibit higher network utilization and faster connection set-up time.

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In this paper, we concentrate on a class of such policies that achieves fairness by allocating transmission quotas to nodes. For such policies, we provide mechanisms for improving delays and increasing overall throughput without compromising fairness.

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In the paper the authors concentrate on a class of such policies that achieve fairness by allocating transmission quotas to nodes. For such policies, they provide mechanisms for improving delays and increasing overall throughput without compromising fairness.>