CS 536 ParkResource Provisioning and NetworkTrafficNetwork engineering:• Feedback traffic control→ closed-loop control (“adaptive”)→ small time scale: msec→ mainly by end systems→ e.g., congestion control• Resource provisioning→ open-loop control (“in advance”)→ large time scale: seconds, minutes, and higher→ mainly by service providersQuestion: what do ISPs do to keep customers happy andmake money (or lose less money)?CS 536 ParkResource provisioning: two main resources• Bandwidth allocation→ primary• Buffer allocation−→ resource dimensioning: long-term−→ also called network planning: months, years−→ on-demand resource allocation: short-term−→ i.e., second, minutes, hoursTurns out:−→ same principles apply to both−→ take ISP’s viewpoint−→ granularity: user-, session-, and packet-levelCS 536 ParkUser- and Session-Level Resource ProvisioningBasic set-up:−→ aggregate demand at access switch−→ n users or CPE (customer premises equipment)CPE 1CPE 2CPE 3CPE n. . .Access SwitchBackbone SwitSet-up applies to:• Telephone switch: TDM slot per session/user• Dial-up modem pool: e.g., AOL Internet access• Broadband access service: e.g., IP address poolCS 536 ParkBasic building block: access switch−→ function: aggregation−→ performance benefit?−→ old banking trick: keep fraction of total deposit−→ observation: not all customers withdraw at once (?)Networking: not all customers access network at once−→ affords efficiency & economy• can keep fewer T1 lines• can keep smaller modem pool• can keep fewer IP addresses• can keep less bandwidthNote: a calculated risk−→ sometimes very many users connect at once−→ access denied: blockingCS 536 ParkIn what other major sector is “old banking trick” em-ployed?What makes old banking trick possible?−→ one of the few “laws of engineering”Law of large numbers (LLN): the sum of many indepen-dent random variables concentrates around the mean−→ i.e., very few outliers−→ also, typically, mean ¿ maximumEx.: Suppose there are n users subscribing to Verizon inWest Lafayette.−→ how many users will make a call at time t?CS 536 ParkAssuming:• Xi(t) = 0 if no call by user i at t, 1 if call• Pr{Xi(t)=1} = p• users make calling decisions independent of each other→ i.e., X1(t),X2(t),...,Xn(t) are i.i.d.→ note: same as coin tossing• total calls at time t→ Sn(t)=X1(t)+X2(t)+···+ Xn(t)• average number of calls→ E[Sn(t)] = E[X1(t)] + ···+ E[Xn(t)] = np→ hence, E[Sn(t)/n]=p→ independence needed?• LLN: Pr{|Sn(t)n−p| >ε}→0asn →∞for any ε>0→ weak LLN→ strong LLN?CS 536 ParkThus, for sufficiently large n deviation from the mean israre.−→ Verizon can expect np calls at time t−→ with large n, very close to np calls−→ but, how large is “large”?−→ does WL have sufficiently many customers?To be useful for engineering, we need to know more−→ rate of convergenceLarge deviation bound:−→ Pr{|Sn(t)n− p| >ε} <e−an−→ constant a depends on ε−→ exponential decrease in n−→ also, holds for all n−→ engineering: blocking probabilityCS 536 ParkLarge deviation bound gives simple prescription for re-source provisioning:• measure p (historical data); ISP knows n• determine acceptable blocking probability δ→ e.g., δ =0.00001→ i.e., one in 10000 calls gets blocked• find ε such thatPr{|Sn(t)n− p| >ε} =Pr{|Sn(t) − np| >nε}<e−an= δ→ note: ε determines excess capacity allocated→ recall: a depends on ε (called rate function)→ one of the main tools used by ISPs/telcosFrom ISP’s perspective, is this enough for making re-source provisioning decision?−→ what crucial element may be missing?CS 536 ParkConnection lifetime or duration−→ also called call holding time−→ for how long a resource (e.g., modem) is busy−→ if fixed, then previous formula holds−→ user session property−→ in general: connection lifetime is variable−→ e.g., average telephone call: 7 minutesLet L denote connection lifetime (assuming i.i.d. acrossall users)−→ by measurement, ISP knows its distribution−→ consider average lifetime E[L]−→ consider two time instances t and t + E[L]−→ what to do?CS 536 ParkView system in terms of time granularity E[L]:expected time for red to free upnew connection arrivals. . .t + E[L]ttime• use large deviation formula to estimate connection ar-rivals during time window [t, t + E[L])→ excess capacity nε above and beyond mean np• use distribution of L to estimate Pr{L>E[L]}→ may refine ε to ε0(ε<ε0)→ for E[L] not-too-small may not be needed (why?)CS 536 ParkRemarks:• LLN: principal engineering tool used by large transitproviders and large access providers→ “largeness” is key→ even though components are random, system iswell-behaved and predictable→ apply at ingress/egress and backbone links→ measurement-based tool: traffic matrixingressegressCS 536 Park• sometimes can apply central limit theorem (CLT): ag-gregate has Gaussian (normal) distribution→ in practice: not very useful→ e.g., tail of Gaussian: not very accurate→ deviation estimate valid only for moderate ε→ may not even look Gaussian!→ needs very large n→ large deviation bound: holds for all n• aggregation over time window [t, t + E[L])→ a single user can have 2 or more sessions→ may violate independence assumption (across users)→ independence over time: separate matterCS 536 Park• we assumed discrete number of resources→ e.g., 10000 modems, 50000 IP addresses, 1000 T1lines, etc.→ valid viewpoint at user/session granularity→ also applies to packet granularity→ as long as independence over time holdsHow does session arrival for a single user over time looklike?−→ aggregation over time−→ resource provisioning: buffering−→ vs. aggregation over users (bandwidth)CS 536 ParkSession arrivals over time:• apply coin tossing idea over time• before: one coin per user• now: one user has multiple coins→ coins are assumed to be i.i.d. with probability p→ apply LLN over time!user 1timeuser itime123. . .muser 2timeuser 3timeuser ntime. . .tLLN over users LLN over timeCS 536 ParkOver discrete time window [1,m], same bounds apply; foruser i:−→ Si(m)=Xi(1) + Xi(2) + ···+ Xi(m)−→ Pr{|Si(m)m− p| >ε} <e−amThus: if we have mp + mε resources (e.g., buffer), thencan buffer user i’s
View Full Document