\magnification=1200
\baselineskip=20pt
\nopagenumbers
\font\big=cmr12 scaled \magstep2

\centerline{\bf STANFORD UNIVERSITY}
\centerline{\bf DEPARTMENT OF STATISTICS}
\centerline{\big DEPARTMENTAL SEMINAR}
\bigskip

\baselineskip=12pt
\centerline{4:15 p.m., Tuesday, April 8, 2003}
\centerline{Sequoia Hall Room 200}
\centerline{(Cookies at 3:45 in 1st Floor Lounge)}
\centerline{Reception to follow at 5:30}

\bigskip
\baselineskip=15pt
\centerline{\sl Bin Yu}
\centerline{\sl Statistics Department}
\centerline{\sl University of California, Berkeley}
\bigskip
\centerline{\bf Network Tomography}
\bigskip


Network monitoring and diagnosis are key to improving network
performance.  The difficulties of performance monitoring lie in
today's fast growing Internet, accompanied by increasingly
heterogeneous and unregulated structures.  Moreover, these tasks
become even harder since one cannot rely on the collaboration of
individual routers and servers to directly measure
network traffic.  The aggregative nature of possible network
measurements gives rise to inverse problems, which are termed
Network Tomography by Vardi (1996) to recognize
the similarities to medical tomography.

We start with an introduction to the general linear network
tomography model, which has as special cases:
(i) link delay distribution estimation through multicast
end-to-end measurements; (2) origin-destination matrix estimation
through link traffic counts.  We review earlier methods including
a fast and recursive algorithm for (i) (Lo Presti et al, 1999),
and a maximum likelihood method via EM (Cao et al, 2000), and
discuss why they are either statistically inefficient
or computational intractable for large networks.
Then we propose a maximum pseudo likelihood (MPLE)
approach (Liang and Yu, 2003) for this general network tomography model.
A pseudo expectation-maximization (EM) algorithm is
developed to maximize the pseudo log-likelihood function.
Through simulations and real data sets, we demonstrate in
the two special cases above that our MPLE keeps a
good balance between the computational complexity and the statistical
efficiency of the parameter estimation.

(Based on joint works with J. Cao, D. Davis, and S. Vander Wiel
at Bell Labs and G. Liang at UC Berkeley. Papers available
at www.stat.berkeley.edu/~binyu/publications.html)

\bye