Publications - with abstracts

We present holistic debugging, a novel method for observing execution of complex and distributed software. It builds on an instruction set simulator, which provides reproducible experiments and non-intrusive probing of state in a distributed system. Instruction set simulators, however, only provide low-level information, so a holistic debugger contains a translation framework that maps this information to higher abstraction level observation tools, such as source code debuggers. We have created Nornir, a proof-of-concept holistic debugger, built on the simulator Simics. For each observed process in the simulated system, Nornir creates an abstraction translation stack, with virtual machine translators that map machine-level storage contents (e.g. physical memory, registers) provided by Simics, to application-level data (e.g. virtual memory contents) by parsing the data structures of operating systems and virtual machines. Nornir includes a modified version of the GNU debugger (GDB), which supports non-intrusive symbolic debugging of distributed applications. Nornir's main interface is a debugger shepherd, a programmable interface that controls multiple debuggers, and allows users to coherently inspect the entire state of heterogeneous, distributed applications. It provides a robust observation platform for construction of new observation tools.

We present holistic debugging, a novel method for observing execution of complex and distributed software. It builds on an instruction set simulator, which provides reproducible experiments and non-intrusive probing of state in a distributed system. Instruction set simulators, however, provide low-level information, so a holistic debugger contains a translation framework that maps this information to higher abstraction level observation tools, such as source code debuggers. We have created Nornir, a proof-of-concept holistic debugger, built on the simulator Simics. For each observed process in the simulated system, Nornir creates an abstraction translation stack, with virtual machine translators that map machine-level storage contents (e.g. physical memory, registers) provided by Simics, to application-level data (e.g. virtual memory contents) by parsing the data structures of operating systems and virtual machines. Nornir includes a modified version of the GNU debugger (GDB), which supports non-intrusive symbolic debugging of distributed applications. Nornir's main interface is a debugger shepherd, a programmable interface that controls multiple debuggers, and allows users to coherently inspect the entire state of heterogeneous, distributed applications. It provides a robust observation platform for construction of new observation tools.

Power saving mechanisms in wireless ad hoc network nodes mainly switch off the transmission and reception hardware for a maximal amount of time and turn it on again within a given interval. Many approaches aim to synchronize the state changes of the nodes in the network through distributed beacon generation and introduce mechanisms where nodes synchronously wake up at designated points of time to exchange announcements about pending traffic. Synchronization however is difficult to achieve, in particular in ad hoc networks. This paper describes the simulation, evaluation and refinement of a recently proposed power saving approach based on asynchronous wake-up patterns and wake-up announcements integrated with AODV. We show that significant improvements of the connectivity under low wake ratios can be achieved by carefully designed forwarding strategies of AODV route request messages.

The Internet consists of independent networks that belong to different administrative domains and vary in scope from personal area networks, private home networks, corporate networks to ISP and global operator networks. These networks may employ different technologies, communications mediums, addressing realms and may have widely different capabilities. The coming years will add a significant level of dynamic behavior, such as mobile nodes and moving networks, which the Internet must support. At the same time, there is a need to address the increasing levels of harmful traffic and denial-of-service attacks. The existing Internet architecture does not support dynamic behavior or secure communication to a sufficient degree. This paper outlines a node-identity-based internetworking architecture that allows heterogeneous networks to work together without loss of functionality. Some of techniques employed in this architecture include reliance on cryptographic node identifiers, identity routers and localized addressing realms.

This report introduces a new sensor network simulator for the Contiki OS - the COOJA Simulator. The Contiki OS is a portable operating system designed specifically for resource limited devices such as sensor nodes. It is built around an event-driven kernel but supports pre-emptive multithreading at a per-process basis. It also supports a full TCP/IP stack via uIP and the programming abstraction Protothreads. The main design goal of the COOJA Simulator is extendibility, for which Interfaces and Plugins are used. An Interface represents a sensor node property or device, such as a position, a button or a radio transmitter. A Plugin is used to interact with a simulation, for example to control the simulation speed or to watch all network traffic between the simulated nodes. Both new Plugins and Interfaces can easily be created and added to the simulation environment. A number of other parts of the simulator, for example a radio medium responsible for forwarding radio network data, can also be implemented and added to the simulator. And by supporting several different simulation environments at the same time in one simulation, different underlying hardware platforms can be simulated in heterogeneous networks. Java Native Interface is used to connect the new simulator with Contiki, allowing simulated applications to run in a real Contiki system. By using this approach, any simulated application can then be run on a real sensor node unaltered.

The Delay Tolerant Networking Architecture (DTN) has been proposed for use in challenged networks that suffer from intermittent connectivity or high delay. The DTN architecture and the bundle protocol presents a standard method to interconnect heterogeneous challenged networks using asynchronous message switching. It provides a framework for dynamic routing, contact scheduling, naming, reliability and transmission status reports. Wireless Sensor Networks (WSNs) are often viewed as challenged networks as nodes operate at low power, often with weak or intermittent radio communication. WSNs are an important application area for DTN. In this work I present ContikiDTN, a TCP/IP based prototype implementation of the DTN architecture and bundle protocol. ContikiDTN aims to evaluate the suitability of the DTN bundle protocol as a solution for messaging inside a TCP/IP WSN and as a way of connecting the WSN to the Internet. I discuss the design and implementation of ContikiDTN using the Contiki operating system. I highlight the issues in implementing the bundle protocol with TCP and Contiki. I show that the event-driven Contiki kernel is very suitable for an asynchronous message forwarding application. I use ContikiDTN to communicate with a full PC platform implementation of DTN and show that it can be used as a gateway to the Internet. I present a simulation and experimental results showing the performance of multi-hop TCP based DTN as compared to only TCP. I show that the core propositions of the DTN architecture hold in a WSN and that it is feasible to implement DTN on resource constrained devices using TCP/IP and Contiki.

This report archives the results of simulation experiments evaluating the sensitivity of certain kinds of asynchronous power save protocols to the actual distribution of nodes' wakeup schedules. The simulation environment is based on a relatively abstract model of network operation that allows us to focus on the interaction between wakeup and communication schedules, as well as being computationally efficient. We observe that the flow capacity of the network (number of flows that can obtain a given throughput) varies significantly with phase distribution in most topology and traffic scenarios. In many cases, the “best” distributions of wakeup schedule provide nearly as much capacity as the network running without power saving. Furthermore, in less heavily loaded networks, we note a surprising moderate positive correlation between flow capacity and mean path length. In more heavily loaded networks, no such correlation is observed, suggesting that more than one underlying mechanism may be involved.

We present work-in-progress developing a communication framework that addresses the communication challenges of the decentralized multihop wireless environment. The main contribution is the combination of a fully distributed, asynchronous power save mechanism with adaptation of the timing patterns defined by the power save mechanism to improve the energy and bandwidth efficiency of communication in multihop wireless networks. The possibility of leveraging this strategy to provide more complex forms of traffic management is explored.

Providing end-to-end communication in heterogeneous internetworking environments is a challenge. Two fundamental problems are bridging between different internetworking technologies and hiding of network complexity and differences from both applications and application developers. This paper presents abstraction and naming mechanisms that address these challenges in the Ambient Networks project. Connectivity abstractions hide the differences of heterogeneous internetworking technologies and enable applications to operate across them. A common naming framework enables end-to-end communication across otherwise independent internetworks and supports advanced networking capabilities, such as indirection or delegation, through dynamic bindings between named entities.

Ambient Networks interconnect independent realms that may use different local network technologies and may belong to different administrative or legal entities. At the core of these advanced internetworking concepts is a flexible naming architecture based on dynamic indirections between names, addresses and identities. This paper gives an overview of the connectivity abstractions of Ambient Networks and then describes its naming architecture in detail, comparing and contrasting them to other related next-generation network architectures.

Wireless sensor networks consist of tiny devices that usually have severe resource constraints in terms of energy, processing power and memory. In order to work efficiently within the constrained memory, many operating systems for such devices are based on an event-driven model rather than on multi-threading. While event-driven systems allow for reduced memory usage, they require programs to be developed as explicit state machines. Since implementing programs as explicit state machines is hard, developing, maintaining, and debugging programs for event-driven systems is difficult.

In this paper, we introduce protothreads, a programming abstraction for event-driven sensor network systems. Protothreads simplify implementation of high-level functionality on top of event-driven systems, without significantly increasing the memory requirements. The memory requirement of a protothread is that of an unsigned integer.

