Space-efficient source routing

Abstract

The required length of a route descriptor in a source routing system is obtained by inserting an implied exit field, use of run-length encoding, and use of variable-length encoding. In the variable-length encoding, codes having lesser bits are reserved for preferred directions. Preferred direction may be encoded in the routing header, and it may be implied by the arrival port.

What is claimed is:  
     
         1 . A router using source routing for multiple hops of a route through a network, each of the multiple hops being encoded at a source by port descriptors in a header of a packet, the router comprising: 
 input router storage which receives port descriptors from a routing header of a packet, the port descriptors source coding each hop of the route through the network;    a port descriptor extractor which extracts a next hop port descriptor from the routing header; and    a header updating circuit which generates a new header representing a remaining route, the header updating circuit inserting an implied exit field in the new header.    
     
     
         2 . A method of routing multiple hops of a route through a network, each of the multiple hops being encoded at a source by port descriptors in a header of a packet, the method comprising, at a router: 
 storing port descriptors from a routing header of a packet, the port descriptors source coding each hop of the route through the network;    extracting a next hop port descriptor from the routing header; and    inserting an implied exit field in generating a new routing header representing a remaining route.