rexford slides

Information about rexford slides

Published on June 18, 2007

Author: FunnyGuy

Source: authorstream.com

Content

Traffic Engineering for ISP Networks:  Traffic Engineering for ISP Networks Jennifer Rexford Internet and Networking Systems ATandamp;T Labs - Research; Florham Park, NJ http://www.research.att.com/~jrex Joint work with Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, and Fred True, and ATandamp;T IP Services Outline:  Outline Background Internet architecture Interdomain and intradomain routing Internet service provider backbone Traffic engineering Optimizing network configuration to prevailing traffic Requirements for topology, routing, and traffic info Traffic demands Volume of load between edges of the network Measurement methodology Analysis of the demands on ATandamp;T’s IP Backbone Internet Architecture:  Internet Architecture Divided into Autonomous Systems Distinct regions of administrative control (~6000-7000) Set of routers and links managed by a single institution Service provider, company, university, … Hierarchy of Autonomous Systems Large, tier-1 provider with a nationwide backbone Medium-sized regional provider with smaller backbone Small network run by a single company or university Interaction between Autonomous Systems Internal topology is not shared between ASes … but, neighboring ASes interact to coordinate routing Autonomous Systems (ASes):  Autonomous Systems (ASes) 1 2 3 4 5 6 7 Client Web server Path: 6, 5, 4, 3, 2, 1 Characteristics of the Internet:  Characteristics of the Internet The Internet is Decentralized (loose confederation of peers) Self-configuring (no global registry of topology) Stateless (limited information in the routers) Connectionless (no fixed connection between hosts) These attributes contribute To the success of Internet To the rapid growth of the Internet … and the difficulty of controlling the Internet! Internet – Interconnection of Networks:  Internet – Interconnection of Networks Internet Protocol Transmit a single packet from one host to another Packet includes the IP address of the sender and receiver Packets may be lost, delayed, or delivered out of order Hosts perform retransmission and reordering of packets IP address 32-bit IP addresses divided into octets (12.34.158.5) Allocated to institutions in contiguous blocks or prefixes 12.34.158.0/24 is a 24-bit prefix with 28 IP addresses Routing of IP packets in the Internet is based on prefixes Interdomain Routing (Between ASes):  Interdomain Routing (Between ASes) ASes exchange info about who they can reach Local policies for path selection (which to use?) Local policies for route propagation (who to tell?) Policies configured by the AS’s network operator 1 2 3 Client (12.34.158.5) 12.34.158.5 'I can reach 12.34.158.0/24' 'I can reach 12.34.158.0/24 via AS 1' Internet Service Provider Backbone:  Internet Service Provider Backbone modem banks, business customers, web/e-mail servers neighboring providers How should traffic be routed through the ISP backbone? Intradomain Routing (Within an AS):  Intradomain Routing (Within an AS) Routers exchange information to learn the topology Routers determine 'next hop' to reach other routers Path selection based on link weights (shortest path) Link weights configured by AS’s network operator … to engineer the flow of traffic 3 2 2 1 1 3 1 4 5 3 Traffic Engineering in an ISP Backbone:  Traffic Engineering in an ISP Backbone Topology of the ISP backbone Connectivity and capacity of routers and links Traffic demands Expected/offered load between points in the network Routing configuration Tunable rules for selecting a path for each traffic flow Performance objective Balanced load, low latency, service level agreements … Question: Given the topology and traffic demands in an IP network, which routes should be used? State-of-the-Art in IP Networks:  State-of-the-Art in IP Networks Missing input information The topology and traffic demands are often unknown Traffic fluctuates over time (user behavior, new appls) Topology changes over time (failures, growth, reconfig) Primitive control over routing The network does not adapt the routes to the load The static routes are not optimized to the traffic Routing parameters are changed manually by operators (But, other than that, everything is under control…) Example: Congested Link:  Example: Congested Link Detecting that a link is congested Utilization statistics reported every five minutes Sample probe traffic suffers degraded performance Customers complain (via the telephone network?) Reasons why the link might be congested Increase in demand between some set of src-dest pairs Failed router/link within the AS causes routing change Failure/reconfiguration in another AS changes routes How to determine why the link is congested??? Need to know the cause, not just the manifestations! How to alleviate the congestion on the link??? Link Utilization:  Link Utilization Utilization: link color (high to low) Requirements for Traffic Engineering:  Requirements for Traffic Engineering Models Traffic demands Network topology/configuration Internet routing algorithms Techniques for populating the models Measuring/computing the traffic demands Determining the network topology/configuration Optimizing the routing parameters Analysis of the traffic demands Knowing how the demands fluctuates over time Understanding the traffic engineering implications Modeling Traffic Demands:  Modeling Traffic Demands Volume of traffic V(s,d,t) From a particular source s To a particular destination d Over a particular time period t Time period Performance debugging -- minutes or tens of minutes Time-of-day traffic engineering -- hours Network design -- days to weeks Sources and destinations Individual hosts -- interesting, but huge! Individual prefixes -- still big; not seen by any one AS! Individual edge links in an ISP backbone -- hmmm…. Traffic Matrix:  Traffic Matrix in out Traffic matrix: V(in,out,t) for all pairs (in,out) Problem: Multiple Exit Points:  Problem: Multiple Exit Points ISP backbone is in the middle of the Internet Multiple connections to other autonomous systems Destination is reachable through multiple exit points Selection of exit point depends on intradomain routes Problem with traditional point-to-point models Want to predict impact of changing intradomain routing But, a change in routing may change the exit point! 1 2 3 4 Traffic Demand:  Traffic Demand Definition: V(in, {out}, t) Entry link (in) Set of possible exit links ({out}) Time period (t) Volume of traffic (V(in,{out},t)) Computing the traffic demands Measure the traffic where it enters the ISP backbone Identify the set of exit links where traffic could leave Associate traffic with the entry link and set of exit links Aggregate over all traffic with same in, {out}, and t Measuring Flows Rather Than Packets:  flow 1 flow 2 flow 3 flow 4 Measuring Flows Rather Than Packets IP flow abstraction Set of packets with 'same' src and dest IP addresses Packets that are 'close' together in time (a few seconds) The closest thing to a 'call' in the Internet Cisco NetFlow Measure all flows between ATandamp;T and neighbors Extremely large amount of data (~100 GB/day) NetFlow Data:  NetFlow Data Source and destination information Source and destination IP addresses (hosts) Source and destination port numbers (application) Source and destination AS numbers Routing information Source and destination IP prefix (network address) Input and output links at this router Traffic information Start and finish time of flow (in seconds) Total number of bytes and packets in the flow Identifying Where the Traffic Can Leave:  Identifying Where the Traffic Can Leave Traffic flows Each flow has a dest IP address (e.g., 12.34.156.5) Each address belongs to a prefix (e.g., 12.34.156.0/24) Forwarding tables Each router has a table to forward a packet to 'next hop' Forwarding table maps a prefix to a 'next hop' link Process Dump the forwarding table from each router Identify the entries where the 'next hop' is an exit link Identify the set of exit links associated with each prefix Associate a flow’s dest address with the set of exit links Locating the Set of Exit Links for Prefix d:  Locating the Set of Exit Links for Prefix d d i k Prefix d: exit links {i, k} Table entry: (d, i) Table entry: (d, k) Experimental Results: AT&T IP Backbone:  Experimental Results: ATandamp;T IP Backbone Measurement for four days in November 1999 Netflow data Forwarding tables Topology and routing configuration Traffic analysis Distribution of traffic volume across demands Small % of demands are responsible for most traffic Time-of-day fluctuations in traffic volumes U.S. business, U.S. residential, International Stability of traffic demands across hours and days Initial results suggest some stability, but need to study Proportion of Traffic in Top Demands (Log Scale):  Proportion of Traffic in Top Demands (Log Scale) Time-of-Day Effects (San Francisco):  Time-of-Day Effects (San Francisco) Traffic-Engineering Implications:  Traffic-Engineering Implications Small number of demands contribute most traffic Can optimize routes for just the heavy hitters Can measuring a small fraction of the traffic Must watch out for changes in load and set of exit links Time-of-day fluctuations Reoptimize routes a few times a day (three?) Traffic (in)stability Select routes that are good for different demand sets Reoptimize routes after sudden changes in load Traffic Flow Through AT&T’s IP Backbone:  Traffic Flow Through ATandamp;T’s IP Backbone Color/size of node: proportional to traffic to this router (high to low) Color/size of link: proportional to traffic carried (high to low) Source node: public peering link (NAP) in New York Destination nodes: ATandamp;T access routers Conclusions:  Conclusions Internet traffic engineering is hard Decentralized (over 6000 Autonomous Systems) Connectionless (traffic sent as individual packets) Changing (topological changes, traffic fluctuations) Traffic engineering requires knowing the demands Interdomain traffic has multiple possible exit points Demand as the load from entry to set of exit points Not available from traditional measurement techniques Measurement of traffic demands Derivable from flow-level measurements at entry points … and 'next hop' forwarding info from exit points Ongoing Work:  Ongoing Work Detailed analysis of traffic demands Statistical properties (how to study stability?) Implications for traffic engineering Online computation of traffic demands Distributed flow-measurement infrastructure Online aggregation of flow data into demands Network operations ('operations' research?) Efficiently detecting sudden changes in traffic or routing Optimizing routes based on topology and demands Planning the design of the network over time Getting the network to run itself…  Interesting Problems:  Interesting Problems Inferring the traffic demands from less information sampling, active probes, inference from utilization Optimizing routes subject to fluctuating demands optimal routes per demand set vs. good for all sets Techniques for analyzing stability of demand sets multidimensional data (in, {out}, time) Detecting shifts in the distribution of load random changes vs. change in underlying distribution Joint route optimization across multiple ASes optimizing routes without divulging topology andamp; traffic

