Specific Systems: #14Part 2: EV-DOCellularVictor S. FrostDan F. ServeyDistinguished Professor Electrical Engineering and Computer ScienceUniversity of Kansas2335 Irving Hill Dr.Lawrence, Kansas 66045Phone: (785) 864-4833 FAX:(785) 864-7789 e-mail: frost@eecs.ku.eduhttp://www.ittc.ku.edu/All material copyright 2006Victor S. Frost, All Rights Reserved#14 1Outline•Part1––––Basiccomponents3G OverviewofW-CDMA/UMTSHSPDA•Part 2–EV-DO overview (Slides provided by SoshantBali, Ph.D. EE, University of Kansas, 2007)–Case study: Mitigating scheduler-induced starvation in 3G wireless networksSlides provided by SoshantBali, Ph.D, University of Kansas, 2007#14 2EV-DO overview-Outline•••••IntroductionNetwork ArchitectureSimplified Protocol StackAir Interface Protocol LayersForward Link–MAC Layer –PHYLayer•Reverse Link–MACLayer–PHYLayer•Some Interesting Features–Radio Link Protocol–Adaptive modulation and coding–Hybrid ARQ #14 3Introduction•1xEV-DO: 1x Evolution for Data Optimized––––3G data rates: up to 2.45Mbps downlink, 153.6Kbps uplinkNatural evolution from IS-95, IS-2000Evolution: leverage existing network elementsOptimized for data transfer•IS-2000 needs 3.75MHz spectrum for 2.07 Mbps•EV-DO only 1.25MHz spectrum for 2.45 Mbps•Data service characteristics–Rates asymmetric–Latency can be tolerated•EV-DO: higher rate in forward link •EV-DO: uses link layer ARQ•EV-DO: powerful error-correcting codes (e.g., turbo codes)•EV-DO: uses time-division multiplexing#14 4–Transmissions are in burstEV-DO network architecture ~50 BTS per ANRouterRNCInternetPCFPDSNAN: Access Network1 per major area, e.g. cityAlthough Router shown above is nota part of the standard, typical implementationsof EV-DO use Juniper or Cisco routers as aggregation router. PCF = Packet Control Function#14 5Network architecture•Base Transceiver Station (BTS)•Radio Network Controller (RNC)–RF components for transmitting/receiving signals–Software/hardware for digital communications/DSP–Connected to RNC with backhaul links–Session establishment and release–Frameselection–Radio Link Protocol (RLP) processing–BTSandRNCformtheAN•Access Network (AN)•Packet Control Function (PCF)•Packet Data Service Node (PDSN)–Allows RNC functions to interface with PDSN–Interfaces with Internet–Home/Foreign agent for mobile IP–Terminates PPP connection with AT#14 6Simplified protocol stackTCP/UDPIPPPPRLPMACPHYRLPMACPHYGREIPL2/L1PPPGREIPL2/L1L1L2IPTCP/UDPIPL2L1GRE= Generic Routing Encapsulation #14 7Air interface –protocol layers ApplicationStreamSessionConnectionSecurityMACPhysicalFlow control protocolLocation update protocolRadio link protocolStream protocolAddress management protocolSession configuration protocolSession management protocolAir link management protocolConnected state protocolIdle state protocolInitialization state protocolAuthentication protocolEncryption protocolAccess channel MAC protocolControl channel MAC protocolForward traffic channel MAC protocolReverse traffic channel MAC protocolOverhead message protocolRoute update protocolPacket consolidation protocolKey exchange protocolSecurity protocolSignaling link protocolSignaling network protocolPhysical layer protocol#14 8Air interface protocol layers •Application layer : Radio link protocol•Streamlayer–Provides reliable octet stream service–Multiplex application layer streams–Four possible application streams (00 to 11)–Stream 00 is signaling application stream–Manage logical session: AT address, protocol parameters–Manages air-link connection: open, close connection, update route as AT moves between cells, etc.–Session lasts longer than connection: close connection to conserve air-link resources when not in use (idle state), but session is still open so that re-connection is quicker–Key exchange, encryption and authentication•Session layer•Connection layer•Securitylayer #14 9 MAC Layer (forward link)•Mechanisms to control access to the forward link–Open-loop rate control•AT’ssend a request Data Rate Control (DRC) message–AdaptivedataScheduler-Opportunistic scheduling–Closed-loop rate control-Hybrid ARQ#14 10MAC Layer (forward link)•Forward traffic channel MAC–TDMonthedownlink–Control rate of transmission••••Each AT measures SINRReports to AN on data rate control (DRC) channelAN sends at the requested rateAN chooses appropriate modulation/coding for SINR•Control channel MAC –––––Generates control channel MAC packetsSent on shared control channelATsidentified using AT identifier record in headerAll ATsread identifierIf packet destined to that AT then read rest of packet#14 11 Downlink Slot Structure1.666msModified From: Naga Bhushan, Chris Lott, Peter Black, Rashid Attar, Yu-CheunJou, MingxiFan, Donna Ghosh, andJean Au, “CDMA2000 1xEV-DO Revision A: A Physical Layer and MAC Layer Overview,”IEEE Communications Magazine, February 2006#14 12Physical Layer (forward link)•Following channels are also used in forward link–Pilot channel •Sync-timing/phase infromation•SNIR–MAC channels•Reverse activity channel•Reverse power control channel•DRCLockchannel (more later)•Forward traffic channel PHY layer packet can contain 1 to 4 MAC layer packets (PHY packet can be 1024, 2048, 3072, 4096 bits long)PHY pktsize (bits)1024204830724096Data rate (kbps)38.4,76.8,153.6,307.2, 614.4, 1228.8307.2,614.4,1228.8912.6,1843.21228.8,2457.6Code rate1/51/31/31/3Modulation typeQPSKQPSK8-PSK16-QAM#14 13Physical Layer (forward link)•Data (not voice) –delays ok –Turbo error correcting code can be used•Traffic control channel–Use only QPSK–Either 76.8Kbps or 38.4Kbps•Each PHY packet–Encoded: error correcting code–Scrambled: reduce peak-to-average ratio of RF waveform–Interleaved: to combat fading–Modulated: QPSK, 8-PSK or 16-QAM#14 14Physical Layer (MAC channel)•Reverse Activity (RA) channel –AN informs all ATsof activity on reverse channel –ATsdecrease data rate if load is high –RA bits are time-multiplexed in forward channel–Power control reverse channel (no power control in forward channel)–RPC bit time multiplexed in forward channel•Reverse Power Control (RPC) channel•DRCLockchannel–AN uses this channel to tell AT if AN received DRC information correctly–DRCLock“yes” or “no” for every time-slot–DRC information includes data rate (12 possible) and DRCCover(AT specifies best serving sector)#14 15Physical Layer (Example)•Consider a 1024 bit PHY packet––––Data rate = 307.2KbpsCoderate=1/5Modulation=QPSKLength of preamble = 128 chips••••Turboencoderconverts1024 bits to 5120 symbolsQPSK outputs 1 symbol for every 2 input symbolsQPSK outputs 2560 symbolsPreamble tells: data channel or control channel –There are different preamble lengths•Pilot channel: 96 chips•MAC channel: 64 chips#14 16•••••Reverse link rate from 9.6 to 153.6 KbpsPower control on reverse linkSoft handoff on reverse linkReverse link CDMA (not TDMA)Reverse traffic channel MAC determines rateMAC Layer (reverse link) •Access channel MAC manages transmission and reception of signaling messages–AT computes MaxRatebased on several parameters–AN sends RateLimitto AT–AT’sMax. transmission rate minimum of MaxRateand RateLimit–AT keeps sending access probes at increasing power levels until it gets back acknowledgement from AN#14 17Physical Layer (reverse link)•Two PHY channels–Access Channel•Pilot channel•Data channel•••••Used for first contact to the AN–Reverse Traffic Channel•To conserve battery power: BPSK in reverse link (QPSK, 16QAM require high power)•Similar to forward, reverse link–slot size 1.67ms –2048 chips per slot (1.22Mc/s)Data channelPilot channelReverse rate indicator (RRI) channelData rate control (DRC) channelACKchannel#14 18Physical Layer (reverse link)•Reverse traffic channel–Transfers both data and signaling messages–One PHY packet contains one MAC packet– Length of PHY packet longer when length of MAC packet longer (256, 512, 1024, 2048, 4096 bits)–PHY packet size depends on achievable data ratePHY pktsize (bits)256512102420484096Data rate (kbps)9.619.238.476.8153.6Code rate1/41/41/41/41/2Modulation typeBPSKBPSKBPSKBPSKBPSK–Each PHY packet occupies 16 slots (26.67ms)–Turbo codes used in reverse link too (delay not a problem)#14 19Physical Layer (reverse link)••Data channelDRCchannel–Different Walsh code from all other channels–When data channel active, so is pilot & RRI channel–AT notifies AN of AT’shome sector using DRC channel–Also AT requests AN to send at certain rates using DRC channel–AN sends on forward channel using rate requested by AT in DRC channel–AT may use the following chart (one implementation) to decide what rate to requestBender, P., et al., “CDMA/HDR: A Bandwidth EfficientHigh Speed Wireless Data Service for Nomadic Users,” IEEE Communications, Vol. 38, No. 7, July 2000, pp. 70-77.#14 20Physical Layer (reverse link)•Reverse rate indicator channel–Tells AN of the rate at which packet are sent in reverse-link data channel –6 possible rates (including 0 Kbps)–Tell AN once every PHY packet (16 slots) so AN knows what rate data is coming at–ACK/NACK a forward channel PHY packet based on CRC check success/failure–Used by AT to first contact AN–Rate fixed at 9.6 Kbps (access packet always 256 bits)–Access probe carries PHY access packet •ACKchannel•Access channel #14 21Power control (reverse link)•On reverse link, pilot channel, data channel, DRC channel and ACK channel are power controlled•Both open-loop and closed-loop power control used•Open-loop power control–AT receives forward pilot channel–AT uses this to compute mean output power in reverse link–Lower the received power of forward channel pilot, higher is the open-loop mean output power of reverse channels–Reverse link power also function of transmission rate•AT needs higher power to transmit at 153.6 than at 9.6 Kbps•Closed-loop power control–AT receives power control bits from AN on RPC channel–AT changes mean output power based on these bits–ANhasEb/N0threshold•If received power less than threshold, send “power up” to AT•If received power more than threshold, send “power down”•Threshold is computed dynamically at AN#14 22Adaptive modulation and coding•Channel is time-varying: mobility, fading, etc.•If adaptive modulation/coding not used then either–Design modulation/coding conservatively for good link quality but then high data rates cannot be achieved–Or design modulation/coding for high data rate but then link quality is low–Improves spectrum efficiency, system performance•Adaptive: match transmission parameters to channel•In EV-DO systems, AT reports DRC (based on SNR) in every time-slot (1.667 ms)•AN uses this information to chose suitable modulation and coding for that time-slot (target packet error rate at less than 1%)#14 23Adaptive modulation and codingData Rate (kbps)38.476.8153.6 307.2307.2614.4614.4921.61228.81228.81843.22457.6Modulation typeQPSKQPSKQPSKQPSKQPSKQPSKQPSK8-PSKQPSK16-QAM8-PSK16-QAMBits per encoder packet102410241024102420481024204830722048409630724096Code rate1/51/51/51/51/31/31/31/31/31/31/31/3Number of slots used per packet1684241221211#14 24Forward link transmission characteristics •AN sends pilot bursts in every time-slot•AT estimates SNR using pilot bursts•AT uses estimated SNR to request a data-rate on the data-rate request channel (DRC)•AN sends at requested rate using suitable modulation/coding for that data rateAdaptive modulation and codingPilot burstAT receivesestimate data rateAT transmitsPilot-DRC1.67 msAN transmit at requested ratePilot-DRC#14 25request data ratePilot-DRCHybrid ARQ (PHY layer ARQ)•PHY ARQ faster than link layer ARQ•Makes adaptive modulation/coding more robust–DRC mechanism discussed previously provides initial estimate of redundancy required–Hybrid ARQ enables fine tuning of effective code rate•For EV-DO multi-slot packets–ATACKSorNACKSdatareceived in each slot–Incremental coding is used to soft-combine data –Erroneous data is not discarded but combined with the data in next slot–Yields better bit-rate than discarding erroneous data #14 26Hybrid ARQ (PHY layer ARQ)•Multi-slot transmissions interleaved by 3 slots–Allows time to receive NACK/ACK•Example case: 153.6kbps –QPSK –4 slots –1/5 codingFWD trafficchannel(AN->AT)slotTransmitslot 1nn+1Transmitslot 2n+2n+3n+4n+5Transmitslot 3Transmitslot 4n+6n+7n+8n+9n+10n+11n+12n+13n+14n+15DRC channel(AT->AN)DRC requestfor 153.6 KbpsOne half slotoffsetACKchannel(AT->AN)NACKNACKNACKACK#14 27Hybrid ARQ (PHY layer ARQ)•If channel conditions improve since DRC request–Data can be received correctly with less coding–Early termination possible in that caseFWD trafficchannel(AN->AT)slotTransmitslot 1nn+1Transmitslot 2n+2n+3n+4n+5Transmitslot 3Transmitslot 1First slot of nextPHY packetn+6n+7n+8n+9n+10n+11n+12n+13n+14n+15DRC Channel(AT->AN)DRC requestfor 153.6 KbpsOne half slotoffsetACKChannel(AT->AN)NACKNACKACKNACK#14 28Radio link protocol (RLP)•Reliable octet-stream service to higher layers–Provides retransmission –Provides duplicate detection•Transmitter–Creates RLP segments from octet-stream–Appends sequence number to each segment •Receiver–Detects duplicate/missing segments–Delete duplicate segments–Send negative ackfor missing segments (transmitter retransmits missing segment only once)–If no missing segments, send data to higher layer–If missing segment retransmitted and lost, send data to higher layer –it is up to the higher layers to recover now#14 29Case studyMitigating scheduler-induced starvation in 3G wireless networksSoshantBali*, Sridhar Machiraju**, HuiZang**See: A Measurement Study of Scheduler-based Attacks in 3G Wireless NetworksSoshantBali, Sridhar Machiraju, HuiZang, Victor Frost, Passive and Active Measurement. April 5-6, 2007, Louvain-la-neuve, BelgiumAlso see:“Detection and Mitigation of Impairments for Real-Time Multimedia Applications”, S. Bali, Phd. Thesis, University of Kansas, 2007. http://www.ittc.ku.edu/research/thesis/documents/Soshant_Bali_thesis.pdfand http://www.ittc.ku.edu/research/thesis/documents/Soshant_Bali.pdf* ITTC, Univ. of Kansas, Lawrence, Kansas** Sprint Advanced Technology Lab, Burlingame, California#14 30Outline•Introduction•Problem: PF with on-off traffic –Highjitter–Throughput reduction–Increased flow completion time–Parallel PF–Shrinking alpha#14 31•Solution Introduction•3G-wireless widely deployed•SprintandVerizonuse1xEV-DO–––––1x Evolution for Data OptimizedUp to 2.45Mbps downlink, 153.6Kbps uplinkNatural evolution from IS-95, IS-2000Evolution: leverage existing network elementsOptimized for data transfer •EV-DO: higher rate in forward link •EV-DO: uses link layer ARQ•EV-DO: powerful error-correcting codes (e.g., turbo codes)•PHY packet error rate < 1%, ARQ on top of that = Reliable link•EV-DO: uses time-division multiplexing•Data service characteristics–Rates asymmetric–Latency can be tolerated–Transmissions are in burst#14 32Introduction•Scheduler–Time divided into time-slots–Scheduling problem: Base station has to decide which mobile it should send data to in next time slot–EV-DO and HSDPA use PF scheduler•••••ContributionChannel-aware schedulerImproves system throughputVery well researched, shown to have very good performanceWidely deployed (all major vendors implement and recommend using this algorithm)–PF scheduler can easily lead to starvation of mobiles•Deliberately (malicious user)•Accidentally (one mobile web browsing can cause impairments to other mobile users) –Propose and evaluate starvation resistant scheduler#14 33EVDO: adaptive modulation/coding•Channel conditions are time-varying: mobility, fading, etc.•If adaptive modulation/coding not used then either–Design modulation/coding conservatively for good link quality but then high data rates cannot be achieved–Or design modulation/coding for high data rate but then link quality is low–Improves spectrum efficiency, system performance•Adaptive: match transmission parameters to channel conditions•AT measures SINR every time slot (1.67ms) and in determines suitable DRC (data rate control)•AT reports DRC in every time-slot •AN uses this information to chose suitable modulation and coding for that time-slot (target packet error rate is less than 1%)#14 34EVDO scheduler•DRC tells AN what modulation/coding to use for an AT for each time slot•However, DRCscan also be used by scheduler to make better scheduling decisions•AN gets DRC information for each time slot from all K ATs•Scheduler at AN must decide which AT to allocate the next time slot to•If scheduler uses DRC information to make scheduling decision then channel-aware scheduler (e.g. PF)•If does not use DRC information then not channel-aware (e.g., Round Robin)•Channel-aware scheduling improves system throughput and throughput of achieved by individual ATsANATAT#14 35PF scheduler with on-off traffic•PF design assumes infinite backlog, but…..–Traffic commonly on-off, e.g., web browsing•Problem: on-off traffic causes starvation––––––When off, no slots allocated to that ATAverage decays when no slots allocatedWhen on after long off, average is very lowAT that goes on has highest R/A amongst all ATs(low A)AT that goes on gets all slots until A increasesThis starves other ATs•PF widely deployed and can be easily corrupted–Deliberately (attacks using burst UDP)–Accidentally (web browsing)#14 36PF scheduler with on-off traffic•AT1 infinitely backlogged•AT2: on for 1000 slots, off for 5000 slotsAT 1: always onAT 2: on-offAT1s queueAT2s queue#14 37PF scheduler with on-off trafficAT 1: always onAT1AT2A1[t−1]AT 2: on-offAT2 offAT2 onA1>>A2A2[t−1]Conclusion: Sending on-off traffic to one laptop can lead to starvation in other AT’sAT1 starvedR1/A1<
Time slot Compute Rk[t]/Ak[t-1]for AT k=1, since thereis no data for AT2. Final scheduling decidedby PF1 Update Ak[t] for all kCompute Rk[t]/AkP[t-1]for each AT k. PF2does not look at the Queues. Assumes backloggedUpdate AkP[t] for all kSummary:-•PF1 decides final scheduling•PF2 only virtual scheduling•PF1 aware of queue size•PF2 unaware of queue size•When on after off, copy averages from PF2 to PF1At time t+M, AT2 queue receives data for AT2Ak[t+M-1]= AkP[t+M-1]Compute Rk[t]/Ak[t-1]for all k. AT with highest ratio gets slot.#14 48Parallel PF schedulerAT1AT2A1[t−1]AT2 ONA1[t−1]AT2 ONA1P[t−1]A2P[t−1]A2[t−1]PF averageA1= 2.4 MbpsA2 very lowA2[t−1]PPF averageA1, A2 1.2Mbps#14 49Parallel PF scheduler•PF: AT1 starved when AT2 goes from off to on•PPF: Both AT1 and AT2 get equal share of slots immediately after AT2 goes from off to onPFPPF#14 50Simulation setup •••••Collect DRC traceCollect stationary user DRC trace in in deployed systemdeployed system using CDMA air interface tester (CAIT)DRC trace input to ns-2Server-base station 100MbpsAT with CAIT-Cisco Base station queue sizes > largest DCR measurement instrumentUDP burst (no losses)DRC trace input to ns-2Base-station to AT DRC variable (from trace)–Loss probability = 0–RLP not implemented (not needed)••High bandwidth link from AT to serverTraced based simulation, DRC’sfrom real channel measurementsAT100Mbps linkbase stationserverATns-2 model#14 51TCP throughput reduction: long flows••AT1 downloads 20 MB file, AT2 sends cbror burstyUDP traffic; burst size = 150 packetsFigure shows that PPF is robust to starvation due to UDP bursts#14 52TCP increased flow completion time: medium flows#14 53PF and PPF : HTTP users••••All users HTTPFile size: uniform 10KB to 100KBTime b/w downloads: uniform 2 to 8 secStationary DRCs#14 54Initial values for A(k)•If Off time small enough then can use last observation•After about 12 sec inactivity–AT connection goes into sleep mode–DRC not reported–PPF cannot work•If flow restarts after 12 or more sec–Average resets to zero–AT that restarts gets all slots for some time–Other ATsstarved#14 55Longer inactivity: shrinking alpha•Solution: use s-alpha when flow restarts–Slot 1: average=0, alpha=1–Slot 2: alpha=1/2, slot 3: alpha=1/3 … slot 1000: alpha=1/1000–Average converges faster than if slot 1: alpha=1/1000#14 56PFS-alphaPF with s-alphaAT1 starvedAT1 not starvedA1[t] grows slowlyA1[t] grows quicklyA1[t−1]A1[t−1]A2[t−1]A2[t−1]#14 57Conclusions•PF can be easily corrupted•Solution–Deliberately (attacks using burst UDP)–Accidentally (web browsing)–Parallel PF–Shrinking alpha –Combination makes PF robust to corruption–PF is well researched, widely deployed–Security issues were not considered–Infinite queue backlog assumption•Lessons learned•Design algorithms taking security into consideration•Simplifying assumptions good for analytical optimality results•But evaluate algorithms for when assumptions violated•Specially when assumption does not represent the common-case scenario#14 58References••••••TIA/EIA/IS-856, cdma2000 High Rate Packet Data Air Interface Specification, Telecommunications Industry Association, January 2002.Samuel C. Yang, “3G CDMA 2000: Wireless System Engineering,” ArtechHouse Inc.KamranEtemad, “CDMA 2000 Evolution,” John Wiley and Sons Inc., 2004MooiChooChuahand QinQingZhnag, “Design and Performance of 3G Wireless Networks and Wireless LANs,” Springer Inc., 2006.Bender, P., et al., “CDMA/HDR: A Bandwidth Efficient High Speed Wireless Data Service for Nomadic Users,” IEEE Communications, Vol. 38, No. 7, July 2000, pp. 70-77.SoshantBali, Sridhar Machiraju, HuiZang, Victor Frost, “A Measurement Study of Scheduler-based Attacks in 3G Wireless Networks, Passive and Active Measurement,” April 5-6, 2007, Louvain-la-neuve, Belgium#14 59