Power saving strategies generally attempt to maximize the time that nodes spend in a low power consumption sleep state. Such strategies often require the sender to notify the receiver about pending traffic using some form of traffic announcement. Although asynchronous traffic announcement mechanisms are particularly suitable for the ad hoc environment, they also provide relatively limited power savings. This paper proposes a mechanism that improves the efficiency of asynchronous traffic announcement mechanisms by reducing the proportion of time that nodes need to spend awake, while still maintaining good connectivity properties. The mechanism is based on allowing traffic announcements to be rebroadcast by neighbouring nodes.

Protothreads are a extremely lightweight, stackless threads designed for use in severely memory constrained systems such as embedded systems. Software for memory constrained embedded systems sometimes are based on an event-driven model rather than on multi-threading. While event-driven systems allow for reduced memory usage, they require programs to be developed as explicit state machines. Since implementing programs as explicit state machines is hard, developing, maintaining, and debugging programs for event-driven systems is difficult.

Protothreads simplify implementation of high-level functionality on top of event-driven systems, without significantly increasing the memory requirements. Protothreads can be implemented in in the C programming language using 10 lines of code and 2 bytes of RAM per protothread.

Two of the most commonly used intra-domain Internet routing protocols are Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). In both these protocols the traffic is routed along shortest paths to the destination without considering other traffic demands or load in the network. The weight of the links, and thereby the shortest paths, can be set by the network operator. This creates the possibility for the network operator to redirect traffic from congested links to less utilised links and achieve a more efficient use of the network. We study three different heuristics for the problem of finding a set of OSPF/IS-IS weights that optimises the performance of the network. We evaluate the heuristics in topologies with power-law properties and compare the obtained results with those from a standard weight setting recommended by Cisco (a major router vendor) as well as with those from an optimal multi-commodity flow routing. Our main conclusion is that one of the heuristics performs better than the rest of the heuristics and achieves results reasonable close to optimum.

Wireless sensor networks are composed of large numbers-up to thousands-of tiny radio-equipped sensors. Every sensor has a small microprocessor with enough power to allow the sensors to autonomously form networks through which sensor information is gathered. Wireless sensor networks makes it possible to monitor places like nuclear disaster areas or volcano craters without requiring humans to be immediately present. Many wireless sensor network applications cannot be performed in isolation; the sensor network must somehow be connected to monitoring and controlling entities.

This thesis investigates a novel approach for connecting sensor networks to existing networks: by using the TCP/IP protocol suite in the sensor network, the sensors can be directly connected to an outside network without the need for special proxy servers or protocol converters.

Bringing TCP/IP to wireless sensor networks is a challenging task, however. First, because of their limited physical size and low cost, sensors are severely constrained in terms of memory and processing power. Traditionally, these constraints have been considered too limiting for a sensor to be able to use the TCP/IP protocols. In this thesis, I show that even tiny sensors can communicate using TCP/IP. Second, the harsh communication conditions make TCP/IP perform poorly in terms of both throughput and energy efficiency. With this thesis, I suggest a number of optimizations that are intended to increase the performance of TCP/IP for sensor networks.

The results of the work presented in this thesis has had a significant impact on the embedded TCP/IP networking community. The software developed as part of the thesis has become widely known in the community. The software is mentioned in books on embedded systems and networking, is used in academic courses on embedded systems, is the focus of articles in professional magazines, is incorporated in embedded operating systems, and is used in a large number of embedded devices.

ScatterWeb, a distributed, heterogeneous platform for the ad-hoc deployment of sensor networks offers hardware together with open, fully documented software for the deployment of embedded sensor networks. Already low power by design, the sensor nodes offer additional energy conservation mechanisms and support energy efficient routing, such as, e.g., solar-aware routing. In order to enable a battery-free operation, the nodes implement permanent power sensing and start the transmission if and only if the energy stored in a capacitor is sufficient for the complete transmission plus the reception of an acknowledgement. Energy-aware routing takes the current incoming power of environmental energy sources into account. Depending on the current power generated by, e.g., solar cells, traffic is always forwarded by the nodes having sufficient power. Together with additional power saving, autoconfiguration, and remote reprogramming techniques, these mechanisms enable ScatterWeb nodes to survive many years in real-life scenarios without any on-site maintenance.

Wireless sensor networks are composed of large numbers of tiny networked devices that communicate untethered. For large scale networks it is important to be able to dynamically download code into the network. In this paper we present Contiki, a lightweight operating system with support for dynamic loading and replacement of individual programs and services. Contiki is built around an event-driven kernel but provides optional preemptive multithreading that can be applied to individual processes. We show that dynamic loading and unloading is feasible in a resource constrained environment, while keeping the base system lightweight and compact.

We present an experimental deployment of an IPbased wireless sensor network that is intended to operate as an intrusion monitoring system. This network is the rst actual deployment of a fully IP-based wireless sensor network with small and computationally constrained sensor nodes. The intrusion monitoring system detects motion in a building which should be empty. The detected events are transmitted to an external monitoring entity, as well as logged inside the network. The logged events are distributed throughout the network and can be collected with a PDA inside the monitored building. We have also learned that the software development process is very time consuming unless support for over-the-air reprogramming is implemented, and that the unpredictability of radio conditions make sensor node placement hard.

The focus of this paper is on traffic engineering in ambient networks. We describe and categorize different alternatives for making the routing more adaptive to the current traffic situation and discuss the challenges that ambient networks pose on traffic engineering methods. One of the main objectives of traffic engineering is to avoid congestion by controlling and optimising the routing function, or in short, to put the traffic where the capacity is. The main challenge for traffic engineering in ambient networks is to cope with the dynamics of both topology and traffic demands. Mechanisms are needed that can handle traffic load dynamics in scenarios with sudden changes in traffic demand and dynamically distribute traffic to benefit from available resources. Trade-offs between optimality, stability and signaling overhead that are important for traffic engineering methods in the fixed Internet becomes even more critical in a dynamic ambient environment.

This paper considers the problem of estimating the point-to-point traffic matrix in an operational IP backbone. Contrary to previous studies, that have used a partial traffic matrix or demands estimated from aggregated Netflow traces, we use a unique data set of complete traffic matrices from a global IP network measured over five-minute intervals. This allows us to do an accurate data analysis on the time-scale of typical link-load measurements and enables us to make a balanced evaluation of different traffic matrix estimation techniques. We describe the data collection infrastructure, present spatial and temporal demand distributions, investigate the stability of fan-out factors, and analyze the mean-variance relationships between demands. We perform a critical evaluation of existing and novel methods for traffic matrix estimation, including recursive fanout estimation, worst-case bounds, regularized estimation techniques, and methods that rely on mean-variance relationships. We discuss the weaknesses and strengths of the various methods, and highlight differences in the results for the European and American subnetworks.

The first age of Internet architectural thinking concentrated on defining the correct principles for designing a packet-switched network and its application protocol suites. Although these same principles remain valid today, they do not address the question of how to reason about the evolution of the Internet or its interworking with other networks of very different heritages. This paper proposes a complementary methodology, motivated by the view that evolution and interworking flexibility are determined not so much by the principles applied during initial design, but by the choice of fundamental components or design invariants in terms of which the design is expressed. The paper discusses the characteristics of such invariants, including examples from the Internet and other networks, and considers what attributes of invariants best support architectural flexibility.

This paper describes a prototype sensor networking platform and its associated development environment. Key elements of the system are the ESB sensor hardware, the Contiki operating system, and the communication stack, which includes a MAC layer and a highly optimized TCP/IP. Because the work is driven by prototype applications being developed by project partners, particular attention is paid to the development environment and to practical deployment issues. Three prototype applications are also presented.

Many applications of wireless sensor networks are useful only when connected to an external network. Previous research on transport layer protocols for sensor networks has focused on designing protocols speci cally targeted for sensor networks. The deployment of TCP/IP in sensor networks would, however, enable direct connection between the sensor network and external TCP/IP networks. In this paper we focus on the performance of TCP in the context of wireless sensor networks. TCP is known to exhibit poor performance in wireless environments, both in terms of throughput and energy ef ciency. To overcome these problems we introduce a mechanism called Distributed TCP Caching (DTC). The DTC mechanism uses segment caching and local retransmissions to avoid expensive end-to-end retransmissions.We show by simulation that DTC signi cantly improves TCP performance so that TCP can be useful even in wireless sensor networks.

