Search

Population protocols (Angluin et al. in PODC, 2004) are a formal model of sensor networks consisting of identical mobile devices. Two devices can interact and thereby change their states. Computations are infinite sequences of interactions satisfying a strong fairness constraint. A population protocol is well specified if for every initial configuration C of devices, and every computation starting at C, all devices eventually agree on a consensus value depending only on C. If a protocol is well specified, then it is said to compute the predicate that assigns to each initial configuration its consensus value. While the computational power of well-specified protocols has been extensively studied, the two basic verification problems remain open: Is a given protocol well specified? Does a given protocol compute a given predicate? We prove that both problems are decidable by reduction to the reachability problem of Petri nets. We also give a new proof of the fact that the predicates computed by well-defined protocols are those definable in Presburger arithmetic (Angluin et al. in PODC, 2006). [ABSTRACT FROM AUTHOR]

Hierarchical cubic networks (HCN) have been introduced as interconnection networks for massively parallel systems. This topology is based on hypercubes, and thus benefits from their desirable properties such as a small diameter. However, an HCN supersedes a hypercube in many ways: for instance, the number of links per node in an HCN is significantly lower than that of a hypercube of the same size, while their diameters remain similar. In this paper we address the decycling problem in an HCN. It consists in finding a node set of minimum size such that excluding these nodes from the network ensures an acyclic (cycle-free) network. This is a critical problem with many applications, and notably in parallel computing as it allows for the prevention of resource allocation issues such as deadlocks, livelocks and starvations. We propose an efficient algorithm generating in an $$n$$ -dimensional HCN a decycling set of at most $$2^{2n-1} - (2^{2n-2}/n + \lfloor 2^{n-1}/n\rfloor )$$ nodes. [ABSTRACT FROM AUTHOR]

We describe an encrypted communication principle that forms a secure link between two parties without electronically saving either of their keys. Instead, random cryptographic bits are kept safe within the unique mesoscopic randomness of two volumetric scattering materials. We demonstrate how a shared set of patterned optical probes can generate 10 gigabits of statistically verified randomness between a pair of unique 2 mm3 scattering objects. This shared randomness is used to facilitate information-theoretically secure communication following a modified one-time pad protocol. Benefits of volumetric physical storage over electronic memory include the inability to probe, duplicate or selectively reset any bits without fundamentally altering the entire key space. Our ability to securely couple the randomness contained within two unique physical objects can extend to strengthen hardware required by a variety of cryptographic protocols, which is currently a critically weak link in the security pipeline of our increasingly mobile communication culture. [ABSTRACT FROM AUTHOR]

With the rapid development of electronic commerce transactions on mobile devices, achieving secure communications between communication parties is an important issue. The typical solutions are authenticated key agreement protocols, designed to efficiently implement secure channels for two or more parties communicating via a public network by providing them with a shared secret key, called a session key. In this paper, we propose two key agreement schemes based on elliptic curve cryptosystems suited for mobile environments. The first one is an identity-based remote mutual authentication with key agreement scheme, and it is used to establish a session key between the client and the server. In the second one, we extend the proposed two-party authentication key exchange scheme to develop an efficient three-party authenticated key agreement scheme for establishing a session key between two users with the help of a trusted server. Both our proposed schemes achieve efficiency, practicability, simplicity, and strong notions of security. [ABSTRACT FROM AUTHOR]

SCTP (Stream control transmission protocol) is a new transport layer protocol that was published as RFC2960 by IETF (the Internet Engineering Task Force) in October 2000 and amended in RFC4960 in September 2007. SCTP provides reliable ordered and unordered transport services. The congestion control and flow controlmechanisms for SCTP are very similar to those for TCP (transmission control protocol). SCTP can apply more than one IP address when establishing associations. SCTP multihoming can support multiple paths in association. These features provide SCTP with some network-level fault tolerance through network address redundancy. SCTP multihoming has tremendous transmission potential. However, SCTP path management is very simple in RFC4960 and therefore cannot effectively distinguish path conditions; it also has no path switch strategy appropriate for wireless networking. These factors all degrade SCTP performance. This study proposes a new path management (quality-aware SCTP) for wireless networks; this includes a new path failure detection method and ICE (idle path congestion window size estimation) mechanism. An experiment using NS2 was performed, showing that quality-aware SCTP can effectively improve the network performance. Quality-aware SCTP is simple and provides a more effective performance than SCTP alone. [ABSTRACT FROM AUTHOR]

