`
`
`
`[19]
`6,130,880
`[11] Patent Number:
`United States Patent
`
`
`
`
`
`
`
`
`Naudus et al.
`[45] Date of Patent:
`Oct. 10, 2000
`
`
`
`
`
`USOO6130880A
`
`
`
`
`
`
`
`
`[54] METHOD AND APPARATUS FOR ADAPTIVE
`
`
`
`
`
`PRIORITIZATION OF MULTIPLE
`
`
`INFORMATION TYPES IN HIGHLY
`
`
`
`CONGESTED COMMUNICATION DEVICES
`
`
`
`
`
`
`
`
`[75]
`
`
`
`
`
`Inventors: Stanley T. Naudus, Springfield, Va.;
`
`
`
`
`Chester Szczepucha, Grass Valley,
`Callf., Guido M. Schuster, DCS
`
`
`
`
`
`
`Plaines, Ill.
`
`
`
`
`
`
`[73] Assignee: 3Com Corporation, Santa Clara, Calif.
`
`
`
`
`
`
`
`
`
`
`
`[21] APP1~ N03 09/044,958
`
`
`
`[22]
`Filed:
`Mar. 20 1998
`
`,
`
`
`
`
`
`
`
`
`Int. Cl.7 .............................. G01R 31/08; H04] 3/16;
`[51]
`
`
`H04] 3/22
`
`
`
`
`
`
`............................................. 370/235; 370/468
`[52] US. Cl.
`
`
`
`
`
`
`[58] Field of Search ..................................... 370/235, 237,
`
`
`
`
`
`
`370/230, 231, 229, 400, 412, 401, 466,
`
`
`
`468, 465, 477
`
`[56]
`
`
`
`
`References Cited
`
`
`
`
`5,528,595
`
`5,568,525
`5,577,105
`
`5,726,640
`
`
`
`
`
`U~S~ PATENT DOCUMENTS
`
`
`
`
`
`6/1996 Walsh et a1.
`......................... 370/8513
`
`
`
`
`
`
`
`
`10/1996 De Nijs et a1,
`375/356
`
`11/1996 Baum et a1.
`..... 379/93
`
`
`
`
`
`3/1998 Jones et a1.
`........................ 340/825.22
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`Kozen, D., Minsky, Y., and Smith, B., “Efficient Algorithms
`
`
`
`
`
`
`for Optimal Video Transmission”, Proceedings of IEEE
`
`
`
`
`
`
`Computer Society Conference, Mar. 30—Apr. 1, 1998, Snow-
`
`
`
`
`
`bird, Utah, pp. 229 to 238‘
`
`
`
`Primary Examiner—Alpus H, Hsu
`Assistant Examiner—Due H0
`
`
`
`
`
`
`
`
`
`Attorney, Agent, or Firm—McDonnell Boehnen Hulbert &
`
`
`
`Berghoff; Stephen Lesavich
`
`
`ABSTRACT
`[57]
`
`
`
`
`
`
`
`
`A method and apparatus are used in a gateway to discard
`
`
`
`
`
`
`selected frames received with a selected encoded-
`
`
`
`
`
`
`information-type from a communication link with a larger
`
`
`
`
`
`
`bandwidth to avoid overflowing an internal delay variance
`
`
`
`
`
`
`
`removing queue used for protocol translation to a commu-
`
`
`
`
`
`
`
`nication link with a smaller bandwidth. The discarded
`
`
`
`
`
`
`
`frames do not decrease the quality 0T “395131th information.
`
`
`
`
`
`
`
`
`Avisual delay variance removing queue congestion indica-
`
`
`
`
`
`
`
`tor is included to indicate three levels of congestion in the
`
`
`
`
`
`
`
`
`delay variance removing queue for received frames. The
`
`
`
`
`
`
`
`method and apparatus are used in a multimedia gateway
`
`
`
`
`
`which is translating audio/video conferencing protocols
`
`
`
`
`
`
`
`(e.g., H.320, H.323/LAN H.323/PPP and H.324) received
`
`
`
`
`
`
`
`
`from a communication link with a large bandwidth and sent
`
`
`
`
`
`
`to a communication link with a smaller bandwidth.
`
`19 Claims, 13 Drawing Sheets
`
`
`
`
`
`
`28
`
`
`
`RECEIVE MULTIPLE FRAMES FOR A FIRST NETWORK PROTOCOL OVER
`
`
`
`
`
`
`A FIRST COMMUNICATION LINK WITH A FIRST COMMUNICATION
`
`
`
`
`
`BANDWIDTH
`
`
`
`
`OVER A SECOND COMMUNICATION LINK WITH A SECOND BANDWIDTH
`
`STORE THE MULTIPLE FRAMES IN A DELAY VARIANCE REMOVING
`
`
`
`
`
`
`
`QUEUE ON AN INTERNETWORKING DEVICE
`
`
`
`
`
`
`TRANSLATE THE FRAMES IN THE DELAY VARIANCE REMOVING QUEUE
`
`
`
`
`
`
`
`FROM THE FIRST NETWORK PROTOCOL INTO A SECOND NETWORK
`
`
`
`
`
`
`
`PROTOCOL
`
`
`
`
`
`SEND THE TRANSLATED FRAMES AS A SECOND NETWORK PROTOCOL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 1 Of 23
`
`GOOGLE EXHIBIT 1012
`
`GOOGLE EXHIBIT 1012
`
`Page 1 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10,2000
`
`
`
`
`
`Sheet 1 0f 13
`
`6,130,880
`
`
`
`
`FIG. 1
`
`12
`
`N1
`
`
`
`10
`
`
`
`
`
`
`
`
`
`PROTOCOLS
`
`
`g
`
`16
`
`
`N2
`
`PROTOCOLS
`
`2_6_
`
`
`
`
`
`
`
`
`
`Page 2 of 23
`
`Page 2 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10,2000
`
`
`
`
`Sheet 2 0f 13
`
`6,130,880
`
`
`
`
`FIG. 2A
`
`
`
`
`28
`
`/
`
`9
`
`
`
` RECEIVE MULTIPLE FRAMES FOR A FIRST NETWORK PROTOCOL OVER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A FIRST COMMUNICATION LINK WITH A FIRST COMMUNICATION
`
`BANDWIDTH
`
`32
`
`30
`
`
`
`
`
`
`
`
`STORE THE MULTIPLE FRAMES IN A DELAY VARIANCE REMOVING
`
`
`
`
`QUEUE ON AN INTERNETWORKING DEVICE
`
`
`
` TRANSLATE THE FRAMES IN THE DELAY VARIANCE REMOVING QUEUE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FROM THE FIRST NETWORK PROTOCOL INTO A SECOND NETWORK
`PROTOCOL
`
`
`TO A
`
`
`FIG. 23
`
`
`
`
`
`
`
`
`
`
`SEND THE TRANSLATED FRAMES AS A SECOND NETWORK PROTOCOL
`
`
`
`
`
`
`
`OVER A SECOND COMMUNICATION LINK WITH A SECOND BANDWIDTH
`
`Page 3 of 23
`
`Page 3 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10,2000
`
`
`
`
`Sheet 3 0f 13
`
`6,130,880
`
`
`
`
`FIG. 2B
`
`
`
`
`QUEUE CONGESTION
`THRESHOLD EXCEEDED?
`
`
`
`
`
`
`
`
`
`
`
`
`YES
`
`
`
`40
`
`
`
`
`SELECT AN ENCODED-INFORMATION-
`
`
`
`TYPE ENCODED IN A FRAME TO
`
`
`
`
`STORE IN THE DVR QUEUE
`
`
`
`INFORMATION-TYPE
`
`
`
`
`
`DISCARD RECEIVED FRAMES THAT DO
`NOT HAVE THE SELECTED ENCODED-
`
`
`
`
`
`
`
`Page 4 of 23
`
`N0 STOP DISCARDING
`
`
`
`
`
`
`
`FRAMES
`
`
`
`
`IF ENOUGH FRAMES
`
`
`
`
`
`IN THE DVR QUEUE
`
`
`
`HAVE BEEN
`
`PROCESSED SO THE
`
`
`
`DVR QUEUE HAS
`
`REACHED A
`
`PREDETERMINED
`
`
`
`
`
`
`
`
`LENGTH
`
`
`
`44
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 4 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10, 2000
`
`
`
`
`Sheet 4 0f 13
`
`6,130,880
`
`
`
`
`FIG. 3
`
`
`
`FIG
`
`
`4
`
`48
`
`
`
`N1
`
`PROTOCOLS
`
`
`14
`
`
`
`N2
`
`PROTOCOLS
`26
`
`
`
`
`T1
`
`
`
`T2
`
`
`
`T3
`
`
`
`T4
`
`
`
`T5
`
`
`
`T6
`
`
`
`
`
`
`
`
`
`
`
`Page 5 of 23
`
`Page 5 of 23
`
`
`
`
`

`

