 |
Claims  |
|
|
We claim:
1. A method for use in an arrangement comprising a communication network
interconnecting a plurality of user stations, said method comprising
providing a first call among a first set of said user stations,
providing a second call among a second set of said user stations and
merging said first and second calls into a single call, comprising
plurality of channels comprising virtual channels of a multicast
connection, among at least three user stations from said first and second
sets of said user stations, said plurality of channels corresponding to a
combination of channels of said first and second calls.
2. A method in accordance with claim 1 wherein said merging comprises
merging said first and second calls into a single call connection,
comprising said plurality of channels, among the union of said first and
second sets of user stations.
3. A method in accordance with claim 1 wherein said first call comprises a
signaling channel, said second call comprises a signaling channel, at
least one of said first and second calls further comprises at least one
non-signaling channel, and said plurality of channels comprises a
signaling channel and at least one non-signaling channel.
4. A method in accordance with claim 1 wherein said first call comprises
at least one data channel, said second call comprises at least one data
channel, and said plurality of channels includes a data channel for each
data channel of said first and second calls.
5. A method in accordance with claim 4 wherein at least one of said first
and second calls further comprises a voice channel, and said plurality of
channels further includes a voice channel.
6. A method in accordance with claim 5 wherein said first call further
comprises a signaling channel, said second call further comprises a
signaling channel, and said plurality of channels further includes a
signaling channel.
7. A method in accordance with claim 4 wherein at least one of said first
and second calls further comprises an image channel, and said plurality of
channels further includes an image channel.
8. A method in accordance with claim 4 wherein at least one of said first
and second calls further comprises a video channel, and said plurality of
channels further includes a video channel.
9. A method in accordance with claim 1 further comprising
in response to user input, selectively providing said at least three user
stations with access to transmit information to and receive information
from said plurality of channels.
10. A method in accordance with claim 1 wherein at least one of said first
set of user stations and at least one of said second set of user stations
include display means, said method further comprising
in response to user input at said one of said first set stations, both
establishing said first call in said network and displaying
representations corresponding to said first set of user stations in a
window on said display means of said one of said first set stations, and
in response to user input at said one of said second set stations, both
establishing said second call in said network and displaying
representations corresponding to said second set of user stations in a
window on said display means of said one of said second set stations.
11. A method in accordance with claim 1 wherein one of said plurality of
user stations is a member of both of said first and second sets, said one
user station comprises display means, said merging is in response to user
input at said one user station, said method further comprising
further in response to said user input at said one user station, displaying
representations corresponding to user stations of said first and second
sets in a window on said display means.
12. A method in accordance with claim 11 further comprising
further in response to said user input at said one user station,
displaying, in said window, representations each corresponding to one of
said plurality of channels.
13. A method in accordance with claim 11 wherein said plurality of channels
includes at least one data channel, said method further comprising
displaying, in a second window of said display means, a data communication
application shared among user stations of said first and second sets via
said one data channel.
14. A method in accordance with claim 1 wherein one of said plurality of
user stations is a member of both of said first and second sets, said
method further comprising
in response to user input at said one user station, transmitting a merge
request via said network to each of the other user stations of said first
and second sets, and
in response to receipt of a favorable reply to said merge request from each
of said other user stations of said first and second sets, said one user
station initiating said merging.
15. A method for use in an arrangement comprising a communication network
interconnecting a plurality of user stations, said method comprising
establishing a first call, comprising at least a voice channel and a data
channel, among one user and a first set of a multiplicity of said user
stations,
establishing a separate, second call, comprising at least a voice channel,
among said one said user and a second set of a different multiplicity of
said user stations, and
in response to a request at said one user station, merging said first and
second calls into a single call, comprising at least a voice channel and a
data channel, among user stations of said first and second sets.
16. A method for use in an arrangement comprising a communication network
interconnecting a plurality of user stations, said method comprising
providing a single call, comprising a plurality of channels, among a set of
said user stations, and
splitting said single call into a first call among a first subset of said
set of user stations and a second call among a second subset of said set
of user stations, said first call including channels corresponding to a
first subset of said plurality of channels and said second call including
channels corresponding to a second subset of said plurality of channels.
17. A method in accordance with claim 16 wherein said plurality of channels
includes a signaling channel and at least one non-signaling channel, said
first call comprises a signaling channel, said second call comprises a
signaling channel, and at least one of said first and second calls further
comprises at least one non-signaling channel.
18. A method in accordance with claim 16 wherein one of said set of user
stations is a member of both of said first and second subsets of user
stations, said method comprising
in response to user input at said one station, transmitting a split request
via said network to each of the other user stations of said set of user
stations, and
in response to receipt of a favorable reply to said split request from each
of said other user stations of said set of user stations, said one station
initiating said splitting.
19. A method for use in an arrangement comprising a communication network
interconnecting a plurality of user stations, said method comprising
said network providing a first call among a first set of at least three of
said user stations, said first call comprising at least a voice channel,
said network providing a separate, second call among a second set of at
least three of said user stations, said second call comprising at least a
voice channel, where only one of said plurality of user stations is a
member of both of said first and second sets, and
said one user station enabling a selected other of said user stations to
communicate via both of said first and second calls at the same time.
20. A method in accordance with claim 19 wherein said enabling comprises
enabling said selected other user station to transmit voice concurrently on
said voice channels of both of said first and second calls.
21. A method in accordance with claim 19 wherein said enabling comprises
enabling said selected other user station to transmit voice on the voice
channel of one of said first and second calls and to concurrently receive
voice on the voice channel of the other of said first and second calls.
22. A method in accordance with claim 19 wherein said enabling comprises
enabling said selected other user station to receive voice concurrently on
said voice channels of both of said first and second calls.
23. A method in accordance with claim 19 wherein said one user station
comprises display means, said method further comprising
displaying, for said first call, representations corresponding to said
first set of user stations in predefined association on said display
means, and concurrently displaying, for said second call, representations
corresponding to said second set of user stations in predefined
association on said display means.
24. A method in accordance with claim 19 wherein said one user station
comprises display means, said method further comprising
displaying, for said first call, representations corresponding to said
first set of user stations in a first window on said display means, and
displaying, for said second call, representations corresponding to said
second set of user stations in a second window on said display means.
25. A method in accordance with claim 19 wherein said one user station
comprises display means, said first call further comprising at least one
data channel, said method further comprising
displaying, for said first call, representations corresponding to said
first set of user stations and a representation corresponding to said data
channel in predefined association on said display means.
26. A method in accordance with claim 19 further comprising
said network merging said first and second calls into a single call,
comprising at least a voice channel, among said first and second sets of
user stations.
27. A method in accordance with claim 19 further comprising
said network splitting a single call into said first and second calls, said
single call comprising at least a voice channel among said first and
second sets of user stations.
28. A method for use in an arrangement comprising a communication network
interconnecting a plurality of user stations, said method comprising
said network providing a first call among a first set of said user
stations,
said network providing a second call among a second set of said user
stations, where one of said plurality of user stations is a member of both
of said first and second sets and said one user station comprises display
means, and
displaying, for said first call, representations corresponding to said
first set of user stations in a first window on said display means, and
concurrently displaying, for said second call, representations
corresponding to said second set of user stations in a second window on
said display means.
29. A method in accordance with claim 28 further comprising
in response to user input at said one station, both excluding one of said
first set of user stations from said first call and removing the
representation corresponding to said excluded user station from said first
window.
30. A method in accordance with claim 28 where said first call comprises a
plurality of channels, said method further comprising
displaying, in said first window, representations each corresponding to one
of said plurality of channels.
31. A method in accordance with claim 30 wherein said plurality of channels
includes at least one data channel, said method further comprising
displaying, in a third window of said display means, a data communication
application shared among said first set of user stations via said one data
channel.
32. A method in accordance with claim 31 further comprising
in response to user input at said one station, both excluding said data
communication application from said first call and removing the
representation corresponding to said one data channel from said first
window.
33. A method in accordance with claim 28 wherein said first call includes
at least one non-signaling channel, said method further comprising
in response to user input at one of said first set of user stations,
selectively providing said first set of user stations with access to
transmit information to and receive information from said non-signaling
channel.
34. A method in accordance with claim 28 further comprising
recording said first call while communicating on said second call. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related to the application of T. J. Baumgartner and W.
F. Leung U.S. Pat. No. 5,138,614 entitled "Transformation Method for
Network Conference Connections", and W. F. Leung and S. Tu U.S. Pat. No.
5,103,444 entitled "Conference Connection Method in a Multicast Packet
Switching Network" filed concurrently herewith and assigned to the same
assignee as the present application.
TECHNICAL FIELD
This invention relates to communication conferencing.
BACKGROUND AND PROBLEM
U.S. Pat. No. 4,905,231, issued to W. F. Leung et al. on Feb. 27, 1990,
discloses a multimedia communication system using a single packet
switching network for the various media based on what is referred to as a
multimedia virtual circuit. A virtual circuit is a packet-switched
communication path between two endpoints. A network call setup procedure
establishes a virtual circuit and an associated virtual circuit identifier
based on a destination address. To route successive packets, the network
needs only the virtual circuit identifier. In a multimedia virtual
circuit, a virtual circuit is divided into multiple virtual channels at
the workstations. Each channel represents a different information medium
and has a separate channel identifier; the composite multimedia virtual
circuit represents the resulting multimedia call. As the various
multimedia call sources generate traffic, the workstation multiplexes the
packetized traffic onto a single network virtual circuit. The destination
workstation demultiplexes this traffic back into multiple channels, which
it routes to a telephone, speaker, file, or other destination. This
process preserves the temporal ordering of the information streams so that
in a voice and video call, for example, the voice corresponds to the mouth
movement in the video picture. The multimedia virtual circuit also
provides a simple way to let a multimedia call destinatio associate the
multiple media. A single incoming call notification arrives from the
network to announce a call. The workstations then exchange signaling
information over a virtual channel of the multimedia virtual circuit to
set up all the necessary channels and to route them to the appropriate
devices.
The Rapport multimedia conferencing system, disclosed in the S. R. Ahuja et
al. article, "The Rapport Multimedia Conferencing System," Proceedings of
Conference on Office Information Systems, March 1988, supports
interactive, real-time distributed conferences among two or more people.
Executing on personal workstations interconnected by separate data and
voice networks, the Rapport system provides basic mechanisms to create,
manage, and terminate conferences. The system provides an environment in
which many types of meetings can take place, including telephone
conversations, discussion among colleagues, and lectures. Existing
workstation programs can be used during a conference to produce and edit
data and displays for the conferees. Rapport is designed to help people
emulate face-to-face conferences as closely as possible with their
workstations. However, the reliance on separate networks for the different
media (data and voice) substantially complicates the control of conference
calls. Although concurrent participation in many conferences is possible,
a user is only able to communicate on one call at a time. A Rapport system
user may participate in many conferences concurrently by switching among
contexts at the click of a mouse button. This is equivalent to being able
to walk in and out of several meeting rooms (and one's office) instantly.
It is anticipated that this capability will encourage users to keep many
conferences active for long periods of time in much the same fashion as
the use of screen windows allows one to keep many programs and files
active with the present data networks. One such long-lived conference
might be an intercom connection between a manager and a secretary. Others
might be among the collaborators in a design project or the authors of a
paper. It is anticipated that once the capability for multiple concurrent
calls is provided, it will be useful to merge and split such calls. For
example, the manager may ask the secretary to join a design project
conference from time to time to assist the project team. The effective
control of a plurality of multimedia calls poses a technical problem,
particularly in the Rapport system arrangement comprising several separate
networks, but also for the system of the above-referenced U.S. Pat. No.
4,905,231 employing a single network for all media.
SOLUTION
This problem is solved and a technical advance is achieved in accordance
with the principles of the invention in a method for controlling multiple
concurrent calls where each call comprises one or more channels. A first
call among a first set of user stations and a second call among a second
set of user stations are, for example, merged into a single call
comprising a plurality of channels among, significantly, at least three
user stations from the first and second sets. The plurality of channels of
the single, merged call corresponds to a combination of channels of the
first and second calls and, illustratively, may include a signalling
channel, a voice channel, and one data channel for each data channel of
the first and second calls (FIG. 1). The method is also applicable to
calls including image or video channels.
In an illustrative embodiment, a user interface is provided such that the
first call is established in response to user input, e.g., input via a
mouse button, and, in addition, representations, e.g., face icons
corresponding to users of the first set of user stations, are displayed in
a window of a display (FIG. 17). The second call is established in similar
fashion among the second set of user stations. The merging of the two
calls is effected in response to user input at a user station that is a
member of both the first and second sets. As a result of the merge,
representations corresponding to the user stations of the first and second
sets are displayed in a window for the merged call. In addition,
representations each corresponding to one of the plurality of channels of
the merged call are also displayed in the window. Icons for a voice
channel, a data channel being used for a character-based application ksh,
and a data channel being used for a graphical-based application EZ, are
illustrated in FIG. 19 in a representation of a conference room. The data
communication applications themselves are displayed in other windows. An
access control mechanism provides selective access for a user station to
transmit information to and receive information from the plurality of
channels of the merged call. The plurality of channels of the merged call
comprise virtual channels of a multicast connection through a packet
switching network. A merge request is transmitted from one user station
via the network to each of the other user stations of the first and second
set. The merging is initiated in response to receipt of a favorable reply
from each of the other user stations.
In a method of the invention, a single call, comprising a plurality of
channels, is provided among a set of user stations. The single call is
split into a first call among a first subset of user stations and a second
call among a second subset of user stations. The first call includes
channels corresponding to a first subset of the channels of the single
call and the second call includes channels corresponding to a second
subset of the channels of the single call (FIG. 2).
A further method of the invention is used in an arrangement comprising a
communication network interconnecting a plurality of user stations. A
first call, comprising at least a voice channel, is provided among a first
set of user stations, and a second call, comprising at least a voice
channel, is provided among a second set of user stations. One user station
is a member of both of the first and second sets. The one user station
enables a user to communicate via both of the first and second calls at
the same time.
Illustratively, the one user station comprises a voice bridge, implemented,
for example, using a plurality of voice packet/analog voice converters,
and a conventional analog voice bridge. A user is able to communicate on
two (or more) calls at a time. The user is able to transmit voice
concurrently on the voice channels of both of the first and second calls.
The user is also able to transmit voice on the voice channel of one call
and to concurrently receive voice on the voice channel of the other call.
Further, the user is able to receive voice concurrently on the voice
channels of both of the first and second calls.
In a further method of the invention, the network provides a first call
among a first set of user stations and a second call among a second set of
user stations. At least one user station, which is a member of both of the
first and second sets, includes a display. Representations corresponding
to the first set of user stations are displayed in a first window for the
first call, and concurrently, representations corresponding to the second
set of user stations are displayed in a second window for the second call.
A user may record a first call while communicating on a second call.
DRAWING DESCRIPTION
FIG. 1 is a diagram illustrating the merger of two, multi-channel calls
into a single call;
FIG. 2 is a diagram illustrating the splitting of a single, multi-channel
call into two calls;
FIG. 3 is a diagram of a multicast packet switching network;
FIG. 4 is a diagram of an individual multicast packet switch in the network
of FIG. 3;
FIG. 5 is a diagram illustrating a strong packet sequencing condition;
FIG. 6 is a diagram illustrating the packet switching process for a
multicast connection through a multicast packet switch;
FIG. 7a-FIG. 7c illustrate three data packet flow patterns within a
multicast packet switch;
FIG. 8a-FIG. 8d are diagrams used in describing properties of data packet
flow patterns;
FIG. 9a-FIG. 9c and FIG. 10a-FIG. 10b diagrams used in describing
properties of vanilla multicast connections;
FIG. 11a-FIG. 11c are diagrams used in describing properties of strong
multicast connections;
FIG. 12 and FIG. 13 are diagrams of two multimedia conferencing
arrangements (the FIG. 13 arrangement is a particular exemplary
embodiment, referred to herein as conference system 1000, which implements
illustrative multiple call control methods of the invention);
FIG. 14 illustrates the use of the connector and the virtual circuit in
sharing a character-based application program;
FIG. 15 illustrates the sharing of a graphical program by two parties;
FIG. 16-FIG. 24 illustrate various menus, window and icons for effecting
conference calls and merging and splitting operations in accordance with a
user interface for the conferencing arrangement of FIG. 13; and
FIG. 25 illustrates a two-phase protocol used for merging and splitting
multi-channel calls in the conferencing arrangement of FIG. 13.
DETAILED DESCRIPTION
Multicast Connections
FIG. 3 shows a multicast packet switching network which consists of
multicast packet switches (MPSs) and network interfaces (NIs).
To achieve high-speed transmission, the multicast packet switching network
is based on fast packet technology (described in J .J. Degan et al., "Fast
Packet Technology for Future Switches", AT&T Technical Journal, Vol. 68,
No. 2, p. 36-50, 1989), having the following attributes:(a) Link-by-link
error and flow control is eliminated. Thus, the required field in the data
link header is for the logical channel number (LCN), which is used for
routing packets through the multicast packet switching network. An LCN for
each link within a connection is decided at connection setup time; (b)
Edge-to-edge error control can be incorporated within the multicast packet
switching network on a per-connection basis; and (c) The multicast packet
switching network provides internal connection-oriented services that
support high-bandwidth applications very efficiently. In such networks,
the required link bandwidth and the end-to-end delay for a multicast
application are independent of the number of users. Also, the network
performance will not degrade as the number of users increases. These
advantages provide a solid foundation for the multicast packet switching
network as a vehicle for supporting various multicast applications,
especially, interactive multimedia multi-party conferencing.
A multicast packet switch is composed of a switch fabric, a switch
processor, and switch interfaces (SIs), as shown in FIG. 4. The switch
fabric is capable of duplicating an incoming packet and routing the copies
to desired outgoing ports. An exemplary multicast packet switch is
disclosed in the U.S. patent application of K. T. Teraslinna et al., Ser.
No. 07/412,952, assigned to the assignee of the present invention.
[Definition 2.1]: With multiple input streams each destined to multiple
outputs, a switch fabric is said to have
a. the weak sequencing (WS) property, if it only guarantees point-to-point
sequential transfer from each input port to any of its output ports; or
b. the strong sequencing (SS) property, if those output ports receiving two
or more common inputs have identical interleaved packet streams with
respect to the packet streams from the common input ports. For example, in
FIG. 5, the two subsequences of outgoing packet streams at switch
interfaces D and E (or switch interfaces E and F) containing {b.sub.i }
and {c.sub.i } (or {a.sub.i } and {b.sub.i }) are identical.
A multicast packet switch will be represented as w-MPS (or s-MPS) if its
switch fabric has the weak sequencing (or strong sequencing) property.
In general, different links within a multicast connection may use different
LCNs. Thus, each switch interface maintains a packet translation table
(PTT) and a multicast control table (MCT) to store routing information
about those multicast connections. Each entry of a packet translation
table, indexed by an incoming LCN, contains a multicast connection number
(MCN) and a switch header. On the incoming link, the MCN field stores the
MCN assigned to a multicast connection during connection setup. The switch
header identifies a set of outgoing links involved in a multicast
connection, which is used for packet duplication and routing through a
switch fabric. Each entry of the multicast control table, indexed by a
MCN, contains the LCN chosen for the outgoing link within a multicast
connection.
FIG. 6 illustrates the data packet switching process through a multicast
packet switch for a multicast connection. An incoming packet accesses the
packet translation table by LCN a at switch interface A. Switch interface
A then replaces LCN a in the packet header by the stored MCN m and
prepends the stored switch header to the packet for packet duplication and
routing. Each outgoing packet uses MCN m in its header to access the
multicast control table at the outgoing switch interface and obtains an
outgoing LCN. Switch interface B and switch interface C then replace MCN m
in the packet header by LCN b and LCN c, respectively. Finally, the switch
header of each outgoing packet will be stripped off at the outgoing switch
interface before it leaves.
[Lemma 1]: Any arbitrary data packet flow pattern (DPFP) within a multicast
packet switch can be achieved.
<Proof>: Given a set of switch interfaces, with an LCN chosen for each
switch interface, it is clear that the direction of data packet flow among
these switch interfaces can be controlled by writing suitable information
into their packet translation tables and multicast control tables.
FIG. 7 illustrates three natural data packet flow patterns within a
multicast packet switch: (a) point-to-multipoint, (b) point-to-mulitpoint
with upstream capability, and (c) multipoint-to-multipoint. They will be
referred to as pattern-1, pattern-2 and pattern-3 data packet flow
patterns, respectively.
The switch processor (FIG. 4) establishes and disconnects switched
multicast connections across the multicast packet switching network.
A network interface (FIG. 3) provides an access point to the multicast
packet switching network for various networks and equipments, e.g., user
stations, connected to it. It is responsible for protocol/speed
conversion, packet assembly/disassembly, signaling, etc. It also provides
an edge-to-edge flow/error control across the multicast packet switching
network on a per-connection basis.
A source-based multicast routing method is used to perform multicast
connection setup. This method can be applied to both switched multicast
connection setup and multicast connectionless packet routing.
For each multicast packet switch in the multicast packet switching network,
several spanning trees rooted at this multicast packet switch are
generated. A unique global tree number (TN) will be assigned for each
tree. Based on these trees, multicast routing tables (MRTs) are
established at each multicast packet switch during network initialization.
The size of the multicast routing tables depends on the number of
multicast packet switches in the multicast packet switching network and
the number of trees. Therefore, a tradeoff between the number of trees and
memory space required at each multicast packet switch is made. These
tables may be updated dynamically. However, it should be done
infrequently. The advantage of using multiple spanning trees is to provide
alternate multicast routes such that the connection completion rate can be
improved. Under normal situations, the connection control packets for
establishing or disconnecting a connection progress forward from the
source multicast packet switch to the next destination multicast packet
switches. They may need to crankback to the source multicast packet switch
for finding alternate spanning trees when some multicast packet switch
belonging to the chosen spanning tree rejects the new connection setup for
some reason.
The basic connection setup procedure is as follows. When a connection setup
packet arrives at the source multicast packet switch, the switch processor
chooses a tree number, among a set of tree numbers which correspond to
those spanning trees rooted at this multicast packet switch, based on a
load sharing method. Based on the destination set in the packet and the
multicast routing table indexed by the chosen global tree number, the
switch processor checks if the appropriate necessary and sufficient
conditions described in detail herein are met to determine whether the
multicast connection that would be established would be usable to effect
communication in accordance with a specified transmission matrix and
meeting a given packet sequencing condition. If the check is positive, the
switch processor then partitions the destination set into several subsets;
each subset will use a different outgoing link. By putting the chosen tree
number in the packet and masking off all other destination addresses in
the destination set except those in the corresponding subset, a modified
copy of the original connection setup packet is then generated and sent to
each desired outgoing link. In addition, the switch processor will choose
an available multicast connection number (MCN) and send signal packets to
update the translation tables in each involved switch interface. When the
modified packet reaches the next multicast packet switch, the switch
processor uses the tree number in the packet to index a multicast routing
table, does some necessary checking, and then further partitions the
destination subset. This procedure repeats until all the destinations are
reached.
The concept of multicast connections is a natural extension of that of
point-to-point connections. That is, a multicast connection is a logical
association among a set of network interfaces over which all packets
following the same route, need not carry complete destination addresses
and arrive in sequence. Based on different requirements, four flavors of
multicast connections are defined over an arbitrary multicast packet
switching network: vanilla multicast connections (VMCs), multicast virtual
circuits (MVCs), strong multicast connections (SMCs) and strong multicast
virtual circuits (SMVCs). Roughly speaking, vanilla multicast connections
and strong multicast connections only provide network-layer
connection-oriented services to the users, and packet loss is allowed.
They depend on the users' transport layer to execute error control, if
necessary. On the other hand, multicast virtual circuits and strong
multicast virtual circuits provide network-layer virtual circuit services
to the users, which ensure reliable packet transfer. Therefore, error
control in the transport layer is not necessary.
Four flavors of multicast connections are defined on acyclic subgraphs of
the graph representing a multicast packet switching network. Acyclic
subgraphs guarantee that each multicast connection contains no loop and
every packet will reach its destination(s) in finite time and low delay.
[Definition 3.1]:
a. An arbitrary multicast packet switching network is represented by a
graph G={S, E, L}, where S is the set of all multicast packet switches, E
is the set of all network interfaces, and L is the set of all links.
b. G={S, E, L} represents an acyclic subgraph of G, which interconnects all
network interfaces in a subset E of E via a subset S of S and a subset L
of L. Any link 1 in L cuts G into two disjoint subgraphs G.sub.1,u and
G.sub.1,d. Let E.sub.1,u and E.sub.1,d be two disjoint subsets of E, which
contain those network interfaces in G.sub.1,u and G.sub.1,d, respectively.
c. Each network interface contains a sender component (SC) and a receiver
component (RC) that sends and receives packets, respectively. Let SC i and
RC i represent the sender component and the receiver component of network
interface i, respectively.
Consider an arbitrary acyclic subgraph G of G. According to Lemma 1, with
an LCN chosen for each switch interface, any arbitrary data packet flow
pattern within each multicast packet switch in S can be achieved.
Interconnection of these individual data packet flow patterns via the
links in L constitutes a data packet flow pattern on G. The flow direction
on each link is determined by two individual data packet flow patterns at
its ends. With a data packet flow pattern within each multicast packet
switches being exemplified, link 3 has a bidirectional flow in FIG. 8(a)
and a unidirectional flow in FIG. 8(c). The corresponding transmission
matrices are given in FIG. 8(b) and FIG. 8(d).
[Lemma 2]: Given a G, any data packet flow pattern constructed on G has the
following properties:
a. Only a single LCN is associated with each link in L.
b. The data packet flow pattern satisfies the weak sequencing (WS)
condition, that is, point-to-point sequential packet transfer from any
network interface in E to each of its receiving network interface(s) is
guaranteed.
<Proof>: (a) is clear since, during the construction of a data packet flow
pattern on G, a common LCN can be chosen for the two switch interfaces at
ends of each link in L. (b) holds since each multicast packet switch has
at least the weak sequencing property.
[Definition 3.2]:
a. Given a E, the sending/receiving relationship among all network
interfaces in E is represented by a N-by-N transmission matrix: TM(E),
where N is the number of network interfaces in E. TM(E)[i,j] is 1 if RCj
receives packets from SC i, and 0 otherwise.
b. Given two subsets X and Y of E, the submatrix TM(X,Y) is obtained from
TM(E) by retaining only those sender components in X and only those
receiver components in Y. Let TM(E.sub.1,u, E.sub.1,d) and TM(E.sub.1,d,
E.sub.1,u) be represented by TM.sub.1,u,d and TM.sub.1,d,u, respectively.
Given a data packet flow pattern on G, a TM(E) can be easily obtained by
tracing data packet flows from each network interface in E.
By imposing different requirements on data packet flow patterns on G, four
flavors of multicast connections are defined.
[Definition 3.3]: Given a G, a data packet flow pattern on G is a vanilla
multicast connection, if it satisfies the multicast condition: There
exists at least one network interface in E from which the packet stream is
destined to two or more network interfaces in E. These network interfaces
are referred to as multicast sources (MSs). The representation VMC(G) will
be used to show the relationship between a vanilla multicast connection
and its associated G.
The multicast condition implies that: (1) At least one multicast packet
switch in S will duplicate packets; and (2) The TM(E), obtained from any
VMC(G), has at least one row containing two or more 1's. From this point
on, only TM(E)'s having at least one row containing two or more 1's are
considered. Given a G, a TM(E) with the weak sequencing condition may not
be satisfied by a VMC(G).
[Theorem 3.1]: Given a G, a TM(E) with the weak sequencing condition can be
satisfied by a VMC(G), if and only if it has the following VMC property:
For any link 1 in L, if TM.sub.1,u,d (or TM.sub.1,d,u) contains two or
more non-zero rows, these rows must be identical. In other words, every
sender component in E.sub.1,u (or E.sub.1,d) sending packets to the
receiver components in E.sub.1,d (or e,ovs/E/ .sub.1,u) must have
identical destination subsets of E.sub.1,d (or E.sub.1,u).
<Proof>: The sufficient condition is shown by contradiction. Assume that
there exists a link 1 in L so that TM.sub.1,u,d contains different
non-zero rows. This implies that there exist sender components e.sub.1 and
e.sub.2 in E.sub.1,u and receiver components e.sub.3 and e.sub.4 in
E.sub.1,d such that TM({e.sub.1, e.sub.2 }, {e.sub.3, e.sub.4 }) is either
FIG. 9(a) or (b). In FIG. 9(a), SC e.sub.1 sends packets to both receiver
component, e.sub.3 and e.sub.4, and SC e.sub.2 only to RC e.sub.3. In FIG.
9(b), SC e.sub.1 only sends packets to RC e.sub.3, and SC e.sub.2 only to
RC e.sub.4. Since G is an acyclic graph, there exists a MPS s in G.sub.1,d
so that packet flows from SCs e.sub.1 and e.sub.2 will enter its switch
interface A via link 1, as shown in FIG. 9(c), and packet flows destined
to RCs e.sub.3 and e.sub.4 will leave from switch interfaces B and C,
respectively.
With a single LCN associated with link 1, packets from SCs e.sub.1 and
e.sub.2 will have the same LCN in their headers when they are sent over
link 1. Since one LCN only indexes one entry in the packet translation
table of switch interface A, packets with the same LCN cannot be
duplicated and routed to different subsets of outgoing switch interfaces.
Therefore, the desired data packet flow pattern within MPS s to support
the submatrices in FIG. 9(a)-(b), can not be achieved. This implies that
the TM(E) can not be implemented by any VMC(G). The above conclusion is
also true when TM.sub.1,d,u contains different non-zero rows.
Next the necessary condition is proved. Let E.sub.u,1 and E.sub.d,2 (or
E.sub.d,1 and E.sub.d,2) be two subsets of E.sub.1,u (or E.sub.1,d), so
that TM(E.sub.d,1, E.sub.u,1) (or TM(E.sub.u,2, E.sub.d,2)) contains all
the 1's in TM.sub.1,d,u (or TM.sub.1,u,d). The corresponding packet flow
models of TM(E.sub.d,1, E.sub.u,1) and TM(E.sub.u,2, E.sub.d,2) are shown
in FIG. 10, in which MPSs s.sub.1 and s.sub.2 both have pattern-1 data
packet flow patterns. Let LCN n be chosen for link 1, then packets from
each sender component in E.sub.u,2 and E.sub.d,1 will use LCN n when they
are sent over link 1. To achieve these two data packet flow patterns, let
the routing field in the switch header entry of the packet translation
table at switch interface A (or SI B, resp.), indexed by LCN n, identify a
set of outgoing links from which packets are transmitted to the receiver
component in E.sub.u,1 (or E.sub.d,2).
Three natural vanilla multicast connections over the multicast packet
switching network are given below.
a. Point-to-multipoint (Pattern-1): There is only one multicast source and
each multicast packet switch in the vanilla multicast connection has
pattern-1 data packet flow pattern.
b. Point-to-multipoint with upstream capability (Pattern-2): There is only
one multicase source and each multicast packet switch in the vanilla
multicast connection has pattern-2 data packet flow pattern.
c. Multipoint-to-multipoint (Pattern-3): In this vanilla multicast
connection, each network interface is a multicast source and each
multicast packet switch has pattern-3 data packet flow pattern.
Most data applications require reliable communication. To provide a
network-based edge-to-edge reliable service to those multicast
applications that require completely error-free transmission and that do
not employ some higher-layer error control protocol, the multicast virtual
circuit is introduced.
[Definition 3.4]: A multicast virtual circuit is a vanilla multicast
connection which also satisfies the reliable condition: Point-to-point
reliable packet transfer from any network interface to each of its
receiving network interfaces is guaranteed.
There are two issues associated with a multicast virtual circuit.
1. Since a vanilla multicast connection may have multiple senders, a
multipoint-to-multipoint error control protocol must be exercised among
all network interfaces.
2. Given a TM(E) with the vanilla multicast connection properties, a VMC(G)
can be set up to meet the desired information flow relationship among
users. However, this VMC(G) is only concerned with transmission of data
(or information) packets, and there may not exist paths in it for
returning acknowledgements (ACKs).
One approach to address the second issue is described below. If the VMC(G)
of a given TM(E) also provides paths for returning acknowledgements, it
will be used to transmit both data and acknowledgements. Otherwise, a a
TM'(E) is obtained, where TM'(E)[i,j] is 1 if TM(E)[i,j] or TM(E)[j,i] is
1. If the TM'(E) still has the vanilla multicast connection properties, a
new VMC(G) is then set up to support the desired information flow
relationship represented by the TM(E) and provide necessary
acknowledgement paths. In both cases, some network interfaces may receive
undesired data packets and/or acknowledgements. Therefore, two address
fields--the addresses of the sending network interface and the receiving
network interface--are reserved in the error control header so that each
network interface can discard undesired incoming packets. The second field
is used only by the acknowledgements.
A vanilla multicast connection and a multicast virtual circuit are not
concerned with the sequencing relationship across multiple senders.
Although most multicast applications can be supported by a vanilla
multicast connection or a multicast virtual circuit, some multicast
applications may request the multicast packet switching network to provide
a multicast service which maintains the sequencing relationship across
multiple senders. A strong multicast connection and a strong multicast
virtual circuit are introduced to provide a network-based strong
sequencing mechanism to those multicast applications that require strong
sequential transmission and that do not employ some higher-layer strong
sequencing protocol.
[Definition 3.5]: A vanilla multicast connection is a strong multicast
connection, if it also satisfies the strong sequencing (SS) condition: the
sequence of packet streams arriving at a set of netwo | | |