An analytical model to evaluate the non-saturated performance of the Distributed Queuing Medium Access Control Protocol for Ad Hoc Networks (DQMANs) in single-hop networks is presented in this paper. DQMAN is comprised of a spontaneous, temporary, and dynamic clustering mechanism integrated with a near-optimum distributed queuing Medium Access Control (MAC) protocol. Clustering is executed in a distributed manner using a mechanism inspired by the Distributed Coordination Function (DCF) of the IEEE 802.11. Once a station seizes the channel, it becomes the temporary clusterhead of a spontaneous cluster and it coordinates the peer-to-peer communications between the clustermembers. Within each cluster, a near-optimum distributed queuing MAC protocol is executed. The theoretical performance analysis of DQMAN in single-hop networks under non-saturation conditions is presented in this paper. The approach integrates the analysis of the clustering mechanism into the MAC layer model. Up to the knowledge of the authors, this approach is novel in the literature. In addition, the performance of an ad hoc network using DQMAN is compared to that obtained when using the DCF of the IEEE 802.11, as a benchmark reference. [ABSTRACT FROM AUTHOR]

Routing in wireless networks has been heavily studied in the last decade. Many routing protocols are based on classic shortest path algorithms. However, shortest path-based routing protocols suffer from uneven load distribution in the network, such as crowed center effect where the center nodes have more load than the nodes in the periphery. Aiming to balance the load, we propose a novel routing method, called Circular Sailing Routing (CSR), which can distribute the traffic more evenly in the network. The proposed method first maps the network onto a sphere via a simple stereographic projection, and then the route decision is made by a newly defined "circular distance" on the sphere instead of the Euclidean distance in the plane. We theoretically prove that for a network, the distance traveled by the packets using CSR is no more than a small constant factor of the minimum (the distance of the shortest path). We also extend CSR to a localized version, Localized CSR, by modifying greedy routing without any additional communication overhead. In addition, we investigate how to design CSR routing for 3D networks. For all proposed methods, we conduct extensive simulations to study their performances and compare them with global shortest path routing or greedy routing in 2D and 3D wireless networks. [ABSTRACT FROM AUTHOR]

The delay in transmitting SIP messages over the wireless link for session resetup at handover is still major bottleneck for interactive multimedia service. In this paper, a proxy agent-based scheme is proposed to minimize the SIP session setup delay over a wireless link in 3G inter-subnet handover scenarios. This scheme is based on the two characteristics. One is that the major factor of SIP session re-setup delay is generally caused by the retransmissions in the unreliable wireless links, and the other is that most of the fields in request messages as well as response messages are duplicated when a set of SIP messages are exchanged during session re-setup procedure. In this scheme, no change is required in the SIP message processing except for the proxy agents in both BS and MH. [ABSTRACT FROM AUTHOR]

We propose a novel channel model to be used for simulating indoor wireless propagation environments. An extensive measurement campaign was carried out to assess the performance of different transport protocols over 802.11 links. This enabled us to better adjust our approach, which is based on an autoregressive filter. One of the main advantages of this proposal lies in its ability to reflect the "bursty" behavior which characterizes indoor wireless scenarios, having a great impact on the behavior of upper layer protocols. We compare this channel model, integrated within the Network Simulator (ns-2) platform, with other traditional approaches, showing that it is able to better reflect the real behavior which was empirically assessed. [ABSTRACT FROM AUTHOR]

