Packet prediction for speculative cut-through switching

ABSTRACT

The amount of intelligent packet processing in an Ethernet switch continues to grow, in order to support of embedded applications such as network security, load balancing and quality of service assurance. This increased packet processing is contributing to greater per-packet latency through the switch.

In addition, there is a growing interest in using Ethernet switches in low latency environments such as high-performance clusters, storage area networks and real-time media distribution. In this paper we propose Packet Prediction for Speculative Cut-through Switching (PPSCS), a novel approach to reducing the latency of modern Ethernet switches without sacrificing feature rich policy-based forwarding enabled by deep packet inspection.

PPSCS exploits the temporal nature of network communications to predict the flow classification of incoming packets and begin the speculative forwarding of packets before complex lookup operations are complete.

Simulation studies using actual network traces indicate that correct prediction rates of up to 97% are achievable using only a small amount of prediction circuitry per port. These studies also indicate that PPSCS can reduce the latency in traditional store-and-forward switches by nearly a factor of 8, and reduce the latency of cut-through switches by a factor of 3.

REFERENCES

• 1: Jiuxing Liu , Balasubramanian Chandrasekaran , Jiesheng Wu , Weihang Jiang , Sushmitha Kini , Weikuan Yu , Darius Buntinas , Peter Wyckoff , D K. Panda, Performance Comparison of MPI Implementations over InfiniBand, Myrinet and Quadrics, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.58, November 15-21, 2003
• 2: Nor Asilah Wati Abdul Hamid , Paul Coddington, Averages, distributions and scalability of MPI communication times for Ethernet and Myrinet networks, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, p.269-276, February 13-15, 2007, Innsbruck, Austria
• 3: Sokolowski, P. J. and Grosu, D. 2004. Performance Considerations for Network Switch Fabrics on Linux Clusters. Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing Systems (MIT Cambridge, USA, November 2004).
• 4: Gupta, P. and McKeown, N. 2001. Algorithms for packet classification. Network, IEEE, 15, 2, (March 2001), 24--32.
• 5: David E. Taylor, Survey and taxonomy of packet classification techniques, ACM Computing Surveys (CSUR), v.37 n.3, p.238-275, September 2005 [doi>10.1145/1108956.1108958]
• 6: Broder, A. and Mitzenmacher, M. 2004. Network applications of Bloom filters: a survey. Internet Math., 1, 4, (May 2004), 485--509.
• 7: Sarang Dharmapurikar , Praveen Krishnamurthy , David E. Taylor, Longest prefix matching using bloom filters, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863979]
• 8: TCPDUMP/LIBPCAP public repository. http://www.tcpdump.org/
• 9: Ruoming Pang , Mark Allman , Mike Bennett , Jason Lee , Vern Paxson , Brian Tierney, A first look at modern enterprise traffic, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.2-2, October 19-21, 2005, Berkeley, CA
• 10: Tsutomu Yoshinaga , Shojiro Kamakura , Michihiro Koibuchi, Predictive Switching in 2-D Torus Routers, Proceedings of the International Workshop on Innovative Architecture for Future Generation High Performance Processors and Systems, p.65-72, January 23-25, 2006 [doi>10.1109/IWIAS.2006.33]
• 11: Li-Shiuan Peh , William J. Dally, A Delay Model and Speculative Architecture for Pipelined Routers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.255, January 20-24, 2001
• 12: Z. Ding , R. Hoare , A. Jones , D. Li , S. Shao , S. Tung , J. Zheng , R. Melhem, Switch Design to Enable Predictive Multiplexed Switching in Multiprocessor Networks, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.100.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.416]
• 13: Christian Kurmann , Michel Müller , Felix Rauch , Thomas M. Stricker, Speculative Defragmentation - A Technique to Improve the Communication Software Efficiency for Gigabit Ethernet, Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing, p.131, August 01-04, 2000
• 14: G. Surendra , S. Banerjee , S. K. Nandy, On the effectiveness of flow aggregation in improving instruction reuse in network processing applications, International Journal of Parallel Programming, v.31 n.6, p.469-487, December 2003 [doi>10.1023/B:IJPP.0000004511.82411.d4]
• 15: Jain, R. and Routhier, S. 1986. Packet Trains--Measurements and a New Model for Computer Network Traffic. IEEE J. Sel. Area Comm., 4, 6 (1986), 986--995.
• 16: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 17: Walter Willinger , Vern Paxson , Murad S. Taqqu, Self-similarity and heavy tails: structural modeling of network traffic, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 18: Jeffrey C. Mogul, Network locality at the scale of processes, ACM Transactions on Computer Systems (TOCS), v.10 n.2, p.81-109, May 1992 [doi>10.1145/128899.128900]
• 19: Kermani, P. and Kleinrock L. 1979. Virtual Cut-Through: A New Computer Communication Switching Technique. Computer Networks 3, (Sept. 1979), 267--286.
• 20: Y. S. Kuo, Generating Essential Primes for a Boolean Function with Multiple-Valued Inputs, IEEE Transactions on Computers, v.36 n.3, p.356-359, March 1987 [doi>10.1109/TC.1987.1676907]
• 21: Feldmeier, D. C. 1988. Improving gateway performance with a routing-table cache. In Proc. IEEE INFOCOM '88. (New Orleans, March, 1988), 298--307
• 22: Newman, P., Minshall, G., Lyon, T. and Huston, L. 1997. IP switching and gigabit routers. IEEE Commun. Mag., 35, 1 (Jan 1997), 64--69.
• 23: Partridge, C. 1996. Locality and route caches. NSF Workshop on Internet Statistics Measurement and Analysis (http://www.caida.org/outreach/isma/9602/positions/partridge.html), 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

General Terms:
Design, Performance

Keywords:
cut-through, ethernet switching, packet prediction, speculation