United States Patent (19J
`Vaid et al.
`
`I 1111111111111111 11111 1111111111 111111111111111 1111111111111111 Ill lllll llll
`US00604 7322A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,047,322
`Apr. 4, 2000
`
`[54] METHOD AND APPARATUS FOR QUALITY
`OF SERVICE MANAGEMENT
`
`5,436,891
`5,548,726
`
`7/1995 Grossman et al ....................... 370/231
`8/1996 Pettus ...................................... 709/221
`
`[75]
`
`Inventors: Aseem Vaid, San Jose; Sanjay
`Sawhney, Santa Clara; Anand K.
`Antur, San Jose; Naveen S. Bisht,
`Campbell, all of Calif.
`
`Primary Examiner-Daniel H. Pan
`Attorney, A.gent, or Firm-Townsend and Townsend and
`Crew LLP
`
`[73]
`
`Ukiah Software, Inc., Campbell, Calif.
`
`(57]
`
`ABSTRACT
`
`[21] Appl. No .. 08/999,096
`
`(22] Filed:
`
`Dec. 29, 1997
`
`[51]
`
`Related U.S. Application Data
`[60] Provisional application No. 60/047,752, May 27, 1997.
`Int. CJ.7
`
`............................ G06F 11/34; G06F 13/36;
`H04L 12/26
`[52] U.S. Cl . ............................ 709/224; 709/225; 714/38;
`714/39; 370/449
`(58] Field of Search ..................................... 709i221, 228,
`709/203, 230, 233, 224, 225; 707/10; 714/38,
`39; 340/825.52; 370/445, 449, 231; 712/1
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`A novel method for a network of computers to improve
`quality of services
`a combination of a bandwidth
`management tool in a firewall. The method ineludes the
`steps of providing a network directory services server pro(cid:173)
`viding 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,
`implementing a quality of service policy for the
`of
`network quality of service devices on the network directory
`the network directory services to
`services server, and
`provide configuration information for the plurality of net(cid:173)
`work quality of service devices, in response to the quality of
`service policy.
`
`5,227,778
`
`7/1993 Vacon et al. ....................... 340/825.52
`
`20 Claims, 11 Drawing Sheets
`
`310
`
`(300
`
`MONITOR
`
`360
`
`370
`
`PROCESSOR
`
`RANDOM
`ACCESS
`MEMORY
`
`320
`
`380
`
`DISK DRIVE
`
`390
`
`NETWORK
`CONNECTION
`
`GRAPHICAL
`INPUT DEVICE
`
`KEYBOARD
`
`350
`
`340
`
`330
`
`4to
`
`INTERNAL /
`NETWORK
`CONNECTION
`
`(400
`
`EXTERNAL
`NETWORK
`CONNECTION
`
`Ex.1018
`APPLE INC. / Page 1 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 1 of 11
`
`6,047,322
`
`130
`
`□ - B
`
`I
`Desktop
`
`A
`~
`
`I
`Desktop
`
`120
`
`1100
`
`150
`
`□-- B
`
`~~~~~///~'~es~top
`.... •······
`Server
`
`160
`
`110
`
`200
`
`220
`
`Web Server
`
`SCHEMA TIC OF QOS SYSTEM DEPLOYED FOR
`AND A PRIVATE WAN
`
`INTERNET ACCESS
`
`FIG. 1
`
`Ex.1018
`APPLE INC. / Page 2 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 2 of 11
`
`6,047,322
`
`310
`
`1300
`
`MONITOR
`
`360
`
`370
`
`PROCESSOR
`
`RANDOM
`ACCESS
`MEMORY
`
`320
`
`380
`
`DISK DRIVE
`
`390
`
`(400
`
`"
`EXTERNAL
`NETWORK -~,
`CONNECTION
`
`NETWORK
`CONNECTION
`
`GRAPHICAL
`INPUT DEVICE
`
`KEYBOARD
`
`350
`
`340
`
`330
`
`FIG.2
`
`INTERNAL /
`NETWORK
`CONNECTION
`
`410
`
`100'/o
`
`FIG.3
`
`Ex.1018
`APPLE INC. / Page 3 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 3 of 11
`
`6,047,322
`
`LIKELY TRAFFIC CLASSES AND POLICIES
`
`Traf fie
`class
`
`Base class
`
`(Traffic type)
`
`[]=App I icat ion
`dependent
`
`Applied Policy Exception Cont ro I
`AC=Admission Control
`Y=A lways
`DP=Drop packets
`N=Ra rely
`P=Po I icy/ App I ica t ion TS= Throttle source
`dependent
`LS=Load Share
`
`Rate Latency
`
`HTTP
`
`HTML
`
`Interactive, [All]
`
`In te roe t ive
`
`GIF, JPEG Bandwidth-intense,
`[In te rac t ive]
`
`RealAudio
`
`Rea 1-T ime,
`[Interactive]
`
`Real time
`Video
`
`Bandwidth-intense,
`Rea 1-T ime,
`[Interactive]
`
`SMTP,
`NNTP
`
`FTP
`
`None
`
`Bandwidth-intense,
`[In te roe t ive]
`
`TELNET
`
`Interactive
`
`DNS
`
`RPC
`
`In te rac t ive
`
`[In te rac t ive]
`
`Novell NCP
`
`[A 11]
`
`y
`
`y
`
`y
`
`y
`
`y
`
`y
`
`y
`
`N
`
`N
`
`p
`
`p
`
`p
`
`p
`
`p
`
`y
`
`y
`
`N
`
`N
`
`y
`
`y
`
`y
`
`p
`
`AC
`p
`
`p
`
`p
`
`y
`
`y
`
`N
`
`p
`
`N
`
`N
`
`p
`
`p
`
`DP
`
`N
`
`N
`
`y
`
`y
`
`y
`
`TS
`p
`
`p
`
`p
`
`N
`
`N
`
`LS
`p
`
`p
`
`p
`
`y
`
`y
`
`N
`
`N N
`
`N
`
`N
`
`N
`
`N
`
`p
`
`y
`
`p
`
`N N
`
`N N
`
`p
`
`p
`
`N
`
`p
`
`FIG.4
`
`Ex.1018
`APPLE INC. / Page 4 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 4 of 11
`
`6,047,322
`
`500
`
`510
`
`520
`
`530
`
`540
`
`NO
`
`560
`
`CLASSIFY TCP CONNECT I ON
`REQUEST
`
`ESTIMATE ROUND-TRIP- TIME
`
`RAMP-UP SOURCE FLOW
`
`DETERMINE ROUND- TR[P- TIME
`
`DETERMINE AVAILABLE
`BANDWIDTH
`
`DELAY ACK SIGNAL/
`MODIFY WINDOW SIZE
`
`FIG.5
`
`Ex.1018
`APPLE INC. / Page 5 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 5 of 11
`
`6,047,322
`
`PARTIALLY
`CLASSIFIED
`(aggregrate or
`defualt class)
`
`Class Estimate
`
`NOT ADMITTED
`
`REQUEST
`DATA
`
`Class Estimate
`
`610
`
`Response Data
`Packets
`
`620
`
`FIN
`
`STATE TRANSITION FOR TCP DATA FLOW REGULATOR
`FIG.6
`
`Ex.1018
`APPLE INC. / Page 6 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 6 of 11
`
`6,047,322
`
`..---------,
`APPLICATION LEVEL FIREWALL AND QoS
`(e.g., HTTP 1proxy, HTTP Lbad Sharing)
`
`: , ....... -, .
`
`:
`
`FIREWALL/QoS SYSTEM
`
`I
`:
`I
`I
`,
`I
`I
`I
`i
`i
`I
`I
`i
`I
`I
`I
`:
`:
`I
`i--;----;----;
`I
`i
`i
`I
`TCP {IP ?TAC~
`I
`i
`i
`I
`( ....... _j
`I
`I
`I
`:
`:
`I
`I
`i
`i
`I
`I
`I
`I
`I
`
`'---l-_ _j ____ .J
`I
`:
`:
`I
`CIRCUIT/PACKET LEVEL FIREWALL AND QoS DRIVER
`(e.g., PORT INSPECTION TCP RA TE CONTROL, QUEUING)
`i
`:
`I
`I
`i ....... _,j
`I
`I
`I
`:
`:
`/
`,
`'
`I
`I
`\
`\
`I
`INTERFACE DRIVER
`\
`;
`:
`\
`;
`:
`\
`;
`;
`\
`:
`:
`:
`
`I
`I
`I
`NETWORK
`I
`I
`I
`J
`/
`PRIY ATE INTERFACE
`
`/
`
`/
`
`~,,'
`
`II
`
`'
`
`\
`PUBLIC INTERF ~CE
`'
`'
`, .....
`i)DATA FLOW
`CONTROL FLOW
`FIN
`(SYN, ACK, REQ. DATA,
`REGULATE ACK)
`
`IMPLEMENTATION ARCHITECTURE - Software Stack and Data Flow
`
`FIG. 7
`
`Ex.1018
`APPLE INC. / Page 7 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 7 of 11
`
`6,047,322
`
`710
`
`0
`
`Untrusted Network
`
`770
`
`770
`
`Trusted Network Firewall Server
`QOS
`
`700
`
`Trusted Network
`IP /IPX
`
`770
`
`770
`
`Di rectory Server
`
`Firewall Server Trusted Network
`QOS
`IP
`
`Trusted Network Firewall Server
`QOS
`
`710
`
`0
`
`Untrusted Network
`
`FIG.8
`
`Ex.1018
`APPLE INC. / Page 8 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 8 of 11
`
`6,047,322
`
`/810
`
`1 800
`~ D Line or Router
`1 □ ~
`!PX
`- ~ 1--------1§]
`■ ~
`
`NetWare Server
`
`1
`
`Ne tRoad Fi reWALL
`QOS Server
`
`Internet
`
`Pure IPX Environmental Configuration
`F JG. 9A
`
`1830
`
`Ne tRoad Fi reWALL
`QOS Server
`
`Dia I-up, ISDN, Lea
`~--~Line or Route
`
`Pure IP Environmental Configuration
`FIG. 9B
`
`Windows 95
`
`Windows NT
`
`□ - a
`
`IP
`
`□-
`B
`Windows 95
`
`UNIX
`
`□-
`B
`
`Ex.1018
`APPLE INC. / Page 9 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 9 of 11
`
`6,047,322
`
`Windows NT
`
`Windows 95
`
`□ □
`- a
`
`UNIX
`
`□-- a
`
`IP
`
`IP
`
`IPX
`
`IP
`
`IPX
`
`-------850
`
`NetRoad FireWALL
`QOS Server
`Dia I-up, ISDN, Lea
`Line or Route
`
`□ - a
`
`Windows 3 .X
`
`Windows 95
`
`Mixed Environment Configuration
`FIG. 9C
`
`=NetWare Administrator
`
`OUkiahsoft
`Ukiahsoftl
`-1NW2
`-8. Adm in
`-~ NW2_SYS
`
`□□□
`
`□□
`
`□
`
`NetRoad Fi reWALL as NDS Object
`F JG. 11A
`
`Ex.1018
`APPLE INC. / Page 10 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 10 of 11
`
`6,047,322
`
`MONITOR
`
`/870
`
`DISK DRIVE
`
`i >
`
`I
`
`•
`KEYBOARD
`
`PROCESSOR
`
`< I
`
`I
`t
`
`NETWORK
`INTERFACE
`
`RANDOM
`ACCESS
`MEMORY
`i
`
`I
`t
`GRAPHlCAL
`INPUT DEVICE
`
`TO TRUSTED NETWORK 1
`
`TO TRUSTED NETWORK 2
`
`TO TRUSTED NETWORK 3
`
`F JG. 10
`
`Ex.1018
`APPLE INC. / Page 11 of 20
`
`

`

`U.S. Patent
`
`Apr. 4, 2000
`
`Sheet 11 of 11
`
`6,047,322
`
`=NetWare Administrator
`
`OUkiahsoft
`£ Ukiahsoft
`..... NW2
`,...8 Adm in
`H~ NW2_SYS I
`~A NetRoad Fi rewa I1/QOS
`
`/890
`
`□□□
`
`II
`
`I
`
`I
`
`Configuration Object Within NetRoad FireWALL
`F JG. 11B
`
`=NetWare Administrator
`
`OUkiahsoft
`£ Ukiahsoft
`-INW2
`-8 Adm in
`~~ NW2_SYS I
`-A NetRoad Fi rewa I l/00S1
`-A NetRoad Fi rewal l/00S2
`
`□□□
`
`II
`
`I
`
`I
`
`Configuration Object Within NetRoad Fi reWALL
`F JG. 11C
`
`Ex.1018
`APPLE INC. / Page 12 of 20
`
`

`

`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(cid:173)
`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 or tele(cid:173)
`communication. More particularly, the present invention
`provides a technique, including a method and system, for
`monitoring and allocating bandwidth on a telecommunica(cid:173)
`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(cid:173)
`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
`numerous years. In the early days, people communicated to
`each other over long distances using "smoke signals."
`Smoke signals were generally used to transfer visual infor(cid:173)
`mation from one geographical location to be observed at
`another geographical location. Since smoke signals could
`only be seen over a limited range of geographical distances,
`they were soon replaced by a communication technique
`known as telegraph. Telegraph generally transferred infor(cid:173)
`mation from one geographical location to another geo(cid:173)
`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(cid:173)
`alized countries today rely heavily upon telephone to facili(cid:173)
`tate communication between businesses and people, in gen(cid:173)
`eral.
`In the 1990s, another significant development in the
`telecommunication industry occurred. People began com(cid:173)
`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(cid:173)
`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(cid:173)
`net "traffic" has increased dramatically in recent years. In
`fact, the increased traffic has caused congestion, which leads
`to problems in responsiveness and throughput. This conges(cid:173)
`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(cid:173)
`ing in telecommunication. As a result, individual users,
`businesses, and others have been spending more time wait(cid:173)
`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 one site to another
`through electronic mail, which is termed "e-mail," may not
`
`5
`
`15
`
`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 amount of 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,
`10 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(cid:173)
`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
`20 like. Drawbacks to these solutions include that they typically
`require additional network service; they also require addi(cid:173)
`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
`25 much faster line or faster modem, another user may still 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
`30 basically going nowhere, or "running" nowhere fast.
`A further problem with quality of service management for
`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
`35 exaggerated. Although WindowsNT is gaining market share,
`there are in excess of three million NetWare servers (and 55
`million NetWare clients) currently in use. Mixed networks at
`both the protocol and operating system platform level,
`therefore, will be around for years to come as well as the
`40 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.
`
`45
`
`SUMMARY OF THE INVENTION
`The present invention relates to a technique including a
`method and system for providing more quality to telecom(cid:173)
`munication services. More particularly, the present inven(cid:173)
`tion relates to quality of service management in a mixed
`50 network environment. More specifically, the invention
`relates to combining computer network firewalls for imple(cid:173)
`menting quality of service management, which can also be
`referred to as "bandwidth" management.
`In a specific embodiment, the present invention provides
`55 a novel method for configuring a plurality of network quality
`of service devices. The method includes the step of provid(cid:173)
`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
`60 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
`65 information for the plurality of network quality of service
`devices, in response to the quality of service policy is also
`provided.
`
`Ex.1018
`APPLE INC. / Page 13 of 20
`
`

`

`6,047,322
`
`4
`Network QoS is managed by managing the resources that
`serve network application traffic, for example. This typically
`includes the following resources: link bandwidth, applica(cid:173)
`tion server bandwidth (CPU) and buffer space on generally
`5 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 number of hops in a route, physical length
`of the route, and extent of congestion in the route. There are
`10 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(cid:173)
`tion provide discrimination of different traffic types and
`15 provide methods for enforcement of traffic flow by manage(cid:173)
`ment to the above resources.
`
`DEFINITIONS
`
`3
`In an alternative embodiment, the present invention pro(cid:173)
`vides an easy to use method for bandwidth management in
`a plurality of networks. The method includes the steps of
`providing a central network server providing directory ser(cid:173)
`vices to the plurality of networks, and configuring band(cid:173)
`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(cid:173)
`vices to provide each of the plurality of network with the
`bandwidth management features.
`Numerous advantages are achieved by way of the present
`invention over pre-existing or conventional techniques. In a
`specific embodiment, the present invention provides a 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 20
`system by way of 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 advantages of the
`invention may be realized by reference to the remaining
`portions of the specification, drawings, and attached docu(cid:173)
`ments
`
`25
`
`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(cid:173)
`posed directory protocol standard.
`DS: Directory Services are global, distributed information
`databases that provide access to network resources, regard-
`30 less of physical location. Such directory services are pref(cid:173)
`erably Novell Directory Services, Microsoft's Active Direc(cid:173)
`tory Services (AD), LDAP and other directory services
`provide central points of administration for entire networks
`of networks. DS typically maintain information about every
`35 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 many individual file 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
`45 defenses provided by the firewall but contains systems that
`are owned by a private organization. Common examples
`would be Web servers and anonymous ftp servers providing
`information to Internet users.
`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.
`
`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- 40
`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(cid:173)
`figurations for embodiments of the present invention;
`FIG. 10 is a block diagram of a system 870 for a directory
`services server according to an embodiment of the present
`invention; and
`FIGS. lla-c illustrate installation of QOS configuration
`information according to an embodiment of the present 55
`invention.
`
`50
`
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`
`An embodiment of the present provides integrated net(cid:173)
`work service policies for firewall platforms. Specifically, the
`present invention provides network or firewall administra(cid:173)
`tors with the ability to implement policy-based schema for
`security and resource management on firewall platforms. In
`a specific embodiment, resource management includes Net(cid:173)
`work Quality of Service (QoS) or "bandwidth" management
`techniques for network servers administered utilizing Direc(cid:173)
`tory Service services.
`
`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-
`60 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
`65 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
`
`Ex.1018
`APPLE INC. / Page 14 of 20
`
`

`

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

`

`6,047,322
`
`7
`A third factor is exception control. The system preferably
`implements exception control when the bandwidth link
`capacity is being exceeded ( congestion) or when a traffic
`class is attempting to exceed it's allotted capacity. Initially,
`the user typically determines what actions to perform when
`there are exceptions, some actions include: admission con(cid:173)
`trol (e.g., deny new requests), service degradation (e.g.,
`dropping packets), sources throttling, traffic redirection
`(load sharing), and the like. Exception control is preferably
`a function of traffic type and policy. For example, the user 10
`may determine that real-time video requires a steady bit-rate
`and thus requires admission control as an exception policy
`when the 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 15
`system to throttle the download sources when the bandwidth
`is low.
`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 20
`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. 25
`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) classes of traffic.
`FIG. 4 illustrates a table summarizing some basic TCP/IP 30
`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 35
`provided, for example. Other combinations or assignments
`of the above policies may be made in alternative embodi(cid:173)
`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 per traffic class
`preferably by using a class of scheduling methods referred
`to as fair queuing algorithms at the firewall. These algo(cid:173)
`rithms mode