DOC PREVIEW
Purdue CS 53600 - Resource Provisioning and Network Traffic

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Purdue CS 53600 - Resource Provisioning and Network Traffic

Download Resource Provisioning and Network Traffic
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Resource Provisioning and Network Traffic and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Resource Provisioning and Network Traffic 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?