### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# AdvanTopics in CSInverse Problems in Imaging CSC 790

WFU

GPA 3.56

### View Full Document

## 16

## 0

## Popular in Course

## Popular in ComputerScienence

This 127 page Class Notes was uploaded by Melyssa Aufderhar on Wednesday October 28, 2015. The Class Notes belongs to CSC 790 at Wake Forest University taught by Errin Fulp in Fall. Since its upload, it has received 16 views. For similar materials see /class/230724/csc-790-wake-forest-university in ComputerScienence at Wake Forest University.

## Popular in ComputerScienence

## Reviews for AdvanTopics in CSInverse Problems in Imaging

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/28/15

TCPIP Review CSC 790 WAKE FOEST Department of Computer Science Fall 2006 High Speed Networks m TCPiP Review 1 TCPIP Reference Model quot Not present in the model OSI TCPIP Application Application Presentation Session Transport Transport Network Internet Data link Hosttonetwork Physical E w Fulp Fall 2006 TCPlP Rewew 2 High Speed Networks m Example TCPIP Protocols LL W layev protocol PL mm layev l Newukpoinlol alladwmem AP application pmloeovmocess lClvP lrlemel coma message pvoloool p lnlemel pvaoool lGMP Heme gvoup message pvaoool ARP address vesolunm pvaoool OSPF 0pm shay est pamm HARP vevevseA p Fall 2006 E w Fulp TCPlP Rewew 3 High Speed Networks m Internet Operation Overview Downlelorpoml Network a FDDl 0 Network layer takes data streams and breaks into datagrams Datagram can be up to 64KB each average is 1500 bytes 0 Each datagram is transmitted through the Internet Possibly fragmented 0 Pieces arrive at destination reassembled into original datagram o Datagram is passed to the transport layer Fall 2006 m w Fulp Hrgr Speed Networks m TCPrp Revrew 4 TCPI P EndtoEnd Communication Des nan39on host Applican39onPDUs Wica on 39 TCPUDP PDUs TCPUDP Access network Router gaieway CPUDP Irensmission oornrd probeduser datagram probed P Imemetp39orood LP Iirk probed PL physical layer E W Furp F2 2006 my Speed Networks m TCPrp Revrew 5 IP Packet Order or rrarrmssrorr r2 3 4 5 6 7 e 9 10H r21314rsre rergzozr2223242525272829303r32 rderrrrrcarron Fragment arse 39 mertorrve Protocor Header Header checksum Source rP addYeS Oprrorrs Payroad Payroad lt55535 byree 9 r0 H r2 r3 r4 rsre a Hrgh rdraurrry Hrghthroughpm Low deray Prromy o7 rHL rrrermedrare header rergm M morerragmerrs Ddorr Hragmerrt E W Furp F2 2006 High Speed Networks m TCPlP Review 6 IP Fragmentation and Reassembly 0 Different network technologies have different packet sizes Every network has 3 Maximum Transmission Unit MTU fthe datagram is larger than the MTU then it is fragmented Neiwoik l Ememel W0 Hl Fll R2 R3 HE Neiwoik 2 Ememe 39 MTU1500 byes R MTU532byie 00 1420 byles loial payload lPHeadeiisZOby es E W Fulp Fall2006 ngh Speed Networks m TCPlP Review 7 0 Assume R2 has a MTU data of 532 bytes allows a 20 byte header and 512 bytes of data 0 The original 1420 byte datagram fragmented into 3 pieces at R2 Original Dalagram Daiagram Fragmented l Siaiiolheadei l l Siaiiolheadei l l ldenigtlt l l lol Ollsei0 l l ldenigtlt l l 1 Ollsei0 l l Resiolheadei l l Resiolheadei l l 1400 daiabyies l 512 daiabyies Slail Ol headei II Rest Ol headei Slail Ol headei Ila Rest Ol headei 0 RFC 1191 gives some example MTU sizes based on the link layer E W Fulp Fall 2006 H gh Speed Networks m TCP P Rev ew 8 Example IP Fragmentation Souvce host Desmauon hOS 70008 Access gateway Acce gateway W E 14909 E 4808 E O BB El 4808 i E 4808 397 El 549 Tokew mg i n eme g oba E hema r LAN n eme wovk 7 N TU 40008 N TU 5008 Not e A Va ues shown ave he amounts a use data m each packetheme n bytes Token Ring LAN Fiame Frame 2 den mca m 20 20 Tda eng h 7000 7000 Fvagmem o se o 497 Use data 3975 3024 Mb 0 Ethernet LAN Fiame Frame 2 Frame 3 Fiame4 Frame 5 Frame 6 den mcat on 0 2 Tda eng h 7000 7000 7000 7000 7000 7000 Fragment O SS 0 85 370 497 582 876 Use data 480 480 0 6 480 480 54 NH 0 E W Fu p Fa 2006 High Speed Networks m TCP P Review 9 IP Network Example Consider one router and seven hosts one address per interface 0 Three hosts at bottom have similar addresses 22131110 The leftmost 24 bits they share is the network portion Remaining 8 bits is the host portion How many hosts can connect to the 22311ac network m w Fu p F2 2005 m ngh Speed Networks m TCPlP Revlew Hosts of 22131110 form a network interconnected via a LAN The network address is 22311024 The 24 is also called the network mask or network prefix gtr Indicates the 24 leftmost bits define the network address Any additional host that would attach to this network must have a unique address of the form 22131110 The remaining networks have a similar structure 22313024 m W ngll Fulp Speed Networks m TCPlP Revlew 1 Fall 2006 Multiple IP Networks lP definition of a network is not restricted to Ethernet segments 0 Consider three routers interconnected via point to point links 2234 1 1 223t1t1t4 W Fulp Fall 2006 10 High Speed Networks m TCPiP Review 12 0 Each router has three interfaces One for each point to point link One for the broadcast link to the hosts 0 What are the networks in the diagram Three networks interconnecting hosts 22311024 22312024 and 22313024 Three additional networks that interconnect routers gtk 22317024 connects R1 gt R2 gtk 22318024 connects R2 gt R3 gtk 22319024 connects R3 gt R1 0 How do we determine what is a network Detach each interface from host or router Resulting islands are the networks E W Fuip Faii 2006 High Speed Networks m TCPiP Review 13 P Classful Addresses Number 0 Nelld l Hoslld ClassA 1502255255 2 14 16 IIIIIIIIIIIIIIIIIIIIIIIIIIII 1ol Nelld l Hoslld JCIassB 13350502205255 Unmas 3 8 IIIIIIIIIIIIIIIIIIIIIIIIIII 11lol Nelld l Hoslld Classc gggggggm 4 28 lIIIIIIIIIIIIIIIIIIIIIII 1391 1o Mullioasladdress ClassD ggggsosoz sggss Mullloasl 4 IIIIIIIIIIIIIIIIIIIIIIIIIII 11l1l1l ClassE 330502 52255 Reserved E W Fuip Faii 2006 High Speed Networks m TCPlP Review 14 o In the diagram each interface Ethernet card is labeled in red 0 For example the router has 3 interfaces ethO eth1 and eth2 Example Routing Tables 223113 223112 223111 Each interface must be uniquely identified since it attaches a unique network Fall 2006 E w Fulp High Speed Networks m TCPlP Review 0 An abbreviated routing table for host A would be Routing Table for A Destination Next Hop Interface 22311024 ethO 22312024 223114 ethO 22313024 223114 ethO First entry indicates 22311024 is the local network The second and third entries indicate datagrams for destinations on network 22312024 or 22313024 must be sent to 223114 ethO is the Ethernet interface only one card on A Each network is represented with one entry how many would 15 be required if each host had a separate entry Fall 2006 E w Fulp m High Speed Networks m E w Fulp High Speed Networks m TCPlP Review 16 0 An abbreviated routing table for the router would be Routing Table for Router Destination Next Hop Interface 22311024 ethO 22312024 ethl 22313024 eth2 First entry indicates 22311024 is local on ethO Second entry indicates 22312024 is local on ethl Third entry indicates 22313024 is local on eth2 TCPlP Review Fall 2006 17 IP Routing Steps 0 IP routing performs the following actions 1 Search routing table for complete destination address if found send packet to the next hop entry M Search routing table for an entry that matches the destination network number if found send packet to the neXt hop entry Must take into account possible subnet mask 3 Search for default entry if found send to next hop router 0 IP search order is host address a host network a default o If all the steps fail then the datagram is not deliverable W Fulp Fall 2006 m High Speed Networks m TCPlP Review 18 Routing Example A gt B Assume A 223111 sends datagram to B 2231 13 223111 223113 Link lP II Desi 223113 LLAol 223113 0 There is no host entry for 2231 13 0 There is a network entry for 2231 1024 0 A link layer frame containing the datagram is created and addressed to the link layer address of 223113 We are at layer 5 how do we get a layer 2 address 0 Ethernet frame is sent and received by host B E w Fulp High Speed Networks m Fall 2006 TCPlP Review 19 Routing Example A gt E Assume A 223111 sends datagram to E 223122 Routing Table for A Routm Table for Router Destination Next Hop Interface Destination Next Hop Interface 22311024 ethO 22311024 ethO 22312024 223114 ethO 22312024 ethl 22313024 223114 ethO 22313024 em 0 Host A finds entry for 22312024 network Requires sending packet to 2231 14 0 Host A creates and sends link layer frame containing datagram addressed to the link layer address of 223114 Therefore the next hop entry is used for the link layer address IP destination address remains unchanged W Fulp Fall 2006 High Speed Networks m TCPlP Review 20 o Router 223 1 1 4 receives frame and removes datagram Destination address is 223 122 Router is allowed to forward datagrams o Router finds entry for 223 1 2024 network This is directly connected via ethl Datagram will be forwarded Router creates and sends link layer frame containing datagram addressed to the link layer address of 223122 on ethl 0 Frame received by host E datagram removed and processed NB operation of host and router are equivalent except routers are allowed to forward datagrams Fall 2006 E w Fulp High Speed Networks m m TCPlP Review 21 Link IP D t Header Header a a Dest223122 LLAOf223122 D Link IP D t Header Header a a Dest223122 LLAOf223114 W Fulp Fall 2006 m Htgh Speed Networks m TCPtP Rewew 22 Example IP Subnet Address Address Structure 1 81624 32 Internetwide netid Hostid l4 Internet routing part gtlt Local part gt Example Address 1 16 24 32 Hostid J Routing within the netid lt gt Subnetid m W an Htgh Speed Networks m Rm 2006 TCPtP Rewew 23 ARP and RARP Message Format ARP am RARP quotwage lormm wee gtt 8 9 p Handmn typ Fitment We HLEN PLEN lapmum 7 PLEN P addvgs tenglh 5nd hamquot 0M Opevanon 1 ARP vequw ARP yspense S RARP vequw 7 Sunday tP add 7 e A RARP yspense Target hardware addrlu 7 Target w address 7 MAC lrame IOI llm Wm ARPHARP data A t 500 4 rcs Ems Ethemet DA SA Type Awmpmesugemtrdmmm 6 301492 4 e 2 tEEEEOZSDA sA Lengthi LLO Tpe ARPRARP mssage ortP datagvarr F08 Type tvametype 0000 peg thA datagvam 0306 ARP vequs vepty mssage z RARP vequs vepw meesage W an Rm 2006 High Speed Networks m m Simulation CSC 790 WAKE FOEST Department of Computer Science Spring 2009 Simulation 1 Operational Laws 0 Many day to day performance analysis issues can be solved simply May not know the distributions of service or arrival Some distribution attributes are difficult to measure Suppose you are measuring the arrivals at a web server how do you know from the data if arriuals are independent Just need simple relationships called operational laws What is one operational law we have already seen 0 The word operational indicates directly measured Therefore they are operationally testable 0 NB many of these laws are for closed systems W Fulp Spring 2009 High Speed Networks m Simulation 2 Operational Quantities 0 Operational quantities are those that are measured over an interval number of arrivals A Arrlval rate 5 J tIme t number of com letions O Throughput Xi J tIme t bus time B UtIlIzatIon UZ J total tIme t total time served Bi Mean serVIce tIme Si 7 number served 0 How large shouldt be 0 These operational quantities are variable Value can change from one period to the next But certain relationships should hold in every period m w Fulp Spring 2009 High Speed Networks m Simulation 3 Utilization Law 0 Given the number of completions O and the busy time B of device i during a time period t the following is true B O B UJJJXS z t t z 2 Consider a network gateway where packets arrive at a rate of 125 packetssec and the gateway takes 2 msec to forward what is the throughput mean service time and utilization E w Fulp Spring 2009 High Speed Networks m m Speed Networks m m Forced Flow Law o Relates the system throughput to individual device throughputs Consider a system of devices for example a computer 0 Vi is the visit ratio of device i com pared to the completions Oi Oi Col239 n 70 which is the mean completion at i per task completed IsVilt00rstigt0 0 Let X be the system throughput 7 number of completions 7 00 time t W High Fulp Simulation o The throughput of the 1 device is Ci 7 Ci CO Xi Vi39 ViX tOOt t which is called the forced flow law we are assuming flow balance What is flow balanced o Combing the forced flow law and utilization law UZ XiSZ XVZSZ XDZ where DZ ViSZ is the total service demand for device i Device with the highest DZ is the bottleneck of the system Assume tasks generate on average 5 disk requests and disk throughput is 10 requestssec What is the system throughput W Fulp Simulation 4 Spring 2009 5 Spring 2009 High Speed Networks m m Simulation 6 General Response Time Law o Little39s Theorem can be applied to any part of a system Only requirement is that the part be balanced 0 Consider a timesharing system that has two components Set of terminal one terminal per user Central computer system shared by all the users 0 We can apply Little39s theorem to the computer system Q XR where Q is the total number ofjobs in the system B is the system response and X is the system throughput W Fulp High Speed Networks m m Spring 2009 Simulation 7 0 Given the individual queue lengths Q of the devices in the computer system then QQ1Q2QM where there are M devices this equals XR X1R1 X2R2 XMRM o Dividing both sides by X and using the forced flow law R V131 V232 VMRM which is the general response law M RRVZ W Fulp Spring 2009 m High Speed Networks m E w Fulp High Speed Networks m Simulation Interactive Response Time Law 0 Consider M users and a timesharing system 0 Let the mean wait time response per user at a terminal be R 0 Let the mean thinking time by a user be Z 0 The total mean time would be R Z 0 From Little39s Theorem we know M XR Z total number of requests where X IS the system throughput total tlme o The interactive response time is M 3772 X Spring 2009 Simulation Predicting Performance Experimentwlth system physical model l mathematical model 0 We have developed analytical methods for predicting performance Single queues Jackson networks and operational laws Requires several assumptions which may not be realistic 0 An alternative is to test with an actual system Although precise typically this is not feasible 0 We can use simulation to predict performance Assumptions may not be as restrictive as analytical methods W Fulp Spring 2009 9 8 m High Speed Networks m Simulation Systems and Models 0 A system is a collection of entities people machines etc Interact together toward the accomplishment of a goal 0 The state is a collection of variables about the system Describe the system at a particular point in time 0 Simulation models can be classified using three categories 1 Static or dynamic models A static system is one where time has no role Dynamic represents a system that changes over time What is an example of each 2 Deterministic or stochastic models Deterministic models do not contain any randomness Stochastic models have random components E w Fulp Spring 2009 High Speed Networks m Simulation 11 What is an example of each 3 Continuous or discrete models Continuous systems have state that changes continuously Discrete systems have state that changes instantaneously What is an example of each 0 We will focus on models that are discrete dynamic and stochastic also called discrete event simulation W Fulp Spring 2009 o High Speed Networks m Simulation 1 Discrete Event Simulation 0 Concerns modeling a system as it evolves over time State variables can change instantaneously Mathematically speaking the system can change at only a countable number of points These points are when events occur therefore DES can be done using paper and pencil For ezrample 9 0 Every DES requires a simulation clock Must record the current time indicates when next event occurs What is the simulation clock How do we advance time E w Fulp Spring 2009 High Speed Networks m Simulation 1 0 0 There are two possible DES time advance mechanisms Fixed increment time advance increment the clock by At and determine poll if any events will occur M Next event time advance update the clock to the time when next event occurs 0 Next event time advance the clock is initialized to zero Times of future event are determined Clock is updated to the time of the most imminent event Once the time is changed the system state is updated and future event times are determined E w Fulp Spring 2009 m High Speed Networks m Simulation 14 Components of a DES 0 System state variables necessary to describe the system 0 Simulation clock variable giving the current simulated time 0 Statistical variables store performance values 0 Initialization routine steps required to initialize system 0 Timing routine determines the next event to occur typically this is an ordered list of events called the calendar 0 Event routine updates the state for a certain event 0 Report generator creates reports of performance E w Fulp Spring 2009 High Speed Networks m Simulation 15 MMl Example 0 Assume we wanted to simulate a MMl queue buffer arrivals depatures server What type of events would the simulation have How are the events related When does the simulation stop m w Fulp Spring 2009 ngh Speed Networks m m Swmu amon 16 schedu e Amva at t O to ca endar check ca endar remove next event from ca endar set dock t to the ume ofevent remove from queue then check queue schedu e next departure at me t AtD schedu e next departure at me t AtD schedu e next amva at ume t AtA not empty add to queue W Fu p Sprmg 2009 Basic Queueing Models csc 790 WAKE FOREST Department of Computer Science Spring 2009 High Speed Networks m Basic Queueing Models 1 Queueing Models 0 The work by Erlang lead to several fundamental models Analysis of resource sharing systems 0 Model consists of consumers and resources Customer demands are at random times Duration of use is also random If all the resources are used the customer waits in queue o Queueing theory addresses these type of systems E w Fulp Spring 2009 m High Speed Networks m Basic Queueing Models 2 Little39s Theorem 0 We have already established the relation N AT where N is the average number of customers in the system T is the average customer time in the system and N is the average number of customers in the system 0 Cannot specify these values further Need to know more about the statistics of the system Statistics about what 0 Given the statistics we can then derive the wait time as well as the number of customers in the queue p7 probability of 11 customers in the system m W High Speed Networks m Fulp Spring 2009 Basic Queueing Models 3 Arrival Processes 0 Assume customers arrive with interarrival times 7391 72 Also assume interarrival times are independent random variables with the same distribution 0 The arrival rate to the system is 1 W customerssec o What can we say about the arrival pattern lnterarrival times are deterministic when interarrival times are all equal to the same constant What is an example What does the PDF look like lnterarrival times are exponential if the interarrival times are exponential random variables with mean El r 1 W Fulp Spring 2009 High Speed Networks m Basic Queueing Models 4 Poisson 0 Interested in the number of events occurring in a finite time For example the number of file requests during a time period 0 Such a random variable is a Poisson if PrX n La 67M 71 where n is the number of requests and A is a rate over the time period t m w Fulp Spring 2009 ngh Speed Networks m Basic Queueing Models 5 0 Important properties The average value is At which is also the variance Memorye55 so arrivals are independent of the past or future What does memoryless mean 0 In addition it has an important closure property Suppose X1X2 X are mutually independent Poisson distributed random variables with parameters A17 A2 A7 Then X X1 l X2 l X7 is a Poisson random variable with parameter A A1 A2 A7 What does this mean 0 This sounds really great but we are interested in interarrivas E w Fulp Spring 2009 High Speed Networks m Basic Queueing Models Exponential 0 Assume arrivals are Poisson distributed with rate A o What is the probability of no requests in an interval s 7 A gt06 s 0 PrX 0 A5 e7 True for any interval t t s is e where t is arbitrary remember the memoryless property 0 Let tn be the time of the n ih arrival The probability the n 1 5h arrives during tmtn s is 1 7 eiks just the inverse of the probability of no arrivals during s m w Fulp High Speed Networks m Spring 2009 Basic Queueing Models 7 o More formally we say this is an exponential distribution Pr r s17e 57 s20 where 739 tn1 7 tn it also known as a Poisson arrival process 0 It is a memoryless process allows tractable analytical results Suppose the lifetime of an appliance has an exponential distribution with an average of 10 years After 5 years the appliance is sold What is the probability that it will not fail in the neat 5 years Exponential Dismbutlun rate 2 5 E w Fulp Spring 2009 6 High Speed Networks m Basic Queueing Models What 0 We were discussing queues and arrivals Now discussing exponential distribution what went wrong 0 Remember the arrival pattern of packets customers is important We may know the average interarrival time between packets but we need to also describe the variation m w Fulp High Speed Networks m Spring 2009 Basic Queueing Models o A queueing system Kendall Notation is specified by the following information Arrival process service mechanism and queue discipline The Kendall notation was developed to define these values Kendall notation is a series of letters separated by quot ABCKmz Where the letters represent A is arrival process B is the service process C is the number of servers K is the maXimum capacity of the queue buffer if it is an infinite queue Koo it is typically omitted m is the population of customers m 00 is assumed Z is the service discipline FIFO is assumed E w Fulp Spring 2009 8 High Speed Networks m Basic Queueing Models 10 o A and B have specific values depending on the distribution M is a Poisson exponenetial distribution D is deterministic GI is general independent can be any distribution G is general can be any distribution not necessarily independent Hk is hyperexponential distribution of order k E is Erlang distribution of order k Consider a multiplexer that has multiple inputs links and transmits over a single output link If arrivals and service times are ezrponentially distributed what is the Kendall notation for this system What is the Kendall notation for an ATM switch E w Fulp Spring 2009 High Speed Networks m Basic Queueing Models 11 M M 1K A buffer arrivals depatures gt server Id K gt 0 Consider a multiplexing system with the following assumptions lnterarrival times 739 are exponential with mean Elr Service time is exponentially distributed with a rate u PrX gt t e Ht for t gt 0 What type of system would have a variable service time SpringQOOQ m W Fulp m High Speed Networks m E w Fulp High Speed Networks m Basic Queueing Models 12 0 Consider a long term flow of packets to the system Packets arrive at a rate A packetssec Maximum rate at which packets depart is M packetssec If A gt M then the system will lose packets unstable If A lt M then the system can handle the packets Would the case ofA lt M result in delays or lost packets 0 Want to develop models to quantify these effects Spring 2009 Basic Queueing Models 13 System Arrivals and Departures 0 Consider what happens in the next At seconds In terms of arrivals there can be 0 1 or gt1 In terms of departures there can be 0 1 or gt1 But as At a 0 only one or or zero arrivals or departures o If the interarrival times are exponential then P7 1 arrival in At AAt 0At where 0At denotes negligible terms relative to At Where did this equation come from 0 Similarly we can have no arrivals in At Pr0 arrivals in At 17 AAt 0At W Fulp Spring 2009 m High Speed Networks m Basic Queueing Models o If the departure times are exponential then P7 1 departure in At MAt 0At 0 Similarly we can have no departures in At P7 0 departures in At 1 7 MAt 0At which means the current customer packet will continue its service after At 0 So we know the probabilities of arrivals and departures Combine these probabilities to model the state of the system 14 15 w Fulp Spring 2009 ngh Speed Networks m Basic Queueing Models Steady State Probabilities 0 We can now determine the probability of change in the system 0 The probability of no arrivals or departures is Pr0 arrivals and 0 departures in At 1 7 pAt 0At17 AAt 0At 1 7 A MAt 0At also the probability the system is the same after At seconds 0 The probability of one arrival and no departures is Pr1 arrival and 0 departures in At 1 7 uAtoAtAtoAt AAt 0At which is the probability the system increases by 1 after At seconds w Fulp m Spring 2009 High Speed Networks Basic Queueing Models 16 o The probability of no arrivals and 1 departure is Pro arrivals and 1 departure in At pAtJr 0At1 7 mm 0At pAt 0At which is the probability the system decreases by 1 after At seconds 0 Remember we are only considering a very small time interval At during this time the system can Stay the same with probability 17 MAt Increase by one with probability AAt Decrease by one with probability MAt E w Fulp High Speed Networks Spring 2009 Basic Queueing Models 17 State Transition Diagram 0 State transition diagram for the number of customers Nt is 14m 1 AMAt 17AMAt 17AMAt 14Awgtm 14m 0 AAt O AAt O AAt 0 AAt aa Em um um o If the system is stable Nt does not grow towards infinity Transition rate from n to n 1 should equal n 1 to n 0 Let pn be the probability that 7 customers are in the system pmwm pnAAt The probability that you are in state 7 and you go to state n 1 should equal the probability you are in state n 1 and you go to state 7 E w Fulp Spring 2009 m High Speed Networks m Basic Queueing Models 18 0 Therefore we can say A pn1 pna 0517quot 7K 0 Applying this definition recursively until 190 A 77 pn1 p717 n 07 17 1 pn1 p 190 where p g which is also utilization 0 To find 190 we know that K 710 pop1p2pKpo1pp2pK1 w Fulp Spring 2009 ngh Speed Networks m Basic Queueing Models 19 1 7 p P0 1 7 pk 1 0 Therefore p71 is 1 7 p p P7 Nt n 1 for n 012K What is the probability of blocking 07 loss 0 Congratulations you have just developed a Markov chain 0 Consider the probabilities as p varies If p lt 1 underload then the system stays around state 0 7 7 1 If p i 1 then each state IS equally pOSSIble p71 7 m If p gt 1 overload then the system stays around state K w Fulp m Spring 2009 High Speed Networks m Basic Queuemg Models 20 Number of Customers and Wait Time o The average number of customers packets in the MMlK K K 1 imp p N 7 i i i K equation IS not valId when p i 1 when p i 1 then N i 7 K WK 1 pK1 o The average wait time delay is obtained using Little39s Theorem N T we Why is the denominator M17 19K E w Fulp ngh Speed Networks m Spring 2009 Basic Queuemg Models 21 MMl 0 Let39s consider the MMl queue Koo State transition diagram Markov chain is the same except states can be any nonnegative integer o Probabilities are still related by Pn1 P0 P P0 M 0 Still use the summation of the probabilities to find 190 219239P0P1P2P01PP21 20 1 P017 summation only converges if p lt 1 1 E w Fulp Spring 2009 High Speed Networks m m Basic Queueing Models 22 0 Probability of being in state n P7 Nt n Pp 17 NP 0 Probability of n or more customers PrNlttgt 2 n pi o The average number in the system N is 0 p p NZ 1 PP fp 710 0 The average delay is W Fulp ngh Speed Networks m Spring 2009 Basic Queueing Models 23 MMl Performance 0 System is stable when p lt 1 underload MMl oueue average delay 0 As the utilization approaches 1 performance decreases unstable MMl oueue Why does queueing exist when p lt 1 underload condition E w Fulp Spring 2009 m ngh Speed Networks m 82le Queuelng Models 24 pulley A pulley A pulley A server server server 0 Consider a single MMl system Scale and Performance Is it better to have in systems or one system that is in times as fast7 bullel selvel 0 Consider a set of m MMl systems parallel The arrival rate to each system is A packetssecond Each system processes at a rate M packetssecond The arrival rate to the system is m packetssecond The system processes at a rate my packetssecond Does it make since to simply add the rates m w Fulp ngh Speed Networks m Sprlng 2009 82le Queuelng Models 25 Why is this the case o The single system has a mean delay of o The parallel system has a mean delay of 1 T 7 p M179 1 T5 mmlip average delay 0 Since T5 Tp the single system is better MMl System Cumparlsun Slngle system Parallel w Fulp Sprlng 2009 m m High Speed Networks m Basic Queueing Models Server Example 0 Consider a LAN with 100 computers and a web server Average time for the server to respond is 06 seconds At peak times the requests rate is 20 requestsminute Web responses and requests are exponentially distributed Want to answer the following questions What is the average response time7 If an additional 20 utilization is experienced will response time increase by more or less than 20 7 w Fulp Spring 2009 High Speed Networks m Basic Queueing Models Return of Erlang o A call system can be modeled as a MMcc queue Calls arrive at a rate of A callssecond and last X seconds Each circuit is view as a server with rate p Ele A call is blocked if all the servers circuits are busy 0 39 sewer x M1b gt gt lb 0 A new connection increases N by 1 while a release decreases N The state of the system has the values 01c 0 As with MMl the probability of a call in the next At is AAL W Fulp Spring 2009 27 High Speed Networks 3m Queueing Models 28 o The departure rate is different than MMl lf Nt n are busy then each server will finish within At time with probability uAt Probability one connection releases and n 7 1 continue is nuAt1 7 uAt 1 nuAt Probability of two connections release uAt2 is negligible Therefore the departure rate when Nt n is nu lihAt 17AuAt 17A2uAt 17A3pm 17A4uAt 17mm 8 um 2pm sum 41qu 9 E w Fulp Spring 2009 High Speed Networks 3m Queueing Models 29 0 Following the MMlK analysis we have pn1n 1uAt pnAAt o This implies that Pn1 7 WM 0 Repeated applications of the preceding recursion Pn1 71 mp0 0 Let the offered load A i we must find 100 c An 1100 P1gtgtgtpCPOZH n E w Fulp Spring 2009 High Speed Networks m Basic Queueing Modeis 30 o The blocking probability is when n c Ai C P7 Nt 0 pc 20 2 7 Which is the Erang B formula m w Fuip Spring 2009 High Speed Networks m Circuit Switched CSC 790 WAKE FOREST Department of Computer Science Spring 2009 Circuit Switched W 1 Network Types Multimedia communication networks Telephone Data Broadcast televtsion Narrowband Broadband networks networks networks IS DN IS DN PSTN PBX X 25 Internet Cable Satelliteterrestrial LANs IS PNs Intranet Multimedia communication services pen L M PBX private branch exchange lSPNs Internet senice provtde network ISDN Integrated servtces digital network Fulp Spring 2009 High Sp eed Networks Circuit Switched 2 Network Types 0 Networks can be categorized based on Media data Internet video cable telephony Technology packet circuit or virtual circuit 0 Circuit switched provided dedicated circuits for transmission Most common example is Public Switched Telephone Network PSTN well is used to be 0 Circuit switched networks are suited for Constant Bit Rate CBR Why What is the bit rate for telephony m w Fulp High Speed Networks Spring 2009 Circuit Switched 3 Connection and Connectionless mm mm mm mm mum gummy Vienan mmpmgemma a 2mm 55 vci mum m ee Wciumlilguclal circuit switched virtual circuit E w Fulp Spring 2009 High Speed Networks Circuit Switched 4 PST N Components 0 PSTN consists of three major components Local loop Trunks toll offices and switching offices 0 Local loop Telephone connected via two wires up to 10km Analog signals carrying voice Lines connect to an end office About 19000 end offices in the US where the area code first three digits in a telephone number specify the end office Telephone to end office is the local loop E w Fulp Spring 2009 High Speed Networks Circuit Switched 5 o Trunks End office are connected to to offices lfthe call can be connected via the same toll office its local otherwise it is considered long distance Lines used are called to collecting trunks o Trunks are high bandwidth connections between elements Multiplex several connections on the line 0 Two types of multiplexing used Frequency Division Multiplexing FDM uses different frequencies to transmit multiple information simultaneously Time Division Multiplexing TDM gives each connection a certain time slot E w Fulp Spring 2009 CWCMH Switched 10 Regional offices High Speed Networks ATampT Switch Hierarchy lt m interconnected 030 n A A v lt p394 Ra Em V 7 I ll 07 Sectional offices s I 230 Primary offices X l x lSOOToH emces 19000 End Offices 9000 o a 0000 0000000 1 2 3 4 5 200 Mllllon telephones l E w Fulp Spring 2009 High Speed Networks Clrcult Switched Creatlng a Connection o End to end path is established before data is sent Initial delay for call setup 0 All data will follow the same path No congestion will occur What How is this possible Should there be any delay 0 Once data transfer is complete the connection is released 7 Spring 2009 E w Fulp High Speed Networks Circuit Switched 8 Call request signal PM 1 Propagation delay M59 PM 2 Pkt 1 T 7 7 77 7 PM 3 PM 2 Msg Queuing PM 1 delay PM 3 33 w E hunting g 39 or an PM 3 utgoing l runk M59 Call accept signal Data AB BC CD trunk trunk trunk A B C D A B C D A B C circuit switching message switching packet switching m w Filip High Speed Networks Spring 2009 Circuit Switched 9 Transmission Forms 0 Digital signal transmission can have one of three forms Asynchronous synchronous or plesiochronous o Asynchronous communications each network device has own clock Therefore clocking signal needed What What is an emample o Synchronous communications require all clocks to be synchronized What is an example What are the advantages 0 Plesiochronous is also synchronized but allows more variation E w Filip Spring 2009 m Higi Speed Networks E w Fulp Higi Speed Networks Circui i Switched 10 SONET o Synchronous Optical NETwork SON ET developed by Bellcore Initially designed for digital telephony circuit mode Really a multiplexing or transport protocol 0 All equipment is synchronized to a single master clock Loca external timing uses an atomic clock located in the same place as the SONET equipment Line derived timing required equipment to derive the time based on the line Hold over a last resort requires equipment to keep a local clock until better timing is available 0 Timing loops are possible where devices derive timing based on others and precision is lost Spring 2009 Circuit Switched 11 SONET Layers o SONET system can be divided into three layers Section fiber between two adjacent devices deals with signaling over the fiber Line span between two adjacent multiplexers can span multiple sections concerns transport of multiplexed streams Path connects two SONET end points Destination gt Sublayer Path Line Section Photonic Source Repeater Multiplexer lt Section Section gt Section Line Line gt Path W Fulp Spring 2009 High Speed Networks Circuit Switched named enmes SE mm mimequot quipmm TE lim humiliation quipmm PrE ml lumilmllm mumm wmul minim l39VCl 12 E w Hip High Speed Networks Spring 2009 Circuit Switched 13 SONET Framing o Adjacent multiplexers exchange info using frames Not really the same as a layer 2 frame Columns for overhead B7 Sonel 125 usec Sonel usec I Path overhead Section Line overhead D overhead 0 A frame is a block of bytes 9 rows by 90 columns Therefore 8 gtlt 9 gtlt 90 6480 bits per frame E w Fulp Spring 2009 m High Speed Networks Circuit Switched o Frames are repeated 8000 timessecond Therefore 6840bits0125sec 5184Mbps This is called a Synchronous Transport Signal STS l o Synchronization is difficult but very helpful Same byte position in a frame arrives every 0125 seconds quotThis relation allows an extremely useful behavior of synchronous optical networking Which is that low data rate channels or streams of data can be extracted from high data rate streams by simply extracting octets at regular time intervals there is no need to understand or decode the entire framequot 0 Ethernet frames are header payload and trailer sent in order 0 SONET frames actually interleave the header and payload Some header then some payload then some header etc Repeats until the frame is transmitted E w Filip High Speed Networks 14 Spring 2009 Circuit Switched SONET Frames 3 Columns for overhead Sons 125 usec Sons 125 usec Section overhead Pa D Line lh overhead overhead SPE 0 First three columns of each frame is for system overhead First three rows are for section overhead framing and error Next size rows are for line overhead sync and muX W Hip 15 Spring 2009 High Speed Networks Circuit Switched 16 o Remaining 87 columns are the information payload Data rate is 87 X 9 gtlt 80125 sec 50112Mbps One column is for path overhead Payload is the Synchronous Payload Envelope SPE Therefore the SPE is inserted inside a STS l frame 0 STS l signal can be broken into virtual channels Virtual tributaries represent slower bit rates Virtual tributary is 12 gtlt 9 gtlt 80125 sec 61912 Mbps How many voice channels per virtual tributary E w Fulp Spring 2009 High Speed Networks 1 Circuit Switched 17 Pointers and Multiplexing o SPE does not always start at row 1 column 4 of STS l It can actually start anywhere within the 87 columns Pointer in the line overhead points to the start of SPE Therefore a SPE can span two STS l frames Why Multiplexing is also an important part of SONET Each data stream is a tributary basic is 5184 Mbps As more tributaries are multiplexed rate must increase nXSTS l which is a n STS E w Fulp Spring 2009 High Speed Networks Circuit Switched 18 SDH o Synchronous Digital Hierarchy SDH is very similar to SONET Developed by International Telecommunications Union ITU Used by everyone except for US and Canada eh o SDH offers a few more options as compared to SONET E w Fulp Spring 2009 High Speed Networks Circuit Switched 19 SO N ET Transports What 0 SONET is a generic transport protocol Possible to transport other network technologies 0 Examples include Asynchronous Transfer Mode ATM Packet over SONETSDH POS 10 GbE Sounds awesome what is the catch E w Fulp Spring 2009 m E w Fulp High Speed Networks High Speed Networks Circuit Switched Switches 0 Circuit switches transfer signals From an input to an output There are three major types of switches Space division Time division Space and time division Spring 2009 Circuit Switched 21 Space Division 0 Space division switches provide separate connections e 0 An example is the crossbar switch Consists of n gtlt n array of crosspoints Input to output crosspoint is closed for connection duration Considered a non blocking design connection is never denied due to lack of connection resources When can it be denied 0 Complexity of crossbar is n2 which isn39t scalable W Fulp Spring 2009 o High Speed Networks Circuit Switched 22 Multistage Switch 0 Multistage switch is another space division design Consists of interconnected small crossbars stages NiBri4lltZ NiBri4llt3 Crussbars N N N 7 Cmssbars 7 Crussbars 7 Crussbars N inputs N uutputs N inputs N uutputs a b 0 Consider a 3 stage switch N input and N output First and third stages group input lines into n assume k crossbars at second stage first and third stages are n gtlt k m w Fulp Spring 2009 High Speed Networks Circuit Switched 23 o How many crosspoints are required FirststagenkNk Second stage k Third stagenkNk Total 2Nkk g2 Fewer than crossbar What is the problem E w Fulp Spring 2009 ATM Networks csc 790 WAKE FOREST Department of Computer Science Spring 2009 High Speed Networks m ATM Networks 1 Integrated Networks 0 We know networks can be categorized based on media Voice data and video each has a specialized network Is there are need for separate networks 0 In the 197039s Integrated Services Digital Network ISDN started Single integrated network to carry various digital traffic Narrowband ISDN N ISDN provides 144 Kbps Bit rate was too low and the service too expensive 0 Broadband ISDN B ISDN is the second generation Based on Asynchronous Transfer Mode ATM networks B ISDN provides 155 Mbps transfer rate E w Fulp Spring 2009 High Speed Networks m ATM Networks 2 ATM 0 ATM combines features from circuit and packet switched Why is this necessary 0 Four important characteristics of ATM 1 Service is connection oriented uses virtual circuits m w Fulp Spring 2009 High Speed Networks m ATM Networks 3 How does a virtual circuit work What is the di erence between a virtual circuit and a circuit 2 Data transferred using 53 byte cells 48 byte payload Why 55 bytes 3 Uses statistical multiplexing 4 Can treat cell streams connections differently Q05 0 NB while ISDN may have been the motivation ATM is a network technology that can be used for any wired network E w Fulp Spring 2009 m High Speed Networks m ATM Networks 4 A What does asynchronous mean7 0 Consider a T1 carrier a given below L r t 1 22 23 24 l 2 3 4 5 6 l 7 E l 9 lU ll 12 13 14 15 16 17 18 19 2U 21 22 23 24 l l 2 Channel 1 gets ekactiy 1 byte atthe start ofeach frame J a l2l1l1lal7l1lwlal1l5l1l There is no requirement about cell ordering 1 cell b 53 bytes Frame generated every 125 usec Slot h of each is for a certain source T1 is synchronous 0 ATM does not have this requirement As seen in cells can arrive randomy m w Fulp Sprwg 2009 High Speed Networks m ATM Networks 5 BlSDNATM Model 0 Network model has three layers and two planes Layers physical ATM and adaptation Plane management Layer management Control plane User plane Upper layers Upper layers we akao CS Convergence sublayer 79377777 ATM adaptation layer eeeee 771 SAR Segmentation and SAR ly sublayer ATM layer tn TC Transmission convergence cupa su layer 19 physica layer quot49quot PMD Physical medium PMD dependent sublayer Planes user control layer and plane plane plane We know what the layers represent what about the planes w Fulp Sprmg 2009 High Speed Networks m ATM Networks 6 Model Overview and Comparison OSI layer layer ATM sublayer Functionality CS Providing the standard interface convergence Segm entation and reassem bly Flow control Cell header generationextraction Virtual circuitpath managemen Cell multiplexingdemultiplexing 7777 r 7 Physical TC Cell rate decouplin Header checksum generation and veri cation Ce generation Packingunpacking cells from the enclosing envelope Frame generation Bit timin Physical network access E w Fulp High Speed Networks m Sprmg 2009 ATM Networks 7 Physical Layer 3 Maps ATM cells to the physical transmission medium 0 Physical layer is divided into 2 sublayers Physical Medium Dependent PMD sublayer Transmission of bits over the medium Bit encoding pulse shapes and timing Transmission Convergence TC sublayer Establishes and maintains boundaries of ATM cells Verifies checksums and removes ide ATM cells 0 There are three methods of transport Cell adaptation to the frame structure of the transport medium PDH SDHSONET FDDI Cell based physical layer E w Fulp Sprmg 2009 High Speed Networks m ATM Networks 8 Parts of an ATM Network 0 User Network Interface UNI connects user to network 0 Network Network Interface NNI connects network devices NetwuvkrNelwuvk lme acE 0m 0 Generally speaking ATM networks are point to point oriented What is the advantage of a point to poz39nt topology E w Fulp Spring 2009 High Speed Networks m ATM Networks 9 ATM Layer 0 Responsible for switching cells from source to destination Also deals with global addresses 0 ATM layer is connection oriented There is a two level hierarchy Virtual Virtual path circuit Transmission Basic element is the Virtual Circuit VC 0 VC is one connection path between source and destination All cells for the connection must follow the established path E w Fulp Spring 2009 High Speed Networks m ATM Networks 10 Does not provide ACK39s Are there any guarantees 0 Virtual Path VP is a group of VC39s Can be dynamic or static Often assume the lifetime a VP is greater than a VC What are the advantages of the two level hetrarchy m w Fulp Spring 2009 High Speed Networks m ATM Networks 1 ATM Cell 0 ATM transmits 53 bytes cells fixed length 5 byte header UNI and NNI and 48 byte payload Useerelwovk imenace NelwovkrNelwovk imenace Busas755432i s755432i i GFC l VPl VPI 2 VPl Header 3 VCI VCl c c 4 PTI ll PTI ll 5 HEC HEC 5 48mm Aaocm Payload minimum Inbrmullon eld eld OOOrusev dala noconges om SDU lypeO are geneneiiow eonuoi PTi payloadlype identi er 00i ruse dala noconges om SDU iypei VPi vmual path identi er CLP cell loss pnomy OtOrusev dala congestion SDU lypeO veiwmai circuit identi er HEC header enov checksum 0H 7 usev dala congestion SDU iypei 1 l 0 7 H0 7 Network eonuoi n E w Fulp Spring 2009 High Speed Networks m ATM Networks 12 Header Fields 0 UNI header has siX fields 1 Generic Flow Control GFC only for UNI supposed to provide flow control for users sharing network device Does this make sense Virtual Path Identifier VPI 8 bits the virtual path Virtual Channel Identifier VCI 16 bits the virtual channel Payload Type Identifier PTI defines the type of payload 9quot Cell Loss Probability CLP 1 bit establishes two classes if set to one then discard when congested 6 Header Error Control H EC CRC checksum of the header 0 NNI header does not have a GFC field these bits are given to VPI E w Fulp Spring 2009 ngh Speed Networks m ATM Networks 13 ATM Addresses 0 An unusual feature of the ATM cell is the lack of addresses IP provides source and destination addresses Required for routing packets 0 ATM cells have VPI and VCI values Number of bits for VPI differs for UNI and NNI headers We need addresses to uniquely identify a source and a destination in the network does the VPIVCI separately or together provide this E w Fulp Spring 2009 E w Fulp High Speed Networks m ATM Networks 14 Connection Setup 0 Permanent Virtual Circuits PVC and switched Virtual Circuits PVC is similar to a leased line has a long duration A switched VC is dynamically created on demand 0 Creating a connection is a two step process Acquire a VC for signaling VPlO VCl5 Use this VC for requesting a new connection Message If Sent by Host If Sent by Network setup please establish a circuit incoming call call proceeding saw the incoming call call request will be attempted connect accept the incoming call call request was accepted connect ACK thanks for accepting thanks for making call release terminate call other side is done release complete ACK release ACK release High Speed Networks m m Spring 2009 ATM Networks 15 0 Consider establishing a VC that traverses two ATM switches 0 Note multicasting is possible by using add party signal b Source Destination h 51 5mm 1 5mm 2 h 51 Selu Call pmceedvng p s Call pTDCeedlUQ SIUK E W p l W connect W a W ReleaSe W Release complete Release KW W Fulp Spring 2009 High Speed Networks m ATM Networks 16 ATM Switching o The setup message goes from the source to the destination Routing algorithm determines the path of the message This path is the final VC if accepted ATM has no standard routing algorithm How would you mute the request 0 There are two types of switching Channel and path switching ch v03 v02 vm v03 v05 vcw vcw W 1 u 1 W at W W mm and paw mm E w Fulp Spring 2009 ngh Speed Networks m ATM Networks 17 o Switches along the path add an entry to their switch tabe Indicates the input port VPl VCl and output port VPl VCl Momma ATM SWllCH Do the VP1 07 V01 labels change as cells are switched Does this happen when IP packets are routed E w Fulp SpringQOOQ High Speed Networks m ATM Networks o The intended use of channel and path switching Channel switching only occurred at the UNI Path switching only occurred at the NNI Today channel and path occurs at the NNI Sorry Tanenbaum why would only allowing path switching in the NNI be helpful 0 A few more things about cel switching The VCIVPI field cannot be viewed as an address versteht7 If path switching is used all the VCl39s stay the same A VCI is local to a VP and a VP is local to a port Various VC39s are multiplexed on a VP and various VP39s are mutlipleXed on the same link each can have different QoS requirements E w Fulp Spring 2009 High Speed Networks m ATM Networks Example ATM VPI and VCI 0 Assume one connection where all numbers are VPI VCI 0 Assume E w Fulp Spring 2009 19 18 High Speed Networks m ATM Networks 20 0 Assume a third connection starts E w Fulp Spring 2009 High Speed Networks m ATM Networks 21 Quality of Service As previously discussed many applications require certain network performance bounds Quality of Service QoS guarantees 0 Delay Most real time applications are delay sensitive lf packet arrives beyond the delay bound it is useless 0 Delay variation Also called jitter relative difference between packet arrivals Do we know of any methods to smooth such arrivals Loss rate Probability ofa lost packet for example 1 gtlt 10 6 What is the problem associated with small loss bounds E w Fulp Spring 2009 m High Speed Networks m ATM Networks 22 ATM LAN 0 The original goal of ATM replacing PSTN has taken too long As a result ATM is more often used to interconnect LANs but it can also be used as a LAN technology Called LAN Emulation LANE How do you provide a connectione55 service over a connection oriented ATM network 0 You can create a permanent VC to all other machines in the LAN Assuming you are using IP over ATM how do you know which VC connects to a particular IP address Why does IP over ATM sound odd How does TOP1P networks determine who has a particular 1P E w Fulp Spring 2009 High Speed Networks m ATM Networks 23 0 LAN Emulation Server LES provides ARP like address translation Takes an IP address and returns appropriate VC This solves the host location probem but not broadcasting 0 Perhaps I39ll just buy 3 Gbps Ethernet switch and not worry about this probem w Fulp Spring 2009 Simulation Part 2 csc 790 WAKE FOREST Department of Computer Science Spring 2009 High Speed Networks m Simulation Part 2 Distributions 0 Given the random variables X1X2 Would like to determine the distribution ifpossibe Useful for empirical and simulation analysis 0 Need to determine the summary statistics Mean variance etc Determine if Xi are independent 0 Afterwards will fit histogram to density function Use goodness of fit tests to measure correctness E w Fulp Spring 2009 1 High Speed Networks m Simulation Part 2 Random Variable Statistics Let X be a random variable while xi is a possible value Mean or expected value of X Ele Z iPWi M 21 Variance of X 00 00 2 72 EWi 02 EWE M 2 314950 iPz gt 2391 2391 Measures the dispersion of the random variable about the mean Standard deviation is 039 02 Coefficient of variation is i E w Fulp High Speed Networks m m 2 Spring 2009 Simulation Part 2 Estimates of Statistics 0 Suppose X1X2 are random variables Want to estimate the random variable statistics Why not use the equations on the previous slide 0 The sample mean is n Is an unbiased point estimator u as it increases 0 The sample variance is 7 X2 7220012 5271 11 n71 W Fulp 3 Spring 2009 High Speed Networks m Simulation Part 2 How Many and which Samples 0 Need to determine how close is to M is a random variable with variance VarX One experiment estimating may be better than another 0 Construct a confidence interval a first step is the variance 77 7 2 52 Z i X A t 21 VarXn 7 n 1101 7 1 Mean am Number misammes am Numbemsampesrmases B I as 05 85 m m B I D3 82 m an 5 B 9 01 mun 2000 3000 mun 5000 B 00 mun 2000 3000 mun sn h an n numbemsampes numbemsampes E w Fulp Spring 2009 High Speed Networks m Simulation Part 2 0 An important assumption for many distributions is independence Scatter diagrams and covariance can help Scatter diagram of X1X2 Xn plots sample pairs Plot XiXZ1 for i 12 n71 If samples are non negative points should be scattered randomly throughout the first quadrant distribution will actually depend on the distribution Scanev Diagram 10 Expunemrar Samples Scanev Diagram 10 Cuiielaled Samples E w Fulp Spring 2009 5 4 High Speed Networks m m ngh Speed Networks m Simulation Part 6 Covariance o Covariance of two random variables X and Y is OXY EKX MXY MYl ElXYl MXMY Is a measure of linear independence 0 What is the value of OXY ifX and Y are independent ElXY Z Zaciyj probaci and yj occur 2391 1 Z me 2 my Ele ElYl e1 31 therefore OXY ElXYl MXMY MXMY MXMY 0 W Fulp Spring 2009 Simulation Part 7 m o If OXY gt 0 then X and Y are positively correlated As a result if xi gt MX then yi gt My move in same direction 0 If OXY lt 0 then X and Y are negatively correlated o The value of OXY is not dimensionless if Xi and are seconds then OXY is second52 use correlation instead OXY pXY VarleVarlY What about correlationcorrelation in a single random variable W Fulp Spring 2009 High Speed Networks m Simulation Part 2 Single Random Variable Correlation 0 Interested in the correlation of a single random variable X A r quot r A X1X2X X X X v v v Measure correlation between neighbors distance is the lag 0 Sample correlation at lagj is p i J 5201 where Oj is 71j 21 Xi X00 Xiw39 XW A Z n i J E w Fulp High Speed Networks m Simulation Part 2 0 Problem with m is that is it is biased has large variance unless n is very large Rammvme empeme We mewquot Rammvme epmmnswp emeem 1 n5 n5 n5 us I IUD ODD BUD EDD 1 EIEI lEI IUD ODD BBB BBB l lag ea E w Fulp Spring 2009 8 High Speed Networks m Simulation Part 2 Distribution Fit 0 Once summary statistics collected fit distribution Use histogram to determine appropriate distribution mth o Quartile summaries can help determine if correct fit E w Fulp High Speed Networks m Simulation Spring 2009 Part 2 Random Numbers 0 Systems that are simulated have at least one random component Arrivals service times etc Simulator needs a method for generating random numbers 0 Many different methods for generating random numbers Must be compatible with computers thus arithmetical based Give a non computer based method 0 A common objection is that these methods are not truly random Random in the sense of being unpredictable As a result generators are often called pseudorana39om E w Fulp Spring 2009 High Speed Networks m simulation Part 2 12 quotAnyone who considers arithmetical methods of producing random digits is or course in a state of sin there is no such thing as a random number von Neumann von Neumann was not that pessimistic about the idea quotIf the digits work well on one problem they seem usually to be successful with others of the same type von Neumann 0 We will consider generating random values between 01 We will generate other distributions later m w Pulp Spring 2009 ngh Speed Networks m simulation Part 2 13 Properties of Good Random Generators Numbers should appear uniformly distributed between 0 1 Generator should be fast and efficient 9 Should be able to reproduce the random stream of numbers 0 A stream is a sequence of random numbers 100000 or more What Why would you want to reproduce the sequence gt The generator should be able to produce separate streams 0 Each substream starts at a different point in the stream E w Pulp Spring 2009 m High Speed Networks m Simulation Pan 2 14 Linear Congruential Generators 0 Linear Congruential Generators LCG are the most common A sequence of integers Z1 Z2 given by Z aZi1 cmod m where m is the modulus a is a multiplier c is an increment and Z0 is a non negative seed starting value These values must satisfy 0ltm altm cltm Z0ltm There are two obvious objections to an LCG o The Z values are not really random Is this applicable only to this random number generator m W ngh Speed Networks m Fulp Spring 2009 Simulation Part 15 You can predict the next value Cai 7 1 Zi 1120 ail mod m If you select the correct values for the parameters the LCG will appear to be llD U01 So is the ability to predict a problem 0 The second objection is that the random numbers can only have the values 0 2 W EV The looping behavior of LCG is inevitable Length of the loop is called the period W Fulp Spring 2009 High Speed Networks m Simulation ParLQ 16 Optimizing LCG 0 We know that Z depends on the previous integer Z111 In addition we know that 0 S ZZ S m 71 Therefore the period is at most m lfthe period is m then the LCG has a full period Why would the LCG not have a full period 0 Following theorem will determine if the LCG has a full period 1 The only positive integer that exactly divides m and c is 1 2 If 1 is a prime number that divides m then 1 divides a 7 1 3 If 4 divides m then 4 divides a 71 E w Fulp Spring 2009 ngh Speed Networks m Simulation Part 2 17 LCG Examples o LCG with parameters equal toa3 03m8 16521652165216 5 216 5 2 o LCG with parameters equal toa5 03m8 10325476103254 7 610 3 2 E w Fulp Spring 2009 High Speed Networks m m Simulation Pan 2 18 Testing Random Number Generators o All the random number generators are completely deterministic We really only want them to appear llD U01 0 There are several tests we can perform to measure the goodness Empirical tests measure how close the sequence is to U01 What is an example empirical test Theoretical tests are not tests the statistical sense use parameters of the generator to assess it w Fulp Spring 2009 High Speed Networks m Simulation Part 19 Lattice Test for Random Number Generators 0 Let U1 U2 WU be the random number sequence Plot the pairs Ui Ui1 and notice the planes formed mm a m 1 Wm m 1 teem 542 m 7 Which LOG is better w Fulp m Spring 2009 m High Speed Networks m Simulation Pan 2 20 Random Variates 0 We know how to generate numbers that appear to be U0 1 We are interested in other distributions U0 1 is the basic ingredient for any other distribution Random value from another distribution is a random variate Let be a cumulative probability distribution function PrX S given at the function returns a probability What about the opposite m w Fulp Spring 2009 High Speed Networks m Simulation Part 21 o Inverse transform yields a random variate that is continuous 1 Generate a random number u U01 2 Random variate x F 1U 0 Consider the exponential distribution 1 7 e77 get u and solve for at FAW i ln iu o This method can be used for any continuous distribution What about discrete distributions Fulp Spring 2009 Simulation Pan 2 22 High Speed Networks m C Random Variates o Exponential distribution double exponentialRVltdouble rate return 10ratelogdoublerandRANDMAX 0 Uniform distribution int intUniformRVltint max int min return intmindouble maxminrandRANDMAX05gt Spring 2009 E w Fulp Simulation Part 2 23 High Speed Networks m More Complex Events 0 We have only discussed events that follow known distributions 0 What distribution would we use for Voice traffic web access email file transfer video We Emma Adea 039 ms Wis empreseamm mm hits 4 o More complex models are available Markov models but that is another class contact your friendly department head and request quotPerformance Modes and Simulation by Fulp its fun Spring 2009 E w Fulp High Speed Networks m Simulation Part 2 General Rules 0 Do not use a seed of zero Some generators use multiplication multiplicative LCG which causes problems 0 Avoid even values for seed values Some random number generators will have a shorter period given an even seed value Do not subdivide one stream Do not use a single stream for all random values in a simulation Results in random events being correlated What is an emample Would this occur using m w Fulp High Speed Networks m 24 Spring 2009 Simulation Part 2 25 0 Do not use overlapping streams Each stream needs a unique seed value Make certain the resulting streams do not overlap o Reuse seeds in successive replications If a simulation is replicated several times within one run then the seed does not need to be reinitialized 0 Do not use random seeds Why not E w Fulp Spring 2009 m High Speed Networks m E w Fulp ngh Speed Networks m Simulation Pan 2 Transient and Steady State 0 Most simulations are only concerned in steady state performance Performance once the system reaches a stable state average number of packets e m m 4 m m 500 mun UN 1500 2000 2 00 e 0 Want to remove the transient state What is the transient state How do you identify Spring 2009 Simulation Part 2 Transient Removal Methods Long runs use very long simulations 0 Long enough to ensure initial conditions do not effect result What is long enough N Proper initialization start at steady state o Initialize system With packets in the queue 00 Truncation eliminate the transient data 0 Assume more variability during transient than steady state 0 Measure variability in terms of a range min and max which should stabilize once in steady state W Fulp Spring 2009 High Speed Networks m Simulation Part 2 2s 0 Given a sample of n observations 1152 Ignore the first 1 items and calculate the min and maX of the remaining n 7 1 items Repeat the process with l 172711 71 until the l l 1 5h observation is neither the minimum or maXimum Does this always work Perform truncation on the data 1234567891011109101110910 value E w Fulp Spring 2009 ngh Speed Networks m Simulation Part 2 29 4 Initial data deletion eliminate the transient data 0 We know that the steady state average will not change However randomness will cause a slight variation 0 Run several simulations just change the seed value 0 Create an overall mean of the observed data 0 Perform truncation on the mean angry data U I Batch means use very long simulation 0 Divide results into equal parts based on time 0 Determine the mean and variance of each batch 0 Repeat with different size batches same simulation data Assume transient period is T and batch size is n lt T When n gt T then the first batch mean will be different from remaining m w Fulp Spring 2009 High Speed Networks m Simulation Part 2 30 Stopping Simulations 0 Important to determine the appropriate simulation length 0 Simple method for determining when to stop is based on variance Simulation should be run until the confidence interval for the mean response narrows to a desired Width 0 The variance of n independent observations is var ac varj A n is only valid is the observations are independent 0 Can calculate the variance of correlated observations using Independent replications Batch means Regeneration E w Fulp Spring 2009 Network Performance csc 790 WAKE FOREST Department of Computer Science Spring 2009 High Speed Networks m Network Performance 1 Performance Evaluation 0 Network designers are always interested in performance Evaluate different network designsconfigurations Trouble shoot or enhance a network system Determine the performance bounds of the system What are we estimatingmodeling What properties 0 We can develop mathematical models or use simulation Specifically queueing theory or discrete event simulation Why use one over the other 0 We will consider each network technology separately Circuit switched packet switched and virtual circuit E w Fulp Spring 2009 m High Speed Networks m m High Speed Networks m Network Performance Simple Teletraffic Design 0 Consider a telephone network consisting of n userscustomers Optimize the number of paths handsets and switches o A simple design would consist of the following Assume each user has a dedicated line to every other user 7101271 paths circuits and 1101 7 1 handsets 41 4 user 1 user 2 Requires eweJ user 3 This is not a scalable solution What are the advantages W Fulp 2 Spring 2009 Network Performance o A mesh network would add a 1 to n 7 1 switch to each handset user 1 user 2 i user 3 7101271 paths Requires n handsets n switches and If n users are communicating there are All of the handsets switches and i of the paths are in use simultaneous calls For example if n 120 then the maximum path utilization is less than 1 while handset and switch utilization are 100 What are the maximum path and handset uttltzattons for the rst design W Fulp 3 Spring 2009 Network Performance 4 High Speed Networks m 0 Alternatively a star network uses two it to 1 switches user 14quot Requires n handsets 2 switches and n 1 paths However only 1 call can occur simultaneously What are the mazrimum path handset and switch utilizations Spring 2009 m w Fulp Network Performance 5 High Speed Networks m Network Performance 0 Suppose 120 users start on average two 3 minute calls per day Total traffic volume is 120 gtlt 3 720 call minutes per day 0 The mesh and star can handle this amount of traffic Mesh network can handle 60 calls simultaneously Star network can only handle one call at a time o Mesh has maximum capability high number of paths and switches 0 Star has minimum capability minimum cost So which design is better E w Fulp Spring 2009 High Speed Networks m Network Performance 6 Another Network Design 0 Can increase the capacity of the star network Interconnect m switching units two n 7 1 switches If m switching units then performance is same as mesh Requires 37 paths Is this design any better than the mesh network m w Fulp Spring 2009 ngh Speed Networks m Network Performance 7 Traffic Intensity 0 Traffic volume is the total holding time for calls Calculated by multiplying number of calls by mean holding time Prefer to measure the average workload traffic intensity 0 Traffic intensity can be measured in two ways Workload applied to the network offered traffic Work done by the network carried traffic 0 The offered traffic intensity is e gtlt h T Where 0 is the number of call attempts during time T and h is the mean holding time call duration A E w Fulp Spring 2009 High Speed Networks m Network Performance 8 m High Speed Networks m m o The rate of call attempts call arrival rate 07 T Therefore the offered traffic intensity also be expressed as A a gtlt h o For a specific patterns of calls there may be insufficient paths to satisfy all customers For example the star network can accept only one call If a call is made and no path is available the user is blocked o If during T 06 calls are carried and 0 calls are lost the total number of attempts is c Ce 0 W Fulp Spring 2009 Network Performance 9 0 We then have OL 06clgtlth A T 0 Where 0 is the carried traffic and L is the lost traffic 06 gtlt h c gtlt h T T Carried traffic intensity 0 is the average number of paths 0 simultaneously used Blocked calls do not last so what is lost tm c intensity 0 Traffic intensity is unitless it is given the honorary dimension of Erlangs in memory or Anders K Erlang founder of traffic theory 0 A formula that relates A and L to n would be really useful W Fulp Spring 2009 High Speed Networks m Network Performance 10 Variation of Traffic Intensity 0 Traffic intensity of x Erlangs can not always carried by x circuits Occurrence of a pattern of calls is a matter of chance Traffic intensity measures the average not the variation 0 The graph below shows a typical call distribution Poisson D Offered Tram lntenslty 2 5 E probability Describes time varying nature of traffic for a constant intensity E w Fulp Spring 2009 High Speed Networks m Network Performance 11 o Is it sensible to use the time average over a day Assume 240 calls are made during the day each lasts 3 minutes 200 of the 240 are made during 10 and 11 am Therefore the intensity for this hour is 2063 10 E What is the day average intensity As a result we should use the larger of the two values Is this really good enough E w Fulp Spring 2009 High Speed Networks m Network Performance 12 Erlang39s Lost Call Formula o In 1917 Erlang published the teletraffic dimensioning formula 0 Don 39t worry Brian we 39 derive the formula later A71 A71 n n 1 2 n n i B is the blocking prob or the proportion of traffic lost B Offered Traffic intensity 2 5 E number of Grain E w Filip High Speed Networks m Spring 2009 Network Performance 13 0 An important assumption is the pattern of arrivals Poisson Calls may occur individually or collectively at random Distribution gives the probability that a certain number of calls arrive during a particular time interval 0 Graph gives the blocking prob given certain number of circuits For example B 001 when n 7 and A 25 E Can use to dimension the network Would like to determine the optimal number of circuits n required for a certain blocking probability B how can this done E w Filip Spring 2009 High Speed Networks m Network Performance 14 Traffic Tables 0 The problem with Erlang39s B equation is it gives the call blocking probability B given a certain n number of trunks The dimensioning question is the opposite use traffic tabe E w Fulp Sprwg 2009 High Speed Networks m Network Performance 15 Load Efficiency of Creme 1 e in 4 circuits 7 circuits 10 circuits mockmg probability 1D offered affr E 0 As the offered load on a circuit increases B increases 0 More circuits can carry more data while maintaining a constant B More circuits provide greater efficiency We have used Erldng B formula to model blocking given a set of circuits What else can it model Does it apply to a circuit switched network E w Fulp Sprwg 2009 High Speed Networks m Network Performance Delay Models in Data Networks 0 One of the most important performance measures is delay Average delay to send a packet from sender to receiver Queueing theory can be used model average delay Can be used evaluate designs and guide network algorithms What type of algorithms Queueing theory is the primary methodological framework Often requires simplifying assumptions arrivals and processing Sometimes it is impossible to obtain accurate predictions We will focus primarily on average packet delay with a network The models are also applicable to other systems processors multiplexers bank offices highways airports etc E w Fulp High Speed Networks m Network Performance Spring 2009 17 N 00 gt Link Delay There are four principle components to link delay 1 Processing delay time the packet is received at the head of the line to the time it is assigned an outgoing link 0 Independent of traffic load dependent on Queueing delay time the packet is in the queue buffer awaiting processingtransmission o Dependent on traffic load Transmission delay time to send each bit of the packet 0 Independent of traffic load dependent on Propagation delay time between when the last bit is transmitted to the time the last bit is received 0 Independent of traffic load dependent on medium E w Fulp Sp ring 2009 16 High Speed Networks m Network Performance 18 A Simple Model buffer Server arrivals gt Packets arrive at the system according to arrival pattern Packets can be from one or multiple sources multiplexer If the buffer is finite and full the packet is dropped Packets are serviced in a FIFO order We are interested in a relationship between the following N05 the number of packets in the system at time t 0405 the number of arrivals in interval 0 to t Ti the time spent in the system by packet i E w Fulp High Speed Networks m Spring 2009 Network Performance 19 Little39s Theorem 0 An intuitive notion of the typical number of packets in the system the time average of NW up to time t o Nt will change over time but it will approach a steady state N flim Nt 5 average number of packets 500 2000 2500 1000 1500 t e E w Fulp Spring 2009 High Speed Networks m Network Performance 20 0 Similarly we can make the same claim about the arrivals o The steady state arrival rate is CW 15 the time average arrival rate up to time t A tlim At average arrival rate m a m a e m m m e m N 2000 2 500 1000 1500 00 Ume E w Fulp High Speed Networks m m Spring 2009 Network Performance 21 o The time average of the packet delay up to time t is 1 t 2 T CW the average time spent in the system per packet up to time 15 Te 0 The steady state time average packet delay is T hm Tt taco 0 These quantities N A and T are related by a simple formula also known as Little39s Theorem lt expresses the natural idea that crowded systems large N are associated with long delays large T Valid for different types of queueing systems W Fulp Spring 2009 High Speed Networks m Network Performance 22 Graphical Proof o Little39s Theorem is really an accounting identity 4 w N 4 T2 packet 2 T1 packet 1 number of arrlvals number of deparlures Ilme 0 Suppose the system is initially empty N0 0 0 Let 0405 be the number of arrivals and Mt be the number of departures at time t The number in the system at time t is NOE 0405 7 Mt E w Fulp Sprmg 2009 my Speed Networks m Network Performance 23 o The area between the graphs of 0405 and t is t MT 1 0 0 Let t be any time at which the system is empty Nt 0 then the same area is equal to 0405 2 Te 2 21 0 Setting equation 1 equal to equation 2 and dividing byt at at 1 t 1 0415 Ti N 7 T2 7A 25 0 T t t 0405 o This equals Nt tTt E w Fulp Sprmg2009 High Speed Networks m Network Performance 24 Applications o The significance of Little39s Theorem is its generality Holds for almost any queueing system that reaches steady state The system need not consist of a single queue The owner of a shop observes that on average 18 customers per hour arrive and there are typically 8 customers in the shop What is the average length of time each customer spends in the shop Consider a sliding window flow control method Let W denote the size of the window A be the arrival rate or packets and T be the average packet delay We know the the number of packets in flight is almost always W Little s Theorem states W 2 AT What does this imply E w Fulp Sprmg 2009 Network of Queues csc 790 WAKE FOREST Department of Computer Science Spring 2009 High Speed Networks m Network of Queues 1 MGl o MMl provides a good approximation to many systems Hoewever exponential service is problematic for many systems What is an emample o MGl applies to systems with general service time distributions Any service distribution is possible Arrivals are exponentially distributed with average rate A 0 Assume Xi is the service time of the ith arrival Then X1X2 are identically distributed mutually independent E w Fulp Spring 2009 Network onueues 2 High Speed Networks m Let i 1 X 7 average service time M W EX2 second moment of the service time What is the second moment 0 The Polaczek Khinchin P K equation states for a MGl system 7 A 21 7 p where W is the expected waiting time in the queue therefore i A T X 7 217 p where T is the average total time in the system E w Fuip Spring 2009 High Speed Networks m Network onueues 3 0 Applying Little39s Theorem to W and T A2 NQ 7 21 7 p which is the average number in the queue and total average is V N p 7 21 7 p o 50 What SpringQOOQ E w Fuip High Speed Networks m Network onueues 4 Return of MMl o P K equation can be applied to any service distribution right 0 Consider service times that are exponentially distributed Average rate is M therefore Y i The second moment is X2 T22 Substitute these items into the P K formulas 1 A T i 7 217 p L M1 7 p M1 7 p 0 Therefore MGl truly represents a general service time T7 7 1 77 M E w Fulp Spring 2009 High Speed Networks m Network onueues 5 Hello MDl 0 We can use P K equations to determine average time for MDl Average rate is M therefore Y i The second moment is X2 712 0 Substitute these items into the P K formulas 1 A72 T 7 M 217 p 2M1 7 p o The average number N can be obtained using Little39s theorem E w Fulp Spring 2009 HIgh Speed Networks m Network onueues 6 Queueing Systems 0 We have discussed single queueing systems in isolation Assume an arrival rate of A and service rate of p assume the service time depends on the packet length Can determine the number in the system and average delay However a network is a set of interconnected queues We never stated anything about the departure process Consider a set of tandem queues I buffer I I buffer 7 I I I 39 I sener sener system 1 system 2 E w Fqu Sprmg 2009 HIgh Speed Networks m Network onueues 7 The output of the first system is the input for the second What is the arrival process for the second system 0 The second system cannot be modeled as a MMl quotnterarriva times at the second system are strongly correlated With the packet lengths Why is this the case Referred to as the tandem queue probem We are still interested in evaluating a network of queues Average end to end delay Need to make more assumptions and approximation caims E W Fqu Sprmg 2009 m m High Speed Networks N High Speed Networks m Network onueues Kleinro ck Independence 0 Networks typically consist of traffic streams merging together 0 Kleinrock suggested merging streams restores independence Called the Kleinrock independence approximation 0 The approximation is acceptable under certain conditions Poisson stream arrivals at the entry points Packet lengths are nearly exponentially distributed Densely connected network and moderate to heavy loads w Fulp Spring 2009 Network of Queues Burke39s Theorem 0 Consider an MMl MMm or MMoo with arrival rate A 0 Assume the system starts in steady state then the following is true 1 The departure process is Poisson with rate A 2 At each time t the number of customers in the system is independent of the sequence of departure times prior to t What Are tandem queues no longer an issue 0 The proof is based on reversibility of the system quotThe forward and reversed systems are statistically indistinguishable in stead state Would this apply to MDI queues Implications 0 Now we can approximate a network of queues W Fulp Spring 2009 9 8 High Speed Networks m Network onueues Network of Queues There are two general classes of queueing networks 0 Open network Customers enter and exit the system Can you give an ezmmple of both types E w Fulp Spring 2009 High Speed Networks m Network onueues 11 Jackson Networks 0 Have already discussed the issues with modeling networks Packet length correlation to arrivals after first queue 0 Eliminate correlation and randomly divide traffic among queues Can assume system queues are MMl Network ergodicity condition xi lt Mi Vi This is considered a Jackson network What are we speci cally assuming Any problems 0 Consider open network with N queues 1 source and 1 destination 1 7i 1 EV yj E w Fulp Spring 2009 High Speed Networks m Network onueues 12 0 Let qmv represent the probability that a packet customer completing service at node i is routed to node j Given these routing probabilities the following must be true N qedZqj1 13 N 31 where d represents the destination note q39s can equal zero What does this equation mean Zero probability 0 Flow conservation provides another necessary condition N We gsiquika 1lt i S N k1 What Why is this equation legal E w Fulp Spring 2009 High Speed Networks m Network onueues 13 o The objective as always is determining pk1 k2 kN Pltk1k2 m 1607 P1k1 192062 39 39PNkN Using 1 can determine average delay How But we won 39t derive the equations sorry Brian 0 Consider a M hop virtual circuit in a network of MMl queues End to end delay through the cascading M queues is M 1 M i TMiiMi 9i E w Fulp Spring 2009 High Speed Networks m Network onueues o The average delay over the entire network is 1N 1N Ai TiagAZTiigg where N is the total number of nodes and y is the net arrival rate into the network 0 Gordon and Newell considered closed queueing networks No customer can enter or leave Same assumptions as open queueing networks E w Fulp Spring 2009 High Speed Networks m Network onueues 15 Example 0 Consider the following network where link speed is 3 packetssec How many MMZ queues are present Does the network follow the probability requirement Does the network follow the flow conservation requirement E w Fulp Spring 2009 ngh Speed Networks m Network onueues What is the average lz39nh delay from 1 t0 5 using node 2 What is the average lz39nh delay from 1 t0 4 using node 5 What is the average network delay E w Pulp Spring 2009 ngh Speed Networks m Network onueues 17 Review 0 Traffic Management Blocking probability and offered load Erlang B equation 0 Queueing system Consists of customers arriving at a servers lnput process service mechanism queue discipline Kendall notation expresses the characteristics Little39s Theorem Average number of customers in a queueing system is equal to the arrival rate times the average service time NT E w Pulp Spring 2009 m High Speed Networks m Network onueues Specific queueing systems MMlKMM1 MMcc MG1and MDl Determined average delay and number Network of queues Tandem queue problem Kleinrock independence approximation and Burke39s theorem Open and closed networks Jackson networks W Fuip Spring 2009 Wavelength Division M ultiplexing CSC 790 FORES EFLSI I Department of Computer Science Spring 2009 High Speed Networks Wavelength Division Multiplexing 1 Packet over SONET 0 Sending IP packets using SONET Should be called IP over PPPHDLC over SONETSDH 0 Defined in RFC 1619 and RC 1661 PPP Optical Fiber E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 2 Point to Point Protocol 0 Internet point to point protocol has different uses Router to router traffic and home user to ISP traffic 0 Provides three features 1 Framing method delineates start and end of frame 2 Link control for starting link negotiating options this protocol is the Link Control Protocol LCP Bytes 1 1 1 1 or 2 Variable 2 or4 1 F1 Flag Control Flag 01111110 l 11111111 00000011 l Pr t l Pay l Ched sum l 01111110 3 Negotiating network layer options which is independent of the network layer called the Network Control Protocol NCP 0 Used in SONET to negotiate link and transport IP packets m w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 3 SO N ET Aggregation 39 M ullmlexed signal H SONETlevmmal m STE Tunplical 11 1 730 Unchannellzed u 1n my tummy 28 30 ATM switchXI H RuulevLWEVS H switch 6 ATM cells 1P dalauvams Pawn we SONET o SONET can be used to transmit several types of data Telephony ATM and IP 0 However there are some disadvantages Multiplexing hierarchy is structured if more capacity is needed then must move to neXt multiple STS 192 10 Gbps next step is STS 768 4O Gbps m w Fulp Spring 2009 ngh Speed Networks Wavelength Division Multiplexing 4 Wavelength Division M ultiplexing o Multiplex carrier signals on single optical fiber Different wavelengths colors carry different signals Higher capacity and bidirectional communications What is the di erence between WDM TDM and FDJM MM m Mix 01 3313 cnennem y 0042 00m 004 l Single by TDM 00452 ingleiibev WDM 003 i y une wavelength SONET multiple 0042 ATM WaElenglns 0048 Channel n 1 GE Multiplexer at the transmitter to join the signals together while demultipleXer at the receiver splits signals apart MUX DEMUX MUXDEMUX MUXDEMUX awe 20 02 Need a method to joinseparate lightwaves E w Fulp Spnng 2009 ngh Speed Networks Wavelength Division Multiplexing 5 Windows and Wavelength Patterns rm wndnw Second wndnw mlal enenuemn ommei lass dBkm l mm sm evmg Raweign l l l l l l l l l l l l 07 00 D91D111213161515171819 2 Wavelenglh micvameievs the impact of quotattenuation and dispersion depends on the optical wavelength however wavelength bands exist Where these effects are weakest making these bands or Windows most favorable for transmissionquot E w Fulp Spnng 2009 High Speed Networks m High Speed Networks m Wavelength Division Multiplexing 6 Course or Dense 0 Optical networks can be divided based on frequency separation Minimum frequency separation between two signals multiplexed in known as the channel spacing mu xuvs um my this diagram has nothing to do With this slide other than being awesome 0 There are two categories of networks ConventionalCoarse WDM Dense WDM W Fulp Spring 2009 Wavelength Division Multiplexing 7 Coarse WDM 0 Provides 18 channels in the 3rd transmission window C band Uses the entire frequency band between second and third transmission window 13101550 nm quotCWDlll channels are typically spaced 20 nanometers nm apart The more relaxed manufacturing tolerance for CWDM components makes CWDM less costly than DWDM systems But CWDM systems also support a limited number of channels the ITU defines 18 lambdas compared to 32 or more 25 and 10 Gbps lambdas typically supported by DWDM technology quot o For example Ethernet LX 4 10 Gbps standard uses four wavelengths near 1310 nm each carrying a 3125 Gbps to carry 10 Gbps total Cable television networks different wavelengths are used for the downstream and upstream signals W Fulp Spring 2009 I High Speed Networks Wavelength Division Multiplexing E W llllp Originally refers to optical Using the basic concepts of DWDM an All Optical Use Erbium Doped Fiber Amplifiers EDF AS allow a single fiber optical link increase the bit rate by replacing only end equipment lrahsport O F Gigabit Ethernet channels Dense WD M signals multiplexed Within 1550 hm Which I owe rs cost systems it possible to Form layer AIM SONIEI IP on di39FFererIt is also possible High Speed Networks s pri ng 2009 Wavelength Division Multiplexing 9 E W liilp Use di39FFractiorI and Oquot optica Mux and Demux I echhiques 0 Simplest demultiplexihg uses a prism nip 1 A1MAn AE ens Lena Beam 0quot polychromatic light impingegca39pom a prism Each wavelength re Fracts di39FFerehtly the rainbow e FFect Each wavelength Bea rrl O F is separated From the next by an angle x1 Flbers interference Diffracted teae polychromatic light impinges on a grattihg s pri ng 2009 Eae wavelength is diFFraeted at diFFererlt angle therefore to dl FFel39er lt r r s llse waveguide gratlngs e An array of eumedeehar lr lel Waveguldes Optical AddDrop Multiplexers Betweer l device multiple Wavelength eslst Often deslrable te addere Wavelength at thls pelr lt Optcal AddDrop Multlpleser Rather than Orr lbth g er C IgtlI ear remove serr separatir l all I ssi r l OADM performs tI l a the en Wavelength Division Multiplexing 12 High Speed Networks Transparent Optical Switching Nodes 0 Optical Cross Connects OXC make an all optical core possible mammm WOW that39s one snazzy diagram Use optical switching fabric wavelength multiplexers and demultipleXers and transparent wavelength converters o The design is transparent the optical signal does not need to be transformed to electricity Implying it can support any protocol and any data rate Spring 2009 E w Fulp Wavelength Division Multiplexing 13 High Speed Networks Optical Network Architecture 0 Consider a multi wavelength network of OXCs and OADMs Lightpath is established by allocating the same wavelength throughout the route of the transmitted data Data remains entirely optical from end to end Nelwork Al70plczl Core Edge lPMPLS 7 AIM Frame Relay sunsown I HDLCIPPP Nelwork dge s lngreslegress Clrcuils 0 There is also a virtual topology set of lighpaths Spring 2009 E w Fulp High Speed Networks Wavelength Division Multiplexing 14 Lightpaths and Allocation 0 Consider n nodes each with m n 7 1 transceivers lfthere are enough wavelengths on all fiber links then every node pair could be connected by an all optical lightpath and there is no networking problemo 0 However transceivers are expensive so in lt n 7 1 Given a set of lightpaths that need to be established and given a constraint on the number of wavelengths determine the routes over which these lightpaths and also determine the wavelengths that should be assigned Recall a lightpath operates on the same wavelength across all fiber links that it traverses in which case the lightpath is said to satisfy the wavelength continuity constraint E w Fulp High Speed Networks Spring 2009 Wavelength Division Multiplexing 15 Also All lightpaths using the same link must be allocated distinct wavelengths called the distinct wavelength constraint This is Routing and Wavelength Assignment RWA problem 0 The continuity constraint can be relaxed if conversion allowed Optical Cross Connects OXC convert input wavelength to another wavelength on output E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 16 RWA Connection requests can be one of three types Static incremental or dynamic Create lightpaths in a global fashion while minimizing resources RWA problem is called Static Lightpath Establishment SLE o Incremental connections requests occur sequentially Lightpath established per request which remains indefinitely Objective is to minimize blocking or maximize the number of connections established at any time 0 Dynamic connections requests also occur sequentially Similar to incremental but connections are released This is Dynamic Lightpath Establishment DLE Static connections the entire set of connections known a priori E w Fulp High Speed Networks Wavelength Division Multiplexing Spring 2009 17 It39s Easy 0 SLE problem can be considered as a miXed integer linear program Which is unfortunately NP complete o SLE can be partitioned into two sub problems Routing and wavelength assignment Each subproblem can be addressed separately 0 DLE is considered equally difficult to solve Why not consider each lightpath as a separate link and use a shortest path algorithm Is there a real heed to divide the problem E w Fulp Spring 2009 ngl Speed Networks Wavelength DlVlSlOn Multlplexlng RWA Routing SubProblem Fixed routing the easiest solution Always use pre determined route for a source destination pair For example use Dijkstra39s or Bellman Form algorithm May result in higher blocking and not fault tolerant o Fixed alternative routing consider multiple routes Maintain ordered list of alternatives for source destinations For example shortest path primary second third etc An alternative route cannot share any links with the primary E w Fulp ngl Speed Networks Sprlng 2009 Wavelength Dlvlslon Multlplexlng 0 Dynamic routing considers the current network state Possible to use shortest cost path routing where unused link cost is 1 full link cost is 00 Wavelength conversion has 0 cost if not possible 0 00 If multiple paths with same minimum cost then random select E w Fulp Sprlng 2009 19 m High Speed Networks Wavelength Division Multiplexing 20 RWA Assignment SubProblem 0 Assume lightpaths arrive sequentially incremental or dynamic Method is needed to assign a wavelength Select wavelengths to reduce blocking probability 0 For example consider the following network and connections A BB OandA O WMA2 WMA2 0 Several heuristics eXist typically implemented on line Random first fit least used and most used E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 21 Random Assignment 0 Search space of wavelengths to determine possible set Set of wavelengths available on the required route 0 Randomly choose from the available set of wavelengths WA1A2 wan E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 22 FirstFit Assignment 0 Wavelengths are numbered Lowest numbered wavelength that can be used is selected 0 The idea is to concentrate the usage toward the lower wavelengths High numbered wavelengths contain longer continuous paths Better than random and actually used 0 For example consider the following requests Request A a B assign A1 Request B a O assign A1 Request A a C assign A2 E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 23 0 Really better than random If B a O assigned A2 possible with random assignment Then A a 0 blocked E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 24 LeastUsed Assignment 0 Selects the wavelength least used in the network Attempts to balance load among all wavelengths o For example consider the following requests WMA2 WMA2 Request A a B assign A1 Request B a O assign A2 Request A a 0 blocked 0 Typically breaks up long paths early only short connections served Performance worse than random while adding overhead E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 25 MostUsed Assignment 0 Opposite of LU attempts to select most used wavelengths Concentrates into fewer wavelengths but global View Performs significantly better than LU o For example consider the following requests wan wan Request A a B assign A1 Request B a O assign A1 Request A a O assign A2 E w Fulp Spring 2009 m High Speed Networks Wavelength Division Multiplexing 26 Traffic Engineering and Provisioning 0 Traditionally provisioning has been done manually Time consuming process only acceptable for static connections Growing need for a control plane for optical networks Routing resource discovery and connection management One solution uses Multi Protocol Label Switching MPLS Provides virtual links or tunnels through the network to connect nodes that lie at the edge of the network Packets injected into the ingress of an established tunnel normal IP routing procedures are suspended instead the packets are label switched so that they automatically follow the tunnel to its egress E w Fulp Spring 2009 High Speed Networks Wavelength Division Multiplexing 27 MPLS overlays a packet switched IP network to facilitate traffic engineering and allow resources to be reserved and routes predetermined Want more MPLS take CSC 790 next fall 0 Generalized Multi Protocol Label Switching GMPLS can be used A label can be generalized to anything related to a flow Wavelengths can have a label from source to destination w Fulp Spring 2009 HIgh Speed Networks m m TCP and UDP Review CSC 790 WAKE FOREST Department of Computer Science Fall 2006 TCP and UDP RevIew 1 Example TCPIP Protocols I 39 0 AP1 AP2 AP3 F ng39faa 39i gse 39 PoIl number In TCPUDP heaier Transpon layer Proloool held In dalagram header IP NeIwork layer Wpe held In Irame header Nemorkdependenl prolocols LInk physIcal layers DesIInaIIon address In Irame header H Frame IP TCPUDP RTPRTCPE APDU Frame header header header header Eheader Apupa lmda39a IraIIer W Fqu Rm 2006 ngh Speed Networks m TCP and UDP Revlew TCPI P EndtoEnd Communication Sourne host PUDP lransmission non1rol prolonoluser dalagram prolonol LP Iirk prollonol TC P lnlemet p dDOd Anness network X l Applina on PDUs 39 TOPUDP PDUs Router lnlemet global inlemelwork oginal nommuninan39ons palh of prolonol data urils PDUs PL physical layer Anness network gagway r Applina on Des nan39on host TCPUDP l Fall 2006 E W Fulp ngl Speed Networks m TCP and UDP Revlew UDP Header UDPheader 1 16 17 32 llllll Source port I Desn39nah39on port UDP lenglh Checksum header Data Payload UDP pseudo header for ohecksum 1 8 9 16 17 32 UDP pseudo 17 header UDPheader UDP Dam dalagram Added if number of bytes in dala eld is odd E W Fulp Fall 2006 3 2 H1gh Speed Networks m TCP and UDP Rewew 4 U D P Socket Interface Sachmm H351 Hm Hm 1 mm 1 mew 1 mew we r g 1 1 We 391 1 39 ENE 3 1m uop segmem 1mm 39 1 V p 7 V 1 7 17 7 7 7 7 1 Wheadq UDPheaner unwame mmems El UDPda gamsmmngbbeDWDMDM SBR Prlnimsamlm39m H081 Os Hm UserAP uop 1p uop MAP ammmmm mew um 1mmu W11 hndHAssgnam addm Senna message sem39 mew 1 new a MM sem39DU H H 1 snmqwm smmDWWU Rdaasemeumt 4 pr1muveca wnh Parameters H remrnva1uelswrenurm E w Mp F211 2006 H1gh Speed Networks m TCP and UDP Rewew 5 TCP Header Tovheaueruem Equot gt1 A 5 1011 1617 32 d 111111111111111111111111111 Souvcepon Des11na11onpon Sequence numbev TCP Acknmmedgmem numbev 11xea neaaev Hmde englh Resened Codesz Wmdwslze Checksum Uvgenl po1n1e1 Op11onswhen pvesem 1 01 move szpnwovas Pawoad Datamany M55 op on Iormax Kmd 2 Leng1h4 Max1mum segmem s1ze M88 Code hn detlnnlons Code p115 E11pos111on Name 40mm URG e Uvgenl po1r11e111e1a vahd AoKeAamWeagmem 11e1a vaHd PSH e Dehvev data on vece1p1 01 m1 se mem PST 7 Rejed a connecuon 1eques1 01 vese1 sequence numbevstothew1n111a1va1ues 3w 7 Used 10 estabhsh a connecum 11 12 1s 14 15 1e Fwwseam aoseaconnewon E w Mp F211 2006 m ngh Speed Networks m TCP and UDP Revwew TC P Socket Interface 50cm mm mp m s WMCMMP ma omm swapm wwmmdm emu enema mm an em wassmmd Dvmmu w vlumrs rsunuzhi wmvm mm mm mm Manama 39mo i 4 r W 7 7 7 We WNW me We sx mu Wm Wm mm m up You You mo 1339 m emmeemm yemmewee W mmzmml Wmmme mm o Memo mnweswkvnwd some new meAgmzwmhmr WWWIU ddn meow mam mwaOn myamwmmmmd enemy E w Mp ngh Speed Networks m Rm 2006 TCP and UDP Revwew H051 Host Chem AP TOP emm TOP enlm semev AP cLosEn ISM x 01055045quot v ooke o mnd e memo Chemserver e 3009p LISTEN sooked 5V 7 servevAP mocked oonned SendSVN Mt x onemAP modlted SYN75ENT Reoewe em a unmooksemevAP LSBQ V 7 vov 5w X AOK My Send SYNAOK socketo t SYN7RCVD ACK oonnemsuooess e ndAOK Vv v onemAP unmooked EsmaLlsHED a EsmaLlsHED Dmauanmev Oonnealon oolllslon sooked sookem mndo e mnd memo memo aooep o f aooepm conned SendSVN 7 Send 5w connedo AP mocked SYN75ENT SYN75ENT AP mocked SYN7RCVD SVN7RCVD AACK I A 1 oonnemsuooess SendAOK f h 1A5V SendACK a connedsuocess AP unmomlted X AP unmomlted EsmaLlsHED T ES39IRELISHED i 7 i i 7 7 7 7 i 7 i Data Uansvev SN mma sequenoe numbev w Mp Rm 2006 7 6 Hrgn Speed Networks m TCP and UDP Revwew 8 Example TCP Data Transfer Sender Apphcanonl W te Apphcanonl Sen der SI b Ock ed Sender mayIII send up to 2K ACK 2043va 2048 Me n SEQ 2045 Recewer Recewer sl bu er 4K lt7 Apphcatronn reads 2K E w Mp Hrgn Speed Networks m Rm 2006 TCP and UDP Revwew 9 Example TCP Data Transfer CEMAP YcPaMw rnnemaeAcKs 5m x Serum RECEIVE em Q DEBEn ms Send m e RECEIVE L av 59m raw RECEIVE saw Names A gnmhm 7 Sam M 52m m Imum Sam M E w Mp Rm 2006 E w Mp Rm 2006 estimateRTT 1 7 a X estimateRTT a gtlt sampleRTT Ume Ume round mp nme Samp e Fm Es umated Fm 00 Samp e Fm Es umated Fm so Examp e Fm Samp es and Es Lmated Fm u 0 75 Examp e Fm Samp es and Es Lmated Fm m 0125 Example RTT H gh Speed Networks TCP and UDP Revwew 11 E w Mp Rm 2006 Fa m saw m Semng Nemmngvt Cumn SNzx M55259 WES we vmssemms Haemrwmmwzmw WES samem nmewgs W9 5 saewaemenwee saewaeemnwee T m 52 rep Tme mp 1 us hwy hu ers vww 1 Li Wszzm mmmsgb x WWW a m Ell W xme m szzm m a s mm Wsztma mmmsawxmee E szzme e m 05mm wsem mm 52px me m V535 Wmst m W5 n Wmdwlc nse xemw SeqVLNLWne mmmwe we 9 W4 lx2ma szn Apeeasmzomesv mRE zumwnsmm xemw mew xezma sztma Wszmzo Wmdnw per Wszm L5yvmm52gtx2me a meme s s We am wmsv mzvl hWHQISHEIENE me We MW mm Wen gt WNW Apeeaemwm we swan mm mm WFW wszmzo WWW Apeeasmzomesv mm 0290 Mm Wmawzw xn72 szzm Weem lt Lemme we ralsmSnn sztma wsem mvmmsappx25m ws n mmammseay meme w 5 send wvmwvznam e 5m Sam739nm hm Er w R racemewmmw vanam e SN 1 sequence quotWe ngh Speed Networks TCP and UDP Revwew 10 H gh Speed Networks m TCP and UDP Rev ew 12 Example Tlmeout Examp e Fm Vames andtmeom u p 0125 Examp e Fm Vames andtmeouuu p 0125 1 1 Samp eRW 2 EsnmatedRTF Timeout a a E E S 50 5 9 9 05 04 02 0 timeout estimateRTT 4 X deviation deviation 1 75 gtlt deviation Q gtlt sampleRTT 7 estimateRT E W Fu p FaHQOO H gh Speed Networks m TCP and UDP Rewew 13 TC P Congestion Control S ow s1an ophgmph avopahee ophs1amwc My Open phase phase phase W c l l l Segmemskpy s 64 32 Sxpws1amhyshpn SST 16 a 4 g 012345 10 20 so 37 40 50 ans L wc mueass by 15egmen ovoh 32 ACKS veoewed c wc Dongs on Wmdow RTT youhmhphme Note MSS maximum Segmem S Ze ihpy e SST 32ksz w c vernams constam E w Mp Rm 2006 High Speed Networks m TCP and UDP Review 14 TCP Congestion Control with Fast Recovery On receipt of dupliaieACKs FHS set Oi 3 duphca e ACKS yeoewed We Segmentskby es 54 Second set oi duphca eACKs 39 yeoewed 39 SST32 39393939 quotW044 32 15 SST17 a 4 0 5 lt0 20 30 37 40 50 w c oongesuon W ndON RTF voundrmp urne Nore in the exampies Mss 1Kby e SST 32 Kby e Tr siow Siaquot thieshoid S RTO veivansmssion urneom Fm Mss rmximum segment size E w Fuip H gn Speed Networks m Rm 2006 TCP and UDP Review 15 TCP Congestion Control with Timeout Timeout Wc Segmentakby es FWS R70 54 Second RTO 32 i 32 39 Tnnd RTO 16 a 4 g lt0 20 3o 40 50 R S w C oongesnon Window SW siow Stan thieshoid Mss rnaxnnurn segment size Fm younddnpwne RTO retransmission urneom Noe in ne exampie MSS1 kbyte and SST 32 Kby e E w Fuip Rm 2006 Htgh Speed Networks m TCP and UDP Revtew TC P Congestion Control Timeout Wc Segmentskbytes FWS R70 54 39 Second RTO 32 t 32 Thwd RTO 15 39 a 4 g 10 20 30 40 50 S W c congestton wmdow SW stow start tmeshotd Mss maxtmum segment stze RTF Voundrmp Mme RTO vetvansmtsstm Umeout Note n the examp e M88 t kbyte and SST 32 kbyte E W Futp FaHQOO Htgh Speed Networks m TCP and UDP Revtew TCP Congestion Control TCP Oongesllon Oontrol packet transmitted Ilmeoul 70 mm Tum tmmmummmmut 6O 50 Q 40 30 20 to 1 O 2 O 3 O 4 O 5 O 6 O 7 O 8 O 9 O congmndow Ttme seconds TOP Congestton Contro WHH Fast Retransmtt packet transmttted ttmeout 70 mm 39 ttutttttuutttttutttttmummmumm t 50 50 m 40 X 30 20 m 1 1 0 2 0 3 0 4 0 5 0 5 0 7 0 quotWindw Ttme seconds E w mo Rm 2006 17 16 High Speed Networks m TCP and UDP Review 18 Fast Retransmission Sender Receiver Packet1 Packet2 Packet3 N ACK2 Packet4 ACK3 Packets ACK3 Packet6 ACK3 ACK3 Retransmit packet3 E W Fuip F2112006 High Speed Networks m TCP and UDP Review 19 TCP Vegas TCP Vegas CongestionAvoidance 70 1 u 1 u lili 11111HHHHHHiHHiHi mum murmur 11111111111 50 congwindow r r r r r r r r r r r r r r r r 05 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 Time seconds expected throughput actual region throughput between thresholds i i i i i i i i i i i i i i i i 05 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 Time seconds E W Fuip F211 2006 TCP and UDP Revlew 20 ngh Speed Networks m TCP Fairness TCP Reno Congesllon Wmdow TCP HenoThmughpul e Source 1 Full bandwldlh ullllzallon Source 3 Falrshare 12 E 15 3 0 414 u 3 a c 3 112 a g 8 E 2 10 g N c 5 3 9 2 E m 3 K 2quot 4 s 8 4 2 2 5 10 35 4 1o sou rce1 lhroughpul 15 20 25 3 number Oftransmlsslons E w Pulp ngh Speed Networks m m Fall 2006 TCP and UDP Revlew 21 Silly Window Syndrome Receivers buller IS lull Applicallon reads 1 byle lt Room lorone more byle Header Window updale segmenl senl I New byle arrives 1 By Receivers buller IS lull W Pulp Fall 2006 TCP and UDP Review 22 High Speed Networks m TCP Window Scale Option NOP option Window scale option i i 32 i 1 8i 9 i i i i i i i i i i i i i i i i i i i i i i i i i nd 1 Kind 3 Length 3 Shift count NOP r 39 g t pd e ea pinto 4 bytes The value in theshift count eld is the power of 2 multiples of the value in the window size eld The maximum oountvalue is 14 Shift count 0 no scaling maximum window 65535 bytes Shiftcount 1mutipy by 2 maximum window 1 1070 Shiftcount 14 multiply by 2 4 maximum window 1073725440 E W Fuip RM 2006 TCP and UDP Review 23 High Speed Networks m RTP Packet mp uswe Auduardorvdeo gamma mm mm 1 i Emuder Mr iErwar Dewey 1 Datum 1751mm AP i j sham Emkz Senate Rmeiwg Serum Renews mp mp mp mp i i i 1 e m W W I mp mp mp hmr mmr Em 63ng i we use up w i w were w W hmr rem magi Em we Rn Reai we Tramv Dmbmi mp hacienomal i 2 4 5 a a 10 a 17 32 RTP padltei headev Data m audio andomaeouames VVeisi0n P pad x exlensiomiag co OSRO count Nlt15 M mavkev bu Rm 2006 m w Fuip ngll Speed Networks m TCP and UDP Reyrew 24 RTP Participant Participant t Dev 09 Interfaces User 0N User interface Systemlevel 4 control messages rn w Fulp Fall 2006 ngll Speed Networks m TCP and UDP Reyrew 25 Transport Protocols for TCPIP Model Transport protocols Transport layer protocols TCP UDP Relalable stream servlce Unrellable datagrarn seNloe All applloallol l data treated as Drrect rnapprng between an applrcatron a strearn ot bytes message ul lll and a UDP datagrarn Connecther Error Flow Congestlon onented control control control l Appllcatlon layer support protocols FtTP RTCP Concerned wrtn tne transter Concerned wrtn addrtronal ot realntlme drgrtal strearns systemnlevel lssues relatrng to RTP rn w Fulp Fall 2006

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.