Communication Networks

I am now mainly working on algorithmic aspects of communication networks. Here is a brief descriptions on some of the things I have been working on:

Minimizing the Price of Anarchy in Internet-like Environments 

The choice of intradomain paths in the Internet is left to the discretion of each Autonomous System (AS) and as a result paths in the Internet as suboptimal from a global perspective. We suggest a mechanism to reduce the price of anarchy in Internet-like environments without the use of payments. We suggest that ASes trade with the resource which is most available to them - their intradomain
paths. We formally show that this path trading mechanism provides appropriate incentives for the trading ASes,
and indeed enables reducing the price of anarchy in the system. We show that while ASes can trade
paths in pairs, obtaining optimal solutions for sets of ASes, and in particular minimizing the price of
anarchy caused by hot-potato routing is computationally hard. To test whether ASes can indeed be
motivated to conduct path trading, we applied the mechanism on a PoP-level map of ASes obtained
from measurement of real AS topologies in the Internet. In comparison to hot-potato routing, our results
suggest that ASes can indeed reduce their expected costs as a result of path trading, which shows we
can provide incentives that apply for real network topologies and as a result reduce of the price of
anarchy.

Backup and Functionality in Networks

In networks characterized by broad degree distribution,

such as the Internet AS graph, node significance is often

associated with its degree or with centrality metrics which relate

to its reachability and shortest paths passing through it. Such

measures do not consider availability of efficient backups of

the node and thus often fail to capture its contribution to the

functionality and resilience of the network operation.

The Quality of Backup (QoB) and Alternative

Path Centrality (APC) are complementary methods

which enable relevant analysis of node significance, considering

backup efficiency.  Here is a link to the paper.  Through this work, I also

developed the Autonomous Systems' Breadth First Search (ASBFS) algorithm which is a linear

shortest path algorithm for graphs with valley-free restrictions such as the Internet AS graph.  Here is the ASBFS paper.

Categorization of the Internet's Topology

 The Distance Hierarchies is a method to categorize the Internet according to the maximal sets of vertices which are reachable within a certain distance.  This method categorizes the Internet as Matryoshki (nested dolls)-like sets, and enables a new perspective on which AS nodes in the Internet are the "core" nodes and on what level.  As shown, obtaining the Distance Hierarchies is computationally hard.  We can show that the problem remains computationally hard, even if one "magically" obtains the maximal clique in the graph.  We show how the Internet topology allows categorizing the majority of the AS graph. 

I am now working on a new mathematical model for networks which impose transitivity restrictions on their edges, like the Internet AS graph.  Beside communication networks, social and biological networks are also examples of such networks.  The idea is to expand the model of a graph in a manner which will allow application of regular graph algorithms.  These networks have unique mathematical properties which arise from their transitivity restrictions.  This work is now also in progress, though a written manuscript will be available soon.