On Bandwidth Tiered Service

Many network operators offer some type of tiered service, in which users may select only from a small set of service levels (tiers). Such a service has the potential to simplify a wide range of core network functions, allowing the providers to scale their operations efficiently. In this work, we study a number of problem variants related to service tier selection. Our contributions include: (1) a faster algorithm for obtaining optimal service tiers; (2) a new formulation and optimal algorithm to optimize jointly the number and magnitude of each service tier; and (3) the concept of ??TDM emulation?? in which all service tiers are multiples of the same (software-configurable) bandwidth unit, and a suite of algorithms to select jointly the basic unit and service tiers. Our work provides a systematic framework for reasoning about and tackling algorithmically the general problem of service tier selection, and has applications to a number of networking contexts, including access networks (e.g., determining the tiers for ADSL, cable modem networks or PONs) and core networks (e.g., LSP sizing for MPLS networks).