Several studies of Internet traffic have shown that it is a small percentage of the flows that dominate the traffic. This is often referred to as the mice and elephants phenomenon. It has been proposed that this might be one of very few invariants of Internet traffic and that this property could somehow be used for traffic engineering purposes. The idea being that one in a scalable way could control a major part of the traffic by only keeping track of a small number of flows. But for this the large flows must also be stable in the meaning that they should be among the largest flows during long periods of time. In this work we analyse packet traces of Internet traffic and study the temporal characteristics of large aggregated traffic flows defined by destination address prefixes.

Energy is one of the most important resources in wireless sensor networks. We use an idealized mathematical model to study the impact of routing on energy consumption. We find explicit bounds on the minimal and maximal energy routings will consume, and use them to bound the lifetime of the network. The bounds are sharp and can be achieved in many situations of interest. Our results apply to sensor networks with a continuous data delivery model, in which all sensors transmit with the same power. Within this class, the results are very general as they apply to arbitrary topologies, routings and radio energy models. We illustrate the theory with some examples. Among these, there is one contradicting the popular belief that it is always the nodes deployed nearest to base nodes that are the most heavily loaded and, hence, the ones that die first.

Wireless sensor networks are based on the collaborative efforts of many small wireless sensor nodes, which collectively are able to form networks through which sensor information can be gathered. Such networks usually cannot operate in complete isolation, but must be connected to an external network to which monitoring and controlling entities are connected. As TCP/IP, the Internet protocol suite, has become the de-facto standard for large-scale networking, it is interesting to be able to connect sensornets to TCP/IP networks. In this paper, we discuss three different ways to connect sensor networks with TCP/IP networks: proxy architectures, DTN overlays, and TCP/IP for sensor networks. We conclude that the methods are in some senses orthogonal and that combinations are possible, but that TCP/IP for sensor networks currently has a number of issues that require further research before TCP/IP can be a viable protocol family for sensor networking.

The TCP/IP protocol suite, which has proven itself highly successful in wired networks, is often claimed to be unsuited for wireless micro-sensor networks. In this work, we question this conventional wisdom and present a number of mechanisms that are intended to enable the use of TCP/IP for wireless sensor networks: spatial IP address assignment, shared context header compression, application overlay routing, and distributed TCP caching (DTC). Sensor networks based on TCP/IP have the advantage of being able to directly communicate with an infrastructure consisting either of a wired IP network or of IP-based wireless technology such as GPRS. We have implemented parts of our mechanisms both in a simulator environment and on actual sensor nodes, and preliminary results are promising.

There are many issues that limit the performance of wireless mobile multi-hop ad hoc networks (MANETs). One of them is that TCP is not well adapted to networks where routes can change or disappear often. In this paper the behaviour of a standard TCP implementation is studied in situations typical for MANETs and compared to the behaviour of a partial implementation of a ATCP, a TCP modification that is intended to increase performance in MANETs. Simulations with simple scenarios show that TCP easily creates a full network load which causes send failures and decreased throughput performance. In some cases the partial ATCP implementation increases throughput but more often it causes an increased amount of duplicate retransmissions. In these scenarios it is unlikely that even a complete ATCP implementation would increase throughput performance. A few modifications to ATCP and TCP are analysed. Especially a limit of the congestion window size shows a large throughput increase. The results are inconclusive, the simulations are too simple to show if the results are applicable in more complex scenarios. It is not clear if ATCP actually is useful in a MANET.

While traditional Internet servers mainly served static and later also dynamic c ontent, the popularity of Web services is increasing rapidly. Web services incorporate additional overhead com pared to traditional web interaction. This overhead increases the demand on Internet servers which is of particular importance when the request rate to the server is high. We conduct experiments that show that the im posed overhead of Web services is non-negligible during server overload. In our experiments the response time f or Web services is more than 30% higher and the server throughput more than 25% lower compared to traditional web interaction using dynamically created HTML pages.

Studies of mobile ad-hoc networks are often based on simulation and their underlying, necessarily simplified assumptions of physical reality. In order to analyse the practical problems we built our own hardware and software. The hardware consists of a core Motorola controller and different wired and wireless interfaces like a Bluetooth and a 433/868 MHz RF module. It allows therefore analysing different scenarios: First, the deployment of a pure ad-hoc network using Bluetooth or 433/868 MHz RF modules. Scenarios going beyond this cover the connection of Bluetooth piconets using the complementary RF technology. This overcomes the proximity requirements of Bluetooth scatternets. Finally, hybrid scenarios with some nodes connected to the Internet and providing Web access over a multihop ad-hoc network can be studied. In this paper we present the testbed and solutions realized up to now. These include home automation scenarios as well as support for mobile ad-hoc games.

Sensor networks are designed especially for deployment in adverse and non-accessible areas without a fixed infrastructure. Therefore, energy conservation plays a crucial role for these networks. We propose to utilize solar power in wireless sensor networks, establishing a topology where - changing over time - some nodes can receive and transmit packets without consuming the limited battery resources. We propose and evaluate two protocols that perform solar-aware routing. The presented simulation results show that both protocols provide significant energy savings when utilizing solar power. The paper shows that incorporating the solar status of nodes in the routing decision is feasible and results in reduced overall battery consumption.

Time, day, location and instantaneous network conditions largely dictate the quality of Voice over IP calls. In this paper we present the results of over 1 8000 VoIP measurements, taken from nine sites connected in a full-mesh configuration. We measure the quality of the routes on a hourly basis by transmitting a pre-recorded call between a pair of sites. We repeat the procedure for all nine sites during the one hour interval. Based on the obtained jitter, delay and loss values as defined in RFC 1889 (RTP) we conclude that the VoIP quality is acceptable for all but one of the nine sites we tested. We also conclude that VoIP quality has improved marginally since we last conducted a similar study i n 1998.

This paper presents a simple and integrated Diff-Serv scheme with feedback preference information (FPI) in the case of strict queueing algorithm. According to the FPI concept, each user just needs to (or even not to) show his intention of receiving a priority service, before a connection establishment, and he needs not to predict any parameters of the flow, the situation of the networks, and etc. The main novelty of this scheme lies in it philosophy that the system charges its users according to the actual preferences that the users have received, which is of more rationalities but less complexities. Comprehensive simulations show that FPI is promising. It not only provides high quality services in a logical way of billing, but also has several other advantages, such as fairness, integration and simplicity.

In wireless sensor networks energy is a valuable but not necessary scarce resour ce. While it is often assumed that nodes in sensor networks are powered by batteries, other energy sources suc h as solar power may provide unlimited energy resources to a changing subset of the nodes. Since these nodes can receive and transmit packets without consuming battery power, routing via these nodes is appealing. I n this paper, we present solar-aware routing, a routing protocol for wireless sensor networks that prefer ably routes traffic via nodes powered by solar energy. Simulations show that solar-aware routing can provide s ignificant energy savings in many scenarios.

The end to end delay is a critical factor in the perceived quality of service for Voice over IP applications. Sicsophone is a complete VoIP system that couples the low level features of audio hardware with a standard jitter buffer playout algorithm. Using the sound card directly eliminates intermediate buffering as well as providing fine control over timers needed by a soft real-time application such as VoIP. A statistical based approach for inserting packets into audio buffers is used in conjunction with a scheme for inhibiting unnecessary fluctuations in the system. We also present mouth-to-ear delay measurements for selected VoIP applications and show that several hundreds of milliseconds can be saved by using the techniques described in this paper. A prototype for both UNIX and Windows platforms has been implemented, demonstrating that our system adapts to network conditions whilst maintaining low delays.

Users of Internet voice services are sensitive to changes in the perceived quality. This work attempts to forecast the quality of Voice over IP sessions from measurements taken in the first few seconds of a call. If the quality can be deemed early, then valuable resources can be saved by terminating or allowing the call to continue. We examine the packet loss from the first few seconds of a VoIP call and attempt to infer the future quality from these initial few seconds. The approach can be seen as using the voice packets as an in-band probing mechanism to sample the current state of the network. We shown within this work that it is indeed possible to assess the quality of calls from the first few seconds with some degree of statistical certainty. One further goal is gain an insight into whether admission control can be performed based on these early measurements.

Web services are an emerging technology that provides a flexible platform for web interaction. We evaluate Web service performance of handheld resource-constrained clients using different wireless technologies. Due to the usage of XML, message sizes in Web services are larger than in traditional web technologies and therefore, compression of Web service messages is attractive; as our experiments show in particular for mobile clients with poor connectivity and high communication costs. However, compression requires CPU time at both the server and the clients. We present measurement results of a simple dynamic scheme that provides benefits by compressing responses only when the required server resources are available.

