Virtual lines, a deadlock free and real-time routing mechanism for ATM networks

Gerardus Johannes Maria Smit, Paul J.M. Havinga, Walter H. Tibboel

    Research output: Contribution to conferencePaper

    112 Downloads (Pure)


    In this paper we present a routing mechanism and buffer allocation mechanism for an ATM switching fabric. Since the fabric will be used to transfer multimedia traffic it should provide a guaranteed throughput and a bounded latency. We focus on the design of a suitable routing mechanism that is capable to fulfil these requirements and is free of deadlocks. We will describe two basic concepts that can be used to implement deadlock free routing. Routing of messages is closely related to buffering. We have organized the buffers into parallel fifos, each representing a virtual line. In this way we not only have solved the problem of Head Of Line blocking, but we can also give real-time guarantees. We will show that for local high-speed networks it is more advantageous to have a proper flow control than to have large buffers. Although the virtual line concept can have a low buffer utilization, the transfer efficiency can be higher. The virtual lines concept allows adaptive routing. The total throughput of the network can be improved by using alternative routes. Adaptive routing is attractive in networks where alternative routes are not much longer than the initial route(s). The network of the switching fabric is built up from switching elements interconnected in a Kautz topology.
    Original languageUndefined
    Number of pages8
    Publication statusPublished - 1993
    EventEight International Symposium on Computer and Information Sciences - Antalya, Turkey
    Duration: 3 Nov 19935 Nov 1993


    ConferenceEight International Symposium on Computer and Information Sciences
    OtherNovember 3-5, 1993


    • IR-18837

    Cite this