 |
Claims  |
|
|
I claim:
1. A method for reserving and allocating a plurality of competing demands
for an ordered bus communications network in response to a plurality of
demands from a source, the network including a plurality of customer
sites, each customer site including one or more endpoints, each endpoint
being connectable to a switching system, the switching system being
connectable to one or more other switching systems, means for connecting a
first endpoint through said one or more switching systems to a second
endpoint, wherein the improvement comprises the steps of:
(a) receiving demands from a customer site for allocating the network for a
communication among a plurality of customer sites;
(b) stratifying the received demands in response to a grouping of endpoints
to be conferenced at the customer sites;
(c) allocating the network resources to connect the endpoints to be
conferenced in response to the stratified demand including
generating setup and terminate times for each endpoint to be connected in a
conference;
reserving the endpoints to be connected in the conference; and
generating a plurality of bindings for signaling the network and the source
as to success of connecting the endpoints to be conference over said
ordered bus network.
2. The method defined in claim 1 further comprising the steps of:
(d) stratifying a customer's demand into sets of strategies for groupings
of like endpoints;
(e) allocating network resources responsive to characteristics of the
different groupings of like endpoints;
(f) for each strategy, generating the setup.sub.-- times and
terminate.sub.-- times for each endpoint;
(g) for each strategy, reserving the endpoints for a reservation; and
(h) for each strategy, generating bindings.
3. The method defined in claim 2 further comprising the steps of:
(i) for a first grouping of like endpoints selected from the group
consisting of codecs, alternate accesses, and offnets, extending a
conference signal through a multiplexer or concentrator at a customer site
over an access line to a homing DACS to which said endpoints are
connected.
4. The method defined in claim 2 further comprising the step of:
(i) for a second grouping of like endpoints including one or more audio
bridges, extending a conference signal from a customer site to a central
bridging DACS on which said audio bridge resides.
5. The method defined in claim 3 or 4 further comprising the step of:
(j) generating instructions for controlling said homing DACS to provide
connectivity of like endpoint conference signals.
6. The method defined in claim 3 further comprising the step of:
(j) generating bindings for connections between said one or more switching
systems required for the first grouping of codec like endpoints.
7. The method defined in claim 2 further comprising the step of:
(i) for a third grouping of like endpoints including one or more video
conference controllers, extending a conference signal from a customer site
to the network.
8. The method defined in claim 2 wherein said bindings generation step (h)
further comprises the steps of:
responsive to a service.sub.-- and to a bandwidth and to a start.sub.--
time and to a stop.sub.-- time from a source of demand, searching for one
or more communication paths, which satisfy the demand;
responsive to the demand satisfying communication paths, searching the
communication paths in a predetermined direction and range of bandwidth to
identify the bandwidth in the paths, which satisfy the source demand.
9. The method defined in claim 8 wherein said bindings generation step (h)
further comprises the steps of:
generating a buffer time around the start.sub.-- time and the stop.sub.--
time;
responsive to the buffer time, searching for a bandwidth which does not
collide with other source demands.
10. The method defined in claim 2 wherein said bindings generation step (h)
further comprises the steps of:
responsive to a delta scheme and responsive to the current.sub.-- time of
the demand, determining whether a new source demand can be satisfied using
existing bindings, or whether new bindings need to be generated;
responsive to the determining step, providing a set of bindings to satisfy
the source demand.
11. The method defined in claim 1 further comprising the step of:
(i) determining if the network is not available for reconfiguration of a
conference during any reconfiguration of the network.
12. The method defined in claim 1 wherein said bindings generation step
further comprises the steps of:
responsive to a service.sub.-- type and to a bandwidth and to a
start.sub.-- time and to a stop.sub.-- time from a source of demand,
searching for one or more communication paths, which satisfy the demand;
responsive to the demand satisfying communication paths, searching the
communication paths in a predetermined direction and range of bandwidth to
identify the bandwidth in the paths, which satisfy the source demand.
13. The method defined in claim 12 wherein said bindings generation step
further comprises the steps of:
generating a buffer time around the start.sub.-- time and the stop.sub.--
time;
responsive to the buffer time, searching for a bandwidth which does not
collide with other source demands.
14. The method defined in claim 1 wherein said bindings generation step
further comprises the steps of:
responsive to a change to a previously processed demand and responsive to
the current.sub.-- time of the demand, determining whether a new source
demand can be satisfied using existing bindings, or whether new bindings
need to be generated;
responsive to the determining step, providing a set of bindings to satisfy
the source demand.
15. A system for reserving and allocating a plurality of competing demands
for an ordered bus communications network in response to a plurality of
demands from a source, the network including a plurality of customer
sites, each customer site including one or more endpoints, each endpoint
being connectable to a switching system, the switching system being
connectable to another switching system, means for connecting a first
endpoint through one or more switching systems to a second endpoint,
wherein the improvement comprises:
means for receiving demands from a customer site for allocating the network
for a communication among a plurality of customer sites;
means for stratisfying the received demands in response to a grouping of
endpoints to be conferenced at the customer sites;
means for allocating the network resources to connect the endpoints to be
conferenced in response to the stratified demand including
(i) means for generating setup and terminate times for each endpoint to be
connected in a conference;
(ii) means for reserving the endpoints to be connected in the conference;
and
(iii) means for generating a plurality of bindings for signalling the
network and the source as to success of connecting the endpoints to be
conferenced over said ordered bus network.
16. The system defined in claim 15 further comprising:
means for stratifying a customer's demand into sets of strategies for
groupings of like endpoints;
means for allocating network resources responsive to characteristics of the
different groupings of like endpoints;
for each strategy, means for generating the setup.sub.-- times and
terminate.sub.-- times for each endpoint;
for each strategy, means for reserving the endpoints for a reservation; and
for each strategy, means for generating bindings.
17. The system defined in claim 16 further comprising:
for a first grouping of like endpoints selected from the group consisting
of codecs, alternate accesses, and offnets, means for extending a
conference signal through a multiplexer or concentrator at a customer site
over an access line to a homing DACS to which said endpoints are
connected.
18. The system defined in claim 16 further comprising:
for a second grouping of like endpoints including one or more audio
bridges, means for extending a conference signal from a customer site to a
central bridging DACS one which said audio bridge resides.
19. The system defined in claim 17 or 18 further comprising:
means for generating instructions for controlling said homing DACS to
provide connectivity of like endpoint conference signals.
20. The system defined in claim 17 further comprising:
means for generating bindings for connections between said one or more
switching system required for the first grouping of codec like endpoints.
21. The system defined in claim 16 further comprising:
for a third grouping of like endpoints including one or more video
conference controllers, means for extending a conference signal from a
customer site to the network.
22. The system defined in claim 16 wherein said last mentioned bindings
generation means further comprises:
responsive to a service.sub.-- type and to a bandwith and to a start.sub.--
time and to a stop.sub.-- time from a source of demand, means for
searching for one or more communication paths, which satisfy the demand;
responsive to the demand satisfying communication paths, means for
searching the communication paths in a predetermined direction and range
of bandwidth to identify the bandwidth in the paths, which satisfy the
source demand.
23. The system defined in claim 22 wherein said last mentioned bindings
generation means further comprises:
means for generating a buffer time around the start.sub.-- time and the
stop.sub.-- time;
responsive to the buffer time, means for searching for a bandwidth which
does not collide with other source demands.
24. The system defined in claim 16 wherein said last mentioned bindings
generation means further comprises:
responsive to a change to a previously processed demand and responsive to
the current.sub.-- time of the demand, means for determining whether a new
source demand can be satisfied using existing bindings, or whether new
bindings need to be generated;
responsive to the determining step, means for providing a set of bindings
to satisfy the source demand.
25. The system defined in claim 15 further comprising:
means for determining if the network is not available for reconfiguration
of a conference during any reconfiguration of the network.
26. The system defined in claim 15 wherein said bindings generation means
further:
responsive to a service.sub.-- type and to a bandwidth and to a
start.sub.-- time and to a stop.sub.-- time from a source of demand, means
for searching for one or more communication paths, which satisfy the
demand;
responsive to the demand satisfying communication paths, means for
searching the communication paths in a predetermined direction and range
of bandwidth to identify the bandwidth in the paths, which satisfy the
source demand.
27. The system defined in claim 26 wherein said bindings generation means
further comprise:
means for generating a buffer time around the start.sub.-- time and the
stop.sub.-- time;
responsive to the buffer time, means for searching for a bandwidth which
does not collide with other source demands.
28. The system defined in claim 15 wherein said bindings generation means
further comprises:
responsive to a delta scheme and responsive to the current.sub.-- time of
the demand, means for determining whether a new source demand can be
satisfied using existing bindings, or whether new bindings need to be
generated;
responsive to the determining step, means for providing a set of bindings
to satisfy the source demand. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to resource allocation and, more particularly, to
allocating a constrained common resource among a plurality of demands for
the resource.
2. Description of the Prior Art
The term "resource allocation" applies to that class of problems, which has
as a common characteristic the need to physically allocate a restricted or
constrained common resource among a plurality of demands for that
resource. For example, in a communications system, it is common to
allocate network resources such as trunks for video conferencing on a
manual first come, first served basis. Obviously, it would be desirable to
automate the allocation process.
Dynamic storage allocation problems are well known in the art. The term
"dynamic storage allocation" applies to that class of problems, which
relates to reserving contiguous space in some storage medium for some
period of time in order to satisfy the demands a customer may have for the
storage medium. Unfortunately, known dynamic storage allocations
algorithms tend to be NP-complete, i.e. they are not generally solvable in
reasonably short periods of time. More specifics can be found in any
standard text such as the text by Michael R. Garey and David S. Johnson
entitled "Computers and Intractability--A Guide to the Theory of
NP-Completeness", New York: W. H. Freeman and Company (1979). In light of
the above, it is common to settle on a solution which may represent a
balance between the imperfect utilization of the resource and the time to
find a recommended solution. Notwithstanding, known processes to find a
recommended solution of the allocation of the constrained common resource
to meet the plurality of demands still require excessive amounts of time
and, therefore, a more timely solution remains needed in the art.
Furthermore, flexibility is needed to better serve the almost
unpredictable needs and demands of the customers, who want and need to use
the common resource. Unfortunately, the common resources often suffers
from maladies and constraints of its own, not the least of which may be
that the common resource is unavailable.
SUMMARY OF THE INVENTION
These and other problems are solved in accord with the principles of my
invention which includes a method and a system for allocating a
constrained common resource among a plurality of demands for the resource.
In response to a plurality of demands from a source, the network, which
includes a plurality of customer sites, each customer site including one
or more endpoints, each endpoint being connectable to a switching system,
the switching system being connectable to another switching system,
comprises means for connecting a first endpoint through one or more
switching systems to a second endpoint. The allocation arrangement
receives demands from a customer site for allocating the network for a
communication among a plurality of customer sites and stratifies the
received demands in response to a grouping of endpoints to be conferenced
at the customer sites. It can then allocate the network resources to
connect the endpoints to be conferenced in response to the stratified
demand including generating setup and terminate times for each endpoint to
be connected in a conference; reserving the endpoints to be connected in
the conference; and generating a plurality of bindings for signalling the
network and the source as to success of connecting the endpoints to be
conferenced over an ordered bus network. The arrangement also stratifies a
customer's demand into sets of strategies for groupings of like endpoints;
allocates network resources responsive to characteristics of the different
groupings of like endpoints; for each strategy, generates the setup.sub.--
times and terminate.sub.-- times for each endpoint and reserves the
endpoints for a reservation and generates bindings. The arrangement also,
for a first grouping of like endpoints such as codecs, alternate accesses,
and offnets, extends a conference signal through a multiplexer or
concentrator at a customer site over an access line to a homing DACS;
while, for a second grouping of like endpoints such as audio bridges,
extends a conference signal from a customer site to a central bridging
DACS; while, for a third grouping of like endpoints such as VCCs, extends
a conference signal from a customer site to the network; means for
generating a DMB sequence number for the reservation.
These and other problems are solved in accord with the principles of my
invention which includes a method and apparatus for allocating a
constrained common resource among a plurality of demands for the resource.
BRIEF DESCRIPTION OF THE DRAWINGS
My invention should become more apparent from the following detailed
description when taken in conjunction with the accompanying drawing in
which:
FIG. 1 is a block diagram illustrating a network, which is useful in
explaining an illustrative embodiment of the principles of the present
invention, and
FIG. 2 illustrates a customer site, which is also useful in explaining an
illustrative embodiment of the principles of the present invention, and
FIG. 3 illustrates a first set of customer demands, which need to be
allocated to satisfy the needs of a customer and which is helpful in
understanding a first example that is also useful in explaining the
principles of the present invention,
FIG. 4 illustrates a second set of customer demands, which need to be
allocated to satisfy the needs of a customer and which is helpful in
understanding a second example that is also useful in explaining the
principles of the present invention,
FIG. 5 illustrates my methodology for allocating a set of customer demands,
which is helpful in understanding the principles of the present invention,
FIG. 6 illustrates an allocator process for codec-like endpoints for use in
the allocator of FIG. 5, which is helpful in understanding the principles
of the present invention,
FIG. 7 illustrates an allocator process for audio bridge-like endpoints for
use in the allocator of FIG. 5, which is helpful in understanding the
principles of the present invention,
FIG. 8 illustrates an allocator process for VCC-like endpoints for use in
the allocator of FIG. 5, which is helpful in understanding the principles
of the present invention, and
FIG. 9 illustrates memory and controller for use in the allocator of FIG.
5, which is helpful in understanding the principles of the present
invention.
DETAILED DESCRIPTION
Referring to FIG. 1, each of a plurality of customer sites 110-1 through
110-N is coupled over a respective access line 120-1 through 120-N (note
that, although N is shown to be eight in FIG. 1, same is for purposes of
illustration and not by way of limitation since N can be a design
parameter, which can be any integer greater than one) to a respective
digital access and cross-connect system (DACS) such as DACS 130-1 through
DACS 130-M (note that, although M is shown to be four in FIG. 1, same is
for purposes of illustration and not by way of limitation since M can be a
design parameter, which can be any integer greater than zero). DACS
equipment such as the publicly used Digital Access and Cross-Connect
System is commercially available from American Telephone and Telegraph
Company. Various features for a DACS including a Digital Multipoint Bridge
(DMB) and Optical Fiber Link Interface are also commercially available and
in public use.
In my example, customer site 110-1 is coupled to DACS 130-1 by way of
access line 120-1; customer sites 110-2 and 110-3 are coupled to DACS
130-2 by way of access lines 120-2 and 120-3, respectively; customer sites
110-4, 110-5, and 110-6 are coupled to DACS 130-3 by way of access lines
120-4, 120-5, and 120-6, respectively; and customer sites 110-7 and 110-8
are coupled to DACS 130-4 by way of access lines 120-7 and 120-8,
respectively. Also, the respective DACS are coupled to each other by way
of an ordered bus communications network arrangement. For example, DACS
130-1 is coupled to DACS 130-2 by way of first internodal link 140-1 and
DACS 130-2 is coupled to DACS 130-3 by way of second internodal link 140-2
and DACS 130-3 is coupled to DACS 130-4 by way of third internodal link
140-3.
Each access line 120-i and each internodal link 140-j can include one or
more communications paths and each communications path has some
predetermined bandwidth and the bandwidth of one communications path may
be, but need not be, the same as the bandwidth of another communications
path and each communications path can be a transmission facility, (a)
which may directly connect, for example, a customer site 110-i and a DACS
130-k or may directly connect one DACS with another DACS, for example,
DACS 130-1 with DACS 130-2 or (b) which may indirectly connect, for
example, a customer site 110-i and a DACS 130-k or may indirectly connect
one DACS with another DACS, for example, DACS 130-1 with DACS 130-3
through interposed equipment or facilities, which interposed equipment or
facilities could include even another DACS like DACS 130-2 interposed
between DACS 130-1 and DACS 130-3.
It is now useful to distinguish between the term "bus" and the term
"internodal link." On the one hand, the term internodal link refers to the
connection between two DACS, e.g., in FIG. 1, internodal links 140-j,
which may directly connect, for example, one DACS 130-k with another DACS
130-m or which may indirectly connect, for example, the two DACS through
interposed equipment or facilities like another DACS. On the other hand,
the term bus refers to an ordered set of internodal links, which connects
a set of DACS in a specific ordered configuration like that shown in FIG.
1. As a further aid in distinguishing the terms, consider the following
example. Each DACS 130-k can be connected to one or more other DACS like
DACS 130-m by a respective internodal link 140-j. Further, when all the
DACS in the network are completely interconnected, it is clear that there
could be many ordered sets of internodal links. Each ordered set of
internodal links that satisfies a predetermined criteria is called a bus.
I have shown only one bus arrangement in FIG. 1, i.e. internodal link
140-1 coupling DACS 130-1 with DACS 130-2 then internodal link 140-2
coupling DACS 130-2 with DACS 130-3 then internodal link 140-3 coupling
DACS 130-3 with DACS 130-4, which results in the ordered set of internodal
links (140-1, 140-2, 140-3), which is a bus. In the trivial case where
there is only a single DACS, there could be a single bus within the single
DACS and there need not be any internodal links.
In general, it is desired that the resources of a network be allocated in
some timely manner such that equipment at one customer site can
communicate with one or more units of equipment at one or more other
customer sites. The term "broadcasting" is often applied to an arrangement
wherein equipment at one customer site communicates in a substantially
simultaneous manner with one or more units of equipment at one or more
other customer sites. Hence, broadcasting is concerned as to the signal
source. The term "conferencing" is applied to an arrangement, which,
without regard to signal source, involves communication among two or more
units of equipment whereby a set of customer sites communicate among each
other.
In accord with one aspect of the principles of my invention, an allocation
methodology is set forth by way of which it is possible to allocate the
limited or constrained resources of a network such as the bandwidth of a
communications path in the network among a plurality of customer demands
for that bandwidth and, importantly, to do the allocation in a manner such
that the expectations of the customer are satisfied.
Assume that a customer or source of a demand at customer site 110-3 places
a demand on a network that a video conferencing connection be set up
between customer site 110-3 and all of the other customer sites 110-i
shown in FIG. 1. The customer typically would have several other demands.
For example, the customer may demand that the conference begin at a
specific time of a day, called a start.sub.-- time-date, and that the
conference terminate at a specific time of the same, or of a different,
day, called a stop.sub.-- time-date. Further, the customer may demand that
the communication paths, which are to be allocated, have some minimum
bandwidth, which may be subject to a constraint such as the constraint
that the network will not allocate bandwidth beyond some predetermined
maximum bandwidth. Still further, the customer may, before the conference
begins or during the time interval of the conference, demand the
flexibility to have certain customer sites dynamically added to, or
terminated from, the conference during the time interval of the conference
and, still even further, these added or terminated demands may be made
with relatively short lead-time and may be made either before or during a
conference call. The customer may further demand that the time to start or
stop the conference be changed or that the minimum bandwidth of the
conference be changed. In addition to the above, there may be still other
customer demands and there may be still other constraints on those
demands.
Those are some of the problems, which are solved in accordance with the
principles of my invention. To illustrate those principles, we will
shortly describe a procedure, which may be used to generate the bindings
for a reservation. But before the procedure is described, some additional
terms will need definition. The term "reservation" refers to a set of
demands by a customer such as the set of demands described in the
immediately preceding paragraph. The term "binding" refers to the concept
represented by a four-tuple of the form (X1, X2, X3, X4) where X1 is a
first specific position within the bandwidth of a communications path; X2,
which for our description is assumed to be larger than X1, is a second
specific position within the bandwidth of the communications path; X3 is
the time-date that the customer wants the conference to be setup; and X4
is the time-date that the customer wants the conference to terminate. Note
that the difference between X2 and X1, i.e. X2-X1, corresponds to the
minimum bandwidth that the the customer demands, which itself is subject
to the constraint that the minimum bandwidth demanded may not exceed the
maximum bandwidth of the communications path, which serves the
reservation.
To better understand one meaning of first position X1 and one meaning of
second position X2 consider a well known digital transmission network,
which includes channelized bandwidth. For example, it is known that a
digital network may include 24 channels (called DS0 channels, each DS0
channel operating nominally at about 64 kilobits per second) in a single
multichannel communications path (called a DS1 channel, which operates
nominally at about 1.544 megabits per second). In turn, it is known that
28 DS1 channels may be included in a single multichannel communications
path (called a DS3 channel, which operates nominally at about 44.7
megabits per second), etc. Now, first position X1 may be a specific one of
the 24 DS0 channels while second position X2, which is larger than X1, may
be a specific other one of the 24 DS0 channels.
To better understand the setup-time-date X3 and the terminate-time-date X4,
note that X3 and X4 could be respectively some time-date before and some
time-date after the actual start-time and actual stop.sub.-- time demanded
by the customer, e.g., the value of X3 in the four-tuple could be less
than the actual start-time-date demanded by the customer so as to allow
the network adequate to set up a connection, hence X3 is also called the
setup.sub.-- time-date, and may be shortened to setup.sub.-- time.
Accordingly, setup.sub.-- time X3 is a time-date such that the conference
connection, if its connection commences before the start.sub.-- time, will
satisfy the expectations of the customer. The difference between the
setup.sub.-- time-date and the start.sub.-- time-date is now described.
The time to allow the network to setup a conference connection is called
the "res.sub.-- setup.sub.-- time.sub.-- delta." While the time to allow
the network to add an endpoint to an in-progress conference is called the
"room.sub.-- setup.sub.-- time.sub.-- delta." The res.sub.-- setup.sub.--
time.sub.-- delta and room.sub.-- setup.sub.-- time.sub.-- delta may have
different values depending on the constraints of the network, but are
assumed to be zero or greater.
Similarly, the value X4 in the four-tuple could be a time-date, which is
greater than the actual stop.sub.-- time-date demanded by the customer, so
as to allow the network adequate time to disconnect, or tear-down, the
connection, hence X4 is also called the terminate.sub.-- time-date, and
may be shortened to terminate.sub.-- time. Accordingly, terminate.sub.--
time X4 is a time-date such that the conference connection, if
disconnected no later that time X4 but certainly no sooner than the actual
stop.sub.-- time-date demanded by the customer, will satisfy the
expectations of the customer. The difference between the terminate.sub.--
time-date and the stop.sub.-- time-date is now described. The time to
allow the network to terminate a conference connection is called the
"res.sub.-- teardown.sub.-- time.sub.-- delta." While the time to allow
the network to terminate an endpoint in an in-progress conference is
called the "room.sub.-- terminate.sub.-- time.sub.-- delta." The
res.sub.-- teardown.sub.-- time.sub.-- delta and room.sub.--
terminate.sub.-- time.sub.-- delta may have different values depending on
the constraints of the network, but are assumed to be zero or greater.
Finally, the plural of the term binding, i.e. the term "bindings", means
the one or more binding that satisfies the customer's demand.
It is now useful to describe more specifically a customer site 110-i.
Typically, a customer site includes one or more units of equipment. Each
unit of equipment at a customer site is called an endpoint. Further, there
may be various kinds of endpoints, e.g. endpoints of a first kind,
endpoints of a second kind, etc. To exemplify this concept, the ensuing
description will consider five kinds of endpoints, called respectively, a
codec (for coder/decoder) endpoint, an audio bridge endpoint, a video
control console (VCC) endpoint, an alternate access endpoint, and an
offnet (for off network) endpoint. A codec like codec 200 in FIG. 2 is a
unit of equipment on a customer's site, one form of which could encode a
video signal from a source for transmission to a sink where the encoded
signal could be decoded, for example, to its original form. An audio
bridge like audio bridge 220 in FIG. 2 is a unit of equipment on a
customer's site, one form of which could be an arrangement, which mixes
audio signals from a plurality of sources into a single signal that is to
be extended to one or more other audio bridges. A VCC like 240 in FIG. 2
is an example of yet another specific unit of equipment, or endpoint,
located on a customer's site, one form of which could include capabilities
that permit a customer site to originate a video conference, to
communicate with a plurality of other customer sites, e.g. to function as
a "broadcaster" of information to many sites at one time, place a
reservation request, or to perform other control functions. Generally, for
purposes of this description, on the one hand, an alternate access like
alternate access 260 in FIG. 2 is the term to describe any unit of
equipment, other than a codec, audio bridge or VCC, which functions as an
endpoint and is located on a customer's site. On the other hand, an offnet
like offnet 280 in FIG. 2, although not necessarily a unit of equipment,
can be thought of as a quasi-unit of equipment, and, as will be made more
clear, is considered as a unit of equipment for our purposes. Indeed, an
offnet could be a service rather than a product. For example, an offnet
could be a member of the Accunet (R) family of digital services, which is
a commercially available service. More generally, an offnet, which is a
short-hand form of the words off network, refers to a signal processing
arrangement, a signal transport arrangement, or any other arrangement,
which may or may not be on the customer's site but which extends a signal
to the instant network for purposes such as interconnecting the offnet
provided signal to one or more endpoints within the instant network. A
distinction between an offnet and an alternate access is that an alternate
access would be a unit of equipment (other than a codec, audio bridge or
VCC) on a customer's site while an offnet would be any arrangement other
than a unit of equipment on the customer's site.
It may be noted that a common characteristic among all the endpoints is
that each endpoint will require some minimum bandwidth to communicate with
another endpoint and that each endpoint is adapted to extend a signal
through a network to one or more "like" endpoints and that the network has
no need to "understand", e.g. no need to decode, the information content
of the extended signal. Using the example of the above five kinds of
endpoints; three of those kinds of endpoints, i.e. codecs, audio bridges
and VCCs, are examples of "unlike" endpoints since, for example, a codec
would typically not understand the information content of a signal
extended from an audio bridge.
Like endpoints are endpoints, which would understand signals transmitted
therebetween. For example, two endpoints having the same kind of equipment
like two codecs, or two audio bridges, or two VCCs would be examples of
like endpoints. In addition, a customer could demand that a signal be
extended from a codec at one customer site to an alternate access or to an
offnet at another customer site. In this example, the codec and the
alternate access or the codec and the offnet could be like endpoints. This
example assumes that some arrangement would be included in the alternate
access or the offnet, which arrangement could understand the information
content of the extended signal.
In contrast, unlike endpoints are endpoints, which would typically not
understand signals transmitted therebetween. For example, a codec at one
customer site would be an unlike endpoint with respect to an audio bridge
or a VCC at another customer site.
Referring to FIG. 2 and keeping the description of FIG. 1 in mind, sample
customer site 110-i is coupled over access line 120-i to DACS 130-k.
Customer site 110-i can include a plurality of endpoints, each endpoint
coupled over a respective communications path through a multiplexer or
concentrator 295 thence coupled over access line 120-i to DACS 130-k. In
my example, the endpoints include codec 200, audio bridge 220, video
control console (VCC) 240, alternate access 260, and offnet 280 coupled
through multiplexer or concentrator device 295 respectively by way of
communications paths 210, 230, 250, 270 and 290 onto access line 120-i.
Although FIG. 2 illustrates one of each of the five kinds of endpoints
that were mentioned above, same is not by way of limitation, but only by
way of example. A customer site may include other combinations of the
shown endpoints, may include other kinds of equipment as endpoints, may
include some but not all of the shown kinds of endpoints, et cetera.
Continuing, a customer may request or demand that a connection be
established, i.e. that there be "connectivity", between two customer
sites, which is herein referred to as a two point reservation. A twopoint
reservation may reflect a customer's demand for connectivity in order to
allow a single signal to be communicated between the two customer sites.
Alternatively, a customer may request or demand connectivity between more
than two customer sites, which is herein referred to as a multipoint
reservation. A multipoint reservation may reflect a customer's demand for
connectivity in order to allow a single signal to be shared among a
plurality of like endpoints such as (a) connectivity to bridge a plurality
of the audio bridges like audio bridge 220 located at different ones of
customer sites 110-i so as to allow a first signal to be commonly shared,
or broadcast, or conferenced among the connected audio bridges and/or (b)
connectivity to connect a plurality of video control consoles like VCC 240
located at different ones of customer sites 110-i so as to allow a second
signal to be commonly shared, or broadcast, or conferenced among the
connected VCCs and/or (c) connectivity to connect a plurality of codec,
alternate access, and offnet endpoints like codec 200, alternate access
260 and offnet 280 located at different ones of customer sites 110-i so as
to allow a third signal to be commonly shared, or broadcast, or
conferenced among the connected endpoints.
A multipoint reservation may specify the desired connectivity among two or
more endpoints or contemplate a predetermined default set of
connectivities. For example, the customer may demand either (a) that
certain codecs be connected AND that certain audio bridges be connected
AND that certain VCCs be connected or (b) that certain codecs AND that
certain alternate accesses AND that certain offnets be connected AND that
a predetermined set of audio bridges and VCCs be connected, which
predetermined set is a function of the specific codecs, alternate accesses
and offnets that were demanded to be connected by the customer.
One example of alternative (b) above is an embodiment having a codec 200 at
a customer site 110-i involved in a conference in which case the
predetermined set could include at least one audio bridge 220 AND at least
one VCC 240 at the customer site 110-i and further result in the audio
bridge 220 and the VCC 240 remaining connected to the conference for so
long as the codec 200 remains connected to the conference. In this
example, connectivity would remain among codec 200 and the endpoints (e.g.
audio bridge 220 and VCC 240) in the predetermined set even though a
connection among other codecs or other alternate accesses or other offnets
at customer site 110-i has been disconnected. The connectivity among codec
200 and the endpoints in the predetermined set would remain for so long as
a conference remains for codec 200 at the customer site 110-i. However, it
should be noted that the endpoints in a first predetermined set for first
codec 200 could also be endpoints in a second predetermined set for a
second codec or other endpoint at customer site 110-i, in which case, even
if the first codec 200 is disconnected from the conference, the common
endpoints in the first and the second predetermined sets could remain
connected by virtue of the second codec remaining or being (e.g. being
added to the conference) in the conference.
Referencing FIG. 5, my methodology stratifies (500) customer demand (400)
by like endpoints into a plurality of sets of customer demands and then
allocates (600, 700, 800) the resources of the network for each set of
customer demands with like endpoints and makes the allocation information
available (900) to the network for use thereby and also feedbacks (510)
the allocation results to the customer. The allocation information is
stored and controlled by way of memory and controller 900 for making the
information available to both the network and the customer. The controller
910 provides the data requested by allocators 600, 700, and 800 to them
and if all allocators are successful in allocating the reservation, the
controller removes all tuples in memory associated with this reservation
and places the new set of tuples associated with this reservation into the
appropriate memories. If the allocators were successful in allocating the
reservation, the controller 910 notifies 510 the customer demand 400 and
the network of the success of the methodology and the new tuples. If the
allocators were not successful in allocating the reservation, the
controller 910 notifies 510 the customer demand 400.
The methodology then iterates the following actions:
1. Stratifies the customer's demands into sets of strategies for groupings
of like endpoints;
2. Allocates network resources responsive to characteristics of the
different groupings of like endpoints;
3. For each strategy, generates the setup.sub.-- times and terminate.sub.--
times for each endpoint;
4. For each strategy, reserves the endpoints for the reservation;
5. For each strategy, generates bindings;
6. For a first grouping of like endpoints such as codecs, alternate
accesses, and offnets, extends a conference signal through a multiplexer
or concentrator at a customer site over an access line to a homing DACS;
7. For a second grouping of like endpoints such as audio bridges, extends a
conference signal from a customer site to a central bridging DACS;
8. For a third grouping of like endpoints such as VCCs, extends a
conference signal from a customer site to the network;
9. Generates a DMB sequence number for the reservation;
10. Generates cross connects in the DACS to provide connectivity of like
endpoint conference signals;
11. Generates the conference signal internodal connectivity required for
the first grouping of codec like endpoints; and
12. Determines if the network is not available for reconfiguration of the
conference during any reconfiguration of the network.
What follows now is a description of each of these actions in further
detail.
As to endpoint demand stratifier 500, endpoints of a first grouping, e.g.
codecs 200, alternate accesses 260, and offnets 280, are allocated
according to a first strategy 600; endpoints of a second grouping, e.g.
audio bridges 220, are allocated according to a second strategy 700;
endpoints of a third grouping, e.g. VCCs 240, are allocated according to a
third strategy 800; etc. Each grouping of endpoints includes only like
endpoints and no one grouping includes both like endpoints and unlike
endpoints.
Common among each strategy are the processes of generating (610 in FIG. 6,
710 in FIG. 7, and 810 in FIG. 8), setup.sub.-- times X3 and
terminate.sub.-- times X4 for the endpoints reserving (620 in FIG. 6, 720
in FIG. 7, and 820 in FIG. 8), the endpoints and generating (630 in FIG.
6, 730 in FIG. 7, and 830 in FIG. 8), bindings (X1, X2, X3 and X4).
Before going into the details of three such strategies, an example of a
process of allocating bandwidth to a conference on an access line or on an
internodal link is provided through the example shown in FIG. 3. The
example is chosen so as to also focus on a process of generating bindings.
Referring to FIG. 3, assume that a plurality of customer demands gives rise
to a corresponding plurality of bindings, which are labelled in summary
form in FIG. 3 as 310-1, 310-2 and 310-3. The customer demands may be
allocated to two communication paths 320-1 and 320-2 of an access line
120-i or an internodal link 140-k. Here assume the paths are part of
internodal link 140-k. Customer demand 310-1 gives rise to a four-tuple
binding on communications path 320-1 of internodal link 140-k. The
four-tuple includes a first specific position X1 within the bandwidth of
| | |