Today's Internet is moving away from the essentially single domain and non-commercial Internet to a multi-domain, combined commercial and not-for-profit Internet. Policy is critical for each domain to protect its business interests. However, the current Inter-domain routing protocol, BGP, only provides a policy mechanism where operators have to rely on mutual trust to protect themselves. This paper tries to measure and evaluate the current BGP policy model through passively logging BGP update messages. A policy-server based approach is proposed to address some of the problems discovered from the measurement.

Multiplayer games for mobile wireless devices are becoming increasingly popular. Many modern devices such as PDAs or mobile telephones are equipped with Bluetooth interfaces. Bluetooth facilitates the formation of ad-hoc networks thus enabling users to set up multiplayer games spontaneously. On the other hand, Blu etooth has strong restrictions in terms of transmission range and the number of users per piconet. We deploy additional inf rastructure in order to overcome these shortcomings. This infrastructure uses a second wireless technology that sets up and maintains a consistent view of a distributed game by exchanging information about the status and location of play ers. We set up an experimental testbed consisting of single-board communication devices developed in our lab and Blueto oth-equipped PDAs. Our experiments show that the proposed infrastructure is able to extend the rang e of games beyond the coverage of a Bluetooth piconet. Furthermore, we are able to track players. Smooth handovers b etween piconets are also possible. However, due to the current limitations of Bluetooth, handovers are not fast eno ugh to enable highly interactive gaming across different piconets. We present a game that uses this and discuss future a pplication scenarios.

We describe two small and portable TCP/IP implementations fulfilling the subset of RFC1122 requirements needed for full host-to-host interoperability. Our TCP/IP implementations do not sacrifice any of TCP's mechanisms such as urgent data or congestion control. They support IP fragment reassembly and the number of multiple simultaneous connections is limited only by the available RAM. Despite being small and simple, our implementations do not require their peers to have complex, full-size stacks, but can communicate with peers running a similarly light-weight stack. The code size is on the order of 10 kilobytes and RAM usage can be configured to be as low as a few hundred bytes.

Packets in an audio stream can be distorted relative to one another during the traversal of a packet switched network. This distortion can be mainly attributed to queues in routers between the source and the destination. The queues can consist of packets either from our own flow, or from other flows. The contribution of this work is a Markov model for the time delay variation of packet audio in this scenario. Our model is extensible, and show this by including sender silence suppression and packet loss into the model. By comparing the model to wide area traffic traces we show the possibility to generate an audio arrival process similar to those created by real conditions. This is done by comparing the probability density functions of our model to the real captured data.

This paper introduces several relative new mathematic theories that can be used in analysis of uncertain and fuzzy information in large scale system, some of which are in the elementary stage of development; then analyzes the interrelation between them, and summarizes the achievement of their interaction; finally it do further study on All Set that is proposed through the analysis of relation between these theories and brings forward a unitive form of them.

Queueing control plays an important role in manufacturing and communication networks and has been of considerable interest to many researchers. In this book, a novel approach is presented using fuzzy control to solve queueing control problems. Specifically, twenty one cases are studied in detail. These control models, either known or new in the literature, are selected from all categories in the queueing control field, i.e., control of the number of servers; control of the service rate; control of the queue discipline; control of the admission of customers, and control of queues with multicriteria. Simulation shows that this new approach is efficient and promising, especially in cases where analytical solutions do not exist. The approach signals a departure from classical techniques. Some applications to the Internet are also presented.

Two of the objectives of Internet are to increase network capacity and offer high quality of differentiated services for traffic with real-time and non-real-time requirements. Differentiated services (Diff-Serv) were established to fulfill such objectives. Up until now several Diff-Serv schemes have been proposed which, among others, handle drop and delay priorities. These two priorities raise important optimization issues for the Internet but their relationship remains an open problem. This paper presents a fuzzy control algorithm to select packets in a fair and efficient manner. Simulation shows that the fuzzy controller is better than a crisp one when the fairness issue is raised.

QoS (Quality of Service) routing is a key network function for the transmission and distribution of digitized audio/video across next-generation high-speed networks. It has two objectives: finding routes that satisfy the QoS constraints and making efficient use of network resources. The complexity involved in the networks may require the consideration of multiple constraints to make the routing decision. In this paper, we propose a novel approach using fuzzy logic technique to QoS routing that allows multiple constraints to be considered in a simple and intuitive way. Simulation shows that this fuzzy routing algorithm is efficient and promising.

The end to end delay is a critical factor in the perceived quality of service for Voice over IP applications. The described solution is a complete system-level platform and complements QoS work in the network and application areas. We describe a VoIP system that couples the low level features of audio hardware with a jitter buffer playout algorithm. Using the sound card directly eliminates intermediate buffering as well as providing fine control over timers needed by a soft real-time application such as VoIP. A statistical based approach for inserting packets into audio buffers is used in conjunction with a scheme for inhibiting unnecessary fluctuations in the system. We give comparisons for the performance of the playout algorithm against idealised playout conditions. We also present mouth to ear delay measurements for selected VoIP applications and show that several hundreds of milliseconds can be saved by using the techniques described in this paper. A prototype for both UNIX and Windows platforms (NT and 9X) has been implemented, demonstrating that our system adapts to network conditions whilst maintaining low delays.

The basic objectives of future Internet are to increase the network capacity, to offer practically differentiated services for traffic with different requirements. These objectives introduce very strict requirements for traffic control systems and lead to the establishment of DS concept. However, the new features of DS networks, where several classes of precedence are allowed, lead the inefficiency of the congestion control approaches for the existed best-effort Internet. In this paper, a new admission control approach using fuzzy logic in the DS domain is presented. Simulation shows that the approach is efficient and promising.

Intra-domain routing in the Internet normally uses a single shortest path to forward packets towards a specific destination with no knowledge of traffic demand. We present an intra-domain routing algorithm based on multi-commodity flow optimisation which enable load sensitive forwarding over multiple paths. It is neither constrained by weight-tuning of legacy routing protocols, such as OSPF, nor requires a totally new forwarding mechanism, such as MPLS. These characteristics are accomplished by aggregating the traffic flows destined for the same egress into one commodity in the optimisation and using a hash based forwarding mechanism. The aggregation also results in a reduction of computational complexity which makes the algorithm feasible for on-line load balancing. Another contribution is the optimisation objective function which allows precise tuning of the tradeoff between load balancing and total network efficiency.

In contrast with work focusing on routing problems in mobile ad hoc networks, this work addresses the problem of system configuration in such networks.

In particular, we are interested in ways to instantiate the configuration infrastructure - naming, addressing, authentication, and key distribution - needed to establish small-to-medium scale ad hoc networks supporting collaborative applications.

We argue that, in such spontaneous networks,much of the necessary infrastructure can be derived from the face-to-face human interactions that these networks are intended to facilitate. This approach has the additional advantage of being intuitive for the non-expert user.

This paper describes a power save protocol for ad hoc networks. The protocol is largely independent of the details of the underlying MAC and friendly toward any overlying energy-aware ad hoc routing. A key advantage of the protocol is that it is fully asynchronous. Each station independently establishes a periodic sleep/wake cycle. Neighbors that wish to communicate estimate the relative phase difference between their sleep/wake cycles. A station uses this phase information to order its pending transmissions so as to maximize value with respect to some QoS function. A station can also adjust its phase relationships to avoid contention and increase effective bandwidth available to a flow, as well as reduce latency.

Guaranteeing Quality of Service (QoS) in the Internet is a topic of active research. The technologies that have drawn the most attention are several different models. IntServ uses the per-flow approach to provide guarantees to individual streams, DiffServ provides aggregate assurances for a group of applications, while MPLS tries to provide the efficiency and simplicity of IP routing together with the high speed switching of ATM by integrating the label-swapping paradigm with network layer routing. However, all these models have been designed to work for fixed Internet so for. There exists an urgent and important requirement today to study and identify the possible modifications that need to be made to make them suitable for the coming mobile Internet. In this paper, we aim to develop a thorough understanding of the unique opportunities and challenges, problems, requirements and candidate solutions, that arise in modifying the existing QoS models in order to enable them to efficiently work in mobile Internet. Some existing work is outlined as a survey, while some new ideas and proposals are presented from the research viewpoint.

