Method and apparatus for communicating quality of service information among computer communication devices

[0002] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

[0003] The present invention is related to computer software and more specifically to management software for computer networking equipment.

[0004] Moving information between two points may involve several computer networks. To send data to a remote site, the data may be sent to a router coupled to the sender's network, sent over a network service provider's network, and received by a router at the recipient's network.

[0005] In many cases, the network service provider is a company distinct from the sender or the recipient, such as a telephone company, that provides communication and switching services to the sender and recipient. The routers at the sender and recipient communicate with switches operated by or for the network service provider.

[0006] If the network service provider's network is an ATM network or frame relay network, information may be moved through the use of virtual circuits. A virtual circuit defines a path between two points of a network, and a physical data link may be used to carry the information from multiple virtual circuits.

[0007] The user of a network service provider pays for service meeting certain parameters which define a Quality of Service for the virtual circuit between the sender's router and the network service provider's switch. If the network operated by the network service provider is a frame relay network, these parameters may include one or more of a committed information rate (CIR), committed burst size (Bc), excess burst size (Be), maximum frame size, or priority. The network service provider configures its network to provide service to the user that meets these parameters. One way of configuring the network is by communicating these parameters to one or more of the switches that make up the network service provider's network. Software in the switch attempts to ensure that sufficient capacity exists to meet the requirements defined by the parameters, and attempts to supply up to this capacity as the data received by the router requires.

[0008] If the sender supplies data via a virtual circuit to the network service provider's network that exceeds the Quality of Service for such link for which the user has paid, the response by the network may be uncertain. Therefore, for each virtual circuit the user maintains to the network service provider's switch, the sender will attempt to keep the level of data it sends within the Quality of Service for which it has contracted. Because the sender's router supplies data to the network service provider's network, the sender will configure its routers to prevent them from exceeding the Quality of Service provided by the network virtual circuits.

[0009] To configure the switches of the network service provider, the network service provider supplies the Quality of Service parameters to one or more of its switches. To configure the router, the sender must supply the Quality of Service parameters to its routers.

[0010] Supplying Quality of Service parameters to routers can be a time-consuming and error-prone task. Each router requires certain Quality of Service parameters for each connection in the network. If a Quality of Service parameter for a virtual circuit does not match that of the switch with which the router communicates, either the router will overload the switch with uncertain results, or the router will underutilize the switch, wasting capability for which the user is paying. If the parameters are changed in the switch, the parameters in the router must also be updated to match, resulting in another time-consuming and error-prone task that can cause the same problems described above if not performed properly.

[0011] What is desired are a method and apparatus that ensures the Quality of Service parameters in the switch match the Quality of Service parameters in the router and reduces the effort involved in communicating such parameters. Because of the large installed base of switches and routers, it is desirable that the method and apparatus implemented on a switch operate with routers that do not utilize such method or apparatus, and the method and apparatus implemented on a router operate with switches that do not utilize such method or apparatus.

[0012] A method and apparatus allows Quality of Service parameters to be received by a router or other user equipment devices from a switch or other network equipment device, thereby eliminating the duplicate entry of such parameters to the router and ensuring the parameters in the router match those of the switch. When a new connection is established between the switch and the router, the switch can request the router to send either a list of available protocols or an indication of whether it can support the features of the present invention. If the router detects a protocol that provides the other features of the present invention, the router instructs the switch, either implicitly or explicitly, to communicate using that protocol. The router can then request the switch to send the Quality of Service parameters it has for various virtual circuits. The router can then use the parameters received from the switch for conventional routing operations. In the event that the switch changes its parameters or adds parameters for a new physical or logical connection, the switch informs the router of the change. The router can then request the switch to resend its parameters. The method and apparatus allows the parameters in the router to match the parameters in the switch while reducing the effort to maintain these parameters in the router in a manner that allows equipment to be compatible with other equipment that does not implement the method and apparatus described herein.

