Packet prioritization protocol for a large-scale, high speed computer network

An apparatus, data structures, and method are provided for prioritizing data transmissions within a network. As applied to a switching station in a network, the method prioritizes transmissions from the network to determine which packets should be transmitted from the switching station first when multiple packets are routed to the same outgoing port of the switching station. A packet prioritization station is provided, preferably as an add-on to the switching station. The packet prioritization station has a cache in which the destination address of each incoming packet is associated with every origin from which it has received a transmission within a certain time period. The packet prioritization station operates to give priority to transmissions to those destinations that have a higher number of associated origins. Thus, packets that are probably en route to time-critical users or groups of users will be sent before those that are less time-sensitive.

BACKGROUND OF THE INVENTION

1. The Field of the Invention

The present invention relates to computer communications networks. More specifically, the present invention relates to methods of chronologically prioritizing time-sensitive data transmissions from a switching station.

2. The Relevant Technology

Computer technology is breaking barriers to inter-personal communications at an amazing rate. Already, it is possible to communicate almost instantaneously with anyone in the world that has a computer and a telephone line. Computer networks, such as the Internet, link individuals and various types of organizations in world-wide digital communication The Internet has almost unlimited promise for communications advances, but is limited by an overburdened and somewhat unsuited transmission medium.

In addition to the Internet, businesses, educational institutions, government agencies, and other similarly related entities also communicate over much smaller-scale networks, such as local area networks (LANs) and wide area networks (WANs). These small-scale networks, particularly LANS, operate at much higher speeds than the Internet, but are expensive to operate at large scales. Thus, a large gap exists, between the scope of coverage and speed of operation of the global, but relatively slow, Internet and the faster but more limited LANs and WANs. It would be advantageous to close this gap with larger-scale networks that operate at speeds close to that of LANS.

Several barriers exist to filling the gap between current limited coverage networks and the Internet. One such barrier is the “last mile” dilemma. That is, the Internet runs at very high speeds over its backbone, but slows down considerably over its localized connections. Generally, the Internet relies upon standard telecommunications industry lines and switching equipment for this last mile. This infrastructure is designed for telephone communications, and is not well adapted to the packetized communications of digital networks. A dilemma lies, however, in replacing the telephone infrastructure with transmission mediums more suited to digital communications. It is currently considered prohibitively expensive to connect high speed communications lines down to the individual users of the Internet.

This fact, together with the general congestion of the Internet in general leads to a substantial slow down of Internet communications. It also limits the deployment of intermediate types of networks. A further barrier to the implementation of networks of varying scopes and to the new introduction of new paradigms for network communication comes in the form of financing. Such developments using current technology would be prohibitively expensive. Who is going to pay for this infrastructure?

Accordingly, a need exists for an intermediate sized network to close the gap between the world-wide Internet and current relatively small scale networks. Preferably, such an intermediate sized network operates at speeds similar to those of LANS, coverage both in geographical area and diversify of user type. Additionally any solution to this problem should also address financing of installation and should overcome the last mile dilemma. New technologies for achieving such a new paradigm in computer networking are similarly needed.

In addition to the lack of larger scale, high-speed networking, prior art networks of every size have additional problems. Many of these problems result from the way in which switching is carried out by known networks. Switches are simply junctions for multiple communication lines. A “data transmission” is simply an analog or digital signal sent from an origin to a destination. Bundled data transmissions, or “packets,” arrive at an incoming port of the switch, and are routed to the proper outgoing port to reach their destination. (Although each port is capable of two-way communication, the port through which a packet arrives is designated as the incoming port, while that port through which it will exit is the outgoing port.) A data transmission from one computer to another may pass through several switches, depending on the size of the network involved. Full-duplex, switched networks are generally far faster than their half-duplex, unswitched counterparts.

However, a special problem arises when multiple packets simultaneously arrive at a switch through different incoming ports, and all of the packets must go through the same outgoing port. Since a line is only capable of conveying a single packet at a time, one packet will be sent while the rest wait. Current networking systems possess significant drawbacks in that they entirely fail to prioritize, or prioritize improperly, the order in which the packets are transmitted.

This has many undesirable effects. Since the switches are typically utilized in a branching network, many more switches may be downstream from the outgoing port. The switch itself is unaware of what type of destination any packet is sent to. The destination may be a server hosting many users simultaneously, or it may be a single home user.

As a result, people waiting for critical communications are forced to wait for other, less important traffic. For example, a company may have a large number of employees receiving e-mail through a server on the network. The e-mails may contain important instructions, information, questions, etc. that should not be delayed. However, if the e-mail is routed through the same switch as a large file download requested by a computer near the mail server, i.e., at the same outgoing port, the e-mail traffic may be slowed down by waiting for the file download. This occurs even though delays are inconsequential for the download, which will require several minutes in any case. Similarly, a number of computer users performing research over the Internet, using a variety of different sites, may be slowed down by a single user transmitting real time game data to another user.

No previously known system provides a sufficient solution to this problem. Simply sending packets through the port in sequential, cyclical form, or “round robin” form, provides equal time to each communication through the switch, and causes the problems described above. Giving priority to the heaviest user, i.e., the destination that has received the most packets, is inadequate because the volume of data is not proportional to its importance.

Thus, a there is a need, unfulfilled by the prior art, for a new method for prioritizing transmission of packets from a switching station. The method should preferably prioritize transmission according to the destination that is receiving the most important, i.e. time critical, information, while avoiding entirely blocking other destinations for lengthy periods of time. In addition, hardware and suitable data structures are needed for carrying out the method described above.