Previous approaches to the dynamic updating of Shortest Path Trees (SPTs) have in the main focused on just one link state change. Not much work has been done on the problem of deriving a new SPT from an existing SPT for multiple link state decrements in a network that applies link-state routing protocols such as OSPF and IS-IS. This problem is complex because in the process of updating an SPT there are, firstly, no simple forms of node set to presumable contain all nodes to be updated and, secondly, multiple decrements can be accumulated to make the updating much harder. If we adopt the updating mechanisms engaged in one link state change for the case of multiple link state decrements, the result is node update redundancy, as a node changes several times before it reaches its final state in the new SPT. This paper proposes two dynamic algorithms ( MaxR, MinD) for obviating unnecessary node updates by having part nodes updated in a branch on the SPT only after selecting a particular node from a built node list. The algorithm complexity analysis and simulation results show that MaxR and MinD require fewer node updates during dynamic update procedures than do other algorithms for updating SPT of multiple link state decrements. [ABSTRACT FROM AUTHOR]

This paper discusses a formal approach for establishing theories of trust for authentication systems which can be used to reason about how agent beliefs evolve through time. The goal of an authentication system is to verify and authorise users in order to protect restricted data and information, so trust is a critical issue for authentication systems. After authentication, two principals (people, computers, services) should be entitled to believe that they are communicating with each other and not with intruders. So, it is important to express such beliefs precisely and to capture the reasoning that leads to them. In this paper, we focus on analysis of agent beliefs in dynamic environments using a temporalised belief logic, obtained by adding a temporal logic onto a belief logic. Working through a well-known authentication protocol, namely Kerberos, we discuss how to express principal beliefs involved in authentication protocols and the evolution of those beliefs based on a series of observations of agents as a consequence of communication. Our approach could be used for designing, verifying and implementing authentication protocols. [ABSTRACT FROM AUTHOR]

This paper proposes a limited feedback SDMA scheme of combining opportunistic scheduling and codebook-based multiuser precoding. A new systematic construction for SDMA codebook, which comprises a set of precoders for multiple simultaneously active users, is first presented. Different from conventional Grassmannian codebook, the proposed codebook is designed in terms of array processing and has a cluster-based structure, with each cluster generated using a perturbation method. In order to tackle the intractable interuser interference issue inhered in limited feedback SDMA, this paper further proposes two novel opportunistic scheduling algorithms, which are able to fully exploit the cluster structure of the proposed codebook. The first proposed algorithm schedules the simultaneous users and their preferred precoders in a successive way, and is implemented in a Markov-like fashion. The second proposed algorithm is capable of rapidly finding a group of channel-matching users along with their preferred precoders. Simulation results demonstrate that in sparse networks, the proposed SDMA exhibits a better throughput performance than the conventional limited feedback SDMA does, while both having a comparable feedback overhead. [ABSTRACT FROM AUTHOR]

Popular software testing tools, such as J Unit, allow frequent retesting of modified code; yet the manually created test scripts are often seriously incomplete. A unit-testing tool called J Walk has therefore been developed to address the need for systematic unit testing within the context of agile methods. The tool operates directly on the compiled code for Java classes and uses a new lazy method for inducing the changing design of a class on the fly. This is achieved partly through introspection, using Java's reflection capability, and partly through interaction with the user, constructing and saving test oracles on the fly. Predictive rules reduce the number of oracle values that must be confirmed by the tester. Without human intervention, J Walk performs bounded exhaustive exploration of the class's method protocols and may be directed to explore the space of algebraic constructions, or the intended design state-space of the tested class. With some human interaction, J Walk performs up to the equivalent of fully automated state-based testing, from a specification that was acquired incrementally. [ABSTRACT FROM AUTHOR]

Privacy preserving association rule mining has been an active research area since recently. To this problem, there have been two different approaches—perturbation based and secure multiparty computation based. One drawback of the perturbation based approach is that it cannot always fully preserve individual’s privacy while achieving precision of mining results. The secure multiparty computation based approach works only for distributed environment and needs sophisticated protocols, which constrains its practical usage. In this paper, we propose a new approach for preserving privacy in association rule mining. The main idea is to use keyed Bloom filters to represent transactions as well as data items. The proposed approach can fully preserve privacy while maintaining the precision of mining results. The tradeoff between mining precision and storage requirement is investigated. We also propose δ-folding technique to further reduce the storage requirement without sacrificing mining precision and running time. [ABSTRACT FROM AUTHOR]

