United States Patent (19)
`Galand et al.
`
`54 METHOD AND SYSTEM FOR OPTIMIZING
`DATA TRANSMISSION LINE BANDWDTH
`OCCUPATION IN A MULTIPRIORITY DATA
`TRAFFICENVIRONMENT
`
`75 Inventors: Claude Galand, Cagnes-sur-mer;
`Gerald Lebizay, Vence; Victor
`Spagnol, Cagnes-Sur-mer, all of France
`
`73 Assignee: International Business Machines
`Corporation, Armonk, N.Y.
`
`21 Appl. No.: 08/907,399
`22 Filed:
`Aug. 7, 1997
`30
`Foreign Application Priority Data
`Dec. 13, 1996 EP European Pat. Off. ............... 9648O111
`51) Int. Cl. ............................. H04L 12/28; H04L 12/56
`52 U.S. Cl. .......................... 370/412; 370/413; 370/415;
`370/417
`58 Field of Search ..................................... 370/412,468,
`370/470, 471, 473, 474, 394, 395,413,
`414, 352
`
`
`
`USOO595 6341A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,956,341
`Sep. 21, 1999
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,570,355 10/1996 Dail et al. ............................... 370/352
`5,608,733 3/1997 Vallee et al. ............................ 370/394
`Primary Examiner Jeffery A. Hofsass
`ASSistant Examiner John Pezzlo
`Attorney, Agent, or Firm John D. Flynn; Morgan &
`Finnegan
`ABSTRACT
`57
`A method and System for optimizing data link occupation in
`a multipriority data traffic environment by using data mul
`tiplexing techniques over fixed or variable length data
`packets being asynchronously transmitted. The packets are
`Split into Segments including both a Segment number and a
`packet number. The Segments are dispatched, on a priority
`basis, Over available links or virtual channels based on a
`global link availability control word indications, which
`control word is dynamically adjusted according to specific
`predefined conditions.
`
`13 Claims, 19 Drawing Sheets
`
`SWITCH
`INTERFACE
`
`REASSEMBLY
`AND
`ROUTING
`
`SEGMENTING
`
`EX 1007 Page 1
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 1 of 19
`
`5,956,341
`
`NETWORK
`
`TRANSIT
`NODE
`
`USER
`
`USER
`
`USER
`
`
`
`
`
`
`
`Ost?
`N->s
`WARIABLE
`LENGTH
`TRAFFIC
`
`FIG. 1
`
`NETWORK
`
`FIG. 2
`
`EX 1007 Page 2
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 2 of 19
`
`5,956,341
`
`SWITCH
`INTERFACE
`
`REASSEMBLY
`AND
`ROUTING
`
`FIG. 3
`
`
`
`QOS -
`VALUES
`
`-
`
`BITS -
`RANGE
`
`-
`
`1
`O
`BITSCAN
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`FIG. 4
`
`EX 1007 Page 3
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 3 of 19
`
`5,956,341
`
`
`
`
`
`
`
`
`
`
`
`
`
`NR PXCB 3
`
`1 BYTE
`
`1 BYTE
`
`4. BYTES
`
`
`
`
`
`XPKTN
`
`XSEGN
`
`XPKT
`
`FIG. 5
`
`EX 1007 Page 4
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 4 of 19
`
`5,956,341
`
`END OF SEGMENT
`INTERRUPTPROGRAM
`
`MAN STEADY STATE PROGRAM
`
`XP-ENTRY
`
`RESET LINK ACTIVE FLAG
`
`
`
`
`
`
`
`
`
`RELEASE SEGMENT BUFFER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EOS INTERRUPT
`
`GET PKT FROM SWITCHAND
`ENOUEUE INTO RELATED OOS
`XOUEUE
`
`
`
`ANY LINKAVAILABLE 2
`
`604
`
`Y
`
`DEQUEUE SEGMENT FROM
`HIGHEST OOS XOUEUE.
`CALCULATE SEG. HEADER
`
`
`
`RETURN
`
`LINK SELECTION AMONG
`AVAILABLE LINKS AND SET LINK
`ACTIVE FLAG ON
`
`START SEGMENT TRANSMIT
`
`FIG. 6
`
`EX 1007 Page 5
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 5 of 19
`
`5,956,341
`
`EOS-ENTRY
`
`GET LINK INDEX : 1X
`
`RESETLINK ACTIVE (1X) FLAG
`INTO LACW
`
`RELEASEXMITTED SEGMENT BUFFER
`
`702
`
`
`
`703
`
`EXIT
`
`FIG. 7
`
`EX 1007 Page 6
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 6 of 19
`
`5,956,341
`
`XP ENTRY
`
`ANY PACKETRECEIVED NN
`FROM SWITCH2
`
`801
`
`
`
`
`
`GET CONNECTION ID FROMPACKET HEADER AND
`FETCHGN (IF ANY)
`- ENOUEUE IT INTO RELATED QOS QUEUE
`(RT1,
`RT2, NRT, NR) OF GROUP GN
`-SET RELATED XO BIT ON INXMIT STATUS
`
`ANY LINKAVAILABLE 2
`
`803
`
`
`
`
`
`SELECT SAD AVAILABLE LINK = 1X
`1X-> 1X INDEX
`
`XP1
`
`FIG. 8
`
`EX 1007 Page 7
`
`

`

`US. Patent
`
`Sep. 21, 1999
`
`Sheet 7 0f 19
`
`5,956,341
`
`5m
`
`mom
`
`EEu9EE_E0E93EEm
`sawEEXAEEManamaNEE529EE93EFo"xo”602.5::5:mm
`
`
`
`
`
`o"6HXEZEE:sxEmozESxEEESEo
`
`EEuONEE35E99EmmES52ONE1
`08VEonwEmangoEoxNEm1xo”x37:ca:5;Em
`
`.ozESxNE1m6”xmazb:ExmmEExNEN
`
`ezEsxE2IN"6H6029.;ExEEn__xE2v
`
`
`
`oz_Io._.<n_w_omgmw3._.<._.m.sz
`
`>.:mo_mm
`
`z<ow“.0
`
`
`
`
`
`5.meuOkmzn:"EC._._mOXIHEZHum>._.n=>_mHOZOhm—zIAxgET0szmagmaEoxE2mNn6”59:b:E;E
`
`fig
`
`EE”92E&oE93%EmEE5282I
`sawE792ManamaEoxENmuxcuXE;b::5;Em
`
`ozEsxmzImux0Hx823:E;mmEm2m2o
`
`m6.".a
`
`:5oh@2552
`
`EX 1007 Page 8
`
`EX 1007 Page 8
`
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 8 of 19
`
`5,956,341
`
`XP2A
`
`SETXIP BIT (QX) = ON
`
`INCREMENT PACKETSEQ NB
`XPKTN (QX)+ 1
`
`1001
`
`NIT SEGTSEQNO
`O-XSEGN (QX)
`
`1002
`
`
`
`XP2B
`
`INCREMENT SEGTSEQNO
`XSEGN (QX) + 1
`
`1003
`
`DEQUEUE SEGT POINTER FROM SELECTED
`PACKET_LISTXPKT (QZ) --XSPTR
`
`1004
`
`SETUP 4. BYTE SEGMENT HEADER
`
`GROUPNUMBER = GN
`-QOS FELD = QX
`-PKT NO =XPKTN (QX)
`-SEGTNO =XSEGN (QX)
`-LBT = 1 WHEN LAST SEGT OF PKT
`= 0 WHEN NOT LAST SEGT OF PKT
`
`CALCULATE AND SET LRC BYTE OF HEADER
`
`1005
`
`STARTXMIT FROMXSPTR POINTER SET SELECTED
`LINK (1X)"ACTIVE"FLAG ON
`
`006
`
`{ let-on Dy
`
`1007
`
`FIG. 10
`
`XP ENTRY
`
`SETXIP BIT (QX)=OFF
`
`1008
`
`EX 1007 Page 9
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 9 of 19
`
`5,956,341
`
`
`
`RTG
`RESEQUENCING
`REASSEMBLY
`
`ROUTING
`
`SWITCH
`INTERFACE
`
`FIG. 11
`
`EX 1007 Page 10
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 10 0f 19
`
`5,956,341
`
`
`
`
`
`BASE PACKETELEMENT
`
`PKT-STAT
`
`BUILT-IN
`LINK
`
`PKT STRUCT (PX)
`
`REASSEMBLY
`SLOTS
`
`1202
`
`PKT INFORMATION
`
`FIG. 12
`
`EX 1007 Page 11
`
`

`

`US. Patent
`
`Sep. 21, 1999
`
`Sheet 11 0f 19
`
`5,956,341
`
`
`
`20a>._._mo_mn_>>o.d
`
`whim>o<m._.m222
`
`SEE00mm
`
`m=2_._.w:oz<O:EOEEhwam.50
`@525
`
`
`
`>._ms_mmm<m_m$.on
`
`
`
`AOmHzOO.50msE.
`
`._.__>_mz<m._.wEbom
`
`
`
`@5onmmfiéoo
`
`Io._._>>mO...
`
`mOw
`
`Eammmhé
`
`zmamm
`
`9..6."—
`
`HZmEGmmn_oozm 5.0mCECE;191
`
`
`
`§<mooma._.n_:mmm._.z.
`
`Hemwo>ommDmDOzm
`
`
`
`n=>_<._.mm=>__._.m._._oz<
`
`0:"mEinE
`
`03425“5ms:
`
`
`
`
`
`mmEHSm>>mzmm<mmmm
`
`
`
`Ham—m._.szmo;
`
`EX 1007 Page 12
`
`EX 1007 Page 12
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 12 of 19
`
`5,956,341
`
`EOS-ENTRY
`
`TIME OF DAY -o- LTGS
`
`1402
`
`
`
`
`
`
`
`ENOUEUE RECEIVED SEGMENT
`-SEGMENT POINTER
`- SEGMENT TIMESTAMP
`
`INTO LINE INPUT QUEUE (LIQ)
`
`1403
`
`PROVIDE RECEIVER WITH NEW BUFFER FOR
`NEW SEGMENT OF PACKET
`
`EXIT
`
`FIG. 14
`
`EX 1007 Page 13
`
`

`

`US. Patent
`
`Sep. 21, 1999
`
`Sheet 13 0f 19
`
`5,956,341
`
`ENE
`
`
`
`._.n_._IIImmkz_0ml._.0mwI
`
`
`
`
`
`>m._.zmumn_
`
`
`
`w>._.n__>_mmDmDOO:
`
`
`
`”G:EOEHOmwManama
`
`
`
`
`
`m._.._lun__2<.rmm§_.p|._.0mm|
`
`62H8362Eva:20$22n02mozmafim-
`--a820%é”wmozfioza-
`
`
`
`62-565zoEVEuXmozwmxoiu
`
`
`
`6215mmzoEvxm”xmozESm-
`
`“95moz<E3;05xomxo
`
`E95:5%8%1Vmo
`
`
`
`Axe$511:EStszAl22
`
`204Alxm
`
`vomF
`
`momF
`
`
`
`AXEzmmIAI23
`
`AxemEIAlm:
`
`Em
`
`
`
`m_..0."—
`
`EX 1007 Page 14
`
`
`
`._.zms_omwom<om_o
`
`
`
`om._020m;u:
`
`EX 1007 Page 14
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 14 of 19
`
`5,956,341
`
`PR1
`
`1601
`
`FLUSH (RX, PX) FLAG ON?
`
`RELEASE
`SEGT BUFFER
`
`1603
`
`
`
`
`
`
`
`
`
`PX& RBPT (RX)
`
`CHANGE BASE PACKET INDEX
`PX-RBPT (RX)
`
`PR2
`
`PR4
`
`F.G. 16
`
`EX 1007 Page 15
`
`

`

`US. Patent
`
`Sep. 21, 1999
`
`Sheet 15 0f 19
`
`5,956,341
`
`
`
`ZmVWWMWmmmeVEzm".mpogmgommmm.
`209:“.ca.meEmBm
`
`SEN9ca.xmvmoi;8256:haI
`ca.3E3525BEEwN3<Ez_
`8:
`
`ouE.me58%F+AxeE82
`
`8:
`
`mm;
`
`1..9:“.$.mela205:
`
`”EC
`
`>a:
`
`025mm0&8me52ha
`
`
`
`>t2w52nAxezmmm
`
`ca255251b:2.54m
`
`mmm
`
`
`
`C..0."—
`
`EX 1007 Page 16
`
`EX 1007 Page 16
`
`
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 16 of 19
`PR3
`
`5,956,341
`
`
`
`
`
`STORE RECEIVED SEGMENT INTO PKT STRUCT
`LPT - PKT STRUCT (RX, PX, SX)
`SEGCTR (RX, PX) + 1
`
`1802
`
`RECEIVED SEGMENT LAST OF
`PACKET 2
`
`SET EXPECTED SEGT CTR
`SX + 1 EXPCTR (RX, PX)
`SETEOP (RX, PX) FLAG ON
`
`EOP (RX, PX) FLAG ON ?
`
`SEGCTR (RX, PX) + 1 = EXPCTR
`(RX, PX)
`
`SETPKT-COMPLETE (RX, PX) FLAG ON
`
`
`
`
`
`
`
`
`
`
`
`
`
`PR4
`
`FIG. 18
`
`EX 1007 Page 17
`
`

`

`US. Patent
`
`Sep. 21, 1999
`
`Sheet 17 0f 19
`
`5,956,341
`
`F+xm
`
`xm‘ll
`0meEma
`
`w9:;ca.me5:285“.
`
`
`
`m..50m2;Axn..xmvEv_0<n_lm_w<m
`
`
`
`
`
`
`
`
`
`2_82528mEnDommmmfidm-
`
`85%Emoz<ca.me5255:
`
`onNuE.me25.5:mm.
`
`2092ca.me1.05:Em.
`
`EE"29m
`
`no
`
`H81.50%
`
`
`
`_.A
`
`meSEE
`
`56$QO52“a5.5>55
`
`5%to$9:1me28¢mm.
`
`
`
`2092ma1:;Emsmd
`
`62.xnoXmoz"1AmeEmaEm-
`
`Hezano555mg52E69
`
`NF?
`
`92.
`
`Em:
`
`
`
`ca.me53¢kameEEmZ/‘E-
`
`52-5:AlmmE-§m
`
`BENuE.me525.5;mm-
`
`moENuE.me$25meEm-
`
`
`
`00mOHZ_GENE;mDmDOzm
`
`no?
`
`9..6."—
`
`EX 1007 Page 18
`
`EX 1007 Page 18
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Sep. 21, 1999
`
`Sheet 18 0f 19
`
`5,956,341
`
`:xmH30
`msE.
`
`txm.50-msE.02
`
`on.0.“—
`
`EX 1007 Page 19
`
`
`605.”.+89Aooh88
`
`59%+8:ESAoohuaz
`
`z
`
`G98+”meEm:A92uN.AXEzmzmvoizmmmz
`
`
`
`
`
`405.200.50-m__>__._.
`
`EX 1007 Page 19
`
`
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 19 of 19
`
`5,956,341
`
`PRS
`
`2101
`
`SOO GUEUE = EMPTY 2
`
`Y
`
`
`
`NS N J J J H W
`
`
`
`Y
`
`2102
`
`DEQUEUE PKT LIST FROM SOQ
`
`PKT ROUTING
`
`2103
`
`2104
`
`SEND PACKET TO SWITCH
`
`PRENTRY
`
`FIG 21
`
`EX 1007 Page 20
`
`

`

`5,956,341
`
`1
`METHOD AND SYSTEM FOR OPTIMIZING
`DATA TRANSMISSION LINE BANDWDTH
`OCCUPATION IN A MULTIPRIORITY DATA
`TRAFFICENVIRONMENT
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`This invention deals relates to data communication net
`WorkS. More particularly, the invention relates to a method
`and System for optimizing data line/link occupation in a
`multipriority data traffic environment by using data multi
`plexing techniques of asynchronously transmitted fixed or
`variable length data packets.
`2. Background Information
`Modern digital networks are made to (1) operate in a
`multimedia environment for transporting different kinds of
`digitally encoded data including voice, images, Video signals
`etc. . . , and (2) enable worldwide coverage while ensuring
`compliance with a number of requirements specific to each
`kind of traffics. For instance, while So-called non-real time
`information can be delivered to the corresponding end-user
`with minor time constraint restrictions, real-time type of
`information must be delivered to end-user with predefined
`limited time delay restrictions.
`World-wide coverage is achieved by interconnecting dif
`ferent types of networks including network nodes (i.e.,
`access nodes and transit nodes) connected to each other
`through high Speed lines herein also referred to as linkS.
`Such a composite network is represented in FIG. 1. The
`users get access to the network through ports located in the
`access nodes. The users data are processed by an acceSS
`agent running in the port. The functions of the acceSS agent
`are two-fold: First interpret the user's protocol, and second
`Set the path and route the data through the network.
`Different techniques have been developed for organizing
`the digitally encoded data transport. These include packet
`Switching techniques whereby the digitized data are
`arranged into So-called packets. The packets may either be
`of fixed length, like in the So-called ASynchronous Transfer
`Mode (ATM), or be of variable length (VL) nature.
`A modern international network may be rather complex,
`include leased lines and look like the network of FIG. 2.
`In addition to leased lines, this network would Support
`Frame Relay and ATM networks. The network offers the
`possibility of carrying native Asynchronous Transfer Mode
`(ATM) traffic as well as Variable Length (VL) traffic, which
`VL traffic may include both user's traffic and control traffic.
`A fundamental difference between both VL traffics is that
`while user's traffic needs be vehiculated along a given path
`from a Source end user to a destination end user without
`affecting the network, control traffic should be addressed to
`(a) specific node (S), be decoded therein and control the very
`network architecture and operation. It should also be noted
`that whatever be the type of traffic, data are provided to the
`network at random.
`The above description of networks helps visioning com
`pleX modern network transmission facilities. The description
`also helps understanding that the System should be opti
`mized from a cost efficiency Standpoint. Accordingly, the
`present invention shall focus on link operation efficiency,
`and more particularly optimizing link bandwidth occupa
`tion.
`Let's first recall that links available in the US include
`so-called T1 operating at 1.544 Mbps and T3 at 44.736
`Mbps, while in Europe one may find the E1 at 2.048 Mbps
`and E3 at 34.368 Mbps.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`Now, let's assume a network Service provider requires
`either an access link to a network or a link between two
`nodes at medium rate, say between 2 and 10 Mbps. The
`obvious solution should lead to selecting a T3/E3 link.
`However, such selection would not fit from a cost/efficiency
`Standpoint, bearing in mind the presently practiced tariffs.
`For example, these tariffs in 1995 are in France (in
`KS/month) as indicated hereunder:
`
`50 Km
`
`250 Km
`
`500 Km
`
`E1 =
`E3 =
`
`2
`50
`
`1O
`150
`
`14
`170
`
`Accordingly, Selecting higher than actually required rates
`would be prohibitive and one should find a solution for
`intermediate rates at affordable prices, i.e., optimize band
`width occupation. A first Solution that comes to a network
`designer's mind involves using multiplexing techniques,
`that is, for instance, cover a 10Mbps bandwidth requirement
`with five multiplexed E1 in Europe or seven T1 in the US,
`or multiplex equivalent virtual channels within a high Speed
`link.
`Both hardware and software alternatives may be
`designed. However, hardware solution would suffer the
`drawback of both high development cost and time to market.
`Obviously, one would prefer keeping the already available
`network hardware architectures (e.g., node architectures)
`and shoot for Software modification.
`On the other hand any Software implementation of Such a
`multiplexing System should fit with the Specific traffic
`requirements, including quality of Service traffic granularity,
`etc. . . , in any variable and/or fixed length packet Switching
`network, while requiring minimal development cost for
`implementation in already existing network architectures.
`SUMMARY OF THE INVENTION
`One object of this invention is a method and system for
`optimizing data communication network bandwidth occu
`pation in a multipriority data traffic environment by Simu
`lating a high bandwidth link through multiplexing lower rate
`links or virtual channels, using Software means fitted to
`already existing network architectures.
`Another object is a method and System for Simulating a
`high bandwidth link by multiplexing lower rate links or
`Virtual channels, particularly Suitable for mixed traffic
`including both variable length and fixed length types of
`randomly provided traffics.
`Still another object is a method and System for Simulating
`a high bandwidth link by multiplexing lower rate links or
`Virtual channels and enabling random reservation of one of
`Said links or channels Specifically assigned a given task.
`Still another object is a method and System for Simulating
`a high bandwidth link by multiplexing lower rate links or
`virtual channels fitted to randomly provided traffics with
`several predefined Quality of Service (QoS) parameters.
`A further object is a method and System for Simulating a
`high bandwidth link by multiplexing lower rate links or
`Virtual channels and enabling dynamic network bandwidth
`adaptations through preempt/resume operations.
`A still further object is a method and system for simulat
`ing a high bandwidth link by multiplexing lower rate links
`or virtual channels and enabling dynamic network band
`width adaptation through non disruptive preempt/resume
`operations.
`
`EX 1007 Page 21
`
`

`

`5,956,341
`
`15
`
`25
`
`3
`The above mentioned objects, features and advantages are
`achieved in a method and System for optimizing data trans
`mission link bandwidth occupation in a multipriority data
`traffic environment of a data communication network. A
`high bandwidth link is simulated by multiplexing said traffic
`5
`over lower rate links or virtual channels. The data commu
`nication network includes network nodes interconnected by
`data transmission links, each Said network nodes including
`input and output adapters interconnected to each other
`through a network Switch. The data traffic is randomly
`provided to the network through fixed and/or variable length
`data packets. The method performed in the node transmis
`Sion Side or output adapter comprises the Steps of:
`Storing Said data packets into output queues Selected
`according to a so-called Quality of Service (QoS) based
`on each Said priority levels,
`Splitting each said data packets into So-called Segments,
`each Segment being provided with a Segment header
`including:
`(a) a QoS flag defining the corresponding priority level;
`(b) a packet number reference;
`(c) a segment number reference;
`(d) an end of packet flag for identifying the last Segment
`of a processed packet; and
`(e) validity control bits for header integrity control;
`generating a Link Status Control Word (LSCW) including
`an at least one bit long flag per link, Said flag being used
`to indicate possible link reservation and thus enable on
`request link masking,
`generating a Link Availability Control word (LACW)
`including an at least one bit long flag dynamically
`Settable during operation to indicate whether the cor
`responding link is currently available or busy,
`performing a logical AND operation between said LSCW
`35
`and LACW words for generating a global link avail
`ability control word; and
`monitoring and Scanning Said output queues on decreas
`ing priority order and multiplexing the Segments of Said
`queued packets over Said node output links or virtual
`channels based on Said global link availability control
`word indications.
`These and other objects characteristics and advantages
`will become more apparent from the following detailed
`description of a preferred embodiment of the invention when
`considered with reference to the accompanying figures.
`DESCRIPTION OF THE DRAWING
`FIGS. 1 and 2 are prior art representations of data
`networks wherein the invention is implementable.
`FIG. 3 is a Schematic representation of a network node
`output adapter incorporating the principles of the present
`invention.
`FIGS. 4 is a table of a Transmit (XMIT) Status Byte used
`in the network of FIG. 3.
`FIG. 5 is a table of a Packet Transmit Control Block
`(PXCB) used in the network of FIG. 3.
`FIG. 6 is a block diagram of a transmission flow chart for
`implementing the invention in the system of FIG. 3.
`FIGS. 7 through 10 are detailed flow charts for imple
`menting the invention on the transmission side of a network
`node.
`FIG. 11 is a block diagram Schematically representing the
`invention on a network node receiving Side.
`FIG. 12 shows a representation of a ring organization to
`be used for the reception of a given traffic priority.
`
`4
`FIG. 13 is a Schematic representation of a general flow
`chart for receiving data according to the invention.
`FIGS. 14 through 21 are detailed flow charts for imple
`menting the operations of FIG. 13.
`DESCRIPTION OF A PREFERRED
`EMBODIMENT
`AS already mentioned, the invention should be imple
`mentable on any network link and therefore it should be
`controlled from within any network node, be it an access
`node or an intermediate transit node. In presently available
`digital networks, each node includes Switching means in
`between receive and transmit adapters. In the preferred
`embodiment of this invention, the data arranged into packets
`of either fixed or variable length within the adapters, shall,
`anyway, be split into fixed length segments (except for the
`last Segment of the packet which might be shorter than Said
`fixed segment length), dispatched through the Switching
`means via Switch interface means.
`FIG. 3 shows a schematic representation of a network
`node transmit adapter Side wherein the packetS/Segments are
`provided through Switch interface means 300. The segments,
`if any, may need first be supplied to reassembly unit 301 and
`then routed toward a queuing means 302 Selected according
`to the specific Quality of Service (QoS) assigned to the
`processed data.
`For illustration purposes, four priority levels based on
`Quality of Service (QoS) have been defined which include:
`RT1 and RT2 for real-time type of traffic with two
`different relative priorities, RT1 bearing the highest
`priority level.
`NRT for non-real-time traffic (e.g., pure data for batch
`traffic).
`NR for non-reserved traffic.
`Typically, the highest priority classes (RT1 and RT2) are
`used to transport Voice or Video that does not Suffer being
`delayed above a predefined delay. Non-real-time is used to
`transport interactive data. Non-reserved traffic, used for file
`transfer for instance, is assigned the lowest priority level. In
`addition, Some control data may require being forwarded to
`a general purpose processor 303 controlling Some of the
`network operations. These control data may therefore just
`leave the transmission path at the considered node level.
`The above-mentioned priority criteria, while they com
`plicate the invention mechanism are of a high interest Since
`they introduce important constraints in the final method to
`be developed. For instance the queues shall be served in a
`scheduler 304 with preempt/resume function facilities, to be
`described hereinafter.
`Accordingly, the packets queued therein are split into
`Segments, each Segment being assigned a Segment number
`between Zero and N, N being equal to the maximum
`expected packet length divided by the predefined Segment
`length according to the required bandwidth. The Scheduler
`304 cooperating with a transmission group Segmenting
`device 305 Sequentially Scans the considered packet queued,
`Segments these packets and assign each of these Segments to
`an available output line/virtual channel L1,L2, .
`. . Ln.
`Preferably all multiplexed links should be conFigured at the
`Same transmission rate. To define the channel availability a
`n-bits long Line Availability Control Word (LACW) is
`defined, with each bit position being dynamically Set either
`to one to indicate that the corresponding link (channel) is
`available, or to Zero for unavailable link, i.e. for a channel
`being currently active or transmitting data. Also, any of the
`in link/channels must be momentarily reservable for a spe
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`EX 1007 Page 22
`
`

`

