CAREER Proposal: Fundamental Algorithmic, Architectural and Economic Issues in Designing High Speed QoS-capable Data Networks

概述了一个广泛的研究计划，用于调查高速，服务质量（QoS）能力数据网络设计中出现的基本问题。在总体架构框架中确定了几个关键问题，类似于IETF下一代互联网（NGI）差异化服务工作组（DIFFSERV）所考虑的问题。该研究计划由技术和经济两个部分组成，每个部分都包含研究界面临的几个问题。向单个用户提供差异化QoS的核心问题是网络资源在用户之间的公平分配。网络可以通过在交换节点上采用像加权公平排队（WFQ）这样的分组调度机制来实现这一点。研究表明，这些方案有效地在不同用户的流之间建立了带宽防火墙，从而保证了一个流的QoS不受其他流的影响。但是像WFQ这样的方案遭受了维度的诅咒：它们需要交换机/路由器维护流状态信息，以区分各个流的数据包。这使得它们过于复杂，无法在大型高速网络中使用。或者，如果可以激励用户将他们的流量限制在规定的参数下，那么网络就可以省去必须建立带宽防火墙的负担。这大大降低了路由器设计的复杂性。利用经济学思维，研究人员认为，必要的激励可以通过向用户收取其他交通因其病态流量而造成的损害的费用来提供。但收费方案的可行性取决于它们的可实施性：尽管它们降低了路由器的成本，但它们需要安装设备来监控每条流量并相应地产生收费。这个研究项目利用了这两种相互关联的趋势，并采取了统一的方法。解决的核心问题是：(i)是否可以设计实现简单的路由器机制来为单个流提供QoS保证？是否可以设计简单而有效的收费机制来鼓励用户限制其流量？提议者进行的初步工作为这些问题提供了令人鼓舞的答案，并提出了一种以最小实现开销提供QoS的通用方法。整个程序包括设计算法，考虑建筑问题，分析数学模型，并使用博弈论和经济思想。解决方案的鲁棒性将通过广泛的网络拓扑和参数值的广泛模拟进行测试。实现它们的复杂性将通过模拟和原型设计来探索。教育计划包括：开设理论与实践紧密结合的高级网络课程，在未来两年开设网络本科课程，开展跨学科的教育和研究活动，让本科生和研究生参与研究。

A broad research program is outlined for investigating fundamental issues arising in the design of high speed, quality-of-service (QoS) capable data networks. Several key problems are identified within an over all architectural framework, similar to that considered by the IETF Working Group on Differentiated Services (DIFFSERV) for the Next Generation Internet (NGI). The research program consists of technological and economic components, each containing several problems that confront the research community. The essential issue of providing differentiated QoS to individual users is the fair allocation of network resources among the users. The network can accomplish this by employing packet scheduling mechanisms like Weighted Fair Queueing (WFQ) at the switching nodes. It has been shown that these schemes effectively erect bandwidth firewalls between the flows of different users, thus guaranteeing that the QoS of one flow is not at the mercy of other flows. But schemes like WFQ suffer from the curse of dimensionality: They require switches/routers to maintain flow state information for distinguishing the packets of individual flows. This renders them too complex to be used in large high speed networks. Alternatively, if users can be incentivised to condition their flows to prescribed parameters, then the network can be spared the burden of having to erect bandwidth firewalls. This considerably reduces the complexity of router design. Using economic thinking researchers argue that the requisite incentive can be provided by charging users for the damage caused to other traffics by their ill-conditioned flows. But the feasibility of charging schemes depends on their implementability: Although they reduce the cost of routers, they require the installation of devices for monitoring each flow and for producing a charge accordingly. This research program taps into both these interrelated currents and takes a unifiedapproach. The central questions addressed are: (i) Can implementationally simple routermechanisms be designed for providing QoS guarantees to individual flows? (ii) Can simple and effective charging mechanisms be devised for incentivising users to condition their flows? Preliminary work conducted by the proposer gives an encouraging answer to these questions, and suggests a general approach to the problem of providing QoS with minimal implementation overhead. The overall program involves devising algorithms, considering architectural issues, analyzing mathematical models, and using game theoretic and economic ideas. The robustness of solutions will be tested through extensive simulation of a wide range of network topologies and parameter values. The complexity of implementing them will be explored through simulation and possibly through prototype design. The education plan consists of developing an advanced networking course which aims to closely integrate theory and practice, developing an undergraduate course in Networking over the next two years, initiating cross-disciplinary education and research activities, and involving undergraduate and graduate students in research.