BGP-Multipath (BGP-M) is a multipath routing technique for load balancing. Distinct from other techniques deployed at a router inside an Autonomous System (AS), BGP-M is deployed at a border router that has installed multiple inter-domain border links to a neighbor AS. It uses the equal-cost multi-path (ECMP) function of a border router to share traffic to a destination prefix on different border links. Despite recent research interests in multipath routing, there is little study on BGP-M. Here we provide the first measurement and a comprehensive analysis of BGP-M routing in the Internet. We extracted information on BGP-M from query data collected from Looking Glass (LG) servers. We revealed that BGP-M has already been extensively deployed and used in the Internet. A particular example is Hurricane Electric (AS6939), a Tier-1 network operator, which has implemented >1,000 cases of BGP-M at 69 of its border routers to prefixes in 611 of its neighbor ASes, including many hyper-giant ASes and large content providers, on both IPv4 and IPv6 Internet. We examined the distribution and operation of BGP-M. We also ran traceroute using RIPE Atlas to infer the routing paths, the schemes of traffic allocation, and the delay on border links. This study provided the state-of-the-art knowledge on BGP-M with novel insights into the unique features and the distinct advantages of BGP-M as an effective and readily available technique for load balancing.

Botnets in online social networks are increasingly often affecting the regular flow of discussion, attacking regular users and their posts, spamming them with irrelevant or offensive content, and even manipulating the popularity of messages and accounts. Researchers and cybercriminals are involved in an arms race, and new and updated botnets designed to defeat current detection systems are constantly developed, rendering such detection systems obsolete.

This work presents an in-depth forensic analysis of a large-scale spam attack launched by one of the largest Twitter botnets reported in academic literature. The Bursty botnet contains over 500,000; many of which have not been suspended. The bots have generated over 2.8 million spam tweets, with 2.2 million mentions directly targeting over 1.3 million distinct Twitter users. We reveal that the botnet used a network of URL shortening services and redirections to obfuscate the real landing pages. We show that users clicked on these URLs shortly after they were published and in large numbers. We even discovered the botmaster who was behind the whole operation, including creation of the Bursty botnet and registration of the several landing pages, which happen to be phishing websites. Furthermore, we found that this botmaster is still active selling Twitter bot related services. Our work reconstructs the complete course of the spam attacks, from planning to execution. This work provides in depth analysis and insight into the operation of cybercriminals on Twitter, and the cyberspace infrastructure and black-markets that they rely on. Finally, we address how the state-of-the-art bot classifiers are unable differentiate the Bursty bots from normal users, highlighting the need and importance of individual botnet analysis.

It is known that many Twitter users are bots, which are accounts controlled and sometimes created by computers. Twitter bots can send spam tweets, manipulate public opinion and be used for online fraud. Here we report the discovery, retrieval, and analysis of the 'Star Wars' botnet in Twitter, which consists of more than 350,000 bots tweeting random quotations exclusively from Star Wars novels. The botnet contains a single type of bot, showing exactly the same properties throughout the botnet. It is unusually large, many times larger than other available datasets. It provides a valuable source of ground truth for research on Twitter bots. We analysed and revealed rich details on how the botnet was designed and created. As of this writing, the Star Wars bots are still alive in Twitter. They have survived since their creation in 2013, despite the increasing efforts in recent years to detect and remove Twitter bots. We also reflect on the 'unconventional' way in which we discovered the Star Wars bots, and discuss the current problems and future challenges of Twitter bot detection.