`5,956,341
`
`15
`
`25
`
`S
`cific assignment, be candidate for a preemption operation or
`be physically dropped, etc. Therefore, the Link Availability
`Control Word (LACW) shall be masked by an n-bits long
`Line Status Control Word (LSCW). Each LSCW bit position
`is either Set to one for enabling conditions or to Zero for
`disabling. In a preferred embodiment, the LSCW shall be
`handled by already existing network facility assigned to line
`resources management, while the LACW shall be handled
`by the transmission program to be described herein.
`In operation, LACW and LSCW may handle groups of
`trunks (physical and/or logical) instead of a same trunk. For
`instance, a first part of a given LACW/LSCW might belong
`to a first group, while the Second part would belong to a
`Second group. In this case, each group defines an aggregate
`trunk. At the System transmit Side, the group is Selected
`according to a routing table for a given packet connection
`identification. Accordingly, a so-called group number (gn)
`parameter should be added to the Segment header.
`Finally, a global link availability for the multiplexing
`operations is defined through logical ANDing of both
`LACW with LSCW control words.
`Also, in practice, each of the n links might be taken at
`random based on availability criteria over the total line or
`trunk bandwidth. Accordingly, the LACW might be longer
`than n, and the required in linkS/channels shall be Selected at
`random over the total available channels.
`In operations, the processed data packet is split into
`Segments and each, Segment shall include a 4 bytes long
`header and 60 bytes (or less in case of the last segment of a
`processed packet) be reserved for the segment payload. In
`the preferred embodiment, the Segment header includes:
`QoS: 2 bits coding RT1, RT2, NRT and NR, i.e., 00 is for
`RT1, 01 for RT2, 10 for NRT, and 11 for NR.
`Packet number: 7 bits for coding the packet number.
`Segment Number: 6 bits for coding the segment number
`L. 1 bit set to one to indicate whether the considered
`Segment is the last Segment of the considered packet.
`Time Stamp: 15 bits for time Stamping and transmit time
`and header integrity check.
`By comparing the "L' bit value and corresponding Seg
`ment number, the system shall be able to check whether the
`packet was fully received or not.
`Let's now focus on the transmit operations as imple
`mented in the preferred embodiment of this invention.
`To that end, Some facilities shall be defined. These include
`first a Transmit (XMIT) Status Byte organized as repre
`sented in FIG. 4. Let's assume the XMIT Status Byte is
`Scanned from bit position Zero to bit position Seven. Each bit
`position is used either to define a So-called Transmit In
`Progress (XIP) flag or a so-called Transmit Queue (XQ) flag.
`Each Quality of Service (QoS) 20 is assigned two consecu
`tive bit positions, one for XIP and one for XO. The XIP flag
`bit being OFF indicates that no packet transmission is in
`progress, it is Set ON to indicate that a packet transmission
`has been Started, i.e., at least its first Segment is transmitted.
`55
`The XQ bit being OFF indicates that the related QoS XMIT
`queue is empty, while it shall be ON when at least one packet
`is Stored in corresponding transmit queue. The transmit
`queues are coded as follows:
`
`6
`of the corresponding packets and Segments as well as
`pointers to packet list. It should be noted also that the packet
`list is a list of Sixty Segment pointers, each pointing to a
`buffer where the data of the corresponding packet Segment
`have been received from the node Switch and stored. Each
`buffer has been made Sixty four bytes long, Sixty bytes being
`used for Segment data and four bytes for Segment header.
`The header bytes position are initially empty. The XMIT
`Packet List, Sixty through sixty three are used for Storing
`packet information Such as: packet routing information,
`packet length, packet assignment Such as network control,
`etc..
`Let's now proceed with describing the flow charts detail
`ing the transmission operations as implemented in the pre
`ferred embodiment of this invention. Given these flow
`charts, a person skilled in the programming art shall be able
`to write the programs driving the transmission process
`without any inventive effort being required from his part.
`FIG. 6 shows the general flow diagram for the transmit
`operations. FIG. 6 includes both high priority tasks for End
`Of Segment (EOS) interrupt program 601, and low priority
`tasks 602 for the main steady state program. At End Of
`Segment (EOS interrupt), the QX value related to a link
`index (1X), (see FIG. 7) resets the related link active flag and
`releases the corresponding Segment buffer, before returning
`to the main Steady State program. The Steady State program
`starts with an operation 603 getting a packet from the Switch
`and enqueuing it in the corresponding QoS transmit queue.
`A test 604 is then performed to detect whether a link is
`available. If not, the process loops back to the Start operation
`603, otherwise, the program proceeds to an operation 605 to
`dequeue a Segment from the highest QoS transmit queue and
`calculate the Segment header (i.e., the already mentioned
`four bytes) for feeding the header in the buffer pointed at by
`the Segment pointer of the transmit packet list. Finally, a link
`selection operation 606 is performed for selecting a link
`among the available links and Setting the corresponding link
`active flag to Start Segment transmission prior to looping
`back to the start operation 603.
`FIG. 7 shows the flow chart for the End Of Segment
`interrupt program shown in FIG. 6. First a link index (1x) is
`provided in an operation 701 by hardware means for
`addressing the Link Xmit Control Block (LCB). Then an
`operation 702 resets the Link Active flag accordingly, by
`setting the LACW bit(x) OFF. An operation 703 releases the
`transmitted Segment buffer, prior to going back to the main
`Steady State program 602.
`In FIG. 8, the main Steady State program operation Starts
`with an operation 801 checking whether a packet has been
`received from the node Switch. If yes, then Said packet in an
`operation 802 is enqueued (after getting connection identity
`from the packet header and fetching group number gn from
`a routing table) into one of the queues based on the packet
`QoS parameter. The operation 802 might, naturally be
`combined with any existing mechanism for regulating the
`queues levels. Once a packet is enqueued, the XQ flag bit is
`set ON in the transmit status byte to indicate the presence of
`Said packet in the queue. A test 803 is performed on a global
`link availability control word obtained by ANDing the Link
`Status Control Word with the Link Available Control Word,
`to check whether a link is available for transmission. The
`link availability test 803 is also performed in case of a
`negative response to test 801. Otherwise, the first available
`link is selected and its index is recorded in an operation 804,
`after which the program transferS to processing the transmit
`status byte XP1.
`In FIG. 9, the transmit status byte XP1 is scanned in
`decreasing priority order, i.e. from QoS=00 to QoS=11 and
`
`35
`
`40
`
`45
`
`50
`
`- RT1
`- RT2
`- NRT
`- NR
`
`RealTime 1
`RealTime 2
`Non RealTime
`Non Reserved
`
`(QoS “OO) for highest priority
`(QoS “O1)
`(QoS “10)
`(QoS “11”)
`
`for lowest priority
`
`In FIG. 5, a Packet Transmit Control Block (PXCB)
`includes Six bytes per QoS to keep record of the numbering
`
`60
`
`65
`
`EX 1007 Page 23
`
`

`

`25
`
`7
`more precisely from bit range Zero to seven in the XMIT
`Status Byte. For each priority, two sets of operations 901/
`902 might be performed. The operation 901 indicates a
`packet of related QoS is transmitting. The operation 901
`includes preparing QX indeX for processing the related
`PXCB (continuing transmission) and then branching to
`XP2B. The operation 902 indicates that at least one packet
`is ready for being transmitted from related QoS. A QX index
`is prepared for processing related PXCB (starting transmis
`Sion of a packet). Additionally, if the queue, after extracting,
`is empty, XO flag is Set to Zero. Naturally, if Scanning the
`transmit status byte in decreasing priority order fails to Stop
`on any of Said priorities, the process exits, i.e., returns to the
`operation 801, otherwise it branches either to (XP2A) for a
`new packet, or to (XP2B) for a new segment being
`transmitted, as will be described in FIG. 10.
`In FIG. 10, for a new packet, the related XIP bit is set ON,
`the packet sequence number as indicated by the XPKTN
`counter is incremented for the considered priority queue in
`an operation 1001. Then the segment sequence number
`counter for Said considered priority is initialized in an
`operation 1002. If the packet transmission already started,
`(XP2B entry) the process would only need incrementing the
`Segment Sequence number counter in an operation 1003.
`Then, in both cases, that is either after 1002 or after 1003 the
`proceSS goes to an operation 1004 for dequeuing a Segment
`pointer from the selected packet list XPKT and starts an
`operation 1005 for constructing the four bytes long segment
`header. The quality of service field of said header is filled
`with the considered QoS, the packet number and Segment
`number fields are filled with the content of the packet
`number counter and Segment number counter fields, respec
`tively. The bit L field defining last Segment of packet is either
`Set to Zero or to one accordingly, L= 1 identifying a last
`Segment. Finally the header integrity control byte is calcu
`35
`lated by XORing all other header bytes as already men
`tioned.
`Transmit operations 1006 proceed with starting transmis
`sion position pointed at the XSPTR pointer position. The
`link active flag is set ON in the 1x position of the Link
`Active Control Word.
`A test 1007 is then performed to detect whether the
`current Segment is the last Segment of the packet being
`transmitted. If not, then the proceSS loops back to the
`operation 801 (see FIG. 8). Otherwise, a new packet is made
`ready for transmission in the considered Quality of Service
`and, to that end, the XIP bit is set OFF in the transmit status
`byte accordingly.
`In FIG. 11, receive operations are shown as implemented
`in the preferred embodiment of this invention. First, a
`receive processor 1101 properly resequence and reassembles
`the Segments into their original packet form. This part is the
`most complex of the receive process. Then a routing pro
`ceSSor 1102 di