[0013] FIG. 1 is a block schematic diagram of a conventional computer system.

[0014] FIG. 2 is a block schematic diagram of a switch and a router that can communicate Quality of Service parameters according to one embodiment of the present invention.

[0015] FIG. 3A is a flowchart illustrating a method of receiving Quality of Service parameters according to one embodiment of the present invention.

[0016] FIG. 3B is a flowchart illustrating a method of providing Quality of Service parameters according to one embodiment of the present invention.

[0017] The present invention may be implemented as computer software on a conventional computer system. Referring now to FIG. 1, a conventional computer system 150 for practicing the present invention is shown. Processor 160 retrieves and executes software instructions stored in storage 162 such as memory, which may be Random Access Memory (RAM) and may control other components to perform the present invention. Storage 162 may be used to store program instructions or data or both. Storage 164, such as a computer disk drive or other nonvolatile storage, may. provide storage of data or program instructions. In one embodiment, storage 164 provides longer term storage of instructions and data, with storage 162 providing storage for data or instructions that may only be required for a shorter time than that of storage 164. Input device 166 such as a computer keyboard or mouse or both allows user input to the system 150. Output 168, such as a display or printer, allows the system to provide information such as instructions, data or other information to the user of the system 150. Storage input device 170 such as a conventional floppy disk drive or CD-ROM drive accepts via input 172 computer program products 174 such as a conventional floppy disk or CD-ROM or other nonvolatile storage media that may be used to transport computer instructions or data to the system 150. Computer program product 174 has encoded thereon computer readable program code devices 176, such as magnetic charges in the case of a floppy disk or optical encodings in the case of a CD-ROM which are encoded as program instructions, data or both to configure the computer system 150 to operate as described below.

[0018] In one embodiment, the switch and the router are each conventional computer systems 150 such as a conventional Pentium II-compatible microcomputer running the Windows 95 operating system commercially available from Microsoft Corporation of Redmond, Wash., along with suitable communication interfaces and software, although other systems may be used.

[0019] Referring now to FIG. 2, a switch and a router are shown according to one embodiment of the present invention. Switch 202 can be a conventional network switch, or any other network equipment device, enhanced as described herein. As used herein, a “network equipment device” is a piece of equipment such as a switch, that supplies wide area network service. Communication interface 240, quality of service storage 250 and switcher 253 perform all the functions of a conventional switch. Communications interface 240 communicates with other switches or other network equipment and routers. Quality of Service storage 250 stores the Quality of Service parameters described above. Switcher 253 controls conventional switching functions.

[0020] Router 204 can be a conventional user router, conventional user bridge, or any other user equipment device, enhanced as described herein. As used herein, a “user equipment device” is a piece of equipment such as a router or bridge that allows computer equipment, which may be connected to a local network, to communicate with a wide area network, such as that used by a network service provider. Communications interface 210, route identifier 224, user interface 226 and Quality of Service status storage 222, described in more detail below, perform the functions of a conventional router. Switch 202 communicates with router 204 via communications line 230 and conventional communications interfaces 210, 240 which perform conventional communications functions between a convention switch and a conventional router. Communications line 230 may consist of one or more virtual circuits. A virtual circuit may be transported over any physical connection made between the switch 202 and the router 204. In one embodiment, switch 202 and router 204 communicate using the conventional frame relay LMI protocol, although other protocols may be used by the present invention. The conventional frame relay LMI protocol is described in Smith, Frame Relay Principles and Applications(1994 Addison Wesly)In one embodiment, virtual circuits are numbered, and virtual circuit number zero is used for communication using the LMI protocol, although other virtual circuit numbers may be used.

[0021] When a data link is established between switch 202 and router 204 communications interfaces 240, 210 detect the link or connection. When communications interface 210 detects the connection, communications interface 210 signals version negotiator 212. Version negotiator 212 produces and sends to communication interface 210 a version status enquiry message, described in more detail below. Communication interface 210 receives the version status enquiry message and transmits it to communication interface 240 via communication line 230. Communication interface 240 receives the version status enquiry message and provides it to version negotiator 242.

