System for communicating labeled routing trees to establish preferred paths and source routes with local identifiers in wireless computer networks

Abstract

One or more labeled routing trees (LRTs) are produced at a router of a computer network according to a shortest path determination made over a partial topology graph of the network, which graph is produced according to knowledge of adjacent links of the router and one or more LRTs of neighboring routers. The LRTs of the router may be updated in response to receipt of routing state update messages, and such messages may include local link identifiers assigned by a head of a link to which the identifiers pertain, and node parameters of a tail of the link to which the local link identifiers pertain. The routing state update messages may be transmitted within the network: (i) in response to a new destination node being detected by an existing node within the network, (ii) in response to a destination becoming unreachable by a collection of the existing nodes, (iii) in response to the change in the cost of a path to at least one destination exceeding a threshold and/or (iv) in situations where a routing loop may be encountered among two or more of the nodes of the network (e.g., at times when a path implied in the LRT of the router leads to a loop).

1 - 27 . (Canceled)  
     
     
         28 . A method for routing information along preferred paths in a computer network in which a plurality of routers are interconnected by communication links, comprising: 
 forming a partial topology graph for a router by combining link-state information of each adjacent link, router-state information of each adjacent router, and link-state information and node-state information of each link adjacent to each adjacent router; and    computing a plurality of labeled routing trees (LRT) for the router using only the partial topology graph, each LRT corresponding to a type of service of the computer network, each LRT specifying a preferred path from the router to each of a plurality of destination routers in the network.    
     
     
         29 . The method of  claim 28  wherein the LRTs of the router are updated in response to receipt of routing state update messages.  
     
     
         30 . The method of  claim 29  wherein the routing state update messages include one or more local link identifiers, each local link identifier assigned by a head-of-link router to which the identifier pertains.  
     
     
         31 . The method of  claim 30  wherein the routing state update messages further include router parameters of a tail-of-link router to which a local link identifier pertains.  
     
     
         32 . A source routing protocol, for a computer network in which a plurality of routers are interconnected by communication links, comprising distributing, among the plurality of routers of the computer network, a local link identifier corresponding to each router within routing state update messages, the routing state update messages including a link-state information and a node-state information, 
 wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network.    
     
     
         33 . The source routing protocol of  claim 32  wherein the local link identifiers are each assigned by a head-of-link router to which the identifiers pertain.  
     
     
         34 . The source routing protocol of  claim 32  wherein the routing state update messages include state parameters for tail-of-link routers to which the identifiers pertain.  
     
     
         35 . The source routing protocol of  claim 32 , further comprising distributing labeled routing trees of the routers of the computer network among the routers.  
     
     
         36 . The source routing protocol of  claim 35  wherein each router of the computer's network distributes its labeled routing trees to adjacent routers.  
     
     
         37 . The source routing protocol of  claim 36  wherein each router of the computer network maintains one labeled routing tree per type of service offered in the network.  
     
     
         38 . The source routing protocol of  claim 36  wherein each router generates its labeled routing trees according to a partial topology graph derived from the router's adjacent links and labeled routing trees of neighboring routers.  
     
     
         39 . The source routing protocol of  claim 38  wherein the labeled routing trees of a router are generated by applying a path selection algorithm to the partial topology graph, the partial topology graph including a) link-state information of adjacent links and b) link-state information and router-state information of adjacent routers.  
     
     
         40 . The source routing protocol of  claim 39  wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network.  
     
     
         41 . The source routing protocol of  claim 40  wherein the labeled routing trees of routers in the computer network are updated in response to receipt of one or more routing state update messages.  
     
     
         42 . The source routing protocol of  claim 41  wherein labeled routing trees are updated according to whether an optimum routing approach or a least overhead routing approach is used within the computer network.  
     
     
         43 . The source routing protocol of  claim 32  wherein the routing state update message includes performance characteristic information and addressing information for a link of the computer network and a tail-of-link router pertaining to the link.  
     
     
         44 . The source routing protocol of  claim 43  wherein the performance characteristics of the link are selected from the group consisting of link delay, link cost, available bandwidth, reliability, and combinations thereof.  
     
     
         45 . The source routing protocol of  claim 43  wherein the routing state update message further includes addressing information of the link comprising a local link identifier assigned to the link by a head-of-link router.