`
`
`US. Patent
`
`
`
`Oct. 10,2000
`
`
`
`
`Sheet 5 0f 13
`
`6,130,880
`
`
`
`
`
`FIG. 5
`
`
`
`52
`
`
`
`
`
`
`
`
`DETERMINE A FIRST LOCATION IN THE DVR QUEUE CONTAINING A
`
`
`
`
`
`FIRST FRAME WITH A SELECTED ENCODED-INFORMATION-TYPE
`
`
`
`
`
`
`
`
`DETERMINE A SECOND LOCATION IN THE DVR QUEUE CONTAINING A
`
`
`
`
`
`
`SECOND FRAME WITH THE SELECTED ENCODED-INFORMATION-TYPE
`
`SECOND LOCATIONS THEREBY INCREASING SPACE IN THE DVR QUEUE
`
`
`
`
`
`
`
`
`
`DISCARD FRAMES IN THE DVR QUEUE BETWEEN THE FIRST AND
`
`
`
`
`
`
`
`
`
`
`
`
`
`DEIIIIIIIEEI
`
`5°
`
`
`
`FIG. 6
`
`
`
`62
`
`
`
`64
`
`
`
`Page 6 of 23
`
`Page 6 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10,2000
`
`
`
`
`Sheet 6 0f 13
`
`6,130,880
`
`
`
`
`
`
`FIG. 7
`
`66
`
`
`
`
`
`
`
`
`DETERMINE A FIRST LOCATION IN THE DVR QUEUE CONTAINING A
`
`
`
`
`
`FIRST FRAME WITH A SELECTED ENCODED-INFORMATION-TYPE
`
`THEREBY INCREASING SPACE IN THE DVR QUEUE
`
`
`
`
`
`
`
`
`
`DISCARD FRAMES IN THE DVR QUEUE BEFORE THE FIRST LOCATION
`
`
`
`
`
`
`
`
`
`72
`
`
`
`FIG. 8 /
`
`50
`
`
`EIIIIIEEIIII
`
`74
`
`
`
`Page 7 of 23
`
`Page 7 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10, 2000
`
`
`
`
`Sheet 7 0f 13
`
`6,130,880
`
`
`
`
`
`FIG. 9
`
`76
`
`
`
`
`
`
`
`DETERMINE AN AVERAGE TIME WHEN A FRAME WITH A SELECTED
`
`
`ENCODED-lNFORMATION-TYPE IS RECEIVED
`
`
`
`
`
`
`
`
`
`SET A TIMER WITH THE DETERMINED AVERAGE TIME
`
`
`
`WITH THE SELECTED ENCODED-INFORMATION-TYPE IS RECEIVED
`
`
`
`
`
`
`
`
`DISCARD FRAMES RECEIVED UNTIL THE TIMER EXPIRES OR A FRAME
`
`
`
`
`
`
`
`
`O
`
`
`SECONDS
`
`
`86
`
`
`
`0.5
`
`
`SECONDS
`
`
`88
`
`
`
`1.0
`
`
`SECONDS
`
`
`90
`
`
`
`Page 8 of 23
`
`Page 8 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10,2000
`
`
`
`
`Sheet 8 0f 13
`
`6,130,880
`
`
`
`
`
`
`FIG. 11
`
`92
`
`
`
`
`
`
`
`RECEIVE A SELECTION INPUT INDICATING A TIME PERIOD TO RECEIVE
`
`
`
`
`FRAMES OF A NEW SELECTED ENCODED-INFORMATION-TYPE
`
`
`
`
`
`
`
`
`SET A TIMER WITH THE INDICATED TIME
`
`
`
`SELECTED ENCODED-INFORMATION-TYPE UNTIL THE TIMER EXPIRES
`
`
`
`
`
`
`
`
`
`DISCARD ALL FRAMES RECEIVED THAT DO NOT HAVE THE NEW
`
`
`
`
`
`
`
`
`
`
`Page 9 of 23
`
`Page 9 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10, 2000
`
`
`
`
`Sheet 9 0f 13
`
`6,130,880
`
`
`
`
`FIG. 12A
`
`
`
`H.323
`
`
`
`MULTIMEDIA
`
`COMPUTER
`
`
`
`
`
`
`
`18
`
`112
`
`
`
`
`
`
`
`AUDIOIRTP
`
`
`AUDIOI
`
`
`
`
`
`
`INTERFACE
`
`LAN
`
`VlDEOIRTP
` 16
`
` DATA/T.120
`
`
`
` AUDIO PDU
`
`
`VIDEOPDU122
`
`
`INTERFACE
`
`
`DATA PDU1 4
`
`
`
`£9.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SERIAL
`
`
`
`104
`
`
`
`
`MULTIMEDIA COMPUTER
`
`
`
`H.324
`
`
`
`Page 10 of 23
`
`Page 10 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10, 2000
`
`
`
`
`Sheet 10 0f 13
`
`6,130,880
`
`
`
`
`FIG. 12B
`
`
`
`H.323ILAN
`
`
`
`MULTIMEDIA
`
`COMPUTER
`
`
`
`AU DIOIRTP
`
`
`
`LAN
`
`
`INTERFACE
`
`
`
`INTERFACE
`
`
`
`VIDEO PDU 122
`
`
`
`DATA PDU1 4 m
`
`
`
`
`MULTIMEDIA COMPUTER
`
`
`
`H.323lPPP
`
`
`
`Page 11 of 23
`
`Page 11 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10,2000
`
`
`
`
`
`Sheet 11 0f 13
`
`6,130,880
`
`
`
`
`FIG. 13
`
`
`
`/26
`
`
`FIG. 14A
`
`
`
`134
`
`
`
`
`
`
`
`
`IRST LEVEL 0
`
`QUEUE
`
`CONGESTION?
`
`
`
`
`14B
`
`
`
`DISPLAY FIRST
`
`VISUAL INDICATOR IN
`
`
`VISUAL QUEUE
`
`CONGESTION
`
`IND
`T R
`'CA 0
`
`
`
`N0
`
`
`
`o B
`
`FIG.
`
`
`
`Page 12 of 23
`
`Page 12 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10, 2000
`
`
`
`
`Sheet 12 0f 13
`
`6,130,880
`
`
`
`
`
`FIG. 14B
`
`
`SELECT AN
`
`ENCODED-
`INFORMATION-TYPE
`
`
`ENCODED IN A
`
`FRAME TO STORE
`
`
`
`IN THE QUEUE
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISCARD ALL
`
`
`FRAMES IN THE
`
`
`QUEUE THAT DO
`
`
`NOT HAVE
`
`SELECTED
`
`ENCODED-
`INFORMATION-TYPE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SECOND
`
`
`LEVEL OF QUEUE
`
`
`
`CONGESTION?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISPLAY SECOND
`
`NO
`
`
`VISUAL INDICATOR
`
`
`
`
`IN VISUAL QUEUE
`
`CONGESTION
`
`INDICATOR
`
`
`
`
`
`
`SELECT AN
`
`ENCODED-
`
`INFORMATION-TYPE
`
`
`
`ENCODED IN A
`
`
`FRAME TO STORE
`
`
`
`
`
`IN THE QUEUE
`
`
`
`
`
`
`
`DISCARD ALL
`
`ADDITIONAL
`
`
`FRAMES RECEIVED
`
`
`
`
`THAT DO NOT HAVE
`
`
`
`THE SELECTED
`
`
`ENCODED-
`INFORMATION-TYPE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 13 of 23
`
`Page 13 of 23
`
`

`