Another problem with known networks is broadcasting. Broadcasting occurs when a packet is sent to an unresolved destination. Communications over the Internet often take place on the third, or network layer of the ISO/OSI model, which is the Internetwork, or IP layer, of the TCP model. Transmissions may be addressed to a certain IP address, but the IP address is a property of the network, and may not be the same for a given device every time. Internet service providers (ISP's), for example, will often assign a temporary IP address to each individual dialed up computer.

In order to successfully route a packet to the proper device, a switch must have access to the hardware, or MAC address of the device, which is unique to each individual network interface card (NIC) that connects a computer to the network. The MAC address corresponds with the second layer of the ISO/OSI and TCP models. A computer sending a transmission may not always have access to the receiver's hardware address.

Thus, the sending computer sends an address resolution protocol (ARP) broadcast, or packet without a specific MAC address destination, which will then be propagated to multiple computers. The ARP broadcast contains a designated IP address for the destination computer, and acts as a request for a requested MAC address of the computer that has that IP address. The computer that has the IP address responds by sending a packet back to the origin of the broadcast, with its MAC address included in the packet. The computers can then communicate directly over the network without broadcasting to other users.

The problem with ARP broadcasting is that it creates a great deal of unnecessary traffic on a system. The ARP broadcast itself typically does not contain a great deal of data, but it must be transmitted to many computers, thereby occupying a great deal of bandwidth. Even if a receiving computer's MAC address is resolved by one transmitting computer on the network, another transmitting computer may transmit data to the computer, thus requiring another ARP broadcast. In a network or branch with a large number of users, a great deal of the network's bandwidth may be occupied by ARP broadcasting.

Consequently, it would be an advancement in the art to provide a method and apparatus capable of reducing ARP broadcasting. The method and apparatus should enable transmitting computers to obtain the MAC addresses of computers to which they will send data, without propagating every ARP broadcast to every computer. Furthermore, the method and apparatus should preferably reduce ARP broadcasting without the need to replace a great deal of the currently-existing network infrastructure. The method and apparatus should be inexpensive, low-maintenance, and fast. Finally, the method should be fully compliant with existing protocols for network data transmission, so as to be transparent to computers and end users on the network.

BRIEF SUMMARY OF THE INVENTION

In order to overcome many or all of the above-discussed problems, the present invention comprises methods, apparatus, and systems for implementing Large-scale high speed computer network. The network may connect an entire neighborhood or city in networked communications, and accordingly, will be referred to herein as a Neighborhood Area Network (NAN). The NAN of the present invention is a network conducted on a unique scale with a unique clientele and is implemented in a manner that transcends traditional network boundaries and protocols. The NAN is not equivalent to a wide area network WAN, in part because it is essentially routerless. That is, while a plurality of NAN, may be interconnected through the use of routers, each individual NAN is preferably constructed without the use of internal routers. The NAN is unique from local area networks (LANs) as well. One reason is that, due to its many novel features, it can be of a size and scope previously unobtainable by conventional LANs.

The NAN is further unique because it is intended to cover and serve a selected geographical area and to blanket that geographical area, rather than functioning to serve a specific government, business, educational, or similarly related entity. Accordingly, the subscribers and users of the NAN may be substantially non-related in any traditional business manner. Furthermore, funding for the NAN, rather than being provided by a business-type entity or subsidized by a governmental organization, may be funded at least in part by an independent third party, such as a utility company and may be funded in total or in part by subscribers.

The NAN is also comparatively inexpensive to install, making the placement of a NAN in every neighborhood a real possibility. The NAN of the present invention is capable of eliminating the message traffic burden from the Internet, thereby speeding up the Internet, as it is adapted to be operated completely independent of the currently highly burdened telecommunications infrastructure (although Internet service may be provided over the NAN).

In one embodiment, the NAN is comprised of an optic fiber ring serving as the outer backbone of the NAN. The ring is preferably populated with one or more fiber boxes, each containing circuitry including switches, repeaters, gateways, etc. The fiber boxes in one embodiment connect the backbone to a central office or headquarters data center in which a server is preferably located. One or more gateways are preferably provided within the backbone for access by Internet Service Providers (ISPs). An inner backbone comprised of scalable 10 to 100 megabit coaxial cable preferably branches from the fiber backbone.

The coaxial cable preferably originates at the fiber boxes and branches through the selected geographical region (discussed herein as a neighborhood, but of course, any geographical scale could be served), connected by repeaters and nodes to individual communicating stations. The inner backbone is preferably partitioned for efficient routing of traffic.

The nodes in one embodiment comprise hubs. The repeaters may be placed three hundred feet apart along the coaxial cable, with hubs placed within thirty feet of every house, business, or other type of communicating station on the NAN. The hubs preferably connect to the local houses or other buildings with ten-base-T twisted pair copper wiring employing the Category 5 (Cat5) standard. The hubs in one embodiment are powered by one or more of the communicating stations that they service. Accordingly, each station connected to a hub may share the powering of the hub and may share the powering of other switching equipment of the NAN as well.

In one embodiment NAN software operates on the server, the fiber boxes, the repeaters, and the hubs. Client software preferably operates a computers located at each communicating station. Additional functional software or logic may also execute on communicating stations or computers of subscribing service providers. For example, software may communicate with an electric power meter for transmitting information regarding power consumption from a communicating station (the power customer) through the network to third party service provider, in this case, a utility power company.

In one embodiment, at least a portion of the backbone is installed over the right-of-way owned by or franchised to a public utility such as gas, electric, or power company. This negates any need for a separate utility administering the NAN to acquire a new easement or franchise from the landowners or the government entity of the geographic region. The NAN may be financed and/or installed through the cooperation of the utility service provider company. This arrangement allows the public utility service provider that would otherwise be unable to enter the digital communication market to participate. It is also advantageous in that a NAN developer or administration entity would otherwise likely be unable to afford to finance and install the NAN due to the cost and risk of funding and lack of sufficient rights-of-way.

In certain embodiments of an apparatus and method in accordance with the present invention, an independent entity may create a city-wide network or NAN. The network includes, in one embodiment, a fiber optic ring within the city to serve as a local backbone. The fiber optic ring may be fully redundant. That is, it preferably completes a loop such that any break in the loop will not shut the whole system down. The fiber can be laid inexpensively as distances are not great and thus, less expensive local short-distance-types of fiber cable can be used. A low cost fiber can be used, such as feeder fiber which is less costly, and which requires less labor to install.

The fiber backbone is preferably populated by fiber boxes having switches therein. Coaxial cable from switches to bridges and repeaters to hubs. The hubs may connect to client stations using twisted-pair, copper cabling. A central server may be used and may be located within a headquarters data center. A headquarters data center may be employed as a gateway for Internet service providers. In addition, the Internet service providers may enter the system through other gateways including one or more switches.

The fiber backbone may be laid using the franchise agreement granted to the power company within a city or region. Thus, as the entire network is laid independently, the ISP service is provided independent of the telecommunications line over the entire route. Additionally, all ISPs are available on the net allowing equal access without choking traffic.

The infrastructure is preferably upgradable from 10 megabit to gigabit technology over the same lines, such that the lines need not be relaid in order to upgrade. Services that can be provided include surveillance, on-line books, two-way multi camera, schools, etc. Additionally, IPBX, telephone, television, CATV, and video on demand can be provided over the NAN. Video can be provided allowing independent selection, broadcast, start time and may be buffered to the user in real time.

The NAN also preferably incorporates one or more multi-port switches which are configured to truncate broadcast data. The multi-port switch is preferably an indoor switch but is contained in an aluminum pedestal of dimensions approximately 3 by 2 by 2 feet and is environmentally controlled.

The repeaters in preferred embodiments convert the data from the switches to be transmitted over coaxial cable and are preferably semi-intelligent. In one embodiment, the repeaters are housed out of doors within a protective pedestal. The pedestal may be located on the ground or hung from power lines.

The bridges are, in preferred embodiments, high speed with a look-up binary tree and are preferably contained in the protective pedestals. The bridges also filter out broadcast traffic. The hubs route traffic to subscribing communicating stations and convert from coaxial to twisted pair cable. The hubs are connected with a T-connector and powered by the cooperative power coupler of the present invention.

The P-coupler preferably includes a series of transformers, one at each communicating station. The communicating station connect with Cat5 wiring to the hub through a home connection box. The home connection box preferably provides convenient connections for power to the hub and for transmit and receive lines. The lines at the home connection box are wired alphabetically. The home connection box connects preferably connects with Ethernet cabling to a network card located within a computer at the client station.

A modular power connector is preferably located at the home connection box. The wiring from the communicating station to the hub operates, in one embodiment, at ten megabytes per second. Three pairs of lines are preferably used, a transmit twisted pair, a receive twisted pair, and an A/C twisted pair running from the transformer to power the hub.

The NAN of the present invention is a high speed routerless network which differs from traditional large scale networks in that traffic is routed locally and that it has the speed of a small local area network but with many more stations connected thereto. The large amount of communicating stations is facilitated by the many novel aspects of the invention.

The NAN can be described as a baseband network rather than a broadband network because it addresses communicating stations directly and linearly rather than through broadcasting of data. The NAN of the present invention defines what cannot be routed rather than defining the types of packets that can be routed. The NAN also preferably uses converse/inverse filtering. Because the communications traffic is direct-routed, neighbor to neighbor communication is very high speed and occupies only a small part of the NAN. It also reduces the burden on the Internet.

Moreover, a packet prioritization method with an apparatus suitable for its implementation is included to improve prioritization of packets leaving a switching station. (A switching station refers to any device that performs switching between a plurality of ports, regardless of whether the device is designated as a hub, bridge, switch, repeater, etc.) The switching station may have a number of ports, each of which has a buffer to temporarily store incoming packets. The switching station may also have a processor and program memory containing instructions for the processor. A cache may also be provided for additional data storage, with a multiplexer to enable the cache to simultaneously receive signals from multiple sources. The processor, buffers, and multiplexer may all be linked by a bus.

Similarly, a packet prioritization station is provided, either as an integral part of the switching station, or as an addition, such as an auxiliary expansion card or board (AEC). If embodied as an AEC, the packet prioritization station may have a bus linked to the bus of the switching station by an interrupt controller that triggers the packet prioritization station when the proper conditions are met in the switching station. The switching station, in its independent form, has a processor and a program memory, both of which may take multiple forms. The processor carries out instructions provided by the program memory in order to carry out the functions of the packet prioritization station.

A cache in the packet prioritization station contains a database binding each MAC layer address (or destination) to other MAC layer addresses (or origins) that have sent packets to that MAC layer address. These destinations and origins are obtained by copying them from a sampling of all packets passing through the switching station. The origins are maintained in the database for a certain period of time. The processor, program memory, and cache of the packet prioritization station are all linked by the bus.

When a new packet is received through an incoming port of the switching station, it is stored in the buffer for the incoming port. Meanwhile, the switching station matches it up with one or more ports, through which it will be transmitted to reach its destination. When packets in multiple buffers are not routed to a single outgoing port, the packets in the buffers are simply sent to their respective outgoing ports in cyclical, or “round robin” fashion. However, when more than one packet is routed to an outgoing port, the packet prioritization station must determine which packet get priority.

It has been discovered that those packets being sent to destinations for which many origins are cached typically are of a higher relative importance, because they represent multiple users or time-intensive network use. The packet prioritization station proceeds through packets routed to a single port in round robin format, until it encounters the first packet with a destination having more than a threshold number of origins bound to it. That packet is immediately sent. When no packet routed to the outgoing port has a destination that has recently received packets from the threshold number of origins, packets are sent in round robin fashion, i.e., by sending packets from alternating incoming ports. The process continues until traffic to that outgoing port subsides.

Consequently, destinations receiving data from many sources will receive priority. More time-critical communications are transferred first, because smaller files, such as e-mail, are typically those for which rapid response is especially important. Large information transfers, such as file downloads, normally are not as critical, and can therefore be delayed until after more important information has been routed. Similarly, files from multiple origins are often sent to multiple recipients. Thus, the packet prioritization station handles the needs of the majority of users as rapidly as possible.

Furthermore, a traffic reduction method and apparatus may also be implemented according to the present invention. An ARP caching station may be provided to work in concert with the switching station. The ARP caching station may be used with or without the packet prioritization station, and the packet prioritization station may similarly function independent of the ARP caching station.

The ARP caching station may also be integral with the switching station, and may share its components for operation. Alternatively, the ARP caching station may be an AEC with independent componentry, in communication with the switching station. Thus, the ARP caching station may have its own processor, program memory, and cache, linked by a bus. As with the packet prioritization station, the bus of the ARP caching station may be linked to the bus of the switching station by an interrupt controller. Thus, operation of the ARP caching station may also be triggered by the switching station.

The ARP caching station may have its own database containing associated IP addresses and MAC addresses. These may be obtained by storing the addresses from any packet, such as an ARP broadcast response, that contains both an IP address and a MAC address denoting the same destination.

When an ARP broadcast is received by the switching station, the ARP caching station may be activated to look for the designated IP address in the cache, and return the associated, requested MAC address if it is available. If the requested MAC address is not found in the cache, the ARP caching station may store the designated IP address in the cache for future reference, or may simply store nothing until another packet with an IP address and a matching MAC address is received. In any case, the ARP broadcast is then propagated by the switching station so that a response can be sent by the destination (the computer having the designated IP address).

If the requested MAC address is available, the ARP caching station creates a packet in the proper form for an ARP broadcast response containing the requested MAC address, and sends it to the originator of the ARP broadcast. The ARP broadcast need not be propagated by the switching station. Thus, if the requested MAC address is in the cache, considerable bandwidth is saved by avoiding transmission of the broadcast through all ports on the switch (except the incoming port of the ARP broadcast). The originator of the broadcast also receives a quicker response and can begin transmitting information to the destination with little delay.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring now toFIG. 1, shown therein is a schematic block diagram showing various hardware components of one embodiment of a large-scale, high speed network of the present invention. Because the network is intended to serve a selected geographical region, it is referred to herein as a neighborhood area network (ANA)10. The NAN10, as depicted, includes a backbone12, that is divided into two components. A first component is a fiber backbone14that is preferably adapted to transmit packetized data using standard optical communications protocols and technology. The fiber backbone14is preferably configured in a ring with incoming traffic traveling in a selected given direction.

A second component comprises a local backbone16that is preferably configured with a non-redundant branching structure and that is adapted to transmit data using radio wave signals. In the schematic depiction ofFIG. 1, the physical locations of connections are represented, while an example of the actual branching structure is shown in FIG.3.

The NAN system10in the depicted embodiment ofFIG. 1also includes a server18which may be located at a central headquarters office20. One or more fiber switches22may be located within the fiber backbone14. Indeed, the fiber backbone14may complete a circle around a neighborhood or other common geographical region which is intended to be networked in computer, voice, and or/video communication. The fiber backbone14may be provided with redundant loops in case one loop becomes inoperable.

The local backbone16preferably communicates with the fiber backbone14through one or more fiber switches22. Each fiber switch22is preferably configured to examine packetized message traffic passing therethrough, and where a message is intended for a communicating station serviced by a portion of the local backbone serviced by the switch22, route the message onto the local backbone16. Each switch22also preferably routes locally generated traffic with external destinations to the fiber backbone14for receipt by other switches or gateways108to the Internet34. The switches22preferably also convert communications between optical communications signals and radio frequency signals.

Within the local backbone16, switching devices, including a series of repeaters24, nodes26, and bridges50are preferably deployed. In one embodiment, the local backbone16is provided with coaxial cable38having a sufficiently high band width and having signals of sufficiently high amplitude that repeaters24are needed only every 300 feet or so. The nodes may comprise hubs26which, due to the efficient propagation of the NAN10, can be located up to 30 feet from each communicating station30.

Communicating stations30in one embodiment connected to the nodes26, with Cat 5, twisted pair wiring40through a home connection box42. Internet Service Providers (ISPs)32are shown connected to the NAN10through in several different types of gateways. An ISP32may connect through the central headquarters office20and from there to a fiber switch22. Alternatively, an ISP may communicate directly with the fiber backbone14through a fiber switch22. The ISPs provide access to the worldwide web and the Internet34.

Each communicating station30may be provided with one or more home service boxes44. The service boxes44communicate over the NAN10and provide interactivity from a remote distance. The service boxes44may comprise, for instance, power meters46, security systems48, and any number of electrical and mechanized devices, including appliances, sprinkling systems, synchronized clocks, etc.

The fiber switches22may be housed within containment units52. The containment units52may be located inside or out of doors and are preferably provided with insulation and/or environmental control devices such as a fan54and/or air conditioning56. The containment units52are preferably vented.

The repeaters24, bridges50and nodes26are preferably located within protective pedestals28which are also preferably vented, which provide a hardened outer shell, and which may be provided with fans54or other environmental control devices. The pedestals28may be mounted in the ground, or may be mounted from utility and/or power lines overhead. The pedestals28preferably provide some type of lightening protection such as a Faraday shield. The pedestals28are described in greater detail below with reference toFIGS. 7 and 8.

FIG. 2is a functional block diagram illustrating a system architecture100including operative data structures and executable modules for controlling the operation of the hardware of the NAN10depicted in FIG.1. The system architecture100controls the interactions of the various intelligent components of the NAN10of FIG.1.

Accordingly, shown inFIG. 2are the different modules and executables for operating the NAN10. Included are a plurality of client stations30communicating over a transmission system102. Other entities may also communicate over the transmission system102. These include the central headquarters office20, the server18, a monitoring station152, and service providers104, including a utility company106.

Referring now to the transmission system102, one method of operation of the NAN10to transmit information between the client stations30will be described. In one embodiment, the NAN backbone12is essentially routerless. That is, the system is operated at a large scale, but using the same principles as a small local area network. This is achievable due to the unique architecture and configuration of the NAN10. Routers (62inFIG. 3) are required only when connecting to outside entities, such as other NANs or the Internet34.

Components included within the system100include the bridges50, the switches22, the repeaters24, and the nodes, which in one embodiment comprise hubs26. Also included within the system102is an Internet routing module108which routes traffic to and from the ISP's32. The Internet routing module108operates as a gateway and may comprise a switch22and a router62.

The switches22are provided with software modules in the form of a switch routing module110and a switch conversion module112. The switch routing module110is used to route traffic between the switches22. The switch conversion module112is used to convert packeted traffic between the optical communications protocol and the radio frequency signals used within the coaxial cable lines16. Thus, in preferred embodiments, each switch includes one or more protocol converters interfacing between fiber cabling and Cat5 twisted pair wiring.

The protocol converters translate the optical signals into radio frequency signals for transmission on the coaxial Cat5 cables. The radio frequency signals are in turn translated into digital signals by the network cards156.

The Cat5 twisted pair wires lead into out of the switch22and connect to the protocol converters112and to repeaters24. The repeaters24place the data packets on the coaxial cable16. The Cat5 wiring may also lead directly to client stations30that are within 300 feet of the switch22.

Traffic is routed in an efficient manner whereby the system100utilizes the high speed fiber cables14to as great a degree as possible routing packetized traffic to the switch22closest to the communicating station30to which the message is addressed. Once the packet reaches the closest switch22, it is routed through a repeater24onto the local backbone12. Once on the local backbone12, the packet passes to a bridge50and then to the node26closest to the client station30in a manner be discussed below with relation to FIG.3.

The repeaters24are preferably spaced approximately every 300 feet in order to avoid over-attenuation of the signals carrying the data packets. The nodes26are placed within 30 feet of each communicating station30.

The communicating stations30are preferably provided with client software126for enabling communications over the NAN10. The NAN10communications medium is, in one embodiment, standardized Ethernet data packets adhering to the Ethernet/OSI standards. In one embodiment, the data packets may be transmitted over the NAN10using merely MAC addresses of the low levels of the OSI model.

Client stations30which are new to the NAN10transmit an initial communication packet over the NAN10to the server18. The server18in reply issues an IP address136to the client station30which is semi-permanent. Thereafter, the client station30has a semi-permanent IP address136which is changed only upon incidents such as the computer or network card of the client station30being changed.

The packets are routed through the switches22, repeaters24, and nodes26, to the addressed client stations30. The packets may be transmitted at a rate of 10 megabits per second due to the unique architecture of the NAN10. This high rate of speed can be upgraded by a factor of 10 or even up to a factor of one hundred without having to redeploy the fiber cables14, the coaxial cables16, and the pair twisted wiring40. This, again, is due to the unique architecture of the system.

The system architecture includes extending the distance a packet can travel up to between 3000 and 25000 feet and increasing the maximum tolerable packet acknowledgment time. This is accomplished in one embodiment by digressing from the IEEE standards.

For instance, the signals with which the packets are transmitted are amplified to a higher power than those on standard networks. This is accomplished by increasing the gain in the amplifiers that make the repeaters function. Additionally, the reception equipment is preferably more sensitive and able to capture a more degraded signal than standard network equipment.

The fact that the system operates on a baseband concept wherein all of the cable bandwidth is restricted to one channel rather than being divided into multiple channels allows for a higher bandwidth and greater power from the repeaters. This allows for collision detection over the cable38and for a release of the collision detection at a much lower level. Thus, voltage spikes are detected and ignored so that lower level collisions are not detected and the large level collisions can be detected. The incidences of these collisions are highly reduced due to the high bandwidth and direct routing of the system100.

Collision detection is preferably accomplished through voltage detection and timed resends and is adjusted to compensate for the increased sensitivity of the repeaters.

The repeaters24are provided with software or other logical circuitry120therein which allows the repeaters24to be semi-intelligent. The repeaters24transmit the fact that they are functioning, as well as information regarding the amount of traffic passing therethrough, in order to better manage the NAN10. Otherwise, the repeaters24merely pass the packets through and do not provide any switching function, merely increasing the amplitude of the signals carrying the packets. As mentioned, the repeaters24are, in one embodiment, placed every 300 feet across the local backbone16.

The hubs26route the packetized traffic through the Cat5 twisted pair wiring38to the communicating stations30. Internet routing108may also take place to route the Internet communications to the ISPs32. Communications with external stations over the Internet34may be conducted with a permanent IP address to get the messages within the NAN10, wherein the outside data packets are routed using MAC addresses. Additionally, stations30without permanent IP addresses may communicate through the use of a masqueraded IP address using a permanent IP address to get into the NAN and the semi-permanent IP addresses136issued to each client station30in a manner that will be discussed below in greater detail.

The bridges50are provided with software114and are also provided with a memory116containing a bank118of the IP addresses136of each client station30. The bank118also includes, for each corresponding IP address136, information regarding the location of the client station30to which the IP address136is assigned.

Accordingly, the bridges limit communications to only a particular portion of the network10to which the communication is addressed. Thus, the bridges50effectively partition the NAN10. A further function of the bridges50and the switches22is to eliminate unwanted communications. For instance, in one embodiment, broadcast packets and messages are forbidden. Accordingly, each switch22and bridge50may be provided with a traffic filter module160as depicted in FIG.4.

Referring toFIG. 4, the traffic filter module160is used to eliminate certain types of traffic that may not be routed over the NAN10. Accordingly, the NAN10is defined as determining what types of communications can not be routed rather than determining what types can be routed, as in the prior art. Within each traffic filter module160may be a broadcast traffic sniffing module162. The broadcast traffic sniffing module162examines each information packet165(shown inFIG. 4A) and checks certain fields171which indicate that the packet165is broadcast data. When the traffic sniffing module162determines that the packet165is broadcast traffic, it then initiates the traffic elimination module164which eliminates the broadcast packet165.

The bridges50and switches22in one embodiment detect broadcast traffic by detecting an empty field171within the MAC address170. Alternatively, the broadcast traffic sniffing module162may detect a series of addresses at a certain level such as255,255,255,255to detect a broadcast packet165.

Thus, because the NAN10eliminates unwanted traffic and restricts traffic to only those portions of the NAN10through which the packet165must travel to reach the addressed communication station30in the most efficient manner, much extraneous traffic is eliminated. This, combined with the higher speeds of the present invention, allow the NAN10to be operated as if it were a local area network but on much grander scales, indeed, even to include entire neighborhoods or municipalities. Additionally, because of this, the NAN10is suitable for use in geographical areas covering extensive distances that are merely geographically or community interest related, rather than being business, government, education or otherwise related. Thus, the NAN system10can be by financed at least in part by the service providers which will benefit from the efficient communication of the NAN10.

Referring now to the service providers104ofFIG. 2, an example of such a service provider is a utility company106. In one embodiment, the utility company106is a power company. Thus, for example, the power company can communicate over the transmission system102on the NAN10with each client station30. Within each client station30is one or more service boxes144having therein customer service software150.

The customer service software150might, in one instance, comprise power meter software148within a power meter box46. The power meter software148may transmit power usage through the NAN10back to the utility company106. The utility company106, with a power usage collection module144, receives the power usage data and transmits it to a billing module146. The billing module146then bills the customer at the communicating station30over the transmission station102. The payment of the bill may also pass through the transmission system102, thus passing through the NAN10back to the utility company106. Of course, utility companies other than the power company may also use this system of data collection billing and payment receipt.

Other types of service boxes144may also contain customer service box software150. For instance, the security system48may contain therein software which notifies the monitoring station152of any irregularities. Software154within the monitoring station152may monitor the data transmitted by the security system48. For instance, this data might include home security system data indicating that a break-in has occurred. The security system48may also indicate the occurrence of a fire, and may transmit full video surveillance data back to the monitoring station152. The monitoring station152or a similar station may also monitor the contents of the NAN10in order to eliminate illegal traffic. Pornography or other types of traffic may likewise be eliminated.

Each client station30as mentioned, preferably communicates at the MAC layer within the NAN10. The client stations30may also be provided with a semi-permanent IP address for communications external to the NAN10. The server18is provided with server software124which maintains a bank138of the IP addresses136. The server18thus issues the IP addresses136and also maintains a binding between the MAC layer communications and the IP addresses136. These bindings are transmitted to the switches22, bridges50, and any other equipment with a need to know the IP addresses136of the client stations30.

Consequently, the server18is not necessary other than for issuing IP addresses and maintaining bindings, and indeed, if the server18were to go down, the transmission system102operating on the NAN10could continue to operate. New client stations30would merely not be able to receive an IP address.

The central headquarters office20preferably contains therein a headquarters software module128. The headquarters software module128may conduct monitoring and billing types of operations. Thus, a customer database130may be maintained therein and may coordinate with a billing module134. A redundant database132is also preferably included. The redundant database132may be located at a distant site such that it maintains a copy of all data in the case of a failure of the customer data130. Synchronizing information may pass between the customer database130and the redundant database132over the NAN10with the use of the transmission system102.

Billing information may be generated and stored within the billing module134and may be transmitted to communicating stations30over the transmission system102. The customer database130may maintain records including records of which customers are behind on their payments. If the customers are behind, the client station130of that customer may be denied services in part or in full of the NAN system10. These services include, in one embodiment, Internet service.

The communicating stations30are preferably provided with standard network cards156which transmit through the home connection box42. The client software126residing at the communicating stations30preferably maintains the client's IP address136and receives and generates data packets (shown at165inFIG. 4A) with which information is transmitted over the transmission system102. The client software126may provide many various types of functions, including video phone communication, audio, and video transmission, payment of bills, ordering of on-demand video, transmission of home security information, etc.

A power coupler135may be provided within or in communication with the home connection box42. The power coupler135preferably conditions incoming power from a power source at each communicating station, combines the power and network connection, and provides a simple manner of connecting the twisted pair wiring to standard computer cabling, preferably Ethernet cable, which passes to the computer at the communicating station30. In one embodiment, the twisted pair wiring is provided with a twisted pair for transmission, a twisted pair for reception, and a twisted pair carrying AC to the hub26, as will be discussed in greater detail below with reference toFIGS. 5 and 6.

The hub26is in one embodiment provided with a power concentrator25which provides power conditioning and power delivery to the hub26. The power concentrator receives power from the power coupler135of the communicating stations30. Preferably the power concentrator25receives power from two or more stations30and passes the power on to the hub26or other switching device. A Power concentrator25receives power through a transformer connected to a wall socket at the communicating station30. In one preferred embodiment, four houses share a hub and provide power to the hub. The hub bleeds power out of the four transformers at a time, but can receive power from less than all of them and be at a full power level. This redundant power supply scheme ensures that the hub26continues operating even if one of the power sources, i.e., one of the communicating station30, goes down. Thus, AC power is received from the communicating station30through the power coupler135to the power concentrator25. In addition, all switching equipment may be powered cooperatively in this manner and may be provided with power concentrators25.

In one embodiment, the AC power is received directly from a power meter at the communicating station30. The power from the communicating stations30may be provided individually or collectively to the switches, bridges, repeaters, router, hubs, and any other switching equipment of the NAN. Additionally, power meters not located at communicating stations30may be utilized to provide power to the hubs26and other switching equipment.

In one embodiment, the communicating stations30or the hubs26comprise a power meter monitoring hub26. The power meter monitoring hub26may comprise an RF receiver and an 8-bit microcontroller as well as an RS 232 communications interface and a power supply. The hub may also contain up to four 10-base T ports. On-site configuration is provided by an RS 232 port. Under this embodiment, the monitoring hub receives power consumption data from power meter transmitters and passes it on to the utility company106over the transmission system102.

Each power meter46in this embodiment provided with a power monitoring transmitter. The transmitter may be comprised of a PIC microcontroller, a 418 megahertz UHF transmitter, a photo-reflective sensor, and an off-line power supply. The transmitter may use the photo-reflective sensor to monitor rotation of the power meter disk and store the information in nonvolatile memory in the microcontroller. The transmitter transmits the power usage information to the power meter monitoring hub along a 418 megahertz RF link.

In one embodiment, the coaxial cable, as well as the 10-base T wire, is housed within a protective conduit. The system may operate with Linux using an IP chain and masquerading which is considered more effective than using a proxy server.

The bridges50, in addition to eliminating broadcast traffic, may also receive and regenerate the packets165at a higher power level. The repeaters24preferably merely amplify the signals carrying the packets165and do so without any delay, while the bridges may slow down the packets somewhat.

Referring now toFIG. 3, shown therein is a functional block diagram of a NAN hierarchy scheme60. Within the scheme60is shown the fiber backbone14looping in a circuitous manner to form a ring. Within the fiber backbone14is a plurality of switches22. A central switch22ais shown connected with the central headquarters20and through a router62to the Internet. Thus, the fiber backbone14comprises an outer circuitous backbone. It should be noted that the NAN10may have a plurality of gateways62. Because of the plurality of gateways, any number of ISP providers32may provide service to the NAN10. Other types of service providers and outside entities may also access the NAN10through the gateways62.

Emanating from the switches22are components of the local backbone16which are arranged in a branched configuration. Thus, shown branching out from each switch22is a series of bridges50, repeaters24, and hubs26. Each bridge50separates and services a plurality of hubs26.

Thus, an incoming packet165received, for instance over the Internet34, passes through the router62. The router62uses an IP address169shown inFIG. 4ato determine that the packet is local to the NAN10. For instance, the IP address may be assigned to the NAN10or to the router62specifically under a masquerade scheme that will be described.

Once the packet165reaches the NAN10, it is routed using a MAC address170ofFIG. 4a.After passing through the router62, the packet165is received by the central switch22a.As shown inFIG. 4A, the packet165comprises a header166, a data portion167, and a footer168. The header comprises the address of the addressed communicating station30. The footer contains redundancy information to make sure the packet165was properly received. A cyclical redundancy check (CRC) may be used using information in the footer for acknowledgment that the packet165was received and has not been degraded.

Within the header166may be both an IP address169and a MAC address170. The MAC address170refers to a unique number given to each network card156ofFIGS. 2 and 5. The IP addresses169are administered by the Internic agency and are addresses utilized under the TCP/IP protocol. Each station has a unique MAC address. Additionally, each station may have a unique IP address169.

Nevertheless, because IP addresses169are becoming scarce and difficult to procure, a masqueraded system may be employed wherein the router62contains a routable IP address or several routable IP addresses and stations30within the NAN10are addressed by the routable IP address of the router62outside the NAN10. Once addresses containing the masqueraded IP address reach the NAN10at the switch22a,the MAC address170may then be used to route the packet165within the NAN10. Indeed, within the NAN10, routing is preferably exclusively conducted using the MAC address170.

When communicating on the MAC level, a communicating station30, in one embodiment, uses a protocol such as an ARP request. The “ARP” request is an address revolution protocol. The ARP protocol talks to the network cards looking for the MAC address. The use of an ARP-type address protocol by the NAN10does not adhere exactly to the ARP address protocol but is similar to it.

Thus, the server18may be characterized as a modified DHCP server but does not broadcast DHCP as with the prior art systems, though it does maintain the IP-MAC address binding and notifies all subscribing components of that binding. Under this arrangement, when a communicating station30comes on-line and receives the non-routable IP address from the server18, it then binds the IP address. In one embodiment, this is done by populating its registry with the IP address. That is, the IP address is bound to the TCP/IP protocol stack. This IP address is used for TCP/IP protocol communications with stations72external to the NAN10. As discussed, all internal communications are preferably routed using the MAC address.

Of course, the communicating stations30could also receive permanent IP addresses either from the server18or directly from Internic. These permanent, routable IP addresses may also be maintained within the binding of the server18.

Preferably, hubs, bridges and switches work on only the lower two levels of the OSI model ofFIG. 4b.When a packet165is addressed to go outside of the NAN-10, it is sent to the router62which acts as a gateway to the Internet34and passes the packet165outside the NAN10. The IP addresses within the communicating stations30communicate through virtual ports on the communicating stations30but preferably not through the same communicating ports as traditional DHCP protocol standards.

Additionally, the IP addresses are semi-permanent. That is, the communicating stations30maintain a single IP address for external communications and do not flood the NAN10with requests for DHCP servers to receive IP addresses from. Indeed, because of this substantially, only direct routed traffic exists on the neighborhood, and all broadcast traffic is substantially squelched. Additionally, all traffic is partitioned within its own area and does not travel across the entire network. For this reason, there are substantially less collisions because traffic is much more localized. This also allows the network to service many more communicating stations30.

The OSI model190is shown inFIG. 4b.As shown therein, the OSI model comprises a first layer191known as the physical layer. A second layer192is known as the data link layer and it is this layer that predominantly deals with the MAC address170. A third layer193is referred to as the network layer, a fourth layer194is referred to as a transport layer, and a fifth layer195is referred to as a session layer. The session layer195primarily deals with the IP address169. A sixth layer196is referred to as the presentation layer, and a seventh layer197is referred to as the application layer. Within the seven layer OSI model, the upper levels allow two communicating stations, one assigned as a client and one assigned as a server, to coordinate communications with each other.

The NAN10may be configured to communicate only on the second layer192within the loop of the fiber backbone14. For example, the router62may be configured to receive IP addresses169from the Internet34, and provide only MAC addresses170to the switch22. IP address resolution may be handled by the ISP32or other suitable entity. Thus, communications between the communication stations30would occur using only MAC addresses170, without the need to send an IP address169within each packet165.

The bridges30may then be omitted, and the hubs26and repeaters24may be replaced by switches22configured to handle only the MAC addresses170. Such an architecture would provide more rapid data transmission throughout the NAN10, since there is less information in each packet165to deal with. In addition, installation and configuration of the NAN10would be simpler because switches22may be installed without any need for hubs26, repeaters24, and bridges30.

Referring back toFIG. 3, once message traffic165is received from the router62to the switch22a,the switch22amaintains the packet165momentarily in a buffer164and refers to a database66to determine whether the MAC address170is local to a partition169belonging to the switch22a.Switch22amakes this binary determination, and if the answer is yes, passes the packet165to a first bridge50a.

If the answer is no, that is, the traffic is not local to a partition168, the switch passes the packet165in a given direction to a subsequent switch22. In the depicted embodiment, the given direction is clockwise. Upon passing the packet165on, a subsequent switch22receives the packet165and similarly examines the packet165to determine whether it is local or external to a partition168. If the packet is local to the partition168, the switch22will pass it on to a bridge50within a partition168to which the switch22belongs. If the packet165is addressed external to the partition168of the switch22, the switch22passes the packet165in the given (clockwise) direction to a subsequent switch22.

Presuming that the packet165was local to switch22a,switch22apasses the packet to a first bridge50a.The bridge50athen holds the packet165temporarily in a buffer64and refers to a local database66to determine whether the packet165is local or external to the bridge50a.If the packet165is local to the bridge50a, the bridge50adetermines which of the hubs26connected with the bridge50athe packet165must be routed through.

If the packet165is addressed external to the bridge50a, the bridge50apasses it to a subsequent bridge50b.The bridge50bthen receives the packet165within a buffer64and examines its database66to determine if it the packet is addressed to a local station30. If it is not, it passes it on to subsequent bridges50(not shown) in the branching structure of the local backbone16.

The bridges50are typically separated by one or more repeaters24to amplify the radio frequency (RF) signals which contain the packets165. Referring now back to bridge50a, if the packet165was local to bridge50a, it determines which of the hubs26to pass it to. Presuming that the packet165was addressed to a station30awithin a hub26a, the bridge passes the packet to the hub26a.The hub26abriefly maintains the packet165within a buffer64and examines its database66to determine which of the subscribing communicating stations30the packet165belongs to. In this case, it determines that the packet belongs to station30aand places the packet on a line40to be received by a network card156located at the communicating station30a.A similar process would occur with every bridge50. Thus, for instance, if the packet were addressed to a station30b,the bridge50bwould receive the packet and transmit to the hub26b,which would receive the packet165and transmit it to the communicating station30b.

Inter-NAN communications are even more simplified. For instance, if the communicating station30awishes to communicate with the communicating station30b, client software126would prepare the packet165and place it through the network card156onto the NAN10. The packet165would be received by hub26awhich would in turn transmit the packet165to the bridge50a. The bridge50awould examine the packet once again to determine whether it is local or external to the bridge50a. If it is locally addressed, the bridge50atransmits to the appropriate hub26connected thereto. If it is not, it directs the packet165to another bridge50or to the switch22a,depending on the MAC address170.

The switching equipment, such as the switches, bridges, and hubs, preferably use a binary tree sorting algorithm to sort through addresses in the attendant databases66to determine the location of stations30addressed by the packets165, which greatly enhances the speed thereof. The binary tree, rather than being just a one dimensional look-up table or bubble sort, is branched and allows for larger databases without significant propagation delays. The binary tree is implemented, in one embodiment, using the Nikolas Wirth style that is known in the art.

Note that each bridge50also preferably contains its own sub-partition70in the partition68of the switch22to which it subscribes. In this case, when a bridge, such as bridge50determines that the packet165is local to the partition68but not within its own subscribing hubs26, the bridge50apasses the packet165on to the bridge, e.g. bridge50b. The bridge50bthen examines the packet165and determines that it belongs to the hub26band passes it on to hub26b.Hub26bin turn examines the packet165and passes it on to the communicating station30b.

If a communicating station30such as the station30awants to communicate with a computer or entity72outside of the NAN10, it addresses the packet165using the IP address169of the entity72. If the outside station72wishes to communicate with the station30a, it also uses an IP address169to get into the NAN. This IP address169may be either a permanent IP address received from the Internic agency or a masqueraded IP address attributable to the router62. The outside station72sends any return messages using this IP address.

If the masqueraded IP address is used, the router62passes the packet165to the switch22a,which then examines the MAC address170without having to refer to the IP address. Thus, one difference between bridges50and the routers62of the present invention is that a bridge50reads only at the MAC level while a router62reads at the IP level.

The outside station72could also be part of a NAN other than the NAN-10. The outside station72could communicate using MAC addresses to other outside stations72within its own NAN, but once it wished to communicate with an entity outside its own NAN such as the communicating station30a,it then must use an IP address to pass packets165through the Internet with the use of routers62.

As presently contemplated, each NAN10may have 10,000 or more communicating stations30. A community having more than 10,000 locations wanting to subscribe to the NAN10would require more than one NAN10. Additionally, under the present system, this maximum number may be increased by increasing the speed of the local backbone16. The speed of the local backbone may be increased up to, for instance, a gigabit per second of throughput without having to reinstall the communicating lines. To increase the number of subscribing communicating stations30within a NAN-10, the firmware constituting the software within the client stations server, hubs, bridges and switches are replaced, in an operation that is substantially transparent to the communicating stations30.

Stations within the different NANs preferably communicate with each other over the Internet, as discussed. Nevertheless, within each NAN communications are routerless in the preferred embodiment.

Presently, the standard for communications on the inner backbone16is 10-base-T, whereas the fiber communications on the fiber backbone14are set at 100-base-T. NAN10communications preferably utilize the Ethernet 802.3 standard which is the standard presently relied upon by most Internet and network organizations. The Ethernet 802.3 standard is used in one embodiment of the NAN for packet encapsulation for transfer of the packets165over communication lines36,38.

In order for a new communicating station30to be admitted to communicate on the NAN10, it must first establish communications with the server18. The server18, as described, maintains a binding between IP addresses and MAC addresses. The client software126which is installed on every communicating station30provides the communicating station30with the proper MAC address of the server18. Thus the communicating station communicates with the server18to receive a localized non-routable IP address for use in communications external to the NAN-10.

In one embodiment, the communicating station30may be given a permanent IP address issued by Internic or may be given a non-routable address and use the masquerading procedure discussed above. Additionally, there may be several different types of IP addresses issued. As discussed, routable and non-routable IP addresses may be issued as well as filtered IP addresses that filter content received from the Internet. Additionally, an IP address may be partially or fully functional depending on whether the communicating station30has paid a monthly or yearly fee.

Every station30checks in with the server18at the initial login in one embodiment, but if the server18is not functioning, the stations30may still continue to operate with the previously issued IP address. E-mail messages may be sent to a permanent IP address, or may be routed in the manner of outside station72communications as discussed above.

In addition to the hardware and systems described above, appropriate new hardware, software, and systems may be included in the NAN to enable prioritization of traffic and reduction of broadcast traffic through address caching.FIGS. 5 through 19are presented to illustrate such hardware, software, and systems, as well as the methods utilized for traffic prioritization and reduction.

In the following figures, a number of definitions are relevant. A “data transmission” is simply a digital or analog signal transmitted to a destination. A “packet”165is a data transmission bundled in suitable form for delivery over the Internet34, as depicted inFIG. 4a.A “switching station”200refers to any device that carries and manages data transmissions between multiple ports. Thus, switches22, hubs26, repeaters24, and bridges30may all be switching stations.

However, the packet prioritization and traffic reduction methods of the current invention are well suited to use with switches22described above. A “property” of a data transmission is simply any characteristic of the data transmission that can be obtained by a switching station. This includes not just information encoded in the packet165, but also any other information the switching station could obtain, such as the identification of the port through which the packet165entered, characteristics of other packets165arriving with the packet165, etc.

“Relative importance” of a data transmission or a packet165refers to how important it is that the data transmission reach its destination rapidly. This is relative to the importance of other data transmissions sent through the NAN10. “Priority” is a related term. The priority of a packet is a designation that determines whether the packet is transmitted before or after other packets. This determination must be made when not all can be simultaneously transmitted, as is the case when multiple packets must go through a single outgoing port. Thus, the relative priorities of multiple packets may be compared to determine a “transmission order” of the packets.

Priority may be quantified with a gradation of values, or may be boolean, i.e., “high priority” or “low priority.” A “threshold value” may be used to obtain boolean priority with reference to a certain value of the property. For example, if the property of the data transmission is above the threshold value, priority of the data transmission is high, and where the property is equal to or less than the threshold value, priority is low.

A “database” is simply an ordered listing of data stored for future retrieval in a memory device. A “destination” of a data transmission or packet165refers to an ultimate, terminal destination, rather than to locations of switches en route to the destination. Thus, a destination MAC address is the address to which a packet165will ultimately be transmitted. Likewise, an “origin” is a location from which the packet first originated, as opposed to switches upstream of the switching station under analysis. “Location” refers to any origin or destination on the NAN10, hence, any communication station30may be encompassed within the word “location.”

A “computer-readable medium” is any physical object that can store information in a form directly readable by a computer. Thus, magnetic, optical, and electrical storage devices are all contemplated, as well as any other method of storing information directly accessible to a computer. Hard disks, floppy disks, CD/DVD ROM drives, RAM chips, punch cards, and the like are all examples of computer-readable media. “Instructions” are simply steps to be carried out by a processor, located within a computer-readable medium. The instructions may be provided by hardware, software, firmware, or any suitable combination thereof.

A “switching system” includes a switching station and any other components added to improve the quality of switching, such as a prioritization system or traffic reduction system. A prioritization system is an apparatus that acts to assign priorities to data transmissions in a network such as the NAN10. A traffic reduction system is an apparatus that reduces unnecessary traffic on a network.

Referring toFIG. 5, one embodiment of a switching system199is shown, including a switching station200with hardware suitable for packet prioritization and traffic reduction through ARP caching. Packet prioritization and ARP caching may function independently of each other; therefore, a NAN10may carry out one method, yet not the other. Different switching stations200within a single NAN10may be differently configured to carry out packet prioritization, ARP caching, both methods, or neither one. Switching stations200with few communication stations30connected may, for example, derive less benefit from packet prioritization and ARP caching than those with many communication stations30.

The switching station200has a plurality of ports202, preferably from four to twenty-four in number. Each port202connects to one of the communication lines38, which preferably provide full-duplex (i.e., simultaneous, two-way) data transmission. Thus, each port202may simultaneously send and receive data. Consequently, the terms “outgoing port” and “incoming port” refer equally to all of the ports202, and simply delineate what the function of the port202is within the process being described. Each port202preferably has a buffer204to store incoming packets165from the port202. These may be stored in the form of a first-in, first-out (FIFO) stack, so that packets165are queued up to be removed from the buffer204for processing in the order in which they were received.

Each buffer204is connected to a bus206, which operates to transfer data to various components of the switching station200at a certain bus speed. A processor208connects to the bus206to process and manipulate data from the buffers204. The processor208may be of any known type, such as a standard microprocessor, reduced instruction set computing (RISC) processor, field programmable gate array (FPGA), or application-specific integrated circuit (ASIC).

A microprocessor is capable of performing a wide variety of instructions, but is not highly specialized to perform any specific instruction set. A RISC processor is more specialized, but is still designed to carry out a comparatively wide variety of instructions. An FPGA is reconfigurable to carry out specific task sets, but is not as fast as an ASIC, which is highly specialized, but not reconfigurable. The ASIC contains a number of logic gates that are fixed in place, and are not reprogrammable. Since the switching station200will always perform a limited set of instructions, an ASIC is an ideal choice for the processor208. Due to its highly specialized nature, the processor208in the form of an ASIC may operate at a speed of 8.4 Gigahertz or greater, thus permitting data transmission through the switching station200with very little delay.

The processor208is connected to a program memory210, which contains instructions or reference data for the operation of the processor208. Although many instructions of an ASIC are built into the configuration of gates used, and therefore hard-coded into the processor208, certain information or instructions needed by the processor208may be stored in the program memory210separate from the processor208. The program memory210may optionally be omitted, if the processor208is configured to contain all needed instructions and information.

The program memory210is situated within a computer-readable medium of any suitable type, such as one or more standard DIMM (Dual In-line Memory Module) or SIMM (Single In-line Memory Module) random access memory (RAM) modules, programmable read-only memory (PROM) modules, electrically erasable PROM (EEPROM) modules, static RAM (SRAM) modules, flash RAM modules, and the like. However, the program memory210is preferably of a nonvolatile type, so as to retain information in the event of a loss of electric power to the switching station200. Additionally, the program memory210is preferably read-only to avoid any alteration or corruption of information in the program memory210. Thus, a PROM module or chip is well-suited for use to form the program memory210.

In addition to the program memory210, the processor208may be connected to a multiplexer211designed to unify streams of information from simultaneous sources, through interleaving or a similar process. Thus, data from all the buffers204and the processor208may be transferred into and out of a cache212through the multiplexer211. The multiplexer211maybe integrated with the cache212.

The cache212is designed to store information pertaining to the operation of the switching station200. Like the program memory210, the cache212may be embodied as any suitable memory type such as one or more RAM DIMM or SIMM modules, PROM modules, EEPROM modules, SPAM (Static RAM) modules, flash RAM modules, or the like. Preferably, the cache212is erasable, and may be volatile because the information stored in the cache212may not be essential to the operation of the switching station200. SRAM is well adapted for use in the cache212.

The bus206may be connected to an interrupt controller (IC)219, which permits the switching station200to actively interface with a prioritization system220connected to work in concert with the switching station200. The prioritization system220preferably takes the form of a packet prioritization station220. The packet prioritization station220may be integrated with the switching station200, and may even utilize the program memory210, processor208, cache212, multiplexer211, and bus206of the switching station200. This may be accomplished by providing a new set of instructions in the program memory210designed to carry out packet prioritization. However, the packet prioritization station220preferably has its own set of independent hardware, so as to be interchangeably usable with any switching station200, and so as to avoid slowing the operation of the switching station200. Thus, the packet prioritization station220may be located on an auxiliary expansion card or board (AEC), which may be connected to the switching station200in modular fashion.

The IC206may be integrated with the switching station200or the packet prioritization station220, or may be a separate component from the stations200,220. The IC219may be connected to a bus222located in the packet prioritization station220such that data from the bus206of the switching station is transmitted to the bus222of the packet prioritization station220. A processor224, program memory226, and cache228for the packet prioritization station220are, in turn, in communication with the bus222.

As with the processor208, program memory210, and cache212for the switching station200, the processor224, program memory226, and cache228may be of any suitable type. However, the processor224is preferably a RISC based processor. This would enable a generalized AEC with a RISC processor to be configured for use as the packet prioritization station. Likewise, the program memory226is in a computer-readable medium, preferably comprising an EEPROM module, to enable use of a general-purpose AEC to form the packet prioritization station220. The EEPROM may then be reconfigured to permit use of the AEC in a different role. The cache228is preferably an SRAM module, so as to be erasable and rewritable.

The bus206is also connected to another interrupt controller (IC)229, which enables the switching station200to interface with a traffic reduction system230, which may take the form of an ARP caching station230. As with the packet prioritization station220, the IC229may be located in the switching station200or the ARP caching station230. A bus232in the ARP caching station230is in communication with the IC229to transmit and receive data from the switching station200.

The ARP caching station, like the packet prioritization station, may be integrated into the switching station200, and may even operate using the program memory210, processor208, cache212, and bus206of the switching station200. However, like the packet prioritization station220, the ARP caching station230is preferably an independent module, which may be located on an AEC. Thus, the processor234may be a RISC processor, the program memory236may be an EEPROM module, and the cache238may be an SRAM module. The ARP caching station230and packet prioritization station220may thus both operate as independent modules in communication with the switching station200.

Referring toFIG. 6, one possible embodiment of one of the buffers204of the switching station200is shown. Packets165are queued in the buffer204for FIFO processing. A packet165may be substantially as described in connection withFIG. 4a. The MAC layer addresses170may be located within the header166at the periphery of the packet, with separate origin240and destination242MAC addresses. A designated value in the broadcast field171denotes that the packet165is to be broadcast throughout all or a specified portion of the NAN10. An IP address169is also provided. Data167may be included, or in the case of a packet such as an ARP request, no data need be sent. The footer168denotes the end of the packet.

Referring toFIG. 7, one possible embodiment of the program memory210of the switching station200is depicted. A number of executable modules designed to carry out the method of the current invention may be stored in the program memory210. As described previously, some or even all of these modules may be hard coded into an ASIC to form the processor208. However, for purposes of illustration for the following discussion, these instructions are simply represented logically as modules within some form of program memory210. The modules may be any set of one or more executable instructions to perform a function.

A packet reception module250handles operations incident to receipt of a packet from one of the ports202. A cache reading module252retrieves information from the cache212for manipulation by the processor208. A cache writing module254, similarly, writes data to the cache212for subsequent use. A packet deleting module256deletes unnecessary packets from the buffers204. A port routing module258decides which port a given packet should be sent to in order to reach its destination.

A comparison module260compares separate values or entries to determine whether they are the same, such as comparing an address form the MAC layer170of a packet165with a value in the cache212to determine whether the address has been stored in the cache212. A blocking module blocks incoming ports202with packets165routed to the same outgoing port202to permit collisions of packets165exiting the switching station200. The operation of the modules250,252,254,256,258,260, and262of the program memory210will be further clarified by the description of the method of operation of the present invention, to be provided in the description ofFIGS. 13-19.

Referring toFIG. 8, one possible embodiment of the cache212of the switching station200is shown. The cache212may contain a database264in the form of a table264associating MAC layer170addresses with ports202. A MAC layer170address is simply a location identifier, which may act as either an origin MAC address240, or a destination MAC address242. Location fields265may be provided, in which MAC addresses are stored. The MAC address simply defines a location of a communication station30that is accessible from a given port. Port fields266corresponding to the location fields265show which port202a packet165must be sent through to reach a given destination MAC address242.

Vacant fields267in the table264may be filled by retrieving the origin MAC address240from a packet165received through a port202. The origin MAC address240is recorded in a vacant location field268, and the port202through which it was received is recorded in a vacant port field269corresponding to the field268. Thus, a MAC layer170address is “bound,” or associated, with the port202through which the MAC layer170address is accessible.

Packets165may then be routed to the appropriate port202by the switching station200by looking up the destination MAC address242in the location fields265and sending the packet165through the corresponding port in the port fields266. As depicted inFIG. 8, one port202may appear several times in the port fields266because there may be switches downstream from the switching station200, so that one port202leads to many unique destination MAC addresses242.

Referring toFIG. 9, one possible embodiment of the program memory226of the packet prioritization station220is shown. As with the switching station200, instructions may be programmed in any way or even hard-wired into the processor224of the packet prioritization station. However, for the sake of discussion, instructions for the processor224are illustrated logically as modules residing in some form of program memory226.

A cache reading module270retrieves data from the cache228, while a cache writing module272stores information in the cache228for future retrieval. An incrementing module provides the ability to cyclically analyze the packets165in each of the buffers204to determine which receives priority for a given outgoing port202. A marking module276is provided to allow the packet prioritization station220to mark a given port202or packet165for priority analysis. A comparison module278compares separate values or entries to determine whether they are the same, such as comparing an address form the MAC layer170of a packet165with a value in the cache238to determine whether the address has been stored in the cache238. The operation of the modules270,272,274,276, and278will be clarified subsequently, as the method of operation of the present invention is described.

Referring toFIG. 10, one possible embodiment of the cache238of the packet prioritization station220is depicted. The cache238maintains some property pertaining to incoming packets165. This property will subsequently be used to prioritize the packets165for transmission. Preferably, the property includes a number of origin MAC addresses240that have previously sent transmissions to a destination MAC address242of the packet165. These MAC layer170addresses may be stored in the following fashion.

A database290or table290may be stored in the cache238to track destination MAC addresses242and associate them with origin MAC addresses240from which they have received packets165. Thus, destination fields292store destination MAC addresses242, while several origin fields294are associated with each destination field292. After receiving a packet165, the packet prioritization station220may determine how many origin MAC addresses240have previously sent data to the destination MAC address242of the packet165by looking up the destination MAC address242in the destination fields292and counting the origin MAC addresses240in the corresponding origin fields294.

Vacant fields296of the table290may be filled by storing destination MAC addresses242and origin MAC addresses240from packets165received by the switching station200. The packet prioritization station220may first look up the destination MAC address242from an incoming packet165in the destination fields292to determine whether it is present, and add it if it is not. The packet prioritization station220may then add the origin MAC address240from the incoming packet165to a vacant field corresponding to the destination MAC address242among the origin fields294. Thus, each destination MAC address240in the table290has at least one origin MAC address242associated with it. The number of origin fields294may be limited to permit up to a maximum number of origin MAC addresses240to be stored for each destination MAC address242, for example, 16 origins per destination.

Referring toFIG. 11, one possible embodiment of the program memory236of the ARP caching station230is shown. As with the switching station200and the packet prioritization station220, the executable modules shown in the program memory236may be configured in any suitable manner, including being hard-wired into the processor234.

A cache reading module302retrieves data from the cache238. A comparison module304, like those of the switching station200and the packet prioritization station220, compares two values to determine whether they are the same. For example, the comparison module304may compare an address form the MAC layer170of a packet165with a value in the cache238to determine whether the address has been stored in the cache238. A cache writing module306stores data in the cache238for subsequent retrieval. A packet preparation module308creates a packet in the form of an ARP response of the proper format, to be sent through one of the ports202of the switching station200. The proper format may be whatever packet architecture is currently in use on the NAN10for an ARP response. Typically, this is a packet169with some special designation to indicate that it is an ARP response. The operation of the modules302,304,306, and308will be clarified during the discussion of methods of operation, starting with the description of FIG.13.

Referring toFIG. 12, one possible embodiment of the cache238of the ARP caching station230is shown. A database310in the form of a table310maybe stored in the cache238, with IP addresses169associated with MAC layer170addresses. The table310may contain bound entries312and vacant fields314to accept new entries. IP address fields316store the IP addresses169, while associated MAC address fields318contain MAC layer170addresses corresponding to the IP addresses169.

When an ARP broadcast is received, it will take the form of a packet165with a designated IP address136corresponding to a requested MAC layer170address sought by the originator of the broadcast. The ARP caching station checks the IP address fields316to determine whether the designated IP address136is stored. If it is found, the ARP caching station may then determine whether the designated IP address136has an associated, requested MAC layer170address stored in the MAC address fields316. If so, the ARP caching station returns the requested MAC layer170address to the originator of the broadcast. If the MAC layer170address is not found in the table310, the ARP caching station220permits propagation of the packet165containing the ARP broadcast through the ports202of the switching station200.

The vacant fields314may be filled by storing IP addresses169and MAC layer170addresses from incoming packets165. For example, when a packet165is received by the switching station200, the ARP caching station230may read the IP address136from the packet165and look it up in the IP address fields316to see if it has been stored. If the IP address136has been stored, the ARP caching station220checks the MAC address fields318to determine whether a corresponding MAC layer170address has been recorded in the table310If necessary, the ARP caching station230adds the MAC layer170address to the associated field in the MAC address fields318. If the IP address136has not been stored, the ARP caching station220stores it in a vacant IP address field320. The ARP caching station then adds the MAC layer170address to the corresponding vacant MAC address field322.

Referring toFIG. 13, one embodiment of an overall method330of handling a packet according to the invention is shown. Steps and queries may be added, deleted, or rearranged, as suited to the characteristics of the NAN10. Several of the steps of the following description will be described in greater detail inFIGS. 14-19.

In a preliminary processing step332, a packet165is received and preliminarily processed by the switching station200. Then, either the processor208of the switching station200or the interrupt controller219executes an availability test334. The availability test334determines whether the packet prioritization station220is available, or not. This step of the method330is necessary because a highly-specialized ASIC-based processor208operates at comparatively high speed, on the order of 8.4 Gigahertz. A RISC-based processor224of a packet prioritization station220, on the other hand, may function at around 200 Megahertz, a speed orders of magnitude lower than that of the ASIC-based processor208.

Thus, the packet prioritization station220may only be available to accept data during certain cycles of the switching station200. If the packet prioritization station220is available, packet information, such as MAC layer170addresses, will be transmitted to the packet prioritization station220from the switching station200. The interrupt controller219preferably produces an intransitive interrupt, i.e., an interrupt that continues with the primary process regardless of the operation of the auxiliary process, for the availability test334. Thus, the switching station200continues processing of the packet165whether or not data has been sent to the packet prioritization station220.

When available, the packet prioritization station220receives and stores the origin and destination MAC addresses240,242from the packet165in a priority information storage step336. The packet prioritization station220need not store MAC layer170addresses from every single packet165received; a representative sampling is sufficient to properly prioritize outgoing packets165later in the process330. An intransitive interrupt permits the packet prioritization station to obtain such a representative sampling without slowing operation of the switching station200.

After the availability test334, a broadcast test338may be performed by the processor208, but is preferably carried out by the interrupt controller229in communication with the ARP caching station230. The broadcast test338determines whether the packet165is a broadcast. The broadcast test338is preferably of a transitive type, since the status of the packet165must be resolved before operation of the switching station200may continue. Thus, the broadcast test338interrupts the operation of the switching station200, if necessary, to process broadcast packets165.

A broadcast packet165may have a specially designated destination MAC address242, an empty destination MAC address242, or a specially designated broadcast field171. If the packet165is a broadcast, an ARP request test340is executed by the interrupt controller229, or preferably by the processor236of the ARP caching station230. If executed by the processor236, no interrupt occurs because the switching station200is still waiting for the status of the packet165to be determined. The ARP request test340determines whether the packet165is an ARP broadcast, or a broadcast requesting a requested MAC layer170address for a designated IP address136. Special designations in the MAC layer170addresses, IP address136, or data167of the packet165may be read to make this determination.

If the packet165is an ARP broadcast, the request is then processed by the ARP caching station230in an ARP request processing step341. This entails creating a response with the requested MAC layer170address if the requested MAC layer170address is in the cache238of the ARP caching station230. Otherwise, the ARP caching station230permits the ARP broadcast packet165to be broadcast.

If the packet165is a broadcast, but is not an ARP broadcast, it need not have further interaction with the ARP caching station, because it has no associated IP address136and MAC layer170address to store, and does not require an ARP response. Thus, the packet165proceeds to a packet routing step342in which the packet165returns to the switching station200for routing.

“Routing” generally refers to the process of selecting a path for a data transmission. In the context ofFIGS. 5 through 19, “routing” refers more specifically to determining which of the ports202a packet165should be sent through to reach a given destination. “Allocation” is simply the process of assigning a packet165a destination MAC address242or an IP address136denoting a destination. This may be done by using a destination MAC address242contained within the packet165. However, significant benefits may be obtained through the use of additional steps to determine where the packet165should most efficiently be sent, as described in greater detail below.

If the broadcast test338determines that the packet165is not a broadcast, the packet165will be processed by the ARP caching station230in an ARP caching step344. In the ARP caching step344, the IP address136and destination MAC address242are stored in the cache238of the ARP caching station in associated form for future use. The packet165is then routed by the switching station200in the packet routing step342.

After routing, yet a multiple routed packets test345is executed, possibly by the processor208of the switching station200, but preferably by the interrupt controller219linked to the packet prioritization station220. The multiple routed packets test345determines whether multiple packets165in the buffers204have been routed to a single outgoing port202. Like the broadcast test338, the multiple routed packets test345preferably takes the form of a transitive interrupt, because the switching station200cannot proceed to block ports202until an order for blocking has been determined. If multiple packets165are routed to a single outgoing port202, a blocking decision step346occurs in which a blocking decision is made by the packet prioritization station220to determine which packet165is sent first.

The blocking decision of the blocking decision step346may be made by assigning a high priority to packets165being sent to destination MAC addresses242with more than a threshold number of associated origin MAC addresses240in the cache228of the packet prioritization station220. The remaining packets receive a low priority. Although multiple priority gradations may be used, high and low are simple and enable rapid operation of the packet prioritization station220. Among packets165with the same priority, the blocking decision step346may unblock ports202in a round robin, or cyclical form. Unblocking is simply the process of permitting the first queued packet165in a buffer204to exit through its outgoing port202, or ports202, in the case of a broadcast.

If multiple packets165are not routed to a single outgoing port202, no special blocking decision need be made. Thus, in a round robin blocking step348, no priority need be assigned to any packet165, but unblocking of the ports202occurs in round robin, or cyclical form among all packets. Finally, after one or more ports202has been unblocked, the packet165is transmitted through the port202or ports202in a packet sending step350. The process330then begins anew with the next packet165.

Referring toFIG. 14, the preliminary processing step332is shown in greater detail. In a packet receiving step360, a packet165is received through an incoming port202and enters the associated buffer204. In an origin cached test362, the switching station200determines whether the origin MAC address240is in the location fields265of the cache212. If not, the switching station200performs a port association step364.

The port association step364may include storage of the origin MAC address240in the vacant location field268, and storage of an identifier (such as a letter) for the incoming port202in the vacant port field269. The switching station200will then be able to route response packets165back to that origin MAC address240without broadcasting the packets165through multiple ports202.

Referring toFIG. 15, the priority information storage step336is shown in greater detail. In a destination cached test370, the packet prioritization station220determines whether the destination MAC address242of the packet165is in the cache228. If the destination MAC address242is not found in the cache228, the destination MAC address242is added to the destination field292of the cache228in a destination storage step372. There is no need to proceed further, so the packet prioritization station220again becomes available in an availability step373.

If the destination MAC address242was found in the cache228, an origin associated test374determines whether the origin MAC address240of the packet165has been associated with the destination MAC address242in the origin fields294of the cache228. If not, in a vacancy test376, the packet prioritization station220checks to see if there is vacancy in the origin fields294associated with the destination MAC address242.

If there is vacancy, the packet prioritization station220performs an origin storage step378. In the origin storage step378, the origin MAC address240is added to the appropriate field of the origin fields294for the destination MAC address242. The packet prioritization station220then becomes available again in the availability step373. This also occurs if the origin MAC address240is already in the cache228, or if there is no vacancy.

Referring toFIG. 16, the ARP request processing step341is shown in greater detail. In an IP address cached test390, the ARP caching station230determines whether the designated IP address136of the packet165is in the IP address fields316of the cache238. If the designated IP address136is not found, the designated IP address136may be cached in a vacant IP address field320of the cache238in an IP address caching step392. If the designated IP address136is already present, the ARP caching station230performs an IP address bound test394to determine whether a MAC layer170address is bound to the IP address136.

If no associated MAC layer170address is found, or if the IP address136was just cached in the IP address caching step392, the ARP caching station230performs an ARP request allocating step396. In the ARP request allocating step396, the ARP broadcast165is allocated to all ports202of the switching station except the incoming port202. In effect, since the cache238does not contain the requested MAC layer170address, the ARP broadcast165is allocated for further broadcast from the switching station200.

If the requested MAC layer170address is found in the cache238, the ARP caching station230initiates a response creation step398, in which a response to the ARP broadcast165is created. The response may take the form of a packet165with the origin MAC address240of the ARP broadcast used to form the destination MAC address242of the packet165of the response. The packet165of the response has thereby been allocated to a single destination, and will only have to be sent through a single port202. The requested MAC layer170address is contained in the packet165of the response, either as the origin MAC address240, or in the data167of the packet165. Thus, the response containing the requested MAC layer170address is returned directly to the originator of the ARP broadcast.

Referring toFIG. 17, the ARP caching step344is shown in greater detail. Since the packet165is not a broadcast, as determined by the broadcast test338, it must have a destination MAC address242. Consequently, the ARP caching station230may perform a MAC address binding step402. The MAC address binding step402entails adding the destination MAC address242to the appropriate field of the MAC address fields318to bind it to the IP address169of the packet165.

The IP address169was previously cached in the IP address caching step392. Thus, the destination MAC address242may be obtained from the cache238of the ARP caching station230for response to another, subsequently received packet165containing an ARP request. In a MAC response allocation step404, the packet165may simply be assigned to the destination MAC address242from the packet165.

The cache238is preferably cleared periodically. Since IP addresses169from most ISP's are only temporary or semi-permanent, a user logging onto an Internet service provider (ISP) for a second time may have a different IP address than that of the prior session. Thus, clearing the cache238may prevent inaccuracies from building up and slowing down the NAN10. Clearing the cache238periodically also permits a smaller cache238to be used. Clearing may take place after a suitable time period, such as one day.

Referring toFIG. 18, the packet routing step342is shown in greater detail. Routing may consist of adding a tag or identifier (not shown) to the packet165in the buffer204, storing a suitable port-to-packet correlation (not shown) in the cache212, or any other method of linking one or more ports202to the packet165. In a destination cached test410, the switching station200determines whether the destination MAC address242is in the cache212of the switching station200.

This may be accomplished by looking up the destination MAC address242in the MAC address fields265of the cache212. If the destination MAC address242is not found, the switching station200has no record of which port202leads to the destination MAC address242, and must therefore route the packet165to all ports202except the incoming port202in an all ports routing step412.

If the destination MAC address242is found in the cache212, the switching station200may then determine whether the destination MAC address242is associated with the incoming port202in a destination associated test414. Thus, the switching station200may be configured to check the field of the port fields266that corresponds with the destination MAC address242from the MAC address fields265.

If the port202associated with the destination MAC address242is the incoming port202of the packet165, the packet165is already travelling through the lines and switches downstream of the port202through which it needs to be sent, so the packet165need not be sent at all. Thus, if the destination MAC address242is associated with the incoming port202, the packet165is deleted from its buffer204in a packet deleting step416. If the destination MAC address242is associated with a different port202than the incoming port202, switching station200performs an associated port routing step418, in which the packet165is routed to the associated port202.

Referring toFIG. 19, the blocking decision step346is shown in greater detail. Since the packet routing step342described previously occurs for each buffer204, several packets165have been routed to their appropriate ports202. If packets165from two or more buffers204are routed to a single port202simultaneously, the switching station200will need to block all but one of the buffers204to transmit a single packet165at a time. This must occur in sequence, until multiple buffers204no longer contain packets165routed to the same outgoing port202.

The process followed by the blocking decision step346ensures that the blocking decision is made intelligently. When a blocking decision must be made, more important packets165are prioritized for transmission. Such a decision may occur according to the process shown in FIG.19. First, in a step419, the starting port202is incremented and marked. The starting port202is the port202connected to the buffer204through which the last transmission was sent. “Incrementing” entails choosing the next port.

Incrementing may be carried out in an arbitrary, cyclical order, for example, W, then X, then Y, then Z, then W again, and so on, for the ports202shown in FIG.5. If a data transmission was just sent from the buffer204attached to a port X, incrementing the current port202causes a port Y to become the current port202. Simply incrementing the ports202in such a cyclical fashion, with no variation to account for priority, may be referred to as “cyclical,” “round robin,” or “alternating” transmission of packets165.

If no port202has priority, the packet165in the current port202is sent. Priority analysis may first be undertaken to determine whether another of the ports202should have priority over the current port202. Thus, in an incrementing and marking step420, a current port420is designated and set to be the same port202as the starting port202. The current port202is the port202under prioritization analysis.

Analysis begins in a port associated test430, in which the packet prioritization station220determines whether the destination MAC address242of the current port202has been routed to only a single outgoing port202. Thus, in the packet routing step342, if the packet165was routed to all ports202except the incoming port202, as in the all ports routing step412, the answer to the port associated test430will be “no.” If, in the packet routing step342, the packet165was routed to a single port202, as in the associated port routing step418, the port associated test430will return a “yes.”

If the answer is “no,” i.e., the packet165in the buffer204of the current port202is routed to multiple ports202, the current port202is incremented to the next port202. The net effect of the port associated test430is to pass over packets165that must be broadcast to multiple ports202to prioritize packets165with a known outgoing port202. As described above, any type of broadcast uses a comparatively greater portion of bandwidth because it must be sent along multiple routes. Thus, broadcast traffic is delayed by the step430in favor of traffic that requires less bandwidth for transmission.

After the current port202has been incremented, i.e., set to the next port202in the cycle, a cycle completed test440inquires whether the current port202has become the same as the starting port202. If so, the buffer204of the current port202is unblocked for transmission through its routed outgoing port202or ports202in a starting port unblocking step442. If not, the new current port202is analyzed by the step430. The effect of the cycle completed test440is to allow priority analysis to occur for each port202only once before a transmission is made. If no port202meets the qualifications for priority, the starting port202, i.e., the next port202in line after the previous transmission is sent, may be unblocked by the starting port unblocking step442.

If the answer to the port associated test430was “yes,” i.e., the packet165in the buffer204of the current port202is routed to a single outgoing port202, priority analysis continues on the current port202in a step450. In the step450, the packet prioritization station220determines whether four or more origin MAC addresses240are associated, or bound, to the destination MAC address242of the packet165in the buffer204of the current port202. This is accomplished by looking up the destination MAC address242of the packet165in the destination fields292of the cache228, and counting the origin MAC addresses240in the origin fields294associated with the destination MAC address242. If more than some threshold number, for example, four, origin MAC addresses240are associated with the destination MAC address242, the current port202may be unblocked to send the packet165in a current port unblocking step452. Otherwise, the packet165does not receive priority and the current port202is incremented in the current port incrementing step432to continue with priority analysis.

The effect of the multiple bound origins test450is to prioritize packets165to destination MAC addresses242that have received packets165from multiple origin MAC addresses240. This is effective because communication stations30that receive traffic from many locations have been shown to be more likely to be receiving more time-critical traffic, or to have many users. Communication stations30that receive data from only a few sources have been shown to be more likely transferring larger amounts of data, for which some delay is acceptable. Thus, the multiple bound origins test450, with the aid of the cache228maintained by the packet prioritization station220, effectively prioritizes transmission of the most important information.

“Unblocking” a port202enables transmission of the packet165in the buffer204of that port202, through its routed outgoing port202or ports202. The cycle described above occurs as many times as necessary to clear the traffic routed to one outgoing port202. When this has been accomplished, unblocking may simply occur in round robin form, i.e., cyclically unblocking ports202with no priority decision, as in the round robin blocking step348, until the need once again arises to make a blocking decision.

As with the cache238, the cache228is preferably cleared periodically. This may be necessary primarily because the usage patterns of a communication station30located at a given MAC layer170address may change over time. A communication station30may be used for a highly time-critical application one day, and then for less critical applications the next day. Clearing the cache228effectively resets the priority of communication stations30on the NAN10so that a newer and more accurate determination can be periodically made. Clearing the cache228also enables a smaller cache228to be used, because fewer MAC layer170addresses need be stored. The cache228may be cleared after a period of suitable length, such as one day.

The NAN of the present invention provides certain advantages including providing high speed (high band width) Internet access at a low cost compared to conventional technologies. Advantages of the NAN also include the capability of real-time video conferencing. The NAN allows a region such as a geographical region of otherwise unrelated entities, such as a town or neighborhood, to be networked in high speed computer communication.

The NAN may be financed at least partially by utilities in order to expedite installation and may rely on the rights of way of public utilities such as power companies. The “last mile” dilemma is also solved under the present invention, as the system allows for inexpensive installation of facilities for the “last mile” of a network infrastructure and relatively faster operation thereof. Thus, an advantage of the NAN is that it provides cost effective last mile service and delivery.

The NAN also operates at very high speeds. Preferably, message traffic is directly delivered to its destination, rather than passing the message traffic through a central server or router. Indeed, in certain embodiments, the NAN efficiencies are achieved without a central server altogether.

Additionally, the NAN provides support for a broader variety of devices and types of devices to be networked. The NAN system of the present invention does not rely on the telephone line infrastructure, and consequently eliminates handling errors that occur with user log ons. Additionally, the telephone lines and other telecommunications infrastructure receive less traffic and are less likely to be jammed with message traffic when the NAN is employed to relieve them of being overburdened. Indeed, the NAN in one embodiment achieves total independence from the telecommunication infrastructure.

Also, no modem hardware or protocol is necessary at the user facility. Conventional T-1 lines, fiber converters, and cable modems are unnecessary in achieving the much higher speeds of the NAN of the present invention. Additionally, Internet access may be provided over the NAN, and Internet connection may operate at comparatively high speeds. For instance, Internet access may in one example be as high as ten Mbps while employing certain currently available hardware.

The NAN allows free competition among Internet service providers and allows them to freely hook into the NAN system. The Internet connectivity is always on and continuous at any given communicating station without the need of a dial-up. Due to the elimination of modems in connecting to the Internet, low data losses are experienced. For instance, hand shaking errors between modems and error data that otherwise arises between modems may be reduced or eliminated. This is largely due to the absence of protocol conversions with the inventive system.

The operational hardware and software of the NAN include hubs, packets, bridges, and gateways disposed at different points to allow directly routed, packeted traffic. The system completes routing and distributes traffic at the lowest possible segment. Direct routing may be peer-to-peer rather than being controlled by a switchboard, server, or central office. The results of this arrangement is very high speed packet transfer.

The system may rely on MAC addresses and static, masqueraded, IP addressing rather than dynamic IP addressing. The system may provide a binding between a hardware device and a user so the system stores the user's public IP addresses.

Additionally, communications within the network are secure and the network is user friendly. The high-speed networking supports real-time communications with cameras. Indeed, because of the low cost, users can connect to more devices, one example of which is utility meters. The system makes remote meter reading and monitoring of other types of utility services cost effective.

The NAN of the present invention is also unique in that no network administration is necessary to control local message traffic. Traffic may be independent of any governing authority. Additionally, because the Internet is both a large scale system and localized within a geographic area, business services such as advertising can be offered locally, making them more efficient. Thus, local advertising may be directed to a local audience. The system may support interconnection with virtually any devices within a community. The system may utilize permanent IP addresses due to a unique Dynamic Host Configuration Protocol (DHCP).

The NAN10of the present invention is further distinguished from the prior art in that packet prioritization is provided for packets transmitted through the switching stations200of the NAN10. The switching stations200may prioritize traffic to destinations receiving traffic from multiple origins. This accords a generally higher priority to traffic with a higher likelihood of being time-critical, such that packets with a higher relative importance are transmitted first. All of this may be accomplished through the use of packet prioritization stations220that can be added or modified at will for use with the switching stations200.

The NAN10is further unique in that a method for reducing traffic from ARP broadcasts is provided. This may be accomplished by caching MAC layer170addresses and associating them with their corresponding IP addresses. ARP broadcast traffic is reduced by simply returning the requested MAC layer170address from the cache238. This saves a great deal of bandwidth over broadcasting multiple ARP request packets165while waiting for a response from the communication station30that has the requested MAC layer170address.