On Profile Optimization inDOCSIS 3.1 Networks ExploitingTraffic PredictionbySumayia AbedinB.Eng. Hons., International Islamic University Malaysia, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Electrical Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)October 2018c© Sumayia Abedin, 2018ii iiAbstractThe latest release of the Data over Cable Service Interface Specification(DOCSIS), namely DOCSIS 3.1, has introduced the use of adaptive bitloading profiles. The optimal design of these profiles is critical for the overallperformance of a Hybrid Fiber Coaxial (HFC) cable system.In this thesis, we introduce a low complexity profile design algorithm thatmaximizes the average throughput of a HFC system by grouping its cablemodems (CMs) on the basis of both their downstream data arrival rates andchannel signal-to-noise ratios (SNRs). Optimizing the profiles on the basisof both CM traffic and CM channel SNRs is challenging as these two criteriaare somewhat contradictory. To account for the CMs’ channel SNRs, CMswith similar SNR distributions should be grouped into the same profiles.However, to take into account the CMs’ traffic, CMs with high data arrivalrates should be grouped into profiles with higher bit loading capabilities,and CMs with lower data arrival rates should be grouped into profiles withlower bit loading capabilities.In this thesis, we take into account these two contradictory criteria inthe profile optimization problem, and we propose a sub-optimal solutionto solve this problem. Performance analysis results of our algorithm showthat accounting for both CM channel SNR and CM traffic can improve theiiiAbstractaverage throughput of a HFC system. Furthermore, our approach accountsfor the CMs’ traffic without requiring future knowledge of their actuallyrealized data arrival rates, which is difficult to obtain in practice.We also consider an asymptotic scenario, where the per-profile arrivalrates (which is the sum of the arrival rates of all the CMs in a profile) isalways guaranteed to be less than the respective per-profile bit loading ca-pacities. For this case, our algorithm optimizes the system profiles with theobjective of minimizing the system’s total average data transmission time.We show that our proposed approach yields significantly high performance,particularly for scenarios with a high degree of heterogeneity in the CMs’traffic.ivLay SummaryDue to the rapidly growing popularity of high-speed applications amongbroadband internet users, the demand for higher and higher speeds amongthese users is rapidly increasing. Hybrid Fiber Coaxial (HFC) cable networksare predicted to soon provide their users with multi-gigabits-per-second(Gbps) speeds. HFC networks can achieve this by tailoring the transmis-sion of the network’s data to the different network conditions experiencedby different users. In this thesis, a novel and practical data transmissionapproach is proposed where the data transmission is tailored to the uniquetraffic conditions experienced by different groups of users. By doing this,the proposed approach yields significant gain in increasing the users’ speeds.The proposed approach is also practical as it requires knowledge of only thetraffic statistics of the users, and not their actually realized traffic, the latterof which is highly challenging to obtain.vPrefaceThis thesis is based on the research work conducted in the School of En-gineering at The University of British Columbia’s Okanagan campus underthe supervision of Dr. Jahangir Hossain. A submitted work is contained inthis thesis.A part of Chapter 3 and the entirety of Chapter 4 of this thesis have beensubmitted for publication in the IEEE Transactions on Network and ServiceManagement. I am an investigator of the analysis and numerical simulationsof the publication. Dr. Mahdi Ben Ghorbel (who was a postdoctoral fellowof Dr. Hossain) and Dr. Hossain helped to prepare the manuscripts byguiding me through the simulations, checking the validity of the analyticaland numerical results, and proofreading the submitted manuscript.viTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 History and Background . . . . . . . . . . . . . . . . . . . . . 11.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 Thesis Outline and Contributions . . . . . . . . . . . . . . . . 9Chapter 2: Background of Bit Loading Profiles in DOCSIS 3.1 122.1 DOCSIS 3.1 Network Architecture . . . . . . . . . . . . . . . 132.2 DOCSIS 3.1 Downstream Physical Layer . . . . . . . . . . . . 152.3 DOCSIS 3.1 Bit Loading Profiles . . . . . . . . . . . . . . . . 17viiTABLE OF CONTENTS2.4 Number of Profiles in an HFC System . . . . . . . . . . . . . 192.5 PMA Introduction and Architecture . . . . . . . . . . . . . . 212.5.1 PMA Architecture . . . . . . . . . . . . . . . . . . . . 232.6 PMA System Operation . . . . . . . . . . . . . . . . . . . . . 252.6.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . 262.6.2 Downstream Profile Optimization . . . . . . . . . . . . 272.6.3 Fallback . . . . . . . . . . . . . . . . . . . . . . . . . . 302.7 DOCSIS 3.1 PHY-MAC Convergence Layer . . . . . . . . . . 302.8 Poisson Process . . . . . . . . . . . . . . . . . . . . . . . . . . 332.8.1 Poisson Random Variable . . . . . . . . . . . . . . . . 332.8.2 Properties of the Poisson Process . . . . . . . . . . . . 342.9 Orthogonal Frequency Division Multiplexing . . . . . . . . . 35Chapter 3: Profile Optimization for Low Data Rate Applica-tions . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 453.3 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . 463.3.1 Derivation of the Total Average Data TransmissionTime of the HFC System . . . . . . . . . . . . . . . . 463.3.2 Traffic Aware Profile Assignment . . . . . . . . . . . . 473.4 Performance Analysis of TAPA . . . . . . . . . . . . . . . . . 493.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57Chapter 4: Profile Optimization for a Generalized Traffic Sce-nario . . . . . . . . . . . . . . . . . . . . . . . . . . . 63viiiTABLE OF CONTENTS4.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 654.3 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . 674.4 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . 704.4.1 Optimality Analysis . . . . . . . . . . . . . . . . . . . 714.4.2 Performance Analysis . . . . . . . . . . . . . . . . . . 734.4.3 Asymptotic Analysis . . . . . . . . . . . . . . . . . . . 764.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78Chapter 5: Conclusions . . . . . . . . . . . . . . . . . . . . . . . 855.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . . 855.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 86Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88ixList of FiguresFigure 2.1 HFC network architecture. . . . . . . . . . . . . . . . 37Figure 2.2 DOCSIS 3.1 downstream OFDM channel. . . . . . . . 38Figure 2.3 PMA network architecture. . . . . . . . . . . . . . . . 39Figure 2.4 PMA downstream profile optimization workflow. . . . 40Figure 2.5 DOCSIS 3.1 PHY-MAC convergence layer (CL). . . . 41Figure 3.1 Absolute and relative transmission time gain of TAPAover CoPA for variable CMs’ distributions among twotraffic patterns (I = 2). . . . . . . . . . . . . . . . . . 58Figure 3.2 Relative transmission time gain of TAPA over CoPAwith uniformly distributed CMs among variable traf-fic patterns. . . . . . . . . . . . . . . . . . . . . . . . 59Figure 3.3 Relative spectrum efficiency loss of TAPA comparedto CoPA with uniformly distributed CMs among vari-able traffic patterns. . . . . . . . . . . . . . . . . . . . 60Figure 3.4 Loss in transmission time relative to the case wherean independent profile is used for every CM. . . . . . 61Figure 3.5 Steps of the Traffic Aware Profile Assignment algo-rithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . 62xLIST OF FIGURESFigure 4.1 Throughput of TAPA with average CM arrival ratesand that with actual arrival rates, with β = 10. . . . 79Figure 4.2 Absolute throughput of TAPA and CoPA, and per-centage throughput gain achieved by TAPA over CoPAunder a uniform scheduler with β = 10. . . . . . . . . 80Figure 4.3 Absolute throughput of TAPA and CoPA, and per-centage throughput gain achieved by TAPA over CoPAunder a maximum capacity scheduler, with β = 10. . 81Figure 4.4 Absolute throughput of TAPA and CoPA, and per-centage throughput gain achieved by TAPA over CoPAunder a maximum fairness scheduler, with β = 10. . . 82Figure 4.5 Average per-CM spectrum efficiency of TAPA andCoPA, under a CM-density-based scheduler with β =10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Figure 4.6 Average per-CM throughput of TAPA and CoPA, andpercentage throughput gain achieved by TAPA overCoPA, for the general scenario and for the asymptoticscenario, under a CM-density-aware scheduler withβ = 10. . . . . . . . . . . . . . . . . . . . . . . . . . . 84xiList of AcronymsAcronyms DefinitionsBER Bit Error RateBiSort Bi-sectional SortingBPSK Binary Phase Shift KeyingCDF Cumulative Distribution FunctionCL Convergence LayerCM Cable ModemCMTS Cable Modem Termination SystemCoPA Clustering for Profile AssignmentCP Cyclic PrefixCPE Customer Premises EquipmentDOCSIS Data over Cable Service Interface SpecificationDPD Downstream Profile DescriptorFDM Frequency Division MultiplexingFEC Forward Error CorrectionGbps Gigabits per secondHFC Hybrid Fiber CoaxialIP Internet ProtocolKHz KilohertzxiiList of AcronymsLAN Local Area NetworkLDPC Low Density Parity CheckMAC Media Access ControlMbps Megabits per secondMILP Mixed Integer Linear ProgrammingMMM MAC Management MessageM-QAM M -ary Quadrature Amplitude ModulationMSO Multiple System OperatorNCP Next Codeword PointerOCD OFDM Channel DescriptorOFDM Orthogonal Frequency Division MultiplexingOPT-REQ OFDM Profile Test RequestOPT-RSP OFDM Profile Test ResponsePAPR Peak to Average Power RatioPHY PhysicalPMA Profile Management ApplicationPMF Probability Mass FunctionPNM Proactive Network MaintenancePPP Poisson Point ProcessQoS Quality of ServiceQPSK Quadrature Phase Shift KeyingRF Radio FrequencyRxMER Receive Modulation Error RatioSC-QAM Single Carrier-QAMxiiiList of AcronymsSDN Software Defined NetworkingSG Serving GroupSNR Signal-to-Noise RatioTAPA Traffic Aware Profile AssignmentxivChapter 1Introduction1.1 History and BackgroundHigh speed applications have rapidly been gaining popularity amongbroadband consumers. Owing to this increase in popularity, the data ratedemands of broadband consumers are rapidly increasing. Hybrid fiber coax-ial (HFC) cable networks have been predicted to be able to soon providetheir users with multi-gigabits-per-second (Gbps) rates [1, 2]. Furthermore,these networks require low installation costs since they use existing cabletelevision infrastructure. This makes HFC networks a viable solution tosatisfy the growing data rate demands of broadband users.The ability of HFC networks to provide multi-Gbps rates to their usersin the near future is due to the recent development in their transmissionstandard, called Data over Cable Service Interface Specification (DOCSIS).The most recent release of the standard, called DOCSIS 3.1, has introducedthe use of multicarrier modulation in the Physical (PHY) and Media Ac-cess Control (MAC) layers [3, 4]. Specifically, DOCSIS 3.1 uses OrthogonalFrequency Division Multiplexing (OFDM) for its downstream transmission.Under this new specification, cable modems (CMs), located at customerpremises, will use wide channels that consist of many narrowband orthog-11.1. History and Backgroundonal subcarriers. Different modulation orders (or equivalently bit loadingvalues) can be assigned to different subcarriers within the same channel.This resulting granularity in the way bit loading values can be assigned toa CM’s OFDM channel allows better accommodation of the channel qualityand network conditions that the CM experiences, (i.e., the signal-to-noiseratio (SNR) distribution, interference, etc.). This customization of the datatransmission to a CM’s network conditions results in the net improvementof the network performance [5].The feasibility of using cable television infrastructure for the purpose ofdata transfer was first tested by MITRE Cablenet in 1979, with the test bedsystem reaching data rates of 307.2 Kbps [6]. In the mid-1990s, CableLabsbegan work on developing the DOCSIS specification to standardize the useof cable television infrastructure for high speed data transfer. The firstversion of the standard, called DOCSIS 1.0 was released in March of 1997 [7],and it provided specifications to ensure that the CMs and Cable ModemTermination Systems (CMTSs) of different vendors would be interoperable.The standard enabled up to 37 Mbps net throughput in the downstreamand 8 Mbps net throughput in the upstream. By allowing them to providesuch unprecedented data rates, DOCSIS made cable vendors providers ofnot only video content but of the Internet too.In 1999, two years after the DOCSIS 1.0 specification was completed,DOCSIS 1.1 was released to add quality of service (QoS) to the standard [8].Following that, in December 2001, the next specification called DOCSIS 2.0was released, focusing on the upstream [9]. This specification increased themaximum upstream throughput from a net 8 Mbps to 27 Mbps.21.1. History and BackgroundDOCSIS 3.0, released nearly five years later, further increased datarates in both the upstream and the downstream [10]. Particularly, it in-troduced channel bonding in which multiple Quadrature Amplitude Modu-lation (QAM) channels could be grouped into one logical group that couldbe used to send and receive data. In this way, a DOCSIS 3.0 modem wasable to transmit at least four times the data of a DOCSIS 2.0 modem. Ad-ditionally, DOCSIS 3.0 also introduced support for IPv6 addresses.Finally in October 2013, the latest release called DOCSIS 3.1 was in-troduced, offering up to 10 Gbps in the downstream and 1 Gbps in theupstream [3]. DOCSIS 3.1 offers such high data rates by doing away withthe use of the traditional 6 MHz and 8 MHz wide channels that were usedby previous DOCSIS systems. Instead, it has adopted the use of much widerchannels consisting of many narrowband OFDM subcarriers, each of whichcan be assigned a QAM bit loading value, function of the SNR value on thesubcarrier. This is in contrast to previous DOCSIS systems where a 6 MHzor 8 MHz channel used a single QAM carrier, and the entire data payloadof that channel modulated this single carrier. By using variable bit loadingthat can be tailored to a CM’s network conditions, DOCSIS 3.1 has beenable to offer much higher CM data rates than its predecessors.With the introduction of OFDM in the PHY layer, DOCSIS 3.1 has in-troduced the concept of profiles. A profile is defined as the set of subcarriersin an OFDM channel along with their respective bit loading values. Clearly,the best system performance will be achieved if every CM in the systemhas its own profile that is tailored to its network conditions. However, thiswould mean that a HFC system consisting of 500 CMs would require 50031.1. History and Backgrounddifferent profiles to be managed, which would entail high complexity andmemory requirements. In fact, for every profile, a CMTS must perform sep-arate buffering and packaging to match the data packets with their relevantmodulation format which is defined by the profile they belong to.To avoid such high complexity, DOCSIS 3.1 allows a maximum numberof 16 profiles to be defined. This implies that the CMs in a HFC networkwill have to be grouped, and all the CMs in a particular group will haveto use one common profile. It is worth noting that for a given profile, themaximum number of bits that the CMs of that profile can transmit over asubcarrier depends on the worst CM’s SNR on that subcarrier, (i.e., for agroup of CMs that use the same profile, the maximum bit loading value thatcan be assigned to a subcarrier in that profile is the bit loading capability ofthe CM with the lowest SNR on that subcarrier out of all the CMs using thatprofile). In other words, for a particular group of CMs, their profile is theset of per-subcarrier bit loading values, where every value is the minimumof all the CMs’ bit loading capabilities on that subcarrier.Thus, it is clear that how the CMs of a HFC system are grouped willdetermine the profiles that are used in the system. These profiles in turndetermine the overall system performance. In other words, the problem ofdesigning the profiles of a HFC system to achieve a certain performanceobjective is essentially a problem of grouping the system’s CMs.41.2. Literature Review1.2 Literature ReviewDue to the recent release of the DOCSIS 3.1 standard, the notion ofprofile optimization in HFC networks is relatively new. Only few workshave focused on optimizing the CMs’ grouping and the resultant systemprofiles. In this section, we provide a review of these algorithms.The performance of the popular K-means [11] algorithm in maximizingthe CMs’ sum rate capacity was studied in [12]. The K-means algorithmgroups a set of points into clusters based on a distance metric between thepoints and the “centroid” (mean) of the clusters. A point is assigned to thatcluster for which the distance between the point and the cluster’s centroidis the minimum. K-means is not guaranteed to find the optimal groupingsolution. In fact it always converges to a local optimum. However, it isvery efficient and a good solution can be obtained by running the algorithmmany times and choosing the best result.The authors of [12] also proposed a Bi-sectional sorting (BiSort) algo-rithm where CMs are first sorted in descending order of the maximum datarate they could achieve. Then the CMs are split into two groups accordingto their data rate capacity. The splitting process is repeated until the de-sired number of groups is obtained. The assumption behind this techniqueis that CMs with similar data rate capabilities have similar SNRs across thesame subcarriers. This assumption, however, may not always be true dueto interference and SNR variation over frequency.In [13], the authors proposed another clustering algorithm, called Clus-tering for Profile Assignment (CoPA), that takes into account the per sub-51.2. Literature Reviewcarrier characteristics of the CMs. CoPA is a greedy algorithm that groupsCMs into profiles with the objective of maximizing their data rate capaci-ties. For a particular number of profiles, a CM per profile is first randomlyassigned; and the remaining CMs are added to profiles that maximize thesum rate of the system. Then, the CMs are considered one by one and eachCM is swapped between the profiles iteratively. At very swap, the result-ing system sum rate is calculated. Whenever a swap is found that furtherincreases the sum rate capacity of the system, the swap is executed for theCM. This procedure is repeated until no swap is found that improves thesum rate of the system.The authors of [14] also proposed to group the CMs with the goal ofmaximizing the system sum rate capacity. However, instead of heuristicallysolving the CM grouping problem, the authors formulated it as a lower di-mensional mixed integer linear programming (MILP) problem and obtaineda near-optimal solution.The authors of [15] proposed a K-Means-Coalescation algorithm. In thisalgorithm, the K-means procedure is first used to group the CMs into NIclusters, where NI is greater than 16. Each cluster has its own profile.To reduce the number of profiles, two of the NI profiles are combined intoone. The decision of which two profiles should be combined is made by firstgenerating the set of all possible pairs of profiles among the NI profiles to becombined, and evaluating the effect of these combinations on the sum rate ofthe system. The pair of profiles whose combination maximizes the sum rateare chosen and combined into one, which results in reducing the numberof profiles to NI − 1. This process of combining profiles is progressively61.3. Motivationrepeated until reaching the required number of profiles.Finally, the authors in [16] proposed the use of principal componentanalysis [17] to derive low-dimensional clustering variables that reduced thecomplexity of the clustering problem and improved the spectral efficiency ofthe resulting system profiles.1.3 MotivationAll of the algorithms discussed above aim to maximize the sum ratecapacities of the CMs in the HFC network. For this reason, the overarchingprinciple behind these algorithms is that the CMs should be grouped on thebasis of the similarity of their subcarrier SNRs. Therefore, CMs with similarper-subcarrier SNRs are grouped together, and are assigned to commonprofiles that maximize the bit loading capacity of the CMs in the system.However, maximizing the data rate capacity of the system may not nec-essarily imply that the system throughput is also being maximized. For aCM, its throughput refers to the amount of data that is actually transmittedto it, which is limited by not only its bit loading capacity but also by thedata available for transmission to the CM.To elucidate this point, let us consider an example of two CMs, calledCM1 and CM2 in a HFC network. We assume CM1 has low SNR acrossmost of its subcarriers but very high data arrival rate, while CM2 has rel-atively higher SNR but significantly lower data arrival rate. For example,CM1 might be streaming a high definition video, while CM2 is browsingtext-based webpages.71.3. MotivationUsing the above-mentioned grouping approaches from the literature,CM1 would be grouped with other CMs in the system that have low per-subcarrier SNRs and assigned to a profile named A, while CM2 would beassigned to a higher bit loading profile named D. However, because the ac-tual data arrival rate of CM2 is low, it is only rarely able to take advantageof the high bit loading capacity enabled by profile D. Thus, the benefit ofhaving CM2 in profile D is small. In addition, because the bit loading usedin a given profile is chosen according to the minimum SNR of all the CMsusing the profile, removing CM2 from D could enhance the capacity of D,and in turn enhance the throughput of the remaining CMs in profile D. Atthe same time, since CM2 has low bandwidth requirements, the impact tothe system may be minimal if it is assigned to a lower profile. On the otherhand, due to the low capacity of profile A, the high data rate required byCM1 would force the downstream transmitter to use A a large fraction ofthe time, degrading the throughput and performance of the network as awhole. It is possible that the system performance would improve if CM1was moved into a dedicated profile with higher bit loading.Therefore, grouping CMs only on the basis of their subcarrier SNRs canlead to inefficient usage of profile capacity for some CMs, and reduction ofthroughput for other CMs in the system. In other words, it is not sufficientto design profiles with the objective of simply maximizing the sum ratecapacity of the system. Rather, in addition to their channel SNRs, the trafficpatterns of the CMs also need to be taken into account when grouping theminto profiles.Designing profiles on the basis of both the CMs’ data arrival rates and81.4. Thesis Outline and Contributionstheir subcarrier SNRs can help to improve the overall performance of theHFC network. However, this is not a straightforward task as these twocriteria are somewhat contradictory. Moreover, a new challenge arises withtaking into account the CM data arrival rates. It is not possible to knowa-priori the actual data arrival rates of the CMs that will be realized in thefuture. It is only the distribution of the CMs’ traffic that can be predictedbased on their historic traffic information. Therefore, a key challenge fortraffic-aware CM grouping algorithms is accounting for CM traffic withoutrequiring information of the actual realization of the CMs’ traffic.1.4 Thesis Outline and ContributionsThis thesis is arranged into six chapters. Chapter 1 presents backgroundknowledge on the history and development of the DOCSIS standard. Inaddition, this chapter provides a literature review related to the rest of thisthesis.Chapter 2 presents the required technical background for the entire the-sis. We first introduce a typical DOCSIS 3.1 network’s architecture. Wethen discuss the DOCSIS 3.1 PHY layer and the concept of bit loadingprofiles. Next, we discuss the number of profiles that can be designed fora HFC system and how the grouping of the CMs determines the differentprofiles. Then we discuss the Profile Management Application (PMA) func-tionality [18] that has been introduced in the DOCSIS 3.1 specification, thedata elements the PMA requires and the PMA’s system operation. Follow-ing this, we present a discussion about the DOCSIS 3.1 convergence layer91.4. Thesis Outline and Contributionsand the different scheduling mechanisms that may be used by the down-stream transmitter. Finally, we conclude this chapter with a discussion ofthe Poisson Point Process (PPP) and OFDM.In Chapter 3, we propose a novel profile design approach that maximizesthe performance of a HFC system by taking into account the variabilityin the CMs’ downstream data arrival rates and subcarrier SNRs. In thischapter, we consider the special case of a HFC system where the arrival rateof every profile is guaranteed to be less than the bit loading capacity of theprofile. For this asymptotic scenario, our approach groups the CMs withthe goal of minimizing the system’s total average data transmission time.We propose an optimal analytical solution that can be written as a functionof only the average arrival data per CM, which can be easily predicted fromhistoric data. A greedy, heuristic algorithm can then be used to optimizeprofiles accounting for both CMs’ SNRs and arrival rates.We show that our approach achieves significant gains in transmissiontime reduction thanks to its consideration of the CMs’ traffic. We demon-strate that these gains increase with increased heterogeneity in the dataarrival rates of the CMs. In this chapter, we also highlight the benefits ofusing multiple profiles on the performance of a HFC system. Specifically, ourresults show that even with simple grouping algorithms, the use of multipleprofiles yields better system performance over a single-profile system.Next, in chapter 4 we consider the more general case of a HFC systemwhere the arrival rate per profile can be less or greater than the profile’s bitloading capacity. As mentioned earlier, our traffic-aware approach groupsthe CMs of the system on the basis of their data arrival rates and subcarrier101.4. Thesis Outline and ContributionsSNRs. For the generalized scenario considered in this chapter, the goal of ourtraffic aware approach is to maximize the system’s total throughput. Thegeneralization adds further complexity to the profile optimization problemsince a profile’s data will need to be stored in its buffer when its arrival rateis greater than its channel capacity. In other words, a coupling between thearrived data of different time slots is introduced which makes knowledge ofthe CMs’ actual data arrival rates required for optimal solving. To this end,we propose a suboptimal solution that can be written as a function of onlythe CMs’ average arrival rates, and we design the system profiles by takinginto account the CMs’ channel SNRs and data arrival.Performance results show that our approach yields significant gain inthroughput improvement by accounting for the CMs’ traffic patterns in theprofile optimization problem. As in the previous chapter, we demonstratethat these gains increase with increased heterogeneity in the data arrivalrates of the CMs. Furthermore, we show that these gains are consistentacross different scheduling mechanisms that may be used by the downstreamtransmitter. More importantly, our algorithm achieves these gains usinginformation about only the average arrival rates of the CMs. In other words,it does not require future knowledge of the actual CM arrival rates, whichmay be impractical and difficult to obtain. We also show that our heuristicapproach yields close to optimal results, at significantly less computationalcomplexity than optimal exhaustive search algorithms.Chapter 5 summarizes the entire thesis and lists our contributions. Inaddition, some future works related to our current research are also sug-gested.11Chapter 2Background of Bit LoadingProfiles in DOCSIS 3.1This thesis focuses on the optimization of bit loading profiles under a cer-tain performance objective for DOCSIS 3.1 HFC networks. In this chapter,we provide an overview of the necessary technical concepts that are relevantto the task of optimizing DOCSIS 3.1 profiles.We begin by providing a description of the network architecture of atypical DOCSIS 3.1 network. As mentioned earlier, DOCSIS 3.1 allowsHFC networks to provide unprecedented multi-Gbps network rates in thedownstream direction. The primary contributors to such high network datarate capacity are the changes introduced by DOCSIS 3.1 in the PHY layer,and accordingly, we next provide a description of the DOCSIS 3.1 PHYlayer. Following this, we discuss the concept of bit loading profiles. Wediscuss how many profiles an HFC system should use and how the groupingof the CMs determines the different system profiles. The successful operationof a DOCSIS 3.1 network using several profiles is greatly dependent on thePMA functionality that has been introduced by DOCSIS 3.1. We providea description of this functionality and discuss how it optimizes the profiles122.1. DOCSIS 3.1 Network Architectureof a HFC system. Following this, we discuss how the data are mapped tothe created profiles by the PHY-MAC convergence layer. We also providea description of different scheduling mechanisms that may be used by thedownstream transmitter. In the traffic-aware profile optimization approachproposed in this thesis, we assume that the data arrival rates of the CMsfollow a Poisson distribution. Therefore, we next provide a brief descriptionof the PPP. Finally, since bit loading profiles are essentially a set of QAMmodulation orders (or equivalently, bit loading values) across a set of OFDMsubcarriers, we conclude this chapter with a description of OFDM.2.1 DOCSIS 3.1 Network ArchitectureA DOCSIS network may take the form of an all-coaxial cable-basednetwork or a HFC cable-based network. In this work, we focus on HFCcable-based networks, which typically consist of a CMTS serving a largenumber of CMs. The CMTS has many ports; and one or more ports servea serving group (SG) that includes multiple CMs [12].The CMTS is located at the operator’s headend, while the CMs arelocated at the customer premises. Bidirectional transmission of InternetProtocol (IP) data takes place between the CMTS and CM over the HFCsystem. As shown in Fig. 2.1, the HFC system uses fiber trunks between theCMTS and fiber nodes, and a coaxial distribution between the fiber nodesand the CMs. It is the responsibility of the CMTS to manage the transmis-sion of data between itself and the CMs. At the customer location, multipleCustomer Premises Equipment (CPE) such as home routers, laptops etc.132.1. DOCSIS 3.1 Network Architecturemay connect to a CM’s local area network (LAN) interfaces or be embeddedinside the CM.Depending on the applications used by the end users, the CMs at dif-ferent customer locations will have different data traffic. For example, CMslocated at homes where users regularly watch live-streamed internet videowill generally have much higher data arrival rates than CMs at homes whereusers only use web-surfing and email applications for the greater portion ofthe time.In addition to their traffic rates, the CMs in a network vary from eachother in their channel conditions, (i.e., SNRs). This is because despite theuse of a shared cable for the greater portion of the path, each CM has its ownpath to the CMTS port. Secondly, different CMs are located at differentdistances from their serving CMTS. Typical distances between the CMTSand the most distant CM range from 10 to 15 miles (16 to 24 km). To boostsignal levels and increase the geographical reach of the network, amplifiersmay be placed at intervals within the network. Due to he network topologydesign and equipment degradation (e.g. degradation of amplifiers or taps),the CMs will vary in their SNRs. For example, a CM located closest tothe optical node after the first amplifier will enjoy higher SNR than theCM located at the end of the coaxial distribution, after the last amplifier.Finally, interference and noise variations also affect the CMs’ channel SNRs.Thus, in the downstream direction, the CMTS in a HFC network hasto connect to multiple CMs, each with different bit loading capabilities anddifferent data arrival rates.142.2. DOCSIS 3.1 Downstream Physical Layer2.2 DOCSIS 3.1 Downstream Physical LayerAs stated in its PHY layer specification, the DOCSIS 3.1 standard “fo-cuses on the eventual use of the entire spectrum resources available in cableenvironment using scalable, cost effective techniques to achieve full spec-trum use” [3]. In line with this focus, one of the most significant changesintroduced by DOCSIS 3.1 is the adoption of OFDM in the PHY layer fordata transmission. Prior to the release of DOCSIS 3.1, cable systems used6 MHz or 8 MHz wide channels consisting of a single QAM modulated car-rier. In contrast, DOCSIS 3.1 has introduced the use of much wider down-stream channels that consist of a large number of narrowband subcarriers.The spacing between the subcarriers is chosen to ensure perfect orthogonal-ity between them which eliminates inter-carrier interference. Consequently,these subcarriers can be placed very close to each other, which effects moreefficient use of the available spectrum. The orthogonality between the sub-carriers also allows different modulation orders (or equivalently, bit loadingvalues) to be independently assigned to the different subcarriers. Thus, theuse of OFDM introduces variable allocation of modulation parameters thatwas not possible in previous DOCSIS systems.The OFDM downstream channels in DOCSIS 3.1 can range from 24 MHzto 192 MHz in bandwidth. The operating range of the channels can rangefrom lower frequency edges of either 108 MHz (assuming the upstream upperfrequency edge is lower than 108 MHz) or 258 MHz, to upper frequencyedges of either 1218 MHz or 1794 MHz. The orthogonal subcarriers of achannel can be spaced either 25 KHz or 50 KHz apart from each other. A152.2. DOCSIS 3.1 Downstream Physical Layerchannel of 192 MHz would therefore be composed of 7680 subcarriers with25 KHz spacing between them, or 3840 subcarriers with 50 KHz spacingbetween them. Channel bandwidths smaller than 192 MHz can be achievedby nulling some of the subcarriers, i.e., assigning zero bit loading to somesubcarriers.As mentioned earlier, OFDM allows different bit loading values to beindependently assigned to different subcarriers within the same channel.This has introduced two kinds of flexibility in the DOCSIS transmission.The first is the flexibility between the CMs in their channel modula-tion parameters. In previous DOCSIS systems, all the CMs in the networkhad to use the same modulation value across their channels. However, inDOCSIS 3.1, all CMs do not have to use a common modulation parameter.Rather, depending on their respective network conditions, different CMs canuse different bit loading values across their channels.The second degree of flexibility is that between the subcarriers in a givenCM’s channel. While in previous systems a CM had to use one modulationvalue across its 6 MHz or 8 MHz channel, now a CM can use a set of manydifferent modulation values across its channel subcarriers, with each per-subcarrier modulation order being a function of the channel conditions thatthe CM sees on that subcarrier. In other words, in DOCSIS 3.1, not onlycan a CM use a set of different bit loading values across its channels butthis set of bit loading values can also be different from CM to CM. It isthis flexibility in assigning bit loading values to a channel’s subcarriers thatenables DOCSIS 3.1 to provide much higher data rates than its predecessors.To operate as close to the Shannon capacity limit as possible, and maxi-162.3. DOCSIS 3.1 Bit Loading Profilesmize the spectral efficiency of the system, DOCSIS 3.1 requires HFC systemsto support higher order modulations, namely M-QAM modulations of up to4096 QAM, (i.e., Binary Phase Shift Keying (BPSK), Quadrature PhaseShift Keying (QPSK), 8-QAM, 16-QAM, 32-QAM, 64-QAM, 128-QAM,256-QAM, 512-QAM, 1024-QAM, 2048-QAM, 4096-QAM), with optionalsupport for 8192-QAM and 16384-QAM.To support the use of such high order modulations, DOCSIS 3.1 usesthe Low Density Parity Check (LDPC) scheme which is a Forward ErrorCorrection (FEC) scheme to correct bit errors caused by noise [19]. LDPCis more powerful than the Reed-Solomon scheme used by previous DOCSISspecifications [3]. Thus, in the DOCSIS 3.1 specification, OFDM allowsbetter customization of transmission parameters to the network conditions,and LDPC allows a greater density of bits-per-Hertz to be transmitted.2.3 DOCSIS 3.1 Bit Loading ProfilesTo maximize the benefits of using variable bit loading, DOCSIS 3.1 in-troduces the concept of bit loading profiles. In DOCSIS 3.1, a profile isdefined as the set of subcarriers in an OFDM channel and their associatedbit loading values. In other words, a profile is a vector whose length is equalto the number of subcarriers in a channel, and every element of this vec-tor denotes the bit loading used on each of the channel’s subcarriers. In aDOCSIS 3.1 system, these profiles are communicated to CMs, which use theinformation they contain to demodulate the OFDM signals.The DOCSIS 3.1 standard allows for defining multiple profiles in a HFC172.3. DOCSIS 3.1 Bit Loading Profilessystem. Every OFDM channel in a HFC network has its own unique set ofprofiles that are independent of the profiles of other channels. Furthermore,for a particular channel, the bit loading pattern of every profile is indepen-dent from profile to profile. A profile may sometimes contain zero-bit-loadingvalues for certain subcarriers. Such nulled subcarriers are necessary to avoidregions of severe impairment such as noise and interference in the channel.It should be noted that a profile defines the bit loading values to be usedonly across the data subcarriers of a channel; it does not apply to the non-data subcarriers such as pilots, exclusion bands and physical link channel.Profiles may be denoted by letters such as profile A, profile B, etc.It is the responsibility of the CMTS to create a set of profiles for everyOFDM channel. Furthermore, the CMTS must also assign each of the CMsusing a particular channel to the different profiles of that channel. EveryCM using a given OFDM channel must be able to support four profiles forlive traffic and one profile for testing purposes. The test profile is used totest the usability of a potential profile when changing the CM’s profiles. Allthe CMs of a HFC system should support one common profile, which may bereferred to as Profile A. To ensure that all CMs can support it, this commonprofile should be robust and consist of low bit loading values. Profile A maybe used for initialization as well as for control purposes such as receivingbroadcast MAC Management Messages (MMM). It may be noted that notall CMs have to receive data on all profiles. One CM may receive data onprofiles A and B, while another CM using the same channel may receive dataon only profiles A and C. It is the responsibility of the CMTS to keep trackof all the active profiles of each of the CMs, and manage the transmission182.4. Number of Profiles in an HFC Systemof data packets to the different CMs through policy and forwarding rules.It should be mentioned here that for a CM using a particular profile overa given OFDM channel, the sum of the per-subcarrier bit loading values of allthe subcarriers in the channel is referred to as the CM’s spectrum efficiencyor bit loading capacity.2.4 Number of Profiles in an HFC SystemThe CMTS in a HFC system often serves hundreds to thousands of CMs,each of which experiences different network conditions such as different traf-fic patterns and channel SNRs. While the best system performance can beachieved if every CM in a HFC system uses a unique bit loading profiletailored to its specific network condition, doing so would entail high com-plexity as well as high latency and memory requirements. This attendantcomplexity effectively makes it infeasible for a HFC system to allow eachCM to have its own profile.Limiting the number of profiles to one would greatly simplify the taskof the CMTS. However, to ensure that every CM can successfully transmitits data, the bit loading pattern of this single profile would have to be thelowest common denominator of the bit loading values of all the CMs in thenetwork. This in turn would severely limit the capacity of the system andcause the flexibility of OFDM to be almost completely lost.Therefore, as a compromise, the DOCSIS 3.1 standard allows a maximumof 16 downstream profiles to be defined in the CMTS. Since the number ofCMs in a HFC system is much larger than 16, it follows that the CMs will192.4. Number of Profiles in an HFC Systemhave to be grouped and each group will have to use one common profile. Asmentioned earlier, for a group of CMs using a common profile, the bit loadingvalue on every subcarrier is the maximum per-subcarrier bit loading valuethat can be supported by the weakest CM within the group. Consequently,the grouping of the CMs of a system will determine the different systemprofiles.This grouping can be done under different performance criteria. Someexamples of such criteria are as follows:• Maximize the sum rate rate capacity of the CMs in the system.• Maximize the data rate capacity of the group of CMs with the lowestdata rate capacity.• Ensure a certain minimum data rate capacity is maintained for allCMs in the system.• Maximize a certain performance objective by grouping users on thebasis of their data traffic.• Maximize a certain performance objective by grouping users on thebasis of their willingness to pay.The exact grouping methodology which will determine the profiles’ configu-rations is not specified in the DOCSIS 3.1 standard; instead it has been leftto vendor preferences.202.5. PMA Introduction and Architecture2.5 PMA Introduction and ArchitectureDue to the large number of CMs and the variation in the network condi-tions they experience, determining the best set of profiles for the CMs in aHFC network is difficult. Accordingly, DOCSIS 3.1 provides for a dedicatedprofile optimization functionality called the Profile Management Application(PMA) [18] that helps network operators determine what the best profilesare for each OFDM channel, given the network conditions seen by each CMin the channel.The PMA in a DOCSIS 3.1 network is able to identify operationalCMTSs with OFDM channels, collect parameters of the operating chan-nels as well as other data pertaining to network conditions by querying CMsand CMTSs, use the collected data to design bit loading profiles that bestsuit the per-subcarrier SNR values in a channel for a single CM or a group ofCMs, and assign the designed modulation profiles to the respective CM(s).Specifically, the tasks that a PMA performs are as follows:• Designing a set of optimized bit loading profiles by selecting the bestmodulation order for each OFDM subcarrier based on network condi-tions measured at each of the subcarriers of every CM in the system.• For a new CM joining the HFC network, and periodically for exist-ing CMs, finding and recommending the best fit among the existingprofiles.• Creating backup profiles or downgrading a CM based on errors it suf-fers on its current profile.212.5. PMA Introduction and ArchitectureWe provide a detailed description of the above tasks in Section 2.6. Itmay be mentioned at this point that the PMA only makes suggestions forthe above three steps. It is the CMTS’s responsibility to actually apply therecommended profile changes on the DOCSIS network. While the PMA canbe responsible for determining how and when to configure the CMs’ profileassignments and updates, the ultimate control remains with the CMTS.It should also be noted that the PMA functionality is implemented asan “application” that is external to the CMTS. In other words, the PMA isnot a part of the DOCSIS 3.1 MAC and PHY layers. Instead, it performsits responsibilities of designing, assigning, and updating bit loading profilesby communicating with the different CMTSs in the network. Deployingthe PMA external to the CMTS allows operators to use one PMA solutionacross different CMTSs. This allows operators to achieve uniform oper-ation of bit loading optimization algorithms across the different CMTSs,each of which may use different scheduling schemes in their downstreamtransmitters. Implementing the PMA outside the CMTS also releases thePMA from the limited upgrade cycles of the CMTSs, and at the same timeallows the CMTSs to operate without being burdened by the extensive stor-age and computation requirements of the PMA. An external PMA can alsotake advantage of network data resources such as the Proactive NetworkMaintenance (PNM) data lakes that are described in the following sections.In the next subsection we describe the PMA in more detail, covering thePMA high level architecture, and specifically the PMA’s interaction withthe CMTS and the PNM servers.222.5. PMA Introduction and Architecture2.5.1 PMA ArchitectureFigure 2.3 provides the high level architecture of a PMA and its inter-action with the system’s CMs. The availability of information about thenetwork conditions experienced by the CMs at every OFDM subcarrier isessential to the tasks of a PMA that were previously mentioned. The PMAcan obtain such information about CM network conditions through eitherthe PNM toolset that has been newly introduced in the DOCSIS 3.1 stan-dard, or through the downstream OFDM Profile Test Request (OPT-REQ)and the downstream OFDM Profile Test Response (OPT-RSP) MMM ex-changes with the CMTS.While other architectures are possible in a DOCSIS 3.1 system, in thisthesis we consider the following architecture where a PMA interacts withthe PNM servers and the CMTS to optimize the system’s profiles.The following entities are depicted in the architecture shown in Fig-ure 2.3.• Cable Modem Termination System (CMTS): At a high level, thePMA can query the CMTS to get information from the CMs abouttheir channel conditions. The CMTS in turn sends out MMMs tothe CMs to collect the needed information which it sends back tothe PMA. The CMTS can obtain information about various aspectsof a CM’s OFDM downstream channel and its ability to receive aparticular profile through the OPT-REQ messages. Once queried bythe CMTS through an OPT-REQ message, each CM reports back inan OPT-RSP message the Receive Modulation Error Ratio (RxMER),232.5. PMA Introduction and Architecturethe SNR margin, codeword statistics etc. of each subcarrier in theCM’s downstream channels.A CM can also compare and report the RxMER per subcarrier to aparticular threshold, as well as calculate the number of subcarrierswhose RxMER is below a certain threshold and report the results inan OPT-RSP message to the CMTS. A CM can help test the usabilityof a candidate profile by reporting the number of codewords receivedduring testing, the Corrected Codeword Count and the UncorrectableCodeword Count. Furthermore, the CM can report if the number ofcodeword failures on a candidate profile was higher than a certainthreshold.• Proactive Network Maintenance (PNM): Instead of querying theCMTS, the PMA can also obtain the CMs’ network state informationfrom the PNM functionality. The PNM functionality requires all CMsin the network to be able to perform certain measurements of theirPHY layer parameters.These measurements include received power, noise power ratio mea-surement, FEC statistics, Symbol Capture, Wideband Spectrum Anal-ysis, Channel Estimate Coefficients, Constellation Display, RxMERPer Subcarrier and Histogram. Some of the PNM data, like theRxMER numbers, are the same as that computed by a CM for theOPT-RSP. A complete listing of the measurements collected by thePNM is available in the DOCSIS 3.1 PHY layer specification [3]. ThePNM measurements are initiated by a central server that stores the242.6. PMA System Operationdata obtained from each CM. The mechanism by which the PNMserver collects information from the network devices is defined in thepublicly available specification [20].As part of the various measurements that either the CM reports in anOPT-RSP message or the PNM server collects, one measurement can be ofthe data arrival rate of each CM. While it is not possible to a-priori predictthe actual realization of the data arrival rate of each CM, the PMA can usethe arrival rate measurements to develop historical trends and accuratelyestimate the probabilistic distribution of the traffic of each CM. In thisthesis, we are interested in the CMs’ SNR measurements and their averagedata arrival rate measurements to be used by the PMA. The PMA retrievesthe per-CM, per-subcarrier network condition information from either theCMTS or the PNM data lakes, and processes the information through itsprofile design algorithm to construct the best set of profiles for the network’sCMs. As mentioned earlier, the specific profile design algorithm used by thePMA is not specified in the DOCSIS 3.1 standard. This algorithm, whichis the subject of this thesis, is vendor specific and can design the system’sprofiles under different network performance goals.2.6 PMA System OperationIn this section, we describe how the PMA designs profiles for a newOFDM channel, how it further optimizes the profiles after designing theinitial set of profiles for the channel, and how it deals with the scenariowhere a profile is no longer working effectively for a CM.252.6. PMA System Operation2.6.1 InitializationThe initialization stage occurs at the time of starting up a new channel,i.e., when the CMTS has been configured with a new downstream OFDMchannel. At this stage, the CMTS is slowly adding CMs to the OFDMchannel over time. Such a channel may not have any profiles, or may onlyhave a single, non-optimized profile. The initialization step also describesthe scenario when the allocated spectrum is changing or when the channelparameters have been changed. In the following, we describe the PMA’sactivities in the initialization stage.The PMA may first probe the CMTS and learn about the new OFDMchannel, or the CMTS itself may inform the PMA about the new channelbeing created.The PMA then queries the CMTS for information regarding the channelparameters (including that of excluded bands), usage of adjacent spectrumregions, the network topology and the list of currently active profiles on thechannel. The PMA also requests information about the the list of CMs as-signed to each downstream channel. If there are there no CMs assigned toa channel, no further information will need to be requested. The PMA mayrequire historical information about a particular plant segment/frequencyrange. It may procure this information from an earlier DOCSIS 3.1 chan-nel or from other DOCSIS 3.0 channels/CMs that have used the particularplant segment/frequency range. Additionally, the PMA can obtain PNMmeasurements (e.g. spectrum captures) from other devices using other fre-quencies in the network.262.6. PMA System OperationUsing the information procured in the previous step, the PMA can thencraft a set of profiles to be used as a starting point for the channel. Fol-lowing this, the created profiles and the assignment of CMs to them can becommunicated to the CMTS.2.6.2 Downstream Profile OptimizationAfter initialization, the CMs receive Downstream Profile Descriptors(DPDs) from the CMTS and begin using the channels assigned to themat registration. The DPDs contain parameters of the downstream profilesand are unique to every profile.Using the assignment information sent to it by the PMA, the CMTSthen assigns to every CM one or more profiles. The CMs then begin usingtheir respective profiles, and performance data can be gathered from the enddevices using the channel. After the profiles have been in use for some time,it would be helpful to analyze the performance of the current set of profilesto see whether they can/should be improved further to better suit the net-work conditions experienced by the devices. In other words, the PMA nowoptimizes the profiles to further improve the network performance. Stepsinvolved in the optimization are depicted in Figure 2.4 and are described asfollows.The optimization process begins with either the CMTS requesting thePMA to optimize a channel’s profiles or the PMA deciding to optimize theprofiles without any explicit request from the CMTS. The PMA first obtainsinformation about the downstream PHY layer, such as, the list of currentOFDM channels in use, the list of profiles of every OFDM channel, the list272.6. PMA System Operationof CMs using every OFDM channel, and the list of profiles used by everyCM in each channel.The PMA then initiates downstream tests on the current profiles to eval-uate their performance and the channel quality. This enables it to determinewhat changes may be necessary for it to incorporate in the profile definitionsof the channels. To this end, the PMA requests the CMTS for the OCD(OFDM Channel Descriptor) parameters, the DPD of every profile and theOPT information from each active CM - which includes the RxMER, theSNR margin, codeword statistics, and the Next Codeword Pointer (NCP)statistics corresponding to every subcarrier. Alternatively, the PMA canalso obtain the RxMER values from the PNM data server to which CMsand CMTS upload their PNM files. The PMA may also require additionalinformation such as the FEC statistics, packet counts, the profile trafficstatistics (e.g. transmitted byte counts, FEC uncorrectables) etc.The PMA next uses its CM grouping and profile optimization algorithmto calculate the new optimum profile definitions based on the above obtainedmetrics. The profile optimization algorithm calculates the optimum profilesbased on the vendor-specified performance objective of the HFC system.The PMA then configures the CMTS with the new profile definitions.The PMA also communicates to the CMTS the assignment of the CMs tothe new downstream profiles.The PMA next manages the process of switching over to the new profiles.However, prior to doing this, it is important for the PMA to conduct sometesting of the new profiles and validate them. As mentioned earlier, theCMTS can support only a maximum of 16 profiles at a time. Therefore, if282.6. PMA System Operationthe CMTS is currently using all 16 profiles, it may need to free up a fewcurrent profiles so that it can test the new profiles. To do this, the PMAasks the CMTS to move the CMs currently using the particular profilesthat are to be deleted to other profiles. If the CMTS cannot do this, thePMA should flag this and discontinue the profile optimization process. Oncethe CMs of the older profiles have been moved, the PMA asks the CMTSto delete these now-unused profiles. For every new profile, the PMA thenrequests the CMTS to conduct OPT measurements with a CM that willpotentially use the profile. The PMA then compares the results with theinitial channel performance results. Based on this comparison the PMAmay decide to leave the older profile definitions unchanged, or it may deletethe older profile from the set of profiles configured for the CMTS. In thelatter case, where the testing of the new profile is favorable, the PMA thenassigns the CM to the profile, communicates this assignment to the CMTSand moves on to the next CM. As an alternative to the above test-and-assignstep, the PMA can also first assign the CMs to the profiles and then performtesting.Once all the CMs of the first new optimum profile have been moved tothe new profile, the PMA can repeat the above process for the remainingnew profiles.Finally, as mentioned in the previous step, if the PMA needs to removea particular profile from the CMTS, it has the option of deleting it from thelist of active profiles.292.7. DOCSIS 3.1 PHY-MAC Convergence Layer2.6.3 FallbackThere may arise a scenario where a CM that has been operating on acertain profile may begin to experience errors on that profile. When theCMTS detects this issue, it may/should take steps to move the CM to adifferent suitable profile.The PMA might have “backup” profiles for the particular CM in theprofiles-to-CMs assignment. In that case, the CMTS could move the CM toits “backup” profile. Otherwise, the CMTS can move the CM to Profile Aor to any other profile that it deems suitable and that will work for the CM.Following this, the CMTS will request the PMA to create a profile forthis particular CM. In response, the PMA requests information about theCM and the channel on which it operates. The PMA may also requestinformation about the CM’s traffic statistics, PNM data etc. Furthermore,it may also analyze the history of its previous assignments for the CM. Basedon all of this information, the PMA may decide to leave the CM where it is,choose a different profile for the CM from among the currently configuredprofiles, or create a new profile for the CM and possibly move other CMs toit. The PMA accomplishes the above by following the steps outlined in theworkflow described in the previous subsection 2.6.2.2.7 DOCSIS 3.1 PHY-MAC Convergence LayerThe PHY-MAC convergence layer in DOCSIS 3.1 plays an integral rolein mapping data into the different bit loading profiles. This section describesthe operation of the downstream convergence layer and its association with302.7. DOCSIS 3.1 PHY-MAC Convergence Layerthe PHY and MAC layers. Figure 3.2 illustrates an example implementationfrom the DOCSIS 3.1 MAC standard [4].At the routing layer of the CMTS, the forwarding engine forwards in-coming CM data packets to the MAC layer. The MAC layer then per-forms per-user-rate-shaping, aggregate-per-channel-rate-shaping and otherQoS operations on the data packets. The MAC layer rate shapes the packetflow to the size of the OFDM channel to ensure that they will fit into thechannel. Depending upon the profile a CM is using, data packets destinedto that CM receive a tag that indicates the profile to which the packetsbelong. The information about which profile a packet belongs to is storedin a lookup table that is located at the forwarding engine or at the DOCSISQoS engine.Next, the packets along with their profile tags are processed by the con-vergence layer. The convergence layer has collection buffers for each profile;and the incoming data packets are sorted into these buffers depending upontheir profile tags. The convergence layer buffers are shallow buffers thatcan hold only a few packets at a time. Since the MAC layer has alreadyrate shaped the packet flow, the buffers can afford to be shallow and do notoverflow.The packets from the profile buffers are then mapped into FEC code-words by the codeword builder. The same profile is used for one codeword,i.e., a codeword can contain the packets of only one profile. In other words,the active profile can be changed only at the codeword boundaries. Duringthe mapping process, if there are no packets available at a profile buffer,the codeword builder can insert a stuffing pattern of 0xFF bytes into the312.7. DOCSIS 3.1 PHY-MAC Convergence Layercodeword.The codeword builder is also responsible for multiplexing the FEC code-words. DOCSIS 3.1 does not specify a scheduling algorithm to be usedfor the downstream scheduler and the codeword builder has the freedomto schedule the codewords in any manner it deems appropriate. Since theMAC layer rate shapes the flow of the packets prior to their arrival at thebuffers, the codeword builder is not concerned with allocating bandwidth tothe profiles. Rather, the codeword builder schedules the codewords with theobjective of maintaining the latency budgets. In this thesis, we consider fourdifferent scheduling mechanisms that may be used by the codeword builderand we describe them briefly as follows:• Uniform scheduling: This is the most basic scheduling scheme,where the profiles’ codewords are transmitted sequentially in a roundrobin approach. The same time-bandwidth is allocated to every profileand the codeword builder services the profiles one after another.• Maximum capacity scheduling: In this scheme, the codewordbuilder targets to maximize the system capacity, and thus allocateshigher bandwidth to profiles with high bit loading, and inversely lowerbandwidth for low-capacity profiles.• Maximum fairness scheduling: Under this scheme, the objectiveis to ensure the maximum possible fairness between the profiles interms of data rate capacity. Thus, the codeword builder favors thelower capacity profiles and gives them higher bandwidth to ensurethey achieve rate capacities equal to or close to that of high capacity322.8. Poisson Processprofiles.• CM-density-aware scheduling: Under this scheme, the codewordbuilder favors profiles that have more CMs assigned to them, andallocates higher bandwidth to them in order to accommodate theirtraffic.2.8 Poisson ProcessA Poisson process is a simple random process that models the times atwhich arrivals enter a system. It has wide applications in many fields suchas in astronomy [21], ecology [22], geology [23] etc.A Poisson process can be considered as a collection of Poisson randomvariables. We first describe the Poisson random variable and its distribution,following which we present some properties of the Poisson process.2.8.1 Poisson Random VariableA discrete random variable N describing the number of arrivals in timeT is said to be a Poisson random variable with parameter α if its ProbabilityMass Function (PMF) is given by [24], [25]:PN (k) =αke−αk!. (2.1)The mean of N which denotes the average number of arrivals in time Tis given by α, and PN (k) denotes the probability of having k arrivals in timeT . The Cumulative Distribution Function (CDF) of the Poisson random332.8. Poisson Processvariable is given by [26]:FN (k) = e−αbkc∑i=0αii!, (2.2)which denotes the probability that N is less than or equal to k, i.e., theprobability that there are k or less than k arrivals in time T .The variance of the Poisson random variable is the same as its mean,i.e., V AR[N ] = E[N ] = α.2.8.2 Properties of the Poisson ProcessA collection of random variables N(t) : t ∈ [0,∞) indexed by time t iscalled a continuous-time random process. The random process N(t) is calleda Poisson process if it satisfies the following properties:• For all t > 0, the process N(t) takes a non-negative integer value, (i.e.,0,1,2,3,...), with N(0)=0.• The increment N(t+ s)−N(t) is always a positive value.• The increments N(t1), N(t2)−N(t1), N(t3)−N(t2), ... are indepen-dent of each other for all 0 < t1 < t2 < t3 < ... < tn−1 < tn.• The distribution of the increment N(t+ s)−N(t) is dependent on thevalue s > 0, and is independent of t > 0.In this thesis, we model the data arrival process of the system’s CMs asa Poisson random process.342.9. Orthogonal Frequency Division Multiplexing2.9 Orthogonal Frequency Division MultiplexingOFDM is a special form of the Frequency Division Multiplexing (FDM)modulation technique. In FDM systems, data transmission typically takesplace through multiple Radio Frequency (RF) carriers over the same trans-mission medium at the same time. This is achieved by dividing the availablespectrum into wide channel slots, each with a particular carrier frequency.Every RF signal is assigned to a slot, operating on a particular carrier fre-quency. The carriers are separated from each other by small guard bands.Since no information can be transmitted over these guard bands, the use ofsuch bands results in the waste of valuable spectrum.In contrast, OFDM uses a large number of narrowband subcarriers whichare orthogonal to each other. The orthogonality is achieved by selecting thespacing between the subcarriers to be the reciprocal of the symbol period.This orthogonality between the subcarriers not only allows the removal ofguard bands but also allows the subcarriers to overlap each other, thuseffecting high spectrum efficiency. Every such narrowband subcarrier inOFDM carries a small percentage of the total data payload at a very lowdata rate. The aggregate of the data rates of all the subcarriers comprisesthe total payload of the OFDM channel.The orthogonality between the subcarriers allows the allocation of differ-ent number of bits, or “bit loading” on the subcarriers. This per-subcarrierbit loading can be allocated as a function of the SNR on the subcarrier. Inother words, OFDM allows variable and adaptive bit allocation in the datatransmission.352.9. Orthogonal Frequency Division MultiplexingThe most distinct advantages of OFDM are with respect to its resilienceto interference and degraded channel conditions. Due to its use of very nar-row subcarriers, OFDM can adapt to degraded channel conditions withoutrequiring complex equalization at the receiver. For example, during micro-reflections that can cause amplitude ripple or standing waves in the coaxialmedium, a narrowband OFDM subcarrier only experiences a small portionof the ripple. The standing waves affect only the amplitude of few subcarri-ers of the entire OFDM signal, which can be easily fixed. This is in contrastto FDM used by older DOCSIS systems. In such systems, a channel maybe 6 MHz or 8 MHz wide, containing a single carrier that uses QAM. Forsuch systems, standing waves would adversely affect the entire widebandchannel. Similarly in the case of interference, a narrowband ingressor wouldaffect only a few narrowband subcarriers of the composite OFDM signal.FEC mechanisms would most likely be able to compensate for the affectedsubcarriers, or the OFDM transmitter can disable few subcarriers in theregion of interference. On the other hand, in older DOCSIS systems usingFDM, an interferer would take out the entire wideband channel.In spite of its multiple benefits, OFDM does have a few disadvantages.These include the frequency and clock synchronization errors that affect theOFDM subcarriers. Additionally, OFDM suffers from high peak-to-average-power-ratio (PAPR). However, it must be noted that a spectrum of manysingle carrier-QAM (SC-QAM) signals also has high PAPR. Additionally,OFDM uses Cyclic Prefixes (CP) to maintain orthogonality between thesubcarriers. The use of CPs somewhat reduces OFDM’s high spectrumefficiency.362.9. Orthogonal Frequency Division MultiplexingFigure 2.1: HFC network architecture.372.9. Orthogonal Frequency Division MultiplexingFigure 2.2: DOCSIS 3.1 downstream OFDM channel.382.9. Orthogonal Frequency Division MultiplexingFigure 2.3: PMA network architecture.392.9. Orthogonal Frequency Division MultiplexingFigure 2.4: PMA downstream profile optimization workflow.402.9. Orthogonal Frequency Division MultiplexingFigure 2.5: DOCSIS 3.1 PHY-MAC convergence layer (CL).41Chapter 3Profile Optimization for LowData Rate ApplicationsIn this chapter, we optimize the profiles of an asymptotic HFC systemin which all the end users use relatively low data rate applications. Conse-quently, the data arrival rates of the CMs are significantly lower than theirrespective channel bit loading capacities. This allows us to assume thatregardless of how the CMs are grouped into profiles, the total data arrivalrate of every profile is always less than the respective channel capacity of theprofile. Thus, at every time slot, all of the data that arrives at the collec-tion buffer of a given profile is immediately sent, (i.e., there is no remainderunsent data in the collection buffers).For such a system, we solve the CM grouping and profile design problemwith the goal of minimizing the total average data transmission time of thesystem. We achieve this by taking into account not only the CMs’ channelSNRs but also their data arrival rates when grouping them into profiles. Weformulate the CM grouping problem as an integer (binary) programmingproblem, and we propose an analytically optimal solution to solve it.Comparing our traffic-aware approach with a non-traffic-aware approach423.1. System Modelfrom the literature, namely CoPA in [13], we demonstrate that our approachyields significant gains in reducing the average system transmission timeby accounting for the CM data arrival rates in the profile design problem.Specifically, we study the effect of heterogeneity in the arrival rates of theCMs; and we demonstrate that the benefits of our approach increase withincreasing heterogeneity in the CMs’ traffic patterns. We also study theeffects of the allowed number of profiles in the system and we show that forany approach, whether our traffic-aware algorithm or CoPA, greater gainsare achieved with a higher allowed number of system profiles.3.1 System ModelConsider a CMTS that is serving K CMs in the downstream over asingle OFDM channel of bandwidth B. The channel comprises N orthogonalsubcarriers for data transmission. The downstream supports different M -QAM modulation orders across the subcarriers. The maximum allowednumber of profiles in the CMTS is denoted by L.The PMA uses periodically collected information about the actually re-alized data arrival rates of each CM to predict every CM’s average dataarrival rates in the period of interest. It should be noted that the data ar-rival prediction approach is out of the scope of this thesis. Several worksin the literature have focused on traffic prediction [27, 28]. We assume thatthe data arrival of each CM follows an independent PPP. We denote theestimated average arrival rate of the k-th CM as λ¯(c)k . We assume λ¯(c)k tobe perfectly estimated and constant for the period of the profile usage. For433.1. System Modelthis scenario, where the arrival rate of every CM is less than its channelcapacity, we can state the following:λ(c)k (t) << RsN∑n=1bk,n, ∀k, ∀t, (3.1)where, λ(c)k (t) is the actual realization of the data arrival of CM k at timeinstant t. The variable bk,n denotes the maximum bit loading capability ofCM k over subcarrier n, which is determined as a function of the SNR ofCM k over subcarrier n, the required bit-error rate, (i.e., the bit loading ofthe highest modulation that can be decoded within the required bit-errorrate), and the symbol rate denoted by Rs. It should be noted that in thisthesis, we use the terms “spectrum efficiency” and “bit loading capacity”interchangeably.Finally, we denote the time period of interest during which the profilesremain unchanged by T , and we also assume that the channels’ SNRs re-main constant over T . We note that this period is usually relatively long(in the order of minutes) as compared to network latency (in the order ofmilliseconds). Thus, scheduling and latency constraints can be assumed tonot have an effect on the total communication time we are computing. Inaddition, we assume unlimited buffers and ignore the effect of overhead.The novelty of the above presented system model is that the data trafficof the CMs (in addition to their channel SNRs) are accounted for in the pro-file optimization. For this reason, the system model assumes the collectionof information about the data arrival rates of the CMs. This is in contrastto previous works in the literature that exploited information about only443.2. Problem Formulationthe CMs’ channel SNRs to optimize the system profiles.3.2 Problem FormulationOur objective is to find the set of profiles which will minimize the averagetotal transmission time of the CMs’ data in the HFC network. The task isthen to determine the best CMs’ grouping that minimizes our objectivefunction by taking into account the CMs’ traffic and channel conditions.Mathematically, the optimization problem can be written as follows:minimize{ak,l, ∀k, l}E [T ] (3.2a)subject toL∑l=1ak,l = 1, ∀k, (3.2b)ak,l ∈ {0, 1}, ∀k, l, (3.2c)where ak,l is the CMs-to-profiles assignment index, (i.e., ak,l = 1 if theCM k is assigned to profile l, otherwise ak,l = 0), T denotes the totaltransmission time for all the CMs’ data arriving in the time period T , andE [.] denotes the expectation operator.We derive the expression of the average transmission time E [T ] in thenext section.453.3. Proposed Solution3.3 Proposed SolutionIn this section, we propose an optimal solution to the formulated profileoptimization problem. We derive the expression of the average transmissiontime of the HFC system, and we present the derivation as follows.3.3.1 Derivation of the Total Average Data TransmissionTime of the HFC SystemUsing the assumption of non consideration of buffer limits and schedulerconstraints on the data transmission time, we can express the total time fordata transmission as the sum of the per profile transmission time as follows:T =L∑l=1T (p)l =L∑l=1∫ T0D(p)l (t)C(p)ldt, (3.3)where D(p)l (t) is the total data arrival of the profile l at instant t. Sinceall of the data that arrives at the buffer of profile l at time instant t isimmediately sent, D(p)l (t) is also the total data being transmitted by profilel in time instant t. The variable C(p)l is the sum rate capacity of profile l.These parameters can be written as follows:D(p)l (t) =K∑k=1ak,lλ(c)k (t), (3.4)and463.3. Proposed SolutionC(p)l = RsN∑n=1mink|ak,l=1{b(n)k}. (3.5)Then, the objective function in (3.2a) is written asE [T ] = EL∑l=1∫ T0K∑k=1ak,l λ(c)k (t)dtRsN∑n=1mink|ak,l=1{b(n)k} . (3.6)Recalling that the average data arrival rate for the k-th CM is λ¯(c)k , theaverage transmission time can be deduced asE [T ] = TRsL∑l=1K∑k=1ak,l λ¯(c)kN∑n=1mink|ak,l=1{b(n)k} . (3.7)We thus show that, under the assumptions in our system model, theaverage system transmission time can be written as a function of only theCMs’ average data arrival rates, the CMs’ bit loading capabilities, and theCMs’ assignment to profiles. This expression allows us to develop a practicalprofile design algorithm that only requires knowledge of the CMs’ averagedata arrival rates, which is practically feasible.3.3.2 Traffic Aware Profile AssignmentAs mentioned earlier, the problem presented in Eq. (3.2) is an integerprogramming problem. In this section, we use the optimal solution proposed473.3. Proposed Solutionin the previous subsection to introduce a traffic-aware heuristic algorithmcalled Traffic Aware Profile Assignment (TAPA). The TAPA algorithm re-quires knowledge of only the average data arrival rates of the CMs, the bitloading vectors of the CMs, and the maximum number of profiles L as input.The bit loading vector of a particular CM k is the vector bk ∈ R1×N whichdescribes the maximum bit loading capability of CM k across each of the Nsubcarriers.The algorithm starts by randomly selecting L CMs out of the total KCMs in the system. A dedicated profile is initially constructed for each ofthese L CMs. Each of the remaining CMs are then assigned successivelyto profiles that minimize the system’s objective function, as expressed byEq. (3.2a). This is done by first considering each CM one by one, assign-ing the CM under consideration to every profile, and then evaluating theobtained performance for the CM’s assignment to every profile using theaverage data arrival rate of the CM and its respective bit loading capacity.The CM is assigned to that profile that minimizes Eq. (3.2a). This greedyprocedure is repeated for all the CMs in the system until they all have beenassigned to one of the L profiles.In the second step, the initial assignment solution is further improved.The algorithm iteratively searches until convergence for a better profile as-signment that will further improve the objective function value for everyCM. Specifically, at every iteration, the CMs are considered one by one. Asearch of the best possible new profile assignment for the CM under consid-eration that decreases the expected transmission time (3.2a) is performed.The profile that results in the best new objective function value is assigned483.4. Performance Analysis of TAPAto the CM. After re-assigning all CMs, the process is repeated until theobjective can not be further improved and the profile assignment remainsconstant. In Fig. 3.5, we present a pseudo-code of the proposed profileassignment approach.3.4 Performance Analysis of TAPAUnless mentioned otherwise, in the following we consider a system withK = 100 CMs. The OFDM channel is composed of N = 1000 active sub-carriers with 50 KHz spacing. We assume that the average SNR across theCMs is normally distributed with mean µ = 36.42 dB and standard devia-tion σ = 1.57 dB. Such an assumption follows the studies of cable multiplesystem operators (MSOs), which concludes that there would be an averageof 8 dB variation between the SNRs of different CMs [29]. Additionally, weassume that the SNR per subcarrier of each CM is normally distributed withmean equal to the average SNR of that CM and a standard deviation of σ.We consider all the supported constellations of DOCSIS 3.1, (i.e., all theM -QAM constellations for M up to to 4096: 4-QAM, 16-QAM, 64-QAM,128-QAM, 256-QAM, 512-QAM, 1024-QAM, 2048-QAM and 4096-QAM).This corresponds to possible bit loading values of {2, 4, 6, 7, 8, 9, 10, 11, 12},respectively.As mentioned earlier, we assume that the CMs’ data arrival follows in-dependent PPPs. We also assume that based on their average data arrivalrates, the CMs can be grouped into a number of different traffic patterns.In other words, the CMs’ average arrival rates are assumed to be accurately493.4. Performance Analysis of TAPApredicted using a classification algorithm that assigns each CM to one of thesystem’s traffic patterns.We denote the number of traffic patterns in the system by I. The pa-rameter I provides a measure of the degree of heterogeneity in the CMs’data arrival rates. All the CMs in a particular traffic pattern have the sameaverage data arrival rate. The average data arrival rate of traffic pattern i(or more accurately, the average data arrival rate of all the CMs in trafficpattern i) is denoted by λ¯(t)i and is defined as follows:λ¯(t)i = βi−1λ¯(t)0 ,∀i ∈ {1, ..., I}; (3.8)where β is the multiplication factor between the successive traffic pat-terns’ arrival rates. The variable λ¯(t)0 is the average arrival rate of the trafficpattern with the lowest rate. It is chosen in such a way so as to ensurethat the average per-traffic-pattern arrival rate is always the same, regard-less of the number of traffic patterns I in the system. This ensures a faircomparison when comparing our results across different values of I.The variable λ¯(t)0 is given by:λ¯(t)0 =νLIC¯(c)(1− β)K(1− βI) , (3.9)where ν is a ratio between the average arrival rates of the CMs and the503.4. Performance Analysis of TAPAchannel’s capacity, and it can be chosen as follows:ν =1, General Scenario103, Very High Data Rate Applications10−3, Very Low Data Rate Applications.(3.10)The variable ν is introduced to account for the different traffic scenar-ios that we consider in this thesis. To enforce the general scenario, wherethe per-profile data arrival is on average equal to the per-profile capacity,the value of ν is set to 1. To enforce the asymptotic scenario where theper-profile data arrival is always greater than the per-profile capacity, thevalue of ν is set to a sufficiently high value of 103. Similarly, for the otherasymptotic case where the per-profile data arrival is always lower than theper-profile capacity, ν is set to a sufficiently low value of 10−3. It was verifiedthrough simulations that the general and asymptotic values of ν enforcedthe respective scenarios. In this chapter, we consider the case where theend users only use very low data rate applications for the greater part ofthe time, and the arrival rates of the profiles are much lesser than their bitloading capacities. Accordingly, we set ν to 10−3.The variable C¯(c) is the per-CM bit loading capacity averaged over allthe CMs in the system, and is given by:C¯(c) =1KK∑k=1RsN∑n=1{bk,n}. (3.11)The variable Rs denotes the symbol rate and it is obtained as the reciprocal513.4. Performance Analysis of TAPAof the FFT symbol duration which is set as 20 µs for the 50 KHz subcarrierspacing [30].As mentioned earlier, we compare the obtained performance of our TAPAalgorithm to that of one of the profile optimization algorithms in the liter-ature that does not consider the CMs’ traffic, namely the CoPA algorithmproposed in [13]. To that end, we compute the absolute and the relative dif-ference between the average system transmission times obtained using theproposed TAPA algorithm and that obtained using the CoPA algorithm, bysubtracting the former from the latter. Since the absolute and the percent-age differences are positive values, they represent the absolute and relativegain in transmission time reduction achieved by TAPA over the CoPA algo-rithm.We first consider a system consisting of two traffic patterns, (i.e., I =2). In Fig. 3.1, we plot the gain curves for such a system, and we vary thepercentage of CMs using each pattern. Furthermore, in plotting the curves,we also vary the value of the factor β. The two extremes of the figurerepresent a low percentage of CMs using one of the two patterns. Thisimplies a low degree of heterogeneity among the CMs in their traffic, since amajority of them are in the same traffic pattern. In contrast, the maximumheterogeneity among the CMs’ data arrival rates occurs when the CMs areuniformly distributed across the two patterns, (i.e., when the percentage ofCMs in each traffic pattern is around 50%).This heterogeneity is directly reflected in the absolute gain in transmis-sion time reduction achieved using our TAPA algorithm. It can be seenfrom Fig. 3.1 that, for all factors, as the heterogeneity in the arrival rates523.4. Performance Analysis of TAPAof the CMs increases, the absolute gain achieved by TAPA over CoPA alsoincreases, and it reaches a maximum value when the CMs are approximatelyequally distributed among the two patterns. In other words, TAPA yieldsthe highest absolute gain when the heterogeneity in the arrival rates of theCMs is the highest. This is because of the way in which TAPA works. Thealgorithm takes into account not only the CMs’ SNR capabilities, but alsothe traffic patterns of the CMs when grouping them into profiles. Whenthe CMs vary significantly from each other in their arrival rates, TAPA at-tempts to assign the CMs with high traffic to higher bit loading profiles andCMs with low traffic to lower bit loading profiles. This is in contrast toCoPA that would assign a CM with high traffic and low subcarrier SNR toa low bit loading profile, and thus cause the CM’s data transmission timeto increase. By assigning the CMs to profiles on the basis of their traffic,TAPA reduces the system’s average data transmission time as compared toCoPA.In other words, TAPA exploits the differences in the traffic patterns ofthe CMs to minimize the total average transmission time of the system.However, when the vast majority of the CMs have similar traffic, there areonly few such differences in their arrival rates that TAPA can exploit. Thescenario then becomes similar to CoPA; and TAPA groups the CMs on thebasis of their subcarrier SNR capabilities. Consequently, the absolute gainachieved by TAPA over CoPA declines. In fact, at the very extreme case,when all the CMs are either all using pattern 1 or pattern 2, TAPA yieldsexactly the same grouping solution as CoPA (based on only the subcarriers’SNRs) and thus provides no gain over it.533.4. Performance Analysis of TAPAWe now focus on the relative gain in Fig. 3.1, and it can be seen that asmore CMs have lower arrival rates, (i.e., as more CMs are in traffic pattern1), the relative gain increases. This can be explained by the normalizationrelative to the total average transmission time obtained using CoPA. As thetotal average transmission time obtained using CoPA decreases, the achievedgains become more precious. However, when the vast majority of the CMsuse traffic pattern 1 and the reduction in the absolute gain between CoPAand TAPA is more than the reduction in average transmission time obtainedwith CoPA, the relative gain also decreases. This can be seen for the casewhen the factor is 10. For this case, when the percentage of CMs exceeds80%, the relative gain declines.The gain achieved by TAPA not only depends on the variation amongthe CMs in their traffic but also on the amount by which their traffic (ordata arrival rates) vary from each other. As mentioned earlier, in our model,this amount is represented by the factor β. It can be seen from both theabsolute and relative gain curves that for a particular distribution of CMs,the gain achieved by TAPA increases with increase in this factor. This againconfirms that the benefits of the proposed approach increase with increasein heterogeneity of the CMs’ traffic. However, from an observation of therelative gain curves, it should be noted that the additional gain that isobtained when the factor β changes from 100 to 1000 is lesser than thatobtained when β jumps from 10 to 100. This indicates that although anincrease in factor leads to an increase in the gain of TAPA over CoPA, thegain does not increase linearly due to the channel’s capacity limit.So far, we have considered the special case of a system that contains543.4. Performance Analysis of TAPAonly 2 traffic patterns. In Fig. 3.2, we study the relative gain of TAPA overCoPA for a variable number of traffic patterns I. A high value of I indicateshigh variation among the CMs in their data arrival rates while a low valueof I indicates a low degree of variation. In Fig. 3.2, the x-axis denotes thenumber of traffic patterns in the system and we assume that for every valueof I, the CMs are uniformly distributed across the different traffic patterns.It can be observed from the figure that as the variation among the CMsin their data arrival rates increases, (i.e., as the number of different trafficpatterns in the system increases), the gain in transmission time reductionachieved by TAPA over CoPA also increases. In fact, as can be seen fromthe figure, gains of over 10% are achieved by TAPA over CoPA. It can thusbe concluded that the greater the variation among the CMs in their arrivalrates, the greater is the gain provided by TAPA over CoPA in reducing thesystem’s average transmission time.We next focus our attention to the performance of the TAPA algorithmin terms of the spectrum efficiency of the HFC system. Fig. 3.3 plots therelative difference between the total system spectrum efficiency obtainedusing CoPA and that obtained when using TAPA. This relative differencehighlights the loss in spectrum efficiency incurred by TAPA when comparedwith CoPA. As can be seen from this figure, the gains provided by TAPAin terms of transmission time reduction comes at the price of a spectrumefficiency loss. However, although our TAPA algorithm results in lower spec-trum efficiency, we believe it enhances system performance by prioritizinghighly demanding CMs in terms of traffic.We now compare the performance of TAPA with CoPA for a variable553.4. Performance Analysis of TAPAnumber of CMs and variable number of allowed profiles (P ). We performthe comparison for P ∈ {1, 4, 8, 16} and we vary the number of CMs in thesystem from 10 to 100. For every value of P , Fig. 3.4 shows the percentageadditional average transmission time incurred by the system relative to theaverage transmission time that can be obtained if the allowed number ofprofiles is unlimited, so as to allow every CM to use its own optimal profile.In other words, Fig. 3.4 shows the loss in transmission time incurred by bothTAPA and CoPA because of having to group a large number of CMs into asmall number of profiles.It can be seen in the figure that for a given number of CMs, as the numberof profiles in the system reduces, the loss in transmission time reductionincurred by both TAPA and CoPA increases. When the number of profilesin the system is one, TAPA and CoPA yield the same grouping solution, andboth algorithms incur a loss of almost 50% compared to the case when everyCM has its own profile. This indicates that reducing the number of allowedprofiles in the system reduces the performance of both TAPA and CoPA.However, the relative loss of TAPA is always lesser than that of CoPA. Inother words, TAPA performs better than CoPA in terms of transmissiontime reduction for any given number of profiles, which indicates that ourresults in Figs. 3.1 and 3.2 remain true for variable number of profiles.It can also be observed from Fig. 3.4 that for a given number of allowedprofiles, as the number of CMs in the system increases, the relative loss intransmission time reduction also increases. This is because, as the numberof CMs increases, the degree to which the system profiles can be customizedto the CMs’ traffic patterns and channel SNRs decreases. In other words,563.5. Summarygreater loss in transmission time reduction is incurred by both TAPA andCoPA due to having to group more CMs into a limited number of profiles.However, as mentioned earlier, the loss incurred by TAPA is always less thanthat incurred by CoPA.3.5 SummaryIn this chapter, we considered a HFC system in which the data arrivalrates of the CMs are significantly lower than their respective channel bitloading capacities. For this system, we designed the system profiles withthe goal of minimizing the system’s average data transmission time. Bytaking into account the CMs’ traffic in the profile optimization, our ap-proach yields significant gain over a non-traffic-aware approach from theliterature. Simulation results show that this gain increases with increase inheterogeneity of the CMs’ traffic. In other words, our results indicate thateven with simple grouping algorithms, sizable gain in system performanceis achieved by accounting for CM data traffic in the profiles’ optimization.Finally, we also showed that for both traffic-aware as well as non-traffic-aware grouping approaches, a multiple-profile-system yields better systemperformance than a single-profile-system.573.5. Summary0 20 40 60 80 100Percentage of CMs Using Traffic Pattern 1 (%)02468101214Relative Average Transmission Time Gain (%)00.511.522.53Absolute Average Transmission Time Gain (s)10-4Relative Gain, =10Relative Gain, =100Relative Gain, =1000Absolute Gain, =10Absolute Gain, =100Absolute Gain, =1000Figure 3.1: Absolute and relative transmission time gain of TAPA overCoPA for variable CMs’ distributions among two traffic patterns (I = 2).583.5. Summary1 2 3 4 5 6 7 8 9 10Number of Traffic Patterns (I)02468101214Gain in Transmission Time Reduction (%)TAPA, =10TAPA, =100TAPA, =1000=10=100 = 1000Figure 3.2: Relative transmission time gain of TAPA over CoPA with uni-formly distributed CMs among variable traffic patterns.593.5. Summary1 2 3 4 5 6 7 8 9 10Number of Traffic Patterns (I)024681012141618Relative Loss in Spectrum Efficiency (%) Relative Loss, =10Relative Loss, =100Relative Loss, =1000Figure 3.3: Relative spectrum efficiency loss of TAPA compared to CoPAwith uniformly distributed CMs among variable traffic patterns.603.5. Summary10 20 30 40 50 60 70 80 90 100K (Number of CMs)0102030405060Loss in Transmission Time Reduction (%)CoPATAPAP=4P=1P=8P=16P=500Figure 3.4: Loss in transmission time relative to the case where an indepen-dent profile is used for every CM.613.5. Summary1: INIT: Choose L CMs randomly:(k1, k2, . . . , kL) ∈ {1, ..,K}2: INIT: Assign each CM to a unique profile:∀l ∈ {1, .., L} : akl,l = 1, ∀k = kl3: repeat4: for each CM k := 1...K do5: for each profile l := 1...L do6: Assign CM k to profile l:ak,l = 1 and ak,l′ = 0, ∀l′ 6= l7: Compute objective function value of this assignment using (3.2a);8: end for9: Determine best profile l∗ for CM k: l∗ = arg minl T (k, l)10: Assign CM k to profile l∗:ak,l∗ = 1 and ak,l′ = 0, ∀l′ 6= l∗11: end for12: until no change in any ak,l =0Figure 3.5: Steps of the Traffic Aware Profile Assignment algorithm.62Chapter 4Profile Optimization for aGeneralized Traffic ScenarioWe have concluded in Chapter 3 that for a network where CMs havevery low data arrival rates, significant gain in reducing the system’s averagedata transmission time can be achieved if the profile optimization approachaccounts for the CMs’ data traffic. In this chapter, we extend the above workto a more general scenario where the sum of the data arrival rates of the CMsin a profile is sometimes greater than, and sometimes less than the profile’sbit loading capacity. For this scenario, we optimize the system profiles withthe goal of maximizing the total average system throughput. As we willshow, the general scenario introduces a challenge to the profile optimizationproblem which we address in our solution. We also consider four differentscheduling mechanisms that may be used by the codeword builder, and weanalyze the performance of our traffic-aware approach under these differentmechanisms. Finally, we study the performance of our approach under anasymptotic scenario where the arrival rates of the CMs are much higherthan their respective channel bit loading capacities. Our work and resultsdemonstrate that good throughput performance can be gained when the634.1. System ModelCMs of a HFC system are grouped on the basis of both their traffic andchannel conditions.4.1 System ModelThe system we consider in this chapter is almost similar to the onewe considered in Chapter 3. For the sake of convenience, in the followingdescription of the system model, we reiterate some features of the systemthat we have already mentioned in the previous chapter.As in Chapter 3, we consider a CMTS that is serving K CMs over a sin-gle OFDM channel that is of bandwidth B, and is composed of N orthogonalsubcarriers. We consider all the different M -QAM modulation orders acrossthe subcarriers. The maximum allowed number of profiles in the CMTS isdenoted by L. We assume that the data arrival of each CM follows an inde-pendent PPP, and that the PMA accurately predicts the distribution of theCMs’ arrival rates based on their historic traffic information. Accordingly,the average arrival rate of the k-th CM, which is denoted as λ¯(c)k , is perfectlyestimated and is assumed to be constant for the period of the profile usage.We denote this period of interest during which the channel SNR and thesystem profiles also remain unchanged by T . We also denote the maximumbit loading capability of a CM k over a subcarrier n as bk,n.Additionally, in this chapter, we assume that the arrival rate of everyprofile can sometimes be greater than and sometimes be lesser than therespective per-profile bit loading capacity. This adds an additional challengeto the profile optimization problem as the data arriving at a particular644.2. Problem Formulationinstant is not guaranteed to be sent immediately. In other words, at anyinstant, the data in each profile’s buffer depends on the arrived and sentdata of the previous time instants. We address this challenge in our solutionpresented in Section 4.3. Finally, we define the amount of data actuallytransmitted over a profile in a particular time slot as the throughput of thatprofile in that time slot. In this chapter, we design the system’s profileswith the goal of maximizing the system’s total average throughput. Thisapproach of optimizing the profiles with the goal of maximizing the system’saverage throughput is novel since previous profile optimization approachesin the literature have focused only on maximizing the profiles’ capacities.4.2 Problem FormulationOur goal is to optimize the HFC system’s profiles so as to maximize thetotal average throughput of the system. Our task is then to determine thebest grouping of the CMs that will maximize our objective function whiletaking into account the CMs’ average data arrival rates and channel SNRconditions. Mathematically, we formulate the optimization problem as theweighted sum of the per profile throughput as follows:maximize{ak,l, ∀k, l}E{L∑l=1ωl∫ T0D(p)l (t)dt}(4.1a)subject to D(p)l (t) ≤ C(p)l , ∀t, l (4.1b)D(p)l (t) ≤ λ(p)l (t), ∀t, l (4.1c)L∑l=1ak,l = 1, ∀k, (4.1d)654.2. Problem Formulationak,l ∈ {0, 1}, ∀k, l. (4.1e)The term D(p)l (t) is the total throughput of the profile l in time instant tand the variable ak,l is the CMs-to-profiles assignment index, (i.e., ak,l = 1if the CM k is assigned to profile l, and ak,l = 0 otherwise). Our goal isto find the best K × L ak,l assignment indices that maximize the objectivefunction (4.1a), in which E {.} denotes the expectation operator.The weights, denoted by ωl, can be set depending on the schedulingmechanism used by the downstream transmitter. Examples of possibleweight choices that we will consider in our simulations are as follows:ωl =ω˜lL∑l=1ω˜l, (4.2)with ω˜l =1, uniform schedulingC(p)l , maximum capacity scheduling1C(p)l, maximum fairness schedulingK∑k=1ak,l, CM-density-aware scheduling.(4.3)The variable C(p)l is the bit loading capacity of profile l and is given byC(p)l = RsN∑n=1mink|ak,l=1{bk,n}. (4.4)The variable λ(p)l (t) is the actual data arrival rate of the l-th profile, and664.3. Proposed Solutionit is written as the sum of the actually realized data arrival rates of theassigned CMs to this profile, as follows:λ(p)l (t) =K∑k=1ak,lλ(c)k (t). (4.5)Constraint (4.1b) ensures that the throughput of every profile at every timeinstant is always less than or equal to the capacity of the profile, and con-straint (4.1c) ensures that the per-profile throughput at every time instantis always less than or equal to the arrived data of the profile at every instant.Finally, Constraints (4.1d) and (4.1e) ensure that each CM is assigned toonly one profile.4.3 Proposed SolutionIn order to solve the above problem, we propose a suboptimal analyticexpression of the actual throughput of each profile at every time instant (de-noted by D(p)l (t)) as a function of the respective profile’s actual data arrivalrate and bit loading capacity. Taking into account the constraints (4.1b)and (4.1c), we propose to set D(p)l (t) as follows:D(p)l (t) = min[C(p)l ;λ(p)l (t)]. (4.6)From that, we are able to derive the expression of E{D(p)l (t)}as afunction of only the average data arrival information as follows.674.3. Proposed SolutionLemma 4.1.E{D(p)l (t)}= (1− ρl)× C(p)l + ρl × λ¯(p)l , (4.7)where the variable ρl denotes the probability that the actually arrived dataof profile l at every instant is less than the bit loading capacity of profile l,and it is written as:ρl = e−λ¯(p)l⌊C(p)l⌋∑i=0(λ¯(p)l )ii!, (4.8)where b.c denotes the floor function.Proof. From Eq. (4.6), D(p)l (t) can be written asD(p)l (t) =C(p)l , if C(p)l ≤ λ(p)l (t)λ(p)l (t), otherwise.(4.9)Taking the average, we obtain:E{D(p)l (t)}= (E{D(p)l (t)|C(p)l ≤ λ(p)l (t)})× P{C(p)l ≤ λ(p)l (t)}+ (E{D(p)l (t)|C(p)l ≥ λ(p)l (t)})× P{C(p)l ≥ λ(p)l (t)}= (E{C(p)l})× P{C(p)l ≤ λ(p)l (t)}+ (E{λ(p)l (t)})684.3. Proposed Solution× P{C(p)l ≥ λ(p)l (t)}= C(p)l × (1− ρl) + λ¯(p)l × ρl.where ρl , P{C(p)l ≥ λ(p)l (t)}is the probability that the actual data arrivalrate of profile l is less than the bit loading capacity of the profile. Since thedata arrival rate of profile l is written as the sum of the data arrival rates ofthe CMs assigned to profile l as in (4.5), and recalling that the arrival ratesof the CMs are independent and distributed according to the PPP, then foreach t, λ(p)l (t) is the sum of independent Poisson random variables. Thus,λ(p)l (t) is also a Poisson random variable where its mean is given by:λ¯(p)l =K∑k=1ak,lλ¯(c)k (4.10)Thus, ρl is deduced from the cumulative distribution function of the Poissonrandom variable and can be expressed as in (4.8).Therefore, we show that the objective function can be written as a func-tion of only the average data arrival rates of the CMs, their subcarrier bitloading capabilities, and their profile assignment indices. This formulationthen allows us to optimize the profiles using only the average arrival rates ofthe CMs and their subcarrier bit loading capacities. The profile optimizationproblem is then written as follows:Theorem 4.2. Given the expression in (4.6), the profile optimization prob-694.4. Results and Discussionlem (4.1) is reduced to:maximize{ak,l, ∀k, l}TL∑l=1ωl((1− ρl)× C(p)l + ρl × λ¯(p)l)(4.11a)subject toL∑l=1ak,l = 1, ∀k, (4.11b)ak,l ∈ {0, 1}, ∀k, l. (4.11c)Thus, similar to the objective function formulation in Chapter 3, weobtain here also an integer (binary) programming problem. We use theheuristic TAPA solution that we presented in Chapter 3 to optimize thesystem’s profiles. While in the previous chapter TAPA grouped the CMsusing the objective function expressed by Eq. (3.2a), in this chapter TAPAgroups the CMs using Eq. (4.11a) as the objective. Specifically, in theinitialization and update steps of TAPA, the algorithm heuristically assignsthe CMs to the different profiles with the objective of maximizing the averagesystem throughput, given by Eq. (4.11a).4.4 Results and DiscussionIn this section, we analyze the performance of our traffic-aware approachin maximizing the average throughput of a HFC system.For our performance analysis simulations, we use the same simulationparameters as in Chapter 3. However, since in this section we consider asystem where the arrival rates of the profiles are on average equal to theprofiles’ capacities, we choose the value of ν to be 1. Later in this section,704.4. Results and Discussionwe also study the case where the average arrival rates of the profiles arealways higher than their bit loading capacities. For that case, we choose thevalue of ν as 103.4.4.1 Optimality AnalysisIn this section, we study the optimality, feasibility and the complexityof our proposed solution. In Fig. 4.1, we compare the absolute averagesystem throughput obtained by the proposed TAPA algorithm that usesinformation about only the CMs’ average data arrival rates with the casewhen TAPA has future information about the CMs’ actually realized dataarrival rates. In addition, for the case when information about the actualdata arrival rates is available, we suppose that the system can dynamically,at every instant, construct new profiles tailored to these actual data rates.Thus, this represents an upper bound for the optimal solution of our profiledesign problem presented in Eq. (4.1).It can be seen from Fig. 4.1 that the sub-optimal solution provided by ourheuristic average-arrival-rates-based TAPA algorithm performs very close tothe upper bound. Since the optimal solution should provide lower through-put than the presented upper bound, it can be concluded that our algorithmprovides a solution close to the optimal solution. It should be noted that theobtained upper bound is not feasible in practice due to two reasons. Firstly,it uses future information of the CMs’ actual data arrival rates which isdifficult to obtain in practice. Secondly, it requires the system to constructnew profiles dynamically and at every instant which is not possible in DOC-SIS 3.1.714.4. Results and DiscussionStudying the two curves in Fig. 4.1 provides another insight. Sincethe actual-arrival-rates-based TAPA algorithm performs very similar to theaverage-arrival-rates-based TAPA algorithm, it can be inferred that there isonly little improvement in the throughput that can be achieved when theactually realized data arrival rates of the CMs are used to design the sys-tem profiles. Thus, TAPA performs well with knowledge of only the CMs’average data arrival rates, which can be easily obtained through predictionalgorithms. In other words, TAPA does not require information about theCMs’ actual data arrival rates.Regarding the complexity, it should be noted that while optimal ex-haustive search algorithms would have exponential complexity, our TAPAalgorithm has a complexity of the order of only O(KP ). Therefore, ourtraffic-based heuristic approach is an efficient solution to the profile designproblem, and it solves the optimization problem near-optimally given thepractical constraints of the DOCSIS 3.1 implementation. Furthermore, itachieves the above at significantly less computational complexity than opti-mal exhaustive search solutions.We now study the performance of our algorithm for different degrees ofheterogeneity in the the CMs’ traffic patterns, and under different down-stream scheduling mechanisms. We also study the performance of the al-gorithm under an asymptotic traffic scenario. Like in the previous chapter,for every scenario, we compare the obtained performance of TAPA to thatof the non-traffic-aware profile optimization algorithm, namely the CoPAalgorithm proposed in [13].724.4. Results and Discussion4.4.2 Performance AnalysisAs mentioned earlier, we are considering the generalized traffic scenariowhere the arrived data per profile can sometimes exceed the capacity of theprofile, and sometimes be less than the capacity of the profile. In otherwords, on average, the per-profile data arrival rate is equal to the per-profilebit loading capacity. For this scenario, we compare the average systemthroughput obtained by TAPA with that obtained by CoPA under severaldifferent scheduling mechanisms used by the codeword multiplexer.In Fig. 4.2, we consider the uniform scheduling scenario and plot theabsolute average system throughput of TAPA and CoPA, and the percentagethroughput gain achieved by TAPA over CoPA for a variable number oftraffic patterns.Observing the throughput curves of TAPA and CoPA in Fig. 4.2, it canbe seen that for a system with even the slightest degree of heterogeneity inthe CMs’ data arrival rates, TAPA provides a higher absolute average sys-tem throughput than CoPA. Furthermore, as the heterogeneity in the CMs’data arrival rates increases, the absolute throughput provided by TAPA alsoincreases while that of CoPA decreases. Accordingly, the relative through-put gain achieved by TAPA over CoPA increases almost linearly. In fact, fora system where there are 6 to 7 different traffic patterns, throughput gainsof over 15% are achieved by TAPA.TAPA is able to provide higher system throughput because it assignseach of the CMs to profiles that are best suited to their traffic conditions.In a system with a certain degree of heterogeneity in the CMs’ traffic pat-734.4. Results and Discussionterns, (i.e., for a certain non-zero value of I), TAPA accommodates the highdata rate demand of a high-traffic CM by assigning it to a high-capacityprofile, while satisfying the low data rate demand of a low-traffic CM byassigning it to a low-capacity profile. Customizing the profile definitionsto the CMs’ traffic patterns (in addition to their subcarrier SNRs) allowsTAPA to provide a high average system throughput. This is in contrast toCoPA that ignores the traffic patterns of the CMs and groups them solelyon the basis of their subcarrier SNRs. By disregarding the CMs’ traffic de-mands, CoPA can group a low-traffic CM into a high-capacity profile or ahigh-traffic CM into a low-capacity profile. This in turn causes CoPA toyield a lower average system throughput.When the variation in the CMs’ traffic increases, (i.e., when I increases),some CMs in the system have very high data arrival rates and some CMshave very low data arrival rates. Consequently, the benefit that is gained bygrouping the high-traffic CM into a high-capacity profile is higher for highvalues of I. For this reason, TAPA yields higher average system throughputwith greater variation in the CMs’ traffic. At the same time, when theheterogeneity in the CMs’ traffic is high, the loss that is incurred by groupingthe high-traffic CM into a low-capacity profile, and the inefficiency that isincurred by grouping the low-traffic CM into a high-capacity profile are alsomagnified. Consequently, as the heterogeneity in the data traffic of the CMsincreases, CoPA yields poorer throughput. For the above reasons, as thedifferences in the data traffic of the CMs increase, (i.e., when I increases), therelative throughput gain of our algorithm over CoPA progressively increases.It should be noted that when the vast majority of the CMs have similar744.4. Results and Discussiontraffic, the traffic heterogeneity among them is low, (i.e., I is low). Specif-ically, when all the CMs are in the same traffic pattern, (i.e., when I=1),there are no significant differences in the CMs’ data arrival rates. SinceTAPA groups the CMs by exploiting the differences in their traffic and theirsubcarrier SNRs, the absence of variation in the CMs’ traffic means thatTAPA now groups the CMs only on the basis of their subcarrier SNRs. Inother words, TAPA behaves like CoPA and consequently, for the case whenI=1, TAPA yields similar average system throughput as that of CoPA.We now focus our attention on the performance of TAPA and CoPAunder different scheduling mechanisms used by the codeword multiplexer.Figs. 4.3 and 4.4 plot the absolute average system throughput of TAPA andCoPA under the maximum capacity scheduling and the maximum fairnessscheduling schemes respectively. In Fig. 4.6, we plot the absolute aver-age per-CM throughput under the CM-density-aware scheduling schemes.Comparing these figures with the uniform scheduling case in Fig. 4.2, itis interesting to note that TAPA’s trend of yielding increasing throughputgains with increasing CM traffic heterogeneity is consistent across differentscheduling mechanisms. It may be noted that under the different schedulingschemes considered above, the performance of TAPA is slightly worse thanthat of CoPA for low degrees of CM traffic heterogeneity. This is becauseof the sub-optimality of the heuristic TAPA algorithm. However, it is in-teresting to see that despite this sub-optimality, TAPA still provides higheraverage system throughput than CoPA for moderate to high values of I.The CoPA algorithm aims to maximize the average per-CM spectrumefficiency, or equivalently the average per-CM bit loading capacity. Un-754.4. Results and Discussionder the CM-density-based scheduling scheme, TAPA essentially attemptsto maximize the average per-CM throughput. Therefore, for the purposeof comparison, we now provide a study of the performance of TAPA andCoPA under the CM-density-based scheduling scheme. Specifically, we con-sider the absolute average system throughput curves of TAPA and CoPA inFig. 4.6, and we compare these curves with the respective algorithms’ per-CM average system spectrum efficiency curves in Fig. 4.5. Comparing thecurves lends an interesting insight. It can be seen that while TAPA provideshigher throughput than CoPA for moderate to high degrees of heterogeneity,its spectrum efficiency is lower than that of CoPA for any degree of trafficheterogeneity, (i.e., for any value of I). In other words, CoPA yields low CMthroughput despite the fact that it enables the CMs to enjoy spectrum effi-ciencies higher than that provided by TAPA. This indicates that designingthe profiles with the goal of simply maximizing the CMs’ bit loading capaci-ties is not sufficient, as these profiles may not ensure a high CM throughput.Rather, designing the system profiles while taking into account the CM dataarrival rate is more effective in increasing the CM throughput even if suchprofiles do not yield the highest CM bit loading capacity.4.4.3 Asymptotic AnalysisIn this section, we consider the asymptotic scenario where the averageper-CM data arrival rate is much higher than the average per-CM bit loadingcapacity. Consequently, the average per-profile data arrival rate is muchgreater than the average per-profile bit loading capacity.While such a scenario should not occur in practice due to the rate-764.4. Results and Discussionshaping and QoS features of the DOCSIS MAC, it provides a useful illus-tration of the characteristics of the TAPA algorithm.Observing Eq. (4.6), it is clear that under this asymptotic scenario wherethe per-profile arrival rate is greater than the per-profile bit loading capacity,the TAPA algorithm attempts to maximize the average spectrum efficiencyof the system profiles. On the other hand, as mentioned earlier, the CoPAalgorithm constructs the profiles with the goal of maximizing the averagespectrum efficiency of the CMs. Therefore, for the purpose of comparison,in Fig. 4.6 we study the performance of TAPA and CoPA under a CM-density-based scheduler for the asymptotic scenario. In Fig. 4.6, we plotthe absolute average per-CM throughput obtained using TAPA and thatobtained using CoPA. As can be seen in the figure, TAPA and CoPA yieldthe exact same average per-CM throughput. Since the data arrival ratesof the CMs are much greater than their bit loading capacities, the averageper-CM throughput is capped by the average per-CM bit loading capacity.Consequently, the average per-CM throughput obtained by both TAPA andCoPA is equal to the average per-CM bit loading capacity.It must be noted that under this asymptotic scenario, the arrival rates ofthe CMs are always greater than their bit loading capacities regardless of thedegree of heterogeneity in their data traffic. This means that under the CM-density-based scheduler, TAPA groups the CMs with the goal of maximizingthe average per-CM spectrum efficiency regardless of the degree of the CMs’traffic heterogeneity. In other words, TAPA behaves like CoPA and groupsthe CMs only on the basis of their subcarrier SNRs, and consequently yieldsthe same grouping solution for any number of traffic patterns in the system.774.5. SummaryFor this reason, TAPA and CoPA yield the same average per-CM throughputfor all values of I. In other words, in the scenario where the average arrivalper-CM is greater than the average capacity per-CM, TAPA provides thesame performance as CoPA.4.5 SummaryIn this chapter, we considered a HFC system in which the data arrivalrate of every profile is on average equal to the bit loading capacity of theprofile. For this system, we designed the system profiles with the goal ofmaximizing the average system throughput. We proposed a suboptimal an-alytical solution to the profile optimization problem by expressing the totalaverage system throughput as a function of only the CMs’ average data ar-rival rates. By taking into account the traffic patterns of the CMs in the pro-file optimization, our approach yields significant gain in system throughputover a non-traffic-aware approach from the literature. Our results demon-strate that this throughput gain increases with increasing heterogeneity inthe CMs’ traffic patterns. Furthermore, our results show that the gainachieved by TAPA is consistent across different scheduling mechanisms thatmay be used by a codeword builder. Finally, our results demonstrate thatwhile grouping the CMs on the basis of solely their channel conditions canmaximize their bit loading capacities, it does not ensure that their through-put is also being maximized. Rather, grouping the CMs on the basis of theirtraffic conditions can improve the CMs’ throughput performance.784.5. Summary1 2 3 4 5 6 7 8 9 10I (Number of Traffic Patterns)4.34.44.54.64.74.84.955.1Total System Throughput (bits/sec)108TAPA, Uniform Scheduling Using Average Arrival RatesTAPA, Uniform Scheduling Using Actually Realized Arrival RatesFigure 4.1: Throughput of TAPA with average CM arrival rates and thatwith actual arrival rates, with β = 10.794.5. Summary1 2 3 4 5 6 7 8 9 10I (Number of Traffic Patterns)-50510152025Relative Gain (%)3.844.24.44.64.85Absolute System Throughput (bits/sec)108Relative Gain - TAPA, Uniform SchedulingAbsolute Throughput - CoPA, Uniform SchedulingAbsolute Throughput - TAPA, Uniform SchedulingFigure 4.2: Absolute throughput of TAPA and CoPA, and percentagethroughput gain achieved by TAPA over CoPA under a uniform schedulerwith β = 10.804.5. Summary1 2 3 4 5 6 7 8 9 10I (Number of Traffic Patterns)-50510152025Relative Gain (%)44.24.44.64.855.2Absolute System Throughput (bits/sec)108Relative Gain - TAPA, Maximum Capacity SchedulingAbsolute Throughput - CoPA, Maximum Capacity SchedulingAbsolute Throughput - TAPA, Maximum Capacity SchedulingFigure 4.3: Absolute throughput of TAPA and CoPA, and percentagethroughput gain achieved by TAPA over CoPA under a maximum capacityscheduler, with β = 10.814.5. Summary1 2 3 4 5 6 7 8 9 10I (Number of Traffic Patterns)-50510152025Relative Gain (%)44.24.44.64.855.2Absolute System Throughput (bits/sec)108Relative Gain - TAPA, Maximum Fairness SchedulingAbsolute Throughput - CoPA, Maximum Fairness SchedulingAbsolute Throughput - TAPA, Maximum Fairness SchedulingFigure 4.4: Absolute throughput of TAPA and CoPA, and percentagethroughput gain achieved by TAPA over CoPA under a maximum fairnessscheduler, with β = 10.824.5. Summary1 2 3 4 5 6 7 8 9 10I (Number of Traffic Patterns)4.354.44.454.54.554.64.65Average Spectrum Efficiency (bits)1010 CoPATAPAFigure 4.5: Average per-CM spectrum efficiency of TAPA and CoPA, undera CM-density-based scheduler with β = 10.834.5. Summary1 2 3 4 5 6 7 8 9 10I (Number of Traffic Patterns)-10-505101520Relative Gain (%)44.14.24.34.44.54.64.7Absolute System Throughput (bits/sec)108Relative Gain - TAPA, General ScenarioAbsolute Throughput - CoPA, General ScenarioAbsolute Throughput - TAPA, General ScenarioAbsolute Throughput - CoPA, Asymptotic ScenarioAbsolute Throughput -TAPA, Asymptotic ScenarioFigure 4.6: Average per-CM throughput of TAPA and CoPA, and percent-age throughput gain achieved by TAPA over CoPA, for the general scenarioand for the asymptotic scenario, under a CM-density-aware scheduler withβ = 10.84Chapter 5ConclusionsIn this chapter, we summarize the contributions of this thesis, and men-tion some future work related to profile optimization in DOCSIS 3.1 systems.5.1 Summary of ContributionsThe work in this thesis addresses the problem of profile optimization inDOCSIS 3.1 networks. In this work, we introduce a low-complexity profiledesign approach that groups the CMs of a HFC system on the basis of boththeir data arrival rates and channel SNRs. By accounting for CM traffic inaddition to CM channel SNR, our algorithm yields significant gain in max-imizing average system throughput when compared to a non-traffic-awareprofile design algorithm in the literature. For the asymptotic scenario wherethe CMs have very low data arrival rates, our algorithm yields significantgain in minimizing the HFC system’s average data transmission time. Weshow that these gains increase with higher degrees of heterogeneity in thetraffic patterns of the CMs. We also show that the throughput gain of ourapproach is consistent across different scheduling mechanisms that may beused by a codeword builder. Furthermore, when accounting for CM traffic,our algorithm uses information about only the average data arrival rates of855.2. Future Workthe CMs. In other words, it does not require future information about theactually realized CM arrival rates which is challenging to obtain in prac-tice. Finally, our work highlights the benefits of adaptive bit loading thatis enabled by the introduction of profiles in DOCSIS 3.1. We show thatwith both traffic-aware and non-traffic-aware algorithms, a multiple-profilesystem yields better performance than a single-profile system. Our resultsshow that by taking into account the CM traffic when optimizing the profilesof a HFC system, significant gain in system performance can be obtained.Our results thus motivate further work into the development of traffic-basedCM grouping and profile design algorithms. Such traffic-aware profile opti-mization algorithms can be implemented by DOCSIS network operators toimprove the throughput of their users.5.2 Future Work• Learning Based Profile Optimization: Optimizing the profileswhile accounting for both CMs’ traffic and the scheduler is essentialto ensure good system performance. In this work, we have assumedthat the scheduling mechanism used by the downstream transmitteris known to the PMA; and that the PMA uses this knowledge of thescheduler to optimize the system profiles. However, depending on theperformance objectives, different CMTSs may use different schedul-ing schemes. Furthermore, the scheduling scheme used by a givenCMTS may change over time depending on the variation in the CMs’applications requirement. Therefore, for a PMA that serves multiple865.2. Future WorkCMTSs, each of which may use different schedulers, which themselvesmay change over time, it is necessary to optimize the profiles with-out requiring a-priori information about the schedulers. An effectivesolution is to learn the behavior of the schedulers through machinelearning techniques, accurately predict the scheduling and use the re-sulting information for profile optimization. Such an approach will al-low dynamic optimization of profiles across multiple CMTS platforms,without requiring a-priori information about their schedulers. Usingmachine learning principles for scheduling prediction in DOCSIS 3.1profile optimization is thus an important area of investigation.• Virtualization and Software Defined Networking: In this the-sis, it can be seen that the growth in data rate demands of HFC usershas translated into requiring the CMTS to perform a myriad of com-plex control operations. In the future, it may be helpful to remove thecontrol plane of the CMTS to centralized servers so as to reduce thecomputational burden of the CMTS. Freeing the CMTS from its con-trol operations falls under the concept of Software Defined Networking(SDN), which can offer benefits to DOCSIS systems in terms of allow-ing the use of simpler hardware and reducing operational costs. Theimplementation of SDN in DOCSIS systems thus becomes an impor-tant area of investigation.87Bibliography[1] B. Hamzeh, M. Toy, Y. Fu, and J. Martin. DOCSIS 3.1: Scaling broad-band cable to gigabit speeds. IEEE Communications Magazine, 53(3):108–113, March 2015. ISSN 0163-6804. doi: 10.1109/MCOM.2015.7060490. → pages 1[2] A. Al-Banna and T. Cloonan. The spectral efficiency of DOCSIS3.1 systems, 2014. URL www.arris.com/globalassets/resources/white-papers/arris_spectral_efficiency_of_docsis_wp.pdf.Retrieved on 2018-08-31. → pages 1[3] Data-Over-Cable Service Interface Specifications (DOCSIS 3.1): Phys-ical Layer Specification, May 2017. URL https://apps.cablelabs.com/specification/CM-SP-PHYv3.1. Retrieved on 2018-01-15. →pages 1, 3, 15, 17, 24[4] Data-Over-Cable Service Interface Specifications (DOCSIS 3.1): MACand Upper Layer Protocols Interface Specification, May 2017. URLhttps://apps.cablelabs.com/specification/CM-SP-MULPIv3.1.Retrieved on 2018-01-15. → pages 1, 31[5] J. T. Chapman. The power of DOCSIS 3.1 down-88Bibliographystream profiles. In Proc. of Spring Technical Forum,2013. URL www.nctatechnicalpapers.com/Paper/2013/2013-the-power-of-docsis-3-1-downstream-profiles. Retrievedon 2016-11-15. → pages 2[6] A. P. Skelton, S. F. Holmgren, and D. C. Wood. The MITRE ca-blenet project. Technical report, RFC Editor, 1979. URL https://www.rfc-editor.org/ien/ien96.txt. Retrieved on 2018-08-25. →pages 2[7] Data-Over-Cable Service Interface Specifications (DOC-SIS 1.0): Radio Frequency Interface Specification, 1997.URL https://apps.cablelabs.com/specification/radio-frequency-interface-specification-3. Retrieved on2018-08-15. → pages 2[8] Data-Over-Cable Service Interface Specifications (DOC-SIS 1.1): Radio Frequency Interface Specification, 1999.URL https://apps.cablelabs.com/specification/radio-frequency-interface-specification. Retrieved on 2018-08-15. → pages 2[9] Data-Over-Cable Service Interface Specifications (DOC-SIS 2.0): Radio Frequency Interface Specification, 2001.URL https://apps.cablelabs.com/specification/radio-frequency-interface-specification-2. Retrieved on2018-08-15. → pages 289Bibliography[10] Data-Over-Cable Service Interface Specifications (DOCSIS 3.0): Phys-ical Layer Specification, 2006. URL https://apps.cablelabs.com/specification/CM-SP-PHYv3.0. Retrieved on 2018-08-15. → pages 3[11] C. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.→ pages 5[12] H. Mehmood, S. Rahman, and J. M. Cioffi. Bit loading profiles forhigh-speed data in DOCSIS 3.1. IEEE Communications Magazine, 53(3):114–120, March 2015. ISSN 0163-6804. doi: 10.1109/MCOM.2015.7060491. → pages 5, 13[13] H. Mehmood and J. Cioffi. User clustering for high-speed small cellbackhaul over coaxial cable. In Proc. of IEEE International Conferenceon Communication Workshop (ICC-Workshops), pages 216–221, June2015. doi: 10.1109/ICCW.2015.7247181. → pages 5, 43, 52, 72[14] F. D’Andreagiovanni and G. Caire. An unconventional clustering prob-lem: User service profile optimization. In Proc. of IEEE InternationalSymposium on Information Theory (ISIT), pages 855–859, July 2016.doi: 10.1109/ISIT.2016.7541420. → pages 6[15] G. White and K. Sundaresan. DOCSIS 3.1 profile management appli-cations and algorithms. In 2016 Spring Technical Forum Proceedings,2016. → pages 6[16] M. Ben Ghorbel, B. Berscheid, E. Bedeer, M. J. Hossain, C. Howlett,and J. Cheng. Principal component-based approach for profile opti-90Bibliographymization algorithms in DOCSIS 3.1. IEEE Transactions on Networkand Service Management, to appear. → pages 7[17] I. Jolliffe. Principal Component Analysis. John Wiley & Sons, Ltd,2014. ISBN 9781118445112. doi: 10.1002/9781118445112.stat06472.URL http://dx.doi.org/10.1002/9781118445112.stat06472. Re-trieved on 2018-08-31. → pages 7[18] DOCSIS 3.1 profile management application technical report. Technicalreport, Cable Television Laboratories, Inc., 2018. → pages 9, 21[19] R. G. Gallager. Low-Density Parity Check Codes. Cambridge MA:MITPress, 1963. → pages 17[20] Cable Modem Operations Support System Interface Specification,May 2017. URL https://apps.cablelabs.com/specification/CM-SP-CM-OSSIv3.1. Retrieved on 2018-08-31. → pages 25[21] G. J. Babu and E. D. Feigelson. Spatial point processes in astronomy.Journal of Statistical Planning and Inference, 50:311–326, 1996. →pages 33[22] H. Thompson. Spatial point processes, with applications to ecology.Biometrika, 42:102–115, 1955. → pages 33[23] C. B. Connor and B. E. Hill. Three nonhomogeneous poisson modelsfor the probability of basaltic volcanism: Application to the YuccaMountain region, Nevada. Journal of Geophysical Research: Solid Earth(1978-2012), 100:10107–10125, 1995. → pages 3391Bibliography[24] A. Papoulis. Probability, Random Variables, and Stochastic Processes.McGraw-Hill, 2nd edition, 1984. → pages 33[25] P. E. Pfeiffer and D. A. Schum. Introduction to Applied Probability.1973. → pages 33[26] N. L. Johnson, S. Kotz, and A. W. Kemp. Univariate Discrete Distri-butions. Wiley, 1993. ISBN 0-471-54897-9. → pages 34[27] R. Li, Z. Zhao, J. Zheng, C. Mei, Y. Cai, and H. Zhang. Thelearning and prediction of application-level traffic data in cellular net-works. IEEE Transactions on Wireless Communications, 16(6):3899–3912, June 2017. ISSN 1536-1276. doi: 10.1109/TWC.2017.2689772.→ pages 43[28] M. Celenk, T. Conley, J. Graham, and J. Willis. Anomaly prediction innetwork traffic using adaptive Wiener filtering and ARMA modeling. InProc. of IEEE International Conference on Systems, Man and Cyber-netics, pages 3548–3553, Oct 2008. doi: 10.1109/ICSMC.2008.4811848.→ pages 43[29] D. Urban. The case for multiple MCS. Technical report, P8023.bnEPoC PHY Task Force, 2012. → pages 49[30] K. Sundaresan. Accurately estimating D3.1 channel ca-pacity. In 2017 Fall Technical Forum, 2017. URLhttps://www.nctatechnicalpapers.com/Paper/2017/2017-accurately-estimating-d3-1-channel-capacity. Retrievedon 2018-08-31. → pages 5292
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On profile optimization in DOCSIS 3.1 networks exploiting...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On profile optimization in DOCSIS 3.1 networks exploiting traffic information Abedin, Sumayia 2018
pdf
Page Metadata
Item Metadata
Title | On profile optimization in DOCSIS 3.1 networks exploiting traffic information |
Creator |
Abedin, Sumayia |
Publisher | University of British Columbia |
Date Issued | 2018 |
Description | The latest release of the Data over Cable Service Interface Specification (DOCSIS), namely DOCSIS 3.1, has introduced the use of adaptive bit loading profiles. The optimal design of these profiles is critical for the overall performance of a Hybrid Fiber Coaxial (HFC) cable system. In this thesis, we introduce a low complexity profile design algorithm that maximizes the average throughput of a HFC system by grouping its cable modems (CMs) on the basis of both their downstream data arrival rates and channel signal-to-noise ratios (SNRs). Optimizing the profiles on the basis of both CM traffic and CM channel SNRs is challenging as these two criteria are somewhat contradictory. To account for the CMs' channel SNRs, CMs with similar SNR distributions should be grouped into the same profiles. However, to take into account the CMs' traffic, CMs with high data arrival rates should be grouped into profiles with higher bit loading capabilities, and CMs with lower data arrival rates should be grouped into profiles with lower bit loading capabilities.%, irrespective of their channel SNRs. In this thesis, we take into account these two contradictory criteria in the profile optimization problem, and we propose a sub-optimal solution to solve this problem. Performance analysis results of our algorithm show that accounting for both CM channel SNR and CM traffic can improve the average throughput of a HFC system. Furthermore, our approach accounts for the CMs' traffic without requiring future knowledge of their actually realized data arrival rates, which is difficult to obtain in practice. We also consider an asymptotic scenario, where the per-profile arrival rates (which is the sum of the arrival rates of all the CMs in a profile) is always guaranteed to be less than the respective per-profile bit loading capacities. For this case, our algorithm optimizes the system profiles with the objective of minimizing the system's total average data transmission time. We show that our proposed approach yields significantly high performance, particularly for scenarios with a high degree of heterogeneity in the CMs' traffic. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2018-11-05 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0373469 |
URI | http://hdl.handle.net/2429/67747 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical Engineering |
Affiliation |
Applied Science, Faculty of Engineering, School of (Okanagan) |
Degree Grantor | University of British Columbia |
GraduationDate | 2019-02 |
Campus |
UBCO |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2019_ February_Abedin_Sumayia.pdf [ 788.78kB ]
- Metadata
- JSON: 24-1.0373469.json
- JSON-LD: 24-1.0373469-ld.json
- RDF/XML (Pretty): 24-1.0373469-rdf.xml
- RDF/JSON: 24-1.0373469-rdf.json
- Turtle: 24-1.0373469-turtle.txt
- N-Triples: 24-1.0373469-rdf-ntriples.txt
- Original Record: 24-1.0373469-source.json
- Full Text
- 24-1.0373469-fulltext.txt
- Citation
- 24-1.0373469.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0373469/manifest