Distributed self-stabilizing placement of replicated resources in emerging networks

Emerging large scale distributed networking systems, such as P2P file sharing systems, sensor networks, and ad hoc wireless networks, require replication of content, functionality, or configuration to enact or optimize communication tasks. The placement of these replicated resources can significantly impact performance. We present a novel self-stabilizing, fully distributed, asynchronous, scalable protocol that can be used to place replicated resources such that each node is "close" to some copy of any object. We describe our protocol in the context of a graph with colored nodes, where a node's color indicates the replica/task that it is assigned. Our combination of theoretical results and simulation prove stabilization of the protocol, and evaluate its performance in the context of convergence time, message transmissions, and color distance. Our results show that the protocol generates colorings that are close to the optimal under a set of metrics, making such a protocol ideal for emerging networking systems.     

The impact of multicast layering on network fairness

Many definitions of fairness for multicast networks assume that sessions are single rate, requiring that each multicast session transmits data to all of its receivers at the same rate. These definitions do not account for multirate approaches, such as layering, that permit receiving rates within a session to be chosen independently. We identify four desirable fairness properties for multicast networks, derived from properties that hold within the max-min fair allocations of unicast networks. We extend the definition of multicast max-min fairness to networks that contain multirate sessions, and show that all four fairness properties hold in a multirate max-min fair allocation, but need not hold in a single-rate max-min fair allocation. We then show that multirate max-min fair rate allocations can be achieved via intra-session coordinated joins and leaves of multicast groups. However, in the absence of coordination, the resulting max-min fair rate allocation uses link bandwidth inefficiently, and does not exhibit some of the desirable fairness properties. We evaluate this inefficiency for several layered multirate congestion control schemes, and find that, in a protocol where the sender coordinates joins, this inefficiency has minimal impact on desirable fairness properties. Our results indicate that sender-coordinated layered protocols show promise for achieving desirable fairness properties for allocations in large-scale multicast networks     

An Analysis of Generalized Slotted-Aloha Protocols

Aloha and its slotted variation are commonly deployed medium access control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each other's presence (the "hidden terminal problem'). Competing 802.11 gateways, as well as most modern digital cellular systems, like GSM, are examples. This paper models and evaluates the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted-Aloha protocols. The protocol is implemented as a two-state system, where the probability that a node transmits in a given slot depends on whether the node's prior transmission attempt was successful. Using Markov models, we evaluate the channel utilization and fairness of this class of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node selfishly maximizing its own throughput, and attacker nodes attempting to jam the channel. If all nodes are selfish and strategically attempt to maximize their own throughput, a situation similar to the traditional Prisoner's Dilemma arises. Our results reveal that under heavy loads, a greedy strategy reduces the utilization, and that attackers cannot do much better than attacking during randomly selected slots.     

Flood search under the California Split rule

We consider flood search on a line and show that no algorithm can achieve an average-case competitive ratio of less than 4 when compared to the optimal off-line algorithm. We also demonstrate that the optimal scanning sequences are described by simple recursive relationships that yield surprisingly complex behavior related to Hamiltonian chaos.     

Detecting shared congestion of flows via end-to-end measurement

Current Internet congestion control protocols operate independently on a per-flow basis. Recent work has demonstrated that cooperative congestion control strategies between flows can improve performance for a variety of applications, ranging from aggregated TCP transmissions to multiple-sender multicast applications. However, in order for this cooperation to be effective, one must first identify the flows that are congested at the same set of resources. We present techniques based on loss or delay observations at end hosts to infer whether or not two flows experiencing congestion are congested at the same network resources. Our novel result is that such detection can be achieved for unicast flows, but the techniques can also be applied to multicast flows. We validate these techniques via queueing analysis, simulation and experimentation within the Internet. In addition, we demonstrate preliminary simulation results that show that the delay-based technique can determine whether two TCP flows are congested at the same set of resources. We also propose metrics that can be used as a measure of the amount of congestion sharing between two flows     

Trends in technology management revisited

Although many in the field of technology management do decry the ultra-narrow and nitpicking foci of some published papers and research projects, systematic, credible research in the field does require a high level of partitioning-as compared with general policy research or management consulting practice. Here, the author discusses fairly specific research approaches to some of the current trends of technology management, given that some of them, indeed, represent fairly broad issues in the field     

SOS: an architecture for mitigating DDoS attacks

We propose an architecture called secure overlay services (SOS) that proactively prevents denial of service (DoS) attacks, including distributed (DDoS) attacks; it is geared toward supporting emergency services, or similar types of communication. The architecture uses a combination of secure overlay tunneling, routing via consistent hashing, and filtering. We reduce the probability of successful attacks by: 1) performing intensive filtering near protected network edges, pushing the attack point perimeter into the core of the network, where high-speed routers can handle the volume of attack traffic and 2) introducing randomness and anonymity into the forwarding architecture, making it difficult for an attacker to target nodes along the path to a specific SOS-protected destination. Using simple analytical models, we evaluate the likelihood that an attacker can successfully launch a DoS attack against an SOS-protected network. Our analysis demonstrates that such an architecture reduces the likelihood of a successful attack to minuscule levels. Our performance measurements using a prototype implementation indicate an increase in end-to-end latency by a factor of two for the general case, and an average heal time of less than 10 s.