Note: Descriptions are shown in the official language in which they were submitted.
PHF 95516
21 72933
~ 1 18 March 1996
Commllnir~tif)n system comprising a network and a multiplexing device suitable for such a
system.
FIELD OF THE INVENTION
The present invention relates to a co,,,,,---nir~tion system comprising at
least a network of the ATM type, notably a network in which infolmation cells comprising a
first destination identifi~r which defines a set of de~li~tions7 and a second destination
identifier which defines a sub-set of said set, are tr~n~mitt~d from one of its access points to
another access point, and at least one multiplexing device coll,~rising:
- a plurality of access terminals for users who have cells to be tr~n~mitted at a
certain rate to a certain destin~ti-)n defined by said de~li~Lion identifiers,
- at least one conn~cting terminal for at least one access point of said network,
10 - a plurality of service circuits connPcted to the access terminals, comprising
queue elements for storing each the user cells which have the same destination
identifiers, and for rendering the stored cells available on cell outputs,
- an allocation circuit for determining the supply of a cell called chosen cell
selected from the available cells to said conn~cting terminal via an output circuit
at a current date, which allocation circuit co~ lises:
a circuit for producing a first destin~tion identifier.
The present invention also relates to a multiplexing device suitable for
such a system.
The ATM (A~yllchronous Transfer Mode) technique permits to transmit
different types of data (sound, image, files etc.) on the same carrier. These data are arranged
in packets called cells of a norm~li7~d length of 53 octets. An address contained in the
header and formed by two sub-fields, the VPI (Virtual Path Identifier) and the VCI (Virtual
Channel Identifier) ensures the routing of the cells inside the ATM network. The payload
content of the tr~n~mi~ion frame is called the ATM path. A succession of ATM cells having
the same VPI form a virtual path VP. The route followed by a succession of ATM cells for
the same VPI and the same VCI forms a virtual circuit VC.
For accessing an ATM network, one is confronted with certain rate
restraints and jitter restraints both as regards the virtual path VP and the virtual channel VC
imposed for reasons of security and call charge rate. A policing system connPcted to the
network ~ce-sces makes tests and may even ~u~ess the cells that lead to an overhead.
PHF 95516 2 1 7~938
~ 2 18 March 1996
The access point to the network is ensured by a multiplexing device
which, in consequence, is to comprise means for arranging the cells in the ATM path, so
that they colle~ol1d to this policing system and also produce the least possible jitter.
BACKGROUND OF THE INVENTION
S The French Patent document filed in the name of the Applicants under no.
94 07664, 22 June 1994 (FR 2 721 777), describes a mech~ni~m which is particularly
suitable for regulating cells "parametered" with a mA~imum rate PCR (Peak Cell Rate) and a
factor ~ < 1 (jitter less than one period). As, on the one hand, in the document "ATM User-
Network Interface Specification Version 3.0" by the ATM Forum, the idea of mean SCR
10 rate (Sllst~in~ble Cell Rate) was defined in September 1993, and as, on the other hand, it
becomes n~ ry to handle the statistical multiplexing between cell streams, the known
m~rhAni~m~ are thus to be mo~ ed to take account of these new requirements.
SUMMARY OF THE INVENTION
The present invention proposes a system of the type described above,
15 which takes account of these new requirements and makes it possible to regulate the
trAn~mi~sion of cells both at the VP level and at the VC level. Needless to observe that the
invention also applies to other ~lwol~ than the ATM n~Lwoll~.
Therefore, such a system is chalac~ ed in that the allocation circuit
additionally colllplises:
. a theoretical date determining circuit for determining a theoretical date for the
tr~n~mi~ion of the available cells of each service circuit as a function of, more
particularly, the certain rate,
a tree circuit presenting:
"leaves" for receiving the theoretical dates for each service circuit,
. a root for contAining dates called root dates, on the basis of which dates a
date called priority date is established from the theoretical dates,
nodes established in layers and conn~cting said leaves to said root,
a sub-tree circuit for selecting leaves from the leaves of the tree circuit in
response to the first destinAtion identifier, and for creating a partition in the first
destin~tion identifier,
a root date determining circuit for determining at least one root date in said
partition.
These and other aspects of the invention will be apparent from and
elucidated with lefelence to the embo-liment~ described hereinafter.
- PHF 95516
2 1 7~938
-- _ 3 18 March 1996
BRIEF DESCRIPTION OF THE DRAWINGS
In the drawings:
- Fig. 1 shows a network to which a multiplexing device according to the
invention is connrcted~
- Fig. 2 shows the structure of the info"l~lion cells tr~n~mitte~ in the
network,
- Fig. 3 shows a multiplexing device according to the invention,
- Fig. 4 shows the structure of an allocation circuit which forms part of
the device of Fig. 3,
- Fig. 5 shows the tree-like structure managed by the tree circuit which
forms part of the system according to the invention,
- Fig. 6 shows the structure of the tree circuit,
- Fig. 7 shows the structure of the tree circuit in more detail,
- Fig. 8 shows a first opelalillg mode of the tree circuit,
- Fig. 9 shows a second ope,~ g mode of the tree circuit,
- Fig. 10 shows a third ope~lil g mode of the tree circuit, and
- Fig. 11 shows the function relations established by the calculation
circuit.
DESCRIPTION OF PREFERRED EMBODIMENTS
Fig. 1 shows in a diagr~mm~tir manner an ATM network referenced 100
in the drawing Figure. A description of this network will be found in the publication entitled
"ASYNCHRONOUS TRANSFER MODE" by MARTIN de PRYCKER, published in the
ALICE HORWOOD Series in Britain in 1991. This network is formed by various nodes 102,
103, 104, 105, 106, 107 and 108, interconnected by links 110 to 118, for connecting the
nodes 102-103, 102-107, 103-105, 103-104, 104-105, 104-108, 104-106, 107-108 and 106-
107, respectively. Various access points to this nelwo,k are designated as 120 to 128. These
access points are connrcted to the nodes 108, 106, 107, 102, 103 and 105 via the links 130
to 138, respectively. Various multiplexing and demultirlexing devices 160, 161 and 162 are
connPcte~ to these access points. Among these devices there is to be distinguished: a
30 multiplexing device 160 which form part of the present invention, and two demultiplexing
devices 161 and 162, which perform reverse operations to those of device 160 and form part
of the system according to the invention. In European Patent Specification EP 0 632 669,
filed 23 June 1994, a description is found of such demultiplexing devices. To be connected to
the four points 120, 121, 122 and 123, the multiplexing device 160 has four connrcting
-PHF 95516
21 72938
- 4 18 March 1996
terminals 170, 171, 172 and 173. Thus, within the scope of that described example, the
hlro~ ation signals can go from device 160 to the devices 162 and 164 by passing through
the network 100. These transmit hlfo,lJlation signals are applied to a plurality of access
terminals 1800 to 1804095 which the multiplexing device 160 has and can be produced, for
5 example, on output terminals 1851 to 18SN of device 161 and 1901 to 190N of device 162.
The order of m~gnit~lde of N and N' is the order of one thousand. The i~ ation signals
tr~ncmitt~d through the network are produced in the form of cells whose shape is shown in
Fig. 2. These cells are formed by 53 octets of which 5 form the header HD and the 48
rem~ining octets referenced PL contain the data for a service to be tr~ncmitted. In the header
10 field, two codes VPI and VCI are distinguished which correspond to virtual path identifier
and virtual circuit identifier, respectively. The path identifiers are controlled by the
tr~ncmicsion opeldtor and the virtual circuit identifier is controlled by the user. To each VP
are assigned sub-sets of VC values: a sub-set of CBR and a sub-set of VBR, itself formed by
two sub-sets, a PCR and a SCR value. A data channel can be of the CBR type (Constant Bit
15 Rate), in which case its rate is normally regulated by the source. Thus, only the jitter is
optimi7ed, without a test of the rate and an arbitration is carried out between VC values of
the CBR type of the same VP to minimi7P the jitter.
A VC can be of the VBR type (Variable Bit Rate), which is considered to
have less priority than the VC of the CBR type. It is normally characterized by its "mean"
20 rate SCR (Sllct~in~ble Cell Rate), and its "peak" rate PCR (Peak Cell Rate). The PCR is
higher than the SCR and can only hold for a specified duration (cell burst). The ATM Forum
cited above defines exactly the VCR type seen from the policing point of view. The ABR
type (Available Bit Rate) defined by the ATM Forum can easily be adapted to the present
device. A process with an EPRCA algorithm (F.nh~n~ed Proportional Rate Control
25 Algorithm), not described here, will dyn~mir~lly modify the rate parameters linked with the
virtual paths or virtual circuits.
Fig. 3 shows a diagram of the multiplexing device 160. For simplicity of
the exposé, attention is only paid in this drawing Figure to the cells to be supplied to the
terminal 170 from access terminals 1800 to 1804095. The priority classification has already
30 been coded in the algorithms in an indirect way via PT_SCR and PT_SCR of the VC
descriptor described in Table 1.
Each of these terminals 1800 to 1804095 receives cells that have the same
identifiers and the same traffic constraints. Index i (0 ~ i ~ 4095) determines the index of
the ~ccesses 1800 to 1804095. The cells are stored in queue elements 2000 to 2004095. These
-PHF95516 2 1 7~938
- _ 5 18 March 1996
various elements 2000 to 2004095 are formed by memories of the FIFO type 2010 to 2014095,
r~ec~ively. These memories restore on their output the data to the order in which they have
come in. A recognition code "ir is ~sign~ to each of these elements 2000 to 2004095. A
common data line 210 connects the output of the queue elements to the terminal 170 via an
5 output circuit 211 which is a simple circuit for adapting the signals to terminal 120. Each
queue elemPnt 2000 to 2004095 comprises a notification circuit 2500 to 2504095 respectively,
for notifying the presence of a cell on its input. This circuit transmits this notification
accomp~ni~d by the recognition code ovçr a common line 260. The queue elements 2000 to
2004095 also comprise send authorization elements which are shown in the form of a switch
10 2700 to 2704095, on the one hand, and a decoding element 2800 to 28095, on the other. The
input of this decoding element is connP~tPd to a third common line 290 which interconnects
all the queue elements 2000 to 2004095.
By processing the notifications tr~n~mitted over line 260, an allocation
circuit 300 produces the recognition code on the last line 290 to authorize the queue element
15 in-lir~ted by this code to transmit a cell called chosen cell. This allocation circuit 300
operates in timing with a clock 302 which also supplies other signals (in a manner not
shown) to the various elements of the multiplexing circuit.
DESCRIPTION OF THE ALLOCATION CIRCUIT (300)
Fig. 4 shows the structure of the allocation circuit 300. It co~ ises a tree
20 circuit 400, a date counter 405 which gives the current date HDc" based upon clock signals
302. It also col~lises a calculation element 410 which ensures the management of the
allocation circuit 300 in collaboration with a working memory 412 which notably contains
information signals linked with the various VP and VCs. A second tree circuit 420 produces
the VP. This circuit 420 may advantageously be of the type described in the EP Patent
25 Specification mentioned above, or by a cyclically polled allocation table described in
European Patent Specification No. 0 618 748. The VC selected by the circuit is supplied by
line 290.
D~ tion of the tree ~llu.~ule.
Fig. 5 shows the tree structure which the tree circuit 400 is to produce.
This tree structure is of the qua~ ~y type and is formed by six levels
LV1 to LV6 co-llplising 1 to 1024 nodes. Each node is formed by four locations implicitly
numbered from left to right "oon, "01n, "10" and "lln. Each of these locations is connected
to a node of a lower level. The locations of the last level LV6 form the leaves of the. tree.
The level LV1 colllplises a single node, called root node, rererellced NR. The level LV2
- PHF 95516
21 7~938
- 6 18 March 1996
comprises four nodes whose references are formed by the letter N followed by a number in a
binary order, that is: N00, N01, N10 and Nll; only the nodes N10 and Nll are shown in
the Figure. The level LV3 co~plises 16 nodes of which only the nodes referenced N1011
and N1100 are shown. For the other levels there are thus:
5 LV4 64 nodes, of which only the nodes N101111 and N110000 are shown.
LV5 256 nodes, of which only the nodes N10111111 and N11000000 are shown, and
LV6 1024 nodes, of which only the nodes N1011111111 and N1100000000 are in~ ted.It will be evident that the numbering of each node is formed, on the one hand, by the binary
part of the node of the higher level to which it is conn~cted and, on the other hand, by the
10 number of the location to which it is particularly allocated.
According to the invention, the tree is divided into sub-trees. In Fig. 5
three sub-trees relating to the same VP are shown. One of these sub-trees relates to VC
PCR, another one to VC SCR and the last one to VC SBR. These various sub-branches are
defined by parameters MIN and MAX. In principle, each VC CBR has an input in the sub-
tree CBR of its VP, while the VC VBRs have two: one input in the sub-tree SCR and the
other input in the sub-tree PCR. For obtaining o~ ulll regulation of the rates on the VC
VBR of a VP, it is n~cess ~ y that the inputs of a sub-tree SCR or PCR be graded in priority
levels depending on the rate of their associated VC, from the higher to the lower rate, and
thus from left to right of the sub-tree.
Fig. 6 shows the structure of the tree circuit 400. This circuit 400
comprises a succession of processors Pl to P6, ~ign~d each to a level LVl to LV6,
respectively. To the processor Pl is conn~cte~ a memory MEMl formed by a line cont~ining
four dates coming from the processor P2. To this processor P2 is connected a memory
MEM2 formed by four lines cont~ining each four dates coming from the processor P3 and so
25 on and so forth up to the processor P6 to which is connPcted a memory MEM6 org~ni~ed in
1024 lines which contain each four dates relating to four leaves, so that the various leaves
numbered from 0 to 4095 can be processed. The leaves are intended to receive dates by
insertion. The dates to be inserted into the leaves form part of the arguments of an "Ins"
function.
30 In response to an information signal relating to a "Rch" function, the tree circuit 400
produces a result "RtRch" which represen~, indirectly through the Table "Ind" 412 (Fig. 4),
the number of the queue element that is to transmit its cell. A distribution circuit 480 makes
it possible to apply the illrollllalion signals which have to travel in the direction of leaves-
root and in the direction of root-leaves.
-PHF 95516
2 1 72938
7 18 March 1996
Fig. 7 shows a detailed diagram of the structure of the processors P5 and
P6. Their associated memories carry references MEM5 and MEM6, respectively.
Leaves-root p.ocr~
This processillg relates to the arguments of the "Ins" function, that is, in
S the calling order:
EMP: the location of the leaf likely to receive a new date.
Dtln: the date likely to be inserted.
V/F: insertion valid or false.
MINM and then MAXM: determine the limits of the sub-tree in which one works in the
10 in~ir~t~ direction.
The two least signifir~nt bits of the h~ llation signal EMP which are
denoted "CEMP" are applied to an input management circuit GES6 to define the location of
the node of level LV6, whereas the rest of the bits denoted "NEMP" are applied to the
addressing input of memory MEM6 via an addressing switch SB6 to define the number of
15 the node. As memory MEM6 is organi~ed in lines which contain four codes each, the
management circuit GES6 has for its task to put this code in the proper line location.
Therefore, in a first period of time, it stores the four stored codes in the addressed line via
the two-position addressing switch SB6, via another part of the code coming from the line
EMP. In a second period of time, the management circuit GES6 ov~,wli~es with the code
20 coming from the line Dtln one of the four stored dates in response to the afore-mentioned
two bits. In a third period of time, all the codes stored in this management circuit are written
in the memory MEM6. In a fourth period of time, these same codes are read out again from
MEM6 and offered to a date determining element CP6 which determines the date code to be
tr~n~mittecl on a line LP6,5.
The date determining element CP6 increases the code that has the smallest
value by taking account of MINM and MAXM in the following manner:
If NII~in is noted to be the value of the node contained in MINM during NEMP~ and C~ n the
value of its two bits having less signif1r~nre, CP6 ignores the codes to the left of the code
defined by "Cn,in" if Nmin is NEMP. Similarly, if Nll~aX is noted to be the value of the node
30 contained in MAXM during NEMP, and CmaX the value of its two bits having lesssi~nifir~nre, CP6 ignores the codes to the right of the code defined by "Cmax" if, however,
Nn~X = NEMP. The tests Nmin = NEMP and NmaX = NEMP are carried out by C6, 1 and
C6,2, respectively. A similar processing is carried out by the other processors PS to P1. A
register Dr finally contains the root date produced by P1 at the output of CP1. However, the
- PHF 95516
2 1 7~938
8 18 March 1996
presence of a signal V/F applied to the single management circuit GES6 will be noticed
which, when the signal has the value FAUX, makes it possible to cancel the writing of a new
date in the memory MEM6. Thus, when considering the last processor PE, it contains in its
memory MEM1 the theoretical dates which have the values resulting from the choice of the
5 prece-~ing processors. This forms the leaves-root processing.
Fig. 5 represents the tree after an insertion with the leaves having binary
notations "10 11 11 11 11 01" and "11 00 00 00 00 Oln, by taking these same values for
values of MINM and MAXM. It will be found that Dr contains the lowest date between
MIND and MAXD. An insertion at the limits of a sub-tree forms the first partitioning step of
10 the tree (applied here to the sub-tree CBR).
Root-leaves procA~
This processing relates to the arguments of the function "Rchn, that is, in
the calling order:
V/CD: permits to have two different criteria for selecting the circuit VC,
15 MIND and then MAXD: determine the sub-tree in which one works,
RT_PRI: gives a priority for the VCs in order to avoid that it is always the same circuits
that are chosen.
The output parameters of this function "Rch" are:
ELEM: number of the leaf and from there the virtual circuit that is chosen; this number is
20 complete by concatenation with each change of level.
RSPRI: gives a change of priority for a new selection of VC. This value conslilules the
argument RT_PRI for a following search.
The root-leaves processing consists of producing, indirectly, the address
that corresponds to the leaf associated to the queue element that is authorized to transmit its
25 cell. This code is formed by collcatel~lion in a similar manner to the one described in the
Patent Specification mentioned above, and appears on the line ELEM. This choice is also
made as a function of m~gnitudes MAXD and MIND, which limit this choice. Furthermore,
a m~gnit~ V/CD permits to change this criterion for making this choice. Another code is
also formed by concatenation, which appears on a line RSPRI. This permits to make a
30 turning priority as this will be described in the following with respect to the present memory.
This processing consists first of all of ch~nging the positions of the
switching circuits SA6 and SB6. The memory MEM6 is in that case addressed by a code
coming from the line ELEM, a searching element PH6 whose input is comlected to the data
- PHF 95516
2 1 72938
9 18 March 1996
output of the memory MEM6 via the switching circuit SA6 determines the last two bits of
the final code of ELEM and RSPRI. This is effected notably by comparing codes contained
in the line addressed by those produced by the dating element 405. The circuits PHj, with j
= 1 to 6, can be conceived as a function of the explanations that follow.
S The circuit Phj chooses a code from those present on the output of the
switching circuit SAj. For being selected, an exclusion principle analogous to the one used
on insertion is applied to the codes present.
With respect to level j, it is required that:
- Nm,D,j is the value of MIND relating to its "2*(j-1)" most signifir~nt bits, and
Cm,nj is the value of MIND relating to the 2 least signifir~nt bits,
- Nrna~C j is the value of MAXD relating to its "2*(j-1)" most signifir~nt bits, and
Cma,c j is the value of MAXD relating to the 2 least si~nifir~nt bits,
- Nrt j is the value of RT_PRIO relating to its "2*(j-1)" most significant bits, and
Crt j is the value of RT PRIO relating to the 2 least signifir~nt bits.
15 One proceeds as follows:
The codes to the left of the code defined by "Cmin j n are ignored if Nrnin j =
ELEMj,
The codes to the right of the code defined by "Cr,,ax j" are ignored if NmaX j =ELEMj.
20 Phj only takes into account only the rem~ining codes for that which follows.
- If V/CD = VBR, Phj chooses the priority code in the following manner: "Crt i"
turns to the right are first made with the priority codes.
The number of the chosen location is that which contains a date that is lower
than the current date Dc and which has the most priority. The number of this
location is then concatenated to ELEMj with its least signifir~nt bits and then
goes to the stage j + 1. If other locations contain a lower date than the current
date Dc, the number of the location having the lowest priority of them is
conr~ tecl to ELEMj to form RSPRI. In the opposite case, ll00" is
co~cate~ted to the former value of RSPRI.
30 - If V/CD = CBR, Phj chooses the priority code by choosing simply the lowest
date.
The number of its associated location is then concatenated to ELEMj with its
least signifir~nt bits and then goes to stage j + 1. "Crt j" and RSPRI are not
evaluated.
-PHF95516 2i 7~938
- _ 10 18 March 1996
The following three examples represent that which has just been described.
a) ~ ti ....i.-;..r RSPRI and ELEM for RT_PRI = "00. . .00".
Reference is made to Fig. 8 for the explanation. In this Figure, reference
K0 l~resents the value of the current date "Dcn, reference Kl represents the values of the
5 locations of the root node NR. Each location is numbered from "oo" to " l l n in binary
notation from left to right and is ~ccign~d a priority number "Pty" running from 3 to 0 in
decimal notation from left to right. A high priority number in~ tes a high priority. Only the
locations cont~ining a date lower than the current date Dc are considered. As the locations of
the node NR contain only dates lower than the date "Dcn, the date 961 having priority 3 is
10 chosen, of which the location is numbered "oon this forms the first two bits of the code
ELEM. Then is chosen the lower-priority date, that is, 922, which corresponds to location
"01" having priority 2. The first two bits of RSPRI are thus "01n. Then the node of the level
LV2 is proceeded to. The number of the node is given by the value ELEM, thus node N00 is
considered. Here it will be obvious that the date having the highest priority is not suitable,
15 because its value 1012 is higher than the current date. If one goes back to the date 971,
having priority 2, which is situated at location "01n, the code ELEM becomes "00 01". The
value of RSPRI passes "00 10n, because the location "01" col,e*,onds to the lower priority.
Then level LV3 is proceeded to, where the node N0001 defined by the code ELEM
established above is considered. This node N0001 contains only one date 971 which is lower
20 than the current date. As this date is situated at the location n 10", the code ELEM becomes
ELEM = noo 01 10n. Under these ch-;ull~lces "00" is added by concatenation to the
value RSPRI already evaluated, so that RSPRI = noo 10 oon.
Then level LV4 is proceeded to where the node N000110 is considered.
This node contains two dates lower than the current date. One thus chooses the date 971
25 which corresponds to the location "01" having priority 2, that is, the new value of ELEM =
"00011001n. Subsequently, the lower priority is chosen, that is, 950, which corresponds to
the location "lln. A new value of RSPRI is thus "00011011n. It should be noted that,
contrary to ELEM which is extended by two bits for each stage without a mo-lifir~ti~ n of the
previously acquired bits, the value of RSPRI is changed by conr~lP~ g the node - thus by
30 erasing the previous value - and the location of the chosen element with second priority. One
proceeds in this manner up to the level of the leaves.
b) det~l.l.il.ation of RSPRI and ELE~I for RT PRI = "01101...".
Reference is now made to Fig. 9. The same root node as in the prece~ing
Figure is considered. This time the initial priority is modified by the first two bits of the
-PHF 95516
2 i 72938
11 18 March 1996
code RT_PRI. As these bits are "01n, the priority codes are shifted to the right, so that the
date 922 gets the highest priority and the date 954 the next priority, so that ELEM = n01"
and RSPRI = n 10" . For the level LV2, the selected location is n 10", which corresponds to
the highest priority, because the priorities have been changed by the third and fourth bits
5 which follow, that is: "10n, finally there is obtained RSPRI = nOlll" and ELEM = "0110n.
c) .lot~ ing RSPRI and ELEM for RT_PRI = "0110..." taking into account MIND
and MAXD.
R~feIence is made to A of Fig. 10. It is supposed that the first two bits
10 having the value MIND are n lOn~ that is to say, this value points at the date 954, all the
dates sitn~ted to the left of this value are inv~ trd as is in(lir~ted by the lines through the
dates 961 and sæ. The first two bits of the value MAXD are n l l n ~ SO that none of the date
bits is inv~ trd by MAXD. The bits of RT_PRI that relate to the node NR are ll01 n, so
that the priority values are shifted. As the date having the highest priority 922 is crossed out,
15 the date 954 having second priority is taken and the bits of RSPRI represent the location
having the priority n 11 n .
Reference is made to B of Fig. 10. MIND is supposed to be equal to
"0010..." and MAXD to "1000...n, and the node N10 of LV1 is considered. Only MAXD is
taken into consideration, because the value of the node "10" is equal to that contained in
20 MAXD in its two most significant bits. The dates st~n~ing to the right of the arrow MAX
are crossed out, that is: 971, 961 and 915. Only the date 995 remains, which results in the
two bits ll00" for ELEM. Since there is no date having a lower priority, RESPRI thus has
the bits "00" concalenated to its previous value.
The circuits thus described permit to operate as a pipeline if registers
25 referenced PA6,5, PB6,5 and PC6,5 in Fig. 7 are utili7.e~. That is to say, while one
processor manages a code, the next processor manages a prece~ing code. The fact that one
processor is taken for each level of the tree permits to increase the rate of the notifications
introduced in the tree circuit. If this rate is low, a person skilled in the art will not find any
difficulty in llimini~hing the number of gates used by the device by assigning various stages
30 to the same processor. One will flnd that the root-leaves processing will take account of an
updating with a code after its leaves-root processing.
The dates are coded in "N" bits in the tree. This quantity depends on the
lowest rates one wishes to process. Two additional Booleans + ~/-~ make it possible to
declare a date that can never be chosen (always higher than the current date) and a date that
PHF 95516
2 1 72938
12 18 March 1996
can always be chosen (always lower than the current date), respectively.
It should be observed that the device supports a date coding with 0 bits,
the date permiKing to be summarized to the Booleans + x/-x possibly coded with 1 bit and
m~rking the absence (+ oo) or the presence (-oo) of stand-by cell(s) for a virtual circuit: the
5 interest of the device is no longer its cell spacing function (which can be realized upstream of
a device), but its capacity to select a part of the virtual circuits and choose a priority bit
thel~rl~lll.
CALCULATION ELE~ENT 410
Fig. 11 shows the logic structure of this element. The element is
10 established around three drivers which drive co~ ently. These processes communicate by
mailbox. They interact with the Arbo function produced by tree 400 via primitives Rch and
Ins, and the result RtRch which have just been described. A person of ordinary skill in the
art will not find any difficulty in tr~n~l~ting into HDL (Har-lw~re Descli~tion Language) to
"compile" them on silicon.
Among these various drivers there are distinguished:
- PrRch: search driver. This process coopelales, on the one hand, with a describer of VP
(DesVP) and indirect variables Ind_A VC (link Acc VAR1) and, on the other hand, with the
current date "Dc" produced by the date counter 405 and the values MINIMUM and
MAXIMUM which define the sub-trees (link Acc VAR2). This process triggers the search
20 Rch for the Arbo function and reslores thelerlolll the result RtRch. This process receives
search requests by a link DRch and supplies the f~ result by a link RRch. It also
commllnir~tes by a link MJSSA with a process PrIns.
- PrIns: insertion driver which triggers the date insertions in the Arbo tree function via the
link that corresponds to the function Ins. This process communir~tes with a VC describer
25 table, called DesVC, via the link Acc VAR3 and also via the variables MINIMUM,
MAXIMUM, and Dc via the link Acc VAR4. It is triggered after a notification coming from
the line 260 (cf. Fig. 3), which is in-lic.~te~l by the link Not. This process is also triggered by
the process PrRch, as observed above. It is finally triggered by a process PrCoh (link
DMJS).
30 - PrCoh: coherence driver which updates the various dates in the tree circuit 400. Below,
these various drivers will be shown in detail.
a) in~ertion driver
The insertion driver has for its function to update a describer of each VC
and to update the tree by insertions. It co~ ,lises the describer table VC (DesVC) indexed by
PHF 95516
21 72938
13 18 March 1996
the notification number (equivalent to the number VC).
The form of a describer is given in the following Table I:
TABLE I
S Type VC selectionVBR/CBR
PT_PCR input sub-tree PCR
PT SCR input sub-tree SCR
PT_CBR input sub-tree CBR
Stop_CBR m~imum permissible jitter in CBR mode
Stop date CBR* m~ximllm theoretical send date sub-tree CBR
Th PCR* minimllm theoretical send date sub-tree PCR
Th_SCR* minimllm theoretical send date sub-tree SRC
Period PCR Sub-tree period PCR
-
Period_SCR Sub-tree period SCR
Cell_counter cell counter for this VC
Burst-time m~imllm permissible burst time PCR
* These variables have two markers + ~ and -~ .
The set of functions EFuncl executed upon the arrival of a notification "i" (Not) is the
20 following:
EFunc1
START
Cell_counter [i] = Cell_counter [i] + 1
if Cell_counter [i] = 1
if Type_VC[i] = CBR
then
Stop_date_CBR[i] = DC + Stop_CBR[i]
"Ins" (PT_CBR[i], Stop Date_CBR[i], TRUE, MINIMUM,
MAXIMUM)
else
calculate and update Th_PCR[i] and Th_SCR[i] as a function
of table II.
n Ins n (PT_PCR[i], Th PCR[i], TRUE, MINIMUM,
3s MAXIMUM)
PHF 95516
2 1 72938
14 . 18 March 1996
"Ins" (PT_SCR[i], Th_SCR[i], TRUE, MINIMUM,
MAXIMUM)
endif
endif
5 END
The set of functions EFunc2 carried out upon the arrival of a request for updating coming
from the search process with a VC having number 'i', tr~n~mitted by the link MJSSA, is the
following:
EFunc2
START
Cell_counter [i] = Cell_counter [i] -1
if Cell_counter [i] ~ > 0
then
if Type_VC[i] = CBR
then
Stop_date_CBR[i] = DC+Stop_CBR[i]
"Ins" (PT CBR[i], Stop date_CBR[i], TRUE,
MINIMUM, MAXIMUM)
else
calculate and update Th PCR[i] and Th_SCR[i] as
a function of Table II.
"Ins" ( PT_PCR[i], Th_PCR[i], TRUE,
MINIMUM, MAXIMUM)
"Ins" ( PT_SCR[i], Th_SCR[i], TRUE,
MINIMUM, MAXIMUM)
endif
else
if Type_VC[i] = CBR
- then
"Ins" (PT_CBR[i], + ~, TRUE,
MINIMUM, MAXIMUM)
PHF 95516 ~ l 7 2~ 38
18 March 1996
else
"Ins" (PT_PCR[i], + ~, TRUE,
MINIMUM, MAXIMUM)
"Ins" (PT_SCR[i], + ~, TRUE,
MINIMUM, MAXIMUM)
endif
endif
END
10 The set of functions EFunc3 carried out upon the arrival of a request for selecting a sub-tree
coming from the search process is the following:
EFunc3
START
"Ins" (MINIMUM, ~uc, FALSE, MINIMUM, MAXIMUM)
"Ins" (MAXIMUM, x~x, FALSE, MINIMUM, MAXIMUM)
END
The set of functions EFunc4 carried out upon the arrival of a request to update coming from
the coherence process (link DMJS) is the following:
EFunc4
START
if Type_VC[i] = CBR
then
"Ins" (PT_CBR[i], - ~, TRUE, MINIMUMj MAXIMUM)
else
"Ins" (PT_SCR[i], - oo, TRUE, MINIMUM, MAXIMUM)
"Ins" (PT_PCR[i], - ~, TRUE, MINIMUM, MAXIMUM)
endif
END
The calculation of the new values of Th_SCR and Th_PCR for a given VC is shown in the
following Table II
.PHF 95516
21 729~3
- 16 18 March 1996
TABLE II
Th SCR + Th?CR + Th SCR + New values of Th_SCR
SCR period PCR period SCR period and Th?CR
< Dc ~ Dc <Dc+Burst_time
no no no Th_SCR = Th_SCR +
(PCR burst SCR period
forbidden) Th?CR = Dc +
SCR period
no no yes Th_SCR = Th SCR +
(PCR burst SCR period
permitted) Th?CR = Th?CR +
PCR period
no yes no Th_SCR = Th_SCR +
(ruptured (PCRburst SCR period
stream) forbidden) Th?CR = Dc +
SCR_period
no yes yes Th_SCR = Th_SCR +
(ruptured (PCRburst SCR period
stream) permitt~ed) Th?CR = Dc
yes no - Th_SCR = Dc
(ruptured stream) (impossible case)
Th?CR = Dc
(SCR period
> PCR period)
yes yes - Th_SCR = Dc
(ruptured stream) (ruptured Th?CR = Dc
stream)
Dc: Current date
b) search driver
The device receives in the search phase an argument VP which
in-lir~tes in which sub-set of VC (the VCs contained in this VP) the selection of the VC has
taken place.
Each VP possec~es a describer (DesVP) with the following arguments:
-PHF95516 2 1 7293~
17 18 March 1996
TABLE III
PTmin_PCR minimum pointer of the VP sub-tree PCR
PTmax_PCR m;.xi,,,u,,, pointer of the VP sub-tree PCR
PTmin_SCR mil~i"~u~ pointer of the VP sub-tree SRC
5 PTmax_SCR m~xi",~J", pointer of the VP sub-tree SCR
PTmin_CBR minimllm pointer of the VP sub-tree CBR
PTmax_CBR m~xi,,,u,,, pointer of the VP sub-tree CBR
ROT_SCR* turning priority index on sub-tree SCR
ROT_PCR* turning priority index on sub-tree PCR
10 OPT ROT_SCR turning priority activation/inactivation Boolean SCR
OPT_ROT_PCR turning priority activation/inactivation Boolean PCR
* ROT_SCR and ROT_PCR are initi~li7~d at 0 at the start.
15An appended table Ins_A_VC permits to find back a VC on the
basis of one of its leaf elements in the tree.
The set of functions EFuncS carried out upon the arrival of a search request in a given VP
(link "DRchn) denoted 'i' is the following:
EFunc5
START
y = - 1 (impossible value)
MINIMUM = PTmin_CBR[i]
MAXIMUM = PTmax_CBR[i]
send a request for selecting a sub-branch to the inserting process
wait for its execution, that is to say, the root date is to be updated.
if Root_date < > +
then
~Rech" (CBR,MINIMUM, MAXIMUM,xxx)
the search return gives 'y' the number of the chosen leaf inthe tree.
-.PHF 95516
2 1 72~8
18 18 March 1996
else
MINIMUM = PTmin_SCR[i]
MAXIMUM = PTmax_SCR[i]
send a request to select a sub-tree to the insertion process;
wait for its execution, that is, the root date is to be updated.
If Root_date ( < or =) Current date
then
"Rech (VBR, MINIMUM, MAXIMUM, ROT_SCR[i])
the search return gives 'y' the number of the chosen leaf in the tree.
the return gives 'resprio' which is the priority index found.
if OPT_Rot_SCR[i] = TRUE
then Rot_SCR[i] = resprio
endif
else
MINIMUM = PTmin PCR[i]
MAXIMUM = PTmax_PCR[i]
Send a tree selection request ss to the insertion process; wait for its
execution, that is, the root date is to be updated.
if Root_date (~ or =) Current date
then
"Rech" (VBR, MINIMUM, MAXIMUM, ROT_PCR[i])
the search return gives 'y' the number of the chosen leaf in the
tree.
the return gives resprio the priority index found
if OPT_ROT_PCR[i] = TRUE
then
Rot_SCR[i] = resprio
endif
endif
endif
endif
if y <>-1
then
vc_found = Ind A_VC
-.PHF 95516
2 1 72938
19 18 March 1996
send an update request with vc_found to the insertion process
vc_found is the VC number returned by the device in "RRch"
else
no VC is returned by the device, because no one can be
selected.
endif
END
c) coherence d~iver
This process scans the various VCs and "cleans" the dates becoming too
10 negative relatively to the current date. This process is slow and can take various milli~econds
to scrutinize all the VCs.
The associated set of functions EFunc6 is the following, with N being the number of VCs
tested by the device:
EFunc6
15 START
for i running from 0 to N-1
repeat
if Type_VC = CBR
then
if Stop_date_CBR[i]_Current date < THRESHOLD
then
Stop_date cbr[I] = x
request the insertion driver for an insertion with 'i'
endif
else
if Th?CR[i] - Current date< THRESHOLD or Th_SCR[i] -
Current date < THRESHOLD
then
Th_PCR[i] = -
Th_SCR[i]=-~
request the insertion driver for an
insertion with 'i'
endif
-PHF 95516 21 729~
18 March 1996
endif
end-of-repetition
END
In a simplified version, the device can function very well without a
5 notification with all or part of its service circuits. In the mode called "autonotifiedh, the tree
is supplied a first time to "trigger~ its service circuits without notification. The calculation
element does not take into consideration the cell counter in the stand-by mode which is
associated to each hautonotified" service circuit, so that the latter are periodically chosen in
the tree, even if there are no stand-by cells.
10 Direct access to the table which contains the period of each service circuit renders the
mo-lific~tion of the rates direct and makes the system attractive to apply the methods of flow
control which necessitate a rapid rate variation without much jitter.
