Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
WO92/21186 PCT/US91/0~1~
210g63~
Method of and S~stem for Accessina Distributed
Resources on ISDN
Technical Field
The invention relates generally to Integrated
Services Digital Networks (ISDN), and more
particularly, to accessing from one computer data and
applications resident at other computers distributed on
an ISDN.
Backaround Art
Small computers such as 'personal computers
ordinarily operate as a stand alone device, carrying
out information processing based on programming and
data stored locally on a floppy or hard disk or in
emiconductor memory media. Data can be transferred
among computers digitally by cables connected to input-
output ports of the computers or to commercial
telephone lines or other physical media following
digital-to-analog conversion by modems. Computers also
can be interconnected in a local area network (LAN),
~sharing common resources such as data bases, files and
programming, and peripheral devices, e.g., printers.
Accessing from one computer a resource of another
computer on a common network is not done
--transparently", i.e., a computer having a desired
resource must be accessed before the resource
~ sssociated with it is accessed. The user accordingly
-~ 25 must have knowledge of the location of the resource on
the Network.
For example, referring to Figure l, a plurality of
terminals T are coupled through modems M to a network.
WO92/21186 PCT/US91/03615
2109635
Each terminal T comprises a personal computer PC and an
optional telephone unit TEL to enable the user to carry
out voice communications with other terminals on the A ,'~
line. The computers PC, which are controlled by a
common operating system, such as MS-D0S, contain data, -
applications and peripheral devices, hereinafter
collectively called ~resources~', that are accessible
through operating system commands. An example is a
floppy or hard disk drive unit DS residing at each
computer PC.
Assume that a local com~uter contains two disk
drive units DSA and DSB, a floppy disk drive and a hard
- disk drive. To copy all data stored on disk drive unit
DSA to drive unit DSB, the operating system command in
lS MS-DOS is:
copy DSA:*.* DSB:
Conventionally, the operating system enables
multiple resources to be accessed by a computer.
However, no sharing of resources among different ;~
computers is possible unless the computers are
programmed to operate as ~master-slave~ units. Remote
access software, such as ~pcANYWHERE~, by Dynamic
Microprocessor Associates, Inc., is an example of
commercially available software for this purpose.
Resource sharing requires each computer on the Network
to be loaded with, and executing, the remote accesses
software.
Files can be transferred between computers using
conventional file transfer software, such as
"SMARTCOM", by Hayes Microcomputing, but file transfer
requires operator attendance at each terminal.
WO92/21186 PCT/US91/03615
3 21 ~ g ~3~:~
The present invention is directed to a router that
pro~ides resource sharing among computers standing
alone or residing in local area networks LANs without
operator attendance at the "slave~' terminal.
S Communications between computers is transparent,
enabling the user to access distributed resources
without knowledge of the locations of the resources on
the Ne~work.
The invention is carried out in the environment of
ISDN. ISDN is a relatively newly developed and
emerging field of telecommunications which integrates
computer and communications technologies to provide,
worldwide, a common, all-digital network. This is
based, in part, on standardizing the structure of
digital protocols developed by the International
Telegraph and Telephone Consultative Committee (CCITT).
Despite implementation of multiple networks within
national boundaries, from a user's point of view there
is a single, uniformly accessible, worldwide network
capable of handling a broad range of telephone, data
and other conventional and enhanced services. The
invention, carried out on the ISDN, will enable
terminal resources to be shared globally.
A complete description of the architecture of ISDN
is beyond the scope of this specification. For
details, and for an extensive bibliography of
references of ISDN, see Stallings, ISDN: An
Introduction, MacMillan Publishing Company, 1989.
Copending application Serial No. , to
Gagliardi et al., entitled "Dynamic Channel Allocation
Method and System for Integrated Services Digital
Network," filed by the assignee of this invention,
provides a background discussion of ISDN features that
W~92/211~ PCT/US91/0~15 -;~
210963~
are germane to the present invention, and is
incorporated herein by reference.
To establish communications between a host and the
ISDN, an interface, or "relay~, must be implemented to
accomplish gateway functions, translating protocols
used on dissimilar networks. A relay of a type termed a
"bridge" forms interconnections at the data-link layer
of the OSI Reference Model. A "router" functions at
the network layer, and a "gateway handles higher-
level protocols.
An ISDN router, designated by R in Figure 2,
operates entirely in the digital domain, carrving out
all necessary protocol conversion between the host
network and ISDN. Details of the router R are given in
copending application Serial No. , to
Gagliardi et al., entitled "ISDN Interfacing of
Personal Computers,' filed by the common assignee on
even date herewith and incorporated herein by
reference.
Copending application Serial No. , to
Gagliardi et al., entitled "ISDN Interfacing of Local
Area Networks," filed on even date herewith and
assigned to the common assignee, describes a router
supporting interconnections among hosts on the ISDN to
2S form a "virtual" LAN. A local area network, or LAN,
provides a cluster of interconnected hosts (computers),
or nodes, on a medium. Each node can communicate with
every other node; the Network requires no central node
or computer.
Figure 3 depicts utilization of one type of router
described in the aforementioned copending application
(LAN connector) for interconnecting a number of hosts
to form a virtual B-channel LAN. A variation, shown in
Fig. 4, provides ISDN routers R to interconnect to LANs
WO92/21186 PCT/US91/0361~
210~S3 ~
of a common type or of different types. In Fig. 5, a
remote host H is connected to a pair of hosts residing
on a LAN through first and second routers at the host
and LAN branches of the ISDN. The host side router Rl
is of a type described in the copending application
entitled "ISDN Interfacing of Personal Computers." The
LAN side router R2 in Fig. 5 is of a type described in
the copending application entitled ~ISDN Interfacing of
Local Area Networks.'l
Copending application Serial No. , to
Gagliardi, entitled "Dynamic Channel Allocation Method
and System for Integrated Service Digital Network",
describes an ISDN router that dynamically allocates
bandwidth by monitoring traffic at each destination
queue and in response allocates or deallocates Yirtual
B-channels. Bandwidth utilization is optimized by
packaging data packets into trains that are transmitted
to the destination when the train is completed and upon
satisfaction of other conditions. Each train undergoes
data compression by execution of a suitable compression
algorithm.
Relays exist for allowing communication to an ISDN
line. For example, U.S.P. 4,885,739 describes a message
trahsport network at a central office, including
gateways connected to a transport node controller or
transport interchange supervisor to enable
communication between internal processors. U.S.P.
4,821,265 describes a nodal architecture for a
communication network including multiple processors for
each node to carry out a Data Link Layer process on a
D-channel message received through a bridge (termed a
"gateway" in the patent). Howe~er, no prior art is
known to enable ISDN users to share terminal resources,
WO92/21186 PCT/US91~03615
2109635
such as data storage disks, transparently from any
terminal on the Network.
Disclosure of the Invention
Accordingly, one object of the invention is to
control access to resources distributed on an ISDN.
Another obje~t is to enable a user at one terminal
to con~rol transparently resources distri~uted among
other terminals on an ISDN.
A further object is to enable a user at one
personal computer to access transparently a resource of
another personal computer on the ISDN.
A further object is to enable a user at one
terminal of an ISDN to access a data storage disk of
another terminal of the ISDN using operating system
1~ commands.
Another object is to enable one computer, that
either stands alone or is a node of a LTA, to access
transparently a resource, such as a storage disk, of
another computer.
Still another object is to provide an ISDN router
enabling one computer, that either stands alone or is a
node of a LTA, to access transparently a resource, such
as a storage disk, of another computer via the ISDN.
Another object is to provide an ISDN routex
enabling one computer, that either stands alone or is a
node of a LTA, to access a resource, such as a storage
dis~, of another computer using operating system
commands.
A further object of the invention is to implement
efficient bandwidth utilization while carrying out
communications between computers on the ISDN to achieve
the foregoing objects.
WOg2/21186 PCT/US91/O~15
7 2 1 09 63~ï
The above and other obje~ts are satisfied in
accordance with o~e aspect of the invention by a
network comprising a plurality of computers having a
common operating system, means for interfacing the
s computers to a common ISDN line and means for
transmitting an operating system command on the ISDN
line, globally to all of the computers.
Preferably, the computers incorporate resources,
such as data storage disks, each having a unique name,
and the operating system command transmitted globally
on the ISDN line accesses by name a resource associated
with one of the computers. Access to any resource
available on the ISDN line is transparent to the user.
In accordance with another aspect of the
lS invention, a network comprises a LTA of computers
having a common operating system, a computer remote
from the LTA and having the common operating system,
and means for interfacing the remote computer and the
LTA to a common ISDN line. Any operating system command
by the remote computer is transmitted on the ISDN line
globally to all of the computers in the LTA.
In accordance with still another aspect of the
invention, resources available at any te~.inal are
shared among terminals of multiple LTAs distributed on
the ISDN. In a preferred embodiment, a network includes
a first local area network LANl comprising computers
having a common operating system, a second local area
network LAN2 of computers remote from the first LAN and
having the common operating system, and means for
interfacing the first and second local area networks to
a common ISDN line. Operating system commands on the
ISDN line from one computer in the first LAN are
transmitted globally to all other computers in the
W O 92/21186 PC~r/US91/0361~
2109635
first and second local area networks to share terminal
resources.
A further aspect of the invention involves
improving bandwidth utilization of the ISDN line while
sharing terminal resources. A B-channel allocation `
algorithm executed by routers between the terminals and
the ISDN line dynamically allocates bandwidth by
moni~oring traffic at each destination queue and in
response allocating or de,allocating virtual B-channels.
Bandwidth utilization is optimized by packaging data
packets into trains that are transmitted to the
destination when the train is completed and upon
satisfaction of other conditions. Each train undergoes
data compression by execution of a suitable compression
algorithm. ''
Still other objects and advantages of the present
invention will become readily apparent to those skilled
in this art from the following detailed description,
wherein only the preferred embodiment of the invention
are shown and described, simply by way of illustration
of the best mode contemplated of carrying out the
invention. As will be realized, the invention is
capable of other and different embodiments, and its
several details are capable of modifications in various -
o~vious respects, all without departing from the
invention. Accordingly, the drawing and description
are to be regarded as illustrative in nature, and not
as restrictive.
Brief Descri~tion of Drawin~s
Figure 1 is a diagram of a network of computer
sharing a network in a conventional manner.
WO 92/21186 PCI/US91/03615
21 09 G3;~
Figure 2 is a symbolic diagram of a network
implementing routers described in a copending
application to interface computers to the ISDN.
Figure 3 is a symbolic diagram showing
5interconnection of multiple hosts through ISDN routers
to form a virtual network, described in a copending
application.
Figure 4 is a symbol~c diagram showing
interconnection of LANs through ISDN routers described
10in another copending application.`
Figure 5 is a symbolic diagram showing
interconnection of a remote host to an existing LAN
through ISDN routers.
Figure 6 is a diagram depicting resource sharing
15on an ISDN line in accordance with a broad aspect of
the invention.
Figure 7 is a simplified block diagram showing the
hardware architecture of an ISDN router implementing
resource sharing in the manner shown in Figure 6.
20Figure 8 is a diagram of software architecture
incorporated in the system master card of Figure 7.
Figure 9 is a diagram of software architecture
shown in one embodiment of a LAN line card of Figure 7.
Figure 10 is a diagram showing software
25architecture incorporated in an ISDN line card depicted
in Figure 7.
Figure ll is a diagram of software architecture
incorporated in the S~LC line card shown in Figure 7.
Figure 12 is a diagram showing mapping of software
30to hardware components within the ISDN router.
Figure 13(a)-(b) depict examples of terminal
resource sharing on the ISDN carried out in accordance
with the invention.
WO92/21186 PCT/US91/0~15
2109635 lO --
Figure l4 is a flow chart of algorithms for
carrying out LTA bandwidth allocation in accordance
with an aspect of the invention.
Figure 15 is a flow chart of algorithms for
selecting between LTA and STA channel allocation.
Figure 16 is a flow chart of channel processes
responding to decisions made by both the LTA and STA
cAannel allocation algorithms.
Figure l7 is a diagram showing development of a
virtual B-channei and its components.
Figure 18 is a diagram of components for carrving
ou_ LTA channel a~loc~tion in accordance with anothe~
aspect of the invention.
Figure 19 is a flow chart describing assembly an~
l~ compression of packet trains for transmission to a new
B-channel.
~ igure 20 is a flow chart showing reception,
decompression and resequencing of packets.
Figures 21a and 21b are diagrams respectively of a `
packet and a data frame.
Figure 22 depicts a train of packets in accordance
with a further aspect of the invention. -
.
2S
BEST MODE FOR PRACTICING THE INVENTION
Ov:erview
The invention provides user transparent sharing of
terminal resources through the ISDN. Resources at any
terminal on the ISDN are identified by unique names.
~or example, each hard disk associated with every`
computer on the ISDN is assigned a uniaue volume name.
The hard disk can be accessed from any computer on the
~.
WO92/21186 PCT/US91/0~15
ll 21~
ISDN line using an operating system command identifying
the disk by volume name. The location of the disk on
the Network is inconsequential to the user; hence,
access to the disk by the user is "transparent". "
For example, assume that a disk containing data of
interest resides with a computer at a remote location
on the ISDN line. The disk of interest is assigned the
unique ~olume name ABCDE, and the disk of the local
computer is assigned the volume name s. The content of
this disk can be copied to disk B of the local computer
by applying globally to the ISDN line the following
operating system command:
copy ABCDE~ *.* B:
As shown in Fig. 6, the above command is applied ;~
to all terminals on the ISDN. The content only of disk
A3CDE will be transferred from that disk at the
corresponding remote computer through the ISDN to disk
B of the local computer from which the command was '~
executed.
Of particular importance to the process is the
quality of '~transparency" to the user of the local
c~mputer. That is, the user at the local-computer has
no prior knowledge of the location of the computer
containing the desired resource; he can access the
resource from any location in t,h,e world subscribing to
-~ the ISDN service and implementing the present
invention, based only on the resource name and
knowledge by the user of operating system commands.
How this capability is implemented is described in
-~ 30 detail hereinafter.
-:
WO92/21186 2 1 0 9 6 3 5 12 PCT/US91/0~15
2. Network Architecture
Referring to Figure 7, an ISDN gateway 100, in
accordance with the invention, comprises four hardware
elements 102, 104, 106, 108 interconnected by a common
bus 110. The elements 102-108 preferably comprise
individual circuit cards, although some or all of the
elements may be incorporated in a single circuit board.
The board or boards preferably reside within a personal
computer but alternatively may reside outside the
computer.
Element 102 is a system master which implements
infrequent user functions, such as configuration
mana~ement and connection requests. The system master
102 furthermore functions as a standard computing
platform, emulating an IBM compatible PC or other
computer standard.
LAN line card 104 implements firmware and hardware
for specific IEEE 802 physical and data link protocol
together with software carrying out host filtering.
Different LAN line cards with corresponding protocols
will be re~uired for other LAN connections, e.g., 802.5
Token Ring and 802.3 Ethernet.
ISDN line card 106 comprises firmware and hardware
implementing the ISDN physical, data link layer (LAPD),
and the D-channel layer 3 protocol, and the physical
layer of the B-channel. Software incorporated in the
ISDN line card 106 implements train protocol and B-
channel allocation algorithms as well as data -
compression algorithms to support a virtual broad band
capability of the router, described in the copending
application entitled "Dynamic Channel Allocation Method
and System for Inteqrated Services Digital Network,
incorporated herein by reference.
WO92/21186 PCT/US91/0~15
13 2 1 ~
SDLC line card 108 includes firmware and hardware
to implement the SNA physical and data link (SDLC)
layers. This card is optional to the Network.
The contents of elements 102-108 are described in
more detail below with reference to Figures 8-12.
Hardware and software incorporating important aspects
of the invention are integrated in ISDN line card 106.
3. Software Architecture
The software architecture of system master element
102, shown in Figure 8, is configured with three layers
of software underlying the system master 102(b) in a
stack. The underlying layers comprise call request
management, configuration management and monitoring
layer 102(b), as well as layers 102(c), 102(d) for
implementing a computing platform.
In Figure S, the software architecture of one
embodiment of a LAN line card (LLC) 104 for 802.S Token
Ring comprises a functional layer 104(a) together with
a layer 104(b) comprising a host filter, receiving and
selectî~ely processing pac~ets addressed to the host,
as well as underlying layers 104(c), 104(d)
implementing the specific IEEE 802 physical and data
link protocol (802.5) for Token Ring.
In Figure 10, the sof~tware architecture of the
ISDN line card 106 comprises a functional layer 106(a),
together with underlying layers 106(b)-106(f) for
carrying out the requirements of the OSI Reference
Model layers associated with the ISDN. Theæe layers
include a communication mode adapter at layer 106(b~
and protocol services at layer 106(c). Layer 106d
(IIM) carries out router peer protocol and executing
buffer allocation algorithms to be described in detail
later. The peer protocols, applied on B-channels used
W O 92/21186 PC~r/US91/03615 2109635 14
~y the router to implement train pac~ing, compression
and error handling, is also described later. Figure 11
depicts the software architecture of the SDLC line card
implementing the SNA physical and data link layers for
s carrying out inter-networking among hosts.
Mapping of software architecture shown in ~igures
8-ll to hardware` components of Figure 7 is symbolized
in Figure 12. Details are given in the copending
application entitled "Dynamic Channel Allocation Method
and System for Integrated Services Digital Network.
4. Terminal Resource Sharin~ ExamPles
Referring to Figure 13(a), a network comprises a
LAN of computers PC having a common operating system,
and a computer PC1 remote from the LAN and having the
common operating system. A relay Rl of a type disclosed
in the copending app~ication entitled "ISDN Interfacing
of Personal Computers" performs gateway functions
between the remote computer PCl and the ISDN, and
another relay R2 of a type disclosed in the copending
application entitled "ISD~ Interfacing of Local Area
Networks,'` gateways the LAN to the common ISDN line.
Any operating system command by the remote computer PCl
is t~ansmitted on the ISDN line globally to all of the
computers PC in the LAN. For example, as shown in Fig.
2~ 13~a), the user of remote computer PCl applies to the
ISDN an operating system command to copy the content of
hard disk ABCDE of computer PC4 on LAN to disk B of the
remote computer. The operating system command undergoes
protocol conversion and transfer by router Rl to the
ISDN. The ISDN message then undergoes another protocol
conversion and transfex to the LAN by router R2, where
the command is routed to computer PC4 and disk ABCDE.
The designated content of disk ABCDE is now read and
WO92/21186 PCT/US91/03615
lS 2 1 0~ 63'~
transferred, via PC4, LAN, ISDN, and PCl, to disk B,
undergoing necessary protocol conversions by routers Rl
and R2.
In Figure 13(b), a network includes a LANl
S comprising computers PCl-^3 having a common operatin~
system, and a LAN2 of computers PC4-6 remote from the
first LAN and having the common operating system. A
relay R2 of a type disclosed in the copending
application entitled "ISDN Interfacing of Local Area
Networks, gateways the first local area network LANl
to the common ISDN line and another like relay R2
gateways the ISDN to the second local area network
LAN2. Operating system commands on the ISDN line from
one computer PCl in LANl are transmitted globally to
all other computers in the first and second LANs to
share terminal resources.
For example, as shown in Fig. 13(b), the user of a
local computer PCl applies to LANl an operating system
command to copy the content of hard disk ABCDE of
computer PC4 on LAN2 to disk B of the local computer.
The operating system command identifies the volume name
of disk ABCDE, not the location of the disk in on the
Network. The operating system command on LANl
undergoes protocol conversion and transfer by router R2
to the ISDN. The ISDN message then undergoes another
protocol conversion and transfer to LAN2 by router R2,
where the command is routed to computer PC4 and disk
ABCDE. The designated content of disk ABCDE is now
read and transferred, via PC4, LAN2, ISDN, LANl and
PCl, to disk B, undergoing necessary LAN2-ISDN and
ISDN-LANl protocol conversions by routers R2.
Although two LANs are depicted as being connected
to the ISDN in the example of Figure 13(b), the number
of LANs in practice is arbitrary. Because the operating
WO92/21186 PCT/US9l/0~15
16
2109635
system command is applied globally to all computers on
all LANs connected to the ISDN and provided with
routers Rl and R2, resource sharing is transparent to
the user. ;
5. D~namic Bandwidth Allocation
A further aspect of the invention involves
improving bandwidth utilization of the ISDN line while
sharing terminal resources. A B-channel allocation
algorithm executed by routers between the terminals and
the ISDN line dynamically allocates bandwidth by
monitoring traffic at each destination queue and in
response allocating or deallocating virtual B-channels.
Bandwidth utilization is optimized by packaging data
packets into trains that are transmitted to the
destination when the train is completed and upon
satisfaction of other conditions. Each train undergoes
data compression by execution of suitable compression
and conrrection a~gorithms.
More specifically, B-channel allocation,
implemented by an allocation algorithm to maximize
utilization of the channels, minimizes response times
and the probability of losing data packets due to
buffer overf}ow. The channel allocation algorithm,
residing within the B-channel manager of IIM 116
2~ (~igure 12), includes commands to establish user-level
connections to destinations and to send and receiye
data. Data passed to the IIM 116 is queued in
destination ~ueues. The channel allocation algorithm
monitors the status of the destination queues, and
dynamically allocates ISDN channel bandwidth to these
queues. The, following definitions support the channel
allocation algorithm.
WO92/21186 PCT/USg1/03615
17 2109~3~
A "destination , which is a connection at the
router level, typically coincides with a physical
router. If peer protocol is compatible, all user-
level connections of various types, such as virtual
S circuit, modem connections, LAN, packets, etc., can
multiplex within the same router connection. If the
peer routers are incompatible, multiple router-level
connections to a single physical gateway are necessary.
Associated with each destination is a ~Idestination -
lOqueue", denoted as Q(d), consisting of a pool of
buffers. The pool of buffers for destination d
comprises the messages destined for d. The number of
buffers in Q(d) is denoted as b(d); it is assumed that
B-channels output from or input to a buffer in
15parallel, with each buffer having a fixed maximum size.
A number of B-channels currently allocated tO a
destination B is denoted as B(d). If a queue Q(d)
becomes too long relative to the number of channels
allocated to d, an extra channel is allocated. On the
20other hand, if Q(d) is relatively short compared to the
size of B(d), some channels are released. If no
buffers are available for accumulation of a new train
at a destination d, a "buffer fault" is created.
~ Events that define the length of a packet train
; 25trigger the invocation of the buffer allocation
algorithm. These events comprise packet arrivals at
ISDN line card 106 for transmission to the public
; network. There are four conditions that must be
considered:
30l. If a destination d is known, and Q(d) contains
an "open" buffer, that is, a buffer that is not filled
to the maximum length, the packet is accumulated into
the train.
WO92/21186 PCT/US91/03615
18
210963~ ~-
2. If the destination d is known, but no ~open~
buffer is available in Q(d), a new buffer is created
and a new train is started.
3. If the destination d is known, but an ''openl~
S buffer is about to fill up, the packet is accumulated
in the current open buffer. Thereafter, the buffer is
closed to seal the train.
4. If destination d is unknown, a new buffer pool
is started for a new train.
10The channel allocation algorithm, in accordance
with the invention, operates asynchronously to the
buffer allocation algorithm described previously. As
- one important aspect of the invention, the channel
allocation algorithm is partitioned into two
lS components, long term allocation and short term
allocation.
6. Lona Term Channel Allocation
Long term allocation LTA monitors the recent
historical track pattern to and from a destination, and
decides upon the bandwidth and types of channels to be
allocated to that destination. A short term allocation
STA monitors the current size of the destination queues
and the aging constraints of these queues, and decides
whether to deviate, temporarily, from decisions of the
long term allocation algorithm. This enables response
to situations that are not well-handled by long term
;allocation, e.g., situations arising due to a temporary
or sudden surge of traffic to certain destinations not
predicted based on the long term allocation algorithm.
Decisions on bandwidth allocation produced by the long
term and short term allocation algorithms preferably
are stored in memory, and are carried out at
W O 92/21186 PC~r/US91/03615 19 2109~3 ~
convenient intervals by ISDN channel processes to be
described later.
Channel allocation is described with reference to
B-channels, although similar allocation can be carried
out for D-channels as well. In general, B-channels can
be used in a circuit switched mode or in a packet
switched mode. The circuit switched mode preferably is
used only to transmit data between low-traffic
destinations in view of the relatively high set-up tear
down overhead required. The packet switched mode is
preferable for transmission to destinations with a low-
traffic rate if there is a moderate response time
requirement. For destinations that require higher
traffic rate or have more stringent response time
requirements, use of B-channels in the circuit switched
mode is preferable. For destinations that do not have
high traffic rate but have very stringent response time
requirements, the B-channels should be dedicated in the
circuit switched mode and deliberately underutilized.
The LTA algorithm i5 sun~arized in the flow chart
of ~igure 14. The traffic rate R at each destination
is monitored by a software flowmeter, which may be a
counter of data quantity arriving at the destination
queue within a particular interval of time. Each
software flowmeter is polled at fixed intervals (w)~
The flowmeter is read, then reset, and the reading is
used ~y the LTA to determine how many B-channels are to
be allocated to that destination.
One embodiment of a LTA algorithm, in accordance
with the invention, is as follows. Referring to Figure
14, step 150 reads a traffic rate R for a destination
d, wherein R is defined as follows.
r = Max {v_in (d, t-w, t)/w, v_out (d, t-w, t)/w},
WO92/21186 PCT/US91/0~15
2 10 9 63S ~ ~X~ 20
where t is the time when the meter is read, v_in(d, t-
w, t) is the accumulated input traffic volume for
destination d between time t and t-w, and v_out(d, t-w,
t ) is that for the output queue.
In step 152, an integer x, that is greater than or
equal to zero, is found such that:
x * hbw_cs < r s (x~l) * hbw_cs
and xB channels in circuit switched mode are allocated ~-
to destination d, where hbw_cs is the achievable
bandwidth once set up for a circuit switched mode B-
channel. This number in practice is close to 64Kbs.
Assuming that residual = r - x * hbw_cs, step 154
determines whether residual is greater than mbw_cs,
where mbw_cs is the minimum utilization of a circuit
switched B-channel, or whether the response time is
more stringent than moderate (step lS6). The term
"moderate" is defined to be the response time that can
be offered by a packet switched channel. If either
condition is true, than one more B-channel is allocated
to destination d (step 158). `
On the other hand, if 0 ~ residual ~ mbw_cs and
the response time requirement is moderate or more
relaxed than moderate, and traffic is suitable for
packet switched channels, a fraction of a packet
switched channel is allocated to destination d, wherein
the fraction f is determined as follows.
ebw_ps = effective bandwidth of a packet switched
channeI.
In step 160, if destination d is not reachable ~y
packet switched channels, or the packet is not of a
nature that is suitably transmitted through packet
switched channels, and the response time requirement is
very relaxed (step 162), then a fraction of a circuit
WO92/21186 PCT/US91/0~15
21 ~
~clOgC3~) ~
switched mode channel is allocated to destination d
(step 164). The fraction in this example is determined
by the size of the residual. The notation used in the
a~ove algorithm is as follows.
x, f: decision variables
t, r, residual: state variables
ebw ps, hbw_cw: ISDN performance profile
mbw_cs, w: algorithm control parameters
response time requirements for ~acket transmission:
tight: ' 260ms
moderate: between z seconds and 260ms
very relaxed: '= z seconds.
In addition, the algorithm is sensitive to the
transmission delay of packet switched channels and the
ISDN call set-up and tear down times for circuit
switched mode. The former is used to derive a boundary
between moderate and tight response times. The latter
is used to calculate the response times o~tainable for
time-shared fractional allocation of B-channels in
circuit switched modes, which in turn determines the
value of z which defines the boundary between moderate
and very relaxed response time requirements. The basic
logic of the algorithm remains unchanged under
different performance profiles.
An important algorithm control parameter is the
~meter window" w, which is selected such that the
algorithm is sufficiently sensitive to short-term
fluctuation in traffic intensity ~ut is not too
sensitive. If w is too small, a very short-termed
surge in traffic may result in too many B-channels
WO92/21186 PCT/USs1/0~15
- ~ 22
21~g63~
allocated and therefore will incur a high set-up tear
down overhead. If w is too large, the algorithm may
not be responsive enough to a short term search,
resulting in a fast destination queue build-up. An
excessive amount of buffer space may be consumed and ~
response time may be degraded. --
To attenuate sensitivity, a method using weighted
averaging of traffic in multiple windows i5 provided.
If a window system w with three windows wl, w2 and w3
is used, with weights wtl, wt2 and wt3, where the sum
of wtl - wt3 is unity, traffic rate r can be equated to
R(d, t, w,) computed as follows:
. .
R(d, w, t) - v(d, t-wl, t) / wl * wtl
; + v(d, t-wl-w2, t-w1) / w2 *wt2
+ v(d, t-wl-w2-w3, t-wl-w2) l w3 ~ wt3 ~
With this generalization, to allow the algorithm ~-
- to be more sensitive to short term fluctuation and less
to the long term pattern, wtl should be increased and
wt3 decreased, and vice versa. Multiple counters are
maintsined for each destination queue using this
strategy.
7. Short Term Channel Allocator
The~LTA algorithm functions well in cases where
there~are sufficient B-channels available and decisions
~, -:
made by the LTA are feasible. This means that the
~total number of B-channels allocated by the LTA is
smaller than the total number of B-channels subscribed,
and sufficiently smaller such that the probability that
an incoming call request finds all channels busy is
very small, and further that the recent past history in
fact represents a good basis for allocation. When such
WOg2/211~ PCT/US91/03615
23 . 210963~
conditions are not met, the STA algorithm must be
implemented.
In general, STA makes decisions which override,
temporarily, decisions made by LTA. Channel processes,
S described hereinafter, implement decisions made by LTA
under normal circumstances. When a B-channel is just
~freed" from servicing an input and output buffer, the
B-channel process checks to see if a decision has been
mnde to deallocate channels from the destination d.
If so, it deallocates itself and finds a new
destination for which a decision has been made by LTA
to have additional channels allocated. However, when
unusual conditions are detected, such as a destination
queue being ignored for too long, or a B-channel
process encountering an empty destination queue, self-
adjustment may be performed by the B-channel process to
execute decisions rendered by STA. Two examples to
which STA responds are ~1) if any buffer in the
:: destination queue d is found to exceed an age limit, or
:~ 20 (2)~ if the following quantity exceeds a relative queue
:~ size limit:
\ T (d
/ k
:- :
k (3)
~ 8~d
::- 30 ; Where:
T (d ) = size of kth train for
k i the ith destination
: ~ 8 (d ) = no. of B-channels
i assigned to the ith
~: 35 destinstion
The above relationship is satisfied when the quantity
~; of data in all trains to a particular destination
.
,
WO92/21186 PCT/US91/0~15
2109`6,~ 24
exceeds the number of B-channels asxigned to that
destination.
Logic implementing execution of the STA is shown
in figure 15, wherein step 170 waits until a B-channel
S is freed from servicing in the input buffer and the
output buffer, and then waits for an STA condition,
such as the two conditions previously described, to be
detected (step 172). LTA is implemented in step 174
unless the STA condition is detected. In response to
an STA condition, STA channel allocation is carried out
in step 176, and the process continues.
8. B-Channel Processes
An important aspect of the invention involves the
B-channel processes which respond to decisions made by
both the LTA and STA. Referring to Figure 16, channel
process invocation is triggered in response to end of
train transmission on any B-channel for input or output
traffic. There are three different cases for
reallocating a recently freed B-channel to release an
emptied buffer to a free buffer pool:
l. The first part of the channel process
algorithm at 180 prevents locking out trains associated
with low traffic rate destinations, or locking out
incoming call requests. Executing lockout prevention
at the first part of the algorithm eliminates
possibility of lockout. Since this part of the
algorithm tends to disturb stable allocations of B-
channels to high intensity traffic streams, probability
of invocation preferably is modulated inversely to the
number of B-channels assigned to the destination
associated with the just freed B-channel.
The probability of invocation is higher if the B-
channel is allocated fractionally to a high number of
WO92/21186 PCT/US91/0~15
i l
distinct destinations. Probability of invocation is
lower if more B-channels have been allocated to the
same destination. In other words, the higher the
traffic rate for a destination d, the lower the
S probability of causing a ~wild~ deallocation of one of
its B-channels to handle of locked out trains.
Sealed trains are time stamped. A check is made
by STA over the entire buffer pool for all destinations
to see if there are trains whase age exceeds a
predetermined age limit. If any are found, absence of
B-channels allocated to their destinations are checked
to confirm that trains are truly locked out. If such a
flag is found, the just freed ~-channel is associated
to all respective destinations, originating fractional
allocations of B-channels, the oldest locked out train
;~ is selected and transmitted. A condition wherein the
agè limit is set at a sufficiently high level, and if
overall traffic does not exceed the capacity of the
gateway is very rare. This condition must be rare to
avoid thrashing in the allocation of B-channels, and
must be handled as the first priority decision to avoid
bloc~ing trains associated with very low packet rates.
;2. If any complete train is waiting f or a
transmission to the same destination, in step 182 of
~the~ flow chart, the B-channel is re-used to transmit
~$t~ Giving priority to the~same destination re-use of
; the~8-ch~nnel minimizes~ ISDN call overhead.
3.~ ~If no complete train is waiting for
transmission toward the same destination, step 184, two
~subc~-es are considered. ~ In the first subcase, the
ust fr-ed B-channel is fractionally allocated to n
de-tinations. The remaining n-l destinations are
checked for waiting trains, and if one is found the
channel is assiqned to it for transmittal. This allows
:
~2 109 635 26 PCT/US91/03615
. ~ ,, .
maintenance of lstable~l pools of low traffic rate
destinations. If none are found, the following second
subcase is executed. If no complete train is waiting
for destination d sub_i, Flag_Queue_Size is checked,
and if set, a new destination d_sub_j is computed as
the one which contains the largest relative queue size.
Thereafter, the channel process remains with decisions
made by LTA.
9. Data Com~ression
Another aspect of the invention provides data
compression of packet trains, such as implementation of
algorithms based on run-length encoding and Huffman
encoding, and variations of Lempel-Ziv algorithms.
Run-length encoding refers to replacement of sequences
of identical source elements by a triple consisting of
a special code indicating a "run" of elements, a count
of the run length and the repeated element. Huffman
encoding translates fixed-sized source elements into
variable-sized codes, where the size of the output code
and bits is approximately the logarithm of the
probability of the source element. For some kinds of
data, the probabilities of elements are well known and
fixed translation tables are available. In more
general cases, where the distribution of source
elements is not known, a translation table can be
computed for a sum block of input data, and transferred ;~
alang with the ~data to allow decompression. This
requires two passes over the input during compression;
table size must be significantly smaller than the data
blocks.
The Lempel-Ziv algorithms convert variable-sized
input elements, or strings, into fixed-sized codes.
Allowing long input se~uences gives the possibility for
.
WO92/21186 ~. PCT/US91/03615
210963~
higher co~pression ratios than are possible with fixed-
size source element algorithms, such as Huf fman
encoding. The Lempel-Ziv algorithms are adaptive in
that translation tables are built dynamically to
reflect characteristics of the input, but require only
a single pass during encoding. Decompression can be
performed by dynamically building the same translation
tables as were used during compression, using
information implicit in the encoded data stream such as
whether a particular code has ~een encountered.
The typical ranges of compression ratios of a
compression algorithm selected to compress packet
trains vary from unity for certain kinds of inherently
random data such as floating point data or previously
compressed data, to eight for some data bases
containing large amounts of r~dundant or null data.
The average compression ratios over mixed input types
depends on the chosen samples, but ratios of between
two and four for fairly large samples of mixed input 20 found on real computer systems are comman; two is
proposed as an example in the preferred embodiment.
~ rror detection and correction, as a surrounding
protocol on compressed data to allow non-delivery of
corrupted blocks, is required since any errors lead to
catastrophic corruption of the rest of the packet
train. ISDN error rates appear to be similar to LAN
- error rates. No additional error handling mechanisms
are required above those that already exist in LAN
software. The D-channel has built-in error protection
by virtue of using the HDLC protocol which includes
error detection, packet sequencing and re-transmission.
In accordance with an aspect of the invention,
shown in Figure 18, a controller 170 comprises a
virtual B Allocator/Resource Manager 172 which opens a
21.0 9 6 ~.5. 28 PCT/US91/03615
. , . : ~ .
virtual s-channel with control attributes in table I,
below, from the B-channel pool as requested. Manager
172 also assigns a virtual B processor 174 implemented -~
from among a plurality of such processors, and handles
related supporting global resources. The virtual B
processors 174 at run time or initialization time
provide the service of transparent addition and
deletion of new or existing component channels in its
virtual B-channel based on virtual B attributes. The
processors 174 further provide transparent multiplexing
of client data. Virtual B-channel monitor 176 carries
out traffic and error monitoring of all virtual ~-
channels. Data traffic ~flow and allocation, day
allocation and replacement of channels to dynamically
alter ~andwidth are performed by the monitor 176.
Call set-up/disconnect processor 178 sets up and
disconnects protocol on the D-channel. Processor 178
interfaces to B-channel hardware to transform the B-
channel call set-up or disconnect, and interfaces with
the virtual 8 processors 174, resource manager 172 and
client. HDLC/LAPD links 180 provide the variable links
for clients, and are optional.
Component channels allocated for a virtual B-
channel have the following four defined states:
activated, deactivated, transien~ and steady. In the
deactivated state, data transfer is for~idden although
control protocol exchange is not. Component channels
allocated or joined are initially in the deactivated
state~ A channel, deactivated for a sender immediately
following the deactive_b command, described later, is
queued for transmission. For a receiver, a channel is
deactivated immediately after the command is received.
Only a bi-directionally deactivated channel is removed
WO92/21186 PCT/US91/03615
29 21
and physically disconnected from the virtual channel of
which it was a member.
In the activated state, both data and control
protocol transfer are permitted. A channel is
activated to a sender only after acknowledgement of the
active _b command transmitted is received. For a
receiver, a channel is activated immediately after this
command is received.
The transient state is defined by guarding periods
before acknowledgements are received from the far-end.
A virtual channel is transi,~ent when any component
channels are transient. No data can be sent over a
channel in the transient state.
A component channel is in the steady state if it
is not in the transient state, that is, if it is
activated or deactivated. A virtual channel is in the
steady state if all its components are in the steady
state.
A virtual B-channel is operative in two
multiplexing modes, restricted mode and forced load-
balancing mode. In the restricted mode,, data received
for transmission is sequentially distributed, one
packet at a time, in~a round-robin fashion over the
steady activated component channels; deactivated
channels are skipped. The f ar-end virtual 8 processor
174 receives and recovers data in the same round-robin
sequence. In the load-balancing mode of operation, the
distribution for transmissions over the channels
follows a protocol of most-empty-channel-first for
transmission. The receiver recovers it by the global
sequence numbers by scanning, comparing and carrying
out trace-back time-out presentation. During either
distribution process, active_b commands, described
below, are sent in-line on the deactivated component
WO92/21186 PCT/US91/0~15
21096~5 30
.. .., . ~. ~; .
channels. For component channels to be deactivated,
deactive_b commands are sent in-line over these
channels in place of the data in the sequence. Time-
fill SYNC_~B packets may be sent over channels in the
restricted mode of operation to avoid ~holes" in the
data stream, and further can be used for time control
in the load-balancing mode of operation.
l0. Control and Multi~lexinq
The following are the command categories and their
detailed format with bit defi,~itions. This protocol
assumes the use of flow control to be optional, at
least to some degree, depending on the implementation
and environment. In the restricted mode, this can be
controlled by client link level protocol; outstanding
transmissions preferably should not result in
difference of twenty-six generations or more between
the receiving and the far-end transmitting loop. The
load-balancing mode has the same format except that all
the numbered command category header-bytes described
below will be two bytes in length.
* DATA
Ossnnnnn: one byte as header of client~s data for
transmit.
* RQST_Bs
l0lnnnnn: one byte header of one or multiple control
bytes. The first control byte can further specify
explicitly whether ,it is global. If it does not
specify, it depends on the address bytes which follow.
No address byte for the in-band operation is required,
and multiple address bytes imply the in-band line is
not explicitly included. The explicit global commands
WOg2/21186 PCT/US91/0~15
31 210963-~
have the leftmost bit on, followed by explicitly
specified address bytes. If the leftmost two bits are
both on, it is a broadcast, and no address ~ytes
follow. Multiple bytes are useful for off-band
control. At present, only one byte of in-band control
is employed. The leftmost third bit is reserved, and
the fourth bit is for system control point
specification. These are external or internal
indicated by E and I respectively as follows. The last
four bits define the commands of this category. At
present, these are: _
DEACTIv_Bs group: uwxlz, w bit is reserved and u
defines two system points.
DEL_Bs - (OXOO , O), an external delete command
DEX_Bs - (DEL_Bs ' l), an DEL_Bs, followed by
external setup
DI~_Bs - (DEL_Bs , OXlO), internally initiated
delete command
DIX_Bs - (DEX_Bs , OXlO), DIL_Bs, followed by
internal setup
ACTIV_Bs group: uwxOz, w bit is reserved, u the same
-~ as defined above.
ADD_Bs - (OXOO , 2), an external add command.
~; AID_Bs - (ADD_Bs ' OXlO), an internally
initiated ADD_Bs
,
- * SYNC vB
- ~ llOnnnnn: one byte only, used for time-fill and
synchronization.
. ~ ~
ll1nnnnn: one byte header, followed by no or multiple
optional bytes. This is an acceptance ac~nowledge in
reply to a RQST_Bs, and in-band is implied if no other
bytes follow.~` Similar to the case in RQST_Bs, the
first by which follows can further specify whether it
3S is global. $he leftmost two bits have exactly the same
meanings, which describe the scope of the possible
further succeeding addrèsæ bytes. The leftmost third
bit, if on, turns the whole meaning of the response
. .
WO92/21186 PCr/US91/0~15
210963$ 32
into a negative acknowledgement, instead. The last
five bits are the same as for RQST_Bs.
* MODE_vB
l000000m: for virtual channel operation and format
specification. THis has two members, MODE_rst with m =
0 and MODE lbc with m = l; MODE_rst defines the nnnnn
five bit generation number in restricted mode. In the
load-balancing mode, it handshakes with MODE_lbc, with
thirteen (13) bits global sequence numbers, when
opening a virtual B. The attributes of Ta~le I to
follow after these headers are optional. The mode
negotiation can proceed only when all component
channels are in deactivated states, or UNA will be
received. if the optional attributes are not acce~ted,
UNA will also be received. A REJ will be received if
the remote end does not support or will not accept this
request. In addition to this role of mode
negotiations, MODE_vB resets the generation number or
the global sequence number for transmitter and the
corresponding variable back to 0 to restart and resets
the transmitter and receiver (loop) pointers back to
the first component position.
* RR
l00000l0: Informs the far-end receiver that this end
is ready.
: ~ *
'
l00000ll: Informs the far-end receiver that his end is
not reàdy.
* ATTRB_vB
l00000l00: The parameters in Table I follow this for
far-end negotiation.
* UA
.
10010000: This unnumbered positive response means
acceptance in the mode negotiation. The same MODE_vB
packet will be sent back as bi-direction
~-~ initialization, following the UA. The UA is also used
for acknowledgement to flow control commands RR and
~` RNR. It is used for acceptance acknowledgement to
ATTR~_yB as well as unnumbered commands.
* UNA
: `
,: ,
~:
: `;
WO92/21186 PCT/US91/0~1
33
2109635
l00l0l00: a negative response for refusing, used
similarly to UA.
* REJ
l00lll00: as explained in the MODE_vB description.
All these unnumbered are in-band, although MoDE-vs
is for glo~al. The ~nnnnn~ is a module 32 correlation
generation number, or a zero based global sequence
number, assigned to each round of transmissions in
restricted mode of operation, or assigned and
incremented by one for each ~umbered transmission in
the load balanced mode. The "ss~ in the DATA command,
which has four values ll, l0, 0l nd ll, is for frame
segmentation.
Processing of these commands is independent of
lS their arriving timing phase with respect to other
channels, once dequeued. The sequence numbers are for
data synchronization across the component channels. A
receiver variable "nr", used for synchronization, is
incremented by one after each round, or each actual
numbered reception. This is a recovery process
corresponding to the far-end sender~s sequence number
increment for each round, or each data or numbered
ccmmand transmission.
Once mode negotiation is done, sequence number
comparison is then started. The selected virtual B
processor 174 polls the receiving queue and then s~eps
to the next component channel. In restricted mode, if
nothing arrives in the queue of an activated channel,
the processor stays and waits indefinitely. In the
case of NAC implementation, the processor waits
indefinitely or steps after a time out period if a
trace-back timer has been started, regardless of the
channel states. At a deactivated component channel,
WO92~21186 PCT/US91/03615
34
210963~
the processor hunts through all following contiguous
deactivated channels for any arrival, and does trace-
back get, steps or stays until the trace-back timer
expires, if arrival time inversion is found. The time-
fill ~YNC_vB commands are to be received over theirpxeceding channels, if no other commands or data are
available through these channels. The receptions in
load-balancing mode are always in hunting mode, across
the full range of component channels. The processor
continues looking for the correct sequence num~er for
presentation. Trace-back time-out presentation scheme
applies in either mode.
Parameters which characterize a virtual B-channel
to be opened and used to monitor the channel
hereinafter are listed in Table I.
typedef struct (
long err threshold: /~ one out of err ~hreshold frames ~/
short err action thres: /~ act on contig err action thres */
short err action De = i~ allow deactivation of errored channel ~/
short max band width; /~ max allowed bandwidth */
shor_ hig~ utiI thres; /~ high effective % band width threshold ~/
shor-. high ~usy util thres;/~ one high util out of high busv util~/ -
short high act~on_thr~s; ,/~ act on contig hi~h busy uti' tnres ~/
snort high action_permit; /~ allow ~andwidth lncrememt ac_ions
short ~in band width; /~ minimum allowed bandwidth ~/
short low util ~hres; /~ low effective % ~andwidth threshold *~
short low ~usy util t~res; ,'~ one low util out of low busv util ~/
shor~ low act on thres; /~ act on contig low ~usy util ~hres ~/
short low act~on Dermit; /~ allow bandwidth decrement ac_ions *~
shorS set UD retry_thres; /~ max contig retry b~ore gi~ing u~ */
shor~ no actlon_thres; /~ no action threshold time ~/
) VB THRESHOLD:
Table I - Virtual 3 C~annel At~-ibutes (in C language representation)
ll. Traffic Sensina
Sensing of traffic for automatic control of
bandwidth is carried out as follows. Assuming that the
sampling rate is one sample every two seconds, the
maximum bandwidth of the virtual channel opened is set
WO92/21186 PCT/US91/0~15
35 .2109635
to be five B-channels, definition of the high_util
thres is 75~, of a high_busy_util_thres is 5, the high
action_thres is ten and the initial channel opened is
one B-channel (64Kbps). As transmission rate increases
steadily from an original effective rate of 45Kbps to
55Kbps, a procedure for adding a new line is
automatically initiated thirty seconds later. This
assumes that the high_action__permit is true. A new
element channel is added and the new line utilization
will be 42.3~ if traffic is maintained at 55Kbps. An
increase in input data rate thus drives up bandwidth
growth. If the input data rate continues to increase,
the bandwidth eventually will reach five B-channels as
a maximum.
When traffic decreases, assuming that the low_util
- thres is 30%, and the low_busy_util_thres and low
action_thres are five and ten, respectively, no line
will be deleted from the virtual B if a pattern of the
driving traffic does not have a utilization of less
than 30% in any continuous ten seconds or there is no
consecutive repeating ten or more times. If the low
action_permit is false, no reduction in virtual B-
channels is permitted. The attributes of the virtual B
thus define the bandwidth control behavior.
- 25 If line error rate is above a predefined threshold
rate for a predetermined period of time, line
replacement operations are reduced in addition to
bandwidth control.
* * * *
l2. Conclusion
The invention provides user transparent sharing of
terminal resources distributed on an ISDN in response
WO92/21186 PCT/US91/03615
36
21~'963~
to operating system commands issued from any terminal
and transmitted globally on the Network. Bandwidth
utilization during information transfer between
terminals is optimized by carrying out dynamic B-
channel allocation in response to traffic directed toeach destination on the Network. Packets of data are
transmitted on the Network from each terminal in packet
~trains" rather than as individual packets. The trains
are compressed using a suitable compression algorithm.
In this disclosure, there is shown and described
only the preferred embodiment of the invention, but, as
aforementioned, it is to be understood Ihat the
invention is capable of use in various other
combinations and environments and is capable of changes
l~ or modifications within the scope of the inventive
concept as expressed herein.