Traffic on the Internet today is routed on the shortest path to the destination. This is considered as the quickest path but if traffic congestion occurs on the route, packets are dropped and the traffic slows down due to the retransmission of the missing packets. If the network resources could be more evenly utilised, some congestions could be avoided and the problem with retransmissions could be reduced. In order to balance the load evenly over a network, the load variation has to be known and predictable. Other studies of IP traffic have shown that a small number of flows carry the main part of the network traffic, these flows are referred to as elephants. This property is studied in this report and the stability of these flows is examined. By aggregating with respect to the source and destination network of the traffic, individual flows are easily identified. This report also discusses how to identify the large flows during runtime in order to use their properties when calculating the stability for the future traffic demand. The traffic prediction is based on analysis of logged Internet traffic. The report concludes that the phenomenon with elephant and mice flows can be observed when aggregating traffic artificially by different lengths of their network prefixes. When calculating future stability of flows the network aggregation does not have a major impact.

Time, day, location and instantaneous network conditions largely dictate the quality of Voice over IP calls. In this paper we describe a VoIP measurement infrastructure to measure the delay, loss and jitter of simulated phone calls on the Internet. We measure the quality by transmitting a simulated voice call between chosen sites and carefully recording the subsequent packet arrivals at the receiver. We have gathered more than 25,000 sample VoIP sessions from nine global sites. This is our second and more detailed attempt at measuring VoIP quality. This second phase has also focused on the effects of packet size, network asymmetry and silence suppression on measuring jitter, delay and loss. We have made the sessions and tools available for future investigations. Generally the quality of VoIP is excellent within the US and Europe and has improved since our last measurements. Finally this paper concludes with what we have learnt from two efforts of measuring VoIP quality on Wide Area Networks.

This report describes a power save protocol for ad hoc networks. The protocol is largely independent of the details of the underlying MAC and is friendly toward any overlying energy-aware ad hoc routing. A key advantage is that the protocol is fully asynchronous. Neighbors that wish to communicate estimate the relative phase difference between their sleep/wake cycles. A station uses this phase information to order its pending transmissions to use the available periods of overlap most efficiently. Stations can also adjust their phase relationships to avoid contention and and reduce latency for delay sensitive flows.

The proposed protocol is defined in considerable detail and it is argued that the protocol is likely to exhibit good energy savings as well as acceptable network performance. The proposed protocol is also carefully distinguished from related work in this area. Based on these arguments, it is recommended that work continue to implement the proposed protocol in a fully featured simulation environment and more carefully study its effectiveness.

Time, day, location and instantaneous network conditions largely dictate the quality of Voice over IP calls. In this paper we present results of VoIP quality mainly in terms of packet jitter and loss. This work revisits our objective of measuring VoIP quality in 1999 enabling us to make comparisons with the results we obtained three years ago. We improved the measurement infra-structure we used previously through adding new functionality plus using more test sites. Furthermore, we present findings on the influence of parameters such as packet size, asymmetry, silence suppression and location as well as much more comprehensive loss and jitter results. Our results conclude that the quality of Voice over IP sessions have improved over the last three years. In spite of this fact however, achieving acceptable global Voice over IP quality still remains a challenge.

We prove a result concerning objective functions that can be used to obtain efficient and balanced solutions to the multi-commodity network flow problem. This type of solution is of interest when routing traffic in the Internet. A particular case of the result proved here (see Corollary 2 below) was stated without proof in a previous paper.

New optical network technologies provide opportunities for fast, controllable bandwidth management. These technologies can now explicitly provide resources to data paths, creating demand driven bandwidth reservation across networks where an applications bandwidth needs can be meet almost exactly. Dynamic synchronous Transfer Mode (DTM) is a gigabit network technology that provides channels with dynamically adjustable capacity. TCP is a reliable end-to-end transport protocol that adapts its rate to the available capacity. Both TCP and the DTM bandwidth can react to changes in the network load, creating a complex system with inter-dependent feedback mechanisms. The contribution of this work is an assessment of a bandwidth allocation scheme for TCP flows on variable capacity technologies. We have created a simulation environment using ns-2 and our results indicate that the allocation of bandwidth maximises TCP throughput for most flows, thus saving valuable capacity when compared to a scheme such as link over-provisioning. We highlight one situation where the allocation scheme might have some deficiencies against the static reservation of resources, and describe its causes. This type of situation warrants further investigation to understand how the algorithm can be modified to achieve performance similar to that of the fixed bandwidth case.

We consider a queueing network with two parallel heterogeneous servers. Each server has its own queue and customers arrive at each queue according to independent Poisson processes. Service times are independent and exponentially distributed. When a customer arrives at queue 1, the customer can be transferred to queue 2 by paying an assignment cost. Each customer in queue pays a holding cost per unit time. The objective is to dynamically determine the optimal assignment policy, based on the state of the system, so as to minimize the average cost. This model has policy implications for computer or communication networks. In this paper, a novel approach is presented using fuzzy control to solve the problem. Simulation shows that the approach is efficient and promising.

We present a temporal debugger, capable of examining time flow of applications in general-purpose computer systems. The debugger is attached to a complete system simulator, which models an entire workstation in sufficient detail to run commodity operating systems and workloads. Unlike traditional debuggers, a debugger operating on a simulated system does not disturb the timing of the target program, allowing reproducible experiments and large amounts of instrumentation and monitoring without intrusion.

We have implemented the temporal debugger by modifying the GNU debugger to operate on applications in a simulated Linux system. Debugger implementation is difficult because the debugger expects application-related data, whereas the simulator provides low-level data. We introduce a technique, virtual machine translation, for mapping simulator data to the debugger by parsing operating system data structures in the simulated system.

The debugger environment allows collection of performance statistics from multiple abstraction levels: hardware, operating system, and application level. We show how this data can be used to profile quality of service performance of a video decoder. The debugger is used to detect display jitter, and by correlating runtime statistics to image rendering time, we expose deviations when the application is unable to render an image in time, thereby locating the cause of the display jitter.

A mobile ad hoc network (or manet) is a group of mobile, wireless nodes which cooperatively form a network independent of any fixed infrastructure or centralized administration. In particular, a manet has no base stations: a node communicates directly with nodes within wireless range and indirectly with all other nodes using a dynamically-computed, multi-hop route via the other nodes of the manet. Simulation and experimental results are combined to show that energy and bandwidth are substantively different metrics and that resource utilization in manet routing protocols is not fully addressed by bandwidth-centric analysis. This report presents a model for evaluating the energy consumption behavior of a mobile ad hoc network. The model was used to examine the energy consumption of two well-known manet routing protocols. Energy-aware performance analysis is shown to provide new insights into costly protocol behaviors and suggests opportunities for improvement at the protocol and link layers.

An ad hoc network must operate independently of a pre-established or centralized network management infrastructure, while still providing administrative services needed to support applications. Address allocation, name resolution, service location, authentication, and access control policies represent just some of the functionality that must be supported - without pre-configuration n or centralized services.

In order to solve these problems, it is necessary to leverage some aspect of the environment in which the network operate. We introduce the notion of a spontaneous network, created when a group of people come together for some collaborative activity. In this case, we can use the human interactions associated with the activity in order to establish a basic service and security infrastructure.

We structure our discussion around a practical real-world scenario illustrating the use of such a network, identifying the key challenges involved and some of the techniques that can be used to address them.

Several overload admission control architectures have been developed to protect web servers from overload. Some of these architectures base their admission decision on information found in the HTTP header. In this context, persistent connections represent a challenging problem since the HTTP header of the first request does not reveal any information about the resource consumption of the requests that might follow on the same connection. We have previously presented a kernel-based architecture that protects web servers from overload. The implemented mechanisms have proven to be more efficient and scalable than application level controls implemented in the web server. In this paper, we extend the kernel-based architecture to prevent overload caused by persistent connections. We evaluate our approach by various experiments.

The increasing number of Internet users and innovative new services such as e-commerce are placing new demands on Web servers. It is becoming essential for Web servers to provide performance isolation, have fast recovery times, and provide continuous service during overload at least to preferred customers. In this paper, we present the design and implementation of three kernel-based mechanisms that protect Web servers against overload by providing admission control and service differentiation based on connection and application level information. Our basic admission control mechanism, TCP SYN policing, limits the acceptance rate of new requests based on the connection attributes. The second mechanism, prioritized listen queue, supports different service classes by reordering the listen queue based on the priorities of the incoming connections. Third, we present HTTP header-based connection control that uses application-level information such as URLs and cookies to set priorities and rate control policies. We have implemented these mechanisms in AIX 5.0. Through numerous experiments we demonstrate their effectiveness in achieving the desired degree of service differentiation during overload. We also show that the kernel mechanisms are more efficient and scalable than application level controls implemented in the Web server.

