An Internet multicast system for the stock market

ABSTRACT

We are moving toward an international, 24-hour, distributed, electronic stock exchange. The exchange will use the global Internet, or internet technology. This system is a natural application of multicast because there are a large number of receivers that should receive the same information simultaneously. The data requirements for the stock exchange are discussed. The current multicast protocols lack the reliability, fairness, and scalability needed in this application. We describe a distributed architecture and a timed reliable multicast protocol, TRMP, that has the appropriate characteristics. We consider three applications: (1) A unified stock ticker of the transactions that are being conducted on the various physical and electronic exchanges. Our objective is to deliver the same combined ticker reliability and simultaneously to all receivers, anywhere in the world. (2) A unified sequence of buy and sell offers that are delivered to a single exchange or a collection of exchanges. Our objective is to give all traders the same fair access to an exchange independent of their relative distances to the exchange or delay and loss characteristics of the international network. (3) A distributed, electronic trading floor that can replace the current exchanges. This application has the fairness attributes of the first two applications and uses TRMP to conduct irrefutable, distributed trades.

REFERENCES

• 1: Rajeev Alur , David L. Dill, A theory of timed automata, Theoretical Computer Science, v.126 n.2, p.183-235, April 25, 1994 [doi>10.1016/0304-3975(94)90010-8]
• 2: Kenneth P. Birman , Robbert Van Renesse, Reliable Distributed Computing with the ISIS Toolkit, IEEE Computer Society Press, Los Alamitos, CA, 1993
• 3: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 4: BRASSIL, J. T., LOW,S.,AND MAXEMCHUK, N. F. 1999. Copyright protection for the electronic distribution of text documents. Proc. IEEE 87, 7 (July), 1181-1196.
• 5: BUSSCHBACH, P. B. 1998. Toward QoS-capable virtual private networks. Bell Labs Tech. J. 3,4 (Oct.-Dec.), 161-175.
• 6: Jo-Mei Chang, Simplifying distributed database systems design by using a broadcast network, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 7: Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
• 8: CHESWICK, B. 1990. The design of a secure Internet gateway. In Proceedings of the Usenix Summer Conference (Anaheim, Calif., June). USENIX Assoc., Berkeley, Calif., 233-237.
• 9: CLIFFORD,B.AND TSO, T. 1994. Kerberos: An authentication service for computer networks. IEEE Commun. Mag. 32, 9 (Sept.), 33-38.
• 10: S. E. Deering, Multicast routing in internetworks and extended LANs, Symposium proceedings on Communications architectures and protocols, p.55-64, August 16-18, 1988, Stanford, California, United States
• 11: DELGROSSI, L., HALSTRICK, C., HERTWICH,R.G.,AND STUTTGEN, H. 1992. HeiTPA transport protocol for ST-II. In Proceedings of the IEEE Globcom '92 Conference, IEEE, New York, 1369-1332.
• 12: DI CRESCENZO, G., OSTROVSKY, R., AND RAJAGOPOLAN, S. 1999. Conditional oblivious transfer and time released encryption. In Proceedings of the Eurocrypt '99 Conference. Springer-Verlag, New York, 74-89.
• 13: DIFFIE, W. 1988. The first ten years of public-key cryptography. Proc. IEEE 76, 5 (May), 560-577.
• 14: DIOT, C., DABBOUS,W.,AND CROWCROFT, J. 1997. Multipoint communications: A survey of protocol, functions and mechanisms. IEEE J. Syst. Comput. 15, 3 (Apr.), 277-290.
• 15: HARN,L.AND LIN, H.-Y. 1993. Key management for decentralized computer network services. IEEE Trans. Commun. 41, 12 (Dec.), 1777-1779.
• 16: KUNG,H.T.AND WANG, S. Y. 1998. TCP Trunking. Harvard University, Boston, Mass.
• 17: MAXEMCHUK, N. F. 1994. Electronic document distribution. ATT Tech. J. 73, 5 (Sept.), 73-80.
• 18: MAXEMCHUK,N.F.AND CHANG, J.-M. 1984. Analysis of the messages transmitted in a broadcast protocol. In Proceedings of the ICC '84 Conference (May). 1263-1267.
• 19: N. F. Maxemchuk , K. Padmanabhan , S. Lo, A cooperative packet recovery protocol for multicast video, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.259, October 28-31, 1997
• 20: MILLER,P.A.AND TURCU, P. N. 1992a. Generic signaling protocol: Architecture, model and services. IEEE Trans. Commun. 40, 5 (May), 957-966.
• 21: MILLER,P.A.AND TURCU, P. N. 1992b. Generic signaling protocol: Switching, networking and interworking. IEEE Trans. Commun. 40, 5 (May), 967-979.
• 22: MILLS, D. L. 1991. Internet time synchronization: The network time protocol. IEEE Trans. Commun. 39, 10 (Oct.), 1482-1493.
• 23: David L. Mills, Improved algorithms for synchronizing computer network clocks, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.245-254, June 1995 [doi>10.1109/90.392384]
• 24: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• 25: PAUL, S., SABNANI, K., LIN, J., BHATTACHARYYA, S. 1997. Reliable multicast transport protocol (RMTP). IEEE J. Syst. Comput. 15, 3 (Apr.), 407-421.
• 26: Sassan Pejhan , Mischa Schwartz , Dimitris Anastassiou, Error control using retransmission schemes in multicast transport protocols for real-time media, IEEE/ACM Transactions on Networking (TON), v.4 n.3, p.413-427, June 1996 [doi>10.1109/90.502240]
• 27: PIERCE, J. R. 1972. How far can loops go. IEEE Trans. Commun. COM-20, 3 (June), 527-530.
• 28: Rico Piantoni , Constantin Stancescu, Implementing the Swiss Exchange Trading System, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.309, June 25-27, 1997
• 29: R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 30: RUBENSTEIN, D., MAXEMCHUK,N.F.,SHUR, D. 2000. A centralized approach to network repair service for multicast streaming media. In Proceedings of the NOSSDAV 2000 Conference (June 26-28, Chapel Hill, N.C.). 173-182.
• 31: STEINER,J.G.,NEUMAN,C.,AND SCHILLER, J. I. 1988. Kerberos: An authentication service for open network systems. In Proceedings of the USENIX Winter Conference (Feb. 9-12, Dallas Tex.). 191- 202.
• 32: WHETTEN,B.AND TASKALE, G. 2000. An overview of reliable multicast transport protocol II. IEEE Network. Mag. (Jan.-Feb.), 37-47.
• 33: Brian Whetten , Todd Montgomery , Simon M. Kaplan, A High Performance Totally Ordered Multicast Protocol, Selected Papers from the International Workshop on Theory and Practice in Distributed Systems, p.33-57, September 05-09, 1994
• 34: WILLETT, M. 1982. A tutorial on public key cryptography. In Computers and Security I. North- Holland Publishing Company, 72-79.
• 35: Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996 [doi>10.1145/227210.227229]
• 36: Mihalis Yannakakis , David Lee, An Efficient Algorithm for Minimizing Real-Time Transition Systems, Formal Methods in System Design, v.11 n.2, p.113-136, Aug. 1997 [doi>10.1023/A:1008621829508]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.4 Distributed Systems

General Terms:
Design, Performance, Theory

Keywords:
multicast