Routing with Minimum Fragmentation Cost

One of the greatest difficulties involved in communication networks project is the need to interconnect different networks to form a unique internetwork. A major headache is the differing maximum packet sizes allowed by each network, which causes oversize packets to be broken up into appropriately sized fragments. Unfortunately, the fragmentation process implies additional costs, tightly bounded up with routing and fragmentation strategies in use. The approach commonly used in IP protocols provides two separated functions which operate in a completely indipendent way. This adversely affects network performance measures, both quantitatively (throughput) and qualitatively (average packet delay), whereas some form of cooperation between the two functions could result in a reduction of this efficiency loss. This paper presents a pseudo-polynomial algorithm for solving the combined fragmentation and routing problem. The method of solution is based on the concept of bicriterion shortest path problem, where two distinct objective functions must be minimized: the path length (in accordance with many classic routing algorithm) and the number of fragments received by the destination host. Besides, the paper deals with the problem of the effective fragments-hops minimization. An algorithm aimed at this purpose is provided together with the analysis of the possibility to reduce its running time under appropriate considerations on the generated fragment sizes.