Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2007-01-02
2007-01-02
Caldwell, Andrew (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
10256168
ABSTRACT:
Routing table update messages that include both network-level and link-level addresses of nodes of a computer network are exchanged among the nodes of the computer network. Further, a routing table maintained by a first one of the nodes of the computer network may be updated in response to receiving one or more of the update messages. The routing table is preferably updated by selecting a next node to a destination node of the computer network only if every intermediate node in a path from the next node to the destination node satisfies a set of nodal conditions required by the first node for its path to the destination node and the next node offers the shortest distance to the destination node and to every intermediate node along the path from the next node to the destination node. The shortest distance to the destination node may be determined according to one or more link-state and/or node-state metrics regarding communication links and nodes along the path to the destination node. Also, the nodal characteristics of the nodes of the computer system may be exchanged between neighbor nodes, prior to updating the routing table. Preferred paths to one or more destination nodes may be computed according to these nodal characteristics, for example using a Dijkstra shortest-path algorithm.
REFERENCES:
patent: 4466060 (1984-08-01), Riddle
patent: 4987536 (1991-01-01), Humblet
patent: 5088032 (1992-02-01), Bosack
patent: 5115433 (1992-05-01), Baran et al.
patent: 5233604 (1993-08-01), Ahmadi et al.
patent: 5487064 (1996-01-01), Galand et al.
patent: 5509123 (1996-04-01), Dobbins et al.
patent: 5515508 (1996-05-01), Pettus et al.
patent: 5528593 (1996-06-01), English et al.
patent: 5548578 (1996-08-01), Matsune et al.
patent: 5557748 (1996-09-01), Norris
patent: 5572528 (1996-11-01), Shuen
patent: 5588121 (1996-12-01), Reddin et al.
patent: 5596719 (1997-01-01), Ramakrishnan et al.
patent: 5600635 (1997-02-01), Hamaki et al.
patent: 5600644 (1997-02-01), Chang et al.
patent: 5608721 (1997-03-01), Natarajan et al.
patent: 5633866 (1997-05-01), Callon
patent: 5638371 (1997-06-01), Raychaudhuri et al.
patent: 5652751 (1997-07-01), Sharony
patent: 5682382 (1997-10-01), Shepard
patent: 5721819 (1998-02-01), Galles et al.
patent: 5737318 (1998-04-01), Melnik
patent: 5805593 (1998-09-01), Busche
patent: 5845086 (1998-12-01), Doebrich et al.
patent: 5854899 (1998-12-01), Callon et al.
patent: 5881246 (1999-03-01), Crawley et al.
patent: 5905872 (1999-05-01), DeSimone et al.
patent: 5918016 (1999-06-01), Brewer et al.
patent: 5922063 (1999-07-01), Olnowich et al.
patent: 5926463 (1999-07-01), Ahearn et al.
patent: 5933425 (1999-08-01), Iwata
patent: 5938736 (1999-08-01), Muller et al.
patent: 5940596 (1999-08-01), Rajan et al.
patent: 5964841 (1999-10-01), Rekhter
patent: 5991299 (1999-11-01), Radogna et al.
patent: 5999536 (1999-12-01), Kawafuji et al.
patent: 6006272 (1999-12-01), Aravamudan et al.
patent: 6026303 (2000-02-01), Minamisawa
patent: 6088590 (2000-07-01), Anderson et al.
patent: 6108314 (2000-08-01), Jones et al.
patent: 6178323 (2001-01-01), Nagata
patent: 6246669 (2001-06-01), Chevalier et al.
patent: 6301244 (2001-10-01), Huang et al.
patent: 6430413 (2002-08-01), Wedi et al.
patent: 6618761 (2003-09-01), Munger et al.
patent: 6690929 (2004-02-01), Yeh
patent: 6754169 (2004-06-01), Baum et al.
patent: 0465201 (1992-01-01), None
patent: 0539737 (1993-05-01), None
patent: 0845889 (1998-06-01), None
patent: 2313254 (1997-11-01), None
patent: WO 96/19887 (1996-06-01), None
patent: WO 97/09805 (1997-03-01), None
patent: WO 98/18280 (1998-04-01), None
F.A. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part II—the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution,” IEEE Trans. Commun., vol. COM-23, No. 12, pp. 1417-1433 (1975).
R.M. Metcalfe and D.R. Boggs, “ETHERNET: Distributed packet switching for local computer networks,” Communications of the ACM, vol. 19, No. 7, pp. 395-403 (1976).
C. Wu and V.O.K. Li, “Receiver-initiated busy-tone multiple access in packet radio networks,” ACM SIGCOMM '87 Workshop: Frontiers in Computer Communications Technology, Stowe, VT, USA, pp. 11-13 (Aug. 1987).
F.A. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part III —polling and (dynamic) split-channel reservation multiple access,” IEEE Trans. Commun., vol. COM-24, No. 8, pp. 832-845 (1976).
P. Karn, “MACA—a new channel access method for packet radio,” in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-140, ARRL (Apr. 1990).
C.L. Fullmer and J.J. Garcia-Luna-Acheves, “Solutions to Hidden Terminal Problems in Wireless Networks,” Proceedings of ACM SIGCOMM '97, Cannes, France (Sep. 14-18, 1997).
C.L. Fullmer and J.J. Garcia-Luna-Acheves, “Floor Acquisition Multiple Access (FAMA) for Packet-Radio Networks,” Proceedings of ACM SIGCOMM '95, Cambridge, MA (Aug. 28-Sep. 1, 1995).
K.C. Chen, “Medium-Access Control of Wireless LANs for Mobile Computing,” IEEE Network, vol. 8, No. 5, pp. 50-63 (1994).
Timothy J. Shepard, “A Channel Access Scheme for Large Dense Packet Radio Networks,” Proceedings of ACM SIGCOMM '96, Stanford University, pp. 1-12 (Aug. 1996).
I. Chlamtac, Andras Farago, and Hongbiao Zhang, “Time-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks,” IEEE/ACM Transactions on Networking, vol. 5, No. 6, pp. 804-812 (Dec. 1997).
Ji-Her Ju and Victor O.K. Li, “An Optimal Topology—Transparent Scheduling Method in Multihop Packet Radio Networks,” IEEE/ACM Transactions on Networking, vol. 6, No. 3, pp. 298-306 (Jun. 1998).
Chenxi Zhu and M.S. Corson, “A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks,” Proceedings of IEEE INFOCOM '98 (Jul. 1998).
A. Ephremides and T. Truong, “Scheduling Broadcasts in Multihop Radio Networks,” IEEE Transactions on Communications, vol. COM-38, No. 4 (Apr. 1990).
J. Haartsen, et al., “Bluetooth: Vision, Goals, and Architecture,” Mobile Computing and Communications Review, XP-0007854002, US, ACM, New York, NY, vol. 2, No. 4, pp. 38-45 (Oct. 1, 1998).
L. Kleinrock and F.A. Tobagi, “Packet Switching in Radio Channels: Part 1 —Carrier Sense Multiple Access Modes and Their Throughput-Delay Characteristics,” IEEE Trans. Comm., vol. COM-23, No. 12 pp. 1400-1416 (1975).
Barry M. Leiner, Donald L. Nielson, and Fouad A. Tobagi, “Issues in Packet Radio Network Design,” Proceedings of the IEEE, vol. 75, No. 1, pp. 6-20 (Jan. 1987).
G. Markowsky and F.H. Moss. “An Evaluation of Local Path ID Swapping in Computer Networks,” IEEE Trans. Commun., vol. COM-29, pp. 329-336 (Mar. 1981).
P. Newman, T. Lyon, and G. Minshall, “Flow Labeled IP: A Connectionless Approach to ATM,” Proc. IEEE Infocom '96, San Francisco, CA, pp. 1251-1260 (Mar. 1996).
Yakov Rekhter, et al., “Tag Switching Architecture Overview,” Proc. IEEE, vol. 85, No. 12 (Dec. 1997).
M. Schwartz and T. Stern, “Routing Techniques Used in Computer Communication Networks,” IEEE Transactions on Communications, vol. COM-28, No. 4, pp. 539-552 (Apr. 1980).
A. Segall and J. Jaffe, “Route Setup with Local Identifiers,” IEEE Trans. Commun., vol. COM-34, pp. 45-53 (Jan. 1986).
S. Murthy and .J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” Proc. IEEE INFOCOMM '97 , Kobe, Japan (Apr. 1997).
J.J. Garcia-Luna-Aceves, et al., “Wireless Internet Gateways (WINGS),” Annual Military Communications Conference, New York, New York, XP-000792611, IEEE pp. 1271-1276 (Nov. 3, 1997).
B. Rajagopalan, et al., “A Responsive Distributed Algorithm for Shortest-Path Routing Within Autonomous Systems,” Internetworking: Research and Experience, XP-000669932 John Wiley & Sons, vol. 2, No. 1 pp. 51-69 (Mar. 1991).
V.O.K. Li and R. Ch
Beyer David A.
Frivold Thane J.
Garcia-Luna-Aceves J Joaquin
Caldwell Andrew
Nokia Corporation
Squire, Sanders & Dempsey LLP.
Willett Stephan
LandOfFree
Unified routing scheme for ad-hoc internetworking does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Unified routing scheme for ad-hoc internetworking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unified routing scheme for ad-hoc internetworking will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3752788