Network services are a critical component of today's networks. They apply critical functions (e.g. security, routing or quality of service) to traffic to enhance the network operators and application consumers experience. Today these services are inserted physically on the data-forwarding plane without providing much flexibility to deal with different traffic types or affiliations. Cloud Computing, however, demands policy enforcement on a per-Provider, per-Service and/or per-Tenant basis. In addition, there is an increasing need for dynamic transparent network chaining independent of the underlying transport infrastructure. We first introduce the concept of Universal Cloud Classification as a Service (UCCaaS). Followed by highlighting how it can be leveraged in conjunction with Network Service Headers (NSH) to address above challenges. UCC provides an addressing scheme to isolate traffic streams on a per-provider, per-service and/or per-tenant basis. To enable bi-directional policy enforcement in network functions we extend the UCC proposal by adding source and destination support. NSH is a way to steer network traffic dynamically across a set of network functions. We demonstrate the feasibility and advantages of our UCCaaS + NSH proposal with an example application, where a service chain defines Access Control Lists and traffic rate limiting on a per-Service and per-Tenant basis. Our proposal opens a door for a wide range of cloud-aware network services and functions.

One of the fundamental requirements of Cloud Computing is the capability to provide scalable, transparent and isolated networks. This is achieved by using L2 segmentation via 802.1Q VLANs or overlay approaches such as 802.1ad, VxLAN, "Stateless Transport Tunneling" (STT) or "Network Virtualization using Generic Routing Encapsulation" (NVGRE). All of these technologies struggle to provide the required level of scalability, flexibility, performance and network isolation within a Data Center. Research efforts in the area of classification have fundamentally approached these challenges by introducing identifiers for segmentation or providing overlay solutions to tunnel traffic. However, these research approaches are too specific without tackling the actual Cloud Computing classification challenges. Here, we investigate classification approaches with the goal of introducing a scalable, optional, hierarchical, end-to-end and transparent Layer 3 provider, service and tenant isolation scheme.This proposal addresses major challenges and limitations of current cloud classification schemes by offering these five advantages: (1) hierarchical end-to-end classification, (2) transparency to upper-layer protocols, (3) optional for en-route and endpoint evaluation, (4) flexibility, and (5) improved performance over current overlay technologies. The solution proposal will be implemented and evaluated based on its feasibility, functionality, performance and usability in cloud-related use-cases.

HIV-1 can disseminate between susceptible cells by two mechanisms: cell-free infection following fluid-phase diffusion of virions and by highly-efficient direct cell-to-cell transmission at immune cell contacts. The contribution of this hybrid spreading mechanism, which is also a characteristic of some important computer worm outbreaks, to HIV-1 progression in vivo remains unknown. Here we present a new mathematical model that explicitly incorporates the ability of HIV-1 to use hybrid spreading mechanisms and evaluate the consequences for HIV-1 pathogenenesis. The model captures the major phases of the HIV-1 infection course of a cohort of treatment naive patients and also accurately predicts the results of the Short Pulse Anti-Retroviral Therapy at Seroconversion (SPARTAC) trial. Using this model we find that hybrid spreading is critical to seed and establish infection, and that cell-to-cell spread and increased CD4+ T cell activation are important for HIV-1 progression. Notably, the model predicts that cell-to-cell spread becomes increasingly effective as infection progresses and thus may present a considerable treatment barrier. Deriving predictions of various treatments' influence on HIV-1 progression highlights the importance of earlier intervention and suggests that treatments effectively targeting cell-to-cell HIV-1 spread can delay progression to AIDS. This study suggests that hybrid spreading is a fundamental feature of HIV infection, and provides the mathematical framework incorporating this feature with which to evaluate future therapeutic strategies.

One of the major concerns cloud computing platforms face today is the lack of a unique identification of the "who" within the network infrastructure. State-of-the-art technologies (such as VLANs or IP addresses) lack functionality to cope with the highly dynamic and scalable, ever changing and virtualized cloud-enabled data center infrastructures. A shared and limited address space or the loss of identification across boundaries render classification unusable for per-tenant, per-service or per-cloud-provider policies. In this work, we introduce the concept of a classification mechanism that is fine-grained enough to associate tenants, services and cloud providers to their network streams. The Tenant-ID, Service-ID and Cloud-ID is added as a tag to Layer 3 packets throughout the consumer-to-service communication. We argue that the proposed service and tenant isolation concept is generic enough to be applicable across the whole cloud environment, thereby eliminating current limitations and enabling new network functionality.

