Heterogeneous networks: How Push-Down Automata rescue Graph models

Heterogeneity in networks is an increasingly important issue, and it is a common scenario that a path crosses several network domains with different protocols. Protocol changes across the path can be supported using encapsulations and decapsulations of protocols. However, due to the delay caused by these changes and difficulties of configuration, such changes should be minimized. It appears that graph theory models are not expressive enough to tackle this problem. In this paper, we provide a Push-Down Automaton model of heterogeneous networks which captures their specificities. Encapsulations of protocols are modeled as pushes and decapsulation of protocols are modeled as pops in the Push-Down Automaton. We provide polynomial algorithms that compute the word which requires a minimal number of pushes and pops to be accepted by the automaton. This word allows to compute a path with a minimal number of encapsulations and decapsulations. 1998 ACM Subject Classification C.2.2 Routing protocols and F.1.1 Push-down Automata Keywords and phrases Net Computing, Heterogeneous Networks, Push-down Automata Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p