Related presentations


Other presentations created by FunnyGuy

history
02. 05. 2008
0 views

history

julac2001
28. 04. 2008
0 views

julac2001

sandiego
22. 04. 2008
0 views

sandiego

ch20
18. 04. 2008
0 views

ch20

unepmahomed
16. 04. 2008
0 views

unepmahomed

lecture14
13. 04. 2008
0 views

lecture14

oca
10. 04. 2008
0 views

oca

Pepsi Presenation
18. 06. 2007
0 views

Pepsi Presenation

MATERIALHANDLING
27. 02. 2008
0 views

MATERIALHANDLING

ny subway
27. 09. 2007
0 views

ny subway

July20 KNN
05. 10. 2007
0 views

July20 KNN

VertebratePPP
10. 10. 2007
0 views

VertebratePPP

Wide World of Animals
10. 10. 2007
0 views

Wide World of Animals

cc
15. 10. 2007
0 views

cc

School for Scandal lecture
17. 10. 2007
0 views

School for Scandal lecture

Profesionesyoficios2
22. 10. 2007
0 views

Profesionesyoficios2

Lecture3 NLP grammars parsing
21. 10. 2007
0 views

Lecture3 NLP grammars parsing

lec6 sensanal 05
05. 10. 2007
0 views

lec6 sensanal 05

