Abstracts for Jean Walrand

The EECS Research Summary for 2003


An Extension of Shortest-Path Algorithms and Their Properties

Antonis Dimakis
(Professor Jean Walrand)

I have been studying the structural properties of shortest path algorithms. The problem can be thought of as an inverse to the classical shortest path problem. In particular, assume that given a network of nodes, e.g., a network of autonomous systems (AS) in the context of BGP, each of these has totally ordered preferences over all possible paths that lead to a specified destination. The problem that we attempt to answer is whether link costs exist such that the ordering induced by such costs coincides with the order given originally.

Necessary and sufficient conditions in terms of the original path order are derived, which characterize when such costs exist. Interestingly, in some cases where appropriate link costs do not exist, if such cost existed, then the calculation of the optimal routes by each node could have been solved efficiently in a distributed fashion by employing some variant of the Bellman-Ford routing algorithm. It turns out that one can extend the notion of link cost to a transformation, and by appropriately defining the action of this transformation on the integers. The classical shortest path algorithm is a particular case of this formulation, where each integer corresponds to a transformation, and each transformation acts by translation by the associated integer. This extended formulation of shortest paths allows us to find appropriate extended link costs that match the given path preferences in cases where the classical formulation fails. Currently, I am looking at methods for efficiently implementing these extended link costs.

An application of this problem occurs in the design of routing algorithms that are robust under node or link failures. In general, the system operator has a fallback plan of alternative routes that are to be followed when failures occur. In the occurrence of failures, the surviving nodes do not need to solve a new optimization problem in order to calculate how failed routes need to be rerouted. In particular, by running a standard shortest path algorithm, e.g., Bellman-Ford, using extended link costs, perhaps each node can find the optimal rerouting.

In the future, I plan to study the properties of extended classes of shortest path algorithms. Although, a single set of extended costs which match arbitrary preferences over an arbitrary network topology exist, their implementation is intractable. What one wants is the construction of a universal set of extended costs that always give a solution in the cases where path preferences posses a pre-specified structure. Thus, I plan to devise a set of theoretical tools that give constructable solutions for the given preference structures.


Send mail to the author : (dimakis@eecs.berkeley.edu)

Providing Quality of Service over an Ad Hoc Wireless Network

Eduardo Magana1, Daniel Morato2, Hoi-Sheung Wilson So, and William Hodge3
(Professor Jean Walrand)
(DARPA) IPTO N66001-00-C-8062

The tremendous success of 802.11b wireless networks ensures such wireless network deployments will become ubiquitous in the near future. An ad hoc wireless network based on ubiquitous and low cost 802.11b interfaces would be an ideal candidate for disaster relief applications during times when traditional networks fail to provide adequate network services. However, 802.11b was not designed with providing QoS in mind, and it is not trivial to provide QoS guarantees over such networks. To bridge the gap, we investigate the problem of providing soft QoS guarantees in a small sized 802.11b ad hoc wireless network.

One of the major challenges in providing QoS is in deciding routes for application traffic. At the heart of this routing problem is finding the right model for describing the shared nature of the wireless medium. We used a simplified model for the delay and bandwidth constraints of a sharing medium based on the use of a cell. We proved, through an implementation, that this simple model captures the important charateristics of the shared medium constraints specific to wireless routing networks. The simplicity of the model allows us to use an integer linear program to find the optimal routes. Furthermore, the routes chosen by using the simple model are verified by a faster than real time simulation that can use more sophisticated interference models that can provide more accurate results but are much harder to analyze. In order to cope with the inevitable differences between the simple model and the more accurate MAC layer simulation model, we invented a control loop that can search and adapt feasible QoS routes, starting from those calculated from a simple model by incorporating a simulator in the loop. In addition, to compensate for the lack of MAC layer reservation capabilities, we introduced a simple distributed scheduling algorithm to rate limit the best effort traffic to protect the QoS requested by high priority applications. Finally, we completed a proof of concept implementation of all of the above features to show that our architecture is both self-contained and sufficient to provide QoS in an ad hoc wireless network using only off-the-shelf 802.11b network equipment.

1Postdoctoral Researcher
2Postdoctoral Researcher
3Staff

