Source: http://www.google.com/patents/US7768926?dq=4200770
Timestamp: 2014-03-17 10:23:43
Document Index: 143537304

Matched Legal Cases: ['art� 401', 'art� 405', 'art� 405', 'art� 405', 'art� 405', 'art� 410', 'Application No. 095126422', 'Application No. 095126419']

Patent US7768926 - Effective bandwidth path metric and path computation method for wireless ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsEnhanced mesh network performance is provided by computation of a path metric with respect to multi-hop paths between nodes in a mesh network and determination of a path through the mesh network that is optimal according to the path metric. Information is communicated in the mesh network according to...http://www.google.com/patents/US7768926?utm_source=gb-gplus-sharePatent US7768926 - Effective bandwidth path metric and path computation method for wireless mesh networks with wired linksAdvanced Patent SearchPublication numberUS7768926 B2Publication typeGrantApplication numberUS 11/618,073Publication dateAug 3, 2010Filing dateDec 29, 2006Priority dateMar 9, 2006Also published asCA2645336A1, CN101421982A, CN101421982B, US8498211, US20070211636, US20110075566Publication number11618073, 618073, US 7768926 B2, US 7768926B2, US-B2-7768926, US7768926 B2, US7768926B2InventorsBhargav Ramachandra Bellur, Ravi Prakash, Amar Singhal, Jorjeta Gueorguieva JetchevaOriginal AssigneeFiretide, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (20), Non-Patent Citations (18), Referenced by (9), Classifications (12), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetEffective bandwidth path metric and path computation method for wireless mesh networks with wired linksUS 7768926 B2Abstract Enhanced mesh network performance is provided by computation of a path metric with respect to multi-hop paths between nodes in a mesh network and determination of a path through the mesh network that is optimal according to the path metric. Information is communicated in the mesh network according to the determined path. Nodes in the mesh network are enabled to communicate via one or more wireless links and/or one or more wired links. The path metric optionally includes an effective bandwidth path metric having elements (listed from highest to lowest conceptual priority) including an inverse of a sustainable data rate, a number of wireless links, and a number of wireless and wired links. The sustainable data rate is a measure of communication bandwidth that is deliverable by a path for a period of time. Accounting is made for interference between contiguous wireless links operating on the same channel.
India Application Serial No. 627/DEL/2006, filed Mar. 9, 2006, first named inventor Bhargav Ramachandra Bellur, and entitled EFFECTIVE BANDWIDTH PATH METRIC AND PATH COMPUTATION ALGORITHM FOR WIRELESS MESH NETWORKS WITH WIRED LINK. BACKGROUND 1. Field
SYNOPSIS The invention may be implemented in numerous ways, including as a process, an article of manufacture, an apparatus, a system, a composition of matter, and a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. In general, the order of the steps of disclosed processes may be altered within the scope of the invention. The Detailed Description provides an exposition of one or more embodiments of the invention that enable improvements in performance, efficiency, and utility of use in the field identified above. The Detailed Description includes an Introduction to facilitate the more rapid understanding of the remainder of the Detailed Description. The Introduction includes Example Embodiments of systems, methods, and computer readable media in accordance with the concepts taught herein. As is discussed in more detail in the Conclusions, the invention encompasses all possible modifications and variations within the scope of the issued claims.
BRIEF DESCRIPTION OF DRAWINGS FIG. 1 illustrates an embodiment of a mixed wireless and wired mesh network.
DETAILED DESCRIPTION A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with the embodiments. It is well established that it is neither necessary, practical, or possible to exhaustively describe every embodiment of the invention. Thus the embodiments herein are understood to be merely illustrative, the invention is expressly not limited to or by any or all of the embodiments herein, and the invention encompasses numerous alternatives, modifications and equivalents. To avoid monotony in the exposition, a variety of word labels (including but not limited to: first, last, certain, particular, select, and notable) may be applied to separate sets of embodiments; as used herein such labels are expressly not meant to convey quality, or any form of preference or prejudice, but merely to conveniently distinguish among the separate sets. Wherever multiple embodiments serve to illustrate variations in process, method, and/or program instruction features, other embodiments are contemplated that in accordance with a predetermined or a dynamically determined criterion perform static and/or dynamic selection of one of a plurality of modes of operation corresponding respectively to a plurality of the multiple embodiments. Numerous specific details are set forth in the following description to provide a thorough understanding of the invention. The details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of the specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured.
In the figure, element identifiers beginning with �100� are associated with nodes of the mesh network (such as Nodes 100A and 100B). Element identifiers beginning with �12� are representative of wireless interfaces, with the third character of the identifier describing a channel associated with the wireless interface, and the last character of the identifier indicating the node the wireless interface is included in. An example of a wireless interface identifier is wireless interface 125F operating on channel 5 and included in Node 100F. Element identifiers starting with �111� represent wireless links formed via wireless interfaces, with the fourth and last characters of the identifier indicating nodes the wireless link couples. An example of a wireless link is wireless link 111EH coupling Nodes 100E and 100H. Element identifiers starting with �110� are used for wired links, with the fourth and last characters of the identifier indicating nodes the wired link couples. An example of a wired link is wired link 110BE coupling Nodes 100B and 100E.
Example Embodiments In concluding the introduction to the detailed description, what follows is a collection of example embodiments, providing additional description of a variety of embodiment types in accordance with the concepts taught herein; these examples are not meant to be mutually exclusive, exhaustive, or restrictive; and the invention is not limited to these example embodiments but rather encompasses all possible modifications and variations within the scope of the issued claims.
A path metric called �effective bandwidth� is defined that takes into account both wireless and wired links, and incorporates the available bandwidth along each link in the path along with effects of interference of consecutive wireless links in the path that are assigned to the same channel. A path computation technique is then defined that given a set of links, computes the best possible paths from a node to all other nodes reachable through the set of links, according to the effective bandwidth path metric. The path metric incorporates the effects of interference along a multi-hop path that includes wireless and wired links, where each node optionally has more than one wireless and/or wired interface.
(InvSR1/InvSR2<(1−Delta)) OR ((1−Delta)<=InvSR1/InvSR2<=1) AND (W1<W2) OR ((1−Delta)<=InvSR1/InvSR2<=1) AND (W1==W2) AND (N1<N2)
vectorSR(P*)=(SR(P*, 0), SR (P*,1) . . . SR(P*, m)). First consider Set 0, i.e. all wired links within the segment P*. Since transmissions on wired links do not interfere with each other, the sustainable data rate across wired links in the segment P* is given by:
SR(P*, 0)=minimum{1<=i<=n such that link i is a wired link}B(i). Next consider Set k, i.e. all wireless links within segment P* that are assigned to channel k. Let Assign(i, k) be a Boolean variable that is true if link i is assigned to channel k. Hence, the time required to transmit a bit across all the hops which are on channel k is given by:
T(P*,k)=sum{1<=i<=n such that Assign(i, k) is True}1/B(i). In the worst case, all links that are assigned to channel k within the segment P* are within interference range of each other. Recall that the sustainable data rate across all the wireless links in Set k within the segment P* is given by SR(P*, k). Therefore, a lower bound on the sustainable data rate SR(P*, k) is given by the inequality SR(P*, k)>=1/T(P*, k). The inequality evolves into a strict equality whenever all the wireless links within a segment assigned to channel k interfere with one another. Hence:
1/SR(P*, k)<=sum{1<=i<=n such that Assign(i, k) is True}1/B(i ) In some usage scenarios, all the wireless links within a segment that are assigned to the same channel do not interfere with each other. This occurs, for example, when the links are not within interference range of one another. In some environments, the interference range is larger than the transmission range, and in some situations is twice as large as the transmission range. Assume that the bandwidth reduction (or degradation) across a sequence of wireless hops ceases (or is ignorable) after IntfHops hops, where IntfHops is a small integer, such as 4 or 5. See the section �Contiguous Wireless Links Sustainable Data Rate�, located elsewhere herein, for details of a computation of the sustainable data rate across a contiguous sequence of wireless links on the same channel assuming bandwidth degradation after IntfHops is ignorable.
SR(P)=minimum(SR(P1), SR( P2) . . . SR(Ph)), and vectorSR(P)=vectorMin(SR(P1), SR(P2) . . . SR(Ph));
InvSR(P)=maximum(InvSR(P1), InvSR(P2) . . . InvSR(Ph)), and vectorInvSR(P)=vectorMax(InvSR( P1), InvSR(P2) . . . InvSR(Ph));
InvSR(X, wired)=1/bandwidth(wired link 110BE); // Note that �wired� is also optionally known as channel 0 InvSR(X, channel 3)=1/bandwidth(wireless link 111DG)+1/bandwidth(wireless link 111DE); and InvSRSegmentX=maximum(InvSR(X, wired), InvSR(X, channel 3)). For segment Y (from Node 100B to Node 100C):
InvSR(Y, wired)=1/bandwidth(wired link 110CS); InvSR(Y, channel 2)=1/bandwidth(wireless link 111BS); and InvSRSegmentY=maximum(InvSR(Y, wired), InvSR(Y, channel 2)). The (inverse of) the sustainable data rate for the entire path from Node 100G to Node 100C is thus the scalar value:
InvSR(wired)=maximum(InvSR(X, wired), InvSR(Y, wired)). The effective bandwidth metric calculation then combines the inverse sustainable data rate for the path along with the number of wireless and total links for the path. According to the path in FIG. 2, the number of wireless links along the path is three, and the total number of links is five.
The path computation technique maintains, for any node x, selected variables associated with up to two paths. For each of the paths, the variables maintained optionally include respective cost and predecessor information. In some embodiments, the variables maintained omit other information about the paths (such as nodes along each path). In the following discussion, a prefix of �0� denotes a wired (or Ethernet) interface while a prefix of �1� denotes a wireless interface. The paths are:
Path[0](x): The currently known minimum cost path from node src to node x such that the last link is an Ethernet link; and Path[1](x): The currently known minimum cost path from node src to node x such that the last link is a wireless link. Let Cost[i](x) denote the cost of the path Path[i](x), for i=0, 1. Cost[i](x) is represented by a 3-tuple where the first entry is a vector. Thus for i=0, 1:
Cost[i](x)=(InvSR[i](x), num_wireless_links[i](x), num_hops[i](x)). Let Cost(x) denote the lexicographic-computed minimum of Cost[0](x) and Cost[1](x). Hence:
Pred[i](x)=(parent[i](x), type_from_parent[i](x)). Similar to Dijkstra's algorithm, the path computation technique proceeds by �marking� nodes one at a time. A set of �unmarked� nodes is maintained, and during each iteration a one node y among the unmarked nodes having the minimum Cost(y) is �marked�. Then variables Cost[0](x) and Cost[1](x) of all unmarked nodes that are neighbors of the marked node y are updated (or reduced) via a process termed relaxation (see the section �Path Computation Implementation�, located elsewhere herein, for more information). Appropriate variables are maintained and updated for up to two paths (corresponding to wired and wireless terminating links), thus enabling computation of an effective bandwidth path metric corresponding to possible optimal paths.
WirelessHops[1](v)�Number of contiguous wireless links immediately preceding node v in the best known path to node v such that the last link is a wireless link; and WirelessTotalInvSR[1](v)�Inverse of the sustainable data rate on the entire sequence of contiguous wireless links immediately preceding node v in the best known path to node v such that the last link is a wireless link. In some embodiments, the path computation assumes that any two wireless links (of a contiguous sequence of wireless links) that are on the same channel do interfere with each other. Even though interference within a contiguous sequence of wireless links ceases (or in some circumstances is ignorable) after links are IntfHops apart, the assumption tends to penalize paths with more wireless links even when the paths have higher sustainable data rates than paths with fewer wireless links. The assumption is in addition to penalizing paths having a similar sustainable data rate but a higher number of wireless links (i.e. the number of wireless links is second in the lexicographic ordering associated with path comparison). Use of more wireless resources creates interference for nearby links and networks and in some usage scenarios is undesirable. In some embodiments, the path computation assumes a penalty on a path proportional to the number of wireless links in the path while assuming interference between wireless links is negligible after IntfHops. The proportional penalty reduces apparent sustainable data rate by a fixed value at each wireless link even though the respective wireless link do not, in some usage scenarios, reduce the sustainable data rate when there is no additional interference experienced. See the section �Contiguous Wireless Links Sustainable Data Rate�, located elsewhere herein, for further details.
bandwidth(111BS)=40, bandwidth(111ES)=30, bandwidth(110BE)=30, and bandwidth(111BK)=40. The path computation considers two paths from Node 100S to Node 100B. The paths correspond to the previous link being a wired (Ethernet) link or the previous link being a wireless link. The variables corresponding to the first (previous link is wired) of the two paths are:
Path[0](Node 100B): [Node 100S]−[Node 100E]−[Node 100B] is a minimum cost path from Node 100S to Node 100B such that the previous link is an Ethernet link; Cost[0](Node 100B)=(maximum(1/bandwidth(link 111ES), 1/bandwidth(link 110BE)), 1, 2); and Pred[0](Node 100B)=(Node 100E, 1 (wireless)). The variables corresponding to the second (previous link is wireless) of the two paths are:
Path[1](Node 100B): [Node 100S]−[Node 100B] is a minimum cost path from Node 100S to Node 100B such that the previous link is a wireless link; Cost[1](Node 100B)=(1/bandwidth(link 111BS), 1, 1); and Pred[1](Node 100B)=(Node 100S, null). If bandwidth(link 111ES) is 30 and bandwidth(link 111BS) is 40, then in terms of the path metric, Path[1](Node 100B) has lower cost than Path[0](Node 100B) since 1/30 is greater than 1/40. However, because of interference between transmissions on two wireless links operating on the same channel (links 111BS and 111BK), the relative cost is reversed at Node 100K.
Path [0] (Node 100K): No path exists; and Cost(Node 100K)=(vectorInfinity, Infinity, Infinity). The variables corresponding to the second of the two paths (i.e. where the link preceding Node 100K is a wireless link) are selected from the minimum of two candidate paths:
Path[1](Node 100K): [Node 100S]−[Node 100B]−[Node 100K], i.e. Path[1](Node 100B) concatenated with link 111BK; and Cost[1](Node 100K)=(1/bandwidth(link 111BS)+1/bandwidth(111BK), 2, 2), since transmissions on the two wireless links 111BS and 111BK do interfere with each other. Candidate2:
Path[1](Node 100K): [Node 100S]−[Node 100E]−[Node 100B]−[Node 100K], i.e. Path[0](Node 100B) concatenated with link 111BK; and Cost[1](Node 100K)=(maximum(1/bandwidth(link 111ES), 1/bandwidth(link 110BE), 1/bandwidth(link 111BK)), 2, 3).
G=(V, E): A directed weighted graph, with a vertex set V (corresponding to nodes of the mesh network) and an edge set E (corresponding to wired and wireless links of the mesh network; src: The source node for which all shortest paths are being computed;
Q: A queue containing all nodes from V not already in S (i.e. all nodes not having final best paths computed with respect to src); Adj[v]: The neighbors of node v (i.e. those nodes reachable from v in one wired or wireless hop); and b(u, v): The available link bandwidth on link(u, v). The path metric corresponding to a path is a 3-tuple:
vectorInvSR is a vector representation of the inverse of the sustainable data rate along the path�in a single wireless interface scenario, the vector is size 2 (i.e. m+1 where m is one) where member 0 of the vector denotes Ethernet (wired) and member 1 denotes wireless; num_wireless_links is the number of wireless links along the path; and num_hops is the total number of hops (or links), wired and wireless, along the path. Let Cost[0](v) be the (current minimum) cost metric of the best known path to node v such that the last link is an Ethernet (or wired) link. Also:
WirelessHops[1](v) is the number of contiguous wireless links immediately preceding node v in the best known path to node v such that the last link is a wireless link; and WirelessTotalInvSR[1](v) is the inverse of the sustainable data rate on the entire sequence of contiguous wireless links immediately preceding node v in the best known path to node v such that the last link is a wireless link. Let Cost(v) denote the minimum of Cost[0](v) and Cost[1](v). Thus:
FIG. 4A illustrates a top-level flow diagram of an embodiment of the path computation. Flow begins (�Start� 401) and continues to set various variables relating to the computation to starting values (�Initialize� 402). It is then determined if there are any remaining nodes to process (�More Nodes?� 403). If not (�No� 403N), then processing is complete (�End� 499). If so (�Yes�, 403Y), then processing continues to select another node to process (�Next Node� 404). Best path information for all nodes adjacent to the selected node (i.e. one link away according to the topology of the mesh network) is then updated (�Process Node Neighbors� 405). Processing then flows back to determine if there are additional nodes to process (�More Nodes� 403).
Processing relating to �Initialize� 402 is described by the following pseudo-code:
For each node v in V { vectorInvSR[0](v) = vectorInfinity; num_wireless_links[0](v) = Infinity; num_hops[0](v) = Infinity; vectorInvSR[1](v) = vectorInfinity; num_wireless_links[1](v) = Infinity; num_hops[1](v) = Infinity; parent[0](v) = null; type_from_parent[0](v) = NA; parent[1](v) = null; type_from_parent[1](v) = NA; // vectorInvSR[0](src) = 0; num_wireless_links[0](src) = 0; num_hops[0](src) = 0; vectorInvSR[1](src) = 0; num_wireless_links[1](src) = 0; num_hops[1](src) = 0; WirelessHops[1](src) = 0; WirelessTotalInvSR[1](src) = 0; } S = nil; Q = V; where vectorInvSR is of size two and all elements therein are set to either zero or infinity as appropriate.
Processing relating to �More Nodes?� 403 is described by the following pseudo-code:
Processing relating to �Next Node� 404 is described by the following pseudo-code:
S = AddNode(S, u); Q = DeleteNode(Q, u); where u is a node (or vertex in a directed graph context) such that:
FIG. 4B illustrates an embodiment of processing associated with �Process Node Neighbors� 405 of FIG. 4A. Processing begins (�Start� 405A) and continues to check if all neighbor nodes have been completed (�All Processed?� 405B). If so (�Yes� 405BY), then processing is complete (�End� 405Z). If not (�No� 405BN), then processing proceeds to select a remaining node (�Next Neighbor Node� 405C). Flow then continues to determine whether the link type associated with the selected node is wired (i.e. Ethernet) or wireless (�Link Type?� 405D). If the link is wired (�Wired� 405D0), then flow proceeds to determine if the link enables a better path than previously known (�Evaluate Wired Link� 405E). If the link is wireless (�Wireless 405D1), then flow continues to determine if the link enables a better path than what has been discovered before (�Evaluate Wireless Link� 405F). Processing to evaluate a wireless link is slightly different than processing a wired link, as described with respect to the FIG. 4C. After completing evaluation of the link (via either of �Evaluate Wired Link� 405E or �Evaluate Wireless Link� 405F) flow proceeds back to determine if more remain to be processed (�All Processed?� 405B).
Processing associated with �All Processed?� 405B is described by the following pseudo-code:
For each node v in Adj[u] where processing associated with �Next Neighbor Node� 405C skips node v if v is already present in S.
Processing associated with �Link Type?� 405D is described by the following pseudo-code:
FIG. 4C illustrates an embodiment of processing associated with either of �Evaluate Wired Link� 405E and �Evaluate Wireless Link� 405F of FIG. 4B. Processing begins (�Start� 405EF.1) and proceeds to determine if a new best path is available based on a link currently being evaluated. The currently evaluated link is processed twice, according to two contexts, a first context where the last link in the path thus far is a wired link, and a second context where the last link in the path thus far is a wireless link. The first context (�Evaluate Wired Last Link Path� 405EF.2) and the second context (�Evaluate Wireless Last Link Path� 405EF.3) are evaluated independently and in any order (such as in parallel as illustrated), in some embodiments. After the evaluations, the minimum of the two is chosen (�Select Minimum� 405EF.4). Processing then continues to determine if a new best path has been discovered (�Better?� 405EF.5). If not (�No� 405EF.5N), then processing is complete (�End� 405EF.99). If so (�Yes� 405EF.5Y), then flow continues to save new information based on the new path (�Update Parent, Cost, Type� 405EF.6). Processing is then complete (�End� 405EF.99).
While the illustrated flow is representative of processing for either of a wired (or Ethernet) link and a wireless link, the wireless link processing is modified from and is described herein after the wired link processing. Processing associated with �Start� 405EF.1 during evaluation of a wired link is described by the following pseudo-code:
Processing associated with �Evaluate Wired Last Link Path� 405EF.2 further during evaluation of a wired link is described by the following pseudo-code:
Processing associated with �Evaluate Wireless Last Link Path� 405EF.3 is described by the following pseudo-code:
Processing associated with �Select Minimum� 405EF.4 is described by the following pseudo-code:
Processing associated with �Better?� 405EF.5 is described by the following pseudo-code:
Processing associated with �Update Parent,Cost,Type� 405EF.6 is described by the following pseudo-code:
parent[0](v) = u; If(candidate_metric0 == min_metric) Cost[0](v) = candidate_metric0; type_from_parent[0](v) = 0 // Ethernet (wired) link If(candidate_metric1 == min_metric) Cost[0](v) = candidate_metric1; type_from_parent[0](v) = 1 // Wireless link The foregoing completes the processing during evaluation of a wired link.
Processing associated with a wireless link is a variation compared to the processing associated with a wireless link, as the following pseudo-code illustrates. Processing associated with �Start� 405EF.1 during evaluation of a wireless link is described by the following pseudo-code:
Processing associated with �Evaluate Wired Last Link Path� 405EF.2 further during evaluation of a wireless link is described by the following pseudo-code:
parent[1](v) = u; If(candidate_metric0 == min_metric) Cost[1](v) = candidate_metric0; type_from_parent[1](v) = 0 // Ethernet (wired) link WirelessHops[1](v) = 1; WirelessTotalInvSR[1](v) = 1/b(u,v) If(candidate_metric1 == min_metric) Cost[1](v) = candidate_metric1; type_from_parent[1](v) = 1 // Wireless link; WirelessHops[1](v) = 1 + WirelessHops[1](u); WirelessTotalInvSR[1](v) = WirelessTotalInvSR[1](u) + 1/b(u,v) The foregoing completes the processing during evaluation of a wireless link.
FIG. 4D illustrates an embodiment of processing associated with determining an effective sustainable data rate along a contiguous sequence of wireless links. Processing begins (�Start� 410) and proceeds to determine if the number of contiguous links equals or surpasses a threshold (�>=IntfHops Links?� 411). If not (�no� 411N), then adding reciprocal bandwidths over the path being processed is sufficient (�Sum Inverse Rates� 412) to determine an effective (inverse) data rate and processing is then complete (�End� 498).
If the threshold is met or exceeded (�Yes� 411Y), then an effective (inverse) bandwidth is computed for every contiguous sequence of wireless links within the path having a length equal to the threshold, and the minimum chosen as the effective (inverse) data rate. Processing for the sequences begins by determining if more sequences remain to be processed in the path (�Another Sequence?� 421). If not (�No� 421), then the smallest data rate of all of the sequences is chosen (�Select Minimum� 422). Processing is then complete (�End� 498). If more sequences remain to be processed (�Yes� 421Y), then flow continues to determine another sequence to process (�Next Sequence� 423). The effective (inverse) data rate for the next sequence is then computed (�Determine Inverse Rate� 424) and then processing flows back to determine if further sequences remain (�Another Sequence?� 421).
vectorInvSR is a vector denoting the reciprocal of available bandwidth along each link of a contiguous sequence of wireless links of length p=|vectorInvSR|, where the ith entry of the vector is denoted InvSR(i), for i=1, 2 . . . p; and b(l) is available bandwidth of the wireless link appended at the end of the path.
Processing associated with �>=IntfHops Links?� 411 is described by the following pseudo-code:
Processing associated with �Sum Inverse Rates� 412 is described by the following pseudo-code:
Processing associated with �Another Sequence?� 421, �Select Minimum� 422, �Next Sequence� 423, and �Determine Inverse Rate� 424 in combination is described by the following pseudo-code:
InvSR(p+1) = 1/b(l); // Append entry 1/b(l) at the end of the InvSR vector, resulting in a vector size of p+1 FinalInvSR = sum{i=1 to IntfHops} InvSR(i) For(j = 1; j <= p+1 − IntfHops; ++j) { CandidateInvSR = 0; For (i =1; i <= IntfHops; ++i) CandidateInvSR += InvSR(j+i) If(CandiadateInvSR > FinalInvSR) FinalInvSR = CandiadteInvSR } return FinalInvSR Node Hardware and Software
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6965575 *Jun 24, 2003Nov 15, 2005Tropos NetworksSelection of routing paths based upon path quality of a wireless mesh networkUS6993034Oct 15, 1998Jan 31, 2006International Business Machines CorporationCluster destination address table�IP routing for clustersUS7366120 *Oct 18, 2004Apr 29, 2008Nortel Networks, LtdMethod and apparatus for improving quality of service over meshed bachaul facilities in a wireless networkUS20010032272Apr 18, 2001Oct 18, 2001Nec CorporationQoS-based shortest path routing for hierarchical communication networkUS20040001008Jun 27, 2002Jan 1, 2004Shuey Kenneth C.Dynamic self-configuring metering networkUS20040008663Jun 24, 2003Jan 15, 2004Devabhaktuni SrikrishnaSelection of routing paths based upon path quality of a wireless mesh networkUS20040190454Dec 9, 2003Sep 30, 2004Anritsu CorporationMesh network bridges making operable spanning tree protocol and line fault backup protocol in optimized forwarding environmentUS20040215687Apr 28, 2003Oct 28, 2004Landmark Networks, Inc.Wireless service point networksUS20040235468May 19, 2003Nov 25, 2004Luebke Charles J.Wireless network clustering communication system, wireless communication network, and access port for sameUS20040264466Jun 25, 2003Dec 30, 2004Nokia CorporationBluetooth personal area network routing protocol optimization using connectivity metricUS20060083255Oct 18, 2004Apr 20, 2006AlcatelAllocating bridge priorities in bridged networkUS20060256724May 10, 2005Nov 16, 2006Luca MartiniMethod of determining transit costs across autonomous systemsUS20070184864Mar 2, 2005Aug 9, 2007Koninklijke Philips Electronics, N.V.Making time-of-flight measurements in master/slave and ad hoc networks by eaves-dropping on messagesUS20080107034Jan 16, 2008May 8, 2008Jorjeta JetchevaRoute optimization for on-demand routing protocols for mesh networksUS20080112422Jan 16, 2008May 15, 2008Jorjeta JetchevaMethod for Enabling the Efficient Operation of Arbitrarily Interconnected Mesh NetworksUS20090190531Apr 3, 2009Jul 30, 2009Jorjeta JetchevaMesh Node Mobility Across Static and Mobile Mesh NetworksWO2007013914A1Jul 19, 2006Feb 1, 2007Firetide IncMethod for enabling the efficient operation of arbitrarily interconnected mesh networksWO2007015822A1Jul 18, 2006Feb 8, 2007Firetide IncRoute optimization for on-demand routing protocols for mesh networksWO2007103837A1Mar 4, 2007Sep 13, 2007Bellur BhargavEffective bandwidth path metric and path computation method for wireless mesh networks with wired linksWO2008046089A2Oct 13, 2007Apr 17, 2008Firetide IncMesh node mobility across static and mobile mesh networks* Cited by examinerNon-Patent CitationsReference1 *Akyildiz et al, A Survey on Wireless Mesh Networks, IEEE, 8 pages, Sep. 2005.2Ashwin Sridharan, et al.; On the Impact of Aggregation on the Performance of Traffic-Aware Routing. In proceedings of the 17th International Teletraffic Congress, Salvador da Bahia, Brazil, Sep. 2001, 13 pgs.3 *Bruno et al, Mesh Networks: Commodity Multihop Ad Hoc Networks, IEEE, 9 pages, Mar. 2005.4David A. Maltz, et al.; The Effects of On-Demand Behavior in Routing Protocols for Multi-Hop Wireless Ad Hoc Networks. IEEE Journal on Selected Areas in Communications Special Issue on Mobile and Wireless Networks, Aug. 1999, 20 pgs.5David B. Johnson, et al.; The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks; IETF MANET Working Group, Feb. 21, 2002, 85 pgs (pp. i-81).6International Preliminary Report and Written Opinion for PCT/US2007/063247, mailed Sep. 9, 2008; 6 pgs.7Jorjeta G. Jetcheva, et al.; Design and Evaluation of a Metropolitan Area Multitier Wireless Ad Hoc Network Architecture; Proceedings of the 5th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA 2003), IEEE, Monterey, CA, Oct. 2003, 12 pgs.8Jorjeta G. Jetcheva, et. al.; A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks, Jul. 20, 2001, 14 pgs. (pp. i-11).9Jorjeta G. Jetcheva, et. al.; Adaptive Demand-Driven Multicast Routing in Multi-Hop Wireless Ad Hoc Networks. In proceedings of the ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Long Beach, CA, Oct. 2001, 12 pgs.10Jorjeta G. Jetcheva, et. al.; The Adaptive Demand-Driven Multicast Routing Protocol for Mobile Ad Hoc Networks, Jul. 13, 2001, 67 pgs. (pp. i-63).11Josh Broch et al.; A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, ACM, Dallas, TX, Oct. 1998, 13 pgs.12Nina Taft et al.; Understanding Traffic Dynamics at a Backbone POP. SPIE ITCOM+ OPTICOMM Workshop on Scalability and Traffic Control in IP Networks, Denver, CO, Aug. 2001, 7 pgs.13 *Raniwala et al, Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Networks, IEEE, 12 pages, 2005.14Search Report for Patent Application ROC (Taiwan) Patent Application No. 095126422 (Translation), Date of Completion: Feb. 26, 2009; 1 pg.15Search Report ROC (Taiwan) Patent Application No. 095126419 (Translation), Date of Completion of the search: Apr. 28, 2009; 2 pgs.16Supratik Bhattacharyya, et al.; Geographical and Temporal Characteristics of Inter-POP Flows: View from a Single POP. European Transactions on Telecommunications (ETT), vol. 13, No. 1. pp. 5-22, Jan./Feb. 2002, 18 pgs.17Supratik Bhattacharyya, et al.; POP-Level and Access-Link-Level Traffic Dynamics in a Tier-1 POP. ACM SIGCOMM Internet Measurement Workshop (IMW), San Francisco, Nov. 2001, 15 pgs.18Yih-Chun Hu, et al.; Efficient Security Mechanisms for Routing Protocols; (Slightly revised post-proceedings version of Cite No. C3, web-published at http://www.monarch.cs.rice.edu/papers.html), Feb. 2003. 17 pgs.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8161191 *Jun 22, 2010Apr 17, 2012Silver Spring Networks, Inc.Method and system for providing network and routing protocols for utility servicesUS8279870Aug 1, 2007Oct 2, 2012Silver Spring Networks, Inc.Method and system of routing in a utility smart-grid networkUS8396987Mar 13, 2012Mar 12, 2013Silver Spring Networks, Inc.Method and system for providing network and routing protocols for utility servicesUS8498211 *Jul 28, 2010Jul 30, 2013Firetide, Inc.Effective bandwidth path metric and path computation method for wireless mesh networks with wired linksUS8559447Jan 22, 2008Oct 15, 2013Firetide, Inc.Utilizing multiple mesh network gateways in a shared access networkUS8593253 *Jun 9, 2010Nov 26, 2013Gm Global Technology Operations, Inc.Systems and methods for efficient authenticationUS20100299452 *Jun 22, 2010Nov 25, 2010Silver Spring Networks, Inc.Method and system for providing network and routing protocols for utility servicesUS20110075566 *Jul 28, 2010Mar 31, 2011Bhargav Ramachandra BellurEffective Bandwidth Path Metric and Path Computation Method for Wireless Mesh Networks with Wired LinksUS20110304425 *Jun 9, 2010Dec 15, 2011Gm Global Technology Operations, IncSystems and Methods for Efficient Authentication* Cited by examinerClassifications U.S. Classification370/238, 370/252, 370/338International ClassificationH04J3/14Cooperative ClassificationH04L43/0882, H04L45/124, H04L45/123, H04W40/02European ClassificationH04L45/123, H04L45/124, H04L43/08G1, H04W40/02Legal EventsDateCodeEventDescriptionFeb 4, 2013ASAssignmentEffective date: 20130204Owner name: FIRETIDE, INC., CALIFORNIAFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:SAND HILL VENTURE DEBT III, LLC;REEL/FRAME:029750/0476Owner name: SILICON VALLEY BANK, CALIFORNIAEffective date: 20130201Free format text: SECURITY AGREEMENT;ASSIGNOR:FIRETIDE, INC.;REEL/FRAME:029745/0148Sep 16, 2008ASAssignmentOwner name: SAND HILL VENTURE DEBT III, LLC, CALIFORNIAFree format text: SECURITY AGREEMENT;ASSIGNOR:FIRETIDE, INC.;REEL/FRAME:021531/0408Effective date: 20080430May 30, 2007ASAssignmentOwner name: FIRETIDE, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BELLUR, BHARGAV RAMACHANDRA;PRAKASH, RAVI;SINGHAL, AMAR;AND OTHERS;REEL/FRAME:019356/0548;SIGNING DATES FROM 20070402 TO 20070410Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BELLUR, BHARGAV RAMACHANDRA;PRAKASH, RAVI;SINGHAL, AMAR;AND OTHERS;SIGNING DATES FROM 20070402 TO 20070410;REEL/FRAME:019356/0548RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google