Systems and methods for analyzing network traffic

[0002] The present invention relates generally to networks and, more particularly, to forecasting traffic flows on a network.

[0003] Spurred by technological advances, the telecommunications industry has experienced tremendous growth over the last decade. This is especially true of networks that carry packetized data, such as those networks that make up the Internet. Within the Internet sector, various Internet Service Providers (ISPs) have reported a yearly quadrupling of traffic. As a result, the traffic on networks is rapidly exceeding system capacity. Network planners, therefore, are constantly faced with the issue of whether the network has adequate capacity to support future traffic requirements.

[0004] Traffic forecasts are a particularly important component of the capacity planning and budget modeling functions performed by network planners. Given a particular network topology, a network planner uses a traffic forecast to evaluate anticipated circuit utilizations. These circuit utilizations may then be translated into circuit requirements. The network planner may also use a traffic forecast to evaluate various topologies and establish a network build-out plan according to this evaluation.

[0005] In general, a network planner is provided with traffic growth estimates. These growth estimates are then combined with actual collected traffic flow statistics to assemble a predictive traffic model.

[0006] Typically, the most time-consuming part of the capacity planning and budgeting process is the construction of a traffic matrix that represents the traffic forecasts. Most ISPs serve millions of sources and destinations of traffic, known as hosts. Consequently, a traffic matrix that captures enough information to be meaningful in a network planning context may be very large.

[0007] One drawback with conventional traffic forecasting methodology is that the mechanics involved in creating the traffic matrices are not systematic. As a result, the generated circuit utilization data is often unreliable.

[0008] Therefore, a need exists for a system and method that provide a systematic approach to traffic forecasting.

[0009] Systems and methods consistent with the present invention address this and other needs by combining observed traffic statistics and projected traffic data in a systematic manner to generate a traffic matrix. The traffic matrix may then be manipulated to generate expected flows to/from each of the nodes in a network.

[0010] In accordance with the purpose of the invention as embodied and broadly described herein, a method for analyzing traffic in a network having a plurality of nodes is provided. The method includes forecasting traffic transmitted to and from each of the plurality of nodes based on observed traffic statistics and an estimated growth. The method also includes generating a traffic matrix using the observed traffic statistics and the forecasted traffic associated with each of the plurality of nodes and determining projected traffic between each of the plurality of nodes using the generated traffic matrix.

[0011] In another aspect of the present invention, a system for analyzing traffic in a network comprising a plurality of nodes includes a memory configured to store observed traffic statistics. The system also includes a processor configured to forecast traffic transmitted to and from each of the plurality of nodes based on observed traffic statistics and an estimated growth. The processor is also configured to generate a traffic matrix using the observed traffic statistics and the forecasted amount of traffic associated with each of the plurality of nodes and determine projected traffic between each of the plurality of nodes using the generated traffic matrix.

[0012] The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention and, together with the description, explain the invention. In the drawings,

[0013] FIG. 1 illustrates an exemplary system consistent with the present invention;

[0014] FIG. 2 is a block diagram of an exemplary system in which systems and methods consistent with the present invention may be implemented;

[0015] FIG. 3 is a flowchart of processing, consistent with the present invention, for determining projected traffic flows in a network; and

[0016] FIG. 4 is a flowchart of processing, consistent with the present invention, for using a traffic matrix to apportion traffic flows in a network.

[0017] The following detailed description of the invention refers to the accompanying drawings. The same reference numbers in different drawings identify the same or similar elements. Also, the following detailed description does not limit the invention. Instead, the scope of the invention is defined by the appended claims and equivalents.

[0018] The present invention will be described in connection with forecasting traffic over a network, such as the Internet. It will become apparent, however, that the present invention is also application to other networks, such as a local area network (LAN), a wide area network (WAN), an intranet or another type of network, as described in detail below.

[0019] The Internet is organized into a collection of Internet Protocol (IP) networks, otherwise known as autonomous systems (ASs). Each AS is administered by a single entity, such as an ISP, a large corporation or a university. In order for traffic to be exchanged between hosts that belong to or are connected to separate ASs, each peer AS advertises the set of hosts that can be reached through its particular IP network. In cases where the traffic destination host is not serviced by the source AS, the source IP network delivers the traffic to the AS that advertises the host address. Otherwise, the source IP network delivers the traffic according to the network's internal routing protocol to a point of presence (POP) that services the destination host address.

