Dynamic bandwidth allocation in a network

ABSTRACT

Recently protocols have been introduced which enable us to integrate periodic traffic (voice or video) and aperiodic traffic (data) and to extend the size of local area networks without any loss in speed and capacity. One of these, the DRAMA protocol, is based on broadband technology and allows for dynamic allocation of bandwidth to clusters of nodes in the total network. In this paper we propose a distributed algorithm to allocate bandwidth in a fair manner, where we have defined fair to mean that every node in the network, regardless of its location, should have the same expected access delay to the net. We show by means of simulation that the algorithm is stable and within a few percentage points of the optimal solution. Stability is measured in terms of the time it takes the system to return to near optimal distribution of the bandwidth after strong disturbances. The algorithm is shown to handle total reallocation of the resources within O(100ms).

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: Digital, Intel, and Xerox, The Ethernet, a local area network. Data link layer and physical layer specifications, Sept. 30. Version 1.0
• 3: F.A. Tobagi and M. Fine, "Performance of Unidirectional Broadcast Local Area Networks: Expressnet and Fasnet," IEEE journal on Selected Areas in Comm., vol. SAC-l, pp. 913- 925, November 1983.
• 4: T.B Fowler and Holmgren, S.F., "A wideband Cable Bus Local Area Network," COMPCON, pp. 405-414, Fall 1982.
• 5: D. Karvelas and A. Leon-Garcia, "Performance of Integrated Packet Voice/Data Token-Passing Rings," IEEE Journal on Selected Areas in Communications, vol. SAC-4, No 6, pp. 823- 832, Sept. 1986.
• 6: Marco A. Marsan and D. Roffinella, "Multichannel Local Area Network Protocols," IEEE J-SAIC, pp. 885-897, Nov. 1983.
• 7: I. Chlamtac , O. Ganz, Performance models of asynchronous multirunk HYPERchannel networks, IEEE Transactions on Computers, v.36 n.2, p.138-146, Feb. 1987 [doi>10.1109/TC.1987.1676876]
• 8: P.C. Wong and T.S. Yum, "Design and Analysis of a Contention - Based Lookahead Reservation Protocol on a Multichannel Local Area Network," IEEE Transactions on Communications, vol. 36, no.2, pp. 234-238, Feb. 1988.
• 9: S M Sharrock , K J Maly , S Ghanta , H C Du, A framed movable-boundry protocol for integrated voice/data in a LAN, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, p.111-119, August 05-07, 1986, Stowe, Vermont, United States
• 10: S. Sharrock, K. Maly, S. Ghanta, and H. Du, "A Broadband Integrated Voice/Data/Video Network of Multiple LANs with Dynamic Bandwidth Partitioning," Proceedings, INFOCOM '87, pp. 417-425, March 1987.
• 11: G.M. Exley and L.F. Merakos, "Throughput- Delay Performance of Interconnected CSMA Local Area Networks," IEEE Journal on Selected Area in Communications, pp. 1380- 1390, Dec. 1987.
• 12: M. Hatamian and E.G. Bowen, "Homenet: A Broadband Voice/Data/Video Network on a CATV System," AT&T Technical Journal, vol. 64, pp. 347-367, February 1985.
• 13: A.N. Netravali and Z.L. Budrilcis, "A Broadband Local Area Network," Bell System Technical Journal, vol. 64, no. 10, pp. 2449-2465, December 1985.
• 14: M.W. Rahm, "CableNet: A User Perspective," COMPCON, pp. 337-342, Fall 1982.
• 15: G. Ennis and P. Filice, "Overview of a Broad- Band Local Area Network Protocol Architecture,'' IEEE journal on Selected Areas in Communications, vol. SAC-l, No.5, pp. 832-841, November 1983.
• 16: N.F. Maxemchuk, "A Variation on CSMA/CD That Yields Movable TDM Slots in Integrated Voice/Data Local Networks," Bell Systems Technical Journal, vol. 61, no 7, pp. 1527-1550, September 1982.
• 17: J.O. Limb, R.F.W. Pease, and K.A. Walsh, "Combining Intraframe and Frame-to-Frame Coding for Television," Bell Systems Technical Journal, vol. 53, No. 6, pp. 1137-1173, July- August 1974.
• 18: H. Yasuda, F. Kanaya, and H. Kawanishi, "l.5444-Mbits/s Transmission on TV Signals by Interframe Coding System," IEEE Transactions on Communications, pp. 1175-1180, October 1976.
• 19: Kurt Maly, C. Michael Overstreet, Xia-Ping Qiu, and Deqing Tang, "Dynamic Resource Allocation in a Metropolitan Area Network," Technical Report 88-03, Computer Science Department, Norfolk, VA 23529-0162, Feb. 16, 1988.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.2 Simulation Languages

          Nouns: SIMSCRIPT

General Terms:
Algorithms, Design, Measurement, Performance