Version 5 (modified by 13 years ago) ( diff ) | ,
---|
Reference - Hierarchically-organized-multihop-mobile-wireless-networks-quality-service-support |
Check the attached document
- Address wireless networks QoS
- Link layer and network layer algorithms
- Distributed - Real Time applications
1. AIM
- Low cost
- Rapidly Deployable
- Self organizing
- No prior infrastructure ( Adhoc networking)
2. SYSTEM
(i) Location Manager : Movement of nodes within the clusters (ii) Adaptive Link Control : Perceived and desired link quality metrics (iii) QoS manager: mean value and Expected values of cluster's quality Parent ->child clusters (link state information distributed by QoS manager) n clusters: n-1 children get link state packets from this manager (iv) Multicast Manager: controls access to multicast groups and sessions extant within cluster and that quickly joins endpoints
3. ROUTING
Routing information dissemination: Link state packets
- Connectivity information
- Service information pertaining to clusters and virtual gateways
- Compute one or more feasible routes for a "session"
- based on link-state information received from other clusters
- Current location of the end point with respect to hierarchical structure
- Service requirements
NETWORK ARCHITECTURE
Nodes ---> Routers ---> clusters ----> super clusters
- Router :
- Forward packets
- Source/Destination of packets
- Peer border routers
- Virtual gateways: connect two adjacent clusters
- Virtual link (between two virtual gateways)
<<Aggregation of one or more peer border router pairs: two border routers from different clusters >>
- Role of router in a cluster
- Border
- Interior
Border router : Router that has one neighbor that does not belong to same cluster Interior router : Router that has no neighbors in different clusters ( opposite f border router)
- Node :
- source/destination of packets
Cluster formation : |
- Node ------> Registers with router ( based on some link parameters)
[Prob-01] only one router at any given time [we would need support for more than one router ??]
Q
possible if two routers inside cluster of clusters!!?
- Moves out of the reach of router >> it is affiliated with : Register with another router
- Router -------> cell head ( serves more than 1 cell/ nodes)
- Many nodes affiliate with this router and router becomes cell head for these
- routers come together ----> Clusters
- Routing and location management
Cluster ----> contains only group of routers (at lowest level)
- contains one/ more clusters as well : super cluster
- Every cluster has only one parent
- Every router belongs to exactly one cluster
Cells
- formed based on connectivity
- Number of endpoints limited (prevent traffic concentration)
- Node has link quality vector ( based on which it decides which router to associate with )
Keep these in mind |
- Bound on Size of clusters fixed --> better control and routing
- Limited number of hierarchical levels ---> prevent too many sub-optimal routes ; maintenance overhead
- Virtual gateways must be stable -->inter cluster connection stability (change in link state distribution overhead increases
Identifying network Elements
- Addresses are autonomously acquired and may change with time
- Every router and end point assumed to have globally unique identity ( lets say GUID)
- router ID
- node ID
- Cluster ID -- sequence of router ID's indicating the hierarchical relation among clusters
- router ID
level 0 cluster Address => router ID
- Node Affiliation with router : << Affiliation protocol>>
- End point activated * Node :Affiliation request -------> Router
- Build link vector * Router: Response ------------>Node (only if it can accommodate )
- selection of router
- Handshake with each of the routers in decreasing order of preference
- Link quality gets low : node restarts affiliation procedure
node may not be affiliated to "best " (closest) router but the link quality that may be acceptable
- Link state topology information :
- Link state data collected during routing: used for clustering as well
<< unlike other Distributed algorithms : Quick convergence of clustering algorithm unlike Centralized algorithms : Avoids single point of failure >>
CLUSTER DYANMICS
- Router movement
- Router birth
- Router death
cluster birth /cluster death / cluster membership change /division of cluster (cluster split) |
[A]. Cluster split : |
- Number of routers in clusters are above acceptable threshold: requires split (checked by leader/backup)
- must maintain connectivity between routers in resulting clusters
- Equalize cluster sizes
- Routers in a cluster are “ranked” in order of their router Ids (independent of the link state info)
- Lowest id router assumes leadership (Cluster Leader)
- Splitting / Merging performed by leader who sends related info to appropriate nodes (subnet of routers) to begin merge/split
- Run splitting heuristic on link state database: partition into two disjoint clusters
- broadcast info about new cluster membership
- Virtual gateway membership to every router in cluster
- Each router that gets this info updates its cluster related state appropriately *Virtual gateways are automatically born as a result of split
- Uses Graph Algorithm:
- Splits a given graph (of cluster) : S1 and S2
[B]. Cluster Merge |
- If number is less than threshold : leader checks this (Router)
- find most appropriate neighboring cluster: using the data on the cluster size available because of link state packet updates
- Sum of the size of cluster 1+ cluster 2 < cluster size split threshold (but as close as possible to preferred size: to attain equal size pattern)
- If such cluster (candidate for merge) is found: Perform merge and inform all routers involved about the change
[A]. Virtual Gateway: create/destroy/grow/split/merge /shrink |
- Create / Destroy: like above
- Distributed protocol involving handshake between routers involved in change
Periodically each router checks if it has to initiate such a procedure (how frequent indicates the sensitivity to change in network
- switch id
- Role (border/interior)
- Virtual gateway ID (if applicable) information carried of router sees a neighbor router (adjacent) and can form virtual gateway -
- Router with lower id initiates handshake to form VG
- Handshake includes selection of VG id
Attachments (1)
-
hierarchically_organised_multihop_mobile_networks.pdf
(796.6 KB
) - added by 13 years ago.
By BBN Networks
Download all attachments as: .zip