The Media Futures group of UCL Computer Science Department will offer a new MSc/MRes programme on the Web Science starting from September 2012.
Dr. Shi Zhou will teach a new core module on Complex Networks & Web.
Our paper on modelling network traffic fluctuations is recently published in the IEEE Circuit and Systems Magazine.
Title: Traffic Fluctuations on Weighted Networks
Authors: Yichao Zhang, Shi Zhou, et al.
Abstract: Traffic fluctuation has so far been studied on unweighted networks. However, many real traffic systems are better represented and understood as weighted networks, where nodes and links are assigned some weight values representing their physical properties such as capacity and delay. Here, we introduce a general random diffusion (GRD) model to investigate the traffic fluctuations on weighted networks, where a random walk’s choice of route is affected not only by the number of links a node has, but also by the weights of individual links. We obtain analytical solutions that characterize the relation between the average traffic and the fluctuations through nodes and links. Our analysis is supported by results of extensive numerical simulations. We observe that the value ranges of the average traffic and the fluctuations, through nodes or links, increase dramatically with the level of heterogeneity in link weights. This highlights the key role that link weight plays in traffic fluctuation and the necessity to study traffic fluctuations on weighted networks.
Network
We will present our latest work on modelling the Internet routing at the IEEE ICC’2012, which is the flagship annual conference of the IEEE Communications Society.
Title: Valley-free violation in Internet routing – Analysis based on BGP Community data
Authors: Vasileios Giotsas and Shi Zhou
Abstract: 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 cannot 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.
Our work on Internet IPv4/IPv6 routing is published in the Proceedings of the ACM SIGCOMM 2011 conference.
Title: Detecting and Assessing the Hybrid IPv4/IPv6 AS Relationships
Authors: Vasileios Giotsas and Shi Zhou
Abstract: The business relationships between the Autonomous Systems (ASes) play a central role in the Internet BGP routing. Existing algorithms on inferring AS relationships relied on AS connectivity data and were profoundly based on the valley-free rule. They have produced inaccurate and conflicting results, and they did not distinguish between IPv4 and IPv6. Recently we proposed a new approach to infer AS relationships using the BGP Community and Local Preference attribute data, which provide an unexploited wealth of reliable information on the AS relationships. We obtain the actual AS relationships for 72% of the IPv6 AS links that are visible in the RouteViews and RIPE RIS repositories in August 2010. 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. We call them the hybrid IPv4/IPv6 relationships. We observe that the hybrid links are present in a large number of IPv6 AS paths and a significant portion of such paths do not follow 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.
Our latest paper on the Internet AS relationships is now available at
| arXiv:1106.2417 [cs.NI] |
Title: Inferring AS relationships from BGP Attributes
Authors: Vasileios Giotsas and Shi Zhou
Abstract: Business relationships between autonomous systems (AS) are crucial for Internet routing. Existing algorithms used heuristics to infer AS relationships from AS topology data. In this paper we propose a different approach to infer AS relationships from more informative data sources, namely the BGP Community and Local Preference attributes. These data contain rich information on AS routing policies and therefore closely reflect AS relationships. We accumulate the BGP data from RouteViews, RIPE RIS and route servers in August 2010 and February 2011. We infer the AS relationships for 39% of links that are visible in our BGP data. They cover the majority of links among the Tier-1 and Tier-2 ASes. The BGP data also allow us to discover special relationship types, namely hybrid relationship, partial-transit relationship, indirect peering relationship and backup links. Finally we evaluate and analyse the problems of the existing inference algorithms.
Vasileios started his PhD in September 2009. He is funded by an EPSRC DTA studentship.
Congratulations to my PhD student Anil Bawa-Cavia. His paper “Sensing the Urban: Using location-based social network data in urban analysis” has won the “Best Student Paper” Award at the 1st Workshop on Pervasive Urban Applications (PURBA) hosted by the 9th International Conference on Pervasive Computing in San Francisco, CA in June 2011.
Anil started his PhD in September 2009. He is funded by the EPSRC project SCALE, which is led by his second supervisor, Prof. Michael Batty, Chairman of Centre for Advanced Spatial Analysis (CASA), UCL.
His personal website, quotesque.net, provides a collection of interesting staff. Highly recommended!
I was recently appointed as a committee member of the BCS Internet Specialist Group.
I highly recommend you to attend the talks and events organised by the IS Group.
We recently published two journal articles on networks in collaboration with researchers at the Institute of Computing Technology, Chinese Academy of Sciences.
Shi Zhou receives an award from The Royal Academy of Engineering through the Research Exchanges with China/Inida scheme. The award will support Shi’s research visit to the City University of Hong Kong in November 2010.
My PhD student Anil Bawa-Cavia will give a talk on Microplexes. Anil is funded by a
joint project with UCL Centre for Advanced Spatical Analysis (CASA).
Anil Bawa-Cavia – PhD Researcher
Location: GALTON LECTURE
Time: 17:40, Wednesday, March 24, 2010
Title: Microplexes
A look at morphology, integration, density, energy and flows in microscopic complex systems – microprocessors, neural nets and cell biology – and how this can inform our analysis of urban spatial systems.
Recent Comments