Although extremely high-speed interconnects are available today, the traditional protocol stacks such as TCP/IP and UDP/IP are not able to utilize the maximum network bandwidth due to inherent overheads in the protocol stacks. Such overheads are a big obstacle for high-performance computing applications to exploit high-speed interconnects in cluster environments. To address this issue, many researchers have been presenting analyses of protocol overheads and suggesting a number of optimization approaches to harness the TCP/IP suite over high-speed interconnects. However, to the best of our knowledge, there is no study that analyzes and optimizes the protocol overheads thoroughly in an integrated manner. In this paper, we exploit a set of protocol optimization mechanisms in an integrated manner while dealing with the full spectrum of the protocol layers from the transport layer to the physical layer. To evaluate the impact of each protocol overhead, we apply the optimization mechanisms one by one and perform detailed analyses at each step. The thorough overhead measurements and analyses reveal the dependencies between protocol overheads. With our comprehensive optimizations, we show that UDP/IP can utilize more than 95% of the maximum network throughput a Myrinet-based experimental system can provide. [ABSTRACT FROM AUTHOR]

Bladed servers are increasingly being adopted in high-density enterprise datacenters by virtue of the improved benefits they offer in form factor density, modularity, and more robust management for control and maintenance with respect to rack-optimized servers. In the future, such servers are likely to form the key foundational blocks for a variety of system architectures in data centers. However, designing a commodity blade system environment that can serve as a general-purpose infrastructure platform for a wide variety of future system architectures poses several challenges. This paper discusses these challenges and presents specific system architecture solutions, along with application examples to illustrate the general-purpose nature of the infrastructure for parallel and distributed applications. [ABSTRACT FROM AUTHOR]

We study the load balancing problem in a dense wireless multihop network, where a typical path consists of a large number of hops, that is, the spatial scales of a typical distance between source and destination and mean distance between the neighboring nodes are strongly separated. In this limit, we present a general framework for analyzing the traffic load resulting from a given set of paths and traffic demands. We formulate the load balancing problem as a minmax problem and give two lower bounds for the achievable minimal maximum traffic load. The framework is illustrated by considering the load balancing problem of uniformly distributed traffic demands in a unit disk. For this special case, we derive efficient expressions for computing the resulting traffic load for a given set of paths. By using these expressions, we are able to optimize a parameterized set of paths yielding a particularly flat traffic load distribution which decreases the maximum traffic load in the network by 40% in comparison with the shortest-path routing. [ABSTRACT FROM AUTHOR]

Because adaptability greatly improves the performance of a broadcast protocol, we identify three ways in which machine learning can be applied to broadcasting in a mobile ad hoc network (MANET). We chose broadcasting because it functions as a foundation of MANET communication. Unicast, multicast, and geocast protocols utilize broadcasting as a building block, providing important control and route establishment functionality. Therefore, any improvements to the process of broadcasting can be immediately realized by higher-level MANET functionality and applications. While efficient broadcast protocols have been proposed, no single broadcasting protocol works well in all possible MANET conditions. Furthermore, protocols tend to fail catastrophically in severe network environments. Our three classes of adaptive protocols are pure machine learning, intra-protocol learning, and inter-protocol learning. In the pure machine learning approach, we exhibit a new approach to the design of a broadcast protocol: the decision of whether to rebroadcast a packet is cast as a classification problem. Each mobile node (MN) builds a classifier and trains it on data collected from the network environment. Using intra-protocol learning, each MN consults a simple machine model for the optimal value of one of its free parameters. Lastly, in inter-protocol learning, MNs learn to switch between different broadcasting protocols based on network conditions. For each class of learning method, we create a prototypical protocol and examine its performance in simulation. [ABSTRACT FROM AUTHOR]