`
`US. Patent
`
`
`
`
`
`Oct. 10, 2000
`
`
`
`
`Sheet 13 0f 13
`
`6,130,880
`
`
`
`
`FIG. 14C
`
`
`
`QUEUE
`
`
`
`
`
`THIRD
`
`LEVEL OF QUEUE
`
`CONGESTION?
`
`
`
`
`
`
`
`
`
`NO CONGESTION IS
`
`OCCURRING SO NO
`
`CONGESTION
`
`INDICATORS ARE
`
`DISPLAYED
`
`
`
`
`
`Page 14 of 23
`
`
`
`DISPLAY THIRD
`
`
`VISUAL INDICATOR
`
`
`
`IN VISUAL QUEUE
`
`CONGESTION
`
`|ND|CATOR
`
`
`
`DISCARD ALL
`
`
`FRAMES IN THE
`
`
`
`
`DISCARD ALL
`
`ADDITIONAL
`
`
`FRAMES RECEIVED
`
`
`UNTIL A FRAME IS
`
`
`RECEIVED THAT
`
`
`HAS A SELECTED
`
`ENCODED-
`
`
`
`INFORMATION-TYPE
`
`Page 14 of 23
`
`

`

`6,130,880
`
`
`
`
`
`
`
`
`
`10
`
`
`1
`METHOD AND APPARATUS FOR ADAPTIVE
`
`
`
`
`PRIORITIZATION OF MULTIPLE
`
`
`INFORMATION TYPES IN HIGHLY
`
`
`
`CONGESTED COMMUNICATION DEVICES
`
`
`FIELD OF INVENTION
`
`
`
`
`
`
`
`The present invention relates to communication in com-
`
`
`
`
`
`
`
`puter networks. More specifically,
`it relates to adaptive
`
`
`
`
`
`prioritization of multiple information types in highly con-
`
`
`
`gested communication devices.
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`As is known in the art, a variety of computing devices are
`
`
`
`
`
`
`
`often connected together to form a computer network. The
`
`
`
`
`
`
`
`computer network may be a Local Area Network (“LAN”)
`
`
`
`
`
`
`
`
`that connects devices over a small geographical area, or a
`
`
`
`
`
`
`
`
`Wide Area Network (“WAN”) that connects devices over a
`
`
`
`
`
`
`
`large geographical area. The computing devices include
`
`
`
`
`
`video cameras, CD-ROMs, microphones,
`televisions,
`
`
`
`
`
`
`
`
`computers, modems, cable modems and other devices that
`
`
`
`
`
`
`
`send high resolution images, graphical
`images, moving
`
`
`
`
`
`
`
`images, audio and data in addition to textual information.
`
`
`
`
`
`
`Different types of computer networks may be interconnected
`
`
`
`
`
`
`
`
`
`to each other to form larger computer networks (e.g., the
`25
`
`
`
`
`
`
`Internet). The interconnections include LAN-LAN, LAN-
`WAN, WAN-WAN, LAN-WAN-LAN, and other network
`
`
`
`
`
`
`interconnections.
`
`
`
`
`
`
`
`The computing devices transfer multimedia information
`
`
`
`
`
`
`
`
`
`(e.g., audio, video and data) between two or more computer
`
`
`
`
`
`
`networks. Transferring multimedia information between two
`
`
`
`
`
`
`
`
`computer networks may or may not require a reserved bit
`
`
`
`
`
`
`
`rate transmission capacity, and a reserved bandwidth possi-
`
`
`
`
`
`
`
`
`
`bly for the total duration of the transaction. For example,
`multimedia information for a ten second video clip with
`
`
`
`
`
`
`
`
`sound that is being sent between two points in a Ethernet
`
`
`
`
`
`
`
`
`
`
`
`
`
`LAN, requires a significant portion of a 10 Mega-bits-per-
`
`
`
`
`
`
`
`second (“Mbps”) data transmission capacity available on the
`LAN for ten seconds to send the multimedia information.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Gateways connect computer networks using different
`
`
`
`
`
`
`network protocols operating at different
`transmission
`
`
`
`
`
`
`
`capacities. For example, a gateway may have network
`connections to serial data lines connected to one or more
`
`
`
`
`
`
`
`modems. The serial data lines may be used one at a time at
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a relatively low transmission speed (e. g., 14,400 bps, 28,800
`
`
`
`
`
`
`
`
`bps, or 56,000 bps) or can be bundled into a group at a higher
`
`
`
`
`
`
`
`
`transmission speed. In contrast, the gateway may also have
`
`
`
`
`
`
`
`
`one or more LAN connections (e.g., Ethernet, Token Ring,
`
`
`
`
`
`
`
`
`or Fiber Distributed Data Interface (“FDDI”)). The LAN
`
`
`
`
`
`
`
`
`connections are higher speed connections (e.g., 10 Mbps)
`50
`
`
`
`
`
`
`and are shared among multiple devices.
`The gateway translates information contained in a first
`
`
`
`
`
`
`
`
`
`
`
`
`
`protocol being used on a first network connection into a
`
`
`
`
`
`
`
`second protocol being used on second network connection,
`and visa-versa, without undue delay or loss of information.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`For example, a modem operating at 28,800 bps may be using
`the International Telecommunications Union-
`
`
`
`
`
`
`
`
`
`
`Telecommunication Standardization Sector (“ITU-T”, for-
`
`
`
`
`
`
`
`merly known as the CCITT) H.324 audio/video conferenc-
`
`
`
`
`
`
`
`
`ing protocol and a LAN operating at 10 Mbps may be using
`
`
`
`
`
`
`
`the ITU-T H.323 audio/video conferencing protocol for a
`
`
`
`
`
`
`video conferencing connection. A gateway translates H.323
`from the LAN into H.324 for use on the modem, and
`
`
`
`
`
`
`
`
`
`
`
`visa-versa, without undue delay or loss of information even
`
`
`
`
`
`
`
`
`
`
`
`
`
`though the LAN is transmitting information at 10 Mbps and
`
`
`
`
`
`
`the modem is transmitting information at 28,800 bps.
`
`
`
`
`
`
`However, the gateway may also translate H.323 on a LAN
`to H.323 on a serial line using the Point-to-Point Protocol
`
`
`
`
`
`
`
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 15 of 23
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`(“PPP”), H.323 on a LAN to H.320 on an Integrated
`
`
`
`
`
`
`Services Digital Network (“ISDN”) line, or translate H.32x
`on a LAN or a serial line to H.32x on a LAN or a serial line.
`
`
`
`
`
`
`
`
`
`
`
`
`
`The gateway is also responsible for maintaining timing
`
`
`
`
`
`
`relationships and packet sequencing even though a first
`
`
`
`
`
`
`protocol may use timing relationships and a second protocol
`
`
`
`
`may not use timing relationships.
`
`
`
`
`
`
`
`When gateways are used to translate multimedia infor-
`
`
`
`
`
`
`
`mation between two computer networks, logical multimedia
`
`
`
`
`
`
`
`
`
`channels are typically created with separate audio, video and
`
`
`
`
`
`
`
`
`
`data channels. The audio and video channels are typically
`
`
`
`
`
`
`allocated with predetermined, fixed maximum bandwidth.
`
`
`
`
`
`
`
`For example, on a modem connection a audio channel may
`
`
`
`
`
`
`
`
`have a bandwidth of 5,300 bps and a video channel may
`have a bandwidth of 23,500 bps for a multimedia bandwidth
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`of 28,800 bps. A LAN connection may use audio and video
`channels with larger bandwidth allocations since the LAN is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`capable of transmitting information at a much larger overall
`
`
`
`
`
`multimedia bandwidth (e.g., 10 Mbps).
`
`
`
`
`
`
`
`
`There are several problems associated with using gate-
`
`
`
`
`
`
`
`
`ways or other internetworking devices known in the art to
`
`
`
`
`
`
`interconnect computer networks operating at different trans-
`
`
`
`
`
`
`
`
`mission capacities. For example, the logical channels for
`
`
`
`
`
`
`
`larger bandwidth computer network connections (e.g., LAN
`
`
`
`
`
`
`
`connections) are often connected to logical channels for
`
`
`
`
`
`
`smaller bandwidth computer network connections (e.g.,
`
`
`
`
`
`
`modem connections). The larger bandwidth connections
`
`
`
`
`
`
`
`have no way of determining they are connected to smaller
`bandwidth, and more constrained connections. This will
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cause a constant congestion problem on a gateway since the
`
`
`
`
`
`
`
`
`logical channels for the larger bandwidth network is con-
`
`
`
`
`
`
`
`stantly transmitting more information than can be accepted
`
`
`
`
`
`
`
`
`by the lower bandwidth network. In addition, the gateway
`must translate between two or more different protocols for
`
`
`
`
`
`
`
`
`the connections without undue delay or loss of information.
`
`
`
`
`
`
`
`If data is sent along with the audio and video information
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`on a multimedia connection, the congestion problems are
`
`
`
`
`
`
`
`further aggravated on the gateway. The gateway allocates a
`chunk of transmission bandwidth for a logical data channel.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Since the data transmission is typically very bursty,
`the
`transmission bandwidth allocated for data channel is often
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`wasted when no data is being sent. For example, the gateway
`
`
`
`
`
`
`
`
`
`may allocate a 5,000 bps logical data channel for each
`network connection using the data. For a modem with a
`
`
`
`
`
`
`
`
`bandwidth of 28,800 bps, this wastes about 17% of the
`
`
`
`
`
`
`
`
`
`available bandwidth on the modem. This is a significant
`
`
`
`
`
`
`
`waste of bandwidth on a smaller bandwidth network con-
`
`
`
`
`
`
`nection.
`
`
`
`
`
`
`
`
`Another problem is that the gateway must maintain timing
`
`
`
`
`
`relationships and packet sequencing translating between
`
`
`
`
`
`
`certain protocols. The timing relationships and packet
`
`
`
`
`
`
`sequencing must be maintained even though a first protocol
`
`
`
`
`
`
`
`uses timing and a second protocol does not.
`SUMMARY OF THE INVENTION
`
`
`
`
`
`
`
`
`
`In accordance with a preferred embodiment of the present
`
`
`
`
`
`
`
`invention, the congestion problems for translating protocols
`
`
`
`
`
`
`
`
`are overcome. A method and apparatus for adaptively pri-
`
`
`
`
`
`oritizing between two or more encoded-information-types
`received over a communication link in multiple frames in an
`
`
`
`
`
`
`
`
`
`
`
`
`internetworking device (e. g., a gateway) is provided. The
`frames include multiple data bits. The method includes
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`receiving multiple frames for a first network protocol over a
`first communication link having a first communication band-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`width. The multiple frames have one of multiple of encoded-
`
`information-types.
`
`Page 15 of 23
`
`

`

`6,130,880
`
`
`
`
`3
`The received frames are stored in a delay variance remov-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing queue in memory in the internetworking device. The
`
`
`
`
`
`
`
`delay variance removing queue allows the internetworking
`
`
`
`
`
`
`device to compensate for sequencing or timing relationships
`
`
`
`
`
`
`
`
`used in the first network protocol. The delay variance
`
`
`
`
`
`
`
`removing queue is also used as a buffer if it is not necessary
`
`
`
`
`
`
`
`
`to maintain timing relationships between two similar pro-
`
`
`
`
`
`
`
`
`
`tocols. The frames from the delay variance removing queue
`
`
`
`
`
`
`
`are translated into a second network protocol. Periodically a
`
`
`
`
`
`
`test is completed to determine if a number of frames arriving
`
`
`
`
`
`
`
`on the first network connection exceeds a predetermined
`
`
`
`
`
`
`
`
`queue congestion threshold. The delay variance queue can
`be overflowed if the first communication link has a larger
`
`
`
`
`
`
`
`
`bandwidth than the second communication link. If the queue
`
`
`
`
`
`
`
`
`
`
`
`
`congestion threshold is exceeded, an encoded-information-
`
`
`
`
`
`
`
`
`type encoded in a frame is selected to store in the delay
`
`
`
`
`
`
`
`variance removing queue. Received frames are discarded
`
`
`
`
`
`
`
`that do have the selected encoded-information-type until
`
`
`
`
`
`
`
`
`enough frames have been processed so the delay variance
`
`
`
`
`
`
`
`removing queue has reached a predetermined length. The
`
`
`
`
`
`
`
`
`
`translated frames for the second network protocol are sent
`
`
`
`
`
`
`
`over a second communication link having a second com-
`munication bandwidth,
`the second communication band-
`
`
`
`
`
`
`width being less than the first communication bandwidth.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In another embodiment of the present invention, received
`frames that do not have the selected encoded-information-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`type are discarded and not stored in the delay variance
`
`
`
`
`
`
`
`removing queue. In yet another embodiment of the present
`
`
`
`
`
`invention, a new encoded-information-type may be selected
`
`
`
`
`
`
`
`
`
`for a specified time period (e.g., to send data) and all frames
`
`
`
`
`
`
`
`
`that do not have the new encoded-information-type are
`
`
`
`
`
`
`discarded during the specified time period.
`
`
`
`
`
`
`
`
`The method and apparatus allow received frames with a
`
`
`
`selected-information-type to be discarded in a multimedia
`
`
`
`
`
`
`
`gateway without significantly affecting the quality of infor-
`
`
`
`
`
`
`
`mation when a first network protocol (e.g., H.323/LAN) is
`
`
`
`
`
`
`
`translated into a second network protocol (e.g., H.320,
`
`
`
`
`
`
`
`H.323/PPP, H.324, H.32x, etc.). The discarding of informa-
`
`
`
`
`
`
`
`
`
`tion is often necessary since frames are arriving on a
`communication link with larger bandwidth faster than they
`
`
`
`
`
`
`
`
`can be translated and sent on a communication link with
`
`
`
`
`
`
`
`smaller bandwidth.
`
`
`
`
`
`
`
`
`
`
`The foregoing and other features and advantages of a
`
`
`
`
`
`
`
`preferred embodiment of the present invention will be more
`
`
`
`
`
`
`
`readily apparent from the following detailed description,
`
`
`
`
`
`
`
`which proceeds with references to the accompanying draw-
`1ngs.
`
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`
`
`
`
`
`
`
`
`
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`
`
`FIG. 1 is a block diagram of a computer network used to
`
`
`
`
`
`implement a preferred embodiment of the present invention;
`
`
`
`
`
`FIGS. 2A and 2B are a flow diagram illustrating a method
`
`
`
`
`
`
`
`for adaptively prioritizing between two or more information
`types received on a communication link;
`
`
`
`
`
`
`
`
`
`FIG. 3 is block diagram illustrating a packet synchroni-
`
`
`
`zation in an internetworking device;
`
`
`
`
`
`FIG. 4 is a block diagram illustrating a delay variance
`
`
`
`
`
`removing queue in an internetworking device;
`
`
`
`
`
`
`FIG. 5 is a flow diagram illustrating a first method of
`
`
`
`
`
`
`
`discarding frames from a delay variance removing queue;
`
`
`
`
`
`
`
`FIG. 6 is a block diagram illustrating the method of FIG.
`
`
`
`
`
`
`
`FIG. 7 is a flow diagram illustrating a second method of
`
`
`
`
`
`
`
`discarding frames from a delay variance removing queue;
`
`
`
`
`
`
`
`FIG. 8 is a block diagram illustrating the method of FIG.
`
`
`
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`5;
`
`7;
`
`Page 16 of 23
`
`
`4
`
`
`
`
`
`
`FIG. 9 is a flow diagram illustrating a method for dis-
`
`
`
`carding received frames;
`
`
`
`
`
`
`FIG. 10 is a block diagram illustrating the method of FIG.
`
`
`
`
`
`
`FIG. 11 is a flow diagram illustrating method for receiving
`
`
`
`
`
`
`frames with a new selected information type;
`
`
`
`
`
`FIG. 12A is a block diagram illustrating a protocol
`
`
`translation system;
`
`
`
`
`
`
`FIG. 12B is a block diagram illustrating another protocol
`
`
`translation system;
`
`
`
`
`
`
`FIG. 13 is a block diagram illustrating a visual queue
`
`
`
`congestion indicator; and
`
`
`
`
`
`
`
`
`FIGS. 14A, 14B and 14C are a flow diagram illustrating
`
`
`
`
`
`
`a method for displaying a visual indication of congestion in
`a queue.
`
`
`DETAILED DESCRIPTION OF A PREFERRED
`
`
`EMBODIMENT
`
`
`
`
`Protocol Translation System
`
`
`
`
`
`
`FIG. 1 is a block diagram of a computer network 10 used
`
`
`
`
`
`
`
`to implement a preferred embodiment of the present inven-
`
`
`
`
`
`
`
`tion. Computer network 10 includes a first computer net-
`
`
`
`
`
`
`work 12 and a second computer network 14 interconnected
`
`
`
`
`
`
`by an InterNetworking Device 16 (“IND”). However, more
`
`
`
`
`
`
`
`or fewer computer networks could be interconnected by IND
`
`
`
`
`
`
`
`
`16 and the invention is not limited to interconnecting two
`
`
`
`
`
`
`computer networks. In addition, computer network 10 may
`
`
`
`
`
`
`
`
`include additional network devices (i.e., other than IND 16)
`and additional network nodes which are not shown in FIG.
`
`
`
`
`
`
`
`
`
`1.
`
`9;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IND 16 is also called an “InterWorking Unit” (“IWU”), an
`
`
`
`
`
`
`“Intermediate System” (“IS”) or a “gateway.” IND 16 has
`
`
`
`
`
`
`multiple communication links 18 to first computer network
`
`
`
`
`
`
`
`12 and multiple communication links 20 to second computer
`
`
`
`
`
`
`network 14 (illustrated as single connections 18 and 20 in
`
`
`
`
`
`
`
`
`FIG. 1). There may also be multiple virtual communication
`
`
`
`
`
`
`
`
`
`channels over the communication links (18, 20) (e.g., sepa-
`
`
`
`
`
`
`
`
`
`rate virtual channels for audio, video and data information).
`IND 16 has a software server 22 with a listing of network
`
`
`
`
`
`
`
`
`
`
`
`
`
`protocols 24 for first computer network 12 and a listing of
`
`
`
`
`
`
`
`network protocols 26 for second computer network 14. IND
`16 uses software server 22 to translate network protocols
`
`
`
`
`
`
`
`that arrive on a communication link from one computer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network into a protocol for another computer network
`without undue delay or loss of information.
`
`
`
`
`
`
`
`
`
`
`
`
`
`For example, a first network protocol P1 that arrives over
`a first communication link 18 with a first communication
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`bandwidth (e.g., 10 Mbps) from first computer network 12
`is translated with software server 22 into a second network
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`protocol P2 for second computer network 14 using protocol
`listings 24 and 26. Protocol P2 is sent over a second
`
`
`
`
`
`
`
`
`
`communication link 20 to second computer network 14.
`
`
`
`
`
`
`
`Second communication link 20 may have a second commu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nication bandwidth (e. g., 28,800 bps) that is smaller than the
`first communication bandwidth but protocol P2 is sent
`
`
`
`
`
`
`
`without undue delay or loss of information.
`
`
`
`
`
`
`
`
`
`
`
`
`An operating environment for IND 16 of the present
`
`
`
`
`
`
`
`invention includes a processing system with at least one high
`
`
`
`
`
`
`speed Central Processing Unit (“CPU”), in conjunction with
`
`
`
`
`
`
`
`
`a memory system. Although described with one CPU, alter-
`
`
`
`
`
`natively multiple CPUs may be used.
`
`
`
`
`
`
`
`
`The memory system includes main memory and second-
`
`
`
`
`
`
`
`ary storage. The main memory is high-speed Random
`
`
`
`
`
`
`
`Access Memory (“RAM”) and Read Only Memory
`
`
`
`
`
`
`
`
`(“ROM”). Main memory can include any additional or
`
`
`
`
`
`
`alternative high-speed memory device or memory circuitry.
`
`
`
`
`
`
`Page 16 of 23
`
`