[0020] Systems and methods consistent with the present invention use this host address organization as a mechanism from which to derive an aggregate traffic model. Namely, the traffic model associated with the forecast characterizes nodes that aggregate various hosts according to the AS that advertises the host addresses. For hosts that are serviced by the particular IP network for which capacity planning is being performed, the hosts' addresses may be further broken down geographically according to the POP that provides network connectivity to the particular host, in implementations consistent with the present invention. The set of hosts serviced at a particular POP may belong to a set of customers that are provided Internet access via that particular POP.

[0021] Systems and methods consistent with the present invention provide a systematic process for generating traffic forecasts. The process uses inputs representing future traffic growth and observed traffic statistics to generate a traffic matrix. The traffic matrix may then be used to plan capacity for a single AS, hereafter referred to as the “model AS.” Each entry in the traffic matrix, consistent with the present invention and described in more detail below, may represent predicted or observed traffic rates for traffic exchanged between: 1) an aggregate of hosts served by a POP on the model AS and an aggregate of hosts served by another AS; 2) an aggregate of hosts served by a POP on the model AS and an aggregate of hosts served by another POP on the model AS; or 3) an aggregate of hosts served by a pair of ASs that are not the model AS.

[0022] FIG. 1 illustrates an exemplary system 100 in which methods and systems, consistent with the present invention, may be implemented. In FIG. 1, system 100 represents a “virtual node” model that includes virtual nodes 110, 120 and 130 and network 140. Each of the virtual nodes 110, 120 and 130 represents a logical aggregation of hosts associated with customers 112, 122 and 132, respectively.

[0023] The data sources/destinations that comprise these hosts may include computers, workstations, servers, printers and any other type of device that may transmit/receive data to/from various points in system 100. Moreover, the data sources/destinations may include devices, such as a personal digital assistant (PDA), which connect to system 100 via a wireless connection.

[0024] Customers 112 and 122, consistent with the present invention, may be served by the model AS and may connect to the model AS via a conventional Internet access circuit (not shown). Customers 132, consistent with the present invention, may be served by an AS different from the AS serving nodes 110 and-120. Network 140, consistent with the present invention, may represent a model network connecting the virtual nodes 110-130 to each other.

[0025] According to an exemplary implementation of the present invention, system 100 may comprise the entire Internet and the aggregation of traffic associated with each virtual node may be represented by a collection of prefixes associated with Internet traffic. Alternatively, system 100 may comprise a subset of the Internet, an intranet, a WAN, a LAN or another network.

[0026] Each virtual node 110, 120 and 130, consistent with the present invention, may also be associated with a service type. That is, the traffic generated by a virtual node may be modeled as coming from a number of lines of business associated with a network service provider, such as GTE Internetworking. For example, a virtual node may include digital subscriber line (DSL) customers, various corporate customers, web hosting stations, a peering interface, etc.

[0027] The virtual node model assumes that each virtual node 110, 120 and 130 feeds a set of edge interfaces at the backbone routers (not shown) interconnecting the virtual nodes. Each virtual node 110-130 may also include internal routers that route information within the respective virtual node and external routers (not shown) that route information via network 140 to the other virtual nodes.

[0028] The number of components illustrated in FIG. 1 is provided for simplicity. In practice, a typical system 100 often includes a larger number of virtual nodes, in addition to internal and external routers, local networks, and data nodes (not shown). More specifically, only two virtual nodes associated with the model AS and one virtual node associated with a peer AS are shown. It should be understood that any number of additional virtual nodes associated with the model AS and any number of peer ASs may also be included in system 100.

[0029] FIG. 2 illustrates an exemplary system in which a system and method, consistent with the present invention, may be implemented. In FIG. 2, the exemplary system 200 includes a bus 210, a processor 220, a main memory 230, a read only memory (ROM) 240, a storage device 250, an input device 260, an output device 270, and a communication interface 280. The bus 210 permits communication among the components of the system 200.

[0030] The processor 220 may include any type of conventional processor or microprocessor that interprets and executes instructions. Main memory 230 may be a random access memory (RAM) or other dynamic storage device that stores information and instructions for execution by processor 220. Main memory 230 may also store temporary variables or other intermediate information during execution of instructions by processor 220. The ROM 240 may include a conventional ROM device or another type of static storage device that stores static information and instructions for processor 220. The storage device 250 may include any type of magnetic or optical recording medium and its corresponding drive, such as a magnetic disk or optical disk and its corresponding disk drive.