We evaluate the performance of realistic wireless sensor networks in indoor scenarios. Most of the considered networks are formed by nodes using the Zigbee communication protocol. For comparison, we also analyze networks based on the proprietary standard Z-Wave. Two main groups of network scenarios are proposed: (i) scenarios with direct transmissions between the remote nodes and the network coordinator, and (ii) scenarios with routers, which relay the packets between the remote nodes and the coordinator. The sensor networks of interest are evaluated considering different performance metrics. In particular, we show how the received signal strength indication (RSSI) behaves in the considered scenarios. Then, the network behavior is characterized in terms of end-to-end delay and throughput. In order to confirm the experiments, analytical and simulation results are also derived. [ABSTRACT FROM AUTHOR]

Current video-surveillance systems typically consist of many video sources distributed over a wide area, transmitting live video streams to a central location for processing and monitoring. The target of this paper is to present an experience of implementation of a large-scale video-surveillance system based on a wireless mesh network infrastructure, discussing architecture, protocol, and implementation issues. More specifically, the paper proposes an architecture for a video-surveillance system, and mainly centers its focus on the routing protocol to be used in the wireless mesh network, evaluating its impact on performance at the receiver side. A wireless mesh network was chosen to support a video-surveillance application in order to reduce the overall system costs and increase scalability and performance. The paper analyzes the performance of the network in order to choose design parameters that will achieve the best trade-off between video encoding quality and the network traffic generated. [ABSTRACT FROM AUTHOR]

Adequate representation of mobility is a very important issue in simulation of mobile ad hoc networks. In this context, we consider the characterization of the mobile nodes movement through a Markovian modeling. Our proposed representation allows for smooth movements and the generation of several different mobility profiles. This approach is also shown to be more suitable for use in various ad hoc networks scenarios than other proposed mobility models, such as the random waypoint (RWP) model. An evaluation of the proposed model is provided, under different border rule scenarios. In addition, the performance of AODV, DSR, and DSDV routing protocols is also studied through simulations, utilizing the proposed model, and the results obtained are discussed. [ABSTRACT FROM AUTHOR]

This article addresses a problem of the severe unfairness between multiple TCP sessions in a wireless context also known as "TCP capture" phenomenon. We present an adapted max-min fairness framework to the specifics of MANETs. We introduce a practically implementable cross-layer network architecture which enforces our formal model. We have verified with simulations and real world experiments that under our adaptive rate limiting scheme unfair behavior virtually vanishes. The direct consequence of this work guaranteed stable services for TCP-based applications in MANETs, including traditional FTP, web as well as for UDP-based sessions. [ABSTRACT FROM AUTHOR]

There has recently been an increasing interest in convergence of p2p and ad hoc network research. Actually, p2p systems and multihop ad hoc networks share similar features, such as self-organisation, decentralisation, self-healing, and so forth. It is thus interesting to understand if p2p systems designed for the wired Internet are suitable also for ad hoc networks and, if they are not, in which direction they should be improved. In this paper, we report our experience in running p2p applications in real multihop ad hoc network testbeds. Specifically, we used group-communication applications that require p2p systems made up of an overlay network and a p2p multicast protocol. In this paper, we present experimental results specifically related to the performance of a well-known p2p shared-tree multicast protocol (Scribe). Our results show that such a solution is far from being efficient on ad hoc networks. We emphasize that the structured multicast approach is one of the main causes of inefficiency, and suggest that stateless solutions could be preferable. [ABSTRACT FROM AUTHOR]

We introduce a novel medium access control (MAC) protocol for radio frequency identification (RFID) systems which exploits the statistical information collected at the reader. The protocol, termed adaptive slotted ALOHA protocol (ASAP), is motivated by the need to significantly improve the total read time performance of the currently suggested MAC protocols for RFID systems. In order to accomplish this task, ASAP estimates the dynamic tag population and adapts the frame size in the subsequent round via a simple policy that maximizes an appropriately defined efficiency function. We demonstrate that ASAP provides significant improvement in total read time performance over the current RFID MAC protocols. We next extend the design to accomplish reliable performance of ASAP in realistic scenarios such as the existence of constraints on frame size, and mobile RFID systems where tags move at constant velocity in the reader's field. We also consider the case where tags may fail to respond because of a physical breakdown or a temporary malfunction, and show the robustness in those scenarios as well. [ABSTRACT FROM AUTHOR]