`

`10
`
`
`
`
`
`
`
`
`5
`
`
`
`
`
`
`
`
`
`
`Secondary storage takes the form of long term storage, such
`
`
`
`
`
`
`
`
`as ROM, optical or magnetic disks, organic memory or any
`
`
`
`
`
`
`
`
`other volatile or non-volatile mass storage system. Those
`
`
`
`
`
`
`
`
`
`
`skilled in the art will recognize that the memory system can
`
`
`
`
`
`
`comprise a variety and/or combination of alternative com-
`ponents.
`
`
`
`
`
`
`
`
`In accordance with the practices of persons skilled in the
`
`
`
`
`
`
`
`art of computer programming,
`the present
`invention is
`
`
`
`
`
`
`
`described below with reference to acts and symbolic repre-
`
`
`
`
`
`sentations of operations that are performed by the processing
`
`
`
`
`
`
`
`system, unless indicated otherwise. Such acts and operations
`
`
`
`
`
`
`
`are referred to as being “computer-executed” or “CPU-
`executed.”
`
`
`
`
`
`
`
`
`
`
`the acts and symbolically
`It will be appreciated that
`
`
`
`
`
`
`represented operations include the manipulation of electrical
`
`
`
`
`
`
`
`
`signals by the CPU. The electrical system represent data bits
`
`
`
`
`
`
`which cause a resulting transformation or reduction of the
`
`
`
`
`
`
`
`electrical signal representation, and the maintenance of data
`
`
`
`
`
`
`
`bits at memory locations in the memory system to thereby
`
`
`
`
`
`
`
`reconfigure or otherwise alter the CPU’s operation, as well
`
`
`
`
`
`
`
`
`as other processing of signals. The memory locations where
`
`
`
`
`
`
`
`
`
`data bits are maintained are physical locations that have
`
`
`
`
`
`
`particular electrical, magnetic, optical, or organic properties
`
`
`
`
`corresponding to the data bits.
`
`
`
`
`
`
`
`
`
`The data bits may also be maintained on a computer
`
`
`
`
`
`
`
`readable medium including magnetic disks, optical disks,
`
`
`
`
`
`
`
`
`
`and any other volatile or non-volatile mass storage system
`
`
`
`
`
`
`
`readable by the computer. The computer readable medium
`
`
`
`
`
`includes cooperating or interconnected computer readable
`
`
`
`
`
`
`
`media, which exist exclusively on the processing system or
`
`
`
`
`
`
`be distributed among multiple interconnected processing
`
`
`
`
`
`
`
`
`systems that may be local or remote to the processing
`system.
`
`
`
`
`
`
`Adaptive Prioritization of Multiple Information Types in a
`Protocol
`
`
`
`
`
`
`FIGS. 2A and 2B are a flow diagram illustrating a method
`
`
`
`
`
`
`
`
`28 for prioritizing between two or more encoded-
`
`
`
`
`
`
`information-types for a selected network protocol received
`
`
`
`
`
`
`in frames over a communication link on an internetworking
`device such as IND 16. The frames include multiple data
`
`
`
`
`
`
`
`
`bits. At step 30 in FIG. 2A, multiple frames arc received for
`
`
`
`
`
`
`
`
`
`a first network protocol over a first communication link
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`having a first communication bandwidth. The multiple
`
`
`
`
`
`frames include multiple encoded-information-types (e.g.,
`
`
`
`
`
`
`
`
`
`video codec frames, audio codec frames and data frames).
`
`
`
`
`
`
`
`For selected protocol translations (e.g., H.3239H.324) that
`
`
`
`
`
`
`
`require timing be maintained, received frames are stored in
`
`
`
`
`
`
`
`a Delay Variance Removing (“DVR”) queue in memory in
`
`
`
`
`
`
`
`
`
`the internetworking device at step 32. The DVR queue
`
`
`
`
`
`
`
`allows IND 16 to compensate for packet sequencing and
`
`
`
`
`
`
`
`timing relationships during protocol translation. The frames
`from the DVR queue are translated into a second network
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`protocol at step 34. In a preferred embodiment of the present
`invention, the second communication bandwidth is less than
`
`
`
`
`
`
`
`the first communication bandwidth but the translated frames
`
`
`
`
`
`
`
`
`are sent without undue delay or
`loss of information.
`
`
`
`
`
`
`
`
`
`However,
`the communication bandwidths may also be
`
`
`
`
`
`
`
`equivalent on both the first and second communication links.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Periodically, a test is completed at step 38 (FIG. 2B) to
`determine whether a number of frames arriving on the first
`
`
`
`
`
`
`
`
`
`
`
`
`
`network connection exceeds a predetermined queue conges-
`tion threshold. If the congestion threshold is exceeded, an
`
`
`
`
`
`
`
`
`
`
`encoded-information-type encoded in a frame is selected at
`step 40 to store in the DVR queue. Frames that do not have
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the selected encoded-information-type are discarded at step
`
`
`
`
`
`
`
`
`
`42 until enough frames in the DVR queue are processed so
`
`
`
`
`
`
`
`the DVR queue reaches a predetermined length. When
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 17 of 23
`
`6,130,880
`
`
`
`
`6
`
`
`
`
`
`
`
`
`
`enough frames in the DVR queue are processed so the DVR
`
`
`
`
`
`
`
`queue reaches a predetermined length at step 38, discarding
`of frames that do not have the selected encoded-information-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`type is discontinued at step 44. Translated frames for the
`
`
`
`
`
`
`
`
`se