Time-varying network tomography: Router link data

• 成果类型: Article
• 署名作者: Cao, J; Davis, D; Vander Wiel, S; Yu, B
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.2307/2669743
• 发表日期: 2000
• 页码: 1063-1075
• 关键词: contingency-tables

摘要

The origin-destination (OD) traffic matrix of a computer network is useful for solving problems in design, routing, configuration debugging, monitoring, and pricing. Directly measuring this matrix is not usually feasible, but less informative Link measurements are easy to obtain. This work studies the inference of OD byte counts from link byte counts measured at router interfaces under a fixed routing scheme. A basic model of the OD counts assumes that they are independent normal over OD pairs and lid over successive measurement periods. The normal means and variances are functionally related through a power law. We deal with the time-varying nature of the counts by fitting the basic lid model locally using a moving data window. Identifiability of the model is proved for router link data and maximum likelihood is used for parameter estimation. The OD counts are estimated by their conditional expectations given the link counts and estimated parameters. Thus, OD estimates are forced to be positive and to harmonize with the link count measurements and the routing scheme. Finally, maximum likelihood estimation is improved by using an adaptive prior, Proposed methods are applied to two simple networks at Lucent Technologies and found to perform well. Furthermore, the estimates are validated in a single-router network fur which direct measurements of origin-destination counts are available through special software.