[0031] The input device 260 may include any conventional mechanism that permits an operator to input information to the system 200, such as a keyboard, a mouse, a pen, voice recognition and/or biometric mechanisms, etc. The output device 270 may include any conventional mechanism that outputs information to the operator, including a display; a printer, a pair of speakers, etc. The communication interface 280 may include any transceiver-like mechanism that enables the system 200 to communicate with other devices and/or systems. For example, the communication interface 280 may include mechanisms, such as a modem or an Ethernet interface, for communicating via a data network, such as the Internet, an intranet, LAN or WAN.

[0032] The system 200, consistent with the present invention, performs the functions necessary to generate a traffic matrix in response to processor 220 executing sequences of instructions contained in memory 230. Such instructions may be read into memory 230 from another computer-readable medium, such as a data storage device 250, or from a separate device via communication interface 280. Execution of the sequences of instructions contained in memory 230 causes processor 220 to perform the process steps that will be described hereafter. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the present invention. Thus, the present invention is not limited to any specific combination of hardware circuitry and software.

[0033] FIG. 3 is an exemplary flow diagram, consistent with the present invention, illustrating processing for forecasting traffic on a network. Processing begins when a user, e.g., a traffic forecaster or network planner, inputs traffic related information to system 200 (step 310). This input information may include unit growth forecasts, load growth forecasts, scale forecasts, a sent/received ratio, total unit forecasts and an “onnet” factor, as described in more detail below.

[0034] The unit growth forecasts represent how many new units of each service type are anticipated between the point in time when the actual traffic flow statistics were collected and the point in time for which the forecast is being made. For example, the unit growth forecast for a particular service, such as DSL service, may represent the expected increase in the number of customers expected to use the DSL service.

[0035] The load growth forecasts represent the load that the existing nodes of each service type are projected to generate. The load may be defined as (inflow+outflow)* (1−onnet/2), where “onnet” specifies the fraction of traffic associated with a service that stays wholly within a particular network. For example, referring to FIG. 1, assume that virtual nodes 110 and 120 are virtual nodes of a first network service provider, such as GTE Internetworking, and virtual node 130 is a peer node associated with a different network service provider. In this situation, the fraction of traffic staying wholly within the network of the service provider associated with virtual nodes 110 and 120 is the onnet fraction.

[0036] The scale forecasts represent how much the traffic associated with each respective service type is expected to increase, in the absence of any growth in units or load. For example, associated with each virtual node 110-130 (FIG. 1) in the traffic matrix is a set of customers 112-132. For these customers, the scale forecast is the expected growth in their traffic in the absence of any new unit growth. Scale forecasts, therefore, represent the projected growth in load per unit customer.

[0037] The sent/received ratio represents the sent to received ratio of traffic for nodes associated with a particular service. In situations where the sent/received ratio is not provided, the system 200 may determine the ratio using available statistics.

[0038] The total unit forecasts represent the total projected traffic transmitted to/from each of the respective virtual nodes in the network.

[0039] Depending on the type of traffic forecast desired, the user may provide some or all of the traffic-related information described above. For example, a user may provide unit growth forecasts and scale forecasts, without providing the load growth forecast. This type of input may be appropriate for certain services where aggregated models for unit behavior are appropriate, such as DSL services and corporate customers. In other types of services, such as web hosting services, the user may input load growth forecasts and a scale forecast. When the user prefers entering total unit forecasts, he/she may also input a scale factor of zero so that system 200 will ignore observed statistics in determining the total load.

[0040] When unit growth forecasts are provided, the system 200 may translate the unit quantities into units of load. For some services, the system 200 may store definitions relating to per unit load.

[0041] After receiving the input information, system 200 determines the total projected received and sent traffic per service, A and B, respectively, using the following equations (step 320): $A=A*s+\frac{L}{\left(1+R\right)\left(1-\mathrm{onnet}\right)\text{/}2}$ $B=B*s+\frac{L*R}{\left(1+R\right)\left(1-\mathrm{onnet}\right)\text{/}2}$

[0042] where “A” represents the total observed traffic received per service, “B” represents the total observed traffic sent per service, “L” represents the total additional load per service, “s” represents a scale factor per service, “R” represents a sent/received ratio per service and “onnet” represents the fraction of traffic staying wholly within the network. “L” may be entered as an input by a user or determined by system 200 by multiplying the unit forecast by the per unit load values.

[0043] After determining the total projected sent and received traffic per service, A and B, system 200 determines the total traffic received from all peer nodes (A_peer) and the total traffic sent to all peers (B_peer) (step 330). As described previously, the network planner should account for traffic transmitted to/from a peer network to accurately determine the traffic forecast. The total traffic received from all peer nodes, consistent with the present invention, may be defined as:

[0044] A_peer=ΣB(1−onnet).

