More Web Proxy on the site http://driver.im/

article

Trajectory sampling for direct traffic observation

Editors: Mostafa H. Ammar, Christophe Diot Authors:

N. G. Duffield,

Matthias GrossglauserAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 9, Issue 3

Pages 280 - 292

https://doi.org/10.1109/90.929851

Published: 01 June 2001 Publication History

Abstract

Traffic measurement is a critical component for the control and engine ering of communication networks. We argue that traffic measurement should make it possible to obtain the spatial flow of traffic through the domain, i.e., the paths followed by packets between any ingress and egress point of the domain. Most resource allocation and capacity planning tasks can benefit from such information. Also, traffic measurements should be obtained without a routing model and without knowledge of network state. This allows the traffic measurement process to be resilient to network failures and state uncertainty. We propose a method that allows the direct inference of traffic flows through a domain by observing the trajectories of a subset of all packets traversing the network. The key advantages of the method are that 1) it does not rely on routing state; 2) its implementation cost is small; and 3) the measurement reporting traffic is modest and can be controlled precisely. The key idea of the method is to sample packets based on a hash function computed over the packet content. Using the same hash function will yield the same sample set of packets in the entire domain, and enables us to reconstruct packet trajectories.

References

[1]

G. Alines, S. Kalidindi, and M. Zekauskas. (1999, Sept.) A one-way delay metric for IPPM. {Online}. Available: http://www.ietf.org/rfc

[2]

---, (1999, Sept.) A one-way packet loss metric for IPPM. {Online}. Available: http://www.ietf.org/rfc

[3]

D. O. Awduche, "MPLS and traffic engineering in IP networks," IEEE Commun. Mag., vol. 37, pp. 42-47, Dec. 1999.

[4]

Y. Bemet, J. Binder, S. Blake, M. Carlson, B. E. Carpenter, S. Keshav, E. David, B. Ohlman, D. Verma, Z. Whang, and W. Weiss. (1999, Feb.) A framework for differentiated services. {Online}Internet draft.

[5]

R. Caceres, N. G. Duffield, J. Horowitz, and D. Towsley, "Multicastbased inference of network-internal loss characteristics," IEEE Trans. Inform. Theory, vol. 45, pp. 2462-2480, 1999.

[6]

R. Callon etal. (1999, Sept.) A framework for MPLS. {Online}Intemet draft.

[7]

CERT/CC and FedCIRC, "Advisory CA-2000-01 denial-of-service developments," Carnegie Mellon Software Engineering Institute, Jan. 2000.

[8]

K.C. Claffy, H.-W. Braun, and G. C. Polyzos, "Parameterizable methodology for Internet traffic flow profiling," 1EEE J. Select. Areas Commun., vol. 13, pp. 1481-1494, Oct. 1995.

[9]

K.C. Claffy, G. C. Polyzos, and H.-W. Braun, "Application of sampling methodologies to network traffic characterization," Comput. Commun. Rev., vol. 23, no. 4, pp. 194-203, Oct. 1993.

[10]

I. Cozzani and S. Giordano, "Traffic sampling methods for end-to-end QoS evaluation in large heterogeneous networks," Comput. Networks and ISDN Syst., vol. 30, pp. 16-18, Sept. 1998.

[11]

A. Feldmann, A. Greenberg, C. Lurid, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Network Mag., vol. 14, pp. 11-19, Mar. 2000.

[12]

A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and E True, "Deriving traffic demands for operational IP networks: Methodology and experience," in Proc. ACM SIGCOMM, Stockholm, Sweden, Aug. 2000, pp. 257-270.

[13]

S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Trans. Networking, vol. 1, pp. 397-413, Aug. 1993.

[14]

S. Floyd and V. Jacobson, "The synchronization of periodic routing messages," IEEE/ACM Trans. Networking, vol. 2, pp. 122-136, Apr. 1994.

[15]

T.G. Griffin and G. Wilfong, "An analysis of BGP convergence properties," Comput. Commun. Rev., vol. 29, pp. 277-288, Oct. 1999.

[16]

V. Jacobson, C. Leres, and S. McCanne. (1989) tcpdurap. {Online}. Available: ftp://ftp.ee.lbl.gov

[17]

D.E. Knuth, "Sorting and searching," in The Art of Computer Programruing. Reading, MA: Addison-Wesley, 1998, vol. 3.

[18]

C. Labovitz, G. R. Malan, and f. Jahanian, "Internet routing instability," IEEE/ACM Trans, Networking, vol. 6, pp. 515-528, Oct, 1998.

[19]

NetFlow, Cisco Systems. (2000). {Online}. Available: http://www.cisco.com/warp/public/732/netflow/index.html

[20]

V. Paxson, "Empirically derived analytic models of wide-area TCP connections," IEEE/ACM Trans. Networking, vol. 2, pp. 8-17, Aug. 1994.

[21]

K. K. Ramakrishnan and S. Floyd. (1999, Jan.) A proposal to add explicit congestion notification (ECN) to IP. {Online}. Available: ftp://ftp.isi.edu/in-notes/rfc2481 .txt

[22]

R. Rivest. (1992, Apr.) The MD5 message-digest algorithm. {Online}. Available: ftp://ftp.isi.edu/in-notes/rfc 1321 .txt

[23]

L. G. Roberts, "Beyond Moore's law: Internet growth trends," IEEE Comput., vol. 33, pp. 117-119, Jan. 2000.

[24]

L. Sachs, Applied Statistics. New York: Springer, 1984.

[25]

H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson. (1996, Jan.) RTP: A transport protocol for real-time applications. {Online}. Available: http://www.ietf.org/rfc

