US006047322A
`6,047,322
`[11] Patent Number:
`115
`United States Patent
`Vaid et al.
`[45] Date of Patent:
`Apr. 4, 2000
`
`
`[54] METHOD AND APPARATUS FOR QUALITY
`OF SERVICE MANAGEMENT
`
`5,436,891
`5,548,726
`
`7/1995 Grossmanet al. wee 370/231
`8/1996 Petts veescssssssssssessensentensee 709/221
`
`[75]
`
`Inventors: Aseem Vaid, San Jose; Sanjay
`Sawhney, Santa Clara; Anand K.
`Antur, San Jose; Naveen S. Bisht,
`.
`Campbell, all of Calif.
`
`[73] Assignee: Ukiah Software, Inc., Campbell, Calif.
`[21] Appl. No.: 08/999,096
`[22]
`Filed:
`Dec. 29, 1997
`
`[60]
`
`Related U.S. Application Data
`Provisional application No. 60/047,752, May 27, 1997.
`7
`.
`
`.
`
`Primary Examiner—Daniel H. Pan
`Attorney, Agent, or Firm—Townsend and Townsend and
`Crew LLP
`
`ABSTRACT
`[57]
`A novel method for a network of computers to improve
`quality of services using a combination of a bandwidth
`managementtool in a firewall. The method includes the
`steps of providing a network directory services server pro-
`viding network directory services to a plurality of network
`
`servers, each of the plurality of network servers coupled to
`[SL] Unt, C10eeeesreneessestee G06F 11/34; WOLLLene
`one of the plurality of network quality of service devices,
`[52] US.)
`709/224; 709/225: 714/38:
`implementing a quality of service policy for the plurality of
`i , 74/39: 370/4.49
`[58] Field of Search occ: 709/221, 228,|network quality of service devices on the network directory
`709/203, 230, 233, 224, 225; 707/10; 714/38,
`services server, and using the network directory services to
`39; 340/825.52; 370/445, 449, 231; 712/1
`provide configuration information for the plurality of net-
`work quality of service devices, in response to the quality of
`.
`:
`service policy.
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,227,778
`
`7/1993 Vacom et al.
`
`ceccsssssssseesssseeees 340/825.52
`
`20 Claims, 11 Drawing Sheets
`
`MONITOR
`
`ym
`
`
`
`RANDOM
`
` PROCESSOR
`
`DISK DRIVE
`ACCESS
`
`MEMORY
`
`400[
`
`310
`
`
`
`EXTERNAL
`
`
`
`NETWORK
`NETWORK
`
`CONNECTION
`
`CONNECTION
`
`GRAPHICAL
`INPUT DEVICE
`
`KEYBOARD
`
`410
`
`INTERNAL
`
`NETWORK
`
`CONNECTION
`
`1
`
`SAMSUNG 1020
`
`SAMSUNG 1020
`
`1
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 1 of 11
`
`6,047,322
`
`140
`
`Desktop
`
`Telnet ~~.
`ginet=——_ATT
`
`Inbound
`
`110
`
` 130
`
`
`
`180L
`
`
` Access
`link
`(Tt,
`ISDN, Dial-up)
`File server
`490
`
`
`
`Desktop
`
`SCHEMATIC OF QOS SYSTEM DEPLOYED FOR INTERNET ACCESS
`
`AND A PRIVATE WAN
`
`FIG. 7
`
`2
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 2 of 11
`
`6,047,322
`
`MONITOR
`
`/300
`
`360
`
`320
`
`
`
`DISK DRIVE
`
`ACCESS
`MEMORY
`
`390
`
`310
`
`
`PROCESSOR
` RANDOM
`
`
`
`
` 400[
`
`NETWORK neuTpevice||“EYBOAR
`
`
`
`EXTERNAL
`
`CONNECTION
`
`NETWORK
`CONNECTION
`
`INTERNAL
`Nena
`
`410
`
`CONNECTION
`
`FIG. 2
`
`100%
`
`
`
`
`Marketing
`Subnet
`
`3
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 3 of 11
`
`6,047,322
`
`LIKELY TRAFFIC CLASSES AND POLICIES
`
`
`Traffic Applied Policy|Exception ControlBase class
`
`class
`wo,
`(Tratfic type)
`Y=A lways
`AC=Admission Control
`yP
`N=Rarely
`DP=Drop packets
`[J=Application|P=Policy/Application] TS=Throttle source
`dependent
`dependent
`LS=Load Share
`
`Rate Latency
`
`AC
`
`DP
`
`TS
`
`LS
`
`fromefo
`
`HTTP
`
`Interactive,
`
`[All]
`
`GIF,
`
`JPEG
`
`|Bandwidth—-intense,
`[Interactive]
`
`RealAudio
`
`|RealtTime,
`[Interactive]
`
`Bandw idth—- intense,
`Real-Time,
`[Interactive]
`
`SMTP,
`NNTP
`
`None
`
`Bandw idth- intense,
`[Interactive]
`
`4
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 4 of 11
`
`6,047,322
`
` CLASSIFY TCP CONNECTION
`
`500
`
`REQUEST
`
`
`
`
`
`
`
`ESTIMATE ROUND-TRIP- TIME
`
`RAMP-UP SOURCE FLOW
`
`DETERMINE ROUND-TRIP-TIME
`
`DETERMINE AVAILABLE
`BANDWIDTH
`
`5
`
`ROUND-TRIP-TIME>
`AVAILABLE BANDWIDTH
`?
`
`YES
`
`DELAY ACK SIGNAL/
`MODIFY WINDOW SIZE
`
`FIG.5
`
`5
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 5 of 11
`
`6,047,322
`
`SYN
`
`REQUEST
`
`SYN/ACK
`
`
`
`PARTIALLY
`CLASSIFIED
`
`(aggregrate or
`
`CLASSIFIED
`
`(leaf class)
`defualt class)
`
`
`
`
`
`
` ESTABLISHED
`
`
`
`
`Class Estimate
`
`
`Lookup
`
`Class Estimate
`
`610
`
`600
`
`NOT ADMITTED
`
`Response Data
`Packets
`
`
`ACK,
`Estimate
`
`REGULATED
`ACK,
`NATIVE TCP
`
`Estimate
`DATA
`
`
`DATA FLOW
`FLOW
`
`
`ACK, Estimate
`
`
`620
`
`
`
`FIN
`
`
`
`630
`
`
`
`FIN
`
`END DATA
`FLOW
`
`STATE TRANSITION FOR TCP DATA FLOW REGULATOR
`
`FIG. 6
`
`6
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 6 of 11
`
`6,047,322
`
`APPLICATION [EVELFIREWALL AND QoS
`
`pepo
`TCP/IP STACK
`
`|
`
`\
`
`(e.g., HTTP proxy, HTTP ‘poe Sharing)
`|
`
`
` lea = j- - — j- —-——
`CIRCUIT/PACKET LEVEL FIREWALL AND QoS DRIVER
`(e.g., PORT INSPECTION TCP RATE CONTROL, QUEUING)
`
`!
`— i
`\
`i
`a:
`\
`
`FIREWALL/QoS SYSTEM
`
`i
`|
`
`oe=
`
`1
`
`P|
`\
`/
`i
`i
`\
`NETWORK INTERFACE DRIVER
`}
`i
`i
`\
`/
`i
`i
`
`\
`
`\
`
`éf
`
`PRIVATE INTERFACE
`4
`/
`
`2”
`
`i
`:
`;
`
`PUBLIC INTERFACE
`XS
`
`:
`:
`1
`ONTROL FLOW
`(SYN, ACK, REQ. DATA,
`REGULATE ACK)
`
`SA
`
`DATA FLOW
`rIN
`
`IMPLEMENTATION ARCHITECTURE - Software Stack and Data Flow
`
`FIG. 7
`
`7
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 7 of 11
`
`6,047,322
`
`710
`rusted Network700 A.I
`
`|
`
`[Era0
`
`I
`
`i“
`
`
`770
`
`Directory Server
`
`Trusted Network Firewall Server
`
`710
`
`Untrusted Network
`
`FIG. 8
`
`|UntrustedNetwork|
`
`
`
`
`Firewayoover Trusted Network
`IP/IPX
`
`L |
`
`
`
`
`G
`
`Firewall Server Trusted Network
`QOS
`P
`
`8
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 8 of 11
`
`6,047,322
`
`
`
`~ CoS
`NetWare Server
`
`NetRoad F ireWALL
`QOS Server
`
`810
`
`
`
`Pure IPX Environmental Configuration
`FIG. 9A
`
`
`
`Windows 95
`
`Windows NT
`
`je
`
`NetRoad FireWALL
`QOS Server
`
`
`
`ISDN, Leased
`Dial-up,
`Line or Router
`
`
`
`
`
`
`Windows 95
`
`Pure IP Environmental Configuration
`FIG. 9B
`
`9
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 9 of 11
`
`6,047,322
`
`Windows NT
`
`Windows 95
`
`850
`
`
`
`
`
`NetRoad FireWALL
`QOS Server
`ISDN, Leased
`Dial-up,
`Line or Router
`
`
`
`
`
`Mixed Environment Configuration
`FIG. 9
`
`Windows 3.X
`
`Windows 95
`
`coNetWare Administrator
`
`[ |Ukiahsoft
`
`NetRoad FireWALL as NDS Object
`
`FIC. 114
`
`10
`
`10
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 10 of 11
`
`6,047,322
`
`MONITOR
`
`J870
`
`
`
`
`
`
`
`RANDOM
`ACCESS
`MEMORY
`
`
`
`Coe
`DISK DRIVE
`
`
`
`
`
`
`
`NETWORK
`INTERFACE
`
`GRAPHICAL
`INPUT DEVICE
`
`KEYBOARD
`
`
`
`TO TRUSTED NETWORK 1
`
`
`
`TO TRUSTED NETWORK 2
`
`TO TRUSTED NETWORK 3
`
`FIG. 10
`
`11
`
`

`

`U.S. Patent
`
`Apr.4, 2000
`
`Sheet 11 of 11
`
`6,047,322
`
`coNetWare Administrator
`
`[_|Ukiahsoft
`
`&,NetRoad Firewall/QOS
`A,NetRoad Firewall/QOS2
`
`Configuration Object Within NetRoad FireWALL
`
`FIC. 11B
`
`NetWare Administrator
`
`[_|Ukiahsoft
`
`Configuration Object Within NetRoad FireWALL
`
`FIG. 11€
`
`12
`
`12
`
`

`

`6,047,322
`
`1
`METHOD AND APPARATUS FOR QUALITY
`OF SERVICE MANAGEMENT
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`The present application claims priority to pending appli-
`cation Ser. No. 60/047,752, entitled: Method and Apparatus
`for Configuring and Managing Firewalls, filed May 27,
`1997, attorney docket no. 18430-000200. The application is
`herein incorporated by reference for all purposes.
`BACKGROUND OF THE INVENTION
`
`The present invention relates to communication ortele-
`communication. More particularly,
`the present
`invention
`provides a technique, including a method and system, for
`monitoring and allocating bandwidth on a telecommunica-
`tion network at a firewall access point. As merely an
`example, the present invention is implemented on a wide
`area network of computers or workstations such as the
`Internet. But it would be recognized that the present inven-
`tion has a much broader range of applicability including
`local area networks, a combination of wide and local area
`networks, and the like.
`Telecommunication techniques have been around for
`numerousyears. In the early days, people communicated to
`each other over long distances using “smoke signals.”
`Smoke signals were generally used to transfer visual infor-
`mation from one geographical location to be observed at
`another geographical location. Since smoke signals could
`only be seen overa limited range of geographical distances,
`they were soon replaced by a communication technique
`knownastelegraph. Telegraph generally transferred infor-
`mation from one geographical
`location to another geo-
`graphical location using electrical signals in the form of
`“dots” and “dashes” over transmission lines. An example of
`commonly used electrical signals is Morse code. Telegraph
`has been, for the most part, replaced by telephone. The
`telephone was invented by Alexander Graham Bell in the
`late 1800’s to transmit and send voice information using
`electrical analog signals over a telephone line, or more
`commonly a single twisted pair copper line. Most industri-
`alized countries today rely heavily upon telephoneto facili-
`tate communication between businesses and people, in gen-
`eral.
`
`in the
`In the 1990s, another significant development
`telecommunication industry occurred. People began com-
`municating to each other by way of computers, which are
`coupled to the telephone lines or telephone network. These
`computers or workstations coupled to each other can trans-
`mit many types of information from one location to another
`location. This information can be in the form of voice, video,
`and data. Information transmitted over the Internet or Inter-
`net “traffic” has increased dramatically in recent years. In
`fact, the increasedtraffic has caused congestion, which leads
`to problemsin responsiveness and throughput. This conges-
`tion is similar to the congestion of automobiles on a freeway,
`such as those in Silicon Valley from the recent “boom” in
`high technology companies, including companies specializ-
`ing in telecommunication. As a result,
`individual users,
`businesses, and others have been spending more time wait-
`ing for information, and less time on productive activities.
`For example, a typical user of the Internet may spend a great
`deal of time attempting to view selected sites, which are
`commonly referred to as “Websites,” on the Internet.
`Additionally, information being sent from onesite to another
`through electronic mail, which is termed “e-mail,” may not
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`reach its destination in a timely or adequate manner. In
`effect, quality of service of the Internet has decreased to the
`point where some messages are being read at some time
`significantly beyond the time the messages were sent.
`Quality of Service is often measured by responsiveness,
`including the amountof time spent waiting for images,texts,
`and other data to be transferred, and by throughput of data
`across the Internet, and the like. Other aspects may be
`application specific, for example, jitter, quality of playback,
`quality of data transferred across the Internet, and the like.
`Three main sources of data latency include:
`the lack of
`bandwidth at the user (receiving) end, the general conges-
`tion of Internet, and the lack of bandwidth at the source
`(sending) end.
`A solution to decreasing data latency includes increasing
`the bandwidth of the user. This is typically accomplished by
`upgrading the network link, for example by upgrading a
`modem or network connection. For example, upgrading to
`X2 modems, 56K modems, ADSL or DMT modems, ISDN
`service and modems, cable TV service and modems,and the
`like. Drawbacksto these solutions include that they typically
`require additional network service; they also require addi-
`tional hardware and/or software, and further they require
`both the sender and receiver to both agree on using the same
`hardware and/or software. Although one user may have a
`much fasterline or faster modem,another user maystill user
`the same 1200 kbaud modem. So,
`the speed at which
`information moves from one location to another location is
`often predicated on the slowest information which is being
`transferred. Accordingly, users of faster technology are
`basically going nowhere, or “running” nowherefast.
`A further problem with quality of service managementfor
`typical business users is that multiple server platforms have
`to be supported by system administrators. Rumors of the
`death of NetWare as a network server platform have been
`exaggerated. Although WindowsNTis gaining marketshare,
`there are in excess of three million NetWare servers (and 55
`million NetWareclients) currently in use. Mixed networksat
`both the protocol and operating system platform level,
`therefore, will be around for years to come as well as the
`need to improve use of the Internet and its rich information
`resources. From the above,it is seen that what is needed are
`quality of service and bandwidth management tools that
`have the ability to operate in hybrid network environments.
`SUMMARYOF THE INVENTION
`
`The present invention relates to a technique including a
`method and system for providing more quality to telecom-
`munication services. More particularly, the present inven-
`tion relates to quality of service management in a mixed
`network environment. More specifically,
`the invention
`relates to combining computer network firewalls for imple-
`menting quality of service management, which can also be
`referred to as “bandwidth” management.
`In a specific embodiment, the present invention provides
`a novel methodfor configuring a plurality of network quality
`of service devices. The method includes the step of provid-
`ing a network directory services server providing network
`directory services to a plurality of network servers, each of
`the plurality of network servers coupled to one of the
`plurality of network quality of service devices. The method
`also includes the step of implementing a quality of service
`policy for the plurality of network quality of service devices
`on the network directory services server. The step of using
`the network directory services to provide configuration
`information for the plurality of network quality of service
`devices, in response to the quality of service policy is also
`provided.
`13
`
`13
`
`

`

`6,047,322
`
`3
`In an alternative embodiment, the present invention pro-
`vides an easy to use method for bandwidth managementin
`a plurality of networks. The method includes the steps of
`providing a central network server providing directory ser-
`vices to the plurality of networks, and configuring band-
`width management features for the plurality of network
`within the central network server via a remote client. The
`
`method also includes the steps of using the directory ser-
`vices to provide each of the plurality of network with the
`bandwidth managementfeatures.
`Numerous advantages are achieved by wayof the present
`invention over pre-existing or conventional techniques. In a
`specific embodiment, the present invention providesa single
`point or a single region to manage telecommunication traffic
`including directory services and bandwidth management.
`Additionally, in some, if not all embodiments, the present
`invention can be implemented at a single point of access
`such as a computer terminal or firewall,
`for example.
`Furthermore,
`the present invention can be predominately
`software based and can be implemented into a pre-existing
`system by wayof a relatively simple installation process.
`These and other advantages are described throughout the
`present specification, and more particularly below.
`Further understanding of the nature and advantagesof the
`invention may be realized by reference to the remaining
`portions of the specification, drawings, and attached docu-
`ments
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates a typical system including a preferred
`embodiment of the present invention;
`FIG. 2 is a block diagram of a firewall server according
`to a preferred embodiment of the present invention;
`FIG. 3 illustrates an example of a hierarchical model for
`determining bandwidth sharing;
`FIG. 4 illustrates a table summarizing some basic TCP/IP
`traffic classes and typical policies that are applied to them;
`FIG. 5 illustrates a block diagram of a flow chart accord-
`ing to a preferred embodiment;
`FIG. 6 illustrates a state transition diagram for a preferred
`embodiment of the present invention;
`FIG. 7 illustrates an implementation architecture of a
`preferred embodiment of the present invention;
`FIG. 8 illustrates a more detailed embodiment of the
`
`present invention;
`FIGS. 9a—c illustrate typical firewall/QOS system con-
`figurations for embodiments of the present invention;
`FIG. 10 is a block diagram of a system 870 fora directory
`services server according to an embodimentof the present
`invention; and
`FIGS. 11a—c illustrate installation of QOS configuration
`information according to an embodiment of the present
`invention.
`
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`
`An embodiment of the present provides integrated net-
`workservice policies for firewall platforms. Specifically, the
`present invention provides network or firewall administra-
`tors with the ability to implement policy-based schema for
`security and resource managementon firewall platforms. In
`a specific embodiment, resource management includes Net-
`work Quality of Service (QoS) or “bandwidth” management
`techniques for network servers administered utilizing Direc-
`tory Service services.
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Network QoS is managed by managingthe resources that
`serve network applicationtraffic, for example. This typically
`includes the following resources: link bandwidth, applica-
`tion server bandwidth (CPU) and buffer space on generally
`all nodes (end-points, routers and gateways). Typically, data
`through-put is limited by the speed of Internet access links
`and by the server CPU Capacity, and response time is
`determined by the numberof hopsin a route, physical length
`of the route, and extent of congestion in the route. There are
`various other factors that may affect QoS, such as the
`behavior of TCP/IP, severe congestion anywhere in the
`route, prioritization of traffic along the route, etc. To a
`network administrator, embodiments of the present inven-
`tion provide discrimination of different
`traffic types and
`provide methods for enforcementof traffic flow by manage-
`ment to the above resources.
`
`DEFINITIONS
`
`Firewall: A type of security mechanism for controlling
`access between a private trusted network and an untrusted
`outside network (which might be the public Internet or some
`other part of the corporate network within an intranet). It
`typically includes software running on general purpose or
`specialized hardware.
`LDAP: Lightweight Directory Access Protocol, a pro-
`posed directory protocol standard.
`DS: Directory Services are global, distributed information
`databases that provide access to network resources, regard-
`less of physical location. Such directory services are pref-
`erably Novell Directory Services, Microsoft’s Active Direc-
`tory Services (AD), LDAP and other directory services
`provide central points of administration for entire networks
`of networks. DS typically maintain information about every
`resource on the network, including users, groups, printers,
`volumes, and other devices. This information is typically
`stored on a single logical database, thus, instead of logging
`onto manyindividualfile servers, users and network admin-
`istrators log onto the network preferably only once.
`Trusted network: Users on this network are, by default,
`deemed to be trustworthy. Users may be physically on a
`common network, or linked together via a virtual private
`network (VPN).
`DMZ:The ‘Demilitarized Zone’ lies outside the perimeter
`defenses provided by the firewall but contains systems that
`are owned by a private organization. Common examples
`would be Web servers and anonymousftp servers providing
`information to Internetusers.
`Untrusted network: These are outside networks of various
`
`kinds, among the many thousands of networks connected to
`the Internet, or even untrusted networks that may be part of
`other departments or divisions within an organization.
`
`I. SYSTEM OVERVIEW
`
`FIG. 1 illustrates a typical system 100 including an
`embodiment of the present invention. The system 100 is
`merely an illustration and should not limit the scope of the
`claims herein. One of ordinary skill in the art would recog-
`nize other variations, modifications, and alternatives. The
`present invention is embodied as an TrafficWare™ firewall
`server 110 from Ukiah Software, Inc, but can be others.
`System 100 typically includes a file server 120, and a
`plurality of computers 130-150, coupled to a local area
`network (LAN) 160, and other elements. Firewall server 110
`includes a typical connection to a wide area network (WAN)
`170 and to a remote LAN 180 (such as an Intranet) and a
`14
`
`14
`
`

`

`5
`typical network connection 190 to the Internet 200. Attached
`to Internet 200 are Web servers 210 and other computers
`220.
`
`6,047,322
`
`6
`application/protocol (e.g., HTTP, SMTP, FTP, Telnet), data-
`type (e.g., MIME type, HTML, JPEG, RealAudio,
`.WAV,
`.MOV), source/destination identifier (e.g., IP address, user
`name, domain, URQ),
`type (real-time,
`interactive,
`As illustrated, computers such as computer 130, 140, and
`throughput-intense), direction (inbound/outbound), and the
`210 communicate using any one or multiple application
`like. Furthertraffic classes are based upon specifics user(e.g.
`layer protocols such as Telnet, file transfer protocol (FTP),
`President, Shipping Clerk, etc), business group (e.g. Sales,
`Hypertext
`transmission protocol (HTTP), and the like.
`Engineering, Accounting, etc.), priority (e.g. user-
`Further, communication across WAN 170 and across net-
`determined priority levels), direction (e.g.
`inbound,
`work connection 190 implements transport layer protocols
`outbound, customer, guest, etc.).
`such as transmission control protocol (TCP), universal data
`FIG. 3 illustrates an example of a hierarchical model for
`protocol (UDP), and the like. LAN 160 and LAN 180 are
`determining bandwidth sharing. This model is merely an
`preferably based upon network protocols such as Internet
`illustration and should not limit the scope of the claims
`protocol (IP), IPX from Novell, AppleTalk, and the like. As
`herein. As illustrated in FIG. 3, a hierarchical model is
`shown in FIG. 1, network connection 190 may be accom-
`represented as a tree, with the root representing the total
`plished using T1, ISDN, Dial-up, and other hardware con-
`available bandwidth, each branch node representing aggre-
`nections. Computers 120-150 and 210-220 may be any
`gated traffic (meta-traffic classes), and the leaves represent-
`suitable make or model of computer that can be coupled to
`ing individual connections(traffic classes). This model gives
`a network. The system can also include a variety of other
`the user flexibility in defining and implementing a service
`elements such as bridges, routers, and the like.
`policy or multiple service policies. For example, the network
`FIG. 2 is a simplified block diagram of a firewall server
`traffic is first divided in different ways and then the specific
`300 according to an embodimentof the present invention.
`policy refined from a top down approach or amalgamated
`The block diagram is merely an illustration and should not
`from a bottom up approach. This model also provides the
`limit the scope of the claims herein. Firewall server 300
`user with different methodsfor different traffic classes since
`typically includes, among other elements, a monitor 310, a
`it abstracts the policy definition from the enforcement or
`computer 320, a keyboard 330, a graphical input device 340,
`implementation.
`and a network interface 350. Computer 320 includes famil-
`The user typically has competing factors to consider when
`iar computer components such as a processor 360, and
`determining a network QoS policy,
`including bandwidth
`memory storage devices, such as a random access memory
`“guarantees”, latency “guarantees”, and exception control. It
`(RAM) 370, a disk drive 380, and a system bus 390
`should be understood “guarantees”refer to best efforts of the
`interconnecting the above components. A external network
`system to provide service, and does not in any way imply an
`connection 400 and an internal network connection 410 are
`absolute guarantee of service. For example, obviously no
`coupled to network interface 350.
`service can be provided or guaranteed if the network con-
`nection is inoperative, if the Internet Service Provider (ISP)
`A mouse is but one example of graphical input device
`has hardware or software glitches, or there is a general
`340, also knownas a pointing device, a trackball is another.
`Internet crash.
`RAM 370 anddisk drive 380 are examples of tangible media
`A first factor is bandwidth guarantee, or data throughput
`for storage of computer programs such as embodiments of
`guarantee, and how excess bandwidth is shared. Fortraffic
`the herein described invention. Other types of tangible
`classes that have data intensive requirements this is an
`media include floppy disks, removable hard disks, optical
`important criteria. Typically,
`the user initially determines
`storage media such as CD-ROMSand bar codes, semicon-
`what are the minimum bandwidth guarantees that are given
`ductor memories such as flash memories, ASICs, read-only-
`for different traffic classes or for connections relying on data
`memories (ROMS), battery-backed volatile memories, and
`from the differenttraffic classes, before determiningapolicy.
`the like. External network connection 400 typically provides
`As result of the policy,
`the system monitors the actual
`access to external networks such as LAN 180 or Internet
`bandwidth provided to different classes, and preferably if
`200, as described in FIG. 1. Internal network connection 410
`bandwidth is critically low, the system attempts to provide
`typically provides access to internal networks such as LAN
`at
`least
`the minimum bandwidth to the different
`traffic
`160.
`classes.
`Typically, the user also initially determines how excess
`bandwidth is allocated. In a hierarchical model, the user
`provides bandwidth sharing by classes ‘passing up’ or
`‘receiving’ unused bandwidthvia their ‘parents’. As a result,
`closer siblings (traffic classes) typically are able to share
`more bandwidth than distant traffic classes. Alternatively,
`the user may decidethat all leaf classes are allowedto utilize
`excess bandwidth simply based on their priority.
`A second factor is latency guarantees, or response time
`guarantees. Fortraffic classes that are sensitive to delays this
`is an importantcriteria. Typically latency is determined by
`the end-end route rather than the local networkor any single
`gateway. The user typically first determines what are the
`maximum latency guarantees that are given for different
`traffic classes, before determining a policy. In responseto the
`policy,
`the system monitors the bandwidth provided to
`different classes and if a particular traffic class requires a
`quicker response,
`the system attempts to provide more
`bandwidth for that
`traffic class. This monitoring occurs
`preferably when the network is idle or when the network is
`congested.
`15
`
`In a specific embodiment, firewall server 300 includes a
`IBM PC compatible computer having a *586-class based
`microprocessor, such a Pentium™ from Intel Corporation,
`running WindowsNT™ from Microsoft Corporation, and
`TrafficWare™ software from Ukiah Software, Inc. Network
`interface 350 is preferably embodied as a hardwarefirewall
`server also from Ukiah Software, Inc., but can be others.
`FIG. 2 is representative of but one type of system for
`embodying the present invention. It will be readily apparent
`to one of ordinary skill in the art that many system types and
`software configurations are suitable for use in conjunction
`with present invention. The present invention can be in the
`form of software in one embodiment. Alternatively,
`the
`present invention can be a combination of hardware and
`software, which can be further combined or even separated.
`Of course, the particular type of system used in the present
`invention depends highly upon the application.
`I]. OUTBOUND CONTROL
`1. Traffic Classes
`An embodiment of the present invention discriminates
`betweentraffic classes or traffic types. For example, between
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`15
`
`

`

`6,047,322
`
`10
`
`15
`
`The user is preferably provided with three properties:
`bandwidth intensive, real-time and/or interactive, which are
`useful in describing meaningful policies for the different
`traffic classes. Bandwidth-intense traffic classes typically
`require relatively large transmission rates (>50 kbps) for
`each connection over short or long intervals to maintain
`reasonable quality. Interactive classes typically require a low
`latency for all packets to maintain a good response time.
`Real-time classes typically require a very steady rate of data
`delivery (high or low) and generally also low latency. These
`three properties or combinations of them can also be thought
`of as describing generic (base) classesof traffic.
`FIG. 4 illustrates a table summarizing some basic TCP/IP
`traffic classes and typical policies that are applied to them.
`Traffic classes such as HTTP, HTML, GIF, JPEG,
`RealAudio, Realtine Video, SMTP, NNTP, FTP, TELNET,
`DNS, RPC, Novell NCP are shown. To these classes, a base
`class is given. Applied policy and exception control are also
`provided, for example. Other combinations or assignments
`of the above policies may be made in alternative embodi-
`ments of the present
`invention. Further,
`in FIG. 4,
`‘P’
`represents dependence upon a specific policy implemented
`by the user.
`2. Packet Scheduling
`The system allocates output bandwidth pertraffic class
`preferably by using a class of scheduling methods referred
`to as fair queuing algorithms at the firewall. These algo-
`rithms modeltraffic as weighted flows and attempt to ensure
`that service is givento all flows(traffic classes) in proportion
`to their assigned minimum bandwidth. Service typically
`occurs in a round robin fashion while monitoring the maxi-
`mum delays. The system preferably combines such methods
`with priority based schedulers in order to provide latency
`guarantees. These types of outbound flows systemstypically
`apply localized control overall time intervals, are generally
`efficient to implement, provide good link utilization, and do
`not depend on protocol or connection semantics.
`Outbound flow control as described above is preferably
`combined with TCP/IP rate control, described below.
`III. SOURCE CONTROL
`
`In an embodiment of the present invention, rate control
`policies are specified in the form of a bandwidth allocation
`hierarchy, as described above, that defines aggregates of
`traffic according to user-specified parameters (e.g., applica-
`tion type, MIME type or source/destination ID). Further,
`classes are either guaranteed or best-effort.
`As described above, inbound flows may have guaranteed
`classes that include a minimum reserved rate per connection
`and preferably have limits on the total bandwidth used or
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`7
`numberof simultaneous guaranteed connections. Preferably,
`A third factor is exception control. The system preferably
`implements exception control when the bandwidth link
`the remainder of the bandwidth, including any excess from
`capacity is being exceeded (congestion) or whenatraffic
`the guaranteed classes, is dynamically allocated to ‘best-
`class is attempting to exceed it’s allotted capacity. Initially,
`effort’ classes, and new best-effort connections. The specific
`the user typically determines what actions to perform when
`allocation and policy are user definable. In the preferred
`embodiment, classes that flow above their rate limits are
`there are exceptions, someactions include: admission con-
`trol (e.g., deny new requests), service degradation (e.g.,
`subject to rate control preferably if there is demand from
`dropping packets), sources throttling,
`traffic redirection
`siblings, either in the form of new connection requests.
`(load sharing), and the like. Exception controlis preferably
`a function oftraffic type and policy. For example, the user
`may determinethat real-time video requires a steady bit-rate
`and thus requires admission control as an exception policy
`whenthe bandwidth is low, and the user may determine that
`bulk file download services (which are weakly interactive)
`may accommodate some new requests thus instruct
`the
`system to throttle the download sources when the bandwidth
`is low.
`
`IV. TCP/AP FLOW CONTROL
`
`Flow control behavior refers to having end-points adjust
`their transfer rates in response to congestion indicators or
`under gateway control. This applies to both inbound and
`outbound traffic. In the preferred embodiment,
`the end-
`points implement TCP/IP.
`TCP flow control uses the concept of “window size” to
`enable a receiver end-point to indicate how much data the
`source end-point can send in a burst at any given time. To do
`this, the receiver transmits a window size limit to the source.
`TCP utilizes timeouts and duplicate acknowledgmentsig-
`nals (ACKs)to initially determine network congestion, and
`then utilizes the concept of window size as a tool to prevent
`and respond to the congestion, To do all this accurately and
`efficiently, TCP uses a half-dozen subtly intertwined algo-
`rithms. Congestion control is done reactively and coarsely
`and typically involves long delays and retransmitted traffic
`on the netw