Send mail to the author : (so@eecs.berkeley.edu)

Eliminating the Free Rider in Peer to Peer Networks

Eric Chi
(Professor Jean Walrand)
(DARPA) IPTO N66001-00-C-8062

Recent measurements have shown that peer-to-peer file transfer volumes comprise almost half of the traffic carried across metropolitan area networks. What is alarming is that peer-to-peer applications have existed for less than five years. What is even more surprising is that these peer-to-peer communities continue to thrive even though measurements show that only a small fraction of the users are willing to share their content with other users.

In this research, we develop models that predict this unexpected behavior. Users clearly behave in self interest, often at the expense of other users. Cooperation, however, is highly desired since all users will benefit from a more diverse selection of media. Furthermore, the network performance, e.g., lower link loads and shorter download times, should only improve as sharing increases. Moreover, better network performance should only improve a user's utility.

The problem of predicting and driving the behavior of self-interested independent decision makers has been well studied in the context of game theory. We have developed simple repeated game models and found sub game perfect equilibria of cooperation among all users. We allow users to punish each other by either allowing the users to block another user or even anouncing to other users to stay away from a free-riding user. In this way users have an incentive to cooperate.

Questions still remain, however, in making models that will make the desirable equilibrium unique so that under any initial conditions all the users will eventually choose actions leading to an equilibrium of total cooperation.


Send mail to the author : (echi@eecs.berkeley.edu)

Game Theoretic Modeling of the Exchange between Wireless Access Provider and Paying User

John Musacchio
(Professor Jean Walrand)

The number of deployed 802.11 wireless access point devices has grown dramatically in recent years. In many cases these devices are deployed by individuals or institutions for their own private use, rather than providing wireless access service to other parties. Often these private access points are underutilized, and thus could potentially be used to provide service to users foreign to the owner of the access point, but that lie within the communications radius of the access point. Such a service would be especially valuable for mobile users that are traveling through an area where they cannot establish Internet connectivity in any other way. However, access point owners would incur costs in offering this service. These costs include any performance degradation due to the additional traffic from foreign users, and the possible security risk in allowing foreign users access to their access point and potentially the other hosts connected to that access point. Because of this, access point owners would need incentives to voluntarily offer service to foreign users. One possible incentive would be in the form of payments from the foreign user to the owner of the access point. A problem with this model is that the foreign user and the access point owner cannot trust each other. For example, if the foreign user were to pay in advance for a service, she cannot be certain that the access point owner would actually provide the service after receiving payment. Likewise, if the foreign user agreed to pay after receiving service for some time, the access point owner cannot be certain that the foreign user would actually deliver on the payment promise. Our work focuses on formulating this situation in a game theoretic model, and using this model to find payment schemes that incentize access point owners to allow foreign users to use the access point, that incentivize both parties to carry out any agreed exchange of payment for service, and that require as little communication between the two parties as possible.


Send mail to the author : (musacchj@eecs.berkeley.edu)

Dynamic Provision of Service Level Agreements between Interconnected Networks

Linhai He
(Professor Jean Walrand)
DARPA

Today's Internet is composed of many interconnected autonomous networks, or domains, that operate independently according to their own set of policies. However, providing end-to-end quality of service (QoS) requires a joint effort by all the networks. One approach used in practice is built upon service level agreements (SLA) between domains. When using this approach, one network offers others forwarding services with certain guarantees on QoS. The concatenation of these SLAs then ensures end-to-end QoS for end users.

Our work focuses on the application of voice over IP (VoIP) and illustrates how measurement-based admission control and SLAs can be designed to provide end-to-end QoS in a dynamic, fully decentralized way. A game-theoretic model for the proposed scheme is developed to demonstrate its feasibility and some of its interesting properties.