[0022] If switch 202 has the capability, version negotiator 242 provides the version of the local management interface or other similar communication management interface software used to transmit information to router 204. Version negotiator 242 builds a version status message described in more detail below, and provides it to communication interface 240. Communication interface 240 transmits the version status message via communication line 230 to communication interface 210. Communication interface 210 provides the version status message to version negotiator 212.

[0023] Version negotiator 212 provides the version status message to protocol discriminator 214. Protocol discriminator 214 identifies from the version status message received whether Quality of Service status messages may be requested and received from the switch 202. In one embodiment, A version status message may include various identifiers of various versions of the protocol supported by the switch 202. If one of the versions supported by the switch 202 supports Quality of Service status messages, protocol discriminator 214 selects such version and provides an indicator of the version selected to version negotiator 212. Version negotiator 212 provides to communication interface 210 a version selection message. Communication interface 210 transmits the version selection command via communication line 230 to communication interface 240. Communication interface 240 provides the version selection command to version negotiator 242. Version negotiator 242 stores an indicator of the version. to be used when communicating using the interface 240 over which the version selection command is received. In one embodiment, the version selection message is communicated as part of one or more of the Quality of Service status enquiry messages described in more detail below.

[0024] If switch 202 does not support the present invention, switch 202 will not respond or will not respond properly to the version status request. In one embodiment, router 204 will repeat the procedure described above a configurable number of times such as twice if no response to the version status request is detected within a configurable amount of time such as twenty seconds. Version negotiator 212 sets timer 213 to detect such period and uses counter 211 to identify the number of retries completed.

[0025] In such event, router 204 will select a protocol that does not support the present invention and will not perform the steps described herein that retrieve Quality of Service parameters from switch 202 and version negotiator 212 stores this protocol. Instead, version negotiator 212 prompts user interface 226 to request via conventional display coupled to input/output 228 or otherwise accept Quality of Service parameters from a user input device such as a conventional keyboard and mouse coupled to input/output 228.

[0026] In one embodiment, version negotiator 212 sets timer 213 for a configurable period such as ten minutes, and repeats the version negotiation described above when the timer 213 period has elapsed. If the switch 202 or router 204 receives a new version of a management protocol, it will be detected upon this periodic renegotiation.

[0027] If a version of the local management interface used by switch 202 does support Quality of Service status messages, version negotiator 212 stores this information, and signals Quality of Service status requester 218.

[0028] Quality of service status requester 218 builds a Quality of Service status enquiry message described in more detail below, and transmits it to status request receiver 243 via communication interfaces 210, 240 and communication line 230. The Quality of Service status enquiry message can specify one or more virtual circuits for which status is requested. Status request receiver 243 passes the Quality of Service status enquiry message to status provider 252. Status provider 252 retrieves from Quality of Service storage 250 the frame relay Quality of Service parameters, such as committed information rate (CIR), committed burst size (Bc), excess burst size (Be), maximum frame size, or priority, associated with the one or more virtual circuits specified and provides to communication interface 240 a Quality of Service status message, described in more detail below, containing this information.

[0029] Communication interface 240 transmits the Quality of Service status message to communication interface 210, which provides it to Quality of Service status receiver 220. Quality of service status receiver 220 stores the Quality of Service parameter information contained in the status message it receives into Quality of Service status storage 222. Quality of Service status storage is used by route identifier 224 to route information using conventional routing methods.

[0030] If a change to a Quality of Service parameter is desired on switch 202, status changer 246 receives the change at input 247, for example from a conventional keyboard and mouse or other device. Status changer 246 stores the change into Quality of Service storage 250 in place of any former value of the parameter. Status changer 246 signals status change provider 244, which provides to communication interface 240 a full status message. In one embodiment, a full status message is a conventional frame relay LMI full status message, modified as described below, and includes an identifier of the one or more virtual circuits for which status has changed.

