We start with a discussion about traffic in IP networks. To describe traffic, we first need to consider sources that generate IP traffic.
An IP network provides many services such aswebandemail; there are also interactive services such astelnet,sshfor terminal services. In current IP networks, the predominant traffic is due to applications that use TCP for transport layer; it has been reported that on a backbone link approximately 90% of traffic is TCP based [350]. A message content created by applications is broken into smaller TCP pieces, called TCP segments, by including TCP header information, which are then transmitted over the IP network after including IP header information; the data entity at the IP level is IP datagrams, while packet is also a commonly used term. Thus, traffic in an IP network is IP datagrams generated by various applications, without wondering which among the applications it is for.
Thus, when we talk about traffic volume on an IP network link, we are interested in knowing the number of IP packets flowing on a link in a certain unit of time. Usually, the time unit is considered in seconds. Thus, traffic volume can be specified in terms of IP pack- ets offered per second, or packets per sec (pps). On the other hand, there is another measure of traffic volume that is often used—raw data rate units such as Megabits per sec (Mbps) or Gigabits per sec (Gbps). Indeed, there is a relation between pps and Mbps (or Gbps). Sup- pose we consider the average packet size to beKMegabits. Then pps is related to Mbps as follows:
Traffic data rate (Mbps)=Packets per sec × Average packet size (Megabits). (7.1.1) It is, however, not required that the average packet size be counted separately to obtain the data rate. With the sophisticated network monitoring system in current IP networks, the traffic data rate in Mbps (or Gbps) can be estimated based on measurements through either an active or passive monitoring system.
7.1.2 Traffic and Performance Measures
In an IP network environment, delay is a critical performance parameter since we are inter- esting in ensuring that a packet generated from one end reaches the other end as soon as
possible. Interestingly, there is an analogy between road transportation networks and IP net- works. In road transportation networks, delay depends on the volume of traffic as well as the number of street lanes (and speed limit) imposed by the system. Similarly, delay in an IP network can depend on the amount of traffic as well as the capacity of the system; thus, the following functional relation can be generally written:
Delay=F(Traffic volume data rate, Capacity). (7.1.2)
To be specific, the above relation is true only in a single-link system. When we consider a network where routing is also a factor, then a more general functional relation is as follows:
Delay=F(Traffic volume data rate, Capacity, Routing). (7.1.3)
7.1.3 Characterizing Traffic
So far, we have not said much about traffic volume except for Eq. (7.1.1); that is, traffic volume may be given through a single number, such as packets per second or Megabits per second.
How do we obtain a number like this one?
Consider the arrival of packets to a network link. If we consider just a single request for a web page that is traversing the link, it may appear that the packets at the IP level are arriving in a deterministic fashion; the page is generated by the web server, which is broken into TCP segments that are wrapped with an IP header, and is then transmitted one after another; this is certainly from the point of view of a single web session. However, in a network link, many web sessions are active, each one being requested at a random start point by a user; this is similar for other traffic due to applications such as email, and so on. Thus, from the point of view of a network link, if we consider only the IP level, the link then sees random arrival of packets. Thus, a number that may represent pps cannot be a fixed, deterministic number; it is rather dictated by the randomness of traffic arrival. Thus, at most what we can say is average pps or average Mbps in regard to random traffic arrival. The primary question is: can we say anything about the characteristics of the random behavior?
Traditionally, it has been assumed that arrival of packets follows a well-known random process called the Poisson process, and the average arrival rate is the average rate for this Pois- son process. However, in the early to mid-1990s, there were a series of studies based on ac- tual measurements of packet traffic that reported that packet arrival behavior is not Poisson;
rather traffic is self-similar in different time scales following heavy-tailed distributions, ex- hibiting long-range dependency; for example, see [160], [404], [545], [551], [740], [741]. Not to clutter the discussion here, definitions for Poisson process, self-similarity, long-range depen- dency, and heavy-tailed distributions are provided in Appendix B.10 and in Appendix B.11.
The key point to note here is that self-similarity contradicts the Poisson assumption; further- more, a self-similar process with a heavy-tailed distribution impacts the delay behavior much worse than for a Poisson process. In a recent illuminating study [350] based on measurements from a backbone network link at OC-48 speed, it was observed that it is indeed possible that both Poisson behavior and self-similarity can co-exist; it is a matter of the time frame being considered. Specifically, they reported that in a subsecond time scale, the behavior is Poisson while in the scale of seconds long-range dependency is observed. We thus start with the as- sumption of the Poisson model and discuss how self-similarity can be factored in indirectly for the purpose of traffic engineering.
7.1.4 Average Delay in a Single-Link System
First, we assume that packet arrival to a network link follows a Poisson process with the average arrival rate as λ packets per sec. The average service rate of packets by the link is assumed to be μ packets per sec. We consider here the case in which the average ar- rival rate is lower than the average service rate, i.e.,λ < μ; otherwise, we would have an overflow situation. If we assume that the service time is exponentially distributed (see Appen- dix B.10), in addition to packet arrival being Poissonian, then the average delay, τ, can be given by the following formula, which is based on theM/M/1 queueing model (see Appen- dix B.12.2):
τ= 1
μ−λ. (7.1.4)
Now consider that the average packet size is κ Megabits, and that the packet size is exponentially distributed. Then, there is a simple relation between the link speed c (in Mbps), the average packet size κ, and the packet service rate μ, which can be written as:
c=κμ. (7.1.5)
This is then essentially the relation discussed earlier in Eq. (7.1.1). Combining κ with the packet arrival rateλ, we can consider the arrival rate,h, in Mbps as follows:
h=κλ. (7.1.6)
If we multiply the numerator and the denominator byκ, we can then transform Eq. (7.1.4) as follows:
τ= κ
κ(μ−λ)= κ
c−h. (7.1.7)
This relation can be rewritten as:
τ
κ = 1
c−h. (7.1.8)
If we now compare Eq. (7.1.4) and Eq. (7.1.8), we see that the average packet delay can be derived directly from the link speed and arrival rate given in a measure such as Mbps;
the only difference is the factorκ, the average packet size. Second, although it may sound odd, the quantity, τκ, can be thought of as the average “bit-level” delay on a network link where the average traffic arrival rate is assumed to beh Mbps. In other words, if we track the traffic volume in Mbps on a link and know the link data rate, we can get a pretty good idea about the average delay. There are a couple of advantages to this observation:
first, we can use traffic volume, h, and link speed, c, in other units such as Gbps with- out changing the basic behavior on delay given by1/(c−h); second, it is not always nec- essary to track the average packet size; third, if the delay is to be measured in millisec instead of sec, then 1/(c−h) must be multiplied by the constant, 1000, without chang- ing the basic structure of the formula. Finally, whether we consider measures in packets
per sec or Mbps (or Gbps), the link utilization parameter, ρ, that captures the ratio of traffic volume over the link rate, remains the same regardless of the average packet size since
ρ=h c =κλ
κμ= λ
μ. (7.1.9)
In essence, we can say that under the M/M/1 queueing assumption, the average delay, t(=τ/κ), can be given in terms of the link speed c and the traffic rate h where h<c as
t= 1
c−h (7.1.10)
with utilization given by ρ =h/c. Incidentally, Eq. (7.1.10) then gives a functional rela- tion mentioned earlier in Eq. (7.1.2). What happens if we were to consider self-similarity of traffic? Unfortunately, there is no simple formula like the above when traffic is self- similar. It has been reported that the delay behavior with heavy-tail traffic is worse than that of the M/M/1 delay. Thus, we will create a fictitious delay function for self-similar traffic and plot it along with the M/M/1 delay as shown in Figure 7.1; note that in this figure the link speed c is kept fixed while the traffic rate h is increased—this is why the x-axis is marked in terms of link utilization, ρ, given in percentage as ρ goes from 0 to 100%.
Figure 7.1 is, in fact, very helpful in letting us see a problem from the perspective of traffic engineering. For instance, suppose that to provide acceptable perception to users, we want to maintain the average delay at say 20 millisec. From the graph, we can see that with the M/M/1 average delay formula, the link can handle an arrival traffic rate up to about 80% of the link capacity while maintaining the acceptable average delay. However, if the traffic does not follow the Poisson process, then the delay would be much worse at the same utilization
F I G U R E 7.1 TheM/M/1 average delay curve along with a fictitious delay curve.
value; for instance, in this fictitious graph of delay, we can see that the delay would be about 50 millisec instead. Certainly this is not desirable when the acceptable delay is required to be below 20 millisec. Thus, instead of taking a vertical view at a certain utilization, we take the horizontal view at an acceptable average delay. If we do so, we see that to maintain the average delay at or below 20 millisec, the non-Poisson traffic cannot go beyond 50% link utilization.
In regard to traffic engineering, there are two important points to note from the above discussion. First, there is a direct relation between delay and utilization; because of this, re- quiring a network to maintain a certain delay can be recast as requiring the utilization to be kept below an appropriate level. Second, since there is no simple formula to consider delay for self-similar traffic, being conservative on the requirement on utilization can often be suf- ficient for the purpose of traffic engineering. For example, in the above example, we observe that keeping utilization at 50% would be more appropriate than letting it grow to 80%. Due to the relation between traffic volume and capacity through utilization (ρ=h/c), this means that for a fixed link speedc, we need to keep the traffic volume at a lower level than would otherwise be indicated for Poisson traffic in order to address traffic engineering needs.
7.1.5 Nonstationarity of Traffic
The analysis/discussion above is based on stationary traffic assuming that an average traffic data rate is given. However, network traffic has been observed to be nonstationary and can be time dependent. For example, consider a 24-hour network traffic profile on a link as shown in Figure 7.2. We can see that the data rate is different depending on the time of the day; in this specific instance, the traffic volume data rate range is from below 8 Mbps to as high as 30 Mbps. If, for the purpose of traffic engineering, we were to use traffic volume to be the data rate, say at midnight (about 8 Mbps), and determine link capacity needed to be, say 15 Mbps (based on utilization being about 50%), then we will certainly be overlooking many
F I G U R E 7.2 Traffic data rate over a 24-hour period.
time windows when the traffic volume will overflow this capacity. This tells us that it would make more sense to consider the peak of the traffic data rate (or, say 90% of the peak traffic) over the 24-hour window as the traffic volume needed for traffic engineering consideration.
In this example, the peak traffic volume rate is about 30 Mbps; thus, for an acceptable delay or utilization, at least a 45 Mbps link would be desirable.
Remark 7.1. Traffic engineering and network dimensioning.
From the illustration above, it could be argued that a 45-Mbps link is not sufficient since the utilization at the peak traffic rate would be over 60%. For example, 60 Mbps would be minimally necessary considering 50% as acceptable utilization. However, the determination of actual link speed to put in place or lease, especially in a backbone network, also depends on the actual cost of establishing or leasing the link. The prob- lem of determining the appropriately sized link, especially taking into consideration net- work cost minimization, is often considered under network dimensioning rather than un- der traffic engineering, while the distinction is sometimes blurry if you read the cur- rent literature. We will assume that the goal of traffic engineering is to see if the net- work can provide acceptable delay or utilization for offered traffic in a capacitated environ-
ment.
Remark 7.2. Traffic engineering and traffic estimation.
From Figure 7.2, it is clear that the offered traffic should be chosen wisely and may de- pend on the time of day. In fact, traffic estimation is itself a challenging problem; there has been much recent work on understanding how to do it and how to do it as accurately as pos- sible, especially for a large network. We assume that through some process, the offered traffic
is determined for use in traffic engineering.