[0045] The total traffic sent to all peer nodes, consistent with the present invention, may be defined as:

[0046] B_peer=ΣA(1−onnet).

[0047] Additionally, the total sent traffic in the network must be equal to the total received traffic, i.e., ΣA+A_peer=ΣB+B_peer.

[0048] Based on the above equations, system 200, consistent with the present invention, determines the peer traffic using the following equations: $A_{\mathrm{peer}}=\sum ^{}B-\left(\frac{\sum ^{}B*O}{2}+\frac{\sum ^{}A*O}{2}\right)$ $B_{\mathrm{peer}}=\sum ^{}A-\left(\frac{\sum ^{}B*O}{2}+\frac{\sum ^{}A*O}{2}\right)$

[0049] where “O” represents the onnet fraction and the sums are taken over the set of defined services.

[0050] At this point, the system 200 has determined the total sent and received traffic volume for each of the services and the peers. The system 200 now determines the sent and received traffic per virtual node, where summations are taken over virtual nodes belonging to the same service (step 340). According to an exemplary implementation, the system 200 determines the projected received and sent traffic per virtual node, a_iand b_j, respectively using the following equations: $p_i=\frac{a_i}{\sum ^{}{a}_i}$ $q_j=\frac{b_j}{\sum ^{}{b}_j}$ $a_i=A*p_i$ $b_j=B*q_j$

[0051] where “a_i” represents the observed flow received by node i, and “b_j” represents the observed flow sent by node j, “p_i” represents” a percentage of received traffic generated by node i for a particular service, and “q_j” represents a percentage of sent traffic sent by node j for a particular service. The term “a_i” represents the forecasted flow received by node i and the term “b_j” represents the forecasted flow sent by node j.

[0052] After determining the total projected sent and received traffic volumes for each virtual node, the system 200 uses the determined values, along with the observed statistics, to generate a traffic matrix and to apportion the determined volumes over the individual flows in the network.

[0053] Processing, consistent with the present invention, uses the sent/received traffic volumes calculated per virtual node to generate a traffic matrix. The system 200 then uses the calculated traffic values per virtual node to apportion the total traffic volumes over the individual data flows in the network.

[0054] FIG. 4 illustrates processing, consistent with the present invention, for generating a traffic matrix and manipulating the matrix to apportion the traffic. Processing begins when system 200 initializes a traffic matrix using observed traffic flow statistics (step 400). These observed traffic flow statistics may be entered into system 200 by a user, e.g., a traffic forecaster, via input device 260 or may be stored in system 200, e.g., on storage device 250 (FIG. 2).

[0055] For example, assume that the traffic matrix is based on system 100 (FIG. 1) and that virtual nodes 110 and 120 are represented by VN1 and VN2, respectively, and virtual node 130 is a peer node represented by P1. In this scenario, system 200, consistent with the present invention, may generate an initial traffic matrix having the following form:

[0056] where F_ijrepresents the observed traffic flow from node i to node j. The observed traffic flow statistics may be determined in any conventional manner, based on the actual data traffic between the virtual nodes 110-130. According to an exemplary implementation, the entries in the traffic matrix may represent the average flow rate in megabits per second (Mbps) over a period of time. For example, if entry F₁₂was equal to “2,” this would indicate that the flow from VN1 to VN2 is two Mbps over the predefined period of time. The particular period of time may be a peak hour period, a day, a week, or any other time period. Additionally, the entries may represent flow rates in units other than Mbps.

[0057] As seen from the above matrix, traffic may be transmitted entirely within a virtual node. For example, traffic may be transmitted between two data nodes within VN1. Such traffic is included in the entry represented by F₁₁in the above matrix.

[0058] Assume that the observed traffic flow statistics for system 100 (FIG. 1) have been determined as illustrated in matrix 1. As described previously, these values may be input by a user or stored in memory on system 200.

[0059] Now suppose that system 200 generates the following projected data for the total sent and received traffic volumes per virtual node (step 340, FIG. 3).

[0060] Next, the system 200 compares the flow quantities in matrix 1 above to the sent and received volumes in Table 1 to determine whether to modify traffic matrix 1 (step 410). In the above example, the total received and total sent values in matrix 1 do not match the forecasted received and sent totals in Table 1. For example, the total received by VN1 in traffic matrix 1 is 12. The total received by VN1 in Table 1, however, is 11.

[0061] Since the observed flow quantity, 12, does not match the forecasted quantity, 11, the system 200 constructs a new traffic matrix (step 420). According to an exemplary implementation, the system 200 inserts the new sent and received projections from Table 1 into matrix 1. The system 200 may also remove all rows or columns having a zero sum, such as the row associated with P1 in matrix 1.