Peer-to-Peer (P2P) file sharing is the hottest, fastest growing application on the Internet. When designing Gnutella-like applications, the most important consideration is the scalability problem, because P2P systems typically support millions of users online concurrently. Gnutella suffers from poor scaling due to its flooding-based search, resulting in excessive amounts of repeated query messages. Therefore, a good search protocol plays an important role in a system’s scalability. However, congestion, due to large query loads from users, definitely impacts on the performance of search protocols, and this consideration has received little attention from the research community. In this paper, we propose a congestion-aware search protocol for unstructured P2P networks. Our protocol consists of three parts—Congestion-Aware Forwarding, Random Early Stop and Emergency Signaling. The aim of our protocol is to integrate congestion control and object discovery functionality so that the search protocol can achieve good performance under congested networks and flash crowds. We perform extensive simulations to study our proposed protocol. The results show that our protocol can significantly reduce the hit delay while maintaining the high hit rate and also the congestion problems such as query loss and the peer overloading problem can be effectively alleviated. [ABSTRACT FROM AUTHOR]

In our study, we investigate a packet-level protocol parallelization approach, which works by parallel multithreading the protocol execution such that packets within and among connections are processed in parallel using distinct processors/threads. The major advantage of this approach is its high scalability—with proper scheduling, more protocol connections, and hence more requests, can be supported by using more threads. In this paper, we present results of our detailed simulations using the NS-2 platform for reliably transferring video stream data in a client-server system. Different types of parameters are used to measure the performance. The parameters include available network bandwidth, different number of TCP connections, and different video sources. Our results show that a parallel approach can indeed significantly enhance the playback quality. [ABSTRACT FROM AUTHOR]

Two experiments examined the judged quality of videoconferencing as a function of three measures of IP network performance: bandwidth, latency, and packet loss. The experiments were realized in a laboratory using a network emulator and a commercial videoconferencing system. Experiment 1 used a fractional factorial design and all three parameters: Experiment 2 was designed (a) to use random packet loss rather than bursty packet loss, and (b) so that a statistical interaction between bandwidth and packet loss could be detected, if present. Bandwidth levels were the same as in Experiment 1, but packet loss was set to 0, 1 and 2%. The experimental design was full factorial. In both experiments, pairs of non-expert judges held five-minute videoconferences for each combination of parameters, then rated the quality of system performance immediately after each videoconference. In both experiments statistical analysis showed that packet loss was the most important network performance parameter in predicting subjective quality of videoconferencing. These results agree with results on VoIP quality. Bandwidth and latency also affected the judges’ ratings, but to a smaller extent. In Experiment 2, an interaction between packet loss and bandwidth was detected: At lower bandwidths and greater packet loss, the subjective ratings were not as low as would be expected, contrary to the idea that quality would degrade catastrophically when both bandwidth and packet loss were simultaneously unfavorable. [ABSTRACT FROM AUTHOR]

In the context of computer networks, conformance testing determines whether an implementation under test conforms to its specification. Testing was carried out in a centralized and sequential way. This is no longer feasible or realistic as systems to be tested have become increasingly complex and can be widely distributed. Our further goal is to evaluate how a distributed approach can help in testing complex systems such as a network’s components efficiently. We present two solutions to generate automatically distributed tests. As it is somehow less difficult to generate centralized tests, the proposed solutions consist in automatically distributing these tests. By applying these solutions to military ISDN protocols, we showed that: (i) the solutions ease development of distributed tests and (ii) distributed tests obtained are well suited for testing complex systems. [ABSTRACT FROM AUTHOR]