Classification ambiguity in Cloud Computing has a catastrophic impact on cloud providers, their services and tenants. It limits the application of various network services to traffic either inside or outside a cloud. This is because IP addresses, VLANs and other transport-level technologies lack the functionality to cope with the highly dynamic, scalable and virtualized environment of cloud-enabled data centers. In this paper, we present the prototype design and discuss its features. We also evaluate the UCC proposal in a cloud-enabled data center environment. Our examination of the compatibility, performance and usability of UCC shows that this scheme is not only feasible, easy to implement, but also has significant advantages over other classification techniques. For example, it enables highly desirable functionality such as traffic volume-based data center billing. Imminent follow-up efforts include scalability testing of UCC on the open Internet. We are confident the UCC scheme can provide a long-term, practical and flexible solution for cloud classification with significant benefits.

Cloud Computing facilitates the new generation of IT and the provisioning of services by introducing virtualization concepts throughout the network. Multi-tenancy introduces the capability to share cloud assets among service users. Service providers currently lack innovative means to enable true multi-tenancy in a cloud environment. There is an urgent need for technologies that introduce tenant security, traffic identification and tenant separation for better billing and fairness. This paper introduces a technology that tackles all these requirements by defining the concept of a Tenant-ID that is incorporated into the OSI Layer 2 frame header. We outline the concept of Tenant-IDs, the adapted 802.1q header and a way to automatically configure tenants via Cloud automation tools and software-defined networking approaches. The paper concludes by outlining interoperability to relevant layer-2 protocols and by introducing use-cases benefiting from the Tenant-ID concept.

The AS topology incompleteness problem is derived from difficulties in the discovery of p2p links, and is amplified by the increasing popularity of Internet eXchange Points (IXPs) to support peering interconnection. We describe, implement, and validate a method for discovering currently invisible IXP peering links by mining BGP communities used by IXP route servers to implement multilateral peering (MLP), including communities that signal the intent to restrict announcements to a subset of participants at a given IXP. Using route server data juxtaposed with a mapping of BGP community values, we can infer 206K p2p links from 13 large European IXPs, four times more p2p links than what is directly observable in public BGP data. The advantages of the proposed technique are threefold. First, it utilizes existing BGP data sources and does not require the deployment of additional vantage points nor the acquisition of private data. Second, it requires only a few active queries, facilitating repeatability of the measurements. Finally, it offers a new source of data regarding the dense establishment of MLP at IXPs.

The Internet Autonomous System (AS) topology has important implications on end-to-end routing, network economics and security. Despite the significance of the AS topology research, it has not been possible to collect a complete map of the AS interconnections due to the difficulties involved in discovering peering links. The problem of topology incompleteness is amplified by the increasing popularity of Internet eXchange Points (IXPs) and the “flattening” AS hierarchy. A recent study discovered that the number of missing peering links at a single IXP is larger than the total number of the observable peering links. As a result a large body of research focuses on measurement techniques that can alleviate the incompleteness problem. Most of these proposals require the deployment of additional BGP vantage points and traceroute monitors. In this paper we propose a new measurement methodology for improving the discovery of missing peering links through the publicly available BGP data. Our approach utilizes the traffic engineering BGP Communities used by IXPs' Route Servers to implement multi-lateral peering agreements. We are able to discover 36K additional p2p links from 11 large IXPs. The discovered links are not only invisible in previous BGP-based AS topology collections, but also 97% of those links are invisible to traceroute data from CAIDA's Ark and DIMES projects for June 2012. The advantages of the proposed technique are threefold. First, it provides a new source of previously invisible p2p links. Second, it does not require changes in the existing measurement infrastructure. Finally, it offers a new source of policy data regarding multilateral peering links at IXPs.