We present a temporal debugger, capable of examining time flow of soft real-time applications in Unix systems. The debugger is based on a simulator modelling an entire workstation in sufficient detail to run unmodified operating systems and applications. It provides a deterministic and non-intrusive debugging environment, allowing reproducible presentation of program time flow.

The primary contribution of this paper is virtual machine translation, a technique necessary to debug applications in a simulated Unix system. We show how a virtual machine translator maps low-level data, provided by the simulator, to data useful to a symbolic debugger. The translator operates by parsing data structures in the target operating system and has been implemented for the GNU debugger and simulated Linux systems.

Packet loss is an important parameter for dimensioning network links or traffic classes carrying IP telephony traffic. We present a model based on the Markov modulated Poisson process (MMPP) which calculates packet loss probabilities for a set of superpositioned voice input sources and the specified link properties. We do not introduce another new model to the community, rather try and verify one of the existing models via extensive simulation and a real world implementation. A plethora of excellent research on queuing theory is still in the domain of ATM researchers and we attempt to highlight it's validity to the IP Telephony community.

Packet level simulations show very good correspondence with the predictions of the model. Our main contribution is the verification of the MMPP model with measurements in a laboratory environment. The loss rates predicted by the model are in general close to the measured loss rates and the loss rates obtained with simulation. The general conclusion is that the MMPP-based model is a tool well suited for dimensioning links carrying packetized voice in a system with limited buffer space.

Energy-aware design and evaluation of network potocols requires knowledge of the energy consumption behavior of actual wireless interfaces. But little practical information is available about the energy consumption behavior of well-known wireless network interfaces and device specifications do not provide information in a form that is helpful to protocol developers. This paper describes a series of experiments which obtained detailed measurements of the energy consumption of an IEEE 802.11 wireless network interface operating in an ad hoc networking environment. The data is presented as a collection of linear equations for calculating the energy consumed in sending, receiving and discarding broadcast and point-to-point data packets of various sizes. Some implications for protocol design and evaluation in ad hoc networks are discussed.

We present a temporal debugger, capable of examining temporal behaviour of operating systems. The debugger is based on a simulator modelling an entire workstation at the instruction level. Unlike traditional debuggers, which need to interfere with program execution, a simulation-based debugger can operate without disturbing time flow of the simulated system. This allows non-intrusive and reproducible debugging of general-purpose operating systems, such as Linux.

We demonstrate the utility of the temporal debugger by analysing two time sensitive parts of Linux, scheduling and interrupt handling. We show how our tool allows a user to identify and isolate temporally unsatisfactory behaviour, and examine short sequences in detail.

Mobile computing and communication is predominantly based on the well-established client-server paradigm, meaning that the mobile unit depends on support from some infrastructure (servers) in order to communicate. This is true even if the mobile units are located very close to each other. By contrast, human communication is based on direct peer-to-peer interaction.

We introduce the concept of spontaneous networking which is independent of infrastructure and more closely follows the human peer-to-peer communication model. We argue that spontaneous networking will enable a more natural form of wireless computing when people physically meet in the real world. This form is more intuitive for the average user and therefore easier to understand and use. The independence from infrastructure makes spontaneous networking possible anywhere, anytime and without being dependent on any third party.

We discuss some of the unique challenges associated with spontaneous networking and identify some of the enabling technologies.

We model a web client using empirical probability distributions for user clicks and transferred data sizes. By using a heuristic threshold value to distinguish user clicks in a packet trace we get a simple method for analyzing large packet traces in order to get information about user OFF times and amount of data transferred due to a user click. We derive the empirical probability distributions from the analysis of the packet trace. The heuristic is not perfect, but we believe it is good enough to produce a useful web client model. We use the empirical model to implement a web client traffic generator. The characteristics of the generated traffic is very close to the original packet trace, including self-similar properties.

Ad hoc networks are mobile wireless networks which do not have any kind of fixed infrastructure. The routing layer in an ad hoc network ties the network together into a seamless entity and provide transparent services to higher layer protocols. This thesis examines the interactions of two routing protocols, AODV and DSR and how the mobile ad hoc network environment affect TCP performance. The results presented here are as follows: the path length and the presence of competing traÆc are the main factors of TCP throughput performance. The size of TCP window affects the loss rate, but the loss rate is not strongly correlated to throughput performance. Using TCP selective acknowledgment option does not improve throughput. Finally, there is hardly any difference in TCP throughput when using DSR and AODV. These conclusions are supported by extensive simulation experiments.

In this paper we present a kernbased architecture that protects Internet servers against overload by controlling the amount and rate of work entering the system. Our basic control algorithm limits the incoming TCP SYN requests based on connection attributes. By dropping non-compliant connection requests, the server can provide continuous service to preferred clients even under overload. We present a second mechanism that reorders the listen queue of a server socket based on the priorities of the incoming connection requests. Our experiments show that both mechanisms enable service differentiation during overload. We describe an adaptive architecture that uses these mechanisms to dynamically protect web servers from overload.

Digital convergence is precipitating the addition of soft real-time applications to mainstream desktop and server operating environments. Most traditional debuggers for mainstream systems lack a notion of temporal correctness, making them unsuitable for real-time system design and analysis.

We propose leveraging complete system simulation to build a temporal debugger capable of analyzing mixed real-world workloads. Traditional real-time system debuggers based on simulation utilize slow, but accurate, simulators. Complete system simulators accept an approximate model of time in exchange for higher performance. The higher performance allows these simulators to analyze high-end commercial operating systems and applications.

We describe a temporal debugger design based on complete system simulation and report on some early experiences in analyzing a simple workload. The tool offers a non-intrusive, predictable environment for debugging complex workloads with partial real-time constraints. The simulator foundation allows for interactive debugging of time-critical sequences while preserving a model of execution time flow.

Transmitting telephone calls over the Internet causes problems not present in current telephone technology such as packet loss and delay due to queueing in routers. In this undergraduate thesis we study how a Markov modulated Poisson process is applied as an arrival process to a multiplexer and we study the performance in terms of loss probability. The input consists of the superposition of independent voice sources. The predictions of the model is compared with results obtained with simulations of the multiplexer made with a network simulator. The buffer occupancy distribution is also studied and we see how this distribution changes as the load increases.

A Mobile Ad hoc NETwork (manet) is a mobile, multi-hop wireless network which is capable of autonomous operation. It is characterized by energy-constrained nodes, bandwidth-constrained, variable-capacity wireless links and dynamic topology, leading to frequent and unpredictable connectivity changes. In the absence of a fixed infrastructure, manet nodes cooperate to provide routing services, relying on each other to forward packets to their destination. Routing protocols designed for the fixed network are not effective in the dynamic and resource-constrained manet environment; many alternative routing protocols have been suggested. This report provides an overview of a number of manet routing protocols. More importantly, it defines a taxonomy that is suitable for examining a wide variety of protocols in a structured way and exploring tradeoffs associated with various design choices. The emphasis is on practical design and implementation issues rather than complexity analysis.

As the Internet grows, more and more applications are being networked. In this thesis, we use the Nemesis operating system to provide networked applications with service guarantees from both the network and the end system. The Nemesis operating system is designed from scratch to provide applications with service guarantees. Nemesis allows applications to reserve resources such as CPU time, transmit bandwidth on network interfaces and disk I/O bandwidth. We have implemented communication protocols in Nemesis. The ability of Nemesis to reserve CPU time enables applications to run the protocol stack within a guaranteed time and the ability to rserve transmit bandwidth enables applications to transmit data into the network at guaranteed rates. Experiments with the Nemesis TCP show, that networked applications with CPU time and transmit bandwidth reservations transmit at desired rates even when several applications contend for both CPU time and transmit bandwidth. We have also implemented the resource reservation protocol RSVP that reserves resources in the network. Nemesis is thus able to provide networked applications with end-to-end service guarantees.

