Co-operative Adaptation Between End Points
Peter Reiher, Richard Guy, Kevin Eustice, Vincent Ferreria, Mark Yarvis
University of California, Los Angeles
Abstract
Open architecture systems present many challenges for system and application designers. Problems such as selecting adaptations, reliability, and security are overly complicated in traditional adaptation paradigms. Frequently, network applications operate peer to peer – where it is in the best interest of both parties to communicate. This model can be exploited to our benefit in open architectures. By shifting adaptation models towards co-operative adaptation along endpoints, hard problems can be simplified; at the same time, we can still maintain desired flexibility.
1.Introduction
Open architecture systems typically assume one of two models of deployment in their designs. Some systems assume a single point of adaptation, such as proxies. A slight variant is systems that perform adaptation on both sides of a single troublesome link. The common alternative is an architecture that assumes widespread deployment of adaptation capabilities. While perhaps not every node is capable of running adaptive code, potentially any router, end machine, gateway, server, firewall, or other machine could be configured to adapt data streams. Such architectures must take many complex possibilities into account in their design, since the system must work properly even for such complex cases.
The first model has the advantages of simplicity and easy deployment. As a result, it is in wide use today. However, it can not meet all the needs of future networks, as it provides a myopic view of the network and its problems. If both the sender and receiver of the data stream use this model, they may perform redundant adaptations (both compressing and decompressing the data stream, for example), or may perform incompatible adaptations (the sender strips all color from a color video stream, while the receiver tries to reduce from full color to a more limited palette). In such a model, those two adaptable endpoints are completely unaware of each other’s existence, and will do nothing to coordinate their activities.
The second model has the full power of generality, but with that power comes a significant set of problems to solve to make the system practical. These problems include difficult performance and security issues, as well as serious distributed systems issues of coordination and reliability.
An intermediate approach between these two extremes has yet to be thoroughly explored. Adaptation could be enabled where it is most easily deployed, at or near the endpoints. Nodes at or near the endpoints could cooperate to provide a coherent set of adaptations. This paper discusses the cooperative endpoint model in more detail, covering areas of applicability, its practical advantages for solving certain hard problems of distributed adaptation, and its limitations.
2.The Cooperative Endpoint Model
An intermediate model offers many of the advantages of both of these existing models. In this model, adaptation essentially occurs only at the endpoints of a point-to-point connection, but the adaptation at both endpoints is coordinated. If both the sender and receiver need to reduce the amount of data being transmitted over their connections to the larger network, the sender will compress before sending and the receiver decompress after receiving. A redundant decompression/compression cycle is avoided, and the overall network is less burdened with data transmission. If security is required, end-to-end encryption can be used. If the data must be customized for a PDA receiver, the customization (and probable reduction in data size) can be performed at the sending node.
This model of adaptation has several advantages. First, many of the more troublesome links and nodes in the networks are close to the edges of the network, anyway. Dial up lines, wireless LAN links, serial lines, and other links of limited capability are not typically used to hook up backbone routers. While this observation is not universally true (satellite links can connect backbone routers, for example, and they have troublesome characteristics), it does cover many cases.
A second advantage is that the end points are under control of (possibly distinct) parties that have a vested interest in the adaptation occurring. Both sender and receiver presumably want the data transmission to occur in the best fashion possible, and are willing to take reasonable measures to achieve that goal. Further, these sites have the best knowledge of the purpose of the transmission, and are thus best able to weigh the costs and benefits of performing adaptation.
A third advantage is that this model decreases the security risks associated with performing adaptations in the middle of the network. The only parties involved in adaptation are those who want to participate in the transmission, and who thus understand the security risks. Further, they are end nodes, and their corruption will have much more limited effects than corruption of a backbone router or ISP point of presence.
Figure 1. A typical scenario for endpoint adaptation.
A fourth advantage is that this model decreases concerns about the scalability of adaptive systems. A backbone router that provides adaptive services faces many scalability concerns, including providing adaptive capabilities for large numbers of flows simultaneously, maintaining many different pieces of adaptation code, and ensuring the secure operation of large numbers of different adaptation modules. In this model, on the other hand, the end nodes need only concern themselves with traffic that they initiate. They can limit the modules they use to those suitable for the kinds of data they handle. The security scaling problem is bounded, since there are controllably few modules to run and controllably few partners who must be authenticated.
A fifth advantage of this model is that several hard problems for general network open architectures become simpler. For example, in the general case where any node in the network can potentially adapt a data flow, there are significant problems of reliability. Each point of adaptation becomes another potential point of failure, and, to the extent that the adaptation was stateful or there was established connectivity between adaptors on different nodes, the failure of one adaptor can lead to a difficult problem in maintaining the connection. In a non-adaptive network, such a failure merely causes packets to take a different route. In this new model, however, adaptation only occurs near the end points. Usually, one can assume that failure of one of those end points will lead to failure of the overall connection. Failures of adaptors that do not crash adaptation nodes can be handled by relatively simple recovery mechanisms, because the limitations of the system rule out complexities that make recovery difficult.
The model can be slightly generalized without losing significant advantages. Instead of assuming a single point of adaptation on each end, the model can accommodate contiguous segments of adaptability on each end, with a “black box” network providing no adaptability between the segments. For example, on one end a user on a machine at his home might dial up a server, which communicates with a local router, which in turn is connected to an ISP. The home machine, the server, and the router are all in the same administrative domain, and can all reasonably provide homogenous adaptive services. At the other end, a router may connect to a wireless bridge, which sends the data over a wireless LAN to a portable computer. At this end, the router, bridge, and portable computer can all run adaptation services. However, the network in the middle does no adaptation. Figure 1 shows this scenario, with the segments of adaptability shown in the circles at either end of the connection.
Generally, the model allows an arbitrary number of adaptation locations at each end of a connection, with a region between the adaptive ends where no adaptation is possible. Each adaptive segment is assumed to be a single administrative domain. Thus, the required software (both the middleware and the actual adaptive modules) can be assumed to be deployed where necessary in the segment, and any required security associations, certificates, or shared keys can be arranged in a relatively straightforward manner. Further, all elements of the segment are assumed to be willing to devote reasonable resources to adapting data flows that originate or terminate at nodes in the segment. Each of the two segments, however, is its own administrative domain, and thus the two segments do not share these advantages between them.
3.Applications of Endpoint Adaptation
A broad spectrum of existing and emerging applications can benefit from this intermediate open architecture model. These include human-to-human communication services, streaming media services, network-based games, file transfer, and smart appliance-enabled purchasing.
Human-to-human communication services range from Internet (voice) telephony to instant messaging to video telephony to distributed whiteboarding. Each of these has a characteristic reliance on an intermediate network outside the control of the end users, but with network and computational resources at the “endpoint” sub-networks that are (or easily could be) under at least some control of the end users. Each of these services also could benefit from one or more adaptations: session-oriented, encryption-based privacy and integrity enforcement; multi-path routing for improved performance and/or security; forward-error correction for mobile wireless end users; lossy compression for bandwidth-constrained links; and format conversion from audio-to-text and vice-versa to compensate for extreme bandwidth limitations. These adaptations may be required at a given endpoint or across the WAN between the endpoints.
Streaming audio and video services such as the existing RealPlayer and RealJukebox products from RealNetworks.com already employ a proprietary form of endpoint adaptation: the endpoints negotiate an appropriate degree of resolution for the data to be streamed, relative to current assessments of network quality of service. Our model would provide a standard framework in which to make not just the conventional arrangements for adaptation, but additional adaptations not envisioned by the service, or deliberately not deployed for development economy’s sake.
Network-based games such as Quake and Doom are often latency-sensitive, and dynamic adaptation of resolution to compensate for limited bandwidth would improve playability. This application-space is another opportunity for an open architecture intermediate model to provide adaptations not originally built into the game.
File transfer protocols like FTP and Gnutella [Gnutella] may require obvious adaptations such as security and compression. In addition, format conversion may be a useful candidate: the choice of whether and where to perform DOS-to-Unix line break translation should be planned, rather than unilaterally decided by one endpoint or the other. Similarly, on-the-fly human language translation requires planning and decision making at the endpoints of the network connection, and not in the intermediate internetwork.
Finally, the arena of network-enabled home appliances and the emerging possibilities of automatic purchasing and re-supply of consumables raise issues of network protocol incompatibility. For instance, Bluetooth-enabled [Bluetooth] refrigerators may need to communicate via the Internet with the local grocery store, despite the absence of IP protocol stacks on one of the endpoints. With our model, negotiation of what protocol to use end-to-end, and appropriate protocol conversion and tunneling, can be performed—even if the endpoints are unaware of each other’s native protocols.
4.Planning for Endpoint Adaptation
Open architectures present a spectrum of planning problem domains. Proxy architectures are at one end of the spectrum, providing local decision making without any coordination with other points of adaptation that might be present. Active networks and other multi-point adaptation architectures are at the other end of the spectrum, requiring complex coordination between unrelated nodes that have independent goals.
In general, planning for adaptation in open architectures consists of detecting the conditions of the links over which data will travel and selecting a coherent set of adaptors to deploy into the network. Inputs to this process include the protocol being adapted, the properties of the links over which data will flow (bandwidth, latency, security, etc), the resources available at the potential points of adaptation (CPU cycles, storage space, etc), and the set of available adaptations. In the most complex case, where adaptation can occur at many points throughout the network, choosing an appropriate set of adaptors can be difficult. The solution space is large, and the planning process must complete quickly so that user data can flow without undue delay. In addition, distributed planning requires an exchange of planning information. A simple algorithm would gather the input data from all nodes at one point, perform planning, and distribute a plan to the participants. Since the information exchange between nodes involved in planning competes for the same resources as user data, the planning algorithm itself must conserve bandwidth.
The endpoint adaptation model has some useful characteristics that simplify the planning process. First, since each adaptive segment is autonomous, it may make sense for the bulk of the planning to occur locally to each segment. With half as many nodes involved in each of two planning processes, the size of each planning problem is reduced. In addition, by localizing the bulk of the planning activities, cross-WAN traffic may be reduced.
Other features of the endpoint adaptation model further simplify the local planning process. First, nodes within the adaptable segment at a given endpoint are likely to be willing to work together for the common good of that endpoint. Less negotiation may be needed between the initiating node and the other nodes to arrange for supporting adaptation. Second, within a given adaptive segment, the number of network deficiencies that typically occur and the number of available adaptors will be small. Thus, the number of possible plans is reduced dramatically. Planning within an adaptable segment may take less time and require less communication than does planning among the same number of unrelated nodes.
The endpoint adaptation model may also simplify coordination between adaptive segments. The two segments at either end of a connection share a common goal: successful communication. Unlike an independent node in the core of the network, a node within one segment should be willing to support the requirements of either segment. This willingness to cooperate may again reduce the amount of inter-segment communication needed to negotiate proper adaptations. In addition, communication patterns contain a certain amount of locality. Two communicating nodes have probably communicated before and will likely do so again. Thus, planning for a session between two adaptive segments might only require the selection of the same set of adaptations used in some previous session between the same adaptive segments.
Planning between two adaptive segments cannot be entirely independent, however: any adaptation required for transmission across the WAN, which can be thought of as a single link between the edges of two adaptive segments, may require coordination between segments. For instance, if the WAN provides insufficient security, encryption should be provided within one adaptive segment and decryption within the other. Similarly, if the WAN provides insufficient bandwidth, compression and decompression may be required between the two segments. Actions taken by one adaptive segment may also be incompatible with the conditions in another. For instance, low bandwidth in one adaptive segment may be interpreted by the other adaptive segment as high WAN latency. If the later segment chooses to overcome this problem via prefetching, the problem will worsen.
Additional coordination may also be desired between adaptive segments to remove any redundancy in the adaptations provided by each. For instance, if each adaptive segment includes a 56 Kbps modem link, compression may be desired across each link. However, it is more efficient to compress before the low-bandwidth link in one adaptive segment and decompress after the low-bandwidth link in the other than to perform this operation twice, once within each segment. Even if only one low-bandwidth link exists, it can be argued that compressing data as early as possible in the transmission path can save bandwidth across many links. Therefore, it may be mutually beneficial for one adaptive segment to compress on behalf of another adaptive segment.
Planning in the endpoint adaptation model might consist of two phases. First, each adaptive segment can perform initial planning independently. The information required for planning within that segment (node and link resources, available adaptors, etc) can be exchanged in some manner and a “local” plan can be formulated. Because of the limited number of nodes, problems, and adaptors, a brute-force evaluation of all plans in the planning space may be possible. Or perhaps the problem characteristics may be matched against a set of templates that describe a predetermined set of solutions.