Browse Prior Art Database

Method of fast bridging in a hierarchical infrastructure-less network

IP.com Disclosure Number: IPCOM000131177D
Original Publication Date: 2005-Nov-09
Included in the Prior Art Database: 2005-Nov-09
Document File: 2 page(s) / 61K

Publishing Venue

Motorola

Related People

Ramandeep Ahuja: AUTHOR [+3]

Abstract

The paper proposes a graphical virtual addressing scheme at layer 2 to bridge packets such that the intermediate bridges do not need to perform a lookup (except the first bridge) and unlike source routing bridges, no route discovery mechanism is required.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 51% of the total text.

 

Method of fast bridging in a hierarchical infrastructure-less network

By

Ramandeep Ahuja

, Bob LoGalbo, Anthony Metke

Abstract— The paper proposes a graphical virtual addressing scheme at layer 2 to bridge packets such that the intermediate bridges do not need to perform a lookup (except the first bridge) and unlike source routing bridges, no route discovery mechanism is required.

Index Terms— Bridge, Bridging, Switch, Performance, Ad-hoc, Wireless.

I.     Introduction

A.     Problem Statement

C

urrent bridging technologies that use the spanning tree protocol (802.1d) standard involve keeping a table with addresses of nodes (all of a bridge’s child nodes) and what interface they are on. The bridge builds this table during the learning phase. The bridge performs table lookups to determine what interface to forward the frame to. The overhead of performing these lookups at each leg of the route to the destination becomes more significant as the capacity of wireless links increase and the number of child nodes of a bridge increases. 

In an ad-hoc network that is structured in a hierarchical fashion, the cost of performing lookups has an impact on the performance of the network in terms of delay especially since the peer to peer devices in an infrastructure-less may have limited processing power.

B.     Network Assumptions

This invention applies to a hierarchical wireless ad-hoc network without any Infrastructure access component. Infrastructure access here refers to access to the wired network outside the wireless network. The hierarchical wireless ad-hoc network would not have loops and all communication is assumed to be only between peer-to-peer nodes.

II.     Proposed Solution

A.     Overview

A graphical virtual addressing scheme at layer 2 is proposed to bridge packets such that the intermediate bridges do not need to perform a lookup (except the first bridge) and unlike source routing bridges, no route discovery mechanism is required.

B.     Virtual Addressing

Each node in the network would be assigned a prefix coded logical endpoint identifier such that this identifier spells out the route to the destination node. A 6 byte header would be appended to all messages. This header would be used to identify the destination logical endpoint identifier (LEI). A fixed number of bits will be assigned for each level in the hierarchy. The length of the header does not have to be fixed but can be determined per implementation and as per link capacity.

An example of such a virtual addressing scheme is shown in Figure 1. The node higher in hierarchy to a new node below it assigns the appropriate virtual address to it called a Logical Endpoint Identifier (LEI.) 

The root is elected by the spanning tree protocol or other root election algorithms.

C.     Node Movement

When a node moves to a new parent bridge, the parent assigns it a new Logical Endpoint Identifier that is topologically correct. All the nodes that are the moving nodes descendants will also be assigned appropri...