[0031] Communication interface 240 transmits the full status message to communication interface 210 via communication line 230. Communication interface 210 provides the full status message to status change detector 216. Status change detector 216 signals Quality of Service status requester 218 upon receipt of full status message. Quality of Service status requester 218 requests from version negotiator 212 whether the protocol in use supports Quality of Service status requests. If such status requests are supported by the protocol negotiated as described above, Quality of Service status requester builds and provides a Quality of Service status inquiry as described above. The switch 202 communicates, and router 204 receives and stores for use in routing, the Quality of Service status via a Quality of Service Status message as described above for the virtual circuit identified by the full status message.

[0032] Switcher 253 performs conventional switching functions using quality of service parameters stored in Quality of Service storage 250 via communication-interface 240. Route identifier 224 performs conventional router or bridging functions receiving data from the users network at input/output 229 and passing it to communication interface 210 using the parameters stored in Quality of Service storage 222. Data received from the network equipment device intended for the user network is provided by route identifier 224 to the user network via input/output 224.

[0033] Referring now to FIG. 3A, a method of receiving Quality of Service parameters used to route information is shown according to one embodiment of the present invention. In one embodiment, the steps of FIG. 3A are performed by a user equipment device, such as a conventional router or bridge, modified to perform the method described below, although the steps may be performed by other equipment is well.

[0034] If a new connection is established, it is identified 310. In response to the identification of the new connection, an identifier of a management interface protocol of a switch, such as a version and type of frame relay LMI, is requested from the switch 312. In one embodiment, the request is performed by transmitting a version status inquiry message described in more detail below. In one embodiment, a management interface protocol such as frame relay LMI is identified by a version, and this version is requested as a part of step 312. The version or other identifier of the protocol is received 314. In one embodiment, step 314 may consist of receiving several versions of management interface protocols supported by the switch to which the request in step 312 was sent. In another embodiment, step 314 consists of receiving an identifier of whether “enhanced” LMI is supported. Enhanced LMI is supported if the switch supports providing Quality of Service information as described herein.

[0035] If the version or at least one of the versions received in step 314 can support the transmission of status requests for Quality of Service parameters 316, a version that can support such request is selected 318 from the versions received in step 314. In one embodiment, step 316 may be performed by consulting a lookup table of versions or comparing the versions with a first version number that will support Quality of Service status enquiry messages, and selecting the latest such version. In another embodiment, step 316 is performed by examining a bit or other indicator in the response indicating support of enhanced LMI is provided.

[0036] An indication of the version selected in step 318 is transmitted 320 to instruct the switch that such version is to be used to perform management functions. In one embodiment, step 320 is performed by transmitting one or more messages that are only applicable to the enhanced LMI protocol described in more detail below. Such embodiment may be used where the difference between original LMI and enhanced LMI to the recipient of the transmission performed in step 320 is in receiving messages and responding to them, but not initiating any such messages until after an enhanced LMI message has been received.

[0037] In another embodiment, step 320 may be performed by providing an identifier of a type of protocol and a version number. For example, rather than selecting a particular version, an identifier corresponding to “any version of enhanced LMI” may be provided. In one embodiment, step 320 is provided as a part of step 322, described in more detail below. This means the identifier of the protocol may be transmitted at more than one repetition of step 322 following step 330 as described in more detail below.

[0038] A status request is provided 322. The status request may be a Quality of Service status enquiry message, described in more detail below. A Quality of Service status message, such as that described in more detail below, is received 324 in response to the status requested in step 322. In one embodiment, a timer is set to set an alarm in ten minutes as part of step 324.

[0039] Some or all of the status received in step 324 is stored 326. The status stored in step 326 is used to perform 328 conventional functions performed by conventional user equipment devices, such as routing, bridging or other functions.

