Utility and Quality-of-Service Models for
the Dissemination of WWW Resources
Dept. of Computer Science
University of Cyprus
PO Box 537, 1678 Nicosia
Dept. of Computer Science
In this paper we introduce a mathematical formulation to
address the problem of Web-content selection in the context
of emerging services that disseminate WWW resources.
In these services, a content-distributor selects and multicasts periodically
Web-content to a number of subscribed clients. Typically, content-distributors
are satellite operators and subscribers are
operators of wide-area WWW-caching schemes.
The basic premise behind these services is
that the disseminated content covers adequately the interests
of subscribers, improves the hit-ratio of installed Web-caches
and, therefore, relieves overloaded terrestrial TCP/IP connections.
The soundness of this premise and the overall
feasibility of the proposed approach, however, depend on a number
of issues, such as:
These issues should be
taken into consideration by
a content-distributor in its selection of Web-content for dissemination,
as well as in its negotiation with potential clients
about the pricing of the service.
The design of content-selection algorithms: such
algorithms should take into account client utility and distributor
The ``profiles'' of potential subscribers, which represent their
information interests, the size of their customer-base, the level
and cost of their terrestrial Internet-connectivity,
The way clients perceive and formalize the utility
they expect to receive with the adoption of the Web-dissemination
The charging schemes proposed by
content-distributors and the negotiation framework that can
be established between distributors and clients to reach flexible and mutually
profitable pricing mechanisms.
To address these issues, we propose
a theoretical modeling of Web-content dissemination that
takes into account subscriber-interests (profiles). In particular,
we introduce two metrics that measure the similarity between the disseminated
content and subscriber profiles: resemblance and coverage.
Furthermore, we define two alternative charging schemes: Usage-
and Subscription-based pricing.
We show that the similarity metrics introduced can be used to define
formally the notions of Client Utility and Quality of Service
(QoS). Consequently, we employ these metrics to model mathematically Client
Utility and QoS for the two pricing schemes in question.
Based on our modeling, we propose a framework
within which the distributor and its
subscribers can define and negotiate
the Web-content-dissemination service. This framework entails three
We use this negotiation framework to compare theoretically the two alternative
pricing schemes considered and prove that Subscription-based pricing is
preferrable over Usage-based pricing for the content-distributor.
The definition of the service provided, which is modeled by the disseminated
The formal definitions of the QoS.
The price tag paid by a particular client for a given service and service-quality.
Finally, according to our modeling framework, we
formalize the selection of Web-content for dissemination
as a combinatorial optimization problem. We prove that
this problem is NP-complete and develop an approximation algorithm
to resolve it. We implement the algorithm and run experiments,
which corroborate the soundness of the proposed negotiation framework.