PPMcNeely
23. 10. 2007
0 views

PPMcNeely

California Demographics 101
29. 10. 2007
0 views

California Demographics 101

Varying sent struct2
30. 10. 2007
0 views

Varying sent struct2

bio435 660 chap3 pt1
16. 11. 2007
0 views

bio435 660 chap3 pt1

dogscatsrabbits
19. 11. 2007
0 views

dogscatsrabbits

Workshop Marketing
20. 11. 2007
0 views

Workshop Marketing

Sablony
15. 11. 2007
0 views

Sablony

poultry prod
26. 11. 2007
0 views

poultry prod

lublin072806
23. 10. 2007
0 views

lublin072806

hcbscrisis
30. 10. 2007
0 views

hcbscrisis

lecture06
30. 12. 2007
0 views

lecture06

mites
01. 01. 2008
0 views

mites

COE Permit Procedure
03. 01. 2008
0 views

COE Permit Procedure

Miss You
09. 08. 2007
0 views

Miss You

history of malaria 2006
16. 10. 2007
0 views

history of malaria 2006

P0200412274947173437 13
16. 10. 2007
0 views

P0200412274947173437 13

Dalby presentation
31. 10. 2007
0 views

Dalby presentation

Medievallyrics
27. 11. 2007
0 views

Medievallyrics

metalurgy
05. 01. 2008
0 views

metalurgy

The Limits Of Computing
07. 01. 2008
0 views

The Limits Of Computing

Sym06ppt Oram
29. 10. 2007
0 views

Sym06ppt Oram

cdc obesity 04
03. 08. 2007
0 views

cdc obesity 04

LSMD
07. 11. 2007
0 views

LSMD

gatewayspace
15. 10. 2007
0 views

gatewayspace

ENG private sector 2004
23. 11. 2007
0 views

ENG private sector 2004

Lecture8dna
15. 10. 2007
0 views

Lecture8dna

Tim POPL
04. 10. 2007
0 views

Tim POPL

M E Quiz Maria
24. 02. 2008
0 views

M E Quiz Maria

