Abstract: Data exchange is the kernel of e-Government. The establishment of an e-Government data exchange overlay network on application layer is one of the crucial parts of the solution to this issue. Based on the analysis of the characteristics of e-Government data exchange, an overlay network conceptual model, eGON (e-Government Data Exchange Overlay Network), was defined. The concepts of "Organizational Distance" between nodes and "Fitness" of a certain node were introduced, and a structural model, which was called DSHON(Dual Scale Heterogeneous Organization Network model),was proposed for eGON accordingly. The proposed model was based on the structure of tree and the network performance was promoted by adding shortcuts to the original tree according to the organizational distance between and the fitness of the nodes. The architecture, construction and maintenance mechanism, routing maintenance protocol and an organizational distance priority routing algorithm were developed for eGON. Simulations were performed for the proposed message routing algorithm and the results demonstrate the effectiveness and efficiency of the algorithm.