Method for adaptive routing in hierarchical networks

Abstract

ABSTRACT. The invention relates to a method for routing packets in a hierarchical network formed by a plurality of routers, each router including local ports and global ports and each comprising a plurality of virtual channels. The routers form groups and the different routers from a single group are interconnected by means of a connection topology using local links joining pairs of local ports, and the different groups are interconnected by means of a connection topology using global links joining pairs of global ports. The method is configured to use hops through said links according to minimal and non-minimal routes. The hops that involve non-minimal routes can be made via both global and local links. The number of virtual channels required in each local and global port is determined simply by the length of a maximum allowed route that does not use local misrouting. For this purpose, a total order is used on the path of the virtual channels, which is violated when a local misrouting occurs.

RESUMEN. Método de encaminamiento de paquetes en una red directa jerárquica formada por una pluralidad de encaminadores, cada uno con puertos de tipo local y puertos de tipo global; cada puerto comprende una pluralidad de canales virtuales; dichos encaminadores forman grupos, donde los diferentes encaminadores de un mismo grupo están interconectados mediante una topología conexa empleando enlaces de tipo local uniendo parejas de puertos de tipo local, y los diferentes grupos están interconectados mediante una topología conexa empleando enlaces de tipo global uniendo parejas de puertos de tipo global. El método está configurado para emplear saltos por dichos enlaces de acuerdo a rutas mínimas y no mínimas; los saltos que implican rutas no mínimas pueden realizarse tanto a través de enlaces globales como locales. El número de canales virtuales necesarios en cada puerto local y global viene determinado solamente por la longitud de una ruta máxima permitida que no emplea misrouting de tipo local, empleando para ello un orden total en el recorrido de los canales virtuales, que se viola cuando se realiza un misrouting local.