Machnet: a simple access protocol for high speed or long haul communications

ABSTRACT

In high-speed networks, the ratio of the end-to-end propagation delay to the transmission delay may exceed one. Under these conditions, neither token-passing nor conventional CSMA/CD schemes can work efficiently. Previous work on access protocols for high-speed networks is generally based on round-robin service and can only operate on unidirectional media. This paper introduces new high-speed access protocols which can work on various LAN's topologies (star, tree, unidirectional media) and also on satellite networks. Based on a tree algorithm with deferred collision detection, this protocol includes mechanisms which reduce collisions and increase throughput. The maximum channel utilization can reach 100% whatever the propagation delay and the total connected population may be.

REFERENCES

• 1: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 2: ANSI/IEEE std 802.4 1985 "Token-passing Bus Access Method and Physical Layer Specifications" The Institute of Electrical and Electronic Engineers, Inc.: New York, 1985.
• 3: F. Tobagi, F. Borgonovo and L. Fratta, "Expressnet: a high-performance integrated services local area network," IEEE Journal in selected areas in communications, Vol 1, No 5, pp. 898-913, 1983.
• 4: "information processing systems Fiber Distributed Data Interface (FDDI), Part 2 : Media Access Control," Draft International Standard ISO/DI8 9314- 2,
• 5: "Draft Of Proposed IEEE Standard 802.6 Metropolitan Area Network" ( MAN ) Distributed Queue Dual Bus Media Access Control. January 19 1988.
• 6: P. Jacquet and P. Mfihletahler, "Lightnet: un protocole d'acc#s k haut d#bit pour bus unidirectionnel," Res. Rep. No 654, INRIA, 1987.
• 7: P. Jacquet and P. Mfhletahler, "Lightnet: A Class Of Efficient High-Speed Protocols," to be presented at ICC 90 in Atlanta. April 90.
• 8: P.Jacquet and P. Miihlethaler: "sc Machnet: un r#- seau performant pour le haut d#bit ou les communications longues distances," INRIA Research Report, No 684, 1987.
• 9: P.Jacquet and P. M iihlethaler: "An Efficient High- Speed Protocol For Broadcast Networks," North- Holland "Protocols For High-Speed Networks" Selected and Revised Papers from IFIP WG 6.1/WG 6.4 International Workshop on Protocols For High- Speed Networks IBM Research Laboratory Riischlikon, Switzerland, 9-11 May, 1989.
• 10: J. Capetanakis: "generalized TDMA: the multi-accessing tree protocol" IEEE Trans. on Comm.'7 Vol Com-27, No 10, 1979.
• 11: P. Jacquet: "Robust and implicitly bimodal collision resolution protocols," INRIA Research Report, No 717, 1987.
• 12: J. L. Massey: "Collision Resolution Algorithms and Random-Access Communications," in Multi- User Communication Systems, G. Longo Editor, CISM Course and Lectures no. 255, Springer Verlag, Wien New York, pp. 73-137, 1981.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Performance