Measurement and analysis of real traffic is important to gain knowledge about the characteristics of the traffic. Without measurement, it is impossible to build realistic traffic models. It is recent that data traffic was found to have self-similar properties. In this thesis work traffic captured on the network at SICS and on the Supernet, is shown to have this fractal-like behaviour. The traffic is also examined with respect to which protocols and packet sizes are present and in what proportions. In the SICS trace most packets are small, TCP is shown to be the predominant transport protocol and NNTP the most common application. In contrast to this, large UDP packets sent between not well-known ports dominates the Supernet traffic. Finally, characteristics of the client side of the WWW traffic are examined more closely. In order to extract useful information from the packet trace, web browsers use of TCP and HTTP is investigated including new features in HTTP/1.1 such as persistent connections and pipelining. Empirical probability distributions are derived describing session lengths, time between user clicks and the amount of data transferred due to a single user click. These probability distributions make up a simple model of WWW-sessions.

The Nemesis operating system is designed to provide Quality of Service to applications. Nemesis also allows applications to reserve CPU time and transmit bandwidth on network interfaces. We have implemented a TCP for Nemesis that makes use of these guarantees. We show that the Nemesis transmit scheduler rate-controls TCP traffic and thus leads to predictable traffic behavior when applications choose not to utilize non-allocated bandwidth. Applications that want to make use of the non-allocated transmit bandwidth receive the guaranteed bandwidth plus a share of the non-allocated bandwidth. We also study the impact of the guaranteed fraction of CPU time on the throughput that networked applications achieve. We measure the amount of CPU time applications have to reserve in order to run the TCP protocol stack and send data at a particular speed. We show that these values hold even when several applications strive for CPU time and transmit bandwidth.

In this paper we review previous work on the applicability and performance of Integrated Layer Processing (ILP). ILP has been shown to clearly improve computer communication performance when integrating simple data manipulation functions, but the situation has been less clear for more complex functions and complete systems.

We discuss complications when applying ILP to protocol stacks, the requirements of ILP on the communication subsystem, caching aspects, the importance of the processor registers, and a model for predicting the performance of data manipulation functions.

We conclude that the main drawback of ILP is its limited aplicability to complex data manipulation functions. The performance to expect from an ILP implementation also depends heavily on the protocol architecture and the host system architecture.

Instruction-set simulators allow programmers a detailed level of insight into, and control over, the execution of a program, including parallel programs and operating systems. In principle, instruction set simulation can model any target computer and gather any statistic. Furthermore, such simulators are usually portable, independent of compiler tools, and deterministic-allowing bugs to be recreated or measurements repeated. Though often viewed as being too slow for use as a general programming tool, in the last several years their performance has improved considerably. We describe SIMICS, an instruction set simulator of SPARC-based multiprocessors developed at SICS, in its rôle as a general programming tool. We discuss some of the benefits of using a tool such as SIMICS to support various tasks in software engineering, including debugging, testing, analysis, and performance tuning. We present in some detail two test cases, where we've used SimICS to support analysis and performance tuning of two applications, Penny and EQNTOTT. This work resulted in improved parallelism in, and understanding of, Penny, as well as a performance improvement for EQNTOTT of over a magnitude. We also present some early work on analyzing SPARC/Linux, demonstrating the ability of tools like SimICS to analyze operating systems.

Integrated Layer Processing is an implementation technique for data manipulation functions in communication protocols. The purpose of this technique is to increase communication performance. It reduces the number of memory accesses and thus relieves the memory bandwidth bottleneck. Integrated Layer Processing can however, in some situations, substantially increase the number of memory accesses, and therefore instead reduce performance. The main reason is contention for processor registers.

We present a performance model that captures the memory behavior of data manipulation functions for both integrated and sequential implementations. By comparing the model to measurements of real and synthetic data manipulation functions, we show that the model accurately predicts the performance. The model can be used to assess whether an integrated implementation will perform better or worse than a sequential implementation. The situations where integration would reduce performance can then be avoided without spending a lot of effort on a more complex integrated implementation.

We describe novel techniques used for efficient simulation of memory in SimICS, an instruction level simulator developed at SICS. The design has focused on efficiently supporting the simulation of multiprocessors, analyzing complex memory hierarchies and running large binaries with a mixture of system-level and user-level code. A software caching mechanism (the Simulator Translation Cache, STC) improves the performance of interpreted memory operaions by reducing the number of calls to complex memory simulation code. A lazy memory allocation scheme reduces the size of the simulator process. A well-defined internal interface to generic memory simulation simplifies user extensions. Leveraging on a flexible interpreter based on threaded code allows runtime selection of statistics gathering, memory profiling, and cache simulation with low overhead. The result is a memory simulation that supports a range of features for use in computer architecture research, program profiling, and debugging.

Integrated Layer Processing (ILP) has been presented as an implementation technique to improve communication protocol performance by reducing the number of memory references. Previous research has however not pointed out that in some circumstances ILP can significantly increase the number of memory references, resulting in lower communication throughput.

We explore the performance effects of applying ILP to data manipulation functions with varying characteristics. The functions are generated from a set of parameters including input and output block size, state size and number of instructions. We present experimental data for varying function state sizes, number of integrated functions and instruction counts.

The results clearly show that the aggregated state of the functions must fit in registers for ILP to be competitive.

The DDMlite is a COMA shared-memory multiprocessor prototype built at SICS. Starting in June last year, less than two man years has been spent on architecture, hardware design, implementation and debugging to a running system. Using experience from previous projects, focusing on the research-relevant architectural issues while sacrificing some performance, and using state-of-the art tools, we have been able to build a functional multiprocessor prototype with a minimal effort. When fully equipped the DDMlite will have 24 processors and 192 MB COMA attraction memory. The custom node controller board consists of three Xilinx XC4013 and one AMD Mach435 FPGAs, SRAM memory and buffer circuits. The DDMlite is an implementation of the BB-COMA architecture previously presented in [1]. We present the detailed architecture of the DDMlite - in particular the node controller implementation, and explain the complexity/performance trade-offs that enabled us to reach our goals on time. Early results from experiments with the prototype will als be presented.

Cache memory behavior is becoming more and more important as the speed of CPUs is increasing faster than the speed of memories. The operation of caches are statistical which means that the system level performance becomes unpredictable.

In this paper we investigate the worst case behavior of cache line conflicts in the context of communication protocols implemented using Integrated Layer Processing. The goal of our work is to control the cache by placing communication buffers and code in non-conflicting positions in the cache. The result would be higher and more predictable performance. Our first results indicate that the worst case behavior can be up to almost four times slower than the best case.

Many current implementations of communication subsystems on workstation class computers transfer communication data to and from primary memory several times. This is due to software copying between user and operating system address spaces, presentation layer data conversion and other data manipulation functions. The consequence is that memory bandwidth is one of the major performance bottlenecks limiting high speed communication on these systems.

We propose a communication subsystem architecture with a minimal-copy data path to widen this bottleneck.

The architecture is tailored for protocol implementations using Integrated Layer Processing (ILP) and Application Layer Framing (ALF). We choose to implement these protocols in the address space of the application program. We present a new application program interface (API) between the protocols and the communication service in the operating system kernel. The API does not copy data, but instead passes pointers to page size data buffers. We analyze and discuss ILP loop and cache memory requirements on these buffers. Initial experiments show that the API can increase the communication performance with 50% compared to a standard BSD Unix socket interface.

We present a so-called no-copy Application Programming Interface (API) for communication. The interface avoids copying when data is transferred between the application and operating system kernel address spaces. The API is an extension to the socket interface for SunOS, and has been implemented on Sun SPARCstations equipped with Fore Systems ATM adapters.

Throughput for the no-copy API is 85 Mbit/s for 8K UDP messages, to be compared to 57 Mbit/s for the regular API on the SPARCstation 2. Processing times through the TCP and UDP stacks are reduced by up to 30% for the SPARCstation 2 and by more than 50% for the SPARCstation 10.

We describe novel techniques used for efficient simulation of memory in SimICS, an instruction level simulator developed at SICS. The design has focused on efficiently supporting the simulation of multiprocess, analyzing complex memory hierarchies and running large binaries with a mixture of system-level and user-level code. A software caching mechanism (the Simulator Translation Cache, STC) improves the performance of interpreted memory operations by reducing the number of calls to complex memory simulation code. Major data structures are allocated lazily to reduce the size of the simulator process. A well-defined internal interface to generic memory simulation simplifies user extensions. Leveraging on a flexible interpreter based on threaded code allows runtime selection of statistics gathering, memory profiling, and cache simulation with low overhead. The result is a memory simulation scheme that supports a range of features for use in computer architecture research, program profiling, and debugging.