This paper presents a language independent runtime framework—called Weaves—for object based composition of unmodified code modules that enables selective sharing of state between multiple control flows through a process. Furthermore, the framework allows dynamic instantiation of code modules and control flows through them. In effect, weaves create intra-process modules (similar to objects in OOP) from code written in any language. Applications can be built by instantiating Weaves to form Tapestries of dynamically interacting code. The framework enables objects to be arbitrarily shared—it is a true superset of both processes as well as threads, with code sharing and fast context switching time similar to threads. Weaves does not require any special support from either the language or application code—practically any code can be weaved. Weaves also include support runtime loading and linking of object modules enabling the next generation of highly dynamic applications. This paper presents the elements of the Weaves framework and its implementation on the Linux platform over source-code independent ELF object files. The current implementation has been validated over Sweep3D, a benchmark for 3D discrete ordinates neutron transport (Koch et al. Trans. Am. Nucl. Soc. 65 (198) [1992]), and a user-level port of the Linux 2.4 family kernel TCP/IP protocol stack. [ABSTRACT FROM AUTHOR]

A model for a random access network controlled by a static conflict warning protocol is designed as a single-server queueing system with a retrial buffer. The domain of stable operation of the system, whose state probability distribution remains constant in a large time interval, is determined under asymptotic conditions. The mean stable operation time of the system is determined and shown to be large, almost infinite, for certain traffic intensities. [ABSTRACT FROM AUTHOR]

Protocols for data transmission over an IP computer network should not only lead to efficient network utilization but also be fair to different users. Current networks accomplish these goals by some form of end-to-end congestion control. Existing protocols, however, assume somewhat altruistic behavior from hosts. Karp et al. (2000) have initiated a study of whether or not a single host's optimum strategy (in a system where other hosts are well behaved) is altruistic. We carry this exploration further by developing an efficient randomized algorithm for bandwidth utilization in their model. The competitive ratio of this algorithm is optimal up to a constant factor. Karp et al. had earlier studied the deterministic case and left open the randomized case. What may be of some interest is that our algorithm is essentially the classical multiplicative increase, multiplicative decrease strategy, which is very aggressive and non-altruistic. [ABSTRACT FROM AUTHOR]

A TCP flow is expected to traverse over a single path. This is in order to avoid performance problems especially on account of reordering of packets and acknowledgements. Reordering can occur on account of the use of different paths with diverse bandwidth and delay characteristics. We argue that the present approach prevents us from getting the advantages associated with multiple paths. Specifically, use of multiple paths for a flow can be advantageous in improving the performance as well as the dependability of a flow. We model the effects of reordering and derive conditions under which the performance of a TCP flow improves with the use of multiple paths. We also provide recommendations for choosing amongst multiple paths. We then verify the conditions using simulations. We also illustrate the applicability of the derived conditions to multiple flows. [ABSTRACT FROM AUTHOR]

Gigabit networks are equipped with “increasingly” intelligent network interface cards, and the firmware running in the cards does various tasks related to end-to-end communication. For an accurate performance evaluation of gigabit networks, it is very important to characterize and quantify the firmware. However, the firmware has been neglected in the latency analyzes of network protocols. This paper presents an in-depth latency analysis of Myrinet. Our findings include that the major bottleneck is the network interface card itself. This is true especially for so-called lightweight user-level protocols (such as BPI of Myrinet) designed for high-speed communication. Although BPI is very lean and efficient in the host, its sending throughput becomes similar to UDP. This result is very unexpected and surprising. Through firmware-level measurements, we identify that the cause of bottleneck is the DMA performance. [ABSTRACT FROM AUTHOR]

Distributed shared memory (DSM) systems provide a simple programming paradigm for networks of workstations, which are gaining popularity due to their cost-effective high computing power. However, DSM systems usually exhibit poor performance due to the large communication delay between the nodes; and a lot of different memory consistency models have been proposed to mask the network delay. In this paper, we propose an asynchronous protocol for the release consistent memory model, which we call an Asynchronous Release Consistency (ARC) protocol. Unlike other protocols where the communication adheres to the synchronous request/receive paradigm, the ARC protocol is asynchronous, such that the necessary pages are broadcast before they are requested. Hence, the network delay can be reduced by proper prefetching of necessary pages. We have also compared the performance of the ARC protocol with the lazy release protocol by running standard benchmark programs; and the experimental results showed that the ARC protocol achieves a performance improvement of up to 29%. [ABSTRACT FROM AUTHOR]