The flow deviation method: an approach to store-and-forward communication network design.

*(English)*Zbl 1131.90321Summary: Two problems relevant to the design of a store-and-forward communication network (the message routing problem and the channel capacity assignment problem) are formulated and are recognized to be essentially nonlinear, unconstrained multicommodity (m.c.) flow problems. A ‘flow deviation’ (FD) method for the solution of these nonlinear, unconstrained m.c. flow problems is described which is quite similar to the gradient method for functions of continuous variables; here the concept of gradient is replaced by the concept of ‘shortest route’ flow. As in the gradient method, the application of successive flow deviations leads to local minima. Finally, two interesting applications of the FD method to the design of the ARPA computer network are discussed.

##### MSC:

90B18 | Communication networks in operations research |

94A20 | Sampling theory in information and communication theory |

Full Text:
DOI

##### References:

[1] | Communication Nets: Stochastic Message Flow and Delay, McGraw-Hill Book Co., New York, 1964. |

[2] | and , ”The Design of Minimum Cost Survivable Networks,” Trans. on Circuit Theory, November 1969, pp. 455–460. |

[3] | ”Multiple Computer Networks and Intercomputer Communications,” ACM Symposium on Operating Systems Principles, Gatlinburg, Tennessee, October 1967. |

[4] | and , ”Computer Network Development to Achieve Resource Sharing,” AFIPS Conference Proc., SJCC, May, 1970, pp. 543–549. |

[5] | , , and , ”The Interface Message Processor for the ARPA Computer Network,” AFIPS Conference Proc., SJCC, May 1970, pp. 551–567. |

[6] | ”Analytic and Simulation Methods in Computer Network Design,” AFIPS Conference Proc., SJCC, May 1970, pp. 569–579. |

[7] | and , ”Topological Considerations in the Design of the ARPA Computer Network,” AFIPS Conference Proc., SJCC, May 1970, pp. 581–587. |

[8] | and , ”HOST-to-HOST Communication Protocol in the ARPA Network,” AFIPS Conference Proc., SJCC, May 1970, pp. 589–597. |

[9] | Integer Programming and Network Flows, Addison-Wesley, 1969. · Zbl 0197.45701 |

[10] | , and , ”Optimization of a New Model for Message-Switching Networks,” ICC’71, pp. 39–16 to 39–21. |

[11] | Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1962. |

[12] | and , Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962. |

[13] | Ford, Management Science 5 pp 97– (1958) |

[14] | Tomlin, Operations Research 14 pp 45– (1966) |

[15] | and , ”Multicopy Traffic Network Models,” Proc. of the Symposium on the Theory of Traffic Flow, (R. Herman, ed.), 1961. |

[16] | Network Analysis Corporation, ”Research in Store and Forward Computer Networks,” Fourth Semiannual Technical Report, December 1971, (Contract No. DAHC 15–70–C–0120). |

[17] | and , ”The Traffic Assignment Problem for a General Network,” Journal of Research of the National Bureau of Standards - B, Vol. 73B, No. 2, April 1969. |

[18] | Yaged, Networks 1 pp 139– (1971) |

[19] | and , ”The Optimal Routing of Messages in a Computer Network via Mathematical Programming,” IEEE Comp. Conference, San Francisco, September 1972. |

[20] | ”Some Theoretical Aspects of Road Traffic Research,” Proc. Inst. Civ. Eng. Part II, I, 1952, pp. 325–378. |

[21] | ”The Design of Store-and-Forward Networks for Computer Communications,” Ph.D. Dissertation, Computer Science Department, School of Engineering and Applied Science, University of California, Los Angeles, California, January 1973. |

[22] | and , ”The Synthesis of Computer Networks: Properties of the Optimum Solution,” ACM-International Computing Symposium, Venice, Italy, April 1972. |

[23] | Nonlinear Programming, McGraw-Hill Book Co., New York, 1969. |

[24] | Frank, Networks 1 pp 99– (1971) |

[25] | , , , and , ”The Terminal IMP for the ARPA Computer Network,” AFIPS Conference Proc., SJCC, 1972, pp. 243–254. |

[26] | and , ”Computer Communication Network Design – Experience with Theory and Practice,” AFIPS Conference Proc., SJCC, 1972, pp. 255–270. |

[27] | , and , ”Function-Oriented Protocols for the ARPA Computer Network,” AFIPS Conference Proc., SJCC, 1972, pp. 271–279. |

[28] | and , ”McROSS – A Multi-Computer Programming System,” AFIPS Conference Proc., SJCC, 1972, pp. 281–293. |

[29] | ”Extension of Packet Communication Technology to a Hand-Held Personal Terminal,” AFIPS Conference Proc., SJCC, 1972, pp. 295–298. |

[30] | Frank, Networks 1 pp 43– |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.