共查询到20条相似文献,搜索用时 78 毫秒
1.
A connection between two hosts across a wide-area network may consist of many sessions over time, each called an incarnation. A connection is synchronized using a connection establishment protocol, based on a handshake mechanism, to allow reliable exchange of data. This paper identifies the precise level of handshake needed under different assumptions
on the nodes and on the network, using a formal model for connection management. In particular, the following parameters are
studied: the size of the memory at the nodes, the information retained between incarnations, and the existence of time constraints
on the network. Among the results we obtain are: (1) If both nodes have bounded memory, no incarnation management protocol
exists. (2) If the nodes have unbounded memory, then a two-way handshake incarnation management protocol exists. (3) If the
nodes have unbounded memory, and the server does not retain connection-specific information between incarnations, then a three-way
handshake incarnation management protocol exists. On the other hand, a two-way handshake incarnation management protocol does
not exist, even if some global information is retained. (4) If a bound on maximum packet lifetime (MPL) is known, then a two-way
handshake incarnation management protocol exists, in which the server does not retain connection-specific information between
incarnations.
Received: July 1995 / Accepted: July 1997 相似文献
2.
Metropolitan area video-on-demand service using pyramid broadcasting 总被引:28,自引:0,他引:28
Pyramid broadcasting is a new way of giving video-on-demand service on a metropolitan scale. We multiplex the most frequently
requested movies on the network, gaining a radical improvement in access time and bandwidth use. This is achieved by using
storage at the receiving end. As the available bandwidth increases, the improvement in access time is exponential instead
of linear as in conventional broadcasting. The larger the bandwidth of the network is, the better gain in the access time
due to pyramid broadcasting. As the access-time requirement decreases, the bandwidth in conventional broadcasting increases
linearly, while the bandwidth in pyramid broadcasting increases only logarithmically. We provide analytical and experimental
evaluations of pyramid broadcasting based on its implementation on an Ethernet LAN. 相似文献
3.
An optimal bandwidth allocation strategy for the delivery of compressed prerecorded video 总被引:1,自引:0,他引:1
The transportation of prerecorded, compressed video data without loss of picture quality requires the network and video
servers to support large fluctuations in bandwidth requirements. Fully utilizing a client-side buffer for smoothing bandwidth
requirements can limit the fluctuations in bandwidth required from the underlying network and the video-on-demand servers.
This paper shows that, for a fixed-size buffer constraint, the critical bandwidth allocation technique results in plans
for continuous playback of stored video that have (1) the minimum number of bandwidth increases, (2) the smallest peak bandwidth
requirements, and (3) the largest minimum bandwidth requirements. In addition, this paper introduces an optimal bandwidth allocation algorithm which, in addition to the three critical bandwidth allocation properties, minimizes the total number of bandwidth
changes necessary for continuous playback. A comparison between the optimal bandwidth allocation algorithm and other critical
bandwidth-based algorithms using 17 full-length movie videos and 3 seminar videos is also presented. 相似文献
4.
In this paper, we propose a new communication abstraction known as the group channel which facilitates and supports the implementation
of multiparty interactive multimedia (MIM) applications such as video conferencing. The group channel is a high-level abstraction for group communication. The credit scheme and the dynamic bandwidth calibration scheme are provided as an integral part of the group channel service for allocating
network bandwidth dynamically as participants join and leave the group channel. The multimedia transport protocol (MTP) is
proposed as a realization of the group channel service in the ATM network. Its prototype implementation and a simple multiparty
video-conferencing application built on top of the MTP prototype are described in this paper. Our results show that the group
channel is capable of guaranteeing the performance of MIM applications irrespective of the group size and differences in workstation
speeds. 相似文献
5.
The system architecture of the Stony Brook Video Server (SBVS), which guarantees end-to-end real-time video playback in a client-server setting, is presented. SBVS employs a real-time network access protocol, RETHER, to use existing Ethernet hardware as the underlying communications media. The video server tightly integrates the bandwidth guarantee mechanisms for network transport and disk I/O. SBVS's stream-by-stream disk scheduling scheme optimizes the effective disk bandwidth without incurring significant scheduling overhead. To demonstrate the feasibility of the proposed architecture, we have implemented a prototype called SBVS-1, which can support five concurrent MPEG-1 video streams on an Intel 486DX2/EISA PC. To our knowledge, this system is the first video server that provides an end-to-end performance guarantee from the server's disks to the each user's display over standard Ethernet. This paper describes the implementation details of integrating network and I/O bandwidth guarantee mechanisms, and the performance measurements that drive and/or validate our design decisions. © 1997 by John Wiley & Sons, Ltd. 相似文献
6.
Summary. A useless checkpoint is a local checkpoint that cannot be part of a consistent global checkpoint. This paper addresses the following
problem. Given a set of processes that take (basic) local checkpoints in an independent and unknown way, the problem is to design communication-induced checkpointing protocols
that direct processes to take additional local (forced) checkpoints to ensure no local checkpoint is useless.
The paper first proves two properties related to integer timestamps which are associated with each local checkpoint. The first
property is a necessary and sufficient condition that these timestamps must satisfy for no checkpoint to be useless. The second
property provides an easy timestamp-based determination of consistent global checkpoints. Then, a general communication-induced
checkpointing protocol is proposed. This protocol, derived from the two previous properties, actually defines a family of
timestamp-based communication-induced checkpointing protocols. It is shown that several existing checkpointing protocols for
the same problem are particular instances of the general protocol. The design of this general protocol is motivated by the
use of communication-induced checkpointing protocols in “consistent global checkpoint”-based distributed applications such
as the detection of stable or unstable properties and the determination of distributed breakpoints.
Received: July 1997 / Accepted: August 1999 相似文献
7.
Ed Brinksma 《Distributed Computing》1999,12(2-3):61-74
Summary. In this paper we present a proof of the sequential consistency of the lazy caching protocol of Afek, Brown, and Merritt.
The proof will follow a strategy of stepwise refinement, developing the distributed caching memory in five transformation steps from a specification of the serial memory, whilst
preserving the sequential consistency in each step. The proof, in fact, presents a rationalized design of the distributed
caching memory. We will carry out our proof using a simple process-algebraic formalism for the specification of the various
design stages. We will not follow a strictly algebraic exposition, however. At some points the correctness will be shown using
direct semantic arguments, and we will also employ higher-order constructs like action transducers to relate behaviours. The distribution of the design/proof over five transformation steps provides a good insight into the
variations that could have been allowed at each point of the design while still maintaining sequential consistency. The design/proof
in fact establishes the correctness of a whole family of related memory architectures. The factorization in smaller steps
also allows for a closer analysis of the fairness assumptions about the distributed memory. 相似文献
8.
Summary. The purpose of compact routing is to provide a labeling of the nodes of a network and a way to encode the routing tables, so that routing can be performed
efficiently (e.g., on shortest paths) whilst keeping the memory-space required to store the routing tables as small as possible.
In this paper, we answer a long-standing conjecture by showing that compact routing may also assist in the performance of
distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows broadcasting with a message-complexity of O(n), where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving the
previous known bound of O(m+n). A general consequence of our result is that a shortest path interval routing scheme contains ample structural information to avoid developing ad-hoc or network-specific solutions for basic problems that distributed systems must handle repeatedly.
Received: December 2000 / Accepted: July 2001 相似文献
9.
Summary. We prove the existence of a “universal” synchronous self-stabilizing protocol, that is, a protocol that allows a distributed
system to stabilize to a desired nonreactive behaviour (as long as a protocol stabilizing to that behaviour exists). Previous
proposals required drastic increases in asymmetry and knowledge to work, whereas our protocol does not use any additional
knowledge, and does not require more symmetry-breaking conditions than available; thus, it is also stabilizing with respect
to dynamic changes in the topology. We prove an optimal quiescence time n+D for a synchronous network of n processors and diameter D; the protocol can be made finite state with a negligible loss in quiescence time. Moreover, an optimal D+1 protocol is given for the case of unique identifiers. As a consequence, we provide an effective proof technique that allows
to show whether self-stabilization to a certain behaviour is possible under a wide range of models.
Received: January 1999 / Accepted: July 2001 相似文献
10.
Summary. Hot-potato routing is a form of synchronous routing which makes no use of buffers at intermediate nodes. Packets must move
at every time step, until they reach their destination. If contention prevents a packet from taking its preferred outgoing
edge, it is deflected on a different edge. Two simple design principles for hot potato routing algorithms are minimum advance, that advances at least one packet towards its destination from every nonempty node (and possibly deflects all other packets),
and maximum advance, that advances the maximum possible number of packets.
Livelock is a situation in which packets keep moving indefinitely in the network without any packet ever reaching its destination.
It is known that even maximum advance algorithms might livelock on some networks. We show that minimum advance algorithms
never livelock on tree networks, and that maximum advance algorithms never livelock on triangulated networks.
Received: March 1999 / Accepted: August 1999 相似文献
11.
An ad hoc network is a multi-hop wireless network of mobile nodes without fixed infrastructure. Its limited bandwidth and frequently changing topology require that its protocol should be robust, simple and energy conserving. In this paper, we propose a new ad hoc multicast protocol based on Passive Data Acknowledgement (PDAODMRP). PDAODMRP has the following contributions: (1) it knows the status of its downstream forwarding nodes by route information collected from data packets instead of BEACON signal of MAC layer, and reduces the waste of wireless bandwidth created by the BEACON signal; (2) it adopts a new route information collection from data packets to reduce the CPU usage of data route information collection; and (3) it adopts a dynamic local route maintenance to enforce its local route maintenance. From simulation results, it can be seen that PDAODMRP has low control overhead and low data delivery delay. 相似文献
12.
Bogdan S. Chlebus Leszek Gasieniec Alan Gibbons Andrzej Pelc Wojciech Rytter 《Distributed Computing》2002,15(1):27-38
We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network
is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of
the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such
networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario.
For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is
optimal, and an algorithm for arbitrary n-node graphs, working in time . Next we show that broadcasting with acknowledgement is not possible in this model at all.
For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting
in strongly connected graphs.
Received: January 2000 / Accepted: June 2001 相似文献
13.
ScholOnto: an ontology-based digital library server for research documents and discourse 总被引:8,自引:0,他引:8
Simon Buckingham Shum Enrico Motta John Domingue 《International Journal on Digital Libraries》2000,3(3):237-248
The internet is rapidly becoming the first place for researchers to publish documents, but at present they receive little
support in searching, tracking, analysing or debating concepts in a literature from scholarly perspectives. This paper describes
the design rationale and implementation of ScholOnto, an ontology-based digital library server to support scholarly interpretation and discourse. It enables researchers to describe
and debate via a semantic network the contributions a document makes, and its relationship to the literature. The paper discusses
the computational services that an ontology-based server supports, alternative user interfaces to support interaction with
a large semantic network, usability issues associated with knowledge formalisation, new work practices that could emerge,
and related work.
Published online: 22 September 2000 相似文献
14.
Pierre Fraigniaud Andrzej Pelc David Peleg Stéphane Pérennes 《Distributed Computing》2001,14(3):163-183
We consider the task of assigning distinct labels to nodes of an unknown anonymous network in a distributed manner. A priori, nodes do not have any identities, except for one distinguished node, called the source, and do not know the topology or
the size of the network. They execute identical algorithms, apart from the source which plays the role of a leader and starts
the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length
of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities
of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present
label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On
the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.
Received: July 2000 / Accepted: February 2001 相似文献
15.
16.
We present efficient schemes for scheduling the delivery of variable-bit-rate MPEG-compressed video with stringent quality-of-service
(QoS) requirements. Video scheduling is being used to improve bandwidth allocation at a video server that uses statistical
multiplexing to aggregate video streams prior to transporting them over a network. A video stream is modeled using a traffic
envelope that provides a deterministic time-varying bound on the bit rate. Because of the periodicity in which frame types
in an MPEG stream are typically generated, a simple traffic envelope can be constructed using only five parameters. Using
the traffic-envelope model, we show that video sources can be statistically multiplexed with an effective bandwidth that is often less than the source peak rate. Bandwidth gain is achieved without sacrificing the stringency of the requested
QoS. The effective bandwidth depends on the arrangement of the multiplexed streams, which is a measure of the lag between the GOP periods of various streams. For homogeneous streams,
we give an optimal scheduling scheme for video sources at a video-on-demand server that results in the minimum effective bandwidth.
For heterogeneous sources, a sub-optimal scheduling scheme is given, which achieves acceptable bandwidth gain. Numerical examples
based on traces of MPEG-coded movies are used to demonstrate the effectiveness of our schemes. 相似文献
17.
Location is one of the most important elements of context in ubiquitous computing. In this paper we describe a location model, a spatial-aware communication model and an implementation of the models that exploit location for processing and communicating context. The location model presented describes a location
tree, which contains human-readable semantic and geometric information about an organisation and a structure to describe the
current location of an object or a context. The proposed system is dedicated to work not only on more powerful devices like
handhelds, but also on small computer systems that are embedded into everyday artefact (making them a digital artefact). Model and design decisions were made on the basis of experiences from three prototype setups with several applications,
which we built from 1998 to 2002. While running these prototypes we collected experiences from designers, implementers and users and formulated them as guidelines in this paper. All the prototype applications heavily use location information for providing their functionality. We found
that location is not only of use as information for the application but also important for communicating context. In this
paper we introduce the concept of spatial-aware communication where data is communicated based on the relative location of
digital artefacts rather than on their identity.
Correspondence to: Michael Biegl, Telecooperation Office (TecO), University of Karlsruhe, Vincenz-Prieβritz-Str. 1 D-76131 Karlsruhe, Germany.
Email: michael@teco.edu 相似文献
18.
An adaptive protocol for synchronizing media streams 总被引:8,自引:0,他引:8
Stream synchronization is widely regarded as a fundamental problem in the field of multimedia systems. Solutions to this
problem can be divided into adaptive and rigid mechanisms. While rigid mechanisms are based on worst case assumptions, adaptive
ones monitor the underlying network and are able to adapt themselves to changing network conditions. In this paper, we will
present an adaptive stream synchronization protocol. This protocol supports any kind of distribution of the sources and
sinks of the streams to be synchronized. It is based on a buffer-level control mechanism, allowing immediate corrections
when the danger of a buffer overflow or underflow is recognized. Moreover, the proposed protocol is flexible enough to support
a wide variety of synchronization policies, which can be dynamically changed while synchronization is in progress. Finally,
the message overhead of this protocol is low, because control messages are only exchanged when network conditions change. 相似文献
19.
A network that offers deterministic, i.e., worst case, quality-of-service guarantees to variable-bit-rate (VBR) video must
provide a resource reservation mechanism that allocates bandwidth, buffer space, and other resources for each video stream.
Such a resource reservation scheme must be carefully designed, otherwise network resources are wasted. A key component for
the design of a resource reservation scheme is the traffic characterization method that specifies the traffic arrivals on a video stream. The traffic characterization should accurately describe the
actual arrivals, so that a large number of streams can be supported; but it must also map directly into efficient traffic-policing
mechanisms that monitor arrivals on each stream. In this study, we present a fast and accurate traffic characterization method
for stored VBR video in networks with a deterministic service. We use this approximation to obtain a traffic characterization
that can be efficiently policed by a small number of leaky buckets. We present a case study where we apply our characterization
method to networks that employ a dynamic resource reservation scheme with renegotiation. We use traces from a set of 25–30-min
MPEG sequences to evaluate our method against other characterization schemes from the literature. 相似文献
20.
In Mobile Ad Hoc Networks (MANETs), nodes depend upon each other for routing and forwarding packets. However, nodes belonging to independent authorities in MANETs may behave selfishly and may not forward packets to save battery and other resources. To stimulate cooperation, nodes are rewarded for their forwarding service. Since nodes spend different cost to forward packets, it is desirable to reimburse nodes according to their cost so that nodes get incentive while the least total payment is charged to the sender. However, to maximize their utility, nodes may tell lie about their cost. This poses the requirement of truthful protocols, which maximizes the utility of nodes only when they declare their true cost. Anderegg and Eidenbenz recently proposed a truthful routing protocol, named ad hoc-VCG. This protocol incurs the route discovery overhead of O(n3), where n is the number of nodes in the network. This routing overhead is likely to become prohibitively large as the network size grows. Moreover, it leads to low network performance due to congestion and interference. We present a low-overhead truthful routing protocol for route discovery in MANETs with selfish nodes by applying mechanism design. The protocol, named LOTTO (Low Overhead Truthful rouTing prOtocol), finds a least cost path for data forwarding with a lower routing overhead of O(n2). We conduct an extensive simulation study to evaluate the performance of our protocol and compare it with ad hoc-VCG. Simulation results show that our protocol provides a much higher packet delivery ratio, generates much lower overhead and has much lower end-to-end delay. 相似文献