[0040] If no version received in step 314 can perform the status requests described in more detailed below 316, Quality of Service parameters may be received 332, for example manually from a user.

[0041] In one embodiment, full status messages may be received. If the full status message is not received 330, the routing or other functions performed in step 328 are performed. If a full status message is received 330, the method continues at step 322. Additionally, if the timer set in step 324 elapses, the method continues at step 330. In one embodiment, routing functions performed in step 328 are performed in parallel with steps 322-326 and 330.

[0042] Referring now to FIG. 3B, a method of providing Quality of Service parameters is shown according to one embodiment of the present invention. The steps shown in FIG. 3B may be performed by a network equipment device such as a switch, although the steps in FIG. 3B may be performed by other devices as well.

[0043] A new connection may be established as described above 350. A version status enquiry message described above may be received 352. A version status message as described in more detail below and including one or more versions identifiers of any management interfaces supported may be provided 354. In one embodiment, several identifiers corresponding to several versions of the management interface supported are provided in step 354.

[0044] In such embodiment, a version selection command may be received 356 specifying one or more of the versions provided in step 354. In another embodiment, the version status message provided in step 354 indicates enhanced LMI, and step 356 involves receiving a command that is only used with enhanced LMI. For example, the version selection command may be received as a Quality of Service status request as part of step 360, causing receipt of the version selection command to be a part of the loop of steps 360-368. The fact that the Quality of Service Status message is sent at all indicates that enhanced LMI should be used, because such a message will only be used when communicating using enhanced LMI. The version or versions selected in step 356 are stored 358 so that they may be used to perform management functions.

[0045] A Quality of Service status enquiry message is received 360. In response to this request, Quality of Service parameters described above are provided 362, for example using a Quality of Service status message described in more detail below. The Quality of Service parameters provided in step 362 may be used to perform functions such as conventional switching functions 364. If a full status is detected 366, a full status message described in more detail below may be provided 368, and the method continues at step 360. In one embodiment, switching functions performed as part of step 364 will continue following step 366 in parallel with steps 360-362.

[0046] The method and apparatus of the present invention may communicate status enquiry messages, full status messages and status messages using any format. Below are described one format of such messages according to one embodiment of the present invention.

[0047] Five types of messages may be sent as described above. User equipment devices send version status enquiry and Quality of Service status enquiry messages, and network equipment devices send version status, full status and Quality of Service status messages.

[0048] Four of the five messages (all but full status messages) contain a first set of nine or ten octets that have similar information in each message. Those octets are described in Table 1 listed below.

[0049] The remaining octets for each message are as follows: For a version status request message, Table 2 describes octets 10-72 (for Cisco LMI and ITU LMI) or 11-73 (for ANSI LMI), which form a version type information indentifier, or version type IE. The values are those of the sender.

[0050] For a version status message, octets 10-72 (Cisco LMI and ITU LMI) or 11-73 (ANSI LMI) are the same as in Table 2 except that the values are those of the sender of the version status message.

[0051] Octets after the first set of nine (Cisco LMI and ITU LMI) or ten (ANSI LMI) octets in a Quality of Service status enquiry message contain one or more Data Link Connection Identifier information elements, or DLCI IEs. A DLDI IE is described in Table 3. The DLCI IE is specified in ITU LMI specification Q.933 for SVCs, and is used in this embodiment for PVCs. Multiple DLCI IEs may be specified in a single message if status for multiple DLCIs is being requested.

[0052] Octets beyond the first nine (Cisco LMI and ITU LMI) or ten (ANSI LMI) octets of a Quality of Service status message contain Quality of Service information elements, or QoS IEs, for each DLCI requested by the Quality of Service status message. There may be multiple QoS IEs appended to the first set of octets described above,

[0053] Full status messages are conventional frame relay LMI full status messages, with bit 7 of the 5^thoctet changed to a value of 1 if Quality of Service parameters for the virtual circuit have changed. All other octets are unchanged from their conventional values.