网络坐标

网络坐标系统（NetworkCoordinateSystem），又称为互联网坐标系统（InternetCoordinateSystem），是一种具有可扩展性的互联网距离预测方案。对于一个有N个节点的网络，每个参与网络坐标系统的节点通过少量测量，得到一个（或者多个）d维矢量，即为该节点的网络坐标。利用任意两个节点的网络坐标，根据事先定义的计算法则，就可以预测它们之间的网络距离。对于一个包含N个网络节点的系统，其测量复杂度为O(N)，因此，网络坐标系统可以通过复杂度为O(N)的测量预测N(N−1)条链路的距离，从而可以避免大量的端到端测量。这是一种具有高可扩展性的方案，可以应用于大规模分布式网络系统。

对网络坐标系统的研究从2001年开始，出现了很多典型的系统。GNP(Global_network_positioning)、VL、ICS等称为第一代系统，又称为中心式网络坐标系统。这一代系统的特点是首先布置少量的中心式服务器节点（以下简称中心节点），中心节点通过相互的测量获取两两之间的距离信息，将这些信息汇总后利用一个中心式的优化算法求得所有中心节点的坐标。系统的其他所有参与节点称为普通节点，它们在中心节点的辅助下计算自身坐标。每一个普通节点通过测量自身到中心节点的距离，再利用中心节点的坐标，通过非线性优化或者主成分分析等方法，求得自身坐标。第一代网络坐标的方法主要不足之处是当参与节点数量较大时，中心节点需要承受很重的测量负载，因而限制了坐标系统的服务规模。

从2004年开始，以Vivaldi(en:Vivaldi_coordinates)、NPS、PIC等系统为代表的第二代网络坐标系统被相继提出。第二代网络坐标系统的特点是完全非中心式实现，不需要事先布置和维护少量的中心式服务器节点，这样，坐标系统的服务规模就不再会受到限制。但是第二代网络坐标系统距离预测的准确性和第一代系统相比并没有提高。