Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
CA 02300453 2000-03-10
Strate~v for Neeotiation of Telecommunication Resources
The present invention relates generally to telecommunications, and more
specifically, to a
method and system of negotiating desired resources over telecommunication
networks offering a
variety of services and/or levels of service.
Background of the Invention
Conventionally, telecommunication networks were comprised of single Service
Providers
making a single service available to Users. However, telecommunication
networks have evolved
greatly over the last two decades, and continue to evolve, so that there are
currently multiple
providers offering multiple services on multiple levels. For example, the data
transmission
methods and protocols now employed include Internet Protocol (IP),
asynchronous transfer mode
(ATM), frame relay, and digital telephony. Similarly, in the long distance
voice telephone market .,
there is a large number of Service Providers who use various transmission
means including analog,
digital and digital compression methods, over wired, wireless, fiber opticand
satellite transmission
facilities. The networks of these Service Providers are typically
interconnected with those of others
to form larger, heterogeneous networks.
Determining the optimal means of communicating between two points over such
telecommunication networks is a complex task, requiring consideration of the
price, quality and
availability of services, in view of the requirements of the communication
desired and the generally
conflicting interests (cost vs. price, network capacity vs. service levels,
etc.)of the parties involved.
While attempts have been made to provide systems to manage these complexities,
the proposed
solutions are inefficient and have shortcomings that limit their
effectiveness.
In general, existing telecommunications systems offer a small number of
finite, non-
negotiable services, though they may allow users to select which of these
finite services they
desire. The Public Switched Telephone Network (PSTN), for example, offers a
finite set of
services which are controlled using a limited set of SS7 messages. Customers
can subscribe to
services over a predetermined time period, or request special services either
through interaction
with a telephone operator or mechanically by use of Interactive Voice Response
(IVR) systems.
Either way, the number of options available to the customer is very limited.
Further, a customer
generally can only select services directly from the Service Provider of the
first link that they
connect with, services on downstream links provided by other Service Providers
are negotiated by
the first link Service Provider.
Similarly, while the Internet provides an efficient network for transporting
data packets, it is
CA 02300453 2000-03-10
-2-
not designed to provide end to end services with guaranteed performance
levels. Typically, there is
a static selection of services available to users, under predetermined terms
and conditions. The
performance level that a user may require is offered on a "best effort" basis
and is not firmly
guaranteed. As well, users communicating over the Internet must use protocols
that are understood
and supported by all the participants.
Voice and computer data were once carried on separate networks, although both
are now
generally transmitted digitally over the same networks. Because the
requirements for voice and
data transmission are so different, it is difficult to optimize the provision
of both on a common
network. Voice communication, for example, produces a steady stream of data at
a fairly low rate,
and rapid delivery is more important than accuracy. In contrast, data
applications such as Web
browsing generally produce bursts of data that are to be delivered accurately,
and for which a delay
of a second or two may be considered acceptable.
Other services may have different requirements for accuracy, delay and data
rate, which
characterize the Quality of Service (QoS) in a communication session. Ideally,
a
telecommunication Service Provider should provide a service which optimizes
communication for
a User's particular application and simultaneously optimizes the provision of
that service over his
own network along with services he is providing to other Users. Using
traditional techniques, this
would require the Service Provider to proactively offer a different Quality of
Service for each new
voice or data application that is developed.
Because Service Providers have limited knowledge of what applications their
Users may be
implementing, it is difficult for them to offer products which are tailored to
those applications. It is
also clearly impossible for Service Providers to anticipate the requirements
of applications that
have yet to be developed. Similarly, Service Providers are not generally aware
of the computing
power that a given User has, in terms of processing speed, memory capacity,
software and operator
expertise. Therefore, Service Providers generally provide products that serve
the most common
market, and possibly one or two major niche markets. Currently, Users must
search for the Service
Provider that offers products best suited to their needs, if one does exist.
Users that have multiple
needs may have to enlist the services of a number of Service Providers.
A conventional telephony network provides a fixed quality of voice service,
called toll
quality, at a pre-arranged price. Long-distance re-sellers may use digital
voice compression to
offer lower-cost long distance service at a reduced price, but again, this
service offers a fixed
quality at a pre-arranged price. Because competitors offer different voice
quality, pricing and
probability of call success, End Users can choose a Service Provider with a
good reputation for
CA 02300453 2000-03-10
-3-
providing service, even when such a provider may charge a greater price than
others, or End Users
can choose a lower priced Service Provider, knowing that service levels may be
less than optimal.
This method becomes cumbersome when new services appear and the end user must
select a
Service Provider for each of his applications and track their performance or
check their reputations
by word of mouth.
The existing systems do not allow provision of diverse services with specific
performance
requirements. For example, remote surgery in which a physician uses a remote
manipulator to
perform surgery, could not be implemented with existing systems. This
application would require
very strict demands on both accuracy and timeliness together with a data rate
sufficient for video.
The consequences of the network failing to perform as required would be very
serious.
Another example is Internet gaming, in which a number of players exchange
small packets
of information to update each other on their moves. Given how such games are
typically
implemented, this application calls for low latencies, but data rate
requirements are light and a
fairly high rate of packet loss can be b~lerated as such game applications are
generally designed to
tolerate these packet losses.
Hence, a demand exists for systems and methodologies which allow users to
tailor
communication parameters to accommodate their specific needs. While attempts
have been made
to provide such systems, the present inventors are unaware of any that have
been effective.
A number of existing systems are surveyed in the article, "Connection
Establishment in
High-Speed Networks", by Scott Jordan and Hong Jiang, IEEE Journal on Selected
Areas in
Communications, vol. 13, no. 7, September 1995 and the contents of this
article are incorporated
herein by reference. The models discussed in the article describe a large
number of parameters that
must be resolved between the participants, including: cell loss probability,
delay fitter, end-to-end
delay, average throughput, peak bandwidth, pricing, network congestion and
degradation, and
incentives to ease load management on the network. But the processes discussed
by Jordan et al.
require all parties to agree on values for all parameters of the communication
in a single stage. The
present inventors have determined that, as the number of participants and
complexity of their
requirements grow, the likelihood of complete agreement diminishes, and no
mechanism to resolve
disagreement is presented by Jordan et al. Further, if the parties fail to
come to terms, it is very
difficult to determine why an agreement could not be reached.
Jordan et al. describe several "two stage" methodologies which include: a
first stage in
which "the user agent characterizes the information streams that will be
transmitted"; followed by a
second stage in which the network offers a rate schedule from which the
calling party selects their
CA 02300453 2000-03-10
-4-
preference.
While these processes appear to be an advance over previous systems, they are
best
described as offer-acceptance models. The user remains at the mercy of the
service provider who
may continue to offer only services that optimize his own resources, as
telecommunication
providers have done in the past. Further, these systems have no incentive for
the service provider
to offer the differentiation of services that today's applications require. As
well, the first stage
described by Jordan et al. is in essence an initialization stage and the offer
and acceptance takes
place in the next stage, so all of their methods are essentially single stage
agreements.
On page 1155 of the Jordan et al. article, a reference is made to a
"distributed iterative
negotiation process" described in , "A New Approach To Service Provisioning In
ATM Networks",
by S. H. Low and P. P. Varaiya, IEEE Transactions on Networking, Vol. l, p.p.
547-553, 1993.
However, Low et al. simply describes an offer- acceptance model. Further, by
"iterative", Low
simply means that the network updates its rates periodically, and re-
negotiates with the users while
their communications are active.
The article, "Connection Establishment Protocol Based on Mutual Selection by
Users and
Network Providers", Nagao Ogino, ACM, 1998, presents a similar methodology in
which a number
of service providers bid on the provision of communication services defined by
the user. This
methodology requires that all parameters be specified and addressed in a
single stage and is merely
a bid-award system.
No instruction is provided in Jordan et al. or Ogino as to how these methods
may be applied
to a general case. For example, how are the logistical difficulties of
establishing a video
conference between six parties to be addressed? This would require at least
six simultaneous and
interactive negotiations between the respective parties and their service
providers, as well as
interconnections between these service providers. Each of these negotiations
would have to
resolve a large number of parameters, possibly including: latency; average
bandwidth; peak
bandwidth; pricing; cost sharing requirements; encryption and video
compression format. With so
many parameters (degrees of freedom), it would be very difficult to find terms
that all parties
would agree to, and such conditions may not exist at all. Therefore, in order
to be effective, some
means of assuring convergence and to address disagreements is required.
There is therefore a need for a method and system of negotiating resources
over
telecommunication networks offering a variety of services. This method and
system must be
provided with consideration for the problems outlined above.
CA 02300453 2000-03-10
-S-
Summary of the Invention
It is therefore an object of the invention to provide a novel method and
system of
negotiating resources over telecommunication networks offering a variety of
services which
obviates or mitigates at least one of the disadvantages of the prior art.
According to one aspect of the present invention, there is provided a method
of establishing
communication between at least two entities, where the characteristics of said
communication are
defined by a set of parameters, said method comprising the steps of:
(i) arranging said set of parameters into a hierarchy of at least two stages
wifi ones of said
parameters in one of said at least two stages;
(ii) negotiating, for each stage in turn, values for said parameters in said
stage with each of
said at least two entities to produce a set of agreed parameter values for
each said stage; and
(iii) responding to agreement at all stages by establishing said communication
between said
at least two entities according to said agreed values for said parameters.
According to another aspect of the present invention, there is provided a
telecommunications system comprising:
a First User Interface;
a Second User Interface;
a telecommunications network operable to interconnect said First User
Interface with said
Second User Interface;
each of said First User Interface, Second User Interface and said
telecommunications
network having an Agent to represent its respective interests in negotiating a
communication
between said First User Interface and said Second User Interface and each said
Agent being
operable to agree on values with each other Agent for a set of parameters
arranged in a hierarchy of
stages to define a desired communication between said First User Interface and
said Second User
Interface.
According to yet another aspect of the present invention, there is provided a
telecommunication method for negotiation between participants to establish a
desired
communication through a telecommunication network, the communication defined
by a set of
parameters arranged in a hierarchy of stages, the method comprising the steps
of, from the highest
stage to the lowest stage in turn:
(i) negotiating and agreeing values with said participants for the parameters
of a stage under
consideration;
(ii) if values for one or more parameters in said stage under consideration
cannot be agreed,
CA 02300453 2000-03-10
-6-
terminating said negotiation and notifying said participants accordingly;
(iii) if values for parameters in the stage of step (i) are agreed, performing
steps (i), (ii) and
(iii) for each succeeding stage in said hierarchy;
(iv) when values for all parameters in all stages have been agreed, said
participants
establishing said desired communication.
In the event that negotiations fail at a stage, a participant can change the
value of a
parameter in a previously agreed stage and can restart the negotiation at that
stage in an attempt to
resolve the failure.
Further, participants can compete to establish the desired communication and
this
competition can occur at each stage. Participants who fail in the negotiations
at a stage are
removed from subsequent negotiations at subsequent stages.
Various negotiating disciplines can be employed to negotiate the stages,
including a Round
Robin negotiating discipline or others as will occur to those of skill in the
art.
Brief Description of the Drawings
Embodiments of the present invention will now be described, by way of example
only, with
reference to the attached Figures, wherein:
Figure 1 shows a flow chart of a method in accordance with an embodiment of
the
invention;
Figure 2 shows a block diagram of the entities of a telecommunications system
in
accordance with an embodiment of the invention;
Figure 3 shows a schematic diagram of the interactions of the entities
involved in the
telecommunications system of Figure 2 ;
Figure 4 shows a flow chart of the generic method used by the Negotiation
Manager shown
in Figure 3;
Figure 5 shows a flow chart of a method used by the Telecommunication
Network's Agent
shown in Figure 2; and
Figure 6 shows a flow chart of a method used by the First User's Agent shown
in Figure 2;
Figure 7 shows a flow chart of the staged negotiation method in accordance
with an
embodiment of the present invention; and
Figure 8 shows a flowchart of the restarting of a negotiation after the
unsuccessful
termination of a negotiation.
CA 02300453 2000-03-10
Description of the Invention
A simplified view of a methodology in accordance with an aspect of the present
invention is
shown in Figure 1. This Figure presents a method of establishing communication
between a first
entity and a second entity, where the communication is defined by a set of
parameters. As will be
discussed in more detail below, negotiation between the first entity and the
second entity occurs in
stages, each stage having a subset of the set of parameters to be negotiated.
The process
commences with the first stage wherein values for one or more parameters are
negotiated between
the entities at step 2. A determination is made at step 4 as to whether values
for all parameters
being negotiated in that stage have been agreed to by the entities. If the
values have not been
agreed, the negotiation in step 2 repeats. If values have been agreed for all
parameters of a stage, a
determination is made at step 6 as to whether any more stages exist to be
negotiated. If one or
more stages do exist to still be negotiated, at step 8 the next stage is
selected and the negotiation of
step 2 is performed for the parameters of that stage. If at step 6 it is
determined that no more stages
exist to be negotiated, the process proceeds to step 9 where the desired
communication is
established and the process completes. As described in more detail below,
various mechanisms can
be employed if the negotiation process of step 2 does not result in a
convergence between the
entities of the values for the parameters of a stage.
The phrase "participant" is used herein to describe hardware or software that
represents any
party having an interest in the parameters for the communication. Such parties
can include end
users, their service provider or providers, and interconnecting communication
providers. End users
will have terminal devices which allow the user to send and receive audio,
video, data or other
similar information, and such terminal devices can be a telecommunication
interface such as a
telephone, personal computer, personal digital assistant, cellular telephone,
pager, fax machine or
other devices as will occur to those of skill in the art. Service providers
can communicate with the
end users via dial-up, cable or wireless modems, or using technologies such as
ISDN (integrated
services digital network), ADSL (asynchronous digital subscriber line), ATM
(asynchronous
transfer mode) or frame relay, for example. These devices and systems are
secondary to the
invention and other suitable means for Service Providers to communicate with
end users within the
scope of the present invention will occur to those of skill in the art.
The parameters that define the communication will depend on the nature of the
communication that is desired. In the simple case of a voice call, the
parameters can include: the
price of the call, who pays, and the quality of the call. More complex
communications will include
other parameters, as will be apparent to those of skill in the art, some of
which are identified
CA 02300453 2000-03-10
_g_
hereinafter. Even in a simple case, the present inventors believe the it is
easier and more
advantageous to negotiate values for the set of parameters in multiple and
successive stages. In
more complex cases of course, there may be many stages. The number of stages
and which
parameters are negotiated during which stage, will depend on the priorities
and goals of the
participants. Once the values for the parameters have been agreed to, the
connection can be
executed according to those parameter values.
As explained above, there is a growing demand for diverse services, which
require
telecommunication service providers to allow service parameters to be tailored
to the specific
requirements of the users. Even simple applications can result in very complex
negotiations, which
cannot be handled effectively by the existing methods. For example with
existing methods, when a
very large number of parameters and degrees of freedom need to be considered,
it can require too
long to perform the negotiation, participants may not be pleased with the
outcome, and there is no
guarantee that an agreement will ever be reached.
Hence, the present invention separates negotiation of a communication into
stages, where
values for smaller sets of parameters are negotiated at the different,
successive stages so that
progress towards agreement is logical and steady. This reduces the level of
complexity at each
stage, so that there are fewer tradeoffs and alternatives to be considered
during negotiation, and
analysis of negotiations which failed or which produced undesirable results,
are easier to perform.
The use of multiple stages allows communications to be managed, organized to
be efficient
and to terminate negotiations with a successful result. The logical division
of the parameters to be
negotiated in a stage makes the resolution of the communication much more
straightforward and
increase the likelihood of success. Further, it will take less time to find
the values for the
parameters that all participants will agree to, without wasting time at a
lower (more specific
parameters) level if agreement is not going to be reached at a higher
(general, or non-negotiable,
parameters) level.
The invention provides for the "categorization of concerns", in that some
terms can be more
important to overall success ("deal breakers") and/or some terms are depaldent
upon others. It
does not make sense to negotiate less important terms if one or more deal
breaker terms cannot be
agreed. For example, an application may require a guaranteed minimum data rate
and, if such a
rate cannot be agreed, then there is no sense in attempting to negotiating
cost. Similarly, it does not
make sense to negotiate a term whose relevance or meaning depends from another
term before that
other term has been agreed. For example, the cost that a calling party is
willing to accept will
depend upon the type of call to be established. So, the parameters whose
values are to be
CA 02300453 2000-03-10
-9-
negotiated are arranged in a multilevel hierarchy, each level being negotiated
as a stage.
The invention also provides another feature that Internet Service Providers
(ISPs) can use to
sell their services. Users who are accustomed to the high reliability of
existing PSTNs could be
hesitant to use the Internet for all of their communications unless there is a
way of offering similar
convenience and reliability. The invention enables such an application. As
noted above, it is
preferred that automated software agents represent the participants in the
negotiation and
configuration of a software agent to mimic a traditional PSTN telephone can be
accomplished
easily.
Finally, preferably, the present invention is implemented as an open system,
where third
parties are able to contribute to the body of related software. In such a
system, the use of the
multiple stages makes it easier to write new negotiation strategies and other
software utilities.
The present invention can include additional features which offer even greater
improvements in effectiveness over previous methods. As noted above,
negotiations may rise
exponentially in complexity with the numbers of parameters and participants.
The invention
manages this complexity by breaking the negotiation down into smaller stages
which can be easily
monitored. The method of the invention can assist in obtaining convergence
because the
negotiation can now be described in manageable terms and status information
fed back to the
participants. In the simple case, the invention can advise all participants
of:
(i) which parameters are to be negotiated in which stage;
(ii) which values have been agreed to; and
(iii) the status of the present stage of negotiation.
In a present embodiment, the communication proposals pass through the trusted
domain of
a Negotiation Manager, described below, so that the progress of the
negotiation can be monitored
with confidence, and convergence to a negotiated agreement is encouraged. A
proposal comprises
a set of values for the set of parameters in a stage, the set of values being
those that a participant
can, or is willing to, accept. The invention allows participants to know what
parameters have been
resolved so far so that the participant can decide how to proceed.
As an example, an agent may repeatedly reject a communication, which is being
negotiated,
because the proposal includes a certain compression algorithm for which the
participant doesnot
have the necessary software. When a participant receives the feedback
information identifying
why the negotiation failed, the participant can obtain the necessary software,
if desired, to allow
future communications requiring the compression algorithm to proceed. Without
the feedback
provided by the invention, the participants often would never have known why
the communication
CA 02300453 2000-03-10
- 10-
was not established.
As well, participants can be advised as to what the contentious
parameters/issues are on a
per stage basis. For example, rather than report that ten parameters are
unresolved, the present
invention can report that the parameters of stages 1 and 2 have been resolved,
while one parameter
(e.g. total permitted end to end latency) has not been resolved in st~e 3 and
that, because of this,
the remaining parameters defined in stages 4 and 5 have not yet been
considered. Having
participants better informed can expedite agreement and user satisfaction.
An end user may wish to focus on particular parameters and does not want
superfluous
disagreements to cause repeated failures. The present invention allows the
user to identify certain
parameters as critical (e.g. deal breakers) and others as merely desired, or
"don't care", and the
feedback that the present invention provides makes it easier for participants
to identify why a
certain communication cannot be resolved and to attempt to correct the
problem.
If the participants in a negotiation fail to reach an agreement, they
generally wish to
determine why, so that the problem can be overcome for the present situation
and avoided in the
future. Such 'forensic analysis' is simplified by breaking the negotiation
down into stag.
Specifically, the Negotiation Manager can return audits to the participants
identifying the
parameter values that were modified, and by whom, in each stage.
In an ideal case, a failure to reach an agreement in one stage can be examined
to determine
the cause of failure so that remedial action can be taken to permit the
communication to be
successfully completed. This remedial action can consist of reinitiating a
preceding stage of the
negotiation with an adjusted set of parameter values, selected in view of the
determined cause, and
which will allow convergence to occur at a subsequent stage As an example, a
communication
may be proposed as a video call, for which a 'type of connection' parameter
value is set in stage 1,
and for which stage 2 has a dependent 'deal breaker' parameter which is a
minimum data rate of
4Mbits per second. In such a case, stage 1 may be successfully negotiated with
the parties
agreeing to the video call, but in stage 2 agreement cannot be reached if such
a data rate cannot be
provided by a participant. With forensic knowledge of the failure at stage 2,
stage 1 can be re-
initiated with the value for the type of connection parameter downgraded to a
degraded type of
video call (slow scan video for example or one employing a high ratio data
compression system),
allowing a data rate of less than 4Mbits per second to be accepted in stage 2.
For such forensic analysis, there are three main situations of interest:
(i) where the discrepancies between parameter values in proposals are very
large, it is easy
to identify why the negotiation failed. The Negotiation Manager can simply
compare consecutive
CA 02300453 2000-03-10
proposals and advise which parameter values were changed;
(ii) smaller conflicts between proposals of participants are harder to detect.
In an
embodiment of the invention, the Negotiation Manager can monitor the
proposals, 3oring the last n
set of parameter values from each participant and advising the participants if
repetition occurs. If
the proposal has the same state (set of parameter values) at a given point in
its circulation through
the participants that it had for a previous negotiation round, some action
must be taken to address
the problem, or the negotiation will not converge; and
(iii) it is also di~cult to detect the situation wherein sets of parameter
values from
participants are very close and yet the proposals do not converge, but follow
a cyclic pattern that
only returns to the same state after a large number of iterations (i.e.-
proposals follow a pattern of
states such as A-B-C-D-E-A-B-C-D-E, etc.). In such a case, the Negotiation
Manager can simply
end the negotiation after a finite number of iterations, and report to the
participants on the states of
past proposals. Alternatively, the Negotiation Manager can identify the
parameters that were being
disputed or manipulated from stage to stage. Techniques for identifying
patterns, loops and other
anomalies in the proposal history produced by the Negotiation Manager are
known in the art and
will not be further discussed herein.
The preferred negotiation system of the invention is presented as a block
diagram in Figure
2. In this example, telecommunication system 10 consists of a First User
Interface 12 and a Second
User Interface 14, interconnected by a telecommunications network 16. The
First User Interface
12 and Second User Interface 14 can be, for example, telephones, cellular
telephones, personal
digital assistants, personal computers or servers which produce and/or consume
data. The
telecommunications network 16 has at least one transmission means and
protocol, which will be
described in detail hereinafter.
First User Interface 12 will have a First User Agent 18 which represents the
interests of the
First User Interface 12 in negotiating a communication between itself and the
Second User
Interface 14. Similarly, Second User Interface 14 has a Second User Agent 19,
which represents
the interests of the Second User in negotiating the communication and the
telecommunications
network 16 has a telecommunications network agent 20 which represents the
interests of the
telecommunications network 16 in negotiating the communication.
The negotiation of the terms of communication is administered by a software
agent called
the Negotiation Manager 22. Negotiation Manager 22 can reside anywhere in the
system 10,
though in a simple implementation, it will reside somewhere in the
telecommunications network 16
which is the First User's Service Provider.
CA 02300453 2000-03-10
- 12-
Preferably, the Negotiation Manager 22 is operable to:
1. identify participating agents in a negotiation;
2. implement a negotiation discipline which allows each participating agent to
consider a
proposal and either accept the proposal or amend the values of one or more
parameters of
the proposal, and do so in a trusted environment;
3. respond to the negotiation being successful in a stage by proceeding to
next stage or by
executing the proposal to provide the communication if all stages have been
successfully
negotiated;
4. identify loops, cycles and other anomalies in the proposal history;
5. determine whether the negotiation will converge;
6. return audits to the participants identifying the values of parameters that
were modified, and
by whom, from stage to stage;
7. detect whether a participant has violated the rules of the negotiation;
8. ensure termination within a limited number of rounds if convergence has not
yet occurred;
and
9. provide forensic information to participants if the negotiation terminates
without
convergence.
Broadly speaking, system 10 provides a flexible telecommunications system for
resolving
contention for network resources. System 10 is flexible in that new services
and features
developed by outside parties can be implemented in the negotiation. In current
telecommunication
systems, all services are provided and controlled by the telecommunication
system providers,
which limits the services available and impedes the provision of new services.
In system 10, an
End User, Negotiation Manager or other Network Entity with an interest in the
negotiation, can
obtain new negotiating disciplines or software agents developed by themselves
or outside parties
and implement them in the negotiation. Further, an End User of a Service
Provider can define a set
of parameters for a new service, feature or application in a timely and
efficient manner. Details of
such options will be described in greater detail herein after.
System 10 of the invention permits multiple participants to negotiate the
terms of a given
communication. The requirement for this functionality is clear, as a
communication may have to
pass through two, three or more telecommunication providers in traversing a
broad geographical
area. It is in the best interest of all the Network Entities involved in the
communication to also
participate in the negotiation.
CA 02300453 2000-03-10
-13-
This generalization also allows communications which have multiple End Users,
such as
conference calls, to be negotiated with all of the End Users and their
associated Service Providers
participating.
System 10 of the invention encourages Service Providers to offer a greater
variety and
flexibility in their services, by improving the efficiency of their networks
accordingly. In turn, this
increased variety and flexibility allows the End User to negotiate the
services that he wants, rather
than being forced to choose between limited services from the Service Provider
to which he
subscribes, or having to seek out a new Service Provider that offers the
services he requires.
System 10 resolves contention between End Users by making a variety of data,
voice and
other telecommunication services available that are suited to varying
applications. System 10 also
provides incentives, such as reduced prices and improved overall network
capacity utilization,
encouraging use of available resources rather than insisting on the highest
quality. By making the .,
provision of those services open to real time negotiation, the partidpants are
able to reach a
mutually agreeable result which might have been impossible to otherwise
achieve.
As described above, the invention allows these improvements by providing a
system
wherein each interested party can have a software agent which negotiates on
his behalf. As a
minor issue, this requires that a convention for negotiation be established
that all the software
agents can understand, though the particular nature and parameters of such a
convention does not
limit the invention. In the event that a user interface is not sophisticated
enough to directly support
an agent, an agent can be created for that user interface, as needed, at
another location in system
10. For example, if in Figure 2 second user interface 14 is a conventional
telephone, second user
agent 19 can be implemented by network 16 or negotiation manager 22 and can
utilize a fixed set
of requirements and capacities which have been predetermined for conventional
telephones.
Figure 3 shows the interactions between the participants and the Negotiation
Manager in the
present invention. In the Figure, each interested party in the negotiation is
shown as a participant
24. In a simple implementation as described with respect to Figure 2 above,
participants 24 will
include the First User's Agent 18, Second User's Agent 19 and the
Telecommunication Network's
Agent 20. While Second User's Agent 19 is not required for conventional models
of a voice
telecommunication where the originating caller assumes the cost of the
service, Second User's
Agent 19 will allow the Second User to assume all or part of the cost of the
telecommunication in
other cases. More importantly, it would allow the communication to be
negotiated with
consideration for the interests of the Second User Interface 14. For example,
if Second User
Interface 14 does not have the modem speed of the First User Interface 12,
there is not any benefit
CA 02300453 2000-03-10
- 14-
to negotiating a high-speed connection between the First User Interface 12 and
the
Telecommunication Network 16.
Similarly, if the Telecommunication Network 16 consists of a number of ATM,
long
distance or frame relay providers, it may be advantageous to include a
software agent for each
respective telecommunication provider in the negotiation as well. Therefore,
any entity in the
telecommunication system 10 which has an interest in the outcome of the
negotiation, may be a
participant 24 in the negotiation.
The Participants 24 communicate with the Negotiation Manager 22 by passing a
proposal
26 back and forth using agreed default communications protocols. At a minimum,
a proposal 26
includes a definition of the communication sought with a set of parameters for
defining the
communication, the parameters arranged in hierarchical stages, as discussed
above.
In general, a negotiation will consist of a single proposal 26 that each
participant 24 is free
to inspect and modify. Use of a single proposal 26 avoids problems that could
be experienced with
multiple proposals which require additional overheads of coordination and time
stamping.
As well, because proposal 26 is a relatively small data packet, little real
time is lost in
transferring it from one participant 24 to another. The User may also have
some control over the
size of proposal 26 by his choice of negotiating strategy and parameters. The
contents of this
proposal 26 will be detailed herein below.
Negotiation Manager 22 will employ a negotiation discipline 28 according to a
set of
discipline parameters 30. The invention will be described herein below with
respect to a specify
example of a negotiation discipline 28, but the invention is independent of
the actual negotiation
discipline 28 employed.
As noted above, the invention is not limited by the physical location of the
Negotiation
Manager 22. In general, it is desirable that the Negotiation Manager 22 be
trusted by all parties,
and/or reside in a secure location, but even this is not necessary if
participants 24 secure themselves
within their negotiating preferences. For example, a participant 24 could
restrain his set of values
in proposal 26 to be revocable, allowing himself a last-look prior to
commencing execution of a
negotiated proposal 26. Other methods of securing, for example, by use of
cryptographic
signatures or an authentication list, are known in the art.
Because the location of Negotiation Manager 22 is not restricted, it can be
provided by a
network Service Provider, the User himself, or a third party. This flexibility
is one of the benefits
of the invention, in that it makes this an open system. A third party can
create a Negotiation
CA 02300453 2000-03-10
-15-
Manager 22 or a negotiation discipline 28 and make it available to all
interested Users and Network
Entities on the telecommunication system 10.
This openness will allow the system 10 of the invention to mature very quickly
by the
addition of new Negotiation Managers 22 and negotiating disciplines 28 with
new features.
A simple flow chart of the Negotiation Manager 22 operation is presented in
Figure 4. The
Negotiation Manager 22 identifies all of the participants 24 in the
negotiation at step 32,
implements the negotiation discipline 28 at step 34, determines if the
negotiation has been
successful at step 35 and, if the negotiation is successful, executes the
contract that results from the
negotiated values for the set of parameters at step 36. If at step 35
Negotiation Manager 22
determines that the negotiation has been unsuccessful, forensic information is
returned to the
participants at step 37 to enable them to re-initiate the negotiations, if
desired, with a revised setof
parameter values in an attempt to converge the negotiation.
The identification of the participants 24 at step 32 can be performed in a
number of
manners. In a simple implementation with three participants 24, namely the
First User's Agent 18,
Second User's Agent and the Telecommunication Network's Agent 20, the
participants 24 will be
identified in the initial proposal 26 created by the First User's Agent 18
when he initiates his
request for communication with the Second User Interface 14. In such a case,
the initial proposal
26 will identify the First User Interface 12 as the source of proposal 26 and
the calling party, the
Second User Interface 14 as the called party, and the Telecommunication
Network 16 as the
Service Provider.
In the more general case, the initial proposal 26 will still identify the
First User Interface 12
as the source of the proposal 26 and the calling party, and the Second User
Interface 14 as the
called party, but the identification of participants 24 at the
Telecommunication Network 16 level
may be left to the Negotiation Manager 22. Having Negotiation Managers 22
identify Service
Providers from a database will give the Service Providers motivation to
actively seek out
Negotiation Managers 22, because if a Service Provider is not on a Negotiation
Manager's 22
database, he will not be advised of any negotiations by that Negotiation
Manager 22. Methods for
creating, accessing and maintaining such a database of Service Providers are
well known in the art.
Ln the embodiment shown in Figure 3, it is sufficient that the negotiation
discipline 28
consist of a strategy which allows a proposal 26 to be negotiated that is
satisfactory to each
participant 24. In the simple case illustrated in Figure 2, the negotiation
discipline 28 can consist
of the Negotiation Manager 22 transferring the proposal 26 back and forth
between the First User's
Agent 18, Second User's Agent 19 and the Telecommunication Network's Agent 20
without any
CA 02300453 2000-03-10
- 16-
interference or active participation by the Negotiation Manager 22. In such a
case, the First User's
Agent 18 or Second User's Agent 19 can "time out" if a successful contract 26
is not negotiated
within a specific time period, in order to halt the negotiation. Other
negotiation disciplines 28,
such as round robin bidding, or other suitable strategies, can be employed in
circumstances with
more participants or wherein more complex negotiations, such as negotiations
allowing tradeoffs
between cost and service qualities, are appropriate. The present invention is
notparticularly
limited to any particular negotiation discipline and appropriate disciplines
will be apparent to those
of skill in the art.
If the initial proposal 26 prepared by the First User's Agent 18 is acceptable
to the
Telecommunication Network's Agent 20, then the Telecommunication Network Agent
20 can
approve the proposal 26 and return it to Negotiation Manager 22 unmodified
which will then
forward the proposal 26 to the Second User's Agent 19 to be considered.
Details on how the
Telecommunication Network's Agent 20 analyses the proposal 26 and responds
will be described
with respect to Figure 5 herein below.
At step 36, the Negotiation Manager 22 determines whether the proposal 26 has
been
successfully negotiated, and if so, allows the contract defined by the
negotiated proposal 26 to
execute. The successful negotiation of the proposal 26 may be indicated by
setting a flag or bit in
the proposal 26 or by any other suitable means as will occur to those of skill
in the art.
Figure 5 describes the broad operation of Telecommunication Network's Agent 20
in the
form of a flow chart. As indicated above, the purpose of the Telecommunication
Network's Agent
20 is to represent the interests of the Telecommunication Network 16 in
negotiating a
communication between the First User Interface 12 and the Second User
Interface 14. As the
Telecommunication Network 16 has at least one telecommunication means and
protocol at its
disposal, it may want to negotiate to optimize efficient use of its resources.
Operation of the Telecommunication Network's Agent 20 is straightforward. At
step 38,
the Telecommunication Network's Agent 20 receives the proposal 26 from the
Negotiation
Manager 22. On the first iteration of a simple implementation as described
with respect toFigure 2
above, this proposal 26 will contain the information supplied by the First
User's Agent 18 and
described above. The Telecommunication Network's Agent 20 inspects the
contents of this
proposal 26 at step 40, and determines whether it is acceptable or not.
If the terms of the proposal 26 are not acceptable, the Telecommunication
Network's Agent
20 modifies the values of the set of parameters of the proposal 26 to terms it
would find acceptable,
at step 42. The modification of the terms of proposal 26 can include an
outright rejection of the
CA 02300453 2000-03-10
- 17-
communication, for example in the case of the network not having capability to
implement the
communication, or can be an adjustment of one or more parameters to values
better suited (on an
economic basis, or a network utilization basis, etc.) to network 16, The
modified proposal 26 is
returned to the Negotiation Manager 22 at step 44. Negotiation Manager 22 can,
depending upon
the negotiation discipline employed, either return it to the First User's
Agent 18 for consideration
of the new terms or forward it to the Second User's Agent 19 for consideration
before returning it
to First User's Agent 18.
In a simple case where the Telecommunication Network 16 has a very limited set
of
resources, the Telecommunication Network's Agent 20 may comprise a simple
algorithm which
generates new proposal 26 terms by referring to a database of resources and
standard rates.
In a more sophisticated implementation, the Telecommunication Network's Agent
20 may
comprise a rules-based agent that optimizes use of a continuum of resources.
For example, if the
Telecommunication Network 16 has access to ATM (Asynchronous Transfer Mode)
services, it
can offer Constant Bit Rate (CBR) transmission on a complete continuum from 10
Kb/s to 10
Mb/s, with a rate corresponding linearly to the traffic level. In such an
arrangement, the
Telecommunication Network's Agent 20 would have to consider its current
traffic capacity, load,
expected traffic and cost, in determining a counter offer that optimi~s use of
its resources. The
implementation of such resource management methods is within the ability of
one skilled in the art
and is not discussed further herein.
If the terms of proposal 26 are determined to be acceptable at step 40, then
the
Telecommunication Network's Agent 20 accepts the proposal 26 at step 46 and
returns the proposal
26 to the Negotiation Manager 22'at step 44. As noted above, a bit, flag or
other indicator is
included in the returned proposal 26 to advise Negotiation Manager 22 that the
proposal is
acceptable to First User's Agent 18.
Figure 6 is a flowchart illustrating the broad operation of First User's Agent
18 and, as will
be apparent to those of skill in the art, the operation of Second User's Agent
19 is similar. This
flow chart illustrates the operation of the agent in response to a returned
proposal 26, but the
operation of Agent 18 in creating the original proposal is similar and will be
apparent to those of
skill in the art.
In broad terms, the First User's Agent 18 operates in a very similar manner to
that of the
Telecommunication Network's Agent 20. As noted above, the purpose of the First
User's Agent 18
is to represent the interests of the First User Interface 12 in negotiating a
communication between
the First User Interface 12 and the Second User Interface 14. As the
computational and
CA 02300453 2000-03-10
-18-
communication resources and constraints of the First User Interface 12 may
only be known to
itself, it may wish to negotiate a communication means and protocol that makes
best use of its
resources in view of the particular application that it is implementing. For
example, these
resources and constraints can include processing speed, memory capacity and
modem speed which
can result in particular requirements and/or wants in the communication
including minimum and
maximum data rates, latency, frame or bit error rates, etc.
Operation of First User's Agent 18 commences at step 48 when the First User's
Agent 18
receives the modified proposal 26 from the Negotiation Manager 22. In the some
implementations,
the First User's Agent 18 may not have the functionality to initiate a
communication negotiation.
In the case of the First User's Agent 18 not having the functionality to
generate an initial proposal
26, the initial proposal 26 may be generated by another party in response to a
request from First
User Interface 12, or may be generated as a standing order by the
Telecommunication Network's
Agent 20 when the First User Interface 12 logs on to the Telecommunication
Service provided by
the Telecommunication Network 16. Other similar methods for establishing an
initial proposal will
be apparent to those of skill in the art.
The First User's Agent 18 inspects the contents of this proposal 26 at step
50, and
determines whether it is acceptable or not. If the terms of the proposal 26
are not acceptable, the
First User's Agent 18 modifies the values of the set of parameters of proposal
26 to terms it would
find acceptable at step 52, or indicates an outright rejection of proposal 26
and returns proposal 26
to the Negotiation Manager 22 at step 54.
In a simple case the First User's Agent 18 may have a pre-defined set of
limits that the First
User Interface 12 does not wish to exceed. For example, such limits can
include: not accepting
charges for any incoming calls (in which case the proposal can be modified to
include an outright
rejection of such a proposed call), not exceeding the transmission rate of
First User Interface's 12
modem, or not accepting voice communication with less than toll quality. If a
value of a parameter
of an incoming contract 26 exceeds any of these limitations, which can be
identified with a simple
logic test, a modified proposal 26 is generated which changes the parameter
value, or values, so
that they fall within the desired bounds or to reject the proposal. The First
User's Agent 18 can
comprise a simple algorithm which refers to a database of resources and
preferences to prepare
suitable changes to parameter values.
In a more sophisticated implementation, the First User's Agent 18 can comprise
a rules-
based software agent that optimizes use of a continuum of resources, in the
same manner as the
Telecommunication Network's Agent 20 described above. The First User's Agent
18 can, for
CA 02300453 2000-03-10
- 19-
example, negotiate the communication with consideration for the particular
application, and the
computation and communication parameters of the First User Interface 12. These
preferences may
correspond to end-to-end telecommunication parameters such as peak cell rate
(PCR), tolerable cell
delay variation (CVDT), cell transfer delay (CTD), cell loss ratio (CLR) and
peak-to-peak delay
variation (CDV). Such parameters are generally used in ATM to specify the
quality of service
(QoS) that a telecommunication service provides. Clearly, the invention may be
applied with
various ones of these parameters, or different parameters known in the art,
such as mean opinion
score (MOS). Other subject measures are also possible with appropriate
mappings as will be
apparent to those of skill in the art.
If the terms of the proposal 26 are determined to be acceptable at step 50,
then the First
User's Agent 18 indicates its acceptance of the proposal 26 at step 56 and
returns it to the
Negotiation Manager 22 at step 54. As noted above, proposal 26 can have a bit
or a flag set to
indicate that it is acceptable to First User Interface 12. The process repeats
with Second User's
Agent 19 until all parties have agreed to the same set of terms in proposal 26
or until the
negotiation is terminated.
Certain interfaces, such as a conventional telephone, will not have the
internal operability
for a software agent, so they can be assigned a software agent by the
Negotiation Manager.
Similarly, a user with a software agent who is remote from his terminal, may
access his agent
remotely, for example, by entering a calling card number at a pay telephone.
The system is
operable to then seek out the user's negotiation agent, and the user will
obtain, at that telephone, all
of the features and preferences he had subscribedto, presuming they can be
operated on the
telephone, such as call waiting.
Figure 7 presents a more detailed flow chart of the present invention. The
process begins at
step 100 wherein a set of parameters, appropriate to the desired type of
communication, is
determined. This set of parameters is arranged in a hierarchy of stages,
depending upon the
relative importance of the parameters (e.g.- deal breakers, desired parameters
or "don't cares")
and their inter-dependencies, if any. At step 104, an initial set of values
for the parameters is
established and the proposal is transferred to the Negotiation Manager. In
this example, the Agent
for the participant desiring to establish the communication has created the
initial proposal, but it
contemplated that in other circumstances Agents of other participants, such as
the Agent of the
called party or the Agent of one of the participating Service Providers can
prepare the initial
proposal.
CA 02300453 2000-03-10
-20-
Further, in this example the initial set of values for the parameters ilcludes
values for
parameters in all stages. However, it is contemplated that, in other
circumstances, initial values
will only be created for the first stage and initial values for subsequent
stages will be created once
values for the preceding stage have been agreed.
Finally, step 104 also includes the transfer of the initial proposal, with
initial values for at
least one stage, to Negotiation Manager 22 (except in cases where Negotiation
Manager 22 itself
created the initial proposal).
Next, a test is performed at step 106 to determine the next stage, if any,
which needs to be
negotiated and, assuming that one or more such stages exist, at step 110 a
first participant is
selected to receive and consider the proposal. The proposal is transferred to
that participant where
it is considered at step 114 and any parameter values which are unacceptable
to that participant are
modified by the participant and the proposal, with amendments if any, is
returned to the negotiation
manager 22 at step 118.
At step 122, a determination is made as to whether any participants remain who
have not
yet reviewed the proposal. If such participants exist, the process returns to
step 110 where the next
such participant is selected. If at step 122 no such participant exists, the
process proceeds to step
126 where a determination is made as to whether an agreement of the parameter
values of the
present stage has been achieved. If agreement has been reached, the process
returns to step 106
where the next stage, if any, is selected and steps 114 through 126 are
performed again.
If no agreement has been reached at step 126, a determination is made at step
130 as to
whether a negotiation limit has been reached. As mentioned above, a
negotiation limit can be an
absolute time limit, a count of negotiation rounds, recognition of the
occurrence of a cyclic in the
negotiations or any other suitable metric for determining that convergence of
the negotiations of
the present stage will not occur. If no such limit has been reached at step
130, the process returns
to step 110 for another round of negotiation. However, if such a limit has
been reached at stage
130, the process proceeds to step 134 wherein the negotiations are terminated
and forensic
information is returned to Negotiation Manager 22 to enable it to take
appropriate action.
Once a determination is made at step 106 that no stages remain to be
negotiated, the process
completes and the connection is established at step 138 with the agreed values
for all parameters.
It is contemplated that the negotiation may require one or more participants
to refer to outside
quotation services or other service providers to obtain cost quotations and/or
to verify availability
of resources.
CA 02300453 2000-03-10
-21 -
In the event that step 134 is reached and forensic information is returned to
the participants,
this information can be analyzed in an attempt to determine why the
negotiation did not converge.
After analysis, one or more of the participants (usually at least the agent
for the originating End
User) can alter one or more parameter values that were agreed at an earlier
stage and recommence
the negotiation at that stage. For example, if the negotiation was halted at
the third stage of
negotiation, changes to the values of one or more parameters in the second, or
even the first, stage
can be made and the negotiations restarted at the earliest stage modified.
The process illustrated in Figure 7 employs a Round Robin negotiating strategy
wherein
each participant has a chance to review, in turn, the parameter values in a
stage before they are
agreed to. As will be apparent to those of skill in the art, and as mentioned
above, other
negotiating disciplines can be employed with the present invention.
While not shown in the process of Figure 7, in some circumstances two or more
participants.
can be in competition in a negotiation. For example, two Service Providers can
be interested in
provided a link for a communication. In such a case, each Service Provider
participates in a
negotiation until a discrepancy between there desired values for one or more
parameter is
experienced and after which Negotiation Manager 22 selects the Service
Provider with the more
favorable value to continue the negotiations and removes the other Service
Providers) from
subsequent stages of the negotiation, which can simplify those subsequent
stages. Of course, other
strategies can be employed for selecting between competing participants,
including allowing an
End User to specify his or her preferences (which could take incentives such
as volume discounts
or rebates in account), etc. It is contemplated that, as convergence and
openness continues to
develop in the telecommunications marketplace, the ability to negotiate with
competing
participants will provide a significant advantage over prior art systems.
Figure 8 shows a flowchart of the method of re-commencing a negotiation. In
this Figure, steps
which are the same as those of Figure 7 are indicated with the same step
numbers. As shown, the
process recommences at step 142 where the proposal, with one or more
previously agreed
parameter values modified, is transferred to Negotiation Manager 22. At step
146, the negotiation
commences for the parameter values in the earliest stage with a modified
parameter value. The
process proceeds next through steps 110, 114, 118, 122, 126, 106, 138 and/or
130 as before. In the
event that step 150 is reached and the negotiation is terminated without
agreement, the proposal
and forensic information is returned to Negotiation Manager 22. Negotiation
Manager 22 can be
configured to limit repetition of the modification and restart process of
Figure 8 a fixed maximum
number of times or with any other suitable strategy to ensure that the process
stops, even when a
CA 02300453 2000-03-10
-22-
negotiated agreement cannot be reached.
As described above, negotiation in the context of the invention refers to a
process in which
each participant is able to consider a proposal and either accept or revise
the proposal. This is in
contrast to the methods in the prior art, particularly, the offer - acceptance
model, such as US
patent 5,859,979 where the originating entity sends a list of options and a
responding entity selects
one.
It is contemplated that existing telephony and data communication service
providers can
modify their routing equipment to apply the invention in a broad range of
manners, including
adding the new operability as stand-alone equipment, or modifying their
existing equipment
accordingly and such developments are within the scope of the present
invention.
The above-described embodiments of the invention are intended to be examples
of the
present invention and alterations and modifications may be effected thereto,
by those of skill in the
art, without departing from the scope of the invention which is defined solely
by the claims
appended hereto.
