随着Internet应用的急剧增长，越来越多的网络应用程序需要了解网络延迟、带宽、吞吐率等网络性能参数，以支持可区分的服务。这些及时的网络性能数据对于许多网管业务，如主动式和被动式的资源管理、流量工程以及端到端的服务质量保证，显得尤为重要。特别是现代的网络管理系统注重于服务级、应用级的管理，网络测量的频率会越来越快，需求的网络性能数据也会越来越多。 近年来网络测量技术和网络测量模型已经成为研究的热点。网络测量方式可以分为主动测量和被动测量两种。主动测量方式通过向目标链路或目标节点发送探测包，来测量链路或端到端的延迟、带宽和丢包率等网络性能参数。被动测量方式通过接入网络的测量探针，记录和统计网络链路或节点上业务流量的信息。本文对基于主动测量和被动测量的网络测量技术、网络测量模型及其近似算法进行了深入研究。本文工作的主要贡献和创新总结如下： (1) 分布式主动测量模型中测量分配问题研究 主动测量的代价包括测量站部署代价和测量代价两个部分。测量站的数量和位置确定下来以后，为了减少测量代价就需要优化测量分配方案，也就是确定链路由哪一个测量站来负责测量。 本文提出了分布式主动带宽测量模型中的测量分配问题，给出了测量分配问题的整数规划形式，并且指出测量分配的最优化问题是NP难的。基于贪婪策略和动态规划的思想，给出了近似比为2的启发式算法，并且通过仿真实验证明了近似算法的有效性。带宽测量分配问题及其解决思路和近似算法，同样可以用来解决测量延迟、丢包率等其它网络性能参数，对分布式主动测量系统的设计和实现具有很强的指导作用。 (2) 链路带宽被动监测模型优化问题研究及其近似算法 被动监测模型的研究重点在于如何部署尽量少的监控器去监控全网的性能，这样一方面减少了安装和维护代价，另一方面也可以减少收集网管数据带来的额外网络流量。利用路由器流守恒规律可以有效减少网管代理的安装数量，从而减少安装代价和收集流量，实现低负载的链路带宽有效监控。 基于流守恒的网络链路带宽被动监测模型的最优化问题可以抽象为无向图中的弱顶点覆盖问题。论文给出了一个从顶点覆盖问题到弱顶点覆盖问题的近似保持归约。根据这个近似保持归约，要想找到弱顶点覆盖问题的一个常数近似比小于2的近似算法也是非常困难的。利用近似算法的原始对偶方法，可以得到一些近似比为2的近似算法。这些算法同样可以应用于解决带禁点的弱顶点覆盖问题。 (3)链路约束的分布式网络收集框架优化问题研究及其近似算法 为了收集实时的网络性能数据，收集过程需要一个稳定可靠的低延迟路由。链路延迟或者路由跳数的限制决定了收集节点负责查询和收集的监控节点的数量是有限的。链路约束的分布式网络收集框架的优化目标是部署尽量少的收集节点收集到所有监控节点的性能数据，其最优化问题是NP难的。论文指出可以把链路约束的分布式收集框架的最优化问题映射到集合覆盖问题，利用贪婪算法可得到