Ch 12 LMIs
29. 10. 2007
0 views

Ch 12 LMIs

FloodLATEST
29. 02. 2008
0 views

FloodLATEST

New Orleans
26. 06. 2007
0 views

New Orleans

M Surdeanu
26. 06. 2007
0 views

M Surdeanu

Mulvey
26. 06. 2007
0 views

Mulvey

law enforcement
19. 02. 2008
0 views

law enforcement

510Women Gender and DDR
06. 03. 2008
0 views

510Women Gender and DDR

NACEpresentation
10. 03. 2008
0 views

NACEpresentation

ec101Chp16
04. 10. 2007
0 views

ec101Chp16

De Toulon aux Canaries
24. 10. 2007
0 views

De Toulon aux Canaries

Tides pp
11. 03. 2008
0 views

Tides pp

Gaved Heath Eisenstadt Wikisym06
12. 03. 2008
0 views

Gaved Heath Eisenstadt Wikisym06

MVD
26. 06. 2007
0 views

MVD

MAGICJFee
22. 10. 2007
0 views

MAGICJFee

Neil Avent
20. 03. 2008
0 views

Neil Avent

The Great Wall of China
25. 03. 2008
0 views

The Great Wall of China

mikey
16. 10. 2007
0 views

mikey

12 hydro wind
07. 04. 2008
0 views

12 hydro wind

How to Apply for a Job
23. 10. 2007
0 views

How to Apply for a Job

Tice Materials 28
03. 01. 2008
0 views

Tice Materials 28

Ecot pres
09. 04. 2008
0 views

Ecot pres

melladoRomeprodNov11 04
31. 10. 2007
0 views

melladoRomeprodNov11 04

intro lect 4
07. 12. 2007
0 views

intro lect 4

peter
18. 06. 2007
0 views

peter

Pay Attention 092904
18. 06. 2007
0 views

Pay Attention 092904

p35 hamilton
18. 06. 2007
0 views

p35 hamilton

Riverside Ballroom Day2 215
18. 06. 2007
0 views

Riverside Ballroom Day2 215

QS plat sg2k
18. 06. 2007
0 views

QS plat sg2k

Prensky 04 07 NCLB post
18. 06. 2007
0 views

Prensky 04 07 NCLB post

pimrc 05 B
18. 06. 2007
0 views

pimrc 05 B

phys 560 Solar Neutrinos
18. 06. 2007
0 views

phys 560 Solar Neutrinos

HSTF Background
01. 11. 2007
0 views

HSTF Background

cis vdotolev
12. 10. 2007
0 views

cis vdotolev

impact of assessment
22. 10. 2007
0 views

impact of assessment

lecture20
28. 12. 2007
0 views

lecture20

poetry
15. 06. 2007
0 views

poetry

Context Future Technology
15. 06. 2007
0 views

Context Future Technology

New Credibility
15. 06. 2007
0 views

New Credibility

Secrets To Scientific Selling
15. 06. 2007
0 views

Secrets To Scientific Selling

Problem Solving Strategies
15. 06. 2007
0 views

Problem Solving Strategies

Power of one Person
15. 06. 2007
0 views

Power of one Person

Jack Dugan
26. 02. 2008
0 views

Jack Dugan

Prot Franjo
22. 11. 2007
0 views

Prot Franjo

pledge
15. 06. 2007
0 views

pledge

NOVE BernabeuMorales
01. 10. 2007
0 views

NOVE BernabeuMorales

vaisanen 181005
07. 10. 2007
0 views

vaisanen 181005

ASOCFILE092003051211 1920
22. 10. 2007
0 views

ASOCFILE092003051211 1920

01 Review of BKK Property Mkt
27. 03. 2008
0 views

01 Review of BKK Property Mkt

2006drt6903cours11
14. 11. 2007
0 views

2006drt6903cours11

abcstrea
19. 11. 2007
0 views

abcstrea

Yang Slid Sho
07. 11. 2007
0 views

Yang Slid Sho

IISR
26. 10. 2007
0 views

IISR

Mon Naughton
26. 06. 2007
0 views

Mon Naughton

praust
21. 11. 2007
0 views

praust

RH vili
18. 06. 2007
0 views

RH vili

DIPRE
17. 10. 2007
0 views

DIPRE

presentation prof liu
15. 10. 2007
0 views

presentation prof liu

Dynafluid Nozzle
03. 01. 2008
0 views

Dynafluid Nozzle