More information (http://www.eecs.berkeley.edu/~linhai) or

Send mail to the author : (linhai@eecs.berkeley.edu)

Efficient Algorithm and Infrastructure for Managing Protection Paths in a Network

Rajarshi Gupta and Eric Chi
(Professor Jean Walrand)
(DARPA) IPTO N66001-00-C-8062 and Extreme Networks

In many network routing situations, it is necessary to calculate a protection path in addition to a normal path. Applications like MPLS networks and optical networks require backup paths that satisfy various constraints of bandwidth, link or node selection, and ease of configuration.

In this research, we first demonstrate the premise that algorithmic treatments of normal and backup path calculation, configuration, and maintenance should be different from those accorded to normal paths. We demonstrate this through a new hysteresis-based scheme to handle dynamic demands in a network, where the different parameters accorded to normal and backup paths enable better utilization of network resources.

The chief contribution of this work is to present an infrastructure for managing normal and protection paths in a network through a modular suite of algorithms. We present several novel mechanisms to enhance the overall performance. (1) A distributed method of separately calculating normal and backup paths in the network, using link state information. (2) A sophisticated per-link state maintained at each node, which allows optimal sharing of backup bandwidth. (3) Piggybacking the link state information on the reservation ack/nack packets, to implement a very low intensity link state update mechanism. This may be deployed in cases where global link state updates are too costly to use. (4) Asynchronous dynamic reorganization of backup paths to reduce congestion in the network. We apply Markov decision process analysis to quantitatively determine the reduction in blocking probability under various network loads.

We have also developed a simulation model which may be used to verify and evaluate the algorithms developed. The modular simulation model allows specific components to be plugged in or out, and has hooks to capture statistics. It enables us to quantify the gains achieved by adopting the mechanisms listed above, e.g. reduction in blocking probability and specific link loads under fixed total loads applied across source destination pairs in the network.


More information (http://www.eecs.berkeley.edu/~guptar) or

Send mail to the author : (guptar@eecs.berkeley.edu)

Optimal Calculation of Backup Paths in a Network, to Accommodate Dynamic Traffic Demands

Rajarshi Gupta
(Professor Jean Walrand)
Extreme Networks

Many different networking scenarios today require the calculation of a backup path in addition to calculating a normal path thorugh the network. Furthermore, both paths are required to satisfy some quality (i.e., bandwidth) constraints. The traditional methods for calculating the backup paths often do not account for sharing of bandwidth between different backup paths, and consequently utilize the network resources poorly.

In this work, we first present a centralized algorithm to exactly consider the bandwidth sharing on each link across various backup paths, and hence minimize the bandwidth resources used for protection. We take into account disjoint normal paths that can share their backup bandwidths and also consider the fact that normal bandwidth need no longer be reserved along all the links if a link on the path fails, thereby achieving the optimal protection bandwidth reuse.

Finally, we also present a distributed algorithm for the same problem, which results in a solution that is less optimal, but still far more efficient than the naive method.


More information (http://www.eecs.berkeley.edu/~guptar) or

Send mail to the author : (guptar@eecs.berkeley.edu)

Providing QoS for VoIP

Teresa Tung
(Professor Jean Walrand)
DARPA

There is great importance in developing networks that provide some guarantee of QoS in order to accommodate real-time (EF) applications such as VoIP and video. These latency sensitive applications are not worthwhile to use over a network if the provided quality is poor. For instance, telephony type traffic can be carried over the Internet in the form of VoIP, but it can also be carried over a public switched telephone network at a guaranteed quality. In order for VoIP to be a competitive alternative there needs to be similar guarantees in expected quality. Poor quality of these real-time applications in terms of delay is a result of congestion in the network.

My research investigates a scheme that provides QoS for such EF traffic by means of adding packet marking capability within the router. Within a network, one can have certain routers that have the capability of marking a packet at the onset of congestion. By means of such packet marking, network resources can be shared by both EF flows and BE flows. The EF flows are governed by admission control in response to the number of packets marked by the network. As such, an EF flow will only be admitted if the routers the flow will use have the available resources to provide the QoS that the EF flow needs. A BE flow is governed by TCP with ECN wherein a marked packet is treated as a dropped packet. As such, a BE flow will not saturate the network with its transmission, leaving adequate resources to service the EF flows.

Past work includes theortical analysis and simulation results via ns. Current work lies in creating an implementation using laptops as wireless routers wherein more extensive tests can be run on a small network of such routers.


Send mail to the author : (teresat@eecs.berkeley.edu)