[26]

W. Simpson. (1995) IP in IP tunneling. {Online}. Available: RFC 1853, ftp://ftp.isi.edu/in-notes/rfc 1853.txt

[27]

W. Stallings, SNMP, SNMP v2, SNMP v3, and RMON 1 and 2, 3rd ed. Reading, MA: Addison-Wesley, 1999.

[28]

D. Tappan et al. (2000, July) MPLS label stack encoding. {Online}Internet draft

[29]

M. Thorup, "Even strongly universal hashing is pretty fast," in Proc. 11 th ACM-SIAM Symp. Discrete Algorithms (SODA), 2000, pp. 496M97.

[30]

V. Paxson and S. Floyd, "Why we don't know how to simulate the Internet," in Proc. 1997 Winter Simulation Conf., Dec. 1997.

[31]

J. Walrand, private communication, Feb. 2000.

[32]

K.C. Claffy, G. C. Polyzos, and H.-W. Braun, "Application of sampling methodologies to network traffic characterization," in Proc. ACM SIG- COMM, Sept. 1993, pp. 194-203.

[33]

T. G. Griffin and G. Wilfong, "An analysis of BGP convergence properties," in Proc. ACM SIGCOMM, Aug./Sept. 1999. pp. 277-288.

Cited By

Li EWu WZhaohua WLi ZNiu J(2024)SAROS: A Self-Adaptive Routing Oblivious Sampling Method for Network-wide Heavy Hitter DetectionProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663429(142-148)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663429
Ding RLiu XYang SHuang QXie BSun RZhang ZCui BSekar VYu MSeneviratne AVeitch D(2024)RD-Probe: Scalable Monitoring With Sufficient Coverage In Complex Datacenter NetworksProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672256(258-273)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672256
Bose SChowdhury AMukherjee N(2024)Scheduling periodic sensors for instantaneous aggregated traffic minimizationWireless Networks10.1007/s11276-024-03722-430:5(3257-3268)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11276-024-03722-4
Show More Cited By

Index Terms

Trajectory sampling for direct traffic observation

Recommendations

Trajectory sampling for direct traffic observation

Traffic measurement is a critical component for the control and engineering of communication networks. We argue that traffic measurement should make it possible to obtain the spatial flow of traffic through the domain, i.e., the paths followed by ...
Trajectory sampling for direct traffic observation
SIGCOMM '00: Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication

Traffic measurement is a critical component for the control and engineering of communication networks. We argue that traffic measurement should make it possible to obtain the spatial flow of traffic through the domain, i.e., the paths followed by ...
Adaptive random sampling for traffic volume measurement

Traffic measurement and monitoring are an important component of network management and traffic engineering. With high-speed Internet backbone links, efficient and effective packet sampling techniques for traffic measurement and monitoring are not only ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 9, Issue 3

June 2001

149 pages

ISSN:1063-6692

Editors:
Mostafa H. Ammar
College of Computing, Atlanta, GA
,
Christophe Diot
Sprint ATL, Burlingame, CA

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 June 2001

Published in TON Volume 9, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

94
Total Citations
View Citations
786
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li EWu WZhaohua WLi ZNiu J(2024)SAROS: A Self-Adaptive Routing Oblivious Sampling Method for Network-wide Heavy Hitter DetectionProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663429(142-148)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663429
Ding RLiu XYang SHuang QXie BSun RZhang ZCui BSekar VYu MSeneviratne AVeitch D(2024)RD-Probe: Scalable Monitoring With Sufficient Coverage In Complex Datacenter NetworksProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672256(258-273)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672256
Bose SChowdhury AMukherjee N(2024)Scheduling periodic sensors for instantaneous aggregated traffic minimizationWireless Networks10.1007/s11276-024-03722-430:5(3257-3268)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11276-024-03722-4
Yang KWu YMiao RYang TLiu ZXu ZQiu RZhao YLv HJi ZXie GSchulzrinne HKohler EMaltz DMisra V(2023)ChameleMon: Shifting Measurement Attention as Network State ChangesProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604850(881-903)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604850
Langlet JBen Basat ROliaro GMitzenmacher MYu MAntichi GSchulzrinne HKohler EMaltz DMisra V(2023)Direct Telemetry AccessProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604827(832-849)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604827
Gou XZou L(2023)Sliding window-based approximate triangle counting with bounded memory usageThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00783-332:5(1087-1110)Online publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1007/s00778-023-00783-3
Gong JLi YAnwer BShaikh AYu M(2020)MicroscopeProceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication10.1145/3387514.3405876(390-403)Online publication date: 30-Jul-2020
https://dl.acm.org/doi/10.1145/3387514.3405876
Basat REinziger GTayh BHan DFeldmann A(2020)A faster and more efficient q-MAX algorithmProceedings of the 16th International Conference on emerging Networking EXperiments and Technologies10.1145/3386367.3431671(538-539)Online publication date: 23-Nov-2020
https://dl.acm.org/doi/10.1145/3386367.3431671
Nikolopoulos PPappas CArgyraki KPerrig A(2019)Retroactive Packet Sampling for Traffic ReceiptsACM SIGMETRICS Performance Evaluation Review10.1145/3376930.337694247:1(17-18)Online publication date: 17-Dec-2019
https://dl.acm.org/doi/10.1145/3376930.3376942
Nikolopoulos PPappas CArgyraki KPerrig A(2019)Retroactive Packet Sampling for Traffic ReceiptsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3322205.33110903:1(1-39)Online publication date: 26-Mar-2019
https://dl.acm.org/doi/10.1145/3322205.3311090
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents