We study a map of the Internet (at autonomous systems level), by introducing and using method k -shell decomposition methods percolation theory fractal geometry, to find model for structure Internet. In particular, our analysis uses information on connectivity network shells separate, in unique (no parameters) way, into three subcomponents: ( i ) nucleus that is small (≈100 nodes), very well connected globally distributed subgraph; ii subcomponent able connect bulk without congesting...

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, content providers often place data server mirrors throughout the improve access for clients, it necessary direct clients nearest based on some distance metric order realize benefit mirrors. We suggest a scalable Internet-wide architecture, called IDMaps, which measures disseminates information global Internet. Higher level...

Today's Internet maps, which are all collected from a small number of vantage points, falling short being accurate. We suggest here paradigm shift for this task. DIMES is distributed measurement infrastructure the that based on deployment thousands light weight agents around globe. describe rationale behind deployment, discuss its design trade-offs and algorithmic challenges, analyze structure as it seen with DIMES.

This paper studies the problem of where to place network caches. Emphasis is given caches that are transparent clients since they easier manage and require no cooperation from clients. Our goal minimize overall flow or average delay by placing a number in network. We formulate these location problems both for general en-route (TERCs), identify that, general, intractable. give optimal algorithms line ring networks, present closed form formulae some special cases. also computationally...

As local area wireless networks based on the IEEE 802.11 standard see increasing public deployment, it is important to ensure that access network by different users remains fair. While fairness issues in have been studied before, this paper first focus TCP presence of both mobile senders and receivers. In paper, we evaluate extensively through analysis, simulation, experimentation interaction between MAC protocol TCP. We identify four regions unfairness depend buffer availability at base...

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

Internet service providers and infrastructural companies often employ mirrors of popular content to decrease client download time server load. Due the immense scale decentralized administration networks, have a limited number sites (relative size Internet) where they can place mirrors. Mirrors are usually replicated on every site maximize reachability clients. We study performance improvements as increases under different placement algorithms subject constraint that be placed only at certain...

In connection-oriented networks, resource reservations must be made before data can sent along a route. For short or bursty connections, selected route have the required resources to ensure appropriate communication with regard desired quality-of-service (QoS). example, in ATM setup process considers only links sufficient and reserves these while it advances toward destination. The same concern for QoS routing appears datagram networks such as Internet, when applications requirements need...

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

Identifying the type of a network flow or specific application has many advantages, but become harder in recent years due to use encryption, e.g., by VPN and Tor. Current solutions rely mostly on handcrafted features then apply supervised learning techniques for classification. We introduce novel approach encrypted Internet traffic classification transforming basic data into picture, FlowPic, using known image deep techniques, Convolutional Neural Networks (CNNs), identify category...

Identifying the type of a network flow or specific application has many advantages, such as, traffic engineering, to detect and prevent types that violate organization's security policy. The use encryption, as VPN, makes identification challenging. Current solutions rely mostly on handcrafted features then apply supervised learning techniques for classification. We introduce novel approach encrypted Internet classification by transforming basic data into an intuitive picture, <italic...

Web content providers and distribution network (CDN) operators often set up mirrors of popular to improve performance. Due the scale decentralized administration Internet, companies have a limited number sites (relative size Internet) where they can place mirrors. We formalize mirror placement problem as case constrained placement, only be placed on preselected candidates. study performance improvement in terms client round-trip time (RTT) server load when clients are clustered by autonomous...

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

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

Estimating distances in the Internet has been studied recent years due to its ability improve performance of many applications, e.g., peer-to-peer realm. One scalable approach estimate between nodes is embed some d dimensional geometric space and use pair this as for real distances. Several algorithms were suggested past do low Euclidean spaces. It was noted that structure a highly connected core long stretched tendrils, most routing paths tendrils pass through core. Therefore, we suggest...

Low-rank Matrix Factorization (MF) methods provide one of the simplest and most effective approaches to collaborative filtering. This paper is first investigate problem efficient retrieval recommendations in a MF framework. We reduce model an apparently simple task finding maximum dot-product for user vector over set item vectors. However, best our knowledge efficiently general case has never been studied. To this end, we propose two techniques search -- (i) index vectors binary...

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS routing protocols are pivotal in enabling new receivers join a group. However, current either too restrictive their search for feasible path between receiver and the tree, or burden network excessive overhead. We propose QMRP, Qos-aware protocol. QMRP achieves scalability by significantly reducing communication overhead constructing yet it retains high chance...

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

In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM an example of algorithm that does this using a sequential crank-back mechanism. We suggest the implementation reservation along several routes in parallel. present analytical model demonstrates when there are destination pays attempt more than single route. Following analytic observation, we family algorithms route reserve resources parallel subroutes....

Detecting and counting the number of copies certain subgraphs (also known as network motifs or graphlets) is motivated by applications in a variety areas ranging from biology to study World Wide Web. Several polynomial-time algorithms have been suggested for detecting occurrences motifs. However, need more efficient arises when input graph very large, indeed case many motif counting. In this paper we design sublinear-time approximating constant-size . That is, our do not read whole graph,...