Experiences with network-based user agents for mobile applications

Wireless networks are characterized by simple end devices and limited bandwidth. One solution to address these and other limitations of the wireless mobile environment that has been widely pursued is the placement of proxies, or agents, inside the network to assist with application processing that would normally take place on end devices. These agents can additionally manipulate data to reduce bandwidth requirements and assist in providing services. The design and implementation of a user agent is heavily impacted by the application it supports. In this paper we present our experiences with user agents in two different types of applications: telephony-based Personal Communication Services (PCS) and two-way messaging. To provide low latency service, the PCS user agents are mobile so that they may be kept close to their end devices. The design of the PCS agents limits migration overhead to the transfer of approximately 100 bytes of information in about 150 milliseconds. To provide advanced messaging services, the messaging user agent supports flexible messages while limiting air interface bandwidth usage. The messaging agents reduce uplink bandwidth usage by approximately 35% when applied to a cellular PCS system, and reduce message payloads by 97%. This revised version was published online in June 2006 with corrections to the Cover Date.     

VLSI implementations of communication protocols-a survey

Several protocol controllers for the IEEE 802 local area networks are surveyed and some characteristics for classifying them are given. Some case studies from these controllers are given as illustrations. Two new developments-the protocol engine and the programmable protocol engine-are also described. The protocol engine, currently under development, implements a new protocol called XTP which performs the functions of both the network and transport layers. The programmable protocol engine can implement several connection-oriented protocols by changing contents of a programmable random access memory     

Design and implementation of a high-speed transport protocol

The design, analysis, and implementation of an end-to-end transport protocol that is capable of high throughput consistent with the evolving high-speed physical networks based on fiber-optic transmission lines and high-capacity switches are presented. Unlike current transport protocols in which changes in control/state information are exchanged between the two communicating entities only when some significant event occurs, this protocol exchanges relevant and full state information periodically and frequently. It is shown that this reduces the complexity of protocol processing by removing many of the procedures required to recover from network inadequacies such as bit errors, packet loss, and out-of-sequence packets and makes it more amenable to parallel processing. Also, to increase channel utilization in the presence of high-speed, long-latency networks and to support diagrams, and efficient implementation of the selective repeat method of error control is incorporated in the protocol. An implementation using a Motorola 68030-based multiprocessor as a front-end processor is described. The current implementation can comfortably handle 10-15 kpackets/s     

Conformance testing of protocols specified as communicating finitestate machines-a guided random walk based approach

We present a new approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs). Our approach uses a guided random walk procedure. This procedure attempts to cover all transitions in the component FSMs. We also introduce the concept of observers that check some aspect of protocol behavior. We present the result of applying our method to two example protocols: full-duplex alternating bit protocol and the ATM-adaptation-layer-convergence protocol. Applying our procedure to the ATM adaptation layer, 99% of component FSMs edges can be covered in a test with 11692 input steps. Previous approaches cannot do conformance test generation for standard protocols (such as asynchronous transfer mode (ATM) adaptation layer) specified as a collection of communicating FSMs     

Protocol pruning

A communication system uses a precise set of rules called a protocol, to define interactions among its entities. With advancing computer transmission and switching technology, communication systems are providing sophisticated services demanded by users over a wide area. Protocol standards include a very, large number of options to take care of different service possibilities and to please all the people involved in the Standards Committees. Consequently, protocols have become large and complex, and, therefore their design and analysis have become a formidable task. To cope with this problem, a variety of approaches to simplify the protocols have been proposed in the published literature, such as protocol projection, homomorphism, selective resolution, and many others. We have recently developed a new technique called protocol pruning. It reduces the complexity of the protocols by pruning them to keep only that part which is required for a specified subset of services. More importantly, it takes polynomial (rather than exponential) time and space in the size of the protocol specification. This makes the algorithm feasible for engineers to use for practical problems involving large and complex protocols. We describe the technique and discuss applications to synthesis of protocol converters/gateways, protocol conformance testing, and thinning for lightweight and high performance protocols. The technique could also be useful for protocol implementation, synthesis, validation, and verification     

Formal methods for generating protocol conformance test sequences

The four major methods of conformance test generation reported in the literature are reviewed: transition tours; distinguishing sequences; characterizing sequences; and unique input/output sequences. These methods are used to test the control portion of a protocol specification. The conformance testing concepts developed in the standards world are summarized. Their relationship with the four formal methods is discussed     

AIRMAIL: A link-layer protocol for wireless networks

This paper describes the design and performance of a link-layer protocol for indoor and outdoor wireless networks. The protocol is asymmetric to reduce the processing load at the mobile, reliability is established by a combination of automatic repeat request and forward error correction, and link-layer packets are transferred appropriately during handoffs. The protocol is namedAIRMAIL (AsymmetrIc Reliable Mobile Access In Link-layer). The asymmetry is needed in the design because the mobile terminals have limited power and smaller processing capability than the base stations. The key ideas in the asymmetric protocol design consist of placing bulk of the intelligence in the base station as opposed to placing it symmetrically, in requiring the mobile terminal to combine several acknowledgments into a single acknowledgment to conserve power, and in designing the base stations to send periodic status messages, while making the acknowledgment from the mobile terminal eventdriven. The asymmetry in the protocol design results in a one-third reduction of compiled code. The forward error correction technique incorporates three levels of channel coding which interact adaptively. The motivation for using a combination of forward error correction and link-layer retransmissions is to obtain better performance in terms of end-to-end throughput and latency by correcting errors in an unreliable wireless channel in addition to end-to-end correction rather than by correcting errors only by end-to-end retransmissions. The coding overhead is changed adaptively so that bandwidth expansion due to forward error correction is minimized. Integrity of the link during handoffs (in the face of mobility) is handled by window management and state transfer. The protocol has been implemented. Experimental performance results based on the implementation are presented.     

A New Connection Establishment Procedure for Multidestination Protocols

A new connection establishment procedure for point-to-multipoint data transfer, the multiple attempts in one shot (MAOS) procedure, is proposed. The MAOS procedure is shown to have substantially lower connection establishment time compared to the conventional procedure used in protocols such as HDLC.     

A polynomial algorithm for gateway generation from formalspecifications

A systematic procedure that takes exponential time to synthesize protocol converters from formal specifications is presented. The algorithm proceeds in two steps: compute the largest common subset of services provided by the two mismatched protocols, and reduce the converter, retaining common services, without traversing the entire machine that represents the composition of the two mismatched protocols. In a number of cases, the converter can be constructed by a memoryless translation of messages from one protocol to another. Conditions under which such stateless conversion is possible are given. Two examples are presented to illustrate the techniques. In the first example, a converter that interconnects a half-duplex protocol with a full-duplex protocol from their formal specifications is computed. In the second example, the polynomial procedure is applied to computation of a converter for interconnecting the SNR and TCP protocols