Instruction set architecture (ISA) simulators are an increasingly popular class of tools for both research and commercial purposes. Common applications include trace generation, program development, and compatibility support. A major concern with ISA simulators is performance and memory overhead. A common technique for achieving good performance is to use threaded code, which involves translating the target object code to an intermediate format which is subsequently interpreted. We describe such an internal format, which we call the 64-bit format, that is compact and meets a range of requirements in terms of flexibility and simplicity. We show how a simulator using this format can be implemented efficiently by taking advantage of extensions to the C language supported by the GNU C compilers. We have used the format to write the core interpreter in SimICS, a system level multiprocessor simulator that supports the Motorola 88110 and the SPARC V8 instruction sets.

Large-scale shared-memory multiprocessors typically have long latencies for remote data accesses. A key issue for execution performance of many common applications is the synchronization cost. The communication scalability of synchronization has been improved by the introduction of queue-based spin-locks instead of Test & (Test & Set). For architectures with long access latencies for global data, attention should also be paid to the number of global accesses that are involved in synchronization. We present a method to characterize the performance of proposed queue lock algorithms, and apply it to previously published algorithms. We also present two new queue locks, the LH lock and the M lock. We compare the locks in terms of performance, memory requirements, code size, and required hardware support. The LH lock is the simplest of all the locks, yet requires only an atomic swap operation. The M lock is superior in terms of global accesses needed to perform synchronization and still competitive in all other criteria. We conclude that the M lock is the best overall queue lock for the class of architectures studied.

We describe novel techniques used for efficient simulation of memory in SimICS, an instruction level simulator developed at SICS. The design has focused on efficiently supporting the simulation of multiprocessors, analyzing complex memory hierarchies and running large binaries with a mixture of system-level and user-level code. A software caching mechanism (the Simulator Translation Cache, STC) improves the performance of interpreted memory operations by reducing the number of calls to complex memory simulation code. A lazy memory allocation scheme reduces the size of the simulator process. A well-defined internal interface to generic memory simulation simplifies user extensions. Leveraging on a flexible interpreter based on threaded code allows runtime selection of statistics gathering, memory profiling, and cache simulation with low overhead. The result is a memory simulation that supports a range of features for use in computer architecture research, program profiling, and debugging.

An implementation of a system level interpreter of the SPARC V8 instruction set architecture is described. The goal is that the simulator, SimICS, should be sufficiently accurate to run an operating system on top of the simulator. The simulation is performed by direct threaded interpretation of an intermediate code. Simulation of condition codes is performed quickly and can handle all combinations of condition codes. The condition codes are evaluated lazily and unnecessary computations are avoided. Access to registers in a register window is as efficient as in a flat file. To optimize instructions specialized variants are identified that can be executed faster. SimICS is tested using a comprehensive test suite. The suite exercises the instruction set using interesting combinations of input parameters and operands and compares the result to a reference implementation. A validation of the results is performed with SPEC benchmarks. The result is a stable and correct system level interpreter of SPARC Architecture Version 8 that runs 15 times slower than the real hardware.

nstruction set architecture (ISA) simulators are an increasingly popular class of tools for both research and commercial purposes. Common applications include trace generation, program development, and compatibility support. A major concern with ISA simulators is performance and memory overhead. A common technique for achieving good performance is to use threaded code, which involves translating the target object code to an intermediate format which is subsequently interpreted. We describe such an internal format, which we call the 64-bit format, that is compact and meets a range of requirements in terms of flexibility and simplicity. We show how a simulator using this format can be implemented efficiently by taking advantage of extensions to the C language supported by the GNU C compilers. We have used the format to write the core interpreter in SimICS, a system level multiprocessor simulator that supports the Motorola 88110 and the SPARC V8 instruction sets.

Instruction-level simulators, also called register-transfer level simulators, are a crucial component in developing and analyzing computer architectures and system software. Simulating a multiprocessor presents some special problems, notably code expansion and efficient time slicing of processors. Also, modern processors have aggravated the memory bottleneck, and the internal formats used by a simulator must be compact. This paper presents a design for a unit-delay simulator for a shared-memory multiprocessor that comes far in meeting these requirements. The simulator interprets at system level, i.e., it faithfully reproduces the interfaces of the principal devices. Previous work in the area is discussed.

Traditional simulation of a target architecture by interpreting object code can be improved by translating the object code to an intermediate format. This approach is called interpretive translation. Despite a substantial performance improvement over traditional interpretation, a large part of the overhead is unnecessary. An alternative approach is block translation, where one or more simulated instructions are translated to directly executable code. This approach has several drawbacks. We discuss the problems with block translation, analyse the overhead of interpretive translation, and describe a hybrid approach-partial translation-that combines the benefits of both approaches. Partial translation implements an intermediate format that supports the addition of run-time generated code whenever appropriate. The perfor- mance limit (slowdown) of interpetive translation is around 15, and real implementations have achieved 20-30. Partial translation will perform considerably better. Finally, we present results from an aggressive implementation of interpretive translation, and results from a proof-of-concept implementation of partial translation.

Instruction-level simulators, also called register-transfer level simulators, are a crucial component in developing and analyzing computer architectures and system software. Simulating a multiprocessor presents some special problems, notably code expansion and efficient time slicing of processors. Also, modern processors have aggravated the memory bottleneck, and the internal formats used by a simulator must be compact. This paper presents a design for a unit-delay simulator for a shared-memory multiprocessor that comes far in meeting these requirements. The simulator interprets at system level, i.e., it faithfully reproduces the interfaces of the principal devices. Previous work in the area is discussed.

Traditional simulation of a target architecture by interpreting object code can be improved by translating the object code to an intermediate format. This approach is called interpretive translation. Despite a substantial performance improvement over traditional interpretation, a large part of the overhead is unnecessary. An alternative approach is block translation, where one or more simulated instructions are translated to directly executable code. This approach has several drawbacks. We discuss the problems with block translation, analyse the overhead of interpretive translation, and describe a hybrid approach-partial translation-that combines the benefits of both approaches. Partial translation implements an intermediate format that supports the addition of run-time generated code whenever appropriate. The performance limit (slowdown) of interpretive translation is around 15, and real implementations have achieved 20-30. Partial translation will perform considerably better. Finally, we present results from an aggressive implementation of interpretive translation, and results from a proof-of-concept implementation of partial translation.

Instruction-level simulators, also called register level simulators, are a crucial component in developing and analyzing computer architectures and system software. This thesis describes the essential components of a Tadpole multi-processor simulator, a Motorola 88000 RISC-based computer. The simulator is sufficiently accurate to boot the monitor program, and runs approximately 30 times slower than the real machine. Possible extensions to improve this slowdown, and some of the issues that will arise when the simulator is extended to simulate a shared-memory multiprocessor, is discussed. The thesis of the author is, in part, to demonstrate for a particular parallel architecture that several of the uses of a simulator can be partially or fully satisfied in a single program. In other words, functionality need not compromise efficiency to the extent previously supposed. A discussion and critique of previous work in the area is presented. Efficient ways of simulating MC88100 instructions and of representing them internally is dealt with in some detail.

Instruction-level simulators, also called register level simulators, are a crucial component in developing and analyzing computer architectures and system software. This thesis describes the essential components of a Tadpole multi-processor simulator, a Motorola 88000 RISC-based computer. The simulator is sufficiently accurate to boot the monitor program, and runs approximately 30 times slower than the real machine. Possible extensions to improve this slowdown, and some of the issues that will arise when the simulator is extended to simulate a shared-memory multiprocessor, is discussed. The thesis of the author is, in part, to demonstrate for a particular parallel architecture that several of the uses of a simulator can be partially or fully satisfied in a single program. In other words, functionality need not compromise efficiency to the extent previously supposed. A discussion and critique of previous work in the area is presented. Efficient ways of simulating MC88100 instructions and of representing them internally is dealt with in some detail.

Modern shared-memory multiprocessors require complex interconnection networks to provide sufficient communication bandwidth between processors. They also rely on advanced memory systems that allow multiple memory operations to be made in parallel. It is expensive to maintain a high consistency level in a machine based on a general network, but for special interconnection topologies, some of these costs can be reduced. We define and study one class of interconnection networks, race-free networks. New conditions for sequential consistency are presented which show that sequential consistency can be maintained if all accesses in a multiprocessor can be ordered in an acyclic graph. We show that this can be done in race-free networks without the need for a transaction to be globally performed before the next transaction can be issued. We also investigate what is required to maintain processor consistency in race-free networks. In a race-free network which maintains processor consistency, writes may be pipelined, and reads may bypass writes. The proposed methods reduce the latencies associated with processor write-misses to shared data.