[0062] The resulting matrix may be illustrated as:

[0063] Next, the system 200 determines if the row sums in matrix 2 match the total received values and whether the column sums match the total sent values (step 430). If all the row and column sums match the total received and sent values, processing stops (step 440), indicating that the matrix represents the projected traffic flows between the virtual nodes in the network, as described in more detail below.

[0064] In the example above, the row sums for VN1 is 2+2+8=12. Since 12≠11, processing continues. The other row sums and column sums also do not match the corresponding totals. When the row and column sums do not match the corresponding totals, the system 200 determines if any of the row or columns sums are greater than the corresponding sent or received totals (step 450). If the answer is “no,” processing continues at step 470. In matrix 2 above, the observed flows sent to VN2 are 2+4=6, which is greater than the forecasted total of 3. Additionally, the sum of the observed flows transmitted from VN1 is 2+2+8=12, which is greater than the forecasted total of 11.

[0065] In this scenario, the system 200 scales down the original matrix until none of the row or columns sums are violated (step 460). That is, the system 200 scales down the matrix so that none of the row/column sums is greater that the corresponding total received/sent values, respectively. In the example above, the system 200 may scale the observed traffic values in matrix 2 by ½, thereby generating matrix 3.

[0066] From matrix 3, the system 200 then determines whether any row or column sum matches the corresponding total received/sent value and if any such row/column exists, the system 200 “freezes” the values in that row/column (step 470). That is, the system 200 will not change the values in that row/column for the remainder of the process. In the scenario above, the sum of column VN2 matches the total sent value (i.e., 1+2=3). The system 200, therefore, freezes these values in the VN2 column. The system 200 also subtracts the values associated with the frozen column from the total received value. The frozen entries represent the projected traffic flow between the corresponding nodes. For example, from matrix 3, the projected traffic flow from VN1 to VN2 is “1.”

[0067] Removing the frozen column and updating the total received values produces the following matrix:

[0068] The system 200 now determines whether the sum of entries in any row/column does not match the corresponding total received/sent value (step 480). If the answer is no, processing stops and the current matrix represents the final traffic matrix.

[0069] From matrix 4 above, the sum of entries in each of the row/columns does not match the corresponding total. In this case, the system 200 scales the matrix again until one of the row or column sums matches the corresponding total received or sent value (step 490). For example, scaling matrix 4 by two makes the first row the limiting row as shown below.

[0070] Processing then returns to step 470. Since the sum of the values in row 1 equals the total received value (i.e., 2+8=10), the system 200 now freezes out the first row and updates the matrix as shown in matrix 6. As described previously, system 200 also subtracts the values associated with the frozen row from the corresponding total sent values.

[0071] Next, the system 200 scales the remaining two entries so that the flows match the total received and total sent values. That is, the system 200 scales the flow from VN2 to VN1 to 6 and the flow from VN2 to P1 to 7. Matrix 7 represents the final traffic matrix.

[0072] Matrix 7 now represents the forecasted traffic flows between the virtual nodes in the network. For example, the forecasted traffic flow from VN2 to VN1 is “6”. This value may represent an average flow rate of 6 Mbps, or some other unit, over a defined period of time.

[0073] System planners may then map the data flows from the virtual nodes to physical locations. For example, assume that VN1 represents virtual node 110 in FIG. 1 and that VN2 represents virtual node 120. Each of these virtual nodes 110 and 120 may then be mapped to physical locations.

[0074] For example, virtual node 110 may represent a POP in Boston and virtual node 120 may represent a POP in Atlanta. The system planner then uses matrix 7 to determine that the projected flow from the POP in Atlanta (VN2) to the POP in Boston (VN1) is 6 Mbps. The virtual nodes may be mapped to other physical locations, in implementations consistent with the present invention, based on the particular network topology.

[0075] According to an exemplary implementation, the system planner may use the information in the final traffic matrix to determine circuit utilization information based on the projected traffic. That is, the system planner may determine whether the current circuits will be able to meet the projected demand. The system planner may also determine how many circuits will be needed to adequately meet the projected traffic demand and whether a particular network topology will be adequate to handle this projected data traffic.

[0076] The foregoing description of exemplary embodiments of the present invention provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. The scope of the invention is defined by the following claims and their equivalents.

[0077] For example, the invention has been described in relation to a virtual node model. The present invention is not limited to forecasting traffic using a virtual node model, however, and may be used with any network topology.