Latency equalization: a programmable routing service primitive

ABSTRACT

Today the Internet is the primary medium for deploying new real time services such as gaming and distributed online live music concerts. Different network services have different expectations from the routing infrastructure. Some network services require conventional routing paths optimized for low latency or low congestion. However, real-time interactive services such as online gaming and distributed live music performance require more than just low latency. They require Latency EQualization (LEQ) among participating users. Although LEQ could be performed by the client or the server, end-system techniques for estimating network conditions are often inaccurate. Instead, we argue that the network should provide a LEQ service. We propose a LEQ routing architecture that can leverage programmable hub nodes. By deploying a few flexible, well-placed programmable nodes to redirect traffic, we can flexibly support both latency equalized and low latency routing services simultaneously. For LEQ routing, programmable hub nodes provide services such as application packet identification, application level packet processing and latency equalized routing paths. Extensive simulation studies on provider network topologies show that using just a few programmable nodes we can achieve an 80% improvement in LEQ over the conventional architecture that uses shortest path routing.

REFERENCES

• 1: http://abilene.internet2.edu/.
• 2: A. Abdelkhalek and A. Bilas. Parallelization and performance of interactive multiplayer game servers. 2004.
• 3: Ajay Kapur , Ge Wang , Philip Davidson , Perry R. Cook, Interactive Network Performance: a dream worth dreaming?, Organised Sound, v.10 n.3, p.209-219, December 2005 [doi>10.1017/S1355771805000956]
• 4: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: G. Armitage. An experimental estimation of latency sensitivity in multiplayer quake 3. In Proceedings of the International Conference on Networks, 2003.
• 6: Daniel Bauer , Sean Rooney , Paolo Scotton, Network infrastructure for massively distributed games, Proceedings of the 1st workshop on Network and system support for games, p.36-43, April 16-17, 2002, Braunschweig, Germany [doi>10.1145/566500.566506]
• 7: S. Bhatia, M. Motiwala, W. Muhlbauer, V. Valancius, A. Bavier, N. Feamster, L. Peterson, and J. Rexford. Hosting virtual networks on commodity hardware. Technical Report GT-CS-07-10, Georgia Tech, 2007.
• 8: M. Cha, S. Moon, C.-D. Park, and A. Shaikh. Placing relay nodes for intra-domain path diversity. Proc. IEEE INFOCOM, 2006.
• 9: C. Diot and L. Gautier. A distributed architecture for multiplayer interactive applications on the internet. IEEE Network Magazine, 1999.
• 10: Johannes Färber, Network game traffic modelling, Proceedings of the 1st workshop on Network and system support for games, p.53-57, April 16-17, 2002, Braunschweig, Germany [doi>10.1145/566500.566508]
• 11: Amy R. Greenwald , Jeffrey O. Kephart , Gerald J. Tesauro, Strategic pricebot dynamics, Proceedings of the 1st ACM conference on Electronic commerce, p.58-67, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337008]
• 12: Anupam Gupta , Jon Kleinberg , Amit Kumar , Rajeev Rastogi , Bulent Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.389-398, July 2001, Hersonissos, Greece [doi>10.1145/380752.380830]
• 13: N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner. OpenFlow: Enabling innovation in campus networks. In Computer Communication Review, 2008.
• 14: R. Ramjee, F. Ansari, M. Havemann, T. V. Lakshman, T. Nandagopal, K. K. Sabnani, and T. Y. C. Woo. Separating control software from routers. COMSWARE, 2006.
• 15: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 16: Jonathan S. Turner, A proposed architecture for the GENI backbone platform, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185349]
• 17: S. Zander and G. Armitage. Empirically measuring the QoS sensitivity of interactive online game players. Australasian Telecommunication Networks and Applications Conference (ATNAC), December 2004.
• 18: Sebastian Zander , Ian Leeder , Grenville Armitage, Achieving fairness in multiplayer network games through automated latency balancing, Proceedings of the 2005 ACM SIGCHI International Conference on Advances in computer entertainment technology, p.117-124, June 15-17, 2005, Valencia, Spain [doi>10.1145/1178477.1178493]
• 19: H. Zhang. The effect of delay on network games. Master's thesis, Computing Science, UMEA University, Sweden, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Design

Keywords:
latency equalization, online interactive applications, optimization, programmable routing