Local memory requirement of universal routing schemes

摘要: In this paper we deal with the compact routing problem that is of implementing schemes use a minimum memory size on each router A universal scheme applies to all networks Peleg and Upfal showed one can not implement less than total n s bits for any satisfying maximum ratio between lengths paths shortest stretch factor bounded by Fraigniaud Gavoille improve bound proving factors at most in worst case Recently P erenn es fact routers an node network may require up logn path extend result showing constant even if length twice distance its source destination