|
Toronto Networking Seminar: Seminar series on computer networks organized by the Dept. of Computer Science and Dept. of Electrical and Computer Engineering, University of Toronto
Online social networks have revolutionized the way we interact and share information over the Internet, and social networking applications such as YouTube, Flickr, MySpace, Facebook, etc., have millions of active users. While already being enormously popular, these applications only scratch the surface of online social networking possibilities. The goal of this research project is to investigate and find new and creative ways of how to make use of social networking applications to enrich people's everyday lives. Answering this question poses challenging and fascinating research problems that require both creativity and rigorous mathematical analysis. As part of the project, we are developing novel mathematical models of how online social networks are formed, and are trying to find creative ways to use the resulting network topologies to efficiently share/distributed information. While our work focuses on online social networks, our models and results also provide surprising insights into how and why the social networks that we form and use in our everyday life are so important and efficient.
The concept of Peer-to-Peer (P2P) networking has received considerable interests recently. A P2P network has no centralized management but all network functionalities are provided by the peers (nodes) themselves in a distributed manner. The most popular P2P systems are file sharing systems, however P2P networking is not restricted to file sharing, but could be applied to any system where peers pool their resources (e.g., files, storage, compute cycles, communication bandwidth) in order to inexpensively handle tasks that would normally require large costly servers. In our research, we focus on issues evolving around resource allocation and cooperation among peers.
Rate control is one of the most important problems in computer networks. If input rates to a network are left uncontrolled, then the offered load may exceed the network capacity causing congestion, i.e. buffers fill up and packets have to be dropped. It is well known that network congestion has a negative impact on performance, potentially leading to a throughput collapse. Rate control schemes should therefore (a) produce a predictable throughput, (b) allow a distributed implementation and (c) allocate network bandwidth among applications (flows) in a fair manner.
Rate control schemes with such important properties have already been proposed for point-to-point networks. To realize end-to-end congestion control in the current Internet, compatible rate control schemes for both point-to-point (wide area) networks and local area networks become necessary and therefore greatly desired. To this end, we consider rate control schemes that have similar properties for contention-based local area networks. Such schemes are thus widely applicable to members of this class of networks; from slotted Aloha to CSMA/CA.
In addition to rate control, we are also intersted in distributed scheduling policies for wireless networks. A key objective of these distributed policies is to achieve any throughput within the capacity region of the network. In this project we focus on Carrier Sense Multiple Access (CSMA) schedulers where nodes sense whether the channel is idle before making an attempt to transmit a packet. For networks single-hop networks where all nodes are within transmission range of each other, it is well-known that CSMA schedulers achieve network capacity as the sensing time becomes negligible (relative to the packet transmission durations). However, the analysis of the CSMA schedulers for general networks is complicated by the fact that the sizes of the idle and transmission durations are not equal which leads to an asynchronous operation of the network. In our research project, we developped a systematic framework for the analysis and design of CSMA schedulers for networks with primary interference constraints. Our results rely on a fixed point approximation, called the CSMA fixed point, to characterize the service rates of CSMA schedulers in networks with primary interference constraints. This formulation relies on an independence assumption which was also used in the analysis of loss networks. We show that under some assumptions the fixed point approximation is asymptotically accurate for large networks with a small sensing time. This is the first time that it has been shown that CSMA-type of random access policies are throughput optimal for wireless networks with primary intereference constraints.
A wireless ad hoc network is a collection of nodes which form a network independently of any fixed base station infrastructure. As opposed to networks which use routers to support networking functions such as packet routing and forwarding, in ad hoc networks these functions are provided by the nodes (hosts) themselves. Initially, wireless ad hoc networks were studied in the realm of military or disaster relief situations; more recently, wireless ad hoc networks have also been envisioned for commercial application such as providing Internet connectivity for nodes that are not in transmission range of a wireless access point. The wireless medium and the infra-structureless nature of wireless ad hoc networks pose a variety of problems that are distinctly different from traditional networks with a fixed infrastructure. For example, routing algorithms for wireless ad hoc networks have to be able to cope with frequent and unpredictable topology changes. Nodes are generally battery powered; thus energy is a precious resource that has to be carefully managed by the nodes in order to avoid an early termination of their activity. Due to interference, ad hoc networks are generally characterized by bandwidth-constrained and variable-capacity links which makes bandwidth allocation difficult. The nature of of ad hoc networks also challenges the traditional approach of separating network protocols into distinct layers in order to help handling the enormous complexity of network design. Due to energy constraints and the nature of the wireless channel, the interdependencies between layers in wireless ad hoc networks are so prominent that it is often desirable to jointly design and optimize protocols at different layers. However, even when layers are kept separate the above problems are challenging and currently not fully understood. In addition to the characteristics outlined above, an important feature of wireless ad hoc networks is that nodes have to cooperate in relaying data packets for other nodes. In applications of wireless ad hoc networks for emergency and military situations all of the nodes belong to a single authority and cooperation among nodes can be assumed. However, in commercial applications nodes may not belong to a single authority but are in fact independent entities that can freely decide how they use their resources such as battery energy and transmission bandwidth. Since relaying a packet will incur a cost (of transmission bandwidth and energy) to a node, in this situation nodes may not necessarily volunteer to relay packets for other nodes and an additional mechanism is needed to give nodes an incentive to cooperate. Our research focuses on routing and mechanisms for stimulating cooperation.
The growth of the Internet both in terms of users and contents in the last few years has resulted in serious performance problems and degraded user experience for a large set of applications. Content Delivery (or, Distribution) Network is an effective approach to improve Internet service quality. CDNs evolves with the promise of higher scalability for the content providers and higher availability and lower user response time for the end users. Loosely speaking, a CDN is architecture of network surrogate servers, arranged for efficient delivery of web items. CDN replicates the content from the place of origin to the surrogate servers scattered over the Internet and serves a request from a surrogate server close to where the request originates. Like other business organizations, CDNs compete with each other to increase their market share. Many important design issues of a CDN such as strategies for surrogate server allocation and placement, dynamic content placement, server load balancing etc. are bound to depend on the technical and marketing strategies of the competitor CDNs. Our ongoing activities include understanding the competition among several CDNs in a competitive economy, studying how the above design issues may be influenced by this competition. Also, there is an increasing trend among big enterprises having campuses in different continents to build their own content delivery network instead of outsourcing the work to CDN companies. In this case, there is no competition. Still it requires a trade off between financial benefit and performance gain. Understanding this trade off and looking into the design factors from this point of view is our another research goal.
Today's "best effort" Internet is enough to support services such as web browsing and e-mail, however emerging applications such as Voice-over-IP (VoIP) and real-time video require more predictable quality of service (QoS). Using ideas from economic theory where multiple demands for a scarce resource are mediated through a market, we are studying price-based (market-based) approaches to QoS.