The valley-free rule defines patterns of routing paths that allow the Internet Autonomous Systems (AS) to minimize their routing costs through selective announcement of BGP routes. The valley-free rule has been widely perceived as a universal property of the Internet BGP routing that is only violated due to transient configuration errors. Analysing the valley-free violations is important for a better understanding of BGP behaviour and inter-domain routing. This requires knowledge of the business relationships between ASes. The ground-truth data of AS relationships are not publicly available. Previous algorithms have inferred AS relationships based on the assumption that AS paths should be valley-free. Such inference results are biased and can not provide an objective assessment of the valley-free rule. Instead we extract the AS relationships directly from routing polices encoded in the BGP Community attribute. We are able to extract the business relationship of more than 30% of AS links based on BGP data collected from the RouteViews and RIPE RIS repositories in June 2011. We use our inferred AS relationships to analyse the valley-free violations in BGP routing. We reveal that the non valley-free paths are significantly more frequent than previously reported. As many as one fifth of AS paths in IPv6 BGP updates are valley paths. A substantial portion of these valley paths are persistent during the whole month of measurement. These observations strongly indicate that the valley paths are not merely a result of BGP misconfigurations. Instead they are the outcome of complex business relationships and deliberate policies by ASes using distinct unconventional models.

The business relationships between the Autonomous Systems (ASes) play a central role in the BGP routing. The existing relationship inference algorithms are profoundly based on the valley-free rule and generalize their inference heuristics for both the IPv4 and IPv6 planes, introducing unavoidable inference artifacts. To discover and analyze the Type-of-Relationship (ToR) properties of the IPv6 topology we mine the BGP Communities attribute which provides an unexploited wealth of reliable relationship information. We obtain the actual relationships for 72% of the IPv6 AS links that are visible in the RouteViews and RIPE RIS repositories. Our results show that as many as 13% of AS links that serve both IPv4 and IPv6 traffic have different relationships depending on the IP version. Such relationships are characterized as hybrid. We observe that links with hybrid relationships are present in a large number of IPv6 AS paths. Furthermore, an unusually large portion of IPv6 AS paths violate the valley-free rule, indicating that the global reachability in the IPv6 Internet requires the relaxation of the valley-free rule. Our work highlights the importance of correctly inferring the AS relationships and the need to appreciate the distinct characteristics of IPv6 routing policies.

In this article, we briefly summarize the motivation, content and structure of the CNIKM'09 workshop.

The Internet topology at the autonomous systems (AS) level exhibits a complex structure. The positive-feedback preference (PFP) model was designed to capture two properties of the Internet, namely the degree distribution and the rich-club connectivity. It has been a pleasant surprise that the model also reproduces a large number of other properties of the Internet, including the degree correlation, the triangle coefficient, the shortest path length etc. Here we explain that the success of the PFP model is due to the inherent structural constraints present in the Internet topology. This work advances our understanding of the Internet structure. It also highlights the importance for a network model to choose carefully its target properties. For example, as we show, an Internet model based on the degree distribution only could produce network structures completely different from the real Internet.

The first complete measurement of the Chinese Internet topology at the autonomous systems (AS) level based on traceroute data probed from servers of major ISPs in mainland China is presented. Both the Chinese Internet AS graph and the global Internet AS graph can be accurately reproduced by the positive-feedback preference model with the same parameters. This result suggests that the Chinese Internet preserves well the topological characteristics of the global Internet. This is the first demonstration of the Internet's topological fractality, or self-similarity, performed at the level of topology evolution modelling.

When modeling the behavior of the Internet, it is vital to obtain a good description of its topology because structure fundamentally affects function. We introduce the positive-feedback preference (PFP) model, which is the most precise and complete Internet topology generator to date. The model uses two generic mechanisms based on observations on Internet history data, namely the interactive growth of new nodes and new internal links, combined with a novel nonlinear preferential probability, which is described by a positive-feedback mechanism. The PFP model accurately reproduces many topological properties of the AS-level Internet, including degree distribution, the maximum degree, rich-club connectivity, disassortative mixing, shortest-path length, short cycles and betweenness centrality. These properties are relevant to crucial network behaviors, such as routing efficiency, flexibility and traffic distribution. The PFP model can be used in more representative Internet simulations.